Re: [RFC] sched: CHOKe packet scheduler

Le mercredi 05 janvier 2011 à 09:17 -0800, Stephen Hemminger a écrit :

On Wed, 05 Jan 2011 07:19:35 +0100
Eric Dumazet [off-list ref] wrote:

quoted

Le mardi 04 janvier 2011 à 16:29 -0800, Stephen Hemminger a écrit :

quoted

+static struct sk_buff *skb_peek_random(struct sk_buff_head *list)
+{
+	struct sk_buff *skb = list->next;
+	unsigned int idx = net_random() % list->qlen;
+
+	while (skb && idx-- > 0)
+		skb = skb->next;
+
+	return skb;
+}

You could avoid the divide op :

unsigned int idx = reciprocal_divide(random32(), list->qlen);

How would this work, it is a mod not a divide??

It works, because random32() provides a 32bit 'random' number.
between 0 and 0xFFFFFFFF

We multiply it by X, get a 64bit number between 0 and 0xFFFFFFFF * X
then we right shift it by 32, get a number between 0 and X - 1 

We dont need to get the modulus, just a random number between 0 and X -
1

Dont worry, we should add a helper function to do that, since it might
be used in many places.

/* deliver a random number between 0 and N - 1 */
u32 random_N(unsigned int N)
{
	reciprocal_divide(random32(), N);
}