4 * Hashing names in the index state
6 * Copyright (C) 2008 Linus Torvalds
10 #include "thread-utils.h"
12 #include "sparse-index.h"
15 struct hashmap_entry ent
;
16 struct dir_entry
*parent
;
19 char name
[FLEX_ARRAY
];
22 static int dir_entry_cmp(const void *cmp_data UNUSED
,
23 const struct hashmap_entry
*eptr
,
24 const struct hashmap_entry
*entry_or_key
,
27 const struct dir_entry
*e1
, *e2
;
28 const char *name
= keydata
;
30 e1
= container_of(eptr
, const struct dir_entry
, ent
);
31 e2
= container_of(entry_or_key
, const struct dir_entry
, ent
);
33 return e1
->namelen
!= e2
->namelen
|| strncasecmp(e1
->name
,
34 name
? name
: e2
->name
, e1
->namelen
);
37 static struct dir_entry
*find_dir_entry__hash(struct index_state
*istate
,
38 const char *name
, unsigned int namelen
, unsigned int hash
)
41 hashmap_entry_init(&key
.ent
, hash
);
42 key
.namelen
= namelen
;
43 return hashmap_get_entry(&istate
->dir_hash
, &key
, ent
, name
);
46 static struct dir_entry
*find_dir_entry(struct index_state
*istate
,
47 const char *name
, unsigned int namelen
)
49 return find_dir_entry__hash(istate
, name
, namelen
, memihash(name
, namelen
));
52 static struct dir_entry
*hash_dir_entry(struct index_state
*istate
,
53 struct cache_entry
*ce
, int namelen
)
56 * Throw each directory component in the hash for quick lookup
57 * during a git status. Directory components are stored without their
58 * closing slash. Despite submodules being a directory, they never
59 * reach this point, because they are stored
60 * in index_state.name_hash (as ordinary cache_entries).
62 struct dir_entry
*dir
;
64 /* get length of parent directory */
65 while (namelen
> 0 && !is_dir_sep(ce
->name
[namelen
- 1]))
71 /* lookup existing entry for that directory */
72 dir
= find_dir_entry(istate
, ce
->name
, namelen
);
74 /* not found, create it and add to hash table */
75 FLEX_ALLOC_MEM(dir
, name
, ce
->name
, namelen
);
76 hashmap_entry_init(&dir
->ent
, memihash(ce
->name
, namelen
));
77 dir
->namelen
= namelen
;
78 hashmap_add(&istate
->dir_hash
, &dir
->ent
);
80 /* recursively add missing parent directories */
81 dir
->parent
= hash_dir_entry(istate
, ce
, namelen
);
86 static void add_dir_entry(struct index_state
*istate
, struct cache_entry
*ce
)
88 /* Add reference to the directory entry (and parents if 0). */
89 struct dir_entry
*dir
= hash_dir_entry(istate
, ce
, ce_namelen(ce
));
90 while (dir
&& !(dir
->nr
++))
94 static void remove_dir_entry(struct index_state
*istate
, struct cache_entry
*ce
)
97 * Release reference to the directory entry. If 0, remove and continue
98 * with parent directory.
100 struct dir_entry
*dir
= hash_dir_entry(istate
, ce
, ce_namelen(ce
));
101 while (dir
&& !(--dir
->nr
)) {
102 struct dir_entry
*parent
= dir
->parent
;
103 hashmap_remove(&istate
->dir_hash
, &dir
->ent
, NULL
);
109 static void hash_index_entry(struct index_state
*istate
, struct cache_entry
*ce
)
111 if (ce
->ce_flags
& CE_HASHED
)
113 ce
->ce_flags
|= CE_HASHED
;
115 if (!S_ISSPARSEDIR(ce
->ce_mode
)) {
116 hashmap_entry_init(&ce
->ent
, memihash(ce
->name
, ce_namelen(ce
)));
117 hashmap_add(&istate
->name_hash
, &ce
->ent
);
121 add_dir_entry(istate
, ce
);
124 static int cache_entry_cmp(const void *cmp_data UNUSED
,
125 const struct hashmap_entry
*eptr
,
126 const struct hashmap_entry
*entry_or_key
,
129 const struct cache_entry
*ce1
, *ce2
;
131 ce1
= container_of(eptr
, const struct cache_entry
, ent
);
132 ce2
= container_of(entry_or_key
, const struct cache_entry
, ent
);
135 * For remove_name_hash, find the exact entry (pointer equality); for
136 * index_file_exists, find all entries with matching hash code and
137 * decide whether the entry matches in same_name.
139 return remove
? !(ce1
== ce2
) : 0;
142 static int lazy_try_threaded
= 1;
143 static int lazy_nr_dir_threads
;
146 * Set a minimum number of cache_entries that we will handle per
147 * thread and use that to decide how many threads to run (up to
148 * the number on the system).
150 * For guidance setting the lower per-thread bound, see:
151 * t/helper/test-lazy-init-name-hash --analyze
153 #define LAZY_THREAD_COST (2000)
156 * We use n mutexes to guard n partitions of the "istate->dir_hash"
157 * hashtable. Since "find" and "insert" operations will hash to a
158 * particular bucket and modify/search a single chain, we can say
159 * that "all chains mod n" are guarded by the same mutex -- rather
160 * than having a single mutex to guard the entire table. (This does
161 * require that we disable "rehashing" on the hashtable.)
163 * So, a larger value here decreases the probability of a collision
164 * and the time that each thread must wait for the mutex.
166 #define LAZY_MAX_MUTEX (32)
168 static pthread_mutex_t
*lazy_dir_mutex_array
;
171 * An array of lazy_entry items is used by the n threads in
172 * the directory parse (first) phase to (lock-free) store the
173 * intermediate results. These values are then referenced by
174 * the 2 threads in the second phase.
177 struct dir_entry
*dir
;
178 unsigned int hash_dir
;
179 unsigned int hash_name
;
183 * Decide if we want to use threads (if available) to load
184 * the hash tables. We set "lazy_nr_dir_threads" to zero when
185 * it is not worth it.
187 static int lookup_lazy_params(struct index_state
*istate
)
191 lazy_nr_dir_threads
= 0;
193 if (!lazy_try_threaded
)
197 * If we are respecting case, just use the original
198 * code to build the "istate->name_hash". We don't
199 * need the complexity here.
204 nr_cpus
= online_cpus();
208 if (istate
->cache_nr
< 2 * LAZY_THREAD_COST
)
211 if (istate
->cache_nr
< nr_cpus
* LAZY_THREAD_COST
)
212 nr_cpus
= istate
->cache_nr
/ LAZY_THREAD_COST
;
213 lazy_nr_dir_threads
= nr_cpus
;
214 return lazy_nr_dir_threads
;
218 * Initialize n mutexes for use when searching and inserting
219 * into "istate->dir_hash". All "dir" threads are trying
220 * to insert partial pathnames into the hash as they iterate
221 * over their portions of the index, so lock contention is
224 * However, the hashmap is going to put items into bucket
225 * chains based on their hash values. Use that to create n
226 * mutexes and lock on mutex[bucket(hash) % n]. This will
227 * decrease the collision rate by (hopefully) a factor of n.
229 static void init_dir_mutex(void)
233 CALLOC_ARRAY(lazy_dir_mutex_array
, LAZY_MAX_MUTEX
);
235 for (j
= 0; j
< LAZY_MAX_MUTEX
; j
++)
236 init_recursive_mutex(&lazy_dir_mutex_array
[j
]);
239 static void cleanup_dir_mutex(void)
243 for (j
= 0; j
< LAZY_MAX_MUTEX
; j
++)
244 pthread_mutex_destroy(&lazy_dir_mutex_array
[j
]);
246 free(lazy_dir_mutex_array
);
249 static void lock_dir_mutex(int j
)
251 pthread_mutex_lock(&lazy_dir_mutex_array
[j
]);
254 static void unlock_dir_mutex(int j
)
256 pthread_mutex_unlock(&lazy_dir_mutex_array
[j
]);
259 static inline int compute_dir_lock_nr(
260 const struct hashmap
*map
,
263 return hashmap_bucket(map
, hash
) % LAZY_MAX_MUTEX
;
266 static struct dir_entry
*hash_dir_entry_with_parent_and_prefix(
267 struct index_state
*istate
,
268 struct dir_entry
*parent
,
269 struct strbuf
*prefix
)
271 struct dir_entry
*dir
;
276 * Either we have a parent directory and path with slash(es)
277 * or the directory is an immediate child of the root directory.
279 assert((parent
!= NULL
) ^ (strchr(prefix
->buf
, '/') == NULL
));
282 hash
= memihash_cont(parent
->ent
.hash
,
283 prefix
->buf
+ parent
->namelen
,
284 prefix
->len
- parent
->namelen
);
286 hash
= memihash(prefix
->buf
, prefix
->len
);
288 lock_nr
= compute_dir_lock_nr(&istate
->dir_hash
, hash
);
289 lock_dir_mutex(lock_nr
);
291 dir
= find_dir_entry__hash(istate
, prefix
->buf
, prefix
->len
, hash
);
293 FLEX_ALLOC_MEM(dir
, name
, prefix
->buf
, prefix
->len
);
294 hashmap_entry_init(&dir
->ent
, hash
);
295 dir
->namelen
= prefix
->len
;
296 dir
->parent
= parent
;
297 hashmap_add(&istate
->dir_hash
, &dir
->ent
);
300 unlock_dir_mutex(lock_nr
);
302 /* All I really need here is an InterlockedIncrement(&(parent->nr)) */
303 lock_nr
= compute_dir_lock_nr(&istate
->dir_hash
, parent
->ent
.hash
);
304 lock_dir_mutex(lock_nr
);
309 unlock_dir_mutex(lock_nr
);
315 * handle_range_1() and handle_range_dir() are derived from
316 * clear_ce_flags_1() and clear_ce_flags_dir() in unpack-trees.c
317 * and handle the iteration over the entire array of index entries.
318 * They use recursion for adjacent entries in the same parent
321 static int handle_range_1(
322 struct index_state
*istate
,
325 struct dir_entry
*parent
,
326 struct strbuf
*prefix
,
327 struct lazy_entry
*lazy_entries
);
329 static int handle_range_dir(
330 struct index_state
*istate
,
333 struct dir_entry
*parent
,
334 struct strbuf
*prefix
,
335 struct lazy_entry
*lazy_entries
,
336 struct dir_entry
**dir_new_out
)
339 int input_prefix_len
= prefix
->len
;
340 struct dir_entry
*dir_new
;
342 dir_new
= hash_dir_entry_with_parent_and_prefix(istate
, parent
, prefix
);
344 strbuf_addch(prefix
, '/');
347 * Scan forward in the index array for index entries having the same
348 * path prefix (that are also in this directory).
350 if (k_start
+ 1 >= k_end
)
352 else if (strncmp(istate
->cache
[k_start
+ 1]->name
, prefix
->buf
, prefix
->len
) > 0)
354 else if (strncmp(istate
->cache
[k_end
- 1]->name
, prefix
->buf
, prefix
->len
) == 0)
360 while (begin
< end
) {
361 int mid
= begin
+ ((end
- begin
) >> 1);
362 int cmp
= strncmp(istate
->cache
[mid
]->name
, prefix
->buf
, prefix
->len
);
363 if (cmp
== 0) /* mid has same prefix; look in second part */
365 else if (cmp
> 0) /* mid is past group; look in first part */
368 die("cache entry out of order");
374 * Recurse and process what we can of this subset [k_start, k).
376 rc
= handle_range_1(istate
, k_start
, k
, dir_new
, prefix
, lazy_entries
);
378 strbuf_setlen(prefix
, input_prefix_len
);
380 *dir_new_out
= dir_new
;
384 static int handle_range_1(
385 struct index_state
*istate
,
388 struct dir_entry
*parent
,
389 struct strbuf
*prefix
,
390 struct lazy_entry
*lazy_entries
)
392 int input_prefix_len
= prefix
->len
;
396 struct cache_entry
*ce_k
= istate
->cache
[k
];
397 const char *name
, *slash
;
399 if (prefix
->len
&& strncmp(ce_k
->name
, prefix
->buf
, prefix
->len
))
402 name
= ce_k
->name
+ prefix
->len
;
403 slash
= strchr(name
, '/');
406 int len
= slash
- name
;
408 struct dir_entry
*dir_new
;
410 strbuf_add(prefix
, name
, len
);
411 processed
= handle_range_dir(istate
, k
, k_end
, parent
, prefix
, lazy_entries
, &dir_new
);
414 strbuf_setlen(prefix
, input_prefix_len
);
418 strbuf_addch(prefix
, '/');
419 processed
= handle_range_1(istate
, k
, k_end
, dir_new
, prefix
, lazy_entries
);
421 strbuf_setlen(prefix
, input_prefix_len
);
426 * It is too expensive to take a lock to insert "ce_k"
427 * into "istate->name_hash" and increment the ref-count
428 * on the "parent" dir. So we defer actually updating
429 * permanent data structures until phase 2 (where we
430 * can change the locking requirements) and simply
431 * accumulate our current results into the lazy_entries
434 * We do not need to lock the lazy_entries array because
435 * we have exclusive access to the cells in the range
436 * [k_start,k_end) that this thread was given.
438 lazy_entries
[k
].dir
= parent
;
440 lazy_entries
[k
].hash_name
= memihash_cont(
442 ce_k
->name
+ parent
->namelen
,
443 ce_namelen(ce_k
) - parent
->namelen
);
444 lazy_entries
[k
].hash_dir
= parent
->ent
.hash
;
446 lazy_entries
[k
].hash_name
= memihash(ce_k
->name
, ce_namelen(ce_k
));
455 struct lazy_dir_thread_data
{
457 struct index_state
*istate
;
458 struct lazy_entry
*lazy_entries
;
463 static void *lazy_dir_thread_proc(void *_data
)
465 struct lazy_dir_thread_data
*d
= _data
;
466 struct strbuf prefix
= STRBUF_INIT
;
467 handle_range_1(d
->istate
, d
->k_start
, d
->k_end
, NULL
, &prefix
, d
->lazy_entries
);
468 strbuf_release(&prefix
);
472 struct lazy_name_thread_data
{
474 struct index_state
*istate
;
475 struct lazy_entry
*lazy_entries
;
478 static void *lazy_name_thread_proc(void *_data
)
480 struct lazy_name_thread_data
*d
= _data
;
483 for (k
= 0; k
< d
->istate
->cache_nr
; k
++) {
484 struct cache_entry
*ce_k
= d
->istate
->cache
[k
];
485 ce_k
->ce_flags
|= CE_HASHED
;
486 hashmap_entry_init(&ce_k
->ent
, d
->lazy_entries
[k
].hash_name
);
487 hashmap_add(&d
->istate
->name_hash
, &ce_k
->ent
);
493 static inline void lazy_update_dir_ref_counts(
494 struct index_state
*istate
,
495 struct lazy_entry
*lazy_entries
)
499 for (k
= 0; k
< istate
->cache_nr
; k
++) {
500 if (lazy_entries
[k
].dir
)
501 lazy_entries
[k
].dir
->nr
++;
505 static void threaded_lazy_init_name_hash(
506 struct index_state
*istate
)
512 struct lazy_entry
*lazy_entries
;
513 struct lazy_dir_thread_data
*td_dir
;
514 struct lazy_name_thread_data
*td_name
;
520 nr_each
= DIV_ROUND_UP(istate
->cache_nr
, lazy_nr_dir_threads
);
522 CALLOC_ARRAY(lazy_entries
, istate
->cache_nr
);
523 CALLOC_ARRAY(td_dir
, lazy_nr_dir_threads
);
524 CALLOC_ARRAY(td_name
, 1);
530 * Build "istate->dir_hash" using n "dir" threads (and a read-only index).
532 for (t
= 0; t
< lazy_nr_dir_threads
; t
++) {
533 struct lazy_dir_thread_data
*td_dir_t
= td_dir
+ t
;
534 td_dir_t
->istate
= istate
;
535 td_dir_t
->lazy_entries
= lazy_entries
;
536 td_dir_t
->k_start
= k_start
;
538 if (k_start
> istate
->cache_nr
)
539 k_start
= istate
->cache_nr
;
540 td_dir_t
->k_end
= k_start
;
541 err
= pthread_create(&td_dir_t
->pthread
, NULL
, lazy_dir_thread_proc
, td_dir_t
);
543 die(_("unable to create lazy_dir thread: %s"), strerror(err
));
545 for (t
= 0; t
< lazy_nr_dir_threads
; t
++) {
546 struct lazy_dir_thread_data
*td_dir_t
= td_dir
+ t
;
547 if (pthread_join(td_dir_t
->pthread
, NULL
))
548 die("unable to join lazy_dir_thread");
553 * Iterate over all index entries and add them to the "istate->name_hash"
554 * using a single "name" background thread.
555 * (Testing showed it wasn't worth running more than 1 thread for this.)
557 * Meanwhile, finish updating the parent directory ref-counts for each
558 * index entry using the current thread. (This step is very fast and
559 * doesn't need threading.)
561 td_name
->istate
= istate
;
562 td_name
->lazy_entries
= lazy_entries
;
563 err
= pthread_create(&td_name
->pthread
, NULL
, lazy_name_thread_proc
, td_name
);
565 die(_("unable to create lazy_name thread: %s"), strerror(err
));
567 lazy_update_dir_ref_counts(istate
, lazy_entries
);
569 err
= pthread_join(td_name
->pthread
, NULL
);
571 die(_("unable to join lazy_name thread: %s"), strerror(err
));
580 static void lazy_init_name_hash(struct index_state
*istate
)
583 if (istate
->name_hash_initialized
)
585 trace_performance_enter();
586 trace2_region_enter("index", "name-hash-init", istate
->repo
);
587 hashmap_init(&istate
->name_hash
, cache_entry_cmp
, NULL
, istate
->cache_nr
);
588 hashmap_init(&istate
->dir_hash
, dir_entry_cmp
, NULL
, istate
->cache_nr
);
590 if (lookup_lazy_params(istate
)) {
592 * Disable item counting and automatic rehashing because
593 * we do per-chain (mod n) locking rather than whole hashmap
594 * locking and we need to prevent the table-size from changing
595 * and bucket items from being redistributed.
597 hashmap_disable_item_counting(&istate
->dir_hash
);
598 threaded_lazy_init_name_hash(istate
);
599 hashmap_enable_item_counting(&istate
->dir_hash
);
602 for (nr
= 0; nr
< istate
->cache_nr
; nr
++)
603 hash_index_entry(istate
, istate
->cache
[nr
]);
606 istate
->name_hash_initialized
= 1;
607 trace2_region_leave("index", "name-hash-init", istate
->repo
);
608 trace_performance_leave("initialize name hash");
612 * A test routine for t/helper/ sources.
614 * Returns the number of threads used or 0 when
615 * the non-threaded code path was used.
617 * Requesting threading WILL NOT override guards
618 * in lookup_lazy_params().
620 int test_lazy_init_name_hash(struct index_state
*istate
, int try_threaded
)
622 lazy_nr_dir_threads
= 0;
623 lazy_try_threaded
= try_threaded
;
625 lazy_init_name_hash(istate
);
627 return lazy_nr_dir_threads
;
630 void add_name_hash(struct index_state
*istate
, struct cache_entry
*ce
)
632 if (istate
->name_hash_initialized
)
633 hash_index_entry(istate
, ce
);
636 void remove_name_hash(struct index_state
*istate
, struct cache_entry
*ce
)
638 if (!istate
->name_hash_initialized
|| !(ce
->ce_flags
& CE_HASHED
))
640 ce
->ce_flags
&= ~CE_HASHED
;
641 hashmap_remove(&istate
->name_hash
, &ce
->ent
, ce
);
644 remove_dir_entry(istate
, ce
);
647 static int slow_same_name(const char *name1
, int len1
, const char *name2
, int len2
)
653 unsigned char c1
= *name1
++;
654 unsigned char c2
= *name2
++;
666 static int same_name(const struct cache_entry
*ce
, const char *name
, int namelen
, int icase
)
668 int len
= ce_namelen(ce
);
671 * Always do exact compare, even if we want a case-ignoring comparison;
672 * we do the quick exact one first, because it will be the common case.
674 if (len
== namelen
&& !memcmp(name
, ce
->name
, len
))
680 return slow_same_name(name
, namelen
, ce
->name
, len
);
683 int index_dir_exists(struct index_state
*istate
, const char *name
, int namelen
)
685 struct dir_entry
*dir
;
687 lazy_init_name_hash(istate
);
688 expand_to_path(istate
, name
, namelen
, 0);
689 dir
= find_dir_entry(istate
, name
, namelen
);
690 return dir
&& dir
->nr
;
693 void adjust_dirname_case(struct index_state
*istate
, char *name
)
695 const char *startPtr
= name
;
696 const char *ptr
= startPtr
;
698 lazy_init_name_hash(istate
);
699 expand_to_path(istate
, name
, strlen(name
), 0);
701 while (*ptr
&& *ptr
!= '/')
705 struct dir_entry
*dir
;
707 dir
= find_dir_entry(istate
, name
, ptr
- name
);
709 memcpy((void *)startPtr
, dir
->name
+ (startPtr
- name
), ptr
- startPtr
);
717 struct cache_entry
*index_file_exists(struct index_state
*istate
, const char *name
, int namelen
, int icase
)
719 struct cache_entry
*ce
;
720 unsigned int hash
= memihash(name
, namelen
);
722 lazy_init_name_hash(istate
);
723 expand_to_path(istate
, name
, namelen
, icase
);
725 ce
= hashmap_get_entry_from_hash(&istate
->name_hash
, hash
, NULL
,
726 struct cache_entry
, ent
);
727 hashmap_for_each_entry_from(&istate
->name_hash
, ce
, ent
) {
728 if (same_name(ce
, name
, namelen
, icase
))
734 void free_name_hash(struct index_state
*istate
)
736 if (!istate
->name_hash_initialized
)
738 istate
->name_hash_initialized
= 0;
740 hashmap_clear(&istate
->name_hash
);
741 hashmap_clear_and_free(&istate
->dir_hash
, struct dir_entry
, ent
);