* Re: [PATCH] sched: QFQ - quick fair queue scheduler (v2)
From: Eric Dumazet @ 2011-03-03 16:03 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: David Miller, Fabio Checconi, Luigi Rizzo, netdev
In-Reply-To: <20110228171738.2cc8c9a0@nehalam>
Le lundi 28 février 2011 à 17:17 -0800, Stephen Hemminger a écrit :
> +static int qfq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
> + struct gnet_dump *d)
> +{
> + struct qfq_class *cl = (struct qfq_class *)arg;
> + struct tc_qfq_stats xstats;
> +
> + memset(&xstats, 0, sizeof(xstats));
> +
> + xstats.weight = ONE_FP/cl->inv_w;
> + xstats.lmax = cl->lmax;
> +
cl->qdisc->qstats.qlen = cl->qdisc->q.qlen;
> + if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
> + gnet_stats_copy_rate_est(d, NULL, &cl->rate_est) < 0 ||
> + gnet_stats_copy_queue(d, &cl->qdisc->qstats) < 0)
> + return -1;
> +
> + return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
> +}
> +
using
gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0
is better : We avoid dumping null rate estimation, if admin never asked
a rate estimation...
^ permalink raw reply
* [BUG net-next-2.6] dst_release() crash
From: Eric Dumazet @ 2011-03-03 16:28 UTC (permalink / raw)
To: David Miller; +Cc: netdev
Just had this while working on latest net-next-2.6
[11483.697210] BUG: unable to handle kernel NULL pointer dereference at
0000002a
[11483.697233] IP: [<c12b0638>] dst_release+0x18/0x60
[11483.697252] *pdpt = 0000000034917001 *pde = 0000000000000000
[11483.697270] Oops: 0002 [#1] SMP
[11483.697283] last sysfs
file: /sys/devices/virtual/net/bond0/bonding/active_slave
[11483.697299] Modules linked in: pktgen ipmi_si ipmi_msghandler hpilo
tg3 bonding ipv6
[11483.697335]
[11483.697340] Pid: 5490, comm: ntpd Not tainted
2.6.38-rc5-02884-g0853e6c-dirty #974 HP ProLiant BL460c G1
[11483.697366] EIP: 0060:[<c12b0638>] EFLAGS: 00010282 CPU: 4
[11483.697392] EIP is at dst_release+0x18/0x60
[11483.697416] EAX: ffffffea EBX: ffffffea ECX: 00000000 EDX: 6e14a8c0
[11483.697444] ESI: ffffffff EDI: ffffffea EBP: f445fd18 ESP: f445fd10
[11483.697471] DS: 007b ES: 007b FS: 00d8 GS: 0033 SS: 0068
[11483.697497] Process ntpd (pid: 5490, ti=f445e000 task=f3542490
task.ti=f445e000)
[11483.697540] Stack:
[11483.697562] f3401400 ffffffea f445fdc0 c12fc9d2 00000030 f445fd3c
c12a1c01 00000282
[11483.697619] 00000008 00000030 0dfeaa0a 6e14a8c0 7b001000 00000000
0dfeaa0a f445fda0
[11483.697680] 00000000 00000000 c12dbd90 00000000 f445ff38 00000000
00000000 00000000
[11483.697741] Call Trace:
[11483.697764] [<c12fc9d2>] udp_sendmsg+0x282/0x6e0
[11483.697790] [<c12a1c01>] ? memcpy_toiovec+0x51/0x70
[11483.697818] [<c12dbd90>] ? ip_generic_getfrag+0x0/0xb0
[11483.697848] [<c1184e00>] ? timerqueue_add+0x30/0xc0
[11483.697874] [<c1304ae5>] inet_sendmsg+0x45/0xa0
[11483.697901] [<c10617ab>] ? __hrtimer_start_range_ns+0x1ab/0x500
[11483.697930] [<c1298543>] sock_sendmsg+0xc3/0xf0
[11483.697957] [<c100b2b4>] ? save_i387_fxsave+0x74/0x80
[11483.697984] [<c1189022>] ? _copy_from_user+0x32/0x50
[11483.698010] [<c1299702>] sys_sendto+0xb2/0xe0
[11483.698035] [<c100bd50>] ? restore_i387_xstate+0xd0/0x1f0
[11483.698062] [<c129a07d>] sys_socketcall+0x18d/0x270
[11483.698088] [<c1002cd0>] sysenter_do_call+0x12/0x26
[11483.698123] Code: 53 c1 e8 ac 0b 0a 00 5b c9 c3 89 f6 8d bc 27 00 00
00 00 55 89 e5 83 ec 08 85 c0 89 1c 24 89 74 24 04 89 c3 74 11 be ff ff
ff ff <f0> 0f c1 70 40 4e 78 2f 85 f6 74 0c 8b 1c 24 8b 74 24 04 c9 c3
[11483.698319] EIP: [<c12b0638>] dst_release+0x18/0x60 SS:ESP
0068:f445fd10
[11483.698350] CR2: 000000000000002a
[11483.698594] ---[ end trace cb654a6638801e35 ]---
crash in
c12b0638: f0 0f c1 70 40 lock xadd %esi,0x40(%eax)
EAX = -EINVAL
commit b23dd4fe42b455af (ipv4: Make output route lookup return rtable
directly) introduced a regression ...
We could add a sanity test in dst_release(), or fix callers ?
What do you think ?
^ permalink raw reply
* Re: bonding...
From: Stephen Hemminger @ 2011-03-03 16:31 UTC (permalink / raw)
To: Ben Hutchings; +Cc: David Miller, fubar, netdev
In-Reply-To: <1299159991.4277.45.camel@localhost>
On Thu, 03 Mar 2011 13:46:31 +0000
Ben Hutchings <bhutchings@solarflare.com> wrote:
> On Wed, 2011-03-02 at 21:49 -0800, David Miller wrote:
> [...]
> > This is unacceptable, people are submitting multiple bonding patches
> > every single day now. It needs a clueful bonding person looking at
> > these submissions on a constant basis.
> [...]
>
> And preferably saying 'no' to most new features...
Agreed. It seems bonding has diverged from the standards and wants
to support every packet flow some user can think up.
^ permalink raw reply
* Re: bonding...
From: Eric Dumazet @ 2011-03-03 16:52 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: Ben Hutchings, David Miller, fubar, netdev
In-Reply-To: <20110303083110.4e7f020c@nehalam>
Le jeudi 03 mars 2011 à 08:31 -0800, Stephen Hemminger a écrit :
> On Thu, 03 Mar 2011 13:46:31 +0000
> Ben Hutchings <bhutchings@solarflare.com> wrote:
>
> > On Wed, 2011-03-02 at 21:49 -0800, David Miller wrote:
> > [...]
> > > This is unacceptable, people are submitting multiple bonding patches
> > > every single day now. It needs a clueful bonding person looking at
> > > these submissions on a constant basis.
> > [...]
> >
> > And preferably saying 'no' to most new features...
>
> Agreed. It seems bonding has diverged from the standards and wants
> to support every packet flow some user can think up.
A simple setup that was working in 2.6.35 doesnt work anymore here
vlan.103 - bond0 - eth3 (tg3 nic)
With a bnx2 nic, it works
Not sure its a bond problem, more probably a vlan one...
^ permalink raw reply
* [PATCH net-next-2.6] udp: udp_sendmsg() fix
From: Eric Dumazet @ 2011-03-03 17:07 UTC (permalink / raw)
To: David Miller; +Cc: netdev
In-Reply-To: <1299169686.2983.129.camel@edumazet-laptop>
Le jeudi 03 mars 2011 à 17:28 +0100, Eric Dumazet a écrit :
> Just had this while working on latest net-next-2.6
>
> [11483.697210] BUG: unable to handle kernel NULL pointer dereference at
> 0000002a
> [11483.697233] IP: [<c12b0638>] dst_release+0x18/0x60
> [11483.697252] *pdpt = 0000000034917001 *pde = 0000000000000000
> [11483.697270] Oops: 0002 [#1] SMP
> [11483.697283] last sysfs
> file: /sys/devices/virtual/net/bond0/bonding/active_slave
> [11483.697299] Modules linked in: pktgen ipmi_si ipmi_msghandler hpilo
> tg3 bonding ipv6
> [11483.697335]
> [11483.697340] Pid: 5490, comm: ntpd Not tainted
> 2.6.38-rc5-02884-g0853e6c-dirty #974 HP ProLiant BL460c G1
> [11483.697366] EIP: 0060:[<c12b0638>] EFLAGS: 00010282 CPU: 4
> [11483.697392] EIP is at dst_release+0x18/0x60
> [11483.697416] EAX: ffffffea EBX: ffffffea ECX: 00000000 EDX: 6e14a8c0
> [11483.697444] ESI: ffffffff EDI: ffffffea EBP: f445fd18 ESP: f445fd10
> [11483.697471] DS: 007b ES: 007b FS: 00d8 GS: 0033 SS: 0068
> [11483.697497] Process ntpd (pid: 5490, ti=f445e000 task=f3542490
> task.ti=f445e000)
> [11483.697540] Stack:
> [11483.697562] f3401400 ffffffea f445fdc0 c12fc9d2 00000030 f445fd3c
> c12a1c01 00000282
> [11483.697619] 00000008 00000030 0dfeaa0a 6e14a8c0 7b001000 00000000
> 0dfeaa0a f445fda0
> [11483.697680] 00000000 00000000 c12dbd90 00000000 f445ff38 00000000
> 00000000 00000000
> [11483.697741] Call Trace:
> [11483.697764] [<c12fc9d2>] udp_sendmsg+0x282/0x6e0
> [11483.697790] [<c12a1c01>] ? memcpy_toiovec+0x51/0x70
> [11483.697818] [<c12dbd90>] ? ip_generic_getfrag+0x0/0xb0
> [11483.697848] [<c1184e00>] ? timerqueue_add+0x30/0xc0
> [11483.697874] [<c1304ae5>] inet_sendmsg+0x45/0xa0
> [11483.697901] [<c10617ab>] ? __hrtimer_start_range_ns+0x1ab/0x500
> [11483.697930] [<c1298543>] sock_sendmsg+0xc3/0xf0
> [11483.697957] [<c100b2b4>] ? save_i387_fxsave+0x74/0x80
> [11483.697984] [<c1189022>] ? _copy_from_user+0x32/0x50
> [11483.698010] [<c1299702>] sys_sendto+0xb2/0xe0
> [11483.698035] [<c100bd50>] ? restore_i387_xstate+0xd0/0x1f0
> [11483.698062] [<c129a07d>] sys_socketcall+0x18d/0x270
> [11483.698088] [<c1002cd0>] sysenter_do_call+0x12/0x26
> [11483.698123] Code: 53 c1 e8 ac 0b 0a 00 5b c9 c3 89 f6 8d bc 27 00 00
> 00 00 55 89 e5 83 ec 08 85 c0 89 1c 24 89 74 24 04 89 c3 74 11 be ff ff
> ff ff <f0> 0f c1 70 40 4e 78 2f 85 f6 74 0c 8b 1c 24 8b 74 24 04 c9 c3
> [11483.698319] EIP: [<c12b0638>] dst_release+0x18/0x60 SS:ESP
> 0068:f445fd10
> [11483.698350] CR2: 000000000000002a
> [11483.698594] ---[ end trace cb654a6638801e35 ]---
>
>
> crash in
>
> c12b0638: f0 0f c1 70 40 lock xadd %esi,0x40(%eax)
>
> EAX = -EINVAL
>
>
>
> commit b23dd4fe42b455af (ipv4: Make output route lookup return rtable
> directly) introduced a regression ...
>
> We could add a sanity test in dst_release(), or fix callers ?
>
> What do you think ?
>
>
Here is the patch I cooked after an audit
[PATCH net-next-2.6] udp: udp_sendmsg() fix
commit b23dd4fe42b455af (ipv4: Make output route lookup return rtable
directly) introduced a regression in udp_sendmsg()
If IP route lookup fails, we should not try to release an non existent
route.
Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
---
diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c
index 95e0c2c..f6c0c00 100644
--- a/net/ipv4/udp.c
+++ b/net/ipv4/udp.c
@@ -927,7 +927,7 @@ int udp_sendmsg(struct kiocb *iocb, struct sock *sk, struct msghdr *msg,
err = PTR_ERR(rt);
if (err == -ENETUNREACH)
IP_INC_STATS_BH(net, IPSTATS_MIB_OUTNOROUTES);
- goto out;
+ goto out2;
}
err = -EACCES;
@@ -991,6 +991,7 @@ do_append_data:
out:
ip_rt_put(rt);
+out2:
if (free)
kfree(ipc.opt);
if (!err)
^ permalink raw reply related
* Re: bonding...
From: Jay Vosburgh @ 2011-03-03 17:24 UTC (permalink / raw)
To: Andy Gospodarek; +Cc: Neil Horman, David Miller, netdev
In-Reply-To: <20110303160404.GO11864@gospo.rdu.redhat.com>
Andy Gospodarek <andy@greyhouse.net> wrote:
>On Thu, Mar 03, 2011 at 06:45:39AM -0500, Neil Horman wrote:
>> On Wed, Mar 02, 2011 at 09:49:10PM -0800, David Miller wrote:
>> >
>> > Hey, if someone could step up and help with bonding maintainence
>> > in some tangible way, I'd really appreciate it.
>> >
>> > Currently the situation is that many people work on bonding patches,
>> > and whilst I do try and wait for some ACKs to arrive, I am the person
>> > who has to sort out when changes are ready, decide to apply them, and
>> > poke for review when things fall through the cracks.
>> >
>> > Sometimes patches go for weeks without ACKs, and in that situation
>> > I have to either try to understand the changes myself, or wait
>> > potentially forever for someone with bonding knowledge to take a
>> > good look at the patch and properly review it.
>> >
>> > It was nearly 2 weeks before Oleg V. Ukhno's 802.3ad round-robin patch
>> > got looked at by anyone with bonding knowledge. And it only happened
>> > because I got tired of seeing his poor patch rot in patchwork
>> > and had to explicitly asked for review the other day.
>> >
>> > This is unacceptable, people are submitting multiple bonding patches
>> > every single day now. It needs a clueful bonding person looking at
>> > these submissions on a constant basis.
>> >
>> > This is a serious problem and is backlogging the netdev patch queue.
>> >
>> > So if someone would become an active bonding patch-accumulator, and
>> > send me sets of patches that are ready to apply, I would really
>> > appreciate it.
>> >
>> > Thanks.
>> I nominate gospo. If he doesn't want to, I can do it
>> Neil
>>
>
>I would be willing to do it, but my one of my goals would be to prevent
>some of the feature creep we are currently seeing with bonding (as Ben
>has suggested). That doesn't mean I want to stop all new features, but
>at this point things are starting to get out of control. I suspect this
>is why Jay has struggled to keep up with the patches.
My main problem keeping up at the moment is another demand on my
time that should run its course in a couple of weeks. My time for
community activity is somewhat limited until then.
As far as the features go, yes, I agree that things are getting
out of hand. The two pending patches for special cases related to
802.3ad (Oleg's patch to permit round robining, the other to enable
spanning aggregators across switches), for example, are fine
functionality, but there really needs to be a better, generic, way to do
this sort of niche case activity without adding more knobs.
I personally like Stephen's suggestion to hook bonding into a
netfilter gadget, similar to ebtables for bridge. Done properly, such a
gadget should handle (or be extended to handle) the niche cases that
right now end up as new knobs in the driver.
>I would also want to look at a restructuring of the configuration. The
>lines are starting to blur between some of the modes and output port
>selection for other modes and that needs to be cleared up.
What did you have in mind here?
-J
---
-Jay Vosburgh, IBM Linux Technology Center, fubar@us.ibm.com
^ permalink raw reply
* Re: [BUG] VPN broken in net-next
From: Stephen Hemminger @ 2011-03-03 17:32 UTC (permalink / raw)
To: Julian Anastasov; +Cc: David Miller, netdev
In-Reply-To: <alpine.LFD.2.00.1103031454060.2113@ja.ssi.bg>
> Hello,
>
> On Thu, 3 Mar 2011, Julian Anastasov wrote:
>
> > May be the problem is in inet_hash_insert(), it should
> > hash ifa_local, not ifa_address. May be they are equal for
>
> ... and of course the new __ip_dev_find should use
> ifa_local too.
>
> > the common case but not for peer addresses. In devinet_ioctl()
> > we can see they are equal initially:
> >
> > ifa->ifa_address = ifa->ifa_local = sin->sin_addr.s_addr;
> >
> > but later SIOCSIFDSTADDR can change ifa_address which
> > is destination address from the same prefix:
> >
> > ifa->ifa_address = sin->sin_addr.s_addr;
>
> While checking for ifa_address usage I see other
> two places that look suspicious:
>
> - inet_gifconf() exposes address from ifa_local but then
> devinet_ioctl() matches by ifa_address in the
> 'if (tryaddrmatch)' block. I think, we should use ifa_local.
>
> - IN_DEV_ARP_NOTIFY: announces ifa_address instead of ifa_local.
Julian you are on the right track with the ifa_local being the issue.
1. Bring up VPN
(no errors)
2. Ping one address gets connect error
3. Instrumentation triggers. I added code so if __ip_dev_find failed,
it walked the hash table.
net=ffffffff81a12d80
[ 393.224228] __ip_dev_find(ffffffff81a12d80, 10.250.0.104) hash=108 failed
[ 393.224232] 138: ffffffff81a12d80 ifa_addr=127.0.0.1 ifa_local=127.0.0.1
[ 393.224236] 150: ffffffff81a12d80 ifa_addr=192.168.1.11 ifa_local=192.168.1.11
[ 393.224239] 249: ffffffff81a12d80 ifa_addr=192.168.100.1 ifa_local=192.168.100.1
[ 393.224242] 254: ffffffff81a12d80 ifa_addr=192.168.99.1 ifa_local=192.168.99.1
[ 393.224245] 255: ffffffff81a12d80 ifa_addr=10.255.254.0 ifa_local=10.250.0.10
^ permalink raw reply
* Re: [PATCH 2/2] netlink: kill eff_cap from struct netlink_skb_parms
From: Chris Wright @ 2011-03-03 17:32 UTC (permalink / raw)
To: Patrick McHardy
Cc: NetDev, dm-devel, David S. Miller, Chris Wright,
linux-security-module@vger.kernel.org, drbd-dev
In-Reply-To: <4D6F6180.5030903@trash.net>
* Patrick McHardy (kaber@trash.net) wrote:
> commit 8ff259625f0ab295fa085b0718eed13093813fbc
> Author: Patrick McHardy <kaber@trash.net>
> Date: Thu Mar 3 10:17:31 2011 +0100
>
> netlink: kill eff_cap from struct netlink_skb_parms
>
> Netlink message processing in the kernel is synchronous these days,
> capabilities can be checked directly in security_netlink_recv() from
> the current process.
>
> Signed-off-by: Patrick McHardy <kaber@trash.net>
Thanks for doing that Patrick. I looked at this earlier and thought
there was still an async path, but I guess that's just to another
userspace process.
BTW, I think you missed a couple connector based callers:
drivers/staging/pohmelfs/config.c: if (!cap_raised(nsp->eff_cap, CAP_SYS_AD
drivers/video/uvesafb.c: if (!cap_raised(nsp->eff_cap, CAP_SYS_ADMIN))
Fix those and:
Acked-by: Chris Wright <chrisw@sous-sol.org>
Ideally, we'd consolidate those into a variant of security_netlink_recv().
However the issue is with types. Inside connector callback we only have
netlink_skb_params (seems inapproriate to cast back out to skb).
We could change the lsm hook to only pass nsp, but SELinux actually
cares about the netlink type. Any ideas?
^ permalink raw reply
* Re: Bad performance when CUBIC HyStart enabled
From: Lucas Nussbaum @ 2011-03-03 17:37 UTC (permalink / raw)
To: Eric Dumazet; +Cc: netdev, Sangtae Ha
In-Reply-To: <1299164580.2983.99.camel@edumazet-laptop>
[-- Attachment #1: Type: text/plain, Size: 3694 bytes --]
On 03/03/11 at 16:03 +0100, Eric Dumazet wrote:
> Le jeudi 03 mars 2011 à 15:22 +0100, Lucas Nussbaum a écrit :
> > Hi,
> >
> > I'm experiencing bad performance transferring data over a large BDP
> > network with CUBIC when HyStart is enabled. Disabling HyStart fixes the
> > problem.
> >
> > Test setup:
> > I'm transfering a 2-GB file between two machines using netcat. On both
> > machines, /dev/shm is used to store the data.
> > On the sending side, I use:
> > /dev/shm# while true; do dd if=foo bs=10M | nc -l -p 2222 -q 0; done
> > On the receiving side, I use:
> > /dev/shm# /usr/bin/time nc 131.254.203.6 2222 > foo
> > Both machines are on Gigabit ethernet networks, and the RTT between them
> > is 11.3ms.
> > The default sysctl values are used.
> > I use nload -i 1000000 -o 1000000 -u m eth0 to visualize the transfer
> > rate.
> >
> > With a 2.6.26 kernel, everything is fine. The bandwidth quickly gets to
> > ~940 Mbps, and I get the following in nload:
> > ..................................
> > .##################################
> > ###################################
> > ###################################
> > ###################################
> > ####################################
> > ####################################
> > ####################################
> > ####################################
> > ####################################
> > ####################################
> > ####################################
> > ####################################
> > ####################################
> > The transfer time is 18.2s, which is reasonable for a 2-GB file.
> >
> > With a 2.6.32 kernel (Debian's) or with a 2.6.37 kernel (on the sending
> > side only), with the default HyStart parameters, I get the following:
> > ..........................
> > |##########################.
> > |############################
> > |#############################
> > |##############################
> > |###############################
> > .#################################
> > |##################################|
> > |#####################################
> > ..||#######################################
> > ....|##############################################
> > .#####################################################
> > The transfer time is 26.8s. (There's one character every 0.5s on the
> > graph above)
> >
> > Disabling hystart on the sending machine with:
> > echo 0 > /sys/module/tcp_cubic/parameters/hystart
> > Fixes the problem.
> >
> > It seems that waiting for some time (or rebooting) fixes the problem for
> > some time, so I'm suspecting that the problem is caused by a cache of
> > some sort. However, doing:
> > echo 1 > /proc/sys/net/ipv4/route/flush
> > doesn't fix the problem.
> >
> > Ideas? I could arrange to give access to the testbed if needed.
> > (https://www.grid5000.fr/)
>
> eventually, after fresh boot of both sender/receiver, it would be nice
> to have "netstat -s" results after one transfert with said problems.
Hi,
Attached.
I had 6 successful transfers. There's the netstat -s output after the 5
first successful transfers. Then the 7th transfer showed the problem,
as well as the 8th and the 9th. There's the netstat -s output after each
of them.
--
| Lucas Nussbaum MCF Université Nancy 2 |
| lucas.nussbaum@loria.fr LORIA / AlGorille |
| http://www.loria.fr/~lnussbau/ +33 3 54 95 86 19 |
[-- Attachment #2: netstat-s.tgz --]
[-- Type: application/x-gtar, Size: 2275 bytes --]
^ permalink raw reply
* Re: Bad performance when CUBIC HyStart enabled
From: Eric Dumazet @ 2011-03-03 17:46 UTC (permalink / raw)
To: Lucas Nussbaum; +Cc: netdev, Sangtae Ha
In-Reply-To: <20110303173733.GB8028@xanadu.blop.info>
Le jeudi 03 mars 2011 à 18:37 +0100, Lucas Nussbaum a écrit :
> I had 6 successful transfers. There's the netstat -s output after the 5
> first successful transfers. Then the 7th transfer showed the problem,
> as well as the 8th and the 9th. There's the netstat -s output after each
> of them.
Its a bit strange : my 'netstat -s' are more verbose than yours :
netstat -s
Ip:
1033944 total packets received
0 forwarded
0 incoming packets discarded
1033705 incoming packets delivered
701852 requests sent out
4 dropped because of missing route
120 reassemblies required
60 packets reassembled ok
60 fragments received ok
120 fragments created
Icmp:
704 ICMP messages received
0 input ICMP message failed.
ICMP input histogram:
destination unreachable: 177
timeout in transit: 117
echo requests: 103
echo replies: 307
693 ICMP messages sent
0 ICMP messages failed
ICMP output histogram:
destination unreachable: 177
echo request: 413
echo replies: 103
IcmpMsg:
InType0: 307
InType3: 177
InType8: 103
InType11: 117
OutType0: 103
OutType3: 177
OutType8: 413
Tcp:
10526 active connections openings
212 passive connection openings
78 failed connection attempts
300 connection resets received
26 connections established
969786 segments received
690213 segments send out
894 segments retransmited
0 bad segments received.
305 resets sent
Udp:
43123 packets received
4 packets to unknown port received.
0 packet receive errors
9570 packets sent
UdpLite:
TcpExt:
877 TCP sockets finished time wait in fast timer
23798 delayed acks sent
10 delayed acks further delayed because of locked socket
Quick ack mode was activated 598 times
542574 packets directly queued to recvmsg prequeue.
140834 bytes directly in process context from backlog
45033318 bytes directly received in process context from prequeue
646384 packet headers predicted
81439 packets header predicted and directly queued to user
24971 acknowledgments not containing data payload received
189383 predicted acknowledgments
2 times recovered from packet loss by selective acknowledgements
3 congestion windows recovered without slow start by DSACK
308 congestion windows recovered without slow start after partial
ack
2 TCP data loss events
3 timeouts after SACK recovery
2 fast retransmits
1 retransmits in slow start
632 other TCP timeouts
9 times receiver scheduled too late for direct processing
587 DSACKs sent for old packets
2 DSACKs sent for out of order packets
417 DSACKs received
130 connections reset due to unexpected data
72 connections aborted due to timeout
TCPDSACKIgnoredOld: 176
TCPDSACKIgnoredNoUndo: 56
TCPSackMerged: 5
TCPSackShiftFallback: 4
TCPDeferAcceptDrop: 106
IpExt:
InNoRoutes: 5
InMcastPkts: 35832
OutMcastPkts: 1403
InBcastPkts: 19536
OutBcastPkts: 89
InOctets: 787953535
OutOctets: 113825814
InMcastOctets: 4098542
OutMcastOctets: 211245
InBcastOctets: 1906912
OutBcastOctets: 13625
^ permalink raw reply
* [PATCH 1/3] KEYS: Add a new keyctl op to reject a key with a specified error code
From: David Howells @ 2011-03-03 17:49 UTC (permalink / raw)
To: linux-security-module, keyrings; +Cc: linux-kernel, netdev, David Howells
Add a new keyctl op to reject a key with a specified error code. This works
much the same as negating a key, and so keyctl_negate_key() is made a special
case of keyctl_reject_key(). The difference is that keyctl_negate_key()
selects ENOKEY as the error to be reported.
Typically the key would be rejected with EKEYEXPIRED, EKEYREVOKED or
EKEYREJECTED, but this is not mandatory.
Signed-off-by: David Howells <dhowells@redhat.com>
---
Documentation/keys-request-key.txt | 9 +++++---
Documentation/keys.txt | 10 +++++++--
include/linux/key-type.h | 11 +++++++++-
include/linux/key.h | 1 +
include/linux/keyctl.h | 1 +
security/keys/compat.c | 3 +++
security/keys/internal.h | 1 +
security/keys/key.c | 19 ++++++++++-------
security/keys/keyctl.c | 40 ++++++++++++++++++++++++++++++++++--
security/keys/keyring.c | 4 ++--
security/keys/request_key.c | 2 +-
11 files changed, 81 insertions(+), 20 deletions(-)
diff --git a/Documentation/keys-request-key.txt b/Documentation/keys-request-key.txt
index 09b55e4..69686ad 100644
--- a/Documentation/keys-request-key.txt
+++ b/Documentation/keys-request-key.txt
@@ -127,14 +127,15 @@ This is because process A's keyrings can't simply be attached to
of them, and (b) it requires the same UID/GID/Groups all the way through.
-======================
-NEGATIVE INSTANTIATION
-======================
+====================================
+NEGATIVE INSTANTIATION AND REJECTION
+====================================
Rather than instantiating a key, it is possible for the possessor of an
authorisation key to negatively instantiate a key that's under construction.
This is a short duration placeholder that causes any attempt at re-requesting
-the key whilst it exists to fail with error ENOKEY.
+the key whilst it exists to fail with error ENOKEY if negated or the specified
+error if rejected.
This is provided to prevent excessive repeated spawning of /sbin/request-key
processes for a key that will never be obtainable.
diff --git a/Documentation/keys.txt b/Documentation/keys.txt
index cf68d1f..a6a97fd 100644
--- a/Documentation/keys.txt
+++ b/Documentation/keys.txt
@@ -657,6 +657,8 @@ The keyctl syscall functions are:
long keyctl(KEYCTL_NEGATE, key_serial_t key,
unsigned timeout, key_serial_t keyring);
+ long keyctl(KEYCTL_REJECT, key_serial_t key,
+ unsigned timeout, unsigned error, key_serial_t keyring);
If the kernel calls back to userspace to complete the instantiation of a
key, userspace should use this call mark the key as negative before the
@@ -669,6 +671,10 @@ The keyctl syscall functions are:
that keyring, however all the constraints applying in KEYCTL_LINK apply in
this case too.
+ If the key is rejected, future searches for it will return the specified
+ error code until the rejected key expires. Negating the key is the same
+ as rejecting the key with ENOKEY as the error code.
+
(*) Set the default request-key destination keyring.
@@ -1240,8 +1246,8 @@ example, the KDE desktop manager).
The program (or whatever it calls) should finish construction of the key by
calling KEYCTL_INSTANTIATE, which also permits it to cache the key in one of
the keyrings (probably the session ring) before returning. Alternatively, the
-key can be marked as negative with KEYCTL_NEGATE; this also permits the key to
-be cached in one of the keyrings.
+key can be marked as negative with KEYCTL_NEGATE or KEYCTL_REJECT; this also
+permits the key to be cached in one of the keyrings.
If it returns with the key remaining in the unconstructed state, the key will
be marked as being negative, it will be added to the session keyring, and an
diff --git a/include/linux/key-type.h b/include/linux/key-type.h
index fc8525e8..9efd081 100644
--- a/include/linux/key-type.h
+++ b/include/linux/key-type.h
@@ -105,11 +105,20 @@ extern int key_instantiate_and_link(struct key *key,
size_t datalen,
struct key *keyring,
struct key *instkey);
-extern int key_negate_and_link(struct key *key,
+extern int key_reject_and_link(struct key *key,
unsigned timeout,
+ unsigned error,
struct key *keyring,
struct key *instkey);
extern void complete_request_key(struct key_construction *cons, int error);
+static inline int key_negate_and_link(struct key *key,
+ unsigned timeout,
+ struct key *keyring,
+ struct key *instkey)
+{
+ return key_reject_and_link(key, timeout, ENOKEY, keyring, instkey);
+}
+
#endif /* CONFIG_KEYS */
#endif /* _LINUX_KEY_TYPE_H */
diff --git a/include/linux/key.h b/include/linux/key.h
index a6b1edc..b2bb017 100644
--- a/include/linux/key.h
+++ b/include/linux/key.h
@@ -170,6 +170,7 @@ struct key {
struct list_head link;
unsigned long x[2];
void *p[2];
+ int reject_error;
} type_data;
/* key data
diff --git a/include/linux/keyctl.h b/include/linux/keyctl.h
index bd383f1..7022974 100644
--- a/include/linux/keyctl.h
+++ b/include/linux/keyctl.h
@@ -53,5 +53,6 @@
#define KEYCTL_ASSUME_AUTHORITY 16 /* assume request_key() authorisation */
#define KEYCTL_GET_SECURITY 17 /* get key security label */
#define KEYCTL_SESSION_TO_PARENT 18 /* apply session keyring to parent process */
+#define KEYCTL_REJECT 19 /* reject a partially constructed key */
#endif /* _LINUX_KEYCTL_H */
diff --git a/security/keys/compat.c b/security/keys/compat.c
index 07a5f35..17c99d0 100644
--- a/security/keys/compat.c
+++ b/security/keys/compat.c
@@ -85,6 +85,9 @@ asmlinkage long compat_sys_keyctl(u32 option,
case KEYCTL_SESSION_TO_PARENT:
return keyctl_session_to_parent();
+ case KEYCTL_REJECT:
+ return keyctl_reject_key(arg2, arg3, arg4, arg5);
+
default:
return -EOPNOTSUPP;
}
diff --git a/security/keys/internal.h b/security/keys/internal.h
index a52aa7c..286c095 100644
--- a/security/keys/internal.h
+++ b/security/keys/internal.h
@@ -214,6 +214,7 @@ extern long keyctl_assume_authority(key_serial_t);
extern long keyctl_get_security(key_serial_t keyid, char __user *buffer,
size_t buflen);
extern long keyctl_session_to_parent(void);
+extern long keyctl_reject_key(key_serial_t, unsigned, unsigned, key_serial_t);
/*
* Debugging key validation
diff --git a/security/keys/key.c b/security/keys/key.c
index 8e315ef..f7f9d93 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -511,26 +511,29 @@ int key_instantiate_and_link(struct key *key,
EXPORT_SYMBOL(key_instantiate_and_link);
/**
- * key_negate_and_link - Negatively instantiate a key and link it into the keyring.
+ * key_reject_and_link - Negatively instantiate a key and link it into the keyring.
* @key: The key to instantiate.
* @timeout: The timeout on the negative key.
+ * @error: The error to return when the key is hit.
* @keyring: Keyring to create a link in on success (or NULL).
* @authkey: The authorisation token permitting instantiation.
*
* Negatively instantiate a key that's in the uninstantiated state and, if
- * successful, set its timeout and link it in to the destination keyring if one
- * is supplied. The key and any links to the key will be automatically garbage
- * collected after the timeout expires.
+ * successful, set its timeout and stored error and link it in to the
+ * destination keyring if one is supplied. The key and any links to the key
+ * will be automatically garbage collected after the timeout expires.
*
* Negative keys are used to rate limit repeated request_key() calls by causing
- * them to return -ENOKEY until the negative key expires.
+ * them to return the stored error code (typically ENOKEY) until the negative
+ * key expires.
*
* If successful, 0 is returned, the authorisation token is revoked and anyone
* waiting for the key is woken up. If the key was already instantiated,
* -EBUSY will be returned.
*/
-int key_negate_and_link(struct key *key,
+int key_reject_and_link(struct key *key,
unsigned timeout,
+ unsigned error,
struct key *keyring,
struct key *authkey)
{
@@ -556,6 +559,7 @@ int key_negate_and_link(struct key *key,
atomic_inc(&key->user->nikeys);
set_bit(KEY_FLAG_NEGATIVE, &key->flags);
set_bit(KEY_FLAG_INSTANTIATED, &key->flags);
+ key->type_data.reject_error = -error;
now = current_kernel_time();
key->expiry = now.tv_sec + timeout;
key_schedule_gc(key->expiry + key_gc_delay);
@@ -585,8 +589,7 @@ int key_negate_and_link(struct key *key,
return ret == 0 ? link_ret : ret;
}
-
-EXPORT_SYMBOL(key_negate_and_link);
+EXPORT_SYMBOL(key_reject_and_link);
/*
* Garbage collect keys in process context so that we don't have to disable
diff --git a/security/keys/keyctl.c b/security/keys/keyctl.c
index 31a0fd8..0d7b194 100644
--- a/security/keys/keyctl.c
+++ b/security/keys/keyctl.c
@@ -1013,12 +1013,42 @@ error:
*/
long keyctl_negate_key(key_serial_t id, unsigned timeout, key_serial_t ringid)
{
+ return keyctl_reject_key(id, timeout, ENOKEY, ringid);
+}
+
+/*
+ * Negatively instantiate the key with the given timeout (in seconds) and error
+ * code and link the key into the destination keyring if one is given.
+ *
+ * The caller must have the appropriate instantiation permit set for this to
+ * work (see keyctl_assume_authority). No other permissions are required.
+ *
+ * The key and any links to the key will be automatically garbage collected
+ * after the timeout expires.
+ *
+ * Negative keys are used to rate limit repeated request_key() calls by causing
+ * them to return the specified error code until the negative key expires.
+ *
+ * If successful, 0 will be returned.
+ */
+long keyctl_reject_key(key_serial_t id, unsigned timeout, unsigned error,
+ key_serial_t ringid)
+{
const struct cred *cred = current_cred();
struct request_key_auth *rka;
struct key *instkey, *dest_keyring;
long ret;
- kenter("%d,%u,%d", id, timeout, ringid);
+ kenter("%d,%u,%u,%d", id, timeout, error, ringid);
+
+ /* must be a valid error code and mustn't be a kernel special */
+ if (error <= 0 ||
+ error >= MAX_ERRNO ||
+ error == ERESTARTSYS ||
+ error == ERESTARTNOINTR ||
+ error == ERESTARTNOHAND ||
+ error == ERESTART_RESTARTBLOCK)
+ return -EINVAL;
/* the appropriate instantiation authorisation key must have been
* assumed before calling this */
@@ -1038,7 +1068,7 @@ long keyctl_negate_key(key_serial_t id, unsigned timeout, key_serial_t ringid)
goto error;
/* instantiate the key and link it into a keyring */
- ret = key_negate_and_link(rka->target_key, timeout,
+ ret = key_reject_and_link(rka->target_key, timeout, error,
dest_keyring, instkey);
key_put(dest_keyring);
@@ -1492,6 +1522,12 @@ SYSCALL_DEFINE5(keyctl, int, option, unsigned long, arg2, unsigned long, arg3,
case KEYCTL_SESSION_TO_PARENT:
return keyctl_session_to_parent();
+ case KEYCTL_REJECT:
+ return keyctl_reject_key((key_serial_t) arg2,
+ (unsigned) arg3,
+ (unsigned) arg4,
+ (key_serial_t) arg5);
+
default:
return -EOPNOTSUPP;
}
diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index 5620f08..cdd2f3f 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -352,7 +352,7 @@ key_ref_t keyring_search_aux(key_ref_t keyring_ref,
goto error_2;
if (key->expiry && now.tv_sec >= key->expiry)
goto error_2;
- key_ref = ERR_PTR(-ENOKEY);
+ key_ref = ERR_PTR(key->type_data.reject_error);
if (kflags & (1 << KEY_FLAG_NEGATIVE))
goto error_2;
goto found;
@@ -401,7 +401,7 @@ descend:
/* we set a different error code if we pass a negative key */
if (kflags & (1 << KEY_FLAG_NEGATIVE)) {
- err = -ENOKEY;
+ err = key->type_data.reject_error;
continue;
}
diff --git a/security/keys/request_key.c b/security/keys/request_key.c
index a3dc0d4..df3c041 100644
--- a/security/keys/request_key.c
+++ b/security/keys/request_key.c
@@ -585,7 +585,7 @@ int wait_for_key_construction(struct key *key, bool intr)
if (ret < 0)
return ret;
if (test_bit(KEY_FLAG_NEGATIVE, &key->flags))
- return -ENOKEY;
+ return key->type_data.reject_error;
return key_validate(key);
}
EXPORT_SYMBOL(wait_for_key_construction);
^ permalink raw reply related
* [PATCH 2/3] KEYS: Define an error code to indicate an authentication service was unavailable
From: David Howells @ 2011-03-03 17:49 UTC (permalink / raw)
To: linux-security-module, keyrings; +Cc: linux-kernel, netdev, David Howells
In-Reply-To: <20110303174934.21635.18601.stgit@warthog.procyon.org.uk>
As the kernel has or will have filesystems (and possibly other services) that
want to obtain authentication tokens and/or encryption data on demand (via
GSSAPI for example), it would seem useful to provide an additional error code
to indicate a problem with the lookup, rather than overloading some other error
code.
We already have EKEYREJECTED, EKEYREVOKED and EKEYEXPIRED to indicate problems
with a token that we already have, but what if the authentication server just
isn't available?
Define ENOAUTHSERVICE to indicate "Authentication service unavailable". This
can be used to indicate, for example, that an attempt was made by request_key()
to retrieve a key, but the authentication server (e.g. a KDC) it is supposed to
contact didn't answer or that it couldn't determine the location of a suitable
server.
One way this can be used is that the user of a network filesystem can get a TGT
from the KDC and stash it in their session keyring, then the filesystem can
attempt to automatically get a ticket for accessing the filesystem - but if the
server is uncontactable then the ticket can be negatively instantiated with
KEYCTL_REJECT, giving the error to be handed to future requests as
ENOAUTHSERVICE and a small timeout so that the key will expire from the cache
and allow a retry after a short while to prevent thrashing.
Signed-off-by: David Howells <dhowells@redhat.com>
---
arch/alpha/include/asm/errno.h | 1 +
arch/mips/include/asm/errno.h | 1 +
arch/parisc/include/asm/errno.h | 1 +
arch/sparc/include/asm/errno.h | 1 +
include/asm-generic/errno.h | 1 +
5 files changed, 5 insertions(+), 0 deletions(-)
diff --git a/arch/alpha/include/asm/errno.h b/arch/alpha/include/asm/errno.h
index 98099bd..519663c 100644
--- a/arch/alpha/include/asm/errno.h
+++ b/arch/alpha/include/asm/errno.h
@@ -121,5 +121,6 @@
#define ENOTRECOVERABLE 137 /* State not recoverable */
#define ERFKILL 138 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 139 /* Authentication service not available */
#endif
diff --git a/arch/mips/include/asm/errno.h b/arch/mips/include/asm/errno.h
index a0efc73..5fa7fed 100644
--- a/arch/mips/include/asm/errno.h
+++ b/arch/mips/include/asm/errno.h
@@ -120,6 +120,7 @@
#define ENOTRECOVERABLE 166 /* State not recoverable */
#define ERFKILL 167 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 168 /* Authentication service not available */
#define EDQUOT 1133 /* Quota exceeded */
diff --git a/arch/parisc/include/asm/errno.h b/arch/parisc/include/asm/errno.h
index 9992abd..6a19346 100644
--- a/arch/parisc/include/asm/errno.h
+++ b/arch/parisc/include/asm/errno.h
@@ -121,5 +121,6 @@
#define ENOTRECOVERABLE 255 /* State not recoverable */
#define ERFKILL 256 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 257 /* Authentication service not available */
#endif
diff --git a/arch/sparc/include/asm/errno.h b/arch/sparc/include/asm/errno.h
index 4e2bc49..ab3a26a 100644
--- a/arch/sparc/include/asm/errno.h
+++ b/arch/sparc/include/asm/errno.h
@@ -111,5 +111,6 @@
#define ENOTRECOVERABLE 133 /* State not recoverable */
#define ERFKILL 134 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 135 /* Authentication service not available */
#endif
diff --git a/include/asm-generic/errno.h b/include/asm-generic/errno.h
index 28cc03b..bcf1908 100644
--- a/include/asm-generic/errno.h
+++ b/include/asm-generic/errno.h
@@ -107,5 +107,6 @@
#define ENOTRECOVERABLE 131 /* State not recoverable */
#define ERFKILL 132 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 133 /* Authentication service not available */
#endif
^ permalink raw reply related
* [PATCH 3/3] KEYS: Define error codes to indicate a name service errors
From: David Howells @ 2011-03-03 17:49 UTC (permalink / raw)
To: linux-security-module, keyrings; +Cc: linux-kernel, netdev, David Howells
In-Reply-To: <20110303174934.21635.18601.stgit@warthog.procyon.org.uk>
Now that the kernel has filesystems (and possibly other services) that want to
look up internet addresses corresponding to arbitrary hostnames retrieved from
the server, it would seem useful to provide a couple of error codes to indicate
problems with the look up, rather than overloading some other error code.
Define ENONAMESERVICE to indicate "Network name service unavailable". This can
be used to indicate, for example, that an attempt was made by dns_query() to
make a query, but the name server (e.g. a DNS server) it is supposed to contact
didn't answer or that it couldn't determine the location of a suitable server.
Define ENAMEUNKNOWN to indicate "Network name unknown". This can be used to
indicate, for example, that an attempt was made by dns_query() to make a query,
but the name server (e.g. a DNS server) replied indicating that it had no
matching records.
The DNS query upcall program can report these to keyctl_reject() so that cached
failed queries will respond with these errors until they expire.
Signed-off-by: David Howells <dhowells@redhat.com>
---
arch/alpha/include/asm/errno.h | 2 ++
arch/mips/include/asm/errno.h | 2 ++
arch/parisc/include/asm/errno.h | 2 ++
arch/sparc/include/asm/errno.h | 2 ++
include/asm-generic/errno.h | 2 ++
5 files changed, 10 insertions(+), 0 deletions(-)
diff --git a/arch/alpha/include/asm/errno.h b/arch/alpha/include/asm/errno.h
index 519663c..ee8a3f0 100644
--- a/arch/alpha/include/asm/errno.h
+++ b/arch/alpha/include/asm/errno.h
@@ -122,5 +122,7 @@
#define ERFKILL 138 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 139 /* Authentication service not available */
+#define ENONAMESERVICE 140 /* Network name service unavailable */
+#define ENAMEUNKNOWN 141 /* Network name unknown */
#endif
diff --git a/arch/mips/include/asm/errno.h b/arch/mips/include/asm/errno.h
index 5fa7fed..faed965 100644
--- a/arch/mips/include/asm/errno.h
+++ b/arch/mips/include/asm/errno.h
@@ -121,6 +121,8 @@
#define ERFKILL 167 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 168 /* Authentication service not available */
+#define ENONAMESERVICE 169 /* Network name service unavailable */
+#define ENAMEUNKNOWN 170 /* Network name unknown */
#define EDQUOT 1133 /* Quota exceeded */
diff --git a/arch/parisc/include/asm/errno.h b/arch/parisc/include/asm/errno.h
index 6a19346..63ee0bc 100644
--- a/arch/parisc/include/asm/errno.h
+++ b/arch/parisc/include/asm/errno.h
@@ -122,5 +122,7 @@
#define ERFKILL 256 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 257 /* Authentication service not available */
+#define ENONAMESERVICE 258 /* Network name service unavailable */
+#define ENAMEUNKNOWN 259 /* Network name unknown */
#endif
diff --git a/arch/sparc/include/asm/errno.h b/arch/sparc/include/asm/errno.h
index ab3a26a..f40d5ae 100644
--- a/arch/sparc/include/asm/errno.h
+++ b/arch/sparc/include/asm/errno.h
@@ -112,5 +112,7 @@
#define ERFKILL 134 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 135 /* Authentication service not available */
+#define ENONAMESERVICE 136 /* Network name service unavailable */
+#define ENAMEUNKNOWN 137 /* Network name unknown */
#endif
diff --git a/include/asm-generic/errno.h b/include/asm-generic/errno.h
index bcf1908..25878f1 100644
--- a/include/asm-generic/errno.h
+++ b/include/asm-generic/errno.h
@@ -108,5 +108,7 @@
#define ERFKILL 132 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 133 /* Authentication service not available */
+#define ENONAMESERVICE 134 /* Network name service unavailable */
+#define ENAMEUNKNOWN 135 /* Network name unknown */
#endif
^ permalink raw reply related
* [PATCH 1/3] KEYS: Add a new keyctl op to reject a key with a specified error code
From: David Howells @ 2011-03-03 17:50 UTC (permalink / raw)
To: linux-security-module, keyrings
Cc: linux-kernel, netdev, linux-cifs, linux-nfs, David Howells
Add a new keyctl op to reject a key with a specified error code. This works
much the same as negating a key, and so keyctl_negate_key() is made a special
case of keyctl_reject_key(). The difference is that keyctl_negate_key()
selects ENOKEY as the error to be reported.
Typically the key would be rejected with EKEYEXPIRED, EKEYREVOKED or
EKEYREJECTED, but this is not mandatory.
Signed-off-by: David Howells <dhowells@redhat.com>
---
Documentation/keys-request-key.txt | 9 +++++---
Documentation/keys.txt | 10 +++++++--
include/linux/key-type.h | 11 +++++++++-
include/linux/key.h | 1 +
include/linux/keyctl.h | 1 +
security/keys/compat.c | 3 +++
security/keys/internal.h | 1 +
security/keys/key.c | 19 ++++++++++-------
security/keys/keyctl.c | 40 ++++++++++++++++++++++++++++++++++--
security/keys/keyring.c | 4 ++--
security/keys/request_key.c | 2 +-
11 files changed, 81 insertions(+), 20 deletions(-)
diff --git a/Documentation/keys-request-key.txt b/Documentation/keys-request-key.txt
index 09b55e4..69686ad 100644
--- a/Documentation/keys-request-key.txt
+++ b/Documentation/keys-request-key.txt
@@ -127,14 +127,15 @@ This is because process A's keyrings can't simply be attached to
of them, and (b) it requires the same UID/GID/Groups all the way through.
-======================
-NEGATIVE INSTANTIATION
-======================
+====================================
+NEGATIVE INSTANTIATION AND REJECTION
+====================================
Rather than instantiating a key, it is possible for the possessor of an
authorisation key to negatively instantiate a key that's under construction.
This is a short duration placeholder that causes any attempt at re-requesting
-the key whilst it exists to fail with error ENOKEY.
+the key whilst it exists to fail with error ENOKEY if negated or the specified
+error if rejected.
This is provided to prevent excessive repeated spawning of /sbin/request-key
processes for a key that will never be obtainable.
diff --git a/Documentation/keys.txt b/Documentation/keys.txt
index cf68d1f..a6a97fd 100644
--- a/Documentation/keys.txt
+++ b/Documentation/keys.txt
@@ -657,6 +657,8 @@ The keyctl syscall functions are:
long keyctl(KEYCTL_NEGATE, key_serial_t key,
unsigned timeout, key_serial_t keyring);
+ long keyctl(KEYCTL_REJECT, key_serial_t key,
+ unsigned timeout, unsigned error, key_serial_t keyring);
If the kernel calls back to userspace to complete the instantiation of a
key, userspace should use this call mark the key as negative before the
@@ -669,6 +671,10 @@ The keyctl syscall functions are:
that keyring, however all the constraints applying in KEYCTL_LINK apply in
this case too.
+ If the key is rejected, future searches for it will return the specified
+ error code until the rejected key expires. Negating the key is the same
+ as rejecting the key with ENOKEY as the error code.
+
(*) Set the default request-key destination keyring.
@@ -1240,8 +1246,8 @@ example, the KDE desktop manager).
The program (or whatever it calls) should finish construction of the key by
calling KEYCTL_INSTANTIATE, which also permits it to cache the key in one of
the keyrings (probably the session ring) before returning. Alternatively, the
-key can be marked as negative with KEYCTL_NEGATE; this also permits the key to
-be cached in one of the keyrings.
+key can be marked as negative with KEYCTL_NEGATE or KEYCTL_REJECT; this also
+permits the key to be cached in one of the keyrings.
If it returns with the key remaining in the unconstructed state, the key will
be marked as being negative, it will be added to the session keyring, and an
diff --git a/include/linux/key-type.h b/include/linux/key-type.h
index fc8525e8..9efd081 100644
--- a/include/linux/key-type.h
+++ b/include/linux/key-type.h
@@ -105,11 +105,20 @@ extern int key_instantiate_and_link(struct key *key,
size_t datalen,
struct key *keyring,
struct key *instkey);
-extern int key_negate_and_link(struct key *key,
+extern int key_reject_and_link(struct key *key,
unsigned timeout,
+ unsigned error,
struct key *keyring,
struct key *instkey);
extern void complete_request_key(struct key_construction *cons, int error);
+static inline int key_negate_and_link(struct key *key,
+ unsigned timeout,
+ struct key *keyring,
+ struct key *instkey)
+{
+ return key_reject_and_link(key, timeout, ENOKEY, keyring, instkey);
+}
+
#endif /* CONFIG_KEYS */
#endif /* _LINUX_KEY_TYPE_H */
diff --git a/include/linux/key.h b/include/linux/key.h
index a6b1edc..b2bb017 100644
--- a/include/linux/key.h
+++ b/include/linux/key.h
@@ -170,6 +170,7 @@ struct key {
struct list_head link;
unsigned long x[2];
void *p[2];
+ int reject_error;
} type_data;
/* key data
diff --git a/include/linux/keyctl.h b/include/linux/keyctl.h
index bd383f1..7022974 100644
--- a/include/linux/keyctl.h
+++ b/include/linux/keyctl.h
@@ -53,5 +53,6 @@
#define KEYCTL_ASSUME_AUTHORITY 16 /* assume request_key() authorisation */
#define KEYCTL_GET_SECURITY 17 /* get key security label */
#define KEYCTL_SESSION_TO_PARENT 18 /* apply session keyring to parent process */
+#define KEYCTL_REJECT 19 /* reject a partially constructed key */
#endif /* _LINUX_KEYCTL_H */
diff --git a/security/keys/compat.c b/security/keys/compat.c
index 07a5f35..17c99d0 100644
--- a/security/keys/compat.c
+++ b/security/keys/compat.c
@@ -85,6 +85,9 @@ asmlinkage long compat_sys_keyctl(u32 option,
case KEYCTL_SESSION_TO_PARENT:
return keyctl_session_to_parent();
+ case KEYCTL_REJECT:
+ return keyctl_reject_key(arg2, arg3, arg4, arg5);
+
default:
return -EOPNOTSUPP;
}
diff --git a/security/keys/internal.h b/security/keys/internal.h
index a52aa7c..286c095 100644
--- a/security/keys/internal.h
+++ b/security/keys/internal.h
@@ -214,6 +214,7 @@ extern long keyctl_assume_authority(key_serial_t);
extern long keyctl_get_security(key_serial_t keyid, char __user *buffer,
size_t buflen);
extern long keyctl_session_to_parent(void);
+extern long keyctl_reject_key(key_serial_t, unsigned, unsigned, key_serial_t);
/*
* Debugging key validation
diff --git a/security/keys/key.c b/security/keys/key.c
index 8e315ef..f7f9d93 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -511,26 +511,29 @@ int key_instantiate_and_link(struct key *key,
EXPORT_SYMBOL(key_instantiate_and_link);
/**
- * key_negate_and_link - Negatively instantiate a key and link it into the keyring.
+ * key_reject_and_link - Negatively instantiate a key and link it into the keyring.
* @key: The key to instantiate.
* @timeout: The timeout on the negative key.
+ * @error: The error to return when the key is hit.
* @keyring: Keyring to create a link in on success (or NULL).
* @authkey: The authorisation token permitting instantiation.
*
* Negatively instantiate a key that's in the uninstantiated state and, if
- * successful, set its timeout and link it in to the destination keyring if one
- * is supplied. The key and any links to the key will be automatically garbage
- * collected after the timeout expires.
+ * successful, set its timeout and stored error and link it in to the
+ * destination keyring if one is supplied. The key and any links to the key
+ * will be automatically garbage collected after the timeout expires.
*
* Negative keys are used to rate limit repeated request_key() calls by causing
- * them to return -ENOKEY until the negative key expires.
+ * them to return the stored error code (typically ENOKEY) until the negative
+ * key expires.
*
* If successful, 0 is returned, the authorisation token is revoked and anyone
* waiting for the key is woken up. If the key was already instantiated,
* -EBUSY will be returned.
*/
-int key_negate_and_link(struct key *key,
+int key_reject_and_link(struct key *key,
unsigned timeout,
+ unsigned error,
struct key *keyring,
struct key *authkey)
{
@@ -556,6 +559,7 @@ int key_negate_and_link(struct key *key,
atomic_inc(&key->user->nikeys);
set_bit(KEY_FLAG_NEGATIVE, &key->flags);
set_bit(KEY_FLAG_INSTANTIATED, &key->flags);
+ key->type_data.reject_error = -error;
now = current_kernel_time();
key->expiry = now.tv_sec + timeout;
key_schedule_gc(key->expiry + key_gc_delay);
@@ -585,8 +589,7 @@ int key_negate_and_link(struct key *key,
return ret == 0 ? link_ret : ret;
}
-
-EXPORT_SYMBOL(key_negate_and_link);
+EXPORT_SYMBOL(key_reject_and_link);
/*
* Garbage collect keys in process context so that we don't have to disable
diff --git a/security/keys/keyctl.c b/security/keys/keyctl.c
index 31a0fd8..0d7b194 100644
--- a/security/keys/keyctl.c
+++ b/security/keys/keyctl.c
@@ -1013,12 +1013,42 @@ error:
*/
long keyctl_negate_key(key_serial_t id, unsigned timeout, key_serial_t ringid)
{
+ return keyctl_reject_key(id, timeout, ENOKEY, ringid);
+}
+
+/*
+ * Negatively instantiate the key with the given timeout (in seconds) and error
+ * code and link the key into the destination keyring if one is given.
+ *
+ * The caller must have the appropriate instantiation permit set for this to
+ * work (see keyctl_assume_authority). No other permissions are required.
+ *
+ * The key and any links to the key will be automatically garbage collected
+ * after the timeout expires.
+ *
+ * Negative keys are used to rate limit repeated request_key() calls by causing
+ * them to return the specified error code until the negative key expires.
+ *
+ * If successful, 0 will be returned.
+ */
+long keyctl_reject_key(key_serial_t id, unsigned timeout, unsigned error,
+ key_serial_t ringid)
+{
const struct cred *cred = current_cred();
struct request_key_auth *rka;
struct key *instkey, *dest_keyring;
long ret;
- kenter("%d,%u,%d", id, timeout, ringid);
+ kenter("%d,%u,%u,%d", id, timeout, error, ringid);
+
+ /* must be a valid error code and mustn't be a kernel special */
+ if (error <= 0 ||
+ error >= MAX_ERRNO ||
+ error == ERESTARTSYS ||
+ error == ERESTARTNOINTR ||
+ error == ERESTARTNOHAND ||
+ error == ERESTART_RESTARTBLOCK)
+ return -EINVAL;
/* the appropriate instantiation authorisation key must have been
* assumed before calling this */
@@ -1038,7 +1068,7 @@ long keyctl_negate_key(key_serial_t id, unsigned timeout, key_serial_t ringid)
goto error;
/* instantiate the key and link it into a keyring */
- ret = key_negate_and_link(rka->target_key, timeout,
+ ret = key_reject_and_link(rka->target_key, timeout, error,
dest_keyring, instkey);
key_put(dest_keyring);
@@ -1492,6 +1522,12 @@ SYSCALL_DEFINE5(keyctl, int, option, unsigned long, arg2, unsigned long, arg3,
case KEYCTL_SESSION_TO_PARENT:
return keyctl_session_to_parent();
+ case KEYCTL_REJECT:
+ return keyctl_reject_key((key_serial_t) arg2,
+ (unsigned) arg3,
+ (unsigned) arg4,
+ (key_serial_t) arg5);
+
default:
return -EOPNOTSUPP;
}
diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index 5620f08..cdd2f3f 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -352,7 +352,7 @@ key_ref_t keyring_search_aux(key_ref_t keyring_ref,
goto error_2;
if (key->expiry && now.tv_sec >= key->expiry)
goto error_2;
- key_ref = ERR_PTR(-ENOKEY);
+ key_ref = ERR_PTR(key->type_data.reject_error);
if (kflags & (1 << KEY_FLAG_NEGATIVE))
goto error_2;
goto found;
@@ -401,7 +401,7 @@ descend:
/* we set a different error code if we pass a negative key */
if (kflags & (1 << KEY_FLAG_NEGATIVE)) {
- err = -ENOKEY;
+ err = key->type_data.reject_error;
continue;
}
diff --git a/security/keys/request_key.c b/security/keys/request_key.c
index a3dc0d4..df3c041 100644
--- a/security/keys/request_key.c
+++ b/security/keys/request_key.c
@@ -585,7 +585,7 @@ int wait_for_key_construction(struct key *key, bool intr)
if (ret < 0)
return ret;
if (test_bit(KEY_FLAG_NEGATIVE, &key->flags))
- return -ENOKEY;
+ return key->type_data.reject_error;
return key_validate(key);
}
EXPORT_SYMBOL(wait_for_key_construction);
^ permalink raw reply related
* [PATCH 2/3] KEYS: Define an error code to indicate an authentication service was unavailable
From: David Howells @ 2011-03-03 17:50 UTC (permalink / raw)
To: linux-security-module, keyrings
Cc: linux-kernel, netdev, linux-cifs, linux-nfs, David Howells
In-Reply-To: <20110303175030.21702.31104.stgit@warthog.procyon.org.uk>
As the kernel has or will have filesystems (and possibly other services) that
want to obtain authentication tokens and/or encryption data on demand (via
GSSAPI for example), it would seem useful to provide an additional error code
to indicate a problem with the lookup, rather than overloading some other error
code.
We already have EKEYREJECTED, EKEYREVOKED and EKEYEXPIRED to indicate problems
with a token that we already have, but what if the authentication server just
isn't available?
Define ENOAUTHSERVICE to indicate "Authentication service unavailable". This
can be used to indicate, for example, that an attempt was made by request_key()
to retrieve a key, but the authentication server (e.g. a KDC) it is supposed to
contact didn't answer or that it couldn't determine the location of a suitable
server.
One way this can be used is that the user of a network filesystem can get a TGT
from the KDC and stash it in their session keyring, then the filesystem can
attempt to automatically get a ticket for accessing the filesystem - but if the
server is uncontactable then the ticket can be negatively instantiated with
KEYCTL_REJECT, giving the error to be handed to future requests as
ENOAUTHSERVICE and a small timeout so that the key will expire from the cache
and allow a retry after a short while to prevent thrashing.
Signed-off-by: David Howells <dhowells@redhat.com>
---
arch/alpha/include/asm/errno.h | 1 +
arch/mips/include/asm/errno.h | 1 +
arch/parisc/include/asm/errno.h | 1 +
arch/sparc/include/asm/errno.h | 1 +
include/asm-generic/errno.h | 1 +
5 files changed, 5 insertions(+), 0 deletions(-)
diff --git a/arch/alpha/include/asm/errno.h b/arch/alpha/include/asm/errno.h
index 98099bd..519663c 100644
--- a/arch/alpha/include/asm/errno.h
+++ b/arch/alpha/include/asm/errno.h
@@ -121,5 +121,6 @@
#define ENOTRECOVERABLE 137 /* State not recoverable */
#define ERFKILL 138 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 139 /* Authentication service not available */
#endif
diff --git a/arch/mips/include/asm/errno.h b/arch/mips/include/asm/errno.h
index a0efc73..5fa7fed 100644
--- a/arch/mips/include/asm/errno.h
+++ b/arch/mips/include/asm/errno.h
@@ -120,6 +120,7 @@
#define ENOTRECOVERABLE 166 /* State not recoverable */
#define ERFKILL 167 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 168 /* Authentication service not available */
#define EDQUOT 1133 /* Quota exceeded */
diff --git a/arch/parisc/include/asm/errno.h b/arch/parisc/include/asm/errno.h
index 9992abd..6a19346 100644
--- a/arch/parisc/include/asm/errno.h
+++ b/arch/parisc/include/asm/errno.h
@@ -121,5 +121,6 @@
#define ENOTRECOVERABLE 255 /* State not recoverable */
#define ERFKILL 256 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 257 /* Authentication service not available */
#endif
diff --git a/arch/sparc/include/asm/errno.h b/arch/sparc/include/asm/errno.h
index 4e2bc49..ab3a26a 100644
--- a/arch/sparc/include/asm/errno.h
+++ b/arch/sparc/include/asm/errno.h
@@ -111,5 +111,6 @@
#define ENOTRECOVERABLE 133 /* State not recoverable */
#define ERFKILL 134 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 135 /* Authentication service not available */
#endif
diff --git a/include/asm-generic/errno.h b/include/asm-generic/errno.h
index 28cc03b..bcf1908 100644
--- a/include/asm-generic/errno.h
+++ b/include/asm-generic/errno.h
@@ -107,5 +107,6 @@
#define ENOTRECOVERABLE 131 /* State not recoverable */
#define ERFKILL 132 /* Operation not possible due to RF-kill */
+#define ENOAUTHSERVICE 133 /* Authentication service not available */
#endif
^ permalink raw reply related
* [PATCH 3/3] KEYS: Define error codes to indicate a name service errors
From: David Howells @ 2011-03-03 17:50 UTC (permalink / raw)
To: linux-security-module, keyrings
Cc: linux-kernel, netdev, linux-cifs, linux-nfs, David Howells
In-Reply-To: <20110303175030.21702.31104.stgit@warthog.procyon.org.uk>
Now that the kernel has filesystems (and possibly other services) that want to
look up internet addresses corresponding to arbitrary hostnames retrieved from
the server, it would seem useful to provide a couple of error codes to indicate
problems with the look up, rather than overloading some other error code.
Define ENONAMESERVICE to indicate "Network name service unavailable". This can
be used to indicate, for example, that an attempt was made by dns_query() to
make a query, but the name server (e.g. a DNS server) it is supposed to contact
didn't answer or that it couldn't determine the location of a suitable server.
Define ENAMEUNKNOWN to indicate "Network name unknown". This can be used to
indicate, for example, that an attempt was made by dns_query() to make a query,
but the name server (e.g. a DNS server) replied indicating that it had no
matching records.
The DNS query upcall program can report these to keyctl_reject() so that cached
failed queries will respond with these errors until they expire.
Signed-off-by: David Howells <dhowells@redhat.com>
---
arch/alpha/include/asm/errno.h | 2 ++
arch/mips/include/asm/errno.h | 2 ++
arch/parisc/include/asm/errno.h | 2 ++
arch/sparc/include/asm/errno.h | 2 ++
include/asm-generic/errno.h | 2 ++
5 files changed, 10 insertions(+), 0 deletions(-)
diff --git a/arch/alpha/include/asm/errno.h b/arch/alpha/include/asm/errno.h
index 519663c..ee8a3f0 100644
--- a/arch/alpha/include/asm/errno.h
+++ b/arch/alpha/include/asm/errno.h
@@ -122,5 +122,7 @@
#define ERFKILL 138 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 139 /* Authentication service not available */
+#define ENONAMESERVICE 140 /* Network name service unavailable */
+#define ENAMEUNKNOWN 141 /* Network name unknown */
#endif
diff --git a/arch/mips/include/asm/errno.h b/arch/mips/include/asm/errno.h
index 5fa7fed..faed965 100644
--- a/arch/mips/include/asm/errno.h
+++ b/arch/mips/include/asm/errno.h
@@ -121,6 +121,8 @@
#define ERFKILL 167 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 168 /* Authentication service not available */
+#define ENONAMESERVICE 169 /* Network name service unavailable */
+#define ENAMEUNKNOWN 170 /* Network name unknown */
#define EDQUOT 1133 /* Quota exceeded */
diff --git a/arch/parisc/include/asm/errno.h b/arch/parisc/include/asm/errno.h
index 6a19346..63ee0bc 100644
--- a/arch/parisc/include/asm/errno.h
+++ b/arch/parisc/include/asm/errno.h
@@ -122,5 +122,7 @@
#define ERFKILL 256 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 257 /* Authentication service not available */
+#define ENONAMESERVICE 258 /* Network name service unavailable */
+#define ENAMEUNKNOWN 259 /* Network name unknown */
#endif
diff --git a/arch/sparc/include/asm/errno.h b/arch/sparc/include/asm/errno.h
index ab3a26a..f40d5ae 100644
--- a/arch/sparc/include/asm/errno.h
+++ b/arch/sparc/include/asm/errno.h
@@ -112,5 +112,7 @@
#define ERFKILL 134 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 135 /* Authentication service not available */
+#define ENONAMESERVICE 136 /* Network name service unavailable */
+#define ENAMEUNKNOWN 137 /* Network name unknown */
#endif
diff --git a/include/asm-generic/errno.h b/include/asm-generic/errno.h
index bcf1908..25878f1 100644
--- a/include/asm-generic/errno.h
+++ b/include/asm-generic/errno.h
@@ -108,5 +108,7 @@
#define ERFKILL 132 /* Operation not possible due to RF-kill */
#define ENOAUTHSERVICE 133 /* Authentication service not available */
+#define ENONAMESERVICE 134 /* Network name service unavailable */
+#define ENAMEUNKNOWN 135 /* Network name unknown */
#endif
^ permalink raw reply related
* Re: [PATCH 1/3] KEYS: Add a new keyctl op to reject a key with a specified error code
From: David Howells @ 2011-03-03 17:53 UTC (permalink / raw)
Cc: dhowells, linux-security-module, keyrings, linux-kernel, netdev
In-Reply-To: <20110303174934.21635.18601.stgit@warthog.procyon.org.uk>
Reposted with a wider readership.
David
^ permalink raw reply
* [PATCH] sched: QFQ - quick fair queue scheduler (v3)
From: Stephen Hemminger @ 2011-03-03 16:48 UTC (permalink / raw)
To: Eric Dumazet; +Cc: David Miller, Fabio Checconi, Luigi Rizzo, netdev
In-Reply-To: <1299168235.2983.116.camel@edumazet-laptop>
This is an implementation of the Quick Fair Queue scheduler developed
by Fabio Checconi. The same algorithm is already implemented in ipfw
in FreeBSD. Fabio had an earlier version developed on Linux, I just
cleaned it up. Thanks to Eric Dumazet for doing the testing and
finding bugs.
Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
---
v3 - bug fixes found by Eric
include/linux/pkt_sched.h | 15
net/sched/Kconfig | 11
net/sched/Makefile | 1
net/sched/sch_qfq.c | 1125 ++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 1152 insertions(+)
--- a/include/linux/pkt_sched.h 2011-03-03 08:19:39.017999002 -0800
+++ b/include/linux/pkt_sched.h 2011-03-03 08:42:17.622145451 -0800
@@ -588,4 +588,19 @@ struct tc_sfb_xstats {
#define SFB_MAX_PROB 0xFFFF
+/* QFQ */
+enum {
+ TCA_QFQ_UNSPEC,
+ TCA_QFQ_WEIGHT,
+ TCA_QFQ_LMAX,
+ __TCA_QFQ_MAX
+};
+
+#define TCA_QFQ_MAX (__TCA_QFQ_MAX - 1)
+
+struct tc_qfq_stats {
+ __u32 weight;
+ __u32 lmax;
+};
+
#endif
--- a/net/sched/Kconfig 2011-03-03 08:19:39.025999323 -0800
+++ b/net/sched/Kconfig 2011-03-03 08:34:00.215849781 -0800
@@ -239,6 +239,17 @@ config NET_SCH_CHOKE
To compile this code as a module, choose M here: the
module will be called sch_choke.
+config NET_SCH_QFQ
+ tristate "Quick Fair Queueing scheduler (QFQ)"
+ help
+ Say Y here if you want to use the Quick Fair Queueing Scheduler (QFQ)
+ packet scheduling algorithm.
+
+ To compile this driver as a module, choose M here: the module
+ will be called sch_qfq.
+
+ If unsure, say N.
+
config NET_SCH_INGRESS
tristate "Ingress Qdisc"
depends on NET_CLS_ACT
--- a/net/sched/Makefile 2011-03-03 08:19:39.033999645 -0800
+++ b/net/sched/Makefile 2011-03-03 08:34:00.215849781 -0800
@@ -35,6 +35,7 @@ obj-$(CONFIG_NET_SCH_NETEM) += sch_netem
obj-$(CONFIG_NET_SCH_DRR) += sch_drr.o
obj-$(CONFIG_NET_SCH_MQPRIO) += sch_mqprio.o
obj-$(CONFIG_NET_SCH_CHOKE) += sch_choke.o
+obj-$(CONFIG_NET_SCH_QFQ) += sch_qfq.o
obj-$(CONFIG_NET_CLS_U32) += cls_u32.o
obj-$(CONFIG_NET_CLS_ROUTE4) += cls_route.o
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ b/net/sched/sch_qfq.c 2011-03-03 08:38:25.141469408 -0800
@@ -0,0 +1,1125 @@
+/*
+ * net/sched/sch_qfq.c Quick Fair Queueing Scheduler.
+ *
+ * Copyright (c) 2009 Fabio Checconi, Luigi Rizzo, and Paolo Valente.
+ *
+ * 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/init.h>
+#include <linux/bitops.h>
+#include <linux/errno.h>
+#include <linux/netdevice.h>
+#include <linux/pkt_sched.h>
+#include <net/sch_generic.h>
+#include <net/pkt_sched.h>
+#include <net/pkt_cls.h>
+
+
+/* Quick Fair Queueing
+ ===================
+
+ Sources:
+ Fabio Checconi and Scuola Superiore and S. Anna
+ and Paolo Valente and Luigi Riz "QFQ: Efficient Packet Scheduling
+ with Tight Bandwidth Distribution Guarantees"
+
+ See also:
+ http://retis.sssup.it/~fabio/linux/qfq/
+ */
+
+/*
+
+ Virtual time computations.
+
+ S, F and V are all computed in fixed point arithmetic with
+ FRAC_BITS decimal bits.
+
+ QFQ_MAX_INDEX is the maximum index allowed for a group. We need
+ one bit per index.
+ QFQ_MAX_WSHIFT is the maximum power of two supported as a weight.
+
+ The layout of the bits is as below:
+
+ [ MTU_SHIFT ][ FRAC_BITS ]
+ [ MAX_INDEX ][ MIN_SLOT_SHIFT ]
+ ^.__grp->index = 0
+ *.__grp->slot_shift
+
+ where MIN_SLOT_SHIFT is derived by difference from the others.
+
+ The max group index corresponds to Lmax/w_min, where
+ Lmax=1<<MTU_SHIFT, w_min = 1 .
+ From this, and knowing how many groups (MAX_INDEX) we want,
+ we can derive the shift corresponding to each group.
+
+ Because we often need to compute
+ F = S + len/w_i and V = V + len/wsum
+ instead of storing w_i store the value
+ inv_w = (1<<FRAC_BITS)/w_i
+ so we can do F = S + len * inv_w * wsum.
+ We use W_TOT in the formulas so we can easily move between
+ static and adaptive weight sum.
+
+ The per-scheduler-instance data contain all the data structures
+ for the scheduler: bitmaps and bucket lists.
+
+ */
+
+/*
+ * Maximum number of consecutive slots occupied by backlogged classes
+ * inside a group.
+ */
+#define QFQ_MAX_SLOTS 32
+
+/*
+ * Shifts used for class<->group mapping. We allow class weights that are
+ * in the range [1, 2^MAX_WSHIFT], and we try to map each class i to the
+ * group with the smallest index that can support the L_i / r_i configured
+ * for the class.
+ *
+ * grp->index is the index of the group; and grp->slot_shift
+ * is the shift for the corresponding (scaled) sigma_i.
+ */
+#define QFQ_MAX_INDEX 19
+#define QFQ_MAX_WSHIFT 16
+
+#define QFQ_MAX_WEIGHT (1<<QFQ_MAX_WSHIFT)
+#define QFQ_MAX_WSUM (2*QFQ_MAX_WEIGHT)
+
+#define FRAC_BITS 30 /* fixed point arithmetic */
+#define ONE_FP (1UL << FRAC_BITS)
+#define IWSUM (ONE_FP/QFQ_MAX_WSUM)
+
+#define QFQ_MTU_SHIFT 11
+#define QFQ_MIN_SLOT_SHIFT (FRAC_BITS + QFQ_MTU_SHIFT - QFQ_MAX_INDEX)
+
+/*
+ * Possible group states. These values are used as indexes for the bitmaps
+ * array of struct qfq_queue.
+ */
+enum qfq_state { ER, IR, EB, IB, QFQ_MAX_STATE };
+
+struct qfq_group;
+
+struct qfq_class {
+ struct Qdisc_class_common common;
+
+ unsigned int refcnt;
+ unsigned int filter_cnt;
+
+ struct gnet_stats_basic_packed bstats;
+ struct gnet_stats_queue qstats;
+ struct gnet_stats_rate_est rate_est;
+ struct Qdisc *qdisc;
+
+ struct qfq_class *next; /* Link for the slot list. */
+ u64 S, F; /* flow timestamps (exact) */
+
+ /* group we belong to. In principle we would need the index,
+ * which is log_2(lmax/weight), but we never reference it
+ * directly, only the group.
+ */
+ struct qfq_group *grp;
+
+ /* these are copied from the flowset. */
+ u32 inv_w; /* ONE_FP/weight */
+ u32 lmax; /* Max packet size for this flow. */
+};
+
+struct qfq_group {
+ u64 S, F; /* group timestamps (approx). */
+ unsigned int slot_shift; /* Slot shift. */
+ unsigned int index; /* Group index. */
+ unsigned int front; /* Index of the front slot. */
+ unsigned long full_slots; /* non-empty slots */
+
+ /* Array of RR lists of active classes. */
+ struct qfq_class *slots[QFQ_MAX_SLOTS];
+};
+
+struct qfq_sched {
+ struct tcf_proto *filter_list;
+ struct Qdisc_class_hash clhash;
+
+ u64 V; /* Precise virtual time. */
+ u32 wsum; /* weight sum */
+
+ unsigned long bitmaps[QFQ_MAX_STATE]; /* Group bitmaps. */
+ struct qfq_group groups[QFQ_MAX_INDEX + 1]; /* The groups. */
+};
+
+static struct qfq_class *qfq_find_class(struct Qdisc *sch, u32 classid)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct Qdisc_class_common *clc;
+
+ clc = qdisc_class_find(&q->clhash, classid);
+ if (clc == NULL)
+ return NULL;
+ return container_of(clc, struct qfq_class, common);
+}
+
+static void qfq_purge_queue(struct qfq_class *cl)
+{
+ unsigned int len = cl->qdisc->q.qlen;
+
+ qdisc_reset(cl->qdisc);
+ qdisc_tree_decrease_qlen(cl->qdisc, len);
+}
+
+static const struct nla_policy qfq_policy[TCA_QFQ_MAX + 1] = {
+ [TCA_QFQ_WEIGHT] = { .type = NLA_U32 },
+ [TCA_QFQ_LMAX] = { .type = NLA_U32 },
+};
+
+/*
+ * Calculate a flow index, given its weight and maximum packet length.
+ * index = log_2(maxlen/weight) but we need to apply the scaling.
+ * This is used only once at flow creation.
+ */
+static int qfq_calc_index(u32 inv_w, unsigned int maxlen)
+{
+ u64 slot_size = (u64)maxlen * inv_w;
+ unsigned long size_map;
+ int index = 0;
+
+ size_map = slot_size >> QFQ_MIN_SLOT_SHIFT;
+ if (!size_map)
+ goto out;
+
+ index = __fls(size_map) + 1; /* basically a log_2 */
+ index -= !(slot_size - (1ULL << (index + QFQ_MIN_SLOT_SHIFT - 1)));
+
+ if (index < 0)
+ index = 0;
+out:
+ pr_debug("qfq calc_index: W = %lu, L = %u, I = %d\n",
+ (unsigned long) ONE_FP/inv_w, maxlen, index);
+
+ return index;
+}
+
+static int qfq_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
+ struct nlattr **tca, unsigned long *arg)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_class *cl = (struct qfq_class *)*arg;
+ struct nlattr *tb[TCA_QFQ_MAX + 1];
+ u32 weight, lmax, inv_w;
+ int i, err;
+
+ if (tca[TCA_OPTIONS] == NULL)
+ return -EINVAL;
+
+ err = nla_parse_nested(tb, TCA_QFQ_MAX, tca[TCA_OPTIONS], qfq_policy);
+ if (err < 0)
+ return err;
+
+ if (tb[TCA_QFQ_WEIGHT]) {
+ weight = nla_get_u32(tb[TCA_QFQ_WEIGHT]);
+ if (!weight || weight > (1UL << QFQ_MAX_WSHIFT)) {
+ pr_notice("qfq: invalid weight %u\n", weight);
+ return -EINVAL;
+ }
+ } else
+ weight = 1;
+
+ inv_w = ONE_FP / weight;
+ weight = ONE_FP / inv_w;
+ if (q->wsum + weight > QFQ_MAX_WSUM) {
+ pr_notice("qfq: total weight out of range (%u + %u)\n",
+ weight, q->wsum);
+ return -EINVAL;
+ }
+
+ if (tb[TCA_QFQ_LMAX]) {
+ lmax = nla_get_u32(tb[TCA_QFQ_LMAX]);
+ if (!lmax || lmax > (1UL << QFQ_MTU_SHIFT)) {
+ pr_notice("qfq: invalid max length %u\n", lmax);
+ return -EINVAL;
+ }
+ } else
+ lmax = 1UL << QFQ_MTU_SHIFT;
+
+ if (cl != NULL) {
+ if (tca[TCA_RATE]) {
+ err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
+ qdisc_root_sleeping_lock(sch),
+ tca[TCA_RATE]);
+ if (err)
+ return err;
+ }
+
+ sch_tree_lock(sch);
+ if (tb[TCA_QFQ_WEIGHT]) {
+ q->wsum = weight - ONE_FP / cl->inv_w;
+ cl->inv_w = inv_w;
+ }
+ sch_tree_unlock(sch);
+
+ return 0;
+ }
+
+ cl = kzalloc(sizeof(struct qfq_class), GFP_KERNEL);
+ if (cl == NULL)
+ return -ENOBUFS;
+
+ cl->refcnt = 1;
+ cl->common.classid = classid;
+ cl->lmax = lmax;
+ cl->inv_w = inv_w;
+ i = qfq_calc_index(cl->inv_w, cl->lmax);
+
+ cl->grp = &q->groups[i];
+ q->wsum += weight;
+
+ cl->qdisc = qdisc_create_dflt(sch->dev_queue,
+ &pfifo_qdisc_ops, classid);
+ if (cl->qdisc == NULL)
+ cl->qdisc = &noop_qdisc;
+
+ if (tca[TCA_RATE]) {
+ err = gen_new_estimator(&cl->bstats, &cl->rate_est,
+ qdisc_root_sleeping_lock(sch),
+ tca[TCA_RATE]);
+ if (err) {
+ qdisc_destroy(cl->qdisc);
+ kfree(cl);
+ return err;
+ }
+ }
+
+ sch_tree_lock(sch);
+ qdisc_class_hash_insert(&q->clhash, &cl->common);
+ sch_tree_unlock(sch);
+
+ qdisc_class_hash_grow(sch, &q->clhash);
+
+ *arg = (unsigned long)cl;
+ return 0;
+}
+
+static void qfq_destroy_class(struct Qdisc *sch, struct qfq_class *cl)
+{
+ struct qfq_sched *q = sched_priv(sch);
+
+ if (cl->inv_w) {
+ q->wsum -= ONE_FP / cl->inv_w;
+ cl->inv_w = 0;
+ }
+
+ gen_kill_estimator(&cl->bstats, &cl->rate_est);
+ qdisc_destroy(cl->qdisc);
+ kfree(cl);
+}
+
+static int qfq_delete_class(struct Qdisc *sch, unsigned long arg)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_class *cl = (struct qfq_class *)arg;
+
+ if (cl->filter_cnt > 0)
+ return -EBUSY;
+
+ sch_tree_lock(sch);
+
+ qfq_purge_queue(cl);
+ qdisc_class_hash_remove(&q->clhash, &cl->common);
+
+ if (--cl->refcnt == 0)
+ qfq_destroy_class(sch, cl);
+
+ sch_tree_unlock(sch);
+ return 0;
+}
+
+static unsigned long qfq_get_class(struct Qdisc *sch, u32 classid)
+{
+ struct qfq_class *cl = qfq_find_class(sch, classid);
+
+ if (cl != NULL)
+ cl->refcnt++;
+
+ return (unsigned long)cl;
+}
+
+static void qfq_put_class(struct Qdisc *sch, unsigned long arg)
+{
+ struct qfq_class *cl = (struct qfq_class *)arg;
+
+ if (--cl->refcnt == 0)
+ qfq_destroy_class(sch, cl);
+}
+
+static struct tcf_proto **qfq_tcf_chain(struct Qdisc *sch, unsigned long cl)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+
+ if (cl)
+ return NULL;
+
+ return &q->filter_list;
+}
+
+static unsigned long qfq_bind_tcf(struct Qdisc *sch, unsigned long parent,
+ u32 classid)
+{
+ struct qfq_class *cl = qfq_find_class(sch, classid);
+
+ if (cl != NULL)
+ cl->filter_cnt++;
+
+ return (unsigned long)cl;
+}
+
+static void qfq_unbind_tcf(struct Qdisc *sch, unsigned long arg)
+{
+ struct qfq_class *cl = (struct qfq_class *)arg;
+
+ cl->filter_cnt--;
+}
+
+static int qfq_graft_class(struct Qdisc *sch, unsigned long arg,
+ struct Qdisc *new, struct Qdisc **old)
+{
+ struct qfq_class *cl = (struct qfq_class *)arg;
+
+ if (new == NULL) {
+ new = qdisc_create_dflt(sch->dev_queue,
+ &pfifo_qdisc_ops, cl->common.classid);
+ if (new == NULL)
+ new = &noop_qdisc;
+ }
+
+ sch_tree_lock(sch);
+ qfq_purge_queue(cl);
+ *old = cl->qdisc;
+ cl->qdisc = new;
+ sch_tree_unlock(sch);
+ return 0;
+}
+
+static struct Qdisc *qfq_class_leaf(struct Qdisc *sch, unsigned long arg)
+{
+ struct qfq_class *cl = (struct qfq_class *)arg;
+
+ return cl->qdisc;
+}
+
+static int qfq_dump_class(struct Qdisc *sch, unsigned long arg,
+ struct sk_buff *skb, struct tcmsg *tcm)
+{
+ struct qfq_class *cl = (struct qfq_class *)arg;
+ struct nlattr *nest;
+
+ tcm->tcm_parent = TC_H_ROOT;
+ tcm->tcm_handle = cl->common.classid;
+ tcm->tcm_info = cl->qdisc->handle;
+
+ nest = nla_nest_start(skb, TCA_OPTIONS);
+ if (nest == NULL)
+ goto nla_put_failure;
+ NLA_PUT_U32(skb, TCA_QFQ_WEIGHT, ONE_FP/cl->inv_w);
+ NLA_PUT_U32(skb, TCA_QFQ_LMAX, cl->lmax);
+ return nla_nest_end(skb, nest);
+
+nla_put_failure:
+ nla_nest_cancel(skb, nest);
+ return -EMSGSIZE;
+}
+
+static int qfq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
+ struct gnet_dump *d)
+{
+ struct qfq_class *cl = (struct qfq_class *)arg;
+ struct tc_qfq_stats xstats;
+
+ memset(&xstats, 0, sizeof(xstats));
+ cl->qdisc->qstats.qlen = cl->qdisc->q.qlen;
+
+ xstats.weight = ONE_FP/cl->inv_w;
+ xstats.lmax = cl->lmax;
+
+ if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
+ gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 ||
+ gnet_stats_copy_queue(d, &cl->qdisc->qstats) < 0)
+ return -1;
+
+ return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
+}
+
+static void qfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_class *cl;
+ struct hlist_node *n;
+ unsigned int i;
+
+ if (arg->stop)
+ return;
+
+ for (i = 0; i < q->clhash.hashsize; i++) {
+ hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
+ if (arg->count < arg->skip) {
+ arg->count++;
+ continue;
+ }
+ if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
+ arg->stop = 1;
+ return;
+ }
+ arg->count++;
+ }
+ }
+}
+
+static struct qfq_class *qfq_classify(struct sk_buff *skb, struct Qdisc *sch,
+ int *qerr)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_class *cl;
+ struct tcf_result res;
+ int result;
+
+ if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) {
+ pr_debug("qfq_classify: found %d\n", skb->priority);
+ cl = qfq_find_class(sch, skb->priority);
+ if (cl != NULL)
+ return cl;
+ }
+
+ *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
+ result = tc_classify(skb, q->filter_list, &res);
+ if (result >= 0) {
+#ifdef CONFIG_NET_CLS_ACT
+ switch (result) {
+ case TC_ACT_QUEUED:
+ case TC_ACT_STOLEN:
+ *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
+ case TC_ACT_SHOT:
+ return NULL;
+ }
+#endif
+ cl = (struct qfq_class *)res.class;
+ if (cl == NULL)
+ cl = qfq_find_class(sch, res.classid);
+ return cl;
+ }
+
+ return NULL;
+}
+
+/* Generic comparison function, handling wraparound. */
+static inline int qfq_gt(u64 a, u64 b)
+{
+ return (s64)(a - b) > 0;
+}
+
+/* Round a precise timestamp to its slotted value. */
+static inline u64 qfq_round_down(u64 ts, unsigned int shift)
+{
+ return ts & ~((1ULL << shift) - 1);
+}
+
+/* return the pointer to the group with lowest index in the bitmap */
+static inline struct qfq_group *qfq_ffs(struct qfq_sched *q,
+ unsigned long bitmap)
+{
+ int index = __ffs(bitmap);
+ return &q->groups[index];
+}
+/* Calculate a mask to mimic what would be ffs_from(). */
+static inline unsigned long mask_from(unsigned long bitmap, int from)
+{
+ return bitmap & ~((1UL << from) - 1);
+}
+
+/*
+ * The state computation relies on ER=0, IR=1, EB=2, IB=3
+ * First compute eligibility comparing grp->S, q->V,
+ * then check if someone is blocking us and possibly add EB
+ */
+static int qfq_calc_state(struct qfq_sched *q, const struct qfq_group *grp)
+{
+ /* if S > V we are not eligible */
+ unsigned int state = qfq_gt(grp->S, q->V);
+ unsigned long mask = mask_from(q->bitmaps[ER], grp->index);
+ struct qfq_group *next;
+
+ if (mask) {
+ next = qfq_ffs(q, mask);
+ if (qfq_gt(grp->F, next->F))
+ state |= EB;
+ }
+
+ return state;
+}
+
+
+/*
+ * In principle
+ * q->bitmaps[dst] |= q->bitmaps[src] & mask;
+ * q->bitmaps[src] &= ~mask;
+ * but we should make sure that src != dst
+ */
+static inline void qfq_move_groups(struct qfq_sched *q, unsigned long mask,
+ int src, int dst)
+{
+ q->bitmaps[dst] |= q->bitmaps[src] & mask;
+ q->bitmaps[src] &= ~mask;
+}
+
+static void qfq_unblock_groups(struct qfq_sched *q, int index, u64 old_F)
+{
+ unsigned long mask = mask_from(q->bitmaps[ER], index + 1);
+ struct qfq_group *next;
+
+ if (mask) {
+ next = qfq_ffs(q, mask);
+ if (!qfq_gt(next->F, old_F))
+ return;
+ }
+
+ mask = (1UL << index) - 1;
+ qfq_move_groups(q, mask, EB, ER);
+ qfq_move_groups(q, mask, IB, IR);
+}
+
+/*
+ * perhaps
+ *
+ old_V ^= q->V;
+ old_V >>= QFQ_MIN_SLOT_SHIFT;
+ if (old_V) {
+ ...
+ }
+ *
+ */
+static void qfq_make_eligible(struct qfq_sched *q, u64 old_V)
+{
+ unsigned long vslot = q->V >> QFQ_MIN_SLOT_SHIFT;
+ unsigned long old_vslot = old_V >> QFQ_MIN_SLOT_SHIFT;
+
+ if (vslot != old_vslot) {
+ unsigned long mask = (1UL << fls(vslot ^ old_vslot)) - 1;
+ qfq_move_groups(q, mask, IR, ER);
+ qfq_move_groups(q, mask, IB, EB);
+ }
+}
+
+/*
+ * XXX we should make sure that slot becomes less than 32.
+ * This is guaranteed by the input values.
+ * roundedS is always cl->S rounded on grp->slot_shift bits.
+ */
+static void qfq_slot_insert(struct qfq_group *grp, struct qfq_class *cl,
+ u64 roundedS)
+{
+ u64 slot = (roundedS - grp->S) >> grp->slot_shift;
+ unsigned int i = (grp->front + slot) % QFQ_MAX_SLOTS;
+
+ cl->next = grp->slots[i];
+ grp->slots[i] = cl;
+ __set_bit(slot, &grp->full_slots);
+}
+
+/*
+ * remove the entry from the slot
+ */
+static void qfq_front_slot_remove(struct qfq_group *grp)
+{
+ struct qfq_class **h = &grp->slots[grp->front];
+
+ *h = (*h)->next;
+ if (!*h)
+ __clear_bit(0, &grp->full_slots);
+}
+
+/*
+ * Returns the first full queue in a group. As a side effect,
+ * adjust the bucket list so the first non-empty bucket is at
+ * position 0 in full_slots.
+ */
+static struct qfq_class *qfq_slot_scan(struct qfq_group *grp)
+{
+ unsigned int i;
+
+ pr_debug("qfq slot_scan: grp %u full %#lx\n",
+ grp->index, grp->full_slots);
+
+ if (grp->full_slots == 0)
+ return NULL;
+
+ i = __ffs(grp->full_slots); /* zero based */
+ if (i > 0) {
+ grp->front = (grp->front + i) % QFQ_MAX_SLOTS;
+ grp->full_slots >>= i;
+ }
+
+ return grp->slots[grp->front];
+}
+
+/*
+ * adjust the bucket list. When the start time of a group decreases,
+ * we move the index down (modulo QFQ_MAX_SLOTS) so we don't need to
+ * move the objects. The mask of occupied slots must be shifted
+ * because we use ffs() to find the first non-empty slot.
+ * This covers decreases in the group's start time, but what about
+ * increases of the start time ?
+ * Here too we should make sure that i is less than 32
+ */
+static void qfq_slot_rotate(struct qfq_group *grp, u64 roundedS)
+{
+ unsigned int i = (grp->S - roundedS) >> grp->slot_shift;
+
+ grp->full_slots <<= i;
+ grp->front = (grp->front - i) % QFQ_MAX_SLOTS;
+}
+
+static void qfq_update_eligible(struct qfq_sched *q, u64 old_V)
+{
+ struct qfq_group *grp;
+ unsigned long ineligible;
+
+ ineligible = q->bitmaps[IR] | q->bitmaps[IB];
+ if (ineligible) {
+ if (!q->bitmaps[ER]) {
+ grp = qfq_ffs(q, ineligible);
+ if (qfq_gt(grp->S, q->V))
+ q->V = grp->S;
+ }
+ qfq_make_eligible(q, old_V);
+ }
+}
+
+/* What is length of next packet in queue (0 if queue is empty) */
+static unsigned int qdisc_peek_len(struct Qdisc *sch)
+{
+ struct sk_buff *skb;
+
+ skb = sch->ops->peek(sch);
+ return skb ? qdisc_pkt_len(skb) : 0;
+}
+
+/*
+ * Updates the class, returns true if also the group needs to be updated.
+ */
+static bool qfq_update_class(struct qfq_group *grp, struct qfq_class *cl)
+{
+ unsigned int len = qdisc_peek_len(cl->qdisc);
+
+ cl->S = cl->F;
+ if (!len)
+ qfq_front_slot_remove(grp); /* queue is empty */
+ else {
+ u64 roundedS;
+
+ cl->F = cl->S + (u64)len * cl->inv_w;
+ roundedS = qfq_round_down(cl->S, grp->slot_shift);
+ if (roundedS == grp->S)
+ return false;
+
+ qfq_front_slot_remove(grp);
+ qfq_slot_insert(grp, cl, roundedS);
+ }
+
+ return true;
+}
+
+static struct sk_buff *qfq_dequeue(struct Qdisc *sch)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_group *grp;
+ struct qfq_class *cl;
+ struct sk_buff *skb;
+ unsigned int len;
+ u64 old_V;
+
+ if (!q->bitmaps[ER])
+ return NULL;
+
+ grp = qfq_ffs(q, q->bitmaps[ER]);
+
+ cl = grp->slots[grp->front];
+ skb = qdisc_dequeue_peeked(cl->qdisc);
+ if (!skb) {
+ WARN_ONCE(1, "qfq_dequeue: non-workconserving leaf\n");
+ return NULL;
+ }
+
+ sch->q.qlen--;
+ qdisc_bstats_update(sch, skb);
+
+ old_V = q->V;
+ len = qdisc_pkt_len(skb);
+ q->V += (u64)len * IWSUM;
+ pr_debug("qfq dequeue: len %u F %lld now %lld\n",
+ len, (unsigned long long) cl->F, (unsigned long long) q->V);
+
+ if (qfq_update_class(grp, cl)) {
+ u64 old_F = grp->F;
+
+ cl = qfq_slot_scan(grp);
+ if (!cl)
+ __clear_bit(grp->index, &q->bitmaps[ER]);
+ else {
+ u64 roundedS = qfq_round_down(cl->S, grp->slot_shift);
+ unsigned int s;
+
+ if (grp->S == roundedS)
+ goto skip_unblock;
+ grp->S = roundedS;
+ grp->F = roundedS + (2ULL << grp->slot_shift);
+ __clear_bit(grp->index, &q->bitmaps[ER]);
+ s = qfq_calc_state(q, grp);
+ __set_bit(grp->index, &q->bitmaps[s]);
+ }
+
+ qfq_unblock_groups(q, grp->index, old_F);
+ }
+
+skip_unblock:
+ qfq_update_eligible(q, old_V);
+
+ return skb;
+}
+
+/*
+ * Assign a reasonable start time for a new flow k in group i.
+ * Admissible values for \hat(F) are multiples of \sigma_i
+ * no greater than V+\sigma_i . Larger values mean that
+ * we had a wraparound so we consider the timestamp to be stale.
+ *
+ * If F is not stale and F >= V then we set S = F.
+ * Otherwise we should assign S = V, but this may violate
+ * the ordering in ER. So, if we have groups in ER, set S to
+ * the F_j of the first group j which would be blocking us.
+ * We are guaranteed not to move S backward because
+ * otherwise our group i would still be blocked.
+ */
+static void qfq_update_start(struct qfq_sched *q, struct qfq_class *cl)
+{
+ unsigned long mask;
+ uint32_t limit, roundedF;
+ int slot_shift = cl->grp->slot_shift;
+
+ roundedF = qfq_round_down(cl->F, slot_shift);
+ limit = qfq_round_down(q->V, slot_shift) + (1UL << slot_shift);
+
+ if (!qfq_gt(cl->F, q->V) || qfq_gt(roundedF, limit)) {
+ /* timestamp was stale */
+ mask = mask_from(q->bitmaps[ER], cl->grp->index);
+ if (mask) {
+ struct qfq_group *next = qfq_ffs(q, mask);
+ if (qfq_gt(roundedF, next->F)) {
+ cl->S = next->F;
+ return;
+ }
+ }
+ cl->S = q->V;
+ } else /* timestamp is not stale */
+ cl->S = cl->F;
+}
+
+static int qfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_group *grp;
+ struct qfq_class *cl;
+ int err;
+ u64 roundedS;
+ int s;
+
+ cl = qfq_classify(skb, sch, &err);
+ if (cl == NULL) {
+ if (err & __NET_XMIT_BYPASS)
+ sch->qstats.drops++;
+ kfree_skb(skb);
+ return err;
+ }
+ pr_debug("qfq_enqueue: cl = %x\n", cl->common.classid);
+
+ err = qdisc_enqueue(skb, cl->qdisc);
+ if (unlikely(err != NET_XMIT_SUCCESS)) {
+ pr_debug("qfq_enqueue: enqueue failed %d\n", err);
+ if (net_xmit_drop_count(err)) {
+ cl->qstats.drops++;
+ sch->qstats.drops++;
+ }
+ return err;
+ }
+
+ bstats_update(&cl->bstats, skb);
+ ++sch->q.qlen;
+
+ /* If the new skb is not the head of queue, then done here. */
+ if (cl->qdisc->q.qlen != 1)
+ return err;
+
+ /* If reach this point, queue q was idle */
+ grp = cl->grp;
+ qfq_update_start(q, cl);
+
+ /* compute new finish time and rounded start. */
+ cl->F = cl->S + (u64)qdisc_pkt_len(skb) * cl->inv_w;
+ roundedS = qfq_round_down(cl->S, grp->slot_shift);
+
+ /*
+ * insert cl in the correct bucket.
+ * If cl->S >= grp->S we don't need to adjust the
+ * bucket list and simply go to the insertion phase.
+ * Otherwise grp->S is decreasing, we must make room
+ * in the bucket list, and also recompute the group state.
+ * Finally, if there were no flows in this group and nobody
+ * was in ER make sure to adjust V.
+ */
+ if (grp->full_slots) {
+ if (!qfq_gt(grp->S, cl->S))
+ goto skip_update;
+
+ /* create a slot for this cl->S */
+ qfq_slot_rotate(grp, roundedS);
+ /* group was surely ineligible, remove */
+ __clear_bit(grp->index, &q->bitmaps[IR]);
+ __clear_bit(grp->index, &q->bitmaps[IB]);
+ } else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V))
+ q->V = roundedS;
+
+ grp->S = roundedS;
+ grp->F = roundedS + (2ULL << grp->slot_shift);
+ s = qfq_calc_state(q, grp);
+ __set_bit(grp->index, &q->bitmaps[s]);
+
+ pr_debug("qfq enqueue: new state %d %#lx S %lld F %lld V %lld\n",
+ s, q->bitmaps[s],
+ (unsigned long long) cl->S,
+ (unsigned long long) cl->F,
+ (unsigned long long) q->V);
+
+skip_update:
+ qfq_slot_insert(grp, cl, roundedS);
+
+ return err;
+}
+
+
+static void qfq_slot_remove(struct qfq_sched *q, struct qfq_group *grp,
+ struct qfq_class *cl, struct qfq_class **pprev)
+{
+ unsigned int i, offset;
+ u64 roundedS;
+
+ roundedS = qfq_round_down(cl->S, grp->slot_shift);
+ offset = (roundedS - grp->S) >> grp->slot_shift;
+ i = (grp->front + offset) % QFQ_MAX_SLOTS;
+
+ if (!pprev) {
+ pprev = &grp->slots[i];
+ while (*pprev && *pprev != cl)
+ pprev = &(*pprev)->next;
+ }
+
+ *pprev = cl->next;
+ if (!grp->slots[i])
+ __clear_bit(offset, &grp->full_slots);
+}
+
+/*
+ * called to forcibly destroy a queue.
+ * If the queue is not in the front bucket, or if it has
+ * other queues in the front bucket, we can simply remove
+ * the queue with no other side effects.
+ * Otherwise we must propagate the event up.
+ */
+static void qfq_deactivate_class(struct qfq_sched *q, struct qfq_class *cl,
+ struct qfq_class **pprev)
+{
+ struct qfq_group *grp = cl->grp;
+ unsigned long mask;
+ u64 roundedS;
+ int s;
+
+ cl->F = cl->S;
+ qfq_slot_remove(q, grp, cl, pprev);
+
+ if (!grp->full_slots) {
+ __clear_bit(grp->index, &q->bitmaps[IR]);
+ __clear_bit(grp->index, &q->bitmaps[EB]);
+ __clear_bit(grp->index, &q->bitmaps[IB]);
+
+ if (test_bit(grp->index, &q->bitmaps[ER]) &&
+ !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) {
+ mask = q->bitmaps[ER] & ((1UL << grp->index) - 1);
+ if (mask)
+ mask = ~((1UL << __fls(mask)) - 1);
+ else
+ mask = ~0UL;
+ qfq_move_groups(q, mask, EB, ER);
+ qfq_move_groups(q, mask, IB, IR);
+ }
+ __clear_bit(grp->index, &q->bitmaps[ER]);
+ } else if (!grp->slots[grp->front]) {
+ cl = qfq_slot_scan(grp);
+ roundedS = qfq_round_down(cl->S, grp->slot_shift);
+ if (grp->S != roundedS) {
+ __clear_bit(grp->index, &q->bitmaps[ER]);
+ __clear_bit(grp->index, &q->bitmaps[IR]);
+ __clear_bit(grp->index, &q->bitmaps[EB]);
+ __clear_bit(grp->index, &q->bitmaps[IB]);
+ grp->S = roundedS;
+ grp->F = roundedS + (2ULL << grp->slot_shift);
+ s = qfq_calc_state(q, grp);
+ __set_bit(grp->index, &q->bitmaps[s]);
+ }
+ }
+
+ qfq_update_eligible(q, q->V);
+}
+
+static void qfq_qlen_notify(struct Qdisc *sch, unsigned long arg)
+{
+ struct qfq_sched *q = sched_priv(sch);
+ struct qfq_class *cl = (struct qfq_class *)arg;
+
+ if (cl->qdisc->q.qlen == 0)
+ qfq_deactivate_class(q, cl, NULL);
+}
+
+static unsigned int qfq_drop(struct Qdisc *sch)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_group *grp;
+ struct qfq_class *cl, **pp;
+ unsigned int i, j, len;
+
+ for (i = 0; i <= QFQ_MAX_INDEX; i++) {
+ grp = &q->groups[i];
+ for (j = 0; j < QFQ_MAX_SLOTS; j++) {
+ for (pp = &grp->slots[j]; *pp; pp = &(*pp)->next) {
+ cl = *pp;
+ if (!cl->qdisc->ops->drop)
+ continue;
+
+ len = cl->qdisc->ops->drop(cl->qdisc);
+ if (len > 0) {
+ sch->q.qlen--;
+ if (!cl->qdisc->q.qlen)
+ qfq_deactivate_class(q, cl, pp);
+
+ return len;
+ }
+ }
+ }
+ }
+
+ return 0;
+}
+
+static int qfq_init_qdisc(struct Qdisc *sch, struct nlattr *opt)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_group *grp;
+ int i, err;
+
+ err = qdisc_class_hash_init(&q->clhash);
+ if (err < 0)
+ return err;
+
+ for (i = 0; i <= QFQ_MAX_INDEX; i++) {
+ grp = &q->groups[i];
+ grp->index = i;
+ }
+
+ return 0;
+}
+
+static void qfq_reset_qdisc(struct Qdisc *sch)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_group *grp;
+ struct qfq_class *cl, **pp;
+ struct hlist_node *n;
+ unsigned int i, j;
+
+ for (i = 0; i <= QFQ_MAX_INDEX; i++) {
+ grp = &q->groups[i];
+ for (j = 0; j < QFQ_MAX_SLOTS; j++) {
+ for (pp = &grp->slots[j]; *pp; pp = &(*pp)->next) {
+ cl = *pp;
+ if (cl->qdisc->q.qlen)
+ qfq_deactivate_class(q, cl, pp);
+ }
+ }
+ }
+
+ for (i = 0; i < q->clhash.hashsize; i++) {
+ hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
+ qdisc_reset(cl->qdisc);
+ }
+ sch->q.qlen = 0;
+}
+
+static void qfq_destroy_qdisc(struct Qdisc *sch)
+{
+ struct qfq_sched *q = qdisc_priv(sch);
+ struct qfq_class *cl;
+ struct hlist_node *n, *next;
+ unsigned int i;
+
+ tcf_destroy_chain(&q->filter_list);
+
+ for (i = 0; i < q->clhash.hashsize; i++) {
+ hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
+ common.hnode)
+ qfq_destroy_class(sch, cl);
+ }
+ qdisc_class_hash_destroy(&q->clhash);
+}
+
+static const struct Qdisc_class_ops qfq_class_ops = {
+ .change = qfq_change_class,
+ .delete = qfq_delete_class,
+ .get = qfq_get_class,
+ .put = qfq_put_class,
+ .tcf_chain = qfq_tcf_chain,
+ .bind_tcf = qfq_bind_tcf,
+ .unbind_tcf = qfq_unbind_tcf,
+ .graft = qfq_graft_class,
+ .leaf = qfq_class_leaf,
+ .qlen_notify = qfq_qlen_notify,
+ .dump = qfq_dump_class,
+ .dump_stats = qfq_dump_class_stats,
+ .walk = qfq_walk,
+};
+
+static struct Qdisc_ops qfq_qdisc_ops __read_mostly = {
+ .cl_ops = &qfq_class_ops,
+ .id = "qfq",
+ .priv_size = sizeof(struct qfq_sched),
+ .enqueue = qfq_enqueue,
+ .dequeue = qfq_dequeue,
+ .peek = qdisc_peek_dequeued,
+ .drop = qfq_drop,
+ .init = qfq_init_qdisc,
+ .reset = qfq_reset_qdisc,
+ .destroy = qfq_destroy_qdisc,
+ .owner = THIS_MODULE,
+};
+
+static int __init qfq_init(void)
+{
+ return register_qdisc(&qfq_qdisc_ops);
+}
+
+static void __exit qfq_exit(void)
+{
+ unregister_qdisc(&qfq_qdisc_ops);
+}
+
+module_init(qfq_init);
+module_exit(qfq_exit);
+MODULE_LICENSE("GPL");
^ permalink raw reply
* Re: Bad performance when CUBIC HyStart enabled
From: Lucas Nussbaum @ 2011-03-03 18:12 UTC (permalink / raw)
To: Eric Dumazet; +Cc: netdev, Sangtae Ha
In-Reply-To: <1299174383.2983.144.camel@edumazet-laptop>
On 03/03/11 at 18:46 +0100, Eric Dumazet wrote:
> Le jeudi 03 mars 2011 à 18:37 +0100, Lucas Nussbaum a écrit :
>
> > I had 6 successful transfers. There's the netstat -s output after the 5
> > first successful transfers. Then the 7th transfer showed the problem,
> > as well as the 8th and the 9th. There's the netstat -s output after each
> > of them.
>
> Its a bit strange : my 'netstat -s' are more verbose than yours :
Strange. Mine is from the debian package, and it hasn't been updated
recently, neither in Debian nor at
https://developer.berlios.de/project/showfiles.php?group_id=4537.
Maybe some fields are not displayed when the value is 0?
--
| Lucas Nussbaum MCF Université Nancy 2 |
| lucas.nussbaum@loria.fr LORIA / AlGorille |
| http://www.loria.fr/~lnussbau/ +33 3 54 95 86 19 |
^ permalink raw reply
* Re: ANNOUNCE: debloat-testing kernel git tree
From: Rick Jones @ 2011-03-03 18:16 UTC (permalink / raw)
To: Dave Täht
Cc: sedat.dilek, linux-wireless, netdev, bloat-devel, linux-kernel
In-Reply-To: <87tyfph2az.fsf@cruithne.co.teklibre.org>
> For wireless routers and cable home gateways especially, this research
> shows that the total un-managed buffers in your system should be less
> than 32.
Would it be a good thing to start describing these queues not so much in
terms of packets but in terms of delay (or bandwidth X delay)?
Constants tend to live longer than they should, no matter how noble in
birth.
rick jones
^ permalink raw reply
* Re: ANNOUNCE: debloat-testing kernel git tree
From: John W. Linville @ 2011-03-03 18:19 UTC (permalink / raw)
To: Rick Jones
Cc: Dave Täht, sedat.dilek, netdev, linux-wireless, bloat-devel,
linux-kernel
In-Reply-To: <1299176168.2157.14.camel@tardy>
On Thu, Mar 03, 2011 at 10:16:08AM -0800, Rick Jones wrote:
> > For wireless routers and cable home gateways especially, this research
> > shows that the total un-managed buffers in your system should be less
> > than 32.
>
> Would it be a good thing to start describing these queues not so much in
> terms of packets but in terms of delay (or bandwidth X delay)?
>
> Constants tend to live longer than they should, no matter how noble in
> birth.
Yes, it probably would -- that would be more meaningful between
different technologies and/or for technologies that might have variable
latencies due to shared media or whatnot.
Now, the question becomes what patches to propose to make that
happen... :-)
John
--
John W. Linville Someday the world will need a hero, and you
linville@tuxdriver.com might be all we have. Be ready.
^ permalink raw reply
* Re: [BUG net-next-2.6] dst_release() crash
From: David Miller @ 2011-03-03 18:38 UTC (permalink / raw)
To: eric.dumazet; +Cc: netdev
In-Reply-To: <1299169686.2983.129.camel@edumazet-laptop>
From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Thu, 03 Mar 2011 17:28:06 +0100
> We could add a sanity test in dst_release(), or fix callers ?
Callers are responsible for not passing garbage pointers around
:-)
Thanks for the report.
I just checked in the following fix.
--------------------
ipv4: Fix crash in dst_release when udp_sendmsg route lookup fails.
As reported by Eric:
[11483.697233] IP: [<c12b0638>] dst_release+0x18/0x60
...
[11483.697741] Call Trace:
[11483.697764] [<c12fc9d2>] udp_sendmsg+0x282/0x6e0
[11483.697790] [<c12a1c01>] ? memcpy_toiovec+0x51/0x70
[11483.697818] [<c12dbd90>] ? ip_generic_getfrag+0x0/0xb0
The pointer passed to dst_release() is -EINVAL, that's because
we leave an error pointer in the local variable "rt" by accident.
NULL it out to fix the bug.
Reported-by: Eric Dumazet <eric.dumazet@gmail.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
---
net/ipv4/udp.c | 1 +
1 files changed, 1 insertions(+), 0 deletions(-)
diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c
index 95e0c2c..c9a73e5 100644
--- a/net/ipv4/udp.c
+++ b/net/ipv4/udp.c
@@ -925,6 +925,7 @@ int udp_sendmsg(struct kiocb *iocb, struct sock *sk, struct msghdr *msg,
rt = ip_route_output_flow(net, &fl, sk);
if (IS_ERR(rt)) {
err = PTR_ERR(rt);
+ rt = NULL;
if (err == -ENETUNREACH)
IP_INC_STATS_BH(net, IPSTATS_MIB_OUTNOROUTES);
goto out;
--
1.7.4.1
^ permalink raw reply related
* Re: [PATCH net-next-2.6] udp: udp_sendmsg() fix
From: David Miller @ 2011-03-03 18:42 UTC (permalink / raw)
To: eric.dumazet; +Cc: netdev
In-Reply-To: <1299172043.2983.142.camel@edumazet-laptop>
From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Thu, 03 Mar 2011 18:07:23 +0100
> [PATCH net-next-2.6] udp: udp_sendmsg() fix
>
> commit b23dd4fe42b455af (ipv4: Make output route lookup return rtable
> directly) introduced a regression in udp_sendmsg()
>
> If IP route lookup fails, we should not try to release an non existent
> route.
>
> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Ok, this works too.
My version NULL's out rt, so that if we had any changes in code paths
here it would be unlikely we'd reintroduce this bug.
I'm fine either way, although my version is in net-next-2.6 at the
moment :-)
^ permalink raw reply
* Re: [PATCH 2/2] netlink: kill eff_cap from struct netlink_skb_parms
From: David Miller @ 2011-03-03 18:56 UTC (permalink / raw)
To: chrisw; +Cc: kaber, netdev, dm-devel, linux-security-module, drbd-dev
In-Reply-To: <20110303173230.GP4988@sequoia.sous-sol.org>
From: Chris Wright <chrisw@sous-sol.org>
Date: Thu, 3 Mar 2011 09:32:30 -0800
> * Patrick McHardy (kaber@trash.net) wrote:
>
>> commit 8ff259625f0ab295fa085b0718eed13093813fbc
>> Author: Patrick McHardy <kaber@trash.net>
>> Date: Thu Mar 3 10:17:31 2011 +0100
>>
>> netlink: kill eff_cap from struct netlink_skb_parms
>>
>> Netlink message processing in the kernel is synchronous these days,
>> capabilities can be checked directly in security_netlink_recv() from
>> the current process.
>>
>> Signed-off-by: Patrick McHardy <kaber@trash.net>
>
> Thanks for doing that Patrick. I looked at this earlier and thought
> there was still an async path, but I guess that's just to another
> userspace process.
>
> BTW, I think you missed a couple connector based callers:
>
> drivers/staging/pohmelfs/config.c: if (!cap_raised(nsp->eff_cap, CAP_SYS_AD
> drivers/video/uvesafb.c: if (!cap_raised(nsp->eff_cap, CAP_SYS_ADMIN))
>
> Fix those and:
>
> Acked-by: Chris Wright <chrisw@sous-sol.org>
Patrick, I'll apply your first patch, please respin this second patch with
the changes mentioned here.
Thanks!
^ permalink raw reply
* Re: [PATCH 0/3] [RFC] Implement multiqueue (RX & TX) virtio-net
From: Andrew Theurer @ 2011-03-03 19:01 UTC (permalink / raw)
To: Krishna Kumar
Cc: rusty, davem, mst, eric.dumazet, arnd, netdev, horms, avi,
anthony, kvm
In-Reply-To: <20110228063427.24908.63561.sendpatchset@krkumar2.in.ibm.com>
On Mon, 2011-02-28 at 12:04 +0530, Krishna Kumar wrote:
> This patch series is a continuation of an earlier one that
> implemented guest MQ TX functionality. This new patchset
> implements both RX and TX MQ. Qemu changes are not being
> included at this time solely to aid in easier review.
> Compatibility testing with old/new combinations of qemu/guest
> and vhost was done without any issues.
>
> Some early TCP/UDP test results are at the bottom of this
> post, I plan to submit more test results in the coming days.
>
> Please review and provide feedback on what can improve.
>
> Thanks!
>
> Signed-off-by: Krishna Kumar <krkumar2@in.ibm.com>
> ---
>
>
> Test configuration:
> Host: 8 Intel Xeon, 8 GB memory
> Guest: 4 cpus, 2 GB memory
>
> Each test case runs for 60 secs, results below are average over
> two runs. Bandwidth numbers are in gbps. I have used default
> netperf, and no testing/system tuning other than taskset each
> vhost to 0xf (cpus 0-3). Comparison is testing original kernel
> vs new kernel with #txqs=8 ("#" refers to number of netperf
> sessions).
>
> _______________________________________________________________________
> TCP: Guest -> Local Host (TCP_STREAM)
> TCP: Local Host -> Guest (TCP_MAERTS)
> UDP: Local Host -> Guest (UDP_STREAM)
Any reason why the tests don't include a guest-to-guest on same host, or
on different hosts? Seems like those would be a lot more common that
guest-to/from-localhost.
Thanks,
-Andrew
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox