Patches for libgit2

Patches for libgit2

[Hervé Cauwelier]

Hi,

Please find patches for libgit2. They allowed me to read the history of a
repository with only 75 patches but hacked by an history shortening.

Commits were both in a 5 GB pack file and loose objects. So I had to add
support for pack files. Hopefully, reading idx files was already there so I
followed the same model.

Patches can also be cloned at "git://git.hforge.org/libgit2.git".

There is a Python wrapper on the next side, forking from the existing
libgit2-python [1]. They bring the same functionnalities but the patches are
not slick yet.

[1] http://code.istique.net/gitweb/?p=libgit2-python.git;a=summary

One thing that would miss is unit tests, but I lack experience on testing C
code, and it would require having a small but exhaustive pack file with
different types of object, including ofs and ref deltas. Help on this part is
welcome.

Next step would be decoding raw objects to commits, trees, blobs and tags.
There is already the start of a commit structure. I'll be starting from that.

Regards,

Hervé

[PATCH 1/6] Open the pack file and keep a map on it.

[Hervé Cauwelier]

On the same model than the idx file.

Signed-off-by: Hervé Cauwelier <herve@itaapy.com>
---
 src/odb.c |   67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 src/odb.h |    5 ++-
 2 files changed, 68 insertions(+), 4 deletions(-)

diff --git a/src/odb.c b/src/odb.c
index 6d646a4..a562a19 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -64,6 +64,10 @@ struct git_pack {
 
 	/** Name of the pack file(s), without extension ("pack-abc"). */
 	char pack_name[GIT_PACK_NAME_MAX];
+
+	/** The .pack file, mapped into memory. */
+	git_file pack_fd;
+	git_map pack_map;
 };
 typedef struct git_pack git_pack;
 
@@ -782,7 +786,7 @@ static int pack_openidx(git_pack *p)
 			goto invalid_fail;
 		data = p->idx_map.data;
 
-		if (decode32(&data[0]) == PACK_TOC) {
+		if (decode32(&data[0]) == IDX_TOC) {
 			switch (decode32(&data[1])) {
 			case 2:
 				if (pack_openidx_v2(p))
@@ -809,6 +813,59 @@ unlock_fail:
 	return GIT_ERROR;
 }
 
+static int pack_openpack_map(git_pack *p)
+{
+	char pb[GIT_PATH_MAX];
+	off_t len;
+
+	if (git__fmt(pb, sizeof(pb), "%s/pack/%s.pack",
+			p->db->objects_dir,
+			p->pack_name) < 0)
+		return GIT_ERROR;
+
+	if ((p->pack_fd = gitfo_open(pb, O_RDONLY)) < 0)
+		return GIT_ERROR;
+
+	if ((len = gitfo_size(p->pack_fd)) < 0
+			|| !git__is_sizet(len)
+			|| gitfo_map_ro(&p->pack_map, p->pack_fd, 0, (size_t)len)) {
+		gitfo_close(p->pack_fd);
+		return GIT_ERROR;
+	}
+
+	return GIT_SUCCESS;
+}
+
+static int pack_openpack(git_pack *p)
+{
+	gitlck_lock(&p->lock);
+	if (p->invalid)
+		goto unlock_fail;
+	if (p->pack_fd < 0) {
+		uint32_t *data;
+
+		if (pack_openpack_map(p))
+			goto invalid_fail;
+		data = p->pack_map.data;
+
+		if (decode32(&data[0]) != PACK_TOC)
+			goto unmap_fail;
+	}
+	gitlck_unlock(&p->lock);
+	return GIT_SUCCESS;
+
+unmap_fail:
+	gitfo_free_map(&p->pack_map);
+
+invalid_fail:
+	p->invalid = 1;
+	p->pack_fd = -1;
+
+unlock_fail:
+	gitlck_unlock(&p->lock);
+	return GIT_ERROR;
+}
+
 static void pack_decidx(git_pack *p)
 {
 	gitlck_lock(&p->lock);
@@ -830,6 +887,11 @@ static void pack_dec(git_pack *p)
 			gitfo_close(p->idx_fd);
 			free(p->im_fanout);
 		}
+		if (p->pack_fd >= 0) {
+			gitfo_free_map(&p->pack_map);
+			gitfo_close(p->pack_fd);
+			p->pack_fd = -1;
+		}
 
 		gitlck_free(&p->lock);
 		free(p);
@@ -861,6 +923,7 @@ static git_pack *alloc_pack(const char *pack_name)
 	gitlck_init(&p->lock);
 	strcpy(p->pack_name, pack_name);
 	p->refcnt = 1;
+	p->pack_fd = -1;
 	return p;
 }
 
@@ -895,7 +958,7 @@ static int scan_one_pack(void *state, char *name)
 
 	r->next = *ret;
 	*ret = r;
-	return 0;
+	return GIT_SUCCESS;
 }
 
 static git_packlist* scan_packs(git_odb *db)
