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.
26 // 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
27 // the ritual is that the oldest entries are in *front* of the sequence collection, so on a hit, move an item to the end
28 // on a miss, move it to the beginning
29 template <typename S, typename C, typename T> void pruneCollection(C& container, T& collection, unsigned int maxCached, unsigned int scanFraction=1000)
32 unsigned int toTrim=0;
34 unsigned int cacheSize=collection.size();
36 if(cacheSize > maxCached) {
37 toTrim = cacheSize - maxCached;
40 // cout<<"Need to trim "<<toTrim<<" from cache to meet target!\n";
42 typedef typename T::template index<S>::type sequence_t;
43 sequence_t& sidx=collection.template get<S>();
45 unsigned int tried=0, lookAt, erased=0;
47 // two modes - if toTrim is 0, just look through 1/scanFraction of all records
48 // and nuke everything that is expired
49 // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
53 lookAt=cacheSize/scanFraction;
55 typename sequence_t::iterator iter=sidx.begin(), eiter;
56 for(; iter != sidx.end() && tried < lookAt ; ++tried) {
57 if(iter->getTTD() < now) {
58 container.preRemoval(*iter);
65 if(toTrim && erased >= toTrim)
69 //cout<<"erased "<<erased<<" records based on ttd\n";
71 if(erased >= toTrim) // done
77 // cout<<"Still have "<<toTrim - erased<<" entries left to erase to meet target\n";
79 eiter=iter=sidx.begin();
80 std::advance(eiter, toTrim);
81 // just lob it off from the beginning
82 for (auto i = iter; ; ) {
87 container.preRemoval(*i);
92 // note: this expects iterator from first index
93 template <typename S, typename T> void moveCacheItemToFrontOrBack(T& collection, typename T::iterator& iter, bool front)
95 typedef typename T::template index<S>::type sequence_t;
96 sequence_t& sidx=collection.template get<S>();
97 typename sequence_t::iterator si=collection.template project<S>(iter);
99 sidx.relocate(sidx.begin(), si); // at the beginning of the delete queue
101 sidx.relocate(sidx.end(), si); // back
104 template <typename S, typename T> void moveCacheItemToFront(T& collection, typename T::iterator& iter)
106 moveCacheItemToFrontOrBack<S>(collection, iter, true);
109 template <typename S, typename T> void moveCacheItemToBack(T& collection, typename T::iterator& iter)
111 moveCacheItemToFrontOrBack<S>(collection, iter, false);
114 template <typename S, typename T> uint64_t pruneLockedCollectionsVector(vector<T>& maps, uint64_t maxCached, uint64_t cacheSize)
116 time_t now = time(nullptr);
117 uint64_t totErased = 0;
121 // two modes - if toTrim is 0, just look through 10% of the cache and nuke everything that is expired
122 // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
123 if (maxCached && cacheSize > maxCached) {
124 toTrim = cacheSize - maxCached;
127 lookAt = cacheSize / 10;
130 for(auto& mc : maps) {
131 WriteLock wl(&mc.d_mut);
132 auto& sidx = boost::multi_index::get<S>(mc.d_map);
133 uint64_t erased = 0, lookedAt = 0;
134 for(auto i = sidx.begin(); i != sidx.end(); lookedAt++) {
142 if(toTrim && erased > toTrim / maps.size())
145 if(lookedAt > lookAt / maps.size())
154 template <typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps)
158 for(auto& mc : maps) {
159 WriteLock wl(&mc.d_mut);
160 delcount += mc.d_map.size();
167 template <typename N, typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps, const std::string& match)
170 string prefix(match);
171 prefix.resize(prefix.size()-1);
172 DNSName dprefix(prefix);
173 for(auto& mc : maps) {
174 WriteLock wl(&mc.d_mut);
175 auto& idx = boost::multi_index::get<N>(mc.d_map);
176 auto iter = idx.lower_bound(dprefix);
179 for(; iter != idx.end(); ++iter) {
180 if(!iter->qname.isPartOf(dprefix)) {
185 idx.erase(start, iter);
191 template <typename N, typename T> uint64_t purgeExactLockedCollection(T& mc, const DNSName& qname)
194 WriteLock wl(&mc.d_mut);
195 auto& idx = boost::multi_index::get<N>(mc.d_map);
196 auto range = idx.equal_range(qname);
197 if(range.first != range.second) {
198 delcount += distance(range.first, range.second);
199 idx.erase(range.first, range.second);
205 template<typename S, typename Index>
206 std::pair<typename Index::iterator,bool>
207 lruReplacingInsert(Index& i,const typename Index::value_type& x)
209 std::pair<typename Index::iterator,bool> res = i.insert(x);
211 moveCacheItemToBack<S>(i, res.first);
212 res.second = i.replace(res.first, x);