d2dbb07601e6c459fa0ef60d69e449ec0fd4f8bf
[olsrd.git] / src / olsr_cookie.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 #include "olsr.h"
43 #include "defs.h"
44 #include "olsr_cookie.h"
45 #include "olsr_logging.h"
46 #include "common/list.h"
47
48 #include <assert.h>
49 #include <errno.h>
50 #include <stdlib.h>
51
52 struct avl_tree olsr_cookie_tree;
53
54 static inline size_t calc_aligned_size(size_t size) {
55   static const size_t add = sizeof(size_t) * 2 - 1;
56   static const size_t mask = ~(sizeof(size_t)*2 - 1);
57
58   return (size + add) & mask;
59 }
60
61 void olsr_cookie_init(void) {
62   /* check size of memory prefix */
63   assert (sizeof(struct olsr_memory_prefix)
64       == calc_aligned_size(sizeof(struct olsr_memory_prefix)));
65
66   avl_init(&olsr_cookie_tree, &avl_comp_strcasecmp, false, NULL);
67 }
68
69 /*
70  * Allocate a cookie for the next available cookie id.
71  */
72 struct olsr_cookie_info *
73 olsr_create_memcookie(const char *cookie_name, size_t size)
74 {
75   struct olsr_cookie_info *ci;
76
77   assert (cookie_name);
78   assert (size > 9);
79
80   ci = olsr_malloc(sizeof(struct olsr_cookie_info), "memory cookie");
81
82   /* Now populate the cookie info */
83   ci->ci_name = olsr_strdup(cookie_name);
84   ci->ci_node.key = ci->ci_name;
85   ci->ci_size = size;
86   ci->ci_custom_offset = sizeof(struct olsr_memory_prefix) + calc_aligned_size(size);
87   ci->ci_min_free_count = COOKIE_FREE_LIST_THRESHOLD;
88
89   /* no custom data at this point */
90   ci->ci_total_size = ci->ci_custom_offset;
91
92   /* Init the free list */
93   list_init_head(&ci->ci_free_list);
94   list_init_head(&ci->ci_used_list);
95   list_init_head(&ci->ci_custom_list);
96
97   avl_insert(&olsr_cookie_tree, &ci->ci_node);
98   return ci;
99 }
100
101 /*
102  * Free a cookie that is no longer being used.
103  */
104 void
105 olsr_cleanup_memcookie(struct olsr_cookie_info *ci)
106 {
107   struct olsr_memory_prefix *memory_entity;
108   struct list_iterator iterator;
109
110   /* remove from tree */
111   avl_delete(&olsr_cookie_tree, &ci->ci_node);
112
113   /* Free name */
114   free(ci->ci_name);
115
116   /* Flush all the memory on the free list */
117   /*
118    * First make all items accessible,
119    * such that valgrind does not complain at shutdown.
120    */
121
122   /* remove all free memory blocks */
123   OLSR_FOR_ALL_FREE_MEM(ci, memory_entity, iterator) {
124     free(memory_entity);
125   }
126
127   /* free all used memory blocks */
128   OLSR_FOR_ALL_USED_MEM(ci, memory_entity, iterator) {
129     free(memory_entity->custom);
130     free(memory_entity);
131   }
132
133   free(ci);
134 }
135
136 /*
137  * Flush all cookies. This is really only called upon shutdown.
138  */
139 void
140 olsr_cookie_cleanup(void)
141 {
142   struct olsr_cookie_info *info;
143   struct list_iterator iterator;
144
145   /*
146    * Walk the full index range and kill 'em all.
147    */
148   OLSR_FOR_ALL_COOKIES(info, iterator) {
149     olsr_cleanup_memcookie(info);
150   }
151 }
152
153 /*
154  * Set if a returned memory block shall be cleared after returning to
155  * the free pool. This is only allowed for memory cookies.
156  */
157 void
158 olsr_cookie_set_min_free(struct olsr_cookie_info *ci, uint32_t min_free)
159 {
160   ci->ci_min_free_count = min_free;
161 }
162
163
164 /*
165  * Increment usage state for a given cookie.
166  */
167 static inline void
168 olsr_cookie_usage_incr(struct olsr_cookie_info *ci)
169 {
170   ci->ci_usage++;
171   ci->ci_changes++;
172 }
173
174 /*
175  * Decrement usage state for a given cookie.
176  */
177 static inline void
178 olsr_cookie_usage_decr(struct olsr_cookie_info *ci)
179 {
180   ci->ci_usage--;
181   ci->ci_changes++;
182 }
183
184 /*
185  * Allocate a fixed amount of memory based on a passed in cookie type.
186  */
187 void *
188 olsr_cookie_malloc(struct olsr_cookie_info *ci)
189 {
190   struct olsr_memory_prefix *mem;
191   struct olsr_cookie_custom *custom;
192   struct list_iterator iterator;
193
194 #if !defined REMOVE_LOG_DEBUG
195   bool reuse = false;
196 #endif
197
198   /*
199    * Check first if we have reusable memory.
200    */
201   if (list_is_empty(&ci->ci_free_list)) {
202     /*
203      * No reusable memory block on the free_list.
204      * Allocate a fresh one.
205      */
206     mem = olsr_malloc(ci->ci_total_size, ci->ci_name);
207   } else {
208     /*
209      * There is a memory block on the free list.
210      * Carve it out of the list, and clean.
211      */
212     mem = list_first_element(&ci->ci_free_list, mem, node);
213     list_remove(&mem->node);
214
215     memset(mem, 0, ci->ci_total_size);
216
217     ci->ci_free_list_usage--;
218 #if !defined REMOVE_LOG_DEBUG
219     reuse = true;
220 #endif
221   }
222
223   /* add to used list */
224   list_add_tail(&ci->ci_used_list, &mem->node);
225
226   /* handle custom initialization */
227   if (!list_is_empty(&ci->ci_custom_list)) {
228     mem->custom = ((uint8_t *)mem) + ci->ci_custom_offset;
229
230     /* call up custom init functions */
231     OLSR_FOR_ALL_CUSTOM_MEM(ci, custom, iterator) {
232       if (custom->init) {
233         custom->init(ci, mem + 1, mem->custom + custom->offset);
234       }
235     }
236   }
237
238   /* Stats keeping */
239   olsr_cookie_usage_incr(ci);
240
241   OLSR_DEBUG(LOG_COOKIE, "MEMORY: alloc %s, %p, %lu bytes%s\n",
242              ci->ci_name, mem + 1, (unsigned long)ci->ci_size, reuse ? ", reuse" : "");
243   return mem + 1;
244 }
245
246 /*
247  * Free a memory block owned by a given cookie.
248  * Run some corruption checks.
249  */
250 void
251 olsr_cookie_free(struct olsr_cookie_info *ci, void *ptr)
252 {
253   struct olsr_memory_prefix *mem;
254   struct olsr_cookie_custom *custom;
255   struct list_iterator iterator;
256 #if !defined REMOVE_LOG_DEBUG
257   bool reuse = false;
258 #endif
259
260   /* calculate pointer to memory prefix */
261   mem = ptr;
262   mem--;
263
264   /* call up custom cleanup */
265   OLSR_FOR_ALL_CUSTOM_MEM(ci, custom, iterator) {
266     if (custom->cleanup) {
267       custom->cleanup(ci, ptr, mem->custom + custom->offset);
268     }
269   }
270
271   /* remove from used_memory list */
272   list_remove(&mem->node);
273
274   /*
275    * Rather than freeing the memory right away, try to reuse at a later
276    * point. Keep at least ten percent of the active used blocks or at least
277    * ten blocks on the free list.
278    */
279   if (mem->is_inline && ((ci->ci_free_list_usage < ci->ci_min_free_count)
280       || (ci->ci_free_list_usage < ci->ci_usage / COOKIE_FREE_LIST_THRESHOLD))) {
281
282     list_add_tail(&ci->ci_free_list, &mem->node);
283
284     ci->ci_free_list_usage++;
285 #if !defined REMOVE_LOG_DEBUG
286     reuse = true;
287 #endif
288   } else {
289
290     /* No interest in reusing memory. */
291     if (!mem->is_inline) {
292       free (mem->custom);
293     }
294     free(mem);
295   }
296
297   /* Stats keeping */
298   olsr_cookie_usage_decr(ci);
299
300   OLSR_DEBUG(LOG_COOKIE, "MEMORY: free %s, %p, %lu bytes%s\n",
301              ci->ci_name, ptr, (unsigned long)ci->ci_total_size, reuse ? ", reuse" : "");
302 }
303
304 struct olsr_cookie_custom *
305 olsr_alloc_cookie_custom(struct olsr_cookie_info *ci, size_t size, const char *name,
306     void (*init)(struct olsr_cookie_info *, void *, void *),
307     void (*cleanup)(struct olsr_cookie_info *, void *, void *)) {
308   struct olsr_cookie_custom *custom;
309   struct olsr_memory_prefix *mem;
310   struct list_iterator iterator;
311   size_t old_total_size, new_total_size;
312
313   custom = olsr_malloc(sizeof(struct olsr_cookie_custom), name);
314   custom->name = strdup(name);
315   custom->size = calc_aligned_size(size);
316   custom->init = init;
317   custom->cleanup = cleanup;
318
319   /* recalculate custom data block size */
320   old_total_size = ci->ci_total_size - ci->ci_custom_offset;
321   new_total_size = old_total_size + custom->size;
322
323   custom->offset = old_total_size;
324   ci->ci_total_size += custom->size;
325
326   /* reallocate custom data blocks on used memory blocks*/
327   OLSR_FOR_ALL_USED_MEM(ci, mem, iterator) {
328     uint8_t *custom_ptr;
329
330     custom_ptr = olsr_malloc(new_total_size, ci->ci_name);
331
332     /* copy old data */
333     if (old_total_size > 0) {
334       memcpy(custom_ptr, mem->custom, old_total_size);
335     }
336
337     mem->is_inline = false;
338     mem->custom = custom_ptr;
339
340     /* call up necessary initialization */
341     init(ci, mem + 1, custom_ptr + old_total_size);
342   }
343
344   /* remove all free data blocks, they have the wrong size */
345   OLSR_FOR_ALL_FREE_MEM(ci, mem, iterator) {
346     list_remove(&mem->node);
347     free(mem);
348   }
349   ci->ci_free_list_usage = 0;
350
351   /* add the custom data object to the list */
352   list_add_tail(&ci->ci_custom_list, &custom->node);
353   return custom;
354 }
355
356 void
357 olsr_free_cookie_custom(struct olsr_cookie_info *ci, struct olsr_cookie_custom *custom) {
358   struct olsr_memory_prefix *mem;
359   struct olsr_cookie_custom *c_ptr;
360   struct list_iterator iterator;
361   size_t prefix_block, suffix_block;
362   bool match;
363
364   prefix_block = 0;
365   suffix_block = 0;
366   match = false;
367
368   OLSR_FOR_ALL_CUSTOM_MEM(ci, c_ptr, iterator) {
369     if (c_ptr == custom) {
370       match = true;
371       continue;
372     }
373
374     if (match) {
375       suffix_block += c_ptr->size;
376       c_ptr->offset -= custom->size;
377     }
378     else {
379       prefix_block += c_ptr->size;
380     }
381   }
382
383   /* move the custom memory back into a continous block */
384   if (suffix_block > 0) {
385     OLSR_FOR_ALL_USED_MEM(ci, mem, iterator) {
386       memmove(mem->custom + prefix_block, mem->custom + prefix_block + custom->size, suffix_block);
387     }
388   }
389   ci->ci_total_size -= custom->size;
390
391   /* remove all free data blocks, they have the wrong size */
392   OLSR_FOR_ALL_FREE_MEM(ci, mem, iterator) {
393     list_remove(&mem->node);
394     free(mem);
395   }
396   ci->ci_free_list_usage = 0;
397
398   /* remove the custom data object from the list */
399   list_remove(&custom->node);
400   free (custom->name);
401   free (custom);
402 }
403
404 /*
405  * Local Variables:
406  * c-basic-offset: 2
407  * indent-tabs-mode: nil
408  * End:
409  */