vmalloced stacks and scatterwalk_map_and_copy()

DISCUSSION Eric Biggers 3 participants 9 messages Nov 3, 2016 – Nov 21, 2016

Subsystems (2)

Memory management Crypto API

lore

Share & tools

lore

Eric Biggers

author

2016-11-03 18:16 UTC #0 lore raw

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

Andy Lutomirski

2016-11-03 20:30 UTC #1 lore raw

Quoted 15 lines · 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;

...

Quoted 8 lines

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 <[email protected]>
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 <[email protected]>

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.

Eric Biggers

author

2016-11-03 21:12 UTC #2 lore raw

Quoted 6 lines · Andy Lutomirski

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

Eric Biggers

author

2016-11-03 23:10 UTC #3 lore raw

Quoted 25 lines · Eric Biggers

Quoted 6 lines · Andy Lutomirski
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.

Quoted 1 line

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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Andy Lutomirski

2016-11-04 03:57 UTC #4 lore raw

Quoted 33 lines · Eric Biggers

Quoted 25 lines · Eric Biggers
Quoted 6 lines · Andy Lutomirski
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.
Quoted 1 line
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:

Quoted 15 lines

        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.

Quoted 5 lines

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.

Quoted 5 lines

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

Eric Biggers

author

2016-11-04 17:05 UTC #5 lore raw

Quoted 6 lines · Andy Lutomirski

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

Andy Lutomirski

2016-11-21 02:19 UTC #6 lore raw

In reply to Andy Lutomirski

[Adding Thorsten to help keep this from getting lost]

Quoted 54 lines · Andy Lutomirski

Quoted 15 lines · 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;
...
Quoted 8 lines
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 <[email protected]>
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 <[email protected]>
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?

Quoted 5 lines

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

Signature · 2 lines

Andy Lutomirski
AMA Capital Management, LLC

Herbert Xu

maintainer

2016-11-21 08:26 UTC #7 lore raw

Quoted 7 lines · Andy Lutomirski

Quoted 7 lines
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 <[email protected]>

Signed-off-by Herbert Xu <[email protected]>

crypto/scatterwalk.c +0 -4

index 52ce17a..c16c94f8 100644
@@ -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);

Signature · 3 lines

Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Eric Biggers

author

2016-11-21 18:08 UTC #8 lore raw

Quoted 15 lines · Herbert Xu

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 <[email protected]>
Signed-off-by Herbert Xu <[email protected]>
crypto/scatterwalk.c +0 -0
index 52ce17a..c16c94f8 100644

crypto/scatterwalk.c void scatterwalk_map_and_copy(void *buf, struct scatterlist *sg, · line 73

Quoted 10 lines

crypto/scatterwalk.c +0 -4

@@ -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