1 #include <magic_sentry.h> 2 #include <magic_splay_tree.h> 3 4 /*===========================================================================* 5 * magic_sentry_get_off_by_n * 6 *===========================================================================*/ 7 PUBLIC long magic_sentry_get_off_by_n(struct _magic_sentry *sentry, 8 void *addr, int flags) 9 { 10 char *el_addr = (char*) addr, *first_el_addr, *last_el_addr; 11 size_t el_size; 12 unsigned long n, diff; 13 long long_n; 14 15 if (sentry->type->type_id != MAGIC_TYPE_ARRAY) { 16 return LONG_MAX; 17 } 18 el_size = sentry->type->contained_types[0]->size; 19 first_el_addr = (char*) sentry->address; 20 last_el_addr = (first_el_addr+sentry->type->size-el_size); 21 if (el_addr >= last_el_addr) { 22 diff = (unsigned long) (el_addr - last_el_addr); 23 } 24 else if (el_addr <= first_el_addr) { 25 diff = (unsigned long) (first_el_addr - el_addr); 26 } 27 else { 28 return LONG_MAX; 29 } 30 if (diff % el_size != 0) { 31 return LONG_MAX; 32 } 33 n = diff / el_size; 34 if (n >= LONG_MAX) { 35 return LONG_MAX; 36 } 37 long_n = (el_addr >= last_el_addr ? (long) n : -((long)n)); 38 if ((long_n < 0 && !(flags & MAGIC_SENTRY_OFF_BY_N_NEGATIVE)) 39 || (long_n > 0 && !(flags & MAGIC_SENTRY_OFF_BY_N_POSITIVE)) 40 || (long_n == 0 && !(flags & MAGIC_SENTRY_OFF_BY_N_ZERO))) { 41 return LONG_MAX; 42 } 43 return long_n; 44 } 45 46 /*===========================================================================* 47 * magic_do_check_sentry * 48 *===========================================================================*/ 49 PRIVATE INLINE int magic_do_check_sentry(struct _magic_sentry *sentry) 50 { 51 int is_size_ok; 52 assert(sentry && "NULL sentry found!"); 53 is_size_ok = sentry->type->size > 0; 54 if (!is_size_ok) { 55 _magic_printf("magic_do_check_sentry: bad sentry, checks: %d\n", is_size_ok); 56 MAGIC_SENTRY_PRINT(sentry, MAGIC_EXPAND_TYPE_STR); 57 _magic_printf("\n"); 58 return FALSE; 59 } 60 return TRUE; 61 } 62 63 /*===========================================================================* 64 * magic_check_sentry * 65 *===========================================================================*/ 66 PUBLIC int magic_check_sentry(struct _magic_sentry *sentry) 67 { 68 int check; 69 check = magic_do_check_sentry(sentry); 70 if (!check) { 71 return FALSE; 72 } 73 74 #if MAGIC_CHECK_LEVEL == 2 75 check = magic_check_sentries(); 76 if (!check) { 77 _magic_printf("magic_check_sentry: bad other sentry\n"); 78 return FALSE; 79 } 80 #endif 81 82 return TRUE; 83 } 84 85 /*===========================================================================* 86 * magic_check_sentries * 87 *===========================================================================*/ 88 PUBLIC int magic_check_sentries() 89 { 90 int i, ret, check = TRUE; 91 92 for (i = 0 ; i < _magic_sentries_num ; i++) { 93 ret = magic_do_check_sentry(&_magic_sentries[i]); 94 if (ret == FALSE) { 95 check = FALSE; 96 } 97 } 98 99 return check; 100 } 101 102 /*===========================================================================* 103 * magic_sentry_lookup_by_id * 104 *===========================================================================*/ 105 PUBLIC struct _magic_sentry *magic_sentry_lookup_by_id(_magic_id_t id, 106 struct _magic_dsentry *dsentry_buff) 107 { 108 struct _magic_sentry *entry = NULL; 109 struct _magic_dsentry *prev_dsentry, *dsentry; 110 struct _magic_sentry *sentry; 111 112 if (id <= 0) { 113 return NULL; 114 } 115 116 /* O(1) ID lookup for sentries. */ 117 #if MAGIC_LOOKUP_SENTRY 118 if ((int)id <= _magic_sentries_num) { 119 return &_magic_sentries[id - 1]; 120 } 121 #endif 122 123 /* O(N) ID lookup for dsentries. */ 124 #if MAGIC_LOOKUP_DSENTRY 125 MAGIC_DSENTRY_LOCK(); 126 MAGIC_DSENTRY_ALIVE_NESTED_ITER(_magic_first_dsentry, prev_dsentry, dsentry, sentry, 127 if(sentry->id == id) { 128 if(dsentry_buff) { 129 magic_copy_dsentry(dsentry, dsentry_buff); 130 entry = MAGIC_DSENTRY_TO_SENTRY(dsentry_buff); 131 } 132 else { 133 entry = sentry; 134 } 135 break; 136 } 137 ); 138 MAGIC_DSENTRY_UNLOCK(); 139 #endif 140 141 return entry; 142 } 143 144 /*===========================================================================* 145 * magic_sentry_lookup_by_addr * 146 *===========================================================================*/ 147 PUBLIC struct _magic_sentry *magic_sentry_lookup_by_addr(void *addr, 148 struct _magic_dsentry *dsentry_buff) 149 { 150 int i; 151 struct _magic_sentry *entry = NULL; 152 struct _magic_dsentry *prev_dsentry, *dsentry; 153 struct _magic_sentry *sentry; 154 155 #if MAGIC_LOOKUP_SENTRY_ALLOW_RANGE_INDEX 156 if (magic_sentry_rl_index) { 157 sentry = magic_sentry_lookup_by_range_index(addr, dsentry_buff); 158 if (sentry && sentry->address == addr) { 159 return sentry; 160 } else { 161 return NULL; 162 } 163 } 164 #endif 165 166 /* Scan all the entries and return the one matching the provided address. */ 167 #if MAGIC_LOOKUP_SENTRY 168 if (MAGIC_ADDR_IS_IN_RANGE(addr, magic_sentry_range)) { 169 for (i = 0 ; i < _magic_sentries_num ; i++) { 170 if (_magic_sentries[i].address == addr) { 171 entry = &_magic_sentries[i]; 172 break; 173 } 174 } 175 if (entry) { 176 return entry; 177 } 178 } 179 #endif 180 181 #if MAGIC_LOOKUP_DSENTRY 182 MAGIC_DSENTRY_LOCK(); 183 if (!MAGIC_ADDR_LOOKUP_USE_DSENTRY_RANGES || magic_range_is_dsentry(addr)) { 184 MAGIC_DSENTRY_ALIVE_BLOCK_ITER(_magic_first_dsentry, prev_dsentry, dsentry, sentry, 185 if (sentry->address == addr) { 186 if (dsentry_buff) { 187 magic_copy_dsentry(dsentry, dsentry_buff); 188 entry = MAGIC_DSENTRY_TO_SENTRY(dsentry_buff); 189 } 190 else { 191 entry = sentry; 192 } 193 break; 194 } 195 ); 196 } 197 MAGIC_DSENTRY_UNLOCK(); 198 #endif 199 200 return entry; 201 } 202 203 /*===========================================================================* 204 * magic_sentry_lookup_by_name * 205 *===========================================================================*/ 206 PUBLIC struct _magic_sentry * 207 magic_sentry_lookup_by_name(const char *parent_name, const char *name, 208 _magic_id_t site_id, struct _magic_dsentry *dsentry_buff) 209 { 210 int i; 211 struct _magic_sentry *entry = NULL; 212 struct _magic_dsentry *prev_dsentry, *dsentry; 213 struct _magic_sentry *sentry; 214 215 #if MAGIC_LOOKUP_SENTRY_ALLOW_NAME_HASH 216 if (magic_sentry_hash_head) { 217 return magic_sentry_lookup_by_name_hash(parent_name, name, 218 site_id, dsentry_buff); 219 } 220 #endif 221 222 /* Scan all the entries and return the one matching the provided name. */ 223 #if MAGIC_LOOKUP_SENTRY 224 for (i = 0 ; i < _magic_sentries_num ; i++) { 225 if (!strcmp(_magic_sentries[i].name, name)) { 226 if (!parent_name || 227 !strcmp(MAGIC_SENTRY_PARENT(&_magic_sentries[i]), 228 parent_name)) { 229 if (MAGIC_SENTRY_SITE_ID(&_magic_sentries[i]) == site_id) { 230 entry = &_magic_sentries[i]; 231 break; 232 } 233 } 234 } 235 } 236 if (entry) { 237 return entry; 238 } 239 #endif 240 241 #if MAGIC_LOOKUP_DSENTRY 242 MAGIC_DSENTRY_LOCK(); 243 MAGIC_DSENTRY_ALIVE_ITER(_magic_first_dsentry, prev_dsentry, 244 dsentry, sentry, 245 if (!strcmp(sentry->name, name)) { 246 if (!parent_name || 247 !strcmp(MAGIC_SENTRY_PARENT(sentry), parent_name)) { 248 if (site_id == MAGIC_DSENTRY_SITE_ID_NULL || 249 dsentry->site_id == site_id) { 250 if (dsentry_buff) { 251 magic_copy_dsentry(dsentry, dsentry_buff); 252 entry = MAGIC_DSENTRY_TO_SENTRY(dsentry_buff); 253 } 254 else { 255 entry = sentry; 256 } 257 break; 258 } 259 } 260 } 261 ); 262 MAGIC_DSENTRY_UNLOCK(); 263 #endif 264 265 return entry; 266 } 267 268 /*===========================================================================* 269 * magic_sentry_lookup_by_range * 270 *===========================================================================*/ 271 PUBLIC struct _magic_sentry *magic_sentry_lookup_by_range(void *addr, 272 struct _magic_dsentry *dsentry_buff) 273 { 274 int i; 275 struct _magic_sentry *entry = NULL; 276 struct _magic_dsentry *prev_dsentry, *dsentry; 277 struct _magic_sentry *sentry; 278 void *start_address, *end_address; 279 280 #if MAGIC_LOOKUP_SENTRY_ALLOW_RANGE_INDEX 281 if (magic_sentry_rl_index) { 282 return magic_sentry_lookup_by_range_index(addr, dsentry_buff); 283 } 284 #endif 285 286 /* Scan all the entries and return the one with a valid range. */ 287 #if MAGIC_LOOKUP_SENTRY 288 if (MAGIC_ADDR_IS_IN_RANGE(addr, magic_sentry_range)) { 289 for (i = 0 ; i < _magic_sentries_num ; i++) { 290 start_address = _magic_sentries[i].address; 291 end_address = (void *) (((char *)_magic_sentries[i].address) + 292 _magic_sentries[i].type->size - 1); 293 if (MAGIC_ADDR_IS_WITHIN(addr, start_address, end_address)) { 294 entry = &_magic_sentries[i]; 295 break; 296 } 297 } 298 if (entry) { 299 return entry; 300 } 301 } 302 #endif 303 304 #if MAGIC_LOOKUP_DSENTRY 305 MAGIC_DSENTRY_LOCK(); 306 if (!MAGIC_ADDR_LOOKUP_USE_DSENTRY_RANGES || magic_range_is_dsentry(addr)) { 307 MAGIC_DSENTRY_ALIVE_BLOCK_ITER(_magic_first_dsentry, prev_dsentry, dsentry, sentry, 308 start_address = sentry->address; 309 end_address = (void *) (((char *)sentry->address) + 310 sentry->type->size - 1); 311 if (MAGIC_ADDR_IS_WITHIN(addr, start_address, end_address)) { 312 if (dsentry_buff) { 313 magic_copy_dsentry(dsentry, dsentry_buff); 314 entry = MAGIC_DSENTRY_TO_SENTRY(dsentry_buff); 315 } 316 else { 317 entry = sentry; 318 } 319 break; 320 } 321 ); 322 } 323 MAGIC_DSENTRY_UNLOCK(); 324 #endif 325 326 return entry; 327 } 328 329 /*===========================================================================* 330 * magic_sentry_lookup_by_min_off_by_n * 331 *===========================================================================*/ 332 PUBLIC struct _magic_sentry *magic_sentry_lookup_by_min_off_by_n(void *addr, 333 int flags, long *min_n_ptr, struct _magic_dsentry *dsentry_buff) 334 { 335 int i; 336 struct _magic_sentry *entry = NULL; 337 struct _magic_dsentry *prev_dsentry, *dsentry; 338 struct _magic_sentry *sentry; 339 long n, abs_n, min_n, min_abs_n = LONG_MAX; 340 int has_multiple_min_entries = FALSE; 341 342 /* Scan all the entries and return the one with the minimum off-by-n. */ 343 #if MAGIC_LOOKUP_SENTRY 344 for (i = 0 ; i < _magic_sentries_num ; i++) { 345 n = magic_sentry_get_off_by_n(&_magic_sentries[i], addr, flags); 346 abs_n = MAGIC_ABS(n); 347 if (n == LONG_MAX || abs_n > min_abs_n) { 348 continue; 349 } 350 if (abs_n == min_abs_n) { 351 has_multiple_min_entries = TRUE; 352 } 353 else { 354 min_abs_n = abs_n; 355 min_n = n; 356 has_multiple_min_entries = FALSE; 357 entry = &_magic_sentries[i]; 358 } 359 } 360 #endif 361 362 #if MAGIC_LOOKUP_DSENTRY 363 MAGIC_DSENTRY_LOCK(); 364 MAGIC_DSENTRY_ALIVE_BLOCK_ITER(_magic_first_dsentry, prev_dsentry, dsentry, sentry, 365 n = magic_sentry_get_off_by_n(sentry, addr, flags); 366 abs_n = MAGIC_ABS(n); 367 if (n == LONG_MAX || abs_n > min_abs_n) { 368 continue; 369 } 370 if (abs_n == min_abs_n) { 371 has_multiple_min_entries = TRUE; 372 } 373 else { 374 min_abs_n = abs_n; 375 min_n = n; 376 has_multiple_min_entries = FALSE; 377 if (dsentry_buff) { 378 magic_copy_dsentry(dsentry, dsentry_buff); 379 entry = MAGIC_DSENTRY_TO_SENTRY(dsentry_buff); 380 } 381 else { 382 entry = sentry; 383 } 384 } 385 ); 386 MAGIC_DSENTRY_UNLOCK(); 387 #endif 388 389 if (has_multiple_min_entries && (flags & MAGIC_SENTRY_OFF_BY_N_NO_DUPLICATES)) { 390 entry = NULL; 391 } 392 if (entry && min_n_ptr) { 393 *min_n_ptr = min_n; 394 } 395 return entry; 396 } 397 398 /*===========================================================================* 399 * magic_sentry_lookup_by_string * 400 *===========================================================================*/ 401 PUBLIC struct _magic_sentry *magic_sentry_lookup_by_string(const char *string) 402 { 403 int i; 404 struct _magic_sentry *entry = NULL; 405 406 /* Scan all the string entries and return the matching one. */ 407 #if MAGIC_LOOKUP_SENTRY 408 for(i = 0 ; i < _magic_sentries_num ; i++) { 409 if (MAGIC_STATE_FLAG(&_magic_sentries[i], MAGIC_STATE_STRING) 410 && !strcmp((char *)_magic_sentries[i].address, string)) { 411 entry = &_magic_sentries[i]; 412 break; 413 } 414 } 415 #endif 416 417 return entry; 418 } 419 420 /*===========================================================================* 421 * magic_print_sentry * 422 *===========================================================================*/ 423 PUBLIC void magic_print_sentry(struct _magic_sentry *sentry) 424 { 425 MAGIC_SENTRY_PRINT(sentry, MAGIC_EXPAND_TYPE_STR); 426 } 427 428 /*===========================================================================* 429 * magic_print_sentry_abs_name * 430 *===========================================================================*/ 431 PUBLIC void magic_print_sentry_abs_name(struct _magic_sentry *sentry) 432 { 433 if (!(sentry->flags & MAGIC_STATE_DYNAMIC)) { 434 _magic_printf(sentry->name); 435 } 436 else { 437 struct _magic_dsentry *dsentry = MAGIC_DSENTRY_FROM_SENTRY(sentry); 438 assert(dsentry->parent_name && strcmp(dsentry->parent_name, "")); 439 assert(sentry->name); 440 assert(strcmp(sentry->name, "")); 441 _magic_printf("%lu%s%s%s%s%s" MAGIC_ID_FORMAT, (unsigned long)MAGIC_SENTRY_ID(sentry), 442 MAGIC_DSENTRY_ABS_NAME_SEP, dsentry->parent_name, 443 MAGIC_DSENTRY_ABS_NAME_SEP, sentry->name, 444 MAGIC_DSENTRY_ABS_NAME_SEP, dsentry->site_id); 445 } 446 } 447 448 /*===========================================================================* 449 * magic_print_sentries * 450 *===========================================================================*/ 451 PUBLIC void magic_print_sentries() 452 { 453 int i; 454 struct _magic_sentry* sentry; 455 456 _magic_printf("magic_print_sentries: Printing %d entries\n", _magic_sentries_num); 457 for (i = 0 ; i < _magic_sentries_num ; i++) { 458 sentry = &_magic_sentries[i]; 459 MAGIC_SENTRY_PRINT(sentry, MAGIC_EXPAND_TYPE_STR); 460 _magic_printf("\n"); 461 } 462 } 463 464 /*===========================================================================* 465 * magic_print_nonstr_sentries * 466 *===========================================================================*/ 467 PUBLIC void magic_print_nonstr_sentries() 468 { 469 int i; 470 struct _magic_sentry *sentry; 471 472 _magic_printf("magic_print_nonstr_sentries: Printing %d/%d non-string entries\n", 473 _magic_sentries_num - _magic_sentries_str_num, _magic_sentries_num); 474 for (i = 0 ; i < _magic_sentries_num ; i++) { 475 sentry = &_magic_sentries[i]; 476 if (MAGIC_SENTRY_IS_STRING(sentry)) { 477 continue; 478 } 479 MAGIC_SENTRY_PRINT(sentry, MAGIC_EXPAND_TYPE_STR); 480 _magic_printf("\n"); 481 } 482 } 483 484 /*===========================================================================* 485 * magic_print_str_sentries * 486 *===========================================================================*/ 487 PUBLIC void magic_print_str_sentries() 488 { 489 int i; 490 struct _magic_sentry *sentry; 491 492 _magic_printf("magic_print_str_sentries: Printing %d/%d string entries\n", 493 _magic_sentries_str_num, _magic_sentries_num); 494 for (i = 0 ; i < _magic_sentries_num ; i++) { 495 sentry = &_magic_sentries[i]; 496 if (!MAGIC_SENTRY_IS_STRING(sentry)) { 497 continue; 498 } 499 MAGIC_SENTRY_PRINT(sentry, MAGIC_EXPAND_TYPE_STR); 500 _magic_printf(", string=\"%s\"\n", (char*)sentry->address); 501 } 502 } 503 504 /*===========================================================================* 505 * magic_sentry_rl_alloc * 506 *===========================================================================*/ 507 PRIVATE void *magic_sentry_rl_alloc(int size, UNUSED(void *data)) 508 { 509 void *addr; 510 511 assert(magic_sentry_rl_buff); 512 assert(magic_sentry_rl_buff_offset + size <= magic_sentry_rl_buff_size); 513 514 addr = (char*) magic_sentry_rl_buff + magic_sentry_rl_buff_offset; 515 magic_sentry_rl_buff_offset += size; 516 517 return addr; 518 } 519 520 /*===========================================================================* 521 * magic_sentry_rl_dealloc * 522 *===========================================================================*/ 523 PRIVATE void magic_sentry_rl_dealloc(UNUSED(void *object), UNUSED(void *data)) 524 { 525 return; 526 } 527 528 /*===========================================================================* 529 * magic_sentry_rl_build_index * 530 *===========================================================================*/ 531 PUBLIC void magic_sentry_rl_build_index(void *buff, size_t buff_size) 532 { 533 /* 534 * Warning: this implementation is thread unsafe and also makes 535 * magic_sentry_lookup_by_range thread unsafe! 536 */ 537 int i; 538 struct _magic_dsentry *prev_dsentry, *dsentry; 539 struct _magic_sentry *sentry; 540 void *start_address; 541 splay_tree index; 542 543 assert(buff && buff_size > 0); 544 magic_sentry_rl_buff = buff; 545 magic_sentry_rl_buff_offset = 0; 546 magic_sentry_rl_buff_size = buff_size; 547 index = splay_tree_new_with_allocator( 548 splay_tree_compare_pointers, 549 NULL, NULL, 550 magic_sentry_rl_alloc, magic_sentry_rl_dealloc, 551 NULL); 552 magic_sentry_rl_index = index; 553 assert(magic_sentry_rl_index); 554 555 /* Add all the sentries to the index. */ 556 #if MAGIC_LOOKUP_SENTRY 557 for (i = 0 ; i < _magic_sentries_num ; i++) { 558 start_address = _magic_sentries[i].address; 559 sentry = &_magic_sentries[i]; 560 magic_sentry_rl_insert(start_address, sentry); 561 } 562 #endif 563 564 /* Add all the dsentries to the index. */ 565 #if MAGIC_LOOKUP_DSENTRY 566 MAGIC_DSENTRY_LOCK(); 567 MAGIC_DSENTRY_ALIVE_BLOCK_ITER(_magic_first_dsentry, prev_dsentry, dsentry, sentry, 568 start_address = sentry->address; 569 magic_sentry_rl_insert(start_address, sentry); 570 ); 571 MAGIC_DSENTRY_UNLOCK(); 572 #endif 573 } 574 575 /*===========================================================================* 576 * magic_sentry_rl_destroy_index * 577 *===========================================================================*/ 578 PUBLIC void magic_sentry_rl_destroy_index(void) 579 { 580 magic_sentry_rl_buff = NULL; 581 magic_sentry_rl_buff_offset = 0; 582 magic_sentry_rl_buff_size = 0; 583 magic_sentry_rl_index = NULL; 584 } 585 586 /*===========================================================================* 587 * magic_sentry_rl_estimate_index_buff_size * 588 *===========================================================================*/ 589 PUBLIC size_t magic_sentry_rl_estimate_index_buff_size(int sentries_num) 590 { 591 if (sentries_num == 0) { 592 MAGIC_DSENTRY_ALIVE_BLOCK_NUM(_magic_first_dsentry, &sentries_num); 593 sentries_num += _magic_sentries_num; 594 } 595 596 return (sentries_num * sizeof(struct splay_tree_node_s)) + 597 (sizeof(struct splay_tree_s) * 2); 598 } 599 600 /*===========================================================================* 601 * magic_sentry_rl_count_index_cb * 602 *===========================================================================*/ 603 PRIVATE int magic_sentry_rl_count_index_cb(splay_tree_node node, void *data) 604 { 605 size_t *count = (size_t *) data; 606 607 (*count)++; 608 return 0; 609 } 610 611 /*===========================================================================* 612 * magic_sentry_rl_print_index_cb * 613 *===========================================================================*/ 614 PRIVATE int magic_sentry_rl_print_index_cb(splay_tree_node node, void *data) 615 { 616 _magic_printf("NODE<key, value>: <%08x, %08x>\n", (unsigned int) node->key, 617 (unsigned int) node->value); 618 return 0; 619 } 620 621 /*===========================================================================* 622 * magic_sentry_rl_print_index * 623 *===========================================================================*/ 624 PUBLIC void magic_sentry_rl_print_index(void) 625 { 626 size_t num_nodes = 0; 627 assert(magic_sentry_rl_index); 628 629 splay_tree_foreach((splay_tree) magic_sentry_rl_index, 630 magic_sentry_rl_count_index_cb, &num_nodes); 631 _magic_printf("magic_sentry_rl_print_index: Found %d nodes:\n", num_nodes); 632 splay_tree_foreach((splay_tree) magic_sentry_rl_index, 633 magic_sentry_rl_print_index_cb, NULL); 634 } 635 636 /*===========================================================================* 637 * magic_sentry_rl_lookup * 638 *===========================================================================*/ 639 PUBLIC struct _magic_sentry *magic_sentry_rl_lookup(void *start_addr) 640 { 641 splay_tree_node node; 642 struct _magic_sentry *sentry = NULL; 643 644 node = splay_tree_lookup((splay_tree) magic_sentry_rl_index, 645 (splay_tree_key) start_addr); 646 if (node) { 647 sentry = (struct _magic_sentry*) node->value; 648 } 649 650 return sentry; 651 } 652 653 /*===========================================================================* 654 * magic_sentry_rl_insert * 655 *===========================================================================*/ 656 PUBLIC struct _magic_sentry *magic_sentry_rl_insert(void *start_addr, 657 struct _magic_sentry *sentry) 658 { 659 if (!splay_tree_lookup((splay_tree) magic_sentry_rl_index, 660 (splay_tree_key) start_addr)) { 661 splay_tree_insert((splay_tree) magic_sentry_rl_index, 662 (splay_tree_key) start_addr, 663 (splay_tree_value) sentry); 664 } 665 else { 666 sentry = NULL; 667 } 668 669 return sentry; 670 } 671 672 /*===========================================================================* 673 * magic_sentry_rl_pred_lookup * 674 *===========================================================================*/ 675 PUBLIC struct _magic_sentry *magic_sentry_rl_pred_lookup(void *addr) 676 { 677 splay_tree_node node; 678 struct _magic_sentry *sentry = NULL; 679 680 node = splay_tree_predecessor((splay_tree) magic_sentry_rl_index, 681 (splay_tree_key) addr); 682 if (node) { 683 sentry = (struct _magic_sentry*) node->value; 684 } 685 686 return sentry; 687 } 688 689 /*===========================================================================* 690 * magic_sentry_lookup_by_range_index * 691 *===========================================================================*/ 692 PUBLIC struct _magic_sentry *magic_sentry_lookup_by_range_index( 693 void *addr, struct _magic_dsentry *dsentry_buff) 694 { 695 /* 696 * Warning: this implementation is thread unsafe! 697 */ 698 void *start_address, *end_address; 699 struct _magic_sentry *sentry = 700 magic_sentry_rl_pred_lookup((char *)addr + 1); 701 702 if (sentry) { 703 start_address = sentry->address; 704 end_address = (void *) (((char *)start_address) + 705 sentry->type->size - 1); 706 if (!MAGIC_ADDR_IS_WITHIN(addr, start_address, end_address)) { 707 sentry = NULL; 708 } else { 709 if (MAGIC_STATE_FLAG(sentry, MAGIC_STATE_DYNAMIC) && 710 dsentry_buff != NULL) { 711 magic_copy_dsentry(MAGIC_DSENTRY_FROM_SENTRY(sentry), 712 dsentry_buff); 713 } 714 } 715 } 716 717 return sentry; 718 } 719 720 /*===========================================================================* 721 * magic_sentry_hash_insert * 722 *===========================================================================*/ 723 PRIVATE void magic_sentry_hash_insert(struct _magic_sentry_hash **head, 724 struct _magic_sentry_hash *elem) 725 { 726 if (head != NULL) { 727 struct _magic_sentry_hash *tmp; 728 HASH_FIND_STR(*head, elem->key, tmp); 729 if (tmp) { 730 LL_APPEND(tmp->sentry_list, elem->sentry_list); 731 return; 732 } 733 } 734 /* 735 * **** START UTHASH SPECIFIC DEFINITIONS **** 736 */ 737 #undef uthash_malloc 738 #undef uthash_free 739 #define uthash_malloc(size) magic_sentry_hash_alloc(size) 740 #define uthash_free(addr, size) magic_sentry_hash_dealloc(addr, size) 741 /* 742 * Since we have a limited buffer, we need to stop bucket expansion when 743 * reaching a certain limit. 744 */ 745 #undef uthash_expand_fyi 746 #define uthash_expand_fyi(tbl) \ 747 do { \ 748 if (tbl->num_buckets == MAGIC_SENTRY_NAME_EST_MAX_BUCKETS) { \ 749 _magic_printf("Warning! Sentry name hash maximum bucket number " \ 750 "reached! Consider increasing " \ 751 "MAGIC_SENTRY_NAME_EST_MAX_BUCKETS, unless you are comfortable"\ 752 " with the current performance.\n"); \ 753 tbl->noexpand = 1; \ 754 } \ 755 } while(0); 756 /* 757 * **** FINISH UTHASH SPECIFIC DEFINITIONS **** 758 */ 759 HASH_ADD_STR(*head, key, elem); 760 /* 761 * **** START UTHASH DEFINITION REMOVAL **** 762 */ 763 #undef uthash_malloc 764 #undef uthash_free 765 #undef uthash_expand_fyi 766 /* 767 * **** FINISH UTHASH DEFINITION REMOVAL **** 768 */ 769 } 770 771 /*===========================================================================* 772 * magic_sentry_hash_build * 773 *===========================================================================*/ 774 PUBLIC void magic_sentry_hash_build(void *buff, size_t buff_size) 775 { 776 /* 777 * XXX: 778 * Warning: this implementation is thread unsafe and also makes 779 * magic_sentry_lookup_by_name thread unsafe! 780 */ 781 int i; 782 struct _magic_dsentry *prev_dsentry, *dsentry; 783 struct _magic_sentry *sentry; 784 struct _magic_sentry_hash *sentry_hash, *head; 785 struct _magic_sentry_list *sentry_list; 786 787 assert(buff && buff_size > 0); 788 magic_sentry_hash_buff = buff; 789 magic_sentry_hash_buff_offset = 0; 790 magic_sentry_hash_buff_size = buff_size; 791 792 head = NULL; 793 794 /* Add all the sentries to the hash. */ 795 #if MAGIC_LOOKUP_SENTRY 796 for(i = 0 ; i < _magic_sentries_num ; i++) { 797 sentry_hash = (struct _magic_sentry_hash *) 798 magic_sentry_hash_alloc(sizeof(struct _magic_sentry_hash)); 799 sentry_list = (struct _magic_sentry_list *) 800 magic_sentry_hash_alloc(sizeof(struct _magic_sentry_list)); 801 sentry = &_magic_sentries[i]; 802 MAGIC_SENTRY_TO_HASH_EL(sentry, sentry_hash, sentry_list); 803 magic_sentry_hash_insert(&head, sentry_hash); 804 } 805 #endif 806 807 /* Add all the dsentries to the hash. */ 808 #if MAGIC_LOOKUP_DSENTRY 809 MAGIC_DSENTRY_LOCK(); 810 MAGIC_DSENTRY_ALIVE_ITER(_magic_first_dsentry, prev_dsentry, dsentry, sentry, 811 sentry_hash = (struct _magic_sentry_hash *) 812 magic_sentry_hash_alloc(sizeof(struct _magic_sentry_hash)); 813 sentry_list = (struct _magic_sentry_list *) 814 magic_sentry_hash_alloc(sizeof(struct _magic_sentry_list)); 815 MAGIC_DSENTRY_TO_HASH_EL(dsentry, sentry, sentry_hash, sentry_list); 816 magic_sentry_hash_insert(&head, sentry_hash); 817 ); 818 MAGIC_DSENTRY_UNLOCK(); 819 #endif 820 magic_sentry_hash_head = (void *)head; 821 assert(magic_sentry_hash_head || (!_magic_sentries_num && _magic_first_dsentry == NULL)); 822 } 823 824 /*===========================================================================* 825 * magic_sentry_hash_destroy * 826 *===========================================================================*/ 827 PUBLIC void magic_sentry_hash_destroy(void) 828 { 829 magic_sentry_hash_buff = NULL; 830 magic_sentry_hash_buff_offset = 0; 831 magic_sentry_hash_buff_size = 0; 832 magic_sentry_hash_head = NULL; 833 } 834 835 /*===========================================================================* 836 * magic_sentry_hash_estimate_buff_size * 837 *===========================================================================*/ 838 PUBLIC size_t magic_sentry_hash_estimate_buff_size(int sentries_num) 839 { 840 if (sentries_num == 0) { 841 MAGIC_DSENTRY_ALIVE_NUM(_magic_first_dsentry, &sentries_num); 842 sentries_num += _magic_sentries_num; 843 } 844 845 return (sentries_num * (sizeof(struct _magic_sentry_hash) + 846 sizeof(struct _magic_sentry_list))) + MAGIC_SENTRY_NAME_HASH_OVERHEAD; 847 } 848 849 /*===========================================================================* 850 * magic_sentry_hash_alloc * 851 *===========================================================================*/ 852 PUBLIC void *magic_sentry_hash_alloc(size_t size) 853 { 854 void *addr; 855 856 assert(magic_sentry_hash_buff); 857 assert(magic_sentry_hash_buff_offset + size <= magic_sentry_hash_buff_size); 858 859 addr = (char *) magic_sentry_hash_buff + magic_sentry_hash_buff_offset; 860 magic_sentry_hash_buff_offset += size; 861 862 return addr; 863 } 864 865 /*===========================================================================* 866 * magic_sentry_hash_dealloc * 867 *===========================================================================*/ 868 PUBLIC void magic_sentry_hash_dealloc(UNUSED(void *object), UNUSED(size_t sz)) 869 { 870 return; 871 } 872 873 /*===========================================================================* 874 * magic_sentry_lookup_by_name_hash * 875 *===========================================================================*/ 876 PUBLIC struct _magic_sentry *magic_sentry_lookup_by_name_hash( 877 const char *parent_name, const char *name, _magic_id_t site_id, 878 struct _magic_dsentry *dsentry_buff) 879 { 880 /* 881 * Warning: this implementation is thread unsafe! 882 */ 883 char key[MAGIC_SENTRY_NAME_MAX_KEY_LEN]; 884 struct _magic_sentry_hash *res, *head; 885 key[0] = 0; 886 snprintf(key, sizeof(key), "%s%s%s%s" MAGIC_ID_FORMAT, parent_name, 887 MAGIC_DSENTRY_ABS_NAME_SEP, name, MAGIC_DSENTRY_ABS_NAME_SEP, site_id); 888 head = (struct _magic_sentry_hash *) magic_sentry_hash_head; 889 890 HASH_FIND_STR(head, key, res); 891 if (res == NULL) 892 return NULL; 893 894 return res->sentry_list->sentry; 895 } 896 897 /*===========================================================================* 898 * magic_sentry_list_lookup_by_name_hash * 899 *===========================================================================*/ 900 PUBLIC struct _magic_sentry_list *magic_sentry_list_lookup_by_name_hash( 901 const char *parent_name, const char *name, _magic_id_t site_id, 902 struct _magic_dsentry *dsentry_buff) 903 { 904 /* 905 * Warning: this implementation is thread unsafe! 906 */ 907 char key[MAGIC_SENTRY_NAME_MAX_KEY_LEN]; 908 struct _magic_sentry_hash *res, *head; 909 key[0] = 0; 910 snprintf(key, sizeof(key), "%s%s%s%s" MAGIC_ID_FORMAT, parent_name, 911 MAGIC_DSENTRY_ABS_NAME_SEP, name, MAGIC_DSENTRY_ABS_NAME_SEP, site_id); 912 head = (struct _magic_sentry_hash *) magic_sentry_hash_head; 913 914 HASH_FIND_STR(head, key, res); 915 if (res == NULL) 916 return NULL; 917 918 return res->sentry_list; 919 } 920 921