1 #include <r_types.h>
2 #include <r_util.h>
3 #include <r_anal.h>
4
5 /* shared internal state of the subgraph generating functions */
6
7 typedef struct esil_cfg_generator_t {
8 RAnalEsil *esil;
9 union {
10 RStack *ifelse;
11 RStack *vals;
12 };
13 // union for semantic purposes
14 RContRBTree *blocks;
15 // consider moving this to cfg? well, yes and no.
16 // making Graph nodes fast available in RAnalEsilCFG is great idea
17 // A balanced tree is only best solution, if we want to store and lookup intervals
18 // We need to look for intervals, so that we can resolve goto destinations INSIDE of a cpu-instruction
19 // After an instruction got graphed, we only need their entry node (nodes with first == {xxx, 0 })
20 // So after graphing an instruction, the blocks-tree should be cleared (don't free the content)
21 // and nodes with first == {xxx, 0} should be stored in an sdb or similar in cfg, with xxx as key
22 RAnalEsilCFG *cfg;
23 RGraphNode *cur;
24 // current graph-node, so that I don't have to abuse cfg->start
25 RIDStorage *atoms;
26 // is this needed
27 ut64 off;
28 // is this needed
29 } EsilCfgGen;
30
31 // esil has support for multiple elses,
32 // so we need these cookies on the ifelse-stack to keep track of things:
33 // when entering an if-block the parent is set as the else_block
34 // when entering an else block it is set as else_block, if is_else is false, other wise as if_block
35 // when entering an else block is_else flips
36 typedef struct esil_cfg_scope_cookie_t {
37 RGraphNode *if_block;
38 RGraphNode *else_block;
39 bool is_else;
40 } EsilCfgScopeCookie;
41
42 typedef enum {
43 ESIL_VAL_CONST,
44 ESIL_VAL_REG,
45 ESIL_VAL_RESULT
46 } EsilValType;
47
48 typedef struct esil_value_t {
49 ut64 val; //should be a union, but for goto-analysis ut64 is fine
50 EsilValType type;
51 } EsilVal;
52
53 /* HELPERS */
54
condrets_strtok(char * str,const char tok)55 static char *condrets_strtok(char *str, const char tok) {
56 if (!str) {
57 return NULL;
58 }
59 ut32 i = 0;
60 while (1 == 1) {
61 if (!str[i]) {
62 break;
63 }
64 if (str[i] == tok) {
65 str[i] = '\0';
66 return &str[i + 1];
67 }
68 i++;
69 }
70 return NULL;
71 }
72
esil_get_op(RAnalEsil * esil,const char * op)73 RAnalEsilOp *esil_get_op (RAnalEsil *esil, const char *op) {
74 r_return_val_if_fail (R_STR_ISNOTEMPTY (op) && esil && esil->ops, NULL);
75 return ht_pp_find (esil->ops, op, NULL);
76 }
77
78 // this little thot atomizes an esil expressions by splitting it on ','
esil_expr_atomize(RIDStorage * atoms,char * expr)79 static void esil_expr_atomize(RIDStorage *atoms, char *expr) {
80 ut32 forget_me;
81 for (
82 ; !!expr && r_id_storage_add (atoms, expr, &forget_me);
83 expr = condrets_strtok (expr, ',')) {
84 }
85 }
86
_free_bb_cb(void * data)87 static void _free_bb_cb(void *data) {
88 RAnalEsilBB *bb = (RAnalEsilBB *)data;
89 free (bb->expr);
90 free (bb);
91 }
92
93 // REMINDER: generating the block content needs to prepend setting the program counter
94 // r_anal_esil_cfg_op does this ^, use it whenever generating cfg from op
95
96 // this nasty function is an insert-compare for RGraphNodes that contain RAnalEsilBB
_graphnode_esilbb_insert_cmp(void * incoming,void * in,void * user)97 static int _graphnode_esilbb_insert_cmp(void *incoming, void *in, void *user) {
98 RGraphNode *incoming_gnode = (RGraphNode *)incoming;
99 RGraphNode *in_gnode = (RGraphNode *)in;
100 RAnalEsilBB *incoming_bb = (RAnalEsilBB *)incoming_gnode->data;
101 RAnalEsilBB *in_bb = (RAnalEsilBB *)in_gnode->data;
102
103 // RAnalEsilBBs have the nice property, that they cannot intersect,
104 // so just comparing first and first should be fine for inserting
105 #if 0
106 return incoming_bb->first - in_bb->first;
107 #endif
108 // We MUST NOT use direct subtraction here, since st64 vs st32 can break the tree
109 // be careful and check by compares
110 if (incoming_bb->first.off < in_bb->first.off) {
111 return -1;
112 }
113 if (incoming_bb->first.off > in_bb->first.off) {
114 return 1;
115 }
116 // ok, so upper 64 msb are equal, now use the lower 16 lsb
117 return incoming_bb->first.idx - in_bb->first.idx;
118 }
119
_graphnode_esilbb_find_cmp(void * incoming,void * in,void * user)120 static int _graphnode_esilbb_find_cmp(void *incoming, void *in, void *user) {
121 RAnalEsilEOffset *find_me = (RAnalEsilEOffset *)incoming;
122 RGraphNode *in_gnode = (RGraphNode *)in;
123 RAnalEsilBB *in_bb = (RAnalEsilBB *)in_gnode->data;
124 // not sure if this is needed that way
125 if (find_me->off < in_bb->first.off) {
126 return -1;
127 }
128 if (find_me->off > in_bb->last.off) {
129 return 1;
130 }
131 if (find_me->idx < in_bb->first.idx) {
132 return -1;
133 }
134 if (find_me->idx > in_bb->last.idx) {
135 return 1;
136 }
137 return 0;
138 }
139
_graphnode_delete_always_0_cmp(void * incoming,void * in,void * user)140 static int _graphnode_delete_always_0_cmp(void *incoming, void *in, void *user) {
141 EsilCfgGen *gen = (EsilCfgGen *)user;
142 RGraphNode *delete_me = (RGraphNode *)in;
143 RAnalEsilBB *delete_me_bb = (RAnalEsilBB *)delete_me->data;
144 r_graph_del_node (gen->cfg->g, delete_me);
145 ut32 id;
146 for (id = delete_me_bb->first.idx; id <= delete_me_bb->last.idx; id++) {
147 r_id_storage_delete (gen->atoms, id);
148 }
149 return 0;
150 }
151
_handle_if_enter(EsilCfgGen * gen,ut32 id,const bool has_next)152 void _handle_if_enter (EsilCfgGen *gen, ut32 id, const bool has_next) {
153 if (!has_next) {
154 return;
155 }
156 // TODO: check allocation here
157 EsilCfgScopeCookie *cookie = R_NEW0 (EsilCfgScopeCookie);
158
159 // get current bb
160 // RAnalEsilBB *bb = (RAnalEsilBB *)gen->cur->data;
161
162 // create if-enter-bb
163 RAnalEsilBB *entered_bb = R_NEW0 (RAnalEsilBB);
164 entered_bb->first.off = entered_bb->last.off = gen->off;
165 entered_bb->first.idx = entered_bb->last.idx = id + 1;
166 entered_bb->enter = R_ANAL_ESIL_BLOCK_ENTER_TRUE;
167
168 // create if-entered-graph-node
169 RGraphNode *entered_node = r_graph_add_node (gen->cfg->g, entered_bb);
170 entered_node->free = _free_bb_cb;
171 r_rbtree_cont_insert (gen->blocks, entered_node, _graphnode_esilbb_insert_cmp, NULL);
172
173 // add edge from entering node to entered node
174 r_graph_add_edge (gen->cfg->g, gen->cur, entered_node);
175
176 // push scope-cookie
177 cookie->if_block = entered_node;
178 cookie->else_block = gen->cur;
179 r_stack_push (gen->ifelse, cookie);
180 gen->cur = entered_node;
181 }
182
_handle_else_enter(EsilCfgGen * gen,ut32 id,const bool has_next)183 void _handle_else_enter (EsilCfgGen *gen, ut32 id, const bool has_next) {
184 if (!has_next || r_stack_is_empty (gen->ifelse)) {
185 // no cookie no todo
186 return;
187 }
188 EsilCfgScopeCookie *cookie = (EsilCfgScopeCookie *)r_stack_peek (gen->ifelse);
189
190 // create if-enter-bb
191 RAnalEsilBB *entered_bb = R_NEW0 (RAnalEsilBB);
192 entered_bb->first.off = entered_bb->last.off = gen->off;
193 entered_bb->first.idx = entered_bb->last.idx = id + 1;
194
195 // create if-entered-graph-node
196 RGraphNode *entered_node = r_graph_add_node (gen->cfg->g, entered_bb);
197 entered_node->free = _free_bb_cb;
198 r_rbtree_cont_insert (gen->blocks, entered_node, _graphnode_esilbb_insert_cmp, NULL);
199
200 if (cookie->is_else) {
201 entered_bb->enter = R_ANAL_ESIL_BLOCK_ENTER_TRUE;
202 r_graph_add_edge (gen->cfg->g, cookie->if_block, entered_node);
203 cookie->if_block = entered_node;
204 cookie->else_block = gen->cur;
205 cookie->is_else = false;
206 } else {
207 entered_bb->enter = R_ANAL_ESIL_BLOCK_ENTER_FALSE;
208 r_graph_add_edge (gen->cfg->g, cookie->else_block, entered_node);
209 cookie->else_block = entered_node;
210 cookie->if_block = gen->cur;
211 cookie->is_else = true;
212 }
213 gen->cur = entered_node;
214 }
215
_handle_fi_leave(EsilCfgGen * gen,ut32 id,const bool has_next)216 void _handle_fi_leave (EsilCfgGen *gen, ut32 id, const bool has_next) {
217 EsilCfgScopeCookie *cookie = r_stack_pop (gen->ifelse);
218 if (!cookie) {
219 // no if, no fi todo
220 return;
221 }
222
223 RAnalEsilBB *cur_bb = (RAnalEsilBB *)gen->cur->data;
224 // this block is not executed when the if or else block is empty
225 if (memcmp (&cur_bb->first, &cur_bb->last, sizeof (RAnalEsilEOffset))) {
226 // TODO: add some thoughts in comments here
227 cur_bb->last.idx--;
228 RAnalEsilBB *leaving_bb = R_NEW0 (RAnalEsilBB);
229 leaving_bb->first.off = leaving_bb->last.off = gen->off;
230 leaving_bb->first.idx = leaving_bb->last.idx = id;
231 RGraphNode *leaving_node = r_graph_add_node (gen->cfg->g, leaving_bb);
232 leaving_node->free = _free_bb_cb;
233 r_graph_add_edge (gen->cfg->g, gen->cur, leaving_node);
234 r_rbtree_cont_insert (gen->blocks, leaving_node, _graphnode_esilbb_insert_cmp, NULL);
235 gen->cur = leaving_node;
236 }
237 r_graph_add_edge (gen->cfg->g, cookie->is_else ? cookie->if_block : cookie->else_block, gen->cur);
238 free (cookie);
239 }
240
241 // this function handles '?{','}{’ and '}'
242 // return type should probably be a bool, but idk
_handle_control_flow_ifelsefi(EsilCfgGen * gen,char * atom,ut32 id)243 void _handle_control_flow_ifelsefi (EsilCfgGen *gen, char *atom, ut32 id) {
244 // we're probably going to see more ?{ and }, than }{
245 // so checking against ?{ and } befor }{ is therefor better for perf (lololol)
246 if (!strcmp (atom, "?{")) {
247 _handle_if_enter (gen, id, !!r_id_storage_get (gen->atoms, id + 1));
248 return;
249 }
250 if (!strcmp (atom, "}")) {
251 _handle_fi_leave (gen, id, !!r_id_storage_get (gen->atoms, id + 1));
252 return;
253 }
254 if (!strcmp (atom, "}{")) {
255 _handle_else_enter (gen, id, !!r_id_storage_get (gen->atoms, id + 1));
256 }
257 }
258
259 // this little function is expected to generate a subgraph with most nodes in it
260 // but not all edges. It's expected to handle if, else and fi
_round_0_cb(void * user,void * data,ut32 id)261 bool _round_0_cb (void *user, void *data, ut32 id) {
262 EsilCfgGen *gen = (EsilCfgGen *)user;
263 char *atom = (char *)data;
264 RAnalEsilBB *bb = (RAnalEsilBB *)gen->cur->data;
265 RAnalEsilOp *op = esil_get_op (gen->esil, atom);
266 bb->last.idx = (ut16)id;
267 if (op && op->type == R_ANAL_ESIL_OP_TYPE_CONTROL_FLOW) {
268 _handle_control_flow_ifelsefi (gen, atom, id);
269 }
270 return true;
271 }
272
_common_break_goto(EsilCfgGen * gen,ut32 id)273 RGraphNode *_common_break_goto (EsilCfgGen *gen, ut32 id) {
274 RAnalEsilEOffset off = { gen->off, (ut16)id };
275 RGraphNode *gnode = r_rbtree_cont_find (gen->blocks, &off, _graphnode_esilbb_find_cmp, NULL);
276 RAnalEsilBB *bb = (RAnalEsilBB *)gnode->data;
277 if (id != bb->last.idx) {
278 RAnalEsilBB *next_bb = R_NEW0 (RAnalEsilBB);
279 // split blocks
280 next_bb->first.off = gen->off;
281 next_bb->first.idx = id + 1;
282 next_bb->last = bb->last;
283 bb->last.idx = id;
284 RGraphNode *next_gnode = r_graph_node_split_forward (gen->cfg->g, gnode, next_bb);
285 // TODO: implement node_split in graph api
286 r_rbtree_cont_insert (gen->blocks, next_gnode, _graphnode_esilbb_insert_cmp, NULL);
287 } else {
288 RListIter *iter, *ator;
289 RGraphNode *node;
290 // TODO: improve perf here
291 r_list_foreach_safe (gnode->out_nodes, iter, ator, node) {
292 r_graph_del_edge (gen->cfg->g, gnode, node);
293 }
294 }
295 return gnode;
296 // r_graph_add_edge(gen->cfg->g, gnode, gen->cfg->end);
297 }
298
_handle_break(EsilCfgGen * gen,ut32 id)299 void _handle_break (EsilCfgGen *gen, ut32 id) {
300 r_graph_add_edge (gen->cfg->g, _common_break_goto (gen, id), gen->cfg->end);
301 }
302
_handle_goto(EsilCfgGen * gen,ut32 idx)303 void _handle_goto (EsilCfgGen *gen, ut32 idx) {
304 RGraphNode *gnode = _common_break_goto (gen, idx);
305 RAnalEsilBB *bb = (RAnalEsilBB *)gnode->data;
306 // so what we're doing here is emulating this block with a certain degree of abstraction:
307 // no reg-access
308 // no io-access
309 // stack-movents
310 // maybe arithmetic stack operations
311 //
312 // we need to figure out the goto destination
313 // ex: "a,b,=,12,GOTO" => goto dst is 12
314 // ex: "42,a,4,+,b,=,GOTO" => goto dst is 42
315 //
316 // TODO: also handle "2,14,+,GOTO" in later versions
317 ut16 id;
318 // bb->last.idx is the GOTO operation itself, we do not reach this in the loop
319 for (id = bb->first.idx; id < bb->last.idx; id++) {
320 char *atom = (char *)r_id_storage_get (gen->atoms, (ut32)id);
321 RAnalEsilOp *op = esil_get_op (gen->esil, atom);
322 if (op) {
323 ut32 j;
324 for (j = 0; j < op->pop; j++) {
325 free (r_stack_pop (gen->vals));
326 }
327 for (j = 0; j < op->push; j++) {
328 EsilVal *val = R_NEW (EsilVal);
329 val->type = ESIL_VAL_RESULT;
330 r_stack_push (gen->vals, val);
331 }
332 } else {
333 EsilVal *val = R_NEW (EsilVal);
334 if (r_reg_get (gen->esil->anal->reg, atom, -1)) {
335 val->type = ESIL_VAL_REG;
336 } else {
337 val->type = ESIL_VAL_CONST;
338 val->val = r_num_get (NULL, atom);
339 }
340 r_stack_push (gen->vals, val);
341 }
342 }
343 EsilVal *v = r_stack_pop (gen->vals);
344 if (!v || v->type != ESIL_VAL_CONST) {
345 free (v);
346 eprintf ("Cannot resolve GOTO dst :(\n");
347 goto beach;
348 }
349
350 // get the node to the corresponding GOTO destination
351 RAnalEsilEOffset dst_off = { gen->off, (ut16)v->val };
352 RGraphNode *dst_node = r_rbtree_cont_find (gen->blocks, &dst_off, _graphnode_esilbb_find_cmp, NULL);
353 if (!dst_node) {
354 // out-of-bounds
355 // check if this works
356 dst_node = gen->cfg->end;
357 } else {
358 RAnalEsilBB *dst_bb = (RAnalEsilBB *)dst_node->data;
359 if (dst_bb->first.idx != v->val) {
360 RAnalEsilBB *split_bb = R_NEW0 (RAnalEsilBB);
361 split_bb[0] = dst_bb[0];
362 dst_bb->last.idx = v->val - 1;
363 split_bb->first.idx = v->val;
364 RGraphNode *split = r_graph_node_split_forward (gen->cfg->g, dst_node, split_bb);
365 r_graph_add_edge (gen->cfg->g, dst_node, split);
366 dst_node = split;
367 }
368 }
369
370 r_graph_add_edge (gen->cfg->g, gnode, dst_node);
371 beach:
372 while (!r_stack_is_empty (gen->vals)) {
373 free (r_stack_pop (gen->vals));
374 }
375 }
376
_round_1_cb(void * user,void * data,ut32 id)377 bool _round_1_cb (void *user, void *data, ut32 id) {
378 EsilCfgGen *gen = (EsilCfgGen *)user;
379 char *atom = (char *)data;
380 RAnalEsilOp *op = esil_get_op (gen->esil, atom);
381 if (op && op->type == R_ANAL_ESIL_OP_TYPE_CONTROL_FLOW) {
382 if (!strcmp ("BREAK", atom)) {
383 _handle_break (gen, id);
384 }
385 if (!strcmp ("GOTO", atom)) {
386 _handle_goto (gen, id);
387 }
388 }
389 return true;
390 }
391
_round_2_cb(RGraphNode * n,RGraphVisitor * vi)392 void _round_2_cb (RGraphNode *n, RGraphVisitor *vi) {
393 RAnalEsilBB *bb = (RAnalEsilBB *)n->data;
394 EsilCfgGen *gen = (EsilCfgGen *)vi->data;
395 RStrBuf *buf = r_strbuf_new ((char *)r_id_storage_get (gen->atoms, bb->first.idx));
396 r_strbuf_append (buf, ",");
397 ut32 id;
398 for (id = bb->first.idx + 1; id <= bb->last.idx; id++) {
399 // use r_id_storage_take here to start fini for the atoms
400 r_strbuf_appendf (buf, "%s,", (char *)r_id_storage_take (gen->atoms, id));
401 }
402 bb->expr = strdup (r_strbuf_get (buf));
403 r_strbuf_free (buf);
404 r_rbtree_cont_delete (gen->blocks, n, _graphnode_esilbb_insert_cmp, NULL);
405 }
406
407 // this function takes a cfg, an offset and an esil expression
408 // concatinates to already existing graph.
409 // Also expects RIDStorage atoms and RContRBTree to be allocate in prior of the call
esil_cfg_gen(RAnalEsilCFG * cfg,RAnal * anal,RIDStorage * atoms,RContRBTree * blocks,RStack * stack,ut64 off,char * expr)410 static RAnalEsilCFG *esil_cfg_gen(RAnalEsilCFG *cfg, RAnal *anal, RIDStorage *atoms, RContRBTree *blocks, RStack *stack, ut64 off, char *expr) {
411 // consider expr as RStrBuf, so that we can sanitze broken esil
412 // (ex: "b,a,+=,$z,zf,:=,7,$c,cf,:=,zf,?{,1,b,+=,cf,?{,3,a,-=" =>
413 // "b,a,+=,$z,zf,:=,7,$c,cf,:=,zf,?{,1,b,+=,cf,?{,3,a,-=,},}")
414
415 // allocate some stuff
416 char *_expr = strdup (expr);
417 if (!_expr) {
418 return cfg; //NULL?
419 }
420 RAnalEsilBB *end_bb = R_NEW0 (RAnalEsilBB);
421 if (!end_bb) {
422 free (_expr);
423 return cfg;
424 }
425 RGraphNode *start, *end = r_graph_add_node (cfg->g, end_bb);
426 if (!end) {
427 free (end_bb);
428 free (_expr);
429 return cfg;
430 }
431 end->free = _free_bb_cb;
432
433 esil_expr_atomize (atoms, _expr);
434
435 // previous expression's post-dominator is the current expression starting point
436 //
437 // MUST NOT use cfg->start as starting point of subgraph,
438 // since it marks the start of the whole graph
439 //
440 // cpu-instruction starts at this node
441 //
442 // without information about the outside cfg, we CANNOT merge cpu-instructions
443
444 RAnalEsilBB *bb = (RAnalEsilBB *)cfg->end->data;
445
446 end_bb->expr = bb->expr;
447 // FIXME: use end_bb here
448 bb->expr = NULL;
449 bb->first.off = bb->last.off = off;
450 bb->first.idx = bb->last.idx = 0;
451 start = cfg->end;
452
453 EsilCfgGen gen = { anal->esil, { stack }, blocks, cfg, start, atoms, off };
454 cfg->end = end;
455 // create an edge from cur to end?
456 // Well yes, but no. Would be great to do this,
457 // but rgraph api is slow af on node delition. Be careful instead
458
459 // We created a new graph node above, which is going to be the post-dominator
460 // of the subgraph, that we are going to add to the existing graph.
461 // The post-dominator of the previous added subgraph is the starting node here.
462 // We add this to the block-tree
463 r_rbtree_cont_insert (blocks, gen.cur, _graphnode_esilbb_insert_cmp, NULL);
464
465 // end of the initial setup, next generate blocks and insert them in the tree
466
467 // round 0 adds a subgraph from if, else and fi
468 r_id_storage_foreach (atoms, _round_0_cb, &gen);
469 // make cfg->end effective post-dominator
470 r_graph_add_edge (cfg->g, gen.cur, cfg->end);
471 {
472 // stack unwinding
473 EsilCfgScopeCookie *cookie;
474 while ((cookie = r_stack_pop (stack))) {
475 r_graph_add_edge (cfg->g,
476 cookie->is_else ? cookie->if_block : cookie->else_block, cfg->end);
477 free (cookie);
478 }
479 }
480
481 // next do round 1: split blocks from GOTOs and BREAKs
482 r_id_storage_foreach (atoms, _round_1_cb, &gen);
483
484 // next do dfs:
485 // - remove each node from blocks-tree, that can be reached by a dfs path
486 // - when removing a node from block-tree, synthesize node->bb->expr with RStrBuf
487 {
488 // dfs walk removes used atoms
489 RGraphVisitor vi = { _round_2_cb, NULL, NULL, NULL, NULL, &gen };
490 r_graph_dfs_node (cfg->g, start, &vi);
491 }
492 // this loop removes unused atoms
493 do {
494 } while (blocks->root && r_rbtree_cont_delete (blocks, NULL, _graphnode_delete_always_0_cmp, &gen));
495
496 free (_expr);
497 return cfg;
498 }
499
r_anal_esil_cfg_new(void)500 R_API RAnalEsilCFG *r_anal_esil_cfg_new(void) {
501 RAnalEsilCFG *cf = R_NEW0 (RAnalEsilCFG);
502 if (cf) {
503 RAnalEsilBB *p = R_NEW0 (RAnalEsilBB);
504 if (!p) {
505 free (cf);
506 return NULL;
507 }
508 p->expr = strdup ("end");
509 if (!p->expr) {
510 free (p);
511 free (cf);
512 return NULL;
513 }
514 cf->g = r_graph_new ();
515 if (!cf->g) {
516 free (p->expr);
517 free (p);
518 free (cf);
519 return NULL;
520 }
521 cf->start = cf->end = r_graph_add_node (cf->g, p);
522 // end node is always needed as post-dominator
523 // idea here is to split the initial one node graph in the node
524 if (!cf->end) {
525 free (p->expr);
526 free (p);
527 r_graph_free (cf->g);
528 free (cf);
529 return NULL;
530 }
531 if (cf->g->nodes) {
532 cf->end->free = _free_bb_cb;
533 }
534 }
535 return cf;
536 }
537
538 // this little function takes a cfg, an offset and an esil expression
539 // concatinates to already existing graph
r_anal_esil_cfg_expr(RAnalEsilCFG * cfg,RAnal * anal,const ut64 off,char * expr)540 R_API RAnalEsilCFG *r_anal_esil_cfg_expr(RAnalEsilCFG *cfg, RAnal *anal, const ut64 off, char *expr) {
541 if (!anal || !anal->esil) {
542 return NULL;
543 }
544 RStack *stack = r_stack_new (4);
545 if (!stack) {
546 return NULL;
547 }
548 RContRBTree *blocks = r_rbtree_cont_new ();
549 if (!blocks) {
550 r_stack_free (stack);
551 return NULL;
552 }
553 RIDStorage *atoms = r_id_storage_new (0, 0xfffe);
554 if (!atoms) {
555 r_stack_free (stack);
556 r_rbtree_cont_free (blocks);
557 return NULL;
558 }
559 RAnalEsilCFG *cf = cfg ? cfg : r_anal_esil_cfg_new ();
560 if (!cf) {
561 r_stack_free (stack);
562 r_id_storage_free (atoms);
563 r_rbtree_cont_free (blocks);
564 return NULL;
565 }
566 RAnalEsilCFG *ret = esil_cfg_gen (cf, anal, atoms, blocks, stack, off, expr);
567 r_stack_free (stack);
568 r_id_storage_free (atoms);
569 r_rbtree_cont_free (blocks);
570 return ret;
571 }
572
r_anal_esil_cfg_op(RAnalEsilCFG * cfg,RAnal * anal,RAnalOp * op)573 R_API RAnalEsilCFG *r_anal_esil_cfg_op(RAnalEsilCFG *cfg, RAnal *anal, RAnalOp *op) {
574 if (!op || !anal || !anal->reg || !anal->esil) {
575 return NULL;
576 }
577 RAnalEsilBB *glue_bb = R_NEW0 (RAnalEsilBB);
578 if (!glue_bb) {
579 eprintf ("Couldn't allocate glue_bb\n");
580 return NULL;
581 }
582 RStrBuf *glue = r_strbuf_new ("");
583 if (!glue) {
584 free (glue_bb);
585 eprintf ("Couldn't allocate glue\n");
586 return NULL;
587 }
588 const char *pc = r_reg_get_name (anal->reg, R_REG_NAME_PC);
589 r_strbuf_setf (glue, "0x%" PFMT64x ",%s,:=,", op->addr + op->size, pc);
590 glue_bb->expr = strdup (r_strbuf_get (glue));
591 r_strbuf_free (glue);
592 if (!glue_bb->expr) {
593 free (glue_bb);
594 eprintf ("Couldn't strdup\n");
595 return NULL;
596 }
597 glue_bb->enter = R_ANAL_ESIL_BLOCK_ENTER_GLUE;
598 glue_bb->first.off = glue_bb->last.off = op->addr;
599 glue_bb->first.idx = glue_bb->last.idx = 0;
600
601 RAnalEsilCFG *ret;
602
603 if (!cfg) {
604 ret = r_anal_esil_cfg_expr (cfg, anal, op->addr, r_strbuf_get (&op->esil));
605 RGraphNode *glue_node = r_graph_add_node (ret->g, glue_bb);
606 glue_node->free = _free_bb_cb;
607 r_graph_add_edge (ret->g, glue_node, ret->start);
608 ret->start = glue_node;
609 } else {
610 RGraphNode *glue_node = r_graph_add_node (cfg->g, glue_bb);
611 glue_node->free = _free_bb_cb;
612 r_graph_add_edge (cfg->g, cfg->end, glue_node);
613 void *foo = cfg->end->data;
614 cfg->end->data = glue_node->data;
615 glue_node->data = foo;
616 cfg->end = glue_node;
617 ret = r_anal_esil_cfg_expr (cfg, anal, op->addr, r_strbuf_get (&op->esil));
618 }
619 return ret;
620 }
621
merge_2_blocks(RAnalEsilCFG * cfg,RGraphNode * node,RGraphNode * block)622 static void merge_2_blocks(RAnalEsilCFG *cfg, RGraphNode *node, RGraphNode *block) {
623 // merge node and block, block dies in this
624 // block----->node ===> node
625 if (node == cfg->end) {
626 // do not merge the post-dominator
627 return;
628 }
629 RListIter *iter;
630 RGraphNode *n;
631 r_list_foreach (block->in_nodes, iter, n) {
632 r_graph_add_edge (cfg->g, n, node);
633 }
634 RAnalEsilBB *block_bb, *node_bb = (RAnalEsilBB *)node->data;
635 block_bb = (RAnalEsilBB *)block->data;
636 if ((block_bb->enter == R_ANAL_ESIL_BLOCK_ENTER_TRUE) || (block_bb->enter == R_ANAL_ESIL_BLOCK_ENTER_FALSE)) {
637 node_bb->enter = block_bb->enter;
638 } else {
639 node_bb->enter = R_ANAL_ESIL_BLOCK_ENTER_NORMAL;
640 }
641 RStrBuf *buf = r_strbuf_new (block_bb->expr);
642 node_bb->first = block_bb->first;
643 r_graph_del_node (cfg->g, block);
644 r_strbuf_appendf (buf, "\n%s", node_bb->expr);
645 free (node_bb->expr);
646 node_bb->expr = strdup (r_strbuf_get (buf));
647 if (block == cfg->start) {
648 cfg->start = node;
649 }
650 }
651
652 // this shit is slow af, bc of foolish graph api
r_anal_esil_cfg_merge_blocks(RAnalEsilCFG * cfg)653 R_API void r_anal_esil_cfg_merge_blocks(RAnalEsilCFG *cfg) {
654 if (!cfg || !cfg->g || !cfg->g->nodes) {
655 return;
656 }
657 RListIter *iter, *ator;
658 RGraphNode *node;
659 r_list_foreach_safe (cfg->g->nodes, iter, ator, node) {
660 if (r_list_length (node->in_nodes) == 1) {
661 RAnalEsilBB *bb = (RAnalEsilBB *)node->data;
662 RGraphNode *top = (RGraphNode *)r_list_get_top (node->out_nodes);
663 // segfaults here ?
664 if (!(top && bb->enter == R_ANAL_ESIL_BLOCK_ENTER_GLUE && (r_list_length (top->in_nodes) > 1))) {
665 RGraphNode *block = (RGraphNode *)r_list_get_top (node->in_nodes);
666 if (r_list_length (block->out_nodes) == 1) {
667 merge_2_blocks (cfg, node, block);
668 }
669 }
670 }
671 }
672 }
673
r_anal_esil_cfg_free(RAnalEsilCFG * cfg)674 R_API void r_anal_esil_cfg_free(RAnalEsilCFG *cfg) {
675 if (cfg && cfg->g) {
676 r_graph_free (cfg->g);
677 }
678 free (cfg);
679 }
680