]>
git.ipfire.org Git - thirdparty/git.git/blob - name-hash.c
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
,
20 const struct hashmap_entry
*eptr
,
21 const struct hashmap_entry
*entry_or_key
,
24 const struct dir_entry
*e1
, *e2
;
25 const char *name
= keydata
;
27 e1
= container_of(eptr
, const struct dir_entry
, ent
);
28 e2
= container_of(entry_or_key
, const struct dir_entry
, ent
);
30 return e1
->namelen
!= e2
->namelen
|| strncasecmp(e1
->name
,
31 name
? name
: e2
->name
, e1
->namelen
);
34 static struct dir_entry
*find_dir_entry__hash(struct index_state
*istate
,
35 const char *name
, unsigned int namelen
, unsigned int hash
)
38 hashmap_entry_init(&key
.ent
, hash
);
39 key
.namelen
= namelen
;
40 return hashmap_get_entry(&istate
->dir_hash
, &key
, name
,
41 struct dir_entry
, ent
);
44 static struct dir_entry
*find_dir_entry(struct index_state
*istate
,
45 const char *name
, unsigned int namelen
)
47 return find_dir_entry__hash(istate
, name
, namelen
, memihash(name
, namelen
));
50 static struct dir_entry
*hash_dir_entry(struct index_state
*istate
,
51 struct cache_entry
*ce
, int namelen
)
54 * Throw each directory component in the hash for quick lookup
55 * during a git status. Directory components are stored without their
56 * closing slash. Despite submodules being a directory, they never
57 * reach this point, because they are stored
58 * in index_state.name_hash (as ordinary cache_entries).
60 struct dir_entry
*dir
;
62 /* get length of parent directory */
63 while (namelen
> 0 && !is_dir_sep(ce
->name
[namelen
- 1]))
69 /* lookup existing entry for that directory */
70 dir
= find_dir_entry(istate
, ce
->name
, namelen
);
72 /* not found, create it and add to hash table */
73 FLEX_ALLOC_MEM(dir
, name
, ce
->name
, namelen
);
74 hashmap_entry_init(&dir
->ent
, memihash(ce
->name
, namelen
));
75 dir
->namelen
= namelen
;
76 hashmap_add(&istate
->dir_hash
, &dir
->ent
);
78 /* recursively add missing parent directories */
79 dir
->parent
= hash_dir_entry(istate
, ce
, namelen
);
84 static void add_dir_entry(struct index_state
*istate
, struct cache_entry
*ce
)
86 /* Add reference to the directory entry (and parents if 0). */
87 struct dir_entry
*dir
= hash_dir_entry(istate
, ce
, ce_namelen(ce
));
88 while (dir
&& !(dir
->nr
++))
92 static void remove_dir_entry(struct index_state
*istate
, struct cache_entry
*ce
)
95 * Release reference to the directory entry. If 0, remove and continue
96 * with parent directory.
98 struct dir_entry
*dir
= hash_dir_entry(istate
, ce
, ce_namelen(ce
));
99 while (dir
&& !(--dir
->nr
)) {
100 struct dir_entry
*parent
= dir
->parent
;
101 hashmap_remove(&istate
->dir_hash
, &dir
->ent
, NULL
);
107 static void hash_index_entry(struct index_state
*istate
, struct cache_entry
*ce
)
109 if (ce
->ce_flags
& CE_HASHED
)
111 ce
->ce_flags
|= CE_HASHED
;
112 hashmap_entry_init(&ce
->ent
, memihash(ce
->name
, ce_namelen(ce
)));
113 hashmap_add(&istate
->name_hash
, &ce
->ent
);
116 add_dir_entry(istate
, ce
);
119 static int cache_entry_cmp(const void *unused_cmp_data
,
120 const struct hashmap_entry
*eptr
,
121 const struct hashmap_entry
*entry_or_key
,
124 const struct cache_entry
*ce1
, *ce2
;
126 ce1
= container_of(eptr
, const struct cache_entry
, ent
);
127 ce2
= container_of(entry_or_key
, const struct cache_entry
, ent
);
130 * For remove_name_hash, find the exact entry (pointer equality); for
131 * index_file_exists, find all entries with matching hash code and
132 * decide whether the entry matches in same_name.
134 return remove
? !(ce1
== ce2
) : 0;
137 static int lazy_try_threaded
= 1;
138 static int lazy_nr_dir_threads
;
141 * Set a minimum number of cache_entries that we will handle per
142 * thread and use that to decide how many threads to run (upto
143 * the number on the system).
145 * For guidance setting the lower per-thread bound, see:
146 * t/helper/test-lazy-init-name-hash --analyze
148 #define LAZY_THREAD_COST (2000)
151 * We use n mutexes to guard n partitions of the "istate->dir_hash"
152 * hashtable. Since "find" and "insert" operations will hash to a
153 * particular bucket and modify/search a single chain, we can say
154 * that "all chains mod n" are guarded by the same mutex -- rather
155 * than having a single mutex to guard the entire table. (This does
156 * require that we disable "rehashing" on the hashtable.)
158 * So, a larger value here decreases the probability of a collision
159 * and the time that each thread must wait for the mutex.
161 #define LAZY_MAX_MUTEX (32)
163 static pthread_mutex_t
*lazy_dir_mutex_array
;
166 * An array of lazy_entry items is used by the n threads in
167 * the directory parse (first) phase to (lock-free) store the
168 * intermediate results. These values are then referenced by
169 * the 2 threads in the second phase.
172 struct dir_entry
*dir
;
173 unsigned int hash_dir
;
174 unsigned int hash_name
;
178 * Decide if we want to use threads (if available) to load
179 * the hash tables. We set "lazy_nr_dir_threads" to zero when
180 * it is not worth it.
182 static int lookup_lazy_params(struct index_state
*istate
)
186 lazy_nr_dir_threads
= 0;
188 if (!lazy_try_threaded
)
192 * If we are respecting case, just use the original
193 * code to build the "istate->name_hash". We don't
194 * need the complexity here.
199 nr_cpus
= online_cpus();
203 if (istate
->cache_nr
< 2 * LAZY_THREAD_COST
)
206 if (istate
->cache_nr
< nr_cpus
* LAZY_THREAD_COST
)
207 nr_cpus
= istate
->cache_nr
/ LAZY_THREAD_COST
;
208 lazy_nr_dir_threads
= nr_cpus
;
209 return lazy_nr_dir_threads
;
213 * Initialize n mutexes for use when searching and inserting
214 * into "istate->dir_hash". All "dir" threads are trying
215 * to insert partial pathnames into the hash as they iterate
216 * over their portions of the index, so lock contention is
219 * However, the hashmap is going to put items into bucket
220 * chains based on their hash values. Use that to create n
221 * mutexes and lock on mutex[bucket(hash) % n]. This will
222 * decrease the collision rate by (hopefully) by a factor of n.
224 static void init_dir_mutex(void)
228 lazy_dir_mutex_array
= xcalloc(LAZY_MAX_MUTEX
, sizeof(pthread_mutex_t
));
230 for (j
= 0; j
< LAZY_MAX_MUTEX
; j
++)
231 init_recursive_mutex(&lazy_dir_mutex_array
[j
]);
234 static void cleanup_dir_mutex(void)
238 for (j
= 0; j
< LAZY_MAX_MUTEX
; j
++)
239 pthread_mutex_destroy(&lazy_dir_mutex_array
[j
]);
241 free(lazy_dir_mutex_array
);
244 static void lock_dir_mutex(int j
)
246 pthread_mutex_lock(&lazy_dir_mutex_array
[j
]);
249 static void unlock_dir_mutex(int j
)
251 pthread_mutex_unlock(&lazy_dir_mutex_array
[j
]);
254 static inline int compute_dir_lock_nr(
255 const struct hashmap
*map
,
258 return hashmap_bucket(map
, hash
) % LAZY_MAX_MUTEX
;
261 static struct dir_entry
*hash_dir_entry_with_parent_and_prefix(
262 struct index_state
*istate
,
263 struct dir_entry
*parent
,
264 struct strbuf
*prefix
)
266 struct dir_entry
*dir
;
271 * Either we have a parent directory and path with slash(es)
272 * or the directory is an immediate child of the root directory.
274 assert((parent
!= NULL
) ^ (strchr(prefix
->buf
, '/') == NULL
));
277 hash
= memihash_cont(parent
->ent
.hash
,
278 prefix
->buf
+ parent
->namelen
,
279 prefix
->len
- parent
->namelen
);
281 hash
= memihash(prefix
->buf
, prefix
->len
);
283 lock_nr
= compute_dir_lock_nr(&istate
->dir_hash
, hash
);
284 lock_dir_mutex(lock_nr
);
286 dir
= find_dir_entry__hash(istate
, prefix
->buf
, prefix
->len
, hash
);
288 FLEX_ALLOC_MEM(dir
, name
, prefix
->buf
, prefix
->len
);
289 hashmap_entry_init(&dir
->ent
, hash
);
290 dir
->namelen
= prefix
->len
;
291 dir
->parent
= parent
;
292 hashmap_add(&istate
->dir_hash
, &dir
->ent
);
295 unlock_dir_mutex(lock_nr
);
297 /* All I really need here is an InterlockedIncrement(&(parent->nr)) */
298 lock_nr
= compute_dir_lock_nr(&istate
->dir_hash
, parent
->ent
.hash
);
299 lock_dir_mutex(lock_nr
);
304 unlock_dir_mutex(lock_nr
);
310 * handle_range_1() and handle_range_dir() are derived from
311 * clear_ce_flags_1() and clear_ce_flags_dir() in unpack-trees.c
312 * and handle the iteration over the entire array of index entries.
313 * They use recursion for adjacent entries in the same parent
316 static int handle_range_1(
317 struct index_state
*istate
,
320 struct dir_entry
*parent
,
321 struct strbuf
*prefix
,
322 struct lazy_entry
*lazy_entries
);
324 static int handle_range_dir(
325 struct index_state
*istate
,
328 struct dir_entry
*parent
,
329 struct strbuf
*prefix
,
330 struct lazy_entry
*lazy_entries
,
331 struct dir_entry
**dir_new_out
)
334 int input_prefix_len
= prefix
->len
;
335 struct dir_entry
*dir_new
;
337 dir_new
= hash_dir_entry_with_parent_and_prefix(istate
, parent
, prefix
);
339 strbuf_addch(prefix
, '/');
342 * Scan forward in the index array for index entries having the same
343 * path prefix (that are also in this directory).
345 if (k_start
+ 1 >= k_end
)
347 else if (strncmp(istate
->cache
[k_start
+ 1]->name
, prefix
->buf
, prefix
->len
) > 0)
349 else if (strncmp(istate
->cache
[k_end
- 1]->name
, prefix
->buf
, prefix
->len
) == 0)
355 while (begin
< end
) {
356 int mid
= begin
+ ((end
- begin
) >> 1);
357 int cmp
= strncmp(istate
->cache
[mid
]->name
, prefix
->buf
, prefix
->len
);
358 if (cmp
== 0) /* mid has same prefix; look in second part */
360 else if (cmp
> 0) /* mid is past group; look in first part */
363 die("cache entry out of order");
369 * Recurse and process what we can of this subset [k_start, k).
371 rc
= handle_range_1(istate
, k_start
, k
, dir_new
, prefix
, lazy_entries
);
373 strbuf_setlen(prefix
, input_prefix_len
);
375 *dir_new_out
= dir_new
;
379 static int handle_range_1(
380 struct index_state
*istate
,
383 struct dir_entry
*parent
,
384 struct strbuf
*prefix
,
385 struct lazy_entry
*lazy_entries
)
387 int input_prefix_len
= prefix
->len
;
391 struct cache_entry
*ce_k
= istate
->cache
[k
];
392 const char *name
, *slash
;
394 if (prefix
->len
&& strncmp(ce_k
->name
, prefix
->buf
, prefix
->len
))
397 name
= ce_k
->name
+ prefix
->len
;
398 slash
= strchr(name
, '/');
401 int len
= slash
- name
;
403 struct dir_entry
*dir_new
;
405 strbuf_add(prefix
, name
, len
);
406 processed
= handle_range_dir(istate
, k
, k_end
, parent
, prefix
, lazy_entries
, &dir_new
);
409 strbuf_setlen(prefix
, input_prefix_len
);
413 strbuf_addch(prefix
, '/');
414 processed
= handle_range_1(istate
, k
, k_end
, dir_new
, prefix
, lazy_entries
);
416 strbuf_setlen(prefix
, input_prefix_len
);
421 * It is too expensive to take a lock to insert "ce_k"
422 * into "istate->name_hash" and increment the ref-count
423 * on the "parent" dir. So we defer actually updating
424 * permanent data structures until phase 2 (where we
425 * can change the locking requirements) and simply
426 * accumulate our current results into the lazy_entries
429 * We do not need to lock the lazy_entries array because
430 * we have exclusive access to the cells in the range
431 * [k_start,k_end) that this thread was given.
433 lazy_entries
[k
].dir
= parent
;
435 lazy_entries
[k
].hash_name
= memihash_cont(
437 ce_k
->name
+ parent
->namelen
,
438 ce_namelen(ce_k
) - parent
->namelen
);
439 lazy_entries
[k
].hash_dir
= parent
->ent
.hash
;
441 lazy_entries
[k
].hash_name
= memihash(ce_k
->name
, ce_namelen(ce_k
));
450 struct lazy_dir_thread_data
{
452 struct index_state
*istate
;
453 struct lazy_entry
*lazy_entries
;
458 static void *lazy_dir_thread_proc(void *_data
)
460 struct lazy_dir_thread_data
*d
= _data
;
461 struct strbuf prefix
= STRBUF_INIT
;
462 handle_range_1(d
->istate
, d
->k_start
, d
->k_end
, NULL
, &prefix
, d
->lazy_entries
);
463 strbuf_release(&prefix
);
467 struct lazy_name_thread_data
{
469 struct index_state
*istate
;
470 struct lazy_entry
*lazy_entries
;
473 static void *lazy_name_thread_proc(void *_data
)
475 struct lazy_name_thread_data
*d
= _data
;
478 for (k
= 0; k
< d
->istate
->cache_nr
; k
++) {
479 struct cache_entry
*ce_k
= d
->istate
->cache
[k
];
480 ce_k
->ce_flags
|= CE_HASHED
;
481 hashmap_entry_init(&ce_k
->ent
, d
->lazy_entries
[k
].hash_name
);
482 hashmap_add(&d
->istate
->name_hash
, &ce_k
->ent
);
488 static inline void lazy_update_dir_ref_counts(
489 struct index_state
*istate
,
490 struct lazy_entry
*lazy_entries
)
494 for (k
= 0; k
< istate
->cache_nr
; k
++) {
495 if (lazy_entries
[k
].dir
)
496 lazy_entries
[k
].dir
->nr
++;
500 static void threaded_lazy_init_name_hash(
501 struct index_state
*istate
)
507 struct lazy_entry
*lazy_entries
;
508 struct lazy_dir_thread_data
*td_dir
;
509 struct lazy_name_thread_data
*td_name
;
515 nr_each
= DIV_ROUND_UP(istate
->cache_nr
, lazy_nr_dir_threads
);
517 lazy_entries
= xcalloc(istate
->cache_nr
, sizeof(struct lazy_entry
));
518 td_dir
= xcalloc(lazy_nr_dir_threads
, sizeof(struct lazy_dir_thread_data
));
519 td_name
= xcalloc(1, sizeof(struct lazy_name_thread_data
));
525 * Build "istate->dir_hash" using n "dir" threads (and a read-only index).
527 for (t
= 0; t
< lazy_nr_dir_threads
; t
++) {
528 struct lazy_dir_thread_data
*td_dir_t
= td_dir
+ t
;
529 td_dir_t
->istate
= istate
;
530 td_dir_t
->lazy_entries
= lazy_entries
;
531 td_dir_t
->k_start
= k_start
;
533 if (k_start
> istate
->cache_nr
)
534 k_start
= istate
->cache_nr
;
535 td_dir_t
->k_end
= k_start
;
536 err
= pthread_create(&td_dir_t
->pthread
, NULL
, lazy_dir_thread_proc
, td_dir_t
);
538 die(_("unable to create lazy_dir thread: %s"), strerror(err
));
540 for (t
= 0; t
< lazy_nr_dir_threads
; t
++) {
541 struct lazy_dir_thread_data
*td_dir_t
= td_dir
+ t
;
542 if (pthread_join(td_dir_t
->pthread
, NULL
))
543 die("unable to join lazy_dir_thread");
548 * Iterate over all index entries and add them to the "istate->name_hash"
549 * using a single "name" background thread.
550 * (Testing showed it wasn't worth running more than 1 thread for this.)
552 * Meanwhile, finish updating the parent directory ref-counts for each
553 * index entry using the current thread. (This step is very fast and
554 * doesn't need threading.)
556 td_name
->istate
= istate
;
557 td_name
->lazy_entries
= lazy_entries
;
558 err
= pthread_create(&td_name
->pthread
, NULL
, lazy_name_thread_proc
, td_name
);
560 die(_("unable to create lazy_name thread: %s"), strerror(err
));
562 lazy_update_dir_ref_counts(istate
, lazy_entries
);
564 err
= pthread_join(td_name
->pthread
, NULL
);
566 die(_("unable to join lazy_name thread: %s"), strerror(err
));
575 static void lazy_init_name_hash(struct index_state
*istate
)
578 if (istate
->name_hash_initialized
)
580 trace_performance_enter();
581 hashmap_init(&istate
->name_hash
, cache_entry_cmp
, NULL
, istate
->cache_nr
);
582 hashmap_init(&istate
->dir_hash
, dir_entry_cmp
, NULL
, istate
->cache_nr
);
584 if (lookup_lazy_params(istate
)) {
586 * Disable item counting and automatic rehashing because
587 * we do per-chain (mod n) locking rather than whole hashmap
588 * locking and we need to prevent the table-size from changing
589 * and bucket items from being redistributed.
591 hashmap_disable_item_counting(&istate
->dir_hash
);
592 threaded_lazy_init_name_hash(istate
);
593 hashmap_enable_item_counting(&istate
->dir_hash
);
596 for (nr
= 0; nr
< istate
->cache_nr
; nr
++)
597 hash_index_entry(istate
, istate
->cache
[nr
]);
600 istate
->name_hash_initialized
= 1;
601 trace_performance_leave("initialize name hash");
605 * A test routine for t/helper/ sources.
607 * Returns the number of threads used or 0 when
608 * the non-threaded code path was used.
610 * Requesting threading WILL NOT override guards
611 * in lookup_lazy_params().
613 int test_lazy_init_name_hash(struct index_state
*istate
, int try_threaded
)
615 lazy_nr_dir_threads
= 0;
616 lazy_try_threaded
= try_threaded
;
618 lazy_init_name_hash(istate
);
620 return lazy_nr_dir_threads
;
623 void add_name_hash(struct index_state
*istate
, struct cache_entry
*ce
)
625 if (istate
->name_hash_initialized
)
626 hash_index_entry(istate
, ce
);
629 void remove_name_hash(struct index_state
*istate
, struct cache_entry
*ce
)
631 if (!istate
->name_hash_initialized
|| !(ce
->ce_flags
& CE_HASHED
))
633 ce
->ce_flags
&= ~CE_HASHED
;
634 hashmap_remove(&istate
->name_hash
, &ce
->ent
, ce
);
637 remove_dir_entry(istate
, ce
);
640 static int slow_same_name(const char *name1
, int len1
, const char *name2
, int len2
)
646 unsigned char c1
= *name1
++;
647 unsigned char c2
= *name2
++;
659 static int same_name(const struct cache_entry
*ce
, const char *name
, int namelen
, int icase
)
661 int len
= ce_namelen(ce
);
664 * Always do exact compare, even if we want a case-ignoring comparison;
665 * we do the quick exact one first, because it will be the common case.
667 if (len
== namelen
&& !memcmp(name
, ce
->name
, len
))
673 return slow_same_name(name
, namelen
, ce
->name
, len
);
676 int index_dir_exists(struct index_state
*istate
, const char *name
, int namelen
)
678 struct dir_entry
*dir
;
680 lazy_init_name_hash(istate
);
681 dir
= find_dir_entry(istate
, name
, namelen
);
682 return dir
&& dir
->nr
;
685 void adjust_dirname_case(struct index_state
*istate
, char *name
)
687 const char *startPtr
= name
;
688 const char *ptr
= startPtr
;
690 lazy_init_name_hash(istate
);
692 while (*ptr
&& *ptr
!= '/')
696 struct dir_entry
*dir
;
698 dir
= find_dir_entry(istate
, name
, ptr
- name
);
700 memcpy((void *)startPtr
, dir
->name
+ (startPtr
- name
), ptr
- startPtr
);
708 struct cache_entry
*index_file_exists(struct index_state
*istate
, const char *name
, int namelen
, int icase
)
710 struct cache_entry
*ce
;
711 unsigned int hash
= memihash(name
, namelen
);
713 lazy_init_name_hash(istate
);
715 ce
= hashmap_get_entry_from_hash(&istate
->name_hash
, hash
, NULL
,
716 struct cache_entry
, ent
);
717 hashmap_for_each_entry_from(&istate
->name_hash
, ce
,
718 struct cache_entry
, ent
) {
719 if (same_name(ce
, name
, namelen
, icase
))
725 void free_name_hash(struct index_state
*istate
)
727 if (!istate
->name_hash_initialized
)
729 istate
->name_hash_initialized
= 0;
731 hashmap_free(&istate
->name_hash
);
732 hashmap_free_entries(&istate
->dir_hash
, struct dir_entry
, ent
);