[PATCH RFC] Let pseudo->users loop on duplicate version of list

[PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

I found a temporary solution is simple enough.

Instead of marking the entry deleted. I just use a duplicate
version of the list->list[] when doing the loop. It will have
unwanted effect that iterator will issue some ptr are already
deleted. Other than that, it is very straight forward.

It pass the kernel compile test without issue different warnings.
It also pass the ptrlist ref checking. The ref count patch can now
complete the full kernel check without die() on it. Again no difference
in warning.

Chris


From 18453b4b920ae53f25bc389609218d97e7f583a1 Mon Sep 17 00:00:00 2001
From: Christopher Li <sparse@chrisli.org>
Date: Mon, 10 Jul 2017 07:53:21 -0700
Subject: [PATCH] Let pseudo->users loop on duplicate version of list

pseudo->users list will change during find dominator.
That cause a bug in the ptrlist because the outer loop iterator
is not award of the deletion of the entry.

Let the outer loop using a duplicate version of entry
to avoid this problem for now.

This is to fix the bug report by the ptrlist ref counting check.
With this change, the ptrlist ref counting check can complete
the kernel compile without reporting an error.

Signed-of-By: Christopher Li <sparse@chrisli.org>
---
 flow.c    |  7 ++++++-
 ptrlist.h | 17 +++++++++++++++++
 2 files changed, 23 insertions(+), 1 deletion(-)

diff --git a/flow.c b/flow.c
index fce8bde..2705448 100644
--- a/flow.c
+++ b/flow.c
@@ -730,7 +730,12 @@ multi_def:
 complex_def:
 external_visibility:
  all = 1;
- FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
+ /*
+ * FIXME: pseudo->users will have some entry deleted during looping.
+ * The loop will run on a duplicated version of the list entry for now.
+ * Should fix it properly later.
+ */
+ FOR_EACH_PTR_REVERSE_DUP(pseudo->users, pu) {
  struct instruction *insn = pu->insn;
  if (insn->opcode == OP_LOAD)
  all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
diff --git a/ptrlist.h b/ptrlist.h
index d09be2f..5299ee5 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -184,6 +184,20 @@ static inline void *last_ptr_list(struct ptr_list *list)
  ptr = PTR_ENTRY(__list,__nr); \
  do {

+#define DO_FOR_EACH_REVERSE_DUP(head, ptr, __head, __list, __dup,
__nr, PTR_ENTRY) do { \
+ struct ptr_list *__head = (struct ptr_list *) (head); \
+ struct ptr_list *__list = __head; \
+ CHECK_TYPE(head,ptr); \
+ if (__head) { \
+ do { int __nr; \
+ __list = __list->prev; \
+ __nr = __list->nr; \
+ struct ptr_list __dup; \
+ memcpy(__dup.list, __list->list, sizeof(ptr)*__nr); \
+ while (--__nr >= 0) { \
+ do { \
+ ptr = PTR_ENTRY(&__dup,__nr); \
+ do {

 #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \
  } while (0); \
@@ -231,6 +245,9 @@ static inline void *last_ptr_list(struct ptr_list *list)
 #define FOR_EACH_PTR_REVERSE(head, ptr) \
  DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)

+#define FOR_EACH_PTR_REVERSE_DUP(head, ptr) \
+ DO_FOR_EACH_REVERSE_DUP(head, ptr, __head##ptr, __list##ptr,
__dup##ptr, __nr##ptr, PTR_ENTRY)
+
 #define END_FOR_EACH_PTR_REVERSE(ptr) \
  DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)

-- 
2.9.4

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

Ping, Any taker want to review or suggest alternative
way to fix the nested loop delete bug?

I will try the mark delete approach as well.  When to pack it is the tricky
part because the function might be call at different place. e.g.
parent in a ptrlist loop already vs not in a ptrlist loop.

I am just glad the ptrlist ref count patch did not reveal more
nesting loop delete offends. This pseudo->user list and ep->bbs
are the only two occasion the patch die on.

We might get away with do not pack the pseudo->users list at all.

Chris


On Mon, Jul 10, 2017 at 8:32 AM, Christopher Li <sparse@chrisli.org> wrote:
> I found a temporary solution is simple enough.
>
> Instead of marking the entry deleted. I just use a duplicate
> version of the list->list[] when doing the loop. It will have
> unwanted effect that iterator will issue some ptr are already
> deleted. Other than that, it is very straight forward.
>
> It pass the kernel compile test without issue different warnings.
> It also pass the ptrlist ref checking. The ref count patch can now
> complete the full kernel check without die() on it. Again no difference
> in warning.
>
> Chris
>
>
> From 18453b4b920ae53f25bc389609218d97e7f583a1 Mon Sep 17 00:00:00 2001
> From: Christopher Li <sparse@chrisli.org>
> Date: Mon, 10 Jul 2017 07:53:21 -0700
> Subject: [PATCH] Let pseudo->users loop on duplicate version of list
>
> pseudo->users list will change during find dominator.
> That cause a bug in the ptrlist because the outer loop iterator
> is not award of the deletion of the entry.
>
> Let the outer loop using a duplicate version of entry
> to avoid this problem for now.
>
> This is to fix the bug report by the ptrlist ref counting check.
> With this change, the ptrlist ref counting check can complete
> the kernel compile without reporting an error.
>
> Signed-of-By: Christopher Li <sparse@chrisli.org>
> ---
>  flow.c    |  7 ++++++-
>  ptrlist.h | 17 +++++++++++++++++
>  2 files changed, 23 insertions(+), 1 deletion(-)
>
> diff --git a/flow.c b/flow.c
> index fce8bde..2705448 100644
> --- a/flow.c
> +++ b/flow.c
> @@ -730,7 +730,12 @@ multi_def:
>  complex_def:
>  external_visibility:
>   all = 1;
> - FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
> + /*
> + * FIXME: pseudo->users will have some entry deleted during looping.
> + * The loop will run on a duplicated version of the list entry for now.
> + * Should fix it properly later.
> + */
> + FOR_EACH_PTR_REVERSE_DUP(pseudo->users, pu) {
>   struct instruction *insn = pu->insn;
>   if (insn->opcode == OP_LOAD)
>   all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
> diff --git a/ptrlist.h b/ptrlist.h
> index d09be2f..5299ee5 100644
> --- a/ptrlist.h
> +++ b/ptrlist.h
> @@ -184,6 +184,20 @@ static inline void *last_ptr_list(struct ptr_list *list)
>   ptr = PTR_ENTRY(__list,__nr); \
>   do {
>
> +#define DO_FOR_EACH_REVERSE_DUP(head, ptr, __head, __list, __dup,
> __nr, PTR_ENTRY) do { \
> + struct ptr_list *__head = (struct ptr_list *) (head); \
> + struct ptr_list *__list = __head; \
> + CHECK_TYPE(head,ptr); \
> + if (__head) { \
> + do { int __nr; \
> + __list = __list->prev; \
> + __nr = __list->nr; \
> + struct ptr_list __dup; \
> + memcpy(__dup.list, __list->list, sizeof(ptr)*__nr); \
> + while (--__nr >= 0) { \
> + do { \
> + ptr = PTR_ENTRY(&__dup,__nr); \
> + do {
>
>  #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \
>   } while (0); \
> @@ -231,6 +245,9 @@ static inline void *last_ptr_list(struct ptr_list *list)
>  #define FOR_EACH_PTR_REVERSE(head, ptr) \
>   DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
>
> +#define FOR_EACH_PTR_REVERSE_DUP(head, ptr) \
> + DO_FOR_EACH_REVERSE_DUP(head, ptr, __head##ptr, __list##ptr,
> __dup##ptr, __nr##ptr, PTR_ENTRY)
> +
>  #define END_FOR_EACH_PTR_REVERSE(ptr) \
>   DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)
>
> --
> 2.9.4

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Dibyendu Majumdar]

Hi Chris,

On 11 July 2017 at 21:53, Christopher Li <sparse@chrisli.org> wrote:
> Ping, Any taker want to review or suggest alternative
> way to fix the nested loop delete bug?
>
>> Instead of marking the entry deleted. I just use a duplicate
>> version of the list->list[] when doing the loop. It will have
>> unwanted effect that iterator will issue some ptr are already
>> deleted. Other than that, it is very straight forward.
>>

I think that duplicating a list because that list is being modified is
quite a sensible thing to do. My only suggestion would be that perhaps
you could have a dup() step that is separate so that you can use the
normal iterator macro after duplicating.

Regards
Dibyendu

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Tue, Jul 11, 2017 at 2:04 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> I think that duplicating a list because that list is being modified is
> quite a sensible thing to do. My only suggestion would be that perhaps
> you could have a dup() step that is separate so that you can use the
> normal iterator macro after duplicating.

So are you suggesting some thing like this:

struct ptr_list *dup_list = NULL:
concat_ptr_list(orign_list, &dup_list);
FOR_EACH_PTR(dup_list, ptr) {
...
} END_FOR_EACH_PTR(ptr);
free_ptr_list(dup_list);

I think that should work. But it come with a price
allocating and freeing the list (otherwise it is a memory leak).

Also run slightly slower. My current way will only duplicate
the list struct one at a time. It never duplicate the full list.
It has fixed memory usage, no allocating, no duplicate of
the ->next and ->prev pointer.

So what macro do you have in mind? I think any thing modify
the duplicate list does not make sense.

On thing I can do is rename the __list into __orig, then rename
__dup into __list. Then most of the list macro using __list should
work. It also means I have to use END_FOR_EACH_PTR_DUP()
as well.


Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Dibyendu Majumdar]

Hi Chris,

On 12 July 2017 at 06:29, Christopher Li <sparse@chrisli.org> wrote:
> On Tue, Jul 11, 2017 at 2:04 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> I think that duplicating a list because that list is being modified is
>> quite a sensible thing to do. My only suggestion would be that perhaps
>> you could have a dup() step that is separate so that you can use the
>> normal iterator macro after duplicating.
>
> So are you suggesting some thing like this:
>
> struct ptr_list *dup_list = NULL:
> concat_ptr_list(orign_list, &dup_list);
> FOR_EACH_PTR(dup_list, ptr) {
> ...
> } END_FOR_EACH_PTR(ptr);
> free_ptr_list(dup_list);
>
> I think that should work. But it come with a price
> allocating and freeing the list (otherwise it is a memory leak).

Yes that is what I meant. This is a typical solution to this type of problem.

>
> Also run slightly slower. My current way will only duplicate
> the list struct one at a time. It never duplicate the full list.
> It has fixed memory usage, no allocating, no duplicate of
> the ->next and ->prev pointer.
>

Okay - but is your approach generic enough? What if there was a split
in the node that you copied? I don't have a full understanding but it
appears to be a very specific solution rather than a general one.

> So what macro do you have in mind? I think any thing modify
> the duplicate list does not make sense.
>
> On thing I can do is rename the __list into __orig, then rename
> __dup into __list. Then most of the list macro using __list should
> work. It also means I have to use END_FOR_EACH_PTR_DUP()
> as well.
>

I was just saying that you can use the standard /existing iterator
macros once you have duplicated the list.

Regards
Dibyendu

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Wed, Jul 12, 2017 at 8:56 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>>
>
> Okay - but is your approach generic enough? What if there was a split
> in the node that you copied? I don't have a full understanding but it
> appears to be a very specific solution rather than a general one.

You have a very good point. I have never thought about splitting the
node. If split the node then there will be some ptr iterate twice. Because
some node move to the next bucket and the dup node know nothing
about it. It would be a problem for the existing code as well.

My ptrlist ref count patch haven't check the split node situation.
Even Luc's suggestion for "mark and sweep" to delete the ptrlist
is not going to help with the nested loop split. I will add that check.
I don't expect new offenders but let's make sure about it.

It means it would be so much nicer if we can avoid nested loop modify at all.

> I was just saying that you can use the standard /existing iterator
> macros once you have duplicated the list.

It was not mean to a temporary fix not generic. But may be just add
a function for duplicate list is needed for long run.

We try to avoid nest loop modify, if it has to be done. Outer loop
use a duplicated list.

Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Dibyendu Majumdar]

Hi Chris,

On 12 July 2017 at 18:03, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Jul 12, 2017 at 8:56 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>>
>>
>> Okay - but is your approach generic enough? What if there was a split
>> in the node that you copied? I don't have a full understanding but it
>> appears to be a very specific solution rather than a general one.
>
> You have a very good point. I have never thought about splitting the
> node. If split the node then there will be some ptr iterate twice. Because
> some node move to the next bucket and the dup node know nothing
> about it. It would be a problem for the existing code as well.
>
> My ptrlist ref count patch haven't check the split node situation.
> Even Luc's suggestion for "mark and sweep" to delete the ptrlist
> is not going to help with the nested loop split. I will add that check.
> I don't expect new offenders but let's make sure about it.
>

I did raise this before
(http://marc.info/?l=linux-sparse&m=149943353732715&w=2) but maybe it
got lost in the other stuff.

> It means it would be so much nicer if we can avoid nested loop modify at all.
>

I agree with that - traversing a list that is also being modified by
recursive code is pretty hard to get right.

>> I was just saying that you can use the standard /existing iterator
>> macros once you have duplicated the list.
>
> It was not mean to a temporary fix not generic. But may be just add
> a function for duplicate list is needed for long run.
>
> We try to avoid nest loop modify, if it has to be done. Outer loop
> use a duplicated list.
>

Personally I think that is a reasonable approach.

Regards
Dibyendu

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Wed, Jul 12, 2017 at 11:05 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> I did raise this before
> (http://marc.info/?l=linux-sparse&m=149943353732715&w=2) but maybe it
> got lost in the other stuff.

Sorry I must miss that part. Yes. the ptrlist ref count will not able to
handle the insert and split the node. The whole idea is def the modify to
the last owner of holding the node. Insert need to split the node right there.

Even lock will not work. The inner loop guy try to get the lock and failed.
What can it do? It can't just retry because the parent is holding the lock.
It is going to be very nasty.

Any way, the patch has been updated to use a full duplicated list.
The git branch is at:
https://git.kernel.org/pub/scm/devel/sparse/sparse.git/log/?h=sparse-next-20170712

The patch follows.

Chris

From 7264a822d9d9e545152ac675fbc5b5e970ce254b Mon Sep 17 00:00:00 2001
From: Christopher Li <sparse@chrisli.org>
Date: Wed, 12 Jul 2017 14:46:50 -0700
Subject: [PATCH] Let pseudo->users loop on duplicate versin of list

pseudo->users list will change during find dominator.
That cause a bug in the ptrlist because the outer loop iterator
is not award of the deletion of the entry.

Let the outer loop using a duplicate version of entry
to avoid this problem for now.

This is to fix the bug report by the ptrlist ref counting check.
With this change, the ptrlist ref counting check can complete
the kernel compile without reporting an error.

Signed-of-By: Christopher Li <sparse@chrisli.org>
---
 flow.c | 21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)

diff --git a/flow.c b/flow.c
index fce8bde..bfe54f7 100644
--- a/flow.c
+++ b/flow.c
@@ -729,12 +729,21 @@ static void simplify_one_symbol(struct
entrypoint *ep, struct symbol *sym)
 multi_def:
 complex_def:
 external_visibility:
- all = 1;
- FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
- struct instruction *insn = pu->insn;
- if (insn->opcode == OP_LOAD)
- all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
- } END_FOR_EACH_PTR_REVERSE(pu);
+ {
+ /*
+ * find_dominating_stores() will modify the pesudo->users list.
+ * Make a duplicate copy before using it.
+ */
+ struct pseudo_user_list *users = NULL;
+ all = 1;
+ concat_user_list(pseudo->users, &users);
+ FOR_EACH_PTR_REVERSE(users, pu) {
+ struct instruction *insn = pu->insn;
+ if (insn->opcode == OP_LOAD)
+ all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
+ } END_FOR_EACH_PTR_REVERSE(pu);
+ free_ptr_list(&users);
+ }

  /* If we converted all the loads, remove the stores. They are dead */
  if (all && !mod) {
-- 
2.9.4

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Luc Van Oostenryck]

On Wed, Jul 12, 2017 at 10:27:25PM -0700, Christopher Li wrote:
> From 7264a822d9d9e545152ac675fbc5b5e970ce254b Mon Sep 17 00:00:00 2001
> From: Christopher Li <sparse@chrisli.org>
> Date: Wed, 12 Jul 2017 14:46:50 -0700
> Subject: [PATCH] Let pseudo->users loop on duplicate versin of list
> 
> pseudo->users list will change during find dominator.
> That cause a bug in the ptrlist because the outer loop iterator
> is not award of the deletion of the entry.
> 
> Let the outer loop using a duplicate version of entry
> to avoid this problem for now.

When I see this description, the first thing I think is:
"you have a problem with an object, you duplicate the object,
 not you have two problem (at least)".
In short, how you will keep coherency between the two?

So yes, without any doubts, this fixes the iteration in the outer loop
not taking correctly in account the deletion in the inner loop.

But is the code working correctly now? I don't think so.
In fact, since the outer loop is using a copy of the initial list,
now *any* changes in the list will siply be ignored by the outer loop.
- if an user is removed from the users list (for example in a
  position much further than the current position in the inner),
  previously, the inner loop will of course not have processed
  this user, while now it will process it although this user no
  more a user of this pseudo.
  It there any explanation which could explain that the current
  behaviour is correct?
- same if the inner loop add a new user, now the outer loop will
  never process this user.

To be clear, the issue I'm raising here is not about 'maybe missing
an optimisation' but well a question of applying an optimization
while the real condition are in fatc not met, and thus producings
incorrect code.

-- Luc

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Wed, Jul 19, 2017 at 2:14 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> When I see this description, the first thing I think is:
> "you have a problem with an object, you duplicate the object,
>  not you have two problem (at least)".
> In short, how you will keep coherency between the two?

We don't :-). Both the remove case and insert case has been
discussed. First of all, the ptrlist-refcount patch check for the
insert case, there is none so far. If you believe there is one,
I would like to know.

About the looping on the deleted entry. That is the very first
thing I shout in the V1 version of the patch. The thing is,
the pseudo_user have a point to instruction. If the instruction
is deleted then that instruction will have insn->bb = NULL.

Not a perfect fix. But better than the previous. Because
the for loop is actually looping on reverse order. Any delete
will cause major align problem __nr counting from the tail.

Any way, My V1 and email asking for suggestion how to fix it
About 10 days  ago. I haven't heard any thing better. If you
have other way to fix it properly, I am all for it. It is not too late
but time is running out soon.

Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Luc Van Oostenryck]

On Wed, Jul 19, 2017 at 11:42 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Jul 19, 2017 at 2:14 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> When I see this description, the first thing I think is:
>> "you have a problem with an object, you duplicate the object,
>>  not you have two problem (at least)".
>> In short, how you will keep coherency between the two?
>
> We don't :-). Both the remove case and insert case has been
> discussed. First of all, the ptrlist-refcount patch check for the
> insert case, there is none so far. If you believe there is one,
> I would like to know.

Some add_user() can be called in this loop. so it's just a question
to some input code complex enough to have an add_user()
done on the same pseudo as the one concerned in the outer
loop.

> About the looping on the deleted entry. That is the very first
> thing I shout in the V1 version of the patch. The thing is,
> the pseudo_user have a point to instruction. If the instruction
> is deleted then that instruction will have insn->bb = NULL.
>
> Not a perfect fix. But better than the previous. Because
> the for loop is actually looping on reverse order. Any delete
> will cause major align problem __nr counting from the tail.

Yes, those list delete inside iteration loops are definitively to avoid.

> Any way, My V1 and email asking for suggestion how to fix it
> About 10 days  ago. I haven't heard any thing better. If you
> have other way to fix it properly, I am all for it. It is not too late
> but time is running out soon.

I stated several times that the only real solution will be to mark the
elements as being deleted (and only effectively delete them in some
safe situations) exactly like it is done for instruction (which are probably
the type the most often deleted from lists. Trying to effectively
removing them from lists like it is currently done for the others types
would most probably fail in the most horrible ways).
It's a simple & clean solution, provably correct in *all* situations.
But I don't remember having seen any replies from you on this subject.

-- Luc

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Wed, Jul 19, 2017 at 3:51 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Some add_user() can be called in this loop. so it's just a question
> to some input code complex enough to have an add_user()
> done on the same pseudo as the one concerned in the outer
> loop.

Can you point me to a call stack that trigger the add_user()?

I have run the full kernel compile did not trigger it. The other two
nested loop delete was catches within the first 15 files or so.

> I stated several times that the only real solution will be to mark the
> elements as being deleted (and only effectively delete them in some
> safe situations) exactly like it is done for instruction (which are probably
> the type the most often deleted from lists. Trying to effectively
> removing them from lists like it is currently done for the others types
> would most probably fail in the most horrible ways).
> It's a simple & clean solution, provably correct in *all* situations.
> But I don't remember having seen any replies from you on this subject.

That is because you are away and you did not read through the email.
I did comment on it. It doesn't correct in *all* situations. We need bigger
hammer.

I locate it out for you.

http://marc.info/?l=linux-sparse&m=149987902920449&w=3
==========quote================
Even Luc's suggestion for "mark and sweep" to delete the ptrlist
is not going to help with the nested loop split. I will add that check.
I don't expect new offenders but let's make sure about it.
==========end quote=============

http://marc.info/?l=linux-sparse&m=149969288517115&w=3
=============quote===============
> I earlier suggested to instead change the way elements are 'deleted'
> (like instructions are already never removed from their list but
> just marked as deleted).

That looks simple but it has hidden complications as well. The issue is that
we need to find out which list need this kind of special treatment. Who is
the outer loop. If the same function can be both call as the outer
loop and inner
loop then it is complicate to decide when it should do the finalize.
There is also
the price to pay for walking the list twice which does not exist if nested loop
can be avoided.

=============end quote==============


Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Luc Van Oostenryck]

On Thu, Jul 20, 2017 at 4:34 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Jul 19, 2017 at 3:51 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>>
>> Some add_user() can be called in this loop. so it's just a question
>> to some input code complex enough to have an add_user()
>> done on the same pseudo as the one concerned in the outer
>> loop.
>
> Can you point me to a call stack that trigger the add_user()?
>
> I have run the full kernel compile did not trigger it. The other two
> nested loop delete was catches within the first 15 files or so.
>
>> I stated several times that the only real solution will be to mark the
>> elements as being deleted (and only effectively delete them in some
>> safe situations) exactly like it is done for instruction (which are probably
>> the type the most often deleted from lists. Trying to effectively
>> removing them from lists like it is currently done for the others types
>> would most probably fail in the most horrible ways).
>> It's a simple & clean solution, provably correct in *all* situations.
>> But I don't remember having seen any replies from you on this subject.
>
> That is because you are away and you did not read through the email.
> I did comment on it. It doesn't correct in *all* situations. We need bigger
> hammer.
>
> I locate it out for you.
>
> http://marc.info/?l=linux-sparse&m=149987902920449&w=3
> ==========quote================
> Even Luc's suggestion for "mark and sweep" to delete the ptrlist
> is not going to help with the nested loop split. I will add that check.
> I don't expect new offenders but let's make sure about it.
> ==========end quote=============

I don't think you understood what I meant.

> http://marc.info/?l=linux-sparse&m=149969288517115&w=3
> =============quote===============
>> I earlier suggested to instead change the way elements are 'deleted'
>> (like instructions are already never removed from their list but
>> just marked as deleted).
>
> That looks simple but it has hidden complications as well. The issue is that
> we need to find out which list need this kind of special treatment.

It's very simple: *all* lists need this 'treatement'.

> Who is
> the outer loop. If the same function can be both call as the outer
> loop and inner
> loop then it is complicate to decide when it should do the finalize.
> There is also
> the price to pay for walking the list twice which does not exist if nested loop
> can be avoided.

Walking twice?

In general, we can't avoid nested loops.

Look at what is done currently with instructions: when we want to 'delete'
an instruction we simply set it's ->bb to NULL which basically means:
"for now, please just ignore this instruction". In other words, instructions
are *never* removed from their lists, they are simply marked as being
deleted. You don't need to know if you're in a nested loop or not.
You will never have the problem with deletion on nested list walking
because they are never removed from the lists.

Why do you think it has been done so?
Do you think it's bad and it would be better to effectively remove
instructions from their lists like others types?
Do you think it would be good or even possible to avoid having
nested loops of instructions?
I don't think so.

-- Luc

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Wed, Aug 2, 2017 at 7:44 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> http://marc.info/?l=linux-sparse&m=149987902920449&w=3
>> ==========quote================
>> Even Luc's suggestion for "mark and sweep" to delete the ptrlist
>> is not going to help with the nested loop split. I will add that check.
>> I don't expect new offenders but let's make sure about it.
>> ==========end quote=============
>
> I don't think you understood what I meant.

I don't think so. Can you please explain?

Let's give it an example on the insert case.

The outer loop is doing

FOR_EACH_PTR_REVERSE(bbs, bb) {
             /* the outer loop macro is holding the
               __nr = list->nr;
                __list = list;
                It is using __nr as the slot number point to the current slot.
              */

              ...
              add_bb(bbs, new_bb);
              /* now list->list[] array has been split.
                   list->nr has less entry.
                __nr does not know about that. it is not  going to
point to the right element */

              ...
} END_FOR_EACH_PTR_REVERSE(bb);

The key insight here is that, we need to preserv list->list[] array not changed,
also list->nr not changed for make reverse ptr loop work.

For the delete case, set bb->ep = NULL; marking the bb dead works.
It does not touch list->list[] nor list->nr. As long as you skip the bb which
bb->ep == NULL you are fine.

Let's look at the insert case.

regardless how you set bb->ep. When you insert the new bb into the list,
the list split will modify list->list[] and list->nr. There is no way
to defer that.
It *will* mess up with the outer loop __nr slot pointer.

How does your purpose method handle this case?
Please explain. I am listening.

>
>> http://marc.info/?l=linux-sparse&m=149969288517115&w=3
>> =============quote===============
>>> I earlier suggested to instead change the way elements are 'deleted'
>>> (like instructions are already never removed from their list but
>>> just marked as deleted).
>>
>> That looks simple but it has hidden complications as well. The issue is that
>> we need to find out which list need this kind of special treatment.
>
> It's very simple: *all* lists need this 'treatement'.

I mean you need to identify the caller who is the outer loop, the outer
loop caller need to do the list packing. That is what I mean by
special treatment.
If packing inside the inner loop, that is the problem we try to avoid.

That is assume we still pack list. If we never pack list, then it is
not a problem
here per say. But we still need to deal with the insert problem.

>
> Walking twice?

I am more worry about the incorrect behavior on insert and packing
than walk twice.

>
> In general, we can't avoid nested loops.

I am thinking breaking the recursive calling into work queue.
Then there is no nest loop. If you known why that will not work,
please point out. I do assume I can convert the recursive call
to non recursive using work queue. Again I haven't dig very deep yet.

>
> Look at what is done currently with instructions: when we want to 'delete'
> an instruction we simply set it's ->bb to NULL which basically means:
> "for now, please just ignore this instruction". In other words, instructions
> are *never* removed from their lists, they are simply marked as being
> deleted. You don't need to know if you're in a nested loop or not.
> You will never have the problem with deletion on nested list walking
> because they are never removed from the lists.

Right, but does not help the insert case.


>
> Why do you think it has been done so?
> Do you think it's bad and it would be better to effectively remove
> instructions from their lists like others types?
> Do you think it would be good or even possible to avoid having
> nested loops of instructions?
> I don't think so.

Please, I *do* understand why it is done that way. I am trying to point out that
did not solve all the problem if inner function want to modify the list.
aka insert. That seems to be the point haven't come across to you.

If you know how to solve the insert case, please explain.

Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Luc Van Oostenryck]

On Wed, Aug 02, 2017 at 08:50:14PM -0400, Christopher Li wrote:
> On Wed, Aug 2, 2017 at 7:44 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >> http://marc.info/?l=linux-sparse&m=149987902920449&w=3
> >> ==========quote================
> >> Even Luc's suggestion for "mark and sweep" to delete the ptrlist
> >> is not going to help with the nested loop split. I will add that check.
> >> I don't expect new offenders but let's make sure about it.
> >> ==========end quote=============
> >
> > I don't think you understood what I meant.
> 
> I don't think so. Can you please explain?
> 
> Let's give it an example on the insert case.

Yes yes.
I already said the 7th July that reverse list walking and list
splitting will be another beast but the subject of this patch
is the *deletion* of elements from lists.
 
> > It's very simple: *all* lists need this 'treatement'.
> 
> I mean you need to identify the caller who is the outer loop, the outer
> loop caller need to do the list packing. That is what I mean by
> special treatment.
> If packing inside the inner loop, that is the problem we try to avoid.
> 
> That is assume we still pack list. If we never pack list, then it is
> not a problem
> here per say.

We don't have to pack all lists.
The ones that we pack can be packed at some specific place/moment.

> >
> > Walking twice?
> 
> I am more worry about the incorrect behavior on insert and packing
> than walk twice.
> 
> >
> > In general, we can't avoid nested loops.
> 
> I am thinking breaking the recursive calling into work queue.
> Then there is no nest loop. If you known why that will not work,
> please point out. I do assume I can convert the recursive call
> to non recursive using work queue. Again I haven't dig very deep yet.

Oh, I'm sure that using a work queue will work in some case.
I'm even sure that it's a good idea for some case. But I don't
think it will solve all problems because:
- some nested loops will remains
- it will be hard to avoid nested loops because we generaly don't
  know if we're nested or not. The mains ep - bbs - insns loop
  is obvious but what for other loops?
- using a work list is not without problems either. For example,
  we'll have no/few control over when things are effectively be
  done. Sometimes it will be fine, sometimes it won't be acceptable.
  If during some operation, we must delete *this* element or
  add a new element *here in the list* just pushing something
  on a work list and saying "OK, it will be done some time later"
  won't solve the problem, won't keep things coherent, ...

> >
> > Look at what is done currently with instructions: when we want to 'delete'
> > an instruction we simply set it's ->bb to NULL which basically means:
> > "for now, please just ignore this instruction". In other words, instructions
> > are *never* removed from their lists, they are simply marked as being
> > deleted. You don't need to know if you're in a nested loop or not.
> > You will never have the problem with deletion on nested list walking
> > because they are never removed from the lists.
> 
> Right, but does not help the insert case.

Sure, it's another problem.
 
> > Why do you think it has been done so?
> > Do you think it's bad and it would be better to effectively remove
> > instructions from their lists like others types?
> > Do you think it would be good or even possible to avoid having
> > nested loops of instructions?
> > I don't think so.
> 
> Please, I *do* understand why it is done that way. I am trying to point out that
> did not solve all the problem if inner function want to modify the list.
> aka insert. That seems to be the point haven't come across to you.
> 
> If you know how to solve the insert case, please explain.

Well, it's not as if saying "let's do everything with work queues"
solve anything in itself. It's a idea that would need lot of patches
and big changes in a lot of code to show if it's up to its promise
(and as I explain shortly here above, I have reasons to believe
that it won't be possible to solve all the list problems with it).

For the reverse walking and insert, I haven't thought much about
it yet. I won't be surprised that it will need some change in the
ptrlist struct & macros.
Maybe it's an operation that is not common enough that trying to ban
it wouldn't be a big constraint on existing & future code.
If all the ones we have go away once everything have been converted
to using work queues then fine, but what if they don't, what if
we can't convert everything to using work queues?

On the other hand, avoiding the problem of list deletion (which seems
to be an operation much more common than reverse & insert) by marking
deleted elements is something that can be done easily, with minimal
code impact and that *will* solve *all* problems with list deletion
(but yes, only list deletion).

-- Luc

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Thu, Aug 3, 2017 at 6:18 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Wed, Aug 02, 2017 at 08:50:14PM -0400, Christopher Li wrote:
>> On Wed, Aug 2, 2017 at 7:44 PM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>> >> http://marc.info/?l=linux-sparse&m=149987902920449&w=3
>> >> ==========quote================
>> >> Even Luc's suggestion for "mark and sweep" to delete the ptrlist
>> >> is not going to help with the nested loop split. I will add that check.
>> >> I don't expect new offenders but let's make sure about it.
>> >> ==========end quote=============
>> >
>> > I don't think you understood what I meant.
>>
>> I don't think so. Can you please explain?
>>
>> Let's give it an example on the insert case.
>
> Yes yes.
> I already said the 7th July that reverse list walking and list
> splitting will be another beast but the subject of this patch
> is the *deletion* of elements from lists.

The text you quote from me clearing is discussing node split here.
" nested loop *split*". Even though the title of the email was original
about delete. The discussion expand to split because I haven't realize
that is a problem earlier. I consider this as the same category delete.
It is basically looping and modify the list at the same time.
I want to find a solution to solve this both situations.

> We don't have to pack all lists.
> The ones that we pack can be packed at some specific place/moment.

Right, we need to make sure the packing *never* call from the same list
looping body. There is no easy way to find out this did not happen.

>> I am thinking breaking the recursive calling into work queue.
>> Then there is no nest loop. If you known why that will not work,
>> please point out. I do assume I can convert the recursive call
>> to non recursive using work queue. Again I haven't dig very deep yet.
>
> Oh, I'm sure that using a work queue will work in some case.
> I'm even sure that it's a good idea for some case. But I don't
> think it will solve all problems because:
> - some nested loops will remains

Can you give an example what nest looping will have to remain.

Converting recursive call into work queue without recursive
is pretty stander algorithm. In theory, as long as you defer
the inner loop calling into the work queue. It can always
avoid the nest looping. In the extreme case you can think
the work queue holding a copy of the list and move the inner
loop body to the outer work queue.

In reality, we don't want to move every thing into work queue.
I think the loop just observe. Defer the modification into work queue
is relative conceptually clean.

> - it will be hard to avoid nested loops because we generaly don't
>   know if we're nested or not. The mains ep - bbs - insns loop

We don't mind nested looping as long as we don't modify it.
We can always know that we are about to modify the bb or insns.
That is a good place to move to the work queue.

My mental model is that, have the detect and modify phase.
The detect phase do all the looping as needed. Look but don't touch.
The modify request is push into work queue and execute after the
loop has been done.

>   is obvious but what for other loops?
> - using a work list is not without problems either. For example,
>   we'll have no/few control over when things are effectively be
>   done. Sometimes it will be fine, sometimes it won't be acceptable.
>   If during some operation, we must delete *this* element or
>   add a new element *here in the list* just pushing something
>   on a work list and saying "OK, it will be done some time later"
>   won't solve the problem, won't keep things coherent, ...

That usually means you have some other things need to defer as well.
You don't have to do it on the spot on the loop. Have a work queue is
actually easier to reason and enforce such ordering.
You can consider our current CSE loop as a poor form of work queue.
It just have one bit of flag for each stage. It does not point to which
insn need to be changed.

You can think it this way, the delete mark and sweep is just another way
to defer the delete as well. In the extreme case, we defer to never delete.

>>
>> If you know how to solve the insert case, please explain.
>
> Well, it's not as if saying "let's do everything with work queues"
> solve anything in itself. It's a idea that would need lot of patches
> and big changes in a lot of code to show if it's up to its promise
> (and as I explain shortly here above, I have reasons to believe
> that it won't be possible to solve all the list problems with it).

Right. It need a lot of discussion and patch experiment. Definitely
after the release.

As I said in the other email. If you have better  patch to solve the
nest loop delete on pseudo list for RC5. Feel free to replace the
current one on sparse. I am aware of the current solution is not perfect.
It can iterate on deleted ptr entry.

>
> For the reverse walking and insert, I haven't thought much about
> it yet. I won't be surprised that it will need some change in the
> ptrlist struct & macros.
> Maybe it's an operation that is not common enough that trying to ban
> it wouldn't be a big constraint on existing & future code.

I think that is let the tail wag the dog. Plus, I can demonstrate,
node split in FOR_EACH_PTR() can also have incorrect behavior as well.
Basically node split will change list->list[] and list->nr. That can have
impact on forward iteration too. The reverse one is just more obvious.


> If all the ones we have go away once everything have been converted
> to using work queues then fine, but what if they don't, what if
> we can't convert everything to using work queues?

We will have to use bigger hammer.  In short, it is going to be ugly.
e.g. have the list node has ref count and a pending change single list.

>
> On the other hand, avoiding the problem of list deletion (which seems
> to be an operation much more common than reverse & insert) by marking
> deleted elements is something that can be done easily, with minimal
> code impact and that *will* solve *all* problems with list deletion
> (but yes, only list deletion).

Yes, I consider that as a short term thing until we find a better way to handle
more general modification including insert.

Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Luc Van Oostenryck]

On Thu, Aug 03, 2017 at 07:48:59PM -0400, Christopher Li wrote:
> On Thu, Aug 3, 2017 at 6:18 AM, Luc Van Oostenryck wrote:
> > We don't have to pack all lists.
> > The ones that we pack can be packed at some specific place/moment.
> 
> Right, we need to make sure the packing *never* call from the same list
> looping body. There is no easy way to find out this did not happen.
> 
> >> I am thinking breaking the recursive calling into work queue.
> >> Then there is no nest loop. If you known why that will not work,
> >> please point out. I do assume I can convert the recursive call
> >> to non recursive using work queue. Again I haven't dig very deep yet.
> >
> > Oh, I'm sure that using a work queue will work in some case.
> > I'm even sure that it's a good idea for some case. But I don't
> > think it will solve all problems because:
> > - some nested loops will remains
> 
> Can you give an example what nest looping will have to remain.

Can you give the assurance that none will remains? 

I said "I think that ..." and of course, I have reasons to
think so. It was explained here under.

> Converting recursive call into work queue without recursive
> is pretty stander algorithm. In theory, as long as you defer
> the inner loop calling into the work queue. It can always
> avoid the nest looping. In the extreme case you can think
> the work queue holding a copy of the list and move the inner
> loop body to the outer work queue.

*standard algorithm*, *in theory*, ...
 
> In reality, we don't want to move every thing into work queue.
> I think the loop just observe. Defer the modification into work queue
> is relative conceptually clean.
> 
> > - it will be hard to avoid nested loops because we generaly don't
> >   know if we're nested or not. The mains ep - bbs - insns loop
> 
> We don't mind nested looping as long as we don't modify it.
> We can always know that we are about to modify the bb or insns.
> That is a good place to move to the work queue.
> 
> My mental model is that, have the detect and modify phase.
> The detect phase do all the looping as needed. Look but don't touch.
> The modify request is push into work queue and execute after the
> loop has been done.
> 
> >   is obvious but what for other loops?
> > - using a work list is not without problems either. For example,
> >   we'll have no/few control over when things are effectively be
> >   done. Sometimes it will be fine, sometimes it won't be acceptable.
> >   If during some operation, we must delete *this* element or
> >   add a new element *here in the list* just pushing something
> >   on a work list and saying "OK, it will be done some time later"
> >   won't solve the problem, won't keep things coherent, ...
> 
> That usually means you have some other things need to defer as well.
> You don't have to do it on the spot on the loop. Have a work queue is
> actually easier to reason and enforce such ordering.

You have all the advantages to decouple things and
you have all the disadvantges to have decoupled things.
It's not a B&W thing.

> > Well, it's not as if saying "let's do everything with work queues"
> > solve anything in itself. It's a idea that would need lot of patches
> > and big changes in a lot of code to show if it's up to its promise
> > (and as I explain shortly here above, I have reasons to believe
> > that it won't be possible to solve all the list problems with it).
> 
> Right. It need a lot of discussion and patch experiment. Definitely
> after the release.

I think you very seriously underestimate the amount of work that will
need to be done.
 
> As I said in the other email. If you have better  patch to solve the
> nest loop delete on pseudo list for RC5. Feel free to replace the
> current one on sparse. I am aware of the current solution is not perfect.
> It can iterate on deleted ptr entry.

I just send a patch.
It's not very pretty and is only lightly tested but IMO it's vastly
superior to the duplication of list.

> > For the reverse walking and insert, I haven't thought much about
> > it yet. I won't be surprised that it will need some change in the
> > ptrlist struct & macros.
> > Maybe it's an operation that is not common enough that trying to ban
> > it wouldn't be a big constraint on existing & future code.
> 
> I think that is let the tail wag the dog. Plus, I can demonstrate,
> node split in FOR_EACH_PTR() can also have incorrect behavior as well.

Yes yes, we know that since the beginning.

> > If all the ones we have go away once everything have been converted
> > to using work queues then fine, but what if they don't, what if
> > we can't convert everything to using work queues?
> 
> We will have to use bigger hammer.  In short, it is going to be ugly.
> e.g. have the list node has ref count and a pending change single list.

Other solutions exist :)
 
> > On the other hand, avoiding the problem of list deletion (which seems
> > to be an operation much more common than reverse & insert) by marking
> > deleted elements is something that can be done easily, with minimal
> > code impact and that *will* solve *all* problems with list deletion
> > (but yes, only list deletion).
> 
> Yes, I consider that as a short term thing until we find a better way to handle
> more general modification including insert.

Good to hear that.

-- Luc

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Thu, Aug 3, 2017 at 8:41 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>>
>> Can you give an example what nest looping will have to remain.
>
> Can you give the assurance that none will remains?

I can have the ptr ref count patch to check if such thing
happen. But I am sure that is not what you are asking :-)

If you follow the observe and modify model. Put the modify
stage on the outer loop. Modify only one thing at  a time.
Then it is easy to reason weather "nest loop modify" exist.

What you are asking in more general setting is not going to
have trivial answer any way. It is equivalent of the truing halting
problem.

On the other hand, if you want to disprove this, you only need
one counter example.


>> Converting recursive call into work queue without recursive
>> is pretty stander algorithm. In theory, as long as you defer
>> the inner loop calling into the work queue. It can always
>> avoid the nest looping. In the extreme case you can think
>> the work queue holding a copy of the list and move the inner
>> loop body to the outer work queue.
>
> *standard algorithm*, *in theory*, ...

I am actually don't worry about weather it can be done or not.
I am sure you don't need me to google converting recursion
to iteration for you.

The question is weather it can be done on sparse cleanly.
It is hard to say without trying.


> You have all the advantages to decouple things and
> you have all the disadvantges to have decoupled things.
> It's not a B&W thing.

It is a white-gray-black thing if you know what I mean :-)
Black is the terminate condition.

>> > Well, it's not as if saying "let's do everything with work queues"
>> > solve anything in itself. It's a idea that would need lot of patches
>> > and big changes in a lot of code to show if it's up to its promise
>> > (and as I explain shortly here above, I have reasons to believe
>> > that it won't be possible to solve all the list problems with it).
>>
>> Right. It need a lot of discussion and patch experiment. Definitely
>> after the release.
>
> I think you very seriously underestimate the amount of work that will
> need to be done.

I realize there will be a lot of change. But actually sparse will need ssa
version of the dead code removal (correctness) and ssa version of constant
propagation any way. (performance, current we scan the whole insn list
to find out
optimization opportunity). A lot of similar algorithm already using work
queue. Some rewrites is expected as far as I can tell.

> I just send a patch.
> It's not very pretty and is only lightly tested but IMO it's vastly
> superior to the duplication of list.

I haven't see it. I saw there is an constant expression patch on the
mailing list.

>> I think that is let the tail wag the dog. Plus, I can demonstrate,
>> node split in FOR_EACH_PTR() can also have incorrect behavior as well.
>
> Yes yes, we know that since the beginning.

Then why ban reverse ptr loop? It is not going to help avoid the bad
situation.

>> We will have to use bigger hammer.  In short, it is going to be ugly.
>> e.g. have the list node has ref count and a pending change single list.
>
> Other solutions exist :)

Yes, idea and patch welcome.

Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Luc Van Oostenryck]

On Thu, Aug 03, 2017 at 10:22:34PM -0400, Christopher Li wrote:
> On Thu, Aug 3, 2017 at 8:41 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >>
> >> Can you give an example what nest looping will have to remain.
> >
> > Can you give the assurance that none will remains?
> 
> I can have the ptr ref count patch to check if such thing
> happen. But I am sure that is not what you are asking :-)

It was a rethorical question as a reponse to your own question
because your own asking to show something while we're talking
design and potentiality doesn't help at all.

> >> Converting recursive call into work queue without recursive
> >> is pretty stander algorithm. In theory, as long as you defer
> >> the inner loop calling into the work queue. It can always
> >> avoid the nest looping. In the extreme case you can think
> >> the work queue holding a copy of the list and move the inner
> >> loop body to the outer work queue.
> >
> > *standard algorithm*, *in theory*, ...
> 
> I am actually don't worry about weather it can be done or not.
> I am sure you don't need me to google converting recursion
> to iteration for you.

1) Converting a recursive algo to an iterative one is not always
   a good solution, for example the iterative one can be much
   more complex/less elegant. You may also need more memory
   (because you often need to store additional info).
   A typical example is searching in a tree: it can be done
   with iteration but it's generaly not done because the
   recursive version is so much simpler & elegant (and probably
   efficient too).
2) Converting something to a work queue is not the same as
   converting recursion to iteration anyway.
   Recursion vs. iteration is something about how walking through
   a data structure. Using a work queue is about how/when doing an
   operation on an object.

An example among other of complications you can have when converting
to work queue is something like:
Imagine you're iterating through a list of instruction checking/
searching after something. If found, you want to do an operation
on the instruction just found.
Sound like something for a work queue, right? Just put the
object you found in the work queue and let do the operation later.
Now what if the operation is about inserting another instruction
just before the one just found (like done when adding death notes)?
- if you do it immediatly, you have the context of the instruction
  and inserting the death notes is easy/cheap
- if you do the insertion later when processing the work queue
  you won't have anymore the context of the instruction
  and to insert the death note you will first have to 
  search after it (to have the context back) before you will
  be able to do the insertion and this search will cost you.

It's just an example but there is a whole class of similar situations.
Delaying thing by moving it to a work queue will also have negative
impact on cache (but in a way, it's also a problem of having lost the
context).

And again, I'm not telling that using workqueue is never a good solution,
I'm saying that most probably it won't always be a good solution.

-- Luc

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Fri, Aug 4, 2017 at 6:38 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> It was a rethorical question as a reponse to your own question
> because your own asking to show something while we're talking
> design and potentiality doesn't help at all.

That is exactly the feeling I am getting from you. You said some thing
might not work. I want to find out exactly what do you have in mind might
not work.  Otherwise the conversion is base on doubt is not very
useful. I want details. This goes both ways. You can also ask me to clarify
more details on certain things in my mental model.
>
> 1) Converting a recursive algo to an iterative one is not always
>    a good solution, for example the iterative one can be much
>    more complex/less elegant. You may also need more memory
>    (because you often need to store additional info).
>    A typical example is searching in a tree: it can be done
>    with iteration but it's generaly not done because the
>    recursive version is so much simpler & elegant (and probably
>    efficient too).

