[1/2] batman-adv: Avoid u32 overflow during gateway select

  From: Ruben Wisniewski <ruben@freifunk-nrw.de>

The gateway selection based on fast connections is using a single value
calculated from the average tq (0-255) and the download bandwidth (in
100Kibit). The formula for the first step (tq ** 2 * 10000 * bandwidth)
tends to overflow a u32 with low bandwidth settings like 50 [100KiBit]
and a tq value of over 92.

Changing this to a 64 bit unsigned integer allows to support a
bandwidth_down with up to ~2.8e10 [100KiBit] and a perfect tq of 255. This
is ~6.6 times higher than the maximum possible value of the gateway
announcement TVLV.

This problem only affects the non-default gw_sel_class 1.

Signed-off-by: Ruben Wisniewsi <ruben@vfn-nrw.de>
[sven@narfation.org: rewritten commit message, changed to kernel type]
Signed-off-by: Sven Eckelmann <sven@narfation.org>
Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch>

Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
---
 net/batman-adv/gateway_client.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
  

From: Antonio Quartulli <antonio@meshcoding.com>
Date: Tue, 16 Jun 2015 21:06:23 +0200

> @@ -133,7 +133,7 @@ batadv_gw_get_best_gw_node(struct batadv_priv *bat_priv)
>  	struct batadv_neigh_node *router;
>  	struct batadv_neigh_ifinfo *router_ifinfo;
>  	struct batadv_gw_node *gw_node, *curr_gw = NULL;
> -	uint32_t max_gw_factor = 0, tmp_gw_factor = 0;
> +	uint64_t max_gw_factor = 0, tmp_gw_factor = 0;
>  	uint32_t gw_divisor;

Divides are performed using these variables, so if you make
them 64-bit the build will fail.  You have to use one of the
routines in include/linux/math64.h in this situation, but
realize that this operation is now going to be quite expensive.
  

On Sunday 21 June 2015 09:37:13 David Miller wrote:
> From: Antonio Quartulli <antonio@meshcoding.com>
> Date: Tue, 16 Jun 2015 21:06:23 +0200
> 
> > @@ -133,7 +133,7 @@ batadv_gw_get_best_gw_node(struct batadv_priv
> > *bat_priv)> 
> >  	struct batadv_neigh_node *router;
> >  	struct batadv_neigh_ifinfo *router_ifinfo;
> >  	struct batadv_gw_node *gw_node, *curr_gw = NULL;
> > 
> > -	uint32_t max_gw_factor = 0, tmp_gw_factor = 0;
> > +	uint64_t max_gw_factor = 0, tmp_gw_factor = 0;
> > 
> >  	uint32_t gw_divisor;
> 
> Divides are performed using these variables, so if you make
> them 64-bit the build will fail.  You have to use one of the
> routines in include/linux/math64.h in this situation, but
> realize that this operation is now going to be quite expensive.

Just a minor comment: The division is currently "max_gw_factor >> 18" which 
the compiler also outputs as such (shrd + shr on i586). This is the reason why 
it currently also works on architectures without a native 64 bit div.

Kind regards,
	Sven
  

On 21/06/15 20:27, Sven Eckelmann wrote:
> On Sunday 21 June 2015 09:37:13 David Miller wrote:
>> From: Antonio Quartulli <antonio@meshcoding.com>
>> Date: Tue, 16 Jun 2015 21:06:23 +0200
>>
>>> @@ -133,7 +133,7 @@ batadv_gw_get_best_gw_node(struct batadv_priv
>>> *bat_priv)> 
>>>  	struct batadv_neigh_node *router;
>>>  	struct batadv_neigh_ifinfo *router_ifinfo;
>>>  	struct batadv_gw_node *gw_node, *curr_gw = NULL;
>>>
>>> -	uint32_t max_gw_factor = 0, tmp_gw_factor = 0;
>>> +	uint64_t max_gw_factor = 0, tmp_gw_factor = 0;
>>>
>>>  	uint32_t gw_divisor;
>>
>> Divides are performed using these variables, so if you make
>> them 64-bit the build will fail.  You have to use one of the
>> routines in include/linux/math64.h in this situation, but
>> realize that this operation is now going to be quite expensive.
> 
> Just a minor comment: The division is currently "max_gw_factor >> 18" which 
> the compiler also outputs as such (shrd + shr on i586). This is the reason why 
> it currently also works on architectures without a native 64 bit div.


Thanks for the comment David and Sven.


David you can drop this pull request.
I'll send a new one later with a modified patch that explicitly
introduces the shift.



Thanks!