1 #include <magic_sentry.h>
2 #include <magic_splay_tree.h>
3
4 /*===========================================================================*
5 * magic_sentry_get_off_by_n *
6 *===========================================================================*/
magic_sentry_get_off_by_n(struct _magic_sentry * sentry,void * addr,int flags)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 *===========================================================================*/
magic_do_check_sentry(struct _magic_sentry * sentry)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 *===========================================================================*/
magic_check_sentry(struct _magic_sentry * sentry)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 *===========================================================================*/
magic_check_sentries()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 *===========================================================================*/
magic_sentry_lookup_by_id(_magic_id_t id,struct _magic_dsentry * dsentry_buff)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 *===========================================================================*/
magic_sentry_lookup_by_addr(void * addr,struct _magic_dsentry * dsentry_buff)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 *
magic_sentry_lookup_by_name(const char * parent_name,const char * name,_magic_id_t site_id,struct _magic_dsentry * dsentry_buff)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 *===========================================================================*/
magic_sentry_lookup_by_range(void * addr,struct _magic_dsentry * dsentry_buff)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 *===========================================================================*/
magic_sentry_lookup_by_min_off_by_n(void * addr,int flags,long * min_n_ptr,struct _magic_dsentry * dsentry_buff)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 *===========================================================================*/
magic_sentry_lookup_by_string(const char * string)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 *===========================================================================*/
magic_print_sentry(struct _magic_sentry * sentry)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 *===========================================================================*/
magic_print_sentry_abs_name(struct _magic_sentry * sentry)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 *===========================================================================*/
magic_print_sentries()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 *===========================================================================*/
magic_print_nonstr_sentries()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 *===========================================================================*/
magic_print_str_sentries()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 *===========================================================================*/
magic_sentry_rl_alloc(int size,UNUSED (void * data))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 *===========================================================================*/
magic_sentry_rl_dealloc(UNUSED (void * object),UNUSED (void * data))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 *===========================================================================*/
magic_sentry_rl_build_index(void * buff,size_t buff_size)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 *===========================================================================*/
magic_sentry_rl_destroy_index(void)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 *===========================================================================*/
magic_sentry_rl_estimate_index_buff_size(int sentries_num)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 *===========================================================================*/
magic_sentry_rl_count_index_cb(splay_tree_node node,void * data)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 *===========================================================================*/
magic_sentry_rl_print_index_cb(splay_tree_node node,void * data)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 *===========================================================================*/
magic_sentry_rl_print_index(void)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 *===========================================================================*/
magic_sentry_rl_lookup(void * start_addr)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 *===========================================================================*/
magic_sentry_rl_insert(void * start_addr,struct _magic_sentry * sentry)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 *===========================================================================*/
magic_sentry_rl_pred_lookup(void * addr)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 *===========================================================================*/
magic_sentry_lookup_by_range_index(void * addr,struct _magic_dsentry * dsentry_buff)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 *===========================================================================*/
magic_sentry_hash_insert(struct _magic_sentry_hash ** head,struct _magic_sentry_hash * elem)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 *===========================================================================*/
magic_sentry_hash_build(void * buff,size_t buff_size)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 *===========================================================================*/
magic_sentry_hash_destroy(void)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 *===========================================================================*/
magic_sentry_hash_estimate_buff_size(int sentries_num)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 *===========================================================================*/
magic_sentry_hash_alloc(size_t size)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 *===========================================================================*/
magic_sentry_hash_dealloc(UNUSED (void * object),UNUSED (size_t sz))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 *===========================================================================*/
magic_sentry_lookup_by_name_hash(const char * parent_name,const char * name,_magic_id_t site_id,struct _magic_dsentry * dsentry_buff)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 *===========================================================================*/
magic_sentry_list_lookup_by_name_hash(const char * parent_name,const char * name,_magic_id_t site_id,struct _magic_dsentry * dsentry_buff)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