1 #include "common.h"
2 #include "c-icap.h"
3 #include "commands.h"
4 #include "debug.h"
5 #include "cache.h"
6 #include "module.h"
7 #include "proc_mutex.h"
8 #include "shared_mem.h"
9 #include <assert.h>
10 
11 static int init_shared_cache(struct ci_server_conf *server_conf);
12 static void release_shared_cache();
13 
14 CI_DECLARE_MOD_DATA common_module_t module = {
15     "shared_cache",
16     init_shared_cache,
17     NULL,
18     release_shared_cache,
19     NULL,
20 };
21 
22 struct ci_cache_type ci_shared_cache;
init_shared_cache(struct ci_server_conf * server_conf)23 static int init_shared_cache(struct ci_server_conf *server_conf)
24 {
25     ci_cache_type_register(&ci_shared_cache);
26     return 1;
27 }
28 
release_shared_cache()29 static void release_shared_cache()
30 {
31 }
32 
33 int ci_shared_cache_init(struct ci_cache *cache, const char *name);
34 const void *ci_shared_cache_search(struct ci_cache *cache, const void *key, void **val, void *data, void *(*dup_from_cache)(const void *stored_val, size_t stored_val_size, void *data));
35 int ci_shared_cache_update(struct ci_cache *cache, const void *key, const void *val, size_t val_size, void *(*copy_to_cache)(void *buf, const void *val, size_t buf_size));
36 void ci_shared_cache_destroy(struct ci_cache *cache);
37 
38 struct ci_cache_type ci_shared_cache = {
39     ci_shared_cache_init,
40     ci_shared_cache_search,
41     ci_shared_cache_update,
42     ci_shared_cache_destroy,
43     "shared"
44 };
45 
46 /*Should be power of 2 and equal or less than 64*/
47 #define CACHE_PAGES 4
48 
49 struct shared_cache_stats {
50     int cache_users;
51     struct page_stats {
52         int64_t hits;
53         int64_t searches;
54         int64_t updates;
55         int64_t update_hits;
56     } page[CACHE_PAGES];
57 };
58 
59 struct shared_cache_data {
60     void *mem_ptr;
61     void *slots;
62     ci_shared_mem_id_t id;
63     size_t max_hash;
64     size_t entry_size;
65     size_t shared_mem_size;
66     int entries;
67     int pages;
68     int page_size;
69     int page_shift_op;
70     struct shared_cache_stats *stats;
71     ci_proc_mutex_t cache_mutex;
72     ci_proc_mutex_t mutex[CACHE_PAGES];
73 };
74 
75 struct shared_cache_slot {
76     unsigned int hash;
77     time_t expires;
78     size_t key_size;
79     size_t value_size;
80     unsigned char bytes[];
81 };
82 
83 unsigned int
ci_hash_compute2(unsigned long hash_max_value,const void * data,unsigned int len)84 ci_hash_compute2(unsigned long hash_max_value, const void *data, unsigned int len)
85 {
86     const unsigned char *s = (const unsigned char *)(data);
87     unsigned int n = 0;
88     unsigned int j = 0;
89     unsigned int i = 0;
90     while ((s - (const unsigned char *)data) < len) {
91         ++j;
92         n ^= 271 * *s;
93         ++s;
94     }
95     i = n ^ (j * 271);
96     return i % hash_max_value;
97 }
98 
ci_shared_mem_print_id(char * buf,size_t size,ci_shared_mem_id_t * id)99 const char *ci_shared_mem_print_id(char *buf, size_t size, ci_shared_mem_id_t *id)
100 {
101     if (buf) {
102         if (id->scheme)
103             id->scheme->shared_mem_print_info(id, buf, size);
104         else
105             *buf = '\0';
106 
107     }
108     return buf;
109 }
110 
command_attach_shared_mem(const char * name,int type,void * data)111 void command_attach_shared_mem(const char *name, int type, void *data)
112 {
113     char buf[128];
114     struct shared_cache_data *shared_cache = (struct shared_cache_data *)data;
115     shared_cache->mem_ptr = ci_shared_mem_attach(&shared_cache->id);
116     shared_cache->stats = (struct shared_cache_stats *)shared_cache->mem_ptr;
117     shared_cache->slots = (void *)(shared_cache->mem_ptr + sizeof(struct shared_cache_stats));
118     ci_debug_printf(3, "Shared cache id:'%s' attached on address %p\n", ci_shared_mem_print_id(buf, sizeof(buf), &shared_cache->id), shared_cache->mem_ptr);
119     ci_proc_mutex_lock(&(shared_cache->cache_mutex));
120     ++shared_cache->stats->cache_users;
121     ci_proc_mutex_unlock(&(shared_cache->cache_mutex));
122 }
123 
ci_shared_cache_init(struct ci_cache * cache,const char * name)124 int ci_shared_cache_init(struct ci_cache *cache, const char *name)
125 {
126     unsigned int next_hash = 63;
127     unsigned int final_max_hash = 63;
128     int i;
129     struct shared_cache_data *data;
130     data = (struct shared_cache_data *)malloc(sizeof(struct shared_cache_data));
131     data->entry_size = _CI_ALIGN(cache->max_object_size > 0 ? cache->max_object_size : 1);
132     data->entries = _CI_ALIGN(cache->mem_size) / data->entry_size;
133 
134     while (next_hash < data->entries) {
135         final_max_hash = next_hash;
136         next_hash++;
137         next_hash = (next_hash << 1) -1;
138     }
139 
140     data->max_hash = final_max_hash;
141     data->entries = final_max_hash + 1;
142     data->shared_mem_size = sizeof(struct shared_cache_stats) + data->entries * data->entry_size;
143 
144     data->mem_ptr = ci_shared_mem_create(&data->id, name, data->shared_mem_size);
145     if (!data->mem_ptr) {
146         free(data);
147         ci_debug_printf(1, "Error allocating shared mem for %s cache\n", name);
148         return 0;
149     }
150     data->stats = (struct shared_cache_stats *)data->mem_ptr;
151     data->slots = data->mem_ptr + sizeof(struct shared_cache_stats);
152     memset(data->stats, 0, sizeof(struct shared_cache_stats));
153     data->stats->cache_users = 1;
154 
155     /*TODO: check for error*/
156     for (i = 0; i < CACHE_PAGES; ++i) {
157         ci_proc_mutex_init(&(data->mutex[i]), name);
158     }
159     ci_proc_mutex_init(&(data->cache_mutex), name);
160 
161     data->page_size = data->entries / CACHE_PAGES;
162     /* CACHE_PAGES can not be bigger than 64, the minimum entries value*/
163     assert(data->entries % data->page_size == 0);
164     data->pages = CACHE_PAGES;
165     /* The pages and page_size should be a power of 2*/
166     assert((data->pages & (data->pages - 1)) == 0);
167     assert((data->page_size & (data->page_size - 1)) == 0);
168     for (data->page_shift_op = 0; ((data->page_size >> data->page_shift_op) & 0x1) ==0 && data->page_shift_op < 64; ++data->page_shift_op );
169     assert(data->page_shift_op < 64);
170 
171     ci_debug_printf(1, "Shared mem %s created\nMax shared memory: %u (of the %u requested), max entry size: %u, maximum entries: %u\n", name, (unsigned int)data->shared_mem_size, (unsigned int)cache->mem_size, (unsigned int)data->entry_size, data->entries);
172 
173     cache->cache_data = data;
174     ci_command_register_action("shared_cache_attach_cmd", CHILD_START_CMD, data, command_attach_shared_mem);
175     return 1;
176 }
177 
rw_lock_page(struct shared_cache_data * cache_data,int pos)178 int rw_lock_page(struct shared_cache_data *cache_data, int pos)
179 {
180     ci_proc_mutex_lock(&cache_data->mutex[pos >> cache_data->page_shift_op]);
181     return 1;
182 }
183 
rd_lock_page(struct shared_cache_data * cache_data,int pos)184 int rd_lock_page(struct shared_cache_data *cache_data, int pos)
185 {
186     ci_proc_mutex_lock(&cache_data->mutex[pos >> cache_data->page_shift_op]);
187     return 1;
188 }
189 
unlock_page(struct shared_cache_data * cache_data,int pos)190 void unlock_page(struct shared_cache_data *cache_data, int pos)
191 {
192     ci_proc_mutex_unlock(&cache_data->mutex[pos >> cache_data->page_shift_op]);
193 }
194 
ci_internal_time()195 time_t ci_internal_time()
196 {
197     return time(NULL);
198 }
199 
ci_shared_cache_search(struct ci_cache * cache,const void * key,void ** val,void * user_data,void * (* dup_from_cache)(const void * stored_val,size_t stored_val_size,void * user_data))200 const void *ci_shared_cache_search(struct ci_cache *cache, const void *key, void **val, void *user_data, void *(*dup_from_cache)(const void *stored_val, size_t stored_val_size, void *user_data))
201 {
202     time_t current_time;
203     const void *cache_key, *cache_val;
204     struct shared_cache_data *cache_data = cache->cache_data;
205     unsigned int hash = ci_hash_compute(cache_data->max_hash, key, cache->key_ops->size(key));
206     *val = NULL;
207     if (hash >= cache_data->entries)
208         hash = cache_data->entries -1;
209 
210     if (!rd_lock_page(cache_data, hash))
211         return NULL;
212     unsigned int page = (hash >> cache_data->page_shift_op);
213     ++cache_data->stats->page[page].searches;
214     unsigned int pos;
215     int done;
216     for (pos = hash, done = 0, cache_key = NULL;
217             !cache_key && !done && ((pos >> cache_data->page_shift_op) == page);
218             ++pos) {
219         struct shared_cache_slot *slot = cache_data->slots + (pos * cache_data->entry_size);
220         cache_key = (const void *)slot->bytes;
221         cache_val = (const void *)(&slot->bytes[slot->key_size + 1]);
222 
223         if (slot->hash != hash) {
224             cache_key = NULL;
225             done = 1;
226         } else if (cache->key_ops->compare(cache_key, key) == 0) {
227             current_time = ci_internal_time();
228             if (slot->expires < current_time)
229                 cache_key = NULL;
230             else if (slot->value_size) {
231                 if (dup_from_cache)
232                     *val = (*dup_from_cache)(cache_val, slot->value_size, user_data);
233                 else {
234                     if ((*val = ci_buffer_alloc(slot->value_size)))
235                         memcpy(*val, cache_val, slot->value_size);
236                 }
237             }
238         } else
239             cache_key = NULL;
240     }
241 
242     if (cache_key)
243         ++cache_data->stats->page[page].hits;
244 
245     unlock_page(cache_data, hash);
246     return cache_key;
247 }
248 
ci_shared_cache_update(struct ci_cache * cache,const void * key,const void * val,size_t val_size,void * (* copy_to_cache)(void * buf,const void * val,size_t buf_size))249 int ci_shared_cache_update(struct ci_cache *cache, const void *key, const void *val, size_t val_size, void *(*copy_to_cache)(void *buf, const void *val, size_t buf_size))
250 {
251     time_t expire_time, current_time;
252     void *cache_key, *cache_val;
253     size_t key_size;
254     int ret, can_updated;
255     struct shared_cache_data *cache_data = cache->cache_data;
256     key_size = cache->key_ops->size(key);
257     if ((key_size + val_size + sizeof(struct shared_cache_slot)) > cache_data->entry_size) {
258         /*Does not fit to a cache_data slot.*/
259         return 0;
260     }
261 
262     unsigned int hash = ci_hash_compute(cache_data->max_hash, key, key_size);
263     if (hash >= cache_data->entries)
264         hash = cache_data->entries -1;
265 
266     current_time = ci_internal_time();
267     expire_time = current_time + cache->ttl;
268 
269     if (!rw_lock_page(cache_data, hash))
270         return 0; /*not able to obtain a rw lock*/
271 
272     unsigned int page = (hash >> cache_data->page_shift_op);
273     ++cache_data->stats->page[page].updates;
274 
275     unsigned int pos;
276     int done;
277     for (pos = hash, ret = 0, done = 0;
278             ret == 0 && !done && ((hash >> cache_data->page_shift_op) == (pos >> cache_data->page_shift_op));
279             ++pos) {
280         struct shared_cache_slot *slot = cache_data->slots + (pos * cache_data->entry_size);
281 
282         cache_key = (void *)slot->bytes;
283         can_updated = 0;
284         if (slot->hash < hash) {
285             can_updated = 1;
286         } else if (cache->key_ops->compare(cache_key, key) == 0) {
287             /*we are updating key with a new value*/
288             can_updated = 1;
289         } else if (slot->expires < current_time + cache->ttl) {
290             can_updated = 1;
291         } else if (pos == hash && slot->expires < (current_time + (cache->ttl / 2))) {
292             /*entries on pos == hash which are near to expire*/
293             can_updated = 1;
294         } else if (pos != hash && slot->hash == pos) {
295             /*entry is not expired, and it is not on a continues block we can use  */
296             done = 1;
297         }
298         if (can_updated) {
299             slot->hash = pos;
300             slot->expires = expire_time;
301             slot->key_size = key_size;
302             slot->value_size = val_size;
303             memcpy(cache_key, key, key_size);
304             cache_val = (void *)(&slot->bytes[slot->key_size + 1]);
305             if (copy_to_cache)
306                 copy_to_cache(cache_val, val, slot->value_size);
307             else
308                 memcpy(cache_val, val, slot->value_size);
309             ret = 1;
310             ++cache_data->stats->page[page].update_hits;
311         } else
312             ret = 0;
313     }
314 
315     unlock_page(cache_data, hash);
316     return ret;
317 }
318 
ci_shared_cache_destroy(struct ci_cache * cache)319 void ci_shared_cache_destroy(struct ci_cache *cache)
320 {
321     int i, users;
322     uint64_t updates, update_hits, searches, hits;
323     struct shared_cache_data *data = cache->cache_data;
324     ci_proc_mutex_lock(&data->cache_mutex);
325     users = --data->stats->cache_users;
326     ci_proc_mutex_unlock(&data->cache_mutex);
327     if (users == 0) {
328         updates = update_hits = searches = hits = 0;
329         for (i = 0; i < CACHE_PAGES; ++i) {
330             updates += data->stats->page[i].updates;
331             update_hits += data->stats->page[i].update_hits;
332             searches += data->stats->page[i].searches;
333             hits += data->stats->page[i].hits;
334         }
335         ci_debug_printf(3, "Last user, the cache will be destroyed\n");
336         ci_debug_printf(3, "Cache updates: %" PRIu64 ", update hits:%" PRIu64 ", searches: %" PRIu64 ", hits: %" PRIu64 "\n",
337                         updates, update_hits, searches, hits
338                        );
339         ci_shared_mem_destroy(&data->id);
340         ci_proc_mutex_destroy(&data->cache_mutex);
341         for (i = 0; i < CACHE_PAGES; ++i) {
342             ci_proc_mutex_destroy(&data->mutex[i]);
343         }
344     } else
345         ci_shared_mem_detach(&data->id);
346 }
347 
348