store_digest.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
3 *
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.
7 */
8
9/* DEBUG: section 71 Store Digest Manager */
10
11/*
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
15 */
16
17#include "squid.h"
18#include "debug/Stream.h"
19#include "event.h"
20#include "globals.h"
21#include "mgr/Registration.h"
22#include "store_digest.h"
23
24#if USE_CACHE_DIGESTS
25#include "CacheDigest.h"
26#include "HttpReply.h"
27#include "HttpRequest.h"
28#include "internal.h"
29#include "MemObject.h"
30#include "PeerDigest.h"
31#include "refresh.h"
32#include "SquidConfig.h"
33#include "Store.h"
34#include "StoreSearch.h"
35#include "util.h"
36
37#include <cmath>
38
39/*
40 * local types
41 */
42
44{
45public:
47 int rebuild_lock = 0;
49 StoreEntry * publicEntry = nullptr;
54};
55
57{
58public:
59 int del_count = 0; /* #store entries deleted from store_digest */
60 int del_lost_count = 0; /* #store entries not found in store_digest on delete */
61 int add_count = 0; /* #store entries accepted to store_digest */
62 int add_coll_count = 0; /* #accepted entries that collided with existing ones */
63 int rej_count = 0; /* #store entries not accepted to store_digest */
64 int rej_coll_count = 0; /* #not accepted entries that collided with existing ones */
65};
66
67/* local vars */
70
71/* local prototypes */
72static void storeDigestRebuildStart(void *datanotused);
73static void storeDigestRebuildResume(void);
74static void storeDigestRebuildFinish(void);
75static void storeDigestRebuildStep(void *datanotused);
76static void storeDigestRewriteStart(void *);
77static void storeDigestRewriteResume(void);
81static void storeDigestAdd(const StoreEntry *);
82
84static uint64_t
86{
87 /*
88 * To-Do: Bloom proved that the optimal filter utilization is 50% (half of
89 * the bits are off). However, we do not have a formula to calculate the
90 * number of _entries_ we want to pre-allocate for.
91 */
92 const uint64_t hi_cap = Store::Root().maxSize() / Config.Store.avgObjectSize;
93 const uint64_t lo_cap = 1 + Store::Root().currentSize() / Config.Store.avgObjectSize;
94 const uint64_t e_count = StoreEntry::inUseCount();
95 uint64_t cap = e_count ? e_count : hi_cap;
96 debugs(71, 2, "have: " << e_count << ", want " << cap <<
97 " entries; limits: [" << lo_cap << ", " << hi_cap << "]");
98
99 if (cap < lo_cap)
100 cap = lo_cap;
101
102 /* do not enforce hi_cap limit, average-based estimation may be wrong
103 *if (cap > hi_cap)
104 * cap = hi_cap;
105 */
106
107 // Bug 4534: we still have to set an upper-limit at some reasonable value though.
108 // this matches cacheDigestCalcMaskSize doing (cap*bpe)+7 < INT_MAX
109 const uint64_t absolute_max = (INT_MAX -8) / Config.digest.bits_per_entry;
110 if (cap > absolute_max) {
111 static time_t last_loud = 0;
112 if (last_loud < squid_curtime - 86400) {
113 debugs(71, DBG_IMPORTANT, "WARNING: Cache Digest cannot store " << cap << " entries. Limiting to " << absolute_max);
114 last_loud = squid_curtime;
115 } else {
116 debugs(71, 3, "WARNING: Cache Digest cannot store " << cap << " entries. Limiting to " << absolute_max);
117 }
118 cap = absolute_max;
119 }
120
121 return cap;
122}
123#endif /* USE_CACHE_DIGESTS */
124
125void
127{
128 Mgr::RegisterAction("store_digest", "Store Digest", storeDigestReport, 0, 1);
129
130#if USE_CACHE_DIGESTS
132 store_digest = nullptr;
133 debugs(71, 3, "Local cache digest generation disabled");
134 return;
135 }
136
137 const uint64_t cap = storeDigestCalcCap();
139 debugs(71, DBG_IMPORTANT, "Local cache digest enabled; rebuild/rewrite every " <<
140 (int) Config.digest.rebuild_period << "/" <<
141 (int) Config.digest.rewrite_period << " sec");
142
144#else
146 debugs(71, 3, "Local cache digest is 'off'");
147#endif
148}
149
150/* called when store_rebuild completes */
151void
153{
154#if USE_CACHE_DIGESTS
155
159 }
160
161#endif
162}
163
164//TODO: this seems to be dead code. Is it needed?
165void
167{
168#if USE_CACHE_DIGESTS
169
171 return;
172 }
173
174 assert(entry && store_digest);
175 debugs(71, 6, "storeDigestDel: checking entry, key: " << entry->getMD5Text());
176
177 if (!EBIT_TEST(entry->flags, KEY_PRIVATE)) {
178 if (!store_digest->contains(static_cast<const cache_key *>(entry->key))) {
180 debugs(71, 6, "storeDigestDel: lost entry, key: " << entry->getMD5Text() << " url: " << entry->url() );
181 } else {
183 store_digest->remove(static_cast<const cache_key *>(entry->key));
184 debugs(71, 6, "storeDigestDel: deled entry, key: " << entry->getMD5Text());
185 }
186 }
187#else
188 (void)entry;
189#endif //USE_CACHE_DIGESTS
190}
191
192void
194{
195#if USE_CACHE_DIGESTS
196
198 return;
199 }
200
201 if (store_digest) {
202 static const SBuf label("store");
204 storeAppendPrintf(e, "\t added: %d rejected: %d ( %.2f %%) del-ed: %d\n",
209 storeAppendPrintf(e, "\t collisions: on add: %.2f %% on rej: %.2f %%\n",
212 } else {
213 storeAppendPrintf(e, "store digest: disabled.\n");
214 }
215#else
216 (void)e;
217#endif //USE_CACHE_DIGESTS
218}
219
220/*
221 * LOCAL FUNCTIONS
222 */
223
224#if USE_CACHE_DIGESTS
225
226/* should we digest this entry? used by storeDigestAdd() */
227static int
229{
230 /* add some stats! XXX */
231
232 debugs(71, 6, "storeDigestAddable: checking entry, key: " << e->getMD5Text());
233
234 /* check various entry flags (mimics StoreEntry::checkCachable XXX) */
235
236 if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
237 debugs(71, 6, "storeDigestAddable: NO: private key");
238 return 0;
239 }
240
242 debugs(71, 6, "storeDigestAddable: NO: negative cached");
243 return 0;
244 }
245
247 debugs(71, 6, "storeDigestAddable: NO: release requested");
248 return 0;
249 }
250
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) */
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
281static void
283{
284 assert(entry && store_digest);
285
286 if (storeDigestAddable(entry)) {
288
289 if (store_digest->contains(static_cast<const cache_key *>(entry->key)))
291
292 store_digest->add(static_cast<const cache_key *>(entry->key));
293
294 debugs(71, 6, "storeDigestAdd: added entry, key: " << entry->getMD5Text());
295 } else {
297
298 if (store_digest->contains(static_cast<const cache_key *>(entry->key)))
300 }
301}
302
303/* rebuilds digest from scratch */
304static void
306{
308 /* prevent overlapping if rebuild schedule is too tight */
309
311 debugs(71, DBG_IMPORTANT, "storeDigestRebuildStart: overlap detected, consider increasing rebuild period");
312 return;
313 }
314
316 debugs(71, 2, "storeDigestRebuildStart: rebuild #" << sd_state.rebuild_count + 1);
317
319 debugs(71, 2, "storeDigestRebuildStart: waiting for Rewrite to finish.");
320 return;
321 }
322
324}
325
327static bool
329{
330 const uint64_t cap = storeDigestCalcCap();
332 uint64_t diff;
333 if (cap > store_digest->capacity)
334 diff = cap - store_digest->capacity;
335 else
336 diff = store_digest->capacity - cap;
337 debugs(71, 2, store_digest->capacity << " -> " << cap << "; change: " <<
338 diff << " (" << xpercentInt(diff, store_digest->capacity) << "%)" );
339 /* avoid minor adjustments */
340
341 if (diff <= store_digest->capacity / 10) {
342 debugs(71, 2, "small change, will not resize.");
343 return false;
344 } else {
345 debugs(71, 2, "big change, resizing.");
347 }
348 return true;
349}
350
351/* called be Rewrite to push Rebuild forward */
352static void
354{
358 /* resize or clear */
359
360 if (!storeDigestResize())
361 store_digest->clear(); /* not clean()! */
362
364
365 eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, nullptr, 0.0, 1);
366}
367
368/* finishes swap out sequence for the digest; schedules next rebuild */
369static void
371{
375 debugs(71, 2, "storeDigestRebuildFinish: done.");
376 eventAdd("storeDigestRebuildStart", storeDigestRebuildStart, nullptr, (double)
378 /* resume pending Rewrite if any */
379
382}
383
384/* recalculate a few hash buckets per invocation; schedules next step */
385static void
387{
388 /* TODO: call Store::Root().size() to determine this.. */
389 int count = Config.Store.objectsPerBucket * (int) ceil((double) store_hash_buckets *
392
393 debugs(71, 3, "storeDigestRebuildStep: buckets: " << store_hash_buckets << " entries to check: " << count);
394
395 while (count-- && !sd_state.theSearch->isDone() && sd_state.theSearch->next())
397
398 /* are we done ? */
401 else
402 eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, nullptr, 0.0, 1);
403}
404
405/* starts swap out sequence for the digest */
406static void
408{
410 /* prevent overlapping if rewrite schedule is too tight */
411
413 debugs(71, DBG_IMPORTANT, "storeDigestRewrite: overlap detected, consider increasing rewrite period");
414 return;
415 }
416
417 debugs(71, 2, "storeDigestRewrite: start rewrite #" << sd_state.rewrite_count + 1);
418
419 const char *url = internalLocalUri("/squid-internal-periodic/", SBuf(StoreDigestFileName));
420 const auto mx = MasterXaction::MakePortless<XactionInitiator::initCacheDigest>();
421 auto req = HttpRequest::FromUrlXXX(url, mx);
422
423 RequestFlags flags;
424 flags.cachable = true;
425
426 StoreEntry *e = storeCreateEntry(url, url, flags, Http::METHOD_GET);
427 assert(e);
429 debugs(71, 3, "storeDigestRewrite: url: " << url << " key: " << e->getMD5Text());
430 e->mem_obj->request = req;
431
432 /* wait for rebuild (if any) to finish */
434 debugs(71, 2, "storeDigestRewriteStart: waiting for rebuild to finish.");
435 return;
436 }
437
439}
440
441static void
443{
444 StoreEntry *e;
445
451 /* setting public key will mark the old digest entry for removal once unlocked */
452 e->setPublicKey();
453 if (const auto oldEntry = sd_state.publicEntry) {
454 oldEntry->release(true);
455 sd_state.publicEntry = nullptr;
456 oldEntry->unlock("storeDigestRewriteResume");
457 }
458 assert(e->locked());
460 /* fake reply */
461 HttpReply *rep = new HttpReply;
462 rep->setHeaders(Http::scOkay, "Cache Digest OK",
463 "application/cache-digest", (store_digest->mask_size + sizeof(sd_state.cblock)),
465 debugs(71, 3, "storeDigestRewrite: entry expires on " << rep->expires <<
466 " (" << std::showpos << (int) (rep->expires - squid_curtime) << ")");
467 e->buffer();
468 e->replaceHttpReply(rep);
470 e->flush();
471 eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, sd_state.rewrite_lock, 0.0, 1, false);
472}
473
474/* finishes swap out sequence for the digest; schedules next rewrite */
475static void
477{
479 e->complete();
480 e->timestampsSet();
481 debugs(71, 2, "storeDigestRewriteFinish: digest expires at " << e->expires <<
482 " (" << std::showpos << (int) (e->expires - squid_curtime) << ")");
483 /* is this the write order? @?@ */
485 sd_state.rewrite_lock = nullptr;
487 eventAdd("storeDigestRewriteStart", storeDigestRewriteStart, nullptr, (double)
489 /* resume pending Rebuild if any */
490
493}
494
495/* swaps out one digest "chunk" per invocation; schedules next swap out */
496static void
498{
499 StoreEntry *e = static_cast<StoreEntry *>(data);
500 int chunk_size = Config.digest.swapout_chunk_size;
502 assert(e);
503 /* _add_ check that nothing bad happened while we were waiting @?@ @?@ */
504
505 if (static_cast<uint32_t>(sd_state.rewrite_offset + chunk_size) > store_digest->mask_size)
507
509
510 debugs(71, 3, "storeDigestSwapOutStep: size: " << store_digest->mask_size <<
511 " offset: " << sd_state.rewrite_offset << " chunk: " <<
512 chunk_size << " bytes");
513
514 sd_state.rewrite_offset += chunk_size;
515
516 /* are we done ? */
517 if (static_cast<uint32_t>(sd_state.rewrite_offset) >= store_digest->mask_size)
519 else
520 eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, data, 0.0, 1, false);
521}
522
523static void
525{
526 memset(&sd_state.cblock, 0, sizeof(sd_state.cblock));
535 e->append((char *) &sd_state.cblock, sizeof(sd_state.cblock));
536}
537
538#endif /* USE_CACHE_DIGESTS */
539
void cacheDigestReport(CacheDigest *cd, const SBuf &label, StoreEntry *e)
Definition: CacheDigest.cc:245
time_t squid_curtime
Definition: stub_libtime.cc:20
class SquidConfig Config
Definition: SquidConfig.cc:12
#define assert(EX)
Definition: assert.h:19
void updateCapacity(uint64_t newCapacity)
changes mask size to fit newCapacity, resets bits to 0
Definition: CacheDigest.cc:86
char * mask
Definition: CacheDigest.h:58
uint64_t del_count
Definition: CacheDigest.h:56
uint64_t count
Definition: CacheDigest.h:55
uint32_t mask_size
Definition: CacheDigest.h:59
void add(const cache_key *key)
Definition: CacheDigest.cc:107
uint64_t capacity
Definition: CacheDigest.h:57
bool contains(const cache_key *key) const
Definition: CacheDigest.cc:93
void clear()
reset the digest mask and counters
Definition: CacheDigest.cc:79
void remove(const cache_key *key)
Definition: CacheDigest.cc:140
void setHeaders(Http::StatusCode status, const char *reason, const char *ctype, int64_t clen, time_t lmt, time_t expires)
Definition: HttpReply.cc:167
time_t expires
Definition: HttpReply.h:44
static HttpRequest * FromUrlXXX(const char *url, const MasterXaction::Pointer &, const HttpRequestMethod &method=Http::METHOD_GET)
Definition: HttpRequest.cc:528
HttpRequestPointer request
Definition: MemObject.h:188
void unlinkRequest()
Definition: MemObject.h:55
Definition: SBuf.h:94
int objectsPerBucket
Definition: SquidConfig.h:262
time_t rebuild_period
Definition: SquidConfig.h:486
int64_t avgObjectSize
Definition: SquidConfig.h:263
struct SquidConfig::@119 digest
struct SquidConfig::@111 onoff
size_t swapout_chunk_size
Definition: SquidConfig.h:488
struct SquidConfig::@109 Store
int rebuild_chunk_percentage
Definition: SquidConfig.h:489
int digest_generation
Definition: SquidConfig.h:307
time_t rewrite_period
Definition: SquidConfig.h:487
int64_t maxObjectSize
Definition: SquidConfig.h:264
int bits_per_entry
Definition: SquidConfig.h:485
unsigned char bits_per_entry
Definition: PeerDigest.h:34
unsigned char hash_func_count
Definition: PeerDigest.h:35
StoreEntry * publicEntry
points to the previous store entry with the digest
Definition: store_digest.cc:49
int rebuild_lock
bucket number
Definition: store_digest.cc:47
StoreDigestCBlock cblock
Definition: store_digest.cc:46
StoreSearchPointer theSearch
Definition: store_digest.cc:50
StoreEntry * rewrite_lock
points to store entry with the digest
Definition: store_digest.cc:48
uint16_t flags
Definition: Store.h:232
virtual void buffer()
Definition: store.cc:1568
int locked() const
Definition: Store.h:146
virtual void flush()
Definition: store.cc:1579
int unlock(const char *context)
Definition: store.cc:442
const char * url() const
Definition: store.cc:1533
void complete()
Definition: store.cc:1004
time_t expires
Definition: Store.h:226
virtual void append(char const *, int)
Appends a c-string to existing packed data.
Definition: store.cc:776
bool timestampsSet()
Definition: store.cc:1360
const char * getMD5Text() const
Definition: store.cc:204
static size_t inUseCount()
Definition: store.cc:196
void replaceHttpReply(const HttpReplyPointer &, const bool andStartWriting=true)
Definition: store.cc:1672
MemObject * mem_obj
Definition: Store.h:221
store_status_t store_status
Definition: Store.h:244
bool setPublicKey(const KeyScope keyScope=ksDefault)
Definition: store.cc:548
uint64_t swap_file_sz
Definition: Store.h:230
virtual void next(void(callback)(void *cbdata), void *cbdata)=0
virtual StoreEntry * currentItem()=0
virtual bool isDone() const =0
virtual uint64_t maxSize() const override
Definition: Controller.cc:159
StoreSearch * search()
Definition: Controller.cc:211
virtual uint64_t currentSize() const override
current size
Definition: Controller.cc:173
short int required
Definition: PeerDigest.h:21
short int current
Definition: PeerDigest.h:20
#define DBG_IMPORTANT
Definition: Stream.h:41
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:196
#define EBIT_SET(flag, bit)
Definition: defines.h:67
#define EBIT_TEST(flag, bit)
Definition: defines.h:69
@ ENTRY_BAD_LENGTH
Definition: enums.h:114
@ ENTRY_SPECIAL
Definition: enums.h:84
@ KEY_PRIVATE
Definition: enums.h:102
@ RELEASE_REQUEST
prohibits making the key public
Definition: enums.h:98
@ ENTRY_NEGCACHED
Definition: enums.h:112
@ STORE_OK
Definition: enums.h:50
void eventAdd(const char *name, EVH *func, void *arg, double when, int weight, bool cbdata)
Definition: event.cc:107
void EVH(void *)
Definition: event.h:18
int store_hash_buckets
int CacheDigestHashFuncCount
const char * StoreDigestFileName
CacheDigest * store_digest
char * internalLocalUri(const char *dir, const SBuf &name)
Definition: internal.cc:130
@ scOkay
Definition: StatusCode.h:26
@ METHOD_GET
Definition: MethodType.h:25
void RegisterAction(char const *action, char const *desc, OBJH *handler, int pw_req_flag, int atomic)
Definition: Registration.cc:16
Controller & Root()
safely access controller singleton
Definition: Controller.cc:926
Version const CacheDigestVer
Definition: peer_digest.cc:55
int refreshCheckDigest(const StoreEntry *entry, time_t delta)
Definition: refresh.cc:611
unsigned char cache_key
Store key.
Definition: forward.h:29
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:828
StoreEntry * storeCreateEntry(const char *url, const char *logUrl, const RequestFlags &flags, const HttpRequestMethod &method)
Definition: store.cc:732
static StoreDigestStats sd_stats
Definition: store_digest.cc:69
static void storeDigestRebuildStart(void *datanotused)
static EVH storeDigestSwapOutStep
Definition: store_digest.cc:79
static void storeDigestRebuildResume(void)
static void storeDigestCBlockSwapOut(StoreEntry *e)
void storeDigestDel(const StoreEntry *entry)
static void storeDigestAdd(const StoreEntry *)
static void storeDigestRewriteFinish(StoreEntry *e)
static void storeDigestRebuildStep(void *datanotused)
void storeDigestNoteStoreReady(void)
static void storeDigestRewriteStart(void *)
void storeDigestReport(StoreEntry *e)
void storeDigestInit(void)
static uint64_t storeDigestCalcCap()
calculates digest capacity
Definition: store_digest.cc:85
static void storeDigestRebuildFinish(void)
static int storeDigestAddable(const StoreEntry *e)
static void storeDigestRewriteResume(void)
static bool storeDigestResize()
static StoreDigestState sd_state
Definition: store_digest.cc:68
void EVH void double
Definition: stub_event.cc:16
int unsigned int
Definition: stub_fd.cc:19
#define NULL
Definition: types.h:166
#define INT_MAX
Definition: types.h:76
SQUIDCEXTERN int xpercentInt(double part, double whole)
Definition: util.c:46
SQUIDCEXTERN double xpercent(double part, double whole)
Definition: util.c:40

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors