Re: malloca, freea are not thread-safe

[Bruno Haible]

Hi Florian,

> Could we please fix this issue along those lines?  Thanks.

Done:


2018-02-02  Bruno Haible  

malloca, xmalloca: Make multithread-safe.
Reported by Florian Weimer .
Implements an idea by Ondřej Bílka .
* lib/malloca.h (malloca): In the stack allocation case, return a
pointer that is a multiple of 2 * sa_alignment_max.
(sa_increment): Remove enum item.
* lib/xmalloca.h (xmalloca): In the stack allocation case, return
a pointer that is a multiple of 2 * sa_alignment_max.
* lib/malloca.c (NO_SANITIZE_MEMORY): Remove macro.
(MAGIC_NUMBER, MAGIC_SIZE, preliminary_header, HEADER_SIZE, header,
HASH_TABLE_SIZE, mmalloca_results): Remove.
(small_t): New type.
(mmalloca, free): Rewritten.
* lib/malloca.valgrind: Remove file.
* modules/malloca (Files): Remove it.
(Depends-on): Remove verify.

diff --git a/lib/malloca.h b/lib/malloca.h
index 8278c58..cbc8fe7 100644
--- a/lib/malloca.h
+++ b/lib/malloca.h
@@ -56,8 +56,10 @@ extern "C" {
the function returns.  Upon failure, it returns NULL.  */
 #if HAVE_ALLOCA
 # define malloca(N) \
-  ((N) < 4032 - sa_increment\
-   ? (void *) ((char *) alloca ((N) + sa_increment) + sa_increment) \
+  ((N) < 4032 - (2 * sa_alignment_max - 1)  \
+   ? (void *) (((uintptr_t) alloca ((N) + 2 * sa_alignment_max - 1) \
++ (2 * sa_alignment_max - 1))   \
+   & ~(uintptr_t)(2 * sa_alignment_max - 1))\
: mmalloca (N))
 #else
 # define malloca(N) \
@@ -119,10 +121,7 @@ enum
   | (sa_alignment_longlong - 1)
 #endif
   | (sa_alignment_longdouble - 1)
- ) + 1,
-/* The increment that guarantees room for a magic word must be >= sizeof (int)
-   and a multiple of sa_alignment_max.  */
-  sa_increment = ((sizeof (int) + sa_alignment_max - 1) / sa_alignment_max) * 
sa_alignment_max
+ ) + 1
 };
 
 #endif /* _MALLOCA_H */
diff --git a/lib/xmalloca.h b/lib/xmalloca.h
index 456f25b..14fc1b9 100644
--- a/lib/xmalloca.h
+++ b/lib/xmalloca.h
@@ -32,8 +32,10 @@ extern "C" {
the function returns.  Upon failure, it exits with an error message.  */
 #if HAVE_ALLOCA
 # define xmalloca(N) \
-  ((N) < 4032 - sa_increment\
-   ? (void *) ((char *) alloca ((N) + sa_increment) + sa_increment) \
+  ((N) < 4032 - (2 * sa_alignment_max - 1)  \
+   ? (void *) (((uintptr_t) alloca ((N) + 2 * sa_alignment_max - 1) \
++ (2 * sa_alignment_max - 1))   \
+   & ~(uintptr_t)(2 * sa_alignment_max - 1))\
: xmmalloca (N))
 extern void * xmmalloca (size_t n);
 #else
diff --git a/lib/malloca.c b/lib/malloca.c
*** a/lib/malloca.c
--- b/lib/malloca.c
***
*** 1,6 
  /* Safe automatic memory allocation.
 Copyright (C) 2003, 2006-2007, 2009-2018 Free Software Foundation, Inc.
!Written by Bruno Haible , 2003.
  
 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
--- 1,6 
  /* Safe automatic memory allocation.
 Copyright (C) 2003, 2006-2007, 2009-2018 Free Software Foundation, Inc.
!Written by Bruno Haible , 2003, 2018.
  
 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
***
*** 21,112 
  /* Specification.  */
  #include "malloca.h"
  
- #include 
- 
- #include "verify.h"
- 
- /* Silence a warning from clang's MemorySanitizer.  */
- #if defined __has_feature
- # if __has_feature(memory_sanitizer)
- #  define NO_SANITIZE_MEMORY __attribute__((no_sanitize("memory")))
- # endif
- #endif
- #ifndef NO_SANITIZE_MEMORY
- # define NO_SANITIZE_MEMORY
- #endif
- 
  /* The speed critical point in this file is freea() applied to an alloca()
 result: it must be fast, to match the speed of alloca().  The speed of
 mmalloca() and freea() in the other case are not critical, because they
!are only invoked for big memory sizes.  */
! 
! #if HAVE_ALLOCA
! 
! /* Store the mmalloca() results in a hash table.  This is needed to reliably
!distinguish a mmalloca() result and an alloca() result.
! 
!Although it is possible that the same pointer is returned by alloca() and
!by mmalloca() at different times in the same application, it does not lead
!to a bug in freea(), because:
!  - Before a pointer returned by alloca() can point into malloc()ed memory,
!the function must return, and once this has happened the programmer 
must
!not call freea() on it anyway.
!  - Before a pointer returned by mmalloca() can point into the stack, it
!must be freed.  The only function that can free it is 

localename test failure on OpenIndiana

[Bruno Haible]

There was a fix for the 'localename' module on Solaris 12 [1], but Solaris 12
is now dead [2][3].

The Solaris 11 variant called OpenIndiana (based on Illumos) fails the
'localename' tests. This patch fixes it.

On the other Solaris 11 variants, Solaris 11.3 and Dyson, the 'uselocale'
function does not exist in libc, therefore the gl_locale_name_thread()
function is a dummy and the tests don't exercise this functionality.

[1] https://lists.gnu.org/archive/html/bug-gnulib/2015-01/msg00078.html
[2] 
https://arstechnica.com/information-technology/2017/01/oracle-sort-of-confirms-demise-of-solaris-12-effort/
[3] 
http://www.itprotoday.com/software-development/new-oracle-layoffs-probably-signal-end-line-solaris


2018-02-02  Bruno Haible  

localename: Add support for OpenIndiana.
* lib/localename.c (gl_locale_name_thread_unsafe): Add code for
Solaris 11 variants with uselocale() but without getlocalename_l().

diff --git a/lib/localename.c b/lib/localename.c
index 00cf997..2133cbc 100644
--- a/lib/localename.c
+++ b/lib/localename.c
@@ -2592,7 +2592,7 @@ get_lcid (const char *locale_name)
 #endif
 
 
-#if HAVE_USELOCALE /* glibc, Solaris >= 12 or Mac OS X */
+#if HAVE_USELOCALE /* glibc, Mac OS X, Solaris 11 OpenIndiana, or Solaris 12  
*/
 
 /* Simple hash set of strings.  We don't want to drag in lots of hash table
code here.  */
@@ -2731,9 +2731,27 @@ gl_locale_name_thread_unsafe (int category, const char 
*categoryname)
 return "";
   }
 return querylocale (mask, thread_locale);
-#  elif defined __sun && HAVE_GETLOCALENAME_L
+#  elif defined __sun
+#   if HAVE_GETLOCALENAME_L
 /* Solaris >= 12.  */
 return getlocalename_l (category, thread_locale);
+#   else
+/* Solaris 11 OpenIndiana.
+   For the internal structure of locale objects, see
+   
https://github.com/OpenIndiana/illumos-gate/blob/master/usr/src/lib/libc/port/locale/localeimpl.h
  */
+switch (category)
+  {
+  case LC_CTYPE:
+  case LC_NUMERIC:
+  case LC_TIME:
+  case LC_COLLATE:
+  case LC_MONETARY:
+  case LC_MESSAGES:
+return ((const char * const *) thread_locale)[category];
+  default: /* We shouldn't get here.  */
+return "";
+  }
+#   endif
 #  elif defined __CYGWIN__
 /* Cygwin < 2.6 lacks uselocale and thread-local locales altogether.
Cygwin <= 2.6.1 lacks NL_LOCALE_NAME, requiring peeking inside

Re: malloca, freea are not thread-safe

[Paul Eggert]

On 02/02/2018 10:35 AM, Bruno Haible wrote:
Done: 


Thanks. Some comments, with a proposed patch attached:

  # define malloca(N) \
-  ((N) < 4032 - sa_increment\
-   ? (void *) ((char *) alloca ((N) + sa_increment) + sa_increment) \
+  ((N) < 4032 - (2 * sa_alignment_max - 1)  \
+   ? (void *) (((uintptr_t) alloca ((N) + 2 * sa_alignment_max - 1) \
++ (2 * sa_alignment_max - 1))   \
+   & ~(uintptr_t)(2 * sa_alignment_max - 1))\
 : mmalloca (N))


This can cause problems when -fcheck-pointer-bounds is in effect, since 
converting a pointer to uintptr_t and back means that GCC won't connect 
the resulting pointer to the original and this messes up bounds checking 
on the result.

! /* Type for holding very small pointer differences.  */
! typedef unsigned char small_t;
There should be a compile-time check guaranteeing that small_t is wide 
enough.

!   size_t nplus = n + sizeof (small_t) + 2 * sa_alignment_max - 1;
For expressions like these, it's a bit better to parenthesize the value 
added to N, mostly because it makes it clearer to the reader that we're 
just adding a constant. Also, on (admittedly-weird) platforms where 
SIZE_MAX <= INT_MAX, it avoids undefined behavior in some 
(admittedly-unusual) cases.



! void
   freea (void *p)
   {
!   /* Determine whether p was a non-NULL pointer returned by mmalloca().  */
!   if ((uintptr_t) p & sa_alignment_max)


This should be "((uintptr_t) p & (2 * sa_alignment_max - 1))", to make 
it more likely that a runtime error is detected if a garbage pointer is 
passed to freea.
From 381dccd214bae32992664a5bab432d166bdecd00 Mon Sep 17 00:00:00 2001
From: Paul Eggert 
Date: Fri, 2 Feb 2018 14:07:19 -0800
Subject: [PATCH] malloca, xmalloca: port to -fcheck-pointer-bounds
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* lib/malloca.c (small_t): Verify that it is wide enough.
(mmalloca) [HAVE_ALLOCA]: Be a bit safer about size arithmetic.
Use malloca_alignoff to avoid issues with -fcheck-pointer-bounds.
(freea): Always use ‘free’ when the pointer’s low-order bits
(sa_alignment_max - 1) are nonzero.  This is cheap and can catch
bad pointers earlier.
* lib/malloca.h (malloca_alignoff): New macro.
(malloca) [HAVE_ALLOCA]: Use it.
* lib/xmalloca.h (xmalloca) [HAVE_ALLOCA]: Use it.
* modules/malloca (Depends-on): Add verify.
---
 ChangeLog   | 14 ++
 lib/malloca.c   | 21 +
 lib/malloca.h   | 25 ++---
 lib/xmalloca.h  |  6 +++---
 modules/malloca |  1 +
 5 files changed, 53 insertions(+), 14 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 898d27592..30eec2148 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,17 @@
+2018-02-02  Paul Eggert  
+
+   malloca, xmalloca: port to -fcheck-pointer-bounds
+   * lib/malloca.c (small_t): Verify that it is wide enough.
+   (mmalloca) [HAVE_ALLOCA]: Be a bit safer about size arithmetic.
+   Use malloca_alignoff to avoid issues with -fcheck-pointer-bounds.
+   (freea): Always use ‘free’ when the pointer’s low-order bits
+   (sa_alignment_max - 1) are nonzero.  This is cheap and can catch
+   bad pointers earlier.
+   * lib/malloca.h (malloca_alignoff): New macro.
+   (malloca) [HAVE_ALLOCA]: Use it.
+   * lib/xmalloca.h (xmalloca) [HAVE_ALLOCA]: Use it.
+   * modules/malloca (Depends-on): Add verify.
+
 2018-02-02  Bruno Haible  
 
malloca, xmalloca: Make multithread-safe.
diff --git a/lib/malloca.c b/lib/malloca.c
index 5741cba6f..f764add4d 100644
--- a/lib/malloca.c
+++ b/lib/malloca.c
@@ -21,6 +21,8 @@
 /* Specification.  */
 #include "malloca.h"
 
+#include "verify.h"
+
 /* The speed critical point in this file is freea() applied to an alloca()
result: it must be fast, to match the speed of alloca().  The speed of
mmalloca() and freea() in the other case are not critical, because they
@@ -34,14 +36,15 @@
 
 /* Type for holding very small pointer differences.  */
 typedef unsigned char small_t;
+verify (2 * sa_alignment_max - 1 <= (small_t) -1);
 
 void *
 mmalloca (size_t n)
 {
 #if HAVE_ALLOCA
-  /* Allocate one more word, used to determine the address to pass to freea(),
+  /* Allocate one more byte, used to determine the address to pass to freea(),
  and room for the alignment ≡ sa_alignment_max mod 2*sa_alignment_max.  */
-  size_t nplus = n + sizeof (small_t) + 2 * sa_alignment_max - 1;
+  size_t nplus = n + (sizeof (small_t) + 2 * sa_alignment_max - 1);
 
   if (nplus >= n)
 {
@@ -49,10 +52,9 @@ mmalloca (size_t n)
 
   if (mem != NULL)
 {
-  char *p =
-(char *)uintptr_t)mem + sizeof (small_t) + sa_alignment_max - 
1)
-  & ~(uintptr_t)(2 * sa_alignment_max - 1))
- + sa_alignment_max);
+  char *p = malloca_alignoff (mem + (sizeof (small_t)
+ 

Re: localename test failure on OpenIndiana

[Paul Eggert]

On 02/02/2018 12:36 PM, Bruno Haible wrote:

There was a fix for the 'localename' module on Solaris 12 [1], but Solaris 12
is now dead [2][3].


Dead, or just renamed to Solaris 11.4?

https://blogs.oracle.com/solaris/oracle-solaris-114-beta-released

Re: malloca, freea are not thread-safe

[Bruno Haible]

Hi Paul,

> > ! void
> >freea (void *p)
> >{
> > !   /* Determine whether p was a non-NULL pointer returned by mmalloca().  
> > */
> > !   if ((uintptr_t) p & sa_alignment_max)
> 
> This should be "((uintptr_t) p & (2 * sa_alignment_max - 1))", to make 
> it more likely that a runtime error is detected if a garbage pointer is 
> passed to freea.

Changing the 'if' condition will not actually detect anything. The function
will still behave according to the "garbage in - garbage out" principle.
But you are right, it is possible here to detect invalid arguments. So let's
do so:


2018-02-02  Bruno Haible  

malloca: Add an argument check.
Suggested by Paul Eggert.
* lib/malloca.c (freea): Check against an invalid argument.

diff --git a/lib/malloca.c b/lib/malloca.c
index 5741cba..c5321d1 100644
--- a/lib/malloca.c
+++ b/lib/malloca.c
@@ -78,6 +78,12 @@ mmalloca (size_t n)
 void
 freea (void *p)
 {
+  /* Check argument.  */
+  if ((uintptr_t) p & (sa_alignment_max - 1))
+{
+  /* p was not the result of a malloca() call.  Invalid argument.  */
+  abort ();
+}
   /* Determine whether p was a non-NULL pointer returned by mmalloca().  */
   if ((uintptr_t) p & sa_alignment_max)
 {

Re: malloca, freea are not thread-safe

[Bruno Haible]

Paul Eggert wrote:
> > !   size_t nplus = n + sizeof (small_t) + 2 * sa_alignment_max - 1;
> For expressions like these, it's a bit better to parenthesize the value 
> added to N, mostly because it makes it clearer to the reader that we're 
> just adding a constant. Also, on (admittedly-weird) platforms where 
> SIZE_MAX <= INT_MAX, it avoids undefined behavior in some 
> (admittedly-unusual) cases.

Regarding the parentheses, I disagree: If we put parentheses they should
be like this:
size_t nplus = (n + sizeof (small_t)) + (2 * sa_alignment_max - 1);
because we want n + sizeof (small_t) consecutive bytes in memory, and the
other summand is for the alignment. Parenthesizing it in the way you suggest
would make the expression _more_ confusing.

I don't see any potential for undefined behaviour: we are taking a size_t
expression and adding a small constant (> 0, < 100). Undefined behaviour
in addition occurs only when signed integers overflow. If SIZE_MAX <= INT_MAX
we know that INT_MAX >= 2*SIZE_MAX-1 > SIZE_MAX + 100, therefore no 'int'
overflow is possible here.

Bruno

Re: malloca, freea are not thread-safe

[Bruno Haible]

Hi Paul,

> > ! /* Type for holding very small pointer differences.  */
> > ! typedef unsigned char small_t;
> There should be a compile-time check guaranteeing that small_t is wide 
> enough.

OK, if you like. Applied:


2018-02-02  Paul Eggert  

malloca: Add a compile-time verification.
* lib/malloca.c (small_t): Verify that it is wide enough.
* modules/malloca (Depends-on): Add verify.

diff --git a/lib/malloca.c b/lib/malloca.c
index c5321d1..c66e0c8 100644
--- a/lib/malloca.c
+++ b/lib/malloca.c
@@ -21,6 +21,8 @@
 /* Specification.  */
 #include "malloca.h"
 
+#include "verify.h"
+
 /* The speed critical point in this file is freea() applied to an alloca()
result: it must be fast, to match the speed of alloca().  The speed of
mmalloca() and freea() in the other case are not critical, because they
@@ -34,6 +36,8 @@
 
 /* Type for holding very small pointer differences.  */
 typedef unsigned char small_t;
+/* Verify that it is wide enough.  */
+verify (2 * sa_alignment_max - 1 <= (small_t) -1);
 
 void *
 mmalloca (size_t n)
diff --git a/modules/malloca b/modules/malloca
index 8f5ab64..0ae3fe0 100644
--- a/modules/malloca
+++ b/modules/malloca
@@ -11,6 +11,7 @@ m4/longlong.m4
 Depends-on:
 alloca-opt
 stdint
+verify
 xalloc-oversized
 
 configure.ac:

Re: malloca, freea are not thread-safe

[Paul Eggert]

On 02/02/2018 03:41 PM, Bruno Haible wrote:

Regarding the parentheses, I disagree: If we put parentheses they should
be like this:
 size_t nplus = (n + sizeof (small_t)) + (2 * sa_alignment_max - 1);
because we want n + sizeof (small_t) consecutive bytes in memory, and the
other summand is for the alignment. Parenthesizing it in the way you suggest
would make the expression_more_  confusing.


Well, it is a matter of style. Personally I find the expression 
confusing and would find it even more confusing with the extra 
parentheses. But perhaps that is because I am worried about integer 
overflow.



If SIZE_MAX <= INT_MAX
we know that INT_MAX >= 2*SIZE_MAX-1 > SIZE_MAX + 100, therefore no 'int'
overflow is possible here.


I was thinking about platforms where SIZE_MAX == INT_MAX, which POSIX 
and ISO C both allow; on such platforms 'int' overflow is possible. 
Admittedly platforms with idiosyncrasies like that are rare nowadays. I 
think Unisys stopped selling their oddball platforms in late 2015.

Re: malloca, freea are not thread-safe

[Bruno Haible]

Hi Paul,

> This can cause problems when -fcheck-pointer-bounds is in effect, since 
> converting a pointer to uintptr_t and back means that GCC won't connect 
> the resulting pointer to the original and this messes up bounds checking 
> on the result.

To be precise: What do you mean by "cause problems" and "messes up bounds
checking"? As far as I understand, it will disable bounds checking on the
returned pointer and its derivatives, right?

Speaking of bounds checking, the code (with or without your patch) will
not provide optimal bounds checking, because a pointer access to the
memory range that we added merely for alignment will not be reported as
an error. AFAIU, we need to tell GCC about the actual bounds, by use of
the functions listed in [1].

[1] https://gcc.gnu.org/onlinedocs/gcc/Pointer-Bounds-Checker-builtins.html

How about this? Will this work?


diff --git a/lib/malloca.c b/lib/malloca.c
index c66e0c8..411bee0 100644
--- a/lib/malloca.c
+++ b/lib/malloca.c
@@ -64,7 +64,13 @@ mmalloca (size_t n)
  [mem, mem + nplus).  */
   ((small_t *) p)[-1] = p - mem;
   /* p ≡ sa_alignment_max mod 2*sa_alignment_max.  */
+# if __GNUC__ >= 5 && !defined __cplusplus && !defined __clang__
+  /* Tell GCC about the allowed memory accesses based on p,
+ if -fcheck-pointer-bounds is in effect.  */
+  return __builtin___bnd_set_ptr_bounds (p, n);
+# else
   return p;
+# endif
 }
 }
   /* Out of memory.  */

Re: malloca, freea are not thread-safe

[Paul Eggert]

On 02/02/2018 04:03 PM, Bruno Haible wrote:

What do you mean by "cause problems" and "messes up bounds
checking"? As far as I understand, it will disable bounds checking on the
returned pointer and its derivatives, right?


I'm operating from memory here (my work desktop doesn't have MPX, nor do 
my school's servers), but as I recall GCC sometimes generated a pointer 
that had no bounds checking, and sometimes generated a pointer that 
could not be dereferenced. Both behaviors conform to ISO C.



How about this? Will this work?


Yes and no. In the sense of just getting -fcheck-pointer-bounds to work 
with GCC, it'll need some work and testing but is on the right path. For 
example, it should be safer to narrow the pointer than to set its bounds 
(this is assuming P currently has no bounds checking). Also, freea will 
need to widen its argument to dereference the alignment byte that 
precedes the memory block.


One other thing. An advantage of the #ifdef __CHKP__ code I suggested is 
that it never calculates a pointer outside the bounds of the 
newly-allocated block (or to just past the block). Such calculations 
violate the C standard, and I wouldn't be surprised if GCC or some other 
fancy optimizer exploits this to generate code to do the "wrong" thing 
with these calculations. With that in mind, I suppose in hindsight that 
my patch should have said "#ifdef __GNUC__" instead of "#ifdef __CHKP__".


By the way, why write "if __GNUC__ >= 5 && !defined __cplusplus && 
!defined __clang__" instead of "ifdef __CHKP__"? The latter is easier to 
read

Re: malloca, freea are not thread-safe

[Bruno Haible]

Hi Paul,

> By the way, why write "if __GNUC__ >= 5 && !defined __cplusplus && 
> !defined __clang__" instead of "ifdef __CHKP__"? The latter is easier to 
> read

I couldn't find any documentation for this __CHKP__ macro.

> An advantage of the #ifdef __CHKP__ code I suggested is 
> that it never calculates a pointer outside the bounds of the 
> newly-allocated block (or to just past the block). Such calculations 
> violate the C standard

The code that I committed does not have such "bad" pointers in intermediate
expressions either. It computes a valid pointer, converts it to uintptr_t,
does some arithmetic on it, and then converts back to a pointer. Since the
resulting pointer is in the malloc'ed range, it is valid.

Bruno