path: root/DESIGN
diff options
authorTimo Teräs <>2010-07-02 20:23:07 +0300
committerTimo Teräs <>2010-07-02 20:25:47 +0300
commit23b95bf1a15322c2f471b80c06cb65d9b2d2a282 (patch)
tree9bf12231db9591852e3b42ca24715d2cbaf6267b /DESIGN
parent0183e33d9a4759764716e771b85e19f7a997b8bd (diff)
libtf: major redesign startedHEADmaster
the idea is to make libtf completely multi-threaded. meaning each fiber can be running concurrently in separate thread. quite a bit of framework is added for this and some atomic helpers are already introduced. however, io polling is busy polling now (will be soon in own thread) and timeouts are still more or less broken. oh, and the multithreading core is not there yet. basically we are currently mostly broken ;)
Diffstat (limited to 'DESIGN')
1 files changed, 65 insertions, 12 deletions
diff --git a/DESIGN b/DESIGN
index 2ffc535..8624446 100644
--- a/DESIGN
+++ b/DESIGN
@@ -1,19 +1,72 @@
-- 4-heap (or 2-heap) with linked nodes
-- epoll
-- edge-triggered monitoring for file i/o (no syscalls to modify fdset)
+- worker thread pool executes read to be run fibers
+- thread pool executes fibers from FIFO queues (one per each priority)
+- possible to make main thread separate scheduler so we can bind some
+ fibers to run in main thread only (not needed?)
+THE BIG SCHEDULING QUEUE (shared queue with all worker threads)
+ --- works also between machines, in which case we just always queue
+ work items to remote vmach (need to send wakeups too)
+ - steal first item from the local cache if any
+ - mutex lock
+ - if stuff to push
+ - while idle_vcpu not empty
+ - pop idle_vcpu from list
+ - push item to idle_vcpu
+ - push rest of items to global lists accordingly
+ - mutex unlock
+ - call futex_wake for all idle_cpu's we stuffed
+ - return stolen item
+ - if stuff on list
+ - pop item from list
+ - mutex unlock
+ - return popped_item
+ - insert self to idle_vcpu list
+ - mutex unlock
+ - futex_wait on local_pointer
+ - return local_pointer
+ - mutex unlock
+ - as minimum keep wakeup bitfield for most common types, and use
+ prepare sleep, and sleep primitives with acceptable wakeup reasons
+ - might add so that wakupper calls wakeupee to execute their wakeup
+ condition check once ask rescheduling based or that or not; this way
+ empty spin does not require pushing to scheduler queue and thread
+ pool wakeup
+- epoll in edge-triggered monitoring for file i/o
+- epoll_wait done in separate thread (or possibly as regular fiber)
+ which sole purpose is to wakeup threads for thread pool
- signalfd for signal handling
-- eventfd for thread pool wakeup
+- timerfd for timeout handling
+- sends a callback to be execute under some other fibre
+- executed at tf_ifc_process() points, or at tf_exit() time
+- might need tfc_ifc_wait() for synchronizing with ifc completion
+- sending uses atomic LIFO (single atomic cmpxchg)
+- receive does LIFO flush (single atomic xchg) and reverses order(?)
+- need way to check if IFC is queued or not (so it's safe to reuse it)
+- one (or more) fibers serving as alarm generators
+- 4-heap with mremappable heap array
+- receives IFC calls from other threads
+- receives io wakeups from timerfd
+- sends async signal to fiber after timeout
-- timer node on fiber control data (for delayed heapify; and reuse on timeouts)
- fd, signal, pid wait struct on stack of wait function
- fiber_kill can interrupt wait
-- scheduler queues to thread pool array fifo queue,
- - semaphore protects threads so no underqueueing happens
- - eventfd notifies scheduler when queue has free space again
- - head/tail updated atomically and item position recovered
-- thread pool atomically pushes to resume atomic stack and sets eventfd
- - scheduler thread atomically pops all and updates fiber states
+- mostly not needed (alarms, io uses async signal wakeups)
+- for mutex, semaphores, possibly send io
+- use thread mutexes for list access
+- wait on single queue only(?)
+- simple wakeup queue, sleep on queue, uninterruptible?