In my observe and modify model, the traverse of a tree can use
recursive, even on the same ptrlist. It is the modify get deferred.
I think I mention that observe and modify in previous email already.
So what you are describing above is not a good example to against it.

> 2) Converting something to a work queue is not the same as
>    converting recursion to iteration anyway.
>    Recursion vs. iteration is something about how walking through
>    a data structure. Using a work queue is about how/when doing an
>    operation on an object.

You walk the graph to do some thing. That is given. Nobody walk the graph
for the sake of just walking the graph. The optimize can be model
as an algorithm walk the graph and make modification of the graph.
Is that a fair statement?

>
> An example among other of complications you can have when converting
> to work queue is something like:
> Imagine you're iterating through a list of instruction checking/
> searching after something. If found, you want to do an operation
> on the instruction just found.

Now we are talking.

> Sound like something for a work queue, right? Just put the
> object you found in the work queue and let do the operation later.
> Now what if the operation is about inserting another instruction
> just before the one just found (like done when adding death notes)?
> - if you do it immediatly, you have the context of the instruction
>   and inserting the death notes is easy/cheap

Here you make some assumption that you can't save the context of
the instruction in the work queue. That is not necessary true. In
my mental model, the work queue will contain the context of what
needs to be done, e.g. the pointer to the instruct. Other context
if needed. I want to know more about what context you can't save.

