Merge branch 'kb/perf-trace'
[git] / split-index.c
1 #include "cache.h"
2 #include "split-index.h"
3 #include "ewah/ewok.h"
4
5 struct split_index *init_split_index(struct index_state *istate)
6 {
7         if (!istate->split_index) {
8                 istate->split_index = xcalloc(1, sizeof(*istate->split_index));
9                 istate->split_index->refcount = 1;
10         }
11         return istate->split_index;
12 }
13
14 int read_link_extension(struct index_state *istate,
15                          const void *data_, unsigned long sz)
16 {
17         const unsigned char *data = data_;
18         struct split_index *si;
19         int ret;
20
21         if (sz < 20)
22                 return error("corrupt link extension (too short)");
23         si = init_split_index(istate);
24         hashcpy(si->base_sha1, data);
25         data += 20;
26         sz -= 20;
27         if (!sz)
28                 return 0;
29         si->delete_bitmap = ewah_new();
30         ret = ewah_read_mmap(si->delete_bitmap, data, sz);
31         if (ret < 0)
32                 return error("corrupt delete bitmap in link extension");
33         data += ret;
34         sz -= ret;
35         si->replace_bitmap = ewah_new();
36         ret = ewah_read_mmap(si->replace_bitmap, data, sz);
37         if (ret < 0)
38                 return error("corrupt replace bitmap in link extension");
39         if (ret != sz)
40                 return error("garbage at the end of link extension");
41         return 0;
42 }
43
44 static int write_strbuf(void *user_data, const void *data, size_t len)
45 {
46         struct strbuf *sb = user_data;
47         strbuf_add(sb, data, len);
48         return len;
49 }
50
51 int write_link_extension(struct strbuf *sb,
52                          struct index_state *istate)
53 {
54         struct split_index *si = istate->split_index;
55         strbuf_add(sb, si->base_sha1, 20);
56         if (!si->delete_bitmap && !si->replace_bitmap)
57                 return 0;
58         ewah_serialize_to(si->delete_bitmap, write_strbuf, sb);
59         ewah_serialize_to(si->replace_bitmap, write_strbuf, sb);
60         return 0;
61 }
62
63 static void mark_base_index_entries(struct index_state *base)
64 {
65         int i;
66         /*
67          * To keep track of the shared entries between
68          * istate->base->cache[] and istate->cache[], base entry
69          * position is stored in each base entry. All positions start
70          * from 1 instead of 0, which is resrved to say "this is a new
71          * entry".
72          */
73         for (i = 0; i < base->cache_nr; i++)
74                 base->cache[i]->index = i + 1;
75 }
76
77 void move_cache_to_base_index(struct index_state *istate)
78 {
79         struct split_index *si = istate->split_index;
80         int i;
81
82         /*
83          * do not delete old si->base, its index entries may be shared
84          * with istate->cache[]. Accept a bit of leaking here because
85          * this code is only used by short-lived update-index.
86          */
87         si->base = xcalloc(1, sizeof(*si->base));
88         si->base->version = istate->version;
89         /* zero timestamp disables racy test in ce_write_index() */
90         si->base->timestamp = istate->timestamp;
91         ALLOC_GROW(si->base->cache, istate->cache_nr, si->base->cache_alloc);
92         si->base->cache_nr = istate->cache_nr;
93         memcpy(si->base->cache, istate->cache,
94                sizeof(*istate->cache) * istate->cache_nr);
95         mark_base_index_entries(si->base);
96         for (i = 0; i < si->base->cache_nr; i++)
97                 si->base->cache[i]->ce_flags &= ~CE_UPDATE_IN_BASE;
98 }
99
100 static void mark_entry_for_delete(size_t pos, void *data)
101 {
102         struct index_state *istate = data;
103         if (pos >= istate->cache_nr)
104                 die("position for delete %d exceeds base index size %d",
105                     (int)pos, istate->cache_nr);
106         istate->cache[pos]->ce_flags |= CE_REMOVE;
107         istate->split_index->nr_deletions = 1;
108 }
109
110 static void replace_entry(size_t pos, void *data)
111 {
112         struct index_state *istate = data;
113         struct split_index *si = istate->split_index;
114         struct cache_entry *dst, *src;
115
116         if (pos >= istate->cache_nr)
117                 die("position for replacement %d exceeds base index size %d",
118                     (int)pos, istate->cache_nr);
119         if (si->nr_replacements >= si->saved_cache_nr)
120                 die("too many replacements (%d vs %d)",
121                     si->nr_replacements, si->saved_cache_nr);
122         dst = istate->cache[pos];
123         if (dst->ce_flags & CE_REMOVE)
124                 die("entry %d is marked as both replaced and deleted",
125                     (int)pos);
126         src = si->saved_cache[si->nr_replacements];
127         if (ce_namelen(src))
128                 die("corrupt link extension, entry %d should have "
129                     "zero length name", (int)pos);
130         src->index = pos + 1;
131         src->ce_flags |= CE_UPDATE_IN_BASE;
132         src->ce_namelen = dst->ce_namelen;
133         copy_cache_entry(dst, src);
134         free(src);
135         si->nr_replacements++;
136 }
137
138 void merge_base_index(struct index_state *istate)
139 {
140         struct split_index *si = istate->split_index;
141         unsigned int i;
142
143         mark_base_index_entries(si->base);
144
145         si->saved_cache     = istate->cache;
146         si->saved_cache_nr  = istate->cache_nr;
147         istate->cache_nr    = si->base->cache_nr;
148         istate->cache       = NULL;
149         istate->cache_alloc = 0;
150         ALLOC_GROW(istate->cache, istate->cache_nr, istate->cache_alloc);
151         memcpy(istate->cache, si->base->cache,
152                sizeof(*istate->cache) * istate->cache_nr);
153
154         si->nr_deletions = 0;
155         si->nr_replacements = 0;
156         ewah_each_bit(si->replace_bitmap, replace_entry, istate);
157         ewah_each_bit(si->delete_bitmap, mark_entry_for_delete, istate);
158         if (si->nr_deletions)
159                 remove_marked_cache_entries(istate);
160
161         for (i = si->nr_replacements; i < si->saved_cache_nr; i++) {
162                 if (!ce_namelen(si->saved_cache[i]))
163                         die("corrupt link extension, entry %d should "
164                             "have non-zero length name", i);
165                 add_index_entry(istate, si->saved_cache[i],
166                                 ADD_CACHE_OK_TO_ADD |
167                                 ADD_CACHE_KEEP_CACHE_TREE |
168                                 /*
169                                  * we may have to replay what
170                                  * merge-recursive.c:update_stages()
171                                  * does, which has this flag on
172                                  */
173                                 ADD_CACHE_SKIP_DFCHECK);
174                 si->saved_cache[i] = NULL;
175         }
176
177         ewah_free(si->delete_bitmap);
178         ewah_free(si->replace_bitmap);
179         free(si->saved_cache);
180         si->delete_bitmap  = NULL;
181         si->replace_bitmap = NULL;
182         si->saved_cache    = NULL;
183         si->saved_cache_nr = 0;
184 }
185
186 void prepare_to_write_split_index(struct index_state *istate)
187 {
188         struct split_index *si = init_split_index(istate);
189         struct cache_entry **entries = NULL, *ce;
190         int i, nr_entries = 0, nr_alloc = 0;
191
192         si->delete_bitmap = ewah_new();
193         si->replace_bitmap = ewah_new();
194
195         if (si->base) {
196                 /* Go through istate->cache[] and mark CE_MATCHED to
197                  * entry with positive index. We'll go through
198                  * base->cache[] later to delete all entries in base
199                  * that are not marked eith either CE_MATCHED or
200                  * CE_UPDATE_IN_BASE. If istate->cache[i] is a
201                  * duplicate, deduplicate it.
202                  */
203                 for (i = 0; i < istate->cache_nr; i++) {
204                         struct cache_entry *base;
205                         /* namelen is checked separately */
206                         const unsigned int ondisk_flags =
207                                 CE_STAGEMASK | CE_VALID | CE_EXTENDED_FLAGS;
208                         unsigned int ce_flags, base_flags, ret;
209                         ce = istate->cache[i];
210                         if (!ce->index)
211                                 continue;
212                         if (ce->index > si->base->cache_nr) {
213                                 ce->index = 0;
214                                 continue;
215                         }
216                         ce->ce_flags |= CE_MATCHED; /* or "shared" */
217                         base = si->base->cache[ce->index - 1];
218                         if (ce == base)
219                                 continue;
220                         if (ce->ce_namelen != base->ce_namelen ||
221                             strcmp(ce->name, base->name)) {
222                                 ce->index = 0;
223                                 continue;
224                         }
225                         ce_flags = ce->ce_flags;
226                         base_flags = base->ce_flags;
227                         /* only on-disk flags matter */
228                         ce->ce_flags   &= ondisk_flags;
229                         base->ce_flags &= ondisk_flags;
230                         ret = memcmp(&ce->ce_stat_data, &base->ce_stat_data,
231                                      offsetof(struct cache_entry, name) -
232                                      offsetof(struct cache_entry, ce_stat_data));
233                         ce->ce_flags = ce_flags;
234                         base->ce_flags = base_flags;
235                         if (ret)
236                                 ce->ce_flags |= CE_UPDATE_IN_BASE;
237                         free(base);
238                         si->base->cache[ce->index - 1] = ce;
239                 }
240                 for (i = 0; i < si->base->cache_nr; i++) {
241                         ce = si->base->cache[i];
242                         if ((ce->ce_flags & CE_REMOVE) ||
243                             !(ce->ce_flags & CE_MATCHED))
244                                 ewah_set(si->delete_bitmap, i);
245                         else if (ce->ce_flags & CE_UPDATE_IN_BASE) {
246                                 ewah_set(si->replace_bitmap, i);
247                                 ce->ce_flags |= CE_STRIP_NAME;
248                                 ALLOC_GROW(entries, nr_entries+1, nr_alloc);
249                                 entries[nr_entries++] = ce;
250                         }
251                 }
252         }
253
254         for (i = 0; i < istate->cache_nr; i++) {
255                 ce = istate->cache[i];
256                 if ((!si->base || !ce->index) && !(ce->ce_flags & CE_REMOVE)) {
257                         assert(!(ce->ce_flags & CE_STRIP_NAME));
258                         ALLOC_GROW(entries, nr_entries+1, nr_alloc);
259                         entries[nr_entries++] = ce;
260                 }
261                 ce->ce_flags &= ~CE_MATCHED;
262         }
263
264         /*
265          * take cache[] out temporarily, put entries[] in its place
266          * for writing
267          */
268         si->saved_cache = istate->cache;
269         si->saved_cache_nr = istate->cache_nr;
270         istate->cache = entries;
271         istate->cache_nr = nr_entries;
272 }
273
274 void finish_writing_split_index(struct index_state *istate)
275 {
276         struct split_index *si = init_split_index(istate);
277
278         ewah_free(si->delete_bitmap);
279         ewah_free(si->replace_bitmap);
280         si->delete_bitmap = NULL;
281         si->replace_bitmap = NULL;
282         free(istate->cache);
283         istate->cache = si->saved_cache;
284         istate->cache_nr = si->saved_cache_nr;
285 }
286
287 void discard_split_index(struct index_state *istate)
288 {
289         struct split_index *si = istate->split_index;
290         if (!si)
291                 return;
292         istate->split_index = NULL;
293         si->refcount--;
294         if (si->refcount)
295                 return;
296         if (si->base) {
297                 discard_index(si->base);
298                 free(si->base);
299         }
300         free(si);
301 }
302
303 void save_or_free_index_entry(struct index_state *istate, struct cache_entry *ce)
304 {
305         if (ce->index &&
306             istate->split_index &&
307             istate->split_index->base &&
308             ce->index <= istate->split_index->base->cache_nr &&
309             ce == istate->split_index->base->cache[ce->index - 1])
310                 ce->ce_flags |= CE_REMOVE;
311         else
312                 free(ce);
313 }
314
315 void replace_index_entry_in_base(struct index_state *istate,
316                                  struct cache_entry *old,
317                                  struct cache_entry *new)
318 {
319         if (old->index &&
320             istate->split_index &&
321             istate->split_index->base &&
322             old->index <= istate->split_index->base->cache_nr) {
323                 new->index = old->index;
324                 if (old != istate->split_index->base->cache[new->index - 1])
325                         free(istate->split_index->base->cache[new->index - 1]);
326                 istate->split_index->base->cache[new->index - 1] = new;
327         }
328 }