StoreMap.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2018 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),
51  fileNos(shm_old(FileNos)(StoreMapFileNosId(path).c_str())),
52  anchors(shm_old(Anchors)(StoreMapAnchorsId(path).c_str())),
53  slices(shm_old(Slices)(StoreMapSlicesId(path).c_str()))
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.size = 0;
350  slice.next = -1;
351  if (cleaner)
352  cleaner->noteFreeMapSlice(sliceId); // might change slice state
353  if (sliceId == splicingPoint) {
354  debugs(54, 5, "preserving chain #" << chainId << " in " << path <<
355  " suffix after slice " << splicingPoint);
356  break; // do not free the rest of the chain
357  }
358  sliceId = nextId;
359  }
360  debugs(54, 7, "freed chain #" << chainId << " in " << path);
361 }
362 
364 Ipc::StoreMap::sliceContaining(const sfileno fileno, const uint64_t bytesNeeded) const
365 {
366  const Anchor &anchor = anchorAt(fileno);
367  Must(anchor.reading());
368  uint64_t bytesSeen = 0;
369  SliceId lastSlice = anchor.start;
370  while (lastSlice >= 0) {
371  const Slice &slice = sliceAt(lastSlice);
372  bytesSeen += slice.size;
373  if (bytesSeen >= bytesNeeded)
374  break;
375  lastSlice = slice.next;
376  }
377  debugs(54, 7, "entry " << fileno << " has " << bytesNeeded << '/' << bytesSeen <<
378  " bytes at slice " << lastSlice << " in " << path);
379  return lastSlice; // may be negative
380 }
381 
382 const Ipc::StoreMap::Anchor *
384 {
385  debugs(54, 5, "opening entry with key " << storeKeyText(key)
386  << " for reading " << path);
387  const int idx = fileNoByKey(key);
388  if (const Anchor *slot = openForReadingAt(idx)) {
389  if (slot->sameKey(key)) {
390  fileno = idx;
391  return slot; // locked for reading
392  }
393  slot->lock.unlockShared();
394  debugs(54, 7, "closed wrong-key entry " << idx << " for reading " << path);
395  }
396  return NULL;
397 }
398 
399 const Ipc::StoreMap::Anchor *
401 {
402  debugs(54, 5, "opening entry " << fileno << " for reading " << path);
403  Anchor &s = anchorAt(fileno);
404 
405  if (!s.lock.lockShared()) {
406  debugs(54, 5, "cannot open busy entry " << fileno <<
407  " for reading " << path);
408  return NULL;
409  }
410 
411  if (s.empty()) {
412  s.lock.unlockShared();
413  debugs(54, 7, "cannot open empty entry " << fileno <<
414  " for reading " << path);
415  return NULL;
416  }
417 
418  if (s.waitingToBeFreed) {
419  s.lock.unlockShared();
420  debugs(54, 7, "cannot open marked entry " << fileno <<
421  " for reading " << path);
422  return NULL;
423  }
424 
425  debugs(54, 5, "opened entry " << fileno << " for reading " << path);
426  return &s;
427 }
428 
429 void
431 {
432  Anchor &s = anchorAt(fileno);
433  assert(s.reading());
434  s.lock.unlockShared();
435  debugs(54, 5, "closed entry " << fileno << " for reading " << path);
436 }
437 
438 bool
440 {
441  Must(update.entry);
442  const StoreEntry &entry = *update.entry;
443  const cache_key *const key = reinterpret_cast<const cache_key*>(entry.key);
444  update.stale.name = nameByKey(key);
445 
446  if (!validEntry(fileNoHint)) {
447  debugs(54, 5, "opening entry with key " << storeKeyText(key) <<
448  " for updating " << path);
449  update.stale.fileNo = fileNoByName(update.stale.name);
450  } else {
451  update.stale.fileNo = fileNoHint;
452  }
453 
454  debugs(54, 5, "opening entry " << update.stale.fileNo << " of " << entry << " for updating " << path);
455 
456  // Unreadable entries cannot (e.g., empty and otherwise problematic entries)
457  // or should not (e.g., entries still forming their metadata) be updated.
458  if (const Anchor *anchor = openForReadingAt(update.stale.fileNo)) {
459  if (!anchor->sameKey(key)) {
460  closeForReading(update.stale.fileNo);
461  debugs(54, 5, "cannot open wrong-key entry " << update.stale.fileNo << " for updating " << path);
462  return false;
463  }
464  } else {
465  debugs(54, 5, "cannot open unreadable entry " << update.stale.fileNo << " for updating " << path);
466  return false;
467  }
468 
469  update.stale.anchor = &anchorAt(update.stale.fileNo);
470  if (update.stale.anchor->writing()) {
471  // TODO: Support updating appending entries.
472  // For example, MemStore::updateHeaders() would not know how
473  // many old prefix body bytes to copy to the new prefix if the last old
474  // prefix slice has not been formed yet (i.e., still gets more bytes).
475  debugs(54, 5, "cannot open appending entry " << update.stale.fileNo <<
476  " for updating " << path);
477  closeForReading(update.stale.fileNo);
478  return false;
479  }
480 
481  if (!update.stale.anchor->lock.lockHeaders()) {
482  debugs(54, 5, "cannot open updating entry " << update.stale.fileNo <<
483  " for updating " << path);
484  closeForReading(update.stale.fileNo);
485  return false;
486  }
487 
488  /* stale anchor is properly locked; we can now use abortUpdating() if needed */
489 
490  if (!openKeyless(update.fresh)) {
491  debugs(54, 5, "cannot open freshchainless entry " << update.stale.fileNo <<
492  " for updating " << path);
493  abortUpdating(update);
494  return false;
495  }
496 
497  Must(update.stale);
498  Must(update.fresh);
499  update.fresh.anchor->set(entry);
500  debugs(54, 5, "opened entry " << update.stale.fileNo << " for updating " << path <<
501  " using entry " << update.fresh.fileNo << " of " << entry);
502 
503  return true;
504 }
505 
508 bool
510 {
511  return visitVictims([&](const sfileno name) {
512  Update::Edition temp;
513  temp.name = name;
514  temp.fileNo = fileNoByName(temp.name);
515  if ((temp.anchor = openForWritingAt(temp.fileNo))) {
516  debugs(54, 5, "created entry " << temp.fileNo <<
517  " for updating " << path);
518  Must(temp);
519  edition = temp;
520  return true;
521  }
522  return false;
523  });
524 }
525 
526 void
528 {
529  Must(update.stale.anchor);
530  Must(update.fresh.anchor);
532  Must(update.stale.splicingPoint >= 0);
533  Must(update.fresh.splicingPoint >= 0);
534 
535  /* the stale prefix cannot overlap with the fresh one (a weak check) */
536  Must(update.stale.anchor->start != update.fresh.anchor->start);
537  Must(update.stale.anchor->start != update.fresh.splicingPoint);
538  Must(update.stale.splicingPoint != update.fresh.anchor->start);
539  Must(update.stale.splicingPoint != update.fresh.splicingPoint);
540 
541  /* the relative order of most operations is significant here */
542 
543  /* splice the fresh chain prefix with the stale chain suffix */
544  Slice &freshSplicingSlice = sliceAt(update.fresh.splicingPoint);
545  const SliceId suffixStart = sliceAt(update.stale.splicingPoint).next; // may be negative
546  // the fresh chain is either properly terminated or already spliced
547  if (freshSplicingSlice.next < 0)
548  freshSplicingSlice.next = suffixStart;
549  else
550  Must(freshSplicingSlice.next == suffixStart);
551  // either way, fresh chain uses the stale chain suffix now
552 
553  // make the fresh anchor/chain readable for everybody
555  // but the fresh anchor is still invisible to anybody but us
556 
557  // This freeEntry() code duplicates the code below to minimize the time when
558  // the freeEntry() race condition (see the Race: comment below) might occur.
559  if (update.stale.anchor->waitingToBeFreed)
560  freeEntry(update.fresh.fileNo);
561 
562  /* any external changes were applied to the stale anchor/chain until now */
563  relocate(update.stale.name, update.fresh.fileNo);
564  /* any external changes will apply to the fresh anchor/chain from now on */
565 
566  // Race: If the stale entry was deleted by some kid during the assignment,
567  // then we propagate that event to the fresh anchor and chain. Since this
568  // update is not atomically combined with the assignment above, another kid
569  // might get a fresh entry just before we have a chance to free it. However,
570  // such deletion races are always possible even without updates.
571  if (update.stale.anchor->waitingToBeFreed)
572  freeEntry(update.fresh.fileNo);
573 
574  /* free the stale chain prefix except for the shared suffix */
575  update.stale.anchor->splicingPoint = update.stale.splicingPoint;
576  freeEntry(update.stale.fileNo);
577 
578  // make the stale anchor/chain reusable, reachable via its new location
579  relocate(update.fresh.name, update.stale.fileNo);
580 
581  const Update updateSaved = update; // for post-close debugging below
582 
583  /* unlock the stale anchor/chain */
584  update.stale.anchor->lock.unlockHeaders();
585  closeForReading(update.stale.fileNo);
586  update.stale = Update::Edition();
587 
588  // finally, unlock the fresh entry
589  closeForReading(update.fresh.fileNo);
590  update.fresh = Update::Edition();
591 
592  debugs(54, 5, "closed entry " << updateSaved.stale.fileNo << " of " << *updateSaved.entry <<
593  " named " << updateSaved.stale.name << " for updating " << path <<
594  " to fresh entry " << updateSaved.fresh.fileNo << " named " << updateSaved.fresh.name <<
595  " with [" << updateSaved.fresh.anchor->start << ',' << updateSaved.fresh.splicingPoint <<
596  "] prefix containing at least " << freshSplicingSlice.size << " bytes");
597 }
598 
603 bool
605 {
606  // Hopefully, we find a usable entry much sooner (TODO: use time?).
607  // The min() will protect us from division by zero inside the loop.
608  const int searchLimit = min(10000, entryLimit());
609  int tries = 0;
610  for (; tries < searchLimit; ++tries) {
611  const sfileno name = static_cast<sfileno>(++anchors->victim % entryLimit());
612  if (visitor(name))
613  return true;
614  }
615 
616  debugs(54, 5, "no victims found in " << path << "; tried: " << tries);
617  return false;
618 }
619 
620 bool
622 {
623  return visitVictims([&](const sfileno name) {
624  const sfileno fileno = fileNoByName(name);
625  Anchor &s = anchorAt(fileno);
626  if (s.lock.lockExclusive()) {
627  // the caller wants a free slice; empty anchor is not enough
628  if (!s.empty() && s.start >= 0) {
629  // this entry may be marked for deletion, and that is OK
630  freeChain(fileno, s, false);
631  debugs(54, 5, "purged entry " << fileno << " from " << path);
632  return true;
633  }
634  s.lock.unlockExclusive();
635  }
636  return false;
637  });
638 }
639 
640 void
641 Ipc::StoreMap::importSlice(const SliceId sliceId, const Slice &slice)
642 {
643  // Slices are imported into positions that should not be available via
644  // "get free slice" API. This is not something we can double check
645  // reliably because the anchor for the imported slice may not have been
646  // imported yet.
647  assert(validSlice(sliceId));
648  sliceAt(sliceId) = slice;
649 }
650 
651 int
653 {
654  return min(sliceLimit(), static_cast<int>(SwapFilenMax+1));
655 }
656 
657 int
659 {
660  return anchors->count;
661 }
662 
663 int
665 {
666  return slices->capacity;
667 }
668 
669 void
671 {
672  for (int i = 0; i < anchors->capacity; ++i)
673  anchorAt(i).lock.updateStats(stats);
674 }
675 
676 bool
677 Ipc::StoreMap::validEntry(const int pos) const
678 {
679  return 0 <= pos && pos < entryLimit();
680 }
681 
682 bool
683 Ipc::StoreMap::validSlice(const int pos) const
684 {
685  return 0 <= pos && pos < sliceLimit();
686 }
687 
690 {
691  assert(validEntry(fileno));
692  return anchors->items[fileno];
693 }
694 
696 Ipc::StoreMap::anchorAt(const sfileno fileno) const
697 {
698  return const_cast<StoreMap&>(*this).anchorAt(fileno);
699 }
700 
701 sfileno
702 Ipc::StoreMap::nameByKey(const cache_key *const key) const
703 {
704  assert(key);
705  const uint64_t *const k = reinterpret_cast<const uint64_t *>(key);
706  // TODO: use a better hash function
707  const int hash = (k[0] + k[1]) % entryLimit();
708  return hash;
709 }
710 
711 sfileno
713 {
714  // fileNos->items are initialized to zero, which we treat as "name is fileno";
715  // a positive value means the entry anchor got moved to a new fileNo
716  if (const int item = fileNos->items[name])
717  return item-1;
718  return name;
719 }
720 
722 void
723 Ipc::StoreMap::relocate(const sfileno name, const sfileno fileno)
724 {
725  // preserve special meaning for zero; see fileNoByName
726  fileNos->items[name] = fileno+1;
727 }
728 
729 sfileno
730 Ipc::StoreMap::fileNoByKey(const cache_key *const key) const
731 {
732  const int name = nameByKey(key);
733  return fileNoByName(name);
734 }
735 
738 {
739  return anchorAt(fileNoByKey(key));
740 }
741 
744 {
745  assert(validSlice(sliceId));
746  return slices->items[sliceId];
747 }
748 
750 Ipc::StoreMap::sliceAt(const SliceId sliceId) const
751 {
752  return const_cast<StoreMap&>(*this).sliceAt(sliceId);
753 }
754 
755 /* Ipc::StoreMapAnchor */
756 
757 Ipc::StoreMapAnchor::StoreMapAnchor(): start(0), splicingPoint(-1)
758 {
759  memset(&key, 0, sizeof(key));
760  memset(&basics, 0, sizeof(basics));
761  // keep in sync with rewind()
762 }
763 
764 void
766 {
767  memcpy(key, aKey, sizeof(key));
768  waitingToBeFreed = Store::Root().markedForDeletion(aKey);
769 }
770 
771 bool
772 Ipc::StoreMapAnchor::sameKey(const cache_key *const aKey) const
773 {
774  const uint64_t *const k = reinterpret_cast<const uint64_t *>(aKey);
775  return k[0] == key[0] && k[1] == key[1];
776 }
777 
778 void
780 {
781  assert(writing() && !reading());
782  setKey(reinterpret_cast<const cache_key*>(aKey ? aKey : from.key));
783  basics.timestamp = from.timestamp;
784  basics.lastref = from.lastref;
785  basics.expires = from.expires;
786  basics.lastmod = from.lastModified();
787  basics.swap_file_sz = from.swap_file_sz;
788  basics.refcount = from.refcount;
789 
790  // do not copy key bit if we are not using from.key
791  // TODO: Replace KEY_PRIVATE with a nil StoreEntry::key!
792  uint16_t cleanFlags = from.flags;
793  if (aKey)
794  EBIT_CLR(cleanFlags, KEY_PRIVATE);
795  basics.flags = cleanFlags;
796 }
797 
798 void
800 {
801  assert(reading());
802  into.timestamp = basics.timestamp;
803  into.lastref = basics.lastref;
804  into.expires = basics.expires;
805  into.lastModified(basics.lastmod);
806  into.swap_file_sz = basics.swap_file_sz;
807  into.refcount = basics.refcount;
808  into.flags = basics.flags;
809 }
810 
811 void
813 {
814  assert(writing());
815  start = 0;
816  splicingPoint = -1;
817  memset(&key, 0, sizeof(key));
818  memset(&basics, 0, sizeof(basics));
819  waitingToBeFreed = false;
820  writerHalted = false;
821  // but keep the lock
822 }
823 
824 /* Ipc::StoreMapUpdate */
825 
827  entry(anEntry)
828 {
829  entry->lock("Ipc::StoreMapUpdate1");
830 }
831 
833  entry(other.entry),
834  stale(other.stale),
835  fresh(other.fresh)
836 {
837  entry->lock("Ipc::StoreMapUpdate2");
838 }
839 
841 {
842  entry->unlock("Ipc::StoreMapUpdate");
843 }
844 
845 /* Ipc::StoreMap::Owner */
846 
848  fileNos(nullptr),
849  anchors(nullptr),
850  slices(nullptr)
851 {
852 }
853 
855 {
856  delete fileNos;
857  delete anchors;
858  delete slices;
859 }
860 
861 /* Ipc::StoreMapAnchors */
862 
864  count(0),
865  victim(0),
866  capacity(aCapacity),
867  items(aCapacity)
868 {
869 }
870 
871 size_t
873 {
874  return SharedMemorySize(capacity);
875 }
876 
877 size_t
879 {
880  return sizeof(StoreMapAnchors) + capacity * sizeof(StoreMapAnchor);
881 }
882 
const Anchor * peekAtReader(const sfileno fileno) const
only works on locked entries; returns nil unless the slice is readable
Definition: StoreMap.cc:245
Mem::Pointer< StoreMapAnchors > anchors
entry inodes (starting blocks)
Definition: StoreMap.h:315
sfileno fileNo
StoreMap::fileNos[name], for convenience/speed.
Definition: StoreMap.h:163
sfileno fileNoByKey(const cache_key *const key) const
computes map entry anchor position for a given entry key
Definition: StoreMap.cc:730
bool validSlice(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:683
const Anchor * openForReadingAt(const sfileno fileno)
opens entry (identified by sfileno) for reading, increments read level
Definition: StoreMap.cc:400
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:641
bool complete() const
Definition: StoreMap.h:74
#define assert(EX)
Definition: assert.h:17
struct Ipc::StoreMapAnchor::Basics basics
Slices::Owner * slices
Definition: StoreMap.h:208
Anchors::Owner * anchors
Definition: StoreMap.h:207
std::atomic< StoreMapSliceId > next
ID of the next entry slice.
Definition: StoreMap.h:46
Aggregates information required for updating entry metadata and headers.
Definition: StoreMap.h:150
void rewind()
undo the effects of set(), setKey(), etc., but keep locks and state
Definition: StoreMap.cc:812
std::atomic< uint8_t > waitingToBeFreed
Definition: StoreMap.h:78
void unlockHeaders()
undo successful lockHeaders()
int entryLimit() const
maximum entryCount() possible
Definition: StoreMap.cc:652
Definition: SBuf.h:86
std::atomic< Size > size
slice contents size
Definition: StoreMap.h:45
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:335
Anchor & anchorByKey(const cache_key *const key)
Definition: StoreMap.cc:737
bool markedForDeletion(const cache_key *const)
Definition: StoreMap.cc:305
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:604
void lastModified(const time_t when)
Definition: Store.h:157
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
StoreMap(const SBuf &aPath)
Definition: StoreMap.cc:50
Slice & sliceAt(const SliceId sliceId)
Definition: StoreMap.cc:743
#define Must(condition)
Like assert() but throws an exception instead of aborting the process.
Definition: TextException.h:69
StoreMapSliceId SliceId
Definition: StoreMap.h:196
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:439
Controller & Root()
safely access controller singleton
Definition: Controller.cc:850
time_t expires
Definition: Store.h:200
bool lockHeaders()
lock for [readable] metadata update or return false
time_t timestamp
Definition: Store.h:198
bool validEntry(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:677
bool sameKey(const cache_key *const aKey) const
Definition: StoreMap.cc:772
void forgetWritingEntry(const sfileno fileno)
Definition: StoreMap.cc:79
uint64_t swap_file_sz
Definition: Store.h:204
sfileno fileNoByName(const sfileno name) const
computes anchor position for a given entry name
Definition: StoreMap.cc:712
#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:509
void switchExclusiveToShared()
stop writing, start reading
static hash_table * hash
Definition: text_backend.cc:41
StoreMapAnchors(const int aCapacity)
Definition: StoreMap.cc:863
#define EBIT_CLR(flag, bit)
Definition: defines.h:106
Slice & writeableSlice(const AnchorId anchorId, const SliceId sliceId)
writeable slice within an entry chain created by openForWriting()
Definition: StoreMap.cc:179
SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const
Definition: StoreMap.cc:364
void updateStats(ReadWriteLockStats &stats) const
adds approximate current stats to the supplied ones
Definition: StoreMap.cc:670
Anchor & writeableEntry(const AnchorId anchorId)
writeable anchor for the entry created by openForWriting()
Definition: StoreMap.cc:195
sfileno nameByKey(const cache_key *const key) const
computes entry name (i.e., key hash) for a given entry key
Definition: StoreMap.cc:702
std::atomic< StoreMapSliceId > splicingPoint
Definition: StoreMap.h:103
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:206
StoreMapAnchor * anchor
StoreMap::anchors[fileNo], for convenience/speed.
Definition: StoreMap.h:162
signed_int32_t sfileno
Definition: forward.h:22
StoreMapUpdate(StoreEntry *anEntry)
Definition: StoreMap.cc:826
bool empty() const
Definition: StoreMap.h:71
size_t sharedMemorySize() const
Definition: StoreMap.cc:872
uint16_t refcount
Definition: Store.h:205
static size_t SharedMemorySize(const int anAnchorLimit)
Definition: StoreMap.cc:878
const Anchor & peekAtEntry(const sfileno fileno) const
only works on locked entries; returns the corresponding Anchor
Definition: StoreMap.cc:257
#define shm_new(Class)
Definition: Pointer.h:179
bool lockExclusive()
lock for modification or return false
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
int sliceLimit() const
maximum number of slices possible
Definition: StoreMap.cc:664
bool writing() const
Definition: StoreMap.h:73
int compareVersions(const sfileno oldFileno, time_t newVersion) const
Definition: StoreMap.cc:63
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
bool markedForDeletion(const cache_key *key) const
Definition: Controller.cc:293
const Anchor * openForReading(const cache_key *const key, sfileno &fileno)
opens entry (identified by key) for reading, increments read level
Definition: StoreMap.cc:383
const Anchor & readableEntry(const AnchorId anchorId) const
readable anchor for the entry created by openForReading()
Definition: StoreMap.cc:202
Edition stale
old anchor and chain being updated
Definition: StoreMap.h:177
Edition fresh
new anchor and updated chain prefix
Definition: StoreMap.h:178
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:80
bool reading() const
Definition: StoreMap.h:72
aggregates anchor and slice owners for Init() caller convenience
Definition: StoreMap.h:201
void exportInto(StoreEntry &) const
load StoreEntry basics that were previously stored with set()
Definition: StoreMap.cc:799
sfileno name
StoreEntry position in StoreMap::fileNos, for swapping Editions.
Definition: StoreMap.h:164
void unlockShared()
undo successful sharedLock()
uint64_t key[2]
StoreEntry key.
Definition: StoreMap.h:85
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:313
Mem::Pointer< StoreMapFileNos > fileNos
entry inodes (starting blocks)
Definition: StoreMap.h:314
void set(const StoreEntry &anEntry, const cache_key *aKey=nullptr)
store StoreEntry key and basics for an inode slot
Definition: StoreMap.cc:779
bool purgeOne()
either finds and frees an entry with at least 1 slice or returns false
Definition: StoreMap.cc:621
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
const Slice & readableSlice(const AnchorId anchorId, const SliceId sliceId) const
readable slice within an entry chain opened by openForReading()
Definition: StoreMap.cc:187
Anchor * openForWritingAt(sfileno fileno, bool overwriteExisting=true)
Definition: StoreMap.cc:113
StoreMapSliceId splicingPoint
the last slice in the chain still containing metadata/headers
Definition: StoreMap.h:167
ReadWriteLock lock
protects slot data below
Definition: StoreMap.h:77
time_t lastref
Definition: Store.h:199
Anchor * openForWriting(const cache_key *const key, sfileno &fileno)
Definition: StoreMap.cc:98
void startAppending()
writer keeps its lock but also allows reading
void closeForReading(const sfileno fileno)
closes open entry after reading, decrements read level
Definition: StoreMap.cc:430
std::atomic< StoreMapSliceId > start
where the chain of StoreEntry slices begins [app]
Definition: StoreMap.h:99
static SBuf StoreMapAnchorsId(const SBuf &path)
Definition: StoreMap.cc:26
int entryCount() const
number of writeable and readable entries
Definition: StoreMap.cc:658
void relocate(const sfileno name, const sfileno fileno)
map name to fileNo
Definition: StoreMap.cc:723
Anchor & anchorAt(const sfileno fileno)
Definition: StoreMap.cc:689
sfileno AnchorId
Definition: StoreMap.h:193
#define NULL
Definition: types.h:166
FileNos::Owner * fileNos
Definition: StoreMap.h:206
A const & min(A const &lhs, A const &rhs)
Mem::Pointer< StoreMapSlices > slices
chained entry pieces positions
Definition: StoreMap.h:316
During an update, the stored entry has two editions: stale and fresh.
Definition: StoreMap.h:154
void closeForUpdating(Update &update)
makes updated info available to others, unlocks, and cleans up
Definition: StoreMap.cc:527
StoreEntry * entry
the store entry being updated
Definition: StoreMap.h:176
void setKey(const cache_key *const aKey)
Definition: StoreMap.cc:765
void lock(const char *context)
Definition: store.cc:435

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors