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->set(entry, 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());
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;
264 debugs(54, 5, "closed dirty entry " << fileno << " for writing " << path);
265 }
266}
267
268void
270{
271 const sfileno fileno = update.stale.fileNo;
272 debugs(54, 5, "aborting entry " << fileno << " for updating " << path);
273 if (update.stale) {
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
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
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
308{
309 return anchorAt(fileno);
310}
311
312bool
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
330void
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);
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
354bool
356{
357 const int idx = fileNoByKey(key);
358 const Anchor &s = anchorAt(idx);
359 return s.sameKey(key) ? bool(s.waitingToBeFreed) : false;
360}
361
362bool
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
374void
375Ipc::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
390void
391Ipc::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
412void
414{
415 // TODO: Move freeSlots here, along with reserveSlotForWriting() logic.
416 assert(validSlice(sliceId));
417 sliceAt(sliceId).clear();
418}
419
421Ipc::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
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
453Ipc::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
496void
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
505void
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
522bool
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
586bool
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
604void
606{
607 Must(update.stale.anchor);
608 Must(update.fresh.anchor);
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
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 */
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
684bool
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
701bool
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 }
716 }
717 return false;
718 });
719}
720
721void
722Ipc::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
732int
734{
735 return min(sliceLimit(), static_cast<int>(SwapFilenMax+1));
736}
737
738int
740{
741 return anchors->count;
742}
743
744int
746{
747 return slices->capacity;
748}
749
750void
752{
753 for (int i = 0; i < anchors->capacity; ++i)
754 anchorAt(i).lock.updateStats(stats);
755}
756
757bool
758Ipc::StoreMap::validEntry(const int pos) const
759{
760 return 0 <= pos && pos < entryLimit();
761}
762
763bool
764Ipc::StoreMap::validSlice(const int pos) const
765{
766 return 0 <= pos && pos < sliceLimit();
767}
768
773{
774public:
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
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
791private:
793 Clock::time_point startTime;
795 Clock::time_point lastTime;
797 const Clock::time_point maxTime;
798};
799
800bool
802{
804 const auto timeIsLimited = Config.paranoid_hit_validation < std::chrono::hours(24);
805
806 const auto &anchor = anchorAt(fileno);
807
809
810 if (!anchor.basics.swap_file_sz) {
812 return true; // presume valid; cannot validate w/o known swap_file_sz
813 }
814
815 if (!anchor.lock.lockHeaders()) {
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();
837 return true;
838 }
839 }
840
841 anchor.lock.unlockHeaders();
842
843 if (actualByteCount == expectedByteCount && lastSeenSlice < 0)
844 return true;
845
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
872{
873 assert(validEntry(fileno));
874 return anchors->items[fileno];
875}
876
879{
880 return const_cast<StoreMap&>(*this).anchorAt(fileno);
881}
882
884Ipc::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
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
904void
905Ipc::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
913{
914 const int name = nameByKey(key);
915 return fileNoByName(name);
916}
917
920{
921 return anchorAt(fileNoByKey(key));
922}
923
926{
927 assert(validSlice(sliceId));
928 return slices->items[sliceId];
929}
930
932Ipc::StoreMap::sliceAt(const SliceId sliceId) const
933{
934 return const_cast<StoreMap&>(*this).sliceAt(sliceId);
935}
936
937/* Ipc::StoreMapAnchor */
938
939Ipc::StoreMapAnchor::StoreMapAnchor(): start(0), splicingPoint(-1)
940{
941 // keep in sync with rewind()
942}
943
944void
946{
947 memcpy(key, aKey, sizeof(key));
948 waitingToBeFreed = Store::Root().markedForDeletion(aKey);
949}
950
951bool
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
958void
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
978void
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)
998 else
1000}
1001
1002void
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
1018 entry(anEntry)
1019{
1020 entry->lock("Ipc::StoreMapUpdate1");
1021}
1022
1024 entry(other.entry),
1025 stale(other.stale),
1026 fresh(other.fresh)
1027{
1028 entry->lock("Ipc::StoreMapUpdate2");
1029}
1030
1032{
1033 entry->unlock("Ipc::StoreMapUpdate");
1034}
1035
1036/* Ipc::StoreMap::Owner */
1037
1039 fileNos(nullptr),
1040 anchors(nullptr),
1041 slices(nullptr)
1042{
1043}
1044
1046{
1047 delete fileNos;
1048 delete anchors;
1049 delete slices;
1050}
1051
1052/* Ipc::StoreMapAnchors */
1053
1055 count(0),
1056 victim(0),
1057 capacity(aCapacity),
1058 items(aCapacity)
1059{
1060}
1061
1062size_t
1064{
1065 return SharedMemorySize(capacity);
1066}
1067
1068size_t
1070{
1071 return sizeof(StoreMapAnchors) + capacity * sizeof(StoreMapAnchor);
1072}
1073
#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:71
#define assert(EX)
Definition: assert.h:17
static time_t now
Definition: cachemgr.cc:109
ConservativeTimer(const Clock::duration max)
Definition: StoreMap.cc:777
bool expired()
whether the current time reached the provided maximum time
Definition: StoreMap.cc:783
Clock::time_point lastTime
the time of the last expired() call, initially equals to startTime
Definition: StoreMap.cc:795
const Clock::time_point maxTime
after going past this point in time, expired() becomes true
Definition: StoreMap.cc:797
Clock::time_point startTime
the object creation time
Definition: StoreMap.cc:793
std::chrono::high_resolution_clock Clock
Definition: StoreMap.cc:775
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:66
void unlockHeaders()
undo successful lockHeaders()
void switchExclusiveToShared()
bool lockHeaders()
lock for [readable] metadata update or return false
std::atomic< uint32_t > readers
number of reading users
Definition: ReadWriteLock.h:49
void unlockExclusive()
undo successful exclusiveLock()
bool lockExclusive()
lock for modification or return false
std::atomic_flag updating
a reader is updating metadata/headers
Definition: ReadWriteLock.h:52
std::atomic< bool > appending
the writer has promised to only append
Definition: ReadWriteLock.h:51
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:1003
bool sameKey(const cache_key *const aKey) const
Definition: StoreMap.cc:952
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:959
bool reading() const
Definition: StoreMap.h:75
void setKey(const cache_key *const aKey)
Definition: StoreMap.cc:945
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:979
StoreMapAnchors(const int aCapacity)
Definition: StoreMap.cc:1054
size_t sharedMemorySize() const
Definition: StoreMap.cc:1063
static size_t SharedMemorySize(const int anAnchorLimit)
Definition: StoreMap.cc:1069
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:1017
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:453
bool validateHit(const sfileno)
Definition: StoreMap.cc:801
bool openForUpdating(Update &update, sfileno fileNoHint)
finds and locks the Update entry for an exclusive metadata update
Definition: StoreMap.cc:523
Anchor * openForWritingAt(sfileno fileno, bool overwriteExisting=true)
Definition: StoreMap.cc:155
bool visitVictims(const NameFilter filter)
Definition: StoreMap.cc:685
bool markedForDeletion(const cache_key *const)
Definition: StoreMap.cc:355
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:287
bool validEntry(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:758
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:919
int entryCount() const
number of writeable and readable entries
Definition: StoreMap.cc:739
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:905
void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock)
unconditionally frees an already locked chain of slots, unlocking if needed
Definition: StoreMap.cc:375
const Anchor * openOrCreateForReading(const cache_key *, sfileno &, const StoreEntry &)
openForReading() but creates a new entry if there is no old one
Definition: StoreMap.cc:103
Slice & sliceAt(const SliceId sliceId)
Definition: StoreMap.cc:925
void closeForWriting(const sfileno fileno)
successfully finish creating or updating the entry at fileno pos
Definition: StoreMap.cc:200
void abortUpdating(Update &update)
undoes partial update, unlocks, and cleans up
Definition: StoreMap.cc:269
SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const
Definition: StoreMap.cc:421
const Anchor * openForReading(const cache_key *const key, sfileno &fileno)
opens entry (identified by key) for reading, increments read level
Definition: StoreMap.cc:440
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:313
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:497
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:722
const Anchor * peekAtWriter(const sfileno fileno) const
Definition: StoreMap.cc:297
void closeForReadingAndFreeIdle(const sfileno fileno)
same as closeForReading() but also frees the entry if it is unlocked
Definition: StoreMap.cc:506
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:764
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:884
void prepFreeSlice(const SliceId sliceId)
prepare a chain-unaffiliated slice for being added to an entry chain
Definition: StoreMap.cc:413
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:605
std::function< bool(const sfileno name)> NameFilter
Definition: StoreMap.h:386
bool openKeyless(Update::Edition &edition)
Definition: StoreMap.cc:587
bool purgeOne()
either finds and frees an entry with at least 1 slice or returns false
Definition: StoreMap.cc:702
void updateStats(ReadWriteLockStats &stats) const
adds approximate current stats to the supplied ones
Definition: StoreMap.cc:751
sfileno fileNoByKey(const cache_key *const key) const
computes map entry anchor position for a given entry key
Definition: StoreMap.cc:912
bool hasReadableEntry(const cache_key *const)
whether the index contains a valid readable entry with the given key
Definition: StoreMap.cc:363
StoreMapSliceId SliceId
Definition: StoreMap.h:227
void freeEntryByKey(const cache_key *const key)
Definition: StoreMap.cc:331
sfileno fileNoByName(const sfileno name) const
computes anchor position for a given entry name
Definition: StoreMap.cc:894
Anchor & anchorAt(const sfileno fileno)
Definition: StoreMap.cc:871
const Anchor & peekAtEntry(const sfileno fileno) const
Definition: StoreMap.cc:307
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:745
void freeChainAt(SliceId sliceId, const SliceId splicingPoint)
unconditionally frees an already locked chain of slots; no anchor maintenance
Definition: StoreMap.cc:391
int entryLimit() const
maximum entryCount() possible
Definition: StoreMap.cc:733
Definition: SBuf.h:94
const char * c_str()
Definition: SBuf.cc:516
std::chrono::nanoseconds paranoid_hit_validation
Definition: SquidConfig.h:352
uint64_t refusalsDueToZeroSize
Definition: StatCounters.h:163
uint64_t refusalsDueToTimeLimit
Definition: StatCounters.h:164
uint64_t attempts
Definition: StatCounters.h:161
struct StatCounters::@133 hitValidation
uint64_t failures
Definition: StatCounters.h:165
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:419
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:193
#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:931
unsigned char cache_key
Store key.
Definition: forward.h:29
signed_int32_t sfileno
Definition: forward.h:22
@ SwapFilenMax
Definition: forward.h:26
const char * storeKeyText(const cache_key *key)
static hash_table * hash
Definition: text_backend.cc:41

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors