Update to new avl/list iteration macros
[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, *iterator;
108
109   /* remove from tree */
110   avl_delete(&olsr_cookie_tree, &ci->ci_node);
111
112   /* Free name */
113   free(ci->ci_name);
114
115   /* Flush all the memory on the free list */
116   /*
117    * First make all items accessible,
118    * such that valgrind does not complain at shutdown.
119    */
120
121   /* remove all free memory blocks */
122   OLSR_FOR_ALL_FREE_MEM(ci, memory_entity, iterator) {
123     free(memory_entity);
124   }
125
126   /* free all used memory blocks */
127   OLSR_FOR_ALL_USED_MEM(ci, memory_entity, iterator) {
128     free(memory_entity->custom);
129     free(memory_entity);
130   }
131
132   free(ci);
133 }
134
135 /*
136  * Flush all cookies. This is really only called upon shutdown.
137  */
138 void
139 olsr_cookie_cleanup(void)
140 {
141   struct olsr_cookie_info *info, *iterator;
142
143   /*
144    * Walk the full index range and kill 'em all.
145    */
146   OLSR_FOR_ALL_COOKIES(info, iterator) {
147     olsr_cleanup_memcookie(info);
148   }
149 }
150
151 /*
152  * Set if a returned memory block shall be cleared after returning to
153  * the free pool. This is only allowed for memory cookies.
154  */
155 void
156 olsr_cookie_set_min_free(struct olsr_cookie_info *ci, uint32_t min_free)
157 {
158   ci->ci_min_free_count = min_free;
159 }
160
161
162 /*
163  * Increment usage state for a given cookie.
164  */
165 static inline void
166 olsr_cookie_usage_incr(struct olsr_cookie_info *ci)
167 {
168   ci->ci_usage++;
169   ci->ci_changes++;
170 }
171
172 /*
173  * Decrement usage state for a given cookie.
174  */
175 static inline void
176 olsr_cookie_usage_decr(struct olsr_cookie_info *ci)
177 {
178   ci->ci_usage--;
179   ci->ci_changes++;
180 }
181
182 /*
183  * Allocate a fixed amount of memory based on a passed in cookie type.
184  */
185 void *
186 olsr_cookie_malloc(struct olsr_cookie_info *ci)
187 {
188   struct olsr_memory_prefix *mem;
189   struct olsr_cookie_custom *custom, *iterator;
190
191 #if !defined REMOVE_LOG_DEBUG
192   bool reuse = false;
193 #endif
194
195   /*
196    * Check first if we have reusable memory.
197    */
198   if (list_is_empty(&ci->ci_free_list)) {
199     /*
200      * No reusable memory block on the free_list.
201      * Allocate a fresh one.
202      */
203     mem = olsr_malloc(ci->ci_total_size, ci->ci_name);
204   } else {
205     /*
206      * There is a memory block on the free list.
207      * Carve it out of the list, and clean.
208      */
209     mem = list_first_element(&ci->ci_free_list, mem, node);
210     list_remove(&mem->node);
211
212     memset(mem, 0, ci->ci_total_size);
213
214     ci->ci_free_list_usage--;
215 #if !defined REMOVE_LOG_DEBUG
216     reuse = true;
217 #endif
218   }
219
220   /* add to used list */
221   list_add_tail(&ci->ci_used_list, &mem->node);
222
223   /* handle custom initialization */
224   if (!list_is_empty(&ci->ci_custom_list)) {
225     mem->custom = ((uint8_t *)mem) + ci->ci_custom_offset;
226
227     /* call up custom init functions */
228     OLSR_FOR_ALL_CUSTOM_MEM(ci, custom, iterator) {
229       if (custom->init) {
230         custom->init(ci, mem + 1, mem->custom + custom->offset);
231       }
232     }
233   }
234
235   /* Stats keeping */
236   olsr_cookie_usage_incr(ci);
237
238   OLSR_DEBUG(LOG_COOKIE, "MEMORY: alloc %s, %p, %lu bytes%s\n",
239              ci->ci_name, mem + 1, (unsigned long)ci->ci_size, reuse ? ", reuse" : "");
240   return mem + 1;
241 }
242
243 /*
244  * Free a memory block owned by a given cookie.
245  * Run some corruption checks.
246  */
247 void
248 olsr_cookie_free(struct olsr_cookie_info *ci, void *ptr)
249 {
250   struct olsr_memory_prefix *mem;
251   struct olsr_cookie_custom *custom, *iterator;
252 #if !defined REMOVE_LOG_DEBUG
253   bool reuse = false;
254 #endif
255
256   /* calculate pointer to memory prefix */
257   mem = ptr;
258   mem--;
259
260   /* call up custom cleanup */
261   OLSR_FOR_ALL_CUSTOM_MEM(ci, custom, iterator) {
262     if (custom->cleanup) {
263       custom->cleanup(ci, ptr, mem->custom + custom->offset);
264     }
265   }
266
267   /* remove from used_memory list */
268   list_remove(&mem->node);
269
270   /*
271    * Rather than freeing the memory right away, try to reuse at a later
272    * point. Keep at least ten percent of the active used blocks or at least
273    * ten blocks on the free list.
274    */
275   if (mem->is_inline && ((ci->ci_free_list_usage < ci->ci_min_free_count)
276       || (ci->ci_free_list_usage < ci->ci_usage / COOKIE_FREE_LIST_THRESHOLD))) {
277
278     list_add_tail(&ci->ci_free_list, &mem->node);
279
280     ci->ci_free_list_usage++;
281 #if !defined REMOVE_LOG_DEBUG
282     reuse = true;
283 #endif
284   } else {
285
286     /* No interest in reusing memory. */
287     if (!mem->is_inline) {
288       free (mem->custom);
289     }
290     free(mem);
291   }
292
293   /* Stats keeping */
294   olsr_cookie_usage_decr(ci);
295
296   OLSR_DEBUG(LOG_COOKIE, "MEMORY: free %s, %p, %lu bytes%s\n",
297              ci->ci_name, ptr, (unsigned long)ci->ci_total_size, reuse ? ", reuse" : "");
298 }
299
300 struct olsr_cookie_custom *
301 olsr_alloc_cookie_custom(struct olsr_cookie_info *ci, size_t size, const char *name,
302     void (*init)(struct olsr_cookie_info *, void *, void *),
303     void (*cleanup)(struct olsr_cookie_info *, void *, void *)) {
304   struct olsr_cookie_custom *custom;
305   struct olsr_memory_prefix *mem, *iterator;
306   size_t old_total_size, new_total_size;
307
308   custom = olsr_malloc(sizeof(struct olsr_cookie_custom), name);
309   custom->name = strdup(name);
310   custom->size = calc_aligned_size(size);
311   custom->init = init;
312   custom->cleanup = cleanup;
313
314   /* recalculate custom data block size */
315   old_total_size = ci->ci_total_size - ci->ci_custom_offset;
316   new_total_size = old_total_size + custom->size;
317
318   custom->offset = old_total_size;
319   ci->ci_total_size += custom->size;
320
321   /* reallocate custom data blocks on used memory blocks*/
322   OLSR_FOR_ALL_USED_MEM(ci, mem, iterator) {
323     uint8_t *custom_ptr;
324
325     custom_ptr = olsr_malloc(new_total_size, ci->ci_name);
326
327     /* copy old data */
328     if (old_total_size > 0) {
329       memcpy(custom_ptr, mem->custom, old_total_size);
330     }
331
332     mem->is_inline = false;
333     mem->custom = custom_ptr;
334
335     /* call up necessary initialization */
336     init(ci, mem + 1, custom_ptr + old_total_size);
337   }
338
339   /* remove all free data blocks, they have the wrong size */
340   OLSR_FOR_ALL_FREE_MEM(ci, mem, iterator) {
341     list_remove(&mem->node);
342     free(mem);
343   }
344   ci->ci_free_list_usage = 0;
345
346   /* add the custom data object to the list */
347   list_add_tail(&ci->ci_custom_list, &custom->node);
348   return custom;
349 }
350
351 void
352 olsr_free_cookie_custom(struct olsr_cookie_info *ci, struct olsr_cookie_custom *custom) {
353   struct olsr_memory_prefix *mem, *mem_iterator;
354   struct olsr_cookie_custom *c_ptr, *c_iterator;
355   size_t prefix_block, suffix_block;
356   bool match;
357
358   prefix_block = 0;
359   suffix_block = 0;
360   match = false;
361
362   OLSR_FOR_ALL_CUSTOM_MEM(ci, c_ptr, c_iterator) {
363     if (c_ptr == custom) {
364       match = true;
365       continue;
366     }
367
368     if (match) {
369       suffix_block += c_ptr->size;
370       c_ptr->offset -= custom->size;
371     }
372     else {
373       prefix_block += c_ptr->size;
374     }
375   }
376
377   /* move the custom memory back into a continous block */
378   if (suffix_block > 0) {
379     OLSR_FOR_ALL_USED_MEM(ci, mem, mem_iterator) {
380       memmove(mem->custom + prefix_block, mem->custom + prefix_block + custom->size, suffix_block);
381     }
382   }
383   ci->ci_total_size -= custom->size;
384
385   /* remove all free data blocks, they have the wrong size */
386   OLSR_FOR_ALL_FREE_MEM(ci, mem, mem_iterator) {
387     list_remove(&mem->node);
388     free(mem);
389   }
390   ci->ci_free_list_usage = 0;
391
392   /* remove the custom data object from the list */
393   list_remove(&custom->node);
394   free (custom->name);
395   free (custom);
396 }
397
398 /*
399  * Local Variables:
400  * c-basic-offset: 2
401  * indent-tabs-mode: nil
402  * End:
403  */