epan/emem.c

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