Context not available.
	#include <sys/kernel.h>	#include <sys/kernel.h>
	#include <sys/blist.h>	#include <sys/blist.h>
	#include <sys/malloc.h>	#include <sys/malloc.h>
		#include <sys/sbuf.h>
	#include <sys/proc.h>	#include <sys/proc.h>
	#include <sys/mutex.h>	#include <sys/mutex.h>
		alcUnsubmitted Not Done Inline Actions This should be <sys/sbuf.h> alc: This should be <sys/sbuf.h>

Context not available.

	#include <sys/types.h>	#include <sys/types.h>
	#include <sys/malloc.h>	#include <sys/malloc.h>
		#include <sys/sbuf.h>
	#include <stdio.h>	#include <stdio.h>
	#include <string.h>	#include <string.h>
	#include <stdlib.h>	#include <stdlib.h>
Context not available.
	#endif	#endif

	CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);	CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);
		#define BLIST_META_MASK (BLIST_META_RADIX - 1)

	/*	/*
	* For a subtree that can represent the state of up to 'radix' blocks, the	* For a subtree that can represent the state of up to 'radix' blocks, the
Context not available.
	{	{

	return (radix /	return (radix /
	((BLIST_BMAP_RADIX / BLIST_META_RADIX) * (BLIST_META_RADIX - 1)));	((BLIST_BMAP_RADIX / BLIST_META_RADIX) * BLIST_META_MASK));
		}

		/*
		* Use binary search to find the 1 bit in a u_daddr_t.
		* Assumes that the argument has only one bit set. ffs(x)
		* could be implemented as return (x==0? 0: 1+bitpos(x&-x)).
		*/
		static inline int
		bitpos(u_daddr_t mask)
		{
		int hi, lo, mid;

		switch (sizeof(u_daddr_t)) {
		#ifdef HAVE_INLINE_FFSLL
		case sizeof(long long):
		return (ffsll(mask) - 1);
		#endif
		default:
		lo = 0;
		hi = BLIST_BMAP_RADIX;
		while (lo + 1 < hi) {
		mid = (lo + hi) >> 1;
		if ((mask >> mid) != 0)
		lo = mid;
		else
		hi = mid;
		}
		return (lo);
		}
	}	}

	/*	/*
Context not available.

	#endif	#endif

		struct gap_stats {
		int num; /* number of gaps observed */
		alcUnsubmitted Not Done Inline Actions Insert blank line. alc: Insert blank line.
		alcUnsubmitted Not Done Inline Actions If every other block is allocated, this field can overflow. alc: If every other block is allocated, this field can overflow.
		daddr_t max; /* largest gap size */
		daddr_t avg; /* average gap size */
		daddr_t err; /* sum - num * avg */
		int histo[127]; /* counts for gaps of various sizes */
		int max_bucket;
		u_daddr_t start;
		};
		alcUnsubmitted Not Done Inline Actions Incorrect indentation. alc: Incorrect indentation.

		/*
		alcUnsubmitted Not Done Inline Actions Insert blank line. alc: Insert blank line.
		* gap_stats_counting() - is the state 'counting 1 bits'?
		* or 'skipping 0 bits'?
		*/
		static inline int
		gap_stats_counting(struct gap_stats *stats)
		{
		alcUnsubmitted Not Done Inline Actions Insert blank line. alc: Insert blank line.

		return (stats->start != -1);
		alcUnsubmitted Not Done Inline Actions Insert a blank line before the bzero(). alc: Insert a blank line before the bzero().
		}

		/*
		* init_gap_stats() - initialize stats on gap sizes
		*/
		alcUnsubmitted Done Inline Actions It is probably better to bzero() the entire structure and then initialize "start". alc: It is probably better to bzero() the entire structure and then initialize "start".
		static inline void
		init_gap_stats(struct gap_stats *stats)
		alcUnsubmitted Done Inline Actions Insert blank line. alc: Insert blank line.
		{

		bzero(stats, sizeof(*stats));
		stats->start = -1;
		}

		/*
		* update_gap_stats() - update stats on gap sizes
		alcUnsubmitted Done Inline Actions The u_daddr_t definition should come first because it is a larger data type. alc: The u_daddr_t definition should come first because it is a larger data type.
		*/
		static void
		update_gap_stats(struct gap_stats *stats, u_daddr_t posn)
		{
		u_daddr_t size;
		int id, logsize;

		if (!gap_stats_counting(stats)) {
		stats->start = posn;
		return;
		}
		size = posn - stats->start;
		stats->start = -1;

		if (size > stats->max)
		alcUnsubmitted Not Done Inline Actions This will probably need to change, but it can wait for a future revision. alc: This will probably need to change, but it can wait for a future revision.
		stats->max = size;
		if (size == 1) {
		id = 0;
		alcUnsubmitted Done Inline Actions Use postfix instead. alc: Use postfix instead.
		} else {
		logsize = 1;
		while ((size >> logsize) > 1)
		logsize++;
		id = 2 * logsize - 1;
		if (size >> (logsize - 1) >= 3)
		alcUnsubmitted Done Inline Actions Use postfix. alc: Use postfix.
		id++;
		}
		stats->histo[id]++;
		if (id > stats->max_bucket)
		stats->max_bucket = id;
		stats->err += (daddr_t)size - stats->avg;
		stats->num++;
		stats->avg += stats->err / stats->num;
		stats->err %= stats->num;
		}

		alcUnsubmitted Done Inline Actions Insert blank line. alc: Insert blank line.
		alcUnsubmitted Not Done Inline Actions You need to use "%ju" and uintmax_t. alc: You need to use "%ju" and uintmax_t.
		/*
		* dump_stats() - print stats on gap sizes
		*/
		static inline void
		dump_gap_stats(struct sbuf s, struct gap_stats stats)
		{
		int i, val;

		sbuf_printf(s, "number of gaps: %d\n", stats->num);
		alcUnsubmitted Done Inline Actions The outermost parens around the expression are not needed. Spaces are required around binary operators. alc: The outermost parens around the expression are not needed. Spaces are required around binary…
		sbuf_printf(s, "largest gap: %jd\n", (intmax_t)stats->max);
		sbuf_printf(s, "average gap size: %jd\n", (intmax_t)stats->avg);
		sbuf_printf(s, "histogram:\n");
		for (i = 0; i <= stats->max_bucket; i++) {
		val = (i == 0) ? 1 : ((3 - i % 2) << ((i - 1) / 2));
		sbuf_printf(s, "%d\t%d\n", val, stats->histo[i]);
		}
		}

		/*
		* blist_stats() - dump radix tree stats
		alcUnsubmitted Not Done Inline Actions This needs to be declared in blist.h. alc: This needs to be declared in blist.h.
		*/
		void
		blist_stats(struct sbuf *s, blist_t bl)
		{
		alcUnsubmitted Done Inline Actions The struct should come first. alc: The struct should come first.
		daddr_t bit, diff, i, nodes, radix;
		u_daddr_t mask;
		struct gap_stats stats;

		init_gap_stats(&stats);
		nodes = 0;
		i = bl->bl_radix;
		while (i < bl->bl_radix + bl->bl_blocks) {
		radix = BLIST_BMAP_RADIX;
		while (((i / radix) & BLIST_META_MASK) == 0) {
		/*
		* Skip meta node.
		*/
		radix *= BLIST_META_RADIX;
		}
		while (radix > BLIST_BMAP_RADIX) {
		if (bl->bl_root[nodes].u.bmu_avail == 0) {
		if (gap_stats_counting(&stats))
		update_gap_stats(&stats, i);
		break;
		}
		if (bl->bl_root[nodes].u.bmu_avail == radix) {
		if (!gap_stats_counting(&stats))
		update_gap_stats(&stats, i);
		break;
		}
		nodes++;
		radix /= BLIST_META_RADIX;
		}
		if (radix == BLIST_BMAP_RADIX) {
		/*
		* Scan leaf.
		*/
		mask = bl->bl_root[nodes].u.bmu_bitmap;
		diff = mask ^ (mask << 1);
		diff ^= gap_stats_counting(&stats);
		while (diff) {
		bit = diff & -diff;
		update_gap_stats(&stats, i + bitpos(bit));
		diff ^= bit;
		}
		}
		nodes += radix_to_skip(radix);
		i += radix;
		}
		update_gap_stats(&stats, i);
		dump_gap_stats(s, &stats);
		}

	/************************************************************************	/************************************************************************
	* ALLOCATION SUPPORT FUNCTIONS *	* ALLOCATION SUPPORT FUNCTIONS *
	************************************************************************	************************************************************************
		alcUnsubmitted Not Done Inline Actions This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy(), or swp_pager_freeswapspace(). alc: This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy…
Context not available.
	*	*
	* This is the core of the allocator and is optimized for the	* This is the core of the allocator and is optimized for the
	* BLIST_BMAP_RADIX block allocation case. Otherwise, execution	* BLIST_BMAP_RADIX block allocation case. Otherwise, execution
	* time is proportional to log2(count) + log2(BLIST_BMAP_RADIX).	* time is proportional to log2(count) + bitpos time.
	*/	*/
	static daddr_t	static daddr_t
	blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)	blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)
	{	{
	u_daddr_t mask;	u_daddr_t mask;
	int count1, hi, lo, mid, num_shifts, range1, range_ext;	int count1, lo, num_shifts, range1, range_ext;

	if (count == BLIST_BMAP_RADIX) {	if (count == BLIST_BMAP_RADIX) {
	/*	/*
Context not available.
	/*	/*
	* The least significant set bit in mask marks the start of the first	* The least significant set bit in mask marks the start of the first
	* available range of sufficient size. Clear all the bits but that one,	* available range of sufficient size. Clear all the bits but that one,
	* and then perform a binary search to find its position.	* and then find its position.
	*/	*/
	mask &= -mask;	mask &= -mask;
	hi = BLIST_BMAP_RADIX - count1;	lo = bitpos(mask);
	while (lo + 1 < hi) {
	mid = (lo + hi) >> 1;
	if ((mask >> mid) != 0)
	lo = mid;
	else
	hi = mid;
	}

	/*	/*
	* Set in mask exactly the bits being allocated, and clear them from	* Set in mask exactly the bits being allocated, and clear them from
Context not available.
	int size = 1024;	int size = 1024;
	int i;	int i;
	blist_t bl;	blist_t bl;
		struct sbuf *s;

	for (i = 1; i < ac; ++i) {	for (i = 1; i < ac; ++i) {
	const char *ptr = av[i];	const char *ptr = av[i];
Context not available.
	case 'p':	case 'p':
	blist_print(bl);	blist_print(bl);
	break;	break;
		case 's':
		s = sbuf_new_auto();
		blist_stats(s, bl);
		sbuf_finish(s);
		printf("%s", sbuf_data(s));
		sbuf_delete(s);
		break;
	case 'a':	case 'a':
	if (sscanf(buf + 1, "%lld", &count) == 1) {	if (sscanf(buf + 1, "%lld", &count) == 1) {
	daddr_t blk = blist_alloc(bl, count);	daddr_t blk = blist_alloc(bl, count);
Context not available.
	case 'h':	case 'h':
	puts(	puts(
	"p -print\n"	"p -print\n"
		"s -stats\n"
	"a %d -allocate\n"	"a %d -allocate\n"
	"f %x %d -free\n"	"f %x %d -free\n"
	"l %x %d -fill\n"	"l %x %d -fill\n"
Context not available.

View Options

sys/sys/ucred.h

Context not available.
	#include <sys/kernel.h>	#include <sys/kernel.h>
	#include <sys/blist.h>	#include <sys/blist.h>
	#include <sys/malloc.h>	#include <sys/malloc.h>
		#include <sys/sbuf.h>
	#include <sys/proc.h>	#include <sys/proc.h>
	#include <sys/mutex.h>	#include <sys/mutex.h>
		alcUnsubmitted Not Done Inline Actions This should be <sys/sbuf.h> alc: This should be <sys/sbuf.h>

Context not available.

	#include <sys/types.h>	#include <sys/types.h>
	#include <sys/malloc.h>	#include <sys/malloc.h>
		#include <sys/sbuf.h>
	#include <stdio.h>	#include <stdio.h>
	#include <string.h>	#include <string.h>
	#include <stdlib.h>	#include <stdlib.h>
Context not available.
	#endif	#endif

	CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);	CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);
		#define BLIST_META_MASK (BLIST_META_RADIX - 1)

	/*	/*
	* For a subtree that can represent the state of up to 'radix' blocks, the	* For a subtree that can represent the state of up to 'radix' blocks, the
Context not available.
	{	{

	return (radix /	return (radix /
	((BLIST_BMAP_RADIX / BLIST_META_RADIX) * (BLIST_META_RADIX - 1)));	((BLIST_BMAP_RADIX / BLIST_META_RADIX) * BLIST_META_MASK));
		}

		/*
		* Use binary search to find the 1 bit in a u_daddr_t.
		* Assumes that the argument has only one bit set. ffs(x)
		* could be implemented as return (x==0? 0: 1+bitpos(x&-x)).
		*/
		static inline int
		bitpos(u_daddr_t mask)
		{
		int hi, lo, mid;

		switch (sizeof(u_daddr_t)) {
		#ifdef HAVE_INLINE_FFSLL
		case sizeof(long long):
		return (ffsll(mask) - 1);
		#endif
		default:
		lo = 0;
		hi = BLIST_BMAP_RADIX;
		while (lo + 1 < hi) {
		mid = (lo + hi) >> 1;
		if ((mask >> mid) != 0)
		lo = mid;
		else
		hi = mid;
		}
		return (lo);
		}
	}	}

	/*	/*
Context not available.

	#endif	#endif

		struct gap_stats {
		int num; /* number of gaps observed */
		alcUnsubmitted Not Done Inline Actions Insert blank line. alc: Insert blank line.
		alcUnsubmitted Not Done Inline Actions If every other block is allocated, this field can overflow. alc: If every other block is allocated, this field can overflow.
		daddr_t max; /* largest gap size */
		daddr_t avg; /* average gap size */
		daddr_t err; /* sum - num * avg */
		int histo[127]; /* counts for gaps of various sizes */
		int max_bucket;
		u_daddr_t start;
		};
		alcUnsubmitted Not Done Inline Actions Incorrect indentation. alc: Incorrect indentation.

		/*
		alcUnsubmitted Not Done Inline Actions Insert blank line. alc: Insert blank line.
		* gap_stats_counting() - is the state 'counting 1 bits'?
		* or 'skipping 0 bits'?
		*/
		static inline int
		gap_stats_counting(struct gap_stats *stats)
		{
		alcUnsubmitted Not Done Inline Actions Insert blank line. alc: Insert blank line.

		return (stats->start != -1);
		alcUnsubmitted Not Done Inline Actions Insert a blank line before the bzero(). alc: Insert a blank line before the bzero().
		}

		/*
		* init_gap_stats() - initialize stats on gap sizes
		*/
		alcUnsubmitted Done Inline Actions It is probably better to bzero() the entire structure and then initialize "start". alc: It is probably better to bzero() the entire structure and then initialize "start".
		static inline void
		init_gap_stats(struct gap_stats *stats)
		alcUnsubmitted Done Inline Actions Insert blank line. alc: Insert blank line.
		{

		bzero(stats, sizeof(*stats));
		stats->start = -1;
		}

		/*
		* update_gap_stats() - update stats on gap sizes
		alcUnsubmitted Done Inline Actions The u_daddr_t definition should come first because it is a larger data type. alc: The u_daddr_t definition should come first because it is a larger data type.
		*/
		static void
		update_gap_stats(struct gap_stats *stats, u_daddr_t posn)
		{
		u_daddr_t size;
		int id, logsize;

		if (!gap_stats_counting(stats)) {
		stats->start = posn;
		return;
		}
		size = posn - stats->start;
		stats->start = -1;

		if (size > stats->max)
		alcUnsubmitted Not Done Inline Actions This will probably need to change, but it can wait for a future revision. alc: This will probably need to change, but it can wait for a future revision.
		stats->max = size;
		if (size == 1) {
		id = 0;
		alcUnsubmitted Done Inline Actions Use postfix instead. alc: Use postfix instead.
		} else {
		logsize = 1;
		while ((size >> logsize) > 1)
		logsize++;
		id = 2 * logsize - 1;
		if (size >> (logsize - 1) >= 3)
		alcUnsubmitted Done Inline Actions Use postfix. alc: Use postfix.
		id++;
		}
		stats->histo[id]++;
		if (id > stats->max_bucket)
		stats->max_bucket = id;
		stats->err += (daddr_t)size - stats->avg;
		stats->num++;
		stats->avg += stats->err / stats->num;
		stats->err %= stats->num;
		}

		alcUnsubmitted Done Inline Actions Insert blank line. alc: Insert blank line.
		alcUnsubmitted Not Done Inline Actions You need to use "%ju" and uintmax_t. alc: You need to use "%ju" and uintmax_t.
		/*
		* dump_stats() - print stats on gap sizes
		*/
		static inline void
		dump_gap_stats(struct sbuf s, struct gap_stats stats)
		{
		int i, val;

		sbuf_printf(s, "number of gaps: %d\n", stats->num);
		alcUnsubmitted Done Inline Actions The outermost parens around the expression are not needed. Spaces are required around binary operators. alc: The outermost parens around the expression are not needed. Spaces are required around binary…
		sbuf_printf(s, "largest gap: %jd\n", (intmax_t)stats->max);
		sbuf_printf(s, "average gap size: %jd\n", (intmax_t)stats->avg);
		sbuf_printf(s, "histogram:\n");
		for (i = 0; i <= stats->max_bucket; i++) {
		val = (i == 0) ? 1 : ((3 - i % 2) << ((i - 1) / 2));
		sbuf_printf(s, "%d\t%d\n", val, stats->histo[i]);
		}
		}

		/*
		* blist_stats() - dump radix tree stats
		alcUnsubmitted Not Done Inline Actions This needs to be declared in blist.h. alc: This needs to be declared in blist.h.
		*/
		void
		blist_stats(struct sbuf *s, blist_t bl)
		{
		alcUnsubmitted Done Inline Actions The struct should come first. alc: The struct should come first.
		daddr_t bit, diff, i, nodes, radix;
		u_daddr_t mask;
		struct gap_stats stats;

		init_gap_stats(&stats);
		nodes = 0;
		i = bl->bl_radix;
		while (i < bl->bl_radix + bl->bl_blocks) {
		radix = BLIST_BMAP_RADIX;
		while (((i / radix) & BLIST_META_MASK) == 0) {
		/*
		* Skip meta node.
		*/
		radix *= BLIST_META_RADIX;
		}
		while (radix > BLIST_BMAP_RADIX) {
		if (bl->bl_root[nodes].u.bmu_avail == 0) {
		if (gap_stats_counting(&stats))
		update_gap_stats(&stats, i);
		break;
		}
		if (bl->bl_root[nodes].u.bmu_avail == radix) {
		if (!gap_stats_counting(&stats))
		update_gap_stats(&stats, i);
		break;
		}
		nodes++;
		radix /= BLIST_META_RADIX;
		}
		if (radix == BLIST_BMAP_RADIX) {
		/*
		* Scan leaf.
		*/
		mask = bl->bl_root[nodes].u.bmu_bitmap;
		diff = mask ^ (mask << 1);
		diff ^= gap_stats_counting(&stats);
		while (diff) {
		bit = diff & -diff;
		update_gap_stats(&stats, i + bitpos(bit));
		diff ^= bit;
		}
		}
		nodes += radix_to_skip(radix);
		i += radix;
		}
		update_gap_stats(&stats, i);
		dump_gap_stats(s, &stats);
		}

	/************************************************************************	/************************************************************************
	* ALLOCATION SUPPORT FUNCTIONS *	* ALLOCATION SUPPORT FUNCTIONS *
	************************************************************************	************************************************************************
		alcUnsubmitted Not Done Inline Actions This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy(), or swp_pager_freeswapspace(). alc: This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy…
Context not available.
	*	*
	* This is the core of the allocator and is optimized for the	* This is the core of the allocator and is optimized for the
	* BLIST_BMAP_RADIX block allocation case. Otherwise, execution	* BLIST_BMAP_RADIX block allocation case. Otherwise, execution
	* time is proportional to log2(count) + log2(BLIST_BMAP_RADIX).	* time is proportional to log2(count) + bitpos time.
	*/	*/
	static daddr_t	static daddr_t
	blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)	blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)
	{	{
	u_daddr_t mask;	u_daddr_t mask;
	int count1, hi, lo, mid, num_shifts, range1, range_ext;	int count1, lo, num_shifts, range1, range_ext;

	if (count == BLIST_BMAP_RADIX) {	if (count == BLIST_BMAP_RADIX) {
	/*	/*
Context not available.
	/*	/*
	* The least significant set bit in mask marks the start of the first	* The least significant set bit in mask marks the start of the first
	* available range of sufficient size. Clear all the bits but that one,	* available range of sufficient size. Clear all the bits but that one,
	* and then perform a binary search to find its position.	* and then find its position.
	*/	*/
	mask &= -mask;	mask &= -mask;
	hi = BLIST_BMAP_RADIX - count1;	lo = bitpos(mask);
	while (lo + 1 < hi) {
	mid = (lo + hi) >> 1;
	if ((mask >> mid) != 0)
	lo = mid;
	else
	hi = mid;
	}

	/*	/*
	* Set in mask exactly the bits being allocated, and clear them from	* Set in mask exactly the bits being allocated, and clear them from
Context not available.
	int size = 1024;	int size = 1024;
	int i;	int i;
	blist_t bl;	blist_t bl;
		struct sbuf *s;

	for (i = 1; i < ac; ++i) {	for (i = 1; i < ac; ++i) {
	const char *ptr = av[i];	const char *ptr = av[i];
Context not available.
	case 'p':	case 'p':
	blist_print(bl);	blist_print(bl);
	break;	break;
		case 's':
		s = sbuf_new_auto();
		blist_stats(s, bl);
		sbuf_finish(s);
		printf("%s", sbuf_data(s));
		sbuf_delete(s);
		break;
	case 'a':	case 'a':
	if (sscanf(buf + 1, "%lld", &count) == 1) {	if (sscanf(buf + 1, "%lld", &count) == 1) {
	daddr_t blk = blist_alloc(bl, count);	daddr_t blk = blist_alloc(bl, count);
Context not available.
	case 'h':	case 'h':
	puts(	puts(
	"p -print\n"	"p -print\n"
		"s -stats\n"
	"a %d -allocate\n"	"a %d -allocate\n"
	"f %x %d -free\n"	"f %x %d -free\n"
	"l %x %d -fill\n"	"l %x %d -fill\n"
Context not available.

cred: Make group_is_supplementary() public; New group_is_primary()ClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 144206

sys/kern/kern_prot.c

sys/sys/ucred.h

cred: Make group_is_supplementary() public; New group_is_primary()
ClosedPublic
Actions

Revision Contents
Changeset List