Merge branch 'jc/apply-fix-mismerge' into maint
[git] / name-hash.c
1 /*
2  * name-hash.c
3  *
4  * Hashing names in the index state
5  *
6  * Copyright (C) 2008 Linus Torvalds
7  */
8 #define NO_THE_INDEX_COMPATIBILITY_MACROS
9 #include "cache.h"
10
11 struct dir_entry {
12         struct hashmap_entry ent;
13         struct dir_entry *parent;
14         int nr;
15         unsigned int namelen;
16         char name[FLEX_ARRAY];
17 };
18
19 static int dir_entry_cmp(const struct dir_entry *e1,
20                 const struct dir_entry *e2, const char *name)
21 {
22         return e1->namelen != e2->namelen || strncasecmp(e1->name,
23                         name ? name : e2->name, e1->namelen);
24 }
25
26 static struct dir_entry *find_dir_entry__hash(struct index_state *istate,
27                 const char *name, unsigned int namelen, unsigned int hash)
28 {
29         struct dir_entry key;
30         hashmap_entry_init(&key, hash);
31         key.namelen = namelen;
32         return hashmap_get(&istate->dir_hash, &key, name);
33 }
34
35 static struct dir_entry *find_dir_entry(struct index_state *istate,
36                 const char *name, unsigned int namelen)
37 {
38         return find_dir_entry__hash(istate, name, namelen, memihash(name, namelen));
39 }
40
41 static struct dir_entry *hash_dir_entry(struct index_state *istate,
42                 struct cache_entry *ce, int namelen)
43 {
44         /*
45          * Throw each directory component in the hash for quick lookup
46          * during a git status. Directory components are stored without their
47          * closing slash.  Despite submodules being a directory, they never
48          * reach this point, because they are stored
49          * in index_state.name_hash (as ordinary cache_entries).
50          */
51         struct dir_entry *dir;
52
53         /* get length of parent directory */
54         while (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))
55                 namelen--;
56         if (namelen <= 0)
57                 return NULL;
58         namelen--;
59
60         /* lookup existing entry for that directory */
61         dir = find_dir_entry(istate, ce->name, namelen);
62         if (!dir) {
63                 /* not found, create it and add to hash table */
64                 FLEX_ALLOC_MEM(dir, name, ce->name, namelen);
65                 hashmap_entry_init(dir, memihash(ce->name, namelen));
66                 dir->namelen = namelen;
67                 hashmap_add(&istate->dir_hash, dir);
68
69                 /* recursively add missing parent directories */
70                 dir->parent = hash_dir_entry(istate, ce, namelen);
71         }
72         return dir;
73 }
74
75 static void add_dir_entry(struct index_state *istate, struct cache_entry *ce)
76 {
77         /* Add reference to the directory entry (and parents if 0). */
78         struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));
79         while (dir && !(dir->nr++))
80                 dir = dir->parent;
81 }
82
83 static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)
84 {
85         /*
86          * Release reference to the directory entry. If 0, remove and continue
87          * with parent directory.
88          */
89         struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));
90         while (dir && !(--dir->nr)) {
91                 struct dir_entry *parent = dir->parent;
92                 hashmap_remove(&istate->dir_hash, dir, NULL);
93                 free(dir);
94                 dir = parent;
95         }
96 }
97
98 static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
99 {
100         if (ce->ce_flags & CE_HASHED)
101                 return;
102         ce->ce_flags |= CE_HASHED;
103         hashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));
104         hashmap_add(&istate->name_hash, ce);
105
106         if (ignore_case)
107                 add_dir_entry(istate, ce);
108 }
109
110 static int cache_entry_cmp(const struct cache_entry *ce1,
111                 const struct cache_entry *ce2, const void *remove)
112 {
113         /*
114          * For remove_name_hash, find the exact entry (pointer equality); for
115          * index_file_exists, find all entries with matching hash code and
116          * decide whether the entry matches in same_name.
117          */
118         return remove ? !(ce1 == ce2) : 0;
119 }
120
121 static int lazy_try_threaded = 1;
122 static int lazy_nr_dir_threads;
123
124 #ifdef NO_PTHREADS
125
126 static inline int lookup_lazy_params(struct index_state *istate)
127 {
128         return 0;
129 }
130
131 static inline void threaded_lazy_init_name_hash(
132         struct index_state *istate)
133 {
134 }
135
136 #else
137
138 #include "thread-utils.h"
139
140 /*
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).
144  *
145  * For guidance setting the lower per-thread bound, see:
146  *     t/helper/test-lazy-init-name-hash --analyze
147  */
148 #define LAZY_THREAD_COST (2000)
149
150 /*
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.)
157  *
158  * So, a larger value here decreases the probability of a collision
159  * and the time that each thread must wait for the mutex.
160  */
161 #define LAZY_MAX_MUTEX   (32)
162
163 static pthread_mutex_t *lazy_dir_mutex_array;
164
165 /*
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.
170  */
171 struct lazy_entry {
172         struct dir_entry *dir;
173         unsigned int hash_dir;
174         unsigned int hash_name;
175 };
176
177 /*
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.
181  */
182 static int lookup_lazy_params(struct index_state *istate)
183 {
184         int nr_cpus;
185
186         lazy_nr_dir_threads = 0;
187
188         if (!lazy_try_threaded)
189                 return 0;
190
191         /*
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.
195          */
196         if (!ignore_case)
197                 return 0;
198
199         nr_cpus = online_cpus();
200         if (nr_cpus < 2)
201                 return 0;
202
203         if (istate->cache_nr < 2 * LAZY_THREAD_COST)
204                 return 0;
205
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;
210 }
211
212 /*
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
217  * high.
218  *
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.
223  */
224 static void init_dir_mutex(void)
225 {
226         int j;
227
228         lazy_dir_mutex_array = xcalloc(LAZY_MAX_MUTEX, sizeof(pthread_mutex_t));
229
230         for (j = 0; j < LAZY_MAX_MUTEX; j++)
231                 init_recursive_mutex(&lazy_dir_mutex_array[j]);
232 }
233
234 static void cleanup_dir_mutex(void)
235 {
236         int j;
237
238         for (j = 0; j < LAZY_MAX_MUTEX; j++)
239                 pthread_mutex_destroy(&lazy_dir_mutex_array[j]);
240
241         free(lazy_dir_mutex_array);
242 }
243
244 static void lock_dir_mutex(int j)
245 {
246         pthread_mutex_lock(&lazy_dir_mutex_array[j]);
247 }
248
249 static void unlock_dir_mutex(int j)
250 {
251         pthread_mutex_unlock(&lazy_dir_mutex_array[j]);
252 }
253
254 static inline int compute_dir_lock_nr(
255         const struct hashmap *map,
256         unsigned int hash)
257 {
258         return hashmap_bucket(map, hash) % LAZY_MAX_MUTEX;
259 }
260
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)
265 {
266         struct dir_entry *dir;
267         unsigned int hash;
268         int lock_nr;
269
270         /*
271          * Either we have a parent directory and path with slash(es)
272          * or the directory is an immediate child of the root directory.
273          */
274         assert((parent != NULL) ^ (strchr(prefix->buf, '/') == NULL));
275
276         if (parent)
277                 hash = memihash_cont(parent->ent.hash,
278                         prefix->buf + parent->namelen,
279                         prefix->len - parent->namelen);
280         else
281                 hash = memihash(prefix->buf, prefix->len);
282
283         lock_nr = compute_dir_lock_nr(&istate->dir_hash, hash);
284         lock_dir_mutex(lock_nr);
285
286         dir = find_dir_entry__hash(istate, prefix->buf, prefix->len, hash);
287         if (!dir) {
288                 FLEX_ALLOC_MEM(dir, name, prefix->buf, prefix->len);
289                 hashmap_entry_init(dir, hash);
290                 dir->namelen = prefix->len;
291                 dir->parent = parent;
292                 hashmap_add(&istate->dir_hash, dir);
293
294                 if (parent) {
295                         unlock_dir_mutex(lock_nr);
296
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);
300                         parent->nr++;
301                 }
302         }
303
304         unlock_dir_mutex(lock_nr);
305
306         return dir;
307 }
308
309 /*
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
314  * directory.
315  */
316 static int handle_range_1(
317         struct index_state *istate,
318         int k_start,
319         int k_end,
320         struct dir_entry *parent,
321         struct strbuf *prefix,
322         struct lazy_entry *lazy_entries);
323
324 static int handle_range_dir(
325         struct index_state *istate,
326         int k_start,
327         int k_end,
328         struct dir_entry *parent,
329         struct strbuf *prefix,
330         struct lazy_entry *lazy_entries,
331         struct dir_entry **dir_new_out)
332 {
333         int rc, k;
334         int input_prefix_len = prefix->len;
335         struct dir_entry *dir_new;
336
337         dir_new = hash_dir_entry_with_parent_and_prefix(istate, parent, prefix);
338
339         strbuf_addch(prefix, '/');
340
341         /*
342          * Scan forward in the index array for index entries having the same
343          * path prefix (that are also in this directory).
344          */
345         if (k_start + 1 >= k_end)
346                 k = k_end;
347         else if (strncmp(istate->cache[k_start + 1]->name, prefix->buf, prefix->len) > 0)
348                 k = k_start + 1;
349         else if (strncmp(istate->cache[k_end - 1]->name, prefix->buf, prefix->len) == 0)
350                 k = k_end;
351         else {
352                 int begin = k_start;
353                 int end = k_end;
354                 while (begin < end) {
355                         int mid = (begin + end) >> 1;
356                         int cmp = strncmp(istate->cache[mid]->name, prefix->buf, prefix->len);
357                         if (cmp == 0) /* mid has same prefix; look in second part */
358                                 begin = mid + 1;
359                         else if (cmp > 0) /* mid is past group; look in first part */
360                                 end = mid;
361                         else
362                                 die("cache entry out of order");
363                 }
364                 k = begin;
365         }
366
367         /*
368          * Recurse and process what we can of this subset [k_start, k).
369          */
370         rc = handle_range_1(istate, k_start, k, dir_new, prefix, lazy_entries);
371
372         strbuf_setlen(prefix, input_prefix_len);
373
374         *dir_new_out = dir_new;
375         return rc;
376 }
377
378 static int handle_range_1(
379         struct index_state *istate,
380         int k_start,
381         int k_end,
382         struct dir_entry *parent,
383         struct strbuf *prefix,
384         struct lazy_entry *lazy_entries)
385 {
386         int input_prefix_len = prefix->len;
387         int k = k_start;
388
389         while (k < k_end) {
390                 struct cache_entry *ce_k = istate->cache[k];
391                 const char *name, *slash;
392
393                 if (prefix->len && strncmp(ce_k->name, prefix->buf, prefix->len))
394                         break;
395
396                 name = ce_k->name + prefix->len;
397                 slash = strchr(name, '/');
398
399                 if (slash) {
400                         int len = slash - name;
401                         int processed;
402                         struct dir_entry *dir_new;
403
404                         strbuf_add(prefix, name, len);
405                         processed = handle_range_dir(istate, k, k_end, parent, prefix, lazy_entries, &dir_new);
406                         if (processed) {
407                                 k += processed;
408                                 strbuf_setlen(prefix, input_prefix_len);
409                                 continue;
410                         }
411
412                         strbuf_addch(prefix, '/');
413                         processed = handle_range_1(istate, k, k_end, dir_new, prefix, lazy_entries);
414                         k += processed;
415                         strbuf_setlen(prefix, input_prefix_len);
416                         continue;
417                 }
418
419                 /*
420                  * It is too expensive to take a lock to insert "ce_k"
421                  * into "istate->name_hash" and increment the ref-count
422                  * on the "parent" dir.  So we defer actually updating
423                  * permanent data structures until phase 2 (where we
424                  * can change the locking requirements) and simply
425                  * accumulate our current results into the lazy_entries
426                  * data array).
427                  *
428                  * We do not need to lock the lazy_entries array because
429                  * we have exclusive access to the cells in the range
430                  * [k_start,k_end) that this thread was given.
431                  */
432                 lazy_entries[k].dir = parent;
433                 if (parent) {
434                         lazy_entries[k].hash_name = memihash_cont(
435                                 parent->ent.hash,
436                                 ce_k->name + parent->namelen,
437                                 ce_namelen(ce_k) - parent->namelen);
438                         lazy_entries[k].hash_dir = parent->ent.hash;
439                 } else {
440                         lazy_entries[k].hash_name = memihash(ce_k->name, ce_namelen(ce_k));
441                 }
442
443                 k++;
444         }
445
446         return k - k_start;
447 }
448
449 struct lazy_dir_thread_data {
450         pthread_t pthread;
451         struct index_state *istate;
452         struct lazy_entry *lazy_entries;
453         int k_start;
454         int k_end;
455 };
456
457 static void *lazy_dir_thread_proc(void *_data)
458 {
459         struct lazy_dir_thread_data *d = _data;
460         struct strbuf prefix = STRBUF_INIT;
461         handle_range_1(d->istate, d->k_start, d->k_end, NULL, &prefix, d->lazy_entries);
462         strbuf_release(&prefix);
463         return NULL;
464 }
465
466 struct lazy_name_thread_data {
467         pthread_t pthread;
468         struct index_state *istate;
469         struct lazy_entry *lazy_entries;
470 };
471
472 static void *lazy_name_thread_proc(void *_data)
473 {
474         struct lazy_name_thread_data *d = _data;
475         int k;
476
477         for (k = 0; k < d->istate->cache_nr; k++) {
478                 struct cache_entry *ce_k = d->istate->cache[k];
479                 ce_k->ce_flags |= CE_HASHED;
480                 hashmap_entry_init(ce_k, d->lazy_entries[k].hash_name);
481                 hashmap_add(&d->istate->name_hash, ce_k);
482         }
483
484         return NULL;
485 }
486
487 static inline void lazy_update_dir_ref_counts(
488         struct index_state *istate,
489         struct lazy_entry *lazy_entries)
490 {
491         int k;
492
493         for (k = 0; k < istate->cache_nr; k++) {
494                 if (lazy_entries[k].dir)
495                         lazy_entries[k].dir->nr++;
496         }
497 }
498
499 static void threaded_lazy_init_name_hash(
500         struct index_state *istate)
501 {
502         int nr_each;
503         int k_start;
504         int t;
505         struct lazy_entry *lazy_entries;
506         struct lazy_dir_thread_data *td_dir;
507         struct lazy_name_thread_data *td_name;
508
509         k_start = 0;
510         nr_each = DIV_ROUND_UP(istate->cache_nr, lazy_nr_dir_threads);
511
512         lazy_entries = xcalloc(istate->cache_nr, sizeof(struct lazy_entry));
513         td_dir = xcalloc(lazy_nr_dir_threads, sizeof(struct lazy_dir_thread_data));
514         td_name = xcalloc(1, sizeof(struct lazy_name_thread_data));
515
516         init_dir_mutex();
517
518         /*
519          * Phase 1:
520          * Build "istate->dir_hash" using n "dir" threads (and a read-only index).
521          */
522         for (t = 0; t < lazy_nr_dir_threads; t++) {
523                 struct lazy_dir_thread_data *td_dir_t = td_dir + t;
524                 td_dir_t->istate = istate;
525                 td_dir_t->lazy_entries = lazy_entries;
526                 td_dir_t->k_start = k_start;
527                 k_start += nr_each;
528                 if (k_start > istate->cache_nr)
529                         k_start = istate->cache_nr;
530                 td_dir_t->k_end = k_start;
531                 if (pthread_create(&td_dir_t->pthread, NULL, lazy_dir_thread_proc, td_dir_t))
532                         die("unable to create lazy_dir_thread");
533         }
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");
538         }
539
540         /*
541          * Phase 2:
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.)
545          *
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.)
549          */
550         td_name->istate = istate;
551         td_name->lazy_entries = lazy_entries;
552         if (pthread_create(&td_name->pthread, NULL, lazy_name_thread_proc, td_name))
553                 die("unable to create lazy_name_thread");
554
555         lazy_update_dir_ref_counts(istate, lazy_entries);
556
557         if (pthread_join(td_name->pthread, NULL))
558                 die("unable to join lazy_name_thread");
559
560         cleanup_dir_mutex();
561
562         free(td_name);
563         free(td_dir);
564         free(lazy_entries);
565 }
566
567 #endif
568
569 static void lazy_init_name_hash(struct index_state *istate)
570 {
571         if (istate->name_hash_initialized)
572                 return;
573         hashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp,
574                         istate->cache_nr);
575         hashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp,
576                         istate->cache_nr);
577
578         if (lookup_lazy_params(istate)) {
579                 hashmap_disallow_rehash(&istate->dir_hash, 1);
580                 threaded_lazy_init_name_hash(istate);
581                 hashmap_disallow_rehash(&istate->dir_hash, 0);
582         } else {
583                 int nr;
584                 for (nr = 0; nr < istate->cache_nr; nr++)
585                         hash_index_entry(istate, istate->cache[nr]);
586         }
587
588         istate->name_hash_initialized = 1;
589 }
590
591 /*
592  * A test routine for t/helper/ sources.
593  *
594  * Returns the number of threads used or 0 when
595  * the non-threaded code path was used.
596  *
597  * Requesting threading WILL NOT override guards
598  * in lookup_lazy_params().
599  */
600 int test_lazy_init_name_hash(struct index_state *istate, int try_threaded)
601 {
602         lazy_nr_dir_threads = 0;
603         lazy_try_threaded = try_threaded;
604
605         lazy_init_name_hash(istate);
606
607         return lazy_nr_dir_threads;
608 }
609
610 void add_name_hash(struct index_state *istate, struct cache_entry *ce)
611 {
612         if (istate->name_hash_initialized)
613                 hash_index_entry(istate, ce);
614 }
615
616 void remove_name_hash(struct index_state *istate, struct cache_entry *ce)
617 {
618         if (!istate->name_hash_initialized || !(ce->ce_flags & CE_HASHED))
619                 return;
620         ce->ce_flags &= ~CE_HASHED;
621         hashmap_remove(&istate->name_hash, ce, ce);
622
623         if (ignore_case)
624                 remove_dir_entry(istate, ce);
625 }
626
627 static int slow_same_name(const char *name1, int len1, const char *name2, int len2)
628 {
629         if (len1 != len2)
630                 return 0;
631
632         while (len1) {
633                 unsigned char c1 = *name1++;
634                 unsigned char c2 = *name2++;
635                 len1--;
636                 if (c1 != c2) {
637                         c1 = toupper(c1);
638                         c2 = toupper(c2);
639                         if (c1 != c2)
640                                 return 0;
641                 }
642         }
643         return 1;
644 }
645
646 static int same_name(const struct cache_entry *ce, const char *name, int namelen, int icase)
647 {
648         int len = ce_namelen(ce);
649
650         /*
651          * Always do exact compare, even if we want a case-ignoring comparison;
652          * we do the quick exact one first, because it will be the common case.
653          */
654         if (len == namelen && !memcmp(name, ce->name, len))
655                 return 1;
656
657         if (!icase)
658                 return 0;
659
660         return slow_same_name(name, namelen, ce->name, len);
661 }
662
663 int index_dir_exists(struct index_state *istate, const char *name, int namelen)
664 {
665         struct dir_entry *dir;
666
667         lazy_init_name_hash(istate);
668         dir = find_dir_entry(istate, name, namelen);
669         return dir && dir->nr;
670 }
671
672 void adjust_dirname_case(struct index_state *istate, char *name)
673 {
674         const char *startPtr = name;
675         const char *ptr = startPtr;
676
677         lazy_init_name_hash(istate);
678         while (*ptr) {
679                 while (*ptr && *ptr != '/')
680                         ptr++;
681
682                 if (*ptr == '/') {
683                         struct dir_entry *dir;
684
685                         ptr++;
686                         dir = find_dir_entry(istate, name, ptr - name + 1);
687                         if (dir) {
688                                 memcpy((void *)startPtr, dir->name + (startPtr - name), ptr - startPtr);
689                                 startPtr = ptr;
690                         }
691                 }
692         }
693 }
694
695 struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase)
696 {
697         struct cache_entry *ce;
698
699         lazy_init_name_hash(istate);
700
701         ce = hashmap_get_from_hash(&istate->name_hash,
702                                    memihash(name, namelen), NULL);
703         while (ce) {
704                 if (same_name(ce, name, namelen, icase))
705                         return ce;
706                 ce = hashmap_get_next(&istate->name_hash, ce);
707         }
708         return NULL;
709 }
710
711 void free_name_hash(struct index_state *istate)
712 {
713         if (!istate->name_hash_initialized)
714                 return;
715         istate->name_hash_initialized = 0;
716
717         hashmap_free(&istate->name_hash, 0);
718         hashmap_free(&istate->dir_hash, 1);
719 }