src/store_digest.cc

   1 /*
   2  * Copyright (C) 1996-2016 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 71    Store Digest Manager */
  10
  11 /*
  12  * TODO: We probably do not track all the cases when
  13  *       storeDigestNoteStoreReady() must be called; this may prevent
  14  *       storeDigestRebuild/write schedule to be activated
  15  */
  16
  17 #include "squid.h"
  18 #include "Debug.h"
  19 #include "event.h"
  20 #include "globals.h"
  21 #include "mgr/Registration.h"
  22 #include "store_digest.h"
  23
  24 #if USE_CACHE_DIGESTS
  25 #include "CacheDigest.h"
  26 #include "HttpReply.h"
  27 #include "HttpRequest.h"
  28 #include "internal.h"
  29 #include "MemObject.h"
  30 #include "PeerDigest.h"
  31 #include "refresh.h"
  32 #include "SquidConfig.h"
  33 #include "SquidTime.h"
  34 #include "Store.h"
  35 #include "StoreSearch.h"
  36 #include "util.h"
  37
  38 #include <cmath>
  39
  40 /*
  41  * local types
  42  */
  43
  44 class StoreDigestState
  45 {
  46
  47 public:
  48     StoreDigestCBlock cblock;
  49     int rebuild_lock;       /* bucket number */
  50     StoreEntry * rewrite_lock;  /* points to store entry with the digest */
  51     StoreSearchPointer theSearch;
  52     int rewrite_offset;
  53     int rebuild_count;
  54     int rewrite_count;
  55 };
  56
  57 typedef struct {
  58     int del_count;      /* #store entries deleted from store_digest */
  59     int del_lost_count;     /* #store entries not found in store_digest on delete */
  60     int add_count;      /* #store entries accepted to store_digest */
  61     int add_coll_count;     /* #accepted entries that collided with existing ones */
  62     int rej_count;      /* #store entries not accepted to store_digest */
  63     int rej_coll_count;     /* #not accepted entries that collided with existing ones */
  64 } StoreDigestStats;
  65
  66 /* local vars */
  67 static StoreDigestState sd_state;
  68 static StoreDigestStats sd_stats;
  69
  70 /* local prototypes */
  71 static void storeDigestRebuildStart(void *datanotused);
  72 static void storeDigestRebuildResume(void);
  73 static void storeDigestRebuildFinish(void);
  74 static void storeDigestRebuildStep(void *datanotused);
  75 static void storeDigestRewriteStart(void *);
  76 static void storeDigestRewriteResume(void);
  77 static void storeDigestRewriteFinish(StoreEntry * e);
  78 static EVH storeDigestSwapOutStep;
  79 static void storeDigestCBlockSwapOut(StoreEntry * e);
  80 static void storeDigestAdd(const StoreEntry *);
  81
  82 /// calculates digest capacity
  83 static uint64_t
  84 storeDigestCalcCap()
  85 {
  86     /*
  87      * To-Do: Bloom proved that the optimal filter utilization is 50% (half of
  88      * the bits are off). However, we do not have a formula to calculate the
  89      * number of _entries_ we want to pre-allocate for.
  90      */
  91     const uint64_t hi_cap = Store::Root().maxSize() / Config.Store.avgObjectSize;
  92     const uint64_t lo_cap = 1 + Store::Root().currentSize() / Config.Store.avgObjectSize;
  93     const uint64_t e_count = StoreEntry::inUseCount();
  94     uint64_t cap = e_count ? e_count : hi_cap;
  95     debugs(71, 2, "have: " << e_count << ", want " << cap <<
  96            " entries; limits: [" << lo_cap << ", " << hi_cap << "]");
  97
  98     if (cap < lo_cap)
  99         cap = lo_cap;
 100
 101     /* do not enforce hi_cap limit, average-based estimation may be wrong
 102      *if (cap > hi_cap)
 103      *  cap = hi_cap;
 104      */
 105
 106     // Bug 4534: we still have to set an upper-limit at some reasonable value though.
 107     // this matches cacheDigestCalcMaskSize doing (cap*bpe)+7 < INT_MAX
 108     const uint64_t absolute_max = (INT_MAX -8) / Config.digest.bits_per_entry;
 109     if (cap > absolute_max) {
 110         debugs(71, DBG_CRITICAL, "WARNING: Cache Digest cannot store " << cap << " entries. Limiting to " << absolute_max);
 111         cap = absolute_max;
 112     }
 113
 114     return cap;
 115 }
 116 #endif /* USE_CACHE_DIGESTS */
 117
 118 void
 119 storeDigestInit(void)
 120 {
 121     Mgr::RegisterAction("store_digest", "Store Digest", storeDigestReport, 0, 1);
 122
 123 #if USE_CACHE_DIGESTS
 124     if (!Config.onoff.digest_generation) {
 125         store_digest = NULL;
 126         debugs(71, 3, "Local cache digest generation disabled");
 127         return;
 128     }
 129
 130     const uint64_t cap = storeDigestCalcCap();
 131     store_digest = new CacheDigest(cap, Config.digest.bits_per_entry);
 132     debugs(71, DBG_IMPORTANT, "Local cache digest enabled; rebuild/rewrite every " <<
 133            (int) Config.digest.rebuild_period << "/" <<
 134            (int) Config.digest.rewrite_period << " sec");
 135
 136     memset(&sd_state, 0, sizeof(sd_state));
 137 #else
 138     store_digest = NULL;
 139     debugs(71, 3, "Local cache digest is 'off'");
 140 #endif
 141 }
 142
 143 /* called when store_rebuild completes */
 144 void
 145 storeDigestNoteStoreReady(void)
 146 {
 147 #if USE_CACHE_DIGESTS
 148
 149     if (Config.onoff.digest_generation) {
 150         storeDigestRebuildStart(NULL);
 151         storeDigestRewriteStart(NULL);
 152     }
 153
 154 #endif
 155 }
 156
 157 //TODO: this seems to be dead code. Is it needed?
 158 void
 159 storeDigestDel(const StoreEntry * entry)
 160 {
 161 #if USE_CACHE_DIGESTS
 162
 163     if (!Config.onoff.digest_generation) {
 164         return;
 165     }
 166
 167     assert(entry && store_digest);
 168     debugs(71, 6, "storeDigestDel: checking entry, key: " << entry->getMD5Text());
 169
 170     if (!EBIT_TEST(entry->flags, KEY_PRIVATE)) {
 171         if (!store_digest->contains(static_cast<const cache_key *>(entry->key))) {
 172             ++sd_stats.del_lost_count;
 173             debugs(71, 6, "storeDigestDel: lost entry, key: " << entry->getMD5Text() << " url: " << entry->url()  );
 174         } else {
 175             ++sd_stats.del_count;
 176             store_digest->remove(static_cast<const cache_key *>(entry->key));
 177             debugs(71, 6, "storeDigestDel: deled entry, key: " << entry->getMD5Text());
 178         }
 179     }
 180 #endif //USE_CACHE_DIGESTS
 181 }
 182
 183 void
 184 storeDigestReport(StoreEntry * e)
 185 {
 186 #if USE_CACHE_DIGESTS
 187
 188     if (!Config.onoff.digest_generation) {
 189         return;
 190     }
 191
 192     if (store_digest) {
 193         cacheDigestReport(store_digest, "store", e);
 194         storeAppendPrintf(e, "\t added: %d rejected: %d ( %.2f %%) del-ed: %d\n",
 195                           sd_stats.add_count,
 196                           sd_stats.rej_count,
 197                           xpercent(sd_stats.rej_count, sd_stats.rej_count + sd_stats.add_count),
 198                           sd_stats.del_count);
 199         storeAppendPrintf(e, "\t collisions: on add: %.2f %% on rej: %.2f %%\n",
 200                           xpercent(sd_stats.add_coll_count, sd_stats.add_count),
 201                           xpercent(sd_stats.rej_coll_count, sd_stats.rej_count));
 202     } else {
 203         storeAppendPrintf(e, "store digest: disabled.\n");
 204     }
 205
 206 #endif //USE_CACHE_DIGESTS
 207 }
 208
 209 /*
 210  * LOCAL FUNCTIONS
 211  */
 212
 213 #if USE_CACHE_DIGESTS
 214
 215 /* should we digest this entry? used by storeDigestAdd() */
 216 static int
 217 storeDigestAddable(const StoreEntry * e)
 218 {
 219     /* add some stats! XXX */
 220
 221     debugs(71, 6, "storeDigestAddable: checking entry, key: " << e->getMD5Text());
 222
 223     /* check various entry flags (mimics StoreEntry::checkCachable XXX) */
 224
 225     if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
 226         debugs(71, 6, "storeDigestAddable: NO: private key");
 227         return 0;
 228     }
 229
 230     if (EBIT_TEST(e->flags, ENTRY_NEGCACHED)) {
 231         debugs(71, 6, "storeDigestAddable: NO: negative cached");
 232         return 0;
 233     }
 234
 235     if (EBIT_TEST(e->flags, RELEASE_REQUEST)) {
 236         debugs(71, 6, "storeDigestAddable: NO: release requested");
 237         return 0;
 238     }
 239
 240     if (e->store_status == STORE_OK && EBIT_TEST(e->flags, ENTRY_BAD_LENGTH)) {
 241         debugs(71, 6, "storeDigestAddable: NO: wrong content-length");
 242         return 0;
 243     }
 244
 245     /* do not digest huge objects */
 246     if (e->swap_file_sz > (uint64_t )Config.Store.maxObjectSize) {
 247         debugs(71, 6, "storeDigestAddable: NO: too big");
 248         return 0;
 249     }
 250
 251     /* still here? check staleness */
 252     /* Note: We should use the time of the next rebuild, not (cur_time+period) */
 253     if (refreshCheckDigest(e, Config.digest.rebuild_period)) {
 254         debugs(71, 6, "storeDigestAdd: entry expires within " << Config.digest.rebuild_period << " secs, ignoring");
 255         return 0;
 256     }
 257
 258     /*
 259      * idea: how about also skipping very fresh (thus, potentially
 260      * unstable) entries? Should be configurable through
 261      * cd_refresh_pattern, of course.
 262      */
 263     /*
 264      * idea: skip objects that are going to be purged before the next
 265      * update.
 266      */
 267     return 1;
 268 }
 269
 270 static void
 271 storeDigestAdd(const StoreEntry * entry)
 272 {
 273     assert(entry && store_digest);
 274
 275     if (storeDigestAddable(entry)) {
 276         ++sd_stats.add_count;
 277
 278         if (store_digest->contains(static_cast<const cache_key *>(entry->key)))
 279             ++sd_stats.add_coll_count;
 280
 281         store_digest->add(static_cast<const cache_key *>(entry->key));
 282
 283         debugs(71, 6, "storeDigestAdd: added entry, key: " << entry->getMD5Text());
 284     } else {
 285         ++sd_stats.rej_count;
 286
 287         if (store_digest->contains(static_cast<const cache_key *>(entry->key)))
 288             ++sd_stats.rej_coll_count;
 289     }
 290 }
 291
 292 /* rebuilds digest from scratch */
 293 static void
 294 storeDigestRebuildStart(void *datanotused)
 295 {
 296     assert(store_digest);
 297     /* prevent overlapping if rebuild schedule is too tight */
 298
 299     if (sd_state.rebuild_lock) {
 300         debugs(71, DBG_IMPORTANT, "storeDigestRebuildStart: overlap detected, consider increasing rebuild period");
 301         return;
 302     }
 303
 304     sd_state.rebuild_lock = 1;
 305     debugs(71, 2, "storeDigestRebuildStart: rebuild #" << sd_state.rebuild_count + 1);
 306
 307     if (sd_state.rewrite_lock) {
 308         debugs(71, 2, "storeDigestRebuildStart: waiting for Rewrite to finish.");
 309         return;
 310     }
 311
 312     storeDigestRebuildResume();
 313 }
 314
 315 /// \returns true if we actually resized the digest
 316 static bool
 317 storeDigestResize()
 318 {
 319     const uint64_t cap = storeDigestCalcCap();
 320     assert(store_digest);
 321     uint64_t diff = abs(cap - store_digest->capacity);
 322     debugs(71, 2, store_digest->capacity << " -> " << cap << "; change: " <<
 323            diff << " (" << xpercentInt(diff, store_digest->capacity) << "%)" );
 324     /* avoid minor adjustments */
 325
 326     if (diff <= store_digest->capacity / 10) {
 327         debugs(71, 2, "small change, will not resize.");
 328         return false;
 329     } else {
 330         debugs(71, 2, "big change, resizing.");
 331         store_digest->updateCapacity(cap);
 332     }
 333     return true;
 334 }
 335
 336 /* called be Rewrite to push Rebuild forward */
 337 static void
 338 storeDigestRebuildResume(void)
 339 {
 340     assert(sd_state.rebuild_lock);
 341     assert(!sd_state.rewrite_lock);
 342     sd_state.theSearch = Store::Root().search();
 343     /* resize or clear */
 344
 345     if (!storeDigestResize())
 346         store_digest->clear();     /* not clean()! */
 347
 348     memset(&sd_stats, 0, sizeof(sd_stats));
 349
 350     eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, NULL, 0.0, 1);
 351 }
 352
 353 /* finishes swap out sequence for the digest; schedules next rebuild */
 354 static void
 355 storeDigestRebuildFinish(void)
 356 {
 357     assert(sd_state.rebuild_lock);
 358     sd_state.rebuild_lock = 0;
 359     ++sd_state.rebuild_count;
 360     debugs(71, 2, "storeDigestRebuildFinish: done.");
 361     eventAdd("storeDigestRebuildStart", storeDigestRebuildStart, NULL, (double)
 362              Config.digest.rebuild_period, 1);
 363     /* resume pending Rewrite if any */
 364
 365     if (sd_state.rewrite_lock)
 366         storeDigestRewriteResume();
 367 }
 368
 369 /* recalculate a few hash buckets per invocation; schedules next step */
 370 static void
 371 storeDigestRebuildStep(void *datanotused)
 372 {
 373     /* TODO: call Store::Root().size() to determine this.. */
 374     int count = Config.Store.objectsPerBucket * (int) ceil((double) store_hash_buckets *
 375                 (double) Config.digest.rebuild_chunk_percentage / 100.0);
 376     assert(sd_state.rebuild_lock);
 377
 378     debugs(71, 3, "storeDigestRebuildStep: buckets: " << store_hash_buckets << " entries to check: " << count);
 379
 380     while (count-- && !sd_state.theSearch->isDone() && sd_state.theSearch->next())
 381         storeDigestAdd(sd_state.theSearch->currentItem());
 382
 383     /* are we done ? */
 384     if (sd_state.theSearch->isDone())
 385         storeDigestRebuildFinish();
 386     else
 387         eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, NULL, 0.0, 1);
 388 }
 389
 390 /* starts swap out sequence for the digest */
 391 static void
 392 storeDigestRewriteStart(void *datanotused)
 393 {
 394     RequestFlags flags;
 395     char *url;
 396     StoreEntry *e;
 397
 398     assert(store_digest);
 399     /* prevent overlapping if rewrite schedule is too tight */
 400
 401     if (sd_state.rewrite_lock) {
 402         debugs(71, DBG_IMPORTANT, "storeDigestRewrite: overlap detected, consider increasing rewrite period");
 403         return;
 404     }
 405
 406     debugs(71, 2, "storeDigestRewrite: start rewrite #" << sd_state.rewrite_count + 1);
 407     /* make new store entry */
 408     url = internalLocalUri("/squid-internal-periodic/", SBuf(StoreDigestFileName));
 409     flags.cachable = true;
 410     e = storeCreateEntry(url, url, flags, Http::METHOD_GET);
 411     assert(e);
 412     sd_state.rewrite_lock = e;
 413     debugs(71, 3, "storeDigestRewrite: url: " << url << " key: " << e->getMD5Text());
 414     HttpRequest *req = HttpRequest::CreateFromUrl(url);
 415     e->mem_obj->request = req;
 416     HTTPMSGLOCK(e->mem_obj->request);
 417     /* wait for rebuild (if any) to finish */
 418
 419     if (sd_state.rebuild_lock) {
 420         debugs(71, 2, "storeDigestRewriteStart: waiting for rebuild to finish.");
 421         return;
 422     }
 423
 424     storeDigestRewriteResume();
 425 }
 426
 427 static void
 428 storeDigestRewriteResume(void)
 429 {
 430     StoreEntry *e;
 431
 432     assert(sd_state.rewrite_lock);
 433     assert(!sd_state.rebuild_lock);
 434     e = sd_state.rewrite_lock;
 435     sd_state.rewrite_offset = 0;
 436     EBIT_SET(e->flags, ENTRY_SPECIAL);
 437     /* setting public key will purge old digest entry if any */
 438     e->setPublicKey();
 439     /* fake reply */
 440     HttpReply *rep = new HttpReply;
 441     rep->setHeaders(Http::scOkay, "Cache Digest OK",
 442                     "application/cache-digest", (store_digest->mask_size + sizeof(sd_state.cblock)),
 443                     squid_curtime, (squid_curtime + Config.digest.rewrite_period) );
 444     debugs(71, 3, "storeDigestRewrite: entry expires on " << rep->expires <<
 445            " (" << std::showpos << (int) (rep->expires - squid_curtime) << ")");
 446     e->buffer();
 447     e->replaceHttpReply(rep);
 448     storeDigestCBlockSwapOut(e);
 449     e->flush();
 450     eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, sd_state.rewrite_lock, 0.0, 1, false);
 451 }
 452
 453 /* finishes swap out sequence for the digest; schedules next rewrite */
 454 static void
 455 storeDigestRewriteFinish(StoreEntry * e)
 456 {
 457     assert(e == sd_state.rewrite_lock);
 458     e->complete();
 459     e->timestampsSet();
 460     debugs(71, 2, "storeDigestRewriteFinish: digest expires at " << e->expires <<
 461            " (" << std::showpos << (int) (e->expires - squid_curtime) << ")");
 462     /* is this the write order? @?@ */
 463     e->mem_obj->unlinkRequest();
 464     e->unlock("storeDigestRewriteFinish");
 465     sd_state.rewrite_lock = NULL;
 466     ++sd_state.rewrite_count;
 467     eventAdd("storeDigestRewriteStart", storeDigestRewriteStart, NULL, (double)
 468              Config.digest.rewrite_period, 1);
 469     /* resume pending Rebuild if any */
 470
 471     if (sd_state.rebuild_lock)
 472         storeDigestRebuildResume();
 473 }
 474
 475 /* swaps out one digest "chunk" per invocation; schedules next swap out */
 476 static void
 477 storeDigestSwapOutStep(void *data)
 478 {
 479     StoreEntry *e = static_cast<StoreEntry *>(data);
 480     int chunk_size = Config.digest.swapout_chunk_size;
 481     assert(e == sd_state.rewrite_lock);
 482     assert(e);
 483     /* _add_ check that nothing bad happened while we were waiting @?@ @?@ */
 484
 485     if (static_cast<uint32_t>(sd_state.rewrite_offset + chunk_size) > store_digest->mask_size)
 486         chunk_size = store_digest->mask_size - sd_state.rewrite_offset;
 487
 488     e->append(store_digest->mask + sd_state.rewrite_offset, chunk_size);
 489
 490     debugs(71, 3, "storeDigestSwapOutStep: size: " << store_digest->mask_size <<
 491            " offset: " << sd_state.rewrite_offset << " chunk: " <<
 492            chunk_size << " bytes");
 493
 494     sd_state.rewrite_offset += chunk_size;
 495
 496     /* are we done ? */
 497     if (static_cast<uint32_t>(sd_state.rewrite_offset) >= store_digest->mask_size)
 498         storeDigestRewriteFinish(e);
 499     else
 500         eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, data, 0.0, 1, false);
 501 }
 502
 503 static void
 504 storeDigestCBlockSwapOut(StoreEntry * e)
 505 {
 506     memset(&sd_state.cblock, 0, sizeof(sd_state.cblock));
 507     sd_state.cblock.ver.current = htons(CacheDigestVer.current);
 508     sd_state.cblock.ver.required = htons(CacheDigestVer.required);
 509     sd_state.cblock.capacity = htonl(store_digest->capacity);
 510     sd_state.cblock.count = htonl(store_digest->count);
 511     sd_state.cblock.del_count = htonl(store_digest->del_count);
 512     sd_state.cblock.mask_size = htonl(store_digest->mask_size);
 513     sd_state.cblock.bits_per_entry = Config.digest.bits_per_entry;
 514     sd_state.cblock.hash_func_count = (unsigned char) CacheDigestHashFuncCount;
 515     e->append((char *) &sd_state.cblock, sizeof(sd_state.cblock));
 516 }
 517
 518 #endif /* USE_CACHE_DIGESTS */
 519