| 1 |
.. _imap-developer-thoughts-bytecode: |
| 2 |
|
| 3 |
.. Note: This document was converted from the original by Nic Bernstein |
| 4 |
(Onlight). Any formatting mistakes are my fault and not the |
| 5 |
original author's. Converted via the pandoc tool from HTML. |
| 6 |
|
| 7 |
Cyrus IMAP Server: Sieve Bytecode |
| 8 |
================================= |
| 9 |
|
| 10 |
Motivation |
| 11 |
---------- |
| 12 |
|
| 13 |
The motivation behind moving to Sieve Bytecode is severalfold: |
| 14 |
|
| 15 |
- Parsing a script at each execution is expensive computationally |
| 16 |
- Lex/Yacc are costly in terms of memory usage and executable size, |
| 17 |
whereas a bytecode parser is much lighter weight. |
| 18 |
- Using bytecode can simplify the code for the execution phase, which |
| 19 |
is far more frequently occurring than the upload/compile phase. |
| 20 |
- Rewriting a significant part of the sieve execution framework forces |
| 21 |
a decent amount of refactoring on what has traditionally been a |
| 22 |
problematic part of the Cyrus code base. There is still work to do in |
| 23 |
this area. |
| 24 |
|
| 25 |
Overall Bytecode Format |
| 26 |
----------------------- |
| 27 |
|
| 28 |
In the final bytecode, each opcode/parameter is aligned on a 4-byte |
| 29 |
boundary. Strings are NUL-terminated (and padded to a 4-byte boundary as |
| 30 |
needed). |
| 31 |
|
| 32 |
Ideally, we'd have all integers in network byte order, so as to make the |
| 33 |
scripts portable, but version 1 does not have this feature. |
| 34 |
|
| 35 |
At the beginning of the file, there is a magic header to identify it as |
| 36 |
a bytecode file, and a 4 byte version number. Immediately following the |
| 37 |
version number are the opcodes that relate to the script. |
| 38 |
|
| 39 |
Generation |
| 40 |
---------- |
| 41 |
|
| 42 |
A Sieve Bytecode file is generated in three "passes": |
| 43 |
|
| 44 |
- Generate a parse tree using lex/yacc from the sieve script. (addr.y, |
| 45 |
addr-lex.l, sieve.y, sieve-lex.l). |
| 46 |
- Serialize the parse tree into an intermediate form, where strings are |
| 47 |
held separate from the rest of the representation. (bc\_generate.c) |
| 48 |
- Serialize the intermediate form into the final bytecode. (bc\_emit.c) |
| 49 |
|
| 50 |
The intermediate form is an array of bytecode\_t unions, with strings |
| 51 |
located elsewhere in memory. The entry point is bc\_generate: |
| 52 |
sieve\_generate\_bytecode() / bc\_action\_generate(). |
| 53 |
|
| 54 |
bc\_action\_generate traverses the commandlist\_t tree and emits opcodes |
| 55 |
in sequence. |
| 56 |
|
| 57 |
Simple actions (STOP, DISCARD, KEEP, MARK, UNMARK) have no arguments, |
| 58 |
and processing proceeds directly. |
| 59 |
|
| 60 |
More complicated options have a sequence of arguments that are emitted |
| 61 |
following the initial opcode. |
| 62 |
|
| 63 |
For example, single argument commands such as REJECT, FILEINTO, REDIRECT |
| 64 |
are followed by a bytecode\_t for a string's length, and then a |
| 65 |
bytecode\_t which contains a pointer to a string. |
| 66 |
|
| 67 |
Commands such as ADDFLAG, SETFLAG, REMOVEFLAG, which take a stringlist, |
| 68 |
format the stringlist as (using bc\_stringlist\_generate): |
| 69 |
|
| 70 |
:: |
| 71 |
|
| 72 |
{Number of Strings}{String 1 Length}{String 1 Ptr}{String 2 Length}.... |
| 73 |
|
| 74 |
So their resulting final output would appear as: |
| 75 |
|
| 76 |
:: |
| 77 |
|
| 78 |
{Opcode}{...stringlist from above...} |
| 79 |
|
| 80 |
Even more complicated action opcodes (vacation, notify) etc, may take a |
| 81 |
sequence of integer values (flags), stringlists, or individual strings. |
| 82 |
These are more specifically documented in the code. |
| 83 |
|
| 84 |
This leaves us with the IF keyword (and tests). In the pass 1 form, IF |
| 85 |
appears as the following bytecode\_t structures: |
| 86 |
|
| 87 |
:: |
| 88 |
|
| 89 |
{IF opcode} |
| 90 |
{Beginning of the then block} |
| 91 |
{End of the then block / beginning of the else block} |
| 92 |
{End of the else block / -1 for no else block} |
| 93 |
{....test opcodes....} |
| 94 |
{....'then' action opcodes....} |
| 95 |
{....'else' action opcodes.... [optional]} |
| 96 |
|
| 97 |
Test opcodes are generated by the bc\_test\_generate function, which is |
| 98 |
very similar to bc\_action\_generate (tests without arguments are just |
| 99 |
opcodes, tests with arguments have them serialized into place directly |
| 100 |
following the original opcode). Test lists are represented as {number of |
| 101 |
tests}{address of the end of the list}{test 1}{test 2}. |
| 102 |
|
| 103 |
In the third pass, strings are serialized into place, and if statement |
| 104 |
jumps are resolved to actual addresses within the file This is done in |
| 105 |
bc\_emit: sieve\_emit\_bytecode / bc\_action\_emit. |
| 106 |
|
| 107 |
This results in a totally serialized representation, using byte offsets |
| 108 |
within the file instead of indexes into the array of bytecode\_t's. In |
| 109 |
addition to the manipulations that are necessary to do this, there are |
| 110 |
several other changes in format. |
| 111 |
|
| 112 |
Two new opcodes exist: NULL and JUMP (which performs an unconditional |
| 113 |
jump). |
| 114 |
|
| 115 |
Stringlists and testslists now include a precomputed byte length of the |
| 116 |
entire list, so it can be skipped over as needed. |
| 117 |
|
| 118 |
So as to be executable without a stack, the IF statements are designed |
| 119 |
as follows: |
| 120 |
|
| 121 |
:: |
| 122 |
|
| 123 |
{IF opcode} |
| 124 |
{....test block....} |
| 125 |
{JUMP (location of false condition) } |
| 126 |
{....then block....} |
| 127 |
{(if there is an else) JUMP (end of else block)} |
| 128 |
{(if there is an else) .... else block ....} |
| 129 |
|
| 130 |
The idea being that if the test is true, the instruction pointer should |
| 131 |
move to the then block, otherwise the else block will be hit |
| 132 |
automatically (due to the unconditional jump). |
| 133 |
|
| 134 |
Evaluation |
| 135 |
---------- |
| 136 |
|
| 137 |
The evaluation routines are in bc\_eval.c, the basic idea is that we can |
| 138 |
simply mmap the bytecode, run straight through it, and complete the |
| 139 |
processing without maintaining a stack. |
| 140 |
|
| 141 |
The processing is done by overlaying a bytecode\_input\_t array over the |
| 142 |
mmap. This allows addressing elements within the file to be simple. |
| 143 |
There is an instruction pointer which is incremented as each action is |
| 144 |
performed, or as actions/tests are skipped. |
| 145 |
|
| 146 |
Of special note in bc\_eval.c is the unwrap\_string function which will |
| 147 |
pull a string out of the bytecode, and return the instruction pointer at |
| 148 |
the end of the string. |
| 149 |
|
| 150 |
Other things to consider |
| 151 |
------------------------ |
| 152 |
|
| 153 |
The Bytecode can be extended to contain other extensions. This could |
| 154 |
require regeneration of older scripts. In many cases this can be avoided |
| 155 |
by putting the new commands at the end of the proper enum in bytecode.h |