← Back to branch summary

~yolanda.robla/+junk/squid3_fresh_branch

« back to all changes in this revision

Viewing changes to src/repl/heap/store_repl_heap.cc

  • Committer: yolanda.robla at canonical
  • Date: 2013-05-27 10:52:43 UTC
  • Revision ID: yolanda.robla@canonical.com-20130527105243-mcd0nscika17sl4w
first branch

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/repl/heap/store_repl_heap.cc
 
1
 
 
2
/*
 
3
 * $Id$
 
4
 *
 
5
 * DEBUG: section 81    Store HEAP Removal Policies
 
6
 * AUTHOR: Henrik Nordstrom
 
7
 *
 
8
 * Based on the ideas of the heap policy implemented by John Dilley of
 
9
 * Hewlett Packard. Rewritten from scratch when modularizing the removal
 
10
 * policy implementation of Squid.
 
11
 *
 
12
 * For details on the original heap policy work and the thinking behind see
 
13
 * http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
 
14
 *
 
15
 *
 
16
 * SQUID Web Proxy Cache          http://www.squid-cache.org/
 
17
 * ----------------------------------------------------------
 
18
 *
 
19
 *  Squid is the result of efforts by numerous individuals from
 
20
 *  the Internet community; see the CONTRIBUTORS file for full
 
21
 *  details.   Many organizations have provided support for Squid's
 
22
 *  development; see the SPONSORS file for full details.  Squid is
 
23
 *  Copyrighted (C) 2001 by the Regents of the University of
 
24
 *  California; see the COPYRIGHT file for full details.  Squid
 
25
 *  incorporates software developed and/or copyrighted by other
 
26
 *  sources; see the CREDITS file for full details.
 
27
 *
 
28
 *  This program is free software; you can redistribute it and/or modify
 
29
 *  it under the terms of the GNU General Public License as published by
 
30
 *  the Free Software Foundation; either version 2 of the License, or
 
31
 *  (at your option) any later version.
 
32
 *
 
33
 *  This program is distributed in the hope that it will be useful,
 
34
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
35
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
36
 *  GNU General Public License for more details.
 
37
 *
 
38
 *  You should have received a copy of the GNU General Public License
 
39
 *  along with this program; if not, write to the Free Software
 
40
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 
41
 *
 
42
 */
 
43
 
 
44
#include "squid.h"
 
45
#include "heap.h"
 
46
#include "store_heap_replacement.h"
 
47
#include "Store.h"
 
48
#include "MemObject.h"
 
49
#include "wordlist.h"
 
50
 
 
51
REMOVALPOLICYCREATE createRemovalPolicy_heap;
 
52
 
 
53
static int nr_heap_policies = 0;
 
54
 
 
55
struct HeapPolicyData {
 
56
    void setPolicyNode (StoreEntry *, void *) const;
 
57
    RemovalPolicy *policy;
 
58
    heap *theHeap;
 
59
    heap_key_func *keyfunc;
 
60
    int count;
 
61
    int nwalkers;
 
62
    enum heap_entry_type {
 
63
        TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
 
64
    } type;
 
65
};
 
66
 
 
67
/* Hack to avoid having to remember the RemovalPolicyNode location.
 
68
 * Needed by the purge walker.
 
69
 */
 
70
static enum HeapPolicyData::heap_entry_type
 
71
heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
 
72
{
 
73
    if (node == &entry->repl)
 
74
        return HeapPolicyData::TYPE_STORE_ENTRY;
 
75
 
 
76
    if (entry->mem_obj && node == &entry->mem_obj->repl)
 
77
        return HeapPolicyData::TYPE_STORE_MEM;
 
78
 
 
79
    fatal("Heap Replacement: Unknown StoreEntry node type");
 
80
 
 
81
    return HeapPolicyData::TYPE_UNKNOWN;
 
82
}
 
83
 
 
84
void
 
85
HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
 
86
{
 
87
    switch (type) {
 
88
 
 
89
    case TYPE_STORE_ENTRY:
 
90
        entry->repl.data = value;
 
91
        break ;
 
92
 
 
93
    case TYPE_STORE_MEM:
 
94
        entry->mem_obj->repl.data = value ;
 
95
        break ;
 
96
 
 
97
    default:
 
98
        break;
 
99
    }
 
100
}
 
101
 
 
102
static void
 
103
heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
 
104
{
 
105
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
106
    assert(!node->data);
 
107
 
 
108
    if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
 
109
        return;                 /* We won't manage these.. they messes things up */
 
110
 
 
111
    node->data = heap_insert(heap->theHeap, entry);
 
112
 
 
113
    heap->count += 1;
 
114
 
 
115
    if (!heap->type)
 
116
        heap->type = heap_guessType(entry, node);
 
117
 
 
118
    /* Add a little more variance to the aging factor */
 
119
    heap->theHeap->age += heap->theHeap->age / 100000000;
 
120
}
 