diff --git a/src/odb.h b/src/odb.h
index 2f205b2..0311d78 100644
--- a/src/odb.h
+++ b/src/odb.h
@@ -11,9 +11,10 @@
  *   uint32_t *fanout = ... the file data at offset 0 ...
  *   ntohl(fanout[0]) < ntohl(fanout[1])
  *
- * The value chosen here for PACK_TOC is such that the above
+ * The value chosen here for IDX_TOC is such that the above
  * cannot be true for an idx v1 file.
  */
-#define PACK_TOC 0xff744f63 /* -1tOc */
+#define IDX_TOC 0xff744f63 /* -1tOc */
+#define PACK_TOC 0x5041434b /* PACK */
 
 #endif
-- 
1.6.4.4

[PATCH 2/6] Read the base offset or name of delta objects

[Hervé Cauwelier]

Signed-off-by: Hervé Cauwelier <herve@itaapy.com>
---
 src/cc-compat.h |    3 +++
 src/odb.c       |   28 ++++++++++++++++++++++++++--
 2 files changed, 29 insertions(+), 2 deletions(-)

diff --git a/src/cc-compat.h b/src/cc-compat.h
index 8997caa..8dd6774 100644
--- a/src/cc-compat.h
+++ b/src/cc-compat.h
@@ -30,6 +30,9 @@
 # define GIT_TYPEOF(x)
 #endif
 
+#define bitsizeof(x)  (CHAR_BIT * sizeof(x))
+#define MSB(x, bits) ((x) & GIT_TYPEOF(x)(~0ULL << (bitsizeof(x) - (bits))))
+
 /*
  * Does our compiler/platform support the C99 <inttypes.h> and
  * <stdint.h> header files. (C99 requires that <inttypes.h>
diff --git a/src/odb.c b/src/odb.c
index a562a19..3cfc932 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -97,8 +97,10 @@ struct git_odb {
 };
 
 typedef struct {  /* object header data */
-	git_otype type;  /* object type */
-	size_t    size;  /* object size */
+	git_otype type;     /* object type */
+	size_t    size;     /* object size */
+	off_t base_offset;  /* delta base offset (GIT_OBJ_OFS_DELTA) */
+	git_oid base_name;  /* delta base name (GIT_OBJ_REF_DELTA) */
 } obj_hdr;
 
 static struct {
@@ -238,6 +240,7 @@ static size_t get_binary_object_header(obj_hdr *hdr, gitfo_buf *obj)
 	unsigned char c;
 	unsigned char *data = obj->data;
 	size_t shift, size, used = 0;
+	off_t base_offset;
 
 	if (obj->len == 0)
 		return 0;
@@ -258,6 +261,27 @@ static size_t get_binary_object_header(obj_hdr *hdr, gitfo_buf *obj)
 	}
 	hdr->size = size;
 
+	hdr->base_offset = 0;
+	hdr->base_name.id[0] = '\0';
+
+	if (hdr->type == GIT_OBJ_OFS_DELTA) {
+		c = data[used++];
+		base_offset = c & 127;
+		while (c & 128) {
+			base_offset++;
+			if (!base_offset || MSB(base_offset, 7))
+				return 0;  /* overflow */
+			c = data[used++];
+			base_offset = (base_offset << 7) + (c & 127);
+		}
+		assert(base_offset > 0);
+		hdr->base_offset = base_offset;
+	}
+	else if (hdr->type == GIT_OBJ_REF_DELTA) {
+		git_oid_mkraw(&hdr->base_name, data + used);
+		used += 20;
+	}
+
 	return used;
 }
 
-- 
1.6.4.4

[PATCH 3/6] Allow zlib to read a pack buffer longer than the actual data

[Hervé Cauwelier]

As we don't know where the compressed data end, only the size of the
uncompressed data.

Signed-off-by: Hervé Cauwelier <herve@itaapy.com>
---
 src/odb.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/src/odb.c b/src/odb.c
index 3cfc932..89ee1f2 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -432,7 +432,7 @@ static int inflate_buffer(void *in, size_t inlen, void *out, size_t outlen)
 
 	inflateEnd(&zs);
 
