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