[ovs-dev] [PATCH 3/3] [bug 2462] datapath: Increase maximum number of datapath ports.

[Jesse Gross]

On Tue, Feb 7, 2012 at 9:30 AM, Ben Pfaff <blp at nicira.com> wrote:
> On Tue, Feb 07, 2012 at 01:54:18AM -0800, Pravin Shelar wrote:
>> On Mon, Feb 6, 2012 at 9:45 PM, Ben Pfaff <blp at nicira.com> wrote:
>> > On Mon, Feb 06, 2012 at 08:56:02PM -0800, Jesse Gross wrote:
>> >> OVS userspace tries not to recycle port numbers, which means that even
>> >> for a constant number of VMs on a machine if there is some churn
>> >> (maybe from migrations) over time we'll keep on expanding the table
>> >> and allocating more memory that's not really used.
>> >
>> > Right.  If I'm following this conversation correctly (I haven't read the
>> > patches) then the kernel datapath is switching to using a strategy where
>> > the space required for the port array is O(max_port) where max_port is
>> > the highest-numbered port in use, regardless of the number of ports
>> > actually in use.  Is that right?  If it is, it worries me a little,
>> > since it makes it expensive to use sparse port numbers.  Why not a hash
>> > (or a radix tree, or whatever) of the port number?
>>
>> Radix tree is good idea, it is already using RCU. I need to check
>> compatibility with older kernel for RCU access for radix tree.
>
> A radix tree is usually slower and consumes more memory than a hash
> table.  I suspect the usual reason to choose a radix tree over a hash
> table is that you need to be able to traverse the table in order by
> index, but I don't think we have that requirement.

Trees do have the advantage of better cache locality in the
(hopefully) common case of a dense grouping of ports.

Either way I'm not too excited about introducing a new data structure
in the middle of the packet execution path.  We had talked some in the
past about directly using pointers to ports for output actions.  We'll
have to deal with refcounting but it seems doable and the most
efficient.