BTW, most of the context can be found on the graph does not
need to save in to work queue.

Take simplify_branch_branch for example, when you know this
instruction should be simplified, there is very little information
need to be save in the work queue. Basically we can start with
call arguments to rewrite_branch(), go from there.

> - if you do the insertion later when processing the work queue
>   you won't have anymore the context of the instruction
>   and to insert the death note you will first have to
>   search after it (to have the context back) before you will
>   be able to do the insertion and this search will cost you.

Again, I don't have a clear picture of what context you are talking
about. Please clarify. If it is the instruction before this instruction,
I can't image why I need it. If really need it I can still cache it or
search it in the bb->insns list.

BTW, my impression is that, the algorithm "constant propagation using ssa"
is such an example what you are describing here. In the constant
propagation, you first find the instruction that use constant.
Then you find out if that instruction can be simplify as constant.
Next thing is put the instruction using of this simplify instruction result
into the queue to see if they can be simplify as well.

It is actually a lot better than our current approach to rescan the
whole instruction list just to find out, oh, we got some new instruction
have constant input now (due to last round constant propagation).

> It's just an example but there is a whole class of similar situations.
> Delaying thing by moving it to a work queue will also have negative
> impact on cache (but in a way, it's also a problem of having lost the
> context).

Caching, maybe. But I don't think caching is a strong point to against it.
I am just a system guy playing catch up game on compiler designs. The more
I read, the more I find out using work queue is a very common
thing amount those classic optimization algorithms.

> And again, I'm not telling that using workqueue is never a good solution,
> I'm saying that most probably it won't always be a good solution.

My reading is that, "I have doubt but I can't articulate precisely why it
is the case." Fill in more detail we can have more discussion.

Granted, no algorithm is *always" a good solution to all problem.
As I express in my previous email, I have no doubt this can be done.
The question is weather it can be done *clean* enough for sparse.

When we introduce "dead code elimination using ssa", work queue like
frame work will be needed any way.

Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Luc Van Oostenryck]

On Fri, Aug 04, 2017 at 10:48:35AM -0400, Christopher Li wrote:
> On Fri, Aug 4, 2017 at 6:38 AM, Luc Van Oostenryck wrote:
> > It was a rethorical question as a reponse to your own question
> > because your own asking to show something while we're talking
> > design and potentiality doesn't help at all.
> 
> That is exactly the feeling I am getting from you. You said some thing
> might not work. I want to find out exactly what do you have in mind might
> not work.  Otherwise the conversion is base on doubt is not very
> useful.

Replace 'doubt' by 'warning' and it give already another sense to it.
My whole message has always been the same: "Warning, it's not so easy
or obvious and I have reasons to think that it won't always be possible
or desirable (so it may be good to also think about alternative or to
somehow accept thet idea that maybe not all cases will be solved the
same way".

> I want details. This goes both ways. You can also ask me to clarify
> more details on certain things in my mental model.

You can ask details about an existing implementation, you can ask
details about some idea already well elaborated. 
You can't ask details about something that by nature have not yet details,
but I have already tried to give you all sort of indices that would
give some matter to think about.

> > 1) Converting a recursive algo to an iterative one is not always
> >    a good solution, for example the iterative one can be much
> >    more complex/less elegant. You may also need more memory
> >    (because you often need to store additional info).
> >    A typical example is searching in a tree: it can be done
> >    with iteration but it's generaly not done because the
> >    recursive version is so much simpler & elegant (and probably
> >    efficient too).
> 
> In my observe and modify model, the traverse of a tree can use
> recursive, even on the same ptrlist.

