Name: Merge Duplicate Names in prom.c Device Tree
Status: Tested on Ameslab 19-May-2004
Version: ppc64

BenH pointed out that there are many duplicate strings in the OF
device tree, such as the "name" property everything has, or even the
contents of many properties.  Given that these nodes are never
deleted, we can reuse the strings if we can find them.

A fun problem to solve with simple efficient code with static
datastructures.  Fortunately duplicates are often near to each other
in the tree. eg. memory nodes all have the name "memory", and only 6
entries, meaning duplicates are six apart.  Hence the choice of a
cache of 256 entries.

On Gogogo before: 134320 after: 110832 (approx).

diff -urNp --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-ppc64-2.5/arch/ppc64/kernel/prom.c working-ppc64-2.5-prom-compress/arch/ppc64/kernel/prom.c
--- linux-ppc64-2.5/arch/ppc64/kernel/prom.c	2004-05-01 23:04:59.000000000 +1000
+++ working-ppc64-2.5-prom-compress/arch/ppc64/kernel/prom.c	2004-05-19 17:06:51.437646169 +1000
@@ -1578,6 +1578,66 @@ static void __init *__make_room(unsigned
 #define make_room(startp, endp, type) \
 	__make_room(startp, endp, sizeof(type), __alignof__(type))
 
+struct value_cache
+{
+	void *value;
+	unsigned int length;
+	unsigned int use;
+};
+static struct value_cache __initdata value_cache[512];
+
+/* This is based on the hash agorithm from gdbm, via tdb */
+static unsigned int __init tdb_hash(const void *val, unsigned int size)
+{
+	unsigned value;	/* Used to compute the hash value.  */
+	unsigned   i;	/* Used to cycle through random values. */
+
+	/* Set the initial value from the key size. */
+	for (value = 0x238F13AF * size, i=0; i < size; i++)
+		value = (value + (((unsigned char *)val)[i] << (i*5 % 24)));
+
+	return (1103515243 * value + 12345);
+}
+
+static void *__init find_value(const void *value,
+			       unsigned int length,
+			       unsigned int align,
+			       unsigned long *mem_start,
+			       unsigned long *mem_end)
+{
+	void *new;
+	unsigned int i, pos, hash = tdb_hash(value, length);
+	unsigned long offset = reloc_offset();
+	struct value_cache *cache = RELOC(value_cache);
+
+	pos = (hash % ARRAY_SIZE(value_cache));
+	/* Found by trial and error: more clashing popular entries unlikely. */
+	for (i = 0; i < 10; i++) { 
+		if (cache[pos].use == 0) {
+			new = __make_room(mem_start, mem_end, length, align);
+			memcpy(new, value, length);
+			cache[pos].value = new;
+			cache[pos].length = length;
+			cache[pos].use = 1;
+			return new;
+		}
+		if (cache[pos].length == length
+		    && (unsigned long)cache[pos].value % align == 0
+		    && memcmp(cache[pos].value, value, length) == 0) {
+			cache[pos].use++;
+			return cache[pos].value;
+		}
+		pos = (pos+i+(hash >> i*3)) % ARRAY_SIZE(value_cache);
+	}
+
+	/* Penalize first cache hit for being wrong. */
+	cache[hash % ARRAY_SIZE(value_cache)].use--;
+
+	new = __make_room(mem_start, mem_end, length, align);
+	memcpy(new, value, length);
+	return new;
+}
+
 static void __init
 inspect_node(phandle node, struct device_node *dad,
 	     unsigned long *mem_start, unsigned long *mem_end,
@@ -1611,18 +1671,14 @@ inspect_node(phandle node, struct device
 	prev_propp = &np->properties;
 	prev_name = RELOC("");
 	for (;;) {
-		/* 32 is max len of name including nul. */
-		namep = make_room(mem_start, mem_end, char[32]);
-		if ((long) call_prom(RELOC("nextprop"), 3, 1, node, prev_name,
-				     namep) <= 0) {
-			/* No more nodes: unwind alloc */
-			*mem_start = (unsigned long)namep;
+		char tmp[128];
+
+		if ((long)call_prom(RELOC("nextprop"), 3, 1, node, prev_name,
+				    tmp) <= 0)
 			break;
-		}
-		/* Trim off some if we can */
-		*mem_start = DOUBLEWORD_ALIGN((unsigned long)namep
-					     + strlen(namep) + 1);
+
 		pp = make_room(mem_start, mem_end, struct property);
+		namep = find_value(tmp, strlen(tmp)+1, 1, mem_start, mem_end);
 		pp->name = PTRUNRELOC(namep);
 		prev_name = namep;
 
@@ -1630,14 +1686,12 @@ inspect_node(phandle node, struct device
 		if (pp->length < 0)
 			continue;
 		if (pp->length > MAX_PROPERTY_LENGTH) {
-			char path[128];
-
 			prom_print(RELOC("WARNING: ignoring large property "));
 			/* It seems OF doesn't null-terminate the path :-( */
-			memset(path, 0, sizeof(path));
+			memset(tmp, 0, sizeof(tmp));
 			if (call_prom(RELOC("package-to-path"), 3, 1, node,
-                            path, sizeof(path)-1) > 0)
-				prom_print(path);
+                            tmp, sizeof(tmp)-1) > 0)
+				prom_print(tmp);
 			prom_print(namep);
 			prom_print(RELOC(" length 0x"));
 			prom_print_hex(pp->length);
@@ -1645,9 +1699,18 @@ inspect_node(phandle node, struct device
 
 			continue;
 		}
-		valp = __make_room(mem_start, mem_end, pp->length, 1);
+		if (pp->length > sizeof(tmp)) {
+			valp = __make_room(mem_start, mem_end, pp->length, 1);
+			call_prom(RELOC("getprop"), 4, 1, node, namep,
+				  valp, pp->length);
+		} else {
+			/* Look for small things in cache. */
+			call_prom(RELOC("getprop"), 4, 1, node, namep,
+				  tmp, pp->length);
+			valp = find_value(tmp, pp->length,8,mem_start,mem_end);
+		}
+
 		pp->value = PTRUNRELOC(valp);
-		call_prom(RELOC("getprop"), 4, 1, node, namep,valp,pp->length);
 		*prev_propp = PTRUNRELOC(pp);
 		prev_propp = &pp->next;
 	}
@@ -1981,8 +2044,13 @@ prom_init(unsigned long r3, unsigned lon
 #endif /* CONFIG_BLK_DEV_INITRD */
 	prom_print(RELOC("copying OF device tree...\n"));
 #endif /* DEBUG_PROM */
+	prom_print(RELOC("copying OF device tree...\n"));
+{
+	unsigned long before = mem;
 	mem = copy_device_tree(mem);
-
+	prom_print_hex(mem - before);
+	prom_print(RELOC("\n"));
+}
 	RELOC(klimit) = mem + offset;
 
 #ifdef DEBUG_PROM