lkml.org 
[lkml]   [2011]   [Apr]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: About lock-less data structure patches
    * huang ying (huang.ying.caritas@gmail.com) wrote:
    > On Tue, Apr 5, 2011 at 12:42 PM, Mathieu Desnoyers
    [snip]
    >
    > >> It seems hard to implement the
    > >> dequeue_all,
    > >
    > > Actually, there is already one implemented :)
    > >
    > > See urcu-call-rcu.c: call_rcu_thread()
    >
    > Have not understand the whole algorithm fully. Will continue to study
    > it. I found there is a synchronize_rcu() in call_crc_thread(). Must
    > "dequeue_all" use that too?

    Please note that call_rcu_thread() does more than just a dequeue_all: it
    dequeues all the current callbacks from the list, waits for a grace
    period to elapse, and then execute all the callbacks it got. So the
    synchronize_rcu() would not be needed in a dequeue_all implementation.

    >
    > >> >> >> mutex is needed between multiple "_slist_stack_pop", but not needed
    > >> >> >> between slist_stack_push_lf and _slist_stack_pop.  I think it is hard to
    > >> >> >> explain that clearly via function naming.
    > >> >> >
    > >> >> > Good point. A ascii-art table might be appropriate here, e.g.:
    > >> >> >
    > >> >> >
    > >> >> > M: Mutual exclusion needed to protect one from another.
    > >> >> > -: lockless.
    > >> >> >
    > >> >> >              |     push     |   pop    |   pop_all
    > >> >> > push         |      -       |    -     |     -
    > >> >> > pop          |              |    L     |     L
    > >> >> > pop_all      |              |          |     -
    > >> >> >
    > >> >> > How about adding this (or something prettier) to the header ?
    > >> >>
    > >> >> Cool!  I will add that to header.
    > >> >>
    > >> >> >>> * If we choose to go with an alternate wait-free push implementation:
    > >> >> >>>
    > >> >> >>> llist_add -> slist_stack_push_wf              (wait-free)
    > >> >> >>> llist_del_first -> slist_stack_pop_blocking   (blocking)
    > >> >> >>> llist_del_all -> slist_stack_pop_all_blocking (blocking)
    > >> >> >>
    > >> >> >> We need non-blocking pop, so maybe you need implement another data
    > >> >> >> structure which has these interface.  I think there can be multiple
    > >> >> >> lock-less data structure in kernel.
    > >> >> >
    > >> >> > As I noted earlier, the blocking was only due to our user-level
    > >> >> > implementation. It can be turned in a very short-lived busy loop
    > >> >> > instead.
    > >> >> >
    > >> >> >>
    > >> >> >>>> + *
    > >> >> >>>> + * If there are multiple producers and multiple consumers, llist_add
    > >> >> >>>> + * can be used in producers and llist_del_all can be used in
    > >> >> >>>> + * consumers.  They can work simultaneously without lock.  But
    > >> >> >>>> + * llist_del_first can not be used here.  Because llist_del_first
    > >> >> >>>> + * depends on list->first->next does not changed if list->first is not
    > >> >> >>>> + * changed during its operation, but llist_del_first, llist_add,
    > >> >> >>>> + * llist_add sequence in another consumer may violate that.
    > >> >> >>>
    > >> >> >>> You did not seem to define the locking rules when using both
    > >> >> >>>
    > >> >> >>>   llist_del_all
    > >> >> >>> and
    > >> >> >>>   llist_del_first
    > >> >> >>>
    > >> >> >>> in parallel. I expect that a mutex is needed, because a
    > >> >> >>>
    > >> >> >>>   llist_del_all, llist_add, llist_add
    > >> >> >>>
    > >> >> >>> in parallel with
    > >> >> >>>
    > >> >> >>>   llist_del_first
    > >> >> >>>
    > >> >> >>> could run into the same ABA problem as described above.
    > >> >> >>
    > >> >> >> OK.  I will add that.
    > >> >> >>
    > >> >> >>>> + *
    > >> >> >>>> + * If there are multiple producers and one consumer, llist_add can be
    > >> >> >>>> + * used in producers and llist_del_all or llist_del_first can be used
    > >> >> >>>> + * in the consumer.
    > >> >> >>>> + *
    > >> >> >>>> + * The list entries deleted via llist_del_all can be traversed with
    > >> >> >>>> + * traversing function such as llist_for_each etc.  But the list
    > >> >> >>>> + * entries can not be traversed safely before deleted from the list.
    > >> >> >>>
    > >> >> >>> Given that this is in fact a stack, specifying the traversal order of
    > >> >> >>> llist_for_each and friends would be appropriate.
    > >> >> >>
    > >> >> >> Ok.  I will add something like "traversing from head to tail" in the
    > >> >> >> comments.
    > >> >> >
    > >> >> > Traversing from last element pushed to first element pushed would
    > >> >> > probably be clearer.
    > >> >>
    > >> >> head and tail describe the current state, while "last/first element
    > >> >> pushed" describe the history.  I think both are understandable.
    > >> >
    > >> > head and tail, in a list implemented as a stack (but that is not
    > >> > clearly advertised as such), don't convey the meaning of "we're
    > >> > iterating from the newest element pushed to the oldest one". This
    > >> > counter-intuitiveness is part of why I would really like to see this
    > >> > turned into a queue.
    > >>
    > >> OK.  I will change the comments, adding these semantics explanation.
    > >> The user should be warned :)
    > >
    > > Yes, that makes sense. After this generalization step, if you're ok with
    > > this, we could aim at moving the implementation from a stack to a queue
    > > and provide fifo semantic rather than lifo, so that other users (e.g.
    > > call_rcu in the kernel) can start benefiting from it.
    >
    > I think that is good to move from stack to queue.
    >
    > I will send out changed lock-less data structure patchset soon. And
    > we can continue to work on the new lock-less queue at the same time.

    Sounds like a very good plan! Thanks!

    Mathieu

    --
    Mathieu Desnoyers
    Operating System Efficiency R&D Consultant
    EfficiOS Inc.
    http://www.efficios.com
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2011-04-06 03:51    [W:2.141 / U:0.048 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site