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