patchlwIP - A Lightweight TCP/IP stack - Patches: patch #9384, Partial SACK (RFC 2018) support

 
 

You are not allowed to post comments on this tracker with your current authentication level.

patch #9384: Partial SACK (RFC 2018) support

Submitter:  Jakub Schmidtke <jschmidtke>
Submitted:  Wed 21 Jun 2017 06:47:55 PM UTC
   
 
Category:  TCP Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  None Open/Closed:  Closed
Planned Release:  None

Jump to the original submission

Thu 27 Jul 2017 06:40:02 PM UTC, comment #33: 

Right. I've added task #14591 for SACK_IN.

Simon Goldschmidt <goldsimon>
Group administrator
Wed 26 Jul 2017 09:39:40 PM UTC, comment #32: 

Agree, SACK_IN can be new ticket, this can be closed!

Joel Cunningham <jcunningham>
Group Member
Wed 26 Jul 2017 07:54:05 PM UTC, comment #31: 

It is a &quot;partial&quot; SACK support, so I think that's it :)
Once there is SACK_IN implemented, it could be a separate ticket...

Jakub Schmidtke <jschmidtke>
Wed 26 Jul 2017 07:40:10 PM UTC, comment #30: 

Guys, is there anything left here? The patch is pushed, SACK_IN is missing, but I guess this can be closed, right?

Simon Goldschmidt <goldsimon>
Group administrator
Mon 03 Jul 2017 07:42:43 PM UTC, comment #29: 

Right. Just found that in my tests... Thanks for checking!

Simon Goldschmidt <goldsimon>
Group administrator
Mon 03 Jul 2017 07:39:35 PM UTC, comment #28: 

Also, it looks like the cleanup changes are broken.
LWIP_TCP_SACK_VALID is reversed (it should be checking whether left != right).
It's also used wrong in tcp_in.c: if (!LWIP_TCP_SACK_VALID(pcb, 0)) - this should be reversed. The other uses are correct (once the macro itself is fixed).

Jakub Schmidtke <jschmidtke>
Mon 03 Jul 2017 07:34:44 PM UTC, comment #27: 

Yes, Section 8 of RFC 2018 talks about it:
"Note that the data receiver is permitted to discard data in its queue that has not been acknowledged to the data sender, even if the data has already been reported in a SACK option."
It is "discouraged", but allowed. Only ACKs should be used to consider the data actually delivered.

Jakub Schmidtke <jschmidtke>
Mon 03 Jul 2017 07:31:05 PM UTC, comment #26: 

I'll have to admit that this was only reading the code, I haven't found the time to test it, yet...

Simon Goldschmidt <goldsimon>
Group administrator
Mon 03 Jul 2017 07:23:22 PM UTC, comment #25: 

I've just pushed the patch with some cleanup additions by myself.

One question that I had while searching through the new code: is it really allowed to remove a SACK we once sent? In other words: are we allowed to remove OOSEQ segments we already SACKed or has the remote side freed them and cannot retransmit them? This is probably covered by the spec, sorry I don't have the time right now to look. Just wanted to write this here to not forget it :-)

Simon Goldschmidt <goldsimon>
Group administrator
Thu 29 Jun 2017 10:21:38 PM UTC, comment #24: 

I updated the patch (twice, because I found one more issue - sorry abotu that).

Jakub Schmidtke <jschmidtke>
Thu 29 Jun 2017 07:53:49 PM UTC, comment #23: 


> Sounds to go me as well!


Correction: "sounds good to me as well"

Joel Cunningham <jcunningham>
Group Member
Thu 29 Jun 2017 07:52:15 PM UTC, comment #22: 


> I see three problems using memp:
> - users have to configure yet another pool
> - memp allocation can fail (what do we do in thist case?)
> - memp uses "sizeof(void*)" more bytes per region (typically 12 instead of 8 bytes per region)


Good point on the failure.  Managing that case is probably more troublesome than the gains from using a general memory pool

> From my point of view, we can go ahead and push this patch (with the formal changes I initially suggested, that is).


Sounds to go me as well!

Joel Cunningham <jcunningham>
Group Member
Thu 29 Jun 2017 06:55:31 PM UTC, comment #21: 

Ok, thanks! I will post updated patch when it's ready.

Jakub Schmidtke <jschmidtke>
Thu 29 Jun 2017 06:18:39 PM UTC, comment #20: 

I see three problems using memp:
- users have to configure yet another pool
- memp allocation can fail (what do we do in thist case?)
- memp uses "sizeof(void*)" more bytes per region (typically 12 instead of 8 bytes per region)

Given that, personally I prefer the array solution as it is now. The code looks simple enough to me, too.

From my point of view, we can go ahead and push this patch (with the formal changes I initially suggested, that is).

Simon Goldschmidt <goldsimon>
Group administrator
Thu 29 Jun 2017 05:21:37 PM UTC, comment #19: 

OK, so to have a precalculated array/list/whatever of SACKs, it can either be kept as an array in TCP PCB (current implementation), use memp pools, or somehow be integrated with ooseq.

What is wrong with using memp? Assuming that SACKs are not that lightweight to begin with.

If we want to avoid having dynamic memory allocation there, but want precalculated SACKs, they have to be stored somewhere.
So it's either the current array, or inside tcp_seg in ooseq queue.
If they are stored in tcp_seg somehow (doesn't really matter how, even if it was a single pointer - and potentially it would be more than that),
it means increased memory usage for every single tcp_seg structure.
Is using memp worse than increasing memory use of every single tcp_seg?

If both are too "heavy", maybe keeping the array is actually more lightweight solution (since the memory cost is per TCP PCB, not per tcp_seg...)?

Jakub Schmidtke <jschmidtke>
Thu 29 Jun 2017 06:43:46 AM UTC, comment #18: 

Well, about lightweight: we certainly move away from that by adding these speed-related implementations. That why I want them optional. And given that, I guess storing a precalculated array is better than recalculating for every ACK...

Simon Goldschmidt <goldsimon>
Group administrator
Wed 28 Jun 2017 08:57:51 PM UTC, comment #17: 


>But this just changes the way SACKs are stored in PCBs, and doesn't solve the main problem,
>which at the moment seems to be inserting SACKs into data packets.


Correct, I didn't mean for my idea to address that issue

>One solution could be to calculate SACKs dynamically by examining the ooseq list


I also thought of this, but didn't suggest it because it seemed like we could be repeating this computation a lot if sending ACKs when OOSEQ/SACK blocks were not changing. Definitely a trade off of using memory to cache the result versus doing more CPU calculations. I'll have to defer to Simon for which is more lightweight

Joel Cunningham <jcunningham>
Group Member
Wed 28 Jun 2017 08:27:12 PM UTC, comment #16: 


> I think for our "lw" thing, 1) would be best.


This is certainly the most lightweight option. And as a bonus, it doesn't limit the MSS, meaning better throughput.

> However, that would also mean we would have to send empty ACKs when SACKs are to be send. We currently avoid this and piggy-back the ACK on data if there's data to be sent - that would have to be changed.


ACKs are already sent right away if the packet received is out of sequence (or out of receive window).
But it should be easy to always send empty ACKs when there are some SACKs.

Jakub Schmidtke <jschmidtke>
Wed 28 Jun 2017 08:04:28 PM UTC, comment #15: 

Re comment #11:
I think for our "lw" thing, 1) would be best. Both 2) and 3) mean limiting the MSS (with the only difference of transfering NOPs).

What I don't get is why the writers of that RFC don't talk about this. Because they do talk about transmitters keeping segments pre-packed on a list, so they should be aware of the MSS size problem that limits us in adding/removing SACK options in data segments...

Simon Goldschmidt <goldsimon>
Group administrator
Wed 28 Jun 2017 08:00:44 PM UTC, comment #14: 

This response comes kind of late but...

> To not violate MSS while adding SACKs to full packets would
> mean not sending all of that packet's payload.
> It feels like a nightmare from segment management perspective.


Given that and reading the RFC, I feel sending the SACKs in empty ACKs could be good enough. The RFC clearly separates receiver and transmitter...

However, that would also mean we would have to send empty ACKs when SACKs are to be send. We currently avoid this and piggy-back the ACK on data if there's data to be sent (by letting 'tcp_ack()' set "pcb->flags |= TF_ACK_NOW") - that would have to be changed.

Simon Goldschmidt <goldsimon>
Group administrator
Wed 28 Jun 2017 08:00:34 PM UTC, comment #13: 


> However, the idea of somehow combining the ooseq list with the SACK list does make sense! Maybe we could think more about it in that direction.


One solution could be to calculate SACKs dynamically by examining the ooseq list.
To do that, we would need to store some time data (or a value of a counter stored somewhere
and incremented every time we get a TCP packet) in each TCP segment (to determine the order of SACKs),
and traverse the entire ooseq list before sending each packet.

