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