← Back to branch summary

~clint-fewbar/ubuntu/precise/squid3/ignore-sighup-early

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Luigi Gangitano
  • Date: 2006-11-11 10:32:06 UTC
  • Revision ID: james.westby@ubuntu.com-20061111103206-f3p0r9g0vq44rp3r
Tags: upstream-3.0.PRE5
Import upstream version 3.0.PRE5

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/repl/heap/store_repl_heap.cc
 
1
 
 
2
/*
 
3
 * $Id: store_repl_heap.cc,v 1.21 2006/08/21 00:50:47 robertc Exp $
 
4
 *
 
5
 * DEBUG: section ?     HEAP based 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
{
 
57
    void setPolicyNode (StoreEntry *, void *) const;
 
58
    RemovalPolicy *policy;
 
59
    heap *theHeap;
 
60
    heap_key_func *keyfunc;
 
61
    int count;
 
62
    int nwalkers;
 
63
    enum heap_entry_type {
 
64
        TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
 
65
    } type;
 
66
};
 
67
 
 
68
/* Hack to avoid having to remember the RemovalPolicyNode location.
 
69
 * Needed by the purge walker.
 
70
 */
 
71
static enum HeapPolicyData::heap_entry_type
 
72
heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
 
73
{
 
74
    if (node == &entry->repl)
 
75
        return HeapPolicyData::TYPE_STORE_ENTRY;
 
76
 
 
77
    if (entry->mem_obj && node == &entry->mem_obj->repl)
 
78
        return HeapPolicyData::TYPE_STORE_MEM;
 
79
 
 
80
    fatal("Heap Replacement: Unknown StoreEntry node type");
 
81
 
 
82
    return HeapPolicyData::TYPE_UNKNOWN;
 
83
}
 
84
 
 
85
void
 
86
HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
 
87
{
 
88
    switch (type) {
 
89
 
 
90
    case TYPE_STORE_ENTRY:
 
91
        entry->repl.data = value;
 
92
        break ;
 
93
 
 
94
    case TYPE_STORE_MEM:
 
95
        entry->mem_obj->repl.data = value ;
 
96
        break ;
 
97
 
 
98
    default:
 
99
        break;
 
100
    }
 
101
}
 
102
 
 
103
static void
 
104
heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
 
105
{
 
106
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
107
    assert(!node->data);
 
108
 
 
109
    if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
 
110
        return;                 /* We won't manage these.. they messes things up */
 
111
 
 
112
    node->data = heap_insert(heap->theHeap, entry);
 
113
 
 
114
    heap->count += 1;
 
115
 
 
116
    if (!heap->type)
 
117
        heap->type = heap_guessType(entry, node);
 
118
 
 
119
    /* Add a little more variance to the aging factor */
 
120
    heap->theHeap->age += heap->theHeap->age / 100000000;
 
121
}
 
122
 
 
123
static void
 
124
heap_remove(RemovalPolicy * policy, StoreEntry * entry,
 
125
            RemovalPolicyNode * node)
 
126
{
 
127
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
128
    heap_node *hnode = (heap_node *)node->data;
 
129
 
 
130
    if (!hnode)
 
131
        return;
 
132
 
 
133
    heap_delete(heap->theHeap, hnode);
 
134
 
 
135
    node->data = NULL;
 
136
 
 
137
    heap->count -= 1;
 
138
}
 
139
 
 
140
static void
 
141
heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 
142
                RemovalPolicyNode * node)
 
143
{
 
144
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
145
    heap_node *hnode = (heap_node *)node->data;
 
146
 
 
147
    if (!hnode)
 
148
        return;
 
149
 
 
150
    heap_update(heap->theHeap, hnode, (StoreEntry *) entry);
 
151
}
 
152
 
 
153
/** RemovalPolicyWalker **/
 
154
 
 
155
typedef struct _HeapWalkData HeapWalkData;
 
156
 
 
157
struct _HeapWalkData
 
158
{
 
159
    size_t current;
 
160
};
 
