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

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

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

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.

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 :-)

> Sounds to go me as well!

Correction: "sounds good to me as well"

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

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...)?

>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

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...

> 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.

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?

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.

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.

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?

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.

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...)