Re: [Patch v2 3/3] IB/cache: don't fill the cache with junk

[Doug Ledford <dledford-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>]

On 10/20/2013 02:51 AM, Jack Morgenstein wrote:
> On Tue, 24 Sep 2013 17:16:29 -0400
> Doug Ledford <dledford-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
>
>> @@ -85,13 +91,26 @@ int ib_get_cached_gid(struct ib_device *device,
>>
>>   	cache = device->cache.gid_cache[port_num -
>> start_port(device)];
>> -	if (index < 0 || index >= cache->table_len)
>> +	if (index < 0 || index >= cache->table_len) {
>>   		ret = -EINVAL;
>> -	else
>> -		*gid = cache->table[index];
>> +		goto out_unlock;
>> +	}
>>
>> -	read_unlock_irqrestore(&device->cache.lock, flags);
>> +	for (i = 0; i < cache->table_len; ++i)
>> +		if (cache->entry[i].index == index)
>> +			break;
>> +
>> +
>
> Hi Doug,
>
> I am a bit concerned about this patch, because where before
> ib_get_cached_gid just returned the GID at the given index, with your
> suggested change, ib_get_cached_gid() requires a search of the new gid
> table (to find the entry with the requested index value).

Yes, I agree.  That was a consideration in things.

> ib_get_cached_gid is called by cm_req_handler, for the gid at index 0.
> There is no guarantee that this will be the first entry in the new
> scheme.

If it's valid, then yes it is.  Only if GID index 0 is invalid will it 
not be the first entry (and then it won't be an entry at all).  This is 
due to how the update of the gid table works (it scans each entry, 
starting at 0 and going to table length, and puts them into a table in 
ascending order).

Which points out that a valid optimization not present in this patch 
would be to break if the current table index is > than the requested index.

I had also thought about doing a bitmap for the valid entries. 
Realistically, most machines only have 1 or 2 ports of IB devices.  For 
common devices, the maximum pkey table length is 128 entries.  So, 2 
ports at 128 entries per port is a pretty miserly 256 bytes of memory. 
We could just allocate a full table and use a bitmap to represent the 
valid entries, and then in the find_cached* cases use the bitmap to 
limit our search.  That would allow us to go back to O(1) for get_cached*.

> Furthermore, ib_get_cached_gid is also called in MAD packet handling,
> with the specific gid index that is required.
>
> Thus, the savings for ib_find_cached_gid might possibly be offset by a
> performance loss in ib_get_cached_gid.

Doubtful.  Given that the common case is trading a single lookup 
increase to a 3 to 5 GID long chain search versus searching 128 entries 
of which 123 to 125 are invalid down to a similar 3 to 5 long chain 
search, the obvious big gain is getting rid of that 123 to 125 wasted 
memcmp's.  And ib_find_cached_gid is used in cma_acquire_dev(), which in 
turn is called by cma_req_handler, iw_conn_req_handler, addr_handler, 
and rdma_bind_addr.  So it sees plenty of use as well.

Now, one thing I haven't tested yet and wish to, is a situation when we 
have lots of SRIOV devices and a GID table on the PF that is highly 
populated.  In that case, further refinement will likely be necessary. 
If so, that will be my next patch, but I'll leave these patches to stand 
as they do now.

> A simpler optimization would be to simply keep a count of the number of
> valid GIDS in the gid table -- and break off the search when the last
> valid GID has been seen.

My understanding, according to the PKey change flow patches that Or 
posted, is that the GID table can have invalid entries prior to valid 
entries, and so that optimization would break.

>  This would optimize cases where, for example,
> you are searching for a GID that is not in the table, and only the
> first 3 gids in the table are valid (so you would not needlessly access
> 125 invalid GIDs).  Clearly, such an optimization is only useful when
> there are a lot of invalid gids bunched together at the end of the
> table.  Still, something to think about.

As you point out, it only works if all the invalid entries are at the 
end, and we can't guarantee that.

I think I like my suggestion better: go back to having a full table, but 
use a bitmap to indicate valid entries and then use the bitmap to limit 
our comparisons in the find_cached* functions, and put the get_* 
funtions back to being O(1).  But I would still do that incrementally 
from here I think.

But I'm not totally convinced of that either.  The exact sitiation I 
listed above, lots of GIDs on an SRIOV PF, makes me concerned that we 
can get back to a horrible situation in the find_cached* functions once 
we actually have lots of valid entries.  It makes me think we need 
something better than just a linear search of all valid entries when you 
take SRIOV into account.  Whether hash chains or ranges or something to 
make the lots of valid GIDs case faster, I suspect something needs to be 
done, but because things simply aren't in common use yet we don't know it.

--
To unsubscribe from this list: send the line "unsubscribe linux-rdma" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html