Skip to contentSkip to conversation

do_gettimeofday

PATCH Steve Modica 6 participants 12 messages Oct 2, 2003 – Oct 3, 2003

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

We've been doing some experiments here with large numbers of adapters on a 64p Linux system.

When running 8 threads and 8 cpus, the do_gettimeofday code starts to use a lot of time.

It turns out that if a driver does not timestamp an incoming packet, the upper layer will stamp it for you in PSCHED_GET_TIME(stamp). What happens then is multiple cpus start fighting over the cacheline for the system clock and things get bad.

One possible solution to this is to have the driver do the stamp using xtime. A number of ATM drivers do this now. In testing, it helps a lot.

Here's a sample diff for the tg3.c driver:

===========================================================================
Index: linux/linux/drivers/net/tg3.c
===========================================================================

linux/drivers/net/tg3.c Wed Oct 1 14:27:54 2003 renamed from usr/tmp/TmpDir.8948-0/linux/linux/drivers/net/tg3.c_1.23 Thu Oct 2 13:30:21 2003 +1 -0
@@ -2019,6 +2019,7 @@
                       skb->ip_summed = CHECKSUM_NONE;
 
               skb->protocol = eth_type_trans(skb, tp->dev);
+               skb->stamp = xtime;
#if TG3_VLAN_TAG_USED
               if (tp->vlgrp != NULL &&
                   desc->type_flags & RXD_FLAG_VLAN) {

It's been suggested that we make this tuneable so it's easy to enable and disable. There was concern as to whether xtime would be accurate enough for all possible uses of ->stamp.

Does anyone have any comments on this?

Regards!
Steve

Signature · 6 lines
Steve Modica
work: 651-683-3224
mobile: 651-261-3201
MTS-Technical Lead
"Give a man a fish, and he will eat for a day, hit him with a fish and
he leaves you alone" - me
#1 lore raw
Quoted 4 lines · Steve Modica

We've been doing some experiments here with large numbers of adapters on a 64p Linux system.
When running 8 threads and 8 cpus, the do_gettimeofday code starts to use a lot of time.

That's a known problem. The funny thing is that the only users of this time stamp is SO_TIMESTAMP, which is rarely used (except tcpdump) and something in DECnet. IMHO the right fix is to add a global counter that counts all all sockets that use SO_TIMESTAMP and when it's zero never call it. Decnet could be probably fixed to just use jiffies like TCP does.

Drawback is that when you enable SO_TIMESTAMP there is a small time window when the packets are not time stamped yet. The socket layer can just fill in the current time though.

-Andi

#2 lore raw
In reply to Steve Modica
Quoted 27 lines · On Thu, 02 Oct 2003 13:32:27 -0500 Steve Modica <[email protected]> wrote:

We've been doing some experiments here with large numbers of adapters on a 64p Linux system.

When running 8 threads and 8 cpus, the do_gettimeofday code starts to use a lot of time.

It turns out that if a driver does not timestamp an incoming packet, the upper layer will stamp it for you in PSCHED_GET_TIME(stamp). What happens then is multiple cpus start fighting over the cacheline for the system clock and things get bad.

One possible solution to this is to have the driver do the stamp using xtime. A number of ATM drivers do this now. In testing, it helps a lot.

Here's a sample diff for the tg3.c driver:

===========================================================================
Index: linux/linux/drivers/net/tg3.c
===========================================================================

linux/drivers/net/tg3.c Wed Oct 1 14:27:54 2003 renamed from usr/tmp/TmpDir.8948-0/linux/linux/drivers/net/tg3.c_1.23 Thu Oct 2 13:30:21 2003 +1 -0
@@ -2019,6 +2019,7 @@
                        skb->ip_summed = CHECKSUM_NONE;
 
                skb->protocol = eth_type_trans(skb, tp->dev);
+               skb->stamp = xtime;
 #if TG3_VLAN_TAG_USED
                if (tp->vlgrp != NULL &&
                    desc->type_flags & RXD_FLAG_VLAN) {
Quoted 3 lines

It's been suggested that we make this tuneable so it's easy to enable and disable. There was concern as to whether xtime would be accurate enough for all possible uses of ->stamp.

Does anyone have any comments on this?

Two problems:
a. xtime is limited to HZ resolution which is insufficient for more advanced
packet schedulers and rtt estimation.
b. unlocked access to xtime is unsafe because it is not atomic!

ATM is busted if it does this.

gettimeofday on 2.6 should be cheap for many systems because of the lockless seqlock. Unfortunately, some architectures (not sure about ia64) have problems with TSC synchronization which make life messy.

It might be possible to introduce a per-cpu monotonic clock that is lockless for use in network code, but that is a moderately painful undertaking which is beyond the scope of getting 2.6.0 out.

#3 lore raw
Quoted 6 lines · Stephen Hemminger

Two problems:
a. xtime is limited to HZ resolution which is insufficient for more advanced
packet schedulers and rtt estimation.
b. unlocked access to xtime is unsafe because it is not atomic!

ATM is busted if it does this.

It got fixed in 2.5 (when skb->stamp got changed to nanosecond resolution so it broke the compile to do it the old way) You can use LXR to see all of the xtime users as of 2.6.0-test2:
http://lxr.linux.no/ident?v=2.6.0-test2&i=xtime

The reason that ATM _had_ been using xtime was not for performance. When the ATM code was originally written (during the 1.X kernels) all network drivers used xtime directly. At some point the network drivers were mass-updated to use do_gettimeofday() but ATM had not been merged into the main tree yet so it missed the conversion.

-Mitch

#4 lore raw
In reply to Stephen Hemminger
Quoted 3 lines · On Thu, 2 Oct 2003 12:56:25 -0700 Stephen Hemminger <[email protected]> wrote:

It might be possible to introduce a per-cpu monotonic clock that is lockless for use in network code, but that is a moderately painful undertaking which is beyond the scope of getting 2.6.0 out.

Yes, this issue is well known and it gets brought up again from time to time.

And it's by no means just SO_TIMESTAMP that uses the skb->stamp values, even IPV4/IPV6 fragmentation uses these things.

The SunRPC and RXRPC layers use it as well.

It really is an arch-specific issue of how to "optimize" this the best, that's why it's hard to decide what the interface is that an arch needs to provide.

But at the base I say we need three things:

1) Some kind of fast_timestamp_t, the property is that this stores enough information at time "T" such that at time "T + something" the fast_timestamp_t can be converted what the timeval was back at time "T".

For networking, make skb->stamp into this type.

2) store_fast_timestamp(fast_timestamp_t *)

