| Message ID | CANeU7QmpvfZutvnSwrjH7ZYXhw3S3HDh19eHXkBGY7oz7ADtmw@mail.gmail.com (mailing list archive) |
|---|---|
| State | Rejected, archived |
| Headers | show |
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 -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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) \
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(-) } 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)