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 @@ -170,6 +172,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 * @@ -337,9 +361,158 @@ 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) +{ + bzero(stats, sizeof(*stats)); + stats->start = -1; +} + +/* + * update_gap_stats() - update stats on gap sizes + */ +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) + 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); +} + /************************************************************************ * ALLOCATION SUPPORT FUNCTIONS * ************************************************************************ @@ -980,6 +1153,7 @@ int size = 1024; int i; blist_t bl; + struct sbuf *s; for (i = 1; i < ac; ++i) { const char *ptr = av[i]; @@ -1014,6 +1188,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); @@ -1041,6 +1222,7 @@ case 'h': puts( "p -print\n" + "s -stats\n" "a %d -allocate\n" "f %x %d -free\n" "l %x %d -fill\n" Index: sys/sys/blist.h =================================================================== --- sys/sys/blist.h +++ sys/sys/blist.h @@ -97,6 +97,8 @@ daddr_t blist_fill(blist_t bl, daddr_t blkno, daddr_t count); void blist_free(blist_t blist, daddr_t blkno, daddr_t count); void blist_print(blist_t blist); +struct sbuf; +void blist_stats(struct sbuf *s, blist_t bl); void blist_resize(blist_t *pblist, daddr_t count, int freenew, int flags); #endif /* _SYS_BLIST_H_ */ Index: sys/vm/swap_pager.c =================================================================== --- sys/vm/swap_pager.c +++ sys/vm/swap_pager.c @@ -166,6 +166,7 @@ SYSCTL_ULONG(_vm, OID_AUTO, swap_maxpages, CTLFLAG_RD, &swap_maxpages, 0, "Maximum amount of swap supported"); + /* bits from overcommit */ #define SWAP_RESERVE_FORCE_ON (1 << 0) #define SWAP_RESERVE_RLIMIT_ON (1 << 1) @@ -323,6 +324,9 @@ SYSCTL_PROC(_vm, OID_AUTO, swap_async_max, CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0, sysctl_swap_async_max, "I", "Maximum running async swap ops"); +static int sysctl_swap_pager_dumpstats(SYSCTL_HANDLER_ARGS); +SYSCTL_OID(_vm, OID_AUTO, swap_pager_dumpstats, CTLTYPE_STRING | CTLFLAG_RD, + NULL, 0, sysctl_swap_pager_dumpstats, "A", "Swap Pager Info"); static struct sx sw_alloc_sx; @@ -780,6 +784,30 @@ } /* + * SYSCTL_SWAP_PAGER_DUMPSTATS() - produce raw swap space stats + */ +static int +sysctl_swap_pager_dumpstats(SYSCTL_HANDLER_ARGS) +{ + struct sbuf sbuf; + int error; + struct swdevt *sp; + + error = sysctl_wire_old_buffer(req, 0); + if (error != 0) + return (error); + sbuf_new_for_sysctl(&sbuf, NULL, 128, req); + + mtx_lock(&sw_dev_mtx); + TAILQ_FOREACH(sp, &swtailq, sw_list) + blist_stats(&sbuf, sp->sw_blist); + mtx_unlock(&sw_dev_mtx); + error = sbuf_finish(&sbuf); + sbuf_delete(&sbuf); + return (error); +} + +/* * SWAP_PAGER_FREESPACE() - frees swap blocks associated with a page * range within an object. *