From: Junio C Hamano Date: Thu, 25 Jul 2019 21:27:12 +0000 (-0700) Subject: Merge branch 'md/list-objects-filter-memfix' into maint X-Git-Tag: v2.23.0-rc0~6^2~9 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/43f40de9409111a86d5a8d5c9d3f4b9415a05f8f?ds=inline;hp=-c Merge branch 'md/list-objects-filter-memfix' into maint The filter_data used in the list-objects-filter (which manages a lazily sparse clone repository) did not use the dynamic array API correctly---'nr' is supposed to point at one past the last element of the array in use. This has been corrected. * md/list-objects-filter-memfix: list-objects-filter: correct usage of ALLOC_GROW --- 43f40de9409111a86d5a8d5c9d3f4b9415a05f8f diff --combined list-objects-filter.c index 53f90442c5,7824a480e1..36e1f774bc --- a/list-objects-filter.c +++ b/list-objects-filter.c @@@ -10,7 -10,6 +10,7 @@@ #include "list-objects.h" #include "list-objects-filter.h" #include "list-objects-filter-options.h" +#include "oidmap.h" #include "oidset.h" #include "object-store.h" @@@ -35,7 -34,6 +35,7 @@@ struct filter_blobs_none_data }; static enum list_objects_filter_result filter_blobs_none( + struct repository *r, enum list_objects_filter_situation filter_situation, struct object *obj, const char *pathname, @@@ -85,136 -83,54 +85,136 @@@ static void *filter_blobs_none__init * A filter for list-objects to omit ALL trees and blobs from the traversal. * Can OPTIONALLY collect a list of the omitted OIDs. */ -struct filter_trees_none_data { +struct filter_trees_depth_data { struct oidset *omits; + + /* + * Maps trees to the minimum depth at which they were seen. It is not + * necessary to re-traverse a tree at deeper or equal depths than it has + * already been traversed. + * + * We can't use LOFR_MARK_SEEN for tree objects since this will prevent + * it from being traversed at shallower depths. + */ + struct oidmap seen_at_depth; + + unsigned long exclude_depth; + unsigned long current_depth; +}; + +struct seen_map_entry { + struct oidmap_entry base; + size_t depth; }; -static enum list_objects_filter_result filter_trees_none( +/* Returns 1 if the oid was in the omits set before it was invoked. */ +static int filter_trees_update_omits( + struct object *obj, + struct filter_trees_depth_data *filter_data, + int include_it) +{ + if (!filter_data->omits) + return 0; + + if (include_it) + return oidset_remove(filter_data->omits, &obj->oid); + else + return oidset_insert(filter_data->omits, &obj->oid); +} + +static enum list_objects_filter_result filter_trees_depth( + struct repository *r, enum list_objects_filter_situation filter_situation, struct object *obj, const char *pathname, const char *filename, void *filter_data_) { - struct filter_trees_none_data *filter_data = filter_data_; + struct filter_trees_depth_data *filter_data = filter_data_; + struct seen_map_entry *seen_info; + int include_it = filter_data->current_depth < + filter_data->exclude_depth; + int filter_res; + int already_seen; + + /* + * Note that we do not use _MARK_SEEN in order to allow re-traversal in + * case we encounter a tree or blob again at a shallower depth. + */ switch (filter_situation) { default: BUG("unknown filter_situation: %d", filter_situation); - case LOFS_BEGIN_TREE: + case LOFS_END_TREE: + assert(obj->type == OBJ_TREE); + filter_data->current_depth--; + return LOFR_ZERO; + case LOFS_BLOB: - if (filter_data->omits) { - oidset_insert(filter_data->omits, &obj->oid); - /* _MARK_SEEN but not _DO_SHOW (hard omit) */ - return LOFR_MARK_SEEN; + filter_trees_update_omits(obj, filter_data, include_it); + return include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO; + + case LOFS_BEGIN_TREE: + seen_info = oidmap_get( + &filter_data->seen_at_depth, &obj->oid); + if (!seen_info) { + seen_info = xcalloc(1, sizeof(*seen_info)); + oidcpy(&seen_info->base.oid, &obj->oid); + seen_info->depth = filter_data->current_depth; + oidmap_put(&filter_data->seen_at_depth, seen_info); + already_seen = 0; } else { - /* - * Not collecting omits so no need to to traverse tree. - */ - return LOFR_SKIP_TREE | LOFR_MARK_SEEN; + already_seen = + filter_data->current_depth >= seen_info->depth; } - case LOFS_END_TREE: - assert(obj->type == OBJ_TREE); - return LOFR_ZERO; + if (already_seen) { + filter_res = LOFR_SKIP_TREE; + } else { + int been_omitted = filter_trees_update_omits( + obj, filter_data, include_it); + seen_info->depth = filter_data->current_depth; + + if (include_it) + filter_res = LOFR_DO_SHOW; + else if (filter_data->omits && !been_omitted) + /* + * Must update omit information of children + * recursively; they have not been omitted yet. + */ + filter_res = LOFR_ZERO; + else + filter_res = LOFR_SKIP_TREE; + } + filter_data->current_depth++; + return filter_res; } } -static void* filter_trees_none__init( +static void filter_trees_free(void *filter_data) { + struct filter_trees_depth_data *d = filter_data; + if (!d) + return; + oidmap_free(&d->seen_at_depth, 1); + free(d); +} + +static void *filter_trees_depth__init( struct oidset *omitted, struct list_objects_filter_options *filter_options, filter_object_fn *filter_fn, filter_free_fn *filter_free_fn) { - struct filter_trees_none_data *d = xcalloc(1, sizeof(*d)); + struct filter_trees_depth_data *d = xcalloc(1, sizeof(*d)); d->omits = omitted; + oidmap_init(&d->seen_at_depth, 0); + d->exclude_depth = filter_options->tree_exclude_depth; + d->current_depth = 0; - *filter_fn = filter_trees_none; - *filter_free_fn = free; + *filter_fn = filter_trees_depth; + *filter_free_fn = filter_trees_free; return d; } @@@ -228,7 -144,6 +228,7 @@@ struct filter_blobs_limit_data }; static enum list_objects_filter_result filter_blobs_limit( + struct repository *r, enum list_objects_filter_situation filter_situation, struct object *obj, const char *pathname, @@@ -256,7 -171,7 +256,7 @@@ assert(obj->type == OBJ_BLOB); assert((obj->flags & SEEN) == 0); - t = oid_object_info(the_repository, &obj->oid, &object_length); + t = oid_object_info(r, &obj->oid, &object_length); if (t != OBJ_BLOB) { /* probably OBJ_NONE */ /* * We DO NOT have the blob locally, so we cannot @@@ -334,7 -249,6 +334,7 @@@ struct filter_sparse_data }; static enum list_objects_filter_result filter_sparse( + struct repository *r, enum list_objects_filter_situation filter_situation, struct object *obj, const char *pathname, @@@ -354,15 -268,15 +354,15 @@@ dtype = DT_DIR; val = is_excluded_from_list(pathname, strlen(pathname), filename, &dtype, &filter_data->el, - &the_index); + r->index); if (val < 0) - val = filter_data->array_frame[filter_data->nr].defval; + val = filter_data->array_frame[filter_data->nr - 1].defval; ALLOC_GROW(filter_data->array_frame, filter_data->nr + 1, filter_data->alloc); - filter_data->nr++; filter_data->array_frame[filter_data->nr].defval = val; filter_data->array_frame[filter_data->nr].child_prov_omit = 0; + filter_data->nr++; /* * A directory with this tree OID may appear in multiple @@@ -387,16 -301,15 +387,15 @@@ case LOFS_END_TREE: assert(obj->type == OBJ_TREE); - assert(filter_data->nr > 0); + assert(filter_data->nr > 1); - frame = &filter_data->array_frame[filter_data->nr]; - filter_data->nr--; + frame = &filter_data->array_frame[--filter_data->nr]; /* * Tell our parent directory if any of our children were * provisionally omitted. */ - filter_data->array_frame[filter_data->nr].child_prov_omit |= + filter_data->array_frame[filter_data->nr - 1].child_prov_omit |= frame->child_prov_omit; /* @@@ -412,12 -325,12 +411,12 @@@ assert(obj->type == OBJ_BLOB); assert((obj->flags & SEEN) == 0); - frame = &filter_data->array_frame[filter_data->nr]; + frame = &filter_data->array_frame[filter_data->nr - 1]; dtype = DT_REG; val = is_excluded_from_list(pathname, strlen(pathname), filename, &dtype, &filter_data->el, - &the_index); + r->index); if (val < 0) val = frame->defval; if (val > 0) { @@@ -453,7 -366,7 +452,7 @@@ static void filter_sparse_free(void *filter_data) { struct filter_sparse_data *d = filter_data; - /* TODO free contents of 'd' */ + free(d->array_frame); free(d); } @@@ -472,12 -385,35 +471,13 @@@ static void *filter_sparse_oid__init ALLOC_GROW(d->array_frame, d->nr + 1, d->alloc); d->array_frame[d->nr].defval = 0; /* default to include */ d->array_frame[d->nr].child_prov_omit = 0; + d->nr++; *filter_fn = filter_sparse; *filter_free_fn = filter_sparse_free; return d; } -static void *filter_sparse_path__init( - struct oidset *omitted, - struct list_objects_filter_options *filter_options, - filter_object_fn *filter_fn, - filter_free_fn *filter_free_fn) -{ - struct filter_sparse_data *d = xcalloc(1, sizeof(*d)); - d->omits = omitted; - if (add_excludes_from_file_to_list(filter_options->sparse_path_value, - NULL, 0, &d->el, NULL) < 0) - die("could not load filter specification"); - - ALLOC_GROW(d->array_frame, d->nr + 1, d->alloc); - d->array_frame[d->nr].defval = 0; /* default to include */ - d->array_frame[d->nr].child_prov_omit = 0; - d->nr++; - - *filter_fn = filter_sparse; - *filter_free_fn = filter_sparse_free; - return d; -} - typedef void *(*filter_init_fn)( struct oidset *omitted, struct list_objects_filter_options *filter_options, @@@ -491,8 -427,9 +491,8 @@@ static filter_init_fn s_filters[] = NULL, filter_blobs_none__init, filter_blobs_limit__init, - filter_trees_none__init, + filter_trees_depth__init, filter_sparse_oid__init, - filter_sparse_path__init, }; void *list_objects_filter__init(