Merge branch 'vendor/OPENSSL'
[dragonfly.git] / usr.sbin / nscd / cachelib.c
1 /*-
2  * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  *
26  * $FreeBSD: src/usr.sbin/nscd/cachelib.c,v 1.4 2008/10/23 00:31:15 delphij Exp $
27  */
28
29 #include <sys/time.h>
30 #include <assert.h>
31 #include <stdlib.h>
32 #include <string.h>
33 #include "cachelib.h"
34 #include "debug.h"
35
36 #define INITIAL_ENTRIES_CAPACITY 32
37 #define ENTRIES_CAPACITY_STEP 32
38
39 #define STRING_SIMPLE_HASH_BODY(in_var, var, a, M)              \
40         for ((var) = 0; *(in_var) != '\0'; ++(in_var))          \
41                 (var) = ((a)*(var) + *(in_var)) % (M)
42
43 #define STRING_SIMPLE_MP2_HASH_BODY(in_var, var, a, M)          \
44         for ((var) = 0; *(in_var) != 0; ++(in_var))             \
45                 (var) = ((a)*(var) + *(in_var)) & (M - 1)
46
47 static int cache_elemsize_common_continue_func(struct cache_common_entry_ *,
48         struct cache_policy_item_ *);
49 static int cache_lifetime_common_continue_func(struct cache_common_entry_ *,
50         struct cache_policy_item_ *);
51 static void clear_cache_entry(struct cache_entry_ *);
52 static void destroy_cache_entry(struct cache_entry_ *);
53 static void destroy_cache_mp_read_session(struct cache_mp_read_session_ *);
54 static void destroy_cache_mp_write_session(struct cache_mp_write_session_ *);
55 static int entries_bsearch_cmp_func(const void *, const void *);
56 static int entries_qsort_cmp_func(const void *, const void *);
57 static struct cache_entry_ ** find_cache_entry_p(struct cache_ *,
58         const char *);
59 static void flush_cache_entry(struct cache_entry_ *);
60 static void flush_cache_policy(struct cache_common_entry_ *,
61         struct cache_policy_ *, struct cache_policy_ *,
62                 int (*)(struct cache_common_entry_ *,
63                 struct cache_policy_item_ *));
64 static int ht_items_cmp_func(const void *, const void *);
65 static int ht_items_fixed_size_left_cmp_func(const void *, const void *);
66 static hashtable_index_t ht_item_hash_func(const void *, size_t);
67
68 /*
69  * Hashing and comparing routines, that are used with the hash tables
70  */
71 static int
72 ht_items_cmp_func(const void *p1, const void *p2)
73 {
74         struct cache_ht_item_data_ *hp1, *hp2;
75         size_t min_size;
76         int result;
77
78         hp1 = (struct cache_ht_item_data_ *)p1;
79         hp2 = (struct cache_ht_item_data_ *)p2;
80
81         assert(hp1->key != NULL);
82         assert(hp2->key != NULL);
83
84         if (hp1->key_size != hp2->key_size) {
85                 min_size = (hp1->key_size < hp2->key_size) ? hp1->key_size :
86                         hp2->key_size;
87                 result = memcmp(hp1->key, hp2->key, min_size);
88
89                 if (result == 0)
90                         return ((hp1->key_size < hp2->key_size) ? -1 : 1);
91                 else
92                         return (result);
93         } else
94                 return (memcmp(hp1->key, hp2->key, hp1->key_size));
95 }
96
97 static int
98 ht_items_fixed_size_left_cmp_func(const void *p1, const void *p2)
99 {
100         struct cache_ht_item_data_ *hp1, *hp2;
101         size_t min_size;
102         int result;
103
104         hp1 = (struct cache_ht_item_data_ *)p1;
105         hp2 = (struct cache_ht_item_data_ *)p2;
106
107         assert(hp1->key != NULL);
108         assert(hp2->key != NULL);
109
110         if (hp1->key_size != hp2->key_size) {
111                 min_size = (hp1->key_size < hp2->key_size) ? hp1->key_size :
112                         hp2->key_size;
113                 result = memcmp(hp1->key, hp2->key, min_size);
114
115                 if (result == 0)
116                         if (min_size == hp1->key_size)
117                             return (0);
118                         else
119                             return ((hp1->key_size < hp2->key_size) ? -1 : 1);
120                 else
121                         return (result);
122         } else
123                 return (memcmp(hp1->key, hp2->key, hp1->key_size));
124 }
125
126 static hashtable_index_t
127 ht_item_hash_func(const void *p, size_t cache_entries_size)
128 {
129         struct cache_ht_item_data_ *hp;
130         size_t i;
131
132         hashtable_index_t retval;
133
134         hp = (struct cache_ht_item_data_ *)p;
135         assert(hp->key != NULL);
136
137         retval = 0;
138         for (i = 0; i < hp->key_size; ++i)
139             retval = (127 * retval + (unsigned char)hp->key[i]) %
140                 cache_entries_size;
141
142         return retval;
143 }
144
145 HASHTABLE_GENERATE(cache_ht_, cache_ht_item_, struct cache_ht_item_data_, data,
146         ht_item_hash_func, ht_items_cmp_func);
147
148 /*
149  * Routines to sort and search the entries by name
150  */
151 static int
152 entries_bsearch_cmp_func(const void *key, const void *ent)
153 {
154
155         assert(key != NULL);
156         assert(ent != NULL);
157
158         return (strcmp((char const *)key,
159                 (*(struct cache_entry_ const **)ent)->name));
160 }
161
162 static int
163 entries_qsort_cmp_func(const void *e1, const void *e2)
164 {
165
166         assert(e1 != NULL);
167         assert(e2 != NULL);
168
169         return (strcmp((*(struct cache_entry_ const **)e1)->name,
170                 (*(struct cache_entry_ const **)e2)->name));
171 }
172
173 static struct cache_entry_ **
174 find_cache_entry_p(struct cache_ *the_cache, const char *entry_name)
175 {
176
177         return ((struct cache_entry_ **)(bsearch(entry_name, the_cache->entries,
178                 the_cache->entries_size, sizeof(struct cache_entry_ *),
179                 entries_bsearch_cmp_func)));
180 }
181
182 static void
183 destroy_cache_mp_write_session(struct cache_mp_write_session_ *ws)
184 {
185
186         struct cache_mp_data_item_      *data_item;
187
188         TRACE_IN(destroy_cache_mp_write_session);
189         assert(ws != NULL);
190         while (!TAILQ_EMPTY(&ws->items)) {
191                 data_item = TAILQ_FIRST(&ws->items);
192                 TAILQ_REMOVE(&ws->items, data_item, entries);
193                 free(data_item->value);
194                 free(data_item);
195         }
196
197         free(ws);
198         TRACE_OUT(destroy_cache_mp_write_session);
199 }
200
201 static void
202 destroy_cache_mp_read_session(struct cache_mp_read_session_ *rs)
203 {
204
205         TRACE_IN(destroy_cache_mp_read_session);
206         assert(rs != NULL);
207         free(rs);
208         TRACE_OUT(destroy_cache_mp_read_session);
209 }
210
211 static void
212 destroy_cache_entry(struct cache_entry_ *entry)
213 {
214         struct cache_common_entry_      *common_entry;
215         struct cache_mp_entry_          *mp_entry;
216         struct cache_mp_read_session_   *rs;
217         struct cache_mp_write_session_  *ws;
218         struct cache_ht_item_ *ht_item;
219         struct cache_ht_item_data_ *ht_item_data;
220
221         TRACE_IN(destroy_cache_entry);
222         assert(entry != NULL);
223
224         if (entry->params->entry_type == CET_COMMON) {
225                 common_entry = (struct cache_common_entry_ *)entry;
226
227                 HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
228                         HASHTABLE_ENTRY_FOREACH(ht_item, data, ht_item_data)
229                         {
230                                 free(ht_item_data->key);
231                                 free(ht_item_data->value);
232                         }
233                         HASHTABLE_ENTRY_CLEAR(ht_item, data);
234                 }
235
236                 HASHTABLE_DESTROY(&(common_entry->items), data);
237
238                 /* FIFO policy is always first */
239                 destroy_cache_fifo_policy(common_entry->policies[0]);
240                 switch (common_entry->common_params.policy) {
241                 case CPT_LRU:
242                         destroy_cache_lru_policy(common_entry->policies[1]);
243                         break;
244                 case CPT_LFU:
245                         destroy_cache_lfu_policy(common_entry->policies[1]);
246                         break;
247                 default:
248                 break;
249                 }
250                 free(common_entry->policies);
251         } else {
252                 mp_entry = (struct cache_mp_entry_ *)entry;
253
254                 while (!TAILQ_EMPTY(&mp_entry->ws_head)) {
255                         ws = TAILQ_FIRST(&mp_entry->ws_head);
256                         TAILQ_REMOVE(&mp_entry->ws_head, ws, entries);
257                         destroy_cache_mp_write_session(ws);
258                 }
259
260                 while (!TAILQ_EMPTY(&mp_entry->rs_head)) {
261                         rs = TAILQ_FIRST(&mp_entry->rs_head);
262                         TAILQ_REMOVE(&mp_entry->rs_head, rs, entries);
263                         destroy_cache_mp_read_session(rs);
264                 }
265
266                 if (mp_entry->completed_write_session != NULL)
267                         destroy_cache_mp_write_session(
268                                 mp_entry->completed_write_session);
269
270                 if (mp_entry->pending_write_session != NULL)
271                         destroy_cache_mp_write_session(
272                                 mp_entry->pending_write_session);
273         }
274
275         free(entry->name);
276         free(entry);
277         TRACE_OUT(destroy_cache_entry);
278 }
279
280 static void
281 clear_cache_entry(struct cache_entry_ *entry)
282 {
283         struct cache_mp_entry_          *mp_entry;
284         struct cache_common_entry_      *common_entry;
285         struct cache_ht_item_ *ht_item;
286         struct cache_ht_item_data_ *ht_item_data;
287         struct cache_policy_ *policy;
288         struct cache_policy_item_ *item, *next_item;
289         size_t entry_size;
290         int i;
291
292         if (entry->params->entry_type == CET_COMMON) {
293                 common_entry = (struct cache_common_entry_ *)entry;
294
295                 entry_size = 0;
296                 HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
297                         HASHTABLE_ENTRY_FOREACH(ht_item, data, ht_item_data)
298                         {
299                                 free(ht_item_data->key);
300                                 free(ht_item_data->value);
301                         }
302                         entry_size += HASHTABLE_ENTRY_SIZE(ht_item, data);
303                         HASHTABLE_ENTRY_CLEAR(ht_item, data);
304                 }
305
306                 common_entry->items_size -= entry_size;
307                 for (i = 0; i < common_entry->policies_size; ++i) {
308                         policy = common_entry->policies[i];
309
310                         next_item = NULL;
311                         item = policy->get_first_item_func(policy);
312                         while (item != NULL) {
313                                 next_item = policy->get_next_item_func(policy,
314                                         item);
315                                 policy->remove_item_func(policy, item);
316                                 policy->destroy_item_func(item);
317                                 item = next_item;
318                         }
319                 }
320         } else {
321                 mp_entry = (struct cache_mp_entry_ *)entry;
322
323                 if (mp_entry->rs_size == 0) {
324                         if (mp_entry->completed_write_session != NULL) {
325                                 destroy_cache_mp_write_session(
326                                         mp_entry->completed_write_session);
327                                 mp_entry->completed_write_session = NULL;
328                         }
329
330                         memset(&mp_entry->creation_time, 0,
331                                 sizeof(struct timeval));
332                         memset(&mp_entry->last_request_time, 0,
333                                 sizeof(struct timeval));
334                 }
335         }
336 }
337
338 /*
339  * When passed to the flush_cache_policy, ensures that all old elements are
340  * deleted.
341  */
342 static int
343 cache_lifetime_common_continue_func(struct cache_common_entry_ *entry,
344         struct cache_policy_item_ *item)
345 {
346
347         return ((item->last_request_time.tv_sec - item->creation_time.tv_sec >
348                 entry->common_params.max_lifetime.tv_sec) ? 1: 0);
349 }
350
351 /*
352  * When passed to the flush_cache_policy, ensures that all elements, that
353  * exceed the size limit, are deleted.
354  */
355 static int
356 cache_elemsize_common_continue_func(struct cache_common_entry_ *entry,
357         struct cache_policy_item_ *item)
358 {
359
360         return ((entry->items_size > entry->common_params.satisf_elemsize) ? 1
361                 : 0);
362 }
363
364 /*
365  * Removes the elements from the cache entry, while the continue_func returns 1.
366  */
367 static void
368 flush_cache_policy(struct cache_common_entry_ *entry,
369         struct cache_policy_ *policy,
370         struct cache_policy_ *connected_policy,
371         int (*continue_func)(struct cache_common_entry_ *,
372                 struct cache_policy_item_ *))
373 {
374         struct cache_policy_item_ *item, *next_item, *connected_item;
375         struct cache_ht_item_ *ht_item;
376         struct cache_ht_item_data_ *ht_item_data, ht_key;
377         hashtable_index_t hash;
378
379         assert(policy != NULL);
380
381         next_item = NULL;
382         item = policy->get_first_item_func(policy);
383         while ((item != NULL) && (continue_func(entry, item) == 1)) {
384                 next_item = policy->get_next_item_func(policy, item);
385
386                 connected_item = item->connected_item;
387                 policy->remove_item_func(policy, item);
388
389                 memset(&ht_key, 0, sizeof(struct cache_ht_item_data_));
390                 ht_key.key = item->key;
391                 ht_key.key_size = item->key_size;
392
393                 hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &entry->items,
394                         &ht_key);
395                 assert(hash >= 0);
396                 assert(hash < HASHTABLE_ENTRIES_COUNT(&entry->items));
397
398                 ht_item = HASHTABLE_GET_ENTRY(&(entry->items), hash);
399                 ht_item_data = HASHTABLE_ENTRY_FIND(cache_ht_, ht_item,
400                         &ht_key);
401                 assert(ht_item_data != NULL);
402                 free(ht_item_data->key);
403                 free(ht_item_data->value);
404                 HASHTABLE_ENTRY_REMOVE(cache_ht_, ht_item, ht_item_data);
405                 --entry->items_size;
406
407                 policy->destroy_item_func(item);
408
409                 if (connected_item != NULL) {
410                         connected_policy->remove_item_func(connected_policy,
411                                 connected_item);
412                         connected_policy->destroy_item_func(connected_item);
413                 }
414
415                 item = next_item;
416         }
417 }
418
419 static void
420 flush_cache_entry(struct cache_entry_ *entry)
421 {
422         struct cache_mp_entry_          *mp_entry;
423         struct cache_common_entry_      *common_entry;
424         struct cache_policy_ *policy, *connected_policy;
425
426         connected_policy = NULL;
427         if (entry->params->entry_type == CET_COMMON) {
428                 common_entry = (struct cache_common_entry_ *)entry;
429                 if ((common_entry->common_params.max_lifetime.tv_sec != 0) ||
430                     (common_entry->common_params.max_lifetime.tv_usec != 0)) {
431
432                         policy = common_entry->policies[0];
433                         if (common_entry->policies_size > 1)
434                                 connected_policy = common_entry->policies[1];
435
436                         flush_cache_policy(common_entry, policy,
437                                 connected_policy,
438                                 cache_lifetime_common_continue_func);
439                 }
440
441
442                 if ((common_entry->common_params.max_elemsize != 0) &&
443                         common_entry->items_size >
444                         common_entry->common_params.max_elemsize) {
445
446                         if (common_entry->policies_size > 1) {
447                                 policy = common_entry->policies[1];
448                                 connected_policy = common_entry->policies[0];
449                         } else {
450                                 policy = common_entry->policies[0];
451                                 connected_policy = NULL;
452                         }
453
454                         flush_cache_policy(common_entry, policy,
455                                 connected_policy,
456                                 cache_elemsize_common_continue_func);
457                 }
458         } else {
459                 mp_entry = (struct cache_mp_entry_ *)entry;
460
461                 if ((mp_entry->mp_params.max_lifetime.tv_sec != 0)
462                         || (mp_entry->mp_params.max_lifetime.tv_usec != 0)) {
463
464                         if (mp_entry->last_request_time.tv_sec -
465                                 mp_entry->last_request_time.tv_sec >
466                                 mp_entry->mp_params.max_lifetime.tv_sec)
467                                 clear_cache_entry(entry);
468                 }
469         }
470 }
471
472 struct cache_ *
473 init_cache(struct cache_params const *params)
474 {
475         struct cache_ *retval;
476
477         TRACE_IN(init_cache);
478         assert(params != NULL);
479
480         retval = (struct cache_ *)calloc(1, sizeof(struct cache_));
481         assert(retval != NULL);
482
483         assert(params != NULL);
484         memcpy(&retval->params, params, sizeof(struct cache_params));
485
486         retval->entries = (struct cache_entry_ **)calloc(1,
487                 sizeof(struct cache_entry_ *) * INITIAL_ENTRIES_CAPACITY);
488         assert(retval->entries != NULL);
489
490         retval->entries_capacity = INITIAL_ENTRIES_CAPACITY;
491         retval->entries_size = 0;
492
493         TRACE_OUT(init_cache);
494         return (retval);
495 }
496
497 void
498 destroy_cache(struct cache_ *the_cache)
499 {
500
501         TRACE_IN(destroy_cache);
502         assert(the_cache != NULL);
503
504         if (the_cache->entries != NULL) {
505                 size_t i;
506                 for (i = 0; i < the_cache->entries_size; ++i)
507                         destroy_cache_entry(the_cache->entries[i]);
508
509                 free(the_cache->entries);
510         }
511
512         free(the_cache);
513         TRACE_OUT(destroy_cache);
514 }
515
516 int
517 register_cache_entry(struct cache_ *the_cache,
518         struct cache_entry_params const *params)
519 {
520         int policies_size;
521         size_t entry_name_size;
522         struct cache_common_entry_      *new_common_entry;
523         struct cache_mp_entry_          *new_mp_entry;
524
525         TRACE_IN(register_cache_entry);
526         assert(the_cache != NULL);
527
528         if (find_cache_entry(the_cache, params->entry_name) != NULL) {
529                 TRACE_OUT(register_cache_entry);
530                 return (-1);
531         }
532
533         if (the_cache->entries_size == the_cache->entries_capacity) {
534                 struct cache_entry_ **new_entries;
535                 size_t  new_capacity;
536
537                 new_capacity = the_cache->entries_capacity +
538                         ENTRIES_CAPACITY_STEP;
539                 new_entries = (struct cache_entry_ **)calloc(1,
540                         sizeof(struct cache_entry_ *) * new_capacity);
541                 assert(new_entries != NULL);
542
543                 memcpy(new_entries, the_cache->entries,
544                         sizeof(struct cache_entry_ *)
545                         * the_cache->entries_size);
546
547                 free(the_cache->entries);
548                 the_cache->entries = new_entries;
549         }
550
551         entry_name_size = strlen(params->entry_name) + 1;
552         switch (params->entry_type)
553         {
554         case CET_COMMON:
555                 new_common_entry = (struct cache_common_entry_ *)calloc(1,
556                         sizeof(struct cache_common_entry_));
557                 assert(new_common_entry != NULL);
558
559                 memcpy(&new_common_entry->common_params, params,
560                         sizeof(struct common_cache_entry_params));
561                 new_common_entry->params =
562                   (struct cache_entry_params *)&new_common_entry->common_params;
563
564                 new_common_entry->common_params.entry_name = (char *)calloc(1,
565                         entry_name_size);
566                 assert(new_common_entry->common_params.entry_name != NULL);
567                 strlcpy(new_common_entry->common_params.entry_name,
568                         params->entry_name, entry_name_size);
569                 new_common_entry->name =
570                         new_common_entry->common_params.entry_name;
571
572                 HASHTABLE_INIT(&(new_common_entry->items),
573                         struct cache_ht_item_data_, data,
574                         new_common_entry->common_params.cache_entries_size);
575
576                 if (new_common_entry->common_params.policy == CPT_FIFO)
577                         policies_size = 1;
578                 else
579                         policies_size = 2;
580
581                 new_common_entry->policies = (struct cache_policy_ **)calloc(1,
582                         sizeof(struct cache_policy_ *) * policies_size);
583                 assert(new_common_entry->policies != NULL);
584
585                 new_common_entry->policies_size = policies_size;
586                 new_common_entry->policies[0] = init_cache_fifo_policy();
587
588                 if (policies_size > 1) {
589                         switch (new_common_entry->common_params.policy) {
590                         case CPT_LRU:
591                                 new_common_entry->policies[1] =
592                                         init_cache_lru_policy();
593                         break;
594                         case CPT_LFU:
595                                 new_common_entry->policies[1] =
596                                         init_cache_lfu_policy();
597                         break;
598                         default:
599                         break;
600                         }
601                 }
602
603                 new_common_entry->get_time_func =
604                         the_cache->params.get_time_func;
605                 the_cache->entries[the_cache->entries_size++] =
606                         (struct cache_entry_ *)new_common_entry;
607                 break;
608         case CET_MULTIPART:
609                 new_mp_entry = (struct cache_mp_entry_ *)calloc(1,
610                         sizeof(struct cache_mp_entry_));
611                 assert(new_mp_entry != NULL);
612
613                 memcpy(&new_mp_entry->mp_params, params,
614                         sizeof(struct mp_cache_entry_params));
615                 new_mp_entry->params =
616                         (struct cache_entry_params *)&new_mp_entry->mp_params;
617
618                 new_mp_entry->mp_params.entry_name = (char *)calloc(1,
619                         entry_name_size);
620                 assert(new_mp_entry->mp_params.entry_name != NULL);
621                 strlcpy(new_mp_entry->mp_params.entry_name, params->entry_name,
622                         entry_name_size);
623                 new_mp_entry->name = new_mp_entry->mp_params.entry_name;
624
625                 TAILQ_INIT(&new_mp_entry->ws_head);
626                 TAILQ_INIT(&new_mp_entry->rs_head);
627
628                 new_mp_entry->get_time_func = the_cache->params.get_time_func;
629                 the_cache->entries[the_cache->entries_size++] =
630                         (struct cache_entry_ *)new_mp_entry;
631                 break;
632         }
633
634
635         qsort(the_cache->entries, the_cache->entries_size,
636                 sizeof(struct cache_entry_ *), entries_qsort_cmp_func);
637
638         TRACE_OUT(register_cache_entry);
639         return (0);
640 }
641
642 int
643 unregister_cache_entry(struct cache_ *the_cache, const char *entry_name)
644 {
645         struct cache_entry_ **del_ent;
646
647         TRACE_IN(unregister_cache_entry);
648         assert(the_cache != NULL);
649
650         del_ent = find_cache_entry_p(the_cache, entry_name);
651         if (del_ent != NULL) {
652                 destroy_cache_entry(*del_ent);
653                 --the_cache->entries_size;
654
655                 memmove(del_ent, del_ent + 1,
656                         (&(the_cache->entries[--the_cache->entries_size]) -
657                         del_ent) * sizeof(struct cache_entry_ *));
658
659                 TRACE_OUT(unregister_cache_entry);
660                 return (0);
661         } else {
662                 TRACE_OUT(unregister_cache_entry);
663                 return (-1);
664         }
665 }
666
667 struct cache_entry_ *
668 find_cache_entry(struct cache_ *the_cache, const char *entry_name)
669 {
670         struct cache_entry_ **result;
671
672         TRACE_IN(find_cache_entry);
673         result = find_cache_entry_p(the_cache, entry_name);
674
675         if (result == NULL) {
676                 TRACE_OUT(find_cache_entry);
677                 return (NULL);
678         } else {
679                 TRACE_OUT(find_cache_entry);
680                 return (*result);
681         }
682 }
683
684 /*
685  * Tries to read the element with the specified key from the cache. If the
686  * value_size is too small, it will be filled with the proper number, and
687  * the user will need to call cache_read again with the value buffer, that
688  * is large enough.
689  * Function returns 0 on success, -1 on error, and -2 if the value_size is too
690  * small.
691  */
692 int
693 cache_read(struct cache_entry_ *entry, const char *key, size_t key_size,
694         char *value, size_t *value_size)
695 {
696         struct cache_common_entry_      *common_entry;
697         struct cache_ht_item_data_      item_data, *find_res;
698         struct cache_ht_item_           *item;
699         hashtable_index_t       hash;
700         struct cache_policy_item_ *connected_item;
701
702         TRACE_IN(cache_read);
703         assert(entry != NULL);
704         assert(key != NULL);
705         assert(value_size != NULL);
706         assert(entry->params->entry_type == CET_COMMON);
707
708         common_entry = (struct cache_common_entry_ *)entry;
709
710         memset(&item_data, 0, sizeof(struct cache_ht_item_data_));
711         /* can't avoid the cast here */
712         item_data.key = (char *)key;
713         item_data.key_size = key_size;
714
715         hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &common_entry->items,
716                 &item_data);
717         assert(hash >= 0);
718         assert(hash < HASHTABLE_ENTRIES_COUNT(&common_entry->items));
719
720         item = HASHTABLE_GET_ENTRY(&(common_entry->items), hash);
721         find_res = HASHTABLE_ENTRY_FIND(cache_ht_, item, &item_data);
722         if (find_res == NULL) {
723                 TRACE_OUT(cache_read);
724                 return (-1);
725         }
726
727         if ((common_entry->common_params.max_lifetime.tv_sec != 0) ||
728                 (common_entry->common_params.max_lifetime.tv_usec != 0)) {
729
730                 if (find_res->fifo_policy_item->last_request_time.tv_sec -
731                         find_res->fifo_policy_item->creation_time.tv_sec >
732                         common_entry->common_params.max_lifetime.tv_sec) {
733
734                         free(find_res->key);
735                         free(find_res->value);
736
737                         connected_item =
738                             find_res->fifo_policy_item->connected_item;
739                         if (connected_item != NULL) {
740                                 common_entry->policies[1]->remove_item_func(
741                                         common_entry->policies[1],
742                                         connected_item);
743                                 common_entry->policies[1]->destroy_item_func(
744                                         connected_item);
745                         }
746
747                         common_entry->policies[0]->remove_item_func(
748                                 common_entry->policies[0],
749                                         find_res->fifo_policy_item);
750                         common_entry->policies[0]->destroy_item_func(
751                                 find_res->fifo_policy_item);
752
753                         HASHTABLE_ENTRY_REMOVE(cache_ht_, item, find_res);
754                         --common_entry->items_size;
755                 }
756         }
757
758         if ((*value_size < find_res->value_size) || (value == NULL)) {
759                 *value_size = find_res->value_size;
760                 TRACE_OUT(cache_read);
761                 return (-2);
762         }
763
764         *value_size = find_res->value_size;
765         memcpy(value, find_res->value, find_res->value_size);
766
767         ++find_res->fifo_policy_item->request_count;
768         common_entry->get_time_func(
769                 &find_res->fifo_policy_item->last_request_time);
770         common_entry->policies[0]->update_item_func(common_entry->policies[0],
771                 find_res->fifo_policy_item);
772
773         if (find_res->fifo_policy_item->connected_item != NULL) {
774                 connected_item = find_res->fifo_policy_item->connected_item;
775                 memcpy(&connected_item->last_request_time,
776                         &find_res->fifo_policy_item->last_request_time,
777                         sizeof(struct timeval));
778                 connected_item->request_count =
779                         find_res->fifo_policy_item->request_count;
780
781                 common_entry->policies[1]->update_item_func(
782                         common_entry->policies[1], connected_item);
783         }
784
785         TRACE_OUT(cache_read);
786         return (0);
787 }
788
789 /*
790  * Writes the value with the specified key into the cache entry.
791  * Functions returns 0 on success, and -1 on error.
792  */
793 int
794 cache_write(struct cache_entry_ *entry, const char *key, size_t key_size,
795         char const *value, size_t value_size)
796 {
797         struct cache_common_entry_      *common_entry;
798         struct cache_ht_item_data_      item_data, *find_res;
799         struct cache_ht_item_           *item;
800         hashtable_index_t       hash;
801
802         struct cache_policy_            *policy, *connected_policy;
803         struct cache_policy_item_       *policy_item;
804         struct cache_policy_item_       *connected_policy_item;
805
806         TRACE_IN(cache_write);
807         assert(entry != NULL);
808         assert(key != NULL);
809         assert(value != NULL);
810         assert(entry->params->entry_type == CET_COMMON);
811
812         common_entry = (struct cache_common_entry_ *)entry;
813
814         memset(&item_data, 0, sizeof(struct cache_ht_item_data_));
815         /* can't avoid the cast here */
816         item_data.key = (char *)key;
817         item_data.key_size = key_size;
818
819         hash = HASHTABLE_CALCULATE_HASH(cache_ht_, &common_entry->items,
820                 &item_data);
821         assert(hash >= 0);
822         assert(hash < HASHTABLE_ENTRIES_COUNT(&common_entry->items));
823
824         item = HASHTABLE_GET_ENTRY(&(common_entry->items), hash);
825         find_res = HASHTABLE_ENTRY_FIND(cache_ht_, item, &item_data);
826         if (find_res != NULL) {
827                 TRACE_OUT(cache_write);
828                 return (-1);
829         }
830
831         item_data.key = (char *)malloc(key_size);
832         memcpy(item_data.key, key, key_size);
833
834         item_data.value = (char *)malloc(value_size);
835         assert(item_data.value != NULL);
836
837         memcpy(item_data.value, value, value_size);
838         item_data.value_size = value_size;
839
840         policy_item = common_entry->policies[0]->create_item_func();
841         policy_item->key = item_data.key;
842         policy_item->key_size = item_data.key_size;
843         common_entry->get_time_func(&policy_item->creation_time);
844
845         if (common_entry->policies_size > 1) {
846                 connected_policy_item =
847                         common_entry->policies[1]->create_item_func();
848                 memcpy(&connected_policy_item->creation_time,
849                         &policy_item->creation_time,
850                         sizeof(struct timeval));
851                 connected_policy_item->key = policy_item->key;
852                 connected_policy_item->key_size = policy_item->key_size;
853
854                 connected_policy_item->connected_item = policy_item;
855                 policy_item->connected_item = connected_policy_item;
856         }
857
858         item_data.fifo_policy_item = policy_item;
859
860         common_entry->policies[0]->add_item_func(common_entry->policies[0],
861                 policy_item);
862         if (common_entry->policies_size > 1)
863                 common_entry->policies[1]->add_item_func(
864                         common_entry->policies[1], connected_policy_item);
865
866         HASHTABLE_ENTRY_STORE(cache_ht_, item, &item_data);
867         ++common_entry->items_size;
868
869         if ((common_entry->common_params.max_elemsize != 0) &&
870                 (common_entry->items_size >
871                 common_entry->common_params.max_elemsize)) {
872                 if (common_entry->policies_size > 1) {
873                         policy = common_entry->policies[1];
874                         connected_policy = common_entry->policies[0];
875                 } else {
876                         policy = common_entry->policies[0];
877                         connected_policy = NULL;
878                 }
879
880                 flush_cache_policy(common_entry, policy, connected_policy,
881                         cache_elemsize_common_continue_func);
882         }
883
884         TRACE_OUT(cache_write);
885         return (0);
886 }
887
888 /*
889  * Initializes the write session for the specified multipart entry. This
890  * session then should be filled with data either committed or abandoned by
891  * using close_cache_mp_write_session or abandon_cache_mp_write_session
892  * respectively.
893  * Returns NULL on errors (when there are too many opened write sessions for
894  * the entry).
895  */
896 struct cache_mp_write_session_ *
897 open_cache_mp_write_session(struct cache_entry_ *entry)
898 {
899         struct cache_mp_entry_  *mp_entry;
900         struct cache_mp_write_session_  *retval;
901
902         TRACE_IN(open_cache_mp_write_session);
903         assert(entry != NULL);
904         assert(entry->params->entry_type == CET_MULTIPART);
905         mp_entry = (struct cache_mp_entry_ *)entry;
906
907         if ((mp_entry->mp_params.max_sessions > 0) &&
908                 (mp_entry->ws_size == mp_entry->mp_params.max_sessions)) {
909                 TRACE_OUT(open_cache_mp_write_session);
910                 return (NULL);
911         }
912
913         retval = (struct cache_mp_write_session_ *)calloc(1,
914                 sizeof(struct cache_mp_write_session_));
915         assert(retval != NULL);
916
917         TAILQ_INIT(&retval->items);
918         retval->parent_entry = mp_entry;
919
920         TAILQ_INSERT_HEAD(&mp_entry->ws_head, retval, entries);
921         ++mp_entry->ws_size;
922
923         TRACE_OUT(open_cache_mp_write_session);
924         return (retval);
925 }
926
927 /*
928  * Writes data to the specified session. Return 0 on success and -1 on errors
929  * (when write session size limit is exceeded).
930  */
931 int
932 cache_mp_write(struct cache_mp_write_session_ *ws, char *data,
933         size_t data_size)
934 {
935         struct cache_mp_data_item_      *new_item;
936
937         TRACE_IN(cache_mp_write);
938         assert(ws != NULL);
939         assert(ws->parent_entry != NULL);
940         assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
941
942         if ((ws->parent_entry->mp_params.max_elemsize > 0) &&
943                 (ws->parent_entry->mp_params.max_elemsize == ws->items_size)) {
944                 TRACE_OUT(cache_mp_write);
945                 return (-1);
946         }
947
948         new_item = (struct cache_mp_data_item_ *)calloc(1,
949                 sizeof(struct cache_mp_data_item_));
950         assert(new_item != NULL);
951
952         new_item->value = (char *)malloc(data_size);
953         assert(new_item->value != NULL);
954         memcpy(new_item->value, data, data_size);
955         new_item->value_size = data_size;
956
957         TAILQ_INSERT_TAIL(&ws->items, new_item, entries);
958         ++ws->items_size;
959
960         TRACE_OUT(cache_mp_write);
961         return (0);
962 }
963
964 /*
965  * Abandons the write session and frees all the connected resources.
966  */
967 void
968 abandon_cache_mp_write_session(struct cache_mp_write_session_ *ws)
969 {
970
971         TRACE_IN(abandon_cache_mp_write_session);
972         assert(ws != NULL);
973         assert(ws->parent_entry != NULL);
974         assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
975
976         TAILQ_REMOVE(&ws->parent_entry->ws_head, ws, entries);
977         --ws->parent_entry->ws_size;
978
979         destroy_cache_mp_write_session(ws);
980         TRACE_OUT(abandon_cache_mp_write_session);
981 }
982
983 /*
984  * Commits the session to the entry, for which it was created.
985  */
986 void
987 close_cache_mp_write_session(struct cache_mp_write_session_ *ws)
988 {
989
990         TRACE_IN(close_cache_mp_write_session);
991         assert(ws != NULL);
992         assert(ws->parent_entry != NULL);
993         assert(ws->parent_entry->params->entry_type == CET_MULTIPART);
994
995         TAILQ_REMOVE(&ws->parent_entry->ws_head, ws, entries);
996         --ws->parent_entry->ws_size;
997
998         if (ws->parent_entry->completed_write_session == NULL) {
999                 /*
1000                  * If there is no completed session yet, this will be the one
1001                  */
1002                 ws->parent_entry->get_time_func(
1003                         &ws->parent_entry->creation_time);
1004                 ws->parent_entry->completed_write_session = ws;
1005         } else {
1006                 /*
1007                  * If there is a completed session, then we'll save our session
1008                  * as a pending session. If there is already a pending session,
1009                  * it would be destroyed.
1010                  */
1011                 if (ws->parent_entry->pending_write_session != NULL)
1012                         destroy_cache_mp_write_session(
1013                                 ws->parent_entry->pending_write_session);
1014
1015                 ws->parent_entry->pending_write_session = ws;
1016         }
1017         TRACE_OUT(close_cache_mp_write_session);
1018 }
1019
1020 /*
1021  * Opens read session for the specified entry. Returns NULL on errors (when
1022  * there are no data in the entry, or the data are obsolete).
1023  */
1024 struct cache_mp_read_session_ *
1025 open_cache_mp_read_session(struct cache_entry_ *entry)
1026 {
1027         struct cache_mp_entry_                  *mp_entry;
1028         struct cache_mp_read_session_   *retval;
1029
1030         TRACE_IN(open_cache_mp_read_session);
1031         assert(entry != NULL);
1032         assert(entry->params->entry_type == CET_MULTIPART);
1033         mp_entry = (struct cache_mp_entry_ *)entry;
1034
1035         if (mp_entry->completed_write_session == NULL) {
1036                 TRACE_OUT(open_cache_mp_read_session);
1037                 return (NULL);
1038         }
1039
1040         if ((mp_entry->mp_params.max_lifetime.tv_sec != 0)
1041                 || (mp_entry->mp_params.max_lifetime.tv_usec != 0)) {
1042                 if (mp_entry->last_request_time.tv_sec -
1043                         mp_entry->last_request_time.tv_sec >
1044                         mp_entry->mp_params.max_lifetime.tv_sec) {
1045                         flush_cache_entry(entry);
1046                         TRACE_OUT(open_cache_mp_read_session);
1047                         return (NULL);
1048                 }
1049         }
1050
1051         retval = (struct cache_mp_read_session_ *)calloc(1,
1052                 sizeof(struct cache_mp_read_session_));
1053         assert(retval != NULL);
1054
1055         retval->parent_entry = mp_entry;
1056         retval->current_item = TAILQ_FIRST(
1057                 &mp_entry->completed_write_session->items);
1058
1059         TAILQ_INSERT_HEAD(&mp_entry->rs_head, retval, entries);
1060         ++mp_entry->rs_size;
1061
1062         mp_entry->get_time_func(&mp_entry->last_request_time);
1063         TRACE_OUT(open_cache_mp_read_session);
1064         return (retval);
1065 }
1066
1067 /*
1068  * Reads the data from the read session - step by step.
1069  * Returns 0 on success, -1 on error (when there are no more data), and -2 if
1070  * the data_size is too small.  In the last case, data_size would be filled
1071  * the proper value.
1072  */
1073 int
1074 cache_mp_read(struct cache_mp_read_session_ *rs, char *data, size_t *data_size)
1075 {
1076
1077         TRACE_IN(cache_mp_read);
1078         assert(rs != NULL);
1079
1080         if (rs->current_item == NULL) {
1081                 TRACE_OUT(cache_mp_read);
1082                 return (-1);
1083         }
1084
1085         if (rs->current_item->value_size > *data_size) {
1086                 *data_size = rs->current_item->value_size;
1087                 if (data == NULL) {
1088                         TRACE_OUT(cache_mp_read);
1089                         return (0);
1090                 }
1091
1092                 TRACE_OUT(cache_mp_read);
1093                 return (-2);
1094         }
1095
1096         *data_size = rs->current_item->value_size;
1097         memcpy(data, rs->current_item->value, rs->current_item->value_size);
1098         rs->current_item = TAILQ_NEXT(rs->current_item, entries);
1099
1100         TRACE_OUT(cache_mp_read);
1101         return (0);
1102 }
1103
1104 /*
1105  * Closes the read session. If there are no more read sessions and there is
1106  * a pending write session, it will be committed and old
1107  * completed_write_session will be destroyed.
1108  */
1109 void
1110 close_cache_mp_read_session(struct cache_mp_read_session_ *rs)
1111 {
1112
1113         TRACE_IN(close_cache_mp_read_session);
1114         assert(rs != NULL);
1115         assert(rs->parent_entry != NULL);
1116
1117         TAILQ_REMOVE(&rs->parent_entry->rs_head, rs, entries);
1118         --rs->parent_entry->rs_size;
1119
1120         if ((rs->parent_entry->rs_size == 0) &&
1121                 (rs->parent_entry->pending_write_session != NULL)) {
1122                 destroy_cache_mp_write_session(
1123                         rs->parent_entry->completed_write_session);
1124                 rs->parent_entry->completed_write_session =
1125                         rs->parent_entry->pending_write_session;
1126                 rs->parent_entry->pending_write_session = NULL;
1127         }
1128
1129         destroy_cache_mp_read_session(rs);
1130         TRACE_OUT(close_cache_mp_read_session);
1131 }
1132
1133 int
1134 transform_cache_entry(struct cache_entry_ *entry,
1135         enum cache_transformation_t transformation)
1136 {
1137
1138         TRACE_IN(transform_cache_entry);
1139         switch (transformation) {
1140         case CTT_CLEAR:
1141                 clear_cache_entry(entry);
1142                 TRACE_OUT(transform_cache_entry);
1143                 return (0);
1144         case CTT_FLUSH:
1145                 flush_cache_entry(entry);
1146                 TRACE_OUT(transform_cache_entry);
1147                 return (0);
1148         default:
1149                 TRACE_OUT(transform_cache_entry);
1150                 return (-1);
1151         }
1152 }
1153
1154 int
1155 transform_cache_entry_part(struct cache_entry_ *entry,
1156         enum cache_transformation_t transformation, const char *key_part,
1157         size_t key_part_size, enum part_position_t part_position)
1158 {
1159         struct cache_common_entry_ *common_entry;
1160         struct cache_ht_item_ *ht_item;
1161         struct cache_ht_item_data_ *ht_item_data, ht_key;
1162
1163         struct cache_policy_item_ *item, *connected_item;
1164
1165         TRACE_IN(transform_cache_entry_part);
1166         if (entry->params->entry_type != CET_COMMON) {
1167                 TRACE_OUT(transform_cache_entry_part);
1168                 return (-1);
1169         }
1170
1171         if (transformation != CTT_CLEAR) {
1172                 TRACE_OUT(transform_cache_entry_part);
1173                 return (-1);
1174         }
1175
1176         memset(&ht_key, 0, sizeof(struct cache_ht_item_data_));
1177         ht_key.key = (char *)key_part;  /* can't avoid casting here */
1178         ht_key.key_size = key_part_size;
1179
1180         common_entry = (struct cache_common_entry_ *)entry;
1181         HASHTABLE_FOREACH(&(common_entry->items), ht_item) {
1182                 do {
1183                         ht_item_data = HASHTABLE_ENTRY_FIND_SPECIAL(cache_ht_,
1184                                 ht_item, &ht_key,
1185                                 ht_items_fixed_size_left_cmp_func);
1186
1187                         if (ht_item_data != NULL) {
1188                             item = ht_item_data->fifo_policy_item;
1189                             connected_item = item->connected_item;
1190
1191                             common_entry->policies[0]->remove_item_func(
1192                                 common_entry->policies[0],
1193                                 item);
1194
1195                             free(ht_item_data->key);
1196                             free(ht_item_data->value);
1197                             HASHTABLE_ENTRY_REMOVE(cache_ht_, ht_item,
1198                                 ht_item_data);
1199                             --common_entry->items_size;
1200
1201                             common_entry->policies[0]->destroy_item_func(
1202                                 item);
1203                             if (common_entry->policies_size == 2) {
1204                                 common_entry->policies[1]->remove_item_func(
1205                                     common_entry->policies[1],
1206                                     connected_item);
1207                                 common_entry->policies[1]->destroy_item_func(
1208                                     connected_item);
1209                             }
1210                         }
1211                 } while (ht_item_data != NULL);
1212         }
1213
1214         TRACE_OUT(transform_cache_entry_part);
1215         return (0);
1216 }