kernel & add-ons: Adjustments to use DoublyLinkedList::InsertBefore.

The Insert(before, element) function has been marked deprecated since
2010, but still had many usage and kept accumulating more. It's long
past time we got rid of all them and actually deprecated the function
itself.

Insert(before, element) just calls InsertBefore, so no functional change.

tcp: fix trace build for BufferQueue

Change-Id: Iab502bdff3da23dff74972e6c480e0784ab3f4dd
Reviewed-on: https://review.haiku-os.org/c/haiku/+/3905
Reviewed-by: Alex von Gluck IV <kallisti5@unixzen.com>

tcp: rfc 2018: implemented SACK option

Change-Id: I269ad2682446c4d37bae21dcf9f3036de964ff2c
Reviewed-on: https://review.haiku-os.org/c/haiku/+/53
Reviewed-by: Jérôme Duval <jerome.duval@gmail.com>

tcp: Remove sanity checks from BufferQueue in release builds

Each TCPEndpoint has two BufferQueue members, one for the send queue
and one for the receive queue.

If DEBUG_BUFFER_QUEUE is enabled, then most methods of BufferQueue
call BufferQueue::Verify(), sometimes twice. This member function
performs some sanity checking which requires iterating through every
net_buffer in the queue.

Disabling this in a debug build improved throughput by a factor of 5x
over the loopback interface on my laptop. Using iperf the measured
throughput went from 900Mbps to around 4.8Gbps.

This patch turns this sanity checking off for release builds.

* Rename DEBUG_BUFFER_QUEUE to DEBUG_TCP_BUFFER_QUEUE
* Change the default in BufferQueue.h to disabled
* Set DEBUG_TCP_BUFFER_QUEUE to KDEBUG_LEVEL_2 in
kernel_debug_config.h

Change-Id: I262dac5d7e2889d2942bbdcf6b667cc0cbafa4c8
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2780
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

Revert "tcp: rfc 2018: implemented SACK option"

This reverts commit 5c31f5a67a0aa37c8f2a1464252b2c5b0a959f33.

tcp: rfc 2018: implemented SACK option

Signed-off-by: Jessica Hamilton <jessica.l.hamilton@gmail.com>

Fixed up network stack and drivers for x86_64.

* Various compilation fixes.
* Fixes to the FreeBSD compatibility layer (from comparing the x86-
specific bits with the equivalent amd64 sources in FreeBSD).
* Compile all the Ethernet drivers except for sis900 and wb840, these
require a bit more work to fix (will file a ticket soon). Tested
ipro1000 and rtl81xx, no issues.

* BufferQueue::Free() no longer will return negative values. As is, the max
bytes restriction is only a soft limit. This fixes stalling TCP connections
because everything received would be out of window once this happened.
* Added a TODO to look into TCP's window management - it doesn't seem to be
right.
* Fixed build with tracing turned on.
* Made the fNumber member of tcp_sequence private.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35468 a95241bf-73f2-0310-859d-f6bbb57e9c96

bonefish + axeld:
* There was one incorrect check in BufferQueue::Get() that happened because
the wrong operator was used due to the uint32 cast operator.
* Consequently, we removed the uint32 cast operator, and changed the code
to deal with this. Fortunately, no other bugs were observed.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@29928 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Fixed one more case of a resulting 0 byte buffer. Also added a test case for
it to the test app. This finally fixes ticket #2594.
* Of course, I neither saw this one before, nor did I accidently reproduce it
with a test :-)


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28967 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Turns out the assert was wrong; since the previous buffer can be adjacent to
the next buffer, it can also cause the new buffer to start at the same
sequence as the next buffer.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28958 a95241bf-73f2-0310-859d-f6bbb57e9c96

* The check to remove bytes at the beginning happened twice.
* There was an off-by-one error that could well be responsible for bug
#2594. Haven't tested it yet, though.
* Added an extra assert to make sure that "next" is set correctly.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28937 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Fixed a few more problems that the test application revealed. This should
also close #2594.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28883 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Applied most parts of Adrian's patch in #2594, applied our coding style.
* Cleaned the net_buffer::sequence handling, and fixed a few more problems of
maintaining it in Add().
* Extended Verify() to check everything that's possible, and call it
conditionally on several places, depending on DEBUG_BUFFER_QUEUE. It's turned
on for now which means that any remaining problems should show up when they
happened.
* Call Dump() from TCPEndpoint::Dump().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28878 a95241bf-73f2-0310-859d-f6bbb57e9c96

