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