| Message ID | 20160613094517.GA25301@mwanda (mailing list archive) |
|---|---|
| State | Superseded, archived |
| Headers | show |
On Mon, Jun 13, 2016 at 12:45:17PM +0300, Dan Carpenter wrote: > This change is similar to 2e7dd34d11cb ('ptrlist: reading deleted items > in NEXT_PTR_LIST()'). If we use DELETE_CURRENT_PTR() then we can end up > with a list->nr that is zero meaning that we have to go back another > list->prev to find what we want. Otherwise we dereference 0xf0f0f0f0 > and crash. > > Signed-off-by: Dan Carpenter <dan.carpenter@oracle.com> > --- > ptrlist.h | 2 ++ > 1 file changed, 2 insertions(+) > > diff --git a/ptrlist.h b/ptrlist.h > index 61e159f..6f90c8f 100644 > --- a/ptrlist.h > +++ b/ptrlist.h > @@ -78,6 +78,8 @@ static inline void *last_ptr_list(struct ptr_list *list) > if (!list) > return NULL; > list = list->prev; > + while (list->nr == 0) > + list = list->prev; > return PTR_ENTRY(list, list->nr-1); > } > > -- Hi, while trying to find a test case for this one, I noticed that something as simple as: void rem_rev(struct vpl *list) { void *last; void *ptr; FOR_EACH_PTR_REVERSE(list, ptr) { DELETE_CURRENT_PTR(ptr); last = last_ptr_list((struct ptr_list *)list); } END_FOR_EACH_PTR_REVERSE(ptr); } loops forever on a list with 1 element with your patch. Without your patch, last_ptr_list() return an invalid pointer instead of NULL. So, I don't think your patch is the right solution but, yes somethings should be done about this. Cheers, Luc Van Oostenryck -- 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, Nov 2, 2016 at 8:48 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: >> + while (list->nr == 0) >> + list = list->prev; Yes, it can deed loop here when the whole list is empty. > FOR_EACH_PTR_REVERSE(list, ptr) { > DELETE_CURRENT_PTR(ptr); > last = last_ptr_list((struct ptr_list *)list); > } END_FOR_EACH_PTR_REVERSE(ptr); > } > loops forever on a list with 1 element with your patch. > Without your patch, last_ptr_list() return an invalid pointer instead of NULL. > I can see what is going on now. The while loop should check for the list->prev has been loop back to the tail of the list. Some thing like this should fix it, I haven't test it at all. list = tail = list->prev; while (list->nr == 0) { list = list->prev; if (list == tail) return NULL; } 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
On Wed, Nov 02, 2016 at 10:52:35PM +0800, Christopher Li wrote: > On Wed, Nov 2, 2016 at 8:48 PM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: > >> + while (list->nr == 0) > >> + list = list->prev; > > Yes, it can deed loop here when the whole list is empty. > > > FOR_EACH_PTR_REVERSE(list, ptr) { > > DELETE_CURRENT_PTR(ptr); > > last = last_ptr_list((struct ptr_list *)list); > > } END_FOR_EACH_PTR_REVERSE(ptr); > > } > > loops forever on a list with 1 element with your patch. > > Without your patch, last_ptr_list() return an invalid pointer instead of NULL. > > > > I can see what is going on now. The while loop should > check for the list->prev has been loop back to the tail of > the list. > > Some thing like this should fix it, I haven't test it at all. > > list = tail = list->prev; > while (list->nr == 0) { > list = list->prev; > if (list == tail) > return NULL; > } > > Chris > -- Yes, something like this should do, indeed. But by looking at the code, I think that 'first_ptr_list()' is also not immunised against the same problem. Also these two functions first_ & last_ptr_list() were trivial ones but now they maybe become a bit too heavy to be inlined? Or, maybe we should create a 'safe' version of those two, not inlined, and which do the correct list walking? Or maybe we need to have a macro like LAST_PTR() which do everything needed, like DELETE_CURRENT_PTR() do? I would vote for the safe version. Luc -- 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
Another thing I noticed is that after using DELETE_CURRENT_PTR() the next PREPARE_PTR_LIST() will fail or give wrong result if the list hasn't been repacked first. Maybe it's obvious but I wouldn't be surprised if there is even more situations that need to be protected against empty blocks. -- 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
Those function originally all assume the list are packed. Is there usage case in current sparse that feed unpacked list to those function? Chris On Fri, Nov 4, 2016 at 6:44 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > Another thing I noticed is that after using DELETE_CURRENT_PTR() > the next PREPARE_PTR_LIST() will fail or give wrong result if the > list hasn't been repacked first. > > Maybe it's obvious but I wouldn't be surprised if there is even more > situations that need to be protected against empty blocks. -- 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 Sat, Nov 05, 2016 at 08:30:31AM +0800, Christopher Li wrote: > Those function originally all assume the list > are packed. > > Is there usage case in current sparse that > feed unpacked list to those function? > > Chris The situation is not black & white. There is two 'unsafe' cases. By 'unsafe' I mean that DELETE_CURRENT_PTR() is used but without PACK_PTR_LIST() and the end of the iteration like done elsewhere. OTOH, I've added at the beginning of every ptr_list loops some assert() that check if the ptr_list is packed or not and none ever triggered, even when LIST_NODE_NR is changed from 29 to 1 (to force list->nr == 0 at each delete). Also, assertions doing bound checking on ptr_list::list[] accesses never triggered. So, to answer your question, it seems that in the current sparse code we don't feed unpacked lists to the 'dangerous' functions but for the two unsafe case you can't guarantee thsi just by looking at the local code (or it's just by chance). I think that for the moment, it's best to simply add PACK_PTR_LIST() at the end of the two unsafe cases (patch will come later). OTOH, I feel this whole situation is a bit fragile. NOTE: for the moment, I've only checked all this with the testsuite. I will recheck on more substantial amount of code but this will need to wait a little bit. Luc -- 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 Sun, Nov 06, 2016 at 09:49:38AM +0100, Luc Van Oostenryck wrote: > On Sat, Nov 05, 2016 at 08:30:31AM +0800, Christopher Li wrote: > > Those function originally all assume the list > > are packed. > > > > Is there usage case in current sparse that > > feed unpacked list to those function? > > > > Chris OK, I've checked this on a more substantial amount of code than the testsuite: the kernel for x86-64 with allyesconfig and I confirm that there is not a single out-of-bounds access to any ->list[], wich is what matters. Nevertheless, there are two cases (in cse.c and evaluate.c) where elements are deleted from a list which is not directly repacked at the end of the loop and it's not obvious in the code why it's OK to not repack them. Luc -- 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 Mon, Nov 7, 2016 at 6:00 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > OK, I've checked this on a more substantial amount of code > than the testsuite: the kernel for x86-64 with allyesconfig > and I confirm that there is not a single out-of-bounds access > to any ->list[], wich is what matters. > > Nevertheless, there are two cases (in cse.c and evaluate.c) > where elements are deleted from a list which is not directly > repacked at the end of the loop and it's not obvious in the code > why it's OK to not repack them. Thanks for the extensive testing. As for the repacking, I think its better to repack the list to after the delete of the entry. However, we don't want to repack the list if there is not deletion at all. How about this, we can introduce a bit field on "struct ptr_list" to keep track of the list needs repack or not. On deletion the ptr_list will be dirty. The other function which assuming the packed list will check the dirty bit and complain if list is not packed. We can even make keep the "struct ptr_list" the same size. Just squeeze some bits from "int nr". However, that will break the binary interface of sparse as a library. The application link with sparse will need to be recompiled. 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
On Thu, Nov 17, 2016 at 06:46:44AM +0800, Christopher Li wrote: > On Mon, Nov 7, 2016 at 6:00 PM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: > > OK, I've checked this on a more substantial amount of code > > than the testsuite: the kernel for x86-64 with allyesconfig > > and I confirm that there is not a single out-of-bounds access > > to any ->list[], wich is what matters. > > > > Nevertheless, there are two cases (in cse.c and evaluate.c) > > where elements are deleted from a list which is not directly > > repacked at the end of the loop and it's not obvious in the code > > why it's OK to not repack them. > > Thanks for the extensive testing. As for the repacking, I think its > better to repack the list to after the delete of the entry. However, > we don't want to repack the list if there is not deletion at all. > > How about this, we can introduce a bit field on "struct ptr_list" to > keep track of the list needs repack or not. On deletion the ptr_list will > be dirty. The other function which assuming the packed list will > check the dirty bit and complain if list is not packed. > > We can even make keep the "struct ptr_list" the same size. > Just squeeze some bits from "int nr". However, that will break the > binary interface of sparse as a library. The application link with > sparse will need to be recompiled. > > Chris > -- Sound good. I'll look at this, probably tomorrow. Luc -- 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/ptrlist.h b/ptrlist.h index 61e159f..6f90c8f 100644 --- a/ptrlist.h +++ b/ptrlist.h @@ -78,6 +78,8 @@ static inline void *last_ptr_list(struct ptr_list *list) if (!list) return NULL; list = list->prev; + while (list->nr == 0) + list = list->prev; return PTR_ENTRY(list, list->nr-1); }
This change is similar to 2e7dd34d11cb ('ptrlist: reading deleted items in NEXT_PTR_LIST()'). If we use DELETE_CURRENT_PTR() then we can end up with a list->nr that is zero meaning that we have to go back another list->prev to find what we want. Otherwise we dereference 0xf0f0f0f0 and crash. Signed-off-by: Dan Carpenter <dan.carpenter@oracle.com> --- ptrlist.h | 2 ++ 1 file changed, 2 insertions(+)