161
 
 
162
static const StoreEntry *
 
163
heap_walkNext(RemovalPolicyWalker * walker)
 
164
{
 
165
    HeapWalkData *heap_walk = (HeapWalkData *)walker->_data;
 
166
    RemovalPolicy *policy = walker->_policy;
 
167
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
168
    StoreEntry *entry;
 
169
 
 
170
    if (heap_walk->current >= heap_nodes(heap->theHeap))
 
171
        return NULL;            /* done */
 
172
 
 
173
    entry = (StoreEntry *) heap_peep(heap->theHeap, heap_walk->current++);
 
174
 
 
175
    return entry;
 
176
}
 
177
 
 
178
static void
 
179
heap_walkDone(RemovalPolicyWalker * walker)
 
180
{
 
181
    RemovalPolicy *policy = walker->_policy;
 
182
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
183
    assert(strcmp(policy->_type, "heap") == 0);
 
184
    assert(heap->nwalkers > 0);
 
185
    heap->nwalkers -= 1;
 
186
    safe_free(walker->_data);
 
187
    delete walker;
 
188
}
 
189
 
 
190
static RemovalPolicyWalker *
 
191
heap_walkInit(RemovalPolicy * policy)
 
192
{
 
193
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
194
    RemovalPolicyWalker *walker;
 
195
    HeapWalkData *heap_walk;
 
196
    heap->nwalkers += 1;
 
197
    walker = new RemovalPolicyWalker;
 
198
    heap_walk = (HeapWalkData *)xcalloc(1, sizeof(*heap_walk));
 
199
    heap_walk->current = 0;
 
200
    walker->_policy = policy;
 
201
    walker->_data = heap_walk;
 
202
    walker->Next = heap_walkNext;
 
203
    walker->Done = heap_walkDone;
 
204
    return walker;
 
205
}
 
206
 
 
207
/** RemovalPurgeWalker **/
 
208
 
 
209
typedef struct _HeapPurgeData HeapPurgeData;
 
210
 
 
211
struct _HeapPurgeData
 
212
{
 
213
    link_list *locked_entries;
 
214
    heap_key min_age;
 
215
};
 
216
 
 
217
static StoreEntry *
 
218
heap_purgeNext(RemovalPurgeWalker * walker)
 
219
{
 
220
    HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 
221
    RemovalPolicy *policy = walker->_policy;
 
222
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
223
    StoreEntry *entry;
 
224
    heap_key age;
 
225
 
 
226
try_again:
 
227
 
 
228
    if (!heap_nodes(heap->theHeap) > 0)
 
229
        return NULL;            /* done */
 
230
 
 
231
    age = heap_peepminkey(heap->theHeap);
 
232
 
 
233
    entry = (StoreEntry *)heap_extractmin(heap->theHeap);
 
234
 
 
235
    if (storeEntryLocked(entry)) {
 
236
 
 
237
        entry->lock()
 
238
 
 
239
        ;
 
240
        linklistPush(&heap_walker->locked_entries, entry);
 
241
 
 
242
        goto try_again;
 
243
    }
 
244
 
 
245
    heap_walker->min_age = age;
 
246
    heap->setPolicyNode(entry, NULL);
 
247
    return entry;
 
248
}
 
249
 
 
250
static void
 
251
heap_purgeDone(RemovalPurgeWalker * walker)
 
252
{
 
253
    HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 
254
    RemovalPolicy *policy = walker->_policy;
 
255
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
256
    StoreEntry *entry;
 
257
    assert(strcmp(policy->_type, "heap") == 0);
 
258
    assert(heap->nwalkers > 0);
 
259
    heap->nwalkers -= 1;
 
260
 
 
261
    if (heap_walker->min_age > 0) {
 
262
        heap->theHeap->age = heap_walker->min_age;
 
263
        debug(81, 3) ("heap_purgeDone: Heap age set to %f\n",
 
264
                      (double) heap->theHeap->age);
 
265
    }
 
266
 
 
267
    /*
 
268
     * Reinsert the locked entries
 
269
     */
 
270
    while ((entry = (StoreEntry *)linklistShift(&heap_walker->locked_entries))) {
 
271
        heap_node *node = heap_insert(heap->theHeap, entry);
 
272
        heap->setPolicyNode(entry, node);
 
273
        entry->unlock();
 
274
    }
 
275
 
 
276
    safe_free(walker->_data);
 
277
    delete walker;
 
278
}
 
