Re: [PATCH v5] mm: SLAB freelist randomization

2016-04-27 Thread Thomas Garnier 
On Wed, Apr 27, 2016 at 12:16 PM, Andrew Morton
 wrote:
> On Wed, 27 Apr 2016 10:20:59 -0700 Thomas Garnier  wrote:
>
>> Provides an optional config (CONFIG_SLAB_FREELIST_RANDOM) to randomize
>> the SLAB freelist.
>
> Forgot this bit?
>

I thought I would change it when we support other kernel heaps.

> From: Andrew Morton 
> Subject: mm-slab-freelist-randomization-v5-fix
>
> propagate gfp_t into cache_random_seq_create()
>
> Cc: Christoph Lameter 
> Cc: David Rientjes 
> Cc: Greg Thelen 
> Cc: Joonsoo Kim 
> Cc: Kees Cook 
> Cc: Laura Abbott 
> Cc: Pekka Enberg 
> Cc: Thomas Garnier 
> Signed-off-by: Andrew Morton 
>
> --- a/mm/slab.c~mm-slab-freelist-randomization-v5-fix
> +++ a/mm/slab.c
> @@ -1262,7 +1262,7 @@ static void freelist_randomize(struct rn
>  }
>
>  /* Create a random sequence per cache */
> -static int cache_random_seq_create(struct kmem_cache *cachep)
> +static int cache_random_seq_create(struct kmem_cache *cachep, gfp_t gfp)
>  {
> unsigned int seed, count = cachep->num;
> struct rnd_state state;
> @@ -1271,7 +1271,7 @@ static int cache_random_seq_create(struc
> return 0;
>
> /* If it fails, we will just use the global lists */
> -   cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), 
> GFP_KERNEL);
> +   cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), gfp);
> if (!cachep->random_seq)
> return -ENOMEM;
>
> @@ -1290,7 +1290,7 @@ static void cache_random_seq_destroy(str
> cachep->random_seq = NULL;
>  }
>  #else
> -static inline int cache_random_seq_create(struct kmem_cache *cachep)
> +static inline int cache_random_seq_create(struct kmem_cache *cachep, gfp_t 
> gfp)
>  {
> return 0;
>  }
> @@ -3999,7 +3999,7 @@ static int enable_cpucache(struct kmem_c
> int shared = 0;
> int batchcount = 0;
>
> -   err = cache_random_seq_create(cachep);
> +   err = cache_random_seq_create(cachep, gfp);
> if (err)
> goto end;
>
> _
>

Re: [PATCH v5] mm: SLAB freelist randomization

2016-04-27 Thread Thomas Garnier 
On Wed, Apr 27, 2016 at 12:16 PM, Andrew Morton
 wrote:
> On Wed, 27 Apr 2016 10:20:59 -0700 Thomas Garnier  wrote:
>
>> Provides an optional config (CONFIG_SLAB_FREELIST_RANDOM) to randomize
>> the SLAB freelist.
>
> Forgot this bit?
>

I thought I would change it when we support other kernel heaps.

> From: Andrew Morton 
> Subject: mm-slab-freelist-randomization-v5-fix
>
> propagate gfp_t into cache_random_seq_create()
>
> Cc: Christoph Lameter 
> Cc: David Rientjes 
> Cc: Greg Thelen 
> Cc: Joonsoo Kim 
> Cc: Kees Cook 
> Cc: Laura Abbott 
> Cc: Pekka Enberg 
> Cc: Thomas Garnier 
> Signed-off-by: Andrew Morton 
>
> --- a/mm/slab.c~mm-slab-freelist-randomization-v5-fix
> +++ a/mm/slab.c
> @@ -1262,7 +1262,7 @@ static void freelist_randomize(struct rn
>  }
>
>  /* Create a random sequence per cache */
> -static int cache_random_seq_create(struct kmem_cache *cachep)
> +static int cache_random_seq_create(struct kmem_cache *cachep, gfp_t gfp)
>  {
> unsigned int seed, count = cachep->num;
> struct rnd_state state;
> @@ -1271,7 +1271,7 @@ static int cache_random_seq_create(struc
> return 0;
>
> /* If it fails, we will just use the global lists */
> -   cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), 
> GFP_KERNEL);
> +   cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), gfp);
> if (!cachep->random_seq)
> return -ENOMEM;
>
> @@ -1290,7 +1290,7 @@ static void cache_random_seq_destroy(str
> cachep->random_seq = NULL;
>  }
>  #else
> -static inline int cache_random_seq_create(struct kmem_cache *cachep)
> +static inline int cache_random_seq_create(struct kmem_cache *cachep, gfp_t 
> gfp)
>  {
> return 0;
>  }
> @@ -3999,7 +3999,7 @@ static int enable_cpucache(struct kmem_c
> int shared = 0;
> int batchcount = 0;
>
> -   err = cache_random_seq_create(cachep);
> +   err = cache_random_seq_create(cachep, gfp);
> if (err)
> goto end;
>
> _
>

Re: [PATCH v5] mm: SLAB freelist randomization

2016-04-27 Thread Andrew Morton 
On Wed, 27 Apr 2016 10:20:59 -0700 Thomas Garnier  wrote:

> Provides an optional config (CONFIG_SLAB_FREELIST_RANDOM) to randomize
> the SLAB freelist.

Forgot this bit?

From: Andrew Morton 
Subject: mm-slab-freelist-randomization-v5-fix

propagate gfp_t into cache_random_seq_create()

Cc: Christoph Lameter 
Cc: David Rientjes 
Cc: Greg Thelen 
Cc: Joonsoo Kim 
Cc: Kees Cook 
Cc: Laura Abbott 
Cc: Pekka Enberg 
Cc: Thomas Garnier 
Signed-off-by: Andrew Morton 

--- a/mm/slab.c~mm-slab-freelist-randomization-v5-fix
+++ a/mm/slab.c
@@ -1262,7 +1262,7 @@ static void freelist_randomize(struct rn
 }
 
 /* Create a random sequence per cache */
-static int cache_random_seq_create(struct kmem_cache *cachep)
+static int cache_random_seq_create(struct kmem_cache *cachep, gfp_t gfp)
 {
unsigned int seed, count = cachep->num;
struct rnd_state state;
@@ -1271,7 +1271,7 @@ static int cache_random_seq_create(struc
return 0;
 
/* If it fails, we will just use the global lists */
-   cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), GFP_KERNEL);
+   cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), gfp);
if (!cachep->random_seq)
return -ENOMEM;
 
