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