* BufferQueue::Get(size_t ...) now always returns successfully if it does not
return an empty buffer. This should avoid losing data in case not everything
could be appended due to a resource shortage.
* Also, it now assures that fNumBytes and fContiguousBytes are always
maintained correctly, thanks to Adrian for pointing this out! This should
fix bug #2594.
* Added extra debug code to BufferQueue::RemoveUntil() so that it checks
whether or not fContiguousBytes could be maintained correctly (ie. if this
function is called only as thought).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28859 a95241bf-73f2-0310-859d-f6bbb57e9c96

CID 26: The status variable was shadowed inside the while loop causing the outer
status to always be B_OK, resulting in an incomplete buffer instead of an error
if the append failed.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27469 a95241bf-73f2-0310-859d-f6bbb57e9c96

* If a new buffer had its last part in common with an existing larger buffer,
BufferQueue::Add() tried to remove a negative amount of bytes. This could
bring a download to a complete halt (as could the other one due to the list
link mixup).
* While the RTT computation still seems to work not that good (with a drop quote
of 50% I would easily reach retransmit timeouts of 80 secs), TCP should now
work a lot better on a flaky connection.
* Renamed _GetMSS() to _MaxSegmentSize().
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@22677 a95241bf-73f2-0310-859d-f6bbb57e9c96

more TCP fixes, we should now be able to send large amounts of data through congestioned links.

- fixed BufferQueue's RemoveUntil.
- reset SND.NXT on third duplicate ACK (fast retransmit).
- on retransmit reset SND.NXT to SND.UNA (it will be updated back when we get good ACKs).
- fixed effective window calculation.
- relaxed SWS checking a bit, don't send partial packets on retransmission as the window might have been reduced due to congestion.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@20769 a95241bf-73f2-0310-859d-f6bbb57e9c96

fixed multiple TCP issues.

- Moved FIN handling to after Segment Text handling, it matches the RFC and fixes a possible issue with a user missing some final segment data when receiving a FIN.
- Fixed the FIN handling to better terminate connections (no more senseless chatter in the end with RSTs etc).
- When Bind()ing, set the socket address so a call to getsockname() gets the allocated port correctly.
- After reaching the ESTABLISHED state, try to wake all pending threads (still needs work).
- Corrected the maximum amount of time we wait in SendData() to respect socket->send.timeout.
- Now ReadData() behaves correctly in all possible states.
- There was a missing handling of MSG_DONTWAIT, fixed.
- Better internal handling of PSH.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@20624 a95241bf-73f2-0310-859d-f6bbb57e9c96

keep PUSH'ed pointer in receiver side of TCP so we can wait for more data in recv()


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@20569 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Add() did not add fNumBytes in case of an out of order packet, causing all kinds of
hickups on TCP connections.
* Added a bit more of debug output to Add().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19817 a95241bf-73f2-0310-859d-f6bbb57e9c96

Calmed down the networking stack a lot - since it basically works, there is no
reason to slow it down with debug output that much; this will also help investigating
some issues where you just aren't interested in most of the output.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19672 a95241bf-73f2-0310-859d-f6bbb57e9c96

Before freeing "next", it should have been removed already...


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19422 a95241bf-73f2-0310-859d-f6bbb57e9c96

* TCPConnection::SendData() now waits until there is enough free space in
the send queue (however, if the buffer sent is larger than the maximum
buffer, it will just hang for now...). The check is also not thread-safe.
* BufferQueue::Get() did not correctly maintain the fFirstSequence member
in remove mode.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19403 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Reintroduced the accept semaphore: it will be inherited by the new connections
of a LISTEN socket.
* Reading data should now more or less work, too.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19401 a95241bf-73f2-0310-859d-f6bbb57e9c96

More work-in-progress:
* Added some timer methods
* Fixed removing the connection too early (and thus replying with a RST instead of nothing
when the peer acknowledged our FIN).
* BufferQueue::RemoveUntil() did not bump the buffer's sequence
* Delayed acknowledge, and retransmitting should work now (the latter is *very* basic
right now)
* Completed TCPConnection::_ShouldSendSegment()
* fReceiveNext was always updated on a received buffer, even if there was a buffer
missing.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19396 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Renamed _SendQueuedData() to _SendQueued(), and made it independent from the
"flags" parameter - this can't be used with retransmitting anyway, and since
the flags are actually fixed per state, the previous solution didn't really
make much sense.
* Made _SendQueued() work a lot more like BSD's tcp_output().
* We can now send even large buffers that need more than one segment at once.
* Added a simple recursive locking mechanism for now - this should be done
differently, though, as we want to have good performance in full duplex mode.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19384 a95241bf-73f2-0310-859d-f6bbb57e9c96

Some more work-in-progress:
* the TCPConnection::Receive() method is now more or less working as it should;
of course, there are a number of missing things (like round-trip time estimation,
retransmit timers, receive window update, ...).
* reply_with_reset() was broken, and accidently always send the segment it should
answer with reset... (causing an endless loop during connect)
* BufferQueue::RemoveUntil() must always set the fFirstSequence member to the new
sequence, or you will never be able to send anything with that queue (as the
data in it would be no longer contiguous).
* connects, sendings (only single segments), and receiving data is working now
basically (but very incomplete); retransmits or even subsequent transmits (if
the data to be sent doesn't fit in one segment) doesn't work yet, so you better
don't lose any segments :-)


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19378 a95241bf-73f2-0310-859d-f6bbb57e9c96

Work-in-progress on TCP:
* Changed the implementation to be more BSD like; state variables are now
the same set as usual.
* The BufferQueue didn't use the initial sequence correctly (problems with
SYN sequence).
* It now also removes data out of the current data set (ie. data that was
already read by the application).
* BufferQueue::Get() also didn't work correctly (the version used by sending
data).
* Fixed various issues around the code like incorrect handling of unexpected
data.
* TCP options don't need the end-of-options marker in case they fill up the
data already, also, the end-of-options marker doesn't need to be padded.
* Options are now only processed during SYN - other options may come
later (timestamps are candidate number one).
* Also broke what was working before: connections do no longer work!


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19376 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Added a helper class tcp_sequence which hides the semantics of comparing sequences
(this was completely broken in the code before).
* Wrote a buffer queue class to replace the previous algorithm - instead of merging
all buffers together, they're kept in a list, so that the most work will be done
in the application's thread and only very little when the data is received; maybe
we should add an append_move() function to net_buffer, and use that instead,
though, to keep the number of fragments small.
* The advertised receive window is now bound to 65535, the receive window shift
is correctly computed, but not yet used.
* The new buffer queue is now also responsible for the send buffer.
* TCPConnection::ListenReceive() used the wrong address to retrieve the target route.
* Fixed TCPConnection::ReadData() to also return data when the connection is already
closed, and to wait if the connection is not yet established (in SO_NONBLOCK mode);
it still doesn't wait until data is available, though...


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19372 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed up network stack and drivers for x86_64.

* Various compilation fixes.
* Fixes to the FreeBSD compatibility layer (from comparing the x86-
specific bits with the equivalent amd64 sources in FreeBSD).
* Compile all the Ethernet drivers except for sis900 and wb840, these
require a bit more work to fix (will file a ticket soon). Tested
ipro1000 and rtl81xx, no issues.

* BufferQueue::Free() no longer will return negative values. As is, the max
bytes restriction is only a soft limit. This fixes stalling TCP connections
because everything received would be out of window once this happened.
* Added a TODO to look into TCP's window management - it doesn't seem to be
right.
* Fixed build with tracing turned on.
* Made the fNumber member of tcp_sequence private.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35468 a95241bf-73f2-0310-859d-f6bbb57e9c96

bonefish + axeld:
* There was one incorrect check in BufferQueue::Get() that happened because
the wrong operator was used due to the uint32 cast operator.
* Consequently, we removed the uint32 cast operator, and changed the code
to deal with this. Fortunately, no other bugs were observed.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@29928 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Fixed one more case of a resulting 0 byte buffer. Also added a test case for
it to the test app. This finally fixes ticket #2594.
* Of course, I neither saw this one before, nor did I accidently reproduce it
with a test :-)


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28967 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Turns out the assert was wrong; since the previous buffer can be adjacent to
the next buffer, it can also cause the new buffer to start at the same
sequence as the next buffer.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28958 a95241bf-73f2-0310-859d-f6bbb57e9c96

* The check to remove bytes at the beginning happened twice.
* There was an off-by-one error that could well be responsible for bug
#2594. Haven't tested it yet, though.
* Added an extra assert to make sure that "next" is set correctly.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28937 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Fixed a few more problems that the test application revealed. This should
also close #2594.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28883 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Applied most parts of Adrian's patch in #2594, applied our coding style.
* Cleaned the net_buffer::sequence handling, and fixed a few more problems of
maintaining it in Add().
* Extended Verify() to check everything that's possible, and call it
conditionally on several places, depending on DEBUG_BUFFER_QUEUE. It's turned
on for now which means that any remaining problems should show up when they
happened.
* Call Dump() from TCPEndpoint::Dump().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28878 a95241bf-73f2-0310-859d-f6bbb57e9c96

* BufferQueue::Get(size_t ...) now always returns successfully if it does not
return an empty buffer. This should avoid losing data in case not everything
could be appended due to a resource shortage.
* Also, it now assures that fNumBytes and fContiguousBytes are always
maintained correctly, thanks to Adrian for pointing this out! This should
fix bug #2594.
* Added extra debug code to BufferQueue::RemoveUntil() so that it checks
whether or not fContiguousBytes could be maintained correctly (ie. if this
function is called only as thought).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28859 a95241bf-73f2-0310-859d-f6bbb57e9c96

CID 26: The status variable was shadowed inside the while loop causing the outer
status to always be B_OK, resulting in an incomplete buffer instead of an error
if the append failed.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27469 a95241bf-73f2-0310-859d-f6bbb57e9c96

* If a new buffer had its last part in common with an existing larger buffer,
BufferQueue::Add() tried to remove a negative amount of bytes. This could
bring a download to a complete halt (as could the other one due to the list
link mixup).
* While the RTT computation still seems to work not that good (with a drop quote
of 50% I would easily reach retransmit timeouts of 80 secs), TCP should now
work a lot better on a flaky connection.
* Renamed _GetMSS() to _MaxSegmentSize().
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@22677 a95241bf-73f2-0310-859d-f6bbb57e9c96

more TCP fixes, we should now be able to send large amounts of data through congestioned links.

- fixed BufferQueue's RemoveUntil.
- reset SND.NXT on third duplicate ACK (fast retransmit).
- on retransmit reset SND.NXT to SND.UNA (it will be updated back when we get good ACKs).
- fixed effective window calculation.
- relaxed SWS checking a bit, don't send partial packets on retransmission as the window might have been reduced due to congestion.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@20769 a95241bf-73f2-0310-859d-f6bbb57e9c96

fixed multiple TCP issues.

- Moved FIN handling to after Segment Text handling, it matches the RFC and fixes a possible issue with a user missing some final segment data when receiving a FIN.
- Fixed the FIN handling to better terminate connections (no more senseless chatter in the end with RSTs etc).
- When Bind()ing, set the socket address so a call to getsockname() gets the allocated port correctly.
- After reaching the ESTABLISHED state, try to wake all pending threads (still needs work).
- Corrected the maximum amount of time we wait in SendData() to respect socket->send.timeout.
- Now ReadData() behaves correctly in all possible states.
- There was a missing handling of MSG_DONTWAIT, fixed.
- Better internal handling of PSH.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@20624 a95241bf-73f2-0310-859d-f6bbb57e9c96

keep PUSH'ed pointer in receiver side of TCP so we can wait for more data in recv()


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@20569 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Add() did not add fNumBytes in case of an out of order packet, causing all kinds of
hickups on TCP connections.
* Added a bit more of debug output to Add().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19817 a95241bf-73f2-0310-859d-f6bbb57e9c96

