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
ht_items_cmp_func(const void * p1,const void * p2)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
ht_items_fixed_size_left_cmp_func(const void * p1,const void * p2)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
ht_item_hash_func(const void * p,size_t cache_entries_size)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
entries_bsearch_cmp_func(const void * key,const void * ent)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
entries_qsort_cmp_func(const void * e1,const void * e2)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_ **
find_cache_entry_p(struct cache_ * the_cache,const char * entry_name)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
destroy_cache_mp_write_session(struct cache_mp_write_session_ * ws)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
destroy_cache_mp_read_session(struct cache_mp_read_session_ * rs)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
destroy_cache_entry(struct cache_entry_ * entry)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
clear_cache_entry(struct cache_entry_ * entry)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
cache_lifetime_common_continue_func(struct cache_common_entry_ * entry,struct cache_policy_item_ * item)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
cache_elemsize_common_continue_func(struct cache_common_entry_ * entry,struct cache_policy_item_ * item)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
flush_cache_policy(struct cache_common_entry_ * entry,struct cache_policy_ * policy,struct cache_policy_ * connected_policy,int (* continue_func)(struct cache_common_entry_ *,struct cache_policy_item_ *))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
flush_cache_entry(struct cache_entry_ * entry)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_ *
init_cache(struct cache_params const * params)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
destroy_cache(struct cache_ * the_cache)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
register_cache_entry(struct cache_ * the_cache,struct cache_entry_params const * params)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
unregister_cache_entry(struct cache_ * the_cache,const char * entry_name)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_ *
find_cache_entry(struct cache_ * the_cache,const char * entry_name)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
cache_read(struct cache_entry_ * entry,const char * key,size_t key_size,char * value,size_t * value_size)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
cache_write(struct cache_entry_ * entry,const char * key,size_t key_size,char const * value,size_t value_size)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_ *
open_cache_mp_write_session(struct cache_entry_ * entry)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
cache_mp_write(struct cache_mp_write_session_ * ws,char * data,size_t data_size)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
abandon_cache_mp_write_session(struct cache_mp_write_session_ * ws)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
close_cache_mp_write_session(struct cache_mp_write_session_ * ws)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_ *
open_cache_mp_read_session(struct cache_entry_ * entry)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
cache_mp_read(struct cache_mp_read_session_ * rs,char * data,size_t * data_size)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
close_cache_mp_read_session(struct cache_mp_read_session_ * rs)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
transform_cache_entry(struct cache_entry_ * entry,enum cache_transformation_t transformation)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
transform_cache_entry_part(struct cache_entry_ * entry,enum cache_transformation_t transformation,const char * key_part,size_t key_part_size,enum part_position_t part_position)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