/*
- * DEBUG: section 71 Store Digest Manager
- * AUTHOR: Alex Rousskov
- *
- * SQUID Web Proxy Cache http://www.squid-cache.org/
- * ----------------------------------------------------------
- *
- * Squid is the result of efforts by numerous individuals from
- * the Internet community; see the CONTRIBUTORS file for full
- * details. Many organizations have provided support for Squid's
- * development; see the SPONSORS file for full details. Squid is
- * Copyrighted (C) 2001 by the Regents of the University of
- * California; see the COPYRIGHT file for full details. Squid
- * incorporates software developed and/or copyrighted by other
- * sources; see the CREDITS file for full details.
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
+ * Copyright (C) 1996-2023 The Squid Software Foundation and contributors
*
+ * Squid software is distributed under GPLv2+ license and includes
+ * contributions from numerous individuals and organizations.
+ * Please see the COPYING and CONTRIBUTORS files for details.
*/
+/* DEBUG: section 71 Store Digest Manager */
+
/*
* TODO: We probably do not track all the cases when
* storeDigestNoteStoreReady() must be called; this may prevent
*/
#include "squid.h"
-#include "Debug.h"
+#include "debug/Stream.h"
#include "event.h"
#include "globals.h"
#include "mgr/Registration.h"
#include "PeerDigest.h"
#include "refresh.h"
#include "SquidConfig.h"
-#include "SquidTime.h"
#include "Store.h"
#include "StoreSearch.h"
+#include "util.h"
-#if HAVE_MATH_H
-#include <math.h>
-#endif
+#include <cmath>
/*
* local types
class StoreDigestState
{
-
public:
StoreDigestCBlock cblock;
- int rebuild_lock; /* bucket number */
- StoreEntry * rewrite_lock; /* points to store entry with the digest */
+ int rebuild_lock = 0; ///< bucket number
+ StoreEntry * rewrite_lock = nullptr; ///< points to store entry with the digest
+ StoreEntry * publicEntry = nullptr; ///< points to the previous store entry with the digest
StoreSearchPointer theSearch;
- int rewrite_offset;
- int rebuild_count;
- int rewrite_count;
+ int rewrite_offset = 0;
+ int rebuild_count = 0;
+ int rewrite_count = 0;
};
-typedef struct {
- int del_count; /* #store entries deleted from store_digest */
- int del_lost_count; /* #store entries not found in store_digest on delete */
- int add_count; /* #store entries accepted to store_digest */
- int add_coll_count; /* #accepted entries that collided with existing ones */
- int rej_count; /* #store entries not accepted to store_digest */
- int rej_coll_count; /* #not accepted entries that collided with existing ones */
-} StoreDigestStats;
+class StoreDigestStats
+{
+public:
+ int del_count = 0; /* #store entries deleted from store_digest */
+ int del_lost_count = 0; /* #store entries not found in store_digest on delete */
+ int add_count = 0; /* #store entries accepted to store_digest */
+ int add_coll_count = 0; /* #accepted entries that collided with existing ones */
+ int rej_count = 0; /* #store entries not accepted to store_digest */
+ int rej_coll_count = 0; /* #not accepted entries that collided with existing ones */
+};
/* local vars */
static StoreDigestState sd_state;
static void storeDigestRewriteFinish(StoreEntry * e);
static EVH storeDigestSwapOutStep;
static void storeDigestCBlockSwapOut(StoreEntry * e);
-static int storeDigestCalcCap(void);
-static int storeDigestResize(void);
static void storeDigestAdd(const StoreEntry *);
-#endif /* USE_CACHE_DIGESTS */
-
-static void
-storeDigestRegisterWithCacheManager(void)
+/// calculates digest capacity
+static uint64_t
+storeDigestCalcCap()
{
- Mgr::RegisterAction("store_digest", "Store Digest", storeDigestReport, 0, 1);
-}
+ /*
+ * To-Do: Bloom proved that the optimal filter utilization is 50% (half of
+ * the bits are off). However, we do not have a formula to calculate the
+ * number of _entries_ we want to pre-allocate for.
+ */
+ const uint64_t hi_cap = Store::Root().maxSize() / Config.Store.avgObjectSize;
+ const uint64_t lo_cap = 1 + Store::Root().currentSize() / Config.Store.avgObjectSize;
+ const uint64_t e_count = StoreEntry::inUseCount();
+ uint64_t cap = e_count ? e_count : hi_cap;
+ debugs(71, 2, "have: " << e_count << ", want " << cap <<
+ " entries; limits: [" << lo_cap << ", " << hi_cap << "]");
-/*
- * PUBLIC FUNCTIONS
- */
+ if (cap < lo_cap)
+ cap = lo_cap;
+
+ /* do not enforce hi_cap limit, average-based estimation may be wrong
+ *if (cap > hi_cap)
+ * cap = hi_cap;
+ */
+
+ // Bug 4534: we still have to set an upper-limit at some reasonable value though.
+ // this matches cacheDigestCalcMaskSize doing (cap*bpe)+7 < INT_MAX
+ const uint64_t absolute_max = (INT_MAX -8) / Config.digest.bits_per_entry;
+ if (cap > absolute_max) {
+ static time_t last_loud = 0;
+ if (last_loud < squid_curtime - 86400) {
+ debugs(71, DBG_IMPORTANT, "WARNING: Cache Digest cannot store " << cap << " entries. Limiting to " << absolute_max);
+ last_loud = squid_curtime;
+ } else {
+ debugs(71, 3, "WARNING: Cache Digest cannot store " << cap << " entries. Limiting to " << absolute_max);
+ }
+ cap = absolute_max;
+ }
+
+ return cap;
+}
+#endif /* USE_CACHE_DIGESTS */
void
storeDigestInit(void)
{
- storeDigestRegisterWithCacheManager();
+ Mgr::RegisterAction("store_digest", "Store Digest", storeDigestReport, 0, 1);
#if USE_CACHE_DIGESTS
- const int cap = storeDigestCalcCap();
-
if (!Config.onoff.digest_generation) {
- store_digest = NULL;
+ store_digest = nullptr;
debugs(71, 3, "Local cache digest generation disabled");
return;
}
- store_digest = cacheDigestCreate(cap, Config.digest.bits_per_entry);
+ const uint64_t cap = storeDigestCalcCap();
+ store_digest = new CacheDigest(cap, Config.digest.bits_per_entry);
debugs(71, DBG_IMPORTANT, "Local cache digest enabled; rebuild/rewrite every " <<
(int) Config.digest.rebuild_period << "/" <<
(int) Config.digest.rewrite_period << " sec");
- memset(&sd_state, 0, sizeof(sd_state));
+ sd_state = StoreDigestState();
#else
store_digest = NULL;
debugs(71, 3, "Local cache digest is 'off'");
#if USE_CACHE_DIGESTS
if (Config.onoff.digest_generation) {
- storeDigestRebuildStart(NULL);
- storeDigestRewriteStart(NULL);
+ storeDigestRebuildStart(nullptr);
+ storeDigestRewriteStart(nullptr);
}
#endif
debugs(71, 6, "storeDigestDel: checking entry, key: " << entry->getMD5Text());
if (!EBIT_TEST(entry->flags, KEY_PRIVATE)) {
- if (!cacheDigestTest(store_digest, (const cache_key *)entry->key)) {
+ if (!store_digest->contains(static_cast<const cache_key *>(entry->key))) {
++sd_stats.del_lost_count;
debugs(71, 6, "storeDigestDel: lost entry, key: " << entry->getMD5Text() << " url: " << entry->url() );
} else {
++sd_stats.del_count;
- cacheDigestDel(store_digest, (const cache_key *)entry->key);
+ store_digest->remove(static_cast<const cache_key *>(entry->key));
debugs(71, 6, "storeDigestDel: deled entry, key: " << entry->getMD5Text());
}
}
+#else
+ (void)entry;
#endif //USE_CACHE_DIGESTS
}
}
if (store_digest) {
- cacheDigestReport(store_digest, "store", e);
+ static const SBuf label("store");
+ cacheDigestReport(store_digest, label, e);
storeAppendPrintf(e, "\t added: %d rejected: %d ( %.2f %%) del-ed: %d\n",
sd_stats.add_count,
sd_stats.rej_count,
} else {
storeAppendPrintf(e, "store digest: disabled.\n");
}
-
+#else
+ (void)e;
#endif //USE_CACHE_DIGESTS
}
/* check various entry flags (mimics StoreEntry::checkCachable XXX) */
- if (!EBIT_TEST(e->flags, ENTRY_CACHABLE)) {
- debugs(71, 6, "storeDigestAddable: NO: not cachable");
- return 0;
- }
-
if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
debugs(71, 6, "storeDigestAddable: NO: private key");
return 0;
if (storeDigestAddable(entry)) {
++sd_stats.add_count;
- if (cacheDigestTest(store_digest, (const cache_key *)entry->key))
+ if (store_digest->contains(static_cast<const cache_key *>(entry->key)))
++sd_stats.add_coll_count;
- cacheDigestAdd(store_digest, (const cache_key *)entry->key);
+ store_digest->add(static_cast<const cache_key *>(entry->key));
debugs(71, 6, "storeDigestAdd: added entry, key: " << entry->getMD5Text());
} else {
++sd_stats.rej_count;
- if (cacheDigestTest(store_digest, (const cache_key *)entry->key))
+ if (store_digest->contains(static_cast<const cache_key *>(entry->key)))
++sd_stats.rej_coll_count;
}
}
/* rebuilds digest from scratch */
static void
-storeDigestRebuildStart(void *datanotused)
+storeDigestRebuildStart(void *)
{
assert(store_digest);
/* prevent overlapping if rebuild schedule is too tight */
storeDigestRebuildResume();
}
+/// \returns true if we actually resized the digest
+static bool
+storeDigestResize()
+{
+ const uint64_t cap = storeDigestCalcCap();
+ assert(store_digest);
+ uint64_t diff;
+ if (cap > store_digest->capacity)
+ diff = cap - store_digest->capacity;
+ else
+ diff = store_digest->capacity - cap;
+ debugs(71, 2, store_digest->capacity << " -> " << cap << "; change: " <<
+ diff << " (" << xpercentInt(diff, store_digest->capacity) << "%)" );
+ /* avoid minor adjustments */
+
+ if (diff <= store_digest->capacity / 10) {
+ debugs(71, 2, "small change, will not resize.");
+ return false;
+ } else {
+ debugs(71, 2, "big change, resizing.");
+ store_digest->updateCapacity(cap);
+ }
+ return true;
+}
+
/* called be Rewrite to push Rebuild forward */
static void
storeDigestRebuildResume(void)
{
assert(sd_state.rebuild_lock);
assert(!sd_state.rewrite_lock);
- sd_state.theSearch = Store::Root().search(NULL, NULL);
+ sd_state.theSearch = Store::Root().search();
/* resize or clear */
if (!storeDigestResize())
- cacheDigestClear(store_digest); /* not clean()! */
+ store_digest->clear(); /* not clean()! */
- memset(&sd_stats, 0, sizeof(sd_stats));
+ sd_stats = StoreDigestStats();
- eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, NULL, 0.0, 1);
+ eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, nullptr, 0.0, 1);
}
/* finishes swap out sequence for the digest; schedules next rebuild */
sd_state.rebuild_lock = 0;
++sd_state.rebuild_count;
debugs(71, 2, "storeDigestRebuildFinish: done.");
- eventAdd("storeDigestRebuildStart", storeDigestRebuildStart, NULL, (double)
+ eventAdd("storeDigestRebuildStart", storeDigestRebuildStart, nullptr, (double)
Config.digest.rebuild_period, 1);
/* resume pending Rewrite if any */
/* recalculate a few hash buckets per invocation; schedules next step */
static void
-storeDigestRebuildStep(void *datanotused)
+storeDigestRebuildStep(void *)
{
/* TODO: call Store::Root().size() to determine this.. */
int count = Config.Store.objectsPerBucket * (int) ceil((double) store_hash_buckets *
if (sd_state.theSearch->isDone())
storeDigestRebuildFinish();
else
- eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, NULL, 0.0, 1);
+ eventAdd("storeDigestRebuildStep", storeDigestRebuildStep, nullptr, 0.0, 1);
}
/* starts swap out sequence for the digest */
static void
-storeDigestRewriteStart(void *datanotused)
+storeDigestRewriteStart(void *)
{
- RequestFlags flags;
- char *url;
- StoreEntry *e;
-
assert(store_digest);
/* prevent overlapping if rewrite schedule is too tight */
}
debugs(71, 2, "storeDigestRewrite: start rewrite #" << sd_state.rewrite_count + 1);
- /* make new store entry */
- url = internalLocalUri("/squid-internal-periodic/", StoreDigestFileName);
- flags.cachable = true;
- e = storeCreateEntry(url, url, flags, Http::METHOD_GET);
+
+ const char *url = internalLocalUri("/squid-internal-periodic/", SBuf(StoreDigestFileName));
+ const auto mx = MasterXaction::MakePortless<XactionInitiator::initCacheDigest>();
+ auto req = HttpRequest::FromUrlXXX(url, mx);
+
+ RequestFlags flags;
+ flags.cachable.support(); // prevent RELEASE_REQUEST in storeCreateEntry()
+
+ StoreEntry *e = storeCreateEntry(url, url, flags, Http::METHOD_GET);
assert(e);
sd_state.rewrite_lock = e;
debugs(71, 3, "storeDigestRewrite: url: " << url << " key: " << e->getMD5Text());
- HttpRequest *req = HttpRequest::CreateFromUrl(url);
- e->mem_obj->request = HTTPMSGLOCK(req);
- /* wait for rebuild (if any) to finish */
+ e->mem_obj->request = req;
+ /* wait for rebuild (if any) to finish */
if (sd_state.rebuild_lock) {
debugs(71, 2, "storeDigestRewriteStart: waiting for rebuild to finish.");
return;
e = sd_state.rewrite_lock;
sd_state.rewrite_offset = 0;
EBIT_SET(e->flags, ENTRY_SPECIAL);
- /* setting public key will purge old digest entry if any */
+ /* setting public key will mark the old digest entry for removal once unlocked */
e->setPublicKey();
+ if (const auto oldEntry = sd_state.publicEntry) {
+ oldEntry->release(true);
+ sd_state.publicEntry = nullptr;
+ oldEntry->unlock("storeDigestRewriteResume");
+ }
+ assert(e->locked());
+ sd_state.publicEntry = e;
/* fake reply */
HttpReply *rep = new HttpReply;
- rep->setHeaders(HTTP_OK, "Cache Digest OK",
+ rep->setHeaders(Http::scOkay, "Cache Digest OK",
"application/cache-digest", (store_digest->mask_size + sizeof(sd_state.cblock)),
squid_curtime, (squid_curtime + Config.digest.rewrite_period) );
debugs(71, 3, "storeDigestRewrite: entry expires on " << rep->expires <<
" (" << std::showpos << (int) (e->expires - squid_curtime) << ")");
/* is this the write order? @?@ */
e->mem_obj->unlinkRequest();
- e->unlock();
- sd_state.rewrite_lock = NULL;
+ sd_state.rewrite_lock = nullptr;
++sd_state.rewrite_count;
- eventAdd("storeDigestRewriteStart", storeDigestRewriteStart, NULL, (double)
+ eventAdd("storeDigestRewriteStart", storeDigestRewriteStart, nullptr, (double)
Config.digest.rewrite_period, 1);
/* resume pending Rebuild if any */
assert(e);
/* _add_ check that nothing bad happened while we were waiting @?@ @?@ */
- if (sd_state.rewrite_offset + chunk_size > store_digest->mask_size)
+ if (static_cast<uint32_t>(sd_state.rewrite_offset + chunk_size) > store_digest->mask_size)
chunk_size = store_digest->mask_size - sd_state.rewrite_offset;
e->append(store_digest->mask + sd_state.rewrite_offset, chunk_size);
sd_state.rewrite_offset += chunk_size;
/* are we done ? */
- if (sd_state.rewrite_offset >= store_digest->mask_size)
+ if (static_cast<uint32_t>(sd_state.rewrite_offset) >= store_digest->mask_size)
storeDigestRewriteFinish(e);
else
eventAdd("storeDigestSwapOutStep", storeDigestSwapOutStep, data, 0.0, 1, false);
sd_state.cblock.count = htonl(store_digest->count);
sd_state.cblock.del_count = htonl(store_digest->del_count);
sd_state.cblock.mask_size = htonl(store_digest->mask_size);
- sd_state.cblock.bits_per_entry = (unsigned char)
- Config.digest.bits_per_entry;
+ sd_state.cblock.bits_per_entry = Config.digest.bits_per_entry;
sd_state.cblock.hash_func_count = (unsigned char) CacheDigestHashFuncCount;
e->append((char *) &sd_state.cblock, sizeof(sd_state.cblock));
}
-/* calculates digest capacity */
-static int
-storeDigestCalcCap(void)
-{
- /*
- * To-Do: Bloom proved that the optimal filter utilization is 50% (half of
- * the bits are off). However, we do not have a formula to calculate the
- * number of _entries_ we want to pre-allocate for.
- */
- const int hi_cap = Store::Root().maxSize() / Config.Store.avgObjectSize;
- const int lo_cap = 1 + Store::Root().currentSize() / Config.Store.avgObjectSize;
- const int e_count = StoreEntry::inUseCount();
- int cap = e_count ? e_count :hi_cap;
- debugs(71, 2, "storeDigestCalcCap: have: " << e_count << ", want " << cap <<
- " entries; limits: [" << lo_cap << ", " << hi_cap << "]");
-
- if (cap < lo_cap)
- cap = lo_cap;
-
- /* do not enforce hi_cap limit, average-based estimation may be wrong
- *if (cap > hi_cap)
- * cap = hi_cap;
- */
- return cap;
-}
-
-/* returns true if we actually resized the digest */
-static int
-storeDigestResize(void)
-{
- const int cap = storeDigestCalcCap();
- int diff;
- assert(store_digest);
- diff = abs(cap - store_digest->capacity);
- debugs(71, 2, "storeDigestResize: " <<
- store_digest->capacity << " -> " << cap << "; change: " <<
- diff << " (" << xpercentInt(diff, store_digest->capacity) << "%)" );
- /* avoid minor adjustments */
-
- if (diff <= store_digest->capacity / 10) {
- debugs(71, 2, "storeDigestResize: small change, will not resize.");
- return 0;
- } else {
- debugs(71, 2, "storeDigestResize: big change, resizing.");
- cacheDigestChangeCap(store_digest, cap);
- return 1;
- }
-}
-
#endif /* USE_CACHE_DIGESTS */
+