From Harald Welte:
[obnox/wireshark/wip.git] / epan / emem.h
1 /* emem.h
2  * Definitions for Wireshark memory management and garbage collection
3  * Ronnie Sahlberg 2005
4  *
5  * $Id$
6  *
7  * Wireshark - Network traffic analyzer
8  * By Gerald Combs <gerald@wireshark.org>
9  * Copyright 1998 Gerald Combs
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software
23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
24  */
25
26 #ifndef __EMEM_H__
27 #define __EMEM_H__
28
29 /** @file
30  */
31 /**  Initialize all the memory allocation pools described below.
32  *  This function must be called once when *shark initialize to set up the
33  *  required structures.
34  */
35 void emem_init(void);
36
37 /* Functions for handling memory allocation and garbage collection with
38  * a packet lifetime scope.
39  * These functions are used to allocate memory that will only remain persistent
40  * until Wireshark starts dissecting the next packet in the list.
41  * Everytime Wireshark starts decoding the next packet all memory allocated
42  * through these functions will be released back to the free pool.
43  *
44  * These functions are very fast and offer automatic garbage collection:
45  * Everytime a new packet is dissected, all memory allocations done in
46  * the previous packet is freed.
47  */
48
49 /** Allocate memory with a packet lifetime scope */
50 void *ep_alloc(size_t size) G_GNUC_MALLOC;
51 #define ep_new(type) ((type*)ep_alloc(sizeof(type)))
52
53 /** Allocate memory with a packet lifetime scope and fill it with zeros*/
54 void* ep_alloc0(size_t size) G_GNUC_MALLOC;
55 #define ep_new0(type) ((type*)ep_alloc0(sizeof(type)))
56
57 /** Duplicate a string with a packet lifetime scope */
58 gchar* ep_strdup(const gchar* src) G_GNUC_MALLOC;
59
60 /** Duplicate at most n characters of a string with a packet lifetime scope */
61 gchar* ep_strndup(const gchar* src, size_t len) G_GNUC_MALLOC;
62
63 /** Duplicate a buffer with a packet lifetime scope */
64 void* ep_memdup(const void* src, size_t len) G_GNUC_MALLOC;
65
66 /** Create a formatted string with a packet lifetime scope */
67 gchar* ep_strdup_vprintf(const gchar* fmt, va_list ap) G_GNUC_MALLOC;
68 gchar* ep_strdup_printf(const gchar* fmt, ...)
69      G_GNUC_MALLOC G_GNUC_PRINTF(1, 2);
70
71 gchar *ep_strconcat(const gchar *string, ...) G_GNUC_MALLOC G_GNUC_NULL_TERMINATED;
72
73 /** allocates with a packet lifetime scope an array of type made of num elements */
74 #define ep_alloc_array(type,num) (type*)ep_alloc(sizeof(type)*(num))
75
76 /** allocates with a packet lifetime scope an array of type made of num elements,
77  * initialised to zero.
78  */
79 #define ep_alloc_array0(type,num) (type*)ep_alloc0(sizeof(type)*(num))
80
81 /**
82  * Splits a string into a maximum of max_tokens pieces, using the given
83  * delimiter. If max_tokens is reached, the remainder of string is appended
84  * to the last token. Consecutive delimiters are treated as a single delimiter.
85  *
86  * The vector and all the strings are allocated with packet lifetime scope
87  */
88 gchar** ep_strsplit(const gchar* string, const gchar* delimiter, int max_tokens);
89
90 /** release all memory allocated in the previous packet dissection */
91 void ep_free_all(void);
92
93
94 /** a stack implemented using ephemeral allocators */
95
96 typedef struct _ep_stack_frame_t** ep_stack_t;
97
98 struct _ep_stack_frame_t {
99     void* payload;
100     struct _ep_stack_frame_t* below;
101     struct _ep_stack_frame_t* above;
102 };
103
104 /**
105  * creates an empty stack with a packet lifetime scope
106  */
107 ep_stack_t ep_stack_new(void) G_GNUC_MALLOC;
108
109 /**
110  * pushes item into stack, returns item
111  */
112 void* ep_stack_push(ep_stack_t stack, void* item);
113
114 /**
115  * pops an item from the stack
116  */
117 void* ep_stack_pop(ep_stack_t stack);
118
119 /**
120  * returns the item on top of the stack without popping it
121  */
122 #define ep_stack_peek(stack) ((*(stack))->payload)
123
124
125 /* Functions for handling memory allocation and garbage collection with
126  * a capture lifetime scope.
127  * These functions are used to allocate memory that will only remain persistent
128  * until Wireshark opens a new capture or capture file.
129  * Everytime Wireshark starts a new capture or opens a new capture file
130  * all the data allocated through these functions will be released back
131  * to the free pool.
132  *
133  * These functions are very fast and offer automatic garbage collection.
134  */
135
136 /** Allocate memory with a capture lifetime scope */
137 void *se_alloc(size_t size) G_GNUC_MALLOC;
138 #define se_new(type) ((type*)se_alloc(sizeof(type)))
139
140 /** Allocate memory with a capture lifetime scope and fill it with zeros*/
141 void* se_alloc0(size_t size) G_GNUC_MALLOC;
142 #define se_new0(type) ((type*)se_alloc0(sizeof(type)))
143
144 /** Duplicate a string with a capture lifetime scope */
145 gchar* se_strdup(const gchar* src) G_GNUC_MALLOC;
146
147 /** Duplicate at most n characters of a string with a capture lifetime scope */
148 gchar* se_strndup(const gchar* src, size_t len) G_GNUC_MALLOC;
149
150 /** Duplicate a buffer with a capture lifetime scope */
151 void* se_memdup(const void* src, size_t len) G_GNUC_MALLOC;
152
153 /* Create a formatted string with a capture lifetime scope */
154 gchar* se_strdup_vprintf(const gchar* fmt, va_list ap) G_GNUC_MALLOC;
155 gchar* se_strdup_printf(const gchar* fmt, ...)
156      G_GNUC_MALLOC G_GNUC_PRINTF(1, 2);
157
158 /** allocates with a capture lifetime scope an array of type made of num elements */
159 #define se_alloc_array(type,num) (type*)se_alloc(sizeof(type)*(num))
160
161 /** release all memory allocated */
162 void se_free_all(void);
163
164 /**************************************************************
165  * slab allocator
166  **************************************************************/
167 struct _emem_chunk_t;
168
169 /* Macros to initialize ws_memory_slab */
170 /* XXX, is G_MEM_ALIGN enough? http://mail.gnome.org/archives/gtk-devel-list/2004-December/msg00091.html */
171 #define WS_MEMORY_SLAB_INIT(type, count) { ((sizeof(type) + (G_MEM_ALIGN - 1)) & ~(G_MEM_ALIGN - 1)), count, NULL, NULL }
172 #define WS_MEMORY_SLAB_INIT_UNALIGNED(size, count) { size, count, NULL, NULL }
173
174 struct ws_memory_slab {
175         const gint item_size;
176         const gint count;
177
178         struct _emem_chunk_t *chunk_list;
179         void *freed;
180 };
181
182 void *sl_alloc(struct ws_memory_slab *mem_chunk);
183 void *sl_alloc0(struct ws_memory_slab *mem_chunk);
184 void sl_free(struct ws_memory_slab *mem_chunk, gpointer ptr);
185
186 /** release all memory allocated */
187 void sl_free_all(struct ws_memory_slab *mem_chunk);
188
189 /**************************************************************
190  * binary trees
191  **************************************************************/
192 typedef struct _emem_tree_node_t {
193         struct _emem_tree_node_t *parent;
194         struct _emem_tree_node_t *left;
195         struct _emem_tree_node_t *right;
196         struct {
197 #define EMEM_TREE_RB_COLOR_RED          0
198 #define EMEM_TREE_RB_COLOR_BLACK        1
199                 guint32 rb_color:1;
200 #define EMEM_TREE_NODE_IS_DATA          0
201 #define EMEM_TREE_NODE_IS_SUBTREE       1
202                 guint32 is_subtree:1;
203         } u;
204         guint32 key32;
205         void *data;
206 } emem_tree_node_t;
207
208 /** Right now we only do basic red/black trees   but in the future we might want
209  * to try something different, such as a tree where each node keeps track
210  * of how many times it has been looked up, and letting often looked up
211  * nodes bubble upwards in the tree using rotate_right/left.
212  * That would probably be good for things like nfs filehandles
213  */
214 #define EMEM_TREE_TYPE_RED_BLACK        1
215 typedef struct _emem_tree_t {
216         struct _emem_tree_t *next;
217         int type;
218         const char *name;    /**< just a string to make debugging easier */
219         emem_tree_node_t *tree;
220         void *(*malloc)(size_t);
221 } emem_tree_t;
222
223 /* *******************************************************************
224  * Tree functions for SE memory allocation scope
225  * ******************************************************************* */
226 /** This function is used to create a se based tree with monitoring.
227  * When the SE heap is released back to the system the pointer to the
228  * tree is automatically reset to NULL.
229  *
230  * type is : EMEM_TREE_TYPE_RED_BLACK for a standard red/black tree.
231  */
232 emem_tree_t *se_tree_create(int type, const char *name) G_GNUC_MALLOC;
233
234 /** This function is similar to the se_tree_create() call but with the
235  * difference that when the se memory is released everything including the
236  * pointer to the tree itself will be released.
237  * This tree will not be just reset to zero, it will be completely forgotten
238  * by the allocator.
239  * Use this function for when you want to store the pointer to a tree inside
240  * another structure that is also se allocated so that when the structure is
241  * released, the tree will be completely released as well.
242  */
243 emem_tree_t *se_tree_create_non_persistent(int type, const char *name) G_GNUC_MALLOC;
244
245 /** se_tree_insert32
246  * Insert data into the tree and key it by a 32bit integer value
247  */
248 #define se_tree_insert32 emem_tree_insert32
249
250 /** se_tree_lookup32
251  * Retrieve the data at the search key. The search key is a 32bit integer value
252  */
253 #define se_tree_lookup32 emem_tree_lookup32
254
255 /** se_tree_lookup32_le
256  * Retrieve the data for the largest key that is less than or equal
257  * to the search key.
258  */
259 #define se_tree_lookup32_le emem_tree_lookup32_le
260
261 /** se_tree_insert32_array
262  * Insert data into the tree and key it by a 32bit integer value
263  */
264 #define se_tree_insert32_array emem_tree_insert32_array
265
266 /** se_tree_lookup32_array
267  * Lookup data from the tree that is index by an array
268  */
269 #define se_tree_lookup32_array emem_tree_lookup32_array
270
271 /** se_tree_lookup32_array_le
272  * Retrieve the data for the largest key that is less than or equal
273  * to the search key.
274  */
275 #define se_tree_lookup32_array_le emem_tree_lookup32_array_le
276
277 /** Create a new string based hash table */
278 #define se_tree_create_string() se_tree_create(SE_TREE_TYPE_RED_BLACK)
279
280 /** Insert a new value under a string key */
281 #define se_tree_insert_string emem_tree_insert_string
282
283 /** Lookup the value under a string key */
284 #define se_tree_lookup_string emem_tree_lookup_string
285
286 /** Traverse a tree */
287 #define se_tree_foreach emem_tree_foreach
288
289
290 /* *******************************************************************
291  * Tree functions for PE memory allocation scope
292  * ******************************************************************* */
293 /* These trees have PErmanent allocation scope and will never be released
294  */
295 emem_tree_t *pe_tree_create(int type, const char *name) G_GNUC_MALLOC;
296 #define pe_tree_insert32 emem_tree_insert32
297 #define pe_tree_lookup32 emem_tree_lookup32
298 #define pe_tree_lookup32_le emem_tree_lookup32_le
299 #define pe_tree_insert32_array emem_tree_insert32_array
300 #define pe_tree_lookup32_array emem_tree_lookup32_array
301 #define pe_tree_insert_string emem_tree_insert_string
302 #define pe_tree_lookup_string emem_tree_lookup_string
303 #define pe_tree_foreach emem_tree_foreach
304
305
306
307 /* ******************************************************************
308  * Real tree functions
309  * ****************************************************************** */
310
311 /** This function is used to insert a node indexed by a guint32 key value.
312  * The data pointer should be allocated by the appropriate storage scope
313  * so that it will be released at the same time as the tree itself is
314  * destroyed.
315  */
316 void emem_tree_insert32(emem_tree_t *se_tree, guint32 key, void *data);
317
318 /** This function will look up a node in the tree indexed by a guint32 integer
319  * value.
320  */
321 void *emem_tree_lookup32(emem_tree_t *se_tree, guint32 key);
322
323 /** This function will look up a node in the tree indexed by a guint32 integer
324  * value.
325  * The function will return the node that has the largest key that is
326  * equal to or smaller than the search key, or NULL if no such key was
327  * found.
328  */
329 void *emem_tree_lookup32_le(emem_tree_t *se_tree, guint32 key);
330
331 typedef struct _emem_tree_key_t {
332         guint32 length;                 /**< length in guint32 words */
333         guint32 *key;
334 } emem_tree_key_t;
335
336 /** This function is used to insert a node indexed by a sequence of guint32
337  * key values.
338  * The data pointer should be allocated by SE allocators so that the
339  * data will be released at the same time as the tree itself is destroyed.
340  *
341  * Note: all the "key" members of the "key" argument MUST be aligned on
342  * 32-bit boundaries; otherwise, this code will crash on platforms such
343  * as SPARC that require aligned pointers.
344  *
345  * If you use ...32_array() calls you MUST make sure that every single node
346  * you add to a specific tree always has a key of exactly the same number of
347  * keylen words or things will most likely crash. Or at least that every single
348  * item that sits behind the same top level node always have exactly the same
349  * number of words.
350  *
351  * One way to guarantee this is the way that NFS does this for the
352  * nfs_name_snoop_known tree which holds filehandles for both v2 and v3.
353  * v2 filehandles are always 32 bytes (8 words) while v3 filehandles can have
354  * any length (though 32 bytes are most common).
355  * The NFS dissector handles this by providing a guint32 containing the length
356  * as the very first item in this vector :
357  *
358  *                      emem_tree_key_t fhkey[3];
359  *
360  *                      fhlen=nns->fh_length;
361  *                      fhkey[0].length=1;
362  *                      fhkey[0].key=&fhlen;
363  *                      fhkey[1].length=fhlen/4;
364  *                      fhkey[1].key=nns->fh;
365  *                      fhkey[2].length=0;
366  */
367 void emem_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data);
368
369 /** This function will look up a node in the tree indexed by a sequence of
370  * guint32 integer values.
371  */
372 void *emem_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key);
373
374 /** This function will look up a node in the tree indexed by a
375  * multi-part tree value.
376  * The function will return the node that has the largest key that is
377  * equal to or smaller than the search key, or NULL if no such key was
378  * found.
379  * Note:  The key returned will be "less" in key order.  The usefullness
380  * of the returned node must be verified prior to use.
381  */
382 void *emem_tree_lookup32_array_le(emem_tree_t *se_tree, emem_tree_key_t *key);
383
384 /** case insensitive strings as keys */
385 #define EMEM_TREE_STRING_NOCASE                 0x00000001
386 /** Insert a new value under a string key */
387 void emem_tree_insert_string(emem_tree_t* h, const gchar* k, void* v, guint32 flags);
388
389 /** Lookup the value under a string key */
390 void* emem_tree_lookup_string(emem_tree_t* h, const gchar* k, guint32 flags);
391
392
393 /** traverse a tree. if the callback returns TRUE the traversal will end */
394 typedef gboolean (*tree_foreach_func)(void *value, void *userdata);
395
396 gboolean emem_tree_foreach(emem_tree_t* emem_tree, tree_foreach_func callback, void *user_data);
397
398
399 /* ******************************************************************
400  * String buffers - Growable strings similar to GStrings
401  * ****************************************************************** */
402
403 typedef struct _emem_strbuf_t {
404     gchar *str;             /**< Points to the character data. It may move as text is       */
405                             /*  added. The str field is null-terminated and so can        */
406                             /*  be used as an ordinary C string.                          */
407     gsize len;              /**< strlen: ie: length of str not including trailing '\0'      */
408     gsize alloc_len;        /**< num bytes curently allocated for str: 1 .. MAX_STRBUF_LEN  */
409     gsize max_alloc_len;    /**< max num bytes to allocate for str: 1 .. MAX_STRBUF_LEN     */
410 } emem_strbuf_t;
411
412 /*
413  * The maximum length is limited to 64K. If you need something bigger, you
414  * should probably use an actual GString or GByteArray.
415  */
416
417 /**
418  * Allocate an ephemeral string buffer with "unlimited" size.
419  *
420  * @param init The initial string for the buffer, or NULL to allocate an initial zero-length string.
421  *
422  * @return A newly-allocated string buffer.
423  */
424 emem_strbuf_t *ep_strbuf_new(const gchar *init) G_GNUC_MALLOC;
425
426 /**
427  * Allocate an ephemeral string buffer suitable for the protocol tree.
428  * The string will never grow beyond the maximum tree item length.
429  *
430  * @param init The initial string for the buffer, or NULL to allocate an initial zero-length string.
431  *
432  * @return A newly-allocated string buffer.
433  */
434 emem_strbuf_t *ep_strbuf_new_label(const gchar *init) G_GNUC_MALLOC;
435
436 /**
437  * Allocate an ephemeral string buffer with enough initial space for alloc_len bytes
438  * and a maximum of max_alloc_len bytes.
439  *
440  * @param alloc_len The initial size of the buffer. This value can be 0, but a nonzero
441  * value is recommended.
442  * @param max_alloc_len The maximum size of the buffer. 0 means "unlimited" (within
443  * reason).
444  *
445  * @return A newly-allocated string buffer. str will be empty.
446  */
447 emem_strbuf_t *ep_strbuf_sized_new(gsize alloc_len, gsize max_alloc_len) G_GNUC_MALLOC;
448
449 /**
450  * Append vprintf-style formatted text to a string buffer.
451  *
452  * @param strbuf The ep_strbuf-allocated string buffer to append to.
453  * @param format A printf-style string format.
454  * @param ap The list of arguments to append.
455  */
456 void ep_strbuf_append_vprintf(emem_strbuf_t *strbuf, const gchar *format, va_list ap);
457
458 /**
459  * Apply printf-style formatted text to a string buffer.
460  *
461  * @param strbuf The ep_strbuf-allocated string buffer to set to.
462  * @param format A printf-style string format.
463  */
464 void ep_strbuf_printf(emem_strbuf_t *strbuf, const gchar *format, ...)
465      G_GNUC_PRINTF(2, 3);
466
467 /**
468  * Append printf-style formatted text to a string buffer.
469  *
470  * @param strbuf The ep_strbuf-allocated string buffer to append to.
471  * @param format A printf-style string format.
472  */
473 void ep_strbuf_append_printf(emem_strbuf_t *strbuf, const gchar *format, ...)
474     G_GNUC_PRINTF(2, 3);
475
476 /**
477  * Append a string to a string buffer.
478  *
479  * @param strbuf The ep_strbuf-allocated string buffer to append to.
480  * @param str A null-terminated string.
481  *
482  * @return strbuf
483  */
484 emem_strbuf_t *ep_strbuf_append(emem_strbuf_t *strbuf, const gchar *str);
485
486 /**
487  * Append a character to a string buffer.
488  *
489  * @param strbuf The ep_strbuf-allocated string buffer to append to.
490  * @param c The character to append.
491  *
492  * @return strbuf
493  */
494 emem_strbuf_t *ep_strbuf_append_c(emem_strbuf_t *strbuf, const gchar c);
495
496 /**
497  * Chop off the end of a string buffer.
498  *
499  * @param strbuf The ep_strbuf-allocated string buffer to append to.
500  * @param len The new string length.
501  *
502  * @return strbuf
503  */
504 emem_strbuf_t *ep_strbuf_truncate(emem_strbuf_t *strbuf, gsize len);
505
506 void emem_print_tree(emem_tree_t* emem_tree);
507
508 /* #define DEBUG_INTENSE_CANARY_CHECKS */
509
510 /** Helper to troubleshoot ep memory corruption.
511  * If compiled and the environment variable WIRESHARK_DEBUG_EP_INTENSE_CANARY exists
512  * it will check the canaries and when found corrupt stop there in the hope
513  * the corruptor is still there in the stack.
514  * Some checkpoints are already set in packet.c in strategic points
515  * before and after dissection of a frame or a dissector call.
516  */
517
518 #ifdef DEBUG_INTENSE_CANARY_CHECKS
519 void ep_check_canary_integrity(const char* fmt, ...)
520     G_GNUC_PRINTF(1, 2);
521 #define EP_CHECK_CANARY(args) ep_check_canary_integrity args
522 #else
523 #define EP_CHECK_CANARY(args)
524 #endif
525
526 /**
527  * Verify that the given pointer is of ephemeral type.
528  *
529  * @param ptr The pointer to verify
530  *
531  * @return TRUE if the pointer belongs to the ephemeral pool.
532  */
533 gboolean ep_verify_pointer(const void *ptr);
534 /**
535  * Verify that the given pointer is of seasonal type.
536  *
537  * @param ptr The pointer to verify
538  *
539  * @return TRUE if the pointer belongs to the seasonal pool.
540  */
541 gboolean se_verify_pointer(const void *ptr);
542
543 #endif /* emem.h */