When you're searching in a (binary) tree, at some point you will need
to backtrack, to return to some previous branching point. The usual
way to do that is to use recursion and the branching point is
implicitely stored in the stack. You can do the same without recursion,
without using the call stack but then you need to store info about the
branching point.
It's an example that this sort of changes is no for free.

> > 2) Converting something to a work queue is not the same as
> >    converting recursion to iteration anyway.
> >    Recursion vs. iteration is something about how walking through
> >    a data structure. Using a work queue is about how/when doing an
> >    operation on an object.
> 
> You walk the graph to do some thing. That is given. Nobody walk the graph
> for the sake of just walking the graph. The optimize can be model
> as an algorithm walk the graph and make modification of the graph.
> Is that a fair statement?

Sorry, I don't understand what you mean. 

> > An example among other of complications you can have when converting
> > to work queue is something like:
> > Imagine you're iterating through a list of instruction checking/
> > searching after something. If found, you want to do an operation
> > on the instruction just found.
> 
> Now we are talking.
> 
> > Sound like something for a work queue, right? Just put the
> > object you found in the work queue and let do the operation later.
> > Now what if the operation is about inserting another instruction
> > just before the one just found (like done when adding death notes)?
> > - if you do it immediatly, you have the context of the instruction
> >   and inserting the death notes is easy/cheap
> 
> Here you make some assumption that you can't save the context of
> the instruction in the work queue.

No, I don't make such assumption, it's an example showing that not
doing things there may have a cost. Saving the context is such a cost.

> That is not necessary true. In
> my mental model, the work queue will contain the context of what
> needs to be done, e.g. the pointer to the instruct. Other context
> if needed. I want to know more about what context you can't save.

I never said you can't save context.
On the contrary I've said that you'll most probably have to store
some context to be able to do things in a deferred way and this
will have a cost (and I use here the word 'context' in a very general
abstract meaning).

> BTW, most of the context can be found on the graph does not
> need to save in to work queue.
> 
> Take simplify_branch_branch for example, when you know this
> instruction should be simplified, there is very little information
> need to be save in the work queue.

Absolutely, in this example yes.
In some others examples, it is less so.

> > - if you do the insertion later when processing the work queue
> >   you won't have anymore the context of the instruction
> >   and to insert the death note you will first have to
> >   search after it (to have the context back) before you will
> >   be able to do the insertion and this search will cost you.
> 
> Again, I don't have a clear picture of what context you are talking
> about.

You have an instruction and you need to insert another instruction
in front of it. If you do that while you was searching after this
instruction, it's very easy because you have the head-list-nr trio
implicitely available via the ptrlist macros. This trio is here
the context you need in order to efficiently insert an instruction
in front ot it.

Now, for some reasons you want to defer this instruction.
What will you put in the work queue?
- the pointer to the instruction?
  then to insert you will need to search again in the list until
  you found the instruction. At this point you will have back
  the context needed to do the insertion but you had to do a search.
- the pointer to where the instruction stored in the list?
  then you can easily exchange this instruction with another one
  but how will this be usefull to the insertion? Well sure,
  with the pointer you can get back the original head-list-nr
  but is this usefull here? If you store somewhere the instruction
  pointer pointer, in practice that mean that the list that contain
  it become immutable (presumably you also hold pointers for the
  neighbour instructions). The only thing that can work at this point
  is a normal liked list, nor the block-based ptrlist.
  Is that a problem? Maybe, maybe not much.

> Please clarify. If it is the instruction before this instruction,
> I can't image why I need it. If really need it I can still cache it or
> search it in the bb->insns list.
> 
> BTW, my impression is that, the algorithm "constant propagation using ssa"
> is such an example what you are describing here. In the constant
> propagation, you first find the instruction that use constant.
> Then you find out if that instruction can be simplify as constant.
> Next thing is put the instruction using of this simplify instruction result
> into the queue to see if they can be simplify as well.

No, because in this case each instruction is still independend, you 
don't need to know anything about the surrounding instructions.
So it's a case where it should be easy to convert it.
The example for the deathnotes insertion is not like this.

> > It's just an example but there is a whole class of similar situations.
> > Delaying thing by moving it to a work queue will also have negative
> > impact on cache (but in a way, it's also a problem of having lost the
> > context).
> 
> Caching, maybe. But I don't think caching is a strong point to against it.
> I am just a system guy playing catch up game on compiler designs. The more
> I read, the more I find out using work queue is a very common
> thing amount those classic optimization algorithms.
> 
> > And again, I'm not telling that using workqueue is never a good solution,
> > I'm saying that most probably it won't always be a good solution.
> 
> My reading is that, "I have doubt but I can't articulate precisely why it
> is the case." Fill in more detail we can have more discussion.

