On Fri, Jul 07, 2017 at 02:06:14AM -0700, Christopher Li wrote: > On Fri, Jul 7, 2017 at 1:28 AM, Luc Van Oostenryck > <luc.vanoostenryck@xxxxxxxxx> wrote: > > > > This reference count is a property of the whole list and would thus > > need to be stored in the head of the list, which doesn't really exist. > > Obviously I am too tired to think straight right now. But I think my > idea of reference counting on the list node, not the while list might > actually work. Because, if the inner loop delete an entry of a different > node than the outer loop was currently holding on, it is actually fine. > Why? Because by the time the outer loop advance to the that the > deleted node, it will reload the list->nr from memory. > I can be wrong through. I should be able to find out soon enough. > > > Also, I'm not convinced that the problem can only caused by the list > > packing in the inner loop (looking at the code for the FOR_EACH, it > > looks as it should be OK, but if you enter in the equation, reverse > > walking and/or list splitting, I have doubts). > > Like I said, if you delete entry while the outer loop holding the > same ptr node, it is a bug even without packing the list in inner > loop. Yup. > I think ref counting the node should be fine with reversing. List > spiting I have to. Will find out. > > > > > Another point to take in account is that the list packing was needed > > because the list walking didn't like empty blocks. But months ago, > > because of another bugs we made all the list walking robust against > > empty blocks, so list packing shouldn't be needed anymore for > > correctness. So we could in general avoid any list packing, > > and only do it at some specific safe points just to save memory & > > CPU time when walking lists with several blocks but few elements > > (and we need to keep in mind that most lists are very very short). > > I still think if ref counting node properly, it will solve the bug I describe > and possible the list packing as well. If nobody else is holding that > node, it should be fine to pack and delete it. Yes, it's very possible that it will work properly, but at which price? You will need to add some complexity to make it work, is it worth? > It is not thread safe but > that is a different issue. That's really the last of my worries, sparse is not designed to be threaded and I don't see why it should. > > > > I'm more and more inclined to: > > 1) in general, avoid altogether deletion from lists in favor > > marking elements as being deleted, either like we do for > > instructions (setting insn->bb to NULL) or storing a special > > value in the ptrlist. > > My idea of the ref count will do exactly that when the inner > loop try to delete an entry but outer loop holding the node as well. > It will increase the deleted count and replace the ptr entry to > NULL. > > When the ref count of the node drop to zero and node has delete count. > Pack the entry[] array, remove NULL entry and even possible delete > the node as well. > > Let me know if you see any problem with that approach. Except for the added complexity of having to maintain the ref count for, IMO, no good enough reasons, the problem is that some lists contains NULL pointers as legitimate values (I don't remember which parts do but I had the case when I added the protection for the empty blocks I also completly rewrote all the ptrlist layer with nice clean iterator structures and a set of functions around it and those functions naturally returned NULL to meant the end-of-list. First testing went quite well but then showed some bugs casued by the fact that some of the lists contained NULL as legitimate value). It's why I said here above "marking as deleted or storing a special value". Of course, maybe we can more easily avoid the few special cases where NULLs are stored in ptrlist. > > 2) at some specific points, as an optimization, doing a sort of > > GC of the list: removing elements marked as deleted and/or > > doing the list packing. > > If the ref count node works, then just pack the node when > ref count drop to zero (or one with some care). > > One idea is that we can use sparse to check itself > if there is any sparse code return in a loop without dec the ref count. > > > That sound to me as simple, generic and robust. > > Yes. So our idea is actually very similar. The only difference > is I use ref count as means of GC, so the ptrlist always knows > when it is safe to delete stuff. > > I will find out more. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
