{"thread":{"id":"202","subject":"[PATCH] multi item packed files","startedAt":"2005-04-21T15:13:13Z","lastAt":"2005-04-25T22:20:57Z","messageCount":17,"participants":["Chris Mason","Linus Torvalds","Krzysztof Halasa","Martin Uecker"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"1136","messageId":"200504211113.13630.mason@suse.com","threadId":"202","inReplyTo":null,"subject":"[PATCH] multi item packed files","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-21T15:13:13Z","receivedAt":"2005-04-21T15:13:13Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"Hello,\n\nThere have been a few threads on making git more space efficient, and \neventually someone mentions tiny files and space fragmentation.  Now that git \nobject names are decoupled from their compression, it's easier to consider a \na variety of compression algorithms.  I whipped up a really silly \"pack files \ntogether\" compression.\n\nThis would maintain the write once semantics but allow a simple mechanism \nwhere objects are combined together.  Choosing which objects to combine is \neasy, things put together into update-cache go together.  This gives us more \nspace efficiency and no seeks when reading that packed file off disk.\n\nA natural extension to this is to make update-cache --commit-tree, which \nincludes the files produced by write-tree and commit-tree into the same \npacked file.  (I haven't coded this).\n\nThe layout works like this:\n\n1) a new object type \"packed\" is added.\n2) new objects are buffered into a packed object, until it gets to around 32k \nin size.  This is complete arbitrary but felt about right.\n3) The packed object is writting to git storage and then hard links are made \nto the packed object from the sha1 filename of each object inside.\n4) read_sha1_file is changed to recognize the packed object and search inside.\n\nI did a simple test on the 2.6.11 tree with my 100 patches applied.  Without \npacking, .git is 99MB.  With packing it only needs 62MB:\n\nread speeds don't suffer with this, time to read-tree ; checkout-cache -a -f \nfrom a cold cache were the same.  I could get the times lower with the patch \nby caching the uncompressed data, since in theory I should be faster here.\n\nUsing this on data you care about would be a really bad idea right now.  I'm \nonly posting the patch to get the basic idea across for benchmarking and \ndiscussion.\n\n-chris\n\n\ndiff -ur linus.back/cache.h linus/cache.h\n--- linus.back/cache.h\t2005-04-21 11:05:27.971607944 -0400\n+++ linus/cache.h\t2005-04-21 09:35:47.173613576 -0400\n@@ -109,7 +109,7 @@\n \n /* Read and unpack a sha1 file into memory, write memory to a sha1 file */\n extern void * map_sha1_file(const unsigned char *sha1, unsigned long *size);\n-extern void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size);\n+extern void * unpack_sha1_file(const unsigned char *sha1, void *map, unsigned long mapsize, char *type, unsigned long *size);\n extern void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size);\n extern int write_sha1_file(char *buf, unsigned len, unsigned char *return_sha1);\n extern int check_sha1_signature(unsigned char *sha1, void *buf, unsigned long size, const char *type);\n@@ -117,6 +117,10 @@\n /* Convert to/from hex/sha1 representation */\n extern int get_sha1_hex(const char *hex, unsigned char *sha1);\n extern char *sha1_to_hex(const unsigned char *sha1);\t/* static buffer result! */\n+extern int pack_sha1_buffer(void *buf, unsigned long buf_len, \n+\t\t     unsigned char *returnsha1, char **dest, \n+\t\t     unsigned long *dest_size);\n+int write_packed_buffer(void *buf, unsigned long len);\n \n /* General helper functions */\n extern void usage(const char *err);\ndiff -ur linus.back/cat-file.c linus/cat-file.c\n--- linus.back/cat-file.c\t2005-04-21 11:05:27.971607944 -0400\n+++ linus/cat-file.c\t2005-04-21 10:04:29.871723656 -0400\n@@ -23,7 +23,7 @@\n \t\ttype[size] = '\\n';\n \t\tsize++;\n \t} else if (strcmp(type, argv[1])) {\n-\t\tdie(\"cat-file %s: bad tag\", argv[2]);\n+\t\tdie(\"cat-file %s: bad tag (%s: %s)\", argv[2], type, argv[1]);\n \t}\n \n \twhile (size > 0) {\ndiff -ur linus.back/fsck-cache.c linus/fsck-cache.c\n--- linus.back/fsck-cache.c\t2005-04-21 11:05:27.974607488 -0400\n+++ linus/fsck-cache.c\t2005-04-21 09:14:03.139856840 -0400\n@@ -85,7 +85,7 @@\n \t\tif (map) {\n \t\t\tchar type[100];\n \t\t\tunsigned long size;\n-\t\t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, &size);\n+\t\t\tvoid *buffer = unpack_sha1_file(sha1, map, mapsize, type, &size);\n \t\t\tif (!buffer)\n \t\t\t\treturn -1;\n \t\t\tif (check_sha1_signature(sha1, buffer, size, type) < 0)\ndiff -ur linus.back/sha1_file.c linus/sha1_file.c\n--- linus.back/sha1_file.c\t2005-04-21 11:05:27.978606880 -0400\n+++ linus/sha1_file.c\t2005-04-21 10:41:51.280977656 -0400\n@@ -116,7 +116,8 @@\n \treturn map;\n }\n \n-void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size)\n+void * unpack_sha1_file(const unsigned char *sha1, void *map, \n+\t\t\tunsigned long mapsize, char *type, unsigned long *size)\n {\n \tint ret, bytes;\n \tz_stream stream;\n@@ -134,12 +135,12 @@\n \tret = inflate(&stream, 0);\n \tif (sscanf(buffer, \"%10s %lu\", type, size) != 2)\n \t\treturn NULL;\n-\n \tbytes = strlen(buffer) + 1;\n \tbuf = malloc(*size);\n-\tif (!buf)\n+\tif (!buf) {\n+\t\tperror(\"malloc\");\n \t\treturn NULL;\n-\n+\t}\n \tmemcpy(buf, buffer + bytes, stream.total_out - bytes);\n \tbytes = stream.total_out - bytes;\n \tif (bytes < *size && ret == Z_OK) {\n@@ -149,6 +150,36 @@\n \t\t\t/* nothing */;\n \t}\n \tinflateEnd(&stream);\n+\n+\t/* we've found a packed object */\n+\tif (strcmp(type, \"packed\") == 0) {\n+\t\tchar *p = buf;\n+\t\tif (!sha1)\n+\t\t\treturn NULL;\n+\t\twhile(p < buf + *size) {\n+\t\t\tunsigned long item_len;\n+\t\t\tunsigned char sha1_hex[50];\n+\t\t\tunsigned char item_sha[20];\n+\t\t\tsscanf(p, \"%50s %lu\", sha1_hex, &item_len);\n+\t\t\tif (get_sha1_hex(sha1_hex, item_sha))\n+\t\t\t\tdie(\"packed file corruption\");\n+\t\t\tif (memcmp(item_sha, sha1, 20) == 0) {\n+\t\t\t\tchar *temp;\n+\t\t\t\tchar *r;\n+\t\t\t\ttemp = p + strlen(p) + 1;\n+\t\t\t\tif (sscanf(temp, \"%10s %lu\", type, size) != 2)\n+\t\t\t\t\treturn NULL;\n+\t\t\t\tr = malloc(*size);\n+\t\t\t\tif (!r)\n+\t\t\t\t\treturn NULL;\n+\t\t\t\tmemcpy(r, temp + strlen(temp) + 1, *size);\n+\t\t\t\tfree(buf);\n+\t\t\t\treturn r;\n+\t\t\t}\n+\t\t\tp += strlen(p) + 1 + item_len;\n+\t\t}\n+\t\treturn NULL;\n+\t}\n \treturn buf;\n }\n \n@@ -159,7 +190,7 @@\n \n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n-\t\tbuf = unpack_sha1_file(map, mapsize, type, size);\n+\t\tbuf = unpack_sha1_file(sha1, map, mapsize, type, size);\n \t\tmunmap(map, mapsize);\n \t\treturn buf;\n \t}\n@@ -305,3 +336,111 @@\n \tclose(fd);\n \treturn 0;\n }\n+\n+int pack_sha1_buffer(void *buf, unsigned long buf_len, \n+\t\t     unsigned char *returnsha1, char **dest, \n+\t\t     unsigned long *dest_size)\n+{\n+\tunsigned char sha1[20];\n+\tSHA_CTX c;\n+\tchar *filename;\n+\tstruct stat st;\n+\tvoid *p;\n+\tint metadata_size;\n+\n+\t/* Sha1.. */\n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, buf, buf_len);\n+\tSHA1_Final(sha1, &c);\n+\n+\tif (returnsha1)\n+\t\tmemcpy(returnsha1, sha1, 20);\n+\n+\tfilename = sha1_file_name(sha1);\n+\tif (stat(filename, &st) == 0)\n+\t\treturn 0;\n+\n+\tp = realloc(*dest, *dest_size + buf_len + 250);\n+\tif (!p)\n+\t\treturn -1;\n+\t*dest = p;\n+\tp += *dest_size;\n+\tmetadata_size = 1 + sprintf(p, \"%s %lu\", sha1_to_hex(sha1), buf_len);\n+\tp += metadata_size;\n+\tmemcpy(p, buf, buf_len);\n+\t*dest_size += buf_len + metadata_size;\n+\treturn 0;\n+}\n+\n+int write_packed_buffer(void *buf, unsigned long len)\n+{\n+\tunsigned char sha1[20];\n+\tSHA_CTX c;\n+\tchar *filename;\n+\tchar *p;\n+\tchar *metadata = malloc(200);\n+\tunsigned char sha1_hex[50];\n+\tint metadata_size;\n+\tint fd;\n+\tint ret = 0;\n+\n+\tmetadata_size = 1+sprintf(metadata, \"packed %lu\", len);\n+\n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, metadata, metadata_size);\n+\tSHA1_Update(&c, buf, len);\n+\tSHA1_Final(sha1, &c);\n+\n+\tfilename = strdup(sha1_file_name(sha1));\n+\tfd = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);\n+\tif (fd < 0) {\n+\t\tif (errno != EEXIST)\n+\t\t\treturn -1;\n+\t\t/* add collision check! */\n+\t} else {\n+\t\tchar *compressed;\n+\t\tz_stream stream;\n+\t\tunsigned long size;\n+\t\t/* Set it up */\n+\t\tmemset(&stream, 0, sizeof(stream));\n+\t\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n+\t\tsize = deflateBound(&stream, len + metadata_size);\n+\t\tcompressed = malloc(size);\n+\n+\t\t/* Compress it */\n+\t\tstream.next_in = metadata;\n+\t\tstream.avail_in = metadata_size;\n+\t\tstream.next_out = compressed;\n+\t\tstream.avail_out = size;\n+\t\twhile (deflate(&stream, 0) == Z_OK)\n+\t\t\t/* nothing */;\n+\t\tstream.next_in = buf;\n+\t\tstream.avail_in = len;\n+\t\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n+\t\t\t/* nothing */;\n+\t\tdeflateEnd(&stream);\n+\t\twrite(fd, compressed, stream.total_out);\n+\t\tclose(fd);\n+\t}\n+\tfree(metadata);\n+\t/* now we have the packed blob on disk, lets link to it */\n+\tp = buf;\n+\twhile(p < (char *)buf + len) {\n+\t\tunsigned long item_len;\n+\t\tchar *item_file;\n+\t\tsscanf(p, \"%50s %lu\\n\", sha1_hex, &item_len);\n+\t\t/* + 1 for the null at the end of p */\n+\t\tp += strlen(p) + item_len + 1;\n+\n+\t\tif (get_sha1_hex(sha1_hex, sha1))\n+\t\t\tdie(\"packed file corruption\");\n+\t\t\n+\t\titem_file = sha1_file_name(sha1);\n+\t\tif (link(filename, item_file) && errno != EEXIST) {\n+\t\t\tret = -errno;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\tfree(filename);\n+\treturn ret;\n+}\ndiff -ur linus.back/update-cache.c linus/update-cache.c\n--- linus.back/update-cache.c\t2005-04-21 11:05:27.979606728 -0400\n+++ linus/update-cache.c\t2005-04-21 10:42:08.109419344 -0400\n@@ -14,55 +14,33 @@\n  */\n static int allow_add = 0, allow_remove = 0;\n \n-static int index_fd(unsigned char *sha1, int fd, struct stat *st)\n+static int index_fd(unsigned char *sha1, int fd, struct stat *st, char **packed_buffer, unsigned long *packed_len)\n {\n-\tz_stream stream;\n \tunsigned long size = st->st_size;\n-\tint max_out_bytes = size + 200;\n-\tvoid *out = malloc(max_out_bytes);\n \tvoid *metadata = malloc(200);\n \tint metadata_size;\n \tvoid *in;\n-\tSHA_CTX c;\n+\tchar *copy;\n+\tint ret;\n \n \tin = \"\";\n \tif (size)\n \t\tin = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n \tclose(fd);\n-\tif (!out || (int)(long)in == -1)\n+\tif (!metadata || (int)(long)in == -1)\n \t\treturn -1;\n \n \tmetadata_size = 1+sprintf(metadata, \"blob %lu\", size);\n-\n-\tSHA1_Init(&c);\n-\tSHA1_Update(&c, metadata, metadata_size);\n-\tSHA1_Update(&c, in, size);\n-\tSHA1_Final(sha1, &c);\n-\n-\tmemset(&stream, 0, sizeof(stream));\n-\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n-\n-\t/*\n-\t * ASCII size + nul byte\n-\t */\t\n-\tstream.next_in = metadata;\n-\tstream.avail_in = metadata_size;\n-\tstream.next_out = out;\n-\tstream.avail_out = max_out_bytes;\n-\twhile (deflate(&stream, 0) == Z_OK)\n-\t\t/* nothing */;\n-\n-\t/*\n-\t * File content\n-\t */\n-\tstream.next_in = in;\n-\tstream.avail_in = size;\n-\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n-\t\t/*nothing */;\n-\n-\tdeflateEnd(&stream);\n-\t\n-\treturn write_sha1_buffer(sha1, out, stream.total_out);\n+\tcopy = malloc(metadata_size + size);\n+\tif (!copy)\n+\t\treturn -1;\n+\tmemcpy(copy, metadata, metadata_size);\n+\tmemcpy(copy + metadata_size, in, size);\n+\tret = pack_sha1_buffer(copy, metadata_size + size,\n+\t\t\t       sha1, packed_buffer, packed_len);\n+\tmunmap(in, size);\n+\tfree(copy);\n+\treturn ret;\n }\n \n /*\n@@ -85,7 +63,7 @@\n \tce->ce_size = htonl(st->st_size);\n }\n \n-static int add_file_to_cache(char *path)\n+static int add_file_to_cache(char *path, char **packed_buffer, unsigned long *packed_len)\n {\n \tint size, namelen;\n \tstruct cache_entry *ce;\n@@ -113,9 +91,14 @@\n \tce->ce_mode = create_ce_mode(st.st_mode);\n \tce->ce_flags = htons(namelen);\n \n-\tif (index_fd(ce->sha1, fd, &st) < 0)\n+\tif (index_fd(ce->sha1, fd, &st, packed_buffer, packed_len) < 0)\n \t\treturn -1;\n \n+\tif (*packed_len > 32768) {\n+\t\tif (write_packed_buffer(*packed_buffer, *packed_len))\n+\t\t\treturn -1;\n+\t\t*packed_len = 0;\n+\t}\n \treturn add_cache_entry(ce, allow_add);\n }\n \n@@ -286,6 +269,8 @@\n {\n \tint i, newfd, entries;\n \tint allow_options = 1;\n+\tchar *packed_buffer = NULL;\n+\tunsigned long packed_len = 0;\n \n \tnewfd = open(\".git/index.lock\", O_RDWR | O_CREAT | O_EXCL, 0600);\n \tif (newfd < 0)\n@@ -330,9 +315,14 @@\n \t\t\tfprintf(stderr, \"Ignoring path %s\\n\", argv[i]);\n \t\t\tcontinue;\n \t\t}\n-\t\tif (add_file_to_cache(path))\n+\t\tif (add_file_to_cache(path, &packed_buffer, &packed_len))\n \t\t\tdie(\"Unable to add %s to database\", path);\n \t}\n+\tif (packed_buffer) {\n+\t\tif (packed_len)\n+\t    \t\tif (write_packed_buffer(packed_buffer, packed_len))\n+\t\tfree(packed_buffer);\n+\t}\n \tif (write_cache(newfd, active_cache, active_nr) ||\n \t    rename(\".git/index.lock\", \".git/index\"))\n \t\tdie(\"Unable to write new cachefile\");\n"},{"id":"1137","messageId":"Pine.LNX.4.58.0504210832490.2344@ppc970.osdl.org","threadId":"202","inReplyTo":"200504211113.13630.mason@suse.com","subject":"Re: [PATCH] multi item packed files","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-21T15:41:12Z","receivedAt":"2005-04-21T15:41:12Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Apr 2005, Chris Mason wrote:\n> \n> There have been a few threads on making git more space efficient, and \n> eventually someone mentions tiny files and space fragmentation.  Now that git \n> object names are decoupled from their compression, it's easier to consider a \n> a variety of compression algorithms.  I whipped up a really silly \"pack files \n> together\" compression.\n\nCareful.\n\nThis is something that needs history to tell whether it's effective. In\nparticular, if one file changes and another one does not, your packed\narchive now ends up being a new blob, so while you \"saved space\" by having\njust one blob for the object, in reality you didn't save any space at all\nbecause with the <x> files changing, you just guaranteed that the packed\nblob changes <x> times more often.\n\nSee? Your \"packing in space\" ends up also resulting in \"packing in time\", \nand you didn't actually win anything.\n\n(If you did a good job of packing, you hopefully didn't _lose_ anything\neither - you needed 1:<x> number of objects that took 1:<x> the space if\nthe packing ended up perfect - but since you needed <x> times more of\nthese objects unless they all change together, you end up with exactly the\nsame space usage).\n\nSo the argument is: you can't lose with the method, and you _can_ win. \nRight?\n\nWrong. You most definitely _can_ lose: you end up having to optimize for\none particular filesystem blocking size, and you'll lose on any other\nfilesystem. And you'll lose on the special filesystem of \"network\ntraffic\", which is byte-granular.\n\nI don't want to pee on peoples parades, and I'm all for gathering numbers, \nbut the thing is, the current git isn't actually all that bad, and I \nguarantee that it's hard to make it better without using delta \nrepresentation. And the current thing is really really simple.\n\n\t\tLinus\n"},{"id":"1143","messageId":"200504211223.03479.mason@suse.com","threadId":"202","inReplyTo":"Pine.LNX.4.58.0504210832490.2344@ppc970.osdl.org","subject":"Re: [PATCH] multi item packed files","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-21T16:23:02Z","receivedAt":"2005-04-21T16:23:02Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Thursday 21 April 2005 11:41, Linus Torvalds wrote:\n> On Thu, 21 Apr 2005, Chris Mason wrote:\n> > There have been a few threads on making git more space efficient, and\n> > eventually someone mentions tiny files and space fragmentation.  Now that\n> > git object names are decoupled from their compression, it's easier to\n> > consider a a variety of compression algorithms.  I whipped up a really\n> > silly \"pack files together\" compression.\n>\n> Careful.\n>\n> This is something that needs history to tell whether it's effective. In\n> particular, if one file changes and another one does not, your packed\n> archive now ends up being a new blob, so while you \"saved space\" by having\n> just one blob for the object, in reality you didn't save any space at all\n> because with the <x> files changing, you just guaranteed that the packed\n> blob changes <x> times more often.\n\nThe packed blob lives in git but never makes it into a tree.  Lets say that I \nhave a packed blob with files \"a, b, c\", and another packed blob with files \n\"x, y, z\".  Someone changes files, b and z and then runs update-cache b z.\n\nNow we have 2 unchanged packed blobs: \"a, b, c\", \"x, y, z\",  and one new \npacked blob: \"b_new, z_new\".  This means that in order for the packing to \nhelp, we have to change more then one file at a time.  That's why it would be \ngood to have update-cache include the write-tree and commit-tree.\n\n>\n> See? Your \"packing in space\" ends up also resulting in \"packing in time\",\n> and you didn't actually win anything.\n>\n> (If you did a good job of packing, you hopefully didn't _lose_ anything\n> either - you needed 1:<x> number of objects that took 1:<x> the space if\n> the packing ended up perfect - but since you needed <x> times more of\n> these objects unless they all change together, you end up with exactly the\n> same space usage).\n>\n> So the argument is: you can't lose with the method, and you _can_ win.\n> Right?\n>\n> Wrong. You most definitely _can_ lose: you end up having to optimize for\n> one particular filesystem blocking size, and you'll lose on any other\n> filesystem. And you'll lose on the special filesystem of \"network\n> traffic\", which is byte-granular.\n>\nThe patch does have one extra directory entry (for the packed blob), but from \na network point of view roughly the same number of bytes should be copied.  \nThe hardlinks won't play nice with rsync though, soft links might be better.\n\npacking isn't just about filesystem block sizes, it's about locality.  All the \nhashing means pretty much every access in git is random.  With packing we can \nat least try to put a single changeset together on disk.  Right now it \ndoesn't matter much, but when the git tree is 6GB in two years we'll feel the \npain.\n\n> I don't want to pee on peoples parades, and I'm all for gathering numbers,\n> but the thing is, the current git isn't actually all that bad, and I\n> guarantee that it's hard to make it better without using delta\n> representation. And the current thing is really really simple.\n>\n\nGrin, if I thought you wanted the patch I might have tried to pretty it up a \nlittle.  The point is that all the discussions about ways to make git use \nless space end up stuck in \"but wait, that'll make a bunch of tiny files and \nfilesystems aren't good at that\".  So I believe some kind of packing is a \nrequired building block for any kind of delta storage.\n\n-chris\n"},{"id":"1179","messageId":"m3u0m0q69a.fsf@defiant.localdomain","threadId":"202","inReplyTo":"Pine.LNX.4.58.0504210832490.2344@ppc970.osdl.org","subject":"Re: [PATCH] multi item packed files","fromName":"Krzysztof Halasa","fromEmail":"khc@pm.waw.pl","sentAt":"2005-04-21T19:28:17Z","receivedAt":"2005-04-21T19:28:17Z","isPatch":true,"sender":{"key":"khc@pm.waw.pl","avatar":null},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Wrong. You most definitely _can_ lose: you end up having to optimize for\n> one particular filesystem blocking size, and you'll lose on any other\n> filesystem. And you'll lose on the special filesystem of \"network\n> traffic\", which is byte-granular.\n\nIf someone needs better on-disk ratio, (s)he can go with 1 KB filesystem\nor something like that, without all the added complexity of packing.\n\nIf we want to optimize that further, I would try doing it at the\nunderlying filesystem level. For example, loop-mounted one.\n-- \nKrzysztof Halasa\n"},{"id":"1184","messageId":"Pine.LNX.4.58.0504211301240.2344@ppc970.osdl.org","threadId":"202","inReplyTo":"m3u0m0q69a.fsf@defiant.localdomain","subject":"Re: [PATCH] multi item packed files","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-21T20:07:25Z","receivedAt":"2005-04-21T20:07:25Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Apr 2005, Krzysztof Halasa wrote:\n> \n> If someone needs better on-disk ratio, (s)he can go with 1 KB filesystem\n> or something like that, without all the added complexity of packing.\n\nI really think the argument that \"you can use filesystem feature XYZ\" is \nbogus.\n\nI know that I'm not willing to switch filesystems on a whim. I suspect \nnobody else is either. I'm not going to create a loopback filesystem just \nfor git, it's just too much pain.\n\nAnd dammit, if I'm the original author and likely biggest power-user, and \n_I_ can't be bothered to use special filesystems, then who can? Nobody.\n\nThis is why I absolutely do not believe in arguments like \"if your\nfilesystem doesn't do tail packing, you shouldn't use it\" or \"if your\ndon't have name hashing enabled in your filesystem it's broken\".\n\nI'm perfectly willing to optimize for the common case, but that's as far \nas it goes. I do not want to make fundamental design decisions that depend \non the target filesystem having some particular feature. \n\n(I'll happily make decisions that say that the target _OS_ has to have a \nparticular feature, though. I'll require a sane base-level for \nfunctionality, but not something like filesystem details).\n\n\t\t\tLinus\n"},{"id":"1186","messageId":"200504211622.48065.mason@suse.com","threadId":"202","inReplyTo":"m3u0m0q69a.fsf@defiant.localdomain","subject":"Re: [PATCH] multi item packed files","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-21T20:22:46Z","receivedAt":"2005-04-21T20:22:46Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Thursday 21 April 2005 15:28, Krzysztof Halasa wrote:\n> Linus Torvalds <torvalds@osdl.org> writes:\n> > Wrong. You most definitely _can_ lose: you end up having to optimize for\n> > one particular filesystem blocking size, and you'll lose on any other\n> > filesystem. And you'll lose on the special filesystem of \"network\n> > traffic\", which is byte-granular.\n>\n> If someone needs better on-disk ratio, (s)he can go with 1 KB filesystem\n> or something like that, without all the added complexity of packing.\n>\n> If we want to optimize that further, I would try doing it at the\n> underlying filesystem level. For example, loop-mounted one.\n\nShrug, we shouldn't need help from the kernel for something like this.  git as \na database hits worst case scenarios for almost every FS.\n\nWe've got:\n\n1) subdirectories with lots of files\n2) wasted space for tiny files\n3) files that are likely to be accessed together spread across the whole disk\n\nOne compromise for SCM use would be one packed file per commit, with an index \nthat lets us quickly figure out which commit has a particular version of a \ngiven file.  My hack gets something close to that (broken into 32k chunks for \nno good reason), and the index to find a given file is just the git directory \ntree.\n\nBut my code does hide the fact that we're packing things from most of the git \ninterfaces.  So I can almost keep a straight face while claiming to be true \nto the original git design...almost.  The whole setup is far from perfect, \nbut it is one option for addressing points 2 & 3 above.\n\n-chris\n"},{"id":"1210","messageId":"Pine.LNX.4.58.0504211530370.2344@ppc970.osdl.org","threadId":"202","inReplyTo":"200504211622.48065.mason@suse.com","subject":"Re: [PATCH] multi item packed files","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-21T22:47:10Z","receivedAt":"2005-04-21T22:47:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Apr 2005, Chris Mason wrote:\n> \n> Shrug, we shouldn't need help from the kernel for something like this.  git as \n> a database hits worst case scenarios for almost every FS.\n\nI really disagree. \n\n> We've got:\n> \n> 1) subdirectories with lots of files\n> 2) wasted space for tiny files\n> 3) files that are likely to be accessed together spread across the whole disk\n\nOn the other hand, git does a lot of things that are just _lovely_ for a \nfilesystem:\n\n - it never rewrites a file. Rewriting a file is unquestionably _the_ \n   single worst access pattern for any filesystem. In contrast, never\n   writing to a file again means that filesystems can optimize their\n   layout and that things like defragmentation actually works.\n\n - it caches beautifully, and efficiently. Part of it comes from never \n   modifying files after they are written (which means that any network \n   filesystem automatically breathes a huge sign of relief), but part of \n   it is that it always reads full files, and the layout is done so that \n   it really actually _uses_ everything it reads.\n\n   It also caches beautifully on a memory subsystem level, largely for the\n   same reasons.\n\n - it doesn't use tons of directories.\n\n   You say that \"subdirectories with lots of files\" is painful, but that's \n   not really the whole story. A _deep_ directory structure tends to \n   actually be worse in many ways, because it's much easier to optimize a \n   flat directory structure than a deep one. In other words, git ends up \n   making name hashing etc _productive_. \n\nSo yes, it's a bit wasteful. But it's wasteful of what is absolutely the\ncheapest resource around: disk space. It's not a huge downside, and in\nfact I really do believe that the biggest downside _by_far_ in diskspace\nutilization is the _seek_ costs, not the space itself. Let's face it, \nanybody who wants three years of kernel archives and thinks that 3GB of \ndisk is too much, has some serious problems.\n\nThe _seek_ issue is real, but git actually has a very nice architecture\neven there: not only dos it cache really really well (and you can do a\nsimple \"ls-tree $(cat .git/HEAD)\" and populate the case from the results),\nbut the low level of indirection in a git archive means that it's almost\ntotally prefetchable with near-perfect access patterns.\n\nIn seeking, the real cost is synchronization, and the git model actually\nmeans that there are very few seeks that have to be synchronized. You\ncould literally do the \"ls-tree\" thing and make an absolutely trivial\nprefetcher that did the prefetching with enough parallellism that the\nfilesystem could probably get decent IO performance out of a disk.\n\nIn other words, we really could have a \"git prefetch\" command that would \npopulate the cache of the current head quite efficiently. Because the data \nlayout supports that.\n\n\t\tLinus\n"},{"id":"1222","messageId":"200504212016.16729.mason@suse.com","threadId":"202","inReplyTo":"Pine.LNX.4.58.0504211530370.2344@ppc970.osdl.org","subject":"Re: [PATCH] multi item packed files","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-22T00:16:16Z","receivedAt":"2005-04-22T00:16:16Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Thursday 21 April 2005 18:47, Linus Torvalds wrote:\n> On Thu, 21 Apr 2005, Chris Mason wrote:\n> > Shrug, we shouldn't need help from the kernel for something like this. \n> > git as a database hits worst case scenarios for almost every FS.\n\n[ ... ]\n\nWe somewhat agree on most of this, I snipped out the parts that aren't worth \nnitpicking over.  git is really fast right now, and I'm all for throwing \ndrive space at things to solve problems.  I just don't think we have to throw \nas much space at it as we are.\n\n> The _seek_ issue is real, but git actually has a very nice architecture\n> even there: not only dos it cache really really well (and you can do a\n> simple \"ls-tree $(cat .git/HEAD)\" and populate the case from the results),\n> but the low level of indirection in a git archive means that it's almost\n> totally prefetchable with near-perfect access patterns.\n\nWe can sort by the files before reading them in, but even if we order things \nperfectly, we're spreading the io out too much across the drive. It works \nright now because the git archive is relatively dense.  At a few hundred MB \nwhen we order things properly the drive head isn't moving that much.\n\nAt 3-6 GB this hurts more.  The data gets farther apart as things age, and \ndrive performance rots away.  I'll never convince you without numbers, which \nmeans I'll have to wait for the full load of old history and try it out ;)\n\n-chris\n"},{"id":"1252","messageId":"m3vf6frvxu.fsf@defiant.localdomain","threadId":"202","inReplyTo":"Pine.LNX.4.58.0504211301240.2344@ppc970.osdl.org","subject":"Re: [PATCH] multi item packed files","fromName":"Krzysztof Halasa","fromEmail":"khc@pm.waw.pl","sentAt":"2005-04-22T09:40:29Z","receivedAt":"2005-04-22T09:40:29Z","isPatch":true,"sender":{"key":"khc@pm.waw.pl","avatar":null},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> And dammit, if I'm the original author and likely biggest power-user, and \n> _I_ can't be bothered to use special filesystems, then who can? Nobody.\n\nIf someone is motivated enough, and if the task is quite trivial (as it\nseems to be) someone may try it. I can see nothing wrong with it as long\nas it doesn't affect other people.\n\n> This is why I absolutely do not believe in arguments like \"if your\n> filesystem doesn't do tail packing, you shouldn't use it\" or \"if your\n> don't have name hashing enabled in your filesystem it's broken\".\n\nOf course. But one may consider using a filesystem with, say, different\nsettings. Or a special filesystem for this task, such as CNFS used by\nnews servers (it seems news servers do quite the same what git does,\nexcept they also purge old contents, i.e., container files don't grow up).\n\n> I'm perfectly willing to optimize for the common case, but that's as far \n> as it goes. I do not want to make fundamental design decisions that depend \n> on the target filesystem having some particular feature.\n\nThe optimization would be (in) the underlying filesystem (i.e., the OS\nthing, or possibly a shared preloaded library?), not git itself.\n-- \nKrzysztof Halasa\n"},{"id":"1253","messageId":"m3r7h3rvjz.fsf@defiant.localdomain","threadId":"202","inReplyTo":"200504211622.48065.mason@suse.com","subject":"Re: [PATCH] multi item packed files","fromName":"Krzysztof Halasa","fromEmail":"khc@pm.waw.pl","sentAt":"2005-04-22T09:48:48Z","receivedAt":"2005-04-22T09:48:48Z","isPatch":true,"sender":{"key":"khc@pm.waw.pl","avatar":null},"body":"Chris Mason <mason@suse.com> writes:\n\n> Shrug, we shouldn't need help from the kernel for something like this.\n>  git as \n> a database hits worst case scenarios for almost every FS.\n\nNot sure.\n\n> 1) subdirectories with lots of files\n\nCorrect. But git doesn't search dirs so it's not that bad.\n\n> 2) wasted space for tiny files\n\n... depends on block size. With 2 KB:\n\ndefiant:~$ du -s /pub/mirror/linux-2.6.git\n88366   /pub/mirror/linux-2.6.git\ndefiant:~$ du -s --apparent-size /pub/mirror/linux-2.6.git\n63400   /pub/mirror/linux-2.6.git\n\nNot bad, is it?\n\n> 3) files that are likely to be accessed together spread across the whole disk\n\n... across the whole filesystem.\n\nWell, probably it isn't best to have git and .iso archives on the same\nfilesystem.\n-- \nKrzysztof Halasa\n"},{"id":"1290","messageId":"Pine.LNX.4.58.0504220916060.2344@ppc970.osdl.org","threadId":"202","inReplyTo":"200504212016.16729.mason@suse.com","subject":"Re: [PATCH] multi item packed files","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-22T16:22:14Z","receivedAt":"2005-04-22T16:22:14Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Apr 2005, Chris Mason wrote:\n> \n> We can sort by the files before reading them in, but even if we order things \n> perfectly, we're spreading the io out too much across the drive.\n\nNo we don't.\n\nIt's easy to just copy the repository in a way where this just isn't true:  \nyou sort the objects by how far they are from the current HEAD, and you\njust copy the repository in that order (\"furthest\" objects first - commits\nlast).\n\nThat's what I meant by defragmentation - you can actually do this on your \nown, even if your filesystem doesn't support it.\n\nDo it twice a year, and I pretty much guarantee that your performance will\nstay pretty constant over time. The one exception is fsck, which doesn't\nseek in \"history order\".\n\nAnd this works exactly because: \n - we don't do no steenking delta's, and don't have deep \"chains\" of data \n   to follow. The longest chain we ever have is just a few deep, and it's \n   trivial to just encourage the filesystem to have recent things together.\n - we have an append-only mentality.\n\nIn fact, it works for exactly the same reason that makes us able to drop \nold history if we want to. We essentially \"drop\" the history to another \npart of the disk.\n\n\t\tLinus\n"},{"id":"1305","messageId":"20050422181228.GA4656@macavity","threadId":"202","inReplyTo":"m3vf6frvxu.fsf@defiant.localdomain","subject":"Re: [PATCH] multi item packed files","fromName":"Martin Uecker","fromEmail":"muecker@gmx.de","sentAt":"2005-04-22T18:12:28Z","receivedAt":"2005-04-22T18:12:28Z","isPatch":true,"sender":{"key":"muecker@gmx.de","avatar":null},"body":"On Fri, Apr 22, 2005 at 11:40:29AM +0200, Krzysztof Halasa wrote:\n\n \n> > This is why I absolutely do not believe in arguments like \"if your\n> > filesystem doesn't do tail packing, you shouldn't use it\" or \"if your\n> > don't have name hashing enabled in your filesystem it's broken\".\n> \n> Of course. But one may consider using a filesystem with, say, different\n> settings. Or a special filesystem for this task, such as CNFS used by\n> news servers (it seems news servers do quite the same what git does,\n> except they also purge old contents, i.e., container files don't grow up).\n\nand nttp would give a nice transfer method for git objects...\n\nMartin\n\n-- \nOne night, when little Giana from Milano was fast asleep,\nshe had a strange dream.\n\n"},{"id":"1309","messageId":"200504221458.36300.mason@suse.com","threadId":"202","inReplyTo":"Pine.LNX.4.58.0504220916060.2344@ppc970.osdl.org","subject":"Re: [PATCH] multi item packed files","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-22T18:58:34Z","receivedAt":"2005-04-22T18:58:34Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Friday 22 April 2005 12:22, Linus Torvalds wrote:\n> On Thu, 21 Apr 2005, Chris Mason wrote:\n> > We can sort by the files before reading them in, but even if we order\n> > things perfectly, we're spreading the io out too much across the drive.\n>\n> No we don't.\n>\n> It's easy to just copy the repository in a way where this just isn't true:\n> you sort the objects by how far they are from the current HEAD, and you\n> just copy the repository in that order (\"furthest\" objects first - commits\n> last).\n>\n> That's what I meant by defragmentation - you can actually do this on your\n> own, even if your filesystem doesn't support it.\n\nThis certainly can help.  Based on some ideas from andrea I made a poor man's \ndefrag script last year that was similar.  It worked by copying files into a \nflat dir in the order you expected to read them in, deleting the original, \nthen hard linking them into their original name.\n\nCopying in order straight into a new git tree doesn't help much when the \nfilesystem is using the subdirectory as a hint to block allocation.  So \nyou'll probably have to copy them all into a flat directory and then hard \nlink back into the git tree (the flat dir can then be deleted of course).\n\nThe problem I see for git is that once you have enough data, it should degrade \nover and over again somewhat quickly.  My own guess is that you'll need to \nrun the script at least monthly.  If we're designing the thing now and say \n'wow, that's going to be really slow without help', it doesn't hurt to look \nat alternatives.\n\nI grabbed Ingo's tarball of 28,000 patches since 2.4.0 and applied them all \ninto git on ext3 (htree).  It only took ~2.5 hrs to apply.  I did use my  \nwrite-tree patch where you had to give write-tree a list of directories to \nsearch, but I don't think this helped much since the operation was mostly \ndisk write bound.\n\nAnyway, I ended up with a 2.6GB .git directory.  Then I:\n\nrm .git/index\numount ; mount again\ntime read-tree `tree-id` (24.45s)\ntime checkout-cache --prefix=../checkout/ -a -f (4m30s)\n\n--prefix is neat ;)\n\nThe tree that ended up in checkout was 239456k, giving us an effective io rate \nfor checkout-cache of 885k/s.  (this drive gets 24MB/s sequential reads).\n\nI'll have numbers for the packed files later on today.  No, I don't really \nexpect the numbers will convince you to implement some kind of packing ;)  \nBut it's still a good data point to have, and generating them here is just \npoking the box every 2 hours or so.\n\n-chris\n"},{"id":"1312","messageId":"Pine.LNX.4.58.0504221230020.2344@ppc970.osdl.org","threadId":"202","inReplyTo":"200504221458.36300.mason@suse.com","subject":"Re: [PATCH] multi item packed files","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-22T19:43:15Z","receivedAt":"2005-04-22T19:43:15Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 22 Apr 2005, Chris Mason wrote:\n> \n> The problem I see for git is that once you have enough data, it should degrade \n> over and over again somewhat quickly.\n\nI really doubt that.\n\nThere's a more or less constant amount of new data added all the time: the \nnumber of changes does _not_ grow with history. The number of changes \ngrows with the amount of changes going on in the tree, and while that \nisn't exactly constant, it definitely is not something that grows very \nfast. \n\nBtw, this is how git is able to be so fast in the first place. Git is fast \nbecause it knows that the \"size of the change\" is a lot smaller than the \n\"size of the repository\", so it fundamentally at all points tries to make \nsure that it only ever bothers with stuff that has changed.\n\nStuff that hasn't changed, it ignores very _very_ efficiently. \n\nThat's really the whole point of the index file: it's a way to quickly\nignore the stuff that hasn't changed - both for simple operations like\n\"show-diff\", but also for complex operations like \"merge these three\ntrees\".\n\nAnd it works exactly because the number of changes does _not_ grow at all \nlinearly with the history of the project. In fact, in most projects, the \nrate of change does _down_ when the project grows, because the projects \nmatures and generally gets more complicated and thus harder to change.\n\n(The kernel _really_ is pretty special. I am willing to bet that there are\nnot a lot of big projects that have been able to continue to take changes\nat the kind of pace that the kernel does. But we've had to work at it a\nlot, including obviously using SCM tools that are very much geared towards\nscaling. Why do you think the kernel puts more pressure on SCM's than\nother projects? It's exactly because we're trying to scale our change\nacceptance to bigger numbers).\n\nSo when you say \"once you have enough data, it will degrade quickly\" \nignores the fact that the rate of change isn't (the \"second derivative of \nthe size of the project in time\") really isn't that high. \n\n> I grabbed Ingo's tarball of 28,000 patches since 2.4.0 and applied them all \n> into git on ext3 (htree).  It only took ~2.5 hrs to apply.\n\nOk, I'd actually wish it took even less, but that's still a pretty\nimpressive average of three patches a second.\n\n> Anyway, I ended up with a 2.6GB .git directory.  Then I:\n> \n> rm .git/index\n> umount ; mount again\n> time read-tree `tree-id` (24.45s)\n> time checkout-cache --prefix=../checkout/ -a -f (4m30s)\n> \n> --prefix is neat ;)\n\nThat sounds pretty acceptable. Four minutes is a long time, but I assume\nthat the whole point of the exercise was to try to test worst-case\nbehaviour.  We can certainly make sure that real usage gets lower numbers\nthan that (in particular, my \"real usage\" ends up being 100% in the disk\ncache ;)\n\n\t\t\tLinus\n"},{"id":"1317","messageId":"200504221632.26278.mason@suse.com","threadId":"202","inReplyTo":"Pine.LNX.4.58.0504221230020.2344@ppc970.osdl.org","subject":"Re: [PATCH] multi item packed files","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-22T20:32:24Z","receivedAt":"2005-04-22T20:32:24Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Friday 22 April 2005 15:43, Linus Torvalds wrote:\n> On Fri, 22 Apr 2005, Chris Mason wrote:\n> > The problem I see for git is that once you have enough data, it should\n> > degrade over and over again somewhat quickly.\n>\n> I really doubt that.\n>\n> There's a more or less constant amount of new data added all the time: the\n> number of changes does _not_ grow with history. The number of changes\n> grows with the amount of changes going on in the tree, and while that\n> isn't exactly constant, it definitely is not something that grows very\n> fast.\n\n>From a filesystem point of view, it's not the number of changes that matters, \nit's the distance between them.  The amount of new data is constant, but the \nspeed of accessing the new data is affected by the bulk of old data on disk.\n\nEven with defragging you hopefully end up with a big chunk of the disk where \neverything is in order.  Then you add a new file and it goes either somewhere \nbehind that big chunk or in front of it.  The next new file might go \nsomewhere behind or in front etc etc.  Having a big chunk just means the new \nfiles are likely to be farther apart making reads of the new data very seeky.\n\n>\n> Btw, this is how git is able to be so fast in the first place. Git is fast\n> because it knows that the \"size of the change\" is a lot smaller than the\n> \"size of the repository\", so it fundamentally at all points tries to make\n> sure that it only ever bothers with stuff that has changed.\n>\n> Stuff that hasn't changed, it ignores very _very_ efficiently.\n>\ngit as a write engine is very fast, and we definitely write more then we read.\n\n> > I grabbed Ingo's tarball of 28,000 patches since 2.4.0 and applied them\n> > all into git on ext3 (htree).  It only took ~2.5 hrs to apply.\n>\n> Ok, I'd actually wish it took even less, but that's still a pretty\n> impressive average of three patches a second.\n\nYeah, and this was a relatively old machine with slowish drives.  One run to \napply into my packed tree is finished and only took 2 hours.  But, I had \n'tuned' it to make bigger packed files, and the end result is 2MB compressed \nobjects.    Great for compression rate, but my dumb format doesn't hold up \nwell for reading it back.\n\nIf I pack every 64k (uncompressed), the checkout-tree time goes down to 3m14s.  \nThat's a very big difference considering how stupid my code is  .git was only \n20% smaller with 64k chunks.  I should be able to do better...I'll do one \nmore run.\n\n>\n> > Anyway, I ended up with a 2.6GB .git directory.  Then I:\n> >\n> > rm .git/index\n> > umount ; mount again\n> > time read-tree `tree-id` (24.45s)\n> > time checkout-cache --prefix=../checkout/ -a -f (4m30s)\n> >\n> > --prefix is neat ;)\n>\n> That sounds pretty acceptable. Four minutes is a long time, but I assume\n> that the whole point of the exercise was to try to test worst-case\n> behaviour.  We can certainly make sure that real usage gets lower numbers\n> than that (in particular, my \"real usage\" ends up being 100% in the disk\n> cache ;)\n\nI had a tree with 28,000 patches.  If we pretend that one bk changeset will \nequal one git changeset, we'd have 64,000 patches (57k without empty \nmergesets), and it probably wouldn't fit into ram anymore ;)  Our bk cset \nrate was about 24k/year, so we'll have to trim very aggressively to have \nreasonable performance.\n\nFor a working tree that's fine, but we need some fast central place to pull \nthe working .git trees from, and we're really going to feel the random io \nthere.\n\n-chris\n"},{"id":"1359","messageId":"200504221955.15422.mason@suse.com","threadId":"202","inReplyTo":"200504221632.26278.mason@suse.com","subject":"Re: [PATCH] multi item packed files","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-22T23:55:14Z","receivedAt":"2005-04-22T23:55:14Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Friday 22 April 2005 16:32, Chris Mason wrote:\n\n> If I pack every 64k (uncompressed), the checkout-tree time goes down to\n> 3m14s. That's a very big difference considering how stupid my code is  .git\n> was only 20% smaller with 64k chunks.  I should be able to do better...I'll\n> do one more run.\n>\n\nThis run also packed tree files together (everything produced by write-tree \nwent into a packed file), but not the commits.  I estimate I could save about \nanother 168m by packing the tree files and commits into the same file with \nthe blobs, but this wouldn't make any of the times below faster.\n\ngit - original (28k commits)\t                packed\nFS size                2,675,408k\t\t\t1,723,820k\nread-tree            24.45s\t\t\t\t18.9s\ncheckout-cache   4m30s\t\t\t\t3m5s\npatch time\t   2h30m\t\t\t\t1h55m\n\nThe format for the packed files could be smarter, such that it didn't require \ndecompressing the whole packed file to read one item.  I would guess I could \nget another 20% checkout-cache performance out of it via more tuning, and \nprobably another 10% of space savings.\n\nOf course, none of this is likely to convince you ;)  If you decide later on \nit's worthwhile, I don't think it would be difficult to add then.\n\n-chris\n"},{"id":"1668","messageId":"200504251820.58985.mason@suse.com","threadId":"202","inReplyTo":"200504221955.15422.mason@suse.com","subject":"Re: [PATCH] multi item packed files","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-04-25T22:20:57Z","receivedAt":"2005-04-25T22:20:57Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Friday 22 April 2005 19:55, Chris Mason wrote:\n> On Friday 22 April 2005 16:32, Chris Mason wrote:\n> > If I pack every 64k (uncompressed), the checkout-tree time goes down to\n> > 3m14s. That's a very big difference considering how stupid my code is \n> > .git was only 20% smaller with 64k chunks.  I should be able to do\n> > better...I'll do one more run.\n>\n> This run also packed tree files together (everything produced by write-tree\n> went into a packed file), but not the commits.  I estimate I could save\n> about another 168m by packing the tree files and commits into the same file\n> with the blobs, but this wouldn't make any of the times below faster.\n>\n> git - original (28k commits)\t                packed\n> FS size                2,675,408k\t\t1,723,820k\n> read-tree            24.45s\t\t\t18.9s\n> checkout-cache   4m30s\t\t\t3m5s\n> patch time\t   2h30m\t\t\t\t1h55m\n>\n\nIt was a rainy weekend, so I took a break from lawn care and hacked in some \nsimple changes to the packed file format.  There's now a header listing the \nsha1 for each subfile and the offset where to find it in the main file.  Each \nsubfile is compressed individually so you don't have to decompress the whole \npacked file to find one.  commits were added into the packed files as well.\n\nSome results were about what I expected:\n\nFS size              -- 1,614,376k\nread-tree          -- 18s\ncheckout-cache -- 2m35s (cold cache)\ncheckout-cache -- 18s      (hot cache)\npatch time        -- 96m\n\nvanilla git needs 56s to checkout with a hot cache.  The hot cache numbers \nweren't done before because I hadn't expected my patch to help at all.  Even \nthough we both do things entirely from cache, vanilla git is much slower at \nwriting the checked out files back to the drive.  I've made no optimizations \nto that code, and the drive is only 30% full, so this seems to just be a bad \ninteraction with filesystem layout.\n\nI also expected vanilla git to perform pretty well when there were no commits \nin the tree.  My test was to put a copy of 2.6.11 under git.\n                                              vanilla                   packed\nupdate-cache (for all files)      2m1s                     48s\ncheckout-cache (cold)            1m23s                    28s\ncheckout-cache (hot)             12s                         15s\n\nThe difference in hot cache checkout time is userland cpu time.  It could be \navoided with smarter caching of the packed file header.  Right now I'm \ndecompressing it over and over again for each checkout.  Still, the \nperformance hit is pretty small because I try to limit the number of subfiles \nthat get packed together.\n\nMy current patch is attached for reference, it's against a git from late last \nweek.  I wouldn't suggest using this for anything other than benchmarking, \nand since I don't think I can get much better numbers easily, I'll stop \nplaying around with this for a while.\n\n-chris\n\n\ndiff -ur linus.back/cache.h linus/cache.h\n--- linus.back/cache.h\t2005-04-25 17:30:21.616654304 -0400\n+++ linus/cache.h\t2005-04-25 10:56:15.000000000 -0400\n@@ -64,6 +64,16 @@\n \tchar name[0];\n };\n \n+struct packed_item {\n+\t/* lenght of compressed data */\n+\tunsigned long len;\n+\tstruct packed_item *next;\n+\t/* sha1 of uncompressed data */\n+\tchar sha1[20];\n+\t/* compressed data */\n+\tchar *data;\n+};\n+\n #define CE_NAMEMASK  (0x0fff)\n #define CE_STAGEMASK (0x3000)\n #define CE_STAGESHIFT 12\n@@ -117,7 +127,7 @@\n \n /* Read and unpack a sha1 file into memory, write memory to a sha1 file */\n extern void * map_sha1_file(const unsigned char *sha1, unsigned long *size);\n-extern void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size);\n+extern void * unpack_sha1_file(const unsigned char *sha1, void *map, unsigned long mapsize, char *type, unsigned long *size);\n extern void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size);\n extern int write_sha1_file(char *buf, unsigned len, unsigned char *return_sha1);\n extern int check_sha1_signature(unsigned char *sha1, void *buf, unsigned long size, const char *type);\n@@ -125,6 +135,9 @@\n /* Convert to/from hex/sha1 representation */\n extern int get_sha1_hex(const char *hex, unsigned char *sha1);\n extern char *sha1_to_hex(const unsigned char *sha1);\t/* static buffer result! */\n+extern int pack_sha1_buffer(void *buf, unsigned long buf_len, \n+                            unsigned char *returnsha1, struct packed_item **);\n+int write_packed_buffer(struct packed_item *head);\n \n /* General helper functions */\n extern void usage(const char *err);\n@@ -137,4 +150,9 @@\n \t\t\t\t\t\tunsigned long *size,\n \t\t\t\t\t\tunsigned char *tree_sha1_ret);\n \n+extern int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1, struct packed_item **head);\n+\n+#define MAXPARENT 16\n+extern int commit_tree(char *tree_sha1_hex, unsigned char parent_sha1[MAXPARENT][20], int num_parents, struct packed_item **head);\n+extern void check_valid_sha1_file(unsigned char *sha1, const char *expect);\n #endif /* CACHE_H */\ndiff -ur linus.back/commit-tree.c linus/commit-tree.c\n--- linus.back/commit-tree.c\t2005-04-25 17:30:21.626652784 -0400\n+++ linus/commit-tree.c\t2005-04-25 10:58:15.000000000 -0400\n@@ -4,360 +4,32 @@\n  * Copyright (C) Linus Torvalds, 2005\n  */\n #include \"cache.h\"\n-\n-#include <pwd.h>\n-#include <time.h>\n-#include <string.h>\n-#include <ctype.h>\n-#include <time.h>\n-\n-#define BLOCKING (1ul << 14)\n-#define ORIG_OFFSET (40)\n-\n-/*\n- * Leave space at the beginning to insert the tag\n- * once we know how big things are.\n- *\n- * FIXME! Share the code with \"write-tree.c\"\n- */\n-static void init_buffer(char **bufp, unsigned int *sizep)\n-{\n-\tchar *buf = malloc(BLOCKING);\n-\tmemset(buf, 0, ORIG_OFFSET);\n-\t*sizep = ORIG_OFFSET;\n-\t*bufp = buf;\n-}\n-\n-static void add_buffer(char **bufp, unsigned int *sizep, const char *fmt, ...)\n-{\n-\tchar one_line[2048];\n-\tva_list args;\n-\tint len;\n-\tunsigned long alloc, size, newsize;\n-\tchar *buf;\n-\n-\tva_start(args, fmt);\n-\tlen = vsnprintf(one_line, sizeof(one_line), fmt, args);\n-\tva_end(args);\n-\tsize = *sizep;\n-\tnewsize = size + len;\n-\talloc = (size + 32767) & ~32767;\n-\tbuf = *bufp;\n-\tif (newsize > alloc) {\n-\t\talloc = (newsize + 32767) & ~32767;\n-\t\tbuf = realloc(buf, alloc);\n-\t\t*bufp = buf;\n-\t}\n-\t*sizep = newsize;\n-\tmemcpy(buf + size, one_line, len);\n-}\n-\n-static int prepend_integer(char *buffer, unsigned val, int i)\n-{\n-\tbuffer[--i] = '\\0';\n-\tdo {\n-\t\tbuffer[--i] = '0' + (val % 10);\n-\t\tval /= 10;\n-\t} while (val);\n-\treturn i;\n-}\n-\n-static void finish_buffer(char *tag, char **bufp, unsigned int *sizep)\n-{\n-\tint taglen;\n-\tint offset;\n-\tchar *buf = *bufp;\n-\tunsigned int size = *sizep;\n-\n-\toffset = prepend_integer(buf, size - ORIG_OFFSET, ORIG_OFFSET);\n-\ttaglen = strlen(tag);\n-\toffset -= taglen;\n-\tbuf += offset;\n-\tsize -= offset;\n-\tmemcpy(buf, tag, taglen);\n-\n-\t*bufp = buf;\n-\t*sizep = size;\n-}\n-\n-static void remove_special(char *p)\n-{\n-\tchar c;\n-\tchar *dst = p, *src = p;\n-\n-\tfor (;;) {\n-\t\tc = *src;\n-\t\tsrc++;\n-\t\tswitch(c) {\n-\t\tcase '\\n': case '<': case '>':\n-\t\t\tcontinue;\n-\t\t}\n-\t\t*dst++ = c;\n-\t\tif (!c)\n-\t\t\tbreak;\n-\t}\n-\n-\t/*\n-\t * Go back, and remove crud from the end: some people\n-\t * have commas etc in their gecos field\n-\t */\n-\tdst--;\n-\twhile (--dst >= p) {\n-\t\tunsigned char c = *dst;\n-\t\tswitch (c) {\n-\t\tcase ',': case ';': case '.':\n-\t\t\t*dst = 0;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tbreak;\n-\t}\n-}\n-\n-static const char *month_names[] = {\n-        \"Jan\", \"Feb\", \"Mar\", \"Apr\", \"May\", \"Jun\",\n-        \"Jul\", \"Aug\", \"Sep\", \"Oct\", \"Nov\", \"Dec\"\n-};\n-\n-static const char *weekday_names[] = {\n-        \"Sun\", \"Mon\", \"Tue\", \"Wed\", \"Thu\", \"Fri\", \"Sat\"\n-};\n-\n-\n-static char *skipfws(char *str)\n-{\n-\twhile (isspace(*str))\n-\t\tstr++;\n-\treturn str;\n-}\n-\n-\t\n-/* Gr. strptime is crap for this; it doesn't have a way to require RFC2822\n-   (i.e. English) day/month names, and it doesn't work correctly with %z. */\n-static void parse_rfc2822_date(char *date, char *result, int maxlen)\n-{\n-\tstruct tm tm;\n-\tchar *p;\n-\tint i, offset;\n-\ttime_t then;\n-\n-\tmemset(&tm, 0, sizeof(tm));\n-\n-\t/* Skip day-name */\n-\tp = skipfws(date);\n-\tif (!isdigit(*p)) {\n-\t\tfor (i=0; i<7; i++) {\n-\t\t\tif (!strncmp(p,weekday_names[i],3) && p[3] == ',') {\n-\t\t\t\tp = skipfws(p+4);\n-\t\t\t\tgoto day;\n-\t\t\t}\n-\t\t}\n-\t\treturn;\n-\t}\t\t\t\t\t\n-\n-\t/* day */\n- day:\n-\ttm.tm_mday = strtoul(p, &p, 10);\n-\n-\tif (tm.tm_mday < 1 || tm.tm_mday > 31)\n-\t\treturn;\n-\n-\tif (!isspace(*p))\n-\t\treturn;\n-\n-\tp = skipfws(p);\n-\n-\t/* month */\n-\n-\tfor (i=0; i<12; i++) {\n-\t\tif (!strncmp(p, month_names[i], 3) && isspace(p[3])) {\n-\t\t\ttm.tm_mon = i;\n-\t\t\tp = skipfws(p+strlen(month_names[i]));\n-\t\t\tgoto year;\n-\t\t}\n-\t}\n-\treturn; /* Error -- bad month */\n-\n-\t/* year */\n- year:\t\n-\ttm.tm_year = strtoul(p, &p, 10);\n-\n-\tif (!tm.tm_year && !isspace(*p))\n-\t\treturn;\n-\n-\tif (tm.tm_year > 1900)\n-\t\ttm.tm_year -= 1900;\n-\t\t\n-\tp=skipfws(p);\n-\n-\t/* hour */\n-\tif (!isdigit(*p))\n-\t\treturn;\n-\ttm.tm_hour = strtoul(p, &p, 10);\n-\t\n-\tif (!tm.tm_hour > 23)\n-\t\treturn;\n-\n-\tif (*p != ':')\n-\t\treturn; /* Error -- bad time */\n-\tp++;\n-\n-\t/* minute */\n-\tif (!isdigit(*p))\n-\t\treturn;\n-\ttm.tm_min = strtoul(p, &p, 10);\n-\t\n-\tif (!tm.tm_min > 59)\n-\t\treturn;\n-\n-\tif (isspace(*p))\n-\t\tgoto zone;\n-\n-\tif (*p != ':')\n-\t\treturn; /* Error -- bad time */\n-\tp++;\n-\n-\t/* second */\n-\tif (!isdigit(*p))\n-\t\treturn;\n-\ttm.tm_sec = strtoul(p, &p, 10);\n-\t\n-\tif (!tm.tm_sec > 59)\n-\t\treturn;\n-\n-\tif (!isspace(*p))\n-\t\treturn;\n-\n- zone:\n-\tp = skipfws(p);\n-\n-\tif (*p == '-')\n-\t\toffset = -60;\n-\telse if (*p == '+')\n-\t\toffset = 60;\n-\telse\n-\t       return;\n-\n-\tif (!isdigit(p[1]) || !isdigit(p[2]) || !isdigit(p[3]) || !isdigit(p[4]))\n-\t\treturn;\n-\n-\ti = strtoul(p+1, NULL, 10);\n-\toffset *= ((i % 100) + ((i / 100) * 60));\n-\n-\tif (*(skipfws(p + 5)))\n-\t\treturn;\n-\n-\tthen = mktime(&tm); /* mktime appears to ignore the GMT offset, stupidly */\n-\tif (then == -1)\n-\t\treturn;\n-\n-\tthen -= offset;\n-\n-\tsnprintf(result, maxlen, \"%lu %5.5s\", then, p);\n-}\n-\n-static void check_valid(unsigned char *sha1, const char *expect)\n-{\n-\tvoid *buf;\n-\tchar type[20];\n-\tunsigned long size;\n-\n-\tbuf = read_sha1_file(sha1, type, &size);\n-\tif (!buf || strcmp(type, expect))\n-\t\tdie(\"%s is not a valid '%s' object\", sha1_to_hex(sha1), expect);\n-\tfree(buf);\n-}\n-\n /*\n  * Having more than two parents is not strange at all, and this is\n  * how multi-way merges are represented.\n  */\n-#define MAXPARENT (16)\n \n static char *commit_tree_usage = \"commit-tree <sha1> [-p <sha1>]* < changelog\";\n \n int main(int argc, char **argv)\n {\n-\tint i, len;\n+\tint i;\n \tint parents = 0;\n \tunsigned char tree_sha1[20];\n \tunsigned char parent_sha1[MAXPARENT][20];\n-\tunsigned char commit_sha1[20];\n-\tchar *gecos, *realgecos, *commitgecos;\n-\tchar *email, *commitemail, realemail[1000];\n-\tchar date[20], realdate[20];\n-\tchar *audate;\n-\tchar comment[1000];\n-\tstruct passwd *pw;\n-\ttime_t now;\n-\tstruct tm *tm;\n-\tchar *buffer;\n-\tunsigned int size;\n \n \tif (argc < 2 || get_sha1_hex(argv[1], tree_sha1) < 0)\n \t\tusage(commit_tree_usage);\n \n-\tcheck_valid(tree_sha1, \"tree\");\n+\tcheck_valid_sha1_file(tree_sha1, \"tree\");\n \tfor (i = 2; i < argc; i += 2) {\n \t\tchar *a, *b;\n \t\ta = argv[i]; b = argv[i+1];\n \t\tif (!b || strcmp(a, \"-p\") || get_sha1_hex(b, parent_sha1[parents]))\n \t\t\tusage(commit_tree_usage);\n-\t\tcheck_valid(parent_sha1[parents], \"commit\");\n+\t\tcheck_valid_sha1_file(parent_sha1[parents], \"commit\");\n \t\tparents++;\n \t}\n-\tif (!parents)\n-\t\tfprintf(stderr, \"Committing initial tree %s\\n\", argv[1]);\n-\tpw = getpwuid(getuid());\n-\tif (!pw)\n-\t\tdie(\"You don't exist. Go away!\");\n-\trealgecos = pw->pw_gecos;\n-\tlen = strlen(pw->pw_name);\n-\tmemcpy(realemail, pw->pw_name, len);\n-\trealemail[len] = '@';\n-\tgethostname(realemail+len+1, sizeof(realemail)-len-1);\n-\tif (!strchr(realemail+len+1, '.')) {\n-\t\tstrcat(realemail, \".\");\n-\t\tgetdomainname(realemail+strlen(realemail), sizeof(realemail)-strlen(realemail)-1);\n-\t}\n-\ttime(&now);\n-\ttm = localtime(&now);\n-\n-\tstrftime(realdate, sizeof(realdate), \"%s %z\", tm);\n-\tstrcpy(date, realdate);\n-\n-\tcommitgecos = getenv(\"COMMIT_AUTHOR_NAME\") ? : realgecos;\n-\tcommitemail = getenv(\"COMMIT_AUTHOR_EMAIL\") ? : realemail;\n-\tgecos = getenv(\"AUTHOR_NAME\") ? : realgecos;\n-\temail = getenv(\"AUTHOR_EMAIL\") ? : realemail;\n-\taudate = getenv(\"AUTHOR_DATE\");\n-\tif (audate)\n-\t\tparse_rfc2822_date(audate, date, sizeof(date));\n-\n-\tremove_special(gecos); remove_special(realgecos); remove_special(commitgecos);\n-\tremove_special(email); remove_special(realemail); remove_special(commitemail);\n-\n-\tinit_buffer(&buffer, &size);\n-\tadd_buffer(&buffer, &size, \"tree %s\\n\", sha1_to_hex(tree_sha1));\n-\n-\t/*\n-\t * NOTE! This ordering means that the same exact tree merged with a\n-\t * different order of parents will be a _different_ changeset even\n-\t * if everything else stays the same.\n-\t */\n-\tfor (i = 0; i < parents; i++)\n-\t\tadd_buffer(&buffer, &size, \"parent %s\\n\", sha1_to_hex(parent_sha1[i]));\n-\n-\t/* Person/date information */\n-\tadd_buffer(&buffer, &size, \"author %s <%s> %s\\n\", gecos, email, date);\n-\tadd_buffer(&buffer, &size, \"committer %s <%s> %s\\n\\n\", commitgecos, commitemail, realdate);\n-\n-\t/* And add the comment */\n-\twhile (fgets(comment, sizeof(comment), stdin) != NULL)\n-\t\tadd_buffer(&buffer, &size, \"%s\", comment);\n-\n-\tfinish_buffer(\"commit \", &buffer, &size);\n-\n-\twrite_sha1_file(buffer, size, commit_sha1);\n-\tprintf(\"%s\\n\", sha1_to_hex(commit_sha1));\n+\tcommit_tree(tree_sha1, parent_sha1, parents, NULL);\n \treturn 0;\n }\ndiff -ur linus.back/fsck-cache.c linus/fsck-cache.c\n--- linus.back/fsck-cache.c\t2005-04-25 17:30:21.630652176 -0400\n+++ linus/fsck-cache.c\t2005-04-22 10:25:07.000000000 -0400\n@@ -85,7 +85,7 @@\n \t\tif (map) {\n \t\t\tchar type[100];\n \t\t\tunsigned long size;\n-\t\t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, &size);\n+\t\t\tvoid *buffer = unpack_sha1_file(sha1, map, mapsize, type, &size);\n \t\t\tif (!buffer)\n \t\t\t\treturn -1;\n \t\t\tif (check_sha1_signature(sha1, buffer, size, type) < 0)\ndiff -ur linus.back/Makefile linus/Makefile\n--- linus.back/Makefile\t2005-04-25 17:30:21.631652024 -0400\n+++ linus/Makefile\t2005-04-25 10:03:53.000000000 -0400\n@@ -23,7 +23,7 @@\n install: $(PROG)\n \tinstall $(PROG) $(HOME)/bin/\n \n-LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o\n+LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o lib-tree.o\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h\n \n@@ -71,6 +71,7 @@\n show-diff.o: $(LIB_H)\n show-files.o: $(LIB_H)\n tree.o: $(LIB_H)\n+lib-tree.o: $(LIB_H)\n update-cache.o: $(LIB_H)\n usage.o: $(LIB_H)\n unpack-file.o: $(LIB_H)\ndiff -ur linus.back/sha1_file.c linus/sha1_file.c\n--- linus.back/sha1_file.c\t2005-04-25 17:30:21.633651720 -0400\n+++ linus/sha1_file.c\t2005-04-25 17:15:53.050696400 -0400\n@@ -116,12 +116,14 @@\n \treturn map;\n }\n \n-void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size)\n+void * unpack_sha1_file(const unsigned char *sha1, void *map, \n+\t\t\tunsigned long mapsize, char *type, unsigned long *size)\n {\n \tint ret, bytes;\n \tz_stream stream;\n \tchar buffer[8192];\n \tchar *buf;\n+\tunsigned long offset;\n \n \t/* Get the data stream */\n \tmemset(&stream, 0, sizeof(stream));\n@@ -134,12 +136,12 @@\n \tret = inflate(&stream, 0);\n \tif (sscanf(buffer, \"%10s %lu\", type, size) != 2)\n \t\treturn NULL;\n-\n \tbytes = strlen(buffer) + 1;\n \tbuf = malloc(*size);\n-\tif (!buf)\n+\tif (!buf) {\n+\t\tperror(\"malloc\");\n \t\treturn NULL;\n-\n+\t}\n \tmemcpy(buf, buffer + bytes, stream.total_out - bytes);\n \tbytes = stream.total_out - bytes;\n \tif (bytes < *size && ret == Z_OK) {\n@@ -149,6 +151,56 @@\n \t\t\t/* nothing */;\n \t}\n \tinflateEnd(&stream);\n+\n+\t/* we've found a packed object */\n+\tif (strcmp(type, \"packed\") == 0) {\n+\t\tchar *p = buf;\n+\t\tunsigned long header_len = *size;\n+\t\toffset = stream.total_in;\n+\t\tif (!sha1)\n+\t\t\treturn NULL;\n+\t\twhile(p < buf + header_len) {\n+\t\t\tunsigned long item_len;\n+\t\t\tunsigned char sha1_hex[50];\n+\t\t\tunsigned char item_sha[20];\n+\t\t\tmemcpy(item_sha, p, 20);\n+\t\t\tsscanf(p + 20, \"%lu \", &item_len);\n+\t\t\tp += 20 + strlen(p + 20) + 1;\n+\t\t\tif (memcmp(item_sha, sha1, 20) == 0) {\n+\t\t\t\t/* Get the data stream */\n+\t\t\t\tfree(buf);\n+\t\t\t\tmemset(&stream, 0, sizeof(stream));\n+\t\t\t\tstream.next_in = map + offset;\n+\t\t\t\tstream.avail_in = mapsize - offset;\n+\t\t\t\tstream.next_out = buffer;\n+\t\t\t\tstream.avail_out = sizeof(buffer);\n+\n+\t\t\t\tinflateInit(&stream);\n+\t\t\t\tret = inflate(&stream, 0);\n+\t\t\t\tif (sscanf(buffer, \"%10s %lu\", type, size) != 2)\n+\t\t\t\t\treturn NULL;\n+\t\t\t\tbytes = strlen(buffer) + 1;\n+\t\t\t\tbuf = malloc(*size);\n+\t\t\t\tif (!buf) {\n+\t\t\t\t\tperror(\"malloc\");\n+\t\t\t\t\treturn NULL;\n+\t\t\t\t}\n+\t\t\t\tmemcpy(buf, buffer + bytes, \n+\t\t\t\t\tstream.total_out - bytes);\n+\t\t\t\tbytes = stream.total_out - bytes;\n+\t\t\t\tif (bytes < *size && ret == Z_OK) {\n+\t\t\t\t\tstream.next_out = buf + bytes;\n+\t\t\t\t\tstream.avail_out = *size - bytes;\n+\t\t\t\t\twhile (inflate(&stream, Z_FINISH) == Z_OK)\n+\t\t\t\t\t\t/* nothing */;\n+\t\t\t\t}\n+\t\t\t\tinflateEnd(&stream);\n+\t\t\t\treturn buf;\n+\t\t\t}\n+\t\t\toffset += item_len;\n+\t\t}\n+\t\treturn NULL;\n+\t}\n \treturn buf;\n }\n \n@@ -159,7 +211,7 @@\n \n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n-\t\tbuf = unpack_sha1_file(map, mapsize, type, size);\n+\t\tbuf = unpack_sha1_file(sha1, map, mapsize, type, size);\n \t\tmunmap(map, mapsize);\n \t\treturn buf;\n \t}\n@@ -305,3 +357,166 @@\n \tclose(fd);\n \treturn 0;\n }\n+\n+int pack_sha1_buffer(void *buf, unsigned long buf_len, \n+\t\t     unsigned char *returnsha1,\n+\t\t     struct packed_item **packed_item)\n+{\n+\tunsigned char sha1[20];\n+\tSHA_CTX c;\n+\tchar *filename;\n+\tstruct stat st;\n+\tchar *compressed;\n+\tz_stream stream;\n+\tunsigned long size;\n+\tstruct packed_item *item;\n+\n+\t*packed_item = NULL;\n+\n+\t/* Sha1.. */\n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, buf, buf_len);\n+\tSHA1_Final(sha1, &c);\n+\n+\tif (returnsha1)\n+\t\tmemcpy(returnsha1, sha1, 20);\n+\n+\tfilename = sha1_file_name(sha1);\n+\tif (stat(filename, &st) == 0)\n+\t\treturn 0;\n+\n+\t/* Set it up */\n+\tmemset(&stream, 0, sizeof(stream));\n+\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n+\tsize = deflateBound(&stream, buf_len);\n+\tcompressed = malloc(size);\n+\n+\t/*\n+\t * ASCII size + nul byte\n+\t */\t\n+\tstream.next_in = buf;\n+\tstream.avail_in = buf_len;\n+\tstream.next_out = compressed;\n+\tstream.avail_out = size;\n+\t/* Compress it */\n+\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n+\t\t/* nothing */;\n+\tdeflateEnd(&stream);\n+\tsize = stream.total_out;\n+\n+\titem = malloc(sizeof(struct packed_item));\n+\tif (!item) {\n+\t\tfree(compressed);\n+\t\treturn -1;\n+\t}\n+\tmemcpy(item->sha1, sha1, 20);\n+\titem->len = size;\n+\titem->next = NULL;\n+\titem->data = compressed;\n+\t*packed_item = item;\n+\treturn 0;\n+}\n+\n+static char *create_packed_header(struct packed_item *head, unsigned long *size)\n+{\n+\tchar *metadata = NULL;\n+\tint metadata_size = 0;\n+\t*size = 0;\n+\n+\twhile(head) {\n+\t\tchar *p;\n+\t\tmetadata = realloc(metadata, metadata_size + 220);\n+\t\tif (!metadata)\n+\t\t\treturn NULL;\n+\t\tp = metadata+metadata_size;\n+\t\tmemcpy(p, head->sha1, 20);\n+\t\tp += 20;\n+\t\tmetadata_size += 1 + sprintf(p, \"%lu \", head->len) + 20;\n+\t\thead = head->next;\n+\t}\n+\t*size = metadata_size;\n+\treturn metadata;\n+}\n+\n+int write_packed_buffer(struct packed_item *head)\n+{\n+\tunsigned char sha1[20];\n+\tSHA_CTX c;\n+\tchar *filename;\n+\tchar *metadata = malloc(200);\n+\tchar *header;\n+\tint metadata_size;\n+\tint fd;\n+\tint ret = 0;\n+\tunsigned long header_len;\n+\tstruct packed_item *item;\n+\tchar *compressed;\n+\tz_stream stream;\n+\tunsigned long size;\n+\tint nr = 0;\n+\n+\theader = create_packed_header(head, &header_len);\n+\tmetadata_size = 1+sprintf(metadata, \"packed %lu\", header_len);\n+\n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, metadata, metadata_size);\n+\tSHA1_Update(&c, header, header_len);\n+\titem = head;\n+\twhile(item) {\n+\t\tSHA1_Update(&c, item->data, item->len);\n+\t\titem = item->next;\n+\t\tnr++;\n+\t}\n+\tSHA1_Final(sha1, &c);\n+\n+\tfilename = strdup(sha1_file_name(sha1));\n+\tfd = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);\n+\tif (fd < 0) {\n+\t\t/* add collision check! */\n+\t\tif (errno != EEXIST) {\n+\t\t\tret = -errno;\n+\t\t}\n+\t\tgoto out;\n+\t}\n+       /* compress just the header info */\n+        memset(&stream, 0, sizeof(stream));\n+        deflateInit(&stream, Z_BEST_COMPRESSION);\n+        size = deflateBound(&stream, header_len + metadata_size);\n+        compressed = malloc(size);\n+\n+        stream.next_in = metadata;\n+        stream.avail_in = metadata_size;\n+        stream.next_out = compressed;\n+        stream.avail_out = size;\n+        while (deflate(&stream, 0) == Z_OK)\n+                /* nothing */;\n+        stream.next_in = header;\n+        stream.avail_in = header_len;\n+        while (deflate(&stream, Z_FINISH) == Z_OK)\n+                /* nothing */;\n+        deflateEnd(&stream);\n+        size = stream.total_out;\n+\n+\twrite(fd, compressed, size);\n+\tfree(compressed);\n+\n+\titem = head;\n+\twhile(item) {\n+\t\tchar *item_file;\n+\t\tstruct packed_item *next = item->next;\n+\t\twrite(fd, item->data, item->len);\n+\t\titem_file = sha1_file_name(item->sha1);\n+\t\tif (link(filename, item_file) && errno != EEXIST) {\n+\t\t\tret = -errno;\n+\t\t\tbreak;\n+\t\t}\n+\t\tfree(item->data);\n+\t\tfree(item);\n+\t\titem = next;\n+\t}\n+out:\n+\tfree(header);\n+\tfree(metadata);\n+\tfree(filename);\n+\treturn ret;\n+}\ndiff -ur linus.back/update-cache.c linus/update-cache.c\n--- linus.back/update-cache.c\t2005-04-25 17:30:21.635651416 -0400\n+++ linus/update-cache.c\t2005-04-25 14:24:14.000000000 -0400\n@@ -12,57 +12,48 @@\n  * like \"update-cache *\" and suddenly having all the object\n  * files be revision controlled.\n  */\n-static int allow_add = 0, allow_remove = 0;\n+static int allow_add = 0, allow_remove = 0, commit = 0;\n \n-static int index_fd(unsigned char *sha1, int fd, struct stat *st)\n+static int index_fd(unsigned char *sha1, int fd, struct stat *st, struct packed_item **head, struct packed_item **tail, unsigned long *packed_size)\n {\n-\tz_stream stream;\n \tunsigned long size = st->st_size;\n-\tint max_out_bytes = size + 200;\n-\tvoid *out = malloc(max_out_bytes);\n \tvoid *metadata = malloc(200);\n \tint metadata_size;\n \tvoid *in;\n-\tSHA_CTX c;\n+\tchar *copy;\n+\tint ret;\n+\tstruct packed_item *new_item;\n \n \tin = \"\";\n \tif (size)\n \t\tin = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n \tclose(fd);\n-\tif (!out || (int)(long)in == -1)\n+\tif (!metadata || (int)(long)in == -1)\n \t\treturn -1;\n-\n \tmetadata_size = 1+sprintf(metadata, \"blob %lu\", size);\n-\n-\tSHA1_Init(&c);\n-\tSHA1_Update(&c, metadata, metadata_size);\n-\tSHA1_Update(&c, in, size);\n-\tSHA1_Final(sha1, &c);\n-\n-\tmemset(&stream, 0, sizeof(stream));\n-\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n-\n-\t/*\n-\t * ASCII size + nul byte\n-\t */\t\n-\tstream.next_in = metadata;\n-\tstream.avail_in = metadata_size;\n-\tstream.next_out = out;\n-\tstream.avail_out = max_out_bytes;\n-\twhile (deflate(&stream, 0) == Z_OK)\n-\t\t/* nothing */;\n-\n-\t/*\n-\t * File content\n-\t */\n-\tstream.next_in = in;\n-\tstream.avail_in = size;\n-\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n-\t\t/*nothing */;\n-\n-\tdeflateEnd(&stream);\n-\t\n-\treturn write_sha1_buffer(sha1, out, stream.total_out);\n+\tcopy = malloc(metadata_size + size);\n+\tif (!copy)\n+\t\treturn -1;\n+\tmemcpy(copy, metadata, metadata_size);\n+\tmemcpy(copy + metadata_size, in, size);\n+\tret = pack_sha1_buffer(copy, metadata_size + size, sha1, &new_item);\n+\tif (new_item) {\n+\t\tif (*tail)\n+\t\t\t(*tail)->next = new_item;\n+\t\t*tail = new_item;\n+\t\tif (!*head)\n+\t\t\t*head = new_item;\n+\t\t*packed_size += new_item->len;\n+\t\tif (*packed_size > (512 * 1024)) {\n+\t\t\twrite_packed_buffer(*head);\n+\t\t\t*head = NULL;\n+\t\t\t*tail = NULL;\n+\t\t\t*packed_size = 0;\n+\t\t}\n+\t}\n+\tmunmap(in, size);\n+\tfree(copy);\n+\treturn ret;\n }\n \n /*\n@@ -85,7 +76,7 @@\n \tce->ce_size = htonl(st->st_size);\n }\n \n-static int add_file_to_cache(char *path)\n+static int add_file_to_cache(char *path, struct packed_item **packed_head, struct packed_item **packed_tail, unsigned long *packed_size)\n {\n \tint size, namelen;\n \tstruct cache_entry *ce;\n@@ -113,7 +104,8 @@\n \tce->ce_mode = create_ce_mode(st.st_mode);\n \tce->ce_flags = htons(namelen);\n \n-\tif (index_fd(ce->sha1, fd, &st) < 0)\n+\tif (index_fd(ce->sha1, fd, &st, packed_head, \n+\t\t     packed_tail, packed_size) < 0)\n \t\treturn -1;\n \n \treturn add_cache_entry(ce, allow_add);\n@@ -282,12 +274,30 @@\n \t\tunlink(lockfile_name);\n }\n \n+static int path_comp(const void *p1, const void *p2)\n+{\n+\tconst char *s1 = *(char **)p1;\n+\tconst char *s2 = *(char **)p2;\n+\tint len1 = strlen(s1);\n+\tint len2 = strlen(s2);\n+\tint ret;\n+\tret = cache_name_compare(s1, len1, s2, len2);\n+\treturn ret;\n+}\n+\n int main(int argc, char **argv)\n {\n \tint i, newfd, entries;\n \tint allow_options = 1;\n \tstatic char lockfile[MAXPATHLEN+1];\n \tconst char *indexfile = get_index_file();\n+\tstruct packed_item *packed_head = NULL;\n+\tstruct packed_item *packed_tail = NULL;\n+\tunsigned long packed_size = 0;\n+\tchar **paths = malloc(argc * sizeof(char *));\n+\tint num_paths = 0;\n+\tunsigned char parent_sha1[20];\n+\tint parents = 0;\n \n \tsnprintf(lockfile, sizeof(lockfile), \"%s.lock\", indexfile);\n \n@@ -318,6 +328,17 @@\n \t\t\t\tallow_remove = 1;\n \t\t\t\tcontinue;\n \t\t\t}\n+\t\t\tif (!strcmp(path, \"--commit\")) {\n+\t\t\t\tcommit = 1;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (!strcmp(path, \"--parent\")) {\n+\t\t\t\tif (i+1 >= argc || get_sha1_hex(argv[i+1], parent_sha1))\n+\t\t\t\t\tdie(\"update-cache: --parent sha1\");\n+\t\t\t\tparents = 1;\n+\t\t\t\ti+=1;\n+\t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tif (!strcmp(path, \"--refresh\")) {\n \t\t\t\trefresh_cache();\n \t\t\t\tcontinue;\n@@ -334,8 +355,27 @@\n \t\t\tfprintf(stderr, \"Ignoring path %s\\n\", argv[i]);\n \t\t\tcontinue;\n \t\t}\n-\t\tif (add_file_to_cache(path))\n-\t\t\tdie(\"Unable to add %s to database\", path);\n+\t\tpaths[num_paths++] = path;\n+\n+\t}\n+\t// qsort(paths, num_paths, sizeof(char *), path_comp);\n+\tfor(i = 0 ; i < num_paths ; i++) {\n+\t\tif (add_file_to_cache(paths[i], &packed_head, &packed_tail, &packed_size))\n+\t\t\tdie(\"Unable to add %s to database\", paths[i]);\n+\n+\t}\n+\tif (commit) {\n+\t\tchar tree_sha1[20];\n+\t\tif (write_tree(active_cache, active_nr, \"\", 0, tree_sha1, &packed_head) != active_nr)\n+\t\t\tdie(\"write-tree failed\");\n+fprintf(stderr, \"write_tree gave us %s\\n\", sha1_to_hex(tree_sha1));\n+\n+\t\tif (commit_tree(tree_sha1, &parent_sha1, parents, &packed_head))\n+\t\t\tdie(\"commit-tree failed\");\n+\t}\n+\tif (packed_head) {\n+\t\tif (write_packed_buffer(packed_head))\n+\t\t\tdie(\"write packed buffer failed\");\n \t}\n \tif (write_cache(newfd, active_cache, active_nr) || rename(lockfile, indexfile))\n \t\tdie(\"Unable to write new cachefile\");\ndiff -ur linus.back/write-tree.c linus/write-tree.c\n--- linus.back/write-tree.c\t2005-04-25 17:30:21.635651416 -0400\n+++ linus/write-tree.c\t2005-04-25 10:01:30.000000000 -0400\n@@ -3,106 +3,15 @@\n  *\n  * Copyright (C) Linus Torvalds, 2005\n  */\n-#include \"cache.h\"\n-\n-static int check_valid_sha1(unsigned char *sha1)\n-{\n-\tchar *filename = sha1_file_name(sha1);\n-\tint ret;\n-\n-\t/* If we were anal, we'd check that the sha1 of the contents actually matches */\n-\tret = access(filename, R_OK);\n-\tif (ret)\n-\t\tperror(filename);\n-\treturn ret;\n-}\n-\n-static int prepend_integer(char *buffer, unsigned val, int i)\n-{\n-\tbuffer[--i] = '\\0';\n-\tdo {\n-\t\tbuffer[--i] = '0' + (val % 10);\n-\t\tval /= 10;\n-\t} while (val);\n-\treturn i;\n-}\n-\n-#define ORIG_OFFSET (40)\t/* Enough space to add the header of \"tree <size>\\0\" */\n-\n-static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)\n-{\n-\tunsigned char subdir_sha1[20];\n-\tunsigned long size, offset;\n-\tchar *buffer;\n-\tint i, nr;\n-\n-\t/* Guess at some random initial size */\n-\tsize = 8192;\n-\tbuffer = malloc(size);\n-\toffset = ORIG_OFFSET;\n-\n-\tnr = 0;\n-\tdo {\n-\t\tstruct cache_entry *ce = cachep[nr];\n-\t\tconst char *pathname = ce->name, *filename, *dirname;\n-\t\tint pathlen = ce_namelen(ce), entrylen;\n-\t\tunsigned char *sha1;\n-\t\tunsigned int mode;\n-\n-\t\t/* Did we hit the end of the directory? Return how many we wrote */\n-\t\tif (baselen >= pathlen || memcmp(base, pathname, baselen))\n-\t\t\tbreak;\n \n-\t\tsha1 = ce->sha1;\n-\t\tmode = ntohl(ce->ce_mode);\n-\n-\t\t/* Do we have _further_ subdirectories? */\n-\t\tfilename = pathname + baselen;\n-\t\tdirname = strchr(filename, '/');\n-\t\tif (dirname) {\n-\t\t\tint subdir_written;\n-\n-\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);\n-\t\t\tnr += subdir_written;\n-\n-\t\t\t/* Now we need to write out the directory entry into this tree.. */\n-\t\t\tmode = S_IFDIR;\n-\t\t\tpathlen = dirname - pathname;\n-\n-\t\t\t/* ..but the directory entry doesn't count towards the total count */\n-\t\t\tnr--;\n-\t\t\tsha1 = subdir_sha1;\n-\t\t}\n-\n-\t\tif (check_valid_sha1(sha1) < 0)\n-\t\t\texit(1);\n-\n-\t\tentrylen = pathlen - baselen;\n-\t\tif (offset + entrylen + 100 > size) {\n-\t\t\tsize = alloc_nr(offset + entrylen + 100);\n-\t\t\tbuffer = realloc(buffer, size);\n-\t\t}\n-\t\toffset += sprintf(buffer + offset, \"%o %.*s\", mode, entrylen, filename);\n-\t\tbuffer[offset++] = 0;\n-\t\tmemcpy(buffer + offset, sha1, 20);\n-\t\toffset += 20;\n-\t\tnr++;\n-\t} while (nr < maxentries);\n-\n-\ti = prepend_integer(buffer, offset - ORIG_OFFSET, ORIG_OFFSET);\n-\ti -= 5;\n-\tmemcpy(buffer+i, \"tree \", 5);\n-\n-\twrite_sha1_file(buffer + i, offset - i, returnsha1);\n-\tfree(buffer);\n-\treturn nr;\n-}\n+#include \"cache.h\"\n \n int main(int argc, char **argv)\n {\n \tint i, unmerged;\n \tint entries = read_cache();\n \tunsigned char sha1[20];\n+\tstruct packed_item *head = NULL;\n \n \tif (entries <= 0)\n \t\tdie(\"write-tree: no cache contents to write\");\n@@ -123,8 +32,12 @@\n \t\tdie(\"write-tree: not able to write tree\");\n \n \t/* Ok, write it out */\n-\tif (write_tree(active_cache, entries, \"\", 0, sha1) != entries)\n+\tif (write_tree(active_cache, entries, \"\", 0, sha1, &head) != entries)\n \t\tdie(\"write-tree: internal error\");\n+\tif (head) {\n+\t\tif (write_packed_buffer(head))\n+\t\t\tdie(\"write_packed_buffer failed\");\n+\t}\n \tprintf(\"%s\\n\", sha1_to_hex(sha1));\n \treturn 0;\n }\n"}]}