4 * Hashing names in the index state
6 * Copyright (C) 2008 Linus Torvalds
9 #include "thread-utils.h"
12 struct hashmap_entry ent
;
13 struct dir_entry
*parent
;
16 char name
[FLEX_ARRAY
];
19 static int dir_entry_cmp(const void *unused_cmp_data
,
21 const void *entry_or_key
,
24 const struct dir_entry
*e1
= entry
;
25 const struct dir_entry
*e2
= entry_or_key
;
26 const char *name
= keydata
;
28 return e1
->namelen
!= e2
->namelen
|| strncasecmp(e1
->name
,
29 name
? name
: e2
->name
, e1
->namelen
);
32 static struct dir_entry
*find_dir_entry__hash(struct index_state
*istate
,
33 const char *name
, unsigned int namelen
, unsigned int hash
)
36 hashmap_entry_init(&key
.ent
, hash
);
37 key
.namelen
= namelen
;
38 return hashmap_get(&istate
->dir_hash
, &key
.ent
, name
);
41 static struct dir_entry
*find_dir_entry(struct index_state
*istate
,
42 const char *name
, unsigned int namelen
)
44 return find_dir_entry__hash(istate
, name
, namelen
, memihash(name
, namelen
));
47 static struct dir_entry
*hash_dir_entry(struct index_state
*istate
,
48 struct cache_entry
*ce
, int namelen
)
51 * Throw each directory component in the hash for quick lookup
52 * during a git status. Directory components are stored without their
53 * closing slash. Despite submodules being a directory, they never
54 * reach this point, because they are stored
55 * in index_state.name_hash (as ordinary cache_entries).
57 struct dir_entry
*dir
;
59 /* get length of parent directory */
60 while (namelen
> 0 && !is_dir_sep(ce
->name
[namelen
- 1]))
66 /* lookup existing entry for that directory */
67 dir
= find_dir_entry(istate
, ce
->name
, namelen
);
69 /* not found, create it and add to hash table */
70 FLEX_ALLOC_MEM(dir
, name
, ce
->name
, namelen
);
71 hashmap_entry_init(&dir
->ent
, memihash(ce
->name
, namelen
));
72 dir
->namelen
= namelen
;
73 hashmap_add(&istate
->dir_hash
, &dir
->ent
);
75 /* recursively add missing parent directories */
76 dir
->parent
= hash_dir_entry(istate
, ce
, namelen
);
81 static void add_dir_entry(struct index_state
*istate
, struct cache_entry
*ce
)
83 /* Add reference to the directory entry (and parents if 0). */
84 struct dir_entry
*dir
= hash_dir_entry(istate
, ce
, ce_namelen(ce
));
85 while (dir
&& !(dir
->nr
++))
89 static void remove_dir_entry(struct index_state
*istate
, struct cache_entry
*ce
)
92 * Release reference to the directory entry. If 0, remove and continue
93 * with parent directory.
95 struct dir_entry
*dir
= hash_dir_entry(istate
, ce
, ce_namelen(ce
));
96 while (dir
&& !(--dir
->nr
)) {
97 struct dir_entry
*parent
= dir
->parent
;
98 hashmap_remove(&istate
->dir_hash
, dir
, NULL
);
104 static void hash_index_entry(struct index_state
*istate
, struct cache_entry
*ce
)
106 if (ce
->ce_flags
& CE_HASHED
)
108 ce
->ce_flags
|= CE_HASHED
;
109 hashmap_entry_init(&ce
->ent
, memihash(ce
->name
, ce_namelen(ce
)));
110 hashmap_add(&istate
->name_hash
, &ce
->ent
);
113 add_dir_entry(istate
, ce
);
116 static int cache_entry_cmp(const void *unused_cmp_data
,
118 const void *entry_or_key
,
121 const struct cache_entry
*ce1
= entry
;
122 const struct cache_entry
*ce2
= entry_or_key
;
124 * For remove_name_hash, find the exact entry (pointer equality); for
125 * index_file_exists, find all entries with matching hash code and
126 * decide whether the entry matches in same_name.
128 return remove
? !(ce1
== ce2
) : 0;
131 static int lazy_try_threaded
= 1;
132 static int lazy_nr_dir_threads
;
135 * Set a minimum number of cache_entries that we will handle per
136 * thread and use that to decide how many threads to run (upto
137 * the number on the system).
139 * For guidance setting the lower per-thread bound, see:
140 * t/helper/test-lazy-init-name-hash --analyze
142 #define LAZY_THREAD_COST (2000)
145 * We use n mutexes to guard n partitions of the "istate->dir_hash"
146 * hashtable. Since "find" and "insert" operations will hash to a
147 * particular bucket and modify/search a single chain, we can say
148 * that "all chains mod n" are guarded by the same mutex -- rather
149 * than having a single mutex to guard the entire table. (This does
150 * require that we disable "rehashing" on the hashtable.)
152 * So, a larger value here decreases the probability of a collision
153 * and the time that each thread must wait for the mutex.
155 #define LAZY_MAX_MUTEX (32)
157 static pthread_mutex_t
*lazy_dir_mutex_array
;
160 * An array of lazy_entry items is used by the n threads in
161 * the directory parse (first) phase to (lock-free) store the
162 * intermediate results. These values are then referenced by
163 * the 2 threads in the second phase.
166 struct dir_entry
*dir
;
167 unsigned int hash_dir
;
168 unsigned int hash_name
;
172 * Decide if we want to use threads (if available) to load
173 * the hash tables. We set "lazy_nr_dir_threads" to zero when
174 * it is not worth it.
176 static int lookup_lazy_params(struct index_state
*istate
)
180 lazy_nr_dir_threads
= 0;
182 if (!lazy_try_threaded
)
186 * If we are respecting case, just use the original
187 * code to build the "istate->name_hash". We don't
188 * need the complexity here.
193 nr_cpus
= online_cpus();
197 if (istate
->cache_nr
< 2 * LAZY_THREAD_COST
)
200 if (istate
->cache_nr
< nr_cpus
* LAZY_THREAD_COST
)
201 nr_cpus
= istate
->cache_nr
/ LAZY_THREAD_COST
;
202 lazy_nr_dir_threads
= nr_cpus
;
203 return lazy_nr_dir_threads
;
207 * Initialize n mutexes for use when searching and inserting
208 * into "istate->dir_hash". All "dir" threads are trying
209 * to insert partial pathnames into the hash as they iterate
210 * over their portions of the index, so lock contention is
213 * However, the hashmap is going to put items into bucket
214 * chains based on their hash values. Use that to create n
215 * mutexes and lock on mutex[bucket(hash) % n]. This will
216 * decrease the collision rate by (hopefully) by a factor of n.
218 static void init_dir_mutex(void)
222 lazy_dir_mutex_array
= xcalloc(LAZY_MAX_MUTEX
, sizeof(pthread_mutex_t
));
224 for (j
= 0; j
< LAZY_MAX_MUTEX
; j
++)
225 init_recursive_mutex(&lazy_dir_mutex_array
[j
]);
228 static void cleanup_dir_mutex(void)
232 for (j
= 0; j
< LAZY_MAX_MUTEX
; j
++)
233 pthread_mutex_destroy(&lazy_dir_mutex_array
[j
]);
235 free(lazy_dir_mutex_array
);
238 static void lock_dir_mutex(int j
)
240 pthread_mutex_lock(&lazy_dir_mutex_array
[j
]);
243 static void unlock_dir_mutex(int j
)
245 pthread_mutex_unlock(&lazy_dir_mutex_array
[j
]);
248 static inline int compute_dir_lock_nr(
249 const struct hashmap
*map
,
252 return hashmap_bucket(map
, hash
) % LAZY_MAX_MUTEX
;
255 static struct dir_entry
*hash_dir_entry_with_parent_and_prefix(
256 struct index_state
*istate
,
257 struct dir_entry
*parent
,
258 struct strbuf
*prefix
)
260 struct dir_entry
*dir
;
265 * Either we have a parent directory and path with slash(es)
266 * or the directory is an immediate child of the root directory.
268 assert((parent
!= NULL
) ^ (strchr(prefix
->buf
, '/') == NULL
));
271 hash
= memihash_cont(parent
->ent
.hash
,
272 prefix
->buf
+ parent
->namelen
,
273 prefix
->len
- parent
->namelen
);
275 hash
= memihash(prefix
->buf
, prefix
->len
);
277 lock_nr
= compute_dir_lock_nr(&istate
->dir_hash
, hash
);
278 lock_dir_mutex(lock_nr
);
280 dir
= find_dir_entry__hash(istate
, prefix
->buf
, prefix
->len
, hash
);
282 FLEX_ALLOC_MEM(dir
, name
, prefix
->buf
, prefix
->len
);
283 hashmap_entry_init(&dir
->ent
, hash
);
284 dir
->namelen
= prefix
->len
;
285 dir
->parent
= parent
;
286 hashmap_add(&istate
->dir_hash
, &dir
->ent
);
289 unlock_dir_mutex(lock_nr
);
291 /* All I really need here is an InterlockedIncrement(&(parent->nr)) */
292 lock_nr
= compute_dir_lock_nr(&istate
->dir_hash
, parent
->ent
.hash
);
293 lock_dir_mutex(lock_nr
);
298 unlock_dir_mutex(lock_nr
);
304 * handle_range_1() and handle_range_dir() are derived from
305 * clear_ce_flags_1() and clear_ce_flags_dir() in unpack-trees.c
306 * and handle the iteration over the entire array of index entries.
307 * They use recursion for adjacent entries in the same parent
310 static int handle_range_1(
311 struct index_state
*istate
,
314 struct dir_entry
*parent
,
315 struct strbuf
*prefix
,
316 struct lazy_entry
*lazy_entries
);
318 static int handle_range_dir(
319 struct index_state
*istate
,
322 struct dir_entry
*parent
,
323 struct strbuf
*prefix
,
324 struct lazy_entry
*lazy_entries
,
325 struct dir_entry
**dir_new_out
)
328 int input_prefix_len
= prefix
->len
;
329 struct dir_entry
*dir_new
;
331 dir_new
= hash_dir_entry_with_parent_and_prefix(istate
, parent
, prefix
);
333 strbuf_addch(prefix
, '/');
336 * Scan forward in the index array for index entries having the same
337 * path prefix (that are also in this directory).
339 if (k_start
+ 1 >= k_end
)
341 else if (strncmp(istate
->cache
[k_start
+ 1]->name
, prefix
->buf
, prefix
->len
) > 0)
343 else if (strncmp(istate
->cache
[k_end
- 1]->name
, prefix
->buf
, prefix
->len
) == 0)
349 while (begin
< end
) {
350 int mid
= begin
+ ((end
- begin
) >> 1);
351 int cmp
= strncmp(istate
->cache
[mid
]->name
, prefix
->buf
, prefix
->len
);
352 if (cmp
== 0) /* mid has same prefix; look in second part */
354 else if (cmp
> 0) /* mid is past group; look in first part */
357 die("cache entry out of order");
363 * Recurse and process what we can of this subset [k_start, k).
365 rc
= handle_range_1(istate
, k_start
, k
, dir_new
, prefix
, lazy_entries
);
367 strbuf_setlen(prefix
, input_prefix_len
);
369 *dir_new_out
= dir_new
;
373 static int handle_range_1(
374 struct index_state
*istate
,
377 struct dir_entry
*parent
,
378 struct strbuf
*prefix
,
379 struct lazy_entry
*lazy_entries
)
381 int input_prefix_len
= prefix
->len
;
385 struct cache_entry
*ce_k
= istate
->cache
[k
];
386 const char *name
, *slash
;
388 if (prefix
->len
&& strncmp(ce_k
->name
, prefix
->buf
, prefix
->len
))
391 name
= ce_k
->name
+ prefix
->len
;
392 slash
= strchr(name
, '/');
395 int len
= slash
- name
;
397 struct dir_entry
*dir_new
;
399 strbuf_add(prefix
, name
, len
);
400 processed
= handle_range_dir(istate
, k
, k_end
, parent
, prefix
, lazy_entries
, &dir_new
);
403 strbuf_setlen(prefix
, input_prefix_len
);
407 strbuf_addch(prefix
, '/');
408 processed
= handle_range_1(istate
, k
, k_end
, dir_new
, prefix
, lazy_entries
);
410 strbuf_setlen(prefix
, input_prefix_len
);
415 * It is too expensive to take a lock to insert "ce_k"
416 * into "istate->name_hash" and increment the ref-count
417 * on the "parent" dir. So we defer actually updating
418 * permanent data structures until phase 2 (where we
419 * can change the locking requirements) and simply
420 * accumulate our current results into the lazy_entries
423 * We do not need to lock the lazy_entries array because
424 * we have exclusive access to the cells in the range
425 * [k_start,k_end) that this thread was given.
427 lazy_entries
[k
].dir
= parent
;
429 lazy_entries
[k
].hash_name
= memihash_cont(
431 ce_k
->name
+ parent
->namelen
,
432 ce_namelen(ce_k
) - parent
->namelen
);
433 lazy_entries
[k
].hash_dir
= parent
->ent
.hash
;
435 lazy_entries
[k
].hash_name
= memihash(ce_k
->name
, ce_namelen(ce_k
));
444 struct lazy_dir_thread_data
{
446 struct index_state
*istate
;
447 struct lazy_entry
*lazy_entries
;
452 static void *lazy_dir_thread_proc(void *_data
)
454 struct lazy_dir_thread_data
*d
= _data
;
455 struct strbuf prefix
= STRBUF_INIT
;
456 handle_range_1(d
->istate
, d
->k_start
, d
->k_end
, NULL
, &prefix
, d
->lazy_entries
);
457 strbuf_release(&prefix
);
461 struct lazy_name_thread_data
{
463 struct index_state
*istate
;
464 struct lazy_entry
*lazy_entries
;
467 static void *lazy_name_thread_proc(void *_data
)
469 struct lazy_name_thread_data
*d
= _data
;
472 for (k
= 0; k
< d
->istate
->cache_nr
; k
++) {
473 struct cache_entry
*ce_k
= d
->istate
->cache
[k
];
474 ce_k
->ce_flags
|= CE_HASHED
;
475 hashmap_entry_init(&ce_k
->ent
, d
->lazy_entries
[k
].hash_name
);
476 hashmap_add(&d
->istate
->name_hash
, &ce_k
->ent
);
482 static inline void lazy_update_dir_ref_counts(
483 struct index_state
*istate
,
484 struct lazy_entry
*lazy_entries
)
488 for (k
= 0; k
< istate
->cache_nr
; k
++) {
489 if (lazy_entries
[k
].dir
)
490 lazy_entries
[k
].dir
->nr
++;
494 static void threaded_lazy_init_name_hash(
495 struct index_state
*istate
)
501 struct lazy_entry
*lazy_entries
;
502 struct lazy_dir_thread_data
*td_dir
;
503 struct lazy_name_thread_data
*td_name
;
509 nr_each
= DIV_ROUND_UP(istate
->cache_nr
, lazy_nr_dir_threads
);
511 lazy_entries
= xcalloc(istate
->cache_nr
, sizeof(struct lazy_entry
));
512 td_dir
= xcalloc(lazy_nr_dir_threads
, sizeof(struct lazy_dir_thread_data
));
513 td_name
= xcalloc(1, sizeof(struct lazy_name_thread_data
));
519 * Build "istate->dir_hash" using n "dir" threads (and a read-only index).
521 for (t
= 0; t
< lazy_nr_dir_threads
; t
++) {
522 struct lazy_dir_thread_data
*td_dir_t
= td_dir
+ t
;
523 td_dir_t
->istate
= istate
;
524 td_dir_t
->lazy_entries
= lazy_entries
;
525 td_dir_t
->k_start
= k_start
;
527 if (k_start
> istate
->cache_nr
)
528 k_start
= istate
->cache_nr
;
529 td_dir_t
->k_end
= k_start
;
530 err
= pthread_create(&td_dir_t
->pthread
, NULL
, lazy_dir_thread_proc
, td_dir_t
);
532 die(_("unable to create lazy_dir thread: %s"), strerror(err
));
534 for (t
= 0; t
< lazy_nr_dir_threads
; t
++) {
535 struct lazy_dir_thread_data
*td_dir_t
= td_dir
+ t
;
536 if (pthread_join(td_dir_t
->pthread
, NULL
))
537 die("unable to join lazy_dir_thread");
542 * Iterate over all index entries and add them to the "istate->name_hash"
543 * using a single "name" background thread.
544 * (Testing showed it wasn't worth running more than 1 thread for this.)
546 * Meanwhile, finish updating the parent directory ref-counts for each
547 * index entry using the current thread. (This step is very fast and
548 * doesn't need threading.)
550 td_name
->istate
= istate
;
551 td_name
->lazy_entries
= lazy_entries
;
552 err
= pthread_create(&td_name
->pthread
, NULL
, lazy_name_thread_proc
, td_name
);
554 die(_("unable to create lazy_name thread: %s"), strerror(err
));
556 lazy_update_dir_ref_counts(istate
, lazy_entries
);
558 err
= pthread_join(td_name
->pthread
, NULL
);
560 die(_("unable to join lazy_name thread: %s"), strerror(err
));
569 static void lazy_init_name_hash(struct index_state
*istate
)
572 if (istate
->name_hash_initialized
)
574 trace_performance_enter();
575 hashmap_init(&istate
->name_hash
, cache_entry_cmp
, NULL
, istate
->cache_nr
);
576 hashmap_init(&istate
->dir_hash
, dir_entry_cmp
, NULL
, istate
->cache_nr
);
578 if (lookup_lazy_params(istate
)) {
580 * Disable item counting and automatic rehashing because
581 * we do per-chain (mod n) locking rather than whole hashmap
582 * locking and we need to prevent the table-size from changing
583 * and bucket items from being redistributed.
585 hashmap_disable_item_counting(&istate
->dir_hash
);
586 threaded_lazy_init_name_hash(istate
);
587 hashmap_enable_item_counting(&istate
->dir_hash
);
590 for (nr
= 0; nr
< istate
->cache_nr
; nr
++)
591 hash_index_entry(istate
, istate
->cache
[nr
]);
594 istate
->name_hash_initialized
= 1;
595 trace_performance_leave("initialize name hash");
599 * A test routine for t/helper/ sources.
601 * Returns the number of threads used or 0 when
602 * the non-threaded code path was used.
604 * Requesting threading WILL NOT override guards
605 * in lookup_lazy_params().
607 int test_lazy_init_name_hash(struct index_state
*istate
, int try_threaded
)
609 lazy_nr_dir_threads
= 0;
610 lazy_try_threaded
= try_threaded
;
612 lazy_init_name_hash(istate
);
614 return lazy_nr_dir_threads
;
617 void add_name_hash(struct index_state
*istate
, struct cache_entry
*ce
)
619 if (istate
->name_hash_initialized
)
620 hash_index_entry(istate
, ce
);
623 void remove_name_hash(struct index_state
*istate
, struct cache_entry
*ce
)
625 if (!istate
->name_hash_initialized
|| !(ce
->ce_flags
& CE_HASHED
))
627 ce
->ce_flags
&= ~CE_HASHED
;
628 hashmap_remove(&istate
->name_hash
, ce
, ce
);
631 remove_dir_entry(istate
, ce
);
634 static int slow_same_name(const char *name1
, int len1
, const char *name2
, int len2
)
640 unsigned char c1
= *name1
++;
641 unsigned char c2
= *name2
++;
653 static int same_name(const struct cache_entry
*ce
, const char *name
, int namelen
, int icase
)
655 int len
= ce_namelen(ce
);
658 * Always do exact compare, even if we want a case-ignoring comparison;
659 * we do the quick exact one first, because it will be the common case.
661 if (len
== namelen
&& !memcmp(name
, ce
->name
, len
))
667 return slow_same_name(name
, namelen
, ce
->name
, len
);
670 int index_dir_exists(struct index_state
*istate
, const char *name
, int namelen
)
672 struct dir_entry
*dir
;
674 lazy_init_name_hash(istate
);
675 dir
= find_dir_entry(istate
, name
, namelen
);
676 return dir
&& dir
->nr
;
679 void adjust_dirname_case(struct index_state
*istate
, char *name
)
681 const char *startPtr
= name
;
682 const char *ptr
= startPtr
;
684 lazy_init_name_hash(istate
);
686 while (*ptr
&& *ptr
!= '/')
690 struct dir_entry
*dir
;
692 dir
= find_dir_entry(istate
, name
, ptr
- name
);
694 memcpy((void *)startPtr
, dir
->name
+ (startPtr
- name
), ptr
- startPtr
);
702 struct cache_entry
*index_file_exists(struct index_state
*istate
, const char *name
, int namelen
, int icase
)
704 struct cache_entry
*ce
;
706 lazy_init_name_hash(istate
);
708 ce
= hashmap_get_from_hash(&istate
->name_hash
,
709 memihash(name
, namelen
), NULL
);
711 if (same_name(ce
, name
, namelen
, icase
))
713 ce
= hashmap_get_next(&istate
->name_hash
, &ce
->ent
);
718 void free_name_hash(struct index_state
*istate
)
720 if (!istate
->name_hash_initialized
)
722 istate
->name_hash_initialized
= 0;
724 hashmap_free(&istate
->name_hash
, 0);
725 hashmap_free(&istate
->dir_hash
, 1);