src/queue_internal.h

   1 /*
   2  * Copyright (c) 2008-2011 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_APACHE_LICENSE_HEADER_START@
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  *
  18  * @APPLE_APACHE_LICENSE_HEADER_END@
  19  */
  20
  21 /*
  22  * IMPORTANT: This header file describes INTERNAL interfaces to libdispatch
  23  * which are subject to change in future releases of Mac OS X. Any applications
  24  * relying on these interfaces WILL break.
  25  */
  26
  27 #ifndef __DISPATCH_QUEUE_INTERNAL__
  28 #define __DISPATCH_QUEUE_INTERNAL__
  29
  30 #ifndef __DISPATCH_INDIRECT__
  31 #error "Please #include <dispatch/dispatch.h> instead of this file directly."
  32 #include <dispatch/base.h> // for HeaderDoc
  33 #endif
  34
  35 // If dc_vtable is less than 127, then the object is a continuation.
  36 // Otherwise, the object has a private layout and memory management rules. The
  37 // layout until after 'do_next' must align with normal objects.
  38 #define DISPATCH_CONTINUATION_HEADER(x) \
  39         _OS_OBJECT_HEADER( \
  40         const void *do_vtable, \
  41         do_ref_cnt, \
  42         do_xref_cnt); \
  43         struct dispatch_##x##_s *volatile do_next; \
  44         dispatch_function_t dc_func; \
  45         void *dc_ctxt; \
  46         void *dc_data; \
  47         void *dc_other;
  48
  49 #define DISPATCH_OBJ_ASYNC_BIT          0x1
  50 #define DISPATCH_OBJ_BARRIER_BIT        0x2
  51 #define DISPATCH_OBJ_GROUP_BIT          0x4
  52 #define DISPATCH_OBJ_SYNC_SLOW_BIT      0x8
  53 // vtables are pointers far away from the low page in memory
  54 #define DISPATCH_OBJ_IS_VTABLE(x) ((unsigned long)(x)->do_vtable > 127ul)
  55
  56 struct dispatch_continuation_s {
  57         DISPATCH_CONTINUATION_HEADER(continuation);
  58 };
  59
  60 typedef struct dispatch_continuation_s *dispatch_continuation_t;
  61
  62 struct dispatch_apply_s {
  63         size_t da_index;
  64         size_t da_iterations;
  65         void (*da_func)(void *, size_t);
  66         void *da_ctxt;
  67         _dispatch_thread_semaphore_t da_sema;
  68         dispatch_queue_t da_queue;
  69         size_t da_done;
  70         uint32_t da_thr_cnt;
  71 };
  72
  73 typedef struct dispatch_apply_s *dispatch_apply_t;
  74
  75 DISPATCH_CLASS_DECL(queue_attr);
  76 struct dispatch_queue_attr_s {
  77         DISPATCH_STRUCT_HEADER(queue_attr);
  78 };
  79
  80 #define DISPATCH_QUEUE_MIN_LABEL_SIZE 64
  81
  82 #ifdef __LP64__
  83 #define DISPATCH_QUEUE_CACHELINE_PAD (4*sizeof(void*))
  84 #else
  85 #define DISPATCH_QUEUE_CACHELINE_PAD (2*sizeof(void*))
  86 #endif
  87
  88 #define DISPATCH_QUEUE_HEADER \
  89         uint32_t volatile dq_running; \
  90         uint32_t dq_width; \
  91         struct dispatch_object_s *volatile dq_items_tail; \
  92         struct dispatch_object_s *volatile dq_items_head; \
  93         unsigned long dq_serialnum; \
  94         dispatch_queue_t dq_specific_q;
  95
  96 DISPATCH_CLASS_DECL(queue);
  97 struct dispatch_queue_s {
  98         DISPATCH_STRUCT_HEADER(queue);
  99         DISPATCH_QUEUE_HEADER;
 100         char dq_label[DISPATCH_QUEUE_MIN_LABEL_SIZE]; // must be last
 101         char _dq_pad[DISPATCH_QUEUE_CACHELINE_PAD]; // for static queues only
 102 };
 103
 104 DISPATCH_INTERNAL_SUBCLASS_DECL(queue_root, queue);
 105 DISPATCH_INTERNAL_SUBCLASS_DECL(queue_mgr, queue);
 106
 107 DISPATCH_DECL_INTERNAL_SUBCLASS(dispatch_queue_specific_queue, dispatch_queue);
 108 DISPATCH_CLASS_DECL(queue_specific_queue);
 109
 110 extern struct dispatch_queue_s _dispatch_mgr_q;
 111
 112 void _dispatch_queue_dispose(dispatch_queue_t dq);
 113 void _dispatch_queue_invoke(dispatch_queue_t dq);
 114 void _dispatch_queue_push_list_slow(dispatch_queue_t dq,
 115                 struct dispatch_object_s *obj, unsigned int n);
 116 void _dispatch_queue_push_slow(dispatch_queue_t dq,
 117                 struct dispatch_object_s *obj);
 118 dispatch_queue_t _dispatch_wakeup(dispatch_object_t dou);
 119 void _dispatch_queue_specific_queue_dispose(dispatch_queue_specific_queue_t
 120                 dqsq);
 121 bool _dispatch_queue_probe_root(dispatch_queue_t dq);
 122 bool _dispatch_mgr_wakeup(dispatch_queue_t dq);
 123 DISPATCH_NORETURN
 124 dispatch_queue_t _dispatch_mgr_thread(dispatch_queue_t dq);
 125
 126 #if DISPATCH_DEBUG
 127 void dispatch_debug_queue(dispatch_queue_t dq, const char* str);
 128 #else
 129 static inline void dispatch_debug_queue(dispatch_queue_t dq DISPATCH_UNUSED,
 130                 const char* str DISPATCH_UNUSED) {}
 131 #endif
 132
 133 size_t dispatch_queue_debug(dispatch_queue_t dq, char* buf, size_t bufsiz);
 134 size_t _dispatch_queue_debug_attr(dispatch_queue_t dq, char* buf,
 135                 size_t bufsiz);
 136
 137 #define DISPATCH_QUEUE_PRIORITY_COUNT 4
 138 #define DISPATCH_ROOT_QUEUE_COUNT (DISPATCH_QUEUE_PRIORITY_COUNT * 2)
 139
 140 // overcommit priority index values need bit 1 set
 141 enum {
 142         DISPATCH_ROOT_QUEUE_IDX_LOW_PRIORITY = 0,
 143         DISPATCH_ROOT_QUEUE_IDX_LOW_OVERCOMMIT_PRIORITY,
 144         DISPATCH_ROOT_QUEUE_IDX_DEFAULT_PRIORITY,
 145         DISPATCH_ROOT_QUEUE_IDX_DEFAULT_OVERCOMMIT_PRIORITY,
 146         DISPATCH_ROOT_QUEUE_IDX_HIGH_PRIORITY,
 147         DISPATCH_ROOT_QUEUE_IDX_HIGH_OVERCOMMIT_PRIORITY,
 148         DISPATCH_ROOT_QUEUE_IDX_BACKGROUND_PRIORITY,
 149         DISPATCH_ROOT_QUEUE_IDX_BACKGROUND_OVERCOMMIT_PRIORITY,
 150 };
 151
 152 extern unsigned long _dispatch_queue_serial_numbers;
 153 extern struct dispatch_queue_s _dispatch_root_queues[];
 154
 155 #if !__OBJC2__
 156
 157 DISPATCH_ALWAYS_INLINE
 158 static inline bool
 159 _dispatch_queue_push_list2(dispatch_queue_t dq, struct dispatch_object_s *head,
 160                 struct dispatch_object_s *tail)
 161 {
 162         struct dispatch_object_s *prev;
 163         tail->do_next = NULL;
 164         dispatch_atomic_store_barrier();
 165         prev = dispatch_atomic_xchg2o(dq, dq_items_tail, tail);
 166         if (fastpath(prev)) {
 167                 // if we crash here with a value less than 0x1000, then we are at a
 168                 // known bug in client code for example, see _dispatch_queue_dispose
 169                 // or _dispatch_atfork_child
 170                 prev->do_next = head;
 171         }
 172         return prev;
 173 }
 174
 175 DISPATCH_ALWAYS_INLINE
 176 static inline void
 177 _dispatch_queue_push_list(dispatch_queue_t dq, dispatch_object_t _head,
 178                 dispatch_object_t _tail, unsigned int n)
 179 {
 180         struct dispatch_object_s *head = _head._do, *tail = _tail._do;
 181         if (!fastpath(_dispatch_queue_push_list2(dq, head, tail))) {
 182                 _dispatch_queue_push_list_slow(dq, head, n);
 183         }
 184 }
 185
 186 DISPATCH_ALWAYS_INLINE
 187 static inline void
 188 _dispatch_queue_push(dispatch_queue_t dq, dispatch_object_t _tail)
 189 {
 190         struct dispatch_object_s *tail = _tail._do;
 191         if (!fastpath(_dispatch_queue_push_list2(dq, tail, tail))) {
 192                 _dispatch_queue_push_slow(dq, tail);
 193         }
 194 }
 195
 196 DISPATCH_ALWAYS_INLINE
 197 static inline dispatch_queue_t
 198 _dispatch_queue_get_current(void)
 199 {
 200         return _dispatch_thread_getspecific(dispatch_queue_key);
 201 }
 202
 203 DISPATCH_ALWAYS_INLINE DISPATCH_CONST
 204 static inline dispatch_queue_t
 205 _dispatch_get_root_queue(long priority, bool overcommit)
 206 {
 207         if (overcommit) switch (priority) {
 208         case DISPATCH_QUEUE_PRIORITY_BACKGROUND:
 209 #if !DISPATCH_NO_BG_PRIORITY
 210                 return &_dispatch_root_queues[
 211                                 DISPATCH_ROOT_QUEUE_IDX_BACKGROUND_OVERCOMMIT_PRIORITY];
 212 #endif
 213         case DISPATCH_QUEUE_PRIORITY_LOW:
 214                 return &_dispatch_root_queues[
 215                                 DISPATCH_ROOT_QUEUE_IDX_LOW_OVERCOMMIT_PRIORITY];
 216         case DISPATCH_QUEUE_PRIORITY_DEFAULT:
 217                 return &_dispatch_root_queues[
 218                                 DISPATCH_ROOT_QUEUE_IDX_DEFAULT_OVERCOMMIT_PRIORITY];
 219         case DISPATCH_QUEUE_PRIORITY_HIGH:
 220                 return &_dispatch_root_queues[
 221                                 DISPATCH_ROOT_QUEUE_IDX_HIGH_OVERCOMMIT_PRIORITY];
 222         }
 223         switch (priority) {
 224         case DISPATCH_QUEUE_PRIORITY_BACKGROUND:
 225 #if !DISPATCH_NO_BG_PRIORITY
 226                 return &_dispatch_root_queues[
 227                                 DISPATCH_ROOT_QUEUE_IDX_BACKGROUND_PRIORITY];
 228 #endif
 229         case DISPATCH_QUEUE_PRIORITY_LOW:
 230                 return &_dispatch_root_queues[DISPATCH_ROOT_QUEUE_IDX_LOW_PRIORITY];
 231         case DISPATCH_QUEUE_PRIORITY_DEFAULT:
 232                 return &_dispatch_root_queues[DISPATCH_ROOT_QUEUE_IDX_DEFAULT_PRIORITY];
 233         case DISPATCH_QUEUE_PRIORITY_HIGH:
 234                 return &_dispatch_root_queues[DISPATCH_ROOT_QUEUE_IDX_HIGH_PRIORITY];
 235         default:
 236                 return NULL;
 237         }
 238 }
 239
 240 // Note to later developers: ensure that any initialization changes are
 241 // made for statically allocated queues (i.e. _dispatch_main_q).
 242 static inline void
 243 _dispatch_queue_init(dispatch_queue_t dq)
 244 {
 245         dq->do_next = DISPATCH_OBJECT_LISTLESS;
 246         // Default target queue is overcommit!
 247         dq->do_targetq = _dispatch_get_root_queue(0, true);
 248         dq->dq_running = 0;
 249         dq->dq_width = 1;
 250         dq->dq_serialnum = dispatch_atomic_inc(&_dispatch_queue_serial_numbers) - 1;
 251 }
 252
 253 dispatch_continuation_t
 254 _dispatch_continuation_alloc_from_heap(void);
 255
 256 DISPATCH_ALWAYS_INLINE
 257 static inline dispatch_continuation_t
 258 _dispatch_continuation_alloc_cacheonly(void)
 259 {
 260         dispatch_continuation_t dc;
 261         dc = fastpath(_dispatch_thread_getspecific(dispatch_cache_key));
 262         if (dc) {
 263                 _dispatch_thread_setspecific(dispatch_cache_key, dc->do_next);
 264         }
 265         return dc;
 266 }
 267
 268 DISPATCH_ALWAYS_INLINE
 269 static inline dispatch_continuation_t
 270 _dispatch_continuation_alloc(void)
 271 {
 272         dispatch_continuation_t dc;
 273
 274         dc = fastpath(_dispatch_continuation_alloc_cacheonly());
 275         if(!dc) {
 276                 return _dispatch_continuation_alloc_from_heap();
 277         }
 278         return dc;
 279 }
 280
 281
 282 DISPATCH_ALWAYS_INLINE
 283 static inline void
 284 _dispatch_continuation_free(dispatch_continuation_t dc)
 285 {
 286         dispatch_continuation_t prev_dc;
 287         prev_dc = _dispatch_thread_getspecific(dispatch_cache_key);
 288         dc->do_next = prev_dc;
 289         _dispatch_thread_setspecific(dispatch_cache_key, dc);
 290 }
 291
 292 #endif // !__OBJC2__
 293
 294 #endif