Add section headers to SpecialCaseLists

Summary:
Sanitizer blacklist entries currently apply to all sanitizers--there
is no way to specify that an entry should only apply to a specific
sanitizer. This is important for Control Flow Integrity since there are
several different CFI modes that can be enabled at once. For maximum
security, CFI blacklist entries should be scoped to only the specific
CFI mode(s) that entry applies to.

Adding section headers to SpecialCaseLists allows users to specify more
information about list entries, like sanitizer names or other metadata,
like so:

  [section1]
  fun:*fun1*
  [section2|section3]
  fun:*fun23*

The section headers are regular expressions. For backwards compatbility,
blacklist entries entered before a section header are put into the '[*]'
section so that blacklists without sections retain the same behavior.

SpecialCaseList has been modified to also accept a section name when
matching against the blacklist. It has also been modified so the
follow-up change to clang can define a derived class that allows
matching sections by SectionMask instead of by string.

Reviewers: pcc, kcc, eugenis, vsk

Reviewed By: eugenis, vsk

Subscribers: vitalybuka, llvm-commits

Differential Revision: https://reviews.llvm.org/D37924

llvm-svn: 314170

1 files changed, 139 insertions, 75 deletions

diff --git a/llvm/lib/Support/SpecialCaseList.cpp b/llvm/lib/Support/SpecialCaseList.cpp
index 05886eaa8ae..25222b04119 100644
--- a/llvm/lib/Support/SpecialCaseList.cpp
+++ b/llvm/lib/Support/SpecialCaseList.cpp
@@ -17,65 +17,72 @@
 #include "llvm/Support/SpecialCaseList.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
-#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Regex.h"
-#include "llvm/Support/TrigramIndex.h"
 #include <string>
 #include <system_error>
 #include <utility>
 
