From patchwork Mon Jun 13 15:48:38 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Theodore Ts'o X-Patchwork-Id: 9173515 X-Patchwork-Delegate: herbert@gondor.apana.org.au 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 B01B56075D for ; Mon, 13 Jun 2016 15:52:07 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id A099321C9A for ; Mon, 13 Jun 2016 15:52:07 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 9418A22473; Mon, 13 Jun 2016 15:52:07 +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=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=unavailable version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 26C8D20223 for ; Mon, 13 Jun 2016 15:52:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1424908AbcFMPvG (ORCPT ); Mon, 13 Jun 2016 11:51:06 -0400 Received: from imap.thunk.org ([74.207.234.97]:45054 "EHLO imap.thunk.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1424417AbcFMPt2 (ORCPT ); Mon, 13 Jun 2016 11:49:28 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=thunk.org; s=ef5046eb; h=References:In-Reply-To:Message-Id:Date:Subject:Cc:To:From; bh=ZWESDpuG2TQlED97Ix+/3g+SP4j90QWvUN/+Fp9TnkQ=; b=Nl4TBsbx65BMibEWuepHP11ev1+GAMeA6NuVE4mhjlmYbYqmmxT6x4IU/GYmdB7+zG4sCK5hrN+k8JSqp79rKtBPwOn+igvqSo24krJmh4W2N0yCr+kyQxFLHZM8wlSdU4sb8IAK+IpbVfgKVzagro7dNxWnPTuWMN0YV1vV27w=; Received: from root (helo=closure.thunk.org) by imap.thunk.org with local-esmtp (Exim 4.84_2) (envelope-from ) id 1bCU73-0005b1-Jl; Mon, 13 Jun 2016 15:49:17 +0000 Received: by closure.thunk.org (Postfix, from userid 15806) id 22F6982F5CC; Mon, 13 Jun 2016 11:49:16 -0400 (EDT) From: Theodore Ts'o To: Linux Kernel Developers List Cc: linux-crypto@vger.kernel.org, smueller@chronox.de, herbert@gondor.apana.org.au, andi@firstfloor.org, sandyinchina@gmail.com, jsd@av8n.com, hpa@zytor.com, Theodore Ts'o Subject: [PATCH 6/7] random: make /dev/urandom scalable for silly userspace programs Date: Mon, 13 Jun 2016 11:48:38 -0400 Message-Id: <1465832919-11316-7-git-send-email-tytso@mit.edu> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1465832919-11316-1-git-send-email-tytso@mit.edu> References: <1465832919-11316-1-git-send-email-tytso@mit.edu> X-SA-Exim-Connect-IP: X-SA-Exim-Mail-From: tytso@thunk.org X-SA-Exim-Scanned: No (on imap.thunk.org); SAEximRunCond expanded to false Sender: linux-crypto-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP On a system with a 4 socket (NUMA) system where a large number of application threads were all trying to read from /dev/urandom, this can result in the system spending 80% of its time contending on the global urandom spinlock. The application should have used its own PRNG, but let's try to help it from running, lemming-like, straight over the locking cliff. Reported-by: Andi Kleen Signed-off-by: Theodore Ts'o --- drivers/char/random.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 58 insertions(+), 4 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 841f9a8..d640865 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -434,6 +434,8 @@ struct crng_state primary_crng = { */ static int crng_init = 0; #define crng_ready() (likely(crng_init > 0)) +static void _extract_crng(struct crng_state *crng, + __u8 out[CHACHA20_BLOCK_SIZE]); static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE]); static void process_random_ready_list(void); @@ -754,6 +756,16 @@ static void credit_entropy_bits_safe(struct entropy_store *r, int nbits) static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait); +#ifdef CONFIG_NUMA +/* + * Hack to deal with crazy userspace progams when they are all trying + * to access /dev/urandom in parallel. The programs are almost + * certainly doing something terribly wrong, but we'll work around + * their brain damage. + */ +static struct crng_state **crng_node_pool __read_mostly; +#endif + static void crng_initialize(struct crng_state *crng) { int i; @@ -815,7 +827,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) if (num == 0) return; } else - extract_crng(buf.block); + _extract_crng(&primary_crng, buf.block); spin_lock_irqsave(&primary_crng.lock, flags); for (i = 0; i < 8; i++) { unsigned long rv; @@ -835,19 +847,26 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) spin_unlock_irqrestore(&primary_crng.lock, flags); } +static inline void maybe_reseed_primary_crng(void) +{ + if (crng_init > 2 && + time_after(jiffies, primary_crng.init_time + CRNG_RESEED_INTERVAL)) + crng_reseed(&primary_crng, &input_pool); +} + static inline void crng_wait_ready(void) { wait_event_interruptible(crng_init_wait, crng_ready()); } -static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE]) +static void _extract_crng(struct crng_state *crng, + __u8 out[CHACHA20_BLOCK_SIZE]) { unsigned long v, flags; - struct crng_state *crng = &primary_crng; if (crng_init > 1 && time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)) - crng_reseed(crng, &input_pool); + crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL); spin_lock_irqsave(&crng->lock, flags); if (arch_get_random_long(&v)) crng->state[14] ^= v; @@ -857,6 +876,19 @@ static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE]) spin_unlock_irqrestore(&crng->lock, flags); } +static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE]) +{ + struct crng_state *crng = NULL; + +#ifdef CONFIG_NUMA + if (crng_node_pool) + crng = crng_node_pool[numa_node_id()]; + if (crng == NULL) +#endif + crng = &primary_crng; + _extract_crng(crng, out); +} + static ssize_t extract_crng_user(void __user *buf, size_t nbytes) { ssize_t ret = 0, i; @@ -1575,9 +1607,31 @@ static void init_std_data(struct entropy_store *r) */ static int rand_initialize(void) { +#ifdef CONFIG_NUMA + int i; + int num_nodes = num_possible_nodes(); + struct crng_state *crng; + struct crng_state **pool; +#endif + init_std_data(&input_pool); init_std_data(&blocking_pool); crng_initialize(&primary_crng); + +#ifdef CONFIG_NUMA + pool = kmalloc(num_nodes * sizeof(void *), + GFP_KERNEL|__GFP_NOFAIL|__GFP_ZERO); + for (i=0; i < num_nodes; i++) { + crng = kmalloc_node(sizeof(struct crng_state), + GFP_KERNEL | __GFP_NOFAIL, i); + spin_lock_init(&crng->lock); + crng_initialize(crng); + pool[i] = crng; + + } + mb(); + crng_node_pool = pool; +#endif return 0; } early_initcall(rand_initialize);