1 /* $NetBSD: pslist.h,v 1.2 2016/04/11 03:46:37 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; 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 static inline struct pslist_entry * 181 pslist_writer_first(struct pslist_head *head) 182 { 183 184 return head->plh_first; 185 } 186 187 static inline struct pslist_entry * 188 pslist_writer_next(struct pslist_entry *entry) 189 { 190 191 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); 192 return entry->ple_next; 193 } 194 195 static inline void * 196 _pslist_writer_first_container(struct pslist_head *head, ptrdiff_t offset) 197 { 198 struct pslist_entry *first = head->plh_first; 199 200 return (first == NULL ? NULL : (char *)first - offset); 201 } 202 203 static inline void * 204 _pslist_writer_next_container(struct pslist_entry *entry, ptrdiff_t offset) 205 { 206 struct pslist_entry *next = entry->ple_next; 207 208 _PSLIST_ASSERT(next != _PSLIST_POISON); 209 return (next == NULL ? NULL : (char *)next - offset); 210 } 211 212 /* 213 * Reader operations. Caller must block pserialize_perform or 214 * equivalent and be bound to a CPU. Only plh_first/ple_next may be 215 * read, and after that, a membar_datadep_consumer must precede 216 * dereferencing the resulting pointer. 217 */ 218 219 static inline struct pslist_entry * 220 pslist_reader_first(struct pslist_head *head) 221 { 222 struct pslist_entry *first = head->plh_first; 223 224 if (first != NULL) 225 membar_datadep_consumer(); 226 227 return first; 228 } 229 230 static inline struct pslist_entry * 231 pslist_reader_next(struct pslist_entry *entry) 232 { 233 struct pslist_entry *next = entry->ple_next; 234 235 _PSLIST_ASSERT(next != _PSLIST_POISON); 236 if (next != NULL) 237 membar_datadep_consumer(); 238 239 return next; 240 } 241 242 static inline void * 243 _pslist_reader_first_container(struct pslist_head *head, ptrdiff_t offset) 244 { 245 struct pslist_entry *first = head->plh_first; 246 247 if (first == NULL) 248 return NULL; 249 membar_datadep_consumer(); 250 251 return (char *)first - offset; 252 } 253 254 static inline void * 255 _pslist_reader_next_container(struct pslist_entry *entry, ptrdiff_t offset) 256 { 257 struct pslist_entry *next = entry->ple_next; 258 259 _PSLIST_ASSERT(next != _PSLIST_POISON); 260 if (next == NULL) 261 return NULL; 262 membar_datadep_consumer(); 263 264 return (char *)next - offset; 265 } 266 267 /* 268 * Type-safe macros for convenience. 269 */ 270 271 #ifdef __COVERITY__ 272 #define _PSLIST_VALIDATE_PTRS(P, Q) 0 273 #define _PSLIST_VALIDATE_CONTAINER(P, T, F) 0 274 #else 275 #define _PSLIST_VALIDATE_PTRS(P, Q) \ 276 (0 * sizeof((P) - (Q)) * sizeof(*(P)) * sizeof(*(Q))) 277 #define _PSLIST_VALIDATE_CONTAINER(P, T, F) \ 278 (0 * sizeof((P) - &((T *)(((char *)(P)) - offsetof(T, F)))->F)) 279 #endif 280 281 #define PSLIST_INITIALIZER { .plh_first = NULL } 282 #define PSLIST_ENTRY_INITIALIZER { .ple_next = NULL, .ple_prevp = NULL } 283 284 #define PSLIST_INIT(H) pslist_init((H)) 285 #define PSLIST_DESTROY(H) pslist_destroy((H)) 286 #define PSLIST_ENTRY_INIT(E, F) pslist_entry_init(&(E)->F) 287 #define PSLIST_ENTRY_DESTROY(E, F) pslist_entry_destroy(&(E)->F) 288 289 #define PSLIST_WRITER_INSERT_HEAD(H, V, F) \ 290 pslist_writer_insert_head((H), &(V)->F) 291 #define PSLIST_WRITER_INSERT_BEFORE(E, N, F) \ 292 pslist_writer_insert_before(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \ 293 &(N)->F) 294 #define PSLIST_WRITER_INSERT_AFTER(E, N, F) \ 295 pslist_writer_insert_after(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \ 296 &(N)->F) 297 #define PSLIST_WRITER_REMOVE(E, F) \ 298 pslist_writer_remove(&(E)->F) 299 #define PSLIST_WRITER_FIRST(H, T, F) \ 300 ((T *)(_pslist_writer_first_container((H), offsetof(T, F))) + \ 301 _PSLIST_VALIDATE_CONTAINER(pslist_writer_first(H), T, F)) 302 #define PSLIST_WRITER_NEXT(V, T, F) \ 303 ((T *)(_pslist_writer_next_container(&(V)->F, offsetof(T, F))) + \ 304 _PSLIST_VALIDATE_CONTAINER(pslist_writer_next(&(V)->F), T, F)) 305 #define PSLIST_WRITER_FOREACH(V, H, T, F) \ 306 for ((V) = PSLIST_WRITER_FIRST((H), T, F); \ 307 (V) != NULL; \ 308 (V) = PSLIST_WRITER_NEXT((V), T, F)) 309 310 #define PSLIST_READER_FIRST(H, T, F) \ 311 ((T *)(_pslist_reader_first_container((H), offsetof(T, F))) + \ 312 _PSLIST_VALIDATE_CONTAINER(pslist_reader_first(H), T, F)) 313 #define PSLIST_READER_NEXT(V, T, F) \ 314 ((T *)(_pslist_reader_next_container(&(V)->F, offsetof(T, F))) + \ 315 _PSLIST_VALIDATE_CONTAINER(pslist_reader_next(&(V)->F), T, F)) 316 #define PSLIST_READER_FOREACH(V, H, T, F) \ 317 for ((V) = PSLIST_READER_FIRST((H), T, F); \ 318 (V) != NULL; \ 319 (V) = PSLIST_READER_NEXT((V), T, F)) 320 321 #endif /* _SYS_PSLIST_H */ 322