[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
  
The series is also available in the git repository at:

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

for you to fetch changes up to 4e2f74793baa52c127653efaedaacb0b52b8f884:

  mark pseudo users as deleted instead of removing them (2017-08-04 23:50:12 +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 v3 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 v3 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 v3 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 v3 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 v3 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>
---
 simplify.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

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

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

[Luc Van Oostenryck]

Please ignore this one. I just resent a -v4.

-- Luc

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

[Christopher Li]

On Fri, Aug 4, 2017 at 6:32 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Please ignore this one. I just resent a -v4.

Your V4 include a git pull address right?

Chris

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

[Luc Van Oostenryck]

On Sat, Aug 5, 2017 at 2:24 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Aug 4, 2017 at 6:32 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> Please ignore this one. I just resent a -v4.
>
> Your V4 include a git pull address right?

Yes, sure.
Why you're asking?

-- Luc

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

[Christopher Li]

On Sat, Aug 5, 2017 at 4:55 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sat, Aug 5, 2017 at 2:24 AM, Christopher Li <sparse@chrisli.org> wrote:
>> On Fri, Aug 4, 2017 at 6:32 PM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>> Please ignore this one. I just resent a -v4.
>>
>> Your V4 include a git pull address right?
>
> Yes, sure.
> Why you're asking?

Because I am expect an email title [PATCH V4 0/5] ... which contain the git url.
I can't find that email. The mail list archive does not have that mail either.

Did you forget to send he 0/5 mail?

Chris

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

[Christopher Li]

On Sat, Aug 5, 2017 at 4:55 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Yes, sure.
> Why you're asking?

OK, I apply the series using patches.
I need to fix up the 4/5 though. As it is the patch 4 will not compile.
The fix is in patch 5. I move that part of the fix from patch 5 to patch 4.

It should be one sparse-next soon. You can check if out if I did any thing
wrong

Chris

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

[Luc Van Oostenryck]

On Sat, Aug 5, 2017 at 1:28 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Sat, Aug 5, 2017 at 4:55 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> On Sat, Aug 5, 2017 at 2:24 AM, Christopher Li <sparse@chrisli.org> wrote:
>>> On Fri, Aug 4, 2017 at 6:32 PM, Luc Van Oostenryck
>>> <luc.vanoostenryck@gmail.com> wrote:
>>>> Please ignore this one. I just resent a -v4.
>>>
>>> Your V4 include a git pull address right?
>>
>> Yes, sure.
>> Why you're asking?
>
> Because I am expect an email title [PATCH V4 0/5] ... which contain the git url.
> I can't find that email. The mail list archive does not have that mail either.
>
> Did you forget to send he 0/5 mail?

No I only forgot to change [PATCH v3 0/5] into [PATCH v4 0/5] while copy pasting
the cover letter.

cfr: http://marc.info/?l=linux-sparse&m=150188507213269&w=4

-- Luc

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

[Christopher Li]

On Sat, Aug 5, 2017 at 7:04 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> No I only forgot to change [PATCH v3 0/5] into [PATCH v4 0/5] while copy pasting
> the cover letter.
>
> cfr: http://marc.info/?l=linux-sparse&m=150188507213269&w=4
>

Do you think I need adjustment or the current version on sparse-next
is fine? I already rebase to master.

The base of your branch is not fast forward to master.

Chris

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

[Luc Van Oostenryck]

On Sun, Aug 6, 2017 at 2:09 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Sat, Aug 5, 2017 at 7:04 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> No I only forgot to change [PATCH v3 0/5] into [PATCH v4 0/5] while copy pasting
>> the cover letter.
>>
>> cfr: http://marc.info/?l=linux-sparse&m=150188507213269&w=4
>>
>
> Do you think I need adjustment or the current version on sparse-next
> is fine? I already rebase to master.

No no. It's fine so.

> The base of your branch is not fast forward to master.

Yes, my branches often don't if there are some other patches but
the branching point is usually quite recent and the merge trivial.

-- Luc

[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(-)