[PATCH net-next 0/3] netem: allow using seeded PRNG for loss and corruption events

[PATCH net-next 0/3] netem: allow using seeded PRNG for loss and corruption events

[Francois Michel]

From: François Michel <francois.michel@uclouvain.be>

In order to reproduce bugs or performance evaluation of
network protocols and applications, it is useful to have
reproducible test suites and tools. This patch adds
a way to specify a PRNG seed for generating netem
loss and corruption events. Initializing the qdisc
with the same seed leads to the exact same loss
and corruption patterns. If no seed is specified, the 
qdisc adopts the classical behaviour, i.e. using the
unseeded get_random_u32() for generating these events.

This patch can be and has been tested using tc from
the following iproute2-next fork:
git@github.com:francoismichel/iproute2-next.git

For instance, setting the seed 42424242 on the loopback
with a loss rate of 10% will systematically drop the 5th,
12th and 24th packet when sending 25 packets.

François Michel (3):
  netem: add prng attribute to netem_sched_data
  netem: allow using a seeded PRNG for generating random losses
  netem: allow using seeded PRNG for correlated loss events

 include/uapi/linux/pkt_sched.h |  1 +
 net/sched/sch_netem.c          | 62 ++++++++++++++++++++++++++--------
 2 files changed, 48 insertions(+), 15 deletions(-)


base-commit: f614a29d6ca6962139b0eb36b985e3dda80258a6
-- 
2.41.0

[PATCH net-next 1/3] [PATCH 1/3] netem: add prng attribute to netem_sched_data

[Francois Michel]

From: François Michel <francois.michel@uclouvain.be>

Add prng attribute to struct netem_sched_data and
allows setting the seed of the PRNG through netlink
using the new TCA_NETEM_PRNG_SEED attribute.
The PRNG attribute is not actually used yet.

Signed-off-by: François Michel <francois.michel@uclouvain.be>
---
 include/uapi/linux/pkt_sched.h |  1 +
 net/sched/sch_netem.c          | 17 +++++++++++++++++
 2 files changed, 18 insertions(+)

diff --git a/include/uapi/linux/pkt_sched.h b/include/uapi/linux/pkt_sched.h
index 00f6ff0aff1f..3f85ae578056 100644
--- a/include/uapi/linux/pkt_sched.h
+++ b/include/uapi/linux/pkt_sched.h
@@ -603,6 +603,7 @@ enum {
 	TCA_NETEM_JITTER64,
 	TCA_NETEM_SLOT,
 	TCA_NETEM_SLOT_DIST,
+	TCA_NETEM_PRNG_SEED,
 	__TCA_NETEM_MAX,
 };
 
diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 38d9aa0cd30e..d73596d0e912 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -105,6 +105,12 @@ struct netem_sched_data {
 		u32 rho;
 	} delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor;
 
