2 * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
37 #include "cacheplcs.h"
40 static void cache_fifo_policy_update_item(struct cache_policy_ *,
41 struct cache_policy_item_ *);
42 static void cache_lfu_policy_add_item(struct cache_policy_ *,
43 struct cache_policy_item_ *);
44 static struct cache_policy_item_ * cache_lfu_policy_create_item(void);
45 static void cache_lfu_policy_destroy_item(struct cache_policy_item_ *);
46 static struct cache_policy_item_ *cache_lfu_policy_get_first_item(
47 struct cache_policy_ *);
48 static struct cache_policy_item_ *cache_lfu_policy_get_last_item(
49 struct cache_policy_ *);
50 static struct cache_policy_item_ *cache_lfu_policy_get_next_item(
51 struct cache_policy_ *, struct cache_policy_item_ *);
52 static struct cache_policy_item_ *cache_lfu_policy_get_prev_item(
53 struct cache_policy_ *, struct cache_policy_item_ *);
54 static void cache_lfu_policy_remove_item(struct cache_policy_ *,
55 struct cache_policy_item_ *);
56 static void cache_lfu_policy_update_item(struct cache_policy_ *,
57 struct cache_policy_item_ *);
58 static void cache_lru_policy_update_item(struct cache_policy_ *,
59 struct cache_policy_item_ *);
60 static void cache_queue_policy_add_item(struct cache_policy_ *,
61 struct cache_policy_item_ *);
62 static struct cache_policy_item_ * cache_queue_policy_create_item(void);
63 static void cache_queue_policy_destroy_item(struct cache_policy_item_ *);
64 static struct cache_policy_item_ *cache_queue_policy_get_first_item(
65 struct cache_policy_ *);
66 static struct cache_policy_item_ *cache_queue_policy_get_last_item(
67 struct cache_policy_ *);
68 static struct cache_policy_item_ *cache_queue_policy_get_next_item(
69 struct cache_policy_ *, struct cache_policy_item_ *);
70 static struct cache_policy_item_ *cache_queue_policy_get_prev_item(
71 struct cache_policy_ *, struct cache_policy_item_ *);
72 static void cache_queue_policy_remove_item(struct cache_policy_ *,
73 struct cache_policy_item_ *);
74 static void destroy_cache_queue_policy(struct cache_queue_policy_ *);
75 static struct cache_queue_policy_ *init_cache_queue_policy(void);
78 * All cache_queue_policy_XXX functions below will be used to fill
79 * the cache_queue_policy structure. They implement the most functionality of
80 * LRU and FIFO policies. LRU and FIFO policies are actually the
81 * cache_queue_policy_ with cache_update_item function changed.
83 static struct cache_policy_item_ *
84 cache_queue_policy_create_item(void)
86 struct cache_queue_policy_item_ *retval;
88 TRACE_IN(cache_queue_policy_create_item);
91 assert(retval != NULL);
93 TRACE_OUT(cache_queue_policy_create_item);
94 return ((struct cache_policy_item_ *)retval);
98 cache_queue_policy_destroy_item(struct cache_policy_item_ *item)
101 TRACE_IN(cache_queue_policy_destroy_item);
102 assert(item != NULL);
104 TRACE_OUT(cache_queue_policy_destroy_item);
108 cache_queue_policy_add_item(struct cache_policy_ *policy,
109 struct cache_policy_item_ *item)
111 struct cache_queue_policy_ *queue_policy;
112 struct cache_queue_policy_item_ *queue_item;
114 TRACE_IN(cache_queue_policy_add_item);
115 queue_policy = (struct cache_queue_policy_ *)policy;
116 queue_item = (struct cache_queue_policy_item_ *)item;
117 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
118 TRACE_OUT(cache_queue_policy_add_item);
122 cache_queue_policy_remove_item(struct cache_policy_ *policy,
123 struct cache_policy_item_ *item)
125 struct cache_queue_policy_ *queue_policy;
126 struct cache_queue_policy_item_ *queue_item;
128 TRACE_IN(cache_queue_policy_remove_item);
129 queue_policy = (struct cache_queue_policy_ *)policy;
130 queue_item = (struct cache_queue_policy_item_ *)item;
131 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
132 TRACE_OUT(cache_queue_policy_remove_item);
135 static struct cache_policy_item_ *
136 cache_queue_policy_get_first_item(struct cache_policy_ *policy)
138 struct cache_queue_policy_ *queue_policy;
140 TRACE_IN(cache_queue_policy_get_first_item);
141 queue_policy = (struct cache_queue_policy_ *)policy;
142 TRACE_OUT(cache_queue_policy_get_first_item);
143 return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head));
146 static struct cache_policy_item_ *
147 cache_queue_policy_get_last_item(struct cache_policy_ *policy)
149 struct cache_queue_policy_ *queue_policy;
151 TRACE_IN(cache_queue_policy_get_last_item);
152 queue_policy = (struct cache_queue_policy_ *)policy;
153 TRACE_OUT(cache_queue_policy_get_last_item);
154 return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head,
155 cache_queue_policy_head_));
158 static struct cache_policy_item_ *
159 cache_queue_policy_get_next_item(struct cache_policy_ *policy,
160 struct cache_policy_item_ *item)
162 struct cache_queue_policy_ *queue_policy;
163 struct cache_queue_policy_item_ *queue_item;
165 TRACE_IN(cache_queue_policy_get_next_item);
166 queue_policy = (struct cache_queue_policy_ *)policy;
167 queue_item = (struct cache_queue_policy_item_ *)item;
169 TRACE_OUT(cache_queue_policy_get_next_item);
170 return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries));
173 static struct cache_policy_item_ *
174 cache_queue_policy_get_prev_item(struct cache_policy_ *policy,
175 struct cache_policy_item_ *item)
177 struct cache_queue_policy_ *queue_policy;
178 struct cache_queue_policy_item_ *queue_item;
180 TRACE_IN(cache_queue_policy_get_prev_item);
181 queue_policy = (struct cache_queue_policy_ *)policy;
182 queue_item = (struct cache_queue_policy_item_ *)item;
184 TRACE_OUT(cache_queue_policy_get_prev_item);
185 return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item,
186 cache_queue_policy_head_, entries));
190 * Initializes cache_queue_policy_ by filling the structure with the functions
191 * pointers, defined above
193 static struct cache_queue_policy_ *
194 init_cache_queue_policy(void)
196 struct cache_queue_policy_ *retval;
198 TRACE_IN(init_cache_queue_policy);
201 assert(retval != NULL);
203 retval->parent_data.create_item_func = cache_queue_policy_create_item;
204 retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item;
206 retval->parent_data.add_item_func = cache_queue_policy_add_item;
207 retval->parent_data.remove_item_func = cache_queue_policy_remove_item;
209 retval->parent_data.get_first_item_func =
210 cache_queue_policy_get_first_item;
211 retval->parent_data.get_last_item_func =
212 cache_queue_policy_get_last_item;
213 retval->parent_data.get_next_item_func =
214 cache_queue_policy_get_next_item;
215 retval->parent_data.get_prev_item_func =
216 cache_queue_policy_get_prev_item;
218 TAILQ_INIT(&retval->head);
219 TRACE_OUT(init_cache_queue_policy);
224 destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy)
226 struct cache_queue_policy_item_ *queue_item;
228 TRACE_IN(destroy_cache_queue_policy);
229 while (!TAILQ_EMPTY(&queue_policy->head)) {
230 queue_item = TAILQ_FIRST(&queue_policy->head);
231 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
232 cache_queue_policy_destroy_item(
233 (struct cache_policy_item_ *)queue_item);
236 TRACE_OUT(destroy_cache_queue_policy);
240 * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything,
241 * when the cache element is updated. So it always stays in its initial
242 * position in the queue - that is exactly the FIFO functionality.
245 cache_fifo_policy_update_item(struct cache_policy_ *policy,
246 struct cache_policy_item_ *item)
249 TRACE_IN(cache_fifo_policy_update_item);
250 /* policy and item arguments are ignored */
251 TRACE_OUT(cache_fifo_policy_update_item);
254 struct cache_policy_ *
255 init_cache_fifo_policy(void)
257 struct cache_queue_policy_ *retval;
259 TRACE_IN(init_cache_fifo_policy);
260 retval = init_cache_queue_policy();
261 retval->parent_data.update_item_func = cache_fifo_policy_update_item;
263 TRACE_OUT(init_cache_fifo_policy);
264 return ((struct cache_policy_ *)retval);
268 destroy_cache_fifo_policy(struct cache_policy_ *policy)
270 struct cache_queue_policy_ *queue_policy;
272 TRACE_IN(destroy_cache_fifo_policy);
273 queue_policy = (struct cache_queue_policy_ *)policy;
274 destroy_cache_queue_policy(queue_policy);
275 TRACE_OUT(destroy_cache_fifo_policy);
279 * Makes cache_queue_policy_ behave like LRU policy. On each update, cache
280 * element is moved to the end of the queue - so it would be deleted in last
281 * turn. That is exactly the LRU policy functionality.
284 cache_lru_policy_update_item(struct cache_policy_ *policy,
285 struct cache_policy_item_ *item)
287 struct cache_queue_policy_ *queue_policy;
288 struct cache_queue_policy_item_ *queue_item;
290 TRACE_IN(cache_lru_policy_update_item);
291 queue_policy = (struct cache_queue_policy_ *)policy;
292 queue_item = (struct cache_queue_policy_item_ *)item;
294 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
295 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
296 TRACE_OUT(cache_lru_policy_update_item);
299 struct cache_policy_ *
300 init_cache_lru_policy(void)
302 struct cache_queue_policy_ *retval;
304 TRACE_IN(init_cache_lru_policy);
305 retval = init_cache_queue_policy();
306 retval->parent_data.update_item_func = cache_lru_policy_update_item;
308 TRACE_OUT(init_cache_lru_policy);
309 return ((struct cache_policy_ *)retval);
313 destroy_cache_lru_policy(struct cache_policy_ *policy)
315 struct cache_queue_policy_ *queue_policy;
317 TRACE_IN(destroy_cache_lru_policy);
318 queue_policy = (struct cache_queue_policy_ *)policy;
319 destroy_cache_queue_policy(queue_policy);
320 TRACE_OUT(destroy_cache_lru_policy);
324 * LFU (least frequently used) policy implementation differs much from the
325 * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_
326 * functions are implemented specifically for this policy. The idea of this
327 * policy is to represent frequency (real number) as the integer number and
328 * use it as the index in the array. Each array's element is
329 * the list of elements. For example, if we have the 100-elements
330 * array for this policy, the elements with frequency 0.1 (calls per-second)
331 * would be in 10th element of the array.
333 static struct cache_policy_item_ *
334 cache_lfu_policy_create_item(void)
336 struct cache_lfu_policy_item_ *retval;
338 TRACE_IN(cache_lfu_policy_create_item);
341 assert(retval != NULL);
343 TRACE_OUT(cache_lfu_policy_create_item);
344 return ((struct cache_policy_item_ *)retval);
348 cache_lfu_policy_destroy_item(struct cache_policy_item_ *item)
351 TRACE_IN(cache_lfu_policy_destroy_item);
352 assert(item != NULL);
354 TRACE_OUT(cache_lfu_policy_destroy_item);
358 * When placed in the LFU policy queue for the first time, the maximum
359 * frequency is assigned to the element
362 cache_lfu_policy_add_item(struct cache_policy_ *policy,
363 struct cache_policy_item_ *item)
365 struct cache_lfu_policy_ *lfu_policy;
366 struct cache_lfu_policy_item_ *lfu_item;
368 TRACE_IN(cache_lfu_policy_add_item);
369 lfu_policy = (struct cache_lfu_policy_ *)policy;
370 lfu_item = (struct cache_lfu_policy_item_ *)item;
372 lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1;
373 TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]),
375 TRACE_OUT(cache_lfu_policy_add_item);
379 * On each update the frequency of the element is recalculated and, if it
380 * changed, the element would be moved to the another place in the array.
383 cache_lfu_policy_update_item(struct cache_policy_ *policy,
384 struct cache_policy_item_ *item)
386 struct cache_lfu_policy_ *lfu_policy;
387 struct cache_lfu_policy_item_ *lfu_item;
390 TRACE_IN(cache_lfu_policy_update_item);
391 lfu_policy = (struct cache_lfu_policy_ *)policy;
392 lfu_item = (struct cache_lfu_policy_item_ *)item;
395 * We calculate the square of the request_count to avoid grouping of
396 * all elements at the start of the array (for example, if array size is
397 * 100 and most of its elements has frequency below the 0.01, they
398 * all would be grouped in the first array's position). Other
399 * techniques should be used here later to ensure, that elements are
400 * equally distributed in the array and not grouped in its beginning.
402 if (lfu_item->parent_data.last_request_time.tv_sec !=
403 lfu_item->parent_data.creation_time.tv_sec) {
404 index = ((double)lfu_item->parent_data.request_count *
405 (double)lfu_item->parent_data.request_count /
406 (lfu_item->parent_data.last_request_time.tv_sec -
407 lfu_item->parent_data.creation_time.tv_sec + 1)) *
408 CACHELIB_MAX_FREQUENCY;
409 if (index >= CACHELIB_MAX_FREQUENCY)
410 index = CACHELIB_MAX_FREQUENCY - 1;
412 index = CACHELIB_MAX_FREQUENCY - 1;
414 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
416 lfu_item->frequency = index;
417 TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries);
419 TRACE_OUT(cache_lfu_policy_update_item);
423 cache_lfu_policy_remove_item(struct cache_policy_ *policy,
424 struct cache_policy_item_ *item)
426 struct cache_lfu_policy_ *lfu_policy;
427 struct cache_lfu_policy_item_ *lfu_item;
429 TRACE_IN(cache_lfu_policy_remove_item);
430 lfu_policy = (struct cache_lfu_policy_ *)policy;
431 lfu_item = (struct cache_lfu_policy_item_ *)item;
433 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
435 TRACE_OUT(cache_lfu_policy_remove_item);
438 static struct cache_policy_item_ *
439 cache_lfu_policy_get_first_item(struct cache_policy_ *policy)
441 struct cache_lfu_policy_ *lfu_policy;
442 struct cache_lfu_policy_item_ *lfu_item;
445 TRACE_IN(cache_lfu_policy_get_first_item);
447 lfu_policy = (struct cache_lfu_policy_ *)policy;
448 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
449 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
450 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
454 TRACE_OUT(cache_lfu_policy_get_first_item);
455 return ((struct cache_policy_item_ *)lfu_item);
458 static struct cache_policy_item_ *
459 cache_lfu_policy_get_last_item(struct cache_policy_ *policy)
461 struct cache_lfu_policy_ *lfu_policy;
462 struct cache_lfu_policy_item_ *lfu_item;
465 TRACE_IN(cache_lfu_policy_get_last_item);
467 lfu_policy = (struct cache_lfu_policy_ *)policy;
468 for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i)
469 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
470 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
471 cache_lfu_policy_group_);
475 TRACE_OUT(cache_lfu_policy_get_last_item);
476 return ((struct cache_policy_item_ *)lfu_item);
479 static struct cache_policy_item_ *
480 cache_lfu_policy_get_next_item(struct cache_policy_ *policy,
481 struct cache_policy_item_ *item)
483 struct cache_lfu_policy_ *lfu_policy;
484 struct cache_lfu_policy_item_ *lfu_item;
487 TRACE_IN(cache_lfu_policy_get_next_item);
488 lfu_policy = (struct cache_lfu_policy_ *)policy;
489 lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries);
490 if (lfu_item == NULL)
492 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1;
493 i < CACHELIB_MAX_FREQUENCY; ++i) {
494 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
495 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
501 TRACE_OUT(cache_lfu_policy_get_next_item);
502 return ((struct cache_policy_item_ *)lfu_item);
505 static struct cache_policy_item_ *
506 cache_lfu_policy_get_prev_item(struct cache_policy_ *policy,
507 struct cache_policy_item_ *item)
509 struct cache_lfu_policy_ *lfu_policy;
510 struct cache_lfu_policy_item_ *lfu_item;
513 TRACE_IN(cache_lfu_policy_get_prev_item);
514 lfu_policy = (struct cache_lfu_policy_ *)policy;
515 lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item,
516 cache_lfu_policy_group_, entries);
517 if (lfu_item == NULL)
519 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1;
521 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
522 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
523 cache_lfu_policy_group_);
528 TRACE_OUT(cache_lfu_policy_get_prev_item);
529 return ((struct cache_policy_item_ *)lfu_item);
533 * Initializes the cache_policy_ structure by filling it with appropriate
536 struct cache_policy_ *
537 init_cache_lfu_policy(void)
540 struct cache_lfu_policy_ *retval;
542 TRACE_IN(init_cache_lfu_policy);
545 assert(retval != NULL);
547 retval->parent_data.create_item_func = cache_lfu_policy_create_item;
548 retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item;
550 retval->parent_data.add_item_func = cache_lfu_policy_add_item;
551 retval->parent_data.update_item_func = cache_lfu_policy_update_item;
552 retval->parent_data.remove_item_func = cache_lfu_policy_remove_item;
554 retval->parent_data.get_first_item_func =
555 cache_lfu_policy_get_first_item;
556 retval->parent_data.get_last_item_func =
557 cache_lfu_policy_get_last_item;
558 retval->parent_data.get_next_item_func =
559 cache_lfu_policy_get_next_item;
560 retval->parent_data.get_prev_item_func =
561 cache_lfu_policy_get_prev_item;
563 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
564 TAILQ_INIT(&(retval->groups[i]));
566 TRACE_OUT(init_cache_lfu_policy);
567 return ((struct cache_policy_ *)retval);
571 destroy_cache_lfu_policy(struct cache_policy_ *policy)
574 struct cache_lfu_policy_ *lfu_policy;
575 struct cache_lfu_policy_item_ *lfu_item;
577 TRACE_IN(destroy_cache_lfu_policy);
578 lfu_policy = (struct cache_lfu_policy_ *)policy;
579 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) {
580 while (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
581 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
582 TAILQ_REMOVE(&(lfu_policy->groups[i]), lfu_item,
584 cache_lfu_policy_destroy_item(
585 (struct cache_policy_item_ *)lfu_item);
589 TRACE_OUT(destroy_cache_lfu_policy);