On Sunday, June 22, 2014 at 3:29:32 PM UTC-5, Ben Fritz wrote: > The attached patch seems to fix the crash reported here: > > https://groups.google.com/d/topic/vim_dev/Nr8Ja4Zjghw/discussion > > The fix is simple in concept: any recursive call can be replaced with > an explicit stack to "cheat" your way into an iterative algorithm.
Updated patch attached. The updates allow aborting if the LUA set_ref fails, and also shows a message if aborting when 'verbose' is greater than zero. I also updated the test file. I *think* this tests the LUA and Python garbage collection. I grabbed the code snippet from Issue 267 (https://code.google.com/p/vim/issues/detail?id=267) to also test that issue. Vim doesn't crash with the patch on that code; but I can't get it to crash without my patch, either. I think the patch is ready now, unless you need another Valgrind run with the updates. I did test again in Windows to make sure task manager doesn't show an obvious increase in memory on iterations of the test. -- -- You received this message from the "vim_dev" maillist. Do not top-post! Type your reply below the text you are replying to. For more information, visit http://www.vim.org/maillist.php --- You received this message because you are subscribed to the Google Groups "vim_dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to vim_dev+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
# HG changeset patch
# User Ben Fritz <fritzophre...@gmail.com>
# Date 1421902422 21600
# Wed Jan 21 22:53:42 2015 -0600
# Branch 2html-dev
# Node ID 3ea803d34387dec1e371d97ff6429a15dfe760e0
# Parent c7a769401fdb72b9a79f37048771f3000eda48e5
Make setref for garbage collect iterative using explicit stack
fixes crash when freeing deeply recursive data structures
diff -r c7a769401fdb -r 3ea803d34387 src/eval.c
--- a/src/eval.c Wed Jan 21 22:26:30 2015 -0600
+++ b/src/eval.c Wed Jan 21 22:53:42 2015 -0600
@@ -93,7 +93,6 @@
char_u *ll_newkey; /* New key for Dict in alloc. mem or NULL. */
} lval_T;
-
static char *e_letunexp = N_("E18: Unexpected characters in :let");
static char *e_listidx = N_("E684: list index out of range: %ld");
static char *e_undefvar = N_("E121: Undefined variable: %s");
@@ -6810,6 +6809,7 @@
garbage_collect()
{
int copyID;
+ int abort = 0;
buf_T *buf;
win_T *wp;
int i;
@@ -6840,82 +6840,89 @@
* the item is referenced elsewhere the funccal must not be freed. */
for (fc = previous_funccal; fc != NULL; fc = fc->caller)
{
- set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID + 1);
- set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID + 1);
+ abort = abort || set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID + 1, NULL);
+ abort = abort || set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID + 1, NULL);
}
/* script-local variables */
for (i = 1; i <= ga_scripts.ga_len; ++i)
- set_ref_in_ht(&SCRIPT_VARS(i), copyID);
+ abort = abort || set_ref_in_ht(&SCRIPT_VARS(i), copyID, NULL);
/* buffer-local variables */
for (buf = firstbuf; buf != NULL; buf = buf->b_next)
- set_ref_in_item(&buf->b_bufvar.di_tv, copyID);
+ abort = abort || set_ref_in_item(&buf->b_bufvar.di_tv, copyID, NULL, NULL);
/* window-local variables */
FOR_ALL_TAB_WINDOWS(tp, wp)
- set_ref_in_item(&wp->w_winvar.di_tv, copyID);
+ abort = abort || set_ref_in_item(&wp->w_winvar.di_tv, copyID, NULL, NULL);
#ifdef FEAT_AUTOCMD
if (aucmd_win != NULL)
- set_ref_in_item(&aucmd_win->w_winvar.di_tv, copyID);
+ abort = abort || set_ref_in_item(&aucmd_win->w_winvar.di_tv, copyID, NULL, NULL);
#endif
#ifdef FEAT_WINDOWS
/* tabpage-local variables */
for (tp = first_tabpage; tp != NULL; tp = tp->tp_next)
- set_ref_in_item(&tp->tp_winvar.di_tv, copyID);
+ abort = abort || set_ref_in_item(&tp->tp_winvar.di_tv, copyID, NULL, NULL);
#endif
/* global variables */
- set_ref_in_ht(&globvarht, copyID);
+ abort = abort || set_ref_in_ht(&globvarht, copyID, NULL);
/* function-local variables */
for (fc = current_funccal; fc != NULL; fc = fc->caller)
{
- set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID);
- set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID);
+ abort = abort || set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID, NULL);
+ abort = abort || set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID, NULL);
}
/* v: vars */
- set_ref_in_ht(&vimvarht, copyID);
+ abort = abort || set_ref_in_ht(&vimvarht, copyID, NULL);
#ifdef FEAT_LUA
- set_ref_in_lua(copyID);
+ abort = abort || set_ref_in_lua(copyID);
#endif
#ifdef FEAT_PYTHON
- set_ref_in_python(copyID);
+ abort = abort || set_ref_in_python(copyID);
#endif
#ifdef FEAT_PYTHON3
- set_ref_in_python3(copyID);
-#endif
-
- /*
- * 2. Free lists and dictionaries that are not referenced.
- */
- did_free = free_unref_items(copyID);
-
- /*
- * 3. Check if any funccal can be freed now.
- */
- for (pfc = &previous_funccal; *pfc != NULL; )
- {
- if (can_free_funccal(*pfc, copyID))
- {
- fc = *pfc;
- *pfc = fc->caller;
- free_funccal(fc, TRUE);
- did_free = TRUE;
- did_free_funccal = TRUE;
- }
- else
- pfc = &(*pfc)->caller;
- }
- if (did_free_funccal)
- /* When a funccal was freed some more items might be garbage
- * collected, so run again. */
- (void)garbage_collect();
+ abort = abort || set_ref_in_python3(copyID);
+#endif
+
+ if (!abort)
+ {
+ /*
+ * 2. Free lists and dictionaries that are not referenced.
+ */
+ did_free = free_unref_items(copyID);
+
+ /*
+ * 3. Check if any funccal can be freed now.
+ */
+ for (pfc = &previous_funccal; *pfc != NULL; )
+ {
+ if (can_free_funccal(*pfc, copyID))
+ {
+ fc = *pfc;
+ *pfc = fc->caller;
+ free_funccal(fc, TRUE);
+ did_free = TRUE;
+ did_free_funccal = TRUE;
+ }
+ else
+ pfc = &(*pfc)->caller;
+ }
+ if (did_free_funccal)
+ /* When a funccal was freed some more items might be garbage
+ * collected, so run again. */
+ (void)garbage_collect();
+ }
+ else if (p_verbose > 0)
+ {
+ verb_msg((char_u *)_("Garbage collection aborted! Not enough memory to set references!"));
+ }
return did_free;
}
@@ -6975,48 +6982,113 @@
/*
* Mark all lists and dicts referenced through hashtab "ht" with "copyID".
- */
- void
-set_ref_in_ht(ht, copyID)
- hashtab_T *ht;
- int copyID;
+ *
+ * Returns 0 if successful, 1 if setting references failed somehow.
+ */
+ int
+set_ref_in_ht(ht, copyID, list_stack)
+ hashtab_T *ht;
+ int copyID;
+ list_stack_T **list_stack;
{
int todo;
+ int abort = 0;
hashitem_T *hi;
-
- todo = (int)ht->ht_used;
- for (hi = ht->ht_array; todo > 0; ++hi)
- if (!HASHITEM_EMPTY(hi))
- {
- --todo;
- set_ref_in_item(&HI2DI(hi)->di_tv, copyID);
- }
+ hashtab_T *cur_ht = ht;
+ ht_stack_T *ht_stack = NULL;
+ ht_stack_T *tempitem;
+
+ ht_stack = (ht_stack_T*)malloc(sizeof(ht_stack_T));
+ if (ht_stack)
+ {
+ ht_stack->ht = ht;
+ ht_stack->prev = NULL;
+ }
+ else
+ {
+ abort = 1;
+ }
+
+ while (ht_stack)
+ {
+ cur_ht = ht_stack->ht;
+ tempitem = ht_stack;
+ ht_stack = ht_stack->prev;
+ free(tempitem);
+
+ if (!abort)
+ {
+ todo = (int)cur_ht->ht_used;
+ for (hi = cur_ht->ht_array; todo > 0; ++hi)
+ if (!HASHITEM_EMPTY(hi))
+ {
+ --todo;
+ abort = set_ref_in_item(&HI2DI(hi)->di_tv, copyID, &ht_stack, list_stack);
+ }
+ }
+ }
+
+ return abort;
}
/*
* Mark all lists and dicts referenced through list "l" with "copyID".
- */
- void
-set_ref_in_list(l, copyID)
+ *
+ * Returns 0 if successful, 1 if setting references failed somehow.
+ */
+ int
+set_ref_in_list(l, copyID, ht_stack)
list_T *l;
int copyID;
-{
- listitem_T *li;
-
- for (li = l->lv_first; li != NULL; li = li->li_next)
- set_ref_in_item(&li->li_tv, copyID);
+ ht_stack_T **ht_stack;
+{
+ listitem_T *li;
+ int abort = 0;
+
+ list_T *cur_l;
+ list_stack_T *list_stack = NULL;
+ list_stack_T *tempitem;
+
+ list_stack = (list_stack_T*)malloc(sizeof(list_stack_T));
+ if (list_stack)
+ {
+ list_stack->list = l;
+ list_stack->prev = NULL;
+ }
+ else
+ {
+ abort = 1;
+ }
+
+ while (list_stack)
+ {
+ cur_l = list_stack->list;
+ tempitem = list_stack;
+ list_stack = list_stack->prev;
+ free(tempitem);
+
+ for (li = cur_l->lv_first; !abort && li != NULL; li = li->li_next)
+ abort = set_ref_in_item(&li->li_tv, copyID, ht_stack, &list_stack);
+ }
+
+ return abort;
}
/*
* Mark all lists and dicts referenced through typval "tv" with "copyID".
- */
- void
-set_ref_in_item(tv, copyID)
- typval_T *tv;
- int copyID;
+ *
+ * Returns 0 if successful, 1 if setting references failed somehow.
+ */
+ int
+set_ref_in_item(tv, copyID, ht_stack, list_stack)
+ typval_T *tv;
+ int copyID;
+ ht_stack_T **ht_stack;
+ list_stack_T **list_stack;
{
dict_T *dd;
list_T *ll;
+ int abort = 0;
switch (tv->v_type)
{
@@ -7026,7 +7098,24 @@
{
/* Didn't see this dict yet. */
dd->dv_copyID = copyID;
- set_ref_in_ht(&dd->dv_hashtab, copyID);
+ if (NULL == ht_stack)
+ {
+ abort = set_ref_in_ht(&dd->dv_hashtab, copyID, list_stack);
+ }
+ else
+ {
+ ht_stack_T *newitem = (ht_stack_T*)malloc(sizeof(ht_stack_T));
+ if (newitem)
+ {
+ newitem->ht = &dd->dv_hashtab;
+ newitem->prev = *ht_stack;
+ *ht_stack = newitem;
+ }
+ else
+ {
+ abort = 1;
+ }
+ }
}
break;
@@ -7036,11 +7125,28 @@
{
/* Didn't see this list yet. */
ll->lv_copyID = copyID;
- set_ref_in_list(ll, copyID);
- }
- break;
- }
- return;
+ if (NULL == list_stack)
+ {
+ abort = set_ref_in_list(ll, copyID, ht_stack);
+ }
+ else
+ {
+ list_stack_T *newitem = (list_stack_T*)malloc(sizeof(list_stack_T));
+ if (newitem)
+ {
+ newitem->list = ll;
+ newitem->prev = *list_stack;
+ *list_stack = newitem;
+ }
+ else
+ {
+ abort = 1;
+ }
+ }
+ }
+ break;
+ }
+ return abort;
}
/*
diff -r c7a769401fdb -r 3ea803d34387 src/if_lua.c
--- a/src/if_lua.c Wed Jan 21 22:26:30 2015 -0600
+++ b/src/if_lua.c Wed Jan 21 22:53:42 2015 -0600
@@ -1524,11 +1524,12 @@
luaV_setref (lua_State *L)
{
int copyID = lua_tointeger(L, 1);
+ int abort = 0;
typval_T tv;
luaV_getfield(L, LUAVIM_LIST);
luaV_getfield(L, LUAVIM_DICT);
lua_pushnil(L);
- while (lua_next(L, lua_upvalueindex(1)) != 0) /* traverse cache table */
+ while (!abort && lua_next(L, lua_upvalueindex(1)) != 0) /* traverse cache table */
{
lua_getmetatable(L, -1);
if (lua_rawequal(L, -1, 2)) /* list? */
@@ -1542,9 +1543,9 @@
tv.vval.v_dict = (dict_T *) lua_touserdata(L, 4); /* key */
}
lua_pop(L, 2); /* metatable and value */
- set_ref_in_item(&tv, copyID);
+ abort = set_ref_in_item(&tv, copyID, NULL, NULL);
}
- return 0;
+ lua_pushinteger(L, abort);
}
static int
@@ -1770,13 +1771,22 @@
lua_call(L, 3, 0);
}
- void
+ int
set_ref_in_lua (int copyID)
{
- if (!lua_isopen()) return;
- luaV_getfield(L, LUAVIM_SETREF);
- lua_pushinteger(L, copyID);
- lua_call(L, 1, 0);
+ int aborted = 0;
+ if (lua_isopen())
+ {
+ luaV_getfield(L, LUAVIM_SETREF);
+ /* call the function with 1 arg, getting 1 result back */
+ lua_pushinteger(L, copyID);
+ lua_call(L, 1, 1);
+ /* get the result */
+ aborted = lua_tointeger(L, -1);
+ /* pop result off the stack */
+ lua_pop(L, 1);
+ }
+ return aborted;
}
#endif
diff -r c7a769401fdb -r 3ea803d34387 src/if_py_both.h
--- a/src/if_py_both.h Wed Jan 21 22:26:30 2015 -0600
+++ b/src/if_py_both.h Wed Jan 21 22:53:42 2015 -0600
@@ -5497,34 +5497,41 @@
PyErr_Clear();
}
- static void
+ static int
set_ref_in_py(const int copyID)
{
pylinkedlist_T *cur;
dict_T *dd;
list_T *ll;
+ int abort = 0;
if (lastdict != NULL)
- for(cur = lastdict ; cur != NULL ; cur = cur->pll_prev)
+ {
+ for(cur = lastdict ; !abort && cur != NULL ; cur = cur->pll_prev)
{
dd = ((DictionaryObject *) (cur->pll_obj))->dict;
if (dd->dv_copyID != copyID)
{
dd->dv_copyID = copyID;
- set_ref_in_ht(&dd->dv_hashtab, copyID);
+ abort = set_ref_in_ht(&dd->dv_hashtab, copyID, NULL);
}
}
+ }
if (lastlist != NULL)
- for(cur = lastlist ; cur != NULL ; cur = cur->pll_prev)
+ {
+ for(cur = lastlist ; !abort && cur != NULL ; cur = cur->pll_prev)
{
ll = ((ListObject *) (cur->pll_obj))->list;
if (ll->lv_copyID != copyID)
{
ll->lv_copyID = copyID;
- set_ref_in_list(ll, copyID);
+ abort = set_ref_in_list(ll, copyID, NULL);
}
}
+ }
+
+ return abort;
}
static int
diff -r c7a769401fdb -r 3ea803d34387 src/if_python.c
--- a/src/if_python.c Wed Jan 21 22:26:30 2015 -0600
+++ b/src/if_python.c Wed Jan 21 22:53:42 2015 -0600
@@ -1567,8 +1567,8 @@
}
#endif /* Python 1.4 */
- void
+ int
set_ref_in_python (int copyID)
{
- set_ref_in_py(copyID);
+ return set_ref_in_py(copyID);
}
diff -r c7a769401fdb -r 3ea803d34387 src/if_python3.c
--- a/src/if_python3.c Wed Jan 21 22:26:30 2015 -0600
+++ b/src/if_python3.c Wed Jan 21 22:53:42 2015 -0600
@@ -1649,8 +1649,8 @@
}
}
- void
+ int
set_ref_in_python3 (int copyID)
{
- set_ref_in_py(copyID);
+ int set_ref_in_py(copyID);
}
diff -r c7a769401fdb -r 3ea803d34387 src/proto/eval.pro
--- a/src/proto/eval.pro Wed Jan 21 22:26:30 2015 -0600
+++ b/src/proto/eval.pro Wed Jan 21 22:53:42 2015 -0600
@@ -62,9 +62,9 @@
void vimlist_remove __ARGS((list_T *l, listitem_T *item, listitem_T *item2));
void list_insert __ARGS((list_T *l, listitem_T *ni, listitem_T *item));
int garbage_collect __ARGS((void));
-void set_ref_in_ht __ARGS((hashtab_T *ht, int copyID));
-void set_ref_in_list __ARGS((list_T *l, int copyID));
-void set_ref_in_item __ARGS((typval_T *tv, int copyID));
+int set_ref_in_ht __ARGS((hashtab_T *ht, int copyID, list_stack_T **list_stack));
+int set_ref_in_list __ARGS((list_T *l, int copyID, ht_stack_T **ht_stack));
+int set_ref_in_item __ARGS((typval_T *tv, int copyID, ht_stack_T **ht_stack, list_stack_T **list_stack));
dict_T *dict_alloc __ARGS((void));
void dict_unref __ARGS((dict_T *d));
void dict_free __ARGS((dict_T *d, int recurse));
diff -r c7a769401fdb -r 3ea803d34387 src/proto/if_lua.pro
--- a/src/proto/if_lua.pro Wed Jan 21 22:26:30 2015 -0600
+++ b/src/proto/if_lua.pro Wed Jan 21 22:53:42 2015 -0600
@@ -7,5 +7,5 @@
void lua_buffer_free __ARGS((buf_T *buf));
void lua_window_free __ARGS((win_T *win));
void do_luaeval __ARGS((char_u *str, typval_T *arg, typval_T *rettv));
-void set_ref_in_lua __ARGS((int copyID));
+int set_ref_in_lua __ARGS((int copyID));
/* vim: set ft=c : */
diff -r c7a769401fdb -r 3ea803d34387 src/proto/if_python.pro
--- a/src/proto/if_python.pro Wed Jan 21 22:26:30 2015 -0600
+++ b/src/proto/if_python.pro Wed Jan 21 22:53:42 2015 -0600
@@ -9,5 +9,5 @@
void python_window_free __ARGS((win_T *win));
void python_tabpage_free __ARGS((tabpage_T *tab));
void do_pyeval __ARGS((char_u *str, typval_T *rettv));
-void set_ref_in_python __ARGS((int copyID));
+int set_ref_in_python __ARGS((int copyID));
/* vim: set ft=c : */
diff -r c7a769401fdb -r 3ea803d34387 src/proto/if_python3.pro
--- a/src/proto/if_python3.pro Wed Jan 21 22:26:30 2015 -0600
+++ b/src/proto/if_python3.pro Wed Jan 21 22:53:42 2015 -0600
@@ -9,5 +9,5 @@
void python3_window_free __ARGS((win_T *win));
void python3_tabpage_free __ARGS((tabpage_T *tab));
void do_py3eval __ARGS((char_u *str, typval_T *rettv));
-void set_ref_in_python3 __ARGS((int copyID));
+int set_ref_in_python3 __ARGS((int copyID));
/* vim: set ft=c : */
diff -r c7a769401fdb -r 3ea803d34387 src/structs.h
--- a/src/structs.h Wed Jan 21 22:26:30 2015 -0600
+++ b/src/structs.h Wed Jan 21 22:53:42 2015 -0600
@@ -1223,6 +1223,20 @@
dict_T *dv_used_prev; /* previous dict in used dicts list */
};
+/* structure used for explicit stack while garbage collecting hash tables */
+typedef struct ht_stack_S
+{
+ hashtab_T *ht;
+ struct ht_stack_S *prev;
+} ht_stack_T;
+
+/* structure used for explicit stack while garbage collecting lists */
+typedef struct list_stack_S
+{
+ list_T *list;
+ struct list_stack_S *prev;
+} list_stack_T;
+
/* values for b_syn_spell: what to do with toplevel text */
#define SYNSPL_DEFAULT 0 /* spell check if @Spell not defined */
#define SYNSPL_TOP 1 /* spell check toplevel text */
crashtest.vim
Description: Binary data
