New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Memory corruption error in "trie_new" method when using libdatrie v2.10.0 #6

truebit opened this Issue May 1, 2017 · 3 comments


None yet
3 participants
Copy link

truebit commented May 1, 2017

I used libdatrie v2.9.0 in a PHP extension and it works.
I saw there was a libdatrie v2.10.0, so I tried it, but it would get memory corruption error in "trie_new" method in trie.c. I think it's because that you changed alpha map data structure in v2.10.0

Here below contains related source file methods and core dump backtrace:

  1. datrie_filter.c
      Trie *trie;
      AlphaMap *alpha_map;
      int ret;
      alpha_map = alpha_map_new();
      if (! alpha_map) {
      if (alpha_map_add_range(alpha_map, 0x00, 0xff) != 0) {
          /* treat all strings as byte stream */
      trie = trie_new(alpha_map); /** line 252*/           
      if (! trie) {
      RETURN_RES(zend_register_resource(trie, le_datrie_filter));
  1. trie.c
Trie *
 trie_new (const AlphaMap *alpha_map)
     Trie *trie;
     trie = (Trie *) malloc (sizeof (Trie));  /** line 120 */
     if (UNLIKELY (!trie))
         return NULL;
     trie->alpha_map = alpha_map_clone (alpha_map);
     if (UNLIKELY (!trie->alpha_map))
         goto exit_trie_created;
     trie->da = da_new ();
     if (UNLIKELY (!trie->da))
         goto exit_alpha_map_created;
     trie->tail = tail_new ();
     if (UNLIKELY (!trie->tail))
         goto exit_da_created;
     trie->is_dirty = TRUE;
     return trie;
     da_free (trie->da);
     alpha_map_free (trie->alpha_map);
     free (trie);
     return NULL;
  1. core dump backtrace
Core was generated by `php test.php'.
Program terminated with signal SIGABRT, Aborted.
#0  0xb76e6cf9 in __kernel_vsyscall ()
(gdb) bt
#0  0xb76e6cf9 in __kernel_vsyscall ()
#1  0xb6ff7050 in __libc_signal_restore_set (set=0xbfb7e890) at ../sysdeps/unix/sysv/linux/nptl-signals.h:79
#2  __GI_raise (sig=6) at ../sysdeps/unix/sysv/linux/raise.c:55
#3  0xb6ff8577 in __GI_abort () at abort.c:89
#4  0xb7032f4f in __libc_message (do_abort=<optimized out>, fmt=<optimized out>)
    at ../sysdeps/posix/libc_fatal.c:175
#5  0xb7039b47 in malloc_printerr (action=<optimized out>, str=0xb712b7fa "malloc(): memory corruption",
    ptr=<optimized out>, ar_ptr=0xb7181780 <main_arena>) at malloc.c:5046
#6  0xb703bb22 in _int_malloc (av=av@entry=0xb7181780 <main_arena>, bytes=bytes@entry=16) at malloc.c:3509
#7  0xb703d735 in __GI___libc_malloc (bytes=16) at malloc.c:2925
#8  0xb76d5257 in trie_new (alpha_map=0x8174b738) at trie.c:120
#9  0xb76dd561 in zif_datrie_filter_new (execute_data=0xb5013290, return_value=0xb50130d0)
    at /home/xiao/Documents/datrie_filter/datrie_filter.c:252
#10 0x802639e4 in ?? ()
#11 0x80253e1a in execute_ex ()
#12 0x802abeae in zend_execute ()
#13 0x8021361d in zend_execute_scripts ()
#14 0x801b0784 in php_execute_script ()
#15 0x802add1d in ?? ()
#16 0x80086fc4 in main ()

This comment has been minimized.

Copy link

nevermatch commented Apr 9, 2018

found one overflow bug

  for (range = alpha_map->first_range; range; range = range->next) {
        for (a = range->begin; a <= range->end; a++) {
            alpha_map->alpha_to_trie_map[a - alpha_begin] = ++trie_last;

  // trie_last can overflow , from 255 to zero.
 // trie_last can overflow , from 255 to zero.

    alpha_map->trie_map_sz =  trie_last + 1;
        = (AlphaChar *) malloc (alpha_map->trie_map_sz * sizeof (AlphaChar));

    // at this time ,trie_to_alpha_map malloc size is 1
     for (range = alpha_map->first_range; range; range = range->next) {
        for (a = range->begin; a <= range->end; a++) {
            alpha_map->trie_to_alpha_map[tc++] = a;
            // range->end can be 255
            // trie_to_alpha_map array across the border

This comment has been minimized.

Copy link

nevermatch commented Apr 11, 2018

v2.9.0 works
v2.10.0 core dump.

"Optimize AlphaMap mapping" commit has one overflow bug.
trie_last can be overflow.

alpha_map_char_to_trie() is called everywhere before trie state
transition. It's an important bottleneck.

We won't change the persistent AlphaMap structure, but will add
pre-calculated lookup tables for use at run-time.


This comment has been minimized.

Copy link

thep commented Apr 21, 2018

Although I cannot reproduce it with a C test case (it survives segfault somehow), I can detect the behavior as @nevermatch described. Indeed, trie_last should be of type TrieIndex, not TrieChar. Changing as such can eliminate the behavior. I'll fix it soon.

@thep thep closed this in 3646819 Apr 21, 2018

@thep thep referenced this issue Nov 23, 2018


possible bug #9

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment