1 /* Author : Joshua Brindle <jbrindle (at) tresys.com> 2 * Karl MacMillan <kmacmillan (at) tresys.com> 3 * Jason Tang <jtang (at) tresys.com> 4 * Added support for binary policy modules 5 * 6 * Copyright (C) 2004 - 2005 Tresys Technology, LLC 7 * This program is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation, version 2. 10 */ 11 12 #include <assert.h> 13 #include <stdarg.h> 14 #include <stdlib.h> 15 #include <string.h> 16 17 #include <sepol/policydb/policydb.h> 18 #include <sepol/policydb/avrule_block.h> 19 #include <sepol/policydb/conditional.h> 20 21 #include "queue.h" 22 #include "module_compiler.h" 23 24 union stack_item_u { 25 avrule_block_t *avrule; 26 cond_list_t *cond_list; 27 }; 28 29 typedef struct scope_stack { 30 union stack_item_u u; 31 int type; /* for above union: 1 = avrule block, 2 = conditional */ 32 avrule_decl_t *decl; /* if in an avrule block, which 33 * declaration is current */ 34 avrule_t *last_avrule; 35 int in_else; /* if in an avrule block, within ELSE branch */ 36 int require_given; /* 1 if this block had at least one require */ 37 struct scope_stack *parent, *child; 38 } scope_stack_t; 39 40 extern policydb_t *policydbp; 41 extern queue_t id_queue; 42 extern int yyerror(char *msg); 43 extern void yyerror2(char *fmt, ...); 44 45 static int push_stack(int stack_type, ...); 46 static void pop_stack(void); 47 48 /* keep track of the last item added to the stack */ 49 static scope_stack_t *stack_top = NULL; 50 static avrule_block_t *last_block; 51 static uint32_t next_decl_id = 1; 52 53 int define_policy(int pass, int module_header_given) 54 { 55 char *id; 56 57 if (module_header_given) { 58 if (policydbp->policy_type != POLICY_MOD) { 59 yyerror 60 ("Module specification found while not building a policy module.\n"); 61 return -1; 62 } 63 64 if (pass == 2) { 65 while ((id = queue_remove(id_queue)) != NULL) 66 free(id); 67 } else { 68 id = (char *)queue_remove(id_queue); 69 if (!id) { 70 yyerror("no module name"); 71 return -1; 72 } 73 policydbp->name = id; 74 if ((policydbp->version = 75 queue_remove(id_queue)) == NULL) { 76 yyerror 77 ("Expected a module version but none was found."); 78 return -1; 79 } 80 } 81 } else { 82 if (policydbp->policy_type == POLICY_MOD) { 83 yyerror 84 ("Building a policy module, but no module specification found.\n"); 85 return -1; 86 } 87 } 88 /* the first declaration within the global avrule 89 block will always have an id of 1 */ 90 next_decl_id = 2; 91 92 /* reset the scoping stack */ 93 while (stack_top != NULL) { 94 pop_stack(); 95 } 96 if (push_stack(1, policydbp->global, policydbp->global->branch_list) == 97 -1) { 98 return -1; 99 } 100 last_block = policydbp->global; 101 return 0; 102 } 103 104 /* Given the current parse stack, returns 1 if a declaration would be 105 * allowed here or 0 if not. For example, declarations are not 106 * allowed in conditionals, so if there are any conditionals in the 107 * current scope stack then this would return a 0. 108 */ 109 static int is_declaration_allowed(void) 110 { 111 if (stack_top->type != 1 || stack_top->in_else) { 112 return 0; 113 } 114 return 1; 115 } 116 117 /* Attempt to declare a symbol within the current declaration. If 118 * currently within a non-conditional and in a non-else branch then 119 * insert the symbol, return 0 on success if symbol was undeclared. 120 * For roles and users, it is legal to have multiple declarations; as 121 * such return 1 to indicate that caller must free() the datum because 122 * it was not added. If symbols may not be declared here return -1. 123 * For duplicate declarations return -2. For all else, including out 124 * of memory, return -3. Note that dest_value and datum_value might 125 * not be restricted pointers. */ 126 int declare_symbol(uint32_t symbol_type, 127 hashtab_key_t key, hashtab_datum_t datum, 128 uint32_t * dest_value, uint32_t * datum_value) 129 { 130 avrule_decl_t *decl = stack_top->decl; 131 int retval; 132 133 /* first check that symbols may be declared here */ 134 if (!is_declaration_allowed()) { 135 return -1; 136 } 137 retval = symtab_insert(policydbp, symbol_type, key, datum, 138 SCOPE_DECL, decl->decl_id, dest_value); 139 if (retval == 1 && dest_value) { 140 symtab_datum_t *s = 141 (symtab_datum_t *) hashtab_search(policydbp-> 142 symtab[symbol_type].table, 143 key); 144 assert(s != NULL); 145 146 if (symbol_type == SYM_LEVELS) { 147 *dest_value = ((level_datum_t *)s)->level->sens; 148 } else { 149 *dest_value = s->value; 150 } 151 } else if (retval == -2) { 152 return -2; 153 } else if (retval < 0) { 154 return -3; 155 } else { /* fall through possible if retval is 0 */ 156 } 157 if (datum_value != NULL) { 158 if (ebitmap_set_bit(decl->declared.scope + symbol_type, 159 *datum_value - 1, 1)) { 160 return -3; 161 } 162 } 163 return retval; 164 } 165 166 static int role_implicit_bounds(hashtab_t roles_tab, 167 char *role_id, role_datum_t *role) 168 { 169 role_datum_t *bounds; 170 char *bounds_id, *delim; 171 172 delim = strrchr(role_id, '.'); 173 if (!delim) 174 return 0; /* no implicit boundary */ 175 176 bounds_id = strdup(role_id); 177 if (!bounds_id) { 178 yyerror("out of memory"); 179 return -1; 180 } 181 bounds_id[(size_t)(delim - role_id)] = '\0'; 182 183 bounds = hashtab_search(roles_tab, bounds_id); 184 if (!bounds) { 185 yyerror2("role %s doesn't exist, is implicit bounds of %s", 186 bounds_id, role_id); 187 return -1; 188 } 189 190 if (!role->bounds) 191 role->bounds = bounds->s.value; 192 else if (role->bounds != bounds->s.value) { 193 yyerror2("role %s has inconsistent bounds %s/%s", 194 role_id, bounds_id, 195 policydbp->p_role_val_to_name[role->bounds - 1]); 196 return -1; 197 } 198 free(bounds_id); 199 200 return 0; 201 } 202 203 role_datum_t *declare_role(unsigned char isattr) 204 { 205 char *id = queue_remove(id_queue), *dest_id = NULL; 206 role_datum_t *role = NULL, *dest_role = NULL; 207 int retval; 208 uint32_t value; 209 210 if (id == NULL) { 211 yyerror("no role name"); 212 return NULL; 213 } 214 if ((role = (role_datum_t *) malloc(sizeof(*role))) == NULL) { 215 yyerror("Out of memory!"); 216 free(id); 217 return NULL; 218 } 219 role_datum_init(role); 220 role->flavor = isattr ? ROLE_ATTRIB : ROLE_ROLE; 221 retval = 222 declare_symbol(SYM_ROLES, id, (hashtab_datum_t *) role, &value, 223 &value); 224 if (retval == 0) { 225 role->s.value = value; 226 if ((dest_id = strdup(id)) == NULL) { 227 yyerror("Out of memory!"); 228 return NULL; 229 } 230 } else { 231 /* this role was already declared in this module, or error */ 232 dest_id = id; 233 role_datum_destroy(role); 234 free(role); 235 } 236 if (retval == 0 || retval == 1) { 237 /* create a new role_datum_t for this decl, if necessary */ 238 hashtab_t roles_tab; 239 assert(stack_top->type == 1); 240 if (stack_top->parent == NULL) { 241 /* in parent, so use global symbol table */ 242 roles_tab = policydbp->p_roles.table; 243 } else { 244 roles_tab = stack_top->decl->p_roles.table; 245 } 246 dest_role = (role_datum_t *) hashtab_search(roles_tab, dest_id); 247 if (dest_role == NULL) { 248 if ((dest_role = 249 (role_datum_t *) malloc(sizeof(*dest_role))) == 250 NULL) { 251 yyerror("Out of memory!"); 252 free(dest_id); 253 return NULL; 254 } 255 role_datum_init(dest_role); 256 dest_role->s.value = value; 257 dest_role->flavor = isattr ? ROLE_ATTRIB : ROLE_ROLE; 258 if (role_implicit_bounds(roles_tab, dest_id, dest_role)) { 259 free(dest_id); 260 role_datum_destroy(dest_role); 261 free(dest_role); 262 return NULL; 263 } 264 if (hashtab_insert(roles_tab, dest_id, dest_role)) { 265 yyerror("Out of memory!"); 266 free(dest_id); 267 role_datum_destroy(dest_role); 268 free(dest_role); 269 return NULL; 270 } 271 } else { 272 free(dest_id); 273 } 274 } else { 275 free(dest_id); 276 } 277 switch (retval) { 278 case -3:{ 279 yyerror("Out of memory!"); 280 return NULL; 281 } 282 case -2:{ 283 yyerror("duplicate declaration of role"); 284 return NULL; 285 } 286 case -1:{ 287 yyerror("could not declare role here"); 288 return NULL; 289 } 290 case 0:{ 291 if (ebitmap_set_bit 292 (&dest_role->dominates, role->s.value - 1, 1)) { 293 yyerror("out of memory"); 294 return NULL; 295 } 296 return dest_role; 297 } 298 case 1:{ 299 return dest_role; /* role already declared for this block */ 300 } 301 default:{ 302 assert(0); /* should never get here */ 303 } 304 } 305 } 306 307 type_datum_t *declare_type(unsigned char primary, unsigned char isattr) 308 { 309 char *id; 310 type_datum_t *typdatum; 311 int retval; 312 uint32_t value = 0; 313 314 id = (char *)queue_remove(id_queue); 315 if (!id) { 316 yyerror("no type/attribute name?"); 317 return NULL; 318 } 319 if (strcmp(id, "self") == 0) { 320 yyerror 321 ("'self' is a reserved type name and may not be declared."); 322 free(id); 323 return NULL; 324 } 325 326 typdatum = (type_datum_t *) malloc(sizeof(type_datum_t)); 327 if (!typdatum) { 328 yyerror("Out of memory!"); 329 free(id); 330 return NULL; 331 } 332 type_datum_init(typdatum); 333 typdatum->primary = primary; 334 typdatum->flavor = isattr ? TYPE_ATTRIB : TYPE_TYPE; 335 336 retval = declare_symbol(SYM_TYPES, id, typdatum, &value, &value); 337 if (retval == 0 || retval == 1) { 338 if (typdatum->primary) { 339 typdatum->s.value = value; 340 } 341 } else { 342 /* error occurred (can't have duplicate type declarations) */ 343 free(id); 344 type_datum_destroy(typdatum); 345 free(typdatum); 346 } 347 switch (retval) { 348 case -3:{ 349 yyerror("Out of memory!"); 350 return NULL; 351 } 352 case -2:{ 353 yyerror2("duplicate declaration of type/attribute"); 354 return NULL; 355 } 356 case -1:{ 357 yyerror("could not declare type/attribute here"); 358 return NULL; 359 } 360 case 0: 361 case 1:{ 362 return typdatum; 363 } 364 default:{ 365 assert(0); /* should never get here */ 366 } 367 } 368 } 369 370 static int user_implicit_bounds(hashtab_t users_tab, 371 char *user_id, user_datum_t *user) 372 { 373 user_datum_t *bounds; 374 char *bounds_id, *delim; 375 376 delim = strrchr(user_id, '.'); 377 if (!delim) 378 return 0; /* no implicit boundary */ 379 380 bounds_id = strdup(user_id); 381 if (!bounds_id) { 382 yyerror("out of memory"); 383 return -1; 384 } 385 bounds_id[(size_t)(delim - user_id)] = '\0'; 386 387 bounds = hashtab_search(users_tab, bounds_id); 388 if (!bounds) { 389 yyerror2("user %s doesn't exist, is implicit bounds of %s", 390 bounds_id, user_id); 391 return -1; 392 } 393 394 if (!user->bounds) 395 user->bounds = bounds->s.value; 396 else if (user->bounds != bounds->s.value) { 397 yyerror2("user %s has inconsistent bounds %s/%s", 398 user_id, bounds_id, 399 policydbp->p_role_val_to_name[user->bounds - 1]); 400 return -1; 401 } 402 free(bounds_id); 403 404 return 0; 405 } 406 407 user_datum_t *declare_user(void) 408 { 409 char *id = queue_remove(id_queue), *dest_id = NULL; 410 user_datum_t *user = NULL, *dest_user = NULL; 411 int retval; 412 uint32_t value = 0; 413 414 if (id == NULL) { 415 yyerror("no user name"); 416 return NULL; 417 } 418 if ((user = (user_datum_t *) malloc(sizeof(*user))) == NULL) { 419 yyerror("Out of memory!"); 420 free(id); 421 return NULL; 422 } 423 user_datum_init(user); 424 425 retval = 426 declare_symbol(SYM_USERS, id, (hashtab_datum_t *) user, &value, 427 &value); 428 429 if (retval == 0) { 430 user->s.value = value; 431 if ((dest_id = strdup(id)) == NULL) { 432 yyerror("Out of memory!"); 433 return NULL; 434 } 435 } else { 436 /* this user was already declared in this module, or error */ 437 dest_id = id; 438 user_datum_destroy(user); 439 free(user); 440 } 441 if (retval == 0 || retval == 1) { 442 /* create a new user_datum_t for this decl, if necessary */ 443 hashtab_t users_tab; 444 assert(stack_top->type == 1); 445 if (stack_top->parent == NULL) { 446 /* in parent, so use global symbol table */ 447 users_tab = policydbp->p_users.table; 448 } else { 449 users_tab = stack_top->decl->p_users.table; 450 } 451 dest_user = (user_datum_t *) hashtab_search(users_tab, dest_id); 452 if (dest_user == NULL) { 453 if ((dest_user = 454 (user_datum_t *) malloc(sizeof(*dest_user))) == 455 NULL) { 456 yyerror("Out of memory!"); 457 free(dest_id); 458 return NULL; 459 } 460 user_datum_init(dest_user); 461 dest_user->s.value = value; 462 if (user_implicit_bounds(users_tab, dest_id, dest_user)) { 463 free(dest_id); 464 user_datum_destroy(dest_user); 465 free(dest_user); 466 return NULL; 467 } 468 if (hashtab_insert(users_tab, dest_id, dest_user)) { 469 yyerror("Out of memory!"); 470 free(dest_id); 471 user_datum_destroy(dest_user); 472 free(dest_user); 473 return NULL; 474 } 475 } else { 476 free(dest_id); 477 } 478 } else { 479 free(dest_id); 480 } 481 switch (retval) { 482 case -3:{ 483 yyerror("Out of memory!"); 484 return NULL; 485 } 486 case -2:{ 487 yyerror("duplicate declaration of user"); 488 return NULL; 489 } 490 case -1:{ 491 yyerror("could not declare user here"); 492 return NULL; 493 } 494 case 0:{ 495 return dest_user; 496 } 497 case 1:{ 498 return dest_user; /* user already declared for this block */ 499 } 500 default:{ 501 assert(0); /* should never get here */ 502 } 503 } 504 } 505 506 /* Return a type_datum_t for the local avrule_decl with the given ID. 507 * If it does not exist, create one with the same value as 'value'. 508 * This function assumes that the ID is within scope. c.f., 509 * is_id_in_scope(). 510 * 511 * NOTE: this function usurps ownership of id afterwards. The caller 512 * shall not reference it nor free() it afterwards. 513 */ 514 type_datum_t *get_local_type(char *id, uint32_t value, unsigned char isattr) 515 { 516 type_datum_t *dest_typdatum; 517 hashtab_t types_tab; 518 assert(stack_top->type == 1); 519 if (stack_top->parent == NULL) { 520 /* in global, so use global symbol table */ 521 types_tab = policydbp->p_types.table; 522 } else { 523 types_tab = stack_top->decl->p_types.table; 524 } 525 dest_typdatum = hashtab_search(types_tab, id); 526 if (!dest_typdatum) { 527 dest_typdatum = (type_datum_t *) malloc(sizeof(type_datum_t)); 528 if (dest_typdatum == NULL) { 529 free(id); 530 return NULL; 531 } 532 type_datum_init(dest_typdatum); 533 dest_typdatum->s.value = value; 534 dest_typdatum->flavor = isattr ? TYPE_ATTRIB : TYPE_TYPE; 535 dest_typdatum->primary = 1; 536 if (hashtab_insert(types_tab, id, dest_typdatum)) { 537 free(id); 538 type_datum_destroy(dest_typdatum); 539 free(dest_typdatum); 540 return NULL; 541 } 542 543 } else { 544 free(id); 545 if (dest_typdatum->flavor != isattr ? TYPE_ATTRIB : TYPE_TYPE) { 546 return NULL; 547 } 548 } 549 return dest_typdatum; 550 } 551 552 /* Return a role_datum_t for the local avrule_decl with the given ID. 553 * If it does not exist, create one with the same value as 'value'. 554 * This function assumes that the ID is within scope. c.f., 555 * is_id_in_scope(). 556 * 557 * NOTE: this function usurps ownership of id afterwards. The caller 558 * shall not reference it nor free() it afterwards. 559 */ 560 role_datum_t *get_local_role(char *id, uint32_t value, unsigned char isattr) 561 { 562 role_datum_t *dest_roledatum; 563 hashtab_t roles_tab; 564 565 assert(stack_top->type == 1); 566 567 if (stack_top->parent == NULL) { 568 /* in global, so use global symbol table */ 569 roles_tab = policydbp->p_roles.table; 570 } else { 571 roles_tab = stack_top->decl->p_roles.table; 572 } 573 574 dest_roledatum = hashtab_search(roles_tab, id); 575 if (!dest_roledatum) { 576 dest_roledatum = (role_datum_t *)malloc(sizeof(role_datum_t)); 577 if (dest_roledatum == NULL) { 578 free(id); 579 return NULL; 580 } 581 582 role_datum_init(dest_roledatum); 583 dest_roledatum->s.value = value; 584 dest_roledatum->flavor = isattr ? ROLE_ATTRIB : ROLE_ROLE; 585 586 if (hashtab_insert(roles_tab, id, dest_roledatum)) { 587 free(id); 588 role_datum_destroy(dest_roledatum); 589 free(dest_roledatum); 590 return NULL; 591 } 592 } else { 593 free(id); 594 if (dest_roledatum->flavor != isattr ? ROLE_ATTRIB : ROLE_ROLE) 595 return NULL; 596 } 597 598 return dest_roledatum; 599 } 600 601 /* Given the current parse stack, returns 1 if a requirement would be 602 * allowed here or 0 if not. For example, the ELSE branch may never 603 * have its own requirements. 604 */ 605 static int is_require_allowed(void) 606 { 607 if (stack_top->type == 1 && !stack_top->in_else) { 608 return 1; 609 } 610 return 0; 611 } 612 613 /* Attempt to require a symbol within the current scope. If currently 614 * within an optional (and not its else branch), add the symbol to the 615 * required list. Return 0 on success, 1 if caller needs to free() 616 * datum. If symbols may not be declared here return -1. For duplicate 617 * declarations return -2. For all else, including out of memory, 618 * return -3.. Note that dest_value and datum_value might not be 619 * restricted pointers. 620 */ 621 int require_symbol(uint32_t symbol_type, 622 hashtab_key_t key, hashtab_datum_t datum, 623 uint32_t * dest_value, uint32_t * datum_value) 624 { 625 avrule_decl_t *decl = stack_top->decl; 626 int retval; 627 628 /* first check that symbols may be required here */ 629 if (!is_require_allowed()) { 630 return -1; 631 } 632 retval = symtab_insert(policydbp, symbol_type, key, datum, 633 SCOPE_REQ, decl->decl_id, dest_value); 634 if (retval == 1) { 635 symtab_datum_t *s = 636 (symtab_datum_t *) hashtab_search(policydbp-> 637 symtab[symbol_type].table, 638 key); 639 assert(s != NULL); 640 641 if (symbol_type == SYM_LEVELS) { 642 *dest_value = ((level_datum_t *)s)->level->sens; 643 } else { 644 *dest_value = s->value; 645 } 646 } else if (retval == -2) { 647 /* ignore require statements if that symbol was 648 * previously declared and is in current scope */ 649 int prev_declaration_ok = 0; 650 if (is_id_in_scope(symbol_type, key)) { 651 if (symbol_type == SYM_TYPES) { 652 /* check that previous symbol has same 653 * type/attribute-ness */ 654 unsigned char new_isattr = 655 ((type_datum_t *) datum)->flavor; 656 type_datum_t *old_datum = 657 (type_datum_t *) hashtab_search(policydbp-> 658 symtab 659 [SYM_TYPES]. 660 table, key); 661 assert(old_datum != NULL); 662 unsigned char old_isattr = old_datum->flavor; 663 prev_declaration_ok = 664 (old_isattr == new_isattr ? 1 : 0); 665 } else { 666 prev_declaration_ok = 1; 667 } 668 } 669 if (prev_declaration_ok) { 670 /* ignore this require statement because it 671 * was already declared within my scope */ 672 stack_top->require_given = 1; 673 return 1; 674 } else { 675 /* previous declaration was not in scope or 676 * had a mismatched type/attribute, so 677 * generate an error */ 678 return -2; 679 } 680 } else if (retval < 0) { 681 return -3; 682 } else { /* fall through possible if retval is 0 or 1 */ 683 } 684 if (datum_value != NULL) { 685 if (ebitmap_set_bit(decl->required.scope + symbol_type, 686 *datum_value - 1, 1)) { 687 return -3; 688 } 689 } 690 stack_top->require_given = 1; 691 return retval; 692 } 693 694 int add_perm_to_class(uint32_t perm_value, uint32_t class_value) 695 { 696 avrule_decl_t *decl = stack_top->decl; 697 scope_index_t *scope; 698 699 assert(perm_value >= 1); 700 assert(class_value >= 1); 701 scope = &decl->required; 702 if (class_value > scope->class_perms_len) { 703 int i; 704 ebitmap_t *new_map = realloc(scope->class_perms_map, 705 class_value * sizeof(*new_map)); 706 if (new_map == NULL) { 707 return -1; 708 } 709 scope->class_perms_map = new_map; 710 for (i = scope->class_perms_len; i < class_value; i++) { 711 ebitmap_init(scope->class_perms_map + i); 712 } 713 scope->class_perms_len = class_value; 714 } 715 if (ebitmap_set_bit(scope->class_perms_map + class_value - 1, 716 perm_value - 1, 1)) { 717 return -1; 718 } 719 return 0; 720 } 721 722 static int perm_destroy(hashtab_key_t key, hashtab_datum_t datum, void *p 723 __attribute__ ((unused))) 724 { 725 if (key) 726 free(key); 727 free(datum); 728 return 0; 729 } 730 731 static void class_datum_destroy(class_datum_t * cladatum) 732 { 733 if (cladatum != NULL) { 734 hashtab_map(cladatum->permissions.table, perm_destroy, NULL); 735 hashtab_destroy(cladatum->permissions.table); 736 free(cladatum); 737 } 738 } 739 740 int require_class(int pass) 741 { 742 char *class_id = queue_remove(id_queue); 743 char *perm_id = NULL; 744 class_datum_t *datum = NULL; 745 perm_datum_t *perm = NULL; 746 int ret; 747 748 if (pass == 2) { 749 free(class_id); 750 while ((perm_id = queue_remove(id_queue)) != NULL) 751 free(perm_id); 752 return 0; 753 } 754 755 /* first add the class if it is not already there */ 756 if (class_id == NULL) { 757 yyerror("no class name for class definition?"); 758 return -1; 759 } 760 761 if ((datum = calloc(1, sizeof(*datum))) == NULL || 762 symtab_init(&datum->permissions, PERM_SYMTAB_SIZE)) { 763 yyerror("Out of memory!"); 764 goto cleanup; 765 } 766 ret = 767 require_symbol(SYM_CLASSES, class_id, datum, &datum->s.value, 768 &datum->s.value); 769 switch (ret) { 770 case -3:{ 771 yyerror("Out of memory!"); 772 free(class_id); 773 class_datum_destroy(datum); 774 goto cleanup; 775 } 776 case -2:{ 777 yyerror("duplicate declaration of class"); 778 free(class_id); 779 class_datum_destroy(datum); 780 goto cleanup; 781 } 782 case -1:{ 783 yyerror("could not require class here"); 784 free(class_id); 785 class_datum_destroy(datum); 786 goto cleanup; 787 } 788 case 0:{ 789 /* a new class was added; reindex everything */ 790 if (policydb_index_classes(policydbp)) { 791 yyerror("Out of memory!"); 792 goto cleanup; 793 } 794 break; 795 } 796 case 1:{ 797 class_datum_destroy(datum); 798 datum = 799 hashtab_search(policydbp->p_classes.table, 800 class_id); 801 assert(datum); /* the class datum should have existed */ 802 free(class_id); 803 break; 804 } 805 default:{ 806 assert(0); /* should never get here */ 807 } 808 } 809 810 /* now add each of the permissions to this class's requirements */ 811 while ((perm_id = queue_remove(id_queue)) != NULL) { 812 int allocated = 0; 813 814 /* Is the permission already in the table? */ 815 perm = hashtab_search(datum->permissions.table, perm_id); 816 if (!perm && datum->comdatum) 817 perm = 818 hashtab_search(datum->comdatum->permissions.table, 819 perm_id); 820 if (perm) { 821 /* Yes, drop the name. */ 822 free(perm_id); 823 } else { 824 /* No - allocate and insert an entry for it. */ 825 if (policydbp->policy_type == POLICY_BASE) { 826 yyerror2 827 ("Base policy - require of permission %s without prior declaration.", 828 perm_id); 829 free(perm_id); 830 goto cleanup; 831 } 832 allocated = 1; 833 if ((perm = malloc(sizeof(*perm))) == NULL) { 834 yyerror("Out of memory!"); 835 free(perm_id); 836 goto cleanup; 837 } 838 memset(perm, 0, sizeof(*perm)); 839 ret = 840 hashtab_insert(datum->permissions.table, perm_id, 841 perm); 842 if (ret) { 843 yyerror("Out of memory!"); 844 free(perm_id); 845 free(perm); 846 goto cleanup; 847 } 848 perm->s.value = datum->permissions.nprim + 1; 849 } 850 851 if (add_perm_to_class(perm->s.value, datum->s.value) == -1) { 852 yyerror("Out of memory!"); 853 goto cleanup; 854 } 855 856 /* Update number of primitives if we allocated one. */ 857 if (allocated) 858 datum->permissions.nprim++; 859 } 860 return 0; 861 cleanup: 862 return -1; 863 } 864 865 static int require_role_or_attribute(int pass, unsigned char isattr) 866 { 867 char *id = queue_remove(id_queue); 868 role_datum_t *role = NULL; 869 int retval; 870 if (pass == 2) { 871 free(id); 872 return 0; 873 } 874 if (id == NULL) { 875 yyerror("no role name"); 876 return -1; 877 } 878 if ((role = malloc(sizeof(*role))) == NULL) { 879 free(id); 880 yyerror("Out of memory!"); 881 return -1; 882 } 883 role_datum_init(role); 884 role->flavor = isattr ? ROLE_ATTRIB : ROLE_ROLE; 885 retval = 886 require_symbol(SYM_ROLES, id, (hashtab_datum_t *) role, 887 &role->s.value, &role->s.value); 888 if (retval != 0) { 889 free(id); 890 role_datum_destroy(role); 891 free(role); 892 } 893 switch (retval) { 894 case -3:{ 895 yyerror("Out of memory!"); 896 return -1; 897 } 898 case -2:{ 899 yyerror("duplicate declaration of role"); 900 return -1; 901 } 902 case -1:{ 903 yyerror("could not require role here"); 904 return -1; 905 } 906 case 0:{ 907 /* all roles dominate themselves */ 908 if (ebitmap_set_bit 909 (&role->dominates, role->s.value - 1, 1)) { 910 yyerror("Out of memory"); 911 return -1; 912 } 913 return 0; 914 } 915 case 1:{ 916 return 0; /* role already required */ 917 } 918 default:{ 919 assert(0); /* should never get here */ 920 } 921 } 922 } 923 924 int require_role(int pass) 925 { 926 return require_role_or_attribute(pass, 0); 927 } 928 929 int require_attribute_role(int pass) 930 { 931 return require_role_or_attribute(pass, 1); 932 } 933 934 static int require_type_or_attribute(int pass, unsigned char isattr) 935 { 936 char *id = queue_remove(id_queue); 937 type_datum_t *type = NULL; 938 int retval; 939 if (pass == 2) { 940 free(id); 941 return 0; 942 } 943 if (id == NULL) { 944 yyerror("no type name"); 945 return -1; 946 } 947 if ((type = malloc(sizeof(*type))) == NULL) { 948 free(id); 949 yyerror("Out of memory!"); 950 return -1; 951 } 952 type_datum_init(type); 953 type->primary = 1; 954 type->flavor = isattr ? TYPE_ATTRIB : TYPE_TYPE; 955 retval = 956 require_symbol(SYM_TYPES, id, (hashtab_datum_t *) type, 957 &type->s.value, &type->s.value); 958 if (retval != 0) { 959 free(id); 960 free(type); 961 } 962 switch (retval) { 963 case -3:{ 964 yyerror("Out of memory!"); 965 return -1; 966 } 967 case -2:{ 968 yyerror("duplicate declaration of type/attribute"); 969 return -1; 970 } 971 case -1:{ 972 yyerror("could not require type/attribute here"); 973 return -1; 974 } 975 case 0:{ 976 return 0; 977 } 978 case 1:{ 979 return 0; /* type already required */ 980 } 981 default:{ 982 assert(0); /* should never get here */ 983 } 984 } 985 } 986 987 int require_type(int pass) 988 { 989 return require_type_or_attribute(pass, 0); 990 } 991 992 int require_attribute(int pass) 993 { 994 return require_type_or_attribute(pass, 1); 995 } 996 997 int require_user(int pass) 998 { 999 char *id = queue_remove(id_queue); 1000 user_datum_t *user = NULL; 1001 int retval; 1002 if (pass == 1) { 1003 free(id); 1004 return 0; 1005 } 1006 if (id == NULL) { 1007 yyerror("no user name"); 1008 return -1; 1009 } 1010 if ((user = malloc(sizeof(*user))) == NULL) { 1011 free(id); 1012 yyerror("Out of memory!"); 1013 return -1; 1014 } 1015 user_datum_init(user); 1016 retval = 1017 require_symbol(SYM_USERS, id, (hashtab_datum_t *) user, 1018 &user->s.value, &user->s.value); 1019 if (retval != 0) { 1020 free(id); 1021 user_datum_destroy(user); 1022 } 1023 switch (retval) { 1024 case -3:{ 1025 yyerror("Out of memory!"); 1026 return -1; 1027 } 1028 case -2:{ 1029 yyerror("duplicate declaration of user"); 1030 return -1; 1031 } 1032 case -1:{ 1033 yyerror("could not require user here"); 1034 return -1; 1035 } 1036 case 0:{ 1037 return 0; 1038 } 1039 case 1:{ 1040 return 0; /* user already required */ 1041 } 1042 default:{ 1043 assert(0); /* should never get here */ 1044 } 1045 } 1046 } 1047 1048 static int require_bool_tunable(int pass, int is_tunable) 1049 { 1050 char *id = queue_remove(id_queue); 1051 cond_bool_datum_t *booldatum = NULL; 1052 int retval; 1053 if (pass == 2) { 1054 free(id); 1055 return 0; 1056 } 1057 if (id == NULL) { 1058 yyerror("no boolean name"); 1059 return -1; 1060 } 1061 if ((booldatum = calloc(1, sizeof(*booldatum))) == NULL) { 1062 cond_destroy_bool(id, booldatum, NULL); 1063 yyerror("Out of memory!"); 1064 return -1; 1065 } 1066 if (is_tunable) 1067 booldatum->flags |= COND_BOOL_FLAGS_TUNABLE; 1068 retval = 1069 require_symbol(SYM_BOOLS, id, (hashtab_datum_t *) booldatum, 1070 &booldatum->s.value, &booldatum->s.value); 1071 if (retval != 0) { 1072 cond_destroy_bool(id, booldatum, NULL); 1073 } 1074 switch (retval) { 1075 case -3:{ 1076 yyerror("Out of memory!"); 1077 return -1; 1078 } 1079 case -2:{ 1080 yyerror("duplicate declaration of boolean"); 1081 return -1; 1082 } 1083 case -1:{ 1084 yyerror("could not require boolean here"); 1085 return -1; 1086 } 1087 case 0:{ 1088 return 0; 1089 } 1090 case 1:{ 1091 return 0; /* boolean already required */ 1092 } 1093 default:{ 1094 assert(0); /* should never get here */ 1095 } 1096 } 1097 } 1098 1099 int require_bool(int pass) 1100 { 1101 return require_bool_tunable(pass, 0); 1102 } 1103 1104 int require_tunable(int pass) 1105 { 1106 return require_bool_tunable(pass, 1); 1107 } 1108 1109 int require_sens(int pass) 1110 { 1111 char *id = queue_remove(id_queue); 1112 level_datum_t *level = NULL; 1113 int retval; 1114 if (pass == 2) { 1115 free(id); 1116 return 0; 1117 } 1118 if (!id) { 1119 yyerror("no sensitivity name"); 1120 return -1; 1121 } 1122 level = malloc(sizeof(level_datum_t)); 1123 if (!level) { 1124 free(id); 1125 yyerror("Out of memory!"); 1126 return -1; 1127 } 1128 level_datum_init(level); 1129 level->level = malloc(sizeof(mls_level_t)); 1130 if (!level->level) { 1131 free(id); 1132 level_datum_destroy(level); 1133 free(level); 1134 yyerror("Out of memory!"); 1135 return -1; 1136 } 1137 mls_level_init(level->level); 1138 retval = require_symbol(SYM_LEVELS, id, (hashtab_datum_t *) level, 1139 &level->level->sens, &level->level->sens); 1140 if (retval != 0) { 1141 free(id); 1142 mls_level_destroy(level->level); 1143 free(level->level); 1144 level_datum_destroy(level); 1145 free(level); 1146 } 1147 switch (retval) { 1148 case -3:{ 1149 yyerror("Out of memory!"); 1150 return -1; 1151 } 1152 case -2:{ 1153 yyerror("duplicate declaration of sensitivity"); 1154 return -1; 1155 } 1156 case -1:{ 1157 yyerror("could not require sensitivity here"); 1158 return -1; 1159 } 1160 case 0:{ 1161 return 0; 1162 } 1163 case 1:{ 1164 return 0; /* sensitivity already required */ 1165 } 1166 default:{ 1167 assert(0); /* should never get here */ 1168 } 1169 } 1170 } 1171 1172 int require_cat(int pass) 1173 { 1174 char *id = queue_remove(id_queue); 1175 cat_datum_t *cat = NULL; 1176 int retval; 1177 if (pass == 2) { 1178 free(id); 1179 return 0; 1180 } 1181 if (!id) { 1182 yyerror("no category name"); 1183 return -1; 1184 } 1185 cat = malloc(sizeof(cat_datum_t)); 1186 if (!cat) { 1187 free(id); 1188 yyerror("Out of memory!"); 1189 return -1; 1190 } 1191 cat_datum_init(cat); 1192 1193 retval = require_symbol(SYM_CATS, id, (hashtab_datum_t *) cat, 1194 &cat->s.value, &cat->s.value); 1195 if (retval != 0) { 1196 free(id); 1197 cat_datum_destroy(cat); 1198 free(cat); 1199 } 1200 switch (retval) { 1201 case -3:{ 1202 yyerror("Out of memory!"); 1203 return -1; 1204 } 1205 case -2:{ 1206 yyerror("duplicate declaration of category"); 1207 return -1; 1208 } 1209 case -1:{ 1210 yyerror("could not require category here"); 1211 return -1; 1212 } 1213 case 0:{ 1214 return 0; 1215 } 1216 case 1:{ 1217 return 0; /* category already required */ 1218 } 1219 default:{ 1220 assert(0); /* should never get here */ 1221 } 1222 } 1223 } 1224 1225 static int is_scope_in_stack(scope_datum_t * scope, scope_stack_t * stack) 1226 { 1227 int i; 1228 if (stack == NULL) { 1229 return 0; /* no matching scope found */ 1230 } 1231 if (stack->type == 1) { 1232 avrule_decl_t *decl = stack->decl; 1233 for (i = 0; i < scope->decl_ids_len; i++) { 1234 if (scope->decl_ids[i] == decl->decl_id) { 1235 return 1; 1236 } 1237 } 1238 } else { 1239 /* note that conditionals can't declare or require 1240 * symbols, so skip this level */ 1241 } 1242 1243 /* not within scope of this stack, so try its parent */ 1244 return is_scope_in_stack(scope, stack->parent); 1245 } 1246 1247 int is_id_in_scope(uint32_t symbol_type, hashtab_key_t id) 1248 { 1249 scope_datum_t *scope = 1250 (scope_datum_t *) hashtab_search(policydbp->scope[symbol_type]. 1251 table, id); 1252 if (scope == NULL) { 1253 return 1; /* id is not known, so return success */ 1254 } 1255 return is_scope_in_stack(scope, stack_top); 1256 } 1257 1258 static int is_perm_in_scope_index(uint32_t perm_value, uint32_t class_value, 1259 scope_index_t * scope) 1260 { 1261 if (class_value > scope->class_perms_len) { 1262 return 1; 1263 } 1264 if (ebitmap_get_bit(scope->class_perms_map + class_value - 1, 1265 perm_value - 1)) { 1266 return 1; 1267 } 1268 return 0; 1269 } 1270 1271 static int is_perm_in_stack(uint32_t perm_value, uint32_t class_value, 1272 scope_stack_t * stack) 1273 { 1274 if (stack == NULL) { 1275 return 0; /* no matching scope found */ 1276 } 1277 if (stack->type == 1) { 1278 avrule_decl_t *decl = stack->decl; 1279 if (is_perm_in_scope_index 1280 (perm_value, class_value, &decl->required) 1281 || is_perm_in_scope_index(perm_value, class_value, 1282 &decl->declared)) { 1283 return 1; 1284 } 1285 } else { 1286 /* note that conditionals can't declare or require 1287 * symbols, so skip this level */ 1288 } 1289 1290 /* not within scope of this stack, so try its parent */ 1291 return is_perm_in_stack(perm_value, class_value, stack->parent); 1292 } 1293 1294 int is_perm_in_scope(hashtab_key_t perm_id, hashtab_key_t class_id) 1295 { 1296 class_datum_t *cladatum = 1297 (class_datum_t *) hashtab_search(policydbp->p_classes.table, 1298 class_id); 1299 perm_datum_t *perdatum; 1300 if (cladatum == NULL) { 1301 return 1; 1302 } 1303 perdatum = (perm_datum_t *) hashtab_search(cladatum->permissions.table, 1304 perm_id); 1305 if (perdatum == NULL) { 1306 return 1; 1307 } 1308 return is_perm_in_stack(perdatum->s.value, cladatum->s.value, 1309 stack_top); 1310 } 1311 1312 cond_list_t *get_current_cond_list(cond_list_t * cond) 1313 { 1314 /* FIX ME: do something different here if in a nested 1315 * conditional? */ 1316 avrule_decl_t *decl = stack_top->decl; 1317 return get_decl_cond_list(policydbp, decl, cond); 1318 } 1319 1320 /* Append the new conditional node to the existing ones. During 1321 * expansion the list will be reversed -- i.e., the last AV rule will 1322 * be the first one listed in the policy. This matches the behavior 1323 * of the upstream compiler. */ 1324 void append_cond_list(cond_list_t * cond) 1325 { 1326 cond_list_t *old_cond = get_current_cond_list(cond); 1327 avrule_t *tmp; 1328 assert(old_cond != NULL); /* probably out of memory */ 1329 if (old_cond->avtrue_list == NULL) { 1330 old_cond->avtrue_list = cond->avtrue_list; 1331 } else { 1332 for (tmp = old_cond->avtrue_list; tmp->next != NULL; 1333 tmp = tmp->next) ; 1334 tmp->next = cond->avtrue_list; 1335 } 1336 if (old_cond->avfalse_list == NULL) { 1337 old_cond->avfalse_list = cond->avfalse_list; 1338 } else { 1339 for (tmp = old_cond->avfalse_list; tmp->next != NULL; 1340 tmp = tmp->next) ; 1341 tmp->next = cond->avfalse_list; 1342 } 1343 1344 old_cond->flags |= cond->flags; 1345 } 1346 1347 void append_avrule(avrule_t * avrule) 1348 { 1349 avrule_decl_t *decl = stack_top->decl; 1350 1351 /* currently avrules follow a completely different code path 1352 * for handling avrules and compute types 1353 * (define_cond_avrule_te_avtab, define_cond_compute_type); 1354 * therefore there ought never be a conditional on top of the 1355 * scope stack */ 1356 assert(stack_top->type == 1); 1357 1358 if (stack_top->last_avrule == NULL) { 1359 decl->avrules = avrule; 1360 } else { 1361 stack_top->last_avrule->next = avrule; 1362 } 1363 stack_top->last_avrule = avrule; 1364 } 1365 1366 /* this doesn't actually append, but really prepends it */ 1367 void append_role_trans(role_trans_rule_t * role_tr_rules) 1368 { 1369 avrule_decl_t *decl = stack_top->decl; 1370 1371 /* role transitions are not allowed within conditionals */ 1372 assert(stack_top->type == 1); 1373 1374 role_tr_rules->next = decl->role_tr_rules; 1375 decl->role_tr_rules = role_tr_rules; 1376 } 1377 1378 /* this doesn't actually append, but really prepends it */ 1379 void append_role_allow(role_allow_rule_t * role_allow_rules) 1380 { 1381 avrule_decl_t *decl = stack_top->decl; 1382 1383 /* role allows are not allowed within conditionals */ 1384 assert(stack_top->type == 1); 1385 1386 role_allow_rules->next = decl->role_allow_rules; 1387 decl->role_allow_rules = role_allow_rules; 1388 } 1389 1390 /* this doesn't actually append, but really prepends it */ 1391 void append_filename_trans(filename_trans_rule_t * filename_trans_rules) 1392 { 1393 avrule_decl_t *decl = stack_top->decl; 1394 1395 /* filename transitions are not allowed within conditionals */ 1396 assert(stack_top->type == 1); 1397 1398 filename_trans_rules->next = decl->filename_trans_rules; 1399 decl->filename_trans_rules = filename_trans_rules; 1400 } 1401 1402 /* this doesn't actually append, but really prepends it */ 1403 void append_range_trans(range_trans_rule_t * range_tr_rules) 1404 { 1405 avrule_decl_t *decl = stack_top->decl; 1406 1407 /* range transitions are not allowed within conditionals */ 1408 assert(stack_top->type == 1); 1409 1410 range_tr_rules->next = decl->range_tr_rules; 1411 decl->range_tr_rules = range_tr_rules; 1412 } 1413 1414 int begin_optional(int pass) 1415 { 1416 avrule_block_t *block = NULL; 1417 avrule_decl_t *decl; 1418 if (pass == 1) { 1419 /* allocate a new avrule block for this optional block */ 1420 if ((block = avrule_block_create()) == NULL || 1421 (decl = avrule_decl_create(next_decl_id)) == NULL) { 1422 goto cleanup; 1423 } 1424 block->flags |= AVRULE_OPTIONAL; 1425 block->branch_list = decl; 1426 last_block->next = block; 1427 } else { 1428 /* select the next block from the chain built during pass 1 */ 1429 block = last_block->next; 1430 assert(block != NULL && 1431 block->branch_list != NULL && 1432 block->branch_list->decl_id == next_decl_id); 1433 decl = block->branch_list; 1434 } 1435 if (push_stack(1, block, decl) == -1) { 1436 goto cleanup; 1437 } 1438 stack_top->last_avrule = NULL; 1439 last_block = block; 1440 next_decl_id++; 1441 return 0; 1442 cleanup: 1443 yyerror("Out of memory!"); 1444 avrule_block_destroy(block); 1445 return -1; 1446 } 1447 1448 int end_optional(int pass) 1449 { 1450 /* once nested conditionals are allowed, do the stack unfolding here */ 1451 pop_stack(); 1452 return 0; 1453 } 1454 1455 int begin_optional_else(int pass) 1456 { 1457 avrule_decl_t *decl; 1458 assert(stack_top->type == 1 && stack_top->in_else == 0); 1459 if (pass == 1) { 1460 /* allocate a new declaration and add it to the 1461 * current chain */ 1462 if ((decl = avrule_decl_create(next_decl_id)) == NULL) { 1463 yyerror("Out of memory!"); 1464 return -1; 1465 } 1466 stack_top->decl->next = decl; 1467 } else { 1468 /* pick the (hopefully last) declaration of this 1469 avrule block, built from pass 1 */ 1470 decl = stack_top->decl->next; 1471 assert(decl != NULL && 1472 decl->next == NULL && decl->decl_id == next_decl_id); 1473 } 1474 stack_top->in_else = 1; 1475 stack_top->decl = decl; 1476 stack_top->last_avrule = NULL; 1477 stack_top->require_given = 0; 1478 next_decl_id++; 1479 return 0; 1480 } 1481 1482 static int copy_requirements(avrule_decl_t * dest, scope_stack_t * stack) 1483 { 1484 int i; 1485 if (stack == NULL) { 1486 return 0; 1487 } 1488 if (stack->type == 1) { 1489 scope_index_t *src_scope = &stack->decl->required; 1490 scope_index_t *dest_scope = &dest->required; 1491 for (i = 0; i < SYM_NUM; i++) { 1492 ebitmap_t *src_bitmap = &src_scope->scope[i]; 1493 ebitmap_t *dest_bitmap = &dest_scope->scope[i]; 1494 if (ebitmap_union(dest_bitmap, src_bitmap)) { 1495 yyerror("Out of memory!"); 1496 return -1; 1497 } 1498 } 1499 /* now copy class permissions */ 1500 if (src_scope->class_perms_len > dest_scope->class_perms_len) { 1501 ebitmap_t *new_map = 1502 realloc(dest_scope->class_perms_map, 1503 src_scope->class_perms_len * 1504 sizeof(*new_map)); 1505 if (new_map == NULL) { 1506 yyerror("Out of memory!"); 1507 return -1; 1508 } 1509 dest_scope->class_perms_map = new_map; 1510 for (i = dest_scope->class_perms_len; 1511 i < src_scope->class_perms_len; i++) { 1512 ebitmap_init(dest_scope->class_perms_map + i); 1513 } 1514 dest_scope->class_perms_len = 1515 src_scope->class_perms_len; 1516 } 1517 for (i = 0; i < src_scope->class_perms_len; i++) { 1518 ebitmap_t *src_bitmap = &src_scope->class_perms_map[i]; 1519 ebitmap_t *dest_bitmap = 1520 &dest_scope->class_perms_map[i]; 1521 if (ebitmap_union(dest_bitmap, src_bitmap)) { 1522 yyerror("Out of memory!"); 1523 return -1; 1524 } 1525 } 1526 } 1527 return copy_requirements(dest, stack->parent); 1528 } 1529 1530 /* During pass 1, check that at least one thing was required within 1531 * this block, for those places where a REQUIRED is necessary. During 1532 * pass 2, have this block inherit its parents' requirements. Return 1533 * 0 on success, -1 on failure. */ 1534 int end_avrule_block(int pass) 1535 { 1536 avrule_decl_t *decl = stack_top->decl; 1537 assert(stack_top->type == 1); 1538 if (pass == 2) { 1539 /* this avrule_decl inherits all of its parents' 1540 * requirements */ 1541 if (copy_requirements(decl, stack_top->parent) == -1) { 1542 return -1; 1543 } 1544 return 0; 1545 } 1546 if (!stack_top->in_else && !stack_top->require_given) { 1547 if (policydbp->policy_type == POLICY_BASE 1548 && stack_top->parent != NULL) { 1549 /* if this is base no require should be in the global block */ 1550 return 0; 1551 } else { 1552 /* non-ELSE branches must have at least one thing required */ 1553 yyerror("This block has no require section."); 1554 return -1; 1555 } 1556 } 1557 return 0; 1558 } 1559 1560 /* Push a new scope on to the stack and update the 'last' pointer. 1561 * Return 0 on success, -1 if out * of memory. */ 1562 static int push_stack(int stack_type, ...) 1563 { 1564 scope_stack_t *s = calloc(1, sizeof(*s)); 1565 va_list ap; 1566 if (s == NULL) { 1567 return -1; 1568 } 1569 va_start(ap, stack_type); 1570 switch (s->type = stack_type) { 1571 case 1:{ 1572 s->u.avrule = va_arg(ap, avrule_block_t *); 1573 s->decl = va_arg(ap, avrule_decl_t *); 1574 break; 1575 } 1576 case 2:{ 1577 s->u.cond_list = va_arg(ap, cond_list_t *); 1578 break; 1579 } 1580 default: 1581 /* invalid stack type given */ 1582 assert(0); 1583 } 1584 va_end(ap); 1585 s->parent = stack_top; 1586 s->child = NULL; 1587 stack_top = s; 1588 return 0; 1589 } 1590 1591 /* Pop off the most recently added from the stack. Update the 'last' 1592 * pointer. */ 1593 static void pop_stack(void) 1594 { 1595 scope_stack_t *parent; 1596 assert(stack_top != NULL); 1597 parent = stack_top->parent; 1598 if (parent != NULL) { 1599 parent->child = NULL; 1600 } 1601 free(stack_top); 1602 stack_top = parent; 1603 } 1604