Skip to contentSkip to conversation

Special code path for large blobs

PATCH In review Nguyễn Thái Ngọc Duy 3 participants 9 messages Jun 15, 2016

lore
Share & tools
lore
#0 lore raw

cover Special code path for large blobs

Thread "Problem with large files on different OSes" reminds me this. This series is in my repository for quite some time. It addresses adding/checking out large blobs as long as:

- no conversion will be done
- blobs are loose (in checkout case)

Together with a patch that prevents large blobs from being packed (something like Dana How sent long ago), and a modification of "lazy clone/remote alternatives" patch to avoid packing large blobs again for sending over network, I think it should make git possible for large files.

Just something to play.

Nguyễn Thái Ng�c Duy (4):
convert.c: refactor in order to skip conversion early without looking
into file content
sha1_file.c: add streaming interface for reading blobs
write_entry: use streaming interface for checkout large files
index_fd: support indexing large files

 cache.h     |   10 +++
 convert.c   |   86 ++++++++++++++++++++---
 entry.c     |   68 +++++++++++++++++
 sha1_file.c |  233 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 388 insertions(+), 9 deletions(-)
#1 lore raw

PATCH 1/4 convert.c: refactor in order to skip conversion early without looking into file content

convert_to_{git,working_tree} require the entire blob content in memory. This is impossible for large files (especially files that cannot be mapped into memory at all). Those files won't likely be converted.

This patch moves out some condition checks that does not require file content, then large file-related routines can do early check to see if it's possible to skip conversion. If not, follow the common routes.

---
 cache.h   |    2 +
 convert.c |   86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 2 files changed, 79 insertions(+), 9 deletions(-)
cache.h +2 -0
index b8503ad..f3fc822 100644
@@ -933,6 +933,8 @@ extern void trace_argv_printf(const char **argv, const char *format, ...);
 extern int convert_to_git(const char *path, const char *src, size_t len,
                           struct strbuf *dst, enum safe_crlf checksafe);
 extern int convert_to_working_tree(const char *path, const char *src, size_t len, struct strbuf *dst);
+extern int convert_to_git_needed(const char *path, size_t len);
+extern int convert_to_working_tree_needed(const char *path, size_t len);
 
 /* add */
 /*
convert.c +77 -9

148 lines not on this page · raw message

Signature · 1 line
1.6.3.1.257.gbd13
#2 lore raw

PATCH 2/4 sha1_file.c: add streaming interface for reading blobs

The reason is quite obvious: large files should not be read entirely into memory (and in some cases, cannot).

This patch deals with separate blobs only for two reasons:

1. large blobs are less likely to be put in packs (*)
2. streaming interface for blobs in pack is more complicated, thus more troublesome

(*) With regard to the first point, there is an assumption that large blobs must stay out of pack otherwise you cannot make use of this interface. This is not true now, but it was discussed and worked on in the past. Hopefully a patch series that makes this assumption true will come soon.

---
 cache.h     |    8 ++++
 sha1_file.c |  113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 121 insertions(+), 0 deletions(-)
cache.h +8 -0
index f3fc822..f6f70ce 100644
@@ -655,6 +655,14 @@ extern int write_sha1_file(void *buf, unsigned long len, const char *type, unsig
 extern int pretend_sha1_file(void *, unsigned long, enum object_type, unsigned char *);
 extern int force_object_loose(const unsigned char *sha1, time_t mtime);
 
+struct loose_object_handle;
+struct loose_object_handle *open_loose_object(const unsigned char *sha1);
+int read_loose_object(struct loose_object_handle *oh, void *buf, unsigned long len);
+int close_loose_object(struct loose_object_handle *oh);
+const unsigned char *loose_object_sha1(struct loose_object_handle *oh);
+unsigned long loose_object_size(struct loose_object_handle *oh);
+enum object_type loose_object_type(struct loose_object_handle *oh);
+
 /* global flag to enable extra checks when accessing packed objects */
 extern int do_check_packed_object_crc;
 
sha1_file.c +113 -0

119 lines not on this page · raw message

