Count the total number of touched pages.

6 files changed, 136 insertions, 12 deletions

diff --git a/Makefile.am b/Makefile.am
index 8cc151b..7f5390d 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -3,6 +3,8 @@ lib_LTLIBRARIES = lwp.la
 
 memfault_gui_SOURCES = src/memfault.h \
 		       src/app.c \
+		       src/block.h \
+		       src/block.c \
 		       src/blockmap.c \
 		       src/timeline.c \
 		       src/allocators.c \
diff --git a/src/allocators.c b/src/allocators.c
index c88603e..ba8a618 100644
--- a/src/allocators.c
+++ b/src/allocators.c
@@ -374,7 +374,7 @@ _sum_allocators_compute_pages_hierachically (struct _sum_allocator *sum,
 					     gulong count)
 {
     struct pages {
-	guint pages[1024];
+	guint32 pages[1024];
     } **pdt, *pde;
     guint n, per_level;
 
@@ -430,15 +430,15 @@ static void
 _sum_allocators_add_to_array (struct _sum_allocator *sum, GPtrArray *array)
 {
     guint pagesize = sysconf (_SC_PAGESIZE);
-    guint pages[1024];
-    gulong n = (sum->max - sum->min + 32) / 32;
+    guint32 pages[1024];
+    gulong n = ((sum->max - sum->min) / pagesize + 32) & ~31;
 
     g_ptr_array_add (array, sum);
 
-    if (n > G_N_ELEMENTS (pages))
+    if (n > 32 * G_N_ELEMENTS (pages))
 	return _sum_allocators_compute_pages_hierachically (sum, pagesize, n);
 
-    memset (pages, 0, n);
+    memset (pages, 0, n / 8);
     for (n = 0; n < sum->count; n++) {
 	Block *block = sum->blocks[n];
 	gulong p = (block->addr - sum->min) / pagesize;
@@ -448,7 +448,7 @@ _sum_allocators_add_to_array (struct _sum_allocator *sum, GPtrArray *array)
 		pages [p / 32] |= 1 << (p & 31);
 		sum->n_pages++;
 	    }
-	} while (++p < last_page);
+	} while (++p <= last_page);
     }
 }
 
@@ -466,6 +466,7 @@ allocators_set_blocks (Allocators *self, Block *blocks)
     GtkTreeIter iter;
     gint index[1];
     struct _sum_allocator *sum, *sums;
+    gulong pagesize = sysconf (_SC_PAGESIZE);
     guint n, count, old_len;
     gint *new_order;
     GPtrArray *allocators;
@@ -525,6 +526,8 @@ allocators_set_blocks (Allocators *self, Block *blocks)
 	count++;
     }
     store->sums = sums;
+    sum->min &= ~(pagesize - 1);
+    sum->max = (sum->max + pagesize) & ~(pagesize - 1);
 
     self->blocks_mem = g_renew (Block *, self->blocks_mem, count);
     block_mem = self->blocks_mem;
diff --git a/src/app.c b/src/app.c
index c8f473f..ecc4670 100644
--- a/src/app.c
+++ b/src/app.c
@@ -11,6 +11,7 @@
 #include <errno.h>
 
 #include "memfault.h"
+#include "block.h"
 #include "callgraph.h"
 #include "frames.h"
 #include "procmap.h"
@@ -563,6 +564,9 @@ app_update_status (App *app)
     gchar active_bytes[80];
     gchar n_frames[80];
     gchar n_unique_frames[80];
+    gulong n_pages;
+    gsize n_bytes;
+    gfloat fragmentation;
     char *txt;
     gint len;
 
@@ -583,8 +587,8 @@ app_update_status (App *app)
 			  _client_get_number_of_blocks (&app->client));
 	pretty_print_number (n_blocks, len, n_blocks + 40);
 
-	len = g_snprintf (active_bytes, 40, "%" G_GSIZE_FORMAT,
-			  _client_count_active_bytes (&app->client));
+	n_bytes = _client_count_active_bytes (&app->client);
+	len = g_snprintf (active_bytes, 40, "%" G_GSIZE_FORMAT, n_bytes);
 	pretty_print_number (active_bytes, len, active_bytes + 40);
 
 	len = g_snprintf (n_frames, 40, "%u",
@@ -595,10 +599,14 @@ app_update_status (App *app)
 		          _client_get_number_of_frames (&app->client));
 	pretty_print_number (n_unique_frames, len, n_unique_frames + 40);
 
