[PATCH 0/5] fixes for rare crashes

[PATCH 0/5] fixes for rare crashes

[Luc Van Oostenryck]

This series contains some fixes for crashes I found during
some fuzzy-testing.

Most of the reproducers are not at all valid C code and
the crashes occurs very very rarely (a few tens of
crashes after more or less 150 CPU hours of fuzzing)
but I don't see much reasons why more 'normal' uses
could not trigger the crashes.

Sorry for coming with this so late in the release.

Note: I'm not really sure if these patches should be
      included in the release but patch 1/5 is a bit
      different and should be included while patch 5/5
      is only for those who use test-linearize.


The following changes since commit ec3f72e981792a86a9e002471a06d61ecd5c6675:

  bump sparse's version to 0.5.1-rc4 (2017-07-04 08:24:40 -0700)

are available in the git repository at:

  git://github.com/lucvoo/sparse.git fix-fuzzy-crashes

for you to fetch changes up to 2f59acac476c07c4d32b82fb8e214d0d6b8b05fc:

  avoid crash with sym->bb_target == NULL (2017-07-06 20:59:10 +0200)

----------------------------------------------------------------

Luc Van Oostenryck (5):
  do not corrupt ptrlist while killing unreachable BBs
  avoid crash when ep->active is NULL
  avoid crash in rewrite_branch()
  avoid some crashes in add_dominators()
  avoid crash with sym->bb_target == NULL

 flow.c                            |  7 ++++---
 flow.h                            |  2 +-
 linearize.c                       | 14 ++++++++++----
 memops.c                          |  2 ++
 validation/crash-add-doms.c       | 22 ++++++++++++++++++++++
 validation/crash-bb_target.c      | 10 ++++++++++
 validation/crash-ep-active.c      | 17 +++++++++++++++++
 validation/crash-ptrlist.c        | 23 +++++++++++++++++++++++
 validation/crash-rewrite-branch.c | 24 ++++++++++++++++++++++++
 9 files changed, 113 insertions(+), 8 deletions(-)
 create mode 100644 validation/crash-add-doms.c
 create mode 100644 validation/crash-bb_target.c
 create mode 100644 validation/crash-ep-active.c
 create mode 100644 validation/crash-ptrlist.c
 create mode 100644 validation/crash-rewrite-branch.c

-- 
2.13.0

[PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

In commit (51cfbc90a5 "fix: kill unreachable BBs after killing a child")
kill_unreachable_bbs() was called during simplification in order
to avoid creating fake cycles between phis and issuing bogus
"crazy programmer" warnings.

However, simplification is done via cse.c:clean_up_insns()
which is looping over all BBs while kill_unreachable_bbs()
loops over all BBs *and* can delete some of them which may
corrupt the looping in clean_up_insns().

Fix this, by adding a flag to kill_unreachable_bbs(), telling
if it is safe to delete the BBs or if we can just mark them
as unreachable (set bb->ep to NULL and unlink any parent and/or
chilren), in which case the deletion will be done later.

Note: the reproducer is one with very broken syntax but nothing
      seems to forbid the same situation to happen with a valid
      program.

Fixes: 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                     |  5 +++--
 flow.h                     |  2 +-
 linearize.c                |  6 +++---
 validation/crash-ptrlist.c | 23 +++++++++++++++++++++++
 4 files changed, 30 insertions(+), 6 deletions(-)
 create mode 100644 validation/crash-ptrlist.c

diff --git a/flow.c b/flow.c
index c7161d47e..3974984de 100644
--- a/flow.c
+++ b/flow.c
@@ -825,7 +825,7 @@ void kill_bb(struct basic_block *bb)
 	bb->parents = NULL;
 }
 
-void kill_unreachable_bbs(struct entrypoint *ep)
+void kill_unreachable_bbs(struct entrypoint *ep, int del)
 {
 	struct basic_block *bb;
 	unsigned long generation = ++bb_generation;
@@ -837,7 +837,8 @@ void kill_unreachable_bbs(struct entrypoint *ep)
 		/* Mark it as being dead */
 		kill_bb(bb);
 		bb->ep = NULL;
-		DELETE_CURRENT_PTR(bb);
+		if (del)
+			DELETE_CURRENT_PTR(bb);
 	} END_FOR_EACH_PTR(bb);
 	PACK_PTR_LIST(&ep->bbs);
 
diff --git a/flow.h b/flow.h
index b592ad4d3..094368fcd 100644
--- a/flow.h
+++ b/flow.h
@@ -24,7 +24,7 @@ extern int simplify_instruction(struct instruction *);
 
 extern void kill_bb(struct basic_block *);
 extern void kill_use(pseudo_t *);
-extern void kill_unreachable_bbs(struct entrypoint *ep);
+extern void kill_unreachable_bbs(struct entrypoint *ep, int del);
 
 extern void kill_insn(struct instruction *, int force);
 static inline void kill_instruction(struct instruction *insn)
diff --git a/linearize.c b/linearize.c
index 7313e72d8..c1ad0c2a4 100644
--- a/linearize.c
+++ b/linearize.c
@@ -673,7 +673,7 @@ void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic
 	PACK_PTR_LIST(&bb->children);
 
 	if (repeat_phase & REPEAT_CFG_CLEANUP)
-		kill_unreachable_bbs(bb->ep);
+		kill_unreachable_bbs(bb->ep, 0);
 }
 	
 
@@ -2225,7 +2225,7 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	 * Do trivial flow simplification - branches to
 	 * branches, kill dead basicblocks etc
 	 */
-	kill_unreachable_bbs(ep);
+	kill_unreachable_bbs(ep, 1);
 
 	/*
 	 * Turn symbols into pseudos
@@ -2242,7 +2242,7 @@ repeat:
 		pack_basic_blocks(ep);
 	} while (repeat_phase & REPEAT_CSE);
 
-	kill_unreachable_bbs(ep);
+	kill_unreachable_bbs(ep, 1);
 	vrfy_flow(ep);
 
 	/* Cleanup */
