Re: [B.A.T.M.A.N.] Patch which fixes a uint32overflow ; fix algorithm which was unintented changed on 2014 update

[Sven Eckelmann <sven@narfation.org>]

[-- Attachment #1: Type: text/plain, Size: 2314 bytes --]

On Sunday 17 May 2015 00:11:52 Sven Eckelmann wrote: 
> And please also include the commit which caused the regression. This makes
> it easier to find out which kernel versions must be patched in case the
> problem is critical. Here is an example how this information should be
> included:

You are most likely want to fix the regression introduced in 0853ec7 ("batman-
adv: tvlv - gateway download/upload bandwidth container"). The gateway client 
code for fast node selection was previously using batadv_gw_bandwidth_to_kbit 
to convert the input parameters to Kibit/s. After the TLV restructuring it 
should have multiplied the TLV value by 100 to get the exact same result 
because the batadv_tvlv_gateway_data bandwidth_down/bandwidth_up stores the 
throughput with the base unit of 100 Kibit/s.

The problem here would be to decide if it changes the result of the algorithm. 
The code goes through all gateways. For each gateway it calculates the formula 
(gw_down is in 100 Kibit/s; gw_divisor is constant	):

    gw_factor = |_ (tq_avg ** 2 * gw_down * 10 ** 4) / gw_divisor _|

You want to change it to

    gw_factor = |_ (tq_avg ** 2 * gw_down * 10 ** 6) / gw_divisor _|

The rest of the algorithm is just comparing the gw_factor of each gateway. The 
question which should have been answered by the commit message would be:

   Why is this constant of 100 affecting your results? Is it rounding related?
   How much does it affect the algorithm?

tq_avg is a value <= 255. A realistic value for bandwidth_down is maybe 
something like 20. gw_divisor is 2 ** 18.

So each difference in "tq_avg ** 2 * gw_down * 10 ** 4" for each gateway must 
be larger than 2 ** 18 to always be distinguishable by the algorithm. For a 
fixed tq_avg value of 255 the algorithm could currently compare two gateways 
with a gw_down difference of (1. / 2480) and still distinguish them. It would 
still detect a difference when the tq_avg is 6 and the gw_down difference is 
1.

For a fixed gw_down value of 1, the current algorithm would have problems to 
distinguish the tq_avg values < 14 when the tq_avg difference is small.

Your change would make it 100x more precise for gw_down. But I am currently 
not seeing the actual impact. Maybe you could explain it in more detail in the 
commit message.

Kind regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 819 bytes --]