^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Lock-less NULL terminated single linked list
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * The basic atomic operation of this list is cmpxchg on long. On
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * architectures that don't have NMI-safe cmpxchg implementation, the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * list can NOT be used in NMI handlers. So code that uses the list in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * Copyright 2010,2011 Intel Corp.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * Author: Huang Ying <ying.huang@intel.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #include <linux/export.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) #include <linux/llist.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * llist_add_batch - add several linked entries in batch
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * @new_first: first entry in batch to be added
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * @new_last: last entry in batch to be added
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * @head: the head for your lock-less list
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * Return whether list is empty before adding.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) struct llist_head *head)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) struct llist_node *first;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) new_last->next = first = READ_ONCE(head->first);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) } while (cmpxchg(&head->first, first, new_first) != first);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) return !first;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) EXPORT_SYMBOL_GPL(llist_add_batch);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) * llist_del_first - delete the first entry of lock-less list
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * @head: the head for your lock-less list
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) * If list is empty, return NULL, otherwise, return the first entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * deleted, this is the newest added one.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) * Only one llist_del_first user can be used simultaneously with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) * multiple llist_add users without lock. Because otherwise
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) * llist_del_first, llist_add, llist_add (or llist_del_all, llist_add,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) * llist_add) sequence in another user may change @head->first->next,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * but keep @head->first. If multiple consumers are needed, please
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) * use llist_del_all or use lock between consumers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) struct llist_node *llist_del_first(struct llist_head *head)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) struct llist_node *entry, *old_entry, *next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) entry = smp_load_acquire(&head->first);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) if (entry == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) old_entry = entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) next = READ_ONCE(entry->next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) entry = cmpxchg(&head->first, old_entry, next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) if (entry == old_entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) return entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) EXPORT_SYMBOL_GPL(llist_del_first);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) * llist_reverse_order - reverse order of a llist chain
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * @head: first item of the list to be reversed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) * Reverse the order of a chain of llist entries and return the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) * new first entry.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) struct llist_node *llist_reverse_order(struct llist_node *head)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) struct llist_node *new_head = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) while (head) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) struct llist_node *tmp = head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) head = head->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) tmp->next = new_head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) new_head = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) return new_head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) EXPORT_SYMBOL_GPL(llist_reverse_order);
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags