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 } 1243