From 89b8139ba25466f02fc5d25e9b9af3af6b7370d7 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Tue, 20 Jan 2004 14:03:28 +0000 Subject: [PATCH] New module 'allocsa'. --- ChangeLog | 5 ++ MODULES.html.sh | 1 + lib/ChangeLog | 5 ++ lib/allocsa.c | 139 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/allocsa.h | 109 +++++++++++++++++++++++++++++++++++++ m4/ChangeLog | 4 ++ m4/allocsa.m4 | 17 ++++++ modules/allocsa | 25 +++++++++ 8 files changed, 305 insertions(+) create mode 100644 lib/allocsa.c create mode 100644 lib/allocsa.h create mode 100644 m4/allocsa.m4 create mode 100644 modules/allocsa diff --git a/ChangeLog b/ChangeLog index 0e1705d219..15f21c3674 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,8 @@ +2004-01-20 Bruno Haible + + * modules/allocsa: New file. + * MODULES.html.sh (func_all_modules): Add allocsa. + 2004-01-20 Bruno Haible * modules/eealloc: New file. diff --git a/MODULES.html.sh b/MODULES.html.sh index 736d34da29..738a38d790 100755 --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -1460,6 +1460,7 @@ func_all_modules () func_module xsize func_module xalloc func_module alloca + func_module allocsa func_end_table element="Integer arithmetic functions " diff --git a/lib/ChangeLog b/lib/ChangeLog index 5c40897f46..1d69735367 100644 --- a/lib/ChangeLog +++ b/lib/ChangeLog @@ -1,3 +1,8 @@ +2003-11-24 Bruno Haible + + * allocsa.h: New file, from GNU gettext. + * allocsa.c: New file, from GNU gettext. + 2003-11-24 Bruno Haible * eealloc.h: New file. diff --git a/lib/allocsa.c b/lib/allocsa.c new file mode 100644 index 0000000000..61e7a4e341 --- /dev/null +++ b/lib/allocsa.c @@ -0,0 +1,139 @@ +/* Safe automatic memory allocation. + Copyright (C) 2003 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 + the Free Software Foundation; either version 2, 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, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#ifdef HAVE_CONFIG_H +# include +#endif + +/* Specification. */ +#include "allocsa.h" + +/* The speed critical point in this file is freesa() applied to an alloca() + result: it must be fast, to match the speed of alloca(). The speed of + mallocsa() and freesa() in the other case are not critical, because they + are only invoked for big memory sizes. */ + +#if HAVE_ALLOCA + +/* Store the mallocsa() results in a hash table. This is needed to reliably + distinguish a mallocsa() result and an alloca() result. + + Although it is possible that the same pointer is returned by alloca() and + by mallocsa() at different times in the same application, it does not lead + to a bug in freesa(), 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 freesa() on it anyway. + - Before a pointer returned by mallocsa() can point into the stack, it + must be freed. The only function that can free it is freesa(), and + when freesa() frees it, it also removes it from the hash table. */ + +#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; char room[MAGIC_SIZE]; }; +/* 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) +struct header { void *next; char room[HEADER_SIZE - sizeof (struct preliminary_header) + MAGIC_SIZE]; }; +/* Verify that HEADER_SIZE == sizeof (struct header). */ +typedef int verify1[2 * (HEADER_SIZE == sizeof (struct header)) - 1]; +/* 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 * mallocsa_results[HASH_TABLE_SIZE]; + +#endif + +void * +mallocsa (size_t n) +{ +#if HAVE_ALLOCA + /* Allocate one more word, that serves as an indicator for malloc()ed + memory, so that freesa() of an alloca() result is fast. */ + size_t nplus = n + HEADER_SIZE; + + if (nplus >= n) + { + char *p = (char *) malloc (nplus); + + if (p != NULL) + { + size_t slot; + + p += HEADER_SIZE; + + /* Put a magic number into the indicator word. */ + ((int *) p)[-1] = MAGIC_NUMBER; + + /* Enter p into the hash table. */ + slot = (unsigned long) p % HASH_TABLE_SIZE; + ((struct header *) (p - HEADER_SIZE))->next = mallocsa_results[slot]; + mallocsa_results[slot] = p; + + return p; + } + } + /* Out of memory. */ + return NULL; +#else +# if !MALLOC_0_IS_NONNULL + if (n == 0) + n = 1; +# endif + return malloc (n); +#endif +} + +#if HAVE_ALLOCA +void +freesa (void *p) +{ + /* mallocsa() may have returned NULL. */ + if (p != NULL) + { + /* Attempt to quickly distinguish the mallocsa() 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 mallocsa() result. To see whether it really is one, + perform a lookup in the hash table. */ + size_t slot = (unsigned long) p % HASH_TABLE_SIZE; + void **chain = &mallocsa_results[slot]; + for (; *chain != NULL;) + { + if (*chain == p) + { + /* Found it. Remove it from the hash table and free it. */ + char *p_begin = (char *) p - HEADER_SIZE; + *chain = ((struct header *) p_begin)->next; + free (p_begin); + return; + } + chain = &((struct header *) ((char *) *chain - HEADER_SIZE))->next; + } + } + /* At this point, we know it was not a mallocsa() result. */ + } +} +#endif diff --git a/lib/allocsa.h b/lib/allocsa.h new file mode 100644 index 0000000000..9d33bdc623 --- /dev/null +++ b/lib/allocsa.h @@ -0,0 +1,109 @@ +/* Safe automatic memory allocation. + Copyright (C) 2003 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 + the Free Software Foundation; either version 2, 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, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#ifndef _ALLOCSA_H +#define _ALLOCSA_H + +#include +#include +#include + +/* safe_alloca(N) is equivalent to alloca(N) when it is safe to call + alloca(N); otherwise it returns NULL. It either returns N bytes of + memory allocated on the stack, that lasts until the function returns, + or NULL. + Use of safe_alloca should be avoided: + - inside arguments of function calls - undefined behaviour, + - in inline functions - the allocation may actually last until the + calling function returns. +*/ +#if HAVE_ALLOCA +/* The OS usually guarantees only one guard page at the bottom of the stack, + and a page size can be as small as 4096 bytes. So we cannot safely + allocate anything larger than 4096 bytes. Also care for the possibility + of a few compiler-allocated temporary stack slots. + This must be a macro, not an inline function. */ +# define safe_alloca(N) ((N) < 4032 ? alloca (N) : NULL) +#else +# define safe_alloca(N) ((N), NULL) +#endif + +/* allocsa(N) is a safe variant of alloca(N). It allocates N bytes of + memory allocated on the stack, that must be freed using freesa() before + the function returns. Upon failure, it returns NULL. */ +#if HAVE_ALLOCA +# define allocsa(N) \ + ((N) < 4032 - sa_increment \ + ? (void *) ((char *) alloca ((N) + sa_increment) + sa_increment) \ + : mallocsa (N)) +#else +# define allocsa(N) \ + mallocsa (N) +#endif +extern void * mallocsa (size_t n); + +/* Free a block of memory allocated through allocsa(). */ +#if HAVE_ALLOCA +extern void freesa (void *p); +#else +# define freesa free +#endif + +/* Maybe we should also define a variant + nallocsa (size_t n, size_t s) - behaves like allocsa (n * s) + If this would be useful in your application. please speak up. */ + + +/* ------------------- Auxiliary, non-public definitions ------------------- */ + +/* Determine the alignment of a type at compile time. */ +#if defined __GNUC__ +# define sa_alignof __alignof__ +#elif defined __cplusplus + template struct sa_alignof_helper { char __slot1; type __slot2; }; +# define sa_alignof(type) offsetof (sa_alignof_helper, __slot2) +#else +# define sa_alignof(type) offsetof (struct { char __slot1; type __slot2; }, __slot2) +#endif + +enum +{ +/* The desired alignment of memory allocations is the maximum alignment + among all elementary types. */ + sa_alignment_long = sa_alignof (long), + sa_alignment_double = sa_alignof (double), +#ifdef HAVE_LONG_LONG + sa_alignment_longlong = sa_alignof (long long), +#endif +#ifdef HAVE_LONG_DOUBLE + sa_alignment_longdouble = sa_alignof (long double), +#endif + sa_alignment_max = ((sa_alignment_long - 1) | (sa_alignment_double - 1) +#ifdef HAVE_LONG_LONG + | (sa_alignment_longlong - 1) +#endif +#ifdef HAVE_LONG_DOUBLE + | (sa_alignment_longdouble - 1) +#endif + ) + 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 +}; + +#endif /* _ALLOCSA_H */ diff --git a/m4/ChangeLog b/m4/ChangeLog index 17db2cfd3c..e6558389b6 100644 --- a/m4/ChangeLog +++ b/m4/ChangeLog @@ -1,3 +1,7 @@ +2003-11-24 Bruno Haible + + * allocsa.m4: New file, from GNU gettext. + 2003-11-24 Bruno Haible * eealloc.m4: New file, from GNU gettext. diff --git a/m4/allocsa.m4 b/m4/allocsa.m4 new file mode 100644 index 0000000000..a18576fec8 --- /dev/null +++ b/m4/allocsa.m4 @@ -0,0 +1,17 @@ +# allocsa.m4 serial 2 +dnl Copyright (C) 2003-2004 Free Software Foundation, Inc. +dnl This file is free software, distributed under the terms of the GNU +dnl General Public License. As a special exception to the GNU General +dnl Public License, this file may be distributed as part of a program +dnl that contains a configuration script generated by Autoconf, under +dnl the same distribution terms as the rest of that program. + +AC_DEFUN([gl_ALLOCSA], +[ + dnl Use the autoconf tests for alloca(), but not the AC_SUBSTed variables + dnl @ALLOCA@ and @LTALLOCA@. + AC_REQUIRE([gl_FUNC_ALLOCA]) + AC_REQUIRE([gl_EEMALLOC]) + AC_REQUIRE([jm_AC_TYPE_LONG_LONG]) + AC_REQUIRE([gt_TYPE_LONGDOUBLE]) +]) diff --git a/modules/allocsa b/modules/allocsa new file mode 100644 index 0000000000..49670c49bc --- /dev/null +++ b/modules/allocsa @@ -0,0 +1,25 @@ +Description: +Safe automatic memory allocation. + +Files: +lib/allocsa.h +lib/allocsa.c +m4/allocsa.m4 +m4/eealloc.m4 +m4/longlong.m4 +m4/longdouble.m4 + +Depends-on: +alloca + +configure.ac: +gl_ALLOCSA + +Makefile.am: +lib_SOURCES += allocsa.h allocsa.c + +Include: +#include + +Maintainer: +Bruno Haible -- 2.30.2