Context Navigation

io.cfa@ 2fafe7e

Visit:

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum

Last change on this file since 2fafe7e was 2fafe7e, checked in by Thierry Delisle <tdelisle@…>, 5 years ago
Changed eager submit to use a leader-lock rather than a regular spinlock to avoid unnecessary spinnig
Property mode set to `100644`
File size: 15.9 KB

Line
1	//
2	// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo
3	//
4	// The contents of this file are covered under the licence agreement in the
5	// file "LICENCE" distributed with Cforall.
6	//
7	// io.cfa --
8	//
9	// Author : Thierry Delisle
10	// Created On : Thu Apr 23 17:31:00 2020
11	// Last Modified By :
12	// Last Modified On :
13	// Update Count :
14	//
15
16	#define __cforall_thread__
17
18	#if defined(__CFA_DEBUG__)
19	// #define __CFA_DEBUG_PRINT_IO__
20	// #define __CFA_DEBUG_PRINT_IO_CORE__
21	#endif
22
23
24	#if defined(CFA_HAVE_LINUX_IO_URING_H)
25	#define _GNU_SOURCE /* See feature_test_macros(7) */
26	#include <errno.h>
27	#include <signal.h>
28	#include <stdint.h>
29	#include <string.h>
30	#include <unistd.h>
31
32	extern "C" {
33	#include <sys/epoll.h>
34	#include <sys/syscall.h>
35
36	#include <linux/io_uring.h>
37	}
38
39	#include "stats.hfa"
40	#include "kernel.hfa"
41	#include "kernel/fwd.hfa"
42	#include "io/types.hfa"
43
44	// returns true of acquired as leader or second leader
45	static inline bool try_lock( __leaderlock_t & this ) {
46	const uintptr_t thrd = 1z \| (uintptr_t)active_thread();
47	bool block;
48	disable_interrupts();
49	for() {
50	struct $thread * expected = this.value;
51	if( 1p != expected && 0p != expected ) {
52	/* paranoid */ verify( thrd != (uintptr_t)expected ); // We better not already be the next leader
53	enable_interrupts( __cfaabi_dbg_ctx );
54	return false;
55	}
56	struct $thread * desired;
57	if( 0p == expected ) {
58	// If the lock isn't locked acquire it, no need to block
59	desired = 1p;
60	block = false;
61	}
62	else {
63	// If the lock is already locked try becomming the next leader
64	desired = (struct $thread *)thrd;
65	block = true;
66	}
67	if( __atomic_compare_exchange_n(&this.value, &expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ) break;
68	}
69	if( block ) {
70	enable_interrupts( __cfaabi_dbg_ctx );
71	park( __cfaabi_dbg_ctx );
72	disable_interrupts();
73	}
74	return true;
75	}
76
77	static inline bool next( __leaderlock_t & this ) {
78	/* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
79	struct $thread * nextt;
80	for() {
81	struct $thread * expected = this.value;
82	/* paranoid */ verify( (1 & (uintptr_t)expected) == 1 ); // The lock better be locked
83
84	struct $thread * desired;
85	if( 1p == expected ) {
86	// No next leader, just unlock
87	desired = 0p;
88	nextt = 0p;
89	}
90	else {
91	// There is a next leader, remove but keep locked
92	desired = 1p;
93	nextt = (struct $thread *)(~1z & (uintptr_t)expected);
94	}
95	if( __atomic_compare_exchange_n(&this.value, &expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ) break;
96	}
97
98	if(nextt) {
99	unpark( nextt __cfaabi_dbg_ctx2 );
100	enable_interrupts( __cfaabi_dbg_ctx );
101	return true;
102	}
103	enable_interrupts( __cfaabi_dbg_ctx );
104	return false;
105	}
106
107	//=============================================================================================
108	// I/O Syscall
109	//=============================================================================================
110	static int __io_uring_enter( struct __io_data & ring, unsigned to_submit, bool get ) {
111	bool need_sys_to_submit = false;
112	bool need_sys_to_complete = false;
113	unsigned flags = 0;
114
115	TO_SUBMIT:
116	if( to_submit > 0 ) {
117	if( !(ring.ring_flags & IORING_SETUP_SQPOLL) ) {
118	need_sys_to_submit = true;
119	break TO_SUBMIT;
120	}
121	if( (*ring.submit_q.flags) & IORING_SQ_NEED_WAKEUP ) {
122	need_sys_to_submit = true;
123	flags \|= IORING_ENTER_SQ_WAKEUP;
124	}
125	}
126
127	if( get && !(ring.ring_flags & IORING_SETUP_SQPOLL) ) {
128	flags \|= IORING_ENTER_GETEVENTS;
129	if( (ring.ring_flags & IORING_SETUP_IOPOLL) ) {
130	need_sys_to_complete = true;
131	}
132	}
133
134	int ret = 0;
135	if( need_sys_to_submit \|\| need_sys_to_complete ) {
136	ret = syscall( __NR_io_uring_enter, ring.fd, to_submit, 0, flags, 0p, _NSIG / 8);
137	if( ret < 0 ) {
138	switch((int)errno) {
139	case EAGAIN:
140	case EINTR:
141	ret = -1;
142	break;
143	default:
144	abort( "KERNEL ERROR: IO_URING SYSCALL - (%d) %s\n", (int)errno, strerror(errno) );
145	}
146	}
147	}
148
149	// Memory barrier
150	__atomic_thread_fence( __ATOMIC_SEQ_CST );
151	return ret;
152	}
153
154	//=============================================================================================
155	// I/O Polling
156	//=============================================================================================
157	static unsigned __collect_submitions( struct __io_data & ring );
158	static __u32 __release_consumed_submission( struct __io_data & ring );
159
160	static inline void process(struct io_uring_cqe & cqe ) {
161	struct __io_user_data_t * data = (struct __io_user_data_t *)(uintptr_t)cqe.user_data;
162	__cfadbg_print_safe( io, "Kernel I/O : Syscall completed : cqe %p, result %d for %p\n", data, cqe.res, data->thrd );
163
164	data->result = cqe.res;
165	post( data->sem );
166	}
167
168	// Process a single completion message from the io_uring
169	// This is NOT thread-safe
170	static [int, bool] __drain_io( & struct __io_data ring ) {
171	/* paranoid */ verify( !kernelTLS.preemption_state.enabled );
172
173	unsigned to_submit = 0;
174	if( ring.poller_submits ) {
175	// If the poller thread also submits, then we need to aggregate the submissions which are ready
176	to_submit = __collect_submitions( ring );
177	}
178
179	int ret = __io_uring_enter(ring, to_submit, true);
180	if( ret < 0 ) {
181	return [0, true];
182	}
183
184	// update statistics
185	if (to_submit > 0) {
186	__STATS__( true,
187	if( to_submit > 0 ) {
188	io.submit_q.submit_avg.rdy += to_submit;
189	io.submit_q.submit_avg.csm += ret;
190	io.submit_q.submit_avg.cnt += 1;
191	}
192	)
193	}
194
195	// Release the consumed SQEs
196	__release_consumed_submission( ring );
197
198	// Drain the queue
199	unsigned head = *ring.completion_q.head;
200	unsigned tail = *ring.completion_q.tail;
201	const __u32 mask = *ring.completion_q.mask;
202
203	// Nothing was new return 0
204	if (head == tail) {
205	return [0, to_submit > 0];
206	}
207
208	__u32 count = tail - head;
209	/* paranoid */ verify( count != 0 );
210	for(i; count) {
211	unsigned idx = (head + i) & mask;
212	struct io_uring_cqe & cqe = ring.completion_q.cqes[idx];
213
214	/* paranoid */ verify(&cqe);
215
216	process( cqe );
217	}
218
219	// Mark to the kernel that the cqe has been seen
220	// Ensure that the kernel only sees the new value of the head index after the CQEs have been read.
221	__atomic_thread_fence( __ATOMIC_SEQ_CST );
222	__atomic_fetch_add( ring.completion_q.head, count, __ATOMIC_RELAXED );
223
224	return [count, count > 0 \|\| to_submit > 0];
225	}
226
227	void main( $io_ctx_thread & this ) {
228	epoll_event ev;
229	__ioctx_register( this, ev );
230
231	__cfadbg_print_safe(io_core, "Kernel I/O : IO poller %p for ring %p ready\n", &this, &this.ring);
232
233	int reset = 0;
234	// Then loop until we need to start
235	while(!__atomic_load_n(&this.done, __ATOMIC_SEQ_CST)) {
236	// Drain the io
237	int count;
238	bool again;
239	disable_interrupts();
240	[count, again] = __drain_io( *this.ring );
241
242	if(!again) reset++;
243
244	// Update statistics
245	__STATS__( true,
246	io.complete_q.completed_avg.val += count;
247	io.complete_q.completed_avg.fast_cnt += 1;
248	)
249	enable_interrupts( __cfaabi_dbg_ctx );
250
251	// If we got something, just yield and check again
252	if(reset < 5) {
253	yield();
254	}
255	// We didn't get anything baton pass to the slow poller
256	else {
257	__cfadbg_print_safe(io_core, "Kernel I/O : Parking io poller %p\n", &this.self);
258	reset = 0;
259
260	// block this thread
261	__ioctx_prepare_block( this, ev );
262	wait( this.sem );
263	}
264	}
265
266	__cfadbg_print_safe(io_core, "Kernel I/O : Fast poller for ring %p stopping\n", &this.ring);
267	}
268
269	//=============================================================================================
270	// I/O Submissions
271	//=============================================================================================
272
273	// Submition steps :
274	// 1 - Allocate a queue entry. The ring already has memory for all entries but only the ones
275	// listed in sq.array are visible by the kernel. For those not listed, the kernel does not
276	// offer any assurance that an entry is not being filled by multiple flags. Therefore, we
277	// need to write an allocator that allows allocating concurrently.
278	//
279	// 2 - Actually fill the submit entry, this is the only simple and straightforward step.
280	//
281	// 3 - Append the entry index to the array and adjust the tail accordingly. This operation
282	// needs to arrive to two concensus at the same time:
283	// A - The order in which entries are listed in the array: no two threads must pick the
284	// same index for their entries
285	// B - When can the tail be update for the kernel. EVERY entries in the array between
286	// head and tail must be fully filled and shouldn't ever be touched again.
287	//
288
289	[* struct io_uring_sqe, __u32] __submit_alloc( struct __io_data & ring, __u64 data ) {
290	/* paranoid */ verify( data != 0 );
291
292	// Prepare the data we need
293	__attribute((unused)) int len = 0;
294	__attribute((unused)) int block = 0;
295	__u32 cnt = *ring.submit_q.num;
296	__u32 mask = *ring.submit_q.mask;
297
298	disable_interrupts();
299	__u32 off = __tls_rand();
300	enable_interrupts( __cfaabi_dbg_ctx );
301
302	// Loop around looking for an available spot
303	for() {
304	// Look through the list starting at some offset
305	for(i; cnt) {
306	__u64 expected = 0;
307	__u32 idx = (i + off) & mask;
308	struct io_uring_sqe * sqe = &ring.submit_q.sqes[idx];
309	volatile __u64 * udata = &sqe->user_data;
310
311	if( *udata == expected &&
312	__atomic_compare_exchange_n( udata, &expected, data, true, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED ) )
313	{
314	// update statistics
315	__STATS__( false,
316	io.submit_q.alloc_avg.val += len;
317	io.submit_q.alloc_avg.block += block;
318	io.submit_q.alloc_avg.cnt += 1;
319	)
320
321
322	// Success return the data
323	return [sqe, idx];
324	}
325	verify(expected != data);
326
327	len ++;
328	}
329
330	block++;
331	yield();
332	}
333	}
334
335	static inline __u32 __submit_to_ready_array( struct __io_data & ring, __u32 idx, const __u32 mask ) {
336	/* paranoid */ verify( idx <= mask );
337	/* paranoid */ verify( idx != -1ul32 );
338
339	// We need to find a spot in the ready array
340	__attribute((unused)) int len = 0;
341	__attribute((unused)) int block = 0;
342	__u32 ready_mask = ring.submit_q.ready_cnt - 1;
343
344	disable_interrupts();
345	__u32 off = __tls_rand();
346	enable_interrupts( __cfaabi_dbg_ctx );
347
348	__u32 picked;
349	LOOKING: for() {
350	for(i; ring.submit_q.ready_cnt) {
351	picked = (i + off) & ready_mask;
352	__u32 expected = -1ul32;
353	if( __atomic_compare_exchange_n( &ring.submit_q.ready[picked], &expected, idx, true, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED ) ) {
354	break LOOKING;
355	}
356	verify(expected != idx);
357
358	len ++;
359	}
360
361	block++;
362
363	__u32 released = __release_consumed_submission( ring );
364	if( released == 0 ) {
365	yield();
366	}
367	}
368
369	// update statistics
370	__STATS__( false,
371	io.submit_q.look_avg.val += len;
372	io.submit_q.look_avg.block += block;
373	io.submit_q.look_avg.cnt += 1;
374	)
375
376	return picked;
377	}
378
379	void __submit( struct io_context * ctx, __u32 idx ) __attribute__((nonnull (1))) {
380	__io_data & ring = *ctx->thrd.ring;
381	// Get now the data we definetely need
382	volatile __u32 * const tail = ring.submit_q.tail;
383	const __u32 mask = *ring.submit_q.mask;
384
385	// There are 2 submission schemes, check which one we are using
386	if( ring.poller_submits ) {
387	// If the poller thread submits, then we just need to add this to the ready array
388	__submit_to_ready_array( ring, idx, mask );
389
390	post( ctx->thrd.sem );
391
392	__cfadbg_print_safe( io, "Kernel I/O : Added %u to ready for %p\n", idx, active_thread() );
393	}
394	else if( ring.eager_submits ) {
395	__u32 picked = __submit_to_ready_array( ring, idx, mask );
396
397	#if defined(LEADER_LOCK)
398	if( !try_lock(ring.submit_q.submit_lock) ) {
399	__STATS__( false,
400	io.submit_q.helped += 1;
401	)
402	return;
403	}
404	/* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
405	__STATS__( true,
406	io.submit_q.leader += 1;
407	)
408	#else
409	for() {
410	yield();
411
412	if( try_lock(ring.submit_q.submit_lock __cfaabi_dbg_ctx2) ) {
413	__STATS__( false,
414	io.submit_q.leader += 1;
415	)
416	break;
417	}
418
419	// If some one else collected our index, we are done
420	#warning ABA problem
421	if( ring.submit_q.ready[picked] != idx ) {
422	__STATS__( false,
423	io.submit_q.helped += 1;
424	)
425	return;
426	}
427
428	__STATS__( false,
429	io.submit_q.busy += 1;
430	)
431	}
432	#endif
433
434	// We got the lock
435	// Collect the submissions
436	unsigned to_submit = __collect_submitions( ring );
437
438	// Actually submit
439	int ret = __io_uring_enter( ring, to_submit, false );
440
441	#if defined(LEADER_LOCK)
442	/* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
443	next(ring.submit_q.submit_lock);
444	#else
445	unlock(ring.submit_q.submit_lock);
446	#endif
447	if( ret < 0 ) return;
448
449	// Release the consumed SQEs
450	__release_consumed_submission( ring );
451
452	// update statistics
453	__STATS__( false,
454	io.submit_q.submit_avg.rdy += to_submit;
455	io.submit_q.submit_avg.csm += ret;
456	io.submit_q.submit_avg.cnt += 1;
457	)
458	}
459	else {
460	// get mutual exclusion
461	#if defined(LEADER_LOCK)
462	while(!try_lock(ring.submit_q.submit_lock));
463	#else
464	lock(ring.submit_q.submit_lock __cfaabi_dbg_ctx2);
465	#endif
466
467	/* paranoid */ verifyf( ring.submit_q.sqes[ idx ].user_data != 0,
468	/* paranoid */ "index %u already reclaimed\n"
469	/* paranoid */ "head %u, prev %u, tail %u\n"
470	/* paranoid */ "[-0: %u,-1: %u,-2: %u,-3: %u]\n",
471	/* paranoid */ idx,
472	/* paranoid / ring.submit_q.head, ring.submit_q.prev_head, *tail
473	/* paranoid / ,ring.submit_q.array[ ((ring.submit_q.head) - 0) & (*ring.submit_q.mask) ]
474	/* paranoid / ,ring.submit_q.array[ ((ring.submit_q.head) - 1) & (*ring.submit_q.mask) ]
475	/* paranoid / ,ring.submit_q.array[ ((ring.submit_q.head) - 2) & (*ring.submit_q.mask) ]
476	/* paranoid / ,ring.submit_q.array[ ((ring.submit_q.head) - 3) & (*ring.submit_q.mask) ]
477	/* paranoid */ );
478
479	// Append to the list of ready entries
480
481	/* paranoid */ verify( idx <= mask );
482	ring.submit_q.array[ (*tail) & mask ] = idx;
483	__atomic_fetch_add(tail, 1ul32, __ATOMIC_SEQ_CST);
484
485	// Submit however, many entries need to be submitted
486	int ret = __io_uring_enter( ring, 1, false );
487	if( ret < 0 ) {
488	switch((int)errno) {
489	default:
490	abort( "KERNEL ERROR: IO_URING SUBMIT - %s\n", strerror(errno) );
491	}
492	}
493
494	// update statistics
495	__STATS__( false,
496	io.submit_q.submit_avg.csm += 1;
497	io.submit_q.submit_avg.cnt += 1;
498	)
499
500	// Release the consumed SQEs
501	__release_consumed_submission( ring );
502
503	#if defined(LEADER_LOCK)
504	next(ring.submit_q.submit_lock);
505	#else
506	unlock(ring.submit_q.submit_lock);
507	#endif
508
509	__cfadbg_print_safe( io, "Kernel I/O : Performed io_submit for %p, returned %d\n", active_thread(), ret );
510	}
511	}
512
513	static unsigned __collect_submitions( struct __io_data & ring ) {
514	/* paranoid */ verify( ring.submit_q.ready != 0p );
515	/* paranoid */ verify( ring.submit_q.ready_cnt > 0 );
516
517	unsigned to_submit = 0;
518	__u32 tail = *ring.submit_q.tail;
519	const __u32 mask = *ring.submit_q.mask;
520
521	// Go through the list of ready submissions
522	for( i; ring.submit_q.ready_cnt ) {
523	// replace any submission with the sentinel, to consume it.
524	__u32 idx = __atomic_exchange_n( &ring.submit_q.ready[i], -1ul32, __ATOMIC_RELAXED);
525
526	// If it was already the sentinel, then we are done
527	if( idx == -1ul32 ) continue;
528
529	// If we got a real submission, append it to the list
530	ring.submit_q.array[ (tail + to_submit) & mask ] = idx & mask;
531	to_submit++;
532	}
533
534	// Increment the tail based on how many we are ready to submit
535	__atomic_fetch_add(ring.submit_q.tail, to_submit, __ATOMIC_SEQ_CST);
536
537	return to_submit;
538	}
539
540	static __u32 __release_consumed_submission( struct __io_data & ring ) {
541	const __u32 smask = *ring.submit_q.mask;
542
543	if( !try_lock(ring.submit_q.release_lock __cfaabi_dbg_ctx2) ) return 0;
544	__u32 chead = *ring.submit_q.head;
545	__u32 phead = ring.submit_q.prev_head;
546	ring.submit_q.prev_head = chead;
547	unlock(ring.submit_q.release_lock);
548
549	__u32 count = chead - phead;
550	for( i; count ) {
551	__u32 idx = ring.submit_q.array[ (phead + i) & smask ];
552	ring.submit_q.sqes[ idx ].user_data = 0;
553	}
554	return count;
555	}
556	#endif

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format