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                         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 }