On Tue, 31 Oct 2017, Waiman Long wrote:
Linked list is used everywhere in the Linux kernel. However, if many threads are trying to add or delete entries into the same linked list, it can create a performance bottleneck. This patch introduces a new list APIs that provide a set of distributed lists (one per CPU), each of which is protected by its own spinlock. To the callers, however, the set of lists acts like a single consolidated list. This allows list entries insertion and deletion operations to happen in parallel instead of being serialized with a global list and lock. List entry insertion is strictly per cpu. List deletion, however, can happen in a cpu other than the one that did the insertion. So we still need lock to protect the list. Because of that, there may still be a small amount of contention when deletion is being done. A new header file include/linux/dlock-list.h will be added with the associated dlock_list_head and dlock_list_node structures. The following functions are provided to manage the per-cpu list: 1. int alloc_dlock_list_heads(struct dlock_list_heads *dlist) 2. void free_dlock_list_heads(struct dlock_list_heads *dlist) 3. void dlock_list_add(struct dlock_list_node *node, struct dlock_list_heads *dlist) 4. void dlock_list_del(struct dlock_list *node) Iteration of all the list entries within a dlock list array is done by calling either the dlist_for_each_entry() or dlist_for_each_entry_safe() macros. They correspond to the list_for_each_entry() and list_for_each_entry_safe() macros respectively. The iteration states are keep in a dlock_list_iter structure that is passed to the iteration macros. Signed-off-by: Waiman Long <longman@xxxxxxxxxx> Reviewed-by: Jan Kara <jack@xxxxxxx>
Reviewed-by: Davidlohr Bueso <dbueso@xxxxxxx>
