cacheplcs.c revision 194087
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: head/usr.sbin/nscd/cacheplcs.c 194087 2009-06-12 23:39:05Z des $"); 30 31#include <assert.h> 32#include <string.h> 33#include "cacheplcs.h" 34#include "debug.h" 35 36static void cache_fifo_policy_update_item(struct cache_policy_ *, 37 struct cache_policy_item_ *); 38static void cache_lfu_policy_add_item(struct cache_policy_ *, 39 struct cache_policy_item_ *); 40static struct cache_policy_item_ * cache_lfu_policy_create_item(void); 41static void cache_lfu_policy_destroy_item(struct cache_policy_item_ *); 42static struct cache_policy_item_ *cache_lfu_policy_get_first_item( 43 struct cache_policy_ *); 44static struct cache_policy_item_ *cache_lfu_policy_get_last_item( 45 struct cache_policy_ *); 46static struct cache_policy_item_ *cache_lfu_policy_get_next_item( 47 struct cache_policy_ *, struct cache_policy_item_ *); 48static struct cache_policy_item_ *cache_lfu_policy_get_prev_item( 49 struct cache_policy_ *, struct cache_policy_item_ *); 50static void cache_lfu_policy_remove_item(struct cache_policy_ *, 51 struct cache_policy_item_ *); 52static void cache_lfu_policy_update_item(struct cache_policy_ *, 53 struct cache_policy_item_ *); 54static void cache_lru_policy_update_item(struct cache_policy_ *, 55 struct cache_policy_item_ *); 56static void cache_queue_policy_add_item(struct cache_policy_ *, 57 struct cache_policy_item_ *); 58static struct cache_policy_item_ * cache_queue_policy_create_item(void); 59static void cache_queue_policy_destroy_item(struct cache_policy_item_ *); 60static struct cache_policy_item_ *cache_queue_policy_get_first_item( 61 struct cache_policy_ *); 62static struct cache_policy_item_ *cache_queue_policy_get_last_item( 63 struct cache_policy_ *); 64static struct cache_policy_item_ *cache_queue_policy_get_next_item( 65 struct cache_policy_ *, struct cache_policy_item_ *); 66static struct cache_policy_item_ *cache_queue_policy_get_prev_item( 67 struct cache_policy_ *, struct cache_policy_item_ *); 68static void cache_queue_policy_remove_item(struct cache_policy_ *, 69 struct cache_policy_item_ *); 70static void destroy_cache_queue_policy(struct cache_queue_policy_ *); 71static struct cache_queue_policy_ *init_cache_queue_policy(void); 72 73/* 74 * All cache_queue_policy_XXX functions below will be used to fill 75 * the cache_queue_policy structure. They implement the most functionality of 76 * LRU and FIFO policies. LRU and FIFO policies are actually the 77 * cache_queue_policy_ with cache_update_item function changed. 78 */ 79static struct cache_policy_item_ * 80cache_queue_policy_create_item(void) 81{ 82 struct cache_queue_policy_item_ *retval; 83 84 TRACE_IN(cache_queue_policy_create_item); 85 retval = (struct cache_queue_policy_item_ *)calloc(1, 86 sizeof(struct cache_queue_policy_item_)); 87 assert(retval != NULL); 88 89 TRACE_OUT(cache_queue_policy_create_item); 90 return ((struct cache_policy_item_ *)retval); 91} 92 93static void 94cache_queue_policy_destroy_item(struct cache_policy_item_ *item) 95{ 96 97 TRACE_IN(cache_queue_policy_destroy_item); 98 assert(item != NULL); 99 free(item); 100 TRACE_OUT(cache_queue_policy_destroy_item); 101} 102 103static void 104cache_queue_policy_add_item(struct cache_policy_ *policy, 105 struct cache_policy_item_ *item) 106{ 107 struct cache_queue_policy_ *queue_policy; 108 struct cache_queue_policy_item_ *queue_item; 109 110 TRACE_IN(cache_queue_policy_add_item); 111 queue_policy = (struct cache_queue_policy_ *)policy; 112 queue_item = (struct cache_queue_policy_item_ *)item; 113 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 114 TRACE_OUT(cache_queue_policy_add_item); 115} 116 117static void 118cache_queue_policy_remove_item(struct cache_policy_ *policy, 119 struct cache_policy_item_ *item) 120{ 121 struct cache_queue_policy_ *queue_policy; 122 struct cache_queue_policy_item_ *queue_item; 123 124 TRACE_IN(cache_queue_policy_remove_item); 125 queue_policy = (struct cache_queue_policy_ *)policy; 126 queue_item = (struct cache_queue_policy_item_ *)item; 127 TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 128 TRACE_OUT(cache_queue_policy_remove_item); 129} 130 131static struct cache_policy_item_ * 132cache_queue_policy_get_first_item(struct cache_policy_ *policy) 133{ 134 struct cache_queue_policy_ *queue_policy; 135 136 TRACE_IN(cache_queue_policy_get_first_item); 137 queue_policy = (struct cache_queue_policy_ *)policy; 138 TRACE_OUT(cache_queue_policy_get_first_item); 139 return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head)); 140} 141 142static struct cache_policy_item_ * 143cache_queue_policy_get_last_item(struct cache_policy_ *policy) 144{ 145 struct cache_queue_policy_ *queue_policy; 146 147 TRACE_IN(cache_queue_policy_get_last_item); 148 queue_policy = (struct cache_queue_policy_ *)policy; 149 TRACE_OUT(cache_queue_policy_get_last_item); 150 return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head, 151 cache_queue_policy_head_)); 152} 153 154static struct cache_policy_item_ * 155cache_queue_policy_get_next_item(struct cache_policy_ *policy, 156 struct cache_policy_item_ *item) 157{ 158 struct cache_queue_policy_ *queue_policy; 159 struct cache_queue_policy_item_ *queue_item; 160 161 TRACE_IN(cache_queue_policy_get_next_item); 162 queue_policy = (struct cache_queue_policy_ *)policy; 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_ *queue_policy; 174 struct cache_queue_policy_item_ *queue_item; 175 176 TRACE_IN(cache_queue_policy_get_prev_item); 177 queue_policy = (struct cache_queue_policy_ *)policy; 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 */ 189static struct cache_queue_policy_ * 190init_cache_queue_policy(void) 191{ 192 struct cache_queue_policy_ *retval; 193 194 TRACE_IN(init_cache_queue_policy); 195 retval = (struct cache_queue_policy_ *)calloc(1, 196 sizeof(struct cache_queue_policy_)); 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 219static void 220destroy_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 */ 240static void 241cache_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 250struct cache_policy_ * 251init_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 263void 264destroy_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 */ 279static void 280cache_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 295struct cache_policy_ * 296init_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 308void 309destroy_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 */ 329static struct cache_policy_item_ * 330cache_lfu_policy_create_item(void) 331{ 332 struct cache_lfu_policy_item_ *retval; 333 334 TRACE_IN(cache_lfu_policy_create_item); 335 retval = (struct cache_lfu_policy_item_ *)calloc(1, 336 sizeof(struct cache_lfu_policy_item_)); 337 assert(retval != NULL); 338 339 TRACE_OUT(cache_lfu_policy_create_item); 340 return ((struct cache_policy_item_ *)retval); 341} 342 343static void 344cache_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 */ 357static void 358cache_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 */ 378static void 379cache_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 418static void 419cache_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 434static struct cache_policy_item_ * 435cache_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 454static struct cache_policy_item_ * 455cache_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 475static struct cache_policy_item_ * 476cache_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 501static struct cache_policy_item_ * 502cache_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 */ 532struct cache_policy_ * 533init_cache_lfu_policy(void) 534{ 535 int i; 536 struct cache_lfu_policy_ *retval; 537 538 TRACE_IN(init_cache_lfu_policy); 539 retval = (struct cache_lfu_policy_ *)calloc(1, 540 sizeof(struct cache_lfu_policy_)); 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 566void 567destroy_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