Resizing io_uring SQ/CQ?

Resizing io_uring SQ/CQ?

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 1461 bytes --]

Hi,
For block I/O an application can queue excess SQEs in userspace when the
SQ ring becomes full. For network and IPC operations that is not
possible because deadlocks can occur when socket, pipe, and eventfd SQEs
cannot be submitted.

Sometimes the application does not know how many SQEs/CQEs are needed upfront
and that's when we face this challenge.

A simple solution is to call io_uring_setup(2) with a higher entries
value than you'll ever need. However, if that value is exceeded then
we're back to the deadlock scenario and that worries me.

I've thought about userspace solutions like keeping a list of io_uring
contexts where a new io_uring context is created and inserted at the
head every time a resize is required. New SQEs are only submitted to the
head io_uring context. The older io_uring contexts are drained until the
CQ ring is empty and then destroyed. But this seems complex to me.

Another idea is a new io_uring_register(2) IORING_REGISTER_RING_SIZE
opcode:
1. Userspace ensures that the kernel has seen all SQEs in the SQ ring.
2. Userspace munmaps the ring fd.
3. Userspace calls io_uring_register(2) IORING_REGISTER_RING_SIZE with the new size.
4. The kernel allocates the new ring.
5. The kernel copies over CQEs that userspace has not consumed from the
   old CQ ring to the new one.
6. The io_uring_register(2) syscall returns.
7. Userspace mmaps the fd again.

How do you deal with changing ring size at runtime?

Thanks,
Stefan

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Resizing io_uring SQ/CQ?

[Ming Lei]

On Thu, Mar 09, 2023 at 08:48:08AM -0500, Stefan Hajnoczi wrote:
> Hi,
> For block I/O an application can queue excess SQEs in userspace when the
> SQ ring becomes full. For network and IPC operations that is not
> possible because deadlocks can occur when socket, pipe, and eventfd SQEs
> cannot be submitted.

Can you explain a bit the deadlock in case of network application? io_uring
does support to queue many network SQEs via IOSQE_IO_LINK, at least for
send.

> 
> Sometimes the application does not know how many SQEs/CQEs are needed upfront
> and that's when we face this challenge.

When running out of SQEs,  the application can call io_uring_enter() to submit
queued SQEs immediately without waiting for get events, then once
io_uring_enter() returns, you get free SQEs for moving one.

> 
> A simple solution is to call io_uring_setup(2) with a higher entries
> value than you'll ever need. However, if that value is exceeded then
> we're back to the deadlock scenario and that worries me.

Can you please explain the deadlock scenario?


Thanks, 
Ming

Re: Resizing io_uring SQ/CQ?

[Jens Axboe]

On 3/9/23 6:38?PM, Ming Lei wrote:
> On Thu, Mar 09, 2023 at 08:48:08AM -0500, Stefan Hajnoczi wrote:
>> Hi,
>> For block I/O an application can queue excess SQEs in userspace when the
>> SQ ring becomes full. For network and IPC operations that is not
>> possible because deadlocks can occur when socket, pipe, and eventfd SQEs
>> cannot be submitted.
> 
> Can you explain a bit the deadlock in case of network application? io_uring
> does support to queue many network SQEs via IOSQE_IO_LINK, at least for
> send.
> 
>>
>> Sometimes the application does not know how many SQEs/CQEs are needed upfront
>> and that's when we face this challenge.
> 
> When running out of SQEs,  the application can call io_uring_enter() to submit
> queued SQEs immediately without waiting for get events, then once
> io_uring_enter() returns, you get free SQEs for moving one.
> 
>>
>> A simple solution is to call io_uring_setup(2) with a higher entries
>> value than you'll ever need. However, if that value is exceeded then
>> we're back to the deadlock scenario and that worries me.
> 
> Can you please explain the deadlock scenario?

I'm also curious of what these deadlocks are. As Ming says, you
generally never run out of SQEs as you can always just submit what you
have pending and now you have a full queue size worth of them available
again.

I do think resizing the CQ ring may have some merit, as for networking
you may want to start smaller and resize it if you run into overflows as
those will be less efficient. But I'm somewhat curious on the reasonings
for wanting to resize the SQ ring?

-- 
Jens Axboe

Re: Resizing io_uring SQ/CQ?

[Vito Caputo]

On Thu, Mar 09, 2023 at 07:58:31PM -0700, Jens Axboe wrote:
> On 3/9/23 6:38?PM, Ming Lei wrote:
> > On Thu, Mar 09, 2023 at 08:48:08AM -0500, Stefan Hajnoczi wrote:
> >> Hi,
> >> For block I/O an application can queue excess SQEs in userspace when the
> >> SQ ring becomes full. For network and IPC operations that is not
> >> possible because deadlocks can occur when socket, pipe, and eventfd SQEs
> >> cannot be submitted.
> > 
> > Can you explain a bit the deadlock in case of network application? io_uring
> > does support to queue many network SQEs via IOSQE_IO_LINK, at least for
> > send.
> > 
> >>
> >> Sometimes the application does not know how many SQEs/CQEs are needed upfront
> >> and that's when we face this challenge.
> > 
> > When running out of SQEs,  the application can call io_uring_enter() to submit
> > queued SQEs immediately without waiting for get events, then once
> > io_uring_enter() returns, you get free SQEs for moving one.
> > 
> >>
> >> A simple solution is to call io_uring_setup(2) with a higher entries
> >> value than you'll ever need. However, if that value is exceeded then
> >> we're back to the deadlock scenario and that worries me.
> > 
> > Can you please explain the deadlock scenario?
> 
> I'm also curious of what these deadlocks are. As Ming says, you
> generally never run out of SQEs as you can always just submit what you
> have pending and now you have a full queue size worth of them available
> again.
> 

In my limited io_uring experiments it was convenient to know I could
*always* get+prepare N number of concurrent SQEs before having to
submit.

I was working with a set of files I needed to first discover the
quantity of, so I would start with a bootstrap ring size sufficient for
the discovery process.  Then once known, I'd resize the ring to
accomodate the maximum width of SEQs N files could produce for the given
operation.

The convenience was it made the dispatch functions logically atomic
units.  In the sense that they didn't need to be able to handle running
out of SQEs, submitting, and resuming in a continuation style.  They
could just be coded simply in a single loop iterating across the N files
getting+preparing SQEs, confident they wouldn't "deadlock" from
exhaustion.

Perhaps that's a similar "deadlock" scenario to Ming's.

But I should note that in my experiments I was always operating under
the assumption that I'd never have N so large it couldn't possibly
exceed the maximum SQ size I could allocate.  And that probably isn't a
safe assumption for a real production program, I was just experimenting
after all.

Also I was able to "resize" by just quiescing the ring, destroying it,
and recreating it with the new size.  It wasn't a perf sensitive thing,
just startup rigamarole.  I do recall being a little surprised I had to
ad-hoc implement the resize at the time though...

Regards,
Vito Caputo

Re: Resizing io_uring SQ/CQ?

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 3613 bytes --]

On Thu, Mar 09, 2023 at 07:58:31PM -0700, Jens Axboe wrote:
> On 3/9/23 6:38?PM, Ming Lei wrote:
> > On Thu, Mar 09, 2023 at 08:48:08AM -0500, Stefan Hajnoczi wrote:
> >> Hi,
> >> For block I/O an application can queue excess SQEs in userspace when the
> >> SQ ring becomes full. For network and IPC operations that is not
> >> possible because deadlocks can occur when socket, pipe, and eventfd SQEs
> >> cannot be submitted.
> > 
> > Can you explain a bit the deadlock in case of network application? io_uring
> > does support to queue many network SQEs via IOSQE_IO_LINK, at least for
> > send.
> > 
> >>
> >> Sometimes the application does not know how many SQEs/CQEs are needed upfront
> >> and that's when we face this challenge.
> > 
> > When running out of SQEs,  the application can call io_uring_enter() to submit
> > queued SQEs immediately without waiting for get events, then once
> > io_uring_enter() returns, you get free SQEs for moving one.
> > 
> >>
> >> A simple solution is to call io_uring_setup(2) with a higher entries
> >> value than you'll ever need. However, if that value is exceeded then
> >> we're back to the deadlock scenario and that worries me.
> > 
> > Can you please explain the deadlock scenario?
> 
> I'm also curious of what these deadlocks are. As Ming says, you
> generally never run out of SQEs as you can always just submit what you
> have pending and now you have a full queue size worth of them available
> again.
> 
> I do think resizing the CQ ring may have some merit, as for networking
> you may want to start smaller and resize it if you run into overflows as
> those will be less efficient. But I'm somewhat curious on the reasonings
> for wanting to resize the SQ ring?

Hi Ming and Jens,
Thanks for the response. I'll try to explain why I worry about
deadlocks.

Imagine an application has an I/O operation that must complete in order
to make progress. If io_uring_enter(2) fails then the application is
unable to submit that critical I/O.

The io_uring_enter(2) man page says:

  EBUSY  If  the IORING_FEAT_NODROP feature flag is set, then EBUSY will
	 be returned if there were overflow entries,
	 IORING_ENTER_GETEVENTS flag is set and not all of the overflow
	 entries were able to be flushed to the CQ ring.

	 Without IORING_FEAT_NODROP the application is attempting to
	 overcommit the number of requests it can have pending. The
	 application should wait for some completions and try again. May
	 occur if the application tries to queue more requests than we
	 have room for in the CQ ring, or if the application attempts to
	 wait for more events without having reaped the ones already
	 present in the CQ ring.

Some I/O operations can take forever (e.g. reading an eventfd), so there
is no guarantee that the I/Os already in flight will complete. If in
flight I/O operations accumulate to the point where io_uring_enter(2)
returns with EBUSY then the application is starved and unable to submit
more I/O.

Starvation turns into a deadlock when the completion of the already in
flight I/O depends on the yet-to-be-submitted I/O. For example, the
application is supposed to write to a socket and another process will
then signal the eventfd that the application is reading, but we're
unable to submit the write.

I asked about resizing the rings because if we can size them
appropriately, then we can ensure there are sufficient resources for all
I/Os that will be in flight. This prevents EBUSY, starvation, and
deadlock.

Maybe I've misunderstood the man page?

Stefan

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Resizing io_uring SQ/CQ?

[Ming Lei]

