2 * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
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.
9 /* DEBUG: section 54 Interprocess Communication */
12 #include "ipc/StoreMap.h"
13 #include "sbuf/SBuf.h"
14 #include "SquidConfig.h"
15 #include "StatCounters.h"
17 #include "store/Controller.h"
18 #include "store_key_md5.h"
24 StoreMapSlicesId(const SBuf
&path
)
26 return Ipc::Mem::Segment::Name(path
, "slices");
30 StoreMapAnchorsId(const SBuf
&path
)
32 return Ipc::Mem::Segment::Name(path
, "anchors");
36 StoreMapFileNosId(const SBuf
&path
)
38 return Ipc::Mem::Segment::Name(path
, "filenos");
41 Ipc::StoreMap::Owner
*
42 Ipc::StoreMap::Init(const SBuf
&path
, const int sliceLimit
)
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
);
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())),
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
68 Ipc::StoreMap::compareVersions(const sfileno fileno
, time_t newVersion
) const
70 const Anchor
&inode
= anchorAt(fileno
);
72 // note: we do not lock, so comparison may be inaccurate
77 if (const time_t diff
= newVersion
- inode
.basics
.timestamp
)
78 return diff
< 0 ? -1 : +1;
84 Ipc::StoreMap::forgetWritingEntry(sfileno fileno
)
86 Anchor
&inode
= anchorAt(fileno
);
88 assert(inode
.writing());
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)
96 inode
.lock
.unlockExclusive();
99 debugs(54, 8, "closed entry " << fileno
<< " for writing " << path
);
102 const Ipc::StoreMap::Anchor
*
103 Ipc::StoreMap::openOrCreateForReading(const cache_key
*const key
, sfileno
&fileno
, const StoreEntry
&entry
)
105 debugs(54, 5, "opening/creating entry with key " << storeKeyText(key
)
106 << " for reading " << path
);
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
)) {
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();
121 assert(anchor
->complete());
123 debugs(54, 5, "switched entry " << fileno
<< " from writing to reading " << path
);
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
)) {
135 // slow entry creator or some other problem
139 Ipc::StoreMap::Anchor
*
140 Ipc::StoreMap::openForWriting(const cache_key
*const key
, sfileno
&fileno
)
142 debugs(54, 5, "opening entry with key " << storeKeyText(key
)
143 << " for writing " << path
);
144 const int idx
= fileNoByKey(key
);
146 if (Anchor
*anchor
= openForWritingAt(idx
)) {
154 Ipc::StoreMap::Anchor
*
155 Ipc::StoreMap::openForWritingAt(const sfileno fileno
, bool overwriteExisting
)
157 Anchor
&s
= anchorAt(fileno
);
158 ReadWriteLock
&lock
= s
.lock
;
160 if (lock
.lockExclusive()) {
161 assert(s
.writing() && !s
.reading());
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
);
171 // free if the entry was used, keeping the entry locked
172 if (s
.waitingToBeFreed
|| !s
.empty())
173 freeChain(fileno
, s
, true);
176 s
.start
= -1; // we have not allocated any slices yet
177 s
.splicingPoint
= -1;
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
185 debugs(54, 5, "cannot open busy entry " << fileno
<<
186 " for writing " << path
);
191 Ipc::StoreMap::startAppending(const sfileno fileno
)
193 Anchor
&s
= anchorAt(fileno
);
195 s
.lock
.startAppending();
196 debugs(54, 5, "restricted entry " << fileno
<< " to appending " << path
);
200 Ipc::StoreMap::closeForWriting(const sfileno fileno
)
202 Anchor
&s
= anchorAt(fileno
);
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
211 Ipc::StoreMap::switchWritingToReading(const sfileno fileno
)
213 debugs(54, 5, "switching entry " << fileno
<< " from writing to reading " << path
);
214 Anchor
&s
= anchorAt(fileno
);
216 s
.lock
.switchExclusiveToShared();
217 assert(s
.complete());
220 Ipc::StoreMap::Slice
&
221 Ipc::StoreMap::writeableSlice(const AnchorId anchorId
, const SliceId sliceId
)
223 assert(anchorAt(anchorId
).writing());
224 assert(validSlice(sliceId
));
225 return sliceAt(sliceId
);
228 const Ipc::StoreMap::Slice
&
229 Ipc::StoreMap::readableSlice(const AnchorId anchorId
, const SliceId sliceId
) const
231 assert(anchorAt(anchorId
).reading());
232 assert(validSlice(sliceId
));
233 return sliceAt(sliceId
);
236 Ipc::StoreMap::Anchor
&
237 Ipc::StoreMap::writeableEntry(const AnchorId anchorId
)
239 assert(anchorAt(anchorId
).writing());
240 return anchorAt(anchorId
);
243 const Ipc::StoreMap::Anchor
&
244 Ipc::StoreMap::readableEntry(const AnchorId anchorId
) const
246 assert(anchorAt(anchorId
).reading());
247 return anchorAt(anchorId
);
251 Ipc::StoreMap::abortWriting(const sfileno fileno
)
253 debugs(54, 5, "aborting entry " << fileno
<< " for writing " << path
);
254 Anchor
&s
= anchorAt(fileno
);
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
);
261 s
.waitingToBeFreed
= true;
262 s
.writerHalted
= true;
263 s
.lock
.unlockExclusive();
264 debugs(54, 5, "closed dirty entry " << fileno
<< " for writing " << path
);
269 Ipc::StoreMap::abortUpdating(Update
&update
)
271 const sfileno fileno
= update
.stale
.fileNo
;
272 debugs(54, 5, "aborting entry " << fileno
<< " for updating " << path
);
274 AssertFlagIsSet(update
.stale
.anchor
->lock
.updating
);
275 update
.stale
.anchor
->lock
.unlockHeaders();
276 closeForReading(update
.stale
.fileNo
);
277 update
.stale
= Update::Edition();
280 abortWriting(update
.fresh
.fileNo
);
281 update
.fresh
= Update::Edition();
283 debugs(54, 5, "aborted entry " << fileno
<< " for updating " << path
);
286 const Ipc::StoreMap::Anchor
*
287 Ipc::StoreMap::peekAtReader(const sfileno fileno
) const
289 const Anchor
&s
= anchorAt(fileno
);
291 return &s
; // immediate access by lock holder so no locking
292 assert(s
.writing()); // must be locked for reading or writing
296 const Ipc::StoreMap::Anchor
*
297 Ipc::StoreMap::peekAtWriter(const sfileno fileno
) const
299 const Anchor
&s
= anchorAt(fileno
);
301 return &s
; // immediate access by lock holder so no locking
302 assert(s
.reading()); // must be locked for reading or writing
306 const Ipc::StoreMap::Anchor
&
307 Ipc::StoreMap::peekAtEntry(const sfileno fileno
) const
309 return anchorAt(fileno
);
313 Ipc::StoreMap::freeEntry(const sfileno fileno
)
315 debugs(54, 5, "marking entry " << fileno
<< " to be freed in " << path
);
317 Anchor
&s
= anchorAt(fileno
);
319 if (s
.lock
.lockExclusive()) {
320 const bool result
= !s
.waitingToBeFreed
&& !s
.empty();
321 freeChain(fileno
, s
, false);
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);
331 Ipc::StoreMap::freeEntryByKey(const cache_key
*const key
)
333 debugs(54, 5, "marking entry with key " << storeKeyText(key
)
334 << " to be freed in " << path
);
336 const int idx
= fileNoByKey(key
);
337 Anchor
&s
= anchorAt(idx
);
338 if (s
.lock
.lockExclusive()) {
340 freeChain(idx
, s
, true);
341 s
.lock
.unlockExclusive();
342 } else if (s
.lock
.lockShared()) {
344 s
.waitingToBeFreed
= true; // mark to free it later
345 s
.lock
.unlockShared();
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
350 s
.waitingToBeFreed
= true; // mark to free it later
355 Ipc::StoreMap::markedForDeletion(const cache_key
*const key
)
357 const int idx
= fileNoByKey(key
);
358 const Anchor
&s
= anchorAt(idx
);
359 return s
.sameKey(key
) ? bool(s
.waitingToBeFreed
) : false;
363 Ipc::StoreMap::hasReadableEntry(const cache_key
*const key
)
366 if (openForReading(reinterpret_cast<const cache_key
*>(key
), index
)) {
367 closeForReading(index
);
373 /// unconditionally frees an already locked chain of slots, unlocking if needed
375 Ipc::StoreMap::freeChain(const sfileno fileno
, Anchor
&inode
, const bool keepLocked
)
377 debugs(54, 7, "freeing entry " << fileno
<<
380 freeChainAt(inode
.start
, inode
.splicingPoint
);
384 inode
.lock
.unlockExclusive();
386 debugs(54, 5, "freed entry " << fileno
<< " in " << path
);
389 /// unconditionally frees an already locked chain of slots; no anchor maintenance
391 Ipc::StoreMap::freeChainAt(SliceId sliceId
, const SliceId splicingPoint
)
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
;
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
409 debugs(54, 7, "freed chain #" << chainId
<< " in " << path
);
413 Ipc::StoreMap::prepFreeSlice(const SliceId sliceId
)
415 // TODO: Move freeSlots here, along with reserveSlotForWriting() logic.
416 assert(validSlice(sliceId
));
417 sliceAt(sliceId
).clear();
420 Ipc::StoreMap::SliceId
421 Ipc::StoreMap::sliceContaining(const sfileno fileno
, const uint64_t bytesNeeded
) const
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
)
432 lastSlice
= slice
.next
;
434 debugs(54, 7, "entry " << fileno
<< " has " << bytesNeeded
<< '/' << bytesSeen
<<
435 " bytes at slice " << lastSlice
<< " in " << path
);
436 return lastSlice
; // may be negative
439 const Ipc::StoreMap::Anchor
*
440 Ipc::StoreMap::openForReading(const cache_key
*const key
, sfileno
&fileno
)
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
)) {
447 return anchor
; // locked for reading
452 const Ipc::StoreMap::Anchor
*
453 Ipc::StoreMap::openForReadingAt(const sfileno fileno
, const cache_key
*const key
)
455 debugs(54, 5, "opening entry " << fileno
<< " for reading " << path
);
456 Anchor
&s
= anchorAt(fileno
);
458 if (!s
.lock
.lockShared()) {
459 debugs(54, 5, "cannot open busy entry " << fileno
<<
460 " for reading " << path
);
465 s
.lock
.unlockShared();
466 debugs(54, 7, "cannot open empty entry " << fileno
<<
467 " for reading " << path
);
471 if (s
.waitingToBeFreed
) {
472 s
.lock
.unlockShared();
473 debugs(54, 7, "cannot open marked entry " << fileno
<<
474 " for reading " << path
);
478 if (!s
.sameKey(key
)) {
479 s
.lock
.unlockShared();
480 debugs(54, 5, "cannot open wrong-key entry " << fileno
<<
481 " for reading " << path
);
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
);
492 debugs(54, 5, "opened entry " << fileno
<< " for reading " << path
);
497 Ipc::StoreMap::closeForReading(const sfileno fileno
)
499 Anchor
&s
= anchorAt(fileno
);
501 s
.lock
.unlockShared();
502 debugs(54, 5, "closed entry " << fileno
<< " for reading " << path
);
506 Ipc::StoreMap::closeForReadingAndFreeIdle(const sfileno fileno
)
508 auto &s
= anchorAt(fileno
);
511 if (!s
.lock
.unlockSharedAndSwitchToExclusive()) {
512 debugs(54, 5, "closed entry " << fileno
<< " for reading " << path
);
517 assert(!s
.reading());
518 freeChain(fileno
, s
, false);
519 debugs(54, 5, "closed idle entry " << fileno
<< " for reading " << path
);
523 Ipc::StoreMap::openForUpdating(Update
&update
, const sfileno fileNoHint
)
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
);
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
);
535 update
.stale
.fileNo
= fileNoHint
;
538 debugs(54, 5, "opening entry " << update
.stale
.fileNo
<< " of " << entry
<< " for updating " << path
);
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
);
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
);
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
);
566 /* stale anchor is properly locked; we can now use abortUpdating() if needed */
568 if (!openKeyless(update
.fresh
)) {
569 debugs(54, 5, "cannot open freshchainless entry " << update
.stale
.fileNo
<<
570 " for updating " << path
);
571 abortUpdating(update
);
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
);
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
587 Ipc::StoreMap::openKeyless(Update::Edition
&edition
)
589 return visitVictims([&](const sfileno name
) {
590 Update::Edition temp
;
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
);
605 Ipc::StoreMap::closeForUpdating(Update
&update
)
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);
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
);
619 /* the relative order of most operations is significant here */
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
;
628 Must(freshSplicingSlice
.next
== suffixStart
);
629 // either way, fresh chain uses the stale chain suffix now
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
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
);
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 */
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
);
652 /* free the stale chain prefix except for the shared suffix */
653 update
.stale
.anchor
->splicingPoint
= update
.stale
.splicingPoint
;
654 freeEntry(update
.stale
.fileNo
);
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
);
662 const Update updateSaved
= update
; // for post-close debugging below
664 /* unlock the stale anchor/chain */
665 update
.stale
.anchor
->lock
.unlockHeaders();
666 closeForReading(update
.stale
.fileNo
);
667 update
.stale
= Update::Edition();
669 // finally, unlock the fresh entry
670 closeForReading(update
.fresh
.fileNo
);
671 update
.fresh
= Update::Edition();
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");
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.
685 Ipc::StoreMap::visitVictims(const NameFilter visitor
)
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());
691 for (; tries
< searchLimit
; ++tries
) {
692 const sfileno name
= static_cast<sfileno
>(++anchors
->victim
% entryLimit());
697 debugs(54, 5, "no victims found in " << path
<< "; tried: " << tries
);
702 Ipc::StoreMap::purgeOne()
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
);
715 s
.lock
.unlockExclusive();
722 Ipc::StoreMap::importSlice(const SliceId sliceId
, const Slice
&slice
)
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
728 assert(validSlice(sliceId
));
729 sliceAt(sliceId
) = slice
;
733 Ipc::StoreMap::entryLimit() const
735 return min(sliceLimit(), static_cast<int>(SwapFilenMax
+1));
739 Ipc::StoreMap::entryCount() const
741 return anchors
->count
;
745 Ipc::StoreMap::sliceLimit() const
747 return slices
->capacity
;
751 Ipc::StoreMap::updateStats(ReadWriteLockStats
&stats
) const
753 for (int i
= 0; i
< anchors
->capacity
; ++i
)
754 anchorAt(i
).lock
.updateStats(stats
);
758 Ipc::StoreMap::validEntry(const int pos
) const
760 return 0 <= pos
&& pos
< entryLimit();
764 Ipc::StoreMap::validSlice(const int pos
) const
766 return 0 <= pos
&& pos
< sliceLimit();
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
775 typedef std::chrono::high_resolution_clock Clock
;
777 explicit ConservativeTimer(const Clock::duration max
):
778 startTime(Clock::now()),
780 maxTime(startTime
+ max
) {}
782 /// whether the current time reached the provided maximum time
784 const auto currentTime
= Clock::now();
785 if (currentTime
< lastTime
) // time went backwards
787 lastTime
= currentTime
;
788 return lastTime
> maxTime
;
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
;
801 Ipc::StoreMap::validateHit(const sfileno fileno
)
803 ConservativeTimer
timer(Config
.paranoid_hit_validation
);
804 const auto timeIsLimited
= Config
.paranoid_hit_validation
< std::chrono::hours(24);
806 const auto &anchor
= anchorAt(fileno
);
808 ++statCounter
.hitValidation
.attempts
;
810 if (!anchor
.basics
.swap_file_sz
) {
811 ++statCounter
.hitValidation
.refusalsDueToZeroSize
;
812 return true; // presume valid; cannot validate w/o known swap_file_sz
815 if (!anchor
.lock
.lockHeaders()) {
816 ++statCounter
.hitValidation
.refusalsDueToLocking
;
817 return true; // presume valid; cannot validate changing entry
820 const uint64_t expectedByteCount
= anchor
.basics
.swap_file_sz
;
822 size_t actualSliceCount
= 0;
823 uint64_t actualByteCount
= 0;
824 SliceId lastSeenSlice
= anchor
.start
;
825 while (lastSeenSlice
>= 0) {
827 if (!validSlice(lastSeenSlice
))
829 const auto &slice
= sliceAt(lastSeenSlice
);
830 actualByteCount
+= slice
.size
;
831 if (actualByteCount
> expectedByteCount
)
833 lastSeenSlice
= slice
.next
;
834 if (timeIsLimited
&& timer
.expired()) {
835 anchor
.lock
.unlockHeaders();
836 ++statCounter
.hitValidation
.refusalsDueToTimeLimit
;
841 anchor
.lock
.unlockHeaders();
843 if (actualByteCount
== expectedByteCount
&& lastSeenSlice
< 0)
846 ++statCounter
.hitValidation
.failures
;
848 debugs(54, DBG_IMPORTANT
, "ERROR: Squid BUG: purging corrupted cache entry " << fileno
<<
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"
870 Ipc::StoreMap::Anchor
&
871 Ipc::StoreMap::anchorAt(const sfileno fileno
)
873 assert(validEntry(fileno
));
874 return anchors
->items
[fileno
];
877 const Ipc::StoreMap::Anchor
&
878 Ipc::StoreMap::anchorAt(const sfileno fileno
) const
880 return const_cast<StoreMap
&>(*this).anchorAt(fileno
);
884 Ipc::StoreMap::nameByKey(const cache_key
*const key
) const
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();
894 Ipc::StoreMap::fileNoByName(const sfileno name
) const
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
])
903 /// map `name` to `fileNo`
905 Ipc::StoreMap::relocate(const sfileno name
, const sfileno fileno
)
907 // preserve special meaning for zero; see fileNoByName
908 fileNos
->items
[name
] = fileno
+1;
912 Ipc::StoreMap::fileNoByKey(const cache_key
*const key
) const
914 const int name
= nameByKey(key
);
915 return fileNoByName(name
);
918 Ipc::StoreMap::Anchor
&
919 Ipc::StoreMap::anchorByKey(const cache_key
*const key
)
921 return anchorAt(fileNoByKey(key
));
924 Ipc::StoreMap::Slice
&
925 Ipc::StoreMap::sliceAt(const SliceId sliceId
)
927 assert(validSlice(sliceId
));
928 return slices
->items
[sliceId
];
931 const Ipc::StoreMap::Slice
&
932 Ipc::StoreMap::sliceAt(const SliceId sliceId
) const
934 return const_cast<StoreMap
&>(*this).sliceAt(sliceId
);
937 /* Ipc::StoreMapAnchor */
939 Ipc::StoreMapAnchor::StoreMapAnchor(): start(0), splicingPoint(-1)
941 // keep in sync with rewind()
945 Ipc::StoreMapAnchor::setKey(const cache_key
*const aKey
)
947 memcpy(key
, aKey
, sizeof(key
));
948 waitingToBeFreed
= Store::Root().markedForDeletion(aKey
);
952 Ipc::StoreMapAnchor::sameKey(const cache_key
*const aKey
) const
954 const uint64_t *const k
= reinterpret_cast<const uint64_t *>(aKey
);
955 return k
[0] == key
[0] && k
[1] == key
[1];
959 Ipc::StoreMapAnchor::set(const StoreEntry
&from
, const cache_key
*aKey
)
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
;
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
;
974 EBIT_CLR(cleanFlags
, KEY_PRIVATE
);
975 basics
.flags
= cleanFlags
;
979 Ipc::StoreMapAnchor::exportInto(StoreEntry
&into
) const
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 const bool collapsingRequired
= into
.hittingRequiresCollapsing();
989 into
.flags
= basics
.flags
;
990 // There are possibly several flags we do not need to overwrite,
991 // and ENTRY_REQUIRES_COLLAPSING is one of them.
992 // TODO: check for other flags.
993 into
.setCollapsingRequirement(collapsingRequired
);
997 Ipc::StoreMapAnchor::rewind()
1002 memset(&key
, 0, sizeof(key
));
1004 waitingToBeFreed
= false;
1005 writerHalted
= false;
1006 // but keep the lock
1009 /* Ipc::StoreMapUpdate */
1011 Ipc::StoreMapUpdate::StoreMapUpdate(StoreEntry
*anEntry
):
1014 entry
->lock("Ipc::StoreMapUpdate1");
1017 Ipc::StoreMapUpdate::StoreMapUpdate(const StoreMapUpdate
&other
):
1022 entry
->lock("Ipc::StoreMapUpdate2");
1025 Ipc::StoreMapUpdate::~StoreMapUpdate()
1027 entry
->unlock("Ipc::StoreMapUpdate");
1030 /* Ipc::StoreMap::Owner */
1032 Ipc::StoreMap::Owner::Owner():
1039 Ipc::StoreMap::Owner::~Owner()
1046 /* Ipc::StoreMapAnchors */
1048 Ipc::StoreMapAnchors::StoreMapAnchors(const int aCapacity
):
1051 capacity(aCapacity
),
1057 Ipc::StoreMapAnchors::sharedMemorySize() const
1059 return SharedMemorySize(capacity
);
1063 Ipc::StoreMapAnchors::SharedMemorySize(const int capacity
)
1065 return sizeof(StoreMapAnchors
) + capacity
* sizeof(StoreMapAnchor
);