RFC object filtering for parital clone

From: Jeff Hostetler <[email protected]>

This patch series contains WIP code demonstrating object (blob) filtering in rev-list and pack-objects using a common filtering API in list-objects and traverse-commit-list that allows both commands to perform the same type of filter operations. And serve as the basis of partial-clone and partial-fetch.

This draft contains filters to:
() omit all blobs
() omit blobs larger than some size
() omit blobs using a sparse-checkout specification

In addition to specifying the filter criteria, the rev-list command was updated to include options to:
() print a list of the omitted objects (due to the current filtering
criteria)
() print a list of missing objects (probably from a prior partial
clone/fetch).

This latter print option can be used with or without a new filter criteria allowing it to be used with a pre-checkout bulk pre-fetch command.

For example, if blobs were omitted during the clone or a fetch, the client can do:

   git rev-list --quiet --objects --filter-print-missing NEWBRANCH

and get a list of just the objects that are required to checkout NEWBRANCH.

Or if a sparse-checkout is in effect, the client can specify the same criteria to look for just the missing blobs needed to do the sparse-checkout:

   git rev-list --quiet --objects --filter-print-missing \
       --filter-use-path=./git/info/sparse-checkout NEWBRANCH

It does not matter why a blob is missing; that is, what filter criteria was used during the clone or fetch. All that matters is the blob is missing and is now needed.

These commands output a list of missing blobs that can be fed into a bulk fetch object request. The goal here is to minimize the need for dynamic object fetch mechanisms currently being discussed. (We cannot eliminate the need for dynamic fetching, but we can use this to precompute/prefetch in bulk.)

Pack-objects was updated to allow the server to build incomplete packfiles without unwanted blobs.

This is the first step to support partial-clone and -fetch. I've omitted from this patch series corresponding changes to fetch-pack, upload-pack, index-pack, verify-pack, fsck, gc, and the git protocol. I can make these available if there is interest. I omit them from this RFC to not distract from the basic filtering ideas.

It also does not address the promisor/promised ideas currently being discussed [2,3]. These should be considered independently.

The code in this patch series can be seen here [1].

[1] https://github.com/jeffhostetler/git/pull/3
[2] https://public-inbox.org/git/[email protected]/t/
[3] https://github.com/jonathantanmy/git/commits/partialclone2

Jeff Hostetler (13):
dir: refactor add_excludes()
oidset2: create oidset subclass with object length and pathname
list-objects: filter objects in traverse_commit_list
list-objects-filter-all: add filter to omit all blobs
list-objects-filter-large: add large blob filter to list-objects list-objects-filter-sparse: add sparse-checkout based filter
object-filter: common declarations for object filtering
list-objects: add traverse_commit_list_filtered method
rev-list: add object filtering support
rev-list: add filtering help text
t6112: rev-list object filtering test
pack-objects: add object filtering support
pack-objects: add filtering help text

 Documentation/git-pack-objects.txt  |  17 +++
 Documentation/git-rev-list.txt      |   9 +-
 Documentation/rev-list-options.txt  |  32 +++++
 Makefile                            |   5 +
 builtin/pack-objects.c              |  24 +++-
 builtin/rev-list.c                  |  73 +++++++++-
 dir.c                               |  53 ++++++-
 dir.h                               |   4 +
 list-objects-filter-all.c           |  85 ++++++++++++
 list-objects-filter-all.h           |  18 +++
 list-objects-filter-large.c         | 108 +++++++++++++++
 list-objects-filter-large.h         |  18 +++
 list-objects-filter-sparse.c        | 221 +++++++++++++++++++++++++++++
 list-objects-filter-sparse.h        |  30 ++++
 list-objects.c                      | 100 +++++++++++---
 list-objects.h                      |  41 ++++++
 object-filter.c                     | 269 ++++++++++++++++++++++++++++++++++++
 object-filter.h                     | 173 +++++++++++++++++++++++
 oidset2.c                           | 104 ++++++++++++++
 oidset2.h                           |  58 ++++++++
 t/t6112-rev-list-filters-objects.sh | 237 +++++++++++++++++++++++++++++++
 21 files changed, 1657 insertions(+), 22 deletions(-)
 create mode 100644 list-objects-filter-all.c
 create mode 100644 list-objects-filter-all.h
 create mode 100644 list-objects-filter-large.c
 create mode 100644 list-objects-filter-large.h
 create mode 100644 list-objects-filter-sparse.c
 create mode 100644 list-objects-filter-sparse.h
 create mode 100644 object-filter.c
 create mode 100644 object-filter.h
 create mode 100644 oidset2.c
 create mode 100644 oidset2.h
 create mode 100755 t/t6112-rev-list-filters-objects.sh

2.9.3

From: Jeff Hostetler <[email protected]>

Refactor add_excludes() to separate the reading of the exclude file into a buffer and the parsing of the buffer into exclude_list items.

Add add_excludes_from_blob_to_list() to allow an exclude file be specified with an OID.

---
 dir.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 dir.h |  4 ++++
 2 files changed, 55 insertions(+), 2 deletions(-)

index ae6f5c9..3aeae06 100644
@@ -739,6 +739,11 @@ static void invalidate_directory(struct untracked_cache *uc,
 		dir->dirs[i]->recurse = 0;
 }
 
+static int add_excludes_from_buffer(
+	char *buf, size_t size,
+	const char *base, int baselen,
+	struct exclude_list *el);
+
 /*
  * Given a file with name "fname", read it (either from disk, or from
  * an index if 'istate' is non-null), parse it and store the

@@ -754,9 +759,9 @@ static int add_excludes(const char *fname, const char *base, int baselen,
 			struct sha1_stat *sha1_stat)
 {
 	struct stat st;
-	int fd, i, lineno = 1;
+	int fd;
 	size_t size = 0;
-	char *buf, *entry;
+	char *buf;
 
 	fd = open(fname, O_RDONLY);
 	if (fd < 0 || fstat(fd, &st) < 0) {

@@ -813,6 +818,18 @@ static int add_excludes(const char *fname, const char *base, int baselen,
 		}
 	}
 
+	add_excludes_from_buffer(buf, size, base, baselen, el);
+	return 0;
+}
+
+static int add_excludes_from_buffer(
+	char *buf, size_t size,
+	const char *base, int baselen,
+	struct exclude_list *el)
+{
+	int i, lineno = 1;
+	char *entry;
+
 	el->filebuf = buf;
 
 	if (skip_utf8_bom(&buf, size))

@@ -841,6 +858,38 @@ int add_excludes_from_file_to_list(const char *fname, const char *base,
 	return add_excludes(fname, base, baselen, el, istate, NULL);
 }
 
+int add_excludes_from_blob_to_list(
+	struct object_id *oid,
+	const char *base, int baselen,
+	struct exclude_list *el)
+{
+	char *buf;
+	unsigned long size;
+	enum object_type type;
+
+	buf = read_sha1_file(oid->hash, &type, &size);
+	if (!buf)
+		return -1;
+
+	if (type != OBJ_BLOB) {
+		free(buf);
+		return -1;
+	}
+
+	if (size == 0) {
+		free(buf);
+		return 0;
+	}
+
+	if (buf[size - 1] != '\n') {
+		buf = xrealloc(buf, st_add(size, 1));
+		buf[size++] = '\n';
+	}
+
+	add_excludes_from_buffer(buf, size, base, baselen, el);
+	return 0;
+}
+
 struct exclude_list *add_exclude_list(struct dir_struct *dir,
 				      int group_type, const char *src)
 {

index e371705..242de63 100644
@@ -256,6 +256,10 @@ extern struct exclude_list *add_exclude_list(struct dir_struct *dir,
 extern int add_excludes_from_file_to_list(const char *fname, const char *base, int baselen,
 					  struct exclude_list *el, struct  index_state *istate);
 extern void add_excludes_from_file(struct dir_struct *, const char *fname);
+extern int add_excludes_from_blob_to_list(
+	struct object_id *oid,
+	const char *base, int baselen,
+	struct exclude_list *el);
 extern void parse_exclude_pattern(const char **string, int *patternlen, unsigned *flags, int *nowildcardlen);
 extern void add_exclude(const char *string, const char *base,
 			int baselen, struct exclude_list *el, int srcpos);

2.9.3

From: Jeff Hostetler <[email protected]>

Create subclass of oidset where each entry has a field to store the length of the object's content and an optional pathname.

This will be used in a future commit to build a manifest of omitted objects in a partial/narrow clone/fetch.

---
 Makefile  |   1 +
 oidset2.c | 104 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 oidset2.h |  58 +++++++++++++++++++++++++++++++++++
 3 files changed, 163 insertions(+)
 create mode 100644 oidset2.c
 create mode 100644 oidset2.h

index 461c845..4e0cc39 100644
@@ -816,6 +816,7 @@ LIB_OBJS += notes-merge.o
 LIB_OBJS += notes-utils.o
 LIB_OBJS += object.o
 LIB_OBJS += oidset.o
+LIB_OBJS += oidset2.o
 LIB_OBJS += pack-bitmap.o
 LIB_OBJS += pack-bitmap-write.o
 LIB_OBJS += pack-check.o

2.9.3

I think it may be better to create an 'oidmap' instead of an 'oidset+some specific other bits' that way, in the future, we have a generalized data structure which we can use to provide a mapping between oids and some arbitrary data.

Brandon Williams

As Brandon mentioned, I think "oidmap" should be the new data structure of choice (with "oidset" modified to use it).

I'll take a look at that. I'm not exactly happy with my oidset2, but it works and it minimized touching other things. But yes, it may clear up a few things.

Yeah, I struggled with that one. Git currently treats file size as a 32-bit unsigned value throughout the code. I assume eventually there will be a round of changes to support 64-bit values, so this anticipates that.

I could change it to be an unknown flag, rather assuming -1, but in an earlier draft I was printing -1 in the rev-list output. I can change this.

WRT a separate structure, the SET I create will contain entries for items where we may or may not know the size and that depends on the context. When building a list of already-missing blobs (with the --filter-print-missing) we never know the size. But when building a list of to-be-omitted blobs (from the current set of filter options), we may or may not know. I'm not sure we need 2 _entry definitions right now.

From: Jeff Hostetler <[email protected]>

Create traverse_commit_list_filtered() and add filtering interface to allow certain objects to be omitted (not shown) during a traversal.

Update traverse_commit_list() to be a wrapper for the above.

Filtering will be used in a future commit by rev-list and pack-objects for narrow/partial clone/fetch to omit certain blobs from the output.

traverse_bitmap_commit_list() does not work with filtering. If a packfile bitmap is present, it will not be used.

---
 list-objects.c | 66 ++++++++++++++++++++++++++++++++++++++++++++--------------
 list-objects.h | 30 ++++++++++++++++++++++++++
 2 files changed, 80 insertions(+), 16 deletions(-)

index b3931fa..3e86008 100644
@@ -13,10 +13,13 @@ static void process_blob(struct rev_info *revs,
 			 show_object_fn show,
 			 struct strbuf *path,
 			 const char *name,
-			 void *cb_data)
+			 void *cb_data,
+			 filter_object_fn filter,
+			 void *filter_data)
 {
 	struct object *obj = &blob->object;
 	size_t pathlen;
+	list_objects_filter_result r = LOFR_MARK_SEEN | LOFR_SHOW;
 
 	if (!revs->blob_objects)
 		return;

@@ -24,11 +27,15 @@ static void process_blob(struct rev_info *revs,
 		die("bad blob object");
 	if (obj->flags & (UNINTERESTING | SEEN))
 		return;
-	obj->flags |= SEEN;
 
 	pathlen = path->len;
 	strbuf_addstr(path, name);
-	show(obj, path->buf, cb_data);
+	if (filter)
+		r = filter(LOFT_BLOB, obj, path->buf, &path->buf[pathlen], filter_data);
+	if (r & LOFR_MARK_SEEN)
+		obj->flags |= SEEN;
+	if (r & LOFR_SHOW)
+		show(obj, path->buf, cb_data);
 	strbuf_setlen(path, pathlen);
 }
 

@@ -69,7 +76,9 @@ static void process_tree(struct rev_info *revs,
 			 show_object_fn show,
 			 struct strbuf *base,
 			 const char *name,
-			 void *cb_data)
+			 void *cb_data,
+			 filter_object_fn filter,
+			 void *filter_data)
 {
 	struct object *obj = &tree->object;
 	struct tree_desc desc;

@@ -77,6 +86,7 @@ static void process_tree(struct rev_info *revs,
 	enum interesting match = revs->diffopt.pathspec.nr == 0 ?
 		all_entries_interesting: entry_not_interesting;
 	int baselen = base->len;
+	list_objects_filter_result r = LOFR_MARK_SEEN | LOFR_SHOW;
 
 	if (!revs->tree_objects)
 		return;

@@ -90,9 +100,13 @@ static void process_tree(struct rev_info *revs,
 		die("bad tree object %s", oid_to_hex(&obj->oid));
 	}
 
-	obj->flags |= SEEN;
 	strbuf_addstr(base, name);
-	show(obj, base->buf, cb_data);
+	if (filter)
+		r = filter(LOFT_BEGIN_TREE, obj, base->buf, &base->buf[baselen], filter_data);
+	if (r & LOFR_MARK_SEEN)
+		obj->flags |= SEEN;
+	if (r & LOFR_SHOW)
+		show(obj, base->buf, cb_data);
 	if (base->len)
 		strbuf_addch(base, '/');
 

@@ -112,7 +126,7 @@ static void process_tree(struct rev_info *revs,
 			process_tree(revs,
 				     lookup_tree(entry.oid),
 				     show, base, entry.path,
-				     cb_data);
+				     cb_data, filter, filter_data);
 		else if (S_ISGITLINK(entry.mode))
 			process_gitlink(revs, entry.oid->hash,
 					show, base, entry.path,

@@ -121,8 +135,17 @@ static void process_tree(struct rev_info *revs,
 			process_blob(revs,
 				     lookup_blob(entry.oid),
 				     show, base, entry.path,
-				     cb_data);
+				     cb_data, filter, filter_data);
 	}
+
+	if (filter) {
+		r = filter(LOFT_END_TREE, obj, base->buf, &base->buf[baselen], filter_data);
+		if (r & LOFR_MARK_SEEN)
+			obj->flags |= SEEN;
+		if (r & LOFR_SHOW)
+			show(obj, base->buf, cb_data);
+	}
+
 	strbuf_setlen(base, baselen);
 	free_tree_buffer(tree);
 }

@@ -183,10 +206,10 @@ static void add_pending_tree(struct rev_info *revs, struct tree *tree)
 	add_pending_object(revs, &tree->object, "");
 }
 
-void traverse_commit_list(struct rev_info *revs,
-			  show_commit_fn show_commit,
-			  show_object_fn show_object,
-			  void *data)
+void traverse_commit_list_worker(
+	struct rev_info *revs,
+	show_commit_fn show_commit, show_object_fn show_object, void *show_data,
+	filter_object_fn filter, void *filter_data)
 {
 	int i;
 	struct commit *commit;

@@ -200,7 +223,7 @@ void traverse_commit_list(struct rev_info *revs,
 		 */
 		if (commit->tree)
 			add_pending_tree(revs, commit->tree);
