Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

64-bit shadow mapping init fails on Fedora 22 #1782

Closed
derekbruening opened this issue Sep 30, 2015 · 10 comments
Closed

64-bit shadow mapping init fails on Fedora 22 #1782

derekbruening opened this issue Sep 30, 2015 · 10 comments

Comments

@derekbruening
Copy link
Contributor

Many tests fail on x64 on Fedora 22:

drmemory-dbg-64: 21 tests passed, **** 8 tests failed: ****

Failures are due to shadow init failing:

        free.exitcode => ~~Dr.M~~ ASSERT FAILURE (thread 17833): /work/drmemory/git/src/drmemory/shadow.c:277: false (fail to create shadow memory mapping)

                CMake Error at runtest.cmake:311 (message):;  ~~Dr.M~~ ASSERT FAILURE (thread 17833):
                  /work/drmemory/git/src/drmemory/shadow.c:277: false (fail to create shadow
                  memory mapping)
        fuzz_buffer => ~~Dr.M~~ ASSERT FAILURE (thread 17837): /work/drmemory/git/src/drmemory/shadow.c:277: false (fail to create shadow memory mapping)

                CMake Error at runtest.cmake:311 (message):;  ~~Dr.M~~ ASSERT FAILURE (thread 17837):
                  /work/drmemory/git/src/drmemory/shadow.c:277: false (fail to create shadow
                  memory mapping)

Running

# bin64/drmemory -- tests/free.pattern

I can reproduce about 1/2 of the time.

Here is an example:

