\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#458: Add Support for epoll() and kqueue() in the Notifier}
\date{November 24, 2016}
\author{Lucio Andr\'{e}s Illanes Albornoz, Lucio Andr\'{e}s Illanes Albornoz}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#458}&\textbf{Add Support for epoll() and kqueue() in the Notifier}\\\hline
Author&

Lucio Andr\'{e}s Illanes Albornoz \tipmail{l.illanes}{gmx.de}
\par
Lucio Andr\'{e}s Illanes Albornoz \tipmail{lucio}{lucioillanes.de}
\\
Created&Thursday, \(\text{24}^{\text{th}}\) November 2016\\
Type&Project\\
Tcl Version&\(8.7\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.6 $\\
Keywords&event loop, scalability\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes to replace \textit{select}(2) in the notifier implementation with \textit{epoll}(7) and \textit{kqueue}(2) on Linux and DragonFly-, Free-, Net-, and OpenBSD respectively. This is to remove a major bottleneck in the ability of Tcl to scale up to thousands and tens of thousands of sockets (aka \textbf{C10K}). Furthermore, this should also provide sufficient infrastructure in order to permit adding support for other platform-specific event mechanisms in the future, such as IOCPs on Solaris and Windows.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

The drawbacks associated with \textit{poll}(2) and \textit{select}(2) and the tremendously improved ability to scale of \textit{epoll}(7) and \textit{kqueue}(2) are well-known [\url{https://en.wikipedia.org/wiki/C10k_problem}]; a previous attempt at implementing this feature elaborates on this subject and can be found at [\url{https://sourceforge.net/p/tcl/mailman/tcl-core/?viewmonth=200909&viewday=10}].

Initially, the notifier thread was retained to provide for event notification and inter-thread IPC. This eventually proved unnecessary and thus the \textit{epoll}(7)/\textit{kqueue}(2) source modules now no longer contain the notifier thread and its infrastructure, particularly as this also reduces code size and complexity.

Threads that intend to wait on one or more file descriptors they own will now directly call \textit{epoll\_wait}(2)/\textit{kevent}(2) themselves during \textit{Tcl\_WaitForEvent}(). Inter-thread IPC is provided for by a per-thread trigger pipe, analogous to the trigger pipe of the notifier thread. On Linux, an \textit{eventfd}(2) is used instead, which only requires one single fd. Furthermore, events for regular files are not processed via \textit{epoll}(7), as it does not support them at present. Instead, events for regular files are immediately returned by the notifier when waiting for events.

The new implementation of the notifier only has two minor drawbacks:
\begin{enumerate}
\item{}
Each thread that has called \textit{Tcl\_WaitForEvent}() at least once will create an \textit{epoll}(7)/\textit{kqueue}(2) file descriptor.
\setcounter{enumi}{1}
\item{}
All threads create two \textit{pipe}(2) file descriptors for inter-thread IPC; on Linux, one single \textit{eventfd}(2) is created and used.
\end{enumerate}

Therefore, threads that have waited on events at least once now own an additional amount of three/two file descriptors. Whether this could prove to be a problem remains a point of contention that should be subject to further discussion.

As far as the notifier implementation is concerned, threads do not share data structures or file descriptors; IPC is provided for explicitly. However, a thread may queue events to and then alert another thread in order to allow for less primitive forms of IPC. Therefore, the previously static mutex protecting the notifier list has become a per-thread mutex. Instead of protecting the notifier list, it protects per-thread event queues from event queue/unqueue race conditions. This only applies to the \textit{epoll}(7)/\textit{kqueue}(2)-based notifier implementations.

The majority of Tcl code should be unable to observe any difference at the script level.

\section{Specification}

At present, code changes are almost entirely constrained to either \textit{unix/tclEpollNotfy.c} wherever \textit{epoll}(7) is supported or \textit{unix/tclKqueueNotfy.c} wherever \textit{kqueue}(2) is supported. The original \textit{select}(2)-based notifier implementation now lives in \textit{unix/tclSelectNotfy.c}.

Subroutines shared between \textit{unix/tcl\{Epoll,Kqueue\}Notfy.c} have been moved to \textit{unix/tclUnixNotfy.c}, which is \textbf{\#include}d by the former. As explained in the last section of this document, the previously static mutex in \textit{generic/tclNotify.c} has become a per-thread mutex.

The new code associates the newly introduced (but private) \textit{PlatformEventData} structure with each file descriptor to wait on and its corresponding \textit{FileHandler} struct. \textit{PlatformEventData} contains:
\begin{enumerate}
\item{}
A pointer to the \textit{FileHandler} the file descriptor belongs to. This specifically facilitates updating the platform-specific mask of new events for the file descriptor of a \textit{FileHandler} after returning from \textit{epoll\_wait}(2)/\textit{kevent}(2) in \textit{NotifierThreadProc}().
\setcounter{enumi}{1}
\item{}
A pointer to the \textit{ThreadSpecificData} of the thread to whom the \textit{FileHandler} belongs. This specifically facilitates alerting threads waiting on one or more \textit{FileHandlers} in \textit{NotifierThreadProc}().
\end{enumerate}

The core implementation is found in a set of six (6) newly introduced static subroutines in \textit{unix/tcl\{Epoll,Kqueue\}Notfy.c}:
\begin{enumerate}
\item{}
\textit{PlatformEventsControl}() --- abstracts \textit{epoll\_ctl}(2)/\textit{kevent}(2). Called by \textit{Tcl\_\{Create,Delete\}FileHandler}() to add/update event masks for a new or an old \textit{FileHandler} and \textit{NotifierThreadProc}() in order to include the \textit{receivePipe} fd when waiting for and processing events.
\setcounter{enumi}{1}
\item{}
\textit{PlatformEventsFinalize}() --- abstracts \textit{close}(2) and \textit{ckfree}(). Called by \textit{Tcl\_FinalizeNotifier}().
\setcounter{enumi}{2}
\item{}
\textit{PlatformEventsGet}() --- abstracts iterating over an array of events. Called by \textit{NotifierThreadProc}().
\setcounter{enumi}{3}
\item{}
\textit{PlatformEventsInit}() --- abstracts \textit{epoll\_create}(2)/\textit{kqueue}(2). Called by \textit{PlatformEvents\{Control,Wait\}}() and \textit{Tcl\_WaitForEvent}().
\setcounter{enumi}{4}
\item{}
\textit{PlatformEventsTranslate}() --- translates platform-specific event masks to \textbf{TCL\_\{READABLE,WRITABLE,EXCEPTION\}} bits. Called by \textit{Tcl\_WaitForEvent}().
\setcounter{enumi}{5}
\item{}
\textit{PlatformEventsWait}() --- abstracts \textit{epoll\_wait}(2)/\textit{kevent}(2). Called by \textit{Tcl\_WaitForEvent}() and \textit{NotifierThreadProc}(). 
\end{enumerate}

Two additional subroutine are used in all three code paths (\textit{epoll}, \textit{kqueue}, \textit{select}) to reduce code redundancy:
\begin{enumerate}
\item{}
\textit{AlertSingleThread}() --- notify a single thread that is waiting on I/O. Called by \textit{NotifierThreadProc}().
\setcounter{enumi}{1}
\item{}
\textit{TclUnixWaitForFile() --- reimplemented via }poll\textit{(2) instead of }select\textit{(2), as }poll\(''\)(2) does not suffer the \textbf{FD\_SETSIZE} limit on file descriptors that can be passed to \textit{select}(2) and is available on a sufficiently large number of platforms. Most importantly, this code would not benefit from using \textit{epoll}(7) or \textit{kqueue}(2) as this subroutine only waits on one single file descriptor at a time.
\end{enumerate}

\textit{PlatformEventsInit}() currently defaults to allocating space for 128 array members of \textit{struct epoll\_event/kevent}. This could preferably be handled through e.g. \textit{fconfigure}.

Originally, a mutex used to protect the \textit{epoll}(7)/\textit{kqueue}(2) file descriptor and the above mentioned array. This proved to be redundant as \textit{epoll\_ctl}(2) can be called whilst blocking on \textit{epoll\_wait}(2) on Linux and as \textit{kevent}(2) can be called whilst blocking on \textit{kevent}(2) on FreeBSD.

Lastly, the \textit{configure} script is updated to define \textbf{HAVE\_EPOLL} or \textbf{HAVE\_KQUEUE} as appropriate.

\section{Reference implementation}

Please refer to the \textit{tip-458} branch. The code is licensed under the BSD license.

\section{Copyright}

This document has been placed in the public domain. In legislations where this concept does not exist the BSD license applies.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
