1 | /* |
2 | * Copyright (c) 2000-2009 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | /* |
29 | * @OSF_COPYRIGHT@ |
30 | */ |
31 | /* |
32 | * Mach Operating System |
33 | * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University |
34 | * All Rights Reserved. |
35 | * |
36 | * Permission to use, copy, modify and distribute this software and its |
37 | * documentation is hereby granted, provided that both the copyright |
38 | * notice and this permission notice appear in all copies of the |
39 | * software, derivative works or modified versions, and any portions |
40 | * thereof, and that both notices appear in supporting documentation. |
41 | * |
42 | * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" |
43 | * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR |
44 | * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. |
45 | * |
46 | * Carnegie Mellon requests users of this software to return to |
47 | * |
48 | * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU |
49 | * School of Computer Science |
50 | * Carnegie Mellon University |
51 | * Pittsburgh PA 15213-3890 |
52 | * |
53 | * any improvements or extensions that they make and grant Carnegie Mellon rights |
54 | * to redistribute these changes. |
55 | */ |
56 | /* |
57 | */ |
58 | /* |
59 | * File: queue.h |
60 | * Author: Avadis Tevanian, Jr. |
61 | * Date: 1985 |
62 | * |
63 | * Type definitions for generic queues. |
64 | * |
65 | */ |
66 | |
67 | #ifndef _KERN_QUEUE_H_ |
68 | #define _KERN_QUEUE_H_ |
69 | |
70 | #include <mach/mach_types.h> |
71 | #include <kern/macro_help.h> |
72 | |
73 | #include <sys/cdefs.h> |
74 | |
75 | __BEGIN_DECLS |
76 | |
77 | /* |
78 | * Queue Management APIs |
79 | * |
80 | * There are currently two subtly different methods of maintining |
81 | * a queue of objects. Both APIs are contained in this file, and |
82 | * unfortunately overlap. |
83 | * (there is also a third way maintained in bsd/sys/queue.h) |
84 | * |
85 | * Both methods use a common queue head and linkage pattern: |
86 | * The head of a queue is declared as: |
87 | * queue_head_t q_head; |
88 | * |
89 | * Elements in this queue are chained together using |
90 | * struct queue_entry objects embedded within a structure: |
91 | * struct some_data { |
92 | * int field1; |
93 | * int field2; |
94 | * ... |
95 | * queue_chain_t link; |
96 | * ... |
97 | * int last_field; |
98 | * }; |
99 | * struct some_data is referred to as the queue "element." |
100 | * (note that queue_chain_t is typedef'd to struct queue_entry) |
101 | * |
102 | * IMPORTANT: The two queue iteration methods described below are not |
103 | * compatible with one another. You must choose one and be careful |
104 | * to use only the supported APIs for that method. |
105 | * |
106 | * Method 1: chaining of queue_chain_t (linkage chains) |
107 | * This method uses the next and prev pointers of the struct queue_entry |
108 | * linkage object embedded in a queue element to point to the next or |
109 | * previous queue_entry structure in the chain. The head of the queue |
110 | * (the queue_head_t object) will point to the first and last |
111 | * struct queue_entry object, and both the next and prev pointer will |
112 | * point back to the head if the queue is empty. |
113 | * |
114 | * This method is the most flexible method of chaining objects together |
115 | * as it allows multiple chains through a given object, by embedding |
116 | * multiple queue_chain_t objects in the structure, while simultaneously |
117 | * providing fast removal and insertion into the queue using only |
118 | * struct queue_entry object pointers. |
119 | * |
120 | * ++ Valid APIs for this style queue ++ |
121 | * ------------------------------------- |
122 | * [C] queue_init |
123 | * [C] queue_first |
124 | * [C] queue_next |
125 | * [C] queue_last |
126 | * [C] queue_prev |
127 | * [C] queue_end |
128 | * [C] queue_empty |
129 | * |
130 | * [1] enqueue |
131 | * [1] dequeue |
132 | * [1] enqueue_head |
133 | * [1] enqueue_tail |
134 | * [1] dequeue_head |
135 | * [1] dequeue_tail |
136 | * [1] remqueue |
137 | * [1] insque |
138 | * [1] remque |
139 | * [1] re_queue_head |
140 | * [1] re_queue_tail |
141 | * [1] movqueue |
142 | * [1] qe_element |
143 | * [1] qe_foreach |
144 | * [1] qe_foreach_safe |
145 | * [1] qe_foreach_element |
146 | * [1] qe_foreach_element_safe |
147 | * |
148 | * Method 2: chaining of elements (element chains) |
149 | * This method uses the next and prev pointers of the struct queue_entry |
150 | * linkage object embedded in a queue element to point to the next or |
151 | * previous queue element (not another queue_entry). The head of the |
152 | * queue will point to the first and last queue element (struct some_data |
153 | * from the above example) NOT the embedded queue_entry structure. The |
154 | * first queue element will have a prev pointer that points to the |
155 | * queue_head_t, and the last queue element will have a next pointer |
156 | * that points to the queue_head_t. |
157 | * |
158 | * This method requires knowledge of the queue_head_t of the queue on |
159 | * which an element resides in order to remove the element. Iterating |
160 | * through the elements of the queue is also more cumbersome because |
161 | * a check against the head pointer plus a cast then offset operation |
162 | * must be performed at each step of the iteration. |
163 | * |
164 | * ++ Valid APIs for this style queue ++ |
165 | * ------------------------------------- |
166 | * [C] queue_init |
167 | * [C] queue_first |
168 | * [C] queue_next |
169 | * [C] queue_last |
170 | * [C] queue_prev |
171 | * [C] queue_end |
172 | * [C] queue_empty |
173 | * |
174 | * [2] queue_enter |
175 | * [2] queue_enter_first |
176 | * [2] queue_insert_before |
177 | * [2] queue_insert_after |
178 | * [2] queue_field |
179 | * [2] queue_remove |
180 | * [2] queue_remove_first |
181 | * [2] queue_remove_last |
182 | * [2] queue_assign |
183 | * [2] queue_new_head |
184 | * [2] queue_iterate |
185 | * |
186 | * Legend: |
187 | * [C] -> API common to both methods |
188 | * [1] -> API used only in method 1 (linkage chains) |
189 | * [2] -> API used only in method 2 (element chains) |
190 | */ |
191 | |
192 | /* |
193 | * A generic doubly-linked list (queue). |
194 | */ |
195 | |
196 | struct queue_entry { |
197 | struct queue_entry *next; /* next element */ |
198 | struct queue_entry *prev; /* previous element */ |
199 | |
200 | #if __arm__ && (__BIGGEST_ALIGNMENT__ > 4) |
201 | /* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers |
202 | * are 32-bit: |
203 | * Since this type is so often cast to various 64-bit aligned types |
204 | * aligning it to 64-bits will avoid -wcast-align without needing |
205 | * to disable it entirely. The impact on memory footprint should be |
206 | * negligible. |
207 | */ |
208 | } __attribute__ ((aligned (8))); |
209 | #else |
210 | }; |
211 | #endif |
212 | |
213 | typedef struct queue_entry *queue_t; |
214 | typedef struct queue_entry queue_head_t; |
215 | typedef struct queue_entry queue_chain_t; |
216 | typedef struct queue_entry *queue_entry_t; |
217 | |
218 | /* |
219 | * enqueue puts "elt" on the "queue". |
220 | * dequeue returns the first element in the "queue". |
221 | * remqueue removes the specified "elt" from its queue. |
222 | */ |
223 | |
224 | #define enqueue(queue,elt) enqueue_tail(queue, elt) |
225 | #define dequeue(queue) dequeue_head(queue) |
226 | |
227 | #ifdef XNU_KERNEL_PRIVATE |
228 | #include <kern/debug.h> |
229 | static inline void __QUEUE_ELT_VALIDATE(queue_entry_t elt) { |
230 | queue_entry_t elt_next, elt_prev; |
231 | |
232 | if (__improbable(elt == (queue_entry_t)0)) { |
233 | panic("Invalid queue element %p" , elt); |
234 | } |
235 | |
236 | elt_next = elt->next; |
237 | elt_prev = elt->prev; |
238 | |
239 | if (__improbable(elt_next == (queue_entry_t)0 || elt_prev == (queue_entry_t)0)) { |
240 | panic("Invalid queue element pointers for %p: next %p prev %p" , elt, elt_next, elt_prev); |
241 | } |
242 | if (__improbable(elt_next->prev != elt || elt_prev->next != elt)) { |
243 | panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p" , |
244 | elt, elt_next, elt_next->prev, elt_prev, elt_prev->next); |
245 | } |
246 | } |
247 | |
248 | static inline void __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) { |
249 | (elt)->next = (queue_entry_t) 0; |
250 | (elt)->prev = (queue_entry_t) 0; |
251 | } |
252 | #else |
253 | #define __QUEUE_ELT_VALIDATE(elt) do { } while (0) |
254 | #define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0) |
255 | #endif /* !XNU_KERNEL_PRIVATE */ |
256 | |
257 | static __inline__ void |
258 | enqueue_head( |
259 | queue_t que, |
260 | queue_entry_t elt) |
261 | { |
262 | queue_entry_t old_head; |
263 | |
264 | __QUEUE_ELT_VALIDATE((queue_entry_t)que); |
265 | old_head = que->next; |
266 | elt->next = old_head; |
267 | elt->prev = que; |
268 | old_head->prev = elt; |
269 | que->next = elt; |
270 | } |
271 | |
272 | static __inline__ void |
273 | enqueue_tail( |
274 | queue_t que, |
275 | queue_entry_t elt) |
276 | { |
277 | queue_entry_t old_tail; |
278 | |
279 | __QUEUE_ELT_VALIDATE((queue_entry_t)que); |
280 | old_tail = que->prev; |
281 | elt->next = que; |
282 | elt->prev = old_tail; |
283 | old_tail->next = elt; |
284 | que->prev = elt; |
285 | } |
286 | |
287 | static __inline__ queue_entry_t |
288 | dequeue_head( |
289 | queue_t que) |
290 | { |
291 | queue_entry_t elt = (queue_entry_t) 0; |
292 | queue_entry_t new_head; |
293 | |
294 | if (que->next != que) { |
295 | elt = que->next; |
296 | __QUEUE_ELT_VALIDATE(elt); |
297 | new_head = elt->next; /* new_head may point to que if elt was the only element */ |
298 | new_head->prev = que; |
299 | que->next = new_head; |
300 | __DEQUEUE_ELT_CLEANUP(elt); |
301 | } |
302 | |
303 | return (elt); |
304 | } |
305 | |
306 | static __inline__ queue_entry_t |
307 | dequeue_tail( |
308 | queue_t que) |
309 | { |
310 | queue_entry_t elt = (queue_entry_t) 0; |
311 | queue_entry_t new_tail; |
312 | |
313 | if (que->prev != que) { |
314 | elt = que->prev; |
315 | __QUEUE_ELT_VALIDATE(elt); |
316 | new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */ |
317 | new_tail->next = que; |
318 | que->prev = new_tail; |
319 | __DEQUEUE_ELT_CLEANUP(elt); |
320 | } |
321 | |
322 | return (elt); |
323 | } |
324 | |
325 | static __inline__ void |
326 | remqueue( |
327 | queue_entry_t elt) |
328 | { |
329 | queue_entry_t next_elt, prev_elt; |
330 | |
331 | __QUEUE_ELT_VALIDATE(elt); |
332 | next_elt = elt->next; |
333 | prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ |
334 | next_elt->prev = prev_elt; |
335 | prev_elt->next = next_elt; |
336 | __DEQUEUE_ELT_CLEANUP(elt); |
337 | } |
338 | |
339 | static __inline__ void |
340 | insque( |
341 | queue_entry_t entry, |
342 | queue_entry_t pred) |
343 | { |
344 | queue_entry_t successor; |
345 | |
346 | __QUEUE_ELT_VALIDATE(pred); |
347 | successor = pred->next; |
348 | entry->next = successor; |
349 | entry->prev = pred; |
350 | successor->prev = entry; |
351 | pred->next = entry; |
352 | } |
353 | |
354 | static __inline__ void |
355 | remque( |
356 | queue_entry_t elt) |
357 | { |
358 | queue_entry_t next_elt, prev_elt; |
359 | |
360 | __QUEUE_ELT_VALIDATE(elt); |
361 | next_elt = elt->next; |
362 | prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ |
363 | next_elt->prev = prev_elt; |
364 | prev_elt->next = next_elt; |
365 | __DEQUEUE_ELT_CLEANUP(elt); |
366 | } |
367 | |
368 | /* |
369 | * Function: re_queue_head |
370 | * Parameters: |
371 | * queue_t que : queue onto which elt will be pre-pended |
372 | * queue_entry_t elt : element to re-queue |
373 | * Description: |
374 | * Remove elt from its current queue and put it onto the |
375 | * head of a new queue |
376 | * Note: |
377 | * This should only be used with Method 1 queue iteration (linkage chains) |
378 | */ |
379 | static __inline__ void |
380 | re_queue_head(queue_t que, queue_entry_t elt) |
381 | { |
382 | queue_entry_t n_elt, p_elt; |
383 | |
384 | __QUEUE_ELT_VALIDATE(elt); |
385 | __QUEUE_ELT_VALIDATE((queue_entry_t)que); |
386 | |
387 | /* remqueue */ |
388 | n_elt = elt->next; |
389 | p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ |
390 | n_elt->prev = p_elt; |
391 | p_elt->next = n_elt; |
392 | |
393 | /* enqueue_head */ |
394 | n_elt = que->next; |
395 | elt->next = n_elt; |
396 | elt->prev = que; |
397 | n_elt->prev = elt; |
398 | que->next = elt; |
399 | } |
400 | |
401 | /* |
402 | * Function: re_queue_tail |
403 | * Parameters: |
404 | * queue_t que : queue onto which elt will be appended |
405 | * queue_entry_t elt : element to re-queue |
406 | * Description: |
407 | * Remove elt from its current queue and put it onto the |
408 | * end of a new queue |
409 | * Note: |
410 | * This should only be used with Method 1 queue iteration (linkage chains) |
411 | */ |
412 | static __inline__ void |
413 | re_queue_tail(queue_t que, queue_entry_t elt) |
414 | { |
415 | queue_entry_t n_elt, p_elt; |
416 | |
417 | __QUEUE_ELT_VALIDATE(elt); |
418 | __QUEUE_ELT_VALIDATE((queue_entry_t)que); |
419 | |
420 | /* remqueue */ |
421 | n_elt = elt->next; |
422 | p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */ |
423 | n_elt->prev = p_elt; |
424 | p_elt->next = n_elt; |
425 | |
426 | /* enqueue_tail */ |
427 | p_elt = que->prev; |
428 | elt->next = que; |
429 | elt->prev = p_elt; |
430 | p_elt->next = elt; |
431 | que->prev = elt; |
432 | } |
433 | |
434 | /* |
435 | * Macro: qe_element |
436 | * Function: |
437 | * Convert a queue_entry_t to a queue element pointer. |
438 | * Get a pointer to the user-defined element containing |
439 | * a given queue_entry_t |
440 | * Header: |
441 | * <type> * qe_element(queue_entry_t qe, <type>, field) |
442 | * qe - queue entry to convert |
443 | * <type> - what's in the queue (e.g., struct some_data) |
444 | * <field> - is the chain field in <type> |
445 | * Note: |
446 | * Do not use pointer types for <type> |
447 | */ |
448 | #define qe_element(qe, type, field) \ |
449 | ((type *)((void *)((char *)(qe) - __offsetof(type, field)))) |
450 | |
451 | /* |
452 | * Macro: qe_foreach |
453 | * Function: |
454 | * Iterate over each queue_entry_t structure. |
455 | * Generates a 'for' loop, setting 'qe' to |
456 | * each queue_entry_t in the queue. |
457 | * Header: |
458 | * qe_foreach(queue_entry_t qe, queue_t head) |
459 | * qe - iteration variable |
460 | * head - pointer to queue_head_t (head of queue) |
461 | * Note: |
462 | * This should only be used with Method 1 queue iteration (linkage chains) |
463 | */ |
464 | #define qe_foreach(qe, head) \ |
465 | for (qe = (head)->next; qe != (head); qe = (qe)->next) |
466 | |
467 | /* |
468 | * Macro: qe_foreach_safe |
469 | * Function: |
470 | * Safely iterate over each queue_entry_t structure. |
471 | * |
472 | * Use this iterator macro if you plan to remove the |
473 | * queue_entry_t, qe, from the queue during the |
474 | * iteration. |
475 | * Header: |
476 | * qe_foreach_safe(queue_entry_t qe, queue_t head) |
477 | * qe - iteration variable |
478 | * head - pointer to queue_head_t (head of queue) |
479 | * Note: |
480 | * This should only be used with Method 1 queue iteration (linkage chains) |
481 | */ |
482 | #define qe_foreach_safe(qe, head) \ |
483 | for (queue_entry_t _ne = ((head)->next)->next, \ |
484 | __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \ |
485 | qe != (head); \ |
486 | qe = _ne, _ne = (qe)->next) |
487 | |
488 | /* |
489 | * Macro: qe_foreach_element |
490 | * Function: |
491 | * Iterate over each _element_ in a queue |
492 | * where each queue_entry_t points to another |
493 | * queue_entry_t, i.e., managed by the [de|en]queue_head/ |
494 | * [de|en]queue_tail / remqueue / etc. function. |
495 | * Header: |
496 | * qe_foreach_element(<type> *elt, queue_t head, <field>) |
497 | * elt - iteration variable |
498 | * <type> - what's in the queue (e.g., struct some_data) |
499 | * <field> - is the chain field in <type> |
500 | * Note: |
501 | * This should only be used with Method 1 queue iteration (linkage chains) |
502 | */ |
503 | #define qe_foreach_element(elt, head, field) \ |
504 | for (elt = qe_element((head)->next, typeof(*(elt)), field); \ |
505 | &((elt)->field) != (head); \ |
506 | elt = qe_element((elt)->field.next, typeof(*(elt)), field)) |
507 | |
508 | /* |
509 | * Macro: qe_foreach_element_safe |
510 | * Function: |
511 | * Safely iterate over each _element_ in a queue |
512 | * where each queue_entry_t points to another |
513 | * queue_entry_t, i.e., managed by the [de|en]queue_head/ |
514 | * [de|en]queue_tail / remqueue / etc. function. |
515 | * |
516 | * Use this iterator macro if you plan to remove the |
517 | * element, elt, from the queue during the iteration. |
518 | * Header: |
519 | * qe_foreach_element_safe(<type> *elt, queue_t head, <field>) |
520 | * elt - iteration variable |
521 | * <type> - what's in the queue (e.g., struct some_data) |
522 | * <field> - is the chain field in <type> |
523 | * Note: |
524 | * This should only be used with Method 1 queue iteration (linkage chains) |
525 | */ |
526 | #define qe_foreach_element_safe(elt, head, field) \ |
527 | for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \ |
528 | *__ ## elt ## _unused_shadow __unused = \ |
529 | (elt = qe_element((head)->next, typeof(*(elt)), field)); \ |
530 | &((elt)->field) != (head); \ |
531 | elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \ |
532 | |
533 | #ifdef XNU_KERNEL_PRIVATE |
534 | |
535 | /* Dequeue an element from head, or return NULL if the queue is empty */ |
536 | #define qe_dequeue_head(head, type, field) ({ \ |
537 | queue_entry_t _tmp_entry = dequeue_head((head)); \ |
538 | type *_tmp_element = (type*) NULL; \ |
539 | if (_tmp_entry != (queue_entry_t) NULL) \ |
540 | _tmp_element = qe_element(_tmp_entry, type, field); \ |
541 | _tmp_element; \ |
542 | }) |
543 | |
544 | /* Dequeue an element from tail, or return NULL if the queue is empty */ |
545 | #define qe_dequeue_tail(head, type, field) ({ \ |
546 | queue_entry_t _tmp_entry = dequeue_tail((head)); \ |
547 | type *_tmp_element = (type*) NULL; \ |
548 | if (_tmp_entry != (queue_entry_t) NULL) \ |
549 | _tmp_element = qe_element(_tmp_entry, type, field); \ |
550 | _tmp_element; \ |
551 | }) |
552 | |
553 | /* Peek at the first element, or return NULL if the queue is empty */ |
554 | #define qe_queue_first(head, type, field) ({ \ |
555 | queue_entry_t _tmp_entry = queue_first((head)); \ |
556 | type *_tmp_element = (type*) NULL; \ |
557 | if (_tmp_entry != (queue_entry_t) head) \ |
558 | _tmp_element = qe_element(_tmp_entry, type, field); \ |
559 | _tmp_element; \ |
560 | }) |
561 | |
562 | /* Peek at the last element, or return NULL if the queue is empty */ |
563 | #define qe_queue_last(head, type, field) ({ \ |
564 | queue_entry_t _tmp_entry = queue_last((head)); \ |
565 | type *_tmp_element = (type*) NULL; \ |
566 | if (_tmp_entry != (queue_entry_t) head) \ |
567 | _tmp_element = qe_element(_tmp_entry, type, field); \ |
568 | _tmp_element; \ |
569 | }) |
570 | |
571 | #endif /* XNU_KERNEL_PRIVATE */ |
572 | |
573 | /* |
574 | * Macro: queue_init |
575 | * Function: |
576 | * Initialize the given queue. |
577 | * Header: |
578 | * void queue_init(q) |
579 | * queue_t q; \* MODIFIED *\ |
580 | */ |
581 | #define queue_init(q) \ |
582 | MACRO_BEGIN \ |
583 | (q)->next = (q);\ |
584 | (q)->prev = (q);\ |
585 | MACRO_END |
586 | |
587 | /* |
588 | * Macro: queue_head_init |
589 | * Function: |
590 | * Initialize the given queue head |
591 | * Header: |
592 | * void queue_head_init(q) |
593 | * queue_head_t q; \* MODIFIED *\ |
594 | */ |
595 | #define queue_head_init(q) \ |
596 | queue_init(&(q)) |
597 | |
598 | /* |
599 | * Macro: queue_chain_init |
600 | * Function: |
601 | * Initialize the given queue chain element |
602 | * Header: |
603 | * void queue_chain_init(q) |
604 | * queue_chain_t q; \* MODIFIED *\ |
605 | */ |
606 | #define queue_chain_init(q) \ |
607 | queue_init(&(q)) |
608 | |
609 | /* |
610 | * Macro: queue_first |
611 | * Function: |
612 | * Returns the first entry in the queue, |
613 | * Header: |
614 | * queue_entry_t queue_first(q) |
615 | * queue_t q; \* IN *\ |
616 | */ |
617 | #define queue_first(q) ((q)->next) |
618 | |
619 | /* |
620 | * Macro: queue_next |
621 | * Function: |
622 | * Returns the entry after an item in the queue. |
623 | * Header: |
624 | * queue_entry_t queue_next(qc) |
625 | * queue_t qc; |
626 | */ |
627 | #define queue_next(qc) ((qc)->next) |
628 | |
629 | /* |
630 | * Macro: queue_last |
631 | * Function: |
632 | * Returns the last entry in the queue. |
633 | * Header: |
634 | * queue_entry_t queue_last(q) |
635 | * queue_t q; \* IN *\ |
636 | */ |
637 | #define queue_last(q) ((q)->prev) |
638 | |
639 | /* |
640 | * Macro: queue_prev |
641 | * Function: |
642 | * Returns the entry before an item in the queue. |
643 | * Header: |
644 | * queue_entry_t queue_prev(qc) |
645 | * queue_t qc; |
646 | */ |
647 | #define queue_prev(qc) ((qc)->prev) |
648 | |
649 | /* |
650 | * Macro: queue_end |
651 | * Function: |
652 | * Tests whether a new entry is really the end of |
653 | * the queue. |
654 | * Header: |
655 | * boolean_t queue_end(q, qe) |
656 | * queue_t q; |
657 | * queue_entry_t qe; |
658 | */ |
659 | #define queue_end(q, qe) ((q) == (qe)) |
660 | |
661 | /* |
662 | * Macro: queue_empty |
663 | * Function: |
664 | * Tests whether a queue is empty. |
665 | * Header: |
666 | * boolean_t queue_empty(q) |
667 | * queue_t q; |
668 | */ |
669 | #define queue_empty(q) queue_end((q), queue_first(q)) |
670 | |
671 | /* |
672 | * Function: movqueue |
673 | * Parameters: |
674 | * queue_t _old : head of a queue whose items will be moved |
675 | * queue_t _new : new queue head onto which items will be moved |
676 | * Description: |
677 | * Rebase queue items in _old onto _new then re-initialize |
678 | * the _old object to an empty queue. |
679 | * Equivalent to the queue_new_head Method 2 macro |
680 | * Note: |
681 | * Similar to the queue_new_head macro, this macros is intented |
682 | * to function as an initializer method for '_new' and thus may |
683 | * leak any list items that happen to be on the '_new' list. |
684 | * This should only be used with Method 1 queue iteration (linkage chains) |
685 | */ |
686 | static __inline__ void |
687 | movqueue(queue_t _old, queue_t _new) |
688 | { |
689 | queue_entry_t next_elt, prev_elt; |
690 | |
691 | __QUEUE_ELT_VALIDATE((queue_entry_t)_old); |
692 | |
693 | if (queue_empty(_old)) { |
694 | queue_init(_new); |
695 | return; |
696 | } |
697 | |
698 | /* |
699 | * move the queue at _old to _new |
700 | * and re-initialize _old |
701 | */ |
702 | next_elt = _old->next; |
703 | prev_elt = _old->prev; |
704 | |
705 | _new->next = next_elt; |
706 | _new->prev = prev_elt; |
707 | next_elt->prev = _new; |
708 | prev_elt->next = _new; |
709 | |
710 | queue_init(_old); |
711 | } |
712 | |
713 | /*----------------------------------------------------------------*/ |
714 | /* |
715 | * Macros that operate on generic structures. The queue |
716 | * chain may be at any location within the structure, and there |
717 | * may be more than one chain. |
718 | */ |
719 | |
720 | /* |
721 | * Macro: queue_enter |
722 | * Function: |
723 | * Insert a new element at the tail of the queue. |
724 | * Header: |
725 | * void queue_enter(q, elt, type, field) |
726 | * queue_t q; |
727 | * <type> elt; |
728 | * <type> is what's in our queue |
729 | * <field> is the chain field in (*<type>) |
730 | * Note: |
731 | * This should only be used with Method 2 queue iteration (element chains) |
732 | * |
733 | * We insert a compiler barrier after setting the fields in the element |
734 | * to ensure that the element is updated before being added to the queue, |
735 | * which is especially important because stackshot, which operates from |
736 | * debugger context, iterates several queues that use this macro (the tasks |
737 | * lists and threads lists) without locks. Without this barrier, the |
738 | * compiler may re-order the instructions for this macro in a way that |
739 | * could cause stackshot to trip over an inconsistent queue during |
740 | * iteration. |
741 | */ |
742 | #define queue_enter(head, elt, type, field) \ |
743 | MACRO_BEGIN \ |
744 | queue_entry_t __prev; \ |
745 | \ |
746 | __prev = (head)->prev; \ |
747 | (elt)->field.prev = __prev; \ |
748 | (elt)->field.next = head; \ |
749 | __compiler_barrier(); \ |
750 | if ((head) == __prev) { \ |
751 | (head)->next = (queue_entry_t) (elt); \ |
752 | } \ |
753 | else { \ |
754 | ((type)(void *)__prev)->field.next = \ |
755 | (queue_entry_t)(elt); \ |
756 | } \ |
757 | (head)->prev = (queue_entry_t) elt; \ |
758 | MACRO_END |
759 | |
760 | /* |
761 | * Macro: queue_enter_first |
762 | * Function: |
763 | * Insert a new element at the head of the queue. |
764 | * Header: |
765 | * void queue_enter_first(q, elt, type, field) |
766 | * queue_t q; |
767 | * <type> elt; |
768 | * <type> is what's in our queue |
769 | * <field> is the chain field in (*<type>) |
770 | * Note: |
771 | * This should only be used with Method 2 queue iteration (element chains) |
772 | */ |
773 | #define queue_enter_first(head, elt, type, field) \ |
774 | MACRO_BEGIN \ |
775 | queue_entry_t __next; \ |
776 | \ |
777 | __next = (head)->next; \ |
778 | if ((head) == __next) { \ |
779 | (head)->prev = (queue_entry_t) (elt); \ |
780 | } \ |
781 | else { \ |
782 | ((type)(void *)__next)->field.prev = \ |
783 | (queue_entry_t)(elt); \ |
784 | } \ |
785 | (elt)->field.next = __next; \ |
786 | (elt)->field.prev = head; \ |
787 | (head)->next = (queue_entry_t) elt; \ |
788 | MACRO_END |
789 | |
790 | /* |
791 | * Macro: queue_insert_before |
792 | * Function: |
793 | * Insert a new element before a given element. |
794 | * Header: |
795 | * void queue_insert_before(q, elt, cur, type, field) |
796 | * queue_t q; |
797 | * <type> elt; |
798 | * <type> cur; |
799 | * <type> is what's in our queue |
800 | * <field> is the chain field in (*<type>) |
801 | * Note: |
802 | * This should only be used with Method 2 queue iteration (element chains) |
803 | */ |
804 | #define queue_insert_before(head, elt, cur, type, field) \ |
805 | MACRO_BEGIN \ |
806 | queue_entry_t __prev; \ |
807 | \ |
808 | if ((head) == (queue_entry_t)(cur)) { \ |
809 | (elt)->field.next = (head); \ |
810 | if ((head)->next == (head)) { /* only element */ \ |
811 | (elt)->field.prev = (head); \ |
812 | (head)->next = (queue_entry_t)(elt); \ |
813 | } else { /* last element */ \ |
814 | __prev = (elt)->field.prev = (head)->prev; \ |
815 | ((type)(void *)__prev)->field.next = \ |
816 | (queue_entry_t)(elt); \ |
817 | } \ |
818 | (head)->prev = (queue_entry_t)(elt); \ |
819 | } else { \ |
820 | (elt)->field.next = (queue_entry_t)(cur); \ |
821 | if ((head)->next == (queue_entry_t)(cur)) { \ |
822 | /* first element */ \ |
823 | (elt)->field.prev = (head); \ |
824 | (head)->next = (queue_entry_t)(elt); \ |
825 | } else { /* middle element */ \ |
826 | __prev = (elt)->field.prev = (cur)->field.prev; \ |
827 | ((type)(void *)__prev)->field.next = \ |
828 | (queue_entry_t)(elt); \ |
829 | } \ |
830 | (cur)->field.prev = (queue_entry_t)(elt); \ |
831 | } \ |
832 | MACRO_END |
833 | |
834 | /* |
835 | * Macro: queue_insert_after |
836 | * Function: |
837 | * Insert a new element after a given element. |
838 | * Header: |
839 | * void queue_insert_after(q, elt, cur, type, field) |
840 | * queue_t q; |
841 | * <type> elt; |
842 | * <type> cur; |
843 | * <type> is what's in our queue |
844 | * <field> is the chain field in (*<type>) |
845 | * Note: |
846 | * This should only be used with Method 2 queue iteration (element chains) |
847 | */ |
848 | #define queue_insert_after(head, elt, cur, type, field) \ |
849 | MACRO_BEGIN \ |
850 | queue_entry_t __next; \ |
851 | \ |
852 | if ((head) == (queue_entry_t)(cur)) { \ |
853 | (elt)->field.prev = (head); \ |
854 | if ((head)->next == (head)) { /* only element */ \ |
855 | (elt)->field.next = (head); \ |
856 | (head)->prev = (queue_entry_t)(elt); \ |
857 | } else { /* first element */ \ |
858 | __next = (elt)->field.next = (head)->next; \ |
859 | ((type)(void *)__next)->field.prev = \ |
860 | (queue_entry_t)(elt); \ |
861 | } \ |
862 | (head)->next = (queue_entry_t)(elt); \ |
863 | } else { \ |
864 | (elt)->field.prev = (queue_entry_t)(cur); \ |
865 | if ((head)->prev == (queue_entry_t)(cur)) { \ |
866 | /* last element */ \ |
867 | (elt)->field.next = (head); \ |
868 | (head)->prev = (queue_entry_t)(elt); \ |
869 | } else { /* middle element */ \ |
870 | __next = (elt)->field.next = (cur)->field.next; \ |
871 | ((type)(void *)__next)->field.prev = \ |
872 | (queue_entry_t)(elt); \ |
873 | } \ |
874 | (cur)->field.next = (queue_entry_t)(elt); \ |
875 | } \ |
876 | MACRO_END |
877 | |
878 | /* |
879 | * Macro: queue_field [internal use only] |
880 | * Function: |
881 | * Find the queue_chain_t (or queue_t) for the |
882 | * given element (thing) in the given queue (head) |
883 | * Note: |
884 | * This should only be used with Method 2 queue iteration (element chains) |
885 | */ |
886 | #define queue_field(head, thing, type, field) \ |
887 | (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field) |
888 | |
889 | /* |
890 | * Macro: queue_remove |
891 | * Function: |
892 | * Remove an arbitrary item from the queue. |
893 | * Header: |
894 | * void queue_remove(q, qe, type, field) |
895 | * arguments as in queue_enter |
896 | * Note: |
897 | * This should only be used with Method 2 queue iteration (element chains) |
898 | */ |
899 | #define queue_remove(head, elt, type, field) \ |
900 | MACRO_BEGIN \ |
901 | queue_entry_t __next, __prev; \ |
902 | \ |
903 | __next = (elt)->field.next; \ |
904 | __prev = (elt)->field.prev; \ |
905 | \ |
906 | if ((head) == __next) \ |
907 | (head)->prev = __prev; \ |
908 | else \ |
909 | ((type)(void *)__next)->field.prev = __prev; \ |
910 | \ |
911 | if ((head) == __prev) \ |
912 | (head)->next = __next; \ |
913 | else \ |
914 | ((type)(void *)__prev)->field.next = __next; \ |
915 | \ |
916 | (elt)->field.next = NULL; \ |
917 | (elt)->field.prev = NULL; \ |
918 | MACRO_END |
919 | |
920 | /* |
921 | * Macro: queue_remove_first |
922 | * Function: |
923 | * Remove and return the entry at the head of |
924 | * the queue. |
925 | * Header: |
926 | * queue_remove_first(head, entry, type, field) |
927 | * entry is returned by reference |
928 | * Note: |
929 | * This should only be used with Method 2 queue iteration (element chains) |
930 | */ |
931 | #define queue_remove_first(head, entry, type, field) \ |
932 | MACRO_BEGIN \ |
933 | queue_entry_t __next; \ |
934 | \ |
935 | (entry) = (type)(void *) ((head)->next); \ |
936 | __next = (entry)->field.next; \ |
937 | \ |
938 | if ((head) == __next) \ |
939 | (head)->prev = (head); \ |
940 | else \ |
941 | ((type)(void *)(__next))->field.prev = (head); \ |
942 | (head)->next = __next; \ |
943 | \ |
944 | (entry)->field.next = NULL; \ |
945 | (entry)->field.prev = NULL; \ |
946 | MACRO_END |
947 | |
948 | /* |
949 | * Macro: queue_remove_last |
950 | * Function: |
951 | * Remove and return the entry at the tail of |
952 | * the queue. |
953 | * Header: |
954 | * queue_remove_last(head, entry, type, field) |
955 | * entry is returned by reference |
956 | * Note: |
957 | * This should only be used with Method 2 queue iteration (element chains) |
958 | */ |
959 | #define queue_remove_last(head, entry, type, field) \ |
960 | MACRO_BEGIN \ |
961 | queue_entry_t __prev; \ |
962 | \ |
963 | (entry) = (type)(void *) ((head)->prev); \ |
964 | __prev = (entry)->field.prev; \ |
965 | \ |
966 | if ((head) == __prev) \ |
967 | (head)->next = (head); \ |
968 | else \ |
969 | ((type)(void *)(__prev))->field.next = (head); \ |
970 | (head)->prev = __prev; \ |
971 | \ |
972 | (entry)->field.next = NULL; \ |
973 | (entry)->field.prev = NULL; \ |
974 | MACRO_END |
975 | |
976 | /* |
977 | * Macro: queue_assign |
978 | * Note: |
979 | * This should only be used with Method 2 queue iteration (element chains) |
980 | */ |
981 | #define queue_assign(to, from, type, field) \ |
982 | MACRO_BEGIN \ |
983 | ((type)(void *)((from)->prev))->field.next = (to); \ |
984 | ((type)(void *)((from)->next))->field.prev = (to); \ |
985 | *to = *from; \ |
986 | MACRO_END |
987 | |
988 | /* |
989 | * Macro: queue_new_head |
990 | * Function: |
991 | * rebase old queue to new queue head |
992 | * Header: |
993 | * queue_new_head(old, new, type, field) |
994 | * queue_t old; |
995 | * queue_t new; |
996 | * <type> is what's in our queue |
997 | * <field> is the chain field in (*<type>) |
998 | * Note: |
999 | * This should only be used with Method 2 queue iteration (element chains) |
1000 | */ |
1001 | #define queue_new_head(old, new, type, field) \ |
1002 | MACRO_BEGIN \ |
1003 | if (!queue_empty(old)) { \ |
1004 | *(new) = *(old); \ |
1005 | ((type)(void *)((new)->next))->field.prev = \ |
1006 | (new); \ |
1007 | ((type)(void *)((new)->prev))->field.next = \ |
1008 | (new); \ |
1009 | } else { \ |
1010 | queue_init(new); \ |
1011 | } \ |
1012 | MACRO_END |
1013 | |
1014 | /* |
1015 | * Macro: queue_iterate |
1016 | * Function: |
1017 | * iterate over each item in the queue. |
1018 | * Generates a 'for' loop, setting elt to |
1019 | * each item in turn (by reference). |
1020 | * Header: |
1021 | * queue_iterate(q, elt, type, field) |
1022 | * queue_t q; |
1023 | * <type> elt; |
1024 | * <type> is what's in our queue |
1025 | * <field> is the chain field in (*<type>) |
1026 | * Note: |
1027 | * This should only be used with Method 2 queue iteration (element chains) |
1028 | */ |
1029 | #define queue_iterate(head, elt, type, field) \ |
1030 | for ((elt) = (type)(void *) queue_first(head); \ |
1031 | !queue_end((head), (queue_entry_t)(elt)); \ |
1032 | (elt) = (type)(void *) queue_next(&(elt)->field)) |
1033 | |
1034 | #ifdef MACH_KERNEL_PRIVATE |
1035 | |
1036 | #include <kern/locks.h> |
1037 | |
1038 | /*----------------------------------------------------------------*/ |
1039 | /* |
1040 | * Define macros for queues with locks. |
1041 | */ |
1042 | struct mpqueue_head { |
1043 | struct queue_entry head; /* header for queue */ |
1044 | uint64_t earliest_soft_deadline; |
1045 | uint64_t count; |
1046 | lck_mtx_t lock_data; |
1047 | #if defined(__i386__) || defined(__x86_64__) |
1048 | lck_mtx_ext_t lock_data_ext; |
1049 | #endif |
1050 | }; |
1051 | |
1052 | typedef struct mpqueue_head mpqueue_head_t; |
1053 | |
1054 | #define round_mpq(size) (size) |
1055 | |
1056 | |
1057 | #if defined(__i386__) || defined(__x86_64__) |
1058 | |
1059 | #define mpqueue_init(q, lck_grp, lck_attr) \ |
1060 | MACRO_BEGIN \ |
1061 | queue_init(&(q)->head); \ |
1062 | lck_mtx_init_ext(&(q)->lock_data, \ |
1063 | &(q)->lock_data_ext, \ |
1064 | lck_grp, \ |
1065 | lck_attr); \ |
1066 | (q)->earliest_soft_deadline = UINT64_MAX; \ |
1067 | (q)->count = 0; \ |
1068 | MACRO_END |
1069 | |
1070 | #else |
1071 | |
1072 | #define mpqueue_init(q, lck_grp, lck_attr) \ |
1073 | MACRO_BEGIN \ |
1074 | queue_init(&(q)->head); \ |
1075 | lck_mtx_init(&(q)->lock_data, \ |
1076 | lck_grp, \ |
1077 | lck_attr); \ |
1078 | MACRO_END |
1079 | #endif |
1080 | |
1081 | |
1082 | #define mpenqueue_tail(q, elt) \ |
1083 | MACRO_BEGIN \ |
1084 | lck_mtx_lock_spin_always(&(q)->lock_data); \ |
1085 | enqueue_tail(&(q)->head, elt); \ |
1086 | lck_mtx_unlock_always(&(q)->lock_data); \ |
1087 | MACRO_END |
1088 | |
1089 | #define mpdequeue_head(q, elt) \ |
1090 | MACRO_BEGIN \ |
1091 | lck_mtx_lock_spin_always(&(q)->lock_data); \ |
1092 | if (queue_empty(&(q)->head)) \ |
1093 | *(elt) = 0; \ |
1094 | else \ |
1095 | *(elt) = dequeue_head(&(q)->head); \ |
1096 | lck_mtx_unlock_always(&(q)->lock_data); \ |
1097 | MACRO_END |
1098 | |
1099 | #endif /* MACH_KERNEL_PRIVATE */ |
1100 | |
1101 | __END_DECLS |
1102 | |
1103 | #endif /* _KERN_QUEUE_H_ */ |
1104 | |