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 #include "frr-llvm-debuginfo.h"
  54
  55 /* if you want to use this without the special FRRouting defines,
  56  * remove the following #define
  57  */
  58 #define FRR_SPECIFIC
  59
  60 static struct dbginfo *dbginfo;
  61
  62 static void dbgloc_add(struct json_object *jsobj, LLVMValueRef obj)
  63 {
  64         unsigned file_len = 0;
  65         const char *file = LLVMGetDebugLocFilename(obj, &file_len);
  66         unsigned line = LLVMGetDebugLocLine(obj);
  67
  68         if (!file)
  69                 file = "???", file_len = 3;
  70         else if (file[0] == '.' && file[1] == '/')
  71                 file += 2, file_len -= 2;
  72
  73         json_object_object_add(jsobj, "filename",
  74                                json_object_new_string_len(file, file_len));
  75         json_object_object_add(jsobj, "line", json_object_new_int64(line));
  76 }
  77
  78 static struct json_object *js_get_or_make(struct json_object *parent,
  79                                           const char *key,
  80                                           struct json_object *(*maker)(void))
  81 {
  82         struct json_object *ret;
  83
  84         ret = json_object_object_get(parent, key);
  85         if (ret)
  86                 return ret;
  87         ret = maker();
  88         json_object_object_add(parent, key, ret);
  89         return ret;
  90 }
  91
  92 static bool try_struct_fptr(struct json_object *js_call, LLVMValueRef gep,
  93                             const char *prefix)
  94 {
  95         unsigned long long val = 0;
  96         bool ret = false;
  97         LLVMTypeRef ptrtype = LLVMTypeOf(LLVMGetOperand(gep, 0));
  98         LLVMValueRef idx;
  99
 100         /* middle steps like struct a -> struct b a_member; -> fptr */
 101         for (int i = 1; ptrtype && i < LLVMGetNumOperands(gep) - 1; i++) {
 102                 if (LLVMGetTypeKind(ptrtype) == LLVMPointerTypeKind
 103                     || LLVMGetTypeKind(ptrtype) == LLVMArrayTypeKind
 104                     || LLVMGetTypeKind(ptrtype) == LLVMVectorTypeKind) {
 105                         ptrtype = LLVMGetElementType(ptrtype);
 106                         continue;
 107                 }
 108
 109                 if (LLVMGetTypeKind(ptrtype) != LLVMStructTypeKind)
 110                         return false;
 111
 112                 idx = LLVMGetOperand(gep, i);
 113                 if (!LLVMIsConstant(idx))
 114                         return false;
 115                 val = LLVMConstIntGetZExtValue(idx);
 116
 117                 unsigned n = LLVMGetNumContainedTypes(ptrtype);
 118                 LLVMTypeRef arr[n];
 119
 120                 if (val > n)
 121                         return false;
 122
 123                 LLVMGetSubtypes(ptrtype, arr);
 124                 ptrtype = arr[val];
 125         }
 126
 127         if (!ptrtype)
 128                 return false;
 129
 130         idx = LLVMGetOperand(gep, LLVMGetNumOperands(gep) - 1);
 131         if (!LLVMIsConstant(idx))
 132                 return false;
 133
 134         val = LLVMConstIntGetZExtValue(idx);
 135
 136         char *sname = NULL, *mname = NULL;
 137
 138         if (dbginfo_struct_member(dbginfo, ptrtype, val, &sname, &mname)) {
 139                 fprintf(stderr, "%s: call to struct %s->%s\n", prefix, sname,
 140                         mname);
 141
 142                 json_object_object_add(js_call, "type",
 143                                        json_object_new_string("struct_memb"));
 144                 json_object_object_add(js_call, "struct",
 145                                        json_object_new_string(sname));
 146                 json_object_object_add(js_call, "member",
 147                                        json_object_new_string(mname));
 148                 ret = true;
 149         }
 150         free(sname);
 151         free(mname);
 152
 153         return ret;
 154 }
 155
 156 static bool details_fptr_vars = false;
 157 static bool details_fptr_consts = true;
 158
 159 enum called_fn {
 160         FN_GENERIC = 0,
 161         FN_NONAME,
 162         FN_INSTALL_ELEMENT,
 163         FN_THREAD_ADD,
 164 };
 165
 166 static void walk_const_fptrs(struct json_object *js_call, LLVMValueRef value,
 167                              const char *prefix, bool *hdr_written)
 168 {
 169         LLVMTypeRef type;
 170         LLVMValueKind kind;
 171
 172         if (LLVMIsAGlobalVariable(value)) {
 173                 type = LLVMGlobalGetValueType(value);
 174                 value = LLVMGetInitializer(value);
 175         } else {
 176                 type = LLVMTypeOf(value);
 177         }
 178
 179         if (LLVMIsAFunction(value)) {
 180                 struct json_object *js_fptrs;
 181
 182                 js_fptrs = js_get_or_make(js_call, "funcptrs",
 183                                           json_object_new_array);
 184
 185                 size_t fn_len;
 186                 const char *fn_name = LLVMGetValueName2(value, &fn_len);
 187
 188                 size_t curlen = json_object_array_length(js_fptrs);
 189                 struct json_object *jsobj;
 190                 const char *s;
 191
 192                 for (size_t i = 0; i < curlen; i++) {
 193                         jsobj = json_object_array_get_idx(js_fptrs, i);
 194                         s = json_object_get_string(jsobj);
 195
 196                         if (s && !strcmp(s, fn_name))
 197                                 return;
 198                 }
 199
 200                 if (details_fptr_consts && !*hdr_written) {
 201                         fprintf(stderr,
 202                                 "%s: calls function pointer from constant or global data\n",
 203                                 prefix);
 204                         *hdr_written = true;
 205                 }
 206                 if (details_fptr_consts)
 207                         fprintf(stderr, "%s-   constant: %.*s()\n",
 208                                 prefix, (int)fn_len, fn_name);
 209
 210                 json_object_array_add(js_fptrs,
 211                                        json_object_new_string_len(fn_name,
 212                                                                   fn_len));
 213                 return;
 214         }
 215
 216         kind = LLVMGetValueKind(value);
 217
 218         unsigned len;
 219         char *dump;
 220
 221         switch (kind) {
 222         case LLVMUndefValueValueKind:
 223         case LLVMConstantAggregateZeroValueKind:
 224         case LLVMConstantPointerNullValueKind:
 225                 /* null pointer / array - ignore */
 226                 break;
 227
 228         case LLVMConstantIntValueKind:
 229                 /* integer - ignore */
 230                 break;
 231
 232         case LLVMConstantStructValueKind:
 233                 len = LLVMCountStructElementTypes(type);
 234                 for (unsigned i = 0; i < len; i++)
 235                         walk_const_fptrs(js_call, LLVMGetOperand(value, i),
 236                                          prefix, hdr_written);
 237                 break;
 238
 239         case LLVMConstantArrayValueKind:
 240                 len = LLVMGetArrayLength(type);
 241                 for (unsigned i = 0; i < len; i++)
 242                         walk_const_fptrs(js_call, LLVMGetOperand(value, i),
 243                                          prefix, hdr_written);
 244                 return;
 245
 246         case LLVMConstantExprValueKind:
 247                 switch (LLVMGetConstOpcode(value)) {
 248                 case LLVMGetElementPtr:
 249                         if (try_struct_fptr(js_call, value, prefix)) {
 250                                 *hdr_written = true;
 251                                 return;
 252                         }
 253
 254                         fprintf(stderr,
 255                                 "%s: calls function pointer from unhandled const GEP\n",
 256                                 prefix);
 257                         *hdr_written = true;
 258                         /* fallthru */
 259                 default:
 260                         /* to help the user / development */
 261                         if (!*hdr_written) {
 262                                 fprintf(stderr,
 263                                         "%s: calls function pointer from constexpr\n",
 264                                         prefix);
 265                                 *hdr_written = true;
 266                         }
 267                         dump = LLVMPrintValueToString(value);
 268                         fprintf(stderr, "%s-   [opcode=%d] %s\n", prefix,
 269                                 LLVMGetConstOpcode(value), dump);
 270                         LLVMDisposeMessage(dump);
 271                 }
 272                 return;
 273
 274         default:
 275                 /* to help the user / development */
 276                 if (!*hdr_written) {
 277                         fprintf(stderr,
 278                                 "%s: calls function pointer from constant or global data\n",
 279                                 prefix);
 280                         *hdr_written = true;
 281                 }
 282                 dump = LLVMPrintValueToString(value);
 283                 fprintf(stderr,
 284                         "%s-   value could not be processed:\n"
 285                         "%s-   [kind=%d] %s\n",
 286                         prefix, prefix, kind, dump);
 287                 LLVMDisposeMessage(dump);
 288                 return;
 289         }
 290         return;
 291 }
 292
 293 #ifdef FRR_SPECIFIC
 294 static bool is_thread_sched(const char *name, size_t len)
 295 {
 296 #define thread_prefix "_"
 297         static const char *const names[] = {
 298                 thread_prefix "thread_add_read_write",
 299                 thread_prefix "thread_add_timer",
 300                 thread_prefix "thread_add_timer_msec",
 301                 thread_prefix "thread_add_timer_tv",
 302                 thread_prefix "thread_add_event",
 303                 thread_prefix "thread_execute",
 304         };
 305         size_t i;
 306
 307         for (i = 0; i < sizeof(names) / sizeof(names[0]); i++) {
 308                 if (strlen(names[i]) != len)
 309                         continue;
 310                 if (!memcmp(names[i], name, len))
 311                         return true;
 312         }
 313         return false;
 314 }
 315 #endif
 316
 317 static bool _check_val(bool cond, const char *text, LLVMValueRef dumpval)
 318 {
 319         if (cond)
 320                 return true;
 321
 322         char *dump = LLVMPrintValueToString(dumpval);
 323         fprintf(stderr, "check failed: %s\ndump:\n\t%s\n", text, dump);
 324         LLVMDisposeMessage(dump);
 325         return false;
 326 }
 327
 328 #define check_val(cond, dump)                                                  \
 329         if (!_check_val(cond, #cond, dump))                                    \
 330                 return;
 331
 332 static char *get_string(LLVMValueRef value)
 333 {
 334         if (!LLVMIsAConstant(value))
 335                 return strdup("!NOT-A-CONST");
 336
 337         if (LLVMGetValueKind(value) == LLVMConstantExprValueKind
 338             && LLVMGetConstOpcode(value) == LLVMGetElementPtr) {
 339                 value = LLVMGetOperand(value, 0);
 340
 341                 if (!LLVMIsAConstant(value))
 342                         return strdup("!NOT-A-CONST-2");
 343         }
 344
 345         if (LLVMIsAGlobalVariable(value))
 346                 value = LLVMGetInitializer(value);
 347
 348         size_t len = 0;
 349         const char *sval = LLVMGetAsString(value, &len);
 350
 351         return strndup(sval, len);
 352 }
 353
 354 static void handle_yang_module(struct json_object *js_special,
 355                                LLVMValueRef yang_mod)
 356 {
 357         check_val(LLVMIsAGlobalVariable(yang_mod), yang_mod);
 358
 359         LLVMValueRef value;
 360
 361         value = LLVMGetInitializer(yang_mod);
 362         LLVMValueKind kind = LLVMGetValueKind(value);
 363
 364         check_val(kind == LLVMConstantStructValueKind, value);
 365
 366         size_t var_len = 0;
 367         const char *var_name = LLVMGetValueName2(yang_mod, &var_len);
 368         char buf_name[var_len + 1];
 369
 370         memcpy(buf_name, var_name, var_len);
 371         buf_name[var_len] = '\0';
 372
 373         struct json_object *js_yang, *js_yangmod, *js_items;
 374
 375         js_yang = js_get_or_make(js_special, "yang", json_object_new_object);
 376         js_yangmod = js_get_or_make(js_yang, buf_name, json_object_new_object);
 377         js_items = js_get_or_make(js_yangmod, "items", json_object_new_array);
 378
 379         char *mod_name = get_string(LLVMGetOperand(value, 0));
 380         json_object_object_add(js_yangmod, "name",
 381                                json_object_new_string(mod_name));
 382         free(mod_name);
 383
 384         value = LLVMGetOperand(value, 1);
 385         kind = LLVMGetValueKind(value);
 386         check_val(kind == LLVMConstantArrayValueKind, value);
 387
 388         unsigned len = LLVMGetArrayLength(LLVMTypeOf(value));
 389
 390         for (unsigned i = 0; i < len - 1; i++) {
 391                 struct json_object *js_item, *js_cbs;
 392                 LLVMValueRef item = LLVMGetOperand(value, i);
 393                 char *xpath = get_string(LLVMGetOperand(item, 0));
 394
 395                 js_item = json_object_new_object();
 396                 json_object_array_add(js_items, js_item);
 397
 398                 json_object_object_add(js_item, "xpath",
 399                                        json_object_new_string(xpath));
 400                 js_cbs = js_get_or_make(js_item, "cbs", json_object_new_object);
 401
 402                 free(xpath);
 403
 404                 LLVMValueRef cbs = LLVMGetOperand(item, 1);
 405
 406                 check_val(LLVMGetValueKind(cbs) == LLVMConstantStructValueKind,
 407                           value);
 408
 409                 LLVMTypeRef cbs_type = LLVMTypeOf(cbs);
 410                 unsigned cblen = LLVMCountStructElementTypes(cbs_type);
 411
 412                 for (unsigned i = 0; i < cblen; i++) {
 413                         LLVMValueRef cb = LLVMGetOperand(cbs, i);
 414
 415                         char *sname = NULL;
 416                         char *mname = NULL;
 417
 418                         if (dbginfo_struct_member(dbginfo, cbs_type, i, &sname,
 419                                                   &mname)) {
 420                                 (void)0;
 421                         }
 422
 423                         if (LLVMIsAFunction(cb)) {
 424                                 size_t fn_len;
 425                                 const char *fn_name;
 426
 427                                 fn_name = LLVMGetValueName2(cb, &fn_len);
 428
 429                                 json_object_object_add(
 430                                         js_cbs, mname,
 431                                         json_object_new_string_len(fn_name,
 432                                                                    fn_len));
 433                         }
 434
 435                         free(sname);
 436                         free(mname);
 437                 }
 438         }
 439 }
 440
 441 static void handle_daemoninfo(struct json_object *js_special,
 442                               LLVMValueRef daemoninfo)
 443 {
 444         check_val(LLVMIsAGlobalVariable(daemoninfo), daemoninfo);
 445
 446         LLVMTypeRef type;
 447         LLVMValueRef value;
 448         unsigned len;
 449
 450         type = LLVMGlobalGetValueType(daemoninfo);
 451         value = LLVMGetInitializer(daemoninfo);
 452         LLVMValueKind kind = LLVMGetValueKind(value);
 453
 454         check_val(kind == LLVMConstantStructValueKind, value);
 455
 456         int yang_idx = -1;
 457
 458         len = LLVMCountStructElementTypes(type);
 459
 460         LLVMTypeRef fieldtypes[len];
 461         LLVMGetSubtypes(type, fieldtypes);
 462
 463         for (unsigned i = 0; i < len; i++) {
 464                 LLVMTypeRef t = fieldtypes[i];
 465
 466                 if (LLVMGetTypeKind(t) != LLVMPointerTypeKind)
 467                         continue;
 468                 t = LLVMGetElementType(t);
 469                 if (LLVMGetTypeKind(t) != LLVMPointerTypeKind)
 470                         continue;
 471                 t = LLVMGetElementType(t);
 472                 if (LLVMGetTypeKind(t) != LLVMStructTypeKind)
 473                         continue;
 474
 475                 const char *name = LLVMGetStructName(t);
 476                 if (!strcmp(name, "struct.frr_yang_module_info"))
 477                         yang_idx = i;
 478         }
 479
 480         if (yang_idx == -1)
 481                 return;
 482
 483         LLVMValueRef yang_mods = LLVMGetOperand(value, yang_idx);
 484         LLVMValueRef yang_size = LLVMGetOperand(value, yang_idx + 1);
 485
 486         check_val(LLVMIsConstant(yang_size), yang_size);
 487
 488         unsigned long long ival = LLVMConstIntGetZExtValue(yang_size);
 489
 490         check_val(LLVMGetValueKind(yang_mods) == LLVMConstantExprValueKind
 491                           && LLVMGetConstOpcode(yang_mods) == LLVMGetElementPtr,
 492                   yang_mods);
 493
 494         yang_mods = LLVMGetOperand(yang_mods, 0);
 495
 496         check_val(LLVMIsAGlobalVariable(yang_mods), yang_mods);
 497
 498         yang_mods = LLVMGetInitializer(yang_mods);
 499
 500         check_val(LLVMGetValueKind(yang_mods) == LLVMConstantArrayValueKind,
 501                   yang_mods);
 502
 503         len = LLVMGetArrayLength(LLVMTypeOf(yang_mods));
 504
 505         if (len != ival)
 506                 fprintf(stderr, "length mismatch - %llu vs. %u\n", ival, len);
 507
 508         for (unsigned i = 0; i < len; i++) {
 509                 char *dump;
 510
 511                 LLVMValueRef item = LLVMGetOperand(yang_mods, i);
 512                 LLVMValueKind kind = LLVMGetValueKind(item);
 513
 514                 check_val(kind == LLVMGlobalVariableValueKind
 515                                   || kind == LLVMConstantExprValueKind,
 516                           item);
 517
 518                 if (kind == LLVMGlobalVariableValueKind)
 519                         continue;
 520
 521                 LLVMOpcode opcode = LLVMGetConstOpcode(item);
 522                 switch (opcode) {
 523                 case LLVMBitCast:
 524                         item = LLVMGetOperand(item, 0);
 525                         handle_yang_module(js_special, item);
 526                         break;
 527
 528                 default:
 529                         dump = LLVMPrintValueToString(item);
 530                         printf("[%u] = [opcode=%u] %s\n", i, opcode, dump);
 531                         LLVMDisposeMessage(dump);
 532                 }
 533         }
 534 }
 535
 536 static void process_call(struct json_object *js_calls,
 537                          struct json_object *js_special,
 538                          LLVMValueRef instr,
 539                          LLVMValueRef function)
 540 {
 541         struct json_object *js_call, *js_fptrs = NULL;
 542
 543         LLVMValueRef called = LLVMGetCalledValue(instr);
 544
 545         if (LLVMIsAInlineAsm(called))
 546                 return;
 547
 548         if (LLVMIsAConstantExpr(called)) {
 549                 LLVMOpcode opcode = LLVMGetConstOpcode(called);
 550
 551                 if (opcode == LLVMBitCast) {
 552                         LLVMValueRef op0 = LLVMGetOperand(called, 0);
 553
 554                         if (LLVMIsAFunction(op0))
 555                                 called = op0;
 556                 }
 557         }
 558
 559         size_t called_len = 0;
 560         const char *called_name = LLVMGetValueName2(called, &called_len);
 561         unsigned n_args = LLVMGetNumArgOperands(instr);
 562
 563         bool is_external = LLVMIsDeclaration(called);
 564         enum called_fn called_type = FN_GENERIC;
 565
 566         js_call = json_object_new_object();
 567         json_object_array_add(js_calls, js_call);
 568         dbgloc_add(js_call, instr);
 569         json_object_object_add(js_call, "is_external",
 570                                json_object_new_boolean(is_external));
 571
 572         if (!called_name || called_len == 0) {
 573                 called_type = FN_NONAME;
 574                 json_object_object_add(js_call, "type",
 575                                        json_object_new_string("indirect"));
 576
 577                 LLVMValueRef last = called;
 578
 579                 size_t name_len = 0;
 580                 const char *name_c = LLVMGetValueName2(function, &name_len);
 581
 582 #ifdef FRR_SPECIFIC
 583                 /* information for FRR hooks is dumped for the registration
 584                  * in _hook_typecheck; we can safely ignore the funcptr here
 585                  */
 586                 if (strncmp(name_c, "hook_call_", 10) == 0)
 587                         return;
 588 #endif
 589
 590                 unsigned file_len = 0;
 591                 const char *file = LLVMGetDebugLocFilename(instr, &file_len);
 592                 unsigned line = LLVMGetDebugLocLine(instr);
 593
 594                 char prefix[256];
 595                 snprintf(prefix, sizeof(prefix), "%.*s:%d:%.*s()",
 596                          (int)file_len, file, line, (int)name_len, name_c);
 597
 598                 if (LLVMIsALoadInst(called)
 599                     && LLVMIsAGetElementPtrInst(LLVMGetOperand(called, 0))
 600                     && try_struct_fptr(js_call, LLVMGetOperand(called, 0),
 601                                        prefix))
 602                         goto out_struct_fptr;
 603
 604                 while (LLVMIsALoadInst(last) || LLVMIsAGetElementPtrInst(last))
 605                         /* skipping over details for GEP here, but meh. */
 606                         last = LLVMGetOperand(last, 0);
 607
 608                 if (LLVMIsAAllocaInst(last)) {
 609                         /* "alloca" is just generically all variables on the
 610                          * stack, this does not refer to C alloca() calls
 611                          *
 612                          * looking at the control flow in the function can
 613                          * give better results here, it's just not implemented
 614                          * (yet?)
 615                          */
 616                         fprintf(stderr,
 617                                 "%s: call to a function pointer variable\n",
 618                                 prefix);
 619
 620                         if (details_fptr_vars) {
 621                                 char *dump = LLVMPrintValueToString(called);
 622                                 printf("%s-   %s\n", prefix, dump);
 623                                 LLVMDisposeMessage(dump);
 624                         }
 625
 626                         json_object_object_add(
 627                                 js_call, "type",
 628                                 json_object_new_string("stack_fptr"));
 629                 } else if (LLVMIsACallInst(last)) {
 630                         /* calling the a function pointer returned from
 631                          * another function.
 632                          */
 633                         struct json_object *js_indirect;
 634
 635                         js_indirect = js_get_or_make(js_call, "return_of",
 636                                                      json_object_new_array);
 637
 638                         process_call(js_indirect, js_special, last, function);
 639                 } else if (LLVMIsAConstant(last)) {
 640                         /* function pointer is a constant (includes loading
 641                          * from complicated constants like structs or arrays.)
 642                          */
 643                         bool hdr_written = false;
 644                         walk_const_fptrs(js_call, last, prefix, &hdr_written);
 645                         if (details_fptr_consts && !hdr_written)
 646                                 fprintf(stderr,
 647                                         "%s: calls function pointer from constant or global data, but no non-NULL function pointers found\n",
 648                                         prefix);
 649                 } else {
 650                         char *dump = LLVMPrintValueToString(called);
 651                         fprintf(stderr, "%s: ??? %s\n", prefix, dump);
 652                         LLVMDisposeMessage(dump);
 653                 }
 654 #ifdef FRR_SPECIFIC
 655         } else if (!strcmp(called_name, "_install_element")) {
 656                 called_type = FN_INSTALL_ELEMENT;
 657
 658                 LLVMValueRef param0 = LLVMGetOperand(instr, 0);
 659                 if (!LLVMIsAConstantInt(param0))
 660                         goto out_nonconst;
 661
 662                 long long vty_node = LLVMConstIntGetSExtValue(param0);
 663                 json_object_object_add(js_call, "vty_node",
 664                                        json_object_new_int64(vty_node));
 665
 666                 LLVMValueRef param1 = LLVMGetOperand(instr, 1);
 667                 if (!LLVMIsAGlobalVariable(param1))
 668                         goto out_nonconst;
 669
 670                 LLVMValueRef intlz = LLVMGetInitializer(param1);
 671                 assert(intlz && LLVMIsConstant(intlz));
 672
 673                 LLVMValueKind intlzkind = LLVMGetValueKind(intlz);
 674                 assert(intlzkind == LLVMConstantStructValueKind);
 675
 676                 LLVMValueRef funcptr = LLVMGetOperand(intlz, 4);
 677                 assert(LLVMIsAFunction(funcptr));
 678
 679                 size_t target_len = 0;
 680                 const char *target;
 681                 target = LLVMGetValueName2(funcptr, &target_len);
 682
 683                 json_object_object_add(
 684                         js_call, "type",
 685                         json_object_new_string("install_element"));
 686                 json_object_object_add(
 687                         js_call, "target",
 688                         json_object_new_string_len(target, target_len));
 689                 return;
 690
 691         out_nonconst:
 692                 json_object_object_add(
 693                         js_call, "target",
 694                         json_object_new_string("install_element"));
 695                 return;
 696         } else if (is_thread_sched(called_name, called_len)) {
 697                 called_type = FN_THREAD_ADD;
 698
 699                 json_object_object_add(js_call, "type",
 700                                        json_object_new_string("thread_sched"));
 701                 json_object_object_add(
 702                         js_call, "subtype",
 703                         json_object_new_string_len(called_name, called_len));
 704
 705                 LLVMValueRef fparam;
 706                 fparam = LLVMGetOperand(instr, 2);
 707                 assert(fparam);
 708
 709                 size_t target_len = 0;
 710                 const char *target;
 711                 target = LLVMGetValueName2(fparam, &target_len);
 712
 713                 json_object_object_add(js_call, "target",
 714                                        !target_len ? NULL :
 715                                json_object_new_string_len(target, target_len));
 716                 if (!LLVMIsAFunction(fparam))
 717                         json_object_object_add(js_call, "target_unresolved",
 718                                                json_object_new_boolean(true));
 719                 return;
 720         } else if (!strncmp(called_name, "_hook_typecheck_",
 721                             strlen("_hook_typecheck_"))) {
 722                 struct json_object *js_hook, *js_this;
 723                 const char *hook_name;
 724
 725                 hook_name = called_name + strlen("_hook_typecheck_");
 726
 727                 json_object_object_add(js_call, "type",
 728                                        json_object_new_string("hook"));
 729
 730                 LLVMValueRef param0 = LLVMGetOperand(instr, 0);
 731                 if (!LLVMIsAFunction(param0))
 732                         return;
 733
 734                 size_t target_len = 0;
 735                 const char *target;
 736                 target = LLVMGetValueName2(param0, &target_len);
 737
 738                 js_hook = js_get_or_make(js_special, "hooks",
 739                                          json_object_new_object);
 740                 js_hook = js_get_or_make(js_hook, hook_name,
 741                                          json_object_new_array);
 742
 743                 js_this = json_object_new_object();
 744                 json_object_array_add(js_hook, js_this);
 745
 746                 dbgloc_add(js_this, instr);
 747                 json_object_object_add(
 748                         js_this, "target",
 749                         json_object_new_string_len(target, target_len));
 750                 return;
 751
 752                 /* TODO (FRR specifics):
 753                  * - workqueues - not sure we can do much there
 754                  * - zclient->* ?
 755                  */
 756 #endif /* FRR_SPECIFIC */
 757         } else if (!strcmp(called_name, "frr_preinit")) {
 758                 LLVMValueRef daemoninfo = LLVMGetOperand(instr, 0);
 759
 760                 handle_daemoninfo(js_special, daemoninfo);
 761
 762                 json_object_object_add(
 763                         js_call, "target",
 764                         json_object_new_string_len(called_name, called_len));
 765         } else {
 766                 json_object_object_add(
 767                         js_call, "target",
 768                         json_object_new_string_len(called_name, called_len));
 769         }
 770
 771 out_struct_fptr:
 772         for (unsigned argno = 0; argno < n_args; argno++) {
 773                 LLVMValueRef param = LLVMGetOperand(instr, argno);
 774                 size_t target_len;
 775                 const char *target_name;
 776
 777                 if (LLVMIsAFunction(param)) {
 778                         js_fptrs = js_get_or_make(js_call, "funcptrs",
 779                                                   json_object_new_array);
 780
 781                         target_name = LLVMGetValueName2(param, &target_len);
 782
 783                         json_object_array_add(js_fptrs,
 784                                               json_object_new_string_len(
 785                                                       target_name, target_len));
 786                 }
 787         }
 788 }
 789
 790 static void process_fn(struct json_object *funcs,
 791                        struct json_object *js_special,
 792                        LLVMValueRef function)
 793 {
 794         struct json_object *js_func, *js_calls;
 795
 796         size_t name_len = 0;
 797         const char *name_c = LLVMGetValueName2(function, &name_len);
 798         char *name;
 799
 800         name = strndup(name_c, name_len);
 801
 802         js_func = json_object_object_get(funcs, name);
 803         if (js_func) {
 804                 unsigned file_len = 0;
 805                 const char *file = LLVMGetDebugLocFilename(function, &file_len);
 806                 unsigned line = LLVMGetDebugLocLine(function);
 807
 808                 fprintf(stderr, "%.*s:%d:%s(): duplicate definition!\n",
 809                         (int)file_len, file, line, name);
 810                 free(name);
 811                 return;
 812         }
 813
 814         js_func = json_object_new_object();
 815         json_object_object_add(funcs, name, js_func);
 816         free(name);
 817
 818         js_calls = json_object_new_array();
 819         json_object_object_add(js_func, "calls", js_calls);
 820
 821         dbgloc_add(js_func, function);
 822
 823         for (LLVMBasicBlockRef basicBlock = LLVMGetFirstBasicBlock(function);
 824              basicBlock; basicBlock = LLVMGetNextBasicBlock(basicBlock)) {
 825
 826                 for (LLVMValueRef instr = LLVMGetFirstInstruction(basicBlock);
 827                      instr; instr = LLVMGetNextInstruction(instr)) {
 828
 829                         if (LLVMIsAIntrinsicInst(instr))
 830                                 continue;
 831
 832                         if (LLVMIsACallInst(instr) || LLVMIsAInvokeInst(instr))
 833                                 process_call(js_calls, js_special, instr,
 834                                              function);
 835                 }
 836         }
 837 }
 838
 839 static void help(int retcode)
 840 {
 841         fprintf(stderr,
 842                 "FRR LLVM bitcode to callgraph analyzer\n"
 843                 "\n"
 844                 "usage:  frr-llvm-cg [-q|-v] [-o <JSONOUTPUT>] BITCODEINPUT\n"
 845                 "\n"
 846                 "\t-o FILENAME\twrite JSON output to file instead of stdout\n"
 847                 "\t-v\t\tbe more verbose\n"
 848                 "\t-q\t\tbe quiet\n"
 849                 "\n"
 850                 "BITCODEINPUT must be a LLVM binary bitcode file (not text\n"
 851                 "representation.)  Use - to read from stdin.\n"
 852                 "\n"
 853                 "Note it may be necessary to build this binary tool against\n"
 854                 "the specific LLVM version that created the bitcode file.\n");
 855         exit(retcode);
 856 }
 857
 858 int main(int argc, char **argv)
 859 {
 860         int opt;
 861         const char *out = NULL;
 862         const char *inp = NULL;
 863         char v_or_q = '\0';
 864
 865         while ((opt = getopt(argc, argv, "hvqo:")) != -1) {
 866                 switch (opt) {
 867                 case 'o':
 868                         if (out)
 869                                 help(1);
 870                         out = optarg;
 871                         break;
 872                 case 'v':
 873                         if (v_or_q && v_or_q != 'v')
 874                                 help(1);
 875                         details_fptr_vars = true;
 876                         details_fptr_consts = true;
 877                         v_or_q = 'v';
 878                         break;
 879                 case 'q':
 880                         if (v_or_q && v_or_q != 'q')
 881                                 help(1);
 882                         details_fptr_vars = false;
 883                         details_fptr_consts = false;
 884                         v_or_q = 'q';
 885                         break;
 886                 case 'h':
 887                         help(0);
 888                         return 0;
 889                 default:
 890                         help(1);
 891                 }
 892         }
 893
 894         if (optind != argc - 1)
 895                 help(1);
 896
 897         inp = argv[optind];
 898
 899         LLVMMemoryBufferRef memoryBuffer;
 900         char *message;
 901         int ret;
 902
 903         // check if we are to read our input file from stdin
 904         if (!strcmp(inp, "-")) {
 905                 inp = "<stdin>";
 906                 ret = LLVMCreateMemoryBufferWithSTDIN(&memoryBuffer, &message);
 907         } else {
 908                 ret = LLVMCreateMemoryBufferWithContentsOfFile(
 909                         inp, &memoryBuffer, &message);
 910         }
 911
 912         if (ret) {
 913                 fprintf(stderr, "failed to open %s: %s\n", inp, message);
 914                 free(message);
 915                 return 1;
 916         }
 917
 918         // now create our module using the memorybuffer
 919         LLVMModuleRef module;
 920         if (LLVMParseBitcode2(memoryBuffer, &module)) {
 921                 fprintf(stderr, "%s: invalid bitcode\n", inp);
 922                 LLVMDisposeMemoryBuffer(memoryBuffer);
 923                 return 1;
 924         }
 925
 926         // done with the memory buffer now, so dispose of it
 927         LLVMDisposeMemoryBuffer(memoryBuffer);
 928
 929         dbginfo = dbginfo_load(module);
 930
 931         struct json_object *js_root, *js_funcs, *js_special;
 932
 933         js_root = json_object_new_object();
 934         js_funcs = json_object_new_object();
 935         json_object_object_add(js_root, "functions", js_funcs);
 936         js_special = json_object_new_object();
 937         json_object_object_add(js_root, "special", js_special);
 938
 939         // loop through all the functions in the module
 940         for (LLVMValueRef function = LLVMGetFirstFunction(module); function;
 941              function = LLVMGetNextFunction(function)) {
 942                 if (LLVMIsDeclaration(function))
 943                         continue;
 944
 945                 process_fn(js_funcs, js_special, function);
 946         }
 947
 948         if (out) {
 949                 char tmpout[strlen(out) + 5];
 950
 951                 snprintf(tmpout, sizeof(tmpout), "%s.tmp", out);
 952                 ret = json_object_to_file_ext(tmpout, js_root,
 953                                         JSON_C_TO_STRING_PRETTY |
 954                                         JSON_C_TO_STRING_PRETTY_TAB |
 955                                         JSON_C_TO_STRING_NOSLASHESCAPE);
 956                 if (ret < 0) {
 957                         fprintf(stderr, "could not write JSON to file\n");
 958                         return 1;
 959                 }
 960                 if (rename(tmpout, out)) {
 961                         fprintf(stderr, "could not rename JSON output: %s\n",
 962                                 strerror(errno));
 963                         unlink(tmpout);
 964                         return 1;
 965                 }
 966         } else {
 967                 ret = json_object_to_fd(1, js_root,
 968                                         JSON_C_TO_STRING_PRETTY |
 969                                         JSON_C_TO_STRING_PRETTY_TAB |
 970                                         JSON_C_TO_STRING_NOSLASHESCAPE);
 971                 if (ret < 0) {
 972                         fprintf(stderr, "could not write JSON to stdout\n");
 973                         return 1;
 974                 }
 975         }
 976
 977         LLVMDisposeModule(module);
 978
 979         return 0;
 980 }