usr.sbin/nscd/cacheplcs.c

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