store_digest.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2020 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.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 "SquidTime.h"
34 #include "Store.h"
35 #include "StoreSearch.h"
36 #include "util.h"
37 
38 #include <cmath>
39 
40 /*
41  * local types
42  */
43 
45 {
46 public:
48  int rebuild_lock = 0;
49  StoreEntry * rewrite_lock = nullptr;
50  StoreEntry * publicEntry = nullptr;
52  int rewrite_offset = 0;
53  int rebuild_count = 0;
54  int rewrite_count = 0;
55 };
56 
58 {
59 public:
60  int del_count = 0; /* #store entries deleted from store_digest */
61  int del_lost_count = 0; /* #store entries not found in store_digest on delete */
62  int add_count = 0; /* #store entries accepted to store_digest */
63  int add_coll_count = 0; /* #accepted entries that collided with existing ones */
64  int rej_count = 0; /* #store entries not accepted to store_digest */
65  int rej_coll_count = 0; /* #not accepted entries that collided with existing ones */
66 };
67 
68 /* local vars */
71 
72 /* local prototypes */
73 static void storeDigestRebuildStart(void *datanotused);
74 static void storeDigestRebuildResume(void);
75 static void storeDigestRebuildFinish(void);
76 static void storeDigestRebuildStep(void *datanotused);
77 static void storeDigestRewriteStart(void *);
78 static void storeDigestRewriteResume(void);
79 static void storeDigestRewriteFinish(StoreEntry * e);
81 static void storeDigestCBlockSwapOut(StoreEntry * e);
82 static void storeDigestAdd(const StoreEntry *);
83 
85 static uint64_t
87 {
88  /*
89  * To-Do: Bloom proved that the optimal filter utilization is 50% (half of
90  * the bits are off). However, we do not have a formula to calculate the
91  * number of _entries_ we want to pre-allocate for.
92  */
93  const uint64_t hi_cap = Store::Root().maxSize() / Config.Store.avgObjectSize;
94  const uint64_t lo_cap = 1 + Store::Root().currentSize() / Config.Store.avgObjectSize;
95  const uint64_t e_count = StoreEntry::inUseCount();
96  uint64_t cap = e_count ? e_count : hi_cap;
97  debugs(71, 2, "have: " << e_count << ", want " << cap <<
98  " entries; limits: [" << lo_cap << ", " << hi_cap << "]");
99 
100  if (cap < lo_cap)
101  cap = lo_cap;
102 
103  /* do not enforce hi_cap limit, average-based estimation may be wrong
104  *if (cap > hi_cap)
105  * cap = hi_cap;
106  */
107 
108  // Bug 4534: we still have to set an upper-limit at some reasonable value though.
109  // this matches cacheDigestCalcMaskSize doing (cap*bpe)+7 < INT_MAX
110  const uint64_t absolute_max = (INT_MAX -8) / Config.digest.bits_per_entry;
111  if (cap > absolute_max) {
112  static time_t last_loud = 0;
113  if (last_loud < squid_curtime - 86400) {
114  debugs(71, DBG_IMPORTANT, "WARNING: Cache Digest cannot store " << cap << " entries. Limiting to " << absolute_max);
115  last_loud = squid_curtime;
116  } else {
117  debugs(71, 3, "WARNING: Cache Digest cannot store " << cap << " entries. Limiting to " << absolute_max);
118  }
119  cap = absolute_max;
120  }
121 
122  return cap;
123 }
124 #endif /* USE_CACHE_DIGESTS */
125 
126 void
128 {
129  Mgr::RegisterAction("store_digest", "Store Digest", storeDigestReport, 0, 1);
130 
131 #if USE_CACHE_DIGESTS
133  store_digest = NULL;
134  debugs(71, 3, "Local cache digest generation disabled");
135  return;
136  }
137 
138  const uint64_t cap = storeDigestCalcCap();
140  debugs(71, DBG_IMPORTANT, "Local cache digest enabled; rebuild/rewrite every " <<
141  (int) Config.digest.rebuild_period << "/" <<
142  (int) Config.digest.rewrite_period << " sec");
143 
145 #else
146  store_digest = NULL;
147  debugs(71, 3, "Local cache digest is 'off'");
148 #endif
149 }
150 
151 /* called when store_rebuild completes */
152 void
154 {
155 #if USE_CACHE_DIGESTS
156 
160  }
161 
162 #endif
163 }
164 
165 //TODO: this seems to be dead code. Is it needed?
166 void
168 {
169 #if USE_CACHE_DIGESTS
170 
172  return;
173  }
174 
175  assert(entry && store_digest);
176  debugs(71, 6, "storeDigestDel: checking entry, key: " << entry->getMD5Text());
177 
178  if (!EBIT_TEST(entry->flags, KEY_PRIVATE)) {
179  if (!store_digest->contains(static_cast<const cache_key *>(entry->key))) {
181  debugs(71, 6, "storeDigestDel: lost entry, key: " << entry->getMD5Text() << " url: " << entry->url() );
182  } else {
184  store_digest->remove(static_cast<const cache_key *>(entry->key));
185  debugs(71, 6, "storeDigestDel: deled entry, key: " << entry->getMD5Text());
186  }
187  }
188 #endif //USE_CACHE_DIGESTS
189 }
190 
191 void
193 {
194 #if USE_CACHE_DIGESTS
195 
197  return;
198  }
199 
200  if (store_digest) {
201  static const SBuf label("store");
202  cacheDigestReport(store_digest, label, e);
203  storeAppendPrintf(e, "\t added: %d rejected: %d ( %.2f %%) del-ed: %d\n",
208  storeAppendPrintf(e, "\t collisions: on add: %.2f %% on rej: %.2f %%\n",
211  } else {
212  storeAppendPrintf(e, "store digest: disabled.\n");
213  }
214 
215 #endif //USE_CACHE_DIGESTS
216 }
217 
218 /*
219  * LOCAL FUNCTIONS
220  */
221 
222 #if USE_CACHE_DIGESTS
223 
224 /* should we digest this entry? used by storeDigestAdd() */
225 static int
227 {
228  /* add some stats! XXX */
229 
230  debugs(71, 6, "storeDigestAddable: checking entry, key: " << e->getMD5Text());
231 
232  /* check various entry flags (mimics StoreEntry::checkCachable XXX) */
233 
234  if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
235  debugs(71, 6, "storeDigestAddable: NO: private key");
236  return 0;
237  }
238 
239  if (EBIT_TEST(e->flags, ENTRY_NEGCACHED)) {
240  debugs(71, 6, "storeDigestAddable: NO: negative cached");
241  return 0;
242  }
243 
244  if (EBIT_TEST(e->flags, RELEASE_REQUEST)) {
245  debugs(71, 6, "storeDigestAddable: NO: release requested");
246  return 0;
247  }
248 
250  debugs(71, 6, "storeDigestAddable: NO: wrong content-length");
251  return 0;
252  }
253 
254  /* do not digest huge objects */
255  if (e->swap_file_sz > (uint64_t )Config.Store.maxObjectSize) {
256  debugs(71, 6, "storeDigestAddable: NO: too big");
257  return 0;
258  }
259 
260  /* still here? check staleness */
261  /* Note: We should use the time of the next rebuild, not (cur_time+period) */
263  debugs(71, 6, "storeDigestAdd: entry expires within " << Config.digest.rebuild_period << " secs, ignoring");
264  return 0;
265  }
266 
267  /*
268  * idea: how about also skipping very fresh (thus, potentially
269  * unstable) entries? Should be configurable through
270  * cd_refresh_pattern, of course.
271  */
272  /*
273  * idea: skip objects that are going to be purged before the next
274  * update.
275  */
276  return 1;
277 }
278 
279 static void
281 {
282  assert(entry && store_digest);
283 
284  if (storeDigestAddable(entry)) {
286 
287  if (store_digest->contains(static_cast<const cache_key *>(entry->key)))
289 
290  store_digest->add(static_cast<const cache_key *>(entry->key));
291 
292  debugs(71, 6, "storeDigestAdd: added entry, key: " << entry->getMD5Text());
293  } else {
295 
296  if (store_digest->contains(static_cast<const cache_key *>(entry->key)))
298  }
299 }
300 
301 /* rebuilds digest from scratch */
302 static void
303 storeDigestRebuildStart(void *datanotused)
304 {
306  /* prevent overlapping if rebuild schedule is too tight */
307 
308  if (sd_state.rebuild_lock) {
309  debugs(71, DBG_IMPORTANT, "storeDigestRebuildStart: overlap detected, consider increasing rebuild period");
310  return;
311  }
312 
314  debugs(71, 2, "storeDigestRebuildStart: rebuild #" << sd_state.rebuild_count + 1);
315 
316  if (sd_state.rewrite_lock) {
317  debugs(71, 2, "storeDigestRebuildStart: waiting for Rewrite to finish.");
318  return;
319  }
320 
322 }
323 
325 static bool
327 {
328  const uint64_t cap = storeDigestCalcCap();
330  uint64_t diff;
331  if (cap > store_digest->capacity)
332  diff = cap - store_digest->capacity;
333  else
334  diff = store_digest->capacity - cap;
335  debugs(71, 2, store_digest->capacity << " -> " << cap << "; change: " <<
336  diff << " (" << xpercentInt(diff, store_digest->capacity) << "%)" );
337  /* avoid minor adjustments */
338 
339  if (diff <= store_digest->capacity / 10) {
340  debugs(71, 2, "small change, will not resize.");
341  return false;
342  } else {
343  debugs(71, 2, "big change, resizing.");
345  }
346  return true;
347 }
348 
349 /* called be Rewrite to push Rebuild forward */
350 static void
352 {
356  /* resize or clear */
357 
358  if (!storeDigestResize())
359  store_digest->clear(); /* not clean()! */
360 
362 
363  eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, NULL, 0.0, 1);
364 }
365 
366 /* finishes swap out sequence for the digest; schedules next rebuild */
367 static void
369 {
373  debugs(71, 2, "storeDigestRebuildFinish: done.");
374  eventAdd("storeDigestRebuildStart", storeDigestRebuildStart, NULL, (double)
376  /* resume pending Rewrite if any */
377 
380 }
381 
382 /* recalculate a few hash buckets per invocation; schedules next step */
383 static void
384 storeDigestRebuildStep(void *datanotused)
385 {
386  /* TODO: call Store::Root().size() to determine this.. */
387  int count = Config.Store.objectsPerBucket * (int) ceil((double) store_hash_buckets *
388  (double) Config.digest.rebuild_chunk_percentage / 100.0);
390 
391  debugs(71, 3, "storeDigestRebuildStep: buckets: " << store_hash_buckets << " entries to check: " << count);
392 
393  while (count-- && !sd_state.theSearch->isDone() && sd_state.theSearch->next())
395 
396  /* are we done ? */
397  if (sd_state.theSearch->isDone())
399  else
400  eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, NULL, 0.0, 1);
401 }
402 
403 /* starts swap out sequence for the digest */
404 static void
405 storeDigestRewriteStart(void *datanotused)
406 {
408  /* prevent overlapping if rewrite schedule is too tight */
409 
410  if (sd_state.rewrite_lock) {
411  debugs(71, DBG_IMPORTANT, "storeDigestRewrite: overlap detected, consider increasing rewrite period");
412  return;
413  }
414 
415  debugs(71, 2, "storeDigestRewrite: start rewrite #" << sd_state.rewrite_count + 1);
416 
417  const char *url = internalLocalUri("/squid-internal-periodic/", SBuf(StoreDigestFileName));
419  auto req = HttpRequest::FromUrlXXX(url, mx);
420 
421  RequestFlags flags;
422  flags.cachable = true;
423 
424  StoreEntry *e = storeCreateEntry(url, url, flags, Http::METHOD_GET);
425  assert(e);
427  debugs(71, 3, "storeDigestRewrite: url: " << url << " key: " << e->getMD5Text());
428  e->mem_obj->request = req;
429 
430  /* wait for rebuild (if any) to finish */
431  if (sd_state.rebuild_lock) {
432  debugs(71, 2, "storeDigestRewriteStart: waiting for rebuild to finish.");
433  return;
434  }
435 
437 }
438 
439 static void
441 {
442  StoreEntry *e;
443 
449  /* setting public key will mark the old digest entry for removal once unlocked */
450  e->setPublicKey();
451  if (const auto oldEntry = sd_state.publicEntry) {
452  oldEntry->release(true);
453  sd_state.publicEntry = nullptr;
454  oldEntry->unlock("storeDigestRewriteResume");
455  }
456  assert(e->locked());
457  sd_state.publicEntry = e;
458  /* fake reply */
459  HttpReply *rep = new HttpReply;
460  rep->setHeaders(Http::scOkay, "Cache Digest OK",
461  "application/cache-digest", (store_digest->mask_size + sizeof(sd_state.cblock)),
463  debugs(71, 3, "storeDigestRewrite: entry expires on " << rep->expires <<
464  " (" << std::showpos << (int) (rep->expires - squid_curtime) << ")");
465  e->buffer();
466  e->replaceHttpReply(rep);
468  e->flush();
469  eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, sd_state.rewrite_lock, 0.0, 1, false);
470 }
471 
472 /* finishes swap out sequence for the digest; schedules next rewrite */
473 static void
475 {
477  e->complete();
478  e->timestampsSet();
479  debugs(71, 2, "storeDigestRewriteFinish: digest expires at " << e->expires <<
480  " (" << std::showpos << (int) (e->expires - squid_curtime) << ")");
481  /* is this the write order? @?@ */
482  e->mem_obj->unlinkRequest();
485  eventAdd("storeDigestRewriteStart", storeDigestRewriteStart, NULL, (double)
487  /* resume pending Rebuild if any */
488 
491 }
492 
493 /* swaps out one digest "chunk" per invocation; schedules next swap out */
494 static void
496 {
497  StoreEntry *e = static_cast<StoreEntry *>(data);
498  int chunk_size = Config.digest.swapout_chunk_size;
500  assert(e);
501  /* _add_ check that nothing bad happened while we were waiting @?@ @?@ */
502 
503  if (static_cast<uint32_t>(sd_state.rewrite_offset + chunk_size) > store_digest->mask_size)
505 
506  e->append(store_digest->mask + sd_state.rewrite_offset, chunk_size);
507 
508  debugs(71, 3, "storeDigestSwapOutStep: size: " << store_digest->mask_size <<
509  " offset: " << sd_state.rewrite_offset << " chunk: " <<
510  chunk_size << " bytes");
511 
512  sd_state.rewrite_offset += chunk_size;
513 
514  /* are we done ? */
515  if (static_cast<uint32_t>(sd_state.rewrite_offset) >= store_digest->mask_size)
517  else
518  eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, data, 0.0, 1, false);
519 }
520 
521 static void
523 {
524  memset(&sd_state.cblock, 0, sizeof(sd_state.cblock));
533  e->append((char *) &sd_state.cblock, sizeof(sd_state.cblock));
534 }
535 
536 #endif /* USE_CACHE_DIGESTS */
537 
unsigned char bits_per_entry
Definition: PeerDigest.h:34
SQUIDCEXTERN double xpercent(double part, double whole)
Definition: util.c:54
virtual void buffer()
Definition: store.cc:1657
static void storeDigestRebuildStep(void *datanotused)
unsigned char cache_key
Store key.
Definition: forward.h:29
#define EBIT_SET(flag, bit)
Definition: defines.h:105
uint64_t capacity
Definition: CacheDigest.h:57
virtual void flush()
Definition: store.cc:1668
MemObject * mem_obj
Definition: Store.h:213
time_t rewrite_period
Definition: SquidConfig.h:493
static int storeDigestAddable(const StoreEntry *e)
void clear()
reset the digest mask and counters
Definition: CacheDigest.cc:79
const char * url() const
Definition: store.cc:1622
time_t rebuild_period
Definition: SquidConfig.h:492
StoreDigestCBlock cblock
Definition: store_digest.cc:47
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:901
StoreSearchPointer theSearch
Definition: store_digest.cc:51
@ KEY_PRIVATE
Definition: enums.h:102
Definition: SBuf.h:86
StoreEntry * publicEntry
points to the previous store entry with the digest
Definition: store_digest.cc:50
int const char int
Definition: stub_libmem.cc:75
int objectsPerBucket
Definition: SquidConfig.h:267
@ ENTRY_NEGCACHED
Definition: enums.h:112
bool setPublicKey(const KeyScope keyScope=ksDefault)
Definition: store.cc:613
const Version CacheDigestVer
Definition: peer_digest.cc:56
void updateCapacity(uint64_t newCapacity)
changes mask size to fit newCapacity, resets bits to 0
Definition: CacheDigest.cc:86
uint16_t flags
Definition: Store.h:224
static StoreDigestState sd_state
Definition: store_digest.cc:69
time_t expires
Definition: Store.h:218
void replaceHttpReply(const HttpReplyPointer &, const bool andStartWriting=true)
Definition: store.cc:1782
#define DBG_IMPORTANT
Definition: Debug.h:46
void remove(const cache_key *key)
Definition: CacheDigest.cc:151
@ ENTRY_BAD_LENGTH
Definition: enums.h:114
@ ENTRY_SPECIAL
Definition: enums.h:84
@ initCacheDigest
Cache Digest fetching code.
const char * StoreDigestFileName
time_t expires
Definition: HttpReply.h:48
#define NULL
Definition: types.h:166
void cacheDigestReport(CacheDigest *cd, const SBuf &label, StoreEntry *e)
Definition: CacheDigest.cc:256
static void storeDigestRewriteFinish(StoreEntry *e)
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:128
short int required
Definition: PeerDigest.h:21
int bits_per_entry
Definition: SquidConfig.h:491
void storeDigestDel(const StoreEntry *entry)
#define INT_MAX
Definition: types.h:76
#define EBIT_TEST(flag, bit)
Definition: defines.h:107
void const char HLPCB void * data
Definition: stub_helper.cc:16
int unlock(const char *context)
Definition: store.cc:483
static void storeDigestRewriteResume(void)
static size_t inUseCount()
Definition: store.cc:197
store_status_t store_status
Definition: Store.h:236
#define assert(EX)
Definition: assert.h:19
void storeDigestNoteStoreReady(void)
virtual void next(void(callback)(void *cbdata), void *cbdata)=0
char * mask
Definition: CacheDigest.h:58
virtual bool isDone() const =0
virtual StoreEntry * currentItem()=0
uint64_t del_count
Definition: CacheDigest.h:56
StoreSearch * search()
Definition: Controller.cc:215
static EVH storeDigestSwapOutStep
Definition: store_digest.cc:80
@ STORE_OK
Definition: enums.h:50
time_t squid_curtime
Definition: stub_time.cc:17
StoreEntry * storeCreateEntry(const char *url, const char *logUrl, const RequestFlags &flags, const HttpRequestMethod &method)
Definition: store.cc:803
static bool storeDigestResize()
struct SquidConfig::@112 onoff
void storeDigestReport(StoreEntry *e)
void EVH(void *)
Definition: event.h:19
static void storeDigestRebuildResume(void)
virtual uint64_t currentSize() const override
current size
Definition: Controller.cc:177
int rebuild_lock
bucket number
Definition: store_digest.cc:48
virtual uint64_t maxSize() const override
Definition: Controller.cc:163
void complete()
Definition: store.cc:1078
void add(const cache_key *key)
Definition: CacheDigest.cc:107
struct SquidConfig::@120 digest
short int current
Definition: PeerDigest.h:20
bool timestampsSet()
Definition: store.cc:1449
static uint64_t storeDigestCalcCap()
calculates digest capacity
Definition: store_digest.cc:86
void unlinkRequest()
Definition: MemObject.h:55
static HttpRequest * FromUrlXXX(const char *url, const MasterXaction::Pointer &, const HttpRequestMethod &method=Http::METHOD_GET)
Definition: HttpRequest.cc:546
uint64_t swap_file_sz
Definition: Store.h:222
bool contains(const cache_key *key) const
Definition: CacheDigest.cc:93
int refreshCheckDigest(const StoreEntry *entry, time_t delta)
Definition: refresh.cc:620
CacheDigest * store_digest
int digest_generation
Definition: SquidConfig.h:314
int64_t maxObjectSize
Definition: SquidConfig.h:269
int64_t avgObjectSize
Definition: SquidConfig.h:268
unsigned char hash_func_count
Definition: PeerDigest.h:35
int rebuild_chunk_percentage
Definition: SquidConfig.h:495
int store_hash_buckets
@ RELEASE_REQUEST
prohibits making the key public
Definition: enums.h:98
virtual void append(char const *, int)
Appends a c-string to existing packed data.
Definition: store.cc:849
struct SquidConfig::@110 Store
void setHeaders(Http::StatusCode status, const char *reason, const char *ctype, int64_t clen, time_t lmt, time_t expires)
Definition: HttpReply.cc:168
static void storeDigestRebuildFinish(void)
int locked() const
Definition: Store.h:136
uint32_t mask_size
Definition: CacheDigest.h:59
@ scOkay
Definition: StatusCode.h:26
void RegisterAction(char const *action, char const *desc, OBJH *handler, int pw_req_flag, int atomic)
Definition: Registration.cc:16
@ METHOD_GET
Definition: MethodType.h:25
static void storeDigestCBlockSwapOut(StoreEntry *e)
uint64_t count
Definition: CacheDigest.h:55
char * internalLocalUri(const char *dir, const SBuf &name)
Definition: internal.cc:130
size_t swapout_chunk_size
Definition: SquidConfig.h:494
static StoreDigestStats sd_stats
Definition: store_digest.cc:70
SQUIDCEXTERN int xpercentInt(double part, double whole)
Definition: util.c:60
HttpRequestPointer request
Definition: MemObject.h:188
int CacheDigestHashFuncCount
const char * getMD5Text() const
Definition: store.cc:205
static void storeDigestRewriteStart(void *)
void eventAdd(const char *name, EVH *func, void *arg, double when, int weight, bool cbdata)
Definition: event.cc:109
void storeDigestInit(void)
class SquidConfig Config
Definition: SquidConfig.cc:12
static void storeDigestRebuildStart(void *datanotused)
static void storeDigestAdd(const StoreEntry *)
StoreEntry * rewrite_lock
points to store entry with the digest
Definition: store_digest.cc:49
Controller & Root()
safely access controller singleton
Definition: Controller.cc:938

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors