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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <f9c1492c-a0f6-c6ec-ec2e-82a5894060f6@gmail.com>
Date:   Mon, 20 Apr 2020 23:12:24 +0300
From:   Pavel Begunkov <asml.silence@...il.com>
To:     Jens Axboe <axboe@...nel.dk>, io-uring@...r.kernel.org,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH 1/2] io_uring: trigger timeout after any sqe->off CQEs

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