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  linux-hardening  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:	Fri, 16 Mar 2007 16:39:57 +0200
From:	"Ilpo Järvinen" <>
Cc:	David Miller <>
Subject: [RFC PATCH 0/5] LOST marking rewrite

This patchset provides new LOST detection algorithm. This is part
of tcp_sock diet program. Removes couple of hints, sadly enough this
is a tradeoff as one u32 is necessary for the new algorithm even though
most of the time the last SACK would give all necessary information.

It might be useful to add unlikely to the rexmit hint clearing since
it really shouldn't happen except very very rarely if ever. And maybe
also the !tp->sacked_out.

I think I have introduced a small problem to the timedout thingie,
however, we can work around that by faking highest_sack to a higher
value if timed out loop advances too far to avoid (potentially expensive)
walking... So that it would be highest_sacked_or_lost (or highest_marked,

I tested v4 and found the off-by-one error (though CBI bit me and I'll
disable it for now on to run cleaner test sets without CBI effects).

    v3-to-v4 changes:
     - Fixed FACK off-by-one error that was introduced in v3 change
     - Provided RFC3517 SACK as a separate patch
     - Added "a fastpath" optimization
     - Restructured the algorithm to get it cleaner
     - Decided that there isn't a clear way to handle R without L frames
       timedout thingie above the reord marking (the old code is quite
       impossible to follow anyway as does not have any reliable invariants
       because the timestamps change when -> R transition occurs). Besides,
       such case is probably too marginal one to do something expensive.
       Depending on the hint state, the results could be vastly different
       in the old algo. Thus I did go for a straight forward way: if we have
       a timed out skb, the remaining will also timeout (this could also be
       seen as ok defination since R without L should be made R|L at some
       point!). It could be possible to have some invariants for this if
       there is cheap way to access the skb right after the last rexmit skb
       (I have intentionally avoided hint usage since we're hopefully going
       to farewell them).
     - Handle !sacked_out case correctly
     - Guarantee highest_sack in sync only when sacked_out > 0
     - Rebased to a recent net-2.6.22 (couple of space changes hit the
       removed area & RB-tree fixes were done)
    v2-to-v3 changes:
     - Replace of skipping made worries in it obsolete and now really
       one skb less is traversed (was promised in v2)
    v1-to-v2 changes:
     - Changes non-fack SACK to something less broken; not a complete
       set of changes (other functions should also be fixed)
     - Fixed NewReno bugs
     - More comments & added RFCs to places I'm unsure of
     - Delayed reord_count increment (traverses now one skb less)
     - Copied retransmit_hint clearing from the original but I
       think it's superfluous
     - Separated highest_sack to own patch
     - Fixed off-by-one bug in skipping

To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to
More majordomo info at

Powered by blists - more mailing lists