lkml.org 
[lkml]   [2015]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
SubjectRe: [PATCH 6/6] Drivers: hv: vmbus: do a fair round robin when selecting an outgoing channel
Date
Dexuan Cui <decui@microsoft.com> writes:

>> -----Original Message-----
>> From: Vitaly Kuznetsov [mailto:vkuznets@redhat.com]
>> Sent: Tuesday, April 21, 2015 22:28
>> To: KY Srinivasan
>> Cc: Haiyang Zhang; devel@linuxdriverproject.org; linux-
>> kernel@vger.kernel.org; Dexuan Cui
>> Subject: [PATCH 6/6] Drivers: hv: vmbus: do a fair round robin when
>> selecting an outgoing channel
>>
>> vmbus_get_outgoing_channel() implements the following algorithm for
>> selecting
>> an outgoing channel (despite the comment before the function saying it
>> distributes the load equally):
>
> Yeah, I also found the issue.
>
>> 1) If we have no subchannels return the primary channel;
>> 2) If primary->next_oc is grater than primary->num_sc reset the primary-
>> >next_oc
>> to 0 and return the primary channel;
>> 3) Aim for the primary->next_oc subchannel, increment primary->next_oc;
>> 4) Loop through all opened subchannels. If we see a channel which has
>> target_cpu == current_cpu return it. If we reached the primary->next_oc'th
>> open subchannel return it;
>> 5) Return the primary channel.
>> The implementation also skips the subchannel No. 0 unless it matches the
>> current
>> cpu as we assign i to 1 in the initialization.
>>
>> This is not a fair round robin as subchannels in the beginning of the list are
>> more likely to be returned and checking for current cpu aslo creates
>
> I suppose the current algorithm is trying to make use of cache locality?
> KY may share more information.
>
>> additional
>> complexity. Simplify the vmbus_get_outgoing_channel() function, make it
>> do what the comment before it says.
>
> Hi Vitaly,
> It looks your algorithm also has an issue:
> Assuming primary->num_sc == 3 (SC1, SC2, SC3)
> 1st time: we choose SC1 and primary->next_oc is set to 1.
> 2nd time: we choose SC2 and primary->next_oc is set to 2.
> 3rd time: we choose SC3 and primary->next_oc is set to 3.
> 4th time and later: since i varies among 1~3 and can't be bigger than 3,
> we always choose the primary channel.

You're right, it seems 'if (primary->next_oc > primary->num_sc)' is
off-by-one, it should be >=

>
> BTW, IMO it's not easy to achieve complete fairness because
> vmbus_get_outgoing_channel() can run simultaneously on different
> CPUs (so primary->next_oc can be modified at the same time by multiple
> CPUs), and we believe it should be lockless.
> Maybe atomic_t can help(?)

This thing bothered me a bit but then I realized that we don't actually
care - doing a mistake once is better than suffering from the slowness
of locks/atomics. I'd suggest we keep it this way (with the fix
mentioned above).

Thanks!

>
> Thanks,
> -- Dexuan
>
>>
>> Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
>> ---
>> drivers/hv/channel_mgmt.c | 27 +++++++++------------------
>> 1 file changed, 9 insertions(+), 18 deletions(-)
>>
>> diff --git a/drivers/hv/channel_mgmt.c b/drivers/hv/channel_mgmt.c
>> index daa6417..df82442 100644
>> --- a/drivers/hv/channel_mgmt.c
>> +++ b/drivers/hv/channel_mgmt.c
>> @@ -827,39 +827,30 @@ cleanup:
>> struct vmbus_channel *vmbus_get_outgoing_channel(struct
>> vmbus_channel *primary)
>> {
>> struct list_head *cur, *tmp;
>> - int cur_cpu;
>> struct vmbus_channel *cur_channel;
>> - struct vmbus_channel *outgoing_channel = primary;
>> - int next_channel;
>> - int i = 1;
>> + int i = 0;
>>
>> if (list_empty(&primary->sc_list))
>> - return outgoing_channel;
>> + return primary;
>>
>> - next_channel = primary->next_oc++;
>> -
>> - if (next_channel > (primary->num_sc)) {
>> + if (primary->next_oc > primary->num_sc) {
>> primary->next_oc = 0;
>> - return outgoing_channel;
>> + return primary;
>> }
>>
>> - cur_cpu = hv_context.vp_index[get_cpu()];
>> - put_cpu();
>> list_for_each_safe(cur, tmp, &primary->sc_list) {
>> + i++;
>> cur_channel = list_entry(cur, struct vmbus_channel, sc_list);
>> if (cur_channel->state != CHANNEL_OPENED_STATE)
>> continue;
>>
>> - if (cur_channel->target_vp == cur_cpu)
>> - return cur_channel;
>> -
>> - if (i == next_channel)
>> + if (i > primary->next_oc) {
>> + primary->next_oc = i;
>> return cur_channel;
>> -
>> - i++;
>> + }
>> }
>>
>> - return outgoing_channel;
>> + return primary;
>> }
>> EXPORT_SYMBOL_GPL(vmbus_get_outgoing_channel);
>>
>> --
>> 1.9.3

--
Vitaly


\
 
 \ /
  Last update: 2015-04-24 11:21    [W:0.053 / U:0.100 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site