1 // This is free and unencumbered software released into the public domain.
3 // Anyone is free to copy, modify, publish, use, compile, sell, or
4 // distribute this software, either in source code form or as a compiled
5 // binary, for any purpose, commercial or non-commercial, and by any
8 // In jurisdictions that recognize copyright laws, the author or authors
9 // of this software dedicate any and all copyright interest in the
10 // software to the public domain. We make this dedication for the benefit
11 // of the public at large and to the detriment of our heirs and
12 // successors. We intend this dedication to be an overt act of
13 // relinquishment in perpetuity of all present and future rights to this
14 // software under copyright law.
16 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19 // IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
20 // OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21 // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22 // OTHER DEALINGS IN THE SOFTWARE.
24 // For more information, please refer to <http://unlicense.org/>
26 /* based on example code: https://github.com/sheredom/llvm_bc_parsing_example
27 * which came under the above (un-)license. does not depend on any FRR
28 * pieces, so no reason to change the license.
30 * please note that while included in the FRR sources, this tool is in no way
31 * supported or maintained by the FRR community. it is provided as a
32 * "convenience"; while it worked at some point (using LLVM 8 / 9), it may
33 * easily break with a future LLVM version or any other factors.
35 * 2020-05-04, David Lamparter
47 #include <llvm-c/BitReader.h>
48 #include <llvm-c/BitWriter.h>
49 #include <llvm-c/Core.h>
51 #include <json-c/json.h>
53 /* if you want to use this without the special FRRouting defines,
54 * remove the following #define
58 static void dbgloc_add(struct json_object
*jsobj
, LLVMValueRef obj
)
60 unsigned file_len
= 0;
61 const char *file
= LLVMGetDebugLocFilename(obj
, &file_len
);
62 unsigned line
= LLVMGetDebugLocLine(obj
);
65 file
= "???", file_len
= 3;
66 else if (file
[0] == '.' && file
[1] == '/')
67 file
+= 2, file_len
-= 2;
69 json_object_object_add(jsobj
, "filename",
70 json_object_new_string_len(file
, file_len
));
71 json_object_object_add(jsobj
, "line", json_object_new_int64(line
));
74 static struct json_object
*js_get_or_make(struct json_object
*parent
,
76 struct json_object
*(*maker
)(void))
78 struct json_object
*ret
;
80 ret
= json_object_object_get(parent
, key
);
84 json_object_object_add(parent
, key
, ret
);
88 static bool details_fptr_vars
= false;
89 static bool details_fptr_consts
= true;
98 static void walk_const_fptrs(struct json_object
*js_call
, LLVMValueRef value
,
99 const char *prefix
, bool *hdr_written
)
104 if (LLVMIsAGlobalVariable(value
)) {
105 type
= LLVMGlobalGetValueType(value
);
106 value
= LLVMGetInitializer(value
);
108 type
= LLVMTypeOf(value
);
111 if (LLVMIsAFunction(value
)) {
112 struct json_object
*js_fptrs
;
114 js_fptrs
= js_get_or_make(js_call
, "funcptrs",
115 json_object_new_array
);
118 const char *fn_name
= LLVMGetValueName2(value
, &fn_len
);
120 size_t curlen
= json_object_array_length(js_fptrs
);
121 struct json_object
*jsobj
;
124 for (size_t i
= 0; i
< curlen
; i
++) {
125 jsobj
= json_object_array_get_idx(js_fptrs
, i
);
126 s
= json_object_get_string(jsobj
);
128 if (s
&& !strcmp(s
, fn_name
))
132 if (details_fptr_consts
&& !*hdr_written
) {
134 "%s: calls function pointer from constant or global data\n",
138 if (details_fptr_consts
)
139 fprintf(stderr
, "%s- constant: %.*s()\n",
140 prefix
, (int)fn_len
, fn_name
);
142 json_object_array_add(js_fptrs
,
143 json_object_new_string_len(fn_name
,
148 kind
= LLVMGetValueKind(value
);
154 case LLVMUndefValueValueKind
:
155 case LLVMConstantAggregateZeroValueKind
:
156 case LLVMConstantPointerNullValueKind
:
157 /* null pointer / array - ignore */
160 case LLVMConstantIntValueKind
:
161 /* integer - ignore */
164 case LLVMConstantStructValueKind
:
165 len
= LLVMCountStructElementTypes(type
);
166 for (unsigned i
= 0; i
< len
; i
++)
167 walk_const_fptrs(js_call
, LLVMGetOperand(value
, i
),
168 prefix
, hdr_written
);
171 case LLVMConstantArrayValueKind
:
172 len
= LLVMGetArrayLength(type
);
173 for (unsigned i
= 0; i
< len
; i
++)
174 walk_const_fptrs(js_call
, LLVMGetOperand(value
, i
),
175 prefix
, hdr_written
);
179 /* to help the user / development */
182 "%s: calls function pointer from constant or global data\n",
186 dump
= LLVMPrintValueToString(value
);
188 "%s- value could not be processed:\n"
189 "%s- [kind=%d] %s\n",
190 prefix
, prefix
, kind
, dump
);
191 LLVMDisposeMessage(dump
);
198 static bool is_thread_sched(const char *name
, size_t len
)
200 #define thread_prefix "funcname_"
201 static const char *const names
[] = {
202 thread_prefix
"thread_add_read_write",
203 thread_prefix
"thread_add_timer",
204 thread_prefix
"thread_add_timer_msec",
205 thread_prefix
"thread_add_timer_tv",
206 thread_prefix
"thread_add_event",
207 thread_prefix
"thread_execute",
211 for (i
= 0; i
< sizeof(names
) / sizeof(names
[0]); i
++) {
212 if (strlen(names
[i
]) != len
)
214 if (!memcmp(names
[i
], name
, len
))
221 static void process_call(struct json_object
*js_calls
,
222 struct json_object
*js_special
,
224 LLVMValueRef function
)
226 struct json_object
*js_call
, *js_fptrs
= NULL
;
228 LLVMValueRef called
= LLVMGetCalledValue(instr
);
230 if (LLVMIsAConstantExpr(called
)) {
231 LLVMOpcode opcode
= LLVMGetConstOpcode(called
);
233 if (opcode
== LLVMBitCast
) {
234 LLVMValueRef op0
= LLVMGetOperand(called
, 0);
236 if (LLVMIsAFunction(op0
))
241 size_t called_len
= 0;
242 const char *called_name
= LLVMGetValueName2(called
, &called_len
);
243 unsigned n_args
= LLVMGetNumArgOperands(instr
);
245 bool is_external
= LLVMIsDeclaration(called
);
246 enum called_fn called_type
= FN_GENERIC
;
248 js_call
= json_object_new_object();
249 json_object_array_add(js_calls
, js_call
);
250 dbgloc_add(js_call
, instr
);
251 json_object_object_add(js_call
, "is_external",
252 json_object_new_boolean(is_external
));
254 if (!called_name
|| called_len
== 0) {
255 called_type
= FN_NONAME
;
256 json_object_object_add(js_call
, "type",
257 json_object_new_string("indirect"));
259 LLVMValueRef last
= called
;
262 const char *name_c
= LLVMGetValueName2(function
, &name_len
);
265 /* information for FRR hooks is dumped for the registration
266 * in _hook_typecheck; we can safely ignore the funcptr here
268 if (strncmp(name_c
, "hook_call_", 10) == 0)
272 unsigned file_len
= 0;
273 const char *file
= LLVMGetDebugLocFilename(instr
, &file_len
);
274 unsigned line
= LLVMGetDebugLocLine(instr
);
277 snprintf(prefix
, sizeof(prefix
), "%.*s:%d:%.*s()",
278 (int)file_len
, file
, line
, (int)name_len
, name_c
);
280 while (LLVMIsALoadInst(last
) || LLVMIsAGetElementPtrInst(last
))
281 /* skipping over details for GEP here, but meh. */
282 last
= LLVMGetOperand(last
, 0);
284 if (LLVMIsAAllocaInst(last
)) {
285 /* "alloca" is just generically all variables on the
286 * stack, this does not refer to C alloca() calls
288 * looking at the control flow in the function can
289 * give better results here, it's just not implemented
293 "%s: call to a function pointer variable\n",
296 if (details_fptr_vars
) {
297 char *dump
= LLVMPrintValueToString(called
);
298 printf("%s- %s\n", prefix
, dump
);
299 LLVMDisposeMessage(dump
);
302 json_object_object_add(
304 json_object_new_string("stack_fptr"));
305 } else if (LLVMIsACallInst(last
)) {
306 /* calling the a function pointer returned from
309 struct json_object
*js_indirect
;
311 js_indirect
= js_get_or_make(js_call
, "return_of",
312 json_object_new_array
);
314 process_call(js_indirect
, js_special
, last
, function
);
315 } else if (LLVMIsAConstant(last
)) {
316 /* function pointer is a constant (includes loading
317 * from complicated constants like structs or arrays.)
319 bool hdr_written
= false;
320 walk_const_fptrs(js_call
, last
, prefix
, &hdr_written
);
321 if (details_fptr_consts
&& !hdr_written
)
323 "%s: calls function pointer from constant or global data, but no non-NULL function pointers found\n",
326 char *dump
= LLVMPrintValueToString(called
);
327 printf("\t%s\n", dump
);
328 LLVMDisposeMessage(dump
);
332 } else if (!strcmp(called_name
, "install_element")) {
333 called_type
= FN_INSTALL_ELEMENT
;
335 LLVMValueRef param0
= LLVMGetOperand(instr
, 0);
336 if (!LLVMIsAConstantInt(param0
))
339 long long vty_node
= LLVMConstIntGetSExtValue(param0
);
340 json_object_object_add(js_call
, "vty_node",
341 json_object_new_int64(vty_node
));
343 LLVMValueRef param1
= LLVMGetOperand(instr
, 1);
344 if (!LLVMIsAGlobalVariable(param1
))
347 LLVMValueRef intlz
= LLVMGetInitializer(param1
);
348 assert(intlz
&& LLVMIsConstant(intlz
));
350 LLVMValueKind intlzkind
= LLVMGetValueKind(intlz
);
351 assert(intlzkind
== LLVMConstantStructValueKind
);
353 LLVMValueRef funcptr
= LLVMGetOperand(intlz
, 4);
354 assert(LLVMIsAFunction(funcptr
));
356 size_t target_len
= 0;
358 target
= LLVMGetValueName2(funcptr
, &target_len
);
360 json_object_object_add(
362 json_object_new_string("install_element"));
363 json_object_object_add(
365 json_object_new_string_len(target
, target_len
));
369 json_object_object_add(
371 json_object_new_string("install_element"));
373 } else if (is_thread_sched(called_name
, called_len
)) {
374 called_type
= FN_THREAD_ADD
;
376 json_object_object_add(js_call
, "type",
377 json_object_new_string("thread_sched"));
378 json_object_object_add(
380 json_object_new_string_len(called_name
, called_len
));
383 if (strstr(called_name
, "_read_"))
384 fparam
= LLVMGetOperand(instr
, 2);
386 fparam
= LLVMGetOperand(instr
, 1);
389 size_t target_len
= 0;
391 target
= LLVMGetValueName2(fparam
, &target_len
);
393 json_object_object_add(js_call
, "target",
395 json_object_new_string_len(target
, target_len
));
396 if (!LLVMIsAFunction(fparam
))
397 json_object_object_add(js_call
, "target_unresolved",
398 json_object_new_boolean(true));
400 } else if (!strncmp(called_name
, "_hook_typecheck_",
401 strlen("_hook_typecheck_"))) {
402 struct json_object
*js_hook
, *js_this
;
403 const char *hook_name
;
405 hook_name
= called_name
+ strlen("_hook_typecheck_");
407 json_object_object_add(js_call
, "type",
408 json_object_new_string("hook"));
410 LLVMValueRef param0
= LLVMGetOperand(instr
, 0);
411 if (!LLVMIsAFunction(param0
))
414 size_t target_len
= 0;
416 target
= LLVMGetValueName2(param0
, &target_len
);
418 js_hook
= js_get_or_make(js_special
, "hooks",
419 json_object_new_object
);
420 js_hook
= js_get_or_make(js_hook
, hook_name
,
421 json_object_new_array
);
423 js_this
= json_object_new_object();
424 json_object_array_add(js_hook
, js_this
);
426 dbgloc_add(js_this
, instr
);
427 json_object_object_add(
429 json_object_new_string_len(target
, target_len
));
432 /* TODO (FRR specifics):
433 * - workqueues - not sure we can do much there
436 #endif /* FRR_SPECIFIC */
438 json_object_object_add(
440 json_object_new_string_len(called_name
, called_len
));
443 for (unsigned argno
= 0; argno
< n_args
; argno
++) {
444 LLVMValueRef param
= LLVMGetOperand(instr
, argno
);
446 const char *target_name
;
448 if (LLVMIsAFunction(param
)) {
449 js_fptrs
= js_get_or_make(js_call
, "funcptrs",
450 json_object_new_array
);
452 target_name
= LLVMGetValueName2(param
, &target_len
);
454 json_object_array_add(js_fptrs
,
455 json_object_new_string_len(
456 target_name
, target_len
));
461 static void process_fn(struct json_object
*funcs
,
462 struct json_object
*js_special
,
463 LLVMValueRef function
)
465 struct json_object
*js_func
, *js_calls
;
468 const char *name_c
= LLVMGetValueName2(function
, &name_len
);
471 name
= strndup(name_c
, name_len
);
473 js_func
= json_object_object_get(funcs
, name
);
475 unsigned file_len
= 0;
476 const char *file
= LLVMGetDebugLocFilename(function
, &file_len
);
477 unsigned line
= LLVMGetDebugLocLine(function
);
479 fprintf(stderr
, "%.*s:%d:%s(): duplicate definition!\n",
480 (int)file_len
, file
, line
, name
);
485 js_func
= json_object_new_object();
486 json_object_object_add(funcs
, name
, js_func
);
489 js_calls
= json_object_new_array();
490 json_object_object_add(js_func
, "calls", js_calls
);
492 dbgloc_add(js_func
, function
);
494 for (LLVMBasicBlockRef basicBlock
= LLVMGetFirstBasicBlock(function
);
495 basicBlock
; basicBlock
= LLVMGetNextBasicBlock(basicBlock
)) {
497 for (LLVMValueRef instr
= LLVMGetFirstInstruction(basicBlock
);
498 instr
; instr
= LLVMGetNextInstruction(instr
)) {
500 if (LLVMIsAIntrinsicInst(instr
))
503 if (LLVMIsACallInst(instr
) || LLVMIsAInvokeInst(instr
))
504 process_call(js_calls
, js_special
, instr
,
510 static void help(int retcode
)
513 "FRR LLVM bitcode to callgraph analyzer\n"
515 "usage: frr-llvm-cg [-q|-v] [-o <JSONOUTPUT>] BITCODEINPUT\n"
517 "\t-o FILENAME\twrite JSON output to file instead of stdout\n"
518 "\t-v\t\tbe more verbose\n"
521 "BITCODEINPUT must be a LLVM binary bitcode file (not text\n"
522 "representation.) Use - to read from stdin.\n"
524 "Note it may be necessary to build this binary tool against\n"
525 "the specific LLVM version that created the bitcode file.\n");
529 int main(int argc
, char **argv
)
532 const char *out
= NULL
;
533 const char *inp
= NULL
;
536 while ((opt
= getopt(argc
, argv
, "hvqo:")) != -1) {
544 if (v_or_q
&& v_or_q
!= 'v')
546 details_fptr_vars
= true;
547 details_fptr_consts
= true;
551 if (v_or_q
&& v_or_q
!= 'q')
553 details_fptr_vars
= false;
554 details_fptr_consts
= false;
565 if (optind
!= argc
- 1)
570 LLVMMemoryBufferRef memoryBuffer
;
574 // check if we are to read our input file from stdin
575 if (!strcmp(inp
, "-")) {
577 ret
= LLVMCreateMemoryBufferWithSTDIN(&memoryBuffer
, &message
);
579 ret
= LLVMCreateMemoryBufferWithContentsOfFile(
580 inp
, &memoryBuffer
, &message
);
584 fprintf(stderr
, "failed to open %s: %s\n", inp
, message
);
589 // now create our module using the memorybuffer
590 LLVMModuleRef module
;
591 if (LLVMParseBitcode2(memoryBuffer
, &module
)) {
592 fprintf(stderr
, "%s: invalid bitcode\n", inp
);
593 LLVMDisposeMemoryBuffer(memoryBuffer
);
597 // done with the memory buffer now, so dispose of it
598 LLVMDisposeMemoryBuffer(memoryBuffer
);
600 struct json_object
*js_root
, *js_funcs
, *js_special
;
602 js_root
= json_object_new_object();
603 js_funcs
= json_object_new_object();
604 json_object_object_add(js_root
, "functions", js_funcs
);
605 js_special
= json_object_new_object();
606 json_object_object_add(js_root
, "special", js_special
);
608 // loop through all the functions in the module
609 for (LLVMValueRef function
= LLVMGetFirstFunction(module
); function
;
610 function
= LLVMGetNextFunction(function
)) {
611 if (LLVMIsDeclaration(function
))
614 process_fn(js_funcs
, js_special
, function
);
618 char tmpout
[strlen(out
) + 5];
620 snprintf(tmpout
, sizeof(tmpout
), "%s.tmp", out
);
621 ret
= json_object_to_file_ext(tmpout
, js_root
,
622 JSON_C_TO_STRING_PRETTY
|
623 JSON_C_TO_STRING_PRETTY_TAB
|
624 JSON_C_TO_STRING_NOSLASHESCAPE
);
626 fprintf(stderr
, "could not write JSON to file\n");
629 if (rename(tmpout
, out
)) {
630 fprintf(stderr
, "could not rename JSON output: %s\n",
636 ret
= json_object_to_fd(1, js_root
,
637 JSON_C_TO_STRING_PRETTY
|
638 JSON_C_TO_STRING_PRETTY_TAB
|
639 JSON_C_TO_STRING_NOSLASHESCAPE
);
641 fprintf(stderr
, "could not write JSON to stdout\n");
646 LLVMDisposeModule(module
);