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