Postcopy: Add stats on page requests
[qemu.git] / qobject / json-lexer.c
1 /*
2 * JSON lexer
3 *
4 * Copyright IBM, Corp. 2009
5 *
6 * Authors:
7 * Anthony Liguori <aliguori@us.ibm.com>
8 *
9 * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
10 * See the COPYING.LIB file in the top-level directory.
11 *
12 */
13
14 #include "qemu/osdep.h"
15 #include "qemu-common.h"
16 #include "qapi/qmp/json-lexer.h"
17
18 #define MAX_TOKEN_SIZE (64ULL << 20)
19
20 /*
21 * \"([^\\\"]|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*\"
22 * '([^\\']|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*'
23 * 0|([1-9][0-9]*(.[0-9]+)?([eE]([-+])?[0-9]+))
24 * [{}\[\],:]
25 * [a-z]+
26 *
27 */
28
29 enum json_lexer_state {
30 IN_ERROR = 0, /* must really be 0, see json_lexer[] */
31 IN_DQ_UCODE3,
32 IN_DQ_UCODE2,
33 IN_DQ_UCODE1,
34 IN_DQ_UCODE0,
35 IN_DQ_STRING_ESCAPE,
36 IN_DQ_STRING,
37 IN_SQ_UCODE3,
38 IN_SQ_UCODE2,
39 IN_SQ_UCODE1,
40 IN_SQ_UCODE0,
41 IN_SQ_STRING_ESCAPE,
42 IN_SQ_STRING,
43 IN_ZERO,
44 IN_DIGITS,
45 IN_DIGIT,
46 IN_EXP_E,
47 IN_MANTISSA,
48 IN_MANTISSA_DIGITS,
49 IN_NONZERO_NUMBER,
50 IN_NEG_NONZERO_NUMBER,
51 IN_KEYWORD,
52 IN_ESCAPE,
53 IN_ESCAPE_L,
54 IN_ESCAPE_LL,
55 IN_ESCAPE_I,
56 IN_ESCAPE_I6,
57 IN_ESCAPE_I64,
58 IN_WHITESPACE,
59 IN_START,
60 };
61
62 QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START);
63
64 #define TERMINAL(state) [0 ... 0x7F] = (state)
65
66 /* Return whether TERMINAL is a terminal state and the transition to it
67 from OLD_STATE required lookahead. This happens whenever the table
68 below uses the TERMINAL macro. */
69 #define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \
70 (json_lexer[(old_state)][0] == (terminal))
71
72 static const uint8_t json_lexer[][256] = {
73 /* Relies on default initialization to IN_ERROR! */
74
75 /* double quote string */
76 [IN_DQ_UCODE3] = {
77 ['0' ... '9'] = IN_DQ_STRING,
78 ['a' ... 'f'] = IN_DQ_STRING,
79 ['A' ... 'F'] = IN_DQ_STRING,
80 },
81 [IN_DQ_UCODE2] = {
82 ['0' ... '9'] = IN_DQ_UCODE3,
83 ['a' ... 'f'] = IN_DQ_UCODE3,
84 ['A' ... 'F'] = IN_DQ_UCODE3,
85 },
86 [IN_DQ_UCODE1] = {
87 ['0' ... '9'] = IN_DQ_UCODE2,
88 ['a' ... 'f'] = IN_DQ_UCODE2,
89 ['A' ... 'F'] = IN_DQ_UCODE2,
90 },
91 [IN_DQ_UCODE0] = {
92 ['0' ... '9'] = IN_DQ_UCODE1,
93 ['a' ... 'f'] = IN_DQ_UCODE1,
94 ['A' ... 'F'] = IN_DQ_UCODE1,
95 },
96 [IN_DQ_STRING_ESCAPE] = {
97 ['b'] = IN_DQ_STRING,
98 ['f'] = IN_DQ_STRING,
99 ['n'] = IN_DQ_STRING,
100 ['r'] = IN_DQ_STRING,
101 ['t'] = IN_DQ_STRING,
102 ['/'] = IN_DQ_STRING,
103 ['\\'] = IN_DQ_STRING,
104 ['\''] = IN_DQ_STRING,
105 ['\"'] = IN_DQ_STRING,
106 ['u'] = IN_DQ_UCODE0,
107 },
108 [IN_DQ_STRING] = {
109 [1 ... 0xBF] = IN_DQ_STRING,
110 [0xC2 ... 0xF4] = IN_DQ_STRING,
111 ['\\'] = IN_DQ_STRING_ESCAPE,
112 ['"'] = JSON_STRING,
113 },
114
115 /* single quote string */
116 [IN_SQ_UCODE3] = {
117 ['0' ... '9'] = IN_SQ_STRING,
118 ['a' ... 'f'] = IN_SQ_STRING,
119 ['A' ... 'F'] = IN_SQ_STRING,
120 },
121 [IN_SQ_UCODE2] = {
122 ['0' ... '9'] = IN_SQ_UCODE3,
123 ['a' ... 'f'] = IN_SQ_UCODE3,
124 ['A' ... 'F'] = IN_SQ_UCODE3,
125 },
126 [IN_SQ_UCODE1] = {
127 ['0' ... '9'] = IN_SQ_UCODE2,
128 ['a' ... 'f'] = IN_SQ_UCODE2,
129 ['A' ... 'F'] = IN_SQ_UCODE2,
130 },
131 [IN_SQ_UCODE0] = {
132 ['0' ... '9'] = IN_SQ_UCODE1,
133 ['a' ... 'f'] = IN_SQ_UCODE1,
134 ['A' ... 'F'] = IN_SQ_UCODE1,
135 },
136 [IN_SQ_STRING_ESCAPE] = {
137 ['b'] = IN_SQ_STRING,
138 ['f'] = IN_SQ_STRING,
139 ['n'] = IN_SQ_STRING,
140 ['r'] = IN_SQ_STRING,
141 ['t'] = IN_SQ_STRING,
142 ['/'] = IN_SQ_STRING,
143 ['\\'] = IN_SQ_STRING,
144 ['\''] = IN_SQ_STRING,
145 ['\"'] = IN_SQ_STRING,
146 ['u'] = IN_SQ_UCODE0,
147 },
148 [IN_SQ_STRING] = {
149 [1 ... 0xBF] = IN_SQ_STRING,
150 [0xC2 ... 0xF4] = IN_SQ_STRING,
151 ['\\'] = IN_SQ_STRING_ESCAPE,
152 ['\''] = JSON_STRING,
153 },
154
155 /* Zero */
156 [IN_ZERO] = {
157 TERMINAL(JSON_INTEGER),
158 ['0' ... '9'] = IN_ERROR,
159 ['.'] = IN_MANTISSA,
160 },
161
162 /* Float */
163 [IN_DIGITS] = {
164 TERMINAL(JSON_FLOAT),
165 ['0' ... '9'] = IN_DIGITS,
166 },
167
168 [IN_DIGIT] = {
169 ['0' ... '9'] = IN_DIGITS,
170 },
171
172 [IN_EXP_E] = {
173 ['-'] = IN_DIGIT,
174 ['+'] = IN_DIGIT,
175 ['0' ... '9'] = IN_DIGITS,
176 },
177
178 [IN_MANTISSA_DIGITS] = {
179 TERMINAL(JSON_FLOAT),
180 ['0' ... '9'] = IN_MANTISSA_DIGITS,
181 ['e'] = IN_EXP_E,
182 ['E'] = IN_EXP_E,
183 },
184
185 [IN_MANTISSA] = {
186 ['0' ... '9'] = IN_MANTISSA_DIGITS,
187 },
188
189 /* Number */
190 [IN_NONZERO_NUMBER] = {
191 TERMINAL(JSON_INTEGER),
192 ['0' ... '9'] = IN_NONZERO_NUMBER,
193 ['e'] = IN_EXP_E,
194 ['E'] = IN_EXP_E,
195 ['.'] = IN_MANTISSA,
196 },
197
198 [IN_NEG_NONZERO_NUMBER] = {
199 ['0'] = IN_ZERO,
200 ['1' ... '9'] = IN_NONZERO_NUMBER,
201 },
202
203 /* keywords */
204 [IN_KEYWORD] = {
205 TERMINAL(JSON_KEYWORD),
206 ['a' ... 'z'] = IN_KEYWORD,
207 },
208
209 /* whitespace */
210 [IN_WHITESPACE] = {
211 TERMINAL(JSON_SKIP),
212 [' '] = IN_WHITESPACE,
213 ['\t'] = IN_WHITESPACE,
214 ['\r'] = IN_WHITESPACE,
215 ['\n'] = IN_WHITESPACE,
216 },
217
218 /* escape */
219 [IN_ESCAPE_LL] = {
220 ['d'] = JSON_ESCAPE,
221 },
222
223 [IN_ESCAPE_L] = {
224 ['d'] = JSON_ESCAPE,
225 ['l'] = IN_ESCAPE_LL,
226 },
227
228 [IN_ESCAPE_I64] = {
229 ['d'] = JSON_ESCAPE,
230 },
231
232 [IN_ESCAPE_I6] = {
233 ['4'] = IN_ESCAPE_I64,
234 },
235
236 [IN_ESCAPE_I] = {
237 ['6'] = IN_ESCAPE_I6,
238 },
239
240 [IN_ESCAPE] = {
241 ['d'] = JSON_ESCAPE,
242 ['i'] = JSON_ESCAPE,
243 ['p'] = JSON_ESCAPE,
244 ['s'] = JSON_ESCAPE,
245 ['f'] = JSON_ESCAPE,
246 ['l'] = IN_ESCAPE_L,
247 ['I'] = IN_ESCAPE_I,
248 },
249
250 /* top level rule */
251 [IN_START] = {
252 ['"'] = IN_DQ_STRING,
253 ['\''] = IN_SQ_STRING,
254 ['0'] = IN_ZERO,
255 ['1' ... '9'] = IN_NONZERO_NUMBER,
256 ['-'] = IN_NEG_NONZERO_NUMBER,
257 ['{'] = JSON_LCURLY,
258 ['}'] = JSON_RCURLY,
259 ['['] = JSON_LSQUARE,
260 [']'] = JSON_RSQUARE,
261 [','] = JSON_COMMA,
262 [':'] = JSON_COLON,
263 ['a' ... 'z'] = IN_KEYWORD,
264 ['%'] = IN_ESCAPE,
265 [' '] = IN_WHITESPACE,
266 ['\t'] = IN_WHITESPACE,
267 ['\r'] = IN_WHITESPACE,
268 ['\n'] = IN_WHITESPACE,
269 },
270 };
271
272 void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func)
273 {
274 lexer->emit = func;
275 lexer->state = IN_START;
276 lexer->token = g_string_sized_new(3);
277 lexer->x = lexer->y = 0;
278 }
279
280 static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
281 {
282 int char_consumed, new_state;
283
284 lexer->x++;
285 if (ch == '\n') {
286 lexer->x = 0;
287 lexer->y++;
288 }
289
290 do {
291 assert(lexer->state <= ARRAY_SIZE(json_lexer));
292 new_state = json_lexer[lexer->state][(uint8_t)ch];
293 char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state);
294 if (char_consumed) {
295 g_string_append_c(lexer->token, ch);
296 }
297
298 switch (new_state) {
299 case JSON_LCURLY:
300 case JSON_RCURLY:
301 case JSON_LSQUARE:
302 case JSON_RSQUARE:
303 case JSON_COLON:
304 case JSON_COMMA:
305 case JSON_ESCAPE:
306 case JSON_INTEGER:
307 case JSON_FLOAT:
308 case JSON_KEYWORD:
309 case JSON_STRING:
310 lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y);
311 /* fall through */
312 case JSON_SKIP:
313 g_string_truncate(lexer->token, 0);
314 new_state = IN_START;
315 break;
316 case IN_ERROR:
317 /* XXX: To avoid having previous bad input leaving the parser in an
318 * unresponsive state where we consume unpredictable amounts of
319 * subsequent "good" input, percolate this error state up to the
320 * tokenizer/parser by forcing a NULL object to be emitted, then
321 * reset state.
322 *
323 * Also note that this handling is required for reliable channel
324 * negotiation between QMP and the guest agent, since chr(0xFF)
325 * is placed at the beginning of certain events to ensure proper
326 * delivery when the channel is in an unknown state. chr(0xFF) is
327 * never a valid ASCII/UTF-8 sequence, so this should reliably
328 * induce an error/flush state.
329 */
330 lexer->emit(lexer, lexer->token, JSON_ERROR, lexer->x, lexer->y);
331 g_string_truncate(lexer->token, 0);
332 new_state = IN_START;
333 lexer->state = new_state;
334 return 0;
335 default:
336 break;
337 }
338 lexer->state = new_state;
339 } while (!char_consumed && !flush);
340
341 /* Do not let a single token grow to an arbitrarily large size,
342 * this is a security consideration.
343 */
344 if (lexer->token->len > MAX_TOKEN_SIZE) {
345 lexer->emit(lexer, lexer->token, lexer->state, lexer->x, lexer->y);
346 g_string_truncate(lexer->token, 0);
347 lexer->state = IN_START;
348 }
349
350 return 0;
351 }
352
353 int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size)
354 {
355 size_t i;
356
357 for (i = 0; i < size; i++) {
358 int err;
359
360 err = json_lexer_feed_char(lexer, buffer[i], false);
361 if (err < 0) {
362 return err;
363 }
364 }
365
366 return 0;
367 }
368
369 int json_lexer_flush(JSONLexer *lexer)
370 {
371 return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0, true);
372 }
373
374 void json_lexer_destroy(JSONLexer *lexer)
375 {
376 g_string_free(lexer->token, true);
377 }