Re: About lock-less data structure patches

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

* 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