Tony Finch's blog

I've come to the conclusion that most programming languages' idea of a string - an array or list of characters - is wrong, or at least too simplistic.

Most languages designed before Unicode have the idea that characters are bytes, which is hopelessly inadequate. Languages designed before Unicode was mature (e.g. Java) have the idea that characters are 16 bits which is still inadequate. The next reasonable step is to use a 32 bit type for characters, but that wastes at least a third of the memory you use for strings since Unicode needs at most 21 bits.

If your language's character type is too narrow then you have to use an encoding scheme (such as a Unicode Transformation Format or ISO-2022) to fit a larger repertoire into the available space. However, when you have done that your char is no longer a character. This causes a number of problems:

• strlen() no longer counts characters.
• random access into strings can lead to nonsense, e.g. if you miss a code shift sequence or you don't land on the start of a UTF-8 sequence or if you accidentally strip off a BOM.

In fact, even in the absence of encodings you have similar problems, e.g.

• the length of a string is not the same as the number of glyphs, because of combining characters.
• even in a fixed width font, the number of glyphs is not the same as the width of the string on the display, because some characters are double-width.

Even ASCII is not simple enough to be immune from problems:

• random access into strings can produce garbage if the string contains escape sequences.
• some logical characters (e.g. newline) are not represented as a single byte (i.e. CR LF).
• in some contexts you can use typewriter-style backspace/overstrike to implement something like combining characters.

On the other hand, if your language's string type is not based on bytes then you have the problem that strings need to be transcoded from their external form into something that the libraries prefer, since UTF-8 is winning the encoding wars.

I think that the solution to this problem is to embrace it, instead of trying to hide behind an inadequate abstraction. The essence of the bug is that, while it is meaningful to talk about a unicode codepoint in isolation, a codepoint is not a character and a string is not an array of codepoints: there is a layer of encoding between the conceptual sequence of codepoints and the representation of strings. (This implies that, although D is refreshingly agnostic about the size of its characters it still falls into the array trap and is chauvinistic towards a subset of Unicode transformation formats.)

What this means is that the language should not have a character or string type, but instead a type for binary blobs like Erlang's. The programmer manipulates binary values using pattern matching (it should probably support Erlang-style matching and some flavour of regular expressions) and some reasonably efficient way of construction by concatenation (as well as its syntax for binary comprehensions, Erlang has the concept of IO lists which support scatter/gather IO). The idea is to shift from thinking of sequences of discrete characters to thinking about strings as structured mass data.

Note that (so far) this design has no built-in preference for any particular string encoding, which should help to make it flexible enough to live gracefully in environments that favour all sorts of textual data, including ones not designed yet. However you need to support string constants reasonably gracefully, which either means that your source encoding is the same as the encoding you deal with at run time (so that the blobs in the source become identical blobs in the object) or you need a good way to transcode them. Ideally transcoding should only happen once, preferably at compile time, but it's probably OK to do it during static initialization. (Note that similar considerations apply to compiling regular expressions.)

To a large extent, what I'm doing is lifting the string representation chauvinism problem from the language level to the library level, and libraries are just as good as languages at growing ugly calluses around poorly-designed features - though you usually have to do less reimplementation when switching libraries. I'm also aiming to encourage a style of string manipulation more like perl's than C's. To succeed properly, though, it'll have to go further with encouraging good use of library support for international text - but at that point I'm stepping on to thin ice.

August, dark and dank and wet, brings more rain than any yet!

Our flat roof is having water permeability problems again. This time it has leaked onto the fire suppression system control panel and broken it, meaning that in the event of a fire someone will have to go downstairs to the room full of gas cylinders to welease Woger the suppwession gas. Should be fixed tomorrow...

Also, the delightful old computer lab tower (metal stairs and ugly wired glass cladding) is leaking copiously, and giving anyone who goes to the Titan rooms a light shower.

To program is to understand: The development of an information system is not just a matter of writing a program that does the job. It is of utmost importance that development of this program has revealed an in-depth understanding of the application domain; otherwise, the information system will probably not fit into the organization. During the development of such systems it is important that descriptions of the application domain are communicated between system specialists and the organization.

This quote is from the book Object-oriented programming in the BETA programming language, and is also quoted in the HOPL III paper The when, why and why not of the BETA programming language which I have recently enjoyed reading.

I've been playing around with Lua recently. It's a really sweet little language. A particular highlight is its "tables", which are generalized associative arrays that can have keys of any type. (Most languages only allow strings and/or numbers.) It also has pretty nice uniform handling of multiple function arguments, multiple return values, and multiple assignment.

A frequent topic of discussion on the Lua list is the fact that Lua does not have a switch/case statement. Most of the people who propose how one should be added tend to copy other languages which can only switch on one value at a time. I think it would me more in keeping with the rest of Lua to have a multi-valued case statement. I also quite like the idea of making it capable of ML-style pattern matching and variable binding.

The syntax I have in mind is as follows. I'm using ? to mean 0 or 1 of the following, * to mean 0 or more, and + to mean 1 or more.

    case explist1
+(+(match patlist
      ?(if exp) )
    then
        block)
  ?(else
        block)
    end

Lua also needs more expressive exception handling - I'm not too fond of its "protected call" mechanism. It would be more palatable if it were dressed up in something like:

    try
        block
+(+(catch patlist
      ?(if exp) )
    then
        block )
  ?(finally
        block )
    end

A useful bit of syntactic sugar is to be able to declare functions in a pattern matching style instead of an argument-passing style, so:

    function (...)
        case ...
        match a, b, c
            blah blah
        end
    end

    function
    match a, b, c
        blah blah
    end

I'm still pondering the syntax for pattern lists. A basic principle is that all direct comparisons should be against constants, so that the match can be compiled into a table lookup against a constant table. This means only numbers and strings - other objects in Lua either do not have compile-time expressions (C userdata) or have expressions that do not denote constant values but instead describe how to create new objects at run-time (function closures and tables). I also want to allow indirect comparisons against table elements, so that it's possible to match against structured data. Finally there needs to be a way of binding a variable to the value being matched against.

I do not intend to support exact matches against tables: only the elements that you specify in the match will be checked and if the table has more elements they will be ignored. This is because the extra check to make the match exact may not be entirely trivial to implement, and because it makes code brittle in the presence of unexpected values squirreled away in a table - it's quite common in prototype-based object systems to add methods to an object without co-operation from the code that created it.

So the basic syntax for a pattern to match against simple constants or to bind a variable is:

    String | Number | Name

    "{" pattern *( "," pattern ) "}"

It's also useful to both match against a table and bind a variable, so that you can refer to the table in the later statements. (It isn't possible to reconstruct the table because it may have extra elements, and even if it were possible it would be inefficient and the result would have a different identity.) It's also useful to both match a constant and bind a variable, if you have multiple match clauses: case f() match 3 match 4 then -- did f return three or four? I'm still unsure about the syntax for matching and binding. Some possibilities are:

    pattern and pattern
    pattern pattern
    Name "=" pattern
    Name "==" pattern

The idea of "and" patterns is that you are matching both the left-hand side and the right-hand side. It suggests that there should also be "or" patterns, as in case f() match 3 or 4 then ... In MCPL you get the same effect as and by just writing the patterns side-by-side, and (like sh) | is used instead of or.

The idea of using "=" is to make binding in a pattern look like assignment, whereas "==" is supposed to be like an assertion. However these get problematic when we try to fit key/value style table matching into the syntax. Table constructors in Lua look like:

    tableconstructor = "{" ?fieldlist "}"
    fieldlist = field *(fieldsep field) ?fieldsep
    fieldsep = "," | ";"
    field = "[" exp "]" "=" exp
        | Name "=" exp
        | exp

If we follow constructor syntax closely, we get the serious difficulty that a pattern like { foo = bar } isn't clear which name is the table index and which is the variable being bound. This probably indicates that = should be avoided.

Perhaps the solution is to use an arrow to indicate which way values flow, as in:

    tablepattern = "{" ?fieldpatterns "}"
    fieldpatterns = fieldpat *(fieldsep fieldpat) ?fieldsep
    fieldpat = "[" (String | Number) "]" "->" pattern
        | Name "->" pattern
        | pattern
    pattern = String | Number | Name
        | pattern and pattern
        | pattern or pattern

It makes me want to change the assignment operator to <- for symmetry :-) But fiddling with Lua's existing features is the topic for another post.

One of the features I like about Firefox is when I run firefox (from the command line or from my window manager) it will start it if it isn't running, and it'll open a new window if it is. I have a lot of virtual desktops, and it is much more convenient to just run firefox than to find a desktop with an existing firefox window, create a new window, then move it to the target desktop. Sadly emacs is not so accommodating.

Emacs has a feature which allows you to tell a running emacs to start editing a file. However it does not open a new frame to display the file, so you have to go searching through your virtual desktops to find where it ended up.

I run emacs version 21, but version 22's emacsclient has a new -e (eval) option which allows you to tell emacs to run arbitrary lisp. This can solve the niggles I have described: e.g. to open a new emacs frame on the current desktop I could just run emacsclient -e '(make-frame)'. It would be nice to have this feature in version 21, so I have come up with an evil hack to do the job.

My original idea was that I could set up a file with a local variables section, including an "eval" specifier that tells emacs to open a new frame. Then opening the file would create a new frame. However emacs is sensibly paranoid and won't run lisp in arbitrary files without manual confirmation.

Plan B was to add a function to the find file hook, so that when I opened a specific file (that need not exist) the necessary magic would occur. Then running emacsclient --no-wait ~/.emacs-newframe would create a new frame. After some fiddling I made this work. The code in my .emacs is as follows. As well as creating a new frame, it kills the buffer containing the dummy file and switches the new frame to the canonical dummy buffer, to keep things tidy. It uses the server-visit-hook which is a bit more specific for my purpose than the file-find-hook.

(defun fanf-newframe ()
  (cond ((string-equal buffer-file-name "/home/fanf2/.emacs-newframe")
	 (kill-buffer nil)
	 (select-frame (make-frame))
	 (switch-to-buffer "*scratch*"))))

(add-hook 'server-visit-hook 'fanf-newframe)

A little wrapper script can start emacs or run emacsclient as necessary, to get behaviour like firefox. Instead of running bare emacsclient, it can now also create a new frame before asking emacs to visit a file, which is a bit nicer. However doing so may be racy because I can't make emacsclient ~/.emacs-newframe (without --no-wait) work sensibly: the hook runs before the buffer is registered as being visited by emacsclient, so the hook can't tell the server that the buffer is finished with after it is sure the frame exists. However emacs is not internally multi-threaded and the server handles requests in-order, so it's probably OK.

Between returning from San Francisco and getting my job at the University, I did some FreeBSD-related things. One of its features which captured my interest was its kernel object system, kobj. This was designed to make the driver ABI more dynamic so that modules compiled against older source could be loaded into newer kernels and still work. The problem is that if a driver call is changed, you don't want to have to add compatibility tests to every call point in the kernel. FreeBSD uses kobj to solve this problem by making drivers into classes (such that each object of the class represents a device controlled by the driver) so that driver calls become method calls. What caught my interest is that the method calls are much more dynamic than I was used to from languages like C++.

C++ does method lookup using an array of method pointers called a vtbl. The static type of the object determines the layout of the vtbl, i.e. which method pointer is at which index in the table. (The dynamic type of the object may be a derived type of its static type, in which case the vtbl contains more entries than are determined by the static type.) A method call object.method(args) compiles to object.vtbl[method_index](args). This is no good for our problem because any change to a class's methods changes its ABI and means that old code will no longer work.

