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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
|
<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
<meta charset="utf-8" /><meta name="generator" content="Docutils 0.19: https://docutils.sourceforge.io/" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Cyrus IMAP Server: Sieve Bytecode — Cyrus IMAP 3.12.1 documentation</title>
<link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/graphviz.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/cyrus.css" type="text/css" />
<script data-url_root="../../../" id="documentation_options" src="../../../_static/documentation_options.js"></script>
<script src="../../../_static/jquery.js"></script>
<script src="../../../_static/underscore.js"></script>
<script src="../../../_static/_sphinx_javascript_frameworks_compat.js"></script>
<script src="../../../_static/doctools.js"></script>
<script src="../../../_static/sphinx_highlight.js"></script>
<script src="../../../_static/js/theme.js"></script>
<link rel="index" title="Index" href="../../../genindex.html" />
<link rel="search" title="Search" href="../../../search.html" />
<link rel="next" title="Cyrus CalDAV Scheduling Flowchart" href="caldav_scheduling_flowchart.html" />
<link rel="prev" title="Developer Thoughts & Notes" href="../thoughts.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="../../../index.html" class="icon icon-home">
Cyrus IMAP
</a>
<div class="version">
3.12.1
</div>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="../../../search.html" method="get">
<input type="text" name="q" placeholder="Search docs" aria-label="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<p class="caption" role="heading"><span class="caption-text">Cyrus IMAP</span></p>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../../../download.html">Download</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../../quickstart.html">Quickstart Guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../../overview.html">Overview</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../../setup.html">Setup</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../../operations.html">Operations</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../../../developers.html">Developers</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="../../../contribute.html">We need your help</a></li>
<li class="toctree-l2"><a class="reference internal" href="../documentation.html">Contribute docs</a></li>
<li class="toctree-l2"><a class="reference internal" href="../../developer.html">Contribute code and tests</a></li>
<li class="toctree-l2"><a class="reference internal" href="../cyrusworks.html">Cyrus.Works</a></li>
<li class="toctree-l2 current"><a class="reference internal" href="../../../developers.html#cyrus-internals">Cyrus Internals</a><ul class="current">
<li class="toctree-l3"><a class="reference internal" href="../API.html">Cyrus APIs</a></li>
<li class="toctree-l3 current"><a class="reference internal" href="../thoughts.html">Thoughts & Notes</a><ul class="current">
<li class="toctree-l4 current"><a class="current reference internal" href="#">Cyrus IMAP Server: Sieve Bytecode</a></li>
<li class="toctree-l4"><a class="reference internal" href="caldav_scheduling_flowchart.html">Cyrus CalDAV Scheduling Flowchart</a></li>
<li class="toctree-l4"><a class="reference internal" href="notes.html">Cyrus IMAP Server: Notes</a></li>
<li class="toctree-l4"><a class="reference internal" href="prot-events.html">Cyrus IMAP Server: Prot Events</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="../guidance.html">Guidance for Developers</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="../../../developers.html#unit-tests">Unit Tests</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../../../support.html">Support/Community</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">Cyrus SASL</span></p>
<ul>
<li class="toctree-l1"><a class="reference external" href="http://www.cyrusimap.org/sasl">Cyrus SASL</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" >
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="../../../index.html">Cyrus IMAP</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="Page navigation">
<ul class="wy-breadcrumbs">
<li><a href="../../../index.html" class="icon icon-home" aria-label="Home"></a></li>
<li class="breadcrumb-item"><a href="../../../developers.html">Developers</a></li>
<li class="breadcrumb-item"><a href="../thoughts.html">Developer Thoughts & Notes</a></li>
<li class="breadcrumb-item active">Cyrus IMAP Server: Sieve Bytecode</li>
<li class="wy-breadcrumbs-aside">
<a href="https://github.com/cyrusimap/cyrus-imapd/blob/master/docsrc/imap/developer/thoughts/bytecode.rst" class="fa fa-github"> Edit on GitHub</a>
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<span class="target" id="imap-developer-thoughts-bytecode"></span><section id="cyrus-imap-server-sieve-bytecode">
<h1>Cyrus IMAP Server: Sieve Bytecode<a class="headerlink" href="#cyrus-imap-server-sieve-bytecode" title="Permalink to this heading"></a></h1>
<section id="motivation">
<h2>Motivation<a class="headerlink" href="#motivation" title="Permalink to this heading"></a></h2>
<p>The motivation behind moving to Sieve Bytecode is severalfold:</p>
<ul class="simple">
<li><p>Parsing a script at each execution is expensive computationally</p></li>
<li><p>Lex/Yacc are costly in terms of memory usage and executable size,
whereas a bytecode parser is much lighter weight.</p></li>
<li><p>Using bytecode can simplify the code for the execution phase, which
is far more frequently occurring than the upload/compile phase.</p></li>
<li><p>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.</p></li>
</ul>
</section>
<section id="overall-bytecode-format">
<h2>Overall Bytecode Format<a class="headerlink" href="#overall-bytecode-format" title="Permalink to this heading"></a></h2>
<p>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).</p>
<p>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.</p>
<p>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.</p>
</section>
<section id="generation">
<h2>Generation<a class="headerlink" href="#generation" title="Permalink to this heading"></a></h2>
<p>A Sieve Bytecode file is generated in three "passes":</p>
<ul class="simple">
<li><p>Generate a parse tree using lex/yacc from the sieve script. (addr.y,
addr-lex.l, sieve.y, sieve-lex.l).</p></li>
<li><p>Serialize the parse tree into an intermediate form, where strings are
held separate from the rest of the representation. (bc_generate.c)</p></li>
<li><p>Serialize the intermediate form into the final bytecode. (bc_emit.c)</p></li>
</ul>
<p>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().</p>
<p>bc_action_generate traverses the commandlist_t tree and emits opcodes
in sequence.</p>
<p>Simple actions (STOP, DISCARD, KEEP, MARK, UNMARK) have no arguments,
and processing proceeds directly.</p>
<p>More complicated options have a sequence of arguments that are emitted
following the initial opcode.</p>
<p>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.</p>
<p>Commands such as ADDFLAG, SETFLAG, REMOVEFLAG, which take a stringlist,
format the stringlist as (using bc_stringlist_generate):</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">{</span><span class="n">Number</span> <span class="n">of</span> <span class="n">Strings</span><span class="p">}{</span><span class="n">String</span> <span class="mi">1</span> <span class="n">Length</span><span class="p">}{</span><span class="n">String</span> <span class="mi">1</span> <span class="n">Ptr</span><span class="p">}{</span><span class="n">String</span> <span class="mi">2</span> <span class="n">Length</span><span class="p">}</span><span class="o">....</span>
</pre></div>
</div>
<p>So their resulting final output would appear as:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">{</span><span class="n">Opcode</span><span class="p">}{</span><span class="o">...</span><span class="n">stringlist</span> <span class="kn">from</span> <span class="nn">above...</span><span class="p">}</span>
</pre></div>
</div>
<p>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.</p>
<p>This leaves us with the IF keyword (and tests). In the pass 1 form, IF
appears as the following bytecode_t structures:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">{</span><span class="n">IF</span> <span class="n">opcode</span><span class="p">}</span>
<span class="p">{</span><span class="n">Beginning</span> <span class="n">of</span> <span class="n">the</span> <span class="n">then</span> <span class="n">block</span><span class="p">}</span>
<span class="p">{</span><span class="n">End</span> <span class="n">of</span> <span class="n">the</span> <span class="n">then</span> <span class="n">block</span> <span class="o">/</span> <span class="n">beginning</span> <span class="n">of</span> <span class="n">the</span> <span class="k">else</span> <span class="n">block</span><span class="p">}</span>
<span class="p">{</span><span class="n">End</span> <span class="n">of</span> <span class="n">the</span> <span class="k">else</span> <span class="n">block</span> <span class="o">/</span> <span class="o">-</span><span class="mi">1</span> <span class="k">for</span> <span class="n">no</span> <span class="k">else</span> <span class="n">block</span><span class="p">}</span>
<span class="p">{</span><span class="o">....</span><span class="n">test</span> <span class="n">opcodes</span><span class="o">....</span><span class="p">}</span>
<span class="p">{</span><span class="o">....</span><span class="s1">'then'</span> <span class="n">action</span> <span class="n">opcodes</span><span class="o">....</span><span class="p">}</span>
<span class="p">{</span><span class="o">....</span><span class="s1">'else'</span> <span class="n">action</span> <span class="n">opcodes</span><span class="o">....</span> <span class="p">[</span><span class="n">optional</span><span class="p">]}</span>
</pre></div>
</div>
<p>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}.</p>
<p>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.</p>
<p>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.</p>
<p>Two new opcodes exist: NULL and JUMP (which performs an unconditional
jump).</p>
<p>Stringlists and testslists now include a precomputed byte length of the
entire list, so it can be skipped over as needed.</p>
<p>So as to be executable without a stack, the IF statements are designed
as follows:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">{</span><span class="n">IF</span> <span class="n">opcode</span><span class="p">}</span>
<span class="p">{</span><span class="o">....</span><span class="n">test</span> <span class="n">block</span><span class="o">....</span><span class="p">}</span>
<span class="p">{</span><span class="n">JUMP</span> <span class="p">(</span><span class="n">location</span> <span class="n">of</span> <span class="n">false</span> <span class="n">condition</span><span class="p">)</span> <span class="p">}</span>
<span class="p">{</span><span class="o">....</span><span class="n">then</span> <span class="n">block</span><span class="o">....</span><span class="p">}</span>
<span class="p">{(</span><span class="k">if</span> <span class="n">there</span> <span class="ow">is</span> <span class="n">an</span> <span class="k">else</span><span class="p">)</span> <span class="n">JUMP</span> <span class="p">(</span><span class="n">end</span> <span class="n">of</span> <span class="k">else</span> <span class="n">block</span><span class="p">)}</span>
<span class="p">{(</span><span class="k">if</span> <span class="n">there</span> <span class="ow">is</span> <span class="n">an</span> <span class="k">else</span><span class="p">)</span> <span class="o">....</span> <span class="k">else</span> <span class="n">block</span> <span class="o">....</span><span class="p">}</span>
</pre></div>
</div>
<p>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).</p>
</section>
<section id="evaluation">
<h2>Evaluation<a class="headerlink" href="#evaluation" title="Permalink to this heading"></a></h2>
<p>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.</p>
<p>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.</p>
<p>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.</p>
</section>
<section id="other-things-to-consider">
<h2>Other things to consider<a class="headerlink" href="#other-things-to-consider" title="Permalink to this heading"></a></h2>
<p>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</p>
</section>
</section>
</div>
</div>
<footer><div class="rst-footer-buttons" role="navigation" aria-label="Footer">
<a href="../thoughts.html" class="btn btn-neutral float-left" title="Developer Thoughts & Notes" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a>
<a href="caldav_scheduling_flowchart.html" class="btn btn-neutral float-right" title="Cyrus CalDAV Scheduling Flowchart" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right" aria-hidden="true"></span></a>
</div>
<hr/>
<div role="contentinfo">
<p>© Copyright 1993–2025, The Cyrus Team.</p>
</div>
Built with <a href="https://www.sphinx-doc.org/">Sphinx</a> using a
<a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a>
provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script>
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>
|