This fails:

                segment_overlap(base, end,
                                app_segments[i].reserve_base[map_idx],
                                app_segments[i].reserve_end[map_idx])) {

For:

0x00000340'00000000-0x00000380'00000000
0x00000370'00000000-0x0000037f'fff00000

scale = UMBRA_MAP_SCALE_DOWN_4X,

> cat /proc/29352/maps
00400000-00401000 r-xp 00000000 fd:09 15222034                           /work/drmemory/git/build_x64_dbg/tests/free.pattern
00401000-00600000 ---p 00000000 00:00 0 
00600000-00602000 rw-p 00000000 fd:09 15222034                           /work/drmemory/git/build_x64_dbg/tests/free.pattern
00602000-00603000 ---p 00000000 00:00 0 
00603000-00604000 rw-p 00000000 00:00 0 
51c94000-51c95000 ---p 00000000 00:00 0 
51c95000-51c9b000 rw-p 00000000 00:00 0 
51c9b000-51c9d000 ---p 00000000 00:00 0 
51c9d000-51c9e000 rw-p 00000000 00:00 0 
51c9e000-51ca5000 ---p 00000000 00:00 0 
51ca5000-51cb3000 rw-p 00000000 00:00 0 
51cb3000-51cb5000 ---p 00000000 00:00 0 
51cb5000-51cc3000 rw-p 00000000 00:00 0 
51cc3000-51cc5000 ---p 00000000 00:00 0 
51cc5000-51cc8000 rwxp 00000000 00:00 0 
51cc8000-51ccd000 ---p 00000000 00:00 0 
51ccd000-51cce000 rwxp 00000000 00:00 0 
51cce000-51cdd000 ---p 00000000 00:00 0 
51cdd000-51cde000 rwxp 00000000 00:00 0 
51cde000-51ce5000 ---p 00000000 00:00 0 
51ce5000-51ce6000 rwxp 00000000 00:00 0 
51ce6000-51ced000 ---p 00000000 00:00 0 
51ced000-51cfb000 rw-p 00000000 00:00 0 
51cfb000-51cfd000 ---p 00000000 00:00 0 
51cfd000-51cfe000 rwxp 00000000 00:00 0 
51cfe000-51d01000 ---p 00000000 00:00 0 
51d01000-51d03000 rwxp 00000000 00:00 0 
51d03000-51d05000 ---p 00000000 00:00 0 
51d05000-51d13000 rw-p 00000000 00:00 0 
51d13000-51d15000 ---p 00000000 00:00 0 
51d15000-51d1a000 rw-p 00000000 00:00 0 
51d1a000-51d1d000 ---p 00000000 00:00 0 
51d1d000-51d1e000 rw-p 00000000 00:00 0 
51d1e000-51d25000 ---p 00000000 00:00 0 
51d25000-51d33000 rw-p 00000000 00:00 0 
51d33000-51d35000 ---p 00000000 00:00 0 
51d35000-51d53000 rw-p 00000000 00:00 0 
51d53000-51d55000 ---p 00000000 00:00 0 
51d55000-51dd6000 rw-p 00000000 00:00 0 
51dd6000-51dd9000 ---p 00000000 00:00 0 
51dd9000-51e5a000 rw-p 00000000 00:00 0 
51e5a000-51e5d000 ---p 00000000 00:00 0 
51e5d000-51ede000 rw-p 00000000 00:00 0 
51ede000-61c94000 ---p 00000000 00:00 0 
73800000-73a5b000 r-xp 00000000 fd:09 15242113                           /work/drmemory/git/build_x64_dbg/bin64/debug/libdrmemorylib.so.1.8.16708
73a5b000-73c5b000 ---p 00000000 00:00 0 
73c5b000-73c8b000 rw-p 0025b000 fd:09 15242113                           /work/drmemory/git/build_x64_dbg/bin64/debug/libdrmemorylib.so.1.8.16708
73c8b000-73c94000 rw-p 00000000 00:00 0 
73c94000-73c95000 ---p 00000000 00:00 0 
55e9d56c5000-55e9d5837000 r-xp 00000000 fd:09 2147290                    /work/dr/git/exports/lib64/release/libdynamorio.so.5.0
55e9d5837000-55e9d5a37000 ---p 00000000 00:00 0 
55e9d5a37000-55e9d5a6e000 rw-p 00172000 fd:09 2147290                    /work/dr/git/exports/lib64/release/libdynamorio.so.5.0
55e9d5a6e000-55e9d5a91000 rw-p 00000000 00:00 0 
7fc490bc6000-7fc490bdc000 r-xp 00000000 09:00 1310735                    /usr/lib64/libgcc_s-5.1.1-20150618.so.1
7fc490bdc000-7fc490ddb000 ---p 00000000 00:00 0 
7fc490ddb000-7fc490ddd000 rw-p 00015000 09:00 1310735                    /usr/lib64/libgcc_s-5.1.1-20150618.so.1
7fc490ddd000-7fc490dde000 ---p 00000000 00:00 0 
7fc490dde000-7fc490dff000 r-xp 00000000 09:00 1313247                    /usr/lib64/ld-2.21.so
7fc490dff000-7fc490ffe000 ---p 00000000 00:00 0 
7fc490ffe000-7fc491000000 rw-p 00020000 09:00 1313247                    /usr/lib64/ld-2.21.so
7fc491000000-7fc491001000 rw-p 00000000 00:00 0 
7fc491001000-7fc491002000 ---p 00000000 00:00 0 
7fc491002000-7fc4911b9000 r-xp 00000000 09:00 1313254                    /usr/lib64/libc-2.21.so
7fc4911b9000-7fc4913b8000 ---p 00000000 00:00 0 
7fc4913b8000-7fc4913be000 rw-p 001b6000 09:00 1313254                    /usr/lib64/libc-2.21.so
7fc4913be000-7fc4913c2000 rw-p 00000000 00:00 0 
7fc4913c2000-7fc4913c3000 ---p 00000000 00:00 0 
7fc4913c3000-7fc4914ca000 r-xp 00000000 09:00 1313262                    /usr/lib64/libm-2.21.so
7fc4914ca000-7fc4916c9000 ---p 00000000 00:00 0 
7fc4916c9000-7fc4916cb000 rw-p 00106000 09:00 1313262                    /usr/lib64/libm-2.21.so
7fc4916cb000-7fc4916cc000 ---p 00000000 00:00 0 
7fc4916cc000-7fc49183e000 r-xp 00000000 09:00 1313557                    /usr/lib64/libstdc++.so.6.0.21
7fc49183e000-7fc491a3e000 ---p 00000000 00:00 0 
7fc491a3e000-7fc491a4a000 rw-p 00172000 09:00 1313557                    /usr/lib64/libstdc++.so.6.0.21
7fc491a4a000-7fc491a4e000 rw-p 00000000 00:00 0 
7fc491a4e000-7fc491a4f000 ---p 00000000 00:00 0 
7fc491a4f000-7fc491a70000 r-xp 00000000 09:00 1313247                    /usr/lib64/ld-2.21.so
7fc491a70000-7fc491c6f000 ---p 00000000 00:00 0 
7fc491c6f000-7fc491c71000 rw-p 00020000 09:00 1313247                    /usr/lib64/ld-2.21.so
7fc491c71000-7fc491c72000 rw-p 00000000 00:00 0 
7fc491c72000-7fc491c73000 ---p 00000000 00:00 0 
7ffefacfc000-7ffefad1d000 rw-p 00000000 00:00 0                          [stack]
7ffefadce000-7ffefadd0000 r--p 00000000 00:00 0                          [vvar]
7ffefadd0000-7ffefadd2000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
@zhaoqin
Copy link
Contributor

zhaoqin commented Oct 6, 2015

On Linux for 4B-2-1B mapping: SHDW(app) = ((app & 0x00000FFF'FFFFFFFF) + 0x00000800'00000000) >> 2
From the memory map, we have several memory segments:

app1: [0x00000000'00000000, 0x00000100'00000000): executable
app2: [0x00005500'00000000, 0x00005600'00000000): dynamorio
app3: [0x00007F00'00000000, 0x00007FFF'00000000): libs, stack, ...
app4: [0xFFFFFFFF'FF600000, 0xFFFFFFFF'FF601000]: vsyscall

shd1: [0x00000000'00000000, 0x00000200'00000000)
shd2: [0x0000340'00000000, 0x00000380'00000000)
shd3: [0x00005C0'00000000, 0x000005FF'00000000)
shd4: [0x000005FF'F0000000, 0x000005FF'FF601000)

shd3's shadow:
[0x00005C0'00000000, 0x000005FF'00000000) => [0x0000370'00000000, 0x0000037F'FFF00000)
which is conflict with shd2.

@zhaoqin
Copy link
Contributor

zhaoqin commented Oct 6, 2015

xref issue #825, this is a kind of known problem. The PIE address may cause mapping conflict.
We can reproduce it by disable the ASLR: echo 0 | sudo tee /proc/sys/kernel/randomize_va_space

@zhaoqin
Copy link
Contributor

zhaoqin commented Oct 7, 2015

I am proposing a new mapping on Linux (different displacement from original):

1B->1B: SHDW(app) = ((app & 0x00000FFF'FFFFFFFF) + 0x00001200'00000000)
app1: [000, 100)   => [1200, 1300) => [1400, 1500)
app2: [500, 600)   => [1700, 1800) => [1900, 1A00)
app3: [7F00, 8000) => [2100, 2200) => [1300, 1400)

2B->1B: SHDW(app) = ((app & 0x00000FFF'FFFFFFFF) + 0x000002400'00000000) / 2
app1: [000, 100)   => [1200, 1280) => [1300, 1340)
app2: [500, 600)   => [1480, 1500) => [1440, 1480)
app3: [7F00, 8000) => [1980, 1a00) => [16C0, 1700)

4B->1B: SHDW(app) = ((app & 0x00000FFF'FFFFFFFF) + 0x00004C00'00000000) / 4
app1: [000, 100)   => [1300, 1340) => [13C0, 13D0)
app2: [500, 600)   => [1440, 1480) => [1410, 1420)
app3: [7F00, 8000) => [16C0, 1700) => [14B0, 14C0)

8B->1B:  SHDW(app) = ((app & 0x00000FFF'FFFFFFFF) + 0x00009000'00000000) / 8
app1: [000, 100)   => [1200, 1220) => [1240, 1244)
app2: [500, 600)   => [12A0, 12C0) => [1254, 1258)
app3: [7F00, 8000) => [13E0, 1400) => [127C, 1280)

1B->2B: SHDW(app) = ((app & 0x00000FFF'FFFFFFFF) + 0x00000480'00000000) << 1
app1: [000, 100)   => [900, B00)   => [1B00, 1F00)
app2: [500, 600)   => [1300, 1500) => [F00,  1300)
app3: [7F00, 8000) => [2700, 2900) => [1700, 1B00)

@derekbruening
Copy link
Contributor Author

The proposal above makes assumptions about app4 (vdso+vvar) not colliding with the stack in app3, as both share the same segment.

I would suggest that we add first, get app4 (vdso) to wrap around, and then mask to get app3 (libs) to not be in the gap.

1B->1B: SHDW(app) = ((app + 0x00000250'00000000) & 0x00000FFF'FFFFFFFF)
app1: [000, 100)   => [250, 350) => [4a0, 5a0)
app2: [5500, 5600) => [750, 850) => [9a0, aa0)
app3: [7F00, 8000) => [150, 250) => [3a0, 4a0)
app4: [F*)         => [24f)      => [49f]

@zhaoqin
Copy link
Contributor

zhaoqin commented Oct 12, 2015

There are two potential problems of the above scheme:

  1. app3 and app4 shadow memory still has overlaps
  2. "add then mask" won't support multiple mapping, i.e., have two separate shadow mappings, because the mask will make them into the same region. In contrast, "mask then add" can make different mapping into different region with different add value.

@zhaoqin
Copy link
Contributor

zhaoqin commented Oct 22, 2015

Current mapping schema will cause app3 and app4 maps to the same shadow segment.

    /* We split app3 [0x7F0000000000, 0x800000000000) into two parts:
     * [0x7F0000000000, 0x7FFFFF400000) and [0x7FFFFF800000, 0x800000000000).
     * And we skip [0x7FFFFF400000-0x7FFFFF800000) for
     * app4 [0xFFFFFFFFFF400000,  0xFFFFFFFFFF800000) because current
     * mapping schema maps app3 and app4 to the same segment.
    */

We could use more expensive instrumentation to check the source app address and translates them to different shadow memory segments. Or better with hybrid, we first use simple instrumentation, and on seeing application allocates memory from [0x7FFFFF400000-0x7FFFFF800000), we fallback to more expensive instrumentation. In such case, we need #1798 (Umbra proactively track memory allocations).

@derekbruening
Copy link
Contributor Author

After cd2c3ec tried to fix this, it's still failing on Fedora 22 in every 3rd run or so:

shadow_table_init
new segment: app [0x00007f0000000000, 0x00007fffff400000), shadow [0x000016c000000000, 0x000016ffffd00000), reserve [0x000014b000000000, 0x000014bffff40000)
new segment: app [0xffffffffff400000, 0xffffffffff800000), shadow [0x000016ffffd00000, 0x000016ffffe00000), reserve [0x000014bffff40000, 0x000014bffff80000)
new segment: app [0x0000000000000000, 0x0000010000000000), shadow [0x0000130000000000, 0x0000134000000000), reserve [0x000013c000000000, 0x000013d000000000)
ASSERT FAILURE (thread 26331): /work/drmemory/git/src/drmemory/shadow.c:277: false (fail to create shadow memory mapping)
> cat /proc/26331/maps
00400000-00401000 r-xp 00000000 fd:09 15228375                           /work/drmemory/git/build_x64_dbg/tests/hello
00401000-00600000 ---p 00000000 00:00 0 
00600000-00602000 rw-p 00000000 fd:09 15228375                           /work/drmemory/git/build_x64_dbg/tests/hello
00602000-00603000 ---p 00000000 00:00 0 
00603000-00604000 rw-p 00000000 00:00 0 
4ee4c000-4ee4d000 ---p 00000000 00:00 0 
4ee4d000-4ee53000 rw-p 00000000 00:00 0 
<many 4ee* entries>
4ef0b000-4ef0d000 ---p 00000000 00:00 0 
4ef0d000-4ef8e000 rw-p 00000000 00:00 0 
4ef8e000-4ef91000 ---p 00000000 00:00 0 
4ef91000-4f012000 rw-p 00000000 00:00 0 
4f012000-4f015000 ---p 00000000 00:00 0 
4f015000-4f096000 rw-p 00000000 00:00 0 
4f096000-5ee4c000 ---p 00000000 00:00 0 
73800000-73a5e000 r-xp 00000000 fd:09 15242516                           /work/drmemory/git/build_x64_dbg/bin64/debug/libdrmemorylib.so.1.9.16730
73a5e000-73c5d000 ---p 00000000 00:00 0 
73c5d000-73c8d000 rw-p 0025d000 fd:09 15242516                           /work/drmemory/git/build_x64_dbg/bin64/debug/libdrmemorylib.so.1.9.16730
73c8d000-73c96000 rw-p 00000000 00:00 0 
73c96000-73c97000 ---p 00000000 00:00 0 
561196e3c000-561196fae000 r-xp 00000000 fd:09 2168023                    /work/dr/git/exports/lib64/release/libdynamorio.so.6.0
561196fae000-5611971ae000 ---p 00000000 00:00 0 
5611971ae000-5611971e5000 rw-p 00172000 fd:09 2168023                    /work/dr/git/exports/lib64/release/libdynamorio.so.6.0
5611971e5000-561197208000 rw-p 00000000 00:00 0 
7f55c8c6e000-7f55c8c84000 r-xp 00000000 09:00 1310735                    /usr/lib64/libgcc_s-5.1.1-20150618.so.1
7f55c8c84000-7f55c8e83000 ---p 00000000 00:00 0 
7f55c8e83000-7f55c8e85000 rw-p 00015000 09:00 1310735                    /usr/lib64/libgcc_s-5.1.1-20150618.so.1
7f55c8e85000-7f55c8e86000 ---p 00000000 00:00 0 
7f55c8e86000-7f55c8ea7000 r-xp 00000000 09:00 1314127                    /usr/lib64/ld-2.21.so
7f55c8ea7000-7f55c90a6000 ---p 00000000 00:00 0 
7f55c90a6000-7f55c90a8000 rw-p 00020000 09:00 1314127                    /usr/lib64/ld-2.21.so
7f55c90a8000-7f55c90a9000 rw-p 00000000 00:00 0 
7f55c90a9000-7f55c90aa000 ---p 00000000 00:00 0 
7f55c90aa000-7f55c9261000 r-xp 00000000 09:00 1313253                    /usr/lib64/libc-2.21.so
7f55c9261000-7f55c9460000 ---p 00000000 00:00 0 
7f55c9460000-7f55c9466000 rw-p 001b6000 09:00 1313253                    /usr/lib64/libc-2.21.so
7f55c9466000-7f55c946a000 rw-p 00000000 00:00 0 
7f55c946a000-7f55c946b000 ---p 00000000 00:00 0 
7f55c946b000-7f55c9572000 r-xp 00000000 09:00 1313261                    /usr/lib64/libm-2.21.so
7f55c9572000-7f55c9771000 ---p 00000000 00:00 0 
7f55c9771000-7f55c9773000 rw-p 00106000 09:00 1313261                    /usr/lib64/libm-2.21.so
7f55c9773000-7f55c9774000 ---p 00000000 00:00 0 
7f55c9774000-7f55c98e6000 r-xp 00000000 09:00 1313557                    /usr/lib64/libstdc++.so.6.0.21
7f55c98e6000-7f55c9ae6000 ---p 00000000 00:00 0 
7f55c9ae6000-7f55c9af2000 rw-p 00172000 09:00 1313557                    /usr/lib64/libstdc++.so.6.0.21
7f55c9af2000-7f55c9af6000 rw-p 00000000 00:00 0 
7f55c9af6000-7f55c9af7000 ---p 00000000 00:00 0 
7f55c9af7000-7f55c9b18000 r-xp 00000000 09:00 1314127                    /usr/lib64/ld-2.21.so
7f55c9b18000-7f55c9d17000 ---p 00000000 00:00 0 
7f55c9d17000-7f55c9d19000 rw-p 00020000 09:00 1314127                    /usr/lib64/ld-2.21.so
7f55c9d19000-7f55c9d1a000 rw-p 00000000 00:00 0 
7f55c9d1a000-7f55c9d1b000 ---p 00000000 00:00 0 
7fffa0edc000-7fffa0efd000 rw-p 00000000 00:00 0                          [stack]
7fffa0f0f000-7fffa0f11000 r--p 00000000 00:00 0                          [vvar]
7fffa0f11000-7fffa0f13000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

@zhaoqin
Copy link
Contributor

zhaoqin commented Oct 23, 2015

According to
http://lxr.free-electrons.com/source/arch/x86/include/asm/processor.h

#define TASK_SIZE_MAX   ((1UL << 47) - PAGE_SIZE)
#define TASK_SIZE       (test_thread_flag(TIF_ADDR32) ? IA32_PAGE_OFFSET : TASK_SIZE_MAX)
#define TASK_UNMAPPED_BASE      (PAGE_ALIGN(TASK_SIZE / 3))

http://lxr.free-electrons.com/source/arch/x86/um/asm/elf.h

#define ELF_ET_DYN_BASE (TASK_SIZE / 3 * 2)

http://lxr.free-electrons.com/source/fs/compat_binfmt_elf.c

#ifdef  COMPAT_ELF_ET_DYN_BASE
#undef  ELF_ET_DYN_BASE
#define ELF_ET_DYN_BASE         COMPAT_ELF_ET_DYN_BASE

http://lxr.free-electrons.com/source/arch/x86/include/asm/elf.h

#define COMPAT_ELF_ET_DYN_BASE  (TASK_UNMAPPED_BASE + 0x1000000)

http://lxr.free-electrons.com/source/fs/binfmt_elf.c

load_bias = ELF_ET_DYN_BASE - vaddr;
if (current->flags & PF_RANDOMIZE)
    load_bias += arch_mmap_rnd();
load_bias = ELF_PAGESTART(load_bias);

http://lxr.free-electrons.com/source/arch/x86/mm/mmap.c

unsigned long arch_mmap_rnd(void)
{
    ...
        /* 28 bits of randomness in 64bit mmaps, 40 address space bits */
        rnd = (unsigned long)get_random_int() % (1<<28);
    return rnd << PAGE_SHIFT; /* 12 */
}

So it most likely that PIE is at [0x5555', 0x5600'), sometimes in [0x5600', 0x5700) as above.
However, we also see the case of 54859ccd6000-54859ccd7000 at https://kernel.googlesource.com/pub/scm/linux/kernel/git/rafael/linux-pm/+/d1fd836dcf00d2028c700c7e44d2c23404062c90%5E!/.
It should not happen unless vaddr is super large. For our case, it is libdynamorio's vaddr, should be small, so we only support [0x5500', 0x5600) and [0x5600, 0x5700) for now.

We may want to change the whole mapping schema if things are getting worse.

@derekbruening
Copy link
Contributor Author

Travis just hit an umbra setup failure.
There are not enough details in the log, but given that it's non-det it is likely related to PIE/shlib ASLR so I'm putting it under this issue:

https://travis-ci.com/github/DynamoRIO/drmemory/jobs/300701337

312810:   ~~Dr.M~~ ASSERT FAILURE (thread 22579):
312910:   /home/travis/build/DynamoRIO/drmemory/drmemory/shadow.c:297: false (fail to
313010:   create shadow memory mapping)
313510: 
3136 9/99 Test #10: multierror ........................***Failed    0.19 sec

@derekbruening
Copy link
Contributor Author

Merging into #1712.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants