store_repl_heap.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 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"
24 #include "store_heap_replacement.h"
25 #include "wordlist.h"
26 
27 #include <queue>
28 
30 
31 static int nr_heap_policies = 0;
32 
34  void setPolicyNode (StoreEntry *, void *) const;
38  int count;
39  int nwalkers;
42  } type;
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 
62 void
63 HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
64 {
65  switch (type) {
66 
67  case TYPE_STORE_ENTRY:
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 
80 static 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 
100 static 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 = NULL;
113 
114  h->count -= 1;
115 }
116 
117 static void
118 heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
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 
138 static 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 NULL; /* done */
148 
149  entry = (StoreEntry *) heap_peep(h->theHeap, heap_walk->current++);
150 
151  return entry;
152 }
153 
154 static 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 
166 static 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 {
187 public:
188  std::queue<StoreEntry *> locked_entries;
190 };
191 
192 static 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 
201 try_again:
202 
203  if (heap_empty(h->theHeap))
204  return NULL; /* 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, NULL);
220  return entry;
221 }
222 
223 static 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 
251 static RemovalPurgeWalker *
252 heap_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 
268 static 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"))
303  heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
304  else if (!strcmp(keytype, "LFUDA"))
306  else if (!strcmp(keytype, "LRU"))
307  heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
308  else {
309  debugs(81, DBG_CRITICAL, "createRemovalPolicy_heap: Unknown key type \"" << keytype << "\". Using LRU");
310  heap_data->keyfunc = HeapKeyGen_StoreEntry_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 = NULL;
335 
336  policy->Dereferenced = heap_referenced;
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 
const char * _type
Definition: RemovalPolicy.h:40
#define assert(EX)
Definition: assert.h:17
RemovalPolicyNode repl
Definition: MemObject.h:167
SQUIDCEXTERN heap_t heap_peep(heap *, int n)
Definition: heap.c:281
int heap_nodes(heap *hp)
Definition: heap.c:294
double heap_key
Definition: heap.h:33
int unlock(const char *context)
Definition: store.cc:485
heap_key age
Definition: heap.h:57
#define xcalloc
Definition: membanger.c:57
SQUIDCEXTERN heap_key heap_peepminkey(heap *)
Definition: heap.c:257
#define safe_free(x)
Definition: xalloc.h:73
RemovalPolicyWalker *(* WalkInit)(RemovalPolicy *policy)
Definition: RemovalPolicy.h:50
char * key
Definition: wordlist.h:33
REMOVALPOLICYCREATE createRemovalPolicy_heap
#define DBG_CRITICAL
Definition: Debug.h:44
heap_key HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age)
enum HeapPolicyData::heap_entry_type type
heap_key HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age)
static void heap_purgeDone(RemovalPurgeWalker *walker)
static StoreEntry * heap_purgeNext(RemovalPurgeWalker *walker)
RemovalPolicy * REMOVALPOLICYCREATE(wordlist *args)
Definition: RemovalPolicy.h:80
static RemovalPurgeWalker * heap_purgeInit(RemovalPolicy *policy, int max_scan)
int locked() const
Definition: store.cc:1320
static RemovalPolicyWalker * heap_walkInit(RemovalPolicy *policy)
Definition: parse.c:104
SQUIDCEXTERN heap_t heap_update(heap *, heap_node *elm, heap_t dat)
Definition: heap.c:228
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:123
#define DBG_IMPORTANT
Definition: Debug.h:45
heap_key HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age)
static int nr_heap_policies
void(* Referenced)(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:48
static const StoreEntry * heap_walkNext(RemovalPolicyWalker *walker)
int heap_empty(heap *hp)
Definition: heap.c:306
void(* Add)(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:46
void fatal(const char *message)
Definition: fatal.cc:39
SQUIDCEXTERN heap_t heap_extractmin(heap *)
Definition: heap.c:188
void(* Free)(RemovalPolicy *policy)
Definition: RemovalPolicy.h:45
uint16_t flags
Definition: Store.h:173
RemovalPolicyNode repl
Definition: Store.h:163
MemObject * mem_obj
Definition: Store.h:162
static enum HeapPolicyData::heap_entry_type heap_guessType(StoreEntry *entry, RemovalPolicyNode *node)
static void heap_walkDone(RemovalPolicyWalker *walker)
static void heap_add(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
RemovalPolicy * _policy
Definition: RemovalPolicy.h:68
std::queue< StoreEntry * > locked_entries
void setPolicyNode(StoreEntry *, void *) const
SQUIDCEXTERN heap * new_heap(int init_size, heap_key_func gen_key)
Definition: heap.c:72
void(* Dereferenced)(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:49
heap_key heap_key_func(heap_t, heap_key)
Definition: heap.h:34
SQUIDCEXTERN heap_node * heap_insert(heap *hp, heap_t dat)
Definition: heap.c:117
static void heap_referenced(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
void(* Remove)(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:47
static void heap_free(RemovalPolicy *policy)
heap_key_func * keyfunc
Definition: heap.h:52
RemovalPolicy * _policy
Definition: RemovalPolicy.h:57
RemovalPolicy * policy
RemovalPurgeWalker *(* PurgeInit)(RemovalPolicy *policy, int max_scan)
Definition: RemovalPolicy.h:51
#define EBIT_TEST(flag, bit)
Definition: defines.h:107
static void heap_remove(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
#define NULL
Definition: types.h:166
wordlist * next
Definition: wordlist.h:34
void lock(const char *context)
Definition: store.cc:448
SQUIDCEXTERN heap_t heap_delete(heap *, heap_node *elm)
Definition: heap.c:142

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors