Date: Mon, 09 Oct 2017 08:54:10 -0700 From: Cy Schubert <Cy.Schubert@komquats.com> To: Alan Cox <alc@FreeBSD.org> Cc: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r324420 - in head/sys: kern sys Message-ID: <201710091554.v99FsAjK002950@slippy.cwsent.com> In-Reply-To: Message from Alan Cox <alc@FreeBSD.org> of "Sun, 08 Oct 2017 22:17:39 -0000." <201710082217.v98MHdNI012272@repo.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
In message <201710082217.v98MHdNI012272@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@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. -- Cheers, Cy Schubert <Cy.Schubert@cschubert.com> FreeBSD UNIX: <cy@FreeBSD.org> Web: http://www.FreeBSD.org The need of the many outweighs the greed of the few.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201710091554.v99FsAjK002950>