source: doc/theses/thierry_delisle_PhD/thesis/text/io.tex @ 6db62fa

ADTast-experimentalenumpthread-emulationqualifiedEnum
Last change on this file since 6db62fa was 6db62fa, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Added some experiments, some graph generation and a whole lot of text

  • Property mode set to 100644
File size: 37.6 KB
Line 
1\chapter{User Level \io}
2As mentioned in Section~\ref{prev:io}, User-Level \io requires multiplexing the \io operations of many \glspl{thrd} onto fewer \glspl{proc} using asynchronous \io operations.
3Different operating systems offer various forms of asynchronous operations and, as mentioned in Chapter~\ref{intro}, this work is exclusively focused on the Linux operating-system.
4
5\section{Kernel Interface}
6Since this work fundamentally depends on operating-system support, the first step of any design is to discuss the available interfaces and pick one (or more) as the foundations of the non-blocking \io subsystem.
7
8\subsection{\lstinline{O_NONBLOCK}}
9In Linux, files can be opened with the flag @O_NONBLOCK@~\cite{MAN:open} (or @SO_NONBLOCK@~\cite{MAN:accept}, the equivalent for sockets) to use the file descriptors in ``nonblocking mode''.
10In this mode, ``Neither the @open()@ nor any subsequent \io operations on the [opened file descriptor] will cause the calling process to wait''~\cite{MAN:open}.
11This feature can be used as the foundation for the non-blocking \io subsystem.
12However, for the subsystem to know when an \io operation completes, @O_NONBLOCK@ must be use in conjunction with a system call that monitors when a file descriptor becomes ready, \ie, the next \io operation on it does not cause the process to wait
13\footnote{In this context, ready means \emph{some} operation can be performed without blocking.
14It does not mean an operation returning \lstinline{EAGAIN} succeeds on the next try.
15For example, a ready read may only return a subset of bytes and the read must be issues again for the remaining bytes, at which point it may return \lstinline{EAGAIN}.}.
16This mechanism is also crucial in determining when all \glspl{thrd} are blocked and the application \glspl{kthrd} can now block.
17
18There are three options to monitor file descriptors in Linux
19\footnote{For simplicity, this section omits \lstinline{pselect} and \lstinline{ppoll}.
20The difference between these system calls and \lstinline{select} and \lstinline{poll}, respectively, is not relevant for this discussion.},
21@select@~\cite{MAN:select}, @poll@~\cite{MAN:poll} and @epoll@~\cite{MAN:epoll}.
22All three of these options offer a system call that blocks a \gls{kthrd} until at least one of many file descriptors becomes ready.
23The group of file descriptors being waited is called the \newterm{interest set}.
24
25\paragraph{\lstinline{select}} is the oldest of these options, it takes as an input a contiguous array of bits, where each bits represent a file descriptor of interest.
26On return, it modifies the set in place to identify which of the file descriptors changed status.
27This destructive change means that calling select in a loop requires re-initializing the array each time and the number of file descriptors supported has a hard limit.
28Another limit of @select@ is that once the call is started, the interest set can no longer be modified.
29Monitoring a new file descriptor generally requires aborting any in progress call to @select@
30\footnote{Starting a new call to \lstinline{select} is possible but requires a distinct kernel thread, and as a result is not an acceptable multiplexing solution when the interest set is large and highly dynamic unless the number of parallel calls to \lstinline{select} can be strictly bounded.}.
31
32\paragraph{\lstinline{poll}} is an improvement over select, which removes the hard limit on the number of file descriptors and the need to re-initialize the input on every call.
33It works using an array of structures as an input rather than an array of bits, thus allowing a more compact input for small interest sets.
34Like @select@, @poll@ suffers from the limitation that the interest set cannot be changed while the call is blocked.
35
36\paragraph{\lstinline{epoll}} further improves these two functions by allowing the interest set to be dynamically added to and removed from while a \gls{kthrd} is blocked on an @epoll@ call.
37This dynamic capability is accomplished by creating an \emph{epoll instance} with a persistent interest set, which is used across multiple calls.
38This capability significantly reduces synchronization overhead on the part of the caller (in this case the \io subsystem), since the interest set can be modified when adding or removing file descriptors without having to synchronize with other \glspl{kthrd} potentially calling @epoll@.
39
40However, all three of these system calls have limitations.
41The @man@ page for @O_NONBLOCK@ mentions that ``[@O_NONBLOCK@] has no effect for regular files and block devices'', which means none of these three system calls are viable multiplexing strategies for these types of \io operations.
42Furthermore, @epoll@ has been shown to have problems with pipes and ttys~\cit{Peter's examples in some fashion}.
43Finally, none of these are useful solutions for multiplexing \io operations that do not have a corresponding file descriptor and can be awkward for operations using multiple file descriptors.
44
45\subsection{POSIX asynchronous I/O (AIO)}
46An alternative to @O_NONBLOCK@ is the AIO interface.
47Its interface lets programmers enqueue operations to be performed asynchronously by the kernel.
48Completions of these operations can be communicated in various ways: either by spawning a new \gls{kthrd}, sending a Linux signal, or by polling for completion of one or more operation.
49For this work, spawning a new \gls{kthrd} is counter-productive but a related solution is discussed in Section~\ref{io:morethreads}.
50Using interrupts handlers can also lead to fairly complicated interactions between subsystems and has non-trivial cost.
51Leaving polling for completion, which is similar to the previous system calls.
52AIO only supports read and write operations to file descriptors, it does not have the same limitation as @O_NONBLOCK@, \ie, the file descriptors can be regular files and blocked devices.
53It also supports batching multiple operations in a single system call.
54
55AIO offers two different approach to polling: @aio_error@ can be used as a spinning form of polling, returning @EINPROGRESS@ until the operation is completed, and @aio_suspend@ can be used similarly to @select@, @poll@ or @epoll@, to wait until one or more requests have completed.
56For the purpose of \io multiplexing, @aio_suspend@ is the best interface.
57However, even if AIO requests can be submitted concurrently, @aio_suspend@ suffers from the same limitation as @select@ and @poll@, \ie, the interest set cannot be dynamically changed while a call to @aio_suspend@ is in progress.
58AIO also suffers from the limitation of specifying which requests have completed, \ie programmers have to poll each request in the interest set using @aio_error@ to identify the completed requests.
59This limitation means that, like @select@ and @poll@ but not @epoll@, the time needed to examine polling results increases based on the total number of requests monitored, not the number of completed requests.
60Finally, AIO does not seem to be a popular interface, which I believe is due in part to this poor polling interface.
61Linus Torvalds talks about this interface as follows:
62
63\begin{displayquote}
64        AIO is a horrible ad-hoc design, with the main excuse being ``other,
65        less gifted people, made that design, and we are implementing it for
66        compatibility because database people - who seldom have any shred of
67        taste - actually use it''.
68
69        But AIO was always really really ugly.
70
71        \begin{flushright}
72                -- Linus Torvalds\cit{https://lwn.net/Articles/671657/}
73        \end{flushright}
74\end{displayquote}
75
76Interestingly, in this e-mail, Linus goes on to describe
77``a true \textit{asynchronous system call} interface''
78that does
79``[an] arbitrary system call X with arguments A, B, C, D asynchronously using a kernel thread''
80in
81``some kind of arbitrary \textit{queue up asynchronous system call} model''.
82This description is actually quite close to the interface described in the next section.
83
84\subsection{\lstinline{io_uring}}
85A very recent addition to Linux, @io_uring@~\cite{MAN:io_uring}, is a framework that aims to solve many of the problems listed in the above interfaces.
86Like AIO, it represents \io operations as entries added to a queue.
87But like @epoll@, new requests can be submitted while a blocking call waiting for requests to complete is already in progress.
88The @io_uring@ interface uses two ring buffers (referred to simply as rings) at its core: a submit ring to which programmers push \io requests and a completion ring from which programmers poll for completion.
89
90One of the big advantages over the prior interfaces is that @io_uring@ also supports a much wider range of operations.
91In addition to supporting reads and writes to any file descriptor like AIO, it supports other operations like @open@, @close@, @fsync@, @accept@, @connect@, @send@, @recv@, @splice@, \etc.
92
93On top of these, @io_uring@ adds many extras like avoiding copies between the kernel and user-space using shared memory, allowing different mechanisms to communicate with device drivers, and supporting chains of requests, \ie, requests that automatically trigger followup requests on completion.
94
95\subsection{Extra Kernel Threads}\label{io:morethreads}
96Finally, if the operating system does not offer a satisfactory form of asynchronous \io operations, an ad-hoc solution is to create a pool of \glspl{kthrd} and delegate operations to it to avoid blocking \glspl{proc}, which is a compromise for multiplexing.
97In the worst case, where all \glspl{thrd} are consistently blocking on \io, it devolves into 1-to-1 threading.
98However, regardless of the frequency of \io operations, it achieves the fundamental goal of not blocking \glspl{proc} when \glspl{thrd} are ready to run.
99This approach is used by languages like Go\cit{Go} and frameworks like libuv\cit{libuv}, since it has the advantage that it can easily be used across multiple operating systems.
100This advantage is especially relevant for languages like Go, which offer a homogeneous \glsxtrshort{api} across all platforms.
101As opposed to C, which has a very limited standard api for \io, \eg, the C standard library has no networking.
102
103\subsection{Discussion}
104These options effectively fall into two broad camps: waiting for \io to be ready versus waiting for \io to complete.
105All operating systems that support asynchronous \io must offer an interface along one of these lines, but the details vary drastically.
106For example, Free BSD offers @kqueue@~\cite{MAN:bsd/kqueue}, which behaves similarly to @epoll@, but with some small quality of use improvements, while Windows (Win32)~\cit{https://docs.microsoft.com/en-us/windows/win32/fileio/synchronous-and-asynchronous-i-o} offers ``overlapped I/O'', which handles submissions similarly to @O_NONBLOCK@ with extra flags on the synchronous system call, but waits for completion events, similarly to @io_uring@.
107
108For this project, I selected @io_uring@, in large parts because of its generality.
109While @epoll@ has been shown to be a good solution for socket \io (\cite{DBLP:journals/pomacs/KarstenB20}), @io_uring@'s transparent support for files, pipes, and more complex operations, like @splice@ and @tee@, make it a better choice as the foundation for a general \io subsystem.
110
111\section{Event-Engine}
112An event engine's responsibility is to use the kernel interface to multiplex many \io operations onto few \glspl{kthrd}.
113In concrete terms, this means \glspl{thrd} enter the engine through an interface, the event engines then starts the operation and parks the calling \glspl{thrd}, returning control to the \gls{proc}.
114The parked \glspl{thrd} are then rescheduled by the event engine once the desired operation has completed.
115
116\subsection{\lstinline{io_uring} in depth}
117Before going into details on the design of my event engine, more details on @io_uring@ usage are presented, each important in the design of the engine.
118Figure~\ref{fig:iouring} shows an overview of an @io_uring@ instance.
119Two ring buffers are used to communicate with the kernel: one for submissions~(left) and one for completions~(right).
120The submission ring contains entries, \newterm{Submit Queue Entries} (SQE), produced (appended) by the application when an operation starts and then consumed by the kernel.
121The completion ring contains entries, \newterm{Completion Queue Entries} (CQE), produced (appended) by the kernel when an operation completes and then consumed by the application.
122The submission ring contains indexes into the SQE array (denoted \emph{S} in the figure) containing entries describing the I/O operation to start;
123the completion ring contains entries for the completed I/O operation.
124Multiple @io_uring@ instances can be created, in which case they each have a copy of the data structures in the figure.
125
126\begin{figure}
127        \centering
128        \input{io_uring.pstex_t}
129        \caption[Overview of \lstinline{io_uring}]{Overview of \lstinline{io_uring} \smallskip\newline Two ring buffer are used to communicate with the kernel, one for completions~(right) and one for submissions~(left). The submission ring indexes into a pre-allocated array (denoted \emph{S}) instead.}
130        \label{fig:iouring}
131\end{figure}
132
133New \io operations are submitted to the kernel following 4 steps, which use the components shown in the figure.
134\begin{enumerate}
135\item
136An SQE is allocated from the pre-allocated array (denoted \emph{S} in Figure~\ref{fig:iouring}).
137This array is created at the same time as the @io_uring@ instance, is in kernel-locked memory visible by both the kernel and the application, and has a fixed size determined at creation.
138How these entries are allocated is not important for the functioning of @io_uring@, the only requirement is that no entry is reused before the kernel has consumed it.
139\item
140The SQE is filled according to the desired operation.
141This step is straight forward, the only detail worth mentioning is that SQEs have a @user_data@ field that must be filled in order to match submission and completion entries.
142\item
143The SQE is submitted to the submission ring by appending the index of the SQE to the ring following regular ring buffer steps: \lstinline{buffer[head] = item; head++}.
144Since the head is visible to the kernel, some memory barriers may be required to prevent the compiler from reordering these operations.
145Since the submission ring is a regular ring buffer, more than one SQE can be added at once and the head is updated only after all entries are updated.
146\item
147The kernel is notified of the change to the ring using the system call @io_uring_enter@.
148The number of elements appended to the submission ring is passed as a parameter and the number of elements consumed is returned.
149The @io_uring@ instance can be constructed so this step is not required, but this requires elevated privilege.% and an early version of @io_uring@ had additional restrictions.
150\end{enumerate}
151
152\begin{sloppypar}
153The completion side is simpler: applications call @io_uring_enter@ with the flag @IORING_ENTER_GETEVENTS@ to wait on a desired number of operations to complete.
154The same call can be used to both submit SQEs and wait for operations to complete.
155When operations do complete, the kernel appends a CQE to the completion ring and advances the head of the ring.
156Each CQE contains the result of the operation as well as a copy of the @user_data@ field of the SQE that triggered the operation.
157It is not necessary to call @io_uring_enter@ to get new events because the kernel can directly modify the completion ring.
158The system call is only needed if the application wants to block waiting for operations to complete.
159\end{sloppypar}
160
161The @io_uring_enter@ system call is protected by a lock inside the kernel.
162This protection means that concurrent call to @io_uring_enter@ using the same instance are possible, but there is no performance gained from parallel calls to @io_uring_enter@.
163It is possible to do the first three submission steps in parallel, however, doing so requires careful synchronization.
164
165@io_uring@ also introduces constraints on the number of simultaneous operations that can be ``in flight''.
166Obviously, SQEs are allocated from a fixed-size array, meaning that there is a hard limit to how many SQEs can be submitted at once.
167In addition, the @io_uring_enter@ system call can fail because ``The  kernel [...] ran out of resources to handle [a request]'' or ``The application is attempting to overcommit the number of requests it can  have  pending.''.
168This restriction means \io request bursts may have to be subdivided and submitted in chunks at a later time.
169
170\subsection{Multiplexing \io: Submission}
171The submission side is the most complicated aspect of @io_uring@ and the completion side effectively follows from the design decisions made in the submission side.
172While it is possible to do the first steps of submission in parallel, the duration of the system call scales with number of entries submitted.
173The consequence is that the amount of parallelism used to prepare submissions for the next system call is limited.
174Beyond this limit, the length of the system call is the throughput limiting factor.
175I concluded from early experiments that preparing submissions seems to take at most as long as the system call itself, which means that with a single @io_uring@ instance, there is no benefit in terms of \io throughput to having more than two \glspl{hthrd}.
176Therefore the design of the submission engine must manage multiple instances of @io_uring@ running in parallel, effectively sharding @io_uring@ instances.
177Similarly to scheduling, this sharding can be done privately, \ie, one instance per \glspl{proc}, in decoupled pools, \ie, a pool of \glspl{proc} use a pool of @io_uring@ instances without one-to-one coupling between any given instance and any given \gls{proc}, or some mix of the two.
178Since completions are sent to the instance where requests were submitted, all instances with pending operations must be polled continously
179\footnote{As will be described in Chapter~\ref{practice}, this does not translate into constant cpu usage.}.
180Note that once an operation completes, there is nothing that ties it to the @io_uring@ instance that handled it.
181There is nothing preventing a new operation with, for example, the same file descriptors to a different @io_uring@ instance.
182
183A complicating aspect of submission is @io_uring@'s support for chains of operations, where the completion of an operation triggers the submission of the next operation on the link.
184SQEs forming a chain must be allocated from the same instance and must be contiguous in the Submission Ring (see Figure~\ref{fig:iouring}).
185The consequence of this feature is that filling SQEs can be arbitrarly complex and therefore users may need to run arbitrary code between allocation and submission.
186Supporting chains is a requirement of the \io subsystem, but it is still valuable.
187Support for this feature can be fulfilled simply to supporting arbitrary user code between allocation and submission.
188
189\subsubsection{Public Instances}
190One approach is to have multiple shared instances.
191\Glspl{thrd} attempting \io operations pick one of the available instances and submit operations to that instance.
192Since there is no coupling between \glspl{proc} and @io_uring@ instances in this approach, \glspl{thrd} running on more than one \gls{proc} can attempt to submit to the same instance concurrently.
193Since @io_uring@ effectively sets the amount of sharding needed to avoid contention on its internal locks, performance in this approach is based on two aspects: the synchronization needed to submit does not induce more contention than @io_uring@ already does and the scheme to route \io requests to specific @io_uring@ instances does not introduce contention.
194This second aspect has an oversized importance because it comes into play before the sharding of instances, and as such, all \glspl{hthrd} can contend on the routing algorithm.
195
196Allocation in this scheme can be handled fairly easily.
197Free SQEs, \ie, SQEs that aren't currently being used to represent a request, can be written to safely and have a field called @user_data@ which the kernel only reads to copy to @cqe@s.
198Allocation also requires no ordering guarantee as all free SQEs are interchangeable.
199This requires a simple concurrent bag.
200The only added complexity is that the number of SQEs is fixed, which means allocation can fail.
201
202Allocation failures need to be pushed up to a routing algorithm: \glspl{thrd} attempting \io operations must not be directed to @io_uring@ instances without sufficient SQEs available.
203Furthermore, the routing algorithm should block operations up-front if none of the instances have available SQEs.
204
205Once an SQE is allocated, \glspl{thrd} can fill them normally, they simply need to keep track of the SQE index and which instance it belongs to.
206
207Once an SQE is filled in, what needs to happen is that the SQE must be added to the submission ring buffer, an operation that is not thread-safe on itself, and the kernel must be notified using the @io_uring_enter@ system call.
208The submission ring buffer is the same size as the pre-allocated SQE buffer, therefore pushing to the ring buffer cannot fail
209\footnote{This is because it is invalid to have the same \lstinline{sqe} multiple times in the ring buffer.}.
210However, as mentioned, the system call itself can fail with the expectation that it will be retried once some of the already submitted operations complete.
211Since multiple SQEs can be submitted to the kernel at once, it is important to strike a balance between batching and latency.
212Operations that are ready to be submitted should be batched together in few system calls, but at the same time, operations should not be left pending for long period of times before being submitted.
213This can be handled by either designating one of the submitting \glspl{thrd} as the being responsible for the system call for the current batch of SQEs or by having some other party regularly submitting all ready SQEs, \eg, the poller \gls{thrd} mentioned later in this section.
214
215In the case of designating a \gls{thrd}, ideally, when multiple \glspl{thrd} attempt to submit operations to the same @io_uring@ instance, all requests would be batched together and one of the \glspl{thrd} would do the system call on behalf of the others, referred to as the \newterm{submitter}.
216In practice however, it is important that the \io requests are not left pending indefinitely and as such, it may be required to have a ``next submitter'' that guarentees everything that is missed by the current submitter is seen by the next one.
217Indeed, as long as there is a ``next'' submitter, \glspl{thrd} submitting new \io requests can move on, knowing that some future system call will include their request.
218Once the system call is done, the submitter must also free SQEs so that the allocator can reused them.
219
220Finally, the completion side is much simpler since the @io_uring@ system call enforces a natural synchronization point.
221Polling simply needs to regularly do the system call, go through the produced CQEs and communicate the result back to the originating \glspl{thrd}.
222Since CQEs only own a signed 32 bit result, in addition to the copy of the @user_data@ field, all that is needed to communicate the result is a simple future~\cite{wiki:future}.
223If the submission side does not designate submitters, polling can also submit all SQEs as it is polling events.
224A simple approach to polling is to allocate a \gls{thrd} per @io_uring@ instance and simply let the poller \glspl{thrd} poll their respective instances when scheduled.
225
226With this pool of instances approach, the big advantage is that it is fairly flexible.
227It does not impose restrictions on what \glspl{thrd} submitting \io operations can and cannot do between allocations and submissions.
228It also can gracefully handle running out of ressources, SQEs or the kernel returning @EBUSY@.
229The down side to this is that many of the steps used for submitting need complex synchronization to work properly.
230The routing and allocation algorithm needs to keep track of which ring instances have available SQEs, block incoming requests if no instance is available, prevent barging if \glspl{thrd} are already queued up waiting for SQEs and handle SQEs being freed.
231The submission side needs to safely append SQEs to the ring buffer, correctly handle chains, make sure no SQE is dropped or left pending forever, notify the allocation side when SQEs can be reused and handle the kernel returning @EBUSY@.
232All this synchronization may have a significant cost and, compared to the next approach presented, this synchronization is entirely overhead.
233
234\subsubsection{Private Instances}
235Another approach is to simply create one ring instance per \gls{proc}.
236This alleviates the need for synchronization on the submissions, requiring only that \glspl{thrd} are not interrupted in between two submission steps.
237This is effectively the same requirement as using @thread_local@ variables.
238Since SQEs that are allocated must be submitted to the same ring, on the same \gls{proc}, this effectively forces the application to submit SQEs in allocation order
239\footnote{The actual requirement is that \glspl{thrd} cannot context switch between allocation and submission.
240This requirement means that from the subsystem's point of view, the allocation and submission are sequential.
241To remove this requirement, a \gls{thrd} would need the ability to ``yield to a specific \gls{proc}'', \ie, park with the promise that it will be run next on a specific \gls{proc}, the \gls{proc} attached to the correct ring.}
242, greatly simplifying both allocation and submission.
243In this design, allocation and submission form a partitionned ring buffer as shown in Figure~\ref{fig:pring}.
244Once added to the ring buffer, the attached \gls{proc} has a significant amount of flexibility with regards to when to do the system call.
245Possible options are: when the \gls{proc} runs out of \glspl{thrd} to run, after running a given number of \glspl{thrd}, etc.
246
247\begin{figure}
248        \centering
249        \input{pivot_ring.pstex_t}
250        \caption[Partitioned ring buffer]{Partitioned ring buffer \smallskip\newline Allocated sqes are appending to the first partition.
251        When submitting, the partition is advanced.
252        The kernel considers the partition as the head of the ring.}
253        \label{fig:pring}
254\end{figure}
255
256This approach has the advantage that it does not require much of the synchronization needed in the shared approach.
257This comes at the cost that \glspl{thrd} submitting \io operations have less flexibility, they cannot park or yield, and several exceptional cases are handled poorly.
258Instances running out of SQEs cannot run \glspl{thrd} wanting to do \io operations, in such a case the \gls{thrd} needs to be moved to a different \gls{proc}, the only current way of achieving this would be to @yield()@ hoping to be scheduled on a different \gls{proc}, which is not guaranteed.
259
260A more involved version of this approach can seem to solve most of these problems, using a pattern called \newterm{helping}.
261\Glspl{thrd} that wish to submit \io operations but cannot do so
262\footnote{either because of an allocation failure or because they were migrate to a different \gls{proc} between allocation and submission}
263create an object representing what they wish to achieve and add it to a list somewhere.
264For this particular problem, one solution would be to have a list of pending submissions per \gls{proc} and a list of pending allocations, probably per cluster.
265The problem with these ``solutions'' is that they are still bound by the strong coupling between \glspl{proc} and @io_uring@ instances.
266These data structures would allow moving \glspl{thrd} to a specific \gls{proc} when the current \gls{proc} cannot fulfill the \io request.
267
268Imagine a simple case with two \glspl{thrd} on two \glspl{proc}, one \gls{thrd} submits an \io operation and then sets a flag, the other \gls{thrd} spins until the flag is set.
269If the first \gls{thrd} is preempted between allocation and submission and moves to the other \gls{proc}, the original \gls{proc} could start running the spinning \gls{thrd}.
270If this happens, the helping ``solution'' is for the \io \gls{thrd}to added append an item to the submission list of the \gls{proc} where the allocation was made.
271No other \gls{proc} can help the \gls{thrd} since @io_uring@ instances are strongly coupled to \glspl{proc}.
272However, in this case, the \gls{proc} is unable to help because it is executing the spinning \gls{thrd} mentioned when first expression this case
273\footnote{This particular example is completely artificial, but in the presence of many more \glspl{thrd}, it is not impossible that this problem would arise ``in the wild''.
274Furthermore, this pattern is difficult to reliably detect and avoid.}
275resulting in a deadlock.
276Once in this situation, the only escape is to interrupted the execution of the \gls{thrd}, either directly or due to regular preemption, only then can the \gls{proc} take the time to handle the pending request to help.
277Interrupting \glspl{thrd} for this purpose is far from desireable, the cost is significant and the situation may be hard to detect.
278However, a more subtle reason why interrupting the \gls{thrd} is not a satisfying solution is that the \gls{proc} is not actually using the instance it is tied to.
279If it were to use it, then helping could be done as part of the usage.
280Interrupts are needed here entirely because the \gls{proc} is tied to an instance it is not using.
281Therefore a more satisfying solution would be for the \gls{thrd} submitting the operation to simply notice that the instance is unused and simply go ahead and use it.
282This is the approach presented next.
283
284\subsubsection{Instance borrowing}
285Both of the approaches presented above have undesirable aspects that stem from too loose or too tight coupling between @io_uring@ and \glspl{proc}.
286In the first approach, loose coupling meant that all operations have synchronization overhead that a tighter coupling can avoid.
287The second approach on the other hand suffers from tight coupling causing problems when the \gls{proc} do not benefit from the coupling.
288While \glspl{proc} are continously issuing \io operations tight coupling is valuable since it avoids synchronization costs.
289However, in unlikely failure cases or when \glspl{proc} are not making use of their instance, tight coupling is no longer advantageous.
290A compromise between these approaches would be to allow tight coupling but have the option to revoke this coupling dynamically when failure cases arise.
291I call this approach ``instance borrowing''\footnote{While it looks similar to work-sharing and work-stealing, I think it is different enough from either to warrant a different verb to avoid confusion.}.
292
293In this approach, each cluster owns a pool of @io_uring@ instances managed by an arbiter.
294When a \gls{thrd} attempts to issue an \io operation, it ask for an instance from the arbiter and issues requests to that instance.
295However, in doing so it ties to the instance to the \gls{proc} it is currently running on.
296This coupling is kept until the arbiter decides to revoke it, taking back the instance and reverting the \gls{proc} to its initial state with respect to \io.
297This tight coupling means that synchronization can be minimal since only one \gls{proc} can use the instance at any given time, akin to the private instances approach.
298However, where it differs is that revocation from the arbiter means this approach does not suffer from the deadlock scenario described above.
299
300Arbitration is needed in the following cases:
301\begin{enumerate}
302        \item The current \gls{proc} does not currently hold an instance.
303        \item The current instance does not have sufficient SQEs to satisfy the request.
304        \item The current \gls{proc} has the wrong instance, this happens if the submitting \gls{thrd} context-switched between allocation and submission.
305        I will refer to these as \newterm{External Submissions}.
306\end{enumerate}
307However, even when the arbiter is not directly needed, \glspl{proc} need to make sure that their ownership of the instance is not being revoked.
308This can be accomplished by a lock-less handshake\footnote{Note that the handshake is not Lock-\emph{Free} since it lacks the proper progress guarantee.}.
309A \gls{proc} raises a local flag before using its borrowed instance and checks if the instance is marked as revoked or if the arbiter has raised its flag.
310If not it proceeds, otherwise it delegates the operation to the arbiter.
311Once the operation is completed, the \gls{proc} lowers its local flag.
312
313Correspondingly, before revoking an instance the arbiter marks the instance and then waits for the \gls{proc} using it to lower its local flag.
314Only then does it reclaim the instance and potentially assign it to an other \gls{proc}.
315
316The arbiter maintains four lists around which it makes its decisions:
317\begin{enumerate}
318        \item A list of pending submissions.
319        \item A list of pending allocations.
320        \item A list of instances currently borrowed by \glspl{proc}.
321        \item A list of instances currently available.
322\end{enumerate}
323
324\paragraph{External Submissions} are handled by the arbiter by revoking the appropriate instance and adding the submission to the submission ring.
325There is no need to immediately revoke the instance however.
326External submissions must simply be added to the ring before the next system call, \ie, when the submission ring is flushed.
327This means that whoever is responsible for the system call first checks if the instance has any external submissions.
328If it is the case, it asks the arbiter to revoke the instance and add the external submissions to the ring.
329
330\paragraph{Pending Allocations} can be more complicated to handle.
331If the arbiter has available instances, the arbiter can attempt to directly hand over the instance and satisfy the request.
332Otherwise it must hold onto the list of threads until SQEs are made available again.
333This handling becomes that much more complex if pending allocation require more than one SQE, since the arbiter must make a decision between statisfying requests in FIFO ordering or satisfy requests for fewer SQEs first.
334
335While this arbiter has the potential to solve many of the problems mentionned in above, it also introduces a significant amount of complexity.
336Tracking which processors are borrowing which instances and which instances have SQEs available ends-up adding a significant synchronization prelude to any I/O operation.
337Any submission must start with a handshake that pins the currently borrowed instance, if available.
338An attempt to allocate is then made, but the arbiter can concurrently be attempting to allocate from the same instance from a different \gls{hthrd}.
339Once the allocation is completed, the submission must still check that the instance is still burrowed before attempt to flush.
340These extra synchronization steps end-up having a similar cost to the multiple shared instances approach.
341Furthermore, if the number of instances does not match the number of processors actively submitting I/O, the system can fall into a state where instances are constantly being revoked and end-up cycling the processors, which leads to significant cache deterioration.
342Because of these reasons, this approach, which sounds promising on paper, does not improve on the private instance approach in practice.
343
344\subsubsection{Private Instances V2}
345
346
347
348% Verbs of this design
349
350% Allocation: obtaining an sqe from which to fill in the io request, enforces the io instance to use since it must be the one which provided the sqe. Must interact with the arbiter if the instance does not have enough sqe for the allocation. (Typical allocation will ask for only one sqe, but chained sqe must be allocated from the same context so chains of sqe must be allocated in bulks)
351
352% Submition: simply adds the sqe(s) to some data structure to communicate that they are ready to go. This operation can't fail because there are as many spots in the submit buffer than there are sqes. Must interact with the arbiter only if the thread was moved between the allocation and the submission.
353
354% Flushing: Taking all the sqes that were submitted and making them visible to the kernel, also counting them in order to figure out what to_submit should be. Must be thread-safe with submission. Has to interact with the Arbiter if there are external submissions. Can't simply use a protected queue because adding to the array is not safe if the ring is still available for submitters. Flushing must therefore: check if there are external pending requests if so, ask the arbiter to flush otherwise use the fast flush operation.
355
356% Collect: Once the system call is done, it returns how many sqes were consumed by the system. These must be freed for allocation. Must interact with the arbiter to notify that things are now ready.
357
358% Handle: process all the produced cqe. No need to interact with any of the submission operations or the arbiter.
359
360
361
362
363% alloc():
364%       proc.io->in_use = true, __ATOMIC_ACQUIRE
365%       if cltr.io.flag || !proc.io || proc.io->flag:
366%               return alloc_slow(cltr.io, proc.io)
367
368%       a = alloc_fast(proc.io)
369%       if a:
370%               proc.io->in_use = false, __ATOMIC_RELEASE
371%               return a
372
373%       return alloc_slow(cltr.io)
374
375% alloc_fast()
376%       left = proc.io->submit_q.free.tail - proc.io->submit_q.free.head
377%       if num_entries - left < want:
378%               return None
379
380%       a = ready[head]
381%       head = head + 1, __ATOMIC_RELEASE
382
383% alloc_slow()
384%       cltr.io.flag = true, __ATOMIC_ACQUIRE
385%       while(proc.io && proc.io->in_use) pause;
386
387
388
389% submit(a):
390%       proc.io->in_use = true, __ATOMIC_ACQUIRE
391%       if cltr.io.flag || proc.io != alloc.io || proc.io->flag:
392%               return submit_slow(cltr.io)
393
394%       submit_fast(proc.io, a)
395%       proc.io->in_use = false, __ATOMIC_RELEASE
396
397% polling()
398%       loop:
399%               yield
400%               flush()
401%               io_uring_enter
402%               collect
403%               handle()
404
405\section{Interface}
406Finally, the last important part of the \io subsystem is it's interface. There are multiple approaches that can be offered to programmers, each with advantages and disadvantages. The new \io subsystem can replace the C runtime's API or extend it. And in the later case the interface can go from very similar to vastly different. The following sections discuss some useful options using @read@ as an example. The standard Linux interface for C is :
407
408@ssize_t read(int fd, void *buf, size_t count);@.
409
410\subsection{Replacement}
411Replacing the C \glsxtrshort{api}
412
413\subsection{Synchronous Extension}
414
415\subsection{Asynchronous Extension}
416
417\subsection{Interface directly to \lstinline{io_uring}}
Note: See TracBrowser for help on using the repository browser.