Use random32() in net/ipv4/multipath
Subsystems (4)
PATCH 1/1 Use random32() in net/ipv4/multipath
Einar Lueck's email addresses bounce
<[email protected]><[email protected]>
Removed local random number generator function
net/ipv4/multipath_random.c +2 -16
@@ -33,6 +33,7 @@#include <linux/module.h> #include <linux/mroute.h> #include <linux/init.h> +#include <linux/random.h> #include <net/ip.h> #include <net/protocol.h> #include <linux/skbuff.h>
@@ -49,21 +50,6 @@#define MULTIPATH_MAX_CANDIDATES 40 -/* interface to random number generation */ -static unsigned int RANDOM_SEED =93186752 ; - -static inline unsigned int random (unsigned int ubound) -{ -static unsigned int a =1588635695 , - q =2 , - r =1117695901 ; - -RANDOM_SEED = a*(RANDOM_SEED % q) - r*(RANDOM_SEED / q); - -return RANDOM_SEED % ubound; -} - -static void random_select_route (const struct flowi *flp,struct rtable *first,struct rtable **rp)
@@ -85,7 +71,7 @@ static void random_select_route(const struct flowi *flp,if (candidate_count >1 ) {unsigned char i =0 ;unsigned char candidate_no = (unsigned char ) -random (candidate_count); + (random32 () % candidate_count);/* find chosen candidate and adjust GC data for all candidates * to ensure they stay in cache
net/ipv4/multipath_wrandom.c +2 -13
@@ -33,6 +33,7 @@#include <linux/module.h> #include <linux/mroute.h> #include <linux/init.h> +#include <linux/random.h> #include <net/ip.h> #include <net/protocol.h> #include <linux/skbuff.h>
@@ -85,18 +86,6 @@ struct multipath_route {/* state: primarily weight per route information */ static struct multipath_bucket state[MULTIPATH_STATE_SIZE ]; -/* interface to random number generation */ -static unsigned int RANDOM_SEED =93186752 ; - -static inline unsigned int random (unsigned int ubound) -{ -static unsigned int a =1588635695 , - q =2 , - r =1117695901 ; -RANDOM_SEED = a*(RANDOM_SEED % q) - r*(RANDOM_SEED / q); -return RANDOM_SEED % ubound; -} -static unsigned char __multipath_lookup_weight (const struct flowi *fl,const struct rtable *rt) {
@@ -194,7 +183,7 @@ static void wrandom_select_route(const struct flowi *flp,/* choose a weighted random candidate */ decision = first; - selector =random (power); + selector =random32 () % power; last_power =0 ;/* select candidate, adjust GC data and cleanup local state */
From: Joe Perches <[email protected]>
Date: Thu, 15 Feb 2007 15:46:44 -0800
Quoted 6 lines
Einar Lueck's email addresses bounce
<[email protected]><[email protected]>Removed local random number generator function
Signed-off-by Joe Perches <[email protected]>
Applied, thanks Joe.
PATCH 1/1 TCP : keep copied_seq, rcv_wup and rcv_next together
Hi David
I noticed in oprofile study a cache miss in tcp_rcv_established() to read copied_seq.
ffffffff80400a80 <tcp_rcv_established>: /* tcp_rcv_established total: 4034293 2.0400 */
55493 0.0281 :ffffffff80400bc9: mov 0x4c8(%r12),%eax copied_seq 543103 0.2746 :ffffffff80400bd1: cmp 0x3e0(%r12),%eax rcv_nxt
if (tp->copied_seq == tp->rcv_nxt &&
len - tcp_header_len <= tp->ucopy.len) {In this function, the cache line 0x4c0 -> 0x500 is used only for this reading 'copied_seq' field.
rcv_wup and copied_seq should be next to rcv_nxt field, to lower number of active cache lines in hot paths. (tcp_rcv_established(), tcp_poll(), ...)
Patch is 64bit friendly (no new hole because of alignment constraints)
include/linux/tcp.h +2 -2
@@ -242,6 +242,8 @@ struct tcp_sock {* See RFC793 and RFC1122. The RFC writes these in capitals. */ u32 rcv_nxt;/* What we want to receive next */ +u32 copied_seq;/* Head of yet unread data */ +u32 rcv_wup;/* rcv_nxt on last window update sent */ u32 snd_nxt;/* Next sequence we send */ u32 snd_una;/* First byte we want an ack for */
@@ -307,10 +309,8 @@ struct tcp_sock {struct sk_buff_head out_of_order_queue;/* Out of order segments go here */ u32 rcv_wnd;/* Current receiver window */ -u32 rcv_wup;/* rcv_nxt on last window update sent */ u32 write_seq;/* Tail(+1) of data held in tcp send buffer */ u32 pushed_seq;/* Last pushed seq, required to talk to windows */ -u32 copied_seq;/* Head of yet unread data */ /* SACKs data */ struct tcp_sack_block duplicate_sack[1 ];/* D-SACK block */
David Miller
maintainerRe: [PATCH] TCP : keep copied_seq, rcv_wup and rcv_next together
From: Eric Dumazet <[email protected]>
Date: Thu, 22 Feb 2007 11:22:02 +0100
Quoted 2 lines
rcv_wupandcopied_seqshould be next torcv_nxtfield, to lower number of active cache lines in hot paths. (tcp_rcv_established(),tcp_poll(), ...)
Please fixup the assignment order in tcp_create_openreq_child() else we'll get a new store buffer stall during socket creation :-)
Thanks Eric.
Re: [PATCH] TCP : keep copied_seq, rcv_wup and rcv_next together
Quoted 9 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Thu, 22 Feb 2007 11:22:02 +0100Quoted 3 lines
rcv_wupandcopied_seqshould be next torcv_nxtfield, to lower number of active cache lines in hot paths. (tcp_rcv_established(),tcp_poll(), ...)Please fixup the assignment order in
tcp_create_openreq_child()else we'll get a new store buffer stall during socket creation :-)
OK :)
I wonder if :
newtp->snd_nxt = newtp->snd_una = newtp->snd_sml = treq->snt_isn + 1;
is correct, since compiler will write snd_sml, then snd_una, and snd_nxt
Maybe we should also reorder this too ?
Eric
David Miller
maintainerRe: [PATCH] TCP : keep copied_seq, rcv_wup and rcv_next together
From: Eric Dumazet <[email protected]>
Date: Thu, 22 Feb 2007 11:43:32 +0100
Quoted 7 lines
I wonder if :
newtp->snd_nxt=newtp->snd_una=newtp->snd_sml=treq->snt_isn+ 1;is correct, since compiler will write
snd_sml, thensnd_una, andsnd_nxtMaybe we should also reorder this too ?
Yes, that appears necessary.
PATCH 1/1 TCP : keep copied_seq, rcv_wup and rcv_next together
In reply to Eric DumazetHi David
I noticed in oprofile study a cache miss in tcp_rcv_established() to read copied_seq.
ffffffff80400a80 <tcp_rcv_established>: /* tcp_rcv_established total: 4034293 2.0400 */
55493 0.0281 :ffffffff80400bc9: mov 0x4c8(%r12),%eax copied_seq 543103 0.2746 :ffffffff80400bd1: cmp 0x3e0(%r12),%eax rcv_nxt
if (tp->copied_seq == tp->rcv_nxt &&
len - tcp_header_len <= tp->ucopy.len) {
In this function, the cache line 0x4c0 -> 0x500 is used only for this reading 'copied_seq' field.
rcv_wup and copied_seq should be next to rcv_nxt field, to lower number of active cache lines in hot paths. (tcp_rcv_established(), tcp_poll(), ...)
As you suggested, I changed tcp_create_openreq_child() so that these fields are changed together, to avoid adding a new store buffer stall.
Patch is 64bit friendly (no new hole because of alignment constraints)
include/linux/tcp.h +2 -2
@@ -242,6 +242,8 @@ struct tcp_sock {* See RFC793 and RFC1122. The RFC writes these in capitals. */ u32 rcv_nxt;/* What we want to receive next */ +u32 copied_seq;/* Head of yet unread data */ +u32 rcv_wup;/* rcv_nxt on last window update sent */ u32 snd_nxt;/* Next sequence we send */ u32 snd_una;/* First byte we want an ack for */
@@ -307,10 +309,8 @@ struct tcp_sock {struct sk_buff_head out_of_order_queue;/* Out of order segments go here */ u32 rcv_wnd;/* Current receiver window */ -u32 rcv_wup;/* rcv_nxt on last window update sent */ u32 write_seq;/* Tail(+1) of data held in tcp send buffer */ u32 pushed_seq;/* Last pushed seq, required to talk to windows */ -u32 copied_seq;/* Head of yet unread data */ /* SACKs data */ struct tcp_sack_block duplicate_sack[1 ];/* D-SACK block */
net/ipv4/tcp_minisocks.c +2 -4
@@ -387,8 +387,8 @@ struct sock *tcp_create_openreq_child(st/* Now setup tcp_sock */ newtp =tcp_sk (newsk); newtp->pred_flags =0 ; - newtp->rcv_nxt = treq->rcv_isn +1 ; - newtp->snd_nxt = newtp->snd_una = newtp->snd_sml = treq->snt_isn +1 ; + newtp->rcv_wup = newtp->copied_seq = newtp->rcv_nxt = treq->rcv_isn +1 ; + newtp->snd_sml = newtp->snd_una = newtp->snd_nxt = treq->snt_isn +1 ;tcp_prequeue_init (newtp);
@@ -422,10 +422,8 @@ struct sock *tcp_create_openreq_child(sttcp_set_ca_state (newsk, TCP_CA_Open);tcp_init_xmit_timers (newsk);skb_queue_head_init (&newtp->out_of_order_queue); - newtp->rcv_wup = treq->rcv_isn +1 ; newtp->write_seq = treq->snt_isn +1 ; newtp->pushed_seq = newtp->write_seq; - newtp->copied_seq = treq->rcv_isn +1 ; newtp->rx_opt.saw_tstamp =0 ;
David Miller
maintainerRe: [PATCH, take 2] TCP : keep copied_seq, rcv_wup and rcv_next together
From: Eric Dumazet <[email protected]>
Date: Thu, 22 Feb 2007 12:11:50 +0100
Quoted 2 lines
I noticed in oprofile study a cache miss in
tcp_rcv_established()to readcopied_seq.
...
Quoted 6 lines
As you suggested, I changed
tcp_create_openreq_child()so that these fields are changed together, to avoid adding a new store buffer stall.Patch is 64bit friendly (no new hole because of alignment constraints)
Signed-off-by Eric Dumazet <[email protected]>
Looks great, applied to my tcp-2.6 GIT tree, thanks a lot!
PATCH 1/1 NET : keep sk_backlog near sk_lock
In reply to Eric DumazetHi David
sk_backlog is a critical field of struct sock. (known famous words)
It is (ab)used in hot paths, in particular in release_sock(), tcp_recvmsg(), tcp_v4_rcv(), sk_receive_skb().
It really makes sense to place it next to sk_lock, because sk_backlog is only used after sk_lock locked (and thus memory cache line in L1 cache). This should reduce cache misses and sk_lock acquisition time.
(In theory, we could only move the head pointer near sk_lock, and leaving tail far away, because 'tail' is normally not so hot, but keep it simple :) )
Thank you
include/net/sock.h +9 -9
@@ -202,6 +202,15 @@ struct sock {unsigned short sk_type;int sk_rcvbuf;socket_lock_t sk_lock; +/* +* The backlog queue is special, it is always used with +* the per-socket spinlock held and requires low latency +* access. Therefore we special case it's implementation. +*/ +struct { +struct sk_buff *head; +struct sk_buff *tail; + } sk_backlog;wait_queue_head_t *sk_sleep;struct dst_entry *sk_dst_cache;struct xfrm_policy *sk_policy[2 ];
@@ -221,15 +230,6 @@ struct sock {int sk_rcvlowat;unsigned long sk_flags;unsigned long sk_lingertime; -/* -* The backlog queue is special, it is always used with -* the per-socket spinlock held and requires low latency -* access. Therefore we special case it's implementation. -*/ -struct { -struct sk_buff *head; -struct sk_buff *tail; - } sk_backlog;struct sk_buff_head sk_error_queue;struct proto *sk_prot_creator;rwlock_t sk_callback_lock;
net/core/sock.c +1 -1
@@ -904,6 +904,7 @@ struct sock *sk_clone(const struct socksk_node_init (&newsk->sk_node);sock_lock_init (newsk);bh_lock_sock (newsk); + newsk->sk_backlog.head = newsk->sk_backlog.tail =NULL ;atomic_set (&newsk->sk_rmem_alloc,0 );atomic_set (&newsk->sk_wmem_alloc,0 );
@@ -923,7 +924,6 @@ struct sock *sk_clone(const struct sock newsk->sk_wmem_queued =0 ; newsk->sk_forward_alloc =0 ; newsk->sk_send_head =NULL ; - newsk->sk_backlog.head = newsk->sk_backlog.tail =NULL ; newsk->sk_userlocks = sk->sk_userlocks & ~SOCK_BINDPORT_LOCK ;sock_reset_flag (newsk,SOCK_DONE );
Re: [PATCH] NET : keep sk_backlog near sk_lock
From: Eric Dumazet <[email protected]>
Date: Thu, 22 Feb 2007 15:50:15 +0100
Quoted 5 lines
sk_backlogis a critical field of struct sock. (known famous words)It is (ab)used in hot paths, in particular in
release_sock(),tcp_recvmsg(),tcp_v4_rcv(),sk_receive_skb().
Quoted 8 lines
It really makes sense to place it next to
sk_lock, becausesk_backlogis only used aftersk_locklocked (and thus memory cache line in L1 cache). This should reduce cache misses andsk_lockacquisition time.(In theory, we could only move the head pointer near
sk_lock, and leaving tail far away, because 'tail' is normally not so hot, but keep it simple :) )Signed-off-by Eric Dumazet <[email protected]>
Applied, thanks a lot Eric.