Stackable Continuation Queues

description

cqueues is a type of event loop for Lua, except it's not a classic event loop. It doesn't use callbacks—neither as part of the API nor internally—but instead you communicate with an event controller by the yielding and resumption of Lua coroutines using objects that adhere to a simple interface.

cqueues are also stackable. Each instantiated cqueue is a pollable object which can be polled from another cqueue, or another event loop system entirely. The design is meant to be unintrusive, composable, and embeddable within existing applications—such as Apache or Nginx—or used standalone. It maintains no global state and never blocks your thread of execution.

cqueues includes a sockets library with DNS, buffering, end-of-line translation, SSL/TLS, and descriptor passing support builtin. Domain querying, connection establishment, and SSL negotiation are handled transparently as part of a state machine entered with every I/O operation, so users can read and write immediately upon instantiating the object, as if opening a regular file.

cqueues also includes modules for handling signals, threads, and file change notifications using native kernel facilities—such as signalfd on Linux, or Solaris PORT_SOURCE_FILE for file events—and accessible through easy to use interfaces which abstract the different kernel facilities.

Additional modules include a light-weight user-defined event system using the condition variable pattern, and a comprehensive interface for DNS querying.

cqueues is almost entirely self-contained, with the sole external dependencies being OpenSSL and, of course, Lua (Lua 5.2 or LuaJIT). However, it only works on Linux, NetBSD, OpenBSD, FreeBSD, Solaris, OS X, and derivatives. The concept is not portable to Windows because Windows lacks an analog to the pollable event queues of modern Unix systems. Libraries which try to abstract the two approaches—event readiness signaling versus event completion—invariably produce a pallid least common denominator library suffering all the weaknesses and enjoying none of the strengths of each approach.

cqueues is presently being used in production for several high-traffic services. However, I try to "release early, release often". Caveat emptor.

usage

Comprehensive usage is documented in the cqueues Userguide PDF. For easy browsing use a PDF viewer with a side tab for the table of contents, such as Preview.app on OS X.

See examples/ in the project tree for example scripts.

A simple client example showing SSL and cqueue controller nesting:

local cqueues = require("cqueues")
local socket = require("cqueues.socket")

local con = socket.connect("www.google.com", 443)
con:starttls()

local inner = cqueues.new()
local outer = cqueues.new()

inner:wrap(function()
	con:write("GET / HTTP/1.0\n")
	con:write("Host: www.google.com:443\n\n")

	for ln in con:lines() do
		print(ln)
	end
end)

outer:wrap(function()
	assert(inner:loop())
end)

assert(outer:loop())
			

A simple multiplexing echo server:

local cqueues = require("cqueues")
local socket = require("cqueues.socket")

local srv = socket.listen("127.0.0.1", 8000)
local loop = cqueues.new()

loop:wrap(function()
	for con in srv:clients() do
		loop:wrap(function()
			for ln in con:lines("*L") do
				con:write(ln)
			end

			con:shutdown("w")
		end)
	end
end)

assert(loop:loop())
				

todo

Add interfaces for handling HTTP chunked transfer encoding, including when used simultaneously with multipart message support. Example: socket:setchunk(1234). This will set a read barrier--similar to how datagram support is handled--which causes block- and line-buffered reads to complete early when the barrier is reached.

Add autoflush-like support. Unlike the Perl idiom, the semantics would be that reading will automatically flush the output stream concurrently. The Perl semantics are anachronistic and not as well suited to multiplexed socket I/O. To get Perl autoflush semantics just unbuffer the outstream stream, as write lists are buffered and flushed together internally anyhow.

Add file globbing to notify module.

Add socket read mode which specifies a Lua string pattern, e.g. "^%d+". Alternatively, finish LPegK work.

Integrate our timing wheel library for O(1) timeouts, replacing the LLRB implementation.

Replace strerror with strerror_r to improve thread-safety.

Employ O_EVTONLY on OS X so file change notifications don't prevent unmounting a drive.

Check PID in cqueues:step and reconstruct our kernel event queue if the application forked.

Return unique ID as second return value from cqueues:wrap and cqueues:attach. And return this ID from the cqueues:errors and similar interfaces so it's easier to detect and handle which coroutine failed.

news

2014-07-29

Fix compilation on NetBSD 5.1, which lacks constant NAN definition.

Make promise.new function optional.

Fix :recvfd to handle no descriptor in message.

Document promise module.

Tag rel-20140729 (622b5baa1115f634408182660e668cb76a59d316).

2014-07-07

Add ability to pass functions as arguments to thread start routine. For C functions dladdr(3)+dlopen(3) is used to anchor the function in memory, in case the initiating thread later unloads the module. This is the same mechanism used when installing lock handlers in OpenSSL.

2014-07-02

Pass on any additional arguments to cqueues:wrap when first resuming. Obviates the need to create an expensive closure every time you want to execute a task asynchronously.

Add promise module. Unlike JavaScript's promise interface, it's simple as it doesn't need to supplement for the inability to write logically synchronous code. It's more similar to C++11's promise/future interface, with :set, :get, and :wait, plus __call and __tostring metamethods.

Add cqueues.auxlib module, including new yieldable tostring implementation. Moved cqueues.assert, cqueues.resume, and cqueues.wrap to auxlib. Add auxlib.assert3, .assert4, etc, for assertions which call error() with a greater stack level. Add auxlib.filesresult, which converts the socket API return protocol to Lua's file API return protocol (specifically, error string followed by system error number).

2014-06-27

Add maxerrs limit to catch unchecked error loops. Unchecked error loops are more likely to happen now that errors are repeated until cleared.

Add :setmaxerrs method to change default unchecked error limit of 100.

2014-06-17

Add resolver pool module.

Fix SRV parsing bug in DNS library.

Update root nameserver hints within DNS library.

2014-06-12

Don't abort process on assert(3) when caller improperly calls dns_res_check after dns_res_fetch, which happens when calling resolver:fetch multiple times.

2014-06-07

Add SO_REUSEPORT support.

2014-05-26

Text-mode block reads now should behave just like C's stdio. That is, if 1024 bytes are requested, then 1024 bytes are returned, which may have necessitated reading more than 1024 bytes from the socket given any EOL translations or to ensure a trailing carriage return is not followed by a linefeed. Previously all block reads were performed as-if in binary mode, without any EOL translation.

Add a read mode for MIME boundaries. Passing a string with the prefix of -- will read blocks of data up to the specified MIME boundary. Any trailing CRLF or LF is stripped from the last block, regardless of input mode, as that's part of the boundary syntax. If text mode is enabled then blocks of multiple, EOL-translated lines are returned together, up to the maximum limit set by the greater of :setbufsiz and :setmaxline, but usually less than that to avoid splitting lines unnecessarily. In binary mode blocks of a fixed sized are returned (as specified by :setbufsiz), except for the last block, which might be less than the block size.

Add socket.debug.lua, which contains unit tests and, in the future, auxiliary interfaces for debugging.

2014-05-07

Add wrappers to coroutine.resume and coroutine.wrap, which support multilevel yielding on polling. This permits code inside a user code coroutine to still poll I/O without interfering with the resume/yield protocol of the user code. But these wrappers are not monkey patched into the current environment, so they must be used explicitly, or manually assigned as replacements to coroutine.resume and coroutine.wrap.

Tag rel-20140508 (3e322160ea3b0e2b4e7d5c188ec7cd869b0d338e).

2014-05-03

Add fast metatable checking to sockets module, to match controller and condition variable module implementations. The speed gain in validating userdata objects is only approximately 30%, so it's probably not worth it to add this to any more modules as the absolute cost is miniscule and they're not called as heavily.

Add .type routine to controller, socket, thread, condition variable, signal listener, file notification, and dns modules.

Make sure all our pollable objects have three :pollfd, :events, and :timeout methods.

Allow :pollfd to return a condition variable, allowing user objects to mimic other pollable objects.

2014-05-02

Don't return to buffered I/O callers an EPIPE received on input channel. That behavior snuck in after various changes to error and flow-control handling.

Make thrown socket errors include a description of the socket's peer name.

2014-05-01

Add timeout capability to all buffered I/O routines through :settimeout. Buffered I/O errors are not preserved across calls until explicitly cleared with :clearerr, to prevent unsuspecting code dropping data on transient errors, particularly timeout errors. The behavior of :starttls had to change for the sake of consistency. It will now poll until completion, rather than return immediately.

