Changeset c65b930
- Timestamp:
- May 25, 2021, 4:15:06 PM (3 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 375fb46, 82f4063
- Parents:
- b984d54 (diff), 887fc79 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - Files:
-
- 3 added
- 9 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/cfalab.sty
rb984d54 rc65b930 126 126 } 127 127 128 % \snake{<identifier>} 129 % Improves writing of snake case (or any convention that uses _) by allowing 130 % line breaks after _. Disables commands inside the block and formats the 131 % identifier to look like code. 132 \newcommand*\snake[1]{\snakefont{\expandafter\snake@next\detokenize{#1}\@nil}} 133 134 % \snakefont{<text>} 135 % Command used by \snake, you may renew the command to change its formating. 136 \newcommand*\snakefont[1]{\texttt{#1}} 137 138 % Thanks Manuel of TeX Stack exchange. (I got the base pattern from one of 139 % their answers.) Note: \@nil should never be defined. 140 \newcommand*\snake@next[1]{\ifx\@nil#1\else 141 \expandafter\ifx\string_#1\string_\allowbreak\else#1\fi 142 \expandafter\snake@next\fi 143 } 144 128 145 % common.tex Compatablity =================================================== 129 146 % Below this line is for compatability with the old common.tex file. -
doc/theses/andrew_beach_MMath/existing.tex
rb984d54 rc65b930 199 199 forall(dtype T) 200 200 struct node { 201 node(T) * next; // generic linked node201 node(T) * next; 202 202 T * data; 203 203 } … … 238 238 \begin{cfa} 239 239 coroutine CountUp { 240 unsigned int next; // communication variable240 unsigned int next; 241 241 } 242 242 CountUp countup; … … 308 308 { 309 309 StringWorker stringworker; // fork thread running in "main" 310 } // implicitly join with thread $\(\Rightarrow\)$wait for completion310 } // <- implicitly join with thread / wait for completion 311 311 \end{cfa} 312 312 The thread main is where a new thread starts execution after a fork operation -
doc/theses/andrew_beach_MMath/features.tex
rb984d54 rc65b930 115 115 116 116 \paragraph{Communication} 117 For effective exception handling, additional information is usuallypassed117 For effective exception handling, additional information is often passed 118 118 from the raise to the handler. 119 119 So far only communication of the exceptions' identity has been covered. … … 327 327 \end{cfa} 328 328 When viewed on its own, a try statement will simply execute the statements 329 in @GUARDED_BLOCK@and when those are finished the try statement finishes.329 in \snake{GUARDED_BLOCK} and when those are finished the try statement finishes. 330 330 331 331 However, while the guarded statements are being executed, including any … … 343 343 344 344 If no termination handler is found during the search then the default handler 345 ( @defaultTerminationHandler@) is run.345 (\defaultTerminationHandler) is run. 346 346 Through \CFA's trait system the best match at the throw sight will be used. 347 347 This function is run and is passed the copied exception. After the default … … 421 421 execution continues after the raise statement. 422 422 423 There is a global @defaultResumptionHandler@is polymorphic over all423 There is a global \defaultResumptionHandler{} is polymorphic over all 424 424 termination exceptions and preforms a termination throw on the exception. 425 The @defaultTerminationHandler@ for that raise is matched at the original426 raise statement (the resumption @throwResume@) and it can be customized by 427 introducing a new or better match as well.425 The \defaultTerminationHandler{} for that raise is matched at the 426 original raise statement (the resumption @throw@\-@Resume@) and it can be 427 customized by introducing a new or better match as well. 428 428 429 429 \subsubsection{Resumption Marking} … … 681 681 @CoroutineCancelled@ exception, which contains a references to the cancelled 682 682 coroutine and the exception used to cancel it. 683 The resume function also takes the @defaultResumptionHandler@from the683 The resume function also takes the \defaultResumptionHandler{} from the 684 684 caller's context and passes it to the internal report. 685 685 -
doc/theses/andrew_beach_MMath/implement.tex
rb984d54 rc65b930 16 16 Virtual types only have one change to their structure: the addition of a 17 17 pointer to the virtual table, which is called the \emph{virtual-table pointer}. 18 Internally, the field is called @virtual_table@.18 Internally, the field is called \snake{virtual_table}. 19 19 The field is fixed after construction. It is always the first field in the 20 20 structure so that its location is always known. … … 124 124 125 125 \begin{figure} 126 \begin{cfa} 127 type_id 128 parent_field0 129 ... 130 parent_fieldN 131 child_field0 132 ... 133 child_fieldN 134 \end{cfa} 126 \input{vtable-layout} 135 127 \caption{Virtual Table Layout} 136 128 \label{f:VirtualTableLayout} … … 171 163 coroutine Example { 172 164 // fields 173 } 165 }; 174 166 \end{cfa} 175 167 … … 329 321 To get full unwinding support all of this has to be done directly with 330 322 assembly and assembler directives. Partiularly the cfi directives 331 \ texttt{.cfi\_lsda} and \texttt{.cfi\_personality}.323 \snake{.cfi_lsda} and \snake{.cfi_personality}. 332 324 333 325 \subsection{Personality Functions} … … 337 329 A personality function can preform different actions depending on how it is 338 330 called. 339 \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] 340 typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) ( 341 _Unwind_Action @action@, 342 _Unwind_Exception_Class @exception_class@, 343 _Unwind_Exception * @exception@, 344 struct _Unwind_Context * @context@ 345 ); 331 \begin{lstlisting} 332 typedef _Unwind_Reason_Code (*_Unwind_Personality_Fn) ( 333 _Unwind_Action action, 334 _Unwind_Exception_Class exception_class, 335 _Unwind_Exception * exception, 336 struct _Unwind_Context * context); 346 337 \end{lstlisting} 347 338 The @action@ argument is a bitmask of possible actions: … … 427 418 function and the stop parameter. The stop function has a similar interface as a 428 419 personality function, except it is also passed the stop parameter. 429 \begin{lstlisting} [language=C,{moredelim=**[is][\color{red}]{@}{@}}]430 typedef _Unwind_Reason_Code (* @_Unwind_Stop_Fn@)(431 _Unwind_Action @action@,432 _Unwind_Exception_Class @exception_class@,433 _Unwind_Exception * @exception@,434 struct _Unwind_Context * @context@,435 void * @stop_parameter@);420 \begin{lstlisting} 421 typedef _Unwind_Reason_Code (*_Unwind_Stop_Fn)( 422 _Unwind_Action action, 423 _Unwind_Exception_Class exception_class, 424 _Unwind_Exception * exception, 425 struct _Unwind_Context * context, 426 void * stop_parameter); 436 427 \end{lstlisting} 437 428 … … 446 437 \begin{sloppypar} 447 438 Its arguments are the same as the paired personality function. The actions 448 @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@are always set when it is439 \snake{_UA_CLEANUP_PHASE} and \snake{_UA_FORCE_UNWIND} are always set when it is 449 440 called. Beyond the libunwind standard, both GCC and Clang add an extra action 450 on the last call at the end of the stack: @_UA_END_OF_STACK@.441 on the last call at the end of the stack: \snake{_UA_END_OF_STACK}. 451 442 \end{sloppypar} 452 443 … … 465 456 466 457 The exception context should be retrieved by calling the function 467 @this_exception_context@. For sequential execution, this function is defined as 458 \snake{this_exception_context}. 459 For sequential execution, this function is defined as 468 460 a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is 469 461 concurrent, it links with @libcfathread@, where this function is defined with a … … 493 485 494 486 \begin{figure} 495 \begin{verbatim} 496 Fixed Header | _Unwind_Exception <- pointer target 497 | 498 | Cforall storage 499 | 500 Variable Body | the exception <- fixed offset 501 V ... 502 \end{verbatim} 487 \input{exception-layout} 503 488 \caption{Exception Layout} 504 489 \label{f:ExceptionLayout} … … 525 510 \begin{figure} 526 511 \centering 527 % Andrew: Figure out what these do and give them better names. 528 \newsavebox{\myboxA} 529 \newsavebox{\myboxB} 530 \begin{lrbox}{\myboxA} 512 \newsavebox{\codeBox} 513 \newsavebox{\stackBox} 514 \begin{lrbox}{\codeBox} 531 515 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}] 532 516 unsigned num_exceptions = 0; … … 551 535 \end{lrbox} 552 536 553 \begin{lrbox}{\ myboxB}537 \begin{lrbox}{\stackBox} 554 538 \begin{lstlisting} 539 | try-finally 540 | try-catch (Example) 541 throws() 542 | try-finally 543 | try-catch (Example) 544 throws() 545 | try-finally 546 | try-catch (Example) 547 throws() 548 main() 555 549 \end{lstlisting} 556 550 \end{lrbox} 557 551 558 {\usebox\ myboxA}552 {\usebox\codeBox} 559 553 \hspace{25pt} 560 {\usebox\ myboxB}554 {\usebox\stackBox} 561 555 562 556 \caption{Multiple Exceptions} … … 647 641 { 648 642 Exception1 * name1; 649 if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) { 643 if (name1 = (virtual Exception1 *)__exception_inst 644 && check(name1)) { 650 645 return 1; 651 646 } … … 732 727 { 733 728 Exception1 * name1; 734 if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) { 729 if (name1 = (virtual Exception1 *)__exception_inst 730 && check(name1)) { 735 731 // CATCH BLOCK 1 736 732 return 1; … … 775 771 776 772 \begin{figure} 777 \begin{minipage}[l][][b]{0,2\textwidth} 778 \begin{verbatim} 779 780 781 X <- 782 | 783 V 784 X 785 | 786 V 787 X 788 \end{verbatim} 789 Initial State 790 \end{minipage} 791 \begin{minipage}[l][][b]{0,2\textwidth} 792 \begin{verbatim} 793 794 795 X 796 | 797 V 798 X <- 799 | 800 V 801 X 802 \end{verbatim} 803 Handler Found 804 \end{minipage} 805 \begin{minipage}[l][][b]{0,2\textwidth} 806 \begin{verbatim} 807 X <- 808 / 809 / X 810 | | 811 \ V 812 X 813 | 814 V 815 X 816 \end{verbatim} 817 Try Block Added 818 \end{minipage} 819 \begin{minipage}[l][][b]{0,2\textwidth} 820 \begin{verbatim} 821 822 823 X <- 824 | 825 V 826 X 827 | 828 V 829 X 830 \end{verbatim} 831 Handler Done 832 \end{minipage} 773 \input{resumption-marking} 833 774 \caption{Resumption Marking} 834 775 \label{f:ResumptionMarking} -
doc/theses/andrew_beach_MMath/uw-ethesis.tex
rb984d54 rc65b930 202 202 \makeglossaries 203 203 204 % New commands/options for this document alone: 205 % Code snipits with formating and line-breaks. 206 \newcommand\defaultResumptionHandler{\texttt{default\-Resumption\-Handler}} 207 \newcommand\defaultTerminationHandler{\texttt{default\-Termination\-Handler}} 208 204 209 % listings package configuation: 205 210 \lstMakeShortInline@ -
doc/theses/thierry_delisle_PhD/thesis/fig/pivot_ring.fig
rb984d54 rc65b930 11 11 1 1 1.00 60.00 120.00 12 12 6 225 2475 1665 2835 13 4 2 0 50 -1 0 12 0.0000 6 135 810 1665 2610 Allocated\001 13 14 4 2 0 50 -1 0 12 0.0000 6 165 1440 1665 2805 \\lstinline|sqe|s\001 14 4 2 0 50 -1 0 12 0.0000 6 135 810 1665 2610 Submitted\00115 15 -6 16 16 6 180 3825 1620 4185 17 4 2 0 50 -1 0 12 0.0000 6 135 810 1620 3960 Allocated\00118 17 4 2 0 50 -1 0 12 0.0000 6 165 1440 1620 4155 \\lstinline|sqe|s\001 18 4 2 0 50 -1 0 12 0.0000 6 135 810 1620 3960 Submitted\001 19 19 -6 20 20 1 3 0 1 0 7 40 -1 20 0.000 1 0.0000 2475 3375 315 315 2475 3375 2790 3375 -
doc/theses/thierry_delisle_PhD/thesis/text/io.tex
rb984d54 rc65b930 1 1 \chapter{User Level \io} 2 As 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. Different 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. 2 As 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. 3 Different 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. 3 4 4 5 \section{Kernel Interface} … … 6 7 7 8 \subsection{\lstinline{O_NONBLOCK}} 8 In 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''. In this mode, ``Neither the @open()@ nor any subsequent \io operations on the [opened file descriptor] will cause the calling 9 process to wait''~\cite{MAN:open}. This feature can be used as the foundation for the non-blocking \io subsystem. However, 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\footnote{In this context, ready means \emph{some} operation can be performed without blocking. It does not mean an operation returning \lstinline{EAGAIN} succeeds on the next try. For 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}.}. 9 In 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''. 10 In 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}. 11 This feature can be used as the foundation for the non-blocking \io subsystem. 12 However, 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. 14 It does not mean an operation returning \lstinline{EAGAIN} succeeds on the next try. 15 For 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}.}. 10 16 This mechanism is also crucial in determining when all \glspl{thrd} are blocked and the application \glspl{kthrd} can now block. 11 17 12 There are three options to monitor file descriptors in Linux\footnote{For simplicity, this section omits \lstinline{pselect} and \lstinline{ppoll}. The difference between these system calls and \lstinline{select} and \lstinline{poll}, respectively, is not relevant for this discussion.}, @select@~\cite{MAN:select}, @poll@~\cite{MAN:poll} and @epoll@~\cite{MAN:epoll}. All three of these options offer a system call that blocks a \gls{kthrd} until at least one of many file descriptors becomes ready. The group of file descriptors being waited is called the \newterm{interest set}. 13 14 \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. On return, it modifies the set in place to identify which of the file descriptors changed status. This 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. Another limit of @select@ is that once the call is started, the interest set can no longer be modified. Monitoring a new file descriptor generally requires aborting any in progress call to @select@\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.}. 15 16 \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. It 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. Like @select@, @poll@ suffers from the limitation that the interest set cannot be changed while the call is blocked. 17 18 \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. This dynamic capability is accomplished by creating an \emph{epoll instance} with a persistent interest set, which is used across multiple calls. This 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@. 19 20 However, all three of these system calls have limitations. The @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. Furthermore, @epoll@ has been shown to have problems with pipes and ttys~\cit{Peter's examples in some fashion}. Finally, 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. 18 There are three options to monitor file descriptors in Linux 19 \footnote{For simplicity, this section omits \lstinline{pselect} and \lstinline{ppoll}. 20 The 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}. 22 All three of these options offer a system call that blocks a \gls{kthrd} until at least one of many file descriptors becomes ready. 23 The 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. 26 On return, it modifies the set in place to identify which of the file descriptors changed status. 27 This 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. 28 Another limit of @select@ is that once the call is started, the interest set can no longer be modified. 29 Monitoring 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. 33 It 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. 34 Like @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. 37 This dynamic capability is accomplished by creating an \emph{epoll instance} with a persistent interest set, which is used across multiple calls. 38 This 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 40 However, all three of these system calls have limitations. 41 The @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. 42 Furthermore, @epoll@ has been shown to have problems with pipes and ttys~\cit{Peter's examples in some fashion}. 43 Finally, 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. 21 44 22 45 \subsection{POSIX asynchronous I/O (AIO)} 23 An alternative to @O_NONBLOCK@ is the AIO interface. Its interface lets programmers enqueue operations to be performed asynchronously by the kernel. Completions 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. For this work, spawning a new \gls{kthrd} is counter-productive but a related solution is discussed in Section~\ref{io:morethreads}. Using interrupts handlers can also lead to fairly complicated interactions between subsystems. Leaving polling for completion, which is similar to the previous system calls. While AIO 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. It also supports batching multiple operations in a single system call. 24 25 AIO 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. For the purpose of \io multiplexing, @aio_suspend@ is the best interface. However, 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. AIO 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. This 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. 26 Finally, AIO does not seem to be a popular interface, which I believe is due in part to this poor polling interface. Linus Torvalds talks about this interface as follows: 46 An alternative to @O_NONBLOCK@ is the AIO interface. 47 Its interface lets programmers enqueue operations to be performed asynchronously by the kernel. 48 Completions 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. 49 For this work, spawning a new \gls{kthrd} is counter-productive but a related solution is discussed in Section~\ref{io:morethreads}. 50 Using interrupts handlers can also lead to fairly complicated interactions between subsystems and has non-trivial cost. 51 Leaving polling for completion, which is similar to the previous system calls. 52 AIO 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. 53 It also supports batching multiple operations in a single system call. 54 55 AIO 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. 56 For the purpose of \io multiplexing, @aio_suspend@ is the best interface. 57 However, 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. 58 AIO 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. 59 This 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. 60 Finally, AIO does not seem to be a popular interface, which I believe is due in part to this poor polling interface. 61 Linus Torvalds talks about this interface as follows: 27 62 28 63 \begin{displayquote} … … 48 83 49 84 \subsection{\lstinline{io_uring}} 50 A 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. Like AIO, it represents \io operations as entries added to a queue. But like @epoll@, new requests can be submitted while a blocking call waiting for requests to complete is already in progress. The @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. 51 52 One of the big advantages over the prior interfaces is that @io_uring@ also supports a much wider range of operations. In 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. 85 A 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. 86 Like AIO, it represents \io operations as entries added to a queue. 87 But like @epoll@, new requests can be submitted while a blocking call waiting for requests to complete is already in progress. 88 The @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 90 One of the big advantages over the prior interfaces is that @io_uring@ also supports a much wider range of operations. 91 In 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. 53 92 54 93 On 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. 55 94 56 95 \subsection{Extra Kernel Threads}\label{io:morethreads} 57 Finally, 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. In the worst case, where all \glspl{thrd} are consistently blocking on \io, it devolves into 1-to-1 threading. However, regardless of the frequency of \io operations, it achieves the fundamental goal of not blocking \glspl{proc} when \glspl{thrd} are ready to run. This 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. This advantage is especially relevant for languages like Go, which offer a homogeneous \glsxtrshort{api} across all platforms. As opposed to C, which has a very limited standard api for \io, \eg, the C standard library has no networking. 96 Finally, 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. 97 In the worst case, where all \glspl{thrd} are consistently blocking on \io, it devolves into 1-to-1 threading. 98 However, regardless of the frequency of \io operations, it achieves the fundamental goal of not blocking \glspl{proc} when \glspl{thrd} are ready to run. 99 This 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. 100 This advantage is especially relevant for languages like Go, which offer a homogeneous \glsxtrshort{api} across all platforms. 101 As opposed to C, which has a very limited standard api for \io, \eg, the C standard library has no networking. 58 102 59 103 \subsection{Discussion} 60 These options effectively fall into two broad camps: waiting for \io to be ready versus waiting for \io to complete. All operating systems that support asynchronous \io must offer an interface along one of these lines, but the details vary drastically. For 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@. 61 62 For this project, I selected @io_uring@, in large parts because to its generality. While @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. 104 These options effectively fall into two broad camps: waiting for \io to be ready versus waiting for \io to complete. 105 All operating systems that support asynchronous \io must offer an interface along one of these lines, but the details vary drastically. 106 For 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 108 For this project, I selected @io_uring@, in large parts because of its generality. 109 While @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. 63 110 64 111 \section{Event-Engine} 65 An event engine's responsibility is to use the kernel interface to multiplex many \io operations onto few \glspl{kthrd}. In 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}. The parked \glspl{thrd} are then rescheduled by the event engine once the desired operation has completed. 112 An event engine's responsibility is to use the kernel interface to multiplex many \io operations onto few \glspl{kthrd}. 113 In 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}. 114 The parked \glspl{thrd} are then rescheduled by the event engine once the desired operation has completed. 66 115 67 116 \subsection{\lstinline{io_uring} in depth} … … 71 120 The submission ring contains entries, \newterm{Submit Queue Entries} (SQE), produced (appended) by the application when an operation starts and then consumed by the kernel. 72 121 The completion ring contains entries, \newterm{Completion Queue Entries} (CQE), produced (appended) by the kernel when an operation completes and then consumed by the application. 73 The submission ring contains indexes into the SQE array (denoted \emph{S} ) containing entries describing the I/O operation to start;122 The submission ring contains indexes into the SQE array (denoted \emph{S} in the figure) containing entries describing the I/O operation to start; 74 123 the completion ring contains entries for the completed I/O operation. 75 124 Multiple @io_uring@ instances can be created, in which case they each have a copy of the data structures in the figure. … … 78 127 \centering 79 128 \input{io_uring.pstex_t} 80 \caption{Overview of \lstinline{io_uring}} 81 % \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 completion ring contains entries, \newterm{CQE}s: Completion Queue Entries, that are produced by the kernel when an operation completes and then consumed by the application. On the other hand, the application produces \newterm{SQE}s: Submit Queue Entries, which it appends to the submission ring for the kernel to consume. Unlike the completion ring, the submission ring does not contain the entries directly, it indexes into the SQE array (denoted \emph{S}) instead.} 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.} 82 130 \label{fig:iouring} 83 131 \end{figure} … … 86 134 \begin{enumerate} 87 135 \item 88 An SQE is allocated from the pre-allocated array (denoted \emph{S} in Figure~\ref{fig:iouring}). This 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. How 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. 136 An SQE is allocated from the pre-allocated array (denoted \emph{S} in Figure~\ref{fig:iouring}). 137 This 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. 138 How 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. 89 139 \item 90 The SQE is filled according to the desired operation. This 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. 140 The SQE is filled according to the desired operation. 141 This 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. 91 142 \item 92 The 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++}. Since the head is visible to the kernel, some memory barriers may be required to prevent the compiler from reordering these operations. Since 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. 143 The 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++}. 144 Since the head is visible to the kernel, some memory barriers may be required to prevent the compiler from reordering these operations. 145 Since 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. 93 146 \item 94 The kernel is notified of the change to the ring using the system call @io_uring_enter@. The number of elements appended to the submission ring is passed as a parameter and the number of elements consumed is returned. The @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. 147 The kernel is notified of the change to the ring using the system call @io_uring_enter@. 148 The number of elements appended to the submission ring is passed as a parameter and the number of elements consumed is returned. 149 The @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. 95 150 \end{enumerate} 96 151 97 152 \begin{sloppypar} 98 The 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. The same call can be used to both submit SQEs and wait for operations to complete. When operations do complete, the kernel appends a CQE to the completion ring and advances the head of the ring. Each CQE contains the result of the operation as well as a copy of the @user_data@ field of the SQE that triggered the operation. It is not necessary to call @io_uring_enter@ to get new events because the kernel can directly modify the completion ring. The system call is only needed if the application wants to block waiting for operations to complete. 153 The 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. 154 The same call can be used to both submit SQEs and wait for operations to complete. 155 When operations do complete, the kernel appends a CQE to the completion ring and advances the head of the ring. 156 Each CQE contains the result of the operation as well as a copy of the @user_data@ field of the SQE that triggered the operation. 157 It is not necessary to call @io_uring_enter@ to get new events because the kernel can directly modify the completion ring. 158 The system call is only needed if the application wants to block waiting for operations to complete. 99 159 \end{sloppypar} 100 160 101 The @io_uring_enter@ system call is protected by a lock inside the kernel. This 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@. It is possible to do the first three submission steps in parallel, however, doing so requires careful synchronization. 102 103 @io_uring@ also introduces constraints on the number of simultaneous operations that can be ``in flight''. Obviously, SQEs are allocated from a fixed-size array, meaning that there is a hard limit to how many SQEs can be submitted at once. In 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.''. This restriction means \io request bursts may have to be subdivided and submitted in chunks at a later time. 161 The @io_uring_enter@ system call is protected by a lock inside the kernel. 162 This 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@. 163 It 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''. 166 Obviously, SQEs are allocated from a fixed-size array, meaning that there is a hard limit to how many SQEs can be submitted at once. 167 In 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.''. 168 This restriction means \io request bursts may have to be subdivided and submitted in chunks at a later time. 104 169 105 170 \subsection{Multiplexing \io: Submission} 106 The submission side is the most complicated aspect of @io_uring@ and its design largely dictates the completion side. 107 108 While it is possible to do the first steps of submission in parallel, the duration of the system call scales with number of entries submitted. The consequence is that the amount of parallelism used to prepare submissions for the next system call is limited. Beyond this limit, the length of the system call is the throughput limiting factor. I concluded from early experiments that preparing submissions seems to take about 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}. Therefore the design of the submission engine must manage multiple instances of @io_uring@ running in parallel, effectively sharding @io_uring@ instances. Similarly to scheduling, this sharding can be done privately, \ie, one instance per \glspl{proc}, or 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}. 109 110 \subsubsection{Pool of Instances} 111 One approach is to have multiple shared instances. \Glspl{thrd} attempting \io operations pick one of the available instances and submits operations to that instance. Since the completion will be sent to the same instance, all instances with pending operations must be polled continuously\footnote{As will be described in Chapter~\ref{practice}, this does not translate into constant CPU usage.}. Since 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. Since @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. This 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. 112 113 Allocation in this scheme can be handled fairly easily. Free 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 CQEs. Allocation also requires no ordering guarantee as all free SQEs are interchangeable. This requires a simple concurrent bag. The only added complexity is that the number of SQEs is fixed, which means allocation can fail. This failure needs to be pushed up to the routing algorithm, \glspl{thrd} attempting \io operations must not be directed to @io_uring@ instances without any available SQEs. Ideally, the routing algorithm would block operations up-front if none of the instances have available SQEs. 171 The 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. 172 While it is possible to do the first steps of submission in parallel, the duration of the system call scales with number of entries submitted. 173 The consequence is that the amount of parallelism used to prepare submissions for the next system call is limited. 174 Beyond this limit, the length of the system call is the throughput limiting factor. 175 I concluded from early experiments that preparing submissions seems to take about 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}. 176 Therefore the design of the submission engine must manage multiple instances of @io_uring@ running in parallel, effectively sharding @io_uring@ instances. 177 Similarly 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. 178 Since 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.}. 180 181 A 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. 182 SQEs forming a chain must be allocated from the same instance and must be contiguous in the Submission Ring (see Figure~\ref{fig:iouring}). 183 The 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. 184 Supporting chains is a requirement of the \io subsystem, but it is still valuable. 185 Support for this feature can be fulfilled simply to supporting arbitrary user code between allocation and submission. 186 187 \subsubsection{Public Instances} 188 One approach is to have multiple shared instances. 189 \Glspl{thrd} attempting \io operations pick one of the available instances and submit operations to that instance. 190 Since 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. 191 Since @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. 192 This 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. 193 194 Allocation in this scheme can be handled fairly easily. 195 Free 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. 196 Allocation also requires no ordering guarantee as all free SQEs are interchangeable. 197 This requires a simple concurrent bag. 198 The only added complexity is that the number of SQEs is fixed, which means allocation can fail. 199 200 Allocation failures need to be pushed up to the routing algorithm: \glspl{thrd} attempting \io operations must not be directed to @io_uring@ instances without sufficient SQEs available. 201 Furthermore, the routing algorithm should block operations up-front if none of the instances have available SQEs. 114 202 115 203 Once 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. 116 204 117 Once 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. The submission ring buffer is the same size as the pre-allocated SQE buffer, therefore pushing to the ring buffer cannot fail\footnote{This is because it is invalid to have the same \lstinline{sqe} multiple times in the ring buffer.}. However, as mentioned, the system call itself can fail with the expectation that it will be retried once some of the already submitted operations complete. Since multiple SQEs can be submitted to the kernel at once, it is important to strike a balance between batching and latency. Operations 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. This 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. 118 119 In 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}. In practice however, it is important that the \io requests are not left pending indefinitely and as such, it may be required to have a current submitter and a next submitter. Indeed, 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. Once the system call is done, the submitter must also free SQEs so that the allocator can reused them. 120 121 Finally, the completion side is much simpler since the @io_uring@ system call enforces a natural synchronization point. Polling simply needs to regularly do the system call, go through the produced CQEs and communicate the result back to the originating \glspl{thrd}. Since 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}. If the submission side does not designate submitters, polling can also submit all SQEs as it is polling events. A 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. This design is especially convenient for reasons explained in Chapter~\ref{practice}. 122 123 With this pool of instances approach, the big advantage is that it is fairly flexible. It does not impose restrictions on what \glspl{thrd} submitting \io operations can and cannot do between allocations and submissions. It also can gracefully handle running out of resources, SQEs or the kernel returning @EBUSY@. The down side to this is that many of the steps used for submitting need complex synchronization to work properly. The 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. The submission side needs to safely append SQEs to the ring buffer, 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@. Sharding the @io_uring@ instances should alleviate much of the contention caused by this, but all this synchronization may still have non-zero cost. 205 Once 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. 206 The submission ring buffer is the same size as the pre-allocated SQE buffer, therefore pushing to the ring buffer cannot fail 207 \footnote{This is because it is invalid to have the same \lstinline{sqe} multiple times in the ring buffer.}. 208 However, as mentioned, the system call itself can fail with the expectation that it will be retried once some of the already submitted operations complete. 209 Since multiple SQEs can be submitted to the kernel at once, it is important to strike a balance between batching and latency. 210 Operations 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. 211 This 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. 212 213 In 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}. 214 In practice however, it is important that the \io requests are not left pending indefinitely and as such, it may be required to have a current submitter and a next submitter. 215 Indeed, 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. 216 Once the system call is done, the submitter must also free SQEs so that the allocator can reused them. 217 218 Finally, the completion side is much simpler since the @io_uring@ system call enforces a natural synchronization point. 219 Polling simply needs to regularly do the system call, go through the produced CQEs and communicate the result back to the originating \glspl{thrd}. 220 Since 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}. 221 If the submission side does not designate submitters, polling can also submit all SQEs as it is polling events. 222 A 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. 223 This design is especially convenient for reasons explained in Chapter~\ref{practice}. 224 225 With this pool of instances approach, the big advantage is that it is fairly flexible. 226 It does not impose restrictions on what \glspl{thrd} submitting \io operations can and cannot do between allocations and submissions. 227 It also can gracefully handles running out of ressources, SQEs or the kernel returning @EBUSY@. 228 The down side to this is that many of the steps used for submitting need complex synchronization to work properly. 229 The 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. 230 The 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@. 231 All this synchronization may have a significant cost and, compare to the next approach presented, this synchronization is entirely overhead. 124 232 125 233 \subsubsection{Private Instances} 126 Another approach is to simply create one ring instance per \gls{proc}. This alleviate the need for synchronization on the submissions, requiring only that \glspl{thrd} are not interrupted in between two submission steps. This is effectively the same requirement as using @thread_local@ variables. Since 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\footnote{The actual requirement is that \glspl{thrd} cannot context switch between allocation and submission. This requirement means that from the subsystem's point of view, the allocation and submission are sequential. To 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. This is not a current or planned feature of \CFA.}, greatly simplifying both allocation and submission. In this design, allocation and submission form a ring partitioned ring buffer as shown in Figure~\ref{fig:pring}. Once added to the ring buffer, the attached \gls{proc} has a significant amount of flexibility with regards to when to do the system call. Possible options are: when the \gls{proc} runs out of \glspl{thrd} to run, after running a given number of threads \glspl{thrd}, etc. 234 Another approach is to simply create one ring instance per \gls{proc}. 235 This alleviate the need for synchronization on the submissions, requiring only that \glspl{thrd} are not interrupted in between two submission steps. 236 This is effectively the same requirement as using @thread_local@ variables. 237 Since 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 238 \footnote{The actual requirement is that \glspl{thrd} cannot context switch between allocation and submission. 239 This requirement means that from the subsystem's point of view, the allocation and submission are sequential. 240 To 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.} 241 , greatly simplifying both allocation and submission. 242 In this design, allocation and submission form a ring partitionned ring buffer as shown in Figure~\ref{fig:pring}. 243 Once added to the ring buffer, the attached \gls{proc} has a significant amount of flexibility with regards to when to do the system call. 244 Possible options are: when the \gls{proc} runs out of \glspl{thrd} to run, after running a given number of threads \glspl{thrd}, etc. 127 245 128 246 \begin{figure} 129 247 \centering 130 248 \input{pivot_ring.pstex_t} 131 \caption[Partitioned ring buffer]{Partitioned ring buffer \smallskip\newline Allocated sqes are appending to the first partition. When submitting, the partition is simply advanced to include all the sqes that should be submitted. The kernel considers the partition as the head of the ring.} 249 \caption[Partitioned ring buffer]{Partitioned ring buffer \smallskip\newline Allocated sqes are appending to the first partition. 250 When submitting, the partition is advanced. 251 The kernel considers the partition as the head of the ring.} 132 252 \label{fig:pring} 133 253 \end{figure} 134 254 135 This approach has the advantage that it does not require much of the synchronization needed in the shared approach. This 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. Instances 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. Another problematic case is that \glspl{thrd} that do not park for long periods of time will delay the submission of any SQE not already submitted. This issue is similar to fairness issues which schedulers that use work-stealing mentioned in the previous chapter. 136 137 255 This approach has the advantage that it does not require much of the synchronization needed in the shared approach. 256 This 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. 257 Instances 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. 258 259 A more involved version of this approach can seem to solve most of these problems, using a pattern called \newterm{helping}. 260 \Glspl{thrd} that wish to submit \io operations but cannot do so 261 \footnote{either because of an allocation failure or because they were migrate to a different \gls{proc} between allocation and submission} 262 create an object representing what they wish to achieve and add it to a list somewhere. 263 For 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. 264 The problem with these ``solutions'' is that they are still bound by the strong coupling between \glspl{proc} and @io_uring@ instances. 265 These data structures would allow moving \glspl{thrd} to a specific \gls{proc} when the current \gls{proc} cannot fulfill the \io request. 266 267 Imagine 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. 268 If 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}. 269 If 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. 270 No other \gls{proc} can help the \gls{thrd} since @io_uring@ instances are strongly coupled to \glspl{proc}. 271 However, in this case, the \gls{proc} is unable to help because it is executing the spinning \gls{thrd} mentioned when first expression this case 272 \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''. 273 Furthermore, this pattern is difficult to reliably detect and avoid.} 274 resulting in a deadlock. 275 Once 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. 276 Interrupting \glspl{thrd} for this purpose is far from desireable, the cost is significant and the situation may be hard to detect. 277 However, 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. 278 If it were to use it, then helping could be done as part of the usage. 279 Interrupts are needed here entirely because the \gls{proc} is tied to an instance it is not using. 280 Therefore 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. 281 This is the approach presented next. 282 283 \subsubsection{Instance borrowing} 284 Both of the approaches presented above have undesirable aspects that stem from too loose or too tight coupling between @io_uring@ and \glspl{proc}. 285 In the first approach, loose coupling meant that all operations have synchronization overhead that a tighter coupling can avoid. 286 The second approach on the other hand suffers from tight coupling causing problems when the \gls{proc} do not benefit from the coupling. 287 While \glspl{proc} are continously issuing \io operations tight coupling is valuable since it avoids synchronization costs. 288 However, in unlikely failure cases or when \glspl{proc} are not making use of their instance, tight coupling is no longer advantageous. 289 A compromise between these approaches would be to allow tight coupling but have the option to revoke this coupling dynamically when failure cases arise. 290 I 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.}. 291 292 In this approach, each cluster owns a pool of @io_uring@ instances managed by an arbiter. 293 When a \gls{thrd} attempts to issue an \io operation, it ask for an instance from the arbiter and issues requests to that instance. 294 However, in doing so it ties to the instance to the \gls{proc} it is currently running on. 295 This 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. 296 This 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. 297 However, where it differs is that revocation from the arbiter means this approach does not suffer from the deadlock scenario described above. 298 299 Arbitration is needed in the following cases: 300 \begin{enumerate} 301 \item The current \gls{proc} does not currently hold an instance. 302 \item The current instance does not have sufficient SQEs to satisfy the request. 303 \item The current \gls{proc} has the wrong instance, this happens if the submitting \gls{thrd} context-switched between allocation and submission. 304 I will refer to these as \newterm{External Submissions}. 305 \end{enumerate} 306 However, even when the arbiter is not directly needed, \glspl{proc} need to make sure that their ownership of the instance is not being revoked. 307 This 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.}. 308 A \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. 309 If not it proceeds, otherwise it delegates the operation to the arbiter. 310 Once the operation is completed, the \gls{proc} lowers its local flag. 311 312 Correspondingly, before revoking an instance the arbiter marks the instance and then waits for the \gls{proc} using it to lower its local flag. 313 Only then does it reclaim the instance and potentially assign it to an other \gls{proc}. 314 315 The arbiter maintains four lists around which it makes its decisions: 316 \begin{enumerate} 317 \item A list of pending submissions. 318 \item A list of pending allocations. 319 \item A list of instances currently borrowed by \glspl{proc}. 320 \item A list of instances currently available. 321 \end{enumerate} 322 323 \paragraph{External Submissions} are handled by the arbiter by revoking the appropriate instance and adding the submission to the submission ring. 324 There is no need to immediately revoke the instance however. 325 External submissions must simply be added to the ring before the next system call, \ie, when the submission ring is flushed. 326 This means that whoever is responsible for the system call first checks if the instance has any external submissions. 327 If it is the case, it asks the arbiter to revoke the instance and add the external submissions to the ring. 328 329 \paragraph{Pending Allocations} can be more complicated to handle. 330 If the arbiter has available instances, the arbiter can attempt to directly hand over the instance and satisfy the request. 331 Otherwise 332 333 334 % Verbs of this design 335 336 % 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) 337 338 % 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. 339 340 % 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. 341 342 % 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. 343 344 % Handle: process all the produced cqe. No need to interact with any of the submission operations or the arbiter. 345 346 347 348 349 % alloc(): 350 % proc.io->in_use = true, __ATOMIC_ACQUIRE 351 % if cltr.io.flag || !proc.io || proc.io->flag: 352 % return alloc_slow(cltr.io, proc.io) 353 354 % a = alloc_fast(proc.io) 355 % if a: 356 % proc.io->in_use = false, __ATOMIC_RELEASE 357 % return a 358 359 % return alloc_slow(cltr.io) 360 361 % alloc_fast() 362 % left = proc.io->submit_q.free.tail - proc.io->submit_q.free.head 363 % if num_entries - left < want: 364 % return None 365 366 % a = ready[head] 367 % head = head + 1, __ATOMIC_RELEASE 368 369 % alloc_slow() 370 % cltr.io.flag = true, __ATOMIC_ACQUIRE 371 % while(proc.io && proc.io->in_use) pause; 372 373 374 375 % submit(a): 376 % proc.io->in_use = true, __ATOMIC_ACQUIRE 377 % if cltr.io.flag || proc.io != alloc.io || proc.io->flag: 378 % return submit_slow(cltr.io) 379 380 % submit_fast(proc.io, a) 381 % proc.io->in_use = false, __ATOMIC_RELEASE 382 383 % polling() 384 % loop: 385 % yield 386 % flush() 387 % io_uring_enter 388 % collect 389 % handle() 138 390 139 391 \section{Interface} -
doc/theses/thierry_delisle_PhD/thesis/thesis.tex
rb984d54 rc65b930 193 193 194 194 % cfa macros used in the document 195 \ input{common}195 \usepackage{common} 196 196 \CFAStyle % CFA code-style for all languages 197 197 \lstset{language=CFA,basicstyle=\linespread{0.9}\tt} % CFA default language -
libcfa/src/heap.cfa
rb984d54 rc65b930 10 10 // Created On : Tue Dec 19 21:58:35 2017 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Wed May 5 13:11:28202113 // Update Count : 103 512 // Last Modified On : Sat May 22 08:46:39 2021 13 // Update Count : 1036 14 14 // 15 15 … … 640 640 641 641 #ifdef __STATISTICS__ 642 free_storage += size; 643 #endif // __STATISTICS__ 642 __atomic_add_fetch( &free_calls, 1, __ATOMIC_SEQ_CST ); 643 __atomic_add_fetch( &free_storage, size, __ATOMIC_SEQ_CST ); 644 #endif // __STATISTICS__ 645 644 646 #if BUCKETLOCK == SPINLOCK 645 647 lock( freeElem->lock __cfaabi_dbg_ctx2 ); // acquire spin lock
Note: See TracChangeset
for help on using the changeset viewer.