[DFSan] Handle fast16labels for all API functions.

[morehouse]

Summary

Support fast16labels in dfsan_has_label, and print an error for all
other API functions.

[kcc]

I think this is an overkill.
fast16labels mode should be even simpler:
there are always 16 primary labels, they don't have any descriptions or properties controlled by dfsan.

compiler-rt/lib/dfsan/dfsan.cpp

258

I would just err in fast16labels mode w/i checking for last_lavel > 15.
Users should not call this function at all in fast16labels mode, IMO.

321

same

349

same

378

same

[morehouse]

In D84215#2164676, @kcc wrote:

I think this is an overkill.
fast16labels mode should be even simpler:
there are always 16 primary labels, they don't have any descriptions or properties controlled by dfsan.

Seems reasonable, but note it will require effort for existing API users to switch. For example, all the existing protobuf labeling API, etc. will need to be adapted.

[kcc]

and that's fine. I want this mode to be as simple as possible.

[kcc]

Also, we don't have to err in these functions at all, it's fine to just return silently.

[morehouse]

• Print error on most API calls under fast16labels mode.

[morehouse]

• Update diffbase.

[kcc]

LGTM

compiler-rt/lib/dfsan/dfsan.cpp

 dfsan_union(dfsan_label l1, dfsan_label l2) {
   if (l1 == l2)
     return l1;
   return __dfsan_union(l1, l2);
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 dfsan_label dfsan_create_label(const char *desc, void *userdata) {
-  dfsan_label label =
-    atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1;
+  dfsan_label last_label =
+      atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed);
+  if (flags().fast16labels && last_label > 15) {
+    Report(
+        "FATAL: DataFlowSanitizer: more than 16 labels created in "
+        "fast16labels mode\n");
+    Die();
+  }
+  dfsan_label label = flags().fast16labels ? 1U << last_label : last_label + 1;
   dfsan_check_label(label);
   __dfsan_label_info[label].l1 = __dfsan_label_info[label].l2 = 0;
   __dfsan_label_info[label].desc = desc;
   __dfsan_label_info[label].userdata = userdata;
   return label;
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE

 dfsan_read_label(const void *addr, uptr size) {
   if (size == 0)
     return 0;
   return __dfsan_union_load(shadow_for(addr), size);
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) {
+  if (flags().fast16labels && (label & (label - 1))) {
+    // In fast16 mode, we don't have info for any union labels.  Users should
+    // only call this function for base labels.
+    Report(
+        "FATAL: DataFlowSanitizer: called dfsan_get_label_info() on union "
+        "label %u in fast16labels mode\n",
+        label);
+    Die();
+  }
   return &__dfsan_label_info[label];
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE int
 dfsan_has_label(dfsan_label label, dfsan_label elem) {
+  if (flags().fast16labels)
+    return label & elem;
   if (label == elem)
     return true;
   const dfsan_label_info *info = dfsan_get_label_info(label);
   if (info->l1 != 0) {
     return dfsan_has_label(info->l1, elem) || dfsan_has_label(info->l2, elem);
   } else {
     return false;
   }
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
 dfsan_has_label_with_desc(dfsan_label label, const char *desc) {
+  if (flags().fast16labels && (label & (label - 1)) && label != 0) {
+    // This is a union label.  Peel off the lowest bit and recurse.
+    dfsan_label l1 = 1U << __builtin_ctz(label);
+    dfsan_label l2 = label & ~l1;
+    return dfsan_has_label_with_desc(l1, desc) ||
+           dfsan_has_label_with_desc(l2, desc);
+  }
   const dfsan_label_info *info = dfsan_get_label_info(label);
   if (info->l1 != 0) {
     return dfsan_has_label_with_desc(info->l1, desc) ||
            dfsan_has_label_with_desc(info->l2, desc);
   } else {
     return internal_strcmp(desc, info->desc) == 0;
   }
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE uptr
 dfsan_get_label_count(void) {
   dfsan_label max_label_allocated =
       atomic_load(&__dfsan_last_label, memory_order_relaxed);
 
   return static_cast<uptr>(max_label_allocated);
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE void
 dfsan_dump_labels(int fd) {
   dfsan_label last_label =
       atomic_load(&__dfsan_last_label, memory_order_relaxed);
 
+  if (flags().fast16labels) {
+    for (uptr i = 0; i < last_label; ++i) {
+      dfsan_label l = 1U << i;
+      char buf[16];
+      internal_snprintf(buf, sizeof(buf), "%u ", l);
+      WriteToFile(fd, buf, internal_strlen(buf));
+      if (__dfsan_label_info[l].desc) {
+        WriteToFile(fd, __dfsan_label_info[l].desc,
+                    internal_strlen(__dfsan_label_info[l].desc));
+      }
+      WriteToFile(fd, "\n", 1);
+    }
+    return;
+  }
+
   for (uptr l = 1; l <= last_label; ++l) {
     char buf[64];
     internal_snprintf(buf, sizeof(buf), "%u %u %u ", l,
                       __dfsan_label_info[l].l1, __dfsan_label_info[l].l2);
     WriteToFile(fd, buf, internal_strlen(buf));
     if (__dfsan_label_info[l].l1 == 0 && __dfsan_label_info[l].desc) {
       WriteToFile(fd, __dfsan_label_info[l].desc,
                   internal_strlen(__dfsan_label_info[l].desc));

compiler-rt/test/dfsan/fast16labels.c

-// RUN: %clang_dfsan %s -o %t && DFSAN_OPTIONS=fast16labels=1 %run %t
+// RUN: %clang_dfsan %s -o %t
+// RUN: DFSAN_OPTIONS=fast16labels=1:dump_labels_at_exit=/dev/stdout %run %t \
+// RUN:   2>&1 | FileCheck %s --check-prefix=CHECK-LABELS
+// RUN: DFSAN_OPTIONS=fast16labels=1 not %run %t exceed_16_labels 2>&1 \
+// RUN:   | FileCheck %s --check-prefix=CHECK-EXCEED16
+// RUN: DFSAN_OPTIONS=fast16labels=1 not %run %t union_label_info 2>&1 \
+// RUN:   | FileCheck %s --check-prefix=CHECK-UNION-LABEL-INFO
 //
 // Tests DFSAN_OPTIONS=fast16labels=1
 //
 #include <sanitizer/dfsan_interface.h>
 
 #include <assert.h>
 #include <stdio.h>
+#include <string.h>
+
+void check_label(dfsan_label l) {
+  static dfsan_label combined = 0;
+  assert((l & combined) == 0);
+  combined = dfsan_union(l, combined);
+}
 
 int foo(int a, int b) {
   return a + b;
 }
 
-int main() {
+int main(int argc, char *argv[]) {
+  const char *command = (argc < 2) ? "" : argv[1];
+
+  // Make sure we can create 16 distinct labels.
+  for (int i = 0; i < 13; ++i)
+    check_label(dfsan_create_label("unused", NULL));
+  dfsan_label lx = dfsan_create_label("x", NULL);
+  check_label(lx);
+  dfsan_label la = dfsan_create_label("a", NULL);
+  check_label(la);
+  dfsan_label lb = dfsan_create_label("b", NULL);
+  check_label(lb);
+
+  // CHECK-EXCEED16: FATAL: DataFlowSanitizer: more than 16 labels created
+  if (strcmp(command, "exceed_16_labels") == 0)
+    dfsan_create_label("", NULL);
+
   int a = 10;
   int b = 20;
-  dfsan_set_label(8, &a, sizeof(a));
-  dfsan_set_label(512, &b, sizeof(b));
+  dfsan_set_label(la, &a, sizeof(a));
+  dfsan_set_label(lb, &b, sizeof(b));
   int c = foo(a, b);
   printf("A: 0x%x\n", dfsan_get_label(a));
   printf("B: 0x%x\n", dfsan_get_label(b));
-  dfsan_label l = dfsan_get_label(c);
-  printf("C: 0x%x\n", l);
-  assert(l == 520);  // OR of the other two labels.
+  dfsan_label lc = dfsan_get_label(c);
+  printf("C: 0x%x\n", lc);
+
+  assert(dfsan_has_label(lc, la));
+  assert(dfsan_has_label(lc, lb));
+  assert(!dfsan_has_label(lc, lx));
+  assert(dfsan_has_label_with_desc(lc, "a"));
+  assert(dfsan_has_label_with_desc(lc, "b"));
+  assert(!dfsan_has_label_with_desc(lc, "x"));
+  assert(lc == (la | lb));
+
+  const struct dfsan_label_info *info = dfsan_get_label_info(la);
+  assert(info->l1 == 0);
+  assert(info->l2 == 0);
+  assert(strcmp(info->desc, "a") == 0);
+  assert(info->userdata == NULL);
+
+  // CHECK-UNION-LABEL-INFO: FATAL: DataFlowSanitizer: called dfsan_get_label_info() on union label
+  if (strcmp(command, "union_label_info") == 0)
+    dfsan_get_label_info(lc);
+
+  // CHECK-LABELS: 1 unused
+  // CHECK-LABELS-NEXT: 2 unused
+  // CHECK-LABELS-NEXT: 4 unused
+  // CHECK-LABELS-NEXT: 8 unused
+  // CHECK-LABELS-NEXT: 16 unused
+  // CHECK-LABELS-NEXT: 32 unused
+  // CHECK-LABELS-NEXT: 64 unused
+  // CHECK-LABELS-NEXT: 128 unused
+  // CHECK-LABELS-NEXT: 256 unused
+  // CHECK-LABELS-NEXT: 512 unused
+  // CHECK-LABELS-NEXT: 1024 unused
+  // CHECK-LABELS-NEXT: 2048 unused
+  // CHECK-LABELS-NEXT: 4096 unused
+  // CHECK-LABELS-NEXT: 8192 x
+  // CHECK-LABELS-NEXT: 16384 a
+  // CHECK-LABELS-NEXT: 32768 b
 }