Skip to content
Snippets Groups Projects
  • Pawel Dziepak's avatar
    bca7bbbe
    sched: reimplement incoming_wakeup_queue · bca7bbbe
    Pawel Dziepak authored
    
    This patch implements lockfree_queue (which is used as incoming_wakeup_queue)
    so that it doesn't need exchange or compare_exchange operations.
    
    The idea is to use a linked list but interleave actual objects stored in the
    queue with helper object (lockless_queue_helper) which are just pointer to the
    next element. Each object in the queue owns the helper that precedes it (and
    they are dequeued together) while the last helper, which does not precede any
    object is owned by the queue itself.
    
    When a new object is enqueued it gains ownership of the last helper in the
    queue in exchange of the helper it owned before which now becomes the new
    tail of the list.
    
    Unlike the original implementation this version of lockfree_queue really
    requires that there is no more than one concurrent producer and no more than
    one concurrent consumer.
    
    The results oftests/misc-ctxs on my test machine are as follows (the values
    are medians of five runs):
    
    before:
    colocated: 332 ns
    apart: 590 ns
    
    after:
    colocated: 313 ns
    apart: 558 ns
    
    Reviewed-by: default avatarNadav Har'El <nyh@cloudius-systems.com>
    Signed-off-by: default avatarPawel Dziepak <pdziepak@quarnos.org>
    Signed-off-by: default avatarPekka Enberg <penberg@cloudius-systems.com>
    bca7bbbe
    History
    sched: reimplement incoming_wakeup_queue
    Pawel Dziepak authored
    
    This patch implements lockfree_queue (which is used as incoming_wakeup_queue)
    so that it doesn't need exchange or compare_exchange operations.
    
    The idea is to use a linked list but interleave actual objects stored in the
    queue with helper object (lockless_queue_helper) which are just pointer to the
    next element. Each object in the queue owns the helper that precedes it (and
    they are dequeued together) while the last helper, which does not precede any
    object is owned by the queue itself.
    
    When a new object is enqueued it gains ownership of the last helper in the
    queue in exchange of the helper it owned before which now becomes the new
    tail of the list.
    
    Unlike the original implementation this version of lockfree_queue really
    requires that there is no more than one concurrent producer and no more than
    one concurrent consumer.
    
    The results oftests/misc-ctxs on my test machine are as follows (the values
    are medians of five runs):
    
    before:
    colocated: 332 ns
    apart: 590 ns
    
    after:
    colocated: 313 ns
    apart: 558 ns
    
    Reviewed-by: default avatarNadav Har'El <nyh@cloudius-systems.com>
    Signed-off-by: default avatarPawel Dziepak <pdziepak@quarnos.org>
    Signed-off-by: default avatarPekka Enberg <penberg@cloudius-systems.com>