<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hello Hal,<br>
<br>
Thanks a lot for your feedback. Particularly, I appreciate
mentioning HPC systems as potential targets for this work as it
helps with figuring out what the generalized memory interface would
look like.<br>
<br>
Answering your questions: what we propose with this RFC is to
support platforms for which there is no way to adopt sanitizers by
adding a special mapping or tweaking the MEM_TO_SHADOW() macro. As
you already said, the problem with such platforms is that the amount
of available physical memory is not sufficient to shadow-map the
whole address space to sanitize. The solution we propose is to claim
a fixed set of ways, such as macros and functions, that provide
access to physical shadow memory so that by implementing these
macros and functions one can support sanitizers even on platforms
that: 1) do not have hardware support for virtual memory and 2) can
only allocate physical memory by relatively small pieces whose base
addressses are not known at compile-time. This includes implementing
a software shadow memory manager on top of a malloc()-like API. In
addition, the resulting support shall be compact and efficient
enough to be practical on such platforms and the introduced
abstraction layer shall have zero penalty in terms of code space and
performance for the already supported targets.<br>
<br>
The proposed approach to the abstraction layer is to provide macros
and functions that perform necessary operations with physical shadow
memory by given virtual shadow addresses or virtual shadow address
ranges. For example, for Asan there is function VShadowToPShadow()
declared as:<br>
<br>
u64 *VShadowToPShadow(uptr vs);<br>
<br>
that returns a pointer to a physical shadow cell by its virtual
address and makes sure that the piece of physical shadow memory (the
physical shadow page) the address belongs to is allocated and
accessible. For perfomance reasons there are also block shadow
memory functions that peform various operations over virtual address
ranges rather than individual addresses. There is also a function
that explicitly releases physical shadow memory. That function can
be implemented in any way suitable for a given specific platform.
The only requirement is that subsequent read accesses to the
released shadow memory yield zeros, so the simplest implementation
is zeroing out the specified region.<br>
<br>
Please see the updated patch at:<br>
<br>
<a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D30583">https://reviews.llvm.org/D30583</a><br>
<br>
for details. This patch implements a software shadow memory manager
on top of Linux mmap(). With this patch we pass Asan and Tsan tests
with a promising slowdown ratio.<br>
<br>
Re: instrumentation: yes, to support platforms that only support
manual/explicit allocation of physical memory the only way is to
instrument the code to sanitize with RTL calls.<br>
<br>
One important quality of the abstraction layer that we would like to
maintain is that it is never required to perform backward
physical-to-virtual translations as they may be extremely
inefficient in some cases. Since the santiziers themselves require
shadow-to-application memory translations to be supported, we have
to deal with both the concepts of virtual and physical shadow
addresses. Since the abstract layer operates in terms of virtual
shadow addresses, it does not affect how application memory
addresses translate to virtual shadow addresses. This means one can
choose whatever mapping will do better for his platform and then
decide whether to rely on hardware-driven allocation of physical
pages or implement a custom software memory manager.<br>
<br>
Thanks again and please let me know if I can help more.<br>
<br>
Regards,<br>
Ivan<br>
<br>
<br>
<div class="moz-cite-prefix">On 09/03/17 15:58, Hal Finkel wrote:<br>
</div>
<blockquote cite="mid:c01216a4-6653-4598-6da8-9a997729a89a@anl.gov"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<p>Hi Ivan,</p>
<p>Thanks for posting this; I'm excited by this proposal - if we
can get this kind of support in without making the
implementation non-trivially-harder to maintain, that would be a
positive development. As Sean mentioned, I did something along
these lines to adapt ASan to the IBM BG/Q - an HPC system that
uses a lightweight operating system. On the BG/Q, the
lightweight operating system does support virtual memory for
some special-purpose mappings, but it does not support mapping
unreserved pages (i.e. MAP_NORESERVE is not supported, and this
functionality is not supported any other way). As a result, the
mechanism that the sanitizers use to cover the complete address
space using shadow memory - by mapping a large region of
unreserved pages - won't work in this environment. Systems
without virtual memory at all will obviously have the same
problem: All shadow memory must be physically backed. I'll also
mention that many normal Linux HPC environments are configured
with overcommit turned off, and I believe that using the
sanitizers in such environments would also currently not work.<br>
</p>
<p>Because all shadow memory must be physically backed, it must be
allocated judicially, and the mapping process might need to be
more complicated than a simple shift/offset. On the BG/Q, there
were a few distinct regions of virtual memory that needed to be
mapped into a single shadow region in the part of the address
space where heap allocations could be made - as a result, I used
a more-complicated mapping function.<br>
</p>
<p>In this light, I'm trying to understand your proposal. I see
that you're proposing to add support for some kind of additional
translation scheme between virtual addresses and physical
addresses, but I'm not exactly sure how you propose to use them.
It might help if you were to provide some hypothetical
implementation of these translations for a simple system so that
we can understand the usage model better. I'd also like to
better understand how the instrumentation works; if the mapping
always replaced by these
__asan_mem_to_vshadow/__asan_mem_to_pshadow calls?</p>
<p>Finally, I recommend that we layer this support so that we
have:</p>
<p>[regular system] -> [system without (sufficient) unreserved
pages] -> [system without any mmu]</p>
<p>I'd like a clear explanation of how these last two differ. It
looks like you have support for manually zeroing pages for the
last category. Please explain exactly how this scheme works.</p>
<p>Thanks,</p>
<p>Hal<br>
</p>
<br>
<div class="moz-cite-prefix">On 02/23/2017 12:16 PM, Ivan A.
Kosarev via llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:153b6433-b001-b0fb-6957-1de8c598ce77@accesssoftek.com"
type="cite">RFC: Generalize means the sanitizers work with
memory <br>
<br>
Overview <br>
======== <br>
<br>
Currently, LLVM sanitizers, such as Asan and Tsan, are tied to a
specific <br>
memory model that relies on presence of hardware support for
virtual memory. <br>
This prevents sanitizers from being used on platforms that lack
such support, <br>
but otherwise are capable of running sanitized programs. Our
research <br>
indicates that adding support for such platforms is possible
with a relatively <br>
small amount of changes to the sanitizers source code and zero
performance and <br>
size penalty on currently supported systems. We also found that
these changes <br>
clarify and formalize the functional and performance
dependencies between <br>
sanitizers and system memory so they can be considered an
improvement in <br>
terms of design and readability regardless of the added
capabilities. One can <br>
think of it as a zero-cost abstraction layer. <br>
<br>
<br>
The Approach <br>
============ <br>
<br>
To support platforms that do not have hardware virtual memory
managers, <br>
we need to introduce the concept of physical memory pages that
work as the <br>
storage for data that sanitizers currently read and write by
virtual <br>
addresses. In presence of the concept of physical memory, every
time we access <br>
virtual memory we have to translate the given virtual address to
a physical <br>
one. For example, this check: <br>
<br>
*(u8 *)MEM_TO_SHADOW(allocated) == 0 <br>
<br>
becomes: <br>
<br>
*MEM_TO_PSHADOW(allocated) == 0 <br>
<br>
where the MEM_TO_PSHADOW(mem) macro is defined as: <br>
<br>
#define MEM_TO_PSHADOW(mem)
VSHADOW_TO_PSHADOW(MEM_TO_VSHADOW(mem)) <br>
#define MEM_TO_VSHADOW(mem) /* Whatever currently
MEM_TO_SHADOW() is. */ <br>
<br>
The VSHADOW_TO_PSHADOW(vs) macro returns a pointer to a byte
within a <br>
physical page that corresponds to the given virtual address and
allocates this <br>
page if it has not been allocated before. On platforms that
leverage hardware <br>
virtual memory managers this macro returns the virtual address
as a physical <br>
one: <br>
<br>
#define VSHADOW_TO_PSHADOW(vs)
(reinterpret_cast<u8*>((vs))) <br>
<br>
Physical pages are required to be aligned by their size. The
size of physical <br>
pages is a multiple of the shadow memory granularity (8 bytes
for Asan) and <br>
not less than the size of the widest scalar access we have to
support (16 <br>
bytes). This makes trivial finding page offsets, which we need
to implement <br>
RTL functions efficiently. This also simplifies handling of
aligned accesses <br>
to physical memory as they are known to not cross bounds of
physical pages. <br>
Note that RTL functions have to be fixed to not rely on specific
size, <br>
location or order of physical pages. <br>
<br>
In addition to the facilities that allow handling of individual
accesses to <br>
the virtual memory we also need a set of functions that
efficiently perform <br>
operations on specified ranges of virtual addresses: <br>
<br>
// Fills a virtual memory with a given value. May release zeroed
pages. For <br>
// DFsan we may need a version of this function that takes
16-bit values to <br>
// fill with. <br>
void vshadow_memset(uptr vs, u8 value, uptr size); <br>
<br>
// Similarly to vshadow_memset(), this function fills a range of
virtual <br>
// memory with a given value and additionally claims that range
as read-only <br>
// so the memory manager is not required to support modifying
accesses for <br>
// these addresses. <br>
void fill_rodata_vshadow(uptr vs, u8 value, uptr size); <br>
<br>
// Copies potentially overlapping memory regions. <br>
void vshadow_memmove(uptr dest, uptr src, uptr size); <br>
<br>
// Returns the virtual address of the first non-zero byte in a
given virtual <br>
// address range. Can also be used to test for zeroed regions. <br>
uptr find_non_zero_vshadow_byte(uptr vs, uptr size); <br>
<br>
// Explicitly releases pages that fit the specified range. <br>
void release_vshadow(uptr vs, uptr size); <br>
<br>
<br>
The Proof-of-Concept Patch <br>
========================== <br>
<br>
To make sure the approach is feasible we have prepared a patch
that <br>
fixes the Asan and Tsan RTL and instrumentation parts to
translate virtual <br>
shadow memory addresses to physical ones and mmap() shadow
memory as we access <br>
it. This way we simulate a software virtual memory manager that
allocates <br>
physical storage for shadow memory on-demand. <br>
<br>
We used that to mock RTL for the sanitizers tests. With this
mock in place we <br>
pass all Tsan tests and fail on 3 of 610 Asan tests: <br>
<br>
test/asan/TestCases/Linux/cuda_test.cc <br>
test/asan/TestCases/Linux/nohugepage_test.cc <br>
test/asan/TestCases/Linux/swapcontext_annotation.cc <br>
<br>
The first two tests rely on specific memory map after
initializtion of the <br>
shadow memory and the latter takes too long to complete. It
would probably be <br>
acceptable to XFAIL them when run with a software memory manager
enabled and <br>
then consider ways to adopt them as necessary on a per-test
basis. <br>
<br>
* * * <br>
<br>
With this paper we propose the changes that make it possible to
use sanitizers <br>
on plaforms that have no MMUs to be part of the mainline.
However, before <br>
moving further we would like some feedback from the community so
comments are <br>
very appreciated. <br>
<br>
If the approach is fine, we will prepare a set of patches
shortly. <br>
<br>
Thank you, <br>
<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</blockquote>
<br>
</body>
</html>