1/* Copyright JS Foundation and other contributors, http://js.foundation 2 * 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16#include "js-parser-internal.h" 17 18#if ENABLED (JERRY_PARSER) 19 20/** \addtogroup mem Memory allocation 21 * @{ 22 * 23 * \addtogroup mem_parser Parser memory manager 24 * @{ 25 */ 26 27/**********************************************************************/ 28/* Memory allocation */ 29/**********************************************************************/ 30 31/** 32 * Allocate memory. 33 * 34 * @return allocated memory. 35 */ 36void * 37parser_malloc (parser_context_t *context_p, /**< context */ 38 size_t size) /**< size of the memory block */ 39{ 40 void *result; 41 42 JERRY_ASSERT (size > 0); 43 result = jmem_heap_alloc_block_null_on_error (size); 44 45 if (result == NULL) 46 { 47 parser_raise_error (context_p, PARSER_ERR_OUT_OF_MEMORY); 48 } 49 return result; 50} /* parser_malloc */ 51 52/** 53 * Free memory allocated by parser_malloc. 54 */ 55inline void JERRY_ATTR_ALWAYS_INLINE 56parser_free (void *ptr, /**< pointer to free */ 57 size_t size) /**< size of the memory block */ 58{ 59 jmem_heap_free_block (ptr, size); 60} /* parser_free */ 61 62/** 63 * Allocate local memory for short term use. 64 * 65 * @return allocated memory. 66 */ 67void * 68parser_malloc_local (parser_context_t *context_p, /**< context */ 69 size_t size) /**< size of the memory */ 70{ 71 void *result; 72 73 JERRY_ASSERT (size > 0); 74 result = jmem_heap_alloc_block (size); 75 if (result == 0) 76 { 77 parser_raise_error (context_p, PARSER_ERR_OUT_OF_MEMORY); 78 } 79 return result; 80} /* parser_malloc_local */ 81 82/** 83 * Free memory allocated by parser_malloc_local. 84 */ 85void 86parser_free_local (void *ptr, /**< pointer to free */ 87 size_t size) /**< size of the memory */ 88{ 89 jmem_heap_free_block (ptr, size); 90} /* parser_free_local */ 91 92/** 93 * Free the dynamically allocated buffer stored in the context 94 */ 95inline void JERRY_ATTR_ALWAYS_INLINE 96parser_free_allocated_buffer (parser_context_t *context_p) /**< context */ 97{ 98 if (context_p->u.allocated_buffer_p != NULL) 99 { 100 parser_free_local (context_p->u.allocated_buffer_p, 101 context_p->allocated_buffer_size); 102 context_p->u.allocated_buffer_p = NULL; 103 } 104} /* parser_free_allocated_buffer */ 105 106/**********************************************************************/ 107/* Parser data management functions */ 108/**********************************************************************/ 109 110/** 111 * Initialize parse data. 112 */ 113static void 114parser_data_init (parser_mem_data_t *data_p, /**< memory manager */ 115 uint32_t page_size) /**< size of each page */ 116{ 117 data_p->first_p = NULL; 118 data_p->last_p = NULL; 119 data_p->last_position = page_size; 120} /* parser_data_init */ 121 122/** 123 * Free parse data. 124 */ 125static void 126parser_data_free (parser_mem_data_t *data_p, /**< memory manager */ 127 uint32_t page_size) /**< size of each page */ 128{ 129 parser_mem_page_t *page_p = data_p->first_p; 130 131 while (page_p != NULL) 132 { 133 parser_mem_page_t *next_p = page_p->next_p; 134 135 parser_free (page_p, page_size); 136 page_p = next_p; 137 } 138} /* parser_data_free */ 139 140/**********************************************************************/ 141/* Parser byte stream management functions */ 142/**********************************************************************/ 143 144/** 145 * Initialize byte stream. 146 */ 147void 148parser_cbc_stream_init (parser_mem_data_t *data_p) /**< memory manager */ 149{ 150 parser_data_init (data_p, PARSER_CBC_STREAM_PAGE_SIZE); 151} /* parser_cbc_stream_init */ 152 153/** 154 * Free byte stream. 155 */ 156void 157parser_cbc_stream_free (parser_mem_data_t *data_p) /**< memory manager */ 158{ 159 parser_data_free (data_p, 160 sizeof (parser_mem_page_t *) + PARSER_CBC_STREAM_PAGE_SIZE); 161} /* parser_cbc_stream_free */ 162 163/** 164 * Appends a byte at the end of the byte stream. 165 */ 166void 167parser_cbc_stream_alloc_page (parser_context_t *context_p, /**< context */ 168 parser_mem_data_t *data_p) /**< memory manager */ 169{ 170 size_t size = sizeof (parser_mem_page_t *) + PARSER_CBC_STREAM_PAGE_SIZE; 171 parser_mem_page_t *page_p = (parser_mem_page_t *) parser_malloc (context_p, size); 172 173 page_p->next_p = NULL; 174 data_p->last_position = 0; 175 176 if (data_p->last_p != NULL) 177 { 178 data_p->last_p->next_p = page_p; 179 } 180 else 181 { 182 data_p->first_p = page_p; 183 } 184 data_p->last_p = page_p; 185} /* parser_cbc_stream_alloc_page */ 186 187/**********************************************************************/ 188/* Parser list management functions */ 189/**********************************************************************/ 190 191/** 192 * Initialize parser list. 193 */ 194void 195parser_list_init (parser_list_t *list_p, /**< parser list */ 196 uint32_t item_size, /**< size for each page */ 197 uint32_t item_count) /**< number of items on each page */ 198{ 199 /* Align to pointer size. */ 200 item_size = (uint32_t) (((item_size) + sizeof (void *) - 1) & ~(sizeof (void *) - 1)); 201 parser_data_init (&list_p->data, item_size * item_count); 202 list_p->page_size = item_size * item_count; 203 list_p->item_size = item_size; 204 list_p->item_count = item_count; 205} /* parser_list_init */ 206 207/** 208 * Free parser list. 209 */ 210void 211parser_list_free (parser_list_t *list_p) /**< parser list */ 212{ 213 parser_data_free (&list_p->data, 214 (uint32_t) (sizeof (parser_mem_page_t *) + list_p->page_size)); 215} /* parser_list_free */ 216 217/** 218 * Reset parser list. 219 */ 220void 221parser_list_reset (parser_list_t *list_p) /**< parser list */ 222{ 223 parser_data_init (&list_p->data, list_p->page_size); 224} /* parser_list_reset */ 225 226/** 227 * Allocate space for the next item. 228 * 229 * @return pointer to the appended item. 230 */ 231void * 232parser_list_append (parser_context_t *context_p, /**< context */ 233 parser_list_t *list_p) /**< parser list */ 234{ 235 parser_mem_page_t *page_p = list_p->data.last_p; 236 void *result; 237 238 if (list_p->data.last_position + list_p->item_size > list_p->page_size) 239 { 240 size_t size = sizeof (parser_mem_page_t *) + list_p->page_size; 241 242 page_p = (parser_mem_page_t *) parser_malloc (context_p, size); 243 244 page_p->next_p = NULL; 245 list_p->data.last_position = 0; 246 247 if (list_p->data.last_p != NULL) 248 { 249 list_p->data.last_p->next_p = page_p; 250 } 251 else 252 { 253 list_p->data.first_p = page_p; 254 } 255 list_p->data.last_p = page_p; 256 } 257 258 result = page_p->bytes + list_p->data.last_position; 259 list_p->data.last_position += list_p->item_size; 260 return result; 261} /* parser_list_append */ 262 263/** 264 * Return the nth item of the list. 265 * 266 * @return pointer to the item. 267 */ 268void * 269parser_list_get (parser_list_t *list_p, /**< parser list */ 270 size_t index) /**< item index */ 271{ 272 size_t item_count = list_p->item_count; 273 parser_mem_page_t *page_p = list_p->data.first_p; 274 275 while (index >= item_count) 276 { 277 JERRY_ASSERT (page_p != NULL); 278 page_p = page_p->next_p; 279 index -= item_count; 280 } 281 282 JERRY_ASSERT (page_p != NULL); 283 JERRY_ASSERT (page_p != list_p->data.last_p 284 || (index * list_p->item_size < list_p->data.last_position)); 285 return page_p->bytes + (index * list_p->item_size); 286} /* parser_list_get */ 287 288/** 289 * Initialize a parser list iterator. 290 */ 291void 292parser_list_iterator_init (parser_list_t *list_p, /**< parser list */ 293 parser_list_iterator_t *iterator_p) /**< iterator */ 294{ 295 iterator_p->list_p = list_p; 296 iterator_p->current_p = list_p->data.first_p; 297 iterator_p->current_position = 0; 298} /* parser_list_iterator_init */ 299 300/** 301 * Next iterator step. 302 * 303 * @return the address of the current item, or NULL at the end. 304 */ 305void * 306parser_list_iterator_next (parser_list_iterator_t *iterator_p) /**< iterator */ 307{ 308 void *result; 309 310 if (iterator_p->current_p == NULL) 311 { 312 return NULL; 313 } 314 315 result = iterator_p->current_p->bytes + iterator_p->current_position; 316 iterator_p->current_position += iterator_p->list_p->item_size; 317 318 if (iterator_p->current_p->next_p == NULL) 319 { 320 if (iterator_p->current_position >= iterator_p->list_p->data.last_position) 321 { 322 iterator_p->current_p = NULL; 323 iterator_p->current_position = 0; 324 } 325 } 326 else if (iterator_p->current_position >= iterator_p->list_p->page_size) 327 { 328 iterator_p->current_p = iterator_p->current_p->next_p; 329 iterator_p->current_position = 0; 330 } 331 return result; 332} /* parser_list_iterator_next */ 333 334/**********************************************************************/ 335/* Parser stack management functions */ 336/**********************************************************************/ 337 338/* Stack is a reversed storage. */ 339 340/** 341 * Initialize parser stack. 342 */ 343void 344parser_stack_init (parser_context_t *context_p) /**< context */ 345{ 346 parser_data_init (&context_p->stack, PARSER_STACK_PAGE_SIZE); 347 context_p->free_page_p = NULL; 348} /* parser_stack_init */ 349 350/** 351 * Free parser stack. 352 */ 353void 354parser_stack_free (parser_context_t *context_p) /**< context */ 355{ 356 parser_data_free (&context_p->stack, 357 sizeof (parser_mem_page_t *) + PARSER_STACK_PAGE_SIZE); 358 359 if (context_p->free_page_p != NULL) 360 { 361 parser_free (context_p->free_page_p, 362 sizeof (parser_mem_page_t *) + PARSER_STACK_PAGE_SIZE); 363 } 364} /* parser_stack_free */ 365 366/** 367 * Pushes an uint8_t value onto the stack. 368 */ 369void 370parser_stack_push_uint8 (parser_context_t *context_p, /**< context */ 371 uint8_t uint8_value) /**< value pushed onto the stack */ 372{ 373 parser_mem_page_t *page_p = context_p->stack.first_p; 374 375 /* This assert might trigger false positive valgrind errors, when 376 * parser_stack_push() pushes not fully initialized structures. 377 * More precisely when the last byte of the structure is uninitialized. */ 378 JERRY_ASSERT (page_p == NULL 379 || context_p->stack_top_uint8 == page_p->bytes[context_p->stack.last_position - 1]); 380 381 if (context_p->stack.last_position >= PARSER_STACK_PAGE_SIZE) 382 { 383 if (context_p->free_page_p != NULL) 384 { 385 page_p = context_p->free_page_p; 386 context_p->free_page_p = NULL; 387 } 388 else 389 { 390 size_t size = sizeof (parser_mem_page_t *) + PARSER_STACK_PAGE_SIZE; 391 page_p = (parser_mem_page_t *) parser_malloc (context_p, size); 392 } 393 394 page_p->next_p = context_p->stack.first_p; 395 context_p->stack.last_position = 0; 396 context_p->stack.first_p = page_p; 397 } 398 399 page_p->bytes[context_p->stack.last_position++] = uint8_value; 400 context_p->stack_top_uint8 = uint8_value; 401} /* parser_stack_push_uint8 */ 402 403/** 404 * Pops the last uint8_t value from the stack. 405 */ 406void 407parser_stack_pop_uint8 (parser_context_t *context_p) /**< context */ 408{ 409 parser_mem_page_t *page_p = context_p->stack.first_p; 410 411 JERRY_ASSERT (page_p != NULL 412 && context_p->stack_top_uint8 == page_p->bytes[context_p->stack.last_position - 1]); 413 414 context_p->stack.last_position--; 415 416 if (context_p->stack.last_position == 0) 417 { 418 context_p->stack.first_p = page_p->next_p; 419 context_p->stack.last_position = PARSER_STACK_PAGE_SIZE; 420 421 if (context_p->free_page_p == NULL) 422 { 423 context_p->free_page_p = page_p; 424 } 425 else 426 { 427 parser_free (page_p, 428 sizeof (parser_mem_page_t *) + PARSER_STACK_PAGE_SIZE); 429 } 430 431 page_p = context_p->stack.first_p; 432 433 JERRY_ASSERT (page_p != NULL); 434 } 435 436 context_p->stack_top_uint8 = page_p->bytes[context_p->stack.last_position - 1]; 437} /* parser_stack_pop_uint8 */ 438 439/** 440 * Pushes an uint16_t value onto the stack. 441 */ 442void 443parser_stack_push_uint16 (parser_context_t *context_p, /**< context */ 444 uint16_t uint16_value) /**< value pushed onto the stack */ 445{ 446 if (context_p->stack.last_position + 2 <= PARSER_STACK_PAGE_SIZE) 447 { 448 parser_mem_page_t *page_p = context_p->stack.first_p; 449 450 JERRY_ASSERT (page_p != NULL 451 && context_p->stack_top_uint8 == page_p->bytes[context_p->stack.last_position - 1]); 452 453 page_p->bytes[context_p->stack.last_position++] = (uint8_t) (uint16_value >> 8); 454 page_p->bytes[context_p->stack.last_position++] = (uint8_t) uint16_value; 455 context_p->stack_top_uint8 = (uint8_t) uint16_value; 456 } 457 else 458 { 459 parser_stack_push_uint8 (context_p, (uint8_t) (uint16_value >> 8)); 460 parser_stack_push_uint8 (context_p, (uint8_t) uint16_value); 461 } 462} /* parser_stack_push_uint16 */ 463 464/** 465 * Pops the last uint16_t value from the stack. 466 * 467 * @return the value popped from the stack. 468 */ 469uint16_t 470parser_stack_pop_uint16 (parser_context_t *context_p) /**< context */ 471{ 472 uint32_t value = context_p->stack_top_uint8; 473 474 if (context_p->stack.last_position >= 3) 475 { 476 parser_mem_page_t *page_p = context_p->stack.first_p; 477 478 JERRY_ASSERT (page_p != NULL 479 && context_p->stack_top_uint8 == page_p->bytes[context_p->stack.last_position - 1]); 480 481 value |= ((uint32_t) page_p->bytes[context_p->stack.last_position - 2]) << 8; 482 context_p->stack_top_uint8 = page_p->bytes[context_p->stack.last_position - 3]; 483 context_p->stack.last_position -= 2; 484 } 485 else 486 { 487 parser_stack_pop_uint8 (context_p); 488 value |= ((uint32_t) context_p->stack_top_uint8) << 8; 489 parser_stack_pop_uint8 (context_p); 490 } 491 return (uint16_t) value; 492} /* parser_stack_pop_uint16 */ 493 494/** 495 * Pushes a data onto the stack. 496 */ 497void 498parser_stack_push (parser_context_t *context_p, /**< context */ 499 const void *data_p, /**< data pushed onto the stack */ 500 uint32_t length) /**< length of the data */ 501{ 502 uint32_t fragment_length = PARSER_STACK_PAGE_SIZE - context_p->stack.last_position; 503 const uint8_t *bytes_p = (const uint8_t *) data_p; 504 parser_mem_page_t *page_p; 505 506 JERRY_ASSERT (length < PARSER_STACK_PAGE_SIZE && length > 0); 507 508 context_p->stack_top_uint8 = bytes_p[length - 1]; 509 510 if (fragment_length > 0) 511 { 512 /* Fill the remaining bytes. */ 513 if (fragment_length > length) 514 { 515 fragment_length = length; 516 } 517 518 memcpy (context_p->stack.first_p->bytes + context_p->stack.last_position, 519 bytes_p, 520 fragment_length); 521 522 if (fragment_length == length) 523 { 524 context_p->stack.last_position += length; 525 return; 526 } 527 528 bytes_p += fragment_length; 529 length -= fragment_length; 530 } 531 532 if (context_p->free_page_p != NULL) 533 { 534 page_p = context_p->free_page_p; 535 context_p->free_page_p = NULL; 536 } 537 else 538 { 539 size_t size = sizeof (parser_mem_page_t *) + PARSER_STACK_PAGE_SIZE; 540 541 page_p = (parser_mem_page_t *) parser_malloc (context_p, size); 542 } 543 544 page_p->next_p = context_p->stack.first_p; 545 546 context_p->stack.first_p = page_p; 547 548 memcpy (page_p->bytes, bytes_p, length); 549 context_p->stack.last_position = length; 550} /* parser_stack_push */ 551 552/** 553 * Pop bytes from the top of the stack. 554 */ 555void 556parser_stack_pop (parser_context_t *context_p, /**< context */ 557 void *data_p, /**< destination buffer, can be NULL */ 558 uint32_t length) /**< length of the data */ 559{ 560 uint8_t *bytes_p = (uint8_t *) data_p; 561 parser_mem_page_t *page_p = context_p->stack.first_p; 562 563 JERRY_ASSERT (length < PARSER_STACK_PAGE_SIZE && length > 0); 564 565 if (context_p->stack.last_position > length) 566 { 567 context_p->stack.last_position -= length; 568 context_p->stack_top_uint8 = page_p->bytes[context_p->stack.last_position - 1]; 569 570 if (bytes_p != NULL) 571 { 572 memcpy (bytes_p, context_p->stack.first_p->bytes + context_p->stack.last_position, length); 573 } 574 return; 575 } 576 577 JERRY_ASSERT (page_p->next_p != NULL); 578 579 length -= context_p->stack.last_position; 580 581 if (bytes_p != NULL) 582 { 583 memcpy (bytes_p + length, page_p->bytes, context_p->stack.last_position); 584 } 585 586 context_p->stack.first_p = page_p->next_p; 587 context_p->stack.last_position = PARSER_STACK_PAGE_SIZE - length; 588 context_p->stack_top_uint8 = page_p->next_p->bytes[context_p->stack.last_position - 1]; 589 590 if (bytes_p != NULL && length > 0) 591 { 592 memcpy (bytes_p, page_p->next_p->bytes + context_p->stack.last_position, length); 593 } 594 595 JERRY_ASSERT (context_p->stack.last_position > 0); 596 597 if (context_p->free_page_p == NULL) 598 { 599 context_p->free_page_p = page_p; 600 } 601 else 602 { 603 parser_free (page_p, 604 sizeof (parser_mem_page_t *) + PARSER_STACK_PAGE_SIZE); 605 } 606} /* parser_stack_pop */ 607 608/** 609 * Skip the next n bytes of the stack. 610 */ 611void 612parser_stack_iterator_skip (parser_stack_iterator_t *iterator, /**< iterator */ 613 size_t length) /**< number of skipped bytes */ 614{ 615 JERRY_ASSERT (length < PARSER_STACK_PAGE_SIZE && length > 0); 616 617 if (length < iterator->current_position) 618 { 619 iterator->current_position -= length; 620 } 621 else 622 { 623 iterator->current_position = PARSER_STACK_PAGE_SIZE - (length - iterator->current_position); 624 iterator->current_p = iterator->current_p->next_p; 625 } 626} /* parser_stack_iterator_skip */ 627 628/** 629 * Read bytes from the stack. 630 */ 631void 632parser_stack_iterator_read (parser_stack_iterator_t *iterator, /**< iterator */ 633 void *data_p, /**< destination buffer */ 634 size_t length) /**< length of the data */ 635{ 636 uint8_t *bytes_p = (uint8_t *) data_p; 637 638 JERRY_ASSERT (length < PARSER_STACK_PAGE_SIZE && length > 0); 639 640 if (length <= iterator->current_position) 641 { 642 memcpy (bytes_p, 643 iterator->current_p->bytes + iterator->current_position - length, 644 length); 645 } 646 else 647 { 648 JERRY_ASSERT (iterator->current_p->next_p != NULL); 649 650 length -= iterator->current_position; 651 memcpy (bytes_p + length, 652 iterator->current_p->bytes, 653 iterator->current_position); 654 memcpy (bytes_p, 655 iterator->current_p->next_p->bytes + PARSER_STACK_PAGE_SIZE - length, 656 length); 657 } 658} /* parser_stack_iterator_read */ 659 660/** 661 * Write bytes onto the stack. 662 */ 663void 664parser_stack_iterator_write (parser_stack_iterator_t *iterator, /**< iterator */ 665 const void *data_p, /**< destination buffer */ 666 size_t length) /**< length of the data */ 667{ 668 const uint8_t *bytes_p = (const uint8_t *) data_p; 669 670 JERRY_ASSERT (length < PARSER_STACK_PAGE_SIZE && length > 0); 671 672 if (length <= iterator->current_position) 673 { 674 memcpy (iterator->current_p->bytes + iterator->current_position - length, 675 bytes_p, 676 length); 677 } 678 else 679 { 680 JERRY_ASSERT (iterator->current_p->next_p != NULL); 681 682 length -= iterator->current_position; 683 memcpy (iterator->current_p->bytes, 684 bytes_p + length, 685 iterator->current_position); 686 memcpy (iterator->current_p->next_p->bytes + PARSER_STACK_PAGE_SIZE - length, 687 bytes_p, 688 length); 689 } 690} /* parser_stack_iterator_write */ 691 692/** 693 * @} 694 * @} 695 */ 696 697#endif /* ENABLED (JERRY_PARSER) */ 698