svn commit: r324420 - in head/sys: kern sys
Alan Cox
alc at rice.edu
Mon Oct 9 18:22:20 UTC 2017
On 10/09/2017 10:54, Cy Schubert wrote:
> In message <201710082217.v98MHdNI012272 at repo.freebsd.org>, Alan Cox writes:
>> Author: alc
>> Date: Sun Oct 8 22:17:39 2017
>> New Revision: 324420
>> URL: https://svnweb.freebsd.org/changeset/base/324420
>>
>> Log:
>> The blst_radix_init function has two purposes - to compute the number of
>> nodes to allocate for the blist, and to initialize them. The computation
>> can be done much more quickly by identifying the terminating node, if any,
>> at every level of the tree and then summing the number of nodes at each
>> level that precedes the topmost terminator. The initialization can also be
>> done quickly, since settings at the root mark the tree as all-allocated, an
>> d
>> only a few terminator nodes need to be marked in the rest of the tree.
>> Eliminate blst_radix_init, and perform its two functions more simply in
>> blist_create.
>>
>> The allocation of the blist takes places in two pieces, but there's no good
>> reason to do so, when a single allocation is sufficient, and simpler.
>> Allocate the blist struct, and the array of nodes associated with it, with
>> a
>> single allocation.
>>
>> Submitted by: Doug Moore <dougm at rice.edu>
>> Reviewed by: markj (an earlier version)
>> MFC after: 1 week
>> Differential Revision: https://reviews.freebsd.org/D11968
>>
>> Modified:
>> head/sys/kern/subr_blist.c
>> head/sys/sys/blist.h
>>
>> Modified: head/sys/kern/subr_blist.c
>> =============================================================================
>> =
>> --- head/sys/kern/subr_blist.c Sun Oct 8 21:20:25 2017 (r32441
>> 9)
>> +++ head/sys/kern/subr_blist.c Sun Oct 8 22:17:39 2017 (r32442
>> 0)
>> @@ -108,6 +108,7 @@ __FBSDID("$FreeBSD$");
>> #include <sys/sbuf.h>
>> #include <stdio.h>
>> #include <string.h>
>> +#include <stddef.h>
>> #include <stdlib.h>
>> #include <stdarg.h>
>> #include <stdbool.h>
>> @@ -137,7 +138,6 @@ static void blst_copy(blmeta_t *scan, daddr_t blk, dad
>> static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count);
>> static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t coun
>> t,
>> u_daddr_t radix);
>> -static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t
>> count);
>> #ifndef _KERNEL
>> static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
>> int tab);
>> @@ -218,30 +218,69 @@ blist_t
>> blist_create(daddr_t blocks, int flags)
>> {
>> blist_t bl;
>> - daddr_t nodes, radix;
>> + daddr_t i, last_block;
>> + u_daddr_t nodes, radix, skip;
>> + int digit;
>>
>> /*
>> - * Calculate the radix field used for scanning.
>> + * Calculate the radix and node count used for scanning. Find the last
>> + * block that is followed by a terminator.
>> */
>> + last_block = blocks - 1;
>> radix = BLIST_BMAP_RADIX;
>> while (radix < blocks) {
>> + if (((last_block / radix + 1) & BLIST_META_MASK) != 0)
>> + /*
>> + * A terminator will be added. Update last_block to th
>> e
>> + * position just before that terminator.
>> + */
>> + last_block |= radix - 1;
>> radix *= BLIST_META_RADIX;
>> }
>> - nodes = 1 + blst_radix_init(NULL, radix, blocks);
>>
>> - bl = malloc(sizeof(struct blist), M_SWAP, flags);
>> + /*
>> + * Count the meta-nodes in the expanded tree, including the final
>> + * terminator, from the bottom level up to the root.
>> + */
>> + nodes = (last_block >= blocks) ? 2 : 1;
>> + last_block /= BLIST_BMAP_RADIX;
>> + while (last_block > 0) {
>> + nodes += last_block + 1;
>> + last_block /= BLIST_META_RADIX;
>> + }
>> + bl = malloc(offsetof(struct blist, bl_root[nodes]), M_SWAP, flags);
>> if (bl == NULL)
>> return (NULL);
>>
>> bl->bl_blocks = blocks;
>> bl->bl_radix = radix;
>> bl->bl_cursor = 0;
>> - bl->bl_root = malloc(nodes * sizeof(blmeta_t), M_SWAP, flags);
>> - if (bl->bl_root == NULL) {
>> - free(bl, M_SWAP);
>> - return (NULL);
>> +
>> + /*
>> + * Initialize the empty tree by filling in root values, then initialize
>> + * just the terminators in the rest of the tree.
>> + */
>> + bl->bl_root[0].bm_bighint = 0;
>> + if (radix == BLIST_BMAP_RADIX)
>> + bl->bl_root[0].u.bmu_bitmap = 0;
>> + else
>> + bl->bl_root[0].u.bmu_avail = 0;
>> + last_block = blocks - 1;
>> + i = 0;
>> + while (radix > BLIST_BMAP_RADIX) {
>> + radix /= BLIST_META_RADIX;
>> + skip = radix_to_skip(radix);
>> + digit = last_block / radix;
>> + i += 1 + digit * skip;
>> + if (digit != BLIST_META_MASK) {
>> + /*
>> + * Add a terminator.
>> + */
>> + bl->bl_root[i + skip].bm_bighint = (daddr_t)-1;
>> + bl->bl_root[i + skip].u.bmu_bitmap = 0;
>> + }
>> + last_block %= radix;
>> }
>> - blst_radix_init(bl->bl_root, radix, blocks);
>>
>> #if defined(BLIST_DEBUG)
>> printf(
>> @@ -261,7 +300,7 @@ blist_create(daddr_t blocks, int flags)
>> void
>> blist_destroy(blist_t bl)
>> {
>> - free(bl->bl_root, M_SWAP);
>> +
>> free(bl, M_SWAP);
>> }
>>
>> @@ -1070,83 +1109,6 @@ blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr
>> }
>> scan->u.bmu_avail -= nblks;
>> return (nblks);
>> -}
>> -
>> -/*
>> - * BLST_RADIX_INIT() - initialize radix tree
>> - *
>> - * Initialize our meta structures and bitmaps and calculate the exact
>> - * amount of space required to manage 'count' blocks - this space may
>> - * be considerably less than the calculated radix due to the large
>> - * RADIX values we use.
>> - */
>> -static daddr_t
>> -blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count)
>> -{
>> - daddr_t i, memindex, next_skip, skip;
>> -
>> - memindex = 0;
>> -
>> - /*
>> - * Leaf node
>> - */
>> -
>> - if (radix == BLIST_BMAP_RADIX) {
>> - if (scan) {
>> - scan->bm_bighint = 0;
>> - scan->u.bmu_bitmap = 0;
>> - }
>> - return (memindex);
>> - }
>> -
>> - /*
>> - * Meta node. If allocating the entire object we can special
>> - * case it. However, we need to figure out how much memory
>> - * is required to manage 'count' blocks, so we continue on anyway.
>> - */
>> -
>> - if (scan) {
>> - scan->bm_bighint = 0;
>> - scan->u.bmu_avail = 0;
>> - }
>> -
>> - skip = radix_to_skip(radix);
>> - next_skip = skip / BLIST_META_RADIX;
>> - radix /= BLIST_META_RADIX;
>> -
>> - for (i = 1; i < skip; i += next_skip) {
>> - if (count >= radix) {
>> - /*
>> - * Allocate the entire object
>> - */
>> - memindex = i +
>> - blst_radix_init(((scan) ? &scan[i] : NULL), radix,
>> - radix);
>> - count -= radix;
>> - } else if (count > 0) {
>> - /*
>> - * Allocate a partial object
>> - */
>> - memindex = i +
>> - blst_radix_init(((scan) ? &scan[i] : NULL), radix,
>> - count);
>> - count = 0;
>> - } else {
>> - /*
>> - * Add terminator and break out. Make terminator bitma
>> p
>> - * zero to avoid a spanning leaf allocation that
>> - * includes the terminator.
>> - */
>> - if (scan) {
>> - scan[i].bm_bighint = (daddr_t)-1;
>> - scan[i].u.bmu_bitmap = 0;
>> - }
>> - break;
>> - }
>> - }
>> - if (memindex < i)
>> - memindex = i;
>> - return (memindex);
>> }
>>
>> #ifdef BLIST_DEBUG
>>
>> Modified: head/sys/sys/blist.h
>> =============================================================================
>> =
>> --- head/sys/sys/blist.h Sun Oct 8 21:20:25 2017 (r324419)
>> +++ head/sys/sys/blist.h Sun Oct 8 22:17:39 2017 (r324420)
>> @@ -82,7 +82,7 @@ typedef struct blist {
>> daddr_t bl_blocks; /* area of coverage */
>> u_daddr_t bl_radix; /* coverage radix */
>> daddr_t bl_cursor; /* next-fit search starts at */
>> - blmeta_t *bl_root; /* root of radix tree */
>> + blmeta_t bl_root[1]; /* root of radix tree */
>> } *blist_t;
>>
>> #define BLIST_META_RADIX 16
>>
> This commit is causing this:
>
> panic: freeing invalid range
>
> On my laptop (Core i3 chip):
>
> (kgdb) bt
> #0 doadump (textdump=1) at pcpu.h:232
> #1 0xffffffff80583e16 in kern_reboot (howto=260)
> at /opt/src/svn-current/sys/kern/kern_shutdown.c:386
> #2 0xffffffff80584306 in vpanic (fmt=<value optimized out>,
> ap=<value optimized out>)
> at /opt/src/svn-current/sys/kern/kern_shutdown.c:779
> #3 0xffffffff80584123 in panic (fmt=<value optimized out>)
> at /opt/src/svn-current/sys/kern/kern_shutdown.c:710
> #4 0xffffffff805b9133 in blst_meta_free (scan=0xfffffe00045c3128,
> freeBlk=<value optimized out>, count=0, radix=<value optimized out>)
> at /opt/src/svn-current/sys/kern/subr_blist.c:869
> #5 0xffffffff805b90df in blst_meta_free (scan=0xfffffe00045c3048,
> freeBlk=<value optimized out>, count=<value optimized out>,
> radix=<value optimized out>)
> at /opt/src/svn-current/sys/kern/subr_blist.c:926
> #6 0xffffffff805b90df in blst_meta_free (scan=0xfffffe00045c3038,
> freeBlk=<value optimized out>, count=<value optimized out>,
> radix=<value optimized out>)
> at /opt/src/svn-current/sys/kern/subr_blist.c:926
> #7 0xffffffff805b90df in blst_meta_free (scan=0xfffffe00045c3028,
> freeBlk=<value optimized out>, count=<value optimized out>,
> radix=<value optimized out>)
> at /opt/src/svn-current/sys/kern/subr_blist.c:926
> #8 0xffffffff805b90df in blst_meta_free (scan=0xfffffe00045c3018,
> freeBlk=<value optimized out>, count=<value optimized out>,
> radix=<value optimized out>)
> at /opt/src/svn-current/sys/kern/subr_blist.c:926
> #9 0xffffffff808359af in swaponsomething (vp=<value optimized out>,
> id=0xfffff8000cb97200, nblks=3145727,
> strategy=0xffffffff80835c60 <swapgeom_strategy>,
> close=0xffffffff80835ee0 <swapgeom_close>, dev=132, flags=1)
> at /opt/src/svn-current/sys/vm/swap_pager.c:2199
> #10 0xffffffff8083392c in sys_swapon (td=<value optimized out>,
> uap=<value optimized out>) at /opt/src/svn-current/sys/vm/swap_pager.c:2
> 728
> #11 0xffffffff80887a11 in amd64_syscall (td=0xfffff8000c659560, traced=0)
> at subr_syscall.c:132
> #12 0xffffffff8086afcb in Xfast_syscall ()
> at /opt/src/svn-current/sys/amd64/amd64/exception.S:419
> #13 0x000000002c689aea in ?? ()
> Previous frame inner to this frame (corrupt stack?)
> Current language: auto; currently minimal
> (kgdb)
>
>
> On my gateway machine (AMD 4600+):
>
> (kgdb) bt
> #0 doadump (textdump=<value optimized out>) at pcpu.h:232
> #1 0xffffffff80573e11 in kern_reboot (howto=260)
> at /opt/src/svn-current/sys/kern/kern_shutdown.c:386
> #2 0xffffffff805742e6 in vpanic (fmt=<value optimized out>,
> ap=<value optimized out>)
> at /opt/src/svn-current/sys/kern/kern_shutdown.c:779
> #3 0xffffffff80574103 in panic (fmt=<value optimized out>)
> at /opt/src/svn-current/sys/kern/kern_shutdown.c:710
> #4 0xffffffff805a8b63 in blst_meta_free (scan=0xfffffe00021c9038,
> freeBlk=<value optimized out>, count=0, radix=<value optimized out>)
> at /opt/src/svn-current/sys/kern/subr_blist.c:869
> #5 0xffffffff805a8b0f in blst_meta_free (scan=0xfffffe00021c9028,
> freeBlk=<value optimized out>, count=<value optimized out>,
> radix=<value optimized out>)
> at /opt/src/svn-current/sys/kern/subr_blist.c:926
> #6 0xffffffff805a8b0f in blst_meta_free (scan=0xfffffe00021c9018,
> freeBlk=<value optimized out>, count=<value optimized out>,
> radix=<value optimized out>)
> at /opt/src/svn-current/sys/kern/subr_blist.c:926
> #7 0xffffffff8081becf in swaponsomething (vp=<value optimized out>,
> id=0xfffff800124d1080, nblks=262144,
> strategy=0xffffffff8081c180 <swapgeom_strategy>,
> close=0xffffffff8081c400 <swapgeom_close>, dev=101, flags=1)
> at /opt/src/svn-current/sys/vm/swap_pager.c:2199
> #8 0xffffffff80819e4c in sys_swapon (td=<value optimized out>,
> uap=<value optimized out>) at /opt/src/svn-current/sys/vm/swap_pager.c:2
> 728
> #9 0xffffffff80869fb1 in amd64_syscall (td=0xfffff80012558000, traced=0)
> at subr_syscall.c:132
> #10 0xffffffff8084dd4b in Xfast_syscall ()
> at /opt/src/svn-current/sys/amd64/amd64/exception.S:419
> #11 0x0000000800a89aea in ?? ()
> Previous frame inner to this frame (corrupt stack?)
> Current language: auto; currently minimal
> (kgdb)
>
> In the case of my laptop, it panicked only once. My gateway machine
> downstairs was in a panic reboot loop, panicking during swapon.
>
> Reverting this diff resolves my issue.
>
>
Doug Moore has provided a fix, which I just committed.
More information about the svn-src-head
mailing list