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