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