# HG changeset patch # User Bruno Haible # Date 1517596322 -3600 # Node ID 6a04b04905e5025eb21c4d40c82cf3811b5a240b # Parent c153a5913479882b4433a81c265cedabdf945bd2 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 -r c153a5913479 -r 6a04b04905e5 ChangeLog --- a/ChangeLog Wed Jan 31 09:04:52 2018 +0100 +++ b/ChangeLog Fri Feb 02 19:32:02 2018 +0100 @@ -1,3 +1,22 @@ +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. + 2018-01-31 Bruno Haible environ: Fix link error on 64-bit Cygwin. diff -r c153a5913479 -r 6a04b04905e5 lib/malloca.c --- a/lib/malloca.c Wed Jan 31 09:04:52 2018 +0100 +++ b/lib/malloca.c Fri Feb 02 19:32:02 2018 +0100 @@ -1,6 +1,6 @@ /* Safe automatic memory allocation. Copyright (C) 2003, 2006-2007, 2009-2018 Free Software Foundation, Inc. - Written by Bruno Haible , 2003. + 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,92 +21,45 @@ /* 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 freea(), and - when freea() frees it, it also removes it from the hash table. */ + are only invoked for big memory sizes. + Here we use a bit in the address as an indicator, an idea by Ondřej Bílka. + malloca() can return three types of pointers: + - Pointers ≡ 0 mod 2*sa_alignment_max come from stack allocation. + - Pointers ≡ sa_alignment_max mod 2*sa_alignment_max come from heap + allocation. + - NULL comes from a failed heap allocation. */ -#define MAGIC_NUMBER 0x1415fb4a -#define MAGIC_SIZE sizeof (int) -/* This is how the header info would look like without any alignment - considerations. */ -struct preliminary_header { void *next; int magic; }; -/* But the header's size must be a multiple of sa_alignment_max. */ -#define HEADER_SIZE \ - (((sizeof (struct preliminary_header) + sa_alignment_max - 1) / sa_alignment_max) * sa_alignment_max) -union header { - void *next; - struct { - char room[HEADER_SIZE - MAGIC_SIZE]; - int word; - } magic; -}; -verify (HEADER_SIZE == sizeof (union header)); -/* We make the hash table quite big, so that during lookups the probability - of empty hash buckets is quite high. There is no need to make the hash - table resizable, because when the hash table gets filled so much that the - lookup becomes slow, it means that the application has memory leaks. */ -#define HASH_TABLE_SIZE 257 -static void * mmalloca_results[HASH_TABLE_SIZE]; - -#endif +/* Type for holding very small pointer differences. */ +typedef unsigned char small_t; void * mmalloca (size_t n) { #if HAVE_ALLOCA - /* Allocate one more word, that serves as an indicator for malloc()ed - memory, so that freea() of an alloca() result is fast. */ - size_t nplus = n + HEADER_SIZE; + /* Allocate one more word, 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; if (nplus >= n) { - void *p = malloc (nplus); - - if (p != NULL) - { - size_t slot; - union header *h = p; - - p = h + 1; + char *mem = (char *) malloc (nplus); - /* Put a magic number into the indicator word. */ - h->magic.word = MAGIC_NUMBER; - - /* Enter p into the hash table. */ - slot = (uintptr_t) p % HASH_TABLE_SIZE; - h->next = mmalloca_results[slot]; - mmalloca_results[slot] = p; - + 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); + /* Here p >= mem + sizeof (small_t), + and p <= mem + sizeof (small_t) + 2 * sa_alignment_max - 1 + hence p + n <= mem + nplus. + So, the memory range [p, p+n) lies in the allocated memory range + [mem, mem + nplus). */ + ((small_t *) p)[-1] = p - mem; + /* p ≡ sa_alignment_max mod 2*sa_alignment_max. */ return p; } } @@ -122,38 +75,21 @@ } #if HAVE_ALLOCA -void NO_SANITIZE_MEMORY +void freea (void *p) { - /* mmalloca() may have returned NULL. */ - if (p != NULL) + /* Determine whether p was a non-NULL pointer returned by mmalloca(). */ + if ((uintptr_t) p & sa_alignment_max) { - /* Attempt to quickly distinguish the mmalloca() result - which has - a magic indicator word - and the alloca() result - which has an - uninitialized indicator word. It is for this test that sa_increment - additional bytes are allocated in the alloca() case. */ - if (((int *) p)[-1] == MAGIC_NUMBER) - { - /* Looks like a mmalloca() result. To see whether it really is one, - perform a lookup in the hash table. */ - size_t slot = (uintptr_t) p % HASH_TABLE_SIZE; - void **chain = &mmalloca_results[slot]; - for (; *chain != NULL;) - { - union header *h = p; - if (*chain == p) - { - /* Found it. Remove it from the hash table and free it. */ - union header *p_begin = h - 1; - *chain = p_begin->next; - free (p_begin); - return; - } - h = *chain; - chain = &h[-1].next; - } - } - /* At this point, we know it was not a mmalloca() result. */ + void *mem = (char *) p - ((small_t *) p)[-1]; + free (mem); } } #endif + +/* + * Hey Emacs! + * Local Variables: + * coding: utf-8 + * End: + */ diff -r c153a5913479 -r 6a04b04905e5 lib/malloca.h --- a/lib/malloca.h Wed Jan 31 09:04:52 2018 +0100 +++ b/lib/malloca.h Fri Feb 02 19:32:02 2018 +0100 @@ -56,8 +56,10 @@ 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 @@ | (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 -r c153a5913479 -r 6a04b04905e5 lib/malloca.valgrind --- a/lib/malloca.valgrind Wed Jan 31 09:04:52 2018 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,7 +0,0 @@ -# Suppress a valgrind message about use of uninitialized memory in freea(). -# This use is OK because it provides only a speedup. -{ - freea - Memcheck:Cond - fun:freea -} diff -r c153a5913479 -r 6a04b04905e5 lib/xmalloca.h --- a/lib/xmalloca.h Wed Jan 31 09:04:52 2018 +0100 +++ b/lib/xmalloca.h Fri Feb 02 19:32:02 2018 +0100 @@ -32,8 +32,10 @@ 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 -r c153a5913479 -r 6a04b04905e5 modules/malloca --- a/modules/malloca Wed Jan 31 09:04:52 2018 +0100 +++ b/modules/malloca Fri Feb 02 19:32:02 2018 +0100 @@ -4,7 +4,6 @@ Files: lib/malloca.h lib/malloca.c -lib/malloca.valgrind m4/malloca.m4 m4/eealloc.m4 m4/longlong.m4 @@ -13,7 +12,6 @@ alloca-opt stdint xalloc-oversized -verify configure.ac: gl_MALLOCA