@@ -1290,7 +1290,7 @@ static void cache_random_seq_destroy(str
cachep->random_seq = NULL;
 }
 #else
-static inline int cache_random_seq_create(struct kmem_cache *cachep)
+static inline int cache_random_seq_create(struct kmem_cache *cachep, gfp_t gfp)
 {
return 0;
 }
@@ -3999,7 +3999,7 @@ static int enable_cpucache(struct kmem_c
int shared = 0;
int batchcount = 0;
 
-   err = cache_random_seq_create(cachep);
+   err = cache_random_seq_create(cachep, gfp);
if (err)
goto end;
 
_

Re: [PATCH v5] mm: SLAB freelist randomization

2016-04-27 Thread Andrew Morton 
On Wed, 27 Apr 2016 10:20:59 -0700 Thomas Garnier  wrote:

> Provides an optional config (CONFIG_SLAB_FREELIST_RANDOM) to randomize
> the SLAB freelist.

Forgot this bit?

From: Andrew Morton 
Subject: mm-slab-freelist-randomization-v5-fix

propagate gfp_t into cache_random_seq_create()

Cc: Christoph Lameter 
Cc: David Rientjes 
Cc: Greg Thelen 
Cc: Joonsoo Kim 
Cc: Kees Cook 
Cc: Laura Abbott 
Cc: Pekka Enberg 
Cc: Thomas Garnier 
Signed-off-by: Andrew Morton 

--- a/mm/slab.c~mm-slab-freelist-randomization-v5-fix
+++ a/mm/slab.c
@@ -1262,7 +1262,7 @@ static void freelist_randomize(struct rn
 }
 
 /* Create a random sequence per cache */
-static int cache_random_seq_create(struct kmem_cache *cachep)
+static int cache_random_seq_create(struct kmem_cache *cachep, gfp_t gfp)
 {
unsigned int seed, count = cachep->num;
struct rnd_state state;
@@ -1271,7 +1271,7 @@ static int cache_random_seq_create(struc
return 0;
 
/* If it fails, we will just use the global lists */
-   cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), GFP_KERNEL);
+   cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), gfp);
if (!cachep->random_seq)
return -ENOMEM;
 