-	if ((status != Z_STREAM_END) || (zs.avail_in != 0))
+	if (status != Z_STREAM_END)
 		return GIT_ERROR;
 
 	if (zs.total_out != outlen)
-- 
1.6.4.4

[PATCH 4/6] Inflate an object from a pack file

[Hervé Cauwelier]

Support delta objects too.

Signed-off-by: Hervé Cauwelier <herve@itaapy.com>
---
 src/odb.c |   69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 68 insertions(+), 1 deletions(-)

diff --git a/src/odb.c b/src/odb.c
index 89ee1f2..bc26cf7 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -28,6 +28,7 @@
 #include "git/zlib.h"
 #include "fileops.h"
 #include "hash.h"
+#include "delta-apply.h"
 #include "odb.h"
 
 #define GIT_PACK_NAME_MAX (5 + 40 + 1)
@@ -232,7 +233,7 @@ static int is_zlib_compressed_data(unsigned char *data)
 	unsigned int w;
 
 	w = ((unsigned int)(data[0]) << 8) + data[1];
-	return data[0] == 0x78 && !(w %31);
+	return data[0] == 0x78 && !(w % 31);
 }
 
 static size_t get_binary_object_header(obj_hdr *hdr, gitfo_buf *obj)
@@ -1192,6 +1193,72 @@ int git_odb__read_loose(git_obj *out, git_odb *db, const git_oid *id)
 	return GIT_SUCCESS;
 }
 
+static int inflate_pack_obj(git_obj *out, git_pack *p, off_t offset)
+{
+	obj_hdr hdr;
+	gitfo_buf buf;
+	size_t used;
+	void *data;
+	git_obj base;
+
+	/* Cast the map to a gitfo_buf */
+	buf.data = (unsigned char *)p->pack_map.data + offset;
+	buf.len = p->pack_map.len - offset;
+
+	/*
+	 * Read the object header, which is an (uncompressed)
+	 * binary encoding of the object type and size.
+	 */
+	if (!(used = get_binary_object_header(&hdr, &buf)))
+		return GIT_ERROR;
+
+	/*
+	 * Read the object data as a zlib compressed data
+	 */
+	buf.data += used;
+	buf.len -= used;
+	assert(is_zlib_compressed_data(buf.data));
+
+	if (!(data = git__malloc(hdr.size + 1)))
+		return GIT_ERROR;
+	if (inflate_buffer(buf.data, buf.len, data, hdr.size))
+		goto inflate_fail;
+
+	switch (hdr.type) {
+		case GIT_OBJ_COMMIT:
+		case GIT_OBJ_TREE:
+		case GIT_OBJ_BLOB:
+		case GIT_OBJ_TAG:
+			out->data = data;
+			out->len = hdr.size;
+			out->type = hdr.type;
+			return GIT_SUCCESS;
+		case GIT_OBJ_OFS_DELTA:
+			offset -= hdr.base_offset;
+			if (inflate_pack_obj(&base, p, offset))
+				goto inflate_fail;
+			if (git__delta_apply(out, base.data, base.len, data, hdr.size))
+				goto inflate_fail;
+			out->type = base.type;
+			return GIT_SUCCESS;
+		case GIT_OBJ_REF_DELTA:
+			if (p->idx_search(&offset, p, &hdr.base_name))
+				goto inflate_fail;
+			if (inflate_pack_obj(&base, p, offset))
+				goto inflate_fail;
+			if (git__delta_apply(out, base.data, base.len, data, hdr.size))
+				goto inflate_fail;
+			out->type = base.type;
+			return GIT_SUCCESS;
+		default:
+			goto inflate_fail;
+	}
+
+inflate_fail:
+	free(data);
+	return GIT_ERROR;
+}
+
 static int read_packed(git_obj *out, git_pack *p, const git_oid *id)
 {
 	off_t pos;
-- 
1.6.4.4

[PATCH 5/6] This assertion is valid for both loose and packed objects

[Hervé Cauwelier]

Signed-off-by: Hervé Cauwelier <herve@itaapy.com>
---
 src/odb.c |    9 +++------
 1 files changed, 3 insertions(+), 6 deletions(-)

diff --git a/src/odb.c b/src/odb.c
index bc26cf7..dd3c142 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -1149,11 +1149,10 @@ void git_odb_close(git_odb *db)
 	free(db);
 }
 
