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
26 * $FreeBSD: src/usr.sbin/nscd/cacheplcs.c,v 1.3 2008/10/12 00:44:27 delphij Exp $
31 #include "cacheplcs.h"
34 static void cache_fifo_policy_update_item(struct cache_policy_
*,
35 struct cache_policy_item_
*);
36 static void cache_lfu_policy_add_item(struct cache_policy_
*,
37 struct cache_policy_item_
*);
38 static struct cache_policy_item_
* cache_lfu_policy_create_item(void);
39 static void cache_lfu_policy_destroy_item(struct cache_policy_item_
*);
40 static struct cache_policy_item_
*cache_lfu_policy_get_first_item(
41 struct cache_policy_
*);
42 static struct cache_policy_item_
*cache_lfu_policy_get_last_item(
43 struct cache_policy_
*);
44 static struct cache_policy_item_
*cache_lfu_policy_get_next_item(
45 struct cache_policy_
*, struct cache_policy_item_
*);
46 static struct cache_policy_item_
*cache_lfu_policy_get_prev_item(
47 struct cache_policy_
*, struct cache_policy_item_
*);
48 static void cache_lfu_policy_remove_item(struct cache_policy_
*,
49 struct cache_policy_item_
*);
50 static void cache_lfu_policy_update_item(struct cache_policy_
*,
51 struct cache_policy_item_
*);
52 static void cache_lru_policy_update_item(struct cache_policy_
*,
53 struct cache_policy_item_
*);
54 static void cache_queue_policy_add_item(struct cache_policy_
*,
55 struct cache_policy_item_
*);
56 static struct cache_policy_item_
* cache_queue_policy_create_item();
57 static void cache_queue_policy_destroy_item(struct cache_policy_item_
*);
58 static struct cache_policy_item_
*cache_queue_policy_get_first_item(
59 struct cache_policy_
*);
60 static struct cache_policy_item_
*cache_queue_policy_get_last_item(
61 struct cache_policy_
*);
62 static struct cache_policy_item_
*cache_queue_policy_get_next_item(
63 struct cache_policy_
*, struct cache_policy_item_
*);
64 static struct cache_policy_item_
*cache_queue_policy_get_prev_item(
65 struct cache_policy_
*, struct cache_policy_item_
*);
66 static void cache_queue_policy_remove_item(struct cache_policy_
*,
67 struct cache_policy_item_
*);
68 static void destroy_cache_queue_policy(struct cache_queue_policy_
*);
69 static struct cache_queue_policy_
*init_cache_queue_policy(void);
72 * All cache_queue_policy_XXX functions below will be used to fill
73 * the cache_queue_policy structure. They implement the most functionality of
74 * LRU and FIFO policies. LRU and FIFO policies are actually the
75 * cache_queue_policy_ with cache_update_item function changed.
77 static struct cache_policy_item_
*
78 cache_queue_policy_create_item(void)
80 struct cache_queue_policy_item_
*retval
;
82 TRACE_IN(cache_queue_policy_create_item
);
83 retval
= (struct cache_queue_policy_item_
*)calloc(1,
84 sizeof(struct cache_queue_policy_item_
));
85 assert(retval
!= NULL
);
87 TRACE_OUT(cache_queue_policy_create_item
);
88 return ((struct cache_policy_item_
*)retval
);
92 cache_queue_policy_destroy_item(struct cache_policy_item_
*item
)
95 TRACE_IN(cache_queue_policy_destroy_item
);
98 TRACE_OUT(cache_queue_policy_destroy_item
);
102 cache_queue_policy_add_item(struct cache_policy_
*policy
,
103 struct cache_policy_item_
*item
)
105 struct cache_queue_policy_
*queue_policy
;
106 struct cache_queue_policy_item_
*queue_item
;
108 TRACE_IN(cache_queue_policy_add_item
);
109 queue_policy
= (struct cache_queue_policy_
*)policy
;
110 queue_item
= (struct cache_queue_policy_item_
*)item
;
111 TAILQ_INSERT_TAIL(&queue_policy
->head
, queue_item
, entries
);
112 TRACE_OUT(cache_queue_policy_add_item
);
116 cache_queue_policy_remove_item(struct cache_policy_
*policy
,
117 struct cache_policy_item_
*item
)
119 struct cache_queue_policy_
*queue_policy
;
120 struct cache_queue_policy_item_
*queue_item
;
122 TRACE_IN(cache_queue_policy_remove_item
);
123 queue_policy
= (struct cache_queue_policy_
*)policy
;
124 queue_item
= (struct cache_queue_policy_item_
*)item
;
125 TAILQ_REMOVE(&queue_policy
->head
, queue_item
, entries
);
126 TRACE_OUT(cache_queue_policy_remove_item
);
129 static struct cache_policy_item_
*
130 cache_queue_policy_get_first_item(struct cache_policy_
*policy
)
132 struct cache_queue_policy_
*queue_policy
;
134 TRACE_IN(cache_queue_policy_get_first_item
);
135 queue_policy
= (struct cache_queue_policy_
*)policy
;
136 TRACE_OUT(cache_queue_policy_get_first_item
);
137 return ((struct cache_policy_item_
*)TAILQ_FIRST(&queue_policy
->head
));
140 static struct cache_policy_item_
*
141 cache_queue_policy_get_last_item(struct cache_policy_
*policy
)
143 struct cache_queue_policy_
*queue_policy
;
145 TRACE_IN(cache_queue_policy_get_last_item
);
146 queue_policy
= (struct cache_queue_policy_
*)policy
;
147 TRACE_OUT(cache_queue_policy_get_last_item
);
148 return ((struct cache_policy_item_
*)TAILQ_LAST(&queue_policy
->head
,
149 cache_queue_policy_head_
));
152 static struct cache_policy_item_
*
153 cache_queue_policy_get_next_item(struct cache_policy_
*policy
,
154 struct cache_policy_item_
*item
)
156 struct cache_queue_policy_item_
*queue_item
;
158 TRACE_IN(cache_queue_policy_get_next_item
);
159 queue_item
= (struct cache_queue_policy_item_
*)item
;
161 TRACE_OUT(cache_queue_policy_get_next_item
);
162 return ((struct cache_policy_item_
*)TAILQ_NEXT(queue_item
, entries
));
165 static struct cache_policy_item_
*
166 cache_queue_policy_get_prev_item(struct cache_policy_
*policy
,
167 struct cache_policy_item_
*item
)
169 struct cache_queue_policy_item_
*queue_item
;
171 TRACE_IN(cache_queue_policy_get_prev_item
);
172 queue_item
= (struct cache_queue_policy_item_
*)item
;
174 TRACE_OUT(cache_queue_policy_get_prev_item
);
175 return ((struct cache_policy_item_
*)TAILQ_PREV(queue_item
,
176 cache_queue_policy_head_
, entries
));
180 * Initializes cache_queue_policy_ by filling the structure with the functions
181 * pointers, defined above
183 static struct cache_queue_policy_
*
184 init_cache_queue_policy(void)
186 struct cache_queue_policy_
*retval
;
188 TRACE_IN(init_cache_queue_policy
);
189 retval
= (struct cache_queue_policy_
*)calloc(1,
190 sizeof(struct cache_queue_policy_
));
191 assert(retval
!= NULL
);
193 retval
->parent_data
.create_item_func
= cache_queue_policy_create_item
;
194 retval
->parent_data
.destroy_item_func
= cache_queue_policy_destroy_item
;
196 retval
->parent_data
.add_item_func
= cache_queue_policy_add_item
;
197 retval
->parent_data
.remove_item_func
= cache_queue_policy_remove_item
;
199 retval
->parent_data
.get_first_item_func
=
200 cache_queue_policy_get_first_item
;
201 retval
->parent_data
.get_last_item_func
=
202 cache_queue_policy_get_last_item
;
203 retval
->parent_data
.get_next_item_func
=
204 cache_queue_policy_get_next_item
;
205 retval
->parent_data
.get_prev_item_func
=
206 cache_queue_policy_get_prev_item
;
208 TAILQ_INIT(&retval
->head
);
209 TRACE_OUT(init_cache_queue_policy
);
214 destroy_cache_queue_policy(struct cache_queue_policy_
*queue_policy
)
216 struct cache_queue_policy_item_
*queue_item
;
218 TRACE_IN(destroy_cache_queue_policy
);
219 while (!TAILQ_EMPTY(&queue_policy
->head
)) {
220 queue_item
= TAILQ_FIRST(&queue_policy
->head
);
221 TAILQ_REMOVE(&queue_policy
->head
, queue_item
, entries
);
222 cache_queue_policy_destroy_item(
223 (struct cache_policy_item_
*)queue_item
);
226 TRACE_OUT(destroy_cache_queue_policy
);
230 * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything,
231 * when the cache element is updated. So it always stays in its initial
232 * position in the queue - that is exactly the FIFO functionality.
235 cache_fifo_policy_update_item(struct cache_policy_
*policy
,
236 struct cache_policy_item_
*item
)
239 TRACE_IN(cache_fifo_policy_update_item
);
240 /* policy and item arguments are ignored */
241 TRACE_OUT(cache_fifo_policy_update_item
);
244 struct cache_policy_
*
245 init_cache_fifo_policy(void)
247 struct cache_queue_policy_
*retval
;
249 TRACE_IN(init_cache_fifo_policy
);
250 retval
= init_cache_queue_policy();
251 retval
->parent_data
.update_item_func
= cache_fifo_policy_update_item
;
253 TRACE_OUT(init_cache_fifo_policy
);
254 return ((struct cache_policy_
*)retval
);
258 destroy_cache_fifo_policy(struct cache_policy_
*policy
)
260 struct cache_queue_policy_
*queue_policy
;
262 TRACE_IN(destroy_cache_fifo_policy
);
263 queue_policy
= (struct cache_queue_policy_
*)policy
;
264 destroy_cache_queue_policy(queue_policy
);
265 TRACE_OUT(destroy_cache_fifo_policy
);
269 * Makes cache_queue_policy_ behave like LRU policy. On each update, cache
270 * element is moved to the end of the queue - so it would be deleted in last
271 * turn. That is exactly the LRU policy functionality.
274 cache_lru_policy_update_item(struct cache_policy_
*policy
,
275 struct cache_policy_item_
*item
)
277 struct cache_queue_policy_
*queue_policy
;
278 struct cache_queue_policy_item_
*queue_item
;
280 TRACE_IN(cache_lru_policy_update_item
);
281 queue_policy
= (struct cache_queue_policy_
*)policy
;
282 queue_item
= (struct cache_queue_policy_item_
*)item
;
284 TAILQ_REMOVE(&queue_policy
->head
, queue_item
, entries
);
285 TAILQ_INSERT_TAIL(&queue_policy
->head
, queue_item
, entries
);
286 TRACE_OUT(cache_lru_policy_update_item
);
289 struct cache_policy_
*
290 init_cache_lru_policy(void)
292 struct cache_queue_policy_
*retval
;
294 TRACE_IN(init_cache_lru_policy
);
295 retval
= init_cache_queue_policy();
296 retval
->parent_data
.update_item_func
= cache_lru_policy_update_item
;
298 TRACE_OUT(init_cache_lru_policy
);
299 return ((struct cache_policy_
*)retval
);
303 destroy_cache_lru_policy(struct cache_policy_
*policy
)
305 struct cache_queue_policy_
*queue_policy
;
307 TRACE_IN(destroy_cache_lru_policy
);
308 queue_policy
= (struct cache_queue_policy_
*)policy
;
309 destroy_cache_queue_policy(queue_policy
);
310 TRACE_OUT(destroy_cache_lru_policy
);
314 * LFU (least frequently used) policy implementation differs much from the
315 * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_
316 * functions are implemented specifically for this policy. The idea of this
317 * policy is to represent frequency (real number) as the integer number and
318 * use it as the index in the array. Each array's element is
319 * the list of elements. For example, if we have the 100-elements
320 * array for this policy, the elements with frequency 0.1 (calls per-second)
321 * would be in 10th element of the array.
323 static struct cache_policy_item_
*
324 cache_lfu_policy_create_item(void)
326 struct cache_lfu_policy_item_
*retval
;
328 TRACE_IN(cache_lfu_policy_create_item
);
329 retval
= (struct cache_lfu_policy_item_
*)calloc(1,
330 sizeof(struct cache_lfu_policy_item_
));
331 assert(retval
!= NULL
);
333 TRACE_OUT(cache_lfu_policy_create_item
);
334 return ((struct cache_policy_item_
*)retval
);
338 cache_lfu_policy_destroy_item(struct cache_policy_item_
*item
)
341 TRACE_IN(cache_lfu_policy_destroy_item
);
342 assert(item
!= NULL
);
344 TRACE_OUT(cache_lfu_policy_destroy_item
);
348 * When placed in the LFU policy queue for the first time, the maximum
349 * frequency is assigned to the element
352 cache_lfu_policy_add_item(struct cache_policy_
*policy
,
353 struct cache_policy_item_
*item
)
355 struct cache_lfu_policy_
*lfu_policy
;
356 struct cache_lfu_policy_item_
*lfu_item
;
358 TRACE_IN(cache_lfu_policy_add_item
);
359 lfu_policy
= (struct cache_lfu_policy_
*)policy
;
360 lfu_item
= (struct cache_lfu_policy_item_
*)item
;
362 lfu_item
->frequency
= CACHELIB_MAX_FREQUENCY
- 1;
363 TAILQ_INSERT_HEAD(&(lfu_policy
->groups
[CACHELIB_MAX_FREQUENCY
- 1]),
365 TRACE_OUT(cache_lfu_policy_add_item
);
369 * On each update the frequency of the element is recalculated and, if it
370 * changed, the element would be moved to the another place in the array.
373 cache_lfu_policy_update_item(struct cache_policy_
*policy
,
374 struct cache_policy_item_
*item
)
376 struct cache_lfu_policy_
*lfu_policy
;
377 struct cache_lfu_policy_item_
*lfu_item
;
380 TRACE_IN(cache_lfu_policy_update_item
);
381 lfu_policy
= (struct cache_lfu_policy_
*)policy
;
382 lfu_item
= (struct cache_lfu_policy_item_
*)item
;
385 * We calculate the square of the request_count to avoid grouping of
386 * all elements at the start of the array (for example, if array size is
387 * 100 and most of its elements has frequency below the 0.01, they
388 * all would be grouped in the first array's position). Other
389 * techniques should be used here later to ensure, that elements are
390 * equally distributed in the array and not grouped in its beginning.
392 if (lfu_item
->parent_data
.last_request_time
.tv_sec
!=
393 lfu_item
->parent_data
.creation_time
.tv_sec
) {
394 index
= ((double)lfu_item
->parent_data
.request_count
*
395 (double)lfu_item
->parent_data
.request_count
/
396 (lfu_item
->parent_data
.last_request_time
.tv_sec
-
397 lfu_item
->parent_data
.creation_time
.tv_sec
+ 1)) *
398 CACHELIB_MAX_FREQUENCY
;
399 if (index
>= CACHELIB_MAX_FREQUENCY
)
400 index
= CACHELIB_MAX_FREQUENCY
- 1;
402 index
= CACHELIB_MAX_FREQUENCY
- 1;
404 TAILQ_REMOVE(&(lfu_policy
->groups
[lfu_item
->frequency
]), lfu_item
,
406 lfu_item
->frequency
= index
;
407 TAILQ_INSERT_HEAD(&(lfu_policy
->groups
[index
]), lfu_item
, entries
);
409 TRACE_OUT(cache_lfu_policy_update_item
);
413 cache_lfu_policy_remove_item(struct cache_policy_
*policy
,
414 struct cache_policy_item_
*item
)
416 struct cache_lfu_policy_
*lfu_policy
;
417 struct cache_lfu_policy_item_
*lfu_item
;
419 TRACE_IN(cache_lfu_policy_remove_item
);
420 lfu_policy
= (struct cache_lfu_policy_
*)policy
;
421 lfu_item
= (struct cache_lfu_policy_item_
*)item
;
423 TAILQ_REMOVE(&(lfu_policy
->groups
[lfu_item
->frequency
]), lfu_item
,
425 TRACE_OUT(cache_lfu_policy_remove_item
);
428 static struct cache_policy_item_
*
429 cache_lfu_policy_get_first_item(struct cache_policy_
*policy
)
431 struct cache_lfu_policy_
*lfu_policy
;
432 struct cache_lfu_policy_item_
*lfu_item
;
435 TRACE_IN(cache_lfu_policy_get_first_item
);
437 lfu_policy
= (struct cache_lfu_policy_
*)policy
;
438 for (i
= 0; i
< CACHELIB_MAX_FREQUENCY
; ++i
)
439 if (!TAILQ_EMPTY(&(lfu_policy
->groups
[i
]))) {
440 lfu_item
= TAILQ_FIRST(&(lfu_policy
->groups
[i
]));
444 TRACE_OUT(cache_lfu_policy_get_first_item
);
445 return ((struct cache_policy_item_
*)lfu_item
);
448 static struct cache_policy_item_
*
449 cache_lfu_policy_get_last_item(struct cache_policy_
*policy
)
451 struct cache_lfu_policy_
*lfu_policy
;
452 struct cache_lfu_policy_item_
*lfu_item
;
455 TRACE_IN(cache_lfu_policy_get_last_item
);
457 lfu_policy
= (struct cache_lfu_policy_
*)policy
;
458 for (i
= CACHELIB_MAX_FREQUENCY
- 1; i
>= 0; --i
)
459 if (!TAILQ_EMPTY(&(lfu_policy
->groups
[i
]))) {
460 lfu_item
= TAILQ_LAST(&(lfu_policy
->groups
[i
]),
461 cache_lfu_policy_group_
);
465 TRACE_OUT(cache_lfu_policy_get_last_item
);
466 return ((struct cache_policy_item_
*)lfu_item
);
469 static struct cache_policy_item_
*
470 cache_lfu_policy_get_next_item(struct cache_policy_
*policy
,
471 struct cache_policy_item_
*item
)
473 struct cache_lfu_policy_
*lfu_policy
;
474 struct cache_lfu_policy_item_
*lfu_item
;
477 TRACE_IN(cache_lfu_policy_get_next_item
);
478 lfu_policy
= (struct cache_lfu_policy_
*)policy
;
479 lfu_item
= TAILQ_NEXT((struct cache_lfu_policy_item_
*)item
, entries
);
480 if (lfu_item
== NULL
)
482 for (i
= ((struct cache_lfu_policy_item_
*)item
)->frequency
+ 1;
483 i
< CACHELIB_MAX_FREQUENCY
; ++i
) {
484 if (!TAILQ_EMPTY(&(lfu_policy
->groups
[i
]))) {
485 lfu_item
= TAILQ_FIRST(&(lfu_policy
->groups
[i
]));
491 TRACE_OUT(cache_lfu_policy_get_next_item
);
492 return ((struct cache_policy_item_
*)lfu_item
);
495 static struct cache_policy_item_
*
496 cache_lfu_policy_get_prev_item(struct cache_policy_
*policy
,
497 struct cache_policy_item_
*item
)
499 struct cache_lfu_policy_
*lfu_policy
;
500 struct cache_lfu_policy_item_
*lfu_item
;
503 TRACE_IN(cache_lfu_policy_get_prev_item
);
504 lfu_policy
= (struct cache_lfu_policy_
*)policy
;
505 lfu_item
= TAILQ_PREV((struct cache_lfu_policy_item_
*)item
,
506 cache_lfu_policy_group_
, entries
);
507 if (lfu_item
== NULL
)
509 for (i
= ((struct cache_lfu_policy_item_
*)item
)->frequency
- 1;
511 if (!TAILQ_EMPTY(&(lfu_policy
->groups
[i
]))) {
512 lfu_item
= TAILQ_LAST(&(lfu_policy
->groups
[i
]),
513 cache_lfu_policy_group_
);
518 TRACE_OUT(cache_lfu_policy_get_prev_item
);
519 return ((struct cache_policy_item_
*)lfu_item
);
523 * Initializes the cache_policy_ structure by filling it with appropriate
526 struct cache_policy_
*
527 init_cache_lfu_policy(void)
530 struct cache_lfu_policy_
*retval
;
532 TRACE_IN(init_cache_lfu_policy
);
533 retval
= (struct cache_lfu_policy_
*)calloc(1,
534 sizeof(struct cache_lfu_policy_
));
535 assert(retval
!= NULL
);
537 retval
->parent_data
.create_item_func
= cache_lfu_policy_create_item
;
538 retval
->parent_data
.destroy_item_func
= cache_lfu_policy_destroy_item
;
540 retval
->parent_data
.add_item_func
= cache_lfu_policy_add_item
;
541 retval
->parent_data
.update_item_func
= cache_lfu_policy_update_item
;
542 retval
->parent_data
.remove_item_func
= cache_lfu_policy_remove_item
;
544 retval
->parent_data
.get_first_item_func
=
545 cache_lfu_policy_get_first_item
;
546 retval
->parent_data
.get_last_item_func
=
547 cache_lfu_policy_get_last_item
;
548 retval
->parent_data
.get_next_item_func
=
549 cache_lfu_policy_get_next_item
;
550 retval
->parent_data
.get_prev_item_func
=
551 cache_lfu_policy_get_prev_item
;
553 for (i
= 0; i
< CACHELIB_MAX_FREQUENCY
; ++i
)
554 TAILQ_INIT(&(retval
->groups
[i
]));
556 TRACE_OUT(init_cache_lfu_policy
);
557 return ((struct cache_policy_
*)retval
);
561 destroy_cache_lfu_policy(struct cache_policy_
*policy
)
564 struct cache_lfu_policy_
*lfu_policy
;
565 struct cache_lfu_policy_item_
*lfu_item
;
567 TRACE_IN(destroy_cache_lfu_policy
);
568 lfu_policy
= (struct cache_lfu_policy_
*)policy
;
569 for (i
= 0; i
< CACHELIB_MAX_FREQUENCY
; ++i
) {
570 while (!TAILQ_EMPTY(&(lfu_policy
->groups
[i
]))) {
571 lfu_item
= TAILQ_FIRST(&(lfu_policy
->groups
[i
]));
572 TAILQ_REMOVE(&(lfu_policy
->groups
[i
]), lfu_item
,
574 cache_lfu_policy_destroy_item(
575 (struct cache_policy_item_
*)lfu_item
);
579 TRACE_OUT(destroy_cache_lfu_policy
);