Cleanup of memory cookie system. Changed name from "cookie" to "memcookie".
[olsrd.git] / src / olsr_memcookie.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_memcookie.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 /**
55  * Align a byte size correctly to "two size_t" units
56  * @param size number of bytes for an unaligned block
57  * @return number of bytes including padding for alignment
58  */
59 static inline size_t
60 calc_aligned_size(size_t size) {
61   static const size_t add = sizeof(size_t) * 2 - 1;
62   static const size_t mask = ~(sizeof(size_t)*2 - 1);
63
64   return (size + add) & mask;
65 }
66
67 /**
68  * Increment usage state for a given cookie.
69  * @param ci pointer to memcookie info
70  */
71 static inline void
72 olsr_cookie_usage_incr(struct olsr_memcookie_info *ci)
73 {
74   ci->ci_usage++;
75   ci->ci_changes++;
76 }
77
78 /**
79  * Decrement usage state for a given cookie.
80  * @param ci pointer to memcookie info
81  */
82 static inline void
83 olsr_cookie_usage_decr(struct olsr_memcookie_info *ci)
84 {
85   ci->ci_usage--;
86   ci->ci_changes++;
87 }
88
89 /**
90  * Initialize the memory cookie system
91  */
92 void
93 olsr_memcookie_init(void) {
94   /* check size of memory prefix */
95   assert (sizeof(struct olsr_memory_prefix)
96       == calc_aligned_size(sizeof(struct olsr_memory_prefix)));
97
98   avl_init(&olsr_cookie_tree, &avl_comp_strcasecmp, false, NULL);
99 }
100
101 /**
102  * Cleanup the memory cookie system
103  */
104 void
105 olsr_memcookie_cleanup(void)
106 {
107   struct olsr_memcookie_info *info, *iterator;
108
109   /*
110    * Walk the full index range and kill 'em all.
111    */
112   OLSR_FOR_ALL_COOKIES(info, iterator) {
113     olsr_memcookie_remove(info);
114   }
115 }
116
117 /**
118  * Allocate a new memcookie.
119  * @param cookie_name id of the cookie
120  * @param size number of bytes to allocate for each cookie
121  * @return memcookie_info pointer
122  */
123 struct olsr_memcookie_info *
124 olsr_memcookie_add(const char *cookie_name, size_t size)
125 {
126   struct olsr_memcookie_info *ci;
127
128   assert (cookie_name);
129   ci = olsr_malloc(sizeof(struct olsr_memcookie_info), "memory cookie");
130
131   /* Now populate the cookie info */
132   ci->ci_name = olsr_strdup(cookie_name);
133   ci->ci_node.key = ci->ci_name;
134   ci->ci_size = size;
135   ci->ci_custom_offset = sizeof(struct olsr_memory_prefix) + calc_aligned_size(size);
136   ci->ci_min_free_count = COOKIE_FREE_LIST_THRESHOLD;
137
138   /* no custom data at this point */
139   ci->ci_total_size = ci->ci_custom_offset;
140
141   /* Init the free list */
142   list_init_head(&ci->ci_free_list);
143   list_init_head(&ci->ci_used_list);
144   list_init_head(&ci->ci_custom_list);
145
146   avl_insert(&olsr_cookie_tree, &ci->ci_node);
147   return ci;
148 }
149
150 /**
151  * Delete a memcookie and all attached memory
152  * @param ci pointer to memcookie
153  */
154 void
155 olsr_memcookie_remove(struct olsr_memcookie_info *ci)
156 {
157   struct olsr_memory_prefix *memory_entity, *iterator;
158
159   /* remove from tree */
160   avl_delete(&olsr_cookie_tree, &ci->ci_node);
161
162   /* Free name */
163   free(ci->ci_name);
164
165   /* Flush all the memory on the free list */
166   /*
167    * First make all items accessible,
168    * such that valgrind does not complain at shutdown.
169    */
170
171   /* remove all free memory blocks */
172   OLSR_FOR_ALL_FREE_MEM(ci, memory_entity, iterator) {
173     free(memory_entity);
174   }
175
176   /* free all used memory blocks */
177   OLSR_FOR_ALL_USED_MEM(ci, memory_entity, iterator) {
178     free(memory_entity->custom);
179     free(memory_entity);
180   }
181
182   free(ci);
183 }
184
185 /**
186  * Allocate a fixed amount of memory based on a passed in cookie type.
187  * @param ci pointer to memcookie info
188  * @return allocated memory
189  */
190 void *
191 olsr_memcookie_malloc(struct olsr_memcookie_info *ci)
192 {
193   struct olsr_memory_prefix *mem;
194   struct olsr_memcookie_custom *custom, *iterator;
195
196 #if !defined REMOVE_LOG_DEBUG
197   bool reuse = false;
198 #endif
199
200   /*
201    * Check first if we have reusable memory.
202    */
203   if (list_is_empty(&ci->ci_free_list)) {
204     /*
205      * No reusable memory block on the free_list.
206      * Allocate a fresh one.
207      */
208     mem = olsr_malloc(ci->ci_total_size, ci->ci_name);
209   } else {
210     /*
211      * There is a memory block on the free list.
212      * Carve it out of the list, and clean.
213      */
214     mem = list_first_element(&ci->ci_free_list, mem, node);
215     list_remove(&mem->node);
216
217     memset(mem, 0, ci->ci_total_size);
218
219     ci->ci_free_list_usage--;
220 #if !defined REMOVE_LOG_DEBUG
221     reuse = true;
222 #endif
223   }
224
225   /* add to used list */
226   list_add_tail(&ci->ci_used_list, &mem->node);
227
228   /* handle custom initialization */
229   if (!list_is_empty(&ci->ci_custom_list)) {
230     mem->custom = ((uint8_t *)mem) + ci->ci_custom_offset;
231
232     /* call up custom init functions */
233     OLSR_FOR_ALL_CUSTOM_MEM(ci, custom, iterator) {
234       if (custom->init) {
235         custom->init(ci, mem + 1, mem->custom + custom->offset);
236       }
237     }
238   }
239
240   /* Stats keeping */
241   olsr_cookie_usage_incr(ci);
242
243   OLSR_DEBUG(LOG_COOKIE, "MEMORY: alloc %s, %p, %lu bytes%s\n",
244              ci->ci_name, mem + 1, (unsigned long)ci->ci_size, reuse ? ", reuse" : "");
245   return mem + 1;
246 }
247
248 /**
249  * Free a memory block owned by a given cookie.
250  * @param ci pointer to memcookie info
251  * @param ptr pointer to memory block
252  */
253 void
254 olsr_memcookie_free(struct olsr_memcookie_info *ci, void *ptr)
255 {
256   struct olsr_memory_prefix *mem;
257 #if !defined REMOVE_LOG_DEBUG
258   bool reuse = false;
259 #endif
260
261   /* calculate pointer to memory prefix */
262   mem = ptr;
263   mem--;
264
265   /* remove from used_memory list */
266   list_remove(&mem->node);
267
268   /*
269    * Rather than freeing the memory right away, try to reuse at a later
270    * point. Keep at least ten percent of the active used blocks or at least
271    * ten blocks on the free list.
272    */
273   if (mem->is_inline && ((ci->ci_free_list_usage < ci->ci_min_free_count)
274       || (ci->ci_free_list_usage < ci->ci_usage / COOKIE_FREE_LIST_THRESHOLD))) {
275
276     list_add_tail(&ci->ci_free_list, &mem->node);
277
278     ci->ci_free_list_usage++;
279 #if !defined REMOVE_LOG_DEBUG
280     reuse = true;
281 #endif
282   } else {
283
284     /* No interest in reusing memory. */
285     if (!mem->is_inline) {
286       free (mem->custom);
287     }
288     free(mem);
289   }
290
291   /* Stats keeping */
292   olsr_cookie_usage_decr(ci);
293
294   OLSR_DEBUG(LOG_COOKIE, "MEMORY: free %s, %p, %lu bytes%s\n",
295              ci->ci_name, ptr, (unsigned long)ci->ci_total_size, reuse ? ", reuse" : "");
296 }
297
298 /**
299  * Add a custom memory section to an existing memcookie.
300  *
301  * Calling this function will call the specified init() callback and
302  * the move() callback of all existing custom extensions of this memcookie
303  * for every existing piece of allocated memory of the memcookie.
304  *
305  * @param memcookie_name name of memory cookie to be extended
306  * @param name name of custom addition for the memory cookie
307  * @param size number of bytes needed for custom addition
308  * @param init callback of the custom memcookie manager which is called every
309  *   times a new memcookie instance is allocated. Parameters are the memcookie_info
310  *   object, a pointer to the allocated memory and a pointer to the custom
311  *   part of the memory object.
312  * @param move callback of the custom memcookie manager which is called every
313  *   times the memory of the custom extension changes (because of adding/removal of
314  *   other custom extensions). Parameters are the memcookie_info object, a pointer to
315  *   the allocated memory, a pointer to the old position of the custom extension and
316  *   a pointer to the new custom extension.
317  * @return custom memory cookie
318  */
319 struct olsr_memcookie_custom *
320 olsr_memcookie_add_custom(const char *memcookie_name, const char *name, size_t size,
321     void (*init)(struct olsr_memcookie_info *, void *, void *),
322     void (*move)(struct olsr_memcookie_info *, void *, void *)) {
323   struct olsr_memcookie_info *ci;
324   struct olsr_memcookie_custom *custom_cookie;
325   struct olsr_memcookie_custom *custom, *custom_iterator;
326   struct olsr_memory_prefix *mem, *mem_iterator;
327   size_t old_total_size, new_total_size;
328
329   ci = avl_find_element(&olsr_cookie_tree, memcookie_name, ci, ci_node);
330   if (ci == NULL) {
331     OLSR_WARN(LOG_COOKIE, "Memory cookie '%s' does not exist, cannot add custom block '%s'\n",
332         memcookie_name, name);
333     return NULL;
334   }
335
336   custom_cookie = olsr_malloc(sizeof(struct olsr_memcookie_custom), name);
337   custom_cookie->name = strdup(name);
338   custom_cookie->size = calc_aligned_size(size);
339   custom_cookie->init = init;
340   custom_cookie->move = move;
341
342   /* recalculate custom data block size */
343   old_total_size = ci->ci_total_size - ci->ci_custom_offset;
344   new_total_size = old_total_size + custom_cookie->size;
345
346   custom_cookie->offset = old_total_size;
347   ci->ci_total_size += custom_cookie->size;
348
349   /* reallocate custom data blocks on used memory blocks*/
350   OLSR_FOR_ALL_USED_MEM(ci, mem, mem_iterator) {
351     uint8_t *new_custom;
352
353     new_custom = olsr_malloc(new_total_size, ci->ci_name);
354
355     /* copy old data */
356     if (old_total_size > 0) {
357       memmove(new_custom, mem->custom, old_total_size);
358     }
359
360     mem->is_inline = false;
361     mem->custom = new_custom;
362
363     /* call up necessary initialization */
364     if (custom->init) {
365       custom->init(ci, mem + 1, new_custom + old_total_size);
366     }
367
368     /* inform the custom cookie managers that their memory has moved */
369     OLSR_FOR_ALL_CUSTOM_MEM(ci, custom, custom_iterator) {
370       if (custom->move) {
371         custom->move(ci, mem+1, new_custom + custom->offset);
372       }
373     }
374   }
375
376   /* remove all free data blocks, they have the wrong size */
377   OLSR_FOR_ALL_FREE_MEM(ci, mem, mem_iterator) {
378     list_remove(&mem->node);
379     free(mem);
380   }
381   ci->ci_free_list_usage = 0;
382
383   /* add the custom data object to the list */
384   list_add_tail(&ci->ci_custom_list, &custom_cookie->node);
385   return custom_cookie;
386 }
387
388 /**
389  * Remove a custom addition to a memcookie
390  * @param memcookie_name name of memcookie
391  * @param custom pointer to custom memcookie
392  */
393 void
394 olsr_memcookie_remove_custom(const char*memcookie_name, struct olsr_memcookie_custom *custom) {
395   struct olsr_memcookie_info *ci;
396   struct olsr_memory_prefix *mem, *mem_iterator;
397   struct olsr_memcookie_custom *c_ptr, *c_iterator;
398   size_t prefix_block, suffix_block;
399   bool match;
400
401   ci = avl_find_element(&olsr_cookie_tree, memcookie_name, ci, ci_node);
402   if (ci == NULL) {
403     OLSR_WARN(LOG_COOKIE, "Memory cookie '%s' does not exist, cannot remove custom block '%s'\n",
404         memcookie_name, custom->name);
405     return;
406   }
407
408   prefix_block = 0;
409   suffix_block = 0;
410   match = false;
411
412   /* calculate size of (not) modified custom data block */
413   OLSR_FOR_ALL_CUSTOM_MEM(ci, c_ptr, c_iterator) {
414     if (c_ptr == custom) {
415       match = true;
416       continue;
417     }
418
419     if (match) {
420       suffix_block += c_ptr->size;
421     }
422     else {
423       prefix_block += c_ptr->size;
424     }
425   }
426
427   /* move the custom memory back into a continous block */
428   if (suffix_block > 0) {
429     OLSR_FOR_ALL_USED_MEM(ci, mem, mem_iterator) {
430       memmove(mem->custom + prefix_block, mem->custom + prefix_block + custom->size, suffix_block);
431
432       /* recalculate offsets of moved blocks and inform callbacks */
433       OLSR_FOR_ALL_CUSTOM_MEM(ci, c_ptr, c_iterator) {
434         if (c_ptr == custom) {
435           match = true;
436           continue;
437         }
438
439         if (match) {
440           c_ptr->offset -= custom->size;
441
442           if (c_ptr->move) {
443             c_ptr->move(ci, mem+1, mem->custom + c_ptr->offset);
444           }
445         }
446       }
447
448     }
449   }
450   ci->ci_total_size -= custom->size;
451
452   /* remove all free data blocks, they have the wrong size */
453   OLSR_FOR_ALL_FREE_MEM(ci, mem, mem_iterator) {
454     list_remove(&mem->node);
455     free(mem);
456   }
457   ci->ci_free_list_usage = 0;
458
459   /* remove the custom data object from the list */
460   list_remove(&custom->node);
461   free (custom->name);
462   free (custom);
463 }
464
465
466 /*
467  * Local Variables:
468  * c-basic-offset: 2
469  * indent-tabs-mode: nil
470  * End:
471  */