minix/lib/libmagicrt/magic_sentry.c

   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