1 /* 2 * JavaScript Object Notation (JSON) parser (RFC7159) 3 * Copyright (c) 2017, Qualcomm Atheros, Inc. 4 * 5 * This software may be distributed under the terms of the BSD license. 6 * See README for more details. 7 */ 8 9 #include "includes.h" 10 11 #include "common.h" 12 #include "base64.h" 13 #include "json.h" 14 15 #define JSON_MAX_DEPTH 10 16 #define JSON_MAX_TOKENS 500 17 18 19 void json_escape_string(char *txt, size_t maxlen, const char *data, size_t len) 20 { 21 char *end = txt + maxlen; 22 size_t i; 23 24 for (i = 0; i < len; i++) { 25 if (txt + 4 >= end) 26 break; 27 28 switch (data[i]) { 29 case '\"': 30 *txt++ = '\\'; 31 *txt++ = '\"'; 32 break; 33 case '\\': 34 *txt++ = '\\'; 35 *txt++ = '\\'; 36 break; 37 case '\n': 38 *txt++ = '\\'; 39 *txt++ = 'n'; 40 break; 41 case '\r': 42 *txt++ = '\\'; 43 *txt++ = 'r'; 44 break; 45 case '\t': 46 *txt++ = '\\'; 47 *txt++ = 't'; 48 break; 49 default: 50 if (data[i] >= 32 && data[i] <= 126) { 51 *txt++ = data[i]; 52 } else { 53 txt += os_snprintf(txt, end - txt, "\\u%04x", 54 data[i]); 55 } 56 break; 57 } 58 } 59 60 *txt = '\0'; 61 } 62 63 64 static char * json_parse_string(const char **json_pos, const char *end) 65 { 66 const char *pos = *json_pos; 67 char *str, *spos, *s_end; 68 size_t max_len, buf_len; 69 u8 bin[2]; 70 71 pos++; /* skip starting quote */ 72 73 max_len = end - pos + 1; 74 buf_len = max_len > 10 ? 10 : max_len; 75 str = os_malloc(buf_len); 76 if (!str) 77 return NULL; 78 spos = str; 79 s_end = str + buf_len; 80 81 for (; pos < end; pos++) { 82 if (buf_len < max_len && s_end - spos < 3) { 83 char *tmp; 84 int idx; 85 86 idx = spos - str; 87 buf_len *= 2; 88 if (buf_len > max_len) 89 buf_len = max_len; 90 tmp = os_realloc(str, buf_len); 91 if (!tmp) 92 goto fail; 93 str = tmp; 94 spos = str + idx; 95 s_end = str + buf_len; 96 } 97 98 switch (*pos) { 99 case '\"': /* end string */ 100 *spos = '\0'; 101 /* caller will move to the next position */ 102 *json_pos = pos; 103 return str; 104 case '\\': 105 pos++; 106 switch (*pos) { 107 case '"': 108 case '\\': 109 case '/': 110 *spos++ = *pos; 111 break; 112 case 'n': 113 *spos++ = '\n'; 114 break; 115 case 'r': 116 *spos++ = '\r'; 117 break; 118 case 't': 119 *spos++ = '\t'; 120 break; 121 case 'u': 122 if (end - pos < 5 || 123 hexstr2bin(pos + 1, bin, 2) < 0 || 124 bin[1] == 0x00) { 125 wpa_printf(MSG_DEBUG, 126 "JSON: Invalid \\u escape"); 127 goto fail; 128 } 129 if (bin[0] == 0x00) { 130 *spos++ = bin[1]; 131 } else { 132 *spos++ = bin[0]; 133 *spos++ = bin[1]; 134 } 135 pos += 4; 136 break; 137 default: 138 wpa_printf(MSG_DEBUG, 139 "JSON: Unknown escape '%c'", *pos); 140 goto fail; 141 } 142 break; 143 default: 144 *spos++ = *pos; 145 break; 146 } 147 } 148 149 fail: 150 os_free(str); 151 return NULL; 152 } 153 154 155 static int json_parse_number(const char **json_pos, const char *end, 156 int *ret_val) 157 { 158 const char *pos = *json_pos; 159 size_t len; 160 char *str; 161 162 for (; pos < end; pos++) { 163 if (*pos != '-' && (*pos < '0' || *pos > '9')) { 164 pos--; 165 break; 166 } 167 } 168 if (pos < *json_pos) 169 return -1; 170 len = pos - *json_pos + 1; 171 str = os_malloc(len + 1); 172 if (!str) 173 return -1; 174 os_memcpy(str, *json_pos, len); 175 str[len] = '\0'; 176 177 *ret_val = atoi(str); 178 os_free(str); 179 *json_pos = pos; 180 return 0; 181 } 182 183 184 static int json_check_tree_state(struct json_token *token) 185 { 186 if (!token) 187 return 0; 188 if (json_check_tree_state(token->child) < 0 || 189 json_check_tree_state(token->sibling) < 0) 190 return -1; 191 if (token->state != JSON_COMPLETED) { 192 wpa_printf(MSG_DEBUG, 193 "JSON: Unexpected token state %d (name=%s type=%d)", 194 token->state, token->name ? token->name : "N/A", 195 token->type); 196 return -1; 197 } 198 return 0; 199 } 200 201 202 static struct json_token * json_alloc_token(unsigned int *tokens) 203 { 204 (*tokens)++; 205 if (*tokens > JSON_MAX_TOKENS) { 206 wpa_printf(MSG_DEBUG, "JSON: Maximum token limit exceeded"); 207 return NULL; 208 } 209 return os_zalloc(sizeof(struct json_token)); 210 } 211 212 213 struct json_token * json_parse(const char *data, size_t data_len) 214 { 215 struct json_token *root = NULL, *curr_token = NULL, *token = NULL; 216 const char *pos, *end; 217 char *str; 218 int num; 219 unsigned int depth = 0; 220 unsigned int tokens = 0; 221 222 pos = data; 223 end = data + data_len; 224 225 for (; pos < end; pos++) { 226 switch (*pos) { 227 case '[': /* start array */ 228 case '{': /* start object */ 229 if (!curr_token) { 230 token = json_alloc_token(&tokens); 231 if (!token) 232 goto fail; 233 if (!root) 234 root = token; 235 } else if (curr_token->state == JSON_WAITING_VALUE) { 236 token = curr_token; 237 } else if (curr_token->parent && 238 curr_token->parent->type == JSON_ARRAY && 239 curr_token->parent->state == JSON_STARTED && 240 curr_token->state == JSON_EMPTY) { 241 token = curr_token; 242 } else { 243 wpa_printf(MSG_DEBUG, 244 "JSON: Invalid state for start array/object"); 245 goto fail; 246 } 247 depth++; 248 if (depth > JSON_MAX_DEPTH) { 249 wpa_printf(MSG_DEBUG, 250 "JSON: Max depth exceeded"); 251 goto fail; 252 } 253 token->type = *pos == '[' ? JSON_ARRAY : JSON_OBJECT; 254 token->state = JSON_STARTED; 255 token->child = json_alloc_token(&tokens); 256 if (!token->child) 257 goto fail; 258 curr_token = token->child; 259 curr_token->parent = token; 260 curr_token->state = JSON_EMPTY; 261 break; 262 case ']': /* end array */ 263 case '}': /* end object */ 264 if (!curr_token || !curr_token->parent || 265 curr_token->parent->state != JSON_STARTED) { 266 wpa_printf(MSG_DEBUG, 267 "JSON: Invalid state for end array/object"); 268 goto fail; 269 } 270 depth--; 271 curr_token = curr_token->parent; 272 if ((*pos == ']' && 273 curr_token->type != JSON_ARRAY) || 274 (*pos == '}' && 275 curr_token->type != JSON_OBJECT)) { 276 wpa_printf(MSG_DEBUG, 277 "JSON: Array/Object mismatch"); 278 goto fail; 279 } 280 if (curr_token->child->state == JSON_EMPTY && 281 !curr_token->child->child && 282 !curr_token->child->sibling) { 283 /* Remove pending child token since the 284 * array/object was empty. */ 285 json_free(curr_token->child); 286 curr_token->child = NULL; 287 } 288 curr_token->state = JSON_COMPLETED; 289 break; 290 case '\"': /* string */ 291 str = json_parse_string(&pos, end); 292 if (!str) 293 goto fail; 294 if (!curr_token) { 295 token = json_alloc_token(&tokens); 296 if (!token) 297 goto fail; 298 token->type = JSON_STRING; 299 token->string = str; 300 token->state = JSON_COMPLETED; 301 } else if (curr_token->parent && 302 curr_token->parent->type == JSON_ARRAY && 303 curr_token->parent->state == JSON_STARTED && 304 curr_token->state == JSON_EMPTY) { 305 curr_token->string = str; 306 curr_token->state = JSON_COMPLETED; 307 curr_token->type = JSON_STRING; 308 wpa_printf(MSG_MSGDUMP, 309 "JSON: String value: '%s'", 310 curr_token->string); 311 } else if (curr_token->state == JSON_EMPTY) { 312 curr_token->type = JSON_VALUE; 313 curr_token->name = str; 314 curr_token->state = JSON_STARTED; 315 } else if (curr_token->state == JSON_WAITING_VALUE) { 316 curr_token->string = str; 317 curr_token->state = JSON_COMPLETED; 318 curr_token->type = JSON_STRING; 319 wpa_printf(MSG_MSGDUMP, 320 "JSON: String value: '%s' = '%s'", 321 curr_token->name, 322 curr_token->string); 323 } else { 324 wpa_printf(MSG_DEBUG, 325 "JSON: Invalid state for a string"); 326 os_free(str); 327 goto fail; 328 } 329 break; 330 case ' ': 331 case '\t': 332 case '\r': 333 case '\n': 334 /* ignore whitespace */ 335 break; 336 case ':': /* name/value separator */ 337 if (!curr_token || curr_token->state != JSON_STARTED) 338 goto fail; 339 curr_token->state = JSON_WAITING_VALUE; 340 break; 341 case ',': /* member separator */ 342 if (!curr_token) 343 goto fail; 344 curr_token->sibling = json_alloc_token(&tokens); 345 if (!curr_token->sibling) 346 goto fail; 347 curr_token->sibling->parent = curr_token->parent; 348 curr_token = curr_token->sibling; 349 curr_token->state = JSON_EMPTY; 350 break; 351 case 't': /* true */ 352 case 'f': /* false */ 353 case 'n': /* null */ 354 if (!((end - pos >= 4 && 355 os_strncmp(pos, "true", 4) == 0) || 356 (end - pos >= 5 && 357 os_strncmp(pos, "false", 5) == 0) || 358 (end - pos >= 4 && 359 os_strncmp(pos, "null", 4) == 0))) { 360 wpa_printf(MSG_DEBUG, 361 "JSON: Invalid literal name"); 362 goto fail; 363 } 364 if (!curr_token) { 365 token = json_alloc_token(&tokens); 366 if (!token) 367 goto fail; 368 curr_token = token; 369 } else if (curr_token->state == JSON_WAITING_VALUE) { 370 wpa_printf(MSG_MSGDUMP, 371 "JSON: Literal name: '%s' = %c", 372 curr_token->name, *pos); 373 } else if (curr_token->parent && 374 curr_token->parent->type == JSON_ARRAY && 375 curr_token->parent->state == JSON_STARTED && 376 curr_token->state == JSON_EMPTY) { 377 wpa_printf(MSG_MSGDUMP, 378 "JSON: Literal name: %c", *pos); 379 } else { 380 wpa_printf(MSG_DEBUG, 381 "JSON: Invalid state for a literal name"); 382 goto fail; 383 } 384 switch (*pos) { 385 case 't': 386 curr_token->type = JSON_BOOLEAN; 387 curr_token->number = 1; 388 pos += 3; 389 break; 390 case 'f': 391 curr_token->type = JSON_BOOLEAN; 392 curr_token->number = 0; 393 pos += 4; 394 break; 395 case 'n': 396 curr_token->type = JSON_NULL; 397 pos += 3; 398 break; 399 } 400 curr_token->state = JSON_COMPLETED; 401 break; 402 case '-': 403 case '0': 404 case '1': 405 case '2': 406 case '3': 407 case '4': 408 case '5': 409 case '6': 410 case '7': 411 case '8': 412 case '9': 413 /* number */ 414 if (json_parse_number(&pos, end, &num) < 0) 415 goto fail; 416 if (!curr_token) { 417 token = json_alloc_token(&tokens); 418 if (!token) 419 goto fail; 420 token->type = JSON_NUMBER; 421 token->number = num; 422 token->state = JSON_COMPLETED; 423 } else if (curr_token->state == JSON_WAITING_VALUE) { 424 curr_token->number = num; 425 curr_token->state = JSON_COMPLETED; 426 curr_token->type = JSON_NUMBER; 427 wpa_printf(MSG_MSGDUMP, 428 "JSON: Number value: '%s' = '%d'", 429 curr_token->name, 430 curr_token->number); 431 } else if (curr_token->parent && 432 curr_token->parent->type == JSON_ARRAY && 433 curr_token->parent->state == JSON_STARTED && 434 curr_token->state == JSON_EMPTY) { 435 curr_token->number = num; 436 curr_token->state = JSON_COMPLETED; 437 curr_token->type = JSON_NUMBER; 438 wpa_printf(MSG_MSGDUMP, 439 "JSON: Number value: %d", 440 curr_token->number); 441 } else { 442 wpa_printf(MSG_DEBUG, 443 "JSON: Invalid state for a number"); 444 goto fail; 445 } 446 break; 447 default: 448 wpa_printf(MSG_DEBUG, 449 "JSON: Unexpected JSON character: %c", *pos); 450 goto fail; 451 } 452 453 if (!root) 454 root = token; 455 if (!curr_token) 456 curr_token = token; 457 } 458 459 if (json_check_tree_state(root) < 0) { 460 wpa_printf(MSG_DEBUG, "JSON: Incomplete token in the tree"); 461 goto fail; 462 } 463 464 return root; 465 fail: 466 wpa_printf(MSG_DEBUG, "JSON: Parsing failed"); 467 json_free(root); 468 return NULL; 469 } 470 471 472 void json_free(struct json_token *json) 473 { 474 if (!json) 475 return; 476 json_free(json->child); 477 json_free(json->sibling); 478 os_free(json->name); 479 os_free(json->string); 480 os_free(json); 481 } 482 483 484 struct json_token * json_get_member(struct json_token *json, const char *name) 485 { 486 struct json_token *token, *ret = NULL; 487 488 if (!json || json->type != JSON_OBJECT) 489 return NULL; 490 /* Return last matching entry */ 491 for (token = json->child; token; token = token->sibling) { 492 if (token->name && os_strcmp(token->name, name) == 0) 493 ret = token; 494 } 495 return ret; 496 } 497 498 499 struct wpabuf * json_get_member_base64url(struct json_token *json, 500 const char *name) 501 { 502 struct json_token *token; 503 unsigned char *buf; 504 size_t buflen; 505 struct wpabuf *ret; 506 507 token = json_get_member(json, name); 508 if (!token || token->type != JSON_STRING) 509 return NULL; 510 buf = base64_url_decode((const unsigned char *) token->string, 511 os_strlen(token->string), &buflen); 512 if (!buf) 513 return NULL; 514 ret = wpabuf_alloc_ext_data(buf, buflen); 515 if (!ret) 516 os_free(buf); 517 518 return ret; 519 } 520 521 522 static const char * json_type_str(enum json_type type) 523 { 524 switch (type) { 525 case JSON_VALUE: 526 return "VALUE"; 527 case JSON_OBJECT: 528 return "OBJECT"; 529 case JSON_ARRAY: 530 return "ARRAY"; 531 case JSON_STRING: 532 return "STRING"; 533 case JSON_NUMBER: 534 return "NUMBER"; 535 case JSON_BOOLEAN: 536 return "BOOLEAN"; 537 case JSON_NULL: 538 return "NULL"; 539 } 540 return "??"; 541 } 542 543 544 static void json_print_token(struct json_token *token, int depth, 545 char *buf, size_t buflen) 546 { 547 size_t len; 548 int ret; 549 550 if (!token) 551 return; 552 len = os_strlen(buf); 553 ret = os_snprintf(buf + len, buflen - len, "[%d:%s:%s]", 554 depth, json_type_str(token->type), 555 token->name ? token->name : ""); 556 if (os_snprintf_error(buflen - len, ret)) { 557 buf[len] = '\0'; 558 return; 559 } 560 json_print_token(token->child, depth + 1, buf, buflen); 561 json_print_token(token->sibling, depth, buf, buflen); 562 } 563 564 565 void json_print_tree(struct json_token *root, char *buf, size_t buflen) 566 { 567 buf[0] = '\0'; 568 json_print_token(root, 1, buf, buflen); 569 } 570