Differential D11968 Diff 33827 head/sys/kern/subr_blist.c

Changeset View

Standalone View

head/sys/kern/subr_blist.c

Show First 20 Lines • Show All 102 Lines • ▼ Show 20 Lines
#define BLIST_DEBUG		#define BLIST_DEBUG
#endif		#endif

#include <sys/types.h>		#include <sys/types.h>
#include <sys/malloc.h>		#include <sys/malloc.h>
#include <sys/sbuf.h>		#include <sys/sbuf.h>
#include <stdio.h>		#include <stdio.h>
#include <string.h>		#include <string.h>
		#include <stddef.h>
#include <stdlib.h>		#include <stdlib.h>
#include <stdarg.h>		#include <stdarg.h>
#include <stdbool.h>		#include <stdbool.h>

#define bitcount64(x) __bitcount64((uint64_t)(x))		#define bitcount64(x) __bitcount64((uint64_t)(x))
#define malloc(a,b,c) calloc(a, 1)		#define malloc(a,b,c) calloc(a, 1)
#define free(a,b) free(a)		#define free(a,b) free(a)
static __inline int imax(int a, int b) { return (a > b ? a : b); }		static __inline int imax(int a, int b) { return (a > b ? a : b); }
Show All 13 Lines
static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);		static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count,		static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count,
u_daddr_t radix);		u_daddr_t radix);
static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,		static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
blist_t dest, daddr_t count);		blist_t dest, daddr_t count);
static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count);		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 count,		static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count,
u_daddr_t radix);		u_daddr_t radix);
static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count);
#ifndef _KERNEL		#ifndef _KERNEL
static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,		static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
int tab);		int tab);
#endif		#endif

#ifdef _KERNEL		#ifdef _KERNEL
static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space");		static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space");
#endif		#endif
▲ Show 20 Lines • Show All 64 Lines • ▼ Show 20 Lines
*		*
* The smallest blist consists of a single leaf node capable of		* The smallest blist consists of a single leaf node capable of
* managing BLIST_BMAP_RADIX blocks.		* managing BLIST_BMAP_RADIX blocks.
*/		*/
blist_t		blist_t
blist_create(daddr_t blocks, int flags)		blist_create(daddr_t blocks, int flags)
{		{
blist_t bl;		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;		radix = BLIST_BMAP_RADIX;
while (radix < blocks) {		while (radix < blocks) {
		if (((last_block / radix + 1) & BLIST_META_MASK) != 0)
		/*
		* A terminator will be added. Update last_block to the
		* position just before that terminator.
		*/
		last_block \|= radix - 1;
radix *= BLIST_META_RADIX;		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)		if (bl == NULL)
return (NULL);		return (NULL);

bl->bl_blocks = blocks;		bl->bl_blocks = blocks;
bl->bl_radix = radix;		bl->bl_radix = radix;
bl->bl_cursor = 0;		bl->bl_cursor = 0;
bl->bl_root = malloc(nodes * sizeof(blmeta_t), M_SWAP, flags);
if (bl->bl_root == NULL) {		/*
free(bl, M_SWAP);		* Initialize the empty tree by filling in root values, then initialize
return (NULL);		* 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;
}		}
blst_radix_init(bl->bl_root, radix, blocks);		last_block %= radix;
		}

#if defined(BLIST_DEBUG)		#if defined(BLIST_DEBUG)
printf(		printf(
"BLIST representing %lld blocks (%lld MB of swap)"		"BLIST representing %lld blocks (%lld MB of swap)"
", requiring %lldK of ram\n",		", requiring %lldK of ram\n",
(long long)bl->bl_blocks,		(long long)bl->bl_blocks,
(long long)bl->bl_blocks * 4 / 1024,		(long long)bl->bl_blocks * 4 / 1024,
(long long)(nodes * sizeof(blmeta_t) + 1023) / 1024		(long long)(nodes * sizeof(blmeta_t) + 1023) / 1024
);		);
printf("BLIST raw radix tree contains %lld records\n",		printf("BLIST raw radix tree contains %lld records\n",
(long long)nodes);		(long long)nodes);
#endif		#endif

return (bl);		return (bl);
}		}

void		void
blist_destroy(blist_t bl)		blist_destroy(blist_t bl)
{		{
free(bl->bl_root, M_SWAP);
free(bl, M_SWAP);		free(bl, M_SWAP);
}		}

/*		/*
* blist_alloc() - reserve space in the block bitmap. Return the base		* blist_alloc() - reserve space in the block bitmap. Return the base
* of a contiguous region or SWAPBLK_NONE if space could		* of a contiguous region or SWAPBLK_NONE if space could
* not be allocated.		* not be allocated.
*/		*/
▲ Show 20 Lines • Show All 792 Lines • ▼ Show 20 Lines	while (i < skip && blk < allocBlk + count) {
nblks += blst_meta_fill(&scan[i], allocBlk, v, radix);		nblks += blst_meta_fill(&scan[i], allocBlk, v, radix);
count -= v;		count -= v;
allocBlk += v;		allocBlk += v;
blk += radix;		blk += radix;
i += next_skip;		i += next_skip;
}		}
scan->u.bmu_avail -= nblks;		scan->u.bmu_avail -= nblks;
return (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 bitmap
* 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		#ifdef BLIST_DEBUG

static void		static void
blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab)		blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab)
{		{
daddr_t i, next_skip, skip;		daddr_t i, next_skip, skip;
▲ Show 20 Lines • Show All 173 Lines • Show Last 20 Lines