vmalloced stacks and scatterwalk_map_and_copy()

vmalloced stacks and scatterwalk_map_and_copy()

[Eric Biggers]

Hello,

I hit the BUG_ON() in arch/x86/mm/physaddr.c:26 while testing some crypto code
in an x86_64 kernel with CONFIG_DEBUG_VIRTUAL=y and CONFIG_VMAP_STACK=y:

	/* carry flag will be set if starting x was >= PAGE_OFFSET */
	VIRTUAL_BUG_ON((x > y) || !phys_addr_valid(x));

The problem is the following code in scatterwalk_map_and_copy() in
crypto/scatterwalk.c, which tries to determine if the buffer passed in aliases
the physical memory of the first segment of the scatterlist:

        if (sg_page(sg) == virt_to_page(buf) &&
            sg->offset == offset_in_page(buf))
                return;

If 'buf' is on the stack with CONFIG_VMAP_STACK=y it will be a vmalloc address.
And virt_to_page(buf) does not have a meaningful behavior on vmalloc addresses.
Hence the BUG.

I don't think this should be fixed by forbidding passing a stack address to
scatterwalk_map_and_copy().  Not only are there a number of callers that
explicitly use stack addresses (e.g. poly_verify_tag() in
crypto/chacha20poly1305.c) but it's also possible for a whole skcipher_request
to be allocated on the stack with the SKCIPHER_REQUEST_ON_STACK() macro.  Note
that this has nothing to do with DMA per se.

Another solution would be to make scatterwalk_map_and_copy() explicitly check
for virt_addr_valid().  But this would make the behavior of
scatterwalk_map_and_copy() confusing because it would detect aliasing but only
under some circumstances, and it would depend on the kernel config.

Currently I think the best solution would be to require that callers to
scatterwalk_map_and_copy() do not alias their source and destination.  Then the
alias check could be removed.  This check has only been there since v4.2 (commit
74412fd5d71b6), so I'd hope not many callers rely on the behavior.  I'm not sure
exactly which ones do, though.

Thoughts on this?

Eric

Re: vmalloced stacks and scatterwalk_map_and_copy()

[Andy Lutomirski]

On Thu, Nov 3, 2016 at 11:16 AM, Eric Biggers <ebiggers@google.com> wrote:
> Hello,
>
> I hit the BUG_ON() in arch/x86/mm/physaddr.c:26 while testing some crypto code
> in an x86_64 kernel with CONFIG_DEBUG_VIRTUAL=y and CONFIG_VMAP_STACK=y:
>
>         /* carry flag will be set if starting x was >= PAGE_OFFSET */
>         VIRTUAL_BUG_ON((x > y) || !phys_addr_valid(x));
>
> The problem is the following code in scatterwalk_map_and_copy() in
> crypto/scatterwalk.c, which tries to determine if the buffer passed in aliases
> the physical memory of the first segment of the scatterlist:
>
>         if (sg_page(sg) == virt_to_page(buf) &&
>             sg->offset == offset_in_page(buf))
>                 return;

...

>
> Currently I think the best solution would be to require that callers to
> scatterwalk_map_and_copy() do not alias their source and destination.  Then the
> alias check could be removed.  This check has only been there since v4.2 (commit
> 74412fd5d71b6), so I'd hope not many callers rely on the behavior.  I'm not sure
> exactly which ones do, though.
>
> Thoughts on this?

The relevant commit is:

commit 74412fd5d71b6eda0beb302aa467da000f0d530c
Author: Herbert Xu <herbert@gondor.apana.org.au>
Date:   Thu May 21 15:11:12 2015 +0800

    crypto: scatterwalk - Check for same address in map_and_copy

    This patch adds a check for in scatterwalk_map_and_copy to avoid
    copying from the same address to the same address.  This is going
    to be used for IV copying in AEAD IV generators.

    There is no provision for partial overlaps.

    This patch also uses the new scatterwalk_ffwd instead of doing
    it by hand in scatterwalk_map_and_copy.

    Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Herbert, can you clarify this?  The check seems rather bizarre --
you're doing an incomplete check for aliasing and skipping the whole
copy if the beginning aliases.  In any event the stack *can't*
reasonably alias the scatterlist because a scatterlist can't safely
point to the stack.  Is there any code that actually relies on the
aliasing-detecting behavior?

Also, Herbert, it seems like the considerable majority of the crypto
code is acting on kernel virtual memory addresses and does software
processing.  Would it perhaps make sense to add a kvec-based or
iov_iter-based interface to the crypto code?  I bet it would be quite
a bit faster and it would make crypto on stack buffers work directly.

Re: vmalloced stacks and scatterwalk_map_and_copy()

[Eric Biggers]

On Thu, Nov 03, 2016 at 01:30:49PM -0700, Andy Lutomirski wrote:
> 
> Also, Herbert, it seems like the considerable majority of the crypto
> code is acting on kernel virtual memory addresses and does software
> processing.  Would it perhaps make sense to add a kvec-based or
> iov_iter-based interface to the crypto code?  I bet it would be quite
> a bit faster and it would make crypto on stack buffers work directly.

I'd like to hear Herbert's opinion on this too, but as I understand it, if a
symmetric cipher API operating on virtual addresses was added, similar to the
existing "shash" API it would only allow software processing.  Whereas with the
current API you can request a transform and use it the same way regardless of
whether the crypto framework has chosen a software or hardware implementation,
or a combination thereof.  If this wasn't a concern then I expect using virtual
addresses would indeed simplify things a lot, at least for users not already
working with physical memory (struct page).

Either way, in the near term it looks like 4.9 will be released with the new
behavior that encryption/decryption is not supported on stack buffers.
Separately from the scatterwalk_map_and_copy() issue, today I've found two
places in the filesystem-level encryption code that do encryption on stack
buffers and therefore hit the 'BUG_ON(!virt_addr_valid(buf));' in sg_set_buf().
I will be sending patches to fix these, but I suspect there may be more crypto
API users elsewhere that have this same problem.

Eric

Re: vmalloced stacks and scatterwalk_map_and_copy()

[Eric Biggers]

On Thu, Nov 03, 2016 at 02:12:07PM -0700, Eric Biggers wrote:
> On Thu, Nov 03, 2016 at 01:30:49PM -0700, Andy Lutomirski wrote:
> > 
> > Also, Herbert, it seems like the considerable majority of the crypto
> > code is acting on kernel virtual memory addresses and does software
> > processing.  Would it perhaps make sense to add a kvec-based or
> > iov_iter-based interface to the crypto code?  I bet it would be quite
> > a bit faster and it would make crypto on stack buffers work directly.
> 
> I'd like to hear Herbert's opinion on this too, but as I understand it, if a
> symmetric cipher API operating on virtual addresses was added, similar to the
> existing "shash" API it would only allow software processing.  Whereas with the
> current API you can request a transform and use it the same way regardless of
> whether the crypto framework has chosen a software or hardware implementation,
> or a combination thereof.  If this wasn't a concern then I expect using virtual
> addresses would indeed simplify things a lot, at least for users not already
> working with physical memory (struct page).
> 
> Either way, in the near term it looks like 4.9 will be released with the new
> behavior that encryption/decryption is not supported on stack buffers.
> Separately from the scatterwalk_map_and_copy() issue, today I've found two
> places in the filesystem-level encryption code that do encryption on stack
> buffers and therefore hit the 'BUG_ON(!virt_addr_valid(buf));' in sg_set_buf().
> I will be sending patches to fix these, but I suspect there may be more crypto
> API users elsewhere that have this same problem.
> 
> Eric

[Added linux-mm to Cc]

For what it's worth, grsecurity has a special case to allow a scatterlist entry
to be created from a stack buffer:

	static inline void sg_set_buf(struct scatterlist *sg, const void *buf,
				      unsigned int buflen)
	{
		const void *realbuf = buf;

	#ifdef CONFIG_GRKERNSEC_KSTACKOVERFLOW
		if (object_starts_on_stack(buf))
			realbuf = buf - current->stack + current->lowmem_stack;
	#endif

	#ifdef CONFIG_DEBUG_SG
		BUG_ON(!virt_addr_valid(realbuf));
	#endif
		sg_set_page(sg, virt_to_page(realbuf), buflen, offset_in_page(realbuf));
	}