+#include <stdio.h>
 namespace llvm {
 
-/// Represents a set of regular expressions.  Regular expressions which are
-/// "literal" (i.e. no regex metacharacters) are stored in Strings, while all
-/// others are represented as a single pipe-separated regex in RegEx.  The
-/// reason for doing so is efficiency; StringSet is much faster at matching
-/// literal strings than Regex.
-struct SpecialCaseList::Entry {
-  StringSet<> Strings;
-  TrigramIndex Trigrams;
-  std::unique_ptr<Regex> RegEx;
-
-  bool match(StringRef Query) const {
-    if (Strings.count(Query))
-      return true;
-    if (Trigrams.isDefinitelyOut(Query))
-      return false;
-    return RegEx && RegEx->match(Query);
+bool SpecialCaseList::Matcher::insert(std::string Regexp,
+                                      std::string &REError) {
+  if (Regex::isLiteralERE(Regexp)) {
+    Strings.insert(Regexp);
+    return true;
+  }
+  Trigrams.insert(Regexp);
+
+  // Replace * with .*
+  for (size_t pos = 0; (pos = Regexp.find('*', pos)) != std::string::npos;
+       pos += strlen(".*")) {
+    Regexp.replace(pos, strlen("*"), ".*");
+  }
+
+  // Check that the regexp is valid.
+  Regex CheckRE(Regexp);
+  if (!CheckRE.isValid(REError))
+    return false;
+
+  if (!UncompiledRegEx.empty())
+    UncompiledRegEx += "|";
+  UncompiledRegEx += "^(" + Regexp + ")$";
+  return true;
+}
+
+void SpecialCaseList::Matcher::compile() {
+  if (!UncompiledRegEx.empty()) {
+    RegEx.reset(new Regex(UncompiledRegEx));
+    UncompiledRegEx.clear();
   }
-};
+}
+
+bool SpecialCaseList::Matcher::match(StringRef Query) const {
+  if (Strings.count(Query))
+    return true;
+  if (Trigrams.isDefinitelyOut(Query))
+    return false;
+  return RegEx && RegEx->match(Query);
+}
 
-SpecialCaseList::SpecialCaseList() : Entries(), Regexps(), IsCompiled(false) {}
+SpecialCaseList::SpecialCaseList() : Sections(), IsCompiled(false) {}
 
 std::unique_ptr<SpecialCaseList>
 SpecialCaseList::create(const std::vector<std::string> &Paths,
                         std::string &Error) {
   std::unique_ptr<SpecialCaseList> SCL(new SpecialCaseList());
-  for (const auto &Path : Paths) {
-    ErrorOr<std::unique_ptr<MemoryBuffer>> FileOrErr =
-        MemoryBuffer::getFile(Path);
-    if (std::error_code EC = FileOrErr.getError()) {
-      Error = (Twine("can't open file '") + Path + "': " + EC.message()).str();
-      return nullptr;
-    }
-    std::string ParseError;
-    if (!SCL->parse(FileOrErr.get().get(), ParseError)) {
-      Error = (Twine("error parsing file '") + Path + "': " + ParseError).str();
-      return nullptr;
-    }
-  }
-  SCL->compile();
-  return SCL;
+  if (SCL->createInternal(Paths, Error))
+    return SCL;
+  return nullptr;
 }
 
 std::unique_ptr<SpecialCaseList> SpecialCaseList::create(const MemoryBuffer *MB,
                                                          std::string &Error) {
   std::unique_ptr<SpecialCaseList> SCL(new SpecialCaseList());
-  if (!SCL->parse(MB, Error))
-    return nullptr;
-  SCL->compile();
-  return SCL;
+  if (SCL->createInternal(MB, Error))
+    return SCL;
+  return nullptr;
 }
 
 std::unique_ptr<SpecialCaseList>
@@ -86,15 +93,71 @@ SpecialCaseList::createOrDie(const std::vector<std::string> &Paths) {
   report_fatal_error(Error);
 }
 
-bool SpecialCaseList::parse(const MemoryBuffer *MB, std::string &Error) {
+bool SpecialCaseList::createInternal(const std::vector<std::string> &Paths,
+                                     std::string &Error) {
+  StringMap<size_t> Sections;
+  for (const auto &Path : Paths) {
+    ErrorOr<std::unique_ptr<MemoryBuffer>> FileOrErr =
+        MemoryBuffer::getFile(Path);
+    if (std::error_code EC = FileOrErr.getError()) {
+      Error = (Twine("can't open file '") + Path + "': " + EC.message()).str();
+      return false;
+    }
+    std::string ParseError;
+    if (!parse(FileOrErr.get().get(), Sections, ParseError)) {
+      Error = (Twine("error parsing file '") + Path + "': " + ParseError).str();
+      return false;
+    }
+  }
+  compile();
+  return true;
+}
+
+bool SpecialCaseList::createInternal(const MemoryBuffer *MB,
+                                     std::string &Error) {
+  StringMap<size_t> Sections;
+  if (!parse(MB, Sections, Error))
+    return false;
+  compile();
+  return true;
+}
+
+bool SpecialCaseList::parse(const MemoryBuffer *MB,
+                            StringMap<size_t> &SectionsMap,
+                            std::string &Error) {
   // Iterate through each line in the blacklist file.
   SmallVector<StringRef, 16> Lines;
   SplitString(MB->getBuffer(), Lines, "\n\r");
+
   int LineNo = 1;
+  StringRef Section = "*";
   for (auto I = Lines.begin(), E = Lines.end(); I != E; ++I, ++LineNo) {
     // Ignore empty lines and lines starting with "#"
     if (I->empty() || I->startswith("#"))
       continue;
+
+    // Save section names
+    if (I->startswith("[")) {
+      if (!I->endswith("]")) {
+        Error = (Twine("malformed section header on line ") + Twine(LineNo) +
+                 ": " + *I).str();
+        return false;
+      }
+
+      Section = I->slice(1, I->size() - 1);
+
+      std::string REError;
+      Regex CheckRE(Section);
+      if (!CheckRE.isValid(REError)) {
+        Error =
+            (Twine("malformed regex for section ") + Section + ": '" + REError)
+                .str();
+        return false;
+      }
+
+      continue;
+    }
+
     // Get our prefix and unparsed regexp.
     std::pair<StringRef, StringRef> SplitLine = I->split(":");
     StringRef Prefix = SplitLine.first;
@@ -109,61 +172,62 @@ bool SpecialCaseList::parse(const MemoryBuffer *MB, std::string &Error) {
     std::string Regexp = SplitRegexp.first;
     StringRef Category = SplitRegexp.second;
 
-    // See if we can store Regexp in Strings.
-    auto &Entry = Entries[Prefix][Category];
-    if (Regex::isLiteralERE(Regexp)) {
-      Entry.Strings.insert(Regexp);
-      continue;
-    }
-    Entry.Trigrams.insert(Regexp);
-
-    // Replace * with .*
-    for (size_t pos = 0; (pos = Regexp.find('*', pos)) != std::string::npos;
-         pos += strlen(".*")) {
-      Regexp.replace(pos, strlen("*"), ".*");
+    // Create this section if it has not been seen before.
+    if (SectionsMap.find(Section) == SectionsMap.end()) {
+      std::unique_ptr<Matcher> M = make_unique<Matcher>();
+      std::string REError;
+      if (!M->insert(Section, REError)) {
+        Error = (Twine("malformed section ") + Section + ": '" + REError).str();
+        return false;
+      }
+      M->compile();
+
+      SectionsMap[Section] = Sections.size();
+      Sections.emplace_back(std::move(M));
     }
 
-    // Check that the regexp is valid.
-    Regex CheckRE(Regexp);
+    auto &Entry = Sections[SectionsMap[Section]].Entries[Prefix][Category];
     std::string REError;
-    if (!CheckRE.isValid(REError)) {
+    if (!Entry.insert(std::move(Regexp), REError)) {
       Error = (Twine("malformed regex in line ") + Twine(LineNo) + ": '" +
                SplitLine.second + "': " + REError).str();
       return false;
     }
-
-    // Add this regexp into the proper group by its prefix.
-    if (!Regexps[Prefix][Category].empty())
-      Regexps[Prefix][Category] += "|";
-    Regexps[Prefix][Category] += "^" + Regexp + "$";
   }
   return true;
 }
 
 void SpecialCaseList::compile() {
   assert(!IsCompiled && "compile() should only be called once");
-  // Iterate through each of the prefixes, and create Regexs for them.
-  for (StringMap<StringMap<std::string>>::const_iterator I = Regexps.begin(),
-                                                         E = Regexps.end();
-       I != E; ++I) {
-    for (StringMap<std::string>::const_iterator II = I->second.begin(),
-                                                IE = I->second.end();
-         II != IE; ++II) {
-      Entries[I->getKey()][II->getKey()].RegEx.reset(new Regex(II->getValue()));
-    }
-  }
-  Regexps.clear();
+  // Iterate through every section compiling regular expressions for every query
+  // and creating Section entries.
+  for (auto &Section : Sections)
+    for (auto &Prefix : Section.Entries)
+      for (auto &Category : Prefix.getValue())
+        Category.getValue().compile();
+
   IsCompiled = true;
 }
 
 SpecialCaseList::~SpecialCaseList() {}
 
-bool SpecialCaseList::inSection(StringRef Section, StringRef Query,
-                                StringRef Category) const {
+bool SpecialCaseList::inSection(StringRef Section, StringRef Prefix,
+                                StringRef Query, StringRef Category) const {
   assert(IsCompiled && "SpecialCaseList::compile() was not called!");
-  StringMap<StringMap<Entry> >::const_iterator I = Entries.find(Section);
+
+  for (auto &SectionIter : Sections)
+    if (SectionIter.SectionMatcher->match(Section) &&
+        inSection(SectionIter.Entries, Prefix, Query, Category))
+      return true;
+
+  return false;
+}
+
+bool SpecialCaseList::inSection(const SectionEntries &Entries, StringRef Prefix,
+                                StringRef Query, StringRef Category) const {
+  SectionEntries::const_iterator I = Entries.find(Prefix);
   if (I == Entries.end()) return false;
-  StringMap<Entry>::const_iterator II = I->second.find(Category);
+  StringMap<Matcher>::const_iterator II = I->second.find(Category);
   if (II == I->second.end()) return false;
 
   return II->getValue().match(Query);