Repository: numba/numba
Pull request: Fix segfault caused by pop from numba.typed.List
Fixes #5264

<!--

Thanks for wanting to contribute to Numba :)

First, if you need some help or want to chat to the core developers, please
visit https://gitter.im/numba/numba for real time chat or post to the Numba
mailing list https://groups.google.com/a/continuum.io/forum/#!forum/numba-users.

Here's some guidelines to help the review process go smoothly.

0. Please write a description in this text box of the changes that are being
   made.

1. Please ensure that you have written units tests for the changes made/features
   added.

2. If you are closing an issue please use one of the automatic closing words as
   noted here: https://help.github.com/articles/closing-issues-using-keywords/

3. If your pull request is not ready for review but you want to make use of the
   continuous integration testing facilities please label it with `[WIP]` and
   then remove the label when you'd like it to be reviewed.

4. Once review has taken place please do not add features or make changes out of
   the scope of those requested by the reviewer (doing this just add delays as
   already reviewed code ends up having to be re-reviewed/it is hard to tell
   what is new etc!). Further, please do not rebase your branch on master/force
   push/rewrite history, doing any of these causes the context of any comments
   made by reviewers to be lost. If conflicts occur against master they should
   be resolved by merging master into the branch used for making the pull
   request.

Many thanks in advance for your cooperation!

-->

Problem statement:
Heap corruption of Lists of numpy arrays
Lists of numpy arrays (at least of float 1D type) cannot be brought to length zero without heap corruption. Best guess at this point: refcount issue and double free of allocated memory.

Also, Lists of numpy scalars for some reason do not suffer this issue.

Minimal reproducer:

```python
import numpy as np
from numba import  float64
from numba.typed import List

float_array = float64[:]

l = List.empty_list(float_array)
l.append(np.ones(3,dtype=np.float64))
l.pop()
````

Hints from issue discussion:
@Viissataa thanks for reporting this on the Numba issue tracker. I have reproduced this locally and can confirm, that it is likely a bug.
After a bit of debugging, this is likely a refcounting issue, essentially a double free is the root cause of the SIGSEGV.
@Viissataa sorry for the delay on this one, I just got around to looking at it. I changed the reproducer slightly, so as to assign the incoming array to a variable. I then no longer receive the segfault. I was wondering if you could try the example and see if you see the same?

```python
import numpy as np
from numba import float64
from numba.typed import List

float_array = float64[:]