279
 
 
280
static RemovalPurgeWalker *
 
281
heap_purgeInit(RemovalPolicy * policy, int max_scan)
 
282
{
 
283
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
284
    RemovalPurgeWalker *walker;
 
285
    HeapPurgeData *heap_walk;
 
286
    heap->nwalkers += 1;
 
287
    walker = new RemovalPurgeWalker;
 
288
    heap_walk = (HeapPurgeData *)xcalloc(1, sizeof(*heap_walk));
 
289
    heap_walk->min_age = 0.0;
 
290
    heap_walk->locked_entries = NULL;
 
291
    walker->_policy = policy;
 
292
    walker->_data = heap_walk;
 
293
    walker->max_scan = max_scan;
 
294
    walker->Next = heap_purgeNext;
 
295
    walker->Done = heap_purgeDone;
 
296
    return walker;
 
297
}
 
298
 
 
299
static void
 
300
heap_free(RemovalPolicy * policy)
 
301
{
 
302
    HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 
303
    /* Make some verification of the policy state */
 
304
    assert(strcmp(policy->_type, "heap") == 0);
 
305
    assert(heap->nwalkers);
 
306
    assert(heap->count);
 
307
    /* Ok, time to destroy this policy */
 
308
    safe_free(heap);
 
309
    memset(policy, 0, sizeof(*policy));
 
310
    delete policy;
 
311
}
 
312
 
 
313
RemovalPolicy *
 
314
createRemovalPolicy_heap(wordlist * args)
 
315
{
 
316
    RemovalPolicy *policy;
 
317
    HeapPolicyData *heap_data;
 
318
    const char *keytype;
 
319
    /* Allocate the needed structures */
 
320
    policy = new RemovalPolicy;
 
321
    heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data));
 
322
    /* Initialize the policy data */
 
323
    heap_data->policy = policy;
 
324
 
 
325
    if (args) {
 
326
        keytype = args->key;
 
327
        args = args->next;
 
328
    } else {
 
329
        debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
 
330
        keytype = "LRU";
 
331
    }
 
332
 
 
333
    if (!strcmp(keytype, "GDSF"))
 
334
        heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
 
335
    else if (!strcmp(keytype, "LFUDA"))
 
336
        heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
 
337
    else if (!strcmp(keytype, "LRU"))
 
338
        heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 
339
    else {
 
340
        debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
 
341
                      keytype);
 
342
        heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 
343
    }
 
344
 
 
345
    /* No additional arguments expected */
 
346
    assert(!args);
 
347
 
 
348
    heap_data->theHeap = new_heap(1000, heap_data->keyfunc);
 
349
 
 
350
    heap_data->theHeap->age = 1.0;
 
351
 
 
352
    /* Populate the policy structure */
 
353
    policy->_type = "heap";
 
354
 
 
355
    policy->_data = heap_data;
 
356
 
 
357
    policy->Free = heap_free;
 
358
 
 
359
    policy->Add = heap_add;
 
360
 
 
361
    policy->Remove = heap_remove;
 
362
 
 
363
    policy->Referenced = NULL;
 
364
 
 
365
    policy->Dereferenced = heap_referenced;
 
366
 
 
367
    policy->WalkInit = heap_walkInit;
 
368
 
 
369
    policy->PurgeInit = heap_purgeInit;
 
370
 
 
371
    /* Increase policy usage count */
 
372
    nr_heap_policies += 0;
 
373
 
 
374
    return policy;
 
375
}