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 * $FreeBSD: src/usr.sbin/nscd/cacheplcs.c,v 1.3 2008/10/12 00:44:27 delphij Exp $ 27 */ 28 29 #include <assert.h> 30 #include <string.h> 31 #include "cacheplcs.h" 32 #include "debug.h" 33 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); 70 71 /* 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. 76 */ 77 static struct cache_policy_item_ * 78 cache_queue_policy_create_item(void) 79 { 80 struct cache_queue_policy_item_ *retval; 81 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); 86 87 TRACE_OUT(cache_queue_policy_create_item); 88 return ((struct cache_policy_item_ *)retval); 89 } 90 91 static void 92 cache_queue_policy_destroy_item(struct cache_policy_item_ *item) 93 { 94 95 TRACE_IN(cache_queue_policy_destroy_item); 96 assert(item != NULL); 97 free(item); 98 TRACE_OUT(cache_queue_policy_destroy_item); 99 } 100 101 static void 102 cache_queue_policy_add_item(struct cache_policy_ *policy, 103 struct cache_policy_item_ *item) 104 { 105 struct cache_queue_policy_ *queue_policy; 106 struct cache_queue_policy_item_ *queue_item; 107 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); 113 } 114 115 static void 116 cache_queue_policy_remove_item(struct cache_policy_ *policy, 117 struct cache_policy_item_ *item) 118 { 119 struct cache_queue_policy_ *queue_policy; 120 struct cache_queue_policy_item_ *queue_item; 121 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); 127 } 128 129 static struct cache_policy_item_ * 130 cache_queue_policy_get_first_item(struct cache_policy_ *policy) 131 { 132 struct cache_queue_policy_ *queue_policy; 133 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)); 138 } 139 140 static struct cache_policy_item_ * 141 cache_queue_policy_get_last_item(struct cache_policy_ *policy) 142 { 143 struct cache_queue_policy_ *queue_policy; 144 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_)); 150 } 151 152 static struct cache_policy_item_ * 153 cache_queue_policy_get_next_item(struct cache_policy_ *policy, 154 struct cache_policy_item_ *item) 155 { 156 struct cache_queue_policy_item_ *queue_item; 157 158 TRACE_IN(cache_queue_policy_get_next_item); 159 queue_item = (struct cache_queue_policy_item_ *)item; 160 161 TRACE_OUT(cache_queue_policy_get_next_item); 162 return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries)); 163 } 164 165 static struct cache_policy_item_ * 166 cache_queue_policy_get_prev_item(struct cache_policy_ *policy, 167 struct cache_policy_item_ *item) 168 { 169 struct cache_queue_policy_item_ *queue_item; 170 171 TRACE_IN(cache_queue_policy_get_prev_item); 172 queue_item = (struct cache_queue_policy_item_ *)item; 173 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)); 177 } 178 179 /* 180 * Initializes cache_queue_policy_ by filling the structure with the functions 181 * pointers, defined above 182 */ 183 static struct cache_queue_policy_ * 184 init_cache_queue_policy(void) 185 { 186 struct cache_queue_policy_ *retval; 187 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); 192 193 retval->parent_data.create_item_func = cache_queue_policy_create_item; 194 retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item; 195 196 retval->parent_data.add_item_func = cache_queue_policy_add_item; 197 retval->parent_data.remove_item_func = cache_queue_policy_remove_item; 198 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; 207 208 TAILQ_INIT(&retval->head); 209 TRACE_OUT(init_cache_queue_policy); 210 return (retval); 211 } 212 213 static void 214 destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy) 215 { 216 struct cache_queue_policy_item_ *queue_item; 217 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); 224 } 225 free(queue_policy); 226 TRACE_OUT(destroy_cache_queue_policy); 227 } 228 229 /* 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. 233 */ 234 static void 235 cache_fifo_policy_update_item(struct cache_policy_ *policy, 236 struct cache_policy_item_ *item) 237 { 238 239 TRACE_IN(cache_fifo_policy_update_item); 240 /* policy and item arguments are ignored */ 241 TRACE_OUT(cache_fifo_policy_update_item); 242 } 243 244 struct cache_policy_ * 245 init_cache_fifo_policy(void) 246 { 247 struct cache_queue_policy_ *retval; 248 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; 252 253 TRACE_OUT(init_cache_fifo_policy); 254 return ((struct cache_policy_ *)retval); 255 } 256 257 void 258 destroy_cache_fifo_policy(struct cache_policy_ *policy) 259 { 260 struct cache_queue_policy_ *queue_policy; 261 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); 266 } 267 268 /* 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. 272 */ 273 static void 274 cache_lru_policy_update_item(struct cache_policy_ *policy, 275 struct cache_policy_item_ *item) 276 { 277 struct cache_queue_policy_ *queue_policy; 278 struct cache_queue_policy_item_ *queue_item; 279 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; 283 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); 287 } 288 289 struct cache_policy_ * 290 init_cache_lru_policy(void) 291 { 292 struct cache_queue_policy_ *retval; 293 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; 297 298 TRACE_OUT(init_cache_lru_policy); 299 return ((struct cache_policy_ *)retval); 300 } 301 302 void 303 destroy_cache_lru_policy(struct cache_policy_ *policy) 304 { 305 struct cache_queue_policy_ *queue_policy; 306 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); 311 } 312 313 /* 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. 322 */ 323 static struct cache_policy_item_ * 324 cache_lfu_policy_create_item(void) 325 { 326 struct cache_lfu_policy_item_ *retval; 327 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); 332 333 TRACE_OUT(cache_lfu_policy_create_item); 334 return ((struct cache_policy_item_ *)retval); 335 } 336 337 static void 338 cache_lfu_policy_destroy_item(struct cache_policy_item_ *item) 339 { 340 341 TRACE_IN(cache_lfu_policy_destroy_item); 342 assert(item != NULL); 343 free(item); 344 TRACE_OUT(cache_lfu_policy_destroy_item); 345 } 346 347 /* 348 * When placed in the LFU policy queue for the first time, the maximum 349 * frequency is assigned to the element 350 */ 351 static void 352 cache_lfu_policy_add_item(struct cache_policy_ *policy, 353 struct cache_policy_item_ *item) 354 { 355 struct cache_lfu_policy_ *lfu_policy; 356 struct cache_lfu_policy_item_ *lfu_item; 357 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; 361 362 lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1; 363 TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]), 364 lfu_item, entries); 365 TRACE_OUT(cache_lfu_policy_add_item); 366 } 367 368 /* 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. 371 */ 372 static void 373 cache_lfu_policy_update_item(struct cache_policy_ *policy, 374 struct cache_policy_item_ *item) 375 { 376 struct cache_lfu_policy_ *lfu_policy; 377 struct cache_lfu_policy_item_ *lfu_item; 378 int index; 379 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; 383 384 /* 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. 391 */ 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; 401 } else 402 index = CACHELIB_MAX_FREQUENCY - 1; 403 404 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 405 entries); 406 lfu_item->frequency = index; 407 TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries); 408 409 TRACE_OUT(cache_lfu_policy_update_item); 410 } 411 412 static void 413 cache_lfu_policy_remove_item(struct cache_policy_ *policy, 414 struct cache_policy_item_ *item) 415 { 416 struct cache_lfu_policy_ *lfu_policy; 417 struct cache_lfu_policy_item_ *lfu_item; 418 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; 422 423 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 424 entries); 425 TRACE_OUT(cache_lfu_policy_remove_item); 426 } 427 428 static struct cache_policy_item_ * 429 cache_lfu_policy_get_first_item(struct cache_policy_ *policy) 430 { 431 struct cache_lfu_policy_ *lfu_policy; 432 struct cache_lfu_policy_item_ *lfu_item; 433 int i; 434 435 TRACE_IN(cache_lfu_policy_get_first_item); 436 lfu_item = NULL; 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])); 441 break; 442 } 443 444 TRACE_OUT(cache_lfu_policy_get_first_item); 445 return ((struct cache_policy_item_ *)lfu_item); 446 } 447 448 static struct cache_policy_item_ * 449 cache_lfu_policy_get_last_item(struct cache_policy_ *policy) 450 { 451 struct cache_lfu_policy_ *lfu_policy; 452 struct cache_lfu_policy_item_ *lfu_item; 453 int i; 454 455 TRACE_IN(cache_lfu_policy_get_last_item); 456 lfu_item = NULL; 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_); 462 break; 463 } 464 465 TRACE_OUT(cache_lfu_policy_get_last_item); 466 return ((struct cache_policy_item_ *)lfu_item); 467 } 468 469 static struct cache_policy_item_ * 470 cache_lfu_policy_get_next_item(struct cache_policy_ *policy, 471 struct cache_policy_item_ *item) 472 { 473 struct cache_lfu_policy_ *lfu_policy; 474 struct cache_lfu_policy_item_ *lfu_item; 475 int i; 476 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) 481 { 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])); 486 break; 487 } 488 } 489 } 490 491 TRACE_OUT(cache_lfu_policy_get_next_item); 492 return ((struct cache_policy_item_ *)lfu_item); 493 } 494 495 static struct cache_policy_item_ * 496 cache_lfu_policy_get_prev_item(struct cache_policy_ *policy, 497 struct cache_policy_item_ *item) 498 { 499 struct cache_lfu_policy_ *lfu_policy; 500 struct cache_lfu_policy_item_ *lfu_item; 501 int i; 502 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) 508 { 509 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1; 510 i >= 0; --i) 511 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 512 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 513 cache_lfu_policy_group_); 514 break; 515 } 516 } 517 518 TRACE_OUT(cache_lfu_policy_get_prev_item); 519 return ((struct cache_policy_item_ *)lfu_item); 520 } 521 522 /* 523 * Initializes the cache_policy_ structure by filling it with appropriate 524 * functions pointers 525 */ 526 struct cache_policy_ * 527 init_cache_lfu_policy(void) 528 { 529 int i; 530 struct cache_lfu_policy_ *retval; 531 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); 536 537 retval->parent_data.create_item_func = cache_lfu_policy_create_item; 538 retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item; 539 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; 543 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; 552 553 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 554 TAILQ_INIT(&(retval->groups[i])); 555 556 TRACE_OUT(init_cache_lfu_policy); 557 return ((struct cache_policy_ *)retval); 558 } 559 560 void 561 destroy_cache_lfu_policy(struct cache_policy_ *policy) 562 { 563 int i; 564 struct cache_lfu_policy_ *lfu_policy; 565 struct cache_lfu_policy_item_ *lfu_item; 566 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, 573 entries); 574 cache_lfu_policy_destroy_item( 575 (struct cache_policy_item_ *)lfu_item); 576 } 577 } 578 free(policy); 579 TRACE_OUT(destroy_cache_lfu_policy); 580 } 581