Date: Mon, 9 Oct 2017 13:22:09 -0500 From: Alan Cox <alc@rice.edu> To: Cy Schubert <Cy.Schubert@komquats.com>, 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: <bfc3c88c-d5ed-2b36-b0f2-3c204c6d95b3@rice.edu> In-Reply-To: <201710091554.v99FsAjK002950@slippy.cwsent.com> References: <201710091554.v99FsAjK002950@slippy.cwsent.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 10/09/2017 10:54, Cy Schubert wrote: > 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. > > Doug Moore has provided a fix, which I just committed.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?bfc3c88c-d5ed-2b36-b0f2-3c204c6d95b3>