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