epan/emem.c

   1 /* emem.c
   2  * Wireshark memory management and garbage collection functions
   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 #ifdef HAVE_CONFIG_H
  26 #include "config.h"
  27 #endif
  28
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <stdarg.h>
  33 #include <ctype.h>
  34
  35 #include <time.h>
  36 #ifdef HAVE_SYS_TIME_H
  37 #include <sys/time.h>
  38 #endif
  39
  40 #ifdef HAVE_UNISTD_H
  41 #include <unistd.h>
  42 #endif
  43
  44 #include <glib.h>
  45
  46 #include <proto.h>
  47 #include "emem.h"
  48
  49 #ifdef _WIN32
  50 #include <windows.h>    /* VirtualAlloc, VirtualProtect */
  51 #include <process.h>    /* getpid */
  52 #endif
  53
  54
  55 /*
  56  * Tools like Valgrind and ElectricFence don't work well with memchunks.
  57  * Uncomment the defines below to make {ep|se}_alloc() allocate each
  58  * object individually.
  59  */
  60 /* #define EP_DEBUG_FREE 1 */
  61 /* #define SE_DEBUG_FREE 1 */
  62
  63 /* Do we want to use guardpages? if available */
  64 #define WANT_GUARD_PAGES 1
  65
  66 /* Do we want to use canaries ? */
  67 #define DEBUG_USE_CANARIES 1
  68
  69 #ifdef WANT_GUARD_PAGES
  70 /* Add guard pages at each end of our allocated memory */
  71 #if defined(HAVE_SYSCONF) && defined(HAVE_MMAP) && defined(HAVE_MPROTECT) && defined(HAVE_STDINT_H)
  72 #include <stdint.h>
  73 #include <sys/types.h>
  74 #include <sys/mman.h>
  75 #if defined(MAP_ANONYMOUS)
  76 #define ANON_PAGE_MODE  (MAP_ANONYMOUS|MAP_PRIVATE)
  77 #elif defined(MAP_ANON)
  78 #define ANON_PAGE_MODE  (MAP_ANON|MAP_PRIVATE)
  79 #else
  80 #define ANON_PAGE_MODE  (MAP_PRIVATE)   /* have to map /dev/zero */
  81 #define NEED_DEV_ZERO
  82 #endif
  83 #ifdef NEED_DEV_ZERO
  84 #include <fcntl.h>
  85 static int dev_zero_fd;
  86 #define ANON_FD dev_zero_fd
  87 #else
  88 #define ANON_FD -1
  89 #endif
  90 #define USE_GUARD_PAGES 1
  91 #endif
  92 #endif
  93
  94 /* When required, allocate more memory from the OS in this size chunks */
  95 #define EMEM_PACKET_CHUNK_SIZE 10485760
  96
  97 /* The maximum number of allocations per chunk */
  98 #define EMEM_ALLOCS_PER_CHUNK (EMEM_PACKET_CHUNK_SIZE / 512)
  99
 100
 101 #ifdef DEBUG_USE_CANARIES
 102 #define EMEM_CANARY_SIZE 8
 103 #define EMEM_CANARY_DATA_SIZE (EMEM_CANARY_SIZE * 2 - 1)
 104
 105 /* this should be static, but if it were gdb would had problems finding it */
 106 guint8  ep_canary[EMEM_CANARY_DATA_SIZE], se_canary[EMEM_CANARY_DATA_SIZE];
 107 #endif /* DEBUG_USE_CANARIES */
 108
 109 typedef struct _emem_chunk_t {
 110         struct _emem_chunk_t *next;
 111         unsigned int    amount_free_init;
 112         unsigned int    amount_free;
 113         unsigned int    free_offset_init;
 114         unsigned int    free_offset;
 115         char *buf;
 116 #ifdef DEBUG_USE_CANARIES
 117 #if ! defined(EP_DEBUG_FREE) && ! defined(SE_DEBUG_FREE)
 118         unsigned int    c_count;
 119         void            *canary[EMEM_ALLOCS_PER_CHUNK];
 120         guint8          cmp_len[EMEM_ALLOCS_PER_CHUNK];
 121 #endif
 122 #endif /* DEBUG_USE_CANARIES */
 123 } emem_chunk_t;
 124
 125 typedef struct _emem_header_t {
 126   emem_chunk_t *free_list;
 127   emem_chunk_t *used_list;
 128 } emem_header_t;
 129
 130 static emem_header_t ep_packet_mem;
 131 static emem_header_t se_packet_mem;
 132
 133 #if !defined(SE_DEBUG_FREE)
 134 #if defined (_WIN32)
 135 static SYSTEM_INFO sysinfo;
 136 static OSVERSIONINFO versinfo;
 137 static int pagesize;
 138 #elif defined(USE_GUARD_PAGES)
 139 static intptr_t pagesize;
 140 #endif /* _WIN32 / USE_GUARD_PAGES */
 141 #endif /* SE_DEBUG_FREE */
 142
 143 #ifdef DEBUG_USE_CANARIES
 144 /*
 145  * Set a canary value to be placed between memchunks.
 146  */
 147 void
 148 emem_canary(guint8 *canary) {
 149         int i;
 150         static GRand   *rand_state = NULL;
 151
 152         if (rand_state == NULL) {
 153                 rand_state = g_rand_new();
 154         }
 155         for (i = 0; i < EMEM_CANARY_DATA_SIZE; i ++) {
 156                 canary[i] = (guint8) g_rand_int(rand_state);
 157         }
 158         return;
 159 }
 160
 161 #if !defined(SE_DEBUG_FREE)
 162 /*
 163  * Given an allocation size, return the amount of padding needed for
 164  * the canary value.
 165  */
 166 static guint8
 167 emem_canary_pad (size_t allocation) {
 168         guint8 pad;
 169
 170         pad = EMEM_CANARY_SIZE - (allocation % EMEM_CANARY_SIZE);
 171         if (pad < EMEM_CANARY_SIZE)
 172                 pad += EMEM_CANARY_SIZE;
 173
 174         return pad;
 175 }
 176 #endif
 177 #endif /* DEBUG_USE_CANARIES */
 178
 179 /* used for debugging canaries, will block */
 180 #ifdef DEBUG_INTENSE_CANARY_CHECKS
 181 gboolean intense_canary_checking = FALSE;
 182
 183 /*  used to intensivelly check ep canaries
 184  */
 185 void ep_check_canary_integrity(const char* fmt, ...) {
 186     va_list ap;
 187     static gchar there[128] = {
 188         'L','a','u','n','c','h',0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 189         0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 190         0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 191         0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
 192     gchar here[128];
 193         emem_chunk_t* npc = NULL;
 194
 195     if (! intense_canary_checking ) return;
 196
 197     here[126] = '\0';
 198     here[127] = '\0';
 199
 200     va_start(ap,fmt);
 201     g_vsnprintf(here, 126,fmt, ap);
 202     va_end(ap);
 203
 204         for (npc = ep_packet_mem.free_list; npc != NULL; npc = npc->next) {
 205         static unsigned i_ctr;
 206
 207         if (npc->c_count > 0x00ffffff) {
 208             g_error("ep_packet_mem.free_list was corrupted\nbetween: %s\nand: %s",there, here);
 209         }
 210
 211                 for (i_ctr = 0; i_ctr < npc->c_count; i_ctr++) {
 212                         if (memcmp(npc->canary[i_ctr], &ep_canary, npc->cmp_len[i_ctr]) != 0) {
 213                                 g_error("Per-packet memory corrupted\nbetween: %s\nand: %s",there, here);
 214             }
 215                 }
 216     }
 217
 218     strncpy(there,here,126);
 219
 220 }
 221 #endif
 222
 223
 224 /* Initialize the packet-lifetime memory allocation pool.
 225  * This function should be called only once when Wireshark or TShark starts
 226  * up.
 227  */
 228 void
 229 ep_init_chunk(void)
 230 {
 231         ep_packet_mem.free_list=NULL;
 232         ep_packet_mem.used_list=NULL;
 233
 234 #ifdef DEBUG_INTENSE_CANARY_CHECKS
 235     intense_canary_checking = (gboolean)getenv("WIRESHARK_DEBUG_EP_CANARY");
 236 #endif
 237
 238 #ifdef DEBUG_USE_CANARIES
 239         emem_canary(ep_canary);
 240 #endif /* DEBUG_USE_CANARIES */
 241
 242 #if !defined(SE_DEBUG_FREE)
 243 #if defined (_WIN32)
 244         /* Set up our guard page info for Win32 */
 245         GetSystemInfo(&sysinfo);
 246         pagesize = sysinfo.dwPageSize;
 247
 248         /* calling GetVersionEx using the OSVERSIONINFO structure.
 249          * OSVERSIONINFOEX requires Win NT4 with SP6 or newer NT Versions.
 250          * OSVERSIONINFOEX will fail on Win9x and older NT Versions.
 251          * See also:
 252          * http://msdn.microsoft.com/library/en-us/sysinfo/base/getversionex.asp
 253          * http://msdn.microsoft.com/library/en-us/sysinfo/base/osversioninfo_str.asp
 254          * http://msdn.microsoft.com/library/en-us/sysinfo/base/osversioninfoex_str.asp
 255          */
 256         versinfo.dwOSVersionInfoSize = sizeof(OSVERSIONINFO);
 257         GetVersionEx(&versinfo);
 258
 259 #elif defined(USE_GUARD_PAGES)
 260         pagesize = sysconf(_SC_PAGESIZE);
 261 #ifdef NEED_DEV_ZERO
 262         dev_zero_fd = ws_open("/dev/zero", O_RDWR);
 263         g_assert(dev_zero_fd != -1);
 264 #endif
 265 #endif /* _WIN32 / USE_GUARD_PAGES */
 266 #endif /* SE_DEBUG_FREE */
 267
 268
 269 }
 270 /* Initialize the capture-lifetime memory allocation pool.
 271  * This function should be called only once when Wireshark or TShark starts
 272  * up.
 273  */
 274 void
 275 se_init_chunk(void)
 276 {
 277         se_packet_mem.free_list=NULL;
 278         se_packet_mem.used_list=NULL;
 279
 280 #ifdef DEBUG_USE_CANARIES
 281         emem_canary(se_canary);
 282 #endif /* DEBUG_USE_CANARIES */
 283 }
 284
 285 #if !defined(SE_DEBUG_FREE)
 286 static void
 287 emem_create_chunk(emem_chunk_t **free_list) {
 288 #if defined (_WIN32)
 289         BOOL ret;
 290         char *buf_end, *prot1, *prot2;
 291         DWORD oldprot;
 292 #elif defined(USE_GUARD_PAGES)
 293         int ret;
 294         char *buf_end, *prot1, *prot2;
 295 #endif /* _WIN32 / USE_GUARD_PAGES */
 296         /* we dont have any free data, so we must allocate a new one */
 297         if(!*free_list){
 298                 emem_chunk_t *npc;
 299                 npc = g_malloc(sizeof(emem_chunk_t));
 300                 npc->next = NULL;
 301 #ifdef DEBUG_USE_CANARIES
 302 #if ! defined(EP_DEBUG_FREE) && ! defined(SE_DEBUG_FREE)
 303                 npc->c_count = 0;
 304 #endif
 305 #endif /* DEBUG_USE_CANARIES */
 306
 307                 *free_list = npc;
 308 #if defined (_WIN32)
 309                 /*
 310                  * MSDN documents VirtualAlloc/VirtualProtect at
 311                  * http://msdn.microsoft.com/library/en-us/memory/base/creating_guard_pages.asp
 312                  */
 313
 314                 /* XXX - is MEM_COMMIT|MEM_RESERVE correct? */
 315                 npc->buf = VirtualAlloc(NULL, EMEM_PACKET_CHUNK_SIZE,
 316                         MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE);
 317                 if(npc->buf == NULL) {
 318                     THROW(OutOfMemoryError);
 319                 }
 320                 buf_end = npc->buf + EMEM_PACKET_CHUNK_SIZE;
 321
 322                 /* Align our guard pages on page-sized boundaries */
 323                 prot1 = (char *) ((((int) npc->buf + pagesize - 1) / pagesize) * pagesize);
 324                 prot2 = (char *) ((((int) buf_end - (1 * pagesize)) / pagesize) * pagesize);
 325
 326                 ret = VirtualProtect(prot1, pagesize, PAGE_NOACCESS, &oldprot);
 327                 g_assert(ret != 0 || versinfo.dwPlatformId == VER_PLATFORM_WIN32_WINDOWS);
 328                 ret = VirtualProtect(prot2, pagesize, PAGE_NOACCESS, &oldprot);
 329                 g_assert(ret != 0 || versinfo.dwPlatformId == VER_PLATFORM_WIN32_WINDOWS);
 330
 331                 npc->amount_free_init = prot2 - prot1 - pagesize;
 332                 npc->amount_free = npc->amount_free_init;
 333                 npc->free_offset_init = (prot1 - npc->buf) + pagesize;
 334                 npc->free_offset = npc->free_offset_init;
 335
 336 #elif defined(USE_GUARD_PAGES)
 337                 npc->buf = mmap(NULL, EMEM_PACKET_CHUNK_SIZE,
 338                         PROT_READ|PROT_WRITE, ANON_PAGE_MODE, ANON_FD, 0);
 339                 if(npc->buf == MAP_FAILED) {
 340                     /* XXX - what do we have to cleanup here? */
 341                     THROW(OutOfMemoryError);
 342                 }
 343                 buf_end = npc->buf + EMEM_PACKET_CHUNK_SIZE;
 344
 345                 /* Align our guard pages on page-sized boundaries */
 346                 prot1 = (char *) ((((intptr_t) npc->buf + pagesize - 1) / pagesize) * pagesize);
 347                 prot2 = (char *) ((((intptr_t) buf_end - (1 * pagesize)) / pagesize) * pagesize);
 348                 ret = mprotect(prot1, pagesize, PROT_NONE);
 349                 g_assert(ret != -1);
 350                 ret = mprotect(prot2, pagesize, PROT_NONE);
 351                 g_assert(ret != -1);
 352
 353                 npc->amount_free_init = prot2 - prot1 - pagesize;
 354                 npc->amount_free = npc->amount_free_init;
 355                 npc->free_offset_init = (prot1 - npc->buf) + pagesize;
 356                 npc->free_offset = npc->free_offset_init;
 357
 358 #else /* Is there a draft in here? */
 359                 npc->buf = malloc(EMEM_PACKET_CHUNK_SIZE);
 360                 if(npc->buf == NULL) {
 361                     THROW(OutOfMemoryError);
 362                 }
 363                 npc->amount_free_init = EMEM_PACKET_CHUNK_SIZE;
 364                 npc->amount_free = npc->amount_free_init;
 365                 npc->free_offset_init = 0;
 366                 npc->free_offset = npc->free_offset_init;
 367 #endif /* USE_GUARD_PAGES */
 368         }
 369 }
 370 #endif
 371
 372 /* allocate 'size' amount of memory with an allocation lifetime until the
 373  * next packet.
 374  */
 375 void *
 376 ep_alloc(size_t size)
 377 {
 378         void *buf;
 379 #ifndef EP_DEBUG_FREE
 380 #ifdef DEBUG_USE_CANARIES
 381         void *cptr;
 382         guint8 pad = emem_canary_pad(size);
 383 #else
 384         static guint8 pad=8;
 385 #endif /* DEBUG_USE_CANARIES */
 386         emem_chunk_t *free_list;
 387 #endif
 388
 389 #ifndef EP_DEBUG_FREE
 390         /* Round up to an 8 byte boundary.  Make sure we have at least
 391          * 8 pad bytes for our canary.
 392          */
 393         size += pad;
 394
 395         /* make sure we dont try to allocate too much (arbitrary limit) */
 396         DISSECTOR_ASSERT(size<(EMEM_PACKET_CHUNK_SIZE>>2));
 397
 398         emem_create_chunk(&ep_packet_mem.free_list);
 399
 400         /* oops, we need to allocate more memory to serve this request
 401          * than we have free. move this node to the used list and try again
 402          */
 403         if(size>ep_packet_mem.free_list->amount_free
 404 #ifdef DEBUG_USE_CANARIES
 405               || ep_packet_mem.free_list->c_count >= EMEM_ALLOCS_PER_CHUNK
 406 #endif /* DEBUG_USE_CANARIES */
 407         ){
 408                 emem_chunk_t *npc;
 409                 npc=ep_packet_mem.free_list;
 410                 ep_packet_mem.free_list=ep_packet_mem.free_list->next;
 411                 npc->next=ep_packet_mem.used_list;
 412                 ep_packet_mem.used_list=npc;
 413         }
 414
 415         emem_create_chunk(&ep_packet_mem.free_list);
 416
 417         free_list = ep_packet_mem.free_list;
 418
 419         buf = free_list->buf + free_list->free_offset;
 420
 421         free_list->amount_free -= size;
 422         free_list->free_offset += size;
 423
 424 #ifdef DEBUG_USE_CANARIES
 425         cptr = (char *)buf + size - pad;
 426         memcpy(cptr, &ep_canary, pad);
 427         free_list->canary[free_list->c_count] = cptr;
 428         free_list->cmp_len[free_list->c_count] = pad;
 429         free_list->c_count++;
 430 #endif /* DEBUG_USE_CANARIES */
 431
 432 #else /* EP_DEBUG_FREE */
 433         emem_chunk_t *npc;
 434
 435         npc=g_malloc(sizeof(emem_chunk_t));
 436         npc->next=ep_packet_mem.used_list;
 437         npc->amount_free=size;
 438         npc->free_offset=0;
 439         npc->buf=g_malloc(size);
 440         buf = npc->buf;
 441         ep_packet_mem.used_list=npc;
 442 #endif /* EP_DEBUG_FREE */
 443
 444         return buf;
 445 }
 446 /* allocate 'size' amount of memory with an allocation lifetime until the
 447  * next capture.
 448  */
 449 void *
 450 se_alloc(size_t size)
 451 {
 452         void *buf;
 453 #ifndef SE_DEBUG_FREE
 454 #ifdef DEBUG_USE_CANARIES
 455         void *cptr;
 456         guint8 pad = emem_canary_pad(size);
 457 #else
 458         static guint8 pad=8;
 459 #endif /* DEBUG_USE_CANARIES */
 460         emem_chunk_t *free_list;
 461 #endif
 462
 463 #ifndef SE_DEBUG_FREE
 464         /* Round up to an 8 byte boundary.  Make sure we have at least
 465          * 8 pad bytes for our canary.
 466          */
 467         size += pad;
 468
 469         /* make sure we dont try to allocate too much (arbitrary limit) */
 470         DISSECTOR_ASSERT(size<(EMEM_PACKET_CHUNK_SIZE>>2));
 471
 472         emem_create_chunk(&se_packet_mem.free_list);
 473
 474         /* oops, we need to allocate more memory to serve this request
 475          * than we have free. move this node to the used list and try again
 476          */
 477         if(size>se_packet_mem.free_list->amount_free
 478 #ifdef DEBUG_USE_CANARIES
 479         || se_packet_mem.free_list->c_count >= EMEM_ALLOCS_PER_CHUNK
 480 #endif /* DEBUG_USE_CANARIES */
 481         ){
 482                 emem_chunk_t *npc;
 483                 npc=se_packet_mem.free_list;
 484                 se_packet_mem.free_list=se_packet_mem.free_list->next;
 485                 npc->next=se_packet_mem.used_list;
 486                 se_packet_mem.used_list=npc;
 487         }
 488
 489         emem_create_chunk(&se_packet_mem.free_list);
 490
 491         free_list = se_packet_mem.free_list;
 492
 493         buf = free_list->buf + free_list->free_offset;
 494
 495         free_list->amount_free -= size;
 496         free_list->free_offset += size;
 497
 498 #ifdef DEBUG_USE_CANARIES
 499         cptr = (char *)buf + size - pad;
 500         memcpy(cptr, &se_canary, pad);
 501         free_list->canary[free_list->c_count] = cptr;
 502         free_list->cmp_len[free_list->c_count] = pad;
 503         free_list->c_count++;
 504 #endif /* DEBUG_USE_CANARIES */
 505
 506 #else /* SE_DEBUG_FREE */
 507         emem_chunk_t *npc;
 508
 509         npc=g_malloc(sizeof(emem_chunk_t));
 510         npc->next=se_packet_mem.used_list;
 511         npc->amount_free=size;
 512         npc->free_offset=0;
 513         npc->buf=g_malloc(size);
 514         buf = npc->buf;
 515         se_packet_mem.used_list=npc;
 516 #endif /* SE_DEBUG_FREE */
 517
 518         return buf;
 519 }
 520
 521
 522 void* ep_alloc0(size_t size) {
 523         return memset(ep_alloc(size),'\0',size);
 524 }
 525
 526 gchar* ep_strdup(const gchar* src) {
 527         guint len = strlen(src);
 528         gchar* dst;
 529
 530         dst = strncpy(ep_alloc(len+1), src, len);
 531
 532         dst[len] = '\0';
 533
 534         return dst;
 535 }
 536
 537 gchar* ep_strndup(const gchar* src, size_t len) {
 538         gchar* dst = ep_alloc(len+1);
 539         guint i;
 540
 541         for (i = 0; (i < len) && src[i]; i++)
 542                 dst[i] = src[i];
 543
 544         dst[i] = '\0';
 545
 546         return dst;
 547 }
 548
 549 void* ep_memdup(const void* src, size_t len) {
 550         return memcpy(ep_alloc(len), src, len);
 551 }
 552
 553 gchar* ep_strdup_vprintf(const gchar* fmt, va_list ap) {
 554         va_list ap2;
 555         guint len;
 556         gchar* dst;
 557
 558         G_VA_COPY(ap2, ap);
 559
 560         len = g_printf_string_upper_bound(fmt, ap);
 561
 562         dst = ep_alloc(len+1);
 563         g_vsnprintf (dst, len, fmt, ap2);
 564         va_end(ap2);
 565
 566         return dst;
 567 }
 568
 569 gchar* ep_strdup_printf(const gchar* fmt, ...) {
 570         va_list ap;
 571         gchar* dst;
 572
 573         va_start(ap,fmt);
 574         dst = ep_strdup_vprintf(fmt, ap);
 575         va_end(ap);
 576         return dst;
 577 }
 578
 579 gchar** ep_strsplit(const gchar* string, const gchar* sep, int max_tokens) {
 580         gchar* splitted;
 581         gchar* s;
 582         guint tokens;
 583         guint str_len;
 584         guint sep_len;
 585         guint i;
 586         gchar** vec;
 587         enum { AT_START, IN_PAD, IN_TOKEN } state;
 588         guint curr_tok = 0;
 589
 590         if ( ! string
 591                  || ! sep
 592                  || ! sep[0])
 593                 return NULL;
 594
 595         s = splitted = ep_strdup(string);
 596         str_len = strlen(splitted);
 597         sep_len = strlen(sep);
 598
 599         if (max_tokens < 1) max_tokens = INT_MAX;
 600
 601         tokens = 1;
 602
 603
 604         while (tokens <= (guint)max_tokens && ( s = strstr(s,sep) )) {
 605                 tokens++;
 606
 607                 for(i=0; i < sep_len; i++ )
 608                         s[i] = '\0';
 609
 610                 s += sep_len;
 611
 612         }
 613
 614         vec = ep_alloc_array(gchar*,tokens+1);
 615         state = AT_START;
 616
 617         for (i=0; i< str_len; i++) {
 618                 switch(state) {
 619                         case AT_START:
 620                                 switch(splitted[i]) {
 621                                         case '\0':
 622                                                 state  = IN_PAD;
 623                                                 continue;
 624                                         default:
 625                                                 vec[curr_tok] = &(splitted[i]);
 626                                                 curr_tok++;
 627                                                 state = IN_TOKEN;
 628                                                 continue;
 629                                 }
 630                         case IN_TOKEN:
 631                                 switch(splitted[i]) {
 632                                         case '\0':
 633                                                 state = IN_PAD;
 634                                         default:
 635                                                 continue;
 636                                 }
 637                         case IN_PAD:
 638                                 switch(splitted[i]) {
 639                                         default:
 640                                                 vec[curr_tok] = &(splitted[i]);
 641                                                 curr_tok++;
 642                                                 state = IN_TOKEN;
 643                                         case '\0':
 644                                                 continue;
 645                                 }
 646                 }
 647         }
 648
 649         vec[curr_tok] = NULL;
 650
 651         return vec;
 652 }
 653
 654
 655
 656 void* se_alloc0(size_t size) {
 657         return memset(se_alloc(size),'\0',size);
 658 }
 659
 660 /* If str is NULL, just return the string "<NULL>" so that the callers dont
 661  * have to bother checking it.
 662  */
 663 gchar* se_strdup(const gchar* src) {
 664         guint len;
 665         gchar* dst;
 666
 667         if(!src){
 668                 return "<NULL>";
 669         }
 670
 671         len = strlen(src);
 672         dst = strncpy(se_alloc(len+1), src, len);
 673
 674         dst[len] = '\0';
 675
 676         return dst;
 677 }
 678
 679 gchar* se_strndup(const gchar* src, size_t len) {
 680         gchar* dst = se_alloc(len+1);
 681         guint i;
 682
 683         for (i = 0; (i < len) && src[i]; i++)
 684                 dst[i] = src[i];
 685
 686         dst[i] = '\0';
 687
 688         return dst;
 689 }
 690
 691 void* se_memdup(const void* src, size_t len) {
 692         return memcpy(se_alloc(len), src, len);
 693 }
 694
 695 gchar* se_strdup_vprintf(const gchar* fmt, va_list ap) {
 696         va_list ap2;
 697         guint len;
 698         gchar* dst;
 699
 700         G_VA_COPY(ap2, ap);
 701
 702         len = g_printf_string_upper_bound(fmt, ap);
 703
 704         dst = se_alloc(len+1);
 705         g_vsnprintf (dst, len, fmt, ap2);
 706         va_end(ap2);
 707
 708         return dst;
 709 }
 710
 711 gchar* se_strdup_printf(const gchar* fmt, ...) {
 712         va_list ap;
 713         gchar* dst;
 714
 715         va_start(ap,fmt);
 716         dst = se_strdup_vprintf(fmt, ap);
 717         va_end(ap);
 718         return dst;
 719 }
 720
 721
 722 /* release all allocated memory back to the pool.
 723  */
 724 void
 725 ep_free_all(void)
 726 {
 727         emem_chunk_t *npc;
 728 #ifndef EP_DEBUG_FREE
 729 #ifdef DEBUG_USE_CANARIES
 730         guint i;
 731 #endif /* DEBUG_USE_CANARIES */
 732 #endif
 733
 734         /* move all used chunks over to the free list */
 735         while(ep_packet_mem.used_list){
 736                 npc=ep_packet_mem.used_list;
 737                 ep_packet_mem.used_list=ep_packet_mem.used_list->next;
 738                 npc->next=ep_packet_mem.free_list;
 739                 ep_packet_mem.free_list=npc;
 740         }
 741
 742         /* clear them all out */
 743         npc = ep_packet_mem.free_list;
 744         while (npc != NULL) {
 745 #ifndef EP_DEBUG_FREE
 746 #ifdef DEBUG_USE_CANARIES
 747                 for (i = 0; i < npc->c_count; i++) {
 748                         if (memcmp(npc->canary[i], &ep_canary, npc->cmp_len[i]) != 0)
 749                                 g_error("Per-packet memory corrupted.");
 750                 }
 751                 npc->c_count = 0;
 752 #endif /* DEBUG_USE_CANARIES */
 753                 npc->amount_free = npc->amount_free_init;
 754                 npc->free_offset = npc->free_offset_init;
 755                 npc = npc->next;
 756 #else /* EP_DEBUG_FREE */
 757                 emem_chunk_t *next = npc->next;
 758
 759                 g_free(npc->buf);
 760                 g_free(npc);
 761                 npc = next;
 762 #endif /* EP_DEBUG_FREE */
 763         }
 764
 765 #ifdef EP_DEBUG_FREE
 766         ep_init_chunk();
 767 #endif
 768 }
 769 /* release all allocated memory back to the pool.
 770  */
 771 void
 772 se_free_all(void)
 773 {
 774         emem_chunk_t *npc;
 775         emem_tree_t *se_tree_list;
 776 #ifndef SE_DEBUG_FREE
 777 #ifdef DEBUG_USE_CANARIES
 778         guint i;
 779 #endif /* DEBUG_USE_CANARIES */
 780 #endif
 781
 782         /* move all used chunks over to the free list */
 783         while(se_packet_mem.used_list){
 784                 npc=se_packet_mem.used_list;
 785                 se_packet_mem.used_list=se_packet_mem.used_list->next;
 786                 npc->next=se_packet_mem.free_list;
 787                 se_packet_mem.free_list=npc;
 788         }
 789
 790         /* clear them all out */
 791         npc = se_packet_mem.free_list;
 792         while (npc != NULL) {
 793 #ifndef SE_DEBUG_FREE
 794 #ifdef DEBUG_USE_CANARIES
 795                 for (i = 0; i < npc->c_count; i++) {
 796                         if (memcmp(npc->canary[i], &se_canary, npc->cmp_len[i]) != 0)
 797                                 g_error("Per-session memory corrupted.");
 798                 }
 799                 npc->c_count = 0;
 800 #endif /* DEBUG_USE_CANARIES */
 801                 npc->amount_free = npc->amount_free_init;
 802                 npc->free_offset = npc->free_offset_init;
 803                 npc = npc->next;
 804 #else /* SE_DEBUG_FREE */
 805                 emem_chunk_t *next = npc->next;
 806
 807                 g_free(npc->buf);
 808                 g_free(npc);
 809                 npc = next;
 810 #endif /* SE_DEBUG_FREE */
 811         }
 812
 813 #ifdef SE_DEBUG_FREE
 814                 se_init_chunk();
 815 #endif
 816
 817         /* release/reset all se allocated trees */
 818         for(se_tree_list=se_trees;se_tree_list;se_tree_list=se_tree_list->next){
 819                 se_tree_list->tree=NULL;
 820         }
 821 }
 822
 823
 824 ep_stack_t ep_stack_new(void) {
 825     ep_stack_t s = ep_new(struct _ep_stack_frame_t*);
 826     *s = ep_new0(struct _ep_stack_frame_t);
 827     return s;
 828 }
 829
 830 /*  for ep_stack_t we'll keep the popped frames so we reuse them instead
 831 of allocating new ones.
 832 */
 833
 834
 835 void* ep_stack_push(ep_stack_t stack, void* data) {
 836     struct _ep_stack_frame_t* frame;
 837     struct _ep_stack_frame_t* head = (*stack);
 838
 839     if (head->above) {
 840         frame = head->above;
 841     } else {
 842        frame = ep_new(struct _ep_stack_frame_t);
 843        head->above = frame;
 844        frame->below = head;
 845        frame->above = NULL;
 846     }
 847
 848     frame->payload = data;
 849     (*stack) = frame;
 850
 851     return data;
 852 }
 853
 854 void* ep_stack_pop(ep_stack_t stack) {
 855
 856     if ((*stack)->below) {
 857         (*stack) = (*stack)->below;
 858         return (*stack)->above->payload;
 859     } else {
 860         return NULL;
 861     }
 862 }
 863
 864
 865
 866 #ifdef REMOVED
 867 void print_tree_item(emem_tree_node_t *node, int level){
 868         int i;
 869         for(i=0;i<level;i++){
 870                 printf("   ");
 871         }
 872         printf("%s  KEY:0x%08x node:0x%08x parent:0x%08x left:0x%08x right:0x%08x\n",node->u.rb_color==EMEM_TREE_RB_COLOR_BLACK?"BLACK":"RED",node->key32,(int)node,(int)node->parent,(int)node->left,(int)node->right);
 873         if(node->left)
 874                 print_tree_item(node->left,level+1);
 875         if(node->right)
 876                 print_tree_item(node->right,level+1);
 877 }
 878
 879 void print_tree(emem_tree_node_t *node){
 880         if(!node){
 881                 return;
 882         }
 883         while(node->parent){
 884                 node=node->parent;
 885         }
 886         print_tree_item(node,0);
 887 }
 888 #endif
 889
 890
 891
 892 /* routines to manage se allocated red-black trees */
 893 emem_tree_t *se_trees=NULL;
 894
 895 emem_tree_t *
 896 se_tree_create(int type, const char *name)
 897 {
 898         emem_tree_t *tree_list;
 899
 900         tree_list=malloc(sizeof(emem_tree_t));
 901         tree_list->next=se_trees;
 902         tree_list->type=type;
 903         tree_list->tree=NULL;
 904         tree_list->name=name;
 905         tree_list->malloc=se_alloc;
 906         se_trees=tree_list;
 907
 908         return tree_list;
 909 }
 910
 911
 912
 913 void *
 914 emem_tree_lookup32(emem_tree_t *se_tree, guint32 key)
 915 {
 916         emem_tree_node_t *node;
 917
 918         node=se_tree->tree;
 919
 920         while(node){
 921                 if(key==node->key32){
 922                         return node->data;
 923                 }
 924                 if(key<node->key32){
 925                         node=node->left;
 926                         continue;
 927                 }
 928                 if(key>node->key32){
 929                         node=node->right;
 930                         continue;
 931                 }
 932         }
 933         return NULL;
 934 }
 935
 936 void *
 937 emem_tree_lookup32_le(emem_tree_t *se_tree, guint32 key)
 938 {
 939         emem_tree_node_t *node;
 940
 941         node=se_tree->tree;
 942
 943         if(!node){
 944                 return NULL;
 945         }
 946
 947
 948         while(node){
 949                 if(key==node->key32){
 950                         return node->data;
 951                 }
 952                 if(key<node->key32){
 953                         if(node->left){
 954                                 node=node->left;
 955                                 continue;
 956                         } else {
 957                                 break;
 958                         }
 959                 }
 960                 if(key>node->key32){
 961                         if(node->right){
 962                                 node=node->right;
 963                                 continue;
 964                         } else {
 965                                 break;
 966                         }
 967                 }
 968         }
 969
 970
 971         /* If we are still at the root of the tree this means that this node
 972          * is either smaller thant the search key and then we return this
 973          * node or else there is no smaller key availabel and then
 974          * we return NULL.
 975          */
 976         if(!node->parent){
 977                 if(key>node->key32){
 978                         return node->data;
 979                 } else {
 980                         return NULL;
 981                 }
 982         }
 983
 984         if(node->parent->left==node){
 985                 /* left child */
 986
 987                 if(key>node->key32){
 988                         /* if this is a left child and its key is smaller than
 989                          * the search key, then this is the node we want.
 990                          */
 991                         return node->data;
 992                 } else {
 993                         /* if this is a left child and its key is bigger than
 994                          * the search key, we have to check if any
 995                          * of our ancestors are smaller than the search key.
 996                          */
 997                         while(node){
 998                                 if(key>node->key32){
 999                                         return node->data;
1000                                 }
1001                                 node=node->parent;
1002                         }
1003                         return NULL;
1004                 }
1005         } else {
1006                 /* right child */
1007
1008                 if(node->key32<key){
1009                         /* if this is the right child and its key is smaller
1010                          * than the search key then this is the one we want.
1011                          */
1012                         return node->data;
1013                 } else {
1014                         /* if this is the right child and its key is larger
1015                          * than the search key then our parent is the one we
1016                          * want.
1017                          */
1018                         return node->parent->data;
1019                 }
1020         }
1021
1022 }
1023
1024
1025 static inline emem_tree_node_t *
1026 emem_tree_parent(emem_tree_node_t *node)
1027 {
1028         return node->parent;
1029 }
1030
1031 static inline emem_tree_node_t *
1032 emem_tree_grandparent(emem_tree_node_t *node)
1033 {
1034         emem_tree_node_t *parent;
1035
1036         parent=emem_tree_parent(node);
1037         if(parent){
1038                 return parent->parent;
1039         }
1040         return NULL;
1041 }
1042 static inline emem_tree_node_t *
1043 emem_tree_uncle(emem_tree_node_t *node)
1044 {
1045         emem_tree_node_t *parent, *grandparent;
1046
1047         parent=emem_tree_parent(node);
1048         if(!parent){
1049                 return NULL;
1050         }
1051         grandparent=emem_tree_parent(parent);
1052         if(!grandparent){
1053                 return NULL;
1054         }
1055         if(parent==grandparent->left){
1056                 return grandparent->right;
1057         }
1058         return grandparent->left;
1059 }
1060
1061 static inline void rb_insert_case1(emem_tree_t *se_tree, emem_tree_node_t *node);
1062 static inline void rb_insert_case2(emem_tree_t *se_tree, emem_tree_node_t *node);
1063
1064 static inline void
1065 rotate_left(emem_tree_t *se_tree, emem_tree_node_t *node)
1066 {
1067         if(node->parent){
1068                 if(node->parent->left==node){
1069                         node->parent->left=node->right;
1070                 } else {
1071                         node->parent->right=node->right;
1072                 }
1073         } else {
1074                 se_tree->tree=node->right;
1075         }
1076         node->right->parent=node->parent;
1077         node->parent=node->right;
1078         node->right=node->right->left;
1079         if(node->right){
1080                 node->right->parent=node;
1081         }
1082         node->parent->left=node;
1083 }
1084
1085 static inline void
1086 rotate_right(emem_tree_t *se_tree, emem_tree_node_t *node)
1087 {
1088         if(node->parent){
1089                 if(node->parent->left==node){
1090                         node->parent->left=node->left;
1091                 } else {
1092                         node->parent->right=node->left;
1093                 }
1094         } else {
1095                 se_tree->tree=node->left;
1096         }
1097         node->left->parent=node->parent;
1098         node->parent=node->left;
1099         node->left=node->left->right;
1100         if(node->left){
1101                 node->left->parent=node;
1102         }
1103         node->parent->right=node;
1104 }
1105
1106 static inline void
1107 rb_insert_case5(emem_tree_t *se_tree, emem_tree_node_t *node)
1108 {
1109         emem_tree_node_t *grandparent;
1110         emem_tree_node_t *parent;
1111
1112         parent=emem_tree_parent(node);
1113         grandparent=emem_tree_parent(parent);
1114         parent->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1115         grandparent->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1116         if( (node==parent->left) && (parent==grandparent->left) ){
1117                 rotate_right(se_tree, grandparent);
1118         } else {
1119                 rotate_left(se_tree, grandparent);
1120         }
1121 }
1122
1123 static inline void
1124 rb_insert_case4(emem_tree_t *se_tree, emem_tree_node_t *node)
1125 {
1126         emem_tree_node_t *grandparent;
1127         emem_tree_node_t *parent;
1128
1129         parent=emem_tree_parent(node);
1130         grandparent=emem_tree_parent(parent);
1131         if(!grandparent){
1132                 return;
1133         }
1134         if( (node==parent->right) && (parent==grandparent->left) ){
1135                 rotate_left(se_tree, parent);
1136                 node=node->left;
1137         } else if( (node==parent->left) && (parent==grandparent->right) ){
1138                 rotate_right(se_tree, parent);
1139                 node=node->right;
1140         }
1141         rb_insert_case5(se_tree, node);
1142 }
1143
1144 static inline void
1145 rb_insert_case3(emem_tree_t *se_tree, emem_tree_node_t *node)
1146 {
1147         emem_tree_node_t *grandparent;
1148         emem_tree_node_t *parent;
1149         emem_tree_node_t *uncle;
1150
1151         uncle=emem_tree_uncle(node);
1152         if(uncle && (uncle->u.rb_color==EMEM_TREE_RB_COLOR_RED)){
1153                 parent=emem_tree_parent(node);
1154                 parent->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1155                 uncle->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1156                 grandparent=emem_tree_grandparent(node);
1157                 grandparent->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1158                 rb_insert_case1(se_tree, grandparent);
1159         } else {
1160                 rb_insert_case4(se_tree, node);
1161         }
1162 }
1163
1164 static inline void
1165 rb_insert_case2(emem_tree_t *se_tree, emem_tree_node_t *node)
1166 {
1167         emem_tree_node_t *parent;
1168
1169         parent=emem_tree_parent(node);
1170         /* parent is always non-NULL here */
1171         if(parent->u.rb_color==EMEM_TREE_RB_COLOR_BLACK){
1172                 return;
1173         }
1174         rb_insert_case3(se_tree, node);
1175 }
1176
1177 static inline void
1178 rb_insert_case1(emem_tree_t *se_tree, emem_tree_node_t *node)
1179 {
1180         emem_tree_node_t *parent;
1181
1182         parent=emem_tree_parent(node);
1183         if(!parent){
1184                 node->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1185                 return;
1186         }
1187         rb_insert_case2(se_tree, node);
1188 }
1189
1190 /* insert a new node in the tree. if this node matches an already existing node
1191  * then just replace the data for that node */
1192 void
1193 emem_tree_insert32(emem_tree_t *se_tree, guint32 key, void *data)
1194 {
1195         emem_tree_node_t *node;
1196
1197         node=se_tree->tree;
1198
1199         /* is this the first node ?*/
1200         if(!node){
1201                 node=se_tree->malloc(sizeof(emem_tree_node_t));
1202                 switch(se_tree->type){
1203                 case EMEM_TREE_TYPE_RED_BLACK:
1204                         node->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1205                         break;
1206                 }
1207                 node->parent=NULL;
1208                 node->left=NULL;
1209                 node->right=NULL;
1210                 node->key32=key;
1211                 node->data=data;
1212                 node->u.is_subtree = EMEM_TREE_NODE_IS_DATA;
1213                 se_tree->tree=node;
1214                 return;
1215         }
1216
1217         /* it was not the new root so walk the tree until we find where to
1218          * insert this new leaf.
1219          */
1220         while(1){
1221                 /* this node already exists, so just replace the data pointer*/
1222                 if(key==node->key32){
1223                         node->data=data;
1224                         return;
1225                 }
1226                 if(key<node->key32) {
1227                         if(!node->left){
1228                                 /* new node to the left */
1229                                 emem_tree_node_t *new_node;
1230                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1231                                 node->left=new_node;
1232                                 new_node->parent=node;
1233                                 new_node->left=NULL;
1234                                 new_node->right=NULL;
1235                                 new_node->key32=key;
1236                                 new_node->data=data;
1237                                 new_node->u.is_subtree=EMEM_TREE_NODE_IS_DATA;
1238                                 node=new_node;
1239                                 break;
1240                         }
1241                         node=node->left;
1242                         continue;
1243                 }
1244                 if(key>node->key32) {
1245                         if(!node->right){
1246                                 /* new node to the right */
1247                                 emem_tree_node_t *new_node;
1248                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1249                                 node->right=new_node;
1250                                 new_node->parent=node;
1251                                 new_node->left=NULL;
1252                                 new_node->right=NULL;
1253                                 new_node->key32=key;
1254                                 new_node->data=data;
1255                                 new_node->u.is_subtree=EMEM_TREE_NODE_IS_DATA;
1256                                 node=new_node;
1257                                 break;
1258                         }
1259                         node=node->right;
1260                         continue;
1261                 }
1262         }
1263
1264         /* node will now point to the newly created node */
1265         switch(se_tree->type){
1266         case EMEM_TREE_TYPE_RED_BLACK:
1267                 node->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1268                 rb_insert_case1(se_tree, node);
1269                 break;
1270         }
1271 }
1272
1273 static void* lookup_or_insert32(emem_tree_t *se_tree, guint32 key, void*(*func)(void*),void* ud, int is_subtree) {
1274         emem_tree_node_t *node;
1275
1276         node=se_tree->tree;
1277
1278         /* is this the first node ?*/
1279         if(!node){
1280                 node=se_tree->malloc(sizeof(emem_tree_node_t));
1281                 switch(se_tree->type){
1282                         case EMEM_TREE_TYPE_RED_BLACK:
1283                                 node->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1284                                 break;
1285                 }
1286                 node->parent=NULL;
1287                 node->left=NULL;
1288                 node->right=NULL;
1289                 node->key32=key;
1290                 node->data= func(ud);
1291                 node->u.is_subtree = is_subtree;
1292                 se_tree->tree=node;
1293                 return node->data;
1294         }
1295
1296         /* it was not the new root so walk the tree until we find where to
1297                 * insert this new leaf.
1298                 */
1299         while(1){
1300                 /* this node already exists, so just return the data pointer*/
1301                 if(key==node->key32){
1302                         return node->data;
1303                 }
1304                 if(key<node->key32) {
1305                         if(!node->left){
1306                                 /* new node to the left */
1307                                 emem_tree_node_t *new_node;
1308                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1309                                 node->left=new_node;
1310                                 new_node->parent=node;
1311                                 new_node->left=NULL;
1312                                 new_node->right=NULL;
1313                                 new_node->key32=key;
1314                                 new_node->data= func(ud);
1315                                 new_node->u.is_subtree = is_subtree;
1316                                 node=new_node;
1317                                 break;
1318                         }
1319                         node=node->left;
1320                         continue;
1321                 }
1322                 if(key>node->key32) {
1323                         if(!node->right){
1324                                 /* new node to the right */
1325                                 emem_tree_node_t *new_node;
1326                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1327                                 node->right=new_node;
1328                                 new_node->parent=node;
1329                                 new_node->left=NULL;
1330                                 new_node->right=NULL;
1331                                 new_node->key32=key;
1332                                 new_node->data= func(ud);
1333                                 new_node->u.is_subtree = is_subtree;
1334                                 node=new_node;
1335                                 break;
1336                         }
1337                         node=node->right;
1338                         continue;
1339                 }
1340         }
1341
1342         /* node will now point to the newly created node */
1343         switch(se_tree->type){
1344                 case EMEM_TREE_TYPE_RED_BLACK:
1345                         node->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1346                         rb_insert_case1(se_tree, node);
1347                         break;
1348         }
1349
1350         return node->data;
1351 }
1352
1353 /* When the se data is released, this entire tree will dissapear as if it
1354  * never existed including all metadata associated with the tree.
1355  */
1356 emem_tree_t *
1357 se_tree_create_non_persistent(int type, const char *name)
1358 {
1359         emem_tree_t *tree_list;
1360
1361         tree_list=se_alloc(sizeof(emem_tree_t));
1362         tree_list->next=NULL;
1363         tree_list->type=type;
1364         tree_list->tree=NULL;
1365         tree_list->name=name;
1366         tree_list->malloc=se_alloc;
1367
1368         return tree_list;
1369 }
1370
1371 /* This tree is PErmanent and will never be released
1372  */
1373 emem_tree_t *
1374 pe_tree_create(int type, const char *name)
1375 {
1376         emem_tree_t *tree_list;
1377
1378         tree_list=g_malloc(sizeof(emem_tree_t));
1379         tree_list->next=NULL;
1380         tree_list->type=type;
1381         tree_list->tree=NULL;
1382         tree_list->name=name;
1383         tree_list->malloc=(void *(*)(size_t)) g_malloc;
1384
1385         return tree_list;
1386 }
1387
1388 /* create another (sub)tree using the same memory allocation scope
1389  * as the parent tree.
1390  */
1391 static emem_tree_t *
1392 emem_tree_create_subtree(emem_tree_t *parent_tree, const char *name)
1393 {
1394         emem_tree_t *tree_list;
1395
1396         tree_list=parent_tree->malloc(sizeof(emem_tree_t));
1397         tree_list->next=NULL;
1398         tree_list->type=parent_tree->type;
1399         tree_list->tree=NULL;
1400         tree_list->name=name;
1401         tree_list->malloc=parent_tree->malloc;
1402
1403         return tree_list;
1404 }
1405
1406 static void* create_sub_tree(void* d) {
1407         emem_tree_t *se_tree = d;
1408         return emem_tree_create_subtree(se_tree, "subtree");
1409 }
1410
1411 /* insert a new node in the tree. if this node matches an already existing node
1412  * then just replace the data for that node */
1413
1414 void
1415 emem_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data)
1416 {
1417         emem_tree_t *next_tree;
1418
1419         if((key[0].length<1)||(key[0].length>100)){
1420                 DISSECTOR_ASSERT_NOT_REACHED();
1421         }
1422         if((key[0].length==1)&&(key[1].length==0)){
1423                 emem_tree_insert32(se_tree, *key[0].key, data);
1424                 return;
1425         }
1426
1427         next_tree=lookup_or_insert32(se_tree, *key[0].key, create_sub_tree, se_tree, EMEM_TREE_NODE_IS_SUBTREE);
1428
1429         if(key[0].length==1){
1430                 key++;
1431         } else {
1432                 key[0].length--;
1433                 key[0].key++;
1434         }
1435         emem_tree_insert32_array(next_tree, key, data);
1436 }
1437
1438 void *
1439 emem_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key)
1440 {
1441         emem_tree_t *next_tree;
1442
1443         if((key[0].length<1)||(key[0].length>100)){
1444                 DISSECTOR_ASSERT_NOT_REACHED();
1445         }
1446         if((key[0].length==1)&&(key[1].length==0)){
1447                 return emem_tree_lookup32(se_tree, *key[0].key);
1448         }
1449         next_tree=emem_tree_lookup32(se_tree, *key[0].key);
1450         if(!next_tree){
1451                 return NULL;
1452         }
1453         if(key[0].length==1){
1454                 key++;
1455         } else {
1456                 key[0].length--;
1457                 key[0].key++;
1458         }
1459         return emem_tree_lookup32_array(next_tree, key);
1460 }
1461
1462
1463 /* Strings are stored as an array of uint32 containing the string characters
1464    with 4 characters in each uint32.
1465    The first byte of the string is stored as the most significant byte.
1466    If the string is not a multiple of 4 characters in length the last
1467    uint32 containing the string bytes are padded with 0 bytes.
1468    After the uint32's containing the string, there is one final terminator
1469    uint32 with the value 0x00000001
1470 */
1471 void
1472 emem_tree_insert_string(emem_tree_t* se_tree, const gchar* k, void* v, guint32 flags)
1473 {
1474         emem_tree_key_t key[2];
1475         guint32 *aligned=NULL;
1476         guint32 len = strlen(k);
1477         guint32 div = (len+3)/4+1;
1478         guint32 i;
1479         guint32 tmp;
1480
1481         aligned = malloc(div * sizeof (guint32));
1482
1483         /* pack the bytes one one by one into guint32s */
1484         tmp = 0;
1485         for (i = 0;i < len;i++) {
1486                 unsigned char ch;
1487
1488                 ch = (unsigned char)k[i];
1489                 if (flags & EMEM_TREE_STRING_NOCASE) {
1490                         if(isupper(ch)) {
1491                                 ch = tolower(ch);
1492                         }
1493                 }
1494                 tmp <<= 8;
1495                 tmp |= ch;
1496                 if (i%4 == 3) {
1497                         aligned[i/4] = tmp;
1498                         tmp = 0;
1499                 }
1500         }
1501         /* add required padding to the last uint32 */
1502         if (i%4 != 0) {
1503                 while (i%4 != 0) {
1504                         i++;
1505                         tmp <<= 8;
1506                 }
1507                 aligned[i/4-1] = tmp;
1508         }
1509
1510         /* add the terminator */
1511         aligned[div-1] = 0x00000001;
1512
1513         key[0].length = div;
1514         key[0].key = aligned;
1515         key[1].length = 0;
1516         key[1].key = NULL;
1517
1518
1519         emem_tree_insert32_array(se_tree, key, v);
1520         free(aligned);
1521 }
1522
1523 void *
1524 emem_tree_lookup_string(emem_tree_t* se_tree, const gchar* k, guint32 flags)
1525 {
1526         emem_tree_key_t key[2];
1527         guint32 *aligned=NULL;
1528         guint32 len = strlen(k);
1529         guint32 div = (len+3)/4+1;
1530         guint32 i;
1531         guint32 tmp;
1532         void *ret;
1533
1534         aligned = malloc(div * sizeof (guint32));
1535
1536         /* pack the bytes one one by one into guint32s */
1537         tmp = 0;
1538         for (i = 0;i < len;i++) {
1539                 unsigned char ch;
1540
1541                 ch = (unsigned char)k[i];
1542                 if (flags & EMEM_TREE_STRING_NOCASE) {
1543                         if(isupper(ch)) {
1544                                 ch = tolower(ch);
1545                         }
1546                 }
1547                 tmp <<= 8;
1548                 tmp |= ch;
1549                 if (i%4 == 3) {
1550                         aligned[i/4] = tmp;
1551                         tmp = 0;
1552                 }
1553         }
1554         /* add required padding to the last uint32 */
1555         if (i%4 != 0) {
1556                 while (i%4 != 0) {
1557                         i++;
1558                         tmp <<= 8;
1559                 }
1560                 aligned[i/4-1] = tmp;
1561         }
1562
1563         /* add the terminator */
1564         aligned[div-1] = 0x00000001;
1565
1566         key[0].length = div;
1567         key[0].key = aligned;
1568         key[1].length = 0;
1569         key[1].key = NULL;
1570
1571
1572         ret = emem_tree_lookup32_array(se_tree, key);
1573         free(aligned);
1574         return ret;
1575 }
1576
1577 static gboolean
1578 emem_tree_foreach_nodes(emem_tree_node_t* node, tree_foreach_func callback, void *user_data)
1579 {
1580         gboolean stop_traverse = FALSE;
1581
1582         if (!node)
1583                 return FALSE;
1584
1585         if(node->left) {
1586                 stop_traverse = emem_tree_foreach_nodes(node->left, callback, user_data);
1587                 if (stop_traverse) {
1588                         return TRUE;
1589                 }
1590         }
1591
1592         if (node->u.is_subtree == EMEM_TREE_NODE_IS_SUBTREE) {
1593                 stop_traverse = emem_tree_foreach(node->data, callback, user_data);
1594         } else {
1595                 stop_traverse = callback(node->data, user_data);
1596         }
1597
1598         if (stop_traverse) {
1599                 return TRUE;
1600         }
1601
1602         if(node->right) {
1603                 stop_traverse = emem_tree_foreach_nodes(node->right, callback, user_data);
1604                 if (stop_traverse) {
1605                         return TRUE;
1606                 }
1607         }
1608
1609         return FALSE;
1610 }
1611
1612 gboolean
1613 emem_tree_foreach(emem_tree_t* emem_tree, tree_foreach_func callback, void *user_data)
1614 {
1615         if (!emem_tree)
1616                 return FALSE;
1617
1618         if(!emem_tree->tree)
1619                 return FALSE;
1620
1621         return emem_tree_foreach_nodes(emem_tree->tree, callback, user_data);
1622 }
1623
1624
1625 static void
1626 emem_tree_print_nodes(emem_tree_node_t* node, int level)
1627 {
1628         int i;
1629
1630         if (!node)
1631                 return;
1632
1633         for(i=0;i<level;i++){
1634                 printf("    ");
1635         }
1636
1637         printf("NODE:%p parent:%p left:0x%p right:%px key:%d data:%p\n",
1638                 (void *)node,(void *)(node->parent),(void *)(node->left),(void *)(node->right),
1639                 (node->key32),node->data);
1640         if(node->left)
1641                 emem_tree_print_nodes(node->left, level+1);
1642         if(node->right)
1643                 emem_tree_print_nodes(node->right, level+1);
1644 }
1645 void
1646 emem_print_tree(emem_tree_t* emem_tree)
1647 {
1648         if (!emem_tree)
1649                 return;
1650
1651         printf("EMEM tree type:%d name:%s tree:%p\n",emem_tree->type,emem_tree->name,(void *)(emem_tree->tree));
1652         if(emem_tree->tree)
1653                 emem_tree_print_nodes(emem_tree->tree, 0);
1654 }
1655
1656 /*
1657  * String buffers
1658  */
1659
1660 /*
1661  * Presumably we're using these routines for building strings for the tree.
1662  * Use ITEM_LABEL_LENGTH as the basis for our default lengths.
1663  */
1664
1665 #define DEFAULT_STRBUF_LEN (ITEM_LABEL_LENGTH / 10)
1666 #define MAX_STRBUF_LEN 65536
1667
1668 static gsize
1669 next_size(gsize cur_len, gsize wanted_len, gsize max_len) {
1670         if (max_len < 1 || max_len > MAX_STRBUF_LEN) {
1671                 max_len = MAX_STRBUF_LEN;
1672         }
1673
1674         if (cur_len < 1) {
1675                 cur_len = DEFAULT_STRBUF_LEN;
1676         }
1677
1678         while (cur_len < wanted_len) {
1679                 cur_len *= 2;
1680         }
1681
1682         return cur_len < max_len ? cur_len : max_len;
1683 }
1684
1685 static void
1686 ep_strbuf_grow(emem_strbuf_t *strbuf, gsize wanted_len) {
1687         gsize new_alloc_len;
1688         gchar *new_str;
1689
1690         if (!strbuf || strbuf->alloc_len >= strbuf->max_len) {
1691                 return;
1692         }
1693
1694         new_alloc_len = next_size(strbuf->len, wanted_len, strbuf->max_len);
1695         new_str = ep_alloc(new_alloc_len);
1696         g_strlcpy(new_str, strbuf->str, new_alloc_len);
1697
1698         strbuf->alloc_len = new_alloc_len;
1699         strbuf->str = new_str;
1700 }
1701
1702 emem_strbuf_t *
1703 ep_strbuf_sized_new(gsize len, gsize max_len) {
1704         emem_strbuf_t *strbuf;
1705
1706         strbuf = ep_alloc(sizeof(emem_strbuf_t));
1707
1708         if (len > 0) {
1709                 strbuf->str = ep_alloc(len);
1710                 strbuf->str[0] = '\0';
1711         } else {
1712                 strbuf->str = ep_strdup("");
1713         }
1714
1715         strbuf->len = len;
1716         strbuf->alloc_len = len;
1717         strbuf->max_len = max_len;
1718         return strbuf;
1719 }
1720
1721 emem_strbuf_t *
1722 ep_strbuf_new(const gchar *init) {
1723         emem_strbuf_t *strbuf;
1724
1725         strbuf = ep_strbuf_sized_new(next_size(0, strlen(init), 0), 0);
1726
1727         g_strlcpy(strbuf->str, init, strbuf->alloc_len);
1728         return strbuf;
1729 }
1730
1731 emem_strbuf_t *
1732 ep_strbuf_new_label(const gchar *init) {
1733         emem_strbuf_t *strbuf;
1734         gsize init_size;
1735
1736         if (!init) {
1737                 init = "";
1738         }
1739
1740         init_size = strlen(init);
1741         strbuf = ep_strbuf_sized_new(init_size > DEFAULT_STRBUF_LEN ? init_size : DEFAULT_STRBUF_LEN,
1742                                      ITEM_LABEL_LENGTH);
1743
1744         g_strlcpy(strbuf->str, init, strbuf->alloc_len);
1745         strbuf->len = MIN(init_size, strbuf->alloc_len);
1746         return strbuf;
1747 }
1748
1749 void
1750 ep_strbuf_append(emem_strbuf_t *strbuf, const gchar *str) {
1751         gsize add_len;
1752
1753         if (!strbuf || !str) {
1754                 return;
1755         }
1756
1757         add_len = strlen(str);
1758
1759         if (strbuf->len + add_len > strbuf->alloc_len) {
1760                 ep_strbuf_grow(strbuf, strbuf->len + add_len);
1761         }
1762
1763         g_strlcpy(&strbuf->str[strbuf->len], str, strbuf->alloc_len - add_len);
1764         strbuf->len += add_len;
1765 }
1766
1767 void
1768 ep_strbuf_append_vprintf(emem_strbuf_t *strbuf, const gchar *format, va_list ap) {
1769         va_list ap2;
1770         gsize add_len, full_len;
1771
1772         G_VA_COPY(ap2, ap);
1773
1774         add_len = g_printf_string_upper_bound(format, ap);
1775
1776         if (strbuf->len + add_len > strbuf->alloc_len) {
1777                 ep_strbuf_grow(strbuf, strbuf->len + add_len);
1778         }
1779
1780         if (strbuf->len + add_len > strbuf->alloc_len) {
1781                 add_len = strbuf->alloc_len - strbuf->len;
1782         }
1783
1784         full_len = g_vsnprintf(&strbuf->str[strbuf->len], add_len, format, ap2);
1785         strbuf->len += MIN(add_len, full_len);
1786         va_end(ap2);
1787
1788 }
1789
1790 void
1791 ep_strbuf_append_printf(emem_strbuf_t *strbuf, const gchar *format, ...) {
1792         va_list ap;
1793
1794         va_start(ap, format);
1795         ep_strbuf_append_vprintf(strbuf, format, ap);
1796         va_end(ap);
1797 }
1798
1799 void
1800 ep_strbuf_truncate(emem_strbuf_t *strbuf, gsize len) {
1801         if (!strbuf || len >= strbuf->len) {
1802                 return;
1803         }
1804
1805         strbuf->str[len] = '\0';
1806         strbuf->len = len;
1807 }