1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
//! The order a shard takes its runnables in (see the module docs of
//! `shard`): the LIFO slot, the local queue, then the work other threads
//! handed it, the inbox's and the home's.
//!
//! Every `tuning.inbox_interval` runs the remote work comes first, so a busy
//! local queue does not starve it; every other such run the home's comes
//! before the inbox's, so neither starves the other: a home looked at only
//! when the inbox is empty never runs while other threads keep the inbox
//! full. `proofs/tla/sched/Sched.tla` checks that every place that holds
//! work is served within a bound of runs. The interval's turn is out of
//! line, so the runs between pay nothing for it.
use super::Shard;
use crate::rt::inbox::Pop;
use crate::rt::task::Runnable;
impl Shard {
/// The next runnable, in the loop's order.
#[inline(always)]
pub(super) fn next(&self) -> Option<Runnable> {
let left = self.until_inbox.get().wrapping_sub(1);
if left == 0 {
return self.interval_turn();
}
self.until_inbox.set(left);
self.next_local()
}
/// The interval's turn: the remote work first, else the rest of the order.
#[cold]
#[inline(never)]
fn interval_turn(&self) -> Option<Runnable> {
self.until_inbox.set(self.tuning.inbox_interval);
if let Some(r) = self.pop_remote() {
return Some(r);
}
self.next_local()
}
/// The slot, the local queue, then the inbox and the home.
#[inline(always)]
fn next_local(&self) -> Option<Runnable> {
if let Some(r) = self.lifo.take() {
if self.lifo_streak.get() < super::LIFO_MAX {
self.lifo_streak.set(self.lifo_streak.get() + 1);
return Some(r);
}
// The slot's task ran enough times in a row: to the back, which
// is the front when nothing else is queued.
let mut queue = self.queue.borrow_mut();
if queue.is_empty() {
self.lifo_streak.set(0);
return Some(r);
}
queue.push_back(r);
}
self.lifo_streak.set(0);
let local = self.queue.borrow_mut().pop_front();
// A match, not `or_else`: a closure's call can stay out of line, which every run that
// finds the local queue empty would pay.
match local {
Some(r) => Some(r),
None => self.pop_inbox(),
}
}
/// The interval's look at the remote work: the inbox first, or every
/// other time the home first.
#[inline(always)]
fn pop_remote(&self) -> Option<Runnable> {
let homes_first = !self.homes_first.get();
self.homes_first.set(homes_first);
if !homes_first {
return self.pop_inbox();
}
if let Some(runnable) = self.pop_home() {
self.remote_wakes.set(self.remote_wakes.get() + 1);
return Some(runnable);
}
// The home was just looked at: the inbox does not look again.
self.pop_inbox_only()
}
// Inlined into the run loop's `next`, whichever codegen unit holds it: it is looked at on
// every run that finds the local queue empty.
#[inline(always)]
pub(super) fn pop_inbox(&self) -> Option<Runnable> {
// SAFETY: the shard holds the inbox's taker's role until it goes
// (`stop` lets go of it, last).
self.counted(match unsafe { self.shared.inbox.pop() } {
Pop::Item(runnable) => Some(runnable),
// A push under way counts as work: the loop comes back. Then the
// bound tasks of the thread that runs the shard.
Pop::Empty | Pop::Busy => self.pop_home(),
})
}
/// The inbox alone, for a turn that has just looked at the home.
#[inline(always)]
fn pop_inbox_only(&self) -> Option<Runnable> {
// SAFETY: as in `pop_inbox`.
self.counted(match unsafe { self.shared.inbox.pop() } {
Pop::Item(runnable) => Some(runnable),
Pop::Empty | Pop::Busy => None,
})
}
/// A remote wake counted when `popped` is one.
#[inline(always)]
fn counted(&self, popped: Option<Runnable>) -> Option<Runnable> {
let runnable = popped?;
self.remote_wakes.set(self.remote_wakes.get() + 1);
Some(runnable)
}
/// A bound task of the thread that runs the shard: a runner's, or the
/// ones of this shard, a thread's own.
#[inline(always)]
fn pop_home(&self) -> Option<Runnable> {
crate::rt::context::pop_home().or_else(|| {
// SAFETY: an own shard runs on its thread only, its home's.
self.home.get().and_then(|home| unsafe { home.pop() })
})
}
}