It seems to maintain two virtual mappings for each stack, a physically
contiguous one (task_struct.lowmem_stack) and a physically non-contiguous one
(task_struct.stack).  This seems different from upstream CONFIG_VMAP_STACK which
just maintains a physically non-contiguous one.

I don't know about all the relative merits of the two approaches.  But one of
the things that will need to be done with the currently upstream approach is
that all callers of sg_set_buf() will need to be checked to make sure they
aren't using stack addresses, and any that are will need to be updated to do
otherwise, e.g. by using heap-allocated memory.  I suppose this is already
happening, but in the case of the crypto API it will probably take a while for
all the users to be identified and updated.  (And it's not always clear from the
local context whether something can be stack memory or not, e.g. the memory for
crypto request objects may be either.)

Eric

Re: vmalloced stacks and scatterwalk_map_and_copy()

[Andy Lutomirski]

On Thu, Nov 3, 2016 at 4:10 PM, Eric Biggers <ebiggers@google.com> wrote:
> On Thu, Nov 03, 2016 at 02:12:07PM -0700, Eric Biggers wrote:
>> On Thu, Nov 03, 2016 at 01:30:49PM -0700, Andy Lutomirski wrote:
>> >
>> > Also, Herbert, it seems like the considerable majority of the crypto
>> > code is acting on kernel virtual memory addresses and does software
>> > processing.  Would it perhaps make sense to add a kvec-based or
>> > iov_iter-based interface to the crypto code?  I bet it would be quite
>> > a bit faster and it would make crypto on stack buffers work directly.
>>
>> I'd like to hear Herbert's opinion on this too, but as I understand it, if a
>> symmetric cipher API operating on virtual addresses was added, similar to the
>> existing "shash" API it would only allow software processing.  Whereas with the
>> current API you can request a transform and use it the same way regardless of
>> whether the crypto framework has chosen a software or hardware implementation,
>> or a combination thereof.  If this wasn't a concern then I expect using virtual
>> addresses would indeed simplify things a lot, at least for users not already
>> working with physical memory (struct page).
>>
>> Either way, in the near term it looks like 4.9 will be released with the new
>> behavior that encryption/decryption is not supported on stack buffers.
>> Separately from the scatterwalk_map_and_copy() issue, today I've found two
>> places in the filesystem-level encryption code that do encryption on stack
>> buffers and therefore hit the 'BUG_ON(!virt_addr_valid(buf));' in sg_set_buf().
>> I will be sending patches to fix these, but I suspect there may be more crypto
>> API users elsewhere that have this same problem.
>>
>> Eric
>
> [Added linux-mm to Cc]
>
> For what it's worth, grsecurity has a special case to allow a scatterlist entry
> to be created from a stack buffer:
>
>         static inline void sg_set_buf(struct scatterlist *sg, const void *buf,
>                                       unsigned int buflen)
>         {
>                 const void *realbuf = buf;
>
>         #ifdef CONFIG_GRKERNSEC_KSTACKOVERFLOW
>                 if (object_starts_on_stack(buf))
>                         realbuf = buf - current->stack + current->lowmem_stack;
>         #endif
>
>         #ifdef CONFIG_DEBUG_SG
>                 BUG_ON(!virt_addr_valid(realbuf));
>         #endif
>                 sg_set_page(sg, virt_to_page(realbuf), buflen, offset_in_page(realbuf));
>         }

Yes, that's how grsecurity works.  The upstream version is going to do
it right instead of hacking around it.

> I don't know about all the relative merits of the two approaches.  But one of
> the things that will need to be done with the currently upstream approach is
> that all callers of sg_set_buf() will need to be checked to make sure they
> aren't using stack addresses, and any that are will need to be updated to do
> otherwise, e.g. by using heap-allocated memory.

I tried to do this, but I may have missed a couple example.

>  I suppose this is already
> happening, but in the case of the crypto API it will probably take a while for
> all the users to be identified and updated.  (And it's not always clear from the
> local context whether something can be stack memory or not, e.g. the memory for
> crypto request objects may be either.)

The crypto request objects can live on the stack just fine.  It's the
request buffers that need to live elsewhere (or the alternative
interfaces can be used, or the crypto core code can start using
something other than scatterlists).

--Andy

Re: vmalloced stacks and scatterwalk_map_and_copy()

[Eric Biggers]

On Thu, Nov 03, 2016 at 08:57:49PM -0700, Andy Lutomirski wrote:
> 
> The crypto request objects can live on the stack just fine.  It's the
> request buffers that need to live elsewhere (or the alternative
> interfaces can be used, or the crypto core code can start using
> something other than scatterlists).
> 

There are cases where a crypto operation is done on a buffer embedded in a
request object.  The example I'm aware of is in the GCM implementation
(crypto/gcm.c).  Basically it needs to encrypt 16 zero bytes prepended with the
actual data, so it fills a buffer in the request object
(crypto_gcm_req_priv_ctx.auth_tag) with zeroes and builds a new scatterlist
which covers both this buffer and the original data scatterlist.

Granted, GCM provides the aead interface not the skcipher interface, and
currently there is no AEAD_REQUEST_ON_STACK() macro like there is a
SKCIPHER_REQUEST_ON_STACK() macro.  So maybe no one is creating aead requests on
the stack right now.  But it's something to watch out for.

Eric

Re: vmalloced stacks and scatterwalk_map_and_copy()

[Andy Lutomirski]

[Adding Thorsten to help keep this from getting lost]

On Thu, Nov 3, 2016 at 1:30 PM, Andy Lutomirski <luto@amacapital.net> wrote:
> On Thu, Nov 3, 2016 at 11:16 AM, Eric Biggers <ebiggers@google.com> wrote:
>> Hello,
>>
>> I hit the BUG_ON() in arch/x86/mm/physaddr.c:26 while testing some crypto code
>> in an x86_64 kernel with CONFIG_DEBUG_VIRTUAL=y and CONFIG_VMAP_STACK=y:
>>
>>         /* carry flag will be set if starting x was >= PAGE_OFFSET */
>>         VIRTUAL_BUG_ON((x > y) || !phys_addr_valid(x));
>>
>> The problem is the following code in scatterwalk_map_and_copy() in
>> crypto/scatterwalk.c, which tries to determine if the buffer passed in aliases
>> the physical memory of the first segment of the scatterlist:
>>
>>         if (sg_page(sg) == virt_to_page(buf) &&
>>             sg->offset == offset_in_page(buf))
>>                 return;
>
> ...
>
>>
>> Currently I think the best solution would be to require that callers to
>> scatterwalk_map_and_copy() do not alias their source and destination.  Then the
>> alias check could be removed.  This check has only been there since v4.2 (commit
>> 74412fd5d71b6), so I'd hope not many callers rely on the behavior.  I'm not sure
>> exactly which ones do, though.
>>
>> Thoughts on this?
>
> The relevant commit is:
>
> commit 74412fd5d71b6eda0beb302aa467da000f0d530c
> Author: Herbert Xu <herbert@gondor.apana.org.au>
> Date:   Thu May 21 15:11:12 2015 +0800
>
>     crypto: scatterwalk - Check for same address in map_and_copy
>
>     This patch adds a check for in scatterwalk_map_and_copy to avoid
>     copying from the same address to the same address.  This is going
>     to be used for IV copying in AEAD IV generators.
>
>     There is no provision for partial overlaps.
>
>     This patch also uses the new scatterwalk_ffwd instead of doing
>     it by hand in scatterwalk_map_and_copy.
>
>     Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
>
> Herbert, can you clarify this?  The check seems rather bizarre --
> you're doing an incomplete check for aliasing and skipping the whole
> copy if the beginning aliases.  In any event the stack *can't*
> reasonably alias the scatterlist because a scatterlist can't safely
> point to the stack.  Is there any code that actually relies on the
> aliasing-detecting behavior?
>
> Also, Herbert, it seems like the considerable majority of the crypto
> code is acting on kernel virtual memory addresses and does software
> processing.  Would it perhaps make sense to add a kvec-based or
> iov_iter-based interface to the crypto code?  I bet it would be quite
> a bit faster and it would make crypto on stack buffers work directly.


