1 /* $NetBSD: pslist.h,v 1.7 2019/12/01 15:28:19 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2016 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #ifndef _SYS_PSLIST_H 33 #define _SYS_PSLIST_H 34 35 #include <sys/param.h> 36 #include <sys/atomic.h> 37 38 struct pslist_head; 39 struct pslist_entry; 40 41 struct pslist_head { 42 struct pslist_entry *plh_first; 43 }; 44 45 struct pslist_entry { 46 struct pslist_entry **ple_prevp; 47 struct pslist_entry *ple_next; 48 }; 49 50 #ifdef _KERNEL 51 #define _PSLIST_ASSERT KASSERT 52 #else 53 #include <assert.h> 54 #define _PSLIST_ASSERT assert 55 #endif 56 57 #define _PSLIST_POISON ((void *)1ul) 58 59 /* 60 * Initialization. Allowed only when the caller has exclusive access, 61 * excluding writers and readers. 62 */ 63 64 static __inline void 65 pslist_init(struct pslist_head *head) 66 { 67 68 head->plh_first = NULL; /* not yet published, so no atomic */ 69 } 70 71 static __inline void 72 pslist_destroy(struct pslist_head *head __diagused) 73 { 74 75 _PSLIST_ASSERT(head->plh_first == NULL); 76 } 77 78 static __inline void 79 pslist_entry_init(struct pslist_entry *entry) 80 { 81 82 entry->ple_next = NULL; 83 entry->ple_prevp = NULL; 84 } 85 86 static __inline void 87 pslist_entry_destroy(struct pslist_entry *entry) 88 { 89 90 _PSLIST_ASSERT(entry->ple_prevp == NULL); 91 92 /* 93 * Poison the next entry. If we used NULL here, then readers 94 * would think they were simply at the end of the list. 95 * Instead, cause readers to crash. 96 */ 97 atomic_store_relaxed(&entry->ple_next, _PSLIST_POISON); 98 } 99 100 /* 101 * Writer operations. Caller must exclude other writers, but not 102 * necessarily readers. 103 * 104 * Writes to initialize a new entry must precede its publication by 105 * writing to plh_first / ple_next / *ple_prevp. 106 * 107 * The ple_prevp field is serialized by the caller's exclusive lock and 108 * not read by readers, and hence its ordering relative to the internal 109 * memory barriers is inconsequential. 110 */ 111 112 static __inline void 113 pslist_writer_insert_head(struct pslist_head *head, struct pslist_entry *new) 114 { 115 116 _PSLIST_ASSERT(head->plh_first == NULL || 117 head->plh_first->ple_prevp == &head->plh_first); 118 _PSLIST_ASSERT(new->ple_next == NULL); 119 _PSLIST_ASSERT(new->ple_prevp == NULL); 120 121 new->ple_prevp = &head->plh_first; 122 new->ple_next = head->plh_first; /* not yet published, so no atomic */ 123 if (head->plh_first != NULL) 124 head->plh_first->ple_prevp = &new->ple_next; 125 atomic_store_release(&head->plh_first, new); 126 } 127 128 static __inline void 129 pslist_writer_insert_before(struct pslist_entry *entry, 130 struct pslist_entry *new) 131 { 132 133 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 134 _PSLIST_ASSERT(entry->ple_prevp != NULL); 135 _PSLIST_ASSERT(*entry->ple_prevp == entry); 136 _PSLIST_ASSERT(new->ple_next == NULL); 137 _PSLIST_ASSERT(new->ple_prevp == NULL); 138 139 new->ple_prevp = entry->ple_prevp; 140 new->ple_next = entry; /* not yet published, so no atomic */ 141 142 /* 143 * Pairs with atomic_load_consume in pslist_reader_first or 144 * pslist_reader_next. 145 */ 146 atomic_store_release(entry->ple_prevp, new); 147 148 entry->ple_prevp = &new->ple_next; 149 } 150 151 static __inline void 152 pslist_writer_insert_after(struct pslist_entry *entry, 153 struct pslist_entry *new) 154 { 155 156 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 157 _PSLIST_ASSERT(entry->ple_prevp != NULL); 158 _PSLIST_ASSERT(*entry->ple_prevp == entry); 159 _PSLIST_ASSERT(new->ple_next == NULL); 160 _PSLIST_ASSERT(new->ple_prevp == NULL); 161 162 new->ple_prevp = &entry->ple_next; 163 new->ple_next = entry->ple_next; /* not yet published, so no atomic */ 164 if (new->ple_next != NULL) 165 new->ple_next->ple_prevp = &new->ple_next; 166 167 /* Pairs with atomic_load_consume in pslist_reader_next. */ 168 atomic_store_release(&entry->ple_next, new); 169 } 170 171 static __inline void 172 pslist_writer_remove(struct pslist_entry *entry) 173 { 174 175 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 176 _PSLIST_ASSERT(entry->ple_prevp != NULL); 177 _PSLIST_ASSERT(*entry->ple_prevp == entry); 178 179 if (entry->ple_next != NULL) 180 entry->ple_next->ple_prevp = entry->ple_prevp; 181 182 /* 183 * No need for atomic_store_release because there's no 184 * initialization that this must happen after -- the store 185 * transitions from a good state with the entry to a good state 186 * without the entry, both of which are valid for readers to 187 * witness. 188 */ 189 atomic_store_relaxed(entry->ple_prevp, entry->ple_next); 190 entry->ple_prevp = NULL; 191 192 /* 193 * Leave entry->ple_next intact so that any extant readers can 194 * continue iterating through the list. The caller must then 195 * wait for readers to drain, e.g. with pserialize_perform, 196 * before destroying and reusing the entry. 197 */ 198 } 199 200 static __inline struct pslist_entry * 201 pslist_writer_first(const struct pslist_head *head) 202 { 203 204 return head->plh_first; 205 } 206 207 static __inline struct pslist_entry * 208 pslist_writer_next(const struct pslist_entry *entry) 209 { 210 211 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 212 return entry->ple_next; 213 } 214 215 static __inline void * 216 _pslist_writer_first_container(const struct pslist_head *head, 217 const ptrdiff_t offset) 218 { 219 struct pslist_entry *first = head->plh_first; 220 221 return (first == NULL ? NULL : (char *)first - offset); 222 } 223 224 static __inline void * 225 _pslist_writer_next_container(const struct pslist_entry *entry, 226 const ptrdiff_t offset) 227 { 228 struct pslist_entry *next = entry->ple_next; 229 230 _PSLIST_ASSERT(next != _PSLIST_POISON); 231 return (next == NULL ? NULL : (char *)next - offset); 232 } 233 234 /* 235 * Reader operations. Caller must block pserialize_perform or 236 * equivalent and be bound to a CPU. Only plh_first/ple_next may be 237 * read, and only with consuming memory order so that data-dependent 238 * loads happen afterward. 239 */ 240 241 static __inline struct pslist_entry * 242 pslist_reader_first(const struct pslist_head *head) 243 { 244 /* 245 * Pairs with atomic_store_release in pslist_writer_insert_head 246 * or pslist_writer_insert_before. 247 */ 248 return atomic_load_consume(&head->plh_first); 249 } 250 251 static __inline struct pslist_entry * 252 pslist_reader_next(const struct pslist_entry *entry) 253 { 254 /* 255 * Pairs with atomic_store_release in 256 * pslist_writer_insert_before or pslist_writer_insert_after. 257 */ 258 struct pslist_entry *next = atomic_load_consume(&entry->ple_next); 259 260 _PSLIST_ASSERT(next != _PSLIST_POISON); 261 262 return next; 263 } 264 265 static __inline void * 266 _pslist_reader_first_container(const struct pslist_head *head, 267 const ptrdiff_t offset) 268 { 269 struct pslist_entry *first = pslist_reader_first(head); 270 271 if (first == NULL) 272 return NULL; 273 return (char *)first - offset; 274 } 275 276 static __inline void * 277 _pslist_reader_next_container(const struct pslist_entry *entry, 278 const ptrdiff_t offset) 279 { 280 struct pslist_entry *next = pslist_reader_next(entry); 281 282 if (next == NULL) 283 return NULL; 284 return (char *)next - offset; 285 } 286 287 /* 288 * Type-safe macros for convenience. 289 */ 290 291 #if defined(__COVERITY__) || defined(__LGTM_BOT__) 292 #define _PSLIST_VALIDATE_PTRS(P, Q) 0 293 #define _PSLIST_VALIDATE_CONTAINER(P, T, F) 0 294 #else 295 #define _PSLIST_VALIDATE_PTRS(P, Q) \ 296 (0 * sizeof((P) - (Q)) * sizeof(*(P)) * sizeof(*(Q))) 297 #define _PSLIST_VALIDATE_CONTAINER(P, T, F) \ 298 (0 * sizeof((P) - &((T *)(((char *)(P)) - offsetof(T, F)))->F)) 299 #endif 300 301 #define PSLIST_INITIALIZER { .plh_first = NULL } 302 #define PSLIST_ENTRY_INITIALIZER { .ple_next = NULL, .ple_prevp = NULL } 303 304 #define PSLIST_INIT(H) pslist_init((H)) 305 #define PSLIST_DESTROY(H) pslist_destroy((H)) 306 #define PSLIST_ENTRY_INIT(E, F) pslist_entry_init(&(E)->F) 307 #define PSLIST_ENTRY_DESTROY(E, F) pslist_entry_destroy(&(E)->F) 308 309 #define PSLIST_WRITER_INSERT_HEAD(H, V, F) \ 310 pslist_writer_insert_head((H), &(V)->F) 311 #define PSLIST_WRITER_INSERT_BEFORE(E, N, F) \ 312 pslist_writer_insert_before(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \ 313 &(N)->F) 314 #define PSLIST_WRITER_INSERT_AFTER(E, N, F) \ 315 pslist_writer_insert_after(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \ 316 &(N)->F) 317 #define PSLIST_WRITER_REMOVE(E, F) \ 318 pslist_writer_remove(&(E)->F) 319 #define PSLIST_WRITER_FIRST(H, T, F) \ 320 ((T *)(_pslist_writer_first_container((H), offsetof(T, F))) + \ 321 _PSLIST_VALIDATE_CONTAINER(pslist_writer_first(H), T, F)) 322 #define PSLIST_WRITER_NEXT(V, T, F) \ 323 ((T *)(_pslist_writer_next_container(&(V)->F, offsetof(T, F))) + \ 324 _PSLIST_VALIDATE_CONTAINER(pslist_writer_next(&(V)->F), T, F)) 325 #define PSLIST_WRITER_FOREACH(V, H, T, F) \ 326 for ((V) = PSLIST_WRITER_FIRST((H), T, F); \ 327 (V) != NULL; \ 328 (V) = PSLIST_WRITER_NEXT((V), T, F)) 329 330 #define PSLIST_READER_FIRST(H, T, F) \ 331 ((T *)(_pslist_reader_first_container((H), offsetof(T, F))) + \ 332 _PSLIST_VALIDATE_CONTAINER(pslist_reader_first(H), T, F)) 333 #define PSLIST_READER_NEXT(V, T, F) \ 334 ((T *)(_pslist_reader_next_container(&(V)->F, offsetof(T, F))) + \ 335 _PSLIST_VALIDATE_CONTAINER(pslist_reader_next(&(V)->F), T, F)) 336 #define PSLIST_READER_FOREACH(V, H, T, F) \ 337 for ((V) = PSLIST_READER_FIRST((H), T, F); \ 338 (V) != NULL; \ 339 (V) = PSLIST_READER_NEXT((V), T, F)) 340 341 #endif /* _SYS_PSLIST_H */ 342