GNU bug report logs -
#10953
Potential logical bug in readtokens.c
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 10953 in the body.
You can then email your comments to 10953 AT debbugs.gnu.org in the normal way.
Toggle the display of automated, internal messages from the tracker.
Report forwarded
to
bug-coreutils <at> gnu.org:
bug#10953; Package
coreutils.
(Tue, 06 Mar 2012 08:18:02 GMT)
Full text and
rfc822 format available.
Acknowledgement sent
to
Xu Zhongxing <xu_zhong_xing <at> 163.com>:
New bug report received and forwarded. Copy sent to
bug-coreutils <at> gnu.org.
(Tue, 06 Mar 2012 08:18:02 GMT)
Full text and
rfc822 format available.
Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):
Hi,
I think I found a potential bug. But I am not sure about it. It looks
real from the code.
For coreutils 8.15, in file readtokens.c, function readtoken()
If delim is NULL, and saved_delim is not NULL, then the condition on
line 75 is not satisfied, but the condition on line 79 is satisfied.
In this case, there could be NULL pointer deference for delim[i] in line 84.
- Zhongxing Xu
Information forwarded
to
bug-coreutils <at> gnu.org:
bug#10953; Package
coreutils.
(Tue, 06 Mar 2012 23:23:01 GMT)
Full text and
rfc822 format available.
Message #8 received at 10953 <at> debbugs.gnu.org (full text, mbox):
Thanks, I agree that code is potentially buggy. I don't see
any way to trigger the bug in coreutils, but it's just asking
for trouble. Here's a proposed patch.
From 4954a3517397dadd217d6244e961dd855fbadbef Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Tue, 6 Mar 2012 15:19:24 -0800
Subject: [PATCH] readtokens: avoid core dumps with unusual calling patterns
Reported by Xu Zhongxing in <http://debbugs.gnu.org/10953>.
* lib/readtokens.c: Include limits.h.
(word, bits_per_word, get_nth_bit, set_nth_bit): New.
(readtoken): Don't cache the delimiters; the cache code was buggy
if !delim && saved_delim, or if the new n_delim differs from the old.
Also, it wasn't thread-safe.
---
ChangeLog | 10 +++++++++
lib/readtokens.c | 56 +++++++++++++++++++++++------------------------------
2 files changed, 34 insertions(+), 32 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 163e154..eb99d25 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2012-03-06 Paul Eggert <eggert <at> cs.ucla.edu>
+
+ readtokens: avoid core dumps with unusual calling patterns
+ Reported by Xu Zhongxing in <http://debbugs.gnu.org/10953>.
+ * lib/readtokens.c: Include limits.h.
+ (word, bits_per_word, get_nth_bit, set_nth_bit): New.
+ (readtoken): Don't cache the delimiters; the cache code was buggy
+ if !delim && saved_delim, or if the new n_delim differs from the old.
+ Also, it wasn't thread-safe.
+
2012-03-06 Bruno Haible <bruno <at> clisp.org>
math: Ensure declarations of math functions.
diff --git a/lib/readtokens.c b/lib/readtokens.c
index 705a62b..f11d3f6 100644
--- a/lib/readtokens.c
+++ b/lib/readtokens.c
@@ -26,6 +26,7 @@
#include "readtokens.h"
+#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
@@ -46,6 +47,22 @@ init_tokenbuffer (token_buffer *tokenbuffer)
tokenbuffer->buffer = NULL;
}
+typedef size_t word;
+enum { bits_per_word = sizeof (word) * CHAR_BIT };
+
+static bool
+get_nth_bit (size_t n, word const *bitset)
+{
+ return bitset[n / bits_per_word] >> n % bits_per_word & 1;
+}
+
+static void
+set_nth_bit (size_t n, word *bitset)
+{
+ size_t one = 1;
+ bitset[n / bits_per_word] |= one << n % bits_per_word;
+}
+
/* Read a token from STREAM into TOKENBUFFER.
A token is delimited by any of the N_DELIM bytes in DELIM.
Upon return, the token is in tokenbuffer->buffer and
@@ -68,42 +85,17 @@ readtoken (FILE *stream,
char *p;
int c;
size_t i, n;
- static const char *saved_delim = NULL;
- static char isdelim[256];
- bool same_delimiters;
-
- if (delim == NULL && saved_delim == NULL)
- abort ();
+ word isdelim[(UCHAR_MAX + bits_per_word) / bits_per_word];
- same_delimiters = false;
- if (delim != saved_delim && saved_delim != NULL)
+ memset (isdelim, 0, sizeof isdelim);
+ for (i = 0; i < n_delim; i++)
{
- same_delimiters = true;
- for (i = 0; i < n_delim; i++)
- {
- if (delim[i] != saved_delim[i])
- {
- same_delimiters = false;
- break;
- }
- }
- }
-
- if (!same_delimiters)
- {
- size_t j;
- saved_delim = delim;
- memset (isdelim, 0, sizeof isdelim);
- for (j = 0; j < n_delim; j++)
- {
- unsigned char ch = delim[j];
- isdelim[ch] = 1;
- }
+ unsigned char ch = delim[i];
+ set_nth_bit (ch, isdelim);
}
- /* FIXME: don't fool with this caching. Use strchr instead. */
/* skip over any leading delimiters */
- for (c = getc (stream); c >= 0 && isdelim[c]; c = getc (stream))
+ for (c = getc (stream); c >= 0 && get_nth_bit (c, isdelim); c = getc (stream))
{
/* empty */
}
@@ -124,7 +116,7 @@ readtoken (FILE *stream,
p[i] = 0;
break;
}
- if (isdelim[c])
+ if (get_nth_bit (c, isdelim))
{
p[i] = 0;
break;
--
1.7.6.5
Information forwarded
to
bug-coreutils <at> gnu.org:
bug#10953; Package
coreutils.
(Tue, 06 Mar 2012 23:34:02 GMT)
Full text and
rfc822 format available.
Message #11 received at 10953 <at> debbugs.gnu.org (full text, mbox):
[Message part 1 (text/plain, inline)]
[adding gnulib, since the code in question lives there]
On 03/06/2012 04:21 PM, Paul Eggert wrote:
> Thanks, I agree that code is potentially buggy. I don't see
> any way to trigger the bug in coreutils, but it's just asking
> for trouble. Here's a proposed patch.
>
>>From 4954a3517397dadd217d6244e961dd855fbadbef Mon Sep 17 00:00:00 2001
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> Date: Tue, 6 Mar 2012 15:19:24 -0800
> Subject: [PATCH] readtokens: avoid core dumps with unusual calling patterns
>
> Reported by Xu Zhongxing in <http://debbugs.gnu.org/10953>.
> * lib/readtokens.c: Include limits.h.
> (word, bits_per_word, get_nth_bit, set_nth_bit): New.
> (readtoken): Don't cache the delimiters; the cache code was buggy
> if !delim && saved_delim, or if the new n_delim differs from the old.
> Also, it wasn't thread-safe.
The fix looks right to me from a correctness perspective, but I'm afraid
we're still sub-optimal in performance.
> ---
> ChangeLog | 10 +++++++++
> lib/readtokens.c | 56 +++++++++++++++++++++++------------------------------
> 2 files changed, 34 insertions(+), 32 deletions(-)
>
> diff --git a/ChangeLog b/ChangeLog
> index 163e154..eb99d25 100644
> --- a/ChangeLog
> +++ b/ChangeLog
> @@ -1,3 +1,13 @@
> +2012-03-06 Paul Eggert <eggert <at> cs.ucla.edu>
> +
> + readtokens: avoid core dumps with unusual calling patterns
> + Reported by Xu Zhongxing in <http://debbugs.gnu.org/10953>.
> + * lib/readtokens.c: Include limits.h.
> + (word, bits_per_word, get_nth_bit, set_nth_bit): New.
> + (readtoken): Don't cache the delimiters; the cache code was buggy
> + if !delim && saved_delim, or if the new n_delim differs from the old.
> + Also, it wasn't thread-safe.
> +
> 2012-03-06 Bruno Haible <bruno <at> clisp.org>
>
> math: Ensure declarations of math functions.
> diff --git a/lib/readtokens.c b/lib/readtokens.c
> index 705a62b..f11d3f6 100644
> --- a/lib/readtokens.c
> +++ b/lib/readtokens.c
> @@ -26,6 +26,7 @@
>
> #include "readtokens.h"
>
> +#include <limits.h>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> @@ -46,6 +47,22 @@ init_tokenbuffer (token_buffer *tokenbuffer)
> tokenbuffer->buffer = NULL;
> }
>
> +typedef size_t word;
> +enum { bits_per_word = sizeof (word) * CHAR_BIT };
> +
> +static bool
> +get_nth_bit (size_t n, word const *bitset)
> +{
> + return bitset[n / bits_per_word] >> n % bits_per_word & 1;
> +}
> +
> +static void
> +set_nth_bit (size_t n, word *bitset)
> +{
> + size_t one = 1;
> + bitset[n / bits_per_word] |= one << n % bits_per_word;
> +}
> +
> /* Read a token from STREAM into TOKENBUFFER.
> A token is delimited by any of the N_DELIM bytes in DELIM.
> Upon return, the token is in tokenbuffer->buffer and
> @@ -68,42 +85,17 @@ readtoken (FILE *stream,
> char *p;
> int c;
> size_t i, n;
> - static const char *saved_delim = NULL;
> - static char isdelim[256];
> - bool same_delimiters;
> -
> - if (delim == NULL && saved_delim == NULL)
> - abort ();
> + word isdelim[(UCHAR_MAX + bits_per_word) / bits_per_word];
>
> - same_delimiters = false;
> - if (delim != saved_delim && saved_delim != NULL)
> + memset (isdelim, 0, sizeof isdelim);
> + for (i = 0; i < n_delim; i++)
> {
> - same_delimiters = true;
> - for (i = 0; i < n_delim; i++)
> - {
> - if (delim[i] != saved_delim[i])
> - {
> - same_delimiters = false;
> - break;
> - }
> - }
> - }
> -
> - if (!same_delimiters)
> - {
> - size_t j;
> - saved_delim = delim;
> - memset (isdelim, 0, sizeof isdelim);
> - for (j = 0; j < n_delim; j++)
> - {
> - unsigned char ch = delim[j];
> - isdelim[ch] = 1;
> - }
> + unsigned char ch = delim[i];
> + set_nth_bit (ch, isdelim);
> }
>
> - /* FIXME: don't fool with this caching. Use strchr instead. */
> /* skip over any leading delimiters */
> - for (c = getc (stream); c >= 0 && isdelim[c]; c = getc (stream))
> + for (c = getc (stream); c >= 0 && get_nth_bit (c, isdelim); c = getc (stream))
Why not just strchr instead of building up an isdelim bitmap? And why
are we calling getc() one character at a time, instead of using tricks
like freadahead() to operate on a larger buffer?
Also, is readtoken() intended to be a more powerful interface than
strtok, in which case we _do_ want to be non-threadsafe, and to have a
readtoken_r interface that is the underlying threadsafe variant that can
benefit from caching?
> {
> /* empty */
> }
> @@ -124,7 +116,7 @@ readtoken (FILE *stream,
> p[i] = 0;
> break;
> }
> - if (isdelim[c])
> + if (get_nth_bit (c, isdelim))
> {
> p[i] = 0;
> break;
--
Eric Blake eblake <at> redhat.com +1-919-301-3266
Libvirt virtualization library http://libvirt.org
[signature.asc (application/pgp-signature, attachment)]
Information forwarded
to
bug-coreutils <at> gnu.org:
bug#10953; Package
coreutils.
(Wed, 07 Mar 2012 05:35:02 GMT)
Full text and
rfc822 format available.
Message #14 received at 10953 <at> debbugs.gnu.org (full text, mbox):
On 03/06/2012 03:32 PM, Eric Blake wrote:
> Why not just strchr instead of building up an isdelim bitmap?
strchr would not be right, since '\0' is valid in data and
as a delimiter.
No doubt you meant 'memchr'; but using 'memchr' would slow
down readtoken by about a factor of two. I got this result by
timing the following benchmark on gcc-4.6.1.tar (uncompressed)
on Fedora 15 x86-64 with GCC 4.6.2:
#include <stdio.h>
#include <readtokens.h>
struct tokenbuffer t;
int main (void)
{
for (;;)
{
size_t s = readtoken (stdin, " \t\n", 3, &t);
if (s == (size_t) -1)
return 0;
}
}
On this benchmark, the relative speeds (user+sys CPU time ratios,
bigger numbers are better) are:
0.54 readtoken with memchr
1.00 current readtoken (with non-thread-safe byte array)
1.13 proposed readtoken (with thread-safe bitset)
So the proposed patch is a performance win even in non-thread-safe use.
> And why
> are we calling getc() one character at a time, instead of using tricks
> like freadahead() to operate on a larger buffer?
>
> Also, is readtoken() intended to be a more powerful interface than
> strtok, in which case we _do_ want to be non-threadsafe, and to have a
> readtoken_r interface that is the underlying threadsafe variant that can
> benefit from caching?
I haven't thought about these issues, but surely they are
independent of the proposed patch.
Information forwarded
to
bug-coreutils <at> gnu.org:
bug#10953; Package
coreutils.
(Wed, 07 Mar 2012 19:54:02 GMT)
Full text and
rfc822 format available.
Message #17 received at 10953 <at> debbugs.gnu.org (full text, mbox):
Paul Eggert wrote:
> Thanks, I agree that code is potentially buggy. I don't see
> any way to trigger the bug in coreutils, but it's just asking
> for trouble. Here's a proposed patch.
Hi Paul,
Thanks for working on that.
I had applied, tested and reviewed it earlier today,
as I was writing the changes below.
I've just noticed that I pushed it along with the quotearg/quote.h fix
that I pushed earlier today. Must remember always to put under-review
change-sets on separate topic branch, not on master. Sorry for the lapse.
>>From 4954a3517397dadd217d6244e961dd855fbadbef Mon Sep 17 00:00:00 2001
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> Date: Tue, 6 Mar 2012 15:19:24 -0800
> Subject: [PATCH] readtokens: avoid core dumps with unusual calling patterns
>
> Reported by Xu Zhongxing in <http://debbugs.gnu.org/10953>.
> * lib/readtokens.c: Include limits.h.
> (word, bits_per_word, get_nth_bit, set_nth_bit): New.
> (readtoken): Don't cache the delimiters; the cache code was buggy
> if !delim && saved_delim, or if the new n_delim differs from the old.
> Also, it wasn't thread-safe.
Here's a proposed readtokens test module:
From 52605d539a37d4d303e7863d946e85bef21bbcc3 Mon Sep 17 00:00:00 2001
From: Jim Meyering <meyering <at> redhat.com>
Date: Wed, 7 Mar 2012 12:16:30 +0100
Subject: [PATCH] readtokens: add tests
* modules/readtokens-tests: New file.
* tests/test-readtokens.c: New file.
* tests/test-readtokens.sh: New file.
---
ChangeLog | 6 +++
modules/readtokens-tests | 13 ++++++
tests/test-readtokens.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++
tests/test-readtokens.sh | 23 +++++++++++
4 files changed, 140 insertions(+)
create mode 100644 modules/readtokens-tests
create mode 100644 tests/test-readtokens.c
create mode 100755 tests/test-readtokens.sh
diff --git a/ChangeLog b/ChangeLog
index 8ac1ba4..83a09a4 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2012-03-07 Jim Meyering <meyering <at> redhat.com>
+ readtokens: add tests
+ * modules/readtokens-tests: New file.
+ * tests/test-readtokens.c: New file.
+
+2012-03-07 Jim Meyering <meyering <at> redhat.com>
+
quotearg: the module must now include quote.h
With commit v0.0-7133-g6417476, quotearg.c includes "quote.h".
So must the module.
diff --git a/modules/readtokens-tests b/modules/readtokens-tests
new file mode 100644
index 0000000..a1982dd
--- /dev/null
+++ b/modules/readtokens-tests
@@ -0,0 +1,13 @@
+Files:
+tests/macros.h
+tests/test-readtokens.c
+tests/test-readtokens.sh
+
+Depends-on:
+closeout
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-readtokens.sh
+check_PROGRAMS += test-readtokens
diff --git a/tests/test-readtokens.c b/tests/test-readtokens.c
new file mode 100644
index 0000000..b0af5c8
--- /dev/null
+++ b/tests/test-readtokens.c
@@ -0,0 +1,98 @@
+/* Test the readtokens module.
+ Copyright (C) 2012 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include <config.h>
+#include <stdbool.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "readtokens.h"
+#include "closeout.h"
+#include "macros.h"
+
+static void
+basic (void)
+{
+ char *filename = "in.827";
+ int fd = open (filename, O_CREAT | O_WRONLY, 0600);
+ ASSERT (fd >= 0);
+ ASSERT (write (fd, "a|b;c+d", 7) == 7);
+ ASSERT (close (fd) == 0);
+
+ {
+ token_buffer tb;
+ FILE *fp = fopen (filename, "r");
+ ASSERT (fp);
+
+ init_tokenbuffer (&tb);
+ ASSERT (readtoken (fp, "|;", 2, &tb) == 1 && tb.buffer[0] == 'a');
+ ASSERT (readtoken (fp, "|;", 2, &tb) == 1 && tb.buffer[0] == 'b');
+ ASSERT (readtoken (fp, "+", 1, &tb) == 1 && tb.buffer[0] == 'c');
+ ASSERT (readtoken (fp, "-", 1, &tb) == 1 && tb.buffer[0] == 'd');
+ ASSERT (readtoken (fp, "%", 0, &tb) == (size_t) -1);
+ ASSERT ( ! ferror (fp));
+ ASSERT (fclose (fp) == 0);
+ }
+}
+
+int
+main (int argc, char **argv)
+{
+ token_buffer tb;
+ char *delim;
+ size_t delim_len;
+ bool ok = true;
+
+ atexit (close_stdout);
+
+ if (argc == 1)
+ {
+ basic ();
+ return 0;
+ }
+
+ init_tokenbuffer (&tb);
+
+ if (argc != 2)
+ return 99;
+
+ delim = argv[1];
+ delim_len = strlen (delim);
+
+ if (STREQ (delim, "\\0"))
+ {
+ delim = "";
+ delim_len = 1;
+ }
+
+ while (1)
+ {
+ size_t token_length = readtoken (stdin, delim, delim_len, &tb);
+ if (token_length == (size_t) -1)
+ break;
+ fwrite (tb.buffer, 1, token_length, stdout);
+ putchar (':');
+ }
+ putchar ('\n');
+ free (tb.buffer);
+
+ ASSERT ( ! ferror (stdin));
+
+ return 0;
+}
diff --git a/tests/test-readtokens.sh b/tests/test-readtokens.sh
new file mode 100755
index 0000000..51fd41e
--- /dev/null
+++ b/tests/test-readtokens.sh
@@ -0,0 +1,23 @@
+#!/bin/sh
+. "${srcdir=.}/init.sh"; path_prepend_ .
+
+fail=0
+
+test-readtokens || fail=1
+
+# Simplest case.
+echo a:b:c: > exp || fail=1
+printf a:b:c | test-readtokens : > out 2>&1 || fail=1
+compare exp out || fail=1
+
+# Use NUL as the delimiter.
+echo a:b:c: > exp || fail=1
+printf 'a\0b\0c' | test-readtokens '\0' > out 2>&1 || fail=1
+compare exp out || fail=1
+
+# Two delimiter bytes, and adjacent delimiters in the input.
+echo a:b:c: > exp || fail=1
+printf a:-:b-:c:: | test-readtokens :- > out 2>&1 || fail=1
+compare exp out || fail=1
+
+Exit $fail
--
1.7.9.3.363.g121f0
Reply sent
to
Paul Eggert <eggert <at> cs.ucla.edu>:
You have taken responsibility.
(Wed, 07 Mar 2012 19:59:02 GMT)
Full text and
rfc822 format available.
Notification sent
to
Xu Zhongxing <xu_zhong_xing <at> 163.com>:
bug acknowledged by developer.
(Wed, 07 Mar 2012 19:59:02 GMT)
Full text and
rfc822 format available.
Message #22 received at 10953-done <at> debbugs.gnu.org (full text, mbox):
On 03/07/2012 11:52 AM, Jim Meyering wrote:
> Here's a proposed readtokens test module:
I took a quick look, and it looks fine, thanks.
The bug's fixed now, so I'm marking it as 'done'.
Message #23 received at 10953-done <at> debbugs.gnu.org (full text, mbox):
Paul Eggert wrote:
> On 03/07/2012 11:52 AM, Jim Meyering wrote:
>> Here's a proposed readtokens test module:
>
> I took a quick look, and it looks fine, thanks.
Thanks for the quick review.
While I'd tested like this,
./gnulib-tool --create-testdir --with-tests --test readtokens
I nearly forgot to compile with warnings enabled,
so nearly missed an unused variable and the lack of <unistd.h>
for declarations of write and close.
Just pushed.
> The bug's fixed now, so I'm marking it as 'done'.
Thanks!
bug archived.
Request was from
Debbugs Internal Request <help-debbugs <at> gnu.org>
to
internal_control <at> debbugs.gnu.org.
(Thu, 05 Apr 2012 11:24:03 GMT)
Full text and
rfc822 format available.
This bug report was last modified 12 years and 23 days ago.
Previous Next
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.