-	txt = g_strdup_printf ("%s: %.1fs, %s bytes over %s allocations, %s allocators, %s active blocks [%s bytes], %s [%s unique] frames.",
+	n_pages = blocks_count_pages (app->client.blocks);
+	n_pages *= sysconf (_SC_PAGESIZE);
+	fragmentation = (n_pages - n_bytes) * 100. / n_pages;
+
+	txt = g_strdup_printf ("%s: %.1fs, %s bytes over %s allocations, %s allocators, %s active blocks [%s bytes (%.1f %%)], %s [%s unique] frames.",
 		app->client.name, app->client.last / 1000.,
 		bytes + 80, n_allocs + 40, n_allocators + 40,
-		n_blocks + 40, active_bytes + 40,
+		n_blocks + 40, active_bytes + 40, fragmentation,
 		n_frames + 40, n_unique_frames + 40);
     } else if (! app->client.terminated) {
 	txt = g_strdup_printf ("%s: running.", app->client.name);
diff --git a/src/block.c b/src/block.c
new file mode 100644
index 0000000..0d9d68f
--- /dev/null
+++ b/src/block.c
@@ -0,0 +1,102 @@
+#include <gtk/gtk.h>
+#include <unistd.h>
+#include <string.h>
+
+#include "block.h"
+
+static guint
+_log2 (gulong n)
+{
+    guint i = 0;
+    while (1U<<i < n)
+	i++;
+    return i;
+}
+
+gulong
+blocks_count_pages (const Block *blocks)
+{
+    struct meta {
+	gulong base;
+	struct meta *next;
+	guint32 pages[128];
+    } *meta[671];
+    const gulong per_meta = 32 * G_N_ELEMENTS (meta[0]->pages);
+    gulong pagesize = sysconf (_SC_PAGESIZE);
+    guint page_shift = _log2 (pagesize);
+    guint meta_shift = _log2 (per_meta);
+    const Block *b;
+    gulong n_pages;
+    guint n;
+
+    memset (meta, 0, sizeof (meta));
+
+    n_pages = 0;
+    for (b = blocks; b != NULL; b = b->next) {
+	guint index;
+	gulong p = b->addr >> page_shift;
+	gulong last_page = (b->addr + b->size) >> page_shift;
+	gulong base = p & ~(per_meta - 1);
+	guint32 *pages;
+	struct meta *m;
+
+	index = (base >> meta_shift) % G_N_ELEMENTS (meta);
+	for (m = meta[index]; m != NULL; m = m->next)
+	    if (m->base == base)
+		break;
+	if (m == NULL) {
+	    struct meta *next = m;
+
+	    m = g_try_new0 (struct meta, 1);
+	    if (m == NULL)
+		goto BAIL;
+
+	    m->base = base;
+	    m->next = meta[index];
+	    meta[index] = m;
+	}
+
+	pages = m->pages;
+	do {
+	    guint po = p - base;
+	    if ((pages[po / 32] & (1 << (po & 31 ))) == 0) {
+		pages[po / 32] |= 1 << (po & 31);
+		n_pages++;
+	    }
+	    if (++p > last_page)
+		break;
+
+	    if ((p & (per_meta - 1)) == 0) {
+		base += per_meta;
+		index = (index + 1) % G_N_ELEMENTS (meta);
+		for (m = meta[index]; m != NULL; m = m->next)
+		    if (m->base == base)
+			break;
+		if (m == NULL) {
+		    struct meta *next = m;
+
+		    m = g_try_new0 (struct meta, 1);
+		    if (m == NULL)
+			goto BAIL;
+
+		    m->base = base;
+		    m->next = meta[index];
+		    meta[index] = m;
+		}
+
+		pages = m->pages;
+	    }
+	} while (TRUE);
+    }
+
+BAIL:
+    for (n = 0; n < G_N_ELEMENTS (meta); n++) {
+	while (meta[n] != NULL) {
+	    struct meta *m = meta[n];
+	    meta[n] = m->next;
+	    g_free (m);
+	}
+    }
+
+    return n_pages;
+}
diff --git a/src/block.h b/src/block.h
new file mode 100644
index 0000000..2355d53
--- /dev/null
+++ b/src/block.h
@@ -0,0 +1,9 @@
+#ifndef BLOCK_H
+#define BLOCK_H
+
+#include "memfault.h"
+
+gulong
+blocks_count_pages (const Block *block);
+
+#endif /* BLOCK_H */
diff --git a/src/blockmap.c b/src/blockmap.c
index fe5ccd7..adc45bb 100644
--- a/src/blockmap.c
+++ b/src/blockmap.c
@@ -13,7 +13,7 @@ struct _block_map {
     gdouble aspect;
     guint width, height;
     gulong min, max, pages;
-    guint pagesize;
+    gulong pagesize;
 
     Block *blocks;
     cairo_pattern_t *pattern;
@@ -57,7 +57,7 @@ block_map_construct (BlockMap *self)
     gulong width;
     gulong height;
     guint stride;
-    guint pagesize;
+    gulong pagesize;
     GSList *l;
 
     pagesize = sysconf (_SC_PAGESIZE);