cookie: fix loop invariant assert and exit on cookie exhaustion
[olsrd.git] / src / olsr_cookie.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2008, Hannes Gredler (hannes@gredler.at)
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 #include "olsr.h"
42 #include "defs.h"
43 #include "olsr_cookie.h"
44 #include "log.h"
45
46 #include <assert.h>
47
48 /* Root directory of the cookies we have in the system */
49 static struct olsr_cookie_info *cookies[COOKIE_ID_MAX] = { 0 };
50
51 /*
52  * Allocate a cookie for the next available cookie id.
53  */
54 struct olsr_cookie_info *
55 olsr_alloc_cookie(const char *cookie_name, olsr_cookie_type cookie_type)
56 {
57   struct olsr_cookie_info *ci;
58   int ci_index;
59
60   /*
61    * Look for an unused index.
62    * For ease of troubleshooting (non-zero patterns) we start at index 1.
63    */
64   for (ci_index = 1; ci_index < COOKIE_ID_MAX; ci_index++) {
65     if (!cookies[ci_index]) {
66       break;
67     }
68   }
69
70   /* 1 <= ci_index <= COOKIE_ID_MAX */
71
72   if (ci_index == COOKIE_ID_MAX) {
73     olsr_exit("No more cookies available", 1);
74     return NULL;
75   }
76
77   ci = calloc(1, sizeof(struct olsr_cookie_info));
78   cookies[ci_index] = ci;
79
80   /* Now populate the cookie info */
81   ci->ci_id = ci_index;
82   ci->ci_type = cookie_type;
83   if (cookie_name) {
84     ci->ci_name = strdup(cookie_name);
85   }
86
87   /* Init the free list */
88   if (cookie_type == OLSR_COOKIE_TYPE_MEMORY) {
89     list_head_init(&ci->ci_free_list);
90   }
91
92   return ci;
93 }
94
95 /*
96  * Free a cookie that is no longer being used.
97  */
98 void
99 olsr_free_cookie(struct olsr_cookie_info *ci)
100 {
101   struct list_node *memory_list;
102
103   /* Mark the cookie as unused */
104   cookies[ci->ci_id] = NULL;
105
106   /* Free name if set */
107   if (ci->ci_name) {
108     free(ci->ci_name);
109   }
110
111   /* Flush all the memory on the free list */
112   if (ci->ci_type == OLSR_COOKIE_TYPE_MEMORY) {
113     while (!list_is_empty(&ci->ci_free_list)) {
114       memory_list = ci->ci_free_list.next;
115       list_remove(memory_list);
116       free(memory_list);
117     }
118   }
119
120   free(ci);
121 }
122
123 /*
124  * Flush all cookies. This is really only called upon shutdown.
125  */
126 void
127 olsr_delete_all_cookies(void)
128 {
129   int ci_index;
130
131   /*
132    * Walk the full index range and kill 'em all.
133    */
134   for (ci_index = 1; ci_index < COOKIE_ID_MAX; ci_index++) {
135     if (!cookies[ci_index]) {
136       continue;
137     }
138     olsr_free_cookie(cookies[ci_index]);
139   }
140 }
141
142 /*
143  * Set the size for fixed block allocations.
144  * This is only allowed for memory cookies.
145  */
146 void
147 olsr_cookie_set_memory_size(struct olsr_cookie_info *ci, size_t size)
148 {
149   if (!ci) {
150     return;
151   }
152
153   assert(ci->ci_type == OLSR_COOKIE_TYPE_MEMORY);
154   ci->ci_size = size;
155 }
156
157 /*
158  * Basic sanity checking for a passed-in cookie-id.
159  */
160 static bool
161 olsr_cookie_valid(olsr_cookie_t cookie_id)
162 {
163   if ((cookie_id < COOKIE_ID_MAX) && cookies[cookie_id]) {
164     return true;
165   }
166   return false;
167 }
168
169 /*
170  * Increment usage state for a given cookie.
171  */
172 void
173 olsr_cookie_usage_incr(olsr_cookie_t cookie_id)
174 {
175   if (olsr_cookie_valid(cookie_id)) {
176     cookies[cookie_id]->ci_usage++;
177     cookies[cookie_id]->ci_changes++;
178   }
179 }
180
181 /*
182  * Decrement usage state for a given cookie.
183  */
184 void
185 olsr_cookie_usage_decr(olsr_cookie_t cookie_id)
186 {
187   if (olsr_cookie_valid(cookie_id)) {
188     cookies[cookie_id]->ci_usage--;
189     cookies[cookie_id]->ci_changes++;
190   }
191 }
192
193 /*
194  * Return a cookie name.
195  * Mostly used for logging purposes.
196  */
197 char *
198 olsr_cookie_name(olsr_cookie_t cookie_id)
199 {
200   static char unknown[] = "unknown";
201
202   if (olsr_cookie_valid(cookie_id)) {
203     return (cookies[cookie_id])->ci_name;
204   }
205
206   return unknown;
207 }
208
209 /*
210  * Allocate a fixed amount of memory based on a passed in cookie type.
211  */
212 void *
213 olsr_cookie_malloc(struct olsr_cookie_info *ci)
214 {
215   void *ptr;
216   struct olsr_cookie_mem_brand *branding;
217   struct list_node *free_list_node;
218
219 #ifdef OLSR_COOKIE_DEBUG
220   bool reuse = false;
221 #endif /* OLSR_COOKIE_DEBUG */
222
223   /*
224    * Check first if we have reusable memory.
225    */
226   if (!ci->ci_free_list_usage) {
227
228     /*
229      * No reusable memory block on the free_list.
230      */
231     ptr = calloc(1, ci->ci_size + sizeof(struct olsr_cookie_mem_brand));
232
233     if (!ptr) {
234       const char *const err_msg = strerror(errno);
235       OLSR_PRINTF(1, "OUT OF MEMORY: %s\n", err_msg);
236       olsr_syslog(OLSR_LOG_ERR, "olsrd: out of memory!: %s\n", err_msg);
237       olsr_exit(ci->ci_name, EXIT_FAILURE);
238     }
239     assert(ptr);
240   } else {
241
242     /*
243      * There is a memory block on the free list.
244      * Carve it out of the list, and clean.
245      */
246     free_list_node = ci->ci_free_list.next;
247     list_remove(free_list_node);
248     ptr = (void *)free_list_node;
249     memset(ptr, 0, ci->ci_size);
250     ci->ci_free_list_usage--;
251 #ifdef OLSR_COOKIE_DEBUG
252     reuse = true;
253 #endif /* OLSR_COOKIE_DEBUG */
254   }
255
256   /*
257    * Now brand mark the end of the memory block with a short signature
258    * indicating presence of a cookie. This will be checked against
259    * When the block is freed to detect corruption.
260    */
261   branding = (struct olsr_cookie_mem_brand *)ARM_NOWARN_ALIGN(((unsigned char *)ptr + ci->ci_size));
262   memcpy(&branding->cmb_sig[0], "cookie", 6);
263   branding->cmb_id = ci->ci_id;
264
265   /* Stats keeping */
266   olsr_cookie_usage_incr(ci->ci_id);
267
268 #ifdef OLSR_COOKIE_DEBUG
269   OLSR_PRINTF(1, "MEMORY: alloc %s, %p, %u bytes%s\n", ci->ci_name, ptr, ci->ci_size, reuse ? ", reuse" : "");
270 #endif /* OLSR_COOKIE_DEBUG */
271
272   return ptr;
273 }
274
275 /*
276  * Free a memory block owned by a given cookie.
277  * Run some corruption checks.
278  */
279 void
280 olsr_cookie_free(struct olsr_cookie_info *ci, void *ptr)
281 {
282   struct olsr_cookie_mem_brand *branding;
283   struct list_node *free_list_node;
284
285 #ifdef OLSR_COOKIE_DEBUG
286   bool reuse = false;
287 #endif /* OLSR_COOKIE_DEBUG */
288
289   branding = (struct olsr_cookie_mem_brand *)ARM_NOWARN_ALIGN(((unsigned char *)ptr + ci->ci_size));
290
291   /*
292    * Verify if there has been a memory overrun, or
293    * the wrong owner is trying to free this.
294    */
295   assert(!memcmp(&branding->cmb_sig, "cookie", 6) && branding->cmb_id == ci->ci_id);
296
297   /* Kill the brand */
298   memset(branding, 0, sizeof(*branding));
299
300   /*
301    * Rather than freeing the memory right away, try to reuse at a later
302    * point. Keep at least ten percent of the active used blocks or at least
303    * ten blocks on the free list.
304    */
305   if ((ci->ci_free_list_usage < COOKIE_FREE_LIST_THRESHOLD) || (ci->ci_free_list_usage < ci->ci_usage / COOKIE_FREE_LIST_THRESHOLD)) {
306
307     free_list_node = (struct list_node *)ptr;
308     list_node_init(free_list_node);
309     list_add_before(&ci->ci_free_list, free_list_node);
310     ci->ci_free_list_usage++;
311 #ifdef OLSR_COOKIE_DEBUG
312     reuse = true;
313 #endif /* OLSR_COOKIE_DEBUG */
314   } else {
315
316     /*
317      * No interest in reusing memory.
318      */
319     free(ptr);
320   }
321
322   /* Stats keeping */
323   olsr_cookie_usage_decr(ci->ci_id);
324
325 #ifdef OLSR_COOKIE_DEBUG
326   OLSR_PRINTF(1, "MEMORY: free %s, %p, %u bytes%s\n", ci->ci_name, ptr, ci->ci_size, reuse ? ", reuse" : "");
327 #endif /* OLSR_COOKIE_DEBUG */
328
329 }
330
331 /*
332  * Local Variables:
333  * c-basic-offset: 2
334  * indent-tabs-mode: nil
335  * End:
336  */