[COMMITTED 2.22] Handle overflow in __hcreate_r

[COMMITTED 2.22] Handle overflow in __hcreate_r

[Aurelien Jarno]

From: Ondřej Bílka <neleai@seznam.cz>

Hi,

As in bugzilla entry there is overflow in hsearch when looking for prime
number as SIZE_MAX - 1 is divisible by 5. We fix that by rejecting large
inputs before looking for prime.

	* misc/hsearch_r.c (__hcreate_r): Handle overflow.

(cherry picked from commit 2f5c1750558fe64bac361f52d6827ab1bcfe52bc)
---
 ChangeLog        | 5 +++++
 misc/hsearch_r.c | 9 ++++++++-
 2 files changed, 13 insertions(+), 1 deletion(-)

diff --git a/ChangeLog b/ChangeLog
index 9740c89..e818995 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2015-08-25  Ondřej Bílka  <neleai@seznam.cz>
+
+	[BZ #18240]
+	* misc/hsearch_r.c (__hcreate_r): Handle overflow.
+
 2015-10-27  Ludovic Courtès  <ludo@gnu.org>
 
 	* locale/loadlocale.c (_nl_intern_locale_data): Change assertion
diff --git a/misc/hsearch_r.c b/misc/hsearch_r.c
index 9f55e84..559df29 100644
--- a/misc/hsearch_r.c
+++ b/misc/hsearch_r.c
@@ -19,7 +19,7 @@
 #include <errno.h>
 #include <malloc.h>
 #include <string.h>
-
+#include <stdint.h>
 #include <search.h>
 
 /* [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
@@ -73,6 +73,13 @@ __hcreate_r (nel, htab)
       return 0;
     }
 
+  if (nel >= SIZE_MAX / sizeof (_ENTRY))
+    {
+      __set_errno (ENOMEM);
+      return 0;
+    }
+
+
   /* There is still another table active. Return with error. */
   if (htab->table != NULL)
     return 0;
-- 
2.7.0.rc3

[COMMITTED 2.22] Improve check against integer wraparound in hcreate_r [BZ #18240]

[Aurelien Jarno]

From: Florian Weimer <fweimer@redhat.com>

(cherry picked from commit bae7c7c764413b23e61cb099ce33be4c4ee259bb)
---
 ChangeLog        | 12 +++++++++
 NEWS             |  4 +--
 misc/Makefile    |  2 +-
 misc/bug18240.c  | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 misc/hsearch_r.c | 35 +++++++++++++-------------
 5 files changed, 107 insertions(+), 21 deletions(-)
 create mode 100644 misc/bug18240.c

diff --git a/ChangeLog b/ChangeLog
index e818995..ed20b9b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,15 @@
+2016-01-27  Paul Eggert  <eggert@cs.ucla.edu>
+
+	[BZ #18240]
+	* misc/hsearch_r.c (isprime, __hcreate_r): Protect against
+	unsigned int wraparound.
+
+2016-01-27  Florian Weimer  <fweimer@redhat.com>
+
+	[BZ #18240]
+	* misc/bug18240.c: New test.
+	* misc/Makefile (tests): Add it.
+
 2015-08-25  Ondřej Bílka  <neleai@seznam.cz>
 
 	[BZ #18240]
diff --git a/NEWS b/NEWS
index 99e68d2..d1daf9b 100644
--- a/NEWS
+++ b/NEWS
@@ -9,8 +9,8 @@ Version 2.22.1
 
 * The following bugs are resolved with this release:
 
-  17905, 18421, 18480, 18589, 18743, 18778, 18781, 18787, 18796, 18870,
-  18887, 18921, 18928, 18969, 18985, 19018, 19058, 19174, 19178.
+  17905, 18420, 18421, 18480, 18589, 18743, 18778, 18781, 18787, 18796,
+  18870, 18887, 18921, 18928, 18969, 18985, 19018, 19058, 19174, 19178.
 
 * The LD_POINTER_GUARD environment variable can no longer be used to
   disable the pointer guard feature.  It is always enabled.
diff --git a/misc/Makefile b/misc/Makefile
index 2f5edf6..12055ce 100644
--- a/misc/Makefile
+++ b/misc/Makefile
@@ -77,7 +77,7 @@ gpl2lgpl := error.c error.h
 
 tests := tst-dirname tst-tsearch tst-fdset tst-efgcvt tst-mntent tst-hsearch \
 	 tst-error1 tst-pselect tst-insremque tst-mntent2 bug-hsearch1 \
-	 tst-mntent-blank-corrupt tst-mntent-blank-passno
+	 tst-mntent-blank-corrupt tst-mntent-blank-passno bug18240
 ifeq ($(run-built-tests),yes)
 tests-special += $(objpfx)tst-error1-mem.out
 endif
diff --git a/misc/bug18240.c b/misc/bug18240.c
new file mode 100644
index 0000000..4b26865
--- /dev/null
+++ b/misc/bug18240.c
@@ -0,0 +1,75 @@
+/* Test integer wraparound in hcreate.
+   Copyright (C) 2016 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <errno.h>
+#include <limits.h>
+#include <search.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+static void
+test_size (size_t size)
+{
+  int res = hcreate (size);
+  if (res == 0)
+    {
+      if (errno == ENOMEM)
+        return;
+      printf ("error: hcreate (%zu): %m\n", size);
+      exit (1);
+    }
+  char *keys[100];
+  for (int i = 0; i < 100; ++i)
+    {
+      if (asprintf (keys + i, "%d", i) < 0)
+        {
+          printf ("error: asprintf: %m\n");
+          exit (1);
+        }
+      ENTRY e = { keys[i], (char *) "value" };
+      if (hsearch (e, ENTER) == NULL)
+        {
+          printf ("error: hsearch (\"%s\"): %m\n", keys[i]);
+          exit (1);
+        }
+    }
+  hdestroy ();
+
+  for (int i = 0; i < 100; ++i)
+    free (keys[i]);
+}
+
+static int
+do_test (void)
+{
+  test_size (500);
+  test_size (-1);
+  test_size (-3);
+  test_size (INT_MAX - 2);
+  test_size (INT_MAX - 1);
+  test_size (INT_MAX);
+  test_size (((unsigned) INT_MAX) + 1);
+  test_size (UINT_MAX - 2);
+  test_size (UINT_MAX - 1);
+  test_size (UINT_MAX);
+  return 0;
+}
+
+#define TEST_FUNCTION do_test ()
+#include "../test-skeleton.c"
diff --git a/misc/hsearch_r.c b/misc/hsearch_r.c
index 559df29..661f0f6 100644
--- a/misc/hsearch_r.c
+++ b/misc/hsearch_r.c
@@ -46,15 +46,12 @@ static int
 isprime (unsigned int number)
 {
   /* no even number will be passed */
-  unsigned int div = 3;
-
-  while (div * div < number && number % div != 0)
-    div += 2;
-
-  return number % div != 0;
+  for (unsigned int div = 3; div <= number / div; div += 2)
+    if (number % div == 0)
+      return 0;
+  return 1;
 }
 
-
 /* Before using the hash table we must allocate memory for it.
    Test for an existing table are done. We allocate one element
    more as the found prime number says. This is done for more effective
@@ -73,13 +70,6 @@ __hcreate_r (nel, htab)
       return 0;
     }
 
-  if (nel >= SIZE_MAX / sizeof (_ENTRY))
-    {
-      __set_errno (ENOMEM);
-      return 0;
-    }
-
-
   /* There is still another table active. Return with error. */
   if (htab->table != NULL)
     return 0;
@@ -88,10 +78,19 @@ __hcreate_r (nel, htab)
      use will not work.  */
   if (nel < 3)
     nel = 3;
-  /* Change nel to the first prime number not smaller as nel. */
-  nel |= 1;      /* make odd */
-  while (!isprime (nel))
-    nel += 2;
+
+  /* Change nel to the first prime number in the range [nel, UINT_MAX - 2],
+     The '- 2' means 'nel += 2' cannot overflow.  */
+  for (nel |= 1; ; nel += 2)
+    {
+      if (UINT_MAX - 2 < nel)
+	{
+	  __set_errno (ENOMEM);
+	  return 0;
+	}
+      if (isprime (nel))
+	break;
+    }
 
   htab->size = nel;
   htab->filled = 0;
-- 
2.7.0.rc3

Re: [COMMITTED 2.22] Handle overflow in __hcreate_r

[Tulio Magno Quites Machado Filho]

Mike Frysinger <vapier@gentoo.org> writes:

> On 02 Feb 2016 10:34, Tulio Magno Quites Machado Filho wrote:
>> Aurelien Jarno <aurelien@aurel32.net> writes:
>> 
>> > diff --git a/ChangeLog b/ChangeLog
>> > index 9740c89..e818995 100644
>> > --- a/ChangeLog
>> > +++ b/ChangeLog
>> > @@ -1,3 +1,8 @@
>> > +2015-08-25  Ondřej Bílka  <neleai@seznam.cz>
>> 
>> Interesting... I noticed you kept the original date in the ChangeLog.
>> 
>> Should we update the date entry when backporting patches to stable branches?
>
> i think a lot of us have because cherry-pick does it for us.

Have updated the ChangeLog date?
If so, what is the magic you've done to let cherry-pick do that?
I always change that by hand.

> i think the date is largely worthless, so leaving it the same as the original
> is fine.

Yes.  I just wanted to follow the same steps you're all following.  If that
means getting rid of a manual step, it's even better.

Thanks!

-- 
Tulio Magno

Re: [COMMITTED 2.22] Handle overflow in __hcreate_r

[Tulio Magno Quites Machado Filho]

Aurelien Jarno <aurelien@aurel32.net> writes:

> diff --git a/ChangeLog b/ChangeLog
> index 9740c89..e818995 100644
> --- a/ChangeLog
> +++ b/ChangeLog
> @@ -1,3 +1,8 @@
> +2015-08-25  Ondřej Bílka  <neleai@seznam.cz>

Interesting... I noticed you kept the original date in the ChangeLog.

Should we update the date entry when backporting patches to stable branches?

-- 
Tulio Magno

Re: [COMMITTED 2.22] Handle overflow in __hcreate_r

[Mike Frysinger]

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

On 02 Feb 2016 15:48, Tulio Magno Quites Machado Filho wrote:
> Mike Frysinger <vapier@gentoo.org> writes:
> > On 02 Feb 2016 10:34, Tulio Magno Quites Machado Filho wrote:
> >> Aurelien Jarno <aurelien@aurel32.net> writes:
> >> 
> >> > diff --git a/ChangeLog b/ChangeLog
> >> > index 9740c89..e818995 100644
> >> > --- a/ChangeLog
> >> > +++ b/ChangeLog
> >> > @@ -1,3 +1,8 @@
> >> > +2015-08-25  Ondřej Bílka  <neleai@seznam.cz>
> >> 
> >> Interesting... I noticed you kept the original date in the ChangeLog.
> >> 
> >> Should we update the date entry when backporting patches to stable branches?
> >
> > i think a lot of us have because cherry-pick does it for us.
> 
> Have updated the ChangeLog date?
> If so, what is the magic you've done to let cherry-pick do that?
> I always change that by hand.

check out:
https://sourceware.org/glibc/wiki/GlibcGit#ChangeLog
-mike

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [COMMITTED 2.22] Handle overflow in __hcreate_r

[Mike Frysinger]

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

On 02 Feb 2016 10:34, Tulio Magno Quites Machado Filho wrote:
> Aurelien Jarno <aurelien@aurel32.net> writes:
> 
> > diff --git a/ChangeLog b/ChangeLog
> > index 9740c89..e818995 100644
> > --- a/ChangeLog
> > +++ b/ChangeLog
> > @@ -1,3 +1,8 @@
> > +2015-08-25  Ondřej Bílka  <neleai@seznam.cz>
> 
> Interesting... I noticed you kept the original date in the ChangeLog.
> 
> Should we update the date entry when backporting patches to stable branches?

i think a lot of us have because cherry-pick does it for us.  i think
the date is largely worthless, so leaving it the same as the original
is fine.
-mike

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]