netdev - Re: [RFC] sched: CHOKe packet scheduler

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1294248332.10633.25.camel@edumazet-laptop>
Date:	Wed, 05 Jan 2011 18:25:32 +0100
From:	Eric Dumazet <eric.dumazet@...il.com>
To:	Stephen Hemminger <shemminger@...tta.com>
Cc:	David Miller <davem@...emloft.net>, netdev@...r.kernel.org
Subject: 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 <eric.dumazet@...il.com> wrote:
> 
> > Le mardi 04 janvier 2011 à 16:29 -0800, Stephen Hemminger a écrit :
> > > +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);
}




--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html