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
  34 #include <time.h>
  35 #ifdef HAVE_SYS_TIME_H
  36 #include <sys/time.h>
  37 #endif
  38
  39 #ifdef HAVE_UNISTD_H
  40 #include <unistd.h>
  41 #endif
  42
  43 #include <glib.h>
  44 #include <proto.h>
  45 #include "emem.h"
  46 #include <wiretap/file_util.h>
  47
  48 #ifdef _WIN32
  49 #include <windows.h>    /* VirtualAlloc, VirtualProtect */
  50 #include <process.h>    /* getpid */
  51 #endif
  52
  53
  54 /*
  55  * Tools like Valgrind and ElectricFence don't work well with memchunks.
  56  * Uncomment the defines below to make {ep|se}_alloc() allocate each
  57  * object individually.
  58  */
  59 /* #define EP_DEBUG_FREE 1 */
  60 /* #define SE_DEBUG_FREE 1 */
  61
  62 /* Do we want to use guardpages? if available */
  63 #define WANT_GUARD_PAGES 1
  64
  65 /* Do we want to use canaries ? */
  66 #define DEBUG_USE_CANARIES 1
  67
  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 static emem_header_t ep_packet_mem;
 129 static 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, EMEM_CANARY_DATA_SIZE, 1, 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; src[i] && i < len; 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; src[i] && i < len; 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                 se_tree->tree=node;
