sparse.c

   1 /*
   2  * Example trivial client program that uses the sparse library
   3  * to tokenize, preprocess and parse a C file, and prints out
   4  * the results.
   5  *
   6  * Copyright (C) 2003 Transmeta Corp.
   7  *               2003-2004 Linus Torvalds
   8  *
   9  *  Licensed under the Open Software License version 1.1
  10  */
  11 #include <stdarg.h>
  12 #include <stdlib.h>
  13 #include <stdio.h>
  14 #include <string.h>
  15 #include <ctype.h>
  16 #include <unistd.h>
  17 #include <fcntl.h>
  18
  19 #include "lib.h"
  20 #include "allocate.h"
  21 #include "token.h"
  22 #include "parse.h"
  23 #include "symbol.h"
  24 #include "expression.h"
  25 #include "linearize.h"
  26
  27 struct context_check {
  28         int val, val_false;
  29         char name[32];
  30 };
  31
  32 DECLARE_ALLOCATOR(context_check);
  33 DECLARE_PTR_LIST(context_check_list, struct context_check);
  34 DECLARE_PTR_LIST(context_list_list, struct context_check_list);
  35 ALLOCATOR(context_check, "context check list");
  36
  37 static const char *unnamed_context = "<unnamed>";
  38
  39 static const char *context_name(struct context *context)
  40 {
  41         if (context->context && context->context->symbol_name)
  42                 return show_ident(context->context->symbol_name);
  43         return unnamed_context;
  44 }
  45
  46 static void context_add(struct context_check_list **ccl, const char *name,
  47                         int offs, int offs_false)
  48 {
  49         struct context_check *check, *found = NULL;
  50
  51         FOR_EACH_PTR(*ccl, check) {
  52                 if (strcmp(name, check->name))
  53                         continue;
  54                 found = check;
  55                 break;
  56         } END_FOR_EACH_PTR(check);
  57
  58         if (!found) {
  59                 found = __alloc_context_check(0);
  60                 strncpy(found->name, name, sizeof(found->name));
  61                 found->name[sizeof(found->name) - 1] = '\0';
  62                 add_ptr_list(ccl, found);
  63         }
  64         found->val += offs;
  65         found->val_false += offs_false;
  66 }
  67
  68 static int context_list_has(struct context_check_list *ccl,
  69                             struct context_check *c)
  70 {
  71         struct context_check *check;
  72
  73         FOR_EACH_PTR(ccl, check) {
  74                 if (strcmp(c->name, check->name))
  75                         continue;
  76                 return check->val == c->val &&
  77                        check->val_false == c->val_false;
  78         } END_FOR_EACH_PTR(check);
  79
  80         /* not found is equal to 0 */
  81         return c->val == 0 && c->val_false == 0;
  82 }
  83
  84 static int context_lists_equal(struct context_check_list *ccl1,
  85                                struct context_check_list *ccl2)
  86 {
  87         struct context_check *check;
  88
  89         /* can be optimised... */
  90
  91         FOR_EACH_PTR(ccl1, check) {
  92                 if (!context_list_has(ccl2, check))
  93                         return 0;
  94         } END_FOR_EACH_PTR(check);
  95
  96         FOR_EACH_PTR(ccl2, check) {
  97                 if (!context_list_has(ccl1, check))
  98                         return 0;
  99         } END_FOR_EACH_PTR(check);
 100
 101         return 1;
 102 }
 103
 104 static struct context_check_list *checked_copy(struct context_check_list *ccl)
 105 {
 106         struct context_check_list *result = NULL;
 107         struct context_check *c;
 108
 109         FOR_EACH_PTR(ccl, c) {
 110                 context_add(&result, c->name, c->val_false, c->val_false);
 111         } END_FOR_EACH_PTR(c);
 112
 113         return result;
 114 }
 115
 116 #define IMBALANCE_IN "context imbalance in '%s': "
 117 #define DEFAULT_CONTEXT_DESCR "   default context: "
 118
 119 static void get_context_string(char **buf, const char **name)
 120 {
 121         if (strcmp(*name, unnamed_context)) {
 122                 *buf = malloc(strlen(*name) + 16);
 123                 sprintf(*buf, "   context '%s': ", *name);
 124                 *name = *buf;
 125         } else {
 126                 *name = DEFAULT_CONTEXT_DESCR;
 127                 *buf = NULL;
 128         }
 129 }
 130
 131 static int context_list_check(struct entrypoint *ep, struct position pos,
 132                               struct context_check_list *ccl_cur,
 133                               struct context_check_list *ccl_target)
 134 {
 135         struct context_check *c1, *c2;
 136         int cur, tgt;
 137         const char *name;
 138         char *buf;
 139
 140         /* make sure the loop below checks all */
 141         FOR_EACH_PTR(ccl_target, c1) {
 142                 context_add(&ccl_cur, c1->name, 0, 0);
 143         } END_FOR_EACH_PTR(c1);
 144
 145         FOR_EACH_PTR(ccl_cur, c1) {
 146                 cur = c1->val;
 147                 tgt = 0;
 148
 149                 FOR_EACH_PTR(ccl_target, c2) {
 150                         if (strcmp(c2->name, c1->name))
 151                                 continue;
 152                         tgt = c2->val;
 153                         break;
 154                 } END_FOR_EACH_PTR(c2);
 155
 156                 if (cur == tgt || !Wcontext)
 157                         continue;
 158
 159                 if (cur > tgt)
 160                         warning(pos, IMBALANCE_IN "wrong count at exit",
 161                                 show_ident(ep->name->ident));
 162                 else if (cur < tgt)
 163                         warning(pos, IMBALANCE_IN "unexpected unlock",
 164                                 show_ident(ep->name->ident));
 165
 166                 name = c1->name;
 167                 get_context_string(&buf, &name);
 168
 169                 info(pos, "%swanted %d, got %d",
 170                      name, tgt, cur);
 171
 172                 free(buf);
 173
 174                 return -1;
 175         } END_FOR_EACH_PTR(c1);
 176
 177         return 0;
 178 }
 179
 180 static int handle_call(struct entrypoint *ep, struct basic_block *bb,
 181                        struct instruction *insn,
 182                        struct context_check_list *combined)
 183 {
 184         struct context *ctx;
 185         struct context_check *c;
 186         const char *name, *call, *cmp;
 187         char *buf;
 188         int val, ok;
 189
 190         if (!insn->func || !insn->func->sym ||
 191             insn->func->type != PSEUDO_SYM)
 192                 return 0;
 193
 194         /*
 195          * Check all contexts the function wants.
 196          */
 197         FOR_EACH_PTR(insn->func->sym->ctype.contexts, ctx) {
 198                 name = context_name(ctx);
 199                 val = 0;
 200
 201                 FOR_EACH_PTR(combined, c) {
 202                         if (strcmp(c->name, name) == 0) {
 203                                 val = c->val;
 204                                 break;
 205                         }
 206                 } END_FOR_EACH_PTR(c);
 207
 208                 if (ctx->exact) {
 209                         ok = ctx->in == val;
 210                         cmp = "";
 211                 } else {
 212                         ok = ctx->in <= val;
 213                         cmp = ">= ";
 214                 }
 215
 216                 if (!ok && Wcontext) {
 217                         get_context_string(&buf, &name);
 218                         call = strdup(show_ident(insn->func->ident));
 219
 220                         warning(insn->pos, "context problem in '%s': "
 221                                 "'%s' expected different context",
 222                                 show_ident(ep->name->ident), call);
 223
 224                         info(insn->pos, "%swanted %s%d, got %d",
 225                              name, cmp, ctx->in, val);
 226
 227                         free((void *)call);
 228                         free(buf);
 229
 230                         return -1;
 231                 }
 232         } END_FOR_EACH_PTR (ctx);
 233
 234         return 0;
 235 }
 236
 237 static int handle_context(struct entrypoint *ep, struct basic_block *bb,
 238                           struct instruction *insn,
 239                           struct context_check_list **combined)
 240 {
 241         struct context_check *c;
 242         const char *name;
 243         char *buf;
 244         int val, ok;
 245
 246         val = 0;
 247
 248         name = unnamed_context;
 249         if (insn->context_expr)
 250                 name = show_ident(insn->context_expr->symbol_name);
 251
 252         FOR_EACH_PTR(*combined, c) {
 253                 if (strcmp(c->name, name) == 0) {
 254                         val = c->val;
 255                         break;
 256                 }
 257         } END_FOR_EACH_PTR(c);
 258
 259         ok = insn->required <= val;
 260
 261         if (!ok && Wcontext) {
 262                 get_context_string(&buf, &name);
 263
 264                 warning(insn->pos,
 265                         IMBALANCE_IN
 266                         "__context__ statement expected different context",
 267                         show_ident(ep->name->ident));
 268
 269                 info(insn->pos, "%swanted >= %d, got %d",
 270                      name, insn->required, val);
 271
 272                 free(buf);
 273                 return -1;
 274         }
 275
 276         context_add(combined, name, insn->increment, insn->inc_false);
 277
 278         return 0;
 279 }
 280
 281 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb,
 282                             struct context_check_list *ccl_in,
 283                             struct context_check_list *ccl_target,
 284                             int in_false)
 285 {
 286         struct context_check_list *combined = NULL, *done;
 287         struct context_check *c;
 288         struct instruction *insn;
 289         struct multijmp *mj;
 290         int err = -1;
 291
 292         /*
 293          * Recurse in once to catch bad loops.
 294          */
 295         if (bb->context_check_recursion > 1)
 296                 return 0;
 297         bb->context_check_recursion++;
 298
 299         /*
 300          * Abort if we have already checked this block out of the same context.
 301          */
 302         FOR_EACH_PTR(bb->checked_contexts, done) {
 303                 if (context_lists_equal(done, ccl_in))
 304                         return 0;
 305         } END_FOR_EACH_PTR(done);
 306
 307         /*
 308          * We're starting with a completely new local list of contexts, so
 309          * initialise it according to what we got from the parent block.
 310          * That may use either the 'false' or the 'true' part of the context
 311          * for the conditional_context() attribute.
 312          */
 313         FOR_EACH_PTR(ccl_in, c) {
 314                 if (in_false)
 315                         context_add(&combined, c->name, c->val_false, c->val_false);
 316                 else
 317                         context_add(&combined, c->name, c->val, c->val);
 318         } END_FOR_EACH_PTR(c);
 319
 320         /* Add the new context to the list of already-checked contexts */
 321         done = checked_copy(combined);
 322         add_ptr_list(&bb->checked_contexts, done);
 323
 324         /*
 325          * Now walk the instructions for this block, recursing into any
 326          * instructions that have children. We need to have the right
 327          * order so we cannot iterate bb->children instead.
 328          */
 329         FOR_EACH_PTR(bb->insns, insn) {
 330                 switch (insn->opcode) {
 331                 case OP_INLINED_CALL:
 332                 case OP_CALL:
 333                         if (handle_call(ep, bb, insn, combined))
 334                                 goto out;
 335                         break;
 336                 case OP_CONTEXT:
 337                         if (handle_context(ep, bb, insn, &combined))
 338                                 goto out;
 339                         break;
 340                 case OP_BR:
 341                         if (insn->bb_true)
 342                                 if (check_bb_context(ep, insn->bb_true,
 343                                                      combined, ccl_target, 0))
 344                                         goto out;
 345                         if (insn->bb_false)
 346                                 if (check_bb_context(ep, insn->bb_false,
 347                                                      combined, ccl_target, 1))
 348                                         goto out;
 349                         break;
 350                 case OP_SWITCH:
 351                 case OP_COMPUTEDGOTO:
 352                         FOR_EACH_PTR(insn->multijmp_list, mj) {
 353                                 if (check_bb_context(ep, mj->target,
 354                                                      combined, ccl_target, 0))
 355                                         goto out;
 356                         } END_FOR_EACH_PTR(mj);
 357                         break;
 358                 }
 359         } END_FOR_EACH_PTR(insn);
 360
 361         insn = last_instruction(bb->insns);
 362         if (!insn)
 363                 goto out_good;
 364
 365         if (insn->opcode == OP_RET) {
 366                 err = context_list_check(ep, insn->pos, combined, ccl_target);
 367                 goto out;
 368         }
 369
 370  out_good:
 371         err = 0;
 372  out:
 373         /* contents will be freed once we return out of recursion */
 374         free_ptr_list(&combined);
 375         bb->context_check_recursion--;
 376         return err;
 377 }
 378
 379 static void free_bb_context_lists(struct basic_block *bb)
 380 {
 381         struct context_check_list *done;
 382         struct instruction *insn;
 383         struct multijmp *mj;
 384
 385         if (!bb->checked_contexts)
 386                 return;
 387
 388         FOR_EACH_PTR(bb->checked_contexts, done) {
 389                 free_ptr_list(&done);
 390         } END_FOR_EACH_PTR(done);
 391
 392         free_ptr_list(&bb->checked_contexts);
 393
 394         FOR_EACH_PTR(bb->insns, insn) {
 395                 switch (insn->opcode) {
 396                 case OP_BR:
 397                         if (insn->bb_true)
 398                                 free_bb_context_lists(insn->bb_true);
 399                         if (insn->bb_false)
 400                                 free_bb_context_lists(insn->bb_false);
 401                         break;
 402                 case OP_SWITCH:
 403                 case OP_COMPUTEDGOTO:
 404                         FOR_EACH_PTR(insn->multijmp_list, mj) {
 405                                 free_bb_context_lists(mj->target);
 406                         } END_FOR_EACH_PTR(mj);
 407                         break;
 408                 }
 409         } END_FOR_EACH_PTR(insn);
 410 }
 411
 412 static void check_cast_instruction(struct instruction *insn)
 413 {
 414         struct symbol *orig_type = insn->orig_type;
 415         if (orig_type) {
 416                 int old = orig_type->bit_size;
 417                 int new = insn->size;
 418                 int oldsigned = (orig_type->ctype.modifiers & MOD_SIGNED) != 0;
 419                 int newsigned = insn->opcode == OP_SCAST;
 420
 421                 if (new > old) {
 422                         if (oldsigned == newsigned)
 423                                 return;
 424                         if (newsigned)
 425                                 return;
 426                         warning(insn->pos, "cast loses sign");
 427                         return;
 428                 }
 429                 if (new < old) {
 430                         warning(insn->pos, "cast drops bits");
 431                         return;
 432                 }
 433                 if (oldsigned == newsigned) {
 434                         warning(insn->pos, "cast wasn't removed");
 435                         return;
 436                 }
 437                 warning(insn->pos, "cast changes sign");
 438         }
 439 }
 440
 441 static void check_range_instruction(struct instruction *insn)
 442 {
 443         warning(insn->pos, "value out of range");
 444 }
 445
 446 static void check_byte_count(struct instruction *insn, pseudo_t count)
 447 {
 448         if (!count)
 449                 return;
 450         if (count->type == PSEUDO_VAL) {
 451                 long long val = count->value;
 452                 if (val <= 0 || val > 100000)
 453                         warning(insn->pos, "%s with byte count of %lld",
 454                                 show_ident(insn->func->sym->ident), val);
 455                 return;
 456         }
 457         /* OK, we could try to do the range analysis here */
 458 }
 459
 460 static pseudo_t argument(struct instruction *call, unsigned int argno)
 461 {
 462         pseudo_t args[8];
 463         struct ptr_list *arg_list = (struct ptr_list *) call->arguments;
 464
 465         argno--;
 466         if (linearize_ptr_list(arg_list, (void *)args, 8) > argno)
 467                 return args[argno];
 468         return NULL;
 469 }
 470
 471 static void check_memset(struct instruction *insn)
 472 {
 473         check_byte_count(insn, argument(insn, 3));
 474 }
 475
 476 #define check_memcpy check_memset
 477 #define check_ctu check_memset
 478 #define check_cfu check_memset
 479
 480 struct checkfn {
 481         struct ident *id;
 482         void (*check)(struct instruction *insn);
 483 };
 484
 485 static void check_call_instruction(struct instruction *insn)
 486 {
 487         pseudo_t fn = insn->func;
 488         struct ident *ident;
 489         static const struct checkfn check_fn[] = {
 490                 { &memset_ident, check_memset },
 491                 { &memcpy_ident, check_memcpy },
 492                 { &copy_to_user_ident, check_ctu },
 493                 { &copy_from_user_ident, check_cfu },
 494         };
 495         int i;
 496
 497         if (fn->type != PSEUDO_SYM)
 498                 return;
 499         ident = fn->sym->ident;
 500         if (!ident)
 501                 return;
 502         for (i = 0; i < sizeof(check_fn)/sizeof(struct checkfn) ; i++) {
 503                 if (check_fn[i].id != ident)
 504                         continue;
 505                 check_fn[i].check(insn);
 506                 break;
 507         }
 508 }
 509
 510 static void check_one_instruction(struct instruction *insn)
 511 {
 512         switch (insn->opcode) {
 513         case OP_CAST: case OP_SCAST:
 514                 if (verbose)
 515                         check_cast_instruction(insn);
 516                 break;
 517         case OP_RANGE:
 518                 check_range_instruction(insn);
 519                 break;
 520         case OP_CALL:
 521                 check_call_instruction(insn);
 522                 break;
 523         default:
 524                 break;
 525         }
 526 }
 527
 528 static void check_bb_instructions(struct basic_block *bb)
 529 {
 530         struct instruction *insn;
 531         FOR_EACH_PTR(bb->insns, insn) {
 532                 if (!insn->bb)
 533                         continue;
 534                 check_one_instruction(insn);
 535         } END_FOR_EACH_PTR(insn);
 536 }
 537
 538 static void check_instructions(struct entrypoint *ep)
 539 {
 540         struct basic_block *bb;
 541         FOR_EACH_PTR(ep->bbs, bb) {
 542                 check_bb_instructions(bb);
 543         } END_FOR_EACH_PTR(bb);
 544 }
 545
 546 static void check_context(struct entrypoint *ep)
 547 {
 548         struct symbol *sym = ep->name;
 549         struct context *context;
 550         struct context_check_list *ccl_in = NULL, *ccl_target = NULL;
 551
 552         if (Wuninitialized && verbose && ep->entry->bb->needs) {
 553                 pseudo_t pseudo;
 554                 FOR_EACH_PTR(ep->entry->bb->needs, pseudo) {
 555                         if (pseudo->type != PSEUDO_ARG)
 556                                 warning(sym->pos, "%s: possible uninitialized variable (%s)",
 557                                         show_ident(sym->ident), show_pseudo(pseudo));
 558                 } END_FOR_EACH_PTR(pseudo);
 559         }
 560
 561         check_instructions(ep);
 562
 563         FOR_EACH_PTR(sym->ctype.contexts, context) {
 564                 const char *name = context_name(context);
 565
 566                 context_add(&ccl_in, name, context->in, context->in);
 567                 context_add(&ccl_target, name, context->out, context->out_false);
 568                 /* we don't currently check the body of trylock functions */
 569                 if (context->out != context->out_false)
 570                         return;
 571         } END_FOR_EACH_PTR(context);
 572
 573         check_bb_context(ep, ep->entry->bb, ccl_in, ccl_target, 0);
 574         free_ptr_list(&ccl_in);
 575         free_ptr_list(&ccl_target);
 576         free_bb_context_lists(ep->entry->bb);
 577         clear_context_check_alloc();
 578 }
 579
 580 static void check_symbols(struct symbol_list *list)
 581 {
 582         struct symbol *sym;
 583
 584         FOR_EACH_PTR(list, sym) {
 585                 struct entrypoint *ep;
 586
 587                 expand_symbol(sym);
 588                 ep = linearize_symbol(sym);
 589                 if (ep) {
 590                         if (dbg_entry)
 591                                 show_entry(ep);
 592
 593                         check_context(ep);
 594                 }
 595         } END_FOR_EACH_PTR(sym);
 596 }
 597
 598 int main(int argc, char **argv)
 599 {
 600         struct string_list *filelist = NULL;
 601         char *file;
 602
 603         // Expand, linearize and show it.
 604         check_symbols(sparse_initialize(argc, argv, &filelist));
 605         FOR_EACH_PTR_NOTAG(filelist, file) {
 606                 check_symbols(sparse(file));
 607         } END_FOR_EACH_PTR_NOTAG(file);
 608         return 0;
 609 }