• Huang Ying's avatar
    lib, Add lock-less NULL terminated single list · f49f23ab
    Huang Ying authored
    Cmpxchg is used to implement adding new entry to the list, deleting
    all entries from the list, deleting first entry of the list and some
    other operations.
    Because this is a single list, so the tail can not be accessed in O(1).
    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 (or llist_del_all, llist_add,
    llist_add) sequence in another consumer may violate 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.
    This can be summarized as follow:
               |   add    | del_first |  del_all
     add       |    -     |     -     |     -
     del_first |          |     L     |     L
     del_all   |          |           |     -
    Where "-" stands for no lock is needed, while "L" stands for lock is
    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.  The order
    of deleted entries is from the newest to the oldest added one.  If you
    want to traverse from the oldest to the newest, you must reverse the
    order by yourself before traversing.
    The basic atomic operation of this list is cmpxchg on long.  On
    architectures that don't have NMI-safe cmpxchg implementation, the
    list can NOT be used in NMI handler.  So code uses the list in NMI
    handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
    Signed-off-by: default avatarHuang Ying <ying.huang@intel.com>
    Reviewed-by: default avatarAndi Kleen <ak@linux.intel.com>
    Reviewed-by: default avatarMathieu Desnoyers <mathieu.desnoyers@efficios.com>
    Cc: Andrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLen Brown <len.brown@intel.com>
llist.h 4.57 KB