2 * Copyright (C) 1996-2014 The Squid Software Foundation and contributors
4 * Squid software is distributed under GPLv2+ license and includes
5 * contributions from numerous individuals and organizations.
6 * Please see the COPYING and CONTRIBUTORS files for details.
9 /* DEBUG: section 71 Store Digest Manager */
12 * TODO: We probably do not track all the cases when
13 * storeDigestNoteStoreReady() must be called; this may prevent
14 * storeDigestRebuild/write schedule to be activated
21 #include "mgr/Registration.h"
22 #include "store_digest.h"
25 #include "CacheDigest.h"
26 #include "HttpReply.h"
27 #include "HttpRequest.h"
29 #include "MemObject.h"
30 #include "PeerDigest.h"
32 #include "SquidConfig.h"
33 #include "SquidTime.h"
35 #include "StoreSearch.h"
44 class StoreDigestState
48 StoreDigestCBlock cblock
;
49 int rebuild_lock
; /* bucket number */
50 StoreEntry
* rewrite_lock
; /* points to store entry with the digest */
51 StoreSearchPointer theSearch
;
58 int del_count
; /* #store entries deleted from store_digest */
59 int del_lost_count
; /* #store entries not found in store_digest on delete */
60 int add_count
; /* #store entries accepted to store_digest */
61 int add_coll_count
; /* #accepted entries that collided with existing ones */
62 int rej_count
; /* #store entries not accepted to store_digest */
63 int rej_coll_count
; /* #not accepted entries that collided with existing ones */
67 static StoreDigestState sd_state
;
68 static StoreDigestStats sd_stats
;
70 /* local prototypes */
71 static void storeDigestRebuildStart(void *datanotused
);
72 static void storeDigestRebuildResume(void);
73 static void storeDigestRebuildFinish(void);
74 static void storeDigestRebuildStep(void *datanotused
);
75 static void storeDigestRewriteStart(void *);
76 static void storeDigestRewriteResume(void);
77 static void storeDigestRewriteFinish(StoreEntry
* e
);
78 static EVH storeDigestSwapOutStep
;
79 static void storeDigestCBlockSwapOut(StoreEntry
* e
);
80 static int storeDigestCalcCap(void);
81 static int storeDigestResize(void);
82 static void storeDigestAdd(const StoreEntry
*);
84 #endif /* USE_CACHE_DIGESTS */
87 storeDigestRegisterWithCacheManager(void)
89 Mgr::RegisterAction("store_digest", "Store Digest", storeDigestReport
, 0, 1);
99 storeDigestRegisterWithCacheManager();
101 #if USE_CACHE_DIGESTS
102 const int cap
= storeDigestCalcCap();
104 if (!Config
.onoff
.digest_generation
) {
106 debugs(71, 3, "Local cache digest generation disabled");
110 store_digest
= cacheDigestCreate(cap
, Config
.digest
.bits_per_entry
);
111 debugs(71, DBG_IMPORTANT
, "Local cache digest enabled; rebuild/rewrite every " <<
112 (int) Config
.digest
.rebuild_period
<< "/" <<
113 (int) Config
.digest
.rewrite_period
<< " sec");
115 memset(&sd_state
, 0, sizeof(sd_state
));
118 debugs(71, 3, "Local cache digest is 'off'");
122 /* called when store_rebuild completes */
124 storeDigestNoteStoreReady(void)
126 #if USE_CACHE_DIGESTS
128 if (Config
.onoff
.digest_generation
) {
129 storeDigestRebuildStart(NULL
);
130 storeDigestRewriteStart(NULL
);
136 //TODO: this seems to be dead code. Is it needed?
138 storeDigestDel(const StoreEntry
* entry
)
140 #if USE_CACHE_DIGESTS
142 if (!Config
.onoff
.digest_generation
) {
146 assert(entry
&& store_digest
);
147 debugs(71, 6, "storeDigestDel: checking entry, key: " << entry
->getMD5Text());
149 if (!EBIT_TEST(entry
->flags
, KEY_PRIVATE
)) {
150 if (!cacheDigestTest(store_digest
, (const cache_key
*)entry
->key
)) {
151 ++sd_stats
.del_lost_count
;
152 debugs(71, 6, "storeDigestDel: lost entry, key: " << entry
->getMD5Text() << " url: " << entry
->url() );
154 ++sd_stats
.del_count
;
155 cacheDigestDel(store_digest
, (const cache_key
*)entry
->key
);
156 debugs(71, 6, "storeDigestDel: deled entry, key: " << entry
->getMD5Text());
159 #endif //USE_CACHE_DIGESTS
163 storeDigestReport(StoreEntry
* e
)
165 #if USE_CACHE_DIGESTS
167 if (!Config
.onoff
.digest_generation
) {
172 cacheDigestReport(store_digest
, "store", e
);
173 storeAppendPrintf(e
, "\t added: %d rejected: %d ( %.2f %%) del-ed: %d\n",
176 xpercent(sd_stats
.rej_count
, sd_stats
.rej_count
+ sd_stats
.add_count
),
178 storeAppendPrintf(e
, "\t collisions: on add: %.2f %% on rej: %.2f %%\n",
179 xpercent(sd_stats
.add_coll_count
, sd_stats
.add_count
),
180 xpercent(sd_stats
.rej_coll_count
, sd_stats
.rej_count
));
182 storeAppendPrintf(e
, "store digest: disabled.\n");
185 #endif //USE_CACHE_DIGESTS
192 #if USE_CACHE_DIGESTS
194 /* should we digest this entry? used by storeDigestAdd() */
196 storeDigestAddable(const StoreEntry
* e
)
198 /* add some stats! XXX */
200 debugs(71, 6, "storeDigestAddable: checking entry, key: " << e
->getMD5Text());
202 /* check various entry flags (mimics StoreEntry::checkCachable XXX) */
204 if (EBIT_TEST(e
->flags
, KEY_PRIVATE
)) {
205 debugs(71, 6, "storeDigestAddable: NO: private key");
209 if (EBIT_TEST(e
->flags
, ENTRY_NEGCACHED
)) {
210 debugs(71, 6, "storeDigestAddable: NO: negative cached");
214 if (EBIT_TEST(e
->flags
, RELEASE_REQUEST
)) {
215 debugs(71, 6, "storeDigestAddable: NO: release requested");
219 if (e
->store_status
== STORE_OK
&& EBIT_TEST(e
->flags
, ENTRY_BAD_LENGTH
)) {
220 debugs(71, 6, "storeDigestAddable: NO: wrong content-length");
224 /* do not digest huge objects */
225 if (e
->swap_file_sz
> (uint64_t )Config
.Store
.maxObjectSize
) {
226 debugs(71, 6, "storeDigestAddable: NO: too big");
230 /* still here? check staleness */
231 /* Note: We should use the time of the next rebuild, not (cur_time+period) */
232 if (refreshCheckDigest(e
, Config
.digest
.rebuild_period
)) {
233 debugs(71, 6, "storeDigestAdd: entry expires within " << Config
.digest
.rebuild_period
<< " secs, ignoring");
238 * idea: how about also skipping very fresh (thus, potentially
239 * unstable) entries? Should be configurable through
240 * cd_refresh_pattern, of course.
243 * idea: skip objects that are going to be purged before the next
250 storeDigestAdd(const StoreEntry
* entry
)
252 assert(entry
&& store_digest
);
254 if (storeDigestAddable(entry
)) {
255 ++sd_stats
.add_count
;
257 if (cacheDigestTest(store_digest
, (const cache_key
*)entry
->key
))
258 ++sd_stats
.add_coll_count
;
260 cacheDigestAdd(store_digest
, (const cache_key
*)entry
->key
);
262 debugs(71, 6, "storeDigestAdd: added entry, key: " << entry
->getMD5Text());
264 ++sd_stats
.rej_count
;
266 if (cacheDigestTest(store_digest
, (const cache_key
*)entry
->key
))
267 ++sd_stats
.rej_coll_count
;
271 /* rebuilds digest from scratch */
273 storeDigestRebuildStart(void *datanotused
)
275 assert(store_digest
);
276 /* prevent overlapping if rebuild schedule is too tight */
278 if (sd_state
.rebuild_lock
) {
279 debugs(71, DBG_IMPORTANT
, "storeDigestRebuildStart: overlap detected, consider increasing rebuild period");
283 sd_state
.rebuild_lock
= 1;
284 debugs(71, 2, "storeDigestRebuildStart: rebuild #" << sd_state
.rebuild_count
+ 1);
286 if (sd_state
.rewrite_lock
) {
287 debugs(71, 2, "storeDigestRebuildStart: waiting for Rewrite to finish.");
291 storeDigestRebuildResume();
294 /* called be Rewrite to push Rebuild forward */
296 storeDigestRebuildResume(void)
298 assert(sd_state
.rebuild_lock
);
299 assert(!sd_state
.rewrite_lock
);
300 sd_state
.theSearch
= Store::Root().search(NULL
, NULL
);
301 /* resize or clear */
303 if (!storeDigestResize())
304 cacheDigestClear(store_digest
); /* not clean()! */
306 memset(&sd_stats
, 0, sizeof(sd_stats
));
308 eventAdd("storeDigestRebuildStep", storeDigestRebuildStep
, NULL
, 0.0, 1);
311 /* finishes swap out sequence for the digest; schedules next rebuild */
313 storeDigestRebuildFinish(void)
315 assert(sd_state
.rebuild_lock
);
316 sd_state
.rebuild_lock
= 0;
317 ++sd_state
.rebuild_count
;
318 debugs(71, 2, "storeDigestRebuildFinish: done.");
319 eventAdd("storeDigestRebuildStart", storeDigestRebuildStart
, NULL
, (double)
320 Config
.digest
.rebuild_period
, 1);
321 /* resume pending Rewrite if any */
323 if (sd_state
.rewrite_lock
)
324 storeDigestRewriteResume();
327 /* recalculate a few hash buckets per invocation; schedules next step */
329 storeDigestRebuildStep(void *datanotused
)
331 /* TODO: call Store::Root().size() to determine this.. */
332 int count
= Config
.Store
.objectsPerBucket
* (int) ceil((double) store_hash_buckets
*
333 (double) Config
.digest
.rebuild_chunk_percentage
/ 100.0);
334 assert(sd_state
.rebuild_lock
);
336 debugs(71, 3, "storeDigestRebuildStep: buckets: " << store_hash_buckets
<< " entries to check: " << count
);
338 while (count
-- && !sd_state
.theSearch
->isDone() && sd_state
.theSearch
->next())
339 storeDigestAdd(sd_state
.theSearch
->currentItem());
342 if (sd_state
.theSearch
->isDone())
343 storeDigestRebuildFinish();
345 eventAdd("storeDigestRebuildStep", storeDigestRebuildStep
, NULL
, 0.0, 1);
348 /* starts swap out sequence for the digest */
350 storeDigestRewriteStart(void *datanotused
)
356 assert(store_digest
);
357 /* prevent overlapping if rewrite schedule is too tight */
359 if (sd_state
.rewrite_lock
) {
360 debugs(71, DBG_IMPORTANT
, "storeDigestRewrite: overlap detected, consider increasing rewrite period");
364 debugs(71, 2, "storeDigestRewrite: start rewrite #" << sd_state
.rewrite_count
+ 1);
365 /* make new store entry */
366 url
= internalLocalUri("/squid-internal-periodic/", StoreDigestFileName
);
367 flags
.cachable
= true;
368 e
= storeCreateEntry(url
, url
, flags
, Http::METHOD_GET
);
370 sd_state
.rewrite_lock
= e
;
371 debugs(71, 3, "storeDigestRewrite: url: " << url
<< " key: " << e
->getMD5Text());
372 HttpRequest
*req
= HttpRequest::CreateFromUrl(url
);
373 e
->mem_obj
->request
= req
;
374 HTTPMSGLOCK(e
->mem_obj
->request
);
375 /* wait for rebuild (if any) to finish */
377 if (sd_state
.rebuild_lock
) {
378 debugs(71, 2, "storeDigestRewriteStart: waiting for rebuild to finish.");
382 storeDigestRewriteResume();
386 storeDigestRewriteResume(void)
390 assert(sd_state
.rewrite_lock
);
391 assert(!sd_state
.rebuild_lock
);
392 e
= sd_state
.rewrite_lock
;
393 sd_state
.rewrite_offset
= 0;
394 EBIT_SET(e
->flags
, ENTRY_SPECIAL
);
395 /* setting public key will purge old digest entry if any */
398 HttpReply
*rep
= new HttpReply
;
399 rep
->setHeaders(Http::scOkay
, "Cache Digest OK",
400 "application/cache-digest", (store_digest
->mask_size
+ sizeof(sd_state
.cblock
)),
401 squid_curtime
, (squid_curtime
+ Config
.digest
.rewrite_period
) );
402 debugs(71, 3, "storeDigestRewrite: entry expires on " << rep
->expires
<<
403 " (" << std::showpos
<< (int) (rep
->expires
- squid_curtime
) << ")");
405 e
->replaceHttpReply(rep
);
406 storeDigestCBlockSwapOut(e
);
408 eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep
, sd_state
.rewrite_lock
, 0.0, 1, false);
411 /* finishes swap out sequence for the digest; schedules next rewrite */
413 storeDigestRewriteFinish(StoreEntry
* e
)
415 assert(e
== sd_state
.rewrite_lock
);
418 debugs(71, 2, "storeDigestRewriteFinish: digest expires at " << e
->expires
<<
419 " (" << std::showpos
<< (int) (e
->expires
- squid_curtime
) << ")");
420 /* is this the write order? @?@ */
421 e
->mem_obj
->unlinkRequest();
422 e
->unlock("storeDigestRewriteFinish");
423 sd_state
.rewrite_lock
= NULL
;
424 ++sd_state
.rewrite_count
;
425 eventAdd("storeDigestRewriteStart", storeDigestRewriteStart
, NULL
, (double)
426 Config
.digest
.rewrite_period
, 1);
427 /* resume pending Rebuild if any */
429 if (sd_state
.rebuild_lock
)
430 storeDigestRebuildResume();
433 /* swaps out one digest "chunk" per invocation; schedules next swap out */
435 storeDigestSwapOutStep(void *data
)
437 StoreEntry
*e
= static_cast<StoreEntry
*>(data
);
438 int chunk_size
= Config
.digest
.swapout_chunk_size
;
439 assert(e
== sd_state
.rewrite_lock
);
441 /* _add_ check that nothing bad happened while we were waiting @?@ @?@ */
443 if (sd_state
.rewrite_offset
+ chunk_size
> store_digest
->mask_size
)
444 chunk_size
= store_digest
->mask_size
- sd_state
.rewrite_offset
;
446 e
->append(store_digest
->mask
+ sd_state
.rewrite_offset
, chunk_size
);
448 debugs(71, 3, "storeDigestSwapOutStep: size: " << store_digest
->mask_size
<<
449 " offset: " << sd_state
.rewrite_offset
<< " chunk: " <<
450 chunk_size
<< " bytes");
452 sd_state
.rewrite_offset
+= chunk_size
;
455 if (sd_state
.rewrite_offset
>= store_digest
->mask_size
)
456 storeDigestRewriteFinish(e
);
458 eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep
, data
, 0.0, 1, false);
462 storeDigestCBlockSwapOut(StoreEntry
* e
)
464 memset(&sd_state
.cblock
, 0, sizeof(sd_state
.cblock
));
465 sd_state
.cblock
.ver
.current
= htons(CacheDigestVer
.current
);
466 sd_state
.cblock
.ver
.required
= htons(CacheDigestVer
.required
);
467 sd_state
.cblock
.capacity
= htonl(store_digest
->capacity
);
468 sd_state
.cblock
.count
= htonl(store_digest
->count
);
469 sd_state
.cblock
.del_count
= htonl(store_digest
->del_count
);
470 sd_state
.cblock
.mask_size
= htonl(store_digest
->mask_size
);
471 sd_state
.cblock
.bits_per_entry
= (unsigned char)
472 Config
.digest
.bits_per_entry
;
473 sd_state
.cblock
.hash_func_count
= (unsigned char) CacheDigestHashFuncCount
;
474 e
->append((char *) &sd_state
.cblock
, sizeof(sd_state
.cblock
));
477 /* calculates digest capacity */
479 storeDigestCalcCap(void)
482 * To-Do: Bloom proved that the optimal filter utilization is 50% (half of
483 * the bits are off). However, we do not have a formula to calculate the
484 * number of _entries_ we want to pre-allocate for.
486 const int hi_cap
= Store::Root().maxSize() / Config
.Store
.avgObjectSize
;
487 const int lo_cap
= 1 + Store::Root().currentSize() / Config
.Store
.avgObjectSize
;
488 const int e_count
= StoreEntry::inUseCount();
489 int cap
= e_count
? e_count
:hi_cap
;
490 debugs(71, 2, "storeDigestCalcCap: have: " << e_count
<< ", want " << cap
<<
491 " entries; limits: [" << lo_cap
<< ", " << hi_cap
<< "]");
496 /* do not enforce hi_cap limit, average-based estimation may be wrong
503 /* returns true if we actually resized the digest */
505 storeDigestResize(void)
507 const int cap
= storeDigestCalcCap();
509 assert(store_digest
);
510 diff
= abs(cap
- store_digest
->capacity
);
511 debugs(71, 2, "storeDigestResize: " <<
512 store_digest
->capacity
<< " -> " << cap
<< "; change: " <<
513 diff
<< " (" << xpercentInt(diff
, store_digest
->capacity
) << "%)" );
514 /* avoid minor adjustments */
516 if (diff
<= store_digest
->capacity
/ 10) {
517 debugs(71, 2, "storeDigestResize: small change, will not resize.");
520 debugs(71, 2, "storeDigestResize: big change, resizing.");
521 cacheDigestChangeCap(store_digest
, cap
);
526 #endif /* USE_CACHE_DIGESTS */