1 /*
2 * Copyright (c) 2025 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 #pragma once
30
31 #include "mocks/std_safe.h"
32 #include "mocks/unit_test_utils.h"
33
34 #define FIBERS_DEFAULT_STACK_SIZE 1048576 // 8mb
35 #define FIBERS_INTERNAL_YIELD_PROB 4 // switch on internal yield points 1/4 of the times
36 #define FIBERS_DEFAULT_YIELD_PROB 256
37
38 /* Configuration variables */
39 extern int fibers_log_level; // see FIBERS_LOG and the levels FIBERS_LOG_*
40 extern bool fibers_debug; // Mostly used to collect backtraces at fibers events points. The slowdown is huge.
41 extern int fibers_abort_on_error; // By default do not stop execution at errors, set to not 0 to abort.
42 extern uint64_t fibers_may_yield_probability; // FIBERS_DEFAULT_YIELD_PROB by default
43
44 typedef struct fiber_context *fiber_t;
45
46 typedef uint32_t fiber_yield_reason_t;
47
48 #define FIBERS_YIELD_REASON_ORDER_PRE_SHIFT (16)
49 #define FIBERS_YIELD_REASON_ORDER_PRE (0 << FIBERS_YIELD_REASON_ORDER_PRE_SHIFT)
50 #define FIBERS_YIELD_REASON_ORDER_POST (1 << FIBERS_YIELD_REASON_ORDER_PRE_SHIFT)
51 #define FIBERS_YIELD_REASON_ORDER(x) ((x) & (1 << FIBERS_YIELD_REASON_ORDER_PRE_SHIFT))
52
53 #define FIBERS_YIELD_REASON_ERROR_SHIFT (17)
54 #define FIBERS_YIELD_REASON_ERROR (1 << FIBERS_YIELD_REASON_ERROR_SHIFT)
55 #define FIBERS_YIELD_REASON_ERROR_IF(x) ((x) ? FIBERS_YIELD_REASON_ERROR : 0)
56 #define FIBERS_YIELD_REASON_IS_ERROR(x) (!!((x) & FIBERS_YIELD_REASON_ERROR))
57
58 #define FIBERS_YIELD_REASON_MUTEX_SHIFT (18)
59 #define FIBERS_YIELD_REASON_MUTEX_LOCK (0 << FIBERS_YIELD_REASON_MUTEX_SHIFT)
60 #define FIBERS_YIELD_REASON_MUTEX_UNLOCK (1 << FIBERS_YIELD_REASON_MUTEX_SHIFT)
61 #define FIBERS_YIELD_REASON_MUTEX_DESTROY (2 << FIBERS_YIELD_REASON_MUTEX_SHIFT)
62 #define FIBERS_YIELD_REASON_MUTEX_STATE(x) ((x) & (3 << FIBERS_YIELD_REASON_MUTEX_DESTROY))
63
64 #define FIBERS_YIELD_REASON_CATEGORY(x) ((x) & 0xffff)
65 #define FIBERS_YIELD_REASON_UNKNOWN 0
66 #define FIBERS_YIELD_REASON_MUTEX 1
67 #define FIBERS_YIELD_REASON_PREEMPTION_CONTROL 2
68 #define FIBERS_YIELD_REASON_PREEMPTION_TRIGGER 3
69 #define FIBERS_YIELD_REASON_BLOCKED 4
70 #define FIBERS_YIELD_REASON_WAKEUP 5
71 #define FIBERS_YIELD_REASON_CREATE 6
72 #define FIBERS_YIELD_REASON_JOIN 7
73
74 #define FIBERS_YIELD_REASON_PREEMPTION_WILL_ENABLE (FIBERS_YIELD_REASON_PREEMPTION_CONTROL | \
75 FIBERS_YIELD_REASON_MUTEX_UNLOCK | \
76 FIBERS_YIELD_REASON_ORDER_PRE)
77
78 #define FIBERS_YIELD_REASON_PREEMPTION_DID_ENABLE (FIBERS_YIELD_REASON_PREEMPTION_CONTROL | \
79 FIBERS_YIELD_REASON_MUTEX_UNLOCK | \
80 FIBERS_YIELD_REASON_ORDER_POST)
81
82 #define FIBERS_YIELD_REASON_PREEMPTION_WILL_DISABLE (FIBERS_YIELD_REASON_PREEMPTION_CONTROL | \
83 FIBERS_YIELD_REASON_MUTEX_LOCK | \
84 FIBERS_YIELD_REASON_ORDER_PRE)
85
86 #define FIBERS_YIELD_REASON_PREEMPTION_DID_DISABLE (FIBERS_YIELD_REASON_PREEMPTION_CONTROL | \
87 FIBERS_YIELD_REASON_MUTEX_LOCK | \
88 FIBERS_YIELD_REASON_ORDER_POST)
89
90 #define FIBERS_YIELD_REASON_MUTEX_WILL_LOCK (FIBERS_YIELD_REASON_MUTEX | \
91 FIBERS_YIELD_REASON_MUTEX_LOCK | \
92 FIBERS_YIELD_REASON_ORDER_PRE)
93
94 #define FIBERS_YIELD_REASON_MUTEX_DID_LOCK (FIBERS_YIELD_REASON_MUTEX | \
95 FIBERS_YIELD_REASON_MUTEX_LOCK | \
96 FIBERS_YIELD_REASON_ORDER_POST)
97
98 #define FIBERS_YIELD_REASON_MUTEX_TRY_LOCK_FAIL (FIBERS_YIELD_REASON_MUTEX_DID_LOCK | \
99 FIBERS_YIELD_REASON_ERROR)
100
101 #define FIBERS_YIELD_REASON_MUTEX_WILL_UNLOCK (FIBERS_YIELD_REASON_MUTEX | \
102 FIBERS_YIELD_REASON_MUTEX_UNLOCK | \
103 FIBERS_YIELD_REASON_ORDER_PRE)
104
105 #define FIBERS_YIELD_REASON_MUTEX_DID_UNLOCK (FIBERS_YIELD_REASON_MUTEX | \
106 FIBERS_YIELD_REASON_MUTEX_UNLOCK | \
107 FIBERS_YIELD_REASON_ORDER_POST)
108
109
110 extern fiber_t fibers_current;
111 extern struct fibers_queue fibers_run_queue;
112 extern struct fibers_queue fibers_existing_queue;
113
114 #define FIBERS_ASSERT(expr, msg, ...) do { \
115 if (!(expr)) { \
116 raw_printf("fibers failure: current=%d expr=" #expr ": " msg "\n", (fibers_current ? fibers_current->id : -1 ), ##__VA_ARGS__); \
117 if (fibers_debug) print_current_backtrace(); \
118 if (fibers_abort_on_error) abort(); \
119 } \
120 } while (0)
121
122 struct fibers_scheduler_t {
123 void (*fibers_choose_next)(void *arg, int state);
124 bool (*fibers_should_yield)(void *arg, uint64_t probability, fiber_yield_reason_t reason);
125 };
126
127 extern void fibers_scheduler_get(struct fibers_scheduler_t **scheduler, void **context);
128 extern void fibers_scheduler_set(struct fibers_scheduler_t *scheduler, void *context);
129
130 extern struct fibers_scheduler_t *fibers_scheduler;
131 extern void *fibers_scheduler_context;
132
133 #define FIBERS_LOG_WARN 0
134 #define FIBERS_LOG_INFO 1
135 #define FIBERS_LOG_DEBUG 2
136 #define FIBERS_LOG_TRACE 3
137 #define FIBERS_LOG(level, msg, ...) do { \
138 if (fibers_log_level >= (level)) { \
139 raw_printf("fibers log(%d): current=%d: " msg "\n", (level), (fibers_current ? fibers_current->id : -1 ), ##__VA_ARGS__); \
140 if (fibers_debug) print_current_backtrace(); \
141 } \
142 } while (0)
143
144 struct fiber_context {
145 int id; /* unique fiber id assigned at creation */
146 int state; /* current state */
147 #define FIBER_RUN 0x1
148 #define FIBER_STOP 0x2
149 #define FIBER_WAIT 0x4
150 #define FIBER_JOIN 0x8
151 #define FIBER_DEAD 0x10
152
153 int may_yield_disabled;
154 int disable_race_checker;
155
156 fiber_t joining; /* waiting for this fiber if FIBER_JOIN */
157 fiber_t joiner; /* signal this fiber on termination */
158 fiber_t next; /* next fiber on the same queue (run or wait queue) */
159 fiber_t next_existing; /* next fiber in the list of existing fibers */
160
161 void* (*start_routine)(void*); /* start routine function pointer */
162 void *ret_value; /* return value upon exit */
163 jmp_buf env; /* buf to jump when run */
164 const void *stack_bottom; /* stack bottom addr, 16 bytes aligned */
165 size_t stack_size;
166
167 void *extra; /* per-fiber extra data */
168 void (*extra_cleanup_routine)(void*);
169
170 #ifdef __BUILDING_WITH_ASAN__
171 void *sanitizer_fake_stack; /* set by asan to track fake stack switches */
172 #endif
173 #ifdef __BUILDING_WITH_TSAN__
174 void *tsan_fiber;
175 #endif
176 };
177
178 static void
fibers_checker_atomic_begin(void)179 fibers_checker_atomic_begin(void)
180 {
181 fibers_current->disable_race_checker++;
182 }
183
184 static void
fibers_checker_atomic_end(void)185 fibers_checker_atomic_end(void)
186 {
187 fibers_current->disable_race_checker--;
188 }
189
190 struct fibers_queue {
191 fiber_t top;
192 size_t count;
193 };
194
195 static inline void
fibers_queue_push(struct fibers_queue * queue,fiber_t fiber)196 fibers_queue_push(struct fibers_queue *queue, fiber_t fiber)
197 {
198 FIBERS_ASSERT(fiber->next == NULL, "fibers_queue_push: already on another queue");
199 fiber->next = queue->top;
200 queue->top = fiber;
201 queue->count++;
202 }
203
204 static inline fiber_t
fibers_queue_pop(struct fibers_queue * queue,size_t index)205 fibers_queue_pop(struct fibers_queue *queue, size_t index)
206 {
207 FIBERS_ASSERT(queue->count > 0, "fibers_queue_pop: empty queue");
208 FIBERS_ASSERT(queue->count > index, "fibers_queue_pop: invalid index");
209 fiber_t *iter = &queue->top;
210 while (*iter != NULL) {
211 if (index == 0) {
212 fiber_t fiber = *iter;
213 *iter = fiber->next;
214 fiber->next = NULL;
215 queue->count--;
216 return fiber;
217 }
218 index--;
219 iter = &(*iter)->next;
220 }
221 FIBERS_ASSERT(false, "fibers_queue_pop: unreachable");
222 return NULL;
223 }
224
225 static inline fiber_t
fibers_queue_peek(struct fibers_queue * queue)226 fibers_queue_peek(struct fibers_queue *queue)
227 {
228 for (fiber_t *iter = &queue->top;
229 *iter != NULL;
230 iter = &(*iter)->next) {
231 if ((*iter)->next == NULL) {
232 return *iter;
233 }
234 }
235 return NULL;
236 }
237
238 static inline bool
fibers_queue_contains(struct fibers_queue * queue,fiber_t fiber)239 fibers_queue_contains(struct fibers_queue *queue, fiber_t fiber)
240 {
241 fiber_t iter = queue->top;
242 while (iter != NULL) {
243 if (iter == fiber) {
244 return true;
245 }
246 iter = iter->next;
247 }
248 return false;
249 }
250
251 static inline bool
fibers_queue_remove(struct fibers_queue * queue,fiber_t fiber)252 fibers_queue_remove(struct fibers_queue *queue, fiber_t fiber)
253 {
254 fiber_t *iter = &queue->top;
255 while (*iter != NULL) {
256 if (*iter == fiber) {
257 *iter = fiber->next;
258 fiber->next = NULL;
259 queue->count--;
260 return true;
261 }
262 iter = &(*iter)->next;
263 }
264 return false;
265 }
266
267 static inline fiber_t
fibers_queue_remove_by_id(struct fibers_queue * queue,int fiber_id)268 fibers_queue_remove_by_id(struct fibers_queue *queue, int fiber_id)
269 {
270 fiber_t *iter = &queue->top;
271 while (*iter != NULL) {
272 if ((*iter)->id == fiber_id) {
273 fiber_t fiber = *iter;
274 *iter = fiber->next;
275 fiber->next = NULL;
276 queue->count--;
277 return fiber;
278 }
279 iter = &(*iter)->next;
280 }
281 return NULL;
282 }
283
284 static inline size_t
fibers_queue_count(struct fibers_queue * queue)285 fibers_queue_count(struct fibers_queue *queue)
286 {
287 fiber_t iter = queue->top;
288 size_t count = 0;
289 while (iter != NULL) {
290 count++;
291 iter = iter->next;
292 }
293 return count;
294 }
295
296 static inline void
fibers_existing_push(fiber_t fiber)297 fibers_existing_push(fiber_t fiber)
298 {
299 FIBERS_ASSERT(fiber->next_existing == NULL, "fibers_existing_push: already on existing queue");
300 fiber->next_existing = fibers_existing_queue.top;
301 fibers_existing_queue.top = fiber;
302 fibers_existing_queue.count++;
303 }
304
305 static inline bool
fibers_existing_remove(fiber_t fiber)306 fibers_existing_remove(fiber_t fiber)
307 {
308 fiber_t *iter = &fibers_existing_queue.top;
309 while (*iter != NULL) {
310 if (*iter == fiber) {
311 *iter = fiber->next_existing;
312 fiber->next_existing = NULL;
313 fibers_existing_queue.count--;
314 return true;
315 }
316 iter = &(*iter)->next_existing;
317 }
318 return false;
319 }
320
321 // Create, exit and join are similar to pthread.
322 // Detaching is not supported at the moment.
323 extern fiber_t fibers_create(size_t stack_size, void *(*start_routine)(void*), void *arg);
324 extern void fibers_exit(void *ret_value);
325 extern void *fibers_join(fiber_t target);
326
327 extern void fibers_switch_to(fiber_t target, int state);
328 extern void fibers_switch_to_by_id(int target_id, int state);
329 extern void fibers_switch_top(int state);
330 extern void fibers_switch_random(int state);
331 extern void fibers_switch_helper(fiber_t target, int state);
332 extern void fibers_choose_next(int state);
333
334 // Force a context switch
335 extern void fibers_yield(void);
336 // Force a context switch to a specific fiber (must be ready to be scheduled)
337 extern void fibers_yield_to(int fiber_id);
338 // Context switch with fibers_may_yield_probability
339 extern bool fibers_may_yield(void);
340 // Context switch with a default priority for infrastructure
341 extern bool fibers_may_yield_internal();
342 // Context switch with a default priority for infrastructure and explicit reason
343 extern bool fibers_may_yield_internal_with_reason(fiber_yield_reason_t reason);
344 // Context switch with custom probability
345 extern bool fibers_may_yield_with_prob(uint64_t probability);
346 // Context switch with fibers_may_yield_probability and an explicit reason
347 extern bool fibers_may_yield_with_reason(fiber_yield_reason_t reason);
348 // Context switch with custom probability and explicit reason
349 extern bool fibers_may_yield_with_prob_and_reason(uint64_t probability, fiber_yield_reason_t reason);
350