[PATCH 1/3] Make /dev/urandom scalable
From: Andi KleenWe had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. For other systems the original nonblocking pool is used until this pool has 128 bits worth of entropy. After that it is used to initialize the other pools. This already gives them different init states, so they don't run in lock-step to avoid "replay" attacks. Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. v2: Fix name of pool 0. Fix race with interrupts. Make iteration loops slightly more efficient. Add ifdefs to avoid any extra code on non-NUMA. Delay other pool use to when the original pool initialized and initialize the pools from pool 0. Add comments on memory allocation. v3: Minor changes from review. Consistent pool names. Signed-off-by: Andi Kleen --- drivers/char/random.c | 187 ++ 1 file changed, 160 insertions(+), 27 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..e7e02c0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool.
[PATCH 1/3] Make /dev/urandom scalable
From: Andi Kleen We had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. For other systems the original nonblocking pool is used until this pool has 128 bits worth of entropy. After that it is used to initialize the other pools. This already gives them different init states, so they don't run in lock-step to avoid "replay" attacks. Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. v2: Fix name of pool 0. Fix race with interrupts. Make iteration loops slightly more efficient. Add ifdefs to avoid any extra code on non-NUMA. Delay other pool use to when the original pool initialized and initialize the pools from pool 0. Add comments on memory allocation. v3: Minor changes from review. Consistent pool names. Signed-off-by: Andi Kleen --- drivers/char/random.c | 187 ++ 1 file changed, 160 insertions(+), 27 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..e7e02c0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool. Each user then only reads entropy from
[PATCH 1/3] Make /dev/urandom scalable
From: Andi Kleen We had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. For other systems the original nonblocking pool is used until this pool has 128 bits worth of entropy. After that it is used to initialize the other pools. This already gives them different init states, so they don't run in lock-step to avoid "replay" attacks. Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. v2: Fix name of pool 0. Fix race with interrupts. Make iteration loops slightly more efficient. Add ifdefs to avoid any extra code on non-NUMA. Delay other pool use to when the original pool initialized and initialize the pools from pool 0. Add comments on memory allocation. v3: Minor changes from review. Consistent pool names. Signed-off-by: Andi Kleen --- drivers/char/random.c | 187 ++ 1 file changed, 160 insertions(+), 27 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..e7e02c0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool. Each user then only reads entropy from
[PATCH 1/3] Make /dev/urandom scalable
From: Andi KleenWe had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. For other systems the original nonblocking pool is used until this pool has 128 bits worth of entropy. After that it is used to initialize the other pools. This already gives them different init states, so they don't run in lock-step to avoid "replay" attacks. Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. v2: Fix name of pool 0. Fix race with interrupts. Make iteration loops slightly more efficient. Add ifdefs to avoid any extra code on non-NUMA. Delay other pool use to when the original pool initialized and initialize the pools from pool 0. Add comments on memory allocation. v3: Minor changes from review. Consistent pool names. Signed-off-by: Andi Kleen --- drivers/char/random.c | 187 ++ 1 file changed, 160 insertions(+), 27 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..e7e02c0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool.
[PATCH 1/3] Make /dev/urandom scalable
From: Andi Kleen We had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. For other systems the original nonblocking pool is used until this pool has 128 bits worth of entropy. After that it is used to initialize the other pools. This already gives them different init states, so they don't run in lock-step to avoid "replay" attacks. Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. v2: Fix name of pool 0. Fix race with interrupts. Make iteration loops slightly more efficient. Add ifdefs to avoid any extra code on non-NUMA. Delay other pool use to when the original pool initialized and initialize the pools from pool 0. Add comments on memory allocation. v3: Minor changes from review. Consistent pool names. Signed-off-by: Andi Kleen --- drivers/char/random.c | 187 ++ 1 file changed, 160 insertions(+), 27 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..e7e02c0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool. Each user then only reads entropy from
[PATCH 1/3] Make /dev/urandom scalable
From: Andi KleenWe had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. For other systems the original nonblocking pool is used until this pool has 128 bits worth of entropy. After that it is used to initialize the other pools. This already gives them different init states, so they don't run in lock-step to avoid "replay" attacks. Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. v2: Fix name of pool 0. Fix race with interrupts. Make iteration loops slightly more efficient. Add ifdefs to avoid any extra code on non-NUMA. Delay other pool use to when the original pool initialized and initialize the pools from pool 0. Add comments on memory allocation. v3: Minor changes from review. Consistent pool names. Signed-off-by: Andi Kleen --- drivers/char/random.c | 187 ++ 1 file changed, 160 insertions(+), 27 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..e7e02c0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool.
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24 2015, Andi Kleen wrote: > > v2: Fix name of pool 0. Fix race with interrupts. Make > iteration loops slightly more efficient. Add ifdefs to avoid > any extra code on non-NUMA. Delay other pool use to when > the original pool initialized and initialize the pools from > pool 0. Add comments on memory allocation. More bikeshedding. Please ignore unless you do a v3 anyway. > static struct entropy_store nonblocking_pool = { > .poolinfo = _table[1], > - .name = "nonblocking", > + .name = "nonblocking pool 0", Hm, yeah, but then you should probably also update the blocking pool's name (or use the format "nonblocking %d"). > +#define POOL_INIT_BYTES (128 / 8) > + > +void init_node_pools(void) > +{ > +#ifdef CONFIG_NUMA > + int i; > + for (i = 0; i < num_possible_nodes(); i++) { int num_nodes = num_possible_nodes(); for (i = 0; i < num_nodes; i++) { > static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) > { > + int i; > int size, ent_count; > int __user *p = (int __user *)arg; > int retval; > + struct entropy_store *pool; > > switch (cmd) { > case RNDGETENTCNT: > @@ -1569,6 +1696,10 @@ static long random_ioctl(struct file *f, unsigned int > cmd, unsigned long arg) > return -EPERM; > input_pool.entropy_count = 0; > nonblocking_pool.entropy_count = 0; > + if (nonblocking_node_pool) > + for_each_nb_pool (i, pool) { > + pool->entropy_count = 0; > + } end_for_each_nb(); extra ;. harmless in this case, but could cause slightly hard-to-understand build failures if that if grows an else. Rasmus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24 2015, Andi Kleenwrote: > > v2: Fix name of pool 0. Fix race with interrupts. Make > iteration loops slightly more efficient. Add ifdefs to avoid > any extra code on non-NUMA. Delay other pool use to when > the original pool initialized and initialize the pools from > pool 0. Add comments on memory allocation. More bikeshedding. Please ignore unless you do a v3 anyway. > static struct entropy_store nonblocking_pool = { > .poolinfo = _table[1], > - .name = "nonblocking", > + .name = "nonblocking pool 0", Hm, yeah, but then you should probably also update the blocking pool's name (or use the format "nonblocking %d"). > +#define POOL_INIT_BYTES (128 / 8) > + > +void init_node_pools(void) > +{ > +#ifdef CONFIG_NUMA > + int i; > + for (i = 0; i < num_possible_nodes(); i++) { int num_nodes = num_possible_nodes(); for (i = 0; i < num_nodes; i++) { > static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) > { > + int i; > int size, ent_count; > int __user *p = (int __user *)arg; > int retval; > + struct entropy_store *pool; > > switch (cmd) { > case RNDGETENTCNT: > @@ -1569,6 +1696,10 @@ static long random_ioctl(struct file *f, unsigned int > cmd, unsigned long arg) > return -EPERM; > input_pool.entropy_count = 0; > nonblocking_pool.entropy_count = 0; > + if (nonblocking_node_pool) > + for_each_nb_pool (i, pool) { > + pool->entropy_count = 0; > + } end_for_each_nb(); extra ;. harmless in this case, but could cause slightly hard-to-understand build failures if that if grows an else. Rasmus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-25 16:24, Theodore Ts'o wrote: On Fri, Sep 25, 2015 at 03:07:54PM -0400, Austin S Hemmelgarn wrote: Interestingly, based on what dieharder is already saying about performance, /dev/urandom is slower than AES_OFB (at least, on this particular system, happy to provide hardware specs if someone wants). Yeah, not surprised by that. We're currently using a crypto hash instead of AES, which means we're not doing any kind of hardware acceleration. Crazy applications that want to spend 100% of the CPU generating random numbers instead of you know, doing _useful_ work notwithstanding, /dev/urandom never had high performance as one of its design goals. The assumption was that if you needed that kind of performance, you would use a user-space cryptographic random number generator. While I do understand that, it's abysmal performance compared to any of the others I tested. Part of the standard testing in dieharder is reporting how many random numbers it can source from the generator per second (it's some bit-width of integers, I just don't remember which). Here's the actual numbers I got: AES_OFB| 1.11e+07 random-glibc2| 6.11e+07 mt19937| 3.30e+07 /dev/urandom| 6.53e+05 That much difference in speed is kind of interesting, and reinforces my statement that you should just use /dev/urandom for seeding other RNG's, just for a different reason than my original statement. smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-25 15:07, Austin S Hemmelgarn wrote: On 2015-09-25 07:41, Austin S Hemmelgarn wrote: On 2015-09-24 16:14, Theodore Ts'o wrote: On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments (this was almost a decade ago), except that I compiled it from source myself, I do remember it was a 32-bit x86 processor (as that was sadly all I had to run Linux on at the time), and an early 2.6 series kernel (which if I remember correctly was already EOL by the time I was using it). It might have been nice if you had said this from the beginning instead of making an unqualified statement with the assumption that it was applicable to kernels likely to be used today in non-obsolete systems. Otherwise it risks generating a click-bait article on Phoronix that would get people really worried for no good reason... I sincerely apologize about this, I should have been more specific right from the beginning (I need to get better about that when talking to people, I'm so used to dealing with some of my friends who couldn't event tell you the difference between RAM and a hard drive, think a bus is only something you use for transportation, and get confused when I try to properly explain even relatively simple CS and statistics concepts). There was a bug a long, long time ago (which where we weren't doing sufficient locking and if two processes raced reading from /dev/urandom at the same time, it was possible that the two processes would get the same value read out from /dev/urandom). This was fixed a long time ago, though, and in fact the scalability problem which Andi is trying to fix was caused by that extra locking that was added. :-) It's possible that is what you saw. I don't know, since there was no reproduction information to back up your rather startling claim. I don't think this was what I hit, I'm pretty sure I had serialized the dieharder runs. If you can reproduce consistent Dieharder failures, please do let us know with detailed reproduction instructures. Will do. OK, just started a couple of runs in parallel using different generators using the following command line: dieharder -a -m 32 -k 1 -Y 1 -g XXX with one each for: /dev/urandom (502) AES_OFB (205) glibc random() (039) mt19937 (013) The above command line will run all dieharder tests with 12800 psamples, using a higher than default precision, and re-running tests that return WEAK until it gets a PASS or FAIL. Even on the relatively fast (at least, fast for a desktop) system I'm running them on, I expect it will take quite some time to finish (although regardless of that I'm probably not going to be getting back to it until Monday). Interestingly, based on what dieharder is already saying about performance, /dev/urandom is slower than AES_OFB (at least, on this particular system, happy to provide hardware specs if someone wants). Apologies for not replying yesterday like I said I would. I actually didn't get a chance to run the tests to completion as the wifi card in the system I was running the tests on lost it's mind about 55 hours in and I had to cold reboot the system to reset it. I would give the results here, except that I have a feeling that people probably don't want 110kb of data in the e-mail body, and thunderbird is for some reason choking on trying to attach files. In general, the results were pretty typical of a good PRNG, performance differences not withstanding. In other words, don't use /dev/urandom except for seeding other PRNG's, but because of the speed, not the quality. smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-25 15:07, Austin S Hemmelgarn wrote: On 2015-09-25 07:41, Austin S Hemmelgarn wrote: On 2015-09-24 16:14, Theodore Ts'o wrote: On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments (this was almost a decade ago), except that I compiled it from source myself, I do remember it was a 32-bit x86 processor (as that was sadly all I had to run Linux on at the time), and an early 2.6 series kernel (which if I remember correctly was already EOL by the time I was using it). It might have been nice if you had said this from the beginning instead of making an unqualified statement with the assumption that it was applicable to kernels likely to be used today in non-obsolete systems. Otherwise it risks generating a click-bait article on Phoronix that would get people really worried for no good reason... I sincerely apologize about this, I should have been more specific right from the beginning (I need to get better about that when talking to people, I'm so used to dealing with some of my friends who couldn't event tell you the difference between RAM and a hard drive, think a bus is only something you use for transportation, and get confused when I try to properly explain even relatively simple CS and statistics concepts). There was a bug a long, long time ago (which where we weren't doing sufficient locking and if two processes raced reading from /dev/urandom at the same time, it was possible that the two processes would get the same value read out from /dev/urandom). This was fixed a long time ago, though, and in fact the scalability problem which Andi is trying to fix was caused by that extra locking that was added. :-) It's possible that is what you saw. I don't know, since there was no reproduction information to back up your rather startling claim. I don't think this was what I hit, I'm pretty sure I had serialized the dieharder runs. If you can reproduce consistent Dieharder failures, please do let us know with detailed reproduction instructures. Will do. OK, just started a couple of runs in parallel using different generators using the following command line: dieharder -a -m 32 -k 1 -Y 1 -g XXX with one each for: /dev/urandom (502) AES_OFB (205) glibc random() (039) mt19937 (013) The above command line will run all dieharder tests with 12800 psamples, using a higher than default precision, and re-running tests that return WEAK until it gets a PASS or FAIL. Even on the relatively fast (at least, fast for a desktop) system I'm running them on, I expect it will take quite some time to finish (although regardless of that I'm probably not going to be getting back to it until Monday). Interestingly, based on what dieharder is already saying about performance, /dev/urandom is slower than AES_OFB (at least, on this particular system, happy to provide hardware specs if someone wants). Apologies for not replying yesterday like I said I would. I actually didn't get a chance to run the tests to completion as the wifi card in the system I was running the tests on lost it's mind about 55 hours in and I had to cold reboot the system to reset it. I would give the results here, except that I have a feeling that people probably don't want 110kb of data in the e-mail body, and thunderbird is for some reason choking on trying to attach files. In general, the results were pretty typical of a good PRNG, performance differences not withstanding. In other words, don't use /dev/urandom except for seeding other PRNG's, but because of the speed, not the quality. smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-25 16:24, Theodore Ts'o wrote: On Fri, Sep 25, 2015 at 03:07:54PM -0400, Austin S Hemmelgarn wrote: Interestingly, based on what dieharder is already saying about performance, /dev/urandom is slower than AES_OFB (at least, on this particular system, happy to provide hardware specs if someone wants). Yeah, not surprised by that. We're currently using a crypto hash instead of AES, which means we're not doing any kind of hardware acceleration. Crazy applications that want to spend 100% of the CPU generating random numbers instead of you know, doing _useful_ work notwithstanding, /dev/urandom never had high performance as one of its design goals. The assumption was that if you needed that kind of performance, you would use a user-space cryptographic random number generator. While I do understand that, it's abysmal performance compared to any of the others I tested. Part of the standard testing in dieharder is reporting how many random numbers it can source from the generator per second (it's some bit-width of integers, I just don't remember which). Here's the actual numbers I got: AES_OFB| 1.11e+07 random-glibc2| 6.11e+07 mt19937| 3.30e+07 /dev/urandom| 6.53e+05 That much difference in speed is kind of interesting, and reinforces my statement that you should just use /dev/urandom for seeding other RNG's, just for a different reason than my original statement. smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On Fri, Sep 25, 2015 at 03:07:54PM -0400, Austin S Hemmelgarn wrote: > > Interestingly, based on what dieharder is already saying about performance, > /dev/urandom is slower than AES_OFB (at least, on this particular system, > happy to provide hardware specs if someone wants). Yeah, not surprised by that. We're currently using a crypto hash instead of AES, which means we're not doing any kind of hardware acceleration. Crazy applications that want to spend 100% of the CPU generating random numbers instead of you know, doing _useful_ work notwithstanding, /dev/urandom never had high performance as one of its design goals. The assumption was that if you needed that kind of performance, you would use a user-space cryptographic random number generator. - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-25 07:41, Austin S Hemmelgarn wrote: On 2015-09-24 16:14, Theodore Ts'o wrote: On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments (this was almost a decade ago), except that I compiled it from source myself, I do remember it was a 32-bit x86 processor (as that was sadly all I had to run Linux on at the time), and an early 2.6 series kernel (which if I remember correctly was already EOL by the time I was using it). It might have been nice if you had said this from the beginning instead of making an unqualified statement with the assumption that it was applicable to kernels likely to be used today in non-obsolete systems. Otherwise it risks generating a click-bait article on Phoronix that would get people really worried for no good reason... I sincerely apologize about this, I should have been more specific right from the beginning (I need to get better about that when talking to people, I'm so used to dealing with some of my friends who couldn't event tell you the difference between RAM and a hard drive, think a bus is only something you use for transportation, and get confused when I try to properly explain even relatively simple CS and statistics concepts). There was a bug a long, long time ago (which where we weren't doing sufficient locking and if two processes raced reading from /dev/urandom at the same time, it was possible that the two processes would get the same value read out from /dev/urandom). This was fixed a long time ago, though, and in fact the scalability problem which Andi is trying to fix was caused by that extra locking that was added. :-) It's possible that is what you saw. I don't know, since there was no reproduction information to back up your rather startling claim. I don't think this was what I hit, I'm pretty sure I had serialized the dieharder runs. If you can reproduce consistent Dieharder failures, please do let us know with detailed reproduction instructures. Will do. OK, just started a couple of runs in parallel using different generators using the following command line: dieharder -a -m 32 -k 1 -Y 1 -g XXX with one each for: /dev/urandom (502) AES_OFB (205) glibc random() (039) mt19937 (013) The above command line will run all dieharder tests with 12800 psamples, using a higher than default precision, and re-running tests that return WEAK until it gets a PASS or FAIL. Even on the relatively fast (at least, fast for a desktop) system I'm running them on, I expect it will take quite some time to finish (although regardless of that I'm probably not going to be getting back to it until Monday). Interestingly, based on what dieharder is already saying about performance, /dev/urandom is slower than AES_OFB (at least, on this particular system, happy to provide hardware specs if someone wants). smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-24 16:14, Theodore Ts'o wrote: On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments (this was almost a decade ago), except that I compiled it from source myself, I do remember it was a 32-bit x86 processor (as that was sadly all I had to run Linux on at the time), and an early 2.6 series kernel (which if I remember correctly was already EOL by the time I was using it). It might have been nice if you had said this from the beginning instead of making an unqualified statement with the assumption that it was applicable to kernels likely to be used today in non-obsolete systems. Otherwise it risks generating a click-bait article on Phoronix that would get people really worried for no good reason... I sincerely apologize about this, I should have been more specific right from the beginning (I need to get better about that when talking to people, I'm so used to dealing with some of my friends who couldn't event tell you the difference between RAM and a hard drive, think a bus is only something you use for transportation, and get confused when I try to properly explain even relatively simple CS and statistics concepts). There was a bug a long, long time ago (which where we weren't doing sufficient locking and if two processes raced reading from /dev/urandom at the same time, it was possible that the two processes would get the same value read out from /dev/urandom). This was fixed a long time ago, though, and in fact the scalability problem which Andi is trying to fix was caused by that extra locking that was added. :-) It's possible that is what you saw. I don't know, since there was no reproduction information to back up your rather startling claim. I don't think this was what I hit, I'm pretty sure I had serialized the dieharder runs. If you can reproduce consistent Dieharder failures, please do let us know with detailed reproduction instructures. Will do. Many thanks, - Ted smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On Fri, Sep 25, 2015 at 03:07:54PM -0400, Austin S Hemmelgarn wrote: > > Interestingly, based on what dieharder is already saying about performance, > /dev/urandom is slower than AES_OFB (at least, on this particular system, > happy to provide hardware specs if someone wants). Yeah, not surprised by that. We're currently using a crypto hash instead of AES, which means we're not doing any kind of hardware acceleration. Crazy applications that want to spend 100% of the CPU generating random numbers instead of you know, doing _useful_ work notwithstanding, /dev/urandom never had high performance as one of its design goals. The assumption was that if you needed that kind of performance, you would use a user-space cryptographic random number generator. - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-25 07:41, Austin S Hemmelgarn wrote: On 2015-09-24 16:14, Theodore Ts'o wrote: On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments (this was almost a decade ago), except that I compiled it from source myself, I do remember it was a 32-bit x86 processor (as that was sadly all I had to run Linux on at the time), and an early 2.6 series kernel (which if I remember correctly was already EOL by the time I was using it). It might have been nice if you had said this from the beginning instead of making an unqualified statement with the assumption that it was applicable to kernels likely to be used today in non-obsolete systems. Otherwise it risks generating a click-bait article on Phoronix that would get people really worried for no good reason... I sincerely apologize about this, I should have been more specific right from the beginning (I need to get better about that when talking to people, I'm so used to dealing with some of my friends who couldn't event tell you the difference between RAM and a hard drive, think a bus is only something you use for transportation, and get confused when I try to properly explain even relatively simple CS and statistics concepts). There was a bug a long, long time ago (which where we weren't doing sufficient locking and if two processes raced reading from /dev/urandom at the same time, it was possible that the two processes would get the same value read out from /dev/urandom). This was fixed a long time ago, though, and in fact the scalability problem which Andi is trying to fix was caused by that extra locking that was added. :-) It's possible that is what you saw. I don't know, since there was no reproduction information to back up your rather startling claim. I don't think this was what I hit, I'm pretty sure I had serialized the dieharder runs. If you can reproduce consistent Dieharder failures, please do let us know with detailed reproduction instructures. Will do. OK, just started a couple of runs in parallel using different generators using the following command line: dieharder -a -m 32 -k 1 -Y 1 -g XXX with one each for: /dev/urandom (502) AES_OFB (205) glibc random() (039) mt19937 (013) The above command line will run all dieharder tests with 12800 psamples, using a higher than default precision, and re-running tests that return WEAK until it gets a PASS or FAIL. Even on the relatively fast (at least, fast for a desktop) system I'm running them on, I expect it will take quite some time to finish (although regardless of that I'm probably not going to be getting back to it until Monday). Interestingly, based on what dieharder is already saying about performance, /dev/urandom is slower than AES_OFB (at least, on this particular system, happy to provide hardware specs if someone wants). smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-24 16:14, Theodore Ts'o wrote: On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments (this was almost a decade ago), except that I compiled it from source myself, I do remember it was a 32-bit x86 processor (as that was sadly all I had to run Linux on at the time), and an early 2.6 series kernel (which if I remember correctly was already EOL by the time I was using it). It might have been nice if you had said this from the beginning instead of making an unqualified statement with the assumption that it was applicable to kernels likely to be used today in non-obsolete systems. Otherwise it risks generating a click-bait article on Phoronix that would get people really worried for no good reason... I sincerely apologize about this, I should have been more specific right from the beginning (I need to get better about that when talking to people, I'm so used to dealing with some of my friends who couldn't event tell you the difference between RAM and a hard drive, think a bus is only something you use for transportation, and get confused when I try to properly explain even relatively simple CS and statistics concepts). There was a bug a long, long time ago (which where we weren't doing sufficient locking and if two processes raced reading from /dev/urandom at the same time, it was possible that the two processes would get the same value read out from /dev/urandom). This was fixed a long time ago, though, and in fact the scalability problem which Andi is trying to fix was caused by that extra locking that was added. :-) It's possible that is what you saw. I don't know, since there was no reproduction information to back up your rather startling claim. I don't think this was what I hit, I'm pretty sure I had serialized the dieharder runs. If you can reproduce consistent Dieharder failures, please do let us know with detailed reproduction instructures. Will do. Many thanks, - Ted smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: > >That is a startling result. Please say what architecture, kernel > >version, dieharder version and commandline arguments you are using to > >get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. > > I do not remember what exact dieharder version or command-line arguments > (this was almost a decade ago), except that I compiled it from source > myself, I do remember it was a 32-bit x86 processor (as that was sadly all I > had to run Linux on at the time), and an early 2.6 series kernel (which if I > remember correctly was already EOL by the time I was using it). It might have been nice if you had said this from the beginning instead of making an unqualified statement with the assumption that it was applicable to kernels likely to be used today in non-obsolete systems. Otherwise it risks generating a click-bait article on Phoronix that would get people really worried for no good reason... There was a bug a long, long time ago (which where we weren't doing sufficient locking and if two processes raced reading from /dev/urandom at the same time, it was possible that the two processes would get the same value read out from /dev/urandom). This was fixed a long time ago, though, and in fact the scalability problem which Andi is trying to fix was caused by that extra locking that was added. :-) It's possible that is what you saw. I don't know, since there was no reproduction information to back up your rather startling claim. If you can reproduce consistent Dieharder failures, please do let us know with detailed reproduction instructures. Many thanks, - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: > I will make a point however to run some tests over the weekend on a > current kernel version (4.2.1), with the current dieharder version I > have available (3.31.1). Please report your findings. If urandom is worse than AES_OFB in statistical tests, we need to know about it. I'm an hour into some test-to-failure runs of diehard_count_1s_str on various RNGs -- urandom, AES_OFB, mt19937_1999, and rand48. So far at psamples >=29000 none have failed, so there's no result to report. (test 8 was chosen by mere human pseudorandomness; hey, it finds in <2s that RANDU is a flawed generator) dieharder -d 8 -g 205 -Y 2 -k 2 dieharder -d 8 -g 200 -Y 2 -k 2 dieharder -d 8 -g 14 -Y 2 -k 2 dieharder -d 8 -g 22 -Y 2 -k 2 If the results are other than "both urandom and aes_ofb were running when I had to reboot my laptop", I'll report my results as well. Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-24 12:52, Jeff Epler wrote: On Thu, Sep 24, 2015 at 12:00:44PM -0400, Austin S Hemmelgarn wrote: I've had cases where I've done thousands of dieharder runs, and it failed almost 10% of the time, while stuff like mt19937 fails in otherwise identical tests only about 1-2% of the time That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments (this was almost a decade ago), except that I compiled it from source myself, I do remember it was a 32-bit x86 processor (as that was sadly all I had to run Linux on at the time), and an early 2.6 series kernel (which if I remember correctly was already EOL by the time I was using it). It may haven been impacted by the fact that I did the testing in QEMU, but I would not expect that to affect things that much. It is worth noting that I only saw this happen three times, and and each time it was in a sample of 2000 runs (which has always been the sample size I've used, as that's the point at which I tend to get impatient). I don't tend to do any of that type of testing anymore (at least, not since I started donating spare cycles to various BOINC projects). I will make a point however to run some tests over the weekend on a current kernel version (4.2.1), with the current dieharder version I have available (3.31.1). Since the structure of linux urandom involves taking a cryptographic hash the basic expectation is that it would fail statistical randomness tests at similar rates to e.g., dieharder's AES_OFB (-g 205) even in the absence of any entropy in the kernel pools. So if 10% failures at correct statistical tests can be replicated it is important and needs attention. I did take a few moments to look into this today and got starling failures (p-value 0.) with e.g., dieharder -g 501 -d 10 (and a few other tests) using dieharder 3.31.1 on both debian linux-4.1-rt-amd64 and debian kfreebsd-10-amd64, but this seems to be an upstream bug known at least to debian and redhat, possibly fixed in current Fedora but apparently not in Debian. https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=745742 https://bugzilla.redhat.com/show_bug.cgi?format=multiple=803292 if you have an affected version, these failures are seen only with -g 501, not with -g 200 < /dev/urandom. They are probably also not seen with 32-bit dieharder. diehard_parking_lot| 0| 12000| 100|0.| FAILED diehard_2dsphere| 2| 8000| 100|0.| FAILED diehard_3dsphere| 3| 4000| 100|0.| FAILED diehard_squeeze| 0|10| 100|0.| FAILED diehard_sums| 0| 100| 100|0.| FAILED The diehard_sums test is known and documented to be a flawed test. As far as the other failures, even a top quality RNG should get them sometimes (because a good RNG _should_ spit out long runs of identical bits from time to time, which is why the absolute insanity that is FIPS cryptography standards should not ever be considered when doing anything other than security work (and only considered cautiously even there)). Based on what I've seen with the AES_OFB generator, 'perfect' generators should be getting WEAK results about 1% of the time, and FAILED results about 0.1% of the time (except on diehard_sums). A generator never getting FAILED or WEAK results over thousands of runs should be an indication that either that generator is flawed in some way (ie, it's actively trying to produce numbers that pass the tests, means it's not really a RNG), or the test itself is flawed in some way. smime.p7s Description: S/MIME Cryptographic Signature
[PATCH 1/3] Make /dev/urandom scalable
From: Andi Kleen We had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. For other systems the original nonblocking pool is used until this pool has 128 bits worth of entropy. After that it is used to initialize the other pools. This already gives them different init states, so they don't run in lock-step to avoid "replay" attacks. Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. v2: Fix name of pool 0. Fix race with interrupts. Make iteration loops slightly more efficient. Add ifdefs to avoid any extra code on non-NUMA. Delay other pool use to when the original pool initialized and initialize the pools from pool 0. Add comments on memory allocation. Signed-off-by: Andi Kleen --- drivers/char/random.c | 185 ++ 1 file changed, 158 insertions(+), 27 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..333a70c 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool. Each user then only reads entropy from their local + * pool. + * + * For the blocking pool there
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24, 2015 at 12:00:44PM -0400, Austin S Hemmelgarn wrote: > I've had cases where I've done thousands of dieharder runs, and it > failed almost 10% of the time, while stuff like mt19937 fails in > otherwise identical tests only about 1-2% of the time That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. Since the structure of linux urandom involves taking a cryptographic hash the basic expectation is that it would fail statistical randomness tests at similar rates to e.g., dieharder's AES_OFB (-g 205) even in the absence of any entropy in the kernel pools. So if 10% failures at correct statistical tests can be replicated it is important and needs attention. I did take a few moments to look into this today and got starling failures (p-value 0.) with e.g., dieharder -g 501 -d 10 (and a few other tests) using dieharder 3.31.1 on both debian linux-4.1-rt-amd64 and debian kfreebsd-10-amd64, but this seems to be an upstream bug known at least to debian and redhat, possibly fixed in current Fedora but apparently not in Debian. https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=745742 https://bugzilla.redhat.com/show_bug.cgi?format=multiple=803292 if you have an affected version, these failures are seen only with -g 501, not with -g 200 < /dev/urandom. They are probably also not seen with 32-bit dieharder. diehard_parking_lot| 0| 12000| 100|0.| FAILED diehard_2dsphere| 2| 8000| 100|0.| FAILED diehard_3dsphere| 3| 4000| 100|0.| FAILED diehard_squeeze| 0|10| 100|0.| FAILED diehard_sums| 0| 100| 100|0.| FAILED Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-24 09:12, Theodore Ts'o wrote: On Thu, Sep 24, 2015 at 07:37:39AM -0400, Austin S Hemmelgarn wrote: Using /dev/urandom directly, yes that doesn't make sense because it consistent returns non-uniformly random numbers when used to generate larger amounts of entropy than the blocking pool can source Why do you think this is the case? Reproduction, please? - Ted Aside from the literature scattered across the web and the fact that it fails Dieharder tests way more than a high quality RNG should (even a good one should fail from time to time, one that never does is inherently flawed for other reasons, but I've had cases where I've done thousands of dieharder runs, and it failed almost 10% of the time, while stuff like mt19937 fails in otherwise identical tests only about 1-2% of the time)? I will admit that it is significantly better than any libc implementation of rand() that I've seen, and many other PRNG's (notably including being significantly more random than the FIPS 140 DRBG's), but it does not do as well (usually) as stuff like OpenBSD's /dev/aranedom (which is way more processor intensive as well from what I've seen) or some of the high quality RNG's found in the GSL. And it's also worth noting that this is with regards to systems that are consistently getting significantly less entropy into the blocking pool than is being sourced from the non-blocking pool by userspace (that is greater than a 100 times or so). In short, I would not trust it as a CSPRNG (although I wouldn't trust most things touted as CSPRNG's either), or even for important simulations that need _lots_ of random numbers. I'm not saying that it shouldn't be used for stuff like seeding other PRNG's however (and TBH, I do trust it more for that than I trust stuff like RDSEED or RDRAND). smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24, 2015 at 07:37:39AM -0400, Austin S Hemmelgarn wrote: > Using /dev/urandom directly, yes that doesn't make sense because it > consistent returns non-uniformly random numbers when used to generate larger > amounts of entropy than the blocking pool can source Why do you think this is the case? Reproduction, please? - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-23 19:28, Andi Kleen wrote: I'd almost say that making the partitioning level configurable at build time might be useful. I can see possible value to being able to at least partition down to physical cores (so, shared between HyperThreads on Intel processors, and between Compute Module cores on AMD processors), as that could potentially help people running large numbers of simulations in parallel. I don't like build time size configurations. It doesn't make sense for simulations to use urandom. It may make sense to have some run time tunable, but for now that's too much complexity. So I'll stay with the simpler per node pool for now. Using /dev/urandom directly, yes that doesn't make sense because it consistent returns non-uniformly random numbers when used to generate larger amounts of entropy than the blocking pool can source, but most that use their own PRNG's seed them off of /dev/urandom, and there are cases I've seen of people doing very large numbers (on the order of millions) of short (15 or so minutes run time on decent hardware) simulations that do this. As for a run-time tunable, I agree that that would be better than build-time, and I also agree that it should be done later. The only reason I suggested a build time tunable was that I figured it would be a lot easier to do than run-time. smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-23 19:28, Andi Kleen wrote: I'd almost say that making the partitioning level configurable at build time might be useful. I can see possible value to being able to at least partition down to physical cores (so, shared between HyperThreads on Intel processors, and between Compute Module cores on AMD processors), as that could potentially help people running large numbers of simulations in parallel. I don't like build time size configurations. It doesn't make sense for simulations to use urandom. It may make sense to have some run time tunable, but for now that's too much complexity. So I'll stay with the simpler per node pool for now. Using /dev/urandom directly, yes that doesn't make sense because it consistent returns non-uniformly random numbers when used to generate larger amounts of entropy than the blocking pool can source, but most that use their own PRNG's seed them off of /dev/urandom, and there are cases I've seen of people doing very large numbers (on the order of millions) of short (15 or so minutes run time on decent hardware) simulations that do this. As for a run-time tunable, I agree that that would be better than build-time, and I also agree that it should be done later. The only reason I suggested a build time tunable was that I figured it would be a lot easier to do than run-time. smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24, 2015 at 07:37:39AM -0400, Austin S Hemmelgarn wrote: > Using /dev/urandom directly, yes that doesn't make sense because it > consistent returns non-uniformly random numbers when used to generate larger > amounts of entropy than the blocking pool can source Why do you think this is the case? Reproduction, please? - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-24 09:12, Theodore Ts'o wrote: On Thu, Sep 24, 2015 at 07:37:39AM -0400, Austin S Hemmelgarn wrote: Using /dev/urandom directly, yes that doesn't make sense because it consistent returns non-uniformly random numbers when used to generate larger amounts of entropy than the blocking pool can source Why do you think this is the case? Reproduction, please? - Ted Aside from the literature scattered across the web and the fact that it fails Dieharder tests way more than a high quality RNG should (even a good one should fail from time to time, one that never does is inherently flawed for other reasons, but I've had cases where I've done thousands of dieharder runs, and it failed almost 10% of the time, while stuff like mt19937 fails in otherwise identical tests only about 1-2% of the time)? I will admit that it is significantly better than any libc implementation of rand() that I've seen, and many other PRNG's (notably including being significantly more random than the FIPS 140 DRBG's), but it does not do as well (usually) as stuff like OpenBSD's /dev/aranedom (which is way more processor intensive as well from what I've seen) or some of the high quality RNG's found in the GSL. And it's also worth noting that this is with regards to systems that are consistently getting significantly less entropy into the blocking pool than is being sourced from the non-blocking pool by userspace (that is greater than a 100 times or so). In short, I would not trust it as a CSPRNG (although I wouldn't trust most things touted as CSPRNG's either), or even for important simulations that need _lots_ of random numbers. I'm not saying that it shouldn't be used for stuff like seeding other PRNG's however (and TBH, I do trust it more for that than I trust stuff like RDSEED or RDRAND). smime.p7s Description: S/MIME Cryptographic Signature
[PATCH 1/3] Make /dev/urandom scalable
From: Andi KleenWe had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. For other systems the original nonblocking pool is used until this pool has 128 bits worth of entropy. After that it is used to initialize the other pools. This already gives them different init states, so they don't run in lock-step to avoid "replay" attacks. Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. v2: Fix name of pool 0. Fix race with interrupts. Make iteration loops slightly more efficient. Add ifdefs to avoid any extra code on non-NUMA. Delay other pool use to when the original pool initialized and initialize the pools from pool 0. Add comments on memory allocation. Signed-off-by: Andi Kleen --- drivers/char/random.c | 185 ++ 1 file changed, 158 insertions(+), 27 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..333a70c 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool. Each user then only reads entropy from their local + *
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: > I will make a point however to run some tests over the weekend on a > current kernel version (4.2.1), with the current dieharder version I > have available (3.31.1). Please report your findings. If urandom is worse than AES_OFB in statistical tests, we need to know about it. I'm an hour into some test-to-failure runs of diehard_count_1s_str on various RNGs -- urandom, AES_OFB, mt19937_1999, and rand48. So far at psamples >=29000 none have failed, so there's no result to report. (test 8 was chosen by mere human pseudorandomness; hey, it finds in <2s that RANDU is a flawed generator) dieharder -d 8 -g 205 -Y 2 -k 2 dieharder -d 8 -g 200 -Y 2 -k 2 dieharder -d 8 -g 14 -Y 2 -k 2 dieharder -d 8 -g 22 -Y 2 -k 2 If the results are other than "both urandom and aes_ofb were running when I had to reboot my laptop", I'll report my results as well. Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24, 2015 at 03:11:23PM -0400, Austin S Hemmelgarn wrote: > >That is a startling result. Please say what architecture, kernel > >version, dieharder version and commandline arguments you are using to > >get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. > > I do not remember what exact dieharder version or command-line arguments > (this was almost a decade ago), except that I compiled it from source > myself, I do remember it was a 32-bit x86 processor (as that was sadly all I > had to run Linux on at the time), and an early 2.6 series kernel (which if I > remember correctly was already EOL by the time I was using it). It might have been nice if you had said this from the beginning instead of making an unqualified statement with the assumption that it was applicable to kernels likely to be used today in non-obsolete systems. Otherwise it risks generating a click-bait article on Phoronix that would get people really worried for no good reason... There was a bug a long, long time ago (which where we weren't doing sufficient locking and if two processes raced reading from /dev/urandom at the same time, it was possible that the two processes would get the same value read out from /dev/urandom). This was fixed a long time ago, though, and in fact the scalability problem which Andi is trying to fix was caused by that extra locking that was added. :-) It's possible that is what you saw. I don't know, since there was no reproduction information to back up your rather startling claim. If you can reproduce consistent Dieharder failures, please do let us know with detailed reproduction instructures. Many thanks, - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-24 12:52, Jeff Epler wrote: On Thu, Sep 24, 2015 at 12:00:44PM -0400, Austin S Hemmelgarn wrote: I've had cases where I've done thousands of dieharder runs, and it failed almost 10% of the time, while stuff like mt19937 fails in otherwise identical tests only about 1-2% of the time That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments (this was almost a decade ago), except that I compiled it from source myself, I do remember it was a 32-bit x86 processor (as that was sadly all I had to run Linux on at the time), and an early 2.6 series kernel (which if I remember correctly was already EOL by the time I was using it). It may haven been impacted by the fact that I did the testing in QEMU, but I would not expect that to affect things that much. It is worth noting that I only saw this happen three times, and and each time it was in a sample of 2000 runs (which has always been the sample size I've used, as that's the point at which I tend to get impatient). I don't tend to do any of that type of testing anymore (at least, not since I started donating spare cycles to various BOINC projects). I will make a point however to run some tests over the weekend on a current kernel version (4.2.1), with the current dieharder version I have available (3.31.1). Since the structure of linux urandom involves taking a cryptographic hash the basic expectation is that it would fail statistical randomness tests at similar rates to e.g., dieharder's AES_OFB (-g 205) even in the absence of any entropy in the kernel pools. So if 10% failures at correct statistical tests can be replicated it is important and needs attention. I did take a few moments to look into this today and got starling failures (p-value 0.) with e.g., dieharder -g 501 -d 10 (and a few other tests) using dieharder 3.31.1 on both debian linux-4.1-rt-amd64 and debian kfreebsd-10-amd64, but this seems to be an upstream bug known at least to debian and redhat, possibly fixed in current Fedora but apparently not in Debian. https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=745742 https://bugzilla.redhat.com/show_bug.cgi?format=multiple=803292 if you have an affected version, these failures are seen only with -g 501, not with -g 200 < /dev/urandom. They are probably also not seen with 32-bit dieharder. diehard_parking_lot| 0| 12000| 100|0.| FAILED diehard_2dsphere| 2| 8000| 100|0.| FAILED diehard_3dsphere| 3| 4000| 100|0.| FAILED diehard_squeeze| 0|10| 100|0.| FAILED diehard_sums| 0| 100| 100|0.| FAILED The diehard_sums test is known and documented to be a flawed test. As far as the other failures, even a top quality RNG should get them sometimes (because a good RNG _should_ spit out long runs of identical bits from time to time, which is why the absolute insanity that is FIPS cryptography standards should not ever be considered when doing anything other than security work (and only considered cautiously even there)). Based on what I've seen with the AES_OFB generator, 'perfect' generators should be getting WEAK results about 1% of the time, and FAILED results about 0.1% of the time (except on diehard_sums). A generator never getting FAILED or WEAK results over thousands of runs should be an indication that either that generator is flawed in some way (ie, it's actively trying to produce numbers that pass the tests, means it's not really a RNG), or the test itself is flawed in some way. smime.p7s Description: S/MIME Cryptographic Signature
Re: [PATCH 1/3] Make /dev/urandom scalable
On Thu, Sep 24, 2015 at 12:00:44PM -0400, Austin S Hemmelgarn wrote: > I've had cases where I've done thousands of dieharder runs, and it > failed almost 10% of the time, while stuff like mt19937 fails in > otherwise identical tests only about 1-2% of the time That is a startling result. Please say what architecture, kernel version, dieharder version and commandline arguments you are using to get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. Since the structure of linux urandom involves taking a cryptographic hash the basic expectation is that it would fail statistical randomness tests at similar rates to e.g., dieharder's AES_OFB (-g 205) even in the absence of any entropy in the kernel pools. So if 10% failures at correct statistical tests can be replicated it is important and needs attention. I did take a few moments to look into this today and got starling failures (p-value 0.) with e.g., dieharder -g 501 -d 10 (and a few other tests) using dieharder 3.31.1 on both debian linux-4.1-rt-amd64 and debian kfreebsd-10-amd64, but this seems to be an upstream bug known at least to debian and redhat, possibly fixed in current Fedora but apparently not in Debian. https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=745742 https://bugzilla.redhat.com/show_bug.cgi?format=multiple=803292 if you have an affected version, these failures are seen only with -g 501, not with -g 200 < /dev/urandom. They are probably also not seen with 32-bit dieharder. diehard_parking_lot| 0| 12000| 100|0.| FAILED diehard_2dsphere| 2| 8000| 100|0.| FAILED diehard_3dsphere| 3| 4000| 100|0.| FAILED diehard_squeeze| 0|10| 100|0.| FAILED diehard_sums| 0| 100| 100|0.| FAILED Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
> I'd almost say that making the partitioning level configurable at > build time might be useful. I can see possible value to being able > to at least partition down to physical cores (so, shared between > HyperThreads on Intel processors, and between Compute Module cores > on AMD processors), as that could potentially help people running > large numbers of simulations in parallel. I don't like build time size configurations. It doesn't make sense for simulations to use urandom. It may make sense to have some run time tunable, but for now that's too much complexity. So I'll stay with the simpler per node pool for now. -Andi -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
> > +{ > > + struct entropy_store *pool = _pool; > > + > > + /* > > +* Non node 0 pools may take longer to initialize. Keep using > > +* the boot nonblocking pool while this happens. > > +*/ > > + if (nonblocking_node_pool) > > + pool = nonblocking_node_pool[numa_node_id()]; > > + if (!pool->initialized) > > + pool = _pool; > > + return pool; > > +} > > I assume this can't get called concurrently with rand_initialize > (otherwise pool may be NULL even if nonblocking_node_pool is non-NULL). Yes. I can move the assignment to the global last and add a memory barrier. > > + char name[40]; > > + > > + nonblocking_node_pool = kzalloc(num_nodes * sizeof(void *), > > + GFP_KERNEL|__GFP_NOFAIL); > > + > > Why kzalloc, when you immediately initialize all elements? New uses of > __GFP_NOFAIL seem to be frowned upon. How hard would it be to just fall > back to only using the single statically allocated pool? It's already doing that. > > Does rand_initialize get called before or after other initialization > code updates node_possible_map to reflect the actual possible number of > nodes? If before, won't we be wasting a lot of memory (not to mention > that we then might as well allocate all the nonblocking pools statically > based on MAX_NUMNODES). I'll check. -Andi -- a...@linux.intel.com -- Speaking for myself only. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
> Does that sound reasonable? Sounds good. I can do that. -Andi -- a...@linux.intel.com -- Speaking for myself only -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On Tue, Sep 22, 2015 at 04:16:05PM -0700, Andi Kleen wrote: > > This patch changes the random driver to use distributed per NUMA node > nonblocking pools. The basic structure is not changed: entropy is > first fed into the input pool and later from there distributed > round-robin into the blocking and non blocking pools. This patch extends > this to use an dedicated non blocking pool for each node, and distribute > evenly from the input pool into these distributed pools, in > addition to the blocking pool. > > Then every urandom/getrandom user fetches data from its node local > pool. At boot time when users may be still waiting for the non > blocking pool initialization we use the node 0 non blocking pool, > to avoid the need for different wake up queues. What I would suggest is that we only create the per-NUMA node pools until the original node 0 is marked as initialized (i.e., that it was been initialized with 128 bits of randomness). At that point initialize pools 1..n using the originial non-blocking pool by using get_random_bytes() to fill up the pool. Once all of the pools are initialized, only then set the nonblocking_node_pool variable. In practice, especially for the large server systems, getting 128 bits of randomness to initialize the primary non-blocking pool shouldn't take long. On my laptop, it takes 4 seconds. My concern, though, is that things like initialized ssh host keys happen at boot time, so anything that weakens the random number generator is a bad thing. (In practice, this isn't a problem pre-systemd, but systemd speeds up the boot sequence quickly enough that this is in fact a potential security problem.) We already have the problem that systemd-udevd grabs random numbers before the random pool is initialized: [1.124926] random: systemd-udevd urandom read with 13 bits of entropy available [4.137543] random: nonblocking pool is initialized > The different per-node pools also start with different start > states and diverge more and more over time, as they get > feed different input data. So "replay" attacks are > difficult after some time. The problem is "after some time" happens after public keys get generated, this isn't good for anything other than starving academics publishing papers about weaknesses in the Linux's random number generator. :-) So I'd strongly prefer if we don't weaken the random number generator boot-time initialization story, and the best way to do this is to wait for a single non-blocking pool to be completely initialized, and then use that pool to initialize the rest of the pools. If that means that we don't have the full /dev/urandom scalability during the first few seconds after the system is booted, to my mind that's a fair tradeoff. Does that sound reasonable? > For saving/restoring /dev/urandom, there is currently no mechanism > to access the non local node pool (short of setting task affinity). > This implies that currently the standard init/exit random save/restore > scripts would only save node 0. On restore all pools are updates. > So the entropy of non 0 gets lost over reboot. That seems acceptable > to me for now (fixing this would need a new separate save/restore interface) Yes, that's fine; I'm not really worried about that, since getrandom(2) only provides a guarantee of initialized cryptographic randomness, and that's what we should most care about. - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-22 19:16, Andi Kleen wrote: From: Andi Kleen We had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. The different per-node pools also start with different start states and diverge more and more over time, as they get feed different input data. So "replay" attacks are difficult after some time. I really like this idea, as it both makes getting random numbers on busy servers faster, and makes replay attacks more difficult. Without hardware random number seed support the start states (until enough real entropy is collected) are not very random, but that's not worse than before Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) I agree that this is acceptable, it wouldn't be hard for someone who wants to to just modify the script to set it's own task affinity and loop through the nodes (although that might get confusing with hot-plugged/hot-removed nodes). Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 3.4x 4 nodes: 6x So it's not quite linear scalability, but 6x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. I'd almost say that making the partitioning level configurable at build time might be useful. I can see possible value to being able to at least partition down to physical cores (so, shared between HyperThreads on Intel processors, and between Compute Module cores on AMD processors), as that could potentially help people running large numbers of simulations in parallel. Personally, I'm the type who would be willing to take the performance hit to do it per logical CPU just for the fact that it would make replay attacks more difficult, but I'm probably part of a very small minority in that case. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems.
Re: [PATCH 1/3] Make /dev/urandom scalable
On Wed, Sep 23 2015, Andi Kleen wrote: > @@ -467,7 +478,7 @@ static struct entropy_store blocking_pool = { > > static struct entropy_store nonblocking_pool = { > .poolinfo = _table[1], > - .name = "nonblocking", > + .name = "nonblocking 0", > .pull = _pool, > .lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock), > .pool = nonblocking_pool_data, > @@ -475,6 +486,32 @@ static struct entropy_store nonblocking_pool = { > push_to_pool), > }; > > +/* > + * Per NUMA node nonblocking pool. This avoids lock contention > + * when many processes extract data from /dev/urandom in parallel. > + * /dev/random stays single instance for now. > + */ > +static struct entropy_store **nonblocking_node_pool __read_mostly; > + > +#define for_each_nb_pool(i, pool) for (i = 0; i < num_possible_nodes(); i++) > { \ > + pool = nonblocking_node_pool[i]; > +#define end_for_each_nb() } You can avoid the need for end_for_each_nb (end_for_each_nb_pool?) by writing the condition i < num_possible_nodes() && (pool = nonblocking_node_pool[i], 1) [if you keep it, please be consistent in whether end_for_each_nb() is followed by ; or not, or add do{}while(0) and make the rule that it is]. But more importantly: Won't this generate a function call (ultimately to bitmap_weight) for each iteration, at least for large enough CONFIG_NODES_SHIFT? It's probably not very expensive, but would be nice to avoid. > +static inline struct entropy_store *get_nonblocking_pool(void) > +{ > + struct entropy_store *pool = _pool; > + > + /* > + * Non node 0 pools may take longer to initialize. Keep using > + * the boot nonblocking pool while this happens. > + */ > + if (nonblocking_node_pool) > + pool = nonblocking_node_pool[numa_node_id()]; > + if (!pool->initialized) > + pool = _pool; > + return pool; > +} I assume this can't get called concurrently with rand_initialize (otherwise pool may be NULL even if nonblocking_node_pool is non-NULL). > > @@ -1393,9 +1446,32 @@ static void init_std_data(struct entropy_store *r) > */ > static int rand_initialize(void) > { > + int i; > + int num_nodes = num_possible_nodes(); > + char name[40]; > + > + nonblocking_node_pool = kzalloc(num_nodes * sizeof(void *), > + GFP_KERNEL|__GFP_NOFAIL); > + Why kzalloc, when you immediately initialize all elements? New uses of __GFP_NOFAIL seem to be frowned upon. How hard would it be to just fall back to only using the single statically allocated pool? Does rand_initialize get called before or after other initialization code updates node_possible_map to reflect the actual possible number of nodes? If before, won't we be wasting a lot of memory (not to mention that we then might as well allocate all the nonblocking pools statically based on MAX_NUMNODES). > init_std_data(_pool); > init_std_data(_pool); > + nonblocking_node_pool[0] = _pool; > init_std_data(_pool); > + for (i = 1; i < num_nodes; i++) { > + struct entropy_store *pool = kzalloc(sizeof(struct > entropy_store), > + GFP_KERNEL|__GFP_NOFAIL); > + nonblocking_node_pool[i] = pool; > + pool->poolinfo = _table[1]; > + pool->pull = _pool; > + spin_lock_init(>lock); > + /* pool data not cleared intentionally */ > + pool->pool = kmalloc(sizeof(nonblocking_pool_data), > + GFP_KERNEL|__GFP_NOFAIL); > + INIT_WORK(>push_work, push_to_pool); > + snprintf(name, sizeof name, "nonblocking pool %d", i); > + pool->name = kstrdup(name, GFP_KERNEL|__GFP_NOFAIL); kasprintf(). Also, you renamed the static pool to "nonblocking 0". Rasmus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On Wed, Sep 23 2015, Andi Kleenwrote: > @@ -467,7 +478,7 @@ static struct entropy_store blocking_pool = { > > static struct entropy_store nonblocking_pool = { > .poolinfo = _table[1], > - .name = "nonblocking", > + .name = "nonblocking 0", > .pull = _pool, > .lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock), > .pool = nonblocking_pool_data, > @@ -475,6 +486,32 @@ static struct entropy_store nonblocking_pool = { > push_to_pool), > }; > > +/* > + * Per NUMA node nonblocking pool. This avoids lock contention > + * when many processes extract data from /dev/urandom in parallel. > + * /dev/random stays single instance for now. > + */ > +static struct entropy_store **nonblocking_node_pool __read_mostly; > + > +#define for_each_nb_pool(i, pool) for (i = 0; i < num_possible_nodes(); i++) > { \ > + pool = nonblocking_node_pool[i]; > +#define end_for_each_nb() } You can avoid the need for end_for_each_nb (end_for_each_nb_pool?) by writing the condition i < num_possible_nodes() && (pool = nonblocking_node_pool[i], 1) [if you keep it, please be consistent in whether end_for_each_nb() is followed by ; or not, or add do{}while(0) and make the rule that it is]. But more importantly: Won't this generate a function call (ultimately to bitmap_weight) for each iteration, at least for large enough CONFIG_NODES_SHIFT? It's probably not very expensive, but would be nice to avoid. > +static inline struct entropy_store *get_nonblocking_pool(void) > +{ > + struct entropy_store *pool = _pool; > + > + /* > + * Non node 0 pools may take longer to initialize. Keep using > + * the boot nonblocking pool while this happens. > + */ > + if (nonblocking_node_pool) > + pool = nonblocking_node_pool[numa_node_id()]; > + if (!pool->initialized) > + pool = _pool; > + return pool; > +} I assume this can't get called concurrently with rand_initialize (otherwise pool may be NULL even if nonblocking_node_pool is non-NULL). > > @@ -1393,9 +1446,32 @@ static void init_std_data(struct entropy_store *r) > */ > static int rand_initialize(void) > { > + int i; > + int num_nodes = num_possible_nodes(); > + char name[40]; > + > + nonblocking_node_pool = kzalloc(num_nodes * sizeof(void *), > + GFP_KERNEL|__GFP_NOFAIL); > + Why kzalloc, when you immediately initialize all elements? New uses of __GFP_NOFAIL seem to be frowned upon. How hard would it be to just fall back to only using the single statically allocated pool? Does rand_initialize get called before or after other initialization code updates node_possible_map to reflect the actual possible number of nodes? If before, won't we be wasting a lot of memory (not to mention that we then might as well allocate all the nonblocking pools statically based on MAX_NUMNODES). > init_std_data(_pool); > init_std_data(_pool); > + nonblocking_node_pool[0] = _pool; > init_std_data(_pool); > + for (i = 1; i < num_nodes; i++) { > + struct entropy_store *pool = kzalloc(sizeof(struct > entropy_store), > + GFP_KERNEL|__GFP_NOFAIL); > + nonblocking_node_pool[i] = pool; > + pool->poolinfo = _table[1]; > + pool->pull = _pool; > + spin_lock_init(>lock); > + /* pool data not cleared intentionally */ > + pool->pool = kmalloc(sizeof(nonblocking_pool_data), > + GFP_KERNEL|__GFP_NOFAIL); > + INIT_WORK(>push_work, push_to_pool); > + snprintf(name, sizeof name, "nonblocking pool %d", i); > + pool->name = kstrdup(name, GFP_KERNEL|__GFP_NOFAIL); kasprintf(). Also, you renamed the static pool to "nonblocking 0". Rasmus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On 2015-09-22 19:16, Andi Kleen wrote: From: Andi KleenWe had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. The different per-node pools also start with different start states and diverge more and more over time, as they get feed different input data. So "replay" attacks are difficult after some time. I really like this idea, as it both makes getting random numbers on busy servers faster, and makes replay attacks more difficult. Without hardware random number seed support the start states (until enough real entropy is collected) are not very random, but that's not worse than before Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) I agree that this is acceptable, it wouldn't be hard for someone who wants to to just modify the script to set it's own task affinity and loop through the nodes (although that might get confusing with hot-plugged/hot-removed nodes). Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 3.4x 4 nodes: 6x So it's not quite linear scalability, but 6x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. I'd almost say that making the partitioning level configurable at build time might be useful. I can see possible value to being able to at least partition down to physical cores (so, shared between HyperThreads on Intel processors, and between Compute Module cores on AMD processors), as that could potentially help people running large numbers of simulations in parallel. Personally, I'm the type who would be willing to take the performance hit to do it per logical CPU just for the fact that it would make replay attacks more difficult, but I'm probably part of a very small minority in that case. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on
Re: [PATCH 1/3] Make /dev/urandom scalable
> > +{ > > + struct entropy_store *pool = _pool; > > + > > + /* > > +* Non node 0 pools may take longer to initialize. Keep using > > +* the boot nonblocking pool while this happens. > > +*/ > > + if (nonblocking_node_pool) > > + pool = nonblocking_node_pool[numa_node_id()]; > > + if (!pool->initialized) > > + pool = _pool; > > + return pool; > > +} > > I assume this can't get called concurrently with rand_initialize > (otherwise pool may be NULL even if nonblocking_node_pool is non-NULL). Yes. I can move the assignment to the global last and add a memory barrier. > > + char name[40]; > > + > > + nonblocking_node_pool = kzalloc(num_nodes * sizeof(void *), > > + GFP_KERNEL|__GFP_NOFAIL); > > + > > Why kzalloc, when you immediately initialize all elements? New uses of > __GFP_NOFAIL seem to be frowned upon. How hard would it be to just fall > back to only using the single statically allocated pool? It's already doing that. > > Does rand_initialize get called before or after other initialization > code updates node_possible_map to reflect the actual possible number of > nodes? If before, won't we be wasting a lot of memory (not to mention > that we then might as well allocate all the nonblocking pools statically > based on MAX_NUMNODES). I'll check. -Andi -- a...@linux.intel.com -- Speaking for myself only. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
> Does that sound reasonable? Sounds good. I can do that. -Andi -- a...@linux.intel.com -- Speaking for myself only -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
On Tue, Sep 22, 2015 at 04:16:05PM -0700, Andi Kleen wrote: > > This patch changes the random driver to use distributed per NUMA node > nonblocking pools. The basic structure is not changed: entropy is > first fed into the input pool and later from there distributed > round-robin into the blocking and non blocking pools. This patch extends > this to use an dedicated non blocking pool for each node, and distribute > evenly from the input pool into these distributed pools, in > addition to the blocking pool. > > Then every urandom/getrandom user fetches data from its node local > pool. At boot time when users may be still waiting for the non > blocking pool initialization we use the node 0 non blocking pool, > to avoid the need for different wake up queues. What I would suggest is that we only create the per-NUMA node pools until the original node 0 is marked as initialized (i.e., that it was been initialized with 128 bits of randomness). At that point initialize pools 1..n using the originial non-blocking pool by using get_random_bytes() to fill up the pool. Once all of the pools are initialized, only then set the nonblocking_node_pool variable. In practice, especially for the large server systems, getting 128 bits of randomness to initialize the primary non-blocking pool shouldn't take long. On my laptop, it takes 4 seconds. My concern, though, is that things like initialized ssh host keys happen at boot time, so anything that weakens the random number generator is a bad thing. (In practice, this isn't a problem pre-systemd, but systemd speeds up the boot sequence quickly enough that this is in fact a potential security problem.) We already have the problem that systemd-udevd grabs random numbers before the random pool is initialized: [1.124926] random: systemd-udevd urandom read with 13 bits of entropy available [4.137543] random: nonblocking pool is initialized > The different per-node pools also start with different start > states and diverge more and more over time, as they get > feed different input data. So "replay" attacks are > difficult after some time. The problem is "after some time" happens after public keys get generated, this isn't good for anything other than starving academics publishing papers about weaknesses in the Linux's random number generator. :-) So I'd strongly prefer if we don't weaken the random number generator boot-time initialization story, and the best way to do this is to wait for a single non-blocking pool to be completely initialized, and then use that pool to initialize the rest of the pools. If that means that we don't have the full /dev/urandom scalability during the first few seconds after the system is booted, to my mind that's a fair tradeoff. Does that sound reasonable? > For saving/restoring /dev/urandom, there is currently no mechanism > to access the non local node pool (short of setting task affinity). > This implies that currently the standard init/exit random save/restore > scripts would only save node 0. On restore all pools are updates. > So the entropy of non 0 gets lost over reboot. That seems acceptable > to me for now (fixing this would need a new separate save/restore interface) Yes, that's fine; I'm not really worried about that, since getrandom(2) only provides a guarantee of initialized cryptographic randomness, and that's what we should most care about. - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
> I'd almost say that making the partitioning level configurable at > build time might be useful. I can see possible value to being able > to at least partition down to physical cores (so, shared between > HyperThreads on Intel processors, and between Compute Module cores > on AMD processors), as that could potentially help people running > large numbers of simulations in parallel. I don't like build time size configurations. It doesn't make sense for simulations to use urandom. It may make sense to have some run time tunable, but for now that's too much complexity. So I'll stay with the simpler per node pool for now. -Andi -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/3] Make /dev/urandom scalable
Andi Kleen writes: > > With the patchkit applied: > > 1 node: 1x > 2 nodes: 2x > 3 nodes: 3.4x > 4 nodes: 6x Sorry there was a typo in the numbers. Correct results are: With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. -- a...@linux.intel.com -- Speaking for myself only -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 1/3] Make /dev/urandom scalable
From: Andi Kleen We had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. The different per-node pools also start with different start states and diverge more and more over time, as they get feed different input data. So "replay" attacks are difficult after some time. Without hardware random number seed support the start states (until enough real entropy is collected) are not very random, but that's not worse than before Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 3.4x 4 nodes: 6x So it's not quite linear scalability, but 6x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. Signed-off-by: Andi Kleen --- drivers/char/random.c | 142 -- 1 file changed, 114 insertions(+), 28 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..d0302be 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool. Each user then only reads entropy from their local + * pool. + * + * For the blocking pool there is still only a single instance. + * * Ensuring unpredictability at system startup * * @@ -467,7 +478,7 @@ static struct entropy_store
[PATCH 1/3] Make /dev/urandom scalable
From: Andi KleenWe had a case where a 4 socket system spent >80% of its total CPU time contending on the global urandom nonblocking pool spinlock. While the application could probably have used an own PRNG, it may have valid reasons to use the best possible key for different session keys. The application still ran acceptable under 2S, but just fell over the locking cliff on 4S. Implementation == The non blocking pool is used widely these days, from every execve() (to set up AT_RANDOM for ld.so randomization), to getrandom(3) and to frequent /dev/urandom users in user space. Clearly having such a popular resource under a global lock is bad thing. This patch changes the random driver to use distributed per NUMA node nonblocking pools. The basic structure is not changed: entropy is first fed into the input pool and later from there distributed round-robin into the blocking and non blocking pools. This patch extends this to use an dedicated non blocking pool for each node, and distribute evenly from the input pool into these distributed pools, in addition to the blocking pool. Then every urandom/getrandom user fetches data from its node local pool. At boot time when users may be still waiting for the non blocking pool initialization we use the node 0 non blocking pool, to avoid the need for different wake up queues. For single node systems (like the vast majority of non server systems) nothing changes. There is still only a single non blocking pool. The different per-node pools also start with different start states and diverge more and more over time, as they get feed different input data. So "replay" attacks are difficult after some time. Without hardware random number seed support the start states (until enough real entropy is collected) are not very random, but that's not worse than before Since we still have a global input pool there are no problems with load balancing entropy data between nodes. Any node that never runs any interrupts would still get the same amount of entropy as other nodes. Entropy is fed preferably to nodes that need it more using the existing 75% threshold. For saving/restoring /dev/urandom, there is currently no mechanism to access the non local node pool (short of setting task affinity). This implies that currently the standard init/exit random save/restore scripts would only save node 0. On restore all pools are updates. So the entropy of non 0 gets lost over reboot. That seems acceptable to me for now (fixing this would need a new separate save/restore interface) Scalability === I tested the patch with a simple will-it-scale test banging on get_random() in parallel on more and more CPUs. Of course that is not a realistic scenario, as real programs should do some work between getting random numbers. But it's a worst case for the random scalability. On a 4S Xeon v3 system _without_ the patchkit the benchmark maxes out when using all the threads on one node. After that it quickly settles to about half the throughput of one node with 2-4 nodes. (all throughput factors, bigger is better) Without patchkit: 1 node: 1x 2 nodes: 0.75x 3 nodes: 0.55x 4 nodes: 0.42x With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 3.4x 4 nodes: 6x So it's not quite linear scalability, but 6x maximum throughput is already a lot better. A node can still have a large number of CPUs: on my test system 36 logical software threads (18C * 2T). In principle it may make sense to split it up further. Per logical CPU would be clearly overkill. But that would also add more pressure on the input pools. For now per node seems like a acceptable compromise. /dev/random still uses a single global lock. For now that seems acceptable as it normally cannot be used for real high volume accesses anyways. The input pool also still uses a global lock. The existing per CPU fast pool and "give up when busy" mechanism seems to scale well enough even on larger systems. Signed-off-by: Andi Kleen --- drivers/char/random.c | 142 -- 1 file changed, 114 insertions(+), 28 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d0da5d8..d0302be 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -156,6 +156,17 @@ * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * + * Distributed pools + * = + * + * On larger systems the locking on the single non blocking pool can + * become a bottleneck. To avoid this, we use an own non blocking pool + * for each NUMA node. The distributed pools are fed round robin from + * the input pool. Each user then only reads entropy from their local + * pool. + * + * For the blocking pool there is still only a single instance. + * * Ensuring unpredictability at system startup * * @@
Re: [PATCH 1/3] Make /dev/urandom scalable
Andi Kleenwrites: > > With the patchkit applied: > > 1 node: 1x > 2 nodes: 2x > 3 nodes: 3.4x > 4 nodes: 6x Sorry there was a typo in the numbers. Correct results are: With the patchkit applied: 1 node: 1x 2 nodes: 2x 3 nodes: 2.4x 4 nodes: 3x So it's not quite linear scalability, but 3x maximum throughput is already a lot better. -- a...@linux.intel.com -- Speaking for myself only -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/