GNU bug report logs - #35291
[PATCH] split: fix incorrect suffix length computation

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 35291 in the body.
You can then email your comments to 35291 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Johannes Altmanninger <aclopte <at> gmail.com>
To: bug-coreutils <at> gnu.org
Cc: Johannes Altmanninger <aclopte <at> gmail.com>
Subject: [PATCH] split: fix incorrect suffix length computation
Date: Mon, 15 Apr 2019 20:05:34 +0200

* src/split.c (set_suffix_length): suffix_needed is now computed
to be the equivalent of ceil(log(n_units_end) / log(alphabet_len)).
Previously, it would give the floor of above logarithm if the number
of units is divisible by the length of the alphabet.
* tests/split/suffix-auto-length.sh: Add test demonstrating the problem.
---

Hi,

This should be a fairly straightforward fix.  It seems like it has been
discovered in 2015 [1] (look for "multiple of 10") but the bug fixed at that
time was a different one. I am not aware of any open bug for this.

Let me know if I am missing something.

Thanks,
Johannes

[1] https://debbugs.gnu.org/cgi/bugreport.cgi?bug=20511

 src/split.c                       | 11 ++++++-----
 tests/split/suffix-auto-length.sh |  4 ++++
 2 files changed, 10 insertions(+), 5 deletions(-)

diff --git a/src/split.c b/src/split.c
index 30fdb4462..22b645fc9 100644
--- a/src/split.c
+++ b/src/split.c
@@ -191,13 +191,14 @@ set_suffix_length (uintmax_t n_units, enum Split_type split_type)
               if (n_start < n_units)
                 n_units_end += n_start;
             }
-
         }
       size_t alphabet_len = strlen (suffix_alphabet);
-      bool alphabet_slop = (n_units_end % alphabet_len) != 0;
-      while (n_units_end /= alphabet_len)
-        suffix_needed++;
-      suffix_needed += alphabet_slop;
+      uintmax_t max_units = 1;
+      while (max_units < n_units_end)
+        {
+          suffix_needed++;
+          max_units *= alphabet_len;
+        }
       suffix_auto = false;
     }
 
diff --git a/tests/split/suffix-auto-length.sh b/tests/split/suffix-auto-length.sh
index e5594d878..691c31ad4 100755
--- a/tests/split/suffix-auto-length.sh
+++ b/tests/split/suffix-auto-length.sh
@@ -50,4 +50,8 @@ rm -f x*
 # as that would result in an incorrect order for the total output file set
 returns_ 1 split --numeric-suffixes=100 --number=r/100 file.in || fail=1
 
+truncate -s0 file.in || framework_failure_
+
+returns_ 0 split --numeric-suffixes --number=r/110 file.in || fail=1
+
 Exit $fail
-- 
2.21.0

Message #8 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Johannes Altmanninger <aclopte <at> gmail.com>
To: bug-coreutils <at> gnu.org
Subject: Re: [PATCH] split: fix incorrect suffix length computation
Date: Fri, 7 Jun 2019 19:36:46 +0200

Does anyone have time to review this? I think it's an evident bug.
I can try to improve the clarity of the patch if needed.

On Mon, Apr 15, 2019 at 08:05:34PM +0200, Johannes Altmanninger wrote:
> * src/split.c (set_suffix_length): suffix_needed is now computed
> to be the equivalent of ceil(log(n_units_end) / log(alphabet_len)).
> Previously, it would give the floor of above logarithm if the number
> of units is divisible by the length of the alphabet.
> * tests/split/suffix-auto-length.sh: Add test demonstrating the problem.
> ---
> 
> Hi,
> 
> This should be a fairly straightforward fix.  It seems like it has been
> discovered in 2015 [1] (look for "multiple of 10") but the bug fixed at that
> time was a different one. I am not aware of any open bug for this.
> 
> Let me know if I am missing something.
> 
> Thanks,
> Johannes
> 
> [1] https://debbugs.gnu.org/cgi/bugreport.cgi?bug=20511
> 
>  src/split.c                       | 11 ++++++-----
>  tests/split/suffix-auto-length.sh |  4 ++++
>  2 files changed, 10 insertions(+), 5 deletions(-)
> 
> diff --git a/src/split.c b/src/split.c
> index 30fdb4462..22b645fc9 100644
> --- a/src/split.c
> +++ b/src/split.c
> @@ -191,13 +191,14 @@ set_suffix_length (uintmax_t n_units, enum Split_type split_type)
>                if (n_start < n_units)
>                  n_units_end += n_start;
>              }
> -
>          }
>        size_t alphabet_len = strlen (suffix_alphabet);
> -      bool alphabet_slop = (n_units_end % alphabet_len) != 0;
> -      while (n_units_end /= alphabet_len)
> -        suffix_needed++;
> -      suffix_needed += alphabet_slop;
> +      uintmax_t max_units = 1;
> +      while (max_units < n_units_end)
> +        {
> +          suffix_needed++;
> +          max_units *= alphabet_len;
> +        }
>        suffix_auto = false;
>      }
>  
> diff --git a/tests/split/suffix-auto-length.sh b/tests/split/suffix-auto-length.sh
> index e5594d878..691c31ad4 100755
> --- a/tests/split/suffix-auto-length.sh
> +++ b/tests/split/suffix-auto-length.sh
> @@ -50,4 +50,8 @@ rm -f x*
>  # as that would result in an incorrect order for the total output file set
>  returns_ 1 split --numeric-suffixes=100 --number=r/100 file.in || fail=1
>  
> +truncate -s0 file.in || framework_failure_
> +
> +returns_ 0 split --numeric-suffixes --number=r/110 file.in || fail=1
> +
>  Exit $fail
> -- 
> 2.21.0
> 

