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

[truebit]

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

  PHP_FUNCTION(datrie_filter_new)
  {
      Trie *trie;
      AlphaMap *alpha_map;
      int ret;
 
      alpha_map = alpha_map_new();
      if (! alpha_map) {
          RETURN_NULL();
      }
 
      if (alpha_map_add_range(alpha_map, 0x00, 0xff) != 0) {
          /* treat all strings as byte stream */
          alpha_map_free(alpha_map);
          RETURN_NULL();
      }
 
      trie = trie_new(alpha_map); /** line 252*/           
      alpha_map_free(alpha_map);
      if (! trie) {
          RETURN_NULL();
      }
      RETURN_RES(zend_register_resource(trie, le_datrie_filter));
  }

2. 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;
 
 exit_da_created:
     da_free (trie->da);
 exit_alpha_map_created:
     alpha_map_free (trie->alpha_map);
 exit_trie_created:
     free (trie);
     return NULL;
 }

3. 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 ()

[nevermatch]

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;
    alpha_map->trie_to_alpha_map
        = (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
        }
    }

[nevermatch]

v2.9.0 works
v2.10.0 core dump.

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

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.

[thep]

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.