1/*- 2 * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 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. 13 * 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 24 * SUCH DAMAGE. 25 * 26 */ 27 28#include <sys/cdefs.h> 29#include <sys/time.h> 30 31#include <assert.h> 32#include <stdlib.h> 33#include <string.h> 34 35#include "cacheplcs.h" 36#include "debug.h" 37 38static void cache_fifo_policy_update_item(struct cache_policy_ *, 39 struct cache_policy_item_ *); 40static void cache_lfu_policy_add_item(struct cache_policy_ *, 41 struct cache_policy_item_ *); 42static struct cache_policy_item_ * cache_lfu_policy_create_item(void); 43static void cache_lfu_policy_destroy_item(struct cache_policy_item_ *); 44static struct cache_policy_item_ *cache_lfu_policy_get_first_item( 45 struct cache_policy_ *); 46static struct cache_policy_item_ *cache_lfu_policy_get_last_item( 47 struct cache_policy_ *); 48static struct cache_policy_item_ *cache_lfu_policy_get_next_item( 49 struct cache_policy_ *, struct cache_policy_item_ *); 50static struct cache_policy_item_ *cache_lfu_policy_get_prev_item( 51 struct cache_policy_ *, struct cache_policy_item_ *); 52static void cache_lfu_policy_remove_item(struct cache_policy_ *, 53 struct cache_policy_item_ *); 54static void cache_lfu_policy_update_item(struct cache_policy_ *, 55 struct cache_policy_item_ *); 56static void cache_lru_policy_update_item(struct cache_policy_ *, 57 struct cache_policy_item_ *); 58static void cache_queue_policy_add_item(struct cache_policy_ *, 59 struct cache_policy_item_ *); 60static struct cache_policy_item_ * cache_queue_policy_create_item(void); 61static void cache_queue_policy_destroy_item(struct cache_policy_item_ *); 62static struct cache_policy_item_ *cache_queue_policy_get_first_item( 63 struct cache_policy_ *); 64static struct cache_policy_item_ *cache_queue_policy_get_last_item( 65 struct cache_policy_ *); 66static struct cache_policy_item_ *cache_queue_policy_get_next_item( 67 struct cache_policy_ *, struct cache_policy_item_ *); 68static struct cache_policy_item_ *cache_queue_policy_get_prev_item( 69 struct cache_policy_ *, struct cache_policy_item_ *); 70static void cache_queue_policy_remove_item(struct cache_policy_ *, 71 struct cache_policy_item_ *); 72static void destroy_cache_queue_policy(struct cache_queue_policy_ *); 73static struct cache_queue_policy_ *init_cache_queue_policy(void); 74 75/* 76 * All cache_queue_policy_XXX functions below will be used to fill 77 * the cache_queue_policy structure. They implement the most functionality of 78 * LRU and FIFO policies. LRU and FIFO policies are actually the 79 * cache_queue_policy_ with cache_update_item function changed. 80 */ 81static struct cache_policy_item_ * 82cache_queue_policy_create_item(void) 83{ 84 struct cache_queue_policy_item_ *retval; 85 86 TRACE_IN(cache_queue_policy_create_item); 87 retval = calloc(1, 88 sizeof(*retval)); 89 assert(retval != NULL); 90 91 TRACE_OUT(cache_queue_policy_create_item); 92 return ((struct cache_policy_item_ *)retval); 93} 94 95static void 96cache_queue_policy_destroy_item(struct cache_policy_item_ *item) 97{ 98 99 TRACE_IN(cache_queue_policy_destroy_item); 100 assert(item != NULL); 101 free(item); 102 TRACE_OUT(cache_queue_policy_destroy_item); 103} 104 105static void 106cache_queue_policy_add_item(struct cache_policy_ *policy, 107 struct cache_policy_item_ *item) 108{ 109 struct cache_queue_policy_ *queue_policy; 110 struct cache_queue_policy_item_ *queue_item; 111 112 TRACE_IN(cache_queue_policy_add_item); 113 queue_policy = (struct cache_queue_policy_ *)policy; 114 queue_item = (struct cache_queue_policy_item_ *)item; 115 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 116 TRACE_OUT(cache_queue_policy_add_item); 117} 118 119static void 120cache_queue_policy_remove_item(struct cache_policy_ *policy, 121 struct cache_policy_item_ *item) 122{ 123 struct cache_queue_policy_ *queue_policy; 124 struct cache_queue_policy_item_ *queue_item; 125 126 TRACE_IN(cache_queue_policy_remove_item); 127 queue_policy = (struct cache_queue_policy_ *)policy; 128 queue_item = (struct cache_queue_policy_item_ *)item; 129 TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 130 TRACE_OUT(cache_queue_policy_remove_item); 131} 132 133static struct cache_policy_item_ * 134cache_queue_policy_get_first_item(struct cache_policy_ *policy) 135{ 136 struct cache_queue_policy_ *queue_policy; 137 138 TRACE_IN(cache_queue_policy_get_first_item); 139 queue_policy = (struct cache_queue_policy_ *)policy; 140 TRACE_OUT(cache_queue_policy_get_first_item); 141 return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head)); 142} 143 144static struct cache_policy_item_ * 145cache_queue_policy_get_last_item(struct cache_policy_ *policy) 146{ 147 struct cache_queue_policy_ *queue_policy; 148 149 TRACE_IN(cache_queue_policy_get_last_item); 150 queue_policy = (struct cache_queue_policy_ *)policy; 151 TRACE_OUT(cache_queue_policy_get_last_item); 152 return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head, 153 cache_queue_policy_head_)); 154} 155 156static struct cache_policy_item_ * 157cache_queue_policy_get_next_item(struct cache_policy_ *policy, 158 struct cache_policy_item_ *item) 159{ 160 struct cache_queue_policy_item_ *queue_item; 161 162 TRACE_IN(cache_queue_policy_get_next_item); 163 queue_item = (struct cache_queue_policy_item_ *)item; 164 165 TRACE_OUT(cache_queue_policy_get_next_item); 166 return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries)); 167} 168 169static struct cache_policy_item_ * 170cache_queue_policy_get_prev_item(struct cache_policy_ *policy, 171 struct cache_policy_item_ *item) 172{ 173 struct cache_queue_policy_item_ *queue_item; 174 175 TRACE_IN(cache_queue_policy_get_prev_item); 176 queue_item = (struct cache_queue_policy_item_ *)item; 177 178 TRACE_OUT(cache_queue_policy_get_prev_item); 179 return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item, 180 cache_queue_policy_head_, entries)); 181} 182 183/* 184 * Initializes cache_queue_policy_ by filling the structure with the functions 185 * pointers, defined above 186 */ 187static struct cache_queue_policy_ * 188init_cache_queue_policy(void) 189{ 190 struct cache_queue_policy_ *retval; 191 192 TRACE_IN(init_cache_queue_policy); 193 retval = calloc(1, 194 sizeof(*retval)); 195 assert(retval != NULL); 196 197 retval->parent_data.create_item_func = cache_queue_policy_create_item; 198 retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item; 199 200 retval->parent_data.add_item_func = cache_queue_policy_add_item; 201 retval->parent_data.remove_item_func = cache_queue_policy_remove_item; 202 203 retval->parent_data.get_first_item_func = 204 cache_queue_policy_get_first_item; 205 retval->parent_data.get_last_item_func = 206 cache_queue_policy_get_last_item; 207 retval->parent_data.get_next_item_func = 208 cache_queue_policy_get_next_item; 209 retval->parent_data.get_prev_item_func = 210 cache_queue_policy_get_prev_item; 211 212 TAILQ_INIT(&retval->head); 213 TRACE_OUT(init_cache_queue_policy); 214 return (retval); 215} 216 217static void 218destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy) 219{ 220 struct cache_queue_policy_item_ *queue_item; 221 222 TRACE_IN(destroy_cache_queue_policy); 223 while (!TAILQ_EMPTY(&queue_policy->head)) { 224 queue_item = TAILQ_FIRST(&queue_policy->head); 225 TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 226 cache_queue_policy_destroy_item( 227 (struct cache_policy_item_ *)queue_item); 228 } 229 free(queue_policy); 230 TRACE_OUT(destroy_cache_queue_policy); 231} 232 233/* 234 * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything, 235 * when the cache element is updated. So it always stays in its initial 236 * position in the queue - that is exactly the FIFO functionality. 237 */ 238static void 239cache_fifo_policy_update_item(struct cache_policy_ *policy, 240 struct cache_policy_item_ *item) 241{ 242 243 TRACE_IN(cache_fifo_policy_update_item); 244 /* policy and item arguments are ignored */ 245 TRACE_OUT(cache_fifo_policy_update_item); 246} 247 248struct cache_policy_ * 249init_cache_fifo_policy(void) 250{ 251 struct cache_queue_policy_ *retval; 252 253 TRACE_IN(init_cache_fifo_policy); 254 retval = init_cache_queue_policy(); 255 retval->parent_data.update_item_func = cache_fifo_policy_update_item; 256 257 TRACE_OUT(init_cache_fifo_policy); 258 return ((struct cache_policy_ *)retval); 259} 260 261void 262destroy_cache_fifo_policy(struct cache_policy_ *policy) 263{ 264 struct cache_queue_policy_ *queue_policy; 265 266 TRACE_IN(destroy_cache_fifo_policy); 267 queue_policy = (struct cache_queue_policy_ *)policy; 268 destroy_cache_queue_policy(queue_policy); 269 TRACE_OUT(destroy_cache_fifo_policy); 270} 271 272/* 273 * Makes cache_queue_policy_ behave like LRU policy. On each update, cache 274 * element is moved to the end of the queue - so it would be deleted in last 275 * turn. That is exactly the LRU policy functionality. 276 */ 277static void 278cache_lru_policy_update_item(struct cache_policy_ *policy, 279 struct cache_policy_item_ *item) 280{ 281 struct cache_queue_policy_ *queue_policy; 282 struct cache_queue_policy_item_ *queue_item; 283 284 TRACE_IN(cache_lru_policy_update_item); 285 queue_policy = (struct cache_queue_policy_ *)policy; 286 queue_item = (struct cache_queue_policy_item_ *)item; 287 288 TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 289 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 290 TRACE_OUT(cache_lru_policy_update_item); 291} 292 293struct cache_policy_ * 294init_cache_lru_policy(void) 295{ 296 struct cache_queue_policy_ *retval; 297 298 TRACE_IN(init_cache_lru_policy); 299 retval = init_cache_queue_policy(); 300 retval->parent_data.update_item_func = cache_lru_policy_update_item; 301 302 TRACE_OUT(init_cache_lru_policy); 303 return ((struct cache_policy_ *)retval); 304} 305 306void 307destroy_cache_lru_policy(struct cache_policy_ *policy) 308{ 309 struct cache_queue_policy_ *queue_policy; 310 311 TRACE_IN(destroy_cache_lru_policy); 312 queue_policy = (struct cache_queue_policy_ *)policy; 313 destroy_cache_queue_policy(queue_policy); 314 TRACE_OUT(destroy_cache_lru_policy); 315} 316 317/* 318 * LFU (least frequently used) policy implementation differs much from the 319 * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_ 320 * functions are implemented specifically for this policy. The idea of this 321 * policy is to represent frequency (real number) as the integer number and 322 * use it as the index in the array. Each array's element is 323 * the list of elements. For example, if we have the 100-elements 324 * array for this policy, the elements with frequency 0.1 (calls per-second) 325 * would be in 10th element of the array. 326 */ 327static struct cache_policy_item_ * 328cache_lfu_policy_create_item(void) 329{ 330 struct cache_lfu_policy_item_ *retval; 331 332 TRACE_IN(cache_lfu_policy_create_item); 333 retval = calloc(1, 334 sizeof(*retval)); 335 assert(retval != NULL); 336 337 TRACE_OUT(cache_lfu_policy_create_item); 338 return ((struct cache_policy_item_ *)retval); 339} 340 341static void 342cache_lfu_policy_destroy_item(struct cache_policy_item_ *item) 343{ 344 345 TRACE_IN(cache_lfu_policy_destroy_item); 346 assert(item != NULL); 347 free(item); 348 TRACE_OUT(cache_lfu_policy_destroy_item); 349} 350 351/* 352 * When placed in the LFU policy queue for the first time, the maximum 353 * frequency is assigned to the element 354 */ 355static void 356cache_lfu_policy_add_item(struct cache_policy_ *policy, 357 struct cache_policy_item_ *item) 358{ 359 struct cache_lfu_policy_ *lfu_policy; 360 struct cache_lfu_policy_item_ *lfu_item; 361 362 TRACE_IN(cache_lfu_policy_add_item); 363 lfu_policy = (struct cache_lfu_policy_ *)policy; 364 lfu_item = (struct cache_lfu_policy_item_ *)item; 365 366 lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1; 367 TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]), 368 lfu_item, entries); 369 TRACE_OUT(cache_lfu_policy_add_item); 370} 371 372/* 373 * On each update the frequency of the element is recalculated and, if it 374 * changed, the element would be moved to the another place in the array. 375 */ 376static void 377cache_lfu_policy_update_item(struct cache_policy_ *policy, 378 struct cache_policy_item_ *item) 379{ 380 struct cache_lfu_policy_ *lfu_policy; 381 struct cache_lfu_policy_item_ *lfu_item; 382 int index; 383 384 TRACE_IN(cache_lfu_policy_update_item); 385 lfu_policy = (struct cache_lfu_policy_ *)policy; 386 lfu_item = (struct cache_lfu_policy_item_ *)item; 387 388 /* 389 * We calculate the square of the request_count to avoid grouping of 390 * all elements at the start of the array (for example, if array size is 391 * 100 and most of its elements has frequency below the 0.01, they 392 * all would be grouped in the first array's position). Other 393 * techniques should be used here later to ensure, that elements are 394 * equally distributed in the array and not grouped in its beginning. 395 */ 396 if (lfu_item->parent_data.last_request_time.tv_sec != 397 lfu_item->parent_data.creation_time.tv_sec) { 398 index = ((double)lfu_item->parent_data.request_count * 399 (double)lfu_item->parent_data.request_count / 400 (lfu_item->parent_data.last_request_time.tv_sec - 401 lfu_item->parent_data.creation_time.tv_sec + 1)) * 402 CACHELIB_MAX_FREQUENCY; 403 if (index >= CACHELIB_MAX_FREQUENCY) 404 index = CACHELIB_MAX_FREQUENCY - 1; 405 } else 406 index = CACHELIB_MAX_FREQUENCY - 1; 407 408 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 409 entries); 410 lfu_item->frequency = index; 411 TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries); 412 413 TRACE_OUT(cache_lfu_policy_update_item); 414} 415 416static void 417cache_lfu_policy_remove_item(struct cache_policy_ *policy, 418 struct cache_policy_item_ *item) 419{ 420 struct cache_lfu_policy_ *lfu_policy; 421 struct cache_lfu_policy_item_ *lfu_item; 422 423 TRACE_IN(cache_lfu_policy_remove_item); 424 lfu_policy = (struct cache_lfu_policy_ *)policy; 425 lfu_item = (struct cache_lfu_policy_item_ *)item; 426 427 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 428 entries); 429 TRACE_OUT(cache_lfu_policy_remove_item); 430} 431 432static struct cache_policy_item_ * 433cache_lfu_policy_get_first_item(struct cache_policy_ *policy) 434{ 435 struct cache_lfu_policy_ *lfu_policy; 436 struct cache_lfu_policy_item_ *lfu_item; 437 int i; 438 439 TRACE_IN(cache_lfu_policy_get_first_item); 440 lfu_item = NULL; 441 lfu_policy = (struct cache_lfu_policy_ *)policy; 442 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 443 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 444 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 445 break; 446 } 447 448 TRACE_OUT(cache_lfu_policy_get_first_item); 449 return ((struct cache_policy_item_ *)lfu_item); 450} 451 452static struct cache_policy_item_ * 453cache_lfu_policy_get_last_item(struct cache_policy_ *policy) 454{ 455 struct cache_lfu_policy_ *lfu_policy; 456 struct cache_lfu_policy_item_ *lfu_item; 457 int i; 458 459 TRACE_IN(cache_lfu_policy_get_last_item); 460 lfu_item = NULL; 461 lfu_policy = (struct cache_lfu_policy_ *)policy; 462 for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i) 463 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 464 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 465 cache_lfu_policy_group_); 466 break; 467 } 468 469 TRACE_OUT(cache_lfu_policy_get_last_item); 470 return ((struct cache_policy_item_ *)lfu_item); 471} 472 473static struct cache_policy_item_ * 474cache_lfu_policy_get_next_item(struct cache_policy_ *policy, 475 struct cache_policy_item_ *item) 476{ 477 struct cache_lfu_policy_ *lfu_policy; 478 struct cache_lfu_policy_item_ *lfu_item; 479 int i; 480 481 TRACE_IN(cache_lfu_policy_get_next_item); 482 lfu_policy = (struct cache_lfu_policy_ *)policy; 483 lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries); 484 if (lfu_item == NULL) 485 { 486 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1; 487 i < CACHELIB_MAX_FREQUENCY; ++i) { 488 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 489 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 490 break; 491 } 492 } 493 } 494 495 TRACE_OUT(cache_lfu_policy_get_next_item); 496 return ((struct cache_policy_item_ *)lfu_item); 497} 498 499static struct cache_policy_item_ * 500cache_lfu_policy_get_prev_item(struct cache_policy_ *policy, 501 struct cache_policy_item_ *item) 502{ 503 struct cache_lfu_policy_ *lfu_policy; 504 struct cache_lfu_policy_item_ *lfu_item; 505 int i; 506 507 TRACE_IN(cache_lfu_policy_get_prev_item); 508 lfu_policy = (struct cache_lfu_policy_ *)policy; 509 lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item, 510 cache_lfu_policy_group_, entries); 511 if (lfu_item == NULL) 512 { 513 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1; 514 i >= 0; --i) 515 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 516 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 517 cache_lfu_policy_group_); 518 break; 519 } 520 } 521 522 TRACE_OUT(cache_lfu_policy_get_prev_item); 523 return ((struct cache_policy_item_ *)lfu_item); 524} 525 526/* 527 * Initializes the cache_policy_ structure by filling it with appropriate 528 * functions pointers 529 */ 530struct cache_policy_ * 531init_cache_lfu_policy(void) 532{ 533 int i; 534 struct cache_lfu_policy_ *retval; 535 536 TRACE_IN(init_cache_lfu_policy); 537 retval = calloc(1, 538 sizeof(*retval)); 539 assert(retval != NULL); 540 541 retval->parent_data.create_item_func = cache_lfu_policy_create_item; 542 retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item; 543 544 retval->parent_data.add_item_func = cache_lfu_policy_add_item; 545 retval->parent_data.update_item_func = cache_lfu_policy_update_item; 546 retval->parent_data.remove_item_func = cache_lfu_policy_remove_item; 547 548 retval->parent_data.get_first_item_func = 549 cache_lfu_policy_get_first_item; 550 retval->parent_data.get_last_item_func = 551 cache_lfu_policy_get_last_item; 552 retval->parent_data.get_next_item_func = 553 cache_lfu_policy_get_next_item; 554 retval->parent_data.get_prev_item_func = 555 cache_lfu_policy_get_prev_item; 556 557 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 558 TAILQ_INIT(&(retval->groups[i])); 559 560 TRACE_OUT(init_cache_lfu_policy); 561 return ((struct cache_policy_ *)retval); 562} 563 564void 565destroy_cache_lfu_policy(struct cache_policy_ *policy) 566{ 567 int i; 568 struct cache_lfu_policy_ *lfu_policy; 569 struct cache_lfu_policy_item_ *lfu_item; 570 571 TRACE_IN(destroy_cache_lfu_policy); 572 lfu_policy = (struct cache_lfu_policy_ *)policy; 573 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) { 574 while (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 575 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 576 TAILQ_REMOVE(&(lfu_policy->groups[i]), lfu_item, 577 entries); 578 cache_lfu_policy_destroy_item( 579 (struct cache_policy_item_ *)lfu_item); 580 } 581 } 582 free(policy); 583 TRACE_OUT(destroy_cache_lfu_policy); 584} 585