Page MenuHomeFreeBSD
Files F173810674

D11906.id31798.diff
No OneTemporary
Actions

D11906.id31798.diff
View Options

Index: sys/kern/subr_blist.c
===================================================================
--- sys/kern/subr_blist.c
+++ sys/kern/subr_blist.c
@@ -92,6 +92,7 @@
#include <sys/malloc.h>
#include <sys/proc.h>
#include <sys/mutex.h>
+#include <sys/sysctl.h>
#else
@@ -101,6 +102,7 @@
#include <sys/types.h>
#include <sys/malloc.h>
+#include <sys/sbuf.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
@@ -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"

File Metadata

Mime Type
text/plain
Expires
Tue, Sep 29, 3:04 PM (18 h, 51 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
39819918
Default Alt Text
D11906.id31798.diff (6 KB)

Event Timeline