1186                 return;
1187         }
1188
1189         /* it was not the new root so walk the tree until we find where to
1190          * insert this new leaf.
1191          */
1192         while(1){
1193                 /* this node already exists, so just replace the data pointer*/
1194                 if(key==node->key32){
1195                         node->data=data;
1196                         return;
1197                 }
1198                 if(key<node->key32) {
1199                         if(!node->left){
1200                                 /* new node to the left */
1201                                 emem_tree_node_t *new_node;
1202                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1203                                 node->left=new_node;
1204                                 new_node->parent=node;
1205                                 new_node->left=NULL;
1206                                 new_node->right=NULL;
1207                                 new_node->key32=key;
1208                                 new_node->data=data;
1209                                 node=new_node;
1210                                 break;
1211                         }
1212                         node=node->left;
1213                         continue;
1214                 }
1215                 if(key>node->key32) {
1216                         if(!node->right){
1217                                 /* new node to the right */
1218                                 emem_tree_node_t *new_node;
1219                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1220                                 node->right=new_node;
1221                                 new_node->parent=node;
1222                                 new_node->left=NULL;
1223                                 new_node->right=NULL;
1224                                 new_node->key32=key;
1225                                 new_node->data=data;
1226                                 node=new_node;
1227                                 break;
1228                         }
1229                         node=node->right;
1230                         continue;
1231                 }
1232         }
1233
1234         /* node will now point to the newly created node */
1235         switch(se_tree->type){
1236         case EMEM_TREE_TYPE_RED_BLACK:
1237                 node->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1238                 rb_insert_case1(se_tree, node);
1239                 break;
1240         }
1241 }
1242
1243 static void* lookup_or_insert32(emem_tree_t *se_tree, guint32 key, void*(*func)(void*),void* ud) {
1244         emem_tree_node_t *node;
1245
1246         node=se_tree->tree;
1247
1248         /* is this the first node ?*/
1249         if(!node){
1250                 node=se_tree->malloc(sizeof(emem_tree_node_t));
1251                 switch(se_tree->type){
1252                         case EMEM_TREE_TYPE_RED_BLACK:
1253                                 node->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1254                                 break;
1255                 }
1256                 node->parent=NULL;
1257                 node->left=NULL;
1258                 node->right=NULL;
1259                 node->key32=key;
1260                 node->data= func(ud);
1261                 se_tree->tree=node;
1262                 return node->data;
1263         }
1264
1265         /* it was not the new root so walk the tree until we find where to
1266                 * insert this new leaf.
1267                 */
1268         while(1){
1269                 /* this node already exists, so just return the data pointer*/
1270                 if(key==node->key32){
1271                         return node->data;
1272                 }
1273                 if(key<node->key32) {
1274                         if(!node->left){
1275                                 /* new node to the left */
1276                                 emem_tree_node_t *new_node;
1277                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1278                                 node->left=new_node;
1279                                 new_node->parent=node;
1280                                 new_node->left=NULL;
1281                                 new_node->right=NULL;
1282                                 new_node->key32=key;
1283                                 new_node->data= func(ud);
1284                                 node=new_node;
1285                                 break;
1286                         }
1287                         node=node->left;
1288                         continue;
1289                 }
1290                 if(key>node->key32) {
1291                         if(!node->right){
1292                                 /* new node to the right */
1293                                 emem_tree_node_t *new_node;
1294                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1295                                 node->right=new_node;
1296                                 new_node->parent=node;
1297                                 new_node->left=NULL;
1298                                 new_node->right=NULL;
1299                                 new_node->key32=key;
1300                                 new_node->data= func(ud);
1301                                 node=new_node;
1302                                 break;
1303                         }
1304                         node=node->right;
1305                         continue;
1306                 }
1307         }
1308
1309         /* node will now point to the newly created node */
1310         switch(se_tree->type){
1311                 case EMEM_TREE_TYPE_RED_BLACK:
1312                         node->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1313                         rb_insert_case1(se_tree, node);
1314                         break;
1315         }
1316
1317         return node->data;
1318 }
1319
1320 /* When the se data is released, this entire tree will dissapear as if it
1321  * never existed including all metadata associated with the tree.
1322  */
1323 emem_tree_t *
1324 se_tree_create_non_persistent(int type, const char *name)
1325 {
1326         emem_tree_t *tree_list;
1327
1328         tree_list=se_alloc(sizeof(emem_tree_t));
1329         tree_list->next=NULL;
1330         tree_list->type=type;
1331         tree_list->tree=NULL;
1332         tree_list->name=name;
1333         tree_list->malloc=se_alloc;
1334
1335         return tree_list;
1336 }
1337
1338 /* This tree is PErmanent and will never be released
1339  */
1340 emem_tree_t *
1341 pe_tree_create(int type, char *name)
1342 {
1343         emem_tree_t *tree_list;
1344
1345         tree_list=g_malloc(sizeof(emem_tree_t));
1346         tree_list->next=NULL;
1347         tree_list->type=type;
1348         tree_list->tree=NULL;
1349         tree_list->name=name;
1350         tree_list->malloc=(void *(*)(size_t)) g_malloc;
1351
1352         return tree_list;
1353 }
1354
1355 /* create another (sub)tree using the same memory allocation scope
1356  * as the parent tree.
1357  */
1358 static emem_tree_t *
1359 emem_tree_create_subtree(emem_tree_t *parent_tree, char *name)
1360 {
1361         emem_tree_t *tree_list;
1362
1363         tree_list=parent_tree->malloc(sizeof(emem_tree_t));
1364         tree_list->next=NULL;
1365         tree_list->type=parent_tree->type;
1366         tree_list->tree=NULL;
1367         tree_list->name=name;
1368         tree_list->malloc=parent_tree->malloc;
1369
1370         return tree_list;
1371 }
1372
1373 static void* create_sub_tree(void* d) {
1374         emem_tree_t *se_tree = d;
1375         return emem_tree_create_subtree(se_tree, "subtree");
1376 }
1377
1378 /* insert a new node in the tree. if this node matches an already existing node
1379  * then just replace the data for that node */
1380
1381 void
1382 emem_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data)
1383 {
1384         emem_tree_t *next_tree;
1385
1386         if((key[0].length<1)||(key[0].length>100)){
1387                 DISSECTOR_ASSERT_NOT_REACHED();
1388         }
1389         if((key[0].length==1)&&(key[1].length==0)){
1390                 emem_tree_insert32(se_tree, *key[0].key, data);
1391                 return;
1392         }
1393
1394         next_tree=lookup_or_insert32(se_tree, *key[0].key, create_sub_tree, se_tree);
1395
1396         if(key[0].length==1){
1397                 key++;
1398         } else {
1399                 key[0].length--;
1400                 key[0].key++;
1401         }
1402         emem_tree_insert32_array(next_tree, key, data);
1403 }
1404
1405 void *
1406 emem_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key)
1407 {
1408         emem_tree_t *next_tree;
1409
1410         if((key[0].length<1)||(key[0].length>100)){
1411                 DISSECTOR_ASSERT_NOT_REACHED();
1412         }
1413         if((key[0].length==1)&&(key[1].length==0)){
1414                 return emem_tree_lookup32(se_tree, *key[0].key);
1415         }
1416         next_tree=emem_tree_lookup32(se_tree, *key[0].key);
1417         if(!next_tree){
1418                 return NULL;
1419         }
1420         if(key[0].length==1){
1421                 key++;
1422         } else {
1423                 key[0].length--;
1424                 key[0].key++;
1425         }
1426         return emem_tree_lookup32_array(next_tree, key);
1427 }
1428
1429
1430 void
1431 emem_tree_insert_string(emem_tree_t* se_tree, const gchar* k, void* v) {
1432         guint32 len = strlen(k);
1433         guint32 div = (len-1)/4;
1434         guint32 residual = 0;
1435         emem_tree_key_t key[] = {
1436                 {1,NULL},
1437                 {0,NULL},
1438                 {1,NULL},
1439                 {0,NULL}
1440         };
1441
1442         key[0].key = &len;
1443         key[1].length = div;
1444         key[1].key = (guint32*)(&k[0]);
1445         key[2].key = &residual;
1446
1447         if (! div) {
1448                 key[1].length = key[2].length;
1449                 key[1].key = key[2].key;
1450                 key[2].length = 0;
1451                 key[2].key = NULL;
1452         }
1453
1454         div *= 4;
1455
1456         switch(len%4) {
1457                 case 0:
1458                         residual |= ( k[div+3] << 24 );
1459                 case 3:
1460                         residual |= ( k[div+2] << 16 );
1461                 case 2:
1462                         residual |= ( k[div+1] << 8  );
1463                 case 1:
1464                         residual |= k[div];
1465                         break;
1466         }
1467
1468         emem_tree_insert32_array(se_tree,key,v);
1469 }
1470
1471 void *
1472 emem_tree_lookup_string(emem_tree_t* se_tree, const gchar* k) {
1473         guint32 len = strlen(k);
1474         guint32 div = (len-1)/4;
1475         guint32 residual = 0;
1476         emem_tree_key_t key[] = {
1477                 {1,NULL},
1478                 {0,NULL},
1479                 {1,NULL},
1480                 {0,NULL}
1481         };
1482
1483         key[0].key = &len;
1484         key[1].length = div;
1485         key[1].key = (guint32*)(&k[0]);
1486         key[2].key = &residual;
1487
1488         if (! div) {
1489                 key[1].length = key[2].length;
1490                 key[1].key = key[2].key;
1491                 key[2].length = 0;
1492                 key[2].key = NULL;
1493         }
1494
1495         div *= 4;
1496
1497         switch(len%4) {
1498                 case 0:
1499                         residual |= k[div+3] << 24;
1500                 case 3:
1501                         residual |= k[div+2] << 16;
1502                 case 2:
1503                         residual |= k[div+1] << 8;
1504                 case 1:
1505                         residual |= k[div];
1506                         break;
1507         }
1508
1509         return emem_tree_lookup32_array(se_tree, key);
1510 }
1511
1512
1513 static void
1514 emem_tree_print_nodes(emem_tree_node_t* node, int level)
1515 {
1516         int i;
1517
1518         if (!node)
1519                 return;
1520
1521         for(i=0;i<level;i++){
1522                 printf("    ");
1523         }
1524
1525         printf("NODE:%08x parent:%08x left:0x%08x right:%08x key:%d data:0x%08x\n",(int)node,(int)node->parent,(int)node->left,(int)node->right,node->key32,(int)node->data);
1526         if(node->left)
1527                 emem_tree_print_nodes(node->left, level+1);
1528         if(node->right)
1529                 emem_tree_print_nodes(node->right, level+1);
1530 }
1531 void
1532 emem_print_tree(emem_tree_t* emem_tree)
1533 {
1534         if (!emem_tree)
1535                 return;
1536
1537         printf("EMEM tree type:%d name:%s tree:0x%08x\n",emem_tree->type,emem_tree->name,(int)emem_tree->tree);
1538         if(emem_tree->tree)
1539                 emem_tree_print_nodes(emem_tree->tree, 0);
1540 }