Replace shadow space zero-out by madvise at mmap

[stephan.yichao.zhao]

Summary

After D88686, munmap uses MADV_DONTNEED to ensure zero-out before the
next access. Because the entire shadow space is created by MAP_PRIVATE
and MAP_ANONYMOUS, the first access is also on zero-filled values.

So it is fine to not zero-out data, but use madvise(MADV_DONTNEED) at mmap. This reduces runtime
overhead.

[morehouse]

We can't remove the mmap interceptors completely, since munmap doesn't always precede mmap.

For example, it is sometimes useful to mmap over an existing mapping to zero it out quickly and/or adjust the flags.

But we can replace dfsan_set_label with madvise(DONT_NEED) as an optimization.

[stephan.yichao.zhao]

addressed comments

[morehouse]

compiler-rt/test/dfsan/mmap_release_shadow.c

1 ↗

(On Diff #295942)

Can we combine this with the munmap test since they are essentially the same? Probably a single ifdef or if (strcmp(argv[1], ...) == 0) would be sufficient to separate the differences.

34 ↗

(On Diff #295942)

Can we do a second mmap to make sure memory usage goes back down to before?

41 ↗

(On Diff #295942)

Why would the second memset increase memory usage further? Essentially these asserts are expecting a 4x memory increase factor, when I would expect at most 3x...

[eugenis]

I would move this under dfsan_set_label for consistency with asan & msan, and also to optimize large memset calls outside of the mmap interceptor (I assume they result in large dfsan_set_label calls?).

compiler-rt/lib/dfsan/dfsan_interceptors.cpp

27

"Release" - typo

[stephan.yichao.zhao]

addressed comments

compiler-rt/test/dfsan/mmap_release_shadow.c

1 ↗

(On Diff #295942)

Yes. These two cases can be merged. I found it is fine not to distinguish them, because the tests need to interleave mmap and munmap for either test.

34 ↗

(On Diff #295942)

After merging them into one file, we have munmap and another mmap in the unified test case.

https://github.com/llvm/llvm-project/commit/88c9162c9d47ef43a505bc5301dc626f3cd4f437 fixed the original test case about measuring RSS after munmap.
On LLVM buildbot, after munmap, RSS does not decrease, which is unlike my local testing.
So we only measure after another mmap to check RSS after the second mmap does not increase memory too much.

41 ↗

(On Diff #295942)

The first memset sets a value without labels. Its memory cost is 1x.
The second memset sets a value with labels. So it increases another 2x.
So the total overhead is 3x. This tests that if after mmap no labeled values are stored into the mmap addresses, it does not need additional shadow space cost.

[stephan.yichao.zhao]

update

[stephan.yichao.zhao]

update

[stephan.yichao.zhao]

update

[stephan.yichao.zhao]

In D88755#2312037, @eugenis wrote:

I would move this under dfsan_set_label for consistency with asan & msan, and also to optimize large memset calls outside of the mmap interceptor (I assume they result in large dfsan_set_label calls?).

Did you mean calling ReleaseShadowMemoryPagesToOS here (https://github.com/llvm/llvm-project/blob/master/compiler-rt/lib/dfsan/dfsan.cpp#L296)?

void __dfsan_set_label(dfsan_label label, void *addr, uptr size) {
  if (label == 0) {
       ReleaseShadowMemoryPagesToOS(addr, size);
       return;
  }

  for (dfsan_label *labelp = shadow_for(addr); size != 0; --size, ++labelp) {
    // Don't write the label if it is already the value we need it to be.
    // In a program where most addresses are not labeled, it is common that
    // a page of shadow memory is entirely zeroed.  The Linux copy-on-write
    // implementation will share all of the zeroed pages, making a copy of a
    // page when any value is written.  The un-sharing will happen even if
    // the value written does not change the value in memory.  Avoiding the
    // write when both |label| and |*labelp| are zero dramatically reduces
    // the amount of real memory used by large programs.
    if (label == *labelp)
      continue;

    *labelp = label;
  }
}

This may help memset and strncpy too if their labels are 0.

But if users call dfsan_set_label on small bytes. Does the madvise system call introduce additional overhead?

The alternative is calling ReleaseShadowMemoryPagesToOS explicitly at memset and strncpy if madvise has overhead.

[eugenis]

Sure, madvise has overhead. Check SetShadow in MSan and FastPoisonShadow in ASan.

I'm confused - I don't see allocator replacement in dfsan. How does it handle the situation where deallocated memory that contains some labelled data is reused for a new allocation - the labels must be cleared somehow, right?

[morehouse]

In D88755#2313133, @eugenis wrote:

Sure, madvise has overhead. Check SetShadow in MSan and FastPoisonShadow in ASan.

I'm confused - I don't see allocator replacement in dfsan. How does it handle the situation where deallocated memory that contains some labelled data is reused for a new allocation - the labels must be cleared somehow, right?

Labels aren't cleared until new data is written there. In some sense this is preferable since it can detect taint propagation through "uninitialized" heap memory.

[stephan.yichao.zhao]

In D88755#2313133, @eugenis wrote:

Sure, madvise has overhead. Check SetShadow in MSan and FastPoisonShadow in ASan.

It seems that FastPoisonShadow (that calls madvise) is called by asan when ever a memory needs to release. Maybe this means the overhead is fine.
I have planned to do some evaluation on dfsan soon, during the evaluation, I will be testing this. If it works, will be making a separate patch.

I'm confused - I don't see allocator replacement in dfsan. How does it handle the situation where deallocated memory that contains some labelled data is reused for a new allocation - the labels must be cleared somehow, right?

I am new to dfsan, not sure about this.

[morehouse]

I agree with @eugenis that the madvise call is more beneficial as a special case for large sizes in dfsan_set_label.

dfsan_set_label is only called from wrappers (which already have lots of branches and shadow propagation), so the overhead from the branch is likely insignificant.

That said, I'm fine with making that change in follow-up patch if you prefer.

compiler-rt/lib/dfsan/dfsan_interceptors.cpp

23

Nit: Since you added an unnamed namespace, let's move this variable into there and remove the static.

compiler-rt/test/dfsan/release_shadow_space.c

26

Why is this additional memset needed?

42

Since we now do madvise instead of writing zeros, I expect memory usage to decrease the same as with munmap.

E.g., memory usage decrease here:

void *p = mmap(NULL, size, ...);
memset(p, 0xff, size);
size_t before = get_rss_kb();
munmap(p, size);
size_t after = get_rss_kb();

should be the same as the decrease with:

void *p = mmap(NULL, size, ...);
memset(p, 0xff, size);
size_t before = get_rss_kb();
mmap(p, size, PROT_READ | PROT_WRITE, MAP_FIXED ...)
size_t after = get_rss_kb();

Please test this.

[stephan.yichao.zhao]

addressed comments

[stephan.yichao.zhao]

In D88755#2313228, @morehouse wrote:

I agree with @eugenis that the madvise call is more beneficial as a special case for large sizes in dfsan_set_label.

dfsan_set_label is only called from wrappers (which already have lots of branches and shadow propagation), so the overhead from the branch is likely insignificant.

That said, I'm fine with making that change in follow-up patch if you prefer.

Will be making another patch after this.

compiler-rt/test/dfsan/release_shadow_space.c

26

without this memset RSS shows the same amount as before mmap. It seems that even at the anonymous mmap, OS still does lazy allocation until we use it.

[stephan.yichao.zhao]

update

[morehouse]

compiler-rt/test/dfsan/release_shadow_space.c

43

after_munmap appears unused.

50

repeating the dfsan_set_label multiple times is unnecessary.

84

I didn't realize this before, but this is 50MB slack. i.e. 50% of map_size.

Is there a chance that your method of measuring RSS isn't very precise or is delayed? IIRC, using /proc/self/smaps is much more precise.

[stephan.yichao.zhao]

changed from statm to smap

[stephan.yichao.zhao]

compiler-rt/test/dfsan/release_shadow_space.c

43

after changing to smaps, this is used by assert.

50

changed to smaps, and removed the additional dfsan_set_label. hopefully LLVM buildbot behaves the same to the local testing environemnt.

84

changed to smaps

[morehouse]

compiler-rt/test/dfsan/release_shadow_space.c

56

We should be able to remove this mmap by moving the fixed mmap below in between the first mmap and the munmap.

i.e. mmap -> memset -> mmap(MAP_FIXED) -> memset -> munmap

57

This dfsan_set_label is unnecessary. We already assigned the label to val.

60

s/mumap/munmap

81

delta is unused.

84

Why two different delta methods? Can we use delta for both?

[stephan.yichao.zhao]

update

compiler-rt/test/dfsan/release_shadow_space.c

57

Thank you. Removed.

81

replaced 5000 by delta.

84

changed them to use delta.

[morehouse]

compiler-rt/test/dfsan/release_shadow_space.c

69

Should we be using %zu instead of %td?

[eugenis]

FYI I believe linux updates the rss count only on every 40th-or-so change to the page tables.
We have a test somewhere that runs a single page mmap-munmap in a loop for a while before taking a measurement.

[morehouse]

In D88755#2315178, @eugenis wrote:

FYI I believe linux updates the rss count only on every 40th-or-so change to the page tables.
We have a test somewhere that runs a single page mmap-munmap in a loop for a while before taking a measurement.

I believe using smaps should avoid this issue. At least I've written a GWP-ASan test in the past that had page precision immediately using smaps.

@stephan.yichao.zhao Please also update the commit description.

[stephan.yichao.zhao]

update

compiler-rt/lib/dfsan/dfsan_interceptors.cpp

 #include <unistd.h>
 
 #include "dfsan/dfsan.h"
 #include "interception/interception.h"
 #include "sanitizer_common/sanitizer_common.h"
 
 using namespace __sanitizer;
 
 static bool interceptors_initialized;
 
+namespace {
+
+void ReleaseShadowMemoryPagesToOS(void *addr, SIZE_T length) {
+  uptr beg_shadow_addr = (uptr)__dfsan::shadow_for(addr);
+  void *end_addr =
+      (void *)((uptr)addr + RoundUpTo(length, GetPageSizeCached()));
+  uptr end_shadow_addr = (uptr)__dfsan::shadow_for(end_addr);
+  ReleaseMemoryPagesToOS(beg_shadow_addr, end_shadow_addr);
+}
+
+}  // namespace
+
 INTERCEPTOR(void *, mmap, void *addr, SIZE_T length, int prot, int flags,
             int fd, OFF_T offset) {
   void *res;
 
   // interceptors_initialized is set to true during preinit_array, when we're
   // single-threaded.  So we don't need to worry about accessing it atomically.
   if (!interceptors_initialized)
     res = (void *)syscall(__NR_mmap, addr, length, prot, flags, fd, offset);
   else
     res = REAL(mmap)(addr, length, prot, flags, fd, offset);
 
   if (res != (void *)-1)
-    dfsan_set_label(0, res, RoundUpTo(length, GetPageSize()));
+    ReleaseShadowMemoryPagesToOS(res, length);
   return res;
 }
 
 INTERCEPTOR(void *, mmap64, void *addr, SIZE_T length, int prot, int flags,
             int fd, OFF64_T offset) {
   void *res = REAL(mmap64)(addr, length, prot, flags, fd, offset);
   if (res != (void *)-1)
-    dfsan_set_label(0, res, RoundUpTo(length, GetPageSize()));
+    ReleaseShadowMemoryPagesToOS(res, length);
   return res;
 }
 
 INTERCEPTOR(int, munmap, void *addr, SIZE_T length) {
   int res = REAL(munmap)(addr, length);
   if (res != -1) {
-    uptr beg_shadow_addr = (uptr)__dfsan::shadow_for(addr);
-    void *end_addr =
-        (void *)((uptr)addr + RoundUpTo(length, GetPageSizeCached()));
-    uptr end_shadow_addr = (uptr)__dfsan::shadow_for(end_addr);
-    ReleaseMemoryPagesToOS(beg_shadow_addr, end_shadow_addr);
+    ReleaseShadowMemoryPagesToOS(addr, length);
   }
   return res;
 }
 
 namespace __dfsan {
 void InitializeInterceptors() {
   CHECK(!interceptors_initialized);
 
   INTERCEPT_FUNCTION(mmap);
   INTERCEPT_FUNCTION(mmap64);
   INTERCEPT_FUNCTION(munmap);
 
   interceptors_initialized = true;
 }
 }  // namespace __dfsan

compiler-rt/test/dfsan/munmap_release_shadow.c

-// RUN: %clang_dfsan %s -o %t && %run %t
-
-#include <assert.h>
-#include <sanitizer/dfsan_interface.h>
-#include <stdbool.h>
-#include <stdio.h>
-#include <string.h>
-#include <sys/mman.h>
-#include <unistd.h>
-
-size_t get_rss_kb() {
-  long rss = 0L;
-  FILE *f = NULL;
-  assert((f = fopen("/proc/self/statm", "r")));
-  assert(fscanf(f, "%*s%ld", &rss) == 1);
-  fclose(f);
-  return ((size_t)rss * (size_t)sysconf(_SC_PAGESIZE)) >> 10;
-}
-
-int main(int argc, char **argv) {
-  const size_t map_size = 100 << 20;
-  size_t before = get_rss_kb();
-
-  char *p = mmap(NULL, map_size, PROT_READ | PROT_WRITE,
-                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
-  const dfsan_label label = dfsan_create_label("l", 0);
-  char val = 0xff;
-  dfsan_set_label(label, &val, sizeof(val));
-  memset(p, val, map_size);
-  size_t after_mmap = get_rss_kb();
-
-  munmap(p, map_size);
-  size_t after_munmap = get_rss_kb();
-
-  p = mmap(NULL, map_size, PROT_READ | PROT_WRITE,
-                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
-  dfsan_set_label(label, &val, sizeof(val));
-  memset(p, val, map_size);
-  size_t after_mmap2 = get_rss_kb();
-
-  fprintf(stderr, "RSS at start: %td, after mmap: %td, after mumap: %td, after mmap2: %td\n",
-          before, after_mmap, after_munmap, after_mmap2);
-
-  // The memory after mmap increases 3 times of map_size because the overhead of
-  // shadow memory is 2x.
-  const size_t mmap_cost_kb = 3 * (map_size >> 10);
-  assert(after_mmap >= before + mmap_cost_kb);
-  // OS does not release memory to the same level as the start of the program.
-  // The assert checks the memory after munmap up to a delta.
-  const size_t delta = 50000;
-  assert(after_mmap2 <= after_mmap + delta);
-
-  return 0;
-}

compiler-rt/test/dfsan/release_shadow_space.c

+// RUN: %clang_dfsan %s -o %t && %run %t
+
+#include <assert.h>
+#include <sanitizer/dfsan_interface.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+size_t get_rss_kb() {
+  long rss = 0L;
+  FILE *f = NULL;
+  assert((f = fopen("/proc/self/statm", "r")));
+  assert(fscanf(f, "%*s%ld", &rss) == 1);
+  fclose(f);
+  return ((size_t)rss * (size_t)sysconf(_SC_PAGESIZE)) >> 10;
+}
+
+int main(int argc, char **argv) {
+  const size_t map_size = 100 << 20;
+  size_t before = get_rss_kb();
+
+  // mmap and touch all addresses. The overhead is 1x.
+  char *p = mmap(NULL, map_size, PROT_READ | PROT_WRITE,
+                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+  memset(p, 0xff, map_size);
+  size_t after_mmap = get_rss_kb();
+
+  // store labels to all addresses. The overhead is 2x.
+  const dfsan_label label = dfsan_create_label("l", 0);
+  char val = 0xff;
+  dfsan_set_label(label, &val, sizeof(val));
+  memset(p, val, map_size);
+  size_t after_mmap_and_set_label = get_rss_kb();
+
+  // munmap the addresses. This releases all the 3x memory to OS. However, the
+  // RSS number after this may not be reduced to the amount before the first
+  // map. We can confirm that the memory is indeed released by requesting more
+  // memory from OS and measuring RSS does not increase too much.
+  munmap(p, map_size);
+  size_t after_munmap = get_rss_kb();
+
+  // mmap the same amount of memory and store labels. This confirms that
+  // although after the last munmap RSS is not increased, memory is already
+  // returned to OS.
+  p = mmap(NULL, map_size, PROT_READ | PROT_WRITE,
+                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+  dfsan_set_label(label, &val, sizeof(val));
+  memset(p, val, map_size);
+  size_t after_mmap_and_set_label2 = get_rss_kb();
+
+  // fixed-mmap the same address. OS recyles pages and reinitializes data at the
+  // address. This should be the same to calling mumap. But, for the same
+  // reason, RSS after this may look unchanged.
+  p = mmap(p, map_size, PROT_READ | PROT_WRITE,
+                 MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, 0);
+  size_t after_fixed_mmap = get_rss_kb();
+
+  // Store labels to all addresses. This confirms that although after the last
+  // fixed-mmap RSS is not increased, memory is already returned to OS.
+  dfsan_set_label(label, &val, sizeof(val));
+  memset(p, val, map_size);
+  size_t after_mmap_and_set_label3 = get_rss_kb();
+
+  fprintf(
+      stderr,
+      "RSS at start: %td, after mmap: %td, after mmap+set label: %td, after "
+      "mumap: %td, after another mmap+set label: %td, after fixed map: %td, "
+      "after another set label: %td\n",
+      before, after_mmap, after_mmap_and_set_label, after_munmap,
+      after_mmap_and_set_label2, after_fixed_mmap, after_mmap_and_set_label3);
+
+  // The memory after mmap increases 3 times of map_size because the overhead of
+  // shadow memory is 2x.
+  const size_t mmap_cost_kb = map_size >> 10;
+  const size_t mmap_shadow_cost_kb = 2 * mmap_cost_kb;
+  assert(after_mmap >= before + mmap_cost_kb);
+  assert(after_mmap_and_set_label >= after_mmap + mmap_shadow_cost_kb);
+  // RSS may not change memory amount after munmap to the same level as the
+  // start of the program. The assert checks the memory after another mmap up to
+  // a delta.
+  const size_t delta = 50000;
+  assert(after_mmap_and_set_label2 <= after_mmap_and_set_label + delta);
+  // RSS may not change memory amount after fixed-mmap. The assert checks the
+  // memory after another memset up to a delta.
+  assert(after_mmap_and_set_label3 <= after_mmap_and_set_label2 + delta);
+
+  return 0;
+}