Add busy poll support for epoll

From: Alexander Duyck <[email protected]>

This patch is a cleanup/fix for NAPI IDs following the changes that made it so that sender_cpu and napi_id were doing a better job of sharing the same location in the sk_buff.

One issue I found is that we weren't validating the napi_id as being valid before we started trying to setup the busy polling. This change corrects that by using the MIN_NAPI_ID value that is now used in both allocating the NAPI IDs, as well as validating them.

Signed-off-by Alexander Duyck <[email protected]>

---

From: Alexander Duyck <[email protected]>

While working on some recent busy poll changes we found that child sockets were being instantiated without NAPI ID being set. In our first attempt to fix it, it was suggested that we should just pull programming the NAPI ID into the function itself since all callers will need to have it set.

In addition to the NAPI ID change I have dropped the code that was populating the Rx hash since it was actually being populated in tcp_get_cookie_sock.

Reported-by Sridhar Samudrala <[email protected]>

Suggested-by Eric Dumazet <[email protected]>

Signed-off-by Alexander Duyck <[email protected]>

---

From: Alexander Duyck <[email protected]>

Instead of defining two versions of skb_mark_napi_id I think it is more readable to just match the format of the sk_mark_napi_id functions and just wrap the contents of the function instead of defining two versions of the function. This way we can save a few lines of code since we only need 2 of the ifdef/endif but needed 5 for the extra function declaration.

Signed-off-by Alexander Duyck <[email protected]>

---
 include/net/busy_poll.h |   22 +++++++++-------------
 1 file changed, 9 insertions(+), 13 deletions(-)

From what I can tell there is only a couple spots where we are actually

From: Alexander Duyck <[email protected]>

Quoted 1 line

From what I can tell there is only a couple spots where we are actually

checking the return value of sk_busy_loop. As there are only a few consumers of that data, and the data being checked for can be replaced with a check for !skb_queue_empty() we might as well just pull the code out of sk_busy_loop and place it in the spots that actually need it.

Signed-off-by Alexander Duyck <[email protected]>

---

From: Alexander Duyck <[email protected]>

The last bit I changed is to move from using a shift by 10 to just using NSEC_PER_USEC and using multiplication for any run time calculations and division for a few compile time ones. This should be more accurate and perform about the same on most architectures since modern CPUs typically handle multiplication without too much overhead.

Quoted 2 lines · Alexander Duyck

From: Alexander Duyck <[email protected]>

Quoted 5 lines

The last bit I changed is to move from using a shift by 10 to just using NSEC_PER_USEC and using multiplication for any run time calculations and division for a few compile time ones. This should be more accurate and perform about the same on most architectures since modern CPUs typically handle multiplication without too much overhead.

busy polling thread can be preempted for more than 2 seconds.

Using usec instead of nanoseconds gave us 3 orders of magnitude cushion.

We do not need nsec accuracy for busy polling users, if this restricts range and usability under stress.

Quoted 4 lines · Eric Dumazet

Quoted 2 lines · Alexander Duyck

From: Alexander Duyck <[email protected]>

Quoted 8 lines

Quoted 5 lines

The last bit I changed is to move from using a shift by 10 to just using NSEC_PER_USEC and using multiplication for any run time calculations and division for a few compile time ones. This should be more accurate and perform about the same on most architectures since modern CPUs typically handle multiplication without too much overhead.

busy polling thread can be preempted for more than 2 seconds.

If it is preempted is the timing value even valid anymore? I was wondering about that. Also when preemption is enabled is there anything to prevent us from being migrated to a CPU? If so what do we do about architectures that allow drift between the clocks?

Quoted 1 line

Using usec instead of nanoseconds gave us 3 orders of magnitude cushion.

Yes, but the problem is we also opened up an issue where if the clock was approaching a roll-over we could add a value to it that would put us in a state where we would never time out.

Quoted 3 lines

We do not need nsec accuracy for busy polling users, if this restricts range and usability under stress.

Yes and no. So the standard use cases suggest using values of 50 to 100 microseconds. I suspect that for most people that is probably what they are using. The addition of preemption kind of threw a wrench in the works because now instead of spending that time busy polling you can get preempted and then are off doing something else for the entire period of time.

What would you think of changing this so that instead of tracking the total time this function is active, instead we tracked the total time we spent with preemption disabled? What I would do is move the start_time configuration to just after the preempt_disable() call. Then if we end up yielding to another thread we would just reset the start_time when we restarted instead of trying to deal with all the extra clock nonsense that we would have to deal with otherwise since I don't know if we actually want to count time where we aren't actually doing anything. In addition this would bring us closer to how NAPI already works since it essentially will either find an event, or if we time out we hand it off to the softirq which in turn can handle it or hand it off to softirqd. The only item that might be a bit more difficult to deal with then would be the way the times are used in fs/select.c but I don't know if that is really the right way to go anyway. With the preemption changes and such it might just make sense to drop those bits and rely on just the socket polling alone.

The other option is to switch over everything from using unsigned long to using uint64_t and time_after64. Then we can guarantee the range needed and then some, but then we are playing with a u64 time value on 32b architectures which might be a bit more expensive. Even with that though I still need to clean up the sysctl since it doesn't make sense to allow negative values for the busy_poll usec to be used which is currently the case.

Anyway let me know what you think and I can probably spin out a new set tomorrow.

If you believe min/max values should be added to the sysctls, because we do not trust root anymore, please send patches only addressing that.

Quoted 21 lines · Alexander Duyck

Quoted 4 lines · Eric Dumazet

Quoted 2 lines · Alexander Duyck

From: Alexander Duyck <[email protected]>

Quoted 8 lines

Quoted 5 lines

The last bit I changed is to move from using a shift by 10 to just using NSEC_PER_USEC and using multiplication for any run time calculations and division for a few compile time ones. This should be more accurate and perform about the same on most architectures since modern CPUs typically handle multiplication without too much overhead.

busy polling thread can be preempted for more than 2 seconds.

If it is preempted is the timing value even valid anymore? I was wondering about that. Also when preemption is enabled is there anything to prevent us from being migrated to a CPU? If so what do we do about architectures that allow drift between the clocks?

Quoted 1 line

Using usec instead of nanoseconds gave us 3 orders of magnitude cushion.

Quoted 3 lines

Yes, but the problem is we also opened up an issue where if the clock was approaching a roll-over we could add a value to it that would put us in a state where we would never time out.

If you believe there is a bug, send a fix for net tree ?

I really do not see a bug, given we use time_after(now, end_time) which handles roll-over just fine.

Quoted 10 lines

Quoted 3 lines

We do not need nsec accuracy for busy polling users, if this restricts range and usability under stress.

Yes and no. So the standard use cases suggest using values of 50 to 100 microseconds. I suspect that for most people that is probably what they are using. The addition of preemption kind of threw a wrench in the works because now instead of spending that time busy polling you can get preempted and then are off doing something else for the entire period of time.

That is fine. Busy polling heavy users are pinning threads to cpu, and the re-schedule check is basically a way to make sure ksoftirqd will get a chance to service BH.

Quoted 26 lines

What would you think of changing this so that instead of tracking the total time this function is active, instead we tracked the total time we spent with preemption disabled? What I would do is move the start_time configuration to just after the preempt_disable() call. Then if we end up yielding to another thread we would just reset the start_time when we restarted instead of trying to deal with all the extra clock nonsense that we would have to deal with otherwise since I don't know if we actually want to count time where we aren't actually doing anything. In addition this would bring us closer to how NAPI already works since it essentially will either find an event, or if we time out we hand it off to the softirq which in turn can handle it or hand it off to softirqd. The only item that might be a bit more difficult to deal with then would be the way the times are used in fs/select.c but I don't know if that is really the right way to go anyway. With the preemption changes and such it might just make sense to drop those bits and rely on just the socket polling alone.

The other option is to switch over everything from using unsigned long to using uint64_t and time_after64. Then we can guarantee the range needed and then some, but then we are playing with a u64 time value on 32b architectures which might be a bit more expensive. Even with that though I still need to clean up the sysctl since it doesn't make sense to allow negative values for the busy_poll usec to be used which is currently the case.

Quoted 2 lines

Anyway let me know what you think and I can probably spin out a new set tomorrow.

Leave usec resolution, I see no point switching to nsec, as long we support 32bit kernels.

If you believe min/max values should be added to the sysctls, because we do not trust root anymore, please send patches only addressing that.

Right, but time_after assumes roll over. When you are using a time value based off of local_clock() >> 10, you don't ever roll over when you do addition. Just the clock rolls over. At least on 64 bit systems.

So if local time approaches something like all 1's, and we have shifted it by 10 it is then the max it can ever reach is 0x003FFFFFFFFFFFFF. I can add our loop time to that and it won't roll over. In the mean time the busy_loop_us_ can never exceed whatever I added to that so we are now locked into a loop. I realize I am probably being pedantic, and it will have an exceedingly small rate of occurrence, but it is still an issue.

Quoted 5 lines · Alexander Duyck

Right, but time_after assumes roll over. When you are using a time value based off of local_clock() >> 10, you don't ever roll over when you do addition. Just the clock rolls over. At least on 64 bit systems.

Quoted 7 lines

So if local time approaches something like all 1's, and we have shifted it by 10 it is then the max it can ever reach is 0x003FFFFFFFFFFFFF. I can add our loop time to that and it won't roll over. In the mean time the busy_loop_us_ can never exceed whatever I added to that so we are now locked into a loop. I realize I am probably being pedantic, and it will have an exceedingly small rate of occurrence, but it is still an issue.

Do you realize that a 64bit clock wont rollover before the host has reached 584 years of uptime ?

From: Sridhar Samudrala <[email protected]>

Move the core functionality in sk_busy_loop() to napi_busy_loop() and make it independent of sk.

This enables re-using this function in epoll busy loop implementation.

Signed-off-by Sridhar Samudrala <[email protected]>

Signed-off-by Alexander Duyck <[email protected]>

---

From: Sridhar Samudrala <[email protected]>

This socket option returns the NAPI ID associated with the queue on which the last frame is received. This information can be used by the apps to split the incoming flows among the threads based on the Rx queue on which they are received.

If the NAPI ID actually represents a sender_cpu then the value is ignored and 0 is returned.

From: Sridhar Samudrala <[email protected]>

This socket option returns the NAPI ID associated with the queue on which the last frame is received. This information can be used by the apps to split the incoming flows among the threads based on the Rx queue on which they are received.

If the NAPI ID actually represents a sender_cpu then the value is ignored and 0 is returned.

Quoted 9 lines · Alexander Duyck

From: Sridhar Samudrala <[email protected]>

This socket option returns the NAPI ID associated with the queue on which the last frame is received. This information can be used by the apps to split the incoming flows among the threads based on the Rx queue on which they are received.

If the NAPI ID actually represents a sender_cpu then the value is ignored and 0 is returned.

This may be more of a naming / documentation issue than a functionality issue, but to me this reads as:

"This socket option returns an internal implementation detail that, if you are sufficiently clueful about the current performance heuristics used by the Linux networking stack, just might give you a hint as to which epoll set to put the socket in." I've done some digging into Linux networking stuff, but not nearly enough to have the slighest clue what you're supposed to do with the NAPI ID.

It would be nice to make this a bit more concrete and a bit less tied in Linux innards. Perhaps a socket option could instead return a hint saying "for best results, put this socket in an epoll set that's on cpu N"? After all, you're unlikely to do anything productive with busy polling at all, even on a totally different kernel implementation, if you have more than one epoll set per CPU. I can see cases where you could plausibly poll with fewer than one set per CPU, I suppose.

Again, though, from the description, it's totally unclear what a user is supposed to do.

Quoted 15 lines · Andy Lutomirski

Quoted 9 lines · Alexander Duyck

From: Sridhar Samudrala <[email protected]>

This socket option returns the NAPI ID associated with the queue on which the last frame is received. This information can be used by the apps to split the incoming flows among the threads based on the Rx queue on which they are received.

If the NAPI ID actually represents a sender_cpu then the value is ignored and 0 is returned.

This may be more of a naming / documentation issue than a functionality issue, but to me this reads as:

Quoted 6 lines

"This socket option returns an internal implementation detail that, if you are sufficiently clueful about the current performance heuristics used by the Linux networking stack, just might give you a hint as to which epoll set to put the socket in." I've done some digging into Linux networking stuff, but not nearly enough to have the slighest clue what you're supposed to do with the NAPI ID.

Really the NAPI ID is an arbitrary number that will be unique per device queue, though multiple Rx queues can share a NAPI ID if they are meant to be processed in the same call to poll.

If we wanted we could probably rename it to something like Device Poll Identifier or Device Queue Identifier, DPID or DQID, if that would work for you. Essentially it is just a unique u32 value that should not identify any other queue in the system while this device queue is active. Really the number itself is mostly arbitrary, the main thing is that it doesn't change and uniquely identifies the queue in the system.

Quoted 9 lines

It would be nice to make this a bit more concrete and a bit less tied in Linux innards. Perhaps a socket option could instead return a hint saying "for best results, put this socket in an epoll set that's on cpu N"? After all, you're unlikely to do anything productive with busy polling at all, even on a totally different kernel implementation, if you have more than one epoll set per CPU. I can see cases where you could plausibly poll with fewer than one set per CPU, I suppose.

Really we kind of already have an option that does what you are implying called SO_INCOMING_CPU. The problem is it requires pinning the interrupts to the CPUs in order to keep the values consistent,

and
even then busy polling can mess that up if the busy poll thread is running on a different CPU. With the NAPI ID we have to do a bit of work on the application end, but we can uniquely identify each incoming queue and interrupt migration and busy polling don't have any effect on it. So for example we could stack all the interrupts on CPU 0, and have our main thread located there doing the sorting of incoming requests and handing them out to epoll listener threads on other CPUs. When those epoll listener threads start doing busy polling the NAPI ID won't change even though the packet is being processed on a different CPU.

Quoted 2 lines

Again, though, from the description, it's totally unclear what a user is supposed to do.