Ping, everyone!

It's getting quite close to 4.9 release time.  Is there an actual bug
here?  Because, if so, we need to fix it.  My preference is to just
delete the weird aliasing check, but it would be really nice to know
if that check is needed for some reason.

--Andy

-- 
Andy Lutomirski
AMA Capital Management, LLC

Re: vmalloced stacks and scatterwalk_map_and_copy()

[Herbert Xu]

On Sun, Nov 20, 2016 at 06:19:48PM -0800, Andy Lutomirski wrote:
>
> > Herbert, can you clarify this?  The check seems rather bizarre --
> > you're doing an incomplete check for aliasing and skipping the whole
> > copy if the beginning aliases.  In any event the stack *can't*
> > reasonably alias the scatterlist because a scatterlist can't safely
> > point to the stack.  Is there any code that actually relies on the
> > aliasing-detecting behavior?

Well at the time the IPsec stack would pass an IV that pointed
into the actual request, which is what prompted that patch.  The
IPsec code has since been changed to provide a separate IV so this
check is no longer necessary.

I will remove it with this patch.

---8<---
crypto: scatterwalk - Remove unnecessary aliasing check in map_and_copy

The aliasing check in map_and_copy is no longer necessary because
the IPsec ESP code no longer provides an IV that points into the
actual request data.  As this check is now triggering BUG checks
due to the vmalloced stack code, I'm removing it.

Reported-by: Eric Biggers <ebiggers@google.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

diff --git a/crypto/scatterwalk.c b/crypto/scatterwalk.c
index 52ce17a..c16c94f8 100644
--- a/crypto/scatterwalk.c
+++ b/crypto/scatterwalk.c
@@ -68,10 +68,6 @@ void scatterwalk_map_and_copy(void *buf, struct scatterlist *sg,
 
 	sg = scatterwalk_ffwd(tmp, sg, start);
 
-	if (sg_page(sg) == virt_to_page(buf) &&
-	    sg->offset == offset_in_page(buf))
-		return;
-
 	scatterwalk_start(&walk, sg);
 	scatterwalk_copychunks(buf, &walk, nbytes, out);
 	scatterwalk_done(&walk, out, 0);
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: vmalloced stacks and scatterwalk_map_and_copy()

[Eric Biggers]

On Mon, Nov 21, 2016 at 04:26:19PM +0800, Herbert Xu wrote:
> crypto: scatterwalk - Remove unnecessary aliasing check in map_and_copy
> 
> The aliasing check in map_and_copy is no longer necessary because
> the IPsec ESP code no longer provides an IV that points into the
> actual request data.  As this check is now triggering BUG checks
> due to the vmalloced stack code, I'm removing it.
> 
> Reported-by: Eric Biggers <ebiggers@google.com>
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
> 
> diff --git a/crypto/scatterwalk.c b/crypto/scatterwalk.c
> index 52ce17a..c16c94f8 100644
> --- a/crypto/scatterwalk.c
> +++ b/crypto/scatterwalk.c
> @@ -68,10 +68,6 @@ void scatterwalk_map_and_copy(void *buf, struct scatterlist *sg,
>  
>  	sg = scatterwalk_ffwd(tmp, sg, start);
>  
> -	if (sg_page(sg) == virt_to_page(buf) &&
> -	    sg->offset == offset_in_page(buf))
> -		return;
> -
>  	scatterwalk_start(&walk, sg);
>  	scatterwalk_copychunks(buf, &walk, nbytes, out);
>  	scatterwalk_done(&walk, out, 0);

This looks fine to me if you're confident that the aliasing check is indeed no
longer necessary.

Another idea I had was to replace memcpy() with memmove().  But I don't want to
be in a situation where we're stuck with memmove() forever because of users who
probably don't even exist.

Eric