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 #define _XOPEN_SOURCE // To use *context deprecated API on OSX
30 #define BSD_KERNEL_PRIVATE
31
32 #include "fibers.h"
33 #include "random.h"
34
35 #include <sys/errno.h>
36 #include <sys/types.h>
37 #include <sys/signal.h>
38
39 #ifdef __BUILDING_WITH_TSAN__
40 #include <sanitizer/tsan_interface.h>
41 #endif
42 #ifdef __BUILDING_WITH_ASAN__
43 #include <sanitizer/asan_interface.h>
44 #endif
45
46 // from ucontext.h
47 #include <sys/_types/_ucontext.h>
48 extern void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...);
49 extern int swapcontext(ucontext_t *oucp, const ucontext_t *ucp);
50 extern int getcontext(ucontext_t *ucp);
51 extern int setcontext(const ucontext_t *ucp);
52
53 int fibers_log_level;
54 bool fibers_debug;
55 int fibers_abort_on_error = 0;
56
57 uint64_t fibers_may_yield_probability = FIBERS_DEFAULT_YIELD_PROB;
58
59 struct fiber_context fibers_main = {
60 .id = 0,
61 .state = FIBER_RUN,
62 };
63 static int fibers_last_forged_id = 0;
64
65 fiber_t fibers_current = &fibers_main; /* currently running */
66 struct fibers_queue fibers_run_queue; /* ready to be scheduled */
67 struct fibers_queue fibers_existing_queue = { .top = &fibers_main, .count = 1 }; /* existing fibers */
68
69 static void
fibers_default_choose_next(__unused void * arg,int state)70 fibers_default_choose_next(__unused void *arg, int state)
71 {
72 fibers_switch_random(state);
73 }
74
75 static bool
fibers_default_should_yield(__unused void * arg,uint64_t probability,__unused fiber_yield_reason_t reason)76 fibers_default_should_yield(__unused void *arg, uint64_t probability, __unused fiber_yield_reason_t reason)
77 {
78 return probability && random_below(probability) == 0;
79 }
80
81 struct fibers_scheduler_t fibers_default_scheduler = {
82 .fibers_choose_next = &fibers_default_choose_next,
83 .fibers_should_yield = &fibers_default_should_yield
84 };
85
86 struct fibers_scheduler_t *fibers_scheduler = &fibers_default_scheduler;
87 void *fibers_scheduler_context = 0;
88
89 void
fibers_scheduler_get(struct fibers_scheduler_t ** scheduler,void ** context)90 fibers_scheduler_get(struct fibers_scheduler_t **scheduler, void **context)
91 {
92 *scheduler = fibers_scheduler;
93 *context = fibers_scheduler_context;
94 }
95
96 void
fibers_scheduler_set(struct fibers_scheduler_t * scheduler,void * context)97 fibers_scheduler_set(struct fibers_scheduler_t *scheduler, void *context)
98 {
99 fibers_scheduler = scheduler;
100 fibers_scheduler_context = context;
101 }
102
103 struct fibers_create_trampoline_args {
104 fiber_t fiber;
105 void *start_routine_arg;
106 jmp_buf parent_env;
107 };
108
109 static void
fibers_create_trampoline(int arg1,int arg2)110 fibers_create_trampoline(int arg1, int arg2)
111 {
112 struct fibers_create_trampoline_args *args = (struct fibers_create_trampoline_args *)(((uintptr_t)arg1 << 32) | (uintptr_t)arg2);
113 // Copy fiber and arg to the local scope as by the time start_routine is called the parent fibers_create stack may have been deallocated
114 fiber_t fiber = args->fiber;
115 void *start_routine_arg = args->start_routine_arg;
116
117 #ifdef __BUILDING_WITH_ASAN__
118 __sanitizer_finish_switch_fiber(&fiber->sanitizer_fake_stack, &fiber->stack_bottom, &fiber->stack_size);
119 #endif
120
121 // setjmp/longjmp are faster context switch primitives compared to swapcontext
122 if (setjmp(fiber->env) == 0) {
123 // The first time the setjmp is called to save the current context in fiber->env
124 // we end un in this branch in which we switch back to fibers_create
125 // When the fiber will be scheduled for the first time, setjmp(fiber->env) != 0
126 // and thus the execution will continue in the other branch that calls args.start_routine
127 #ifdef __BUILDING_WITH_ASAN__
128 __sanitizer_start_switch_fiber(&fibers_current->sanitizer_fake_stack, fibers_current->stack_bottom, fibers_current->stack_size);
129 #endif
130 #ifdef __BUILDING_WITH_TSAN__
131 __tsan_switch_to_fiber(fibers_current->tsan_fiber, 0);
132 #endif
133 longjmp(args->parent_env, 1337);
134 }
135
136 #ifdef __BUILDING_WITH_ASAN__
137 __sanitizer_finish_switch_fiber(&fiber->sanitizer_fake_stack, &fiber->stack_bottom, &fiber->stack_size);
138 #endif
139
140 fibers_current = fiber;
141 FIBERS_LOG(FIBERS_LOG_INFO, "starting to execute the routine");
142
143 void *ret_value = fiber->start_routine(start_routine_arg);
144 fibers_exit(ret_value);
145 }
146
147 fiber_t
fibers_create(size_t stack_size,void * (* start_routine)(void *),void * arg)148 fibers_create(size_t stack_size, void* (*start_routine)(void*), void* arg)
149 {
150 if (fibers_current == &fibers_main && fibers_main.stack_bottom == NULL) {
151 // fibers_main has no stack_bottom or stack_size, get them here the first time
152 void* stackaddr = pthread_get_stackaddr_np(pthread_self());
153 size_t stacksize = pthread_get_stacksize_np(pthread_self());
154 fibers_main.stack_bottom = stackaddr - stacksize;
155 fibers_main.stack_size = stacksize;
156
157 #ifdef __BUILDING_WITH_TSAN__
158 fibers_main.tsan_fiber = __tsan_get_current_fiber();
159 __tsan_set_fiber_name(fibers_main.tsan_fiber, "fiber0");
160 #endif
161 }
162
163 void *stack_addr = malloc(stack_size);
164
165 fiber_t fiber = calloc(1, sizeof(struct fiber_context));
166 fiber->id = ++fibers_last_forged_id;
167 FIBERS_ASSERT(fibers_last_forged_id != 0, "fibers_create: new fiber id integer overflow");
168 fiber->state = FIBER_STOP;
169 fiber->start_routine = start_routine;
170 fiber->stack_size = stack_size;
171 fiber->stack_bottom = stack_addr;
172 FIBERS_ASSERT(fiber->stack_bottom, "fibers_create: stack malloc failed");
173
174 #ifdef __BUILDING_WITH_TSAN__
175 fiber->tsan_fiber = __tsan_create_fiber(0);
176 char tsan_fiber_name[32];
177 snprintf(tsan_fiber_name, 32, "fiber%d", fiber->id);
178 __tsan_set_fiber_name(fiber->tsan_fiber, tsan_fiber_name);
179 #endif
180
181 ucontext_t tmp_uc;
182 ucontext_t child_uc = {0};
183 FIBERS_ASSERT(getcontext(&child_uc) == 0, "fibers_create: getcontext");
184 child_uc.uc_stack.ss_sp = stack_addr;
185 child_uc.uc_stack.ss_size = stack_size;
186 child_uc.uc_link = 0;
187
188 struct fibers_create_trampoline_args trampoline_args = {0};
189 trampoline_args.fiber = fiber;
190 trampoline_args.start_routine_arg = arg;
191
192 int trampoline_args1 = (int)((uintptr_t)&trampoline_args >> 32);
193 int trampoline_args2 = (int)((uintptr_t)&trampoline_args);
194
195 makecontext(&child_uc, (void (*)())fibers_create_trampoline, 2, trampoline_args1, trampoline_args2);
196
197 // switch to the trampoline to setup the setjmp env of the fiber on the newly created stack, then switch back
198 // setjmp/longjmp are faster context switch primitives, swapcontext will never be used again for this fiber
199 // ref. the ThreadSanitizer fibers example in LLVM at compiler-rt/test/tsan/fiber_longjmp.cpp
200 if (setjmp(trampoline_args.parent_env) == 0) {
201 #ifdef __BUILDING_WITH_ASAN__
202 __sanitizer_start_switch_fiber(&fiber->sanitizer_fake_stack, fiber->stack_bottom, fiber->stack_size);
203 #endif
204 #ifdef __BUILDING_WITH_TSAN__
205 __tsan_switch_to_fiber(fiber->tsan_fiber, 0);
206 #endif
207 FIBERS_ASSERT(swapcontext(&tmp_uc, &child_uc) == 0, "fibers_create: swapcontext");
208 }
209
210 #ifdef __BUILDING_WITH_ASAN__
211 // fibers_create_trampoline did not change fibers_current
212 __sanitizer_finish_switch_fiber(&fibers_current->sanitizer_fake_stack, &fibers_current->stack_bottom, &fibers_current->stack_size);
213 #endif
214
215 fibers_queue_push(&fibers_run_queue, fiber);
216 fibers_existing_push(fiber);
217
218 FIBERS_LOG(FIBERS_LOG_INFO, "fiber %d created", fiber->id);
219
220 /* chance to schedule the newly created fiber */
221 fibers_may_yield_internal_with_reason(FIBERS_YIELD_REASON_CREATE);
222 return fiber;
223 }
224
225 static void
fibers_dispose(fiber_t fiber)226 fibers_dispose(fiber_t fiber)
227 {
228 FIBERS_LOG(FIBERS_LOG_DEBUG, "dispose %d", fiber->id);
229
230 fibers_existing_remove(fiber);
231
232 #ifdef __BUILDING_WITH_TSAN__
233 __tsan_destroy_fiber(fiber->tsan_fiber);
234 #endif
235
236 if (fiber->extra_cleanup_routine) {
237 fiber->extra_cleanup_routine(fiber->extra);
238 }
239
240 free((void*)fiber->stack_bottom);
241 free(fiber);
242 }
243
244 void
fibers_exit(void * ret_value)245 fibers_exit(void *ret_value)
246 {
247 FIBERS_ASSERT(fibers_current->may_yield_disabled == 0, "fibers_exit: fibers_current->may_yield_disabled is not 0");
248
249 fibers_current->ret_value = ret_value;
250 if (fibers_current->joiner) {
251 FIBERS_LOG(FIBERS_LOG_INFO, "exiting, joined by %d", fibers_current->joiner->id);
252 fibers_queue_push(&fibers_run_queue, fibers_current->joiner);
253 } else {
254 FIBERS_LOG(FIBERS_LOG_INFO, "exiting, no joiner");
255 }
256
257 fibers_choose_next(FIBER_DEAD);
258 FIBERS_ASSERT(false, "fibers_exit: unreachable");
259 }
260
261 void *
fibers_join(fiber_t target)262 fibers_join(fiber_t target)
263 {
264 FIBERS_ASSERT(fibers_current->may_yield_disabled == 0, "fibers_join: fibers_current->may_yield_disabled is not 0");
265
266 fibers_may_yield_internal_with_reason(FIBERS_YIELD_REASON_JOIN | FIBERS_YIELD_REASON_ORDER_PRE);
267
268 FIBERS_LOG(FIBERS_LOG_INFO, "join %d", target->id);
269 if (target->state != FIBER_DEAD) {
270 FIBERS_ASSERT(target->joiner == NULL, "fibers_join: %d already joined by %d", target->id, target->joiner->id);
271
272 target->joiner = fibers_current;
273 fibers_current->joining = target;
274
275 // RANGELOCKINGTODO rdar://150845975 maybe have a queue for fibers in join to output debug info in case of deadlock
276 fibers_choose_next(FIBER_JOIN);
277 }
278
279 FIBERS_LOG(FIBERS_LOG_INFO, "finish joining %d", target->id);
280 FIBERS_ASSERT(target->state == FIBER_DEAD, "fibers_join: not dead");
281
282 void *ret_value = target->ret_value;
283 fibers_dispose(target);
284
285 fibers_may_yield_internal_with_reason(FIBERS_YIELD_REASON_JOIN | FIBERS_YIELD_REASON_ORDER_POST);
286 return ret_value;
287 }
288
289 void
fibers_switch_helper(fiber_t target,int state)290 fibers_switch_helper(fiber_t target, int state)
291 {
292 if (target == fibers_current) {
293 target->state = FIBER_RUN;
294 return;
295 }
296 FIBERS_LOG(FIBERS_LOG_TRACE, "switch to %d, state=%d", target->id, state);
297
298 fibers_current->state = state;
299 fiber_t save = fibers_current;
300
301 if (setjmp(save->env) == 0) {
302 #ifdef __BUILDING_WITH_ASAN__
303 __sanitizer_start_switch_fiber(&target->sanitizer_fake_stack, target->stack_bottom, target->stack_size);
304 #endif
305 #ifdef __BUILDING_WITH_TSAN__
306 __tsan_switch_to_fiber(target->tsan_fiber, state == FIBER_DEAD ? 0 : __tsan_switch_to_fiber_no_sync);
307 #endif
308 longjmp(target->env, 1337);
309 }
310 #ifdef __BUILDING_WITH_ASAN__
311 __sanitizer_finish_switch_fiber(&save->sanitizer_fake_stack, &save->stack_bottom, &save->stack_size);
312 #endif
313
314 fibers_current = save;
315 save->state = FIBER_RUN;
316 }
317
318 void
fibers_choose_next(int state)319 fibers_choose_next(int state)
320 {
321 fibers_scheduler->fibers_choose_next(fibers_scheduler_context, state);
322 }
323
324 void
fibers_switch_to(fiber_t target,int state)325 fibers_switch_to(fiber_t target, int state)
326 {
327 FIBERS_ASSERT(fibers_queue_remove(&fibers_run_queue, target), "fibers_switch_to");
328 fibers_switch_helper(target, state);
329 }
330
331 void
fibers_switch_to_by_id(int target_id,int state)332 fibers_switch_to_by_id(int target_id, int state)
333 {
334 fiber_t target = fibers_queue_remove_by_id(&fibers_run_queue, target_id);
335 FIBERS_ASSERT(target != NULL, "fibers_switch_to_by_id");
336 fibers_switch_helper(target, state);
337 }
338
339 void
fibers_switch_top(int state)340 fibers_switch_top(int state)
341 {
342 fiber_t target = fibers_queue_pop(&fibers_run_queue, 0);
343 fibers_switch_helper(target, state);
344 }
345
346 void
fibers_switch_random(int state)347 fibers_switch_random(int state)
348 {
349 fiber_t target = fibers_queue_pop(&fibers_run_queue, random_below(fibers_run_queue.count));
350 fibers_switch_helper(target, state);
351 }
352
353 void
fibers_yield_to(int fiber_id)354 fibers_yield_to(int fiber_id)
355 {
356 fibers_queue_push(&fibers_run_queue, fibers_current);
357 fibers_switch_to_by_id(fiber_id, FIBER_STOP);
358 }
359
360 void
fibers_yield(void)361 fibers_yield(void)
362 {
363 fibers_queue_push(&fibers_run_queue, fibers_current);
364 fibers_choose_next(FIBER_STOP);
365 }
366
367 bool
fibers_may_yield_internal(void)368 fibers_may_yield_internal(void)
369 {
370 return fibers_may_yield_with_prob_and_reason(FIBERS_INTERNAL_YIELD_PROB, FIBERS_YIELD_REASON_UNKNOWN);
371 }
372
373 bool
fibers_may_yield_internal_with_reason(fiber_yield_reason_t reason)374 fibers_may_yield_internal_with_reason(fiber_yield_reason_t reason)
375 {
376 return fibers_may_yield_with_prob_and_reason(FIBERS_INTERNAL_YIELD_PROB, reason);
377 }
378
379 bool
fibers_may_yield(void)380 fibers_may_yield(void)
381 {
382 return fibers_may_yield_with_prob(fibers_may_yield_probability);
383 }
384
385 bool
fibers_may_yield_with_prob(uint64_t probability)386 fibers_may_yield_with_prob(uint64_t probability)
387 {
388 return fibers_may_yield_with_prob_and_reason(probability, FIBERS_YIELD_REASON_UNKNOWN);
389 }
390
391 bool
fibers_may_yield_with_reason(fiber_yield_reason_t reason)392 fibers_may_yield_with_reason(fiber_yield_reason_t reason)
393 {
394 return fibers_may_yield_with_prob_and_reason(fibers_may_yield_probability, reason);
395 }
396
397 bool
fibers_may_yield_with_prob_and_reason(uint64_t probability,fiber_yield_reason_t reason)398 fibers_may_yield_with_prob_and_reason(uint64_t probability, fiber_yield_reason_t reason)
399 {
400 if (fibers_current->may_yield_disabled) {
401 return false;
402 }
403
404 if (fibers_scheduler->fibers_should_yield(fibers_scheduler_context, probability, reason)) {
405 fibers_queue_push(&fibers_run_queue, fibers_current);
406 fibers_choose_next(FIBER_STOP);
407 return true;
408 }
409
410 return false;
411 }
412