Debian Codegraph @

doc/html/_sources/imap/developer/thoughts/bytecode.rst.txt

raw
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