Merge branch '2018-09-13-radix-tree-bug'

2 files changed, 38 insertions, 12 deletions

diff --git a/base/Makefile b/base/Makefile
index ff7781577..e30cb4498 100644
--- a/base/Makefile
+++ b/base/Makefile
@@ -12,7 +12,7 @@
 
 # Uncomment this to build the simple radix tree.  You'll need to make clean too.
 # Comment to build the advanced radix tree.
-base/data-struct/radix-tree.o: CFLAGS += -DSIMPLE_RADIX_TREE
+#base/data-struct/radix-tree.o: CFLAGS += -DSIMPLE_RADIX_TREE
 
 BASE_SOURCE=\
 	base/data-struct/radix-tree.c \
diff --git a/base/data-struct/radix-tree-adaptive.c b/base/data-struct/radix-tree-adaptive.c
index 1eef1f896..cd53dd600 100644
--- a/base/data-struct/radix-tree-adaptive.c
+++ b/base/data-struct/radix-tree-adaptive.c
@@ -581,12 +581,11 @@ static void _degrade_to_n16(struct node48 *n48, struct value *result)
         for (i = 0; i < 256; i++) {
 	        if (n48->keys[i] < 48) {
 		        n16->keys[count] = i;
+		        n16->values[count] = n48->values[n48->keys[i]];
 		        count++;
 	        }
         }
 
-        memcpy(n16->values, n48->values, n48->nr_entries * sizeof(*n16->values));
-
         free(n48);
 
 	result->type = NODE16;
@@ -598,16 +597,16 @@ static void _degrade_to_n48(struct node256 *n256, struct value *result)
         unsigned i, count = 0;
         struct node48 *n48 = zalloc(sizeof(*n48));
 
-	memset(n48->keys, 48, sizeof(n48->keys));
-
         n48->nr_entries = n256->nr_entries;
         for (i = 0; i < 256; i++) {
 		if (n256->values[i].type == UNSET)
-        		continue;
+			n48->keys[i] = 48;
 
-		n48->keys[i] = count;
-		n48->values[count] = n256->values[i];
-		count++;
+		else {
+			n48->keys[i] = count;
+			n48->values[count] = n256->values[i];
+			count++;
+		}
         }
 
         free(n256);
@@ -1036,6 +1035,7 @@ void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke,
 
 static bool _check_nodes(struct value *v, unsigned *count)
 {
+	uint64_t bits;
 	unsigned i, ncount;
 	struct value_chain *vc;
 	struct prefix_chain *pc;
@@ -1090,22 +1090,47 @@ static bool _check_nodes(struct value *v, unsigned *count)
 		return true;
 
 	case NODE48:
+		bits = 0;
 		n48 = v->value.ptr;
 		ncount = 0;
 		for (i = 0; i < 256; i++) {
 			if (n48->keys[i] < 48) {
+				if (n48->keys[i] >= n48->nr_entries) {
+					fprintf(stderr, "referencing value past nr_entries (n48)\n");
+					return false;
+				}
+
+				if (bits & (1ull << n48->keys[i])) {
+					fprintf(stderr, "duplicate entry (n48) %u\n", (unsigned) n48->keys[i]);
+					return false;
+				}
+				bits = bits | (1ull << n48->keys[i]);
 				ncount++;
+
 				if (!_check_nodes(n48->values + n48->keys[i], count))
 					return false;
 			}
 		}
 
+		for (i = 0; i < n48->nr_entries; i++) {
+			if (!(bits & (1ull << i))) {
+				fprintf(stderr, "not all values are referenced (n48)\n");
+				return false;
+			}
+		}
+
 		if (ncount != n48->nr_entries) {
 			fprintf(stderr, "incorrect number of entries in n48, n48->nr_entries = %u, actual = %u\n",
                                 n48->nr_entries, ncount);
 			return false;
 		}
 
+		for (i = 0; i < n48->nr_entries; i++)
+			if (n48->values[i].type == UNSET) {
+				fprintf(stderr, "value in UNSET (n48)\n");
+				return false;
+			}
+
 		for (i = n48->nr_entries; i < 48; i++)
 			if (n48->values[i].type != UNSET) {
 				fprintf(stderr, "unused value is not UNSET (n48)\n");
@@ -1234,9 +1259,10 @@ static void _dump(FILE *out, struct value v, unsigned indent)
 				fprintf(out, "%x ", i);
 		fprintf(out, ">\n");
 
-		for (i = 0; i < 256; i++)
-			if (n48->keys[i] < 48)
-				_dump(out, n48->values[i], indent + 1);
+		for (i = 0; i < n48->nr_entries; i++) {
+			assert(n48->values[i].type != UNSET);
+			_dump(out, n48->values[i], indent + 1);
+		}
 		break;
 
 	case NODE256: