lib/rculist.h

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2013, 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #ifndef RCULIST_H
  17 #define RCULIST_H 1
  18
  19 /* A single writer multiple RCU-reader doubly linked list.
  20  *
  21  * RCU readers may iterate over the list at the same time as a writer is
  22  * modifying the list.  Multiple writers can be supported by use of mutual
  23  * exclusion, but rculist does not provide that, as the user of rculist
  24  * typically does that already.
  25  *
  26  * To be RCU-friendly, the struct rculist instances must be freed via
  27  * ovsrcu_postpone().
  28  *
  29  * The API is almost the same as for struct ovs_list, with the following
  30  * exceptions:
  31  *
  32  * - The 'prev' pointer may not be accessed by the user.
  33  * - The 'next' pointer should be accessed via rculist_next() by readers, and
  34  *   rculist_next_protected() by the writer.
  35  * - No rculist_moved(): due to the memory management limitation stated above,
  36  *   rculist instances may not be reallocated, as realloc may instantly free
  37  *   the old memory.
  38  * - rculist_front() returns a const pointer to accommodate for an RCU reader.
  39  * - rculist_splice_hidden(): Spliced elements may not have been visible to
  40  *   RCU readers before the operation.
  41  * - rculist_poison(): Only poisons the 'prev' pointer.
  42  *
  43  * The following functions are variations of the struct ovs_list functions with
  44  * similar names, but are now restricted to the writer use:
  45  *
  46  * - rculist_back_protected()
  47  * - rculist_is_short_protected()
  48  * - rculist_is_singleton_protected()
  49  */
  50
  51 #include <stdbool.h>
  52 #include <stddef.h>
  53 #include "ovs-rcu.h"
  54 #include "util.h"
  55
  56 /* A non-existing mutex to make it more difficult for an user to accidentally
  57  * keep using the 'prev' pointer.  This may be helpful when porting code from
  58  * struct ovs_list to rculist. */
  59 extern struct ovs_mutex rculist_fake_mutex;
  60
  61 /* Doubly linked list head or element. */
  62 struct rculist {
  63     /* Previous list element. */
  64     struct rculist *prev OVS_GUARDED_BY(rculist_fake_mutex);
  65
  66     /* Next list element. */
  67     OVSRCU_TYPE(struct rculist *) next;
  68 };
  69
  70 /* Easier access to 'next' member. */
  71 static inline const struct rculist *rculist_next(const struct rculist *);
  72 static inline struct rculist *rculist_next_protected(const struct rculist *);
  73
  74 /* List initialization. */
  75 #define RCUOVS_LIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) }
  76
  77 static inline void rculist_init(struct rculist *list);
  78 static inline void rculist_poison(struct rculist *elem);
  79
  80 /* List insertion. */
  81 static inline void rculist_insert(struct rculist *list, struct rculist *elem);
  82 static inline void rculist_splice_hidden(struct rculist *before,
  83                                          struct rculist *first,
  84                                          struct rculist *last);
  85 static inline void rculist_push_front(struct rculist *list,
  86                                       struct rculist *elem);
  87 static inline void rculist_push_back(struct rculist *list,
  88                                      struct rculist *elem);
  89 static inline void rculist_replace(struct rculist *replacement,
  90                                    struct rculist *replaced);
  91 static inline void rculist_move(struct rculist *dst, struct rculist *src);
  92
  93 /* List removal. */
  94 static inline struct rculist *rculist_remove(struct rculist *elem);
  95 static inline struct rculist *rculist_pop_front(struct rculist *list);
  96 static inline struct rculist *rculist_pop_back(struct rculist *list);
  97
  98 /* List elements. */
  99 static inline const struct rculist *rculist_front(const struct rculist *);
 100 static inline struct rculist *rculist_back_protected(const struct rculist *);
 101
 102 /* List properties. */
 103 static inline size_t rculist_size(const struct rculist *);
 104 static inline bool rculist_is_empty(const struct rculist *);
 105 static inline bool rculist_is_singleton_protected(const struct rculist *);
 106 static inline bool rculist_is_short_protected(const struct rculist *);
 107
 108 \f
 109 /* Inline implementations. */
 110
 111 static inline const struct rculist *
 112 rculist_next(const struct rculist *list)
 113 {
 114     return ovsrcu_get(struct rculist *, &list->next);
 115 }
 116
 117 static inline struct rculist *
 118 rculist_next_protected(const struct rculist *list)
 119
 120 {
 121     return ovsrcu_get_protected(struct rculist *, &list->next);
 122 }
 123
 124 static inline void
 125 rculist_init(struct rculist *list)
 126     OVS_NO_THREAD_SAFETY_ANALYSIS
 127 {
 128     list->prev = list;
 129     ovsrcu_init(&list->next, list);
 130 }
 131
 132 #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc)
 133
 134 /* Initializes 'list' with pointers that will (probably) cause segfaults if
 135  * dereferenced and, better yet, show up clearly in a debugger. */
 136 static inline void
 137 rculist_poison(struct rculist *list)
 138     OVS_NO_THREAD_SAFETY_ANALYSIS
 139 {
 140     list->prev = RCULIST_POISON;
 141 }
 142
 143 /* Initializes 'list' with pointers that will (probably) cause segfaults if
 144  * dereferenced and, better yet, show up clearly in a debugger.
 145  *
 146  * This variant poisons also the next pointer, so this may not be called if
 147  * this list element is still visible to RCU readers. */
 148 static inline void
 149 rculist_poison__(struct rculist *list)
 150     OVS_NO_THREAD_SAFETY_ANALYSIS
 151 {
 152     rculist_poison(list);
 153     ovsrcu_set_hidden(&list->next, RCULIST_POISON);
 154 }
 155
 156 /* rculist insertion. */
 157 static inline void
 158 rculist_insert(struct rculist *before, struct rculist *elem)
 159     OVS_NO_THREAD_SAFETY_ANALYSIS
 160 {
 161     elem->prev = before->prev;
 162     ovsrcu_set_hidden(&elem->next, before);
 163     ovsrcu_set(&before->prev->next, elem);
 164     before->prev = elem;
 165 }
 166
 167 /* Removes elements 'first' though 'last' (exclusive) from their current list,
 168  * which may NOT be visible to any other threads (== be hidden from them),
 169  * then inserts them just before 'before'. */
 170 static inline void
 171 rculist_splice_hidden(struct rculist *before, struct rculist *first,
 172                       struct rculist *last)
 173     OVS_NO_THREAD_SAFETY_ANALYSIS
 174 {
 175     struct rculist *last_next;
 176
 177     if (first == last) {
 178         return;
 179     }
 180     last = last->prev;
 181
 182     /* Cleanly remove 'first'...'last' from its current list. */
 183     last_next = rculist_next_protected(last);
 184     last_next->prev = first->prev;
 185     ovsrcu_set_hidden(&first->prev->next, last_next);
 186
 187     /* Splice 'first'...'last' into new list. */
 188     first->prev = before->prev;
 189     ovsrcu_set(&last->next, before);
 190     ovsrcu_set(&before->prev->next, first);
 191     before->prev = last;
 192 }
 193
 194 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
 195  * 'list'. */
 196 static inline void
 197 rculist_push_front(struct rculist *list, struct rculist *elem)
 198 {
 199     rculist_insert(rculist_next_protected(list), elem);
 200 }
 201
 202 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
 203  * 'list'. */
 204 static inline void
 205 rculist_push_back(struct rculist *list, struct rculist *elem)
 206 {
 207     rculist_insert(list, elem);
 208 }
 209
 210 /* Puts 'element' in the position currently occupied by 'position'.
 211  *
 212  * Afterward, 'position' is not linked to from the list any more, but still
 213  * links to the nodes in the list, and may still be referenced by other threads
 214  * until all other threads quiesce.  The replaced node ('position') may not be
 215  * re-inserted, re-initialized, or deleted until after all other threads have
 216  * quiesced (use ovsrcu_postpone). */
 217 static inline void
 218 rculist_replace(struct rculist *element, struct rculist *position)
 219     OVS_NO_THREAD_SAFETY_ANALYSIS
 220 {
 221     struct rculist *position_next = rculist_next_protected(position);
 222
 223     ovsrcu_set_hidden(&element->next, position_next);
 224     position_next->prev = element;
 225     element->prev = position->prev;
 226     ovsrcu_set(&element->prev->next, element);
 227     rculist_poison(position);
 228 }
 229
 230 /* Initializes 'dst' with the contents of 'src', compensating for moving it
 231  * around in memory.  The effect is that, if 'src' was the head of a list, now
 232  * 'dst' is the head of a list containing the same elements.
 233  *
 234  * Memory for 'src' must be kept around until the next RCU quiescent period.
 235  * rculist cannot be simply reallocated, so there is no rculist_moved(). */
 236 static inline void
 237 rculist_move(struct rculist *dst, struct rculist *src)
 238     OVS_NO_THREAD_SAFETY_ANALYSIS
 239 {
 240     if (!rculist_is_empty(src)) {
 241         struct rculist *src_next = rculist_next_protected(src);
 242
 243         dst->prev = src->prev;
 244         ovsrcu_set_hidden(&dst->next, src_next);
 245
 246         src_next->prev = dst;
 247         ovsrcu_set(&src->prev->next, dst);
 248     } else {
 249         rculist_init(dst);
 250     }
 251     rculist_poison(src);
 252 }
 253
 254 /* Removes 'elem' from its list and returns the element that followed it.
 255  * Has no effect when 'elem' is initialized, but not in a list.
 256  * Undefined behavior if 'elem' is not initialized.
 257  *
 258  * Afterward, 'elem' is not linked to from the list any more, but still links
 259  * to the nodes in the list, and may still be referenced by other threads until
 260  * all other threads quiesce.  The removed node ('elem') may not be
 261  * re-inserted, re-initialized, or deleted until after all other threads have
 262  * quiesced (use ovsrcu_postpone).
 263  */
 264 static inline struct rculist *
 265 rculist_remove(struct rculist *elem)
 266     OVS_NO_THREAD_SAFETY_ANALYSIS
 267 {
 268     struct rculist *elem_next = rculist_next_protected(elem);
 269
 270     elem_next->prev = elem->prev;
 271     ovsrcu_set(&elem->prev->next, elem_next);
 272     rculist_poison(elem);
 273     return elem_next;
 274 }
 275
 276 /* Removes the front element from 'list' and returns it.  Undefined behavior if
 277  * 'list' is empty before removal.
 278  *
 279  * Afterward, teh returned former first node is not linked to from the list any
 280  * more, but still links to the nodes in the list, and may still be referenced
 281  * by other threads until all other threads quiesce.  The returned node may not
 282  * be re-inserted, re-initialized, or deleted until after all other threads
 283  * have quiesced (use ovsrcu_postpone). */
 284 static inline struct rculist *
 285 rculist_pop_front(struct rculist *list)
 286     OVS_NO_THREAD_SAFETY_ANALYSIS
 287 {
 288     struct rculist *front = rculist_next_protected(list);
 289     rculist_remove(front);
 290     return front;
 291 }
 292
 293 /* Removes the back element from 'list' and returns it.
 294  * Undefined behavior if 'list' is empty before removal.
 295  *
 296  * Afterward, teh returned former last node is not linked to from the list any
 297  * more, but still links to the nodes in the list, and may still be referenced
 298  * by other threads until all other threads quiesce.  The returned node may not
 299  * be re-inserted, re-initialized, or deleted until after all other threads
 300  * have quiesced (use ovsrcu_postpone). */
 301 static inline struct rculist *
 302 rculist_pop_back(struct rculist *list)
 303     OVS_NO_THREAD_SAFETY_ANALYSIS
 304 {
 305     struct rculist *back = list->prev;
 306     rculist_remove(back);
 307     return back;
 308 }
 309
 310 /* Returns the front element in 'list_'.
 311  * Undefined behavior if 'list_' is empty. */
 312 static inline const struct rculist *
 313 rculist_front(const struct rculist *list)
 314 {
 315     ovs_assert(!rculist_is_empty(list));
 316
 317     return rculist_next(list);
 318 }
 319
 320 /* Returns the back element in 'list_'.
 321  * Returns the 'list_' itself, if 'list_' is empty. */
 322 static inline struct rculist *
 323 rculist_back_protected(const struct rculist *list)
 324     OVS_NO_THREAD_SAFETY_ANALYSIS
 325 {
 326     return CONST_CAST(struct rculist *, list)->prev;
 327 }
 328
 329 /* Returns the number of elements in 'list'.
 330  * Runs in O(n) in the number of elements. */
 331 static inline size_t
 332 rculist_size(const struct rculist *list)
 333 {
 334     const struct rculist *e;
 335     size_t cnt = 0;
 336
 337     for (e = rculist_next(list); e != list; e = rculist_next(e)) {
 338         cnt++;
 339     }
 340     return cnt;
 341 }
 342
 343 /* Returns true if 'list' is empty, false otherwise. */
 344 static inline bool
 345 rculist_is_empty(const struct rculist *list)
 346 {
 347     return rculist_next(list) == list;
 348 }
 349
 350 /* Returns true if 'list' has 0 or 1 elements, false otherwise. */
 351 static inline bool
 352 rculist_is_short_protected(const struct rculist *list)
 353     OVS_NO_THREAD_SAFETY_ANALYSIS
 354 {
 355     return rculist_next_protected(list) == list->prev;
 356 }
 357
 358 /* Returns true if 'list' has exactly 1 element, false otherwise. */
 359 static inline bool
 360 rculist_is_singleton_protected(const struct rculist *list)
 361     OVS_NO_THREAD_SAFETY_ANALYSIS
 362 {
 363     const struct rculist *list_next = rculist_next_protected(list);
 364
 365     return list_next == list->prev && list_next != list;
 366 }
 367
 368 #define RCULIST_FOR_EACH(ITER, MEMBER, RCULIST)                         \
 369     for (INIT_CONTAINER(ITER, rculist_next(RCULIST), MEMBER);           \
 370          &(ITER)->MEMBER != (RCULIST);                                  \
 371          ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER))
 372 #define RCULIST_FOR_EACH_CONTINUE(ITER, MEMBER, RCULIST)                \
 373     for (ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER); \
 374          &(ITER)->MEMBER != (RCULIST);                                  \
 375          ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER))
 376
 377 #define RCULIST_FOR_EACH_REVERSE_PROTECTED(ITER, MEMBER, RCULIST)       \
 378     for (INIT_CONTAINER(ITER, (RCULIST)->prev, MEMBER);                 \
 379          &(ITER)->MEMBER != (RCULIST);                                  \
 380          ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
 381 #define RCULIST_FOR_EACH_REVERSE_PROTECTED_CONTINUE(ITER, MEMBER, RCULIST) \
 382     for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER);           \
 383          &(ITER)->MEMBER != (RCULIST);                                  \
 384          ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
 385
 386 #define RCULIST_FOR_EACH_PROTECTED(ITER, MEMBER, RCULIST)               \
 387     for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \
 388          &(ITER)->MEMBER != (RCULIST);                                  \
 389          ASSIGN_CONTAINER(ITER, rculist_next_protected(&(ITER)->MEMBER), \
 390                           MEMBER))
 391
 392 #define RCULIST_FOR_EACH_SAFE_PROTECTED(ITER, NEXT, MEMBER, RCULIST)    \
 393     for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \
 394          (&(ITER)->MEMBER != (RCULIST)                                  \
 395           ? INIT_CONTAINER(NEXT, rculist_next_protected(&(ITER)->MEMBER), \
 396                            MEMBER), 1 : 0);                             \
 397          (ITER) = (NEXT))
 398
 399 #endif /* rculist.h */