Context Navigation

io.cfa @ 290553a

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 290553a was b4b63e8, checked in by Thierry Delisle <tdelisle@…>, 4 years ago
Fixed missing changes to park/unpark. Added canary to threads to check when the thread was destroyed
Property mode set to `100644`
File size: 16.3 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();
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 );
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_future_t * future = (struct io_future_t *)(uintptr_t)cqe.user_data;
162	__cfadbg_print_safe( io, "Kernel I/O : Syscall completed : cqe %p, result %d for %p\n", future, cqe.res, data->thrd );
163
164	fulfil( *future, cqe.res );
165	}
166
167	// Process a single completion message from the io_uring
168	// This is NOT thread-safe
169	static [int, bool] __drain_io( & struct __io_data ring ) {
170	/* paranoid */ verify( !kernelTLS.preemption_state.enabled );
171
172	unsigned to_submit = 0;
173	if( ring.poller_submits ) {
174	// If the poller thread also submits, then we need to aggregate the submissions which are ready
175	to_submit = __collect_submitions( ring );
176	}
177
178	int ret = __io_uring_enter(ring, to_submit, true);
179	if( ret < 0 ) {
180	return [0, true];
181	}
182
183	// update statistics
184	if (to_submit > 0) {
185	__STATS__( true,
186	if( to_submit > 0 ) {
187	io.submit_q.submit_avg.rdy += to_submit;
188	io.submit_q.submit_avg.csm += ret;
189	io.submit_q.submit_avg.cnt += 1;
190	}
191	)
192	}
193
194	// Release the consumed SQEs
195	__release_consumed_submission( ring );
196
197	// Drain the queue
198	unsigned head = *ring.completion_q.head;
199	unsigned tail = *ring.completion_q.tail;
200	const __u32 mask = *ring.completion_q.mask;
201
202	// Nothing was new return 0
203	if (head == tail) {
204	return [0, to_submit > 0];
205	}
206
207	__u32 count = tail - head;
208	/* paranoid */ verify( count != 0 );
209	for(i; count) {
210	unsigned idx = (head + i) & mask;
211	struct io_uring_cqe & cqe = ring.completion_q.cqes[idx];
212
213	/* paranoid */ verify(&cqe);
214
215	process( cqe );
216	}
217
218	// Mark to the kernel that the cqe has been seen
219	// Ensure that the kernel only sees the new value of the head index after the CQEs have been read.
220	__atomic_thread_fence( __ATOMIC_SEQ_CST );
221	__atomic_fetch_add( ring.completion_q.head, count, __ATOMIC_RELAXED );
222
223	return [count, count > 0 \|\| to_submit > 0];
224	}
225
226	void main( $io_ctx_thread & this ) {
227	epoll_event ev;
228	__ioctx_register( this, ev );
229
230	__cfadbg_print_safe(io_core, "Kernel I/O : IO poller %p for ring %p ready\n", &this, &this.ring);
231
232	int reset = 0;
233	// Then loop until we need to start
234	while(!__atomic_load_n(&this.done, __ATOMIC_SEQ_CST)) {
235	// Drain the io
236	int count;
237	bool again;
238	disable_interrupts();
239	[count, again] = __drain_io( *this.ring );
240
241	if(!again) reset++;
242
243	// Update statistics
244	__STATS__( true,
245	io.complete_q.completed_avg.val += count;
246	io.complete_q.completed_avg.cnt += 1;
247	)
248	enable_interrupts( __cfaabi_dbg_ctx );
249
250	// If we got something, just yield and check again
251	if(reset < 5) {
252	yield();
253	}
254	// We didn't get anything baton pass to the slow poller
255	else {
256	__STATS__( false,
257	io.complete_q.blocks += 1;
258	)
259	__cfadbg_print_safe(io_core, "Kernel I/O : Parking io poller %p\n", &this.self);
260	reset = 0;
261
262	// block this thread
263	__ioctx_prepare_block( this, ev );
264	wait( this.sem );
265	}
266	}
267
268	__cfadbg_print_safe(io_core, "Kernel I/O : Fast poller for ring %p stopping\n", &this.ring);
269	}
270
271	//=============================================================================================
272	// I/O Submissions
273	//=============================================================================================
274
275	// Submition steps :
276	// 1 - Allocate a queue entry. The ring already has memory for all entries but only the ones
277	// listed in sq.array are visible by the kernel. For those not listed, the kernel does not
278	// offer any assurance that an entry is not being filled by multiple flags. Therefore, we
279	// need to write an allocator that allows allocating concurrently.
280	//
281	// 2 - Actually fill the submit entry, this is the only simple and straightforward step.
282	//
283	// 3 - Append the entry index to the array and adjust the tail accordingly. This operation
284	// needs to arrive to two concensus at the same time:
285	// A - The order in which entries are listed in the array: no two threads must pick the
286	// same index for their entries
287	// B - When can the tail be update for the kernel. EVERY entries in the array between
288	// head and tail must be fully filled and shouldn't ever be touched again.
289	//
290
291	[* struct io_uring_sqe, __u32] __submit_alloc( struct __io_data & ring, __u64 data ) {
292	/* paranoid */ verify( data != 0 );
293
294	// Prepare the data we need
295	__attribute((unused)) int len = 0;
296	__attribute((unused)) int block = 0;
297	__u32 cnt = *ring.submit_q.num;
298	__u32 mask = *ring.submit_q.mask;
299
300	disable_interrupts();
301	__u32 off = __tls_rand();
302	enable_interrupts( __cfaabi_dbg_ctx );
303
304	// Loop around looking for an available spot
305	for() {
306	// Look through the list starting at some offset
307	for(i; cnt) {
308	__u64 expected = 0;
309	__u32 idx = (i + off) & mask;
310	struct io_uring_sqe * sqe = &ring.submit_q.sqes[idx];
311	volatile __u64 * udata = &sqe->user_data;
312
313	if( *udata == expected &&
314	__atomic_compare_exchange_n( udata, &expected, data, true, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED ) )
315	{
316	// update statistics
317	__STATS__( false,
318	io.submit_q.alloc_avg.val += len;
319	io.submit_q.alloc_avg.block += block;
320	io.submit_q.alloc_avg.cnt += 1;
321	)
322
323
324	// Success return the data
325	return [sqe, idx];
326	}
327	verify(expected != data);
328
329	len ++;
330	}
331
332	block++;
333	yield();
334	}
335	}
336
337	static inline __u32 __submit_to_ready_array( struct __io_data & ring, __u32 idx, const __u32 mask ) {
338	/* paranoid */ verify( idx <= mask );
339	/* paranoid */ verify( idx != -1ul32 );
340
341	// We need to find a spot in the ready array
342	__attribute((unused)) int len = 0;
343	__attribute((unused)) int block = 0;
344	__u32 ready_mask = ring.submit_q.ready_cnt - 1;
345
346	disable_interrupts();
347	__u32 off = __tls_rand();
348	enable_interrupts( __cfaabi_dbg_ctx );
349
350	__u32 picked;
351	LOOKING: for() {
352	for(i; ring.submit_q.ready_cnt) {
353	picked = (i + off) & ready_mask;
354	__u32 expected = -1ul32;
355	if( __atomic_compare_exchange_n( &ring.submit_q.ready[picked], &expected, idx, true, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED ) ) {
356	break LOOKING;
357	}
358	verify(expected != idx);
359
360	len ++;
361	}
362
363	block++;
364
365	__u32 released = __release_consumed_submission( ring );
366	if( released == 0 ) {
367	yield();
368	}
369	}
370
371	// update statistics
372	__STATS__( false,
373	io.submit_q.look_avg.val += len;
374	io.submit_q.look_avg.block += block;
375	io.submit_q.look_avg.cnt += 1;
376	)
377
378	return picked;
379	}
380
381	void __submit( struct io_context * ctx, __u32 idx ) __attribute__((nonnull (1))) {
382	__io_data & ring = *ctx->thrd.ring;
383	// Get now the data we definetely need
384	volatile __u32 * const tail = ring.submit_q.tail;
385	const __u32 mask = *ring.submit_q.mask;
386
387	// There are 2 submission schemes, check which one we are using
388	if( ring.poller_submits ) {
389	// If the poller thread submits, then we just need to add this to the ready array
390	__submit_to_ready_array( ring, idx, mask );
391
392	post( ctx->thrd.sem );
393
394	__cfadbg_print_safe( io, "Kernel I/O : Added %u to ready for %p\n", idx, active_thread() );
395	}
396	else if( ring.eager_submits ) {
397	__u32 picked = __submit_to_ready_array( ring, idx, mask );
398
399	#if defined(LEADER_LOCK)
400	if( !try_lock(ring.submit_q.submit_lock) ) {
401	__STATS__( false,
402	io.submit_q.helped += 1;
403	)
404	return;
405	}
406	/* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
407	__STATS__( true,
408	io.submit_q.leader += 1;
409	)
410	#else
411	for() {
412	yield();
413
414	if( try_lock(ring.submit_q.submit_lock __cfaabi_dbg_ctx2) ) {
415	__STATS__( false,
416	io.submit_q.leader += 1;
417	)
418	break;
419	}
420
421	// If some one else collected our index, we are done
422	#warning ABA problem
423	if( ring.submit_q.ready[picked] != idx ) {
424	__STATS__( false,
425	io.submit_q.helped += 1;
426	)
427	return;
428	}
429
430	__STATS__( false,
431	io.submit_q.busy += 1;
432	)
433	}
434	#endif
435
436	// We got the lock
437	// Collect the submissions
438	unsigned to_submit = __collect_submitions( ring );
439
440	// Actually submit
441	int ret = __io_uring_enter( ring, to_submit, false );
442
443	#if defined(LEADER_LOCK)
444	/* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
445	next(ring.submit_q.submit_lock);
446	#else
447	unlock(ring.submit_q.submit_lock);
448	#endif
449	if( ret < 0 ) return;
450
451	// Release the consumed SQEs
452	__release_consumed_submission( ring );
453
454	// update statistics
455	__STATS__( false,
456	io.submit_q.submit_avg.rdy += to_submit;
457	io.submit_q.submit_avg.csm += ret;
458	io.submit_q.submit_avg.cnt += 1;
459	)
460	}
461	else {
462	// get mutual exclusion
463	#if defined(LEADER_LOCK)
464	while(!try_lock(ring.submit_q.submit_lock));
465	#else
466	lock(ring.submit_q.submit_lock __cfaabi_dbg_ctx2);
467	#endif
468
469	/* paranoid */ verifyf( ring.submit_q.sqes[ idx ].user_data != 0,
470	/* paranoid */ "index %u already reclaimed\n"
471	/* paranoid */ "head %u, prev %u, tail %u\n"
472	/* paranoid */ "[-0: %u,-1: %u,-2: %u,-3: %u]\n",
473	/* paranoid */ idx,
474	/* paranoid / ring.submit_q.head, ring.submit_q.prev_head, *tail
475	/* paranoid / ,ring.submit_q.array[ ((ring.submit_q.head) - 0) & (*ring.submit_q.mask) ]
476	/* paranoid / ,ring.submit_q.array[ ((ring.submit_q.head) - 1) & (*ring.submit_q.mask) ]
477	/* paranoid / ,ring.submit_q.array[ ((ring.submit_q.head) - 2) & (*ring.submit_q.mask) ]
478	/* paranoid / ,ring.submit_q.array[ ((ring.submit_q.head) - 3) & (*ring.submit_q.mask) ]
479	/* paranoid */ );
480
481	// Append to the list of ready entries
482
483	/* paranoid */ verify( idx <= mask );
484	ring.submit_q.array[ (*tail) & mask ] = idx;
485	__atomic_fetch_add(tail, 1ul32, __ATOMIC_SEQ_CST);
486
487	// Submit however, many entries need to be submitted
488	int ret = __io_uring_enter( ring, 1, false );
489	if( ret < 0 ) {
490	switch((int)errno) {
491	default:
492	abort( "KERNEL ERROR: IO_URING SUBMIT - %s\n", strerror(errno) );
493	}
494	}
495
496	// update statistics
497	__STATS__( false,
498	io.submit_q.submit_avg.csm += 1;
499	io.submit_q.submit_avg.cnt += 1;
500	)
501
502	// Release the consumed SQEs
503	__release_consumed_submission( ring );
504
505	#if defined(LEADER_LOCK)
506	next(ring.submit_q.submit_lock);
507	#else
508	unlock(ring.submit_q.submit_lock);
509	#endif
510
511	__cfadbg_print_safe( io, "Kernel I/O : Performed io_submit for %p, returned %d\n", active_thread(), ret );
512	}
513	}
514
515	// #define PARTIAL_SUBMIT 32
516	static unsigned __collect_submitions( struct __io_data & ring ) {
517	/* paranoid */ verify( ring.submit_q.ready != 0p );
518	/* paranoid */ verify( ring.submit_q.ready_cnt > 0 );
519
520	unsigned to_submit = 0;
521	__u32 tail = *ring.submit_q.tail;
522	const __u32 mask = *ring.submit_q.mask;
523	#if defined(PARTIAL_SUBMIT)
524	#if defined(LEADER_LOCK)
525	#error PARTIAL_SUBMIT and LEADER_LOCK cannot co-exist
526	#endif
527	const __u32 cnt = ring.submit_q.ready_cnt > PARTIAL_SUBMIT ? PARTIAL_SUBMIT : ring.submit_q.ready_cnt;
528	const __u32 offset = ring.submit_q.prev_ready;
529	ring.submit_q.prev_ready += cnt;
530	#else
531	const __u32 cnt = ring.submit_q.ready_cnt;
532	const __u32 offset = 0;
533	#endif
534
535	// Go through the list of ready submissions
536	for( c; cnt ) {
537	__u32 i = (offset + c) % ring.submit_q.ready_cnt;
538
539	// replace any submission with the sentinel, to consume it.
540	__u32 idx = __atomic_exchange_n( &ring.submit_q.ready[i], -1ul32, __ATOMIC_RELAXED);
541
542	// If it was already the sentinel, then we are done
543	if( idx == -1ul32 ) continue;
544
545	// If we got a real submission, append it to the list
546	ring.submit_q.array[ (tail + to_submit) & mask ] = idx & mask;
547	to_submit++;
548	}
549
550	// Increment the tail based on how many we are ready to submit
551	__atomic_fetch_add(ring.submit_q.tail, to_submit, __ATOMIC_SEQ_CST);
552
553	return to_submit;
554	}
555
556	static __u32 __release_consumed_submission( struct __io_data & ring ) {
557	const __u32 smask = *ring.submit_q.mask;
558
559	if( !try_lock(ring.submit_q.release_lock __cfaabi_dbg_ctx2) ) return 0;
560	__u32 chead = *ring.submit_q.head;
561	__u32 phead = ring.submit_q.prev_head;
562	ring.submit_q.prev_head = chead;
563	unlock(ring.submit_q.release_lock);
564
565	__u32 count = chead - phead;
566	for( i; count ) {
567	__u32 idx = ring.submit_q.array[ (phead + i) & smask ];
568	ring.submit_q.sqes[ idx ].user_data = 0;
569	}
570	return count;
571	}
572	#endif

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

Download in other formats:

Original Format