On Fri, Mar 10, 2023 at 08:44:00AM -0500, Stefan Hajnoczi wrote:
> On Thu, Mar 09, 2023 at 07:58:31PM -0700, Jens Axboe wrote:
> > On 3/9/23 6:38?PM, Ming Lei wrote:
> > > On Thu, Mar 09, 2023 at 08:48:08AM -0500, Stefan Hajnoczi wrote:
> > >> Hi,
> > >> For block I/O an application can queue excess SQEs in userspace when the
> > >> SQ ring becomes full. For network and IPC operations that is not
> > >> possible because deadlocks can occur when socket, pipe, and eventfd SQEs
> > >> cannot be submitted.
> > > 
> > > Can you explain a bit the deadlock in case of network application? io_uring
> > > does support to queue many network SQEs via IOSQE_IO_LINK, at least for
> > > send.
> > > 
> > >>
> > >> Sometimes the application does not know how many SQEs/CQEs are needed upfront
> > >> and that's when we face this challenge.
> > > 
> > > When running out of SQEs,  the application can call io_uring_enter() to submit
> > > queued SQEs immediately without waiting for get events, then once
> > > io_uring_enter() returns, you get free SQEs for moving one.
> > > 
> > >>
> > >> A simple solution is to call io_uring_setup(2) with a higher entries
> > >> value than you'll ever need. However, if that value is exceeded then
> > >> we're back to the deadlock scenario and that worries me.
> > > 
> > > Can you please explain the deadlock scenario?
> > 
> > I'm also curious of what these deadlocks are. As Ming says, you
> > generally never run out of SQEs as you can always just submit what you
> > have pending and now you have a full queue size worth of them available
> > again.
> > 
> > I do think resizing the CQ ring may have some merit, as for networking
> > you may want to start smaller and resize it if you run into overflows as
> > those will be less efficient. But I'm somewhat curious on the reasonings
> > for wanting to resize the SQ ring?
> 
> Hi Ming and Jens,
> Thanks for the response. I'll try to explain why I worry about
> deadlocks.
> 
> Imagine an application has an I/O operation that must complete in order
> to make progress. If io_uring_enter(2) fails then the application is
> unable to submit that critical I/O.
> 
> The io_uring_enter(2) man page says:
> 
>   EBUSY  If  the IORING_FEAT_NODROP feature flag is set, then EBUSY will
> 	 be returned if there were overflow entries,
> 	 IORING_ENTER_GETEVENTS flag is set and not all of the overflow
> 	 entries were able to be flushed to the CQ ring.
> 
> 	 Without IORING_FEAT_NODROP the application is attempting to
> 	 overcommit the number of requests it can have pending. The
> 	 application should wait for some completions and try again. May
> 	 occur if the application tries to queue more requests than we
> 	 have room for in the CQ ring, or if the application attempts to
> 	 wait for more events without having reaped the ones already
> 	 present in the CQ ring.
> 
> Some I/O operations can take forever (e.g. reading an eventfd), so there
> is no guarantee that the I/Os already in flight will complete. If in
> flight I/O operations accumulate to the point where io_uring_enter(2)
> returns with EBUSY then the application is starved and unable to submit

The man page said clearly that EBUSY will be returned if there were overflow
CQE entries. But here, no in-flight IOs are completed and no CQEs actually in
CQ ring, so how can the -EBUSY be triggered?

Also I don't see any words about the following description:

	-EBUSY will be returned if many enough in-flight IOs are accumulated,

So care to explain it a bit?

> more I/O.
> 
> Starvation turns into a deadlock when the completion of the already in
> flight I/O depends on the yet-to-be-submitted I/O. For example, the
> application is supposed to write to a socket and another process will
> then signal the eventfd that the application is reading, but we're
> unable to submit the write.

OK, looks it is IO dependency issue, I understand it should be solved
by application. I remember I saw sort of problem when I write ublk/nbd,
but just forget the details now.

> 
> I asked about resizing the rings because if we can size them
> appropriately, then we can ensure there are sufficient resources for all
> I/Os that will be in flight. This prevents EBUSY, starvation, and
> deadlock.

But how can this issue be related with resizing rings and IORING_FEAT_NODROP?

In above description, both SQ and CQ ring are supposed to be empty.



Thanks,
Ming

Re: Resizing io_uring SQ/CQ?

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 5070 bytes --]

