]>
Commit | Line | Data |
---|---|---|
96872bc2 LT |
1 | /* |
2 | * name-hash.c | |
3 | * | |
4 | * Hashing names in the index state | |
5 | * | |
6 | * Copyright (C) 2008 Linus Torvalds | |
7 | */ | |
bc5c5ec0 | 8 | #include "git-compat-util.h" |
32a8f510 | 9 | #include "environment.h" |
f394e093 | 10 | #include "gettext.h" |
f5653856 | 11 | #include "name-hash.h" |
08c46a49 EN |
12 | #include "object.h" |
13 | #include "read-cache-ll.h" | |
07642942 | 14 | #include "thread-utils.h" |
74ea5c95 | 15 | #include "trace.h" |
6a9372f4 | 16 | #include "trace2.h" |
4589bca8 | 17 | #include "sparse-index.h" |
96872bc2 | 18 | |
2092678c | 19 | struct dir_entry { |
e05881a4 | 20 | struct hashmap_entry ent; |
2092678c | 21 | struct dir_entry *parent; |
2092678c KB |
22 | int nr; |
23 | unsigned int namelen; | |
41284eb0 | 24 | char name[FLEX_ARRAY]; |
2092678c KB |
25 | }; |
26 | ||
5cf88fd8 | 27 | static int dir_entry_cmp(const void *cmp_data UNUSED, |
939af16e EW |
28 | const struct hashmap_entry *eptr, |
29 | const struct hashmap_entry *entry_or_key, | |
56a14ea7 | 30 | const void *keydata) |
e05881a4 | 31 | { |
939af16e | 32 | const struct dir_entry *e1, *e2; |
56a14ea7 SB |
33 | const char *name = keydata; |
34 | ||
939af16e EW |
35 | e1 = container_of(eptr, const struct dir_entry, ent); |
36 | e2 = container_of(entry_or_key, const struct dir_entry, ent); | |
37 | ||
41284eb0 DT |
38 | return e1->namelen != e2->namelen || strncasecmp(e1->name, |
39 | name ? name : e2->name, e1->namelen); | |
e05881a4 KB |
40 | } |
41 | ||
846df809 JH |
42 | static struct dir_entry *find_dir_entry__hash(struct index_state *istate, |
43 | const char *name, unsigned int namelen, unsigned int hash) | |
2092678c | 44 | { |
e05881a4 | 45 | struct dir_entry key; |
d22245a2 | 46 | hashmap_entry_init(&key.ent, hash); |
e05881a4 | 47 | key.namelen = namelen; |
404ab78e | 48 | return hashmap_get_entry(&istate->dir_hash, &key, ent, name); |
2092678c KB |
49 | } |
50 | ||
846df809 JH |
51 | static struct dir_entry *find_dir_entry(struct index_state *istate, |
52 | const char *name, unsigned int namelen) | |
53 | { | |
54 | return find_dir_entry__hash(istate, name, namelen, memihash(name, namelen)); | |
55 | } | |
56 | ||
2092678c KB |
57 | static struct dir_entry *hash_dir_entry(struct index_state *istate, |
58 | struct cache_entry *ce, int namelen) | |
5102c617 JJ |
59 | { |
60 | /* | |
61 | * Throw each directory component in the hash for quick lookup | |
d28eec26 | 62 | * during a git status. Directory components are stored without their |
5102c617 | 63 | * closing slash. Despite submodules being a directory, they never |
d28eec26 | 64 | * reach this point, because they are stored |
2092678c | 65 | * in index_state.name_hash (as ordinary cache_entries). |
5102c617 | 66 | */ |
2092678c KB |
67 | struct dir_entry *dir; |
68 | ||
69 | /* get length of parent directory */ | |
70 | while (namelen > 0 && !is_dir_sep(ce->name[namelen - 1])) | |
71 | namelen--; | |
72 | if (namelen <= 0) | |
73 | return NULL; | |
d28eec26 | 74 | namelen--; |
2092678c KB |
75 | |
76 | /* lookup existing entry for that directory */ | |
77 | dir = find_dir_entry(istate, ce->name, namelen); | |
78 | if (!dir) { | |
79 | /* not found, create it and add to hash table */ | |
96ffc06f | 80 | FLEX_ALLOC_MEM(dir, name, ce->name, namelen); |
d22245a2 | 81 | hashmap_entry_init(&dir->ent, memihash(ce->name, namelen)); |
2092678c | 82 | dir->namelen = namelen; |
b94e5c1d | 83 | hashmap_add(&istate->dir_hash, &dir->ent); |
2092678c KB |
84 | |
85 | /* recursively add missing parent directories */ | |
d28eec26 | 86 | dir->parent = hash_dir_entry(istate, ce, namelen); |
5102c617 | 87 | } |
2092678c KB |
88 | return dir; |
89 | } | |
90 | ||
91 | static void add_dir_entry(struct index_state *istate, struct cache_entry *ce) | |
92 | { | |
93 | /* Add reference to the directory entry (and parents if 0). */ | |
94 | struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce)); | |
95 | while (dir && !(dir->nr++)) | |
96 | dir = dir->parent; | |
97 | } | |
98 | ||
99 | static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce) | |
100 | { | |
101 | /* | |
1c8cca19 KB |
102 | * Release reference to the directory entry. If 0, remove and continue |
103 | * with parent directory. | |
2092678c KB |
104 | */ |
105 | struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce)); | |
1c8cca19 KB |
106 | while (dir && !(--dir->nr)) { |
107 | struct dir_entry *parent = dir->parent; | |
28ee7941 | 108 | hashmap_remove(&istate->dir_hash, &dir->ent, NULL); |
1c8cca19 KB |
109 | free(dir); |
110 | dir = parent; | |
111 | } | |
5102c617 JJ |
112 | } |
113 | ||
96872bc2 LT |
114 | static void hash_index_entry(struct index_state *istate, struct cache_entry *ce) |
115 | { | |
96872bc2 LT |
116 | if (ce->ce_flags & CE_HASHED) |
117 | return; | |
118 | ce->ce_flags |= CE_HASHED; | |
5f116695 DS |
119 | |
120 | if (!S_ISSPARSEDIR(ce->ce_mode)) { | |
121 | hashmap_entry_init(&ce->ent, memihash(ce->name, ce_namelen(ce))); | |
122 | hashmap_add(&istate->name_hash, &ce->ent); | |
123 | } | |
5102c617 | 124 | |
419a597f | 125 | if (ignore_case) |
2092678c | 126 | add_dir_entry(istate, ce); |
96872bc2 LT |
127 | } |
128 | ||
5cf88fd8 | 129 | static int cache_entry_cmp(const void *cmp_data UNUSED, |
939af16e EW |
130 | const struct hashmap_entry *eptr, |
131 | const struct hashmap_entry *entry_or_key, | |
7663cdc8 | 132 | const void *remove) |
419a597f | 133 | { |
939af16e EW |
134 | const struct cache_entry *ce1, *ce2; |
135 | ||
136 | ce1 = container_of(eptr, const struct cache_entry, ent); | |
137 | ce2 = container_of(entry_or_key, const struct cache_entry, ent); | |
138 | ||
419a597f KB |
139 | /* |
140 | * For remove_name_hash, find the exact entry (pointer equality); for | |
7b359ea6 | 141 | * index_file_exists, find all entries with matching hash code and |
419a597f KB |
142 | * decide whether the entry matches in same_name. |
143 | */ | |
144 | return remove ? !(ce1 == ce2) : 0; | |
145 | } | |
146 | ||
846df809 JH |
147 | static int lazy_try_threaded = 1; |
148 | static int lazy_nr_dir_threads; | |
149 | ||
846df809 JH |
150 | /* |
151 | * Set a minimum number of cache_entries that we will handle per | |
15beaaa3 | 152 | * thread and use that to decide how many threads to run (up to |
846df809 JH |
153 | * the number on the system). |
154 | * | |
155 | * For guidance setting the lower per-thread bound, see: | |
156 | * t/helper/test-lazy-init-name-hash --analyze | |
157 | */ | |
158 | #define LAZY_THREAD_COST (2000) | |
159 | ||
160 | /* | |
161 | * We use n mutexes to guard n partitions of the "istate->dir_hash" | |
162 | * hashtable. Since "find" and "insert" operations will hash to a | |
163 | * particular bucket and modify/search a single chain, we can say | |
164 | * that "all chains mod n" are guarded by the same mutex -- rather | |
165 | * than having a single mutex to guard the entire table. (This does | |
166 | * require that we disable "rehashing" on the hashtable.) | |
167 | * | |
168 | * So, a larger value here decreases the probability of a collision | |
169 | * and the time that each thread must wait for the mutex. | |
170 | */ | |
171 | #define LAZY_MAX_MUTEX (32) | |
172 | ||
173 | static pthread_mutex_t *lazy_dir_mutex_array; | |
174 | ||
175 | /* | |
176 | * An array of lazy_entry items is used by the n threads in | |
177 | * the directory parse (first) phase to (lock-free) store the | |
178 | * intermediate results. These values are then referenced by | |
179 | * the 2 threads in the second phase. | |
180 | */ | |
181 | struct lazy_entry { | |
182 | struct dir_entry *dir; | |
183 | unsigned int hash_dir; | |
184 | unsigned int hash_name; | |
185 | }; | |
186 | ||
187 | /* | |
188 | * Decide if we want to use threads (if available) to load | |
189 | * the hash tables. We set "lazy_nr_dir_threads" to zero when | |
190 | * it is not worth it. | |
191 | */ | |
192 | static int lookup_lazy_params(struct index_state *istate) | |
193 | { | |
194 | int nr_cpus; | |
195 | ||
196 | lazy_nr_dir_threads = 0; | |
197 | ||
198 | if (!lazy_try_threaded) | |
199 | return 0; | |
200 | ||
201 | /* | |
202 | * If we are respecting case, just use the original | |
203 | * code to build the "istate->name_hash". We don't | |
204 | * need the complexity here. | |
205 | */ | |
206 | if (!ignore_case) | |
207 | return 0; | |
208 | ||
209 | nr_cpus = online_cpus(); | |
210 | if (nr_cpus < 2) | |
211 | return 0; | |
212 | ||
213 | if (istate->cache_nr < 2 * LAZY_THREAD_COST) | |
214 | return 0; | |
96872bc2 | 215 | |
846df809 JH |
216 | if (istate->cache_nr < nr_cpus * LAZY_THREAD_COST) |
217 | nr_cpus = istate->cache_nr / LAZY_THREAD_COST; | |
218 | lazy_nr_dir_threads = nr_cpus; | |
219 | return lazy_nr_dir_threads; | |
220 | } | |
221 | ||
222 | /* | |
223 | * Initialize n mutexes for use when searching and inserting | |
224 | * into "istate->dir_hash". All "dir" threads are trying | |
225 | * to insert partial pathnames into the hash as they iterate | |
226 | * over their portions of the index, so lock contention is | |
227 | * high. | |
228 | * | |
229 | * However, the hashmap is going to put items into bucket | |
230 | * chains based on their hash values. Use that to create n | |
231 | * mutexes and lock on mutex[bucket(hash) % n]. This will | |
77363a51 | 232 | * decrease the collision rate by (hopefully) a factor of n. |
846df809 JH |
233 | */ |
234 | static void init_dir_mutex(void) | |
235 | { | |
236 | int j; | |
237 | ||
ca56dadb | 238 | CALLOC_ARRAY(lazy_dir_mutex_array, LAZY_MAX_MUTEX); |
846df809 JH |
239 | |
240 | for (j = 0; j < LAZY_MAX_MUTEX; j++) | |
241 | init_recursive_mutex(&lazy_dir_mutex_array[j]); | |
242 | } | |
243 | ||
244 | static void cleanup_dir_mutex(void) | |
245 | { | |
246 | int j; | |
247 | ||
248 | for (j = 0; j < LAZY_MAX_MUTEX; j++) | |
249 | pthread_mutex_destroy(&lazy_dir_mutex_array[j]); | |
250 | ||
251 | free(lazy_dir_mutex_array); | |
252 | } | |
253 | ||
254 | static void lock_dir_mutex(int j) | |
255 | { | |
256 | pthread_mutex_lock(&lazy_dir_mutex_array[j]); | |
257 | } | |
258 | ||
259 | static void unlock_dir_mutex(int j) | |
260 | { | |
261 | pthread_mutex_unlock(&lazy_dir_mutex_array[j]); | |
262 | } | |
263 | ||
264 | static inline int compute_dir_lock_nr( | |
265 | const struct hashmap *map, | |
266 | unsigned int hash) | |
267 | { | |
268 | return hashmap_bucket(map, hash) % LAZY_MAX_MUTEX; | |
269 | } | |
270 | ||
271 | static struct dir_entry *hash_dir_entry_with_parent_and_prefix( | |
272 | struct index_state *istate, | |
273 | struct dir_entry *parent, | |
274 | struct strbuf *prefix) | |
275 | { | |
276 | struct dir_entry *dir; | |
277 | unsigned int hash; | |
278 | int lock_nr; | |
279 | ||
280 | /* | |
281 | * Either we have a parent directory and path with slash(es) | |
282 | * or the directory is an immediate child of the root directory. | |
283 | */ | |
284 | assert((parent != NULL) ^ (strchr(prefix->buf, '/') == NULL)); | |
285 | ||
286 | if (parent) | |
287 | hash = memihash_cont(parent->ent.hash, | |
288 | prefix->buf + parent->namelen, | |
289 | prefix->len - parent->namelen); | |
290 | else | |
291 | hash = memihash(prefix->buf, prefix->len); | |
292 | ||
293 | lock_nr = compute_dir_lock_nr(&istate->dir_hash, hash); | |
294 | lock_dir_mutex(lock_nr); | |
295 | ||
296 | dir = find_dir_entry__hash(istate, prefix->buf, prefix->len, hash); | |
297 | if (!dir) { | |
298 | FLEX_ALLOC_MEM(dir, name, prefix->buf, prefix->len); | |
d22245a2 | 299 | hashmap_entry_init(&dir->ent, hash); |
846df809 JH |
300 | dir->namelen = prefix->len; |
301 | dir->parent = parent; | |
b94e5c1d | 302 | hashmap_add(&istate->dir_hash, &dir->ent); |
846df809 JH |
303 | |
304 | if (parent) { | |
305 | unlock_dir_mutex(lock_nr); | |
306 | ||
307 | /* All I really need here is an InterlockedIncrement(&(parent->nr)) */ | |
308 | lock_nr = compute_dir_lock_nr(&istate->dir_hash, parent->ent.hash); | |
309 | lock_dir_mutex(lock_nr); | |
310 | parent->nr++; | |
311 | } | |
312 | } | |
313 | ||
314 | unlock_dir_mutex(lock_nr); | |
315 | ||
316 | return dir; | |
317 | } | |
318 | ||
319 | /* | |
320 | * handle_range_1() and handle_range_dir() are derived from | |
321 | * clear_ce_flags_1() and clear_ce_flags_dir() in unpack-trees.c | |
322 | * and handle the iteration over the entire array of index entries. | |
323 | * They use recursion for adjacent entries in the same parent | |
324 | * directory. | |
325 | */ | |
326 | static int handle_range_1( | |
327 | struct index_state *istate, | |
328 | int k_start, | |
329 | int k_end, | |
330 | struct dir_entry *parent, | |
331 | struct strbuf *prefix, | |
332 | struct lazy_entry *lazy_entries); | |
333 | ||
334 | static int handle_range_dir( | |
335 | struct index_state *istate, | |
336 | int k_start, | |
337 | int k_end, | |
338 | struct dir_entry *parent, | |
339 | struct strbuf *prefix, | |
340 | struct lazy_entry *lazy_entries, | |
341 | struct dir_entry **dir_new_out) | |
342 | { | |
343 | int rc, k; | |
344 | int input_prefix_len = prefix->len; | |
345 | struct dir_entry *dir_new; | |
346 | ||
347 | dir_new = hash_dir_entry_with_parent_and_prefix(istate, parent, prefix); | |
348 | ||
349 | strbuf_addch(prefix, '/'); | |
350 | ||
351 | /* | |
352 | * Scan forward in the index array for index entries having the same | |
353 | * path prefix (that are also in this directory). | |
354 | */ | |
2a1bd45b KW |
355 | if (k_start + 1 >= k_end) |
356 | k = k_end; | |
357 | else if (strncmp(istate->cache[k_start + 1]->name, prefix->buf, prefix->len) > 0) | |
846df809 JH |
358 | k = k_start + 1; |
359 | else if (strncmp(istate->cache[k_end - 1]->name, prefix->buf, prefix->len) == 0) | |
360 | k = k_end; | |
361 | else { | |
362 | int begin = k_start; | |
363 | int end = k_end; | |
568a05c5 | 364 | assert(begin >= 0); |
846df809 | 365 | while (begin < end) { |
568a05c5 | 366 | int mid = begin + ((end - begin) >> 1); |
846df809 JH |
367 | int cmp = strncmp(istate->cache[mid]->name, prefix->buf, prefix->len); |
368 | if (cmp == 0) /* mid has same prefix; look in second part */ | |
369 | begin = mid + 1; | |
370 | else if (cmp > 0) /* mid is past group; look in first part */ | |
371 | end = mid; | |
372 | else | |
373 | die("cache entry out of order"); | |
374 | } | |
375 | k = begin; | |
376 | } | |
377 | ||
378 | /* | |
379 | * Recurse and process what we can of this subset [k_start, k). | |
380 | */ | |
381 | rc = handle_range_1(istate, k_start, k, dir_new, prefix, lazy_entries); | |
382 | ||
383 | strbuf_setlen(prefix, input_prefix_len); | |
384 | ||
385 | *dir_new_out = dir_new; | |
386 | return rc; | |
387 | } | |
388 | ||
389 | static int handle_range_1( | |
390 | struct index_state *istate, | |
391 | int k_start, | |
392 | int k_end, | |
393 | struct dir_entry *parent, | |
394 | struct strbuf *prefix, | |
395 | struct lazy_entry *lazy_entries) | |
396 | { | |
397 | int input_prefix_len = prefix->len; | |
398 | int k = k_start; | |
399 | ||
400 | while (k < k_end) { | |
401 | struct cache_entry *ce_k = istate->cache[k]; | |
402 | const char *name, *slash; | |
403 | ||
404 | if (prefix->len && strncmp(ce_k->name, prefix->buf, prefix->len)) | |
405 | break; | |
406 | ||
407 | name = ce_k->name + prefix->len; | |
408 | slash = strchr(name, '/'); | |
409 | ||
410 | if (slash) { | |
411 | int len = slash - name; | |
412 | int processed; | |
413 | struct dir_entry *dir_new; | |
414 | ||
415 | strbuf_add(prefix, name, len); | |
416 | processed = handle_range_dir(istate, k, k_end, parent, prefix, lazy_entries, &dir_new); | |
417 | if (processed) { | |
418 | k += processed; | |
419 | strbuf_setlen(prefix, input_prefix_len); | |
420 | continue; | |
421 | } | |
422 | ||
423 | strbuf_addch(prefix, '/'); | |
424 | processed = handle_range_1(istate, k, k_end, dir_new, prefix, lazy_entries); | |
425 | k += processed; | |
426 | strbuf_setlen(prefix, input_prefix_len); | |
427 | continue; | |
428 | } | |
429 | ||
430 | /* | |
431 | * It is too expensive to take a lock to insert "ce_k" | |
432 | * into "istate->name_hash" and increment the ref-count | |
433 | * on the "parent" dir. So we defer actually updating | |
434 | * permanent data structures until phase 2 (where we | |
435 | * can change the locking requirements) and simply | |
436 | * accumulate our current results into the lazy_entries | |
437 | * data array). | |
438 | * | |
439 | * We do not need to lock the lazy_entries array because | |
440 | * we have exclusive access to the cells in the range | |
441 | * [k_start,k_end) that this thread was given. | |
442 | */ | |
443 | lazy_entries[k].dir = parent; | |
444 | if (parent) { | |
445 | lazy_entries[k].hash_name = memihash_cont( | |
446 | parent->ent.hash, | |
447 | ce_k->name + parent->namelen, | |
448 | ce_namelen(ce_k) - parent->namelen); | |
449 | lazy_entries[k].hash_dir = parent->ent.hash; | |
450 | } else { | |
451 | lazy_entries[k].hash_name = memihash(ce_k->name, ce_namelen(ce_k)); | |
452 | } | |
453 | ||
454 | k++; | |
455 | } | |
456 | ||
457 | return k - k_start; | |
458 | } | |
459 | ||
460 | struct lazy_dir_thread_data { | |
461 | pthread_t pthread; | |
462 | struct index_state *istate; | |
463 | struct lazy_entry *lazy_entries; | |
464 | int k_start; | |
465 | int k_end; | |
466 | }; | |
467 | ||
468 | static void *lazy_dir_thread_proc(void *_data) | |
469 | { | |
470 | struct lazy_dir_thread_data *d = _data; | |
471 | struct strbuf prefix = STRBUF_INIT; | |
472 | handle_range_1(d->istate, d->k_start, d->k_end, NULL, &prefix, d->lazy_entries); | |
473 | strbuf_release(&prefix); | |
474 | return NULL; | |
475 | } | |
476 | ||
477 | struct lazy_name_thread_data { | |
478 | pthread_t pthread; | |
479 | struct index_state *istate; | |
480 | struct lazy_entry *lazy_entries; | |
481 | }; | |
482 | ||
483 | static void *lazy_name_thread_proc(void *_data) | |
484 | { | |
485 | struct lazy_name_thread_data *d = _data; | |
486 | int k; | |
487 | ||
488 | for (k = 0; k < d->istate->cache_nr; k++) { | |
489 | struct cache_entry *ce_k = d->istate->cache[k]; | |
490 | ce_k->ce_flags |= CE_HASHED; | |
d22245a2 | 491 | hashmap_entry_init(&ce_k->ent, d->lazy_entries[k].hash_name); |
b94e5c1d | 492 | hashmap_add(&d->istate->name_hash, &ce_k->ent); |
846df809 JH |
493 | } |
494 | ||
495 | return NULL; | |
496 | } | |
497 | ||
498 | static inline void lazy_update_dir_ref_counts( | |
499 | struct index_state *istate, | |
500 | struct lazy_entry *lazy_entries) | |
501 | { | |
502 | int k; | |
503 | ||
504 | for (k = 0; k < istate->cache_nr; k++) { | |
505 | if (lazy_entries[k].dir) | |
506 | lazy_entries[k].dir->nr++; | |
507 | } | |
508 | } | |
509 | ||
510 | static void threaded_lazy_init_name_hash( | |
511 | struct index_state *istate) | |
512 | { | |
2179045f | 513 | int err; |
846df809 JH |
514 | int nr_each; |
515 | int k_start; | |
516 | int t; | |
517 | struct lazy_entry *lazy_entries; | |
518 | struct lazy_dir_thread_data *td_dir; | |
519 | struct lazy_name_thread_data *td_name; | |
520 | ||
07642942 NTND |
521 | if (!HAVE_THREADS) |
522 | return; | |
523 | ||
846df809 JH |
524 | k_start = 0; |
525 | nr_each = DIV_ROUND_UP(istate->cache_nr, lazy_nr_dir_threads); | |
526 | ||
ca56dadb RS |
527 | CALLOC_ARRAY(lazy_entries, istate->cache_nr); |
528 | CALLOC_ARRAY(td_dir, lazy_nr_dir_threads); | |
529 | CALLOC_ARRAY(td_name, 1); | |
846df809 JH |
530 | |
531 | init_dir_mutex(); | |
532 | ||
533 | /* | |
534 | * Phase 1: | |
535 | * Build "istate->dir_hash" using n "dir" threads (and a read-only index). | |
536 | */ | |
537 | for (t = 0; t < lazy_nr_dir_threads; t++) { | |
538 | struct lazy_dir_thread_data *td_dir_t = td_dir + t; | |
539 | td_dir_t->istate = istate; | |
540 | td_dir_t->lazy_entries = lazy_entries; | |
541 | td_dir_t->k_start = k_start; | |
542 | k_start += nr_each; | |
543 | if (k_start > istate->cache_nr) | |
544 | k_start = istate->cache_nr; | |
545 | td_dir_t->k_end = k_start; | |
2179045f NTND |
546 | err = pthread_create(&td_dir_t->pthread, NULL, lazy_dir_thread_proc, td_dir_t); |
547 | if (err) | |
548 | die(_("unable to create lazy_dir thread: %s"), strerror(err)); | |
846df809 JH |
549 | } |
550 | for (t = 0; t < lazy_nr_dir_threads; t++) { | |
551 | struct lazy_dir_thread_data *td_dir_t = td_dir + t; | |
552 | if (pthread_join(td_dir_t->pthread, NULL)) | |
553 | die("unable to join lazy_dir_thread"); | |
554 | } | |
555 | ||
556 | /* | |
557 | * Phase 2: | |
558 | * Iterate over all index entries and add them to the "istate->name_hash" | |
559 | * using a single "name" background thread. | |
560 | * (Testing showed it wasn't worth running more than 1 thread for this.) | |
561 | * | |
562 | * Meanwhile, finish updating the parent directory ref-counts for each | |
563 | * index entry using the current thread. (This step is very fast and | |
564 | * doesn't need threading.) | |
565 | */ | |
566 | td_name->istate = istate; | |
567 | td_name->lazy_entries = lazy_entries; | |
2179045f NTND |
568 | err = pthread_create(&td_name->pthread, NULL, lazy_name_thread_proc, td_name); |
569 | if (err) | |
570 | die(_("unable to create lazy_name thread: %s"), strerror(err)); | |
846df809 JH |
571 | |
572 | lazy_update_dir_ref_counts(istate, lazy_entries); | |
573 | ||
2179045f NTND |
574 | err = pthread_join(td_name->pthread, NULL); |
575 | if (err) | |
576 | die(_("unable to join lazy_name thread: %s"), strerror(err)); | |
846df809 JH |
577 | |
578 | cleanup_dir_mutex(); | |
579 | ||
580 | free(td_name); | |
581 | free(td_dir); | |
582 | free(lazy_entries); | |
583 | } | |
584 | ||
846df809 JH |
585 | static void lazy_init_name_hash(struct index_state *istate) |
586 | { | |
ca54d9ba | 587 | |
96872bc2 LT |
588 | if (istate->name_hash_initialized) |
589 | return; | |
c46c406a | 590 | trace_performance_enter(); |
6a9372f4 | 591 | trace2_region_enter("index", "name-hash-init", istate->repo); |
56a14ea7 SB |
592 | hashmap_init(&istate->name_hash, cache_entry_cmp, NULL, istate->cache_nr); |
593 | hashmap_init(&istate->dir_hash, dir_entry_cmp, NULL, istate->cache_nr); | |
846df809 JH |
594 | |
595 | if (lookup_lazy_params(istate)) { | |
8b604d19 JH |
596 | /* |
597 | * Disable item counting and automatic rehashing because | |
598 | * we do per-chain (mod n) locking rather than whole hashmap | |
599 | * locking and we need to prevent the table-size from changing | |
600 | * and bucket items from being redistributed. | |
601 | */ | |
602 | hashmap_disable_item_counting(&istate->dir_hash); | |
846df809 | 603 | threaded_lazy_init_name_hash(istate); |
8b604d19 | 604 | hashmap_enable_item_counting(&istate->dir_hash); |
846df809 JH |
605 | } else { |
606 | int nr; | |
607 | for (nr = 0; nr < istate->cache_nr; nr++) | |
608 | hash_index_entry(istate, istate->cache[nr]); | |
609 | } | |
610 | ||
96872bc2 | 611 | istate->name_hash_initialized = 1; |
6a9372f4 | 612 | trace2_region_leave("index", "name-hash-init", istate->repo); |
c46c406a | 613 | trace_performance_leave("initialize name hash"); |
96872bc2 LT |
614 | } |
615 | ||
846df809 JH |
616 | /* |
617 | * A test routine for t/helper/ sources. | |
618 | * | |
619 | * Returns the number of threads used or 0 when | |
620 | * the non-threaded code path was used. | |
621 | * | |
622 | * Requesting threading WILL NOT override guards | |
623 | * in lookup_lazy_params(). | |
624 | */ | |
625 | int test_lazy_init_name_hash(struct index_state *istate, int try_threaded) | |
626 | { | |
627 | lazy_nr_dir_threads = 0; | |
628 | lazy_try_threaded = try_threaded; | |
629 | ||
630 | lazy_init_name_hash(istate); | |
631 | ||
632 | return lazy_nr_dir_threads; | |
633 | } | |
634 | ||
96872bc2 LT |
635 | void add_name_hash(struct index_state *istate, struct cache_entry *ce) |
636 | { | |
96872bc2 LT |
637 | if (istate->name_hash_initialized) |
638 | hash_index_entry(istate, ce); | |
639 | } | |
640 | ||
2092678c KB |
641 | void remove_name_hash(struct index_state *istate, struct cache_entry *ce) |
642 | { | |
419a597f KB |
643 | if (!istate->name_hash_initialized || !(ce->ce_flags & CE_HASHED)) |
644 | return; | |
645 | ce->ce_flags &= ~CE_HASHED; | |
28ee7941 | 646 | hashmap_remove(&istate->name_hash, &ce->ent, ce); |
2092678c | 647 | |
419a597f KB |
648 | if (ignore_case) |
649 | remove_dir_entry(istate, ce); | |
2092678c KB |
650 | } |
651 | ||
cd2fef59 LT |
652 | static int slow_same_name(const char *name1, int len1, const char *name2, int len2) |
653 | { | |
654 | if (len1 != len2) | |
655 | return 0; | |
656 | ||
657 | while (len1) { | |
658 | unsigned char c1 = *name1++; | |
659 | unsigned char c2 = *name2++; | |
660 | len1--; | |
661 | if (c1 != c2) { | |
662 | c1 = toupper(c1); | |
663 | c2 = toupper(c2); | |
664 | if (c1 != c2) | |
665 | return 0; | |
666 | } | |
667 | } | |
668 | return 1; | |
669 | } | |
670 | ||
671 | static int same_name(const struct cache_entry *ce, const char *name, int namelen, int icase) | |
672 | { | |
673 | int len = ce_namelen(ce); | |
674 | ||
675 | /* | |
676 | * Always do exact compare, even if we want a case-ignoring comparison; | |
677 | * we do the quick exact one first, because it will be the common case. | |
678 | */ | |
be99ec97 | 679 | if (len == namelen && !memcmp(name, ce->name, len)) |
cd2fef59 LT |
680 | return 1; |
681 | ||
5102c617 JJ |
682 | if (!icase) |
683 | return 0; | |
684 | ||
2092678c | 685 | return slow_same_name(name, namelen, ce->name, len); |
cd2fef59 LT |
686 | } |
687 | ||
41284eb0 | 688 | int index_dir_exists(struct index_state *istate, const char *name, int namelen) |
db5360f3 | 689 | { |
db5360f3 ES |
690 | struct dir_entry *dir; |
691 | ||
692 | lazy_init_name_hash(istate); | |
4589bca8 | 693 | expand_to_path(istate, name, namelen, 0); |
db5360f3 | 694 | dir = find_dir_entry(istate, name, namelen); |
41284eb0 DT |
695 | return dir && dir->nr; |
696 | } | |
db5360f3 | 697 | |
41284eb0 DT |
698 | void adjust_dirname_case(struct index_state *istate, char *name) |
699 | { | |
700 | const char *startPtr = name; | |
701 | const char *ptr = startPtr; | |
db5360f3 | 702 | |
41284eb0 | 703 | lazy_init_name_hash(istate); |
4589bca8 | 704 | expand_to_path(istate, name, strlen(name), 0); |
41284eb0 DT |
705 | while (*ptr) { |
706 | while (*ptr && *ptr != '/') | |
707 | ptr++; | |
708 | ||
709 | if (*ptr == '/') { | |
710 | struct dir_entry *dir; | |
711 | ||
c95525e9 | 712 | dir = find_dir_entry(istate, name, ptr - name); |
41284eb0 DT |
713 | if (dir) { |
714 | memcpy((void *)startPtr, dir->name + (startPtr - name), ptr - startPtr); | |
c95525e9 | 715 | startPtr = ptr + 1; |
41284eb0 | 716 | } |
c95525e9 | 717 | ptr++; |
41284eb0 DT |
718 | } |
719 | } | |
db5360f3 ES |
720 | } |
721 | ||
722 | struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase) | |
96872bc2 | 723 | { |
96872bc2 | 724 | struct cache_entry *ce; |
f0e63c41 | 725 | unsigned int hash = memihash(name, namelen); |
96872bc2 LT |
726 | |
727 | lazy_init_name_hash(istate); | |
4589bca8 | 728 | expand_to_path(istate, name, namelen, icase); |
96872bc2 | 729 | |
f0e63c41 EW |
730 | ce = hashmap_get_entry_from_hash(&istate->name_hash, hash, NULL, |
731 | struct cache_entry, ent); | |
23dee69f | 732 | hashmap_for_each_entry_from(&istate->name_hash, ce, ent) { |
419a597f KB |
733 | if (same_name(ce, name, namelen, icase)) |
734 | return ce; | |
96872bc2 | 735 | } |
df292c79 | 736 | return NULL; |
96872bc2 | 737 | } |
2092678c | 738 | |
2092678c KB |
739 | void free_name_hash(struct index_state *istate) |
740 | { | |
741 | if (!istate->name_hash_initialized) | |
742 | return; | |
743 | istate->name_hash_initialized = 0; | |
2092678c | 744 | |
6da1a258 EN |
745 | hashmap_clear(&istate->name_hash); |
746 | hashmap_clear_and_free(&istate->dir_hash, struct dir_entry, ent); | |
2092678c | 747 | } |