For networking, change do_gettimeofday(&skb->stamp) into store_fast_timestamp(&skb->stamp)

3) fast_timestamp_to_timeval(arch_timestamp_t *, struct timeval *)

For networking, change things that read the skb->stamp value into calls to fast_timestamp_to_timeval().

It is defined that the timeval given by fast_timestamp_to_timeval() needs to be the same thing that do_gettimeofday() would have recorded at the time store_fast_timestamp() was called.

Here is the default generic implementation that would go into asm-generic/faststamp.h:

1) fast_timestamp_t is struct timeval
2) store_fast_timestamp() is gettimeofday()
3) fast_timestamp_to_timeval() merely copies the fast_timestamp_t into the passed in timeval.

And here is how an example implementation could work on sparc64:

1) fast_timestamp_t is a u64

2) store_fast_timestamp() reads the cpu cycle counter

3) fast_timestamp_to_timeval() records the difference between the current cpu cycle counter and the one recorded, it takes a sample of the current xtime value and adjusts it accordingly to account for the cpu cycle counter difference.

This only works because sparc64's cpu cycle counters are synchronized across all cpus, they increase monotonically, and are guarenteed not to overflow for at least 10 years.

Alpha, for example, cannot do it this way because it's cpu cycle counter register overflows too quickly to be useful.

Platforms with inter-cpu TSC synchronization issues will have some troubles doing the same trick too, because one must handle properly the case where the fast timestamp is converted to a timeval on a different cpu on which the fast timestamp was recorded.