@@ -1290,7 +1290,7 @@ static void cache_random_seq_destroy(str
cachep->random_seq = NULL;
 }
 #else
-static inline int cache_random_seq_create(struct kmem_cache *cachep)
+static inline int cache_random_seq_create(struct kmem_cache *cachep, gfp_t gfp)
 {
return 0;
 }
@@ -3999,7 +3999,7 @@ static int enable_cpucache(struct kmem_c
int shared = 0;
int batchcount = 0;
 
-   err = cache_random_seq_create(cachep);
+   err = cache_random_seq_create(cachep, gfp);
if (err)
goto end;
 
_

[PATCH v5] mm: SLAB freelist randomization

2016-04-27 Thread Thomas Garnier 
Provides an optional config (CONFIG_SLAB_FREELIST_RANDOM) to randomize
the SLAB freelist. The list is randomized during initialization of a new
set of pages. The order on different freelist sizes is pre-computed at
boot for performance. Each kmem_cache has its own randomized
freelist. Before pre-computed lists are available freelists are
generated dynamically. This security feature reduces the predictability
of the kernel SLAB allocator against heap overflows rendering attacks
much less stable.

For example this attack against SLUB (also applicable against SLAB)
would be affected:
https://jon.oberheide.org/blog/2010/09/10/linux-kernel-can-slub-overflow/

Also, since v4.6 the freelist was moved at the end of the SLAB. It means
a controllable heap is opened to new attacks not yet publicly discussed.
A kernel heap overflow can be transformed to multiple use-after-free.
This feature makes this type of attack harder too.

To generate entropy, we use get_random_bytes_arch because 0 bits of
entropy is available in the boot stage. In the worse case this function
will fallback to the get_random_bytes sub API. We also generate a shift
random number to shift pre-computed freelist for each new set of pages.

The config option name is not specific to the SLAB as this approach will
be extended to other allocators like SLUB.

Performance results highlighted no major changes:

Hackbench (running 90 10 times):

Before average: 0.0698
After average: 0.0663 (-5.01%)

slab_test 1 run on boot. Difference only seen on the 2048 size test
being the worse case scenario covered by freelist randomization. New
slab pages are constantly being created on the 1 allocations.
Variance should be mainly due to getting new pages every few
allocations.

Before:

Single thread testing
=
1. Kmalloc: Repeatedly allocate then free test
1 times kmalloc(8) -> 99 cycles kfree -> 112 cycles
1 times kmalloc(16) -> 109 cycles kfree -> 140 cycles
1 times kmalloc(32) -> 129 cycles kfree -> 137 cycles
1 times kmalloc(64) -> 141 cycles kfree -> 141 cycles
1 times kmalloc(128) -> 152 cycles kfree -> 148 cycles
1 times kmalloc(256) -> 195 cycles kfree -> 167 cycles
1 times kmalloc(512) -> 257 cycles kfree -> 199 cycles
1 times kmalloc(1024) -> 393 cycles kfree -> 251 cycles
1 times kmalloc(2048) -> 649 cycles kfree -> 228 cycles
1 times kmalloc(4096) -> 806 cycles kfree -> 370 cycles
1 times kmalloc(8192) -> 814 cycles kfree -> 411 cycles
1 times kmalloc(16384) -> 892 cycles kfree -> 455 cycles
2. Kmalloc: alloc/free test
1 times kmalloc(8)/kfree -> 121 cycles
1 times kmalloc(16)/kfree -> 121 cycles
1 times kmalloc(32)/kfree -> 121 cycles
1 times kmalloc(64)/kfree -> 121 cycles
1 times kmalloc(128)/kfree -> 121 cycles
1 times kmalloc(256)/kfree -> 119 cycles
1 times kmalloc(512)/kfree -> 119 cycles
1 times kmalloc(1024)/kfree -> 119 cycles
1 times kmalloc(2048)/kfree -> 119 cycles
1 times kmalloc(4096)/kfree -> 121 cycles
1 times kmalloc(8192)/kfree -> 119 cycles
1 times kmalloc(16384)/kfree -> 119 cycles

After:

Single thread testing
=
1. Kmalloc: Repeatedly allocate then free test
1 times kmalloc(8) -> 130 cycles kfree -> 86 cycles
1 times kmalloc(16) -> 118 cycles kfree -> 86 cycles
1 times kmalloc(32) -> 121 cycles kfree -> 85 cycles
1 times kmalloc(64) -> 176 cycles kfree -> 102 cycles
1 times kmalloc(128) -> 178 cycles kfree -> 100 cycles
1 times kmalloc(256) -> 205 cycles kfree -> 109 cycles
1 times kmalloc(512) -> 262 cycles kfree -> 136 cycles
1 times kmalloc(1024) -> 342 cycles kfree -> 157 cycles
1 times kmalloc(2048) -> 701 cycles kfree -> 238 cycles
1 times kmalloc(4096) -> 803 cycles kfree -> 364 cycles
1 times kmalloc(8192) -> 835 cycles kfree -> 404 cycles
1 times kmalloc(16384) -> 896 cycles kfree -> 441 cycles
2. Kmalloc: alloc/free test
1 times kmalloc(8)/kfree -> 121 cycles
1 times kmalloc(16)/kfree -> 121 cycles
1 times kmalloc(32)/kfree -> 123 cycles
1 times kmalloc(64)/kfree -> 142 cycles
1 times kmalloc(128)/kfree -> 121 cycles
1 times kmalloc(256)/kfree -> 119 cycles
1 times kmalloc(512)/kfree -> 119 cycles
1 times kmalloc(1024)/kfree -> 119 cycles
1 times kmalloc(2048)/kfree -> 119 cycles
1 times kmalloc(4096)/kfree -> 119 cycles
1 times kmalloc(8192)/kfree -> 119 cycles
1 times kmalloc(16384)/kfree -> 119 cycles

Signed-off-by: Thomas Garnier 
Acked-by: Christoph Lameter 
---
Based on next-20160422
---
 include/linux/slab_def.h |   4 ++
 init/Kconfig |   9 +++
 mm/slab.c| 167 ++-
 3 files changed, 178 insertions(+), 2 deletions(-)

diff --git a/include/linux/slab_def.h b/include/linux/slab_def.h
index 9edbbf3..8694f7a 100644
--- a/include/linux/slab_def.h
+++ b/include/linux/slab_def.h
@@

[PATCH v5] mm: SLAB freelist randomization

2016-04-27 Thread Thomas Garnier 
Provides an optional config (CONFIG_SLAB_FREELIST_RANDOM) to randomize
the SLAB freelist. The list is randomized during initialization of a new
set of pages. The order on different freelist sizes is pre-computed at
boot for performance. Each kmem_cache has its own randomized
freelist. Before pre-computed lists are available freelists are
generated dynamically. This security feature reduces the predictability
of the kernel SLAB allocator against heap overflows rendering attacks
much less stable.

For example this attack against SLUB (also applicable against SLAB)
would be affected:
https://jon.oberheide.org/blog/2010/09/10/linux-kernel-can-slub-overflow/

Also, since v4.6 the freelist was moved at the end of the SLAB. It means
a controllable heap is opened to new attacks not yet publicly discussed.
A kernel heap overflow can be transformed to multiple use-after-free.
This feature makes this type of attack harder too.

To generate entropy, we use get_random_bytes_arch because 0 bits of
entropy is available in the boot stage. In the worse case this function
will fallback to the get_random_bytes sub API. We also generate a shift
random number to shift pre-computed freelist for each new set of pages.

The config option name is not specific to the SLAB as this approach will
be extended to other allocators like SLUB.

Performance results highlighted no major changes:

Hackbench (running 90 10 times):

Before average: 0.0698
After average: 0.0663 (-5.01%)

slab_test 1 run on boot. Difference only seen on the 2048 size test
being the worse case scenario covered by freelist randomization. New
slab pages are constantly being created on the 1 allocations.
Variance should be mainly due to getting new pages every few
allocations.

Before:

Single thread testing
=
1. Kmalloc: Repeatedly allocate then free test
1 times kmalloc(8) -> 99 cycles kfree -> 112 cycles
1 times kmalloc(16) -> 109 cycles kfree -> 140 cycles
1 times kmalloc(32) -> 129 cycles kfree -> 137 cycles
1 times kmalloc(64) -> 141 cycles kfree -> 141 cycles
1 times kmalloc(128) -> 152 cycles kfree -> 148 cycles
1 times kmalloc(256) -> 195 cycles kfree -> 167 cycles
1 times kmalloc(512) -> 257 cycles kfree -> 199 cycles
1 times kmalloc(1024) -> 393 cycles kfree -> 251 cycles
1 times kmalloc(2048) -> 649 cycles kfree -> 228 cycles
1 times kmalloc(4096) -> 806 cycles kfree -> 370 cycles
1 times kmalloc(8192) -> 814 cycles kfree -> 411 cycles
1 times kmalloc(16384) -> 892 cycles kfree -> 455 cycles
2. Kmalloc: alloc/free test
1 times kmalloc(8)/kfree -> 121 cycles
1 times kmalloc(16)/kfree -> 121 cycles
1 times kmalloc(32)/kfree -> 121 cycles
1 times kmalloc(64)/kfree -> 121 cycles
1 times kmalloc(128)/kfree -> 121 cycles
1 times kmalloc(256)/kfree -> 119 cycles
1 times kmalloc(512)/kfree -> 119 cycles
1 times kmalloc(1024)/kfree -> 119 cycles
1 times kmalloc(2048)/kfree -> 119 cycles
1 times kmalloc(4096)/kfree -> 121 cycles
1 times kmalloc(8192)/kfree -> 119 cycles
1 times kmalloc(16384)/kfree -> 119 cycles

After:

Single thread testing
=
1. Kmalloc: Repeatedly allocate then free test
1 times kmalloc(8) -> 130 cycles kfree -> 86 cycles
1 times kmalloc(16) -> 118 cycles kfree -> 86 cycles
1 times kmalloc(32) -> 121 cycles kfree -> 85 cycles
1 times kmalloc(64) -> 176 cycles kfree -> 102 cycles
1 times kmalloc(128) -> 178 cycles kfree -> 100 cycles
1 times kmalloc(256) -> 205 cycles kfree -> 109 cycles
1 times kmalloc(512) -> 262 cycles kfree -> 136 cycles
1 times kmalloc(1024) -> 342 cycles kfree -> 157 cycles
1 times kmalloc(2048) -> 701 cycles kfree -> 238 cycles
1 times kmalloc(4096) -> 803 cycles kfree -> 364 cycles
1 times kmalloc(8192) -> 835 cycles kfree -> 404 cycles
1 times kmalloc(16384) -> 896 cycles kfree -> 441 cycles
2. Kmalloc: alloc/free test
1 times kmalloc(8)/kfree -> 121 cycles
1 times kmalloc(16)/kfree -> 121 cycles
1 times kmalloc(32)/kfree -> 123 cycles
1 times kmalloc(64)/kfree -> 142 cycles
1 times kmalloc(128)/kfree -> 121 cycles
1 times kmalloc(256)/kfree -> 119 cycles
1 times kmalloc(512)/kfree -> 119 cycles
1 times kmalloc(1024)/kfree -> 119 cycles
1 times kmalloc(2048)/kfree -> 119 cycles
1 times kmalloc(4096)/kfree -> 119 cycles
1 times kmalloc(8192)/kfree -> 119 cycles
1 times kmalloc(16384)/kfree -> 119 cycles

Signed-off-by: Thomas Garnier 
Acked-by: Christoph Lameter 
---
Based on next-20160422
---
 include/linux/slab_def.h |   4 ++
 init/Kconfig |   9 +++
 mm/slab.c| 167 ++-
 3 files changed, 178 insertions(+), 2 deletions(-)

diff --git a/include/linux/slab_def.h b/include/linux/slab_def.h
index 9edbbf3..8694f7a 100644
--- a/include/linux/slab_def.h
+++ b/include/linux/slab_def.h
@@ -80,6 +80,10 @@ struct kmem_cache {