Line data Source code
1 : #ifndef HEADER_fd_src_disco_sleep_fd_sleep_h
2 : #define HEADER_fd_src_disco_sleep_fd_sleep_h
3 :
4 : /* Idle tiles park in futex_wait instead of spinning and are woken
5 : when work arrives. Three roles share one shmem region:
6 :
7 : sleeper a stem tile with no work: flushes its link state, sets
8 : its bit in parked_bits, re-checks its ins once under the
9 : RMW fence, then FUTEX_WAIT_BITSETs on its word, timed
10 : only if a deadline is due before the park cap (the sweep
11 : enforces the cap).
12 :
13 : producer on publish: load parked_bits[w] & a mask precomputed at
14 : boot; if nonzero, locked OR into doorbell[w].
15 :
16 : mwaitx naps in hardware on the doorbell line (umwait/mwaitx),
17 : turns rung bits into FUTEX_WAKEs, and runs the verifying
18 : sweep (seq_mirror vs seq_snap) that bounds a lost
19 : doorbell to one nap. The only FUTEX_WAKE issuer.
20 :
21 : word 0 = parked, nonzero = running (the value says why). The
22 : doorbell is a hint: truth is level triggered (seqs, deadline) and
23 : re-checked on every wake, so spurious wakes are absorbed and a lost
24 : hint costs only bounded latency (the sweep, then the tile's own
25 : deadline).
26 :
27 : A tile with its own kernel fds (tile->sleep_eventfd) parks in epoll
28 : instead, with an eventfd doorbell at FD_SLEEP_EVENTFD( id ) that
29 : mwaitx writes in place of FUTEX_WAKE. */
30 :
31 : #include "../../util/fd_util_base.h"
32 :
33 0 : #define FD_SLEEP_ALIGN (128UL)
34 0 : #define FD_SLEEP_MAGIC (0xf17eda2c3751ee90UL) /* firedancer sleep ver 0 */
35 :
36 0 : #define FD_SLEEP_TILE_MAX ( 512UL)
37 0 : #define FD_SLEEP_BITS_CNT (FD_SLEEP_TILE_MAX/64UL)
38 : #define FD_SLEEP_LINK_MAX (1024UL) /* ==FD_TOPO_MAX_LINKS */
39 : #define FD_SLEEP_IN_MAX ( 256UL) /* ==FD_TOPO_MAX_TILE_IN_LINKS */
40 : #define FD_SLEEP_OUT_MAX ( 64UL) /* ==FD_TOPO_MAX_TILE_OUT_LINKS */
41 :
42 0 : #define FD_SLEEP_LINGER_NS (0L) /* park as soon as caught up */
43 0 : #define FD_SLEEP_PARK_CAP_NS (20000000L) /* longest park */
44 0 : #define FD_SLEEP_PARK_MIN_NS (5000L) /* shorter than this and the futex round trip costs more than the spin */
45 :
46 : /* Inherited fd number of a tile's eventfd doorbell */
47 0 : #define FD_SLEEP_EVENTFD_BASE (123600)
48 0 : #define FD_SLEEP_EVENTFD( id ) (FD_SLEEP_EVENTFD_BASE+(int)(id))
49 :
50 : /* epoll data of the eventfd doorbell in a tile's park set */
51 0 : #define FD_SLEEP_EPOLL_DOORBELL (ULONG_MAX)
52 :
53 : struct __attribute__((aligned(FD_SLEEP_ALIGN))) fd_sleep_private {
54 : /* Loaded on every publish, written only at park/unpark */
55 : ulong parked_bits[ FD_SLEEP_BITS_CNT ];
56 : ulong magic; /* ==FD_SLEEP_MAGIC, off the parked_bits line */
57 : double tick_per_ns; /* fd_tickcount ticks per ns, for futex deadlines */
58 : ulong pad0[ 6 ];
59 :
60 : /* Locked OR on wake edges; the line mwaitx monitors. Own line. */
61 : ulong doorbell[ FD_SLEEP_BITS_CNT ];
62 : ulong pad1[ 8 ];
63 :
64 : /* Subset of parked_bits: tiles parked on backpressure, which only a
65 : consumer's credit return can wake. Loaded on every credit return. */
66 : ulong credit_bits[ FD_SLEEP_BITS_CNT ];
67 : ulong pad2[ 8 ];
68 :
69 : /* Indexed by tile->id; written by the owner and mwaitx only */
70 : struct __attribute__((aligned(64UL))) {
71 : ulong word; /* futex word: 0 parked, 1 running */
72 : ulong pad0;
73 : ulong deadline; /* abs fd_tickcount of the next timed obligation */
74 : ulong pad[ 5 ];
75 : } tile[ FD_SLEEP_TILE_MAX ];
76 :
77 : /* Sweep state: producers mirror out seqs at housekeeping, a parking
78 : tile snapshots the next seq it expects per polled in.
79 : mirror[link]>snap means a frag is pending. */
80 : ulong seq_mirror[ FD_SLEEP_LINK_MAX ];
81 : ulong seq_snap[ FD_SLEEP_TILE_MAX ][ FD_SLEEP_IN_MAX ];
82 : };
83 :
84 : typedef struct fd_sleep_private fd_sleep_t;
85 :
86 : /* Wake table entry: the consumers of one out link as a (bitmap word,
87 : mask) pair. One pair per link in practice. */
88 :
89 : struct fd_sleep_wake {
90 : ulong w;
91 : ulong mask;
92 : };
93 :
94 : typedef struct fd_sleep_wake fd_sleep_wake_t;
95 :
96 : struct fd_topo;
97 :
98 : FD_PROTOTYPES_BEGIN
99 :
100 : FD_FN_CONST ulong fd_sleep_align ( void );
101 : FD_FN_CONST ulong fd_sleep_footprint( void );
102 :
103 : /* fd_sleep_new formats shmem (fd_sleep_align aligned, fd_sleep_footprint
104 : bytes) as a sleep region with every tile running. tick_per_ns is
105 : the fd_tickcount rate used to turn park deadlines into futex
106 : timeouts. Returns shmem on success, NULL on failure (logs
107 : details). */
108 :
109 : void * fd_sleep_new( void * shmem,
110 : double tick_per_ns );
111 :
112 : fd_sleep_t * fd_sleep_join( void * shsleep );
113 :
114 : /* fd_sleep_wake_table fills wake (FD_SLEEP_BITS_CNT entries) with the
115 : (word,mask) pairs covering every tile that polls link_id, and
116 : returns the pair count (0 if none, or in performance mode). A
117 : consumer that never parks never has its bit set, so rings to it are
118 : free. */
119 :
120 : ulong
121 : fd_sleep_wake_table( fd_sleep_wake_t * wake,
122 : struct fd_topo const * topo,
123 : ulong link_id );
124 :
125 : /* fd_sleep_ring marks tile_id as having work. Safe from any thread;
126 : ringing a running tile is harmless. */
127 :
128 : static inline void
129 : fd_sleep_ring( fd_sleep_t * sleep,
130 0 : ulong tile_id ) {
131 0 : __atomic_fetch_or( &sleep->doorbell[ tile_id>>6 ], 1UL<<(tile_id&63UL), __ATOMIC_RELEASE );
132 0 : }
133 :
134 : /* fd_sleep_wake_check rings the parked consumers of one out link,
135 : except those parked on backpressure (credit_bits): a frag cannot
136 : help them, only a credit return can. One load per pair; the
137 : second load and the locked OR only on a hit. */
138 :
139 : static inline void
140 : fd_sleep_wake_check( fd_sleep_t * sleep,
141 : fd_sleep_wake_t const * wake,
142 0 : ulong wake_cnt ) {
143 0 : for( ulong k=0UL; k<wake_cnt; k++ ) {
144 0 : ulong rung = FD_VOLATILE_CONST( sleep->parked_bits[ wake[ k ].w ] ) & wake[ k ].mask;
145 0 : if( FD_UNLIKELY( rung ) ) {
146 0 : rung &= ~FD_VOLATILE_CONST( sleep->credit_bits[ wake[ k ].w ] );
147 0 : if( FD_LIKELY( rung ) ) __atomic_fetch_or( &sleep->doorbell[ wake[ k ].w ], rung, __ATOMIC_RELEASE );
148 0 : }
149 0 : }
150 0 : }
151 :
152 : /* Unpark causes, in ParkWake metrics enum order */
153 :
154 0 : #define FD_SLEEP_UNPARK_RING (0)
155 0 : #define FD_SLEEP_UNPARK_DEADLINE (1)
156 : #define FD_SLEEP_UNPARK_PENDING (2)
157 :
158 : /* FD_SLEEP_WORD( cause ) is what a wake stores in the word: nonzero
159 : and distinct per cause */
160 :
161 0 : #define FD_SLEEP_WORD( cause ) (1UL+(ulong)(cause))
162 :
163 : /* fd_sleep_park_wait blocks on word until woken or deadline_ticks
164 : passes (LONG_MAX: no timer, the mwaitx sweep must end the park).
165 : Returns FD_SLEEP_UNPARK_RING or FD_SLEEP_UNPARK_DEADLINE. */
166 :
167 : int
168 : fd_sleep_park_wait( ulong * word,
169 : long deadline_ticks,
170 : double tick_per_ns );
171 :
172 : /* fd_sleep_wake_one wakes the tile parked on word for cause. */
173 :
174 : void
175 : fd_sleep_wake_one( ulong * word,
176 : int cause );
177 :
178 : /* fd_sleep_wake_eventfd is fd_sleep_wake_one for a tile parked in
179 : fd_sleep_park_wait_epoll. */
180 :
181 : void
182 : fd_sleep_wake_eventfd( ulong * word,
183 : int eventfd,
184 : int cause );
185 :
186 : /* fd_sleep_park_wait_epoll is fd_sleep_park_wait for a tile with its
187 : own fds. Blocks in epoll_pwait on epfd until an fd is ready, a wake,
188 : or the deadline. Ready events are returned in evs / *ev_cnt. epfd
189 : must hold the tile's eventfd doorbell registered EPOLLIN|EPOLLET
190 : with data FD_SLEEP_EPOLL_DOORBELL, and the caller must never read
191 : it: a stale doorbell (word still 0) is waited through, which relies
192 : on the edge being consumed by the wait. */
193 :
194 : struct epoll_event;
195 :
196 : int
197 : fd_sleep_park_wait_epoll( int epfd,
198 : ulong const * word,
199 : struct epoll_event * evs,
200 : int ev_max,
201 : int * ev_cnt,
202 : long deadline_ticks,
203 : double tick_per_ns );
204 :
205 : /* fd_sleep_eventfd_install creates the eventfd doorbell of every
206 : sleep_eventfd tile at FD_SLEEP_EVENTFD( tile->id ). */
207 :
208 : void
209 : fd_sleep_eventfd_install( struct fd_topo const * topo );
210 :
211 : FD_PROTOTYPES_END
212 :
213 : #endif /* HEADER_fd_src_disco_sleep_fd_sleep_h */
|
