lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date:	Wed,  8 Oct 2008 16:27:48 -0400
From:	Vlad Yasevich <vladislav.yasevich@...com>
To:	netdev@...r.kernel.org
Cc:	davem@...emloft.net, linux-sctp@...r.kernel.org
Subject: [PATCH net-next 0/2] sctp: Improve the tsn_map

The following two patches improve the TSN map implementation in sctp.
The TSN map is used to track which TSNs (transmission sequence numbers) we
received.  The way it's currently written, we have a 4K array of bytes
where each byte represents the TSN.  When we receive a TSN we mark the
corresponding byte and then run through an algorithm to update the
ack points.

This is grossely inefficient in both memory and code.  The only time it
makes sense to mark the TSN in the map is if it's out of order.  In-order
tsns can simply move the ack point and be done with it.  Also, since this
is a simple a 1 or 0 (we have the TSN or we do not), we can do all this
with bitmaps and shrink our map by a factor of 8.  Further more,
it is hightly unlikely that we are every going to see 2 out of order
number with a difference/gap of 4096.  So, we can start our map at
the optimum size of a long word (32 or 64 bits depending on architecure).
We can then grow the map in the unlikely event that we receive a gap
that will push us outside of the map.  On a low loss network, fast
retransmis will prevent that before the map grows to much.

Running netperf shows a tiny improvement, but it's very stable, ie.
it's the same 3% across 10.  It also shows about 1% reduction is
CPU utilization.

The second patch gets rid of the rather useless member of the tsn_map
and was done after the bulk of the work above.  It became more obvious
that the structure member was useless after all the clean up.

Please consider for 2.6.28.

Thanks
-vlad
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists