]>
Commit | Line | Data |
---|---|---|
12471842 PL |
1 | /* |
2 | * This file is part of PowerDNS or dnsdist. | |
3 | * Copyright -- PowerDNS.COM B.V. and its contributors | |
4 | * | |
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. | |
8 | * | |
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. | |
12 | * | |
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. | |
17 | * | |
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. | |
21 | */ | |
e7135447 | 22 | #pragma once |
38c9ceaa | 23 | |
a7956123 | 24 | #include <mutex> |
bf269e28 RG |
25 | #include "lock.hh" |
26 | ||
e74f866a | 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 |
c2567ad1 BH |
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 | |
94306029 | 30 | template <typename S, typename C, typename T> void pruneCollection(C& container, T& collection, unsigned int maxCached, unsigned int scanFraction=1000) |
38c9ceaa | 31 | { |
6b68a4e3 | 32 | time_t now=time(0); |
38c9ceaa BH |
33 | unsigned int toTrim=0; |
34 | ||
35 | unsigned int cacheSize=collection.size(); | |
36 | ||
157f806e | 37 | if(cacheSize > maxCached) { |
38c9ceaa BH |
38 | toTrim = cacheSize - maxCached; |
39 | } | |
40 | ||
41 | // cout<<"Need to trim "<<toTrim<<" from cache to meet target!\n"; | |
42 | ||
94306029 OM |
43 | typedef typename T::template index<S>::type sequence_t; |
44 | sequence_t& sidx=collection.template get<S>(); | |
38c9ceaa BH |
45 | |
46 | unsigned int tried=0, lookAt, erased=0; | |
47 | ||
1a16adf0 BH |
48 | // two modes - if toTrim is 0, just look through 1/scanFraction of all records |
49 | // and nuke everything that is expired | |
38c9ceaa BH |
50 | // otherwise, scan first 5*toTrim records, and stop once we've nuked enough |
51 | if(toTrim) | |
52 | lookAt=5*toTrim; | |
53 | else | |
1a16adf0 | 54 | lookAt=cacheSize/scanFraction; |
38c9ceaa BH |
55 | |
56 | typename sequence_t::iterator iter=sidx.begin(), eiter; | |
57 | for(; iter != sidx.end() && tried < lookAt ; ++tried) { | |
e74f866a RG |
58 | if(iter->getTTD() < now) { |
59 | container.preRemoval(*iter); | |
a7956123 | 60 | iter = sidx.erase(iter); |
38c9ceaa BH |
61 | erased++; |
62 | } | |
63 | else | |
64 | ++iter; | |
65 | ||
9a4cb110 | 66 | if(toTrim && erased >= toTrim) |
38c9ceaa BH |
67 | break; |
68 | } | |
69 | ||
70 | //cout<<"erased "<<erased<<" records based on ttd\n"; | |
71 | ||
72 | if(erased >= toTrim) // done | |
73 | return; | |
74 | ||
75 | toTrim -= erased; | |
76 | ||
77 | //if(toTrim) | |
78 | // cout<<"Still have "<<toTrim - erased<<" entries left to erase to meet target\n"; | |
79 | ||
80 | eiter=iter=sidx.begin(); | |
e74f866a RG |
81 | std::advance(eiter, toTrim); |
82 | // just lob it off from the beginning | |
83 | for (auto i = iter; ; ) { | |
84 | if (i == eiter) { | |
85 | break; | |
86 | } | |
87 | ||
88 | container.preRemoval(*i); | |
89 | sidx.erase(i++); | |
90 | } | |
38c9ceaa BH |
91 | } |
92 | ||
94306029 OM |
93 | // note: this expects iterator from first index |
94 | template <typename S, typename T> void moveCacheItemToFrontOrBack(T& collection, typename T::iterator& iter, bool front) | |
c2567ad1 | 95 | { |
94306029 OM |
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); | |
c2567ad1 BH |
99 | if(front) |
100 | sidx.relocate(sidx.begin(), si); // at the beginning of the delete queue | |
101 | else | |
102 | sidx.relocate(sidx.end(), si); // back | |
103 | } | |
104 | ||
94306029 | 105 | template <typename S, typename T> void moveCacheItemToFront(T& collection, typename T::iterator& iter) |
c2567ad1 | 106 | { |
94306029 | 107 | moveCacheItemToFrontOrBack<S>(collection, iter, true); |
c2567ad1 BH |
108 | } |
109 | ||
94306029 | 110 | template <typename S, typename T> void moveCacheItemToBack(T& collection, typename T::iterator& iter) |
c2567ad1 | 111 | { |
94306029 | 112 | moveCacheItemToFrontOrBack<S>(collection, iter, false); |
c2567ad1 BH |
113 | } |
114 | ||
94306029 | 115 | template <typename S, typename T> uint64_t pruneLockedCollectionsVector(vector<T>& maps, uint64_t maxCached, uint64_t cacheSize) |
bf269e28 RG |
116 | { |
117 | time_t now = time(nullptr); | |
118 | uint64_t totErased = 0; | |
119 | uint64_t toTrim = 0; | |
120 | uint64_t lookAt = 0; | |
121 | ||
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; | |
126 | lookAt = 5 * toTrim; | |
127 | } else { | |
128 | lookAt = cacheSize / 10; | |
129 | } | |
130 | ||
131 | for(auto& mc : maps) { | |
132 | WriteLock wl(&mc.d_mut); | |
94306029 | 133 | auto& sidx = boost::multi_index::get<S>(mc.d_map); |
bf269e28 RG |
134 | uint64_t erased = 0, lookedAt = 0; |
135 | for(auto i = sidx.begin(); i != sidx.end(); lookedAt++) { | |
cdde2458 | 136 | if (i->ttd < now) { |
bf269e28 RG |
137 | i = sidx.erase(i); |
138 | erased++; | |
139 | } else { | |
140 | ++i; | |
141 | } | |
142 | ||
143 | if(toTrim && erased > toTrim / maps.size()) | |
144 | break; | |
145 | ||
146 | if(lookedAt > lookAt / maps.size()) | |
147 | break; | |
148 | } | |
149 | totErased += erased; | |
150 | } | |
151 | ||
152 | return totErased; | |
153 | } | |
154 | ||
a7956123 OM |
155 | template <typename S, typename C, typename T> uint64_t pruneMutexCollectionsVector(C& container, vector<T>& maps, uint64_t maxCached, uint64_t cacheSize) |
156 | { | |
157 | time_t now = time(nullptr); | |
158 | uint64_t totErased = 0; | |
159 | uint64_t toTrim = 0; | |
160 | uint64_t lookAt = 0; | |
161 | ||
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; | |
166 | lookAt = 5 * toTrim; | |
167 | } else { | |
168 | lookAt = cacheSize / 10; | |
169 | } | |
04bd5303 OM |
170 | |
171 | uint64_t maps_size = maps.size(); | |
172 | if (maps_size == 0) | |
173 | return 0; | |
174 | ||
a7956123 OM |
175 | for (auto& mc : maps) { |
176 | const std::lock_guard<std::mutex> lock(mc.mutex); | |
4cda5b6e | 177 | mc.d_cachecachevalid = false; |
a7956123 OM |
178 | auto& sidx = boost::multi_index::get<S>(mc.d_map); |
179 | uint64_t erased = 0, lookedAt = 0; | |
180 | for (auto i = sidx.begin(); i != sidx.end(); lookedAt++) { | |
181 | if (i->getTTD() < now) { | |
182 | container.preRemoval(*i); | |
183 | i = sidx.erase(i); | |
184 | erased++; | |
cdde2458 | 185 | mc.d_entriesCount--; |
a7956123 OM |
186 | } else { |
187 | ++i; | |
188 | } | |
189 | ||
04bd5303 | 190 | if (toTrim && erased >= toTrim / maps_size) |
a7956123 OM |
191 | break; |
192 | ||
04bd5303 | 193 | if (lookedAt > lookAt / maps_size) |
a7956123 OM |
194 | break; |
195 | } | |
196 | totErased += erased; | |
197 | if (toTrim && totErased >= toTrim) | |
198 | break; | |
199 | } | |
200 | ||
201 | if (totErased >= toTrim) { // done | |
202 | return totErased; | |
203 | } | |
204 | ||
205 | toTrim -= totErased; | |
206 | ||
207 | // XXXX kinda desperate method | |
208 | while (toTrim > 0) { | |
209 | for (auto& mc : maps) { | |
210 | const std::lock_guard<std::mutex> lock(mc.mutex); | |
4cda5b6e | 211 | mc.d_cachecachevalid = false; |
a7956123 OM |
212 | auto& sidx = boost::multi_index::get<S>(mc.d_map); |
213 | auto i = sidx.begin(); | |
214 | container.preRemoval(*i); | |
215 | i = sidx.erase(i); | |
cdde2458 | 216 | mc.d_entriesCount--; |
a7956123 OM |
217 | totErased++; |
218 | toTrim--; | |
219 | if (toTrim == 0) | |
220 | break; | |
221 | } | |
222 | } | |
223 | return totErased; | |
224 | } | |
225 | ||
bf269e28 RG |
226 | template <typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps) |
227 | { | |
228 | uint64_t delcount=0; | |
229 | ||
230 | for(auto& mc : maps) { | |
231 | WriteLock wl(&mc.d_mut); | |
232 | delcount += mc.d_map.size(); | |
233 | mc.d_map.clear(); | |
234 | } | |
235 | ||
236 | return delcount; | |
237 | } | |
238 | ||
94306029 | 239 | template <typename N, typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps, const std::string& match) |
bf269e28 RG |
240 | { |
241 | uint64_t delcount=0; | |
242 | string prefix(match); | |
243 | prefix.resize(prefix.size()-1); | |
244 | DNSName dprefix(prefix); | |
245 | for(auto& mc : maps) { | |
246 | WriteLock wl(&mc.d_mut); | |
94306029 | 247 | auto& idx = boost::multi_index::get<N>(mc.d_map); |
bf269e28 RG |
248 | auto iter = idx.lower_bound(dprefix); |
249 | auto start = iter; | |
250 | ||
251 | for(; iter != idx.end(); ++iter) { | |
252 | if(!iter->qname.isPartOf(dprefix)) { | |
253 | break; | |
254 | } | |
255 | delcount++; | |
256 | } | |
257 | idx.erase(start, iter); | |
258 | } | |
259 | ||
260 | return delcount; | |
261 | } | |
262 | ||
94306029 | 263 | template <typename N, typename T> uint64_t purgeExactLockedCollection(T& mc, const DNSName& qname) |
bf269e28 RG |
264 | { |
265 | uint64_t delcount=0; | |
266 | WriteLock wl(&mc.d_mut); | |
94306029 | 267 | auto& idx = boost::multi_index::get<N>(mc.d_map); |
bf269e28 RG |
268 | auto range = idx.equal_range(qname); |
269 | if(range.first != range.second) { | |
270 | delcount += distance(range.first, range.second); | |
271 | idx.erase(range.first, range.second); | |
272 | } | |
273 | ||
274 | return delcount; | |
275 | } | |
1d704752 | 276 | |
94306029 | 277 | template<typename S, typename Index> |
1d704752 RG |
278 | std::pair<typename Index::iterator,bool> |
279 | lruReplacingInsert(Index& i,const typename Index::value_type& x) | |
280 | { | |
281 | std::pair<typename Index::iterator,bool> res = i.insert(x); | |
282 | if (!res.second) { | |
94306029 | 283 | moveCacheItemToBack<S>(i, res.first); |
1d704752 RG |
284 | res.second = i.replace(res.first, x); |
285 | } | |
286 | return res; | |
287 | } |