121
 
 
122
static void
 
123
heap_remove(RemovalPolicy * policy, StoreEntry * entry,
 
124
            RemovalPolicyNode * node)
 
125
{
 
126
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
127
    heap_node *hnode = (heap_node *)node->data;
 
128
 
 
129
    if (!hnode)
 
130
        return;
 
131
 
 
132
    heap_delete(heap->theHeap, hnode);
 
133
 
 
134
    node->data = NULL;
 
135
 
 
136
    heap->count -= 1;
 
137
}
 
138
 
 
139
static void
 
140
heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 
141
                RemovalPolicyNode * node)
 
142
{
 
143
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
144
    heap_node *hnode = (heap_node *)node->data;
 
145
 
 
146
    if (!hnode)
 
147
        return;
 
148
 
 
149
    heap_update(heap->theHeap, hnode, (StoreEntry *) entry);
 
150
}
 
151
 
 
152
/** RemovalPolicyWalker **/
 
153
 
 
154
typedef struct _HeapWalkData HeapWalkData;
 
155
 
 
156
struct _HeapWalkData {
 
157
    size_t current;
 
158
};
 
159
 
 
160
static const StoreEntry *
 
161
heap_walkNext(RemovalPolicyWalker * walker)
 
162
{
 
163
    HeapWalkData *heap_walk = (HeapWalkData *)walker->_data;
 
164
    RemovalPolicy *policy = walker->_policy;
 
165
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
166
    StoreEntry *entry;
 
167
 
 
168
    if (heap_walk->current >= heap_nodes(heap->theHeap))
 
169
        return NULL;            /* done */
 
170
 
 
171
    entry = (StoreEntry *) heap_peep(heap->theHeap, heap_walk->current++);
 
172
 
 
173
    return entry;
 
174
}
 
175
 
 
176
static void
 
177
heap_walkDone(RemovalPolicyWalker * walker)
 
178
{
 
179
    RemovalPolicy *policy = walker->_policy;
 
180
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
181
    assert(strcmp(policy->_type, "heap") == 0);
 
182
    assert(heap->nwalkers > 0);
 
183
    heap->nwalkers -= 1;
 
184
    safe_free(walker->_data);
 
185
    delete walker;
 
186
}
 
187
 
 
188
static RemovalPolicyWalker *
 
189
heap_walkInit(RemovalPolicy * policy)
 
190
{
 
191
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
192
    RemovalPolicyWalker *walker;
 
193
    HeapWalkData *heap_walk;
 
194
    heap->nwalkers += 1;
 
195
    walker = new RemovalPolicyWalker;
 
196
    heap_walk = (HeapWalkData *)xcalloc(1, sizeof(*heap_walk));
 
197
    heap_walk->current = 0;
 
198
    walker->_policy = policy;
 
199
    walker->_data = heap_walk;
 
200
    walker->Next = heap_walkNext;
 
201
    walker->Done = heap_walkDone;
 
202
    return walker;
 
203
}
 
204
 
 
205
/** RemovalPurgeWalker **/
 
206
 
 
207
typedef struct _HeapPurgeData HeapPurgeData;
 
208
 
 
209
struct _HeapPurgeData {
 
210
    link_list *locked_entries;
 
211
    heap_key min_age;
 
212
};
 
213
 
 
214
static StoreEntry *
 
215
heap_purgeNext(RemovalPurgeWalker * walker)
 
216
{
 
217
    HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 
218
    RemovalPolicy *policy = walker->_policy;
 
219
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
220
    StoreEntry *entry;
 
221
    heap_key age;
 
222
 
 
223
try_again:
 
224
 
 
225
    if (!heap_nodes(heap->theHeap) > 0)
 
226
        return NULL;            /* done */
 
227
 
 
228
    age = heap_peepminkey(heap->theHeap);
 
229
 
 
230
    entry = (StoreEntry *)heap_extractmin(heap->theHeap);
 
231
 
 
232
    if (entry->locked()) {
 
233
 
 
234
        entry->lock();
 
235
        linklistPush(&heap_walker->locked_entries, entry);
 
236
 
 
237
        goto try_again;
 
238
    }
 
239
 
 
240
    heap_walker->min_age = age;
 
241
    heap->setPolicyNode(entry, NULL);
 
242
    return entry;
 
243
}
 
244
 
 
245
static void
 
246
heap_purgeDone(RemovalPurgeWalker * walker)
 
