Move from fixed cookie array to dynamic tree
[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 "log.h"
46 #include "valgrind/valgrind.h"
47 #include "valgrind/memcheck.h"
48
49 #include <assert.h>
50 #include <errno.h>
51 #include <stdlib.h>
52
53 struct avl_tree olsr_cookie_tree;
54
55 void olsr_cookie_init(void) {
56   avl_init(&olsr_cookie_tree, &avl_comp_strcasecmp);
57 }
58
59 /*
60  * Allocate a cookie for the next available cookie id.
61  */
62 struct olsr_cookie_info *
63 olsr_alloc_cookie(const char *cookie_name, olsr_cookie_type cookie_type)
64 {
65   static uint16_t next_brand_id = 1;
66
67   struct olsr_cookie_info *ci;
68
69   assert (cookie_name);
70
71   ci = olsr_malloc(sizeof(struct olsr_cookie_info), "new cookie");
72
73   /* Now populate the cookie info */
74   ci->ci_type = cookie_type;
75   ci->ci_name = olsr_strdup(cookie_name);
76
77   ci->node.key = ci->ci_name;
78
79   /* Init the free list */
80   if (cookie_type == OLSR_COOKIE_TYPE_MEMORY) {
81     list_head_init(&ci->ci_free_list);
82     VALGRIND_CREATE_MEMPOOL(ci, 0, 1);
83
84     ci->ci_membrand = next_brand_id++;
85   }
86   else {
87     ci->ci_membrand = 0;
88   }
89
90   avl_insert(&olsr_cookie_tree, &ci->node, AVL_DUP_NO);
91   return ci;
92 }
93
94 /*
95  * Free a cookie that is no longer being used.
96  */
97 static void
98 olsr_free_cookie(struct olsr_cookie_info *ci)
99 {
100   struct list_node *memory_list;
101
102   /* remove from tree */
103   avl_delete(&olsr_cookie_tree, &ci->node);
104
105   /* Free name */
106   free(ci->ci_name);
107
108   /* Flush all the memory on the free list */
109   if (ci->ci_type == OLSR_COOKIE_TYPE_MEMORY) {
110
111     /*
112      * First make all items accessible,
113      * such that valgrind does not complain at shutdown.
114      */
115     if (!list_is_empty(&ci->ci_free_list)) {
116       for (memory_list = ci->ci_free_list.next; memory_list != &ci->ci_free_list; memory_list = memory_list->next) {
117         VALGRIND_MAKE_MEM_DEFINED(memory_list, ci->ci_size);
118       }
119     }
120
121     while (!list_is_empty(&ci->ci_free_list)) {
122       memory_list = ci->ci_free_list.next;
123       list_remove(memory_list);
124       free(memory_list);
125     }
126     VALGRIND_DESTROY_MEMPOOL(ci);
127   }
128
129   free(ci);
130 }
131
132 /*
133  * Flush all cookies. This is really only called upon shutdown.
134  */
135 void
136 olsr_delete_all_cookies(void)
137 {
138   struct olsr_cookie_info *info;
139
140   /*
141    * Walk the full index range and kill 'em all.
142    */
143   OLSR_FOR_ALL_COOKIES(info) {
144     olsr_free_cookie(info);
145   } OLSR_FOR_ALL_COOKIES_END(info)
146 }
147
148 /*
149  * Set the size for fixed block allocations.
150  * This is only allowed for memory cookies.
151  */
152 void
153 olsr_cookie_set_memory_size(struct olsr_cookie_info *ci, size_t size)
154 {
155   if (!ci) {
156     return;
157   }
158
159   assert(ci->ci_type == OLSR_COOKIE_TYPE_MEMORY);
160   ci->ci_size = size;
161 }
162
163 /*
164  * Set if a returned memory block shall be cleared after returning to
165  * the free pool. This is only allowed for memory cookies.
166  */
167 void
168 olsr_cookie_set_memory_clear(struct olsr_cookie_info *ci, bool clear)
169 {
170   if (!ci) {
171     return;
172   }
173
174   assert(ci->ci_type == OLSR_COOKIE_TYPE_MEMORY);
175
176   if (!clear) {
177     ci->ci_flags |= COOKIE_NO_MEMCLEAR;
178   } else {
179     ci->ci_flags &= ~COOKIE_NO_MEMCLEAR;
180   }
181 }
182
183 /*
184  * Set if a returned memory block shall be initialized to an all zero or
185  * to a poison memory pattern after returning to the free pool.
186  * This is only allowed for memory cookies.
187  */
188 void
189 olsr_cookie_set_memory_poison(struct olsr_cookie_info *ci, bool poison)
190 {
191   if (!ci) {
192     return;
193   }
194
195   assert(ci->ci_type == OLSR_COOKIE_TYPE_MEMORY);
196
197   if (poison) {
198     ci->ci_flags |= COOKIE_MEMPOISON;
199   } else {
200     ci->ci_flags &= ~COOKIE_MEMPOISON;
201   }
202 }
203
204 /*
205  * Increment usage state for a given cookie.
206  */
207 void
208 olsr_cookie_usage_incr(struct olsr_cookie_info *ci)
209 {
210   ci->ci_usage++;
211   ci->ci_changes++;
212 }
213
214 /*
215  * Decrement usage state for a given cookie.
216  */
217 void
218 olsr_cookie_usage_decr(struct olsr_cookie_info *ci)
219 {
220   ci->ci_usage--;
221   ci->ci_changes++;
222 }
223
224 /*
225  * Allocate a fixed amount of memory based on a passed in cookie type.
226  */
227 void *
228 olsr_cookie_malloc(struct olsr_cookie_info *ci)
229 {
230   void *ptr;
231   struct olsr_cookie_mem_brand *branding;
232   struct list_node *free_list_node;
233 #if !defined REMOVE_LOG_DEBUG
234   bool reuse = false;
235 #endif
236   size_t size;
237
238   /*
239    * Check first if we have reusable memory.
240    */
241   if (!ci->ci_free_list_usage) {
242
243     /*
244      * No reusable memory block on the free_list.
245      * Allocate a fresh one.
246      */
247     size = ci->ci_size + sizeof(struct olsr_cookie_mem_brand);
248     ptr = olsr_malloc(size, ci->ci_name);
249
250     /*
251      * Poison the memory for debug purposes ?
252      */
253     if (ci->ci_flags & COOKIE_MEMPOISON) {
254       memset(ptr, COOKIE_MEMPOISON_PATTERN, size);
255     }
256
257   } else {
258
259     /*
260      * There is a memory block on the free list.
261      * Carve it out of the list, and clean.
262      */
263     free_list_node = ci->ci_free_list.next;
264     ptr = (void *)free_list_node;
265     VALGRIND_MAKE_MEM_DEFINED(ptr, ci->ci_size);
266
267     /*
268      * Before dequeuing the node from the free list,
269      * make the list pointers of the node ahead of
270      * us accessible, such that valgrind does not
271      * log a false positive.
272      */
273     if (free_list_node->next == &ci->ci_free_list) {
274       list_remove(free_list_node);
275     } else {
276
277       /*
278        * Make next item accessible, remove it and make next item inaccessible.
279        */
280       VALGRIND_MAKE_MEM_DEFINED(free_list_node->next, ci->ci_size);
281       list_remove(free_list_node);
282       VALGRIND_MAKE_MEM_NOACCESS(free_list_node->next, ci->ci_size);
283     }
284
285     /*
286      * Reset the memory unless the caller has told us so.
287      */
288     if (!(ci->ci_flags & COOKIE_NO_MEMCLEAR)) {
289
290       /*
291        * Poison the memory for debug purposes ?
292        */
293       if (ci->ci_flags & COOKIE_MEMPOISON) {
294         memset(ptr, COOKIE_MEMPOISON_PATTERN, ci->ci_size);
295       } else {
296         memset(ptr, 0, ci->ci_size);
297       }
298     }
299
300     ci->ci_free_list_usage--;
301 #if !defined REMOVE_LOG_DEBUG
302     reuse = true;
303 #endif
304   }
305
306   /*
307    * Now brand mark the end of the memory block with a short signature
308    * indicating presence of a cookie. This will be checked against
309    * When the block is freed to detect corruption.
310    */
311   branding = (struct olsr_cookie_mem_brand *)
312     ((unsigned char *)ptr + ci->ci_size);
313   memcpy(&branding->cmb_sig, "cookie", 6);
314   branding->id = ci->ci_membrand;
315
316   /* Stats keeping */
317   olsr_cookie_usage_incr(ci);
318
319   OLSR_DEBUG(LOG_COOKIE, "MEMORY: alloc %s, %p, %lu bytes%s\n",
320              ci->ci_name, ptr, (unsigned long)ci->ci_size, reuse ? ", reuse" : "");
321
322   VALGRIND_MEMPOOL_ALLOC(ci, ptr, ci->ci_size);
323   return ptr;
324 }
325
326 /*
327  * Free a memory block owned by a given cookie.
328  * Run some corruption checks.
329  */
330 void
331 olsr_cookie_free(struct olsr_cookie_info *ci, void *ptr)
332 {
333   struct list_node *free_list_node;
334 #if !defined REMOVE_LOG_DEBUG
335   bool reuse = false;
336 #endif
337   struct olsr_cookie_mem_brand *branding = (struct olsr_cookie_mem_brand *)
338     ((unsigned char *)ptr + ci->ci_size);
339
340   /*
341    * Verify if there has been a memory overrun, or
342    * the wrong owner is trying to free this.
343    */
344   assert(!memcmp(&branding->cmb_sig, "cookie", 6) && branding->id == ci->ci_membrand);
345
346   /* Kill the brand */
347   memset(branding, 0, sizeof(*branding));
348
349   /*
350    * Rather than freeing the memory right away, try to reuse at a later
351    * point. Keep at least ten percent of the active used blocks or at least
352    * ten blocks on the free list.
353    */
354   if ((ci->ci_free_list_usage < COOKIE_FREE_LIST_THRESHOLD) || (ci->ci_free_list_usage < ci->ci_usage / COOKIE_FREE_LIST_THRESHOLD)) {
355
356     free_list_node = (struct list_node *)ptr;
357     list_node_init(free_list_node);
358
359     /*
360      * Before enqueuing the node to the free list,
361      * make the list pointers of the node ahead of
362      * us accessible, such that valgrind does not
363      * log a false positive.
364      */
365     if (list_is_empty(&ci->ci_free_list)) {
366       list_add_before(&ci->ci_free_list, free_list_node);
367     } else {
368
369       /*
370        * Make next item accessible, add it and make next item inaccessible.
371        */
372       VALGRIND_MAKE_MEM_DEFINED(ci->ci_free_list.prev, ci->ci_size);
373       list_add_before(&ci->ci_free_list, free_list_node);
374       VALGRIND_MAKE_MEM_NOACCESS(ci->ci_free_list.prev, ci->ci_size);
375     }
376
377     ci->ci_free_list_usage++;
378 #if !defined REMOVE_LOG_DEBUG
379     reuse = true;
380 #endif
381
382   } else {
383
384     /*
385      * No interest in reusing memory.
386      */
387     free(ptr);
388   }
389
390   /* Stats keeping */
391   olsr_cookie_usage_decr(ci);
392
393   OLSR_DEBUG(LOG_COOKIE, "MEMORY: free %s, %p, %lu bytes%s\n",
394              ci->ci_name, ptr, (unsigned long)ci->ci_size, reuse ? ", reuse" : "");
395
396   VALGRIND_MEMPOOL_FREE(ci, ptr);
397   VALGRIND_MAKE_MEM_NOACCESS(ptr, ci->ci_size);
398 }
399
400 /*
401  * Local Variables:
402  * c-basic-offset: 2
403  * indent-tabs-mode: nil
404  * End:
405  */