epan/emem.c

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