src/store_digest.cc

   1 /*
   2  * $Id: store_digest.cc,v 1.31 1998/11/12 06:28:28 wessels Exp $
   3  *
   4  * DEBUG: section 71    Store Digest Manager
   5  * AUTHOR: Alex Rousskov
   6  *
   7  * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
   8  * ----------------------------------------------------------
   9  *
  10  *  Squid is the result of efforts by numerous individuals from the
  11  *  Internet community.  Development is led by Duane Wessels of the
  12  *  National Laboratory for Applied Network Research and funded by the
  13  *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
  14  *  Duane Wessels and the University of California San Diego.  Please
  15  *  see the COPYRIGHT file for full details.  Squid incorporates
  16  *  software developed and/or copyrighted by other sources.  Please see
  17  *  the CREDITS file for full details.
  18  *
  19  *  This program is free software; you can redistribute it and/or modify
  20  *  it under the terms of the GNU General Public License as published by
  21  *  the Free Software Foundation; either version 2 of the License, or
  22  *  (at your option) any later version.
  23  *
  24  *  This program is distributed in the hope that it will be useful,
  25  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  26  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  27  *  GNU General Public License for more details.
  28  *
  29  *  You should have received a copy of the GNU General Public License
  30  *  along with this program; if not, write to the Free Software
  31  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  32  *
  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
  44 #if USE_CACHE_DIGESTS
  45
  46 /*
  47  * local types
  48  */
  49
  50 typedef struct {
  51     StoreDigestCBlock cblock;
  52     int rebuild_lock;           /* bucket number */
  53     StoreEntry *rewrite_lock;   /* store entry with the digest */
  54     int rebuild_offset;
  55     int rewrite_offset;
  56     int rebuild_count;
  57     int rewrite_count;
  58 } StoreDigestState;
  59
  60 typedef struct {
  61     int del_count;              /* #store entries deleted from store_digest */
  62     int del_lost_count;         /* #store entries not found in store_digest on delete */
  63     int add_count;              /* #store entries accepted to store_digest */
  64     int add_coll_count;         /* #accepted entries that collided with existing ones */
  65     int rej_count;              /* #store entries not accepted to store_digest */
  66     int rej_coll_count;         /* #not accepted entries that collided with existing ones */
  67 } StoreDigestStats;
  68
  69 /*
  70  * local constants (many of these are good candidates for SquidConfig
  71  */
  72
  73 /* #bits per entry in store digest */
  74 static const int StoreDigestBitsPerEntry = 5;
  75 /* how often we want to rebuild the digest, in seconds */
  76 static const time_t StoreDigestRebuildPeriod = 60 * 60;
  77 /* how often we want to rewrite the digest after rebuild, in seconds */
  78 static const int StoreDigestRewritePeriod = 60 * 60;
  79 /* how many bytes to swap out at a time */
  80 static const int StoreDigestSwapOutChunkSize = SM_PAGE_SIZE;
  81 /* portion (0,1] of a hash table to be rescanned at a time */
  82 static const double StoreDigestRebuildChunkPercent = 0.10;
  83
  84 /* local vars */
  85 static StoreDigestState sd_state;
  86 static StoreDigestStats sd_stats;
  87
  88 /* local prototypes */
  89 static void storeDigestRebuildStart(void *datanotused);
  90 static void storeDigestRebuildResume(void);
  91 static void storeDigestRebuildFinish(void);
  92 static void storeDigestRebuildStep(void *datanotused);
  93 static void storeDigestRewriteStart(void *);
  94 static void storeDigestRewriteResume(void);
  95 static void storeDigestRewriteFinish(StoreEntry * e);
  96 static EVH storeDigestSwapOutStep;
  97 static void storeDigestCBlockSwapOut(StoreEntry * e);
  98 static int storeDigestCalcCap(void);
  99 static int storeDigestResize(void);
 100 static void storeDigestAdd(const StoreEntry *);
 101
 102 #endif /* USE_CACHE_DIGESTS */
 103
 104 /*
 105  * PUBLIC FUNCTIONS
 106  */
 107
 108 void
 109 storeDigestInit(void)
 110 {
 111 #if USE_CACHE_DIGESTS
 112     const int cap = storeDigestCalcCap();
 113     store_digest = cacheDigestCreate(cap, StoreDigestBitsPerEntry);
 114     debug(71, 1) ("Local cache digest enabled; rebuild/rewrite every %d/%d sec\n",
 115         StoreDigestRebuildPeriod, StoreDigestRewritePeriod);
 116     memset(&sd_state, 0, sizeof(sd_state));
 117     cachemgrRegister("store_digest", "Store Digest",
 118         storeDigestReport, 0, 1);
 119 #else
 120     store_digest = NULL;
 121     debug(71, 3) ("Local cache digest is 'off'\n");
 122 #endif
 123 }
 124
 125 /* called when store_rebuild completes */
 126 void
 127 storeDigestNoteStoreReady(void)
 128 {
 129 #if USE_CACHE_DIGESTS
 130     storeDigestRebuildStart(NULL);
 131     storeDigestRewriteStart(NULL);
 132 #endif
 133 }
 134
 135 void
 136 storeDigestDel(const StoreEntry * entry)
 137 {
 138 #if USE_CACHE_DIGESTS
 139     assert(entry && store_digest);
 140     debug(71, 6) ("storeDigestDel: checking entry, key: %s\n",
 141         storeKeyText(entry->key));
 142     if (!EBIT_TEST(entry->flags, KEY_PRIVATE)) {
 143         if (!cacheDigestTest(store_digest, entry->key)) {
 144             sd_stats.del_lost_count++;
 145             debug(71, 6) ("storeDigestDel: lost entry, key: %s url: %s\n",
 146                 storeKeyText(entry->key), storeUrl(entry));
 147         } else {
 148             sd_stats.del_count++;
 149             cacheDigestDel(store_digest, entry->key);
 150             debug(71, 6) ("storeDigestDel: deled entry, key: %s\n",
 151                 storeKeyText(entry->key));
 152         }
 153     }
 154 #endif
 155 }
 156
 157 void
 158 storeDigestReport(StoreEntry * e)
 159 {
 160 #if USE_CACHE_DIGESTS
 161     if (store_digest) {
 162         cacheDigestReport(store_digest, "store", e);
 163         storeAppendPrintf(e, "\t added: %d rejected: %d ( %.2f %%) del-ed: %d\n",
 164             sd_stats.add_count,
 165             sd_stats.rej_count,
 166             xpercent(sd_stats.rej_count, sd_stats.rej_count + sd_stats.add_count),
 167             sd_stats.del_count);
 168         storeAppendPrintf(e, "\t collisions: on add: %.2f %% on rej: %.2f %%\n",
 169             xpercent(sd_stats.add_coll_count, sd_stats.add_count),
 170             xpercent(sd_stats.rej_coll_count, sd_stats.rej_count));
 171     } else {
 172         storeAppendPrintf(e, "store digest: disabled.\n");
 173     }
 174 #endif
 175 }
 176
 177 /*
 178  * LOCAL FUNCTIONS
 179  */
 180
 181 #if USE_CACHE_DIGESTS
 182
 183 /* should we digest this entry? used by storeDigestAdd() */
 184 static int
 185 storeDigestAddable(const StoreEntry * e)
 186 {
 187     /* add some stats! XXX */
 188
 189     debug(71, 6) ("storeDigestAddable: checking entry, key: %s\n",
 190         storeKeyText(e->key));
 191
 192     /* check various entry flags (mimics storeCheckCachable XXX) */
 193     if (!EBIT_TEST(e->flags, ENTRY_CACHABLE)) {
 194         debug(71, 6) ("storeDigestAddable: NO: not cachable\n");
 195         return 0;
 196     }
 197     if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
 198         debug(71, 6) ("storeDigestAddable: NO: private key\n");
 199         return 0;
 200     }
 201     if (EBIT_TEST(e->flags, ENTRY_NEGCACHED)) {
 202         debug(71, 6) ("storeDigestAddable: NO: negative cached\n");
 203         return 0;
 204     }
 205     if (EBIT_TEST(e->flags, RELEASE_REQUEST)) {
 206         debug(71, 6) ("storeDigestAddable: NO: release requested\n");
 207         return 0;
 208     }
 209     if (e->store_status == STORE_OK && EBIT_TEST(e->flags, ENTRY_BAD_LENGTH)) {
 210         debug(71, 6) ("storeDigestAddable: NO: wrong content-length\n");
 211         return 0;
 212     }
 213     /* do not digest huge objects */
 214     if (e->swap_file_sz > Config.Store.maxObjectSize) {
 215         debug(71, 6) ("storeDigestAddable: NO: too big\n");
 216         return 0;
 217     }
 218     /* still here? check staleness */
 219     /* Note: We should use the time of the next rebuild, not (cur_time+period) */
 220     if (refreshCheckDigest(e, StoreDigestRebuildPeriod)) {
 221         debug(71, 6) ("storeDigestAdd: entry expires within %d secs, ignoring\n",
 222             StoreDigestRebuildPeriod);
 223         return 0;
 224     }
 225     /* idea: how about also skipping very fresh (thus, potentially unstable)
 226      * entries? Should be configurable through cd_refresh_pattern, of course */
 227
 228     return 1;
 229 }
 230
 231 static void
 232 storeDigestAdd(const StoreEntry * entry)
 233 {
 234     assert(entry && store_digest);
 235
 236     if (storeDigestAddable(entry)) {
 237         sd_stats.add_count++;
 238         if (cacheDigestTest(store_digest, entry->key))
 239             sd_stats.add_coll_count++;
 240         cacheDigestAdd(store_digest, entry->key);
 241         debug(71, 6) ("storeDigestAdd: added entry, key: %s\n",
 242             storeKeyText(entry->key));
 243     } else {
 244         sd_stats.rej_count++;
 245         if (cacheDigestTest(store_digest, entry->key))
 246             sd_stats.rej_coll_count++;
 247     }
 248 }
 249
 250 /* rebuilds digest from scratch */
 251 static void
 252 storeDigestRebuildStart(void *datanotused)
 253 {
 254     assert(store_digest);
 255     /* prevent overlapping if rebuild schedule is too tight */
 256     if (sd_state.rebuild_lock) {
 257         debug(71, 1) ("storeDigestRebuildStart: overlap detected, consider increasing rebuild period\n");
 258         return;
 259     }
 260     sd_state.rebuild_lock = 1;
 261     debug(71, 2) ("storeDigestRebuildStart: rebuild #%d\n", sd_state.rebuild_count + 1);
 262     if (sd_state.rewrite_lock) {
 263         debug(71, 2) ("storeDigestRebuildStart: waiting for Rewrite to finish.\n");
 264         return;
 265     }
 266     storeDigestRebuildResume();
 267 }
 268
 269 /* called be Rewrite to push Rebuild forward */
 270 static void
 271 storeDigestRebuildResume(void)
 272 {
 273     assert(sd_state.rebuild_lock);
 274     assert(!sd_state.rewrite_lock);
 275     sd_state.rebuild_offset = 0;
 276     /* resize or clear */
 277     if (!storeDigestResize())
 278         cacheDigestClear(store_digest);         /* not clean()! */
 279     memset(&sd_stats, 0, sizeof(sd_stats));
 280     eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, NULL, 0.0, 1);
 281 }
 282
 283 /* finishes swap out sequence for the digest; schedules next rebuild */
 284 static void
 285 storeDigestRebuildFinish(void)
 286 {
 287     assert(sd_state.rebuild_lock);
 288     sd_state.rebuild_lock = 0;
 289     sd_state.rebuild_count++;
 290     debug(71, 2) ("storeDigestRebuildFinish: done.\n");
 291     eventAdd("storeDigestRebuildStart", storeDigestRebuildStart, NULL, (double) StoreDigestRebuildPeriod, 1);
 292     /* resume pending Rewrite if any */
 293     if (sd_state.rewrite_lock)
 294         storeDigestRewriteResume();
 295 }
 296
 297 /* recalculate a few hash buckets per invocation; schedules next step */
 298 static void
 299 storeDigestRebuildStep(void *datanotused)
 300 {
 301     int bcount = (int) ceil(store_hash_buckets * StoreDigestRebuildChunkPercent);
 302     assert(sd_state.rebuild_lock);
 303     if (sd_state.rebuild_offset + bcount > store_hash_buckets)
 304         bcount = store_hash_buckets - sd_state.rebuild_offset;
 305     debug(71, 3) ("storeDigestRebuildStep: buckets: %d offset: %d chunk: %d buckets\n",
 306         store_hash_buckets, sd_state.rebuild_offset, bcount);
 307     while (bcount--) {
 308         hash_link *link_ptr = hash_get_bucket(store_table, sd_state.rebuild_offset);
 309         for (; link_ptr; link_ptr = link_ptr->next) {
 310             storeDigestAdd((StoreEntry *) link_ptr);
 311         }
 312         sd_state.rebuild_offset++;
 313     }
 314     /* are we done ? */
 315     if (sd_state.rebuild_offset >= store_hash_buckets)
 316         storeDigestRebuildFinish();
 317     else
 318         eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, NULL, 0.0, 1);
 319 }
 320
 321
 322 /* starts swap out sequence for the digest */
 323 static void
 324 storeDigestRewriteStart(void *datanotused)
 325 {
 326     request_flags flags;
 327     char *url;
 328     StoreEntry *e;
 329
 330     assert(store_digest);
 331     /* prevent overlapping if rewrite schedule is too tight */
 332     if (sd_state.rewrite_lock) {
 333         debug(71, 1) ("storeDigestRewrite: overlap detected, consider increasing rewrite period\n");
 334         return;
 335     }
 336     debug(71, 2) ("storeDigestRewrite: start rewrite #%d\n", sd_state.rewrite_count + 1);
 337     /* make new store entry */
 338     url = internalLocalUri("/squid-internal-periodic/", StoreDigestUrlPath);
 339     flags = null_request_flags;
 340     flags.cachable = 1;
 341     sd_state.rewrite_lock = e = storeCreateEntry(url, url, flags, METHOD_GET);
 342     assert(sd_state.rewrite_lock);
 343     cbdataAdd(sd_state.rewrite_lock, MEM_DONTFREE);
 344     debug(71, 3) ("storeDigestRewrite: url: %s key: %s\n", url, storeKeyText(e->key));
 345     e->mem_obj->request = requestLink(urlParse(METHOD_GET, url));
 346     /* wait for rebuild (if any) to finish */
 347     if (sd_state.rebuild_lock) {
 348         debug(71, 2) ("storeDigestRewriteStart: waiting for rebuild to finish.\n");
 349         return;
 350     }
 351     storeDigestRewriteResume();
 352 }
 353
 354 static void
 355 storeDigestRewriteResume(void)
 356 {
 357     StoreEntry *e = sd_state.rewrite_lock;
 358
 359     assert(sd_state.rewrite_lock);
 360     assert(!sd_state.rebuild_lock);
 361     sd_state.rewrite_offset = 0;
 362     EBIT_SET(e->flags, ENTRY_SPECIAL);
 363     /* setting public key will purge old digest entry if any */
 364     storeSetPublicKey(e);
 365     /* fake reply */
 366     httpReplyReset(e->mem_obj->reply);
 367     httpReplySetHeaders(e->mem_obj->reply, 1.0, 200, "Cache Digest OK",
 368         "application/cache-digest", store_digest->mask_size + sizeof(sd_state.cblock),
 369         squid_curtime, squid_curtime + StoreDigestRewritePeriod);
 370     debug(71, 3) ("storeDigestRewrite: entry expires on %s\n", mkrfc1123(e->mem_obj->reply->expires));
 371     storeBuffer(e);
 372     httpReplySwapOut(e->mem_obj->reply, e);
 373     storeDigestCBlockSwapOut(e);
 374     storeBufferFlush(e);
 375     eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, sd_state.rewrite_lock, 0.0, 1);
 376 }
 377
 378 /* finishes swap out sequence for the digest; schedules next rewrite */
 379 static void
 380 storeDigestRewriteFinish(StoreEntry * e)
 381 {
 382     assert(e == sd_state.rewrite_lock);
 383     storeComplete(e);
 384     storeTimestampsSet(e);
 385     debug(71, 2) ("storeDigestRewriteFinish: digest expires on %s (%d)\n",
 386         mkrfc1123(e->expires), e->expires);
 387     /* is this the write order? @?@ */
 388     requestUnlink(e->mem_obj->request);
 389     e->mem_obj->request = NULL;
 390     storeUnlockObject(e);
 391     /*
 392      * note, it won't really get free()'d here because we used
 393      * MEM_DONTFREE in the call to cbdataAdd().
 394      */
 395     cbdataFree(sd_state.rewrite_lock);
 396     sd_state.rewrite_lock = e = NULL;
 397     sd_state.rewrite_count++;
 398     eventAdd("storeDigestRewriteStart", storeDigestRewriteStart, NULL, (double) StoreDigestRewritePeriod, 1);
 399     /* resume pending Rebuild if any */
 400     if (sd_state.rebuild_lock)
 401         storeDigestRebuildResume();
 402 }
 403
 404 /* swaps out one digest "chunk" per invocation; schedules next swap out */
 405 static void
 406 storeDigestSwapOutStep(void *data)
 407 {
 408     StoreEntry *e = data;
 409     int chunk_size = StoreDigestSwapOutChunkSize;
 410     assert(e);
 411     assert(e == sd_state.rewrite_lock);
 412     /* _add_ check that nothing bad happened while we were waiting @?@ @?@ */
 413     if (sd_state.rewrite_offset + chunk_size > store_digest->mask_size)
 414         chunk_size = store_digest->mask_size - sd_state.rewrite_offset;
 415     storeAppend(e, store_digest->mask + sd_state.rewrite_offset, chunk_size);
 416     debug(71, 3) ("storeDigestSwapOutStep: size: %d offset: %d chunk: %d bytes\n",
 417         store_digest->mask_size, sd_state.rewrite_offset, chunk_size);
 418     sd_state.rewrite_offset += chunk_size;
 419     /* are we done ? */
 420     if (sd_state.rewrite_offset >= store_digest->mask_size)
 421         storeDigestRewriteFinish(e);
 422     else
 423         eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, e, 0.0, 1);
 424 }
 425
 426 static void
 427 storeDigestCBlockSwapOut(StoreEntry * e)
 428 {
 429     memset(&sd_state.cblock, 0, sizeof(sd_state.cblock));
 430     sd_state.cblock.ver.current = htons(CacheDigestVer.current);
 431     sd_state.cblock.ver.required = htons(CacheDigestVer.required);
 432     sd_state.cblock.capacity = htonl(store_digest->capacity);
 433     sd_state.cblock.count = htonl(store_digest->count);
 434     sd_state.cblock.del_count = htonl(store_digest->del_count);
 435     sd_state.cblock.mask_size = htonl(store_digest->mask_size);
 436     sd_state.cblock.bits_per_entry = (unsigned char) StoreDigestBitsPerEntry;
 437     sd_state.cblock.hash_func_count = (unsigned char) CacheDigestHashFuncCount;
 438     storeAppend(e, (char *) &sd_state.cblock, sizeof(sd_state.cblock));
 439 }
 440
 441 /* calculates digest capacity */
 442 static int
 443 storeDigestCalcCap(void)
 444 {
 445     /*
 446      * To-Do: Bloom proved that the optimal filter utilization is 50% (half of
 447      * the bits are off). However, we do not have a formula to calculate the
 448      * number of _entries_ we want to pre-allocate for.
 449      */
 450     const int hi_cap = Config.Swap.maxSize / Config.Store.avgObjectSize;
 451     const int lo_cap = 1 + store_swap_size / Config.Store.avgObjectSize;
 452     const int e_count = memInUse(MEM_STOREENTRY);
 453     int cap = e_count ? e_count : hi_cap;
 454     debug(71, 2) ("storeDigestCalcCap: have: %d, want %d entries; limits: [%d, %d]\n",
 455         e_count, cap, lo_cap, hi_cap);
 456     if (cap < lo_cap)
 457         cap = lo_cap;
 458     /* do not enforce hi_cap limit, average-based estimation may be wrong
 459      *if (cap > hi_cap)
 460      *  cap = hi_cap;
 461      */
 462     return cap;
 463 }
 464
 465 /* returns true if we actually resized the digest */
 466 static int
 467 storeDigestResize(void)
 468 {
 469     const int cap = storeDigestCalcCap();
 470     int diff;
 471     assert(store_digest);
 472     diff = abs(cap - store_digest->capacity);
 473     debug(71, 2) ("storeDigestResize: %d -> %d; change: %d (%d%%)\n",
 474         store_digest->capacity, cap, diff,
 475         xpercentInt(diff, store_digest->capacity));
 476     /* avoid minor adjustments */
 477     if (diff <= store_digest->capacity / 10) {
 478         debug(71, 2) ("storeDigestResize: small change, will not resize.\n");
 479         return 0;
 480     } else {
 481         debug(71, 2) ("storeDigestResize: big change, resizing.\n");
 482         cacheDigestChangeCap(store_digest, cap);
 483         return 1;
 484     }
 485 }
 486
 487 #endif /* USE_CACHE_DIGESTS */