93#include <sys/kernel.h>
95#include <sys/malloc.h>
102#ifndef BLIST_NO_DEBUG
106#include <sys/errno.h>
107#include <sys/types.h>
108#include <sys/malloc.h>
118#define bitcount64(x) __bitcount64((uint64_t)(x))
119#define malloc(a,b,c) calloc(a, 1)
120#define free(a,b) free(a)
121#define ummin(a,b) ((a) < (b) ? (a) : (b))
122#define imin(a,b) ((a) < (b) ? (a) : (b))
123#define KASSERT(a,b) assert(a)
125#include <sys/blist.h>
139static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
140 blist_t dest, daddr_t
count);
145static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
153#define BLIST_MASK (BLIST_RADIX - 1)
179static inline u_daddr_t
183 return (((u_daddr_t)-1 << n) &
184 ((u_daddr_t)-1 >> (BLIST_RADIX - (n +
count))));
197 while (lo + 1 < hi) {
198 mid = (lo + hi) >> 1;
211 switch (
sizeof(
mask)) {
212#ifdef HAVE_INLINE_FFSLL
213 case sizeof(
long long):
214 return (ffsll(
mask) - 1);
216#ifdef HAVE_INLINE_FFS
218 return (ffs(
mask) - 1);
239 u_daddr_t nodes, radix;
241 KASSERT(blocks > 0, (
"invalid block count"));
247 for (radix = 1; (blocks - 1) / BLIST_RADIX / radix > 0;
248 radix *= BLIST_RADIX)
249 nodes += 1 + (blocks - 1) / BLIST_RADIX / radix;
255 if (blocks % BLIST_RADIX == 0)
258 bl =
malloc(offsetof(
struct blist, bl_root[nodes]), M_SWAP,
flags |
263 bl->bl_blocks = blocks;
264 bl->bl_radix = radix;
266#if defined(BLIST_DEBUG)
268 "BLIST representing %lld blocks (%lld MB of swap)"
269 ", requiring %lldK of ram\n",
270 (
long long)bl->bl_blocks,
271 (
long long)bl->bl_blocks * 4 / 1024,
272 (
long long)(nodes *
sizeof(blmeta_t) + 1023) / 1024
274 printf(
"BLIST raw radix tree contains %lld records\n",
300 KASSERT(*
count <= BLIST_MAX_ALLOC,
301 (
"minimum allocation too large: %d", *
count));
309 for (cursor = bl->bl_cursor;; cursor = 0) {
312 if (blk != SWAPBLK_NONE) {
313 bl->bl_avail -= *
count;
314 bl->bl_cursor = blk + *
count;
315 if (bl->bl_cursor == bl->bl_blocks)
320 return (SWAPBLK_NONE);
331 return (bl->bl_avail);
342 KASSERT(blkno >= 0 && blkno + count <= bl->bl_blocks,
343 (
"freeing invalid range: blkno %jx, count %d, blocks %jd",
344 (uintmax_t)blkno, (
int)
count, (uintmax_t)bl->bl_blocks));
346 bl->bl_avail +=
count;
360 KASSERT(blkno >= 0 && blkno + count <= bl->bl_blocks,
361 (
"filling invalid range: blkno %jx, count %d, blocks %jd",
362 (uintmax_t)blkno, (
int)
count, (uintmax_t)bl->bl_blocks));
364 bl->bl_avail -= filled;
382 if (
count > save->bl_blocks)
383 count = save->bl_blocks;
389 if (freenew && count < newbl->bl_blocks) {
401blist_print(blist_t bl)
403 printf(
"BLIST avail = %jd, cursor = %08jx {\n",
404 (uintmax_t)bl->bl_avail, (uintmax_t)bl->bl_cursor);
406 if (bl->bl_root->bm_bitmap != 0)
407 blst_radix_print(bl->bl_root, 0, bl->bl_radix, 4);
413static const u_daddr_t
fib[] = {
414 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
415 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811,
416 514229, 832040, 1346269, 2178309, 3524578,
440 return (stats->
start != SWAPBLK_NONE);
450 bzero(stats,
sizeof(*stats));
451 stats->
start = SWAPBLK_NONE;
467 size = posn - stats->
start;
468 stats->
start = SWAPBLK_NONE;
469 if (size > stats->
max)
478 while (hi < nitems(
fib) &&
fib[hi] <= size) {
482 if (hi >= nitems(
fib))
484 while (lo + 1 != hi) {
485 mid = (lo + hi) >> 1;
486 if (
fib[mid] <= size)
494 stats->
err += size - stats->
avg;
508 sbuf_printf(s,
"number of maximal free ranges: %jd\n",
509 (intmax_t)stats->
num);
510 sbuf_printf(s,
"largest free range: %jd\n", (intmax_t)stats->
max);
511 sbuf_printf(s,
"average maximal free range size: %jd\n",
512 (intmax_t)stats->
avg);
513 sbuf_printf(s,
"number of maximal free ranges of different sizes:\n");
517 if (stats->
histo[i] != 0) {
519 (intmax_t)stats->
histo[i]);
520 if (
fib[i] !=
fib[i + 1] - 1)
522 (intmax_t)
fib[i + 1] - 1);
528 if (stats->
histo[i] > 1)
530 (intmax_t)stats->
max);
543 daddr_t i, nodes, radix;
544 u_daddr_t diff,
mask;
549 radix = bl->bl_radix;
550 for (i = 0; i < bl->bl_blocks; ) {
555 if (bl->bl_root[nodes].bm_bitmap == 0) {
565 radix /= BLIST_RADIX;
571 mask = bl->bl_root[nodes].bm_bitmap;
582 i += radix * BLIST_RADIX;
588 ((i / BLIST_RADIX / radix) &
BLIST_MASK) == 0;
589 radix *= BLIST_RADIX)
624 start += BLIST_RADIX;
628 while (((++scan)->bm_bitmap & 1) == 1 &&
630 radix *= BLIST_RADIX;
631 if (~scan->bm_bitmap != 0) {
639 if (avail <
count || avail == 0) {
654 radix /= BLIST_RADIX;
656 }
while (radix != 1);
667 scan->bm_bitmap &= ~bitrange(0,
maxcount % BLIST_RADIX);
674 for (radix = BLIST_RADIX;
676 radix *= BLIST_RADIX) {
677 if ((scan--)->bm_bitmap == 0)
678 scan->bm_bitmap ^= 1;
680 if ((scan--)->bm_bitmap == 0)
682 (u_daddr_t)1 << digit;
703 int bighint, count1, hi, lo, num_shifts;
706 num_shifts = fls(count1);
707 mask = ~scan->bm_bitmap;
708 while ((
mask & (
mask + 1)) != 0 && num_shifts > 0) {
720 mask |=
mask >> ((count1 >> num_shifts) + 1) / 2;
722 bighint = count1 >> num_shifts;
728 scan->bm_bighint = bighint;
729 return (SWAPBLK_NONE);
739 scan->bm_bighint = bighint;
740 return (SWAPBLK_NONE);
762 }
else if (
maxcount <= BLIST_RADIX - lo) {
767 if (hi == BLIST_RADIX)
768 scan->bm_bighint = bighint;
771 count1 = *
count - (BLIST_RADIX - lo);
783 return (SWAPBLK_NONE);
784 *
count = BLIST_RADIX - lo + hi;
785 scan->bm_bighint = bighint;
789 scan->bm_bitmap &=
mask;
805 daddr_t blk, i, r, skip;
807 bool scan_from_start;
812 blk = cursor & -(radix * BLIST_RADIX);
813 scan_from_start = (cursor == blk);
815 mask = scan->bm_bitmap;
819 mask &= (u_daddr_t)-1 << digit;
821 return (SWAPBLK_NONE);
828 if (((
mask >> digit) & 1) == 1)
829 cursor -= digit * radix;
838 i = 1 + digit * skip;
839 if (*
count <= scan[i].bm_bighint) {
845 if (r != SWAPBLK_NONE) {
846 if (scan[i].bm_bitmap == 0)
847 scan->bm_bitmap ^=
bitrange(digit, 1);
858 if (scan_from_start && !(digit == BLIST_RADIX - 1 &&
859 scan[i].bm_bighint == BLIST_MAX_ALLOC))
860 scan->bm_bighint = *
count - 1;
862 return (SWAPBLK_NONE);
881 KASSERT((scan->bm_bitmap &
mask) == 0,
882 (
"freeing free block: %jx, size %d, mask %jx",
883 (uintmax_t)blk,
count, (uintmax_t)scan->bm_bitmap &
mask));
884 scan->bm_bitmap |=
mask;
900 daddr_t blk, endBlk, i, skip;
909 scan->bm_bighint = BLIST_MAX_ALLOC;
914 endBlk = freeBlk +
count;
915 blk = (freeBlk + radix * BLIST_RADIX) & -(radix * BLIST_RADIX);
921 endBlk = ummin(endBlk, blk);
923 blk = freeBlk & -radix;
925 endDigit = 1 + (((endBlk - 1) / radix) &
BLIST_MASK);
926 scan->bm_bitmap |=
bitrange(digit, endDigit - digit);
927 for (i = 1 + digit * skip; blk < endBlk; i += skip) {
929 count = ummin(blk, endBlk) - freeBlk;
942blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, blist_t dest,
945 daddr_t endBlk, i, skip;
952 u_daddr_t v = scan->bm_bitmap;
954 if (v == (u_daddr_t)-1) {
959 for (i = 0; i <
count; ++i) {
960 if (v & ((u_daddr_t)1 << i))
971 if (scan->bm_bitmap == 0) {
978 endBlk = blk +
count;
980 for (i = 1; blk < endBlk; i += skip) {
984 count -= blk - endBlk;
986 radix / BLIST_RADIX, dest,
count);
1006 nblks = bitcount64(scan->bm_bitmap &
mask);
1008 scan->bm_bitmap &= ~mask;
1023 daddr_t blk, endBlk, i, nblks, skip;
1029 endBlk = allocBlk +
count;
1030 blk = (allocBlk + radix * BLIST_RADIX) & -(radix * BLIST_RADIX);
1036 endBlk = ummin(endBlk, blk);
1038 blk = allocBlk & -radix;
1040 while (blk < endBlk) {
1042 i = 1 + digit * skip;
1044 count = ummin(blk, endBlk) - allocBlk;
1046 radix / BLIST_RADIX);
1047 if (scan[i].bm_bitmap == 0)
1048 scan->bm_bitmap &= ~((u_daddr_t)1 << digit);
1057blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
int tab)
1065 "%*.*s(%08llx,%lld): bitmap %0*llx big=%lld\n",
1067 (
long long)blk, (
long long)BLIST_RADIX,
1068 (
int)(1 + (BLIST_RADIX - 1) / 4),
1069 (
long long)scan->bm_bitmap,
1070 (
long long)scan->bm_bighint
1076 "%*.*s(%08llx): subtree (%lld/%lld) bitmap %0*llx big=%lld {\n",
1078 (
long long)blk, (
long long)radix * BLIST_RADIX,
1079 (
long long)radix * BLIST_RADIX,
1080 (
int)(1 + (BLIST_RADIX - 1) / 4),
1081 (
long long)scan->bm_bitmap,
1082 (
long long)scan->bm_bighint
1088 mask = scan->bm_bitmap;
1092 blst_radix_print(&scan[1 + digit * skip], blk + digit * radix,
1093 radix / BLIST_RADIX, tab);
1108main(
int ac,
char **av)
1110 daddr_t size = BLIST_RADIX * BLIST_RADIX;
1115 for (i = 1; i < ac; ++i) {
1116 const char *ptr = av[i];
1118 size = strtoll(ptr, NULL, 0);
1122 fprintf(stderr,
"Bad option: %s\n", ptr - 2);
1127 fprintf(stderr,
"blist_create failed\n");
1138 (
long long)size, (
long long)bl->bl_radix * BLIST_RADIX);
1140 if (fgets(
buf,
sizeof(
buf), stdin) == NULL)
1153 s = sbuf_new_auto();
1162 printf(
" R=%08llx, c=%08d\n",
1163 (
long long)blk,
count);
1188 "a %d %d -allocate\n"
void *() malloc(size_t size, struct malloc_type *mtp, int flags)
void free(void *addr, struct malloc_type *mtp)
daddr_t histo[nitems(fib)]
static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t cursor, int *count, int maxcount, u_daddr_t radix)
static void init_gap_stats(struct gap_stats *stats)
static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space")
static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count)
static int blst_next_leaf_alloc(blmeta_t *scan, daddr_t start, int count, int maxcount)
daddr_t blist_avail(blist_t bl)
static void dump_gap_stats(const struct gap_stats *stats, struct sbuf *s)
static bool gap_stats_counting(const struct gap_stats *stats)
blist_t blist_create(daddr_t blocks, int flags)
static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int *count, int maxcount)
static u_daddr_t bitrange(int n, int count)
void blist_destroy(blist_t bl)
static int bitpos(u_daddr_t mask)
daddr_t blist_alloc(blist_t bl, int *count, int maxcount)
void blist_resize(blist_t *pbl, daddr_t count, int freenew, int flags)
daddr_t blist_fill(blist_t bl, daddr_t blkno, daddr_t count)
static void update_gap_stats(struct gap_stats *stats, daddr_t posn)
static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, u_daddr_t radix)
void blist_stats(blist_t bl, struct sbuf *s)
void blist_free(blist_t bl, daddr_t blkno, daddr_t count)
static const u_daddr_t fib[]
static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, blist_t dest, daddr_t count)
static int generic_bitpos(u_daddr_t mask)
static daddr_t radix_to_skip(daddr_t radix)
static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, u_daddr_t radix)
static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count)
int printf(const char *fmt,...)
int sbuf_finish(struct sbuf *s)
void sbuf_delete(struct sbuf *s)
int sbuf_printf(struct sbuf *s, const char *fmt,...)
char * sbuf_data(struct sbuf *s)
int sscanf(const char *ibuf, const char *fmt,...)