compiler: prevent dead store elimination
Subsystems (4)
PATCH 1/1 compiler: prevent dead store elimination
Due to optimization A call to memset() may be removed as a dead store when the buffer is not used after its value is overwritten. The new function secure_bzero() ensures a section of memory is padded with zeroes.
Quoted 1 line
From the GCC manual, section 5.37:
If your assembler instructions access memory in an unpredictable fashion, add `memory' to the list of clobbered registers. This will cause GCC to not keep memory values cached in registers across the assembler instruction and not optimize stores or loads to that memory.
Every byte in the [p,p+n[ range must be used. If you only use the first byte, via e.g. asm("" :: "m"(*(char*)p)), then the compiler _will_ skip scrubbing bytes beyond the first. This works with gcc-3.2.3 up to gcc-4.4.3.
--- include/linux/compiler-gcc.h | 11 +++++++++++ include/linux/compiler-intel.h | 2 ++ include/linux/string.h | 1 + lib/string.c | 13 +++++++++++++ 4 files changed, 27 insertions(+), 0 deletions(-)
Thanks all for the required information, checkpatch.pl and compile tested. In my (non-kernel) testcase this prevents dead store elimination. Comments?
Roel
include/linux/compiler-gcc.h +11 -0
@@ -12,6 +12,17 @@#define barrier () __asm__ __volatile__("": : :"memory")/* +* Dead store elimination (DSE) is an optimization that may remove a write to +* a buffer that is not used anymore. Use ARRAY_PREVENT_DSE after a write when +* the scrub is required for security reasons. +*/ +#define ARRAY_PREVENT_DSE (p, n) \ + do { \ + struct __scrub { char c[n]; }; \ + asm("" : : "m"(*(struct __scrub *)p)); \ + } while (0) + +/* * This macro obfuscates arithmetic on a variable address so that gcc * shouldn't recognize the original var, and make assumptions about it. *
include/linux/compiler-intel.h +2 -0
@@ -14,9 +14,11 @@* It uses intrinsics to do the equivalent things. */ #undef barrier +#undef ARRAY_PREVENT_DSE#undef RELOC_HIDE#define barrier () __memory_barrier() +#define ARRAY_PREVENT_DSE (p, n)#define RELOC_HIDE (ptr, off) \ ({ unsigned long __ptr; \
include/linux/string.h +1 -0
@@ -118,6 +118,7 @@ extern void * memchr(const void *,int,__kernel_size_t);extern char *kstrdup (const char *s,gfp_t gfp);extern char *kstrndup (const char *s,size_t len,gfp_t gfp);extern void *kmemdup (const void *src,size_t len,gfp_t gfp); +extern void secure_bzero (void *,__kernel_size_t );extern char **argv_split (gfp_t gfp,const char *str,int *argcp);extern void argv_free (char **argv);
lib/string.c +13 -0
@@ -559,6 +559,19 @@ void *memset(void *s, int c, size_t count)EXPORT_SYMBOL (memset);#endif +/** +* secure_bzero - Call memset to fill a region of memory with zeroes and +* ensure this memset is not removed due to dead store elimination. +* @p: Pointer to the start of the area. +* @n: The size of the area. +*/ +void secure_bzero (void *p,size_t n) +{ +memset (p,0 , n); +ARRAY_PREVENT_DSE (p, n); +} +EXPORT_SYMBOL (secure_bzero); +#ifndef __HAVE_ARCH_MEMCPY/** * memcpy - Copy one area of memory to another
Quoted 4 lines
Every byte in the [p,p+n[ range must be used. If you only use the first byte, via e.g.
asm("" :: "m"(*(char*)p)), then the compiler _will_ skip scrubbing bytes beyond the first. This works with gcc-3.2.3 up to gcc-4.4.3.
You forgot to credit Mikael who did all the hard work figuring this out?
Quoted 6 lines
/*
+ * Dead store elimination (DSE) is an optimization that may remove a write to
+ * a buffer that is not used anymore. UseARRAY_PREVENT_DSEafter a write when
+ * the scrub is required for security reasons.
+ */
+#defineARRAY_PREVENT_DSE(p, n)\
Maybe it's just me, but the name is ugly.
include/linux/compiler-gcc.h line 21
Quoted 2 lines
include/linux/compiler-gcc.h +2
-0+ do { \ + struct __scrub { char c[n]; }; \
Better typeof(*p)[n]
include/linux/compiler-intel.h line 21
Quoted 10 lines
+++
b/include/linux/compiler-intel.hinclude/linux/compiler-intel.h +2
-0@@ -14,9 +14,11 @@* It uses intrinsics to do the equivalent things. */ #undef barrier +#undef ARRAY_PREVENT_DSE#undef RELOC_HIDE#define barrier () __memory_barrier() +#define ARRAY_PREVENT_DSE (p, n)
Who says the Intel compiler doesn't need this?
I'm sure it does dead store elimination too and it understands gcc asm syntax.
lib/string.c void *memset(void *s, int c, size_t count) · line 571
Quoted 10 lines
lib/string.c +10
-0+/** +* secure_bzero - Call memset to fill a region of memory with zeroes and +* ensure this memset is not removed due to dead store elimination. +* @p: Pointer to the start of the area. +* @n: The size of the area. +*/ +void secure_bzero (void *p,size_t n) +{ +memset (p,0 , n); +ARRAY_PREVENT_DSE (p, n);
I think that's a candidate for a inline
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only.
PATCH v2 1/1 compiler: prevent dead store elimination
Due to optimization A call to memset() may be removed as a dead store when the buffer is not used after its value is overwritten. The new function secure_bzero() ensures a section of memory is padded with zeroes.
Quoted 1 line
From the GCC manual, section 5.37:
If your assembler instructions access memory in an unpredictable fashion, add `memory' to the list of clobbered registers. This will cause GCC to not keep memory values cached in registers across the assembler instruction and not optimize stores or loads to that memory.
Every byte in the [p,p+n[ range must be used. If you only use the first byte, via e.g. asm("" :: "m"(*(char*)p)), then the compiler _will_ skip scrubbing bytes beyond the first. This works with gcc-3.2.3 up to gcc-4.4.3.
Thanks to Mikael Pettersson for this information.
---
Quoted 1 line
You forgot to credit Mikael
Not intended, I first put it in the changelog but then decided to thank all involved in my comments. Do credits belong in the changelog?
Quoted 3 lines
Quoted 1 line
+#define
ARRAY_PREVENT_DSE(p, n)\Maybe it's just me, but the name is ugly.
Ok, changed it to ARRAY_KEEP_STORE() or do you have a suggestion?
Quoted 4 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ do { \ + struct __scrub { char c[n]; }; \Better typeof(*p)[n]
I guess you meant `struct __scrub { typeof(*p) c[n]; };' ?
In the current implementation p is a void pointer. Is it ok to declare an array of voids? In kernel it compiles, in my testcase it produces an error.
Quoted 5 lines
Quoted 3 lines
+++
b/include/linux/compiler-intel.h+#define
ARRAY_PREVENT_DSE(p, n)Who says the Intel compiler doesn't need this?
There was a comment in include/linux/compiler-intel.h that it's not supported.
Quoted 2 lines
I'm sure it does dead store elimination too and it understands gcc asm syntax.
Ok, should I put it in include/linux/compiler.h or where?
Quoted 6 lines
Review
Quoted 4 lines
(quoted diff) +4
-0+void secure_bzero(void *p, size_t n) +{ + memset(p, 0, n); + ARRAY_PREVENT_DSE(p, n);I think that's a candidate for a inline
You mean the secure_bzero() function, right?
Thanks for comments, Roel
include/linux/compiler.h | 11 +++++++++++ include/linux/string.h | 1 + lib/string.c | 13 +++++++++++++ 3 files changed, 25 insertions(+), 0 deletions(-)
include/linux/compiler.h +11 -0
@@ -302,4 +302,15 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);*/ #define ACCESS_ONCE (x) (*(volatile typeof(x) *)&(x)) +/* +* Dead store elimination is an optimization that may remove a write to a +* buffer that is not used anymore. Use ARRAY_KEEP_STORE after a write when +* the scrub is required for security reasons. +*/ +#define ARRAY_KEEP_STORE (p, n) \ + do { \ + struct __scrub { typeof(*p) c[n]; }; \ + asm("" : : "m"(*(struct __scrub *)p)); \ + } while (0) +#endif /* __LINUX_COMPILER_H */
include/linux/string.h +1 -0
@@ -118,6 +118,7 @@ extern void * memchr(const void *,int,__kernel_size_t);extern char *kstrdup (const char *s,gfp_t gfp);extern char *kstrndup (const char *s,size_t len,gfp_t gfp);extern void *kmemdup (const void *src,size_t len,gfp_t gfp); +extern void secure_bzero (void *,__kernel_size_t );extern char **argv_split (gfp_t gfp,const char *str,int *argcp);extern void argv_free (char **argv);
lib/string.c +13 -0
@@ -559,6 +559,19 @@ void *memset(void *s, int c, size_t count)EXPORT_SYMBOL (memset);#endif +/** +* secure_bzero - Call memset to fill a region of memory with zeroes and +* ensure this memset is not removed due to dead store elimination. +* @p: Pointer to the start of the area. +* @n: The size of the area. +*/ +inline void secure_bzero (void *p,size_t n) +{ +memset (p,0 , n); +ARRAY_KEEP_STORE (p, n); +} +EXPORT_SYMBOL (secure_bzero); +#ifndef __HAVE_ARCH_MEMCPY/** * memcpy - Copy one area of memory to another
Quoted 1 line · Roel Kluin
Due to optimization A call to
memset()may be removed as a dead store when
_______________________^ lower-case a
Quoted 8 lines
the buffer is not used after its value is overwritten. The new function
secure_bzero()ensures a section of memory is padded with zeroes.Quoted 1 line
From the GCC manual, section 5.37:
If your assembler instructions access memory in an unpredictable fashion, add `memory' to the list of clobbered registers. This will cause GCC to not keep memory values cached in registers across the assembler instruction and not optimize stores or loads to that memory.
This paragraph, while accurate, is unrelated to the contents of this patch. Note that in an asm(), a "memory" clobber (see barrier()) is not at all the same thing as a memory operand "m"(...), which is what we're using here. Just drop this bit.
Quoted 3 lines
Every byte in the [p,p+n[ range must be used. If you only use the first byte, via e.g.
asm("" :: "m"(*(char*)p)), then the compiler _will_ skip scrubbing bytes beyond the first.
and then
Quoted 2 lines
This works with
gcc-3.2.3 up to gcc-4.4.3.
You've edited my comments and put them together in a way that doesn't quite make sense. In particular, "This works" doesn't refer to the previous text but the local-struct-of-variable-size trick. The text should read something like:
To prevent a memset() from being eliminated, the compiler must belive that the memory area is used after the memset(). Also, every byte in the memory area must be used. If only the first byte is used, via e.g. asm("" :: "m"(*(char*)p)), then the compiler _will_ skip scrubbing bytes beyond the first.
The trick is to define a local type of the same size as the memory area, and use it for the "m" operand in a dummy asm():
static inline void fake_memory_use(void *p, size_t n)
{
struct __scrub { char c[n]; }
asm("" : : "m"(*(struct __scrub *)p));
}This looks strange, n being a variable, but has been confirmed to work with gcc-3.2.3 up to gcc-4.4.3.
Quoted 5 lines
include/linux/compiler.h +0
-0
include/linux/compiler.h void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect); · line 310
Quoted 9 lines
include/linux/compiler.h +6
-0@@ -302,4 +302,15 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);*/ #define ACCESS_ONCE (x) (*(volatile typeof(x) *)&(x)) +/* +* Dead store elimination is an optimization that may remove a write to a +* buffer that is not used anymore. Use ARRAY_KEEP_STORE after a write when +* the scrub is required for security reasons. +*/ +#define ARRAY_KEEP_STORE (p, n) \
1. This doesn't need to be a macro. Please make it a static inline function.
2. Its function is to "fake" a use of a memory area, which allows us to prevent unwanted DSE elsewhere. So this should be fake_memory_use() or something.
include/linux/compiler.h void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect); · line 312
Quoted 2 lines
include/linux/compiler.h +2
-0+ do { \ + struct __scrub { typeof(*p) c[n]; }; \
The typeof(*p) suggestion doesn't work. It would require p to always be a pointer type with an accurate (for memset) sizeof(*p). In general however we'll memset some array described by a void*/size_t pair, and typeof in that case is useless. The original'struct __scrub { char c[n]; };' was Ok.
include/linux/compiler.h void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);
Quoted 3 lines
include/linux/compiler.h +1
-0extern char *kstrndup (const char *s,size_t len,gfp_t gfp);extern void *kmemdup (const void *src,size_t len,gfp_t gfp); +extern void secure_bzero (void *,__kernel_size_t );
Why is this __kernel_size_t and not just plain size_t? It's not a user-space API.
Quoted 7 lines
include/linux/compiler.h void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect); · line 312
Quoted 2 lines
include/linux/compiler.h +2
-0+ do { \ + struct __scrub { typeof(*p) c[n]; }; \The
typeof(*p)suggestion doesn't work. It would require p to always be a pointer type with an accurate (for memset)sizeof(*p). In general however we'll memset some array described by a void*/size_t pair, and typeof in that case is useless. The original'struct__scrub{ char c[n]; };' was Ok.
I just suggested it because of the original array name of the macro and without it it would have only worked for char arrays. With the new naming it's ok I guess.
It could be made to work with macros and builtin_type_match I guess, but it would be fairly ugly and not worth it.
-Andi
PATCH v3 1/1 compiler: prevent dead store elimination
In reply to Mikael PetterssonDue to optimization a call to memset() may be removed as a dead store when the buffer is not used after its value is overwritten. The new function secure_bzero() ensures a section of memory is padded with zeroes.
To prevent a memset() from being eliminated, the compiler must belive that the memory area is used after the memset(). Also, every byte in the memory area must be used. If only the first byte is used, via e.g. asm("" :: "m"(*(char*)p)), then the compiler _will_ skip scrubbing bytes beyond the first.
The trick is to define a local type of the same size as the memory area, and use it for the "m" operand in a dummy asm():
static inline void fake_memory_use(void *p, size_t n)
{
struct __scrub { char c[n]; }
asm("" : : "m"(*(struct __scrub *)p));
}This looks strange, n being a variable, but has been confirmed to work with gcc-3.2.3 up to gcc-4.4.3.
Many thanks to Mikael Pettersson and Andi Kleen.
---
I used a trick to prevent the assembly for Itanium, defining fake_memory_use in instrinsics.h and checking its definition in string.c, but maybe there's a better way to do this?
To provide a memory clobber for Itanium it appears we could use the pragma directive to set the optimization level [1]. Only when optimization level is greater than 3, dead store removal occurs[2]. But this will be ugly:
inline void secure_bzero(void *p, size_t n)
{
#ifdef _ASM_IA64_INTRINSICS_H
#pragma OPT_LEVEL 2
memset(p, 0, n); #pragma OPT_LEVEL INITIAL #else memset(p, 0, n); fake_memory_use(p, n);
#endif /* _ASM_IA64_INTRINSICS_H */
}
Do we want this?
Thanks, Roel
[1] http://docs.hp.com/en/B3901-90030/ch03s04.html
[2] http://h21007.www2.hp.com/portal/download/files/unprot/Itanium/OptimizingApps-ItaniumV9-1.pdf
(page 6)
arch/ia64/include/asm/intrinsics.h | 3 +++ include/linux/string.h | 1 + lib/string.c | 27 +++++++++++++++++++++++++++ 3 files changed, 31 insertions(+), 0 deletions(-)
arch/ia64/include/asm/intrinsics.h +3 -0
@@ -241,6 +241,9 @@ extern long ia64_cmpxchg_called_with_bad_pointer (void); IA64_INTRINSIC_API(intrin_local_irq_restore)#define ia64_set_rr0_to_rr4 IA64_INTRINSIC_API(set_rr0_to_rr4) +/* FIXME: define fake_memory_use as a memory clobber for Itanium */ +#define fake_memory_use +#endif /* !__ASSEMBLY__ */ #endif /* _ASM_IA64_INTRINSICS_H */
include/linux/string.h +1 -0
@@ -118,6 +118,7 @@ extern void * memchr(const void *,int,__kernel_size_t);extern char *kstrdup (const char *s,gfp_t gfp);extern char *kstrndup (const char *s,size_t len,gfp_t gfp);extern void *kmemdup (const void *src,size_t len,gfp_t gfp); +extern void secure_bzero (void *,size_t );extern char **argv_split (gfp_t gfp,const char *str,int *argcp);extern void argv_free (char **argv);
lib/string.c +27 -0
@@ -559,6 +559,33 @@ void *memset(void *s, int c, size_t count)EXPORT_SYMBOL (memset);#endif +#ifndef fake_memory_use +/* + * Dead store elimination is an optimization that may remove a write to a + * buffer that is not used anymore. To prevent this, e.g. for security + * reasons, the compiler must believe that every byte in this memory area + * is used after the last write. + */ +static inline void fake_memory_use(void *p, size_t n) +{ + struct __scrub { char c[n]; } + asm("" : : "m"(*(struct __scrub *)p)); +} +#endif /* fake_memory_use */ + +/** + * secure_bzero - Call memset to fill a region of memory with zeroes and + * ensure this memset is not removed due to dead store elimination. + * @p: Pointer to the start of the area. + * @n: The size of the area. + */ +inline void secure_bzero(void *p, size_t n) +{ + memset(p, 0, n); + fake_memory_use(p, n); +} +EXPORT_SYMBOL(secure_bzero); + #ifndef __HAVE_ARCH_MEMCPY /** * memcpy - Copy one area of memory to another
Quoted 6 lines
Quoted 4 lines
Quoted 2 lines
+#define
ARRAY_PREVENT_DSE(p, n)Who says the Intel compiler doesn't need this?
There was a comment in
include/linux/compiler-intel.hthat it's not supported.
That's true for the ia64 version, but not for the x86 version which supports gcc compatible inline assembler. So on x86 you can use it. On Itanium it probably would need some other compiler built in.
Also in any case some form of memory clobber is needed because it'll surely do dead-store-optimization.
-Andi
Quoted 31 lines · Andi Kleen
Quoted 4 lines
Every byte in the [p,p+n[ range must be used. If you only use the first byte, via e.g.
asm("" :: "m"(*(char*)p)), then the compiler _will_ skip scrubbing bytes beyond the first. This works with gcc-3.2.3 up to gcc-4.4.3.You forgot to credit Mikael who did all the hard work figuring this out?
Quoted 6 lines
/*
+ * Dead store elimination (DSE) is an optimization that may remove a write to
+ * a buffer that is not used anymore. UseARRAY_PREVENT_DSEafter a write when
+ * the scrub is required for security reasons.
+ */
+#defineARRAY_PREVENT_DSE(p, n)\Maybe it's just me, but the name is ugly.
include/linux/compiler-gcc.h line 21
Quoted 2 lines
include/linux/compiler-gcc.h +2
-0+ do { \ + struct __scrub { char c[n]; }; \Better typeof(*p)[n]
Quoted 8 lines
+++
b/include/linux/compiler-intel.hinclude/linux/compiler-intel.h +1
-0@@ -14,9 +14,11 @@* It uses intrinsics to do the equivalent things. */ #undef barrier +#undef ARRAY_PREVENT_DSE#undef RELOC_HIDE
Quoted 8 lines
include/linux/compiler-intel.h line 21
Quoted 2 lines
include/linux/compiler-intel.h +1
-0#define barrier () __memory_barrier() +#define ARRAY_PREVENT_DSE (p, n)Who says the Intel compiler doesn't need this?
I'm sure it does dead store elimination too and it understands gcc asm syntax.
According to the Intel forum, it not only doesn't, but a request for this as a feature was rejected, so it won't. Or am I misreading this?
http://software.intel.com/en-us/forums/showthread.php?t=46770
Signature · 3 lines
Bill Davidsen <[email protected]> "We have more to fear from the bungling of the incompetent than from the machinations of the wicked." - from Slashdot
lib/string.c void *memset(void *s, int c, size_t count) · line 573
Quoted 6 lines · On Sat, 27 Feb 2010 21:47:42 +0100 Roel Kluin <[email protected]> wrote:
lib/string.c +6
-0+void secure_bzero (void *p,size_t n) +{ +memset (p,0 , n); +ARRAY_PREVENT_DSE (p, n); +} +EXPORT_SYMBOL (secure_bzero);
please don't introduce bzero again to the kernel;
make it secure_memset() please.
Signature · 3 lines
Arjan van de Ven Intel Open Source Technology Centre For development, discussion and tips for power savings, visit http://www.lesswatts.org
Quoted 12 lines · Arjan van de Ven
lib/string.c void *memset(void *s, int c, size_t count) · line 573
Quoted 6 lines · On Sat, 27 Feb 2010 21:47:42 +0100 Roel Kluin <[email protected]> wrote:
lib/string.c +6
-0+void secure_bzero (void *p,size_t n) +{ +memset (p,0 , n); +ARRAY_PREVENT_DSE (p, n); +} +EXPORT_SYMBOL (secure_bzero);please don't introduce bzero again to the kernel;
Quoted 1 line
make it
secure_memset()please.
In principle I would agree, but bzero() avoids the unfortunately rather common mistake of swapping the int/size_t parameters to memset(). I.e., people writing memset(p, n, 0) not memset(p, 0, n).
Quoted 6 lines · Mikael Pettersson
Arjan van de Ven writes:
> On Sat, 27 Feb 2010 21:47:42 +0100
> Roel Kluin <[email protected]> wrote:
> > +voidsecure_bzero(void *p, size_t n)
> > +{
> > + memset(p, 0, n);
Quoted 8 lines
> > + ARRAY_PREVENT_DSE(p, n);
> > +}
> > +EXPORT_SYMBOL(secure_bzero);
>
>
> please don't introduce bzero again to the kernel; >
> make itsecure_memset()please.
What's so secure in this function? :^)
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 12 lines · Arjan van de Ven
lib/string.c void *memset(void *s, int c, size_t count) · line 573
Quoted 6 lines · On Sat, 27 Feb 2010 21:47:42 +0100 Roel Kluin <[email protected]> wrote:
lib/string.c +6
-0+void secure_bzero (void *p,size_t n) +{ +memset (p,0 , n); +ARRAY_PREVENT_DSE (p, n); +} +EXPORT_SYMBOL (secure_bzero);please don't introduce bzero again to the kernel;
Quoted 1 line
make it
secure_memset()please.
Would there ever be any reason to set the key to something else than 0?
IMHO bzero is less error prone. With memset there are regular bugs when the two end arguments get exchanged.
You could call it differently if you have a problem with old BSD names, but inherently there's nothing wrong with them. One possibility would be the same name as VC++ uses.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only.