git/name-hash.c

/*
 * name-hash.c
 *
 * Hashing names in the index state
 *
 * Copyright (C) 2008 Linus Torvalds
 */

#define USE_THE_REPOSITORY_VARIABLE

#include "git-compat-util.h"
#include "environment.h"
#include "gettext.h"
#include "name-hash.h"
#include "object.h"
#include "read-cache-ll.h"
#include "thread-utils.h"
#include "trace.h"
#include "trace2.h"
#include "sparse-index.h"

struct dir_entry { … };

static int dir_entry_cmp(const void *cmp_data UNUSED,
			 const struct hashmap_entry *eptr,
			 const struct hashmap_entry *entry_or_key,
			 const void *keydata)
{ … }

static struct dir_entry *find_dir_entry__hash(struct index_state *istate,
		const char *name, unsigned int namelen, unsigned int hash)
{ … }

static struct dir_entry *find_dir_entry(struct index_state *istate,
		const char *name, unsigned int namelen)
{ … }

static struct dir_entry *hash_dir_entry(struct index_state *istate,
		struct cache_entry *ce, int namelen)
{ … }

static void add_dir_entry(struct index_state *istate, struct cache_entry *ce)
{ … }

static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)
{ … }

static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
{ … }

static int cache_entry_cmp(const void *cmp_data UNUSED,
			   const struct hashmap_entry *eptr,
			   const struct hashmap_entry *entry_or_key,
			   const void *remove)
{ … }

static int lazy_try_threaded = …;
static int lazy_nr_dir_threads;

/*
 * Set a minimum number of cache_entries that we will handle per
 * thread and use that to decide how many threads to run (up to
 * the number on the system).
 *
 * For guidance setting the lower per-thread bound, see:
 *     t/helper/test-lazy-init-name-hash --analyze
 */
#define LAZY_THREAD_COST …

/*
 * We use n mutexes to guard n partitions of the "istate->dir_hash"
 * hashtable.  Since "find" and "insert" operations will hash to a
 * particular bucket and modify/search a single chain, we can say
 * that "all chains mod n" are guarded by the same mutex -- rather
 * than having a single mutex to guard the entire table.  (This does
 * require that we disable "rehashing" on the hashtable.)
 *
 * So, a larger value here decreases the probability of a collision
 * and the time that each thread must wait for the mutex.
 */
#define LAZY_MAX_MUTEX …

static pthread_mutex_t *lazy_dir_mutex_array;

/*
 * An array of lazy_entry items is used by the n threads in
 * the directory parse (first) phase to (lock-free) store the
 * intermediate results.  These values are then referenced by
 * the 2 threads in the second phase.
 */
struct lazy_entry { … };

/*
 * Decide if we want to use threads (if available) to load
 * the hash tables.  We set "lazy_nr_dir_threads" to zero when
 * it is not worth it.
 */
static int lookup_lazy_params(struct index_state *istate)
{ … }

/*
 * Initialize n mutexes for use when searching and inserting
 * into "istate->dir_hash".  All "dir" threads are trying
 * to insert partial pathnames into the hash as they iterate
 * over their portions of the index, so lock contention is
 * high.
 *
 * However, the hashmap is going to put items into bucket
 * chains based on their hash values.  Use that to create n
 * mutexes and lock on mutex[bucket(hash) % n].  This will
 * decrease the collision rate by (hopefully) a factor of n.
 */
static void init_dir_mutex(void)
{ … }

static void cleanup_dir_mutex(void)
{ … }

static void lock_dir_mutex(int j)
{ … }

static void unlock_dir_mutex(int j)
{ … }

static inline int compute_dir_lock_nr(
	const struct hashmap *map,
	unsigned int hash)
{ … }

static struct dir_entry *hash_dir_entry_with_parent_and_prefix(
	struct index_state *istate,
	struct dir_entry *parent,
	struct strbuf *prefix)
{ … }

/*
 * handle_range_1() and handle_range_dir() are derived from
 * clear_ce_flags_1() and clear_ce_flags_dir() in unpack-trees.c
 * and handle the iteration over the entire array of index entries.
 * They use recursion for adjacent entries in the same parent
 * directory.
 */
static int handle_range_1(
	struct index_state *istate,
	int k_start,
	int k_end,
	struct dir_entry *parent,
	struct strbuf *prefix,
	struct lazy_entry *lazy_entries);

static int handle_range_dir(
	struct index_state *istate,
	int k_start,
	int k_end,
	struct dir_entry *parent,
	struct strbuf *prefix,
	struct lazy_entry *lazy_entries,
	struct dir_entry **dir_new_out)
{ … }

static int handle_range_1(
	struct index_state *istate,
	int k_start,
	int k_end,
	struct dir_entry *parent,
	struct strbuf *prefix,
	struct lazy_entry *lazy_entries)
{ … }

struct lazy_dir_thread_data { … };

static void *lazy_dir_thread_proc(void *_data)
{ … }

struct lazy_name_thread_data { … };

static void *lazy_name_thread_proc(void *_data)
{ … }

static inline void lazy_update_dir_ref_counts(
	struct index_state *istate,
	struct lazy_entry *lazy_entries)
{ … }

static void threaded_lazy_init_name_hash(
	struct index_state *istate)
{ … }

static void lazy_init_name_hash(struct index_state *istate)
{ … }

/*
 * A test routine for t/helper/ sources.
 *
 * Returns the number of threads used or 0 when
 * the non-threaded code path was used.
 *
 * Requesting threading WILL NOT override guards
 * in lookup_lazy_params().
 */
int test_lazy_init_name_hash(struct index_state *istate, int try_threaded)
{ … }

void add_name_hash(struct index_state *istate, struct cache_entry *ce)
{ … }

void remove_name_hash(struct index_state *istate, struct cache_entry *ce)
{ … }

static int slow_same_name(const char *name1, int len1, const char *name2, int len2)
{ … }

static int same_name(const struct cache_entry *ce, const char *name, int namelen, int icase)
{ … }

int index_dir_find(struct index_state *istate, const char *name, int namelen,
		   struct strbuf *canonical_path)
{ … }

void adjust_dirname_case(struct index_state *istate, char *name)
{ … }

struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase)
{ … }

void free_name_hash(struct index_state *istate)
{ … }