+	struct prng  {
+		bool deterministic_rng;
+		u64 original_seed;
+		struct rnd_state prng_state;
+	} prng;
+
 	struct disttable *delay_dist;
 
 	enum  {
@@ -922,6 +928,7 @@ static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = {
 	[TCA_NETEM_LATENCY64]	= { .type = NLA_S64 },
 	[TCA_NETEM_JITTER64]	= { .type = NLA_S64 },
 	[TCA_NETEM_SLOT]	= { .len = sizeof(struct tc_netem_slot) },
+	[TCA_NETEM_PRNG_SEED]	= { .type = NLA_U64 },
 };
 
 static int parse_attr(struct nlattr *tb[], int maxtype, struct nlattr *nla,
@@ -1040,6 +1047,12 @@ static int netem_change(struct Qdisc *sch, struct nlattr *opt,
 	/* capping jitter to the range acceptable by tabledist() */
 	q->jitter = min_t(s64, abs(q->jitter), INT_MAX);
 
+	if (tb[TCA_NETEM_PRNG_SEED]) {
+		q->prng.deterministic_rng = true;
+		q->prng.original_seed = nla_get_u64(tb[TCA_NETEM_PRNG_SEED]);
+		prandom_seed_state(&q->prng.prng_state, q->prng.original_seed);
+	}
+
 unlock:
 	sch_tree_unlock(sch);
 
@@ -1203,6 +1216,10 @@ static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
 			goto nla_put_failure;
 	}
 
+	if (nla_put_u64_64bit(skb, TCA_NETEM_PRNG_SEED, q->prng.original_seed,
+			      TCA_NETEM_PAD))
+		goto nla_put_failure;
+
 	return nla_nest_end(skb, nla);
 
 nla_put_failure:
-- 
2.41.0

[PATCH net-next 2/3] [PATCH 2/3] netem: allow using a seeded PRNG for generating random losses

[Francois Michel]

From: François Michel <francois.michel@uclouvain.be>

Add the netem_get_random_u32 function to sch_netem.c
and use it to generate the random loss events of netem.

If no seed was specified by the application through
setting TCA_NETEM_PRNG_SEED, the default behaviour
is the same as before, i.e. it relies on the unseeded
get_random_u32() function. If a seed was provided,
it relies on the seeded prng attribute of
struct netem_sched_data.

Signed-off-by: François Michel <francois.michel@uclouvain.be>
---
 net/sched/sch_netem.c | 24 +++++++++++++++++++-----
 1 file changed, 19 insertions(+), 5 deletions(-)

diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index d73596d0e912..1190782ef79d 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -154,6 +154,19 @@ struct netem_sched_data {
 	struct disttable *slot_dist;
 };
 
+/* netem_get_random_u32 - polls a new random 32-bits integer from
+ * the prng.
+ * Uses a deterministic seeded prng if p->deterministic_rng is true.
+ * Uses get_random_u32() underneath if p is NULL or if p->deterministic_rng
+ * is false.
+ */
+static u32 netem_get_random_u32(struct prng *p)
+{
+	if (p && p->deterministic_rng)
+		return prandom_u32_state(&p->prng_state);
+	return get_random_u32();
+}
+
 /* Time stamp put into socket buffer control block
  * Only valid when skbs are in our internal t(ime)fifo queue.
  *
@@ -207,7 +220,7 @@ static u32 get_crandom(struct crndstate *state)
 static bool loss_4state(struct netem_sched_data *q)
 {
 	struct clgstate *clg = &q->clg;
-	u32 rnd = get_random_u32();
+	u32 rnd = netem_get_random_u32(&q->prng);
 
 	/*
 	 * Makes a comparison between rnd and the transition
@@ -272,18 +285,19 @@ static bool loss_4state(struct netem_sched_data *q)
 static bool loss_gilb_ell(struct netem_sched_data *q)
 {
 	struct clgstate *clg = &q->clg;
+	struct prng *p = &q->prng;
 
 	switch (clg->state) {
 	case GOOD_STATE:
-		if (get_random_u32() < clg->a1)
+		if (netem_get_random_u32(p) < clg->a1)
 			clg->state = BAD_STATE;
-		if (get_random_u32() < clg->a4)
+		if (netem_get_random_u32(p) < clg->a4)
 			return true;
 		break;
 	case BAD_STATE:
-		if (get_random_u32() < clg->a2)
+		if (netem_get_random_u32(p) < clg->a2)
 			clg->state = GOOD_STATE;
-		if (get_random_u32() > clg->a3)
+		if (netem_get_random_u32(p) > clg->a3)
 			return true;
 	}
 
-- 
2.41.0

[PATCH net-next 3/3] [PATCH 3/3] netem: allow using seeded PRNG for correlated loss events

[Francois Michel]

From: François Michel <francois.michel@uclouvain.be>

Use the netem_get_random_u32() function to generate correlated loss
events of netem.

Signed-off-by: François Michel <francois.michel@uclouvain.be>
---
 net/sched/sch_netem.c | 21 +++++++++++----------
 1 file changed, 11 insertions(+), 10 deletions(-)

diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 1190782ef79d..da333c3d24ac 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -198,15 +198,15 @@ static void init_crandom(struct crndstate *state, unsigned long rho)
  * Next number depends on last value.
  * rho is scaled to avoid floating point.
  */
-static u32 get_crandom(struct crndstate *state)
+static u32 get_crandom(struct crndstate *state, struct prng *p)
 {
 	u64 value, rho;
 	unsigned long answer;
 
 	if (!state || state->rho == 0)	/* no correlation */
-		return get_random_u32();
+		return netem_get_random_u32(p);
 
-	value = get_random_u32();
+	value = netem_get_random_u32(p);
 	rho = (u64)state->rho + 1;
 	answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
 	state->last = answer;
@@ -309,7 +309,7 @@ static bool loss_event(struct netem_sched_data *q)
 	switch (q->loss_model) {
 	case CLG_RANDOM:
 		/* Random packet drop 0 => none, ~0 => all */
-		return q->loss && q->loss >= get_crandom(&q->loss_cor);
+		return q->loss && q->loss >= get_crandom(&q->loss_cor, &q->prng);
 
 	case CLG_4_STATES:
 		/* 4state loss model algorithm (used also for GI model)
@@ -338,6 +338,7 @@ static bool loss_event(struct netem_sched_data *q)
  */
 static s64 tabledist(s64 mu, s32 sigma,
 		     struct crndstate *state,
+			 struct prng *prng,
 		     const struct disttable *dist)
 {
 	s64 x;
@@ -347,7 +348,7 @@ static s64 tabledist(s64 mu, s32 sigma,
 	if (sigma == 0)
 		return mu;
 
-	rnd = get_crandom(state);
+	rnd = get_crandom(state, prng);
 
 	/* default uniform distribution */
 	if (dist == NULL)
@@ -469,7 +470,7 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	skb->prev = NULL;
 
 	/* Random duplication */
-	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
+	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor, &q->prng))
 		++count;
 
 	/* Drop packet? */
@@ -512,7 +513,7 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	 * If packet is going to be hardware checksummed, then
 	 * do it now in software before we mangle it.
 	 */
-	if (q->corrupt && q->corrupt >= get_crandom(&q->corrupt_cor)) {
+	if (q->corrupt && q->corrupt >= get_crandom(&q->corrupt_cor, &q->prng)) {
 		if (skb_is_gso(skb)) {
 			skb = netem_segment(skb, sch, to_free);
 			if (!skb)
@@ -550,12 +551,12 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	cb = netem_skb_cb(skb);
 	if (q->gap == 0 ||		/* not doing reordering */
 	    q->counter < q->gap - 1 ||	/* inside last reordering gap */
-	    q->reorder < get_crandom(&q->reorder_cor)) {
+	    q->reorder < get_crandom(&q->reorder_cor, &q->prng)) {
 		u64 now;
 		s64 delay;
 
 		delay = tabledist(q->latency, q->jitter,
-				  &q->delay_cor, q->delay_dist);
+				  &q->delay_cor, &q->prng, q->delay_dist);
 
 		now = ktime_get_ns();
 
@@ -659,7 +660,7 @@ static void get_slot_next(struct netem_sched_data *q, u64 now)
 	else
 		next_delay = tabledist(q->slot_config.dist_delay,
 				       (s32)(q->slot_config.dist_jitter),
-				       NULL, q->slot_dist);
+				       NULL, &q->prng, q->slot_dist);
 
 	q->slot.slot_next = now + next_delay;
 	q->slot.packets_left = q->slot_config.max_packets;
-- 
2.41.0

Re: [PATCH net-next 2/3] [PATCH 2/3] netem: allow using a seeded PRNG for generating random losses

[Stephen Hemminger]

On Mon, 14 Aug 2023 04:31:39 +0200
Francois Michel <francois.michel@uclouvain.be> wrote:

> +/* netem_get_random_u32 - polls a new random 32-bits integer from
> + * the prng.
> + * Uses a deterministic seeded prng if p->deterministic_rng is true.
> + * Uses get_random_u32() underneath if p is NULL or if p->deterministic_rng
> + * is false.
> + */
> +static u32 netem_get_random_u32(struct prng *p)

Overall I am fine with this patch, but the function name is getting excessively
long. It is a local function, so no need for netem_ prefix.

Checking for p == NULL is redundant, all callers are passing a valid pointer.

For logical consistency, put the new wrapper before init_crandom() and after netem_skb_cb().

Since this is not security related, the change could also be simplified to just
always prandom_u32_state() and initialize the state on first use with either 
get_random or provided seed.  This would also simplify the code around storing
original seed and boolean.

Reminds me of the quote attributed to Mark Twain:
“I apologize for such a long letter - I didn't have time to write a short one.”

Re: [PATCH net-next 2/3] [PATCH 2/3] netem: allow using a seeded PRNG for generating random losses

[François Michel]

Hi,

Le 14/08/23 à 17:49, Stephen Hemminger a écrit :
> On Mon, 14 Aug 2023 04:31:39 +0200
> Francois Michel <francois.michel@uclouvain.be> wrote:
> 
>> +/* netem_get_random_u32 - polls a new random 32-bits integer from
>> + * the prng.
>> + * Uses a deterministic seeded prng if p->deterministic_rng is true.
>> + * Uses get_random_u32() underneath if p is NULL or if p->deterministic_rng
>> + * is false.
>> + */
>> +static u32 netem_get_random_u32(struct prng *p)
> 
> Overall I am fine with this patch, but the function name is getting excessively
> long. It is a local function, so no need for netem_ prefix.
> 
> Checking for p == NULL is redundant, all callers are passing a valid pointer.
> 
> For logical consistency, put the new wrapper before init_crandom() and after netem_skb_cb().
> 
> Since this is not security related, the change could also be simplified to just
> always prandom_u32_state() and initialize the state on first use with either
> get_random or provided seed.  This would also simplify the code around storing
> original seed and boolean.

Thank you very much for your comment.

I do not use prandom_u32_state() directly in order to ensure
that the original netem behaviour is preserved when no seed is specified.

But I agree that it would be cleaner to directly use prandom_u32_state() 
instead of get_random_u32(), if we are sure that we won't have problems 
(e.g. short prng cycles) with the randomly generated seeds when no seed 
is explicitly provided. If it is okay, then
I don't see a reason to not use prandom_u32_state() directly.

I'll make an update of the patch taking these comments into account and 
simplifying the patch.

Thank you !

François

> 
> Reminds me of the quote attributed to Mark Twain:
> “I apologize for such a long letter - I didn't have time to write a short one.”

Re: [PATCH net-next 2/3] [PATCH 2/3] netem: allow using a seeded PRNG for generating random losses

[Stephen Hemminger]

On Mon, 14 Aug 2023 22:14:53 +0200
François Michel <francois.michel@uclouvain.be> wrote:

> Thank you very much for your comment.
> 
> I do not use prandom_u32_state() directly in order to ensure
> that the original netem behaviour is preserved when no seed is specified.
> 
> But I agree that it would be cleaner to directly use prandom_u32_state() 
> instead of get_random_u32(), if we are sure that we won't have problems 
> (e.g. short prng cycles) with the randomly generated seeds when no seed 
> is explicitly provided. If it is okay, then
> I don't see a reason to not use prandom_u32_state() directly.
> 
> I'll make an update of the patch taking these comments into account and 
> simplifying the patch.
> 
> Thank you !
> 
> François

Older versions of netem had prandom_u32_state() equivalent built inside.
The code was split out later to be usable in other places.
Over time, get_random_u32() was added because it was more random and
there were calls to unify random number usage.

The prandom was based on Tausworthe to have good long simulation cycles
and reasonable performance.

Going back to prandom always is good idea, since get_random_u32()
has addition locking and batched entropy which netem really doesn't need/want.