[PATCH v3 0/5] fix list corruption with recursive remove_usage()

[PATCH v3 0/5] fix list corruption with recursive remove_usage()

[Luc Van Oostenryck]

The goal of this series is to avoid list corruption that may happen
with pseudo-users when deleting one while doing nested ptrlist walking.
This can occurs with mutually recursive calls:
        remove_usage() -> kill_instruction() -> remove_usage() ...

Changes since v2:
- replace the local tests against null list elements
  by one done directly by the list iteration macros
Changes since v3:
- effectively commit the last commit
  
The series is also available in the git repository at:

  git://github.com/lucvoo/sparse.git fix-nested-pseudo-users-deletion-v4

for you to fetch changes up to bddf7d1e4ed81c3def7c6de2796a5489ca678399:

  mark pseudo users as deleted instead of removing them (2017-08-05 00:14:02 +0200)

----------------------------------------------------------------
Luc Van Oostenryck (5):
      ptrlist: add a counter for the number of removed elemnets
      ptrlist: adjust ptr_list_size for the new ->rm field
      ptrlist: add MARK_CURRENT_DELETED
      ptrlist: avoid iteration on NULL entries
      mark pseudo users as deleted instead of removing them

 ptrlist.c  |  2 +-
 ptrlist.h  | 15 ++++++++++++++-
 simplify.c |  5 +++--
 3 files changed, 18 insertions(+), 4 deletions(-)

[PATCH v4 1/5] ptrlist: add a counter for the number of removed elemnets

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ptrlist.h | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/ptrlist.h b/ptrlist.h
index d09be2f51..d8203cf0b 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -25,7 +25,8 @@
 #define LIST_NODE_NR (29)
 
 struct ptr_list {
-	int nr;
+	int nr:8;
+	int rm:8;
 	struct ptr_list *prev;
 	struct ptr_list *next;
 	void *list[LIST_NODE_NR];
-- 
2.13.2

[PATCH v4 2/5] ptrlist: adjust ptr_list_size for the new ->rm field

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ptrlist.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/ptrlist.c b/ptrlist.c
index 5dc1117c5..8402f8d2b 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -23,7 +23,7 @@ int ptr_list_size(struct ptr_list *head)
 	if (head) {
 		struct ptr_list *list = head;
 		do {
-			nr += list->nr;
+			nr += list->nr - list->rm;
 		} while ((list = list->next) != head);
 	}
 	return nr;
-- 
2.13.2

[PATCH v4 3/5] ptrlist: add MARK_CURRENT_DELETED

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ptrlist.h | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/ptrlist.h b/ptrlist.h
index d8203cf0b..74b80e220 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -287,6 +287,14 @@ extern void split_ptr_list_head(struct ptr_list *);
 #define REPLACE_CURRENT_PTR(ptr, new_ptr)						\
 	do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
 
+#define DO_MARK_CURRENT_DELETED(ptr, __list) do {	\
+		REPLACE_CURRENT_PTR(ptr, NULL);		\
+		__list->rm++;				\
+	} while (0)
+
+#define MARK_CURRENT_DELETED(ptr) \
+	DO_MARK_CURRENT_DELETED(ptr, __list##ptr)
+
 extern void pack_ptr_list(struct ptr_list **);
 
 #define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x))
-- 
2.13.2

[PATCH v4 4/5] ptrlist: avoid iteration on NULL entries

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ptrlist.h | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/ptrlist.h b/ptrlist.h
index 74b80e220..1839b0f46 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -162,6 +162,8 @@ static inline void *last_ptr_list(struct ptr_list *list)
 			for (__nr = 0; __nr < __list->nr; __nr++) {			\
 				do {							\
 					ptr = PTR_ENTRY(__list,__nr);			\
+					if (list->rm && !ptr)				\
+						continue;				\
 					do {
 
 #define DO_END_FOR_EACH(ptr, __head, __list, __nr)					\
@@ -183,6 +185,8 @@ static inline void *last_ptr_list(struct ptr_list *list)
 			while (--__nr >= 0) {						\
 				do {							\
 					ptr = PTR_ENTRY(__list,__nr);			\
+					if (list->rm && !ptr)				\
+						continue;				\
 					do {
 
 
-- 
2.13.2

[PATCH v4 5/5] mark pseudo users as deleted instead of removing them

[Luc Van Oostenryck]

This will fix the (rare) problems with deletion while doing
nested ptrlist walking that occurs when doing recursive
kill_instruction() - remove_usage() - kill_instruction()

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ptrlist.h  | 4 ++--
 simplify.c | 5 +++--
 2 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 1839b0f46..78625c8d8 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -162,7 +162,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
 			for (__nr = 0; __nr < __list->nr; __nr++) {			\
 				do {							\
 					ptr = PTR_ENTRY(__list,__nr);			\
-					if (list->rm && !ptr)				\
+					if (__list->rm && !ptr)				\
 						continue;				\
 					do {
 
@@ -185,7 +185,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
 			while (--__nr >= 0) {						\
 				do {							\
 					ptr = PTR_ENTRY(__list,__nr);			\
-					if (list->rm && !ptr)				\
+					if (__list->rm && !ptr)				\
 						continue;				\
 					do {
 
diff --git a/simplify.c b/simplify.c
index 03ff9c942..2bc86f53e 100644
--- a/simplify.c
+++ b/simplify.c
@@ -172,14 +172,15 @@ static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_
 
 	FOR_EACH_PTR(*list, pu) {
 		if (pu->userp == entry) {
-			DELETE_CURRENT_PTR(pu);
+			MARK_CURRENT_DELETED(pu);
 			if (!--count)
 				goto out;
 		}
 	} END_FOR_EACH_PTR(pu);
 	assert(count <= 0);
 out:
-	pack_ptr_list((struct ptr_list **)list);
+	if (ptr_list_size((struct ptr_list *) *list) == 0)
+		*list = NULL;
 	return count;
 }
 
-- 
2.13.2