Repository navigation
-
A task now returns its continuation, and with it its stack, to the continuation pool as soon as it finishes, instead of keeping it until execution teardown, so a task spawned later in the same execution reuses it. The stack memory an execution uses therefore grows with the number of tasks alive at the same time rather than with the number of tasks it has ever spawned, which is what made long-running, spawn-heavy executions impractical. Spawning and joining 30,000 threads one after the other in a single execution went from 152 MB resident and 1.9 GB of mapped stacks to 29 MB and 42 MB (release build, without vector clocks, Linux x86-64). Before this change the same program could not get much further: at 33,000 threads it ran out of memory mappings (each stack takes two, and Linux allows 65,530 by default), and the test died in
DefaultStack::newwithCannot allocate memory. It now reaches 50,000 threads at 47 MB.A task gives up only what it cannot use again once it has finished: its stack, and any backtrace captured while it was blocked. Everything whose destructor runs user code — its spans, its tag and its task-local values — is still dropped by execution teardown, as the task, exactly as before, so nothing of the user's runs any earlier than it used to and a finished task's
stepspan still closes at the end of the execution. Everything that can be asked about a finished task is unchanged. Each finished task still keeps its record until the execution ends, which under thevector-clocksfeature includes its clock, so a spawn-heavy execution is still quadratic in memory with that feature on. -
Fix a thread spawned with
thread::Builder::stack_sizesometimes running on, and overflowing, a smaller stack than it asked for. The pool reused whichever continuation came first, whatever stack size it had been created with, so a thread could be handed a smaller stack that another task had freed — for instance when threads with different stack sizes were spawned in a different order than in a previous execution, since the pool outlives each execution. The pool now reuses the smallest continuation whose stack is at least as large as the one requested. Reusing stacks within an execution, as above, would have made this much easier to hit. Taking the smallest rather than the first that fits also keeps the pool from growing: handing a large stack to a task that asked for a small one would leave the next large request with nothing to reuse, so the pool would accumulate more large stacks than the execution ever needs at once. -
Performance: a thread exiting no longer looks at every task the execution has created, only at the unfinished ones, so its cost no longer grows with the number of threads that finished before it. Together with the stack reuse above, spawning and joining 30,000 threads one after the other in a single execution takes 0.05 s instead of 0.67 s.
-
Take a scheduling point before an
Acquireof aBatchSemaphorethat is dropped before it completes leaves the semaphore, when it is queued or holds the reservation. Such anAcquireis still visible to other tasks: a release grants it permits ahead of later requests on a strictly fair semaphore, and on an unfair one no other request can take a permit while it holds the reservation. The drop ran in the same step as the task's previous operation, so Shuttle missed the interleavings in which a release or atry_acquiresees theAcquirestill there. This happens whenever aselect!, a timeout or an abort cancels a blocked acquire, including the tokio wrapper'sSemaphoreacquires and its bounded mpscsendandreserve. Addruntime::thread::switch_if_not_stopping, and makeBatchSemaphore::release_no_scheduling_pointpublic, for primitives whose release is part of an operation that has already taken its scheduling point. (#412, #407) -
shuttle-tokio: add the scheduling points that were missing fromNotify,mpsc,oneshot,watchandOnceCell(#262). In each of the operations below, the access to the primitive's state ran in the same step as the task's previous operation, so Shuttle never ran another task between the two and missed the bugs that need such an interleaving; for example, a waiter that readtruefrom a flag that the notifier stored right beforenotify_onealways found a permit stored. Each now takes one scheduling point before the access:Notify:notify_one,notify_waiters,enable(), apollof aNotifiedthat does not follow a wake-up, and the drop of aNotifiedthat has not completed.Notifynow wakes its waiters through thefuturesoneshot directly, so it takes no further scheduling points inside these. (#404, #410)mpsc:UnboundedSender::send,Permit::sendandOwnedPermit::send, and the drop of the last sender. Each send now pushes its message and releases the receiver's permit in the same step: before, a receiver could run between the two, see the message inlen()and getEmptyfromtry_recv(). The drop of the last sender now closes the channel in the same step as it drops the sender count to zero, sois_closed()returnstrueoncerecvhas returnedNone, and it no longer panics when the sender is dropped outside of an execution. The number of scheduling points per operation stays the same. (#407)oneshot:Receiver::poll(before the poll, not after aReadyone),Sender::closed,Sender::poll_closed, the drop of aSenderthat did not send and the drop of aReceiver. (#410)watch:Sender::send,Sender::subscribe, the drops of the lastSenderand of the lastReceiver, and the reads ofchanged,wait_forandSender::closedafter they register for a notification. (#411)OnceCell: the store of the value that the initializer ofget_or_initorget_or_try_initreturns. (#413)
The drops skip their scheduling point outside of an execution and after the execution stops. Query methods such as
is_closed,len,receiver_countandhas_changedstill take none. These scheduling points add schedules to explore, so exhaustive tests of code that uses these primitives can take longer. The drop of aNotifiedthatnotify_onepicked now also passes the notification on while its task unwinds a caught panic. -
Publish
shuttle0.9.10,shuttle-engine0.1.8 andshuttle-tokio-impl-inner0.1.7.shuttle-tokio-impl-innerrequiresshuttle-engine0.1.8, forswitch_if_not_stoppingand the publicrelease_no_scheduling_point, andshuttlerequires it for the fixes above.shuttle-std0.1.5 andshuttle-schedulers0.1.1 are unchanged; they takeshuttle-engineas^0.1.7and^0.1.1, so they build against 0.1.8 as they stand. The already-publishedshuttle-tokio-impl0.1.2 andshuttle-tokio1.0.0 require inner as^0.1.5and re-export it with a glob, so they pick up the fixes without being republished.