Tony Finch's blog

So last week I wrote about some simple "desugaring" transformations that turn a fairly conventional block-structured programming language into the call-by-value lambda calculus with some small extensions. The main problem is that I relied on first-class continuations. This has at least two undesirable consequences:

• First-class continuations are the goto of functional programming. Actually, that understates the amount of unconstrained tangle that they can unleash - they are far more powerful and dangerous than goto. So one can argue that programmers are better off avoiding first-class continuations and using more constrained control flow, much like we are advised to shun goto in favour of break, return, and exceptions.
• Continuations can't easily be implemented with a conventional linear stack. When you return a normal value up the stack, the top stack frame(s) can be freed, but if you return a continuation up the stack, they cannot: calling the continuation re-activates these frames. The stack becomes a cactus. A common solution to this problem is to allocate activation frames on the heap, but this seriously stresses the garbage collector and harms locality: whereas a stack works up and down over the same small area of memory, the heap blasts forever upwards.

Fortunately there's a nice solution: multi-return function calls. The idea is to separate continuation arguments from normal arguments, and restrict the continuations so that activation frames are still used in a normal stack-like LIFO manner. What's really neat is that it preserves a lot of the the power of first-class continuations.

However, the desugaring transforms become more complicated. The scope of the multi-return continuations is restricted so that you cannot (for example) return from a function by invoking its continuation from an inner block, because the continuation is not available there. Instead you have to add plumbing to pass the early-return continuation into the block along with the block's normal sequential continuation. This plumbing ends up being rather like the standard continuation-passing-style transformation described in the lambda-the-ultimate papers linked to above, but with an extra continuation for each early exit.

This extra-continuation plumbing is also similar to a standard implementation technique for exceptions (which I called "non-trivial" last week, but isn't actually hard to understand). As well as the sequential continuation that is passed around in CPS, you pass around an exception handler continuation which is invoked in order to throw an exception. This is very similar to implementing exceptions in C with setjmp and longjmp, except in C you can keep the current exception handler in a global variable instead of passing it around.

The downside of these techniques is that the plumbing is an overhead. However, it is "pay-as-you-go", in that you only need the plumbing if you use early exits from blocks. (It's less easy to avoid the exception plumbing since exceptions can usually be thrown anywhere.) By contrast, the more complicated infrastructure needed for first-class continuations affects the performance of the whole run-time system.

(The mathematics in the typing of these constructions relates directly to their balance of practicality and power. Constrained continuations like multi-return functions and exceptions are usually used linearly and have an intuitionistic (constructive) typing. Call-with-current-continuation, however, has a classical typing which is not expressible in most practical type systems. This kind of direct relationship between theory and practice is one of the beauties of computer science.)

Recently I've read about Lua. It's a nice simple language, with a syntax that's quite close to my ideal for a dynamically-typed imperative language. One of the things it omits for simplicity's sake is first-class continuations. I've been wondering how one might specify a similar syntax if you have a Schemeish infrastructure, so that the usual control structures can be desugared into functions, conditionals, and tail-calls. I also have in mind Modula-3's definition of some control structures in terms of exceptions. In the following I'm not going to talk about the whole syntax; I'll omit things which don't involve blocks.

The basic form of a block expression is:

	name(arguments): do
		statements
	end

The value of this expression is a function which takes some arguments and which when called executes the statements. The scope of its name is just within the block itself; it is used in inner scopes to refer to shadowed variables in outer scopes.

To execute the block immediately, the arguments can be omitted:

	name: do statements; end

is equivalent to

	name(): do statements; end()

that is, it specifies a function that has no arguments and which is called immediately.

The name can also be omitted. Doing so just means there's no way to refer to this block's variables if they are shadowed in an inner scope. For example, an anonymous function (lambda expression) is typically

	(args): do statements; end

You might also want to allow a shorter version of

	(args): do return(values); end

for use in expressions, perhaps

	(args): return (values)

A minimal block like the following is just like a Lua block:

	do statements; end

Just before the end of each block there's an implicit return(nil). You can return from a block early with whatever value or list of values you want.

Instead of do...end you can write a conditional:

	if expression then
		true statements
	else
		false statements
	end

If the else part is omitted then the false statements are implicitly return(nil). You can also add elsif expression then alternate statements parts in the usual way.

The basic form of a loop is

	name: do
		statements
	loop

which is equivalent to

	name: do
		statements
		return(name())
	end

that is, loops are implemented using tail recursion. (Loops do not have to be named, but I've written the desugaring in terms of a named block to avoid having to talk about hypothetical unique names.)

	name: while expression do
		statements
	loop

is equivalent to

	name: if expression then
		statements
		return(name())
	end

and

	name: do
		statements
	while expression loop

is equivalent to

	name: do
		statements
		if expression then
			return(name())
		end
	end

You can use until expression instead of while not(expression).

Given the above, you can see that return inside a loop is similar to break in C. It's often nice to be able to break out of more than one nested loop at a time, or return from a function inside a loop. This is where a block's name comes into play. To return from a named outer block, call name.return. For example:

	def bsearch(arr, val): do
		def lo, hi := 1, #arr
		while lo <= hi do
			def mid := math.floor((lo + hi) / 2);
			if arr[mid] == val then
				bsearch.return(mid)
			elsif arr[mid] < val then
				lo := mid + 1
			else
				hi := mid - 1
			end
		loop
	end

A bare return in the above would specify the value of the if block, not the function.

This kind of return makes it easy to write call-with-current-continuation:

	def callcc(f): do
		def cont(...): do
			callcc.return(...)
		end
		return(f(cont))
	end

However this is unnecessary because return is already an expression whose value is the current continuation. It's just like other function arguments, except that it's implicit (a bit like the self argument in Lua's methods) and can't be assigned to (so that the compiler can do tail-call optimisation). (Actually, what if you *could* assign to return? Eeeeevil!)

There are three forms of statement within a block: definitions, assignments, and function calls. Since a block without arguments is equivalent to a function expression that is immediately called, non-function blocks can be statements. A function definition

	def name(arguments): do ...

is equivalent to

	def name := name(arguments): do ...

For bigger code, it's useful to allow a block's name to be repeated after its end or loop, for example:

	def long_function(arguments): do
		code
		code
		code
	end long_function

You can further desugar definitions, since

	old_name: do
		before statements
		def variables := values
		after statements
	end

is equivalent to

	outer_name: do
		before statements
		inner_name(variables): do
			after statements
		end(values)
	end

except that you need to fix up the after statements so that unqualified returns are qualified with the outer_name, and variables qualified with the old_name are qualified with the outer_name or inner_name as necessary.

Some things are still missing from this description. A for loop is necessary, probably based on some kind of iterator concept, but that's too far away from the topic of this post to be worth pursuing in detail now. Also, we would probably like a standard exception mechanism; this is not trivial to implement in terms of continuations because the code that handles an exception is determined dynamically (like Perl local) whereas continuations are lexical (like Perl my). Finally, the combination of continuations and concurrency is utterly filthy: imagine what happens if one thread calls a continuation created by another...

Following on from http://fanf.livejournal.com/65203.html I feel the need to write down some more details of my log-structured queue idea.

My approach has a "crash-only software" architecture. According to the abstract of that paper: "Crash-only programs crash safely and recover quickly. There is only one way to stop such software - by crashing it - and only one way to bring it up - by initiating recovery." So, no shutdown code.

Essentials:

The queue consists of a sequence of records of various types.

The most important record type is a message envelope, which contains everything you need to route a message: at a minimum the recipient addresses, though practicality demands rather more than that. The envelope also contains a reference to the spool file which contains the message data etc.

When a message is delivered the MTA must immediately update its recipient list on stable storage. (It has to be immediate in order to avoid duplicate deliveries when the MTA restarts after being stopped at the wrong point.) We don't want to have to rewrite the whole envelope for every delivery: it is big and complicated, whereas we want delivery records to be small and simple since there will often be more than one of them for each message (especially for bigger envelopes!) and they will be most of the fsync()ed write traffic on the queue. So delivery records are just deltas relative to envelope records.

Once the current set of delivery attempts for a message has been completed, we write a replacement envelope for the message, or if there are no recipients left, we need to record that all work on the message is finished. At this point the old envelope and all its updates have become garbage.

Unless the MTA has only one message in the queue, the old envelope, the delivery records, and the replacement envelope will all be separated from each other in the queue by records related to other messages. Therefore we need some way of linking them together so that we can restart quickly, without scanning the whole queue. The point of this article is how to solve this problem.

Details:

The procedure for delivering a message is as follows. A queue runner scans the queue until it encounters an envelope which is not marked as garbage, is past its retry time, and is not already being worked on. It then kicks off delivery of this message. (There is a queue runner for newly received messages as well as older messages so all deliveries start this way.) First write a start record to the queue to record that this message is being worked on and to link back to its envelope record. These start records are used to recover state after a restart. Then the envelope is marked as garbage. This is done early so that these garbage marks are added sequentially - it's common to finish working on messages in a different order. Then deliver the message, recording the results for each set of recipients (successful or otherwise) as a delivery record in the queue, with an fsync() for each set. When there's nothing left to do for the message, either write an updated envelope record (if it is to be retried) or a finish record. Finally, mark the start record as garbage, which implicitly marks its associated delivery records as garbage.

When we restart, the part of the queue that we can't avoid scanning is the "working suffix", which contains delivery records of messages which have not yet had their replacement envelopes written. The original envelopes of the these messages are marked as garbage, but they are still needed until their replacement is written, so they can't yet be discarded. These are the messages that the MTA was working on when it stopped, so we need to recover that working state, or at least the parts that still matter. The start of the working suffix is the earliest start record which has not been marked as garbage.

One thing we can avoid scanning for at startup is the appropriate positions of the queue runners in the queue. Every so often the MTA records the set of queue runner positions for use at a restart. Doing this more frequently means less wasted work at startup, but also means more overhead in normal operation. Similarly, it also records the start of the working suffix. The procedure is to find out the current restart positions, fsync() all the queue files, then write these restart positions to disk. There are multiple queue files because - like log files - the MTA switches to a new file every so often so that when old files become entirely garbage they can be deleted. The queue runners will be marking envelopes as garbage as they go, and since they will not all be scanning the current queue file, they can't benefit from that file's frequent fsync()s, hence the need for the extra fsync() to ensure that the restart positions correctly reflect the on-disk state in case of a crash. This procedure lags slightly behind the activity of the queue runners, which is OK because the restart positions don't need to be accurate: if they are out of date the only harm will be a little more garbage to scan after startup. The important feature is that the older portions of the queue before the restart pointers are consistent.

When the MTA is restarted it can immediately start receiving messages, since this just involves appending new envelope records to the queue. However deliveries have to wait. Having read the queue positions, the MTA starts scanning the working suffix. For each start record that isn't marked as garbage, ensure that the envelope it refers to is marked as garbage (it might not be if there was a crash) then add it to the list of working messages. Remember each delivery record that is associated with a working message. If we encounter a replacement envelope or finish record for a working message (again because of a crash), mark its start record as garbage and remove it from the working list. When we run out of queue, write replacement envelopes for all the working messages, and mark their start records as garbage. The on-disk data has now been made consistent, so we can start the queue runners at their recorded positions.

There's one remaining mechanism. The earliest queue runner (dealing with the messages with the longest retry interval) leaves behind it a queue that is entirely marked as garbage. However envelopes just behind the queue runner are not true garbage until their replacement envelope has been written. Thus there must be a process which tracks the point where true garbage starts, so that when it rolls past a file boundary we know the older file can safely be removed. This can be done entirely in memory by keeping note of when deliveries triggered by the earliest queue runner complete. No persistent state is needed because after the working suffix has been scanned the garbage markers are all correct.

Optimizations:

No fsync()s are needed for writing garbage flags, start or finish records, or replacement envelopes, because if they are lost in a crash they can be recovered, or other fsync() activity prevents such a loss. These writes are book-keeping - they aren't necessary in a conventional one-file-per-message spool - so it's good that they can be coalesced with other more unavoidable writes.

The envelope of a new message does need to be fsync()ed before we return a 250 to the client that sent it to us, but if we delay a little we can piggy-back it on a delivery fsync().

Delivery records contain sets of recipients when a single delivery has multiple recipients. One delivery record is written when we get the destination server's final response to the message data. Thus we can get less than one fsync() per recipient per message.

I haven't said where to record the restart positions. This could be in the queue, which implies a bit of furtling around to find them, or in a fixed location, which implies extra seeks (similar to mtime seeks).

It might be more efficient to have multiple queues, the key difference being that replacement envelopes are written to a queue with queue runners that have an appropriate retry interval. With the single queue setup the long-interval queue runners are mostly skipping garbage, which wastes IO bandwidth and pollutes the page cache. However multiple queues may increase seeking too much. As chrislightfoot points out, the conventional wisdom isn't a reliable guide in this area. More benchmarks needed.

Edit:

Actually, the garbage bits on the start records are unnecessary: they are only for use by the restart process, but it can (and does!) infer their correct value. When we finish working on a message, instead of frobbing this bit, we just update our current in-memory note of the start-of-working-suffx and end-of-garbage-prefix positions, as appropriate.

A correspondence with Postfix terminology: The working suffix is like Postfix's active queue. The new envelopes being appended to the queue are the incoming queue. The other queue runners are scanning the deferred queue. Postfix has a fairness strategy of adding messages to the active queue alternately from the incoming and deferred queues, and we can apply something similar here by controlling when we ask each queue runner to scan for its next envelope.

It's traditional for most MTAs to use something close to the host operating system's standard text file format for storing messages that are queued for delivery. For example, on Unix that means using bare LF for newlines instead of the Internet standard CRLF. Exim, Sendmail, and qmail do this. On other systems the translation may be more extensive, e.g. if the native charset is EBCDIC, or if text files are record-oriented rather than stream-oriented. Postfix is a bit of a counter-example, since it runs on Unix but turns the lines of a message into records, as part of its general IPC scheme that I mentioned in part 2.

This makes sense if you are working in an environment where local email is more common than remote email: messages stay in the system's local format so are less likely to be munged. However, nowadays MTAs (especially on Unix) generally act as relays to and from SMTP (and variants like message submission or LMTP). The mismatch between local text formats and the Internet standard format leads to all sorts of transparency bugs. For example, SMTP was originally specified to be 7 bit clean, with no restrictions on bare CR or LF. However these characters will get mangled when a message is transferred via an MTA that translates newlines. There are descriptions of many similar problems in RFC 2049.

The other problem with all of this translation and re-translation is that it's horribly inefficient: it requires lots of copying back-and-forth, meaning you use several times more memory bus bandwidth than is needed to shift bits between the network and the disk. One of the neat things that the Cyrus IMAP server does is store its data in wire format, so that it can be transferred from disk to network with minimal copying. (UW IMAP, Courier, and Dovecot all use Unix native Berkeley or maildir folders.) Why not do the same in an SMTP server?

The main difficulty with this idea is that SMTP does not have a single wire format. What's worse is that you don't find out a message's outgoing wire format until you have connected to the destination host and are about to transmit it. Even worse, there might not even be a single outgoing wire format if the message has multiple recipients at different hosts with different capabilities.

You can make this problem much more tractable if you store the messages in the format that they are received in, and prepare for any recoding that may be necessary on transmission. In most cases, the incoming and outgoing software will have the same capabilities, so you will be able to use efficient APIs like sendfile(). But what do I mean by "prepare"?

• You need to parse the MIME structure of the message, and note at least the content-transfer-encoding of each part. This will allow you to downgrade each part in the appropriate way when that is necessary.
• If you are really keen, then you can also scan the data in each part to (say) choose between quoted-printable or base64 depending on which would be most efficient.
• You need to note dot-stuffing points: in traditional SMTP, where dots have been inserted, and with chunked SMTP, where they need to be inserted for onward traditional transmission.
• If you support UTF8SMTP, you have to scan the RFC822 and MIME headers for top-bit-set characters that may need downgrading to RFC2047 or RFC2231 encodings.

This can be done as the message is received, which only requires the message data to go over the memory bus once. (Data goes over the bus twice in a copy - from the old buffer and to the new buffer - so a parse is cheaper than a copy.) When you come to send the message onwards, you can directly sendfile() those parts that do not need to be downgraded and only recode where absolutely necessary.

It's worth noting that transmission between chunked and traditional SMTP can be done efficiently (assuming no MIME recoding is necessary). Dot-stuffing is only rarely necessary (e.g. it never happens in base64 attachments) so there will be reasonably large blocks of the message between dots which can sensibly be passed to sendfile(). When removing dots you will be sending blocks with a one byte gap between the file offset of the end of one block and the start of the next, and when adding dots you can use the leader or trailer feature of sendfile() to add the dot. This is good because it means it is cheap to use the more pipelineable BDAT command when it is available. It's also way more efficient than the usual scan-every-byte-of-the-message implementation of dot-stuffing. And I think it is quite cute :-)

Existing MTAs that implement 8BITMIME downgrading (such as Sendmail) generally do the MIME parse and recode when sending the message, and just use base64 because it would be too expensive to do two passes to work out if quoted-printable would be better. Another situation when two passes are necessary is adding a DomainKeys signature, because it appears at the top of the message. In many cases (if you aren't going to alter the message) you can make DK more efficient by calculating the signature as the message arrives so that it's easy to add when the message is transmitted.

Is it worth trying to make this more efficient? For example, if you have a cache of destination host capabilities, you could recode the message as it comes in to save a trip over the memory bus. But you will still have to support late recoding if the cache lookup misses, so the extra complexity probably isn't worth it.

Previously: part 3- local delivery; part 2 - partitioning for security; part 1 - the sendmail command; message identification.

fanf2@cyrus-21.csi.private.cam.ac.uk:~
: 0 ; df -h
Filesystem            Size  Used Avail Use% Mounted on
/dev/sda1             2.0G  970M  951M  51% /
tmpfs                 1.8G  8.0K  1.8G   1% /dev/shm
/dev/md0              3.3T  1.5T  1.8T  46% /spool
/dev/sdb1             2.0G  289M  1.6G  16% /var

brad

• The development of the University's data network to support the conversion of the University's analogue telephone network to Voice-over-IP;
• The expansion of the University's data network by means of an injection of up to £1M of SRIF3 funding.

kaboom_defer:
  driver		= redirect
  domains		= kaboom.cam.ac.uk
  data			= :defer: email server is currently unavailable
  allow_defer

kaboom_accept:
  driver		= accept
  verify_only
  domains		= kaboom.cam.ac.uk

kaboom_hermes:
  driver		= redirect
  domains		= kaboom.cam.ac.uk
  local_parts		= +hermes_active
  condition		= ${if !match{$sender_host_name}{cyrus-[0-9]+[.]csi[.]private[.]cam[.]ac[.]uk} }
  data			= $local_part@hermes.cam.ac.uk
  forbid_blackhole
  forbid_file
  forbid_include
  forbid_pipe
  check_ancestor
  retry_use_local_part

• Get the Chat service deployed!
  
• Hermes projects:
  
  • Re-do and improve the anti-spam and anti-virus infrastructure. This has three parts:
    
    1. Replace MailScanner with exiscan, so that we can scan messages at SMTP time, and reject those we don't like instead of discarding them. If we don't want to rely totally on ClamAV we'd need to replace McAfee with a better commercial AV scanner, because McAfee is not fast enough for non-batch-mode scanning; it's also pretty bad at promptly issuing new signatures. This would allow us to have a default SpamAssassin threshold (without the lost-email consent problems caused by the way MailScanner works) which in turn would help with our AOL problems.
       
    2. Allow per-user options at SMTP time, e.g. spam threshold, stricter sender verification, greylisting, etc. This requires some data-shifting infrastructure which I have made a small start at, and user-interface extensions to Prayer.
       
    3. Add a new component for per-user statistical spam filtering. This would live on the message store (with other per-user state), and hook into message delivery for initial filtering, and copying to or from the spam folder for training. Again we need user-interface changes to Prayer to present the results of the filter and allow users to train it - similar functionality to full MUAs like Mac OS X Mail or Thunderbird.
       
  • Shared folders. Requires a new IMAP proxy (like the Cyrus Murder) and changes to the replication system. Does Cyrus 2.3 have the necessary functionality?
    
  • Internationalized webmail. Replace (or run alongside) Prayer with some better-known software?
    
  • Finish the ratelimit project. Will require time to work on a user interface, so that it is sufficiently friendly. My current idea for how it would work requires the double-bounce patch mentioned below.
    
  • Deploy DKIM (server-side message signatures for anti-spam).
    
• Exim projects:
  
  • Improved hints DB infrastructure. The aim is to remove the performance bottleneck caused by whole-table locking, and make the back-end more pluggable so that we could have distributed hints databases. PPswitch would then act as a cluster with the machines sharing knowledge about other hosts on the net.
    
  • Concurrent DNS lookups during routing, to improve mailing list performance. I've done some work on this already.
    
  • Better handling of double bounces. If we can't deliver a bounce to recipient@domain, try postmaster@domain then postmaster@cam instead of freezing the message.
    
  • Finish the bounce address protection code.
    
• Service integration:
  
  • Kerberos. Proper single-sign-on! Users really hate typing in passwords.
    
  • Raven-authenticated webmail for more single-sign-on.
    
  • Mailing lists generated from Lookup groups. Lookup groups generated from data in CamSIS/CHRIS.
    
  • Web presence: an extension to the chat service which allows other Raven-authenticated sites (such as lookup and webmail) to display a presence icon next to a username. If I am looking at your lookup page and you are on my chat buddy list, then I can see whether you are currently on-line and I can click on the presence icon to chat with you. Depends crucially on transparent single-sign-on. In particular, the default for Raven at the moment is confirmed sign-on, which isn't transparent enough.
    
  • Short URL service, like go.warwick.ac.uk, which doesn't host content but instead redirects to full URLs. Mainly for use on printed material such as business cards, academic papers, posters, press releases, etc. Namespace divided into ~CRSID for homepages (using data from lookup) and ad-hoc names managed by user-admin. Could include societies.
    
• Web stuff, etc.:
  
  • Blogging service.
    
  • Web forums.
    
  • The two could be aspects of the same thing (e.g. Livejournal's blogs and communities).
    
  • Society information in Lookup, similar to the institution information.
    
  • More effective use of talks.cam.ac.uk.
    
  • Shared calendars / meeting manager.
    
• Networking:
  
  • Make it easier for depts and colleges to host conferences. e.g. at the Durham UKUUG I was given a short-term uid which gave me access to their PWF and wifi.