Debian Codegraph @

src/kj/async.c++

raw
1 // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
2 // Licensed under the MIT License:
3 //
4 // Permission is hereby granted, free of charge, to any person obtaining a copy
5 // of this software and associated documentation files (the "Software"), to deal
6 // in the Software without restriction, including without limitation the rights
7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 // copies of the Software, and to permit persons to whom the Software is
9 // furnished to do so, subject to the following conditions:
10 //
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
13 //
14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 // THE SOFTWARE.
21
22 #undef _FORTIFY_SOURCE
23 // If _FORTIFY_SOURCE is defined, longjmp will complain when it detects the stack
24 // pointer moving in the "wrong direction", thinking you're jumping to a non-existent
25 // stack frame. But we use longjmp to jump between different stacks to implement fibers,
26 // so this check isn't appropriate for us.
27
28 #if _WIN32 || __CYGWIN__
29 #include <kj/win32-api-version.h>
30 #elif __APPLE__
31 // getcontext() and friends are marked deprecated on MacOS but seemingly no replacement is
32 // provided. It appears as if they deprecated it solely because the standards bodies deprecated it,
33 // which they seemingly did mainly because the proper semantics are too difficult for them to
34 // define. I doubt MacOS would actually remove these functions as they are widely used. But if they
35 // do, then I guess we'll need to fall back to using setjmp()/longjmp(), and some sort of hack
36 // involving sigaltstack() (and generating a fake signal I guess) in order to initialize the fiber
37 // in the first place. Or we could use assembly, I suppose. Either way, ick.
38 #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
39 #define _XOPEN_SOURCE // Must be defined to see getcontext() on MacOS.
40 #endif
41
42 #include "async.h"
43 #include "debug.h"
44 #include "vector.h"
45 #include "threadlocal.h"
46 #include "mutex.h"
47 #include "one-of.h"
48 #include "function.h"
49 #include "list.h"
50 #include <deque>
51 #include <atomic>
52
53 #if _WIN32 || __CYGWIN__
54 #include <windows.h> // for Sleep(0) and fibers
55 #include <kj/windows-sanity.h>
56 #else
57
58 #if KJ_USE_FIBERS
59 #include <ucontext.h>
60 #include <setjmp.h> // for fibers
61 #endif
62
63 #include <sys/mman.h> // mmap(), for allocating new stacks
64 #include <unistd.h> // sysconf()
65 #include <errno.h>
66 #endif
67
68 #if !_WIN32
69 #include <sched.h> // just for sched_yield()
70 #endif
71
72 #if !KJ_NO_RTTI
73 #include <typeinfo>
74 #if __GNUC__
75 #include <cxxabi.h>
76 #endif
77 #endif
78
79 #include <stdlib.h>
80
81 #if KJ_HAS_COMPILER_FEATURE(address_sanitizer)
82 // Clang's address sanitizer requires special hints when switching fibers, especially in order for
83 // stack-use-after-return handling to work right.
84 //
85 // TODO(someday): Does GCC's sanitizer, flagged by __SANITIZE_ADDRESS__, have these hints too? I
86 // don't know and am not in a position to test, so I'm assuming not for now.
87 #include <sanitizer/common_interface_defs.h>
88 #else
89 // Nop the hints so that we don't have to put #ifdefs around every use.
90 #define __sanitizer_start_switch_fiber(...)
91 #define __sanitizer_finish_switch_fiber(...)
92 #endif
93
94 #if _MSC_VER && !__clang__
95 // MSVC's atomic intrinsics are weird and different, whereas the C++ standard atomics match the GCC
96 // builtins -- except for requiring the obnoxious std::atomic<T> wrapper. So, on MSVC let's just
97 // #define the builtins based on the C++ library, reinterpret-casting native types to
98 // std::atomic... this is cheating but ugh, whatever.
99 template <typename T>
100 static std::atomic<T>* reinterpretAtomic(T* ptr) { return reinterpret_cast<std::atomic<T>*>(ptr); }
101 #define __atomic_store_n(ptr, val, order) \
102 std::atomic_store_explicit(reinterpretAtomic(ptr), val, order)
103 #define __atomic_load_n(ptr, order) \
104 std::atomic_load_explicit(reinterpretAtomic(ptr), order)
105 #define __atomic_compare_exchange_n(ptr, expected, desired, weak, succ, fail) \
106 std::atomic_compare_exchange_strong_explicit( \
107 reinterpretAtomic(ptr), expected, desired, succ, fail)
108 #define __atomic_exchange_n(ptr, val, order) \
109 std::atomic_exchange_explicit(reinterpretAtomic(ptr), val, order)
110 #define __ATOMIC_RELAXED std::memory_order_relaxed
111 #define __ATOMIC_ACQUIRE std::memory_order_acquire
112 #define __ATOMIC_RELEASE std::memory_order_release
113 #endif
114
115 namespace kj {
116
117 namespace {
118
119 KJ_THREADLOCAL_PTR(DisallowAsyncDestructorsScope) disallowAsyncDestructorsScope = nullptr;
120
121 } // namespace
122
123 AsyncObject::~AsyncObject() {
124 if (disallowAsyncDestructorsScope != nullptr) {
125 // If we try to do the KJ_FAIL_REQUIRE here (declaring `~AsyncObject()` itself to be noexcept),
126 // it seems to have a non-negligible performance impact in the HTTP benchmark. My guess is that
127 // it's because it breaks inlining of `~AsyncObject()` into various subclass destructors that
128 // are defined inside this file, which are some of the biggest ones. By forcing the actual
129 // failure code out into a separate function we get a little performance boost.
130 failed();
131 }
132 }
133
134 void AsyncObject::failed() noexcept {
135 // Since the method is noexcept, this will abort the process.
136 KJ_FAIL_REQUIRE(
137 kj::str("KJ async object being destroyed when not allowed: ",
138 disallowAsyncDestructorsScope->reason));
139 }
140
141 DisallowAsyncDestructorsScope::DisallowAsyncDestructorsScope(kj::StringPtr reason)
142 : reason(reason), previousValue(disallowAsyncDestructorsScope) {
143 requireOnStack(this, "DisallowAsyncDestructorsScope must be allocated on the stack.");
144 disallowAsyncDestructorsScope = this;
145 }
146
147 DisallowAsyncDestructorsScope::~DisallowAsyncDestructorsScope() {
148 disallowAsyncDestructorsScope = previousValue;
149 }
150
151 AllowAsyncDestructorsScope::AllowAsyncDestructorsScope()
152 : previousValue(disallowAsyncDestructorsScope) {
153 requireOnStack(this, "AllowAsyncDestructorsScope must be allocated on the stack.");
154 disallowAsyncDestructorsScope = nullptr;
155 }
156 AllowAsyncDestructorsScope::~AllowAsyncDestructorsScope() {
157 disallowAsyncDestructorsScope = previousValue;
158 }
159
160 // =======================================================================================
161
162 namespace {
163
164 KJ_THREADLOCAL_PTR(EventLoop) threadLocalEventLoop = nullptr;
165
166 #define _kJ_ALREADY_READY reinterpret_cast< ::kj::_::Event*>(1)
167
168 EventLoop& currentEventLoop() {
169 EventLoop* loop = threadLocalEventLoop;
170 KJ_REQUIRE(loop != nullptr, "No event loop is running on this thread.");
171 return *loop;
172 }
173
174 class RootEvent: public _::Event {
175 public:
176 RootEvent(_::PromiseNode* node, void* traceAddr, SourceLocation location)
177 : Event(location), node(node), traceAddr(traceAddr) {}
178
179 bool fired = false;
180
181 Maybe<Own<_::Event>> fire() override {
182 fired = true;
183 return nullptr;
184 }
185
186 void traceEvent(_::TraceBuilder& builder) override {
187 node->tracePromise(builder, true);
188 builder.add(traceAddr);
189 }
190
191 private:
192 _::PromiseNode* node;
193 void* traceAddr;
194 };
195
196 struct DummyFunctor {
197 void operator()() {};
198 };
199
200 } // namespace
201
202 // =======================================================================================
203
204 void END_CANCELER_STACK_START_CANCELEE_STACK() {}
205 // Dummy symbol used when reporting how a Canceler was canceled. We end up combining two stack
206 // traces into one and we use this as a separator.
207
208 Canceler::~Canceler() noexcept(false) {
209 if (isEmpty()) return;
210 cancel(getDestructionReason(
211 reinterpret_cast<void*>(&END_CANCELER_STACK_START_CANCELEE_STACK),
212 Exception::Type::DISCONNECTED, __FILE__, __LINE__, "operation canceled"_kj));
213 }
214
215 void Canceler::cancel(StringPtr cancelReason) {
216 if (isEmpty()) return;
217 // We can't use getDestructionReason() here because if an exception is in-flight, it would use
218 // that exception, totally discarding the reason given by the caller. This would probably be
219 // unexpected. The caller can always use getDestructionReason() themselves if desired.
220 cancel(Exception(Exception::Type::DISCONNECTED, __FILE__, __LINE__, kj::str(cancelReason)));
221 }
222
223 void Canceler::cancel(const Exception& exception) {
224 for (;;) {
225 KJ_IF_MAYBE(a, list) {
226 a->unlink();
227 a->cancel(kj::cp(exception));
228 } else {
229 break;
230 }
231 }
232 }
233
234 void Canceler::release() {
235 for (;;) {
236 KJ_IF_MAYBE(a, list) {
237 a->unlink();
238 } else {
239 break;
240 }
241 }
242 }
243
244 Canceler::AdapterBase::AdapterBase(Canceler& canceler)
245 : prev(canceler.list),
246 next(canceler.list) {
247 canceler.list = *this;
248 KJ_IF_MAYBE(n, next) {
249 n->prev = next;
250 }
251 }
252
253 Canceler::AdapterBase::~AdapterBase() noexcept(false) {
254 unlink();
255 }
256
257 void Canceler::AdapterBase::unlink() {
258 KJ_IF_MAYBE(p, prev) {
259 *p = next;
260 }
261 KJ_IF_MAYBE(n, next) {
262 n->prev = prev;
263 }
264 next = nullptr;
265 prev = nullptr;
266 }
267
268 Canceler::AdapterImpl<void>::AdapterImpl(kj::PromiseFulfiller<void>& fulfiller,
269 Canceler& canceler, kj::Promise<void> inner)
270 : AdapterBase(canceler),
271 fulfiller(fulfiller),
272 inner(inner.then(
273 [&fulfiller]() { fulfiller.fulfill(); },
274 [&fulfiller](kj::Exception&& e) { fulfiller.reject(kj::mv(e)); })
275 .eagerlyEvaluate(nullptr)) {}
276
277 void Canceler::AdapterImpl<void>::cancel(kj::Exception&& e) {
278 fulfiller.reject(kj::mv(e));
279 inner = nullptr;
280 }
281
282 // =======================================================================================
283
284 TaskSet::TaskSet(TaskSet::ErrorHandler& errorHandler, SourceLocation location)
285 : errorHandler(errorHandler), location(location) {}
286
287 class TaskSet::Task final: public _::PromiseArenaMember, public _::Event {
288 public:
289 Task(_::OwnPromiseNode&& nodeParam, TaskSet& taskSet)
290 : Event(taskSet.location), taskSet(taskSet), node(kj::mv(nodeParam)) {
291 node->setSelfPointer(&node);
292 node->onReady(this);
293 }
294
295 void destroy() override { freePromise(this); }
296
297 OwnTask pop() {
298 KJ_IF_MAYBE(n, next) { n->get()->prev = prev; }
299 OwnTask self = kj::mv(KJ_ASSERT_NONNULL(*prev));
300 KJ_ASSERT(self.get() == this);
301 *prev = kj::mv(next);
302 next = nullptr;
303 prev = nullptr;
304 return self;
305 }
306
307 Maybe<OwnTask> next;
308 Maybe<OwnTask>* prev = nullptr;
309
310 kj::String trace() {
311 void* space[32];
312 _::TraceBuilder builder(space);
313 node->tracePromise(builder, false);
314 return kj::str("task: ", builder);
315 }
316
317 protected:
318 Maybe<Own<Event>> fire() override {
319 // Get the result.
320 _::ExceptionOr<_::Void> result;
321 node->get(result);
322
323 // Delete the node, catching any exceptions.
324 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([this]() {
325 node = nullptr;
326 })) {
327 result.addException(kj::mv(*exception));
328 }
329
330 // Remove from the task list. Do this before calling taskFailed(), so that taskFailed() can
331 // safely call clear().
332 auto self = pop();
333
334 // We'll also process onEmpty() now, just in case `taskFailed()` actually destroys the whole
335 // `TaskSet`.
336 KJ_IF_MAYBE(f, taskSet.emptyFulfiller) {
337 if (taskSet.tasks == nullptr) {
338 f->get()->fulfill();
339 taskSet.emptyFulfiller = nullptr;
340 }
341 }
342
343 // Call the error handler if there was an exception.
344 KJ_IF_MAYBE(e, result.exception) {
345 taskSet.errorHandler.taskFailed(kj::mv(*e));
346 }
347
348 return Own<Event>(mv(self));
349 }
350
351 void traceEvent(_::TraceBuilder& builder) override {
352 // Pointing out the ErrorHandler's taskFailed() implementation will usually identify the
353 // particular TaskSet that contains this event.
354 builder.add(_::getMethodStartAddress(taskSet.errorHandler, &ErrorHandler::taskFailed));
355 }
356
357 private:
358 TaskSet& taskSet;
359 _::OwnPromiseNode node;
360 };
361
362 TaskSet::~TaskSet() noexcept(false) {
363 // You could argue it is dubious, but some applications would like for the destructor of a
364 // task to be able to schedule new tasks. So when we cancel our tasks... we might find new
365 // tasks added! We'll have to repeatedly cancel. Additionally, we need to make sure that we destroy
366 // the items in a loop to prevent any issues with stack overflow.
367 while (tasks != nullptr) {
368 auto removed = KJ_REQUIRE_NONNULL(tasks)->pop();
369 }
370 }
371
372 void TaskSet::add(Promise<void>&& promise) {
373 auto task = _::appendPromise<Task>(_::PromiseNode::from(kj::mv(promise)), *this);
374 KJ_IF_MAYBE(head, tasks) {
375 head->get()->prev = &task->next;
376 task->next = kj::mv(tasks);
377 }
378 task->prev = &tasks;
379 tasks = kj::mv(task);
380 }
381
382 kj::String TaskSet::trace() {
383 kj::Vector<kj::String> traces;
384
385 Maybe<OwnTask>* ptr = &tasks;
386 for (;;) {
387 KJ_IF_MAYBE(task, *ptr) {
388 traces.add(task->get()->trace());
389 ptr = &task->get()->next;
390 } else {
391 break;
392 }
393 }
394
395 return kj::strArray(traces, "\n");
396 }
397
398 Promise<void> TaskSet::onEmpty() {
399 KJ_IF_MAYBE(fulfiller, emptyFulfiller) {
400 if (fulfiller->get()->isWaiting()) {
401 KJ_FAIL_REQUIRE("onEmpty() can only be called once at a time");
402 }
403 }
404
405 if (tasks == nullptr) {
406 return READY_NOW;
407 } else {
408 auto paf = newPromiseAndFulfiller<void>();
409 emptyFulfiller = kj::mv(paf.fulfiller);
410 return kj::mv(paf.promise);
411 }
412 }
413
414 void TaskSet::clear() {
415 tasks = nullptr;
416
417 KJ_IF_MAYBE(fulfiller, emptyFulfiller) {
418 fulfiller->get()->fulfill();
419 }
420 }
421
422 // =======================================================================================
423
424 namespace {
425
426 #if _WIN32 || __CYGWIN__
427 thread_local void* threadMainFiber = nullptr;
428
429 void* getMainWin32Fiber() {
430 return threadMainFiber;
431 }
432 #endif
433
434 inline void ensureThreadCanRunFibers() {
435 #if _WIN32 || __CYGWIN__
436 // Make sure the current thread has been converted to a fiber.
437 void* fiber = threadMainFiber;
438 if (fiber == nullptr) {
439 // Thread not initialized. Convert it to a fiber now.
440 // Note: Unfortunately, if the application has already converted the thread to a fiber, I
441 // guess this will fail. But trying to call GetCurrentFiber() when the thread isn't a fiber
442 // doesn't work (it returns null on WINE but not on real windows, ugh). So I guess we're
443 // just incompatible with the application doing anything with fibers, which is sad.
444 threadMainFiber = fiber = ConvertThreadToFiber(nullptr);
445 }
446 #endif
447 }
448
449 } // namespace
450
451 namespace _ {
452
453 class FiberStack final {
454 // A class containing a fiber stack impl. This is separate from fiber
455 // promises since it lets us move the stack itself around and reuse it.
456
457 public:
458 FiberStack(size_t stackSize);
459 ~FiberStack() noexcept(false);
460
461 struct SynchronousFunc {
462 kj::FunctionParam<void()>& func;
463 kj::Maybe<kj::Exception> exception;
464 };
465
466 void initialize(FiberBase& fiber);
467 void initialize(SynchronousFunc& syncFunc);
468
469 void reset() {
470 main = {};
471 }
472
473 void switchToFiber();
474 void switchToMain();
475
476 void trace(TraceBuilder& builder) {
477 // TODO(someday): Trace through fiber stack? Can it be done???
478 builder.add(getMethodStartAddress(*this, &FiberStack::trace));
479 }
480
481 private:
482 size_t stackSize;
483 OneOf<FiberBase*, SynchronousFunc*> main;
484
485 friend class FiberBase;
486 friend class FiberPool::Impl;
487
488 struct StartRoutine;
489
490 #if KJ_USE_FIBERS
491 #if _WIN32 || __CYGWIN__
492 void* osFiber;
493 #else
494 struct Impl;
495 Impl* impl;
496 #endif
497 #endif
498
499 [[noreturn]] void run();
500
501 bool isReset() { return main == nullptr; }
502 };
503
504 } // namespace _
505
506 #if __linux__
507 // TODO(someday): Support core-local freelists on OSs other than Linux. The only tricky part is
508 // finding what to use instead of sched_getcpu() to get the current CPU ID.
509 #define USE_CORE_LOCAL_FREELISTS 1
510 #endif
511
512 #if USE_CORE_LOCAL_FREELISTS
513 static const size_t CACHE_LINE_SIZE = 64;
514 // Most modern architectures have 64-byte cache lines.
515 #endif
516
517 class FiberPool::Impl final: private Disposer {
518 public:
519 Impl(size_t stackSize): stackSize(stackSize) {}
520 ~Impl() noexcept(false) {
521 #if USE_CORE_LOCAL_FREELISTS
522 if (coreLocalFreelists != nullptr) {
523 KJ_DEFER(free(coreLocalFreelists));
524
525 for (uint i: kj::zeroTo(nproc)) {
526 for (auto stack: coreLocalFreelists[i].stacks) {
527 if (stack != nullptr) {
528 delete stack;
529 }
530 }
531 }
532 }
533 #endif
534
535 // Make sure we're not leaking anything from the global freelist either.
536 auto lock = freelist.lockExclusive();
537 auto dangling = kj::mv(*lock);
538 for (auto& stack: dangling) {
539 delete stack;
540 }
541 }
542
543 void setMaxFreelist(size_t count) {
544 maxFreelist = count;
545 }
546
547 size_t getFreelistSize() const {
548 return freelist.lockShared()->size();
549 }
550
551 void useCoreLocalFreelists() {
552 #if USE_CORE_LOCAL_FREELISTS
553 if (coreLocalFreelists != nullptr) {
554 // Ignore repeat call.
555 return;
556 }
557
558 int nproc_;
559 KJ_SYSCALL(nproc_ = sysconf(_SC_NPROCESSORS_CONF));
560 nproc = nproc_;
561
562 void* allocPtr;
563 size_t totalSize = nproc * sizeof(CoreLocalFreelist);
564 int error = posix_memalign(&allocPtr, CACHE_LINE_SIZE, totalSize);
565 if (error != 0) {
566 KJ_FAIL_SYSCALL("posix_memalign", error);
567 }
568 memset(allocPtr, 0, totalSize);
569 coreLocalFreelists = reinterpret_cast<CoreLocalFreelist*>(allocPtr);
570 #endif
571 }
572
573 Own<_::FiberStack> takeStack() const {
574 // Get a stack from the pool. The disposer on the returned Own pointer will return the stack
575 // to the pool, provided that reset() has been called to indicate that the stack is not in
576 // a weird state.
577
578 #if USE_CORE_LOCAL_FREELISTS
579 KJ_IF_MAYBE(core, lookupCoreLocalFreelist()) {
580 for (auto& stackPtr: core->stacks) {
581 _::FiberStack* result = __atomic_exchange_n(&stackPtr, nullptr, __ATOMIC_ACQUIRE);
582 if (result != nullptr) {
583 // Found a stack in this slot!
584 return { result, *this };
585 }
586 }
587 // No stacks found, fall back to global freelist.
588 }
589 #endif
590
591 {
592 auto lock = freelist.lockExclusive();
593 if (!lock->empty()) {
594 _::FiberStack* result = lock->back();
595 lock->pop_back();
596 return { result, *this };
597 }
598 }
599
600 _::FiberStack* result = new _::FiberStack(stackSize);
601 return { result, *this };
602 }
603
604 private:
605 size_t stackSize;
606 size_t maxFreelist = kj::maxValue;
607 MutexGuarded<std::deque<_::FiberStack*>> freelist;
608
609 #if USE_CORE_LOCAL_FREELISTS
610 struct CoreLocalFreelist {
611 union {
612 _::FiberStack* stacks[2];
613 // For now, we don't try to freelist more than 2 stacks per core. If you have three or more
614 // threads interleaved on a core, chances are you have bigger problems...
615
616 byte padToCacheLine[CACHE_LINE_SIZE];
617 // We don't want two core-local freelists to live in the same cache line, otherwise the
618 // cores will fight over ownership of that line.
619 };
620 };
621
622 uint nproc;
623 CoreLocalFreelist* coreLocalFreelists = nullptr;
624
625 kj::Maybe<CoreLocalFreelist&> lookupCoreLocalFreelist() const {
626 if (coreLocalFreelists == nullptr) {
627 return nullptr;
628 } else {
629 int cpu = sched_getcpu();
630 if (cpu >= 0) {
631 // TODO(perf): Perhaps two hyperthreads on the same physical core should share a freelist?
632 // But I don't know how to find out if the system uses hyperthreading.
633 return coreLocalFreelists[cpu];
634 } else {
635 static bool logged = false;
636 if (!logged) {
637 KJ_LOG(ERROR, "invalid cpu number from sched_getcpu()?", cpu, nproc);
638 logged = true;
639 }
640 return nullptr;
641 }
642 }
643 }
644 #endif
645
646 void disposeImpl(void* pointer) const {
647 _::FiberStack* stack = reinterpret_cast<_::FiberStack*>(pointer);
648 KJ_DEFER(delete stack);
649
650 // Verify that the stack was reset before returning, otherwise it might be in a weird state
651 // where we don't want to reuse it.
652 if (stack->isReset()) {
653 #if USE_CORE_LOCAL_FREELISTS
654 KJ_IF_MAYBE(core, lookupCoreLocalFreelist()) {
655 for (auto& stackPtr: core->stacks) {
656 stack = __atomic_exchange_n(&stackPtr, stack, __ATOMIC_RELEASE);
657 if (stack == nullptr) {
658 // Cool, we inserted the stack into an unused slot. We're done.
659 return;
660 }
661 }
662 // All slots were occupied, so we inserted the new stack in the front, pushed the rest back,
663 // and now `stack` refers to the stack that fell off the end of the core-local list. That
664 // needs to go into the global freelist.
665 }
666 #endif
667
668 auto lock = freelist.lockExclusive();
669 lock->push_back(stack);
670 if (lock->size() > maxFreelist) {
671 stack = lock->front();
672 lock->pop_front();
673 } else {
674 stack = nullptr;
675 }
676 }
677 }
678 };
679
680 FiberPool::FiberPool(size_t stackSize) : impl(kj::heap<FiberPool::Impl>(stackSize)) {}
681 FiberPool::~FiberPool() noexcept(false) {}
682
683 void FiberPool::setMaxFreelist(size_t count) {
684 impl->setMaxFreelist(count);
685 }
686
687 size_t FiberPool::getFreelistSize() const {
688 return impl->getFreelistSize();
689 }
690
691 void FiberPool::useCoreLocalFreelists() {
692 impl->useCoreLocalFreelists();
693 }
694
695 void FiberPool::runSynchronously(kj::FunctionParam<void()> func) const {
696 ensureThreadCanRunFibers();
697
698 _::FiberStack::SynchronousFunc syncFunc { func, nullptr };
699
700 {
701 auto stack = impl->takeStack();
702 stack->initialize(syncFunc);
703 stack->switchToFiber();
704 stack->reset(); // safe to reuse
705 }
706
707 KJ_IF_MAYBE(e, syncFunc.exception) {
708 kj::throwRecoverableException(kj::mv(*e));
709 }
710 }
711
712 namespace _ { // private
713
714 class LoggingErrorHandler: public TaskSet::ErrorHandler {
715 public:
716 static LoggingErrorHandler instance;
717
718 void taskFailed(kj::Exception&& exception) override {
719 KJ_LOG(ERROR, "Uncaught exception in daemonized task.", exception);
720 }
721 };
722
723 LoggingErrorHandler LoggingErrorHandler::instance = LoggingErrorHandler();
724
725 } // namespace _ (private)
726
727 // =======================================================================================
728
729 struct Executor::Impl {
730 Impl(EventLoop& loop): state(loop) {}
731
732 struct State {
733 // Queues of notifications from other threads that need this thread's attention.
734
735 State(EventLoop& loop): loop(loop) {}
736
737 kj::Maybe<EventLoop&> loop;
738 // Becomes null when the loop is destroyed.
739
740 List<_::XThreadEvent, &_::XThreadEvent::targetLink> start;
741 List<_::XThreadEvent, &_::XThreadEvent::targetLink> cancel;
742 List<_::XThreadEvent, &_::XThreadEvent::replyLink> replies;
743 // Lists of events that need actioning by this thread.
744
745 List<_::XThreadEvent, &_::XThreadEvent::targetLink> executing;
746 // Events that have already been dispatched and are happily executing. This list is maintained
747 // so that they can be canceled if the event loop exits.
748
749 List<_::XThreadPaf, &_::XThreadPaf::link> fulfilled;
750 // Set of XThreadPafs that have been fulfilled by another thread.
751
752 bool waitingForCancel = false;
753 // True if this thread is currently blocked waiting for some other thread to pump its
754 // cancellation queue. If that other thread tries to block on *this* thread, then it could
755 // deadlock -- it must take precautions against this.
756
757 bool isDispatchNeeded() const {
758 return !start.empty() || !cancel.empty() || !replies.empty() || !fulfilled.empty();
759 }
760
761 void dispatchAll(Vector<_::XThreadEvent*>& eventsToCancelOutsideLock) {
762 for (auto& event: start) {
763 start.remove(event);
764 executing.add(event);
765 event.state = _::XThreadEvent::EXECUTING;
766 event.armBreadthFirst();
767 }
768
769 dispatchCancels(eventsToCancelOutsideLock);
770
771 for (auto& event: replies) {
772 replies.remove(event);
773 event.onReadyEvent.armBreadthFirst();
774 }
775
776 for (auto& event: fulfilled) {
777 fulfilled.remove(event);
778 event.state = _::XThreadPaf::DISPATCHED;
779 event.onReadyEvent.armBreadthFirst();
780 }
781 }
782
783 void dispatchCancels(Vector<_::XThreadEvent*>& eventsToCancelOutsideLock) {
784 for (auto& event: cancel) {
785 cancel.remove(event);
786
787 if (event.promiseNode == nullptr) {
788 event.setDoneState();
789 } else {
790 // We can't destroy the promiseNode while the mutex is locked, because we don't know
791 // what the destructor might do. But, we *must* destroy it before acknowledging
792 // cancellation. So we have to add it to a list to destroy later.
793 eventsToCancelOutsideLock.add(&event);
794 }
795 }
796 }
797 };
798
799 kj::MutexGuarded<State> state;
800 // After modifying state from another thread, the loop's port.wake() must be called.
801
802 void processAsyncCancellations(Vector<_::XThreadEvent*>& eventsToCancelOutsideLock) {
803 // After calling dispatchAll() or dispatchCancels() with the lock held, it may be that some
804 // cancellations require dropping the lock before destroying the promiseNode. In that case
805 // those cancellations will be added to the eventsToCancelOutsideLock Vector passed to the
806 // method. That vector must then be passed to processAsyncCancellations() as soon as the lock
807 // is released.
808
809 for (auto& event: eventsToCancelOutsideLock) {
810 event->promiseNode = nullptr;
811 event->disarm();
812 }
813
814 // Now we need to mark all the events "done" under lock.
815 auto lock = state.lockExclusive();
816 for (auto& event: eventsToCancelOutsideLock) {
817 event->setDoneState();
818 }
819 }
820
821 void disconnect() {
822 state.lockExclusive()->loop = nullptr;
823
824 // Now that `loop` is set null in `state`, other threads will no longer try to manipulate our
825 // lists, so we can access them without a lock. That's convenient because a bunch of the things
826 // we want to do with them would require dropping the lock to avoid deadlocks. We'd end up
827 // copying all the lists over into separate vectors first, dropping the lock, operating on
828 // them, and then locking again.
829 auto& s = state.getWithoutLock();
830
831 // We do, however, take and release the lock on the way out, to make sure anyone performing
832 // a conditional wait for state changes gets a chance to have their wait condition re-checked.
833 KJ_DEFER(state.lockExclusive());
834
835 for (auto& event: s.start) {
836 KJ_ASSERT(event.state == _::XThreadEvent::QUEUED, event.state) { break; }
837 s.start.remove(event);
838 event.setDisconnected();
839 event.sendReply();
840 event.setDoneState();
841 }
842
843 for (auto& event: s.executing) {
844 KJ_ASSERT(event.state == _::XThreadEvent::EXECUTING, event.state) { break; }
845 s.executing.remove(event);
846 event.promiseNode = nullptr;
847 event.setDisconnected();
848 event.sendReply();
849 event.setDoneState();
850 }
851
852 for (auto& event: s.cancel) {
853 KJ_ASSERT(event.state == _::XThreadEvent::CANCELING, event.state) { break; }
854 s.cancel.remove(event);
855 event.promiseNode = nullptr;
856 event.setDoneState();
857 }
858
859 // The replies list "should" be empty, because any locally-initiated tasks should have been
860 // canceled before destroying the EventLoop.
861 if (!s.replies.empty()) {
862 KJ_LOG(ERROR, "EventLoop destroyed with cross-thread event replies outstanding");
863 for (auto& event: s.replies) {
864 s.replies.remove(event);
865 }
866 }
867
868 // Similarly for cross-thread fulfillers. The waiting tasks should have been canceled.
869 if (!s.fulfilled.empty()) {
870 KJ_LOG(ERROR, "EventLoop destroyed with cross-thread fulfiller replies outstanding");
871 for (auto& event: s.fulfilled) {
872 s.fulfilled.remove(event);
873 event.state = _::XThreadPaf::DISPATCHED;
874 }
875 }
876 }};
877
878 namespace _ { // (private)
879
880 XThreadEvent::XThreadEvent(
881 ExceptionOrValue& result, const Executor& targetExecutor, EventLoop& loop,
882 void* funcTracePtr, SourceLocation location)
883 : Event(loop, location), result(result), funcTracePtr(funcTracePtr),
884 targetExecutor(targetExecutor.addRef()) {}
885
886 void XThreadEvent::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
887 // We can't safely trace into another thread, so we'll stop here.
888 builder.add(funcTracePtr);
889 }
890
891 void XThreadEvent::ensureDoneOrCanceled() {
892 if (__atomic_load_n(&state, __ATOMIC_ACQUIRE) != DONE) {
893 auto lock = targetExecutor->impl->state.lockExclusive();
894
895 const EventLoop* loop;
896 KJ_IF_MAYBE(l, lock->loop) {
897 loop = l;
898 } else {
899 // Target event loop is already dead, so we know it's already working on transitioning all
900 // events to the DONE state. We can just wait.
901 lock.wait([&](auto&) { return state == DONE; });
902 return;
903 }
904
905 switch (state) {
906 case UNUSED:
907 // Nothing to do.
908 break;
909 case QUEUED:
910 lock->start.remove(*this);
911 // No wake needed since we removed work rather than adding it.
912 state = DONE;
913 break;
914 case EXECUTING: {
915 lock->executing.remove(*this);
916 lock->cancel.add(*this);
917 state = CANCELING;
918 KJ_IF_MAYBE(p, loop->port) {
919 p->wake();
920 }
921
922 Maybe<Executor&> maybeSelfExecutor = nullptr;
923 if (threadLocalEventLoop != nullptr) {
924 KJ_IF_MAYBE(e, threadLocalEventLoop->executor) {
925 maybeSelfExecutor = **e;
926 }
927 }
928
929 KJ_IF_MAYBE(selfExecutor, maybeSelfExecutor) {
930 // If, while waiting for other threads to process our cancellation request, we have
931 // cancellation requests queued back to this thread, we must process them. Otherwise,
932 // we could deadlock with two threads waiting on each other to process cancellations.
933 //
934 // We don't have a terribly good way to detect this, except to check if the remote
935 // thread is itself waiting for cancellations and, if so, wake ourselves up to check for
936 // cancellations to process. This will busy-loop but at least it should eventually
937 // resolve assuming fair scheduling.
938 //
939 // To make things extra-annoying, in order to update our waitingForCancel flag, we have
940 // to lock our own executor state, but we can't take both locks at once, so we have to
941 // release the other lock in the meantime.
942
943 // Make sure we unset waitingForCancel on the way out.
944 KJ_DEFER({
945 lock = {};
946
947 Vector<_::XThreadEvent*> eventsToCancelOutsideLock;
948 KJ_DEFER(selfExecutor->impl->processAsyncCancellations(eventsToCancelOutsideLock));
949
950 auto selfLock = selfExecutor->impl->state.lockExclusive();
951 selfLock->waitingForCancel = false;
952 selfLock->dispatchCancels(eventsToCancelOutsideLock);
953
954 // We don't need to re-take the lock on the other executor here; it's not used again
955 // after this scope.
956 });
957
958 while (state != DONE) {
959 bool otherThreadIsWaiting = lock->waitingForCancel;
960
961 // Make sure our waitingForCancel is on and dispatch any pending cancellations on this
962 // thread.
963 lock = {};
964 {
965 Vector<_::XThreadEvent*> eventsToCancelOutsideLock;
966 KJ_DEFER(selfExecutor->impl->processAsyncCancellations(eventsToCancelOutsideLock));
967
968 auto selfLock = selfExecutor->impl->state.lockExclusive();
969 selfLock->waitingForCancel = true;
970
971 // Note that we don't have to proactively delete the PromiseNodes extracted from
972 // the canceled events because those nodes belong to this thread and can't possibly
973 // continue executing while we're blocked here.
974 selfLock->dispatchCancels(eventsToCancelOutsideLock);
975 }
976
977 if (otherThreadIsWaiting) {
978 // We know the other thread was waiting for cancellations to complete a moment ago.
979 // We may have just processed the necessary cancellations in this thread, in which
980 // case the other thread needs a chance to receive control and notice this. Or, it
981 // may be that the other thread is waiting for some third thread to take action.
982 // Either way, we should yield control here to give things a chance to settle.
983 // Otherwise we could end up in a tight busy loop.
984 #if _WIN32
985 Sleep(0);
986 #else
987 sched_yield();
988 #endif
989 }
990
991 // OK now we can take the original lock again.
992 lock = targetExecutor->impl->state.lockExclusive();
993
994 // OK, now we can wait for the other thread to either process our cancellation or
995 // indicate that it is waiting for remote cancellation.
996 lock.wait([&](const Executor::Impl::State& executorState) {
997 return state == DONE || executorState.waitingForCancel;
998 });
999 }
1000 } else {
1001 // We have no executor of our own so we don't have to worry about cancellation cycles
1002 // causing deadlock.
1003 //
1004 // NOTE: I don't think we can actually get here, because it implies that this is a
1005 // synchronous execution, which means there's no way to cancel it.
1006 lock.wait([&](auto&) { return state == DONE; });
1007 }
1008 KJ_DASSERT(!targetLink.isLinked());
1009 break;
1010 }
1011 case CANCELING:
1012 KJ_FAIL_ASSERT("impossible state: CANCELING should only be set within the above case");
1013 case DONE:
1014 // Became done while we waited for lock. Nothing to do.
1015 break;
1016 }
1017 }
1018
1019 KJ_IF_MAYBE(e, replyExecutor) {
1020 // Since we know we reached the DONE state (or never left UNUSED), we know that the remote
1021 // thread is all done playing with our `replyPrev` pointer. Only the current thread could
1022 // possibly modify it after this point. So we can skip the lock if it's already null.
1023 if (replyLink.isLinked()) {
1024 auto lock = e->impl->state.lockExclusive();
1025 lock->replies.remove(*this);
1026 }
1027 }
1028 }
1029
1030 void XThreadEvent::sendReply() {
1031 KJ_IF_MAYBE(e, replyExecutor) {
1032 // Queue the reply.
1033 const EventLoop* replyLoop;
1034 {
1035 auto lock = e->impl->state.lockExclusive();
1036 KJ_IF_MAYBE(l, lock->loop) {
1037 lock->replies.add(*this);
1038 replyLoop = l;
1039 } else {
1040 // Calling thread exited without cancelling the promise. This is UB. In fact,
1041 // `replyExecutor` is probably already destroyed and we are in use-after-free territory
1042 // already. Better abort.
1043 KJ_LOG(FATAL,
1044 "the thread which called kj::Executor::executeAsync() apparently exited its own "
1045 "event loop without canceling the cross-thread promise first; this is undefined "
1046 "behavior so I will crash now");
1047 abort();
1048 }
1049 }
1050
1051 // Note that it's safe to assume `replyLoop` still exists even though we dropped the lock
1052 // because that thread would have had to cancel any promises before destroying its own
1053 // EventLoop, and when it tries to destroy this promise, it will wait for `state` to become
1054 // `DONE`, which we don't set until later on. That's nice because wake() probably makes a
1055 // syscall and we'd rather not hold the lock through syscalls.
1056 KJ_IF_MAYBE(p, replyLoop->port) {
1057 p->wake();
1058 }
1059 }
1060 }
1061
1062 void XThreadEvent::done() {
1063 KJ_ASSERT(targetExecutor.get() == &currentEventLoop().getExecutor(),
1064 "calling done() from wrong thread?");
1065
1066 sendReply();
1067
1068 {
1069 auto lock = targetExecutor->impl->state.lockExclusive();
1070
1071 switch (state) {
1072 case EXECUTING:
1073 lock->executing.remove(*this);
1074 break;
1075 case CANCELING:
1076 // Sending thread requested cancellation, but we're done anyway, so it doesn't matter at this
1077 // point.
1078 lock->cancel.remove(*this);
1079 break;
1080 default:
1081 KJ_FAIL_ASSERT("can't call done() from this state", (uint)state);
1082 }
1083
1084 setDoneState();
1085 }
1086 }
1087
1088 inline void XThreadEvent::setDoneState() {
1089 __atomic_store_n(&state, DONE, __ATOMIC_RELEASE);
1090 }
1091
1092 void XThreadEvent::setDisconnected() {
1093 result.addException(KJ_EXCEPTION(DISCONNECTED,
1094 "Executor's event loop exited before cross-thread event could complete"));
1095 }
1096
1097 class XThreadEvent::DelayedDoneHack: public Disposer {
1098 // Crazy hack: In fire(), we want to call done() if the event is finished. But done() signals
1099 // the requesting thread to wake up and possibly delete the XThreadEvent. But the caller (the
1100 // EventLoop) still has to set `event->firing = false` after `fire()` returns, so this would be
1101 // a race condition use-after-free.
1102 //
1103 // It just so happens, though, that fire() is allowed to return an optional `Own<Event>` to drop,
1104 // and the caller drops that pointer immediately after setting event->firing = false. So we
1105 // return a pointer whose disposer calls done().
1106 //
1107 // It's not quite as much of a hack as it seems: The whole reason fire() returns an Own<Event> is
1108 // so that the event can delete itself, but do so after the caller sets event->firing = false.
1109 // It just happens to be that in this case, the event isn't deleting itself, but rather releasing
1110 // itself back to the other thread.
1111
1112 protected:
1113 void disposeImpl(void* pointer) const override {
1114 reinterpret_cast<XThreadEvent*>(pointer)->done();
1115 }
1116 };
1117
1118 Maybe<Own<Event>> XThreadEvent::fire() {
1119 static constexpr DelayedDoneHack DISPOSER {};
1120
1121 KJ_IF_MAYBE(n, promiseNode) {
1122 n->get()->get(result);
1123 promiseNode = nullptr; // make sure to destroy in the thread that created it
1124 return Own<Event>(this, DISPOSER);
1125 } else {
1126 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([&]() {
1127 promiseNode = execute();
1128 })) {
1129 result.addException(kj::mv(*exception));
1130 };
1131 KJ_IF_MAYBE(n, promiseNode) {
1132 n->get()->onReady(this);
1133 } else {
1134 return Own<Event>(this, DISPOSER);
1135 }
1136 }
1137
1138 return nullptr;
1139 }
1140
1141 void XThreadEvent::traceEvent(TraceBuilder& builder) {
1142 KJ_IF_MAYBE(n, promiseNode) {
1143 n->get()->tracePromise(builder, true);
1144 }
1145
1146 // We can't safely trace into another thread, so we'll stop here.
1147 builder.add(funcTracePtr);
1148 }
1149
1150 void XThreadEvent::onReady(Event* event) noexcept {
1151 onReadyEvent.init(event);
1152 }
1153
1154 XThreadPaf::XThreadPaf()
1155 : state(WAITING), executor(getCurrentThreadExecutor()) {}
1156 XThreadPaf::~XThreadPaf() noexcept(false) {}
1157
1158 void XThreadPaf::destroy() {
1159 auto oldState = WAITING;
1160
1161 if (__atomic_load_n(&state, __ATOMIC_ACQUIRE) == DISPATCHED) {
1162 // Common case: Promise was fully fulfilled and dispatched, no need for locking.
1163 delete this;
1164 } else if (__atomic_compare_exchange_n(&state, &oldState, CANCELED, false,
1165 __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE)) {
1166 // State transitioned from WAITING to CANCELED, so now it's the fulfiller's job to destroy the
1167 // object.
1168 } else {
1169 // Whoops, another thread is already in the process of fulfilling this promise. We'll have to
1170 // wait for it to finish and transition the state to FULFILLED.
1171 executor.impl->state.when([&](auto&) {
1172 return state == FULFILLED || state == DISPATCHED;
1173 }, [&](Executor::Impl::State& exState) {
1174 if (state == FULFILLED) {
1175 // The object is on the queue but was not yet dispatched. Remove it.
1176 exState.fulfilled.remove(*this);
1177 }
1178 });
1179
1180 // It's ours now, delete it.
1181 delete this;
1182 }
1183 }
1184
1185 void XThreadPaf::onReady(Event* event) noexcept {
1186 onReadyEvent.init(event);
1187 }
1188
1189 void XThreadPaf::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
1190 // We can't safely trace into another thread, so we'll stop here.
1191 // Maybe returning the address of get() will give us a function name with meaningful type
1192 // information.
1193 builder.add(getMethodStartAddress(implicitCast<PromiseNode&>(*this), &PromiseNode::get));
1194 }
1195
1196 XThreadPaf::FulfillScope::FulfillScope(XThreadPaf** pointer) {
1197 obj = __atomic_exchange_n(pointer, static_cast<XThreadPaf*>(nullptr), __ATOMIC_ACQUIRE);
1198 auto oldState = WAITING;
1199 if (obj == nullptr) {
1200 // Already fulfilled (possibly by another thread).
1201 } else if (__atomic_compare_exchange_n(&obj->state, &oldState, FULFILLING, false,
1202 __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE)) {
1203 // Transitioned to FULFILLING, good.
1204 } else {
1205 // The waiting thread must have canceled.
1206 KJ_ASSERT(oldState == CANCELED);
1207
1208 // It's our responsibility to clean up, then.
1209 delete obj;
1210
1211 // Set `obj` null so that we don't try to fill it in or delete it later.
1212 obj = nullptr;
1213 }
1214 }
1215 XThreadPaf::FulfillScope::~FulfillScope() noexcept(false) {
1216 if (obj != nullptr) {
1217 auto lock = obj->executor.impl->state.lockExclusive();
1218 KJ_IF_MAYBE(l, lock->loop) {
1219 lock->fulfilled.add(*obj);
1220 __atomic_store_n(&obj->state, FULFILLED, __ATOMIC_RELEASE);
1221 KJ_IF_MAYBE(p, l->port) {
1222 // TODO(perf): It's annoying we have to call wake() with the lock held, but we have to
1223 // prevent the destination EventLoop from being destroyed first.
1224 p->wake();
1225 }
1226 } else {
1227 KJ_LOG(FATAL,
1228 "the thread which called kj::newPromiseAndCrossThreadFulfiller<T>() apparently exited "
1229 "its own event loop without canceling the cross-thread promise first; this is "
1230 "undefined behavior so I will crash now");
1231 abort();
1232 }
1233 }
1234 }
1235
1236 kj::Exception XThreadPaf::unfulfilledException() {
1237 // TODO(cleanup): Share code with regular PromiseAndFulfiller for stack tracing here.
1238 return kj::Exception(kj::Exception::Type::FAILED, __FILE__, __LINE__, kj::heapString(
1239 "cross-thread PromiseFulfiller was destroyed without fulfilling the promise."));
1240 }
1241
1242 class ExecutorImpl: public Executor, public AtomicRefcounted {
1243 public:
1244 using Executor::Executor;
1245
1246 kj::Own<const Executor> addRef() const override {
1247 return kj::atomicAddRef(*this);
1248 }
1249 };
1250
1251 } // namespace _
1252
1253 Executor::Executor(EventLoop& loop, Badge<EventLoop>): impl(kj::heap<Impl>(loop)) {}
1254 Executor::~Executor() noexcept(false) {}
1255
1256 bool Executor::isLive() const {
1257 return impl->state.lockShared()->loop != nullptr;
1258 }
1259
1260 void Executor::send(_::XThreadEvent& event, bool sync) const {
1261 KJ_ASSERT(event.state == _::XThreadEvent::UNUSED);
1262
1263 if (sync) {
1264 EventLoop* thisThread = threadLocalEventLoop;
1265 if (thisThread != nullptr &&
1266 thisThread->executor.map([this](auto& e) { return e == this; }).orDefault(false)) {
1267 // Invoking a sync request on our own thread. Just execute it directly; if we try to queue
1268 // it to the loop, we'll deadlock.
1269 auto promiseNode = event.execute();
1270
1271 // If the function returns a promise, we have no way to pump the event loop to wait for it,
1272 // because the event loop may already be pumping somewhere up the stack.
1273 KJ_ASSERT(promiseNode == nullptr,
1274 "can't call executeSync() on own thread's executor with a promise-returning function");
1275
1276 return;
1277 }
1278 } else {
1279 event.replyExecutor = getCurrentThreadExecutor();
1280
1281 // Note that async requests will "just work" even if the target executor is our own thread's
1282 // executor. In theory we could detect this case to avoid some locking and signals but that
1283 // would be extra code complexity for probably little benefit.
1284 }
1285
1286 auto lock = impl->state.lockExclusive();
1287 const EventLoop* loop;
1288 KJ_IF_MAYBE(l, lock->loop) {
1289 loop = l;
1290 } else {
1291 event.setDisconnected();
1292 event.setDoneState();
1293 return;
1294 }
1295
1296 event.state = _::XThreadEvent::QUEUED;
1297 lock->start.add(event);
1298
1299 KJ_IF_MAYBE(p, loop->port) {
1300 p->wake();
1301 } else {
1302 // Event loop will be waiting on executor.wait(), which will be woken when we unlock the mutex.
1303 }
1304
1305 if (sync) {
1306 lock.wait([&](auto&) { return event.state == _::XThreadEvent::DONE; });
1307 }
1308 }
1309
1310 void Executor::wait() {
1311 Vector<_::XThreadEvent*> eventsToCancelOutsideLock;
1312 KJ_DEFER(impl->processAsyncCancellations(eventsToCancelOutsideLock));
1313
1314 auto lock = impl->state.lockExclusive();
1315
1316 lock.wait([](const Impl::State& state) {
1317 return state.isDispatchNeeded();
1318 });
1319
1320 lock->dispatchAll(eventsToCancelOutsideLock);
1321 }
1322
1323 bool Executor::poll() {
1324 Vector<_::XThreadEvent*> eventsToCancelOutsideLock;
1325 KJ_DEFER(impl->processAsyncCancellations(eventsToCancelOutsideLock));
1326
1327 auto lock = impl->state.lockExclusive();
1328 if (lock->isDispatchNeeded()) {
1329 lock->dispatchAll(eventsToCancelOutsideLock);
1330 return true;
1331 } else {
1332 return false;
1333 }
1334 }
1335
1336 EventLoop& Executor::getLoop() const {
1337 KJ_IF_MAYBE(l, impl->state.lockShared()->loop) {
1338 return *l;
1339 } else {
1340 kj::throwFatalException(KJ_EXCEPTION(DISCONNECTED, "Executor's event loop has exited"));
1341 }
1342 }
1343
1344 const Executor& getCurrentThreadExecutor() {
1345 return currentEventLoop().getExecutor();
1346 }
1347
1348 // =======================================================================================
1349 // Fiber implementation.
1350
1351 namespace _ { // private
1352
1353 #if KJ_USE_FIBERS
1354 #if !(_WIN32 || __CYGWIN__)
1355 struct FiberStack::Impl {
1356 // This struct serves two purposes:
1357 // - It contains OS-specific state that we don't want to declare in the header.
1358 // - It is allocated at the top of the fiber's stack area, so the Impl pointer also serves to
1359 // track where the stack was allocated.
1360
1361 jmp_buf fiberJmpBuf;
1362 jmp_buf originalJmpBuf;
1363
1364 #if KJ_HAS_COMPILER_FEATURE(address_sanitizer)
1365 // Stuff that we need to pass to __sanitizer_start_switch_fiber() /
1366 // __sanitizer_finish_switch_fiber() when using ASAN.
1367
1368 void* originalFakeStack = nullptr;
1369 void* fiberFakeStack = nullptr;
1370 // Pointer to ASAN "fake stack" associated with the fiber and its calling stack. Filled in by
1371 // __sanitizer_start_switch_fiber() before switching away, consumed by
1372 // __sanitizer_finish_switch_fiber() upon switching back.
1373
1374 void const* originalBottom;
1375 size_t originalSize;
1376 // Size and location of the original stack before switching fibers. These are filled in by
1377 // __sanitizer_finish_switch_fiber() after the switch, and must be passed to
1378 // __sanitizer_start_switch_fiber() when switching back later.
1379 #endif
1380
1381 static Impl* alloc(size_t stackSize, ucontext_t* context) {
1382 #ifndef MAP_ANONYMOUS
1383 #define MAP_ANONYMOUS MAP_ANON
1384 #endif
1385 size_t pageSize = getPageSize();
1386 size_t allocSize = stackSize + pageSize; // size plus guard page and impl
1387
1388 // Allocate virtual address space for the stack but make it inaccessible initially.
1389 // TODO(someday): Does it make sense to use MAP_GROWSDOWN on Linux? It's a kind of bizarre flag
1390 // that causes the mapping to automatically allocate extra pages (beyond the range specified)
1391 // until it hits something... Note that on FreeBSD, MAP_STACK has the effect that
1392 // MAP_GROWSDOWN has on Linux. (MAP_STACK, meanwhile, has no effect on Linux.)
1393 void* stackMapping = mmap(nullptr, allocSize, PROT_NONE,
1394 MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
1395 if (stackMapping == MAP_FAILED) {
1396 KJ_FAIL_SYSCALL("mmap(new stack)", errno);
1397 }
1398 KJ_ON_SCOPE_FAILURE({
1399 KJ_SYSCALL(munmap(stackMapping, allocSize)) { break; }
1400 });
1401
1402 void* stack = reinterpret_cast<byte*>(stackMapping) + pageSize;
1403 // Now mark everything except the guard page as read-write. We assume the stack grows down, so
1404 // the guard page is at the beginning. No modern architecture uses stacks that grow up.
1405 KJ_SYSCALL(mprotect(stack, stackSize, PROT_READ | PROT_WRITE));
1406
1407 // Stick `Impl` at the top of the stack.
1408 Impl* impl = (reinterpret_cast<Impl*>(reinterpret_cast<byte*>(stack) + stackSize) - 1);
1409
1410 // Note: mmap() allocates zero'd pages so we don't have to memset() anything here.
1411
1412 KJ_SYSCALL(getcontext(context));
1413 #if __APPLE__ && __aarch64__
1414 // Per issue #1386, apple on arm64 zeros the entire configured stack.
1415 // But this is redundant, since we just allocated the stack with mmap() which
1416 // returns zero'd pages. Re-zeroing is both slow and results in prematurely
1417 // allocating pages we may not need -- it's normal for stacks to rely heavily
1418 // on lazy page allocation to avoid wasting memory. Instead, we lie:
1419 // we allocate the full size, but tell the ucontext the stack is the last
1420 // page only. This appears to work as no particular bounds checks or
1421 // anything are set up based on what we say here.
1422 context->uc_stack.ss_size = min(pageSize, stackSize) - sizeof(Impl);
1423 context->uc_stack.ss_sp = reinterpret_cast<char*>(stack) + stackSize - min(pageSize, stackSize);
1424 #else
1425 context->uc_stack.ss_size = stackSize - sizeof(Impl);
1426 context->uc_stack.ss_sp = reinterpret_cast<char*>(stack);
1427 #endif
1428 context->uc_stack.ss_flags = 0;
1429 // We don't use uc_link since our fiber start routine runs forever in a loop to allow for
1430 // reuse. When we're done with the fiber, we just destroy it, without switching to it's
1431 // stack. This is safe since the start routine doesn't allocate any memory or RAII objects
1432 // before looping.
1433 context->uc_link = 0;
1434
1435 return impl;
1436 }
1437
1438 static void free(Impl* impl, size_t stackSize) {
1439 size_t allocSize = stackSize + getPageSize();
1440 void* stack = reinterpret_cast<byte*>(impl + 1) - allocSize;
1441 KJ_SYSCALL(munmap(stack, allocSize)) { break; }
1442 }
1443
1444 static size_t getPageSize() {
1445 #ifndef _SC_PAGESIZE
1446 #define _SC_PAGESIZE _SC_PAGE_SIZE
1447 #endif
1448 static size_t result = sysconf(_SC_PAGESIZE);
1449 return result;
1450 }
1451 };
1452 #endif
1453 #endif
1454
1455 struct FiberStack::StartRoutine {
1456 #if _WIN32 || __CYGWIN__
1457 static void WINAPI run(LPVOID ptr) {
1458 // This is the static C-style function we pass to CreateFiber().
1459 reinterpret_cast<FiberStack*>(ptr)->run();
1460 }
1461 #else
1462 [[noreturn]] static void run(int arg1, int arg2) {
1463 // This is the static C-style function we pass to makeContext().
1464
1465 // POSIX says the arguments are ints, not pointers. So we split our pointer in half in order to
1466 // work correctly on 64-bit machines. Gross.
1467 uintptr_t ptr = static_cast<uint>(arg1);
1468 ptr |= static_cast<uintptr_t>(static_cast<uint>(arg2)) << (sizeof(ptr) * 4);
1469
1470 auto& stack = *reinterpret_cast<FiberStack*>(ptr);
1471
1472 __sanitizer_finish_switch_fiber(nullptr,
1473 &stack.impl->originalBottom, &stack.impl->originalSize);
1474
1475 // We first switch to the fiber inside of the FiberStack constructor. This is just for
1476 // initialization purposes, and we're expected to switch back immediately.
1477 stack.switchToMain();
1478
1479 // OK now have a real job.
1480 stack.run();
1481 }
1482 #endif
1483 };
1484
1485 void FiberStack::run() {
1486 // Loop forever so that the fiber can be reused.
1487 for (;;) {
1488 KJ_SWITCH_ONEOF(main) {
1489 KJ_CASE_ONEOF(event, FiberBase*) {
1490 event->run();
1491 }
1492 KJ_CASE_ONEOF(func, SynchronousFunc*) {
1493 KJ_IF_MAYBE(exception, kj::runCatchingExceptions(func->func)) {
1494 func->exception.emplace(kj::mv(*exception));
1495 }
1496 }
1497 }
1498
1499 // Wait for the fiber to be used again. Note the fiber might simply be destroyed without this
1500 // ever returning. That's OK because we don't have any nontrivial destructors on the stack
1501 // at this point.
1502 switchToMain();
1503 }
1504 }
1505
1506 FiberStack::FiberStack(size_t stackSizeParam)
1507 // Force stackSize to a reasonable minimum.
1508 : stackSize(kj::max(stackSizeParam, 65536))
1509 {
1510
1511 #if KJ_USE_FIBERS
1512 #if _WIN32 || __CYGWIN__
1513 // We can create fibers before we convert the main thread into a fiber in FiberBase
1514 KJ_WIN32(osFiber = CreateFiber(stackSize, &StartRoutine::run, this));
1515
1516 #else
1517 // Note: Nothing below here can throw. If that changes then we need to call Impl::free(impl)
1518 // on exceptions...
1519 ucontext_t context;
1520 impl = Impl::alloc(stackSize, &context);
1521
1522 // POSIX says the arguments are ints, not pointers. So we split our pointer in half in order to
1523 // work correctly on 64-bit machines. Gross.
1524 uintptr_t ptr = reinterpret_cast<uintptr_t>(this);
1525 int arg1 = ptr & ((uintptr_t(1) << (sizeof(ptr) * 4)) - 1);
1526 int arg2 = ptr >> (sizeof(ptr) * 4);
1527
1528 makecontext(&context, reinterpret_cast<void(*)()>(&StartRoutine::run), 2, arg1, arg2);
1529
1530 __sanitizer_start_switch_fiber(&impl->originalFakeStack, impl, stackSize - sizeof(Impl));
1531 if (_setjmp(impl->originalJmpBuf) == 0) {
1532 setcontext(&context);
1533 }
1534 __sanitizer_finish_switch_fiber(impl->originalFakeStack, nullptr, nullptr);
1535 #endif
1536 #else
1537 #if KJ_NO_EXCEPTIONS
1538 KJ_UNIMPLEMENTED("Fibers are not implemented because exceptions are disabled");
1539 #else
1540 KJ_UNIMPLEMENTED(
1541 "Fibers are not implemented on this platform because its C library lacks setcontext() "
1542 "and friends. If you'd like to see fiber support added, file a bug to let us know. "
1543 "We can likely make it happen using assembly, but didn't want to try unless it was "
1544 "actually needed.");
1545 #endif
1546 #endif
1547 }
1548
1549 FiberStack::~FiberStack() noexcept(false) {
1550 #if KJ_USE_FIBERS
1551 #if _WIN32 || __CYGWIN__
1552 DeleteFiber(osFiber);
1553 #else
1554 Impl::free(impl, stackSize);
1555 #endif
1556 #endif
1557 }
1558
1559 void FiberStack::initialize(FiberBase& fiber) {
1560 KJ_REQUIRE(this->main == nullptr);
1561 this->main = &fiber;
1562 }
1563
1564 void FiberStack::initialize(SynchronousFunc& func) {
1565 KJ_REQUIRE(this->main == nullptr);
1566 this->main = &func;
1567 }
1568
1569 FiberBase::FiberBase(size_t stackSize, _::ExceptionOrValue& result, SourceLocation location)
1570 : Event(location), state(WAITING), stack(kj::heap<FiberStack>(stackSize)), result(result) {
1571 stack->initialize(*this);
1572 ensureThreadCanRunFibers();
1573 }
1574
1575 FiberBase::FiberBase(const FiberPool& pool, _::ExceptionOrValue& result, SourceLocation location)
1576 : Event(location), state(WAITING), result(result) {
1577 stack = pool.impl->takeStack();
1578 stack->initialize(*this);
1579 ensureThreadCanRunFibers();
1580 }
1581
1582 FiberBase::~FiberBase() noexcept(false) {}
1583
1584 void FiberBase::cancel() {
1585 // Called by `~Fiber()` to begin teardown. We can't do this work in `~FiberBase()` because the
1586 // `Fiber` subclass contains members that may still be in-use until the fiber stops.
1587
1588 switch (state) {
1589 case WAITING:
1590 // We can't just free the stack while the fiber is running. We need to force it to execute
1591 // until finished, so we cause it to throw an exception.
1592 state = CANCELED;
1593 stack->switchToFiber();
1594
1595 // The fiber should only switch back to the main stack on completion, because any further
1596 // calls to wait() would throw before trying to switch.
1597 KJ_ASSERT(state == FINISHED);
1598
1599 // The fiber shut down properly so the stack is safe to reuse.
1600 stack->reset();
1601 break;
1602
1603 case RUNNING:
1604 case CANCELED:
1605 // Bad news.
1606 KJ_LOG(FATAL, "fiber tried to cancel itself");
1607 ::abort();
1608 break;
1609
1610 case FINISHED:
1611 // Normal completion, yay.
1612 stack->reset();
1613 break;
1614 }
1615 }
1616
1617 Maybe<Own<Event>> FiberBase::fire() {
1618 KJ_ASSERT(state == WAITING);
1619 state = RUNNING;
1620 stack->switchToFiber();
1621 return nullptr;
1622 }
1623
1624 void FiberStack::switchToFiber() {
1625 // Switch from the main stack to the fiber. Returns once the fiber either calls switchToMain()
1626 // or returns from its main function.
1627 #if KJ_USE_FIBERS
1628 #if _WIN32 || __CYGWIN__
1629 SwitchToFiber(osFiber);
1630 #else
1631 __sanitizer_start_switch_fiber(&impl->originalFakeStack, impl, stackSize - sizeof(Impl));
1632 if (_setjmp(impl->originalJmpBuf) == 0) {
1633 _longjmp(impl->fiberJmpBuf, 1);
1634 }
1635 __sanitizer_finish_switch_fiber(impl->originalFakeStack, nullptr, nullptr);
1636 #endif
1637 #endif
1638 }
1639 void FiberStack::switchToMain() {
1640 // Switch from the fiber to the main stack. Returns the next time the main stack calls
1641 // switchToFiber().
1642 #if KJ_USE_FIBERS
1643 #if _WIN32 || __CYGWIN__
1644 SwitchToFiber(getMainWin32Fiber());
1645 #else
1646 // TODO(someady): In theory, the last time we switch away from the fiber, we should pass `nullptr`
1647 // for the first argument here, so that ASAN destroys the fake stack. However, as currently
1648 // designed, we don't actually know if we're switching away for the last time. It's understood
1649 // that when we call switchToMain() in FiberStack::run(), then the main stack is allowed to
1650 // destroy the fiber, or reuse it. I don't want to develop a mechanism to switch back to the
1651 // fiber on final destruction just to get the hints right, so instead we leak the fake stack.
1652 // This doesn't seem to cause any problems -- it's not even detected by ASAN as a memory leak.
1653 // But if we wanted to run ASAN builds in production or something, it might be an issue.
1654 __sanitizer_start_switch_fiber(&impl->fiberFakeStack,
1655 impl->originalBottom, impl->originalSize);
1656 if (_setjmp(impl->fiberJmpBuf) == 0) {
1657 _longjmp(impl->originalJmpBuf, 1);
1658 }
1659 __sanitizer_finish_switch_fiber(impl->fiberFakeStack,
1660 &impl->originalBottom, &impl->originalSize);
1661 #endif
1662 #endif
1663 }
1664
1665 void FiberBase::run() {
1666 #if !KJ_NO_EXCEPTIONS
1667 bool caughtCanceled = false;
1668 state = RUNNING;
1669 KJ_DEFER(state = FINISHED);
1670
1671 WaitScope waitScope(currentEventLoop(), *this);
1672
1673 try {
1674 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([&]() {
1675 runImpl(waitScope);
1676 })) {
1677 result.addException(kj::mv(*exception));
1678 }
1679 } catch (CanceledException) {
1680 if (state != CANCELED) {
1681 // no idea who would throw this but it's not really our problem
1682 result.addException(KJ_EXCEPTION(FAILED, "Caught CanceledException, but fiber wasn't canceled"));
1683 }
1684 caughtCanceled = true;
1685 }
1686
1687 if (state == CANCELED && !caughtCanceled) {
1688 KJ_LOG(ERROR, "Canceled fiber apparently caught CanceledException and didn't rethrow it. "
1689 "Generally, applications should not catch CanceledException, but if they do, they must always rethrow.");
1690 }
1691
1692 onReadyEvent.arm();
1693 #endif
1694 }
1695
1696 void FiberBase::onReady(_::Event* event) noexcept {
1697 onReadyEvent.init(event);
1698 }
1699
1700 void FiberBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
1701 if (stopAtNextEvent) return;
1702 currentInner->tracePromise(builder, false);
1703 stack->trace(builder);
1704 }
1705
1706 void FiberBase::traceEvent(TraceBuilder& builder) {
1707 currentInner->tracePromise(builder, true);
1708 stack->trace(builder);
1709 onReadyEvent.traceEvent(builder);
1710 }
1711
1712 } // namespace _ (private)
1713
1714 // =======================================================================================
1715
1716 void EventPort::setRunnable(bool runnable) {}
1717
1718 void EventPort::wake() const {
1719 kj::throwRecoverableException(KJ_EXCEPTION(UNIMPLEMENTED,
1720 "cross-thread wake() not implemented by this EventPort implementation"));
1721 }
1722
1723 EventLoop::EventLoop()
1724 : daemons(kj::heap<TaskSet>(_::LoggingErrorHandler::instance)) {}
1725
1726 EventLoop::EventLoop(EventPort& port)
1727 : port(port),
1728 daemons(kj::heap<TaskSet>(_::LoggingErrorHandler::instance)) {}
1729
1730 EventLoop::~EventLoop() noexcept(false) {
1731 // Destroy all "daemon" tasks, noting that their destructors might register more daemon tasks.
1732 while (!daemons->isEmpty()) {
1733 auto oldDaemons = kj::mv(daemons);
1734 daemons = kj::heap<TaskSet>(_::LoggingErrorHandler::instance);
1735 }
1736 daemons = nullptr;
1737
1738 KJ_IF_MAYBE(e, executor) {
1739 // Cancel all outstanding cross-thread events.
1740 e->get()->impl->disconnect();
1741 }
1742
1743 // The application _should_ destroy everything using the EventLoop before destroying the
1744 // EventLoop itself, so if there are events on the loop, this indicates a memory leak.
1745 KJ_REQUIRE(head == nullptr, "EventLoop destroyed with events still in the queue. Memory leak?",
1746 head->traceEvent()) {
1747 // Unlink all the events and hope that no one ever fires them...
1748 _::Event* event = head;
1749 while (event != nullptr) {
1750 _::Event* next = event->next;
1751 event->next = nullptr;
1752 event->prev = nullptr;
1753 event = next;
1754 }
1755 break;
1756 }
1757
1758 KJ_REQUIRE(threadLocalEventLoop != this,
1759 "EventLoop destroyed while still current for the thread.") {
1760 threadLocalEventLoop = nullptr;
1761 break;
1762 }
1763 }
1764
1765 void EventLoop::run(uint maxTurnCount) {
1766 running = true;
1767 KJ_DEFER(running = false);
1768
1769 for (uint i = 0; i < maxTurnCount; i++) {
1770 if (!turn()) {
1771 break;
1772 }
1773 }
1774
1775 setRunnable(isRunnable());
1776 }
1777
1778 bool EventLoop::turn() {
1779 _::Event* event = head;
1780
1781 if (event == nullptr) {
1782 // No events in the queue.
1783 return false;
1784 } else {
1785 head = event->next;
1786 if (head != nullptr) {
1787 head->prev = &head;
1788 }
1789
1790 depthFirstInsertPoint = &head;
1791 if (breadthFirstInsertPoint == &event->next) {
1792 breadthFirstInsertPoint = &head;
1793 }
1794 if (tail == &event->next) {
1795 tail = &head;
1796 }
1797
1798 event->next = nullptr;
1799 event->prev = nullptr;
1800
1801 Maybe<Own<_::Event>> eventToDestroy;
1802 {
1803 event->firing = true;
1804 KJ_DEFER(event->firing = false);
1805 currentlyFiring = event;
1806 KJ_DEFER(currentlyFiring = nullptr);
1807 eventToDestroy = event->fire();
1808 }
1809
1810 depthFirstInsertPoint = &head;
1811 return true;
1812 }
1813 }
1814
1815 bool EventLoop::isRunnable() {
1816 return head != nullptr;
1817 }
1818
1819 const Executor& EventLoop::getExecutor() {
1820 KJ_IF_MAYBE(e, executor) {
1821 return **e;
1822 } else {
1823 return *executor.emplace(kj::atomicRefcounted<_::ExecutorImpl>(*this, Badge<EventLoop>()));
1824 }
1825 }
1826
1827 void EventLoop::setRunnable(bool runnable) {
1828 if (runnable != lastRunnableState) {
1829 KJ_IF_MAYBE(p, port) {
1830 p->setRunnable(runnable);
1831 }
1832 lastRunnableState = runnable;
1833 }
1834 }
1835
1836 void EventLoop::enterScope() {
1837 KJ_REQUIRE(threadLocalEventLoop == nullptr, "This thread already has an EventLoop.");
1838 threadLocalEventLoop = this;
1839 }
1840
1841 void EventLoop::leaveScope() {
1842 KJ_REQUIRE(threadLocalEventLoop == this,
1843 "WaitScope destroyed in a different thread than it was created in.") {
1844 break;
1845 }
1846 threadLocalEventLoop = nullptr;
1847 }
1848
1849 void EventLoop::wait() {
1850 KJ_IF_MAYBE(p, port) {
1851 if (p->wait()) {
1852 // Another thread called wake(). Check for cross-thread events.
1853 KJ_IF_MAYBE(e, executor) {
1854 e->get()->poll();
1855 }
1856 }
1857 } else KJ_IF_MAYBE(e, executor) {
1858 e->get()->wait();
1859 } else {
1860 KJ_FAIL_REQUIRE("Nothing to wait for; this thread would hang forever.");
1861 }
1862 }
1863
1864 void EventLoop::poll() {
1865 KJ_IF_MAYBE(p, port) {
1866 if (p->poll()) {
1867 // Another thread called wake(). Check for cross-thread events.
1868 KJ_IF_MAYBE(e, executor) {
1869 e->get()->poll();
1870 }
1871 }
1872 } else KJ_IF_MAYBE(e, executor) {
1873 e->get()->poll();
1874 }
1875 }
1876
1877 uint WaitScope::poll(uint maxTurnCount) {
1878 KJ_REQUIRE(&loop == threadLocalEventLoop, "WaitScope not valid for this thread.");
1879 KJ_REQUIRE(!loop.running, "poll() is not allowed from within event callbacks.");
1880
1881 loop.running = true;
1882 KJ_DEFER(loop.running = false);
1883
1884 uint turnCount = 0;
1885 runOnStackPool([&]() {
1886 while (turnCount < maxTurnCount) {
1887 if (loop.turn()) {
1888 ++turnCount;
1889 } else {
1890 // No events in the queue. Poll for I/O.
1891 loop.poll();
1892
1893 if (!loop.isRunnable()) {
1894 // Still no events in the queue. We're done.
1895 return;
1896 }
1897 }
1898 }
1899 });
1900 return turnCount;
1901 }
1902
1903 void WaitScope::cancelAllDetached() {
1904 KJ_REQUIRE(fiber == nullptr,
1905 "can't call cancelAllDetached() on a fiber WaitScope, only top-level");
1906
1907 while (!loop.daemons->isEmpty()) {
1908 auto oldDaemons = kj::mv(loop.daemons);
1909 loop.daemons = kj::heap<TaskSet>(_::LoggingErrorHandler::instance);
1910 // Destroying `oldDaemons` could theoretically add new ones.
1911 }
1912 }
1913
1914 namespace _ { // private
1915
1916 #if !KJ_NO_EXCEPTIONS
1917 static kj::CanceledException fiberCanceledException() {
1918 // Construct the exception to throw from wait() when the fiber has been canceled (because the
1919 // promise returned by startFiber() was dropped before completion).
1920 return kj::CanceledException { };
1921 };
1922 #endif
1923
1924 void waitImpl(_::OwnPromiseNode&& node, _::ExceptionOrValue& result, WaitScope& waitScope,
1925 SourceLocation location) {
1926 EventLoop& loop = waitScope.loop;
1927 KJ_REQUIRE(&loop == threadLocalEventLoop, "WaitScope not valid for this thread.");
1928
1929 #if !KJ_NO_EXCEPTIONS
1930 // we don't support fibers when running without exceptions, so just remove the whole block
1931 KJ_IF_MAYBE(fiber, waitScope.fiber) {
1932 if (fiber->state == FiberBase::CANCELED) {
1933 throw fiberCanceledException();
1934 }
1935 KJ_REQUIRE(fiber->state == FiberBase::RUNNING,
1936 "This WaitScope can only be used within the fiber that created it.");
1937
1938 node->setSelfPointer(&node);
1939 node->onReady(fiber);
1940
1941 fiber->currentInner = node;
1942 KJ_DEFER(fiber->currentInner = nullptr);
1943
1944 // Switch to the main stack to run the event loop.
1945 fiber->state = FiberBase::WAITING;
1946 fiber->stack->switchToMain();
1947
1948 // The main stack switched back to us, meaning either the event we registered with
1949 // node->onReady() fired, or we are being canceled by FiberBase's destructor.
1950
1951 if (fiber->state == FiberBase::CANCELED) {
1952 throw fiberCanceledException();
1953 }
1954
1955 KJ_ASSERT(fiber->state == FiberBase::RUNNING);
1956 } else {
1957 #endif
1958 KJ_REQUIRE(!loop.running, "wait() is not allowed from within event callbacks.");
1959
1960 RootEvent doneEvent(node, reinterpret_cast<void*>(&waitImpl), location);
1961 node->setSelfPointer(&node);
1962 node->onReady(&doneEvent);
1963
1964 loop.running = true;
1965 KJ_DEFER(loop.running = false);
1966
1967 for (;;) {
1968 waitScope.runOnStackPool([&]() {
1969 uint counter = 0;
1970 while (!doneEvent.fired) {
1971 if (!loop.turn()) {
1972 // No events in the queue. Wait for callback.
1973 return;
1974 } else if (++counter > waitScope.busyPollInterval) {
1975 // Note: It's intentional that if busyPollInterval is kj::maxValue, we never poll.
1976 counter = 0;
1977 loop.poll();
1978 }
1979 }
1980 });
1981
1982 if (doneEvent.fired) {
1983 break;
1984 } else {
1985 loop.wait();
1986 }
1987 }
1988
1989 loop.setRunnable(loop.isRunnable());
1990 #if !KJ_NO_EXCEPTIONS
1991 }
1992 #endif
1993
1994 waitScope.runOnStackPool([&]() {
1995 node->get(result);
1996 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([&]() {
1997 node = nullptr;
1998 })) {
1999 result.addException(kj::mv(*exception));
2000 }
2001 });
2002 }
2003
2004 bool pollImpl(_::PromiseNode& node, WaitScope& waitScope, SourceLocation location) {
2005 EventLoop& loop = waitScope.loop;
2006 KJ_REQUIRE(&loop == threadLocalEventLoop, "WaitScope not valid for this thread.");
2007 KJ_REQUIRE(waitScope.fiber == nullptr, "poll() is not supported in fibers.");
2008 KJ_REQUIRE(!loop.running, "poll() is not allowed from within event callbacks.");
2009
2010 RootEvent doneEvent(&node, reinterpret_cast<void*>(&pollImpl), location);
2011 node.onReady(&doneEvent);
2012
2013 loop.running = true;
2014 KJ_DEFER(loop.running = false);
2015
2016 waitScope.runOnStackPool([&]() {
2017 while (!doneEvent.fired) {
2018 if (!loop.turn()) {
2019 // No events in the queue. Poll for I/O.
2020 loop.poll();
2021
2022 if (!doneEvent.fired && !loop.isRunnable()) {
2023 // No progress. Give up.
2024 node.onReady(nullptr);
2025 loop.setRunnable(false);
2026 break;
2027 }
2028 }
2029 }
2030 });
2031
2032 if (!doneEvent.fired) {
2033 return false;
2034 }
2035
2036 loop.setRunnable(loop.isRunnable());
2037 return true;
2038 }
2039
2040 Promise<void> yield() {
2041 class YieldPromiseNode final: public _::PromiseNode {
2042 public:
2043 void destroy() override {}
2044
2045 void onReady(_::Event* event) noexcept override {
2046 if (event) event->armBreadthFirst();
2047 }
2048 void get(_::ExceptionOrValue& output) noexcept override {
2049 output.as<_::Void>() = _::Void();
2050 }
2051 void tracePromise(_::TraceBuilder& builder, bool stopAtNextEvent) override {
2052 builder.add(reinterpret_cast<void*>(&kj::evalLater<DummyFunctor>));
2053 }
2054 };
2055
2056 static YieldPromiseNode NODE;
2057 return _::PromiseNode::to<Promise<void>>(OwnPromiseNode(&NODE));
2058 }
2059
2060 Promise<void> yieldHarder() {
2061 class YieldHarderPromiseNode final: public _::PromiseNode {
2062 public:
2063 void destroy() override {}
2064
2065 void onReady(_::Event* event) noexcept override {
2066 if (event) event->armLast();
2067 }
2068 void get(_::ExceptionOrValue& output) noexcept override {
2069 output.as<_::Void>() = _::Void();
2070 }
2071 void tracePromise(_::TraceBuilder& builder, bool stopAtNextEvent) override {
2072 builder.add(reinterpret_cast<void*>(&kj::evalLast<DummyFunctor>));
2073 }
2074 };
2075
2076 static YieldHarderPromiseNode NODE;
2077 return _::PromiseNode::to<Promise<void>>(OwnPromiseNode(&NODE));
2078 }
2079
2080 OwnPromiseNode readyNow() {
2081 class ReadyNowPromiseNode: public ImmediatePromiseNodeBase {
2082 // This is like `ConstPromiseNode<Void, Void{}>`, but the compiler won't let me pass a literal
2083 // value of type `Void` as a template parameter. (Might require C++20?)
2084
2085 public:
2086 void destroy() override {}
2087 void get(ExceptionOrValue& output) noexcept override {
2088 output.as<Void>() = Void();
2089 }
2090 };
2091
2092 static ReadyNowPromiseNode NODE;
2093 return OwnPromiseNode(&NODE);
2094 }
2095
2096 OwnPromiseNode neverDone() {
2097 class NeverDonePromiseNode final: public _::PromiseNode {
2098 public:
2099 void destroy() override {}
2100
2101 void onReady(_::Event* event) noexcept override {
2102 // ignore
2103 }
2104 void get(_::ExceptionOrValue& output) noexcept override {
2105 KJ_FAIL_REQUIRE("Not ready.");
2106 }
2107 void tracePromise(_::TraceBuilder& builder, bool stopAtNextEvent) override {
2108 builder.add(_::getMethodStartAddress(kj::NEVER_DONE, &_::NeverDone::wait));
2109 }
2110 };
2111
2112 static NeverDonePromiseNode NODE;
2113 return OwnPromiseNode(&NODE);
2114 }
2115
2116 void NeverDone::wait(WaitScope& waitScope, SourceLocation location) const {
2117 ExceptionOr<Void> dummy;
2118 waitImpl(neverDone(), dummy, waitScope, location);
2119 KJ_UNREACHABLE;
2120 }
2121
2122 void detach(kj::Promise<void>&& promise) {
2123 EventLoop& loop = currentEventLoop();
2124 KJ_REQUIRE(loop.daemons.get() != nullptr, "EventLoop is shutting down.") { return; }
2125 loop.daemons->add(kj::mv(promise));
2126 }
2127
2128 Event::Event(SourceLocation location)
2129 : loop(currentEventLoop()), next(nullptr), prev(nullptr), location(location) {}
2130
2131 Event::Event(kj::EventLoop& loop, SourceLocation location)
2132 : loop(loop), next(nullptr), prev(nullptr), location(location) {}
2133
2134 Event::~Event() noexcept(false) {
2135 live = 0;
2136
2137 // Prevent compiler from eliding this store above. This line probably isn't needed because there
2138 // are complex calls later in this destructor, and the compiler probably can't prove that they
2139 // won't come back and examine `live`, so it won't elide the write anyway. However, an
2140 // atomic_signal_fence is also sufficient to tell the compiler that a signal handler might access
2141 // `live`, so it won't optimize away the write. Note that a signal fence does not produce
2142 // any instructions, it just blocks compiler optimizations.
2143 std::atomic_signal_fence(std::memory_order_acq_rel);
2144
2145 disarm();
2146
2147 KJ_REQUIRE(!firing, "Promise callback destroyed itself.");
2148 }
2149
2150 void Event::armDepthFirst() {
2151 KJ_REQUIRE(threadLocalEventLoop == &loop || threadLocalEventLoop == nullptr,
2152 "Event armed from different thread than it was created in. You must use "
2153 "Executor to queue events cross-thread.");
2154 if (live != MAGIC_LIVE_VALUE) {
2155 ([this]() noexcept {
2156 KJ_FAIL_ASSERT("tried to arm Event after it was destroyed", location);
2157 })();
2158 }
2159
2160 if (prev == nullptr) {
2161 next = *loop.depthFirstInsertPoint;
2162 prev = loop.depthFirstInsertPoint;
2163 *prev = this;
2164 if (next != nullptr) {
2165 next->prev = &next;
2166 }
2167
2168 loop.depthFirstInsertPoint = &next;
2169
2170 if (loop.breadthFirstInsertPoint == prev) {
2171 loop.breadthFirstInsertPoint = &next;
2172 }
2173 if (loop.tail == prev) {
2174 loop.tail = &next;
2175 }
2176
2177 loop.setRunnable(true);
2178 }
2179 }
2180
2181 void Event::armBreadthFirst() {
2182 KJ_REQUIRE(threadLocalEventLoop == &loop || threadLocalEventLoop == nullptr,
2183 "Event armed from different thread than it was created in. You must use "
2184 "Executor to queue events cross-thread.");
2185 if (live != MAGIC_LIVE_VALUE) {
2186 ([this]() noexcept {
2187 KJ_FAIL_ASSERT("tried to arm Event after it was destroyed", location);
2188 })();
2189 }
2190
2191 if (prev == nullptr) {
2192 next = *loop.breadthFirstInsertPoint;
2193 prev = loop.breadthFirstInsertPoint;
2194 *prev = this;
2195 if (next != nullptr) {
2196 next->prev = &next;
2197 }
2198
2199 loop.breadthFirstInsertPoint = &next;
2200
2201 if (loop.tail == prev) {
2202 loop.tail = &next;
2203 }
2204
2205 loop.setRunnable(true);
2206 }
2207 }
2208
2209 void Event::armLast() {
2210 KJ_REQUIRE(threadLocalEventLoop == &loop || threadLocalEventLoop == nullptr,
2211 "Event armed from different thread than it was created in. You must use "
2212 "Executor to queue events cross-thread.");
2213 if (live != MAGIC_LIVE_VALUE) {
2214 ([this]() noexcept {
2215 KJ_FAIL_ASSERT("tried to arm Event after it was destroyed", location);
2216 })();
2217 }
2218
2219 if (prev == nullptr) {
2220 next = *loop.breadthFirstInsertPoint;
2221 prev = loop.breadthFirstInsertPoint;
2222 *prev = this;
2223 if (next != nullptr) {
2224 next->prev = &next;
2225 }
2226
2227 // We don't update loop.breadthFirstInsertPoint because we want further inserts to go *before*
2228 // this event.
2229
2230 if (loop.tail == prev) {
2231 loop.tail = &next;
2232 }
2233
2234 loop.setRunnable(true);
2235 }
2236 }
2237
2238 bool Event::isNext() {
2239 return loop.running && loop.head == this;
2240 }
2241
2242 void Event::disarm() {
2243 if (prev != nullptr) {
2244 if (threadLocalEventLoop != &loop && threadLocalEventLoop != nullptr) {
2245 KJ_LOG(FATAL, "Promise destroyed from a different thread than it was created in.");
2246 // There's no way out of this place without UB, so abort now.
2247 abort();
2248 }
2249
2250 if (loop.tail == &next) {
2251 loop.tail = prev;
2252 }
2253 if (loop.depthFirstInsertPoint == &next) {
2254 loop.depthFirstInsertPoint = prev;
2255 }
2256 if (loop.breadthFirstInsertPoint == &next) {
2257 loop.breadthFirstInsertPoint = prev;
2258 }
2259
2260 *prev = next;
2261 if (next != nullptr) {
2262 next->prev = prev;
2263 }
2264
2265 prev = nullptr;
2266 next = nullptr;
2267 }
2268 }
2269
2270 String Event::traceEvent() {
2271 void* space[32];
2272 TraceBuilder builder(space);
2273 traceEvent(builder);
2274 return kj::str(builder);
2275 }
2276
2277 String TraceBuilder::toString() {
2278 auto result = finish();
2279 return kj::str(stringifyStackTraceAddresses(result),
2280 stringifyStackTrace(result));
2281 }
2282
2283 } // namespace _ (private)
2284
2285 ArrayPtr<void* const> getAsyncTrace(ArrayPtr<void*> space) {
2286 EventLoop* loop = threadLocalEventLoop;
2287 if (loop == nullptr) return nullptr;
2288 if (loop->currentlyFiring == nullptr) return nullptr;
2289
2290 _::TraceBuilder builder(space);
2291 loop->currentlyFiring->traceEvent(builder);
2292 return builder.finish();
2293 }
2294
2295 kj::String getAsyncTrace() {
2296 void* space[32];
2297 auto trace = getAsyncTrace(space);
2298 return kj::str(stringifyStackTraceAddresses(trace), stringifyStackTrace(trace));
2299 }
2300
2301 // =======================================================================================
2302
2303 namespace _ { // private
2304
2305 kj::String PromiseBase::trace() {
2306 void* space[32];
2307 TraceBuilder builder(space);
2308 node->tracePromise(builder, false);
2309 return kj::str(builder);
2310 }
2311
2312 void PromiseNode::setSelfPointer(OwnPromiseNode* selfPtr) noexcept {}
2313
2314 void PromiseNode::OnReadyEvent::init(Event* newEvent) {
2315 if (event == _kJ_ALREADY_READY) {
2316 // A new continuation was added to a promise that was already ready. In this case, we schedule
2317 // breadth-first, to make it difficult for applications to accidentally starve the event loop
2318 // by repeatedly waiting on immediate promises.
2319 if (newEvent) newEvent->armBreadthFirst();
2320 } else {
2321 event = newEvent;
2322 }
2323 }
2324
2325 void PromiseNode::OnReadyEvent::arm() {
2326 KJ_ASSERT(event != _kJ_ALREADY_READY, "arm() should only be called once");
2327
2328 if (event != nullptr) {
2329 // A promise resolved and an event is already waiting on it. In this case, arm in depth-first
2330 // order so that the event runs immediately after the current one. This way, chained promises
2331 // execute together for better cache locality and lower latency.
2332 event->armDepthFirst();
2333 }
2334
2335 event = _kJ_ALREADY_READY;
2336 }
2337
2338 void PromiseNode::OnReadyEvent::armBreadthFirst() {
2339 KJ_ASSERT(event != _kJ_ALREADY_READY, "armBreadthFirst() should only be called once");
2340
2341 if (event != nullptr) {
2342 // A promise resolved and an event is already waiting on it.
2343 event->armBreadthFirst();
2344 }
2345
2346 event = _kJ_ALREADY_READY;
2347 }
2348
2349 // -------------------------------------------------------------------
2350
2351 ImmediatePromiseNodeBase::ImmediatePromiseNodeBase() {}
2352 ImmediatePromiseNodeBase::~ImmediatePromiseNodeBase() noexcept(false) {}
2353
2354 void ImmediatePromiseNodeBase::onReady(Event* event) noexcept {
2355 if (event) event->armBreadthFirst();
2356 }
2357
2358 void ImmediatePromiseNodeBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2359 // Maybe returning the address of get() will give us a function name with meaningful type
2360 // information.
2361 builder.add(getMethodStartAddress(implicitCast<PromiseNode&>(*this), &PromiseNode::get));
2362 }
2363
2364 ImmediateBrokenPromiseNode::ImmediateBrokenPromiseNode(Exception&& exception)
2365 : exception(kj::mv(exception)) {}
2366
2367 void ImmediateBrokenPromiseNode::destroy() { freePromise(this); }
2368
2369 void ImmediateBrokenPromiseNode::get(ExceptionOrValue& output) noexcept {
2370 output.exception = kj::mv(exception);
2371 }
2372
2373 // -------------------------------------------------------------------
2374
2375 AttachmentPromiseNodeBase::AttachmentPromiseNodeBase(OwnPromiseNode&& dependencyParam)
2376 : dependency(kj::mv(dependencyParam)) {
2377 dependency->setSelfPointer(&dependency);
2378 }
2379
2380 void AttachmentPromiseNodeBase::onReady(Event* event) noexcept {
2381 dependency->onReady(event);
2382 }
2383
2384 void AttachmentPromiseNodeBase::get(ExceptionOrValue& output) noexcept {
2385 dependency->get(output);
2386 }
2387
2388 void AttachmentPromiseNodeBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2389 dependency->tracePromise(builder, stopAtNextEvent);
2390
2391 // TODO(debug): Maybe use __builtin_return_address to get the locations that called fork() and
2392 // addBranch()?
2393 }
2394
2395 void AttachmentPromiseNodeBase::dropDependency() {
2396 dependency = nullptr;
2397 }
2398
2399 // -------------------------------------------------------------------
2400
2401 TransformPromiseNodeBase::TransformPromiseNodeBase(
2402 OwnPromiseNode&& dependencyParam, void* continuationTracePtr)
2403 : dependency(kj::mv(dependencyParam)), continuationTracePtr(continuationTracePtr) {
2404 dependency->setSelfPointer(&dependency);
2405 }
2406
2407 void TransformPromiseNodeBase::onReady(Event* event) noexcept {
2408 dependency->onReady(event);
2409 }
2410
2411 void TransformPromiseNodeBase::get(ExceptionOrValue& output) noexcept {
2412 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([&]() {
2413 getImpl(output);
2414 dropDependency();
2415 })) {
2416 output.addException(kj::mv(*exception));
2417 }
2418 }
2419
2420 void TransformPromiseNodeBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2421 // Note that we null out the dependency just before calling our own continuation, which
2422 // conveniently means that if we're currently executing the continuation when the trace is
2423 // requested, it won't trace into the obsolete dependency. Nice.
2424 if (dependency.get() != nullptr) {
2425 dependency->tracePromise(builder, stopAtNextEvent);
2426 }
2427
2428 builder.add(continuationTracePtr);
2429 }
2430
2431 void TransformPromiseNodeBase::dropDependency() {
2432 dependency = nullptr;
2433 }
2434
2435 void TransformPromiseNodeBase::getDepResult(ExceptionOrValue& output) {
2436 dependency->get(output);
2437 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([&]() {
2438 dependency = nullptr;
2439 })) {
2440 output.addException(kj::mv(*exception));
2441 }
2442
2443 KJ_IF_MAYBE(e, output.exception) {
2444 e->addTrace(continuationTracePtr);
2445 }
2446 }
2447
2448 // -------------------------------------------------------------------
2449
2450 ForkBranchBase::ForkBranchBase(OwnForkHubBase&& hubParam): hub(kj::mv(hubParam)) {
2451 if (hub->tailBranch == nullptr) {
2452 onReadyEvent.arm();
2453 } else {
2454 // Insert into hub's linked list of branches.
2455 prevPtr = hub->tailBranch;
2456 *prevPtr = this;
2457 next = nullptr;
2458 hub->tailBranch = &next;
2459 }
2460 }
2461
2462 ForkBranchBase::~ForkBranchBase() noexcept(false) {
2463 if (prevPtr != nullptr) {
2464 // Remove from hub's linked list of branches.
2465 *prevPtr = next;
2466 (next == nullptr ? hub->tailBranch : next->prevPtr) = prevPtr;
2467 }
2468 }
2469
2470 void ForkBranchBase::hubReady() noexcept {
2471 onReadyEvent.arm();
2472 }
2473
2474 void ForkBranchBase::releaseHub(ExceptionOrValue& output) {
2475 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([this]() {
2476 hub = nullptr;
2477 })) {
2478 output.addException(kj::mv(*exception));
2479 }
2480 }
2481
2482 void ForkBranchBase::onReady(Event* event) noexcept {
2483 onReadyEvent.init(event);
2484 }
2485
2486 void ForkBranchBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2487 if (stopAtNextEvent) return;
2488
2489 if (hub.get() != nullptr) {
2490 hub->inner->tracePromise(builder, false);
2491 }
2492
2493 // TODO(debug): Maybe use __builtin_return_address to get the locations that called fork() and
2494 // addBranch()?
2495 }
2496
2497 // -------------------------------------------------------------------
2498
2499 ForkHubBase::ForkHubBase(OwnPromiseNode&& innerParam, ExceptionOrValue& resultRef,
2500 SourceLocation location)
2501 : Event(location), inner(kj::mv(innerParam)), resultRef(resultRef) {
2502 inner->setSelfPointer(&inner);
2503 inner->onReady(this);
2504 }
2505
2506 Maybe<Own<Event>> ForkHubBase::fire() {
2507 // Dependency is ready. Fetch its result and then delete the node.
2508 inner->get(resultRef);
2509 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([this]() {
2510 inner = nullptr;
2511 })) {
2512 resultRef.addException(kj::mv(*exception));
2513 }
2514
2515 for (auto branch = headBranch; branch != nullptr; branch = branch->next) {
2516 branch->hubReady();
2517 *branch->prevPtr = nullptr;
2518 branch->prevPtr = nullptr;
2519 }
2520 *tailBranch = nullptr;
2521
2522 // Indicate that the list is no longer active.
2523 tailBranch = nullptr;
2524
2525 return nullptr;
2526 }
2527
2528 void ForkHubBase::traceEvent(TraceBuilder& builder) {
2529 if (inner.get() != nullptr) {
2530 inner->tracePromise(builder, true);
2531 }
2532
2533 if (headBranch != nullptr) {
2534 // We'll trace down the first branch, I guess.
2535 headBranch->onReadyEvent.traceEvent(builder);
2536 }
2537 }
2538
2539 // -------------------------------------------------------------------
2540
2541 ChainPromiseNode::ChainPromiseNode(OwnPromiseNode innerParam, SourceLocation location)
2542 : Event(location), state(STEP1), inner(kj::mv(innerParam)) {
2543 inner->setSelfPointer(&inner);
2544 inner->onReady(this);
2545 }
2546
2547 ChainPromiseNode::~ChainPromiseNode() noexcept(false) {}
2548
2549 void ChainPromiseNode::destroy() { freePromise(this); }
2550
2551 void ChainPromiseNode::onReady(Event* event) noexcept {
2552 switch (state) {
2553 case STEP1:
2554 onReadyEvent = event;
2555 return;
2556 case STEP2:
2557 inner->onReady(event);
2558 return;
2559 }
2560 KJ_UNREACHABLE;
2561 }
2562
2563 void ChainPromiseNode::setSelfPointer(OwnPromiseNode* selfPtr) noexcept {
2564 if (state == STEP2) {
2565 *selfPtr = kj::mv(inner); // deletes this!
2566 selfPtr->get()->setSelfPointer(selfPtr);
2567 } else {
2568 this->selfPtr = selfPtr;
2569 }
2570 }
2571
2572 void ChainPromiseNode::get(ExceptionOrValue& output) noexcept {
2573 KJ_REQUIRE(state == STEP2);
2574 return inner->get(output);
2575 }
2576
2577 void ChainPromiseNode::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2578 if (stopAtNextEvent && state == STEP1) {
2579 // In STEP1, we are an Event -- when the inner node resolves, it will arm *this* object.
2580 // In STEP2, we are not an Event -- when the inner node resolves, it directly arms our parent
2581 // event.
2582 return;
2583 }
2584
2585 inner->tracePromise(builder, stopAtNextEvent);
2586 }
2587
2588 Maybe<Own<Event>> ChainPromiseNode::fire() {
2589 KJ_REQUIRE(state != STEP2);
2590
2591 static_assert(sizeof(Promise<int>) == sizeof(PromiseBase),
2592 "This code assumes Promise<T> does not add any new members to PromiseBase.");
2593
2594 ExceptionOr<PromiseBase> intermediate;
2595 inner->get(intermediate);
2596
2597 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([this]() {
2598 inner = nullptr;
2599 })) {
2600 intermediate.addException(kj::mv(*exception));
2601 }
2602
2603 KJ_IF_MAYBE(exception, intermediate.exception) {
2604 // There is an exception. If there is also a value, delete it.
2605 kj::runCatchingExceptions([&]() { intermediate.value = nullptr; });
2606 // Now set step2 to a rejected promise.
2607 inner = allocPromise<ImmediateBrokenPromiseNode>(kj::mv(*exception));
2608 } else KJ_IF_MAYBE(value, intermediate.value) {
2609 // There is a value and no exception. The value is itself a promise. Adopt it as our
2610 // step2.
2611 inner = _::PromiseNode::from(kj::mv(*value));
2612 } else {
2613 // We can only get here if inner->get() returned neither an exception nor a
2614 // value, which never actually happens.
2615 KJ_FAIL_ASSERT("Inner node returned empty value.");
2616 }
2617 state = STEP2;
2618
2619 if (selfPtr != nullptr) {
2620 // Hey, we can shorten the chain here.
2621 auto chain = selfPtr->downcast<ChainPromiseNode>();
2622 *selfPtr = kj::mv(inner);
2623 selfPtr->get()->setSelfPointer(selfPtr);
2624 if (onReadyEvent != nullptr) {
2625 selfPtr->get()->onReady(onReadyEvent);
2626 }
2627
2628 // Return our self-pointer so that the caller takes care of deleting it.
2629 return Own<Event>(kj::Own<ChainPromiseNode>(kj::mv(chain)));
2630 } else {
2631 inner->setSelfPointer(&inner);
2632 if (onReadyEvent != nullptr) {
2633 inner->onReady(onReadyEvent);
2634 }
2635
2636 return nullptr;
2637 }
2638 }
2639
2640 void ChainPromiseNode::traceEvent(TraceBuilder& builder) {
2641 switch (state) {
2642 case STEP1:
2643 if (inner.get() != nullptr) {
2644 inner->tracePromise(builder, true);
2645 }
2646 if (!builder.full() && onReadyEvent != nullptr) {
2647 onReadyEvent->traceEvent(builder);
2648 }
2649 break;
2650 case STEP2:
2651 // This probably never happens -- a trace being generated after the meat of fire() already
2652 // executed. If it does, though, we probably can't do anything here. We don't know if
2653 // `onReadyEvent` is still valid because we passed it on to the phase-2 promise, and tracing
2654 // just `inner` would probably be confusing. Let's just do nothing.
2655 break;
2656 }
2657 }
2658
2659 // -------------------------------------------------------------------
2660
2661 ExclusiveJoinPromiseNode::ExclusiveJoinPromiseNode(
2662 OwnPromiseNode left, OwnPromiseNode right, SourceLocation location)
2663 : left(*this, kj::mv(left), location), right(*this, kj::mv(right), location) {}
2664
2665 ExclusiveJoinPromiseNode::~ExclusiveJoinPromiseNode() noexcept(false) {}
2666
2667 void ExclusiveJoinPromiseNode::destroy() { freePromise(this); }
2668
2669 void ExclusiveJoinPromiseNode::onReady(Event* event) noexcept {
2670 onReadyEvent.init(event);
2671 }
2672
2673 void ExclusiveJoinPromiseNode::get(ExceptionOrValue& output) noexcept {
2674 KJ_REQUIRE(left.get(output) || right.get(output), "get() called before ready.");
2675 }
2676
2677 void ExclusiveJoinPromiseNode::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2678 // TODO(debug): Maybe use __builtin_return_address to get the locations that called
2679 // exclusiveJoin()?
2680
2681 if (stopAtNextEvent) return;
2682
2683 // Trace the left branch I guess.
2684 if (left.dependency.get() != nullptr) {
2685 left.dependency->tracePromise(builder, false);
2686 } else if (right.dependency.get() != nullptr) {
2687 right.dependency->tracePromise(builder, false);
2688 }
2689 }
2690
2691 ExclusiveJoinPromiseNode::Branch::Branch(
2692 ExclusiveJoinPromiseNode& joinNode, OwnPromiseNode dependencyParam, SourceLocation location)
2693 : Event(location), joinNode(joinNode), dependency(kj::mv(dependencyParam)) {
2694 dependency->setSelfPointer(&dependency);
2695 dependency->onReady(this);
2696 }
2697
2698 ExclusiveJoinPromiseNode::Branch::~Branch() noexcept(false) {}
2699
2700 bool ExclusiveJoinPromiseNode::Branch::get(ExceptionOrValue& output) {
2701 if (dependency) {
2702 dependency->get(output);
2703 return true;
2704 } else {
2705 return false;
2706 }
2707 }
2708
2709 Maybe<Own<Event>> ExclusiveJoinPromiseNode::Branch::fire() {
2710 if (dependency) {
2711 // Cancel the branch that didn't return first. Ignore exceptions caused by cancellation.
2712 if (this == &joinNode.left) {
2713 kj::runCatchingExceptions([&]() { joinNode.right.dependency = nullptr; });
2714 } else {
2715 kj::runCatchingExceptions([&]() { joinNode.left.dependency = nullptr; });
2716 }
2717
2718 joinNode.onReadyEvent.arm();
2719 } else {
2720 // The other branch already fired, and this branch was canceled. It's possible for both
2721 // branches to fire if both were armed simultaneously.
2722 }
2723 return nullptr;
2724 }
2725
2726 void ExclusiveJoinPromiseNode::Branch::traceEvent(TraceBuilder& builder) {
2727 if (dependency.get() != nullptr) {
2728 dependency->tracePromise(builder, true);
2729 }
2730 joinNode.onReadyEvent.traceEvent(builder);
2731 }
2732
2733 // -------------------------------------------------------------------
2734
2735 ArrayJoinPromiseNodeBase::ArrayJoinPromiseNodeBase(
2736 Array<OwnPromiseNode> promises, ExceptionOrValue* resultParts, size_t partSize,
2737 SourceLocation location, ArrayJoinBehavior joinBehavior)
2738 : joinBehavior(joinBehavior), countLeft(promises.size()) {
2739 // Make the branches.
2740 auto builder = heapArrayBuilder<Branch>(promises.size());
2741 for (uint i: indices(promises)) {
2742 ExceptionOrValue& output = *reinterpret_cast<ExceptionOrValue*>(
2743 reinterpret_cast<byte*>(resultParts) + i * partSize);
2744 builder.add(*this, kj::mv(promises[i]), output, location);
2745 }
2746 branches = builder.finish();
2747
2748 if (branches.size() == 0) {
2749 onReadyEvent.arm();
2750 }
2751 }
2752 ArrayJoinPromiseNodeBase::~ArrayJoinPromiseNodeBase() noexcept(false) {}
2753
2754 void ArrayJoinPromiseNodeBase::onReady(Event* event) noexcept {
2755 onReadyEvent.init(event);
2756 }
2757
2758 void ArrayJoinPromiseNodeBase::get(ExceptionOrValue& output) noexcept {
2759 for (auto& branch: branches) {
2760 if (joinBehavior == ArrayJoinBehavior::LAZY) {
2761 // This implements `joinPromises()`'s lazy evaluation semantics.
2762 branch.dependency->get(branch.output);
2763 }
2764
2765 // If any of the elements threw exceptions, propagate them.
2766 KJ_IF_MAYBE(exception, branch.output.exception) {
2767 output.addException(kj::mv(*exception));
2768 }
2769 }
2770
2771 // We either failed fast, or waited for all promises.
2772 KJ_DASSERT(countLeft == 0 || output.exception != nullptr);
2773
2774 if (output.exception == nullptr) {
2775 // No errors. The template subclass will need to fill in the result.
2776 getNoError(output);
2777 }
2778 }
2779
2780 void ArrayJoinPromiseNodeBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2781 // TODO(debug): Maybe use __builtin_return_address to get the locations that called
2782 // joinPromises()?
2783
2784 if (stopAtNextEvent) return;
2785
2786 // Trace the first branch I guess.
2787 if (branches != nullptr) {
2788 branches[0].dependency->tracePromise(builder, false);
2789 }
2790 }
2791
2792 ArrayJoinPromiseNodeBase::Branch::Branch(
2793 ArrayJoinPromiseNodeBase& joinNode, OwnPromiseNode dependencyParam, ExceptionOrValue& output,
2794 SourceLocation location)
2795 : Event(location), joinNode(joinNode), dependency(kj::mv(dependencyParam)), output(output) {
2796 dependency->setSelfPointer(&dependency);
2797 dependency->onReady(this);
2798 }
2799
2800 ArrayJoinPromiseNodeBase::Branch::~Branch() noexcept(false) {}
2801
2802 Maybe<Own<Event>> ArrayJoinPromiseNodeBase::Branch::fire() {
2803 if (--joinNode.countLeft == 0 && !joinNode.armed) {
2804 joinNode.onReadyEvent.arm();
2805 joinNode.armed = true;
2806 }
2807
2808 if (joinNode.joinBehavior == ArrayJoinBehavior::EAGER) {
2809 // This implements `joinPromisesFailFast()`'s eager-evaluation semantics.
2810 dependency->get(output);
2811 if (output.exception != nullptr && !joinNode.armed) {
2812 joinNode.onReadyEvent.arm();
2813 joinNode.armed = true;
2814 }
2815 }
2816
2817 return nullptr;
2818 }
2819
2820 void ArrayJoinPromiseNodeBase::Branch::traceEvent(TraceBuilder& builder) {
2821 dependency->tracePromise(builder, true);
2822 joinNode.onReadyEvent.traceEvent(builder);
2823 }
2824
2825 ArrayJoinPromiseNode<void>::ArrayJoinPromiseNode(
2826 Array<OwnPromiseNode> promises, Array<ExceptionOr<_::Void>> resultParts,
2827 SourceLocation location, ArrayJoinBehavior joinBehavior)
2828 : ArrayJoinPromiseNodeBase(kj::mv(promises), resultParts.begin(), sizeof(ExceptionOr<_::Void>),
2829 location, joinBehavior),
2830 resultParts(kj::mv(resultParts)) {}
2831
2832 ArrayJoinPromiseNode<void>::~ArrayJoinPromiseNode() {}
2833
2834 void ArrayJoinPromiseNode<void>::destroy() { freePromise(this); }
2835
2836 void ArrayJoinPromiseNode<void>::getNoError(ExceptionOrValue& output) noexcept {
2837 output.as<_::Void>() = _::Void();
2838 }
2839
2840 } // namespace _ (private)
2841
2842 Promise<void> joinPromises(Array<Promise<void>>&& promises, SourceLocation location) {
2843 return _::PromiseNode::to<Promise<void>>(_::allocPromise<_::ArrayJoinPromiseNode<void>>(
2844 KJ_MAP(p, promises) { return _::PromiseNode::from(kj::mv(p)); },
2845 heapArray<_::ExceptionOr<_::Void>>(promises.size()), location,
2846 _::ArrayJoinBehavior::LAZY));
2847 }
2848
2849 Promise<void> joinPromisesFailFast(Array<Promise<void>>&& promises, SourceLocation location) {
2850 return _::PromiseNode::to<Promise<void>>(_::allocPromise<_::ArrayJoinPromiseNode<void>>(
2851 KJ_MAP(p, promises) { return _::PromiseNode::from(kj::mv(p)); },
2852 heapArray<_::ExceptionOr<_::Void>>(promises.size()), location,
2853 _::ArrayJoinBehavior::EAGER));
2854 }
2855
2856 namespace _ { // (private)
2857
2858 // -------------------------------------------------------------------
2859
2860 EagerPromiseNodeBase::EagerPromiseNodeBase(
2861 OwnPromiseNode&& dependencyParam, ExceptionOrValue& resultRef, SourceLocation location)
2862 : Event(location), dependency(kj::mv(dependencyParam)), resultRef(resultRef) {
2863 dependency->setSelfPointer(&dependency);
2864 dependency->onReady(this);
2865 }
2866
2867 void EagerPromiseNodeBase::onReady(Event* event) noexcept {
2868 onReadyEvent.init(event);
2869 }
2870
2871 void EagerPromiseNodeBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2872 // TODO(debug): Maybe use __builtin_return_address to get the locations that called
2873 // eagerlyEvaluate()? But note that if a non-null exception handler was passed to it, that
2874 // creates a TransformPromiseNode which will report the location anyhow.
2875
2876 if (stopAtNextEvent) return;
2877 if (dependency.get() != nullptr) {
2878 dependency->tracePromise(builder, stopAtNextEvent);
2879 }
2880 }
2881
2882 void EagerPromiseNodeBase::traceEvent(TraceBuilder& builder) {
2883 if (dependency.get() != nullptr) {
2884 dependency->tracePromise(builder, true);
2885 }
2886 onReadyEvent.traceEvent(builder);
2887 }
2888
2889 Maybe<Own<Event>> EagerPromiseNodeBase::fire() {
2890 dependency->get(resultRef);
2891 KJ_IF_MAYBE(exception, kj::runCatchingExceptions([this]() {
2892 dependency = nullptr;
2893 })) {
2894 resultRef.addException(kj::mv(*exception));
2895 }
2896
2897 onReadyEvent.arm();
2898 return nullptr;
2899 }
2900
2901 // -------------------------------------------------------------------
2902
2903 void AdapterPromiseNodeBase::onReady(Event* event) noexcept {
2904 onReadyEvent.init(event);
2905 }
2906
2907 void AdapterPromiseNodeBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
2908 // Maybe returning the address of get() will give us a function name with meaningful type
2909 // information.
2910 builder.add(getMethodStartAddress(implicitCast<PromiseNode&>(*this), &PromiseNode::get));
2911 }
2912
2913 void END_FULFILLER_STACK_START_LISTENER_STACK() {}
2914 // Dummy symbol used when reporting how a PromiseFulfiller was destroyed without fulfilling the
2915 // promise. We end up combining two stack traces into one and we use this as a separator.
2916
2917 void WeakFulfillerBase::disposeImpl(void* pointer) const {
2918 if (inner == nullptr) {
2919 // Already detached.
2920 delete this;
2921 } else {
2922 if (inner->isWaiting()) {
2923 // Let's find out if there's an exception being thrown. If so, we'll use it to reject the
2924 // promise.
2925 inner->reject(getDestructionReason(
2926 reinterpret_cast<void*>(&END_FULFILLER_STACK_START_LISTENER_STACK),
2927 kj::Exception::Type::FAILED, __FILE__, __LINE__,
2928 "PromiseFulfiller was destroyed without fulfilling the promise."_kj));
2929 }
2930 inner = nullptr;
2931 }
2932 }
2933
2934 } // namespace _ (private)
2935
2936 // -------------------------------------------------------------------
2937
2938 namespace _ { // (private)
2939
2940 Promise<void> IdentityFunc<Promise<void>>::operator()() const { return READY_NOW; }
2941
2942 } // namespace _ (private)
2943
2944 // -------------------------------------------------------------------
2945
2946 #if KJ_HAS_COROUTINE
2947
2948 namespace _ { // (private)
2949
2950 CoroutineBase::CoroutineBase(stdcoro::coroutine_handle<> coroutine, ExceptionOrValue& resultRef,
2951 SourceLocation location)
2952 : Event(location),
2953 coroutine(coroutine),
2954 resultRef(resultRef) {}
2955 CoroutineBase::~CoroutineBase() noexcept(false) {
2956 readMaybe(maybeDisposalResults)->destructorRan = true;
2957 }
2958
2959 void CoroutineBase::unhandled_exception() {
2960 // Pretty self-explanatory, we propagate the exception to the promise which owns us, unless
2961 // we're being destroyed, in which case we propagate it back to our disposer. Note that all
2962 // unhandled exceptions end up here, not just ones after the first co_await.
2963
2964 auto exception = getCaughtExceptionAsKj();
2965
2966 KJ_IF_MAYBE(disposalResults, maybeDisposalResults) {
2967 // Exception during coroutine destruction. Only record the first one.
2968 if (disposalResults->exception == nullptr) {
2969 disposalResults->exception = kj::mv(exception);
2970 }
2971 } else if (isWaiting()) {
2972 // Exception during coroutine execution.
2973 resultRef.addException(kj::mv(exception));
2974 scheduleResumption();
2975 } else {
2976 // Okay, what could this mean? We've already been fulfilled or rejected, but we aren't being
2977 // destroyed yet. The only possibility is that we are unwinding the coroutine frame due to a
2978 // successful completion, and something in the frame threw. We can't already be rejected,
2979 // because rejecting a coroutine involves throwing, which would have unwound the frame prior
2980 // to setting `waiting = false`.
2981 //
2982 // Since we know we're unwinding due to a successful completion, we also know that whatever
2983 // Event we may have armed has not yet fired, because we haven't had a chance to return to
2984 // the event loop.
2985
2986 // final_suspend() has not been called.
2987 #if _MSC_VER && !defined(__clang__)
2988 // See comment at `finalSuspendCalled`'s definition.
2989 KJ_IASSERT(!finalSuspendCalled);
2990 #else
2991 KJ_IASSERT(!coroutine.done());
2992 #endif
2993
2994 // Since final_suspend() hasn't been called, whatever Event is waiting on us has not fired,
2995 // and will see this exception.
2996 resultRef.addException(kj::mv(exception));
2997 }
2998 }
2999
3000 void CoroutineBase::onReady(Event* event) noexcept {
3001 onReadyEvent.init(event);
3002 }
3003
3004 void CoroutineBase::tracePromise(TraceBuilder& builder, bool stopAtNextEvent) {
3005 if (stopAtNextEvent) return;
3006
3007 KJ_IF_MAYBE(promise, promiseNodeForTrace) {
3008 promise->tracePromise(builder, stopAtNextEvent);
3009 }
3010
3011 // Maybe returning the address of coroutine() will give us a function name with meaningful type
3012 // information. (Narrator: It doesn't.)
3013 builder.add(GetFunctorStartAddress<>::apply(coroutine));
3014 };
3015
3016 Maybe<Own<Event>> CoroutineBase::fire() {
3017 // Call Awaiter::await_resume() and proceed with the coroutine. Note that this will not destroy
3018 // the coroutine if control flows off the end of it, because we return suspend_always() from
3019 // final_suspend().
3020 //
3021 // It's tempting to arrange to check for exceptions right now and reject the promise that owns
3022 // us without resuming the coroutine, which would save us from throwing an exception when we
3023 // already know where it's going. But, we don't really know: unlike in the KJ_NO_EXCEPTIONS
3024 // case, the `co_await` might be in a try-catch block, so we have no choice but to resume and
3025 // throw later.
3026 //
3027 // TODO(someday): If we ever support coroutines with -fno-exceptions, we'll need to reject the
3028 // enclosing coroutine promise here, if the Awaiter's result is exceptional.
3029
3030 promiseNodeForTrace = nullptr;
3031
3032 coroutine.resume();
3033
3034 return nullptr;
3035 }
3036
3037 void CoroutineBase::traceEvent(TraceBuilder& builder) {
3038 KJ_IF_MAYBE(promise, promiseNodeForTrace) {
3039 promise->tracePromise(builder, true);
3040 }
3041
3042 // Maybe returning the address of coroutine() will give us a function name with meaningful type
3043 // information. (Narrator: It doesn't.)
3044 builder.add(GetFunctorStartAddress<>::apply(coroutine));
3045
3046 onReadyEvent.traceEvent(builder);
3047 }
3048
3049 void CoroutineBase::destroy() {
3050 // Called by PromiseDisposer to delete the object. Basically a wrapper around coroutine.destroy()
3051 // with some stuff to propagate exceptions appropriately.
3052
3053 // Objects in the coroutine frame might throw from their destructors, so unhandled_exception()
3054 // will need some way to communicate those exceptions back to us. Separately, we also want
3055 // confirmation that our own ~Coroutine() destructor ran. To solve this, we put a
3056 // DisposalResults object on the stack and set a pointer to it in the Coroutine object. This
3057 // indicates to unhandled_exception() and ~Coroutine() where to store the results of the
3058 // destruction operation.
3059 DisposalResults disposalResults;
3060 maybeDisposalResults = &disposalResults;
3061
3062 // Need to save this while `unwindDetector` is still valid.
3063 bool shouldRethrow = !unwindDetector.isUnwinding();
3064
3065 do {
3066 // Clang's implementation of the Coroutines TS does not destroy the Coroutine object or
3067 // deallocate the coroutine frame if a destructor of an object on the frame threw an
3068 // exception. This is despite the fact that it delivered the exception to _us_ via
3069 // unhandled_exception(). Anyway, it appears we can work around this by running
3070 // coroutine.destroy() a second time.
3071 //
3072 // On Clang, `disposalResults.exception != nullptr` implies `!disposalResults.destructorRan`.
3073 // We could optimize out the separate `destructorRan` flag if we verify that other compilers
3074 // behave the same way.
3075 coroutine.destroy();
3076 } while (!disposalResults.destructorRan);
3077
3078 // WARNING: `this` is now a dangling pointer.
3079
3080 KJ_IF_MAYBE(exception, disposalResults.exception) {
3081 if (shouldRethrow) {
3082 kj::throwFatalException(kj::mv(*exception));
3083 } else {
3084 // An exception is already unwinding the stack, so throwing this secondary exception would
3085 // call std::terminate().
3086 }
3087 }
3088 }
3089
3090 CoroutineBase::AwaiterBase::AwaiterBase(OwnPromiseNode node): node(kj::mv(node)) {}
3091 CoroutineBase::AwaiterBase::AwaiterBase(AwaiterBase&&) = default;
3092 CoroutineBase::AwaiterBase::~AwaiterBase() noexcept(false) {
3093 // Make sure it's safe to generate an async stack trace between now and when the Coroutine is
3094 // destroyed.
3095 KJ_IF_MAYBE(coroutineEvent, maybeCoroutineEvent) {
3096 coroutineEvent->promiseNodeForTrace = nullptr;
3097 }
3098
3099 unwindDetector.catchExceptionsIfUnwinding([this]() {
3100 // No need to check for a moved-from state, node will just ignore the nullification.
3101 node = nullptr;
3102 });
3103 }
3104
3105 void CoroutineBase::AwaiterBase::getImpl(ExceptionOrValue& result, void* awaitedAt) {
3106 node->get(result);
3107
3108 KJ_IF_MAYBE(exception, result.exception) {
3109 // Manually extend the stack trace with the instruction address where the co_await occurred.
3110 exception->addTrace(awaitedAt);
3111
3112 // Pass kj::maxValue for ignoreCount here so that `throwFatalException()` dosen't try to
3113 // extend the stack trace. There's no point in extending the trace beyond the single frame we
3114 // added above, as the rest of the trace will always be async framework stuff that no one wants
3115 // to see.
3116 kj::throwFatalException(kj::mv(*exception), kj::maxValue);
3117 }
3118 }
3119
3120 bool CoroutineBase::AwaiterBase::awaitSuspendImpl(CoroutineBase& coroutineEvent) {
3121 node->setSelfPointer(&node);
3122 node->onReady(&coroutineEvent);
3123
3124 if (coroutineEvent.hasSuspendedAtLeastOnce && coroutineEvent.isNext()) {
3125 // The result is immediately ready and this coroutine is running on the event loop's stack, not
3126 // a user code stack. Let's cancel our event and immediately resume. It's important that we
3127 // don't perform this optimization if this is the first suspension, because our caller may
3128 // depend on running code before this promise's continuations fire.
3129 coroutineEvent.disarm();
3130
3131 // We can resume ourselves by returning false. This accomplishes the same thing as if we had
3132 // returned true from await_ready().
3133 return false;
3134 } else {
3135 // Otherwise, we must suspend. Store a reference to the promise we're waiting on for tracing
3136 // purposes; coroutineEvent.fire() and/or ~Adapter() will null this out.
3137 coroutineEvent.promiseNodeForTrace = *node;
3138 maybeCoroutineEvent = coroutineEvent;
3139
3140 coroutineEvent.hasSuspendedAtLeastOnce = true;
3141
3142 return true;
3143 }
3144 }
3145
3146 // ---------------------------------------------------------
3147 // Helpers for coCapture()
3148
3149 void throwMultipleCoCaptureInvocations() {
3150 KJ_FAIL_REQUIRE("Attempted to invoke CaptureForCoroutine functor multiple times");
3151 }
3152
3153 } // namespace _ (private)
3154
3155 #endif // KJ_HAS_COROUTINE
3156
3157 } // namespace kj