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_ *queue_policy; 163 struct cache_queue_policy_item_ *queue_item; 164 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; 168 169 TRACE_OUT(cache_queue_policy_get_next_item); 170 return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries)); 171 } 172 173 static struct cache_policy_item_ * 174 cache_queue_policy_get_prev_item(struct cache_policy_ *policy, 175 struct cache_policy_item_ *item) 176 { 177 struct cache_queue_policy_ *queue_policy; 178 struct cache_queue_policy_item_ *queue_item; 179 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; 183 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)); 187 } 188 189 /* 190 * Initializes cache_queue_policy_ by filling the structure with the functions 191 * pointers, defined above 192 */ 193 static struct cache_queue_policy_ * 194 init_cache_queue_policy(void) 195 { 196 struct cache_queue_policy_ *retval; 197 198 TRACE_IN(init_cache_queue_policy); 199 retval = calloc(1, 200 sizeof(*retval)); 201 assert(retval != NULL); 202 203 retval->parent_data.create_item_func = cache_queue_policy_create_item; 204 retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item; 205 206 retval->parent_data.add_item_func = cache_queue_policy_add_item; 207 retval->parent_data.remove_item_func = cache_queue_policy_remove_item; 208 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; 217 218 TAILQ_INIT(&retval->head); 219 TRACE_OUT(init_cache_queue_policy); 220 return (retval); 221 } 222 223 static void 224 destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy) 225 { 226 struct cache_queue_policy_item_ *queue_item; 227 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); 234 } 235 free(queue_policy); 236 TRACE_OUT(destroy_cache_queue_policy); 237 } 238 239 /* 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. 243 */ 244 static void 245 cache_fifo_policy_update_item(struct cache_policy_ *policy, 246 struct cache_policy_item_ *item) 247 { 248 249 TRACE_IN(cache_fifo_policy_update_item); 250 /* policy and item arguments are ignored */ 251 TRACE_OUT(cache_fifo_policy_update_item); 252 } 253 254 struct cache_policy_ * 255 init_cache_fifo_policy(void) 256 { 257 struct cache_queue_policy_ *retval; 258 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; 262 263 TRACE_OUT(init_cache_fifo_policy); 264 return ((struct cache_policy_ *)retval); 265 } 266 267 void 268 destroy_cache_fifo_policy(struct cache_policy_ *policy) 269 { 270 struct cache_queue_policy_ *queue_policy; 271 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); 276 } 277 278 /* 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. 282 */ 283 static void 284 cache_lru_policy_update_item(struct cache_policy_ *policy, 285 struct cache_policy_item_ *item) 286 { 287 struct cache_queue_policy_ *queue_policy; 288 struct cache_queue_policy_item_ *queue_item; 289 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; 293 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); 297 } 298 299 struct cache_policy_ * 300 init_cache_lru_policy(void) 301 { 302 struct cache_queue_policy_ *retval; 303 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; 307 308 TRACE_OUT(init_cache_lru_policy); 309 return ((struct cache_policy_ *)retval); 310 } 311 312 void 313 destroy_cache_lru_policy(struct cache_policy_ *policy) 314 { 315 struct cache_queue_policy_ *queue_policy; 316 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); 321 } 322 323 /* 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. 332 */ 333 static struct cache_policy_item_ * 334 cache_lfu_policy_create_item(void) 335 { 336 struct cache_lfu_policy_item_ *retval; 337 338 TRACE_IN(cache_lfu_policy_create_item); 339 retval = calloc(1, 340 sizeof(*retval)); 341 assert(retval != NULL); 342 343 TRACE_OUT(cache_lfu_policy_create_item); 344 return ((struct cache_policy_item_ *)retval); 345 } 346 347 static void 348 cache_lfu_policy_destroy_item(struct cache_policy_item_ *item) 349 { 350 351 TRACE_IN(cache_lfu_policy_destroy_item); 352 assert(item != NULL); 353 free(item); 354 TRACE_OUT(cache_lfu_policy_destroy_item); 355 } 356 357 /* 358 * When placed in the LFU policy queue for the first time, the maximum 359 * frequency is assigned to the element 360 */ 361 static void 362 cache_lfu_policy_add_item(struct cache_policy_ *policy, 363 struct cache_policy_item_ *item) 364 { 365 struct cache_lfu_policy_ *lfu_policy; 366 struct cache_lfu_policy_item_ *lfu_item; 367 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; 371 372 lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1; 373 TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]), 374 lfu_item, entries); 375 TRACE_OUT(cache_lfu_policy_add_item); 376 } 377 378 /* 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. 381 */ 382 static void 383 cache_lfu_policy_update_item(struct cache_policy_ *policy, 384 struct cache_policy_item_ *item) 385 { 386 struct cache_lfu_policy_ *lfu_policy; 387 struct cache_lfu_policy_item_ *lfu_item; 388 int index; 389 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; 393 394 /* 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. 401 */ 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; 411 } else 412 index = CACHELIB_MAX_FREQUENCY - 1; 413 414 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 415 entries); 416 lfu_item->frequency = index; 417 TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries); 418 419 TRACE_OUT(cache_lfu_policy_update_item); 420 } 421 422 static void 423 cache_lfu_policy_remove_item(struct cache_policy_ *policy, 424 struct cache_policy_item_ *item) 425 { 426 struct cache_lfu_policy_ *lfu_policy; 427 struct cache_lfu_policy_item_ *lfu_item; 428 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; 432 433 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 434 entries); 435 TRACE_OUT(cache_lfu_policy_remove_item); 436 } 437 438 static struct cache_policy_item_ * 439 cache_lfu_policy_get_first_item(struct cache_policy_ *policy) 440 { 441 struct cache_lfu_policy_ *lfu_policy; 442 struct cache_lfu_policy_item_ *lfu_item; 443 int i; 444 445 TRACE_IN(cache_lfu_policy_get_first_item); 446 lfu_item = NULL; 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])); 451 break; 452 } 453 454 TRACE_OUT(cache_lfu_policy_get_first_item); 455 return ((struct cache_policy_item_ *)lfu_item); 456 } 457 458 static struct cache_policy_item_ * 459 cache_lfu_policy_get_last_item(struct cache_policy_ *policy) 460 { 461 struct cache_lfu_policy_ *lfu_policy; 462 struct cache_lfu_policy_item_ *lfu_item; 463 int i; 464 465 TRACE_IN(cache_lfu_policy_get_last_item); 466 lfu_item = NULL; 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_); 472 break; 473 } 474 475 TRACE_OUT(cache_lfu_policy_get_last_item); 476 return ((struct cache_policy_item_ *)lfu_item); 477 } 478 479 static struct cache_policy_item_ * 480 cache_lfu_policy_get_next_item(struct cache_policy_ *policy, 481 struct cache_policy_item_ *item) 482 { 483 struct cache_lfu_policy_ *lfu_policy; 484 struct cache_lfu_policy_item_ *lfu_item; 485 int i; 486 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) 491 { 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])); 496 break; 497 } 498 } 499 } 500 501 TRACE_OUT(cache_lfu_policy_get_next_item); 502 return ((struct cache_policy_item_ *)lfu_item); 503 } 504 505 static struct cache_policy_item_ * 506 cache_lfu_policy_get_prev_item(struct cache_policy_ *policy, 507 struct cache_policy_item_ *item) 508 { 509 struct cache_lfu_policy_ *lfu_policy; 510 struct cache_lfu_policy_item_ *lfu_item; 511 int i; 512 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) 518 { 519 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1; 520 i >= 0; --i) 521 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 522 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 523 cache_lfu_policy_group_); 524 break; 525 } 526 } 527 528 TRACE_OUT(cache_lfu_policy_get_prev_item); 529 return ((struct cache_policy_item_ *)lfu_item); 530 } 531 532 /* 533 * Initializes the cache_policy_ structure by filling it with appropriate 534 * functions pointers 535 */ 536 struct cache_policy_ * 537 init_cache_lfu_policy(void) 538 { 539 int i; 540 struct cache_lfu_policy_ *retval; 541 542 TRACE_IN(init_cache_lfu_policy); 543 retval = calloc(1, 544 sizeof(*retval)); 545 assert(retval != NULL); 546 547 retval->parent_data.create_item_func = cache_lfu_policy_create_item; 548 retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item; 549 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; 553 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; 562 563 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 564 TAILQ_INIT(&(retval->groups[i])); 565 566 TRACE_OUT(init_cache_lfu_policy); 567 return ((struct cache_policy_ *)retval); 568 } 569 570 void 571 destroy_cache_lfu_policy(struct cache_policy_ *policy) 572 { 573 int i; 574 struct cache_lfu_policy_ *lfu_policy; 575 struct cache_lfu_policy_item_ *lfu_item; 576 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, 583 entries); 584 cache_lfu_policy_destroy_item( 585 (struct cache_policy_item_ *)lfu_item); 586 } 587 } 588 free(policy); 589 TRACE_OUT(destroy_cache_lfu_policy); 590 } 591