git.oblomov.eu Git - git/blob - 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                 CALLOC_ARRAY(istate->split_index, 1);
   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 < the_hash_algo->rawsz)
  22                 return error("corrupt link extension (too short)");
  23         si = init_split_index(istate);
  24         oidread(&si->base_oid, data);
  25         data += the_hash_algo->rawsz;
  26         sz -= the_hash_algo->rawsz;
  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 int write_link_extension(struct strbuf *sb,
  45                          struct index_state *istate)
  46 {
  47         struct split_index *si = istate->split_index;
  48         strbuf_add(sb, si->base_oid.hash, the_hash_algo->rawsz);
  49         if (!si->delete_bitmap && !si->replace_bitmap)
  50                 return 0;
  51         ewah_serialize_strbuf(si->delete_bitmap, sb);
  52         ewah_serialize_strbuf(si->replace_bitmap, sb);
  53         return 0;
  54 }
  55
  56 static void mark_base_index_entries(struct index_state *base)
  57 {
  58         int i;
  59         /*
  60          * To keep track of the shared entries between
  61          * istate->base->cache[] and istate->cache[], base entry
  62          * position is stored in each base entry. All positions start
  63          * from 1 instead of 0, which is reserved to say "this is a new
  64          * entry".
  65          */
  66         for (i = 0; i < base->cache_nr; i++)
  67                 base->cache[i]->index = i + 1;
  68 }
  69
  70 void move_cache_to_base_index(struct index_state *istate)
  71 {
  72         struct split_index *si = istate->split_index;
  73         int i;
  74
  75         /*
  76          * If there was a previous base index, then transfer ownership of allocated
  77          * entries to the parent index.
  78          */
  79         if (si->base &&
  80                 si->base->ce_mem_pool) {
  81
  82                 if (!istate->ce_mem_pool) {
  83                         istate->ce_mem_pool = xmalloc(sizeof(struct mem_pool));
  84                         mem_pool_init(istate->ce_mem_pool, 0);
  85                 }
  86
  87                 mem_pool_combine(istate->ce_mem_pool, istate->split_index->base->ce_mem_pool);
  88         }
  89
  90         CALLOC_ARRAY(si->base, 1);
  91         si->base->version = istate->version;
  92         /* zero timestamp disables racy test in ce_write_index() */
  93         si->base->timestamp = istate->timestamp;
  94         ALLOC_GROW(si->base->cache, istate->cache_nr, si->base->cache_alloc);
  95         si->base->cache_nr = istate->cache_nr;
  96
  97         /*
  98          * The mem_pool needs to move with the allocated entries.
  99          */
 100         si->base->ce_mem_pool = istate->ce_mem_pool;
 101         istate->ce_mem_pool = NULL;
 102
 103         COPY_ARRAY(si->base->cache, istate->cache, istate->cache_nr);
 104         mark_base_index_entries(si->base);
 105         for (i = 0; i < si->base->cache_nr; i++)
 106                 si->base->cache[i]->ce_flags &= ~CE_UPDATE_IN_BASE;
 107 }
 108
 109 static void mark_entry_for_delete(size_t pos, void *data)
 110 {
 111         struct index_state *istate = data;
 112         if (pos >= istate->cache_nr)
 113                 die("position for delete %d exceeds base index size %d",
 114                     (int)pos, istate->cache_nr);
 115         istate->cache[pos]->ce_flags |= CE_REMOVE;
 116         istate->split_index->nr_deletions++;
 117 }
 118
 119 static void replace_entry(size_t pos, void *data)
 120 {
 121         struct index_state *istate = data;
 122         struct split_index *si = istate->split_index;
 123         struct cache_entry *dst, *src;
 124
 125         if (pos >= istate->cache_nr)
 126                 die("position for replacement %d exceeds base index size %d",
 127                     (int)pos, istate->cache_nr);
 128         if (si->nr_replacements >= si->saved_cache_nr)
 129                 die("too many replacements (%d vs %d)",
 130                     si->nr_replacements, si->saved_cache_nr);
 131         dst = istate->cache[pos];
 132         if (dst->ce_flags & CE_REMOVE)
 133                 die("entry %d is marked as both replaced and deleted",
 134                     (int)pos);
 135         src = si->saved_cache[si->nr_replacements];
 136         if (ce_namelen(src))
 137                 die("corrupt link extension, entry %d should have "
 138                     "zero length name", (int)pos);
 139         src->index = pos + 1;
 140         src->ce_flags |= CE_UPDATE_IN_BASE;
 141         src->ce_namelen = dst->ce_namelen;
 142         copy_cache_entry(dst, src);
 143         discard_cache_entry(src);
 144         si->nr_replacements++;
 145 }
 146
 147 void merge_base_index(struct index_state *istate)
 148 {
 149         struct split_index *si = istate->split_index;
 150         unsigned int i;
 151
 152         mark_base_index_entries(si->base);
 153
 154         si->saved_cache     = istate->cache;
 155         si->saved_cache_nr  = istate->cache_nr;
 156         istate->cache_nr    = si->base->cache_nr;
 157         istate->cache       = NULL;
 158         istate->cache_alloc = 0;
 159         ALLOC_GROW(istate->cache, istate->cache_nr, istate->cache_alloc);
 160         COPY_ARRAY(istate->cache, si->base->cache, istate->cache_nr);
 161
 162         si->nr_deletions = 0;
 163         si->nr_replacements = 0;
 164         ewah_each_bit(si->replace_bitmap, replace_entry, istate);
 165         ewah_each_bit(si->delete_bitmap, mark_entry_for_delete, istate);
 166         if (si->nr_deletions)
 167                 remove_marked_cache_entries(istate, 0);
 168
 169         for (i = si->nr_replacements; i < si->saved_cache_nr; i++) {
 170                 if (!ce_namelen(si->saved_cache[i]))
 171                         die("corrupt link extension, entry %d should "
 172                             "have non-zero length name", i);
 173                 add_index_entry(istate, si->saved_cache[i],
 174                                 ADD_CACHE_OK_TO_ADD |
 175                                 ADD_CACHE_KEEP_CACHE_TREE |
 176                                 /*
 177                                  * we may have to replay what
 178                                  * merge-recursive.c:update_stages()
 179                                  * does, which has this flag on
 180                                  */
 181                                 ADD_CACHE_SKIP_DFCHECK);
 182                 si->saved_cache[i] = NULL;
 183         }
 184
 185         ewah_free(si->delete_bitmap);
 186         ewah_free(si->replace_bitmap);
 187         FREE_AND_NULL(si->saved_cache);
 188         si->delete_bitmap  = NULL;
 189         si->replace_bitmap = NULL;
 190         si->saved_cache_nr = 0;
 191 }
 192
 193 /*
 194  * Compare most of the fields in two cache entries, i.e. all except the
 195  * hashmap_entry and the name.
 196  */
 197 static int compare_ce_content(struct cache_entry *a, struct cache_entry *b)
 198 {
 199         const unsigned int ondisk_flags = CE_STAGEMASK | CE_VALID |
 200                                           CE_EXTENDED_FLAGS;
 201         unsigned int ce_flags = a->ce_flags;
 202         unsigned int base_flags = b->ce_flags;
 203         int ret;
 204
 205         /* only on-disk flags matter */
 206         a->ce_flags &= ondisk_flags;
 207         b->ce_flags &= ondisk_flags;
 208         ret = memcmp(&a->ce_stat_data, &b->ce_stat_data,
 209                      offsetof(struct cache_entry, name) -
 210                      offsetof(struct cache_entry, oid)) ||
 211                 !oideq(&a->oid, &b->oid);
 212         a->ce_flags = ce_flags;
 213         b->ce_flags = base_flags;
 214
 215         return ret;
 216 }
 217
 218 void prepare_to_write_split_index(struct index_state *istate)
 219 {
 220         struct split_index *si = init_split_index(istate);
 221         struct cache_entry **entries = NULL, *ce;
 222         int i, nr_entries = 0, nr_alloc = 0;
 223
 224         si->delete_bitmap = ewah_new();
 225         si->replace_bitmap = ewah_new();
 226
 227         if (si->base) {
 228                 /* Go through istate->cache[] and mark CE_MATCHED to
 229                  * entry with positive index. We'll go through
 230                  * base->cache[] later to delete all entries in base
 231                  * that are not marked with either CE_MATCHED or
 232                  * CE_UPDATE_IN_BASE. If istate->cache[i] is a
 233                  * duplicate, deduplicate it.
 234                  */
 235                 for (i = 0; i < istate->cache_nr; i++) {
 236                         struct cache_entry *base;
 237                         ce = istate->cache[i];
 238                         if (!ce->index) {
 239                                 /*
 240                                  * During simple update index operations this
 241                                  * is a cache entry that is not present in
 242                                  * the shared index.  It will be added to the
 243                                  * split index.
 244                                  *
 245                                  * However, it might also represent a file
 246                                  * that already has a cache entry in the
 247                                  * shared index, but a new index has just
 248                                  * been constructed by unpack_trees(), and
 249                                  * this entry now refers to different content
 250                                  * than what was recorded in the original
 251                                  * index, e.g. during 'read-tree -m HEAD^' or
 252                                  * 'checkout HEAD^'.  In this case the
 253                                  * original entry in the shared index will be
 254                                  * marked as deleted, and this entry will be
 255                                  * added to the split index.
 256                                  */
 257                                 continue;
 258                         }
 259                         if (ce->index > si->base->cache_nr) {
 260                                 BUG("ce refers to a shared ce at %d, which is beyond the shared index size %d",
 261                                     ce->index, si->base->cache_nr);
 262                         }
 263                         ce->ce_flags |= CE_MATCHED; /* or "shared" */
 264                         base = si->base->cache[ce->index - 1];
 265                         if (ce == base) {
 266                                 /* The entry is present in the shared index. */
 267                                 if (ce->ce_flags & CE_UPDATE_IN_BASE) {
 268                                         /*
 269                                          * Already marked for inclusion in
 270                                          * the split index, either because
 271                                          * the corresponding file was
 272                                          * modified and the cached stat data
 273                                          * was refreshed, or because there
 274                                          * is already a replacement entry in
 275                                          * the split index.
 276                                          * Nothing more to do here.
 277                                          */
 278                                 } else if (!ce_uptodate(ce) &&
 279                                            is_racy_timestamp(istate, ce)) {
 280                                         /*
 281                                          * A racily clean cache entry stored
 282                                          * only in the shared index: it must
 283                                          * be added to the split index, so
 284                                          * the subsequent do_write_index()
 285                                          * can smudge its stat data.
 286                                          */
 287                                         ce->ce_flags |= CE_UPDATE_IN_BASE;
 288                                 } else {
 289                                         /*
 290                                          * The entry is only present in the
 291                                          * shared index and it was not
 292                                          * refreshed.
 293                                          * Just leave it there.
 294                                          */
 295                                 }
 296                                 continue;
 297                         }
 298                         if (ce->ce_namelen != base->ce_namelen ||
 299                             strcmp(ce->name, base->name)) {
 300                                 ce->index = 0;
 301                                 continue;
 302                         }
 303                         /*
 304                          * This is the copy of a cache entry that is present
 305                          * in the shared index, created by unpack_trees()
 306                          * while it constructed a new index.
 307                          */
 308                         if (ce->ce_flags & CE_UPDATE_IN_BASE) {
 309                                 /*
 310                                  * Already marked for inclusion in the split
 311                                  * index, either because the corresponding
 312                                  * file was modified and the cached stat data
 313                                  * was refreshed, or because the original
 314                                  * entry already had a replacement entry in
 315                                  * the split index.
 316                                  * Nothing to do.
 317                                  */
 318                         } else if (!ce_uptodate(ce) &&
 319                                    is_racy_timestamp(istate, ce)) {
 320                                 /*
 321                                  * A copy of a racily clean cache entry from
 322                                  * the shared index.  It must be added to
 323                                  * the split index, so the subsequent
 324                                  * do_write_index() can smudge its stat data.
 325                                  */
 326                                 ce->ce_flags |= CE_UPDATE_IN_BASE;
 327                         } else {
 328                                 /*
 329                                  * Thoroughly compare the cached data to see
 330                                  * whether it should be marked for inclusion
 331                                  * in the split index.
 332                                  *
 333                                  * This comparison might be unnecessary, as
 334                                  * code paths modifying the cached data do
 335                                  * set CE_UPDATE_IN_BASE as well.
 336                                  */
 337                                 if (compare_ce_content(ce, base))
 338                                         ce->ce_flags |= CE_UPDATE_IN_BASE;
 339                         }
 340                         discard_cache_entry(base);
 341                         si->base->cache[ce->index - 1] = ce;
 342                 }
 343                 for (i = 0; i < si->base->cache_nr; i++) {
 344                         ce = si->base->cache[i];
 345                         if ((ce->ce_flags & CE_REMOVE) ||
 346                             !(ce->ce_flags & CE_MATCHED))
 347                                 ewah_set(si->delete_bitmap, i);
 348                         else if (ce->ce_flags & CE_UPDATE_IN_BASE) {
 349                                 ewah_set(si->replace_bitmap, i);
 350                                 ce->ce_flags |= CE_STRIP_NAME;
 351                                 ALLOC_GROW(entries, nr_entries+1, nr_alloc);
 352                                 entries[nr_entries++] = ce;
 353                         }
 354                         if (is_null_oid(&ce->oid))
 355                                 istate->drop_cache_tree = 1;
 356                 }
 357         }
 358
 359         for (i = 0; i < istate->cache_nr; i++) {
 360                 ce = istate->cache[i];
 361                 if ((!si->base || !ce->index) && !(ce->ce_flags & CE_REMOVE)) {
 362                         assert(!(ce->ce_flags & CE_STRIP_NAME));
 363                         ALLOC_GROW(entries, nr_entries+1, nr_alloc);
 364                         entries[nr_entries++] = ce;
 365                 }
 366                 ce->ce_flags &= ~CE_MATCHED;
 367         }
 368
 369         /*
 370          * take cache[] out temporarily, put entries[] in its place
 371          * for writing
 372          */
 373         si->saved_cache = istate->cache;
 374         si->saved_cache_nr = istate->cache_nr;
 375         istate->cache = entries;
 376         istate->cache_nr = nr_entries;
 377 }
 378
 379 void finish_writing_split_index(struct index_state *istate)
 380 {
 381         struct split_index *si = init_split_index(istate);
 382
 383         ewah_free(si->delete_bitmap);
 384         ewah_free(si->replace_bitmap);
 385         si->delete_bitmap = NULL;
 386         si->replace_bitmap = NULL;
 387         free(istate->cache);
 388         istate->cache = si->saved_cache;
 389         istate->cache_nr = si->saved_cache_nr;
 390 }
 391
 392 void discard_split_index(struct index_state *istate)
 393 {
 394         struct split_index *si = istate->split_index;
 395         if (!si)
 396                 return;
 397         istate->split_index = NULL;
 398         si->refcount--;
 399         if (si->refcount)
 400                 return;
 401         if (si->base) {
 402                 discard_index(si->base);
 403                 free(si->base);
 404         }
 405         free(si);
 406 }
 407
 408 void save_or_free_index_entry(struct index_state *istate, struct cache_entry *ce)
 409 {
 410         if (ce->index &&
 411             istate->split_index &&
 412             istate->split_index->base &&
 413             ce->index <= istate->split_index->base->cache_nr &&
 414             ce == istate->split_index->base->cache[ce->index - 1])
 415                 ce->ce_flags |= CE_REMOVE;
 416         else
 417                 discard_cache_entry(ce);
 418 }
 419
 420 void replace_index_entry_in_base(struct index_state *istate,
 421                                  struct cache_entry *old_entry,
 422                                  struct cache_entry *new_entry)
 423 {
 424         if (old_entry->index &&
 425             istate->split_index &&
 426             istate->split_index->base &&
 427             old_entry->index <= istate->split_index->base->cache_nr) {
 428                 new_entry->index = old_entry->index;
 429                 if (old_entry != istate->split_index->base->cache[new_entry->index - 1])
 430                         discard_cache_entry(istate->split_index->base->cache[new_entry->index - 1]);
 431                 istate->split_index->base->cache[new_entry->index - 1] = new_entry;
 432         }
 433 }
 434
 435 void add_split_index(struct index_state *istate)
 436 {
 437         if (!istate->split_index) {
 438                 init_split_index(istate);
 439                 istate->cache_changed |= SPLIT_INDEX_ORDERED;
 440         }
 441 }
 442
 443 void remove_split_index(struct index_state *istate)
 444 {
 445         if (istate->split_index) {
 446                 if (istate->split_index->base) {
 447                         /*
 448                          * When removing the split index, we need to move
 449                          * ownership of the mem_pool associated with the
 450                          * base index to the main index. There may be cache entries
 451                          * allocated from the base's memory pool that are shared with
 452                          * the_index.cache[].
 453                          */
 454                         mem_pool_combine(istate->ce_mem_pool,
 455                                          istate->split_index->base->ce_mem_pool);
 456
 457                         /*
 458                          * The split index no longer owns the mem_pool backing
 459                          * its cache array. As we are discarding this index,
 460                          * mark the index as having no cache entries, so it
 461                          * will not attempt to clean up the cache entries or
 462                          * validate them.
 463                          */
 464                         istate->split_index->base->cache_nr = 0;
 465                 }
 466
 467                 /*
 468                  * We can discard the split index because its
 469                  * memory pool has been incorporated into the
 470                  * memory pool associated with the the_index.
 471                  */
 472                 discard_split_index(istate);
 473
 474                 istate->cache_changed |= SOMETHING_CHANGED;
 475         }
 476 }