src/ipc/StoreMap.cc

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