Skip site navigation (1)Skip section navigation (2)
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>