Cyrus IMAP Server: Sieve Bytecode

Motivation

The motivation behind moving to Sieve Bytecode is severalfold:

• Parsing a script at each execution is expensive computationally

• Lex/Yacc are costly in terms of memory usage and executable size, whereas a bytecode parser is much lighter weight.

• Using bytecode can simplify the code for the execution phase, which is far more frequently occurring than the upload/compile phase.

• Rewriting a significant part of the sieve execution framework forces a decent amount of refactoring on what has traditionally been a problematic part of the Cyrus code base. There is still work to do in this area.

Overall Bytecode Format

In the final bytecode, each opcode/parameter is aligned on a 4-byte boundary. Strings are NUL-terminated (and padded to a 4-byte boundary as needed).

Ideally, we'd have all integers in network byte order, so as to make the scripts portable, but version 1 does not have this feature.

At the beginning of the file, there is a magic header to identify it as a bytecode file, and a 4 byte version number. Immediately following the version number are the opcodes that relate to the script.

Generation

A Sieve Bytecode file is generated in three "passes":

• Generate a parse tree using lex/yacc from the sieve script. (addr.y, addr-lex.l, sieve.y, sieve-lex.l).

• Serialize the parse tree into an intermediate form, where strings are held separate from the rest of the representation. (bc_generate.c)

• Serialize the intermediate form into the final bytecode. (bc_emit.c)

The intermediate form is an array of bytecode_t unions, with strings located elsewhere in memory. The entry point is bc_generate: sieve_generate_bytecode() / bc_action_generate().

bc_action_generate traverses the commandlist_t tree and emits opcodes in sequence.

Simple actions (STOP, DISCARD, KEEP, MARK, UNMARK) have no arguments, and processing proceeds directly.

More complicated options have a sequence of arguments that are emitted following the initial opcode.

For example, single argument commands such as REJECT, FILEINTO, REDIRECT are followed by a bytecode_t for a string's length, and then a bytecode_t which contains a pointer to a string.

Commands such as ADDFLAG, SETFLAG, REMOVEFLAG, which take a stringlist, format the stringlist as (using bc_stringlist_generate):

{Number of Strings}{String 1 Length}{String 1 Ptr}{String 2 Length}....

So their resulting final output would appear as:

{Opcode}{...stringlist from above...}

Even more complicated action opcodes (vacation, notify) etc, may take a sequence of integer values (flags), stringlists, or individual strings. These are more specifically documented in the code.

This leaves us with the IF keyword (and tests). In the pass 1 form, IF appears as the following bytecode_t structures:

{IF opcode}
{Beginning of the then block}
{End of the then block / beginning of the else block}
{End of the else block / -1 for no else block}
{....test opcodes....}
{....'then' action opcodes....}
{....'else' action opcodes.... [optional]}

Test opcodes are generated by the bc_test_generate function, which is very similar to bc_action_generate (tests without arguments are just opcodes, tests with arguments have them serialized into place directly following the original opcode). Test lists are represented as {number of tests}{address of the end of the list}{test 1}{test 2}.

In the third pass, strings are serialized into place, and if statement jumps are resolved to actual addresses within the file This is done in bc_emit: sieve_emit_bytecode / bc_action_emit.

This results in a totally serialized representation, using byte offsets within the file instead of indexes into the array of bytecode_t's. In addition to the manipulations that are necessary to do this, there are several other changes in format.

Two new opcodes exist: NULL and JUMP (which performs an unconditional jump).

Stringlists and testslists now include a precomputed byte length of the entire list, so it can be skipped over as needed.

So as to be executable without a stack, the IF statements are designed as follows:

{IF opcode}
{....test block....}
{JUMP (location of false condition) }
{....then block....}
{(if there is an else) JUMP (end of else block)}
{(if there is an else) .... else block ....}

The idea being that if the test is true, the instruction pointer should move to the then block, otherwise the else block will be hit automatically (due to the unconditional jump).

Evaluation

The evaluation routines are in bc_eval.c, the basic idea is that we can simply mmap the bytecode, run straight through it, and complete the processing without maintaining a stack.

The processing is done by overlaying a bytecode_input_t array over the mmap. This allows addressing elements within the file to be simple. There is an instruction pointer which is incremented as each action is performed, or as actions/tests are skipped.

Of special note in bc_eval.c is the unwrap_string function which will pull a string out of the bytecode, and return the instruction pointer at the end of the string.

Other things to consider

The Bytecode can be extended to contain other extensions. This could require regeneration of older scripts. In many cases this can be avoided by putting the new commands at the end of the proper enum in bytecode.h