-int git_odb_read(
-	git_obj *out,
-	git_odb *db,
-	const git_oid *id)
+int git_odb_read(git_obj *out, git_odb *db, const git_oid *id)
 {
+	assert(out && db && id);
+
 attempt:
 	if (!git_odb__read_packed(out, db, id))
 		return GIT_SUCCESS;
@@ -1171,8 +1170,6 @@ int git_odb__read_loose(git_obj *out, git_odb *db, const git_oid *id)
 	char file[GIT_PATH_MAX];
 	gitfo_buf obj = GITFO_BUF_INIT;
 
-	assert(out && db && id);
-
 	out->data = NULL;
 	out->len  = 0;
 	out->type = GIT_OBJ_BAD;
-- 
1.6.4.4

[PATCH 6/6] Read an object from a pack file

[Hervé Cauwelier]

Signed-off-by: Hervé Cauwelier <herve@itaapy.com>
---
 src/odb.c |   11 +++++++----
 1 files changed, 7 insertions(+), 4 deletions(-)

diff --git a/src/odb.c b/src/odb.c
index dd3c142..a712d71 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -1263,13 +1263,16 @@ static int read_packed(git_obj *out, git_pack *p, const git_oid *id)
 
 	if (pack_openidx(p))
 		return GIT_ERROR;
+	if (pack_openpack(p)) {
+		pack_decidx(p);
+		return GIT_ERROR;
+	}
 	res = p->idx_search(&pos, p, id);
 	pack_decidx(p);
+	assert(pos < p->pack_map.len);
 
-	if (!res) {
-		/* TODO unpack object at pos */
-		res = GIT_ERROR;
-	}
+	if (res == GIT_SUCCESS)
+		return inflate_pack_obj(out, p, pos);
 
 	return res;
 }
-- 
1.6.4.4

Re: [PATCH 1/6] Open the pack file and keep a map on it.

[Shawn O. Pearce]

Herv?? Cauwelier <herve@itaapy.com> wrote:
> diff --git a/src/odb.h b/src/odb.h
> index 2f205b2..0311d78 100644
> --- a/src/odb.h
> +++ b/src/odb.h
> @@ -11,9 +11,10 @@
>   *   uint32_t *fanout = ... the file data at offset 0 ...
>   *   ntohl(fanout[0]) < ntohl(fanout[1])
>   *
> - * The value chosen here for PACK_TOC is such that the above
> + * The value chosen here for IDX_TOC is such that the above
>   * cannot be true for an idx v1 file.
>   */
> -#define PACK_TOC 0xff744f63 /* -1tOc */
> +#define IDX_TOC 0xff744f63 /* -1tOc */
> +#define PACK_TOC 0x5041434b /* PACK */

FWIW, I wouldn't call the magic string 'PACK' PACK_TOC.  TOC here
meant "table of contents".  The magic string '-1tOc' for PACK_TOC
is no accident, its trying to show that this file is a table of
contents file.

I think at the time I meant for PACK_TOC to be the pack-*.idx
header magic string, and PACK_SIG or PACK_HDR to be the magic
string for pack-*.pack.

-- 
Shawn.

[PATCH 1/6] Open the pack file and keep a map on it.

[Hervé Cauwelier]

On the same model than the idx file.

Signed-off-by: Hervé Cauwelier <herve@itaapy.com>
---
 src/odb.c |   65 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 src/odb.h |    1 +
 2 files changed, 65 insertions(+), 1 deletions(-)

diff --git a/src/odb.c b/src/odb.c
index 6d646a4..2319998 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -64,6 +64,10 @@ struct git_pack {
 
 	/** Name of the pack file(s), without extension ("pack-abc"). */
 	char pack_name[GIT_PACK_NAME_MAX];
+
+	/** The .pack file, mapped into memory. */
+	git_file pack_fd;
+	git_map pack_map;
 };
 typedef struct git_pack git_pack;
 
@@ -809,6 +813,59 @@ unlock_fail:
 	return GIT_ERROR;
 }
 