247
{
 
248
    HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 
249
    RemovalPolicy *policy = walker->_policy;
 
250
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
251
    StoreEntry *entry;
 
252
    assert(strcmp(policy->_type, "heap") == 0);
 
253
    assert(heap->nwalkers > 0);
 
254
    heap->nwalkers -= 1;
 
255
 
 
256
    if (heap_walker->min_age > 0) {
 
257
        heap->theHeap->age = heap_walker->min_age;
 
258
        debugs(81, 3, "heap_purgeDone: Heap age set to " << heap->theHeap->age  );
 
259
    }
 
260
 
 
261
    /*
 
262
     * Reinsert the locked entries
 
263
     */
 
264
    while ((entry = (StoreEntry *)linklistShift(&heap_walker->locked_entries))) {
 
265
        heap_node *node = heap_insert(heap->theHeap, entry);
 
266
        heap->setPolicyNode(entry, node);
 
267
        entry->unlock();
 
268
    }
 
269
 
 
270
    safe_free(walker->_data);
 
271
    delete walker;
 
272
}
 
273
 
 
274
static RemovalPurgeWalker *
 
275
heap_purgeInit(RemovalPolicy * policy, int max_scan)
 
276
{
 
277
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
278
    RemovalPurgeWalker *walker;
 
279
    HeapPurgeData *heap_walk;
 
280
    heap->nwalkers += 1;
 
281
    walker = new RemovalPurgeWalker;
 
282
    heap_walk = (HeapPurgeData *)xcalloc(1, sizeof(*heap_walk));
 
283
    heap_walk->min_age = 0.0;
 
284
    heap_walk->locked_entries = NULL;
 
285
    walker->_policy = policy;
 
286
    walker->_data = heap_walk;
 
287
    walker->max_scan = max_scan;
 
288
    walker->Next = heap_purgeNext;
 
289
    walker->Done = heap_purgeDone;
 
290
    return walker;
 
291
}
 
292
 
 
293
static void
 
294
heap_free(RemovalPolicy * policy)
 
295
{
 
296
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
297
    /* Make some verification of the policy state */
 
298
    assert(strcmp(policy->_type, "heap") == 0);
 
299
    assert(heap->nwalkers);
 
300
    assert(heap->count);
 
301
    /* Ok, time to destroy this policy */
 
302
    safe_free(heap);
 
303
    memset(policy, 0, sizeof(*policy));
 
304
    delete policy;
 
305
}
 
306
 
 
307
RemovalPolicy *
 
308
createRemovalPolicy_heap(wordlist * args)
 
309
{
 
310
    RemovalPolicy *policy;
 
311
    HeapPolicyData *heap_data;
 
312
    const char *keytype;
 
313
    /* Allocate the needed structures */
 
314
    policy = new RemovalPolicy;
 
315
    heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data));
 
316
    /* Initialize the policy data */
 
317
    heap_data->policy = policy;
 
318
 
 
319
    if (args) {
 
320
        keytype = args->key;
 
321
        args = args->next;
 
322
    } else {
 
323
        debugs(81, 1, "createRemovalPolicy_heap: No key type specified. Using LRU");
 
324
        keytype = "LRU";
 
325
    }
 
326
 
 
327
    if (!strcmp(keytype, "GDSF"))
 
328
        heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
 
329
    else if (!strcmp(keytype, "LFUDA"))
 
330
        heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
 
331
    else if (!strcmp(keytype, "LRU"))
 
332
        heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 
333
    else {
 
334
        debugs(81, 0, "createRemovalPolicy_heap: Unknown key type \"" << keytype << "\". Using LRU");
 
335
        heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 
336
    }
 
337
 
 
338
    /* No additional arguments expected */
 
339
    while (args) {
 
340
        debugs(81, DBG_IMPORTANT, "WARNING: discarding unknown removal policy '" << args->key << "'");
 
341
        args = args->next;
 
342
    }
 
343
 
 
344
    heap_data->theHeap = new_heap(1000, heap_data->keyfunc);
 
345
 
 
346
    heap_data->theHeap->age = 1.0;
 
347
 
 
348
    /* Populate the policy structure */
 
349
    policy->_type = "heap";
 
350
 
 
351
    policy->_data = heap_data;
 
352
 
 
353
    policy->Free = heap_free;
 
354
 
 
355
    policy->Add = heap_add;
 
356
 
 
357
    policy->Remove = heap_remove;
 
358
 
 
359
    policy->Referenced = NULL;
 
360
 
 
361
    policy->Dereferenced = heap_referenced;
 
362
 
 
363
    policy->WalkInit = heap_walkInit;
 
364
 
 
365
    policy->PurgeInit = heap_purgeInit;
 
366
 
 
367
    /* Increase policy usage count */
 
368
    nr_heap_policies += 0;
 
369
 
 
370
    return policy;
 
371
}