src/ipc/StoreMap.cc

   1 /*
   2  * Copyright (C) 1996-2015 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.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 Ipc::StoreMap::Owner *
  31 Ipc::StoreMap::Init(const SBuf &path, const int sliceLimit)
  32 {
  33     assert(sliceLimit > 0); // we should not be created otherwise
  34     const int anchorLimit = min(sliceLimit, static_cast<int>(SwapFilenMax));
  35     Owner *owner = new Owner;
  36     owner->anchors = shm_new(Anchors)(StoreMapAnchorsId(path).c_str(), anchorLimit);
  37     owner->slices = shm_new(Slices)(StoreMapSlicesId(path).c_str(), sliceLimit);
  38     debugs(54, 5, "created " << path << " with " << anchorLimit << '+' << sliceLimit);
  39     return owner;
  40 }
  41
  42 Ipc::StoreMap::StoreMap(const SBuf &aPath): cleaner(NULL), path(aPath),
  43     anchors(shm_old(Anchors)(StoreMapAnchorsId(path).c_str())),
  44     slices(shm_old(Slices)(StoreMapSlicesId(path).c_str()))
  45 {
  46     debugs(54, 5, "attached " << path << " with " <<
  47            anchors->capacity << '+' << slices->capacity);
  48     assert(entryLimit() > 0); // key-to-position mapping requires this
  49     assert(entryLimit() <= sliceLimit()); // at least one slice per entry
  50 }
  51
  52 int
  53 Ipc::StoreMap::compareVersions(const sfileno fileno, time_t newVersion) const
  54 {
  55     const Anchor &inode = anchorAt(fileno);
  56
  57     // note: we do not lock, so comparison may be inacurate
  58
  59     if (inode.empty())
  60         return +2;
  61
  62     if (const time_t diff = newVersion - inode.basics.timestamp)
  63         return diff < 0 ? -1 : +1;
  64
  65     return 0;
  66 }
  67
  68 void
  69 Ipc::StoreMap::forgetWritingEntry(sfileno fileno)
  70 {
  71     Anchor &inode = anchorAt(fileno);
  72
  73     assert(inode.writing());
  74
  75     // we do not iterate slices because we were told to forget about
  76     // them; the caller is responsible for freeing them (most likely
  77     // our slice list is incomplete or has holes)
  78
  79     inode.waitingToBeFreed = false;
  80     inode.rewind();
  81
  82     inode.lock.unlockExclusive();
  83     --anchors->count;
  84
  85     debugs(54, 8, "closed entry " << fileno << " for writing " << path);
  86 }
  87
  88 Ipc::StoreMap::Anchor *
  89 Ipc::StoreMap::openForWriting(const cache_key *const key, sfileno &fileno)
  90 {
  91     debugs(54, 5, "opening entry with key " << storeKeyText(key)
  92            << " for writing " << path);
  93     const int idx = anchorIndexByKey(key);
  94
  95     if (Anchor *anchor = openForWritingAt(idx)) {
  96         fileno = idx;
  97         return anchor;
  98     }
  99
 100     return NULL;
 101 }
 102
 103 Ipc::StoreMap::Anchor *
 104 Ipc::StoreMap::openForWritingAt(const sfileno fileno, bool overwriteExisting)
 105 {
 106     Anchor &s = anchorAt(fileno);
 107     ReadWriteLock &lock = s.lock;
 108
 109     if (lock.lockExclusive()) {
 110         assert(s.writing() && !s.reading());
 111
 112         // bail if we cannot empty this position
 113         if (!s.waitingToBeFreed && !s.empty() && !overwriteExisting) {
 114             lock.unlockExclusive();
 115             debugs(54, 5, "cannot open existing entry " << fileno <<
 116                    " for writing " << path);
 117             return NULL;
 118         }
 119
 120         // free if the entry was used, keeping the entry locked
 121         if (s.waitingToBeFreed || !s.empty())
 122             freeChain(fileno, s, true);
 123
 124         assert(s.empty());
 125         s.start = -1; // we have not allocated any slices yet
 126         ++anchors->count;
 127
 128         //s.setKey(key); // XXX: the caller should do that
 129         debugs(54, 5, "opened entry " << fileno << " for writing " << path);
 130         return &s; // and keep the entry locked
 131     }
 132
 133     debugs(54, 5, "cannot open busy entry " << fileno <<
 134            " for writing " << path);
 135     return NULL;
 136 }
 137
 138 void
 139 Ipc::StoreMap::startAppending(const sfileno fileno)
 140 {
 141     Anchor &s = anchorAt(fileno);
 142     assert(s.writing());
 143     s.lock.startAppending();
 144     debugs(54, 5, "restricted entry " << fileno << " to appending " << path);
 145 }
 146
 147 void
 148 Ipc::StoreMap::closeForWriting(const sfileno fileno, bool lockForReading)
 149 {
 150     Anchor &s = anchorAt(fileno);
 151     assert(s.writing());
 152     if (lockForReading) {
 153         s.lock.switchExclusiveToShared();
 154         debugs(54, 5, "switched entry " << fileno <<
 155                " from writing to reading " << path);
 156         assert(s.complete());
 157     } else {
 158         s.lock.unlockExclusive();
 159         debugs(54, 5, "closed entry " << fileno << " for writing " << path);
 160         // cannot assert completeness here because we have no lock
 161     }
 162 }
 163
 164 Ipc::StoreMap::Slice &
 165 Ipc::StoreMap::writeableSlice(const AnchorId anchorId, const SliceId sliceId)
 166 {
 167     assert(anchorAt(anchorId).writing());
 168     assert(validSlice(sliceId));
 169     return sliceAt(sliceId);
 170 }
 171
 172 const Ipc::StoreMap::Slice &
 173 Ipc::StoreMap::readableSlice(const AnchorId anchorId, const SliceId sliceId) const
 174 {
 175     assert(anchorAt(anchorId).reading());
 176     assert(validSlice(sliceId));
 177     return sliceAt(sliceId);
 178 }
 179
 180 Ipc::StoreMap::Anchor &
 181 Ipc::StoreMap::writeableEntry(const AnchorId anchorId)
 182 {
 183     assert(anchorAt(anchorId).writing());
 184     return anchorAt(anchorId);
 185 }
 186
 187 const Ipc::StoreMap::Anchor &
 188 Ipc::StoreMap::readableEntry(const AnchorId anchorId) const
 189 {
 190     assert(anchorAt(anchorId).reading());
 191     return anchorAt(anchorId);
 192 }
 193
 194 void
 195 Ipc::StoreMap::abortWriting(const sfileno fileno)
 196 {
 197     debugs(54, 5, "aborting entry " << fileno << " for writing " << path);
 198     Anchor &s = anchorAt(fileno);
 199     assert(s.writing());
 200     s.lock.appending = false; // locks out any new readers
 201     if (!s.lock.readers) {
 202         freeChain(fileno, s, false);
 203         debugs(54, 5, "closed clean entry " << fileno << " for writing " << path);
 204     } else {
 205         s.waitingToBeFreed = true;
 206         s.lock.unlockExclusive();
 207         debugs(54, 5, "closed dirty entry " << fileno << " for writing " << path);
 208     }
 209 }
 210
 211 const Ipc::StoreMap::Anchor *
 212 Ipc::StoreMap::peekAtReader(const sfileno fileno) const
 213 {
 214     const Anchor &s = anchorAt(fileno);
 215     if (s.reading())
 216         return &s; // immediate access by lock holder so no locking
 217     if (s.writing())
 218         return NULL; // the caller is not a read lock holder
 219     assert(false); // must be locked for reading or writing
 220     return NULL;
 221 }
 222
 223 const Ipc::StoreMap::Anchor &
 224 Ipc::StoreMap::peekAtEntry(const sfileno fileno) const
 225 {
 226     return anchorAt(fileno);
 227 }
 228
 229 void
 230 Ipc::StoreMap::freeEntry(const sfileno fileno)
 231 {
 232     debugs(54, 5, "marking entry " << fileno << " to be freed in " << path);
 233
 234     Anchor &s = anchorAt(fileno);
 235
 236     if (s.lock.lockExclusive())
 237         freeChain(fileno, s, false);
 238     else
 239         s.waitingToBeFreed = true; // mark to free it later
 240 }
 241
 242 void
 243 Ipc::StoreMap::freeEntryByKey(const cache_key *const key)
 244 {
 245     debugs(54, 5, "marking entry with key " << storeKeyText(key)
 246            << " to be freed in " << path);
 247
 248     const int idx = anchorIndexByKey(key);
 249     Anchor &s = anchorAt(idx);
 250     if (s.lock.lockExclusive()) {
 251         if (s.sameKey(key))
 252             freeChain(idx, s, true);
 253         s.lock.unlockExclusive();
 254     } else if (s.lock.lockShared()) {
 255         if (s.sameKey(key))
 256             s.waitingToBeFreed = true; // mark to free it later
 257         s.lock.unlockShared();
 258     } else {
 259         // we cannot be sure that the entry we found is ours because we do not
 260         // have a lock on it, but we still check to minimize false deletions
 261         if (s.sameKey(key))
 262             s.waitingToBeFreed = true; // mark to free it later
 263     }
 264 }
 265
 266 /// unconditionally frees an already locked chain of slots, unlocking if needed
 267 void
 268 Ipc::StoreMap::freeChain(const sfileno fileno, Anchor &inode, const bool keepLocked)
 269 {
 270     debugs(54, 7, "freeing entry " << fileno <<
 271            " in " << path);
 272     if (!inode.empty()) {
 273         sfileno sliceId = inode.start;
 274         debugs(54, 8, "first slice " << sliceId);
 275         while (sliceId >= 0) {
 276             Slice &slice = sliceAt(sliceId);
 277             const sfileno nextId = slice.next;
 278             slice.size = 0;
 279             slice.next = -1;
 280             if (cleaner)
 281                 cleaner->noteFreeMapSlice(sliceId); // might change slice state
 282             sliceId = nextId;
 283         }
 284     }
 285
 286     inode.waitingToBeFreed = false;
 287     inode.rewind();
 288
 289     if (!keepLocked)
 290         inode.lock.unlockExclusive();
 291     --anchors->count;
 292     debugs(54, 5, "freed entry " << fileno << " in " << path);
 293 }
 294
 295 const Ipc::StoreMap::Anchor *
 296 Ipc::StoreMap::openForReading(const cache_key *const key, sfileno &fileno)
 297 {
 298     debugs(54, 5, "opening entry with key " << storeKeyText(key)
 299            << " for reading " << path);
 300     const int idx = anchorIndexByKey(key);
 301     if (const Anchor *slot = openForReadingAt(idx)) {
 302         if (slot->sameKey(key)) {
 303             fileno = idx;
 304             return slot; // locked for reading
 305         }
 306         slot->lock.unlockShared();
 307         debugs(54, 7, "closed entry " << idx << " for reading " << path);
 308     }
 309     return NULL;
 310 }
 311
 312 const Ipc::StoreMap::Anchor *
 313 Ipc::StoreMap::openForReadingAt(const sfileno fileno)
 314 {
 315     debugs(54, 5, "opening entry " << fileno << " for reading " << path);
 316     Anchor &s = anchorAt(fileno);
 317
 318     if (!s.lock.lockShared()) {
 319         debugs(54, 5, "cannot open busy entry " << fileno <<
 320                " for reading " << path);
 321         return NULL;
 322     }
 323
 324     if (s.empty()) {
 325         s.lock.unlockShared();
 326         debugs(54, 7, "cannot open empty entry " << fileno <<
 327                " for reading " << path);
 328         return NULL;
 329     }
 330
 331     if (s.waitingToBeFreed) {
 332         s.lock.unlockShared();
 333         debugs(54, 7, "cannot open marked entry " << fileno <<
 334                " for reading " << path);
 335         return NULL;
 336     }
 337
 338     debugs(54, 5, "opened entry " << fileno << " for reading " << path);
 339     return &s;
 340 }
 341
 342 void
 343 Ipc::StoreMap::closeForReading(const sfileno fileno)
 344 {
 345     Anchor &s = anchorAt(fileno);
 346     assert(s.reading());
 347     s.lock.unlockShared();
 348     debugs(54, 5, "closed entry " << fileno << " for reading " << path);
 349 }
 350
 351 bool
 352 Ipc::StoreMap::purgeOne()
 353 {
 354     // Hopefully, we find a removable entry much sooner (TODO: use time?).
 355     // The min() will protect us from division by zero inside the loop.
 356     const int searchLimit = min(10000, entryLimit());
 357     int tries = 0;
 358     for (; tries < searchLimit; ++tries) {
 359         const sfileno fileno = static_cast<sfileno>(++anchors->victim % entryLimit());
 360         Anchor &s = anchorAt(fileno);
 361         if (s.lock.lockExclusive()) {
 362             // the caller wants a free slice; empty anchor is not enough
 363             if (!s.empty() && s.start >= 0) {
 364                 // this entry may be marked for deletion, and that is OK
 365                 freeChain(fileno, s, false);
 366                 debugs(54, 5, "purged entry " << fileno << " from " << path);
 367                 return true;
 368             }
 369             s.lock.unlockExclusive();
 370         }
 371     }
 372     debugs(54, 5, "no entries to purge from " << path << "; tried: " << tries);
 373     return false;
 374 }
 375
 376 void
 377 Ipc::StoreMap::importSlice(const SliceId sliceId, const Slice &slice)
 378 {
 379     // Slices are imported into positions that should not be available via
 380     // "get free slice" API. This is not something we can double check
 381     // reliably because the anchor for the imported slice may not have been
 382     // imported yet.
 383     assert(validSlice(sliceId));
 384     sliceAt(sliceId) = slice;
 385 }
 386
 387 int
 388 Ipc::StoreMap::entryLimit() const
 389 {
 390     return min(sliceLimit(), static_cast<int>(SwapFilenMax+1));
 391 }
 392
 393 int
 394 Ipc::StoreMap::entryCount() const
 395 {
 396     return anchors->count;
 397 }
 398
 399 int
 400 Ipc::StoreMap::sliceLimit() const
 401 {
 402     return slices->capacity;
 403 }
 404
 405 void
 406 Ipc::StoreMap::updateStats(ReadWriteLockStats &stats) const
 407 {
 408     for (int i = 0; i < anchors->capacity; ++i)
 409         anchorAt(i).lock.updateStats(stats);
 410 }
 411
 412 bool
 413 Ipc::StoreMap::validEntry(const int pos) const
 414 {
 415     return 0 <= pos && pos < entryLimit();
 416 }
 417
 418 bool
 419 Ipc::StoreMap::validSlice(const int pos) const
 420 {
 421     return 0 <= pos && pos < sliceLimit();
 422 }
 423
 424 Ipc::StoreMap::Anchor&
 425 Ipc::StoreMap::anchorAt(const sfileno fileno)
 426 {
 427     assert(validEntry(fileno));
 428     return anchors->items[fileno];
 429 }
 430
 431 const Ipc::StoreMap::Anchor&
 432 Ipc::StoreMap::anchorAt(const sfileno fileno) const
 433 {
 434     return const_cast<StoreMap&>(*this).anchorAt(fileno);
 435 }
 436
 437 sfileno
 438 Ipc::StoreMap::anchorIndexByKey(const cache_key *const key) const
 439 {
 440     const uint64_t *const k = reinterpret_cast<const uint64_t *>(key);
 441     // TODO: use a better hash function
 442     return (k[0] + k[1]) % entryLimit();
 443 }
 444
 445 Ipc::StoreMap::Anchor &
 446 Ipc::StoreMap::anchorByKey(const cache_key *const key)
 447 {
 448     return anchorAt(anchorIndexByKey(key));
 449 }
 450
 451 Ipc::StoreMap::Slice&
 452 Ipc::StoreMap::sliceAt(const SliceId sliceId)
 453 {
 454     assert(validSlice(sliceId));
 455     return slices->items[sliceId];
 456 }
 457
 458 const Ipc::StoreMap::Slice&
 459 Ipc::StoreMap::sliceAt(const SliceId sliceId) const
 460 {
 461     return const_cast<StoreMap&>(*this).sliceAt(sliceId);
 462 }
 463
 464 /* Ipc::StoreMapAnchor */
 465
 466 Ipc::StoreMapAnchor::StoreMapAnchor(): start(0)
 467 {
 468     memset(&key, 0, sizeof(key));
 469     memset(&basics, 0, sizeof(basics));
 470     // keep in sync with rewind()
 471 }
 472
 473 void
 474 Ipc::StoreMapAnchor::setKey(const cache_key *const aKey)
 475 {
 476     memcpy(key, aKey, sizeof(key));
 477 }
 478
 479 bool
 480 Ipc::StoreMapAnchor::sameKey(const cache_key *const aKey) const
 481 {
 482     const uint64_t *const k = reinterpret_cast<const uint64_t *>(aKey);
 483     return k[0] == key[0] && k[1] == key[1];
 484 }
 485
 486 void
 487 Ipc::StoreMapAnchor::set(const StoreEntry &from)
 488 {
 489     assert(writing() && !reading());
 490     memcpy(key, from.key, sizeof(key));
 491     basics.timestamp = from.timestamp;
 492     basics.lastref = from.lastref;
 493     basics.expires = from.expires;
 494     basics.lastmod = from.lastmod;
 495     basics.swap_file_sz = from.swap_file_sz;
 496     basics.refcount = from.refcount;
 497     basics.flags = from.flags;
 498 }
 499
 500 void
 501 Ipc::StoreMapAnchor::rewind()
 502 {
 503     assert(writing());
 504     start = 0;
 505     memset(&key, 0, sizeof(key));
 506     memset(&basics, 0, sizeof(basics));
 507     // but keep the lock
 508 }
 509
 510 Ipc::StoreMap::Owner::Owner(): anchors(NULL), slices(NULL)
 511 {
 512 }
 513
 514 Ipc::StoreMap::Owner::~Owner()
 515 {
 516     delete anchors;
 517     delete slices;
 518 }
 519
 520 /* Ipc::StoreMapAnchors */
 521
 522 Ipc::StoreMapAnchors::StoreMapAnchors(const int aCapacity):
 523     count(0),
 524     victim(0),
 525     capacity(aCapacity),
 526     items(aCapacity)
 527 {
 528 }
 529
 530 size_t
 531 Ipc::StoreMapAnchors::sharedMemorySize() const
 532 {
 533     return SharedMemorySize(capacity);
 534 }
 535
 536 size_t
 537 Ipc::StoreMapAnchors::SharedMemorySize(const int capacity)
 538 {
 539     return sizeof(StoreMapAnchors) + capacity * sizeof(StoreMapAnchor);
 540 }
 541