llist.c 2.5 KB

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