You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

262 lines
7.3 KiB

  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. */
  22. #pragma once
  23. #include <mutex>
  24. #include "lock.hh"
  25. // 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
  26. // the ritual is that the oldest entries are in *front* of the sequence collection, so on a hit, move an item to the end
  27. // on a miss, move it to the beginning
  28. template <typename S, typename C, typename T> void pruneCollection(C& container, T& collection, size_t maxCached, size_t scanFraction = 1000)
  29. {
  30. const time_t now = time(0);
  31. size_t toTrim = 0;
  32. const size_t cacheSize = collection.size();
  33. if (cacheSize > maxCached) {
  34. toTrim = cacheSize - maxCached;
  35. }
  36. auto& sidx = collection.template get<S>();
  37. // two modes - if toTrim is 0, just look through 1/scanFraction of all records
  38. // and nuke everything that is expired
  39. // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
  40. const size_t lookAt = toTrim ? 5 * toTrim : cacheSize / scanFraction;
  41. size_t tried = 0, erased = 0;
  42. for (auto iter = sidx.begin(); iter != sidx.end() && tried < lookAt ; ++tried) {
  43. if (iter->getTTD() < now) {
  44. container.preRemoval(*iter);
  45. iter = sidx.erase(iter);
  46. erased++;
  47. }
  48. else {
  49. ++iter;
  50. }
  51. if (toTrim && erased >= toTrim) {
  52. break;
  53. }
  54. }
  55. if (erased >= toTrim) { // done
  56. return;
  57. }
  58. toTrim -= erased;
  59. // just lob it off from the beginning
  60. auto iter = sidx.begin();
  61. for (size_t i = 0; i < toTrim && iter != sidx.end(); i++) {
  62. container.preRemoval(*iter);
  63. iter = sidx.erase(iter);
  64. }
  65. }
  66. // note: this expects iterator from first index
  67. template <typename S, typename T> void moveCacheItemToFrontOrBack(T& collection, typename T::iterator& iter, bool front)
  68. {
  69. typedef typename T::template index<S>::type sequence_t;
  70. sequence_t& sidx=collection.template get<S>();
  71. typename sequence_t::iterator si=collection.template project<S>(iter);
  72. if(front)
  73. sidx.relocate(sidx.begin(), si); // at the beginning of the delete queue
  74. else
  75. sidx.relocate(sidx.end(), si); // back
  76. }
  77. template <typename S, typename T> void moveCacheItemToFront(T& collection, typename T::iterator& iter)
  78. {
  79. moveCacheItemToFrontOrBack<S>(collection, iter, true);
  80. }
  81. template <typename S, typename T> void moveCacheItemToBack(T& collection, typename T::iterator& iter)
  82. {
  83. moveCacheItemToFrontOrBack<S>(collection, iter, false);
  84. }
  85. template <typename S, typename T> uint64_t pruneLockedCollectionsVector(vector<T>& maps)
  86. {
  87. uint64_t totErased = 0;
  88. time_t now = time(nullptr);
  89. for(auto& mc : maps) {
  90. WriteLock wl(&mc.d_mut);
  91. uint64_t lookAt = (mc.d_map.size() + 9) / 10; // Look at 10% of this shard
  92. uint64_t erased = 0;
  93. auto& sidx = boost::multi_index::get<S>(mc.d_map);
  94. for(auto i = sidx.begin(); i != sidx.end() && lookAt > 0; lookAt--) {
  95. if(i->ttd < now) {
  96. i = sidx.erase(i);
  97. erased++;
  98. } else {
  99. ++i;
  100. }
  101. }
  102. totErased += erased;
  103. }
  104. return totErased;
  105. }
  106. template <typename S, typename C, typename T> uint64_t pruneMutexCollectionsVector(C& container, vector<T>& maps, uint64_t maxCached, uint64_t cacheSize)
  107. {
  108. time_t now = time(nullptr);
  109. uint64_t totErased = 0;
  110. uint64_t toTrim = 0;
  111. uint64_t lookAt = 0;
  112. // two modes - if toTrim is 0, just look through 10% of the cache and nuke everything that is expired
  113. // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
  114. if (cacheSize > maxCached) {
  115. toTrim = cacheSize - maxCached;
  116. lookAt = 5 * toTrim;
  117. } else {
  118. lookAt = cacheSize / 10;
  119. }
  120. uint64_t maps_size = maps.size();
  121. if (maps_size == 0)
  122. return 0;
  123. for (auto& mc : maps) {
  124. const typename C::lock l(mc);
  125. mc.d_cachecachevalid = false;
  126. auto& sidx = boost::multi_index::get<S>(mc.d_map);
  127. uint64_t erased = 0, lookedAt = 0;
  128. for (auto i = sidx.begin(); i != sidx.end(); lookedAt++) {
  129. if (i->getTTD() < now) {
  130. container.preRemoval(*i);
  131. i = sidx.erase(i);
  132. erased++;
  133. mc.d_entriesCount--;
  134. } else {
  135. ++i;
  136. }
  137. if (toTrim && erased >= toTrim / maps_size)
  138. break;
  139. if (lookedAt > lookAt / maps_size)
  140. break;
  141. }
  142. totErased += erased;
  143. if (toTrim && totErased >= toTrim)
  144. break;
  145. }
  146. if (totErased >= toTrim) { // done
  147. return totErased;
  148. }
  149. toTrim -= totErased;
  150. while (true) {
  151. size_t pershard = toTrim / maps_size + 1;
  152. for (auto& mc : maps) {
  153. const typename C::lock l(mc);
  154. mc.d_cachecachevalid = false;
  155. auto& sidx = boost::multi_index::get<S>(mc.d_map);
  156. size_t removed = 0;
  157. for (auto i = sidx.begin(); i != sidx.end() && removed < pershard; removed++) {
  158. container.preRemoval(*i);
  159. i = sidx.erase(i);
  160. mc.d_entriesCount--;
  161. totErased++;
  162. toTrim--;
  163. if (toTrim == 0) {
  164. return totErased;
  165. }
  166. }
  167. }
  168. }
  169. // Not reached
  170. return totErased;
  171. }
  172. template <typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps)
  173. {
  174. uint64_t delcount=0;
  175. for(auto& mc : maps) {
  176. WriteLock wl(&mc.d_mut);
  177. delcount += mc.d_map.size();
  178. mc.d_map.clear();
  179. }
  180. return delcount;
  181. }
  182. template <typename N, typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps, const std::string& match)
  183. {
  184. uint64_t delcount=0;
  185. string prefix(match);
  186. prefix.resize(prefix.size()-1);
  187. DNSName dprefix(prefix);
  188. for(auto& mc : maps) {
  189. WriteLock wl(&mc.d_mut);
  190. auto& idx = boost::multi_index::get<N>(mc.d_map);
  191. auto iter = idx.lower_bound(dprefix);
  192. auto start = iter;
  193. for(; iter != idx.end(); ++iter) {
  194. if(!iter->qname.isPartOf(dprefix)) {
  195. break;
  196. }
  197. delcount++;
  198. }
  199. idx.erase(start, iter);
  200. }
  201. return delcount;
  202. }
  203. template <typename N, typename T> uint64_t purgeExactLockedCollection(T& mc, const DNSName& qname)
  204. {
  205. uint64_t delcount=0;
  206. WriteLock wl(&mc.d_mut);
  207. auto& idx = boost::multi_index::get<N>(mc.d_map);
  208. auto range = idx.equal_range(qname);
  209. if(range.first != range.second) {
  210. delcount += distance(range.first, range.second);
  211. idx.erase(range.first, range.second);
  212. }
  213. return delcount;
  214. }
  215. template<typename S, typename Index>
  216. std::pair<typename Index::iterator,bool>
  217. lruReplacingInsert(Index& i,const typename Index::value_type& x)
  218. {
  219. std::pair<typename Index::iterator,bool> res = i.insert(x);
  220. if (!res.second) {
  221. moveCacheItemToBack<S>(i, res.first);
  222. res.second = i.replace(res.first, x);
  223. }
  224. return res;
  225. }