-		show_commit(commit, data);
+		show_commit(commit, show_data);
 	}
 	for (i = 0; i < revs->pending.nr; i++) {
 		struct object_array_entry *pending = revs->pending.objects + i;

@@ -211,19 +234,19 @@ void traverse_commit_list(struct rev_info *revs,
 			continue;
 		if (obj->type == OBJ_TAG) {
 			obj->flags |= SEEN;
-			show_object(obj, name, data);
+			show_object(obj, name, show_data);
 			continue;
 		}
 		if (!path)
 			path = "";
 		if (obj->type == OBJ_TREE) {
 			process_tree(revs, (struct tree *)obj, show_object,
-				     &base, path, data);
+				     &base, path, show_data, filter, filter_data);
 			continue;
 		}
 		if (obj->type == OBJ_BLOB) {
 			process_blob(revs, (struct blob *)obj, show_object,
-				     &base, path, data);
+				     &base, path, show_data, filter, filter_data);
 			continue;
 		}
 		die("unknown pending object %s (%s)",

@@ -232,3 +255,14 @@ void traverse_commit_list(struct rev_info *revs,
 	object_array_clear(&revs->pending);
 	strbuf_release(&base);
 }
+
+void traverse_commit_list(struct rev_info *revs,
+			  show_commit_fn show_commit,
+			  show_object_fn show_object,
+			  void *show_data)
+{
+	traverse_commit_list_worker(
+		revs,
+		show_commit, show_object, show_data,
+		NULL, NULL);
+}

index 0cebf85..39fcbb5 100644
@@ -8,4 +8,34 @@ void traverse_commit_list(struct rev_info *, show_commit_fn, show_object_fn, voi
 typedef void (*show_edge_fn)(struct commit *);
 void mark_edges_uninteresting(struct rev_info *, show_edge_fn);
 
+enum list_objects_filter_result {
+	LOFR_ZERO      = 0,
+	LOFR_MARK_SEEN = 1<<0,
+	LOFR_SHOW      = 1<<1,
+};
+
+/* See object.h and revision.h */
+#define FILTER_REVISIT (1<<25)
+
+enum list_objects_filter_type {
+	LOFT_BEGIN_TREE,
+	LOFT_END_TREE,
+	LOFT_BLOB
+};
+
+typedef enum list_objects_filter_result list_objects_filter_result;
+typedef enum list_objects_filter_type list_objects_filter_type;
+
+typedef list_objects_filter_result (*filter_object_fn)(
+	list_objects_filter_type filter_type,
+	struct object *obj,
+	const char *pathname,
+	const char *filename,
+	void *filter_data);
+
+void traverse_commit_list_worker(
+	struct rev_info *,
+	show_commit_fn, show_object_fn, void *show_data,
+	filter_object_fn filter, void *filter_data);
+
 #endif

2.9.3

You mention _filtered() here, but this patch contains _worker().

thanks.

I wanted the filtering function to be independent of the showing function. As you can see in pack-objects.c and rev-list.c: All I needed to change there was to call the new version of the traverse code and not alter the show function. The filtering is completely isolated inside the traverse code.

It also means that the filtering code can do higher-level filtering. Currently, the show-object callback gets called with each terminal node (blob) and it has already lost any chance for tree-level optimizations. The filtering code participates in the treewalk on the commit and can do subtree elimination.

The sparse filter is looking at pathnames and using the same rules as sparse-checkout to decide which to *include* in the result. This is essentially backwards from the other filters which are looking for reasons to *exclude* a blob. If I see a {pathname, sha} pair and the pathname is not wanted (by the sparse-checkout rules), I still don't know anything about the object -- since the same SHA may appear later in the treewalk but with a different pathname that *does* match the patterns and *is* wanted.

The net-net is that I have to mark the blob as "provisionally omitted" until I've seen all the pathnames associated with it. Only then can I say it should be omitted.

Likewise, there are things about the tree object that we cannot decide until we've seen all possible directory paths that reference it. For example, if you rename a tree/directory between 2 commits, but make no other changes within the directory, it will/should have the same SHA in the second commit. If one of those paths is included in the sparse-checkout and one is not, then you need include those blobs (and the tree object) in the result. If the treewalk visits the excluded case first, you don't want to discard the tree object (and shortcut future treewalks) because the filter won't get a chance to see the included directory path case.

Also, the current code does not attempt to omit tree objects, but a future version may. And having the _BEGIN_ and _END_ events means the filter can keep track of the nesting without the expense of having to discover it by parsing the pathname looking for slashes as we do elsewhere.

right. thanks.

How is this different from refraining from marking the blob as LOFR_MARK_SEEN? When you would provisionally omit the blob, return LOFR_ZERO so that a future iteration will revisit the blob again, and when you would include it in the output, return LOFR_MARK_SEEN|LOFR_SHOW.

For trees, I guess it's slightly different in that you do need an extra flag to keep track of whether the tree has been shown. So mark SHOWN and return LOFR_SHOW on the first time the tree is shown, and LOFR_ZERO otherwise. And trees must never be marked as LOFR_MARK_SEEN.

(This SHOWN flag might play a similar role to your FILTER_REVISIT.)

Until now, it seems to me that the _END event is not required.

A feature that omits tree objects would need _END, true. But until then, I personally don't think we should add such infrastructure until we have a feature that needs it.

By adding it to the set of provisionally omitted objects, we have the option to capture a little extra information with it and refer to that the next time we see the object in the traversal. For example, in the sparse-checkout case, the first time we see the object we know the pathname and know that it does not need to be included. The second time we see that object, we can see if the new pathname is the same as the previous one with a simple strcmp and avoid the expensive is_excluded_from_list() computation. Keep in mind that rev-list or pack-objects could be called be on something like HEAD~100000..HEAD or that there may be 50,000 tips. So a file that doesn't change across that range will be visited many times with the same {pathname, sha}.

Then when the traversal is finished, we have a resulting set of (now actually) omitted objects. Which we can iterate over if the caller is interested in.

Right now I want to force the tree to be shown the first time it is visited (because I don't want to do tree filtering yet). I don't mark it SEEN yet because we may want to revisit blobs within (say, after a folder rename like I described previously).

I do, however, mark the tree object as SEEN (in the _END event) when I can verify that I've included ALL of the children.

So it might be possible that I could change the flags and not use FILTER_REVISIT on tree objects, I hesitate to do that right now.

Having the FILTER_REVISIT flag on blob objects means I can avoid doing a hash/oidset lookup on subsequent visits.

The sparse filter is using the _END now to try to help shortcut the treewalk (when all referenced objects within it are known to already be included).

The _END event's role may expand with a 4th filter that also filters tree objects, but I don't want to eliminate it right now.

Thanks
Jeff

Ah, capturing the extra information makes sense. I missed that detail.

This optimization makes sense too.

You're probably right that we need some sort of flag on tree objects, and FILTER_REVISIT can do the job. (My suggestion SHOWN plays a similar role anyway.)

By the hash/oidset lookup, I presume you mean the lookup on the set of provisionally omitted objects? If yes, this makes sense.

Thanks for your clarifications - I'll take another look at the code here.

From: Jeff Hostetler <[email protected]>

Create a simple filter for traverse_commit_list_worker() to omit all blobs from the result.

This filter will be used in a future commit by rev-list and pack-objects to create a "commits and trees" result. This is intended for partial clone and fetch support.

---
 Makefile                  |  1 +
 list-objects-filter-all.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++
 list-objects-filter-all.h | 18 ++++++++++
 3 files changed, 104 insertions(+)
 create mode 100644 list-objects-filter-all.c
 create mode 100644 list-objects-filter-all.h

index 4e0cc39..b98e3dc 100644
@@ -798,6 +798,7 @@ LIB_OBJS += levenshtein.o
 LIB_OBJS += line-log.o
 LIB_OBJS += line-range.o
 LIB_OBJS += list-objects.o
+LIB_OBJS += list-objects-filter-all.o
 LIB_OBJS += ll-merge.o
 LIB_OBJS += lockfile.o
 LIB_OBJS += log-tree.o

new file mode 100644
index 0000000..591589f
@@ -0,0 +1,18 @@
+#ifndef LIST_OBJECTS_FILTER_ALL_H
+#define LIST_OBJECTS_FILTER_ALL_H
+
+#include "oidset2.h"
+
+/*
+ * A filter for list-objects to omit ALL blobs
+ * from the traversal.
+ */
+void traverse_commit_list_omit_all_blobs(
+	struct rev_info *revs,
+	show_commit_fn show_commit,
+	show_object_fn show_object,
+	oidset2_foreach_cb print_omitted_object,
+	void *ctx_data);
+
+#endif /* LIST_OBJECTS_FILTER_ALL_H */
+

2.9.3

Thanks, this last point seems useful.

I tried applying your patches and it doesn't apply cleanly on master. Could you try rebasing? In particular, the code references get_sha1_with_context(), which no longer exists (it was replaced with get_oid_with_context()).

I usually build and submit patches relative to the latest available tag (v2.14.1) rather than a moving target, but yeah I'll look thru the other comments and rebase it forward.

Thanks
Jeff

https://github.com/jeffhostetler/git/tree/core/rev_list_filtering

I rebased this branch onto a current master and fixed the get_sha1_with_context() problems.

Let me know if you have problems with it (or would prefer that I send it to the mailing list).

Jeff