StoreMap.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2020 The Squid Software Foundation and contributors
3  *
4  * Squid software is distributed under GPLv2+ license and includes
5  * contributions from numerous individuals and organizations.
6  * Please see the COPYING and CONTRIBUTORS files for details.
7  */
8 
9 /* DEBUG: section 54 Interprocess Communication */
10 
11 #include "squid.h"
12 #include "ipc/StoreMap.h"
13 #include "sbuf/SBuf.h"
14 #include "SquidConfig.h"
15 #include "StatCounters.h"
16 #include "Store.h"
17 #include "store/Controller.h"
18 #include "store_key_md5.h"
19 #include "tools.h"
20 
21 #include <chrono>
22 
23 static SBuf
24 StoreMapSlicesId(const SBuf &path)
25 {
26  return Ipc::Mem::Segment::Name(path, "slices");
27 }
28 
29 static SBuf
30 StoreMapAnchorsId(const SBuf &path)
31 {
32  return Ipc::Mem::Segment::Name(path, "anchors");
33 }
34 
35 static SBuf
36 StoreMapFileNosId(const SBuf &path)
37 {
38  return Ipc::Mem::Segment::Name(path, "filenos");
39 }
40 
42 Ipc::StoreMap::Init(const SBuf &path, const int sliceLimit)
43 {
44  assert(sliceLimit > 0); // we should not be created otherwise
45  const int anchorLimit = min(sliceLimit, static_cast<int>(SwapFilenMax));
46  Owner *owner = new Owner;
47  owner->fileNos = shm_new(FileNos)(StoreMapFileNosId(path).c_str(), anchorLimit);
48  owner->anchors = shm_new(Anchors)(StoreMapAnchorsId(path).c_str(), anchorLimit);
50  debugs(54, 5, "created " << path << " with " << anchorLimit << '+' << sliceLimit);
51  return owner;
52 }
53 
54 Ipc::StoreMap::StoreMap(const SBuf &aPath): cleaner(NULL), path(aPath),
55  fileNos(shm_old(FileNos)(StoreMapFileNosId(path).c_str())),
56  anchors(shm_old(Anchors)(StoreMapAnchorsId(path).c_str())),
57  slices(shm_old(Slices)(StoreMapSlicesId(path).c_str())),
58  hitValidation(true)
59 {
60  debugs(54, 5, "attached " << path << " with " <<
61  fileNos->capacity << '+' <<
62  anchors->capacity << '+' << slices->capacity);
63  assert(entryLimit() > 0); // key-to-position mapping requires this
64  assert(entryLimit() <= sliceLimit()); // at least one slice per entry
65 }
66 
67 int
68 Ipc::StoreMap::compareVersions(const sfileno fileno, time_t newVersion) const
69 {
70  const Anchor &inode = anchorAt(fileno);
71 
72  // note: we do not lock, so comparison may be inaccurate
73 
74  if (inode.empty())
75  return +2;
76 
77  if (const time_t diff = newVersion - inode.basics.timestamp)
78  return diff < 0 ? -1 : +1;
79 
80  return 0;
81 }
82 
83 void
85 {
86  Anchor &inode = anchorAt(fileno);
87 
88  assert(inode.writing());
89 
90  // we do not iterate slices because we were told to forget about
91  // them; the caller is responsible for freeing them (most likely
92  // our slice list is incomplete or has holes)
93 
94  inode.rewind();
95 
96  inode.lock.unlockExclusive();
97  --anchors->count;
98 
99  debugs(54, 8, "closed entry " << fileno << " for writing " << path);
100 }
101 
102 const Ipc::StoreMap::Anchor *
103 Ipc::StoreMap::openOrCreateForReading(const cache_key *const key, sfileno &fileno, const StoreEntry &entry)
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 NULL;
152 }
153 
155 Ipc::StoreMap::openForWritingAt(const sfileno fileno, bool overwriteExisting)
156 {
157  Anchor &s = anchorAt(fileno);
158  ReadWriteLock &lock = s.lock;
159 
160  if (lock.lockExclusive()) {
161  assert(s.writing() && !s.reading());
162 
163  // bail if we cannot empty this position
164  if (!s.waitingToBeFreed && !s.empty() && !overwriteExisting) {
165  lock.unlockExclusive();
166  debugs(54, 5, "cannot open existing entry " << fileno <<
167  " for writing " << path);
168  return NULL;
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 NULL;
188 }
189 
190 void
192 {
193  Anchor &s = anchorAt(fileno);
194  assert(s.writing());
195  s.lock.startAppending();
196  debugs(54, 5, "restricted entry " << fileno << " to appending " << path);
197 }
198 
199 void
201 {
202  Anchor &s = anchorAt(fileno);
203  assert(s.writing());
204  // TODO: assert(!s.empty()); // i.e., unlocked s becomes s.complete()
205  s.lock.unlockExclusive();
206  debugs(54, 5, "closed entry " << fileno << " for writing " << path);
207  // cannot assert completeness here because we have no lock
208 }
209 
210 void
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 
221 Ipc::StoreMap::writeableSlice(const AnchorId anchorId, const SliceId sliceId)
222 {
223  assert(anchorAt(anchorId).writing());
224  assert(validSlice(sliceId));
225  return sliceAt(sliceId);
226 }
227 
228 const Ipc::StoreMap::Slice &
229 Ipc::StoreMap::readableSlice(const AnchorId anchorId, const SliceId sliceId) const
230 {
231  assert(anchorAt(anchorId).reading());
232  assert(validSlice(sliceId));
233  return sliceAt(sliceId);
234 }
235 
238 {
239  assert(anchorAt(anchorId).writing());
240  return anchorAt(anchorId);
241 }
242 
243 const Ipc::StoreMap::Anchor &
245 {
246  assert(anchorAt(anchorId).reading());
247  return anchorAt(anchorId);
248 }
249 
250 void
252 {
253  debugs(54, 5, "aborting entry " << fileno << " for writing " << path);
254  Anchor &s = anchorAt(fileno);
255  assert(s.writing());
256  s.lock.appending = false; // locks out any new readers
257  if (!s.lock.readers) {
258  freeChain(fileno, s, false);
259  debugs(54, 5, "closed clean entry " << fileno << " for writing " << path);
260  } else {
261  s.waitingToBeFreed = true;
262  s.writerHalted = true;
263  s.lock.unlockExclusive();
264  debugs(54, 5, "closed dirty entry " << fileno << " for writing " << path);
265  }
266 }
267 
268 void
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 
286 const Ipc::StoreMap::Anchor *
288 {
289  const Anchor &s = anchorAt(fileno);
290  if (s.reading())
291  return &s; // immediate access by lock holder so no locking
292  assert(s.writing()); // must be locked for reading or writing
293  return nullptr;
294 }
295 
296 const Ipc::StoreMap::Anchor *
298 {
299  const Anchor &s = anchorAt(fileno);
300  if (s.writing())
301  return &s; // immediate access by lock holder so no locking
302  assert(s.reading()); // must be locked for reading or writing
303  return nullptr;
304 }
305 
306 const Ipc::StoreMap::Anchor &
308 {
309  return anchorAt(fileno);
310 }
311 
312 bool
314 {
315  debugs(54, 5, "marking entry " << fileno << " to be freed in " << path);
316 
317  Anchor &s = anchorAt(fileno);
318 
319  if (s.lock.lockExclusive()) {
320  const bool result = !s.waitingToBeFreed && !s.empty();
321  freeChain(fileno, s, false);
322  return result;
323  }
324 
325  uint8_t expected = false;
326  // mark to free the locked entry later (if not already marked)
327  return s.waitingToBeFreed.compare_exchange_strong(expected, true);
328 }
329 
330 void
332 {
333  debugs(54, 5, "marking entry with key " << storeKeyText(key)
334  << " to be freed in " << path);
335 
336  const int idx = fileNoByKey(key);
337  Anchor &s = anchorAt(idx);
338  if (s.lock.lockExclusive()) {
339  if (s.sameKey(key))
340  freeChain(idx, s, true);
341  s.lock.unlockExclusive();
342  } else if (s.lock.lockShared()) {
343  if (s.sameKey(key))
344  s.waitingToBeFreed = true; // mark to free it later
345  s.lock.unlockShared();
346  } else {
347  // we cannot be sure that the entry we found is ours because we do not
348  // have a lock on it, but we still check to minimize false deletions
349  if (s.sameKey(key))
350  s.waitingToBeFreed = true; // mark to free it later
351  }
352 }
353 
354 bool
356 {
357  const int idx = fileNoByKey(key);
358  const Anchor &s = anchorAt(idx);
359  return s.sameKey(key) ? bool(s.waitingToBeFreed) : false;
360 }
361 
362 bool
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 
374 void
375 Ipc::StoreMap::freeChain(const sfileno fileno, Anchor &inode, const bool keepLocked)
376 {
377  debugs(54, 7, "freeing entry " << fileno <<
378  " in " << path);
379  if (!inode.empty())
380  freeChainAt(inode.start, inode.splicingPoint);
381  inode.rewind();
382 
383  if (!keepLocked)
384  inode.lock.unlockExclusive();
385  --anchors->count;
386  debugs(54, 5, "freed entry " << fileno << " in " << path);
387 }
388 
390 void
391 Ipc::StoreMap::freeChainAt(SliceId sliceId, const SliceId splicingPoint)
392 {
393  static uint64_t ChainId = 0; // to pair freeing/freed calls in debugs()
394  const uint64_t chainId = ++ChainId;
395  debugs(54, 7, "freeing chain #" << chainId << " starting at " << sliceId << " in " << path);
396  while (sliceId >= 0) {
397  Slice &slice = sliceAt(sliceId);
398  const SliceId nextId = slice.next;
399  slice.clear();
400  if (cleaner)
401  cleaner->noteFreeMapSlice(sliceId); // might change slice state
402  if (sliceId == splicingPoint) {
403  debugs(54, 5, "preserving chain #" << chainId << " in " << path <<
404  " suffix after slice " << splicingPoint);
405  break; // do not free the rest of the chain
406  }
407  sliceId = nextId;
408  }
409  debugs(54, 7, "freed chain #" << chainId << " in " << path);
410 }
411 
412 void
414 {
415  // TODO: Move freeSlots here, along with reserveSlotForWriting() logic.
416  assert(validSlice(sliceId));
417  sliceAt(sliceId).clear();
418 }
419 
421 Ipc::StoreMap::sliceContaining(const sfileno fileno, const uint64_t bytesNeeded) const
422 {
423  const Anchor &anchor = anchorAt(fileno);
424  Must(anchor.reading());
425  uint64_t bytesSeen = 0;
426  SliceId lastSlice = anchor.start;
427  while (lastSlice >= 0) {
428  const Slice &slice = sliceAt(lastSlice);
429  bytesSeen += slice.size;
430  if (bytesSeen >= bytesNeeded)
431  break;
432  lastSlice = slice.next;
433  }
434  debugs(54, 7, "entry " << fileno << " has " << bytesNeeded << '/' << bytesSeen <<
435  " bytes at slice " << lastSlice << " in " << path);
436  return lastSlice; // may be negative
437 }
438 
439 const Ipc::StoreMap::Anchor *
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 NULL;
450 }
451 
452 const Ipc::StoreMap::Anchor *
453 Ipc::StoreMap::openForReadingAt(const sfileno fileno, const cache_key *const key)
454 {
455  debugs(54, 5, "opening entry " << fileno << " for reading " << path);
456  Anchor &s = anchorAt(fileno);
457 
458  if (!s.lock.lockShared()) {
459  debugs(54, 5, "cannot open busy entry " << fileno <<
460  " for reading " << path);
461  return NULL;
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 NULL;
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 NULL;
476  }
477 
478  if (!s.sameKey(key)) {
479  s.lock.unlockShared();
480  debugs(54, 5, "cannot open wrong-key entry " << fileno <<
481  " for reading " << path);
482  return nullptr;
483  }
484 
485  if (Config.paranoid_hit_validation.count() && hitValidation && !validateHit(fileno)) {
486  s.lock.unlockShared();
487  debugs(54, 5, "cannot open corrupted entry " << fileno <<
488  " for reading " << path);
489  return nullptr;
490  }
491 
492  debugs(54, 5, "opened entry " << fileno << " for reading " << path);
493  return &s;
494 }
495 
496 void
498 {
499  Anchor &s = anchorAt(fileno);
500  assert(s.reading());
501  s.lock.unlockShared();
502  debugs(54, 5, "closed entry " << fileno << " for reading " << path);
503 }
504 
505 void
507 {
508  auto &s = anchorAt(fileno);
509  assert(s.reading());
510 
511  if (!s.lock.unlockSharedAndSwitchToExclusive()) {
512  debugs(54, 5, "closed entry " << fileno << " for reading " << path);
513  return;
514  }
515 
516  assert(s.writing());
517  assert(!s.reading());
518  freeChain(fileno, s, false);
519  debugs(54, 5, "closed idle entry " << fileno << " for reading " << path);
520 }
521 
522 bool
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 
586 bool
588 {
589  return visitVictims([&](const sfileno name) {
590  Update::Edition temp;
591  temp.name = name;
592  temp.fileNo = fileNoByName(temp.name);
593  if ((temp.anchor = openForWritingAt(temp.fileNo))) {
594  debugs(54, 5, "created entry " << temp.fileNo <<
595  " for updating " << path);
596  Must(temp);
597  edition = temp;
598  return true;
599  }
600  return false;
601  });
602 }
603 
604 void
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 */
653  update.stale.anchor->splicingPoint = update.stale.splicingPoint;
654  freeEntry(update.stale.fileNo);
655 
656  // Make the stale anchor/chain reusable, reachable via update.fresh.name. If
657  // update.entry->swap_filen is still update.stale.fileNo, and the entry is
658  // using store, then the entry must have a lock on update.stale.fileNo,
659  // preventing its premature reuse by others.
660  relocate(update.fresh.name, update.stale.fileNo);
661 
662  const Update updateSaved = update; // for post-close debugging below
663 
664  /* unlock the stale anchor/chain */
665  update.stale.anchor->lock.unlockHeaders();
666  closeForReading(update.stale.fileNo);
667  update.stale = Update::Edition();
668 
669  // finally, unlock the fresh entry
670  closeForReading(update.fresh.fileNo);
671  update.fresh = Update::Edition();
672 
673  debugs(54, 5, "closed entry " << updateSaved.stale.fileNo << " of " << *updateSaved.entry <<
674  " named " << updateSaved.stale.name << " for updating " << path <<
675  " to fresh entry " << updateSaved.fresh.fileNo << " named " << updateSaved.fresh.name <<
676  " with [" << updateSaved.fresh.anchor->start << ',' << updateSaved.fresh.splicingPoint <<
677  "] prefix containing at least " << freshSplicingSlice.size << " bytes");
678 }
679 
684 bool
686 {
687  // Hopefully, we find a usable entry much sooner (TODO: use time?).
688  // The min() will protect us from division by zero inside the loop.
689  const int searchLimit = min(10000, entryLimit());
690  int tries = 0;
691  for (; tries < searchLimit; ++tries) {
692  const sfileno name = static_cast<sfileno>(++anchors->victim % entryLimit());
693  if (visitor(name))
694  return true;
695  }
696 
697  debugs(54, 5, "no victims found in " << path << "; tried: " << tries);
698  return false;
699 }
700 
701 bool
703 {
704  return visitVictims([&](const sfileno name) {
705  const sfileno fileno = fileNoByName(name);
706  Anchor &s = anchorAt(fileno);
707  if (s.lock.lockExclusive()) {
708  // the caller wants a free slice; empty anchor is not enough
709  if (!s.empty() && s.start >= 0) {
710  // this entry may be marked for deletion, and that is OK
711  freeChain(fileno, s, false);
712  debugs(54, 5, "purged entry " << fileno << " from " << path);
713  return true;
714  }
715  s.lock.unlockExclusive();
716  }
717  return false;
718  });
719 }
720 
721 void
722 Ipc::StoreMap::importSlice(const SliceId sliceId, const Slice &slice)
723 {
724  // Slices are imported into positions that should not be available via
725  // "get free slice" API. This is not something we can double check
726  // reliably because the anchor for the imported slice may not have been
727  // imported yet.
728  assert(validSlice(sliceId));
729  sliceAt(sliceId) = slice;
730 }
731 
732 int
734 {
735  return min(sliceLimit(), static_cast<int>(SwapFilenMax+1));
736 }
737 
738 int
740 {
741  return anchors->count;
742 }
743 
744 int
746 {
747  return slices->capacity;
748 }
749 
750 void
752 {
753  for (int i = 0; i < anchors->capacity; ++i)
754  anchorAt(i).lock.updateStats(stats);
755 }
756 
757 bool
758 Ipc::StoreMap::validEntry(const int pos) const
759 {
760  return 0 <= pos && pos < entryLimit();
761 }
762 
763 bool
764 Ipc::StoreMap::validSlice(const int pos) const
765 {
766  return 0 <= pos && pos < sliceLimit();
767 }
768 
773 {
774 public:
775  typedef std::chrono::high_resolution_clock Clock;
776 
777  explicit ConservativeTimer(const Clock::duration max):
778  startTime(Clock::now()),
779  lastTime(startTime),
780  maxTime(startTime + max) {}
781 
783  bool expired() {
784  const auto currentTime = Clock::now();
785  if (currentTime < lastTime) // time went backwards
786  return true;
787  lastTime = currentTime;
788  return lastTime > maxTime;
789  }
790 
791 private:
793  Clock::time_point startTime;
795  Clock::time_point lastTime;
797  const Clock::time_point maxTime;
798 };
799 
800 bool
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, "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 
878 Ipc::StoreMap::anchorAt(const sfileno fileno) const
879 {
880  return const_cast<StoreMap&>(*this).anchorAt(fileno);
881 }
882 
883 sfileno
884 Ipc::StoreMap::nameByKey(const cache_key *const key) const
885 {
886  assert(key);
887  const uint64_t *const k = reinterpret_cast<const uint64_t *>(key);
888  // TODO: use a better hash function
889  const int hash = (k[0] + k[1]) % entryLimit();
890  return hash;
891 }
892 
893 sfileno
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 
904 void
905 Ipc::StoreMap::relocate(const sfileno name, const sfileno fileno)
906 {
907  // preserve special meaning for zero; see fileNoByName
908  fileNos->items[name] = fileno+1;
909 }
910 
911 sfileno
912 Ipc::StoreMap::fileNoByKey(const cache_key *const key) const
913 {
914  const int name = nameByKey(key);
915  return fileNoByName(name);
916 }
917 
920 {
921  return anchorAt(fileNoByKey(key));
922 }
923 
926 {
927  assert(validSlice(sliceId));
928  return slices->items[sliceId];
929 }
930 
932 Ipc::StoreMap::sliceAt(const SliceId sliceId) const
933 {
934  return const_cast<StoreMap&>(*this).sliceAt(sliceId);
935 }
936 
937 /* Ipc::StoreMapAnchor */
938 
939 Ipc::StoreMapAnchor::StoreMapAnchor(): start(0), splicingPoint(-1)
940 {
941  // keep in sync with rewind()
942 }
943 
944 void
946 {
947  memcpy(key, aKey, sizeof(key));
948  waitingToBeFreed = Store::Root().markedForDeletion(aKey);
949 }
950 
951 bool
952 Ipc::StoreMapAnchor::sameKey(const cache_key *const aKey) const
953 {
954  const uint64_t *const k = reinterpret_cast<const uint64_t *>(aKey);
955  return k[0] == key[0] && k[1] == key[1];
956 }
957 
958 void
960 {
961  assert(writing() && !reading());
962  setKey(reinterpret_cast<const cache_key*>(aKey ? aKey : from.key));
963  basics.timestamp = from.timestamp;
964  basics.lastref = from.lastref;
965  basics.expires = from.expires;
966  basics.lastmod = from.lastModified();
967  basics.swap_file_sz = from.swap_file_sz;
968  basics.refcount = from.refcount;
969 
970  // do not copy key bit if we are not using from.key
971  // TODO: Replace KEY_PRIVATE with a nil StoreEntry::key!
972  uint16_t cleanFlags = from.flags;
973  if (aKey)
974  EBIT_CLR(cleanFlags, KEY_PRIVATE);
975  basics.flags = cleanFlags;
976 }
977 
978 void
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  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);
994 }
995 
996 void
998 {
999  assert(writing());
1000  start = 0;
1001  splicingPoint = -1;
1002  memset(&key, 0, sizeof(key));
1003  basics.clear();
1004  waitingToBeFreed = false;
1005  writerHalted = false;
1006  // but keep the lock
1007 }
1008 
1009 /* Ipc::StoreMapUpdate */
1010 
1012  entry(anEntry)
1013 {
1014  entry->lock("Ipc::StoreMapUpdate1");
1015 }
1016 
1018  entry(other.entry),
1019  stale(other.stale),
1020  fresh(other.fresh)
1021 {
1022  entry->lock("Ipc::StoreMapUpdate2");
1023 }
1024 
1026 {
1027  entry->unlock("Ipc::StoreMapUpdate");
1028 }
1029 
1030 /* Ipc::StoreMap::Owner */
1031 
1033  fileNos(nullptr),
1034  anchors(nullptr),
1035  slices(nullptr)
1036 {
1037 }
1038 
1040 {
1041  delete fileNos;
1042  delete anchors;
1043  delete slices;
1044 }
1045 
1046 /* Ipc::StoreMapAnchors */
1047 
1049  count(0),
1050  victim(0),
1051  capacity(aCapacity),
1052  items(aCapacity)
1053 {
1054 }
1055 
1056 size_t
1058 {
1059  return SharedMemorySize(capacity);
1060 }
1061 
1062 size_t
1064 {
1065  return sizeof(StoreMapAnchors) + capacity * sizeof(StoreMapAnchor);
1066 }
1067 
#define EBIT_CLR(flag, bit)
Definition: defines.h:106
Anchor & writeableEntry(const AnchorId anchorId)
writeable anchor for the entry created by openForWriting()
Definition: StoreMap.cc:237
void freeEntryByKey(const cache_key *const key)
Definition: StoreMap.cc:331
bool empty() const
Definition: StoreMap.h:74
class Ping::pingStats_ stats
approximate stats of a set of ReadWriteLocks
Definition: ReadWriteLock.h:63
time_t timestamp
Definition: Store.h:216
void closeForWriting(const sfileno fileno)
successfully finish creating or updating the entry at fileno pos
Definition: StoreMap.cc:200
void startAppending(const sfileno fileno)
restrict opened for writing entry to appending operations; allow reads
Definition: StoreMap.cc:191
uint64_t refusalsDueToZeroSize
Definition: StatCounters.h:163
uint64_t refusalsDueToLocking
Definition: StatCounters.h:162
void importSlice(const SliceId sliceId, const Slice &slice)
copies slice to its designated position
Definition: StoreMap.cc:722
unsigned char cache_key
Store key.
Definition: forward.h:29
bool lockShared()
lock for reading or return false
Clock::time_point startTime
the object creation time
Definition: StoreMap.cc:793
static hrtime_t now
Definition: ProfStats.cc:253
void lock(const char *context)
Definition: store.cc:459
StoreMap(const SBuf &aPath)
Definition: StoreMap.cc:54
bool sameKey(const cache_key *const aKey) const
Definition: StoreMap.cc:952
void relocate(const sfileno name, const sfileno fileno)
map name to fileNo
Definition: StoreMap.cc:905
@ KEY_PRIVATE
Definition: enums.h:102
Definition: SBuf.h:86
bool lockExclusive()
lock for modification or return false
size_t sharedMemorySize() const
Definition: StoreMap.cc:1057
void set(const StoreEntry &anEntry, const cache_key *aKey=nullptr)
store StoreEntry key and basics for an inode slot
Definition: StoreMap.cc:959
Edition fresh
new anchor and the updated chain prefix
Definition: StoreMap.h:209
std::atomic< bool > appending
the writer has promised to only append
Definition: ReadWriteLock.h:51
void forgetWritingEntry(const sfileno fileno)
Definition: StoreMap.cc:84
const Anchor * peekAtReader(const sfileno fileno) const
Definition: StoreMap.cc:287
SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const
Definition: StoreMap.cc:421
bool writing() const
Definition: StoreMap.h:76
Mem::Pointer< StoreMapAnchors > anchors
entry inodes (starting blocks)
Definition: StoreMap.h:366
const A & max(A const &lhs, A const &rhs)
std::atomic_flag updating
a reader is updating metadata/headers
Definition: ReadWriteLock.h:52
ReadWriteLock lock
protects slot data below
Definition: StoreMap.h:80
const Anchor * openForReadingAt(const sfileno, const cache_key *const)
opens entry (identified by sfileno) for reading, increments read level
Definition: StoreMap.cc:453
uint16_t flags
Definition: Store.h:224
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
void unlockShared()
undo successful sharedLock()
bool validEntry(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:758
time_t expires
Definition: Store.h:218
bool expired()
whether the current time reached the provided maximum time
Definition: StoreMap.cc:783
#define shm_new(Class)
Definition: Pointer.h:200
std::chrono::nanoseconds paranoid_hit_validation
Definition: SquidConfig.h:358
Anchor & anchorAt(const sfileno fileno)
Definition: StoreMap.cc:871
void updateStats(ReadWriteLockStats &stats) const
adds approximate current stats to the supplied ones
Definition: StoreMap.cc:751
std::atomic< uint32_t > readers
number of reading users
Definition: ReadWriteLock.h:49
#define DBG_IMPORTANT
Definition: Debug.h:46
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
static size_t SharedMemorySize(const int anAnchorLimit)
Definition: StoreMap.cc:1063
static Owner * Init(const SBuf &path, const int slotLimit)
initialize shared memory
Definition: StoreMap.cc:42
Mem::Pointer< StoreMapFileNos > fileNos
entry inodes (starting blocks)
Definition: StoreMap.h:365
uint64_t failures
Definition: StatCounters.h:165
std::atomic< uint8_t > writerHalted
whether StoreMap::abortWriting() was called for a read-locked entry
Definition: StoreMap.h:83
void unlockExclusive()
undo successful exclusiveLock()
std::atomic< StoreMapSliceId > start
where the chain of StoreEntry slices begins [app]
Definition: StoreMap.h:111
StoreMapUpdate(StoreEntry *anEntry)
Definition: StoreMap.cc:1011
std::atomic< StoreMapSliceId > splicingPoint
Definition: StoreMap.h:115
void closeForUpdating(Update &update)
makes updated info available to others, unlocks, and cleans up
Definition: StoreMap.cc:605
const Anchor * openForReading(const cache_key *const key, sfileno &fileno)
opens entry (identified by key) for reading, increments read level
Definition: StoreMap.cc:440
std::atomic< StoreMapSliceId > next
ID of the next entry slice.
Definition: StoreMap.h:49
struct Ipc::StoreMapAnchor::Basics basics
#define NULL
Definition: types.h:166
const Anchor & readableEntry(const AnchorId anchorId) const
readable anchor for the entry created by openForReading()
Definition: StoreMap.cc:244
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:128
sfileno AnchorId
Definition: StoreMap.h:224
int entryLimit() const
maximum entryCount() possible
Definition: StoreMap.cc:733
uint16_t refcount
Definition: Store.h:223
Edition stale
old anchor and chain
Definition: StoreMap.h:208
#define true
Definition: GnuRegex.c:234
bool openKeyless(Update::Edition &edition)
Definition: StoreMap.cc:587
int sliceLimit() const
maximum number of slices possible
Definition: StoreMap.cc:745
FileNos::Owner * fileNos
Definition: StoreMap.h:237
void setCollapsingRequirement(const bool required)
allow or forbid collapsed requests feeding
Definition: store.cc:2053
bool validateHit(const sfileno)
Definition: StoreMap.cc:801
void closeForReading(const sfileno fileno)
closes open entry after reading, decrements read level
Definition: StoreMap.cc:497
bool markedForDeletion(const cache_key *key) const
Definition: Controller.cc:312
StoreEntry * entry
the store entry being updated
Definition: StoreMap.h:207
void setKey(const cache_key *const aKey)
Definition: StoreMap.cc:945
#define shm_old(Class)
Definition: Pointer.h:201
bool validSlice(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:764
void rewind()
undo the effects of set(), setKey(), etc., but keep locks and state
Definition: StoreMap.cc:997
const SBuf path
cache_dir path or similar cache name; for logging
Definition: StoreMap.h:364
#define assert(EX)
Definition: assert.h:19
bool lockHeaders()
lock for [readable] metadata update or return false
int entryCount() const
number of writeable and readable entries
Definition: StoreMap.cc:739
Aggregates information required for updating entry metadata and headers.
Definition: StoreMap.h:181
std::atomic< uint8_t > waitingToBeFreed
Definition: StoreMap.h:81
StoreMapAnchor * anchor
StoreMap::anchors[fileNo], for convenience/speed.
Definition: StoreMap.h:193
sfileno nameByKey(const cache_key *const key) const
computes entry name (i.e., key hash) for a given entry key
Definition: StoreMap.cc:884
const char * c_str()
Definition: SBuf.cc:523
bool complete() const
Definition: StoreMap.h:77
static hash_table * hash
Definition: text_backend.cc:41
int compareVersions(const sfileno oldFileno, time_t newVersion) const
Definition: StoreMap.cc:68
uint64_t attempts
Definition: StatCounters.h:161
Anchor * openForWriting(const cache_key *const key, sfileno &fileno)
Definition: StoreMap.cc:140
Slice & sliceAt(const SliceId sliceId)
Definition: StoreMap.cc:925
Slices::Owner * slices
Definition: StoreMap.h:239
signed_int32_t sfileno
Definition: forward.h:22
void clear()
restore default-constructed state
Definition: StoreMap.h:46
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
bool freeEntry(const sfileno)
Definition: StoreMap.cc:313
Anchor & anchorByKey(const cache_key *const key)
Definition: StoreMap.cc:919
Clock::time_point lastTime
the time of the last expired() call, initially equals to startTime
Definition: StoreMap.cc:795
std::chrono::high_resolution_clock Clock
Definition: StoreMap.cc:775
During an update, the stored entry has two editions: stale and fresh.
Definition: StoreMap.h:185
ConservativeTimer(const Clock::duration max)
Definition: StoreMap.cc:777
sfileno fileNoByName(const sfileno name) const
computes anchor position for a given entry name
Definition: StoreMap.cc:894
bool hasReadableEntry(const cache_key *const)
whether the index contains a valid readable entry with the given key
Definition: StoreMap.cc:363
void unlockHeaders()
undo successful lockHeaders()
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
void exportInto(StoreEntry &) const
load StoreEntry basics that were previously stored with set()
Definition: StoreMap.cc:979
void AssertFlagIsSet(std::atomic_flag &flag)
StoreMapSliceId splicingPoint
the last slice in the chain still containing metadata/headers
Definition: StoreMap.h:198
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 * peekAtWriter(const sfileno fileno) const
Definition: StoreMap.cc:297
sfileno fileNo
StoreMap::fileNos[name], for convenience/speed.
Definition: StoreMap.h:194
static SBuf StoreMapFileNosId(const SBuf &path)
Definition: StoreMap.cc:36
Anchors::Owner * anchors
Definition: StoreMap.h:238
uint64_t refusalsDueToTimeLimit
Definition: StatCounters.h:164
const Clock::time_point maxTime
after going past this point in time, expired() becomes true
Definition: StoreMap.cc:797
bool purgeOne()
either finds and frees an entry with at least 1 slice or returns false
Definition: StoreMap.cc:702
StoreMapAnchors(const int aCapacity)
Definition: StoreMap.cc:1048
bool markedForDeletion(const cache_key *const)
Definition: StoreMap.cc:355
const Anchor & peekAtEntry(const sfileno fileno) const
Definition: StoreMap.cc:307
#define Must(condition)
Like assert() but throws an exception instead of aborting the process.
Definition: TextException.h:69
uint64_t swap_file_sz
Definition: Store.h:222
void closeForReadingAndFreeIdle(const sfileno fileno)
same as closeForReading() but also frees the entry if it is unlocked
Definition: StoreMap.cc:506
const char * storeKeyText(const cache_key *key)
sfileno name
StoreEntry position in StoreMap::fileNos, for swapping Editions.
Definition: StoreMap.h:195
void abortWriting(const sfileno fileno)
stop writing the entry, freeing its slot for others to use if possible
Definition: StoreMap.cc:251
void lastModified(const time_t when)
Definition: Store.h:168
std::atomic< Size > size
slice contents size
Definition: StoreMap.h:48
bool hittingRequiresCollapsing() const
whether this entry can feed collapsed requests and only them
Definition: Store.h:208
static SBuf StoreMapAnchorsId(const SBuf &path)
Definition: StoreMap.cc:30
bool visitVictims(const NameFilter filter)
Definition: StoreMap.cc:685
Anchor * openForWritingAt(sfileno fileno, bool overwriteExisting=true)
Definition: StoreMap.cc:155
void switchExclusiveToShared()
static SBuf StoreMapSlicesId(const SBuf &path)
Definition: StoreMap.cc:24
void abortUpdating(Update &update)
undoes partial update, unlocks, and cleans up
Definition: StoreMap.cc:269
bool openForUpdating(Update &update, sfileno fileNoHint)
finds and locks the Update entry for an exclusive metadata update
Definition: StoreMap.cc:523
bool reading() const
Definition: StoreMap.h:75
void freeChainAt(SliceId sliceId, const SliceId splicingPoint)
unconditionally frees an already locked chain of slots; no anchor maintenance
Definition: StoreMap.cc:391
struct StatCounters::@139 hitValidation
const A & min(A const &lhs, A const &rhs)
sfileno fileNoByKey(const cache_key *const key) const
computes map entry anchor position for a given entry key
Definition: StoreMap.cc:912
StoreMapSliceId SliceId
Definition: StoreMap.h:227
@ SwapFilenMax
Definition: forward.h:26
aggregates anchor and slice owners for Init() caller convenience
Definition: StoreMap.h:232
void startAppending()
writer keeps its lock but also allows reading
time_t lastref
Definition: Store.h:217
std::function< bool(const sfileno name)> NameFilter
Definition: StoreMap.h:386
void switchWritingToReading(const sfileno fileno)
stop writing (or updating) the locked entry and start reading it
Definition: StoreMap.cc:211
class SquidConfig Config
Definition: SquidConfig.cc:12
StatCounters statCounter
Definition: StatCounters.cc:12
Slice & writeableSlice(const AnchorId anchorId, const SliceId sliceId)
writeable slice within an entry chain created by openForWriting()
Definition: StoreMap.cc:221
Controller & Root()
safely access controller singleton
Definition: Controller.cc:938

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors