store_repl_heap.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
3 *
4 * Squid software is distributed under GPLv2+ license and includes
5 * contributions from numerous individuals and organizations.
6 * Please see the COPYING and CONTRIBUTORS files for details.
7 */
8
9/*
10 * DEBUG: section 81 Store HEAP Removal Policies
11 *
12 * Based on the ideas of the heap policy implemented by John Dilley of
13 * Hewlett Packard. Rewritten from scratch when modularizing the removal
14 * policy implementation of Squid.
15 *
16 * For details on the original heap policy work and the thinking behind see
17 * http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
18 */
19
20#include "squid.h"
21#include "heap.h"
22#include "MemObject.h"
23#include "Store.h"
25#include "wordlist.h"
26
27#include <queue>
28
30
31static int nr_heap_policies = 0;
32
34 void setPolicyNode (StoreEntry *, void *) const;
38 int count;
43};
44
45/* Hack to avoid having to remember the RemovalPolicyNode location.
46 * Needed by the purge walker.
47 */
50{
51 if (node == &entry->repl)
53
54 if (entry->mem_obj && node == &entry->mem_obj->repl)
56
57 fatal("Heap Replacement: Unknown StoreEntry node type");
58
60}
61
62void
63HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
64{
65 switch (type) {
66
68 entry->repl.data = value;
69 break ;
70
71 case TYPE_STORE_MEM:
72 entry->mem_obj->repl.data = value ;
73 break ;
74
75 default:
76 break;
77 }
78}
79
80static void
82{
83 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
84 assert(!node->data);
85
86 if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
87 return; /* We won't manage these.. they messes things up */
88
89 node->data = heap_insert(h->theHeap, entry);
90
91 h->count += 1;
92
93 if (!h->type)
94 h->type = heap_guessType(entry, node);
95
96 /* Add a little more variance to the aging factor */
97 h->theHeap->age += h->theHeap->age / 100000000;
98}
99
100static void
103{
104 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
105 heap_node *hnode = (heap_node *)node->data;
106
107 if (!hnode)
108 return;
109
110 heap_delete(h->theHeap, hnode);
111
112 node->data = nullptr;
113
114 h->count -= 1;
115}
116
117static void
120{
121 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
122 heap_node *hnode = (heap_node *)node->data;
123
124 if (!hnode)
125 return;
126
127 heap_update(h->theHeap, hnode, (StoreEntry *) entry);
128}
129
133
135 size_t current;
136};
137
138static const StoreEntry *
140{
141 HeapWalkData *heap_walk = (HeapWalkData *)walker->_data;
142 RemovalPolicy *policy = walker->_policy;
143 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
144 StoreEntry *entry;
145
146 if (heap_walk->current >= heap_nodes(h->theHeap))
147 return nullptr; /* done */
148
149 entry = (StoreEntry *) heap_peep(h->theHeap, heap_walk->current++);
150
151 return entry;
152}
153
154static void
156{
157 RemovalPolicy *policy = walker->_policy;
158 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
159 assert(strcmp(policy->_type, "heap") == 0);
160 assert(h->nwalkers > 0);
161 h->nwalkers -= 1;
162 safe_free(walker->_data);
163 delete walker;
164}
165
166static RemovalPolicyWalker *
168{
169 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
170 RemovalPolicyWalker *walker;
171 HeapWalkData *heap_walk;
172 h->nwalkers += 1;
173 walker = new RemovalPolicyWalker;
174 heap_walk = (HeapWalkData *)xcalloc(1, sizeof(*heap_walk));
175 heap_walk->current = 0;
176 walker->_policy = policy;
177 walker->_data = heap_walk;
178 walker->Next = heap_walkNext;
179 walker->Done = heap_walkDone;
180 return walker;
181}
182
186{
187public:
188 std::queue<StoreEntry *> locked_entries;
190};
191
192static StoreEntry *
194{
195 HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
196 RemovalPolicy *policy = walker->_policy;
197 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
198 StoreEntry *entry;
199 heap_key age;
200
201try_again:
202
203 if (heap_empty(h->theHeap))
204 return nullptr; /* done */
205
206 age = heap_peepminkey(h->theHeap);
207
208 entry = (StoreEntry *)heap_extractmin(h->theHeap);
209
210 if (entry->locked()) {
211
212 entry->lock("heap_purgeNext");
213 heap_walker->locked_entries.push(entry);
214
215 goto try_again;
216 }
217
218 heap_walker->min_age = age;
219 h->setPolicyNode(entry, nullptr);
220 return entry;
221}
222
223static void
225{
226 HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
227 RemovalPolicy *policy = walker->_policy;
228 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
229 assert(strcmp(policy->_type, "heap") == 0);
230 assert(h->nwalkers > 0);
231 h->nwalkers -= 1;
232
233 if (heap_walker->min_age > 0) {
234 h->theHeap->age = heap_walker->min_age;
235 debugs(81, 3, "Heap age set to " << h->theHeap->age);
236 }
237
238 // Reinsert the locked entries
239 while (!heap_walker->locked_entries.empty()) {
240 StoreEntry *entry = heap_walker->locked_entries.front();
241 heap_node *node = heap_insert(h->theHeap, entry);
242 h->setPolicyNode(entry, node);
243 entry->unlock("heap_purgeDone");
244 heap_walker->locked_entries.pop();
245 }
246
247 delete heap_walker;
248 delete walker;
249}
250
251static RemovalPurgeWalker *
252heap_purgeInit(RemovalPolicy * policy, int max_scan)
253{
254 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
255 RemovalPurgeWalker *walker;
256 HeapPurgeData *heap_walk;
257 h->nwalkers += 1;
258 walker = new RemovalPurgeWalker;
259 heap_walk = new HeapPurgeData;
260 walker->_policy = policy;
261 walker->_data = heap_walk;
262 walker->max_scan = max_scan;
263 walker->Next = heap_purgeNext;
264 walker->Done = heap_purgeDone;
265 return walker;
266}
267
268static void
270{
271 HeapPolicyData *h = (HeapPolicyData *)policy->_data;
272 /* Make some verification of the policy state */
273 assert(strcmp(policy->_type, "heap") == 0);
274 assert(h->nwalkers);
275 assert(h->count);
276 /* Ok, time to destroy this policy */
277 safe_free(h);
278 memset(policy, 0, sizeof(*policy));
279 delete policy;
280}
281
284{
285 RemovalPolicy *policy;
286 HeapPolicyData *heap_data;
287 const char *keytype;
288 /* Allocate the needed structures */
289 policy = new RemovalPolicy;
290 heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data));
291 /* Initialize the policy data */
292 heap_data->policy = policy;
293
294 if (args) {
295 keytype = args->key;
296 args = args->next;
297 } else {
298 debugs(81, DBG_IMPORTANT, "createRemovalPolicy_heap: No key type specified. Using LRU");
299 keytype = "LRU";
300 }
301
302 if (!strcmp(keytype, "GDSF"))
304 else if (!strcmp(keytype, "LFUDA"))
306 else if (!strcmp(keytype, "LRU"))
308 else {
309 debugs(81, DBG_CRITICAL, "ERROR: createRemovalPolicy_heap: Unknown key type \"" << keytype << "\". Using LRU");
311 }
312
313 /* No additional arguments expected */
314 while (args) {
315 debugs(81, DBG_IMPORTANT, "WARNING: discarding unknown removal policy '" << args->key << "'");
316 args = args->next;
317 }
318
319 heap_data->theHeap = new_heap(1000, heap_data->keyfunc);
320
321 heap_data->theHeap->age = 1.0;
322
323 /* Populate the policy structure */
324 policy->_type = "heap";
325
326 policy->_data = heap_data;
327
328 policy->Free = heap_free;
329
330 policy->Add = heap_add;
331
332 policy->Remove = heap_remove;
333
334 policy->Referenced = nullptr;
335
337
338 policy->WalkInit = heap_walkInit;
339
340 policy->PurgeInit = heap_purgeInit;
341
342 /* Increase policy usage count */
343 nr_heap_policies += 0;
344
345 return policy;
346}
347
RemovalPolicy * REMOVALPOLICYCREATE(wordlist *args)
Definition: RemovalPolicy.h:80
#define assert(EX)
Definition: assert.h:19
std::queue< StoreEntry * > locked_entries
RemovalPolicyNode repl
Definition: MemObject.h:196
RemovalPolicy * _policy
Definition: RemovalPolicy.h:60
const char * _type
Definition: RemovalPolicy.h:43
void(* Free)(RemovalPolicy *policy)
Definition: RemovalPolicy.h:45
void(* Referenced)(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:48
void(* Add)(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:46
RemovalPurgeWalker *(* PurgeInit)(RemovalPolicy *policy, int max_scan)
Definition: RemovalPolicy.h:51
void(* Dereferenced)(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:49
void(* Remove)(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:47
RemovalPolicyWalker *(* WalkInit)(RemovalPolicy *policy)
Definition: RemovalPolicy.h:50
RemovalPolicy * _policy
Definition: RemovalPolicy.h:71
uint16_t flags
Definition: Store.h:230
int locked() const
Definition: Store.h:144
int unlock(const char *context)
Definition: store.cc:444
void lock(const char *context)
Definition: store.cc:420
RemovalPolicyNode repl
Definition: Store.h:220
MemObject * mem_obj
Definition: Store.h:219
char * key
Definition: wordlist.h:32
wordlist * next
Definition: wordlist.h:33
#define DBG_IMPORTANT
Definition: Stream.h:41
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:196
#define DBG_CRITICAL
Definition: Stream.h:40
#define EBIT_TEST(flag, bit)
Definition: defines.h:69
@ ENTRY_SPECIAL
Definition: enums.h:84
void fatal(const char *message)
Definition: fatal.cc:28
int heap_empty(heap *hp)
Definition: heap.c:306
int heap_nodes(heap *hp)
Definition: heap.c:294
SQUIDCEXTERN heap_t heap_peep(heap *, int n)
Definition: heap.c:281
SQUIDCEXTERN heap_t heap_update(heap *, heap_node *elm, heap_t dat)
Definition: heap.c:228
double heap_key
Definition: heap.h:33
SQUIDCEXTERN heap_t heap_delete(heap *, heap_node *elm)
Definition: heap.c:142
SQUIDCEXTERN heap_key heap_peepminkey(heap *)
Definition: heap.c:257
SQUIDCEXTERN heap_node * heap_insert(heap *hp, heap_t dat)
Definition: heap.c:117
SQUIDCEXTERN heap * new_heap(int init_size, heap_key_func gen_key)
Definition: heap.c:72
heap_key heap_key_func(heap_t, heap_key)
Definition: heap.h:34
SQUIDCEXTERN heap_t heap_extractmin(heap *)
Definition: heap.c:188
heap_key HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age)
heap_key HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age)
heap_key HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age)
static void heap_purgeDone(RemovalPurgeWalker *walker)
static RemovalPolicyWalker * heap_walkInit(RemovalPolicy *policy)
static const StoreEntry * heap_walkNext(RemovalPolicyWalker *walker)
static void heap_referenced(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
static enum HeapPolicyData::heap_entry_type heap_guessType(StoreEntry *entry, RemovalPolicyNode *node)
static RemovalPurgeWalker * heap_purgeInit(RemovalPolicy *policy, int max_scan)
static void heap_add(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
static void heap_free(RemovalPolicy *policy)
static void heap_remove(RemovalPolicy *policy, StoreEntry *, RemovalPolicyNode *node)
static int nr_heap_policies
static void heap_walkDone(RemovalPolicyWalker *walker)
REMOVALPOLICYCREATE createRemovalPolicy_heap
static StoreEntry * heap_purgeNext(RemovalPurgeWalker *walker)
heap_key_func * keyfunc
enum HeapPolicyData::heap_entry_type type
void setPolicyNode(StoreEntry *, void *) const
RemovalPolicy * policy
Definition: heap.h:52
heap_key age
Definition: heap.h:57
Definition: parse.c:104
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
#define safe_free(x)
Definition: xalloc.h:73

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors