src/store_digest.cc

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