2014-04-19

Add fast metatable checking to the controller code, and short circuit on socket objects by calling straight into the socket library C code for the polling parameters.

2014-03-30

Add chat server example.

2014-03-28

Add :peereid and :peerpid socket methods.

Fix endless loop bug when an AF_UNIX socket could not be bound. The failure path depended on the SO_S_GETADDR iterator state to try another socket name or return the error. But the SO_S_GETADDR iterator state isn't used for AF_UNIX sockets.

Fix linking on various platforms after we required dlopen/dlsym in the threading module.

Add socket:listen wrapper to simplify error detection on listening sockets.

Silence some obnoxious compiler warnings on Linux and Solaris. They were totally bogus, but I finally relented because of the noise.

Tag rel-20140328 (52aec6d478cced10669254d90b6813a4c60ad602).

2014-03-22

Remove openssl module documention and move to dedicated user guide under luaossl project.

Add Lua 5.3 support.

Tag rel-20140322 (bd7b727a9a212d8582af0bc9fce413285da7ebaf).

2014-03-21

Add condition variable module, allowing light-weight user-defined events.

Add socket:connect wrapper to simplify explicit connect-phase timeout management.

2014-02-20

Support primitve types other than LUA_TSTRING when passing arguments to a new thread.

2014-01-30

Install OpenSSL mutexes when loading thread module.

Tag rel-20140130 (2d1f959d2c4ef82f4d0dcddd5812ed3803707648).

2013-12-09

Fix slurp mode, which only slurped until the input bufsiz was filled. It resulted in a spurious EFAULT error being thrown (the default if errno == 0), because the code behaved as if something failed.

Fix socket.connect documentation to match the actual code.

2013-12-06

Add openssl.rand.uniform() for generating cryptographically strong, uniform random integers in the interval [0, N-1]. The maximum interval is [0, 2^64-1], although for Lua 5.1 and 5.2 you're restricted to the integral range of your Lua VM number type, which is too narrow in most implementations. Lua 5.3 is expected to add a 64-bit integer type.

2013-12-05

Obey SOCK_DGRAM semantics in input buffering code. Output buffering should work without changes, provided the output modes are sane—no buffering, line buffering, or explicit flushing when fully buffered.

Implement the "*a" slurp operation. Reads to EOF on SOCK_STREAM sockets, or the next message for SOCK_DGRAM.

Add openssl.rand module, with bindings to OpenSSL RAND_bytes and RAND_status.

Add :setbufsiz and :setmaxline methods, so applications can manipulate the internal soft buffer sizes and hard line limits.

Add :errors iterator method on cqueues object, so looping over continuation errors is made easier. Also add :loop method, to make it easier for constructs which only want to loop until an error is encountered.

2013-10-23

Fix module preloading from threads to use loadstring on Lua 5.1/LuaJIT. Fix bug which cleared the O_NONBLOCK flag on pipe descriptors used for thread joining.

2013-09-09

Refactored build system to be non-recursive, and to use new luapath script, enabling simultaneous builds of both Lua 5.1 and Lua 5.2 modules in a single invocation. I needed this for work, plus it makes development much easier.

2013-03-14

Fixed bug in digest and HMAC modules which left the last argument to :update unprocessed.

Added openssl.cipher module, which binds OpenSSL EVP_CIPHER_CTX objects.

Moved the build to GNUmakefile. Now Makefile is a POSIX compatible stub using the special .DEFAULT target to forward to an invocation of gmake. This allows simply invoking make(1) on all supported platforms, presuming gmake is also installed.

2013-03-02

Fixed bug in *h and *H read modes.

Added example HTTP daemon.

2013-02-28

Added helper script to derive Lua compilation and installation paths. Simply passing prefix="..." to make should find the proper headers, even if multiple versions are installed, and select the proper installation paths. luainclude, luapath, luacpath, and LUAC can still be explicitly specified.

2013-02-27

Changed the Make variables lua52include, lua52path, and lua52cpath to just luainclude, luapath, and luacpath.

2013-02-26

Added openssl.pubkey:sign and openssl.pubkey:verify, which bind OpenSSL EVP_SignFinal and EVP_VerifyFinal. This allows constructing ad hoc signature schemes in applications.

2013-01-31

Added openssl.digest and openssl.hmac modules.

2013-01-29

Wrap dns_res_stat as resolver:stat, which returns a table of transmission statistics.

Tag rel-20130129 (65e4bf06b2d97741043dd52f5ad691014c67e7a9).

2013-01-13

Added Makefile.debian, which was mistakenly left out of the tree previously.

2013-01-06

Added Debian dpkg build. make -f Makefile.debian will build a lua-cqueues module.

2012-10-15

Added and documented new bindings for SSL connection instances, including a new socket:checktls() method.

2012-10-14

Added and documented DNS bindings.

Fixed OpenBSD build.

2012-10-11

Documented OpenSSL bindings in PDF user guide.

2012-10-10

Fixed LuaJIT compilation. No guarantees it won't break, however. Certainly one must be careful not to hold an upvalue reference to a cqueue controller from a coroutine, otherwise neither will ever be collected. Use cqueues.running, instead, to get a reference to the running controller.

2012-10-09

Added insanely comprehensive OpenSSL bindings in ext/, including Lua bindings for manipulating bignums, public keys, X.509 certificates (names, altnames, chains, stores, etc), and SSL_CTX objects.

These bindings are similar to a X.509 Perl XS module I wrote several years ago and used for a CA which dynamically issued certificates to clients on an encrypted multimedia streaming network. That Perl module was proprietary, unfortunately. But I like using Lua better, anyhow.

2012-09-25

Added a title page and examples to user guide, and tidied up some of the sections.

2012-09-24

Added file change notification module supporting all three kernel facilities—Linux inotify, BSD EVFILT_VNODE, and Solaris PORT_SOURCE_FILE.

Tag rel-20120924 (dc930e4b0408556601b1bf78a26213f6387fee8b).

2012-09-18

NetBSD 5.1 also has a broken pselect—neither pending nor unblocked signals are delivered inside pselect—so use internal implementation.

Added thread.start and accompanying thread module. On FreeBSD and NetBSD, if using the lua command-line interpreter it must be linked with pthreads, otherwise thread.start will hang.

2012-09-17

Added pselect for OpenBSD and Apple using sigpending to predict interrupts before the signal swap and kqueue EVFILT_SIGNAL to detect interrupts after the swap.

2012-09-14

Added socket.connect{} and socket.listen{}, which allow passing socket options as well as specifying a UNIX domain socket path instead of host/port pair. See README for documentation.

Added socket:uncork, for disabling the TCP_NOPUSH or TCP_CORK option set in the connect options table.

Added socket:close, for explicit and immediate closure of socket resources.

2012-09-11

Added *h and *H read modes for reading MIME headers. Returns nil when a compliant header—field name, optional blanks, and colon—cannot be scanned from the head of the buffer.

2012-09-09

Added socket.onerror and socket:onerror, which allow specifying per-socket error handlers. The handler receives a tuple—self, method-string, error-integer. It should either return an error-integer or throw an error.

By default EPIPE and ETIMEDOUT are returned directly; everything else thrown. EAGAIN is only ever returned from the semi-private internal methods, which always return socket errors directly.

Error codes are now always returned as integer values, unless thrown as formatted exception strings. Previously, some were returned as strings.

2012-08-25

Added socket.pack and socket.unpack, for buffered network byte order bit packing.

2012-08-22

POSIX threading work is mostly done, except for some magic which will allow copying cqueues modules into the new Lua VM. This will allow creating and running threads while inside a chroot jail. Access to other Lua modules could then be arranged via IPC or some other mechanism, with at least cqueues and the standard Lua modules available for use.

2012-08-13

Added descriptor passing with socket.sendmsg and socket.recvmsg. Both bypass normal buffering. sendmsg sends Lua files, cqueues sockets, or integer descriptors. recvmsg always returns a cqueues socket object.

2012-08-12

Add cqueues.cancel and cqueue:cancel, which allow explicit removal of a descriptor from polling queues, in preparation for allowing explicit early closure of descriptors.

Add cqueues.running, which returns the top-most cqueue currently executing, if any. The second return value is a boolean, true only if the calling coroutine is the one which the cqueue resumed.

Add a new cqueues.signal module. Signal disposition can be manipulated with signal.ignore, signal.default, signal.discard, signal.block, and signal.unblock. Each takes a series of signal number parameters, e.g. signal.SIGTERM, signal.SIGHUP, etc.

Add support for BSD EVFILT_SIGNAL and Linux signalfd. To create a new signal listener, do local sl = signal.listen(signal.SIGTERM). To poll for a signal call sl:wait([timeout]), which returns the signal number, or nil on timeout.

Solaris has nothing comparable to EVFILT_SIGNAL or signalfd, so Solaris uses a small timeout. For immediate response to signals for simple process management, a simple pattern using the new cqueue:pause routine can be used. cqueue:pause is a wrapper around pselect, which allows atomically changing a signal mask when polling on a descriptor. See examples/signal.pause for an example of the pattern.

I elected not to implement any hacks to handle signal retrieval from the main loop. Most event loops set a global handler which writes to a global pipe. But cqueues is intended to be embeddable, and automatically mucking around with global process state is to be avoided.

2012-08-06

Add socket.pair binding to the socketpair syscall. Takes one optional argument, either "stream" or "dgram". On success returns two socket objects bound to each other, otherwise returns two nils and an error number.

This is in preparation for adding proc.fork and thread.start. Each will return a socket object to use for IPC with the new process or thread. I will also need to add socket:sendmsg so descriptors can be sent, as well.

2012-08-05

Merged SIGPIPE suppression and /etc/nsswitch.conf support into dns.c. The work was done in this tree, but see the dns.c project page for a description.

Tag rel-20120805 (6d673b77209e1a5e4b1d37c25ec8600e73e3af5c).

2012-08-04

Fix Solaris port_getn usage bug triggered by signal interruption.

2012-07-13

Change Solaris build to use native SunPro by default. Fix SunPro warnings about unsupported GCC attributes originally used just to silence GCC and (especially) clang warnings. SunPro seems to have a broken diagnostic pass confused by macroized calls, resulting in erroneous "argument mismatch" warnings.

NetBSD's kevent definition uses intptr_t instead of void * for the .udata member. Fix conversion warnings by casting to typeof(.udata).

Add cqueues.VERSION, cqueues.VENDOR, and cqueues.COMMIT to identify different library versions.

Tagged release rel-20120713 (99cae0d736239a910c1dfc901335a7cc5fcf7f3d).

2012-07-12

Add yielding socket:accept() with socket:clients() iterator. Add example script, echo.srv, to show usage.

Add cqueues.monotime, which returns the system's monotonic clock time.

Unbreak FreeBSD after fixing Solaris byte order issue in dns.h. FreeBSD also defines _BIG_ENDIAN, but the semantics are like BYTE_ORDER/BIG_ENDIAN, not the boolean behavior on Solaris.

Use esyscmd when generating errno table because NetBSD's M4 implementation had flushing issues and divert/undivert wouldn't work to solve it. Solaris lacks esyscmd, so stick with syscmd, which didn't exhibit flushing issues.

Tagged release rel-20120712 (b8deeb0e663d163d567c24adb5fd1291e1b6e8ae).

At this time, rel-20120712 is known to build and run on NetBSD 5.1, FreeBSD 9.0, Ubuntu Linux 12.04, Solaris 11, OS X 10.7.4, and OpenBSD 5.1.

2012-07-11

Tagged release rel-20120711 (e0f6fbbb05cb7aa5d95becd6251417155987205e).

2012-07-10

Tagged release rel-20120710.

license

Copyright (c) 2012-2014 William Ahern

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

source

git clone http://25thandClement.com/~william/projects/cqueues.git

Or visit the GitHub mirror

download

cqueues-20140729.tgz (not always the most recent tagged release)

cqueues-20140508.tgz

cqueues-20140328.tgz

cqueues-20140322.tgz

cqueues-20140130.tgz

cqueues-20130129.tgz

cqueues-20120924.tgz

other projects

airctl | bsdauth | cnippets | libmime | libarena | libevnet | authldap | streamlocal | libnostd | zoned | dns.c | delegate.c | llrb.h | lpegk | json.c | cqueues | siphash.h | hexdump.c | timeout.c | luapath | luaossl | lunix | AnonNet