Calmed down the networking stack a lot - since it basically works, there is no
reason to slow it down with debug output that much; this will also help investigating
some issues where you just aren't interested in most of the output.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19672 a95241bf-73f2-0310-859d-f6bbb57e9c96

Before freeing "next", it should have been removed already...


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19422 a95241bf-73f2-0310-859d-f6bbb57e9c96

* TCPConnection::SendData() now waits until there is enough free space in
the send queue (however, if the buffer sent is larger than the maximum
buffer, it will just hang for now...). The check is also not thread-safe.
* BufferQueue::Get() did not correctly maintain the fFirstSequence member
in remove mode.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19403 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Reintroduced the accept semaphore: it will be inherited by the new connections
of a LISTEN socket.
* Reading data should now more or less work, too.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19401 a95241bf-73f2-0310-859d-f6bbb57e9c96

More work-in-progress:
* Added some timer methods
* Fixed removing the connection too early (and thus replying with a RST instead of nothing
when the peer acknowledged our FIN).
* BufferQueue::RemoveUntil() did not bump the buffer's sequence
* Delayed acknowledge, and retransmitting should work now (the latter is *very* basic
right now)
* Completed TCPConnection::_ShouldSendSegment()
* fReceiveNext was always updated on a received buffer, even if there was a buffer
missing.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19396 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Renamed _SendQueuedData() to _SendQueued(), and made it independent from the
"flags" parameter - this can't be used with retransmitting anyway, and since
the flags are actually fixed per state, the previous solution didn't really
make much sense.
* Made _SendQueued() work a lot more like BSD's tcp_output().
* We can now send even large buffers that need more than one segment at once.
* Added a simple recursive locking mechanism for now - this should be done
differently, though, as we want to have good performance in full duplex mode.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19384 a95241bf-73f2-0310-859d-f6bbb57e9c96

Some more work-in-progress:
* the TCPConnection::Receive() method is now more or less working as it should;
of course, there are a number of missing things (like round-trip time estimation,
retransmit timers, receive window update, ...).
* reply_with_reset() was broken, and accidently always send the segment it should
answer with reset... (causing an endless loop during connect)
* BufferQueue::RemoveUntil() must always set the fFirstSequence member to the new
sequence, or you will never be able to send anything with that queue (as the
data in it would be no longer contiguous).
* connects, sendings (only single segments), and receiving data is working now
basically (but very incomplete); retransmits or even subsequent transmits (if
the data to be sent doesn't fit in one segment) doesn't work yet, so you better
don't lose any segments :-)


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19378 a95241bf-73f2-0310-859d-f6bbb57e9c96

Work-in-progress on TCP:
* Changed the implementation to be more BSD like; state variables are now
the same set as usual.
* The BufferQueue didn't use the initial sequence correctly (problems with
SYN sequence).
* It now also removes data out of the current data set (ie. data that was
already read by the application).
* BufferQueue::Get() also didn't work correctly (the version used by sending
data).
* Fixed various issues around the code like incorrect handling of unexpected
data.
* TCP options don't need the end-of-options marker in case they fill up the
data already, also, the end-of-options marker doesn't need to be padded.
* Options are now only processed during SYN - other options may come
later (timestamps are candidate number one).
* Also broke what was working before: connections do no longer work!


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19376 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Added a helper class tcp_sequence which hides the semantics of comparing sequences
(this was completely broken in the code before).
* Wrote a buffer queue class to replace the previous algorithm - instead of merging
all buffers together, they're kept in a list, so that the most work will be done
in the application's thread and only very little when the data is received; maybe
we should add an append_move() function to net_buffer, and use that instead,
though, to keep the number of fragments small.
* The advertised receive window is now bound to 65535, the receive window shift
is correctly computed, but not yet used.
* The new buffer queue is now also responsible for the send buffer.
* TCPConnection::ListenReceive() used the wrong address to retrieve the target route.
* Fixed TCPConnection::ReadData() to also return data when the connection is already
closed, and to wait if the connection is not yet established (in SO_NONBLOCK mode);
it still doesn't wait until data is available, though...


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19372 a95241bf-73f2-0310-859d-f6bbb57e9c96