epan/emem.c

   1 /* emem.c
   2  * Wireshark memory management and garbage collection functions
   3  * Ronnie Sahlberg 2005
   4  *
   5  * $Id$
   6  *
   7  * Wireshark - Network traffic analyzer
   8  * By Gerald Combs <gerald@wireshark.org>
   9  * Copyright 1998 Gerald Combs
  10  *
  11  * This program is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU General Public License
  13  * as published by the Free Software Foundation; either version 2
  14  * of the License, or (at your option) any later version.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with this program; if not, write to the Free Software
  23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  24  */
  25 #ifdef HAVE_CONFIG_H
  26 #include "config.h"
  27 #endif
  28
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <stdarg.h>
  33 #include <ctype.h>
  34
  35 #include <time.h>
  36 #ifdef HAVE_SYS_TIME_H
  37 #include <sys/time.h>
  38 #endif
  39
  40 #ifdef HAVE_UNISTD_H
  41 #include <unistd.h>
  42 #endif
  43
  44 #include <glib.h>
  45
  46 #include <proto.h>
  47 #include "emem.h"
  48
  49 #ifdef _WIN32
  50 #include <windows.h>    /* VirtualAlloc, VirtualProtect */
  51 #include <process.h>    /* getpid */
  52 #endif
  53
  54
  55 /*
  56  * Tools like Valgrind and ElectricFence don't work well with memchunks.
  57  * Uncomment the defines below to make {ep|se}_alloc() allocate each
  58  * object individually.
  59  */
  60 /* #define EP_DEBUG_FREE 1 */
  61 /* #define SE_DEBUG_FREE 1 */
  62
  63 /* Do we want to use guardpages? if available */
  64 #define WANT_GUARD_PAGES 1
  65
  66 /* Do we want to use canaries ? */
  67 #define DEBUG_USE_CANARIES 1
  68
  69 #ifdef WANT_GUARD_PAGES
  70 /* Add guard pages at each end of our allocated memory */
  71 #if defined(HAVE_SYSCONF) && defined(HAVE_MMAP) && defined(HAVE_MPROTECT) && defined(HAVE_STDINT_H)
  72 #include <stdint.h>
  73 #include <sys/types.h>
  74 #include <sys/mman.h>
  75 #if defined(MAP_ANONYMOUS)
  76 #define ANON_PAGE_MODE  (MAP_ANONYMOUS|MAP_PRIVATE)
  77 #elif defined(MAP_ANON)
  78 #define ANON_PAGE_MODE  (MAP_ANON|MAP_PRIVATE)
  79 #else
  80 #define ANON_PAGE_MODE  (MAP_PRIVATE)   /* have to map /dev/zero */
  81 #define NEED_DEV_ZERO
  82 #endif
  83 #ifdef NEED_DEV_ZERO
  84 #include <fcntl.h>
  85 static int dev_zero_fd;
  86 #define ANON_FD dev_zero_fd
  87 #else
  88 #define ANON_FD -1
  89 #endif
  90 #define USE_GUARD_PAGES 1
  91 #endif
  92 #endif
  93
  94 /* When required, allocate more memory from the OS in this size chunks */
  95 #define EMEM_PACKET_CHUNK_SIZE 10485760
  96
  97 /* The maximum number of allocations per chunk */
  98 #define EMEM_ALLOCS_PER_CHUNK (EMEM_PACKET_CHUNK_SIZE / 512)
  99
 100
 101 #ifdef DEBUG_USE_CANARIES
 102 #define EMEM_CANARY_SIZE 8
 103 #define EMEM_CANARY_DATA_SIZE (EMEM_CANARY_SIZE * 2 - 1)
 104
 105 /* this should be static, but if it were gdb would had problems finding it */
 106 guint8  ep_canary[EMEM_CANARY_DATA_SIZE], se_canary[EMEM_CANARY_DATA_SIZE];
 107 #endif /* DEBUG_USE_CANARIES */
 108
 109 typedef struct _emem_chunk_t {
 110         struct _emem_chunk_t *next;
 111         unsigned int    amount_free_init;
 112         unsigned int    amount_free;
 113         unsigned int    free_offset_init;
 114         unsigned int    free_offset;
 115         char *buf;
 116 #ifdef DEBUG_USE_CANARIES
 117 #if ! defined(EP_DEBUG_FREE) && ! defined(SE_DEBUG_FREE)
 118         unsigned int    c_count;
 119         void            *canary[EMEM_ALLOCS_PER_CHUNK];
 120         guint8          cmp_len[EMEM_ALLOCS_PER_CHUNK];
 121 #endif
 122 #endif /* DEBUG_USE_CANARIES */
 123 } emem_chunk_t;
 124
 125 typedef struct _emem_header_t {
 126         emem_chunk_t *free_list;
 127         emem_chunk_t *used_list;
 128 } emem_header_t;
 129
 130 static emem_header_t ep_packet_mem;
 131 static emem_header_t se_packet_mem;
 132
 133 #if !defined(SE_DEBUG_FREE)
 134 #if defined (_WIN32)
 135 static SYSTEM_INFO sysinfo;
 136 static OSVERSIONINFO versinfo;
 137 static int pagesize;
 138 #elif defined(USE_GUARD_PAGES)
 139 static intptr_t pagesize;
 140 #endif /* _WIN32 / USE_GUARD_PAGES */
 141 #endif /* SE_DEBUG_FREE */
 142
 143 #ifdef DEBUG_USE_CANARIES
 144 /*
 145  * Set a canary value to be placed between memchunks.
 146  */
 147 void
 148 emem_canary(guint8 *canary) {
 149         int i;
 150         static GRand   *rand_state = NULL;
 151
 152         if (rand_state == NULL) {
 153                 rand_state = g_rand_new();
 154         }
 155         for (i = 0; i < EMEM_CANARY_DATA_SIZE; i ++) {
 156                 canary[i] = (guint8) g_rand_int(rand_state);
 157         }
 158         return;
 159 }
 160
 161 /*
 162  * Given an allocation size, return the amount of padding needed for
 163  * the canary value.
 164  */
 165 static guint8
 166 emem_canary_pad (size_t allocation) {
 167         guint8 pad;
 168
 169         pad = EMEM_CANARY_SIZE - (allocation % EMEM_CANARY_SIZE);
 170         if (pad < EMEM_CANARY_SIZE)
 171                 pad += EMEM_CANARY_SIZE;
 172
 173         return pad;
 174 }
 175 #endif /* DEBUG_USE_CANARIES */
 176
 177 /* used for debugging canaries, will block */
 178 #ifdef DEBUG_INTENSE_CANARY_CHECKS
 179 gboolean intense_canary_checking = FALSE;
 180
 181 /*  used to intensivelly check ep canaries
 182  */
 183 void ep_check_canary_integrity(const char* fmt, ...) {
 184         va_list ap;
 185         static gchar there[128] = {
 186                 'L','a','u','n','c','h',0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 187                 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 188                 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 189                 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
 190         gchar here[128];
 191         emem_chunk_t* npc = NULL;
 192
 193         if (! intense_canary_checking ) return;
 194
 195         here[126] = '\0';
 196         here[127] = '\0';
 197
 198         va_start(ap,fmt);
 199         g_vsnprintf(here, 126,fmt, ap);
 200         va_end(ap);
 201
 202         for (npc = ep_packet_mem.free_list; npc != NULL; npc = npc->next) {
 203                 static unsigned i_ctr;
 204
 205                 if (npc->c_count > 0x00ffffff) {
 206                         g_error("ep_packet_mem.free_list was corrupted\nbetween: %s\nand: %s",there, here);
 207                 }
 208
 209                 for (i_ctr = 0; i_ctr < npc->c_count; i_ctr++) {
 210                         if (memcmp(npc->canary[i_ctr], &ep_canary, npc->cmp_len[i_ctr]) != 0) {
 211                                 g_error("Per-packet memory corrupted\nbetween: %s\nand: %s",there, here);
 212                         }
 213                 }
 214         }
 215
 216         strncpy(there,here,126);
 217
 218 }
 219 #endif
 220
 221
 222 /* Initialize the packet-lifetime memory allocation pool.
 223  * This function should be called only once when Wireshark or TShark starts
 224  * up.
 225  */
 226 void
 227 ep_init_chunk(void)
 228 {
 229         ep_packet_mem.free_list=NULL;
 230         ep_packet_mem.used_list=NULL;
 231
 232 #ifdef DEBUG_INTENSE_CANARY_CHECKS
 233         intense_canary_checking = (gboolean)getenv("WIRESHARK_DEBUG_EP_CANARY");
 234 #endif
 235
 236 #ifdef DEBUG_USE_CANARIES
 237         emem_canary(ep_canary);
 238 #endif /* DEBUG_USE_CANARIES */
 239
 240 #if !defined(SE_DEBUG_FREE)
 241 #if defined (_WIN32)
 242         /* Set up our guard page info for Win32 */
 243         GetSystemInfo(&sysinfo);
 244         pagesize = sysinfo.dwPageSize;
 245
 246         /* calling GetVersionEx using the OSVERSIONINFO structure.
 247          * OSVERSIONINFOEX requires Win NT4 with SP6 or newer NT Versions.
 248          * OSVERSIONINFOEX will fail on Win9x and older NT Versions.
 249          * See also:
 250          * http://msdn.microsoft.com/library/en-us/sysinfo/base/getversionex.asp
 251          * http://msdn.microsoft.com/library/en-us/sysinfo/base/osversioninfo_str.asp
 252          * http://msdn.microsoft.com/library/en-us/sysinfo/base/osversioninfoex_str.asp
 253          */
 254         versinfo.dwOSVersionInfoSize = sizeof(OSVERSIONINFO);
 255         GetVersionEx(&versinfo);
 256
 257 #elif defined(USE_GUARD_PAGES)
 258         pagesize = sysconf(_SC_PAGESIZE);
 259 #ifdef NEED_DEV_ZERO
 260         dev_zero_fd = ws_open("/dev/zero", O_RDWR);
 261         g_assert(dev_zero_fd != -1);
 262 #endif
 263 #endif /* _WIN32 / USE_GUARD_PAGES */
 264 #endif /* SE_DEBUG_FREE */
 265
 266
 267 }
 268 /* Initialize the capture-lifetime memory allocation pool.
 269  * This function should be called only once when Wireshark or TShark starts
 270  * up.
 271  */
 272 void
 273 se_init_chunk(void)
 274 {
 275         se_packet_mem.free_list=NULL;
 276         se_packet_mem.used_list=NULL;
 277
 278 #ifdef DEBUG_USE_CANARIES
 279         emem_canary(se_canary);
 280 #endif /* DEBUG_USE_CANARIES */
 281 }
 282
 283 #if !defined(SE_DEBUG_FREE)
 284 static void
 285 emem_create_chunk(emem_chunk_t **free_list) {
 286 #if defined (_WIN32)
 287         BOOL ret;
 288         char *buf_end, *prot1, *prot2;
 289         DWORD oldprot;
 290 #elif defined(USE_GUARD_PAGES)
 291         int ret;
 292         char *buf_end, *prot1, *prot2;
 293 #endif /* _WIN32 / USE_GUARD_PAGES */
 294         /* we dont have any free data, so we must allocate a new one */
 295         if(!*free_list){
 296                 emem_chunk_t *npc;
 297                 npc = g_malloc(sizeof(emem_chunk_t));
 298                 npc->next = NULL;
 299 #ifdef DEBUG_USE_CANARIES
 300 #if ! defined(EP_DEBUG_FREE) && ! defined(SE_DEBUG_FREE)
 301                 npc->c_count = 0;
 302 #endif
 303 #endif /* DEBUG_USE_CANARIES */
 304
 305                 *free_list = npc;
 306 #if defined (_WIN32)
 307                 /*
 308                  * MSDN documents VirtualAlloc/VirtualProtect at
 309                  * http://msdn.microsoft.com/library/en-us/memory/base/creating_guard_pages.asp
 310                  */
 311
 312                 /* XXX - is MEM_COMMIT|MEM_RESERVE correct? */
 313                 npc->buf = VirtualAlloc(NULL, EMEM_PACKET_CHUNK_SIZE,
 314                         MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE);
 315                 if(npc->buf == NULL) {
 316                         THROW(OutOfMemoryError);
 317                 }
 318                 buf_end = npc->buf + EMEM_PACKET_CHUNK_SIZE;
 319
 320                 /* Align our guard pages on page-sized boundaries */
 321                 prot1 = (char *) ((((int) npc->buf + pagesize - 1) / pagesize) * pagesize);
 322                 prot2 = (char *) ((((int) buf_end - (1 * pagesize)) / pagesize) * pagesize);
 323
 324                 ret = VirtualProtect(prot1, pagesize, PAGE_NOACCESS, &oldprot);
 325                 g_assert(ret != 0 || versinfo.dwPlatformId == VER_PLATFORM_WIN32_WINDOWS);
 326                 ret = VirtualProtect(prot2, pagesize, PAGE_NOACCESS, &oldprot);
 327                 g_assert(ret != 0 || versinfo.dwPlatformId == VER_PLATFORM_WIN32_WINDOWS);
 328
 329                 npc->amount_free_init = (unsigned int) (prot2 - prot1 - pagesize);
 330                 npc->amount_free = npc->amount_free_init;
 331                 npc->free_offset_init = (unsigned int) (prot1 - npc->buf) + pagesize;
 332                 npc->free_offset = npc->free_offset_init;
 333
 334 #elif defined(USE_GUARD_PAGES)
 335                 npc->buf = mmap(NULL, EMEM_PACKET_CHUNK_SIZE,
 336                         PROT_READ|PROT_WRITE, ANON_PAGE_MODE, ANON_FD, 0);
 337                 if(npc->buf == MAP_FAILED) {
 338                         /* XXX - what do we have to cleanup here? */
 339                         THROW(OutOfMemoryError);
 340                 }
 341                 buf_end = npc->buf + EMEM_PACKET_CHUNK_SIZE;
 342
 343                 /* Align our guard pages on page-sized boundaries */
 344                 prot1 = (char *) ((((intptr_t) npc->buf + pagesize - 1) / pagesize) * pagesize);
 345                 prot2 = (char *) ((((intptr_t) buf_end - (1 * pagesize)) / pagesize) * pagesize);
 346                 ret = mprotect(prot1, pagesize, PROT_NONE);
 347                 g_assert(ret != -1);
 348                 ret = mprotect(prot2, pagesize, PROT_NONE);
 349                 g_assert(ret != -1);
 350
 351                 npc->amount_free_init = prot2 - prot1 - pagesize;
 352                 npc->amount_free = npc->amount_free_init;
 353                 npc->free_offset_init = (prot1 - npc->buf) + pagesize;
 354                 npc->free_offset = npc->free_offset_init;
 355
 356 #else /* Is there a draft in here? */
 357                 npc->buf = malloc(EMEM_PACKET_CHUNK_SIZE);
 358                 if(npc->buf == NULL) {
 359                         THROW(OutOfMemoryError);
 360                 }
 361                 npc->amount_free_init = EMEM_PACKET_CHUNK_SIZE;
 362                 npc->amount_free = npc->amount_free_init;
 363                 npc->free_offset_init = 0;
 364                 npc->free_offset = npc->free_offset_init;
 365 #endif /* USE_GUARD_PAGES */
 366         }
 367 }
 368 #endif
 369
 370 /* allocate 'size' amount of memory. */
 371 static void *
 372 emem_alloc(size_t size, gboolean debug_free, emem_header_t *mem, guint8 *canary)
 373 {
 374         void *buf;
 375 #ifdef DEBUG_USE_CANARIES
 376         void *cptr;
 377         guint8 pad = emem_canary_pad(size);
 378 #else
 379         static guint8 pad = 8;
 380 #endif /* DEBUG_USE_CANARIES */
 381         emem_chunk_t *free_list;
 382
 383         if (!debug_free) {
 384                 /* Round up to an 8 byte boundary.      Make sure we have at least
 385                  * 8 pad bytes for our canary.
 386                  */
 387                 size += pad;
 388
 389                 /* make sure we dont try to allocate too much (arbitrary limit) */
 390                 DISSECTOR_ASSERT(size<(EMEM_PACKET_CHUNK_SIZE>>2));
 391
 392                 emem_create_chunk(&mem->free_list);
 393
 394                 /* oops, we need to allocate more memory to serve this request
 395                  * than we have free. move this node to the used list and try again
 396                  */
 397                 if(size>mem->free_list->amount_free
 398 #ifdef DEBUG_USE_CANARIES
 399                    || mem->free_list->c_count >= EMEM_ALLOCS_PER_CHUNK
 400 #endif /* DEBUG_USE_CANARIES */
 401                         ) {
 402                         emem_chunk_t *npc;
 403                         npc=mem->free_list;
 404                         mem->free_list=mem->free_list->next;
 405                         npc->next=mem->used_list;
 406                         mem->used_list=npc;
 407                 }
 408
 409                 emem_create_chunk(&mem->free_list);
 410
 411                 free_list = mem->free_list;
 412
 413                 buf = free_list->buf + free_list->free_offset;
 414
 415                 free_list->amount_free -= (unsigned int) size;
 416                 free_list->free_offset += (unsigned int) size;
 417
 418 #ifdef DEBUG_USE_CANARIES
 419                 cptr = (char *)buf + size - pad;
 420                 memcpy(cptr, canary, pad);
 421                 free_list->canary[free_list->c_count] = cptr;
 422                 free_list->cmp_len[free_list->c_count] = pad;
 423                 free_list->c_count++;
 424 #endif /* DEBUG_USE_CANARIES */
 425         } else {
 426                 emem_chunk_t *npc;
 427
 428                 npc=g_malloc(sizeof(emem_chunk_t));
 429                 npc->next=mem->used_list;
 430                 npc->amount_free=size;
 431                 npc->free_offset=0;
 432                 npc->buf=g_malloc(size);
 433                 buf = npc->buf;
 434                 mem->used_list=npc;
 435         }
 436
 437         return buf;
 438 }
 439
 440 /* allocate 'size' amount of memory with an allocation lifetime until the
 441  * next packet.
 442  */
 443 void *
 444 ep_alloc(size_t size)
 445 {
 446 #ifdef EP_DEBUG_FREE
 447         return emem_alloc(size, TRUE, &ep_packet_mem, ep_canary);
 448 #else
 449         return emem_alloc(size, FALSE, &ep_packet_mem, ep_canary);
 450 #endif
 451 }
 452
 453 /* allocate 'size' amount of memory with an allocation lifetime until the
 454  * next capture.
 455  */
 456 void *
 457 se_alloc(size_t size)
 458 {
 459 #ifdef SE_DEBUG_FREE
 460         return emem_alloc(size, TRUE, &se_packet_mem, se_canary);
 461 #else
 462         return emem_alloc(size, FALSE, &se_packet_mem, se_canary);
 463 #endif
 464 }
 465
 466 void* ep_alloc0(size_t size) {
 467         return memset(ep_alloc(size),'\0',size);
 468 }
 469
 470 gchar* ep_strdup(const gchar* src) {
 471         guint len = (guint) strlen(src);
 472         gchar* dst;
 473
 474         dst = strncpy(ep_alloc(len+1), src, len);
 475
 476         dst[len] = '\0';
 477
 478         return dst;
 479 }
 480
 481 gchar* ep_strndup(const gchar* src, size_t len) {
 482         gchar* dst = ep_alloc(len+1);
 483         guint i;
 484
 485         for (i = 0; (i < len) && src[i]; i++)
 486                 dst[i] = src[i];
 487
 488         dst[i] = '\0';
 489
 490         return dst;
 491 }
 492
 493 void* ep_memdup(const void* src, size_t len) {
 494         return memcpy(ep_alloc(len), src, len);
 495 }
 496
 497 gchar* ep_strdup_vprintf(const gchar* fmt, va_list ap) {
 498         va_list ap2;
 499         gsize len;
 500         gchar* dst;
 501
 502         G_VA_COPY(ap2, ap);
 503
 504         len = g_printf_string_upper_bound(fmt, ap);
 505
 506         dst = ep_alloc(len+1);
 507         g_vsnprintf (dst, (gulong) len, fmt, ap2);
 508         va_end(ap2);
 509
 510         return dst;
 511 }
 512
 513 gchar* ep_strdup_printf(const gchar* fmt, ...) {
 514         va_list ap;
 515         gchar* dst;
 516
 517         va_start(ap,fmt);
 518         dst = ep_strdup_vprintf(fmt, ap);
 519         va_end(ap);
 520         return dst;
 521 }
 522
 523 gchar** ep_strsplit(const gchar* string, const gchar* sep, int max_tokens) {
 524         gchar* splitted;
 525         gchar* s;
 526         guint tokens;
 527         guint str_len;
 528         guint sep_len;
 529         guint i;
 530         gchar** vec;
 531         enum { AT_START, IN_PAD, IN_TOKEN } state;
 532         guint curr_tok = 0;
 533
 534         if (    ! string
 535              || ! sep
 536              || ! sep[0])
 537                 return NULL;
 538
 539         s = splitted = ep_strdup(string);
 540         str_len = (guint) strlen(splitted);
 541         sep_len = (guint) strlen(sep);
 542
 543         if (max_tokens < 1) max_tokens = INT_MAX;
 544
 545         tokens = 1;
 546
 547
 548         while (tokens <= (guint)max_tokens && ( s = strstr(s,sep) )) {
 549                 tokens++;
 550
 551                 for(i=0; i < sep_len; i++ )
 552                         s[i] = '\0';
 553
 554                 s += sep_len;
 555
 556         }
 557
 558         vec = ep_alloc_array(gchar*,tokens+1);
 559         state = AT_START;
 560
 561         for (i=0; i< str_len; i++) {
 562                 switch(state) {
 563                         case AT_START:
 564                                 switch(splitted[i]) {
 565                                         case '\0':
 566                                                 state  = IN_PAD;
 567                                                 continue;
 568                                         default:
 569                                                 vec[curr_tok] = &(splitted[i]);
 570                                                 curr_tok++;
 571                                                 state = IN_TOKEN;
 572                                                 continue;
 573                                 }
 574                         case IN_TOKEN:
 575                                 switch(splitted[i]) {
 576                                         case '\0':
 577                                                 state = IN_PAD;
 578                                         default:
 579                                                 continue;
 580                                 }
 581                         case IN_PAD:
 582                                 switch(splitted[i]) {
 583                                         default:
 584                                                 vec[curr_tok] = &(splitted[i]);
 585                                                 curr_tok++;
 586                                                 state = IN_TOKEN;
 587                                         case '\0':
 588                                                 continue;
 589                                 }
 590                 }
 591         }
 592
 593         vec[curr_tok] = NULL;
 594
 595         return vec;
 596 }
 597
 598
 599
 600 void* se_alloc0(size_t size) {
 601         return memset(se_alloc(size),'\0',size);
 602 }
 603
 604 /* If str is NULL, just return the string "<NULL>" so that the callers dont
 605  * have to bother checking it.
 606  */
 607 gchar* se_strdup(const gchar* src) {
 608         guint len;
 609         gchar* dst;
 610
 611         if(!src){
 612                 return "<NULL>";
 613         }
 614
 615         len = (guint) strlen(src);
 616         dst = strncpy(se_alloc(len+1), src, len);
 617
 618         dst[len] = '\0';
 619
 620         return dst;
 621 }
 622
 623 gchar* se_strndup(const gchar* src, size_t len) {
 624         gchar* dst = se_alloc(len+1);
 625         guint i;
 626
 627         for (i = 0; (i < len) && src[i]; i++)
 628                 dst[i] = src[i];
 629
 630         dst[i] = '\0';
 631
 632         return dst;
 633 }
 634
 635 void* se_memdup(const void* src, size_t len) {
 636         return memcpy(se_alloc(len), src, len);
 637 }
 638
 639 gchar* se_strdup_vprintf(const gchar* fmt, va_list ap) {
 640         va_list ap2;
 641         gsize len;
 642         gchar* dst;
 643
 644         G_VA_COPY(ap2, ap);
 645
 646         len = g_printf_string_upper_bound(fmt, ap);
 647
 648         dst = se_alloc(len+1);
 649         g_vsnprintf (dst, (gulong) len, fmt, ap2);
 650         va_end(ap2);
 651
 652         return dst;
 653 }
 654
 655 gchar* se_strdup_printf(const gchar* fmt, ...) {
 656         va_list ap;
 657         gchar* dst;
 658
 659         va_start(ap,fmt);
 660         dst = se_strdup_vprintf(fmt, ap);
 661         va_end(ap);
 662         return dst;
 663 }
 664
 665 /* release all allocated memory back to the pool. */
 666 static void
 667 emem_free_all(gboolean debug_free, emem_header_t *mem, guint8 *canary, emem_tree_t *trees)
 668 {
 669         emem_chunk_t *npc;
 670         emem_tree_t *tree_list;
 671 #ifdef DEBUG_USE_CANARIES
 672         guint i;
 673 #endif /* DEBUG_USE_CANARIES */
 674
 675         /* move all used chunks over to the free list */
 676         while(mem->used_list){
 677                 npc=mem->used_list;
 678                 mem->used_list=mem->used_list->next;
 679                 npc->next=mem->free_list;
 680                 mem->free_list=npc;
 681         }
 682
 683         /* clear them all out */
 684         npc = mem->free_list;
 685         while (npc != NULL) {
 686                 if (!debug_free) {
 687 #ifdef DEBUG_USE_CANARIES
 688                         for (i = 0; i < npc->c_count; i++) {
 689                                 if (memcmp(npc->canary[i], canary, npc->cmp_len[i]) != 0)
 690                                         g_error("Memory corrupted");
 691                         }
 692                         npc->c_count = 0;
 693 #endif /* DEBUG_USE_CANARIES */
 694                         npc->amount_free = npc->amount_free_init;
 695                         npc->free_offset = npc->free_offset_init;
 696                         npc = npc->next;
 697                 } else {
 698                         emem_chunk_t *next = npc->next;
 699
 700                         g_free(npc->buf);
 701                         g_free(npc);
 702                         npc = next;
 703                 }
 704         }
 705
 706         /* release/reset all allocated trees */
 707         for(tree_list=trees;tree_list;tree_list=tree_list->next){
 708                 tree_list->tree=NULL;
 709         }
 710 }
 711
 712 /* release all allocated memory back to the pool. */
 713 void
 714 ep_free_all(void)
 715 {
 716 #ifdef EP_DEBUG_FREE
 717     emem_free_all(TRUE, &ep_packet_mem, ep_canary, NULL);
 718 #else
 719     emem_free_all(FALSE, &ep_packet_mem, ep_canary, NULL);
 720 #endif
 721
 722 #ifdef EP_DEBUG_FREE
 723         ep_init_chunk();
 724 #endif
 725 }
 726
 727 /* release all allocated memory back to the pool. */
 728 void
 729 se_free_all(void)
 730 {
 731 #ifdef SE_DEBUG_FREE
 732     emem_free_all(TRUE, &se_packet_mem, se_canary, se_trees);
 733 #else
 734     emem_free_all(FALSE, &se_packet_mem, se_canary, se_trees);
 735 #endif
 736
 737 #ifdef SE_DEBUG_FREE
 738         se_init_chunk();
 739 #endif
 740 }
 741
 742 ep_stack_t ep_stack_new(void) {
 743         ep_stack_t s = ep_new(struct _ep_stack_frame_t*);
 744         *s = ep_new0(struct _ep_stack_frame_t);
 745         return s;
 746 }
 747
 748 /*  for ep_stack_t we'll keep the popped frames so we reuse them instead
 749 of allocating new ones.
 750 */
 751
 752
 753 void* ep_stack_push(ep_stack_t stack, void* data) {
 754         struct _ep_stack_frame_t* frame;
 755         struct _ep_stack_frame_t* head = (*stack);
 756
 757         if (head->above) {
 758                 frame = head->above;
 759         } else {
 760                 frame = ep_new(struct _ep_stack_frame_t);
 761                 head->above = frame;
 762                 frame->below = head;
 763                 frame->above = NULL;
 764         }
 765
 766         frame->payload = data;
 767         (*stack) = frame;
 768
 769         return data;
 770 }
 771
 772 void* ep_stack_pop(ep_stack_t stack) {
 773
 774         if ((*stack)->below) {
 775                 (*stack) = (*stack)->below;
 776                 return (*stack)->above->payload;
 777         } else {
 778                 return NULL;
 779         }
 780 }
 781
 782
 783
 784 #ifdef REMOVED
 785 void print_tree_item(emem_tree_node_t *node, int level){
 786         int i;
 787         for(i=0;i<level;i++){
 788                 printf("   ");
 789         }
 790         printf("%s  KEY:0x%08x node:0x%08x parent:0x%08x left:0x%08x right:0x%08x\n",node->u.rb_color==EMEM_TREE_RB_COLOR_BLACK?"BLACK":"RED",node->key32,(int)node,(int)node->parent,(int)node->left,(int)node->right);
 791         if(node->left)
 792                 print_tree_item(node->left,level+1);
 793         if(node->right)
 794                 print_tree_item(node->right,level+1);
 795 }
 796
 797 void print_tree(emem_tree_node_t *node){
 798         if(!node){
 799                 return;
 800         }
 801         while(node->parent){
 802                 node=node->parent;
 803         }
 804         print_tree_item(node,0);
 805 }
 806 #endif
 807
 808
 809
 810 /* routines to manage se allocated red-black trees */
 811 emem_tree_t *se_trees=NULL;
 812
 813 emem_tree_t *
 814 se_tree_create(int type, const char *name)
 815 {
 816         emem_tree_t *tree_list;
 817
 818         tree_list=malloc(sizeof(emem_tree_t));
 819         tree_list->next=se_trees;
 820         tree_list->type=type;
 821         tree_list->tree=NULL;
 822         tree_list->name=name;
 823         tree_list->malloc=se_alloc;
 824         se_trees=tree_list;
 825
 826         return tree_list;
 827 }
 828
 829
 830
 831 void *
 832 emem_tree_lookup32(emem_tree_t *se_tree, guint32 key)
 833 {
 834         emem_tree_node_t *node;
 835
 836         node=se_tree->tree;
 837
 838         while(node){
 839                 if(key==node->key32){
 840                         return node->data;
 841                 }
 842                 if(key<node->key32){
 843                         node=node->left;
 844                         continue;
 845                 }
 846                 if(key>node->key32){
 847                         node=node->right;
 848                         continue;
 849                 }
 850         }
 851         return NULL;
 852 }
 853
 854 void *
 855 emem_tree_lookup32_le(emem_tree_t *se_tree, guint32 key)
 856 {
 857         emem_tree_node_t *node;
 858
 859         node=se_tree->tree;
 860
 861         if(!node){
 862                 return NULL;
 863         }
 864
 865
 866         while(node){
 867                 if(key==node->key32){
 868                         return node->data;
 869                 }
 870                 if(key<node->key32){
 871                         if(node->left){
 872                                 node=node->left;
 873                                 continue;
 874                         } else {
 875                                 break;
 876                         }
 877                 }
 878                 if(key>node->key32){
 879                         if(node->right){
 880                                 node=node->right;
 881                                 continue;
 882                         } else {
 883                                 break;
 884                         }
 885                 }
 886         }
 887
 888
 889         /* If we are still at the root of the tree this means that this node
 890          * is either smaller than the search key and then we return this
 891          * node or else there is no smaller key available and then
 892          * we return NULL.
 893          */
 894         if(!node->parent){
 895                 if(key>node->key32){
 896                         return node->data;
 897                 } else {
 898                         return NULL;
 899                 }
 900         }
 901
 902         if(node->parent->left==node){
 903                 /* left child */
 904
 905                 if(key>node->key32){
 906                         /* if this is a left child and its key is smaller than
 907                          * the search key, then this is the node we want.
 908                          */
 909                         return node->data;
 910                 } else {
 911                         /* if this is a left child and its key is bigger than
 912                          * the search key, we have to check if any
 913                          * of our ancestors are smaller than the search key.
 914                          */
 915                         while(node){
 916                                 if(key>node->key32){
 917                                         return node->data;
 918                                 }
 919                                 node=node->parent;
 920                         }
 921                         return NULL;
 922                 }
 923         } else {
 924                 /* right child */
 925
 926                 if(node->key32<key){
 927                         /* if this is the right child and its key is smaller
 928                          * than the search key then this is the one we want.
 929                          */
 930                         return node->data;
 931                 } else {
 932                         /* if this is the right child and its key is larger
 933                          * than the search key then our parent is the one we
 934                          * want.
 935                          */
 936                         return node->parent->data;
 937                 }
 938         }
 939
 940 }
 941
 942
 943 static inline emem_tree_node_t *
 944 emem_tree_parent(emem_tree_node_t *node)
 945 {
 946         return node->parent;
 947 }
 948
 949 static inline emem_tree_node_t *
 950 emem_tree_grandparent(emem_tree_node_t *node)
 951 {
 952         emem_tree_node_t *parent;
 953
 954         parent=emem_tree_parent(node);
 955         if(parent){
 956                 return parent->parent;
 957         }
 958         return NULL;
 959 }
 960 static inline emem_tree_node_t *
 961 emem_tree_uncle(emem_tree_node_t *node)
 962 {
 963         emem_tree_node_t *parent, *grandparent;
 964
 965         parent=emem_tree_parent(node);
 966         if(!parent){
 967                 return NULL;
 968         }
 969         grandparent=emem_tree_parent(parent);
 970         if(!grandparent){
 971                 return NULL;
 972         }
 973         if(parent==grandparent->left){
 974                 return grandparent->right;
 975         }
 976         return grandparent->left;
 977 }
 978
 979 static inline void rb_insert_case1(emem_tree_t *se_tree, emem_tree_node_t *node);
 980 static inline void rb_insert_case2(emem_tree_t *se_tree, emem_tree_node_t *node);
 981
 982 static inline void
 983 rotate_left(emem_tree_t *se_tree, emem_tree_node_t *node)
 984 {
 985         if(node->parent){
 986                 if(node->parent->left==node){
 987                         node->parent->left=node->right;
 988                 } else {
 989                         node->parent->right=node->right;
 990                 }
 991         } else {
 992                 se_tree->tree=node->right;
 993         }
 994         node->right->parent=node->parent;
 995         node->parent=node->right;
 996         node->right=node->right->left;
 997         if(node->right){
 998                 node->right->parent=node;
 999         }
1000         node->parent->left=node;
1001 }
1002
1003 static inline void
1004 rotate_right(emem_tree_t *se_tree, emem_tree_node_t *node)
1005 {
1006         if(node->parent){
1007                 if(node->parent->left==node){
1008                         node->parent->left=node->left;
1009                 } else {
1010                         node->parent->right=node->left;
1011                 }
1012         } else {
1013                 se_tree->tree=node->left;
1014         }
1015         node->left->parent=node->parent;
1016         node->parent=node->left;
1017         node->left=node->left->right;
1018         if(node->left){
1019                 node->left->parent=node;
1020         }
1021         node->parent->right=node;
1022 }
1023
1024 static inline void
1025 rb_insert_case5(emem_tree_t *se_tree, emem_tree_node_t *node)
1026 {
1027         emem_tree_node_t *grandparent;
1028         emem_tree_node_t *parent;
1029
1030         parent=emem_tree_parent(node);
1031         grandparent=emem_tree_parent(parent);
1032         parent->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1033         grandparent->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1034         if( (node==parent->left) && (parent==grandparent->left) ){
1035                 rotate_right(se_tree, grandparent);
1036         } else {
1037                 rotate_left(se_tree, grandparent);
1038         }
1039 }
1040
1041 static inline void
1042 rb_insert_case4(emem_tree_t *se_tree, emem_tree_node_t *node)
1043 {
1044         emem_tree_node_t *grandparent;
1045         emem_tree_node_t *parent;
1046
1047         parent=emem_tree_parent(node);
1048         grandparent=emem_tree_parent(parent);
1049         if(!grandparent){
1050                 return;
1051         }
1052         if( (node==parent->right) && (parent==grandparent->left) ){
1053                 rotate_left(se_tree, parent);
1054                 node=node->left;
1055         } else if( (node==parent->left) && (parent==grandparent->right) ){
1056                 rotate_right(se_tree, parent);
1057                 node=node->right;
1058         }
1059         rb_insert_case5(se_tree, node);
1060 }
1061
1062 static inline void
1063 rb_insert_case3(emem_tree_t *se_tree, emem_tree_node_t *node)
1064 {
1065         emem_tree_node_t *grandparent;
1066         emem_tree_node_t *parent;
1067         emem_tree_node_t *uncle;
1068
1069         uncle=emem_tree_uncle(node);
1070         if(uncle && (uncle->u.rb_color==EMEM_TREE_RB_COLOR_RED)){
1071                 parent=emem_tree_parent(node);
1072                 parent->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1073                 uncle->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1074                 grandparent=emem_tree_grandparent(node);
1075                 grandparent->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1076                 rb_insert_case1(se_tree, grandparent);
1077         } else {
1078                 rb_insert_case4(se_tree, node);
1079         }
1080 }
1081
1082 static inline void
1083 rb_insert_case2(emem_tree_t *se_tree, emem_tree_node_t *node)
1084 {
1085         emem_tree_node_t *parent;
1086
1087         parent=emem_tree_parent(node);
1088         /* parent is always non-NULL here */
1089         if(parent->u.rb_color==EMEM_TREE_RB_COLOR_BLACK){
1090                 return;
1091         }
1092         rb_insert_case3(se_tree, node);
1093 }
1094
1095 static inline void
1096 rb_insert_case1(emem_tree_t *se_tree, emem_tree_node_t *node)
1097 {
1098         emem_tree_node_t *parent;
1099
1100         parent=emem_tree_parent(node);
1101         if(!parent){
1102                 node->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1103                 return;
1104         }
1105         rb_insert_case2(se_tree, node);
1106 }
1107
1108 /* insert a new node in the tree. if this node matches an already existing node
1109  * then just replace the data for that node */
1110 void
1111 emem_tree_insert32(emem_tree_t *se_tree, guint32 key, void *data)
1112 {
1113         emem_tree_node_t *node;
1114
1115         node=se_tree->tree;
1116
1117         /* is this the first node ?*/
1118         if(!node){
1119                 node=se_tree->malloc(sizeof(emem_tree_node_t));
1120                 switch(se_tree->type){
1121                 case EMEM_TREE_TYPE_RED_BLACK:
1122                         node->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1123                         break;
1124                 }
1125                 node->parent=NULL;
1126                 node->left=NULL;
1127                 node->right=NULL;
1128                 node->key32=key;
1129                 node->data=data;
1130                 node->u.is_subtree = EMEM_TREE_NODE_IS_DATA;
1131                 se_tree->tree=node;
1132                 return;
1133         }
1134
1135         /* it was not the new root so walk the tree until we find where to
1136          * insert this new leaf.
1137          */
1138         while(1){
1139                 /* this node already exists, so just replace the data pointer*/
1140                 if(key==node->key32){
1141                         node->data=data;
1142                         return;
1143                 }
1144                 if(key<node->key32) {
1145                         if(!node->left){
1146                                 /* new node to the left */
1147                                 emem_tree_node_t *new_node;
1148                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1149                                 node->left=new_node;
1150                                 new_node->parent=node;
1151                                 new_node->left=NULL;
1152                                 new_node->right=NULL;
1153                                 new_node->key32=key;
1154                                 new_node->data=data;
1155                                 new_node->u.is_subtree=EMEM_TREE_NODE_IS_DATA;
1156                                 node=new_node;
1157                                 break;
1158                         }
1159                         node=node->left;
1160                         continue;
1161                 }
1162                 if(key>node->key32) {
1163                         if(!node->right){
1164                                 /* new node to the right */
1165                                 emem_tree_node_t *new_node;
1166                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1167                                 node->right=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                                 new_node->u.is_subtree=EMEM_TREE_NODE_IS_DATA;
1174                                 node=new_node;
1175                                 break;
1176                         }
1177                         node=node->right;
1178                         continue;
1179                 }
1180         }
1181
1182         /* node will now point to the newly created node */
1183         switch(se_tree->type){
1184         case EMEM_TREE_TYPE_RED_BLACK:
1185                 node->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1186                 rb_insert_case1(se_tree, node);
1187                 break;
1188         }
1189 }
1190
1191 static void* lookup_or_insert32(emem_tree_t *se_tree, guint32 key, void*(*func)(void*),void* ud, int is_subtree) {
1192         emem_tree_node_t *node;
1193
1194         node=se_tree->tree;
1195
1196         /* is this the first node ?*/
1197         if(!node){
1198                 node=se_tree->malloc(sizeof(emem_tree_node_t));
1199                 switch(se_tree->type){
1200                         case EMEM_TREE_TYPE_RED_BLACK:
1201                                 node->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
1202                                 break;
1203                 }
1204                 node->parent=NULL;
1205                 node->left=NULL;
1206                 node->right=NULL;
1207                 node->key32=key;
1208                 node->data= func(ud);
1209                 node->u.is_subtree = is_subtree;
1210                 se_tree->tree=node;
1211                 return node->data;
1212         }
1213
1214         /* it was not the new root so walk the tree until we find where to
1215                 * insert this new leaf.
1216                 */
1217         while(1){
1218                 /* this node already exists, so just return the data pointer*/
1219                 if(key==node->key32){
1220                         return node->data;
1221                 }
1222                 if(key<node->key32) {
1223                         if(!node->left){
1224                                 /* new node to the left */
1225                                 emem_tree_node_t *new_node;
1226                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1227                                 node->left=new_node;
1228                                 new_node->parent=node;
1229                                 new_node->left=NULL;
1230                                 new_node->right=NULL;
1231                                 new_node->key32=key;
1232                                 new_node->data= func(ud);
1233                                 new_node->u.is_subtree = is_subtree;
1234                                 node=new_node;
1235                                 break;
1236                         }
1237                         node=node->left;
1238                         continue;
1239                 }
1240                 if(key>node->key32) {
1241                         if(!node->right){
1242                                 /* new node to the right */
1243                                 emem_tree_node_t *new_node;
1244                                 new_node=se_tree->malloc(sizeof(emem_tree_node_t));
1245                                 node->right=new_node;
1246                                 new_node->parent=node;
1247                                 new_node->left=NULL;
1248                                 new_node->right=NULL;
1249                                 new_node->key32=key;
1250                                 new_node->data= func(ud);
1251                                 new_node->u.is_subtree = is_subtree;
1252                                 node=new_node;
1253                                 break;
1254                         }
1255                         node=node->right;
1256                         continue;
1257                 }
1258         }
1259
1260         /* node will now point to the newly created node */
1261         switch(se_tree->type){
1262                 case EMEM_TREE_TYPE_RED_BLACK:
1263                         node->u.rb_color=EMEM_TREE_RB_COLOR_RED;
1264                         rb_insert_case1(se_tree, node);
1265                         break;
1266         }
1267
1268         return node->data;
1269 }
1270
1271 /* When the se data is released, this entire tree will dissapear as if it
1272  * never existed including all metadata associated with the tree.
1273  */
1274 emem_tree_t *
1275 se_tree_create_non_persistent(int type, const char *name)
1276 {
1277         emem_tree_t *tree_list;
1278
1279         tree_list=se_alloc(sizeof(emem_tree_t));
1280         tree_list->next=NULL;
1281         tree_list->type=type;
1282         tree_list->tree=NULL;
1283         tree_list->name=name;
1284         tree_list->malloc=se_alloc;
1285
1286         return tree_list;
1287 }
1288
1289 /* This tree is PErmanent and will never be released
1290  */
1291 emem_tree_t *
1292 pe_tree_create(int type, const char *name)
1293 {
1294         emem_tree_t *tree_list;
1295
1296         tree_list=g_malloc(sizeof(emem_tree_t));
1297         tree_list->next=NULL;
1298         tree_list->type=type;
1299         tree_list->tree=NULL;
1300         tree_list->name=name;
1301         tree_list->malloc=(void *(*)(size_t)) g_malloc;
1302
1303         return tree_list;
1304 }
1305
1306 /* create another (sub)tree using the same memory allocation scope
1307  * as the parent tree.
1308  */
1309 static emem_tree_t *
1310 emem_tree_create_subtree(emem_tree_t *parent_tree, const char *name)
1311 {
1312         emem_tree_t *tree_list;
1313
1314         tree_list=parent_tree->malloc(sizeof(emem_tree_t));
1315         tree_list->next=NULL;
1316         tree_list->type=parent_tree->type;
1317         tree_list->tree=NULL;
1318         tree_list->name=name;
1319         tree_list->malloc=parent_tree->malloc;
1320
1321         return tree_list;
1322 }
1323
1324 static void* create_sub_tree(void* d) {
1325         emem_tree_t *se_tree = d;
1326         return emem_tree_create_subtree(se_tree, "subtree");
1327 }
1328
1329 /* insert a new node in the tree. if this node matches an already existing node
1330  * then just replace the data for that node */
1331
1332 void
1333 emem_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data)
1334 {
1335         emem_tree_t *next_tree;
1336
1337         if((key[0].length<1)||(key[0].length>100)){
1338                 DISSECTOR_ASSERT_NOT_REACHED();
1339         }
1340         if((key[0].length==1)&&(key[1].length==0)){
1341                 emem_tree_insert32(se_tree, *key[0].key, data);
1342                 return;
1343         }
1344
1345         next_tree=lookup_or_insert32(se_tree, *key[0].key, create_sub_tree, se_tree, EMEM_TREE_NODE_IS_SUBTREE);
1346
1347         if(key[0].length==1){
1348                 key++;
1349         } else {
1350                 key[0].length--;
1351                 key[0].key++;
1352         }
1353         emem_tree_insert32_array(next_tree, key, data);
1354 }
1355
1356 void *
1357 emem_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key)
1358 {
1359         emem_tree_t *next_tree;
1360
1361         if((key[0].length<1)||(key[0].length>100)){
1362                 DISSECTOR_ASSERT_NOT_REACHED();
1363         }
1364         if((key[0].length==1)&&(key[1].length==0)){
1365                 return emem_tree_lookup32(se_tree, *key[0].key);
1366         }
1367         next_tree=emem_tree_lookup32(se_tree, *key[0].key);
1368         if(!next_tree){
1369                 return NULL;
1370         }
1371         if(key[0].length==1){
1372                 key++;
1373         } else {
1374                 key[0].length--;
1375                 key[0].key++;
1376         }
1377         return emem_tree_lookup32_array(next_tree, key);
1378 }
1379
1380
1381 /* Strings are stored as an array of uint32 containing the string characters
1382    with 4 characters in each uint32.
1383    The first byte of the string is stored as the most significant byte.
1384    If the string is not a multiple of 4 characters in length the last
1385    uint32 containing the string bytes are padded with 0 bytes.
1386    After the uint32's containing the string, there is one final terminator
1387    uint32 with the value 0x00000001
1388 */
1389 void
1390 emem_tree_insert_string(emem_tree_t* se_tree, const gchar* k, void* v, guint32 flags)
1391 {
1392         emem_tree_key_t key[2];
1393         guint32 *aligned=NULL;
1394         guint32 len = (guint32) strlen(k);
1395         guint32 div = (len+3)/4+1;
1396         guint32 i;
1397         guint32 tmp;
1398
1399         aligned = malloc(div * sizeof (guint32));
1400
1401         /* pack the bytes one one by one into guint32s */
1402         tmp = 0;
1403         for (i = 0;i < len;i++) {
1404                 unsigned char ch;
1405
1406                 ch = (unsigned char)k[i];
1407                 if (flags & EMEM_TREE_STRING_NOCASE) {
1408                         if(isupper(ch)) {
1409                                 ch = tolower(ch);
1410                         }
1411                 }
1412                 tmp <<= 8;
1413                 tmp |= ch;
1414                 if (i%4 == 3) {
1415                         aligned[i/4] = tmp;
1416                         tmp = 0;
1417                 }
1418         }
1419         /* add required padding to the last uint32 */
1420         if (i%4 != 0) {
1421                 while (i%4 != 0) {
1422                         i++;
1423                         tmp <<= 8;
1424                 }
1425                 aligned[i/4-1] = tmp;
1426         }
1427
1428         /* add the terminator */
1429         aligned[div-1] = 0x00000001;
1430
1431         key[0].length = div;
1432         key[0].key = aligned;
1433         key[1].length = 0;
1434         key[1].key = NULL;
1435
1436
1437         emem_tree_insert32_array(se_tree, key, v);
1438         free(aligned);
1439 }
1440
1441 void *
1442 emem_tree_lookup_string(emem_tree_t* se_tree, const gchar* k, guint32 flags)
1443 {
1444         emem_tree_key_t key[2];
1445         guint32 *aligned=NULL;
1446         guint32 len = (guint) strlen(k);
1447         guint32 div = (len+3)/4+1;
1448         guint32 i;
1449         guint32 tmp;
1450         void *ret;
1451
1452         aligned = malloc(div * sizeof (guint32));
1453
1454         /* pack the bytes one one by one into guint32s */
1455         tmp = 0;
1456         for (i = 0;i < len;i++) {
1457                 unsigned char ch;
1458
1459                 ch = (unsigned char)k[i];
1460                 if (flags & EMEM_TREE_STRING_NOCASE) {
1461                         if(isupper(ch)) {
1462                                 ch = tolower(ch);
1463                         }
1464                 }
1465                 tmp <<= 8;
1466                 tmp |= ch;
1467                 if (i%4 == 3) {
1468                         aligned[i/4] = tmp;
1469                         tmp = 0;
1470                 }
1471         }
1472         /* add required padding to the last uint32 */
1473         if (i%4 != 0) {
1474                 while (i%4 != 0) {
1475                         i++;
1476                         tmp <<= 8;
1477                 }
1478                 aligned[i/4-1] = tmp;
1479         }
1480
1481         /* add the terminator */
1482         aligned[div-1] = 0x00000001;
1483
1484         key[0].length = div;
1485         key[0].key = aligned;
1486         key[1].length = 0;
1487         key[1].key = NULL;
1488
1489
1490         ret = emem_tree_lookup32_array(se_tree, key);
1491         free(aligned);
1492         return ret;
1493 }
1494
1495 static gboolean
1496 emem_tree_foreach_nodes(emem_tree_node_t* node, tree_foreach_func callback, void *user_data)
1497 {
1498         gboolean stop_traverse = FALSE;
1499
1500         if (!node)
1501                 return FALSE;
1502
1503         if(node->left) {
1504                 stop_traverse = emem_tree_foreach_nodes(node->left, callback, user_data);
1505                 if (stop_traverse) {
1506                         return TRUE;
1507                 }
1508         }
1509
1510         if (node->u.is_subtree == EMEM_TREE_NODE_IS_SUBTREE) {
1511                 stop_traverse = emem_tree_foreach(node->data, callback, user_data);
1512         } else {
1513                 stop_traverse = callback(node->data, user_data);
1514         }
1515
1516         if (stop_traverse) {
1517                 return TRUE;
1518         }
1519
1520         if(node->right) {
1521                 stop_traverse = emem_tree_foreach_nodes(node->right, callback, user_data);
1522                 if (stop_traverse) {
1523                         return TRUE;
1524                 }
1525         }
1526
1527         return FALSE;
1528 }
1529
1530 gboolean
1531 emem_tree_foreach(emem_tree_t* emem_tree, tree_foreach_func callback, void *user_data)
1532 {
1533         if (!emem_tree)
1534                 return FALSE;
1535
1536         if(!emem_tree->tree)
1537                 return FALSE;
1538
1539         return emem_tree_foreach_nodes(emem_tree->tree, callback, user_data);
1540 }
1541
1542
1543 static void
1544 emem_tree_print_nodes(emem_tree_node_t* node, int level)
1545 {
1546         int i;
1547
1548         if (!node)
1549                 return;
1550
1551         for(i=0;i<level;i++){
1552                 printf("    ");
1553         }
1554
1555         printf("NODE:%p parent:%p left:0x%p right:%px key:%d data:%p\n",
1556                 (void *)node,(void *)(node->parent),(void *)(node->left),(void *)(node->right),
1557                 (node->key32),node->data);
1558         if(node->left)
1559                 emem_tree_print_nodes(node->left, level+1);
1560         if(node->right)
1561                 emem_tree_print_nodes(node->right, level+1);
1562 }
1563 void
1564 emem_print_tree(emem_tree_t* emem_tree)
1565 {
1566         if (!emem_tree)
1567                 return;
1568
1569         printf("EMEM tree type:%d name:%s tree:%p\n",emem_tree->type,emem_tree->name,(void *)(emem_tree->tree));
1570         if(emem_tree->tree)
1571                 emem_tree_print_nodes(emem_tree->tree, 0);
1572 }
1573
1574 /*
1575  * String buffers
1576  */
1577
1578 /*
1579  * Presumably we're using these routines for building strings for the tree.
1580  * Use ITEM_LABEL_LENGTH as the basis for our default lengths.
1581  */
1582
1583 #define DEFAULT_STRBUF_LEN (ITEM_LABEL_LENGTH / 10)
1584 #define MAX_STRBUF_LEN 65536
1585
1586 static gsize
1587 next_size(gsize cur_alloc_len, gsize wanted_alloc_len, gsize max_alloc_len) {
1588         if (max_alloc_len < 1 || max_alloc_len > MAX_STRBUF_LEN) {
1589                 max_alloc_len = MAX_STRBUF_LEN;
1590         }
1591
1592         if (cur_alloc_len < 1) {
1593                 cur_alloc_len = DEFAULT_STRBUF_LEN;
1594         }
1595
1596         while (cur_alloc_len < wanted_alloc_len) {
1597                 cur_alloc_len *= 2;
1598         }
1599
1600         return cur_alloc_len < max_alloc_len ? cur_alloc_len : max_alloc_len;
1601 }
1602
1603 static void
1604 ep_strbuf_grow(emem_strbuf_t *strbuf, gsize wanted_alloc_len) {
1605         gsize new_alloc_len;
1606         gchar *new_str;
1607
1608         if (!strbuf || (wanted_alloc_len <= strbuf->alloc_len) || (strbuf->alloc_len >= strbuf->max_alloc_len)) {
1609                 return;
1610         }
1611
1612         new_alloc_len = next_size(strbuf->alloc_len, wanted_alloc_len, strbuf->max_alloc_len);
1613         new_str = ep_alloc(new_alloc_len);
1614         g_strlcpy(new_str, strbuf->str, new_alloc_len);
1615
1616         strbuf->alloc_len = new_alloc_len;
1617         strbuf->str = new_str;
1618 }
1619
1620 emem_strbuf_t *
1621 ep_strbuf_sized_new(gsize alloc_len, gsize max_alloc_len) {
1622         emem_strbuf_t *strbuf;
1623
1624         strbuf = ep_alloc(sizeof(emem_strbuf_t));
1625
1626         if ((max_alloc_len == 0) || (max_alloc_len > MAX_STRBUF_LEN))
1627                 max_alloc_len = MAX_STRBUF_LEN;
1628         if (alloc_len == 0)
1629                 alloc_len = 1;
1630         else if (alloc_len > max_alloc_len)
1631                 alloc_len = max_alloc_len;
1632
1633         strbuf->str = ep_alloc(alloc_len);
1634         strbuf->str[0] = '\0';
1635
1636         strbuf->len = 0;
1637         strbuf->alloc_len = alloc_len;
1638         strbuf->max_alloc_len = max_alloc_len;
1639
1640         return strbuf;
1641 }
1642
1643 emem_strbuf_t *
1644 ep_strbuf_new(const gchar *init) {
1645         emem_strbuf_t *strbuf;
1646
1647         strbuf = ep_strbuf_sized_new(next_size(0, init?strlen(init):0, 0), 0);
1648         if (init) {
1649                 gsize full_len;
1650                 full_len = g_strlcpy(strbuf->str, init, strbuf->alloc_len);
1651                 strbuf->len = MIN(full_len, strbuf->alloc_len-1);
1652         }
1653
1654         return strbuf;
1655 }
1656
1657 emem_strbuf_t *
1658 ep_strbuf_new_label(const gchar *init) {
1659         emem_strbuf_t *strbuf;
1660         gsize full_len;
1661
1662         /* Be optimistic: Allocate default size strbuf string and only      */
1663         /*  request an increase if needed.                                  */
1664         /* XXX: Is it reasonable to assume that much of the usage of        */
1665         /*  ep_strbuf_new_label will have  init==NULL or                    */
1666         /*   strlen(init) < DEFAULT_STRBUF_LEN) ???                         */
1667         strbuf = ep_strbuf_sized_new(DEFAULT_STRBUF_LEN, ITEM_LABEL_LENGTH);
1668
1669         if (!init)
1670                 return strbuf;
1671
1672         /* full_len does not count the trailing '\0'.                       */
1673         full_len = g_strlcpy(strbuf->str, init, strbuf->alloc_len);
1674         if (full_len < strbuf->alloc_len) {
1675                 strbuf->len += full_len;
1676         } else {
1677                 strbuf = ep_strbuf_sized_new(full_len+1, ITEM_LABEL_LENGTH);
1678                 full_len = g_strlcpy(strbuf->str, init, strbuf->alloc_len);
1679                 strbuf->len = MIN(full_len, strbuf->alloc_len-1);
1680         }
1681
1682         return strbuf;
1683 }
1684
1685 emem_strbuf_t *
1686 ep_strbuf_append(emem_strbuf_t *strbuf, const gchar *str) {
1687         gsize add_len, full_len;
1688
1689         if (!strbuf || !str || str[0] == '\0') {
1690                 return strbuf;
1691         }
1692
1693         /* Be optimistic; try the g_strlcpy first & see if enough room.                 */
1694         /* Note: full_len doesn't count the trailing '\0'; add_len does allow for same  */
1695         add_len = strbuf->alloc_len - strbuf->len;
1696         full_len = g_strlcpy(&strbuf->str[strbuf->len], str, add_len);
1697         if (full_len < add_len) {
1698                 strbuf->len += full_len;
1699         } else {
1700                 strbuf->str[strbuf->len] = '\0'; /* end string at original length again */
1701                 ep_strbuf_grow(strbuf, strbuf->len + full_len + 1);
1702                 add_len = strbuf->alloc_len - strbuf->len;
1703                 full_len = g_strlcpy(&strbuf->str[strbuf->len], str, add_len);
1704                 strbuf->len += MIN(add_len-1, full_len);
1705         }
1706
1707         return strbuf;
1708 }
1709
1710 void
1711 ep_strbuf_append_vprintf(emem_strbuf_t *strbuf, const gchar *format, va_list ap) {
1712         va_list ap2;
1713         gsize add_len, full_len;
1714
1715         G_VA_COPY(ap2, ap);
1716
1717         /* Be optimistic; try the g_vsnprintf first & see if enough room.               */
1718         /* Note: full_len doesn't count the trailing '\0'; add_len does allow for same. */
1719         add_len = strbuf->alloc_len - strbuf->len;
1720         full_len = g_vsnprintf(&strbuf->str[strbuf->len], (gulong) add_len, format, ap);
1721         if (full_len < add_len) {
1722                 strbuf->len += full_len;
1723         } else {
1724                 strbuf->str[strbuf->len] = '\0'; /* end string at original length again */
1725                 ep_strbuf_grow(strbuf, strbuf->len + full_len + 1);
1726                 add_len = strbuf->alloc_len - strbuf->len;
1727                 full_len = g_vsnprintf(&strbuf->str[strbuf->len], (gulong) add_len, format, ap2);
1728                 strbuf->len += MIN(add_len-1, full_len);
1729         }
1730
1731         va_end(ap2);
1732 }
1733
1734 void
1735 ep_strbuf_append_printf(emem_strbuf_t *strbuf, const gchar *format, ...) {
1736         va_list ap;
1737
1738         va_start(ap, format);
1739         ep_strbuf_append_vprintf(strbuf, format, ap);
1740         va_end(ap);
1741 }
1742
1743 void
1744 ep_strbuf_printf(emem_strbuf_t *strbuf, const gchar *format, ...) {
1745         va_list ap;
1746         if (!strbuf) {
1747                 return;
1748         }
1749
1750         strbuf->len = 0;
1751
1752         va_start(ap, format);
1753         ep_strbuf_append_vprintf(strbuf, format, ap);
1754         va_end(ap);
1755 }
1756
1757 emem_strbuf_t *
1758 ep_strbuf_append_c(emem_strbuf_t *strbuf, const gchar c) {
1759         if (!strbuf) {
1760                 return strbuf;
1761         }
1762
1763         /* +1 for the new character & +1 for the trailing '\0'. */
1764         if (strbuf->alloc_len < strbuf->len + 1 + 1) {
1765                 ep_strbuf_grow(strbuf, strbuf->len + 1 + 1);
1766         }
1767         if (strbuf->alloc_len >= strbuf->len + 1 + 1) {
1768                 strbuf->str[strbuf->len] = c;
1769                 strbuf->len++;
1770                 strbuf->str[strbuf->len] = '\0';
1771         }
1772
1773         return strbuf;
1774 }
1775
1776 emem_strbuf_t *
1777 ep_strbuf_truncate(emem_strbuf_t *strbuf, gsize len) {
1778         if (!strbuf || len >= strbuf->len) {
1779                 return strbuf;
1780         }
1781
1782         strbuf->str[len] = '\0';
1783         strbuf->len = len;
1784
1785         return strbuf;
1786 }
1787
1788 /*
1789  * Editor modelines
1790  *
1791  * Local Variables:
1792  * c-basic-offset: 8
1793  * tab-width: 8
1794  * indent-tabs-mode: t
1795  * End:
1796  *
1797  * ex: set shiftwidth=8 tabstop=8 noexpandtab
1798  * :indentSize=8:tabSize=8:noTabs=false:
1799  */