tools/frr-llvm-cg.c

   1 // This is free and unencumbered software released into the public domain.
   2 //
   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
   6 // means.
   7 //
   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.
  15 //
  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.
  23 //
  24 // For more information, please refer to <http://unlicense.org/>
  25
  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.
  29  *
  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.
  34  *
  35  * 2020-05-04, David Lamparter
  36  */
  37
  38 #include <string.h>
  39 #include <strings.h>
  40 #include <stdbool.h>
  41 #include <stdlib.h>
  42 #include <stdio.h>
  43 #include <unistd.h>
  44 #include <errno.h>
  45 #include <assert.h>
  46
  47 #include <llvm-c/BitReader.h>
  48 #include <llvm-c/BitWriter.h>
  49 #include <llvm-c/Core.h>
  50
  51 #include <json-c/json.h>
  52
  53 /* if you want to use this without the special FRRouting defines,
  54  * remove the following #define
  55  */
  56 #define FRR_SPECIFIC
  57
  58 static void dbgloc_add(struct json_object *jsobj, LLVMValueRef obj)
  59 {
  60         unsigned file_len = 0;
  61         const char *file = LLVMGetDebugLocFilename(obj, &file_len);
  62         unsigned line = LLVMGetDebugLocLine(obj);
  63
  64         if (!file)
  65                 file = "???", file_len = 3;
  66         else if (file[0] == '.' && file[1] == '/')
  67                 file += 2, file_len -= 2;
  68
  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));
  72 }
  73
  74 static struct json_object *js_get_or_make(struct json_object *parent,
  75                                           const char *key,
  76                                           struct json_object *(*maker)(void))
  77 {
  78         struct json_object *ret;
  79
  80         ret = json_object_object_get(parent, key);
  81         if (ret)
  82                 return ret;
  83         ret = maker();
  84         json_object_object_add(parent, key, ret);
  85         return ret;
  86 }
  87
  88 static bool details_fptr_vars = false;
  89 static bool details_fptr_consts = true;
  90
  91 enum called_fn {
  92         FN_GENERIC = 0,
  93         FN_NONAME,
  94         FN_INSTALL_ELEMENT,
  95         FN_THREAD_ADD,
  96 };
  97
  98 static void walk_const_fptrs(struct json_object *js_call, LLVMValueRef value,
  99                              const char *prefix, bool *hdr_written)
 100 {
 101         LLVMTypeRef type;
 102         LLVMValueKind kind;
 103
 104         if (LLVMIsAGlobalVariable(value)) {
 105                 type = LLVMGlobalGetValueType(value);
 106                 value = LLVMGetInitializer(value);
 107         } else {
 108                 type = LLVMTypeOf(value);
 109         }
 110
 111         if (LLVMIsAFunction(value)) {
 112                 struct json_object *js_fptrs;
 113
 114                 js_fptrs = js_get_or_make(js_call, "funcptrs",
 115                                           json_object_new_array);
 116
 117                 size_t fn_len;
 118                 const char *fn_name = LLVMGetValueName2(value, &fn_len);
 119
 120                 size_t curlen = json_object_array_length(js_fptrs);
 121                 struct json_object *jsobj;
 122                 const char *s;
 123
 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);
 127
 128                         if (s && !strcmp(s, fn_name))
 129                                 return;
 130                 }
 131
 132                 if (details_fptr_consts && !*hdr_written) {
 133                         fprintf(stderr,
 134                                 "%s: calls function pointer from constant or global data\n",
 135                                 prefix);
 136                         *hdr_written = true;
 137                 }
 138                 if (details_fptr_consts)
 139                         fprintf(stderr, "%s-   constant: %.*s()\n",
 140                                 prefix, (int)fn_len, fn_name);
 141
 142                 json_object_array_add(js_fptrs,
 143                                        json_object_new_string_len(fn_name,
 144                                                                   fn_len));
 145                 return;
 146         }
 147
 148         kind = LLVMGetValueKind(value);
 149
 150         unsigned len;
 151         char *dump;
 152
 153         switch (kind) {
 154         case LLVMUndefValueValueKind:
 155         case LLVMConstantAggregateZeroValueKind:
 156         case LLVMConstantPointerNullValueKind:
 157                 /* null pointer / array - ignore */
 158                 break;
 159
 160         case LLVMConstantIntValueKind:
 161                 /* integer - ignore */
 162                 break;
 163
 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);
 169                 break;
 170
 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);
 176                 return;
 177
 178         default:
 179                 /* to help the user / development */
 180                 if (!*hdr_written) {
 181                         fprintf(stderr,
 182                                 "%s: calls function pointer from constant or global data\n",
 183                                 prefix);
 184                         *hdr_written = true;
 185                 }
 186                 dump = LLVMPrintValueToString(value);
 187                 fprintf(stderr,
 188                         "%s-   value could not be processed:\n"
 189                         "%s-   [kind=%d] %s\n",
 190                         prefix, prefix, kind, dump);
 191                 LLVMDisposeMessage(dump);
 192                 return;
 193         }
 194         return;
 195 }
 196
 197 #ifdef FRR_SPECIFIC
 198 static bool is_thread_sched(const char *name, size_t len)
 199 {
 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",
 208         };
 209         size_t i;
 210
 211         for (i = 0; i < sizeof(names) / sizeof(names[0]); i++) {
 212                 if (strlen(names[i]) != len)
 213                         continue;
 214                 if (!memcmp(names[i], name, len))
 215                         return true;
 216         }
 217         return false;
 218 }
 219 #endif
 220
 221 static void process_call(struct json_object *js_calls,
 222                          struct json_object *js_special,
 223                          LLVMValueRef instr,
 224                          LLVMValueRef function)
 225 {
 226         struct json_object *js_call, *js_fptrs = NULL;
 227
 228         LLVMValueRef called = LLVMGetCalledValue(instr);
 229
 230         if (LLVMIsAConstantExpr(called)) {
 231                 LLVMOpcode opcode = LLVMGetConstOpcode(called);
 232
 233                 if (opcode == LLVMBitCast) {
 234                         LLVMValueRef op0 = LLVMGetOperand(called, 0);
 235
 236                         if (LLVMIsAFunction(op0))
 237                                 called = op0;
 238                 }
 239         }
 240
 241         size_t called_len = 0;
 242         const char *called_name = LLVMGetValueName2(called, &called_len);
 243         unsigned n_args = LLVMGetNumArgOperands(instr);
 244
 245         bool is_external = LLVMIsDeclaration(called);
 246         enum called_fn called_type = FN_GENERIC;
 247
 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));
 253
 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"));
 258
 259                 LLVMValueRef last = called;
 260
 261                 size_t name_len = 0;
 262                 const char *name_c = LLVMGetValueName2(function, &name_len);
 263
 264 #ifdef FRR_SPECIFIC
 265                 /* information for FRR hooks is dumped for the registration
 266                  * in _hook_typecheck; we can safely ignore the funcptr here
 267                  */
 268                 if (strncmp(name_c, "hook_call_", 10) == 0)
 269                         return;
 270 #endif
 271
 272                 unsigned file_len = 0;
 273                 const char *file = LLVMGetDebugLocFilename(instr, &file_len);
 274                 unsigned line = LLVMGetDebugLocLine(instr);
 275
 276                 char prefix[256];
 277                 snprintf(prefix, sizeof(prefix), "%.*s:%d:%.*s()",
 278                          (int)file_len, file, line, (int)name_len, name_c);
 279
 280                 while (LLVMIsALoadInst(last) || LLVMIsAGetElementPtrInst(last))
 281                         /* skipping over details for GEP here, but meh. */
 282                         last = LLVMGetOperand(last, 0);
 283
 284                 if (LLVMIsAAllocaInst(last)) {
 285                         /* "alloca" is just generically all variables on the
 286                          * stack, this does not refer to C alloca() calls
 287                          *
 288                          * looking at the control flow in the function can
 289                          * give better results here, it's just not implemented
 290                          * (yet?)
 291                          */
 292                         fprintf(stderr,
 293                                 "%s: call to a function pointer variable\n",
 294                                 prefix);
 295
 296                         if (details_fptr_vars) {
 297                                 char *dump = LLVMPrintValueToString(called);
 298                                 printf("%s-   %s\n", prefix, dump);
 299                                 LLVMDisposeMessage(dump);
 300                         }
 301
 302                         json_object_object_add(
 303                                 js_call, "type",
 304                                 json_object_new_string("stack_fptr"));
 305                 } else if (LLVMIsACallInst(last)) {
 306                         /* calling the a function pointer returned from
 307                          * another function.
 308                          */
 309                         struct json_object *js_indirect;
 310
 311                         js_indirect = js_get_or_make(js_call, "return_of",
 312                                                      json_object_new_array);
 313
 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.)
 318                          */
 319                         bool hdr_written = false;
 320                         walk_const_fptrs(js_call, last, prefix, &hdr_written);
 321                         if (details_fptr_consts && !hdr_written)
 322                                 fprintf(stderr,
 323                                         "%s: calls function pointer from constant or global data, but no non-NULL function pointers found\n",
 324                                         prefix);
 325                 } else {
 326                         char *dump = LLVMPrintValueToString(called);
 327                         printf("\t%s\n", dump);
 328                         LLVMDisposeMessage(dump);
 329                 }
 330                 return;
 331 #ifdef FRR_SPECIFIC
 332         } else if (!strcmp(called_name, "install_element")) {
 333                 called_type = FN_INSTALL_ELEMENT;
 334
 335                 LLVMValueRef param0 = LLVMGetOperand(instr, 0);
 336                 if (!LLVMIsAConstantInt(param0))
 337                         goto out_nonconst;
 338
 339                 long long vty_node = LLVMConstIntGetSExtValue(param0);
 340                 json_object_object_add(js_call, "vty_node",
 341                                        json_object_new_int64(vty_node));
 342
 343                 LLVMValueRef param1 = LLVMGetOperand(instr, 1);
 344                 if (!LLVMIsAGlobalVariable(param1))
 345                         goto out_nonconst;
 346
 347                 LLVMValueRef intlz = LLVMGetInitializer(param1);
 348                 assert(intlz && LLVMIsConstant(intlz));
 349
 350                 LLVMValueKind intlzkind = LLVMGetValueKind(intlz);
 351                 assert(intlzkind == LLVMConstantStructValueKind);
 352
 353                 LLVMValueRef funcptr = LLVMGetOperand(intlz, 4);
 354                 assert(LLVMIsAFunction(funcptr));
 355
 356                 size_t target_len = 0;
 357                 const char *target;
 358                 target = LLVMGetValueName2(funcptr, &target_len);
 359
 360                 json_object_object_add(
 361                         js_call, "type",
 362                         json_object_new_string("install_element"));
 363                 json_object_object_add(
 364                         js_call, "target",
 365                         json_object_new_string_len(target, target_len));
 366                 return;
 367
 368         out_nonconst:
 369                 json_object_object_add(
 370                         js_call, "target",
 371                         json_object_new_string("install_element"));
 372                 return;
 373         } else if (is_thread_sched(called_name, called_len)) {
 374                 called_type = FN_THREAD_ADD;
 375
 376                 json_object_object_add(js_call, "type",
 377                                        json_object_new_string("thread_sched"));
 378                 json_object_object_add(
 379                         js_call, "subtype",
 380                         json_object_new_string_len(called_name, called_len));
 381
 382                 LLVMValueRef fparam;
 383                 if (strstr(called_name, "_read_"))
 384                         fparam = LLVMGetOperand(instr, 2);
 385                 else
 386                         fparam = LLVMGetOperand(instr, 1);
 387                 assert(fparam);
 388
 389                 size_t target_len = 0;
 390                 const char *target;
 391                 target = LLVMGetValueName2(fparam, &target_len);
 392
 393                 json_object_object_add(js_call, "target",
 394                                        !target_len ? NULL :
 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));
 399                 return;
 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;
 404
 405                 hook_name = called_name + strlen("_hook_typecheck_");
 406
 407                 json_object_object_add(js_call, "type",
 408                                        json_object_new_string("hook"));
 409
 410                 LLVMValueRef param0 = LLVMGetOperand(instr, 0);
 411                 if (!LLVMIsAFunction(param0))
 412                         return;
 413
 414                 size_t target_len = 0;
 415                 const char *target;
 416                 target = LLVMGetValueName2(param0, &target_len);
 417
 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);
 422
 423                 js_this = json_object_new_object();
 424                 json_object_array_add(js_hook, js_this);
 425
 426                 dbgloc_add(js_this, instr);
 427                 json_object_object_add(
 428                         js_this, "target",
 429                         json_object_new_string_len(target, target_len));
 430                 return;
 431
 432                 /* TODO (FRR specifics):
 433                  * - workqueues - not sure we can do much there
 434                  * - zclient->* ?
 435                  */
 436 #endif /* FRR_SPECIFIC */
 437         } else {
 438                 json_object_object_add(
 439                         js_call, "target",
 440                         json_object_new_string_len(called_name, called_len));
 441         }
 442
 443         for (unsigned argno = 0; argno < n_args; argno++) {
 444                 LLVMValueRef param = LLVMGetOperand(instr, argno);
 445                 size_t target_len;
 446                 const char *target_name;
 447
 448                 if (LLVMIsAFunction(param)) {
 449                         js_fptrs = js_get_or_make(js_call, "funcptrs",
 450                                                   json_object_new_array);
 451
 452                         target_name = LLVMGetValueName2(param, &target_len);
 453
 454                         json_object_array_add(js_fptrs,
 455                                               json_object_new_string_len(
 456                                                       target_name, target_len));
 457                 }
 458         }
 459 }
 460
 461 static void process_fn(struct json_object *funcs,
 462                        struct json_object *js_special,
 463                        LLVMValueRef function)
 464 {
 465         struct json_object *js_func, *js_calls;
 466
 467         size_t name_len = 0;
 468         const char *name_c = LLVMGetValueName2(function, &name_len);
 469         char *name;
 470
 471         name = strndup(name_c, name_len);
 472
 473         js_func = json_object_object_get(funcs, name);
 474         if (js_func) {
 475                 unsigned file_len = 0;
 476                 const char *file = LLVMGetDebugLocFilename(function, &file_len);
 477                 unsigned line = LLVMGetDebugLocLine(function);
 478
 479                 fprintf(stderr, "%.*s:%d:%s(): duplicate definition!\n",
 480                         (int)file_len, file, line, name);
 481                 free(name);
 482                 return;
 483         }
 484
 485         js_func = json_object_new_object();
 486         json_object_object_add(funcs, name, js_func);
 487         free(name);
 488
 489         js_calls = json_object_new_array();
 490         json_object_object_add(js_func, "calls", js_calls);
 491
 492         dbgloc_add(js_func, function);
 493
 494         for (LLVMBasicBlockRef basicBlock = LLVMGetFirstBasicBlock(function);
 495              basicBlock; basicBlock = LLVMGetNextBasicBlock(basicBlock)) {
 496
 497                 for (LLVMValueRef instr = LLVMGetFirstInstruction(basicBlock);
 498                      instr; instr = LLVMGetNextInstruction(instr)) {
 499
 500                         if (LLVMIsAIntrinsicInst(instr))
 501                                 continue;
 502
 503                         if (LLVMIsACallInst(instr) || LLVMIsAInvokeInst(instr))
 504                                 process_call(js_calls, js_special, instr,
 505                                              function);
 506                 }
 507         }
 508 }
 509
 510 static void help(int retcode)
 511 {
 512         fprintf(stderr,
 513                 "FRR LLVM bitcode to callgraph analyzer\n"
 514                 "\n"
 515                 "usage:  frr-llvm-cg [-q|-v] [-o <JSONOUTPUT>] BITCODEINPUT\n"
 516                 "\n"
 517                 "\t-o FILENAME\twrite JSON output to file instead of stdout\n"
 518                 "\t-v\t\tbe more verbose\n"
 519                 "\t-q\t\tbe quiet\n"
 520                 "\n"
 521                 "BITCODEINPUT must be a LLVM binary bitcode file (not text\n"
 522                 "representation.)  Use - to read from stdin.\n"
 523                 "\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");
 526         exit(retcode);
 527 }
 528
 529 int main(int argc, char **argv)
 530 {
 531         int opt;
 532         const char *out = NULL;
 533         const char *inp = NULL;
 534         char v_or_q = '\0';
 535
 536         while ((opt = getopt(argc, argv, "hvqo:")) != -1) {
 537                 switch (opt) {
 538                 case 'o':
 539                         if (out)
 540                                 help(1);
 541                         out = optarg;
 542                         break;
 543                 case 'v':
 544                         if (v_or_q && v_or_q != 'v')
 545                                 help(1);
 546                         details_fptr_vars = true;
 547                         details_fptr_consts = true;
 548                         v_or_q = 'v';
 549                         break;
 550                 case 'q':
 551                         if (v_or_q && v_or_q != 'q')
 552                                 help(1);
 553                         details_fptr_vars = false;
 554                         details_fptr_consts = false;
 555                         v_or_q = 'q';
 556                         break;
 557                 case 'h':
 558                         help(0);
 559                         return 0;
 560                 default:
 561                         help(1);
 562                 }
 563         }
 564
 565         if (optind != argc - 1)
 566                 help(1);
 567
 568         inp = argv[optind];
 569
 570         LLVMMemoryBufferRef memoryBuffer;
 571         char *message;
 572         int ret;
 573
 574         // check if we are to read our input file from stdin
 575         if (!strcmp(inp, "-")) {
 576                 inp = "<stdin>";
 577                 ret = LLVMCreateMemoryBufferWithSTDIN(&memoryBuffer, &message);
 578         } else {
 579                 ret = LLVMCreateMemoryBufferWithContentsOfFile(
 580                         inp, &memoryBuffer, &message);
 581         }
 582
 583         if (ret) {
 584                 fprintf(stderr, "failed to open %s: %s\n", inp, message);
 585                 free(message);
 586                 return 1;
 587         }
 588
 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);
 594                 return 1;
 595         }
 596
 597         // done with the memory buffer now, so dispose of it
 598         LLVMDisposeMemoryBuffer(memoryBuffer);
 599
 600         struct json_object *js_root, *js_funcs, *js_special;
 601
 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);
 607
 608         // loop through all the functions in the module
 609         for (LLVMValueRef function = LLVMGetFirstFunction(module); function;
 610              function = LLVMGetNextFunction(function)) {
 611                 if (LLVMIsDeclaration(function))
 612                         continue;
 613
 614                 process_fn(js_funcs, js_special, function);
 615         }
 616
 617         if (out) {
 618                 char tmpout[strlen(out) + 5];
 619
 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);
 625                 if (ret < 0) {
 626                         fprintf(stderr, "could not write JSON to file\n");
 627                         return 1;
 628                 }
 629                 if (rename(tmpout, out)) {
 630                         fprintf(stderr, "could not rename JSON output: %s\n",
 631                                 strerror(errno));
 632                         unlink(tmpout);
 633                         return 1;
 634                 }
 635         } else {
 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);
 640                 if (ret < 0) {
 641                         fprintf(stderr, "could not write JSON to stdout\n");
 642                         return 1;
 643                 }
 644         }
 645
 646         LLVMDisposeModule(module);
 647
 648         return 0;
 649 }