+static int pack_openpack_map(git_pack *p)
+{
+	char pb[GIT_PATH_MAX];
+	off_t len;
+
+	if (git__fmt(pb, sizeof(pb), "%s/pack/%s.pack",
+			p->db->objects_dir,
+			p->pack_name) < 0)
+		return GIT_ERROR;
+
+	if ((p->pack_fd = gitfo_open(pb, O_RDONLY)) < 0)
+		return GIT_ERROR;
+
+	if ((len = gitfo_size(p->pack_fd)) < 0
+			|| !git__is_sizet(len)
+			|| gitfo_map_ro(&p->pack_map, p->pack_fd, 0, (size_t)len)) {
+		gitfo_close(p->pack_fd);
+		return GIT_ERROR;
+	}
+
+	return GIT_SUCCESS;
+}
+
+static int pack_openpack(git_pack *p)
+{
+	gitlck_lock(&p->lock);
+	if (p->invalid)
+		goto unlock_fail;
+	if (p->pack_fd < 0) {
+		uint32_t *data;
+
+		if (pack_openpack_map(p))
+			goto invalid_fail;
+		data = p->pack_map.data;
+
+		if (decode32(&data[0]) != PACK_HDR)
+			goto unmap_fail;
+	}
+	gitlck_unlock(&p->lock);
+	return GIT_SUCCESS;
+
+unmap_fail:
+	gitfo_free_map(&p->pack_map);
+
+invalid_fail:
+	p->invalid = 1;
+	p->pack_fd = -1;
+
+unlock_fail:
+	gitlck_unlock(&p->lock);
+	return GIT_ERROR;
+}
+
 static void pack_decidx(git_pack *p)
 {
 	gitlck_lock(&p->lock);
@@ -830,6 +887,11 @@ static void pack_dec(git_pack *p)
 			gitfo_close(p->idx_fd);
 			free(p->im_fanout);
 		}
+		if (p->pack_fd >= 0) {
+			gitfo_free_map(&p->pack_map);
+			gitfo_close(p->pack_fd);
+			p->pack_fd = -1;
+		}
 
 		gitlck_free(&p->lock);
 		free(p);
@@ -861,6 +923,7 @@ static git_pack *alloc_pack(const char *pack_name)
 	gitlck_init(&p->lock);
 	strcpy(p->pack_name, pack_name);
 	p->refcnt = 1;
+	p->pack_fd = -1;
 	return p;
 }
 
@@ -895,7 +958,7 @@ static int scan_one_pack(void *state, char *name)
 
 	r->next = *ret;
 	*ret = r;
-	return 0;
+	return GIT_SUCCESS;
 }
 
 static git_packlist* scan_packs(git_odb *db)
diff --git a/src/odb.h b/src/odb.h
index 2f205b2..121583f 100644
--- a/src/odb.h
+++ b/src/odb.h
@@ -15,5 +15,6 @@
  * cannot be true for an idx v1 file.
  */
 #define PACK_TOC 0xff744f63 /* -1tOc */
+#define PACK_HDR 0x5041434b /* PACK */
 
 #endif
-- 
1.6.5

Re: [PATCH 1/6] Open the pack file and keep a map on it.

[Sverre Rabbelier]

Heya,

2009/10/14 Hervé Cauwelier <herve@itaapy.com>:

Please include a cover letter for series as long as these (anything
larger than 4 should have a cover letter IMHO). Doing so makes it
easier for those that follow the series to see what changed (assuming
you write down what changed in the cover letter). Also, it makes it
easier for those that were not following the series to drop in at the
current version (assuming you provide a short summary of what the
series is about in the cover letter).

-- 
Cheers,

Sverre Rabbelier

Re: [PATCH 1/6] Open the pack file and keep a map on it.

[Hervé Cauwelier]

On 14/10/2009 14:48, Sverre Rabbelier wrote:
> Heya,
>
> 2009/10/14 Hervé Cauwelier<herve@itaapy.com>:
>
> Please include a cover letter for series as long as these (anything
> larger than 4 should have a cover letter IMHO). Doing so makes it
> easier for those that follow the series to see what changed (assuming
> you write down what changed in the cover letter). Also, it makes it
> easier for those that were not following the series to drop in at the
> current version (assuming you provide a short summary of what the
> series is about in the cover letter).

Hi, indeed I forgot and send-email sent them without asking confirmation.

The only change is the comment by Shawn about keeping the PACK_TOC 
constant as is and calling the other one PACK_HDR.

Regards

-- 
Hervé Cauwelier - ITAAPY - 9 rue Darwin 75018 Paris
Tél. 01 42 23 67 45 - Fax 01 53 28 27 88
http://www.itaapy.com/ - http://www.cms-migration.com

Re: [PATCH 1/6] Open the pack file and keep a map on it.

[Sverre Rabbelier]

Heya,

2009/10/14 Hervé Cauwelier <herve@itaapy.com>:
> Hi, indeed I forgot and send-email sent them without asking confirmation.

Note to self: write patch to git send-email...
Note to self 2: learn perl
Note to self 3: find someone else to write said patch to git
send-email, perl is scary

-- 
Cheers,

Sverre Rabbelier