{"thread":{"id":"7705","subject":"[RFD PATCH 0/3] Use \"object index\" rather than pointers in the object hashing","startedAt":"2007-04-17T04:12:50Z","lastAt":"2007-04-17T05:13:09Z","messageCount":9,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"39593","messageId":"Pine.LNX.4.64.0704162041290.5473@woody.linux-foundation.org","threadId":"7705","inReplyTo":null,"subject":"[RFD PATCH 0/3] Use \"object index\" rather than pointers in the object hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-17T04:12:50Z","receivedAt":"2007-04-17T04:12:50Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis is a series of three patches that changes the low-level object \nhashing to use a \"object index\" rather than the pointer to a \"struct \nobject\" in the hash-tables. It's something I've been thinking about for a \nlong time, so I just decided to do it.\n\nThe reason to do it is that on 64-bit architectures the object hash table \nis actually a fairly sizeable entity, and not for a very good reason. It \nhas a ton of pointers to the objects we have allocated, so each hash-table \nentry is 64-bits, even though obviously we aren't likely to ever have that \nmany objects.\n\nSo instead, we could use a 32-bit index into an object table - and in \nfact, since we already do all normal object allocations using a special \ndense allocatory that allocates 1024 objects in one go, we already kind of \nwere set up for this, with the low 10 bits of the object index being a \nvery natural index into each allocation block.\n\nCould we ever want more than 4 billion objects? Unlikely, since you'd \nactually need 80GB of memory just to keep track of the object names in \nsuch a hash table, but hey, if that day ever comes, we can certainly \ntrivially make the index be 64-bit instead (or more likely, make it be \n48-bit and use 16 bits of the hash table entry as an extended hash value \nor something).\n\nAnyway, the before-and-after numbers are somewhat debatable, so this is \npurely a request for discussion..\n\nBefore:\n\n\t[torvalds@woody linux]$ /usr/bin/time git-rev-list --all --objects | wc -l\n\t5.66user 0.46system 0:06.12elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n\t0inputs+0outputs (0major+44389minor)pagefaults 0swaps\n\t445065\n\nAfter:\n\n\t[torvalds@woody linux]$ /usr/bin/time ~/git/git-rev-list --all --objects | wc -l\n\t6.96user 0.36system 0:07.36elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n\t0inputs+0outputs (0major+40240minor)pagefaults 0swaps\n\t445065\n\nie it's actually slightly slower, but it uses almost 10% less memory \n(minor page faults). Is it worth it? Probably not, but since I made the \npatches, I thought I'd post them anyway. And the two first patches are \nprobably worth applying regardless - it's only the third patch that \nactually changes things to use a hash index.\n\nAnyway, the three patches are:\n\n\t0001-Use-proper-object-allocators-for-unknown-object-node.patch\n\t0002-Clean-up-object-creation-to-use-more-common-code.patch\n\t0003-Make-the-object-lookup-hash-use-a-object-index-ins.patch\n\nwhere 1-2 are pretty much just cleanups.\n\nComments?\n\n\t\tLinus\n"},{"id":"39594","messageId":"Pine.LNX.4.64.0704162112560.5473@woody.linux-foundation.org","threadId":"7705","inReplyTo":"Pine.LNX.4.64.0704162041290.5473@woody.linux-foundation.org","subject":"[PATCH 1/3] Use proper object allocators for unknown object nodes too","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-17T04:13:20Z","receivedAt":"2007-04-17T04:13:20Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nWe used to use a different allocator scheme for when we didn't know the\nobject type.  That meant that objects that were created without any\nup-front knowledge of the type would not go through the same allocation\npaths as normal object allocations, and would miss out on the statistics.\n\nBut perhaps more importantly than the statistics (that are useful when\nlooking at memory usage but not much else), if we want to make the\nobject hash tables use a denser object pointer representation, we need\nto make sure that they all go through the same blocking allocator.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n alloc.c  |   21 +++++++++++++++------\n cache.h  |    1 +\n object.c |   15 +++------------\n 3 files changed, 19 insertions(+), 18 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 460db19..c73aeec 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -18,7 +18,7 @@\n \n #define BLOCKING 1024\n \n-#define DEFINE_ALLOCATOR(name)\t\t\t\t\t\\\n+#define DEFINE_ALLOCATOR(name, type)\t\t\t\t\\\n static unsigned int name##_allocs;\t\t\t\t\\\n struct name *alloc_##name##_node(void)\t\t\t\t\\\n {\t\t\t\t\t\t\t\t\\\n@@ -27,17 +27,26 @@ struct name *alloc_##name##_node(void)\t\t\t\t\\\n \t\t\t\t\t\t\t\t\\\n \tif (!nr) {\t\t\t\t\t\t\\\n \t\tnr = BLOCKING;\t\t\t\t\t\\\n-\t\tblock = xcalloc(BLOCKING, sizeof(struct name));\t\\\n+\t\tblock = xcalloc(BLOCKING, sizeof(type));\t\\\n \t}\t\t\t\t\t\t\t\\\n \tnr--;\t\t\t\t\t\t\t\\\n \tname##_allocs++;\t\t\t\t\t\\\n \treturn block++;\t\t\t\t\t\t\\\n }\n \n-DEFINE_ALLOCATOR(blob)\n-DEFINE_ALLOCATOR(tree)\n-DEFINE_ALLOCATOR(commit)\n-DEFINE_ALLOCATOR(tag)\n+union any_object {\n+\tstruct object object;\n+\tstruct blob blob;\n+\tstruct tree tree;\n+\tstruct commit commit;\n+\tstruct tag tag;\n+};\n+\n+DEFINE_ALLOCATOR(blob, struct blob)\n+DEFINE_ALLOCATOR(tree, struct tree)\n+DEFINE_ALLOCATOR(commit, struct commit)\n+DEFINE_ALLOCATOR(tag, struct tag)\n+DEFINE_ALLOCATOR(object, union any_object)\n \n #ifdef NO_C99_FORMAT\n #define SZ_FMT \"%u\"\ndiff --git a/cache.h b/cache.h\nindex b1bd9e4..aa72791 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -484,6 +484,7 @@ extern struct blob *alloc_blob_node(void);\n extern struct tree *alloc_tree_node(void);\n extern struct commit *alloc_commit_node(void);\n extern struct tag *alloc_tag_node(void);\n+extern struct object *alloc_object_node(void);\n extern void alloc_report(void);\n \n /* trace.c */\ndiff --git a/object.c b/object.c\nindex 78a44a6..153ebac 100644\n--- a/object.c\n+++ b/object.c\n@@ -120,22 +120,13 @@ void created_object(const unsigned char *sha1, struct object *obj)\n \tnr_objs++;\n }\n \n-union any_object {\n-\tstruct object object;\n-\tstruct commit commit;\n-\tstruct tree tree;\n-\tstruct blob blob;\n-\tstruct tag tag;\n-};\n-\n struct object *lookup_unknown_object(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n \tif (!obj) {\n-\t\tunion any_object *ret = xcalloc(1, sizeof(*ret));\n-\t\tcreated_object(sha1, &ret->object);\n-\t\tret->object.type = OBJ_NONE;\n-\t\treturn &ret->object;\n+\t\tobj = alloc_object_node();\n+\t\tcreated_object(sha1, obj);\n+\t\tobj->type = OBJ_NONE;\n \t}\n \treturn obj;\n }\n-- \n1.5.1.1.107.g7a15\n"},{"id":"39595","messageId":"Pine.LNX.4.64.0704162113220.5473@woody.linux-foundation.org","threadId":"7705","inReplyTo":"Pine.LNX.4.64.0704162041290.5473@woody.linux-foundation.org","subject":"[PATCH 2/3] Clean up object creation to use more common code","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-17T04:13:44Z","receivedAt":"2007-04-17T04:13:44Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis replaces the fairly odd \"created_object()\" function that did _most_\nof the object setup with a more complete \"create_object()\" function that\nalso has a more natural calling convention.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n alloc.c  |    2 +-\n blob.c   |    8 ++------\n cache.h  |   14 +++++---------\n commit.c |    8 ++------\n object.c |   14 +++++++-------\n object.h |    2 +-\n tag.c    |   10 +++-------\n tree.c   |    8 ++------\n 8 files changed, 23 insertions(+), 43 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex c73aeec..70f3c32 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -20,7 +20,7 @@\n \n #define DEFINE_ALLOCATOR(name, type)\t\t\t\t\\\n static unsigned int name##_allocs;\t\t\t\t\\\n-struct name *alloc_##name##_node(void)\t\t\t\t\\\n+void *alloc_##name##_node(void)\t\t\t\t\t\\\n {\t\t\t\t\t\t\t\t\\\n \tstatic int nr;\t\t\t\t\t\t\\\n \tstatic struct name *block;\t\t\t\t\\\ndiff --git a/blob.c b/blob.c\nindex 0a9ea41..bd7d078 100644\n--- a/blob.c\n+++ b/blob.c\n@@ -6,12 +6,8 @@ const char *blob_type = \"blob\";\n struct blob *lookup_blob(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj) {\n-\t\tstruct blob *ret = alloc_blob_node();\n-\t\tcreated_object(sha1, &ret->object);\n-\t\tret->object.type = OBJ_BLOB;\n-\t\treturn ret;\n-\t}\n+\tif (!obj)\n+\t\treturn create_object(sha1, OBJ_BLOB, alloc_blob_node());\n \tif (!obj->type)\n \t\tobj->type = OBJ_BLOB;\n \tif (obj->type != OBJ_BLOB) {\ndiff --git a/cache.h b/cache.h\nindex aa72791..4de25cc 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -476,15 +476,11 @@ int decode_85(char *dst, const char *line, int linelen);\n void encode_85(char *buf, const unsigned char *data, int bytes);\n \n /* alloc.c */\n-struct blob;\n-struct tree;\n-struct commit;\n-struct tag;\n-extern struct blob *alloc_blob_node(void);\n-extern struct tree *alloc_tree_node(void);\n-extern struct commit *alloc_commit_node(void);\n-extern struct tag *alloc_tag_node(void);\n-extern struct object *alloc_object_node(void);\n+extern void *alloc_blob_node(void);\n+extern void *alloc_tree_node(void);\n+extern void *alloc_commit_node(void);\n+extern void *alloc_tag_node(void);\n+extern void *alloc_object_node(void);\n extern void alloc_report(void);\n \n /* trace.c */\ndiff --git a/commit.c b/commit.c\nindex 952095f..10466c4 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -98,12 +98,8 @@ struct commit *lookup_commit_reference(const unsigned char *sha1)\n struct commit *lookup_commit(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj) {\n-\t\tstruct commit *ret = alloc_commit_node();\n-\t\tcreated_object(sha1, &ret->object);\n-\t\tret->object.type = OBJ_COMMIT;\n-\t\treturn ret;\n-\t}\n+\tif (!obj)\n+\t\treturn create_object(sha1, OBJ_COMMIT, alloc_commit_node());\n \tif (!obj->type)\n \t\tobj->type = OBJ_COMMIT;\n \treturn check_commit(obj, sha1, 0);\ndiff --git a/object.c b/object.c\nindex 153ebac..7bd3fec 100644\n--- a/object.c\n+++ b/object.c\n@@ -105,11 +105,13 @@ static void grow_object_hash(void)\n \tobj_hash_size = new_hash_size;\n }\n \n-void created_object(const unsigned char *sha1, struct object *obj)\n+void *create_object(const unsigned char *sha1, int type, void *o)\n {\n+\tstruct object *obj = o;\n+\n \tobj->parsed = 0;\n \tobj->used = 0;\n-\tobj->type = OBJ_NONE;\n+\tobj->type = type;\n \tobj->flags = 0;\n \thashcpy(obj->sha1, sha1);\n \n@@ -118,16 +120,14 @@ void created_object(const unsigned char *sha1, struct object *obj)\n \n \tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n \tnr_objs++;\n+\treturn obj;\n }\n \n struct object *lookup_unknown_object(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj) {\n-\t\tobj = alloc_object_node();\n-\t\tcreated_object(sha1, obj);\n-\t\tobj->type = OBJ_NONE;\n-\t}\n+\tif (!obj)\n+\t\tobj = create_object(sha1, OBJ_NONE, alloc_object_node());\n \treturn obj;\n }\n \ndiff --git a/object.h b/object.h\nindex bdbf0fa..c0a5fd3 100644\n--- a/object.h\n+++ b/object.h\n@@ -47,7 +47,7 @@ extern struct object_refs *lookup_object_refs(struct object *);\n /** Internal only **/\n struct object *lookup_object(const unsigned char *sha1);\n \n-void created_object(const unsigned char *sha1, struct object *obj);\n+extern void *create_object(const unsigned char *sha1, int type, void *obj);\n \n /** Returns the object, having parsed it to find out what it is. **/\n struct object *parse_object(const unsigned char *sha1);\ndiff --git a/tag.c b/tag.c\nindex 56a49f4..330d287 100644\n--- a/tag.c\n+++ b/tag.c\n@@ -20,13 +20,9 @@ struct object *deref_tag(struct object *o, const char *warn, int warnlen)\n \n struct tag *lookup_tag(const unsigned char *sha1)\n {\n-        struct object *obj = lookup_object(sha1);\n-        if (!obj) {\n-                struct tag *ret = alloc_tag_node();\n-                created_object(sha1, &ret->object);\n-                ret->object.type = OBJ_TAG;\n-                return ret;\n-        }\n+\tstruct object *obj = lookup_object(sha1);\n+\tif (!obj)\n+\t\treturn create_object(sha1, OBJ_TAG, alloc_tag_node());\n \tif (!obj->type)\n \t\tobj->type = OBJ_TAG;\n         if (obj->type != OBJ_TAG) {\ndiff --git a/tree.c b/tree.c\nindex d188c0f..e5bfbce 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -127,12 +127,8 @@ int read_tree(struct tree *tree, int stage, const char **match)\n struct tree *lookup_tree(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj) {\n-\t\tstruct tree *ret = alloc_tree_node();\n-\t\tcreated_object(sha1, &ret->object);\n-\t\tret->object.type = OBJ_TREE;\n-\t\treturn ret;\n-\t}\n+\tif (!obj)\n+\t\treturn create_object(sha1, OBJ_TREE, alloc_tree_node());\n \tif (!obj->type)\n \t\tobj->type = OBJ_TREE;\n \tif (obj->type != OBJ_TREE) {\n-- \n1.5.1.1.107.g7a15\n"},{"id":"39596","messageId":"Pine.LNX.4.64.0704162113480.5473@woody.linux-foundation.org","threadId":"7705","inReplyTo":"Pine.LNX.4.64.0704162041290.5473@woody.linux-foundation.org","subject":"[PATCH 3/3] Make the object lookup hash use a \"object index\" instead of a pointer","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-17T04:14:42Z","receivedAt":"2007-04-17T04:14:42Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis uses less memory on 64-bit architectures (a 32-bit object index\nrather than a full 64-bit pointer), but could also allow for some other\noptimizations (like hiding part of the hash in unused bits of the index).\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n alloc.c  |   86 ++++++++++++++++++++++++++++++++++++++++++++++++++-----------\n cache.h  |   11 ++++---\n object.c |   50 ++++++++++++++++++++++-------------\n object.h |    2 +-\n 4 files changed, 108 insertions(+), 41 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 70f3c32..bc6aa30 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -16,24 +16,78 @@\n #include \"commit.h\"\n #include \"tag.h\"\n \n-#define BLOCKING 1024\n+/*\n+ * We allocate 1024 object nodes at a time.\n+ *\n+ * This not only avoids any fragmentation in the system \"malloc()\"\n+ * libraries, it also means that we can generate a denser \"object\n+ * index\" that does not need a full pointer: we can use an integer\n+ * with the low bits indicating the object node ID within an\n+ * allocation block, and the high bits indicating the allocation\n+ * block number.\n+ */\n+#define BLOCKING_BITS 10\n+#define BLOCKING_SIZE (1u << BLOCKING_BITS)\n+#define BLOCKING_MASK (BLOCKING_SIZE-1)\n \n-#define DEFINE_ALLOCATOR(name, type)\t\t\t\t\\\n-static unsigned int name##_allocs;\t\t\t\t\\\n-void *alloc_##name##_node(void)\t\t\t\t\t\\\n-{\t\t\t\t\t\t\t\t\\\n-\tstatic int nr;\t\t\t\t\t\t\\\n-\tstatic struct name *block;\t\t\t\t\\\n-\t\t\t\t\t\t\t\t\\\n-\tif (!nr) {\t\t\t\t\t\t\\\n-\t\tnr = BLOCKING;\t\t\t\t\t\\\n-\t\tblock = xcalloc(BLOCKING, sizeof(type));\t\\\n-\t}\t\t\t\t\t\t\t\\\n-\tnr--;\t\t\t\t\t\t\t\\\n-\tname##_allocs++;\t\t\t\t\t\\\n-\treturn block++;\t\t\t\t\t\t\\\n+struct alloc_descriptor {\n+\tunsigned int size, nr;\n+\tunsigned int block;\n+};\n+\n+struct block_descriptor {\n+\tunsigned int size;\n+\tunsigned char *base;\n+};\n+\n+static struct block_descriptor *block_allocations;\n+static unsigned int nr_block_allocations;\n+\n+static unsigned int alloc_new_block(unsigned int size)\n+{\n+\tstatic unsigned int index;\n+\tunsigned int i = ++index;\n+\n+\tif (i >= nr_block_allocations) {\n+\t\tunsigned int old = nr_block_allocations;\n+\t\tunsigned int nr = alloc_nr(i);\n+\t\tblock_allocations = xrealloc(block_allocations, nr * sizeof(*block_allocations));\n+\t\tmemset(block_allocations + old, 0, (nr - old) * sizeof(*block_allocations));\n+\t\tnr_block_allocations = nr;\n+\t}\n+\tblock_allocations[i].size = size;\n+\tblock_allocations[i].base = xcalloc(BLOCKING_SIZE, size);\n+\treturn i;\n+}\n+\n+static unsigned int allocate_one_index(struct alloc_descriptor *desc)\n+{\n+\tunsigned int nr = desc->nr++;\n+\tunsigned int index = nr & BLOCKING_MASK;\n+\tif (!index)\n+\t\tdesc->block = alloc_new_block(desc->size);\n+\treturn (desc->block << BLOCKING_BITS) + index;\n+}\n+\n+struct object *object_index_address(unsigned int index)\n+{\n+\tunsigned int block = index >> BLOCKING_BITS;\n+\tstruct block_descriptor *desc;\n+\n+\tindex &= BLOCKING_MASK;\n+\tif (!block || block >= nr_block_allocations)\n+\t\tdie(\"invalid object index (block = %u/%u)\", block, nr_block_allocations);\n+\tdesc = block_allocations + block;\n+\tif (!desc->size || !desc->base)\n+\t\tdie(\"bad object block index entry %u:%p\", desc->size, desc->base);\n+\treturn (struct object *)(index * desc->size + desc->base);\n }\n \n+#define DEFINE_ALLOCATOR(name, type)\t\t\t\t\\\n+static struct alloc_descriptor name##_desc = { sizeof(type) };\t\\\n+unsigned int alloc_##name##_node(void)\t\t\t\t\\\n+{ return allocate_one_index(&name##_desc); }\n+\n union any_object {\n \tstruct object object;\n \tstruct blob blob;\n@@ -62,7 +116,7 @@ static void report(const char* name, unsigned int count, size_t size)\n #undef SZ_FMT\n \n #define REPORT(name)\t\\\n-    report(#name, name##_allocs, name##_allocs*sizeof(struct name) >> 10)\n+    report(#name, name##_desc.nr, name##_desc.nr*sizeof(struct name) >> 10)\n \n void alloc_report(void)\n {\ndiff --git a/cache.h b/cache.h\nindex 4de25cc..9342980 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -476,12 +476,13 @@ int decode_85(char *dst, const char *line, int linelen);\n void encode_85(char *buf, const unsigned char *data, int bytes);\n \n /* alloc.c */\n-extern void *alloc_blob_node(void);\n-extern void *alloc_tree_node(void);\n-extern void *alloc_commit_node(void);\n-extern void *alloc_tag_node(void);\n-extern void *alloc_object_node(void);\n+extern unsigned int alloc_blob_node(void);\n+extern unsigned int alloc_tree_node(void);\n+extern unsigned int alloc_commit_node(void);\n+extern unsigned int alloc_tag_node(void);\n+extern unsigned int alloc_object_node(void);\n extern void alloc_report(void);\n+extern struct object *object_index_address(unsigned int index);\n \n /* trace.c */\n extern int nfasprintf(char **str, const char *fmt, ...);\ndiff --git a/object.c b/object.c\nindex 7bd3fec..a91d238 100644\n--- a/object.c\n+++ b/object.c\n@@ -5,7 +5,11 @@\n #include \"commit.h\"\n #include \"tag.h\"\n \n-static struct object **obj_hash;\n+struct hash_entry {\n+\tunsigned int index;\n+};\n+\n+static struct hash_entry *obj_hash;\n static int nr_objs, obj_hash_size;\n \n unsigned int get_max_object_index(void)\n@@ -13,9 +17,11 @@ unsigned int get_max_object_index(void)\n \treturn obj_hash_size;\n }\n \n+/* Purely for external object walkers (like fsck) */\n struct object *get_indexed_object(unsigned int idx)\n {\n-\treturn obj_hash[idx];\n+\tunsigned int object_index = obj_hash[idx].index;\n+\treturn object_index ? object_index_address(object_index) : NULL;\n }\n \n static const char *object_type_strings[] = {\n@@ -49,16 +55,16 @@ static unsigned int hash_obj(struct object *obj, unsigned int n)\n \treturn hash % n;\n }\n \n-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n+static void insert_obj_hash(unsigned int object_index, struct object *object, struct hash_entry *hash, unsigned int size)\n {\n-\tint j = hash_obj(obj, size);\n+\tint j = hash_obj(object, size);\n \n-\twhile (hash[j]) {\n+\twhile (hash[j].index) {\n \t\tj++;\n \t\tif (j >= size)\n \t\t\tj = 0;\n \t}\n-\thash[j] = obj;\n+\thash[j].index = object_index;\n }\n \n static int hashtable_index(const unsigned char *sha1)\n@@ -71,43 +77,49 @@ static int hashtable_index(const unsigned char *sha1)\n struct object *lookup_object(const unsigned char *sha1)\n {\n \tint i;\n-\tstruct object *obj;\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n \ti = hashtable_index(sha1);\n-\twhile ((obj = obj_hash[i]) != NULL) {\n-\t\tif (!hashcmp(sha1, obj->sha1))\n+\tfor (;;) {\n+\t\tstruct hash_entry *entry = obj_hash + i;\n+\t\tunsigned int index = entry->index;\n+\t\tstruct object *obj;\n+\n+\t\tif (!index)\n \t\t\tbreak;\n+\t\tobj = object_index_address(index);\n+\t\tif (!hashcmp(sha1, obj->sha1))\n+\t\t\treturn obj;\n \t\ti++;\n \t\tif (i == obj_hash_size)\n \t\t\ti = 0;\n \t}\n-\treturn obj;\n+\treturn NULL;\n }\n \n static void grow_object_hash(void)\n {\n \tint i;\n \tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n-\tstruct object **new_hash;\n+\tstruct hash_entry *new_hash;\n \n-\tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n+\tnew_hash = xcalloc(new_hash_size, sizeof(struct hash_entry));\n \tfor (i = 0; i < obj_hash_size; i++) {\n-\t\tstruct object *obj = obj_hash[i];\n-\t\tif (!obj)\n+\t\tunsigned int index = obj_hash[i].index;\n+\t\tif (!index)\n \t\t\tcontinue;\n-\t\tinsert_obj_hash(obj, new_hash, new_hash_size);\n+\t\tinsert_obj_hash(index, object_index_address(index), new_hash, new_hash_size);\n \t}\n \tfree(obj_hash);\n \tobj_hash = new_hash;\n \tobj_hash_size = new_hash_size;\n }\n \n-void *create_object(const unsigned char *sha1, int type, void *o)\n+void *create_object(const unsigned char *sha1, int type, unsigned int index)\n {\n-\tstruct object *obj = o;\n+\tstruct object *obj = object_index_address(index);\n \n \tobj->parsed = 0;\n \tobj->used = 0;\n@@ -118,7 +130,7 @@ void *create_object(const unsigned char *sha1, int type, void *o)\n \tif (obj_hash_size - 1 <= nr_objs * 2)\n \t\tgrow_object_hash();\n \n-\tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n+\tinsert_obj_hash(index, obj, obj_hash, obj_hash_size);\n \tnr_objs++;\n \treturn obj;\n }\n@@ -127,7 +139,7 @@ struct object *lookup_unknown_object(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n \tif (!obj)\n-\t\tobj = create_object(sha1, OBJ_NONE, alloc_object_node());\n+\t\treturn create_object(sha1, OBJ_NONE, alloc_object_node());\n \treturn obj;\n }\n \ndiff --git a/object.h b/object.h\nindex c0a5fd3..099bbdb 100644\n--- a/object.h\n+++ b/object.h\n@@ -47,7 +47,7 @@ extern struct object_refs *lookup_object_refs(struct object *);\n /** Internal only **/\n struct object *lookup_object(const unsigned char *sha1);\n \n-extern void *create_object(const unsigned char *sha1, int type, void *obj);\n+extern void *create_object(const unsigned char *sha1, int type, unsigned int object_index);\n \n /** Returns the object, having parsed it to find out what it is. **/\n struct object *parse_object(const unsigned char *sha1);\n-- \n1.5.1.1.107.g7a15\n"},{"id":"39598","messageId":"7vfy6zskb4.fsf@assigned-by-dhcp.cox.net","threadId":"7705","inReplyTo":"Pine.LNX.4.64.0704162041290.5473@woody.linux-foundation.org","subject":"Re: [RFD PATCH 0/3] Use \"object index\" rather than pointers in the object hashing","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-04-17T04:21:03Z","receivedAt":"2007-04-17T04:21:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> This is a series of three patches that changes the low-level object \n> hashing to use a \"object index\" rather than the pointer to a \"struct \n> object\" in the hash-tables. It's something I've been thinking about for a \n> long time, so I just decided to do it.\n>\n> The reason to do it is that on 64-bit architectures the object hash table \n> is actually a fairly sizeable entity, and not for a very good reason. It \n> has a ton of pointers to the objects we have allocated, so each hash-table \n> entry is 64-bits, even though obviously we aren't likely to ever have that \n> many objects.\n\nI was thinking about revamping that \"keeping track of all\nobjects\" stuff for some time, too, but in a different direction.\nGlad I have not touched that area ;-).\n\nI think this makes sense, although the numbers are somewhat\ndissapointing.\n"},{"id":"39606","messageId":"Pine.LNX.4.64.0704162200420.5473@woody.linux-foundation.org","threadId":"7705","inReplyTo":"7vfy6zskb4.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFD PATCH 0/3] Use \"object index\" rather than pointers in the object hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-17T05:06:53Z","receivedAt":"2007-04-17T05:06:53Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 16 Apr 2007, Junio C Hamano wrote:\n> \n> I was thinking about revamping that \"keeping track of all\n> objects\" stuff for some time, too, but in a different direction.\n> Glad I have not touched that area ;-).\n\nWell, I obviously shouldn't have touched it either. I introduced a bug in \nthe first patch of the series (and the bug got removed by the third patch, \nbut since the third patch was not worth applying yet, it means that \npatches 1 and 2 shouldn't be applied either, because of the bug).\n\nThe bug was that when I modified the generic object allocator framework to \nwork with \"union any_object\", it would still do\n\n\tstatic struct name *block;\t\t/* where \"name\" was \"object\" */\n\t...\n\treturn block++;\n\nso while we *allocated* a block of \"union any_objects\", the patch would \nthen end up doling them out as \"struct object\" (which is *wrong* - we \ndon't know which kind of object it is yet, so we need to allocate the \nmaximum size!).\n\nSo it *should* have been\n\n\tstatic type *block;\n\t...\n\treturn block++;\n\nbut it actually turns out that my timings seem to say that it's better to \ndo the memset of the object just before returning it, so I changed it to \nuse \"xmalloc()\" instead of \"xcalloc()\" for the block allocation, and then \nuse\n\n\tstatic type *block;\n\tvoid *ret;\n\t...\n\tret = block++;\n\tmemset(ret, 0, sizeof(type));\n\treturn ret;\n\ninstead.\n\n> I think this makes sense, although the numbers are somewhat\n> dissapointing.\n\nWell, with just patches 1&2, the numbers don't go down, and the code looks \ncleaner (and it removes more lines than it adds). So let me re-send the \nseries, and while I will re-send the final patch#3, only #1/#2 are \nactually meant to be considered for actual inclusion at this point.\n\n\t\tLinus\n"},{"id":"39608","messageId":"Pine.LNX.4.64.0704162208290.5473@woody.linux-foundation.org","threadId":"7705","inReplyTo":"Pine.LNX.4.64.0704162200420.5473@woody.linux-foundation.org","subject":"[FIXED PATCH 1/3] Use proper object allocators for unknown object nodes too","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-17T05:10:19Z","receivedAt":"2007-04-17T05:10:19Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nWe used to use a different allocator scheme for when we didn't know the\nobject type.  That meant that objects that were created without any\nup-front knowledge of the type would not go through the same allocation\npaths as normal object allocations, and would miss out on the statistics.\n\nBut perhaps more importantly than the statistics (that are useful when\nlooking at memory usage but not much else), if we want to make the\nobject hash tables use a denser object pointer representation, we need\nto make sure that they all go through the same blocking allocator.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nGaah. So this should be the properly working version. Not a lot of code \nactually uses the \"allocate unknown object\", which is why nothing obvious \nbroke with the previous version that effectively only allocated a \"struct \nobject\", but it was still a bad bug.\n\nSomebody should triple-check that I didn't screw up *again*.\n\n alloc.c  |   28 ++++++++++++++++++++--------\n cache.h  |    1 +\n object.c |   15 +++------------\n 3 files changed, 24 insertions(+), 20 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 460db19..53eba37 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -18,26 +18,38 @@\n \n #define BLOCKING 1024\n \n-#define DEFINE_ALLOCATOR(name)\t\t\t\t\t\\\n+#define DEFINE_ALLOCATOR(name, type)\t\t\t\t\\\n static unsigned int name##_allocs;\t\t\t\t\\\n struct name *alloc_##name##_node(void)\t\t\t\t\\\n {\t\t\t\t\t\t\t\t\\\n \tstatic int nr;\t\t\t\t\t\t\\\n-\tstatic struct name *block;\t\t\t\t\\\n+\tstatic type *block;\t\t\t\t\t\\\n+\tvoid *ret;\t\t\t\t\t\t\\\n \t\t\t\t\t\t\t\t\\\n \tif (!nr) {\t\t\t\t\t\t\\\n \t\tnr = BLOCKING;\t\t\t\t\t\\\n-\t\tblock = xcalloc(BLOCKING, sizeof(struct name));\t\\\n+\t\tblock = xmalloc(BLOCKING * sizeof(type));\t\\\n \t}\t\t\t\t\t\t\t\\\n \tnr--;\t\t\t\t\t\t\t\\\n \tname##_allocs++;\t\t\t\t\t\\\n-\treturn block++;\t\t\t\t\t\t\\\n+\tret = block++;\t\t\t\t\t\t\\\n+\tmemset(ret, 0, sizeof(type));\t\t\t\t\\\n+\treturn ret;\t\t\t\t\t\t\\\n }\n \n-DEFINE_ALLOCATOR(blob)\n-DEFINE_ALLOCATOR(tree)\n-DEFINE_ALLOCATOR(commit)\n-DEFINE_ALLOCATOR(tag)\n+union any_object {\n+\tstruct object object;\n+\tstruct blob blob;\n+\tstruct tree tree;\n+\tstruct commit commit;\n+\tstruct tag tag;\n+};\n+\n+DEFINE_ALLOCATOR(blob, struct blob)\n+DEFINE_ALLOCATOR(tree, struct tree)\n+DEFINE_ALLOCATOR(commit, struct commit)\n+DEFINE_ALLOCATOR(tag, struct tag)\n+DEFINE_ALLOCATOR(object, union any_object)\n \n #ifdef NO_C99_FORMAT\n #define SZ_FMT \"%u\"\ndiff --git a/cache.h b/cache.h\nindex b1bd9e4..aa72791 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -484,6 +484,7 @@ extern struct blob *alloc_blob_node(void);\n extern struct tree *alloc_tree_node(void);\n extern struct commit *alloc_commit_node(void);\n extern struct tag *alloc_tag_node(void);\n+extern struct object *alloc_object_node(void);\n extern void alloc_report(void);\n \n /* trace.c */\ndiff --git a/object.c b/object.c\nindex 78a44a6..153ebac 100644\n--- a/object.c\n+++ b/object.c\n@@ -120,22 +120,13 @@ void created_object(const unsigned char *sha1, struct object *obj)\n \tnr_objs++;\n }\n \n-union any_object {\n-\tstruct object object;\n-\tstruct commit commit;\n-\tstruct tree tree;\n-\tstruct blob blob;\n-\tstruct tag tag;\n-};\n-\n struct object *lookup_unknown_object(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n \tif (!obj) {\n-\t\tunion any_object *ret = xcalloc(1, sizeof(*ret));\n-\t\tcreated_object(sha1, &ret->object);\n-\t\tret->object.type = OBJ_NONE;\n-\t\treturn &ret->object;\n+\t\tobj = alloc_object_node();\n+\t\tcreated_object(sha1, obj);\n+\t\tobj->type = OBJ_NONE;\n \t}\n \treturn obj;\n }\n-- \n1.5.1.1.107.g7a15\n"},{"id":"39609","messageId":"Pine.LNX.4.64.0704162210230.5473@woody.linux-foundation.org","threadId":"7705","inReplyTo":"Pine.LNX.4.64.0704162200420.5473@woody.linux-foundation.org","subject":"[FIXED PATCH 2/3] Clean up object creation to use more common code","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-17T05:11:43Z","receivedAt":"2007-04-17T05:11:43Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis replaces the fairly odd \"created_object()\" function that did _most_\nof the object setup with a more complete \"create_object()\" function that\nalso has a more natural calling convention.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nShould be identical to last version, except for the context around the \nfix.. It removes 20 lines of code. Yay.\n\n alloc.c  |    2 +-\n blob.c   |    8 ++------\n cache.h  |   14 +++++---------\n commit.c |    8 ++------\n object.c |   14 +++++++-------\n object.h |    2 +-\n tag.c    |   10 +++-------\n tree.c   |    8 ++------\n 8 files changed, 23 insertions(+), 43 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 53eba37..216c23a 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -20,7 +20,7 @@\n \n #define DEFINE_ALLOCATOR(name, type)\t\t\t\t\\\n static unsigned int name##_allocs;\t\t\t\t\\\n-struct name *alloc_##name##_node(void)\t\t\t\t\\\n+void *alloc_##name##_node(void)\t\t\t\t\t\\\n {\t\t\t\t\t\t\t\t\\\n \tstatic int nr;\t\t\t\t\t\t\\\n \tstatic type *block;\t\t\t\t\t\\\ndiff --git a/blob.c b/blob.c\nindex 0a9ea41..bd7d078 100644\n--- a/blob.c\n+++ b/blob.c\n@@ -6,12 +6,8 @@ const char *blob_type = \"blob\";\n struct blob *lookup_blob(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj) {\n-\t\tstruct blob *ret = alloc_blob_node();\n-\t\tcreated_object(sha1, &ret->object);\n-\t\tret->object.type = OBJ_BLOB;\n-\t\treturn ret;\n-\t}\n+\tif (!obj)\n+\t\treturn create_object(sha1, OBJ_BLOB, alloc_blob_node());\n \tif (!obj->type)\n \t\tobj->type = OBJ_BLOB;\n \tif (obj->type != OBJ_BLOB) {\ndiff --git a/cache.h b/cache.h\nindex aa72791..4de25cc 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -476,15 +476,11 @@ int decode_85(char *dst, const char *line, int linelen);\n void encode_85(char *buf, const unsigned char *data, int bytes);\n \n /* alloc.c */\n-struct blob;\n-struct tree;\n-struct commit;\n-struct tag;\n-extern struct blob *alloc_blob_node(void);\n-extern struct tree *alloc_tree_node(void);\n-extern struct commit *alloc_commit_node(void);\n-extern struct tag *alloc_tag_node(void);\n-extern struct object *alloc_object_node(void);\n+extern void *alloc_blob_node(void);\n+extern void *alloc_tree_node(void);\n+extern void *alloc_commit_node(void);\n+extern void *alloc_tag_node(void);\n+extern void *alloc_object_node(void);\n extern void alloc_report(void);\n \n /* trace.c */\ndiff --git a/commit.c b/commit.c\nindex 952095f..10466c4 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -98,12 +98,8 @@ struct commit *lookup_commit_reference(const unsigned char *sha1)\n struct commit *lookup_commit(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj) {\n-\t\tstruct commit *ret = alloc_commit_node();\n-\t\tcreated_object(sha1, &ret->object);\n-\t\tret->object.type = OBJ_COMMIT;\n-\t\treturn ret;\n-\t}\n+\tif (!obj)\n+\t\treturn create_object(sha1, OBJ_COMMIT, alloc_commit_node());\n \tif (!obj->type)\n \t\tobj->type = OBJ_COMMIT;\n \treturn check_commit(obj, sha1, 0);\ndiff --git a/object.c b/object.c\nindex 153ebac..7bd3fec 100644\n--- a/object.c\n+++ b/object.c\n@@ -105,11 +105,13 @@ static void grow_object_hash(void)\n \tobj_hash_size = new_hash_size;\n }\n \n-void created_object(const unsigned char *sha1, struct object *obj)\n+void *create_object(const unsigned char *sha1, int type, void *o)\n {\n+\tstruct object *obj = o;\n+\n \tobj->parsed = 0;\n \tobj->used = 0;\n-\tobj->type = OBJ_NONE;\n+\tobj->type = type;\n \tobj->flags = 0;\n \thashcpy(obj->sha1, sha1);\n \n@@ -118,16 +120,14 @@ void created_object(const unsigned char *sha1, struct object *obj)\n \n \tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n \tnr_objs++;\n+\treturn obj;\n }\n \n struct object *lookup_unknown_object(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj) {\n-\t\tobj = alloc_object_node();\n-\t\tcreated_object(sha1, obj);\n-\t\tobj->type = OBJ_NONE;\n-\t}\n+\tif (!obj)\n+\t\tobj = create_object(sha1, OBJ_NONE, alloc_object_node());\n \treturn obj;\n }\n \ndiff --git a/object.h b/object.h\nindex bdbf0fa..c0a5fd3 100644\n--- a/object.h\n+++ b/object.h\n@@ -47,7 +47,7 @@ extern struct object_refs *lookup_object_refs(struct object *);\n /** Internal only **/\n struct object *lookup_object(const unsigned char *sha1);\n \n-void created_object(const unsigned char *sha1, struct object *obj);\n+extern void *create_object(const unsigned char *sha1, int type, void *obj);\n \n /** Returns the object, having parsed it to find out what it is. **/\n struct object *parse_object(const unsigned char *sha1);\ndiff --git a/tag.c b/tag.c\nindex 56a49f4..330d287 100644\n--- a/tag.c\n+++ b/tag.c\n@@ -20,13 +20,9 @@ struct object *deref_tag(struct object *o, const char *warn, int warnlen)\n \n struct tag *lookup_tag(const unsigned char *sha1)\n {\n-        struct object *obj = lookup_object(sha1);\n-        if (!obj) {\n-                struct tag *ret = alloc_tag_node();\n-                created_object(sha1, &ret->object);\n-                ret->object.type = OBJ_TAG;\n-                return ret;\n-        }\n+\tstruct object *obj = lookup_object(sha1);\n+\tif (!obj)\n+\t\treturn create_object(sha1, OBJ_TAG, alloc_tag_node());\n \tif (!obj->type)\n \t\tobj->type = OBJ_TAG;\n         if (obj->type != OBJ_TAG) {\ndiff --git a/tree.c b/tree.c\nindex d188c0f..e5bfbce 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -127,12 +127,8 @@ int read_tree(struct tree *tree, int stage, const char **match)\n struct tree *lookup_tree(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj) {\n-\t\tstruct tree *ret = alloc_tree_node();\n-\t\tcreated_object(sha1, &ret->object);\n-\t\tret->object.type = OBJ_TREE;\n-\t\treturn ret;\n-\t}\n+\tif (!obj)\n+\t\treturn create_object(sha1, OBJ_TREE, alloc_tree_node());\n \tif (!obj->type)\n \t\tobj->type = OBJ_TREE;\n \tif (obj->type != OBJ_TREE) {\n-- \n1.5.1.1.107.g7a15\n"},{"id":"39610","messageId":"Pine.LNX.4.64.0704162211460.5473@woody.linux-foundation.org","threadId":"7705","inReplyTo":"Pine.LNX.4.64.0704162200420.5473@woody.linux-foundation.org","subject":"[DUBIOUS PATCH 3/3] Make the object lookup hash use a \"object index\" instead of a pointer","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-17T05:13:09Z","receivedAt":"2007-04-17T05:13:09Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis uses less memory on 64-bit architectures (a 32-bit object index\nrather than a full 64-bit pointer), but could also allow for some other\noptimizations.  However, most of them would require that we actually\nexpose the object index to other parts of the system, which we currently\ndon't.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nAs mentioned, the overhead of doing the index->object pointer conversion \nseems to be big enough that this isn't worth it.\n\nAdmittedly part of that overhead is the debugging code I added, so this \nmay not be that bad an idea after all, but still..\n\n alloc.c  |   89 ++++++++++++++++++++++++++++++++++++++++++++++++-------------\n cache.h  |   11 ++++---\n object.c |   50 +++++++++++++++++++++-------------\n object.h |    2 +-\n 4 files changed, 108 insertions(+), 44 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 216c23a..bc6aa30 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -16,27 +16,78 @@\n #include \"commit.h\"\n #include \"tag.h\"\n \n-#define BLOCKING 1024\n+/*\n+ * We allocate 1024 object nodes at a time.\n+ *\n+ * This not only avoids any fragmentation in the system \"malloc()\"\n+ * libraries, it also means that we can generate a denser \"object\n+ * index\" that does not need a full pointer: we can use an integer\n+ * with the low bits indicating the object node ID within an\n+ * allocation block, and the high bits indicating the allocation\n+ * block number.\n+ */\n+#define BLOCKING_BITS 10\n+#define BLOCKING_SIZE (1u << BLOCKING_BITS)\n+#define BLOCKING_MASK (BLOCKING_SIZE-1)\n \n-#define DEFINE_ALLOCATOR(name, type)\t\t\t\t\\\n-static unsigned int name##_allocs;\t\t\t\t\\\n-void *alloc_##name##_node(void)\t\t\t\t\t\\\n-{\t\t\t\t\t\t\t\t\\\n-\tstatic int nr;\t\t\t\t\t\t\\\n-\tstatic type *block;\t\t\t\t\t\\\n-\tvoid *ret;\t\t\t\t\t\t\\\n-\t\t\t\t\t\t\t\t\\\n-\tif (!nr) {\t\t\t\t\t\t\\\n-\t\tnr = BLOCKING;\t\t\t\t\t\\\n-\t\tblock = xmalloc(BLOCKING * sizeof(type));\t\\\n-\t}\t\t\t\t\t\t\t\\\n-\tnr--;\t\t\t\t\t\t\t\\\n-\tname##_allocs++;\t\t\t\t\t\\\n-\tret = block++;\t\t\t\t\t\t\\\n-\tmemset(ret, 0, sizeof(type));\t\t\t\t\\\n-\treturn ret;\t\t\t\t\t\t\\\n+struct alloc_descriptor {\n+\tunsigned int size, nr;\n+\tunsigned int block;\n+};\n+\n+struct block_descriptor {\n+\tunsigned int size;\n+\tunsigned char *base;\n+};\n+\n+static struct block_descriptor *block_allocations;\n+static unsigned int nr_block_allocations;\n+\n+static unsigned int alloc_new_block(unsigned int size)\n+{\n+\tstatic unsigned int index;\n+\tunsigned int i = ++index;\n+\n+\tif (i >= nr_block_allocations) {\n+\t\tunsigned int old = nr_block_allocations;\n+\t\tunsigned int nr = alloc_nr(i);\n+\t\tblock_allocations = xrealloc(block_allocations, nr * sizeof(*block_allocations));\n+\t\tmemset(block_allocations + old, 0, (nr - old) * sizeof(*block_allocations));\n+\t\tnr_block_allocations = nr;\n+\t}\n+\tblock_allocations[i].size = size;\n+\tblock_allocations[i].base = xcalloc(BLOCKING_SIZE, size);\n+\treturn i;\n+}\n+\n+static unsigned int allocate_one_index(struct alloc_descriptor *desc)\n+{\n+\tunsigned int nr = desc->nr++;\n+\tunsigned int index = nr & BLOCKING_MASK;\n+\tif (!index)\n+\t\tdesc->block = alloc_new_block(desc->size);\n+\treturn (desc->block << BLOCKING_BITS) + index;\n+}\n+\n+struct object *object_index_address(unsigned int index)\n+{\n+\tunsigned int block = index >> BLOCKING_BITS;\n+\tstruct block_descriptor *desc;\n+\n+\tindex &= BLOCKING_MASK;\n+\tif (!block || block >= nr_block_allocations)\n+\t\tdie(\"invalid object index (block = %u/%u)\", block, nr_block_allocations);\n+\tdesc = block_allocations + block;\n+\tif (!desc->size || !desc->base)\n+\t\tdie(\"bad object block index entry %u:%p\", desc->size, desc->base);\n+\treturn (struct object *)(index * desc->size + desc->base);\n }\n \n+#define DEFINE_ALLOCATOR(name, type)\t\t\t\t\\\n+static struct alloc_descriptor name##_desc = { sizeof(type) };\t\\\n+unsigned int alloc_##name##_node(void)\t\t\t\t\\\n+{ return allocate_one_index(&name##_desc); }\n+\n union any_object {\n \tstruct object object;\n \tstruct blob blob;\n@@ -65,7 +116,7 @@ static void report(const char* name, unsigned int count, size_t size)\n #undef SZ_FMT\n \n #define REPORT(name)\t\\\n-    report(#name, name##_allocs, name##_allocs*sizeof(struct name) >> 10)\n+    report(#name, name##_desc.nr, name##_desc.nr*sizeof(struct name) >> 10)\n \n void alloc_report(void)\n {\ndiff --git a/cache.h b/cache.h\nindex 4de25cc..9342980 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -476,12 +476,13 @@ int decode_85(char *dst, const char *line, int linelen);\n void encode_85(char *buf, const unsigned char *data, int bytes);\n \n /* alloc.c */\n-extern void *alloc_blob_node(void);\n-extern void *alloc_tree_node(void);\n-extern void *alloc_commit_node(void);\n-extern void *alloc_tag_node(void);\n-extern void *alloc_object_node(void);\n+extern unsigned int alloc_blob_node(void);\n+extern unsigned int alloc_tree_node(void);\n+extern unsigned int alloc_commit_node(void);\n+extern unsigned int alloc_tag_node(void);\n+extern unsigned int alloc_object_node(void);\n extern void alloc_report(void);\n+extern struct object *object_index_address(unsigned int index);\n \n /* trace.c */\n extern int nfasprintf(char **str, const char *fmt, ...);\ndiff --git a/object.c b/object.c\nindex 7bd3fec..a91d238 100644\n--- a/object.c\n+++ b/object.c\n@@ -5,7 +5,11 @@\n #include \"commit.h\"\n #include \"tag.h\"\n \n-static struct object **obj_hash;\n+struct hash_entry {\n+\tunsigned int index;\n+};\n+\n+static struct hash_entry *obj_hash;\n static int nr_objs, obj_hash_size;\n \n unsigned int get_max_object_index(void)\n@@ -13,9 +17,11 @@ unsigned int get_max_object_index(void)\n \treturn obj_hash_size;\n }\n \n+/* Purely for external object walkers (like fsck) */\n struct object *get_indexed_object(unsigned int idx)\n {\n-\treturn obj_hash[idx];\n+\tunsigned int object_index = obj_hash[idx].index;\n+\treturn object_index ? object_index_address(object_index) : NULL;\n }\n \n static const char *object_type_strings[] = {\n@@ -49,16 +55,16 @@ static unsigned int hash_obj(struct object *obj, unsigned int n)\n \treturn hash % n;\n }\n \n-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n+static void insert_obj_hash(unsigned int object_index, struct object *object, struct hash_entry *hash, unsigned int size)\n {\n-\tint j = hash_obj(obj, size);\n+\tint j = hash_obj(object, size);\n \n-\twhile (hash[j]) {\n+\twhile (hash[j].index) {\n \t\tj++;\n \t\tif (j >= size)\n \t\t\tj = 0;\n \t}\n-\thash[j] = obj;\n+\thash[j].index = object_index;\n }\n \n static int hashtable_index(const unsigned char *sha1)\n@@ -71,43 +77,49 @@ static int hashtable_index(const unsigned char *sha1)\n struct object *lookup_object(const unsigned char *sha1)\n {\n \tint i;\n-\tstruct object *obj;\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n \ti = hashtable_index(sha1);\n-\twhile ((obj = obj_hash[i]) != NULL) {\n-\t\tif (!hashcmp(sha1, obj->sha1))\n+\tfor (;;) {\n+\t\tstruct hash_entry *entry = obj_hash + i;\n+\t\tunsigned int index = entry->index;\n+\t\tstruct object *obj;\n+\n+\t\tif (!index)\n \t\t\tbreak;\n+\t\tobj = object_index_address(index);\n+\t\tif (!hashcmp(sha1, obj->sha1))\n+\t\t\treturn obj;\n \t\ti++;\n \t\tif (i == obj_hash_size)\n \t\t\ti = 0;\n \t}\n-\treturn obj;\n+\treturn NULL;\n }\n \n static void grow_object_hash(void)\n {\n \tint i;\n \tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n-\tstruct object **new_hash;\n+\tstruct hash_entry *new_hash;\n \n-\tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n+\tnew_hash = xcalloc(new_hash_size, sizeof(struct hash_entry));\n \tfor (i = 0; i < obj_hash_size; i++) {\n-\t\tstruct object *obj = obj_hash[i];\n-\t\tif (!obj)\n+\t\tunsigned int index = obj_hash[i].index;\n+\t\tif (!index)\n \t\t\tcontinue;\n-\t\tinsert_obj_hash(obj, new_hash, new_hash_size);\n+\t\tinsert_obj_hash(index, object_index_address(index), new_hash, new_hash_size);\n \t}\n \tfree(obj_hash);\n \tobj_hash = new_hash;\n \tobj_hash_size = new_hash_size;\n }\n \n-void *create_object(const unsigned char *sha1, int type, void *o)\n+void *create_object(const unsigned char *sha1, int type, unsigned int index)\n {\n-\tstruct object *obj = o;\n+\tstruct object *obj = object_index_address(index);\n \n \tobj->parsed = 0;\n \tobj->used = 0;\n@@ -118,7 +130,7 @@ void *create_object(const unsigned char *sha1, int type, void *o)\n \tif (obj_hash_size - 1 <= nr_objs * 2)\n \t\tgrow_object_hash();\n \n-\tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n+\tinsert_obj_hash(index, obj, obj_hash, obj_hash_size);\n \tnr_objs++;\n \treturn obj;\n }\n@@ -127,7 +139,7 @@ struct object *lookup_unknown_object(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n \tif (!obj)\n-\t\tobj = create_object(sha1, OBJ_NONE, alloc_object_node());\n+\t\treturn create_object(sha1, OBJ_NONE, alloc_object_node());\n \treturn obj;\n }\n \ndiff --git a/object.h b/object.h\nindex c0a5fd3..099bbdb 100644\n--- a/object.h\n+++ b/object.h\n@@ -47,7 +47,7 @@ extern struct object_refs *lookup_object_refs(struct object *);\n /** Internal only **/\n struct object *lookup_object(const unsigned char *sha1);\n \n-extern void *create_object(const unsigned char *sha1, int type, void *obj);\n+extern void *create_object(const unsigned char *sha1, int type, unsigned int object_index);\n \n /** Returns the object, having parsed it to find out what it is. **/\n struct object *parse_object(const unsigned char *sha1);\n-- \n1.5.1.1.107.g7a15\n"}]}