src/store_digest.cc

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