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

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors