[PATCH 0/2] be more generous with ptrlist repacking

[PATCH 0/2] be more generous with ptrlist repacking

[Luc Van Oostenryck]

The macros that do the ptrlist walking don't handle empty blocks.
So, when some elements are removed from a list some list rapacking
need to be done to remove the empty blocks. Failure to do this
can result in crashes or data corruption.

This series aims to improve the situation by:
- doing the repacking at the places where some elements are removed
  but no repacking where done.
- to compensate the added cost, mark ptrlists as dirty when some
  element are removed from it and only do the repacking when the list
  is marked as dirty.

Another thing that can be done would be to check the dirty bit at every
list walking but I think this should be reserved for testing/debugging.

In fact, while at first agreeing with the idea of the second patch,
I think less and less that it's the right approach.
What are we looking after here?
* Performance?
  - Will this bit save us a lot of list repacking?
* Robustness?
  - What this bit bring us? Nothing without check at each list walking.
    Is it a good idea to sprinkle some assert() on the macros?
  - I would much prefer to have something that either:
    - can do the list walking with empty blocks, or
    - never leave any empty blocks.
    and this without making the macros heavier :)


I'll try later to propose something but for now ...

Luc Van Oostenryck (2):
  add missing PACK_PTR_LIST()
  mark lists to be repacked as dirty

 cse.c      | 1 +
 evaluate.c | 1 +
 ptrlist.c  | 7 +++++++
 ptrlist.h  | 4 +++-
 4 files changed, 12 insertions(+), 1 deletion(-)

-- 

[PATCH 1/2] add missing PACK_PTR_LIST()

[Luc Van Oostenryck]

At two places in the code, DELETE_PTR() is called on soem list
but PACK_PTR_LIST() is not called at the end of the loop.
This potentially leave empty ptrlist 'blocks' which are not handled
by the usual list walking macros.

No concrete situation have been found where a real problem
occurs but better be safe than sorry and call PACK_PTR_LIST()
here too.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c      | 1 +
 evaluate.c | 1 +
 2 files changed, 2 insertions(+)

diff --git a/cse.c b/cse.c
index e8fbe344..71325a74 100644
--- a/cse.c
+++ b/cse.c
@@ -260,6 +260,7 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct
 				if (pu->insn == insn)
 					DELETE_CURRENT_PTR(pu);
 			} END_FOR_EACH_PTR(pu);
+			PACK_PTR_LIST(&phi->users);
 		} END_FOR_EACH_PTR(phi);
 	}
 
diff --git a/evaluate.c b/evaluate.c
index e350c0c0..d1383902 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -2521,6 +2521,7 @@ found:
 		excess(e, lclass & TYPE_PTR ? "array" : "struct or union");
 
 	} END_FOR_EACH_PTR(e);
+	PACK_PTR_LIST(&expr->expr_list);
 
 	convert_designators(last);
 	expr->ctype = ctype;
-- 
2.10.2

[PATCH 2/2] mark lists to be repacked as dirty

[Luc Van Oostenryck]

Use a bit in the head of a ptrlist and set it when
DELETE_PTR() is called.
Check the bit when repacking a list and do nothing if the
bit is not set.

Note: delete_ptr_list_entry() & delete_ptr_list_last()
don't need any handling because they either always call
pack_ptr_list() or remove the last block when it becomes empty.

Suggested-by: Christopher Li <sparse@chrisli.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ptrlist.c | 7 +++++++
 ptrlist.h | 4 +++-
 2 files changed, 10 insertions(+), 1 deletion(-)

diff --git a/ptrlist.c b/ptrlist.c
index 5dc1117c..e817bad1 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -70,6 +70,11 @@ void pack_ptr_list(struct ptr_list **listp)
 
 	if (head) {
 		struct ptr_list *entry = head;
+
+		if (!head->dirty)
+			return;
+		head->dirty = 0;
+
 		do {
 			struct ptr_list *next;
 restart:
@@ -138,6 +143,7 @@ void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
 			list->prev = newlist;
 			last->next = newlist;
 		}
+		newlist->dirty = 0;
 		last = newlist;
 		nr = 0;
 	}
@@ -188,6 +194,7 @@ void * undo_ptr_list_last(struct ptr_list **head)
 
 	if (!first)
 		return NULL;
+	first->dirty = 1;
 	last = first;
 	do {
 		last = last->prev;
diff --git a/ptrlist.h b/ptrlist.h
index 61e159fd..c24bfb82 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -25,7 +25,8 @@
 #define LIST_NODE_NR (29)
 
 struct ptr_list {
-	int nr;
+	int nr:31;
+	unsigned int dirty:1;		// will need to be repacked
 	struct ptr_list *prev;
 	struct ptr_list *next;
 	void *list[LIST_NODE_NR];
@@ -254,6 +255,7 @@ extern void split_ptr_list_head(struct ptr_list *);
 		__this++;								\
 	}										\
 	*__this = (void *)0xf0f0f0f0;							\
+	__head->dirty = 1;								\
 	__list->nr--; __nr--;								\
 } while (0)
 
-- 
2.10.2

Re: [PATCH 0/2] be more generous with ptrlist repacking

[Linus Torvalds]

On Thu, Nov 17, 2016 at 9:25 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The macros that do the ptrlist walking don't handle empty blocks.

Actually, most of the_do_ handle empty blocks. In particular, the
normal FOR_EACH_PTR() case should handle it just fine.

The exception is, I think:

 - first_ptr_list/last_ptr_list

 - DO_PREPARE/DO_RESET

which just don't walk the pointer block list, they just end up blindly doing

        PTR_ENTRY(list, 0);

for the first entry, or

        list = list->prev;
        PTR_ENTRY(list, list->nr-1);

for the last one.

I suspect they should be fairly easy to update to just walk the list
until they hit a non-empty case (like DO_NEXT() already does, for
example).

              Linus

Re: [PATCH 0/2] be more generous with ptrlist repacking

[Christopher Li]

On Fri, Nov 18, 2016 at 1:40 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> I suspect they should be fairly easy to update to just walk the list
> until they hit a non-empty case (like DO_NEXT() already does, for
> example).

I think you are right, as always. It just need to add four while loops
into first_ptr_list/last_ptr_list/DO_PREPARE/DO_RESET.

Amount those 3 of the place should be able to share a function
(or macro) to find the next not empty entry from list head.

Ptrlist deletion happen so rare, it does not justify the complexity.

Luc, sorry about the bad suggestion.

Chris

Re: [PATCH 0/2] be more generous with ptrlist repacking

[Luc Van Oostenryck]

On Thu, Nov 17, 2016 at 09:40:20AM -0800, Linus Torvalds wrote:
> On Thu, Nov 17, 2016 at 9:25 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > The macros that do the ptrlist walking don't handle empty blocks.
> 
> Actually, most of the_do_ handle empty blocks. In particular, the
> normal FOR_EACH_PTR() case should handle it just fine.

Yes, indeed.
 
> The exception is, I think:
> 
>  - first_ptr_list/last_ptr_list
> 
>  - DO_PREPARE/DO_RESET

... 

> I suspect they should be fairly easy to update to just walk the list
> until they hit a non-empty case (like DO_NEXT() already does, for
> example).
> 
>               Linus
> --

Would something like the following be fine?

From bf7f856f95a71b931559a17c0f5144cd3a3875b5 Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Thu, 17 Nov 2016 20:59:18 +0100
Subject: [PATCH] make ptrlist walking against robust against empty blocks

Not all macros or function involved in the ptrlist walking
can handle a ptrlist containing some empty blocks.

Fix this by:
- add the proper check & looping to first & last_ptr_list().
- add a safe version of PTR_ENTRY doing the needed check & looping.
- use this safe version for DO_PREPARE() & DO_RESET()

Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
CC: Dan Carpenter <dan.carpenter@oracle.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

---
I've quickly checked it on the testsuite (and it seems to pass ;).
I'll validate this more thoroughly but I won't be able to do this
just now.
---
 ptrlist.h | 29 ++++++++++++++++++++++++++---
 1 file changed, 26 insertions(+), 3 deletions(-)

diff --git a/ptrlist.h b/ptrlist.h
index 61e159fd..d09be2f5 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -67,28 +67,51 @@ extern int linearize_ptr_list(struct ptr_list *, void **, int);
 
 static inline void *first_ptr_list(struct ptr_list *list)
 {
+	struct ptr_list *head = list;
+
 	if (!list)
 		return NULL;
+
+	while (list->nr == 0) {
+		list = list->next;
+		if (list == head)
+			return NULL;
+	}
 	return PTR_ENTRY(list, 0);
 }
 
 static inline void *last_ptr_list(struct ptr_list *list)
 {
+	struct ptr_list *head = list;
 
 	if (!list)
 		return NULL;
 	list = list->prev;
+	while (list->nr == 0) {
+		if (list == head)
+			return NULL;
+		list = list->prev;
+	}
 	return PTR_ENTRY(list, list->nr-1);
 }
 
+#define PTR_DEREF(__head, idx, PTR_ENTRY) ({						\
+	struct ptr_list *__list = __head;						\
+	while (__list && __list->nr == 0) {						\
+		__list = __list->next;							\
+		if (__list == __head)							\
+			__list = NULL;							\
+	}										\
+	__list ? PTR_ENTRY(__list, idx) : NULL;						\
+})
+
 #define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY)				\
 	do {										\
 		struct ptr_list *__head = (struct ptr_list *) (head);			\
 		struct ptr_list *__list = __head;					\
 		int __nr = 0;								\
 		CHECK_TYPE(head,ptr);							\
-		if (__head) ptr = PTR_ENTRY(__head, 0);					\
-		else ptr = NULL
+		ptr = PTR_DEREF(__head, 0, PTR_ENTRY);					\
 
 #define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY)					\
 		if (ptr) {								\
@@ -110,7 +133,7 @@ static inline void *last_ptr_list(struct ptr_list *list)
 	do {										\
 		__nr = 0;								\
 		__list = __head;							\
-		if (__head) ptr = PTR_ENTRY(__head, 0);					\
+		if (__head) ptr = PTR_DEREF(__head, 0, PTR_ENTRY);			\
 	} while (0)
 
 #define DO_FINISH(ptr, __head, __list, __nr)						\
-- 
2.10.2

Re: [PATCH 0/2] be more generous with ptrlist repacking

[Linus Torvalds]

On Thu, Nov 17, 2016 at 12:25 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Would something like the following be fine?

This looks good to me, although I didn't actually test it.  But it
looks like what I would have expected.

Some of those inlines look large enough that I wonder how much sense
they make as inlines any more, but I think that's a separate issue.

               Linus

Re: [PATCH 0/2] be more generous with ptrlist repacking

[Luc Van Oostenryck]

On Thu, Nov 17, 2016 at 02:03:05PM -0800, Linus Torvalds wrote:
> On Thu, Nov 17, 2016 at 12:25 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > Would something like the following be fine?
> 
> This looks good to me, although I didn't actually test it.  But it
> looks like what I would have expected.
> 
> Some of those inlines look large enough that I wonder how much sense
> they make as inlines any more, but I think that's a separate issue.

Oh, I absolutely agree.
What I would like is something more iterator oriented which keep track
of the head-list-nr state. I have a working prototype I made last week
but it still needs some more polishing.

Luc

Re: [PATCH 0/2] be more generous with ptrlist repacking

[Luc Van Oostenryck]

On Thu, Nov 17, 2016 at 09:25:24PM +0100, Luc Van Oostenryck wrote:
> Would something like the following be fine?
> 
...

> I've quickly checked it on the testsuite (and it seems to pass ;).
> I'll validate this more thoroughly but I won't be able to do this
> just now.

OK, I've run it on a much bigger set: a make C=2 kernel with allyesconfig,
the same tree as the test I did previously and it gives me the same result
and, of course, no crashes.
So for me the changes are OK.

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

Re: [PATCH 0/2] be more generous with ptrlist repacking

[Luc Van Oostenryck]

On Fri, Nov 18, 2016 at 01:29:19AM +0100, Luc Van Oostenryck wrote:
> On Thu, Nov 17, 2016 at 02:03:05PM -0800, Linus Torvalds wrote:
> > On Thu, Nov 17, 2016 at 12:25 PM, Luc Van Oostenryck
> > <luc.vanoostenryck@gmail.com> wrote:
> > >
> > > Would something like the following be fine?
> > 
> > This looks good to me, although I didn't actually test it.  But it
> > looks like what I would have expected.
> > 
> > Some of those inlines look large enough that I wonder how much sense
> > they make as inlines any more, but I think that's a separate issue.
> 
> Oh, I absolutely agree.
> What I would like is something more iterator oriented which keep track
> of the head-list-nr state. I have a working prototype I made last week
> but it still needs some more polishing.
> 

I've worked a bit more on this. I had a nice, clean & compact
implementation where basically all ptr_list walking was done by
something like:
	struct ptr_iter iter;
	ptr_iter_init(&iter, head);
	while ((ptr = ptr_iter_next(&iter)))
		...

Of course, still hidden under the macros which do the type checking.
This had the advantage that all the logic was in a single place.
It seemed to work well that is until I discovered that at a few places we're
storing null pointers in ptr_lists. It's thus not possible to use the
returned pointer to also check the end of list condition. The situation
is even a bit more complex because the PREPARE/NEXT_PTR_LIST() also
can't work with null pointers.

I've found a few alternative that work in all the cases but they aren't
simple & compact enough to my taste so I'll let things like they are
and maybe just sent a few cleanups later.

Luc

Re: [PATCH 0/2] be more generous with ptrlist repacking

[Christopher Li]

On Mon, Nov 28, 2016 at 1:15 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> I've worked a bit more on this. I had a nice, clean & compact
> implementation where basically all ptr_list walking was done by
> something like:
>         struct ptr_iter iter;
>         ptr_iter_init(&iter, head);
>         while ((ptr = ptr_iter_next(&iter)))
>                 ...

Last time I try that, I look at the machine code and realized that
using iter struct is not quite the same as using macro. On each function
boundary, the compiler still try to sync the data register content
into the iter structure in memory. In other words, there is no way to make the
iter variable as register, it always get sync into memory.

I did run a full kernel source check back then, did not find an observable
difference. The time difference is within the variance of each run.
Maybe due to most of the list are very short.

Chris