1 /* radare - LGPL - Copyright 2019-2020 - pancake, thestr4ng3r */
2
3 #include <r_anal.h>
4 #include <r_hash.h>
5 #include <ht_uu.h>
6
7 #include <assert.h>
8
9 #define unwrap(rbnode) container_of (rbnode, RAnalBlock, _rb)
10
__max_end(RBNode * node)11 static void __max_end(RBNode *node) {
12 RAnalBlock *block = unwrap (node);
13 block->_max_end = block->addr + block->size;
14 int i;
15 for (i = 0; i < 2; i++) {
16 if (node->child[i]) {
17 ut64 end = unwrap (node->child[i])->_max_end;
18 if (end > block->_max_end) {
19 block->_max_end = end;
20 }
21 }
22 }
23 }
24
__bb_addr_cmp(const void * incoming,const RBNode * in_tree,void * user)25 static int __bb_addr_cmp(const void *incoming, const RBNode *in_tree, void *user) {
26 ut64 incoming_addr = *(ut64 *)incoming;
27 const RAnalBlock *in_tree_block = container_of (in_tree, const RAnalBlock, _rb);
28 if (incoming_addr < in_tree_block->addr) {
29 return -1;
30 }
31 if (incoming_addr > in_tree_block->addr) {
32 return 1;
33 }
34 return 0;
35 }
36
37 #define D if (anal && anal->verbose)
38
r_anal_block_ref(RAnalBlock * bb)39 R_API void r_anal_block_ref(RAnalBlock *bb) {
40 assert (bb->ref > 0); // 0-refd must already be freed.
41 bb->ref++;
42 }
43
44 #define DFLT_NINSTR 3
45
block_new(RAnal * a,ut64 addr,ut64 size)46 static RAnalBlock *block_new(RAnal *a, ut64 addr, ut64 size) {
47 RAnalBlock *block = R_NEW0 (RAnalBlock);
48 if (!block) {
49 return NULL;
50 }
51 block->addr = addr;
52 block->size = size;
53 block->anal = a;
54 block->ref = 1;
55 block->jump = UT64_MAX;
56 block->fail = UT64_MAX;
57 block->op_pos = R_NEWS0 (ut16, DFLT_NINSTR);
58 block->op_pos_size = DFLT_NINSTR;
59 block->stackptr = 0;
60 block->parent_stackptr = INT_MAX;
61 block->cmpval = UT64_MAX;
62 block->fcns = r_list_new ();
63 if (size) {
64 r_anal_block_update_hash (block);
65 }
66 return block;
67 }
68
block_free(RAnalBlock * block)69 static void block_free(RAnalBlock *block) {
70 if (!block) {
71 return;
72 }
73 r_anal_cond_free (block->cond);
74 free (block->fingerprint);
75 r_anal_diff_free (block->diff);
76 free (block->op_bytes);
77 r_anal_switch_op_free (block->switch_op);
78 r_list_free (block->fcns);
79 free (block->op_pos);
80 free (block->parent_reg_arena);
81 free (block);
82 }
83
__block_free_rb(RBNode * node,void * user)84 void __block_free_rb(RBNode *node, void *user) {
85 RAnalBlock *block = unwrap (node);
86 block_free (block);
87 }
88
r_anal_get_block_at(RAnal * anal,ut64 addr)89 R_API RAnalBlock *r_anal_get_block_at(RAnal *anal, ut64 addr) {
90 RBNode *node = r_rbtree_find (anal->bb_tree, &addr, __bb_addr_cmp, NULL);
91 return node? unwrap (node): NULL;
92 }
93
94 // This is a special case of what r_interval_node_all_in() does
all_in(RAnalBlock * node,ut64 addr,RAnalBlockCb cb,void * user)95 static bool all_in(RAnalBlock *node, ut64 addr, RAnalBlockCb cb, void *user) {
96 while (node && addr < node->addr) {
97 // less than the current node, but might still be contained further down
98 node = unwrap (node->_rb.child[0]);
99 }
100 if (!node) {
101 return true;
102 }
103 if (addr >= node->_max_end) {
104 return true;
105 }
106 if (addr < node->addr + node->size) {
107 if (!cb (node, user)) {
108 return false;
109 }
110 }
111 // This can be done more efficiently by building the stack manually
112 if (!all_in (unwrap (node->_rb.child[0]), addr, cb, user)) {
113 return false;
114 }
115 if (!all_in (unwrap (node->_rb.child[1]), addr, cb, user)) {
116 return false;
117 }
118 return true;
119 }
120
r_anal_blocks_foreach_in(RAnal * anal,ut64 addr,RAnalBlockCb cb,void * user)121 R_API bool r_anal_blocks_foreach_in(RAnal *anal, ut64 addr, RAnalBlockCb cb, void *user) {
122 return all_in (anal->bb_tree ? unwrap (anal->bb_tree) : NULL, addr, cb, user);
123 }
124
block_list_cb(RAnalBlock * block,void * user)125 static bool block_list_cb(RAnalBlock *block, void *user) {
126 RList *list = user;
127 r_anal_block_ref (block);
128 r_list_push (list, block);
129 return true;
130 }
131
r_anal_get_blocks_in(RAnal * anal,ut64 addr)132 R_API RList *r_anal_get_blocks_in(RAnal *anal, ut64 addr) {
133 RList *list = r_list_newf ((RListFree)r_anal_block_unref);
134 if (list) {
135 r_anal_blocks_foreach_in (anal, addr, block_list_cb, list);
136 }
137 return list;
138 }
139
all_intersect(RAnalBlock * node,ut64 addr,ut64 size,RAnalBlockCb cb,void * user)140 static void all_intersect(RAnalBlock *node, ut64 addr, ut64 size, RAnalBlockCb cb, void *user) {
141 ut64 end = addr + size;
142 while (node && end <= node->addr) {
143 // less than the current node, but might still be contained further down
144 node = unwrap (node->_rb.child[0]);
145 }
146 if (!node) {
147 return;
148 }
149 if (addr >= node->_max_end) {
150 return;
151 }
152 if (addr < node->addr + node->size) {
153 cb (node, user);
154 }
155 // This can be done more efficiently by building the stack manually
156 all_intersect (unwrap (node->_rb.child[0]), addr, size, cb, user);
157 all_intersect (unwrap (node->_rb.child[1]), addr, size, cb, user);
158 }
159
r_anal_blocks_foreach_intersect(RAnal * anal,ut64 addr,ut64 size,RAnalBlockCb cb,void * user)160 R_API void r_anal_blocks_foreach_intersect(RAnal *anal, ut64 addr, ut64 size, RAnalBlockCb cb, void *user) {
161 all_intersect (anal->bb_tree ? unwrap (anal->bb_tree) : NULL, addr, size, cb, user);
162 }
163
r_anal_get_blocks_intersect(RAnal * anal,ut64 addr,ut64 size)164 R_API RList *r_anal_get_blocks_intersect(RAnal *anal, ut64 addr, ut64 size) {
165 RList *list = r_list_newf ((RListFree)r_anal_block_unref);
166 if (!list) {
167 return NULL;
168 }
169 r_anal_blocks_foreach_intersect (anal, addr, size, block_list_cb, list);
170 return list;
171 }
172
r_anal_create_block(RAnal * anal,ut64 addr,ut64 size)173 R_API RAnalBlock *r_anal_create_block(RAnal *anal, ut64 addr, ut64 size) {
174 if (r_anal_get_block_at (anal, addr)) {
175 return NULL;
176 }
177 RAnalBlock *block = block_new (anal, addr, size);
178 if (!block) {
179 return NULL;
180 }
181 r_rbtree_aug_insert (&anal->bb_tree, &block->addr, &block->_rb, __bb_addr_cmp, NULL, __max_end);
182 return block;
183 }
184
r_anal_delete_block(RAnalBlock * bb)185 R_API void r_anal_delete_block(RAnalBlock *bb) {
186 r_anal_block_ref (bb);
187 while (!r_list_empty (bb->fcns)) {
188 r_anal_function_remove_block (r_list_first (bb->fcns), bb);
189 }
190 r_anal_block_unref (bb);
191 }
192
r_anal_block_set_size(RAnalBlock * block,ut64 size)193 R_API void r_anal_block_set_size(RAnalBlock *block, ut64 size) {
194 if (block->size == size) {
195 return;
196 }
197
198 // Update the block's function's cached ranges
199 RAnalFunction *fcn;
200 RListIter *iter;
201 r_list_foreach (block->fcns, iter, fcn) {
202 if (fcn->meta._min != UT64_MAX && fcn->meta._max == block->addr + block->size) {
203 fcn->meta._max = block->addr + size;
204 }
205 }
206
207 // Do the actual resize
208 block->size = size;
209 r_rbtree_aug_update_sum (block->anal->bb_tree, &block->addr, &block->_rb, __bb_addr_cmp, NULL, __max_end);
210 }
211
r_anal_block_relocate(RAnalBlock * block,ut64 addr,ut64 size)212 R_API bool r_anal_block_relocate(RAnalBlock *block, ut64 addr, ut64 size) {
213 if (block->addr == addr) {
214 r_anal_block_set_size (block, size);
215 r_anal_block_update_hash (block);
216 return true;
217 }
218 if (r_anal_get_block_at (block->anal, addr)) {
219 // Two blocks at the same addr is illegle you know...
220 return false;
221 }
222
223 // Update the block's function's cached ranges
224 RAnalFunction *fcn;
225 RListIter *iter;
226 r_list_foreach (block->fcns, iter, fcn) {
227 if (fcn->meta._min != UT64_MAX) {
228 if (addr + size > fcn->meta._max) {
229 // we extend after the maximum, so we are the maximum afterwards.
230 fcn->meta._max = addr + size;
231 } else if (block->addr + block->size == fcn->meta._max && addr + size != block->addr + block->size) {
232 // we were the maximum before and may not be it afterwards, not trivial to recalculate.
233 fcn->meta._min = UT64_MAX;
234 continue;
235 }
236 if (block->addr < fcn->meta._min) {
237 // less than the minimum, we know that we are the minimum afterwards.
238 fcn->meta._min = addr;
239 } else if (block->addr == fcn->meta._min && addr != block->addr) {
240 // we were the minimum before and may not be it afterwards, not trivial to recalculate.
241 fcn->meta._min = UT64_MAX;
242 }
243 }
244 }
245
246 r_rbtree_aug_delete (&block->anal->bb_tree, &block->addr, __bb_addr_cmp, NULL, NULL, NULL, __max_end);
247 block->addr = addr;
248 block->size = size;
249 r_anal_block_update_hash (block);
250 r_rbtree_aug_insert (&block->anal->bb_tree, &block->addr, &block->_rb, __bb_addr_cmp, NULL, __max_end);
251 return true;
252 }
253
r_anal_block_split(RAnalBlock * bbi,ut64 addr)254 R_API RAnalBlock *r_anal_block_split(RAnalBlock *bbi, ut64 addr) {
255 RAnal *anal = bbi->anal;
256 r_return_val_if_fail (bbi && addr >= bbi->addr && addr < bbi->addr + bbi->size && addr != UT64_MAX, 0);
257 if (addr == bbi->addr) {
258 r_anal_block_ref (bbi); // ref to be consistent with splitted return refcount
259 return bbi;
260 }
261
262 if (r_anal_get_block_at (bbi->anal, addr)) {
263 // can't have two bbs at the same addr
264 return NULL;
265 }
266
267 // create the second block
268 RAnalBlock *bb = block_new (anal, addr, bbi->addr + bbi->size - addr);
269 if (!bb) {
270 return NULL;
271 }
272 bb->jump = bbi->jump;
273 bb->fail = bbi->fail;
274 bb->parent_stackptr = bbi->stackptr;
275
276 // resize the first block
277 r_anal_block_set_size (bbi, addr - bbi->addr);
278 bbi->jump = addr;
279 bbi->fail = UT64_MAX;
280 r_anal_block_update_hash (bbi);
281
282 // insert the second block into the tree
283 r_rbtree_aug_insert (&anal->bb_tree, &bb->addr, &bb->_rb, __bb_addr_cmp, NULL, __max_end);
284
285 // insert the second block into all functions of the first
286 RListIter *iter;
287 RAnalFunction *fcn;
288 r_list_foreach (bbi->fcns, iter, fcn) {
289 r_anal_function_add_block (fcn, bb);
290 }
291
292 // recalculate offset of instructions in both bb and bbi
293 int i;
294 i = 0;
295 while (i < bbi->ninstr && r_anal_bb_offset_inst (bbi, i) < bbi->size) {
296 i++;
297 }
298 int new_bbi_instr = i;
299 if (bb->addr - bbi->addr == r_anal_bb_offset_inst (bbi, i)) {
300 bb->ninstr = 0;
301 while (i < bbi->ninstr) {
302 ut16 off_op = r_anal_bb_offset_inst (bbi, i);
303 if (off_op >= bbi->size + bb->size) {
304 break;
305 }
306 r_anal_bb_set_offset (bb, bb->ninstr, off_op - bbi->size);
307 bb->ninstr++;
308 i++;
309 }
310 }
311 bbi->ninstr = new_bbi_instr;
312 return bb;
313 }
314
r_anal_block_merge(RAnalBlock * a,RAnalBlock * b)315 R_API bool r_anal_block_merge(RAnalBlock *a, RAnalBlock *b) {
316 if (!r_anal_block_is_contiguous (a, b)) {
317 return false;
318 }
319
320 // check if function lists are identical
321 if (r_list_length (a->fcns) != r_list_length (b->fcns)) {
322 return false;
323 }
324 RAnalFunction *fcn;
325 RListIter *iter;
326 r_list_foreach (a->fcns, iter, fcn) {
327 if (!r_list_contains (b->fcns, fcn)) {
328 return false;
329 }
330 }
331
332 // Keep a ref to b, but remove all references of b from its functions
333 r_anal_block_ref (b);
334 while (!r_list_empty (b->fcns)) {
335 r_anal_function_remove_block (r_list_first (b->fcns), b);
336 }
337
338 // merge ops from b into a
339 size_t i;
340 for (i = 0; i < b->ninstr; i++) {
341 r_anal_bb_set_offset (a, a->ninstr++, a->size + r_anal_bb_offset_inst (b, i));
342 }
343
344 // merge everything else into a
345 a->size += b->size;
346 a->jump = b->jump;
347 a->fail = b->fail;
348 r_anal_block_update_hash (a);
349
350 // kill b completely
351 r_rbtree_aug_delete (&a->anal->bb_tree, &b->addr, __bb_addr_cmp, NULL, __block_free_rb, NULL, __max_end);
352
353 // invalidate ranges of a's functions
354 r_list_foreach (a->fcns, iter, fcn) {
355 fcn->meta._min = UT64_MAX;
356 }
357
358 return true;
359 }
360
r_anal_block_unref(RAnalBlock * bb)361 R_API void r_anal_block_unref(RAnalBlock *bb) {
362 if (!bb) {
363 return;
364 }
365 assert (bb->ref > 0);
366 bb->ref--;
367 assert (bb->ref >= r_list_length (bb->fcns)); // all of the block's functions must hold a reference to it
368 if (bb->ref < 1) {
369 RAnal *anal = bb->anal;
370 assert (!bb->fcns || r_list_empty (bb->fcns));
371 r_rbtree_aug_delete (&anal->bb_tree, &bb->addr, __bb_addr_cmp, NULL, __block_free_rb, NULL, __max_end);
372 }
373 }
374
r_anal_block_successor_addrs_foreach(RAnalBlock * block,RAnalAddrCb cb,void * user)375 R_API bool r_anal_block_successor_addrs_foreach(RAnalBlock *block, RAnalAddrCb cb, void *user) {
376 #define CB_ADDR(addr) do { \
377 if (addr == UT64_MAX) { \
378 break; \
379 } \
380 if (!cb (addr, user)) { \
381 return false; \
382 } \
383 } while(0);
384
385 CB_ADDR (block->jump);
386 CB_ADDR (block->fail);
387 if (block->switch_op && block->switch_op->cases) {
388 RListIter *iter;
389 RAnalCaseOp *caseop;
390 r_list_foreach (block->switch_op->cases, iter, caseop) {
391 CB_ADDR (caseop->jump);
392 }
393 }
394
395 return true;
396 #undef CB_ADDR
397 }
398
399 typedef struct r_anal_block_recurse_context_t {
400 RAnal *anal;
401 RPVector/*<RAnalBlock>*/ to_visit;
402 HtUP *visited;
403 } RAnalBlockRecurseContext;
404
block_recurse_successor_cb(ut64 addr,void * user)405 static bool block_recurse_successor_cb(ut64 addr, void *user) {
406 RAnalBlockRecurseContext *ctx = user;
407 if (ht_up_find_kv (ctx->visited, addr, NULL)) {
408 // already visited
409 return true;
410 }
411 ht_up_insert (ctx->visited, addr, NULL);
412 RAnalBlock *block = r_anal_get_block_at (ctx->anal, addr);
413 if (!block) {
414 return true;
415 }
416 r_pvector_push (&ctx->to_visit, block);
417 return true;
418 }
419
r_anal_block_recurse(RAnalBlock * block,RAnalBlockCb cb,void * user)420 R_API bool r_anal_block_recurse(RAnalBlock *block, RAnalBlockCb cb, void *user) {
421 bool breaked = false;
422 RAnalBlockRecurseContext ctx;
423 ctx.anal = block->anal;
424 r_pvector_init (&ctx.to_visit, NULL);
425 ctx.visited = ht_up_new0 ();
426 if (!ctx.visited) {
427 goto beach;
428 }
429
430 ht_up_insert (ctx.visited, block->addr, NULL);
431 r_pvector_push (&ctx.to_visit, block);
432
433 while (!r_pvector_empty (&ctx.to_visit)) {
434 RAnalBlock *cur = r_pvector_pop (&ctx.to_visit);
435 breaked = !cb (cur, user);
436 if (breaked) {
437 break;
438 }
439 r_anal_block_successor_addrs_foreach (cur, block_recurse_successor_cb, &ctx);
440 }
441
442 beach:
443 ht_up_free (ctx.visited);
444 r_pvector_clear (&ctx.to_visit);
445 return !breaked;
446 }
447
r_anal_block_recurse_followthrough(RAnalBlock * block,RAnalBlockCb cb,void * user)448 R_API bool r_anal_block_recurse_followthrough(RAnalBlock *block, RAnalBlockCb cb, void *user) {
449 bool breaked = false;
450 RAnalBlockRecurseContext ctx;
451 ctx.anal = block->anal;
452 r_pvector_init (&ctx.to_visit, NULL);
453 ctx.visited = ht_up_new0 ();
454 if (!ctx.visited) {
455 goto beach;
456 }
457
458 ht_up_insert (ctx.visited, block->addr, NULL);
459 r_pvector_push (&ctx.to_visit, block);
460
461 while (!r_pvector_empty (&ctx.to_visit)) {
462 RAnalBlock *cur = r_pvector_pop (&ctx.to_visit);
463 bool b = !cb (cur, user);
464 if (b) {
465 breaked = true;
466 } else {
467 r_anal_block_successor_addrs_foreach (cur, block_recurse_successor_cb, &ctx);
468 }
469 }
470
471 beach:
472 ht_up_free (ctx.visited);
473 r_pvector_clear (&ctx.to_visit);
474 return !breaked;
475 }
476
477 typedef struct {
478 RAnalBlock *bb;
479 RListIter *switch_it;
480 } RecurseDepthFirstCtx;
481
r_anal_block_recurse_depth_first(RAnalBlock * block,RAnalBlockCb cb,R_NULLABLE RAnalBlockCb on_exit,void * user)482 R_API bool r_anal_block_recurse_depth_first(RAnalBlock *block, RAnalBlockCb cb, R_NULLABLE RAnalBlockCb on_exit, void *user) {
483 bool breaked = false;
484 HtUP *visited = ht_up_new0 ();
485 if (!visited) {
486 goto beach;
487 }
488 RAnal *anal = block->anal;
489 RVector path;
490 r_vector_init (&path, sizeof (RecurseDepthFirstCtx), NULL, NULL);
491 RAnalBlock *cur_bb = block;
492 RecurseDepthFirstCtx ctx = { cur_bb, NULL };
493 r_vector_push (&path, &ctx);
494 ht_up_insert (visited, cur_bb->addr, NULL);
495 breaked = !cb (cur_bb, user);
496 if (breaked) {
497 goto beach;
498 }
499 do {
500 RecurseDepthFirstCtx *cur_ctx = r_vector_index_ptr (&path, path.len - 1);
501 cur_bb = cur_ctx->bb;
502 if (cur_bb->jump != UT64_MAX && !ht_up_find_kv (visited, cur_bb->jump, NULL)) {
503 cur_bb = r_anal_get_block_at (anal, cur_bb->jump);
504 } else if (cur_bb->fail != UT64_MAX && !ht_up_find_kv (visited, cur_bb->fail, NULL)) {
505 cur_bb = r_anal_get_block_at (anal, cur_bb->fail);
506 } else {
507 RAnalCaseOp *cop = NULL;
508 if (cur_bb->switch_op && !cur_ctx->switch_it) {
509 cur_ctx->switch_it = cur_bb->switch_op->cases->head;
510 cop = r_list_first (cur_bb->switch_op->cases);
511 } else if (cur_ctx->switch_it) {
512 while ((cur_ctx->switch_it = r_list_iter_get_next (cur_ctx->switch_it))) {
513 cop = r_list_iter_get_data (cur_ctx->switch_it);
514 if (!ht_up_find_kv (visited, cop->jump, NULL)) {
515 break;
516 }
517 cop = NULL;
518 }
519 }
520 cur_bb = cop ? r_anal_get_block_at (anal, cop->jump) : NULL;
521 }
522 if (cur_bb) {
523 RecurseDepthFirstCtx ctx = { cur_bb, NULL };
524 r_vector_push (&path, &ctx);
525 ht_up_insert (visited, cur_bb->addr, NULL);
526 bool breaked = !cb (cur_bb, user);
527 if (breaked) {
528 break;
529 }
530 } else {
531 if (on_exit) {
532 on_exit (cur_ctx->bb, user);
533 }
534 r_vector_pop (&path, NULL);
535 }
536 } while (!r_vector_empty (&path));
537
538 beach:
539 ht_up_free (visited);
540 r_vector_clear (&path);
541 return !breaked;
542 }
543
recurse_list_cb(RAnalBlock * block,void * user)544 static bool recurse_list_cb(RAnalBlock *block, void *user) {
545 RList *list = user;
546 r_anal_block_ref (block);
547 r_list_push (list, block);
548 return true;
549 }
550
r_anal_block_recurse_list(RAnalBlock * block)551 R_API RList *r_anal_block_recurse_list(RAnalBlock *block) {
552 RList *ret = r_list_newf ((RListFree)r_anal_block_unref);
553 if (ret) {
554 r_anal_block_recurse (block, recurse_list_cb, ret);
555 }
556 return ret;
557 }
558
r_anal_block_add_switch_case(RAnalBlock * block,ut64 switch_addr,ut64 case_value,ut64 case_addr)559 R_API void r_anal_block_add_switch_case(RAnalBlock *block, ut64 switch_addr, ut64 case_value, ut64 case_addr) {
560 if (!block->switch_op) {
561 block->switch_op = r_anal_switch_op_new (switch_addr, 0, 0, 0);
562 }
563 r_anal_switch_op_add_case (block->switch_op, case_addr, case_value, case_addr);
564 }
565
r_anal_block_op_starts_at(RAnalBlock * bb,ut64 addr)566 R_API bool r_anal_block_op_starts_at(RAnalBlock *bb, ut64 addr) {
567 if (!r_anal_block_contains (bb, addr)) {
568 return false;
569 }
570 ut64 off = addr - bb->addr;
571 if (off > UT16_MAX) {
572 return false;
573 }
574 size_t i;
575 for (i = 0; i < bb->ninstr; i++) {
576 ut16 inst_off = r_anal_bb_offset_inst (bb, i);
577 if (off == inst_off) {
578 return true;
579 }
580 }
581 return false;
582 }
583
584 typedef struct {
585 RAnal *anal;
586 RAnalBlock *cur_parent;
587 ut64 dst;
588 RPVector/*<RAnalBlock>*/ *next_visit; // accumulate block of the next level in the tree
589 HtUP/*<RAnalBlock>*/ *visited; // maps addrs to their previous block (or NULL for entry)
590 } PathContext;
591
shortest_path_successor_cb(ut64 addr,void * user)592 static bool shortest_path_successor_cb(ut64 addr, void *user) {
593 PathContext *ctx = user;
594 if (ht_up_find_kv (ctx->visited, addr, NULL)) {
595 // already visited
596 return true;
597 }
598 ht_up_insert (ctx->visited, addr, ctx->cur_parent);
599 RAnalBlock *block = r_anal_get_block_at (ctx->anal, addr);
600 if (block) {
601 r_pvector_push (ctx->next_visit, block);
602 }
603 return addr != ctx->dst; // break if we found our destination
604 }
605
606
r_anal_block_shortest_path(RAnalBlock * block,ut64 dst)607 R_API R_NULLABLE RList/*<RAnalBlock *>*/ *r_anal_block_shortest_path(RAnalBlock *block, ut64 dst) {
608 RList *ret = NULL;
609 PathContext ctx;
610 ctx.anal = block->anal;
611 ctx.dst = dst;
612
613 // two vectors to swap cur_visit/next_visit
614 RPVector visit_a;
615 r_pvector_init (&visit_a, NULL);
616 RPVector visit_b;
617 r_pvector_init (&visit_b, NULL);
618 ctx.next_visit = &visit_a;
619 RPVector *cur_visit = &visit_b; // cur visit is the current level in the tree
620
621 ctx.visited = ht_up_new0 ();
622 if (!ctx.visited) {
623 goto beach;
624 }
625
626 ht_up_insert (ctx.visited, block->addr, NULL);
627 r_pvector_push (cur_visit, block);
628
629 // BFS
630 while (!r_pvector_empty (cur_visit)) {
631 void **it;
632 r_pvector_foreach (cur_visit, it) {
633 RAnalBlock *cur = *it;
634 ctx.cur_parent = cur;
635 r_anal_block_successor_addrs_foreach (cur, shortest_path_successor_cb, &ctx);
636 }
637 RPVector *tmp = cur_visit;
638 cur_visit = ctx.next_visit;
639 ctx.next_visit = tmp;
640 r_pvector_clear (ctx.next_visit);
641 }
642
643 // reconstruct the path
644 bool found = false;
645 RAnalBlock *prev = ht_up_find (ctx.visited, dst, &found);
646 RAnalBlock *dst_block = r_anal_get_block_at (block->anal, dst);
647 if (found && dst_block) {
648 ret = r_list_newf ((RListFree)r_anal_block_unref);
649 r_anal_block_ref (dst_block);
650 r_list_prepend (ret, dst_block);
651 while (prev) {
652 r_anal_block_ref (prev);
653 r_list_prepend (ret, prev);
654 prev = ht_up_find (ctx.visited, prev->addr, NULL);
655 }
656 }
657
658 beach:
659 ht_up_free (ctx.visited);
660 r_pvector_clear (&visit_a);
661 r_pvector_clear (&visit_b);
662 return ret;
663 }
664
r_anal_block_was_modified(RAnalBlock * block)665 R_API bool r_anal_block_was_modified(RAnalBlock *block) {
666 r_return_val_if_fail (block, false);
667 if (!block->anal->iob.read_at) {
668 return false;
669 }
670 ut8 *buf = malloc (block->size);
671 if (!buf) {
672 return false;
673 }
674 if (!block->anal->iob.read_at (block->anal->iob.io, block->addr, buf, block->size)) {
675 free (buf);
676 return false;
677 }
678 ut32 cur_hash = r_hash_xxhash (buf, block->size);
679 free (buf);
680 return block->bbhash != cur_hash;
681 }
682
r_anal_block_update_hash(RAnalBlock * block)683 R_API void r_anal_block_update_hash(RAnalBlock *block) {
684 r_return_if_fail (block);
685 if (!block->anal->iob.read_at) {
686 return;
687 }
688 ut8 *buf = malloc (block->size);
689 if (!buf) {
690 return;
691 }
692 if (!block->anal->iob.read_at (block->anal->iob.io, block->addr, buf, block->size)) {
693 free (buf);
694 return;
695 }
696 block->bbhash = r_hash_xxhash (buf, block->size);
697 free (buf);
698 }
699
700 typedef struct {
701 RAnalBlock *block;
702 bool reachable;
703 } NoreturnSuccessor;
704
noreturn_successor_free(HtUPKv * kv)705 static void noreturn_successor_free(HtUPKv *kv) {
706 NoreturnSuccessor *succ = kv->value;
707 r_anal_block_unref (succ->block);
708 free (succ);
709 }
710
noreturn_successors_cb(RAnalBlock * block,void * user)711 static bool noreturn_successors_cb(RAnalBlock *block, void *user) {
712 HtUP *succs = user;
713 NoreturnSuccessor *succ = R_NEW0 (NoreturnSuccessor);
714 if (!succ) {
715 return false;
716 }
717 r_anal_block_ref (block);
718 succ->block = block;
719 succ->reachable = false; // reset for first iteration
720 ht_up_insert (succs, block->addr, succ);
721 return true;
722 }
723
noreturn_successors_reachable_cb(RAnalBlock * block,void * user)724 static bool noreturn_successors_reachable_cb(RAnalBlock *block, void *user) {
725 HtUP *succs = user;
726 NoreturnSuccessor *succ = ht_up_find (succs, block->addr, NULL);
727 if (succ) {
728 succ->reachable = true;
729 }
730 return true;
731 }
732
noreturn_remove_unreachable_cb(void * user,const ut64 k,const void * v)733 static bool noreturn_remove_unreachable_cb(void *user, const ut64 k, const void *v) {
734 RAnalFunction *fcn = user;
735 NoreturnSuccessor *succ = (NoreturnSuccessor *)v;
736 if (!succ->reachable && r_list_contains (succ->block->fcns, fcn)) {
737 r_anal_function_remove_block (fcn, succ->block);
738 }
739 succ->reachable = false; // reset for next iteration
740 return true;
741 }
742
noreturn_get_blocks_cb(void * user,const ut64 k,const void * v)743 static bool noreturn_get_blocks_cb(void *user, const ut64 k, const void *v) {
744 RList *blocks = user;
745 NoreturnSuccessor *succ = (NoreturnSuccessor *)v;
746 r_anal_block_ref (succ->block);
747 r_list_push (blocks, succ->block);
748 return true;
749 }
750
r_anal_block_chop_noreturn(RAnalBlock * block,ut64 addr)751 R_API RAnalBlock *r_anal_block_chop_noreturn(RAnalBlock *block, ut64 addr) {
752 r_return_val_if_fail (block, NULL);
753 if (!r_anal_block_contains (block, addr) || addr == block->addr) {
754 return block;
755 }
756 r_anal_block_ref (block);
757
758 // Cache all recursive successors of block here.
759 // These are the candidates that we might have to remove from functions later.
760 HtUP *succs = ht_up_new (NULL, noreturn_successor_free, NULL); // maps block addr (ut64) => NoreturnSuccessor *
761 if (!succs) {
762 return block;
763 }
764 r_anal_block_recurse (block, noreturn_successors_cb, succs);
765
766 // Chop the block. Resize and remove all destination addrs
767 r_anal_block_set_size (block, addr - block->addr);
768 r_anal_block_update_hash (block);
769 block->jump = UT64_MAX;
770 block->fail = UT64_MAX;
771 r_anal_switch_op_free (block->switch_op);
772 block->switch_op = NULL;
773
774 // Now, for each fcn, check which of our successors are still reachable in the function remove and the ones that are not.
775 RListIter *it;
776 RAnalFunction *fcn;
777 // We need to clone the list because block->fcns will get modified in the loop
778 RList *fcns_cpy = r_list_clone (block->fcns);
779 r_list_foreach (fcns_cpy, it, fcn) {
780 RAnalBlock *entry = r_anal_get_block_at (block->anal, fcn->addr);
781 if (entry && r_list_contains (entry->fcns, fcn)) {
782 r_anal_block_recurse (entry, noreturn_successors_reachable_cb, succs);
783 }
784 ht_up_foreach (succs, noreturn_remove_unreachable_cb, fcn);
785 }
786 r_list_free (fcns_cpy);
787
788 // This last step isn't really critical, but nice to have.
789 // Prepare to merge blocks with their predecessors if possible
790 RList merge_blocks;
791 r_list_init (&merge_blocks);
792 merge_blocks.free = (RListFree)r_anal_block_unref;
793 ht_up_foreach (succs, noreturn_get_blocks_cb, &merge_blocks);
794
795 // Free/unref BEFORE doing the merge!
796 // Some of the blocks might not be valid anymore later!
797 r_anal_block_unref (block);
798 ht_up_free (succs);
799
800 ut64 block_addr = block->addr; // save the addr to identify the block. the automerge might free it so we must not use the pointer!
801
802 // Do the actual merge
803 r_anal_block_automerge (&merge_blocks);
804
805 // No try to recover the pointer to the block if it still exists
806 RAnalBlock *ret = NULL;
807 for (it = merge_blocks.head; it && (block = it->data, 1); it = it->n) {
808 if (block->addr == block_addr) {
809 // block is still there
810 ret = block;
811 break;
812 }
813 }
814
815 r_list_purge (&merge_blocks);
816 return ret;
817 }
818
819 typedef struct {
820 HtUP *predecessors; // maps a block to its predecessor if it has exactly one, or NULL if there are multiple or the predecessor has multiple successors
821 HtUP *visited_blocks; // during predecessor search, mark blocks whose successors we already checked. Value is void *-casted count of successors
822 HtUP *blocks; // adresses of the blocks we might want to merge with their predecessors => RAnalBlock *
823
824 RAnalBlock *cur_pred;
825 size_t cur_succ_count;
826 } AutomergeCtx;
827
count_successors_cb(ut64 addr,void * user)828 static bool count_successors_cb(ut64 addr, void *user) {
829 AutomergeCtx *ctx = user;
830 ctx->cur_succ_count++;
831 return true;
832 }
833
automerge_predecessor_successor_cb(ut64 addr,void * user)834 static bool automerge_predecessor_successor_cb(ut64 addr, void *user) {
835 AutomergeCtx *ctx = user;
836 ctx->cur_succ_count++;
837 RAnalBlock *block = ht_up_find (ctx->blocks, addr, NULL);
838 if (!block) {
839 // we shouldn't merge this one so GL_DONT_CARE
840 return true;
841 }
842 bool found;
843 RAnalBlock *pred = ht_up_find (ctx->predecessors, (ut64)(size_t)block, &found);
844 if (found) {
845 if (pred) {
846 // only one predecessor found so far, but we are the second so there are multiple now
847 ht_up_update (ctx->predecessors, (ut64)(size_t) block, NULL);
848 } // else: already found multiple predecessors, nothing to do
849 } else {
850 // no predecessor found yet, this is the only one until now
851 ht_up_insert (ctx->predecessors, (ut64)(size_t) block, ctx->cur_pred);
852 }
853 return true;
854 }
855
automerge_get_predecessors_cb(void * user,ut64 k)856 static bool automerge_get_predecessors_cb(void *user, ut64 k) {
857 AutomergeCtx *ctx = user;
858 const RAnalFunction *fcn = (const RAnalFunction *)(size_t)k;
859 RListIter *it;
860 RAnalBlock *block;
861 r_list_foreach (fcn->bbs, it, block) {
862 bool already_visited;
863 ht_up_find (ctx->visited_blocks, (ut64)(size_t)block, &already_visited);
864 if (already_visited) {
865 continue;
866 }
867 ctx->cur_pred = block;
868 ctx->cur_succ_count = 0;
869 r_anal_block_successor_addrs_foreach (block, automerge_predecessor_successor_cb, ctx);
870 ht_up_insert (ctx->visited_blocks, (ut64)(size_t)block, (void *)ctx->cur_succ_count);
871 }
872 return true;
873 }
874
875 // Try to find the contiguous predecessors of all given blocks and merge them if possible,
876 // i.e. if there are no other blocks that have this block as one of their successors
r_anal_block_automerge(RList * blocks)877 R_API void r_anal_block_automerge(RList *blocks) {
878 r_return_if_fail (blocks);
879 AutomergeCtx ctx = {
880 .predecessors = ht_up_new0 (),
881 .visited_blocks = ht_up_new0 (),
882 .blocks = ht_up_new0 ()
883 };
884
885 SetU *relevant_fcns = set_u_new ();
886 RList *fixup_candidates = r_list_new (); // used further down
887 if (!ctx.predecessors || !ctx.visited_blocks || !ctx.blocks || !relevant_fcns || !fixup_candidates) {
888 goto beach;
889 }
890
891 // Get all the functions and prepare ctx.blocks
892 RListIter *it;
893 RAnalBlock *block;
894 r_list_foreach (blocks, it, block) {
895 RListIter *fit;
896 RAnalFunction *fcn;
897 r_list_foreach (block->fcns, fit, fcn) {
898 set_u_add (relevant_fcns, (ut64)(size_t)fcn);
899 }
900 ht_up_insert (ctx.blocks, block->addr, block);
901 }
902
903 // Get the single predecessors we might want to merge with
904 set_u_foreach (relevant_fcns, automerge_get_predecessors_cb, &ctx);
905
906 // Now finally do the merging
907 RListIter *tmp;
908 r_list_foreach_safe (blocks, it, tmp, block) {
909 RAnalBlock *predecessor = ht_up_find (ctx.predecessors, (ut64)(size_t)block, NULL);
910 if (!predecessor) {
911 continue;
912 }
913 size_t pred_succs_count = (size_t)ht_up_find (ctx.visited_blocks, (ut64)(size_t)predecessor, NULL);
914 if (pred_succs_count != 1) {
915 // we can only merge this predecessor if it has exactly one successor
916 continue;
917 }
918
919 // We are about to merge block into predecessor
920 // However if there are other blocks that have block as the predecessor,
921 // we would uaf after the merge since block will be freed.
922 RListIter *bit;
923 RAnalBlock *clock;
924 for (bit = it->n; bit && (clock = bit->data, 1); bit = bit->n) {
925 RAnalBlock *fixup_pred = ht_up_find (ctx.predecessors, (ut64)(size_t)clock, NULL);
926 if (fixup_pred == block) {
927 r_list_push (fixup_candidates, clock);
928 }
929 }
930
931 if (r_anal_block_merge (predecessor, block)) { // r_anal_block_merge() does checks like contiguous, to that's fine
932 // block was merged into predecessor, it is now freed!
933 // Update number of successors of the predecessor
934 ctx.cur_succ_count = 0;
935 r_anal_block_successor_addrs_foreach (predecessor, count_successors_cb, &ctx);
936 ht_up_update (ctx.visited_blocks, (ut64)(size_t)predecessor, (void *)ctx.cur_succ_count);
937 r_list_foreach (fixup_candidates, bit, clock) {
938 // Make sure all previous pointers to block now go to predecessor
939 ht_up_update (ctx.predecessors, (ut64)(size_t)clock, predecessor);
940 }
941 // Remove it from the list
942 r_list_split_iter (blocks, it);
943 free (it);
944 }
945
946 r_list_purge (fixup_candidates);
947 }
948
949 beach:
950 ht_up_free (ctx.predecessors);
951 ht_up_free (ctx.visited_blocks);
952 ht_up_free (ctx.blocks);
953 set_u_free (relevant_fcns);
954 r_list_free (fixup_candidates);
955 }
956