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
| ||
|
Date: Mon, 10 Jan 2011 09:31:23 -0800 From: Stephen Hemminger <shemminger@...tta.com> To: Eric Dumazet <eric.dumazet@...il.com> Cc: David Miller <davem@...emloft.net>, netdev@...r.kernel.org Subject: Re: [RFC] sched: CHOKe packet scheduler (v0.2) On Mon, 10 Jan 2011 14:46:50 +0100 Eric Dumazet <eric.dumazet@...il.com> wrote: > Le jeudi 06 janvier 2011 à 20:55 -0800, Stephen Hemminger a écrit : > > > > > The problem is that large tables of pointers in kernel require either > > contiguous allocation or some indirect table algorithm. > > > > Here is a v3 version with an array based queue for O(1) peek_random > complexity. > > Could you send the iproute2 patch so that I can test it ? > > Thanks ! > > > diff --git a/net/sched/sch_choke.c b/net/sched/sch_choke.c > index e69de29..ea9db00 100644 > --- a/net/sched/sch_choke.c > +++ b/net/sched/sch_choke.c > @@ -0,0 +1,388 @@ > +/* > + * net/sched/sch_choke.c CHOKE scheduler > + * > + * Copyright (c) 2011 Stephen Hemminger <shemminger@...tta.com> > + * Copyright (c) 2011 Eric Dumazet <eric.dumazet@...il.com> > + * > + * This program is free software; you can redistribute it and/or > + * modify it under the terms of the GNU General Public License > + * version 2 as published by the Free Software Foundation. > + * > + */ > + > +#include <linux/module.h> > +#include <linux/types.h> > +#include <linux/kernel.h> > +#include <linux/skbuff.h> > +#include <linux/reciprocal_div.h> > +#include <net/pkt_sched.h> > +#include <net/inet_ecn.h> > +#include <net/red.h> > + > +/* CHOKe stateless AQM for fair bandwidth allocation > + ================================================= > + > + CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for > + unresponsive flows) is a variant of RED that penalizes misbehaving flows but > + maintains no flow state. The difference from RED is an additional step > + during the enqueuing process. If average queue size is over the > + low threshold (qmin), a packet is chosen at random from the queue. > + If both the new and chosen packet are from the same flow, both > + are dropped. Unlike RED, CHOKe is not a "classful" qdisc because it > + needs to access packets in queue randomly. > + > + Source: > + R. Pan, B. Prabhakar, and K. Psounis, "CHOKe, A Stateless > + Active Queue Management Scheme for Approximating Fair Bandwidth Allocation", > + IEEE INFOCOM, 2000. > + > + A. Tang, J. Wang, S. Low, "Understanding CHOKe: Throughput and Spatial > + Characteristics", IEEE/ACM Transactions on Networking, 2004 > + > + */ > + > +struct choke_sched_data { > + u32 limit; > + unsigned char flags; > + > + struct red_parms parms; > + struct red_stats stats; > + > + unsigned int head; > + unsigned int tail; > + unsigned int holes; > + unsigned int tab_mask; /* size - 1 */ > + struct sk_buff **tab; > +}; > + > +static inline unsigned int choke_len(const struct choke_sched_data *q) > +{ > + return (q->tail - q->head) & q->tab_mask; > +} > + > +/* deliver a random number between 0 and N - 1 */ > +static inline u32 random_N(unsigned int N) > +{ > + return reciprocal_divide(random32(), N); > +} > + > +/* Select a packet at random from the queue in O(1) */ > +static struct sk_buff *choke_peek_random(struct choke_sched_data *q, unsigned int *pidx) > +{ > + *pidx = (q->head + random_N(choke_len(q))) & q->tab_mask; > + return q->tab[*pidx]; > +} I don't think this works right. The choke_peek_random could find a hole. Either the data structure has to change, or the peek_random has to retry, or if quick peek fails then compress the slot with memmove and retry. -- -- 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
Powered by blists - more mailing lists