You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by zw...@apache.org on 2020/04/17 23:13:39 UTC
[trafficserver] 01/05: Refactor the cache_promote policies
This is an automated email from the ASF dual-hosted git repository.
zwoop pushed a commit to branch 9.0.x
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit f4ed4c43a78bb48f1818d5da3f4f828068c7f526
Author: Leif Hedstrom <zw...@apache.org>
AuthorDate: Wed Feb 26 13:32:29 2020 -0700
Refactor the cache_promote policies
(cherry picked from commit 47d4435dc99c7111d198f94462e79a6356481c46)
---
plugins/cache_promote/Makefile.inc | 5 +-
plugins/cache_promote/cache_promote.cc | 517 +--------------------------------
plugins/cache_promote/chance_policy.h | 76 +++++
plugins/cache_promote/config.cc | 92 ++++++
plugins/cache_promote/lru_policy.cc | 185 ++++++++++++
plugins/cache_promote/lru_policy.h | 124 ++++++++
plugins/cache_promote/policy.cc | 56 ++++
plugins/cache_promote/policy.h | 96 ++++++
8 files changed, 636 insertions(+), 515 deletions(-)
diff --git a/plugins/cache_promote/Makefile.inc b/plugins/cache_promote/Makefile.inc
index a0029d3..103eb8b 100644
--- a/plugins/cache_promote/Makefile.inc
+++ b/plugins/cache_promote/Makefile.inc
@@ -17,4 +17,7 @@
pkglib_LTLIBRARIES += cache_promote/cache_promote.la
cache_promote_cache_promote_la_SOURCES = \
- cache_promote/cache_promote.cc
+ cache_promote/cache_promote.cc \
+ cache_promote/config.cc \
+ cache_promote/policy.cc \
+ cache_promote/lru_policy.cc
diff --git a/plugins/cache_promote/cache_promote.cc b/plugins/cache_promote/cache_promote.cc
index 4a3aab5..06e1ef6 100644
--- a/plugins/cache_promote/cache_promote.cc
+++ b/plugins/cache_promote/cache_promote.cc
@@ -18,525 +18,14 @@
#include <cstdio>
#include <cstring>
-#include <unistd.h>
-#include <getopt.h>
-#include <cstdlib>
-#include <ctime>
-#include <openssl/sha.h>
-
-#include <string>
-#include <unordered_map>
-#include <list>
-
-#include "tscore/ink_config.h"
-#include "tscore/ink_defs.h"
-#include "tscore/BufferWriter.h"
#include "ts/ts.h"
#include "ts/remap.h"
-#include "tscore/ink_config.h"
-
-#define MINIMUM_BUCKET_SIZE 10
-#define MAX_STAT_LENGTH (1 << 8)
-
-static const char *PLUGIN_NAME = "cache_promote";
-
-//////////////////////////////////////////////////////////////////////////////////////////////
-// Note that all options for all policies has to go here. Not particularly pretty...
-//
-static const struct option longopt[] = {
- {const_cast<char *>("policy"), required_argument, nullptr, 'p'},
- // This is for both Chance and LRU (optional) policy
- {const_cast<char *>("sample"), required_argument, nullptr, 's'},
- // For the LRU policy
- {const_cast<char *>("buckets"), required_argument, nullptr, 'b'},
- {const_cast<char *>("stats-enable-with-id"), required_argument, nullptr, 'e'},
- {const_cast<char *>("hits"), required_argument, nullptr, 'h'},
- // EOF
- {nullptr, no_argument, nullptr, '\0'},
-};
-
-//////////////////////////////////////////////////////////////////////////////////////////////
-// Abstract base class for all policies.
-//
-class PromotionPolicy
-{
-public:
- PromotionPolicy()
- {
- // This doesn't have to be perfect, since this is just chance sampling.
- // coverity[dont_call]
- srand48(static_cast<long>(time(nullptr)));
- }
-
- void
- setSample(char *s)
- {
- _sample = strtof(s, nullptr) / 100.0;
- }
-
- float
- getSample() const
- {
- return _sample;
- }
-
- bool
- doSample() const
- {
- if (_sample > 0) {
- // coverity[dont_call]
- double r = drand48();
-
- if (_sample > r) {
- TSDebug(PLUGIN_NAME, "checking sampling, is %f > %f? Yes!", _sample, r);
- } else {
- TSDebug(PLUGIN_NAME, "checking sampling, is %f > %f? No!", _sample, r);
- return false;
- }
- }
- return true;
- }
-
- int
- create_stat(std::string_view name, std::string_view remap_identifier)
- {
- int stat_id = -1;
- ts::LocalBufferWriter<MAX_STAT_LENGTH> stat_name;
- stat_name.reset().clip(1);
- stat_name.print("plugin.{}.{}.{}", PLUGIN_NAME, remap_identifier, name);
- stat_name.extend(1).write('\0');
-
- if (TS_ERROR == TSStatFindName(stat_name.data(), &stat_id)) {
- stat_id = TSStatCreate(stat_name.data(), TS_RECORDDATATYPE_INT, TS_STAT_NON_PERSISTENT, TS_STAT_SYNC_SUM);
- if (TS_ERROR == stat_id) {
- TSDebug(PLUGIN_NAME, "Error creating stat_name: %s", stat_name.data());
- } else {
- TSDebug(PLUGIN_NAME, "Created stat_name: %s, stat_id: %d", stat_name.data(), stat_id);
- }
- }
-
- return stat_id;
- }
- void
- decrementStat(const int stat, const int amount)
- {
- if (stats_enabled) {
- TSStatIntDecrement(stat, amount);
- }
- }
-
- void
- incrementStat(const int stat, const int amount)
- {
- if (stats_enabled) {
- TSStatIntIncrement(stat, amount);
- }
- }
-
- virtual ~PromotionPolicy() = default;
- ;
-
- virtual bool
- parseOption(int opt, char *optarg)
- {
- return false;
- }
-
- // These are pure virtual
- virtual bool doPromote(TSHttpTxn txnp) = 0;
- virtual const char *policyName() const = 0;
- virtual void usage() const = 0;
- virtual bool stats_add(const char *remap_id) = 0;
-
- // when true stats are incremented.
- bool stats_enabled = false;
- int cache_hits_id = -1;
- int promoted_id = -1;
- int total_requests_id = -1;
-
-private:
- float _sample = 0.0;
-};
-
-//////////////////////////////////////////////////////////////////////////////////////////////
-// This is the simplest of all policies, just give each request a (small)
-// percentage chance to be promoted to cache.
-//
-class ChancePolicy : public PromotionPolicy
-{
-public:
- bool doPromote(TSHttpTxn /* txnp ATS_UNUSED */) override
- {
- TSDebug(PLUGIN_NAME, "ChancePolicy::doPromote(%f)", getSample());
-
- incrementStat(promoted_id, 1);
-
- return true;
- }
-
- void
- usage() const override
- {
- TSError("[%s] Usage: @plugin=%s.so @pparam=--policy=chance @pparam=--sample=<x>%%", PLUGIN_NAME, PLUGIN_NAME);
- }
-
- const char *
- policyName() const override
- {
- return "chance";
- }
-
- bool
- stats_add(const char *remap_id) override
- {
- std::string_view remap_identifier = remap_id;
- const std::tuple<std::string_view, int *> stats[] = {
- {"cache_hits", &cache_hits_id},
- {"promoted", &promoted_id},
- {"total_requests", &total_requests_id},
- };
-
- if (nullptr == remap_id) {
- TSError("[%s] no remap identifier specified for for stats, no stats will be used", PLUGIN_NAME);
- return false;
- }
-
- for (int ii = 0; ii < 3; ii++) {
- std::string_view name = std::get<0>(stats[ii]);
- int *id = std::get<1>(stats[ii]);
- if ((*(id) = create_stat(name, remap_identifier)) == TS_ERROR) {
- return false;
- }
- }
-
- return true;
- }
-};
-
-//////////////////////////////////////////////////////////////////////////////////////////////
-// The LRU based policy keeps track of <bucket> number of URLs, with a counter for each slot.
-// Objects are not promoted unless the counter reaches <hits> before it gets evicted. An
-// optional <chance> parameter can be used to sample hits, this can reduce contention and
-// churning in the LRU as well.
-//
-class LRUHash
-{
- friend struct LRUHashHasher;
-
-public:
- LRUHash() { TSDebug(PLUGIN_NAME, "In LRUHash()"); }
- ~LRUHash() { TSDebug(PLUGIN_NAME, "In ~LRUHash()"); }
- LRUHash &
- operator=(const LRUHash &h)
- {
- TSDebug(PLUGIN_NAME, "copying an LRUHash object");
- if (this != &h) {
- memcpy(_hash, h._hash, sizeof(_hash));
- }
- return *this;
- }
-
- void
- init(char *data, int len)
- {
- SHA_CTX sha;
-
- SHA1_Init(&sha);
- SHA1_Update(&sha, data, len);
- SHA1_Final(_hash, &sha);
- }
-private:
- u_char _hash[SHA_DIGEST_LENGTH];
-};
-
-struct LRUHashHasher {
- bool
- operator()(const LRUHash *s1, const LRUHash *s2) const
- {
- return 0 == memcmp(s1->_hash, s2->_hash, sizeof(s2->_hash));
- }
-
- size_t
- operator()(const LRUHash *s) const
- {
- return *(reinterpret_cast<const size_t *>(s->_hash)) ^ *(reinterpret_cast<const size_t *>(s->_hash + 9));
- }
-};
-
-typedef std::pair<LRUHash, unsigned> LRUEntry;
-using LRUList = std::list<LRUEntry>;
-typedef std::unordered_map<const LRUHash *, LRUList::iterator, LRUHashHasher, LRUHashHasher> LRUMap;
-
-static LRUEntry NULL_LRU_ENTRY; // Used to create an "empty" new LRUEntry
-
-class LRUPolicy : public PromotionPolicy
-{
-public:
- LRUPolicy() : PromotionPolicy(), _lock(TSMutexCreate()) {}
- ~LRUPolicy() override
- {
- TSDebug(PLUGIN_NAME, "deleting LRUPolicy object");
- TSMutexLock(_lock);
-
- _map.clear();
- _list.clear();
- _list_size = 0;
- _freelist.clear();
- _freelist_size = 0;
-
- TSMutexUnlock(_lock);
- TSMutexDestroy(_lock);
- }
-
- bool
- parseOption(int opt, char *optarg) override
- {
- switch (opt) {
- case 'b':
- _buckets = static_cast<unsigned>(strtol(optarg, nullptr, 10));
- if (_buckets < MINIMUM_BUCKET_SIZE) {
- TSError("%s: Enforcing minimum LRU bucket size of %d", PLUGIN_NAME, MINIMUM_BUCKET_SIZE);
- TSDebug(PLUGIN_NAME, "Enforcing minimum bucket size of %d", MINIMUM_BUCKET_SIZE);
- _buckets = MINIMUM_BUCKET_SIZE;
- }
- break;
- case 'h':
- _hits = static_cast<unsigned>(strtol(optarg, nullptr, 10));
- break;
- default:
- // All other options are unsupported for this policy
- return false;
- }
-
- // This doesn't have to be perfect, since this is just chance sampling.
- // coverity[dont_call]
- srand48(static_cast<long>(time(nullptr)) ^ static_cast<long>(getpid()) ^ static_cast<long>(getppid()));
-
- return true;
- }
-
- bool
- doPromote(TSHttpTxn txnp) override
- {
- LRUHash hash;
- LRUMap::iterator map_it;
- char *url = nullptr;
- int url_len = 0;
- bool ret = false;
- TSMBuffer request;
- TSMLoc req_hdr;
-
- if (TS_SUCCESS == TSHttpTxnClientReqGet(txnp, &request, &req_hdr)) {
- TSMLoc c_url = TS_NULL_MLOC;
-
- // Get the cache key URL (for now), since this has better lookup behavior when using
- // e.g. the cachekey plugin.
- if (TS_SUCCESS == TSUrlCreate(request, &c_url)) {
- if (TS_SUCCESS == TSHttpTxnCacheLookupUrlGet(txnp, request, c_url)) {
- url = TSUrlStringGet(request, c_url, &url_len);
- TSHandleMLocRelease(request, TS_NULL_MLOC, c_url);
- }
- }
- TSHandleMLocRelease(request, TS_NULL_MLOC, req_hdr);
- }
-
- // Generally shouldn't happen ...
- if (!url) {
- return false;
- }
-
- TSDebug(PLUGIN_NAME, "LRUPolicy::doPromote(%.*s%s)", url_len > 100 ? 100 : url_len, url, url_len > 100 ? "..." : "");
- hash.init(url, url_len);
- TSfree(url);
-
- // We have to hold the lock across all list and hash access / updates
- TSMutexLock(_lock);
-
- map_it = _map.find(&hash);
- if (_map.end() != map_it) {
- // We have an entry in the LRU
- TSAssert(_list_size > 0); // mismatch in the LRUs hash and list, shouldn't happen
- incrementStat(lru_hit_id, 1);
- if (++(map_it->second->second) >= _hits) {
- // Promoted! Cleanup the LRU, and signal success. Save the promoted entry on the freelist.
- TSDebug(PLUGIN_NAME, "saving the LRUEntry to the freelist");
- _freelist.splice(_freelist.begin(), _list, map_it->second);
- ++_freelist_size;
- --_list_size;
- _map.erase(map_it->first);
- incrementStat(promoted_id, 1);
- incrementStat(freelist_size_id, 1);
- decrementStat(lru_size_id, 1);
- ret = true;
- } else {
- // It's still not promoted, make sure it's moved to the front of the list
- TSDebug(PLUGIN_NAME, "still not promoted, got %d hits so far", map_it->second->second);
- _list.splice(_list.begin(), _list, map_it->second);
- }
- } else {
- // New LRU entry for the URL, try to repurpose the list entry as much as possible
- incrementStat(lru_miss_id, 1);
- if (_list_size >= _buckets) {
- TSDebug(PLUGIN_NAME, "repurposing last LRUHash entry");
- _list.splice(_list.begin(), _list, --_list.end());
- _map.erase(&(_list.begin()->first));
- incrementStat(lru_vacated_id, 1);
- } else if (_freelist_size > 0) {
- TSDebug(PLUGIN_NAME, "reusing LRUEntry from freelist");
- _list.splice(_list.begin(), _freelist, _freelist.begin());
- --_freelist_size;
- ++_list_size;
- incrementStat(lru_size_id, 1);
- decrementStat(freelist_size_id, 1);
- } else {
- TSDebug(PLUGIN_NAME, "creating new LRUEntry");
- _list.push_front(NULL_LRU_ENTRY);
- ++_list_size;
- incrementStat(lru_size_id, 1);
- }
- // Update the "new" LRUEntry and add it to the hash
- _list.begin()->first = hash;
- _list.begin()->second = 1;
- _map[&(_list.begin()->first)] = _list.begin();
- }
-
- TSMutexUnlock(_lock);
-
- return ret;
- }
-
- void
- usage() const override
- {
- TSError("[%s] Usage: @plugin=%s.so @pparam=--policy=lru @pparam=--buckets=<n> --hits=<m> --sample=<x>", PLUGIN_NAME,
- PLUGIN_NAME);
- }
-
- const char *
- policyName() const override
- {
- return "LRU";
- }
-
- bool
- stats_add(const char *remap_id) override
- {
- std::string_view remap_identifier = remap_id;
- const std::tuple<std::string_view, int *> stats[] = {
- {"cache_hits", &cache_hits_id}, {"freelist_size", &freelist_size_id},
- {"lru_size", &lru_size_id}, {"lru_hit", &lru_hit_id},
- {"lru_miss", &lru_miss_id}, {"lru_vacated", &lru_vacated_id},
- {"promoted", &promoted_id}, {"total_requests", &total_requests_id},
- };
-
- if (nullptr == remap_id) {
- TSError("[%s] no remap identifier specified for for stats, no stats will be used", PLUGIN_NAME);
- return false;
- }
-
- for (int ii = 0; ii < 8; ii++) {
- std::string_view name = std::get<0>(stats[ii]);
- int *id = std::get<1>(stats[ii]);
- if ((*(id) = create_stat(name, remap_identifier)) == TS_ERROR) {
- return false;
- }
- }
-
- return true;
- }
-
-private:
- unsigned _buckets = 1000;
- unsigned _hits = 10;
- // For the LRU. Note that we keep track of the List sizes, because some versions fo STL have broken
- // implementations of size(), making them obsessively slow on calling ::size().
- TSMutex _lock;
- LRUMap _map;
- LRUList _list, _freelist;
- size_t _list_size = 0, _freelist_size = 0;
-
- // internal stats ids
- int freelist_size_id = -1;
- int lru_size_id = -1;
- int lru_hit_id = -1;
- int lru_miss_id = -1;
- int lru_vacated_id = -1;
- int promoted_id = -1;
-};
-
-//////////////////////////////////////////////////////////////////////////////////////////////
-// This holds the configuration for a remap rule, as well as parses the configurations.
-//
-class PromotionConfig
-{
-public:
- PromotionConfig() = default;
- ~PromotionConfig() { delete _policy; }
- PromotionPolicy *
- getPolicy() const
- {
- return _policy;
- }
-
- // Parse the command line arguments to the plugin, and instantiate the appropriate policy
- bool
- factory(int argc, char *argv[])
- {
- while (true) {
- int opt = getopt_long(argc, (char *const *)argv, "psbhe", longopt, nullptr);
-
- if (opt == -1) {
- break;
- } else if (opt == 'p') {
- if (0 == strncasecmp(optarg, "chance", 6)) {
- _policy = new ChancePolicy();
- } else if (0 == strncasecmp(optarg, "lru", 3)) {
- _policy = new LRUPolicy();
- } else {
- TSError("[%s] Unknown policy --policy=%s", PLUGIN_NAME, optarg);
- return false;
- }
- if (_policy) {
- TSDebug(PLUGIN_NAME, "created remap with cache promotion policy = %s", _policy->policyName());
- }
- } else if (opt == 'e') {
- if (optarg == nullptr) {
- TSError("[%s] the -%c option requires an argument, the remap identifier.", PLUGIN_NAME, opt);
- return false;
- } else {
- if (_policy && _policy->stats_add(optarg)) {
- _policy->stats_enabled = true;
- TSDebug(PLUGIN_NAME, "stats collection is enabled");
- }
- }
- } else {
- if (_policy) {
- // The --sample (-s) option is allowed for all configs, but only after --policy is specified.
- if (opt == 's') {
- _policy->setSample(optarg);
- } else {
- if (!_policy->parseOption(opt, optarg)) {
- TSError("[%s] The specified policy (%s) does not support the -%c option", PLUGIN_NAME, _policy->policyName(), opt);
- delete _policy;
- _policy = nullptr;
- return false;
- }
- }
- } else {
- TSError("[%s] The --policy=<n> parameter must come first on the remap configuration", PLUGIN_NAME);
- return false;
- }
- }
- }
-
- return true;
- }
+// All policies are instantitated (and configured) via the configuration manager
+#include "config.h"
-private:
- PromotionPolicy *_policy = nullptr;
-};
+const char *PLUGIN_NAME = "cache_promote";
//////////////////////////////////////////////////////////////////////////////////////////////
// Main "plugin", a TXN hook in the TS_HTTP_READ_CACHE_HDR_HOOK. Unless the policy allows
diff --git a/plugins/cache_promote/chance_policy.h b/plugins/cache_promote/chance_policy.h
new file mode 100644
index 0000000..0841b9c
--- /dev/null
+++ b/plugins/cache_promote/chance_policy.h
@@ -0,0 +1,76 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#pragma once
+
+#include "policy.h"
+
+//////////////////////////////////////////////////////////////////////////////////////////////
+// This is the simplest of all policies, just give each request a (small)
+// percentage chance to be promoted to cache.
+//
+class ChancePolicy : public PromotionPolicy
+{
+public:
+ bool doPromote(TSHttpTxn /* txnp ATS_UNUSED */) override
+ {
+ TSDebug(PLUGIN_NAME, "ChancePolicy::doPromote(%f)", getSample());
+
+ incrementStat(promoted_id, 1);
+
+ return true;
+ }
+
+ void
+ usage() const override
+ {
+ TSError("[%s] Usage: @plugin=%s.so @pparam=--policy=chance @pparam=--sample=<x>%%", PLUGIN_NAME, PLUGIN_NAME);
+ }
+
+ const char *
+ policyName() const override
+ {
+ return "chance";
+ }
+
+ bool
+ stats_add(const char *remap_id) override
+ {
+ std::string_view remap_identifier = remap_id;
+ const std::tuple<std::string_view, int *> stats[] = {
+ {"cache_hits", &cache_hits_id},
+ {"promoted", &promoted_id},
+ {"total_requests", &total_requests_id},
+ };
+
+ if (nullptr == remap_id) {
+ TSError("[%s] no remap identifier specified for for stats, no stats will be used", PLUGIN_NAME);
+ return false;
+ }
+
+ for (int ii = 0; ii < 3; ii++) {
+ std::string_view name = std::get<0>(stats[ii]);
+ int *id = std::get<1>(stats[ii]);
+ if ((*(id) = create_stat(name, remap_identifier)) == TS_ERROR) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+};
diff --git a/plugins/cache_promote/config.cc b/plugins/cache_promote/config.cc
new file mode 100644
index 0000000..dacd425
--- /dev/null
+++ b/plugins/cache_promote/config.cc
@@ -0,0 +1,92 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#include <getopt.h>
+
+#include "config.h"
+#include "lru_policy.h"
+#include "chance_policy.h"
+
+//////////////////////////////////////////////////////////////////////////////////////////////
+// Note that all options for all policies has to go here. Not particularly pretty...
+//
+static const struct option longopt[] = {
+ {const_cast<char *>("policy"), required_argument, nullptr, 'p'},
+ // This is for both Chance and LRU (optional) policy
+ {const_cast<char *>("sample"), required_argument, nullptr, 's'},
+ // For the LRU policy
+ {const_cast<char *>("buckets"), required_argument, nullptr, 'b'},
+ {const_cast<char *>("stats-enable-with-id"), required_argument, nullptr, 'e'},
+ {const_cast<char *>("hits"), required_argument, nullptr, 'h'},
+ // EOF
+ {nullptr, no_argument, nullptr, '\0'},
+};
+
+// Parse the command line arguments to the plugin, and instantiate the appropriate policy
+bool
+PromotionConfig::factory(int argc, char *argv[])
+{
+ while (true) {
+ int opt = getopt_long(argc, (char *const *)argv, "psbhe", longopt, nullptr);
+
+ if (opt == -1) {
+ break;
+ } else if (opt == 'p') {
+ if (0 == strncasecmp(optarg, "chance", 6)) {
+ _policy = new ChancePolicy();
+ } else if (0 == strncasecmp(optarg, "lru", 3)) {
+ _policy = new LRUPolicy();
+ } else {
+ TSError("[%s] Unknown policy --policy=%s", PLUGIN_NAME, optarg);
+ return false;
+ }
+ if (_policy) {
+ TSDebug(PLUGIN_NAME, "created remap with cache promotion policy = %s", _policy->policyName());
+ }
+ } else if (opt == 'e') {
+ if (optarg == nullptr) {
+ TSError("[%s] the -%c option requires an argument, the remap identifier.", PLUGIN_NAME, opt);
+ return false;
+ } else {
+ if (_policy && _policy->stats_add(optarg)) {
+ _policy->stats_enabled = true;
+ TSDebug(PLUGIN_NAME, "stats collection is enabled");
+ }
+ }
+ } else {
+ if (_policy) {
+ // The --sample (-s) option is allowed for all configs, but only after --policy is specified.
+ if (opt == 's') {
+ _policy->setSample(optarg);
+ } else {
+ if (!_policy->parseOption(opt, optarg)) {
+ TSError("[%s] The specified policy (%s) does not support the -%c option", PLUGIN_NAME, _policy->policyName(), opt);
+ delete _policy;
+ _policy = nullptr;
+ return false;
+ }
+ }
+ } else {
+ TSError("[%s] The --policy=<n> parameter must come first on the remap configuration", PLUGIN_NAME);
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
diff --git a/plugins/cache_promote/lru_policy.cc b/plugins/cache_promote/lru_policy.cc
new file mode 100644
index 0000000..0a884f2
--- /dev/null
+++ b/plugins/cache_promote/lru_policy.cc
@@ -0,0 +1,185 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#include <unistd.h>
+
+#include "lru_policy.h"
+
+#define MINIMUM_BUCKET_SIZE 10
+
+static LRUEntry NULL_LRU_ENTRY; // Used to create an "empty" new LRUEntry
+
+LRUPolicy::~LRUPolicy()
+{
+ TSDebug(PLUGIN_NAME, "deleting LRUPolicy object");
+ TSMutexLock(_lock);
+
+ _map.clear();
+ _list.clear();
+ _list_size = 0;
+ _freelist.clear();
+ _freelist_size = 0;
+
+ TSMutexUnlock(_lock);
+ TSMutexDestroy(_lock);
+}
+
+bool
+LRUPolicy::parseOption(int opt, char *optarg)
+{
+ switch (opt) {
+ case 'b':
+ _buckets = static_cast<unsigned>(strtol(optarg, nullptr, 10));
+ if (_buckets < MINIMUM_BUCKET_SIZE) {
+ TSError("%s: Enforcing minimum LRU bucket size of %d", PLUGIN_NAME, MINIMUM_BUCKET_SIZE);
+ TSDebug(PLUGIN_NAME, "Enforcing minimum bucket size of %d", MINIMUM_BUCKET_SIZE);
+ _buckets = MINIMUM_BUCKET_SIZE;
+ }
+ break;
+ case 'h':
+ _hits = static_cast<unsigned>(strtol(optarg, nullptr, 10));
+ break;
+ default:
+ // All other options are unsupported for this policy
+ return false;
+ }
+
+ // This doesn't have to be perfect, since this is just chance sampling.
+ // coverity[dont_call]
+ srand48(static_cast<long>(time(nullptr)) ^ static_cast<long>(getpid()) ^ static_cast<long>(getppid()));
+
+ return true;
+}
+
+bool
+LRUPolicy::doPromote(TSHttpTxn txnp)
+{
+ LRUHash hash;
+ LRUMap::iterator map_it;
+ char *url = nullptr;
+ int url_len = 0;
+ bool ret = false;
+ TSMBuffer request;
+ TSMLoc req_hdr;
+
+ if (TS_SUCCESS == TSHttpTxnClientReqGet(txnp, &request, &req_hdr)) {
+ TSMLoc c_url = TS_NULL_MLOC;
+
+ // Get the cache key URL (for now), since this has better lookup behavior when using
+ // e.g. the cachekey plugin.
+ if (TS_SUCCESS == TSUrlCreate(request, &c_url)) {
+ if (TS_SUCCESS == TSHttpTxnCacheLookupUrlGet(txnp, request, c_url)) {
+ url = TSUrlStringGet(request, c_url, &url_len);
+ TSHandleMLocRelease(request, TS_NULL_MLOC, c_url);
+ }
+ }
+ TSHandleMLocRelease(request, TS_NULL_MLOC, req_hdr);
+ }
+
+ // Generally shouldn't happen ...
+ if (!url) {
+ return false;
+ }
+
+ TSDebug(PLUGIN_NAME, "LRUPolicy::doPromote(%.*s%s)", url_len > 100 ? 100 : url_len, url, url_len > 100 ? "..." : "");
+ hash.init(url, url_len);
+ TSfree(url);
+
+ // We have to hold the lock across all list and hash access / updates
+ TSMutexLock(_lock);
+
+ map_it = _map.find(&hash);
+ if (_map.end() != map_it) {
+ // We have an entry in the LRU
+ TSAssert(_list_size > 0); // mismatch in the LRUs hash and list, shouldn't happen
+ incrementStat(lru_hit_id, 1);
+ if (++(map_it->second->second) >= _hits) {
+ // Promoted! Cleanup the LRU, and signal success. Save the promoted entry on the freelist.
+ TSDebug(PLUGIN_NAME, "saving the LRUEntry to the freelist");
+ _freelist.splice(_freelist.begin(), _list, map_it->second);
+ ++_freelist_size;
+ --_list_size;
+ _map.erase(map_it->first);
+ incrementStat(promoted_id, 1);
+ incrementStat(freelist_size_id, 1);
+ decrementStat(lru_size_id, 1);
+ ret = true;
+ } else {
+ // It's still not promoted, make sure it's moved to the front of the list
+ TSDebug(PLUGIN_NAME, "still not promoted, got %d hits so far", map_it->second->second);
+ _list.splice(_list.begin(), _list, map_it->second);
+ }
+ } else {
+ // New LRU entry for the URL, try to repurpose the list entry as much as possible
+ incrementStat(lru_miss_id, 1);
+ if (_list_size >= _buckets) {
+ TSDebug(PLUGIN_NAME, "repurposing last LRUHash entry");
+ _list.splice(_list.begin(), _list, --_list.end());
+ _map.erase(&(_list.begin()->first));
+ incrementStat(lru_vacated_id, 1);
+ } else if (_freelist_size > 0) {
+ TSDebug(PLUGIN_NAME, "reusing LRUEntry from freelist");
+ _list.splice(_list.begin(), _freelist, _freelist.begin());
+ --_freelist_size;
+ ++_list_size;
+ incrementStat(lru_size_id, 1);
+ decrementStat(freelist_size_id, 1);
+ } else {
+ TSDebug(PLUGIN_NAME, "creating new LRUEntry");
+ _list.push_front(NULL_LRU_ENTRY);
+ ++_list_size;
+ incrementStat(lru_size_id, 1);
+ }
+ // Update the "new" LRUEntry and add it to the hash
+ _list.begin()->first = hash;
+ _list.begin()->second = 1;
+ _map[&(_list.begin()->first)] = _list.begin();
+ }
+
+ TSMutexUnlock(_lock);
+
+ return ret;
+}
+
+bool
+LRUPolicy::stats_add(const char *remap_id)
+
+{
+ std::string_view remap_identifier = remap_id;
+ const std::tuple<std::string_view, int *> stats[] = {
+ {"cache_hits", &cache_hits_id}, {"freelist_size", &freelist_size_id},
+ {"lru_size", &lru_size_id}, {"lru_hit", &lru_hit_id},
+ {"lru_miss", &lru_miss_id}, {"lru_vacated", &lru_vacated_id},
+ {"promoted", &promoted_id}, {"total_requests", &total_requests_id},
+ };
+
+ if (nullptr == remap_id) {
+ TSError("[%s] no remap identifier specified for for stats, no stats will be used", PLUGIN_NAME);
+ return false;
+ }
+
+ for (int ii = 0; ii < 8; ii++) {
+ std::string_view name = std::get<0>(stats[ii]);
+ int *id = std::get<1>(stats[ii]);
+ if ((*(id) = create_stat(name, remap_identifier)) == TS_ERROR) {
+ return false;
+ }
+ }
+
+ return true;
+}
diff --git a/plugins/cache_promote/lru_policy.h b/plugins/cache_promote/lru_policy.h
new file mode 100644
index 0000000..7a9ed8d
--- /dev/null
+++ b/plugins/cache_promote/lru_policy.h
@@ -0,0 +1,124 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#pragma once
+
+#include <openssl/sha.h>
+#include <unordered_map>
+#include <list>
+
+#include "policy.h"
+
+#define MINIMUM_BUCKET_SIZE 10
+
+//////////////////////////////////////////////////////////////////////////////////////////////
+// The LRU based policy keeps track of <bucket> number of URLs, with a counter for each slot.
+// Objects are not promoted unless the counter reaches <hits> before it gets evicted. An
+// optional <chance> parameter can be used to sample hits, this can reduce contention and
+// churning in the LRU as well.
+//
+class LRUHash
+{
+ friend struct LRUHashHasher;
+
+public:
+ LRUHash() { TSDebug(PLUGIN_NAME, "In LRUHash()"); }
+ ~LRUHash() { TSDebug(PLUGIN_NAME, "In ~LRUHash()"); }
+ LRUHash &
+ operator=(const LRUHash &h)
+ {
+ TSDebug(PLUGIN_NAME, "copying an LRUHash object");
+ if (this != &h) {
+ memcpy(_hash, h._hash, sizeof(_hash));
+ }
+ return *this;
+ }
+
+ void
+ init(char *data, int len)
+ {
+ SHA_CTX sha;
+
+ SHA1_Init(&sha);
+ SHA1_Update(&sha, data, len);
+ SHA1_Final(_hash, &sha);
+ }
+
+private:
+ u_char _hash[SHA_DIGEST_LENGTH];
+};
+
+struct LRUHashHasher {
+ bool
+ operator()(const LRUHash *s1, const LRUHash *s2) const
+ {
+ return 0 == memcmp(s1->_hash, s2->_hash, sizeof(s2->_hash));
+ }
+
+ size_t
+ operator()(const LRUHash *s) const
+ {
+ return *(reinterpret_cast<const size_t *>(s->_hash)) ^ *(reinterpret_cast<const size_t *>(s->_hash + 9));
+ }
+};
+
+typedef std::pair<LRUHash, unsigned> LRUEntry;
+using LRUList = std::list<LRUEntry>;
+typedef std::unordered_map<const LRUHash *, LRUList::iterator, LRUHashHasher, LRUHashHasher> LRUMap;
+
+class LRUPolicy : public PromotionPolicy
+{
+public:
+ LRUPolicy() : PromotionPolicy(), _lock(TSMutexCreate()) {}
+ ~LRUPolicy() override;
+
+ bool parseOption(int opt, char *optarg) override;
+ bool doPromote(TSHttpTxn txnp) override;
+ bool stats_add(const char *remap_id) override;
+
+ void
+ usage() const override
+ {
+ TSError("[%s] Usage: @plugin=%s.so @pparam=--policy=lru @pparam=--buckets=<n> --hits=<m> --sample=<x>", PLUGIN_NAME,
+ PLUGIN_NAME);
+ }
+
+ const char *
+ policyName() const override
+ {
+ return "LRU";
+ }
+
+private:
+ unsigned _buckets = 1000;
+ unsigned _hits = 10;
+ // For the LRU. Note that we keep track of the List sizes, because some versions fo STL have broken
+ // implementations of size(), making them obsessively slow on calling ::size().
+ TSMutex _lock;
+ LRUMap _map;
+ LRUList _list, _freelist;
+ size_t _list_size = 0, _freelist_size = 0;
+
+ // internal stats ids
+ int freelist_size_id = -1;
+ int lru_size_id = -1;
+ int lru_hit_id = -1;
+ int lru_miss_id = -1;
+ int lru_vacated_id = -1;
+ int promoted_id = -1;
+};
diff --git a/plugins/cache_promote/policy.cc b/plugins/cache_promote/policy.cc
new file mode 100644
index 0000000..dedfd82
--- /dev/null
+++ b/plugins/cache_promote/policy.cc
@@ -0,0 +1,56 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+#include "policy.h"
+
+bool
+PromotionPolicy::doSample() const
+{
+ if (_sample > 0) {
+ // coverity[dont_call]
+ double r = drand48();
+
+ if (_sample > r) {
+ TSDebug(PLUGIN_NAME, "checking sampling, is %f > %f? Yes!", _sample, r);
+ } else {
+ TSDebug(PLUGIN_NAME, "checking sampling, is %f > %f? No!", _sample, r);
+ return false;
+ }
+ }
+ return true;
+}
+
+int
+PromotionPolicy::create_stat(std::string_view name, std::string_view remap_identifier)
+{
+ int stat_id = -1;
+ ts::LocalBufferWriter<MAX_STAT_LENGTH> stat_name;
+ stat_name.reset().clip(1);
+ stat_name.print("plugin.{}.{}.{}", PLUGIN_NAME, remap_identifier, name);
+ stat_name.extend(1).write('\0');
+
+ if (TS_ERROR == TSStatFindName(stat_name.data(), &stat_id)) {
+ stat_id = TSStatCreate(stat_name.data(), TS_RECORDDATATYPE_INT, TS_STAT_NON_PERSISTENT, TS_STAT_SYNC_SUM);
+ if (TS_ERROR == stat_id) {
+ TSDebug(PLUGIN_NAME, "Error creating stat_name: %s", stat_name.data());
+ } else {
+ TSDebug(PLUGIN_NAME, "Created stat_name: %s, stat_id: %d", stat_name.data(), stat_id);
+ }
+ }
+
+ return stat_id;
+}
diff --git a/plugins/cache_promote/policy.h b/plugins/cache_promote/policy.h
new file mode 100644
index 0000000..081ee18
--- /dev/null
+++ b/plugins/cache_promote/policy.h
@@ -0,0 +1,96 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#pragma once
+
+#include "tscore/BufferWriter.h"
+
+#include "ts/ts.h"
+#include "ts/remap.h"
+
+#define MAX_STAT_LENGTH (1 << 8)
+
+extern const char *PLUGIN_NAME;
+
+//////////////////////////////////////////////////////////////////////////////////////////////
+// Abstract base class for all policies.
+//
+class PromotionPolicy
+{
+public:
+ PromotionPolicy()
+ {
+ // This doesn't have to be perfect, since this is just chance sampling.
+ // coverity[dont_call]
+ srand48(static_cast<long>(time(nullptr)));
+ }
+
+ void
+ setSample(char *s)
+ {
+ _sample = strtof(s, nullptr) / 100.0;
+ }
+
+ float
+ getSample() const
+ {
+ return _sample;
+ }
+
+ void
+ decrementStat(const int stat, const int amount)
+ {
+ if (stats_enabled) {
+ TSStatIntDecrement(stat, amount);
+ }
+ }
+
+ void
+ incrementStat(const int stat, const int amount)
+ {
+ if (stats_enabled) {
+ TSStatIntIncrement(stat, amount);
+ }
+ }
+
+ virtual ~PromotionPolicy() = default;
+
+ virtual bool
+ parseOption(int opt, char *optarg)
+ {
+ return false;
+ }
+
+ bool doSample() const;
+ int create_stat(std::string_view name, std::string_view remap_identifier);
+
+ // These are pure virtual
+ virtual bool doPromote(TSHttpTxn txnp) = 0;
+ virtual const char *policyName() const = 0;
+ virtual void usage() const = 0;
+ virtual bool stats_add(const char *remap_id) = 0;
+
+ // when true stats are incremented.
+ bool stats_enabled = false;
+ int cache_hits_id = -1;
+ int promoted_id = -1;
+ int total_requests_id = -1;
+
+private:
+ float _sample = 0.0;
+};