1#!/usr/bin/python 2 3# Copyright (C) 2013 Oracle. 4# 5# Licensed under the Open Software License version 1.1 6 7import sqlite3 8import sys 9import re 10 11try: 12 con = sqlite3.connect('smatch_db.sqlite') 13except sqlite3.Error, e: 14 print "Error %s:" % e.args[0] 15 sys.exit(1) 16 17def usage(): 18 print "%s" %(sys.argv[0]) 19 print "<function> - how a function is called" 20 print "return_states <function> - what a function returns" 21 print "call_tree <function> - show the call tree" 22 print "where <struct_type> <member> - where a struct member is set" 23 print "type_size <struct_type> <member> - how a struct member is allocated" 24 print "data_info <struct_type> <member> - information about a given data type" 25 print "function_ptr <function> - which function pointers point to this" 26 print "trace_param <function> <param> - trace where a parameter came from" 27 print "locals <file> - print the local values in a file." 28 sys.exit(1) 29 30function_ptrs = [] 31searched_ptrs = [] 32def get_function_pointers_helper(func): 33 cur = con.cursor() 34 cur.execute("select distinct ptr from function_ptr where function = '%s';" %(func)) 35 for row in cur: 36 ptr = row[0] 37 if ptr in function_ptrs: 38 continue 39 function_ptrs.append(ptr) 40 if not ptr in searched_ptrs: 41 searched_ptrs.append(ptr) 42 get_function_pointers_helper(ptr) 43 44def get_function_pointers(func): 45 global function_ptrs 46 global searched_ptrs 47 function_ptrs = [func] 48 searched_ptrs = [func] 49 get_function_pointers_helper(func) 50 return function_ptrs 51 52db_types = { 0: "INTERNAL", 53 101: "PARAM_CLEARED", 54 103: "PARAM_LIMIT", 55 104: "PARAM_FILTER", 56 1001: "PARAM_VALUE", 57 1002: "BUF_SIZE", 58 1003: "USER_DATA", 59 1004: "CAPPED_DATA", 60 1005: "RETURN_VALUE", 61 1006: "DEREFERENCE", 62 1007: "RANGE_CAP", 63 1008: "LOCK_HELD", 64 1009: "LOCK_RELEASED", 65 1010: "ABSOLUTE_LIMITS", 66 1012: "PARAM_ADD", 67 1013: "PARAM_FREED", 68 1014: "DATA_SOURCE", 69 1015: "FUZZY_MAX", 70 1016: "STR_LEN", 71 1017: "ARRAY_LEN", 72 1018: "CAPABLE", 73 1019: "NS_CAPABLE", 74 1022: "TYPE_LINK", 75 1023: "UNTRACKED_PARAM", 76 1024: "CULL_PATH", 77 1025: "PARAM_SET", 78 1026: "PARAM_USED", 79 1027: "BYTE_UNITS", 80 1028: "COMPARE_LIMIT", 81 1029: "PARAM_COMPARE", 82 8017: "USER_DATA2", 83 8018: "NO_OVERFLOW", 84 8019: "NO_OVERFLOW_SIMPLE", 85 8020: "LOCKED", 86 8021: "UNLOCKED", 87 8023: "ATOMIC_INC", 88 8024: "ATOMIC_DEC", 89}; 90 91def add_range(rl, min_val, max_val): 92 check_next = 0 93 done = 0 94 ret = [] 95 idx = 0 96 97 if len(rl) == 0: 98 return [[min_val, max_val]] 99 100 for idx in range(len(rl)): 101 cur_min = rl[idx][0] 102 cur_max = rl[idx][1] 103 104 # we already merged the new range but we might need to change later 105 # ranges if they over lap with more than one 106 if check_next: 107 # join with added range 108 if max_val + 1 == cur_min: 109 ret[len(ret) - 1][1] = cur_max 110 done = 1 111 break 112 # don't overlap 113 if max_val < cur_min: 114 ret.append([cur_min, cur_max]) 115 done = 1 116 break 117 # partially overlap 118 if max_val < cur_max: 119 ret[len(ret) - 1][1] = cur_max 120 done = 1 121 break 122 # completely overlap 123 continue 124 125 # join 2 ranges into one 126 if max_val + 1 == cur_min: 127 ret.append([min_val, cur_max]) 128 done = 1 129 break 130 # range is entirely below 131 if max_val < cur_min: 132 ret.append([min_val, max_val]) 133 ret.append([cur_min, cur_max]) 134 done = 1 135 break 136 # range is partially below 137 if min_val < cur_min: 138 if max_val <= cur_max: 139 ret.append([min_val, cur_max]) 140 done = 1 141 break 142 else: 143 ret.append([min_val, max_val]) 144 check_next = 1 145 continue 146 # range already included 147 if max_val <= cur_max: 148 ret.append([cur_min, cur_max]) 149 done = 1 150 break; 151 # range partially above 152 if min_val <= cur_max: 153 ret.append([cur_min, max_val]) 154 check_next = 1 155 continue 156 # join 2 ranges on the other side 157 if min_val - 1 == cur_max: 158 ret.append([cur_min, max_val]) 159 check_next = 1 160 continue 161 # range is above 162 ret.append([cur_min, cur_max]) 163 164 if idx + 1 < len(rl): # we hit a break statement 165 ret = ret + rl[idx + 1:] 166 elif done: # we hit a break on the last iteration 167 pass 168 elif not check_next: # it's past the end of the rl 169 ret.append([min_val, max_val]) 170 171 return ret; 172 173def rl_union(rl1, rl2): 174 ret = [] 175 for r in rl1: 176 ret = add_range(ret, r[0], r[1]) 177 for r in rl2: 178 ret = add_range(ret, r[0], r[1]) 179 180 if (rl1 or rl2) and not ret: 181 print "bug: merging %s + %s gives empty" %(rl1, rl2) 182 183 return ret 184 185def txt_to_val(txt): 186 if txt == "s64min": 187 return -(2**63) 188 elif txt == "s32min": 189 return -(2**31) 190 elif txt == "s16min": 191 return -(2**15) 192 elif txt == "s64max": 193 return 2**63 - 1 194 elif txt == "s32max": 195 return 2**31 - 1 196 elif txt == "s16max": 197 return 2**15 - 1 198 elif txt == "u64max": 199 return 2**64 - 1 200 elif txt == "u32max": 201 return 2**32 - 1 202 elif txt == "u16max": 203 return 2**16 - 1 204 else: 205 try: 206 return int(txt) 207 except ValueError: 208 return 0 209 210def val_to_txt(val): 211 if val == -(2**63): 212 return "s64min" 213 elif val == -(2**31): 214 return "s32min" 215 elif val == -(2**15): 216 return "s16min" 217 elif val == 2**63 - 1: 218 return "s64max" 219 elif val == 2**31 - 1: 220 return "s32max" 221 elif val == 2**15 - 1: 222 return "s16max" 223 elif val == 2**64 - 1: 224 return "u64max" 225 elif val == 2**32 - 1: 226 return "u32max" 227 elif val == 2**16 - 1: 228 return "u16max" 229 elif val < 0: 230 return "(%d)" %(val) 231 else: 232 return "%d" %(val) 233 234def get_next_str(txt): 235 val = "" 236 parsed = 0 237 238 if txt[0] == '(': 239 parsed += 1 240 for char in txt[1:]: 241 if char == ')': 242 break 243 parsed += 1 244 val = txt[1:parsed] 245 parsed += 1 246 elif txt[0] == 's' or txt[0] == 'u': 247 parsed += 6 248 val = txt[:parsed] 249 else: 250 if txt[0] == '-': 251 parsed += 1 252 for char in txt[parsed:]: 253 if char == '-': 254 break 255 parsed += 1 256 val = txt[:parsed] 257 return [parsed, val] 258 259def txt_to_rl(txt): 260 if len(txt) == 0: 261 return [] 262 263 ret = [] 264 pairs = txt.split(",") 265 for pair in pairs: 266 cnt, min_str = get_next_str(pair) 267 if cnt == len(pair): 268 max_str = min_str 269 else: 270 cnt, max_str = get_next_str(pair[cnt + 1:]) 271 min_val = txt_to_val(min_str) 272 max_val = txt_to_val(max_str) 273 ret.append([min_val, max_val]) 274 275# Hm... Smatch won't call INT_MAX s32max if the variable is unsigned. 276# if txt != rl_to_txt(ret): 277# print "bug: converting: text = %s rl = %s internal = %s" %(txt, rl_to_txt(ret), ret) 278 279 return ret 280 281def rl_to_txt(rl): 282 ret = "" 283 for idx in range(len(rl)): 284 cur_min = rl[idx][0] 285 cur_max = rl[idx][1] 286 287 if idx != 0: 288 ret += "," 289 290 if cur_min == cur_max: 291 ret += val_to_txt(cur_min) 292 else: 293 ret += val_to_txt(cur_min) 294 ret += "-" 295 ret += val_to_txt(cur_max) 296 return ret 297 298def type_to_str(type_int): 299 300 t = int(type_int) 301 if db_types.has_key(t): 302 return db_types[t] 303 return type_int 304 305def type_to_int(type_string): 306 for k in db_types.keys(): 307 if db_types[k] == type_string: 308 return k 309 return -1 310 311def display_caller_info(printed, cur, param_names): 312 for txt in cur: 313 if not printed: 314 print "file | caller | function | type | parameter | key | value |" 315 printed = 1 316 317 parameter = int(txt[6]) 318 key = txt[7] 319 if len(param_names) and parameter in param_names: 320 key = key.replace("$", param_names[parameter]) 321 322 print "%20s | %20s | %20s |" %(txt[0], txt[1], txt[2]), 323 print " %10s |" %(type_to_str(txt[5])), 324 print " %d | %s | %s" %(parameter, key, txt[8]) 325 return printed 326 327def get_caller_info(filename, ptrs, my_type): 328 cur = con.cursor() 329 param_names = get_param_names(filename, func) 330 printed = 0 331 type_filter = "" 332 if my_type != "": 333 type_filter = "and type = %d" %(type_to_int(my_type)) 334 for ptr in ptrs: 335 cur.execute("select * from caller_info where function = '%s' %s;" %(ptr, type_filter)) 336 printed = display_caller_info(printed, cur, param_names) 337 338def print_caller_info(filename, func, my_type = ""): 339 ptrs = get_function_pointers(func) 340 get_caller_info(filename, ptrs, my_type) 341 342def merge_values(param_names, vals, cur): 343 for txt in cur: 344 parameter = int(txt[0]) 345 name = txt[1] 346 rl = txt_to_rl(txt[2]) 347 if parameter in param_names: 348 name = name.replace("$", param_names[parameter]) 349 350 if not parameter in vals: 351 vals[parameter] = {} 352 353 # the first item on the list is the number of rows. it's incremented 354 # every time we call merge_values(). 355 if name in vals[parameter]: 356 vals[parameter][name] = [vals[parameter][name][0] + 1, rl_union(vals[parameter][name][1], rl)] 357 else: 358 vals[parameter][name] = [1, rl] 359 360def get_param_names(filename, func): 361 cur = con.cursor() 362 param_names = {} 363 cur.execute("select parameter, value from parameter_name where file = '%s' and function = '%s';" %(filename, func)) 364 for txt in cur: 365 parameter = int(txt[0]) 366 name = txt[1] 367 param_names[parameter] = name 368 if len(param_names): 369 return param_names 370 371 cur.execute("select parameter, value from parameter_name where function = '%s';" %(func)) 372 for txt in cur: 373 parameter = int(txt[0]) 374 name = txt[1] 375 param_names[parameter] = name 376 return param_names 377 378def get_caller_count(ptrs): 379 cur = con.cursor() 380 count = 0 381 for ptr in ptrs: 382 cur.execute("select count(distinct(call_id)) from caller_info where function = '%s';" %(ptr)) 383 for txt in cur: 384 count += int(txt[0]) 385 return count 386 387def print_merged_caller_values(filename, func, ptrs, param_names, call_cnt): 388 cur = con.cursor() 389 vals = {} 390 for ptr in ptrs: 391 cur.execute("select parameter, key, value from caller_info where function = '%s' and type = %d;" %(ptr, type_to_int("PARAM_VALUE"))) 392 merge_values(param_names, vals, cur); 393 394 for param in sorted(vals): 395 for name in sorted(vals[param]): 396 if vals[param][name][0] != call_cnt: 397 continue 398 print "%d %s -> %s" %(param, name, rl_to_txt(vals[param][name][1])) 399 400 401def print_unmerged_caller_values(filename, func, ptrs, param_names): 402 cur = con.cursor() 403 for ptr in ptrs: 404 prev = -1 405 cur.execute("select file, caller, call_id, parameter, key, value from caller_info where function = '%s' and type = %d;" %(ptr, type_to_int("PARAM_VALUE"))) 406 for filename, caller, call_id, parameter, name, value in cur: 407 if prev != int(call_id): 408 prev = int(call_id) 409 410 parameter = int(parameter) 411 if parameter < len(param_names): 412 name = name.replace("$", param_names[parameter]) 413 else: 414 name = name.replace("$", "$%d" %(parameter)) 415 416 print "%s | %s | %s | %s" %(filename, caller, name, value) 417 print "==========================" 418 419def print_caller_values(filename, func, ptrs): 420 param_names = get_param_names(filename, func) 421 call_cnt = get_caller_count(ptrs) 422 423 print_merged_caller_values(filename, func, ptrs, param_names, call_cnt) 424 print "==========================" 425 print_unmerged_caller_values(filename, func, ptrs, param_names) 426 427def caller_info_values(filename, func): 428 ptrs = get_function_pointers(func) 429 print_caller_values(filename, func, ptrs) 430 431def print_return_states(func): 432 cur = con.cursor() 433 cur.execute("select * from return_states where function = '%s';" %(func)) 434 count = 0 435 for txt in cur: 436 printed = 1 437 if count == 0: 438 print "file | function | return_id | return_value | type | param | key | value |" 439 count += 1 440 print "%s | %s | %2s | %13s" %(txt[0], txt[1], txt[3], txt[4]), 441 print "| %13s |" %(type_to_str(txt[6])), 442 print " %2d | %20s | %20s |" %(txt[7], txt[8], txt[9]) 443 444def print_return_implies(func): 445 cur = con.cursor() 446 cur.execute("select * from return_implies where function = '%s';" %(func)) 447 count = 0 448 for txt in cur: 449 if not count: 450 print "file | function | type | param | key | value |" 451 count += 1 452 print "%15s | %15s" %(txt[0], txt[1]), 453 print "| %15s" %(type_to_str(txt[4])), 454 print "| %3d | %s | %15s |" %(txt[5], txt[6], txt[7]) 455 456def print_type_size(struct_type, member): 457 cur = con.cursor() 458 cur.execute("select * from type_size where type like '(struct %s)->%s';" %(struct_type, member)) 459 print "type | size" 460 for txt in cur: 461 print "%-15s | %s" %(txt[0], txt[1]) 462 463 cur.execute("select * from function_type_size where type like '(struct %s)->%s';" %(struct_type, member)) 464 print "file | function | type | size" 465 for txt in cur: 466 print "%-15s | %-15s | %-15s | %s" %(txt[0], txt[1], txt[2], txt[3]) 467 468def print_data_info(struct_type, member): 469 cur = con.cursor() 470 cur.execute("select * from data_info where data like '(struct %s)->%s';" %(struct_type, member)) 471 print "file | data | type | value" 472 for txt in cur: 473 print "%-15s | %-15s | %-15s | %s" %(txt[0], txt[1], type_to_str(txt[2]), txt[3]) 474 475def print_fn_ptrs(func): 476 ptrs = get_function_pointers(func) 477 if not ptrs: 478 return 479 print "%s = " %(func), 480 print(ptrs) 481 482def print_functions(member): 483 cur = con.cursor() 484 cur.execute("select * from function_ptr where ptr like '%%->%s';" %(member)) 485 print "File | Pointer | Function | Static" 486 for txt in cur: 487 print "%-15s | %-15s | %-15s | %s" %(txt[0], txt[2], txt[1], txt[3]) 488 489def get_callers(func): 490 ret = [] 491 cur = con.cursor() 492 ptrs = get_function_pointers(func) 493 for ptr in ptrs: 494 cur.execute("select distinct caller from caller_info where function = '%s';" %(ptr)) 495 for row in cur: 496 ret.append(row[0]) 497 return ret 498 499printed_funcs = [] 500def call_tree_helper(func, indent = 0): 501 global printed_funcs 502 if func in printed_funcs: 503 return 504 print "%s%s()" %(" " * indent, func) 505 if func == "too common": 506 return 507 if indent > 6: 508 return 509 printed_funcs.append(func) 510 callers = get_callers(func) 511 if len(callers) >= 20: 512 print "Over 20 callers for %s()" %(func) 513 return 514 for caller in callers: 515 call_tree_helper(caller, indent + 2) 516 517def print_call_tree(func): 518 global printed_funcs 519 printed_funcs = [] 520 call_tree_helper(func) 521 522def function_type_value(struct_type, member): 523 cur = con.cursor() 524 cur.execute("select * from function_type_value where type like '(struct %s)->%s';" %(struct_type, member)) 525 for txt in cur: 526 print "%-30s | %-30s | %s | %s" %(txt[0], txt[1], txt[2], txt[3]) 527 528def trace_callers(func, param): 529 sources = [] 530 prev_type = 0 531 532 cur = con.cursor() 533 ptrs = get_function_pointers(func) 534 for ptr in ptrs: 535 cur.execute("select type, caller, value from caller_info where function = '%s' and (type = 0 or type = 1014 or type = 1028) and (parameter = -1 or parameter = %d);" %(ptr, param)) 536 for row in cur: 537 data_type = int(row[0]) 538 if data_type == 1014: 539 sources.append((row[1], row[2])) 540 elif data_type == 1028: 541 sources.append(("%", row[2])) # hack... 542 elif data_type == 0 and prev_type == 0: 543 sources.append((row[1], "")) 544 prev_type = data_type 545 return sources 546 547def trace_param_helper(func, param, indent = 0): 548 global printed_funcs 549 if func in printed_funcs: 550 return 551 print "%s%s(param %d)" %(" " * indent, func, param) 552 if func == "too common": 553 return 554 if indent > 20: 555 return 556 printed_funcs.append(func) 557 sources = trace_callers(func, param) 558 for path in sources: 559 560 if len(path[1]) and path[1][0] == 'p' and path[1][1] == ' ': 561 p = int(path[1][2:]) 562 trace_param_helper(path[0], p, indent + 2) 563 elif len(path[0]) and path[0][0] == '%': 564 print " %s%s" %(" " * indent, path[1]) 565 else: 566 print "* %s%s %s" %(" " * (indent - 1), path[0], path[1]) 567 568def trace_param(func, param): 569 global printed_funcs 570 printed_funcs = [] 571 print "tracing %s %d" %(func, param) 572 trace_param_helper(func, param) 573 574def print_locals(filename): 575 cur = con.cursor() 576 cur.execute("select file,data,value from data_info where file = '%s' and type = 8029 and value != 0;" %(filename)) 577 for txt in cur: 578 print "%s | %s | %s" %(txt[0], txt[1], txt[2]) 579 580def constraint(struct_type, member): 581 cur = con.cursor() 582 cur.execute("select * from constraints_required where data like '(struct %s)->%s' or bound like '(struct %s)->%s';" %(struct_type, member, struct_type, member)) 583 for txt in cur: 584 print "%-30s | %-30s | %s | %s" %(txt[0], txt[1], txt[2], txt[3]) 585 586if len(sys.argv) < 2: 587 usage() 588 589if len(sys.argv) == 2: 590 func = sys.argv[1] 591 print_caller_info("", func) 592elif sys.argv[1] == "call_info": 593 if len(sys.argv) != 4: 594 usage() 595 filename = sys.argv[2] 596 func = sys.argv[3] 597 caller_info_values(filename, func) 598 print_caller_info(filename, func) 599elif sys.argv[1] == "user_data": 600 func = sys.argv[2] 601 print_caller_info(filename, func, "USER_DATA") 602elif sys.argv[1] == "param_value": 603 func = sys.argv[2] 604 print_caller_info(filename, func, "PARAM_VALUE") 605elif sys.argv[1] == "function_ptr" or sys.argv[1] == "fn_ptr": 606 func = sys.argv[2] 607 print_fn_ptrs(func) 608elif sys.argv[1] == "return_states": 609 func = sys.argv[2] 610 print_return_states(func) 611 print "================================================" 612 print_return_implies(func) 613elif sys.argv[1] == "return_implies": 614 func = sys.argv[2] 615 print_return_implies(func) 616elif sys.argv[1] == "type_size" or sys.argv[1] == "buf_size": 617 struct_type = sys.argv[2] 618 member = sys.argv[3] 619 print_type_size(struct_type, member) 620elif sys.argv[1] == "data_info": 621 struct_type = sys.argv[2] 622 member = sys.argv[3] 623 print_data_info(struct_type, member) 624elif sys.argv[1] == "call_tree": 625 func = sys.argv[2] 626 print_call_tree(func) 627elif sys.argv[1] == "where": 628 if len(sys.argv) == 3: 629 struct_type = "%" 630 member = sys.argv[2] 631 elif len(sys.argv) == 4: 632 struct_type = sys.argv[2] 633 member = sys.argv[3] 634 function_type_value(struct_type, member) 635elif sys.argv[1] == "local": 636 filename = sys.argv[2] 637 variable = "" 638 if len(sys.argv) == 4: 639 variable = sys.argv[3] 640 local_values(filename, variable) 641elif sys.argv[1] == "functions": 642 member = sys.argv[2] 643 print_functions(member) 644elif sys.argv[1] == "trace_param": 645 if len(sys.argv) != 4: 646 usage() 647 func = sys.argv[2] 648 param = int(sys.argv[3]) 649 trace_param(func, param) 650elif sys.argv[1] == "locals": 651 if len(sys.argv) != 3: 652 usage() 653 filename = sys.argv[2] 654 print_locals(filename); 655elif sys.argv[1] == "constraint": 656 if len(sys.argv) == 3: 657 struct_type = "%" 658 member = sys.argv[2] 659 elif len(sys.argv) == 4: 660 struct_type = sys.argv[2] 661 member = sys.argv[3] 662 constraint(struct_type, member) 663elif sys.argv[1] == "test": 664 filename = sys.argv[2] 665 func = sys.argv[3] 666 caller_info_values(filename, func) 667else: 668 usage() 669