From: Dexuan Cui <decui@microsoft.com>
To: Vitaly Kuznetsov <vkuznets@redhat.com>, KY Srinivasan <kys@microsoft.com>
CC: Haiyang Zhang <haiyangz@microsoft.com>,
        "devel@linuxdriverproject.org" <devel@linuxdriverproject.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>
Subject: RE: [PATCH 6/6] Drivers: hv: vmbus: do a fair round robin when
 selecting an outgoing channel
Thread-Topic: [PATCH 6/6] Drivers: hv: vmbus: do a fair round robin when
 selecting an outgoing channel
Thread-Index: AQHQfD9glT+T1Ik2P0KscewofWQgI51b1oaQ
Date: Fri, 24 Apr 2015 08:42:11 +0000
Message-ID: <fffd7d5f88334c308029dd0c0bf9e9d9@SIXPR30MB031.064d.mgd.msft.net>
References: <1429626460-7947-1-git-send-email-vkuznets@redhat.com>
 <1429626460-7947-7-git-send-email-vkuznets@redhat.com>
In-Reply-To: <1429626460-7947-7-git-send-email-vkuznets@redhat.com>
Accept-Language: en-US
Content-Language: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 8BIT
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Apr 2015 08:42:18.0029
 (UTC)
X-MS-Exchange-CrossTenant-Id: 72f988bf-86f1-41af-91ab-2d7cd011db47
X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=72f988bf-86f1-41af-91ab-2d7cd011db47;Ip=[206.191.229.116];Helo=[064-smtp-out.microsoft.com]
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY1PR0301MB1319
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Length: 4068
Lines: 127

> -----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.


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(?)

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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/