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$");
33 #include "cacheplcs.h"
36 static void cache_fifo_policy_update_item(struct cache_policy_ *,
37 struct cache_policy_item_ *);
38 static void cache_lfu_policy_add_item(struct cache_policy_ *,
39 struct cache_policy_item_ *);
40 static struct cache_policy_item_ * cache_lfu_policy_create_item(void);
41 static void cache_lfu_policy_destroy_item(struct cache_policy_item_ *);
42 static struct cache_policy_item_ *cache_lfu_policy_get_first_item(
43 struct cache_policy_ *);
44 static struct cache_policy_item_ *cache_lfu_policy_get_last_item(
45 struct cache_policy_ *);
46 static struct cache_policy_item_ *cache_lfu_policy_get_next_item(
47 struct cache_policy_ *, struct cache_policy_item_ *);
48 static struct cache_policy_item_ *cache_lfu_policy_get_prev_item(
49 struct cache_policy_ *, struct cache_policy_item_ *);
50 static void cache_lfu_policy_remove_item(struct cache_policy_ *,
51 struct cache_policy_item_ *);
52 static void cache_lfu_policy_update_item(struct cache_policy_ *,
53 struct cache_policy_item_ *);
54 static void cache_lru_policy_update_item(struct cache_policy_ *,
55 struct cache_policy_item_ *);
56 static void cache_queue_policy_add_item(struct cache_policy_ *,
57 struct cache_policy_item_ *);
58 static struct cache_policy_item_ * cache_queue_policy_create_item();
59 static void cache_queue_policy_destroy_item(struct cache_policy_item_ *);
60 static struct cache_policy_item_ *cache_queue_policy_get_first_item(
61 struct cache_policy_ *);
62 static struct cache_policy_item_ *cache_queue_policy_get_last_item(
63 struct cache_policy_ *);
64 static struct cache_policy_item_ *cache_queue_policy_get_next_item(
65 struct cache_policy_ *, struct cache_policy_item_ *);
66 static struct cache_policy_item_ *cache_queue_policy_get_prev_item(
67 struct cache_policy_ *, struct cache_policy_item_ *);
68 static void cache_queue_policy_remove_item(struct cache_policy_ *,
69 struct cache_policy_item_ *);
70 static void destroy_cache_queue_policy(struct cache_queue_policy_ *);
71 static struct cache_queue_policy_ *init_cache_queue_policy(void);
74 * All cache_queue_policy_XXX functions below will be used to fill
75 * the cache_queue_policy structure. They implement the most functionality of
76 * LRU and FIFO policies. LRU and FIFO policies are actually the
77 * cache_queue_policy_ with cache_update_item function changed.
79 static struct cache_policy_item_ *
80 cache_queue_policy_create_item()
82 struct cache_queue_policy_item_ *retval;
84 TRACE_IN(cache_queue_policy_create_item);
85 retval = (struct cache_queue_policy_item_ *)calloc(1,
86 sizeof(struct cache_queue_policy_item_));
87 assert(retval != NULL);
89 TRACE_OUT(cache_queue_policy_create_item);
90 return ((struct cache_policy_item_ *)retval);
94 cache_queue_policy_destroy_item(struct cache_policy_item_ *item)
97 TRACE_IN(cache_queue_policy_destroy_item);
100 TRACE_OUT(cache_queue_policy_destroy_item);
104 cache_queue_policy_add_item(struct cache_policy_ *policy,
105 struct cache_policy_item_ *item)
107 struct cache_queue_policy_ *queue_policy;
108 struct cache_queue_policy_item_ *queue_item;
110 TRACE_IN(cache_queue_policy_add_item);
111 queue_policy = (struct cache_queue_policy_ *)policy;
112 queue_item = (struct cache_queue_policy_item_ *)item;
113 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
114 TRACE_OUT(cache_queue_policy_add_item);
118 cache_queue_policy_remove_item(struct cache_policy_ *policy,
119 struct cache_policy_item_ *item)
121 struct cache_queue_policy_ *queue_policy;
122 struct cache_queue_policy_item_ *queue_item;
124 TRACE_IN(cache_queue_policy_remove_item);
125 queue_policy = (struct cache_queue_policy_ *)policy;
126 queue_item = (struct cache_queue_policy_item_ *)item;
127 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
128 TRACE_OUT(cache_queue_policy_remove_item);
131 static struct cache_policy_item_ *
132 cache_queue_policy_get_first_item(struct cache_policy_ *policy)
134 struct cache_queue_policy_ *queue_policy;
136 TRACE_IN(cache_queue_policy_get_first_item);
137 queue_policy = (struct cache_queue_policy_ *)policy;
138 TRACE_OUT(cache_queue_policy_get_first_item);
139 return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head));
142 static struct cache_policy_item_ *
143 cache_queue_policy_get_last_item(struct cache_policy_ *policy)
145 struct cache_queue_policy_ *queue_policy;
147 TRACE_IN(cache_queue_policy_get_last_item);
148 queue_policy = (struct cache_queue_policy_ *)policy;
149 TRACE_OUT(cache_queue_policy_get_last_item);
150 return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head,
151 cache_queue_policy_head_));
154 static struct cache_policy_item_ *
155 cache_queue_policy_get_next_item(struct cache_policy_ *policy,
156 struct cache_policy_item_ *item)
158 struct cache_queue_policy_ *queue_policy;
159 struct cache_queue_policy_item_ *queue_item;
161 TRACE_IN(cache_queue_policy_get_next_item);
162 queue_policy = (struct cache_queue_policy_ *)policy;
163 queue_item = (struct cache_queue_policy_item_ *)item;
165 TRACE_OUT(cache_queue_policy_get_next_item);
166 return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries));
169 static struct cache_policy_item_ *
170 cache_queue_policy_get_prev_item(struct cache_policy_ *policy,
171 struct cache_policy_item_ *item)
173 struct cache_queue_policy_ *queue_policy;
174 struct cache_queue_policy_item_ *queue_item;
176 TRACE_IN(cache_queue_policy_get_prev_item);
177 queue_policy = (struct cache_queue_policy_ *)policy;
178 queue_item = (struct cache_queue_policy_item_ *)item;
180 TRACE_OUT(cache_queue_policy_get_prev_item);
181 return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item,
182 cache_queue_policy_head_, entries));
186 * Initializes cache_queue_policy_ by filling the structure with the functions
187 * pointers, defined above
189 static struct cache_queue_policy_ *
190 init_cache_queue_policy(void)
192 struct cache_queue_policy_ *retval;
194 TRACE_IN(init_cache_queue_policy);
195 retval = (struct cache_queue_policy_ *)calloc(1,
196 sizeof(struct cache_queue_policy_));
197 assert(retval != NULL);
199 retval->parent_data.create_item_func = cache_queue_policy_create_item;
200 retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item;
202 retval->parent_data.add_item_func = cache_queue_policy_add_item;
203 retval->parent_data.remove_item_func = cache_queue_policy_remove_item;
205 retval->parent_data.get_first_item_func =
206 cache_queue_policy_get_first_item;
207 retval->parent_data.get_last_item_func =
208 cache_queue_policy_get_last_item;
209 retval->parent_data.get_next_item_func =
210 cache_queue_policy_get_next_item;
211 retval->parent_data.get_prev_item_func =
212 cache_queue_policy_get_prev_item;
214 TAILQ_INIT(&retval->head);
215 TRACE_OUT(init_cache_queue_policy);
220 destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy)
222 struct cache_queue_policy_item_ *queue_item;
224 TRACE_IN(destroy_cache_queue_policy);
225 while (!TAILQ_EMPTY(&queue_policy->head)) {
226 queue_item = TAILQ_FIRST(&queue_policy->head);
227 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
228 cache_queue_policy_destroy_item(
229 (struct cache_policy_item_ *)queue_item);
232 TRACE_OUT(destroy_cache_queue_policy);
236 * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything,
237 * when the cache element is updated. So it always stays in its initial
238 * position in the queue - that is exactly the FIFO functionality.
241 cache_fifo_policy_update_item(struct cache_policy_ *policy,
242 struct cache_policy_item_ *item)
245 TRACE_IN(cache_fifo_policy_update_item);
246 /* policy and item arguments are ignored */
247 TRACE_OUT(cache_fifo_policy_update_item);
250 struct cache_policy_ *
251 init_cache_fifo_policy()
253 struct cache_queue_policy_ *retval;
255 TRACE_IN(init_cache_fifo_policy);
256 retval = init_cache_queue_policy();
257 retval->parent_data.update_item_func = cache_fifo_policy_update_item;
259 TRACE_OUT(init_cache_fifo_policy);
260 return ((struct cache_policy_ *)retval);
264 destroy_cache_fifo_policy(struct cache_policy_ *policy)
266 struct cache_queue_policy_ *queue_policy;
268 TRACE_IN(destroy_cache_fifo_policy);
269 queue_policy = (struct cache_queue_policy_ *)policy;
270 destroy_cache_queue_policy(queue_policy);
271 TRACE_OUT(destroy_cache_fifo_policy);
275 * Makes cache_queue_policy_ behave like LRU policy. On each update, cache
276 * element is moved to the end of the queue - so it would be deleted in last
277 * turn. That is exactly the LRU policy functionality.
280 cache_lru_policy_update_item(struct cache_policy_ *policy,
281 struct cache_policy_item_ *item)
283 struct cache_queue_policy_ *queue_policy;
284 struct cache_queue_policy_item_ *queue_item;
286 TRACE_IN(cache_lru_policy_update_item);
287 queue_policy = (struct cache_queue_policy_ *)policy;
288 queue_item = (struct cache_queue_policy_item_ *)item;
290 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
291 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
292 TRACE_OUT(cache_lru_policy_update_item);
295 struct cache_policy_ *
296 init_cache_lru_policy()
298 struct cache_queue_policy_ *retval;
300 TRACE_IN(init_cache_lru_policy);
301 retval = init_cache_queue_policy();
302 retval->parent_data.update_item_func = cache_lru_policy_update_item;
304 TRACE_OUT(init_cache_lru_policy);
305 return ((struct cache_policy_ *)retval);
309 destroy_cache_lru_policy(struct cache_policy_ *policy)
311 struct cache_queue_policy_ *queue_policy;
313 TRACE_IN(destroy_cache_lru_policy);
314 queue_policy = (struct cache_queue_policy_ *)policy;
315 destroy_cache_queue_policy(queue_policy);
316 TRACE_OUT(destroy_cache_lru_policy);
320 * LFU (least frequently used) policy implementation differs much from the
321 * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_
322 * functions are implemented specifically for this policy. The idea of this
323 * policy is to represent frequency (real number) as the integer number and
324 * use it as the index in the array. Each array's element is
325 * the list of elements. For example, if we have the 100-elements
326 * array for this policy, the elements with frequency 0.1 (calls per-second)
327 * would be in 10th element of the array.
329 static struct cache_policy_item_ *
330 cache_lfu_policy_create_item(void)
332 struct cache_lfu_policy_item_ *retval;
334 TRACE_IN(cache_lfu_policy_create_item);
335 retval = (struct cache_lfu_policy_item_ *)calloc(1,
336 sizeof(struct cache_lfu_policy_item_));
337 assert(retval != NULL);
339 TRACE_OUT(cache_lfu_policy_create_item);
340 return ((struct cache_policy_item_ *)retval);
344 cache_lfu_policy_destroy_item(struct cache_policy_item_ *item)
347 TRACE_IN(cache_lfu_policy_destroy_item);
348 assert(item != NULL);
350 TRACE_OUT(cache_lfu_policy_destroy_item);
354 * When placed in the LFU policy queue for the first time, the maximum
355 * frequency is assigned to the element
358 cache_lfu_policy_add_item(struct cache_policy_ *policy,
359 struct cache_policy_item_ *item)
361 struct cache_lfu_policy_ *lfu_policy;
362 struct cache_lfu_policy_item_ *lfu_item;
364 TRACE_IN(cache_lfu_policy_add_item);
365 lfu_policy = (struct cache_lfu_policy_ *)policy;
366 lfu_item = (struct cache_lfu_policy_item_ *)item;
368 lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1;
369 TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]),
371 TRACE_OUT(cache_lfu_policy_add_item);
375 * On each update the frequency of the element is recalculated and, if it
376 * changed, the element would be moved to the another place in the array.
379 cache_lfu_policy_update_item(struct cache_policy_ *policy,
380 struct cache_policy_item_ *item)
382 struct cache_lfu_policy_ *lfu_policy;
383 struct cache_lfu_policy_item_ *lfu_item;
386 TRACE_IN(cache_lfu_policy_update_item);
387 lfu_policy = (struct cache_lfu_policy_ *)policy;
388 lfu_item = (struct cache_lfu_policy_item_ *)item;
391 * We calculate the square of the request_count to avoid grouping of
392 * all elements at the start of the array (for example, if array size is
393 * 100 and most of its elements has frequency below the 0.01, they
394 * all would be grouped in the first array's position). Other
395 * techniques should be used here later to ensure, that elements are
396 * equally distributed in the array and not grouped in its beginning.
398 if (lfu_item->parent_data.last_request_time.tv_sec !=
399 lfu_item->parent_data.creation_time.tv_sec) {
400 index = ((double)lfu_item->parent_data.request_count *
401 (double)lfu_item->parent_data.request_count /
402 (lfu_item->parent_data.last_request_time.tv_sec -
403 lfu_item->parent_data.creation_time.tv_sec + 1)) *
404 CACHELIB_MAX_FREQUENCY;
405 if (index >= CACHELIB_MAX_FREQUENCY)
406 index = CACHELIB_MAX_FREQUENCY - 1;
408 index = CACHELIB_MAX_FREQUENCY - 1;
410 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
412 lfu_item->frequency = index;
413 TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries);
415 TRACE_OUT(cache_lfu_policy_update_item);
419 cache_lfu_policy_remove_item(struct cache_policy_ *policy,
420 struct cache_policy_item_ *item)
422 struct cache_lfu_policy_ *lfu_policy;
423 struct cache_lfu_policy_item_ *lfu_item;
425 TRACE_IN(cache_lfu_policy_remove_item);
426 lfu_policy = (struct cache_lfu_policy_ *)policy;
427 lfu_item = (struct cache_lfu_policy_item_ *)item;
429 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
431 TRACE_OUT(cache_lfu_policy_remove_item);
434 static struct cache_policy_item_ *
435 cache_lfu_policy_get_first_item(struct cache_policy_ *policy)
437 struct cache_lfu_policy_ *lfu_policy;
438 struct cache_lfu_policy_item_ *lfu_item;
441 TRACE_IN(cache_lfu_policy_get_first_item);
443 lfu_policy = (struct cache_lfu_policy_ *)policy;
444 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
445 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
446 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
450 TRACE_OUT(cache_lfu_policy_get_first_item);
451 return ((struct cache_policy_item_ *)lfu_item);
454 static struct cache_policy_item_ *
455 cache_lfu_policy_get_last_item(struct cache_policy_ *policy)
457 struct cache_lfu_policy_ *lfu_policy;
458 struct cache_lfu_policy_item_ *lfu_item;
461 TRACE_IN(cache_lfu_policy_get_last_item);
463 lfu_policy = (struct cache_lfu_policy_ *)policy;
464 for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i)
465 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
466 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
467 cache_lfu_policy_group_);
471 TRACE_OUT(cache_lfu_policy_get_last_item);
472 return ((struct cache_policy_item_ *)lfu_item);
475 static struct cache_policy_item_ *
476 cache_lfu_policy_get_next_item(struct cache_policy_ *policy,
477 struct cache_policy_item_ *item)
479 struct cache_lfu_policy_ *lfu_policy;
480 struct cache_lfu_policy_item_ *lfu_item;
483 TRACE_IN(cache_lfu_policy_get_next_item);
484 lfu_policy = (struct cache_lfu_policy_ *)policy;
485 lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries);
486 if (lfu_item == NULL)
488 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1;
489 i < CACHELIB_MAX_FREQUENCY; ++i) {
490 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
491 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
497 TRACE_OUT(cache_lfu_policy_get_next_item);
498 return ((struct cache_policy_item_ *)lfu_item);
501 static struct cache_policy_item_ *
502 cache_lfu_policy_get_prev_item(struct cache_policy_ *policy,
503 struct cache_policy_item_ *item)
505 struct cache_lfu_policy_ *lfu_policy;
506 struct cache_lfu_policy_item_ *lfu_item;
509 TRACE_IN(cache_lfu_policy_get_prev_item);
510 lfu_policy = (struct cache_lfu_policy_ *)policy;
511 lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item,
512 cache_lfu_policy_group_, entries);
513 if (lfu_item == NULL)
515 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1;
517 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
518 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
519 cache_lfu_policy_group_);
524 TRACE_OUT(cache_lfu_policy_get_prev_item);
525 return ((struct cache_policy_item_ *)lfu_item);
529 * Initializes the cache_policy_ structure by filling it with appropriate
532 struct cache_policy_ *
533 init_cache_lfu_policy()
536 struct cache_lfu_policy_ *retval;
538 TRACE_IN(init_cache_lfu_policy);
539 retval = (struct cache_lfu_policy_ *)calloc(1,
540 sizeof(struct cache_lfu_policy_));
541 assert(retval != NULL);
543 retval->parent_data.create_item_func = cache_lfu_policy_create_item;
544 retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item;
546 retval->parent_data.add_item_func = cache_lfu_policy_add_item;
547 retval->parent_data.update_item_func = cache_lfu_policy_update_item;
548 retval->parent_data.remove_item_func = cache_lfu_policy_remove_item;
550 retval->parent_data.get_first_item_func =
551 cache_lfu_policy_get_first_item;
552 retval->parent_data.get_last_item_func =
553 cache_lfu_policy_get_last_item;
554 retval->parent_data.get_next_item_func =
555 cache_lfu_policy_get_next_item;
556 retval->parent_data.get_prev_item_func =
557 cache_lfu_policy_get_prev_item;
559 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
560 TAILQ_INIT(&(retval->groups[i]));
562 TRACE_OUT(init_cache_lfu_policy);
563 return ((struct cache_policy_ *)retval);
567 destroy_cache_lfu_policy(struct cache_policy_ *policy)
570 struct cache_lfu_policy_ *lfu_policy;
571 struct cache_lfu_policy_item_ *lfu_item;
573 TRACE_IN(destroy_cache_lfu_policy);
574 lfu_policy = (struct cache_lfu_policy_ *)policy;
575 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) {
576 while (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
577 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
578 TAILQ_REMOVE(&(lfu_policy->groups[i]), lfu_item,
580 cache_lfu_policy_destroy_item(
581 (struct cache_policy_item_ *)lfu_item);
585 TRACE_OUT(destroy_cache_lfu_policy);