Regardless, we could put the infrastructure in there now and arch folks can work on implementations. The generic implementation code, which is what everyone will end up with at first, will cancel out to what we have currently.

This is a pretty powerful idea that could be applied to other places, not just the networking.

#5 lore raw
Quoted 4 lines · David S. Miller

3) fast_timestamp_to_timeval(arch_timestamp_t *, struct timeval *)

For networking, change things that read the skb->stamp value into calls to fast_timestamp_to_timeval().

Are there any common cases where skb->stamp is looked at more than once? If so I might recommend changing the API to be more like:

	const struct timeval *skb_timestamp(struct skbuff *skb);

where the generic form would just be:

	typedef struct {
		struct timeval tv;
	} fast_timestamp_t;

	static inline const struct timeval *skb_timestamp(struct skbuff *skb) {
		return &skb->faststamp.tv;
	}

...but an arch could accelerate it with:

	typedef struct {
		union {
			struct timeval tv;
			u64 tsc;
		}
		int is_converted;
	} fast_timestamp_t;

	/* Caller must be sure we have exclusive ownership of this skbuff */
	const struct timeval *skb_timestamp(struct skbuff *skb) {
		if (!skb->faststamp.is_converted) {
			tsc_to_timeval(&skb->faststamp.tv, skb->faststamp.tsc);
			skb->faststamp.is_converted = 1;
		}
		return &skb->faststamp.tv;
	}

If we could hide "is_converted" as a flag somewhere else this would have zero storage penalty (since most archs would have a fast-stamp at least as big as a timeval)

I dunno, just an idea.

Quoted 4 lines

Platforms with inter-cpu TSC synchronization issues will have some troubles doing the same trick too, because one must handle properly the case where the fast timestamp is converted to a timeval on a different cpu on which the fast timestamp was recorded.

Yeah, you'd probably have something like

	typedef struct {
		union {
			struct timeval tv;
			struct {
				u64 tsc;
#ifdef CONFIG_SMP
				unsigned int cpu_id;
#endif /* CONFIG_SMP */
			} fast;
		}
		int is_converted;
	} fast_timestamp_t;

And then skb_timestamp() would have to rummage around in the per-cpu timer state for whatever processor started the packet. (This is why I thought it might be good to cache the result - you don't want to thrash those cachelines more than once if you can help it)

-Mitch

#6 lore raw
Quoted 2 lines · On Fri, 3 Oct 2003 01:26:42 -0700 Mitchell Blank Jr <[email protected]> wrote:

Are there any common cases where skb->stamp is looked at more than once?

Yes, the packet scheduler can cause this to happen.

Quoted 3 lines

If so I might recommend changing the API to be more like:

	const struct timeval *skb_timestamp(struct skbuff *skb);

Please no, making this a SKB or networking specific interface make it nearly valueless and we might as well just stay with the stuff we have.

Quoted 6 lines
Quoted 4 lines

Platforms with inter-cpu TSC synchronization issues will have some troubles doing the same trick too, because one must handle properly the case where the fast timestamp is converted to a timeval on a different cpu on which the fast timestamp was recorded.

Yeah, you'd probably have something like

Doesn't work as-is. You'd have to not only store the timestamp and the cpu it was stored on, but also cross-call to that cpu to compute the correct timeval. That's really expensive and probably do_gettimeofday() is going to be faster in the long run compared to such a scheme.

#7 lore raw
Quoted 3 lines · David S. Miller

Doesn't work as-is. You'd have to not only store the timestamp and the cpu it was stored on, but also cross-call to that cpu to compute the correct timeval.

That's definately the worst case. You could have each CPU periodically store its current {tsc,timeval} tuple in a per-cpu location and extrapolate from that.

Quoted 3 lines

That's really expensive and probably
do_gettimeofday() is going to be faster in the long run compared to such a scheme.

It all depends on what percentage of skb's have ->stamp computed on a CPU different from the one they came it on. For the common users of ->stamp won't they have stayed on the same CPU? The worst case of doing a cross-cpu-call should only happen relatively rarely.

-Mitch

#8 lore raw
Quoted 8 lines · On Fri, 3 Oct 2003 01:48:47 -0700 Mitchell Blank Jr <[email protected]> wrote:
Quoted 3 lines · David S. Miller

Doesn't work as-is. You'd have to not only store the timestamp and the cpu it was stored on, but also cross-call to that cpu to compute the correct timeval.

That's definately the worst case. You could have each CPU periodically store its current {tsc,timeval} tuple in a per-cpu location and extrapolate from that.

Right, that would work.

There is the weird issue (with both the sparc64 example and your's here) of whether we should care about what happens when settimeofday() occurs. We probably shouldn't worry about it... as it gives weird results even currently.

Quoted 4 lines

It all depends on what percentage of skb's have ->stamp computed on a CPU different from the one they came it on. For the common users of ->stamp won't they have stayed on the same CPU? The worst case of doing a cross-cpu-call should only happen relatively rarely.

No, they typically won't. The packet comes in on cpu X, we stamp it on X, and we do a wakeup of tcpdump which will typically get scheduled first onto some other processor before X is done processing incoming packets. The higher the packet load the more likely this will happen.

But forget this, as your dual tsc+timeval recording idea would work well and doesn't need a cross-cpu call. Although we'd need to think about how costly the cacheline activity is going to be with your idea compared to the seqlocked accesses to xtime. This is mainly a product of how often you intend to update the tsc+timeval thingy.

#9 lore raw
Quoted 4 lines · David S. Miller

There is the weird issue (with both the sparc64 example and your's here) of whether we should care about what happens when settimeofday() occurs. We probably shouldn't worry about it... as it gives weird results even currently.

Nah. If anything you'll get better results since you're computing the timeval later.

This is another argument for caching the computation though - otherwise a settimeofday() could cause the packet timestamp to change drasically from one observation to the next :-)

Quoted 8 lines
Quoted 2 lines

The worst case of
doing a cross-cpu-call should only happen relatively rarely.

No, they typically won't. The packet comes in on cpu X, we stamp it on X, and we do a wakeup of tcpdump which will typically get scheduled first onto some other processor before X is done processing incoming packets. The higher the packet load the more likely this will happen.

I was more thinking about the other timestamp users. I don't consider tcpdump something that needs as much optimization. If we really wanted to we could have set a per-interface flag that says "someone will want the timestamp so compute it in the bh while we're still on the same processor" But see below - there probably isn't much cost anyways...

Quoted 2 lines

This is mainly a product
of how often you intend to update the tsc+timeval thingy.

You could compute it relatively frequently and then only actually copy it to the hot cacheline if its diverged significantly from whats there. This would make the writes almost never happen (maybe once a minute)

-Mitch

#10 lore raw
Quoted 2 lines · On Fri, 3 Oct 2003 02:26:17 -0700 Mitchell Blank Jr <[email protected]> wrote:

I was more thinking about the other timestamp users. I don't consider tcpdump something that needs as much optimization.

Well, it's is the fact that usage of the timestamp is rare which we're trying to take advantage of.

The whole idea is that fast_timestamp_to_timeval() can be a bit slow or suboptimal in order to make store_fast_timestamp() a lot faster or access less shared or locked state.

#11 lore raw
In reply to Mitchell Blank Jr
Quoted 8 lines · Mitchell Blank Jr
Quoted 4 lines · David S. Miller

There is the weird issue (with both the sparc64 example and your's here) of whether we should care about what happens when settimeofday() occurs. We probably shouldn't worry about it... as it gives weird results even currently.

Quoted 6 lines

Nah. If anything you'll get better results since you're computing the timeval later.

This is another argument for caching the computation though - otherwise a settimeofday() could cause the packet timestamp to change drasically from one observation to the next :-)

It would also be nice to be able to set a flag on raw sockets to just have the 'raw' timestamp passed up to user-space. In many cases, the relative timestamp may be all that is needed, and user-space could optimize the conversion to gettimeofday as needed.

Ben

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com