In kobj, the method lookup table is a cache, so that method lookups are fast in the normal case, but fall back to a more complicated dynamic lookup if there is a cache miss. This means that if a new method is called against an old object then the lookup code can return a pointer to a compatibility shim method instead of one of the methods defined by the object's class. I'm going to show you my version of the method call sequence, but I need to explain a few basics first. In kobj (and my object system cobj) a class is just a collection of method implementations: there is no type system determining the set of methods implemented by a class. The most obvious consequence is that method declarations are divorced from classes. They are effectively just names, like method selectors in Smalltalk. A method has several parts: at compile time it has an inline function that is used to call the method, and a type so that implementations and calls can be checked; at run time it has an extern object that serves to represent the method selector.

	/* In a header file somewhere... */

	/* The type signature of my_method() */
	typedef int my_method_t(cobj_t *o, int a, void *p);

	/* An extern object representing the method selector.
	 * It is not declared as a pointer because we want to
	 * be able to get its address efficiently: addresses
	 * are resolved at link time, saving an indirection
	 * at run time. The object itself is just a place-
	 * holder, but may be useful for introspection.
	 */
	extern struct cobj_meth_t my_method_sel;

	/* Method dispatch is implemented as an inline function.
	 * The actual code is the same for all methods, except
	 * for variations in the types, and would normally be
	 * created with a macro.
	 */
	static inline int my_method(cobj_t *o, int a, void *p) {
		cobj_mi_t *mi = &o->cobj_mi[COBJ_HASH(&my_method_sel)];
		if(mi.m != &my_method_sel)
			cobj_lookup(o, &my_method_sel);
		return ((my_method_t*)mi.i)(o, a, p);
	}

The lookup cache is an array of {method,implementation} pairs, indexed by a hash of the method selector. If the selector doesn't match then we call the dynamic lookup function to find the implementation and fill in the table entry. Then we can just do an indirect call of the implementation. The hash function is defined to be as lightweight as possible:

	/* In the main cobj header file... */

	typedef void cobj_impl_t(void);

	/* {method,implementation} pairs */
	typedef struct cobj_mi_t {
		cobj_meth_t *m;
		cobj_impl_t *i;
	} cobj_mi_t;

	/* standard prefix of all objects */
	#define COBJ_PREFIX cobj_mi_t *cobj_mi

	typedef struct cobj_t {
		COBJ_PREFIX;
	} cobj_t;

	#define COBJ_MI_SIZE 32
	#define COBJ_HASH(m) (((int)(m) / sizeof(cobj_mi_t)) % COBJ_MI_SIZE)

As well as the explicit operations for computing the hash, the compiler needs to multiply it by sizeof(cobj_mi_t) when indexing the cache. The resulting combination will just compile to (m & 0xF8) - i.e. we use the most random bits from the method object's address as the index.

In kobj, the lookup function was fixed. Classes just consisted of a lookup cache shared by all instances, and a simple table of {method,implementation} pairs that the dynamic lookup function could search. Objects had a similarly simple structure: they were just structs whose first member pointed to the object's class's method cache. There was no support for inheritance; however some parts of the kernel had hacked up their own implementations using the C++ layout with the base class's members as the prefix of the object with the derived class's members following. The problem with this is it introduces another opportunity for ABI incompatibility: if the base class changes size then all derived classes need to be recompiled.

I was interested in extending the object system to allow inheritance of various kinds whilst avoiding as much ABI coupling as possible. I had read the Art of the Metaobject Protocol so I was also interested in playing around with object systems where you could replace key parts like object layout, inheritance structure, etc.

In a traditional OO system, each class is also an object. The class-dependent operations are things like dynamic method lookup and object creation. If a class is an object then these operations should be methods on the class object. This implies that a class must be an instance of a class, which in Smalltalk terminology is called a metaclass. I envisioned having different metaclasses to implement simple method lookup, single inheritance, multiple inheritance, mixin inheritance, etc. Thus the dynamic lookup function just juggles things so that it can perform the appropriate method invocation on the original object's class and save the result in the cache.

	/* In the main cobj header file... */

	/* common prefix of class objects */
	#define COBJ_CLASS_PREFIX COBJ_PREFIX; cobj_mi_t cache[COBJ_MI_SIZE]

	typedef struct cobj_class_t {
		COBJ_CLASS_PREFIX;
	} cobj_class_t;

	static inline cobj_t *cobj_class(cobj_t *obj) {
		void *cache = obj->cobj_mi;
		void *class = (char *)cache - offsetof(cobj_class_t, cache);
		return(class);
	}

	/* In the main cobj code file... */

	void cobj_lookup(cobj_t *obj, cobj_meth_t *meth) {
		cobj_mi_t *mi = &obj->cobj_mi[COBJ_HASH(meth)];
		mi->i = cobj_do_lookup(cobj_class(obj), meth, obj);
		mi->m = meth;
	}

This function is designed to make the method dispatch fast path as small as possible, particularly by minimizing the number of arguments. It is also the vehicle for recursion up through the metaclasses. Since a class is an object with an implementation of the cobj_do_lookup() method, and a metaclass is the class of a class, metaclasses are also objects with implementations of the cobj_do_lookup() method. Obviously we need a way to bound the recursion.

Eventually we must reach the class that is its own metaclass. The safe way is to detect this case in cobj_lookup() and call a hardcoded cobj_do_lookup_base() implementation. This tactic allows the ur-class to be a fairly normal class that supports other methods (e.g. for introspection or construction). A much more amusing way is to arrange that the ur-class only has one method, so we can pre-populate its cache. (We can't do this if there's more than one method because we don't know what addresses and therefore indexes they will have - and they might clash). Then the recursion will always terminate with a cache hit. You then need a slightly more elaborate bootstrap strategy. The ur-class is the metaclass of classes with one method, of which there will be a zeroth instance with the pre-populated cache. There will be one other instance which knows how to do method lookup for simple classes with more than one method but no inheritance etc. This will in turn have an instance which is the same as the safe (boring) ur-class.

	struct cobj_class_ur {
		COBJ_CLASS_PREFIX;
		cobj_impl_t *do_lookup;
	} cobj_zero = {
		/* cache pointer */
		&cobj_zero.cobj_mi,
		/* pre-populated cache */
		{ { cobj_do_lookup_o, cobj_do_lookup_ur },
		  /* COBJ_MI_SIZE times... */ 	
		  { cobj_do_lookup_o, cobj_do_lookup_ur } },
		/* the only method we support */
		(cobj_impl_t *)cobj_do_lookup_ur
	}, cobj_one = {
		/* cache pointer */
		&cobj_zero.cobj_mi,
		/* no need to pre-populate this cache */
		{ { NULL, NULL } },
		/* the only method we support */
		(cobj_impl_t *)cobj_do_lookup_simple
	};

	cobj_impl_t *cobj_do_lookup_ur(cobj_t *class, cobj_meth_t *meth, cobj_t *obj) {
		assert(meth == cobj_do_lookup_sel);
		return(class->do_lookup);
	}

Apart from the goal of supporting different kinds of inheritance, this metaclass approach is very like Smalltalk (including the recursion back to a class that is its own metaclass), and Objective C is very like Smalltalk. However they are not solutions to the ABI skew problem (or the API skew problem!) that I started with, because in Smalltalk and Objective C the members of base classes and the size of base objects are exposed to derived classes, so you can't extend a base class without losing compatibility.

This was all quite fun to play with, but unfortunately I got hung up on writing a preprocessor to make declaring classes and methods less painful, so it never got very far before I got a job.

Previously: part 1 part 2 part 3 part 4 part 5a part 5b part 5c part 6

Message content scanning is vital for blocking viruses and spam that aren't blocked by DNSBLs. Unfortunately the interface between MTAs and scanners varies wildly depending on the MTA and the scanner - there are no good standards in this area. However I'm going to ignore that cesspit for now, and instead concentrate on when the scanning is performed relative to other message processing. As you might expect, most of the time it is done wrong. Fortunately for me the Postfix documentation has an excellent catalogue of wrong ways that I can refer to in this article.

An old approach is for the MTA to deliver the message to the scanner which then re-injects it into the MTA. The MTA needs to distinguish messages from outside and messages from the scanner so that the former are scanned and the latter are delivered normally. The Postfix documentation describes doing the delivery and re-injection in the "simple" way via a pipe and the sendmail command, or in the "advanced" way via SMTP. The usual way to do this with Exim is to tell Exim to deliver to itself using BSMTP over a pipe, using the transport filter feature to invoke the scanner. This setup has a couple of disadvantages that are worth noting. It (at a minimum) doubles your load because each message is received and delivered twice. It also makes the logs confusing to read, since the message has a different queue ID before and after scanning and therefore different IDs when it is originally received and finally delivered.

Another arrangement is MailScanner's bump-in-the-queue setup. The MTA is configured to leave messages in the queue after receiving them, instead of delivering them immediately as it usually would. MailScanner picks them up fairly promptly - it scans the queue every second or two - and after scanning them, drops them in a second queue then tells the MTA to deliver the messages from this second queue. MailScanner has the advantage that it can work in batch mode, so when load is high (several messages arrive between incoming queue scans) the scanner startup cost is spread more thinly. This is useful for old-fashioned scanners that can't be daemonized. Apart from the scanning itself, its only overhead is moving the messages between queues. MailScanner also preserves queue IDs, keeping logs simple. A key disadvantage is that MailScanner needs intimate knowledge of the MTA's queue format, which is usually considered private to the MTA. Sendmail and Exim do at least document their queue formats, though MailScanner is still vulnerable to format changes (e.g. Exim's recent extension to ACL variable syntax). Postfix is much more shy of its private parts, so there's a long-standing argument between people who want to use MailScanner and Wietse Venema who insists that it is completely wrong to fiddle with the queue in this way.

So far I have completely ignored the most important problem that both these designs have. It is too late to identify junk email after you have accepted responsibility for delivering it. You can't bounce the junk, because it will have a bogus return path so the bounce will go to the wrong place. You can't discard it because of the risk of throwing away legitimate email. You can't quarantine it or file it in a junk mailbox, because people will not check the quarantine and the ultimate effect will be the same as discarding. (Perhaps I exaggerate a bit: If the recipient doesn't get an expected message promptly, or if the sender contacts them out of band because they didn't get a reply, the recipient can at least look in the quarantine for it. However you can only expect people to check their quarantines for unexpected misclassified email if the volume of junk in the quarantine is relatively small. Which means the quarantine should be reserved for the most difficult-to-classify messages.)

You must design the MTA to scan email during the SMTP conversation, before it accepts responsibility for the message. It can then reject messages that smell bad. Software that sends junk will just drop a rejected message, whereas legitimate software will generate a bounce to inform the sender of the problem. You minimise the problem of spam backscatter and legitimate senders still get prompt notification of false positives. However you become much more vulnerable to overload: If you scan messages after accepting them, you can deal with an overload situation by letting a backlog build up, to be dealt with when the load goes down again. You do not have this latitude with SMTP-time scanning.

