Re: [PATCH 1/2] io_uring: trigger timeout after any sqe->off CQEs

[Pavel Begunkov <asml.silence@gmail.com>]

On 20/04/2020 22:40, Jens Axboe wrote:
> On 4/18/20 11:20 AM, Pavel Begunkov wrote:
>> +static void __io_flush_timeouts(struct io_ring_ctx *ctx)
>> +{
>> +	u32 end, start;
>> +
>> +	start = end = ctx->cached_cq_tail;
>> +	do {
>> +		struct io_kiocb *req = list_first_entry(&ctx->timeout_list,
>> +							struct io_kiocb, list);
>> +
>> +		if (req->flags & REQ_F_TIMEOUT_NOSEQ)
>> +			break;
>> +		/*
>> +		 * multiple timeouts may have the same target,
>> +		 * check that @req is in [first_tail, cur_tail]
>> +		 */
>> +		if (!io_check_in_range(req->timeout.target_cq, start, end))
>> +			break;
>> +
>> +		list_del_init(&req->list);
>> +		io_kill_timeout(req);
>> +		end = ctx->cached_cq_tail;
>> +	} while (!list_empty(&ctx->timeout_list));
>> +}
>> +
>>  static void io_commit_cqring(struct io_ring_ctx *ctx)
>>  {
>>  	struct io_kiocb *req;
>>  
>> -	while ((req = io_get_timeout_req(ctx)) != NULL)
>> -		io_kill_timeout(req);
>> +	if (!list_empty(&ctx->timeout_list))
>> +		__io_flush_timeouts(ctx);
>>  
>>  	__io_commit_cqring(ctx);
>>  
> 
> Any chance we can do this without having to iterate timeouts on the
> completion path?
> 

If you mean the one in __io_flush_timeouts(), then no, unless we forbid timeouts
with identical target sequences + some extra constraints. The loop there is not
new, it iterates only over timeouts, that need to be completed, and removes
them. That's amortised O(1).

On the other hand, there was a loop in io_timeout_fn() doing in total O(n^2),
and it was killed by this patch.

-- 
Pavel Begunkov