~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/llist.c

Version: ~ [ linux-6.11.5 ] ~ [ linux-6.10.14 ] ~ [ linux-6.9.12 ] ~ [ linux-6.8.12 ] ~ [ linux-6.7.12 ] ~ [ linux-6.6.58 ] ~ [ linux-6.5.13 ] ~ [ linux-6.4.16 ] ~ [ linux-6.3.13 ] ~ [ linux-6.2.16 ] ~ [ linux-6.1.114 ] ~ [ linux-6.0.19 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.169 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.228 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.284 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.322 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.336 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.337 ] ~ [ linux-4.4.302 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

Diff markup

Differences between /lib/llist.c (Version linux-6.11.5) and /lib/llist.c (Version linux-3.10.108)


  1 // SPDX-License-Identifier: GPL-2.0-only       << 
  2 /*                                                  1 /*
  3  * Lock-less NULL terminated single linked lis      2  * Lock-less NULL terminated single linked list
  4  *                                                  3  *
  5  * The basic atomic operation of this list is       4  * The basic atomic operation of this list is cmpxchg on long.  On
  6  * architectures that don't have NMI-safe cmpx      5  * architectures that don't have NMI-safe cmpxchg implementation, the
  7  * list can NOT be used in NMI handlers.  So c      6  * list can NOT be used in NMI handlers.  So code that uses the list in
  8  * an NMI handler should depend on CONFIG_ARCH      7  * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
  9  *                                                  8  *
 10  * Copyright 2010,2011 Intel Corp.                  9  * Copyright 2010,2011 Intel Corp.
 11  *   Author: Huang Ying <ying.huang@intel.com>     10  *   Author: Huang Ying <ying.huang@intel.com>
                                                   >>  11  *
                                                   >>  12  * This program is free software; you can redistribute it and/or
                                                   >>  13  * modify it under the terms of the GNU General Public License version
                                                   >>  14  * 2 as published by the Free Software Foundation;
                                                   >>  15  *
                                                   >>  16  * This program is distributed in the hope that it will be useful,
                                                   >>  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
                                                   >>  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
                                                   >>  19  * GNU General Public License for more details.
                                                   >>  20  *
                                                   >>  21  * You should have received a copy of the GNU General Public License
                                                   >>  22  * along with this program; if not, write to the Free Software
                                                   >>  23  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 12  */                                                24  */
 13 #include <linux/kernel.h>                          25 #include <linux/kernel.h>
 14 #include <linux/export.h>                          26 #include <linux/export.h>
                                                   >>  27 #include <linux/interrupt.h>
 15 #include <linux/llist.h>                           28 #include <linux/llist.h>
 16                                                    29 
 17                                                    30 
 18 /**                                                31 /**
 19  * llist_add_batch - add several linked entrie     32  * llist_add_batch - add several linked entries in batch
 20  * @new_first:  first entry in batch to be add     33  * @new_first:  first entry in batch to be added
 21  * @new_last:   last entry in batch to be adde     34  * @new_last:   last entry in batch to be added
 22  * @head:       the head for your lock-less li     35  * @head:       the head for your lock-less list
 23  *                                                 36  *
 24  * Return whether list is empty before adding.     37  * Return whether list is empty before adding.
 25  */                                                38  */
 26 bool llist_add_batch(struct llist_node *new_fi     39 bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
 27                      struct llist_head *head)      40                      struct llist_head *head)
 28 {                                                  41 {
 29         struct llist_node *first = READ_ONCE(h !!  42         struct llist_node *entry, *old_entry;
 30                                                    43 
 31         do {                                   !!  44         entry = head->first;
 32                 new_last->next = first;        !!  45         for (;;) {
 33         } while (!try_cmpxchg(&head->first, &f !!  46                 old_entry = entry;
                                                   >>  47                 new_last->next = entry;
                                                   >>  48                 entry = cmpxchg(&head->first, old_entry, new_first);
                                                   >>  49                 if (entry == old_entry)
                                                   >>  50                         break;
                                                   >>  51         }
 34                                                    52 
 35         return !first;                         !!  53         return old_entry == NULL;
 36 }                                                  54 }
 37 EXPORT_SYMBOL_GPL(llist_add_batch);                55 EXPORT_SYMBOL_GPL(llist_add_batch);
 38                                                    56 
 39 /**                                                57 /**
 40  * llist_del_first - delete the first entry of     58  * llist_del_first - delete the first entry of lock-less list
 41  * @head:       the head for your lock-less li     59  * @head:       the head for your lock-less list
 42  *                                                 60  *
 43  * If list is empty, return NULL, otherwise, r     61  * If list is empty, return NULL, otherwise, return the first entry
 44  * deleted, this is the newest added one.          62  * deleted, this is the newest added one.
 45  *                                                 63  *
 46  * Only one llist_del_first user can be used s     64  * Only one llist_del_first user can be used simultaneously with
 47  * multiple llist_add users without lock.  Bec     65  * multiple llist_add users without lock.  Because otherwise
 48  * llist_del_first, llist_add, llist_add (or l     66  * llist_del_first, llist_add, llist_add (or llist_del_all, llist_add,
 49  * llist_add) sequence in another user may cha     67  * llist_add) sequence in another user may change @head->first->next,
 50  * but keep @head->first.  If multiple consume     68  * but keep @head->first.  If multiple consumers are needed, please
 51  * use llist_del_all or use lock between consu     69  * use llist_del_all or use lock between consumers.
 52  */                                                70  */
 53 struct llist_node *llist_del_first(struct llis     71 struct llist_node *llist_del_first(struct llist_head *head)
 54 {                                                  72 {
 55         struct llist_node *entry, *next;       !!  73         struct llist_node *entry, *old_entry, *next;
 56                                                    74 
 57         entry = smp_load_acquire(&head->first) !!  75         entry = head->first;
 58         do {                                   !!  76         for (;;) {
 59                 if (entry == NULL)                 77                 if (entry == NULL)
 60                         return NULL;               78                         return NULL;
 61                 next = READ_ONCE(entry->next); !!  79                 old_entry = entry;
 62         } while (!try_cmpxchg(&head->first, &e !!  80                 next = entry->next;
                                                   >>  81                 entry = cmpxchg(&head->first, old_entry, next);
                                                   >>  82                 if (entry == old_entry)
                                                   >>  83                         break;
                                                   >>  84         }
 63                                                    85 
 64         return entry;                              86         return entry;
 65 }                                                  87 }
 66 EXPORT_SYMBOL_GPL(llist_del_first);                88 EXPORT_SYMBOL_GPL(llist_del_first);
 67                                                << 
 68 /**                                            << 
 69  * llist_del_first_this - delete given entry o << 
 70  * @head:       the head for your lock-less li << 
 71  * @this:       a list entry.                  << 
 72  *                                             << 
 73  * If head of the list is given entry, delete  << 
 74  * return %false.                              << 
 75  *                                             << 
 76  * Multiple callers can safely call this concu << 
 77  * llist_add() callers, providing all the call << 
 78  */                                            << 
 79 bool llist_del_first_this(struct llist_head *h << 
 80                           struct llist_node *t << 
 81 {                                              << 
 82         struct llist_node *entry, *next;       << 
 83                                                << 
 84         /* acquire ensures orderig wrt try_cmp << 
 85         entry = smp_load_acquire(&head->first) << 
 86         do {                                   << 
 87                 if (entry != this)             << 
 88                         return false;          << 
 89                 next = READ_ONCE(entry->next); << 
 90         } while (!try_cmpxchg(&head->first, &e << 
 91                                                << 
 92         return true;                           << 
 93 }                                              << 
 94 EXPORT_SYMBOL_GPL(llist_del_first_this);       << 
 95                                                << 
 96 /**                                            << 
 97  * llist_reverse_order - reverse order of a ll << 
 98  * @head:       first item of the list to be r << 
 99  *                                             << 
100  * Reverse the order of a chain of llist entri << 
101  * new first entry.                            << 
102  */                                            << 
103 struct llist_node *llist_reverse_order(struct  << 
104 {                                              << 
105         struct llist_node *new_head = NULL;    << 
106                                                << 
107         while (head) {                         << 
108                 struct llist_node *tmp = head; << 
109                 head = head->next;             << 
110                 tmp->next = new_head;          << 
111                 new_head = tmp;                << 
112         }                                      << 
113                                                << 
114         return new_head;                       << 
115 }                                              << 
116 EXPORT_SYMBOL_GPL(llist_reverse_order);        << 
117                                                    89 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

sflogo.php