split-index.c

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