Index: sys/kern/subr_blist.c =================================================================== --- sys/kern/subr_blist.c +++ sys/kern/subr_blist.c @@ -92,6 +92,7 @@ #include #include #include +#include #else @@ -101,6 +102,7 @@ #include #include +#include #include #include #include @@ -141,6 +143,9 @@ #ifdef _KERNEL static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); +static int sysctl_subr_blist_segs(SYSCTL_HANDLER_ARGS); +SYSCTL_OID(_subr, OID_AUTO, blist_segs, CTLTYPE_STRING | CTLFLAG_RD, + NULL, 0, sysctl_subr_blist_segs, "A", "Blist Seg Info"); #endif CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0); @@ -170,6 +175,28 @@ } /* + * Use a de Bruijn sequence to find the 1 bit in a 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(daddr_t mask) +{ + const u_daddr_t magic = 0x025f9a9c5643dba3; + const unsigned char magictable[64] = { + 0, 1, 2, 42, 3, 30, 59, 43, + 39, 4, 31, 7, 60, 17, 25, 44, + 40, 57, 5, 23, 21, 32, 34, 8, + 61, 36, 18, 50, 26, 53, 45, 10, + 63, 41, 29, 58, 38, 6, 16, 24, + 56, 22, 20, 33, 35, 49, 52, 9, + 62, 28, 37, 15, 55, 19, 48, 51, + 27, 14, 54, 47, 13, 46, 12, 11, + }; + return (magictable[(mask * magic) >> 58]); +} + +/* * blist_create() - create a blist capable of handling up to the specified * number of blocks * @@ -335,7 +362,180 @@ blst_radix_print(bl->bl_root, 0, bl->bl_radix, 4); printf("}\n"); } +#endif + +struct gap_stats { + int num; /* number of gaps observed */ + u_daddr_t max; /* largest gap size */ + u_daddr_t avg; /* average gap size */ + u_daddr_t err; /* sum - num * avg */ + int histo[127]; /* counts for gaps of various sizes */ + int max_bucket; + u_daddr_t start; +}; +/* + * gap_stats_counting() - is the state 'counting 1 bits'? + * or 'skipping 0 bits'? + */ +static inline int +gap_stats_counting(struct gap_stats *stats) +{ + return (stats->start != -1); +} +/* + * init_gap_stats() - initialize stats on gap sizes + */ +static inline void +init_gap_stats(struct gap_stats *stats) +{ + int i; + stats->num = 0; + stats->max = 0; + stats->avg = 0; + stats->err = 0; + for (i = 0; i < nitems(stats->histo); i++) + stats->histo[i] = 0; + stats->max_bucket = 0; + stats->start = -1; +} +/* + * update_gap_stats() - update stats on gap sizes + */ +static void +update_gap_stats(struct gap_stats *stats, u_daddr_t posn) +{ + int id, logsize; + u_daddr_t size; + + if (!gap_stats_counting(stats)) { + stats->start = posn; + return; + } + size = posn - stats->start; + stats->start = -1; + if (size > stats->max) + stats->max = size; + if (size == 1) { + id = 0; + } else { + logsize = flsll(size) - 1; + const unsigned long long sqrt2_1 = 0x6A09E667F3BCC908ull; + id = 2 * logsize - 1; + if ((size << (64 - logsize)) > sqrt2_1) + ++id; + } + stats->histo[id]++; + if (id > stats->max_bucket) + stats->max_bucket = id; + stats->err += size - stats->avg; + ++stats->num; + stats->avg += stats->err / stats->num; + stats->err %= stats->num; +} + +/* + * dump_stats() - print stats on gap sizes + */ +static inline void +dump_gap_stats(struct sbuf *s, struct gap_stats *stats) +{ + int i; + sbuf_printf(s, "number of gaps: %d\n", stats->num); + sbuf_printf(s, "largest gap: %llu\n", stats->max); + sbuf_printf(s, "average gap size: %llu\n", stats->avg); + sbuf_printf(s, "histogram:\n"); + for (i = 0; i <= stats->max_bucket; i++) { + if (i == 0) + sbuf_printf(s, "1\t"); + else if (i % 2 == 1) + sbuf_printf(s, "%d\t", (1 << (1+i/2))); + else + sbuf_printf(s, "\t"); + sbuf_printf(s, "%d\n", stats->histo[i]); + } +} + +/* + * blist_stats() - dump radix tree stats + */ +void +blist_stats(struct sbuf *s, blist_t bl) +{ + daddr_t bit, diff, i, last_block, num_meta, 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) { + last_block = i / BLIST_BMAP_RADIX; + radix = BLIST_BMAP_RADIX; + num_meta = 0; + while ((last_block & (BLIST_META_RADIX - 1)) == 0) { + /* + * Skip meta node. + */ + last_block /= BLIST_META_RADIX; + radix *= BLIST_META_RADIX; + num_meta++; + } + while (num_meta > 0) { + 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; + } + num_meta--; + nodes++; + radix /= BLIST_META_RADIX; + } + if (num_meta == 0) { + /* + * 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); +} + +#ifdef _KERNEL +/* + * Outputs for free memory block stats + */ +static int +sysctl_subr_blist_segs(SYSCTL_HANDLER_ARGS) +{ + struct sbuf sbuf; + struct vm_phys_seg *seg; + int error, segind; + + error = sysctl_wire_old_buffer(req, 0); + if (error != 0) + return (error); + sbuf_new_for_sysctl(&sbuf, NULL, 128, req); + blist_stats(&sbuf, bl); + error = sbuf_finish(&sbuf); + sbuf_delete(&sbuf); + return (error); +} #endif /************************************************************************ @@ -978,6 +1178,7 @@ int size = 1024; int i; blist_t bl; + struct sbuf *s; for (i = 1; i < ac; ++i) { const char *ptr = av[i]; @@ -1012,6 +1213,13 @@ case 'p': blist_print(bl); 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': if (sscanf(buf + 1, "%lld", &count) == 1) { daddr_t blk = blist_alloc(bl, count); @@ -1039,6 +1247,7 @@ case 'h': puts( "p -print\n" + "s -stats\n" "a %d -allocate\n" "f %x %d -free\n" "l %x %d -fill\n"