From patchwork Thu May 26 20:37:10 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Thomas Garnier X-Patchwork-Id: 9137399 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 8D3676075A for ; Thu, 26 May 2016 20:37:56 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7BCA427BFE for ; Thu, 26 May 2016 20:37:56 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7045927D10; Thu, 26 May 2016 20:37:56 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.1 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, RCVD_IN_DNSWL_MED, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from mother.openwall.net (mother.openwall.net [195.42.179.200]) by mail.wl.linuxfoundation.org (Postfix) with SMTP id BF7AE27BFE for ; Thu, 26 May 2016 20:37:54 +0000 (UTC) Received: (qmail 11533 invoked by uid 550); 26 May 2016 20:37:48 -0000 Mailing-List: contact kernel-hardening-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: kernel-hardening@lists.openwall.com Delivered-To: mailing list kernel-hardening@lists.openwall.com Received: (qmail 11469 invoked from network); 26 May 2016 20:37:47 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=79UcjxvPKR8fFLznZE/RJ8kaoS31O1htRacvwZhPIU4=; b=PPgBeUswas2YHpCufyfzTSfPtJxyDiBKBhOoGQ0wKWmyyfS9ZXbUm/3PRQzsh+0NHM AE6xLNAlGBUgFxMcVdnZva0OEFG2DsTBq7LaAnJxvm0hdx8zTQhCam6LPKMAqIYsWu6f ntuIgW13Hmw0K3qNjxZXbHqUVx0rBmkiMQ5nE9OKjFfT6ZDWKsPxr/a9h0pN6TUSZ82Q N5nzrXimFQqxT6fXorjrgk2mXEsZufLWIEA4MgvP9y022drg4cVZfpcsCN+Jo3nzf3gm wPzPGc2D84Qa27Whu733uZL4qquwlo8jfIBdNWlUvFyG5cTsouxz5avDv3QfKu4URh0+ eG4Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=79UcjxvPKR8fFLznZE/RJ8kaoS31O1htRacvwZhPIU4=; b=km4ypZsE+xqjwB2NO0rpQxdrsT+Nj6nwv7OeCupf8q5h0x72PGc0O0ZHuhj9/ACBsd 7+8AVpED78IakEdnBvfLb9GyEEIj9RpYe2PnELn+OMlJkxfazFBXH2wF5REyBsRW9ypc uMnysEbWEtNihSDuO98DpRd1e7AgFwFncrAOmDRh3V6ixwolZMOVawsFZOEd3udr/TH9 2Je1rbnzOXX3q0Nggk8LHFGd1Vo/b3gOlvRYH8nbm4x76pcwTVvJVaSeQvMAM9ulzE05 inYIbiilBdzbfT4pPh5NfV2yLWRDrxcpZlVNDRiFJ+iveGDj5GT4Z0tTA/qAGxI5Csvz CEiA== X-Gm-Message-State: ALyK8tJodJLlJNI20NbIO/7OV5U2Ik38Gx49AvXIJIto9c+zDKYOxc532yG2YfeUBzD1trjT X-Received: by 10.98.67.93 with SMTP id q90mr16876759pfa.100.1464295055353; Thu, 26 May 2016 13:37:35 -0700 (PDT) From: Thomas Garnier To: Christoph Lameter , Pekka Enberg , David Rientjes , Joonsoo Kim , Andrew Morton , "Paul E . McKenney" , Pranith Kumar , David Howells , Tejun Heo , Johannes Weiner , David Woodhouse , Thomas Garnier , Petr Mladek , Kees Cook Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, gthelen@google.com, kernel-hardening@lists.openwall.com Date: Thu, 26 May 2016 13:37:10 -0700 Message-Id: <1464295031-26375-2-git-send-email-thgarnie@google.com> X-Mailer: git-send-email 2.8.0.rc3.226.g39d4020 In-Reply-To: <1464295031-26375-1-git-send-email-thgarnie@google.com> References: <1464295031-26375-1-git-send-email-thgarnie@google.com> Subject: [kernel-hardening] [PATCH v1 1/2] mm: Reorganize SLAB freelist randomization X-Virus-Scanned: ClamAV using ClamSMTP This commit reorganizes the previous SLAB freelist randomization to prepare for the SLUB implementation. It moves functions that will be shared to slab_common. The entropy functions are changed to align with the SLUB implementation, now using get_random_(int|long) functions. These functions were chosen because they provide a bit more entropy early on boot and better performance when specific arch instructions are not available. Signed-off-by: Thomas Garnier Reviewed-by: Kees Cook --- Based on next-20160526 --- include/linux/slab_def.h | 2 +- mm/slab.c | 80 ++++++++++++------------------------------------ mm/slab.h | 14 +++++++++ mm/slab_common.c | 47 ++++++++++++++++++++++++++++ 4 files changed, 82 insertions(+), 61 deletions(-) diff --git a/include/linux/slab_def.h b/include/linux/slab_def.h index 8694f7a..339ba02 100644 --- a/include/linux/slab_def.h +++ b/include/linux/slab_def.h @@ -81,7 +81,7 @@ struct kmem_cache { #endif #ifdef CONFIG_SLAB_FREELIST_RANDOM - void *random_seq; + unsigned int *random_seq; #endif struct kmem_cache_node *node[MAX_NUMNODES]; diff --git a/mm/slab.c b/mm/slab.c index cc8bbc1..763096a 100644 --- a/mm/slab.c +++ b/mm/slab.c @@ -1236,61 +1236,6 @@ static void __init set_up_node(struct kmem_cache *cachep, int index) } } -#ifdef CONFIG_SLAB_FREELIST_RANDOM -static void freelist_randomize(struct rnd_state *state, freelist_idx_t *list, - size_t count) -{ - size_t i; - unsigned int rand; - - for (i = 0; i < count; i++) - list[i] = i; - - /* Fisher-Yates shuffle */ - for (i = count - 1; i > 0; i--) { - rand = prandom_u32_state(state); - rand %= (i + 1); - swap(list[i], list[rand]); - } -} - -/* Create a random sequence per cache */ -static int cache_random_seq_create(struct kmem_cache *cachep, gfp_t gfp) -{ - unsigned int seed, count = cachep->num; - struct rnd_state state; - - if (count < 2) - return 0; - - /* If it fails, we will just use the global lists */ - cachep->random_seq = kcalloc(count, sizeof(freelist_idx_t), gfp); - if (!cachep->random_seq) - return -ENOMEM; - - /* Get best entropy at this stage */ - get_random_bytes_arch(&seed, sizeof(seed)); - prandom_seed_state(&state, seed); - - freelist_randomize(&state, cachep->random_seq, count); - return 0; -} - -/* Destroy the per-cache random freelist sequence */ -static void cache_random_seq_destroy(struct kmem_cache *cachep) -{ - kfree(cachep->random_seq); - cachep->random_seq = NULL; -} -#else -static inline int cache_random_seq_create(struct kmem_cache *cachep, gfp_t gfp) -{ - return 0; -} -static inline void cache_random_seq_destroy(struct kmem_cache *cachep) { } -#endif /* CONFIG_SLAB_FREELIST_RANDOM */ - - /* * Initialisation. Called after the page allocator have been initialised and * before smp_init(). @@ -2535,7 +2480,7 @@ static void cache_init_objs_debug(struct kmem_cache *cachep, struct page *page) union freelist_init_state { struct { unsigned int pos; - freelist_idx_t *list; + unsigned int *list; unsigned int count; unsigned int rand; }; @@ -2554,7 +2499,7 @@ static bool freelist_state_initialize(union freelist_init_state *state, unsigned int rand; /* Use best entropy available to define a random shift */ - get_random_bytes_arch(&rand, sizeof(rand)); + rand = get_random_int(); /* Use a random state if the pre-computed list is not available */ if (!cachep->random_seq) { @@ -2576,13 +2521,20 @@ static freelist_idx_t next_random_slot(union freelist_init_state *state) return (state->list[state->pos++] + state->rand) % state->count; } +/* Swap two freelist entries */ +static void swap_free_obj(struct page *page, unsigned int a, unsigned int b) +{ + swap(((freelist_idx_t *)page->freelist)[a], + ((freelist_idx_t *)page->freelist)[b]); +} + /* * Shuffle the freelist initialization state based on pre-computed lists. * return true if the list was successfully shuffled, false otherwise. */ static bool shuffle_freelist(struct kmem_cache *cachep, struct page *page) { - unsigned int objfreelist = 0, i, count = cachep->num; + unsigned int objfreelist = 0, i, rand, count = cachep->num; union freelist_init_state state; bool precomputed; @@ -2607,7 +2559,15 @@ static bool shuffle_freelist(struct kmem_cache *cachep, struct page *page) * Later use a pre-computed list for speed. */ if (!precomputed) { - freelist_randomize(&state.rnd_state, page->freelist, count); + for (i = 0; i < count; i++) + set_free_obj(page, i, i); + + /* Fisher-Yates shuffle */ + for (i = count - 1; i > 0; i--) { + rand = prandom_u32_state(&state.rnd_state); + rand %= (i + 1); + swap_free_obj(page, i, rand); + } } else { for (i = 0; i < count; i++) set_free_obj(page, i, next_random_slot(&state)); @@ -3979,7 +3939,7 @@ static int enable_cpucache(struct kmem_cache *cachep, gfp_t gfp) int shared = 0; int batchcount = 0; - err = cache_random_seq_create(cachep, gfp); + err = cache_random_seq_create(cachep, cachep->num, gfp); if (err) goto end; diff --git a/mm/slab.h b/mm/slab.h index dedb1a9..5fa8b8f 100644 --- a/mm/slab.h +++ b/mm/slab.h @@ -42,6 +42,7 @@ struct kmem_cache { #include #include #include +#include /* * State of the slab allocator. @@ -464,4 +465,17 @@ int memcg_slab_show(struct seq_file *m, void *p); void ___cache_free(struct kmem_cache *cache, void *x, unsigned long addr); +#ifdef CONFIG_SLAB_FREELIST_RANDOM +int cache_random_seq_create(struct kmem_cache *cachep, unsigned int count, + gfp_t gfp); +void cache_random_seq_destroy(struct kmem_cache *cachep); +#else +static inline int cache_random_seq_create(struct kmem_cache *cachep, + unsigned int count, gfp_t gfp) +{ + return 0; +} +static inline void cache_random_seq_destroy(struct kmem_cache *cachep) { } +#endif /* CONFIG_SLAB_FREELIST_RANDOM */ + #endif /* MM_SLAB_H */ diff --git a/mm/slab_common.c b/mm/slab_common.c index a65dad7..eb1789b 100644 --- a/mm/slab_common.c +++ b/mm/slab_common.c @@ -1142,6 +1142,53 @@ int memcg_slab_show(struct seq_file *m, void *p) } #endif +#ifdef CONFIG_SLAB_FREELIST_RANDOM +/* Randomize a generic freelist */ +static void freelist_randomize(struct rnd_state *state, unsigned int *list, + size_t count) +{ + size_t i; + unsigned int rand; + + for (i = 0; i < count; i++) + list[i] = i; + + /* Fisher-Yates shuffle */ + for (i = count - 1; i > 0; i--) { + rand = prandom_u32_state(state); + rand %= (i + 1); + swap(list[i], list[rand]); + } +} + +/* Create a random sequence per cache */ +int cache_random_seq_create(struct kmem_cache *cachep, unsigned int count, + gfp_t gfp) +{ + struct rnd_state state; + + if (count < 2 || cachep->random_seq) + return 0; + + cachep->random_seq = kcalloc(count, sizeof(unsigned int), gfp); + if (!cachep->random_seq) + return -ENOMEM; + + /* Get best entropy at this stage of boot */ + prandom_seed_state(&state, get_random_long()); + + freelist_randomize(&state, cachep->random_seq, count); + return 0; +} + +/* Destroy the per-cache random freelist sequence */ +void cache_random_seq_destroy(struct kmem_cache *cachep) +{ + kfree(cachep->random_seq); + cachep->random_seq = NULL; +} +#endif /* CONFIG_SLAB_FREELIST_RANDOM */ + /* * slabinfo_op - iterator that generates /proc/slabinfo *