* [patch added to 3.12-stable] random32: add prandom_u32_max and convert open coded users
[not found] <20160818124953.31969-1-jslaby@suse.cz>
@ 2016-08-18 12:49 ` Jiri Slaby
2016-08-18 12:49 ` [patch added to 3.12-stable] KEYS: 64-bit MIPS needs to use compat_sys_keyctl for 32-bit userspace Jiri Slaby
1 sibling, 0 replies; 2+ messages in thread
From: Jiri Slaby @ 2016-08-18 12:49 UTC (permalink / raw)
To: stable
Cc: Daniel Borkmann, Jakub Zawadzki, Eric Dumazet, linux-kernel,
Hannes Frederic Sowa, David S . Miller, Jiri Slaby
From: Daniel Borkmann <dborkman@redhat.com>
This patch has been added to the 3.12 stable tree. If you have any
objections, please let us know.
===============
commit f337db64af059c9a94278a8b0ab97d87259ff62f upstream.
Many functions have open coded a function that returns a random
number in range [0,N-1]. Under the assumption that we have a PRNG
such as taus113 with being well distributed in [0, ~0U] space,
we can implement such a function as uword t = (n*m')>>32, where
m' is a random number obtained from PRNG, n the right open interval
border and t our resulting random number, with n,m',t in u32 universe.
Lets go with Joe and simply call it prandom_u32_max(), although
technically we have an right open interval endpoint, but that we
have documented. Other users can further be migrated to the new
prandom_u32_max() function later on; for now, we need to make sure
to migrate reciprocal_divide() users for the reciprocal_divide()
follow-up fixup since their function signatures are going to change.
Joint work with Hannes Frederic Sowa.
Cc: Jakub Zawadzki <darkjames-ws@darkjames.pl>
Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: linux-kernel@vger.kernel.org
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Signed-off-by: Jiri Slaby <jslaby@suse.cz>
---
drivers/net/team/team_mode_random.c | 8 +-------
include/linux/random.h | 18 +++++++++++++++++-
net/packet/af_packet.c | 2 +-
net/sched/sch_choke.c | 9 +--------
4 files changed, 20 insertions(+), 17 deletions(-)
diff --git a/drivers/net/team/team_mode_random.c b/drivers/net/team/team_mode_random.c
index 7f032e211343..cd2f692b8074 100644
--- a/drivers/net/team/team_mode_random.c
+++ b/drivers/net/team/team_mode_random.c
@@ -13,20 +13,14 @@
#include <linux/module.h>
#include <linux/init.h>
#include <linux/skbuff.h>
-#include <linux/reciprocal_div.h>
#include <linux/if_team.h>
-static u32 random_N(unsigned int N)
-{
- return reciprocal_divide(prandom_u32(), N);
-}
-
static bool rnd_transmit(struct team *team, struct sk_buff *skb)
{
struct team_port *port;
int port_index;
- port_index = random_N(team->en_port_count);
+ port_index = prandom_u32_max(team->en_port_count);
port = team_get_port_by_index_rcu(team, port_index);
if (unlikely(!port))
goto drop;
diff --git a/include/linux/random.h b/include/linux/random.h
index bf9085e89fb5..230040642bea 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -8,7 +8,6 @@
#include <uapi/linux/random.h>
-
extern void add_device_randomness(const void *, unsigned int);
extern void add_input_randomness(unsigned int type, unsigned int code,
unsigned int value);
@@ -33,6 +32,23 @@ void prandom_seed(u32 seed);
u32 prandom_u32_state(struct rnd_state *);
void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes);
+/**
+ * prandom_u32_max - returns a pseudo-random number in interval [0, ep_ro)
+ * @ep_ro: right open interval endpoint
+ *
+ * Returns a pseudo-random number that is in interval [0, ep_ro). Note
+ * that the result depends on PRNG being well distributed in [0, ~0U]
+ * u32 space. Here we use maximally equidistributed combined Tausworthe
+ * generator, that is, prandom_u32(). This is useful when requesting a
+ * random index of an array containing ep_ro elements, for example.
+ *
+ * Returns: pseudo-random number in interval [0, ep_ro)
+ */
+static inline u32 prandom_u32_max(u32 ep_ro)
+{
+ return (u32)(((u64) prandom_u32() * ep_ro) >> 32);
+}
+
/*
* Handle minimum values for seeds
*/
diff --git a/net/packet/af_packet.c b/net/packet/af_packet.c
index 63d0f92f45d0..1e9cb9921daa 100644
--- a/net/packet/af_packet.c
+++ b/net/packet/af_packet.c
@@ -1178,7 +1178,7 @@ static unsigned int fanout_demux_rnd(struct packet_fanout *f,
struct sk_buff *skb,
unsigned int num)
{
- return reciprocal_divide(prandom_u32(), num);
+ return prandom_u32_max(num);
}
static unsigned int fanout_demux_rollover(struct packet_fanout *f,
diff --git a/net/sched/sch_choke.c b/net/sched/sch_choke.c
index ddd73cb2d7ba..2aee02802c27 100644
--- a/net/sched/sch_choke.c
+++ b/net/sched/sch_choke.c
@@ -14,7 +14,6 @@
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/skbuff.h>
-#include <linux/reciprocal_div.h>
#include <linux/vmalloc.h>
#include <net/pkt_sched.h>
#include <net/inet_ecn.h>
@@ -77,12 +76,6 @@ struct choke_sched_data {
struct sk_buff **tab;
};
-/* deliver a random number between 0 and N - 1 */
-static u32 random_N(unsigned int N)
-{
- return reciprocal_divide(prandom_u32(), N);
-}
-
/* number of elements in queue including holes */
static unsigned int choke_len(const struct choke_sched_data *q)
{
@@ -233,7 +226,7 @@ static struct sk_buff *choke_peek_random(const struct choke_sched_data *q,
int retrys = 3;
do {
- *pidx = (q->head + random_N(choke_len(q))) & q->tab_mask;
+ *pidx = (q->head + prandom_u32_max(choke_len(q))) & q->tab_mask;
skb = q->tab[*pidx];
if (skb)
return skb;
--
2.9.3
^ permalink raw reply related [flat|nested] 2+ messages in thread* [patch added to 3.12-stable] KEYS: 64-bit MIPS needs to use compat_sys_keyctl for 32-bit userspace
[not found] <20160818124953.31969-1-jslaby@suse.cz>
2016-08-18 12:49 ` [patch added to 3.12-stable] random32: add prandom_u32_max and convert open coded users Jiri Slaby
@ 2016-08-18 12:49 ` Jiri Slaby
1 sibling, 0 replies; 2+ messages in thread
From: Jiri Slaby @ 2016-08-18 12:49 UTC (permalink / raw)
To: stable
Cc: David Howells, linux-mips, linux-kernel, linux-security-module,
keyrings, Ralf Baechle, Jiri Slaby
From: David Howells <dhowells@redhat.com>
This patch has been added to the 3.12 stable tree. If you have any
objections, please let us know.
===============
commit 20f06ed9f61a185c6dabd662c310bed6189470df upstream.
MIPS64 needs to use compat_sys_keyctl for 32-bit userspace rather than
calling sys_keyctl. The latter will work in a lot of cases, thereby hiding
the issue.
Reported-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: David Howells <dhowells@redhat.com>
Cc: linux-mips@linux-mips.org
Cc: linux-kernel@vger.kernel.org
Cc: linux-security-module@vger.kernel.org
Cc: keyrings@vger.kernel.org
Patchwork: https://patchwork.linux-mips.org/patch/13832/
Signed-off-by: Ralf Baechle <ralf@linux-mips.org>
Signed-off-by: Jiri Slaby <jslaby@suse.cz>
---
arch/mips/kernel/scall64-n32.S | 2 +-
arch/mips/kernel/scall64-o32.S | 2 +-
2 files changed, 2 insertions(+), 2 deletions(-)
diff --git a/arch/mips/kernel/scall64-n32.S b/arch/mips/kernel/scall64-n32.S
index cab150789c8d..b657fbefc466 100644
--- a/arch/mips/kernel/scall64-n32.S
+++ b/arch/mips/kernel/scall64-n32.S
@@ -349,7 +349,7 @@ EXPORT(sysn32_call_table)
PTR sys_ni_syscall /* available, was setaltroot */
PTR sys_add_key
PTR sys_request_key
- PTR sys_keyctl /* 6245 */
+ PTR compat_sys_keyctl /* 6245 */
PTR sys_set_thread_area
PTR sys_inotify_init
PTR sys_inotify_add_watch
diff --git a/arch/mips/kernel/scall64-o32.S b/arch/mips/kernel/scall64-o32.S
index 37605dc8eef7..bf56d7e271dd 100644
--- a/arch/mips/kernel/scall64-o32.S
+++ b/arch/mips/kernel/scall64-o32.S
@@ -474,7 +474,7 @@ sys_call_table:
PTR sys_ni_syscall /* available, was setaltroot */
PTR sys_add_key /* 4280 */
PTR sys_request_key
- PTR sys_keyctl
+ PTR compat_sys_keyctl
PTR sys_set_thread_area
PTR sys_inotify_init
PTR sys_inotify_add_watch /* 4285 */
--
2.9.3
^ permalink raw reply related [flat|nested] 2+ messages in thread