1 /* $NetBSD: pslist.h,v 1.5 2018/04/19 21:19:07 christos 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; 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 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; 123 if (head->plh_first != NULL) 124 head->plh_first->ple_prevp = &new->ple_next; 125 membar_producer(); 126 head->plh_first = new; 127 } 128 129 static __inline void 130 pslist_writer_insert_before(struct pslist_entry *entry, 131 struct pslist_entry *new) 132 { 133 134 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 135 _PSLIST_ASSERT(entry->ple_prevp != NULL); 136 _PSLIST_ASSERT(*entry->ple_prevp == entry); 137 _PSLIST_ASSERT(new->ple_next == NULL); 138 _PSLIST_ASSERT(new->ple_prevp == NULL); 139 140 new->ple_prevp = entry->ple_prevp; 141 new->ple_next = entry; 142 membar_producer(); 143 *entry->ple_prevp = new; 144 entry->ple_prevp = &new->ple_next; 145 } 146 147 static __inline void 148 pslist_writer_insert_after(struct pslist_entry *entry, 149 struct pslist_entry *new) 150 { 151 152 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 153 _PSLIST_ASSERT(entry->ple_prevp != NULL); 154 _PSLIST_ASSERT(*entry->ple_prevp == entry); 155 _PSLIST_ASSERT(new->ple_next == NULL); 156 _PSLIST_ASSERT(new->ple_prevp == NULL); 157 158 new->ple_prevp = &entry->ple_next; 159 new->ple_next = entry->ple_next; 160 if (new->ple_next != NULL) 161 new->ple_next->ple_prevp = &new->ple_next; 162 membar_producer(); 163 entry->ple_next = new; 164 } 165 166 static __inline void 167 pslist_writer_remove(struct pslist_entry *entry) 168 { 169 170 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 171 _PSLIST_ASSERT(entry->ple_prevp != NULL); 172 _PSLIST_ASSERT(*entry->ple_prevp == entry); 173 174 if (entry->ple_next != NULL) 175 entry->ple_next->ple_prevp = entry->ple_prevp; 176 *entry->ple_prevp = entry->ple_next; 177 entry->ple_prevp = NULL; 178 179 /* 180 * Leave entry->ple_next intact so that any extant readers can 181 * continue iterating through the list. The caller must then 182 * wait for readers to drain, e.g. with pserialize_perform, 183 * before destroying and reusing the entry. 184 */ 185 } 186 187 static __inline struct pslist_entry * 188 pslist_writer_first(const struct pslist_head *head) 189 { 190 191 return head->plh_first; 192 } 193 194 static __inline struct pslist_entry * 195 pslist_writer_next(const struct pslist_entry *entry) 196 { 197 198 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 199 return entry->ple_next; 200 } 201 202 static __inline void * 203 _pslist_writer_first_container(const struct pslist_head *head, 204 const ptrdiff_t offset) 205 { 206 struct pslist_entry *first = head->plh_first; 207 208 return (first == NULL ? NULL : (char *)first - offset); 209 } 210 211 static __inline void * 212 _pslist_writer_next_container(const struct pslist_entry *entry, 213 const ptrdiff_t offset) 214 { 215 struct pslist_entry *next = entry->ple_next; 216 217 _PSLIST_ASSERT(next != _PSLIST_POISON); 218 return (next == NULL ? NULL : (char *)next - offset); 219 } 220 221 /* 222 * Reader operations. Caller must block pserialize_perform or 223 * equivalent and be bound to a CPU. Only plh_first/ple_next may be 224 * read, and after that, a membar_datadep_consumer must precede 225 * dereferencing the resulting pointer. 226 */ 227 228 static __inline struct pslist_entry * 229 pslist_reader_first(const struct pslist_head *head) 230 { 231 struct pslist_entry *first = head->plh_first; 232 233 if (first != NULL) 234 membar_datadep_consumer(); 235 236 return first; 237 } 238 239 static __inline struct pslist_entry * 240 pslist_reader_next(const struct pslist_entry *entry) 241 { 242 struct pslist_entry *next = entry->ple_next; 243 244 _PSLIST_ASSERT(next != _PSLIST_POISON); 245 if (next != NULL) 246 membar_datadep_consumer(); 247 248 return next; 249 } 250 251 static __inline void * 252 _pslist_reader_first_container(const struct pslist_head *head, 253 const ptrdiff_t offset) 254 { 255 struct pslist_entry *first = head->plh_first; 256 257 if (first == NULL) 258 return NULL; 259 membar_datadep_consumer(); 260 261 return (char *)first - offset; 262 } 263 264 static __inline void * 265 _pslist_reader_next_container(const struct pslist_entry *entry, 266 const ptrdiff_t offset) 267 { 268 struct pslist_entry *next = entry->ple_next; 269 270 _PSLIST_ASSERT(next != _PSLIST_POISON); 271 if (next == NULL) 272 return NULL; 273 membar_datadep_consumer(); 274 275 return (char *)next - offset; 276 } 277 278 /* 279 * Type-safe macros for convenience. 280 */ 281 282 #ifdef __COVERITY__ 283 #define _PSLIST_VALIDATE_PTRS(P, Q) 0 284 #define _PSLIST_VALIDATE_CONTAINER(P, T, F) 0 285 #else 286 #define _PSLIST_VALIDATE_PTRS(P, Q) \ 287 (0 * sizeof((P) - (Q)) * sizeof(*(P)) * sizeof(*(Q))) 288 #define _PSLIST_VALIDATE_CONTAINER(P, T, F) \ 289 (0 * sizeof((P) - &((T *)(((char *)(P)) - offsetof(T, F)))->F)) 290 #endif 291 292 #define PSLIST_INITIALIZER { .plh_first = NULL } 293 #define PSLIST_ENTRY_INITIALIZER { .ple_next = NULL, .ple_prevp = NULL } 294 295 #define PSLIST_INIT(H) pslist_init((H)) 296 #define PSLIST_DESTROY(H) pslist_destroy((H)) 297 #define PSLIST_ENTRY_INIT(E, F) pslist_entry_init(&(E)->F) 298 #define PSLIST_ENTRY_DESTROY(E, F) pslist_entry_destroy(&(E)->F) 299 300 #define PSLIST_WRITER_INSERT_HEAD(H, V, F) \ 301 pslist_writer_insert_head((H), &(V)->F) 302 #define PSLIST_WRITER_INSERT_BEFORE(E, N, F) \ 303 pslist_writer_insert_before(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \ 304 &(N)->F) 305 #define PSLIST_WRITER_INSERT_AFTER(E, N, F) \ 306 pslist_writer_insert_after(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \ 307 &(N)->F) 308 #define PSLIST_WRITER_REMOVE(E, F) \ 309 pslist_writer_remove(&(E)->F) 310 #define PSLIST_WRITER_FIRST(H, T, F) \ 311 ((T *)(_pslist_writer_first_container((H), offsetof(T, F))) + \ 312 _PSLIST_VALIDATE_CONTAINER(pslist_writer_first(H), T, F)) 313 #define PSLIST_WRITER_NEXT(V, T, F) \ 314 ((T *)(_pslist_writer_next_container(&(V)->F, offsetof(T, F))) + \ 315 _PSLIST_VALIDATE_CONTAINER(pslist_writer_next(&(V)->F), T, F)) 316 #define PSLIST_WRITER_FOREACH(V, H, T, F) \ 317 for ((V) = PSLIST_WRITER_FIRST((H), T, F); \ 318 (V) != NULL; \ 319 (V) = PSLIST_WRITER_NEXT((V), T, F)) 320 321 #define PSLIST_READER_FIRST(H, T, F) \ 322 ((T *)(_pslist_reader_first_container((H), offsetof(T, F))) + \ 323 _PSLIST_VALIDATE_CONTAINER(pslist_reader_first(H), T, F)) 324 #define PSLIST_READER_NEXT(V, T, F) \ 325 ((T *)(_pslist_reader_next_container(&(V)->F, offsetof(T, F))) + \ 326 _PSLIST_VALIDATE_CONTAINER(pslist_reader_next(&(V)->F), T, F)) 327 #define PSLIST_READER_FOREACH(V, H, T, F) \ 328 for ((V) = PSLIST_READER_FIRST((H), T, F); \ 329 (V) != NULL; \ 330 (V) = PSLIST_READER_NEXT((V), T, F)) 331 332 #endif /* _SYS_PSLIST_H */ 333