* [PATCH 0/2] be more generous with ptrlist repacking @ 2016-11-17 17:25 Luc Van Oostenryck 2016-11-17 17:25 ` [PATCH 1/2] add missing PACK_PTR_LIST() Luc Van Oostenryck ` (2 more replies) 0 siblings, 3 replies; 11+ messages in thread From: Luc Van Oostenryck @ 2016-11-17 17:25 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck The macros that do the ptrlist walking don't handle empty blocks. So, when some elements are removed from a list some list rapacking need to be done to remove the empty blocks. Failure to do this can result in crashes or data corruption. This series aims to improve the situation by: - doing the repacking at the places where some elements are removed but no repacking where done. - to compensate the added cost, mark ptrlists as dirty when some element are removed from it and only do the repacking when the list is marked as dirty. Another thing that can be done would be to check the dirty bit at every list walking but I think this should be reserved for testing/debugging. In fact, while at first agreeing with the idea of the second patch, I think less and less that it's the right approach. What are we looking after here? * Performance? - Will this bit save us a lot of list repacking? * Robustness? - What this bit bring us? Nothing without check at each list walking. Is it a good idea to sprinkle some assert() on the macros? - I would much prefer to have something that either: - can do the list walking with empty blocks, or - never leave any empty blocks. and this without making the macros heavier :) I'll try later to propose something but for now ... Luc Van Oostenryck (2): add missing PACK_PTR_LIST() mark lists to be repacked as dirty cse.c | 1 + evaluate.c | 1 + ptrlist.c | 7 +++++++ ptrlist.h | 4 +++- 4 files changed, 12 insertions(+), 1 deletion(-) -- ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 1/2] add missing PACK_PTR_LIST() 2016-11-17 17:25 [PATCH 0/2] be more generous with ptrlist repacking Luc Van Oostenryck @ 2016-11-17 17:25 ` Luc Van Oostenryck 2016-11-17 17:25 ` [PATCH 2/2] mark lists to be repacked as dirty Luc Van Oostenryck 2016-11-17 17:40 ` [PATCH 0/2] be more generous with ptrlist repacking Linus Torvalds 2 siblings, 0 replies; 11+ messages in thread From: Luc Van Oostenryck @ 2016-11-17 17:25 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck At two places in the code, DELETE_PTR() is called on soem list but PACK_PTR_LIST() is not called at the end of the loop. This potentially leave empty ptrlist 'blocks' which are not handled by the usual list walking macros. No concrete situation have been found where a real problem occurs but better be safe than sorry and call PACK_PTR_LIST() here too. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- cse.c | 1 + evaluate.c | 1 + 2 files changed, 2 insertions(+) diff --git a/cse.c b/cse.c index e8fbe344..71325a74 100644 --- a/cse.c +++ b/cse.c @@ -260,6 +260,7 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct if (pu->insn == insn) DELETE_CURRENT_PTR(pu); } END_FOR_EACH_PTR(pu); + PACK_PTR_LIST(&phi->users); } END_FOR_EACH_PTR(phi); } diff --git a/evaluate.c b/evaluate.c index e350c0c0..d1383902 100644 --- a/evaluate.c +++ b/evaluate.c @@ -2521,6 +2521,7 @@ found: excess(e, lclass & TYPE_PTR ? "array" : "struct or union"); } END_FOR_EACH_PTR(e); + PACK_PTR_LIST(&expr->expr_list); convert_designators(last); expr->ctype = ctype; -- 2.10.2 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH 2/2] mark lists to be repacked as dirty 2016-11-17 17:25 [PATCH 0/2] be more generous with ptrlist repacking Luc Van Oostenryck 2016-11-17 17:25 ` [PATCH 1/2] add missing PACK_PTR_LIST() Luc Van Oostenryck @ 2016-11-17 17:25 ` Luc Van Oostenryck 2016-11-17 17:40 ` [PATCH 0/2] be more generous with ptrlist repacking Linus Torvalds 2 siblings, 0 replies; 11+ messages in thread From: Luc Van Oostenryck @ 2016-11-17 17:25 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck Use a bit in the head of a ptrlist and set it when DELETE_PTR() is called. Check the bit when repacking a list and do nothing if the bit is not set. Note: delete_ptr_list_entry() & delete_ptr_list_last() don't need any handling because they either always call pack_ptr_list() or remove the last block when it becomes empty. Suggested-by: Christopher Li <sparse@chrisli.org> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- ptrlist.c | 7 +++++++ ptrlist.h | 4 +++- 2 files changed, 10 insertions(+), 1 deletion(-) diff --git a/ptrlist.c b/ptrlist.c index 5dc1117c..e817bad1 100644 --- a/ptrlist.c +++ b/ptrlist.c @@ -70,6 +70,11 @@ void pack_ptr_list(struct ptr_list **listp) if (head) { struct ptr_list *entry = head; + + if (!head->dirty) + return; + head->dirty = 0; + do { struct ptr_list *next; restart: @@ -138,6 +143,7 @@ void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag) list->prev = newlist; last->next = newlist; } + newlist->dirty = 0; last = newlist; nr = 0; } @@ -188,6 +194,7 @@ void * undo_ptr_list_last(struct ptr_list **head) if (!first) return NULL; + first->dirty = 1; last = first; do { last = last->prev; diff --git a/ptrlist.h b/ptrlist.h index 61e159fd..c24bfb82 100644 --- a/ptrlist.h +++ b/ptrlist.h @@ -25,7 +25,8 @@ #define LIST_NODE_NR (29) struct ptr_list { - int nr; + int nr:31; + unsigned int dirty:1; // will need to be repacked struct ptr_list *prev; struct ptr_list *next; void *list[LIST_NODE_NR]; @@ -254,6 +255,7 @@ extern void split_ptr_list_head(struct ptr_list *); __this++; \ } \ *__this = (void *)0xf0f0f0f0; \ + __head->dirty = 1; \ __list->nr--; __nr--; \ } while (0) -- 2.10.2 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 0/2] be more generous with ptrlist repacking 2016-11-17 17:25 [PATCH 0/2] be more generous with ptrlist repacking Luc Van Oostenryck 2016-11-17 17:25 ` [PATCH 1/2] add missing PACK_PTR_LIST() Luc Van Oostenryck 2016-11-17 17:25 ` [PATCH 2/2] mark lists to be repacked as dirty Luc Van Oostenryck @ 2016-11-17 17:40 ` Linus Torvalds 2016-11-17 18:17 ` Christopher Li 2016-11-17 20:25 ` Luc Van Oostenryck 2 siblings, 2 replies; 11+ messages in thread From: Linus Torvalds @ 2016-11-17 17:40 UTC (permalink / raw) To: Luc Van Oostenryck; +Cc: Sparse Mailing-list, Christopher Li On Thu, Nov 17, 2016 at 9:25 AM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > The macros that do the ptrlist walking don't handle empty blocks. Actually, most of the_do_ handle empty blocks. In particular, the normal FOR_EACH_PTR() case should handle it just fine. The exception is, I think: - first_ptr_list/last_ptr_list - DO_PREPARE/DO_RESET which just don't walk the pointer block list, they just end up blindly doing PTR_ENTRY(list, 0); for the first entry, or list = list->prev; PTR_ENTRY(list, list->nr-1); for the last one. I suspect they should be fairly easy to update to just walk the list until they hit a non-empty case (like DO_NEXT() already does, for example). Linus ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 0/2] be more generous with ptrlist repacking 2016-11-17 17:40 ` [PATCH 0/2] be more generous with ptrlist repacking Linus Torvalds @ 2016-11-17 18:17 ` Christopher Li 2016-11-17 20:25 ` Luc Van Oostenryck 1 sibling, 0 replies; 11+ messages in thread From: Christopher Li @ 2016-11-17 18:17 UTC (permalink / raw) To: Linus Torvalds; +Cc: Luc Van Oostenryck, Sparse Mailing-list On Fri, Nov 18, 2016 at 1:40 AM, Linus Torvalds <torvalds@linux-foundation.org> wrote: > > I suspect they should be fairly easy to update to just walk the list > until they hit a non-empty case (like DO_NEXT() already does, for > example). I think you are right, as always. It just need to add four while loops into first_ptr_list/last_ptr_list/DO_PREPARE/DO_RESET. Amount those 3 of the place should be able to share a function (or macro) to find the next not empty entry from list head. Ptrlist deletion happen so rare, it does not justify the complexity. Luc, sorry about the bad suggestion. Chris ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 0/2] be more generous with ptrlist repacking 2016-11-17 17:40 ` [PATCH 0/2] be more generous with ptrlist repacking Linus Torvalds 2016-11-17 18:17 ` Christopher Li @ 2016-11-17 20:25 ` Luc Van Oostenryck 2016-11-17 22:03 ` Linus Torvalds 2016-11-18 12:26 ` Luc Van Oostenryck 1 sibling, 2 replies; 11+ messages in thread From: Luc Van Oostenryck @ 2016-11-17 20:25 UTC (permalink / raw) To: Linus Torvalds; +Cc: Sparse Mailing-list, Christopher Li, Dan Carpenter On Thu, Nov 17, 2016 at 09:40:20AM -0800, Linus Torvalds wrote: > On Thu, Nov 17, 2016 at 9:25 AM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: > > The macros that do the ptrlist walking don't handle empty blocks. > > Actually, most of the_do_ handle empty blocks. In particular, the > normal FOR_EACH_PTR() case should handle it just fine. Yes, indeed. > The exception is, I think: > > - first_ptr_list/last_ptr_list > > - DO_PREPARE/DO_RESET ... > I suspect they should be fairly easy to update to just walk the list > until they hit a non-empty case (like DO_NEXT() already does, for > example). > > Linus > -- Would something like the following be fine? From bf7f856f95a71b931559a17c0f5144cd3a3875b5 Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> Date: Thu, 17 Nov 2016 20:59:18 +0100 Subject: [PATCH] make ptrlist walking against robust against empty blocks Not all macros or function involved in the ptrlist walking can handle a ptrlist containing some empty blocks. Fix this by: - add the proper check & looping to first & last_ptr_list(). - add a safe version of PTR_ENTRY doing the needed check & looping. - use this safe version for DO_PREPARE() & DO_RESET() Suggested-by: Linus Torvalds <torvalds@linux-foundation.org> CC: Dan Carpenter <dan.carpenter@oracle.com> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- I've quickly checked it on the testsuite (and it seems to pass ;). I'll validate this more thoroughly but I won't be able to do this just now. --- ptrlist.h | 29 ++++++++++++++++++++++++++--- 1 file changed, 26 insertions(+), 3 deletions(-) diff --git a/ptrlist.h b/ptrlist.h index 61e159fd..d09be2f5 100644 --- a/ptrlist.h +++ b/ptrlist.h @@ -67,28 +67,51 @@ extern int linearize_ptr_list(struct ptr_list *, void **, int); static inline void *first_ptr_list(struct ptr_list *list) { + struct ptr_list *head = list; + if (!list) return NULL; + + while (list->nr == 0) { + list = list->next; + if (list == head) + return NULL; + } return PTR_ENTRY(list, 0); } static inline void *last_ptr_list(struct ptr_list *list) { + struct ptr_list *head = list; if (!list) return NULL; list = list->prev; + while (list->nr == 0) { + if (list == head) + return NULL; + list = list->prev; + } return PTR_ENTRY(list, list->nr-1); } +#define PTR_DEREF(__head, idx, PTR_ENTRY) ({ \ + struct ptr_list *__list = __head; \ + while (__list && __list->nr == 0) { \ + __list = __list->next; \ + if (__list == __head) \ + __list = NULL; \ + } \ + __list ? PTR_ENTRY(__list, idx) : NULL; \ +}) + #define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY) \ do { \ struct ptr_list *__head = (struct ptr_list *) (head); \ struct ptr_list *__list = __head; \ int __nr = 0; \ CHECK_TYPE(head,ptr); \ - if (__head) ptr = PTR_ENTRY(__head, 0); \ - else ptr = NULL + ptr = PTR_DEREF(__head, 0, PTR_ENTRY); \ #define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \ if (ptr) { \ @@ -110,7 +133,7 @@ static inline void *last_ptr_list(struct ptr_list *list) do { \ __nr = 0; \ __list = __head; \ - if (__head) ptr = PTR_ENTRY(__head, 0); \ + if (__head) ptr = PTR_DEREF(__head, 0, PTR_ENTRY); \ } while (0) #define DO_FINISH(ptr, __head, __list, __nr) \ -- 2.10.2 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 0/2] be more generous with ptrlist repacking 2016-11-17 20:25 ` Luc Van Oostenryck @ 2016-11-17 22:03 ` Linus Torvalds 2016-11-18 0:29 ` Luc Van Oostenryck 2016-11-18 12:26 ` Luc Van Oostenryck 1 sibling, 1 reply; 11+ messages in thread From: Linus Torvalds @ 2016-11-17 22:03 UTC (permalink / raw) To: Luc Van Oostenryck; +Cc: Sparse Mailing-list, Christopher Li, Dan Carpenter On Thu, Nov 17, 2016 at 12:25 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > Would something like the following be fine? This looks good to me, although I didn't actually test it. But it looks like what I would have expected. Some of those inlines look large enough that I wonder how much sense they make as inlines any more, but I think that's a separate issue. Linus ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 0/2] be more generous with ptrlist repacking 2016-11-17 22:03 ` Linus Torvalds @ 2016-11-18 0:29 ` Luc Van Oostenryck 2016-11-28 21:15 ` Luc Van Oostenryck 0 siblings, 1 reply; 11+ messages in thread From: Luc Van Oostenryck @ 2016-11-18 0:29 UTC (permalink / raw) To: Linus Torvalds; +Cc: Sparse Mailing-list, Christopher Li, Dan Carpenter On Thu, Nov 17, 2016 at 02:03:05PM -0800, Linus Torvalds wrote: > On Thu, Nov 17, 2016 at 12:25 PM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: > > > > Would something like the following be fine? > > This looks good to me, although I didn't actually test it. But it > looks like what I would have expected. > > Some of those inlines look large enough that I wonder how much sense > they make as inlines any more, but I think that's a separate issue. Oh, I absolutely agree. What I would like is something more iterator oriented which keep track of the head-list-nr state. I have a working prototype I made last week but it still needs some more polishing. Luc ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 0/2] be more generous with ptrlist repacking 2016-11-18 0:29 ` Luc Van Oostenryck @ 2016-11-28 21:15 ` Luc Van Oostenryck 2016-12-06 0:24 ` Christopher Li 0 siblings, 1 reply; 11+ messages in thread From: Luc Van Oostenryck @ 2016-11-28 21:15 UTC (permalink / raw) To: Linus Torvalds; +Cc: Sparse Mailing-list, Christopher Li, Dan Carpenter On Fri, Nov 18, 2016 at 01:29:19AM +0100, Luc Van Oostenryck wrote: > On Thu, Nov 17, 2016 at 02:03:05PM -0800, Linus Torvalds wrote: > > On Thu, Nov 17, 2016 at 12:25 PM, Luc Van Oostenryck > > <luc.vanoostenryck@gmail.com> wrote: > > > > > > Would something like the following be fine? > > > > This looks good to me, although I didn't actually test it. But it > > looks like what I would have expected. > > > > Some of those inlines look large enough that I wonder how much sense > > they make as inlines any more, but I think that's a separate issue. > > Oh, I absolutely agree. > What I would like is something more iterator oriented which keep track > of the head-list-nr state. I have a working prototype I made last week > but it still needs some more polishing. > I've worked a bit more on this. I had a nice, clean & compact implementation where basically all ptr_list walking was done by something like: struct ptr_iter iter; ptr_iter_init(&iter, head); while ((ptr = ptr_iter_next(&iter))) ... Of course, still hidden under the macros which do the type checking. This had the advantage that all the logic was in a single place. It seemed to work well that is until I discovered that at a few places we're storing null pointers in ptr_lists. It's thus not possible to use the returned pointer to also check the end of list condition. The situation is even a bit more complex because the PREPARE/NEXT_PTR_LIST() also can't work with null pointers. I've found a few alternative that work in all the cases but they aren't simple & compact enough to my taste so I'll let things like they are and maybe just sent a few cleanups later. Luc ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 0/2] be more generous with ptrlist repacking 2016-11-28 21:15 ` Luc Van Oostenryck @ 2016-12-06 0:24 ` Christopher Li 0 siblings, 0 replies; 11+ messages in thread From: Christopher Li @ 2016-12-06 0:24 UTC (permalink / raw) To: Luc Van Oostenryck; +Cc: Linus Torvalds, Sparse Mailing-list, Dan Carpenter On Mon, Nov 28, 2016 at 1:15 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > I've worked a bit more on this. I had a nice, clean & compact > implementation where basically all ptr_list walking was done by > something like: > struct ptr_iter iter; > ptr_iter_init(&iter, head); > while ((ptr = ptr_iter_next(&iter))) > ... Last time I try that, I look at the machine code and realized that using iter struct is not quite the same as using macro. On each function boundary, the compiler still try to sync the data register content into the iter structure in memory. In other words, there is no way to make the iter variable as register, it always get sync into memory. I did run a full kernel source check back then, did not find an observable difference. The time difference is within the variance of each run. Maybe due to most of the list are very short. Chris ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 0/2] be more generous with ptrlist repacking 2016-11-17 20:25 ` Luc Van Oostenryck 2016-11-17 22:03 ` Linus Torvalds @ 2016-11-18 12:26 ` Luc Van Oostenryck 1 sibling, 0 replies; 11+ messages in thread From: Luc Van Oostenryck @ 2016-11-18 12:26 UTC (permalink / raw) To: Linus Torvalds; +Cc: Sparse Mailing-list, Christopher Li, Dan Carpenter On Thu, Nov 17, 2016 at 09:25:24PM +0100, Luc Van Oostenryck wrote: > Would something like the following be fine? > ... > I've quickly checked it on the testsuite (and it seems to pass ;). > I'll validate this more thoroughly but I won't be able to do this > just now. OK, I've run it on a much bigger set: a make C=2 kernel with allyesconfig, the same tree as the test I did previously and it gives me the same result and, of course, no crashes. So for me the changes are OK. Tested-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2016-12-06 0:38 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2016-11-17 17:25 [PATCH 0/2] be more generous with ptrlist repacking Luc Van Oostenryck 2016-11-17 17:25 ` [PATCH 1/2] add missing PACK_PTR_LIST() Luc Van Oostenryck 2016-11-17 17:25 ` [PATCH 2/2] mark lists to be repacked as dirty Luc Van Oostenryck 2016-11-17 17:40 ` [PATCH 0/2] be more generous with ptrlist repacking Linus Torvalds 2016-11-17 18:17 ` Christopher Li 2016-11-17 20:25 ` Luc Van Oostenryck 2016-11-17 22:03 ` Linus Torvalds 2016-11-18 0:29 ` Luc Van Oostenryck 2016-11-28 21:15 ` Luc Van Oostenryck 2016-12-06 0:24 ` Christopher Li 2016-11-18 12:26 ` Luc Van Oostenryck
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.