src/ipc/StoreMap.cc

   1 /*
   2  * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 /* DEBUG: section 54    Interprocess Communication */
  10
  11 #include "squid.h"
  12 #include "ipc/StoreMap.h"
  13 #include "sbuf/SBuf.h"
  14 #include "Store.h"
  15 #include "store/Controller.h"
  16 #include "store_key_md5.h"
  17 #include "tools.h"
  18
  19 static SBuf
  20 StoreMapSlicesId(const SBuf &path)
  21 {
  22     return Ipc::Mem::Segment::Name(path, "slices");
  23 }
  24
  25 static SBuf
  26 StoreMapAnchorsId(const SBuf &path)
  27 {
  28     return Ipc::Mem::Segment::Name(path, "anchors");
  29 }
  30
  31 static SBuf
  32 StoreMapFileNosId(const SBuf &path)
  33 {
  34     return Ipc::Mem::Segment::Name(path, "filenos");
  35 }
  36
  37 Ipc::StoreMap::Owner *
  38 Ipc::StoreMap::Init(const SBuf &path, const int sliceLimit)
  39 {
  40     assert(sliceLimit > 0); // we should not be created otherwise
  41     const int anchorLimit = min(sliceLimit, static_cast<int>(SwapFilenMax));
  42     Owner *owner = new Owner;
  43     owner->fileNos = shm_new(FileNos)(StoreMapFileNosId(path).c_str(), anchorLimit);
  44     owner->anchors = shm_new(Anchors)(StoreMapAnchorsId(path).c_str(), anchorLimit);
  45     owner->slices = shm_new(Slices)(StoreMapSlicesId(path).c_str(), sliceLimit);
  46     debugs(54, 5, "created " << path << " with " << anchorLimit << '+' << sliceLimit);
  47     return owner;
  48 }
  49
  50 Ipc::StoreMap::StoreMap(const SBuf &aPath): cleaner(NULL), path(aPath),
  51     fileNos(shm_old(FileNos)(StoreMapFileNosId(path).c_str())),
  52     anchors(shm_old(Anchors)(StoreMapAnchorsId(path).c_str())),
  53     slices(shm_old(Slices)(StoreMapSlicesId(path).c_str()))
  54 {
  55     debugs(54, 5, "attached " << path << " with " <<
  56            fileNos->capacity << '+' <<
  57            anchors->capacity << '+' << slices->capacity);
  58     assert(entryLimit() > 0); // key-to-position mapping requires this
  59     assert(entryLimit() <= sliceLimit()); // at least one slice per entry
  60 }
  61
  62 int
  63 Ipc::StoreMap::compareVersions(const sfileno fileno, time_t newVersion) const
  64 {
  65     const Anchor &inode = anchorAt(fileno);
  66
  67     // note: we do not lock, so comparison may be inacurate
  68
  69     if (inode.empty())
  70         return +2;
  71
  72     if (const time_t diff = newVersion - inode.basics.timestamp)
  73         return diff < 0 ? -1 : +1;
  74
  75     return 0;
  76 }
  77
  78 void
  79 Ipc::StoreMap::forgetWritingEntry(sfileno fileno)
  80 {
  81     Anchor &inode = anchorAt(fileno);
  82
  83     assert(inode.writing());
  84
  85     // we do not iterate slices because we were told to forget about
  86     // them; the caller is responsible for freeing them (most likely
  87     // our slice list is incomplete or has holes)
  88
  89     inode.rewind();
  90
  91     inode.lock.unlockExclusive();
  92     --anchors->count;
  93
  94     debugs(54, 8, "closed entry " << fileno << " for writing " << path);
  95 }
  96
  97 const Ipc::StoreMap::Anchor *
  98 Ipc::StoreMap::openOrCreateForReading(const cache_key *const key, sfileno &fileno, const StoreEntry &entry)
  99 {
 100     debugs(54, 5, "opening/creating entry with key " << storeKeyText(key)
 101            << " for reading " << path);
 102
 103     // start with reading so that we do not overwrite an existing unlocked entry
 104     auto idx = fileNoByKey(key);
 105     if (const auto anchor = openForReadingAt(idx, key)) {
 106         fileno = idx;
 107         return anchor;
 108     }
 109
 110     // the competing openOrCreateForReading() workers race to create a new entry
 111     idx = fileNoByKey(key);
 112     if (auto anchor = openForWritingAt(idx)) {
 113         anchor->set(entry, key);
 114         anchor->lock.switchExclusiveToShared();
 115         // race ended
 116         assert(anchor->complete());
 117         fileno = idx;
 118         debugs(54, 5, "switched entry " << fileno << " from writing to reading " << path);
 119         return anchor;
 120     }
 121
 122     // we lost the above race; see if the winner-created entry is now readable
 123     // TODO: Do some useful housekeeping work here to give the winner more time.
 124     idx = fileNoByKey(key);
 125     if (const auto anchor = openForReadingAt(idx, key)) {
 126         fileno = idx;
 127         return anchor;
 128     }
 129
 130     // slow entry creator or some other problem
 131     return nullptr;
 132 }
 133
 134 Ipc::StoreMap::Anchor *
 135 Ipc::StoreMap::openForWriting(const cache_key *const key, sfileno &fileno)
 136 {
 137     debugs(54, 5, "opening entry with key " << storeKeyText(key)
 138            << " for writing " << path);
 139     const int idx = fileNoByKey(key);
 140
 141     if (Anchor *anchor = openForWritingAt(idx)) {
 142         fileno = idx;
 143         return anchor;
 144     }
 145
 146     return NULL;
 147 }
 148
 149 Ipc::StoreMap::Anchor *
 150 Ipc::StoreMap::openForWritingAt(const sfileno fileno, bool overwriteExisting)
 151 {
 152     Anchor &s = anchorAt(fileno);
 153     ReadWriteLock &lock = s.lock;
 154
 155     if (lock.lockExclusive()) {
 156         assert(s.writing() && !s.reading());
 157
 158         // bail if we cannot empty this position
 159         if (!s.waitingToBeFreed && !s.empty() && !overwriteExisting) {
 160             lock.unlockExclusive();
 161             debugs(54, 5, "cannot open existing entry " << fileno <<
 162                    " for writing " << path);
 163             return NULL;
 164         }
 165
 166         // free if the entry was used, keeping the entry locked
 167         if (s.waitingToBeFreed || !s.empty())
 168             freeChain(fileno, s, true);
 169
 170         assert(s.empty());
 171         s.start = -1; // we have not allocated any slices yet
 172         s.splicingPoint = -1;
 173         ++anchors->count;
 174
 175         //s.setKey(key); // XXX: the caller should do that
 176         debugs(54, 5, "opened entry " << fileno << " for writing " << path);
 177         return &s; // and keep the entry locked
 178     }
 179
 180     debugs(54, 5, "cannot open busy entry " << fileno <<
 181            " for writing " << path);
 182     return NULL;
 183 }
 184
 185 void
 186 Ipc::StoreMap::startAppending(const sfileno fileno)
 187 {
 188     Anchor &s = anchorAt(fileno);
 189     assert(s.writing());
 190     s.lock.startAppending();
 191     debugs(54, 5, "restricted entry " << fileno << " to appending " << path);
 192 }
 193
 194 void
 195 Ipc::StoreMap::closeForWriting(const sfileno fileno)
 196 {
 197     Anchor &s = anchorAt(fileno);
 198     assert(s.writing());
 199     // TODO: assert(!s.empty()); // i.e., unlocked s becomes s.complete()
 200     s.lock.unlockExclusive();
 201     debugs(54, 5, "closed entry " << fileno << " for writing " << path);
 202     // cannot assert completeness here because we have no lock
 203 }
 204
 205 void
 206 Ipc::StoreMap::switchWritingToReading(const sfileno fileno)
 207 {
 208     debugs(54, 5, "switching entry " << fileno << " from writing to reading " << path);
 209     Anchor &s = anchorAt(fileno);
 210     assert(s.writing());
 211     s.lock.switchExclusiveToShared();
 212     assert(s.complete());
 213 }
 214
 215 Ipc::StoreMap::Slice &
 216 Ipc::StoreMap::writeableSlice(const AnchorId anchorId, const SliceId sliceId)
 217 {
 218     assert(anchorAt(anchorId).writing());
 219     assert(validSlice(sliceId));
 220     return sliceAt(sliceId);
 221 }
 222
 223 const Ipc::StoreMap::Slice &
 224 Ipc::StoreMap::readableSlice(const AnchorId anchorId, const SliceId sliceId) const
 225 {
 226     assert(anchorAt(anchorId).reading());
 227     assert(validSlice(sliceId));
 228     return sliceAt(sliceId);
 229 }
 230
 231 Ipc::StoreMap::Anchor &
 232 Ipc::StoreMap::writeableEntry(const AnchorId anchorId)
 233 {
 234     assert(anchorAt(anchorId).writing());
 235     return anchorAt(anchorId);
 236 }
 237
 238 const Ipc::StoreMap::Anchor &
 239 Ipc::StoreMap::readableEntry(const AnchorId anchorId) const
 240 {
 241     assert(anchorAt(anchorId).reading());
 242     return anchorAt(anchorId);
 243 }
 244
 245 void
 246 Ipc::StoreMap::abortWriting(const sfileno fileno)
 247 {
 248     debugs(54, 5, "aborting entry " << fileno << " for writing " << path);
 249     Anchor &s = anchorAt(fileno);
 250     assert(s.writing());
 251     s.lock.appending = false; // locks out any new readers
 252     if (!s.lock.readers) {
 253         freeChain(fileno, s, false);
 254         debugs(54, 5, "closed clean entry " << fileno << " for writing " << path);
 255     } else {
 256         s.waitingToBeFreed = true;
 257         s.writerHalted = true;
 258         s.lock.unlockExclusive();
 259         debugs(54, 5, "closed dirty entry " << fileno << " for writing " << path);
 260     }
 261 }
 262
 263 void
 264 Ipc::StoreMap::abortUpdating(Update &update)
 265 {
 266     const sfileno fileno = update.stale.fileNo;
 267     debugs(54, 5, "aborting entry " << fileno << " for updating " << path);
 268     if (update.stale) {
 269         AssertFlagIsSet(update.stale.anchor->lock.updating);
 270         update.stale.anchor->lock.unlockHeaders();
 271         closeForReading(update.stale.fileNo);
 272         update.stale = Update::Edition();
 273     }
 274     if (update.fresh) {
 275         abortWriting(update.fresh.fileNo);
 276         update.fresh = Update::Edition();
 277     }
 278     debugs(54, 5, "aborted entry " << fileno << " for updating " << path);
 279 }
 280
 281 const Ipc::StoreMap::Anchor *
 282 Ipc::StoreMap::peekAtReader(const sfileno fileno) const
 283 {
 284     const Anchor &s = anchorAt(fileno);
 285     if (s.reading())
 286         return &s; // immediate access by lock holder so no locking
 287     assert(s.writing()); // must be locked for reading or writing
 288     return nullptr;
 289 }
 290
 291 const Ipc::StoreMap::Anchor *
 292 Ipc::StoreMap::peekAtWriter(const sfileno fileno) const
 293 {
 294     const Anchor &s = anchorAt(fileno);
 295     if (s.writing())
 296         return &s; // immediate access by lock holder so no locking
 297     assert(s.reading()); // must be locked for reading or writing
 298     return nullptr;
 299 }
 300
 301 const Ipc::StoreMap::Anchor &
 302 Ipc::StoreMap::peekAtEntry(const sfileno fileno) const
 303 {
 304     return anchorAt(fileno);
 305 }
 306
 307 bool
 308 Ipc::StoreMap::freeEntry(const sfileno fileno)
 309 {
 310     debugs(54, 5, "marking entry " << fileno << " to be freed in " << path);
 311
 312     Anchor &s = anchorAt(fileno);
 313
 314     if (s.lock.lockExclusive()) {
 315         const bool result = !s.waitingToBeFreed && !s.empty();
 316         freeChain(fileno, s, false);
 317         return result;
 318     }
 319
 320     uint8_t expected = false;
 321     // mark to free the locked entry later (if not already marked)
 322     return s.waitingToBeFreed.compare_exchange_strong(expected, true);
 323 }
 324
 325 void
 326 Ipc::StoreMap::freeEntryByKey(const cache_key *const key)
 327 {
 328     debugs(54, 5, "marking entry with key " << storeKeyText(key)
 329            << " to be freed in " << path);
 330
 331     const int idx = fileNoByKey(key);
 332     Anchor &s = anchorAt(idx);
 333     if (s.lock.lockExclusive()) {
 334         if (s.sameKey(key))
 335             freeChain(idx, s, true);
 336         s.lock.unlockExclusive();
 337     } else if (s.lock.lockShared()) {
 338         if (s.sameKey(key))
 339             s.waitingToBeFreed = true; // mark to free it later
 340         s.lock.unlockShared();
 341     } else {
 342         // we cannot be sure that the entry we found is ours because we do not
 343         // have a lock on it, but we still check to minimize false deletions
 344         if (s.sameKey(key))
 345             s.waitingToBeFreed = true; // mark to free it later
 346     }
 347 }
 348
 349 bool
 350 Ipc::StoreMap::markedForDeletion(const cache_key *const key)
 351 {
 352     const int idx = fileNoByKey(key);
 353     const Anchor &s = anchorAt(idx);
 354     return s.sameKey(key) ? bool(s.waitingToBeFreed) : false;
 355 }
 356
 357 bool
 358 Ipc::StoreMap::hasReadableEntry(const cache_key *const key)
 359 {
 360     sfileno index;
 361     if (openForReading(reinterpret_cast<const cache_key*>(key), index)) {
 362         closeForReading(index);
 363         return true;
 364     }
 365     return false;
 366 }
 367
 368 /// unconditionally frees an already locked chain of slots, unlocking if needed
 369 void
 370 Ipc::StoreMap::freeChain(const sfileno fileno, Anchor &inode, const bool keepLocked)
 371 {
 372     debugs(54, 7, "freeing entry " << fileno <<
 373            " in " << path);
 374     if (!inode.empty())
 375         freeChainAt(inode.start, inode.splicingPoint);
 376     inode.rewind();
 377
 378     if (!keepLocked)
 379         inode.lock.unlockExclusive();
 380     --anchors->count;
 381     debugs(54, 5, "freed entry " << fileno << " in " << path);
 382 }
 383
 384 /// unconditionally frees an already locked chain of slots; no anchor maintenance
 385 void
 386 Ipc::StoreMap::freeChainAt(SliceId sliceId, const SliceId splicingPoint)
 387 {
 388     static uint64_t ChainId = 0; // to pair freeing/freed calls in debugs()
 389     const uint64_t chainId = ++ChainId;
 390     debugs(54, 7, "freeing chain #" << chainId << " starting at " << sliceId << " in " << path);
 391     while (sliceId >= 0) {
 392         Slice &slice = sliceAt(sliceId);
 393         const SliceId nextId = slice.next;
 394         slice.clear();
 395         if (cleaner)
 396             cleaner->noteFreeMapSlice(sliceId); // might change slice state
 397         if (sliceId == splicingPoint) {
 398             debugs(54, 5, "preserving chain #" << chainId << " in " << path <<
 399                    " suffix after slice " << splicingPoint);
 400             break; // do not free the rest of the chain
 401         }
 402         sliceId = nextId;
 403     }
 404     debugs(54, 7, "freed chain #" << chainId << " in " << path);
 405 }
 406
 407 void
 408 Ipc::StoreMap::prepFreeSlice(const SliceId sliceId)
 409 {
 410     // TODO: Move freeSlots here, along with reserveSlotForWriting() logic.
 411     assert(validSlice(sliceId));
 412     sliceAt(sliceId).clear();
 413 }
 414
 415 Ipc::StoreMap::SliceId
 416 Ipc::StoreMap::sliceContaining(const sfileno fileno, const uint64_t bytesNeeded) const
 417 {
 418     const Anchor &anchor = anchorAt(fileno);
 419     Must(anchor.reading());
 420     uint64_t bytesSeen = 0;
 421     SliceId lastSlice = anchor.start;
 422     while (lastSlice >= 0) {
 423         const Slice &slice = sliceAt(lastSlice);
 424         bytesSeen += slice.size;
 425         if (bytesSeen >= bytesNeeded)
 426             break;
 427         lastSlice = slice.next;
 428     }
 429     debugs(54, 7, "entry " << fileno << " has " << bytesNeeded << '/' << bytesSeen <<
 430            " bytes at slice " << lastSlice << " in " << path);
 431     return lastSlice; // may be negative
 432 }
 433
 434 const Ipc::StoreMap::Anchor *
 435 Ipc::StoreMap::openForReading(const cache_key *const key, sfileno &fileno)
 436 {
 437     debugs(54, 5, "opening entry with key " << storeKeyText(key)
 438            << " for reading " << path);
 439     const int idx = fileNoByKey(key);
 440     if (const auto anchor = openForReadingAt(idx, key)) {
 441         fileno = idx;
 442         return anchor; // locked for reading
 443     }
 444     return NULL;
 445 }
 446
 447 const Ipc::StoreMap::Anchor *
 448 Ipc::StoreMap::openForReadingAt(const sfileno fileno, const cache_key *const key)
 449 {
 450     debugs(54, 5, "opening entry " << fileno << " for reading " << path);
 451     Anchor &s = anchorAt(fileno);
 452
 453     if (!s.lock.lockShared()) {
 454         debugs(54, 5, "cannot open busy entry " << fileno <<
 455                " for reading " << path);
 456         return NULL;
 457     }
 458
 459     if (s.empty()) {
 460         s.lock.unlockShared();
 461         debugs(54, 7, "cannot open empty entry " << fileno <<
 462                " for reading " << path);
 463         return NULL;
 464     }
 465
 466     if (s.waitingToBeFreed) {
 467         s.lock.unlockShared();
 468         debugs(54, 7, "cannot open marked entry " << fileno <<
 469                " for reading " << path);
 470         return NULL;
 471     }
 472
 473     if (!s.sameKey(key)) {
 474         s.lock.unlockShared();
 475         debugs(54, 5, "cannot open wrong-key entry " << fileno <<
 476                " for reading " << path);
 477         return nullptr;
 478     }
 479
 480     debugs(54, 5, "opened entry " << fileno << " for reading " << path);
 481     return &s;
 482 }
 483
 484 void
 485 Ipc::StoreMap::closeForReading(const sfileno fileno)
 486 {
 487     Anchor &s = anchorAt(fileno);
 488     assert(s.reading());
 489     s.lock.unlockShared();
 490     debugs(54, 5, "closed entry " << fileno << " for reading " << path);
 491 }
 492
 493 void
 494 Ipc::StoreMap::closeForReadingAndFreeIdle(const sfileno fileno)
 495 {
 496     auto &s = anchorAt(fileno);
 497     assert(s.reading());
 498
 499     if (!s.lock.unlockSharedAndSwitchToExclusive()) {
 500         debugs(54, 5, "closed entry " << fileno << " for reading " << path);
 501         return;
 502     }
 503
 504     assert(s.writing());
 505     assert(!s.reading());
 506     freeChain(fileno, s, false);
 507     debugs(54, 5, "closed idle entry " << fileno << " for reading " << path);
 508 }
 509
 510 bool
 511 Ipc::StoreMap::openForUpdating(Update &update, const sfileno fileNoHint)
 512 {
 513     Must(update.entry);
 514     const StoreEntry &entry = *update.entry;
 515     const cache_key *const key = reinterpret_cast<const cache_key*>(entry.key);
 516     update.stale.name = nameByKey(key);
 517
 518     if (!validEntry(fileNoHint)) {
 519         debugs(54, 5, "opening entry with key " << storeKeyText(key) <<
 520                " for updating " << path);
 521         update.stale.fileNo = fileNoByName(update.stale.name);
 522     } else {
 523         update.stale.fileNo = fileNoHint;
 524     }
 525
 526     debugs(54, 5, "opening entry " << update.stale.fileNo << " of " << entry << " for updating " << path);
 527
 528     // Unreadable entries cannot (e.g., empty and otherwise problematic entries)
 529     // or should not (e.g., entries still forming their metadata) be updated.
 530     if (!openForReadingAt(update.stale.fileNo, key)) {
 531         debugs(54, 5, "cannot open unreadable entry " << update.stale.fileNo << " for updating " << path);
 532         return false;
 533     }
 534
 535     update.stale.anchor = &anchorAt(update.stale.fileNo);
 536     if (update.stale.anchor->writing()) {
 537         // TODO: Support updating appending entries.
 538         // For example, MemStore::updateHeaders() would not know how
 539         // many old prefix body bytes to copy to the new prefix if the last old
 540         // prefix slice has not been formed yet (i.e., still gets more bytes).
 541         debugs(54, 5, "cannot open appending entry " << update.stale.fileNo <<
 542                " for updating " << path);
 543         closeForReading(update.stale.fileNo);
 544         return false;
 545     }
 546
 547     if (!update.stale.anchor->lock.lockHeaders()) {
 548         debugs(54, 5, "cannot open updating entry " << update.stale.fileNo <<
 549                " for updating " << path);
 550         closeForReading(update.stale.fileNo);
 551         return false;
 552     }
 553
 554     /* stale anchor is properly locked; we can now use abortUpdating() if needed */
 555
 556     if (!openKeyless(update.fresh)) {
 557         debugs(54, 5, "cannot open freshchainless entry " << update.stale.fileNo <<
 558                " for updating " << path);
 559         abortUpdating(update);
 560         return false;
 561     }
 562
 563     Must(update.stale);
 564     Must(update.fresh);
 565     update.fresh.anchor->set(entry);
 566     debugs(54, 5, "opened entry " << update.stale.fileNo << " for updating " << path <<
 567            " using entry " << update.fresh.fileNo << " of " << entry);
 568
 569     return true;
 570 }
 571
 572 /// finds an anchor that is currently not associated with any entry key and
 573 /// locks it for writing so ensure exclusive access during updates
 574 bool
 575 Ipc::StoreMap::openKeyless(Update::Edition &edition)
 576 {
 577     return visitVictims([&](const sfileno name) {
 578         Update::Edition temp;
 579         temp.name = name;
 580         temp.fileNo = fileNoByName(temp.name);
 581         if ((temp.anchor = openForWritingAt(temp.fileNo))) {
 582             debugs(54, 5, "created entry " << temp.fileNo <<
 583                    " for updating " << path);
 584             Must(temp);
 585             edition = temp;
 586             return true;
 587         }
 588         return false;
 589     });
 590 }
 591
 592 void
 593 Ipc::StoreMap::closeForUpdating(Update &update)
 594 {
 595     Must(update.stale.anchor);
 596     Must(update.fresh.anchor);
 597     AssertFlagIsSet(update.stale.anchor->lock.updating);
 598     Must(update.stale.splicingPoint >= 0);
 599     Must(update.fresh.splicingPoint >= 0);
 600
 601     /* the stale prefix cannot overlap with the fresh one (a weak check) */
 602     Must(update.stale.anchor->start != update.fresh.anchor->start);
 603     Must(update.stale.anchor->start != update.fresh.splicingPoint);
 604     Must(update.stale.splicingPoint != update.fresh.anchor->start);
 605     Must(update.stale.splicingPoint != update.fresh.splicingPoint);
 606
 607     /* the relative order of most operations is significant here */
 608
 609     /* splice the fresh chain prefix with the stale chain suffix */
 610     Slice &freshSplicingSlice = sliceAt(update.fresh.splicingPoint);
 611     const SliceId suffixStart = sliceAt(update.stale.splicingPoint).next; // may be negative
 612     // the fresh chain is either properly terminated or already spliced
 613     if (freshSplicingSlice.next < 0)
 614         freshSplicingSlice.next = suffixStart;
 615     else
 616         Must(freshSplicingSlice.next == suffixStart);
 617     // either way, fresh chain uses the stale chain suffix now
 618
 619     // make the fresh anchor/chain readable for everybody
 620     update.fresh.anchor->lock.switchExclusiveToShared();
 621     // but the fresh anchor is still invisible to anybody but us
 622
 623     // This freeEntry() code duplicates the code below to minimize the time when
 624     // the freeEntry() race condition (see the Race: comment below) might occur.
 625     if (update.stale.anchor->waitingToBeFreed)
 626         freeEntry(update.fresh.fileNo);
 627
 628     /* any external changes were applied to the stale anchor/chain until now */
 629     relocate(update.stale.name, update.fresh.fileNo);
 630     /* any external changes will apply to the fresh anchor/chain from now on */
 631
 632     // Race: If the stale entry was deleted by some kid during the assignment,
 633     // then we propagate that event to the fresh anchor and chain. Since this
 634     // update is not atomically combined with the assignment above, another kid
 635     // might get a fresh entry just before we have a chance to free it. However,
 636     // such deletion races are always possible even without updates.
 637     if (update.stale.anchor->waitingToBeFreed)
 638         freeEntry(update.fresh.fileNo);
 639
 640     /* free the stale chain prefix except for the shared suffix */
 641     update.stale.anchor->splicingPoint = update.stale.splicingPoint;
 642     freeEntry(update.stale.fileNo);
 643
 644     // Make the stale anchor/chain reusable, reachable via update.fresh.name. If
 645     // update.entry->swap_filen is still update.stale.fileNo, and the entry is
 646     // using store, then the entry must have a lock on update.stale.fileNo,
 647     // preventing its premature reuse by others.
 648     relocate(update.fresh.name, update.stale.fileNo);
 649
 650     const Update updateSaved = update; // for post-close debugging below
 651
 652     /* unlock the stale anchor/chain */
 653     update.stale.anchor->lock.unlockHeaders();
 654     closeForReading(update.stale.fileNo);
 655     update.stale = Update::Edition();
 656
 657     // finally, unlock the fresh entry
 658     closeForReading(update.fresh.fileNo);
 659     update.fresh = Update::Edition();
 660
 661     debugs(54, 5, "closed entry " << updateSaved.stale.fileNo << " of " << *updateSaved.entry <<
 662            " named " << updateSaved.stale.name << " for updating " << path <<
 663            " to fresh entry " << updateSaved.fresh.fileNo << " named " << updateSaved.fresh.name <<
 664            " with [" << updateSaved.fresh.anchor->start << ',' << updateSaved.fresh.splicingPoint <<
 665            "] prefix containing at least " << freshSplicingSlice.size << " bytes");
 666 }
 667
 668 /// Visits entries until either
 669 /// * the `visitor` returns true (indicating its satisfaction with the offer);
 670 /// * we give up finding a suitable entry because it already took "too long"; or
 671 /// * we have offered all entries.
 672 bool
 673 Ipc::StoreMap::visitVictims(const NameFilter visitor)
 674 {
 675     // Hopefully, we find a usable entry much sooner (TODO: use time?).
 676     // The min() will protect us from division by zero inside the loop.
 677     const int searchLimit = min(10000, entryLimit());
 678     int tries = 0;
 679     for (; tries < searchLimit; ++tries) {
 680         const sfileno name = static_cast<sfileno>(++anchors->victim % entryLimit());
 681         if (visitor(name))
 682             return true;
 683     }
 684
 685     debugs(54, 5, "no victims found in " << path << "; tried: " << tries);
 686     return false;
 687 }
 688
 689 bool
 690 Ipc::StoreMap::purgeOne()
 691 {
 692     return visitVictims([&](const sfileno name) {
 693         const sfileno fileno = fileNoByName(name);
 694         Anchor &s = anchorAt(fileno);
 695         if (s.lock.lockExclusive()) {
 696             // the caller wants a free slice; empty anchor is not enough
 697             if (!s.empty() && s.start >= 0) {
 698                 // this entry may be marked for deletion, and that is OK
 699                 freeChain(fileno, s, false);
 700                 debugs(54, 5, "purged entry " << fileno << " from " << path);
 701                 return true;
 702             }
 703             s.lock.unlockExclusive();
 704         }
 705         return false;
 706     });
 707 }
 708
 709 void
 710 Ipc::StoreMap::importSlice(const SliceId sliceId, const Slice &slice)
 711 {
 712     // Slices are imported into positions that should not be available via
 713     // "get free slice" API. This is not something we can double check
 714     // reliably because the anchor for the imported slice may not have been
 715     // imported yet.
 716     assert(validSlice(sliceId));
 717     sliceAt(sliceId) = slice;
 718 }
 719
 720 int
 721 Ipc::StoreMap::entryLimit() const
 722 {
 723     return min(sliceLimit(), static_cast<int>(SwapFilenMax+1));
 724 }
 725
 726 int
 727 Ipc::StoreMap::entryCount() const
 728 {
 729     return anchors->count;
 730 }
 731
 732 int
 733 Ipc::StoreMap::sliceLimit() const
 734 {
 735     return slices->capacity;
 736 }
 737
 738 void
 739 Ipc::StoreMap::updateStats(ReadWriteLockStats &stats) const
 740 {
 741     for (int i = 0; i < anchors->capacity; ++i)
 742         anchorAt(i).lock.updateStats(stats);
 743 }
 744
 745 bool
 746 Ipc::StoreMap::validEntry(const int pos) const
 747 {
 748     return 0 <= pos && pos < entryLimit();
 749 }
 750
 751 bool
 752 Ipc::StoreMap::validSlice(const int pos) const
 753 {
 754     return 0 <= pos && pos < sliceLimit();
 755 }
 756
 757 Ipc::StoreMap::Anchor&
 758 Ipc::StoreMap::anchorAt(const sfileno fileno)
 759 {
 760     assert(validEntry(fileno));
 761     return anchors->items[fileno];
 762 }
 763
 764 const Ipc::StoreMap::Anchor&
 765 Ipc::StoreMap::anchorAt(const sfileno fileno) const
 766 {
 767     return const_cast<StoreMap&>(*this).anchorAt(fileno);
 768 }
 769
 770 sfileno
 771 Ipc::StoreMap::nameByKey(const cache_key *const key) const
 772 {
 773     assert(key);
 774     const uint64_t *const k = reinterpret_cast<const uint64_t *>(key);
 775     // TODO: use a better hash function
 776     const int hash = (k[0] + k[1]) % entryLimit();
 777     return hash;
 778 }
 779
 780 sfileno
 781 Ipc::StoreMap::fileNoByName(const sfileno name) const
 782 {
 783     // fileNos->items are initialized to zero, which we treat as "name is fileno";
 784     // a positive value means the entry anchor got moved to a new fileNo
 785     if (const int item = fileNos->items[name])
 786         return item-1;
 787     return name;
 788 }
 789
 790 /// map `name` to `fileNo`
 791 void
 792 Ipc::StoreMap::relocate(const sfileno name, const sfileno fileno)
 793 {
 794     // preserve special meaning for zero; see fileNoByName
 795     fileNos->items[name] = fileno+1;
 796 }
 797
 798 sfileno
 799 Ipc::StoreMap::fileNoByKey(const cache_key *const key) const
 800 {
 801     const int name = nameByKey(key);
 802     return fileNoByName(name);
 803 }
 804
 805 Ipc::StoreMap::Anchor &
 806 Ipc::StoreMap::anchorByKey(const cache_key *const key)
 807 {
 808     return anchorAt(fileNoByKey(key));
 809 }
 810
 811 Ipc::StoreMap::Slice&
 812 Ipc::StoreMap::sliceAt(const SliceId sliceId)
 813 {
 814     assert(validSlice(sliceId));
 815     return slices->items[sliceId];
 816 }
 817
 818 const Ipc::StoreMap::Slice&
 819 Ipc::StoreMap::sliceAt(const SliceId sliceId) const
 820 {
 821     return const_cast<StoreMap&>(*this).sliceAt(sliceId);
 822 }
 823
 824 /* Ipc::StoreMapAnchor */
 825
 826 Ipc::StoreMapAnchor::StoreMapAnchor(): start(0), splicingPoint(-1)
 827 {
 828     // keep in sync with rewind()
 829 }
 830
 831 void
 832 Ipc::StoreMapAnchor::setKey(const cache_key *const aKey)
 833 {
 834     memcpy(key, aKey, sizeof(key));
 835     waitingToBeFreed = Store::Root().markedForDeletion(aKey);
 836 }
 837
 838 bool
 839 Ipc::StoreMapAnchor::sameKey(const cache_key *const aKey) const
 840 {
 841     const uint64_t *const k = reinterpret_cast<const uint64_t *>(aKey);
 842     return k[0] == key[0] && k[1] == key[1];
 843 }
 844
 845 void
 846 Ipc::StoreMapAnchor::set(const StoreEntry &from, const cache_key *aKey)
 847 {
 848     assert(writing() && !reading());
 849     setKey(reinterpret_cast<const cache_key*>(aKey ? aKey : from.key));
 850     basics.timestamp = from.timestamp;
 851     basics.lastref = from.lastref;
 852     basics.expires = from.expires;
 853     basics.lastmod = from.lastModified();
 854     basics.swap_file_sz = from.swap_file_sz;
 855     basics.refcount = from.refcount;
 856
 857     // do not copy key bit if we are not using from.key
 858     // TODO: Replace KEY_PRIVATE with a nil StoreEntry::key!
 859     uint16_t cleanFlags = from.flags;
 860     if (aKey)
 861         EBIT_CLR(cleanFlags, KEY_PRIVATE);
 862     basics.flags = cleanFlags;
 863 }
 864
 865 void
 866 Ipc::StoreMapAnchor::exportInto(StoreEntry &into) const
 867 {
 868     assert(reading());
 869     into.timestamp = basics.timestamp;
 870     into.lastref = basics.lastref;
 871     into.expires = basics.expires;
 872     into.lastModified(basics.lastmod);
 873     into.swap_file_sz = basics.swap_file_sz;
 874     into.refcount = basics.refcount;
 875     const bool collapsingRequired = into.hittingRequiresCollapsing();
 876     into.flags = basics.flags;
 877     // There are possibly several flags we do not need to overwrite,
 878     // and ENTRY_REQUIRES_COLLAPSING is one of them.
 879     // TODO: check for other flags.
 880     into.setCollapsingRequirement(collapsingRequired);
 881 }
 882
 883 void
 884 Ipc::StoreMapAnchor::rewind()
 885 {
 886     assert(writing());
 887     start = 0;
 888     splicingPoint = -1;
 889     memset(&key, 0, sizeof(key));
 890     basics.clear();
 891     waitingToBeFreed = false;
 892     writerHalted = false;
 893     // but keep the lock
 894 }
 895
 896 /* Ipc::StoreMapUpdate */
 897
 898 Ipc::StoreMapUpdate::StoreMapUpdate(StoreEntry *anEntry):
 899     entry(anEntry)
 900 {
 901     entry->lock("Ipc::StoreMapUpdate1");
 902 }
 903
 904 Ipc::StoreMapUpdate::StoreMapUpdate(const StoreMapUpdate &other):
 905     entry(other.entry),
 906     stale(other.stale),
 907     fresh(other.fresh)
 908 {
 909     entry->lock("Ipc::StoreMapUpdate2");
 910 }
 911
 912 Ipc::StoreMapUpdate::~StoreMapUpdate()
 913 {
 914     entry->unlock("Ipc::StoreMapUpdate");
 915 }
 916
 917 /* Ipc::StoreMap::Owner */
 918
 919 Ipc::StoreMap::Owner::Owner():
 920     fileNos(nullptr),
 921     anchors(nullptr),
 922     slices(nullptr)
 923 {
 924 }
 925
 926 Ipc::StoreMap::Owner::~Owner()
 927 {
 928     delete fileNos;
 929     delete anchors;
 930     delete slices;
 931 }
 932
 933 /* Ipc::StoreMapAnchors */
 934
 935 Ipc::StoreMapAnchors::StoreMapAnchors(const int aCapacity):
 936     count(0),
 937     victim(0),
 938     capacity(aCapacity),
 939     items(aCapacity)
 940 {
 941 }
 942
 943 size_t
 944 Ipc::StoreMapAnchors::sharedMemorySize() const
 945 {
 946     return SharedMemorySize(capacity);
 947 }
 948
 949 size_t
 950 Ipc::StoreMapAnchors::SharedMemorySize(const int capacity)
 951 {
 952     return sizeof(StoreMapAnchors) + capacity * sizeof(StoreMapAnchor);
 953 }
 954