diff --git a/validation/crash-ptrlist.c b/validation/crash-ptrlist.c
new file mode 100644
index 000000000..8e9b5cb5f
--- /dev/null
+++ b/validation/crash-ptrlist.c
@@ -0,0 +1,23 @@
+a;
+char b;
+c() {
+  while () {
+    int *d;
+    while () {
+      char *e = &b;
+      if (a ?: (*d = f || *0) || g) {
+        if
+          ;
+      } else {
+        int h = 0;
+        if (j) {
+          char **i = &e;
+          if (0 ? 0 : 0 ?: (**i = 1 || 0 && 0))             h ?: (*e = i && &h
+
+/*
+ * check-name: crash ptrlist
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.0

[PATCH 2/5] avoid crash when ep->active is NULL

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                  |  3 +++
 validation/crash-ep-active.c | 17 +++++++++++++++++
 2 files changed, 20 insertions(+)
 create mode 100644 validation/crash-ep-active.c

diff --git a/linearize.c b/linearize.c
index c1ad0c2a4..b76e980dc 100644
--- a/linearize.c
+++ b/linearize.c
@@ -827,6 +827,9 @@ pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size)
 	pseudo_t phi = __alloc_pseudo(0);
 	static int nr = 0;
 
+	if (!source)
+		return VOID;
+
 	phi->type = PSEUDO_PHI;
 	phi->nr = ++nr;
 	phi->def = insn;
diff --git a/validation/crash-ep-active.c b/validation/crash-ep-active.c
new file mode 100644
index 000000000..61e17a188
--- /dev/null
+++ b/validation/crash-ep-active.c
@@ -0,0 +1,17 @@
+void a(void)
+{
+	0 (0
+		&&
+			({
+				goto b;
+			});
+	);
+}
+
+/*
+ * check-name: crash ep->active
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.0

[PATCH 3/5] avoid crash in rewrite_branch()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                            |  2 +-
 validation/crash-rewrite-branch.c | 24 ++++++++++++++++++++++++
 2 files changed, 25 insertions(+), 1 deletion(-)
 create mode 100644 validation/crash-rewrite-branch.c

diff --git a/flow.c b/flow.c
index 3974984de..d8198ce8d 100644
--- a/flow.c
+++ b/flow.c
@@ -30,7 +30,7 @@ static int rewrite_branch(struct basic_block *bb,
 	struct basic_block *old,
 	struct basic_block *new)
 {
-	if (*ptr != old || new == old)
+	if (*ptr != old || new == old || !bb->ep)
 		return 0;
 
 	/* We might find new if-conversions or non-dominating CSEs */
diff --git a/validation/crash-rewrite-branch.c b/validation/crash-rewrite-branch.c
new file mode 100644
index 000000000..eb310df1c
--- /dev/null
+++ b/validation/crash-rewrite-branch.c
@@ -0,0 +1,24 @@
+void a(int c, int e)
+{
+	for(;                   b; c ;
+
+	if (()) {
+		unsigned short d = e;
+		if (())
+			while ()
+				;
+		&d;
+	}
+
+	if (()) {
+		int f = &f;
+	}
+}
+
+/*
+ * check-name: crash rewrite_branch
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.0

[PATCH 4/5] avoid some crashes in add_dominators()

[Luc Van Oostenryck]

---
 memops.c                    |  2 ++
 validation/crash-add-doms.c | 22 ++++++++++++++++++++++
 2 files changed, 24 insertions(+)
 create mode 100644 validation/crash-add-doms.c

diff --git a/memops.c b/memops.c
index 5efdd6f2d..aeacdf566 100644
--- a/memops.c
+++ b/memops.c
@@ -29,6 +29,8 @@ static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 
 		FOR_EACH_PTR_REVERSE(parent->insns, one) {
 			int dominance;
+			if (!one->bb)
+				continue;
 			if (one == insn)
 				goto no_dominance;
 			dominance = dominates(pseudo, insn, one, local);
diff --git a/validation/crash-add-doms.c b/validation/crash-add-doms.c
new file mode 100644
index 000000000..54ad93e84
--- /dev/null
+++ b/validation/crash-add-doms.c
@@ -0,0 +1,22 @@
+char a;
+int b;
+void c(void)
+{
+	if (0) {
+		char *d;
+		for (;;)
+			for (;;)
+e:
+				*d *= (a && 0) ^ b && *d;
+	}
+	goto e;
+}
+
+
+/*
+ * check-name: crash add-doms
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.0

[PATCH 5/5] avoid crash with sym->bb_target == NULL

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                  |  5 ++++-
 validation/crash-bb_target.c | 10 ++++++++++
 2 files changed, 14 insertions(+), 1 deletion(-)
 create mode 100644 validation/crash-bb_target.c

diff --git a/linearize.c b/linearize.c
index b76e980dc..d868c4551 100644
--- a/linearize.c
+++ b/linearize.c
@@ -334,6 +334,7 @@ const char *show_instruction(struct instruction *insn)
 		
 	case OP_SETVAL: {
 		struct expression *expr = insn->val;
+		struct symbol *sym;
 		buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
 
 		if (!expr) {
@@ -355,7 +356,9 @@ const char *show_instruction(struct instruction *insn)
 			buf += sprintf(buf, "%s", show_ident(expr->symbol->ident));
 			break;
 		case EXPR_LABEL:
-			buf += sprintf(buf, ".L%u", expr->symbol->bb_target->nr);
+			sym = expr->symbol;
+			if (sym->bb_target)
+				buf += sprintf(buf, ".L%u", sym->bb_target->nr);
 			break;
 		default:
 			buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type);
diff --git a/validation/crash-bb_target.c b/validation/crash-bb_target.c
new file mode 100644
index 000000000..bc5a3d354
--- /dev/null
+++ b/validation/crash-bb_target.c
@@ -0,0 +1,10 @@
+a() {
+  &&b
+
+/*
+ * check-name: crash bb_target
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.0

Re: [PATCH 0/5] fixes for rare crashes

[Christopher Li]

On Thu, Jul 6, 2017 at 12:19 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This series contains some fixes for crashes I found during
> some fuzzy-testing.
>
> Most of the reproducers are not at all valid C code and
> the crashes occurs very very rarely (a few tens of
> crashes after more or less 150 CPU hours of fuzzing)
> but I don't see much reasons why more 'normal' uses
> could not trigger the crashes.
>
> Sorry for coming with this so late in the release.

Let me take a look after my lunch.

I might delay the release a bit if there is a real bug there.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Thu, Jul 6, 2017 at 12:19 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> In commit (51cfbc90a5 "fix: kill unreachable BBs after killing a child")
> kill_unreachable_bbs() was called during simplification in order
> to avoid creating fake cycles between phis and issuing bogus
> "crazy programmer" warnings.
>
> However, simplification is done via cse.c:clean_up_insns()
> which is looping over all BBs while kill_unreachable_bbs()
> loops over all BBs *and* can delete some of them which may
> corrupt the looping in clean_up_insns().
>
> Fix this, by adding a flag to kill_unreachable_bbs(), telling
> if it is safe to delete the BBs or if we can just mark them
> as unreachable (set bb->ep to NULL and unlink any parent and/or
> chilren), in which case the deletion will be done later.
>
> Note: the reproducer is one with very broken syntax but nothing
>       seems to forbid the same situation to happen with a valid
>       program.
>
> Fixes: 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

Thanks for catching it. That is a very serious bug.
The release will be on hold until this bug has been fix.
It is actually more than one of them. I will send out a separate patch
catching this kind of behavior.


When the parent is doing the loop on this, the
lower level  caller remove the list element is very hasty.

> -void kill_unreachable_bbs(struct entrypoint *ep)
> +void kill_unreachable_bbs(struct entrypoint *ep, int del)
>  {
>         struct basic_block *bb;
>         unsigned long generation = ++bb_generation;
> @@ -837,7 +837,8 @@ void kill_unreachable_bbs(struct entrypoint *ep)
>                 /* Mark it as being dead */
>                 kill_bb(bb);
>                 bb->ep = NULL;
> -               DELETE_CURRENT_PTR(bb);
> +               if (del)
> +                       DELETE_CURRENT_PTR(bb);
>         } END_FOR_EACH_PTR(bb);
>         PACK_PTR_LIST(&ep->bbs);
>

Well, it can happen to other ptr list as well. And it did.

For this one, I thing it is simpler just move the kill_unreachable_bbs()
to the outer stage.

Some thing like this, what do you say?
It did pass the validation test you send out on this patch.

From c4ef6086b07cdf1d0d1790a274ba056910b00b44 Mon Sep 17 00:00:00 2001
From: Christopher Li <sparse@chrisli.org>
Date: Thu, 6 Jul 2017 16:25:38 -0700
Subject: [PATCH 1/2] move kill_unreachable_bbs to outer cse stage

---
 cse.c       | 3 +++
 linearize.c | 3 ---
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/cse.c b/cse.c
index 0d3815c..af9863f 100644
--- a/cse.c
+++ b/cse.c
@@ -387,6 +387,9 @@ repeat:
  }
  }

+ if (repeat_phase & REPEAT_CFG_CLEANUP)
+ kill_unreachable_bbs(ep);
+
  if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
  simplify_memops(ep);

diff --git a/linearize.c b/linearize.c
index 7313e72..a367207 100644
--- a/linearize.c
+++ b/linearize.c
@@ -671,9 +671,6 @@ void insert_branch(struct basic_block *bb, struct
instruction *jmp, struct basic
  remove_parent(child, bb);
  } END_FOR_EACH_PTR(child);
  PACK_PTR_LIST(&bb->children);

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Thu, Jul 6, 2017 at 5:40 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> Thanks for catching it. That is a very serious bug.
> The release will be on hold until this bug has been fix.
> It is actually more than one of them. I will send out a separate patch
> catching this kind of behavior.
>

Here is the patch. There is another offender in simplify.c

Chris

From: Christopher Li <sparse@chrisli.org>
Date: Thu, 6 Jul 2017 16:25:38 -0700
Subject: [PATCH 2/2] check on delete list entry while parent caller using it.

This is checking for type the bug Luc reported.
Basiclly, the parent DO_FOR_EACH() has __nr caching the
current ptr position. When the inner loop function delete
one entry before the current position. The parent current
position needs to be adjust, because the entry[] has been
move forward.

This patch only check usage FOR_EACH_XXX macro. There is
also PREPARE_PTR_LIST haven't cover by this patch.
It is already catching bugs left and right.

Most noticablely remove_usage() inside of the  kill_use_list()
loop.
---
 ptrlist.h | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

diff --git a/ptrlist.h b/ptrlist.h
index d09be2f..4f38a4e 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -25,7 +25,8 @@
 #define LIST_NODE_NR (29)

 struct ptr_list {
- int nr;
+ unsigned int nr:16;
+ unsigned int active:16;
  struct ptr_list *prev;
  struct ptr_list *next;
  void *list[LIST_NODE_NR];
@@ -44,6 +45,7 @@ extern void concat_ptr_list(struct ptr_list *a,
struct ptr_list **b);
 extern void __free_ptr_list(struct ptr_list **);
 extern int ptr_list_size(struct ptr_list *);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);
+extern void die(const char *, ...);

 /*
  * Hey, who said that you can't do overloading in C?
@@ -158,6 +160,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  CHECK_TYPE(head,ptr); \
  if (__head) { \
  do { int __nr; \
+ __list->active++; \
  for (__nr = 0; __nr < __list->nr; __nr++) { \
  do { \
  ptr = PTR_ENTRY(__list,__nr); \
@@ -167,6 +170,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  } while (0); \
  } while (0); \
  } \
+ __list->active--; \
  } while ((__list = __list->next) != __head); \
  } \
 } while (0)
@@ -179,6 +183,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  do { int __nr; \
  __list = __list->prev; \
  __nr = __list->nr; \
+ __list->active++; \
  while (--__nr >= 0) { \
  do { \
  ptr = PTR_ENTRY(__list,__nr); \
@@ -189,6 +194,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  } while (0); \
  } while (0); \
  } \
+ __list->active--; \
  } while (__list != __head); \
  } \
 } while (0)From: Christopher Li <sparse@chrisli.org>
Date: Thu, 6 Jul 2017 16:25:38 -0700
Subject: [PATCH 2/2] check on delete list entry while parent caller using it.

This is checking for type the bug Luc reported.
Basiclly, the parent DO_FOR_EACH() has __nr caching the
current ptr position. When the inner loop function delete
one entry before the current position. The parent current
position needs to be adjust, because the entry[] has been
move forward.

This patch only check usage FOR_EACH_XXX macro. There is
also PREPARE_PTR_LIST haven't cover by this patch.
It is already catching bugs left and right.

Most noticablely remove_usage() inside of the  kill_use_list()
loop.
---
 ptrlist.h | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

diff --git a/ptrlist.h b/ptrlist.h
index d09be2f..4f38a4e 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -25,7 +25,8 @@
 #define LIST_NODE_NR (29)

 struct ptr_list {
- int nr;
+ unsigned int nr:16;
+ unsigned int active:16;
  struct ptr_list *prev;
  struct ptr_list *next;
  void *list[LIST_NODE_NR];
@@ -44,6 +45,7 @@ extern void concat_ptr_list(struct ptr_list *a,
struct ptr_list **b);
 extern void __free_ptr_list(struct ptr_list **);
 extern int ptr_list_size(struct ptr_list *);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);
+extern void die(const char *, ...);

 /*
  * Hey, who said that you can't do overloading in C?
@@ -158,6 +160,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  CHECK_TYPE(head,ptr); \
  if (__head) { \
  do { int __nr; \
+ __list->active++; \
  for (__nr = 0; __nr < __list->nr; __nr++) { \
  do { \
  ptr = PTR_ENTRY(__list,__nr); \
@@ -167,6 +170,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  } while (0); \
  } while (0); \
  } \
+ __list->active--; \From: Christopher Li <sparse@chrisli.org>
Date: Thu, 6 Jul 2017 16:25:38 -0700
Subject: [PATCH 2/2] check on delete list entry while parent caller using it.

This is checking for type the bug Luc reported.
Basiclly, the parent DO_FOR_EACH() has __nr caching the
current ptr position. When the inner loop function delete
one entry before the current position. The parent current
position needs to be adjust, because the entry[] has been
move forward.

This patch only check usage FOR_EACH_XXX macro. There is
also PREPARE_PTR_LIST haven't cover by this patch.
It is already catching bugs left and right.

Most noticablely remove_usage() inside of the  kill_use_list()
loop.
---
 ptrlist.h | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

diff --git a/ptrlist.h b/ptrlist.h
index d09be2f..4f38a4e 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -25,7 +25,8 @@
 #define LIST_NODE_NR (29)

 struct ptr_list {
- int nr;
+ unsigned int nr:16;
+ unsigned int active:16;
  struct ptr_list *prev;
  struct ptr_list *next;
  void *list[LIST_NODE_NR];
@@ -44,6 +45,7 @@ extern void concat_ptr_list(struct ptr_list *a,
struct ptr_list **b);
 extern void __free_ptr_list(struct ptr_list **);
 extern int ptr_list_size(struct ptr_list *);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);
+extern void die(const char *, ...);

 /*
  * Hey, who said that you can't do overloading in C?
@@ -158,6 +160,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  CHECK_TYPE(head,ptr); \
  if (__head) { \
  do { int __nr; \
+ __list->active++; \
  for (__nr = 0; __nr < __list->nr; __nr++) { \
  do { \
  ptr = PTR_ENTRY(__list,__nr); \
@@ -167,6 +170,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  } while (0); \
  } while (0); \
  } \
+ __list->active--; \
  } while ((__list = __list->next) != __head); \
  } \
 } while (0)
@@ -179,6 +183,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  do { int __nr; \
  __list = __list->prev; \
  __nr = __list->nr; \
+ __list->active++; \
  while (--__nr >= 0) { \
  do { \
  ptr = PTR_ENTRY(__list,__nr); \
@@ -189,6 +194,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  } while (0); \
  } while (0); \
  } \
+ __list->active--; \
  } while (__list != __head); \
  } \
 } while (0)
@@ -270,6 +276,9 @@ extern void split_ptr_list_head(struct ptr_list *);
  DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)

 #define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do { \
+ if (__list->active > 1) \
+ die("%s:%d delete entry with %d parent using ", \
+       __FILE__, __LINE__, __list->active - 1); \
  void **__this = __list->list + __nr; \
  void **__last = __list->list + __list->nr - 1; \
  while (__this < __last) { \
-- 
2.9.4

  } while ((__list = __list->next) != __head); \
  } \
 } while (0)
@@ -179,6 +183,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  do { int __nr; \
  __list = __list->prev; \
  __nr = __list->nr; \
+ __list->active++; \
  while (--__nr >= 0) { \
  do { \
  ptr = PTR_ENTRY(__list,__nr); \
@@ -189,6 +194,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
  } while (0); \
  } while (0); \
  } \
+ __list->active--; \
  } while (__list != __head); \
  } \
 } while (0)
@@ -270,6 +276,9 @@ extern void split_ptr_list_head(struct ptr_list *);
  DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)

 #define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do { \
+ if (__list->active > 1) \
+ die("%s:%d delete entry with %d parent using ", \
+       __FILE__, __LINE__, __list->active - 1); \
  void **__this = __list->list + __nr; \
  void **__last = __list->list + __list->nr - 1; \
  while (__this < __last) { \
-- 
2.9.4

@@ -270,6 +276,9 @@ extern void split_ptr_list_head(struct ptr_list *);
  DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)

 #define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do { \
+ if (__list->active > 1) \
+ die("%s:%d delete entry with %d parent using ", \
+       __FILE__, __LINE__, __list->active - 1); \
  void **__this = __list->list + __nr; \
  void **__last = __list->list + __list->nr - 1; \
  while (__this < __last) { \
-- 
2.9.4

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Linus Torvalds]

On Thu, Jul 6, 2017 at 6:18 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> Basiclly, the parent DO_FOR_EACH() has __nr caching the
> current ptr position. When the inner loop function delete
> one entry before the current position. The parent current
> position needs to be adjust, because the entry[] has been
> move forward.

Gaah.

I think the original idea for this was to call pack_ptr_list() only at
the end of all the list traversal that could delete things.

                 Linus

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Thu, Jul 6, 2017 at 6:35 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> Gaah.
>
> I think the original idea for this was to call pack_ptr_list() only at
> the end of all the list traversal that could delete things.
>

That is a very good suggestion. The problem would be to find out who
is the last one using that list. Also walking the list to find out the empty
ptr is extra overhead.

I have an idea. We can actually reference count the ptr_list usage like the
above patch. We need to because we want to know who is the lats one using
that ptrlist bucket. The last one using the ptr_list bucket (not the whole list)
can pack this bucket. It will avoid walking the list more than once just to do
the packing. I will try this idea soon. It might work.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Thu, Jul 06, 2017 at 06:18:48PM -0700, Christopher Li wrote:
> On Thu, Jul 6, 2017 at 5:40 PM, Christopher Li <sparse@chrisli.org> wrote:
> >
> > Thanks for catching it. That is a very serious bug.
> > The release will be on hold until this bug has been fix.
> > It is actually more than one of them. I will send out a separate patch
> > catching this kind of behavior.
> >
> 
> Here is the patch. There is another offender in simplify.c
> 
> Chris
> 
> From: Christopher Li <sparse@chrisli.org>
> Date: Thu, 6 Jul 2017 16:25:38 -0700
> Subject: [PATCH 2/2] check on delete list entry while parent caller using it.
> 
> This is checking for type the bug Luc reported.
> Basiclly, the parent DO_FOR_EACH() has __nr caching the
> current ptr position. When the inner loop function delete
> one entry before the current position. The parent current
> position needs to be adjust, because the entry[] has been
> move forward.
> 
> This patch only check usage FOR_EACH_XXX macro. There is
> also PREPARE_PTR_LIST haven't cover by this patch.
> It is already catching bugs left and right.
> 
> Most noticablely remove_usage() inside of the  kill_use_list()
> loop.
> ---
>  ptrlist.h | 11 ++++++++++-
>  1 file changed, 10 insertions(+), 1 deletion(-)
> 
> diff --git a/ptrlist.h b/ptrlist.h
> index d09be2f..4f38a4e 100644
> --- a/ptrlist.h
> +++ b/ptrlist.h
> @@ -25,7 +25,8 @@
>  #define LIST_NODE_NR (29)
> 
>  struct ptr_list {
> - int nr;
> + unsigned int nr:16;
> + unsigned int active:16;

Mmmm ...

I really don't like this kind of solution.
The ptrlist is already fragile and now it would contains
yet another field that need to be taken care of *and* stay
coherent with other users. I doubt this will help to reduce bugs.

Also, I don't think the principle of this solution is sound.
In particular, these die() make me nervous. 
Can you explain a bit how it is working, how you can guarantee
that these die() won't be called?

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Thu, Jul 6, 2017 at 10:44 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Mmmm ...
>
> I really don't like this kind of solution.
> The ptrlist is already fragile and now it would contains
> yet another field that need to be taken care of *and* stay
> coherent with other users. I doubt this will help to reduce bugs.

You totally miss the point. This patch is not a final solution.
I am not suggesting submit this patch as it is.

It is mean to expose existing bugs. The reason ptrlist is fragile
is we did not do it properly. Not safe against recursive ptr
loop with inner loop delete stuff from the same list.

> Also, I don't think the principle of this solution is sound.
> In particular, these die() make me nervous.
> Can you explain a bit how it is working, how you can guarantee
> that these die() won't be called?

It wouldn't, every die() means a bug get discovered. We need to fix that.

Go try this patch with a "make check". It has over one hundreds fails.
Those are real bugs. The current big offender is remove_usage() inside
of the  kill_use_list(). It might relate to your code as well. Can you help me
take a look at the offender?

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Thu, Jul 06, 2017 at 06:18:48PM -0700, Christopher Li wrote:
> On Thu, Jul 6, 2017 at 5:40 PM, Christopher Li <sparse@chrisli.org> wrote:
> Most noticablely remove_usage() inside of the  kill_use_list()
> loop.

Can you explain a bit what's wrong with this one?

The call chain looks basically like:
   simplify_instruction()			loop over ep->bb & bb->insns)
      kill_use_list()				loop over insn->phi_list
         kill_use() -> remove_use()
            delete_pseudo_user_list_entry	loop over pseudo->users
            kill_instruction()
               kill_use_list()


Note: kill_instruction() doesn't delete the instruction from
      the BB but just mark them as removed which is, I think,
      the right pattern to adopt in general instead of the
      delete/pack.

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Thu, Jul 6, 2017 at 6:35 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>>
>> Basiclly, the parent DO_FOR_EACH() has __nr caching the
>> current ptr position. When the inner loop function delete
>> one entry before the current position. The parent current
>> position needs to be adjust, because the entry[] has been
>> move forward.
>
> Gaah.
>
> I think the original idea for this was to call pack_ptr_list() only at
> the end of all the list traversal that could delete things.

Actually,  the point I am making is different than pack_ptr_list().
I just take a closer look. Pack_ptr_list() only remove empty ptr nodes.
It does not take care my realization that entry[] array sliding forward
causing the parent for loop *missing* ptr entry. Basically the parent
for loop will skip some ptr entry. It is s very subtle and hard to discover.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Thu, Jul 06, 2017 at 11:02:24PM -0700, Christopher Li wrote:
> On Thu, Jul 6, 2017 at 10:44 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Mmmm ...
> >
> > I really don't like this kind of solution.
> > The ptrlist is already fragile and now it would contains
> > yet another field that need to be taken care of *and* stay
> > coherent with other users. I doubt this will help to reduce bugs.
> 
> You totally miss the point. This patch is not a final solution.
> I am not suggesting submit this patch as it is.
> 
> It is mean to expose existing bugs.

Ah, OK.

> Go try this patch with a "make check". It has over one hundreds fails.

I'll do, later (just wakeup here).

> Those are real bugs. The current big offender is remove_usage() inside
> of the  kill_use_list(). It might relate to your code as well. Can you help me
> take a look at the offender?

Yes, of course I'll help with this.
And yes, I added a bunch of these remove_use() with the recursive call
to kill_instruction() which I never liked much but solved a bunch of
things.
 
-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Thu, Jul 6, 2017 at 11:04 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Thu, Jul 06, 2017 at 06:18:48PM -0700, Christopher Li wrote:
>> On Thu, Jul 6, 2017 at 5:40 PM, Christopher Li <sparse@chrisli.org> wrote:
>> Most noticablely remove_usage() inside of the  kill_use_list()
>> loop.
>
> Can you explain a bit what's wrong with this one?

Sure. Sorry I haven't be more specific.
The offending list in question is not the instruction list. It is the
pesudo->user list.

kill_use_list is iterate though p->user.
FOR_EACH_PTR(list, p) {
if (p == VOID)
continue;
kill_use(THIS_ADDRESS(p));
} END_FOR_EACH_PTR(p)


And remove_usage() is deleting the very same list
from with in the loop. That is the bug.

Basically, deleting entry from inner loop while outer loop
is going over the same list has the deleted entry[] sliding
forward problem. Cause the outer loop possible to skip some
entries.

It likely a different bug than the one you discover.
Your crash is likely cause by pack_ptr_list inside the
ptrlist loop. Which cause some pointer point to deleted
node.


I set a break point at die and get the back track as follows:
#0  die (fmt=fmt@entry=0x43e160 "%s:%d delete entry with %d parent
using ") at lib.c:204
#1  0x0000000000420a0f in delete_pseudo_user_list_entry
(list=list@entry=0x7ffff7f2e158, entry=entry@entry=0x7ffff7f72c28,
count=1)
    at simplify.c:175
#2  0x0000000000420d16 in remove_usage (usep=0x7ffff7f72c28,
p=0x7ffff7f2e150) at simplify.c:189
#3  kill_use (usep=0x7ffff7f72c28) at simplify.c:200
#4  kill_use_list (list=0x7ffff7f72c10) at simplify.c:210
#5  0x0000000000420bc9 in kill_insn (insn=insn@entry=0x7ffff7f36450,
force=force@entry=0) at simplify.c:249
#6  0x0000000000422244 in kill_instruction (insn=0x7ffff7f36450) at flow.h:32
#7  clean_up_phi (insn=0x7ffff7f36450) at simplify.c:162
#8  simplify_instruction (insn=insn@entry=0x7ffff7f36450) at simplify.c:1202
#9  0x000000000042015b in clean_up_one_instruction
(insn=0x7ffff7f36450, bb=0x7ffff7f3e5b0) at cse.c:45
#10 clean_up_insns (ep=0x7ffff7f56010) at cse.c:135
#11 cleanup_and_cse (ep=ep@entry=0x7ffff7f56010) at cse.c:366
#12 0x00000000004182e0 in linearize_fn (base_type=<optimized out>,
sym=0x7ffff7f56010) at linearize.c:2244
#13 linearize_symbol (sym=sym@entry=0x7ffff7f69490) at linearize.c:2286
#14 0x0000000000401139 in clean_up_symbols (list=0x7ffff7f6f510) at
test-linearize.c:49
#15 main (argc=<optimized out>, argv=<optimized out>) at test-linearize.c:62

Hope that helps.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Thu, Jul 6, 2017 at 11:10 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
>> Go try this patch with a "make check". It has over one hundreds fails.
>
> I'll do, later (just wakeup here).

No problem at all.

Just a head up. I need to crash soon. And tomorrow I will not have much
Internet access at all. I have time to code but no internet. I will see if I
can get a ptrlist safe against delete.

>
>> Those are real bugs. The current big offender is remove_usage() inside
>> of the  kill_use_list(). It might relate to your code as well. Can you help me
>> take a look at the offender?
>
> Yes, of course I'll help with this.
> And yes, I added a bunch of these remove_use() with the recursive call
> to kill_instruction() which I never liked much but solved a bunch of
> things.

Thanks for the help. Yes, that is exactly the bug I am talking about.
Deleting list entry while the parent is still looping on it.
Sparse ptrlist currently has very subtle bug on this situation.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Thu, Jul 06, 2017 at 11:18:39PM -0700, Christopher Li wrote:
> On Thu, Jul 6, 2017 at 11:04 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > On Thu, Jul 06, 2017 at 06:18:48PM -0700, Christopher Li wrote:
> >> On Thu, Jul 6, 2017 at 5:40 PM, Christopher Li <sparse@chrisli.org> wrote:
> >> Most noticablely remove_usage() inside of the  kill_use_list()
> >> loop.
> >
> > Can you explain a bit what's wrong with this one?
> 
> Sure. Sorry I haven't be more specific.
> The offending list in question is not the instruction list. It is the
> pesudo->user list.
> 
> kill_use_list is iterate though p->user.
> FOR_EACH_PTR(list, p) {
> if (p == VOID)
> continue;
> kill_use(THIS_ADDRESS(p));
> } END_FOR_EACH_PTR(p)
> 
> 
> And remove_usage() is deleting the very same list
> from with in the loop. That is the bug.

Strange. kill_use_list() is only iterated via insn->phi_list
or insn->arguments, not p->user.

But yes, something is surely messing with the lists here.

> It likely a different bug than the one you discover.
> Your crash is likely cause by pack_ptr_list inside the
> ptrlist loop. Which cause some pointer point to deleted
> node.

Yes, it's a different one.
Mine wasn't through pack_ptr_list() but directly in the macros
doing the list walking of ep->bbs.

Anyway, look at all this later.

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Thu, Jul 06, 2017 at 11:27:58PM -0700, Christopher Li wrote:
> On Thu, Jul 6, 2017 at 11:10 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> >> Go try this patch with a "make check". It has over one hundreds fails.
> >
> > I'll do, later (just wakeup here).
> 
> No problem at all.
> 
> Just a head up. I need to crash soon. And tomorrow I will not have much
> Internet access at all. I have time to code but no internet. I will see if I
> can get a ptrlist safe against delete.

Sure, no problem.
 
> Sparse ptrlist currently has very subtle bug on this situation.

Yes, it's not the first time we have been bitten by them.

The real problem, in my opinion, is:
- The ptr_list macros & functions have rules about their usage but
  * they are not explained at all
  * they is no way to enforce them or detect a violation
  * detection a violation will probably have a cost higher than
    we'll be willing to pay.
  * it's hard to not violate these rules because list walking is
    ubiquitous.
- Problems can only occurs when deleting an element from the list.
  Pure walking of the list, adding an element or modifying one
  is safe. Even modifying the pointer itself, like, for example,
  setting it to NULL, is safe (hint, hint!).

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Fri, Jul 7, 2017 at 12:11 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> And remove_usage() is deleting the very same list
>> from with in the loop. That is the bug.
>
> Strange. kill_use_list() is only iterated via insn->phi_list
> or insn->arguments, not p->user.
>
> But yes, something is surely messing with the lists here.
>

I figure it out. It is a false alarm on the checking side.
The condition I want to check can still cause a bug,
but this report is not one of those conditions.

It is cause by this code:

static int dead_insn(struct instruction *insn, pseudo_t *src1,
pseudo_t *src2, pseudo_t *src3)
{
struct pseudo_user *pu;
FOR_EACH_PTR(insn->target->users, pu) {
if (*pu->userp != VOID)
return 0;
} END_FOR_EACH_PTR(pu);

So the return terminate the execution flow before
reaching to the  END_FOR_EACH_PTR(pu).
The ptr->active still think we are in the loop
But we are not.

It is a bug in the checking side. I still think this kind
of checking is useful, but need some special handle
of bail out of the ptr_list loop.

Very sorry about that.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Thu, Jul 06, 2017 at 10:15:02PM -0700, Christopher Li wrote:
> On Thu, Jul 6, 2017 at 6:35 PM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> > Gaah.
> >
> > I think the original idea for this was to call pack_ptr_list() only at
> > the end of all the list traversal that could delete things.
> >
> 
> That is a very good suggestion. The problem would be to find out who
> is the last one using that list. Also walking the list to find out the empty
> ptr is extra overhead.
> 
> I have an idea. We can actually reference count the ptr_list usage like the
> above patch. We need to because we want to know who is the lats one using
> that ptrlist bucket. The last one using the ptr_list bucket (not the whole list)
> can pack this bucket. It will avoid walking the list more than once just to do
> the packing. I will try this idea soon. It might work.

This reference count is a property of the whole list and would thus
need to be stored in the head of the list, which doesn't really exist.

Also, I'm not convinced that the problem can only caused by the list
packing in the inner loop (looking at the code for the FOR_EACH, it
looks as it should be OK, but if you enter in the equation, reverse
walking and/or list splitting, I have doubts).

Another point to take in account is that the list packing was needed
because the list walking didn't like empty blocks. But months ago,
because of another bugs we made all the list walking robust against
empty blocks, so list packing shouldn't be needed anymore for
correctness. So we could in general avoid any list packing,
and only do it at some specific safe points just to save memory &
CPU time when walking lists with several blocks but few elements
(and we need to keep in mind that most lists are very very short).

I'm more and more inclined to:
1) in general, avoid altogether deletion from lists in favor
   marking elements as being deleted, either like we do for
   instructions (setting insn->bb to NULL) or storing a special
   value in the ptrlist.
2) at some specific points, as an optimization, doing a sort of
   GC of the list: removing elements marked as deleted and/or
   doing the list packing.
That sound to me as simple, generic and robust.

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Fri, Jul 07, 2017 at 01:25:14AM -0700, Christopher Li wrote:
> On Fri, Jul 7, 2017 at 12:11 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >> And remove_usage() is deleting the very same list
> >> from with in the loop. That is the bug.
> >
> > Strange. kill_use_list() is only iterated via insn->phi_list
> > or insn->arguments, not p->user.
> >
> > But yes, something is surely messing with the lists here.
> >
> 
> I figure it out. It is a false alarm on the checking side.
> The condition I want to check can still cause a bug,
> but this report is not one of those conditions.
> 
> It is cause by this code:
> 
> static int dead_insn(struct instruction *insn, pseudo_t *src1,
> pseudo_t *src2, pseudo_t *src3)
> {
> struct pseudo_user *pu;
> FOR_EACH_PTR(insn->target->users, pu) {
> if (*pu->userp != VOID)
> return 0;
> } END_FOR_EACH_PTR(pu);
> 
> So the return terminate the execution flow before
> reaching to the  END_FOR_EACH_PTR(pu).
> The ptr->active still think we are in the loop
> But we are not.

OK, I see.
 
> It is a bug in the checking side. I still think this kind
> of checking is useful, but need some special handle
> of bail out of the ptr_list loop.

Yes, some kind of optional integrity checking or the kind of
checks you're doing here should be very usefull.

> Very sorry about that.

No problem, of course. 

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Fri, Jul 7, 2017 at 1:28 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> This reference count is a property of the whole list and would thus
> need to be stored in the head of the list, which doesn't really exist.

Obviously I am too tired to think straight right now. But I  think my
idea of reference counting on the list node, not the while list might
actually work.  Because, if the inner loop delete an entry of a different
node than the outer loop was currently holding on, it is actually fine.
Why? Because by the time the outer loop advance to the that the
deleted node, it will reload the list->nr from memory.
I can be wrong through. I should be able to find out soon enough.

> Also, I'm not convinced that the problem can only caused by the list
> packing in the inner loop (looking at the code for the FOR_EACH, it
> looks as it should be OK, but if you enter in the equation, reverse
> walking and/or list splitting, I have doubts).

Like I said, if you delete entry while the outer loop holding the
same ptr node, it is a bug even without packing the list in inner
loop.

I think ref counting the node should be fine with reversing. List
spiting I have to. Will find out.

>
> Another point to take in account is that the list packing was needed
> because the list walking didn't like empty blocks. But months ago,
> because of another bugs we made all the list walking robust against
> empty blocks, so list packing shouldn't be needed anymore for
> correctness. So we could in general avoid any list packing,
> and only do it at some specific safe points just to save memory &
> CPU time when walking lists with several blocks but few elements
> (and we need to keep in mind that most lists are very very short).

I still think if ref counting node properly, it will solve the bug I describe
and possible the list packing as well. If nobody else is holding that
node, it should be fine to pack and delete it. It is not thread safe but
that is a different issue.

>
> I'm more and more inclined to:
> 1) in general, avoid altogether deletion from lists in favor
>    marking elements as being deleted, either like we do for
>    instructions (setting insn->bb to NULL) or storing a special
>    value in the ptrlist.

My idea of the ref count will do exactly that when the inner
loop try to delete an entry but outer loop holding the node as well.
It will increase the deleted count and replace the ptr entry to
NULL.

When the ref count of the node drop to zero and node has delete count.
Pack the entry[] array, remove NULL entry and even possible delete
the node as well.

Let me know if you see any problem with that approach.

> 2) at some specific points, as an optimization, doing a sort of
>    GC of the list: removing elements marked as deleted and/or
>    doing the list packing.

If the ref count node works, then just pack the node when
ref count drop to zero (or one with some care).

One idea is that we can use sparse to check itself
if there is any sparse code return in a loop without dec the ref count.

> That sound to me as simple, generic and robust.

Yes. So our idea is actually very similar. The only difference
is I use ref count as means of GC, so the ptrlist always knows
when it is safe to delete stuff.

I will find out more.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Dibyendu Majumdar]

Hi,

On 7 July 2017 at 07:02, Christopher Li <sparse@chrisli.org> wrote:
> On Thu, Jul 6, 2017 at 10:44 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> The ptrlist is already fragile and now it would contains
>> yet another field that need to be taken care of *and* stay
>> coherent with other users. I doubt this will help to reduce bugs.
>>
> The reason ptrlist is fragile
> is we did not do it properly. Not safe against recursive ptr
> loop with inner loop delete stuff from the same list.
>

One of the first things I encountered when trying to get Sparse to
compile with MSVC was ptrlist as it uses some gcc only features. I
found it quite hard to follow the Macros so I attempted to reduce the
use of macros, and introduced the concept of iterators. So the macros
I use now look like below. I think this approach is easier to
understand and maintain. If you would like a patch for similar
implementation for Sparse then please let me know.

In general though - while a list is being traversed, deleting items
should be expected to work, as long as a ptrlist node is not deleted.
The reason is that an iterator is presumably on a particular node -
and if unknown to it the iterator is deleted, then it has no way to
continue. So maybe calling pack in the middle of an operation is
causing the problem?

Anyway - here is a snippet from my modified ptrlist implementation.

/* Each node in the list */
struct ptr_list {
int nr_;
struct ptr_list *prev_;
struct ptr_list *next_;
struct allocator *allocator_;
void *list_[LIST_NODE_NR];
};

struct ptr_list_iter {
struct ptr_list *__head;
struct ptr_list *__list;
int __nr;
};


#define FOR_EACH_PTR(list, var) \
{ struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
for (var = ptrlist_iter_next(&var##iter__); var != NULL; var =
ptrlist_iter_next(&var##iter__))
#define FOR_EACH_PTR_TYPED(list, type, var) \
{ struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
for (var = (type) ptrlist_iter_next(&var##iter__); var != NULL; var =
(type) ptrlist_iter_next(&var##iter__))
#define FOR_EACH_PTR_TYPE(list, var, ptr_type) \
{ struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
for (var = (ptr_type) ptrlist_iter_next(&var##iter__); var != NULL;
var = (ptr_type) ptrlist_iter_next(&var##iter__))
#define END_FOR_EACH_PTR(var) }

#define FOR_EACH_PTR_REVERSE(list, var) \
{ struct ptr_list_iter var##iter__ = ptrlist_reverse_iterator(list); \
for (var = ptrlist_iter_prev(&var##iter__); var != NULL; var =
ptrlist_iter_prev(&var##iter__))
#define END_FOR_EACH_PTR_REVERSE(var) }

#define RECURSE_PTR_REVERSE(list, var) \
{ struct ptr_list_iter var##iter__ = list##iter__; \
for (var = ptrlist_iter_prev(&var##iter__); var != NULL; var =
ptrlist_iter_prev(&var##iter__))

#define PREPARE_PTR_LIST(list, var) \
struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
var = ptrlist_iter_next(&var##iter__)

#define NEXT_PTR_LIST(var) \
var = ptrlist_iter_next(&var##iter__)
#define FINISH_PTR_LIST(var)

#define THIS_ADDRESS(type, var) \
(type *)ptrlist_iter_this_address(&var##iter__)

#define DELETE_CURRENT_PTR(var) \
ptrlist_iter_remove(&var##iter__)

#define REPLACE_CURRENT_PTR(type, var, replacement) \
ptrlist_iter_set(&var##iter__, replacement)

#define INSERT_CURRENT(newval, var) \
ptrlist_iter_insert(&var##iter__, newval)

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Dibyendu Majumdar]

Apologies for the typo - correction below.

On 7 July 2017 at 10:19, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> Hi,
>
> On 7 July 2017 at 07:02, Christopher Li <sparse@chrisli.org> wrote:
>> On Thu, Jul 6, 2017 at 10:44 PM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>> The ptrlist is already fragile and now it would contains
>>> yet another field that need to be taken care of *and* stay
>>> coherent with other users. I doubt this will help to reduce bugs.
>>>
>> The reason ptrlist is fragile
>> is we did not do it properly. Not safe against recursive ptr
>> loop with inner loop delete stuff from the same list.
>>
>

In general though - while a list is being traversed, deleting items
should be expected to work, as long as a ptrlist node is not deleted.
The reason is that an iterator is presumably on a particular node -
and if unknown to if the node it is on is deleted, then the iterator
has no way to
continue. So maybe calling pack in the middle of an operation is
causing the problem?

I think the current implementation (and my version too) is safe as
long as nodes are not deleted while a traversal is going on?

Thanks and Regards
Dibyendu

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Fri, Jul 07, 2017 at 02:06:14AM -0700, Christopher Li wrote:
> On Fri, Jul 7, 2017 at 1:28 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > This reference count is a property of the whole list and would thus
> > need to be stored in the head of the list, which doesn't really exist.
> 
> Obviously I am too tired to think straight right now. But I  think my
> idea of reference counting on the list node, not the while list might
> actually work.  Because, if the inner loop delete an entry of a different
> node than the outer loop was currently holding on, it is actually fine.
> Why? Because by the time the outer loop advance to the that the
> deleted node, it will reload the list->nr from memory.
> I can be wrong through. I should be able to find out soon enough.
> 
> > Also, I'm not convinced that the problem can only caused by the list
> > packing in the inner loop (looking at the code for the FOR_EACH, it
> > looks as it should be OK, but if you enter in the equation, reverse
> > walking and/or list splitting, I have doubts).
> 
> Like I said, if you delete entry while the outer loop holding the
> same ptr node, it is a bug even without packing the list in inner
> loop.

Yup.
 
> I think ref counting the node should be fine with reversing. List
> spiting I have to. Will find out.
> 
> >
> > Another point to take in account is that the list packing was needed
> > because the list walking didn't like empty blocks. But months ago,
> > because of another bugs we made all the list walking robust against
> > empty blocks, so list packing shouldn't be needed anymore for
> > correctness. So we could in general avoid any list packing,
> > and only do it at some specific safe points just to save memory &
> > CPU time when walking lists with several blocks but few elements
> > (and we need to keep in mind that most lists are very very short).
> 
> I still think if ref counting node properly, it will solve the bug I describe
> and possible the list packing as well. If nobody else is holding that
> node, it should be fine to pack and delete it.

Yes, it's very possible that it will work properly, but at which price?
You will need to add some complexity to make it work, is it worth?

> It is not thread safe but
> that is a different issue.

That's really the last of my worries, sparse is not designed to be threaded
and I don't see why it should.
 
> >
> > I'm more and more inclined to:
> > 1) in general, avoid altogether deletion from lists in favor
> >    marking elements as being deleted, either like we do for
> >    instructions (setting insn->bb to NULL) or storing a special
> >    value in the ptrlist.
> 
> My idea of the ref count will do exactly that when the inner
> loop try to delete an entry but outer loop holding the node as well.
> It will increase the deleted count and replace the ptr entry to
> NULL.
> 
> When the ref count of the node drop to zero and node has delete count.
> Pack the entry[] array, remove NULL entry and even possible delete
> the node as well.
> 
> Let me know if you see any problem with that approach.

Except for the added complexity of having to maintain the ref count
for, IMO, no good enough reasons, the problem is that some lists
contains NULL pointers as legitimate values (I don't remember which
parts do but I had the case when I added the protection for the empty
blocks I also completly rewrote all the ptrlist layer with nice clean
iterator structures and a set of functions around it and those functions
naturally returned NULL to meant the end-of-list. First testing went
quite well but then showed some bugs casued by the fact that some
of the lists contained NULL as legitimate value).
It's why I said here above "marking as deleted or storing a special
value". Of course, maybe we can more easily avoid the few special cases
where NULLs are stored in ptrlist.

> > 2) at some specific points, as an optimization, doing a sort of
> >    GC of the list: removing elements marked as deleted and/or
> >    doing the list packing.
> 
> If the ref count node works, then just pack the node when
> ref count drop to zero (or one with some care).
> 
> One idea is that we can use sparse to check itself
> if there is any sparse code return in a loop without dec the ref count.
> 
> > That sound to me as simple, generic and robust.
> 
> Yes. So our idea is actually very similar. The only difference
> is I use ref count as means of GC, so the ptrlist always knows
> when it is safe to delete stuff.
> 
> I will find out more.


-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Fri, Jul 07, 2017 at 10:26:38AM +0100, Dibyendu Majumdar wrote:
> In general though - while a list is being traversed, deleting items
> should be expected to work, as long as a ptrlist node is not deleted.
> The reason is that an iterator is presumably on a particular node -
> and if unknown to if the node it is on is deleted, then the iterator
> has no way to
> continue. So maybe calling pack in the middle of an operation is
> causing the problem?
> 
> I think the current implementation (and my version too) is safe as
> long as nodes are not deleted while a traversal is going on?

Yes, but the problem is that we do delete nodes while another traversal
is going on. And this can be very indirect.

-- Luc 

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Dibyendu Majumdar]

On 7 July 2017 at 10:38, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote:
> On Fri, Jul 07, 2017 at 10:26:38AM +0100, Dibyendu Majumdar wrote:
>> In general though - while a list is being traversed, deleting items
>> should be expected to work, as long as a ptrlist node is not deleted.
>> The reason is that an iterator is presumably on a particular node -
>> and if unknown to if the node it is on is deleted, then the iterator
>> has no way to
>> continue. So maybe calling pack in the middle of an operation is
>> causing the problem?
>>
>> I think the current implementation (and my version too) is safe as
>> long as nodes are not deleted while a traversal is going on?
>
> Yes, but the problem is that we do delete nodes while another traversal
> is going on. And this can be very indirect.
>

Well I think it is best not to do that really. Why do the nodes need
to be deleted? There is no harm in retaining them surely as long as
the the iterators can handle it?

Regards

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Fri, Jul 7, 2017 at 2:19 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi,
>
> On 7 July 2017 at 07:02, Christopher Li <sparse@chrisli.org> wrote:
>
> Anyway - here is a snippet from my modified ptrlist implementation.
>
> /* Each node in the list */
> struct ptr_list {
> int nr_;
> struct ptr_list *prev_;
> struct ptr_list *next_;
> struct allocator *allocator_;
> void *list_[LIST_NODE_NR];
> };
>
> struct ptr_list_iter {
> struct ptr_list *__head;
> struct ptr_list *__list;
> int __nr;
> };

I try exactly that before.

The problem with that is, it generate horrible code.
I never able to teach gcc the member of the list_iter
does not need to sync at memory boundary. I really
want it to be register like.




>
>
> #define FOR_EACH_PTR(list, var) \
> { struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
> for (var = ptrlist_iter_next(&var##iter__); var != NULL; var =
> ptrlist_iter_next(&var##iter__))
> #define FOR_EACH_PTR_TYPED(list, type, var) \
> { struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
> for (var = (type) ptrlist_iter_next(&var##iter__); var != NULL; var =
> (type) ptrlist_iter_next(&var##iter__))
> #define FOR_EACH_PTR_TYPE(list, var, ptr_type) \
> { struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
> for (var = (ptr_type) ptrlist_iter_next(&var##iter__); var != NULL;
> var = (ptr_type) ptrlist_iter_next(&var##iter__))
> #define END_FOR_EACH_PTR(var) }
>
> #define FOR_EACH_PTR_REVERSE(list, var) \
> { struct ptr_list_iter var##iter__ = ptrlist_reverse_iterator(list); \
> for (var = ptrlist_iter_prev(&var##iter__); var != NULL; var =
> ptrlist_iter_prev(&var##iter__))
> #define END_FOR_EACH_PTR_REVERSE(var) }

The problem with this is that, once you put delete into mix.
The iter will need to know which direction it need to go after
the delete. It is actually very messy.

 I end up abandon that approach.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Dibyendu Majumdar]

On 7 July 2017 at 10:44, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Jul 7, 2017 at 2:19 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> On 7 July 2017 at 07:02, Christopher Li <sparse@chrisli.org> wrote:
>>
>> Anyway - here is a snippet from my modified ptrlist implementation.
>>
>> /* Each node in the list */
>> struct ptr_list {
>> int nr_;
>> struct ptr_list *prev_;
>> struct ptr_list *next_;
>> struct allocator *allocator_;
>> void *list_[LIST_NODE_NR];
>> };
>>
>> struct ptr_list_iter {
>> struct ptr_list *__head;
>> struct ptr_list *__list;
>> int __nr;
>> };
>
> I try exactly that before.
>
> The problem with that is, it generate horrible code.
> I never able to teach gcc the member of the list_iter
> does not need to sync at memory boundary. I really
> want it to be register like.
>
>>
>> #define FOR_EACH_PTR(list, var) \
>> { struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
>> for (var = ptrlist_iter_next(&var##iter__); var != NULL; var =
>> ptrlist_iter_next(&var##iter__))
>> #define FOR_EACH_PTR_TYPED(list, type, var) \
>> { struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
>> for (var = (type) ptrlist_iter_next(&var##iter__); var != NULL; var =
>> (type) ptrlist_iter_next(&var##iter__))
>> #define FOR_EACH_PTR_TYPE(list, var, ptr_type) \
>> { struct ptr_list_iter var##iter__ = ptrlist_forward_iterator(list); \
>> for (var = (ptr_type) ptrlist_iter_next(&var##iter__); var != NULL;
>> var = (ptr_type) ptrlist_iter_next(&var##iter__))
>> #define END_FOR_EACH_PTR(var) }
>>
>> #define FOR_EACH_PTR_REVERSE(list, var) \
>> { struct ptr_list_iter var##iter__ = ptrlist_reverse_iterator(list); \
>> for (var = ptrlist_iter_prev(&var##iter__); var != NULL; var =
>> ptrlist_iter_prev(&var##iter__))
>> #define END_FOR_EACH_PTR_REVERSE(var) }
>
> The problem with this is that, once you put delete into mix.
> The iter will need to know which direction it need to go after
> the delete. It is actually very messy.
>
>  I end up abandon that approach.

I am using this without problems in dmr_C so not sure I understand why
it did not work.

Regards
Dibyendu

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Fri, Jul 07, 2017 at 10:28:03AM +0200, Luc Van Oostenryck wrote:
> Another point to take in account is that the list packing was needed
> because the list walking didn't like empty blocks. But months ago,
> because of another bugs we made all the list walking robust against
> empty blocks, so list packing shouldn't be needed anymore for
> correctness. So we could in general avoid any list packing,
> and only do it at some specific safe points just to save memory &
> CPU time when walking lists with several blocks but few elements
> (and we need to keep in mind that most lists are very very short).
> 
> I'm more and more inclined to:
> 1) in general, avoid altogether deletion from lists in favor
>    marking elements as being deleted, either like we do for
>    instructions (setting insn->bb to NULL) or storing a special
>    value in the ptrlist.
> 2) at some specific points, as an optimization, doing a sort of
>    GC of the list: removing elements marked as deleted and/or
>    doing the list packing.
> That sound to me as simple, generic and robust.

Another thing that could help is that, in fact, for most lists/
list types we can't have nested list walking.

In practice, BB & insn lists will be the ones really concerned
and insns are immune to the problem since they are never deleted
but simply marked as deleted.

And this is only because the cleanup code is all done inside the
ep->bbs & bb->insns loops. So at the end, I wouldn't be surprised
that only the BBs are impacted, which is coherent to what the
testing showed.

But yes, we need to have guarantees.

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Fri, Jul 7, 2017 at 2:30 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Yes, it's very possible that it will work properly, but at which price?
> You will need to add some complexity to make it work, is it worth?

We will see. I think it is clean enough I will take a try.
The price is my time and other's who will need to review it.



> Except for the added complexity of having to maintain the ref count
> for, IMO, no good enough reasons, the problem is that some lists
> contains NULL pointers as legitimate values (I don't remember which

I guess we will find out. It is not hard to assert of NULL add to the
ptrlist. I do have ways to allow any value in entry but add more complexity.
Doing the correct thing is first priority.

If we are talking about the run time cost, I double it will make much of
the difference. We can benchmark for it.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Fri, Jul 7, 2017 at 2:41 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Well I think it is best not to do that really. Why do the nodes need
> to be deleted? There is no harm in retaining them surely as long as
> the the iterators can handle it?
>
Please know that, even the node is not deleted. Just remove the
entry from list->list[] will cause problem on the outer loop on the same
list, if there is one.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Fri, Jul 7, 2017 at 11:46 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> I am using this without problems in dmr_C so not sure I understand why
> it did not work.

It may be related to the amount of testing.
The problem we have here is not exactly frequent, on the contrary.
I have tested sparse in all sort of conditions, during hours with a lot of
code, normal and less normal, without any problems.
It's only after I did some fuzzing that I got these, and I only had a few tens
of crashes after more than 150 hours of fuzzing and more than 600GB
of generated code (which was then sometimes purposely corrupted).

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Dibyendu Majumdar]

On 7 July 2017 at 10:58, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Jul 7, 2017 at 2:41 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> Well I think it is best not to do that really. Why do the nodes need
>> to be deleted? There is no harm in retaining them surely as long as
>> the the iterators can handle it?
>>
> Please know that, even the node is not deleted. Just remove the
> entry from list->list[] will cause problem on the outer loop on the same
> list, if there is one.
>

I will test this in my version but I believe that deleting entries in
list->list[] is okay. Every time the next operation on the iterator is
called, it checks whether its index in the node is still valid. As
long as nodes are not deleted then it should work - but I need to
prove it via a test case.

Here is my forward iterator next implementation:

void *ptrlist_iter_next(struct ptr_list_iter *self) {
  if (self->__head == NULL)
    return NULL;
  self->__nr++;
Lretry:
  if (self->__nr < self->__list->nr_) {
    return self->__list->list_[self->__nr];
  } else if (self->__list->next_ != self->__head) {
    self->__list = self->__list->next_;
    self->__nr = 0;
    goto Lretry;
  }
  return NULL;
}

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Fri, Jul 7, 2017 at 3:08 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> I will test this in my version but I believe that deleting entries in
> list->list[] is okay. Every time the next operation on the iterator is
> called, it checks whether its index in the node is still valid. As
> long as nodes are not deleted then it should work - but I need to
> prove it via a test case.

As far as I can tell, your code will have the same bug.  If
same list used in the outer loop and inner loop and inner
loop delete an entry.


>
> Here is my forward iterator next implementation:
>
> void *ptrlist_iter_next(struct ptr_list_iter *self) {
>   if (self->__head == NULL)
>     return NULL;
>   self->__nr++;
> Lretry:
>   if (self->__nr < self->__list->nr_) {
>     return self->__list->list_[self->__nr];
>   } else if (self->__list->next_ != self->__head) {
>     self->__list = self->__list->next_;
>     self->__nr = 0;
>     goto Lretry;
>   }

Let say __list has 8 entry. nr = 8.  self->__nr = 3.
In the inner loop delete first 2 entry. Then the list[2:8]
will shift to list[0:6]. Now your self->__nr = 3 will
skip the next 2 entry because they move to list[1:3].

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Dibyendu Majumdar]

On 7 July 2017 at 13:54, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Jul 7, 2017 at 3:08 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> I will test this in my version but I believe that deleting entries in
>> list->list[] is okay. Every time the next operation on the iterator is
>> called, it checks whether its index in the node is still valid. As
>> long as nodes are not deleted then it should work - but I need to
>> prove it via a test case.
>
> As far as I can tell, your code will have the same bug.  If
> same list used in the outer loop and inner loop and inner
> loop delete an entry.
>
>
>>
>> Here is my forward iterator next implementation:
>>
>> void *ptrlist_iter_next(struct ptr_list_iter *self) {
>>   if (self->__head == NULL)
>>     return NULL;
>>   self->__nr++;
>> Lretry:
>>   if (self->__nr < self->__list->nr_) {
>>     return self->__list->list_[self->__nr];
>>   } else if (self->__list->next_ != self->__head) {
>>     self->__list = self->__list->next_;
>>     self->__nr = 0;
>>     goto Lretry;
>>   }
>
> Let say __list has 8 entry. nr = 8.  self->__nr = 3.
> In the inner loop delete first 2 entry. Then the list[2:8]
> will shift to list[0:6]. Now your self->__nr = 3 will
> skip the next 2 entry because they move to list[1:3].
>

Yes okay. So that means the inner loop cannot modify the list, as even
adding an element will alter the order.

Presumably this issue occurs when the same list is traversed
recursively and the inner loop modifies the list. Was this usage
always there is Sparse or is it a recent change?

Regards
Dibyendu

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Dibyendu Majumdar]

Hi Chris,

On 7 July 2017 at 10:06, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Jul 7, 2017 at 1:28 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>>
> My idea of the ref count will do exactly that when the inner
> loop try to delete an entry but outer loop holding the node as well.
> It will increase the deleted count and replace the ptr entry to
> NULL.
>
> When the ref count of the node drop to zero and node has delete count.
> Pack the entry[] array, remove NULL entry and even possible delete
> the node as well.
>
> Let me know if you see any problem with that approach.
>

How will the insertion scenario be handled - or even splits caused by
insertion? These would also invalidate the order of the entries in a
ptr list node, right?

I think that maybe an alternative approach is to use a lock, and
ensure that the ptr list node is locked while it is being iterated.
Only lock holder can modify. Any inner loop will fail if it tries to
modify the node. The lock can be a pointer - so if NULL unlocked, else
locked. Using a pointer as lock allows concept of ownership.

But anyway this is only to catch scenarios where the list is being
changed by an inner loop.

Regards
Dibyendu

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Fri, Jul 7, 2017 at 3:18 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Chris,
>
> On 7 July 2017 at 10:06, Christopher Li <sparse@chrisli.org> wrote:
>> On Fri, Jul 7, 2017 at 1:28 AM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>>
>> My idea of the ref count will do exactly that when the inner
>> loop try to delete an entry but outer loop holding the node as well.
>> It will increase the deleted count and replace the ptr entry to
>> NULL.
>>
>> When the ref count of the node drop to zero and node has delete count.
>> Pack the entry[] array, remove NULL entry and even possible delete
>> the node as well.
>>
>> Let me know if you see any problem with that approach.
>>
>
> How will the insertion scenario be handled - or even splits caused by
> insertion? These would also invalidate the order of the entries in a
> ptr list node, right?
>
> I think that maybe an alternative approach is to use a lock, and
> ensure that the ptr list node is locked while it is being iterated.

Don't forget that it's not multithreaded code we're talking here:
a lock, in itself, won't help since there is no concurrent access.

Otherwise, it's quite similar to Chris' idea of using a refcount.
But then, we 'just' have to correctly maintain this refcount.

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Dibyendu Majumdar]

Hi Luc,

On 7 July 2017 at 14:25, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote:
> On Fri, Jul 7, 2017 at 3:18 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> On 7 July 2017 at 10:06, Christopher Li <sparse@chrisli.org> wrote:
>>> On Fri, Jul 7, 2017 at 1:28 AM, Luc Van Oostenryck
>>> <luc.vanoostenryck@gmail.com> wrote:
>>>>
>>> My idea of the ref count will do exactly that when the inner
>>> loop try to delete an entry but outer loop holding the node as well.
>>> It will increase the deleted count and replace the ptr entry to
>>> NULL.
>>>
>>> When the ref count of the node drop to zero and node has delete count.
>>> Pack the entry[] array, remove NULL entry and even possible delete
>>> the node as well.
>>>
>>> Let me know if you see any problem with that approach.
>>>
>>
>> How will the insertion scenario be handled - or even splits caused by
>> insertion? These would also invalidate the order of the entries in a
>> ptr list node, right?
>>
>> I think that maybe an alternative approach is to use a lock, and
>> ensure that the ptr list node is locked while it is being iterated.
>
> Don't forget that it's not multithreaded code we're talking here:
> a lock, in itself, won't help since there is no concurrent access.

Yes realize that - so the lock here is only a concept. It is not a
mutex or anything like that.

>
> Otherwise, it's quite similar to Chris' idea of using a refcount.
> But then, we 'just' have to correctly maintain this refcount.
>

Agree that if refcount is used as a lock to prevent inner loops from
amending the list then it is the same. But I think Chris is trying to
do more - i.e. allow an inner loop to amend the list. That might
simply not be possible to handle safely.

Regards
Dibyendu

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Fri, Jul 07, 2017 at 02:29:56PM +0100, Dibyendu Majumdar wrote:
> Agree that if refcount is used as a lock to prevent inner loops from
> amending the list then it is the same. But I think Chris is trying to
> do more - i.e. allow an inner loop to amend the list. That might
> simply not be possible to handle safely.

We have to do something more (or something less :)) otherwise
the refcount can only be used to detect a problem. In other words,
having a situation like "OK, I can't safely do XYZ here" is maybe
better than the current situation but doesn't help when you need
to do XYZ.

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Fri, Jul 7, 2017 at 6:47 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> We have to do something more (or something less :)) otherwise
> the refcount can only be used to detect a problem. In other words,
> having a situation like "OK, I can't safely do XYZ here" is maybe
> better than the current situation but doesn't help when you need
> to do XYZ.

Right. The real implementation will replace the die with some code to
handle those situation. I am also considering a debug version of
sparse which performance those extra test at a performance penalty.

Just generate two executable. One for normal production use. The
other one for developer to find out potential issue. Some of the code
have to be compile differently(ptrlist), it is not easy to implement as turn on
by a command line options.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Thu, Jul 6, 2017 at 12:19 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Fix this, by adding a flag to kill_unreachable_bbs(), telling
> if it is safe to delete the BBs or if we can just mark them
> as unreachable (set bb->ep to NULL and unlink any parent and/or
> chilren), in which case the deletion will be done later.
>
> Note: the reproducer is one with very broken syntax but nothing
>       seems to forbid the same situation to happen with a valid
>       program.

I think it is simpler to move the kill not reachable bb to outer
CSE stage. The following patch has been test pass kernel compile
test. Feel free to combine that with your test as one patch.

git branch:

https://git.kernel.org/pub/scm/devel/sparse/sparse.git/log/?h=sparse-next-20170708

Chris

From 5234b1fcb69ade5e69ab3a528b57c8f5cea9b11e Mon Sep 17 00:00:00 2001
From: Christopher Li <sparse@chrisli.org>
Date: Sat, 8 Jul 2017 19:34:49 -0700
Subject: [PATCH 1/2] move kill_unreachable_bbs to outer cse stage

The current way of kill_unreach_bbs in insert_branch()
cause delete entry in ptrlist that the upper level
caller is looping on.

Move it outside to the cse stage avoid that problem.

Reported-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Signed-of-By: Christopher Li <sparse@chrisli.org>
---
 cse.c       | 3 +++
 flow.c      | 2 +-
 linearize.c | 3 ---
 3 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/cse.c b/cse.c
index 0d3815c..af9863f 100644
--- a/cse.c
+++ b/cse.c
@@ -387,6 +387,9 @@ repeat:
  }
  }

+ if (repeat_phase & REPEAT_CFG_CLEANUP)
+ kill_unreachable_bbs(ep);
+
  if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
  simplify_memops(ep);

diff --git a/flow.c b/flow.c
index c7161d4..5d2f15a 100644
--- a/flow.c
+++ b/flow.c
@@ -841,7 +841,7 @@ void kill_unreachable_bbs(struct entrypoint *ep)
  } END_FOR_EACH_PTR(bb);
  PACK_PTR_LIST(&ep->bbs);

- repeat_phase &= ~REPEAT_CFG_CLEANUP;
+ repeat_phase |=  REPEAT_CSE ;
 }

 static int rewrite_parent_branch(struct basic_block *bb, struct
basic_block *old, struct basic_block *new)
diff --git a/linearize.c b/linearize.c
index 7313e72..a367207 100644
--- a/linearize.c
+++ b/linearize.c
@@ -671,9 +671,6 @@ void insert_branch(struct basic_block *bb, struct
instruction *jmp, struct basic
  remove_parent(child, bb);
  } END_FOR_EACH_PTR(child);
  PACK_PTR_LIST(&bb->children);

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

> diff --git a/flow.c b/flow.c
> index c7161d4..5d2f15a 100644
> --- a/flow.c
> +++ b/flow.c
> @@ -841,7 +841,7 @@ void kill_unreachable_bbs(struct entrypoint *ep)
>   } END_FOR_EACH_PTR(bb);
>   PACK_PTR_LIST(&ep->bbs);
> 
> - repeat_phase &= ~REPEAT_CFG_CLEANUP;
> + repeat_phase |=  REPEAT_CSE ;

It would be good to add a comment for why the '|= REPEAT_CSE' is needed here.

And not removing the REPEAT_CFG_CLEANUP is an error IMO.
At the end of the function the CFG *is* clean. If you don't
clear it here, then what is its meaning?

-- Luc

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

On Sun, Jul 9, 2017 at 3:26 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> diff --git a/flow.c b/flow.c
>> index c7161d4..5d2f15a 100644
>> --- a/flow.c
>> +++ b/flow.c
>> @@ -841,7 +841,7 @@ void kill_unreachable_bbs(struct entrypoint *ep)
>>   } END_FOR_EACH_PTR(bb);
>>   PACK_PTR_LIST(&ep->bbs);
>>
>> - repeat_phase &= ~REPEAT_CFG_CLEANUP;
>> + repeat_phase |=  REPEAT_CSE ;
>
> It would be good to add a comment for why the '|= REPEAT_CSE' is needed here.
OK. I will update the patch. Basically removing unreachable dead code will
impact the us


> And not removing the REPEAT_CFG_CLEANUP is an error IMO.
> At the end of the function the CFG *is* clean. If you don't
> clear it here, then what is its meaning?
It is an error as concept or it is an error the program will do wrong
things?

I want to turn REPEAT_CFG_CLEANUP usage pattern similar
to REPEAT_SYMBOL_CLEANUP. Take the a look at

if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
simplify_memops(ep);

The simplify_memops does not clear the REPEAT_SYMBOL_CLEANUP
either. It was clear at the very beginning of the cse repeat loop:

repeat:
repeat_phase = 0;

I just want to be consistent with other usage of the similar flags.

It is also a reflection of my review feedback when you submit the
patch back then. One of the comment I give was that I want to
avoid calling "kill unreachable bb" multiple time within one "ep->bbs"
pass. You said there is no simple way to do it. This patch is actually
what I want back then.

I think when you introduce REPEAT_CFG_CLEANUP you have
different usage in mind. I found the flag clean at beginning of the
CSE loop is conceptually clean as well, it is simpler. The flag
is just a request, it can set more than one times. The action is
perform only once at one CSE pass.

Chris

Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

On Sun, Jul 09, 2017 at 07:44:46AM -0700, Christopher Li wrote:
> On Sun, Jul 9, 2017 at 3:26 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >> diff --git a/flow.c b/flow.c
> >> index c7161d4..5d2f15a 100644
> >> --- a/flow.c
> >> +++ b/flow.c
> >> @@ -841,7 +841,7 @@ void kill_unreachable_bbs(struct entrypoint *ep)
> >>   } END_FOR_EACH_PTR(bb);
> >>   PACK_PTR_LIST(&ep->bbs);
> >>
> >> - repeat_phase &= ~REPEAT_CFG_CLEANUP;
> >> + repeat_phase |=  REPEAT_CSE ;
> >
> > It would be good to add a comment for why the '|= REPEAT_CSE' is needed here.
> OK. I will update the patch. Basically removing unreachable dead code will
> impact the us
> 
> 
> > And not removing the REPEAT_CFG_CLEANUP is an error IMO.
> > At the end of the function the CFG *is* clean. If you don't
> > clear it here, then what is its meaning?
> It is an error as concept or it is an error the program will do wrong
> things?

Concept.
 
> I want to turn REPEAT_CFG_CLEANUP usage pattern similar
> to REPEAT_SYMBOL_CLEANUP.


> I just want to be consistent with other usage of the similar flags.

For the other usage, the clearing of the flag (REPEAT_CSE) was done
just after the CSE was done.

You focus on the placement. I would focus on the meaning.
But it's your choice.

> I think when you introduce REPEAT_CFG_CLEANUP you have
> different usage in mind. I found the flag clean at beginning of the
> CSE loop is conceptually clean as well, it is simpler. The flag
> is just a request, it can set more than one times. The action is
> perform only once at one CSE pass.

This doesn't sound technically convincing to me, not at all.
Does the facts that:
1) it's a request flag
2) it can be set more than once
imply in any sort of way that:
1) the action is to be performed at the CSE pass and only there
2) and thus the only sane place where the flag can be cleared
   is there like the other flags?

By clearing the flag there and not at the end of the function
doing the action, you're more or less forcing the action to be
done there and only there. This may be a good enough reason to
for whishing to enforce that but then tell it, put it in a nice
comment in the code.

This is certainly not "conceptually clean as well" to me.

-- Luc

Re: [PATCH 2/5] avoid crash when ep->active is NULL

[Luc Van Oostenryck]

This patch fixes a reproducible crash and have been ignored
since it has been posted two weeks ago.
Is there any reasons why?

-- Luc

Re: [PATCH 3/5] avoid crash in rewrite_branch()

[Luc Van Oostenryck]

This patch fixes a reproducible crash and have been ignored
since it has been posted two weeks ago.
Is there any reasons why?

-- Luc

Re: [PATCH 4/5] avoid some crashes in add_dominators()

[Luc Van Oostenryck]

This patch fixes a reproducible crash and have been ignored
since it has been posted two weeks ago.
Is there any reasons why?

BTW, I had forgot the SoB. Here it is:

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

Re: [PATCH 5/5] avoid crash with sym->bb_target == NULL

[Luc Van Oostenryck]

This patch fixes a reproducible crash and have been ignored
since it has been posted two weeks ago.
Is there any reasons why?

-- Luc

Re: [PATCH 2/5] avoid crash when ep->active is NULL

[Christopher Li]

On Wed, Jul 19, 2017 at 3:20 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This patch fixes a reproducible crash and have been ignored
> since it has been posted two weeks ago.
> Is there any reasons why?

Because you are away? We are discussing the different approach of the first
patch and all the sudden you stop response to email.

Those small patch are trivial to review. Just a ping would be good enough.

BTW, the check should happen before the allocation. Otherwise there is
memory leak.

Chris

        pseudo_t phi = __alloc_pseudo(0);
        static int nr = 0;

+       if (!source)
+               return VOID;
+

Re: [PATCH 5/5] avoid crash with sym->bb_target == NULL

[Christopher Li]

On Thu, Jul 6, 2017 at 3:19 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> +                       sym = expr->symbol;
> +                       if (sym->bb_target)
> +                               buf += sprintf(buf, ".L%u", sym->bb_target->nr);
You chould do:
bb = expr->symbol->target;
if (bb)
    buf +=  sprintf(buf, ".L%u", bb ? bb->nr);
else
    buf += sprintf(buf, ".L<invalid>");

It is up to you.

Chris

Re: [PATCH 5/5] avoid crash with sym->bb_target == NULL

[Luc Van Oostenryck]

On Thu, Jul 20, 2017 at 12:57 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Thu, Jul 6, 2017 at 3:19 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> +                       sym = expr->symbol;
>> +                       if (sym->bb_target)
>> +                               buf += sprintf(buf, ".L%u", sym->bb_target->nr);
> You chould do:
> bb = expr->symbol->target;
> if (bb)
>     buf +=  sprintf(buf, ".L%u", bb ? bb->nr);
> else
>     buf += sprintf(buf, ".L<invalid>");
>
> It is up to you.

Yes, it's more informative but I have a later series which convert all these
to calls to a function show_label() which then do the right thing.
So, I prefer to leave like this for the moment.

-- Luc

Re: [PATCH 5/5] avoid crash with sym->bb_target == NULL

[Christopher Li]

On Sat, Jul 29, 2017 at 8:30 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Yes, it's more informative but I have a later series which convert all these
> to calls to a function show_label() which then do the right thing.
> So, I prefer to leave like this for the moment.

That is of course fine. Let me know if you have updated series to pull from.

Chris