StoreMap.cc
Go to the documentation of this file.
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
23static SBuf
25{
26 return Ipc::Mem::Segment::Name(path, "slices");
27}
28
29static SBuf
31{
32 return Ipc::Mem::Segment::Name(path, "anchors");
33}
34
35static SBuf
37{
38 return Ipc::Mem::Segment::Name(path, "filenos");
39}
40
42Ipc::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);
50 debugs(54, 5, "created " << path << " with " << anchorLimit << '+' << sliceLimit);
51 return owner;
52}
53
54Ipc::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
67int
68Ipc::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
83void
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
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
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
155Ipc::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
190void
192{
193 Anchor &s = anchorAt(fileno);
194 assert(s.writing());
196 debugs(54, 5, "restricted entry " << fileno << " to appending " << path);
197}
198
199void
201{
202 Anchor &s = anchorAt(fileno);
203 assert(s.writing());
204 // TODO: assert(!s.empty()); // i.e., unlocked s becomes s.complete()
206 debugs(54, 5, "closed entry " << fileno << " for writing " << path);
207 // cannot assert completeness here because we have no lock
208}
209
210void
212{
213 debugs(54, 5, "switching entry " << fileno << " from writing to reading " << path);
214 Anchor &s = anchorAt(fileno);
215 assert(s.writing());
217 assert(s.complete());
218}
219
221Ipc::StoreMap::writeableSlice(const AnchorId anchorId, const SliceId sliceId)
222{
223 assert(anchorAt(anchorId).writing());
224 assert(validSlice(sliceId));
225 return sliceAt(sliceId);
226}
227
229Ipc::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
238{
239 assert(anchorAt(anchorId).writing());
240 return anchorAt(anchorId);
241}
242
245{
246 assert(anchorAt(anchorId).reading());
247 return anchorAt(anchorId);
248}
249
250void
252{
253 debugs(54, 5, "aborting entry " << fileno << " for writing " << path);
254 Anchor &s = anchorAt(fileno);
255 assert(s.writing());
257 freeChain(fileno, s, false);
258 debugs(54, 5, "closed idle entry " << fileno << " for writing " << path);
259 } else {
260 s.waitingToBeFreed = true;
261 s.writerHalted = true;
263 debugs(54, 5, "closed busy entry " << fileno << " for writing " << path);
264 }
265}
266
267void
269{
270 const sfileno fileno = update.stale.fileNo;
271 debugs(54, 5, "aborting entry " << fileno << " for updating " << path);
272 if (update.stale) {
274 update.stale.anchor->lock.unlockHeaders();
275 closeForReading(update.stale.fileNo);
276 update.stale = Update::Edition();
277 }
278 if (update.fresh) {
279 abortWriting(update.fresh.fileNo);
280 update.fresh = Update::Edition();
281 }
282 debugs(54, 5, "aborted entry " << fileno << " for updating " << path);
283}
284
287{
288 const Anchor &s = anchorAt(fileno);
289 if (s.reading())
290 return &s; // immediate access by lock holder so no locking
291 assert(s.writing()); // must be locked for reading or writing
292 return nullptr;
293}
294
297{
298 const Anchor &s = anchorAt(fileno);
299 if (s.writing())
300 return &s; // immediate access by lock holder so no locking
301 assert(s.reading()); // must be locked for reading or writing
302 return nullptr;
303}
304
307{
308 return anchorAt(fileno);
309}
310
311bool
313{
314 debugs(54, 5, "marking entry " << fileno << " to be freed in " << path);
315
316 Anchor &s = anchorAt(fileno);
317
318 if (s.lock.lockExclusive()) {
319 const bool result = !s.waitingToBeFreed && !s.empty();
320 freeChain(fileno, s, false);
321 return result;
322 }
323
324 uint8_t expected = false;
325 // mark to free the locked entry later (if not already marked)
326 return s.waitingToBeFreed.compare_exchange_strong(expected, true);
327}
328
329void
331{
332 debugs(54, 5, "marking entry with key " << storeKeyText(key)
333 << " to be freed in " << path);
334
335 const int idx = fileNoByKey(key);
336 Anchor &s = anchorAt(idx);
337 if (s.lock.lockExclusive()) {
338 if (s.sameKey(key))
339 freeChain(idx, s, true);
341 } else if (s.lock.lockShared()) {
342 if (s.sameKey(key))
343 s.waitingToBeFreed = true; // mark to free it later
344 s.lock.unlockShared();
345 } else {
346 // we cannot be sure that the entry we found is ours because we do not
347 // have a lock on it, but we still check to minimize false deletions
348 if (s.sameKey(key))
349 s.waitingToBeFreed = true; // mark to free it later
350 }
351}
352
353bool
355{
356 const int idx = fileNoByKey(key);
357 const Anchor &s = anchorAt(idx);
358 return s.sameKey(key) ? bool(s.waitingToBeFreed) : false;
359}
360
361bool
363{
364 sfileno index;
365 if (openForReading(reinterpret_cast<const cache_key*>(key), index)) {
366 closeForReading(index);
367 return true;
368 }
369 return false;
370}
371
373void
374Ipc::StoreMap::freeChain(const sfileno fileno, Anchor &inode, const bool keepLocked)
375{
376 debugs(54, 7, "freeing entry " << fileno <<
377 " in " << path);
378 if (!inode.empty())
379 freeChainAt(inode.start, inode.splicingPoint);
380 inode.rewind();
381
382 if (!keepLocked)
383 inode.lock.unlockExclusive();
384 --anchors->count;
385 debugs(54, 5, "freed entry " << fileno << " in " << path);
386}
387
389void
390Ipc::StoreMap::freeChainAt(SliceId sliceId, const SliceId splicingPoint)
391{
392 static uint64_t ChainId = 0; // to pair freeing/freed calls in debugs()
393 const uint64_t chainId = ++ChainId;
394 debugs(54, 7, "freeing chain #" << chainId << " starting at " << sliceId << " in " << path);
395 while (sliceId >= 0) {
396 Slice &slice = sliceAt(sliceId);
397 const SliceId nextId = slice.next;
398 slice.clear();
399 if (cleaner)
400 cleaner->noteFreeMapSlice(sliceId); // might change slice state
401 if (sliceId == splicingPoint) {
402 debugs(54, 5, "preserving chain #" << chainId << " in " << path <<
403 " suffix after slice " << splicingPoint);
404 break; // do not free the rest of the chain
405 }
406 sliceId = nextId;
407 }
408 debugs(54, 7, "freed chain #" << chainId << " in " << path);
409}
410
411void
413{
414 // TODO: Move freeSlots here, along with reserveSlotForWriting() logic.
415 assert(validSlice(sliceId));
416 sliceAt(sliceId).clear();
417}
418
420Ipc::StoreMap::sliceContaining(const sfileno fileno, const uint64_t bytesNeeded) const
421{
422 const Anchor &anchor = anchorAt(fileno);
423 Must(anchor.reading());
424 uint64_t bytesSeen = 0;
425 SliceId lastSlice = anchor.start;
426 while (lastSlice >= 0) {
427 const Slice &slice = sliceAt(lastSlice);
428 bytesSeen += slice.size;
429 if (bytesSeen >= bytesNeeded)
430 break;
431 lastSlice = slice.next;
432 }
433 debugs(54, 7, "entry " << fileno << " has " << bytesNeeded << '/' << bytesSeen <<
434 " bytes at slice " << lastSlice << " in " << path);
435 return lastSlice; // may be negative
436}
437
440{
441 debugs(54, 5, "opening entry with key " << storeKeyText(key)
442 << " for reading " << path);
443 const int idx = fileNoByKey(key);
444 if (const auto anchor = openForReadingAt(idx, key)) {
445 fileno = idx;
446 return anchor; // locked for reading
447 }
448 return nullptr;
449}
450
452Ipc::StoreMap::openForReadingAt(const sfileno fileno, const cache_key *const key)
453{
454 debugs(54, 5, "opening entry " << fileno << " for reading " << path);
455 Anchor &s = anchorAt(fileno);
456
457 if (!s.lock.lockShared()) {
458 debugs(54, 5, "cannot open busy entry " << fileno <<
459 " for reading " << path);
460 return nullptr;
461 }
462
463 if (s.empty()) {
464 s.lock.unlockShared();
465 debugs(54, 7, "cannot open empty entry " << fileno <<
466 " for reading " << path);
467 return nullptr;
468 }
469
470 if (s.waitingToBeFreed) {
471 s.lock.unlockShared();
472 debugs(54, 7, "cannot open marked entry " << fileno <<
473 " for reading " << path);
474 return nullptr;
475 }
476
477 if (!s.sameKey(key)) {
478 s.lock.unlockShared();
479 debugs(54, 5, "cannot open wrong-key entry " << fileno <<
480 " for reading " << path);
481 return nullptr;
482 }
483
484 if (Config.paranoid_hit_validation.count() && hitValidation && !validateHit(fileno)) {
485 s.lock.unlockShared();
486 debugs(54, 5, "cannot open corrupted entry " << fileno <<
487 " for reading " << path);
488 return nullptr;
489 }
490
491 debugs(54, 5, "opened entry " << fileno << " for reading " << path);
492 return &s;
493}
494
495void
497{
498 Anchor &s = anchorAt(fileno);
499 assert(s.reading());
500 s.lock.unlockShared();
501 debugs(54, 5, "closed entry " << fileno << " for reading " << path);
502}
503
504void
506{
507 auto &s = anchorAt(fileno);
508 assert(s.reading());
509
510 if (!s.lock.unlockSharedAndSwitchToExclusive()) {
511 debugs(54, 5, "closed entry " << fileno << " for reading " << path);
512 return;
513 }
514
515 assert(s.writing());
516 assert(!s.reading());
517 freeChain(fileno, s, false);
518 debugs(54, 5, "closed idle entry " << fileno << " for reading " << path);
519}
520
521bool
523{
524 Must(update.entry);
525 const StoreEntry &entry = *update.entry;
526 const cache_key *const key = reinterpret_cast<const cache_key*>(entry.key);
527 update.stale.name = nameByKey(key);
528
529 if (!validEntry(fileNoHint)) {
530 debugs(54, 5, "opening entry with key " << storeKeyText(key) <<
531 " for updating " << path);
532 update.stale.fileNo = fileNoByName(update.stale.name);
533 } else {
534 update.stale.fileNo = fileNoHint;
535 }
536
537 debugs(54, 5, "opening entry " << update.stale.fileNo << " of " << entry << " for updating " << path);
538
539 // Unreadable entries cannot (e.g., empty and otherwise problematic entries)
540 // or should not (e.g., entries still forming their metadata) be updated.
541 if (!openForReadingAt(update.stale.fileNo, key)) {
542 debugs(54, 5, "cannot open unreadable entry " << update.stale.fileNo << " for updating " << path);
543 return false;
544 }
545
546 update.stale.anchor = &anchorAt(update.stale.fileNo);
547 if (update.stale.anchor->writing()) {
548 // TODO: Support updating appending entries.
549 // For example, MemStore::updateHeaders() would not know how
550 // many old prefix body bytes to copy to the new prefix if the last old
551 // prefix slice has not been formed yet (i.e., still gets more bytes).
552 debugs(54, 5, "cannot open appending entry " << update.stale.fileNo <<
553 " for updating " << path);
554 closeForReading(update.stale.fileNo);
555 return false;
556 }
557
558 if (!update.stale.anchor->lock.lockHeaders()) {
559 debugs(54, 5, "cannot open updating entry " << update.stale.fileNo <<
560 " for updating " << path);
561 closeForReading(update.stale.fileNo);
562 return false;
563 }
564
565 /* stale anchor is properly locked; we can now use abortUpdating() if needed */
566
567 if (!openKeyless(update.fresh)) {
568 debugs(54, 5, "cannot open freshchainless entry " << update.stale.fileNo <<
569 " for updating " << path);
570 abortUpdating(update);
571 return false;
572 }
573
574 Must(update.stale);
575 Must(update.fresh);
576 update.fresh.anchor->set(entry);
577 debugs(54, 5, "opened entry " << update.stale.fileNo << " for updating " << path <<
578 " using entry " << update.fresh.fileNo << " of " << entry);
579
580 return true;
581}
582
585bool
587{
588 return visitVictims([&](const sfileno name) {
589 Update::Edition temp;
590 temp.name = name;
591 temp.fileNo = fileNoByName(temp.name);
592 if ((temp.anchor = openForWritingAt(temp.fileNo))) {
593 debugs(54, 5, "created entry " << temp.fileNo <<
594 " for updating " << path);
595 Must(temp);
596 edition = temp;
597 return true;
598 }
599 return false;
600 });
601}
602
603void
605{
606 Must(update.stale.anchor);
607 Must(update.fresh.anchor);
609 Must(update.stale.splicingPoint >= 0);
610 Must(update.fresh.splicingPoint >= 0);
611
612 /* the stale prefix cannot overlap with the fresh one (a weak check) */
613 Must(update.stale.anchor->start != update.fresh.anchor->start);
614 Must(update.stale.anchor->start != update.fresh.splicingPoint);
615 Must(update.stale.splicingPoint != update.fresh.anchor->start);
616 Must(update.stale.splicingPoint != update.fresh.splicingPoint);
617
618 /* the relative order of most operations is significant here */
619
620 /* splice the fresh chain prefix with the stale chain suffix */
621 Slice &freshSplicingSlice = sliceAt(update.fresh.splicingPoint);
622 const SliceId suffixStart = sliceAt(update.stale.splicingPoint).next; // may be negative
623 // the fresh chain is either properly terminated or already spliced
624 if (freshSplicingSlice.next < 0)
625 freshSplicingSlice.next = suffixStart;
626 else
627 Must(freshSplicingSlice.next == suffixStart);
628 // either way, fresh chain uses the stale chain suffix now
629
630 // make the fresh anchor/chain readable for everybody
632 // but the fresh anchor is still invisible to anybody but us
633
634 // This freeEntry() code duplicates the code below to minimize the time when
635 // the freeEntry() race condition (see the Race: comment below) might occur.
636 if (update.stale.anchor->waitingToBeFreed)
637 freeEntry(update.fresh.fileNo);
638
639 /* any external changes were applied to the stale anchor/chain until now */
640 relocate(update.stale.name, update.fresh.fileNo);
641 /* any external changes will apply to the fresh anchor/chain from now on */
642
643 // Race: If the stale entry was deleted by some kid during the assignment,
644 // then we propagate that event to the fresh anchor and chain. Since this
645 // update is not atomically combined with the assignment above, another kid
646 // might get a fresh entry just before we have a chance to free it. However,
647 // such deletion races are always possible even without updates.
648 if (update.stale.anchor->waitingToBeFreed)
649 freeEntry(update.fresh.fileNo);
650
651 /* free the stale chain prefix except for the shared suffix */
653 freeEntry(update.stale.fileNo);
654
655 // Make the stale anchor/chain reusable, reachable via update.fresh.name. If
656 // update.entry->swap_filen is still update.stale.fileNo, and the entry is
657 // using store, then the entry must have a lock on update.stale.fileNo,
658 // preventing its premature reuse by others.
659 relocate(update.fresh.name, update.stale.fileNo);
660
661 const Update updateSaved = update; // for post-close debugging below
662
663 /* unlock the stale anchor/chain */
664 update.stale.anchor->lock.unlockHeaders();
665 closeForReading(update.stale.fileNo);
666 update.stale = Update::Edition();
667
668 // finally, unlock the fresh entry
669 closeForReading(update.fresh.fileNo);
670 update.fresh = Update::Edition();
671
672 debugs(54, 5, "closed entry " << updateSaved.stale.fileNo << " of " << *updateSaved.entry <<
673 " named " << updateSaved.stale.name << " for updating " << path <<
674 " to fresh entry " << updateSaved.fresh.fileNo << " named " << updateSaved.fresh.name <<
675 " with [" << updateSaved.fresh.anchor->start << ',' << updateSaved.fresh.splicingPoint <<
676 "] prefix containing at least " << freshSplicingSlice.size << " bytes");
677}
678
683bool
685{
686 // Hopefully, we find a usable entry much sooner (TODO: use time?).
687 // The min() will protect us from division by zero inside the loop.
688 const int searchLimit = min(10000, entryLimit());
689 int tries = 0;
690 for (; tries < searchLimit; ++tries) {
691 const sfileno name = static_cast<sfileno>(++anchors->victim % entryLimit());
692 if (visitor(name))
693 return true;
694 }
695
696 debugs(54, 5, "no victims found in " << path << "; tried: " << tries);
697 return false;
698}
699
700bool
702{
703 return visitVictims([&](const sfileno name) {
704 const sfileno fileno = fileNoByName(name);
705 Anchor &s = anchorAt(fileno);
706 if (s.lock.lockExclusive()) {
707 // the caller wants a free slice; empty anchor is not enough
708 if (!s.empty() && s.start >= 0) {
709 // this entry may be marked for deletion, and that is OK
710 freeChain(fileno, s, false);
711 debugs(54, 5, "purged entry " << fileno << " from " << path);
712 return true;
713 }
715 }
716 return false;
717 });
718}
719
720void
721Ipc::StoreMap::importSlice(const SliceId sliceId, const Slice &slice)
722{
723 // Slices are imported into positions that should not be available via
724 // "get free slice" API. This is not something we can double check
725 // reliably because the anchor for the imported slice may not have been
726 // imported yet.
727 assert(validSlice(sliceId));
728 sliceAt(sliceId) = slice;
729}
730
731int
733{
734 return min(sliceLimit(), static_cast<int>(SwapFilenMax+1));
735}
736
737int
739{
740 return anchors->count;
741}
742
743int
745{
746 return slices->capacity;
747}
748
749void
751{
752 for (int i = 0; i < anchors->capacity; ++i)
753 anchorAt(i).lock.updateStats(stats);
754}
755
756bool
757Ipc::StoreMap::validEntry(const int pos) const
758{
759 return 0 <= pos && pos < entryLimit();
760}
761
762bool
763Ipc::StoreMap::validSlice(const int pos) const
764{
765 return 0 <= pos && pos < sliceLimit();
766}
767
772{
773public:
774 typedef std::chrono::high_resolution_clock Clock;
775
776 explicit ConservativeTimer(const Clock::duration max):
777 startTime(Clock::now()),
778 lastTime(startTime),
779 maxTime(startTime + max) {}
780
782 bool expired() {
783 const auto currentTime = Clock::now();
784 if (currentTime < lastTime) // time went backwards
785 return true;
786 lastTime = currentTime;
787 return lastTime > maxTime;
788 }
789
790private:
792 Clock::time_point startTime;
794 Clock::time_point lastTime;
796 const Clock::time_point maxTime;
797};
798
799bool
801{
803 const auto timeIsLimited = Config.paranoid_hit_validation < std::chrono::hours(24);
804
805 const auto &anchor = anchorAt(fileno);
806
808
809 if (!anchor.basics.swap_file_sz) {
811 return true; // presume valid; cannot validate w/o known swap_file_sz
812 }
813
814 if (!anchor.lock.lockHeaders()) {
816 return true; // presume valid; cannot validate changing entry
817 }
818
819 const uint64_t expectedByteCount = anchor.basics.swap_file_sz;
820
821 size_t actualSliceCount = 0;
822 uint64_t actualByteCount = 0;
823 SliceId lastSeenSlice = anchor.start;
824 while (lastSeenSlice >= 0) {
825 ++actualSliceCount;
826 if (!validSlice(lastSeenSlice))
827 break;
828 const auto &slice = sliceAt(lastSeenSlice);
829 actualByteCount += slice.size;
830 if (actualByteCount > expectedByteCount)
831 break;
832 lastSeenSlice = slice.next;
833 if (timeIsLimited && timer.expired()) {
834 anchor.lock.unlockHeaders();
836 return true;
837 }
838 }
839
840 anchor.lock.unlockHeaders();
841
842 if (actualByteCount == expectedByteCount && lastSeenSlice < 0)
843 return true;
844
846
847 debugs(54, DBG_IMPORTANT, "ERROR: Squid BUG: purging corrupted cache entry " << fileno <<
848 " from " << path <<
849 " expected swap_file_sz=" << expectedByteCount <<
850 " actual swap_file_sz=" << actualByteCount <<
851 " actual slices=" << actualSliceCount <<
852 " last slice seen=" << lastSeenSlice << "\n" <<
853 " key=" << storeKeyText(reinterpret_cast<const cache_key*>(anchor.key)) << "\n" <<
854 " tmestmp=" << anchor.basics.timestamp << "\n" <<
855 " lastref=" << anchor.basics.lastref << "\n" <<
856 " expires=" << anchor.basics.expires << "\n" <<
857 " lastmod=" << anchor.basics.lastmod << "\n" <<
858 " refcount=" << anchor.basics.refcount << "\n" <<
859 " flags=0x" << std::hex << anchor.basics.flags << std::dec << "\n" <<
860 " start=" << anchor.start << "\n" <<
861 " splicingPoint=" << anchor.splicingPoint << "\n" <<
862 " lock=" << anchor.lock << "\n" <<
863 " waitingToBeFreed=" << (anchor.waitingToBeFreed ? 1 : 0) << "\n"
864 );
865 freeEntry(fileno);
866 return false;
867}
868
871{
872 assert(validEntry(fileno));
873 return anchors->items[fileno];
874}
875
878{
879 return const_cast<StoreMap&>(*this).anchorAt(fileno);
880}
881
883Ipc::StoreMap::nameByKey(const cache_key *const key) const
884{
885 assert(key);
886 const uint64_t *const k = reinterpret_cast<const uint64_t *>(key);
887 // TODO: use a better hash function
888 const int hash = (k[0] + k[1]) % entryLimit();
889 return hash;
890}
891
894{
895 // fileNos->items are initialized to zero, which we treat as "name is fileno";
896 // a positive value means the entry anchor got moved to a new fileNo
897 if (const int item = fileNos->items[name])
898 return item-1;
899 return name;
900}
901
903void
904Ipc::StoreMap::relocate(const sfileno name, const sfileno fileno)
905{
906 // preserve special meaning for zero; see fileNoByName
907 fileNos->items[name] = fileno+1;
908}
909
912{
913 const int name = nameByKey(key);
914 return fileNoByName(name);
915}
916
919{
920 return anchorAt(fileNoByKey(key));
921}
922
925{
926 assert(validSlice(sliceId));
927 return slices->items[sliceId];
928}
929
931Ipc::StoreMap::sliceAt(const SliceId sliceId) const
932{
933 return const_cast<StoreMap&>(*this).sliceAt(sliceId);
934}
935
936/* Ipc::StoreMapAnchor */
937
938Ipc::StoreMapAnchor::StoreMapAnchor(): start(0), splicingPoint(-1)
939{
940 // keep in sync with rewind()
941}
942
943void
945{
946 memcpy(key, aKey, sizeof(key));
947 waitingToBeFreed = Store::Root().markedForDeletion(aKey);
948}
949
950bool
952{
953 const uint64_t *const k = reinterpret_cast<const uint64_t *>(aKey);
954 return k[0] == key[0] && k[1] == key[1];
955}
956
957void
959{
960 assert(writing() && !reading());
961 setKey(reinterpret_cast<const cache_key*>(aKey ? aKey : from.key));
962 basics.timestamp = from.timestamp;
963 basics.lastref = from.lastref;
964 basics.expires = from.expires;
965 basics.lastmod = from.lastModified();
966 basics.swap_file_sz = from.swap_file_sz;
967 basics.refcount = from.refcount;
968
969 // do not copy key bit if we are not using from.key
970 // TODO: Replace KEY_PRIVATE with a nil StoreEntry::key!
971 uint16_t cleanFlags = from.flags;
972 if (aKey)
973 EBIT_CLR(cleanFlags, KEY_PRIVATE);
974 basics.flags = cleanFlags;
975}
976
977void
979{
980 assert(reading());
981 into.timestamp = basics.timestamp;
982 into.lastref = basics.lastref;
983 into.expires = basics.expires;
984 into.lastModified(basics.lastmod);
985 into.swap_file_sz = basics.swap_file_sz;
986 into.refcount = basics.refcount;
987
988 // Some basics.flags are not meaningful and should not be overwritten here.
989 // ENTRY_REQUIRES_COLLAPSING is one of them. TODO: check other flags.
990 const bool collapsingRequired = into.hittingRequiresCollapsing();
991 into.flags = basics.flags;
992 // Avoid into.setCollapsingRequirement() here: We only restore the bit we
993 // just cleared in the assignment above, while that method debugging will
994 // falsely imply that the collapsing requirements have changed.
995 if (collapsingRequired)
997 else
999}
1000
1001void
1003{
1004 assert(writing());
1005 start = 0;
1006 splicingPoint = -1;
1007 memset(&key, 0, sizeof(key));
1008 basics.clear();
1009 waitingToBeFreed = false;
1010 writerHalted = false;
1011 // but keep the lock
1012}
1013
1014/* Ipc::StoreMapUpdate */
1015
1017 entry(anEntry)
1018{
1019 entry->lock("Ipc::StoreMapUpdate1");
1020}
1021
1023 entry(other.entry),
1024 stale(other.stale),
1025 fresh(other.fresh)
1026{
1027 entry->lock("Ipc::StoreMapUpdate2");
1028}
1029
1031{
1032 entry->unlock("Ipc::StoreMapUpdate");
1033}
1034
1035/* Ipc::StoreMap::Owner */
1036
1038 fileNos(nullptr),
1039 anchors(nullptr),
1040 slices(nullptr)
1041{
1042}
1043
1045{
1046 delete fileNos;
1047 delete anchors;
1048 delete slices;
1049}
1050
1051/* Ipc::StoreMapAnchors */
1052
1054 count(0),
1055 victim(0),
1056 capacity(aCapacity),
1057 items(aCapacity)
1058{
1059}
1060
1061size_t
1063{
1064 return SharedMemorySize(capacity);
1065}
1066
1067size_t
1069{
1070 return sizeof(StoreMapAnchors) + capacity * sizeof(StoreMapAnchor);
1071}
1072
#define shm_new(Class)
Definition: Pointer.h:200
#define shm_old(Class)
Definition: Pointer.h:201
class SquidConfig Config
Definition: SquidConfig.cc:12
StatCounters statCounter
Definition: StatCounters.cc:12
static SBuf StoreMapFileNosId(const SBuf &path)
Definition: StoreMap.cc:36
static SBuf StoreMapSlicesId(const SBuf &path)
Definition: StoreMap.cc:24
static SBuf StoreMapAnchorsId(const SBuf &path)
Definition: StoreMap.cc:30
#define Must(condition)
Definition: TextException.h:75
#define assert(EX)
Definition: assert.h:17
static time_t now
Definition: cachemgr.cc:109
ConservativeTimer(const Clock::duration max)
Definition: StoreMap.cc:776
bool expired()
whether the current time reached the provided maximum time
Definition: StoreMap.cc:782
Clock::time_point lastTime
the time of the last expired() call, initially equals to startTime
Definition: StoreMap.cc:794
const Clock::time_point maxTime
after going past this point in time, expired() becomes true
Definition: StoreMap.cc:796
Clock::time_point startTime
the object creation time
Definition: StoreMap.cc:792
std::chrono::high_resolution_clock Clock
Definition: StoreMap.cc:774
static SBuf Name(const SBuf &prefix, const char *suffix)
concatenates parts of a name to form a complete name (or its prefix)
Definition: Segment.cc:52
approximate stats of a set of ReadWriteLocks
Definition: ReadWriteLock.h:71
void unlockHeaders()
undo successful lockHeaders()
void switchExclusiveToShared()
bool lockHeaders()
lock for [readable] metadata update or return false
void unlockExclusive()
undo successful exclusiveLock()
bool lockExclusive()
lock for modification or return false
bool stopAppendingAndRestoreExclusive()
std::atomic_flag updating
a reader is updating metadata/headers
Definition: ReadWriteLock.h:57
std::atomic< bool > appending
the writer has promised to only append
Definition: ReadWriteLock.h:56
void unlockShared()
undo successful sharedLock()
bool lockShared()
lock for reading or return false
void startAppending()
writer keeps its lock but also allows reading
std::atomic< StoreMapSliceId > splicingPoint
Definition: StoreMap.h:115
std::atomic< StoreMapSliceId > start
where the chain of StoreEntry slices begins [app]
Definition: StoreMap.h:111
void rewind()
undo the effects of set(), setKey(), etc., but keep locks and state
Definition: StoreMap.cc:1002
bool sameKey(const cache_key *const aKey) const
Definition: StoreMap.cc:951
bool empty() const
Definition: StoreMap.h:74
struct Ipc::StoreMapAnchor::Basics basics
bool complete() const
Definition: StoreMap.h:77
std::atomic< uint8_t > writerHalted
whether StoreMap::abortWriting() was called for a read-locked entry
Definition: StoreMap.h:83
bool writing() const
Definition: StoreMap.h:76
void set(const StoreEntry &anEntry, const cache_key *aKey=nullptr)
store StoreEntry key and basics for an inode slot
Definition: StoreMap.cc:958
bool reading() const
Definition: StoreMap.h:75
void setKey(const cache_key *const aKey)
Definition: StoreMap.cc:944
ReadWriteLock lock
protects slot data below
Definition: StoreMap.h:80
std::atomic< uint8_t > waitingToBeFreed
Definition: StoreMap.h:81
void exportInto(StoreEntry &) const
load StoreEntry basics that were previously stored with set()
Definition: StoreMap.cc:978
StoreMapAnchors(const int aCapacity)
Definition: StoreMap.cc:1053
size_t sharedMemorySize() const
Definition: StoreMap.cc:1062
static size_t SharedMemorySize(const int anAnchorLimit)
Definition: StoreMap.cc:1068
void clear()
restore default-constructed state
Definition: StoreMap.h:46
std::atomic< StoreMapSliceId > next
ID of the next entry slice.
Definition: StoreMap.h:49
std::atomic< Size > size
slice contents size
Definition: StoreMap.h:48
During an update, the stored entry has two editions: stale and fresh.
Definition: StoreMap.h:186
sfileno name
StoreEntry position in StoreMap::fileNos, for swapping Editions.
Definition: StoreMap.h:195
sfileno fileNo
StoreMap::fileNos[name], for convenience/speed.
Definition: StoreMap.h:194
StoreMapSliceId splicingPoint
the last slice in the chain still containing metadata/headers
Definition: StoreMap.h:198
StoreMapAnchor * anchor
StoreMap::anchors[fileNo], for convenience/speed.
Definition: StoreMap.h:193
Aggregates information required for updating entry metadata and headers.
Definition: StoreMap.h:182
Edition fresh
new anchor and the updated chain prefix
Definition: StoreMap.h:209
Edition stale
old anchor and chain
Definition: StoreMap.h:208
StoreEntry * entry
the store entry being updated
Definition: StoreMap.h:207
StoreMapUpdate(StoreEntry *anEntry)
Definition: StoreMap.cc:1016
aggregates anchor and slice owners for Init() caller convenience
Definition: StoreMap.h:233
Slices::Owner * slices
Definition: StoreMap.h:239
Anchors::Owner * anchors
Definition: StoreMap.h:238
FileNos::Owner * fileNos
Definition: StoreMap.h:237
Anchor * openForWriting(const cache_key *const key, sfileno &fileno)
Definition: StoreMap.cc:140
const Slice & readableSlice(const AnchorId anchorId, const SliceId sliceId) const
readable slice within an entry chain opened by openForReading()
Definition: StoreMap.cc:229
const Anchor * openForReadingAt(const sfileno, const cache_key *const)
opens entry (identified by sfileno) for reading, increments read level
Definition: StoreMap.cc:452
bool validateHit(const sfileno)
Definition: StoreMap.cc:800
bool openForUpdating(Update &update, sfileno fileNoHint)
finds and locks the Update entry for an exclusive metadata update
Definition: StoreMap.cc:522
Anchor * openForWritingAt(sfileno fileno, bool overwriteExisting=true)
Definition: StoreMap.cc:155
bool visitVictims(const NameFilter filter)
Definition: StoreMap.cc:684
bool markedForDeletion(const cache_key *const)
Definition: StoreMap.cc:354
Anchor & writeableEntry(const AnchorId anchorId)
writeable anchor for the entry created by openForWriting()
Definition: StoreMap.cc:237
sfileno AnchorId
Definition: StoreMap.h:224
Mem::Pointer< StoreMapAnchors > anchors
entry inodes (starting blocks)
Definition: StoreMap.h:366
const Anchor * peekAtReader(const sfileno fileno) const
Definition: StoreMap.cc:286
bool validEntry(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:757
const Anchor & readableEntry(const AnchorId anchorId) const
readable anchor for the entry created by openForReading()
Definition: StoreMap.cc:244
Anchor & anchorByKey(const cache_key *const key)
Definition: StoreMap.cc:918
int entryCount() const
number of writeable and readable entries
Definition: StoreMap.cc:738
static Owner * Init(const SBuf &path, const int slotLimit)
initialize shared memory
Definition: StoreMap.cc:42
void relocate(const sfileno name, const sfileno fileno)
map name to fileNo
Definition: StoreMap.cc:904
void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock)
unconditionally frees an already locked chain of slots, unlocking if needed
Definition: StoreMap.cc:374
Slice & sliceAt(const SliceId sliceId)
Definition: StoreMap.cc:924
void closeForWriting(const sfileno fileno)
successfully finish creating or updating the entry at fileno pos
Definition: StoreMap.cc:200
const Anchor * openOrCreateForReading(const cache_key *, sfileno &)
openForReading() but creates a new entry if there is no old one
Definition: StoreMap.cc:103
void abortUpdating(Update &update)
undoes partial update, unlocks, and cleans up
Definition: StoreMap.cc:268
SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const
Definition: StoreMap.cc:420
const Anchor * openForReading(const cache_key *const key, sfileno &fileno)
opens entry (identified by key) for reading, increments read level
Definition: StoreMap.cc:439
void forgetWritingEntry(const sfileno fileno)
Definition: StoreMap.cc:84
int compareVersions(const sfileno oldFileno, time_t newVersion) const
Definition: StoreMap.cc:68
bool freeEntry(const sfileno)
Definition: StoreMap.cc:312
const SBuf path
cache_dir path or similar cache name; for logging
Definition: StoreMap.h:364
void closeForReading(const sfileno fileno)
closes open entry after reading, decrements read level
Definition: StoreMap.cc:496
StoreMap(const SBuf &aPath)
Definition: StoreMap.cc:54
void importSlice(const SliceId sliceId, const Slice &slice)
copies slice to its designated position
Definition: StoreMap.cc:721
const Anchor * peekAtWriter(const sfileno fileno) const
Definition: StoreMap.cc:296
void closeForReadingAndFreeIdle(const sfileno fileno)
same as closeForReading() but also frees the entry if it is unlocked
Definition: StoreMap.cc:505
void abortWriting(const sfileno fileno)
stop writing the entry, freeing its slot for others to use if possible
Definition: StoreMap.cc:251
bool validSlice(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:763
void startAppending(const sfileno fileno)
restrict opened for writing entry to appending operations; allow reads
Definition: StoreMap.cc:191
sfileno nameByKey(const cache_key *const key) const
computes entry name (i.e., key hash) for a given entry key
Definition: StoreMap.cc:883
void prepFreeSlice(const SliceId sliceId)
prepare a chain-unaffiliated slice for being added to an entry chain
Definition: StoreMap.cc:412
Mem::Pointer< StoreMapSlices > slices
chained entry pieces positions
Definition: StoreMap.h:367
void closeForUpdating(Update &update)
makes updated info available to others, unlocks, and cleans up
Definition: StoreMap.cc:604
std::function< bool(const sfileno name)> NameFilter
Definition: StoreMap.h:386
bool openKeyless(Update::Edition &edition)
Definition: StoreMap.cc:586
bool purgeOne()
either finds and frees an entry with at least 1 slice or returns false
Definition: StoreMap.cc:701
void updateStats(ReadWriteLockStats &stats) const
adds approximate current stats to the supplied ones
Definition: StoreMap.cc:750
sfileno fileNoByKey(const cache_key *const key) const
computes map entry anchor position for a given entry key
Definition: StoreMap.cc:911
bool hasReadableEntry(const cache_key *const)
whether the index contains a valid readable entry with the given key
Definition: StoreMap.cc:362
StoreMapSliceId SliceId
Definition: StoreMap.h:227
void freeEntryByKey(const cache_key *const key)
Definition: StoreMap.cc:330
sfileno fileNoByName(const sfileno name) const
computes anchor position for a given entry name
Definition: StoreMap.cc:893
Anchor & anchorAt(const sfileno fileno)
Definition: StoreMap.cc:870
const Anchor & peekAtEntry(const sfileno fileno) const
Definition: StoreMap.cc:306
Mem::Pointer< StoreMapFileNos > fileNos
entry inodes (starting blocks)
Definition: StoreMap.h:365
Slice & writeableSlice(const AnchorId anchorId, const SliceId sliceId)
writeable slice within an entry chain created by openForWriting()
Definition: StoreMap.cc:221
void switchWritingToReading(const sfileno fileno)
stop writing (or updating) the locked entry and start reading it
Definition: StoreMap.cc:211
int sliceLimit() const
maximum number of slices possible
Definition: StoreMap.cc:744
void freeChainAt(SliceId sliceId, const SliceId splicingPoint)
unconditionally frees an already locked chain of slots; no anchor maintenance
Definition: StoreMap.cc:390
int entryLimit() const
maximum entryCount() possible
Definition: StoreMap.cc:732
Definition: SBuf.h:94
const char * c_str()
Definition: SBuf.cc:516
std::chrono::nanoseconds paranoid_hit_validation
Definition: SquidConfig.h:354
uint64_t refusalsDueToZeroSize
Definition: StatCounters.h:163
uint64_t refusalsDueToTimeLimit
Definition: StatCounters.h:164
uint64_t attempts
Definition: StatCounters.h:161
uint64_t failures
Definition: StatCounters.h:165
struct StatCounters::@132 hitValidation
uint64_t refusalsDueToLocking
Definition: StatCounters.h:162
uint16_t flags
Definition: Store.h:232
time_t expires
Definition: Store.h:226
void lastModified(const time_t when)
Definition: Store.h:176
void lock(const char *context)
Definition: store.cc:431
time_t timestamp
Definition: Store.h:224
time_t lastref
Definition: Store.h:225
uint64_t swap_file_sz
Definition: Store.h:230
uint16_t refcount
Definition: Store.h:231
bool hittingRequiresCollapsing() const
whether this entry can feed collapsed requests and only them
Definition: Store.h:216
bool markedForDeletion(const cache_key *key) const
Definition: Controller.cc:305
A const & max(A const &lhs, A const &rhs)
A const & min(A const &lhs, A const &rhs)
#define DBG_IMPORTANT
Definition: Stream.h:38
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:194
#define EBIT_CLR(flag, bit)
Definition: defines.h:68
#define EBIT_SET(flag, bit)
Definition: defines.h:67
@ ENTRY_REQUIRES_COLLAPSING
Definition: enums.h:118
@ KEY_PRIVATE
Definition: enums.h:102
void AssertFlagIsSet(std::atomic_flag &flag)
class Ping::pingStats_ stats
Controller & Root()
safely access controller singleton
Definition: Controller.cc:938
@ SwapFilenMax
Definition: forward.h:26
unsigned char cache_key
Store key.
Definition: forward.h:29
signed_int32_t sfileno
Definition: forward.h:22
const char * storeKeyText(const cache_key *key)
static hash_table * hash
Definition: text_backend.cc:41

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors