]>
Commit | Line | Data |
---|---|---|
6a566b9c | 1 | |
2 | /* | |
2b6662ba | 3 | * $Id: store_repl_lru.cc,v 1.6 2001/01/12 00:37:36 wessels Exp $ |
6a566b9c | 4 | * |
5 | * DEBUG: section ? LRU Removal policy | |
6 | * AUTHOR: Henrik Nordstrom | |
7 | * | |
2b6662ba | 8 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
6a566b9c | 9 | * ---------------------------------------------------------- |
10 | * | |
2b6662ba | 11 | * Squid is the result of efforts by numerous individuals from |
12 | * the Internet community; see the CONTRIBUTORS file for full | |
13 | * details. Many organizations have provided support for Squid's | |
14 | * development; see the SPONSORS file for full details. Squid is | |
15 | * Copyrighted (C) 2001 by the Regents of the University of | |
16 | * California; see the COPYRIGHT file for full details. Squid | |
17 | * incorporates software developed and/or copyrighted by other | |
18 | * sources; see the CREDITS file for full details. | |
6a566b9c | 19 | * |
20 | * This program is free software; you can redistribute it and/or modify | |
21 | * it under the terms of the GNU General Public License as published by | |
22 | * the Free Software Foundation; either version 2 of the License, or | |
23 | * (at your option) any later version. | |
24 | * | |
25 | * This program is distributed in the hope that it will be useful, | |
26 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
27 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
28 | * GNU General Public License for more details. | |
29 | * | |
30 | * You should have received a copy of the GNU General Public License | |
31 | * along with this program; if not, write to the Free Software | |
32 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. | |
33 | * | |
34 | */ | |
35 | ||
36 | #include "squid.h" | |
37 | ||
38 | REMOVALPOLICYCREATE createRemovalPolicy_lru; | |
39 | ||
40 | typedef struct _LruPolicyData LruPolicyData; | |
41 | struct _LruPolicyData { | |
42 | RemovalPolicy *policy; | |
43 | dlink_list list; | |
44 | int count; | |
45 | int nwalkers; | |
9f913cf1 | 46 | enum heap_entry_type { |
47 | TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM | |
48 | } type; | |
6a566b9c | 49 | }; |
50 | ||
51 | /* Hack to avoid having to remember the RemovalPolicyNode location. | |
52 | * Needed by the purge walker to clear the policy information | |
53 | */ | |
54 | static enum heap_entry_type | |
55 | repl_guessType(StoreEntry * entry, RemovalPolicyNode * node) | |
56 | { | |
57 | if (node == &entry->repl) | |
58 | return TYPE_STORE_ENTRY; | |
59 | if (entry->mem_obj && node == &entry->mem_obj->repl) | |
60 | return TYPE_STORE_MEM; | |
61 | fatal("Heap Replacement: Unknown StoreEntry node type"); | |
62 | return TYPE_UNKNOWN; | |
63 | } | |
64 | #define SET_POLICY_NODE(entry,value) \ | |
65 | switch(lru->type) { \ | |
66 | case TYPE_STORE_ENTRY: entry->repl.data = value; break ; \ | |
67 | case TYPE_STORE_MEM: entry->mem_obj->repl.data = value ; break ; \ | |
68 | default: break; \ | |
69 | } | |
70 | ||
71 | typedef struct _LruNode LruNode; | |
9f913cf1 | 72 | struct _LruNode { |
6a566b9c | 73 | /* Note: the dlink_node MUST be the first member of the LruNode |
74 | * structure. This member is later pointer typecasted to LruNode *. | |
75 | */ | |
76 | dlink_node node; | |
77 | }; | |
78 | ||
79 | static MemPool *lru_node_pool = NULL; | |
80 | static int nr_lru_policies = 0; | |
81 | ||
82 | static void | |
83 | lru_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) | |
84 | { | |
85 | LruPolicyData *lru = policy->_data; | |
86 | LruNode *lru_node; | |
87 | assert(!node->data); | |
88 | node->data = lru_node = memPoolAlloc(lru_node_pool); | |
89 | dlinkAddTail(entry, &lru_node->node, &lru->list); | |
90 | lru->count += 1; | |
91 | if (!lru->type) | |
92 | lru->type = repl_guessType(entry, node); | |
93 | } | |
94 | ||
95 | static void | |
96 | lru_remove(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) | |
97 | { | |
98 | LruPolicyData *lru = policy->_data; | |
99 | LruNode *lru_node = node->data; | |
100 | if (!lru_node) | |
101 | return; | |
75240ca9 | 102 | /* |
103 | * It seems to be possible for an entry to exist in the hash | |
104 | * but not be in the LRU list, so check for that case rather | |
105 | * than suffer a NULL pointer access. | |
106 | */ | |
107 | if (NULL == lru_node->node.data) | |
108 | return; | |
6a566b9c | 109 | assert(lru_node->node.data == entry); |
110 | node->data = NULL; | |
111 | dlinkDelete(&lru_node->node, &lru->list); | |
112 | memPoolFree(lru_node_pool, lru_node); | |
113 | lru->count -= 1; | |
114 | } | |
115 | ||
116 | static void | |
117 | lru_referenced(RemovalPolicy * policy, const StoreEntry * entry, | |
118 | RemovalPolicyNode * node) | |
119 | { | |
120 | LruPolicyData *lru = policy->_data; | |
121 | LruNode *lru_node = node->data; | |
122 | if (!lru_node) | |
123 | return; | |
124 | dlinkDelete(&lru_node->node, &lru->list); | |
125 | dlinkAddTail((void *) entry, &lru_node->node, &lru->list); | |
126 | } | |
127 | ||
128 | /** RemovalPolicyWalker **/ | |
129 | ||
130 | typedef struct _LruWalkData LruWalkData; | |
9f913cf1 | 131 | struct _LruWalkData { |
6a566b9c | 132 | LruNode *current; |
133 | }; | |
134 | ||
135 | const StoreEntry * | |
136 | lru_walkNext(RemovalPolicyWalker * walker) | |
137 | { | |
138 | LruWalkData *lru_walk = walker->_data; | |
139 | LruNode *lru_node = lru_walk->current; | |
140 | if (!lru_node) | |
141 | return NULL; | |
142 | lru_walk->current = (LruNode *) lru_node->node.next; | |
143 | return (StoreEntry *) lru_node->node.data; | |
144 | } | |
145 | ||
146 | static void | |
147 | lru_walkDone(RemovalPolicyWalker * walker) | |
148 | { | |
149 | RemovalPolicy *policy = walker->_policy; | |
150 | LruPolicyData *lru = policy->_data; | |
151 | assert(strcmp(policy->_type, "lru") == 0); | |
152 | assert(lru->nwalkers > 0); | |
153 | lru->nwalkers -= 1; | |
154 | safe_free(walker->_data); | |
155 | cbdataFree(walker); | |
156 | } | |
157 | ||
158 | static RemovalPolicyWalker * | |
159 | lru_walkInit(RemovalPolicy * policy) | |
160 | { | |
161 | LruPolicyData *lru = policy->_data; | |
162 | RemovalPolicyWalker *walker; | |
163 | LruWalkData *lru_walk; | |
164 | lru->nwalkers += 1; | |
468ae12b | 165 | walker = CBDATA_ALLOC(RemovalPolicyWalker, NULL); |
6a566b9c | 166 | lru_walk = xcalloc(1, sizeof(*lru_walk)); |
167 | walker->_policy = policy; | |
168 | walker->_data = lru_walk; | |
169 | walker->Next = lru_walkNext; | |
170 | walker->Done = lru_walkDone; | |
171 | lru_walk->current = (LruNode *) lru->list.head; | |
6a566b9c | 172 | return walker; |
173 | } | |
174 | ||
175 | /** RemovalPurgeWalker **/ | |
176 | ||
177 | typedef struct _LruPurgeData LruPurgeData; | |
9f913cf1 | 178 | struct _LruPurgeData { |
6a566b9c | 179 | LruNode *current; |
180 | LruNode *start; | |
181 | }; | |
182 | ||
183 | static StoreEntry * | |
184 | lru_purgeNext(RemovalPurgeWalker * walker) | |
185 | { | |
186 | LruPurgeData *lru_walker = walker->_data; | |
187 | RemovalPolicy *policy = walker->_policy; | |
188 | LruPolicyData *lru = policy->_data; | |
189 | LruNode *lru_node; | |
190 | StoreEntry *entry; | |
191 | try_again: | |
192 | lru_node = lru_walker->current; | |
193 | if (!lru_node || walker->scanned >= walker->max_scan) | |
194 | return NULL; | |
195 | walker->scanned += 1; | |
196 | lru_walker->current = (LruNode *) lru_node->node.next; | |
197 | if (lru_walker->current == lru_walker->start) { | |
198 | /* Last node found */ | |
199 | lru_walker->current = NULL; | |
200 | } | |
201 | entry = (StoreEntry *) lru_node->node.data; | |
202 | dlinkDelete(&lru_node->node, &lru->list); | |
203 | if (storeEntryLocked(entry)) { | |
204 | /* Shit, it is locked. we can't return this one */ | |
205 | walker->locked++; | |
206 | dlinkAddTail(entry, &lru_node->node, &lru->list); | |
207 | goto try_again; | |
208 | } | |
209 | memPoolFree(lru_node_pool, lru_node); | |
210 | lru->count -= 1; | |
211 | SET_POLICY_NODE(entry, NULL); | |
212 | return entry; | |
213 | } | |
214 | ||
215 | static void | |
216 | lru_purgeDone(RemovalPurgeWalker * walker) | |
217 | { | |
218 | RemovalPolicy *policy = walker->_policy; | |
219 | LruPolicyData *lru = policy->_data; | |
220 | assert(strcmp(policy->_type, "lru") == 0); | |
221 | assert(lru->nwalkers > 0); | |
222 | lru->nwalkers -= 1; | |
223 | safe_free(walker->_data); | |
224 | cbdataFree(walker); | |
225 | } | |
226 | ||
227 | static RemovalPurgeWalker * | |
228 | lru_purgeInit(RemovalPolicy * policy, int max_scan) | |
229 | { | |
230 | LruPolicyData *lru = policy->_data; | |
231 | RemovalPurgeWalker *walker; | |
232 | LruPurgeData *lru_walk; | |
233 | lru->nwalkers += 1; | |
468ae12b | 234 | walker = CBDATA_ALLOC(RemovalPurgeWalker, NULL); |
6a566b9c | 235 | lru_walk = xcalloc(1, sizeof(*lru_walk)); |
236 | walker->_policy = policy; | |
237 | walker->_data = lru_walk; | |
238 | walker->max_scan = max_scan; | |
239 | walker->Next = lru_purgeNext; | |
240 | walker->Done = lru_purgeDone; | |
241 | lru_walk->start = lru_walk->current = (LruNode *) lru->list.head; | |
6a566b9c | 242 | return walker; |
243 | } | |
244 | ||
245 | static void | |
246 | lru_free(RemovalPolicy * policy) | |
247 | { | |
248 | LruPolicyData *lru = policy->_data; | |
249 | /* Make some verification of the policy state */ | |
250 | assert(strcmp(policy->_type, "lru") == 0); | |
251 | assert(lru->nwalkers); | |
252 | assert(lru->count); | |
253 | /* Ok, time to destroy this policy */ | |
254 | safe_free(policy->_data); | |
255 | memset(policy, 0, sizeof(*policy)); | |
256 | cbdataFree(policy); | |
257 | } | |
258 | ||
259 | RemovalPolicy * | |
9f913cf1 | 260 | createRemovalPolicy_lru(wordlist * args) |
6a566b9c | 261 | { |
262 | RemovalPolicy *policy; | |
263 | LruPolicyData *lru_data; | |
264 | /* no arguments expected or understood */ | |
265 | assert(!args); | |
266 | /* Initialize */ | |
267 | if (!lru_node_pool) | |
268 | lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode)); | |
269 | /* Allocate the needed structures */ | |
6a566b9c | 270 | lru_data = xcalloc(1, sizeof(*lru_data)); |
468ae12b | 271 | policy = CBDATA_ALLOC(RemovalPolicy, NULL); |
6a566b9c | 272 | /* Initialize the URL data */ |
273 | lru_data->policy = policy; | |
274 | /* Populate the policy structure */ | |
275 | policy->_type = "lru"; | |
276 | policy->_data = lru_data; | |
277 | policy->Free = lru_free; | |
278 | policy->Add = lru_add; | |
279 | policy->Remove = lru_remove; | |
280 | policy->Referenced = lru_referenced; | |
281 | policy->Dereferenced = lru_referenced; | |
282 | policy->WalkInit = lru_walkInit; | |
283 | policy->PurgeInit = lru_purgeInit; | |
284 | /* Increase policy usage count */ | |
285 | nr_lru_policies += 0; | |
286 | return policy; | |
287 | } |