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  * exeptions:
  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(): Immediately poisons the 'prev' pointer, and schedules
  42  *   ovsrcu_postpone() to poison the 'next' pointer.  This issues a memory
  43  *   write operation to the list element, hopefully crashing the program if
  44  *   the list node was freed or re-used too early.
  45  *
  46  * The following functions are variations of the struct ovs_list functions with
  47  * similar names, but are now restricted to the writer use:
  48  *
  49  * - rculist_back_protected()
  50  * - rculist_is_short_protected()
  51  * - rculist_is_singleton_protected()
  52  */
  53
  54 #include <stdbool.h>
  55 #include <stddef.h>
  56 #include "ovs-rcu.h"
  57 #include "util.h"
  58
  59 /* A non-existing mutex to make it more difficult for an user to accidentally
  60  * keep using the 'prev' pointer.  This may be helpful when porting code from
  61  * struct ovs_list to rculist. */
  62 extern struct ovs_mutex rculist_fake_mutex;
  63
  64 /* Doubly linked list head or element. */
  65 struct rculist {
  66     /* Previous list element. */
  67     struct rculist *prev OVS_GUARDED_BY(rculist_fake_mutex);
  68
  69     /* Next list element. */
  70     OVSRCU_TYPE(struct rculist *) next;
  71 };
  72
  73 /* Easier access to 'next' member. */
  74 static inline const struct rculist *rculist_next(const struct rculist *);
  75 static inline struct rculist *rculist_next_protected(const struct rculist *);
  76
  77 /* List initialization. */
  78 #define RCULIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) }
  79
  80 static inline void rculist_init(struct rculist *list);
  81 static inline void rculist_poison(struct rculist *elem);
  82
  83 /* List insertion. */
  84 static inline void rculist_insert(struct rculist *list, struct rculist *elem);
  85 static inline void rculist_splice_hidden(struct rculist *before,
  86                                          struct rculist *first,
  87                                          struct rculist *last);
  88 static inline void rculist_push_front(struct rculist *list,
  89                                       struct rculist *elem);
  90 static inline void rculist_push_back(struct rculist *list,
  91                                      struct rculist *elem);
  92 static inline void rculist_replace(struct rculist *replacement,
  93                                    struct rculist *replaced);
  94 static inline void rculist_move(struct rculist *dst, struct rculist *src);
  95
  96 /* List removal. */
  97 static inline struct rculist *rculist_remove(struct rculist *elem);
  98 static inline struct rculist *rculist_pop_front(struct rculist *list);
  99 static inline struct rculist *rculist_pop_back(struct rculist *list);
 100
 101 /* List elements. */
 102 static inline const struct rculist *rculist_front(const struct rculist *);
 103 static inline struct rculist *rculist_back_protected(const struct rculist *);
 104
 105 /* List properties. */
 106 static inline size_t rculist_size(const struct rculist *);
 107 static inline bool rculist_is_empty(const struct rculist *);
 108 static inline bool rculist_is_singleton_protected(const struct rculist *);
 109 static inline bool rculist_is_short_protected(const struct rculist *);
 110
 111 \f
 112 /* Inline implementations. */
 113
 114 static inline const struct rculist *
 115 rculist_next(const struct rculist *list)
 116 {
 117     return ovsrcu_get(struct rculist *, &list->next);
 118 }
 119
 120 static inline struct rculist *
 121 rculist_next_protected(const struct rculist *list)
 122
 123 {
 124     return ovsrcu_get_protected(struct rculist *, &list->next);
 125 }
 126
 127 static inline void
 128 rculist_init(struct rculist *list)
 129     OVS_NO_THREAD_SAFETY_ANALYSIS
 130 {
 131     list->prev = list;
 132     ovsrcu_init(&list->next, list);
 133 }
 134
 135 #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc)
 136
 137 void rculist_poison__(struct rculist *list);
 138
 139 /* Initializes 'list' with pointers that will (probably) cause segfaults if
 140  * dereferenced and, better yet, show up clearly in a debugger. */
 141 static inline void
 142 rculist_poison(struct rculist *list)
 143     OVS_NO_THREAD_SAFETY_ANALYSIS
 144 {
 145     list->prev = RCULIST_POISON;
 146     ovsrcu_postpone(rculist_poison__, list);
 147 }
 148
 149 /* rculist insertion. */
 150 static inline void
 151 rculist_insert(struct rculist *before, struct rculist *elem)
 152     OVS_NO_THREAD_SAFETY_ANALYSIS
 153 {
 154     elem->prev = before->prev;
 155     ovsrcu_set_hidden(&elem->next, before);
 156     ovsrcu_set(&before->prev->next, elem);
 157     before->prev = elem;
 158 }
 159
 160 /* Removes elements 'first' though 'last' (exclusive) from their current list,
 161  * which may NOT be visible to any other threads (== be hidden from them),
 162  * then inserts them just before 'before'. */
 163 static inline void
 164 rculist_splice_hidden(struct rculist *before, struct rculist *first,
 165                       struct rculist *last)
 166     OVS_NO_THREAD_SAFETY_ANALYSIS
 167 {
 168     struct rculist *last_next;
 169
 170     if (first == last) {
 171         return;
 172     }
 173     last = last->prev;
 174
 175     /* Cleanly remove 'first'...'last' from its current list. */
 176     last_next = rculist_next_protected(last);
 177     last_next->prev = first->prev;
 178     ovsrcu_set_hidden(&first->prev->next, last_next);
 179
 180     /* Splice 'first'...'last' into new list. */
 181     first->prev = before->prev;
 182     ovsrcu_set(&last->next, before);
 183     ovsrcu_set(&before->prev->next, first);
 184     before->prev = last;
 185 }
 186
 187 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
 188  * 'list'. */
 189 static inline void
 190 rculist_push_front(struct rculist *list, struct rculist *elem)
 191 {
 192     rculist_insert(rculist_next_protected(list), elem);
 193 }
 194
 195 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
 196  * 'list'. */
 197 static inline void
 198 rculist_push_back(struct rculist *list, struct rculist *elem)
 199 {
 200     rculist_insert(list, elem);
 201 }
 202
 203 /* Puts 'element' in the position currently occupied by 'position'.
 204  *
 205  * Afterward, 'position' is not linked to from the list any more, but still
 206  * links to the nodes in the list, and may still be referenced by other threads
 207  * until all other threads quiesce.  The replaced node ('position') may not be
 208  * re-inserted, re-initialized, or deleted until after all other threads have
 209  * quiesced (use ovsrcu_postpone). */
 210 static inline void
 211 rculist_replace(struct rculist *element, struct rculist *position)
 212     OVS_NO_THREAD_SAFETY_ANALYSIS
 213 {
 214     struct rculist *position_next = rculist_next_protected(position);
 215
 216     ovsrcu_set_hidden(&element->next, position_next);
 217     position_next->prev = element;
 218     element->prev = position->prev;
 219     ovsrcu_set(&element->prev->next, element);
 220
 221 #ifndef NDEBUG
 222     rculist_poison(position); /* XXX: Some overhead due to ovsrcu_postpone() */
 223 #endif
 224 }
 225
 226 /* Initializes 'dst' with the contents of 'src', compensating for moving it
 227  * around in memory.  The effect is that, if 'src' was the head of a list, now
 228  * 'dst' is the head of a list containing the same elements.
 229  *
 230  * Memory for 'src' must be kept around until the next RCU quiescent period.
 231  * rculist cannot be simply reallocated, so there is no rculist_moved(). */
 232 static inline void
 233 rculist_move(struct rculist *dst, struct rculist *src)
 234     OVS_NO_THREAD_SAFETY_ANALYSIS
 235 {
 236     if (!rculist_is_empty(src)) {
 237         struct rculist *src_next = rculist_next_protected(src);
 238
 239         dst->prev = src->prev;
 240         ovsrcu_set_hidden(&dst->next, src_next);
 241
 242         src_next->prev = dst;
 243         ovsrcu_set(&src->prev->next, dst);
 244     } else {
 245         rculist_init(dst);
 246     }
 247
 248 #ifndef NDEBUG
 249     rculist_poison(src); /* XXX: Some overhead due to ovsrcu_postpone() */
 250 #endif
 251 }
 252
 253 /* Removes 'elem' from its list and returns the element that followed it.
 254  * Has no effect when 'elem' is initialized, but not in a list.
 255  * Undefined behavior if 'elem' is not initialized.
 256  *
 257  * Afterward, 'elem' is not linked to from the list any more, but still links
 258  * to the nodes in the list, and may still be referenced by other threads until
 259  * all other threads quiesce.  The removed node ('elem') may not be
 260  * re-inserted, re-initialized, or deleted until after all other threads have
 261  * quiesced (use ovsrcu_postpone).
 262  */
 263 static inline struct rculist *
 264 rculist_remove(struct rculist *elem)
 265     OVS_NO_THREAD_SAFETY_ANALYSIS
 266 {
 267     struct rculist *elem_next = rculist_next_protected(elem);
 268
 269     elem_next->prev = elem->prev;
 270     ovsrcu_set(&elem->prev->next, elem_next);
 271
 272 #ifndef NDEBUG
 273     rculist_poison(elem); /* XXX: Some overhead due to ovsrcu_postpone() */
 274 #endif
 275     return elem_next;
 276 }
 277
 278 /* Removes the front element from 'list' and returns it.  Undefined behavior if
 279  * 'list' is empty before removal.
 280  *
 281  * Afterward, teh returned former first node is not linked to from the list any
 282  * more, but still links to the nodes in the list, and may still be referenced
 283  * by other threads until all other threads quiesce.  The returned node may not
 284  * be re-inserted, re-initialized, or deleted until after all other threads
 285  * have quiesced (use ovsrcu_postpone). */
 286 static inline struct rculist *
 287 rculist_pop_front(struct rculist *list)
 288     OVS_NO_THREAD_SAFETY_ANALYSIS
 289 {
 290     struct rculist *front = rculist_next_protected(list);
 291     rculist_remove(front);
 292     return front;
 293 }
 294
 295 /* Removes the back element from 'list' and returns it.
 296  * Undefined behavior if 'list' is empty before removal.
 297  *
 298  * Afterward, teh returned former last node is not linked to from the list any
 299  * more, but still links to the nodes in the list, and may still be referenced
 300  * by other threads until all other threads quiesce.  The returned node may not
 301  * be re-inserted, re-initialized, or deleted until after all other threads
 302  * have quiesced (use ovsrcu_postpone). */
 303 static inline struct rculist *
 304 rculist_pop_back(struct rculist *list)
 305     OVS_NO_THREAD_SAFETY_ANALYSIS
 306 {
 307     struct rculist *back = list->prev;
 308     rculist_remove(back);
 309     return back;
 310 }
 311
 312 /* Returns the front element in 'list_'.
 313  * Undefined behavior if 'list_' is empty. */
 314 static inline const struct rculist *
 315 rculist_front(const struct rculist *list)
 316 {
 317     ovs_assert(!rculist_is_empty(list));
 318
 319     return rculist_next(list);
 320 }
 321
 322 /* Returns the back element in 'list_'.
 323  * Returns the 'list_' itself, if 'list_' is empty. */
 324 static inline struct rculist *
 325 rculist_back_protected(const struct rculist *list)
 326     OVS_NO_THREAD_SAFETY_ANALYSIS
 327 {
 328     return CONST_CAST(struct rculist *, list)->prev;
 329 }
 330
 331 /* Returns the number of elements in 'list'.
 332  * Runs in O(n) in the number of elements. */
 333 static inline size_t
 334 rculist_size(const struct rculist *list)
 335 {
 336     const struct rculist *e;
 337     size_t cnt = 0;
 338
 339     for (e = rculist_next(list); e != list; e = rculist_next(e)) {
 340         cnt++;
 341     }
 342     return cnt;
 343 }
 344
 345 /* Returns true if 'list' is empty, false otherwise. */
 346 static inline bool
 347 rculist_is_empty(const struct rculist *list)
 348 {
 349     return rculist_next(list) == list;
 350 }
 351
 352 /* Returns true if 'list' has 0 or 1 elements, false otherwise. */
 353 static inline bool
 354 rculist_is_short_protected(const struct rculist *list)
 355     OVS_NO_THREAD_SAFETY_ANALYSIS
 356 {
 357     return rculist_next_protected(list) == list->prev;
 358 }
 359
 360 /* Returns true if 'list' has exactly 1 element, false otherwise. */
 361 static inline bool
 362 rculist_is_singleton_protected(const struct rculist *list)
 363     OVS_NO_THREAD_SAFETY_ANALYSIS
 364 {
 365     const struct rculist *list_next = rculist_next_protected(list);
 366
 367     return list_next == list->prev && list_next != list;
 368 }
 369
 370 #define RCULIST_FOR_EACH(ITER, MEMBER, RCULIST)                         \
 371     for (INIT_CONTAINER(ITER, rculist_next(RCULIST), MEMBER);           \
 372          &(ITER)->MEMBER != (RCULIST);                                  \
 373          ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER))
 374 #define RCULIST_FOR_EACH_CONTINUE(ITER, MEMBER, RCULIST)                \
 375     for (ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER); \
 376          &(ITER)->MEMBER != (RCULIST);                                  \
 377          ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER))
 378
 379 #define RCULIST_FOR_EACH_REVERSE_PROTECTED(ITER, MEMBER, RCULIST)       \
 380     for (INIT_CONTAINER(ITER, (RCULIST)->prev, MEMBER);                 \
 381          &(ITER)->MEMBER != (RCULIST);                                  \
 382          ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
 383 #define RCULIST_FOR_EACH_REVERSE_PROTECTED_CONTINUE(ITER, MEMBER, RCULIST) \
 384     for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER);           \
 385          &(ITER)->MEMBER != (RCULIST);                                  \
 386          ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
 387
 388 #define RCULIST_FOR_EACH_PROTECTED(ITER, MEMBER, RCULIST)               \
 389     for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \
 390          &(ITER)->MEMBER != (RCULIST);                                  \
 391          ASSIGN_CONTAINER(ITER, rculist_next_protected(&(ITER)->MEMBER), \
 392                           MEMBER))
 393
 394 #define RCULIST_FOR_EACH_SAFE_PROTECTED(ITER, NEXT, MEMBER, RCULIST)    \
 395     for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \
 396          (&(ITER)->MEMBER != (RCULIST)                                  \
 397           ? INIT_CONTAINER(NEXT, rculist_next_protected(&(ITER)->MEMBER), \
 398                            MEMBER), 1 : 0);                             \
 399          (ITER) = (NEXT))
 400
 401 #endif /* rculist.h */