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
--
Ben Greear (greearb@xxxxxxxxxxxxxxx) http://www.candelatech.com
Author of ScryMUD: scry.wanfear.com 4444 (Released under GPL)
http://scry.wanfear.com http://scry.wanfear.com/~greear
|