On Thu, Apr 25, 2002 at 09:26:05PM +0200, Ignatios Souvatzis wrote:
> On Thu, Apr 25, 2002 at 12:17:16PM +0300, Tero Kivinen wrote:
> > 
> > That is going to be 8000 fragments. The ip_input will find the struct
> > ipq *fp to match that packet. The struct ipq *fp will have list of all
> > those fragments belonging to same packet as a list and it will go
> > through that list twice in the ip_reass function (one to find out
> > where to put the fragment, and second time to see if the packet is
> > complete).
> > 
> > This means that for each of those 56 byte (48 bytes of ip header
> > (header + some options) and 8 bytes of actual data) * 8000 fragment
> > packets, we do 2 * 8000 * 8000 / 2 list operations. This means that we
> > do 64000000 list operations for each 448000 bytes of data. If each
> 
> I wonder: shouldn't that per-packet list be a per-packet balanced tree of
> some sort, such that the case above would be some constant times
> 8000 log 8000?

I suspect it would be better to detect the amount of free space in
the buffer and copy small fragmets together.
(Ok you receive frags 1,3,5 etc...)

Also since an interface is required to have an mtu of at least
(about) 512, anything with stupid fragmentation can be safely
dumped!  - now detect stupid :-)

Even if you fix the search, you can easily run out of kva
(if nothing else first) trying to hold all the fragments
until the reassembly timer expires.
(just odd fragments are a good DoS attack)

OTOH using balanced trees instead of hash lists will probably
improve the scalability of the kernel throughout.

	David

-- 
David Laight: david@l8s.co.uk