memzap

commit 1ead999b8cca9588a8e0a74d67590dd8f01d86eb
parent 634a1c5d750f77ea0f2bc8f51d1a92e31b1f61ef
Author: sin <sin@2f30.org>
Date:   Wed,  6 Mar 2013 17:03:18 +0000

mem: Remove rbtree optimization

This is not needed so far and it only complicates the code.  We'll
revisit it in the future.  For now keep the code in a separate
branch named `mem-rbtree'.

Diffstat:
M
mem.c
 | 
146
++++++++++---------------------------------------------------------------------
M
memzap.c
 | 
9
+--------
M
proto.h
 | 
26
+-------------------------

3 files changed, 20 insertions(+), 161 deletions(-)
diff --git a/mem.c b/mem.c
@@ -127,113 +127,18 @@ free_mem_region(struct mem_region *mr)
 	free(mr);
 }
 
-RB_GENERATE(mem_tree, mem_tree_entry, entry,
-	    mem_cmp);
-int
-mem_cmp(struct mem_tree_entry *a, struct mem_tree_entry *b)
-{
-	if (a->weak_sum < b->weak_sum)
-		return -1;
-	if (a->weak_sum > b->weak_sum)
-		return 1;
-	return 0;
-}
-
-/* Given a memory region, build an rbtree
- * of the checksums.  We use this rbtree later on
- * when we want to find the differences between
- * two memory regions */
-struct mem_tree *
-build_mem_tree(struct mem_region *mr)
-{
-	struct mem_blk *mb;
-	struct mem_tree_entry *me, *n;
-	struct mem_tree *mt;
-	size_t i;
-
-	if (!mr)
-		return NULL;
-
-	mt = xmalloc(sizeof(*mt));
-	RB_INIT(mt);
-
-	for (i = 0; i < mr->nblocks; i++) {
-		mb = &mr->mblks[i];
-		me = xmalloc(sizeof(*me));
-		me->weak_sum = mb->weak_sum;
-		me->mr = mr;
-		n = RB_INSERT(mem_tree, mt, me);
-		if (!n) {
-			me->mblks = xmalloc(sizeof(*me->mblks));
-			me->mblks[0] = mb;
-			me->nmblks = 1;
-			continue;
-		}
-		/* If we have two blocks with the same weak
-		 * sum then try to chain the MD5 hash so we can keep track
-		 * of it */
-		n->mblks = xrealloc(n->mblks,
-				    (n->nmblks + 1) * sizeof(*me->mblks));
-		n->mblks[n->nmblks] = mb;
-		n->nmblks++;
-	}
-	return mt;
-}
-
-void
-dump_mem_tree(struct mem_tree *mt)
-{
-
-	struct mem_tree_entry *me;
-	struct mem_blk *mb;
-	size_t i;
-
-	if (!mt)
-		return;
-
-	RB_FOREACH(me, mem_tree, mt) {
-		for (i = 0; i < me->nmblks; i++) {
-			mb = me->mblks[i];
-			dump_mem_blk(mb);
-		}
-	}
-}
-
-void
-free_mem_tree(struct mem_tree *mt)
-{
-
-	struct mem_tree_entry *me, *next;
-
-	if (!mt)
-		return;
-
-	next = RB_MIN(mem_tree, mt);
-	while (next) {
-		me = next;
-		next = RB_NEXT(mem_tree, mt, me);
-		RB_REMOVE(mem_tree, mt, me);
-		free(me->mblks);
-		free(me);
-	}
-	free(mt);
-}
-
 /* Diff the two memory regions and return a
- * a diff structure.  In fact `dst' is an rbtree
- * that describes the *old* memory region
- * and `src' is the *new* and updated version of
- * the memory region. */
+ * a diff structure. In fact `dst' describes
+ * the *old* memory region and `src' is the
+ * *new* and updated copy */
 struct mem_region_diff *
-diff_mem_region(struct mem_tree *dst,
+diff_mem_region(struct mem_region *dst,
 		struct mem_region *src)
 {
-	struct mem_blk *mb;
+	struct mem_blk *mb_src, *mb_dst;
 	struct mem_diff *mdiff;
 	struct mem_region_diff *rdiff;
-	struct mem_region *mr_old;
-	struct mem_tree_entry find, *me;
-	size_t i, j;
+	size_t i;
 	bool found;
 	size_t size;
 
@@ -243,47 +148,32 @@ diff_mem_region(struct mem_tree *dst,
 	rdiff = xmalloc(sizeof(*rdiff));
 	rdiff->mrdiffs = NULL;
 	rdiff->nmrdiffs = 0;
-	me = RB_MIN(mem_tree, dst);
-	mr_old = me->mr;
 
 	/* We can only diff regions of the same size */
-	if (mr_old->rsize != src->rsize)
+	if (dst->rsize != src->rsize)
 		return NULL;
 
 	for (i = 0; i < src->nblocks; i++) {
 		found = false;
-		mb = &src->mblks[i];
-		find.weak_sum = mb->weak_sum;
-		me = RB_FIND(mem_tree, dst, &find);
-		if (me) {
-			for (j = 0; j < me->nmblks; j++) {
-				if (me->mblks[j]->offset == mb->offset) {
+		mb_src = &src->mblks[i];
+		mb_dst = &dst->mblks[i];
+		if (mb_src->weak_sum == mb_dst->weak_sum) {
+			if (mb_src->offset == mb_dst->offset) {
+				if (!memcmp(mb_src->digest,
+					    mb_dst->digest,
+					    MD5_DIGEST_LENGTH)) {
 					found = true;
-					break;
-				}
-			}
-			if (found) {
-				/* We might have a weak sum collision
-				 * so check the strong sum as well */
-				for (j = 0; j < me->nmblks; j++) {
-					if (!memcmp(me->mblks[j]->digest,
-						    mb->digest,
-						    MD5_DIGEST_LENGTH)) {
-						found = true;
-						break;
-					}
 				}
 			}
 		}
 		if (!found) {
-			/* Cool, this is a modified block - update the rdiff */
 			size = (rdiff->nmrdiffs + 1) * sizeof(*rdiff->mrdiffs);
 			rdiff->mrdiffs = xrealloc(rdiff->mrdiffs, size);
 			mdiff = &rdiff->mrdiffs[rdiff->nmrdiffs];
-			mdiff->buf = xmalloc(mb->len);
-			memcpy(mdiff->buf, mb->buf, mb->len);
-			mdiff->offset = mb->offset;
-			mdiff->len = mb->len;
+			mdiff->buf = xmalloc(mb_src->len);
+			memcpy(mdiff->buf, mb_src->buf, mb_src->len);
+			mdiff->offset = mb_src->offset;
+			mdiff->len = mb_src->len;
 			mdiff->index = i;
 			rdiff->nmrdiffs++;
 		}
diff --git a/memzap.c b/memzap.c
@@ -44,7 +44,6 @@ int
 main(int argc, char *argv[])
 {
 	struct mem_region *mr_old, *mr_new;
-	struct mem_tree *mt_old;
 	struct mem_region_diff *rdiff;
 	struct mdiff_hdr hdr;
 	int c;
@@ -214,10 +213,6 @@ main(int argc, char *argv[])
 		mr_old = build_mem_region(buf, len);
 		if (!mr_old)
 			errx(1, "failed to build memory region\n");
-		/* Build an rbtree that tracks this memory region */
-		mt_old = build_mem_tree(mr_old);
-		if (!mt_old)
-			errx(1, "failed to build memory tree\n");
 
 		/* Single step the child in order to get the next
 		 * generation */
@@ -225,7 +220,6 @@ main(int argc, char *argv[])
 		wait(&stat);
 		if (!WIFSTOPPED(stat)) {
 			free_mem_region(mr_old);
-			free_mem_tree(mt_old);
 			break;
 		}
 		cycle++;
@@ -240,7 +234,7 @@ main(int argc, char *argv[])
 			errx(1, "failed to build memory region\n");
 
 		/* Diff the original copy with the updated copy */
-		rdiff = diff_mem_region(mt_old, mr_new);
+		rdiff = diff_mem_region(mr_old, mr_new);
 		if (rdiff->nmrdiffs) {
 			/* If we've found differences, then apply them on
 			 * the Nth generation */
@@ -250,7 +244,6 @@ main(int argc, char *argv[])
 
 		/* Free these and go up for another run */
 		free_mem_region(mr_old);
-		free_mem_tree(mt_old);
 		free_mem_region(mr_new);
 		free_mem_region_diff(rdiff);
 	} while(1);
diff --git a/proto.h b/proto.h
@@ -83,24 +83,6 @@ struct mem_region_diff {
 	size_t nmrdiffs;
 };
 
-struct mem_tree_entry {
-	/* The rolling sum for this rbnode, we sort
-	 * based on this property */
-	uint32_t weak_sum;
-	/* Pointers to memory blocks, normally there
-	 * will be only 1 memory block here, however,
-	 * if we have weak sum collisions, then we will
-	 * chain more entries here */
-	struct mem_blk **mblks;
-	/* Actual number of tracked memory blocks */
-	size_t nmblks;
-	/* The memory region this tree is generated
-	 * from */
-	struct mem_region *mr;
-	RB_ENTRY(mem_tree_entry) entry;
-};
-RB_HEAD(mem_tree, mem_tree_entry);
-
 struct mdiff_hdr {
 	/* MDIFF */
 	uint8_t magic[8];
@@ -150,13 +132,7 @@ void dump_mem_blk(struct mem_blk *mb);
 struct mem_region *build_mem_region(unsigned char *buf, size_t len);
 void dump_mem_region(struct mem_region *mr);
 void free_mem_region(struct mem_region *mr);
-int mem_cmp(struct mem_tree_entry *a, struct mem_tree_entry *b);
-RB_PROTOTYPE(mem_tree, mem_tree_entry, entry,
-             mem_cmp);
-struct mem_tree *build_mem_tree(struct mem_region *mr);
-void dump_mem_tree(struct mem_tree *mt);
-void free_mem_tree(struct mem_tree *mt);
-struct mem_region_diff *diff_mem_region(struct mem_tree *dst,
+struct mem_region_diff *diff_mem_region(struct mem_region *dst,
 					struct mem_region *src);
 struct mem_region *apply_diff(struct mem_region *dst,
 			      struct mem_region_diff *rdiff);