On Fri, Mar 10, 2023 at 11:14:04PM +0800, Ming Lei wrote:
> On Fri, Mar 10, 2023 at 08:44:00AM -0500, Stefan Hajnoczi wrote:
> > On Thu, Mar 09, 2023 at 07:58:31PM -0700, Jens Axboe wrote:
> > > On 3/9/23 6:38?PM, Ming Lei wrote:
> > > > On Thu, Mar 09, 2023 at 08:48:08AM -0500, Stefan Hajnoczi wrote:
> > > >> Hi,
> > > >> For block I/O an application can queue excess SQEs in userspace when the
> > > >> SQ ring becomes full. For network and IPC operations that is not
> > > >> possible because deadlocks can occur when socket, pipe, and eventfd SQEs
> > > >> cannot be submitted.
> > > > 
> > > > Can you explain a bit the deadlock in case of network application? io_uring
> > > > does support to queue many network SQEs via IOSQE_IO_LINK, at least for
> > > > send.
> > > > 
> > > >>
> > > >> Sometimes the application does not know how many SQEs/CQEs are needed upfront
> > > >> and that's when we face this challenge.
> > > > 
> > > > When running out of SQEs,  the application can call io_uring_enter() to submit
> > > > queued SQEs immediately without waiting for get events, then once
> > > > io_uring_enter() returns, you get free SQEs for moving one.
> > > > 
> > > >>
> > > >> A simple solution is to call io_uring_setup(2) with a higher entries
> > > >> value than you'll ever need. However, if that value is exceeded then
> > > >> we're back to the deadlock scenario and that worries me.
> > > > 
> > > > Can you please explain the deadlock scenario?
> > > 
> > > I'm also curious of what these deadlocks are. As Ming says, you
> > > generally never run out of SQEs as you can always just submit what you
> > > have pending and now you have a full queue size worth of them available
> > > again.
> > > 
> > > I do think resizing the CQ ring may have some merit, as for networking
> > > you may want to start smaller and resize it if you run into overflows as
> > > those will be less efficient. But I'm somewhat curious on the reasonings
> > > for wanting to resize the SQ ring?
> > 
> > Hi Ming and Jens,
> > Thanks for the response. I'll try to explain why I worry about
> > deadlocks.
> > 
> > Imagine an application has an I/O operation that must complete in order
> > to make progress. If io_uring_enter(2) fails then the application is
> > unable to submit that critical I/O.
> > 
> > The io_uring_enter(2) man page says:
> > 
> >   EBUSY  If  the IORING_FEAT_NODROP feature flag is set, then EBUSY will
> > 	 be returned if there were overflow entries,
> > 	 IORING_ENTER_GETEVENTS flag is set and not all of the overflow
> > 	 entries were able to be flushed to the CQ ring.
> > 
> > 	 Without IORING_FEAT_NODROP the application is attempting to
> > 	 overcommit the number of requests it can have pending. The
> > 	 application should wait for some completions and try again. May
> > 	 occur if the application tries to queue more requests than we
> > 	 have room for in the CQ ring, or if the application attempts to
> > 	 wait for more events without having reaped the ones already
> > 	 present in the CQ ring.
> > 
> > Some I/O operations can take forever (e.g. reading an eventfd), so there
> > is no guarantee that the I/Os already in flight will complete. If in
> > flight I/O operations accumulate to the point where io_uring_enter(2)
> > returns with EBUSY then the application is starved and unable to submit
> 
> The man page said clearly that EBUSY will be returned if there were overflow
> CQE entries. But here, no in-flight IOs are completed and no CQEs actually in
> CQ ring, so how can the -EBUSY be triggered?
> 
> Also I don't see any words about the following description:
> 
> 	-EBUSY will be returned if many enough in-flight IOs are accumulated,
> 
> So care to explain it a bit?

Thanks, Ming. I think it's because I wasn't considering IORING_FEAT_NODROP!

Can you confirm that io_uring_enter() with IORING_FEAT_NODROP always
succeeds in submitting more requests (except for out-of-memory) provided
the application keeps consuming the CQ ring? If yes, then
IORING_FEAT_NODROP solves the issue on Linux 5.5 and later.

Regarding the non-IORING_FEAT_NODROP case, I think the deadlock issue
exists:

  Without IORING_FEAT_NODROP the application is attempting to overcommit
  the number of requests it can have pending.

A general statement that does not mention the CQ ring.

  The application should wait for some completions and try again.

Doesn't help in the deadlock scenario because we must submit one more
I/O in order for existing I/Os to start completing.

  May occur if the application tries to queue more requests than we
  have room for in the CQ ring,