What you end up having to do is essentially create a hash of sorts so that you can go from NAPI IDs to threads. In an ideal setup what you end up with multiple threads, each one running one epoll, and each epoll polling on one specific queue.

So don't we want queue id, not NAPI id? Or am I still missing something?

But I'm also a but confused as to the overall performance effect. Suppose I have an rx queue that has its interrupt bound to cpu 0. For whatever reason (random chance if I'm hashing, for example), I end up with the epoll caller on cpu 1. Suppose further that cpus 0 and 1 are on different NUMA nodes.

Now, let's suppose that I get lucky and *all* the packets are pulled off the queue by epoll busy polling. Life is great [1]. But suppose that, due to a tiny hiccup or simply user code spending some cycles processing those packets, an rx interrupt fires. Now cpu 0 starts pulling packets off the queue via NAPI, right? So both NUMA nodes are fighting over all the cachelines involved in servicing the queue *and* the packets just got dequeued on the wrong NUMA node.

ISTM this would work better if the epoll busy polling could handle the case where one epoll set polls sockets on different queues as long as those queues are all owned by the same CPU. Then user code could use SO_INCOMING_CPU to sort out the sockets.

Am I missing something?

[1] Maybe. How smart is direct cache access? If it's smart enough, it'll pre-populate node 0's LLC, which means that life isn't so great after all.

This is my second pass at trying to add support for busy polling when using epoll. It is pretty much a full rewrite as I have made serious changes to most of the patches.

In the v1 series I had submitted we only allowed epoll to make use of busy poll when all NAPI IDs were the same. I gave this some more thought and after making several other changes based on feedback from Eric Dumazet I decided to try changing the main concept a bit and instead we will now attempt to busy poll on the NAPI ID of the last socket added to the ready list. By doing it this way we are able to take advantage of the changes Eric has already made so that we get woken up by the softirq, we then pull packets via busy poll, and will return to the softirq until we are woken up and a new socket has been added to the ready list.

Most of the changes in this set authored by me are meant to be cleanup or fixes for various things. For example, I am trying to make it so that we don't perform hash look-ups for the NAPI instance when we are only working with sender_cpu and the like.

The most complicated change of the set is probably the clean-ups for the timeout. I realized that the timeout could potentially get into a state where it would never timeout if the local_clock() was approaching a rollover and the added busy poll usecs interval would be enough to roll it over. Because we were shifting the value you would never be able to get time_after to actually trigger.

At the heart of this set is the last 3 patches which enable epoll support and add support for obtaining the NAPI ID of a given socket. With these It becomes possible for an application to make use of epoll and get optimal busy poll utilization by stacking multiple sockets with the same NAPI ID on the same epoll context.

Quoted 26 lines · Alexander Duyck

This is my second pass at trying to add support for busy polling when using epoll. It is pretty much a full rewrite as I have made serious changes to most of the patches.

In the v1 series I had submitted we only allowed epoll to make use of busy poll when all NAPI IDs were the same. I gave this some more thought and after making several other changes based on feedback from Eric Dumazet I decided to try changing the main concept a bit and instead we will now attempt to busy poll on the NAPI ID of the last socket added to the ready list. By doing it this way we are able to take advantage of the changes Eric has already made so that we get woken up by the softirq, we then pull packets via busy poll, and will return to the softirq until we are woken up and a new socket has been added to the ready list.

Most of the changes in this set authored by me are meant to be cleanup or fixes for various things. For example, I am trying to make it so that we don't perform hash look-ups for the NAPI instance when we are only working with sender_cpu and the like.

The most complicated change of the set is probably the clean-ups for the timeout. I realized that the timeout could potentially get into a state where it would never timeout if the local_clock() was approaching a rollover and the added busy poll usecs interval would be enough to roll it over. Because we were shifting the value you would never be able to get time_after to actually trigger.

Quoted 5 lines

At the heart of this set is the last 3 patches which enable epoll support and add support for obtaining the NAPI ID of a given socket. With these It becomes possible for an application to make use of epoll and get optimal busy poll utilization by stacking multiple sockets with the same NAPI ID on the same epoll context.

it all sounds awesome, but i cannot quite visualize the impact. Can you post some sample code/minibenchmark and numbers before/after?

Thanks!

On Thu, Mar 23, 2017 at 3:07 PM, Alexei Starovoitov

Quoted 5 lines

it all sounds awesome, but i cannot quite visualize the impact. Can you post some sample code/minibenchmark and numbers before/after?

Thanks!

Anything specific you are looking for? I can probably work with our team internally to setup the benchmark in the next day or so.

I've been doing most of my benchmarking at my desk with sockperf with just one thread and multiple sockets and seeing some modest savings with my round trip times dropping from something like 18 microseconds on average to 8 microseconds for ping-pong tests.