[Top] [All Lists]

Re: 802.1q Was (Re: Plans for 2.5 / 2.6 ???

To: Mitchell Blank Jr <mitch@xxxxxxxxxx>
Subject: Re: 802.1q Was (Re: Plans for 2.5 / 2.6 ???
From: Ben Greear <greearb@xxxxxxxxxxxxxxx>
Date: Sun, 04 Jun 2000 22:57:31 -0700
Cc: jamal <hadi@xxxxxxxxxx>, rob@xxxxxxxxxxx, buytenh@xxxxxxx, netdev@xxxxxxxxxxx, gleb@xxxxxxxxxxxxxxxxxxxxx
Organization: Candela Technologies
References: <20000603091818.B48132@xxxxxxxxxx> <Pine.GSO.4.20.0006040924390.16882-100000@xxxxxxxxxxxxxxxx> <20000604214856.B77216@xxxxxxxxxx>
Sender: owner-netdev@xxxxxxxxxxx
Mitchell Blank Jr wrote:

> The one tricky part is dev_alloc_name() function... it's current
> algorithm is to search for "prefix0" through "prefix99" and if
> they're all in use bail out.  Not only does this mean that you
> won't naturally end up with "ppp100", the search is N^2 (meaning
> the time to set up N of them is N^3).  The best algorithm compromise
> isn't clear - I'd say that for each prefix in use ("ppp", "eth") keep
> an ordered linked list of them, that way you can quickly linearly
> scan looking for the lowest hole.  An added optomization would be
> to hold a "next_to_try_after" pointer into the list.  (after adding
> an interface, set to self.  When deleting an interface, set to
> our previous one if it's before next_to_try_after) which greatly
> reduces the length of the search for many common access patterns.
> This sounds complicated, but would actually be pretty easy to implement
> using linux/list.h - just keep the next_to_try_after as the first
> element and just rotate the list around it as it changes.

VLAN, by default, allocs it's names in constant time (eth-dev-name + VLAN-ID)

I would imagine FrameRelay and ATM could do something similar.  ppp an others
should be able to easily get it down to a linear search of the list by
parsing the names in one pass, then allocating the first hole, or appending
onto the end.  I believe that will not touch any of the data structures,
only a smarter, or just more specific, dev_alloc_name.

The ppp component itself could keep track of things itself too, and
just never call the dev_alloc_name, perhaps with a list as you mentioned...

> The tricker part is where the IP stack searches through the list
> itself (ipv4/devinet.c:inet_selcect_addr(),
> ipv6/addrconf.c/ipv6_get_saddr())... I assume these are just used
> for corner cases, right?  I assume that things on the fast path
> (selecting source IPs for outgoing packets is taken care by the
> routing code, right?!?)

I hope someone has a good answer here...I certainly have no idea!

> Anyway, assuming that those code paths in ipv4 and ipv6 aren't
> hotspots, some basic datastructure work in net/core/dev.c would
> remove the algorithmic limitations on hosting thousands of devices.

Thanks for the information!

Ben Greear (greearb@xxxxxxxxxxxxxxx)
Author of ScryMUD: 4444        (Released under GPL)     

<Prev in Thread] Current Thread [Next in Thread>