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 __FBSDID("$FreeBSD$"); 30 31 #include <sys/time.h> 32 33 #include <assert.h> 34 #include <stdlib.h> 35 #include <string.h> 36 37 #include "cacheplcs.h" 38 #include "debug.h" 39 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); 76 77 /* 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. 82 */ 83 static struct cache_policy_item_ * 84 cache_queue_policy_create_item(void) 85 { 86 struct cache_queue_policy_item_ *retval; 87 88 TRACE_IN(cache_queue_policy_create_item); 89 retval = calloc(1, 90 sizeof(*retval)); 91 assert(retval != NULL); 92 93 TRACE_OUT(cache_queue_policy_create_item); 94 return ((struct cache_policy_item_ *)retval); 95 } 96 97 static void 98 cache_queue_policy_destroy_item(struct cache_policy_item_ *item) 99 { 100 101 TRACE_IN(cache_queue_policy_destroy_item); 102 assert(item != NULL); 103 free(item); 104 TRACE_OUT(cache_queue_policy_destroy_item); 105 } 106 107 static void 108 cache_queue_policy_add_item(struct cache_policy_ *policy, 109 struct cache_policy_item_ *item) 110 { 111 struct cache_queue_policy_ *queue_policy; 112 struct cache_queue_policy_item_ *queue_item; 113 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); 119 } 120 121 static void 122 cache_queue_policy_remove_item(struct cache_policy_ *policy, 123 struct cache_policy_item_ *item) 124 { 125 struct cache_queue_policy_ *queue_policy; 126 struct cache_queue_policy_item_ *queue_item; 127 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); 133 } 134 135 static struct cache_policy_item_ * 136 cache_queue_policy_get_first_item(struct cache_policy_ *policy) 137 { 138 struct cache_queue_policy_ *queue_policy; 139 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)); 144 } 145 146 static struct cache_policy_item_ * 147 cache_queue_policy_get_last_item(struct cache_policy_ *policy) 148 { 149 struct cache_queue_policy_ *queue_policy; 150 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_)); 156 } 157 158 static struct cache_policy_item_ * 159 cache_queue_policy_get_next_item(struct cache_policy_ *policy, 160 struct cache_policy_item_ *item) 161 { 162 struct cache_queue_policy_item_ *queue_item; 163 164 TRACE_IN(cache_queue_policy_get_next_item); 165 queue_item = (struct cache_queue_policy_item_ *)item; 166 167 TRACE_OUT(cache_queue_policy_get_next_item); 168 return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries)); 169 } 170 171 static struct cache_policy_item_ * 172 cache_queue_policy_get_prev_item(struct cache_policy_ *policy, 173 struct cache_policy_item_ *item) 174 { 175 struct cache_queue_policy_item_ *queue_item; 176 177 TRACE_IN(cache_queue_policy_get_prev_item); 178 queue_item = (struct cache_queue_policy_item_ *)item; 179 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)); 183 } 184 185 /* 186 * Initializes cache_queue_policy_ by filling the structure with the functions 187 * pointers, defined above 188 */ 189 static struct cache_queue_policy_ * 190 init_cache_queue_policy(void) 191 { 192 struct cache_queue_policy_ *retval; 193 194 TRACE_IN(init_cache_queue_policy); 195 retval = calloc(1, 196 sizeof(*retval)); 197 assert(retval != NULL); 198 199 retval->parent_data.create_item_func = cache_queue_policy_create_item; 200 retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item; 201 202 retval->parent_data.add_item_func = cache_queue_policy_add_item; 203 retval->parent_data.remove_item_func = cache_queue_policy_remove_item; 204 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; 213 214 TAILQ_INIT(&retval->head); 215 TRACE_OUT(init_cache_queue_policy); 216 return (retval); 217 } 218 219 static void 220 destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy) 221 { 222 struct cache_queue_policy_item_ *queue_item; 223 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); 230 } 231 free(queue_policy); 232 TRACE_OUT(destroy_cache_queue_policy); 233 } 234 235 /* 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. 239 */ 240 static void 241 cache_fifo_policy_update_item(struct cache_policy_ *policy, 242 struct cache_policy_item_ *item) 243 { 244 245 TRACE_IN(cache_fifo_policy_update_item); 246 /* policy and item arguments are ignored */ 247 TRACE_OUT(cache_fifo_policy_update_item); 248 } 249 250 struct cache_policy_ * 251 init_cache_fifo_policy(void) 252 { 253 struct cache_queue_policy_ *retval; 254 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; 258 259 TRACE_OUT(init_cache_fifo_policy); 260 return ((struct cache_policy_ *)retval); 261 } 262 263 void 264 destroy_cache_fifo_policy(struct cache_policy_ *policy) 265 { 266 struct cache_queue_policy_ *queue_policy; 267 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); 272 } 273 274 /* 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. 278 */ 279 static void 280 cache_lru_policy_update_item(struct cache_policy_ *policy, 281 struct cache_policy_item_ *item) 282 { 283 struct cache_queue_policy_ *queue_policy; 284 struct cache_queue_policy_item_ *queue_item; 285 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; 289 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); 293 } 294 295 struct cache_policy_ * 296 init_cache_lru_policy(void) 297 { 298 struct cache_queue_policy_ *retval; 299 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; 303 304 TRACE_OUT(init_cache_lru_policy); 305 return ((struct cache_policy_ *)retval); 306 } 307 308 void 309 destroy_cache_lru_policy(struct cache_policy_ *policy) 310 { 311 struct cache_queue_policy_ *queue_policy; 312 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); 317 } 318 319 /* 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. 328 */ 329 static struct cache_policy_item_ * 330 cache_lfu_policy_create_item(void) 331 { 332 struct cache_lfu_policy_item_ *retval; 333 334 TRACE_IN(cache_lfu_policy_create_item); 335 retval = calloc(1, 336 sizeof(*retval)); 337 assert(retval != NULL); 338 339 TRACE_OUT(cache_lfu_policy_create_item); 340 return ((struct cache_policy_item_ *)retval); 341 } 342 343 static void 344 cache_lfu_policy_destroy_item(struct cache_policy_item_ *item) 345 { 346 347 TRACE_IN(cache_lfu_policy_destroy_item); 348 assert(item != NULL); 349 free(item); 350 TRACE_OUT(cache_lfu_policy_destroy_item); 351 } 352 353 /* 354 * When placed in the LFU policy queue for the first time, the maximum 355 * frequency is assigned to the element 356 */ 357 static void 358 cache_lfu_policy_add_item(struct cache_policy_ *policy, 359 struct cache_policy_item_ *item) 360 { 361 struct cache_lfu_policy_ *lfu_policy; 362 struct cache_lfu_policy_item_ *lfu_item; 363 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; 367 368 lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1; 369 TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]), 370 lfu_item, entries); 371 TRACE_OUT(cache_lfu_policy_add_item); 372 } 373 374 /* 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. 377 */ 378 static void 379 cache_lfu_policy_update_item(struct cache_policy_ *policy, 380 struct cache_policy_item_ *item) 381 { 382 struct cache_lfu_policy_ *lfu_policy; 383 struct cache_lfu_policy_item_ *lfu_item; 384 int index; 385 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; 389 390 /* 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. 397 */ 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; 407 } else 408 index = CACHELIB_MAX_FREQUENCY - 1; 409 410 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 411 entries); 412 lfu_item->frequency = index; 413 TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries); 414 415 TRACE_OUT(cache_lfu_policy_update_item); 416 } 417 418 static void 419 cache_lfu_policy_remove_item(struct cache_policy_ *policy, 420 struct cache_policy_item_ *item) 421 { 422 struct cache_lfu_policy_ *lfu_policy; 423 struct cache_lfu_policy_item_ *lfu_item; 424 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; 428 429 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 430 entries); 431 TRACE_OUT(cache_lfu_policy_remove_item); 432 } 433 434 static struct cache_policy_item_ * 435 cache_lfu_policy_get_first_item(struct cache_policy_ *policy) 436 { 437 struct cache_lfu_policy_ *lfu_policy; 438 struct cache_lfu_policy_item_ *lfu_item; 439 int i; 440 441 TRACE_IN(cache_lfu_policy_get_first_item); 442 lfu_item = NULL; 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])); 447 break; 448 } 449 450 TRACE_OUT(cache_lfu_policy_get_first_item); 451 return ((struct cache_policy_item_ *)lfu_item); 452 } 453 454 static struct cache_policy_item_ * 455 cache_lfu_policy_get_last_item(struct cache_policy_ *policy) 456 { 457 struct cache_lfu_policy_ *lfu_policy; 458 struct cache_lfu_policy_item_ *lfu_item; 459 int i; 460 461 TRACE_IN(cache_lfu_policy_get_last_item); 462 lfu_item = NULL; 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_); 468 break; 469 } 470 471 TRACE_OUT(cache_lfu_policy_get_last_item); 472 return ((struct cache_policy_item_ *)lfu_item); 473 } 474 475 static struct cache_policy_item_ * 476 cache_lfu_policy_get_next_item(struct cache_policy_ *policy, 477 struct cache_policy_item_ *item) 478 { 479 struct cache_lfu_policy_ *lfu_policy; 480 struct cache_lfu_policy_item_ *lfu_item; 481 int i; 482 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) 487 { 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])); 492 break; 493 } 494 } 495 } 496 497 TRACE_OUT(cache_lfu_policy_get_next_item); 498 return ((struct cache_policy_item_ *)lfu_item); 499 } 500 501 static struct cache_policy_item_ * 502 cache_lfu_policy_get_prev_item(struct cache_policy_ *policy, 503 struct cache_policy_item_ *item) 504 { 505 struct cache_lfu_policy_ *lfu_policy; 506 struct cache_lfu_policy_item_ *lfu_item; 507 int i; 508 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) 514 { 515 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1; 516 i >= 0; --i) 517 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 518 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 519 cache_lfu_policy_group_); 520 break; 521 } 522 } 523 524 TRACE_OUT(cache_lfu_policy_get_prev_item); 525 return ((struct cache_policy_item_ *)lfu_item); 526 } 527 528 /* 529 * Initializes the cache_policy_ structure by filling it with appropriate 530 * functions pointers 531 */ 532 struct cache_policy_ * 533 init_cache_lfu_policy(void) 534 { 535 int i; 536 struct cache_lfu_policy_ *retval; 537 538 TRACE_IN(init_cache_lfu_policy); 539 retval = calloc(1, 540 sizeof(*retval)); 541 assert(retval != NULL); 542 543 retval->parent_data.create_item_func = cache_lfu_policy_create_item; 544 retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item; 545 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; 549 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; 558 559 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 560 TAILQ_INIT(&(retval->groups[i])); 561 562 TRACE_OUT(init_cache_lfu_policy); 563 return ((struct cache_policy_ *)retval); 564 } 565 566 void 567 destroy_cache_lfu_policy(struct cache_policy_ *policy) 568 { 569 int i; 570 struct cache_lfu_policy_ *lfu_policy; 571 struct cache_lfu_policy_item_ *lfu_item; 572 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, 579 entries); 580 cache_lfu_policy_destroy_item( 581 (struct cache_policy_item_ *)lfu_item); 582 } 583 } 584 free(policy); 585 TRACE_OUT(destroy_cache_lfu_policy); 586 } 587