path: root/lib/Makefile
diff options
authorHuang Ying <ying.huang@intel.com>2011-07-13 13:14:23 +0800
committerLen Brown <len.brown@intel.com>2011-08-03 11:15:56 -0400
commitf49f23abf3dd786ddcac1c1e7db3c2013b07413f (patch)
tree0726af5e245025b60be8adee0deb8bc665510904 /lib/Makefile
parentdf013ffb8119c89f062ab05b7f544704315db47b (diff)
lib, Add lock-less NULL terminated single list
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 needed. 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: Huang Ying <ying.huang@intel.com> Reviewed-by: Andi Kleen <ak@linux.intel.com> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Cc: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Len Brown <len.brown@intel.com>
Diffstat (limited to 'lib/Makefile')
1 files changed, 2 insertions, 0 deletions
diff --git a/lib/Makefile b/lib/Makefile
index 6b597fdb189..d770b817202 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -112,6 +112,8 @@ obj-$(CONFIG_AVERAGE) += average.o
obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o
+obj-$(CONFIG_LLIST) += llist.o
hostprogs-y := gen_crc32table
clean-files := crc32table.h