I interpreted this to mean that once there are cq_entries I/Os in
flight, then io_uring_enter(2) may return with EBUSY if you attempt to
submit more I/Os. Is that right?

  or if the application attempts to wait for more events without having
  reaped the ones already present in the CQ ring.

This doesn't apply to the deadlock scenario.

Stefan

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Resizing io_uring SQ/CQ?

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 467 bytes --]

On Fri, Mar 10, 2023 at 11:14:04PM +0800, Ming Lei wrote:

Hi Ming,
Another question about this:

Does the io worker thread pool have limits so that eventually work
queues up and new work is not able to execute until in-flight work
completes?

In that case, even if io_uring_enter(2) accepts requests without
returning EBUSY/EAGAIN, it seems like there is still a deadlock scenario
when work that is executing depends on later work that is unable to
execute.

Stefan

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Resizing io_uring SQ/CQ?

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 199 bytes --]

Hi Ming and Jens,
It would be great if you have time to clarify whether deadlocks can
occur or not. If you have any questions about the scenario I was
describing, please let me know.

Thanks,
Stefan

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Resizing io_uring SQ/CQ?

[Jens Axboe]

On 3/10/23 9:56 AM, Stefan Hajnoczi wrote:
> On Fri, Mar 10, 2023 at 11:14:04PM +0800, Ming Lei wrote:
> 
> Hi Ming,
> Another question about this:
> 
> Does the io worker thread pool have limits so that eventually work
> queues up and new work is not able to execute until in-flight work
> completes?

It's effectively limited by how many processes you are allowed to
create. If you exceed that limit, then yes you would have work
sitting behind other work, and that new work won't get to run
before _something_ completes.

But no ring sizing will save that, you've effectively exhausted
any resources in the system, at least for you.

-- 
Jens Axboe

Re: Resizing io_uring SQ/CQ?

[Jens Axboe]

On 3/15/23 9:15 AM, Stefan Hajnoczi wrote:
> Hi Ming and Jens,
> It would be great if you have time to clarify whether deadlocks can
> occur or not. If you have any questions about the scenario I was
> describing, please let me know.

I don't believe there is. In anything not ancient, you are always
allowed to submit and the documentation should be updated to
describe that correctly. We don't return -EBUSY for submits with
overflow pending.

-- 
Jens Axboe

Re: Resizing io_uring SQ/CQ?

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 601 bytes --]

On Wed, Mar 15, 2023 at 09:19:39AM -0600, Jens Axboe wrote:
> On 3/15/23 9:15 AM, Stefan Hajnoczi wrote:
> > Hi Ming and Jens,
> > It would be great if you have time to clarify whether deadlocks can
> > occur or not. If you have any questions about the scenario I was
> > describing, please let me know.
> 
> I don't believe there is. In anything not ancient, you are always
> allowed to submit and the documentation should be updated to
> describe that correctly. We don't return -EBUSY for submits with
> overflow pending.

Thank you both for the discussion! It has helped.

Stefan

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Resizing io_uring SQ/CQ?

[Jens Axboe]

On 3/15/23 1:01?PM, Stefan Hajnoczi wrote:
> On Wed, Mar 15, 2023 at 09:19:39AM -0600, Jens Axboe wrote:
>> On 3/15/23 9:15?AM, Stefan Hajnoczi wrote:
>>> Hi Ming and Jens,
>>> It would be great if you have time to clarify whether deadlocks can
>>> occur or not. If you have any questions about the scenario I was
>>> describing, please let me know.
>>
>> I don't believe there is. In anything not ancient, you are always
>> allowed to submit and the documentation should be updated to
>> describe that correctly. We don't return -EBUSY for submits with
>> overflow pending.
> 
> Thank you both for the discussion! It has helped.

Would like to add that while I don't think ring resizing is necessary
because of any potential deadlocks, I do think CQ ring resizing would be
a useful addition to avoid networked applications using giant CQ ring
sizes by default... If we had that, you could start smaller and make it
larger if you ran into overflows.

-- 
Jens Axboe