l = List.empty_list(float_array)
z = np.ones(3,dtype=np.float64)
l.append(z)
l.pop()
print(repr(l))
```
I still get segfault
![2020-04-20 17 43 07](https://user-images.githubusercontent.com/7416056/79764886-9df47780-832e-11ea-9c9e-4e8a221ab88c.jpg)

My numba version is 0.46.0 as per pip.
Possible fix in #5602 - @Viissataa would you have a chance to try that fix?

Commit message: use delitem instead of pop

Both `remove` and `clear` need to delete items somehow, so instead of
using pop, we use `delitem`directly. While being conceptually clearer it
may have some benefits to performance also (assumption).

Patch to review:
diff --git a/numba/_helpermod.c b/numba/_helpermod.c
index d8ee632e2ac..e8640c6fb72 100644
--- a/numba/_helpermod.c
+++ b/numba/_helpermod.c
@@ -156,7 +156,7 @@ build_c_helpers_dict(void)
     declmethod(list_setitem);
     declmethod(list_getitem);
     declmethod(list_append);
-    declmethod(list_pop);
+    declmethod(list_delitem);
     declmethod(list_delete_slice);
     declmethod(list_iter_sizeof);
     declmethod(list_iter);
diff --git a/numba/cext/listobject.c b/numba/cext/listobject.c
index 6cbfcf62c86..6072b029df9 100644
--- a/numba/cext/listobject.c
+++ b/numba/cext/listobject.c
@@ -32,8 +32,8 @@
  * - Appending to the list    numba_list_append
  * - Getting an item          numba_list_setitem
  * - Setting an item          numba_list_getitem
- * - Poping an item           numba_list_pop
  * - Resizing the list        numba_list_resize
+ * - Deleting an item         numba_list_delitem
  * - Deleting a slice         numba_list_delete_slice
  *
  * As you can see, only a single function for slices is implemented. The rest
@@ -329,48 +329,6 @@ numba_list_append(NB_List *lp, const char *item) {
     return LIST_OK;
 }
 
-/* Pop (get and delete) an item from a list at a given location.
- *
- * lp: a list
- * index: the index of the item to pop
- * out: a pointer to hold the item
- */
-int
-numba_list_pop(NB_List *lp, Py_ssize_t index, char *out) {
-    char *loc, *new_loc;
-    int result;
-    // check for mutability
-    if (!lp->is_mutable) {
-        return LIST_ERR_IMMUTABLE;
-    }
-    Py_ssize_t leftover_bytes;
-    // check index is valid
-    // FIXME: this can be (and probably is) checked at the compiler level
-    if (!valid_index(index, lp->size)) {
-        return LIST_ERR_INDEX;
-    }
-    // obtain item and decref if needed
-    loc = lp->items + lp->item_size * index;
-    copy_item(lp, out, loc);
-    list_decref_item(lp, loc);
-    if (index != lp->size - 1) {
-        // pop from somewhere other than the end, incur the dreaded memory copy
-        leftover_bytes = (lp->size - 1 - index) * lp->item_size;
-        new_loc = lp->items + (lp->item_size * (index + 1));
-        // use memmove instead of memcpy since we may be dealing with
-        // overlapping regions of memory and the behaviour of memcpy is
-        // undefined in such situation (C99).
-        memmove(loc, new_loc, leftover_bytes);
-    }
-    // finally, shrink list by one
-    result = numba_list_resize(lp, lp->size - 1);
-    if(result < LIST_OK) {
-         // Since we are decreasing the size, this should never happen
-        return result;
-    }
-    return LIST_OK;
-
-}
 /* Resize a list.
  *
  * lp: a list
@@ -441,6 +399,50 @@ numba_list_resize(NB_List *lp, Py_ssize_t newsize) {
     return LIST_OK;
 }
 
+/* Delete a single item.
+ *
+ * lp: a list
+ * index: the index of the item to delete
+ *
+ * */
+int
+numba_list_delitem(NB_List *lp, Py_ssize_t index) {
+    // FIXME the following line is the lazy implementation
+    //result = numba_list_delete_slice(lp, index, index+1, 1);
+    int result;
+    char *loc, *new_loc;
+    Py_ssize_t leftover_bytes;
+    // check for mutability
+    if (!lp->is_mutable) {
+        return LIST_ERR_IMMUTABLE;
+    }
+    // check index is valid
+    // FIXME: this can be (and probably is) checked at the compiler level
+    if (!valid_index(index, lp->size)) {
+        return LIST_ERR_INDEX;
+    }
+    // obtain item and decref if needed
+    loc = lp->items + lp->item_size * index;
+    list_decref_item(lp, loc);
+    if (index != lp->size - 1) {
+        // delitem from somewhere other than the end, incur the dreaded memory copy
+        leftover_bytes = (lp->size - 1 - index) * lp->item_size;
+        new_loc = lp->items + (lp->item_size * (index + 1));
+        // use memmove instead of memcpy since we may be dealing with
+        // overlapping regions of memory and the behaviour of memcpy is
+        // undefined in such situation (C99).
+        memmove(loc, new_loc, leftover_bytes);
+    }
+    // finally, shrink list by one
+    result = numba_list_resize(lp, lp->size - 1);
+    if(result < LIST_OK) {
+         // Since we are decreasing the size, this should never happen
+        return result;
+    }
+    return LIST_OK;
+
+}
+
 /* Delete a slice
  *
  * start: the start index of ths slice
@@ -679,16 +681,18 @@ numba_test_list(void) {
     CHECK(status == LIST_OK);
     CHECK(memcmp(got_item, "pqr", 4) == 0);
 
-    // pop 1st item, check item shift
-    status = numba_list_pop(lp, 0, got_item);
+    // get and del 1st item, check item shift
+    status = numba_list_getitem(lp, 0, got_item);
+    status = numba_list_delitem(lp, 0);
     CHECK(status == LIST_OK);
     CHECK(lp->size == 4);
     CHECK(lp->allocated == 8);
     CHECK(memcmp(got_item, "pqr", 4) == 0);
     CHECK(memcmp(lp->items, "def\x00ghi\x00jkl\x00mno\x00", 16) == 0);
 
-    // pop last (4th) item, no shift since only last item affected
-    status = numba_list_pop(lp, 3, got_item);
+    // get and del last (4th) item, no shift since only last item affected
+    status = numba_list_getitem(lp, 3, got_item);
+    status = numba_list_delitem(lp, 3);
     CHECK(status == LIST_OK);
     CHECK(lp->size == 3);
     CHECK(lp->allocated == 6);  // this also shrinks the allocation
@@ -703,7 +707,7 @@ numba_test_list(void) {
     // ensure that any attempts to mutate an immutable list fail
     CHECK(numba_list_setitem(lp, 0, "zzz") == LIST_ERR_IMMUTABLE);
     CHECK(numba_list_append(lp, "zzz") == LIST_ERR_IMMUTABLE);
-    CHECK(numba_list_pop(lp, 0, got_item) == LIST_ERR_IMMUTABLE);
+    CHECK(numba_list_delitem(lp, 0) == LIST_ERR_IMMUTABLE);
     CHECK(numba_list_resize(lp, 23) == LIST_ERR_IMMUTABLE);
     CHECK(numba_list_delete_slice(lp, 0, 3, 1) == LIST_ERR_IMMUTABLE);
 
@@ -740,7 +744,7 @@ numba_test_list(void) {
     // free existing list
     numba_list_free(lp);
 
-    // test growth upon append and shrink during pop
+    // test growth upon append and shrink during delitem
     status = numba_list_new(&lp, 1, 0);
     CHECK(status == LIST_OK);
     CHECK(lp->item_size == 1);
@@ -774,10 +778,10 @@ numba_test_list(void) {
     test_items_2  = "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10";
     CHECK(memcmp(lp->items, test_items_2, 17) == 0);
 
-    // Now, pop them again and check that list shrinks
+    // Now, delete them again and check that list shrinks
     for (i = 17; i > 0 ; i--) {
         switch(i) {
-             // Check the allocation before pop
+             // Check the allocation before delitem
              case 17:  CHECK(lp->allocated == 25); break;
              case 12:  CHECK(lp->allocated == 25); break;
              case 9:   CHECK(lp->allocated == 18); break;
@@ -787,7 +791,8 @@ numba_test_list(void) {
              case 2:   CHECK(lp->allocated == 5); break;
              case 1:   CHECK(lp->allocated == 4); break;
         }
-        status = numba_list_pop(lp, i-1, got_item);
+        status = numba_list_getitem(lp, i-1, got_item);
+        status = numba_list_delitem(lp, i-1);
         CHECK(status == LIST_OK);
         switch(i) {
              // Check that the shrink happened accordingly
diff --git a/numba/cext/listobject.h b/numba/cext/listobject.h
index 363edf94123..93ef9a5bb68 100644
--- a/numba/cext/listobject.h
+++ b/numba/cext/listobject.h
@@ -103,13 +103,13 @@ numba_list_getitem(NB_List *lp, Py_ssize_t index, char *out);
 NUMBA_EXPORT_FUNC(int)
 numba_list_append(NB_List *lp, const char *item);
 
-NUMBA_EXPORT_FUNC(int)
-numba_list_pop(NB_List *lp, Py_ssize_t index, char *out);
-
 // FIXME: should this be public?
 NUMBA_EXPORT_FUNC(int)
 numba_list_resize(NB_List *lp, Py_ssize_t newsize);
 
+NUMBA_EXPORT_FUNC(int)
+numba_list_delitem(NB_List *lp, Py_ssize_t index);
+
 NUMBA_EXPORT_FUNC(int)
 numba_list_delete_slice(NB_List *lp,
                         Py_ssize_t start, Py_ssize_t stop, Py_ssize_t step);
diff --git a/numba/tests/test_listimpl.py b/numba/tests/test_listimpl.py
index f47f2be6385..f55e2369a42 100644
--- a/numba/tests/test_listimpl.py
+++ b/numba/tests/test_listimpl.py
@@ -55,6 +55,15 @@ def __iter__(self):
     def __delitem__(self, i):
         self.list_delitem(i)
 
+    def handle_index(self, i):
+        # handling negative indices is done at the compiler level, so we only
+        # support -1 to be last element of the list here
+        if i < -1 or len(self) == 0:
+            IndexError("list index out of range")
+        elif i == -1:
+            i = len(self) - 1
+        return i
+
     @property
     def allocated(self):
         return self.list_allocated()
@@ -107,6 +116,7 @@ def list_setitem(self, i, item):
             self.tc.assertEqual(status, LIST_OK)
 
     def list_getitem(self, i):
+        i = self.handle_index(i)
         item_out_buffer = ctypes.create_string_buffer(self.item_size)
         status = self.tc.numba_list_getitem(self.lp, i, item_out_buffer)
         if status == LIST_ERR_INDEX:
@@ -122,21 +132,11 @@ def list_append(self, item):
         self.tc.assertEqual(status, LIST_OK)
 
     def list_pop(self, i):
-        # handling negative indices is done at the compiler level, so we only
-        # support -1 to be last element of the list here
-        if i < -1 or len(self) == 0:
-            IndexError("list index out of range")
-        elif i == -1:
-            i = len(self) - 1
-        item_out_buffer = ctypes.create_string_buffer(self.item_size)
-        status = self.tc.numba_list_pop(self.lp, i, item_out_buffer)
-        if status == LIST_ERR_INDEX:
-            raise IndexError("list index out of range")
-        elif status == LIST_ERR_IMMUTABLE:
-            raise ValueError("list is immutable")
-        else:
-            self.tc.assertEqual(status, LIST_OK)
-            return item_out_buffer.raw
+        # pop is getitem and delitem
+        i = self.handle_index(i)
+        item = self.list_getitem(i)
+        self.list_delitem(i)
+        return item
 
     def list_delitem(self, i):
         # special case slice
@@ -148,9 +148,15 @@ def list_delitem(self, i):
             if status == LIST_ERR_IMMUTABLE:
                 raise ValueError("list is immutable")
             self.tc.assertEqual(status, LIST_OK)
-        # must be an integer, defer to pop
+        # must be an integer, defer to delitem
         else:
-            self.list_pop(i)
+            i = self.handle_index(i)
+            status = self.tc.numba_list_delitem(self.lp, i)
+            if status == LIST_ERR_INDEX:
+                raise IndexError("list index out of range")
+            elif status == LIST_ERR_IMMUTABLE:
+                raise ValueError("list is immutable")
+            self.tc.assertEqual(status, LIST_OK)
 
     def list_iter(self, itptr):
         self.tc.numba_list_iter(itptr, self.lp)
@@ -260,11 +266,11 @@ def wrap(name, restype, argtypes=()):
             ctypes.c_int,
             [list_t, ctypes.c_ssize_t, ctypes.c_char_p],
         )
-        # numba_list_pop(NB_List *l,  Py_ssize_t i, char *out)
-        self.numba_list_pop = wrap(
-            'list_pop',
+        # numba_list_delitem(NB_List *l,  Py_ssize_t i)
+        self.numba_list_delitem = wrap(
+            'list_delitem',
             ctypes.c_int,
-            [list_t, ctypes.c_ssize_t, ctypes.c_char_p],
+            [list_t, ctypes.c_ssize_t],
         )
         # numba_list_delete_slice(NB_List *l,
         #                         Py_ssize_t start,
@@ -410,6 +416,26 @@ def test_pop_byte(self):
         received = [j for j in l]
         self.assertEqual(received, expected)
 
+    def test_delitem(self):
+        l = List(self, 1, 0)
+        values = [b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h']
+        for i in values:
+            l.append(i)
+        self.assertEqual(len(l), 8)
+
+        # delete first item
+        del l[0]
+        self.assertEqual(len(l), 7)
+        self.assertEqual(list(l), values[1:])
+        # delete last item
+        del l[-1]
+        self.assertEqual(len(l), 6)
+        self.assertEqual(list(l), values[1:-1])
+        # delete item from middle
+        del l[2]
+        self.assertEqual(len(l), 5)
+        self.assertEqual(list(l), [b'b', b'c', b'e', b'f', b'g'])
+
     def test_delete_slice(self):
         l = List(self, 1, 0)
         values = [b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h']
diff --git a/numba/tests/test_typedlist.py b/numba/tests/test_typedlist.py
index 72f17fb5a98..74cbc53d801 100644
--- a/numba/tests/test_typedlist.py
+++ b/numba/tests/test_typedlist.py
@@ -619,6 +619,7 @@ def bar():
             return njit(context["bar"])
         for line1, line2 in (
                 ("lst.append(None)", "lst.pop()"),
+                ("lst.append(None)", "del lst[0]"),
                 ("lst.append(None)", "lst.count(None)"),
                 ("lst.append(None)", "lst.index(None)"),
                 ("lst.append(None)", "lst.insert(0, None)"),
@@ -1014,6 +1015,20 @@ def foo():
         # Need to compare the nested arrays
         self.assertTrue(np.all(expected[0] == got[0]))
 
+    def test_array_pop_from_single_value_list(self):
+        @njit
+        def foo():
+            l = List((np.zeros((1,)),))
+            l.pop()
+            return l
+
+        expected, got = foo.py_func(), foo()
+        # Need to compare the nested arrays
+        self.assertEqual(len(expected), 0)
+        self.assertEqual(len(got), 0)
+        # FIXME comparison of empty array-typed lists fails
+        # self.assertEqual(expected, got)
+
     def test_jitclass_as_item_in_list(self):
 
         spec = [
diff --git a/numba/typed/listobject.py b/numba/typed/listobject.py
index 83f7556c082..6a85024fd68 100644
--- a/numba/typed/listobject.py
+++ b/numba/typed/listobject.py
@@ -661,24 +661,11 @@ def handle_slice(l, s):
 
 @intrinsic
 def _list_getitem(typingctx, l, index):
-    return _list_getitem_pop_helper(typingctx, l, index, 'getitem')
-
-
-@intrinsic
-def _list_pop(typingctx, l, index):
-    return _list_getitem_pop_helper(typingctx, l, index, 'pop')
-
-
-def _list_getitem_pop_helper(typingctx, l, index, op):
-    """Wrap numba_list_getitem and numba_list_pop
+    """Wrap numba_list_getitem
 
     Returns 2-tuple of (int32, ?item_type)
 
-    This is a helper that is parametrized on the type of operation, which can
-    be either 'pop' or 'getitem'. This is because, signature wise, getitem and
-    pop and are the same.
     """
-    assert(op in ("pop", "getitem"))
     IS_NOT_NONE = not isinstance(l.item_type, types.NoneType)
     resty = types.Tuple([types.int32,
                          types.Optional(l.item_type
@@ -694,7 +681,7 @@ def codegen(context, builder, sig, args):
         [tl, tindex] = sig.args
         [l, index] = args
         fn = builder.module.get_or_insert_function(
-            fnty, name='numba_list_{}'.format(op))
+            fnty, name='numba_list_getitem')
 
         dm_item = context.data_model_manager[tl.item_type]
         ll_item = context.get_data_type(tl.item_type)
@@ -900,21 +887,38 @@ def impl_pop(l, index=-1):
         def impl(l, index=-1):
             if len(l) == 0:
                 raise IndexError("pop from empty list")
-            index = handle_index(l, index)
-            castedindex = _cast(index, indexty)
-            status, item = _list_pop(l, castedindex)
-            if status == ListStatus.LIST_OK:
-                return _nonoptional(item)
-            elif status == ListStatus.LIST_ERR_IMMUTABLE:
-                raise ValueError("list is immutable")
-            else:
-                raise AssertionError("internal list error during pop")
+            cindex = _cast(handle_index(l, index), indexty)
+            item = l[cindex]
+            del l[cindex]
+            return item
         return impl
 
     else:
         raise TypingError("argument for pop must be an integer")
 
 
+@intrinsic
+def _list_delitem(typingctx, l, index):
+    resty = types.int32
+    sig = resty(l, index)
+
+    def codegen(context, builder, sig, args):
+        fnty = ir.FunctionType(
+            ll_status,
+            [ll_list_type, ll_ssize_t],
+        )
+        [tl, tindex] = sig.args
+        [l, index] = args
+        fn = builder.module.get_or_insert_function(
+            fnty, name='numba_list_delitem')
+
+        lp = _container_get_data(context, builder, tl, l)
+        status = builder.call(fn, [lp, index])
+        return status
+
+    return sig, codegen
+
+
 @intrinsic
 def _list_delete_slice(typingctx, l, start, stop, step):
     """Wrap numba_list_delete_slice
@@ -952,10 +956,18 @@ def impl_delitem(l, index):
     if not isinstance(l, types.ListType):
         return
 
+    _check_for_none_typed(l, 'delitem')
+
     if index in index_types:
         def integer_impl(l, index):
-            l.pop(index)
-
+            cindex = _cast(handle_index(l, index), INDEXTY)
+            status = _list_delitem(l, cindex)
+            if status == ListStatus.LIST_OK:
+                return
+            elif status == ListStatus.LIST_ERR_IMMUTABLE:
+                raise ValueError("list is immutable")
+            else:
+                raise AssertionError("internal list error during delitem")
         return integer_impl
 
     elif isinstance(index, types.SliceType):
@@ -1123,7 +1135,7 @@ def impl(l, item):
         casteditem = _cast(item, itemty)
         for i, n in enumerate(l):
             if casteditem == n:
-                l.pop(i)
+                del l[i]
                 return
         else:
             raise ValueError("list.remove(x): x not in list")
@@ -1138,7 +1150,7 @@ def impl_clear(l):
 
     def impl(l):
         while len(l):
-            l.pop()
+            del l[-1]
 
     return impl
 


Code review comments:
diff_hunk: @@ -441,6 +399,50 @@ numba_list_resize(NB_List *lp, Py_ssize_t newsize) {
     return LIST_OK;
 }
 
+/* Delete a single item.
+ *
+ * lp: a list
+ * index: the index of the item to delete
+ *
+ * */
+int
+numba_list_delitem(NB_List *lp, Py_ssize_t index) {
+    // FIXME the following line is the lazy implementation
+    //result = numba_list_delete_slice(lp, index, index+1, 1);
path: numba/cext/listobject.c
text: @user1:
Remove?

@author:
done