On Wed, Aug 2, 2017 at 7:44 PM, Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx> 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 -- 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
