diff options
Diffstat (limited to 'lib/libc/stdlib')
39 files changed, 2307 insertions, 538 deletions
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index 5298202..81e8ed0 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -4,18 +4,22 @@ .PATH: ${.CURDIR}/${MACHINE}/stdlib ${.CURDIR}/stdlib SRCS+= abort.c atexit.c atof.c atoi.c atol.c bsearch.c calloc.c div.c \ - exit.c getenv.c getopt.c getsubopt.c heapsort.c labs.c ldiv.c \ - malloc.c merge.c putenv.c qsort.c radixsort.c rand.c random.c \ + exit.c getenv.c getopt.c getsubopt.c strhash.c heapsort.c labs.c \ + ldiv.c malloc.c merge.c putenv.c qsort.c radixsort.c rand.c random.c \ realpath.c setenv.c strtod.c strtol.c strtoq.c strtoul.c \ strtouq.c system.c # machine-dependent stdlib sources .include "${.CURDIR}/${MACHINE}/stdlib/Makefile.inc" -MAN3+= abort.0 abs.0 alloca.0 atexit.0 atof.0 atoi.0 atol.0 bsearch.0 \ - calloc.0 div.0 exit.0 free.0 getenv.0 getopt.0 getsubopt.0 labs.0 \ - ldiv.0 malloc.0 memory.0 qsort.0 radixsort.0 rand.0 random.0 \ - realloc.0 realpath.0 strtod.0 strtol.0 strtoul.0 system.0 +MAN3+= stdlib/abort.3 stdlib/abs.3 stdlib/alloca.3 stdlib/atexit.3 \ + stdlib/atof.3 stdlib/atoi.3 stdlib/atol.3 stdlib/bsearch.3 \ + stdlib/calloc.3 stdlib/div.3 stdlib/exit.3 \ + stdlib/getenv.3 stdlib/getopt.3 stdlib/getsubopt.3 stdlib/labs.3 \ + stdlib/ldiv.3 stdlib/malloc.3 stdlib/memory.3 stdlib/qsort.3 \ + stdlib/radixsort.3 stdlib/rand.3 stdlib/random.3 \ + stdlib/realpath.3 stdlib/strtod.3 stdlib/strtol.3 stdlib/strtoul.3 \ + stdlib/system.3 MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 @@ -23,3 +27,4 @@ MLINKS+=rand.3 srand.3 MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 MLINKS+=strtol.3 strtoq.3 MLINKS+=strtoul.3 strtouq.3 +MLINKS+=malloc.3 free.3 malloc.3 realloc.3 diff --git a/lib/libc/stdlib/abort.3 b/lib/libc/stdlib/abort.3 index 83b4e04..17717e9 100644 --- a/lib/libc/stdlib/abort.3 +++ b/lib/libc/stdlib/abort.3 @@ -53,18 +53,18 @@ signal .Dv SIGABRT is being caught and the signal handler does not return. .Pp -No open streams are closed or flushed. +Any open streams are flushed and closed. .Sh RETURN VALUES The -.Nm abort +.Fn abort function never returns. .Sh SEE ALSO .Xr sigaction 2 , -.Xr exit 2 +.Xr exit 3 .Sh STANDARDS The .Fn abort function conforms to -.St -ansiC . +.St -p1003.1-90 . diff --git a/lib/libc/stdlib/abort.c b/lib/libc/stdlib/abort.c index e56e7e9..4fd34dc 100644 --- a/lib/libc/stdlib/abort.c +++ b/lib/libc/stdlib/abort.c @@ -35,31 +35,52 @@ static char sccsid[] = "@(#)abort.c 8.1 (Berkeley) 6/4/93"; #endif /* LIBC_SCCS and not lint */ -#include <sys/signal.h> +#include <signal.h> #include <stdlib.h> #include <stddef.h> #include <unistd.h> +#ifdef _THREAD_SAFE +#include <pthread.h> +#include "pthread_private.h" +#endif + +void (*__cleanup)(); void abort() { sigset_t mask; + /* + * POSIX requires we flush stdio buffers on abort + */ + if (__cleanup) + (*__cleanup)(); + sigfillset(&mask); /* * don't block SIGABRT to give any handler a chance; we ignore * any errors -- X311J doesn't allow abort to return anyway. */ sigdelset(&mask, SIGABRT); +#ifdef _THREAD_SAFE + (void) _thread_sys_sigprocmask(SIG_SETMASK, &mask, (sigset_t *)NULL); +#else (void)sigprocmask(SIG_SETMASK, &mask, (sigset_t *)NULL); +#endif (void)kill(getpid(), SIGABRT); /* * if SIGABRT ignored, or caught and the handler returns, do * it again, only harder. */ +#ifdef _THREAD_SAFE + (void) _thread_sys_signal(SIGABRT, SIG_DFL); + (void) _thread_sys_sigprocmask(SIG_SETMASK, &mask, (sigset_t *)NULL); +#else (void)signal(SIGABRT, SIG_DFL); (void)sigprocmask(SIG_SETMASK, &mask, (sigset_t *)NULL); +#endif (void)kill(getpid(), SIGABRT); exit(1); } diff --git a/lib/libc/stdlib/abs.3 b/lib/libc/stdlib/abs.3 index e12f798..501263e 100644 --- a/lib/libc/stdlib/abs.3 +++ b/lib/libc/stdlib/abs.3 @@ -34,6 +34,7 @@ .\" SUCH DAMAGE. .\" .\" @(#)abs.3 8.1 (Berkeley) 6/4/93 +.\" $Id$ .\" .Dd June 4, 1993 .Dt ABS 3 @@ -59,10 +60,10 @@ function returns the absolute value. .Sh SEE ALSO +.Xr cabs 3 , .Xr floor 3 , -.Xr labs 3 -.Xr cabs 3 -.Xr hypot 3 +.Xr hypot 3 , +.Xr labs 3 , .Xr math 3 .Sh STANDARDS The diff --git a/lib/libc/stdlib/alloca.3 b/lib/libc/stdlib/alloca.3 index ad5aaf69..498348c 100644 --- a/lib/libc/stdlib/alloca.3 +++ b/lib/libc/stdlib/alloca.3 @@ -59,10 +59,10 @@ If the allocation failed, a pointer is returned. .Sh SEE ALSO .Xr brk 2 , -.Xr pagesize 2 .Xr calloc 3 , +.Xr getpagesize 3 , .Xr malloc 3 , -.Xr realloc 3 , +.Xr realloc 3 .Sh BUGS The .Fn alloca diff --git a/lib/libc/stdlib/atexit.c b/lib/libc/stdlib/atexit.c index 9c4caed..ea2a7e2 100644 --- a/lib/libc/stdlib/atexit.c +++ b/lib/libc/stdlib/atexit.c @@ -40,6 +40,7 @@ static char sccsid[] = "@(#)atexit.c 8.1 (Berkeley) 6/4/93"; #include <stddef.h> #include <stdlib.h> +#include <unistd.h> #include "atexit.h" /* @@ -55,7 +56,7 @@ atexit(fn) if ((p = __atexit) == NULL) __atexit = p = &__atexit0; else if (p->ind >= ATEXIT_SIZE) { - if ((p = malloc(sizeof(*p))) == NULL) + if ((p = (struct atexit *)sbrk(sizeof(*p))) == (struct atexit *)-1) return (-1); p->ind = 0; p->next = __atexit; diff --git a/lib/libc/stdlib/atoi.c b/lib/libc/stdlib/atoi.c index a13c0e2..48e508a 100644 --- a/lib/libc/stdlib/atoi.c +++ b/lib/libc/stdlib/atoi.c @@ -38,6 +38,7 @@ static char sccsid[] = "@(#)atoi.c 8.1 (Berkeley) 6/4/93"; #include <stdlib.h> #include <stddef.h> +int atoi(str) const char *str; { diff --git a/lib/libc/stdlib/bsearch.3 b/lib/libc/stdlib/bsearch.3 index e4cf49f..a4e076e 100644 --- a/lib/libc/stdlib/bsearch.3 +++ b/lib/libc/stdlib/bsearch.3 @@ -81,7 +81,7 @@ If two members compare as equal, which member is matched is unspecified. .Sh SEE ALSO .Xr db 3 , .Xr lsearch 3 , -.Xr qsort 3 , +.Xr qsort 3 .\" .Xr tsearch 3 .Sh STANDARDS The diff --git a/lib/libc/stdlib/calloc.3 b/lib/libc/stdlib/calloc.3 index 0ca15e5..6c79272 100644 --- a/lib/libc/stdlib/calloc.3 +++ b/lib/libc/stdlib/calloc.3 @@ -34,6 +34,7 @@ .\" SUCH DAMAGE. .\" .\" @(#)calloc.3 8.1 (Berkeley) 6/4/93 +.\" $Id$ .\" .Dd June 4, 1993 .Dt CALLOC 3 @@ -60,9 +61,9 @@ function returns a pointer to the the allocated space if successful; otherwise a null pointer is returned. .Sh SEE ALSO -.Xr malloc 3 , -.Xr realloc 3 , .Xr free 3 , +.Xr malloc 3 , +.Xr realloc 3 .Sh STANDARDS The .Fn calloc diff --git a/lib/libc/stdlib/calloc.c b/lib/libc/stdlib/calloc.c index d7c8e07..7a83603 100644 --- a/lib/libc/stdlib/calloc.c +++ b/lib/libc/stdlib/calloc.c @@ -46,7 +46,7 @@ calloc(num, size) register void *p; size *= num; - if (p = malloc(size)) + if ( (p = malloc(size)) ) bzero(p, size); return(p); } diff --git a/lib/libc/stdlib/exit.3 b/lib/libc/stdlib/exit.3 index 43ee3c0..de91276 100644 --- a/lib/libc/stdlib/exit.3 +++ b/lib/libc/stdlib/exit.3 @@ -65,6 +65,11 @@ Unlink all files created with the .Xr tmpfile 3 function. .El +.Pp +Passing arbitrary values back to the environment as +.Ar status +is considered bad style. Instead, use the values as described in +.Xr sysexits 3 . .Sh RETURN VALUES The .Fn exit @@ -74,6 +79,7 @@ never returns. .Xr _exit 2 , .Xr atexit 3 , .Xr intro 3 , +.Xr sysexits 3 , .Xr tmpfile 3 .Sh STANDARDS The diff --git a/lib/libc/stdlib/getenv.c b/lib/libc/stdlib/getenv.c index 7407e0b..a6bbd35 100644 --- a/lib/libc/stdlib/getenv.c +++ b/lib/libc/stdlib/getenv.c @@ -39,20 +39,7 @@ static char sccsid[] = "@(#)getenv.c 8.1 (Berkeley) 6/4/93"; #include <stddef.h> #include <string.h> -char *__findenv __P((const char *, int *)); - -/* - * getenv -- - * Returns ptr to value associated with name, if any, else NULL. - */ -char * -getenv(name) - const char *name; -{ - int offset; - - return (__findenv(name, &offset)); -} +inline char *__findenv __P((const char *, int *)); /* * __findenv -- @@ -63,25 +50,42 @@ getenv(name) * * This routine *should* be a static; don't use it. */ -char * +inline char * __findenv(name, offset) register const char *name; int *offset; { extern char **environ; - register int len; + register int len, i; register const char *np; - register char **p, *c; + register char **p, *cp; if (name == NULL || environ == NULL) return (NULL); for (np = name; *np && *np != '='; ++np) continue; len = np - name; - for (p = environ; (c = *p) != NULL; ++p) - if (strncmp(c, name, len) == 0 && c[len] == '=') { + for (p = environ; (cp = *p) != NULL; ++p) { + for (np = name, i = len; i && *cp; i--) + if (*cp++ != *np++) + break; + if (i == 0 && *cp++ == '=') { *offset = p - environ; - return (c + len + 1); + return (cp); } + } return (NULL); } + +/* + * getenv -- + * Returns ptr to value associated with name, if any, else NULL. + */ +char * +getenv(name) + const char *name; +{ + int offset; + + return (__findenv(name, &offset)); +} diff --git a/lib/libc/stdlib/getopt.3 b/lib/libc/stdlib/getopt.3 index 95ff6e6..3047183 100644 --- a/lib/libc/stdlib/getopt.3 +++ b/lib/libc/stdlib/getopt.3 @@ -122,9 +122,11 @@ The function returns an .Dv EOF -when the argument list is exhausted, or a non-recognized +when the argument list is exhausted, or +.Ql ? +if a non-recognized option is encountered. -The interpretation of options in the argument list may be cancelled +The interpretation of options in the argument list may be canceled by the option .Ql -- (double dash) which causes @@ -142,10 +144,10 @@ If the function encounters a character not found in the string .Va optarg or detects -a missing option argument it writes an error message and returns -.Ql ? -to the -.Em stderr . +a missing option argument it writes an error message to the +.Em stderr +and returns +.Ql ? . Setting .Va opterr to a zero will disable these error messages. diff --git a/lib/libc/stdlib/getsubopt.3 b/lib/libc/stdlib/getsubopt.3 index e1040d7..3f6f547 100644 --- a/lib/libc/stdlib/getsubopt.3 +++ b/lib/libc/stdlib/getsubopt.3 @@ -142,4 +142,5 @@ while ((ch = getopt(argc, argv, "ab:")) != \-1) { .Sh HISTORY The .Fn getsubopt -function first appeared in 4.4BSD. +function first appeared in +.Bx 4.4 . diff --git a/lib/libc/stdlib/getsubopt.c b/lib/libc/stdlib/getsubopt.c index d0ebde2..bc055b8 100644 --- a/lib/libc/stdlib/getsubopt.c +++ b/lib/libc/stdlib/getsubopt.c @@ -46,6 +46,7 @@ static char sccsid[] = "@(#)getsubopt.c 8.1 (Berkeley) 6/4/93"; */ char *suboptarg; +int getsubopt(optionp, tokens, valuep) register char **optionp, **valuep; register char * const *tokens; @@ -80,7 +81,7 @@ getsubopt(optionp, tokens, valuep) *p = '\0'; for (*valuep = ++p; *p && *p != ',' && *p != ' ' && *p != '\t'; ++p); - if (*p) + if (*p) *p++ = '\0'; } else *p++ = '\0'; diff --git a/lib/libc/stdlib/heapsort.c b/lib/libc/stdlib/heapsort.c index d800064..9649553 100644 --- a/lib/libc/stdlib/heapsort.c +++ b/lib/libc/stdlib/heapsort.c @@ -38,10 +38,9 @@ static char sccsid[] = "@(#)heapsort.c 8.1 (Berkeley) 6/4/93"; #endif /* LIBC_SCCS and not lint */ -#include <sys/types.h> #include <errno.h> -#include <stdlib.h> #include <stddef.h> +#include <stdlib.h> /* * Swap two areas of size number of bytes. Although qsort(3) permits random diff --git a/lib/libc/stdlib/labs.3 b/lib/libc/stdlib/labs.3 index ef9ba80..2dba8cc 100644 --- a/lib/libc/stdlib/labs.3 +++ b/lib/libc/stdlib/labs.3 @@ -53,8 +53,8 @@ returns the absolute value of the long integer .Ar j . .Sh SEE ALSO .Xr abs 3 , -.Xr floor 3 , .Xr cabs 3 , +.Xr floor 3 , .Xr math 3 .Sh STANDARDS The diff --git a/lib/libc/stdlib/ldiv.3 b/lib/libc/stdlib/ldiv.3 index a68952f..2b61499 100644 --- a/lib/libc/stdlib/ldiv.3 +++ b/lib/libc/stdlib/ldiv.3 @@ -44,7 +44,7 @@ .Sh SYNOPSIS .Fd #include <stdlib.h> .Ft ldiv_t -.Fn ldiv "int num" "int denom" +.Fn ldiv "long num" "long denom" .Sh DESCRIPTION The .Fn ldiv diff --git a/lib/libc/stdlib/malloc.3 b/lib/libc/stdlib/malloc.3 index 98ebadc..cd10039 100644 --- a/lib/libc/stdlib/malloc.3 +++ b/lib/libc/stdlib/malloc.3 @@ -34,17 +34,30 @@ .\" SUCH DAMAGE. .\" .\" @(#)malloc.3 8.1 (Berkeley) 6/4/93 +.\" $Id$ .\" -.Dd June 4, 1993 +.Dd August 27, 1996 .Dt MALLOC 3 -.Os BSD 4 +.Os FreeBSD 2 .Sh NAME .Nm malloc , .Nd general memory allocation function +.Pp +.Nm free +.Nd free up memory allocated with malloc, calloc or realloc +.Pp +.Nm realloc +.Nd reallocation of memory function .Sh SYNOPSIS .Fd #include <stdlib.h> .Ft void * .Fn malloc "size_t size" +.Ft void +.Fn free "void *ptr" +.Ft void * +.Fn realloc "void *ptr" "size_t size" +.Ft char * +.Va malloc_options .Sh DESCRIPTION The .Fn malloc @@ -61,30 +74,221 @@ suitably aligned (after possible pointer coercion) for storage of any type of object. If the space is of .Em pagesize or larger, the memory returned will be page-aligned. +.Pp +The +.Fn free +function causes the space pointed to by +.Fa ptr +to be deallocated, that is, at least made available for further allocation, +but if possible, it will passed back to the kernel with +.Xr sbrk 2 . +If +.Fa ptr +is a null pointer, no action occurs. +.Pp +The +.Fn realloc +function changes the size of the object pointed to by +.Fa ptr +to the size specified by +.Fa size . +The contents of the object are unchanged up to the lesser +of the new and old sizes. +If the new size is larger, the value of the newly allocated portion +of the object is indeterminate. +If +.Fa ptr +is a null pointer, the +.Fn realloc +function behaves like the +.Fn malloc +function for the specified size. +If the space cannot be allocated, the object +pointed to by +.Fa ptr +is unchanged. +If +.Fa size +is zero and +.Fa ptr +is not a null pointer, the object it points to is freed. +.Pp +Malloc will first look for a symbolic link called +.Pa /etc/malloc.conf +and next check the environment for a variable called +.Ev MALLOC_OPTIONS +and finally for the global variable +.Va malloc_options +and scan them for flags in that order. +Flags are single letters, uppercase means on, lowercase means off. +.Bl -tag -width indent +.It A +``abort'' malloc will coredump the process, rather than tolerate failure. +This is a very handy debugging aid, since the core file will represent the +time of failure, +rather than when the NULL pointer was accessed. + +.It D +``dump'' malloc will dump statistics in a file called ``malloc.out'' at exit. + +.It J +``junk'' fill some junk into the area allocated. +Currently junk is bytes of 0xd0, this is pronounced ``Duh'' :-) + +.It H +``hint'' pass a hint to the kernel about pages we don't use. If the +machine is paging a lot this may help a bit. + +.It R +``realloc'' always reallocate when +.Fn realloc +is called, even if the initial allocation was big enough. +This can substantially aid in compacting memory. + +.It U +``utrace'' generate entries for ktrace(1) for all operations. +Consult the source for this one. + +.It Z +``zero'' fill some junk into the area allocated (see ``J''), +except for the exact length the user asked for, which is zeroed. + +.It < +``Half the cache size'' Reduce the size of the cache by a factor of two. + +.It > +``Double the cache size'' Double the size of the cache by a factor of two. +.El +.Pp +So to set a systemwide reduction of cache size and coredumps on problems +one would: +.Li ln -s 'A<' /etc/malloc.conf +.Pp +The ``J'' and ``Z'' is mostly for testing and debugging, +if a program changes behavior if either of these options are used, +it is buggy. +.Pp +The default cache size is 16 pages. +.Sh ENVIRONMENT +See above. .Sh RETURN VALUES The .Fn malloc function returns a pointer to the allocated space if successful; otherwise a null pointer is returned. +.Pp +The +.Fn free +function returns no value. +.Pp +The +.Fn realloc +function returns either a null pointer or a pointer +to the possibly moved allocated space. +.Sh MESSAGES +If +.Fn malloc , +.Fn free +or +.Fn realloc +detects an error or warning condition, +a message will be printed to filedescriptor +2 (not using stdio). +Errors will always result in the process being +.Xr abort 2 'ed, +If the ``A'' option has been specified, also warnings will +.Xr abort 2 +the process. +.Pp +Here is a brief description of the error messages and what they mean: +.Pp +``(ES): mumble mumble mumble'': +malloc have been compiled with -DEXTRA_SANITY and something looks +fishy in there. Consult sources and or wizards. +.Pp +``allocation failed'' +if the ``A'' option is specified it is an error for +.Fn malloc +or +.Fn realloc +to return NULL. +.Pp +``mmap(2) failed, check limits.'' +This is a rather weird condition that is most likely to mean that +the system is seriously overloaded or that your ulimits are sick. +.Pp +``freelist is destroyed.'' +mallocs internal freelist has been stomped on. +.Pp +Here is a brief description of the warning messages and what they mean: +.Pp +``chunk/page is already free.'' +A pointer to a free chunk is attempted freed again. +.Pp +``junk pointer, too high to make sense.'' +The pointer doesn't make sense. It's above the area of memory that +malloc knows something about. +This could be a pointer from some +.Xr mmap 2 'ed +memory. +.Pp +``junk pointer, too low to make sense.'' +The pointer doesn't make sense. It's below the area of memory that +malloc knows something about. +This pointer probably came from your data or bss segments. +.Pp +``malloc() has never been called.'' +Nothing has ever been allocated, yet something is being freed or +realloc'ed. +.Pp +``modified (chunk-/page-) pointer.'' +The pointer passed to free or realloc has been modified. +.Pp +``pointer to wrong page.'' +The pointer that malloc is trying to free is not pointing to +a sensible page. +.Pp +``recursive call.'' +You have tried to call recursively into these functions. +I can only imagine this as happening if you call one of these +functions from a signal function, which happens to be called +while you're already in here. +Well, sorry to say: that's not supported. +If this is a problem for you I'd like to hear about it. It +would be possible to add a sigblock() around this package, +but it would have a performance penalty that is not acceptable +as the default. +.Pp +``unknown char in MALLOC_OPTIONS'' +we found something we didn't understand. .Sh SEE ALSO .Xr brk 2 , -.Xr pagesize 2 , -.Xr free 3 , -.Xr calloc 3 , .Xr alloca 3 , -.Xr realloc 3 , +.Xr calloc 3 , +.Xr getpagesize 3 , .Xr memory 3 +.Pa /usr/share/doc/papers/malloc.ascii.gz .Sh STANDARDS The .Fn malloc function conforms to .St -ansiC . -.Sh BUGS -The current implementation of -.Xr malloc -does not always fail gracefully when system -memory limits are approached. -It may fail to allocate memory when larger free blocks could be broken -up, or when limits are exceeded because the size is rounded up. -It is optimized for sizes that are powers of two. +.Sh HISTORY +The present implementation of malloc started out as a filesystem on a drum +attached to a 20bit binary challenged computer built with discrete germanium +transistors, and it has since graduated to handle primary storage rather than +secondary. +.Pp +The main difference from other malloc implementations are believed to be that +the free pages are not accessed until allocated. +Most malloc implementations will store a data structure containing a, +possibly double-, linked list in the free chunks of memory, used to tie +all the free memory together. +That is a quite suboptimal thing to do. +Every time the free-list is traversed, all the otherwise unused, and very +likely paged out, pages get faulted into primary memory, just to see what +lies after them in the list. +.Pp +On systems which are paging, this can make a factor five in difference on the +page-faults of a process. diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c index ea8f092..6462ad1 100644 --- a/lib/libc/stdlib/malloc.c +++ b/lib/libc/stdlib/malloc.c @@ -1,420 +1,1156 @@ /* - * Copyright (c) 1983, 1993 - * The Regents of the University of California. All rights reserved. + * ---------------------------------------------------------------------------- + * "THE BEER-WARE LICENSE" (Revision 42): + * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you + * can do whatever you want with this stuff. If we meet some day, and you think + * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp + * ---------------------------------------------------------------------------- * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. + * $Id$ * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. */ -#if defined(LIBC_SCCS) && !defined(lint) -static char sccsid[] = "@(#)malloc.c 8.1 (Berkeley) 6/4/93"; -#endif /* LIBC_SCCS and not lint */ +/* + * Defining EXTRA_SANITY will enable extra checks which are related + * to internal conditions and consistency in malloc.c. This has a + * noticeable runtime performance hit, and generally will not do you + * any good unless you fiddle with the internals of malloc or want + * to catch random pointer corruption as early as possible. + */ +#ifndef MALLOC_EXTRA_SANITY +#undef MALLOC_EXTRA_SANITY +#endif + +/* + * Defining MALLOC_STATS will enable you to call malloc_dump() and set + * the [dD] options in the MALLOC_OPTIONS environment variable. + * It has no run-time performance hit. + */ +#ifndef MALLOC_STATS +#undef MALLOC_STATS +#endif + +/* + * What to use for Junk. This is the byte value we use to fill with + * when the 'J' option is enabled. + */ +#define SOME_JUNK 0xd0 /* as in "Duh" :-) */ /* - * malloc.c (Caltech) 2/21/82 - * Chris Kingsley, kingsley@cit-20. + * The basic parameters you can tweak. + * + * malloc_pageshift pagesize = 1 << malloc_pageshift + * It's probably best if this is the native + * page size, but it shouldn't have to be. + * + * malloc_minsize minimum size of an allocation in bytes. + * If this is too small it's too much work + * to manage them. This is also the smallest + * unit of alignment used for the storage + * returned by malloc/realloc. * - * This is a very fast storage allocator. It allocates blocks of a small - * number of different sizes, and keeps free lists of each size. Blocks that - * don't exactly fit are passed up to the next larger size. In this - * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. - * This is designed for use in a virtual memory environment. */ -#include <sys/types.h> +#if defined(__i386__) && defined(__FreeBSD__) +# define malloc_pageshift 12U +# define malloc_minsize 16U +#endif /* __i386__ && __FreeBSD__ */ + +/* Insert your combination here... */ +#if defined(__FOOCPU__) && defined(__BAROS__) +# define malloc_pageshift 12U +# define malloc_minsize 16U +#endif /* __i386__ && __FreeBSD__ */ + +/* + * No user serviceable parts behind this point. + */ +#include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> +#include <errno.h> +#include <sys/types.h> +#include <sys/mman.h> -#define NULL 0 +/* + * This structure describes a page worth of chunks. + */ -static void morecore(); -static int findbucket(); +struct pginfo { + struct pginfo *next; /* next on the free list */ + void *page; /* Pointer to the page */ + u_short size; /* size of this page's chunks */ + u_short shift; /* How far to shift for this size chunks */ + u_short free; /* How many free chunks */ + u_short total; /* How many chunk */ + u_int bits[1]; /* Which chunks are free */ +}; /* - * The overhead on a block is at least 4 bytes. When free, this space - * contains a pointer to the next free block, and the bottom two bits must - * be zero. When in use, the first byte is set to MAGIC, and the second - * byte is the size index. The remaining bytes are for alignment. - * If range checking is enabled then a second word holds the size of the - * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). - * The order of elements is critical: ov_magic must overlay the low order - * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. + * This structure describes a number of free pages. */ -union overhead { - union overhead *ov_next; /* when free */ - struct { - u_char ovu_magic; /* magic number */ - u_char ovu_index; /* bucket # */ -#ifdef RCHECK - u_short ovu_rmagic; /* range magic number */ - u_int ovu_size; /* actual block size */ -#endif - } ovu; -#define ov_magic ovu.ovu_magic -#define ov_index ovu.ovu_index -#define ov_rmagic ovu.ovu_rmagic -#define ov_size ovu.ovu_size + +struct pgfree { + struct pgfree *next; /* next run of free pages */ + struct pgfree *prev; /* prev run of free pages */ + void *page; /* pointer to free pages */ + void *end; /* pointer to end of free pages */ + u_long size; /* number of bytes free */ }; -#define MAGIC 0xef /* magic # on accounting info */ -#define RMAGIC 0x5555 /* magic # on range info */ +/* + * How many bits per u_int in the bitmap. + * Change only if not 8 bits/byte + */ +#define MALLOC_BITS (8*sizeof(u_int)) + +/* + * Magic values to put in the page_directory + */ +#define MALLOC_NOT_MINE ((struct pginfo*) 0) +#define MALLOC_FREE ((struct pginfo*) 1) +#define MALLOC_FIRST ((struct pginfo*) 2) +#define MALLOC_FOLLOW ((struct pginfo*) 3) +#define MALLOC_MAGIC ((struct pginfo*) 4) -#ifdef RCHECK -#define RSLOP sizeof (u_short) -#else -#define RSLOP 0 +#ifndef malloc_pageshift +#define malloc_pageshift 12U +#endif + +#ifndef malloc_minsize +#define malloc_minsize 16U +#endif + +#ifndef malloc_pageshift +#error "malloc_pageshift undefined" +#endif + +#if !defined(malloc_pagesize) +#define malloc_pagesize (1U<<malloc_pageshift) +#endif + +#if ((1<<malloc_pageshift) != malloc_pagesize) +#error "(1<<malloc_pageshift) != malloc_pagesize" +#endif + +#ifndef malloc_maxsize +#define malloc_maxsize ((malloc_pagesize)>>1) #endif +/* A mask for the offset inside a page. */ +#define malloc_pagemask ((malloc_pagesize)-1) + +#define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask))) +#define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)-malloc_origo) + +/* Set when initialization has been done */ +static unsigned malloc_started; + +/* Number of free pages we cache */ +static unsigned malloc_cache = 16; + +/* The offset from pagenumber to index into the page directory */ +static u_long malloc_origo; + +/* The last index in the page directory we care about */ +static u_long last_index; + +/* Pointer to page directory. Allocated "as if with" malloc */ +static struct pginfo **page_dir; + +/* How many slots in the page directory */ +static unsigned malloc_ninfo; + +/* Free pages line up here */ +static struct pgfree free_list; + +/* Abort(), user doesn't handle problems. */ +static int malloc_abort; + +/* Are we trying to die ? */ +static int suicide; + +/* dump statistics */ +static int malloc_stats; + +/* always realloc ? */ +static int malloc_realloc; + +/* pass the kernel a hint on free pages ? */ +static int malloc_hint; + +/* zero fill ? */ +static int malloc_zero; + +/* junk fill ? */ +static int malloc_junk; + +/* utrace ? */ +static int malloc_utrace; + +#ifdef __FreeBSD__ +struct ut { void *p; size_t s; void *r; }; + +void utrace __P((struct ut *, int)); + +#define UTRACE(a, b, c) \ + if (malloc_utrace) \ + {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);} +#else /* !__FreeBSD__ */ +#define UTRACE(a,b,c) +#endif + +/* my last break. */ +static void *malloc_brk; + +/* one location cache for free-list holders */ +static struct pgfree *px; + +/* compile-time options */ +char *malloc_options; + +/* Name of the current public function */ +static char *malloc_func; + /* - * nextf[i] is the pointer to the next free block of size 2^(i+3). The - * smallest allocatable block is 8 bytes. The overhead information - * precedes the data area returned to the user. + * Necessary function declarations */ -#define NBUCKETS 30 -static union overhead *nextf[NBUCKETS]; -extern char *sbrk(); +static int extend_pgdir(u_long index); +static void *imalloc(size_t size); +static void ifree(void *ptr); +static void *irealloc(void *ptr, size_t size); + +#ifdef MALLOC_STATS +void +malloc_dump(FILE *fd) +{ + struct pginfo **pd; + struct pgfree *pf; + int j; + + pd = page_dir; + + /* print out all the pages */ + for(j=0;j<=last_index;j++) { + fprintf(fd, "%08lx %5d ", (j+malloc_origo) << malloc_pageshift, j); + if (pd[j] == MALLOC_NOT_MINE) { + for(j++;j<=last_index && pd[j] == MALLOC_NOT_MINE;j++) + ; + j--; + fprintf(fd, ".. %5d not mine\n", j); + } else if (pd[j] == MALLOC_FREE) { + for(j++;j<=last_index && pd[j] == MALLOC_FREE;j++) + ; + j--; + fprintf(fd, ".. %5d free\n", j); + } else if (pd[j] == MALLOC_FIRST) { + for(j++;j<=last_index && pd[j] == MALLOC_FOLLOW;j++) + ; + j--; + fprintf(fd, ".. %5d in use\n", j); + } else if (pd[j] < MALLOC_MAGIC) { + fprintf(fd, "(%p)\n", pd[j]); + } else { + fprintf(fd, "%p %d (of %d) x %d @ %p --> %p\n", + pd[j], pd[j]->free, pd[j]->total, + pd[j]->size, pd[j]->page, pd[j]->next); + } + } + + for(pf=free_list.next; pf; pf=pf->next) { + fprintf(fd, "Free: @%p [%p...%p[ %ld ->%p <-%p\n", + pf, pf->page, pf->end, pf->size, pf->prev, pf->next); + if (pf == pf->next) { + fprintf(fd, "Free_list loops.\n"); + break; + } + } + + /* print out various info */ + fprintf(fd, "Minsize\t%d\n", malloc_minsize); + fprintf(fd, "Maxsize\t%d\n", malloc_maxsize); + fprintf(fd, "Pagesize\t%d\n", malloc_pagesize); + fprintf(fd, "Pageshift\t%d\n", malloc_pageshift); + fprintf(fd, "FirstPage\t%ld\n", malloc_origo); + fprintf(fd, "LastPage\t%ld %lx\n", last_index+malloc_pageshift, + (last_index + malloc_pageshift) << malloc_pageshift); + fprintf(fd, "Break\t%ld\n", (u_long)sbrk(0) >> malloc_pageshift); +} +#endif /* MALLOC_STATS */ + +extern char *__progname; + +static void +wrterror(char *p) +{ + char *q = " error: "; + suicide = 1; + write(2, __progname, strlen(__progname)); + write(2, malloc_func, strlen(malloc_func)); + write(2, q, strlen(q)); + write(2, p, strlen(p)); +#ifdef MALLOC_STATS + if (malloc_stats) + malloc_dump(stderr); +#endif /* MALLOC_STATS */ + abort(); +} + +static void +wrtwarning(char *p) +{ + char *q = " warning: "; + if (malloc_abort) + wrterror(p); + write(2, __progname, strlen(__progname)); + write(2, malloc_func, strlen(malloc_func)); + write(2, q, strlen(q)); + write(2, p, strlen(p)); +} + +#ifdef MALLOC_STATS +static void +malloc_exit() +{ + FILE *fd = fopen("malloc.out", "a"); + char *q = "malloc() warning: Couldn't dump stats.\n"; + if (fd) { + malloc_dump(fd); + fclose(fd); + } else + write(2, q, strlen(q)); +} +#endif /* MALLOC_STATS */ -static int pagesz; /* page size */ -static int pagebucket; /* page size bucket */ -#ifdef MSTATS /* - * nmalloc[i] is the difference between the number of mallocs and frees - * for a given block size. + * Allocate a number of pages from the OS */ -static u_int nmalloc[NBUCKETS]; -#include <stdio.h> -#endif +static caddr_t +map_pages(int pages) +{ + caddr_t result, tail; -#if defined(DEBUG) || defined(RCHECK) -#define ASSERT(p) if (!(p)) botch("p") -#include <stdio.h> -static -botch(s) - char *s; + result = (caddr_t)pageround((u_long)sbrk(0)); + tail = result + (pages << malloc_pageshift); + + if (brk(tail)) { +#ifdef EXTRA_SANITY + wrterror("(ES): map_pages fails\n"); +#endif /* EXTRA_SANITY */ + return 0; + } + + last_index = ptr2index(tail) - 1; + malloc_brk = tail; + + if ((last_index+1) >= malloc_ninfo && !extend_pgdir(last_index)) + return 0;; + + return result; +} + +/* + * Extend page directory + */ +static int +extend_pgdir(u_long index) { - fprintf(stderr, "\r\nassertion botched: %s\r\n", s); - (void) fflush(stderr); /* just in case user buffered it */ - abort(); + struct pginfo **new, **old; + int i, oldlen; + + /* Make it this many pages */ + i = index * sizeof *page_dir; + i /= malloc_pagesize; + i += 2; + + /* remember the old mapping size */ + oldlen = malloc_ninfo * sizeof *page_dir; + + /* + * NOTE: we allocate new pages and copy the directory rather than tempt + * fate by trying to "grow" the region.. There is nothing to prevent + * us from accidently re-mapping space that's been allocated by our caller + * via dlopen() or other mmap(). + * + * The copy problem is not too bad, as there is 4K of page index per + * 4MB of malloc arena. + * + * We can totally avoid the copy if we open a file descriptor to associate + * the anon mappings with. Then, when we remap the pages at the new + * address, the old pages will be "magically" remapped.. But this means + * keeping open a "secret" file descriptor..... + */ + + /* Get new pages */ + new = (struct pginfo**) mmap(0, i * malloc_pagesize, PROT_READ|PROT_WRITE, + MAP_ANON|MAP_PRIVATE, -1, 0); + if (new == (struct pginfo **)-1) + return 0; + + /* Copy the old stuff */ + memcpy(new, page_dir, + malloc_ninfo * sizeof *page_dir); + + /* register the new size */ + malloc_ninfo = i * malloc_pagesize / sizeof *page_dir; + + /* swap the pointers */ + old = page_dir; + page_dir = new; + + /* Now free the old stuff */ + munmap((caddr_t)old, oldlen); + return 1; } -#else -#define ASSERT(p) -#endif -void * -malloc(nbytes) - size_t nbytes; +/* + * Initialize the world + */ +static void +malloc_init () { - register union overhead *op; - register int bucket, n; - register unsigned amt; + char *p, b[64]; + int i, j; - /* - * First time malloc is called, setup page size and - * align break pointer so all data will be page aligned. - */ - if (pagesz == 0) { - pagesz = n = getpagesize(); - op = (union overhead *)sbrk(0); - n = n - sizeof (*op) - ((int)op & (n - 1)); - if (n < 0) - n += pagesz; - if (n) { - if (sbrk(n) == (char *)-1) - return (NULL); - } - bucket = 0; - amt = 8; - while (pagesz > amt) { - amt <<= 1; - bucket++; - } - pagebucket = bucket; - } - /* - * Convert amount of memory requested into closest block size - * stored in hash buckets which satisfies request. - * Account for space used per block for accounting. - */ - if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { -#ifndef RCHECK - amt = 8; /* size of first bucket */ - bucket = 0; -#else - amt = 16; /* size of first bucket */ - bucket = 1; -#endif - n = -(sizeof (*op) + RSLOP); + +#ifdef EXTRA_SANITY + malloc_junk = 1; +#endif /* EXTRA_SANITY */ + + for (i = 0; i < 3; i++) { + if (i == 0) { + j = readlink("/etc/malloc.conf", b, sizeof b - 1); + if (j <= 0) + continue; + b[j] = '\0'; + p = b; + } else if (i == 1) { + p = getenv("MALLOC_OPTIONS"); } else { - amt = pagesz; - bucket = pagebucket; + p = malloc_options; } - while (nbytes > amt + n) { - amt <<= 1; - if (amt == 0) - return (NULL); - bucket++; - } - /* - * If nothing in hash bucket right now, - * request more memory from the system. - */ - if ((op = nextf[bucket]) == NULL) { - morecore(bucket); - if ((op = nextf[bucket]) == NULL) - return (NULL); + for (; p && *p; p++) { + switch (*p) { + case '>': malloc_cache <<= 1; break; + case '<': malloc_cache >>= 1; break; + case 'a': malloc_abort = 0; break; + case 'A': malloc_abort = 1; break; + case 'd': malloc_stats = 0; break; + case 'D': malloc_stats = 1; break; + case 'h': malloc_hint = 0; break; + case 'H': malloc_hint = 1; break; + case 'r': malloc_realloc = 0; break; + case 'R': malloc_realloc = 1; break; + case 'j': malloc_junk = 0; break; + case 'J': malloc_junk = 1; break; + case 'u': malloc_utrace = 0; break; + case 'U': malloc_utrace = 1; break; + case 'z': malloc_zero = 0; break; + case 'Z': malloc_zero = 1; break; + default: + j = malloc_abort; + malloc_abort = 0; + wrtwarning("unknown char in MALLOC_OPTIONS\n"); + malloc_abort = j; + break; + } } - /* remove from linked list */ - nextf[bucket] = op->ov_next; - op->ov_magic = MAGIC; - op->ov_index = bucket; -#ifdef MSTATS - nmalloc[bucket]++; -#endif -#ifdef RCHECK - /* - * Record allocated size of block and - * bound space with magic numbers. - */ - op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); - op->ov_rmagic = RMAGIC; - *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; -#endif - return ((char *)(op + 1)); + } + + UTRACE(0, 0, 0); + + /* + * We want junk in the entire allocation, and zero only in the part + * the user asked for. + */ + if (malloc_zero) + malloc_junk=1; + +#ifdef MALLOC_STATS + if (malloc_stats) + atexit(malloc_exit); +#endif /* MALLOC_STATS */ + + /* Allocate one page for the page directory */ + page_dir = (struct pginfo **) mmap(0, malloc_pagesize, PROT_READ|PROT_WRITE, + MAP_ANON|MAP_PRIVATE, -1, 0); + if (page_dir == (struct pginfo **) -1) + wrterror("mmap(2) failed, check limits.\n"); + + /* + * We need a maximum of malloc_pageshift buckets, steal these from the + * front of the page_directory; + */ + malloc_origo = ((u_long)pageround((u_long)sbrk(0))) >> malloc_pageshift; + malloc_origo -= malloc_pageshift; + + malloc_ninfo = malloc_pagesize / sizeof *page_dir; + + /* Been here, done that */ + malloc_started++; + + /* Recalculate the cache size in bytes, and make sure it's nonzero */ + + if (!malloc_cache) + malloc_cache++; + + malloc_cache <<= malloc_pageshift; + + /* + * This is a nice hack from Kaleb Keithly (kaleb@x.org). + * We can sbrk(2) further back when we keep this on a low address. + */ + px = (struct pgfree *) imalloc (sizeof *px); + } /* - * Allocate more memory to the indicated bucket. + * Allocate a number of complete pages */ -static void -morecore(bucket) - int bucket; +static void * +malloc_pages(size_t size) { - register union overhead *op; - register int sz; /* size of desired block */ - int amt; /* amount to allocate */ - int nblks; /* how many blocks we get */ + void *p, *delay_free = 0; + int i; + struct pgfree *pf; + u_long index; - /* - * sbrk_size <= 0 only for big, FLUFFY, requests (about - * 2^30 bytes on a VAX, I think) or for a negative arg. - */ - sz = 1 << (bucket + 3); -#ifdef DEBUG - ASSERT(sz > 0); -#else - if (sz <= 0) - return; -#endif - if (sz < pagesz) { - amt = pagesz; - nblks = amt / sz; - } else { - amt = sz + pagesz; - nblks = 1; + size = pageround(size); + + p = 0; + /* Look for free pages before asking for more */ + for(pf = free_list.next; pf; pf = pf->next) { + +#ifdef EXTRA_SANITY + if (pf->size & malloc_pagemask) + wrterror("(ES): junk length entry on free_list\n"); + if (!pf->size) + wrterror("(ES): zero length entry on free_list\n"); + if (pf->page == pf->end) + wrterror("(ES): zero entry on free_list\n"); + if (pf->page > pf->end) + wrterror("(ES): sick entry on free_list\n"); + if ((void*)pf->page >= (void*)sbrk(0)) + wrterror("(ES): entry on free_list past brk\n"); + if (page_dir[ptr2index(pf->page)] != MALLOC_FREE) + wrterror("(ES): non-free first page on free-list\n"); + if (page_dir[ptr2index(pf->end)-1] != MALLOC_FREE) + wrterror("(ES): non-free last page on free-list\n"); +#endif /* EXTRA_SANITY */ + + if (pf->size < size) + continue; + + if (pf->size == size) { + p = pf->page; + if (pf->next) + pf->next->prev = pf->prev; + pf->prev->next = pf->next; + delay_free = pf; + break; + } + + p = pf->page; + pf->page = (char *)pf->page + size; + pf->size -= size; + break; + } + +#ifdef EXTRA_SANITY + if (p && page_dir[ptr2index(p)] != MALLOC_FREE) + wrterror("(ES): allocated non-free page on free-list\n"); +#endif /* EXTRA_SANITY */ + + size >>= malloc_pageshift; + + /* Map new pages */ + if (!p) + p = map_pages(size); + + if (p) { + + index = ptr2index(p); + page_dir[index] = MALLOC_FIRST; + for (i=1;i<size;i++) + page_dir[index+i] = MALLOC_FOLLOW; + + if (malloc_junk) + memset(p, SOME_JUNK, size << malloc_pageshift); + } + + if (delay_free) { + if (!px) + px = delay_free; + else + ifree(delay_free); + } + + return p; +} + +/* + * Allocate a page of fragments + */ + +static __inline__ int +malloc_make_chunks(int bits) +{ + struct pginfo *bp; + void *pp; + int i, k, l; + + /* Allocate a new bucket */ + pp = malloc_pages(malloc_pagesize); + if (!pp) + return 0; + + /* Find length of admin structure */ + l = sizeof *bp - sizeof(u_long); + l += sizeof(u_long) * + (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS); + + /* Don't waste more than two chunks on this */ + if ((1<<(bits)) <= l+l) { + bp = (struct pginfo *)pp; + } else { + bp = (struct pginfo *)imalloc(l); + if (!bp) { + ifree(pp); + return 0; } - op = (union overhead *)sbrk(amt); - /* no more room! */ - if ((int)op == -1) - return; - /* - * Add new memory allocated to that on - * free list for this hash bucket. - */ - nextf[bucket] = op; - while (--nblks > 0) { - op->ov_next = (union overhead *)((caddr_t)op + sz); - op = (union overhead *)((caddr_t)op + sz); - } + } + + bp->size = (1<<bits); + bp->shift = bits; + bp->total = bp->free = malloc_pagesize >> bits; + bp->page = pp; + + /* set all valid bits in the bitmap */ + k = bp->total; + i = 0; + + /* Do a bunch at a time */ + for(;k-i >= MALLOC_BITS; i += MALLOC_BITS) + bp->bits[i / MALLOC_BITS] = ~0; + + for(; i < k; i++) + bp->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS); + + if (bp == bp->page) { + /* Mark the ones we stole for ourselves */ + for(i=0;l > 0;i++) { + bp->bits[i/MALLOC_BITS] &= ~(1<<(i%MALLOC_BITS)); + bp->free--; + bp->total--; + l -= (1 << bits); + } + } + + /* MALLOC_LOCK */ + + page_dir[ptr2index(pp)] = bp; + + bp->next = page_dir[bits]; + page_dir[bits] = bp; + + /* MALLOC_UNLOCK */ + + return 1; } -void -free(cp) - void *cp; -{ - register int size; - register union overhead *op; - - if (cp == NULL) - return; - op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); -#ifdef DEBUG - ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ -#else - if (op->ov_magic != MAGIC) - return; /* sanity */ -#endif -#ifdef RCHECK - ASSERT(op->ov_rmagic == RMAGIC); - ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); -#endif - size = op->ov_index; - ASSERT(size < NBUCKETS); - op->ov_next = nextf[size]; /* also clobbers ov_magic */ - nextf[size] = op; -#ifdef MSTATS - nmalloc[size]--; -#endif +/* + * Allocate a fragment + */ +static void * +malloc_bytes(size_t size) +{ + int i,j; + u_int u; + struct pginfo *bp; + int k; + u_int *lp; + + /* Don't bother with anything less than this */ + if (size < malloc_minsize) + size = malloc_minsize; + + /* Find the right bucket */ + j = 1; + i = size-1; + while (i >>= 1) + j++; + + /* If it's empty, make a page more of that size chunks */ + if (!page_dir[j] && !malloc_make_chunks(j)) + return 0; + + bp = page_dir[j]; + + /* Find first word of bitmap which isn't empty */ + for (lp = bp->bits; !*lp; lp++) + ; + + /* Find that bit, and tweak it */ + u = 1; + k = 0; + while (!(*lp & u)) { + u += u; + k++; + } + *lp ^= u; + + /* If there are no more free, remove from free-list */ + if (!--bp->free) { + page_dir[j] = bp->next; + bp->next = 0; + } + + /* Adjust to the real offset of that chunk */ + k += (lp-bp->bits)*MALLOC_BITS; + k <<= bp->shift; + + if (malloc_junk) + memset((u_char*)bp->page + k, SOME_JUNK, bp->size); + + return (u_char *)bp->page + k; } /* - * When a program attempts "storage compaction" as mentioned in the - * old malloc man page, it realloc's an already freed block. Usually - * this is the last block it freed; occasionally it might be farther - * back. We have to search all the free lists for the block in order - * to determine its bucket: 1st we make one pass thru the lists - * checking only the first block in each; if that fails we search - * ``__realloc_srchlen'' blocks in each list for a match (the variable - * is extern so the caller can modify it). If that fails we just copy - * however many bytes was given to realloc() and hope it's not huge. + * Allocate a piece of memory */ -int __realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ +static void * +imalloc(size_t size) +{ + void *result; -void * -realloc(cp, nbytes) - void *cp; - size_t nbytes; -{ - register u_int onb; - register int i; - union overhead *op; - char *res; - int was_alloced = 0; - - if (cp == NULL) - return (malloc(nbytes)); - op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); - if (op->ov_magic == MAGIC) { - was_alloced++; - i = op->ov_index; - } else { - /* - * Already free, doing "compaction". - * - * Search for the old block of memory on the - * free list. First, check the most common - * case (last element free'd), then (this failing) - * the last ``__realloc_srchlen'' items free'd. - * If all lookups fail, then assume the size of - * the memory block being realloc'd is the - * largest possible (so that all "nbytes" of new - * memory are copied into). Note that this could cause - * a memory fault if the old area was tiny, and the moon - * is gibbous. However, that is very unlikely. - */ - if ((i = findbucket(op, 1)) < 0 && - (i = findbucket(op, __realloc_srchlen)) < 0) - i = NBUCKETS; + if (!malloc_started) + malloc_init(); + + if (suicide) + abort(); + + if (size <= malloc_maxsize) + result = malloc_bytes(size); + else + result = malloc_pages(size); + + if (malloc_abort && !result) + wrterror("allocation failed.\n"); + + if (malloc_zero && result) + memset(result, 0, size); + + return result; +} + +/* + * Change the size of an allocation. + */ +static void * +irealloc(void *ptr, size_t size) +{ + void *p; + u_long osize, index; + struct pginfo **mp; + int i; + + if (suicide) + return 0; + + if (!malloc_started) { + wrtwarning("malloc() has never been called.\n"); + return 0; + } + + index = ptr2index(ptr); + + if (index < malloc_pageshift) { + wrtwarning("junk pointer, too low to make sense.\n"); + return 0; + } + + if (index > last_index) { + wrtwarning("junk pointer, too high to make sense.\n"); + return 0; + } + + mp = &page_dir[index]; + + if (*mp == MALLOC_FIRST) { /* Page allocation */ + + /* Check the pointer */ + if ((u_long)ptr & malloc_pagemask) { + wrtwarning("modified (page-) pointer.\n"); + return 0; } - onb = 1 << (i + 3); - if (onb < pagesz) - onb -= sizeof (*op) + RSLOP; - else - onb += pagesz - sizeof (*op) - RSLOP; - /* avoid the copy if same size block */ - if (was_alloced) { - if (i) { - i = 1 << (i + 2); - if (i < pagesz) - i -= sizeof (*op) + RSLOP; - else - i += pagesz - sizeof (*op) - RSLOP; - } - if (nbytes <= onb && nbytes > i) { -#ifdef RCHECK - op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); - *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; -#endif - return(cp); - } else - free(cp); + + /* Find the size in bytes */ + for (osize = malloc_pagesize; *++mp == MALLOC_FOLLOW;) + osize += malloc_pagesize; + + if (!malloc_realloc && /* unless we have to, */ + size <= osize && /* .. or are too small, */ + size > (osize - malloc_pagesize)) { /* .. or can free a page, */ + return ptr; /* don't do anything. */ } - if ((res = malloc(nbytes)) == NULL) - return (NULL); - if (cp != res) /* common optimization if "compacting" */ - bcopy(cp, res, (nbytes < onb) ? nbytes : onb); - return (res); + + } else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */ + + /* Check the pointer for sane values */ + if (((u_long)ptr & ((*mp)->size-1))) { + wrtwarning("modified (chunk-) pointer.\n"); + return 0; + } + + /* Find the chunk index in the page */ + i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift; + + /* Verify that it isn't a free chunk already */ + if ((*mp)->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) { + wrtwarning("chunk is already free.\n"); + return 0; + } + + osize = (*mp)->size; + + if (!malloc_realloc && /* Unless we have to, */ + size < osize && /* ..or are too small, */ + (size > osize/2 || /* ..or could use a smaller size, */ + osize == malloc_minsize)) { /* ..(if there is one) */ + return ptr; /* ..Don't do anything */ + } + + } else { + wrtwarning("pointer to wrong page.\n"); + return 0; + } + + p = imalloc(size); + + if (p) { + /* copy the lesser of the two sizes, and free the old one */ + if (osize < size) + memcpy(p, ptr, osize); + else + memcpy(p, ptr, size); + ifree(ptr); + } + return p; } /* - * Search ``srchlen'' elements of each free list for a block whose - * header starts at ``freep''. If srchlen is -1 search the whole list. - * Return bucket number, or -1 if not found. + * Free a sequence of pages */ -static -findbucket(freep, srchlen) - union overhead *freep; - int srchlen; + +static __inline__ void +free_pages(void *ptr, int index, struct pginfo *info) { - register union overhead *p; - register int i, j; - - for (i = 0; i < NBUCKETS; i++) { - j = 0; - for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { - if (p == freep) - return (i); - j++; - } + int i; + struct pgfree *pf, *pt=0; + u_long l; + void *tail; + + if (info == MALLOC_FREE) { + wrtwarning("page is already free.\n"); + return; + } + + if (info != MALLOC_FIRST) { + wrtwarning("pointer to wrong page.\n"); + return; + } + + if ((u_long)ptr & malloc_pagemask) { + wrtwarning("modified (page-) pointer.\n"); + return; + } + + /* Count how many pages and mark them free at the same time */ + page_dir[index] = MALLOC_FREE; + for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++) + page_dir[index + i] = MALLOC_FREE; + + l = i << malloc_pageshift; + + if (malloc_junk) + memset(ptr, SOME_JUNK, l); + + if (malloc_hint) + madvise(ptr, l, MADV_FREE); + + tail = (char *)ptr+l; + + /* add to free-list */ + if (!px) + px = imalloc(sizeof *pt); /* This cannot fail... */ + px->page = ptr; + px->end = tail; + px->size = l; + if (!free_list.next) { + + /* Nothing on free list, put this at head */ + px->next = free_list.next; + px->prev = &free_list; + free_list.next = px; + pf = px; + px = 0; + + } else { + + /* Find the right spot, leave pf pointing to the modified entry. */ + tail = (char *)ptr+l; + + for(pf = free_list.next; pf->end < ptr && pf->next; pf = pf->next) + ; /* Race ahead here */ + + if (pf->page > tail) { + /* Insert before entry */ + px->next = pf; + px->prev = pf->prev; + pf->prev = px; + px->prev->next = px; + pf = px; + px = 0; + } else if (pf->end == ptr ) { + /* Append to the previous entry */ + pf->end = (char *)pf->end + l; + pf->size += l; + if (pf->next && pf->end == pf->next->page ) { + /* And collapse the next too. */ + pt = pf->next; + pf->end = pt->end; + pf->size += pt->size; + pf->next = pt->next; + if (pf->next) + pf->next->prev = pf; + } + } else if (pf->page == tail) { + /* Prepend to entry */ + pf->size += l; + pf->page = ptr; + } else if (!pf->next) { + /* Append at tail of chain */ + px->next = 0; + px->prev = pf; + pf->next = px; + pf = px; + px = 0; + } else { + wrterror("freelist is destroyed.\n"); } - return (-1); + } + + /* Return something to OS ? */ + if (!pf->next && /* If we're the last one, */ + pf->size > malloc_cache && /* ..and the cache is full, */ + pf->end == malloc_brk && /* ..and none behind us, */ + malloc_brk == sbrk(0)) { /* ..and it's OK to do... */ + + /* + * Keep the cache intact. Notice that the '>' above guarantees that + * the pf will always have at least one page afterwards. + */ + pf->end = (char *)pf->page + malloc_cache; + pf->size = malloc_cache; + + brk(pf->end); + malloc_brk = pf->end; + + index = ptr2index(pf->end); + last_index = index - 1; + + for(i=index;i <= last_index;) + page_dir[i++] = MALLOC_NOT_MINE; + + /* XXX: We could realloc/shrink the pagedir here I guess. */ + } + if (pt) + ifree(pt); } -#ifdef MSTATS /* - * mstats - print out statistics about malloc - * - * Prints two lines of numbers, one showing the length of the free list - * for each size category, the second showing the number of mallocs - - * frees for each size category. + * Free a chunk, and possibly the page it's on, if the page becomes empty. */ -mstats(s) - char *s; + +static __inline__ void +free_bytes(void *ptr, int index, struct pginfo *info) { - register int i, j; - register union overhead *p; - int totfree = 0, - totused = 0; - - fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); - for (i = 0; i < NBUCKETS; i++) { - for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) - ; - fprintf(stderr, " %d", j); - totfree += j * (1 << (i + 3)); - } - fprintf(stderr, "\nused:\t"); - for (i = 0; i < NBUCKETS; i++) { - fprintf(stderr, " %d", nmalloc[i]); - totused += nmalloc[i] * (1 << (i + 3)); - } - fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", - totused, totfree); + int i; + struct pginfo **mp; + void *vp; + + /* Find the chunk number on the page */ + i = ((u_long)ptr & malloc_pagemask) >> info->shift; + + if (((u_long)ptr & (info->size-1))) { + wrtwarning("modified (chunk-) pointer.\n"); + return; + } + + if (info->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) { + wrtwarning("chunk is already free.\n"); + return; + } + + if (malloc_junk) + memset(ptr, SOME_JUNK, info->size); + + info->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS); + info->free++; + + mp = page_dir + info->shift; + + if (info->free == 1) { + + /* Page became non-full */ + + mp = page_dir + info->shift; + /* Insert in address order */ + while (*mp && (*mp)->next && (*mp)->next->page < info->page) + mp = &(*mp)->next; + info->next = *mp; + *mp = info; + return; + } + + if (info->free != info->total) + return; + + /* Find & remove this page in the queue */ + while (*mp != info) { + mp = &((*mp)->next); +#ifdef EXTRA_SANITY + if (!*mp) + wrterror("(ES): Not on queue\n"); +#endif /* EXTRA_SANITY */ + } + *mp = info->next; + + /* Free the page & the info structure if need be */ + page_dir[ptr2index(info->page)] = MALLOC_FIRST; + vp = info->page; /* Order is important ! */ + if(vp != (void*)info) + ifree(info); + ifree(vp); } + +static void +ifree(void *ptr) +{ + struct pginfo *info; + int index; + + /* This is legal */ + if (!ptr) + return; + + if (!malloc_started) { + wrtwarning("malloc() has never been called.\n"); + return; + } + + /* If we're already sinking, don't make matters any worse. */ + if (suicide) + return; + + index = ptr2index(ptr); + + if (index < malloc_pageshift) { + wrtwarning("junk pointer, too low to make sense.\n"); + return; + } + + if (index > last_index) { + wrtwarning("junk pointer, too high to make sense.\n"); + return; + } + + info = page_dir[index]; + + if (info < MALLOC_MAGIC) + free_pages(ptr, index, info); + else + free_bytes(ptr, index, info); + return; +} + +/* + * These are the public exported interface routines. + */ + +#ifdef _THREAD_SAFE +#include <pthread.h> +#include "pthread_private.h" +static int malloc_lock; +#define THREAD_LOCK() _thread_kern_sig_block(&malloc_lock); +#define THREAD_UNLOCK() _thread_kern_sig_unblock(malloc_lock); +#else +#define THREAD_LOCK() +#define THREAD_UNLOCK() #endif + +static int malloc_active; + +void * +malloc(size_t size) +{ + register void *r; + + malloc_func = " in malloc():"; + THREAD_LOCK(); + if (malloc_active++) { + wrtwarning("recursive call.\n"); + malloc_active--; + return (0); + } + r = imalloc(size); + UTRACE(0, size, r); + malloc_active--; + THREAD_UNLOCK(); + return (r); +} + +void +free(void *ptr) +{ + malloc_func = " in free():"; + THREAD_LOCK(); + if (malloc_active++) { + wrtwarning("recursive call.\n"); + malloc_active--; + return; + } + ifree(ptr); + UTRACE(ptr, 0, 0); + malloc_active--; + THREAD_UNLOCK(); + return; +} + +void * +realloc(void *ptr, size_t size) +{ + register void *r; + + malloc_func = " in realloc():"; + THREAD_LOCK(); + if (malloc_active++) { + wrtwarning("recursive call.\n"); + malloc_active--; + return (0); + } + if (!ptr) { + r = imalloc(size); + } else if (ptr && !size) { + ifree(ptr); + r = 0; + } else { + r = irealloc(ptr, size); + } + UTRACE(ptr, size, r); + malloc_active--; + THREAD_UNLOCK(); + return (r); +} diff --git a/lib/libc/stdlib/memory.3 b/lib/libc/stdlib/memory.3 index 9bc600b..0a1fed4 100644 --- a/lib/libc/stdlib/memory.3 +++ b/lib/libc/stdlib/memory.3 @@ -30,6 +30,7 @@ .\" SUCH DAMAGE. .\" .\" @(#)memory.3 8.1 (Berkeley) 6/4/93 +.\" $Id$ .\" .Dd June 4, 1993 .Dt MEMORY 3 @@ -58,11 +59,11 @@ These functions allocate and free memory for the calling process. They are described in the individual manual pages. .Sh SEE ALSO +.Xr alloca 3 , .Xr calloc 3 , .Xr free 3 , .Xr malloc 3 , -.Xr realloc 3 , -.Xr alloca 3 , +.Xr realloc 3 .Sh STANDARDS These functions, with the exception of .Fn alloca diff --git a/lib/libc/stdlib/merge.c b/lib/libc/stdlib/merge.c index 7d00844..a47e300 100644 --- a/lib/libc/stdlib/merge.c +++ b/lib/libc/stdlib/merge.c @@ -80,7 +80,7 @@ static void insertionsort __P((u_char *, size_t, size_t, int (*)())); do \ *dst++ = *src++; \ while (i -= 1) - + /* * Find the next possible pointer head. (Trickery for forcing an array * to do double duty as a linked list when objects do not align with word @@ -164,7 +164,7 @@ EXPONENTIAL: for (i = size; ; i <<= 1) } else if ((*cmp)(q, p) <= sense) { t = p; if (i == size) - big = 0; + big = 0; goto FASTCASE; } else b = p; diff --git a/lib/libc/stdlib/qsort.c b/lib/libc/stdlib/qsort.c index 1d3aa93..ff3def5 100644 --- a/lib/libc/stdlib/qsort.c +++ b/lib/libc/stdlib/qsort.c @@ -32,13 +32,17 @@ */ #if defined(LIBC_SCCS) && !defined(lint) +#if 0 static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93"; +#endif +static const char rcsid[] = + "$Id$"; #endif /* LIBC_SCCS and not lint */ -#include <sys/types.h> #include <stdlib.h> -static inline char *med3 __P((char *, char *, char *, int (*)())); +typedef int cmp_t __P((const void *, const void *)); +static inline char *med3 __P((char *, char *, char *, cmp_t *)); static inline void swapfunc __P((char *, char *, int, int)); #define min(a, b) (a) < (b) ? a : b @@ -65,7 +69,7 @@ swapfunc(a, b, n, swaptype) char *a, *b; int n, swaptype; { - if(swaptype <= 1) + if(swaptype <= 1) swapcode(long, a, b, n) else swapcode(char, a, b, n) @@ -84,7 +88,7 @@ swapfunc(a, b, n, swaptype) static inline char * med3(a, b, c, cmp) char *a, *b, *c; - int (*cmp)(); + cmp_t *cmp; { return cmp(a, b) < 0 ? (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) @@ -95,7 +99,7 @@ void qsort(a, n, es, cmp) void *a; size_t n, es; - int (*cmp)(); + cmp_t *cmp; { char *pa, *pb, *pc, *pd, *pl, *pm, *pn; int d, r, swaptype, swap_cnt; @@ -103,16 +107,16 @@ qsort(a, n, es, cmp) loop: SWAPINIT(a, es); swap_cnt = 0; if (n < 7) { - for (pm = a + es; pm < (char *) a + n * es; pm += es) - for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; + for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) + for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es) swap(pl, pl - es); return; } - pm = a + (n / 2) * es; + pm = (char *)a + (n / 2) * es; if (n > 7) { pl = a; - pn = a + (n - 1) * es; + pn = (char *)a + (n - 1) * es; if (n > 40) { d = (n / 8) * es; pl = med3(pl, pl + d, pl + 2 * d, cmp); @@ -122,9 +126,9 @@ loop: SWAPINIT(a, es); pm = med3(pl, pm, pn, cmp); } swap(a, pm); - pa = pb = a + es; + pa = pb = (char *)a + es; - pc = pd = a + (n - 1) * es; + pc = pd = (char *)a + (n - 1) * es; for (;;) { while (pb <= pc && (r = cmp(pb, a)) <= 0) { if (r == 0) { @@ -150,21 +154,21 @@ loop: SWAPINIT(a, es); pc -= es; } if (swap_cnt == 0) { /* Switch to insertion sort */ - for (pm = a + es; pm < (char *) a + n * es; pm += es) - for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; + for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) + for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es) swap(pl, pl - es); return; } - pn = a + n * es; + pn = (char *)a + n * es; r = min(pa - (char *)a, pb - pa); vecswap(a, pb - r, r); r = min(pd - pc, pn - pd - es); vecswap(pb, pn - r, r); if ((r = pb - pa) > es) qsort(a, r / es, es, cmp); - if ((r = pd - pc) > es) { + if ((r = pd - pc) > es) { /* Iterate rather than recurse to save stack space */ a = pn - r; n = r / es; diff --git a/lib/libc/stdlib/radixsort.3 b/lib/libc/stdlib/radixsort.3 index ce30378..4d49d46 100644 --- a/lib/libc/stdlib/radixsort.3 +++ b/lib/libc/stdlib/radixsort.3 @@ -157,4 +157,5 @@ for any of the errors specified for the library routine .Sh HISTORY The .Fn radixsort -function first appeared in 4.4BSD. +function first appeared in +.Bx 4.4 . diff --git a/lib/libc/stdlib/radixsort.c b/lib/libc/stdlib/radixsort.c index d211f3d..af47fb0 100644 --- a/lib/libc/stdlib/radixsort.c +++ b/lib/libc/stdlib/radixsort.c @@ -3,7 +3,7 @@ * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by - * Peter McIlroy and by Dan Bernstein at New York University, + * Peter McIlroy and by Dan Bernstein at New York University, * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -40,13 +40,13 @@ static char sccsid[] = "@(#)radixsort.c 8.1 (Berkeley) 6/4/93"; /* * Radixsort routines. - * + * * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack. * Use radixsort(a, n, trace, endchar) for this case. - * + * * For stable sorting (using N extra pointers) use sradixsort(), which calls * r_sort_b(). - * + * * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic, * "Engineering Radix Sort". */ @@ -294,7 +294,7 @@ r_sort_b(a, ta, n, i, tr, endch) *--top[tr[(*ak)[i]]] = *ak; } } - + static inline void simplesort(a, n, b, tr, endch) /* insertion sort */ register const u_char **a; diff --git a/lib/libc/stdlib/random.3 b/lib/libc/stdlib/random.3 index 84680e2..dd85711 100644 --- a/lib/libc/stdlib/random.3 +++ b/lib/libc/stdlib/random.3 @@ -64,11 +64,16 @@ The period of this random number generator is very large, approximately .if n 16*((2**31)\(mi1). .Pp The -.Fn random Ns / Fn srandom -have (almost) the same calling sequence and initialization properties as -.Xr rand 3 Ns / Xr srand 3 . +.Fn random +and +.Fn srandom +functions have (almost) the same calling sequence and initialization properties as the +.Xr rand 3 +and +.Xr srand 3 +functions. The difference is that -.Xr rand +.Xr rand 3 produces a much less random sequence \(em in fact, the low dozen bits generated by rand go through a cyclic pattern. All the bits generated by .Fn random @@ -77,15 +82,8 @@ are usable. For example, will produce a random binary value. .Pp -Unlike -.Xr srand , -.Fn srandom -does not return the old seed; the reason for this is that the amount of -state information used is much more than a single word. (Two other -routines are provided to deal with restarting/changing random -number generators). Like +Like .Xr rand 3 , -however, .Fn random will by default produce a sequence of numbers that can be duplicated by calling @@ -156,11 +154,29 @@ is called with less than 8 bytes of state information, or if detects that the state information has been garbled, error messages are printed on the standard error output. .Sh SEE ALSO -.Xr rand 3 +.Xr rand 3 , +.Xr srand 3 .Sh HISTORY These functions appeared in .Bx 4.2 . .Sh BUGS +.Pp About 2/3 the speed of .Xr rand 3 . +.Pp +The historical implementation used to have a very weak seeding; the +random sequence did not vary much with the seed. For compatibility +reasons, this implementation has been made available until the +next FreeBSD release +via the +functions +.Fn orandom , +.Fn osrandom , +.Fn oinitstate +and +.Fn osetstate +from the compatibility library, +.Em libcompat . +The current implementation employs a better pseudo-random number +generator for the initial state calculation. diff --git a/lib/libc/stdlib/random.c b/lib/libc/stdlib/random.c index 18babba..d1ec971 100644 --- a/lib/libc/stdlib/random.c +++ b/lib/libc/stdlib/random.c @@ -35,6 +35,14 @@ static char sccsid[] = "@(#)random.c 8.1 (Berkeley) 6/4/93"; #endif /* LIBC_SCCS and not lint */ +#ifdef COMPAT_WEAK_SEEDING +#define USE_WEAK_SEEDING +#define random orandom +#define srandom osrandom +#define initstate oinitstate +#define setstate osetstate +#endif + #include <stdio.h> #include <stdlib.h> @@ -61,7 +69,7 @@ static char sccsid[] = "@(#)random.c 8.1 (Berkeley) 6/4/93"; * state information, which will allow a degree seven polynomial. (Note: * the zeroeth word of state information also has some other information * stored in it -- see setstate() for details). - * + * * The random number generation technique is a linear feedback shift register * approach, employing trinomials (since there are fewer terms to sum up that * way). In this approach, the least significant bit of all the numbers in @@ -122,7 +130,7 @@ static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; /* * Initially, everything is set up as if from: * - * initstate(1, &randtbl, 128); + * initstate(1, randtbl, 128); * * Note that this initialization takes advantage of the fact that srandom() * advances the front and rear pointers 10*rand_deg times, and hence the @@ -135,12 +143,23 @@ static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; static long randtbl[DEG_3 + 1] = { TYPE_3, +#ifdef USE_WEAK_SEEDING +/* Historic implementation compatibility */ +/* The random sequences do not vary much with the seed */ 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5, 0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, 0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7, 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc, 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b, 0x27fb47b9, +#else /* !USE_WEAK_SEEDING */ + 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05, + 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454, + 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471, + 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1, + 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41, + 0xf3bec5da +#endif /* !USE_WEAK_SEEDING */ }; /* @@ -176,6 +195,38 @@ static int rand_deg = DEG_3; static int rand_sep = SEP_3; static long *end_ptr = &randtbl[DEG_3 + 1]; +static inline long good_rand __P((long)); + +static inline long good_rand (x) + register long x; +{ +#ifdef USE_WEAK_SEEDING +/* + * Historic implementation compatibility. + * The random sequences do not vary much with the seed, + * even with overflowing. + */ + return (1103515245 * x + 12345); +#else /* !USE_WEAK_SEEDING */ +/* + * Compute x = (7^5 * x) mod (2^31 - 1) + * wihout overflowing 31 bits: + * (2^31 - 1) = 127773 * (7^5) + 2836 + * From "Random number generators: good ones are hard to find", + * Park and Miller, Communications of the ACM, vol. 31, no. 10, + * October 1988, p. 1195. + */ + register long hi, lo; + + hi = x / 127773; + lo = x % 127773; + x = 16807 * lo - 2836 * hi; + if (x <= 0) + x += 0x7fffffff; + return (x); +#endif /* !USE_WEAK_SEEDING */ +} + /* * srandom: * @@ -190,17 +241,16 @@ static long *end_ptr = &randtbl[DEG_3 + 1]; */ void srandom(x) - u_int x; + unsigned int x; { - register int i, j; + register int i; if (rand_type == TYPE_0) state[0] = x; else { - j = 1; state[0] = x; for (i = 1; i < rand_deg; i++) - state[i] = 1103515245 * state[i - 1] + 12345; + state[i] = good_rand(state[i - 1]); fptr = &state[rand_sep]; rptr = &state[0]; for (i = 0; i < 10 * rand_deg; i++) @@ -216,12 +266,12 @@ srandom(x) * the break values for the different R.N.G.'s, we choose the best (largest) * one we can and set things up for it. srandom() is then called to * initialize the state information. - * + * * Note that on return from srandom(), we set state[-1] to be the type * multiplexed with the current value of the rear pointer; this is so * successive calls to initstate() won't lose this information and will be * able to restart with setstate(). - * + * * Note: the first thing we do is save the current state, if any, just like * setstate() so that it doesn't matter when initstate is called. * @@ -229,7 +279,7 @@ srandom(x) */ char * initstate(seed, arg_state, n) - u_int seed; /* seed for R.N.G. */ + unsigned int seed; /* seed for R.N.G. */ char *arg_state; /* pointer to state array */ int n; /* # bytes of state info */ { @@ -349,7 +399,7 @@ random() long i; if (rand_type == TYPE_0) - i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff; + i = state[0] = good_rand(state[0]) & 0x7fffffff; else { *fptr += *rptr; i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */ diff --git a/lib/libc/stdlib/realpath.c b/lib/libc/stdlib/realpath.c index 20efabd..28380d7 100644 --- a/lib/libc/stdlib/realpath.c +++ b/lib/libc/stdlib/realpath.c @@ -98,7 +98,7 @@ loop: p = resolved; /* Deal with the last component. */ - if (lstat(p, &sb) == 0) { + if (*p != '\0' && lstat(p, &sb) == 0) { if (S_ISLNK(sb.st_mode)) { n = readlink(p, resolved, MAXPATHLEN); if (n < 0) diff --git a/lib/libc/stdlib/setenv.c b/lib/libc/stdlib/setenv.c index b36d673..d981277 100644 --- a/lib/libc/stdlib/setenv.c +++ b/lib/libc/stdlib/setenv.c @@ -39,13 +39,14 @@ static char sccsid[] = "@(#)setenv.c 8.1 (Berkeley) 6/4/93"; #include <stdlib.h> #include <string.h> -char *__findenv __P((const char *, int *)); +char *__findenv __P((const char *, int *)); /* * setenv -- * Set the value of the environmental variable "name" to be * "value". If rewrite is set, replace any current value. */ +int setenv(name, value, rewrite) register const char *name; register const char *value; @@ -63,7 +64,7 @@ setenv(name, value, rewrite) if (!rewrite) return (0); if (strlen(c) >= l_value) { /* old larger; copy over */ - while (*c++ = *value++); + while ( (*c++ = *value++) ); return (0); } } else { /* create new slot */ @@ -93,7 +94,7 @@ setenv(name, value, rewrite) malloc((size_t)((int)(c - name) + l_value + 2)))) return (-1); for (c = environ[offset]; (*c = *name++) && *c != '='; ++c); - for (*c++ = '='; *c++ = *value++;); + for (*c++ = '='; (*c++ = *value++); ); return (0); } diff --git a/lib/libc/stdlib/strhash.c b/lib/libc/stdlib/strhash.c new file mode 100644 index 0000000..8e2230b --- /dev/null +++ b/lib/libc/stdlib/strhash.c @@ -0,0 +1,436 @@ +#ifndef lint +static char *rcsid = "$Header: /home/ncvs/src/lib/libc/stdlib/strhash.c,v 1.5 1995/10/22 14:53:17 phk Exp $"; +#endif + +/* + * + * Copyright 1990 + * Terry Jones & Jordan Hubbard + * + * PCS Computer Systeme, GmbH. + * Munich, West Germany + * + * + * All rights reserved. + * + * This is unsupported software and is subject to change without notice. + * the author makes no representations about the suitability of this software + * for any purpose. It is supplied "as is" without express or implied + * warranty. + * + * Permission to use, copy, modify, and distribute this software and its + * documentation for any purpose and without fee is hereby granted, provided + * that the above copyright notice appear in all copies and that both that + * copyright notice and this permission notice appear in supporting + * documentation, and that the name of the author not be used in + * advertising or publicity pertaining to distribution of the software + * without specific, written prior permission. + * + */ + +/* + * This is a fairly simple open addressing hash scheme. + * Terry did all the code, I just did the spec. + * Thanks again, you crazy Aussie.. + * + */ + +/* + * $Log: strhash.c,v $ + * Revision 1.5 1995/10/22 14:53:17 phk + * Mino cleanup, #includes & unused vars. + * + * Revision 1.4 1995/05/30 05:41:55 rgrimes + * Remove trailing whitespace. + * + * Revision 1.3 1995/03/28 08:41:02 jkh + * Fix a missing _hash() to prevent namespace pollution with the db/hash routines. + * Grrr. If the dbhash routines weren't grossly overengineered I wouldn't + * even need to do this! :-( + * + * Also now export the hash_stats routine. Manpage coming RSN - I promise. + * + * Revision 1.2 1995/03/26 19:32:24 ache + * Hash 8bit chars without sign extension + * + * Revision 1.1 1995/03/26 10:21:55 jkh + * Add the strhash family of routines. They provide a number of features + * that the db/hash functions don't, and they're much simpler to use for + * low-overhead string hashing. + * + * Revision 1.1 1995/02/25 02:16:34 jkh + * Second version of this - now support the essentials of a basic + * attributed file system for storing menu information and command + * templates. This is not finished yet, but it does compile so I can + * commit it to the tree now and continue working on it. + * + * Revision 2.0 90/03/26 01:44:26 jkh + * pre-beta check-in + * + * Revision 1.8 90/03/09 19:22:35 jkh + * Fixed bogus comment. + * + * Revision 1.7 90/03/09 19:01:08 jkh + * Added comments, GPL. + * + * Revision 1.6 90/03/08 17:55:58 terry + * Rearranged hash_purge to be a tiny bit more efficient. + * Added verbose option to hash_stats. + * + * Revision 1.5 90/03/08 17:19:54 terry + * Added hash_purge. Added arg to hash_traverse. Changed all + * void * to Generic. + * + * Revision 1.4 90/03/08 12:02:35 terry + * Fixed problems with allocation that I screwed up last night. + * Changed bucket lists to be singly linked. Thanks to JKH, my hero. + * + * Revision 1.3 90/03/07 21:33:33 terry + * Cleaned up a few decls to keep gcc -Wall quiet. + * + * Revision 1.2 90/03/07 21:14:53 terry + * Comments. Added HASH_STATS define. Removed hash_find() + * and new_node(). + * + * Revision 1.1 90/03/07 20:49:45 terry + * Initial revision + * + * + */ + + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/types.h> +#include <strhash.h> + +#define HASH_NULL (hash_table *)0 +#define NODE_NULL (hash_node *)0 +#define GENERIC_NULL (void *)0 + +#define HASH_SZ 97 + + +static int _hash(int size, char *key); +static hash_node *list_find(caddr_t key, hash_node *head); + + +/* + * hash_create() + * + * Malloc room for a new hash table and then room for its + * bucket pointers. Then set all the buckets to + * point to 0. Return the address of the new table. + */ +hash_table * +hash_create(int size) +{ + register int i; + hash_table *new = (hash_table *)malloc(sizeof(hash_table)); + + if (!new || size < 0){ + return HASH_NULL; + } + + if (size == 0){ + size = HASH_SZ; + } + + if (!(new->buckets = (hash_node **)malloc(size * sizeof(hash_node *)))){ + return HASH_NULL; + } + + for (i = 0; i < size; i++){ + new->buckets[i] = NODE_NULL; + } + new->size = size; + + return new; +} + + +/* + * list_find() + * + * Find the key in the linked list pointed to by head. + */ +static hash_node * +list_find(caddr_t key, hash_node *head) +{ + while (head){ + if (!strcmp(head->key, key)){ + return head; + } + head = head->next; + } + return NODE_NULL; +} + + +/* + * _hash() + * + * Compute the hash value for the given key. + */ +static int +_hash(int size, char *key) +{ + unsigned int h = 0x0; + + while (*key){ + h = (h << 1) ^ (h ^ (unsigned char) *key++); + } + + h %= size; + return h; +} + +/* + * hash_destroy() + * + * Find the key and (if it's there) remove it entirely. + * The function (*nukefunc)() is in charge of disposing + * of the storage help by the data associated with the node. + */ +void +hash_destroy(hash_table *table, char *key, void (*nukefunc)()) +{ + int bucket = _hash(table->size, key); + hash_node *found = table->buckets[bucket]; + hash_node *to_free = NODE_NULL; + + if (!found) { + return; + } + + if (!strcmp(found->key, key)) { + /* + * It was the head of the list. + */ + table->buckets[bucket] = found->next; + to_free = found; + } + else { + /* + * Walk the list, looking one ahead. + */ + while (found->next) { + if (!strcmp(found->next->key, key)) { + to_free = found->next; + found->next = found->next->next; + break; + } + found = found->next; + } + + if (!to_free){ + return; + } + } + + if (nukefunc) + (*nukefunc)(to_free->key, to_free->data); + free(to_free); + return; +} + + +/* + * hash_search() + * + * Search the table for the given key. Then: + * + * 1) If you find it and there is no replacement function, just + * return what you found. (This is a simple search). + * 2) If you find it and there is a replacement function, run + * the function on the data you found, and replace the old + * data with whatever is passed in datum. Return 0. + * 3) If you don't find it and there is some datum, insert a + * new item into the table. Insertions go at the front of + * the bucket. Return 0. + * 4) Otherwise just return 0. + * + */ +void * +hash_search(hash_table *table, caddr_t key, void *datum, + void (*replace_func)()) +{ + int bucket = _hash(table->size, key); + hash_node *found = list_find(key, table->buckets[bucket]); + + if (found){ + if (!replace_func){ + return found->data; + } + else{ + (*replace_func)(found->data); + found->data = datum; + } + } + else{ + if (datum){ + + static int assign_key(); + + hash_node *new = (hash_node *)malloc(sizeof(hash_node)); + + if (!new || !assign_key(key, new)){ + return GENERIC_NULL; + } + new->data = datum; + new->next = table->buckets[bucket]; + table->buckets[bucket] = new; + return new; + } + } + return GENERIC_NULL; +} + + +/* + * assign_key() + * + * Set the key value of a node to be 'key'. Get some space from + * malloc and copy it in etc. Return 1 if all is well, 0 otherwise. + */ +static int +assign_key(char *key, hash_node *node) +{ + if (!node || !key){ + return 0; + } + + if (!(node->key = (char *)malloc(strlen(key) + 1))){ + return 0; + } + + node->key[0] = '\0'; + strcat(node->key, key); + return 1; +} + +/* + * hash_traverse() + * + * Traverse the hash table and run the function func on the + * data found at each node and the argument we're passed for it. + */ +void +hash_traverse(hash_table *table, int (*func)(), void *arg) +{ + register int i; + register int size = table->size; + + if (!func) + return; + + for (i = 0; i < size; i++) { + hash_node *n = table->buckets[i]; + while (n) { + if ((*func)(n->key, n->data, arg) == 0) + return; + n = n->next; + } + } + return; +} + +/* + * hash_purge() + * + * Run through the entire hash table. Call purge_func + * on the data found at each node, and then free the node. + * Set all the bucket pointers to 0. + */ +void +hash_purge(hash_table *table, void (*purge_func)(char *p1, void *p2)) +{ + register int i; + register int size = table->size; + + for (i = 0; i < size; i++) { + hash_node *n = table->buckets[i]; + if (n) { + do { + hash_node *to_free = n; + if (purge_func) { + (*purge_func)(n->key, n->data); + } + n = n->next; + free(to_free); + } while (n); + table->buckets[i] = NODE_NULL; + } + } +} + +#undef min +#define min(a, b) (a) < (b) ? (a) : (b) + +/* + * hash_stats() + * + * Print statistics about the current table allocation to stdout. + */ +void +hash_stats(hash_table *table, int verbose) +{ + register int i; + int total_elements = 0; + int non_empty_buckets = 0; + int max_count = 0; + int max_repeats = 0; + int *counts; + int size = table->size; + + if (!(counts = (int *)malloc(size * sizeof(int)))){ + fprintf(stderr, "malloc returns 0\n"); + exit(1); + } + + for (i = 0; i < size; i++){ + int x = 0; + hash_node *n = table->buckets[i]; + counts[i] = 0; + while (n){ + if (!x){ + x = 1; + non_empty_buckets++; + if (verbose){ + printf("bucket %2d: ", i); + } + } + if (verbose){ + printf(" %s", n->key); + } + counts[i]++; + n = n->next; + } + + total_elements += counts[i]; + if (counts[i] > max_count){ + max_count = counts[i]; + max_repeats = 1; + } + else if (counts[i] == max_count){ + max_repeats++; + } + + if (counts[i] && verbose){ + printf(" (%d)\n", counts[i]); + } + } + + printf("\n"); + printf("%d element%s in storage.\n", total_elements, total_elements == 1 ? "" : "s"); + + if (total_elements){ + printf("%d of %d (%.2f%%) buckets are in use\n", non_empty_buckets, size, + (double)100 * (double)non_empty_buckets / (double)(size)); + printf("the maximum number of elements in a bucket is %d (%d times)\n", max_count, max_repeats); + printf("average per bucket is %f\n", (double)total_elements / (double)non_empty_buckets); + printf("optimal would be %f\n", (double)total_elements / (double)(min(size, total_elements))); + } + return; +} diff --git a/lib/libc/stdlib/strtod.c b/lib/libc/stdlib/strtod.c index cd82c73..27fb499 100644 --- a/lib/libc/stdlib/strtod.c +++ b/lib/libc/stdlib/strtod.c @@ -146,6 +146,7 @@ static char sccsid[] = "@(#)strtod.c 8.1 (Berkeley) 6/4/93"; #endif #include "errno.h" +#include <ctype.h> #ifdef Bad_float_h #undef __STDC__ #ifdef IEEE_MC68k @@ -381,7 +382,7 @@ Balloc int x; Bigint *rv; - if (rv = freelist[k]) { + if ( (rv = freelist[k]) ) { freelist[k] = rv->next; } else { x = 1 << k; @@ -627,7 +628,7 @@ mult xc0 = c->x; #ifdef Pack_32 for (; xb < xbe; xb++, xc0++) { - if (y = *xb & 0xffff) { + if ( (y = *xb & 0xffff) ) { x = xa; xc = xc0; carry = 0; @@ -640,7 +641,7 @@ mult } while (x < xae); *xc = carry; } - if (y = *xb >> 16) { + if ( (y = *xb >> 16) ) { x = xa; xc = xc0; carry = 0; @@ -689,7 +690,7 @@ pow5mult int i; static int p05[3] = { 5, 25, 125 }; - if (i = k & 3) + if ( (i = k & 3) ) b = multadd(b, p05[i-1], 0); if (!(k >>= 2)) @@ -751,7 +752,7 @@ lshift *x1++ = *x << k | z; z = *x++ >> k1; } while (x < xe); - if (*x1 = z) + if ( (*x1 = z) ) ++n1; } #else @@ -917,7 +918,7 @@ ulp } else { word0(a) = 0; L -= Exp_shift; - word1(a) = L >= 31 ? 1 : 1 << 31 - L; + word1(a) = L >= 31 ? 1 : 1 << (31 - L); } } #endif @@ -952,16 +953,16 @@ b2d *e = 32 - k; #ifdef Pack_32 if (k < Ebits) { - d0 = Exp_1 | y >> Ebits - k; + d0 = Exp_1 | (y >> (Ebits - k)); w = xa > xa0 ? *--xa : 0; - d1 = y << (32-Ebits) + k | w >> Ebits - k; + d1 = (y << ((32-Ebits) + k)) | (w >> (Ebits - k)); goto ret_d; } z = xa > xa0 ? *--xa : 0; if (k -= Ebits) { - d0 = Exp_1 | y << k | z >> 32 - k; + d0 = Exp_1 | (y << k) | (z >> (32 - k)); y = xa > xa0 ? *--xa : 0; - d1 = z << k | y >> 32 - k; + d1 = (z << k) | (y >> (32 - k)); } else { d0 = Exp_1 | y; d1 = z; @@ -1028,13 +1029,13 @@ d2b z |= Exp_msk11; #endif #else - if (de = (int)(d0 >> Exp_shift)) + if ( (de = (int)(d0 >> Exp_shift)) ) z |= Exp_msk1; #endif #ifdef Pack_32 - if (y = d1) { - if (k = lo0bits(&y)) { - x[0] = y | z << 32 - k; + if ( (y = d1) ) { + if ( (k = lo0bits(&y)) ) { + x[0] = y | (z << (32 - k)); z >>= k; } else @@ -1212,14 +1213,9 @@ strtod case 0: s = s00; goto ret; - case '\t': - case '\n': - case '\v': - case '\f': - case '\r': - case ' ': - continue; default: + if (isspace((unsigned char)*s)) + continue; goto break2; } break2: @@ -1375,9 +1371,9 @@ strtod /* Get starting approximation = rv * 10**e1 */ if (e1 > 0) { - if (i = e1 & 15) + if ( (i = e1 & 15) ) rv *= tens[i]; - if (e1 &= ~15) { + if ( (e1 &= ~15) ) { if (e1 > DBL_MAX_10_EXP) { ovfl: errno = ERANGE; @@ -1417,9 +1413,9 @@ strtod } } else if (e1 < 0) { e1 = -e1; - if (i = e1 & 15) + if ( (i = e1 & 15) ) rv /= tens[i]; - if (e1 &= ~15) { + if ( (e1 &= ~15) ) { e1 >>= 4; for (j = 0; e1 > 1; j++, e1 >>= 1) if (e1 & 1) @@ -1950,13 +1946,13 @@ __dtoa #ifdef Sudden_Underflow i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1)); #else - if (i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1))) { + if ( (i = (int)((word0(d) >> Exp_shift1) & (Exp_mask>>Exp_shift1))) ) { #endif d2 = d; word0(d2) &= Frac_mask1; word0(d2) |= Exp_11; #ifdef IBM - if (j = 11 - hi0bits(word0(d2) & Frac_mask)) + if ( (j = 11 - hi0bits(word0(d2) & Frac_mask)) ) d2 /= 1 << j; #endif @@ -1993,8 +1989,8 @@ __dtoa /* d is denormalized */ i = bbits + be + (Bias + (P-1) - 1); - x = i > 32 ? word0(d) << 64 - i | word1(d) >> i - 32 - : word1(d) << 32 - i; + x = i > 32 ? ((word0(d) << (64 - i)) | (word1(d) >> (i - 32))) + : (word1(d) << (32 - i)); d2 = x; word0(d2) -= 31*Exp_msk1; /* adjust exponent */ i -= (Bias + (P-1) - 1) + 1; @@ -2091,7 +2087,7 @@ __dtoa ds *= bigtens[i]; } d /= ds; - } else if (j1 = -k) { + } else if ( (j1 = -k) ) { d *= tens[j1 & 0xf]; for (j = j1 >> 4; j; j >>= 1, i++) if (j & 1) { @@ -2190,7 +2186,7 @@ __dtoa *s++ = '0' + (int)L; if (i == ilim) { d += d; - if (d > ds || d == ds && L & 1) { + if (d > ds || (d == ds && L & 1)) { bump_up: while (*--s == '9') if (s == s0) { @@ -2254,7 +2250,7 @@ __dtoa Bfree(b); b = b1; } - if (j = b5 - m5) + if ( (j = b5 - m5) ) b = pow5mult(b, j); } else b = pow5mult(b, b5); @@ -2287,10 +2283,10 @@ __dtoa * can do shifts and ors to compute the numerator for q. */ #ifdef Pack_32 - if (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0x1f) + if ( (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0x1f) ) i = 32 - i; #else - if (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0xf) + if ( (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0xf) ) i = 16 - i; #endif if (i > 4) { @@ -2363,15 +2359,15 @@ __dtoa goto ret; } #endif - if (j < 0 || j == 0 && !mode + if (j < 0 || (j == 0 && !mode #ifndef ROUND_BIASED && !(word1(d) & 1) #endif - ) { + )) { if (j1 > 0) { b = lshift(b, 1); j1 = cmp(b, S); - if ((j1 > 0 || j1 == 0 && dig & 1) + if ((j1 > 0 || (j1 == 0 && dig & 1)) && dig++ == '9') goto round_9_up; } @@ -2410,7 +2406,7 @@ __dtoa b = lshift(b, 1); j = cmp(b, S); - if (j > 0 || j == 0 && dig & 1) { + if (j > 0 || (j == 0 && dig & 1)) { roundoff: while (*--s == '9') if (s == s0) { diff --git a/lib/libc/stdlib/strtol.c b/lib/libc/stdlib/strtol.c index 1a7f7b3..18e3972 100644 --- a/lib/libc/stdlib/strtol.c +++ b/lib/libc/stdlib/strtol.c @@ -55,7 +55,7 @@ strtol(nptr, endptr, base) { register const char *s = nptr; register unsigned long acc; - register int c; + register unsigned char c; register unsigned long cutoff; register int neg = 0, any, cutlim; @@ -102,6 +102,8 @@ strtol(nptr, endptr, base) cutlim = cutoff % (unsigned long)base; cutoff /= (unsigned long)base; for (acc = 0, any = 0;; c = *s++) { + if (!isascii(c)) + break; if (isdigit(c)) c -= '0'; else if (isalpha(c)) @@ -110,7 +112,7 @@ strtol(nptr, endptr, base) break; if (c >= base) break; - if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim)) any = -1; else { any = 1; diff --git a/lib/libc/stdlib/strtoll.c b/lib/libc/stdlib/strtoll.c new file mode 100644 index 0000000..2666749 --- /dev/null +++ b/lib/libc/stdlib/strtoll.c @@ -0,0 +1,138 @@ +/*- + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtoq.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> + +#include <limits.h> +#include <errno.h> +#include <ctype.h> +#include <stdlib.h> + +/* + * Convert a string to a quad integer. + * + * Ignores `locale' stuff. Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +quad_t +strtoq(nptr, endptr, base) + const char *nptr; + char **endptr; + register int base; +{ + register const char *s; + register u_quad_t acc; + register unsigned char c; + register u_quad_t qbase, cutoff; + register int neg, any, cutlim; + + /* + * Skip white space and pick up leading +/- sign if any. + * If base is 0, allow 0x for hex and 0 for octal, else + * assume decimal; if base is already 16, allow 0x. + */ + s = nptr; + do { + c = *s++; + } while (isspace(c)); + if (c == '-') { + neg = 1; + c = *s++; + } else { + neg = 0; + if (c == '+') + c = *s++; + } + if ((base == 0 || base == 16) && + c == '0' && (*s == 'x' || *s == 'X')) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + + /* + * Compute the cutoff value between legal numbers and illegal + * numbers. That is the largest legal value, divided by the + * base. An input number that is greater than this value, if + * followed by a legal input character, is too big. One that + * is equal to this value may be valid or not; the limit + * between valid and invalid numbers is then based on the last + * digit. For instance, if the range for quads is + * [-9223372036854775808..9223372036854775807] and the input base + * is 10, cutoff will be set to 922337203685477580 and cutlim to + * either 7 (neg==0) or 8 (neg==1), meaning that if we have + * accumulated a value > 922337203685477580, or equal but the + * next digit is > 7 (or 8), the number is too big, and we will + * return a range error. + * + * Set any if any `digits' consumed; make it negative to indicate + * overflow. + */ + qbase = (unsigned)base; + cutoff = neg ? -(u_quad_t)QUAD_MIN : QUAD_MAX; + cutlim = cutoff % qbase; + cutoff /= qbase; + for (acc = 0, any = 0;; c = *s++) { + if (!isascii(c)) + break; + if (isdigit(c)) + c -= '0'; + else if (isalpha(c)) + c -= isupper(c) ? 'A' - 10 : 'a' - 10; + else + break; + if (c >= base) + break; + if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim)) + any = -1; + else { + any = 1; + acc *= qbase; + acc += c; + } + } + if (any < 0) { + acc = neg ? QUAD_MIN : QUAD_MAX; + errno = ERANGE; + } else if (neg) + acc = -acc; + if (endptr != 0) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/lib/libc/stdlib/strtoq.c b/lib/libc/stdlib/strtoq.c index b31cca4..2666749 100644 --- a/lib/libc/stdlib/strtoq.c +++ b/lib/libc/stdlib/strtoq.c @@ -56,7 +56,7 @@ strtoq(nptr, endptr, base) { register const char *s; register u_quad_t acc; - register int c; + register unsigned char c; register u_quad_t qbase, cutoff; register int neg, any, cutlim; @@ -109,6 +109,8 @@ strtoq(nptr, endptr, base) cutlim = cutoff % qbase; cutoff /= qbase; for (acc = 0, any = 0;; c = *s++) { + if (!isascii(c)) + break; if (isdigit(c)) c -= '0'; else if (isalpha(c)) @@ -117,7 +119,7 @@ strtoq(nptr, endptr, base) break; if (c >= base) break; - if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim)) any = -1; else { any = 1; diff --git a/lib/libc/stdlib/strtoul.c b/lib/libc/stdlib/strtoul.c index e60556c0..304150a 100644 --- a/lib/libc/stdlib/strtoul.c +++ b/lib/libc/stdlib/strtoul.c @@ -54,7 +54,7 @@ strtoul(nptr, endptr, base) { register const char *s = nptr; register unsigned long acc; - register int c; + register unsigned char c; register unsigned long cutoff; register int neg = 0, any, cutlim; @@ -80,6 +80,8 @@ strtoul(nptr, endptr, base) cutoff = (unsigned long)ULONG_MAX / (unsigned long)base; cutlim = (unsigned long)ULONG_MAX % (unsigned long)base; for (acc = 0, any = 0;; c = *s++) { + if (!isascii(c)) + break; if (isdigit(c)) c -= '0'; else if (isalpha(c)) @@ -88,7 +90,7 @@ strtoul(nptr, endptr, base) break; if (c >= base) break; - if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim)) any = -1; else { any = 1; diff --git a/lib/libc/stdlib/strtoull.c b/lib/libc/stdlib/strtoull.c new file mode 100644 index 0000000..7656a3c --- /dev/null +++ b/lib/libc/stdlib/strtoull.c @@ -0,0 +1,116 @@ +/*- + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtouq.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> + +#include <limits.h> +#include <errno.h> +#include <ctype.h> +#include <stdlib.h> + +/* + * Convert a string to an unsigned quad integer. + * + * Ignores `locale' stuff. Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +u_quad_t +strtouq(nptr, endptr, base) + const char *nptr; + char **endptr; + register int base; +{ + register const char *s = nptr; + register u_quad_t acc; + register unsigned char c; + register u_quad_t qbase, cutoff; + register int neg, any, cutlim; + + /* + * See strtoq for comments as to the logic used. + */ + s = nptr; + do { + c = *s++; + } while (isspace(c)); + if (c == '-') { + neg = 1; + c = *s++; + } else { + neg = 0; + if (c == '+') + c = *s++; + } + if ((base == 0 || base == 16) && + c == '0' && (*s == 'x' || *s == 'X')) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + qbase = (unsigned)base; + cutoff = (u_quad_t)UQUAD_MAX / qbase; + cutlim = (u_quad_t)UQUAD_MAX % qbase; + for (acc = 0, any = 0;; c = *s++) { + if (!isascii(c)) + break; + if (isdigit(c)) + c -= '0'; + else if (isalpha(c)) + c -= isupper(c) ? 'A' - 10 : 'a' - 10; + else + break; + if (c >= base) + break; + if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim)) + any = -1; + else { + any = 1; + acc *= qbase; + acc += c; + } + } + if (any < 0) { + acc = UQUAD_MAX; + errno = ERANGE; + } else if (neg) + acc = -acc; + if (endptr != 0) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/lib/libc/stdlib/strtouq.c b/lib/libc/stdlib/strtouq.c index cc62a07..7656a3c 100644 --- a/lib/libc/stdlib/strtouq.c +++ b/lib/libc/stdlib/strtouq.c @@ -56,7 +56,7 @@ strtouq(nptr, endptr, base) { register const char *s = nptr; register u_quad_t acc; - register int c; + register unsigned char c; register u_quad_t qbase, cutoff; register int neg, any, cutlim; @@ -70,7 +70,7 @@ strtouq(nptr, endptr, base) if (c == '-') { neg = 1; c = *s++; - } else { + } else { neg = 0; if (c == '+') c = *s++; @@ -87,6 +87,8 @@ strtouq(nptr, endptr, base) cutoff = (u_quad_t)UQUAD_MAX / qbase; cutlim = (u_quad_t)UQUAD_MAX % qbase; for (acc = 0, any = 0;; c = *s++) { + if (!isascii(c)) + break; if (isdigit(c)) c -= '0'; else if (isalpha(c)) @@ -95,7 +97,7 @@ strtouq(nptr, endptr, base) break; if (c >= base) break; - if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim)) any = -1; else { any = 1; diff --git a/lib/libc/stdlib/system.3 b/lib/libc/stdlib/system.3 index d89c79e..9b82e7b 100644 --- a/lib/libc/stdlib/system.3 +++ b/lib/libc/stdlib/system.3 @@ -76,7 +76,7 @@ The .Fn system function returns the exit status of the shell, or \-1 if the -.Xr wait 3 +.Xr wait 2 for the shell failed. A return value of 127 means the execution of the shell failed. @@ -91,3 +91,6 @@ The function conforms to .St -ansiC . +and is expected to be +.St -p1003.2 +compatible. diff --git a/lib/libc/stdlib/system.c b/lib/libc/stdlib/system.c index c438f17..00db7d6 100644 --- a/lib/libc/stdlib/system.c +++ b/lib/libc/stdlib/system.c @@ -42,35 +42,51 @@ static char sccsid[] = "@(#)system.c 8.1 (Berkeley) 6/4/93"; #include <stddef.h> #include <unistd.h> #include <paths.h> +#include <errno.h> -system(command) +int system(command) const char *command; { - union wait pstat; pid_t pid; - int omask; - sig_t intsave, quitsave; + int pstat; + struct sigaction ign, intact, quitact; + sigset_t newsigblock, oldsigblock; if (!command) /* just checking... */ return(1); - omask = sigblock(sigmask(SIGCHLD)); - switch(pid = vfork()) { + /* + * Ignore SIGINT and SIGQUIT, block SIGCHLD. Remember to save + * existing signal dispositions. + */ + ign.sa_handler = SIG_IGN; + (void)sigemptyset(&ign.sa_mask); + ign.sa_flags = 0; + (void)sigaction(SIGINT, &ign, &intact); + (void)sigaction(SIGQUIT, &ign, &quitact); + (void)sigemptyset(&newsigblock); + (void)sigaddset(&newsigblock, SIGCHLD); + (void)sigprocmask(SIG_BLOCK, &newsigblock, &oldsigblock); + switch(pid = fork()) { case -1: /* error */ - (void)sigsetmask(omask); - pstat.w_status = 0; - pstat.w_retcode = 127; - return(pstat.w_status); + break; case 0: /* child */ - (void)sigsetmask(omask); + /* + * Restore original signal dispositions and exec the command. + */ + (void)sigaction(SIGINT, &intact, NULL); + (void)sigaction(SIGQUIT, &quitact, NULL); + (void)sigprocmask(SIG_SETMASK, &oldsigblock, NULL); execl(_PATH_BSHELL, "sh", "-c", command, (char *)NULL); _exit(127); + default: /* parent */ + do { + pid = waitpid(pid, &pstat, 0); + } while (pid == -1 && errno == EINTR); + break; } - intsave = signal(SIGINT, SIG_IGN); - quitsave = signal(SIGQUIT, SIG_IGN); - pid = waitpid(pid, (int *)&pstat, 0); - (void)sigsetmask(omask); - (void)signal(SIGINT, intsave); - (void)signal(SIGQUIT, quitsave); - return(pid == -1 ? -1 : pstat.w_status); + (void)sigaction(SIGINT, &intact, NULL); + (void)sigaction(SIGQUIT, &quitact, NULL); + (void)sigprocmask(SIG_SETMASK, &oldsigblock, NULL); + return(pid == -1 ? -1 : pstat); } |
