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