If by "I have doubt" you understand "I have doubt about using it
systematically to avoid problems with nested lists", you would be
quite close. If you mean instead "I have doubt about using
it preferably (for cleanless and effective solution to avoid problems
with nested lists" you would be very wrong.

> Granted, no algorithm is *always" a good solution to all problem.
> As I express in my previous email, I have no doubt this can be done.

You have no doubts that it can be done everywhere in sparse to avoid
problems with nested lists or you have no doubts that it can be
done at least in some or most case?

Like I have already told since the beginning, I have doubts about doing
it everywhere and I have already explained why (or at least tried to).

-- Luc

Fwd: [PATCH] mark pseudo user as deleted instead of removing them

[Christopher Li]

Luc mean to send this to the mailing list as well.

Here we go.

Chris


---------- Forwarded message ----------
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Thu, Aug 3, 2017 at 8:22 PM
Subject: [PATCH] mark pseudo user as deleted instead of removing them
To: Christopher Li <sparse@chrisli.org>
Cc: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>


For discussion only.

This atch is also available in the git repository at:

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

----------------------------------------------------------------
Luc Van Oostenryck (1):
      mark pseudo user as deleted instead of removing them

 flow.c      | 28 ++++++++++++++++++++++------
 linearize.c |  2 ++
 memops.c    |  5 ++++-
 ptrlist.c   | 21 +++++++++++++++++++++
 ptrlist.h   | 14 +++++++++++++-
 simplify.c  |  8 ++++++--
 unssa.c     |  4 +++-
 7 files changed, 71 insertions(+), 11 deletions(-)

diff --git a/flow.c b/flow.c
index 6cac21b24..1dbfd431e 100644
--- a/flow.c
+++ b/flow.c
@@ -283,6 +283,8 @@ void convert_instruction_target(struct instruction
*insn, pseudo_t src)
        if (target == src)
                return;
        FOR_EACH_PTR(target->users, pu) {
+               if (!pu)
+                       continue;
                if (*pu->userp != VOID) {
                        assert(*pu->userp == target);
                        *pu->userp = src;
@@ -675,8 +677,10 @@ static void simplify_one_symbol(struct entrypoint
*ep, struct symbol *sym)
        complex = 0;
        FOR_EACH_PTR(pseudo->users, pu) {
                /* We know that the symbol-pseudo use is the "src" in
the instruction */
-               struct instruction *insn = pu->insn;
-
+               struct instruction *insn;
+               if (!pu)
+                       continue;
+               insn = pu->insn;
                switch (insn->opcode) {
                case OP_STORE:
                        stores++;
@@ -715,7 +719,10 @@ static void simplify_one_symbol(struct entrypoint
*ep, struct symbol *sym)
                src = def->target;

        FOR_EACH_PTR(pseudo->users, pu) {
-               struct instruction *insn = pu->insn;
+               struct instruction *insn;
+               if (!pu)
+                       continue;
+               insn = pu->insn;
                if (insn->opcode == OP_LOAD) {
                        check_access(insn);
                        convert_load_instruction(insn, src);
@@ -731,7 +738,10 @@ complex_def:
 external_visibility:
        all = 1;
        FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
-               struct instruction *insn = pu->insn;
+               struct instruction *insn;
+               if (!pu)
+                       continue;
+               insn = pu->insn;
                if (insn->opcode == OP_LOAD)
                        all &= find_dominating_stores(pseudo, insn,
++bb_generation, !mod);
        } END_FOR_EACH_PTR_REVERSE(pu);
@@ -739,7 +749,10 @@ external_visibility:
        /* If we converted all the loads, remove the stores. They are dead */
        if (all && !mod) {
                FOR_EACH_PTR(pseudo->users, pu) {
-                       struct instruction *insn = pu->insn;
+                       struct instruction *insn;
+                       if (!pu)
+                               continue;
+                       insn = pu->insn;
                        if (insn->opcode == OP_STORE)
                                kill_store(insn);
                } END_FOR_EACH_PTR(pu);
@@ -749,7 +762,10 @@ external_visibility:
                 * of them..
                 */
                FOR_EACH_PTR(pseudo->users, pu) {
-                       struct instruction *insn = pu->insn;
+                       struct instruction *insn;
+                       if (!pu)
+                               continue;
+                       insn = pu->insn;
                        if (insn->opcode == OP_STORE)
                                kill_dominated_stores(pseudo, insn,
++bb_generation, insn->bb, !mod, 0);
                } END_FOR_EACH_PTR(pu);
diff --git a/linearize.c b/linearize.c
index ba76397ea..0933e935f 100644
--- a/linearize.c
+++ b/linearize.c
@@ -542,6 +542,8 @@ static void show_symbol_usage(pseudo_t pseudo)

        if (pseudo) {
                FOR_EACH_PTR(pseudo->users, pu) {
+                       if (!pu)
+                               continue;
                        printf("\t%s\n", show_instruction(pu->insn));
                } END_FOR_EACH_PTR(pu);
        }
diff --git a/memops.c b/memops.c
index aeacdf566..ce5aecbe8 100644
--- a/memops.c
+++ b/memops.c
@@ -66,7 +66,10 @@ static int address_taken(pseudo_t pseudo)
 {
        struct pseudo_user *pu;
        FOR_EACH_PTR(pseudo->users, pu) {
-               struct instruction *insn = pu->insn;
+               struct instruction *insn;
+               if (!pu)
+                       continue;
+               insn = pu->insn;
                if (insn->bb && (insn->opcode != OP_LOAD &&
insn->opcode != OP_STORE))
                        return 1;
        } END_FOR_EACH_PTR(pu);
diff --git a/ptrlist.c b/ptrlist.c
index 5dc1117c5..609d4feba 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -29,6 +29,19 @@ int ptr_list_size(struct ptr_list *head)
        return nr;
 }

+int ptr_list_size_null(struct ptr_list *head)
+{
+       int nr = 0;
+
+       if (head) {
+               struct ptr_list *list = head;
+               do {
+                       nr += list->nr - list->rm;
+               } while ((list = list->next) != head);
+       }
+       return nr;
+}
+
 /*
  * Linearize the entries of a list up to a total of 'max',
  * and return the nr of entries linearized.
@@ -97,6 +110,14 @@ restart:
        }
 }

+void pack_ptr_list_null(struct ptr_list **listp)
+{
+       struct ptr_list *head = *listp;
+
+       if (ptr_list_size_null(head) == 0)
+               *listp = NULL;
+}
+
 void split_ptr_list_head(struct ptr_list *head)
 {
        int old = head->nr, nr = old / 2;
diff --git a/ptrlist.h b/ptrlist.h
index d09be2f51..cbdd34f93 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];
@@ -43,6 +44,7 @@ extern void **__add_ptr_list(struct ptr_list **,
void *, unsigned long);
 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 ptr_list_size_null(struct ptr_list *);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);

 /*
@@ -283,10 +285,20 @@ extern void split_ptr_list_head(struct ptr_list *);
 #define DELETE_CURRENT_PTR(ptr) \
        DO_DELETE_CURRENT(ptr, __head##ptr, __list##ptr, __nr##ptr)

+#define DO_DELETE_CURRENT_NULL(__list, __nr) do {
         \
+       void **__this = __list->list + __nr;
         \
+       *__this = NULL;
         \
+       __list->rm++;
         \
+} while (0)
+
+#define DELETE_CURRENT_PTR_NULL(ptr) \
+       DO_DELETE_CURRENT_NULL(__list##ptr, __nr##ptr)
+
 #define REPLACE_CURRENT_PTR(ptr, new_ptr)
                 \
        do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)

 extern void pack_ptr_list(struct ptr_list **);
+extern void pack_ptr_list_null(struct ptr_list **);

 #define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x))

diff --git a/simplify.c b/simplify.c
index 03ff9c942..eddef76e8 100644
--- a/simplify.c
+++ b/simplify.c
@@ -171,15 +171,17 @@ static int delete_pseudo_user_list_entry(struct
pseudo_user_list **list, pseudo_
        struct pseudo_user *pu;

        FOR_EACH_PTR(*list, pu) {
+               if (!pu)
+                       continue;
                if (pu->userp == entry) {
-                       DELETE_CURRENT_PTR(pu);
+                       DELETE_CURRENT_PTR_NULL(pu);
                        if (!--count)
                                goto out;
                }
        } END_FOR_EACH_PTR(pu);
        assert(count <= 0);
 out:
-       pack_ptr_list((struct ptr_list **)list);
+       pack_ptr_list_null((struct ptr_list **)list);
        return count;
 }

@@ -308,6 +310,8 @@ static int dead_insn(struct instruction *insn,
pseudo_t *src1, pseudo_t *src2, p
 {
        struct pseudo_user *pu;
        FOR_EACH_PTR(insn->target->users, pu) {
+               if (!pu)
+                       continue;
                if (*pu->userp != VOID)
                        return 0;
        } END_FOR_EACH_PTR(pu);
diff --git a/unssa.c b/unssa.c
index e7c9154d5..28af0833c 100644
--- a/unssa.c
+++ b/unssa.c
@@ -36,7 +36,7 @@

 static inline int nbr_pseudo_users(pseudo_t p)
 {
-       return ptr_list_size((struct ptr_list *)p->users);
+       return ptr_list_size_null((struct ptr_list *)p->users);
 }

 static int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
@@ -58,6 +58,8 @@ static int simplify_phi_node(struct instruction
*phi, pseudo_t tmp)
        // no need to make a copy of this one
        // -> replace the target pseudo by the tmp
        FOR_EACH_PTR(target->users, pu) {
+               if (!pu)
+                       continue;
                use_pseudo(pu->insn, tmp, pu->userp);
        } END_FOR_EACH_PTR(pu);

--
2.13.2

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Christopher Li]

> From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> Date: Thu, Aug 3, 2017 at 8:22 PM
> Subject: [PATCH] mark pseudo user as deleted instead of removing them
> To: Christopher Li <sparse@chrisli.org>
> Cc: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>
>
> For discussion only.
>
> This atch is also available in the git repository at:

Hah, that is very similar to one of my private patch attempt to use
ptrlist refcount
to make the delete right. Abandoned due to the insert case.

My ptrlist->deletes is your ptrlist->rm here.
https://git.kernel.org/pub/scm/devel/sparse/chrisl/sparse.git/diff/ptrlist.h?h=ptrlist-refcount-clean


> @@ -283,6 +283,8 @@ void convert_instruction_target(struct instruction
> *insn, pseudo_t src)
>         if (target == src)
>                 return;
>         FOR_EACH_PTR(target->users, pu) {
> +               if (!pu)
> +                       continue;

I think this kind of the check should be put into FOR_EACH_PTR()
If you have ptr->rm && current ptr == NULL, then the ptr should be skipped.
In other words, it is a bug if the ptr->rm > 0 and ptr == NULL and ptr
is not skipped.
I can totally see some usage case some one forget to make that check.

There is a few design choice here. We can make ptr==NULL for the condition
of ptr is marked deleted. We can also use tags to do the marking. Using tags
will allow NULL pointer as valid entry in the ptrlist.

I am still curious which ptrlist want to use NULL pointer as valid pointers.
We might want to revisit that decision.

>  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 ptr_list_size_null(struct ptr_list *);

I don't think we need ptr_list_size_null vs ptr_list_size.
Nobody care what was the ptr list size counting the deleted entry.
We want the ptrlist size with valid entry only.


>
> +#define DO_DELETE_CURRENT_NULL(__list, __nr) do {

I think the name of the macro should more like DO_MARK_CURRENT_DELETED

>          \
> +       void **__this = __list->list + __nr;
>          \
> +       *__this = NULL;

You can use PTR_ENTRY() here instead.

>          \
> +       __list->rm++;
>          \
> +} while (0)
> +
> +#define DELETE_CURRENT_PTR_NULL(ptr) \
> +       DO_DELETE_CURRENT_NULL(__list##ptr, __nr##ptr)
> +

MARK_CURRENT_DELETED()


>  #define REPLACE_CURRENT_PTR(ptr, new_ptr)
>                  \
>         do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
>
>  extern void pack_ptr_list(struct ptr_list **);
> +extern void pack_ptr_list_null(struct ptr_list **);

Why do we need two different version of pack_ptr_list?
If the ptrlist->rm != 0, that already means this ptrlist has been
used for mark deleted. Can we use just one pack_ptr_list instead?

Another thing is that, we might want to put some code
to assert in the ptrlist split and seeing ptrlist->rm != 0.
ptrlist->rm !=0 means we do care about preserve the list->list[]
and list->nr. Ptrlist split will make some damage to that assumption.

Another thing I am thinking is weather this change too big for RC5.
This patch is very similar to mine after removing dependency of the
ptrlist refcount.

Chris

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Luc Van Oostenryck]

On Fri, Aug 04, 2017 at 11:29:50AM -0400, Christopher Li wrote:
> > From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> > Date: Thu, Aug 3, 2017 at 8:22 PM
> > Subject: [PATCH] mark pseudo user as deleted instead of removing them
> > To: Christopher Li <sparse@chrisli.org>
> > Cc: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> >
> >
> > For discussion only.
...
> > @@ -283,6 +283,8 @@ void convert_instruction_target(struct instruction
> > *insn, pseudo_t src)
> >         if (target == src)
> >                 return;
> >         FOR_EACH_PTR(target->users, pu) {
> > +               if (!pu)
> > +                       continue;
> 
> I think this kind of the check should be put into FOR_EACH_PTR()

Of course, it's why I said it wasn't very pretty.

It is so for now because this patch only concerns lists
with pseudo_users and only these lists need this check
(and I certainly don't want to duplicate all the macros now).

> There is a few design choice here. We can make ptr==NULL for the condition
> of ptr is marked deleted. We can also use tags to do the marking. Using tags
> will allow NULL pointer as valid entry in the ptrlist.

It's a possibility indeed.
 
> I am still curious which ptrlist want to use NULL pointer as valid pointers.
> We might want to revisit that decision.

There is only one case and it's to support an abuse of the list typing.
I have a patch to have the clean typing (and thus no more null pointers in lists).
Not -rc5 material IMO though.

> >  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 ptr_list_size_null(struct ptr_list *);
> 
> I don't think we need ptr_list_size_null vs ptr_list_size.

Certainly true when all the lists will have been converted.
Even true for the ones that doesn't but for the moment,
as prototype to discuss the principle and to be sure to not
introduce any changes else where, I've kept them separated.

> Nobody care what was the ptr list size counting the deleted entry.
> We want the ptrlist size with valid entry only.

> > +#define DO_DELETE_CURRENT_NULL(__list, __nr) do {
> I think the name of the macro should more like DO_MARK_CURRENT_DELETED
> You can use PTR_ENTRY() here instead.
> MARK_CURRENT_DELETED()

Yes, details that will matter once we'll agree on the principle.
 
> Why do we need two different version of pack_ptr_list?

same as for ptr_list_size_null().

> If the ptrlist->rm != 0, that already means this ptrlist has been
> used for mark deleted. Can we use just one pack_ptr_list instead?

Not sure to understand you here.
 
> Another thing is that, we might want to put some code
> to assert in the ptrlist split and seeing ptrlist->rm != 0.

OK, but again the goal of this patch is not about ptrlist split.
It's only for the very specific case you found where there is a
problem with deletion on pseudo-users lists. No more, no less.

> Another thing I am thinking is weather this change too big for RC5.

As such, I don't think it's a big change for -rc5, it's quite well
contained to some very specific code.

I agree that it would be natural to ask if we want a fix for this problem
in the -rc5, though, as the problem have been there forever and nothing
really bad has been discovered.

I would be fine with this patch (but it would need a bit more testing).
I would be fine with no patch at all.
I would be ok with your patch (the one with list duplication) but I
think it's not a good one, even as a temporary bandaid (for the reasons
I explained the first time I commented on it).

-- Luc

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Christopher Li]

First thing first, I don't have strong reason to object this patch.
So it can be merge into RC5.

On Fri, Aug 4, 2017 at 11:58 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Of course, it's why I said it wasn't very pretty.
>
> It is so for now because this patch only concerns lists
> with pseudo_users and only these lists need this check
> (and I certainly don't want to duplicate all the macros now).

OK. I see. As a minor point, (will not affect patch being accepted)
I want to make this into a part of the stander list.
And the "if (list->rm)" will make sure we only take the new code
path for pseudo_users. Because we only call to MARK_CURRENT_DELTE()
on pseudo_users.

Have two version of the API is confusing to the developer of sparse.
I would rather hind those temporary detail from the developer.
This ptr_list_size_null() is likely get remove from the next version of
sparse any way. So it would better not to expose it.


>
> There is only one case and it's to support an abuse of the list typing.
> I have a patch to have the clean typing (and thus no more null pointers in lists).
> Not -rc5 material IMO though.

Agree.

>
>> >  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 ptr_list_size_null(struct ptr_list *);
>>
>> I don't think we need ptr_list_size_null vs ptr_list_size.
>
> Certainly true when all the lists will have been converted.
> Even true for the ones that doesn't but for the moment,
> as prototype to discuss the principle and to be sure to not
> introduce any changes else where, I've kept them separated.

I do not mean to convert all ptrlist. I am object to have two similar
api. If we do a test of "if (list->rm)", we can make sure only the
pseudo_user get the new code path. Because that is the only
ptrlist is going to mark ptrlist deleted and having list->rm != 0.

>
> Yes, details that will matter once we'll agree on the principle.

Principle is fine :-)

>
>> Why do we need two different version of pack_ptr_list?
>
> same as for ptr_list_size_null().

I see your reasoning was to reduce code impact.
I think the testing of (ptrlist->rm) can do the same thing.


>
>> If the ptrlist->rm != 0, that already means this ptrlist has been
>> used for mark deleted. Can we use just one pack_ptr_list instead?


I want to have one single API instead of two. As the code impact
caution, the "if (ptrlist->rm)" test will make sure only pseudo_user
list get the new code path.

Currently you use two different api function call to make sure
the new code don't impact other list. I mean to say you can do
the same with "if (ptrlist->rm)" testing.

Sparse also has usage as library for other projects.
Having some stable api is a good thing. I don't want a new temporary
API which get removed later if we can avoid it.

>
> Not sure to understand you here.

See above, hope I explain it clear enough.


>
>> Another thing is that, we might want to put some code
>> to assert in the ptrlist split and seeing ptrlist->rm != 0.
>
> OK, but again the goal of this patch is not about ptrlist split.
> It's only for the very specific case you found where there is a
> problem with deletion on pseudo-users lists. No more, no less.

OK, that is just a suggestion any way. Minor one.

>
>> Another thing I am thinking is weather this change too big for RC5.
>
> As such, I don't think it's a big change for -rc5, it's quite well
> contained to some very specific code.

If we are going to push this for RC5, can we have one set of API
for this case? I see reason not to introduce temporary API which
will get remove later.

Having the check for "if (list->rm)" and only add new code under
that condition will make sure enough we don't impact the other list
and old code?

> I agree that it would be natural to ask if we want a fix for this problem
> in the -rc5, though, as the problem have been there forever and nothing
> really bad has been discovered.

Fine with me.

> I would be fine with this patch (but it would need a bit more testing).
> I would be fine with no patch at all.
> I would be ok with your patch (the one with list duplication) but I
> think it's not a good one, even as a temporary bandaid (for the reasons
> I explained the first time I commented on it).

Fair enough. Yes. I can apply it. The question is, do you want to remove
the duplicate set of API? (by testing "list->rm").

Chris

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Luc Van Oostenryck]

On Fri, Aug 04, 2017 at 02:19:54PM -0400, Christopher Li wrote:
> First thing first, I don't have strong reason to object this patch.
> So it can be merge into RC5.

OK, good.
 
> > I would be fine with this patch (but it would need a bit more testing).
> > I would be fine with no patch at all.
> > I would be ok with your patch (the one with list duplication) but I
> > think it's not a good one, even as a temporary bandaid (for the reasons
> > I explained the first time I commented on it).
> 
> Fair enough. Yes. I can apply it. The question is, do you want to remove
> the duplicate set of API? (by testing "list->rm").

Sure but I think I will even not test anything at all.
For the others lists we don't touch to the ->rm field and
we have the guarantee that it will be initialized to zero
so adding nr or adding (nr - rm) will be the same anyway
(and doing the substraction certainly won't cost more than
adding a test).

-- Luc

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Christopher Li]

On Fri, Aug 4, 2017 at 3:12 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> Fair enough. Yes. I can apply it. The question is, do you want to remove
>> the duplicate set of API? (by testing "list->rm").
>
> Sure but I think I will even not test anything at all.
> For the others lists we don't touch to the ->rm field and
> we have the guarantee that it will be initialized to zero
> so adding nr or adding (nr - rm) will be the same anyway
> (and doing the substraction certainly won't cost more than
> adding a test).

Yes, exactly. Testing was the mental model. Implementation
can be optimized away. :-)

Wait for your new patch then.

Chris

[PATCH 0/4] 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() - ...

Luc Van Oostenryck (4):
  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
  mark pseudo users as deleted instead of removing them

 flow.c      | 28 ++++++++++++++++++++++------
 linearize.c |  2 ++
 memops.c    |  5 ++++-
 ptrlist.c   |  2 +-
 ptrlist.h   | 11 ++++++++++-
 simplify.c  | 10 ++++++++--
 unssa.c     |  2 ++
 7 files changed, 49 insertions(+), 11 deletions(-)

-- 
2.13.2

[PATCH 1/4] 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 2/4] 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 3/4] 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 4/4] 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>
---
 flow.c      | 28 ++++++++++++++++++++++------
 linearize.c |  2 ++
 memops.c    |  5 ++++-
 simplify.c  | 10 ++++++++--
 unssa.c     |  2 ++
 5 files changed, 38 insertions(+), 9 deletions(-)

diff --git a/flow.c b/flow.c
index 6cac21b24..1dbfd431e 100644
--- a/flow.c
+++ b/flow.c
@@ -283,6 +283,8 @@ void convert_instruction_target(struct instruction *insn, pseudo_t src)
 	if (target == src)
 		return;
 	FOR_EACH_PTR(target->users, pu) {
+		if (!pu)
+			continue;
 		if (*pu->userp != VOID) {
 			assert(*pu->userp == target);
 			*pu->userp = src;
@@ -675,8 +677,10 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 	complex = 0;
 	FOR_EACH_PTR(pseudo->users, pu) {
 		/* We know that the symbol-pseudo use is the "src" in the instruction */
-		struct instruction *insn = pu->insn;
-
+		struct instruction *insn;
+		if (!pu)
+			continue;
+		insn = pu->insn;
 		switch (insn->opcode) {
 		case OP_STORE:
 			stores++;
@@ -715,7 +719,10 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 		src = def->target;
 
 	FOR_EACH_PTR(pseudo->users, pu) {
-		struct instruction *insn = pu->insn;
+		struct instruction *insn;
+		if (!pu)
+			continue;
+		insn = pu->insn;
 		if (insn->opcode == OP_LOAD) {
 			check_access(insn);
 			convert_load_instruction(insn, src);
@@ -731,7 +738,10 @@ complex_def:
 external_visibility:
 	all = 1;
 	FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
-		struct instruction *insn = pu->insn;
+		struct instruction *insn;
+		if (!pu)
+			continue;
+		insn = pu->insn;
 		if (insn->opcode == OP_LOAD)
 			all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
 	} END_FOR_EACH_PTR_REVERSE(pu);
@@ -739,7 +749,10 @@ external_visibility:
 	/* If we converted all the loads, remove the stores. They are dead */
 	if (all && !mod) {
 		FOR_EACH_PTR(pseudo->users, pu) {
-			struct instruction *insn = pu->insn;
+			struct instruction *insn;
+			if (!pu)
+				continue;
+			insn = pu->insn;
 			if (insn->opcode == OP_STORE)
 				kill_store(insn);
 		} END_FOR_EACH_PTR(pu);
@@ -749,7 +762,10 @@ external_visibility:
 		 * of them..
 		 */
 		FOR_EACH_PTR(pseudo->users, pu) {
-			struct instruction *insn = pu->insn;
+			struct instruction *insn;
+			if (!pu)
+				continue;
+			insn = pu->insn;
 			if (insn->opcode == OP_STORE)
 				kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0);
 		} END_FOR_EACH_PTR(pu);
diff --git a/linearize.c b/linearize.c
index ba76397ea..0933e935f 100644
--- a/linearize.c
+++ b/linearize.c
@@ -542,6 +542,8 @@ static void show_symbol_usage(pseudo_t pseudo)
 
 	if (pseudo) {
 		FOR_EACH_PTR(pseudo->users, pu) {
+			if (!pu)
+				continue;
 			printf("\t%s\n", show_instruction(pu->insn));
 		} END_FOR_EACH_PTR(pu);
 	}
diff --git a/memops.c b/memops.c
index aeacdf566..ce5aecbe8 100644
--- a/memops.c
+++ b/memops.c
@@ -66,7 +66,10 @@ static int address_taken(pseudo_t pseudo)
 {
 	struct pseudo_user *pu;
 	FOR_EACH_PTR(pseudo->users, pu) {
-		struct instruction *insn = pu->insn;
+		struct instruction *insn;
+		if (!pu)
+			continue;
+		insn = pu->insn;
 		if (insn->bb && (insn->opcode != OP_LOAD && insn->opcode != OP_STORE))
 			return 1;
 	} END_FOR_EACH_PTR(pu);
diff --git a/simplify.c b/simplify.c
index 03ff9c942..0569007a1 100644
--- a/simplify.c
+++ b/simplify.c
@@ -166,20 +166,24 @@ static int clean_up_phi(struct instruction *insn)
 	return if_convert_phi(insn);
 }
 
+
 static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
 {
 	struct pseudo_user *pu;
 
 	FOR_EACH_PTR(*list, pu) {
+		if (!pu)
+			continue;
 		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;
 }
 
@@ -308,6 +312,8 @@ static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, p
 {
 	struct pseudo_user *pu;
 	FOR_EACH_PTR(insn->target->users, pu) {
+		if (!pu)
+			continue;
 		if (*pu->userp != VOID)
 			return 0;
 	} END_FOR_EACH_PTR(pu);
diff --git a/unssa.c b/unssa.c
index e7c9154d5..87d0c2c7f 100644
--- a/unssa.c
+++ b/unssa.c
@@ -58,6 +58,8 @@ static int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
 	// no need to make a copy of this one
 	// -> replace the target pseudo by the tmp
 	FOR_EACH_PTR(target->users, pu) {
+		if (!pu)
+			continue;
 		use_pseudo(pu->insn, tmp, pu->userp);
 	} END_FOR_EACH_PTR(pu);
 
-- 
2.13.2

Re: [PATCH 4/4] mark pseudo users as deleted instead of removing them

[Christopher Li]

On Fri, Aug 4, 2017 at 4:09 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>         FOR_EACH_PTR(target->users, pu) {
> +               if (!pu)
> +                       continue;

Your previous patch looks fine.

Here in my previous email feed back I mean to include  this check into
FOR_EACH_PTR()
so you don't need touch every pseudo_user list looping every where.
Just do some thing like
       if (list->rm && list->list[__nr] == NULL)
              continue;

inside the FOR_EACH_PTR(). and REVERSE as well.

It will not have impact on other list because other list will not
have list->rm != 0.

With this change, the caller side of the change not needed.

Chris

Re: [PATCH 4/4] mark pseudo users as deleted instead of removing them

[Christopher Li]

On Fri, Aug 4, 2017 at 4:17 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> Your previous patch looks fine.

I mean your patch 1-3 looks fine. This one can be simplified.

Chris

Re: [PATCH 4/4] mark pseudo users as deleted instead of removing them

[Luc Van Oostenryck]

On Fri, Aug 4, 2017 at 10:17 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Aug 4, 2017 at 4:09 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>>         FOR_EACH_PTR(target->users, pu) {
>> +               if (!pu)
>> +                       continue;
>
> Your previous patch looks fine.
>
> Here in my previous email feed back I mean to include  this check into
> FOR_EACH_PTR()
> so you don't need touch every pseudo_user list looping every where.
> Just do some thing like
>        if (list->rm && list->list[__nr] == NULL)
>               continue;
>
> inside the FOR_EACH_PTR(). and REVERSE as well.
>
> It will not have impact on other list because other list will not
> have list->rm != 0.

It will not have a functional impact but you will add this test
(and code for both tests) for every other use of the list macros
for which it is totally unneeded.
Are you sure to really want that?

-- Luc

Re: [PATCH 4/4] mark pseudo users as deleted instead of removing them

[Christopher Li]

On Fri, Aug 4, 2017 at 4:34 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> It will not have a functional impact but you will add this test
> (and code for both tests) for every other use of the list macros
> for which it is totally unneeded.
> Are you sure to really want that?

I am not sure we are on the same page. Only 2 macro need to be updated:
DO_FOR_EACH_PTR, DO_FOR_EACH_REVERSE.

Maybe DO_REPAIR(), DO_NEXT() and DO_REVERSE() if we are ambition.
It think it is fine without touch the last three also.

That is not too bad, is it?

Chris

Re: [PATCH 4/4] mark pseudo users as deleted instead of removing them

[Luc Van Oostenryck]

On Fri, Aug 4, 2017 at 10:48 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Aug 4, 2017 at 4:34 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> It will not have a functional impact but you will add this test
>> (and code for both tests) for every other use of the list macros
>> for which it is totally unneeded.
>> Are you sure to really want that?
>
> I am not sure we are on the same page. Only 2 macro need to be updated:
> DO_FOR_EACH_PTR, DO_FOR_EACH_REVERSE.

It's not for the number of macros defined.
It's about the code size & the run-time effect on the iteration of
the other lists. It seems simple enough but it would add two load-test-branch
to every such macro invocation and these macros are already quite heavy.

-- Luc

Re: [PATCH 4/4] mark pseudo users as deleted instead of removing them

[Christopher Li]

On Fri, Aug 4, 2017 at 5:03 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> I am not sure we are on the same page. Only 2 macro need to be updated:
>> DO_FOR_EACH_PTR, DO_FOR_EACH_REVERSE.
>
> It's not for the number of macros defined.
> It's about the code size & the run-time effect on the iteration of
> the other lists. It seems simple enough but it would add two load-test-branch

Because the rm is near the nr, which get visit every loop iteration.
From cache line point of view, the ptrlist->rm will not cause extra cache load.
The second test and load will not matter for most of the ptrlist any way.

I am willing to bet even my test-ptrlist benchmark will not see much a
difference.

> to every such macro invocation and these macros are already quite heavy.

The flip side is if some one forget to check that, it will be very
bad. How do you
make sure you add the check to every single one of the loop iterator?

I can take patch as it is. It is only a suggestion. No deal breaker.

Chris

Re: [PATCH 4/4] mark pseudo users as deleted instead of removing them

[Luc Van Oostenryck]

On Fri, Aug 4, 2017 at 11:14 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Aug 4, 2017 at 5:03 PM, Luc Van Oostenryck wrote:
>>> I am not sure we are on the same page. Only 2 macro need to be updated:
>>> DO_FOR_EACH_PTR, DO_FOR_EACH_REVERSE.
>>
>> It's not for the number of macros defined.
>> It's about the code size & the run-time effect on the iteration of
>> the other lists. It seems simple enough but it would add two load-test-branch
>
> Because the rm is near the nr, which get visit every loop iteration.
> From cache line point of view, the ptrlist->rm will not cause extra cache load.
> The second test and load will not matter for most of the ptrlist any way.

Yes, we agree.

> I am willing to bet even my test-ptrlist benchmark will not see much a
> difference.

It will depend on how micro the benchmark is but indeed on real code,
most probably it won't make any measurable difference.

>> to every such macro invocation and these macros are already quite heavy.
>
> The flip side is if some one forget to check that, it will be very
> bad. How do you
> make sure you add the check to every single one of the loop iterator?

Oh, I agree on this one but the same argument when pushed further
can lead to absurd situations. We're not there though.

> I can take patch as it is. It is only a suggestion. No deal breaker.

Frankly, I don't know.

I never liked to have to add these checks a bit everywhere,
that's why I called it 'not very pretty'.
My inclination would be to create a variant FOR_EACH_PTR_NULL(),
this can be done without duplicating the real macro DO_...
but then you can as easily forgot to call this variant that you could
forgot to add the test locally (adding some typing could help here though).
On the other hand, adding these tests to all list iteration code when
not needed looks bad.

OK, since the run-time impact will be low enough let's choose the
solution with the smallest (source) code impact.
New version on the way.

-- Luc

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Linus Torvalds]

On Fri, Aug 4, 2017 at 8:29 AM, Christopher Li <sparse@chrisli.org> wrote:
>
> There is a few design choice here. We can make ptr==NULL for the condition
> of ptr is marked deleted. We can also use tags to do the marking. Using tags
> will allow NULL pointer as valid entry in the ptrlist.

I think what might be a good idea is to simply replace the "nr" in
"ptr_list" with a bitmap of entries instead.

We already limit each ptr_list[] to 29 entries, so making it an
"unsigned int" bitmap instead wouldn't be hard. So it would be just a
single-bit "tag" whether an entry is present or not.

And that allows easy deletion, easy insertion and easy to iterate over too.

The insertion is admittedly a *bit* awkward, since you have to find a
free bit, but it's either a fairly simple loop or on newer CPU's you
can use the "find first bit" instruction.

                Linus

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Christopher Li]

On Fri, Aug 4, 2017 at 12:54 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> I think what might be a good idea is to simply replace the "nr" in
> "ptr_list" with a bitmap of entries instead.

That is one interesting idea.

>
> We already limit each ptr_list[] to 29 entries, so making it an
> "unsigned int" bitmap instead wouldn't be hard. So it would be just a
> single-bit "tag" whether an entry is present or not.

Sure. I think Luc has a patch to make it 13 entries now.

>
> And that allows easy deletion, easy insertion and easy to iterate over too.

I have to think about the insert and ptrlist node split more.

>
> The insertion is admittedly a *bit* awkward, since you have to find a
> free bit, but it's either a fairly simple loop or on newer CPU's you
> can use the "find first bit" instruction.

So for the nested loop insert case, the parent loop iterator will keep
track of __nth_valid_ptr as the slot indicator instead of __nr. If the insert
happen before the __nth_valid_ptr, That still doesn't work, because
the list->list[] will still get shifted.

If the insert only happen after __nth_valid_ptr, that might be
able to work.

For node spiting, We just need to carry over the __nth_valid_ptr to
the next splinted node, still not work if the insert position is
before the carry
over part of the __nth_valid_ptr.

Again I need to think about it more.

Or do you see a way to make insert into any slot position work with
parent holding pointer to the slot number?

Yes, the bit mask seems better than the mark ptr entry as NULL or tag it.

Chris

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Christopher Li]

On Fri, Aug 4, 2017 at 2:33 PM, Christopher Li <sparse@chrisli.org> wrote:
> So for the nested loop insert case, the parent loop iterator will keep
> track of __nth_valid_ptr as the slot indicator instead of __nr. If the insert
> happen before the __nth_valid_ptr, That still doesn't work, because
> the list->list[] will still get shifted.
>
> If the insert only happen after __nth_valid_ptr, that might be
> able to work.
>
> For node spiting, We just need to carry over the __nth_valid_ptr to
> the next splinted node, still not work if the insert position is
> before the carry
> over part of the __nth_valid_ptr.
>
> Again I need to think about it more.
>
> Or do you see a way to make insert into any slot position work with
> parent holding pointer to the slot number?

OK. I might have a way to make it work for insert case.
Let me lay it out here.

Has two bit mask, one for deleted entry. one for inserted entry, let's
call it insert slot mask.

The deleted entry is what Linus suggested. The inserted slot mask is marking
which entry is new element insert into the list->list[]. When the list->list[]
was shifted to make room for new ptr entry, the insert slot mask will need
to be shift accordingly was well. (so does the delete slot mask).

I was original thinking only track element insert in the middle of list->list[].
But then I realize for the reverse ptr loop case I need to track insert
from the tail as well.

Then the parent loop iterator will keep a copy of the insert mask and
__nth_slot_ptr before execute the loop body.

The inner loop might update the ptrlist and the insert
slot mask.

The parent can compare the cached version of the insert slot mask
and the current list insert slot mask to find out which slot are inserted
during the execution of the loop body. Then the parent can adjust
__nth_slot_ptr accordingly.

It is complicated, but it seems possible to make correct loop iterator
when the inner loop modify insert element to the list. It is the first idea
I have that does not involve with a link list of the previous modify log.

I obvious need to think about it more. For now, I do think this can
produce the correct behavior. The space cost of extra 32 bit slot is not
too bad either.

Chris

Re: [PATCH] mark pseudo user as deleted instead of removing them

[Christopher Li]

On Fri, Aug 4, 2017 at 4:08 PM, Christopher Li <sparse@chrisli.org> wrote:
> Then the parent loop iterator will keep a copy of the insert mask and
> __nth_slot_ptr before execute the loop body.

I found a small bug here. The outer most loop iterator need to
reset insert mask to zero. In other words, it need the ptrlist
refcount patch. The outer most iterator can even compact the list->list[]
and clear out delete slot mask and insert slot mask when refcount
drop to zero.

>
> The inner loop might update the ptrlist and the insert
> slot mask.

The insert only need to update insert slot mask when list->refcout != 0.
In other words, some one is looping on this list entry. Which is very rare.

I expect his have very minimal performance impact (other than the refcount
part). Most of the case there is no insert happen in this ptrlist. We can
do the fast path, need need to adjust __nth_slot_ptr. Let a non inlined
function to do the slow patch adjustment of __nth_slot_ptr base on
the two  insert slot mask(before and after).

Chris

Re: [PATCH RFC] Let pseudo->users loop on duplicate version of list

[Christopher Li]

On Wed, Jul 12, 2017 at 11:05 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>> My ptrlist ref count patch haven't check the split node situation.
>> Even Luc's suggestion for "mark and sweep" to delete the ptrlist
>> is not going to help with the nested loop split. I will add that check.
>> I don't expect new offenders but let's make sure about it.
>>
>
> I did raise this before
> (http://marc.info/?l=linux-sparse&m=149943353732715&w=2) but maybe it
> got lost in the other stuff.

I add a check to the ptrlist refcount patch to look for insert inside
nested loop. Just as I expected,  running the full kernel source check
did not reveal any such situation. That is a good news in a sense.

Chris