1 #include "git-compat-util.h"
6 #include "read-cache-ll.h"
7 #include "split-index.h"
11 struct split_index
*init_split_index(struct index_state
*istate
)
13 if (!istate
->split_index
) {
14 if (istate
->sparse_index
)
15 die(_("cannot use split index with a sparse index"));
17 CALLOC_ARRAY(istate
->split_index
, 1);
18 istate
->split_index
->refcount
= 1;
20 return istate
->split_index
;
23 int read_link_extension(struct index_state
*istate
,
24 const void *data_
, unsigned long sz
)
26 const unsigned char *data
= data_
;
27 struct split_index
*si
;
30 if (sz
< the_hash_algo
->rawsz
)
31 return error("corrupt link extension (too short)");
32 si
= init_split_index(istate
);
33 oidread(&si
->base_oid
, data
);
34 data
+= the_hash_algo
->rawsz
;
35 sz
-= the_hash_algo
->rawsz
;
38 si
->delete_bitmap
= ewah_new();
39 ret
= ewah_read_mmap(si
->delete_bitmap
, data
, sz
);
41 return error("corrupt delete bitmap in link extension");
44 si
->replace_bitmap
= ewah_new();
45 ret
= ewah_read_mmap(si
->replace_bitmap
, data
, sz
);
47 return error("corrupt replace bitmap in link extension");
49 return error("garbage at the end of link extension");
53 int write_link_extension(struct strbuf
*sb
,
54 struct index_state
*istate
)
56 struct split_index
*si
= istate
->split_index
;
57 strbuf_add(sb
, si
->base_oid
.hash
, the_hash_algo
->rawsz
);
58 if (!si
->delete_bitmap
&& !si
->replace_bitmap
)
60 ewah_serialize_strbuf(si
->delete_bitmap
, sb
);
61 ewah_serialize_strbuf(si
->replace_bitmap
, sb
);
65 static void mark_base_index_entries(struct index_state
*base
)
69 * To keep track of the shared entries between
70 * istate->base->cache[] and istate->cache[], base entry
71 * position is stored in each base entry. All positions start
72 * from 1 instead of 0, which is reserved to say "this is a new
75 for (i
= 0; i
< base
->cache_nr
; i
++)
76 base
->cache
[i
]->index
= i
+ 1;
79 void move_cache_to_base_index(struct index_state
*istate
)
81 struct split_index
*si
= istate
->split_index
;
85 * If there was a previous base index, then transfer ownership of allocated
86 * entries to the parent index.
89 si
->base
->ce_mem_pool
) {
91 if (!istate
->ce_mem_pool
) {
92 istate
->ce_mem_pool
= xmalloc(sizeof(struct mem_pool
));
93 mem_pool_init(istate
->ce_mem_pool
, 0);
96 mem_pool_combine(istate
->ce_mem_pool
, istate
->split_index
->base
->ce_mem_pool
);
99 ALLOC_ARRAY(si
->base
, 1);
100 index_state_init(si
->base
, istate
->repo
);
101 si
->base
->version
= istate
->version
;
102 /* zero timestamp disables racy test in ce_write_index() */
103 si
->base
->timestamp
= istate
->timestamp
;
104 ALLOC_GROW(si
->base
->cache
, istate
->cache_nr
, si
->base
->cache_alloc
);
105 si
->base
->cache_nr
= istate
->cache_nr
;
108 * The mem_pool needs to move with the allocated entries.
110 si
->base
->ce_mem_pool
= istate
->ce_mem_pool
;
111 istate
->ce_mem_pool
= NULL
;
113 COPY_ARRAY(si
->base
->cache
, istate
->cache
, istate
->cache_nr
);
114 mark_base_index_entries(si
->base
);
115 for (i
= 0; i
< si
->base
->cache_nr
; i
++)
116 si
->base
->cache
[i
]->ce_flags
&= ~CE_UPDATE_IN_BASE
;
119 static void mark_entry_for_delete(size_t pos
, void *data
)
121 struct index_state
*istate
= data
;
122 if (pos
>= istate
->cache_nr
)
123 die("position for delete %d exceeds base index size %d",
124 (int)pos
, istate
->cache_nr
);
125 istate
->cache
[pos
]->ce_flags
|= CE_REMOVE
;
126 istate
->split_index
->nr_deletions
++;
129 static void replace_entry(size_t pos
, void *data
)
131 struct index_state
*istate
= data
;
132 struct split_index
*si
= istate
->split_index
;
133 struct cache_entry
*dst
, *src
;
135 if (pos
>= istate
->cache_nr
)
136 die("position for replacement %d exceeds base index size %d",
137 (int)pos
, istate
->cache_nr
);
138 if (si
->nr_replacements
>= si
->saved_cache_nr
)
139 die("too many replacements (%d vs %d)",
140 si
->nr_replacements
, si
->saved_cache_nr
);
141 dst
= istate
->cache
[pos
];
142 if (dst
->ce_flags
& CE_REMOVE
)
143 die("entry %d is marked as both replaced and deleted",
145 src
= si
->saved_cache
[si
->nr_replacements
];
147 die("corrupt link extension, entry %d should have "
148 "zero length name", (int)pos
);
149 src
->index
= pos
+ 1;
150 src
->ce_flags
|= CE_UPDATE_IN_BASE
;
151 src
->ce_namelen
= dst
->ce_namelen
;
152 copy_cache_entry(dst
, src
);
153 discard_cache_entry(src
);
154 si
->nr_replacements
++;
157 void merge_base_index(struct index_state
*istate
)
159 struct split_index
*si
= istate
->split_index
;
162 mark_base_index_entries(si
->base
);
164 si
->saved_cache
= istate
->cache
;
165 si
->saved_cache_nr
= istate
->cache_nr
;
166 istate
->cache_nr
= si
->base
->cache_nr
;
167 istate
->cache
= NULL
;
168 istate
->cache_alloc
= 0;
169 ALLOC_GROW(istate
->cache
, istate
->cache_nr
, istate
->cache_alloc
);
170 COPY_ARRAY(istate
->cache
, si
->base
->cache
, istate
->cache_nr
);
172 si
->nr_deletions
= 0;
173 si
->nr_replacements
= 0;
174 ewah_each_bit(si
->replace_bitmap
, replace_entry
, istate
);
175 ewah_each_bit(si
->delete_bitmap
, mark_entry_for_delete
, istate
);
176 if (si
->nr_deletions
)
177 remove_marked_cache_entries(istate
, 0);
179 for (i
= si
->nr_replacements
; i
< si
->saved_cache_nr
; i
++) {
180 if (!ce_namelen(si
->saved_cache
[i
]))
181 die("corrupt link extension, entry %d should "
182 "have non-zero length name", i
);
183 add_index_entry(istate
, si
->saved_cache
[i
],
184 ADD_CACHE_OK_TO_ADD
|
185 ADD_CACHE_KEEP_CACHE_TREE
|
187 * we may have to replay what
188 * merge-recursive.c:update_stages()
189 * does, which has this flag on
191 ADD_CACHE_SKIP_DFCHECK
);
192 si
->saved_cache
[i
] = NULL
;
195 ewah_free(si
->delete_bitmap
);
196 ewah_free(si
->replace_bitmap
);
197 FREE_AND_NULL(si
->saved_cache
);
198 si
->delete_bitmap
= NULL
;
199 si
->replace_bitmap
= NULL
;
200 si
->saved_cache_nr
= 0;
204 * Compare most of the fields in two cache entries, i.e. all except the
205 * hashmap_entry and the name.
207 static int compare_ce_content(struct cache_entry
*a
, struct cache_entry
*b
)
209 const unsigned int ondisk_flags
= CE_STAGEMASK
| CE_VALID
|
211 unsigned int ce_flags
= a
->ce_flags
;
212 unsigned int base_flags
= b
->ce_flags
;
215 /* only on-disk flags matter */
216 a
->ce_flags
&= ondisk_flags
;
217 b
->ce_flags
&= ondisk_flags
;
218 ret
= memcmp(&a
->ce_stat_data
, &b
->ce_stat_data
,
219 offsetof(struct cache_entry
, name
) -
220 offsetof(struct cache_entry
, oid
)) ||
221 !oideq(&a
->oid
, &b
->oid
);
222 a
->ce_flags
= ce_flags
;
223 b
->ce_flags
= base_flags
;
228 void prepare_to_write_split_index(struct index_state
*istate
)
230 struct split_index
*si
= init_split_index(istate
);
231 struct cache_entry
**entries
= NULL
, *ce
;
232 int i
, nr_entries
= 0, nr_alloc
= 0;
234 si
->delete_bitmap
= ewah_new();
235 si
->replace_bitmap
= ewah_new();
238 /* Go through istate->cache[] and mark CE_MATCHED to
239 * entry with positive index. We'll go through
240 * base->cache[] later to delete all entries in base
241 * that are not marked with either CE_MATCHED or
242 * CE_UPDATE_IN_BASE. If istate->cache[i] is a
243 * duplicate, deduplicate it.
245 for (i
= 0; i
< istate
->cache_nr
; i
++) {
246 struct cache_entry
*base
;
247 ce
= istate
->cache
[i
];
250 * During simple update index operations this
251 * is a cache entry that is not present in
252 * the shared index. It will be added to the
255 * However, it might also represent a file
256 * that already has a cache entry in the
257 * shared index, but a new index has just
258 * been constructed by unpack_trees(), and
259 * this entry now refers to different content
260 * than what was recorded in the original
261 * index, e.g. during 'read-tree -m HEAD^' or
262 * 'checkout HEAD^'. In this case the
263 * original entry in the shared index will be
264 * marked as deleted, and this entry will be
265 * added to the split index.
269 if (ce
->index
> si
->base
->cache_nr
) {
270 BUG("ce refers to a shared ce at %d, which is beyond the shared index size %d",
271 ce
->index
, si
->base
->cache_nr
);
273 ce
->ce_flags
|= CE_MATCHED
; /* or "shared" */
274 base
= si
->base
->cache
[ce
->index
- 1];
276 /* The entry is present in the shared index. */
277 if (ce
->ce_flags
& CE_UPDATE_IN_BASE
) {
279 * Already marked for inclusion in
280 * the split index, either because
281 * the corresponding file was
282 * modified and the cached stat data
283 * was refreshed, or because there
284 * is already a replacement entry in
286 * Nothing more to do here.
288 } else if (!ce_uptodate(ce
) &&
289 is_racy_timestamp(istate
, ce
)) {
291 * A racily clean cache entry stored
292 * only in the shared index: it must
293 * be added to the split index, so
294 * the subsequent do_write_index()
295 * can smudge its stat data.
297 ce
->ce_flags
|= CE_UPDATE_IN_BASE
;
300 * The entry is only present in the
301 * shared index and it was not
303 * Just leave it there.
308 if (ce
->ce_namelen
!= base
->ce_namelen
||
309 strcmp(ce
->name
, base
->name
)) {
314 * This is the copy of a cache entry that is present
315 * in the shared index, created by unpack_trees()
316 * while it constructed a new index.
318 if (ce
->ce_flags
& CE_UPDATE_IN_BASE
) {
320 * Already marked for inclusion in the split
321 * index, either because the corresponding
322 * file was modified and the cached stat data
323 * was refreshed, or because the original
324 * entry already had a replacement entry in
328 } else if (!ce_uptodate(ce
) &&
329 is_racy_timestamp(istate
, ce
)) {
331 * A copy of a racily clean cache entry from
332 * the shared index. It must be added to
333 * the split index, so the subsequent
334 * do_write_index() can smudge its stat data.
336 ce
->ce_flags
|= CE_UPDATE_IN_BASE
;
339 * Thoroughly compare the cached data to see
340 * whether it should be marked for inclusion
341 * in the split index.
343 * This comparison might be unnecessary, as
344 * code paths modifying the cached data do
345 * set CE_UPDATE_IN_BASE as well.
347 if (compare_ce_content(ce
, base
))
348 ce
->ce_flags
|= CE_UPDATE_IN_BASE
;
350 discard_cache_entry(base
);
351 si
->base
->cache
[ce
->index
- 1] = ce
;
353 for (i
= 0; i
< si
->base
->cache_nr
; i
++) {
354 ce
= si
->base
->cache
[i
];
355 if ((ce
->ce_flags
& CE_REMOVE
) ||
356 !(ce
->ce_flags
& CE_MATCHED
))
357 ewah_set(si
->delete_bitmap
, i
);
358 else if (ce
->ce_flags
& CE_UPDATE_IN_BASE
) {
359 ewah_set(si
->replace_bitmap
, i
);
360 ce
->ce_flags
|= CE_STRIP_NAME
;
361 ALLOC_GROW(entries
, nr_entries
+1, nr_alloc
);
362 entries
[nr_entries
++] = ce
;
364 if (is_null_oid(&ce
->oid
))
365 istate
->drop_cache_tree
= 1;
369 for (i
= 0; i
< istate
->cache_nr
; i
++) {
370 ce
= istate
->cache
[i
];
371 if ((!si
->base
|| !ce
->index
) && !(ce
->ce_flags
& CE_REMOVE
)) {
372 assert(!(ce
->ce_flags
& CE_STRIP_NAME
));
373 ALLOC_GROW(entries
, nr_entries
+1, nr_alloc
);
374 entries
[nr_entries
++] = ce
;
376 ce
->ce_flags
&= ~CE_MATCHED
;
380 * take cache[] out temporarily, put entries[] in its place
383 si
->saved_cache
= istate
->cache
;
384 si
->saved_cache_nr
= istate
->cache_nr
;
385 istate
->cache
= entries
;
386 istate
->cache_nr
= nr_entries
;
389 void finish_writing_split_index(struct index_state
*istate
)
391 struct split_index
*si
= init_split_index(istate
);
393 ewah_free(si
->delete_bitmap
);
394 ewah_free(si
->replace_bitmap
);
395 si
->delete_bitmap
= NULL
;
396 si
->replace_bitmap
= NULL
;
398 istate
->cache
= si
->saved_cache
;
399 istate
->cache_nr
= si
->saved_cache_nr
;
402 void discard_split_index(struct index_state
*istate
)
404 struct split_index
*si
= istate
->split_index
;
407 istate
->split_index
= NULL
;
412 discard_index(si
->base
);
418 void save_or_free_index_entry(struct index_state
*istate
, struct cache_entry
*ce
)
421 istate
->split_index
&&
422 istate
->split_index
->base
&&
423 ce
->index
<= istate
->split_index
->base
->cache_nr
&&
424 ce
== istate
->split_index
->base
->cache
[ce
->index
- 1])
425 ce
->ce_flags
|= CE_REMOVE
;
427 discard_cache_entry(ce
);
430 void replace_index_entry_in_base(struct index_state
*istate
,
431 struct cache_entry
*old_entry
,
432 struct cache_entry
*new_entry
)
434 if (old_entry
->index
&&
435 istate
->split_index
&&
436 istate
->split_index
->base
&&
437 old_entry
->index
<= istate
->split_index
->base
->cache_nr
) {
438 new_entry
->index
= old_entry
->index
;
439 if (old_entry
!= istate
->split_index
->base
->cache
[new_entry
->index
- 1])
440 discard_cache_entry(istate
->split_index
->base
->cache
[new_entry
->index
- 1]);
441 istate
->split_index
->base
->cache
[new_entry
->index
- 1] = new_entry
;
445 void add_split_index(struct index_state
*istate
)
447 if (!istate
->split_index
) {
448 init_split_index(istate
);
449 istate
->cache_changed
|= SPLIT_INDEX_ORDERED
;
453 void remove_split_index(struct index_state
*istate
)
455 if (istate
->split_index
) {
456 if (istate
->split_index
->base
) {
458 * When removing the split index, we need to move
459 * ownership of the mem_pool associated with the
460 * base index to the main index. There may be cache entries
461 * allocated from the base's memory pool that are shared with
464 mem_pool_combine(istate
->ce_mem_pool
,
465 istate
->split_index
->base
->ce_mem_pool
);
468 * The split index no longer owns the mem_pool backing
469 * its cache array. As we are discarding this index,
470 * mark the index as having no cache entries, so it
471 * will not attempt to clean up the cache entries or
474 istate
->split_index
->base
->cache_nr
= 0;
478 * We can discard the split index because its
479 * memory pool has been incorporated into the
480 * memory pool associated with the the_index.
482 discard_split_index(istate
);
484 istate
->cache_changed
|= SOMETHING_CHANGED
;