Message #11 received at 35291 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Johannes Altmanninger <aclopte <at> gmail.com>
Cc: 35291 <at> debbugs.gnu.org
Subject: Re: bug#35291: [PATCH] split: fix incorrect suffix length computation
Date: Sat, 8 Jun 2019 12:36:16 -0700

Johannes Altmanninger wrote:
> Does anyone have time to review this? I think it's an evident bug.
> I can try to improve the clarity of the patch if needed.

It's not clarity that needs fixing, it's also correctness. A quick look suggests 
that the proposed fix can go into an infinite loop due to unsigned integer 
overflow. This is why the current code uses division and not multiplication.

Message #16 received at 35291-done <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: Johannes Altmanninger <aclopte <at> gmail.com>, 35291-done <at> debbugs.gnu.org
Subject: Re: bug#35291: [PATCH] split: fix incorrect suffix length computation
Date: Sat, 8 Jun 2019 23:06:07 +0100

On 15/04/19 19:05, Johannes Altmanninger wrote:
> * src/split.c (set_suffix_length): suffix_needed is now computed
> to be the equivalent of ceil(log(n_units_end) / log(alphabet_len)).
> Previously, it would give the floor of above logarithm if the number
> of units is divisible by the length of the alphabet.
> * tests/split/suffix-auto-length.sh: Add test demonstrating the problem.
> ---
> 
> Hi,
> 
> This should be a fairly straightforward fix.  It seems like it has been
> discovered in 2015 [1] (look for "multiple of 10") but the bug fixed at that
> time was a different one. I am not aware of any open bug for this.
> 
> Let me know if I am missing something.
> 
> Thanks,
> Johannes
> 
> [1] https://debbugs.gnu.org/cgi/bugreport.cgi?bug=20511
> 
>  src/split.c                       | 11 ++++++-----
>  tests/split/suffix-auto-length.sh |  4 ++++
>  2 files changed, 10 insertions(+), 5 deletions(-)
> 
> diff --git a/src/split.c b/src/split.c
> index 30fdb4462..22b645fc9 100644
> --- a/src/split.c
> +++ b/src/split.c
> @@ -191,13 +191,14 @@ set_suffix_length (uintmax_t n_units, enum Split_type split_type)
>                if (n_start < n_units)
>                  n_units_end += n_start;
>              }
> -
>          }
>        size_t alphabet_len = strlen (suffix_alphabet);
> -      bool alphabet_slop = (n_units_end % alphabet_len) != 0;
> -      while (n_units_end /= alphabet_len)
> -        suffix_needed++;
> -      suffix_needed += alphabet_slop;
> +      uintmax_t max_units = 1;
> +      while (max_units < n_units_end)
> +        {
> +          suffix_needed++;
> +          max_units *= alphabet_len;
> +        }

Unlikely, but this could inf loop for n_units > UINTMAX_MAX / alphabet_len

>        suffix_auto = false;
>      }
>  
> diff --git a/tests/split/suffix-auto-length.sh b/tests/split/suffix-auto-length.sh
> index e5594d878..691c31ad4 100755
> --- a/tests/split/suffix-auto-length.sh
> +++ b/tests/split/suffix-auto-length.sh
> @@ -50,4 +50,8 @@ rm -f x*
>  # as that would result in an incorrect order for the total output file set
>  returns_ 1 split --numeric-suffixes=100 --number=r/100 file.in || fail=1
>  
> +truncate -s0 file.in || framework_failure_
> +
> +returns_ 0 split --numeric-suffixes --number=r/110 file.in || fail=1

returns_ 0 is redundant.
returns_ 1 is used so as not to conflate segfaults etc. with EXIT_FAILURE

I've installed the following to address the issue.

https://git.sv.gnu.org/gitweb/?p=coreutils.git;a=commitdiff;h=738a746

Marking this as done.

thanks!
Pádraig

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.