From 4b830dd16ae281e1f6a7c7b5f2993cc0c3997f57 Mon Sep 17 00:00:00 2001 From: Simon Josefsson Date: Tue, 9 Jun 2009 13:21:23 +0200 Subject: Update gnulib files. --- gl/Makefile.am | 9 +++ gl/m4/getpagesize.m4 | 29 ++++++++ gl/m4/gnulib-comp.m4 | 13 ++++ gl/m4/memchr.m4 | 18 +++++ gl/m4/mmap-anon.m4 | 59 +++++++++++++++++ gl/memchr.c | 172 ++++++++++++++++++++++++++++++++++++++++++++++++ gl/tests/Makefile.am | 17 +++++ gl/tests/getpagesize.c | 39 +++++++++++ gl/tests/test-memchr.c | 130 ++++++++++++++++++++++++++++++++++++ gl/tests/zerosize-ptr.h | 68 +++++++++++++++++++ 10 files changed, 554 insertions(+) create mode 100644 gl/m4/getpagesize.m4 create mode 100644 gl/m4/memchr.m4 create mode 100644 gl/m4/mmap-anon.m4 create mode 100644 gl/memchr.c create mode 100644 gl/tests/getpagesize.c create mode 100644 gl/tests/test-memchr.c create mode 100644 gl/tests/zerosize-ptr.h (limited to 'gl') diff --git a/gl/Makefile.am b/gl/Makefile.am index c6c10ea680..0ec3251f58 100644 --- a/gl/Makefile.am +++ b/gl/Makefile.am @@ -358,6 +358,15 @@ EXTRA_DIST += $(top_srcdir)/maint.mk ## end gnulib module maintainer-makefile +## begin gnulib module memchr + + +EXTRA_DIST += memchr.c + +EXTRA_libgnu_la_SOURCES += memchr.c + +## end gnulib module memchr + ## begin gnulib module minmax libgnu_la_SOURCES += minmax.h diff --git a/gl/m4/getpagesize.m4 b/gl/m4/getpagesize.m4 new file mode 100644 index 0000000000..0d07a3a53b --- /dev/null +++ b/gl/m4/getpagesize.m4 @@ -0,0 +1,29 @@ +# getpagesize.m4 serial 7 +dnl Copyright (C) 2002, 2004-2005, 2007 Free Software Foundation, Inc. +dnl This file is free software; the Free Software Foundation +dnl gives unlimited permission to copy and/or distribute it, +dnl with or without modifications, as long as this notice is preserved. + +AC_DEFUN([gl_FUNC_GETPAGESIZE], +[ + AC_REQUIRE([gl_UNISTD_H_DEFAULTS]) + AC_REQUIRE([AC_CANONICAL_HOST]) + AC_CHECK_FUNCS([getpagesize]) + if test $ac_cv_func_getpagesize = no; then + HAVE_GETPAGESIZE=0 + AC_CHECK_HEADERS([OS.h]) + if test $ac_cv_header_OS_h = yes; then + HAVE_OS_H=1 + fi + AC_CHECK_HEADERS([sys/param.h]) + if test $ac_cv_header_sys_param_h = yes; then + HAVE_SYS_PARAM_H=1 + fi + fi + case "$host_os" in + mingw*) + REPLACE_GETPAGESIZE=1 + AC_LIBOBJ([getpagesize]) + ;; + esac +]) diff --git a/gl/m4/gnulib-comp.m4 b/gl/m4/gnulib-comp.m4 index 91cf94c439..fec57a6ca0 100644 --- a/gl/m4/gnulib-comp.m4 +++ b/gl/m4/gnulib-comp.m4 @@ -113,6 +113,7 @@ AC_SUBST([LTALLOCA]) gl_SYS_SOCKET_MODULE_INDICATOR([listen]) gl_FUNC_LSEEK gl_UNISTD_MODULE_INDICATOR([lseek]) + gl_FUNC_MEMCHR gl_MINMAX gl_MULTIARCH gl_HEADER_NETDB @@ -220,6 +221,8 @@ AC_SUBST([LTALLOCA]) gl_COMMON gl_source_base='gl/tests' gl_FUNC_UNGETC_WORKS + gl_FUNC_GETPAGESIZE + gl_UNISTD_MODULE_INDICATOR([getpagesize]) gl_FUNC_GETTIMEOFDAY AC_REQUIRE([gl_HEADER_SYS_SOCKET]) if test "$ac_cv_header_winsock2_h" = yes; then @@ -228,6 +231,9 @@ AC_SUBST([LTALLOCA]) fi gl_SYS_IOCTL_MODULE_INDICATOR([ioctl]) gl_MODULE_INDICATOR([ioctl]) + gl_FUNC_MMAP_ANON + AC_CHECK_HEADERS_ONCE([sys/mman.h]) + AC_CHECK_FUNCS_ONCE([mprotect]) AC_CHECK_HEADERS_ONCE([unistd.h sys/wait.h]) gt_TYPE_WCHAR_T gt_TYPE_WINT_T @@ -371,6 +377,7 @@ AC_DEFUN([gl_FILE_LIST], [ lib/intprops.h lib/listen.c lib/lseek.c + lib/memchr.c lib/minmax.h lib/netdb.in.h lib/netinet_in.in.h @@ -432,6 +439,7 @@ AC_DEFUN([gl_FILE_LIST], [ m4/getaddrinfo.m4 m4/getdelim.m4 m4/getline.m4 + m4/getpagesize.m4 m4/getpass.m4 m4/gettimeofday.m4 m4/gnulib-common.m4 @@ -448,7 +456,9 @@ AC_DEFUN([gl_FILE_LIST], [ m4/lseek.m4 m4/malloc.m4 m4/manywarnings.m4 + m4/memchr.m4 m4/minmax.m4 + m4/mmap-anon.m4 m4/multiarch.m4 m4/netdb_h.m4 m4/netinet_in_h.m4 @@ -501,6 +511,7 @@ AC_DEFUN([gl_FILE_LIST], [ tests/test-gettimeofday.c tests/test-lseek.c tests/test-lseek.sh + tests/test-memchr.c tests/test-netdb.c tests/test-netinet_in.c tests/test-perror.c @@ -528,7 +539,9 @@ AC_DEFUN([gl_FILE_LIST], [ tests/test-vc-list-files-cvs.sh tests/test-vc-list-files-git.sh tests/test-wchar.c + tests/zerosize-ptr.h tests=lib/dummy.c + tests=lib/getpagesize.c tests=lib/gettimeofday.c tests=lib/ioctl.c tests=lib/sys_ioctl.in.h diff --git a/gl/m4/memchr.m4 b/gl/m4/memchr.m4 new file mode 100644 index 0000000000..53c5380281 --- /dev/null +++ b/gl/m4/memchr.m4 @@ -0,0 +1,18 @@ +# memchr.m4 serial 5 +dnl Copyright (C) 2002, 2003, 2004, 2009 Free Software Foundation, Inc. +dnl This file is free software; the Free Software Foundation +dnl gives unlimited permission to copy and/or distribute it, +dnl with or without modifications, as long as this notice is preserved. + +AC_DEFUN([gl_FUNC_MEMCHR], +[ + AC_REPLACE_FUNCS([memchr]) + if test $ac_cv_func_memchr = no; then + gl_PREREQ_MEMCHR + fi +]) + +# Prerequisites of lib/memchr.c. +AC_DEFUN([gl_PREREQ_MEMCHR], [ + AC_CHECK_HEADERS([bp-sym.h]) +]) diff --git a/gl/m4/mmap-anon.m4 b/gl/m4/mmap-anon.m4 new file mode 100644 index 0000000000..14b6270d28 --- /dev/null +++ b/gl/m4/mmap-anon.m4 @@ -0,0 +1,59 @@ +# mmap-anon.m4 serial 8 +dnl Copyright (C) 2005, 2007, 2009 Free Software Foundation, Inc. +dnl This file is free software; the Free Software Foundation +dnl gives unlimited permission to copy and/or distribute it, +dnl with or without modifications, as long as this notice is preserved. + +# Detect how mmap can be used to create anonymous (not file-backed) memory +# mappings. +# - On Linux, AIX, OSF/1, Solaris, Cygwin, Interix, Haiku, both MAP_ANONYMOUS +# and MAP_ANON exist and have the same value. +# - On HP-UX, only MAP_ANONYMOUS exists. +# - On MacOS X, FreeBSD, NetBSD, OpenBSD, only MAP_ANON exists. +# - On IRIX, neither exists, and a file descriptor opened to /dev/zero must be +# used. + +AC_DEFUN([gl_FUNC_MMAP_ANON], +[ + dnl Work around a bug of AC_EGREP_CPP in autoconf-2.57. + AC_REQUIRE([AC_PROG_CPP]) + AC_REQUIRE([AC_PROG_EGREP]) + + dnl Persuade glibc to define MAP_ANONYMOUS. + AC_REQUIRE([gl_USE_SYSTEM_EXTENSIONS]) + + # Check for mmap(). Don't use AC_FUNC_MMAP, because it checks too much: it + # fails on HP-UX 11, because MAP_FIXED mappings do not work. But this is + # irrelevant for anonymous mappings. + AC_CHECK_FUNC([mmap], [gl_have_mmap=yes], [gl_have_mmap=no]) + + # Try to allow MAP_ANONYMOUS. + gl_have_mmap_anonymous=no + if test $gl_have_mmap = yes; then + AC_MSG_CHECKING([for MAP_ANONYMOUS]) + AC_EGREP_CPP([I cant identify this map.], [ +#include +#ifdef MAP_ANONYMOUS + I cant identify this map. +#endif +], + [gl_have_mmap_anonymous=yes]) + if test $gl_have_mmap_anonymous != yes; then + AC_EGREP_CPP([I cant identify this map.], [ +#include +#ifdef MAP_ANON + I cant identify this map. +#endif +], + [AC_DEFINE([MAP_ANONYMOUS], [MAP_ANON], + [Define to a substitute value for mmap()'s MAP_ANONYMOUS flag.]) + gl_have_mmap_anonymous=yes]) + fi + AC_MSG_RESULT([$gl_have_mmap_anonymous]) + if test $gl_have_mmap_anonymous = yes; then + AC_DEFINE([HAVE_MAP_ANONYMOUS], [1], + [Define to 1 if mmap()'s MAP_ANONYMOUS flag is available after including + config.h and .]) + fi + fi +]) diff --git a/gl/memchr.c b/gl/memchr.c new file mode 100644 index 0000000000..2253d2d651 --- /dev/null +++ b/gl/memchr.c @@ -0,0 +1,172 @@ +/* Copyright (C) 1991, 1993, 1996, 1997, 1999, 2000, 2003, 2004, 2006, 2008 + Free Software Foundation, Inc. + + Based on strlen implementation by Torbjorn Granlund (tege@sics.se), + with help from Dan Sahlin (dan@sics.se) and + commentary by Jim Blandy (jimb@ai.mit.edu); + adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu), + and implemented by Roland McGrath (roland@ai.mit.edu). + +NOTE: The canonical source of this file is maintained with the GNU C Library. +Bugs can be reported to bug-glibc@prep.ai.mit.edu. + +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 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 . */ + +#ifndef _LIBC +# include +#endif + +#include + +#include + +#if defined _LIBC +# include +#else +# define reg_char char +#endif + +#include + +#if HAVE_BP_SYM_H || defined _LIBC +# include +#else +# define BP_SYM(sym) sym +#endif + +#undef __memchr +#ifdef _LIBC +# undef memchr +#endif + +#ifndef weak_alias +# define __memchr memchr +#endif + +/* Search no more than N bytes of S for C. */ +void * +__memchr (void const *s, int c_in, size_t n) +{ + /* On 32-bit hardware, choosing longword to be a 32-bit unsigned + long instead of a 64-bit uintmax_t tends to give better + performance. On 64-bit hardware, unsigned long is generally 64 + bits already. Change this typedef to experiment with + performance. */ + typedef unsigned long int longword; + + const unsigned char *char_ptr; + const longword *longword_ptr; + longword repeated_one; + longword repeated_c; + unsigned reg_char c; + + c = (unsigned char) c_in; + + /* Handle the first few bytes by reading one byte at a time. + Do this until CHAR_PTR is aligned on a longword boundary. */ + for (char_ptr = (const unsigned char *) s; + n > 0 && (size_t) char_ptr % sizeof (longword) != 0; + --n, ++char_ptr) + if (*char_ptr == c) + return (void *) char_ptr; + + longword_ptr = (const longword *) char_ptr; + + /* All these elucidatory comments refer to 4-byte longwords, + but the theory applies equally well to any size longwords. */ + + /* Compute auxiliary longword values: + repeated_one is a value which has a 1 in every byte. + repeated_c has c in every byte. */ + repeated_one = 0x01010101; + repeated_c = c | (c << 8); + repeated_c |= repeated_c << 16; + if (0xffffffffU < (longword) -1) + { + repeated_one |= repeated_one << 31 << 1; + repeated_c |= repeated_c << 31 << 1; + if (8 < sizeof (longword)) + { + size_t i; + + for (i = 64; i < sizeof (longword) * 8; i *= 2) + { + repeated_one |= repeated_one << i; + repeated_c |= repeated_c << i; + } + } + } + + /* Instead of the traditional loop which tests each byte, we will test a + longword at a time. The tricky part is testing if *any of the four* + bytes in the longword in question are equal to c. We first use an xor + with repeated_c. This reduces the task to testing whether *any of the + four* bytes in longword1 is zero. + + We compute tmp = + ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). + That is, we perform the following operations: + 1. Subtract repeated_one. + 2. & ~longword1. + 3. & a mask consisting of 0x80 in every byte. + Consider what happens in each byte: + - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, + and step 3 transforms it into 0x80. A carry can also be propagated + to more significant bytes. + - If a byte of longword1 is nonzero, let its lowest 1 bit be at + position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, + the byte ends in a single bit of value 0 and k bits of value 1. + After step 2, the result is just k bits of value 1: 2^k - 1. After + step 3, the result is 0. And no carry is produced. + So, if longword1 has only non-zero bytes, tmp is zero. + Whereas if longword1 has a zero byte, call j the position of the least + significant zero byte. Then the result has a zero at positions 0, ..., + j-1 and a 0x80 at position j. We cannot predict the result at the more + significant bytes (positions j+1..3), but it does not matter since we + already have a non-zero bit at position 8*j+7. + + So, the test whether any byte in longword1 is zero is equivalent to + testing whether tmp is nonzero. */ + + while (n >= sizeof (longword)) + { + longword longword1 = *longword_ptr ^ repeated_c; + + if ((((longword1 - repeated_one) & ~longword1) + & (repeated_one << 7)) != 0) + break; + longword_ptr++; + n -= sizeof (longword); + } + + char_ptr = (const unsigned char *) longword_ptr; + + /* At this point, we know that either n < sizeof (longword), or one of the + sizeof (longword) bytes starting at char_ptr is == c. On little-endian + machines, we could determine the first such byte without any further + memory accesses, just by looking at the tmp result from the last loop + iteration. But this does not work on big-endian machines. Choose code + that works in both cases. */ + + for (; n > 0; --n, ++char_ptr) + { + if (*char_ptr == c) + return (void *) char_ptr; + } + + return NULL; +} +#ifdef weak_alias +weak_alias (__memchr, BP_SYM (memchr)) +#endif diff --git a/gl/tests/Makefile.am b/gl/tests/Makefile.am index a37a580ca7..698e89bd3d 100644 --- a/gl/tests/Makefile.am +++ b/gl/tests/Makefile.am @@ -124,6 +124,15 @@ EXTRA_DIST += test-getline.c ## end gnulib module getline-tests +## begin gnulib module getpagesize + + +EXTRA_DIST += getpagesize.c + +EXTRA_libtests_a_SOURCES += getpagesize.c + +## end gnulib module getpagesize + ## begin gnulib module gettimeofday @@ -160,6 +169,14 @@ EXTRA_DIST += test-lseek.c test-lseek.sh ## end gnulib module lseek-tests +## begin gnulib module memchr-tests + +TESTS += test-memchr +check_PROGRAMS += test-memchr +EXTRA_DIST += test-memchr.c zerosize-ptr.h + +## end gnulib module memchr-tests + ## begin gnulib module netdb-tests TESTS += test-netdb diff --git a/gl/tests/getpagesize.c b/gl/tests/getpagesize.c new file mode 100644 index 0000000000..5498aa9483 --- /dev/null +++ b/gl/tests/getpagesize.c @@ -0,0 +1,39 @@ +/* getpagesize emulation for systems where it cannot be done in a C macro. + + Copyright (C) 2007 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 . */ + +/* Written by Bruno Haible and Martin Lambers. */ + +#include + +/* Specification. */ +#include + +/* This implementation is only for native Win32 systems. */ +#if (defined _WIN32 || defined __WIN32__) && ! defined __CYGWIN__ + +# define WIN32_LEAN_AND_MEAN +# include + +int +getpagesize (void) +{ + SYSTEM_INFO system_info; + GetSystemInfo (&system_info); + return system_info.dwPageSize; +} + +#endif diff --git a/gl/tests/test-memchr.c b/gl/tests/test-memchr.c new file mode 100644 index 0000000000..1124f8b587 --- /dev/null +++ b/gl/tests/test-memchr.c @@ -0,0 +1,130 @@ +/* + * Copyright (C) 2008-2009 Free Software Foundation + * Written by Eric Blake and Bruno Haible + * + * 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 . */ + +#include + +#include + +#include +#include + +#include "zerosize-ptr.h" + +#define ASSERT(expr) \ + do \ + { \ + if (!(expr)) \ + { \ + fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \ + fflush (stderr); \ + abort (); \ + } \ + } \ + while (0) + +/* Calculating void * + int is not portable, so this wrapper converts + to char * to make the tests easier to write. */ +#define MEMCHR (char *) memchr + +int +main () +{ + size_t n = 0x100000; + char *input = malloc (n); + ASSERT (input); + + input[0] = 'a'; + input[1] = 'b'; + memset (input + 2, 'c', 1024); + memset (input + 1026, 'd', n - 1028); + input[n - 2] = 'e'; + input[n - 1] = 'a'; + + /* Basic behavior tests. */ + ASSERT (MEMCHR (input, 'a', n) == input); + + ASSERT (MEMCHR (input, 'a', 0) == NULL); + ASSERT (MEMCHR (zerosize_ptr (), 'a', 0) == NULL); + + ASSERT (MEMCHR (input, 'b', n) == input + 1); + ASSERT (MEMCHR (input, 'c', n) == input + 2); + ASSERT (MEMCHR (input, 'd', n) == input + 1026); + + ASSERT (MEMCHR (input + 1, 'a', n - 1) == input + n - 1); + ASSERT (MEMCHR (input + 1, 'e', n - 1) == input + n - 2); + + ASSERT (MEMCHR (input, 'f', n) == NULL); + ASSERT (MEMCHR (input, '\0', n) == NULL); + + /* Check that a very long haystack is handled quickly if the byte is + found near the beginning. */ + { + size_t repeat = 10000; + for (; repeat > 0; repeat--) + { + ASSERT (MEMCHR (input, 'c', n) == input + 2); + } + } + + /* Alignment tests. */ + { + int i, j; + for (i = 0; i < 32; i++) + { + for (j = 0; j < 256; j++) + input[i + j] = j; + for (j = 0; j < 256; j++) + { + ASSERT (MEMCHR (input + i, j, 256) == input + i + j); + } + } + } + + /* Check that memchr() does not read past the first occurrence of the + byte being searched. See the Austin Group's clarification + . */ + { + char *page_boundary = (char *) zerosize_ptr (); + + if (page_boundary != NULL) + { + int n; + + for (n = 1; n <= 500; n++) + { + char *mem = page_boundary - n; + memset (mem, 'X', n); + ASSERT (MEMCHR (mem, 'U', n) == NULL); + + { + int i; + + for (i = 0; i < n; i++) + { + mem[i] = 'U'; + ASSERT (MEMCHR (mem, 'U', 4000) == mem + i); + mem[i] = 'X'; + } + } + } + } + } + + free (input); + + return 0; +} diff --git a/gl/tests/zerosize-ptr.h b/gl/tests/zerosize-ptr.h new file mode 100644 index 0000000000..a38a2cf494 --- /dev/null +++ b/gl/tests/zerosize-ptr.h @@ -0,0 +1,68 @@ +/* Return a pointer to a zero-size object in memory. + Copyright (C) 2009 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 . */ + +/* ISO C 99 does not allow memcmp(), memchr() etc. to be invoked with a NULL + argument. Therefore this file produces a non-NULL pointer which cannot + be dereferenced, if possible. */ + +#include + +/* Test whether mmap() and mprotect() are available. + We don't use HAVE_MMAP, because AC_FUNC_MMAP would not define it on HP-UX. + HAVE_MPROTECT is not enough, because mingw does not have mmap() but has an + mprotect() function in libgcc.a. */ +#if HAVE_SYS_MMAN_H && HAVE_MPROTECT +# include +# include +# include +# include +/* Define MAP_FILE when it isn't otherwise. */ +# ifndef MAP_FILE +# define MAP_FILE 0 +# endif +#endif + +/* Return a pointer to a zero-size object in memory (that is, actually, a + pointer to a page boundary where the previous page is readable and writable + and the next page is neither readable not writable), if possible. + Return NULL otherwise. */ + +static void * +zerosize_ptr (void) +{ +/* Use mmap and mprotect when they exist. Don't test HAVE_MMAP, because it is + not defined on HP-UX 11 (since it does not support MAP_FIXED). */ +#if HAVE_SYS_MMAN_H && HAVE_MPROTECT +# if HAVE_MAP_ANONYMOUS + const int flags = MAP_ANONYMOUS | MAP_PRIVATE; + const int fd = -1; +# else /* !HAVE_MAP_ANONYMOUS */ + const int flags = MAP_FILE | MAP_PRIVATE; + int fd = open ("/dev/zero", O_RDONLY, 0666); + if (fd >= 0) +# endif + { + int pagesize = getpagesize (); + char *two_pages = + (char *) mmap (NULL, 2 * pagesize, PROT_READ | PROT_WRITE, + flags, fd, 0); + if (two_pages != (char *)(-1) + && mprotect (two_pages + pagesize, pagesize, PROT_NONE) == 0) + return two_pages + pagesize; + } +#endif + return NULL; +} -- cgit v1.2.1