Jakub Schmidtke <jschmidtke>
Wed 28 Jun 2017 07:46:13 PM UTC, comment #12: 

Re comment #10:

> Would it make more sense to have a MEMP_SACK_BLOCK?


Not a bad idea. However what I dislike about it is that we can come into a situation where we fail to allocate such a SACK region. Memp allocation might be slower than using the array, but all that array-moving code is not fast, either...

However, the idea of somehow combining the ooseq list with the SACK list does make sense! Maybe we could think more about it in that direction.

Simon Goldschmidt <goldsimon>
Group administrator
Wed 28 Jun 2017 07:32:44 PM UTC, comment #11: 

I could modify the way SACKs are stored, if using a memp approach is preferred.
That would (I assume) remove the complexity of removing entries from the SACKs list,
but inserting new entries is not that complex to begin with.
I am assuming the max length of a list of SACKs to hold for a single PCB should still be limited (but could be higher than 4).

But this just changes the way SACKs are stored in PCBs, and doesn't solve the main problem,
which at the moment seems to be inserting SACKs into data packets.

I am assuming that violating MSS is not acceptable, and sending only parts of payload of some of the packets
doesn't really make sense.

So I see three approaches:

1. Sending SACKs only in empty ACK packets. This violates the RFC (I think), but maybe it is acceptable.

2. Making MSS lower to make room for max number of SACKs, and padding the header with zeroes (or NOPs)
   if there is no need to send any SACKs. This is very straightforward and would result in the simplest code,
   but it wastes up to 36 bytes per each TCP data packet - and I'm not sure if that's OK. It also lowers the throughput by using smaller MSS.

3. Making MSS lower to make room for max number of SACKs, but only include those SACKs if we want to send any.
   This lowers the throughput (by making MSS smaller), but doesn't waste bytes.
   However, to achieve that, there has to be additional space reserve for the TCP header, and that header may have to be moved back and forth.
   And given that SACK option would be padded, that shifting would by by 12, 20, 28 or 36 bytes one way or the other.
   I don't know enough about memory models and alignment in lwIP to determine if that could cause any problems.

So the question is: What makes most sense and which approach should I take?



Jakub Schmidtke <jschmidtke>
Wed 28 Jun 2017 02:11:51 PM UTC, comment #10: 


> Now if that array had 5 entries (or more) that were valid SACKs, filling one gap would leave us with 4 SACKs that could be included.

This is because we don't calculate them dynamically, but rather when new data packets are received.

I got to thinking about this and how there is a decent amount of complexity managing the rcv_sacks array (tracking inuse/free slots, shifting entries up/down, inserting new entries, etc) and thought we already have infrastructure (in LwIP) for managing memory in this manner; the memory pools.

Would it make more sense to have a MEMP_SACK_BLOCK?  Then maintain a linked list in each pcb that has SACKs enabled and has entries on the OOSEQ queue.

This would allow much simpler insertion removal since it's a linked list and inuse/free tracking is provided by the memp abstraction.  This could potentially provide better memory usage as each pcb doesn't have to have spots for 4 SACK blocks in their pcb.  It would also allow individual pcbs to have more than 4 SACK blocks since they are allocated from a general pool

In some cases (each PCB claims MAX SACK blocks) it could use more memory compared to implementation in your patch since we would need to add an extra next pointer to the SACK block and the overhead from the memory pool structure, but I'd imagine this wouldn't be the normal case

Is this more inline with how LwIP uses memory?  I can't think of an existing case where an array is used directly like rcv_sacks is

Joel Cunningham <jcunningham>
Group Member
Tue 27 Jun 2017 07:58:14 PM UTC, comment #9: 

The comment is wrong. It's because I originally kept SACKs as an u32[8] array (with mixed left,right,left,right,...) edges,
but it was cleaner to hold an array of structs with 'left' and 'right' fields. I will fix the comment.

I will fix the spacing.

I don't think reducing TCP_MAX_SACK_NUM based on LWIP_TCP_TIMESTAMPS define makes sense.
Even if it is defined, we may not negotiate it use (if the other side doesn't support or want it),
in which case the timestamps will not be included.

On the other hand, keeping more SACKs (even more than 4) may be useful.
We only include up to 4 SACKs in packets, but additional SACK entries provide more context.
If we have 4 individual SACK ranges, and incoming data packet fills a gap between two of them, we will have 3 SACKs.
If the size of the array is 4, we will only include up to 3 SACKs.

Now if that array had 5 entries (or more) that were valid SACKs, filling one gap would leave us with 4 SACKs that could be included.
This is because we don't calculate them dynamically, but rather when new data packets are received.

We could also recalculate SACKs whenever we remove some, but this would not preserve the "more recent first" order of SACK entries.


Jakub Schmidtke <jschmidtke>
Tue 27 Jun 2017 07:33:55 PM UTC, comment #8: 

Jakub,

I've done a cursory review of the patch, found a couple of minor things:


+  /* Now 'unused_idx' is the index of the first invalid SACK entry,
+     anywhere between 0 (no valid entries) and 8 (all entries are valid).

Shouldn't the maximum be 4 based on the comment in opt.h and my understanding that there is only space for 4 SACK entries in the TCP options?


+    if (TCP_SEQ_LEQ(pcb->rcv_sacks[i].right,left) || TCP_SEQ_LEQ(right, pcb->rcv_sacks[i].left)) {

I found a couple instances like this above where parameters were not separated by a space (the convention in LwIP code)

Should we also be reducing TCP_MAX_SACK_NUM to 3 (programmatically) if LWIP_TCP_TIMESTAMPS is enabled?  Page 3 of RFC 2018 mentions SACKS being reduced to a maximum of 3 when timestamps are also enabled

I'll continue to look at the patch more as time permits

Joel Cunningham <jcunningham>
Group Member
Tue 27 Jun 2017 06:11:34 PM UTC, comment #7: 

Reserving space for SACKs simplifies memory management a lot. However, it means that each data packet that does not have SACKs wastes up 36 bytes (max 4 SACKs take 8 bytes, plus 2 bytes for option header, plus 2 bytes of padding to ensure proper alignment). Is it OK to do that?

To not violate MSS while adding SACKs to full packets would mean not sending all of that packet's payload.
It feels like a nightmare from segment management perspective.

Another solution would be to send SACKs only in empty ACK packets (just like this patch does right now).
I feel like this violates the RFC: "If the data receiver generates SACK options under any circumstance,
it SHOULD generate them under all permitted circumstances."

Yet another solution would be to always limit the payload size (as if SACKs were included in each packet),
but only add them if necessary (so packets without SACKs would be slightly smaller, but without empty NOPs/zero padding).
This would also require moving the TCP header, but would not violate the MSS.

Jakub Schmidtke <jschmidtke>
Tue 27 Jun 2017 05:40:30 PM UTC, comment #6: 


> About the alignment and MACs...


For this, it's worth to know that Mac/DMa-Alignment != MEM_ALIGNMENT! We don't have that implemented yet, but it's on the roadmap. Some systems have a larger alignment requirement and for them, we would need to know the exact space required for all headers when allocating.

On the other hand, many MACs (or drivers) don't support scatter-gather, so having a frame in one pieces requires memcpy.

In any case, ideas like moving the TCP header don't really work, since we must obey the MSS. So we could as well transmit 32 bytes of NOPs (at max.) instead to have room for SACK regions...?

Simon Goldschmidt <goldsimon>
Group administrator
Tue 27 Jun 2017 06:57:38 AM UTC, comment #5: 

The problem with SACKs in data packets is that the size of the TCP header is calculated when the data segment is created.
By the time it's actually sent out, the number of SACKs to include may change. It may even be different the next time the same packet gets re-transmitted...
With empty ACKs there is no such problem...

About the alignment and MACs... could you please elaborate? What's the difference between allocating space for SACKs in advance,
versus changing it later (assuming SACK options would be padded to 4 bytes boundary)?
Is there a difference between reserving some payload bytes at the beginning (as it's done for regular options right now),
and changing the header size (the "transport" layer passed to pbuf allocation)?

The other idea I had, was to always allocate TCP segments as two pbufs - one for the header, and one for the data
(just like it's done when the "copy data" flag is not passed to tcp_write). When sending, I could actually create a brand new
pbuf for TCP header and required number of SACKs, copy the original over, and concat it with the data payload...

I will add the LWIP_ prefix to the define's name.
The idea was to add full support, hence the current name.
Maybe I could use the other name, and rename it once there is full support?

Jakub Schmidtke <jschmidtke>
Tue 27 Jun 2017 06:41:38 AM UTC, comment #4: 

From what I read, the pbuf allocation is the limitation why you only include SACKs in empty ACKs? I would have thought it's the memory allocation (calculate the SACKs on the fly and send them out directly), but reading the patch, you added the info to the tcp pcb, so it should work.

The allocation of headers might be tricky though, especially with zero-copy MACs where the start of the ethernet header must meed a specific alignment requirement. You can't just move the tcp header in this case. But sending a bunch of NOPs limits performance again...

Oh, and given the fact that only outgoing SACKs are supported, you could change the opt.h define from "TCP_SACK" to "LWIP_TCP_SACK_OUT" (please put "LWIP_" in front of new defines to prevent possible name clash with other sources!).

Simon Goldschmidt <goldsimon>
Group administrator
Mon 26 Jun 2017 04:26:58 PM UTC, comment #3: 

I saw this improve the performance while downloading files over a high bandwidth link with somewhat higher latency (around 100ms).
By "downloading" I mean that lwIP is on the receiving end, and it receives most of the data over the connection.
I'm not sure about the timers, but from monitoring the traffic it looks like the speed goes up, until something gets lost.
Then there are thousands of duplicate ACKs being sent by lwIP which keeps getting out of order packets.
Eventually wireshark signals "end of receive window", and the transfer slows down to 1 packet each RTT.
It is able to recover, after a while, until there are more losses and the scenario repeats itself.
I have actually seen the similar behaviour of the native TCP stack with SACKs disabled.

This patch adds support for lwIP to include SACKs in outgoing ACK packets.
So it improves the way it reports back to the sender.

For now it only includes SACKs in empty ACK packets, and not in data packets.
However, I'm pretty sure I know how to add SACKs to data packets as well.
I think that there should be a bit more data reserved for headers while TCP segments are created,
and while they are being sent back and SACKs need to be added (or removed), the TCP header
at the beginning of the packet could be moved (to create more space for SACK options,
or to remove SACK options that are no longer needed).

It also does not add support for lwIP to handle SACKs received from the other side,
but I haven't looked into that yet.

Jakub Schmidtke <jschmidtke>
Mon 26 Jun 2017 02:44:39 PM UTC, comment #2: 

I can help spin up on SACKS support and hopefully provide some review feedback

Jakub,

I'm curious about the case where this improves performance?  Is it for cases where there are enough dropped segments that fast retransmission is no longer signaling and you have to wait for the RTO timer?

Does the patch allow LwIP to SACK the remote TCP or is this for allowing our transmissions to be SACK'd by the remote TCP?

Joel Cunningham <jcunningham>
Group Member
Wed 21 Jun 2017 08:04:19 PM UTC, comment #1: 

Without having the time to look at the patch file, I'd greatly appreciate having SACK support. I know it's not 'lw' any more then, but I think we should have it as well.

(We do need some decent configuration options though to select between "lw/small" defaults and "performance" defaults for opt.h settings...)

Simon Goldschmidt <goldsimon>
Group administrator
Wed 21 Jun 2017 06:47:55 PM UTC, original submission:  

This patch adds partial SACK (RFC 2018) support.
It is limited to including SACK ranges in outgoing empty ACK packets.

In my tests it makes a huge performance difference for downloads over higher latency links.
However, it does not add support for handling incoming SACK values.
It also does not include SACK ranges in outgoing packets with payload.
As such, this may not be ready to be actually included yet.

I would like to get some feedback about this.
Is it something that lwIP community would be interested in merging?
Am I doing things the right way?
Finally, would the full support be required to merge anything,
or maybe even partial support like this is useful and could be merged?

Thanks!

Jakub Schmidtke <jschmidtke>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #41078:  0001-Partial-SACK-RFC-2018-support_v3.patch added by jschmidtke (26KiB - text/x-patch - Updated SACK patch)
file #41077:  0001-Partial-SACK-RFC-2018-support_v2.patch added by jschmidtke (25KiB - text/x-patch - Updated SACK patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jcunningham (Posted a comment)
  • -email is unavailable- added by goldsimon (Posted a comment)
  • -email is unavailable- added by jschmidtke (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-07-27 goldsimon CategoryNone TCP
        StatusNone Done
        Open/ClosedOpen Closed
    2017-06-29 jschmidtke Attached File- Added 0001-Partial-SACK-RFC-2018-support_v3.patch, #41078
    2017-06-29 jschmidtke Attached File- Added 0001-Partial-SACK-RFC-2018-support_v2.patch, #41077
    2017-06-21 jschmidtke Attached File- Added 0001-Partial-SACK-support.patch, #41016

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code