{"thread":{"id":"21122","subject":"[PATCH 1/6] Open the pack file and keep a map on it.","startedAt":"2009-10-03T18:09:55Z","lastAt":"2009-10-05T15:27:55Z","messageCount":8,"participants":["Hervé Cauwelier","Shawn O. Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"124177","messageId":"1254593401-18801-1-git-send-email-herve@itaapy.com","threadId":"21122","inReplyTo":null,"subject":"Patches for libgit2","fromName":"Hervé Cauwelier","fromEmail":"herve@itaapy.com","sentAt":"2009-10-03T18:09:55Z","receivedAt":"2009-10-03T18:09:55Z","isPatch":false,"sender":{"key":"herve@itaapy.com","avatar":null},"body":"\nHi,\n\nPlease find patches for libgit2. They allowed me to read the history of a\nrepository with only 75 patches but hacked by an history shortening.\n\nCommits were both in a 5 GB pack file and loose objects. So I had to add\nsupport for pack files. Hopefully, reading idx files was already there so I\nfollowed the same model.\n\nPatches can also be cloned at \"git://git.hforge.org/libgit2.git\".\n\nThere is a Python wrapper on the next side, forking from the existing\nlibgit2-python [1]. They bring the same functionnalities but the patches are\nnot slick yet.\n\n[1] http://code.istique.net/gitweb/?p=libgit2-python.git;a=summary\n\nOne thing that would miss is unit tests, but I lack experience on testing C\ncode, and it would require having a small but exhaustive pack file with\ndifferent types of object, including ofs and ref deltas. Help on this part is\nwelcome.\n\nNext step would be decoding raw objects to commits, trees, blobs and tags.\nThere is already the start of a commit structure. I'll be starting from that.\n\nRegards,\n\nHervé\n"},{"id":"124175","messageId":"1254593401-18801-2-git-send-email-herve@itaapy.com","threadId":"21122","inReplyTo":"1254593401-18801-1-git-send-email-herve@itaapy.com","subject":"[PATCH 1/6] Open the pack file and keep a map on it.","fromName":"Hervé Cauwelier","fromEmail":"herve@itaapy.com","sentAt":"2009-10-03T18:09:56Z","receivedAt":"2009-10-03T18:09:56Z","isPatch":true,"sender":{"key":"herve@itaapy.com","avatar":null},"body":"On the same model than the idx file.\n\nSigned-off-by: Hervé Cauwelier \n---\n src/odb.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n src/odb.h | 5 ++-\n 2 files changed, 68 insertions(+), 4 deletions(-)\n\ndiff --git a/src/odb.c b/src/odb.c\nindex 6d646a4..a562a19 100644\n--- a/src/odb.c\n+++ b/src/odb.c\n@@ -64,6 +64,10 @@ struct git_pack {\n \n \t/** Name of the pack file(s), without extension (\"pack-abc\"). */\n \tchar pack_name[GIT_PACK_NAME_MAX];\n+\n+\t/** The .pack file, mapped into memory. */\n+\tgit_file pack_fd;\n+\tgit_map pack_map;\n };\n typedef struct git_pack git_pack;\n \n@@ -782,7 +786,7 @@ static int pack_openidx(git_pack *p)\n \t\t\tgoto invalid_fail;\n \t\tdata = p->idx_map.data;\n \n-\t\tif (decode32(&data[0]) == PACK_TOC) {\n+\t\tif (decode32(&data[0]) == IDX_TOC) {\n \t\t\tswitch (decode32(&data[1])) {\n \t\t\tcase 2:\n \t\t\t\tif (pack_openidx_v2(p))\n@@ -809,6 +813,59 @@ unlock_fail:\n \treturn GIT_ERROR;\n }\n \n+static int pack_openpack_map(git_pack *p)\n+{\n+\tchar pb[GIT_PATH_MAX];\n+\toff_t len;\n+\n+\tif (git__fmt(pb, sizeof(pb), \"%s/pack/%s.pack\",\n+\t\t\tp->db->objects_dir,\n+\t\t\tp->pack_name) < 0)\n+\t\treturn GIT_ERROR;\n+\n+\tif ((p->pack_fd = gitfo_open(pb, O_RDONLY)) < 0)\n+\t\treturn GIT_ERROR;\n+\n+\tif ((len = gitfo_size(p->pack_fd)) < 0\n+\t\t\t|| !git__is_sizet(len)\n+\t\t\t|| gitfo_map_ro(&p->pack_map, p->pack_fd, 0, (size_t)len)) {\n+\t\tgitfo_close(p->pack_fd);\n+\t\treturn GIT_ERROR;\n+\t}\n+\n+\treturn GIT_SUCCESS;\n+}\n+\n+static int pack_openpack(git_pack *p)\n+{\n+\tgitlck_lock(&p->lock);\n+\tif (p->invalid)\n+\t\tgoto unlock_fail;\n+\tif (p->pack_fd < 0) {\n+\t\tuint32_t *data;\n+\n+\t\tif (pack_openpack_map(p))\n+\t\t\tgoto invalid_fail;\n+\t\tdata = p->pack_map.data;\n+\n+\t\tif (decode32(&data[0]) != PACK_TOC)\n+\t\t\tgoto unmap_fail;\n+\t}\n+\tgitlck_unlock(&p->lock);\n+\treturn GIT_SUCCESS;\n+\n+unmap_fail:\n+\tgitfo_free_map(&p->pack_map);\n+\n+invalid_fail:\n+\tp->invalid = 1;\n+\tp->pack_fd = -1;\n+\n+unlock_fail:\n+\tgitlck_unlock(&p->lock);\n+\treturn GIT_ERROR;\n+}\n+\n static void pack_decidx(git_pack *p)\n {\n \tgitlck_lock(&p->lock);\n@@ -830,6 +887,11 @@ static void pack_dec(git_pack *p)\n \t\t\tgitfo_close(p->idx_fd);\n \t\t\tfree(p->im_fanout);\n \t\t}\n+\t\tif (p->pack_fd >= 0) {\n+\t\t\tgitfo_free_map(&p->pack_map);\n+\t\t\tgitfo_close(p->pack_fd);\n+\t\t\tp->pack_fd = -1;\n+\t\t}\n \n \t\tgitlck_free(&p->lock);\n \t\tfree(p);\n@@ -861,6 +923,7 @@ static git_pack *alloc_pack(const char *pack_name)\n \tgitlck_init(&p->lock);\n \tstrcpy(p->pack_name, pack_name);\n \tp->refcnt = 1;\n+\tp->pack_fd = -1;\n \treturn p;\n }\n \n@@ -895,7 +958,7 @@ static int scan_one_pack(void *state, char *name)\n \n \tr->next = *ret;\n \t*ret = r;\n-\treturn 0;\n+\treturn GIT_SUCCESS;\n }\n \n static git_packlist* scan_packs(git_odb *db)\ndiff --git a/src/odb.h b/src/odb.h\nindex 2f205b2..0311d78 100644\n--- a/src/odb.h\n+++ b/src/odb.h\n@@ -11,9 +11,10 @@\n * uint32_t *fanout = ... the file data at offset 0 ...\n * ntohl(fanout[0]) < ntohl(fanout[1])\n *\n- * The value chosen here for PACK_TOC is such that the above\n+ * The value chosen here for IDX_TOC is such that the above\n * cannot be true for an idx v1 file.\n */\n-#define PACK_TOC 0xff744f63 /* -1tOc */\n+#define IDX_TOC 0xff744f63 /* -1tOc */\n+#define PACK_TOC 0x5041434b /* PACK */\n \n #endif\n-- \n1.6.4.4\n"},{"id":"124178","messageId":"1254593401-18801-3-git-send-email-herve@itaapy.com","threadId":"21122","inReplyTo":"1254593401-18801-2-git-send-email-herve@itaapy.com","subject":"[PATCH 2/6] Read the base offset or name of delta objects","fromName":"Hervé Cauwelier","fromEmail":"herve@itaapy.com","sentAt":"2009-10-03T18:09:57Z","receivedAt":"2009-10-03T18:09:57Z","isPatch":true,"sender":{"key":"herve@itaapy.com","avatar":null},"body":"Signed-off-by: Hervé Cauwelier \n---\n src/cc-compat.h | 3 +++\n src/odb.c | 28 ++++++++++++++++++++++++++--\n 2 files changed, 29 insertions(+), 2 deletions(-)\n\ndiff --git a/src/cc-compat.h b/src/cc-compat.h\nindex 8997caa..8dd6774 100644\n--- a/src/cc-compat.h\n+++ b/src/cc-compat.h\n@@ -30,6 +30,9 @@\n # define GIT_TYPEOF(x)\n #endif\n \n+#define bitsizeof(x) (CHAR_BIT * sizeof(x))\n+#define MSB(x, bits) ((x) & GIT_TYPEOF(x)(~0ULL << (bitsizeof(x) - (bits))))\n+\n /*\n * Does our compiler/platform support the C99 and\n * header files. (C99 requires that \ndiff --git a/src/odb.c b/src/odb.c\nindex a562a19..3cfc932 100644\n--- a/src/odb.c\n+++ b/src/odb.c\n@@ -97,8 +97,10 @@ struct git_odb {\n };\n \n typedef struct { /* object header data */\n-\tgit_otype type; /* object type */\n-\tsize_t size; /* object size */\n+\tgit_otype type; /* object type */\n+\tsize_t size; /* object size */\n+\toff_t base_offset; /* delta base offset (GIT_OBJ_OFS_DELTA) */\n+\tgit_oid base_name; /* delta base name (GIT_OBJ_REF_DELTA) */\n } obj_hdr;\n \n static struct {\n@@ -238,6 +240,7 @@ static size_t get_binary_object_header(obj_hdr *hdr, gitfo_buf *obj)\n \tunsigned char c;\n \tunsigned char *data = obj->data;\n \tsize_t shift, size, used = 0;\n+\toff_t base_offset;\n \n \tif (obj->len == 0)\n \t\treturn 0;\n@@ -258,6 +261,27 @@ static size_t get_binary_object_header(obj_hdr *hdr, gitfo_buf *obj)\n \t}\n \thdr->size = size;\n \n+\thdr->base_offset = 0;\n+\thdr->base_name.id[0] = '\\0';\n+\n+\tif (hdr->type == GIT_OBJ_OFS_DELTA) {\n+\t\tc = data[used++];\n+\t\tbase_offset = c & 127;\n+\t\twhile (c & 128) {\n+\t\t\tbase_offset++;\n+\t\t\tif (!base_offset || MSB(base_offset, 7))\n+\t\t\t\treturn 0; /* overflow */\n+\t\t\tc = data[used++];\n+\t\t\tbase_offset = (base_offset << 7) + (c & 127);\n+\t\t}\n+\t\tassert(base_offset > 0);\n+\t\thdr->base_offset = base_offset;\n+\t}\n+\telse if (hdr->type == GIT_OBJ_REF_DELTA) {\n+\t\tgit_oid_mkraw(&hdr->base_name, data + used);\n+\t\tused += 20;\n+\t}\n+\n \treturn used;\n }\n \n-- \n1.6.4.4\n"},{"id":"124181","messageId":"1254593401-18801-4-git-send-email-herve@itaapy.com","threadId":"21122","inReplyTo":"1254593401-18801-3-git-send-email-herve@itaapy.com","subject":"[PATCH 3/6] Allow zlib to read a pack buffer longer than the actual data","fromName":"Hervé Cauwelier","fromEmail":"herve@itaapy.com","sentAt":"2009-10-03T18:09:58Z","receivedAt":"2009-10-03T18:09:58Z","isPatch":true,"sender":{"key":"herve@itaapy.com","avatar":null},"body":"As we don't know where the compressed data end, only the size of the\nuncompressed data.\n\nSigned-off-by: Hervé Cauwelier \n---\n src/odb.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/src/odb.c b/src/odb.c\nindex 3cfc932..89ee1f2 100644\n--- a/src/odb.c\n+++ b/src/odb.c\n@@ -432,7 +432,7 @@ static int inflate_buffer(void *in, size_t inlen, void *out, size_t outlen)\n \n \tinflateEnd(&zs);\n \n-\tif ((status != Z_STREAM_END) || (zs.avail_in != 0))\n+\tif (status != Z_STREAM_END)\n \t\treturn GIT_ERROR;\n \n \tif (zs.total_out != outlen)\n-- \n1.6.4.4\n"},{"id":"124176","messageId":"1254593401-18801-5-git-send-email-herve@itaapy.com","threadId":"21122","inReplyTo":"1254593401-18801-4-git-send-email-herve@itaapy.com","subject":"[PATCH 4/6] Inflate an object from a pack file","fromName":"Hervé Cauwelier","fromEmail":"herve@itaapy.com","sentAt":"2009-10-03T18:09:59Z","receivedAt":"2009-10-03T18:09:59Z","isPatch":true,"sender":{"key":"herve@itaapy.com","avatar":null},"body":"Support delta objects too.\n\nSigned-off-by: Hervé Cauwelier \n---\n src/odb.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 68 insertions(+), 1 deletions(-)\n\ndiff --git a/src/odb.c b/src/odb.c\nindex 89ee1f2..bc26cf7 100644\n--- a/src/odb.c\n+++ b/src/odb.c\n@@ -28,6 +28,7 @@\n #include \"git/zlib.h\"\n #include \"fileops.h\"\n #include \"hash.h\"\n+#include \"delta-apply.h\"\n #include \"odb.h\"\n \n #define GIT_PACK_NAME_MAX (5 + 40 + 1)\n@@ -232,7 +233,7 @@ static int is_zlib_compressed_data(unsigned char *data)\n \tunsigned int w;\n \n \tw = ((unsigned int)(data[0]) << 8) + data[1];\n-\treturn data[0] == 0x78 && !(w %31);\n+\treturn data[0] == 0x78 && !(w % 31);\n }\n \n static size_t get_binary_object_header(obj_hdr *hdr, gitfo_buf *obj)\n@@ -1192,6 +1193,72 @@ int git_odb__read_loose(git_obj *out, git_odb *db, const git_oid *id)\n \treturn GIT_SUCCESS;\n }\n \n+static int inflate_pack_obj(git_obj *out, git_pack *p, off_t offset)\n+{\n+\tobj_hdr hdr;\n+\tgitfo_buf buf;\n+\tsize_t used;\n+\tvoid *data;\n+\tgit_obj base;\n+\n+\t/* Cast the map to a gitfo_buf */\n+\tbuf.data = (unsigned char *)p->pack_map.data + offset;\n+\tbuf.len = p->pack_map.len - offset;\n+\n+\t/*\n+\t * Read the object header, which is an (uncompressed)\n+\t * binary encoding of the object type and size.\n+\t */\n+\tif (!(used = get_binary_object_header(&hdr, &buf)))\n+\t\treturn GIT_ERROR;\n+\n+\t/*\n+\t * Read the object data as a zlib compressed data\n+\t */\n+\tbuf.data += used;\n+\tbuf.len -= used;\n+\tassert(is_zlib_compressed_data(buf.data));\n+\n+\tif (!(data = git__malloc(hdr.size + 1)))\n+\t\treturn GIT_ERROR;\n+\tif (inflate_buffer(buf.data, buf.len, data, hdr.size))\n+\t\tgoto inflate_fail;\n+\n+\tswitch (hdr.type) {\n+\t\tcase GIT_OBJ_COMMIT:\n+\t\tcase GIT_OBJ_TREE:\n+\t\tcase GIT_OBJ_BLOB:\n+\t\tcase GIT_OBJ_TAG:\n+\t\t\tout->data = data;\n+\t\t\tout->len = hdr.size;\n+\t\t\tout->type = hdr.type;\n+\t\t\treturn GIT_SUCCESS;\n+\t\tcase GIT_OBJ_OFS_DELTA:\n+\t\t\toffset -= hdr.base_offset;\n+\t\t\tif (inflate_pack_obj(&base, p, offset))\n+\t\t\t\tgoto inflate_fail;\n+\t\t\tif (git__delta_apply(out, base.data, base.len, data, hdr.size))\n+\t\t\t\tgoto inflate_fail;\n+\t\t\tout->type = base.type;\n+\t\t\treturn GIT_SUCCESS;\n+\t\tcase GIT_OBJ_REF_DELTA:\n+\t\t\tif (p->idx_search(&offset, p, &hdr.base_name))\n+\t\t\t\tgoto inflate_fail;\n+\t\t\tif (inflate_pack_obj(&base, p, offset))\n+\t\t\t\tgoto inflate_fail;\n+\t\t\tif (git__delta_apply(out, base.data, base.len, data, hdr.size))\n+\t\t\t\tgoto inflate_fail;\n+\t\t\tout->type = base.type;\n+\t\t\treturn GIT_SUCCESS;\n+\t\tdefault:\n+\t\t\tgoto inflate_fail;\n+\t}\n+\n+inflate_fail:\n+\tfree(data);\n+\treturn GIT_ERROR;\n+}\n+\n static int read_packed(git_obj *out, git_pack *p, const git_oid *id)\n {\n \toff_t pos;\n-- \n1.6.4.4\n"},{"id":"124180","messageId":"1254593401-18801-6-git-send-email-herve@itaapy.com","threadId":"21122","inReplyTo":"1254593401-18801-5-git-send-email-herve@itaapy.com","subject":"[PATCH 5/6] This assertion is valid for both loose and packed objects","fromName":"Hervé Cauwelier","fromEmail":"herve@itaapy.com","sentAt":"2009-10-03T18:10:00Z","receivedAt":"2009-10-03T18:10:00Z","isPatch":true,"sender":{"key":"herve@itaapy.com","avatar":null},"body":"Signed-off-by: Hervé Cauwelier \n---\n src/odb.c | 9 +++------\n 1 files changed, 3 insertions(+), 6 deletions(-)\n\ndiff --git a/src/odb.c b/src/odb.c\nindex bc26cf7..dd3c142 100644\n--- a/src/odb.c\n+++ b/src/odb.c\n@@ -1149,11 +1149,10 @@ void git_odb_close(git_odb *db)\n \tfree(db);\n }\n \n-int git_odb_read(\n-\tgit_obj *out,\n-\tgit_odb *db,\n-\tconst git_oid *id)\n+int git_odb_read(git_obj *out, git_odb *db, const git_oid *id)\n {\n+\tassert(out && db && id);\n+\n attempt:\n \tif (!git_odb__read_packed(out, db, id))\n \t\treturn GIT_SUCCESS;\n@@ -1171,8 +1170,6 @@ int git_odb__read_loose(git_obj *out, git_odb *db, const git_oid *id)\n \tchar file[GIT_PATH_MAX];\n \tgitfo_buf obj = GITFO_BUF_INIT;\n \n-\tassert(out && db && id);\n-\n \tout->data = NULL;\n \tout->len = 0;\n \tout->type = GIT_OBJ_BAD;\n-- \n1.6.4.4\n"},{"id":"124179","messageId":"1254593401-18801-7-git-send-email-herve@itaapy.com","threadId":"21122","inReplyTo":"1254593401-18801-6-git-send-email-herve@itaapy.com","subject":"[PATCH 6/6] Read an object from a pack file","fromName":"Hervé Cauwelier","fromEmail":"herve@itaapy.com","sentAt":"2009-10-03T18:10:01Z","receivedAt":"2009-10-03T18:10:01Z","isPatch":true,"sender":{"key":"herve@itaapy.com","avatar":null},"body":"Signed-off-by: Hervé Cauwelier \n---\n src/odb.c | 11 +++++++----\n 1 files changed, 7 insertions(+), 4 deletions(-)\n\ndiff --git a/src/odb.c b/src/odb.c\nindex dd3c142..a712d71 100644\n--- a/src/odb.c\n+++ b/src/odb.c\n@@ -1263,13 +1263,16 @@ static int read_packed(git_obj *out, git_pack *p, const git_oid *id)\n \n \tif (pack_openidx(p))\n \t\treturn GIT_ERROR;\n+\tif (pack_openpack(p)) {\n+\t\tpack_decidx(p);\n+\t\treturn GIT_ERROR;\n+\t}\n \tres = p->idx_search(&pos, p, id);\n \tpack_decidx(p);\n+\tassert(pos < p->pack_map.len);\n \n-\tif (!res) {\n-\t\t/* TODO unpack object at pos */\n-\t\tres = GIT_ERROR;\n-\t}\n+\tif (res == GIT_SUCCESS)\n+\t\treturn inflate_pack_obj(out, p, pos);\n \n \treturn res;\n }\n-- \n1.6.4.4\n"},{"id":"124256","messageId":"20091005152755.GF9261@spearce.org","threadId":"21122","inReplyTo":"1254593401-18801-2-git-send-email-herve@itaapy.com","subject":"Re: [PATCH 1/6] Open the pack file and keep a map on it.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-10-05T15:27:55Z","receivedAt":"2009-10-05T15:27:55Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Herv?? Cauwelier wrote:\n> diff --git a/src/odb.h b/src/odb.h\n> index 2f205b2..0311d78 100644\n> --- a/src/odb.h\n> +++ b/src/odb.h\n> @@ -11,9 +11,10 @@\n> * uint32_t *fanout = ... the file data at offset 0 ...\n> * ntohl(fanout[0]) < ntohl(fanout[1])\n> *\n> - * The value chosen here for PACK_TOC is such that the above\n> + * The value chosen here for IDX_TOC is such that the above\n> * cannot be true for an idx v1 file.\n> */\n> -#define PACK_TOC 0xff744f63 /* -1tOc */\n> +#define IDX_TOC 0xff744f63 /* -1tOc */\n> +#define PACK_TOC 0x5041434b /* PACK */\n\nFWIW, I wouldn't call the magic string 'PACK' PACK_TOC. TOC here\nmeant \"table of contents\". The magic string '-1tOc' for PACK_TOC\nis no accident, its trying to show that this file is a table of\ncontents file.\n\nI think at the time I meant for PACK_TOC to be the pack-*.idx\nheader magic string, and PACK_SIG or PACK_HDR to be the magic\nstring for pack-*.pack.\n\n-- \nShawn.\n"}]}