diff mbox series

[Openvpn-devel,v2] Improve shuffling algorithm of connection list

Message ID 20241118142019.31045-1-shujifurukawa1213@gmail.com
State Accepted
Headers
Series [Openvpn-devel,v2] Improve shuffling algorithm of connection list |

Commit Message

Hurukawa2121 Nov. 18, 2024, 2:20 p.m. UTC 
  ---
 Improve shuffling algorithm of connection list

 This patch implements the Fisher-Yates shuffle algorithm to ensure that all permutations of the connection target list are generated with equal probability, eliminating biases present in the previous shuffling method. In the Fisher-Yates algorithm, there's only one way to obtain each permutation through a series of element swaps, so all permutations occur with equal probability in theory.

 Signed-off-by: Shuji Furukawa <shujifurukawa1213@gmail.com>

 src/openvpn/init.c | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

Comments

Antonio Quartulli Nov. 18, 2024, 3:11 p.m. UTC | #1 
Thanks for resending the patch!

On 18/11/2024 15:20, Hurukawa2121 wrote:
> ---

However, please note that anything you write should go *before* these 
three dashes, otherwise the text is ignored by git on commit.

Anyway, no need to resend the patch for this.
Probably Gert can easily fix this before moving forward with your patch.

>   Improve shuffling algorithm of connection list
> 
>   This patch implements the Fisher-Yates shuffle algorithm to ensure that all permutations of the connection target list are generated with equal probability, eliminating biases present in the previous shuffling method. In the Fisher-Yates algorithm, there's only one way to obtain each permutation through a series of element swaps, so all permutations occur with equal probability in theory.

Also one single loooong line in the commit message is absolutely not 
acceptable.
Better to split the text in lines no longer than 72 chars.
Technically Gert can fix this too upon commit.

But please do remember these details for your next patch.

> 
>   Signed-off-by: Shuji Furukawa <shujifurukawa1213@gmail.com>

>   src/openvpn/init.c | 13 ++++++++++---
>   1 file changed, 10 insertions(+), 3 deletions(-)
> 
> diff --git a/src/openvpn/init.c b/src/openvpn/init.c
> index 9371024e..c4fb5cd7 100644
> --- a/src/openvpn/init.c
> +++ b/src/openvpn/init.c
> @@ -467,7 +467,14 @@ ce_management_query_remote(struct context *c)
>   #endif /* ENABLE_MANAGEMENT */
>   
>   /*
> - * Initialize and possibly randomize connection list.
> + * Initialize and randomize the connection list.
> + *
> + * Applies the Fisher-Yates shuffle algorithm to ensure all permutations are equally probable,
> + * thereby eliminating shuffling bias in the previous method.
> + *
> + * The algorithm randomly selects an element from the unshuffled portion and places it at position i.
> + * There's only one way to obtain each permutation through these swaps.
> + * This guarantees that each permutation occurs with equal probability in theory.

Same goes for comments (and any other line of code):
maximum line length is 80 chars..

This said, the patch looks good to me and I can apply my

Acked-by: Antonio Quartulli <antonio@mandelbit.com>

However, I live it to Gert if he wants a new patch with these layout 
errors fixed or not.

Regards,



>    */
>   static void
>   init_connection_list(struct context *c)
> @@ -478,9 +485,9 @@ init_connection_list(struct context *c)
>       if (c->options.remote_random)
>       {
>           int i;
> -        for (i = 0; i < l->len; ++i)
> +        for (i = l->len - 1; i > 0; --i)
>           {
> -            const int j = get_random() % l->len;
> +            const int j = get_random() % (i + 1);
>               if (i != j)
>               {
>                   struct connection_entry *tmp;
Gert Doering Dec. 29, 2024, 12:24 p.m. UTC | #2 
Thanks for your patch.

I have reformatted the comment section (line length was too long) and
brought back the word "possibly" ("possibly randomize", it's not always
randomized).  I have not done any detailed tests on randomness and
distribution of permutations, though :-)

Your patch has been applied to the master branch.

commit 9502e5257c59bfd23b9afcdb28f7994470591430 (master)
Author: Shuji Furukawa
Date:   Mon Nov 18 23:20:20 2024 +0900

     Improve shuffling algorithm of connection list

     Signed-off-by: Shuji Furukawa <shujifurukawa1213@gmail.com>
     Acked-by: Antonio Quartulli <antonio@openvpn.net>
     Message-Id: <20241118142019.31045-1-shujifurukawa1213@gmail.com>
     URL: https://www.mail-archive.com/openvpn-devel@lists.sourceforge.net/msg29837.html
     Signed-off-by: Gert Doering <gert@greenie.muc.de>


--
kind regards,

Gert Doering
diff mbox series

Patch

diff --git a/src/openvpn/init.c b/src/openvpn/init.c
index 9371024e..c4fb5cd7 100644
--- a/src/openvpn/init.c
+++ b/src/openvpn/init.c
@@ -467,7 +467,14 @@  ce_management_query_remote(struct context *c)
 #endif /* ENABLE_MANAGEMENT */
 
 /*
- * Initialize and possibly randomize connection list.
+ * Initialize and randomize the connection list.
+ * 
+ * Applies the Fisher-Yates shuffle algorithm to ensure all permutations are equally probable,
+ * thereby eliminating shuffling bias in the previous method.
+ * 
+ * The algorithm randomly selects an element from the unshuffled portion and places it at position i.
+ * There's only one way to obtain each permutation through these swaps.
+ * This guarantees that each permutation occurs with equal probability in theory.
  */
 static void
 init_connection_list(struct context *c)
@@ -478,9 +485,9 @@  init_connection_list(struct context *c)
     if (c->options.remote_random)
     {
         int i;
-        for (i = 0; i < l->len; ++i)
+        for (i = l->len - 1; i > 0; --i)
         {
-            const int j = get_random() % l->len;
+            const int j = get_random() % (i + 1);
             if (i != j)
             {
                 struct connection_entry *tmp;