Re: [PATCH v2 1/4] odb: decouple source path comparisons from `the_repository`

Karthik Nayak <[email protected]> Thu, 13 Aug 2026 05:23:39 -0700
Newsgroups	org.kernel.vger.git
Message-ID	<CAOLa=ZTsumAT6U8+pJQmNjYL6Rt=JkvTJ0V7KQ7MvLYkThTFYA@mail.gmail.com>
Patrick Steinhardt <[email protected]> writes:

> When registering alternates we deduplicate object database sources by
> their path so that the same source won't be added twice. Ever since
> cf2dc1c238 (speed up alt_odb_usable() with many alternates, 2021-07-07)
> this duplicate check is backed by a map keyed by the source's path,
> using `fspathhash()` and `fspatheq()` as hash and equality functions,
> respectively.
>
> These functions are problematic in this context for two reasons:
>
>   - They implicitly depend on `the_repository` instead of the
>     repository that owns the object database.
>
>   - They derive case-sensitivity from `repo_ignore_case()`, which
>     returns a default value in case the repository's configuration has
>     not been parsed yet. Object database sources may be registered
>     before that is the case, so the answer may flip depending on when a
>     source gets registered.
>
> Fix this by making the comparison self-contained in the object
> database. Instead of using `fspathhash()` and `fspatheq()` we resolve
> "core.ignoreCase" manually and then use the correct comparison function
> based on the result. This requires us to migrate to a `struct hashmap`,
> as the khash interface does not give us the ability to change these
> functions.
>
> Note that we can unconditionally use `strihash()` to compute entry
> hashes regardless of case sensitivity: a hash function only needs to
> guarantee that equal keys have equal hashes, and a case-insensitive
> hash satisfies this requirement for both case-sensitive and
> case-insensitive equality.
>
> Overall it's quite debatable whether all of this complexity really is
> worth it, or whether we should just linearly search through all sources
> to find duplicates. But the mentioned commit cares about cases with
> thousands of alternates, and a linear search would of course regress
> performance quite a bit. This doesn't really feel like a reasonable case
> to care about though, but I don't feel comfortable regressing it anyway.
>
> Signed-off-by: Patrick Steinhardt <[email protected]>
> ---
>  odb.c        | 63 ++++++++++++++++++++++++++++++++++++++++--------------------
>  odb.h        | 15 ++++++++++++++-
>  odb/source.h |  7 +++++++
>  3 files changed, 63 insertions(+), 22 deletions(-)
>
> diff --git a/odb.c b/odb.c
> index bd02d8ad54..51da386f22 100644
> --- a/odb.c
> +++ b/odb.c
> @@ -2,11 +2,10 @@
>  #include "abspath.h"
>  #include "commit-graph.h"
>  #include "config.h"
> -#include "dir.h"
>  #include "environment.h"
>  #include "gettext.h"
> +#include "hashmap.h"
>  #include "hex.h"
> -#include "khash.h"
>  #include "lockfile.h"
>  #include "loose.h"
>  #include "midx.h"
> @@ -29,8 +28,32 @@
>  #include "trace2.h"
>  #include "write-or-die.h"
>
> -KHASH_INIT(odb_path_map, const char * /* key: odb_path */,
> -	struct odb_source *, 1, fspathhash, fspatheq)
> +static int odb_source_paths_cmp(struct object_database *o,
> +				const char *a, const char *b)
> +{
> +	if (o->source_paths_icase < 0) {
> +		int icase = 0;
> +		repo_config_get_bool(o->repo, "core.ignorecase", &icase);
> +		o->source_paths_icase = icase;
> +	}
> +

Nit: couldn't this be simplified to

if (o->source_paths_icase < 0)
   repo_config_get_bool(o->repo, "core.ignorecase", &o->source_paths_icase);

> +	return o->source_paths_icase ? strcasecmp(a, b) : strcmp(a, b);
> +}
> +
> +static int odb_source_by_path_cmp(const void *cb_data,
> +				  const struct hashmap_entry *entry,
> +				  const struct hashmap_entry *entry_or_key,
> +				  const void *keydata)
> +{
> +	struct object_database *o = (struct object_database *)cb_data;
> +	const struct odb_source *source = container_of(entry, const struct odb_source, by_path_entry);
> +	const char *path = keydata;
> +
> +	if (!path)
> +		path = container_of(entry_or_key, const struct odb_source, by_path_entry)->path;
> +
> +	return odb_source_paths_cmp(o, source->path, path);
> +}
>
>  int odb_mkstemp(struct object_database *odb,
>  		struct strbuf *temp_filename, const char *pattern)
> @@ -58,8 +81,8 @@ int odb_mkstemp(struct object_database *odb,
>   */
>  static bool odb_is_source_usable(struct object_database *o, const char *path)
>  {
> -	int r;
>  	struct strbuf normalized_objdir = STRBUF_INIT;
> +	struct hashmap_entry key;
>  	bool usable = false;
>
>  	strbuf_realpath(&normalized_objdir, o->sources->path, 1);
> @@ -76,20 +99,18 @@ static bool odb_is_source_usable(struct object_database *o, const char *path)
>  	 * Prevent the common mistake of listing the same
>  	 * thing twice, or object directory itself.
>  	 */
> -	if (!o->source_by_path) {
> -		khiter_t p;
> -
> -		o->source_by_path = kh_init_odb_path_map();
> +	if (!hashmap_get_size(&o->source_by_path)) {
>  		assert(!o->sources->next);
> -		p = kh_put_odb_path_map(o->source_by_path, o->sources->path, &r);
> -		assert(r == 1); /* never used */
> -		kh_value(o->source_by_path, p) = o->sources;
> +		hashmap_entry_init(&o->sources->by_path_entry,
> +				   strihash(o->sources->path));
> +		hashmap_add(&o->source_by_path, &o->sources->by_path_entry);
>  	}
>
> -	if (fspatheq(path, normalized_objdir.buf))
> +	if (!odb_source_paths_cmp(o, path, normalized_objdir.buf))
>  		goto out;
>
> -	if (kh_get_odb_path_map(o->source_by_path, path) < kh_end(o->source_by_path))
> +	hashmap_entry_init(&key, strihash(path));
> +	if (hashmap_get(&o->source_by_path, &key, path))
>  		goto out;
>
>  	usable = true;
> @@ -172,8 +193,6 @@ static struct odb_source *odb_add_alternate_recursively(struct object_database *
>  {
>  	struct odb_source *alternate = NULL;
>  	struct strvec sources = STRVEC_INIT;
> -	khiter_t pos;
> -	int ret;
>
>  	if (!odb_is_source_usable(odb, source))
>  		goto error;
> @@ -184,10 +203,11 @@ static struct odb_source *odb_add_alternate_recursively(struct object_database *
>  	*odb->sources_tail = alternate;
>  	odb->sources_tail = &(alternate->next);
>
> -	pos = kh_put_odb_path_map(odb->source_by_path, alternate->path, &ret);
> -	if (!ret)
> +	hashmap_entry_init(&alternate->by_path_entry, strihash(alternate->path));
> +	if (hashmap_get(&odb->source_by_path, &alternate->by_path_entry,
> +			alternate->path))
>  		BUG("source must not yet exist");
> -	kh_value(odb->source_by_path, pos) = alternate;
> +	hashmap_add(&odb->source_by_path, &alternate->by_path_entry);
>
>  	/* recursively add alternates */
>  	odb_source_read_alternates(alternate, &sources);
> @@ -1056,6 +1076,8 @@ struct object_database *odb_new(struct repository *repo,
>  	o->repo = repo;
>  	pthread_mutex_init(&o->replace_mutex, NULL);
>  	string_list_init_dup(&o->submodule_source_paths);
> +	hashmap_init(&o->source_by_path, odb_source_by_path_cmp, o, 0);
> +	o->source_paths_icase = -1;
>
>  	if (flags & ODB_NEW_HONOR_ENV) {
>  		primary_source = xstrdup_or_null(getenv(DB_ENVIRONMENT));
> @@ -1094,8 +1116,7 @@ static void odb_free_sources(struct object_database *o)
>  	odb_source_free(o->inmemory_objects);
>  	o->inmemory_objects = NULL;
>
> -	kh_destroy_odb_path_map(o->source_by_path);
> -	o->source_by_path = NULL;
> +	hashmap_clear(&o->source_by_path);
>  }
>
>  void odb_free(struct object_database *o)
> diff --git a/odb.h b/odb.h
> index 8eb4e85d64..71af7450a9 100644
> --- a/odb.h
> +++ b/odb.h
> @@ -1,6 +1,7 @@
>  #ifndef ODB_H
>  #define ODB_H
>
> +#include "hashmap.h"
>  #include "object.h"
>  #include "oidset.h"
>  #include "oidmap.h"
> @@ -54,7 +55,19 @@ struct object_database {
>  	 */
>  	struct odb_source *sources;
>  	struct odb_source **sources_tail;
> -	struct kh_odb_path_map *source_by_path;
> +
> +	/*
> +	 * Map of object database sources, keyed by their respective paths.
> +	 * This map is used to detect the case where the same source is
> +	 * registered multiple times.
> +	 */
> +	struct hashmap source_by_path;
> +
> +	/*
> +	 * Whether source paths shall be compared case-insensitively, as
> +	 * determined by "core.ignoreCase".
> +	 */
> +	int source_paths_icase;
>
>  	int loaded_alternates;
>
> diff --git a/odb/source.h b/odb/source.h
> index 4bc037b8d6..82cda8ad75 100644
> --- a/odb/source.h
> +++ b/odb/source.h
> @@ -1,6 +1,7 @@
>  #ifndef ODB_SOURCE_H
>  #define ODB_SOURCE_H
>
> +#include "hashmap.h"
>  #include "object.h"
>  #include "odb.h"
>  #include "odb/transaction.h"
> @@ -50,6 +51,12 @@ struct strvec;
>  struct odb_source {
>  	struct odb_source *next;
>
> +	/*
> +	 * Entry in the object database's map of sources, keyed by this
> +	 * source's path.
> +	 */
> +	struct hashmap_entry by_path_entry;
> +
>  	/* Object database that owns this object source. */
>  	struct object_database *odb;
>
>
> --
> 2.55.0.679.g6767b8d81c.dirty

Apart from the nit, this patch looks good.
signature.asc (application/pgp-signature, 690 B)