usr.sbin/nscd/cachelib.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 #include <sys/time.h>
  30
  31 #include <assert.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #include "cachelib.h"
  36 #include "debug.h"
  37
  38 #define INITIAL_ENTRIES_CAPACITY 32
  39 #define ENTRIES_CAPACITY_STEP 32
  40
  41 #define STRING_SIMPLE_HASH_BODY(in_var, var, a, M)              \
  42         for ((var) = 0; *(in_var) != '\0'; ++(in_var))          \
  43                 (var) = ((a)*(var) + *(in_var)) % (M)
  44
  45 #define STRING_SIMPLE_MP2_HASH_BODY(in_var, var, a, M)          \
  46         for ((var) = 0; *(in_var) != 0; ++(in_var))             \
  47                 (var) = ((a)*(var) + *(in_var)) & (M - 1)
  48
  49 static int cache_elemsize_common_continue_func(struct cache_common_entry_ *,
  50         struct cache_policy_item_ *);
  51 static int cache_lifetime_common_continue_func(struct cache_common_entry_ *,
  52         struct cache_policy_item_ *);
  53 static void clear_cache_entry(struct cache_entry_ *);
  54 static void destroy_cache_entry(struct cache_entry_ *);
  55 static void destroy_cache_mp_read_session(struct cache_mp_read_session_ *);
  56 static void destroy_cache_mp_write_session(struct cache_mp_write_session_ *);
  57 static int entries_bsearch_cmp_func(const void *, const void *);
  58 static int entries_qsort_cmp_func(const void *, const void *);
  59 static struct cache_entry_ ** find_cache_entry_p(struct cache_ *,
  60         const char *);
  61 static void flush_cache_entry(struct cache_entry_ *);
  62 static void flush_cache_policy(struct cache_common_entry_ *,
  63         struct cache_policy_ *, struct cache_policy_ *,
  64                 int (*)(struct cache_common_entry_ *,
  65                 struct cache_policy_item_ *));
  66 static int ht_items_cmp_func(const void *, const void *);
  67 static int ht_items_fixed_size_left_cmp_func(const void *, const void *);
  68 static hashtable_index_t ht_item_hash_func(const void *, size_t);
  69
  70 /*
  71  * Hashing and comparing routines, that are used with the hash tables
  72  */
  73 static int
  74 ht_items_cmp_func(const void *p1, const void *p2)
  75 {
  76         struct cache_ht_item_data_ *hp1, *hp2;
  77         size_t min_size;
  78         int result;
  79
  80         hp1 = (struct cache_ht_item_data_ *)p1;
  81         hp2 = (struct cache_ht_item_data_ *)p2;
  82
  83         assert(hp1->key != NULL);
  84         assert(hp2->key != NULL);
  85
  86         if (hp1->key_size != hp2->key_size) {
  87                 min_size = (hp1->key_size < hp2->key_size) ? hp1->key_size :
  88                         hp2->key_size;
  89                 result = memcmp(hp1->key, hp2->key, min_size);
  90
  91                 if (result == 0)
  92                         return ((hp1->key_size < hp2->key_size) ? -1 : 1);
  93                 else
  94                         return (result);
  95         } else
  96                 return (memcmp(hp1->key, hp2->key, hp1->key_size));
  97 }
  98
  99 static int
 100 ht_items_fixed_size_left_cmp_func(const void *p1, const void *p2)
 101 {
 102         struct cache_ht_item_data_ *hp1, *hp2;
 103         size_t min_size;
 104         int result;
 105
 106         hp1 = (struct cache_ht_item_data_ *)p1;
 107         hp2 = (struct cache_ht_item_data_ *)p2;
 108
 109         assert(hp1->key != NULL);
 110         assert(hp2->key != NULL);
 111
 112         if (hp1->key_size != hp2->key_size) {
 113                 min_size = (hp1->key_size < hp2->key_size) ? hp1->key_size :
 114                         hp2->key_size;
 115                 result = memcmp(hp1->key, hp2->key, min_size);
 116
 117                 if (result == 0)
 118                         if (min_size == hp1->key_size)
 119                             return (0);
 120                         else
 121                             return ((hp1->key_size < hp2->key_size) ? -1 : 1);
 122                 else
 123                         return (result);
 124         } else
 125                 return (memcmp(hp1->key, hp2->key, hp1->key_size));
 126 }
 127
 128 static hashtable_index_t
 129 ht_item_hash_func(const void *p, size_t cache_entries_size)
 130 {
 131         struct cache_ht_item_data_ *hp;
 132         size_t i;
 133
 134         hashtable_index_t retval;
 135
 136         hp = (struct cache_ht_item_data_ *)p;
 137         assert(hp->key != NULL);
 138
 139         retval = 0;
 140         for (i = 0; i < hp->key_size; ++i)
 141             retval = (127 * retval + (unsigned char)hp->key[i]) %
 142                 cache_entries_size;
 143
 144         return retval;
 145 }
 146
 147 HASHTABLE_PROTOTYPE(cache_ht_, cache_ht_item_, struct cache_ht_item_data_);
 148 HASHTABLE_GENERATE(cache_ht_, cache_ht_item_, struct cache_ht_item_data_, data,
 149         ht_item_hash_func, ht_items_cmp_func);
 150
 151 /*
 152  * Routines to sort and search the entries by name
 153  */
 154 static int
 155 entries_bsearch_cmp_func(const void *key, const void *ent)
 156 {
 157
 158         assert(key != NULL);
 159         assert(ent != NULL);
 160
 161         return (strcmp((char const *)key,
 162                 (*(struct cache_entry_ const **)ent)->name));
 163 }
 164
 165 static int
 166 entries_qsort_cmp_func(const void *e1, const void *e2)
 167 {
 168
 169         assert(e1 != NULL);
 170         assert(e2 != NULL);
 171
 172         return (strcmp((*(struct cache_entry_ const **)e1)->name,
 173                 (*(struct cache_entry_ const **)e2)->name));
 174 }
 175
 176 static struct cache_entry_ **
 177 find_cache_entry_p(struct cache_ *the_cache, const char *entry_name)
 178 {
 179
 180         return ((struct cache_entry_ **)(bsearch(entry_name, the_cache->entries,
 181                 the_cache->entries_size, sizeof(struct cache_entry_ *),
 182                 entries_bsearch_cmp_func)));
 183 }
 184
 185 static void
 186 destroy_cache_mp_write_session(struct cache_mp_write_session_ *ws)
 187 {
 188
 189         struct cache_mp_data_item_      *data_item;
 190
 191         TRACE_IN(destroy_cache_mp_write_session);
 192         assert(ws != NULL);
 193         while (!TAILQ_EMPTY(&ws->items)) {
 194                 data_item = TAILQ_FIRST(&ws->items);
 195                 TAILQ_REMOVE(&ws->items, data_item, entries);
 196                 free(data_item->value);
 197                 free(data_item);
 198         }
 199
 200         free(ws);
 201         TRACE_OUT(destroy_cache_mp_write_session);
 202 }
 203
 204 static void
 205 destroy_cache_mp_read_session(struct cache_mp_read_session_ *rs)
 206 {
 207
 208         TRACE_IN(destroy_cache_mp_read_session);
 209         assert(rs != NULL);
 210         free(rs);
 211         TRACE_OUT(destroy_cache_mp_read_session);
 212 }
 213
 214 static void
 215 destroy_cache_entry(struct cache_entry_ *entry)
 216 {
 217         struct cache_common_entry_      *common_entry;
 218         struct cache_mp_entry_          *mp_entry;
 219         struct cache_mp_read_session_   *rs;
 220         struct cache_mp_write_session_  *ws;
 221         struct cache_ht_item_ *ht_item;
 222         struct cache_ht_item_data_ *ht_item_data;
 223
 224         TRACE_IN(destroy_cache_entry);
 225         assert(entry != NULL);
 226
 227         if (entry->params->entry_type == CET_COMMON) {
 228                 common_entry = (struct cache_common_entry_ *)entry;
 229
 230                 HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
 231                         HASHTABLE_ENTRY_FOREACH(ht_item, data, ht_item_data)
 232                         {
 233                                 free(ht_item_data->key);
 234                                 free(ht_item_data->value);
 235                         }
 236                         HASHTABLE_ENTRY_CLEAR(ht_item, data);
 237                 }
 238
 239                 HASHTABLE_DESTROY(&(common_entry->items), data);
 240
 241                 /* FIFO policy is always first */
 242                 destroy_cache_fifo_policy(common_entry->policies[0]);
 243                 switch (common_entry->common_params.policy) {
 244                 case CPT_LRU:
 245                         destroy_cache_lru_policy(common_entry->policies[1]);
 246                         break;
 247                 case CPT_LFU:
 248                         destroy_cache_lfu_policy(common_entry->policies[1]);
 249                         break;
 250                 default:
 251                 break;
 252                 }
 253                 free(common_entry->policies);
 254         } else {
 255                 mp_entry = (struct cache_mp_entry_ *)entry;
 256
 257                 while (!TAILQ_EMPTY(&mp_entry->ws_head)) {
 258                         ws = TAILQ_FIRST(&mp_entry->ws_head);
 259                         TAILQ_REMOVE(&mp_entry->ws_head, ws, entries);
 260                         destroy_cache_mp_write_session(ws);
 261                 }
 262
 263                 while (!TAILQ_EMPTY(&mp_entry->rs_head)) {
 264                         rs = TAILQ_FIRST(&mp_entry->rs_head);
 265                         TAILQ_REMOVE(&mp_entry->rs_head, rs, entries);
 266                         destroy_cache_mp_read_session(rs);
 267                 }
 268
 269                 if (mp_entry->completed_write_session != NULL)
 270                         destroy_cache_mp_write_session(
 271                                 mp_entry->completed_write_session);
 272
 273                 if (mp_entry->pending_write_session != NULL)
 274                         destroy_cache_mp_write_session(
 275                                 mp_entry->pending_write_session);
 276         }
 277
 278         free(entry->name);
 279         free(entry);
 280         TRACE_OUT(destroy_cache_entry);
 281 }
 282
 283 static void
 284 clear_cache_entry(struct cache_entry_ *entry)
 285 {
 286         struct cache_mp_entry_          *mp_entry;
 287         struct cache_common_entry_      *common_entry;
 288         struct cache_ht_item_ *ht_item;
 289         struct cache_ht_item_data_ *ht_item_data;
 290         struct cache_policy_ *policy;
 291         struct cache_policy_item_ *item, *next_item;
 292         size_t entry_size;
 293         unsigned int i;
 294
 295         if (entry->params->entry_type == CET_COMMON) {
 296                 common_entry = (struct cache_common_entry_ *)entry;
 297
 298                 entry_size = 0;
 299                 HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
 300                         HASHTABLE_ENTRY_FOREACH(ht_item, data, ht_item_data)
 301                         {
 302                                 free(ht_item_data->key);
 303                                 free(ht_item_data->value);
 304                         }
 305                         entry_size += HASHTABLE_ENTRY_SIZE(ht_item, data);
 306                         HASHTABLE_ENTRY_CLEAR(ht_item, data);
 307                 }
 308
 309                 common_entry->items_size -= entry_size;
 310                 for (i = 0; i < common_entry->policies_size; ++i) {
 311                         policy = common_entry->policies[i];
 312
 313                         next_item = NULL;
 314                         item = policy->get_first_item_func(policy);
 315                         while (item != NULL) {
 316                                 next_item = policy->get_next_item_func(policy,
 317                                         item);
 318                                 policy->remove_item_func(policy, item);
 319                                 policy->destroy_item_func(item);
 320                                 item = next_item;
 321                         }
 322                 }
 323         } else {
 324                 mp_entry = (struct cache_mp_entry_ *)entry;
 325
 326                 if (mp_entry->rs_size == 0) {
 327                         if (mp_entry->completed_write_session != NULL) {
 328                                 destroy_cache_mp_write_session(
 329                                         mp_entry->completed_write_session);
 330                                 mp_entry->completed_write_session = NULL;
 331                         }
 332
 333                         memset(&mp_entry->creation_time, 0,
 334                                 sizeof(struct timeval));
 335                         memset(&mp_entry->last_request_time, 0,
 336                                 sizeof(struct timeval));
 337                 }
 338         }
 339 }
 340
 341 /*
 342  * When passed to the flush_cache_policy, ensures that all old elements are
 343  * deleted.
 344  */
 345 static int
 346 cache_lifetime_common_continue_func(struct cache_common_entry_ *entry,
 347         struct cache_policy_item_ *item)
 348 {
 349
 350         return ((item->last_request_time.tv_sec - item->creation_time.tv_sec >
 351                 entry->common_params.max_lifetime.tv_sec) ? 1: 0);
 352 }
 353
 354 /*
 355  * When passed to the flush_cache_policy, ensures that all elements, that
 356  * exceed the size limit, are deleted.
 357  */
 358 static int
 359 cache_elemsize_common_continue_func(struct cache_common_entry_ *entry,
 360         struct cache_policy_item_ *item)
 361 {
 362
 363         return ((entry->items_size > entry->common_params.satisf_elemsize) ? 1
 364                 : 0);
 365 }
 366
 367 /*
 368  * Removes the elements from the cache entry, while the continue_func returns 1.
 369  */
 370 static void
 371 flush_cache_policy(struct cache_common_entry_ *entry,
 372         struct cache_policy_ *policy,
 373         struct cache_policy_ *connected_policy,
 374         int (*continue_func)(struct cache_common_entry_ *,
 375                 struct cache_policy_item_ *))
 376 {
 377         struct cache_policy_item_ *item, *next_item, *connected_item;
 378         struct cache_ht_item_ *ht_item;
 379         struct cache_ht_item_data_ *ht_item_data, ht_key;
 380         hashtable_index_t hash;
 381
 382         assert(policy != NULL);
 383
 384         next_item = NULL;
 385         item = policy->get_first_item_func(policy);
 386         while ((item != NULL) && (continue_func(entry, item) == 1)) {
 387                 next_item = policy->get_next_item_func(policy, item);
 388
 389                 connected_item = item->connected_item;
 390                 policy->remove_item_func(policy, item);
 391
 392                 memset(&ht_key, 0, sizeof(struct cache_ht_item_data_));
 393                 ht_key.key = item->key;
 394                 ht_key.key_size = item->key_size;
 395
 396                 hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &entry->items,
 397                         &ht_key);
 398                 assert(hash < HASHTABLE_ENTRIES_COUNT(&entry->items));
 399
 400                 ht_item = HASHTABLE_GET_ENTRY(&(entry->items), hash);
 401                 ht_item_data = HASHTABLE_ENTRY_FIND(cache_ht_, ht_item,
 402                         &ht_key);
 403                 assert(ht_item_data != NULL);
 404                 free(ht_item_data->key);
 405                 free(ht_item_data->value);
 406                 HASHTABLE_ENTRY_REMOVE(cache_ht_, ht_item, ht_item_data);
 407                 --entry->items_size;
 408
 409                 policy->destroy_item_func(item);
 410
 411                 if (connected_item != NULL) {
 412                         connected_policy->remove_item_func(connected_policy,
 413                                 connected_item);
 414                         connected_policy->destroy_item_func(connected_item);
 415                 }
 416
 417                 item = next_item;
 418         }
 419 }
 420
 421 static void
 422 flush_cache_entry(struct cache_entry_ *entry)
 423 {
 424         struct cache_mp_entry_          *mp_entry;
 425         struct cache_common_entry_      *common_entry;
 426         struct cache_policy_ *policy, *connected_policy;
 427
 428         connected_policy = NULL;
 429         if (entry->params->entry_type == CET_COMMON) {
 430                 common_entry = (struct cache_common_entry_ *)entry;
 431                 if ((common_entry->common_params.max_lifetime.tv_sec != 0) ||
 432                     (common_entry->common_params.max_lifetime.tv_usec != 0)) {
 433
 434                         policy = common_entry->policies[0];
 435                         if (common_entry->policies_size > 1)
 436                                 connected_policy = common_entry->policies[1];
 437
 438                         flush_cache_policy(common_entry, policy,
 439                                 connected_policy,
 440                                 cache_lifetime_common_continue_func);
 441                 }
 442
 443
 444                 if ((common_entry->common_params.max_elemsize != 0) &&
 445                         common_entry->items_size >
 446                         common_entry->common_params.max_elemsize) {
 447
 448                         if (common_entry->policies_size > 1) {
 449                                 policy = common_entry->policies[1];
 450                                 connected_policy = common_entry->policies[0];
 451                         } else {
 452                                 policy = common_entry->policies[0];
 453                                 connected_policy = NULL;
 454                         }
 455
 456                         flush_cache_policy(common_entry, policy,
 457                                 connected_policy,
 458                                 cache_elemsize_common_continue_func);
 459                 }
 460         } else {
 461                 mp_entry = (struct cache_mp_entry_ *)entry;
 462
 463                 if ((mp_entry->mp_params.max_lifetime.tv_sec != 0)
 464                         || (mp_entry->mp_params.max_lifetime.tv_usec != 0)) {
 465
 466                         if (mp_entry->last_request_time.tv_sec -
 467                                 mp_entry->last_request_time.tv_sec >
 468                                 mp_entry->mp_params.max_lifetime.tv_sec)
 469                                 clear_cache_entry(entry);
 470                 }
 471         }
 472 }
 473
 474 struct cache_ *
 475 init_cache(struct cache_params const *params)
 476 {
 477         struct cache_ *retval;
 478
 479         TRACE_IN(init_cache);
 480         assert(params != NULL);
 481
 482         retval = calloc(1, sizeof(*retval));
 483         assert(retval != NULL);
 484
 485         assert(params != NULL);
 486         memcpy(&retval->params, params, sizeof(struct cache_params));
 487
 488         retval->entries = calloc(INITIAL_ENTRIES_CAPACITY,
 489                 sizeof(*retval->entries));
 490         assert(retval->entries != NULL);
 491
 492         retval->entries_capacity = INITIAL_ENTRIES_CAPACITY;
 493         retval->entries_size = 0;
 494
 495         TRACE_OUT(init_cache);
 496         return (retval);
 497 }
 498
 499 void
 500 destroy_cache(struct cache_ *the_cache)
 501 {
 502
 503         TRACE_IN(destroy_cache);
 504         assert(the_cache != NULL);
 505
 506         if (the_cache->entries != NULL) {
 507                 size_t i;
 508                 for (i = 0; i < the_cache->entries_size; ++i)
 509                         destroy_cache_entry(the_cache->entries[i]);
 510
 511                 free(the_cache->entries);
 512         }
 513
 514         free(the_cache);
 515         TRACE_OUT(destroy_cache);
 516 }
 517
 518 int
 519 register_cache_entry(struct cache_ *the_cache,
 520         struct cache_entry_params const *params)
 521 {
 522         int policies_size;
 523         size_t entry_name_size;
 524         struct cache_common_entry_      *new_common_entry;
 525         struct cache_mp_entry_          *new_mp_entry;
 526
 527         TRACE_IN(register_cache_entry);
 528         assert(the_cache != NULL);
 529
 530         if (find_cache_entry(the_cache, params->entry_name) != NULL) {
 531                 TRACE_OUT(register_cache_entry);
 532                 return (-1);
 533         }
 534
 535         if (the_cache->entries_size == the_cache->entries_capacity) {
 536                 struct cache_entry_ **new_entries;
 537                 size_t  new_capacity;
 538
 539                 new_capacity = the_cache->entries_capacity +
 540                         ENTRIES_CAPACITY_STEP;
 541                 new_entries = calloc(new_capacity,
 542                         sizeof(*new_entries));
 543                 assert(new_entries != NULL);
 544
 545                 memcpy(new_entries, the_cache->entries,
 546                         sizeof(struct cache_entry_ *)
 547                         * the_cache->entries_size);
 548
 549                 free(the_cache->entries);
 550                 the_cache->entries = new_entries;
 551         }
 552
 553         entry_name_size = strlen(params->entry_name) + 1;
 554         switch (params->entry_type)
 555         {
 556         case CET_COMMON:
 557                 new_common_entry = calloc(1,
 558                         sizeof(*new_common_entry));
 559                 assert(new_common_entry != NULL);
 560
 561                 memcpy(&new_common_entry->common_params, params,
 562                         sizeof(struct common_cache_entry_params));
 563                 new_common_entry->params =
 564                   (struct cache_entry_params *)&new_common_entry->common_params;
 565
 566                 new_common_entry->common_params.cep.entry_name = calloc(1,
 567                         entry_name_size);
 568                 assert(new_common_entry->common_params.cep.entry_name != NULL);
 569                 strlcpy(new_common_entry->common_params.cep.entry_name,
 570                         params->entry_name, entry_name_size);
 571                 new_common_entry->name =
 572                         new_common_entry->common_params.cep.entry_name;
 573
 574                 HASHTABLE_INIT(&(new_common_entry->items),
 575                         struct cache_ht_item_data_, data,
 576                         new_common_entry->common_params.cache_entries_size);
 577
 578                 if (new_common_entry->common_params.policy == CPT_FIFO)
 579                         policies_size = 1;
 580                 else
 581                         policies_size = 2;
 582
 583                 new_common_entry->policies = calloc(policies_size,
 584                         sizeof(*new_common_entry->policies));
 585                 assert(new_common_entry->policies != NULL);
 586
 587                 new_common_entry->policies_size = policies_size;
 588                 new_common_entry->policies[0] = init_cache_fifo_policy();
 589
 590                 if (policies_size > 1) {
 591                         switch (new_common_entry->common_params.policy) {
 592                         case CPT_LRU:
 593                                 new_common_entry->policies[1] =
 594                                         init_cache_lru_policy();
 595                         break;
 596                         case CPT_LFU:
 597                                 new_common_entry->policies[1] =
 598                                         init_cache_lfu_policy();
 599                         break;
 600                         default:
 601                         break;
 602                         }
 603                 }
 604
 605                 new_common_entry->get_time_func =
 606                         the_cache->params.get_time_func;
 607                 the_cache->entries[the_cache->entries_size++] =
 608                         (struct cache_entry_ *)new_common_entry;
 609                 break;
 610         case CET_MULTIPART:
 611                 new_mp_entry = calloc(1,
 612                         sizeof(*new_mp_entry));
 613                 assert(new_mp_entry != NULL);
 614
 615                 memcpy(&new_mp_entry->mp_params, params,
 616                         sizeof(struct mp_cache_entry_params));
 617                 new_mp_entry->params =
 618                         (struct cache_entry_params *)&new_mp_entry->mp_params;
 619
 620                 new_mp_entry->mp_params.cep.entry_name = calloc(1,
 621                         entry_name_size);
 622                 assert(new_mp_entry->mp_params.cep.entry_name != NULL);
 623                 strlcpy(new_mp_entry->mp_params.cep.entry_name, params->entry_name,
 624                         entry_name_size);
 625                 new_mp_entry->name = new_mp_entry->mp_params.cep.entry_name;
 626
 627                 TAILQ_INIT(&new_mp_entry->ws_head);
 628                 TAILQ_INIT(&new_mp_entry->rs_head);
 629
 630                 new_mp_entry->get_time_func = the_cache->params.get_time_func;
 631                 the_cache->entries[the_cache->entries_size++] =
 632                         (struct cache_entry_ *)new_mp_entry;
 633                 break;
 634         }
 635
 636
 637         qsort(the_cache->entries, the_cache->entries_size,
 638                 sizeof(struct cache_entry_ *), entries_qsort_cmp_func);
 639
 640         TRACE_OUT(register_cache_entry);
 641         return (0);
 642 }
 643
 644 int
 645 unregister_cache_entry(struct cache_ *the_cache, const char *entry_name)
 646 {
 647         struct cache_entry_ **del_ent;
 648
 649         TRACE_IN(unregister_cache_entry);
 650         assert(the_cache != NULL);
 651
 652         del_ent = find_cache_entry_p(the_cache, entry_name);
 653         if (del_ent != NULL) {
 654                 destroy_cache_entry(*del_ent);
 655                 --the_cache->entries_size;
 656
 657                 memmove(del_ent, del_ent + 1,
 658                         (&(the_cache->entries[--the_cache->entries_size]) -
 659                         del_ent) * sizeof(struct cache_entry_ *));
 660
 661                 TRACE_OUT(unregister_cache_entry);
 662                 return (0);
 663         } else {
 664                 TRACE_OUT(unregister_cache_entry);
 665                 return (-1);
 666         }
 667 }
 668
 669 struct cache_entry_ *
 670 find_cache_entry(struct cache_ *the_cache, const char *entry_name)
 671 {
 672         struct cache_entry_ **result;
 673
 674         TRACE_IN(find_cache_entry);
 675         result = find_cache_entry_p(the_cache, entry_name);
 676
 677         if (result == NULL) {
 678                 TRACE_OUT(find_cache_entry);
 679                 return (NULL);
 680         } else {
 681                 TRACE_OUT(find_cache_entry);
 682                 return (*result);
 683         }
 684 }
 685
 686 /*
 687  * Tries to read the element with the specified key from the cache. If the
 688  * value_size is too small, it will be filled with the proper number, and
 689  * the user will need to call cache_read again with the value buffer, that
 690  * is large enough.
 691  * Function returns 0 on success, -1 on error, and -2 if the value_size is too
 692  * small.
 693  */
 694 int
 695 cache_read(struct cache_entry_ *entry, const char *key, size_t key_size,
 696         char *value, size_t *value_size)
 697 {
 698         struct cache_common_entry_      *common_entry;
 699         struct cache_ht_item_data_      item_data, *find_res;
 700         struct cache_ht_item_           *item;
 701         hashtable_index_t       hash;
 702         struct cache_policy_item_ *connected_item;
 703
 704         TRACE_IN(cache_read);
 705         assert(entry != NULL);
 706         assert(key != NULL);
 707         assert(value_size != NULL);
 708         assert(entry->params->entry_type == CET_COMMON);
 709
 710         common_entry = (struct cache_common_entry_ *)entry;
 711
 712         memset(&item_data, 0, sizeof(struct cache_ht_item_data_));
 713         /* can't avoid the cast here */
 714         item_data.key = (char *)key;
 715         item_data.key_size = key_size;
 716
 717         hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &common_entry->items,
 718                 &item_data);
 719         assert(hash < HASHTABLE_ENTRIES_COUNT(&common_entry->items));
 720
 721         item = HASHTABLE_GET_ENTRY(&(common_entry->items), hash);
 722         find_res = HASHTABLE_ENTRY_FIND(cache_ht_, item, &item_data);
 723         if (find_res == NULL) {
 724                 TRACE_OUT(cache_read);
 725                 return (-1);
 726         }
 727         /* pretend that entry was not found if confidence is below threshold*/
 728         if (find_res->confidence <
 729             common_entry->common_params.confidence_threshold) {
 730                 TRACE_OUT(cache_read);
 731                 return (-1);
 732         }
 733
 734         if ((common_entry->common_params.max_lifetime.tv_sec != 0) ||
 735                 (common_entry->common_params.max_lifetime.tv_usec != 0)) {
 736
 737                 if (find_res->fifo_policy_item->last_request_time.tv_sec -
 738                         find_res->fifo_policy_item->creation_time.tv_sec >
 739                         common_entry->common_params.max_lifetime.tv_sec) {
 740
 741                         free(find_res->key);
 742                         free(find_res->value);
 743
 744                         connected_item =
 745                             find_res->fifo_policy_item->connected_item;
 746                         if (connected_item != NULL) {
 747                                 common_entry->policies[1]->remove_item_func(
 748                                         common_entry->policies[1],
 749                                         connected_item);
 750                                 common_entry->policies[1]->destroy_item_func(
 751                                         connected_item);
 752                         }
 753
 754                         common_entry->policies[0]->remove_item_func(
 755                                 common_entry->policies[0],
 756                                         find_res->fifo_policy_item);
 757                         common_entry->policies[0]->destroy_item_func(
 758                                 find_res->fifo_policy_item);
 759
 760                         HASHTABLE_ENTRY_REMOVE(cache_ht_, item, find_res);
 761                         --common_entry->items_size;
 762                 }
 763         }
 764
 765         if ((*value_size < find_res->value_size) || (value == NULL)) {
 766                 *value_size = find_res->value_size;
 767                 TRACE_OUT(cache_read);
 768                 return (-2);
 769         }
 770
 771         *value_size = find_res->value_size;
 772         memcpy(value, find_res->value, find_res->value_size);
 773
 774         ++find_res->fifo_policy_item->request_count;
 775         common_entry->get_time_func(
 776                 &find_res->fifo_policy_item->last_request_time);
 777         common_entry->policies[0]->update_item_func(common_entry->policies[0],
 778                 find_res->fifo_policy_item);
 779
 780         if (find_res->fifo_policy_item->connected_item != NULL) {
 781                 connected_item = find_res->fifo_policy_item->connected_item;
 782                 memcpy(&connected_item->last_request_time,
 783                         &find_res->fifo_policy_item->last_request_time,
 784                         sizeof(struct timeval));
 785                 connected_item->request_count =
 786                         find_res->fifo_policy_item->request_count;
 787
 788                 common_entry->policies[1]->update_item_func(
 789                         common_entry->policies[1], connected_item);
 790         }
 791
 792         TRACE_OUT(cache_read);
 793         return (0);
 794 }
 795
 796 /*
 797  * Writes the value with the specified key into the cache entry.
 798  * Functions returns 0 on success, and -1 on error.
 799  */
 800 int
 801 cache_write(struct cache_entry_ *entry, const char *key, size_t key_size,
 802         char const *value, size_t value_size)
 803 {
 804         struct cache_common_entry_      *common_entry;
 805         struct cache_ht_item_data_      item_data, *find_res;
 806         struct cache_ht_item_           *item;
 807         hashtable_index_t       hash;
 808
 809         struct cache_policy_            *policy, *connected_policy;
 810         struct cache_policy_item_       *policy_item;
 811         struct cache_policy_item_       *connected_policy_item;
 812
 813         TRACE_IN(cache_write);
 814         assert(entry != NULL);
 815         assert(key != NULL);
 816         assert(value != NULL);
 817         assert(entry->params->entry_type == CET_COMMON);
 818
 819         common_entry = (struct cache_common_entry_ *)entry;
 820
 821         memset(&item_data, 0, sizeof(struct cache_ht_item_data_));
 822         /* can't avoid the cast here */
 823         item_data.key = (char *)key;
 824         item_data.key_size = key_size;
 825
 826         hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &common_entry->items,
 827                 &item_data);
 828         assert(hash < HASHTABLE_ENTRIES_COUNT(&common_entry->items));
 829
 830         item = HASHTABLE_GET_ENTRY(&(common_entry->items), hash);
 831         find_res = HASHTABLE_ENTRY_FIND(cache_ht_, item, &item_data);
 832         if (find_res != NULL) {
 833                 if (find_res->confidence < common_entry->common_params.confidence_threshold) {
 834                         /* duplicate entry is no error, if confidence is low */
 835                         if ((find_res->value_size == value_size) &&
 836                             (memcmp(find_res->value, value, value_size) == 0)) {
 837                                 /* increase confidence on exact match (key and values) */
 838                                 find_res->confidence++;
 839                         } else {
 840                                 /* create new entry with low confidence, if value changed */
 841                                 free(item_data.value);
 842                                 item_data.value = malloc(value_size);
 843                                 assert(item_data.value != NULL);
 844                                 memcpy(item_data.value, value, value_size);
 845                                 item_data.value_size = value_size;
 846                                 find_res->confidence = 1;
 847                         }
 848                         TRACE_OUT(cache_write);
 849                         return (0);
 850                 }
 851                 TRACE_OUT(cache_write);
 852                 return (-1);
 853         }
 854
 855         item_data.key = malloc(key_size);
 856         memcpy(item_data.key, key, key_size);
 857
 858         item_data.value = malloc(value_size);
 859         assert(item_data.value != NULL);
 860
 861         memcpy(item_data.value, value, value_size);
 862         item_data.value_size = value_size;
 863
 864         item_data.confidence = 1;
 865
 866         policy_item = common_entry->policies[0]->create_item_func();
 867         policy_item->key = item_data.key;
 868         policy_item->key_size = item_data.key_size;
 869         common_entry->get_time_func(&policy_item->creation_time);
 870
 871         if (common_entry->policies_size > 1) {
 872                 connected_policy_item =
 873                         common_entry->policies[1]->create_item_func();
 874                 memcpy(&connected_policy_item->creation_time,
 875                         &policy_item->creation_time,
 876                         sizeof(struct timeval));
 877                 connected_policy_item->key = policy_item->key;
 878                 connected_policy_item->key_size = policy_item->key_size;
 879
 880                 connected_policy_item->connected_item = policy_item;
 881                 policy_item->connected_item = connected_policy_item;
 882         }
 883
 884         item_data.fifo_policy_item = policy_item;
 885
 886         common_entry->policies[0]->add_item_func(common_entry->policies[0],
 887                 policy_item);
 888         if (common_entry->policies_size > 1)
 889                 common_entry->policies[1]->add_item_func(
 890                         common_entry->policies[1], connected_policy_item);
 891
 892         HASHTABLE_ENTRY_STORE(cache_ht_, item, &item_data);
 893         ++common_entry->items_size;
 894
 895         if ((common_entry->common_params.max_elemsize != 0) &&
 896                 (common_entry->items_size >
 897                 common_entry->common_params.max_elemsize)) {
 898                 if (common_entry->policies_size > 1) {
 899                         policy = common_entry->policies[1];
 900                         connected_policy = common_entry->policies[0];
 901                 } else {
 902                         policy = common_entry->policies[0];
 903                         connected_policy = NULL;
 904                 }
 905
 906                 flush_cache_policy(common_entry, policy, connected_policy,
 907                         cache_elemsize_common_continue_func);
 908         }
 909
 910         TRACE_OUT(cache_write);
 911         return (0);
 912 }
 913
 914 /*
 915  * Initializes the write session for the specified multipart entry. This
 916  * session then should be filled with data either committed or abandoned by
 917  * using close_cache_mp_write_session or abandon_cache_mp_write_session
 918  * respectively.
 919  * Returns NULL on errors (when there are too many opened write sessions for
 920  * the entry).
 921  */
 922 struct cache_mp_write_session_ *
 923 open_cache_mp_write_session(struct cache_entry_ *entry)
 924 {
 925         struct cache_mp_entry_  *mp_entry;
 926         struct cache_mp_write_session_  *retval;
 927
 928         TRACE_IN(open_cache_mp_write_session);
 929         assert(entry != NULL);
 930         assert(entry->params->entry_type == CET_MULTIPART);
 931         mp_entry = (struct cache_mp_entry_ *)entry;
 932
 933         if ((mp_entry->mp_params.max_sessions > 0) &&
 934                 (mp_entry->ws_size == mp_entry->mp_params.max_sessions)) {
 935                 TRACE_OUT(open_cache_mp_write_session);
 936                 return (NULL);
 937         }
 938
 939         retval = calloc(1,
 940                 sizeof(*retval));
 941         assert(retval != NULL);
 942
 943         TAILQ_INIT(&retval->items);
 944         retval->parent_entry = mp_entry;
 945
 946         TAILQ_INSERT_HEAD(&mp_entry->ws_head, retval, entries);
 947         ++mp_entry->ws_size;
 948
 949         TRACE_OUT(open_cache_mp_write_session);
 950         return (retval);
 951 }
 952
 953 /*
 954  * Writes data to the specified session. Return 0 on success and -1 on errors
 955  * (when write session size limit is exceeded).
 956  */
 957 int
 958 cache_mp_write(struct cache_mp_write_session_ *ws, char *data,
 959         size_t data_size)
 960 {
 961         struct cache_mp_data_item_      *new_item;
 962
 963         TRACE_IN(cache_mp_write);
 964         assert(ws != NULL);
 965         assert(ws->parent_entry != NULL);
 966         assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
 967
 968         if ((ws->parent_entry->mp_params.max_elemsize > 0) &&
 969                 (ws->parent_entry->mp_params.max_elemsize == ws->items_size)) {
 970                 TRACE_OUT(cache_mp_write);
 971                 return (-1);
 972         }
 973
 974         new_item = calloc(1,
 975                 sizeof(*new_item));
 976         assert(new_item != NULL);
 977
 978         new_item->value = malloc(data_size);
 979         assert(new_item->value != NULL);
 980         memcpy(new_item->value, data, data_size);
 981         new_item->value_size = data_size;
 982
 983         TAILQ_INSERT_TAIL(&ws->items, new_item, entries);
 984         ++ws->items_size;
 985
 986         TRACE_OUT(cache_mp_write);
 987         return (0);
 988 }
 989
 990 /*
 991  * Abandons the write session and frees all the connected resources.
 992  */
 993 void
 994 abandon_cache_mp_write_session(struct cache_mp_write_session_ *ws)
 995 {
 996
 997         TRACE_IN(abandon_cache_mp_write_session);
 998         assert(ws != NULL);
 999         assert(ws->parent_entry != NULL);
1000         assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
1001
1002         TAILQ_REMOVE(&ws->parent_entry->ws_head, ws, entries);
1003         --ws->parent_entry->ws_size;
1004
1005         destroy_cache_mp_write_session(ws);
1006         TRACE_OUT(abandon_cache_mp_write_session);
1007 }
1008
1009 /*
1010  * Commits the session to the entry, for which it was created.
1011  */
1012 void
1013 close_cache_mp_write_session(struct cache_mp_write_session_ *ws)
1014 {
1015
1016         TRACE_IN(close_cache_mp_write_session);
1017         assert(ws != NULL);
1018         assert(ws->parent_entry != NULL);
1019         assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
1020
1021         TAILQ_REMOVE(&ws->parent_entry->ws_head, ws, entries);
1022         --ws->parent_entry->ws_size;
1023
1024         if (ws->parent_entry->completed_write_session == NULL) {
1025                 /*
1026                  * If there is no completed session yet, this will be the one
1027                  */
1028                 ws->parent_entry->get_time_func(
1029                         &ws->parent_entry->creation_time);
1030                 ws->parent_entry->completed_write_session = ws;
1031         } else {
1032                 /*
1033                  * If there is a completed session, then we'll save our session
1034                  * as a pending session. If there is already a pending session,
1035                  * it would be destroyed.
1036                  */
1037                 if (ws->parent_entry->pending_write_session != NULL)
1038                         destroy_cache_mp_write_session(
1039                                 ws->parent_entry->pending_write_session);
1040
1041                 ws->parent_entry->pending_write_session = ws;
1042         }
1043         TRACE_OUT(close_cache_mp_write_session);
1044 }
1045
1046 /*
1047  * Opens read session for the specified entry. Returns NULL on errors (when
1048  * there are no data in the entry, or the data are obsolete).
1049  */
1050 struct cache_mp_read_session_ *
1051 open_cache_mp_read_session(struct cache_entry_ *entry)
1052 {
1053         struct cache_mp_entry_                  *mp_entry;
1054         struct cache_mp_read_session_   *retval;
1055
1056         TRACE_IN(open_cache_mp_read_session);
1057         assert(entry != NULL);
1058         assert(entry->params->entry_type == CET_MULTIPART);
1059         mp_entry = (struct cache_mp_entry_ *)entry;
1060
1061         if (mp_entry->completed_write_session == NULL) {
1062                 TRACE_OUT(open_cache_mp_read_session);
1063                 return (NULL);
1064         }
1065
1066         if ((mp_entry->mp_params.max_lifetime.tv_sec != 0)
1067                 || (mp_entry->mp_params.max_lifetime.tv_usec != 0)) {
1068                 if (mp_entry->last_request_time.tv_sec -
1069                         mp_entry->last_request_time.tv_sec >
1070                         mp_entry->mp_params.max_lifetime.tv_sec) {
1071                         flush_cache_entry(entry);
1072                         TRACE_OUT(open_cache_mp_read_session);
1073                         return (NULL);
1074                 }
1075         }
1076
1077         retval = calloc(1,
1078                 sizeof(*retval));
1079         assert(retval != NULL);
1080
1081         retval->parent_entry = mp_entry;
1082         retval->current_item = TAILQ_FIRST(
1083                 &mp_entry->completed_write_session->items);
1084
1085         TAILQ_INSERT_HEAD(&mp_entry->rs_head, retval, entries);
1086         ++mp_entry->rs_size;
1087
1088         mp_entry->get_time_func(&mp_entry->last_request_time);
1089         TRACE_OUT(open_cache_mp_read_session);
1090         return (retval);
1091 }
1092
1093 /*
1094  * Reads the data from the read session - step by step.
1095  * Returns 0 on success, -1 on error (when there are no more data), and -2 if
1096  * the data_size is too small.  In the last case, data_size would be filled
1097  * the proper value.
1098  */
1099 int
1100 cache_mp_read(struct cache_mp_read_session_ *rs, char *data, size_t *data_size)
1101 {
1102
1103         TRACE_IN(cache_mp_read);
1104         assert(rs != NULL);
1105
1106         if (rs->current_item == NULL) {
1107                 TRACE_OUT(cache_mp_read);
1108                 return (-1);
1109         }
1110
1111         if (rs->current_item->value_size > *data_size) {
1112                 *data_size = rs->current_item->value_size;
1113                 if (data == NULL) {
1114                         TRACE_OUT(cache_mp_read);
1115                         return (0);
1116                 }
1117
1118                 TRACE_OUT(cache_mp_read);
1119                 return (-2);
1120         }
1121
1122         *data_size = rs->current_item->value_size;
1123         memcpy(data, rs->current_item->value, rs->current_item->value_size);
1124         rs->current_item = TAILQ_NEXT(rs->current_item, entries);
1125
1126         TRACE_OUT(cache_mp_read);
1127         return (0);
1128 }
1129
1130 /*
1131  * Closes the read session. If there are no more read sessions and there is
1132  * a pending write session, it will be committed and old
1133  * completed_write_session will be destroyed.
1134  */
1135 void
1136 close_cache_mp_read_session(struct cache_mp_read_session_ *rs)
1137 {
1138
1139         TRACE_IN(close_cache_mp_read_session);
1140         assert(rs != NULL);
1141         assert(rs->parent_entry != NULL);
1142
1143         TAILQ_REMOVE(&rs->parent_entry->rs_head, rs, entries);
1144         --rs->parent_entry->rs_size;
1145
1146         if ((rs->parent_entry->rs_size == 0) &&
1147                 (rs->parent_entry->pending_write_session != NULL)) {
1148                 destroy_cache_mp_write_session(
1149                         rs->parent_entry->completed_write_session);
1150                 rs->parent_entry->completed_write_session =
1151                         rs->parent_entry->pending_write_session;
1152                 rs->parent_entry->pending_write_session = NULL;
1153         }
1154
1155         destroy_cache_mp_read_session(rs);
1156         TRACE_OUT(close_cache_mp_read_session);
1157 }
1158
1159 int
1160 transform_cache_entry(struct cache_entry_ *entry,
1161         enum cache_transformation_t transformation)
1162 {
1163
1164         TRACE_IN(transform_cache_entry);
1165         switch (transformation) {
1166         case CTT_CLEAR:
1167                 clear_cache_entry(entry);
1168                 TRACE_OUT(transform_cache_entry);
1169                 return (0);
1170         case CTT_FLUSH:
1171                 flush_cache_entry(entry);
1172                 TRACE_OUT(transform_cache_entry);
1173                 return (0);
1174         default:
1175                 TRACE_OUT(transform_cache_entry);
1176                 return (-1);
1177         }
1178 }
1179
1180 int
1181 transform_cache_entry_part(struct cache_entry_ *entry,
1182         enum cache_transformation_t transformation, const char *key_part,
1183         size_t key_part_size, enum part_position_t part_position)
1184 {
1185         struct cache_common_entry_ *common_entry;
1186         struct cache_ht_item_ *ht_item;
1187         struct cache_ht_item_data_ *ht_item_data, ht_key;
1188
1189         struct cache_policy_item_ *item, *connected_item;
1190
1191         TRACE_IN(transform_cache_entry_part);
1192         if (entry->params->entry_type != CET_COMMON) {
1193                 TRACE_OUT(transform_cache_entry_part);
1194                 return (-1);
1195         }
1196
1197         if (transformation != CTT_CLEAR) {
1198                 TRACE_OUT(transform_cache_entry_part);
1199                 return (-1);
1200         }
1201
1202         memset(&ht_key, 0, sizeof(struct cache_ht_item_data_));
1203         ht_key.key = (char *)key_part;  /* can't avoid casting here */
1204         ht_key.key_size = key_part_size;
1205
1206         common_entry = (struct cache_common_entry_ *)entry;
1207         HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
1208                 do {
1209                         ht_item_data = HASHTABLE_ENTRY_FIND_SPECIAL(cache_ht_,
1210                                 ht_item, &ht_key,
1211                                 ht_items_fixed_size_left_cmp_func);
1212
1213                         if (ht_item_data != NULL) {
1214                             item = ht_item_data->fifo_policy_item;
1215                             connected_item = item->connected_item;
1216
1217                             common_entry->policies[0]->remove_item_func(
1218                                 common_entry->policies[0],
1219                                 item);
1220
1221                             free(ht_item_data->key);
1222                             free(ht_item_data->value);
1223                             HASHTABLE_ENTRY_REMOVE(cache_ht_, ht_item,
1224                                 ht_item_data);
1225                             --common_entry->items_size;
1226
1227                             common_entry->policies[0]->destroy_item_func(
1228                                 item);
1229                             if (common_entry->policies_size == 2) {
1230                                 common_entry->policies[1]->remove_item_func(
1231                                     common_entry->policies[1],
1232                                     connected_item);
1233                                 common_entry->policies[1]->destroy_item_func(
1234                                     connected_item);
1235                             }
1236                         }
1237                 } while (ht_item_data != NULL);
1238         }
1239
1240         TRACE_OUT(transform_cache_entry_part);
1241         return (0);
1242 }