2 * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
40 #define INITIAL_ENTRIES_CAPACITY 32
41 #define ENTRIES_CAPACITY_STEP 32
43 #define STRING_SIMPLE_HASH_BODY(in_var, var, a, M) \
44 for ((var) = 0; *(in_var) != '\0'; ++(in_var)) \
45 (var) = ((a)*(var) + *(in_var)) % (M)
47 #define STRING_SIMPLE_MP2_HASH_BODY(in_var, var, a, M) \
48 for ((var) = 0; *(in_var) != 0; ++(in_var)) \
49 (var) = ((a)*(var) + *(in_var)) & (M - 1)
51 static int cache_elemsize_common_continue_func(struct cache_common_entry_ *,
52 struct cache_policy_item_ *);
53 static int cache_lifetime_common_continue_func(struct cache_common_entry_ *,
54 struct cache_policy_item_ *);
55 static void clear_cache_entry(struct cache_entry_ *);
56 static void destroy_cache_entry(struct cache_entry_ *);
57 static void destroy_cache_mp_read_session(struct cache_mp_read_session_ *);
58 static void destroy_cache_mp_write_session(struct cache_mp_write_session_ *);
59 static int entries_bsearch_cmp_func(const void *, const void *);
60 static int entries_qsort_cmp_func(const void *, const void *);
61 static struct cache_entry_ ** find_cache_entry_p(struct cache_ *,
63 static void flush_cache_entry(struct cache_entry_ *);
64 static void flush_cache_policy(struct cache_common_entry_ *,
65 struct cache_policy_ *, struct cache_policy_ *,
66 int (*)(struct cache_common_entry_ *,
67 struct cache_policy_item_ *));
68 static int ht_items_cmp_func(const void *, const void *);
69 static int ht_items_fixed_size_left_cmp_func(const void *, const void *);
70 static hashtable_index_t ht_item_hash_func(const void *, size_t);
73 * Hashing and comparing routines, that are used with the hash tables
76 ht_items_cmp_func(const void *p1, const void *p2)
78 struct cache_ht_item_data_ *hp1, *hp2;
82 hp1 = (struct cache_ht_item_data_ *)p1;
83 hp2 = (struct cache_ht_item_data_ *)p2;
85 assert(hp1->key != NULL);
86 assert(hp2->key != NULL);
88 if (hp1->key_size != hp2->key_size) {
89 min_size = (hp1->key_size < hp2->key_size) ? hp1->key_size :
91 result = memcmp(hp1->key, hp2->key, min_size);
94 return ((hp1->key_size < hp2->key_size) ? -1 : 1);
98 return (memcmp(hp1->key, hp2->key, hp1->key_size));
102 ht_items_fixed_size_left_cmp_func(const void *p1, const void *p2)
104 struct cache_ht_item_data_ *hp1, *hp2;
108 hp1 = (struct cache_ht_item_data_ *)p1;
109 hp2 = (struct cache_ht_item_data_ *)p2;
111 assert(hp1->key != NULL);
112 assert(hp2->key != NULL);
114 if (hp1->key_size != hp2->key_size) {
115 min_size = (hp1->key_size < hp2->key_size) ? hp1->key_size :
117 result = memcmp(hp1->key, hp2->key, min_size);
120 if (min_size == hp1->key_size)
123 return ((hp1->key_size < hp2->key_size) ? -1 : 1);
127 return (memcmp(hp1->key, hp2->key, hp1->key_size));
130 static hashtable_index_t
131 ht_item_hash_func(const void *p, size_t cache_entries_size)
133 struct cache_ht_item_data_ *hp;
136 hashtable_index_t retval;
138 hp = (struct cache_ht_item_data_ *)p;
139 assert(hp->key != NULL);
142 for (i = 0; i < hp->key_size; ++i)
143 retval = (127 * retval + (unsigned char)hp->key[i]) %
149 HASHTABLE_PROTOTYPE(cache_ht_, cache_ht_item_, struct cache_ht_item_data_);
150 HASHTABLE_GENERATE(cache_ht_, cache_ht_item_, struct cache_ht_item_data_, data,
151 ht_item_hash_func, ht_items_cmp_func);
154 * Routines to sort and search the entries by name
157 entries_bsearch_cmp_func(const void *key, const void *ent)
163 return (strcmp((char const *)key,
164 (*(struct cache_entry_ const **)ent)->name));
168 entries_qsort_cmp_func(const void *e1, const void *e2)
174 return (strcmp((*(struct cache_entry_ const **)e1)->name,
175 (*(struct cache_entry_ const **)e2)->name));
178 static struct cache_entry_ **
179 find_cache_entry_p(struct cache_ *the_cache, const char *entry_name)
182 return ((struct cache_entry_ **)(bsearch(entry_name, the_cache->entries,
183 the_cache->entries_size, sizeof(struct cache_entry_ *),
184 entries_bsearch_cmp_func)));
188 destroy_cache_mp_write_session(struct cache_mp_write_session_ *ws)
191 struct cache_mp_data_item_ *data_item;
193 TRACE_IN(destroy_cache_mp_write_session);
195 while (!TAILQ_EMPTY(&ws->items)) {
196 data_item = TAILQ_FIRST(&ws->items);
197 TAILQ_REMOVE(&ws->items, data_item, entries);
198 free(data_item->value);
203 TRACE_OUT(destroy_cache_mp_write_session);
207 destroy_cache_mp_read_session(struct cache_mp_read_session_ *rs)
210 TRACE_IN(destroy_cache_mp_read_session);
213 TRACE_OUT(destroy_cache_mp_read_session);
217 destroy_cache_entry(struct cache_entry_ *entry)
219 struct cache_common_entry_ *common_entry;
220 struct cache_mp_entry_ *mp_entry;
221 struct cache_mp_read_session_ *rs;
222 struct cache_mp_write_session_ *ws;
223 struct cache_ht_item_ *ht_item;
224 struct cache_ht_item_data_ *ht_item_data;
226 TRACE_IN(destroy_cache_entry);
227 assert(entry != NULL);
229 if (entry->params->entry_type == CET_COMMON) {
230 common_entry = (struct cache_common_entry_ *)entry;
232 HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
233 HASHTABLE_ENTRY_FOREACH(ht_item, data, ht_item_data)
235 free(ht_item_data->key);
236 free(ht_item_data->value);
238 HASHTABLE_ENTRY_CLEAR(ht_item, data);
241 HASHTABLE_DESTROY(&(common_entry->items), data);
243 /* FIFO policy is always first */
244 destroy_cache_fifo_policy(common_entry->policies[0]);
245 switch (common_entry->common_params.policy) {
247 destroy_cache_lru_policy(common_entry->policies[1]);
250 destroy_cache_lfu_policy(common_entry->policies[1]);
255 free(common_entry->policies);
257 mp_entry = (struct cache_mp_entry_ *)entry;
259 while (!TAILQ_EMPTY(&mp_entry->ws_head)) {
260 ws = TAILQ_FIRST(&mp_entry->ws_head);
261 TAILQ_REMOVE(&mp_entry->ws_head, ws, entries);
262 destroy_cache_mp_write_session(ws);
265 while (!TAILQ_EMPTY(&mp_entry->rs_head)) {
266 rs = TAILQ_FIRST(&mp_entry->rs_head);
267 TAILQ_REMOVE(&mp_entry->rs_head, rs, entries);
268 destroy_cache_mp_read_session(rs);
271 if (mp_entry->completed_write_session != NULL)
272 destroy_cache_mp_write_session(
273 mp_entry->completed_write_session);
275 if (mp_entry->pending_write_session != NULL)
276 destroy_cache_mp_write_session(
277 mp_entry->pending_write_session);
282 TRACE_OUT(destroy_cache_entry);
286 clear_cache_entry(struct cache_entry_ *entry)
288 struct cache_mp_entry_ *mp_entry;
289 struct cache_common_entry_ *common_entry;
290 struct cache_ht_item_ *ht_item;
291 struct cache_ht_item_data_ *ht_item_data;
292 struct cache_policy_ *policy;
293 struct cache_policy_item_ *item, *next_item;
297 if (entry->params->entry_type == CET_COMMON) {
298 common_entry = (struct cache_common_entry_ *)entry;
301 HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
302 HASHTABLE_ENTRY_FOREACH(ht_item, data, ht_item_data)
304 free(ht_item_data->key);
305 free(ht_item_data->value);
307 entry_size += HASHTABLE_ENTRY_SIZE(ht_item, data);
308 HASHTABLE_ENTRY_CLEAR(ht_item, data);
311 common_entry->items_size -= entry_size;
312 for (i = 0; i < common_entry->policies_size; ++i) {
313 policy = common_entry->policies[i];
316 item = policy->get_first_item_func(policy);
317 while (item != NULL) {
318 next_item = policy->get_next_item_func(policy,
320 policy->remove_item_func(policy, item);
321 policy->destroy_item_func(item);
326 mp_entry = (struct cache_mp_entry_ *)entry;
328 if (mp_entry->rs_size == 0) {
329 if (mp_entry->completed_write_session != NULL) {
330 destroy_cache_mp_write_session(
331 mp_entry->completed_write_session);
332 mp_entry->completed_write_session = NULL;
335 memset(&mp_entry->creation_time, 0,
336 sizeof(struct timeval));
337 memset(&mp_entry->last_request_time, 0,
338 sizeof(struct timeval));
344 * When passed to the flush_cache_policy, ensures that all old elements are
348 cache_lifetime_common_continue_func(struct cache_common_entry_ *entry,
349 struct cache_policy_item_ *item)
352 return ((item->last_request_time.tv_sec - item->creation_time.tv_sec >
353 entry->common_params.max_lifetime.tv_sec) ? 1: 0);
357 * When passed to the flush_cache_policy, ensures that all elements, that
358 * exceed the size limit, are deleted.
361 cache_elemsize_common_continue_func(struct cache_common_entry_ *entry,
362 struct cache_policy_item_ *item)
365 return ((entry->items_size > entry->common_params.satisf_elemsize) ? 1
370 * Removes the elements from the cache entry, while the continue_func returns 1.
373 flush_cache_policy(struct cache_common_entry_ *entry,
374 struct cache_policy_ *policy,
375 struct cache_policy_ *connected_policy,
376 int (*continue_func)(struct cache_common_entry_ *,
377 struct cache_policy_item_ *))
379 struct cache_policy_item_ *item, *next_item, *connected_item;
380 struct cache_ht_item_ *ht_item;
381 struct cache_ht_item_data_ *ht_item_data, ht_key;
382 hashtable_index_t hash;
384 assert(policy != NULL);
387 item = policy->get_first_item_func(policy);
388 while ((item != NULL) && (continue_func(entry, item) == 1)) {
389 next_item = policy->get_next_item_func(policy, item);
391 connected_item = item->connected_item;
392 policy->remove_item_func(policy, item);
394 memset(&ht_key, 0, sizeof(struct cache_ht_item_data_));
395 ht_key.key = item->key;
396 ht_key.key_size = item->key_size;
398 hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &entry->items,
400 assert(hash < HASHTABLE_ENTRIES_COUNT(&entry->items));
402 ht_item = HASHTABLE_GET_ENTRY(&(entry->items), hash);
403 ht_item_data = HASHTABLE_ENTRY_FIND(cache_ht_, ht_item,
405 assert(ht_item_data != NULL);
406 free(ht_item_data->key);
407 free(ht_item_data->value);
408 HASHTABLE_ENTRY_REMOVE(cache_ht_, ht_item, ht_item_data);
411 policy->destroy_item_func(item);
413 if (connected_item != NULL) {
414 connected_policy->remove_item_func(connected_policy,
416 connected_policy->destroy_item_func(connected_item);
424 flush_cache_entry(struct cache_entry_ *entry)
426 struct cache_mp_entry_ *mp_entry;
427 struct cache_common_entry_ *common_entry;
428 struct cache_policy_ *policy, *connected_policy;
430 connected_policy = NULL;
431 if (entry->params->entry_type == CET_COMMON) {
432 common_entry = (struct cache_common_entry_ *)entry;
433 if ((common_entry->common_params.max_lifetime.tv_sec != 0) ||
434 (common_entry->common_params.max_lifetime.tv_usec != 0)) {
436 policy = common_entry->policies[0];
437 if (common_entry->policies_size > 1)
438 connected_policy = common_entry->policies[1];
440 flush_cache_policy(common_entry, policy,
442 cache_lifetime_common_continue_func);
446 if ((common_entry->common_params.max_elemsize != 0) &&
447 common_entry->items_size >
448 common_entry->common_params.max_elemsize) {
450 if (common_entry->policies_size > 1) {
451 policy = common_entry->policies[1];
452 connected_policy = common_entry->policies[0];
454 policy = common_entry->policies[0];
455 connected_policy = NULL;
458 flush_cache_policy(common_entry, policy,
460 cache_elemsize_common_continue_func);
463 mp_entry = (struct cache_mp_entry_ *)entry;
465 if ((mp_entry->mp_params.max_lifetime.tv_sec != 0)
466 || (mp_entry->mp_params.max_lifetime.tv_usec != 0)) {
468 if (mp_entry->last_request_time.tv_sec -
469 mp_entry->last_request_time.tv_sec >
470 mp_entry->mp_params.max_lifetime.tv_sec)
471 clear_cache_entry(entry);
477 init_cache(struct cache_params const *params)
479 struct cache_ *retval;
481 TRACE_IN(init_cache);
482 assert(params != NULL);
484 retval = calloc(1, sizeof(*retval));
485 assert(retval != NULL);
487 assert(params != NULL);
488 memcpy(&retval->params, params, sizeof(struct cache_params));
490 retval->entries = calloc(1,
491 sizeof(*retval->entries) * INITIAL_ENTRIES_CAPACITY);
492 assert(retval->entries != NULL);
494 retval->entries_capacity = INITIAL_ENTRIES_CAPACITY;
495 retval->entries_size = 0;
497 TRACE_OUT(init_cache);
502 destroy_cache(struct cache_ *the_cache)
505 TRACE_IN(destroy_cache);
506 assert(the_cache != NULL);
508 if (the_cache->entries != NULL) {
510 for (i = 0; i < the_cache->entries_size; ++i)
511 destroy_cache_entry(the_cache->entries[i]);
513 free(the_cache->entries);
517 TRACE_OUT(destroy_cache);
521 register_cache_entry(struct cache_ *the_cache,
522 struct cache_entry_params const *params)
525 size_t entry_name_size;
526 struct cache_common_entry_ *new_common_entry;
527 struct cache_mp_entry_ *new_mp_entry;
529 TRACE_IN(register_cache_entry);
530 assert(the_cache != NULL);
532 if (find_cache_entry(the_cache, params->entry_name) != NULL) {
533 TRACE_OUT(register_cache_entry);
537 if (the_cache->entries_size == the_cache->entries_capacity) {
538 struct cache_entry_ **new_entries;
541 new_capacity = the_cache->entries_capacity +
542 ENTRIES_CAPACITY_STEP;
543 new_entries = calloc(1,
544 sizeof(*new_entries) * new_capacity);
545 assert(new_entries != NULL);
547 memcpy(new_entries, the_cache->entries,
548 sizeof(struct cache_entry_ *)
549 * the_cache->entries_size);
551 free(the_cache->entries);
552 the_cache->entries = new_entries;
555 entry_name_size = strlen(params->entry_name) + 1;
556 switch (params->entry_type)
559 new_common_entry = calloc(1,
560 sizeof(*new_common_entry));
561 assert(new_common_entry != NULL);
563 memcpy(&new_common_entry->common_params, params,
564 sizeof(struct common_cache_entry_params));
565 new_common_entry->params =
566 (struct cache_entry_params *)&new_common_entry->common_params;
568 new_common_entry->common_params.cep.entry_name = calloc(1,
570 assert(new_common_entry->common_params.cep.entry_name != NULL);
571 strlcpy(new_common_entry->common_params.cep.entry_name,
572 params->entry_name, entry_name_size);
573 new_common_entry->name =
574 new_common_entry->common_params.cep.entry_name;
576 HASHTABLE_INIT(&(new_common_entry->items),
577 struct cache_ht_item_data_, data,
578 new_common_entry->common_params.cache_entries_size);
580 if (new_common_entry->common_params.policy == CPT_FIFO)
585 new_common_entry->policies = calloc(1,
586 sizeof(*new_common_entry->policies) * policies_size);
587 assert(new_common_entry->policies != NULL);
589 new_common_entry->policies_size = policies_size;
590 new_common_entry->policies[0] = init_cache_fifo_policy();
592 if (policies_size > 1) {
593 switch (new_common_entry->common_params.policy) {
595 new_common_entry->policies[1] =
596 init_cache_lru_policy();
599 new_common_entry->policies[1] =
600 init_cache_lfu_policy();
607 new_common_entry->get_time_func =
608 the_cache->params.get_time_func;
609 the_cache->entries[the_cache->entries_size++] =
610 (struct cache_entry_ *)new_common_entry;
613 new_mp_entry = calloc(1,
614 sizeof(*new_mp_entry));
615 assert(new_mp_entry != NULL);
617 memcpy(&new_mp_entry->mp_params, params,
618 sizeof(struct mp_cache_entry_params));
619 new_mp_entry->params =
620 (struct cache_entry_params *)&new_mp_entry->mp_params;
622 new_mp_entry->mp_params.cep.entry_name = calloc(1,
624 assert(new_mp_entry->mp_params.cep.entry_name != NULL);
625 strlcpy(new_mp_entry->mp_params.cep.entry_name, params->entry_name,
627 new_mp_entry->name = new_mp_entry->mp_params.cep.entry_name;
629 TAILQ_INIT(&new_mp_entry->ws_head);
630 TAILQ_INIT(&new_mp_entry->rs_head);
632 new_mp_entry->get_time_func = the_cache->params.get_time_func;
633 the_cache->entries[the_cache->entries_size++] =
634 (struct cache_entry_ *)new_mp_entry;
639 qsort(the_cache->entries, the_cache->entries_size,
640 sizeof(struct cache_entry_ *), entries_qsort_cmp_func);
642 TRACE_OUT(register_cache_entry);
647 unregister_cache_entry(struct cache_ *the_cache, const char *entry_name)
649 struct cache_entry_ **del_ent;
651 TRACE_IN(unregister_cache_entry);
652 assert(the_cache != NULL);
654 del_ent = find_cache_entry_p(the_cache, entry_name);
655 if (del_ent != NULL) {
656 destroy_cache_entry(*del_ent);
657 --the_cache->entries_size;
659 memmove(del_ent, del_ent + 1,
660 (&(the_cache->entries[--the_cache->entries_size]) -
661 del_ent) * sizeof(struct cache_entry_ *));
663 TRACE_OUT(unregister_cache_entry);
666 TRACE_OUT(unregister_cache_entry);
671 struct cache_entry_ *
672 find_cache_entry(struct cache_ *the_cache, const char *entry_name)
674 struct cache_entry_ **result;
676 TRACE_IN(find_cache_entry);
677 result = find_cache_entry_p(the_cache, entry_name);
679 if (result == NULL) {
680 TRACE_OUT(find_cache_entry);
683 TRACE_OUT(find_cache_entry);
689 * Tries to read the element with the specified key from the cache. If the
690 * value_size is too small, it will be filled with the proper number, and
691 * the user will need to call cache_read again with the value buffer, that
693 * Function returns 0 on success, -1 on error, and -2 if the value_size is too
697 cache_read(struct cache_entry_ *entry, const char *key, size_t key_size,
698 char *value, size_t *value_size)
700 struct cache_common_entry_ *common_entry;
701 struct cache_ht_item_data_ item_data, *find_res;
702 struct cache_ht_item_ *item;
703 hashtable_index_t hash;
704 struct cache_policy_item_ *connected_item;
706 TRACE_IN(cache_read);
707 assert(entry != NULL);
709 assert(value_size != NULL);
710 assert(entry->params->entry_type == CET_COMMON);
712 common_entry = (struct cache_common_entry_ *)entry;
714 memset(&item_data, 0, sizeof(struct cache_ht_item_data_));
715 /* can't avoid the cast here */
716 item_data.key = (char *)key;
717 item_data.key_size = key_size;
719 hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &common_entry->items,
721 assert(hash < HASHTABLE_ENTRIES_COUNT(&common_entry->items));
723 item = HASHTABLE_GET_ENTRY(&(common_entry->items), hash);
724 find_res = HASHTABLE_ENTRY_FIND(cache_ht_, item, &item_data);
725 if (find_res == NULL) {
726 TRACE_OUT(cache_read);
729 /* pretend that entry was not found if confidence is below threshold*/
730 if (find_res->confidence <
731 common_entry->common_params.confidence_threshold) {
732 TRACE_OUT(cache_read);
736 if ((common_entry->common_params.max_lifetime.tv_sec != 0) ||
737 (common_entry->common_params.max_lifetime.tv_usec != 0)) {
739 if (find_res->fifo_policy_item->last_request_time.tv_sec -
740 find_res->fifo_policy_item->creation_time.tv_sec >
741 common_entry->common_params.max_lifetime.tv_sec) {
744 free(find_res->value);
747 find_res->fifo_policy_item->connected_item;
748 if (connected_item != NULL) {
749 common_entry->policies[1]->remove_item_func(
750 common_entry->policies[1],
752 common_entry->policies[1]->destroy_item_func(
756 common_entry->policies[0]->remove_item_func(
757 common_entry->policies[0],
758 find_res->fifo_policy_item);
759 common_entry->policies[0]->destroy_item_func(
760 find_res->fifo_policy_item);
762 HASHTABLE_ENTRY_REMOVE(cache_ht_, item, find_res);
763 --common_entry->items_size;
767 if ((*value_size < find_res->value_size) || (value == NULL)) {
768 *value_size = find_res->value_size;
769 TRACE_OUT(cache_read);
773 *value_size = find_res->value_size;
774 memcpy(value, find_res->value, find_res->value_size);
776 ++find_res->fifo_policy_item->request_count;
777 common_entry->get_time_func(
778 &find_res->fifo_policy_item->last_request_time);
779 common_entry->policies[0]->update_item_func(common_entry->policies[0],
780 find_res->fifo_policy_item);
782 if (find_res->fifo_policy_item->connected_item != NULL) {
783 connected_item = find_res->fifo_policy_item->connected_item;
784 memcpy(&connected_item->last_request_time,
785 &find_res->fifo_policy_item->last_request_time,
786 sizeof(struct timeval));
787 connected_item->request_count =
788 find_res->fifo_policy_item->request_count;
790 common_entry->policies[1]->update_item_func(
791 common_entry->policies[1], connected_item);
794 TRACE_OUT(cache_read);
799 * Writes the value with the specified key into the cache entry.
800 * Functions returns 0 on success, and -1 on error.
803 cache_write(struct cache_entry_ *entry, const char *key, size_t key_size,
804 char const *value, size_t value_size)
806 struct cache_common_entry_ *common_entry;
807 struct cache_ht_item_data_ item_data, *find_res;
808 struct cache_ht_item_ *item;
809 hashtable_index_t hash;
811 struct cache_policy_ *policy, *connected_policy;
812 struct cache_policy_item_ *policy_item;
813 struct cache_policy_item_ *connected_policy_item;
815 TRACE_IN(cache_write);
816 assert(entry != NULL);
818 assert(value != NULL);
819 assert(entry->params->entry_type == CET_COMMON);
821 common_entry = (struct cache_common_entry_ *)entry;
823 memset(&item_data, 0, sizeof(struct cache_ht_item_data_));
824 /* can't avoid the cast here */
825 item_data.key = (char *)key;
826 item_data.key_size = key_size;
828 hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &common_entry->items,
830 assert(hash < HASHTABLE_ENTRIES_COUNT(&common_entry->items));
832 item = HASHTABLE_GET_ENTRY(&(common_entry->items), hash);
833 find_res = HASHTABLE_ENTRY_FIND(cache_ht_, item, &item_data);
834 if (find_res != NULL) {
835 if (find_res->confidence < common_entry->common_params.confidence_threshold) {
836 /* duplicate entry is no error, if confidence is low */
837 if ((find_res->value_size == value_size) &&
838 (memcmp(find_res->value, value, value_size) == 0)) {
839 /* increase confidence on exact match (key and values) */
840 find_res->confidence++;
842 /* create new entry with low confidence, if value changed */
843 free(item_data.value);
844 item_data.value = malloc(value_size);
845 assert(item_data.value != NULL);
846 memcpy(item_data.value, value, value_size);
847 item_data.value_size = value_size;
848 find_res->confidence = 1;
850 TRACE_OUT(cache_write);
853 TRACE_OUT(cache_write);
857 item_data.key = malloc(key_size);
858 memcpy(item_data.key, key, key_size);
860 item_data.value = malloc(value_size);
861 assert(item_data.value != NULL);
863 memcpy(item_data.value, value, value_size);
864 item_data.value_size = value_size;
866 item_data.confidence = 1;
868 policy_item = common_entry->policies[0]->create_item_func();
869 policy_item->key = item_data.key;
870 policy_item->key_size = item_data.key_size;
871 common_entry->get_time_func(&policy_item->creation_time);
873 if (common_entry->policies_size > 1) {
874 connected_policy_item =
875 common_entry->policies[1]->create_item_func();
876 memcpy(&connected_policy_item->creation_time,
877 &policy_item->creation_time,
878 sizeof(struct timeval));
879 connected_policy_item->key = policy_item->key;
880 connected_policy_item->key_size = policy_item->key_size;
882 connected_policy_item->connected_item = policy_item;
883 policy_item->connected_item = connected_policy_item;
886 item_data.fifo_policy_item = policy_item;
888 common_entry->policies[0]->add_item_func(common_entry->policies[0],
890 if (common_entry->policies_size > 1)
891 common_entry->policies[1]->add_item_func(
892 common_entry->policies[1], connected_policy_item);
894 HASHTABLE_ENTRY_STORE(cache_ht_, item, &item_data);
895 ++common_entry->items_size;
897 if ((common_entry->common_params.max_elemsize != 0) &&
898 (common_entry->items_size >
899 common_entry->common_params.max_elemsize)) {
900 if (common_entry->policies_size > 1) {
901 policy = common_entry->policies[1];
902 connected_policy = common_entry->policies[0];
904 policy = common_entry->policies[0];
905 connected_policy = NULL;
908 flush_cache_policy(common_entry, policy, connected_policy,
909 cache_elemsize_common_continue_func);
912 TRACE_OUT(cache_write);
917 * Initializes the write session for the specified multipart entry. This
918 * session then should be filled with data either committed or abandoned by
919 * using close_cache_mp_write_session or abandon_cache_mp_write_session
921 * Returns NULL on errors (when there are too many opened write sessions for
924 struct cache_mp_write_session_ *
925 open_cache_mp_write_session(struct cache_entry_ *entry)
927 struct cache_mp_entry_ *mp_entry;
928 struct cache_mp_write_session_ *retval;
930 TRACE_IN(open_cache_mp_write_session);
931 assert(entry != NULL);
932 assert(entry->params->entry_type == CET_MULTIPART);
933 mp_entry = (struct cache_mp_entry_ *)entry;
935 if ((mp_entry->mp_params.max_sessions > 0) &&
936 (mp_entry->ws_size == mp_entry->mp_params.max_sessions)) {
937 TRACE_OUT(open_cache_mp_write_session);
943 assert(retval != NULL);
945 TAILQ_INIT(&retval->items);
946 retval->parent_entry = mp_entry;
948 TAILQ_INSERT_HEAD(&mp_entry->ws_head, retval, entries);
951 TRACE_OUT(open_cache_mp_write_session);
956 * Writes data to the specified session. Return 0 on success and -1 on errors
957 * (when write session size limit is exceeded).
960 cache_mp_write(struct cache_mp_write_session_ *ws, char *data,
963 struct cache_mp_data_item_ *new_item;
965 TRACE_IN(cache_mp_write);
967 assert(ws->parent_entry != NULL);
968 assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
970 if ((ws->parent_entry->mp_params.max_elemsize > 0) &&
971 (ws->parent_entry->mp_params.max_elemsize == ws->items_size)) {
972 TRACE_OUT(cache_mp_write);
978 assert(new_item != NULL);
980 new_item->value = malloc(data_size);
981 assert(new_item->value != NULL);
982 memcpy(new_item->value, data, data_size);
983 new_item->value_size = data_size;
985 TAILQ_INSERT_TAIL(&ws->items, new_item, entries);
988 TRACE_OUT(cache_mp_write);
993 * Abandons the write session and frees all the connected resources.
996 abandon_cache_mp_write_session(struct cache_mp_write_session_ *ws)
999 TRACE_IN(abandon_cache_mp_write_session);
1001 assert(ws->parent_entry != NULL);
1002 assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
1004 TAILQ_REMOVE(&ws->parent_entry->ws_head, ws, entries);
1005 --ws->parent_entry->ws_size;
1007 destroy_cache_mp_write_session(ws);
1008 TRACE_OUT(abandon_cache_mp_write_session);
1012 * Commits the session to the entry, for which it was created.
1015 close_cache_mp_write_session(struct cache_mp_write_session_ *ws)
1018 TRACE_IN(close_cache_mp_write_session);
1020 assert(ws->parent_entry != NULL);
1021 assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
1023 TAILQ_REMOVE(&ws->parent_entry->ws_head, ws, entries);
1024 --ws->parent_entry->ws_size;
1026 if (ws->parent_entry->completed_write_session == NULL) {
1028 * If there is no completed session yet, this will be the one
1030 ws->parent_entry->get_time_func(
1031 &ws->parent_entry->creation_time);
1032 ws->parent_entry->completed_write_session = ws;
1035 * If there is a completed session, then we'll save our session
1036 * as a pending session. If there is already a pending session,
1037 * it would be destroyed.
1039 if (ws->parent_entry->pending_write_session != NULL)
1040 destroy_cache_mp_write_session(
1041 ws->parent_entry->pending_write_session);
1043 ws->parent_entry->pending_write_session = ws;
1045 TRACE_OUT(close_cache_mp_write_session);
1049 * Opens read session for the specified entry. Returns NULL on errors (when
1050 * there are no data in the entry, or the data are obsolete).
1052 struct cache_mp_read_session_ *
1053 open_cache_mp_read_session(struct cache_entry_ *entry)
1055 struct cache_mp_entry_ *mp_entry;
1056 struct cache_mp_read_session_ *retval;
1058 TRACE_IN(open_cache_mp_read_session);
1059 assert(entry != NULL);
1060 assert(entry->params->entry_type == CET_MULTIPART);
1061 mp_entry = (struct cache_mp_entry_ *)entry;
1063 if (mp_entry->completed_write_session == NULL) {
1064 TRACE_OUT(open_cache_mp_read_session);
1068 if ((mp_entry->mp_params.max_lifetime.tv_sec != 0)
1069 || (mp_entry->mp_params.max_lifetime.tv_usec != 0)) {
1070 if (mp_entry->last_request_time.tv_sec -
1071 mp_entry->last_request_time.tv_sec >
1072 mp_entry->mp_params.max_lifetime.tv_sec) {
1073 flush_cache_entry(entry);
1074 TRACE_OUT(open_cache_mp_read_session);
1081 assert(retval != NULL);
1083 retval->parent_entry = mp_entry;
1084 retval->current_item = TAILQ_FIRST(
1085 &mp_entry->completed_write_session->items);
1087 TAILQ_INSERT_HEAD(&mp_entry->rs_head, retval, entries);
1088 ++mp_entry->rs_size;
1090 mp_entry->get_time_func(&mp_entry->last_request_time);
1091 TRACE_OUT(open_cache_mp_read_session);
1096 * Reads the data from the read session - step by step.
1097 * Returns 0 on success, -1 on error (when there are no more data), and -2 if
1098 * the data_size is too small. In the last case, data_size would be filled
1102 cache_mp_read(struct cache_mp_read_session_ *rs, char *data, size_t *data_size)
1105 TRACE_IN(cache_mp_read);
1108 if (rs->current_item == NULL) {
1109 TRACE_OUT(cache_mp_read);
1113 if (rs->current_item->value_size > *data_size) {
1114 *data_size = rs->current_item->value_size;
1116 TRACE_OUT(cache_mp_read);
1120 TRACE_OUT(cache_mp_read);
1124 *data_size = rs->current_item->value_size;
1125 memcpy(data, rs->current_item->value, rs->current_item->value_size);
1126 rs->current_item = TAILQ_NEXT(rs->current_item, entries);
1128 TRACE_OUT(cache_mp_read);
1133 * Closes the read session. If there are no more read sessions and there is
1134 * a pending write session, it will be committed and old
1135 * completed_write_session will be destroyed.
1138 close_cache_mp_read_session(struct cache_mp_read_session_ *rs)
1141 TRACE_IN(close_cache_mp_read_session);
1143 assert(rs->parent_entry != NULL);
1145 TAILQ_REMOVE(&rs->parent_entry->rs_head, rs, entries);
1146 --rs->parent_entry->rs_size;
1148 if ((rs->parent_entry->rs_size == 0) &&
1149 (rs->parent_entry->pending_write_session != NULL)) {
1150 destroy_cache_mp_write_session(
1151 rs->parent_entry->completed_write_session);
1152 rs->parent_entry->completed_write_session =
1153 rs->parent_entry->pending_write_session;
1154 rs->parent_entry->pending_write_session = NULL;
1157 destroy_cache_mp_read_session(rs);
1158 TRACE_OUT(close_cache_mp_read_session);
1162 transform_cache_entry(struct cache_entry_ *entry,
1163 enum cache_transformation_t transformation)
1166 TRACE_IN(transform_cache_entry);
1167 switch (transformation) {
1169 clear_cache_entry(entry);
1170 TRACE_OUT(transform_cache_entry);
1173 flush_cache_entry(entry);
1174 TRACE_OUT(transform_cache_entry);
1177 TRACE_OUT(transform_cache_entry);
1183 transform_cache_entry_part(struct cache_entry_ *entry,
1184 enum cache_transformation_t transformation, const char *key_part,
1185 size_t key_part_size, enum part_position_t part_position)
1187 struct cache_common_entry_ *common_entry;
1188 struct cache_ht_item_ *ht_item;
1189 struct cache_ht_item_data_ *ht_item_data, ht_key;
1191 struct cache_policy_item_ *item, *connected_item;
1193 TRACE_IN(transform_cache_entry_part);
1194 if (entry->params->entry_type != CET_COMMON) {
1195 TRACE_OUT(transform_cache_entry_part);
1199 if (transformation != CTT_CLEAR) {
1200 TRACE_OUT(transform_cache_entry_part);
1204 memset(&ht_key, 0, sizeof(struct cache_ht_item_data_));
1205 ht_key.key = (char *)key_part; /* can't avoid casting here */
1206 ht_key.key_size = key_part_size;
1208 common_entry = (struct cache_common_entry_ *)entry;
1209 HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
1211 ht_item_data = HASHTABLE_ENTRY_FIND_SPECIAL(cache_ht_,
1213 ht_items_fixed_size_left_cmp_func);
1215 if (ht_item_data != NULL) {
1216 item = ht_item_data->fifo_policy_item;
1217 connected_item = item->connected_item;
1219 common_entry->policies[0]->remove_item_func(
1220 common_entry->policies[0],
1223 free(ht_item_data->key);
1224 free(ht_item_data->value);
1225 HASHTABLE_ENTRY_REMOVE(cache_ht_, ht_item,
1227 --common_entry->items_size;
1229 common_entry->policies[0]->destroy_item_func(
1231 if (common_entry->policies_size == 2) {
1232 common_entry->policies[1]->remove_item_func(
1233 common_entry->policies[1],
1235 common_entry->policies[1]->destroy_item_func(
1239 } while (ht_item_data != NULL);
1242 TRACE_OUT(transform_cache_entry_part);