Line data Source code
1 : /* SPDX-License-Identifier: BSD-3-Clause
2 : * Copyright (C) 2016 Intel Corporation.
3 : * All rights reserved.
4 : */
5 :
6 : #include "spdk/json.h"
7 :
8 : #include "spdk_internal/utf.h"
9 :
10 : #define SPDK_JSON_MAX_NESTING_DEPTH 64
11 :
12 : static int
13 140 : hex_value(uint8_t c)
14 : {
15 : #define V(x, y) [x] = y + 1
16 : static const int8_t val[256] = {
17 : V('0', 0), V('1', 1), V('2', 2), V('3', 3), V('4', 4),
18 : V('5', 5), V('6', 6), V('7', 7), V('8', 8), V('9', 9),
19 : V('A', 0xA), V('B', 0xB), V('C', 0xC), V('D', 0xD), V('E', 0xE), V('F', 0xF),
20 : V('a', 0xA), V('b', 0xB), V('c', 0xC), V('d', 0xD), V('e', 0xE), V('f', 0xF),
21 : };
22 : #undef V
23 :
24 140 : return val[c] - 1;
25 : }
26 :
27 : static int
28 45 : json_decode_string_escape_unicode(uint8_t **strp, uint8_t *buf_end, uint8_t *out)
29 : {
30 45 : uint8_t *str = *strp;
31 : int v0, v1, v2, v3;
32 : uint32_t val;
33 45 : uint32_t surrogate_high = 0;
34 : int rc;
35 54 : decode:
36 : /* \uXXXX */
37 54 : assert(buf_end > str);
38 :
39 54 : if (*str++ != '\\') { return SPDK_JSON_PARSE_INVALID; }
40 52 : if (buf_end == str) { return SPDK_JSON_PARSE_INCOMPLETE; }
41 :
42 51 : if (*str++ != 'u') { return SPDK_JSON_PARSE_INVALID; }
43 41 : if (buf_end == str) { return SPDK_JSON_PARSE_INCOMPLETE; }
44 :
45 39 : if ((v3 = hex_value(*str++)) < 0) { return SPDK_JSON_PARSE_INVALID; }
46 38 : if (buf_end == str) { return SPDK_JSON_PARSE_INCOMPLETE; }
47 :
48 36 : if ((v2 = hex_value(*str++)) < 0) { return SPDK_JSON_PARSE_INVALID; }
49 35 : if (buf_end == str) { return SPDK_JSON_PARSE_INCOMPLETE; }
50 :
51 34 : if ((v1 = hex_value(*str++)) < 0) { return SPDK_JSON_PARSE_INVALID; }
52 33 : if (buf_end == str) { return SPDK_JSON_PARSE_INCOMPLETE; }
53 :
54 31 : if ((v0 = hex_value(*str++)) < 0) { return SPDK_JSON_PARSE_INVALID; }
55 29 : if (buf_end == str) { return SPDK_JSON_PARSE_INCOMPLETE; }
56 :
57 28 : val = v0 | (v1 << 4) | (v2 << 8) | (v3 << 12);
58 :
59 28 : if (surrogate_high) {
60 : /* We already parsed the high surrogate, so this should be the low part. */
61 3 : if (!utf16_valid_surrogate_low(val)) {
62 1 : return SPDK_JSON_PARSE_INVALID;
63 : }
64 :
65 : /* Convert UTF-16 surrogate pair into codepoint and fall through to utf8_encode. */
66 2 : val = utf16_decode_surrogate_pair(surrogate_high, val);
67 25 : } else if (utf16_valid_surrogate_high(val)) {
68 9 : surrogate_high = val;
69 :
70 : /*
71 : * We parsed a \uXXXX sequence that decoded to the first half of a
72 : * UTF-16 surrogate pair, so it must be immediately followed by another
73 : * \uXXXX escape.
74 : *
75 : * Loop around to get the low half of the surrogate pair.
76 : */
77 9 : if (buf_end == str) { return SPDK_JSON_PARSE_INCOMPLETE; }
78 9 : goto decode;
79 16 : } else if (utf16_valid_surrogate_low(val)) {
80 : /*
81 : * We found the second half of surrogate pair without the first half;
82 : * this is an invalid encoding.
83 : */
84 4 : return SPDK_JSON_PARSE_INVALID;
85 : }
86 :
87 : /*
88 : * Convert Unicode escape (or surrogate pair) to UTF-8 in place.
89 : *
90 : * This is safe (will not write beyond the buffer) because the \uXXXX sequence is 6 bytes
91 : * (or 12 bytes for surrogate pairs), and the longest possible UTF-8 encoding of a
92 : * single codepoint is 4 bytes.
93 : */
94 14 : if (out) {
95 7 : rc = utf8_encode_unsafe(out, val);
96 : } else {
97 7 : rc = utf8_codepoint_len(val);
98 : }
99 14 : if (rc < 0) {
100 0 : return SPDK_JSON_PARSE_INVALID;
101 : }
102 :
103 14 : *strp = str; /* update input pointer */
104 14 : return rc; /* return number of bytes decoded */
105 : }
106 :
107 : static int
108 69 : json_decode_string_escape_twochar(uint8_t **strp, uint8_t *buf_end, uint8_t *out)
109 : {
110 : static const uint8_t escapes[256] = {
111 : ['b'] = '\b',
112 : ['f'] = '\f',
113 : ['n'] = '\n',
114 : ['r'] = '\r',
115 : ['t'] = '\t',
116 : ['/'] = '/',
117 : ['"'] = '"',
118 : ['\\'] = '\\',
119 : };
120 69 : uint8_t *str = *strp;
121 : uint8_t c;
122 :
123 69 : assert(buf_end > str);
124 69 : if (buf_end - str < 2) {
125 0 : return SPDK_JSON_PARSE_INCOMPLETE;
126 : }
127 :
128 69 : assert(str[0] == '\\');
129 :
130 69 : c = escapes[str[1]];
131 69 : if (c) {
132 24 : if (out) {
133 11 : *out = c;
134 : }
135 24 : *strp += 2; /* consumed two bytes */
136 24 : return 1; /* produced one byte */
137 : }
138 :
139 45 : return SPDK_JSON_PARSE_INVALID;
140 : }
141 :
142 : /*
143 : * Decode JSON string backslash escape.
144 : * \param strp pointer to pointer to first character of escape (the backslash).
145 : * *strp is also advanced to indicate how much input was consumed.
146 : *
147 : * \return Number of bytes appended to out
148 : */
149 : static int
150 69 : json_decode_string_escape(uint8_t **strp, uint8_t *buf_end, uint8_t *out)
151 : {
152 : int rc;
153 :
154 69 : rc = json_decode_string_escape_twochar(strp, buf_end, out);
155 69 : if (rc > 0) {
156 24 : return rc;
157 : }
158 :
159 45 : return json_decode_string_escape_unicode(strp, buf_end, out);
160 : }
161 :
162 : /*
163 : * Decode JSON string in place.
164 : *
165 : * \param str_start Pointer to the beginning of the string (the opening " character).
166 : *
167 : * \return Number of bytes in decoded string (beginning from start).
168 : */
169 : static int
170 869 : json_decode_string(uint8_t *str_start, uint8_t *buf_end, uint8_t **str_end, uint32_t flags)
171 : {
172 869 : uint8_t *str = str_start;
173 869 : uint8_t *out = str_start + 1; /* Decode string in place (skip the initial quote) */
174 : int rc;
175 :
176 869 : if (buf_end - str_start < 2) {
177 : /*
178 : * Shortest valid string (the empty string) is two bytes (""),
179 : * so this can't possibly be valid
180 : */
181 6 : *str_end = str;
182 6 : return SPDK_JSON_PARSE_INCOMPLETE;
183 : }
184 :
185 863 : if (*str++ != '"') {
186 0 : *str_end = str;
187 0 : return SPDK_JSON_PARSE_INVALID;
188 : }
189 :
190 4916 : while (str < buf_end) {
191 4884 : if (str[0] == '"') {
192 : /*
193 : * End of string.
194 : * Update str_end to point at next input byte and return output length.
195 : */
196 720 : *str_end = str + 1;
197 720 : return out - str_start - 1;
198 4164 : } else if (str[0] == '\\') {
199 69 : rc = json_decode_string_escape(&str, buf_end,
200 69 : flags & SPDK_JSON_PARSE_FLAG_DECODE_IN_PLACE ? out : NULL);
201 69 : assert(rc != 0);
202 69 : if (rc < 0) {
203 31 : *str_end = str;
204 31 : return rc;
205 : }
206 38 : out += rc;
207 4095 : } else if (str[0] <= 0x1f) {
208 : /* control characters must be escaped */
209 35 : *str_end = str;
210 35 : return SPDK_JSON_PARSE_INVALID;
211 : } else {
212 4060 : rc = utf8_valid(str, buf_end);
213 4060 : if (rc == 0) {
214 0 : *str_end = str;
215 0 : return SPDK_JSON_PARSE_INCOMPLETE;
216 4060 : } else if (rc < 0) {
217 45 : *str_end = str;
218 45 : return SPDK_JSON_PARSE_INVALID;
219 : }
220 :
221 4015 : if (out && out != str && (flags & SPDK_JSON_PARSE_FLAG_DECODE_IN_PLACE)) {
222 6 : memmove(out, str, rc);
223 : }
224 4015 : out += rc;
225 4015 : str += rc;
226 : }
227 : }
228 :
229 : /* If execution gets here, we ran out of buffer. */
230 32 : *str_end = str;
231 32 : return SPDK_JSON_PARSE_INCOMPLETE;
232 : }
233 :
234 : static int
235 296 : json_valid_number(uint8_t *start, uint8_t *buf_end)
236 : {
237 296 : uint8_t *p = start;
238 : uint8_t c;
239 :
240 296 : if (p >= buf_end) { return -1; }
241 :
242 296 : c = *p++;
243 296 : if (c >= '1' && c <= '9') { goto num_int_digits; }
244 88 : if (c == '0') { goto num_frac_or_exp; }
245 20 : if (c == '-') { goto num_int_first_digit; }
246 0 : p--;
247 0 : goto done_invalid;
248 :
249 20 : num_int_first_digit:
250 20 : if (spdk_likely(p != buf_end)) {
251 19 : c = *p++;
252 19 : if (c == '0') { goto num_frac_or_exp; }
253 11 : if (c >= '1' && c <= '9') { goto num_int_digits; }
254 1 : p--;
255 : }
256 2 : goto done_invalid;
257 :
258 218 : num_int_digits:
259 310 : if (spdk_likely(p != buf_end)) {
260 302 : c = *p++;
261 302 : if (c >= '0' && c <= '9') { goto num_int_digits; }
262 210 : if (c == '.') { goto num_frac_first_digit; }
263 166 : if (c == 'e' || c == 'E') { goto num_exp_sign; }
264 154 : p--;
265 : }
266 162 : goto done_valid;
267 :
268 76 : num_frac_or_exp:
269 76 : if (spdk_likely(p != buf_end)) {
270 66 : c = *p++;
271 66 : if (c == '.') { goto num_frac_first_digit; }
272 66 : if (c == 'e' || c == 'E') { goto num_exp_sign; }
273 56 : p--;
274 : }
275 66 : goto done_valid;
276 :
277 44 : num_frac_first_digit:
278 44 : if (spdk_likely(p != buf_end)) {
279 42 : c = *p++;
280 42 : if (c >= '0' && c <= '9') { goto num_frac_digits; }
281 2 : p--;
282 : }
283 4 : goto done_invalid;
284 :
285 164 : num_frac_digits:
286 164 : if (spdk_likely(p != buf_end)) {
287 154 : c = *p++;
288 154 : if (c >= '0' && c <= '9') { goto num_frac_digits; }
289 30 : if (c == 'e' || c == 'E') { goto num_exp_sign; }
290 14 : p--;
291 : }
292 24 : goto done_valid;
293 :
294 38 : num_exp_sign:
295 38 : if (spdk_likely(p != buf_end)) {
296 38 : c = *p++;
297 38 : if (c >= '0' && c <= '9') { goto num_exp_digits; }
298 24 : if (c == '-' || c == '+') { goto num_exp_first_digit; }
299 1 : p--;
300 : }
301 1 : goto done_invalid;
302 :
303 23 : num_exp_first_digit:
304 23 : if (spdk_likely(p != buf_end)) {
305 21 : c = *p++;
306 21 : if (c >= '0' && c <= '9') { goto num_exp_digits; }
307 2 : p--;
308 : }
309 4 : goto done_invalid;
310 :
311 33 : num_exp_digits:
312 63 : if (spdk_likely(p != buf_end)) {
313 33 : c = *p++;
314 33 : if (c >= '0' && c <= '9') { goto num_exp_digits; }
315 3 : p--;
316 : }
317 33 : goto done_valid;
318 :
319 285 : done_valid:
320 : /* Valid end state */
321 285 : return p - start;
322 :
323 11 : done_invalid:
324 : /* Invalid end state */
325 11 : if (p == buf_end) {
326 : /* Hit the end of the buffer - the stream is incomplete. */
327 5 : return SPDK_JSON_PARSE_INCOMPLETE;
328 : }
329 :
330 : /* Found an invalid character in an invalid end state */
331 6 : return SPDK_JSON_PARSE_INVALID;
332 : }
333 :
334 : static int
335 20 : json_valid_comment(const uint8_t *start, const uint8_t *buf_end)
336 : {
337 20 : const uint8_t *p = start;
338 : bool multiline;
339 :
340 20 : assert(buf_end > p);
341 20 : if (buf_end - p < 2) {
342 1 : return SPDK_JSON_PARSE_INCOMPLETE;
343 : }
344 :
345 19 : if (p[0] != '/') {
346 0 : return SPDK_JSON_PARSE_INVALID;
347 : }
348 19 : if (p[1] == '*') {
349 9 : multiline = true;
350 10 : } else if (p[1] == '/') {
351 9 : multiline = false;
352 : } else {
353 1 : return SPDK_JSON_PARSE_INVALID;
354 : }
355 18 : p += 2;
356 :
357 18 : if (multiline) {
358 63 : while (p != buf_end - 1) {
359 63 : if (p[0] == '*' && p[1] == '/') {
360 : /* Include the terminating star and slash in the comment */
361 9 : return p - start + 2;
362 : }
363 54 : p++;
364 : }
365 : } else {
366 52 : while (p != buf_end) {
367 50 : if (*p == '\r' || *p == '\n') {
368 : /* Do not include the line terminator in the comment */
369 7 : return p - start;
370 : }
371 43 : p++;
372 : }
373 : }
374 :
375 2 : return SPDK_JSON_PARSE_INCOMPLETE;
376 : }
377 :
378 : struct json_literal {
379 : enum spdk_json_val_type type;
380 : uint32_t len;
381 : uint8_t str[8];
382 : };
383 :
384 : /*
385 : * JSON only defines 3 possible literals; they can be uniquely identified by bits
386 : * 3 and 4 of the first character:
387 : * 'f' = 0b11[00]110
388 : * 'n' = 0b11[01]110
389 : * 't' = 0b11[10]100
390 : * These two bits can be used as an index into the g_json_literals array.
391 : */
392 : static const struct json_literal g_json_literals[] = {
393 : {SPDK_JSON_VAL_FALSE, 5, "false"},
394 : {SPDK_JSON_VAL_NULL, 4, "null"},
395 : {SPDK_JSON_VAL_TRUE, 4, "true"},
396 : {}
397 : };
398 :
399 : static int
400 75 : match_literal(const uint8_t *start, const uint8_t *end, const uint8_t *literal, size_t len)
401 : {
402 75 : assert(end >= start);
403 75 : if ((size_t)(end - start) < len) {
404 6 : return SPDK_JSON_PARSE_INCOMPLETE;
405 : }
406 :
407 69 : if (memcmp(start, literal, len) != 0) {
408 3 : return SPDK_JSON_PARSE_INVALID;
409 : }
410 :
411 66 : return len;
412 : }
413 :
414 : ssize_t
415 555 : spdk_json_parse(void *json, size_t size, struct spdk_json_val *values, size_t num_values,
416 : void **end, uint32_t flags)
417 : {
418 555 : uint8_t *json_end = json + size;
419 555 : enum spdk_json_val_type containers[SPDK_JSON_MAX_NESTING_DEPTH];
420 555 : size_t con_value[SPDK_JSON_MAX_NESTING_DEPTH];
421 555 : enum spdk_json_val_type con_type = SPDK_JSON_VAL_INVALID;
422 555 : bool trailing_comma = false;
423 555 : size_t depth = 0; /* index into containers */
424 555 : size_t cur_value = 0; /* index into values */
425 : size_t con_start_value;
426 555 : uint8_t *data = json;
427 555 : uint8_t *new_data;
428 555 : int rc = 0;
429 : const struct json_literal *lit;
430 : enum {
431 : STATE_VALUE, /* initial state */
432 : STATE_VALUE_SEPARATOR, /* value separator (comma) */
433 : STATE_NAME, /* "name": value */
434 : STATE_NAME_SEPARATOR, /* colon */
435 : STATE_END, /* parsed the complete value, so only whitespace is valid */
436 555 : } state = STATE_VALUE;
437 :
438 : #define ADD_VALUE(t, val_start_ptr, val_end_ptr) \
439 : if (values && cur_value < num_values) { \
440 : values[cur_value].type = t; \
441 : values[cur_value].start = val_start_ptr; \
442 : values[cur_value].len = val_end_ptr - val_start_ptr; \
443 : } \
444 : cur_value++
445 :
446 3857 : while (data < json_end) {
447 3819 : uint8_t c = *data;
448 :
449 3819 : switch (c) {
450 1073 : case ' ':
451 : case '\t':
452 : case '\r':
453 : case '\n':
454 : /* Whitespace is allowed between any tokens. */
455 1073 : data++;
456 1073 : break;
457 :
458 75 : case 't':
459 : case 'f':
460 : case 'n':
461 : /* true, false, or null */
462 75 : if (state != STATE_VALUE) { goto done_invalid; }
463 75 : lit = &g_json_literals[(c >> 3) & 3]; /* See comment above g_json_literals[] */
464 75 : assert(lit->str[0] == c);
465 75 : rc = match_literal(data, json_end, lit->str, lit->len);
466 75 : if (rc < 0) { goto done_rc; }
467 66 : ADD_VALUE(lit->type, data, data + rc);
468 66 : data += rc;
469 66 : state = depth ? STATE_VALUE_SEPARATOR : STATE_END;
470 66 : trailing_comma = false;
471 66 : break;
472 :
473 869 : case '"':
474 869 : if (state != STATE_VALUE && state != STATE_NAME) { goto done_invalid; }
475 869 : rc = json_decode_string(data, json_end, &new_data, flags);
476 869 : if (rc < 0) {
477 149 : data = new_data;
478 149 : goto done_rc;
479 : }
480 : /*
481 : * Start is data + 1 to skip initial quote.
482 : * Length is data + rc - 1 to skip both quotes.
483 : */
484 720 : ADD_VALUE(state == STATE_VALUE ? SPDK_JSON_VAL_STRING : SPDK_JSON_VAL_NAME,
485 : data + 1, data + rc - 1);
486 720 : data = new_data;
487 720 : if (state == STATE_NAME) {
488 399 : state = STATE_NAME_SEPARATOR;
489 : } else {
490 321 : state = depth ? STATE_VALUE_SEPARATOR : STATE_END;
491 : }
492 720 : trailing_comma = false;
493 720 : break;
494 :
495 298 : case '-':
496 : case '0':
497 : case '1':
498 : case '2':
499 : case '3':
500 : case '4':
501 : case '5':
502 : case '6':
503 : case '7':
504 : case '8':
505 : case '9':
506 298 : if (state != STATE_VALUE) { goto done_invalid; }
507 296 : rc = json_valid_number(data, json_end);
508 296 : if (rc < 0) { goto done_rc; }
509 285 : ADD_VALUE(SPDK_JSON_VAL_NUMBER, data, data + rc);
510 285 : data += rc;
511 285 : state = depth ? STATE_VALUE_SEPARATOR : STATE_END;
512 285 : trailing_comma = false;
513 285 : break;
514 :
515 461 : case '{':
516 : case '[':
517 461 : if (state != STATE_VALUE) { goto done_invalid; }
518 461 : if (depth == SPDK_JSON_MAX_NESTING_DEPTH) {
519 1 : rc = SPDK_JSON_PARSE_MAX_DEPTH_EXCEEDED;
520 1 : goto done_rc;
521 : }
522 460 : if (c == '{') {
523 193 : con_type = SPDK_JSON_VAL_OBJECT_BEGIN;
524 193 : state = STATE_NAME;
525 : } else {
526 267 : con_type = SPDK_JSON_VAL_ARRAY_BEGIN;
527 267 : state = STATE_VALUE;
528 : }
529 460 : con_value[depth] = cur_value;
530 460 : containers[depth++] = con_type;
531 460 : ADD_VALUE(con_type, data, data + 1);
532 460 : data++;
533 460 : trailing_comma = false;
534 460 : break;
535 :
536 246 : case '}':
537 : case ']':
538 246 : if (trailing_comma) { goto done_invalid; }
539 244 : if (depth == 0) { goto done_invalid; }
540 242 : con_type = containers[--depth];
541 242 : con_start_value = con_value[depth];
542 242 : if (values && con_start_value < num_values) {
543 114 : values[con_start_value].len = cur_value - con_start_value - 1;
544 : }
545 242 : if (c == '}') {
546 125 : if (state != STATE_NAME && state != STATE_VALUE_SEPARATOR) {
547 2 : goto done_invalid;
548 : }
549 123 : if (con_type != SPDK_JSON_VAL_OBJECT_BEGIN) {
550 2 : goto done_invalid;
551 : }
552 121 : ADD_VALUE(SPDK_JSON_VAL_OBJECT_END, data, data + 1);
553 : } else {
554 117 : if (state != STATE_VALUE && state != STATE_VALUE_SEPARATOR) {
555 1 : goto done_invalid;
556 : }
557 116 : if (con_type != SPDK_JSON_VAL_ARRAY_BEGIN) {
558 1 : goto done_invalid;
559 : }
560 115 : ADD_VALUE(SPDK_JSON_VAL_ARRAY_END, data, data + 1);
561 : }
562 236 : con_type = depth == 0 ? SPDK_JSON_VAL_INVALID : containers[depth - 1];
563 236 : data++;
564 236 : state = depth ? STATE_VALUE_SEPARATOR : STATE_END;
565 236 : trailing_comma = false;
566 236 : break;
567 :
568 373 : case ',':
569 373 : if (state != STATE_VALUE_SEPARATOR) { goto done_invalid; }
570 367 : data++;
571 367 : assert(con_type == SPDK_JSON_VAL_ARRAY_BEGIN ||
572 : con_type == SPDK_JSON_VAL_OBJECT_BEGIN);
573 367 : state = con_type == SPDK_JSON_VAL_ARRAY_BEGIN ? STATE_VALUE : STATE_NAME;
574 367 : trailing_comma = true;
575 367 : break;
576 :
577 390 : case ':':
578 390 : if (state != STATE_NAME_SEPARATOR) { goto done_invalid; }
579 390 : data++;
580 390 : state = STATE_VALUE;
581 390 : break;
582 :
583 23 : case '/':
584 23 : if (!(flags & SPDK_JSON_PARSE_FLAG_ALLOW_COMMENTS)) {
585 3 : goto done_invalid;
586 : }
587 20 : rc = json_valid_comment(data, json_end);
588 20 : if (rc < 0) { goto done_rc; }
589 : /* Skip over comment */
590 16 : data += rc;
591 16 : break;
592 :
593 11 : default:
594 11 : goto done_invalid;
595 : }
596 :
597 3613 : if (state == STATE_END) {
598 311 : break;
599 : }
600 : }
601 :
602 349 : if (state == STATE_END) {
603 : /* Skip trailing whitespace */
604 331 : while (data < json_end) {
605 68 : uint8_t c = *data;
606 :
607 68 : if (c == ' ' || c == '\t' || c == '\r' || c == '\n') {
608 20 : data++;
609 : } else {
610 : break;
611 : }
612 : }
613 :
614 : /*
615 : * These asserts are just for sanity checking - they are guaranteed by the allowed
616 : * state transitions.
617 : */
618 311 : assert(depth == 0);
619 311 : assert(trailing_comma == false);
620 311 : assert(data <= json_end);
621 311 : if (end) {
622 304 : *end = data;
623 : }
624 311 : return cur_value;
625 : }
626 :
627 : /* Invalid end state - ran out of data */
628 38 : rc = SPDK_JSON_PARSE_INCOMPLETE;
629 :
630 244 : done_rc:
631 244 : assert(rc < 0);
632 244 : if (end) {
633 244 : *end = data;
634 : }
635 244 : return rc;
636 :
637 32 : done_invalid:
638 32 : rc = SPDK_JSON_PARSE_INVALID;
639 32 : goto done_rc;
640 : }
|