Signature · 1 line
1.6.3.1.257.gbd13
#3 lore raw

PATCH 3/4 write_entry: use streaming interface for checkout large files

With this patch, Git's memory consumption should go pretty flat no matter how large input files are. So:

- less memory will be used
- more less memory for systems that do not have proper mmap() support
- unmappable files can now be checked in

TODO: buffer size, file size limit that triggers this routine

---
 entry.c |   68 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 68 insertions(+), 0 deletions(-)
entry.c +68 -0
index cc841ed..2a49d7b 100644
@@ -91,6 +91,65 @@ static void *read_blob_entry(struct cache_entry *ce, unsigned long *size)
 	return NULL;
 }
 
+/*
+ * Trying to write entry using blob streaming interface.
+ * Return 1 if normal interface should be used.
+ */
+static int write_large_entry(struct cache_entry *ce, char *path,
+			     const struct checkout *state, int to_tempfile)
+{
+	unsigned int ce_mode_s_ifmt = ce->ce_mode & S_IFMT;
+	struct loose_object_handle *oh = open_loose_object(ce->sha1);
+	char buf[8192];
+	long len;
+	int fd;
+	size_t wrote;
+
+	if (!oh)
+		return 1;
+
+	if (loose_object_type(oh) != OBJ_BLOB) {
+		close_loose_object(oh);
+		return error("git checkout-index: unable to read sha1 file of %s (%s)",
+			     path, sha1_to_hex(ce->sha1));
+	}
+
+	if (convert_to_working_tree_needed(ce->name,  xsize_t(loose_object_size(oh)))) {
+		close_loose_object(oh);
+		return 1;
+	}
+
+	if (to_tempfile) {
+		if (ce_mode_s_ifmt == S_IFREG)
+			strcpy(path, ".merge_file_XXXXXX");
+		else
+			strcpy(path, ".merge_link_XXXXXX");
+		fd = mkstemp(path);
+	} else if (ce_mode_s_ifmt == S_IFREG) {
+		fd = create_file(path, ce->ce_mode);
+	} else {
+		fd = create_file(path, 0666);
+	}
+	if (fd < 0) {
+		close_loose_object(oh);
+		return error("git checkout-index: unable to create file %s (%s)",
+			     path, strerror(errno));
+	}
+
+	while ((len = read_loose_object(oh, buf, sizeof(buf))) > 0) {
+		wrote = write_in_full(fd, buf, len);
+		if (wrote != len) {
+			close(fd);
+			close_loose_object(oh);
+			return error("git checkout-index: unable to write file %s", path);
+		}
+	}
+
+	close(fd);
+	close_loose_object(oh);
+	return 0;
+}
+
 static int write_entry(struct cache_entry *ce, char *path, const struct checkout *state, int to_tempfile)
 {
 	unsigned int ce_mode_s_ifmt = ce->ce_mode & S_IFMT;
@@ -104,6 +163,15 @@ static int write_entry(struct cache_entry *ce, char *path, const struct checkout
 	switch (ce_mode_s_ifmt) {
 	case S_IFREG:
 	case S_IFLNK:
+		if (ce_mode_s_ifmt == S_IFREG) {
+			ret = write_large_entry(ce, path, state, to_tempfile);
+			if (ret < 0) /* failed */
+				return ret;
+			if (ret == 0) /* successful */
+				break;
+			/* else, go through */
+		}
+
 		new = read_blob_entry(ce, &size);
 		if (!new)
 			return error("git checkout-index: unable to read sha1 file of %s (%s)",
Signature · 1 line
1.6.3.1.257.gbd13
#4 lore raw

PATCH 4/4 index_fd: support indexing large files

This patch is less impressed than the previous one as memory usage is usually lower. But then systems without proper mmap() would still love it.

TODO: again, file limit

---
 sha1_file.c |  120 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 120 insertions(+), 0 deletions(-)
sha1_file.c +120 -0
index 2ed06a2..f4f90ab 100644
@@ -2609,12 +2609,132 @@ static int index_mem(unsigned char *sha1, void *buf, size_t size,
 	return ret;
 }
 
+static int index_and_write_fd(unsigned char *sha1, int fd, struct stat *st,
+			      enum object_type type, const char *path)
+{
+	int fdo, ret;
+	z_stream stream;
+	char *filename;
+	static char tmpfile[PATH_MAX];
+	int hdrlen;
+	int bufin_length = 8192, bufout_length = 8192;
+	char bufin[8192], bufout[8192];
+	int written_out = 0;
+	git_SHA_CTX c;
+
+	fdo = create_tmpfile(tmpfile, sizeof(tmpfile), "foo");
+	if (fdo < 0) {
+		if (errno == EACCES)
+			return error("insufficient permission for adding an object to repository database %s\n", get_object_directory());
+		else
+			return error("unable to create temporary sha1 filename %s: %s\n", tmpfile, strerror(errno));
+	}
+
+	hdrlen = sprintf(bufin, "%s %lu", typename(type), (unsigned long)st->st_size)+1;
+	git_SHA1_Init(&c);
+	git_SHA1_Update(&c, bufin, hdrlen);
+
+	/* Set it up */
+	memset(&stream, 0, sizeof(stream));
+	deflateInit(&stream, zlib_compression_level);
+	stream.next_out = (unsigned char *)bufout;
+	stream.avail_out = bufout_length;
+
+	/* First header.. */
+	stream.next_in = (unsigned char *)bufin;
+	stream.avail_in = hdrlen;
+	while (deflate(&stream, 0) == Z_OK)
+		/* nothing */;
+
+	written_out = stream.total_out;
+	write_or_die(fdo, bufout, written_out);
+	stream.next_out = (unsigned char *)bufout;
+	stream.avail_out = bufout_length;
+
+	/* Then the data itself.. */
+	stream.next_in = (unsigned char *)bufin;
+	stream.avail_in = xread(fd, bufin, bufin_length);
+	git_SHA1_Update(&c, stream.next_in, stream.avail_in);
+
+	while ((ret = deflate(&stream, Z_NO_FLUSH)) == Z_OK || ret == Z_BUF_ERROR) {
+		if (stream.total_out > written_out) {
+			write_or_die(fdo, bufout, stream.total_out - written_out);
+			written_out = stream.total_out;
+			stream.next_out = (unsigned char *)bufout;
+			stream.avail_out = bufout_length;
+		}
+		if (stream.avail_in == 0) {
+			stream.next_in = (unsigned char *)bufin;
+			stream.avail_in = xread(fd, bufin, bufin_length);
+			if (!stream.avail_in)
+				break;
+			git_SHA1_Update(&c, stream.next_in, stream.avail_in);
+		}
+	}
+
+	/* Done computing SHA-1 */
+	git_SHA1_Final(sha1, &c);
+
+	/* Make sure everything is flushed out */
+	while ((ret = deflate(&stream, Z_FINISH)) == Z_OK) {
+		write_or_die(fdo, bufout, stream.total_out - written_out);
+		written_out = stream.total_out;
+		stream.next_out = (unsigned char *)bufout;
+		stream.avail_out = bufout_length;
+	}
+
+	if (ret != Z_STREAM_END)
+		die("unable to deflate new object %s (%d)", sha1_to_hex(sha1), ret);
+
+	/* Last piece */
+	if (written_out < stream.total_out)
+		write_or_die(fdo, bufout, stream.total_out - written_out);
+	close_sha1_file(fdo);
+
+	ret = deflateEnd(&stream);
+	if (ret != Z_OK)
+		die("deflateEnd on object %s failed (%d)", sha1_to_hex(sha1), ret);
+
+	/* Now generate proper path from SHA-1 */
+	filename = sha1_file_name(sha1);
+	safe_create_leading_directories_const(filename);
+	return move_temp_to_file(tmpfile, filename);
+}
+
+static int hash_fd(unsigned char *sha1, int fd, struct stat *st,
+		   enum object_type type, const char *path)
+{
+	git_SHA_CTX c;
+	char buf[8192];
+	int buflen;
+
+	/* Generate the header */
+	buflen = sprintf(buf, "%s %lu", typename(type), (unsigned long)st->st_size)+1;
+
+	/* Sha1.. */
+	git_SHA1_Init(&c);
+	git_SHA1_Update(&c, buf, buflen);
+	while ((buflen = xread(fd, buf, 8192)) > 0)
+		git_SHA1_Update(&c, buf, buflen);
+	git_SHA1_Final(sha1, &c);
+	return 0;
+}
+
 int index_fd(unsigned char *sha1, int fd, struct stat *st, int write_object,
 	     enum object_type type, const char *path)
 {
 	int ret;
 	size_t size = xsize_t(st->st_size);
 
+	if (S_ISREG(st->st_mode) && path && !convert_to_git_needed(path, size)) {
+		if (write_object)
+			ret = index_and_write_fd(sha1, fd, st, type, path);
+		else
+			ret = hash_fd(sha1, fd, st, type, path);
+		close(fd);
+		return ret;
+	}
+
 	if (!S_ISREG(st->st_mode)) {
 		struct strbuf sbuf = STRBUF_INIT;
 		if (strbuf_read(&sbuf, fd, 4096) >= 0)
Signature · 1 line
1.6.3.1.257.gbd13
#5 lore raw
In reply to Nguyễn Thái Ngọc Duy
Quoted 7 lines · Nguy�n Th�i Ng�c Duy

Thread "Problem with large files on different OSes" reminds me this. This series is in my repository for quite some time. It addresses adding/checking out large blobs as long as:

- no conversion will be done
- blobs are loose (in checkout case)

Quoted 7 lines

Together with a patch that prevents large blobs from being packed (something like Dana How sent long ago), and a modification of "lazy clone/remote alternatives" patch to avoid packing large blobs again for sending over network, I think it should make git possible for large files.

Just something to play.

I think this is a good start.

However, like I said previously, I'd encapsulate large blobs in a pack right away instead of storing them as loose objects. The reason is that you can effortlessly repack/fetch/push them afterwards by simply triggering the pack data reuse code path for them. Extracting large and undeltified blobs from a pack is just as easy as from a loose object.

To accomplish that, you only need to copy write_pack_file() from builtin-pack-objects.c and strip it to the bone with only one object to write.

Nicolas

#6 lore raw

2009/5/29 Nicolas Pitre <[email protected]>:

Quoted 5 lines

However, like I said previously, I'd encapsulate large blobs in a pack right away instead of storing them as loose objects.  The reason is that you can effortlessly repack/fetch/push them afterwards by simply triggering the pack data reuse code path for them.  Extracting large and undeltified blobs from a pack is just as easy as from a loose object.

Makes sense. And the code looks nice too.

Quoted 3 lines

To accomplish that, you only need to copy write_pack_file() from builtin-pack-objects.c and strip it to the bone with only one object to write.

write_pack_file() is too scary to me, I ripped from fast-import.c instead. BTW, how does git handle hundreds of single object packs? I don't know if prepare_packed_git scales in such cases.

Signature · 1 line
Duy
#7 lore raw
Quoted 9 lines · Nguyen Thai Ngoc Duy

2009/5/29 Nicolas Pitre <[email protected]>:

Quoted 5 lines

However, like I said previously, I'd encapsulate large blobs in a pack right away instead of storing them as loose objects. ??The reason is that you can effortlessly repack/fetch/push them afterwards by simply triggering the pack data reuse code path for them. ??Extracting large and undeltified blobs from a pack is just as easy as from a loose object.

Makes sense. And the code looks nice too.

Quoted 7 lines
Quoted 3 lines

To accomplish that, you only need to copy write_pack_file() from builtin-pack-objects.c and strip it to the bone with only one object to write.

write_pack_file() is too scary to me, I ripped from fast-import.c instead. BTW, how does git handle hundreds of single object packs? I don't know if prepare_packed_git scales in such cases.

Yea, its not going to do that great.

We may be able to improve that code path by sorting any pack whose index is really small and pack file is really big to the end of the list, where its least likely to be matched, so we don't even bother to load the index into memory during normal commit traversal.

But even with that sorting, its still going to suck. Lookup for a large binary is O(N), where N is the number of large binary *revisions*. Yuck.

Really, objects in the 200MB+ range probably should just be in a lone file named by its SHA-1... aka, a loose object. Combining them into a pack is going to be potentially expensive disk IO wise, and may not gain you very much (its over 200 MB compressed with deflate, its likely already compressed binary content that may not delta well).

Way back we had that pack-style loose object format, for exactly these sorts of files, and exactly to avoid having many packs of just 1 object, but that didn't go anywhere... indeed, Nico deleted the code that creates that format.

Signature · 1 line
Shawn.
#8 lore raw
Quoted 14 lines · Shawn O. Pearce
Quoted 13 lines · Nguyen Thai Ngoc Duy

2009/5/29 Nicolas Pitre <[email protected]>:

Quoted 5 lines

However, like I said previously, I'd encapsulate large blobs in a pack right away instead of storing them as loose objects. ??The reason is that you can effortlessly repack/fetch/push them afterwards by simply triggering the pack data reuse code path for them. ??Extracting large and undeltified blobs from a pack is just as easy as from a loose object.

Makes sense. And the code looks nice too.

Quoted 3 lines

To accomplish that, you only need to copy write_pack_file() from builtin-pack-objects.c and strip it to the bone with only one object to write.

Quoted 5 lines
Quoted 3 lines

write_pack_file() is too scary to me, I ripped from fast-import.c instead. BTW, how does git handle hundreds of single object packs? I don't know if prepare_packed_git scales in such cases.

Yea, its not going to do that great.

Well... remember that we're talking about huge objects here. You're not likely to have so many of them. And if you do have that many huge objects, then any operation you do is likely to access one of them anyway and then the pack lookup overhead will be lost in the noise.

Quoted 6 lines

We may be able to improve that code path by sorting any pack whose index is really small and pack file is really big to the end of the list, where its least likely to be matched, so we don't even bother to load the index into memory during normal commit traversal.

But even with that sorting, its still going to suck.

I don't agree with that statement. Supposing the sorting you propose above which I consider a pretty good idea doesn't provide any improvement, we already do pretty well with many packs since commit f7c22cc6.

Quoted 2 lines

Lookup for a large binary is O(N), where N is the number of large binary *revisions*. Yuck.

It is almost like loose object lookups, except that you don't have a 256 entry fanout. But since the IO corresponding to such objects is expected to be much more significant than 256 times the IO for a tree or commit object, then again this shouldn't matter much in practice.

Quoted 5 lines

Really, objects in the 200MB+ range probably should just be in a lone file named by its SHA-1... aka, a loose object. Combining them into a pack is going to be potentially expensive disk IO wise, and may not gain you very much (its over 200 MB compressed with deflate, its likely already compressed binary content that may not delta well).

I must disagree again. The above notwithstanding, the idea is _not_ to keep those large blobs into their own packs. The idea is mainly to make a future repack much much easier with the current repack-objects code. And yes, we should repack even those large blobs eventually just like we do for loose objects. Really there is no point keeping even large blobs in their own files. If you do care about object lookup efficiency, having large objects into their own pack or loose does not make such a huge difference. Sure a factor of 256 might be considered significant, but this is only a linear cost improvement while object lookup within a pack gets an exponential cost improvement.

There are ways already to enforce some size policies on pack files if you don't want to keep all your objects into a single pack, but even a single huge pack should work just fine as well and you may .keep it afterward not to repack it anymore, or until a monthly or quarterly repository maintenance. So in practice you shouldn't be accumulating _that_ many single object packs anyway.

Quoted 4 lines

Way back we had that pack-style loose object format, for exactly these sorts of files, and exactly to avoid having many packs of just 1 object, but that didn't go anywhere... indeed, Nico deleted the code that creates that format.

And the rational was exactly the one above: large blobs have no reason what so ever to _remain_ alone into a file, be it a loose object or a single object pack. And just like for loose objects, you don't have to repack large blobs right away so the IO cost can be postponed for when that doesn't matter.

Nicolas