The Postfix before-queue content filter setup uses the Postfix smtpd on the front end to do non-content anti-spam checks (e.g. DNS blacklists and address verification), and then passes the messages through the scanner using SMTP (in a similar manner to Postfix's "advanced" after-queue filters) then in turn to another instance of the smtpd which inserts the message into the queue. There is minimal buffering before the scanner, so the whole message must be scanned in memory as it comes in, which means the scanner's concurrency is the same as the number of incoming connections. This is a waste: messages come in over the network slowly; if you buffer them so that you can pass them to the scanner at full speed, you can handle the same volume of email with lower scanner concurrency, saving memory resources or increasing the number of connections you can handle at once. However you don't want to buffer large messages in memory because that brings back the problem in another form. You also don't want to buffer them on disk, since that would add overhead to the slowest part of the system - unless you use the queue file as the buffer. This implies that Posfix's before-queue filtering is too early since the writing to disk happens after the message has gone through the scanner.

Sendmail's milter API couples scanners to the MTA in about the same place as Postfix's before-queue content filter, so it has the same performance problems. (Actually, in some cases it is worse: If you have a filter that wants to modify the message body, then with Postfix it can in principle do so in streaming mode with minimal in-memory buffering, whereas with Sendmail the milter API forces it to buffer the entire message before it can start emitting the modified version.) What's more interesting is their contrasting approach to protocol design. Postfix goes for a simple open standard on-the-wire protocol as the interface to its scanners. However it misses its target: It speaks a simplified version of SMTP to the scanner, with a non-standard protocol extension to pass information about the client through to Postfix's back end. The simplification means that Postfix cannot offer SMTP extensions such as BINARYMIME if the scanner does not do so too, which is a bit crippling. Sendmail goes for an open API, and expects scanners to link to a library that provides this API. The connection to the MTA is a private undocumented protocol internal to Sendmail, and subject to change between versions. This decouples scanners from the details of SMTP, but instead couples them to Sendmail. This is terrible for interoperability - and in practice it's futile to fight against interoperability by making the protocol private, because people will create independent implementations of it anyway: 1 2 3. So I don't like the Postfix or the Sendmail approaches, both because of their performance characteristics and because of their bad interfaces.

Exim is agnostic about its interface to scanners: it has sections of code that talk directly to each of the popular scanners, e.g. SpamAssassin, ClamAV, etc. This is rather inefficient in terms of development resources (though the protocols tend to be simple), and is succumbing to exactly the Babel that Postfix and Sendmail were trying to avoid. Exim's approach has the potential to be better from the performance point of view: It writes the message to disk before passing it to the scanner at full speed, so in principle the same file could act as the buffer for the scanner and the queue file for later delivery. This would mean there are no overheads for buffering messages that are accepted; if the message is rejected then it will only hit the disk if the machine is under memory pressure. Sadly the current implementation formats the message to a second file on disk before passing it to the scanner(s), instead of formatting it in the process of piping it to the scanner. The other weakness is that although there is a limit on the number of concurrent SMTP connections, you can't set a lower limit on the number of messages being scanned at once. You must instead rely on the scanners themselves to implement concurrency limits, and avoid undaemonized scanners that don't have such limits. This is probably adequate for many setups, but it means the MTA can't make use of its greater knowledge to do things like prioritize internal traffic over external traffic in the event of overload.

So, having criticised everything in sight, what properties do we want from the MTA's interface to scanners? In general, we would like the logistics of passing the message to the scanner to add no significant overhead - i.e. the cost should be the same as receiving the message and scanning the message considered separately, with nothing added to plug these processes together. Furthermore we'd like to save scanners from having to duplicate functionality that already exists in the MTA. Specifically:

• Buffer the message in its queue file before scanning, so that the scanner does not take longer than necessary because it is limited by the client's sending speed.
• Insulate the scanner from the details of SMTP extensions and wire formats, without compromising the MTA's support for same. This implies that any reformatting (e.g. downgrade binary attachments to base64) needed by the scanner should not pessimize onward delivery.
• Put sensible limits on the concurrency demanded of the scanner to maximise its throughput. Use short-term queueing and scheduling (a few seconds) to handle spikes in load.
• Cache scanner results.
• Put a security boundary between the MTA and the scanner.

Notice that these have a certain commonality with callout address verification, which also needs a results cache, concurrency limits, and a queue / scheduler. This gives me the idea for what I call "data callouts" for content scanning, based on a loose analogy between verifying that the message's addresses are OK and verifying that the message's contents are OK. Also notice that message reformatting and security boundaries are requirements for local delivery. So a "data callout" is essentially a special kind of local delivery that the MTA performs before sending its reply to the last of the message data; it's a special kind of delivery because it is only done to check for success or failure - unlike normal deliveries the message isn't stored in a mailbox. This design makes good use of existing infrastructure: The MTA can use its global scheduler to manage the load on the scanner. There is already lots of variability in local delivery, so the variability in content scanner protocols fits in nicely.

The data callout is actually a special case of "early delivery", i.e. delivering a message before telling the client that it has been accepted. This feature gives you a massive performance boost, since you can relay a message without touching disk at all (except to log!). If you are going to attempt this stunt then you need a coherent way to deal with problems caused by the early delivery taking too long. Probably the best plan is to ensure that a very slow diskless early delivery can be converted to a normal on-disk delivery, so that a response can be given to the client before it times out, and so that the effort spent on delivery so far is not wasted. This is similar to allowing lengthy callouts address verifications to continue even after the client that triggered them has gone, so that the callout cache will be populated with a result that can be returned quickly when the client retries. (I'm not sure if it's worth doing the same thing with data callouts, or if a slow scanner more likely indicates some nasty problem that the MTA should back away from.)

The Postfix and Sendmail filter interfaces have a feature that is missing from Exim's scanner interface and my data callout idea. The filters can modify the message, whereas the scanners can only return a short result (such as a score). Message mangling is not something I particularly approve of, but it is a popular requirement. Fortunately my idea can support it, by going back to the old approach of delivering the message to the scanner which then re-injects it. Early delivery removes most of the disadvantages from this technique: it happens before we accept the message, and it doesn't add to disk load. It adds a new advantage of being able to fall back gracefully from scan-then-accept to accept-then-scan in the event of overload, if that's what you want. It still has the disadvantages of log obfuscation and depending on the scanner to support advanced SMTP features (though perhaps these can be avoided with a better filter protocol).

I hope that this convinces you that - as I said in my last essay - lots of cool things become possible if you get callouts right. This essay also serves as a response to iwj10, who complained that my log-structured queue idea was a pointless optimisation because early delivery is much more effective. He wasn't convinced when I said that early delivery was a separate problem. Even when you have early delivery - so that the queue only contains very slow or undeliverable messages - the log-structured queue reduces the effort required to work out which messages to retry next because the necessary information is stored in the right order.

(This isn't really part of my "how not to design an MTA" series since I don't have much to say about how other MTAs do it. That's mainly because most of them don't have schedulers to speak of. Postfix has one, but it isn't able to pipeline messages down a connection, and it doesn't have a centralized router. Its current queue manager is described in the attachment linked from a message to postfix-devel from Patrik Rak.)

There are two important parts of an MTA that need a concurrent scheduler: routing (where you want concurrent DNS/LDAP/etc. lookups) and delivery (where you want concurrent connections to remote hosts). (Aside: incoming messages are also concurrent but in this case the demand arises externally so can't be scheduled).

Scheduling is tricky because of the mix of work that we have to handle. Messages can have multiple recipients: the vast majority (around 90%) have only a single recipient, but those with more than one can have very large envelopes if they combine mailing list and alias expansion. Remote systems can respond with varying speed: as well as DNS and SMTP being slow because of network latency or brokenness, SMTP servers sometimes introduce delays deliberately to cause problems for clients they think are bad in some way.

(Note: a big message has lots of data whereas a big envelope belongs to a message with lots of recipients.)

In the following I'll talk about jobs and workers to abstract from the differences between routing and delivery. In routing a job is just a recipient that needs to be routed, and the workers are routing processes; the workers are all equivalent and we have not yet found any differences between the jobs. In delivery, a job is a subset of the recipients for a message which can all be delivered to the same place, and a worker is a connection to a remote SMTP server or to a local delivery agent; there is more complexity because it's more efficient to re-use a connection for jobs routed to its destination than to handle each delivery independently.

First I'll examine the basics that are shared between routing and delivery. It's worth looking at a couple of simple schedulers that don't work.

1. Do not allocate jobs to workers on a first-come-first-served basis. A big envelope may be able to use up your resources, holding back other messages. Once you have dealt with all its fast jobs you will be dealing with just slow jobs, so your throughput will be poor.

2. Do not allocate an equal number of workers to each message. When you are heavily loaded each message will only have one worker each, which means that large envelopes will be processed serially - but we want to make use of concurrency to handle large envelopes effectively.

A possible compromise is to use a FCFS scheduler up to some maximum concurrency per message. However a maximum that makes sense on a heavily-loaded system means that big envelopes won't be able to make use of the spare resources on a lightly-loaded system. So we need a way to scale up the maximum if there are free workers.

	def allowed_new_worker(job):
		if job.message.concurrency < max_message_concurrency
		then return true
		else if job.message.concurrency < scale_max_concurrency * free_workers
		then return true
		else return false
		end

A scale factor of 10 means that a message can use about 91% of an otherwise-idle system, or two messages can use 47% each, etc. If a second big envelope comes along when the first one already has 91% of the system, then message 2 will slurp up the remaining 9% (assuming that is less than the max_message_concurrency) and as jobs in message 1 complete message 2 will take over their workers until the new equilibrium is reached.

	def next_router_job(jobs):
		if allowed_new_worker(jobs.first)
		then return jobs.first
		else return next_router_job(jobs.rest)
		end

The allowed_new_worker() function is still useful in the delivery scheduler, but we want to spread the cost of connection set-up by delivering multiple messages down each connection. If we are going to make good use of pipelining we should allocate new deliveries to connections before the previous deliveries are complete, i.e. there can be a queue of multiple jobs per worker. Furthermore, if a worker is overloaded (its queue is backlogging) we need to open another connection to a suitable destination; we should do so in a way that spreads the load across the possible destinations. We also need to detect when the load has dropped and we can close a connection.

This will depend on a database of destinations, destdb. For broken destinations it records when we should next bother to try to connecting to them. It allows us to look up efficiently any connection(s) that we have currently open to a destination, whether they are active or idle, and how old they are. When we close the last connection to a destination, we keep a record of when it was made to help the decision of where to open new connections. The destdb has a garbage collector to remove stale retry and closed-connection records.

When deciding which worker to use for a delivery job, we first classify its possible destinations (initially just the primary destinations) based on destdb into active, idle, closed, unused (absent from destdb), and retry (in which case we omit destinations that have not passed their retry time).

First sort the active list by connection time and traverse it from most recent to least recent. If we find one that has less than the backlog threshold then the first we find is the worker for this job. We prefer recent connections so that when our load goes down older connections will become idle and eventually be closed.

If this fails then check if this job is allowed to use a new worker. If it is not, we still allocate it to an active connection so that big envelopes can get a free ride off smaller ones. Note that this means their concurrency can be higher than the configured maximum even under load. We choose the first connection in the active list that has fewer jobs than the newest active connection (to spread the load evenly). If they all have the same number of jobs, use the first one. If there are no active connections then this job must wait to be rescheduled when a worker becomes free. (We can fall back to this procedure a couple of other ways below.)

The alternative case is that we have a job which can and should use a new worker. If there are destinations on its idle list the job should use the most recent one (which presumably was active until not long ago). Otherwise we are going to open a new connection. If the system has no unused workers (or idle ones that we can close) to handle the new connection, then add the job to an active connection as above.

If there are destinations on its unused list the job should pick one at random and use that. This will become a new connection which will attract new jobs, thereby spreading our load onto a part of the destination cluster we haven't used yet. Otherwise, we have previously used all the possible destinations. If there are destinations on the closed list, pick the oldest. This means we will spread our load around the destination cluster round-robin style, though in a random order because of the way we pick previously-unused destinations. Finally, if there are destinations on the retry list, try one of them at random. Since this is the last option, we will normally not retry a destination until its record is garbage-collected from destdb (causing it to appear on the unused list), unless we are under load.

At this point we have failed to find a candidate destination. There are two possibilities: all of the working destinations have active connections, or all of them failed the retry time check. In the first case, we open another connection to a destination picked at random from those with the fewest concurrent connections. If they have all reached their per-destination concurrency limit, add the job to an active connection as above.

In the second case, none of the job's primary destinations are currently working. So we repeat the whole process from the classification stage using the secondary destination list. If necessary we can fall back to the tertiary etc. destinations. If we run out of fallbacks then the message must be deferred for later retry.

That wraps up the delivery job scheduling algorithm.

I should note that there are a number of mechanisms that cause connections to be closed, so that the MTA can recover unused resources. Firstly, idle connections can be closed if the worker is required for a new connection. Secondly, we should have an ageing mechanism that closes connections after some period of time; it may be worth using different times for active and idle connections. (We want to close active connections after a time to spread load around even when it is low.) Thirdly, remote MTAs can close connections whenever they wish. If the connection has a queue of pending jobs when it is closed then these must be re-scheduled.

If the MTA is part of a cluster, the destdb should ideally be shared. This allows hosts to pool their knowledge of which hosts are down and when to retry, and it means that the destination load balancing will work across the cluster. (It would not be too difficult to implement this feature for Exim's hints databases.)

There is a little scope for simplification, because it probably isn't worth keeping track of closed connections. (I described them because I wanted to note my thoughts fairly completely.) It's probably OK to remove the special case handling for retries too, and instead rely on the destdb garbage collector.

Note that it probably isn't worth worrying about a large envelope using all your resources, because SMTP only guarantees that envelopes of up to 100 recipients will work. To encounter problems you would probably have to configure your mailing list manager to use large envelopes. (I'm assuming that you are using modern concurrency techniques, i.e. hundreds of connections per process, not one per process.) On the other hand it probably is worth taking care to limit the load imposed from outside (attackers) by smtp-time verification. You can do so within the above framework by assigning all verifications to a pseudo-message, which would probably have specially tuned concurrency settings.

The essentials

A clock consists of:

• an oscillator that ticks at a frequency which (ideally) is accurately known and stable over long periods of time;
• and a counter which keeps track of the ticks.

Traditional clocks have a counter which directly represents civil time (12 hours per half day or 24 hours per day, 60 minutes per hour, etc.) but in computing it's more usual to have a binary counter with a separate mechanism to translate its value into civil time.

The visible part of the counter does not necessarily count ticks directly: its low-order digits may be invisible. For example, wrist watches often have a quartz oscillator that ticks at 32,768 Hz but a fastest hand that moves once per second. On the other hand, in computing the counter may have a higher resolution than the tick granularity. For example, on Unix gettimeofday() returns the value of a counter with a resolution of 1μs but a granularity of typically 100 Hz or 1000 Hz. A counter's interval is the amount it is incremented by for each tick, so 10,000 or 1000 for the gettimeofday() example.

Types of clock

A real-time clock or RTC can be used to keep civil time. As well as an oscillator and a counter, it has an epoch, which is the point in civil time at which the counter's value was zero, and a mapping between other values of the counter and civil time. This mapping is generally complicated and dependent on what kind of civil time you want.

In my terminology, a clock that is not a real-time clock is a timer.

An interval timer counts time like a real-time clock but does not have a mapping to civil time.

A countdown timer has a negative interval and typically triggers some action when its counter reaches zero.

An activity timer does not tick continuously but only when some activity is being performed, for example when a process is running on the CPU. It may even tick faster than its nominal frequency, for example if a process has threads running on multiple CPUs.

Correcting clocks

The terminology I use when correcting a clock varies depending on which of the clock's parameters I am changing.

You can reset the counter to step the clock to the correct time. Unexpected resets can confuse software that makes unwarranted assumptions about a clock.

You can adjust the rate of a clock. This usually means that the counter interval is changed, not the frequency of the hardware oscillator! This might be done to slew the clock to the correct time as well as to correct a systematic error in the clock's nominal frequency.

You can change the epoch of a clock. In practice most clocks have fixed epochs and are corrected by resetting their counters.

Clocks may be corrected automatically. A good way of doing this on a networked machine is with NTP which avoids resetting the clock if it can, but it has been common for crappier systems to use less clever protocols.

A clock that is stabilized is automatically adjusted to conform to a frequency standard. A clock that is synchronized is automatically corrected to conform to civil time. It's possible to have one without the other in either direction.

Mapping to civil time

A monotonic clock cannot be reset, so you can only make gross corrections by changing its epoch. It's common for computer systems to provide monotonic clocks without any mapping to civil time, in which case they are there for use as interval timers.

A clock that keeps atomic time counts SI seconds and has a trivial mapping to TAI. (Monotonic clocks keep atomic time.) The system must have an up-to-date table of leap seconds in order to map atomic-time clocks to civil time.

Clocks that don't keep atomic time keep some kind of universal time. The POSIX and NTP clocks are examples. They have to have some kind of fudge to deal with UTC leap seconds. They may reset the clock or vary its rate on or near a leap second.

Some very limited computer systems do not have any sophistication in the mapping between their clock and civil time, so the clock just represents local time fairly directly. This implies that the clock is reset when Summer Time transitions occur.

Complications

It is common for clocks to be made more complicated so that they include some of the semantics of civil time. They may represent the counter with a non-uniform base similar to the one we use for writing times in natural language, or include mechanisms for handling leap seconds. (A linear counter has a simple integer or fixed-point representation.)

For example, the clock accessed via ntp_gettime() has an additional field that can warn about an impending leap second or that one is currently in progress.

For a hypothetical example, counters like the one returned by gettimeofday() have separate parts that count seconds and fractions of seconds. Markus Kuhn suggests that you could represent leap seconds as double-length seconds where the sub-second part of the counter increments past the point where it would normally carry into the seconds part.

These complications are motivated by keeping the mapping between counter values and civil time simple. Since time is promulgated in the form of UTC rather than TAI, and common external time representations (POSIX, NTP, etc) are based on UT, this makes some sense. However it means that the clock is not suitable for use as the basis of an interval or countdown timer.

Simplifying the kernel

Ideally the kernel could just provide simple time counters and leave all civil time handling to userland. Unfortunately that isn't quite possible because of API compatibility constraints (POSIX time) and file systems have to store time stamps as representations of civil time. However the kernel does not have to deal with times other than the present, or simple interval computations. So it could just represent other clocks as epoch adjustments to a master monotonic clock.

Summary of clock properties

• counter value
• tick interval
• counter resolution
• epoch (only for RTCs)

Flags

• stabilized
• synchronized (only for RTCs)

Types of clock

• countdown timer
• activity timer (possibly several variants)
• interval timer
• monotonic timer
• monotonic RTC
• atomic
• universal w/ rate change around leap seconds
• universal w/ resets at leap seconds
• universal w/ variable-length seconds (not with linear counters)
• local time

Next Wednesday (29th November) is going to be busy.

In the afternoon there will be a Techlinks meeting to introduce new IT staff to the Computing Service. I'll be standing up briefly to say HELO on behalf of Mail Support, and so I have produced a "crib sheet" which lists most of what we do so that I won't have to. I only have a few minutes so there won't be enough time to say anything substantial, and anyway it can wait until my full-length techlinks next term.

In the evening I'll be helping Bob to give a tour of our computer room. This is principally for students, but any interested member of the University is welcome. Email me for more info.

I've recently been pondering models of concurrent programming. One of the simplest, most beautiful and most powerful is the π calculus - it's effetively the λ calculus of concurrent programming.

The π calculus is oriented around channels, which can be read from, written to, and passed along channels: that is, they can be passed between processes (though processes are implicit). Reading and writing are synchronous: if a process wants to read or write a channel, it blocks until there is another process wanting to do the opposite, and after the communication both processes can proceed with their sequels. The alternative to this is for writes to be asynchronous: they do not block.

The problem with synchronous writes is that they do not translate well into a distributed setting. An asynchronous write translates directly into a network transmission, but a synchronous write requires a round trip to unblock the writer. As a result it is less efficient and more vulnerable to failure. Even in a simple local setting, asynchronous sends may be preferable: in fact, Pict, a programming language closely based on the π calculus, is restricted to asynchronous writes. On the other hand, with asynchronous writes you may need a queue on the reader's end, and some way to avoid running out of memory because of overflowing queues.

Another design alternative is to focus on processes instead of channels. Messages are sent to processes, and PIDs can be transmitted between processes . In this model the read ends of channels are effectively fixed. This is the actor model as used by Erlang.

The problem with the π calculus's channels, or a distributed-object system like Obliq or E (see §17.4 on p. 126), is that you need distributed garbage collection. If I spawn a process to listen on a channel locally, and send the channel to a remote system, I must keep the process around as long as that remote system may want to write on the channel. Distributed garbage collection is far too difficult. On the other hand, in the actor model a process is the master of its own lifetime, because it lasts until its thread of execution completes. Thus you avoid relying on tricky algorithms, at the cost of needing some way of dealing with failed message sends. But in a distributed system you have to deal with failure anyway, and the same mechanism can deal with the queue overflow problem.

So I conclude that the π calculus is wrong for distributed programming and that Erlang's actor model is right. Those Erlang designers are clever chaps.

Iterators are used in some programming languages to generalise the for loop. They were introduced by CLU in the 1970s and have been adopted by Python and Lua, amongst others. They are traditionally a special kind of function that has yield statements that return successive values in the iteration. This function is called at the start of the loop, and when it yields, the loop body is run. Each time round the loop the function is resumed until it yields again.

The iterator's activation frame is typically on top of the stack. This seems a bit backwards to me, because it leads to contortions to maintain the iterator's state between yields, e.g. using an auxiliary object or first-class closures. (See the first example here.)

I think it's simpler to desugar a for loop like this:

    for varlist in iterator(arglist) do
        statements
    loop

into

    iterator(
        (varlist): do
            statements
        end,
        arglist)

That is, you turn the loop body into an anonymous function which is passed to the iterator function. Instead of yielding, the iterator just calls the body function. The iterator can then be written as a normal loop without contortions to keep state between yields. (Pretty much like this, in fact.)

What makes this slightly interesting is how to desugar break, continue, and return statements inside the loop. A continue becomes just a return from the anonymous function, but the others have to escape from the iterator function as well as the anonymous function. This could be done with exceptions or continuation passing.

At the end of http://fanf.livejournal.com/65911.html I mentioned that it might be beneficial to have multiple queues, in order to reduce the density of garbage in the older parts of the queue. There are at least a couple of other reasons why one might want multiple queues.

Even faster

In the absence of any other bottlenecks, the MTA is going to be limited by the rate that it can fsync the main queue. You can raise this limit if you have two parallel queues on different disks, and spread the load of incoming messages between them. I got this idea from the Sendmail X design document which describes a similar (but not quite so neat) queue structure to the one I have been describing.

TURN

SMTP's TURN feature allows a client to ask the server to deliver any email queued on the server for a particular domain. This might be used by business dial-up customers who call in to their ISP every so often to collect email.

There are two variants of TURN in the current specifications, ETRN and ATRN, because the original form was insecure. With ETRN the server delivers the queued messages as if from a normal queue run; the only security concern is that the server must have some throttling to prevent clients from starting unlimited numbers of queue runners. With ATRN the existing connection is used to deliver the messages from the server to the client, which switch roles after the ATRN command. The client must be authenticated so that the server knows the client is permitted to receive the email it is asking for. ATRN is used on the "on-demand mail relay" port 366 instead of the usual SMTP port.

The basic implementation of ETRN (common to sendmail, Exim, and older Postfix) is for the server to fire off sendmail -qR, which scans the entire queue for messages with recipient addresses containing the domain given by the client. This is horribly inefficient if you have lots of messages on the queue, and the more clients you have using ETRN the more your queues get clogged with undeliverable messages.

The solution to this problem is to get messages for your ETRN domains off the queue; with Exim this is typically done by delivering them to a batch-SMTP file per domain, which can then be re-injected for delivery fairly efficiently when the client says ETRN. This kind of setup is a must for ATRN: whereas ETRN uses normal SMTP routing and delivery (which works if the clients have static IP addresses), ATRN does not, so there is generally no way to deliver the messages except by ATRN. ETRN is an optimisation to allow clients to tell the server not to wait for a retry timeout, whereas ATRN is purely on-demand so it is actually wrong to leave the messages on the retry queue.

With my log-structured queues we can use this idea but do it more efficiently. When a message is addressed to an ATRN domain, or cannot be delivered to an ETRN domain, its envelope is written to that domain's queue instead of appended to the main queue. One thing that makes this slightly more interesting is that the envelope may have to be split if it has recipients at multiple domains. This introduces the requirement for some kind of reference counting of spool files. The per-domain queue files are not routinely scanned, and when a client requests a delivery the server can simply and efficiently work through its queue.

Postfix leaves ETRN messages on its "deferred" queue, but optimises ETRN by keeping per-domain indexes of messages. This has the advantage of avoiding the need to split messages per domain, and means that ETRN domains are still retried even if the client doesn't ask. However it means that the deferred queue can get large and normal queue runs can get expensive. We should also periodically retry ETRN domains, but this won't happen unless they have messages on the main queue. To deal with that we should periodically probe these domains, which does not need any disk activity if the domain remains unreachable.