StoreMap.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2019 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 "Store.h"
15 #include "store/Controller.h"
16 #include "store_key_md5.h"
17 #include "tools.h"
18 
19 static SBuf
20 StoreMapSlicesId(const SBuf &path)
21 {
22  return Ipc::Mem::Segment::Name(path, "slices");
23 }
24 
25 static SBuf
26 StoreMapAnchorsId(const SBuf &path)
27 {
28  return Ipc::Mem::Segment::Name(path, "anchors");
29 }
30 
31 static SBuf
32 StoreMapFileNosId(const SBuf &path)
33 {
34  return Ipc::Mem::Segment::Name(path, "filenos");
35 }
36 
38 Ipc::StoreMap::Init(const SBuf &path, const int sliceLimit)
39 {
40  assert(sliceLimit > 0); // we should not be created otherwise
41  const int anchorLimit = min(sliceLimit, static_cast<int>(SwapFilenMax));
42  Owner *owner = new Owner;
43  owner->fileNos = shm_new(FileNos)(StoreMapFileNosId(path).c_str(), anchorLimit);
44  owner->anchors = shm_new(Anchors)(StoreMapAnchorsId(path).c_str(), anchorLimit);
46  debugs(54, 5, "created " << path << " with " << anchorLimit << '+' << sliceLimit);
47  return owner;
48 }
49 
50 Ipc::StoreMap::StoreMap(const SBuf &aPath): cleaner(NULL), path(aPath),
54 {
55  debugs(54, 5, "attached " << path << " with " <<
56  fileNos->capacity << '+' <<
57  anchors->capacity << '+' << slices->capacity);
58  assert(entryLimit() > 0); // key-to-position mapping requires this
59  assert(entryLimit() <= sliceLimit()); // at least one slice per entry
60 }
61 
62 int
63 Ipc::StoreMap::compareVersions(const sfileno fileno, time_t newVersion) const
64 {
65  const Anchor &inode = anchorAt(fileno);
66 
67  // note: we do not lock, so comparison may be inacurate
68 
69  if (inode.empty())
70  return +2;
71 
72  if (const time_t diff = newVersion - inode.basics.timestamp)
73  return diff < 0 ? -1 : +1;
74 
75  return 0;
76 }
77 
78 void
80 {
81  Anchor &inode = anchorAt(fileno);
82 
83  assert(inode.writing());
84 
85  // we do not iterate slices because we were told to forget about
86  // them; the caller is responsible for freeing them (most likely
87  // our slice list is incomplete or has holes)
88 
89  inode.rewind();
90 
91  inode.lock.unlockExclusive();
92  --anchors->count;
93 
94  debugs(54, 8, "closed entry " << fileno << " for writing " << path);
95 }
96 
99 {
100  debugs(54, 5, "opening entry with key " << storeKeyText(key)
101  << " for writing " << path);
102  const int idx = fileNoByKey(key);
103 
104  if (Anchor *anchor = openForWritingAt(idx)) {
105  fileno = idx;
106  return anchor;
107  }
108 
109  return NULL;
110 }
111 
113 Ipc::StoreMap::openForWritingAt(const sfileno fileno, bool overwriteExisting)
114 {
115  Anchor &s = anchorAt(fileno);
116  ReadWriteLock &lock = s.lock;
117 
118  if (lock.lockExclusive()) {
119  assert(s.writing() && !s.reading());
120 
121  // bail if we cannot empty this position
122  if (!s.waitingToBeFreed && !s.empty() && !overwriteExisting) {
123  lock.unlockExclusive();
124  debugs(54, 5, "cannot open existing entry " << fileno <<
125  " for writing " << path);
126  return NULL;
127  }
128 
129  // free if the entry was used, keeping the entry locked
130  if (s.waitingToBeFreed || !s.empty())
131  freeChain(fileno, s, true);
132 
133  assert(s.empty());
134  s.start = -1; // we have not allocated any slices yet
135  s.splicingPoint = -1;
136  ++anchors->count;
137 
138  //s.setKey(key); // XXX: the caller should do that
139  debugs(54, 5, "opened entry " << fileno << " for writing " << path);
140  return &s; // and keep the entry locked
141  }
142 
143  debugs(54, 5, "cannot open busy entry " << fileno <<
144  " for writing " << path);
145  return NULL;
146 }
147 
148 void
150 {
151  Anchor &s = anchorAt(fileno);
152  assert(s.writing());
153  s.lock.startAppending();
154  debugs(54, 5, "restricted entry " << fileno << " to appending " << path);
155 }
156 
157 void
159 {
160  Anchor &s = anchorAt(fileno);
161  assert(s.writing());
162  // TODO: assert(!s.empty()); // i.e., unlocked s becomes s.complete()
163  s.lock.unlockExclusive();
164  debugs(54, 5, "closed entry " << fileno << " for writing " << path);
165  // cannot assert completeness here because we have no lock
166 }
167 
168 void
170 {
171  debugs(54, 5, "switching entry " << fileno << " from writing to reading " << path);
172  Anchor &s = anchorAt(fileno);
173  assert(s.writing());
175  assert(s.complete());
176 }
177 
179 Ipc::StoreMap::writeableSlice(const AnchorId anchorId, const SliceId sliceId)
180 {
181  assert(anchorAt(anchorId).writing());
182  assert(validSlice(sliceId));
183  return sliceAt(sliceId);
184 }
185 
186 const Ipc::StoreMap::Slice &
187 Ipc::StoreMap::readableSlice(const AnchorId anchorId, const SliceId sliceId) const
188 {
189  assert(anchorAt(anchorId).reading());
190  assert(validSlice(sliceId));
191  return sliceAt(sliceId);
192 }
193 
196 {
197  assert(anchorAt(anchorId).writing());
198  return anchorAt(anchorId);
199 }
200 
201 const Ipc::StoreMap::Anchor &
203 {
204  assert(anchorAt(anchorId).reading());
205  return anchorAt(anchorId);
206 }
207 
208 void
210 {
211  debugs(54, 5, "aborting entry " << fileno << " for writing " << path);
212  Anchor &s = anchorAt(fileno);
213  assert(s.writing());
214  s.lock.appending = false; // locks out any new readers
215  if (!s.lock.readers) {
216  freeChain(fileno, s, false);
217  debugs(54, 5, "closed clean entry " << fileno << " for writing " << path);
218  } else {
219  s.waitingToBeFreed = true;
220  s.writerHalted = true;
221  s.lock.unlockExclusive();
222  debugs(54, 5, "closed dirty entry " << fileno << " for writing " << path);
223  }
224 }
225 
226 void
228 {
229  const sfileno fileno = update.stale.fileNo;
230  debugs(54, 5, "aborting entry " << fileno << " for updating " << path);
231  if (update.stale) {
233  update.stale.anchor->lock.unlockHeaders();
234  closeForReading(update.stale.fileNo);
235  update.stale = Update::Edition();
236  }
237  if (update.fresh) {
238  abortWriting(update.fresh.fileNo);
239  update.fresh = Update::Edition();
240  }
241  debugs(54, 5, "aborted entry " << fileno << " for updating " << path);
242 }
243 
244 const Ipc::StoreMap::Anchor *
246 {
247  const Anchor &s = anchorAt(fileno);
248  if (s.reading())
249  return &s; // immediate access by lock holder so no locking
250  if (s.writing())
251  return NULL; // the caller is not a read lock holder
252  assert(false); // must be locked for reading or writing
253  return NULL;
254 }
255 
256 const Ipc::StoreMap::Anchor &
258 {
259  return anchorAt(fileno);
260 }
261 
262 bool
264 {
265  debugs(54, 5, "marking entry " << fileno << " to be freed in " << path);
266 
267  Anchor &s = anchorAt(fileno);
268 
269  if (s.lock.lockExclusive()) {
270  const bool result = !s.waitingToBeFreed && !s.empty();
271  freeChain(fileno, s, false);
272  return result;
273  }
274 
275  uint8_t expected = false;
276  // mark to free the locked entry later (if not already marked)
277  return s.waitingToBeFreed.compare_exchange_strong(expected, true);
278 }
279 
280 void
282 {
283  debugs(54, 5, "marking entry with key " << storeKeyText(key)
284  << " to be freed in " << path);
285 
286  const int idx = fileNoByKey(key);
287  Anchor &s = anchorAt(idx);
288  if (s.lock.lockExclusive()) {
289  if (s.sameKey(key))
290  freeChain(idx, s, true);
291  s.lock.unlockExclusive();
292  } else if (s.lock.lockShared()) {
293  if (s.sameKey(key))
294  s.waitingToBeFreed = true; // mark to free it later
295  s.lock.unlockShared();
296  } else {
297  // we cannot be sure that the entry we found is ours because we do not
298  // have a lock on it, but we still check to minimize false deletions
299  if (s.sameKey(key))
300  s.waitingToBeFreed = true; // mark to free it later
301  }
302 }
303 
304 bool
306 {
307  const int idx = fileNoByKey(key);
308  const Anchor &s = anchorAt(idx);
309  return s.sameKey(key) ? bool(s.waitingToBeFreed) : false;
310 }
311 
312 bool
314 {
315  sfileno index;
316  if (openForReading(reinterpret_cast<const cache_key*>(key), index)) {
317  closeForReading(index);
318  return true;
319  }
320  return false;
321 }
322 
324 void
325 Ipc::StoreMap::freeChain(const sfileno fileno, Anchor &inode, const bool keepLocked)
326 {
327  debugs(54, 7, "freeing entry " << fileno <<
328  " in " << path);
329  if (!inode.empty())
330  freeChainAt(inode.start, inode.splicingPoint);
331  inode.rewind();
332 
333  if (!keepLocked)
334  inode.lock.unlockExclusive();
335  --anchors->count;
336  debugs(54, 5, "freed entry " << fileno << " in " << path);
337 }
338 
340 void
341 Ipc::StoreMap::freeChainAt(SliceId sliceId, const SliceId splicingPoint)
342 {
343  static uint64_t ChainId = 0; // to pair freeing/freed calls in debugs()
344  const uint64_t chainId = ++ChainId;
345  debugs(54, 7, "freeing chain #" << chainId << " starting at " << sliceId << " in " << path);
346  while (sliceId >= 0) {
347  Slice &slice = sliceAt(sliceId);
348  const SliceId nextId = slice.next;
349  slice.clear();
350  if (cleaner)
351  cleaner->noteFreeMapSlice(sliceId); // might change slice state
352  if (sliceId == splicingPoint) {
353  debugs(54, 5, "preserving chain #" << chainId << " in " << path <<
354  " suffix after slice " << splicingPoint);
355  break; // do not free the rest of the chain
356  }
357  sliceId = nextId;
358  }
359  debugs(54, 7, "freed chain #" << chainId << " in " << path);
360 }
361 
362 void
364 {
365  // TODO: Move freeSlots here, along with reserveSlotForWriting() logic.
366  assert(validSlice(sliceId));
367  sliceAt(sliceId).clear();
368 }
369 
371 Ipc::StoreMap::sliceContaining(const sfileno fileno, const uint64_t bytesNeeded) const
372 {
373  const Anchor &anchor = anchorAt(fileno);
374  Must(anchor.reading());
375  uint64_t bytesSeen = 0;
376  SliceId lastSlice = anchor.start;
377  while (lastSlice >= 0) {
378  const Slice &slice = sliceAt(lastSlice);
379  bytesSeen += slice.size;
380  if (bytesSeen >= bytesNeeded)
381  break;
382  lastSlice = slice.next;
383  }
384  debugs(54, 7, "entry " << fileno << " has " << bytesNeeded << '/' << bytesSeen <<
385  " bytes at slice " << lastSlice << " in " << path);
386  return lastSlice; // may be negative
387 }
388 
389 const Ipc::StoreMap::Anchor *
391 {
392  debugs(54, 5, "opening entry with key " << storeKeyText(key)
393  << " for reading " << path);
394  const int idx = fileNoByKey(key);
395  if (const Anchor *slot = openForReadingAt(idx)) {
396  if (slot->sameKey(key)) {
397  fileno = idx;
398  return slot; // locked for reading
399  }
400  slot->lock.unlockShared();
401  debugs(54, 7, "closed wrong-key entry " << idx << " for reading " << path);
402  }
403  return NULL;
404 }
405 
406 const Ipc::StoreMap::Anchor *
408 {
409  debugs(54, 5, "opening entry " << fileno << " for reading " << path);
410  Anchor &s = anchorAt(fileno);
411 
412  if (!s.lock.lockShared()) {
413  debugs(54, 5, "cannot open busy entry " << fileno <<
414  " for reading " << path);
415  return NULL;
416  }
417 
418  if (s.empty()) {
419  s.lock.unlockShared();
420  debugs(54, 7, "cannot open empty entry " << fileno <<
421  " for reading " << path);
422  return NULL;
423  }
424 
425  if (s.waitingToBeFreed) {
426  s.lock.unlockShared();
427  debugs(54, 7, "cannot open marked entry " << fileno <<
428  " for reading " << path);
429  return NULL;
430  }
431 
432  debugs(54, 5, "opened entry " << fileno << " for reading " << path);
433  return &s;
434 }
435 
436 void
438 {
439  Anchor &s = anchorAt(fileno);
440  assert(s.reading());
441  s.lock.unlockShared();
442  debugs(54, 5, "closed entry " << fileno << " for reading " << path);
443 }
444 
445 bool
447 {
448  Must(update.entry);
449  const StoreEntry &entry = *update.entry;
450  const cache_key *const key = reinterpret_cast<const cache_key*>(entry.key);
451  update.stale.name = nameByKey(key);
452 
453  if (!validEntry(fileNoHint)) {
454  debugs(54, 5, "opening entry with key " << storeKeyText(key) <<
455  " for updating " << path);
456  update.stale.fileNo = fileNoByName(update.stale.name);
457  } else {
458  update.stale.fileNo = fileNoHint;
459  }
460 
461  debugs(54, 5, "opening entry " << update.stale.fileNo << " of " << entry << " for updating " << path);
462 
463  // Unreadable entries cannot (e.g., empty and otherwise problematic entries)
464  // or should not (e.g., entries still forming their metadata) be updated.
465  if (const Anchor *anchor = openForReadingAt(update.stale.fileNo)) {
466  if (!anchor->sameKey(key)) {
467  closeForReading(update.stale.fileNo);
468  debugs(54, 5, "cannot open wrong-key entry " << update.stale.fileNo << " for updating " << path);
469  return false;
470  }
471  } else {
472  debugs(54, 5, "cannot open unreadable entry " << update.stale.fileNo << " for updating " << path);
473  return false;
474  }
475 
476  update.stale.anchor = &anchorAt(update.stale.fileNo);
477  if (update.stale.anchor->writing()) {
478  // TODO: Support updating appending entries.
479  // For example, MemStore::updateHeaders() would not know how
480  // many old prefix body bytes to copy to the new prefix if the last old
481  // prefix slice has not been formed yet (i.e., still gets more bytes).
482  debugs(54, 5, "cannot open appending entry " << update.stale.fileNo <<
483  " for updating " << path);
484  closeForReading(update.stale.fileNo);
485  return false;
486  }
487 
488  if (!update.stale.anchor->lock.lockHeaders()) {
489  debugs(54, 5, "cannot open updating entry " << update.stale.fileNo <<
490  " for updating " << path);
491  closeForReading(update.stale.fileNo);
492  return false;
493  }
494 
495  /* stale anchor is properly locked; we can now use abortUpdating() if needed */
496 
497  if (!openKeyless(update.fresh)) {
498  debugs(54, 5, "cannot open freshchainless entry " << update.stale.fileNo <<
499  " for updating " << path);
500  abortUpdating(update);
501  return false;
502  }
503 
504  Must(update.stale);
505  Must(update.fresh);
506  update.fresh.anchor->set(entry);
507  debugs(54, 5, "opened entry " << update.stale.fileNo << " for updating " << path <<
508  " using entry " << update.fresh.fileNo << " of " << entry);
509 
510  return true;
511 }
512 
515 bool
517 {
518  return visitVictims([&](const sfileno name) {
519  Update::Edition temp;
520  temp.name = name;
521  temp.fileNo = fileNoByName(temp.name);
522  if ((temp.anchor = openForWritingAt(temp.fileNo))) {
523  debugs(54, 5, "created entry " << temp.fileNo <<
524  " for updating " << path);
525  Must(temp);
526  edition = temp;
527  return true;
528  }
529  return false;
530  });
531 }
532 
533 void
535 {
536  Must(update.stale.anchor);
537  Must(update.fresh.anchor);
539  Must(update.stale.splicingPoint >= 0);
540  Must(update.fresh.splicingPoint >= 0);
541 
542  /* the stale prefix cannot overlap with the fresh one (a weak check) */
543  Must(update.stale.anchor->start != update.fresh.anchor->start);
544  Must(update.stale.anchor->start != update.fresh.splicingPoint);
545  Must(update.stale.splicingPoint != update.fresh.anchor->start);
546  Must(update.stale.splicingPoint != update.fresh.splicingPoint);
547 
548  /* the relative order of most operations is significant here */
549 
550  /* splice the fresh chain prefix with the stale chain suffix */
551  Slice &freshSplicingSlice = sliceAt(update.fresh.splicingPoint);
552  const SliceId suffixStart = sliceAt(update.stale.splicingPoint).next; // may be negative
553  // the fresh chain is either properly terminated or already spliced
554  if (freshSplicingSlice.next < 0)
555  freshSplicingSlice.next = suffixStart;
556  else
557  Must(freshSplicingSlice.next == suffixStart);
558  // either way, fresh chain uses the stale chain suffix now
559 
560  // make the fresh anchor/chain readable for everybody
562  // but the fresh anchor is still invisible to anybody but us
563 
564  // This freeEntry() code duplicates the code below to minimize the time when
565  // the freeEntry() race condition (see the Race: comment below) might occur.
566  if (update.stale.anchor->waitingToBeFreed)
567  freeEntry(update.fresh.fileNo);
568 
569  /* any external changes were applied to the stale anchor/chain until now */
570  relocate(update.stale.name, update.fresh.fileNo);
571  /* any external changes will apply to the fresh anchor/chain from now on */
572 
573  // Race: If the stale entry was deleted by some kid during the assignment,
574  // then we propagate that event to the fresh anchor and chain. Since this
575  // update is not atomically combined with the assignment above, another kid
576  // might get a fresh entry just before we have a chance to free it. However,
577  // such deletion races are always possible even without updates.
578  if (update.stale.anchor->waitingToBeFreed)
579  freeEntry(update.fresh.fileNo);
580 
581  /* free the stale chain prefix except for the shared suffix */
582  update.stale.anchor->splicingPoint = update.stale.splicingPoint;
583  freeEntry(update.stale.fileNo);
584 
585  // make the stale anchor/chain reusable, reachable via its new location
586  relocate(update.fresh.name, update.stale.fileNo);
587 
588  const Update updateSaved = update; // for post-close debugging below
589 
590  /* unlock the stale anchor/chain */
591  update.stale.anchor->lock.unlockHeaders();
592  closeForReading(update.stale.fileNo);
593  update.stale = Update::Edition();
594 
595  // finally, unlock the fresh entry
596  closeForReading(update.fresh.fileNo);
597  update.fresh = Update::Edition();
598 
599  debugs(54, 5, "closed entry " << updateSaved.stale.fileNo << " of " << *updateSaved.entry <<
600  " named " << updateSaved.stale.name << " for updating " << path <<
601  " to fresh entry " << updateSaved.fresh.fileNo << " named " << updateSaved.fresh.name <<
602  " with [" << updateSaved.fresh.anchor->start << ',' << updateSaved.fresh.splicingPoint <<
603  "] prefix containing at least " << freshSplicingSlice.size << " bytes");
604 }
605 
610 bool
612 {
613  // Hopefully, we find a usable entry much sooner (TODO: use time?).
614  // The min() will protect us from division by zero inside the loop.
615  const int searchLimit = min(10000, entryLimit());
616  int tries = 0;
617  for (; tries < searchLimit; ++tries) {
618  const sfileno name = static_cast<sfileno>(++anchors->victim % entryLimit());
619  if (visitor(name))
620  return true;
621  }
622 
623  debugs(54, 5, "no victims found in " << path << "; tried: " << tries);
624  return false;
625 }
626 
627 bool
629 {
630  return visitVictims([&](const sfileno name) {
631  const sfileno fileno = fileNoByName(name);
632  Anchor &s = anchorAt(fileno);
633  if (s.lock.lockExclusive()) {
634  // the caller wants a free slice; empty anchor is not enough
635  if (!s.empty() && s.start >= 0) {
636  // this entry may be marked for deletion, and that is OK
637  freeChain(fileno, s, false);
638  debugs(54, 5, "purged entry " << fileno << " from " << path);
639  return true;
640  }
641  s.lock.unlockExclusive();
642  }
643  return false;
644  });
645 }
646 
647 void
648 Ipc::StoreMap::importSlice(const SliceId sliceId, const Slice &slice)
649 {
650  // Slices are imported into positions that should not be available via
651  // "get free slice" API. This is not something we can double check
652  // reliably because the anchor for the imported slice may not have been
653  // imported yet.
654  assert(validSlice(sliceId));
655  sliceAt(sliceId) = slice;
656 }
657 
658 int
660 {
661  return min(sliceLimit(), static_cast<int>(SwapFilenMax+1));
662 }
663 
664 int
666 {
667  return anchors->count;
668 }
669 
670 int
672 {
673  return slices->capacity;
674 }
675 
676 void
678 {
679  for (int i = 0; i < anchors->capacity; ++i)
680  anchorAt(i).lock.updateStats(stats);
681 }
682 
683 bool
684 Ipc::StoreMap::validEntry(const int pos) const
685 {
686  return 0 <= pos && pos < entryLimit();
687 }
688 
689 bool
690 Ipc::StoreMap::validSlice(const int pos) const
691 {
692  return 0 <= pos && pos < sliceLimit();
693 }
694 
697 {
698  assert(validEntry(fileno));
699  return anchors->items[fileno];
700 }
701 
703 Ipc::StoreMap::anchorAt(const sfileno fileno) const
704 {
705  return const_cast<StoreMap&>(*this).anchorAt(fileno);
706 }
707 
708 sfileno
709 Ipc::StoreMap::nameByKey(const cache_key *const key) const
710 {
711  assert(key);
712  const uint64_t *const k = reinterpret_cast<const uint64_t *>(key);
713  // TODO: use a better hash function
714  const int hash = (k[0] + k[1]) % entryLimit();
715  return hash;
716 }
717 
718 sfileno
720 {
721  // fileNos->items are initialized to zero, which we treat as "name is fileno";
722  // a positive value means the entry anchor got moved to a new fileNo
723  if (const int item = fileNos->items[name])
724  return item-1;
725  return name;
726 }
727 
729 void
730 Ipc::StoreMap::relocate(const sfileno name, const sfileno fileno)
731 {
732  // preserve special meaning for zero; see fileNoByName
733  fileNos->items[name] = fileno+1;
734 }
735 
736 sfileno
737 Ipc::StoreMap::fileNoByKey(const cache_key *const key) const
738 {
739  const int name = nameByKey(key);
740  return fileNoByName(name);
741 }
742 
745 {
746  return anchorAt(fileNoByKey(key));
747 }
748 
751 {
752  assert(validSlice(sliceId));
753  return slices->items[sliceId];
754 }
755 
757 Ipc::StoreMap::sliceAt(const SliceId sliceId) const
758 {
759  return const_cast<StoreMap&>(*this).sliceAt(sliceId);
760 }
761 
762 /* Ipc::StoreMapAnchor */
763 
764 Ipc::StoreMapAnchor::StoreMapAnchor(): start(0), splicingPoint(-1)
765 {
766  // keep in sync with rewind()
767 }
768 
769 void
771 {
772  memcpy(key, aKey, sizeof(key));
774 }
775 
776 bool
777 Ipc::StoreMapAnchor::sameKey(const cache_key *const aKey) const
778 {
779  const uint64_t *const k = reinterpret_cast<const uint64_t *>(aKey);
780  return k[0] == key[0] && k[1] == key[1];
781 }
782 
783 void
785 {
786  assert(writing() && !reading());
787  setKey(reinterpret_cast<const cache_key*>(aKey ? aKey : from.key));
788  basics.timestamp = from.timestamp;
789  basics.lastref = from.lastref;
790  basics.expires = from.expires;
791  basics.lastmod = from.lastModified();
793  basics.refcount = from.refcount;
794 
795  // do not copy key bit if we are not using from.key
796  // TODO: Replace KEY_PRIVATE with a nil StoreEntry::key!
797  uint16_t cleanFlags = from.flags;
798  if (aKey)
799  EBIT_CLR(cleanFlags, KEY_PRIVATE);
800  basics.flags = cleanFlags;
801 }
802 
803 void
805 {
806  assert(reading());
807  into.timestamp = basics.timestamp;
808  into.lastref = basics.lastref;
809  into.expires = basics.expires;
812  into.refcount = basics.refcount;
813  const bool collapsingRequired = into.hittingRequiresCollapsing();
814  into.flags = basics.flags;
815  // There are possibly several flags we do not need to overwrite,
816  // and ENTRY_REQUIRES_COLLAPSING is one of them.
817  // TODO: check for other flags.
818  into.setCollapsingRequirement(collapsingRequired);
819 }
820 
821 void
823 {
824  assert(writing());
825  start = 0;
826  splicingPoint = -1;
827  memset(&key, 0, sizeof(key));
828  basics.clear();
829  waitingToBeFreed = false;
830  writerHalted = false;
831  // but keep the lock
832 }
833 
834 /* Ipc::StoreMapUpdate */
835 
837  entry(anEntry)
838 {
839  entry->lock("Ipc::StoreMapUpdate1");
840 }
841 
843  entry(other.entry),
844  stale(other.stale),
845  fresh(other.fresh)
846 {
847  entry->lock("Ipc::StoreMapUpdate2");
848 }
849 
851 {
852  entry->unlock("Ipc::StoreMapUpdate");
853 }
854 
855 /* Ipc::StoreMap::Owner */
856 
858  fileNos(nullptr),
859  anchors(nullptr),
860  slices(nullptr)
861 {
862 }
863 
865 {
866  delete fileNos;
867  delete anchors;
868  delete slices;
869 }
870 
871 /* Ipc::StoreMapAnchors */
872 
874  count(0),
875  victim(0),
876  capacity(aCapacity),
877  items(aCapacity)
878 {
879 }
880 
881 size_t
883 {
884  return SharedMemorySize(capacity);
885 }
886 
887 size_t
889 {
890  return sizeof(StoreMapAnchors) + capacity * sizeof(StoreMapAnchor);
891 }
892 
bool validEntry(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:684
virtual void noteFreeMapSlice(const StoreMapSliceId sliceId)=0
adjust slice-linked state before a locked Readable slice is erased
Mem::Pointer< StoreMapAnchors > anchors
entry inodes (starting blocks)
Definition: StoreMap.h:330
sfileno fileNo
StoreMap::fileNos[name], for convenience/speed.
Definition: StoreMap.h:175
const Anchor * openForReadingAt(const sfileno fileno)
opens entry (identified by sfileno) for reading, increments read level
Definition: StoreMap.cc:407
std::atomic< uint64_t > swap_file_sz
Definition: StoreMap.h:105
bool freeEntry(const sfileno)
Definition: StoreMap.cc:263
void importSlice(const SliceId sliceId, const Slice &slice)
copies slice to its designated position
Definition: StoreMap.cc:648
#define assert(EX)
Definition: assert.h:17
bool sameKey(const cache_key *const aKey) const
Definition: StoreMap.cc:777
struct Ipc::StoreMapAnchor::Basics basics
Slices::Owner * slices
Definition: StoreMap.h:220
Anchors::Owner * anchors
Definition: StoreMap.h:219
std::atomic< StoreMapSliceId > next
ID of the next entry slice.
Definition: StoreMap.h:49
Aggregates information required for updating entry metadata and headers.
Definition: StoreMap.h:162
void rewind()
undo the effects of set(), setKey(), etc., but keep locks and state
Definition: StoreMap.cc:822
int unlock(const char *context)
Definition: store.cc:463
std::atomic< uint8_t > waitingToBeFreed
Definition: StoreMap.h:81
void unlockHeaders()
undo successful lockHeaders()
Definition: SBuf.h:86
std::atomic< Size > size
slice contents size
Definition: StoreMap.h:48
unsigned char cache_key
Store key.
Definition: forward.h:29
#define shm_old(Class)
Definition: Pointer.h:180
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
std::function< bool(const sfileno name)> NameFilter
Definition: StoreMap.h:350
Anchor & anchorByKey(const cache_key *const key)
Definition: StoreMap.cc:744
bool markedForDeletion(const cache_key *const)
Definition: StoreMap.cc:305
const Anchor & peekAtEntry(const sfileno fileno) const
only works on locked entries; returns the corresponding Anchor
Definition: StoreMap.cc:257
void freeEntryByKey(const cache_key *const key)
Definition: StoreMap.cc:281
int i
Definition: membanger.c:49
void switchWritingToReading(const sfileno fileno)
stop writing (or updating) the locked entry and start reading it
Definition: StoreMap.cc:169
bool visitVictims(const NameFilter filter)
Definition: StoreMap.cc:611
int entryCount() const
number of writeable and readable entries
Definition: StoreMap.cc:665
void lastModified(const time_t when)
Definition: Store.h:159
const char * storeKeyText(const cache_key *key)
void abortUpdating(Update &update)
undoes partial update, unlocks, and cleans up
Definition: StoreMap.cc:227
class Ping::pingStats_ stats
bool reading() const
Definition: StoreMap.h:75
StoreMap(const SBuf &aPath)
Definition: StoreMap.cc:50
Slice & sliceAt(const SliceId sliceId)
Definition: StoreMap.cc:750
#define Must(condition)
Like assert() but throws an exception instead of aborting the process.
Definition: TextException.h:69
StoreMapCleaner * cleaner
notified before a readable entry is freed
Definition: StoreMap.h:325
StoreMapSliceId SliceId
Definition: StoreMap.h:208
approximate stats of a set of ReadWriteLocks
Definition: ReadWriteLock.h:56
void closeForWriting(const sfileno fileno)
successfully finish creating or updating the entry at fileno pos
Definition: StoreMap.cc:158
static Owner * Init(const SBuf &path, const int slotLimit)
initialize shared memory
Definition: StoreMap.cc:38
bool openForUpdating(Update &update, sfileno fileNoHint)
finds and locks the Update entry for an exclusive metadata update
Definition: StoreMap.cc:446
Controller & Root()
safely access controller singleton
Definition: Controller.cc:877
time_t expires
Definition: Store.h:204
bool lockHeaders()
lock for [readable] metadata update or return false
time_t timestamp
Definition: Store.h:202
bool empty() const
Definition: StoreMap.h:74
bool complete() const
Definition: StoreMap.h:77
void forgetWritingEntry(const sfileno fileno)
Definition: StoreMap.cc:79
uint64_t swap_file_sz
Definition: Store.h:208
int entryLimit() const
maximum entryCount() possible
Definition: StoreMap.cc:659
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:124
void startAppending(const sfileno fileno)
restrict opened for writing entry to appending operations; allow reads
Definition: StoreMap.cc:149
bool openKeyless(Update::Edition &edition)
Definition: StoreMap.cc:516
void switchExclusiveToShared()
stop writing, start reading
static hash_table * hash
Definition: text_backend.cc:41
StoreMapAnchors(const int aCapacity)
Definition: StoreMap.cc:873
#define EBIT_CLR(flag, bit)
Definition: defines.h:106
bool markedForDeletion(const cache_key *key) const
Definition: Controller.cc:303
size_t sharedMemorySize() const
Definition: StoreMap.cc:882
const Anchor & readableEntry(const AnchorId anchorId) const
readable anchor for the entry created by openForReading()
Definition: StoreMap.cc:202
Slice & writeableSlice(const AnchorId anchorId, const SliceId sliceId)
writeable slice within an entry chain created by openForWriting()
Definition: StoreMap.cc:179
Anchor & writeableEntry(const AnchorId anchorId)
writeable anchor for the entry created by openForWriting()
Definition: StoreMap.cc:195
std::atomic< StoreMapSliceId > splicingPoint
Definition: StoreMap.h:115
void clear()
restore default-constructed state
Definition: StoreMap.h:46
const int capacity
total number of anchors
Definition: StoreMap.h:153
const char * c_str()
Definition: SBuf.cc:526
void abortWriting(const sfileno fileno)
stop writing the entry, freeing its slot for others to use if possible
Definition: StoreMap.cc:209
uint16_t flags
Definition: Store.h:210
StoreMapAnchor * anchor
StoreMap::anchors[fileNo], for convenience/speed.
Definition: StoreMap.h:174
bool hittingRequiresCollapsing() const
whether this entry can feed collapsed requests and only them
Definition: Store.h:194
signed_int32_t sfileno
Definition: forward.h:22
SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const
Definition: StoreMap.cc:371
StoreMapUpdate(StoreEntry *anEntry)
Definition: StoreMap.cc:836
void prepFreeSlice(const SliceId sliceId)
prepare a chain-unaffiliated slice for being added to an entry chain
Definition: StoreMap.cc:363
uint16_t refcount
Definition: Store.h:209
static size_t SharedMemorySize(const int anAnchorLimit)
Definition: StoreMap.cc:888
#define shm_new(Class)
Definition: Pointer.h:179
bool lockExclusive()
lock for modification or return false
void setCollapsingRequirement(const bool required)
allow or forbid collapsed requests feeding
Definition: store.cc:2087
void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock)
unconditionally frees an already locked chain of slots, unlocking if needed
Definition: StoreMap.cc:325
static SBuf StoreMapFileNosId(const SBuf &path)
Definition: StoreMap.cc:32
bool writing() const
Definition: StoreMap.h:76
void unlockExclusive()
undo successful exclusiveLock()
void freeChainAt(SliceId sliceId, const SliceId splicingPoint)
unconditionally frees an already locked chain of slots; no anchor maintenance
Definition: StoreMap.cc:341
bool lockShared()
lock for reading or return false
const Anchor * openForReading(const cache_key *const key, sfileno &fileno)
opens entry (identified by key) for reading, increments read level
Definition: StoreMap.cc:390
void updateStats(ReadWriteLockStats &stats) const
adds approximate current stats to the supplied ones
Definition: StoreMap.cc:677
Edition stale
old anchor and chain being updated
Definition: StoreMap.h:189
void updateStats(ReadWriteLockStats &stats) const
adds approximate current stats to the supplied ones
const Anchor * peekAtReader(const sfileno fileno) const
only works on locked entries; returns nil unless the slice is readable
Definition: StoreMap.cc:245
sfileno fileNoByName(const sfileno name) const
computes anchor position for a given entry name
Definition: StoreMap.cc:719
Edition fresh
new anchor and updated chain prefix
Definition: StoreMap.h:190
void AssertFlagIsSet(std::atomic_flag &flag)
std::atomic< bool > appending
the writer has promised to only append
Definition: ReadWriteLock.h:47
std::atomic< uint8_t > writerHalted
whether StoreMap::abortWriting() was called for a read-locked entry
Definition: StoreMap.h:83
aggregates anchor and slice owners for Init() caller convenience
Definition: StoreMap.h:213
sfileno name
StoreEntry position in StoreMap::fileNos, for swapping Editions.
Definition: StoreMap.h:176
int compareVersions(const sfileno oldFileno, time_t newVersion) const
Definition: StoreMap.cc:63
void unlockShared()
undo successful sharedLock()
uint64_t key[2]
StoreEntry key.
Definition: StoreMap.h:88
sfileno fileNoByKey(const cache_key *const key) const
computes map entry anchor position for a given entry key
Definition: StoreMap.cc:737
std::atomic_flag updating
a reader is updating metadata/headers
Definition: ReadWriteLock.h:48
const SBuf path
cache_dir path or similar cache name; for logging
Definition: StoreMap.h:328
Mem::Pointer< StoreMapFileNos > fileNos
entry inodes (starting blocks)
Definition: StoreMap.h:329
void set(const StoreEntry &anEntry, const cache_key *aKey=nullptr)
store StoreEntry key and basics for an inode slot
Definition: StoreMap.cc:784
bool validSlice(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:690
bool purgeOne()
either finds and frees an entry with at least 1 slice or returns false
Definition: StoreMap.cc:628
std::atomic< uint32_t > readers
number of reading users
Definition: ReadWriteLock.h:45
static SBuf StoreMapSlicesId(const SBuf &path)
Definition: StoreMap.cc:20
bool hasReadableEntry(const cache_key *const)
whether the index contains a valid readable entry with the given key
Definition: StoreMap.cc:313
Anchor * openForWritingAt(sfileno fileno, bool overwriteExisting=true)
Definition: StoreMap.cc:113
int sliceLimit() const
maximum number of slices possible
Definition: StoreMap.cc:671
StoreMapSliceId splicingPoint
the last slice in the chain still containing metadata/headers
Definition: StoreMap.h:179
ReadWriteLock lock
protects slot data below
Definition: StoreMap.h:80
time_t lastref
Definition: Store.h:203
Anchor * openForWriting(const cache_key *const key, sfileno &fileno)
Definition: StoreMap.cc:98
void startAppending()
writer keeps its lock but also allows reading
sfileno nameByKey(const cache_key *const key) const
computes entry name (i.e., key hash) for a given entry key
Definition: StoreMap.cc:709
void closeForReading(const sfileno fileno)
closes open entry after reading, decrements read level
Definition: StoreMap.cc:437
const Slice & readableSlice(const AnchorId anchorId, const SliceId sliceId) const
readable slice within an entry chain opened by openForReading()
Definition: StoreMap.cc:187
std::atomic< StoreMapSliceId > start
where the chain of StoreEntry slices begins [app]
Definition: StoreMap.h:111
static SBuf StoreMapAnchorsId(const SBuf &path)
Definition: StoreMap.cc:26
void relocate(const sfileno name, const sfileno fileno)
map name to fileNo
Definition: StoreMap.cc:730
Anchor & anchorAt(const sfileno fileno)
Definition: StoreMap.cc:696
sfileno AnchorId
Definition: StoreMap.h:205
#define NULL
Definition: types.h:166
void exportInto(StoreEntry &) const
load StoreEntry basics that were previously stored with set()
Definition: StoreMap.cc:804
FileNos::Owner * fileNos
Definition: StoreMap.h:218
A const & min(A const &lhs, A const &rhs)
Mem::Pointer< StoreMapSlices > slices
chained entry pieces positions
Definition: StoreMap.h:331
During an update, the stored entry has two editions: stale and fresh.
Definition: StoreMap.h:166
void closeForUpdating(Update &update)
makes updated info available to others, unlocks, and cleans up
Definition: StoreMap.cc:534
StoreEntry * entry
the store entry being updated
Definition: StoreMap.h:188
void setKey(const cache_key *const aKey)
Definition: StoreMap.cc:770
void lock(const char *context)
Definition: store.cc:439

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors