2 * This file is part of PowerDNS or dnsdist.
3 * Copyright -- PowerDNS.COM B.V. and its contributors
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of version 2 of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * In addition, for the avoidance of any doubt, permission is granted to
10 * link this program with OpenSSL and to (re)distribute the binaries
11 * produced as the result of such linking.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 // this function can clean any cache that has a getTTD() method on its entries, a preRemoval() method and a 'sequence' index as its second index
28 // the ritual is that the oldest entries are in *front* of the sequence collection, so on a hit, move an item to the end
29 // on a miss, move it to the beginning
30 template <typename S, typename C, typename T> void pruneCollection(C& container, T& collection, unsigned int maxCached, unsigned int scanFraction=1000)
33 unsigned int toTrim=0;
35 unsigned int cacheSize=collection.size();
37 if(cacheSize > maxCached) {
38 toTrim = cacheSize - maxCached;
41 // cout<<"Need to trim "<<toTrim<<" from cache to meet target!\n";
43 typedef typename T::template index<S>::type sequence_t;
44 sequence_t& sidx=collection.template get<S>();
46 unsigned int tried=0, lookAt, erased=0;
48 // two modes - if toTrim is 0, just look through 1/scanFraction of all records
49 // and nuke everything that is expired
50 // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
54 lookAt=cacheSize/scanFraction;
56 typename sequence_t::iterator iter=sidx.begin(), eiter;
57 for(; iter != sidx.end() && tried < lookAt ; ++tried) {
58 if(iter->getTTD() < now) {
59 container.preRemoval(*iter);
60 iter = sidx.erase(iter);
66 if(toTrim && erased >= toTrim)
70 //cout<<"erased "<<erased<<" records based on ttd\n";
72 if(erased >= toTrim) // done
78 // cout<<"Still have "<<toTrim - erased<<" entries left to erase to meet target\n";
80 eiter=iter=sidx.begin();
81 std::advance(eiter, toTrim);
82 // just lob it off from the beginning
83 for (auto i = iter; ; ) {
88 container.preRemoval(*i);
93 // note: this expects iterator from first index
94 template <typename S, typename T> void moveCacheItemToFrontOrBack(T& collection, typename T::iterator& iter, bool front)
96 typedef typename T::template index<S>::type sequence_t;
97 sequence_t& sidx=collection.template get<S>();
98 typename sequence_t::iterator si=collection.template project<S>(iter);
100 sidx.relocate(sidx.begin(), si); // at the beginning of the delete queue
102 sidx.relocate(sidx.end(), si); // back
105 template <typename S, typename T> void moveCacheItemToFront(T& collection, typename T::iterator& iter)
107 moveCacheItemToFrontOrBack<S>(collection, iter, true);
110 template <typename S, typename T> void moveCacheItemToBack(T& collection, typename T::iterator& iter)
112 moveCacheItemToFrontOrBack<S>(collection, iter, false);
115 template <typename S, typename T> uint64_t pruneLockedCollectionsVector(vector<T>& maps, uint64_t maxCached, uint64_t cacheSize)
117 time_t now = time(nullptr);
118 uint64_t totErased = 0;
122 // two modes - if toTrim is 0, just look through 10% of the cache and nuke everything that is expired
123 // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
124 if (maxCached && cacheSize > maxCached) {
125 toTrim = cacheSize - maxCached;
128 lookAt = cacheSize / 10;
131 for(auto& mc : maps) {
132 WriteLock wl(&mc.d_mut);
133 auto& sidx = boost::multi_index::get<S>(mc.d_map);
134 uint64_t erased = 0, lookedAt = 0;
135 for(auto i = sidx.begin(); i != sidx.end(); lookedAt++) {
136 if (i->getTTD() < now) {
143 if(toTrim && erased > toTrim / maps.size())
146 if(lookedAt > lookAt / maps.size())
155 template <typename S, typename C, typename T> uint64_t pruneMutexCollectionsVector(C& container, vector<T>& maps, uint64_t maxCached, uint64_t cacheSize)
157 time_t now = time(nullptr);
158 uint64_t totErased = 0;
162 // two modes - if toTrim is 0, just look through 10% of the cache and nuke everything that is expired
163 // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
164 if (cacheSize > maxCached) {
165 toTrim = cacheSize - maxCached;
168 lookAt = cacheSize / 10;
171 for (auto& mc : maps) {
172 const std::lock_guard<std::mutex> lock(mc.mutex);
173 auto& sidx = boost::multi_index::get<S>(mc.d_map);
174 uint64_t erased = 0, lookedAt = 0;
175 for (auto i = sidx.begin(); i != sidx.end(); lookedAt++) {
176 if (i->getTTD() < now) {
177 container.preRemoval(*i);
184 if (toTrim && erased >= toTrim / maps.size())
187 if (lookedAt > lookAt / maps.size())
191 if (toTrim && totErased >= toTrim)
195 if (totErased >= toTrim) { // done
201 // XXXX kinda desperate method
203 for (auto& mc : maps) {
204 const std::lock_guard<std::mutex> lock(mc.mutex);
205 auto& sidx = boost::multi_index::get<S>(mc.d_map);
206 auto i = sidx.begin();
207 container.preRemoval(*i);
218 template <typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps)
222 for(auto& mc : maps) {
223 WriteLock wl(&mc.d_mut);
224 delcount += mc.d_map.size();
231 template <typename N, typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps, const std::string& match)
234 string prefix(match);
235 prefix.resize(prefix.size()-1);
236 DNSName dprefix(prefix);
237 for(auto& mc : maps) {
238 WriteLock wl(&mc.d_mut);
239 auto& idx = boost::multi_index::get<N>(mc.d_map);
240 auto iter = idx.lower_bound(dprefix);
243 for(; iter != idx.end(); ++iter) {
244 if(!iter->qname.isPartOf(dprefix)) {
249 idx.erase(start, iter);
255 template <typename N, typename T> uint64_t purgeExactLockedCollection(T& mc, const DNSName& qname)
258 WriteLock wl(&mc.d_mut);
259 auto& idx = boost::multi_index::get<N>(mc.d_map);
260 auto range = idx.equal_range(qname);
261 if(range.first != range.second) {
262 delcount += distance(range.first, range.second);
263 idx.erase(range.first, range.second);
269 template<typename S, typename Index>
270 std::pair<typename Index::iterator,bool>
271 lruReplacingInsert(Index& i,const typename Index::value_type& x)
273 std::pair<typename Index::iterator,bool> res = i.insert(x);
275 moveCacheItemToBack<S>(i, res.first);
276 res.second = i.replace(res.first, x);