Home | History | Annotate | Download | only in tsan 
      1 /* Copyright (c) 2008-2010, Google Inc.
      2  * All rights reserved.
      3  *
      4  * Redistribution and use in source and binary forms, with or without
      5  * modification, are permitted provided that the following conditions are
      6  * met:
      7  *
      8  *     * Redistributions of source code must retain the above copyright
      9  * notice, this list of conditions and the following disclaimer.
     10  *     * Neither the name of Google Inc. nor the names of its
     11  * contributors may be used to endorse or promote products derived from
     12  * this software without specific prior written permission.
     13  *
     14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     15  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     16  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     17  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     18  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     19  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     20  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     25  */
     26 
     27 // This file is part of ThreadSanitizer, a dynamic data race detector.
     28 // Author: Evgeniy Stepanov.
     29 
     30 // This file contains the parser for valgrind-compatible suppressions.
     31 
     32 #include "suppressions.h"
     33 
     34 // TODO(eugenis): convert checks to warning messages.
     35 // TODO(eugenis): write tests for incorrect syntax.
     36 
     37 enum LocationType {
     38   LT_STAR,  // ...
     39   LT_OBJ,  // obj:
     40   LT_FUN,  // fun:
     41 };
     42 
     43 struct Location {
     44   LocationType type;
     45   string name;
     46 };
     47 
     48 struct StackTraceTemplate {
     49   vector<Location> locations;
     50 };
     51 
     52 struct Suppression {
     53   string name;
     54   set<string> tools;
     55   string warning_name;
     56   // Extra information available for some suppression types.
     57   // ex.: Memcheck:Param
     58   string extra;
     59   vector<StackTraceTemplate> templates;
     60 };
     61 
     62 class Parser {
     63  public:
     64   explicit Parser(const string &str)
     65       : buffer_(str), next_(buffer_.c_str()),
     66         end_(buffer_.c_str() + buffer_.size()), line_no_(0), error_(false) {}
     67 
     68   bool NextSuppression(Suppression* suppression);
     69   bool GetError();
     70   string GetErrorString();
     71   int GetLineNo();
     72 
     73  private:
     74   bool Eof() { return next_ >= end_; }
     75   string NextLine();
     76   string NextLineSkipComments();
     77   void PutBackSkipComments(string line);
     78   bool ParseSuppressionToolsLine(Suppression* supp, string line);
     79   bool IsExtraLine(string line);
     80   bool ParseStackTraceLine(StackTraceTemplate* trace, string line);
     81   bool NextStackTraceTemplate(StackTraceTemplate* trace, bool* last);
     82 
     83   void SetError(string desc);
     84 
     85   const string& buffer_;
     86   const char* next_;
     87   const char* end_;
     88   stack<string> put_back_stack_;
     89 
     90   int line_no_;
     91   bool error_;
     92   string error_string_;
     93 };
     94 
     95 #define PARSER_CHECK(cond, desc) do {\
     96     if (!(cond)) {\
     97       SetError(desc);\
     98       return false;\
     99     }} while (0)
    100 
    101 void Parser::SetError(string desc) {
    102   error_ = true;
    103   error_string_ = desc;
    104 }
    105 
    106 bool Parser::GetError() {
    107   return error_;
    108 }
    109 
    110 string Parser::GetErrorString() {
    111   return error_string_;
    112 }
    113 
    114 int Parser::GetLineNo() {
    115   return line_no_;
    116 }
    117 
    118 string Parser::NextLine() {
    119   const char* first = next_;
    120   while (!Eof() && *next_ != '\n') {
    121     ++next_;
    122   }
    123   string line(first, next_ - first);
    124   if (*next_ == '\n') {
    125     ++next_;
    126   }
    127   ++line_no_;
    128   return line;
    129 }
    130 
    131 string Parser::NextLineSkipComments() {
    132   string line;
    133   if (!put_back_stack_.empty()) {
    134     line = put_back_stack_.top();
    135     put_back_stack_.pop();
    136     return line;
    137   }
    138   while (!Eof()) {
    139     line = NextLine();
    140     // Skip empty lines.
    141     if (line.empty())
    142       continue;
    143     // Skip comments.
    144     if (line[0] == '#')
    145       continue;
    146     const char* p = line.c_str();
    147     const char* e = p + line.size();
    148     // Strip whitespace.
    149     while (p < e && (*p == ' ' || *p == '\t'))
    150       ++p;
    151     if (p >= e)
    152       continue;
    153     const char* last = e - 1;
    154     while (last > p && (*last == ' ' || *last == '\t'))
    155       --last;
    156     return string(p, last - p + 1);
    157   }
    158   return "";
    159 }
    160 
    161 void Parser::PutBackSkipComments(string line) {
    162   put_back_stack_.push(line);
    163 }
    164 
    165 bool Parser::ParseSuppressionToolsLine(Suppression* supp, string line) {
    166   size_t idx = line.find(':');
    167   PARSER_CHECK(idx != string::npos, "expected ':' in tools line");
    168   string s1 = line.substr(0, idx);
    169   string s2 = line.substr(idx + 1);
    170   PARSER_CHECK(!s1.empty(), "expected non-empty tool(s) name");
    171   PARSER_CHECK(!s2.empty(), "expected non-empty warning name");
    172   size_t idx2;
    173   while ((idx2 = s1.find(',')) != string::npos) {
    174     supp->tools.insert(s1.substr(0, idx2));
    175     s1.erase(0, idx2 + 1);
    176   }
    177   supp->tools.insert(s1);
    178   supp->warning_name = s2;
    179   return true;
    180 }
    181 
    182 bool Parser::ParseStackTraceLine(StackTraceTemplate* trace, string line) {
    183   if (line == "...") {
    184     Location location = {LT_STAR, ""};
    185     trace->locations.push_back(location);
    186     return true;
    187   } else {
    188     size_t idx = line.find(':');
    189     PARSER_CHECK(idx != string::npos, "expected ':' in stack trace line");
    190     string s1 = line.substr(0, idx);
    191     string s2 = line.substr(idx + 1);
    192     if (s1 == "obj") {
    193       Location location = {LT_OBJ, s2};
    194       trace->locations.push_back(location);
    195       return true;
    196     } else if (s1 == "fun") {
    197       Location location = {LT_FUN, s2};
    198       // A suppression frame can only have ( or ) if it comes from Objective-C,
    199       // i.e. starts with +[ or -[ or =[
    200       PARSER_CHECK(s2.find_first_of("()") == string::npos ||
    201                    (s2[1] == '[' && strchr("+-=", s2[0]) != NULL),
    202                    "'fun:' lines can't contain '()'");
    203       PARSER_CHECK(s2.find_first_of("<>") == string::npos,
    204                    "'fun:' lines can't contain '<>'");
    205       trace->locations.push_back(location);
    206       return true;
    207     } else {
    208       SetError("bad stack trace line");
    209       return false;
    210     }
    211   }
    212 }
    213 
    214 // Checks if this line can not be parsed by Parser::NextStackTraceTemplate
    215 // and, therefore, is an extra information for the suppression.
    216 bool Parser::IsExtraLine(string line) {
    217   if (line == "..." || line == "{" || line == "}")
    218     return false;
    219   if (line.size() < 4)
    220     return true;
    221   string prefix = line.substr(0, 4);
    222   return !(prefix == "obj:" || prefix == "fun:");
    223 }
    224 
    225 bool Parser::NextStackTraceTemplate(StackTraceTemplate* trace,
    226     bool* last_stack_trace) {
    227   string line = NextLineSkipComments();
    228   if (line == "}") {  // No more stack traces in multi-trace syntax
    229     *last_stack_trace = true;
    230     return false;
    231   }
    232 
    233   if (line == "{") {  // A multi-trace syntax
    234     line = NextLineSkipComments();
    235   } else {
    236     *last_stack_trace = true;
    237   }
    238 
    239   while (true) {
    240     if (!ParseStackTraceLine(trace, line))
    241       return false;
    242     line = NextLineSkipComments();
    243     if (line == "}")
    244       break;
    245   }
    246   return true;
    247 }
    248 
    249 bool Parser::NextSuppression(Suppression* supp) {
    250   string line;
    251   line = NextLineSkipComments();
    252   if (line.empty())
    253     return false;
    254   // Opening {
    255   PARSER_CHECK(line == "{", "expected '{'");
    256   // Suppression name.
    257   line = NextLineSkipComments();
    258   PARSER_CHECK(!line.empty(), "expected suppression name");
    259   supp->name = line;
    260   // tool[,tool]:warning_name.
    261   line = NextLineSkipComments();
    262   PARSER_CHECK(!line.empty(), "expected tool[, tool]:warning_name line");
    263   if (!ParseSuppressionToolsLine(supp, line))
    264     return false;
    265   if (0) {  // Not used currently. May still be needed later.
    266     // A possible extra line.
    267     line = NextLineSkipComments();
    268     if (IsExtraLine(line))
    269       supp->extra = line;
    270     else
    271       PutBackSkipComments(line);
    272   }
    273   // Everything else.
    274   bool done = false;
    275   while (!done) {
    276     StackTraceTemplate trace;
    277     if (NextStackTraceTemplate(&trace, &done))
    278       supp->templates.push_back(trace);
    279     if (error_)
    280       return false;
    281   }
    282   // TODO(eugenis): Do we need to check for empty traces?
    283   return true;
    284 }
    285 
    286 struct Suppressions::SuppressionsRep {
    287   vector<Suppression> suppressions;
    288   string error_string_;
    289   int error_line_no_;
    290 };
    291 
    292 Suppressions::Suppressions() : rep_(new SuppressionsRep) {}
    293 
    294 Suppressions::~Suppressions() {
    295   delete rep_;
    296 }
    297 
    298 int Suppressions::ReadFromString(const string &str) {
    299   int sizeBefore = rep_->suppressions.size();
    300   Parser parser(str);
    301   Suppression supp;
    302   while (parser.NextSuppression(&supp)) {
    303     rep_->suppressions.push_back(supp);
    304   }
    305   if (parser.GetError()) {
    306     rep_->error_string_ = parser.GetErrorString();
    307     rep_->error_line_no_ = parser.GetLineNo();
    308     return -1;
    309   }
    310   return rep_->suppressions.size() - sizeBefore;
    311 }
    312 
    313 string Suppressions::GetErrorString() {
    314   return rep_->error_string_;
    315 }
    316 
    317 int Suppressions::GetErrorLineNo() {
    318   return rep_->error_line_no_;
    319 }
    320 
    321 struct MatcherContext {
    322   MatcherContext(
    323       const vector<string>& function_names_mangled_,
    324       const vector<string>& function_names_demangled_,
    325       const vector<string>& object_names_) :
    326       function_names_mangled(function_names_mangled_),
    327       function_names_demangled(function_names_demangled_),
    328       object_names(object_names_),
    329       tmpl(NULL)
    330   {}
    331 
    332   const vector<string>& function_names_mangled;
    333   const vector<string>& function_names_demangled;
    334   const vector<string>& object_names;
    335   StackTraceTemplate* tmpl;
    336 };
    337 
    338 static bool MatchStackTraceRecursive(MatcherContext ctx, int trace_index,
    339     int tmpl_index) {
    340   const int trace_size = ctx.function_names_mangled.size();
    341   const int tmpl_size = ctx.tmpl->locations.size();
    342   while (trace_index < trace_size && tmpl_index < tmpl_size) {
    343     Location& location = ctx.tmpl->locations[tmpl_index];
    344     if (location.type == LT_STAR) {
    345       ++tmpl_index;
    346       while (trace_index < trace_size) {
    347         if (MatchStackTraceRecursive(ctx, trace_index++, tmpl_index))
    348           return true;
    349       }
    350       return false;
    351     } else {
    352       bool match = false;
    353       if (location.type == LT_OBJ) {
    354         match = StringMatch(location.name, ctx.object_names[trace_index]);
    355       } else {
    356         CHECK(location.type == LT_FUN);
    357         match =
    358           StringMatch(location.name, ctx.function_names_mangled[trace_index]) ||
    359           StringMatch(location.name, ctx.function_names_demangled[trace_index]);
    360       }
    361       if (match) {
    362         ++trace_index;
    363         ++tmpl_index;
    364       } else {
    365         return false;
    366       }
    367     }
    368   }
    369   return tmpl_index == tmpl_size;
    370 }
    371 
    372 bool Suppressions::StackTraceSuppressed(string tool_name, string warning_name,
    373     const vector<string>& function_names_mangled,
    374     const vector<string>& function_names_demangled,
    375     const vector<string>& object_names,
    376     string *name_of_suppression) {
    377   MatcherContext ctx(function_names_mangled, function_names_demangled,
    378       object_names);
    379   for (vector<Suppression>::iterator it = rep_->suppressions.begin();
    380        it != rep_->suppressions.end(); ++it) {
    381     if (it->warning_name != warning_name ||
    382         it->tools.find(tool_name) == it->tools.end())
    383       continue;
    384     for (vector<StackTraceTemplate>::iterator it2 = it->templates.begin();
    385          it2 != it->templates.end(); ++it2) {
    386       ctx.tmpl = &*it2;
    387       bool result = MatchStackTraceRecursive(ctx, 0, 0);
    388       if (result) {
    389         *name_of_suppression = it->name;
    390         return true;
    391       }
    392     }
    393   }
    394   return false;
    395 }
    396