contrib/wpa/src/utils/json.c

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