Re: [PATCH v4 1/3] kasan: support backing vmalloc space with real shadow memory
> On Aug 18, 2019, at 8:58 PM, Daniel Axtens wrote: > >>> Each page of shadow memory represent 8 pages of real memory. Could we use >>> page_ref to count how many pieces of a shadow page are used so that we can >>> free it when the ref count decreases to 0. > > I'm not sure how much of a difference it will make, but I'll have a look. > There are a grand total of eight possible pages that could require a given shadow page. I would suggest that, instead of reference counting, you just check all eight pages. Or, better yet, look at the actual vm_area_struct and are where prev and next point. That should tell you exactly which range can be freed.
Re: [PATCH v4 1/3] kasan: support backing vmalloc space with real shadow memory
On Fri, Aug 16, 2019 at 10:41:00AM -0700, Andy Lutomirski wrote: > On Fri, Aug 16, 2019 at 10:08 AM Mark Rutland wrote: > > > > Hi Christophe, > > > > On Fri, Aug 16, 2019 at 09:47:00AM +0200, Christophe Leroy wrote: > > > Le 15/08/2019 à 02:16, Daniel Axtens a écrit : > > > > Hook into vmalloc and vmap, and dynamically allocate real shadow > > > > memory to back the mappings. > > > > > > > > Most mappings in vmalloc space are small, requiring less than a full > > > > page of shadow space. Allocating a full shadow page per mapping would > > > > therefore be wasteful. Furthermore, to ensure that different mappings > > > > use different shadow pages, mappings would have to be aligned to > > > > KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE. > > > > > > > > Instead, share backing space across multiple mappings. Allocate > > > > a backing page the first time a mapping in vmalloc space uses a > > > > particular page of the shadow region. Keep this page around > > > > regardless of whether the mapping is later freed - in the mean time > > > > the page could have become shared by another vmalloc mapping. > > > > > > > > This can in theory lead to unbounded memory growth, but the vmalloc > > > > allocator is pretty good at reusing addresses, so the practical memory > > > > usage grows at first but then stays fairly stable. > > > > > > I guess people having gigabytes of memory don't mind, but I'm concerned > > > about tiny targets with very little amount of memory. I have boards with > > > as > > > little as 32Mbytes of RAM. The shadow region for the linear space already > > > takes one eighth of the RAM. I'd rather avoid keeping unused shadow pages > > > busy. > > > > I think this depends on how much shadow would be in constant use vs what > > would get left unused. If the amount in constant use is sufficiently > > large (or the residue is sufficiently small), then it may not be > > worthwhile to support KASAN_VMALLOC on such small systems. > > > > > Each page of shadow memory represent 8 pages of real memory. Could we use > > > page_ref to count how many pieces of a shadow page are used so that we can > > > free it when the ref count decreases to 0. > > > > > > > This requires architecture support to actually use: arches must stop > > > > mapping the read-only zero page over portion of the shadow region that > > > > covers the vmalloc space and instead leave it unmapped. > > > > > > Why 'must' ? Couldn't we switch back and forth from the zero page to real > > > page on demand ? > > > > > > If the zero page is not mapped for unused vmalloc space, bad memory > > > accesses > > > will Oops on the shadow memory access instead of Oopsing on the real bad > > > access, making it more difficult to locate and identify the issue. > > > > I agree this isn't nice, though FWIW this can already happen today for > > bad addresses that fall outside of the usual kernel address space. We > > could make the !KASAN_INLINE checks resilient to this by using > > probe_kernel_read() to check the shadow, and treating unmapped shadow as > > poison. > > Could we instead modify the page fault handlers to detect this case > and print a useful message? In general we can't know if a bad access was a KASAN shadow lookup (e.g. since the shadow of NULL falls outside of the shadow region), but we could always print a message using kasan_shadow_to_mem() for any unhandled fault to suggeest what the "real" address might have been. Thanks, Mark.
Re: [PATCH v4 1/3] kasan: support backing vmalloc space with real shadow memory
>> > Instead, share backing space across multiple mappings. Allocate
>> > a backing page the first time a mapping in vmalloc space uses a
>> > particular page of the shadow region. Keep this page around
>> > regardless of whether the mapping is later freed - in the mean time
>> > the page could have become shared by another vmalloc mapping.
>> >
>> > This can in theory lead to unbounded memory growth, but the vmalloc
>> > allocator is pretty good at reusing addresses, so the practical memory
>> > usage grows at first but then stays fairly stable.
>>
>> I guess people having gigabytes of memory don't mind, but I'm concerned
>> about tiny targets with very little amount of memory. I have boards with as
>> little as 32Mbytes of RAM. The shadow region for the linear space already
>> takes one eighth of the RAM. I'd rather avoid keeping unused shadow pages
>> busy.
>
> I think this depends on how much shadow would be in constant use vs what
> would get left unused. If the amount in constant use is sufficiently
> large (or the residue is sufficiently small), then it may not be
> worthwhile to support KASAN_VMALLOC on such small systems.
I'm not unsympathetic to the cause of small-memory systems, but this is
useful as-is for x86, especially for VMAP_STACK. arm64 and s390 have
already been able to make use of it as well. So unless the design is
going to make it difficult to extend to small-memory systems - if it
bakes in concepts or APIs that are going to make things harder - I think
it might be worth merging as is. (pending the fixes for documentation
nits etc that you point out.)
>> Each page of shadow memory represent 8 pages of real memory. Could we use
>> page_ref to count how many pieces of a shadow page are used so that we can
>> free it when the ref count decreases to 0.
I'm not sure how much of a difference it will make, but I'll have a look.
>> > This requires architecture support to actually use: arches must stop
>> > mapping the read-only zero page over portion of the shadow region that
>> > covers the vmalloc space and instead leave it unmapped.
>>
>> Why 'must' ? Couldn't we switch back and forth from the zero page to real
>> page on demand ?
This code as currently written will not work if the architecture maps
the zero page over the portion of the shadow region that covers the
vmalloc space. So it's an implementation 'must' rather than a laws of
the universe 'must'.
We could perhaps map the zero page, but:
- you have to be really careful to get it right. If you accidentally
map the zero page onto memory where you shouldn't, you may permit
memory accesses that you should catch.
We could ameliorate this by taking Mark's suggestion and mapping a
poision page over the vmalloc space instead.
- I'm not sure what benefit is provided by having something mapped vs
leaving a hole, other than making the fault addresses more obvious.
- This gets complex, especially to do swapping correctly with respect
to various architectures' quirks (see e.g. 56eecdb912b5 "mm: Use
ptep/pmdp_set_numa() for updating _PAGE_NUMA bit" - ppc64 at least
requires that set_pte_at is never called on a valid PTE).
>> If the zero page is not mapped for unused vmalloc space, bad memory accesses
>> will Oops on the shadow memory access instead of Oopsing on the real bad
>> access, making it more difficult to locate and identify the issue.
I suppose. It's pretty easy on at least x86 and my draft ppc64
implementation to identify when an access falls into the shadow region
and then to reverse engineer the memory access that was being checked
based on the offset. As Andy points out, the fault handler could do this
automatically.
> I agree this isn't nice, though FWIW this can already happen today for
> bad addresses that fall outside of the usual kernel address space. We
> could make the !KASAN_INLINE checks resilient to this by using
> probe_kernel_read() to check the shadow, and treating unmapped shadow as
> poison.
>
> It's also worth noting that flipping back and forth isn't generally safe
> unless going via an invalid table entry, so there'd still be windows
> where a bad access might not have shadow mapped.
>
> We'd need to reuse the common p4d/pud/pmd/pte tables for unallocated
> regions, or the tables alone would consume significant amounts of memory
> (e..g ~32GiB for arm64 defconfig), and thus we'd need to be able to
> switch all levels between pgd and pte, which is much more complicated.
>
> I strongly suspect that the additional complexity will outweigh the
> benefit.
>
I'm not opposed to this in principle but I am also concerned about the
complexity involved.
Regards,
Daniel
> [...]
>
>> > +#ifdef CONFIG_KASAN_VMALLOC
>> > +static int kasan_populate_vmalloc_pte(pte_t *ptep, unsigned long addr,
>> > +void *unused)
>> > +{
>> > + unsigned long page;
>> > + pte_t pte;
>> > +
>> > + if (likely(!pte_none(*ptep)))
>> > + return 0;
>>
>> Prior
Re: [PATCH v4 1/3] kasan: support backing vmalloc space with real shadow memory
On Fri, Aug 16, 2019 at 10:08 AM Mark Rutland wrote: > > Hi Christophe, > > On Fri, Aug 16, 2019 at 09:47:00AM +0200, Christophe Leroy wrote: > > Le 15/08/2019 à 02:16, Daniel Axtens a écrit : > > > Hook into vmalloc and vmap, and dynamically allocate real shadow > > > memory to back the mappings. > > > > > > Most mappings in vmalloc space are small, requiring less than a full > > > page of shadow space. Allocating a full shadow page per mapping would > > > therefore be wasteful. Furthermore, to ensure that different mappings > > > use different shadow pages, mappings would have to be aligned to > > > KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE. > > > > > > Instead, share backing space across multiple mappings. Allocate > > > a backing page the first time a mapping in vmalloc space uses a > > > particular page of the shadow region. Keep this page around > > > regardless of whether the mapping is later freed - in the mean time > > > the page could have become shared by another vmalloc mapping. > > > > > > This can in theory lead to unbounded memory growth, but the vmalloc > > > allocator is pretty good at reusing addresses, so the practical memory > > > usage grows at first but then stays fairly stable. > > > > I guess people having gigabytes of memory don't mind, but I'm concerned > > about tiny targets with very little amount of memory. I have boards with as > > little as 32Mbytes of RAM. The shadow region for the linear space already > > takes one eighth of the RAM. I'd rather avoid keeping unused shadow pages > > busy. > > I think this depends on how much shadow would be in constant use vs what > would get left unused. If the amount in constant use is sufficiently > large (or the residue is sufficiently small), then it may not be > worthwhile to support KASAN_VMALLOC on such small systems. > > > Each page of shadow memory represent 8 pages of real memory. Could we use > > page_ref to count how many pieces of a shadow page are used so that we can > > free it when the ref count decreases to 0. > > > > > This requires architecture support to actually use: arches must stop > > > mapping the read-only zero page over portion of the shadow region that > > > covers the vmalloc space and instead leave it unmapped. > > > > Why 'must' ? Couldn't we switch back and forth from the zero page to real > > page on demand ? > > > > If the zero page is not mapped for unused vmalloc space, bad memory accesses > > will Oops on the shadow memory access instead of Oopsing on the real bad > > access, making it more difficult to locate and identify the issue. > > I agree this isn't nice, though FWIW this can already happen today for > bad addresses that fall outside of the usual kernel address space. We > could make the !KASAN_INLINE checks resilient to this by using > probe_kernel_read() to check the shadow, and treating unmapped shadow as > poison. Could we instead modify the page fault handlers to detect this case and print a useful message?
Re: [PATCH v4 1/3] kasan: support backing vmalloc space with real shadow memory
Hi Christophe,
On Fri, Aug 16, 2019 at 09:47:00AM +0200, Christophe Leroy wrote:
> Le 15/08/2019 à 02:16, Daniel Axtens a écrit :
> > Hook into vmalloc and vmap, and dynamically allocate real shadow
> > memory to back the mappings.
> >
> > Most mappings in vmalloc space are small, requiring less than a full
> > page of shadow space. Allocating a full shadow page per mapping would
> > therefore be wasteful. Furthermore, to ensure that different mappings
> > use different shadow pages, mappings would have to be aligned to
> > KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE.
> >
> > Instead, share backing space across multiple mappings. Allocate
> > a backing page the first time a mapping in vmalloc space uses a
> > particular page of the shadow region. Keep this page around
> > regardless of whether the mapping is later freed - in the mean time
> > the page could have become shared by another vmalloc mapping.
> >
> > This can in theory lead to unbounded memory growth, but the vmalloc
> > allocator is pretty good at reusing addresses, so the practical memory
> > usage grows at first but then stays fairly stable.
>
> I guess people having gigabytes of memory don't mind, but I'm concerned
> about tiny targets with very little amount of memory. I have boards with as
> little as 32Mbytes of RAM. The shadow region for the linear space already
> takes one eighth of the RAM. I'd rather avoid keeping unused shadow pages
> busy.
I think this depends on how much shadow would be in constant use vs what
would get left unused. If the amount in constant use is sufficiently
large (or the residue is sufficiently small), then it may not be
worthwhile to support KASAN_VMALLOC on such small systems.
> Each page of shadow memory represent 8 pages of real memory. Could we use
> page_ref to count how many pieces of a shadow page are used so that we can
> free it when the ref count decreases to 0.
>
> > This requires architecture support to actually use: arches must stop
> > mapping the read-only zero page over portion of the shadow region that
> > covers the vmalloc space and instead leave it unmapped.
>
> Why 'must' ? Couldn't we switch back and forth from the zero page to real
> page on demand ?
>
> If the zero page is not mapped for unused vmalloc space, bad memory accesses
> will Oops on the shadow memory access instead of Oopsing on the real bad
> access, making it more difficult to locate and identify the issue.
I agree this isn't nice, though FWIW this can already happen today for
bad addresses that fall outside of the usual kernel address space. We
could make the !KASAN_INLINE checks resilient to this by using
probe_kernel_read() to check the shadow, and treating unmapped shadow as
poison.
It's also worth noting that flipping back and forth isn't generally safe
unless going via an invalid table entry, so there'd still be windows
where a bad access might not have shadow mapped.
We'd need to reuse the common p4d/pud/pmd/pte tables for unallocated
regions, or the tables alone would consume significant amounts of memory
(e..g ~32GiB for arm64 defconfig), and thus we'd need to be able to
switch all levels between pgd and pte, which is much more complicated.
I strongly suspect that the additional complexity will outweigh the
benefit.
[...]
> > +#ifdef CONFIG_KASAN_VMALLOC
> > +static int kasan_populate_vmalloc_pte(pte_t *ptep, unsigned long addr,
> > + void *unused)
> > +{
> > + unsigned long page;
> > + pte_t pte;
> > +
> > + if (likely(!pte_none(*ptep)))
> > + return 0;
>
> Prior to this, the zero shadow area should be mapped, and the test should
> be:
>
> if (likely(pte_pfn(*ptep) != PHYS_PFN(__pa(kasan_early_shadow_page
> return 0;
As above, this would need a more comprehensive redesign, so I don't
think it's worth going into that level of nit here. :)
If we do try to use common shadow for unallocate VA ranges, it probably
makes sense to have a common poison page that we can use, so that we can
report vmalloc-out-of-bounfds.
Thanks,
Mark.
Re: [PATCH v4 1/3] kasan: support backing vmalloc space with real shadow memory
Le 15/08/2019 à 02:16, Daniel Axtens a écrit : Hook into vmalloc and vmap, and dynamically allocate real shadow memory to back the mappings. Most mappings in vmalloc space are small, requiring less than a full page of shadow space. Allocating a full shadow page per mapping would therefore be wasteful. Furthermore, to ensure that different mappings use different shadow pages, mappings would have to be aligned to KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE. Instead, share backing space across multiple mappings. Allocate a backing page the first time a mapping in vmalloc space uses a particular page of the shadow region. Keep this page around regardless of whether the mapping is later freed - in the mean time the page could have become shared by another vmalloc mapping. This can in theory lead to unbounded memory growth, but the vmalloc allocator is pretty good at reusing addresses, so the practical memory usage grows at first but then stays fairly stable. I guess people having gigabytes of memory don't mind, but I'm concerned about tiny targets with very little amount of memory. I have boards with as little as 32Mbytes of RAM. The shadow region for the linear space already takes one eighth of the RAM. I'd rather avoid keeping unused shadow pages busy. Each page of shadow memory represent 8 pages of real memory. Could we use page_ref to count how many pieces of a shadow page are used so that we can free it when the ref count decreases to 0. This requires architecture support to actually use: arches must stop mapping the read-only zero page over portion of the shadow region that covers the vmalloc space and instead leave it unmapped. Why 'must' ? Couldn't we switch back and forth from the zero page to real page on demand ? If the zero page is not mapped for unused vmalloc space, bad memory accesses will Oops on the shadow memory access instead of Oopsing on the real bad access, making it more difficult to locate and identify the issue. This allows KASAN with VMAP_STACK, and will be needed for architectures that do not have a separate module space (e.g. powerpc64, which I am currently working on). It also allows relaxing the module alignment back to PAGE_SIZE. Why 'needed' ? powerpc32 doesn't have a separate module space and doesn't need that. Link: https://bugzilla.kernel.org/show_bug.cgi?id=202009 Acked-by: Vasily Gorbik Signed-off-by: Daniel Axtens [Mark: rework shadow allocation] Signed-off-by: Mark Rutland -- v2: let kasan_unpoison_shadow deal with ranges that do not use a full shadow byte. v3: relax module alignment rename to kasan_populate_vmalloc which is a much better name deal with concurrency correctly v4: Integrate Mark's rework Poision pages on vfree Handle allocation failures. I've tested this by inserting artificial failures and using test_vmalloc to stress it. I haven't handled the per-cpu case: it looked like it would require a messy hacking-up of the function to deal with an OOM failure case in a debug feature. --- Documentation/dev-tools/kasan.rst | 60 +++ include/linux/kasan.h | 24 +++ include/linux/moduleloader.h | 2 +- include/linux/vmalloc.h | 12 ++ lib/Kconfig.kasan | 16 lib/test_kasan.c | 26 mm/kasan/common.c | 67 +++ mm/kasan/generic_report.c | 3 ++ mm/kasan/kasan.h | 1 + mm/vmalloc.c | 28 - 10 files changed, 237 insertions(+), 2 deletions(-) diff --git a/Documentation/dev-tools/kasan.rst b/Documentation/dev-tools/kasan.rst index b72d07d70239..35fda484a672 100644 --- a/Documentation/dev-tools/kasan.rst +++ b/Documentation/dev-tools/kasan.rst @@ -215,3 +215,63 @@ brk handler is used to print bug reports. A potential expansion of this mode is a hardware tag-based mode, which would use hardware memory tagging support instead of compiler instrumentation and manual shadow memory manipulation. + +What memory accesses are sanitised by KASAN? + + +The kernel maps memory in a number of different parts of the address +space. This poses something of a problem for KASAN, which requires +that all addresses accessed by instrumented code have a valid shadow +region. + +The range of kernel virtual addresses is large: there is not enough +real memory to support a real shadow region for every address that +could be accessed by the kernel. + +By default +~~ + +By default, architectures only map real memory over the shadow region +for the linear mapping (and potentially other small areas). For all +other areas - such as vmalloc and vmemmap space - a single read-only +page is mapped over the shadow area. This read-only shadow page +declares all memory accesses as permitted. + +This presents a problem for modules: they do not
[PATCH v4 1/3] kasan: support backing vmalloc space with real shadow memory
Hook into vmalloc and vmap, and dynamically allocate real shadow memory to back the mappings. Most mappings in vmalloc space are small, requiring less than a full page of shadow space. Allocating a full shadow page per mapping would therefore be wasteful. Furthermore, to ensure that different mappings use different shadow pages, mappings would have to be aligned to KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE. Instead, share backing space across multiple mappings. Allocate a backing page the first time a mapping in vmalloc space uses a particular page of the shadow region. Keep this page around regardless of whether the mapping is later freed - in the mean time the page could have become shared by another vmalloc mapping. This can in theory lead to unbounded memory growth, but the vmalloc allocator is pretty good at reusing addresses, so the practical memory usage grows at first but then stays fairly stable. This requires architecture support to actually use: arches must stop mapping the read-only zero page over portion of the shadow region that covers the vmalloc space and instead leave it unmapped. This allows KASAN with VMAP_STACK, and will be needed for architectures that do not have a separate module space (e.g. powerpc64, which I am currently working on). It also allows relaxing the module alignment back to PAGE_SIZE. Link: https://bugzilla.kernel.org/show_bug.cgi?id=202009 Acked-by: Vasily Gorbik Signed-off-by: Daniel Axtens [Mark: rework shadow allocation] Signed-off-by: Mark Rutland -- v2: let kasan_unpoison_shadow deal with ranges that do not use a full shadow byte. v3: relax module alignment rename to kasan_populate_vmalloc which is a much better name deal with concurrency correctly v4: Integrate Mark's rework Poision pages on vfree Handle allocation failures. I've tested this by inserting artificial failures and using test_vmalloc to stress it. I haven't handled the per-cpu case: it looked like it would require a messy hacking-up of the function to deal with an OOM failure case in a debug feature. --- Documentation/dev-tools/kasan.rst | 60 +++ include/linux/kasan.h | 24 +++ include/linux/moduleloader.h | 2 +- include/linux/vmalloc.h | 12 ++ lib/Kconfig.kasan | 16 lib/test_kasan.c | 26 mm/kasan/common.c | 67 +++ mm/kasan/generic_report.c | 3 ++ mm/kasan/kasan.h | 1 + mm/vmalloc.c | 28 - 10 files changed, 237 insertions(+), 2 deletions(-) diff --git a/Documentation/dev-tools/kasan.rst b/Documentation/dev-tools/kasan.rst index b72d07d70239..35fda484a672 100644 --- a/Documentation/dev-tools/kasan.rst +++ b/Documentation/dev-tools/kasan.rst @@ -215,3 +215,63 @@ brk handler is used to print bug reports. A potential expansion of this mode is a hardware tag-based mode, which would use hardware memory tagging support instead of compiler instrumentation and manual shadow memory manipulation. + +What memory accesses are sanitised by KASAN? + + +The kernel maps memory in a number of different parts of the address +space. This poses something of a problem for KASAN, which requires +that all addresses accessed by instrumented code have a valid shadow +region. + +The range of kernel virtual addresses is large: there is not enough +real memory to support a real shadow region for every address that +could be accessed by the kernel. + +By default +~~ + +By default, architectures only map real memory over the shadow region +for the linear mapping (and potentially other small areas). For all +other areas - such as vmalloc and vmemmap space - a single read-only +page is mapped over the shadow area. This read-only shadow page +declares all memory accesses as permitted. + +This presents a problem for modules: they do not live in the linear +mapping, but in a dedicated module space. By hooking in to the module +allocator, KASAN can temporarily map real shadow memory to cover +them. This allows detection of invalid accesses to module globals, for +example. + +This also creates an incompatibility with ``VMAP_STACK``: if the stack +lives in vmalloc space, it will be shadowed by the read-only page, and +the kernel will fault when trying to set up the shadow data for stack +variables. + +CONFIG_KASAN_VMALLOC + + +With ``CONFIG_KASAN_VMALLOC``, KASAN can cover vmalloc space at the +cost of greater memory usage. Currently this is only supported on x86. + +This works by hooking into vmalloc and vmap, and dynamically +allocating real shadow memory to back the mappings. + +Most mappings in vmalloc space are small, requiring less than a full +page of shadow space. Allocating a full shadow page per mapping would +therefore be wasteful. Furthermore, to ensure that different mappings
