1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
.. _imap-developer-thoughts-bytecode:
.. Note: This document was converted from the original by Nic Bernstein
(Onlight). Any formatting mistakes are my fault and not the
original author's. Converted via the pandoc tool from HTML.
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
|
