diff options
Diffstat (limited to 'security/nss/lib/dbm/src')
| -rw-r--r-- | security/nss/lib/dbm/src/Makefile | 48 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/config.mk | 33 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/db.c | 134 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/dirent.c | 344 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/dirent.h | 97 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/h_bigkey.c | 707 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/h_func.c | 207 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/h_log2.c | 54 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/h_page.c | 1252 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/hash.c | 1172 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/hash_buf.c | 407 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/manifest.mn | 28 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/memmove.c | 146 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/mktemp.c | 149 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/snprintf.c | 50 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/src.gyp | 40 | ||||
| -rw-r--r-- | security/nss/lib/dbm/src/strerror.c | 73 |
17 files changed, 4941 insertions, 0 deletions
diff --git a/security/nss/lib/dbm/src/Makefile b/security/nss/lib/dbm/src/Makefile new file mode 100644 index 000000000..862544362 --- /dev/null +++ b/security/nss/lib/dbm/src/Makefile @@ -0,0 +1,48 @@ +#! gmake +# +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +####################################################################### +# (1) Include initial platform-independent assignments (MANDATORY). # +####################################################################### + +include manifest.mn + +####################################################################### +# (2) Include "global" configuration information. (OPTIONAL) # +####################################################################### + +include $(CORE_DEPTH)/coreconf/config.mk + +####################################################################### +# (3) Include "component" configuration information. (OPTIONAL) # +####################################################################### + +include $(CORE_DEPTH)/lib/dbm/config/config.mk + +####################################################################### +# (4) Include "local" platform-dependent assignments (OPTIONAL). # +####################################################################### + +include config.mk + +####################################################################### +# (5) Execute "global" rules. (OPTIONAL) # +####################################################################### + +include $(CORE_DEPTH)/coreconf/rules.mk + +####################################################################### +# (6) Execute "component" rules. (OPTIONAL) # +####################################################################### + + + +####################################################################### +# (7) Execute "local" rules. (OPTIONAL). # +####################################################################### + + + diff --git a/security/nss/lib/dbm/src/config.mk b/security/nss/lib/dbm/src/config.mk new file mode 100644 index 000000000..eab180540 --- /dev/null +++ b/security/nss/lib/dbm/src/config.mk @@ -0,0 +1,33 @@ +#! gmake +# +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +DEFINES += -DMEMMOVE -D__DBINTERFACE_PRIVATE + +# +# Currently, override TARGETS variable so that only static libraries +# are specifed as dependencies within rules.mk. +# + +TARGETS = $(LIBRARY) +SHARED_LIBRARY = +IMPORT_LIBRARY = +PURE_LIBRARY = +PROGRAM = + +ifdef SHARED_LIBRARY + ifeq (,$(filter-out WIN%,$(OS_TARGET))) + DLLBASE=/BASE:0x30000000 + RES=$(OBJDIR)/dbm.res + RESNAME=../include/dbm.rc + endif + ifeq ($(DLL_SUFFIX),dll) + DEFINES += -D_DLL + endif +endif + +ifeq ($(OS_TARGET),AIX) + OS_LIBS += -lc_r +endif diff --git a/security/nss/lib/dbm/src/db.c b/security/nss/lib/dbm/src/db.c new file mode 100644 index 000000000..5c35bbd48 --- /dev/null +++ b/security/nss/lib/dbm/src/db.c @@ -0,0 +1,134 @@ +/*- + * Copyright (c) 1991, 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)db.c 8.4 (Berkeley) 2/21/94"; +#endif /* LIBC_SCCS and not lint */ + +#ifndef __DBINTERFACE_PRIVATE +#define __DBINTERFACE_PRIVATE +#endif +#ifdef macintosh +#include <unix.h> +#else +#include <sys/types.h> +#endif + +#include <errno.h> +#include <fcntl.h> +#include <stddef.h> +#include <stdio.h> + +#include "mcom_db.h" + +/* a global flag that locks closed all databases */ +int all_databases_locked_closed = 0; + +/* set or unset a global lock flag to disable the + * opening of any DBM file + */ +void +dbSetOrClearDBLock(DBLockFlagEnum type) +{ + if (type == LockOutDatabase) + all_databases_locked_closed = 1; + else + all_databases_locked_closed = 0; +} + +DB * +dbopen(const char *fname, int flags, int mode, DBTYPE type, const void *openinfo) +{ + + /* lock out all file databases. Let in-memory databases through + */ + if (all_databases_locked_closed && fname) { + errno = EINVAL; + return (NULL); + } + +#define DB_FLAGS (DB_LOCK | DB_SHMEM | DB_TXN) + +#if 0 /* most systems don't have EXLOCK and SHLOCK */ +#define USE_OPEN_FLAGS \ + (O_CREAT | O_EXCL | O_EXLOCK | O_NONBLOCK | O_RDONLY | \ + O_RDWR | O_SHLOCK | O_TRUNC) +#else +#define USE_OPEN_FLAGS \ + (O_CREAT | O_EXCL | O_RDONLY | \ + O_RDWR | O_TRUNC) +#endif + + if ((flags & ~(USE_OPEN_FLAGS | DB_FLAGS)) == 0) + switch (type) { +/* we don't need btree and recno right now */ +#if 0 + case DB_BTREE: + return (__bt_open(fname, flags & USE_OPEN_FLAGS, + mode, openinfo, flags & DB_FLAGS)); + case DB_RECNO: + return (__rec_open(fname, flags & USE_OPEN_FLAGS, + mode, openinfo, flags & DB_FLAGS)); +#endif + + case DB_HASH: + return (__hash_open(fname, flags & USE_OPEN_FLAGS, + mode, (const HASHINFO *)openinfo, flags & DB_FLAGS)); + default: + break; + } + errno = EINVAL; + return (NULL); +} + +static int +__dberr() +{ + return (RET_ERROR); +} + +/* + * __DBPANIC -- Stop. + * + * Parameters: + * dbp: pointer to the DB structure. + */ +void +__dbpanic(DB *dbp) +{ + /* The only thing that can succeed is a close. */ + dbp->del = (int (*)(const struct __db *, const DBT *, uint))__dberr; + dbp->fd = (int (*)(const struct __db *))__dberr; + dbp->get = (int (*)(const struct __db *, const DBT *, DBT *, uint))__dberr; + dbp->put = (int (*)(const struct __db *, DBT *, const DBT *, uint))__dberr; + dbp->seq = (int (*)(const struct __db *, DBT *, DBT *, uint))__dberr; + dbp->sync = (int (*)(const struct __db *, uint))__dberr; +} diff --git a/security/nss/lib/dbm/src/dirent.c b/security/nss/lib/dbm/src/dirent.c new file mode 100644 index 000000000..da3e83e5c --- /dev/null +++ b/security/nss/lib/dbm/src/dirent.c @@ -0,0 +1,344 @@ +#ifdef OS2 + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <ctype.h> + +#include <dirent.h> +#include <errno.h> + +/*#ifndef __EMX__ +#include <libx.h> +#endif */ + +#define INCL_DOSFILEMGR +#define INCL_DOSERRORS +#include <os2.h> + +#if OS2 >= 2 +#define FFBUF FILEFINDBUF3 +#define Word ULONG +/* + * LS20 recommends a request count of 100, but according to the + * APAR text it does not lead to missing files, just to funny + * numbers of returned entries. + * + * LS30 HPFS386 requires a count greater than 2, or some files + * are missing (those starting with a character less that '.'). + * + * Novell loses entries which overflow the buffer. In previous + * versions of dirent2, this could have lead to missing files + * when the average length of 100 directory entries was 40 bytes + * or more (quite unlikely for files on a Novell server). + * + * Conclusion: Make sure that the entries all fit into the buffer + * and that the buffer is large enough for more than 2 entries + * (each entry is at most 300 bytes long). And ignore the LS20 + * effect. + */ +#define Count 25 +#define BufSz (25 * (sizeof(FILEFINDBUF3) + 1)) +#else +#define FFBUF FILEFINDBUF +#define Word USHORT +#define BufSz 1024 +#define Count 3 +#endif + +#if defined(__IBMC__) || defined(__IBMCPP__) +#define error(rc) _doserrno = rc, errno = EOS2ERR +#elif defined(MICROSOFT) +#define error(rc) _doserrno = rc, errno = 255 +#else +#define error(rc) errno = 255 +#endif + +struct _dirdescr { + HDIR handle; /* DosFindFirst handle */ + char fstype; /* filesystem type */ + Word count; /* valid entries in <ffbuf> */ + long number; /* absolute number of next entry */ + int index; /* relative number of next entry */ + FFBUF *next; /* pointer to next entry */ + char name[MAXPATHLEN + 3]; /* directory name */ + unsigned attrmask; /* attribute mask for seekdir */ + struct dirent entry; /* buffer for directory entry */ + BYTE ffbuf[BufSz]; +}; + +/* + * Return first char of filesystem type, or 0 if unknown. + */ +static char +getFSType(const char *path) +{ + static char cache[1 + 26]; + char drive[3], info[512]; + Word unit, infolen; + char r; + + if (isalpha(path[0]) && path[1] == ':') { + unit = toupper(path[0]) - '@'; + path += 2; + } else { + ULONG driveMap; +#if OS2 >= 2 + if (DosQueryCurrentDisk(&unit, &driveMap)) +#else + if (DosQCurDisk(&unit, &driveMap)) +#endif + return 0; + } + + if ((path[0] == '\\' || path[0] == '/') && + (path[1] == '\\' || path[1] == '/')) + return 0; + + if (cache[unit]) + return cache[unit]; + + drive[0] = '@' + unit; + drive[1] = ':'; + drive[2] = '\0'; + infolen = sizeof info; +#if OS2 >= 2 + if (DosQueryFSAttach(drive, 0, FSAIL_QUERYNAME, (PVOID)info, &infolen)) + return 0; + if (infolen >= sizeof(FSQBUFFER2)) { + FSQBUFFER2 *p = (FSQBUFFER2 *)info; + r = p->szFSDName[p->cbName]; + } else +#else + if (DosQFSAttach((PSZ)drive, 0, FSAIL_QUERYNAME, (PVOID)info, &infolen, 0)) + return 0; + if (infolen >= 9) { + char *p = info + sizeof(USHORT); + p += sizeof(USHORT) + *(USHORT *)p + 1 + sizeof(USHORT); + r = *p; + } else +#endif + r = 0; + return cache[unit] = r; +} + +char * +abs_path(const char *name, char *buffer, int len) +{ + char buf[4]; + if (isalpha(name[0]) && name[1] == ':' && name[2] == '\0') { + buf[0] = name[0]; + buf[1] = name[1]; + buf[2] = '.'; + buf[3] = '\0'; + name = buf; + } +#if OS2 >= 2 + if (DosQueryPathInfo((PSZ)name, FIL_QUERYFULLNAME, buffer, len)) +#else + if (DosQPathInfo((PSZ)name, FIL_QUERYFULLNAME, (PBYTE)buffer, len, 0L)) +#endif + return NULL; + return buffer; +} + +DIR * +openxdir(const char *path, unsigned att_mask) +{ + DIR *dir; + char name[MAXPATHLEN + 3]; + Word rc; + + dir = malloc(sizeof(DIR)); + if (dir == NULL) { + errno = ENOMEM; + return NULL; + } + + strncpy(name, path, MAXPATHLEN); + name[MAXPATHLEN] = '\0'; + switch (name[strlen(name) - 1]) { + default: + strcat(name, "\\"); + case '\\': + case '/': + case ':':; + } + strcat(name, "."); + if (!abs_path(name, dir->name, MAXPATHLEN + 1)) + strcpy(dir->name, name); + if (dir->name[strlen(dir->name) - 1] == '\\') + strcat(dir->name, "*"); + else + strcat(dir->name, "\\*"); + + dir->fstype = getFSType(dir->name); + dir->attrmask = att_mask | A_DIR; + + dir->handle = HDIR_CREATE; + dir->count = 100; +#if OS2 >= 2 + rc = DosFindFirst(dir->name, &dir->handle, dir->attrmask, + dir->ffbuf, sizeof dir->ffbuf, &dir->count, FIL_STANDARD); +#else + rc = DosFindFirst((PSZ)dir->name, &dir->handle, dir->attrmask, + (PFILEFINDBUF)dir->ffbuf, sizeof dir->ffbuf, &dir->count, 0); +#endif + switch (rc) { + default: + free(dir); + error(rc); + return NULL; + case NO_ERROR: + case ERROR_NO_MORE_FILES:; + } + + dir->number = 0; + dir->index = 0; + dir->next = (FFBUF *)dir->ffbuf; + + return (DIR *)dir; +} + +DIR * +opendir(const char *pathname) +{ + return openxdir(pathname, 0); +} + +struct dirent * +readdir(DIR *dir) +{ + static int dummy_ino = 2; + + if (dir->index == dir->count) { + Word rc; + dir->count = 100; +#if OS2 >= 2 + rc = DosFindNext(dir->handle, dir->ffbuf, + sizeof dir->ffbuf, &dir->count); +#else + rc = DosFindNext(dir->handle, (PFILEFINDBUF)dir->ffbuf, + sizeof dir->ffbuf, &dir->count); +#endif + if (rc) { + error(rc); + return NULL; + } + + dir->index = 0; + dir->next = (FFBUF *)dir->ffbuf; + } + + if (dir->index == dir->count) + return NULL; + + memcpy(dir->entry.d_name, dir->next->achName, dir->next->cchName); + dir->entry.d_name[dir->next->cchName] = '\0'; + dir->entry.d_ino = dummy_ino++; + dir->entry.d_reclen = dir->next->cchName; + dir->entry.d_namlen = dir->next->cchName; + dir->entry.d_size = dir->next->cbFile; + dir->entry.d_attribute = dir->next->attrFile; + dir->entry.d_time = *(USHORT *)&dir->next->ftimeLastWrite; + dir->entry.d_date = *(USHORT *)&dir->next->fdateLastWrite; + + switch (dir->fstype) { + case 'F': /* FAT */ + case 'C': /* CDFS */ + if (dir->next->attrFile & FILE_DIRECTORY) + strupr(dir->entry.d_name); + else + strlwr(dir->entry.d_name); + } + +#if OS2 >= 2 + dir->next = (FFBUF *)((BYTE *)dir->next + dir->next->oNextEntryOffset); +#else + dir->next = (FFBUF *)((BYTE *)dir->next->achName + dir->next->cchName + 1); +#endif + ++dir->number; + ++dir->index; + + return &dir->entry; +} + +long +telldir(DIR *dir) +{ + return dir->number; +} + +void +seekdir(DIR *dir, long off) +{ + if (dir->number > off) { + char name[MAXPATHLEN + 2]; + Word rc; + + DosFindClose(dir->handle); + + strcpy(name, dir->name); + strcat(name, "*"); + + dir->handle = HDIR_CREATE; + dir->count = 32767; +#if OS2 >= 2 + rc = DosFindFirst(name, &dir->handle, dir->attrmask, + dir->ffbuf, sizeof dir->ffbuf, &dir->count, FIL_STANDARD); +#else + rc = DosFindFirst((PSZ)name, &dir->handle, dir->attrmask, + (PFILEFINDBUF)dir->ffbuf, sizeof dir->ffbuf, &dir->count, 0); +#endif + switch (rc) { + default: + error(rc); + return; + case NO_ERROR: + case ERROR_NO_MORE_FILES:; + } + + dir->number = 0; + dir->index = 0; + dir->next = (FFBUF *)dir->ffbuf; + } + + while (dir->number < off && readdir(dir)) + ; +} + +void +closedir(DIR *dir) +{ + DosFindClose(dir->handle); + free(dir); +} + +/*****************************************************************************/ + +#ifdef TEST + +main(int argc, char **argv) +{ + int i; + DIR *dir; + struct dirent *ep; + + for (i = 1; i < argc; ++i) { + dir = opendir(argv[i]); + if (!dir) + continue; + while (ep = readdir(dir)) + if (strchr("\\/:", argv[i][strlen(argv[i]) - 1])) + printf("%s%s\n", argv[i], ep->d_name); + else + printf("%s/%s\n", argv[i], ep->d_name); + closedir(dir); + } + + return 0; +} + +#endif + +#endif /* OS2 */ diff --git a/security/nss/lib/dbm/src/dirent.h b/security/nss/lib/dbm/src/dirent.h new file mode 100644 index 000000000..0b4ae5dd2 --- /dev/null +++ b/security/nss/lib/dbm/src/dirent.h @@ -0,0 +1,97 @@ +#ifndef __DIRENT_H__ +#define __DIRENT_H__ +/* + * @(#)msd_dir.h 1.4 87/11/06 Public Domain. + * + * A public domain implementation of BSD directory routines for + * MS-DOS. Written by Michael Rendell ({uunet,utai}michael@garfield), + * August 1897 + * + * Extended by Peter Lim (lim@mullian.oz) to overcome some MS DOS quirks + * and returns 2 more pieces of information - file size & attribute. + * Plus a little reshuffling of some #define's positions December 1987 + * + * Some modifications by Martin Junius 02-14-89 + * + * AK900712 + * AK910410 abs_path - make absolute path + * + */ + +#ifdef __EMX__ +#include <sys/param.h> +#else +#if defined(__IBMC__) || defined(__IBMCPP__) || defined(XP_W32_MSVC) +#include <stdio.h> +#ifdef MAXPATHLEN +#undef MAXPATHLEN +#endif +#define MAXPATHLEN (FILENAME_MAX * 4) +#define MAXNAMLEN FILENAME_MAX + +#else +#include <param.h> +#endif +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +/* attribute stuff */ +#ifndef A_RONLY +#define A_RONLY 0x01 +#define A_HIDDEN 0x02 +#define A_SYSTEM 0x04 +#define A_LABEL 0x08 +#define A_DIR 0x10 +#define A_ARCHIVE 0x20 +#endif + +struct dirent { +#if defined(OS2) || defined(WIN32) /* use the layout of EMX to avoid trouble */ + int d_ino; /* Dummy */ + int d_reclen; /* Dummy, same as d_namlen */ + int d_namlen; /* length of name */ + char d_name[MAXNAMLEN + 1]; + unsigned long d_size; + unsigned short d_attribute; /* attributes (see above) */ + unsigned short d_time; /* modification time */ + unsigned short d_date; /* modification date */ +#else + char d_name[MAXNAMLEN + 1]; /* garentee null termination */ + char d_attribute; /* .. extension .. */ + unsigned long d_size; /* .. extension .. */ +#endif +}; + +typedef struct _dirdescr DIR; +/* the structs do not have to be defined here */ + +extern DIR *opendir(const char *); +extern DIR *openxdir(const char *, unsigned); +extern struct dirent *readdir(DIR *); +extern void seekdir(DIR *, long); +extern long telldir(DIR *); +extern void closedir(DIR *); +#define rewinddir(dirp) seekdir(dirp, 0L) + +extern char *abs_path(const char *name, char *buffer, int len); + +#ifndef S_IFMT +#define S_IFMT (S_IFDIR | S_IFREG) +#endif + +#ifndef S_ISDIR +#define S_ISDIR(m) (((m)&S_IFMT) == S_IFDIR) +#endif + +#ifndef S_ISREG +#define S_ISREG(m) (((m)&S_IFMT) == S_IFREG) +#endif + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/security/nss/lib/dbm/src/h_bigkey.c b/security/nss/lib/dbm/src/h_bigkey.c new file mode 100644 index 000000000..6edfe7f5a --- /dev/null +++ b/security/nss/lib/dbm/src/h_bigkey.c @@ -0,0 +1,707 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94"; +#endif /* LIBC_SCCS and not lint */ + +/* + * PACKAGE: hash + * DESCRIPTION: + * Big key/data handling for the hashing package. + * + * ROUTINES: + * External + * __big_keydata + * __big_split + * __big_insert + * __big_return + * __big_delete + * __find_last_page + * Internal + * collect_key + * collect_data + */ + +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) +#include <sys/param.h> +#endif + +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#ifdef DEBUG +#include <assert.h> +#endif + +#include "mcom_db.h" +#include "hash.h" +#include "page.h" +/* #include "extern.h" */ + +static int collect_key(HTAB *, BUFHEAD *, int, DBT *, int); +static int collect_data(HTAB *, BUFHEAD *, int, int); + +/* + * Big_insert + * + * You need to do an insert and the key/data pair is too big + * + * Returns: + * 0 ==> OK + *-1 ==> ERROR + */ +extern int +__big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) +{ + register uint16 *p; + uint key_size, n, val_size; + uint16 space, move_bytes, off; + char *cp, *key_data, *val_data; + + cp = bufp->page; /* Character pointer of p. */ + p = (uint16 *)cp; + + key_data = (char *)key->data; + key_size = key->size; + val_data = (char *)val->data; + val_size = val->size; + + /* First move the Key */ + for (space = FREESPACE(p) - BIGOVERHEAD; key_size; + space = FREESPACE(p) - BIGOVERHEAD) { + move_bytes = PR_MIN(space, key_size); + off = OFFSET(p) - move_bytes; + memmove(cp + off, key_data, move_bytes); + key_size -= move_bytes; + key_data += move_bytes; + n = p[0]; + p[++n] = off; + p[0] = ++n; + FREESPACE(p) = off - PAGE_META(n); + OFFSET(p) = off; + p[n] = PARTIAL_KEY; + bufp = __add_ovflpage(hashp, bufp); + if (!bufp) + return (-1); + n = p[0]; + if (!key_size) { + if (FREESPACE(p)) { + move_bytes = PR_MIN(FREESPACE(p), val_size); + off = OFFSET(p) - move_bytes; + p[n] = off; + memmove(cp + off, val_data, move_bytes); + val_data += move_bytes; + val_size -= move_bytes; + p[n - 2] = FULL_KEY_DATA; + FREESPACE(p) = FREESPACE(p) - move_bytes; + OFFSET(p) = off; + } else + p[n - 2] = FULL_KEY; + } + p = (uint16 *)bufp->page; + cp = bufp->page; + bufp->flags |= BUF_MOD; + } + + /* Now move the data */ + for (space = FREESPACE(p) - BIGOVERHEAD; val_size; + space = FREESPACE(p) - BIGOVERHEAD) { + move_bytes = PR_MIN(space, val_size); + /* + * Here's the hack to make sure that if the data ends on the + * same page as the key ends, FREESPACE is at least one. + */ + if (space == val_size && val_size == val->size) + move_bytes--; + off = OFFSET(p) - move_bytes; + memmove(cp + off, val_data, move_bytes); + val_size -= move_bytes; + val_data += move_bytes; + n = p[0]; + p[++n] = off; + p[0] = ++n; + FREESPACE(p) = off - PAGE_META(n); + OFFSET(p) = off; + if (val_size) { + p[n] = FULL_KEY; + bufp = __add_ovflpage(hashp, bufp); + if (!bufp) + return (-1); + cp = bufp->page; + p = (uint16 *)cp; + } else + p[n] = FULL_KEY_DATA; + bufp->flags |= BUF_MOD; + } + return (0); +} + +/* + * Called when bufp's page contains a partial key (index should be 1) + * + * All pages in the big key/data pair except bufp are freed. We cannot + * free bufp because the page pointing to it is lost and we can't get rid + * of its pointer. + * + * Returns: + * 0 => OK + *-1 => ERROR + */ +extern int +__big_delete(HTAB *hashp, BUFHEAD *bufp) +{ + register BUFHEAD *last_bfp, *rbufp; + uint16 *bp, pageno; + int key_done, n; + + rbufp = bufp; + last_bfp = NULL; + bp = (uint16 *)bufp->page; + pageno = 0; + key_done = 0; + + while (!key_done || (bp[2] != FULL_KEY_DATA)) { + if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) + key_done = 1; + + /* + * If there is freespace left on a FULL_KEY_DATA page, then + * the data is short and fits entirely on this page, and this + * is the last page. + */ + if (bp[2] == FULL_KEY_DATA && FREESPACE(bp)) + break; + pageno = bp[bp[0] - 1]; + rbufp->flags |= BUF_MOD; + rbufp = __get_buf(hashp, pageno, rbufp, 0); + if (last_bfp) + __free_ovflpage(hashp, last_bfp); + last_bfp = rbufp; + if (!rbufp) + return (-1); /* Error. */ + bp = (uint16 *)rbufp->page; + } + + /* + * If we get here then rbufp points to the last page of the big + * key/data pair. Bufp points to the first one -- it should now be + * empty pointing to the next page after this pair. Can't free it + * because we don't have the page pointing to it. + */ + + /* This is information from the last page of the pair. */ + n = bp[0]; + pageno = bp[n - 1]; + + /* Now, bp is the first page of the pair. */ + bp = (uint16 *)bufp->page; + if (n > 2) { + /* There is an overflow page. */ + bp[1] = pageno; + bp[2] = OVFLPAGE; + bufp->ovfl = rbufp->ovfl; + } else + /* This is the last page. */ + bufp->ovfl = NULL; + n -= 2; + bp[0] = n; + FREESPACE(bp) = hashp->BSIZE - PAGE_META(n); + OFFSET(bp) = hashp->BSIZE - 1; + + bufp->flags |= BUF_MOD; + if (rbufp) + __free_ovflpage(hashp, rbufp); + if (last_bfp != rbufp) + __free_ovflpage(hashp, last_bfp); + + hashp->NKEYS--; + return (0); +} +/* + * Returns: + * 0 = key not found + * -1 = get next overflow page + * -2 means key not found and this is big key/data + * -3 error + */ +extern int +__find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size) +{ + register uint16 *bp; + register char *p; + int ksize; + uint16 bytes; + char *kkey; + + bp = (uint16 *)bufp->page; + p = bufp->page; + ksize = size; + kkey = key; + + for (bytes = hashp->BSIZE - bp[ndx]; + bytes <= size && bp[ndx + 1] == PARTIAL_KEY; + bytes = hashp->BSIZE - bp[ndx]) { + if (memcmp(p + bp[ndx], kkey, bytes)) + return (-2); + kkey += bytes; + ksize -= bytes; + bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0); + if (!bufp) + return (-3); + p = bufp->page; + bp = (uint16 *)p; + ndx = 1; + } + + if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) { +#ifdef HASH_STATISTICS + ++hash_collisions; +#endif + return (-2); + } else + return (ndx); +} + +/* + * Given the buffer pointer of the first overflow page of a big pair, + * find the end of the big pair + * + * This will set bpp to the buffer header of the last page of the big pair. + * It will return the pageno of the overflow page following the last page + * of the pair; 0 if there isn't any (i.e. big pair is the last key in the + * bucket) + */ +extern uint16 +__find_last_page(HTAB *hashp, BUFHEAD **bpp) +{ + BUFHEAD *bufp; + uint16 *bp, pageno; + uint n; + + bufp = *bpp; + bp = (uint16 *)bufp->page; + for (;;) { + n = bp[0]; + + /* + * This is the last page if: the tag is FULL_KEY_DATA and + * either only 2 entries OVFLPAGE marker is explicit there + * is freespace on the page. + */ + if (bp[2] == FULL_KEY_DATA && + ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp)))) + break; + + /* LJM bound the size of n to reasonable limits + */ + if (n > hashp->BSIZE / sizeof(uint16)) + return (0); + + pageno = bp[n - 1]; + bufp = __get_buf(hashp, pageno, bufp, 0); + if (!bufp) + return (0); /* Need to indicate an error! */ + bp = (uint16 *)bufp->page; + } + + *bpp = bufp; + if (bp[0] > 2) + return (bp[3]); + else + return (0); +} + +/* + * Return the data for the key/data pair that begins on this page at this + * index (index should always be 1). + */ +extern int +__big_return( + HTAB *hashp, + BUFHEAD *bufp, + int ndx, + DBT *val, + int set_current) +{ + BUFHEAD *save_p; + uint16 *bp, len, off, save_addr; + char *tp; + int save_flags; + + bp = (uint16 *)bufp->page; + while (bp[ndx + 1] == PARTIAL_KEY) { + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) + return (-1); + bp = (uint16 *)bufp->page; + ndx = 1; + } + + if (bp[ndx + 1] == FULL_KEY) { + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) + return (-1); + bp = (uint16 *)bufp->page; + save_p = bufp; + save_addr = save_p->addr; + off = bp[1]; + len = 0; + } else if (!FREESPACE(bp)) { + /* + * This is a hack. We can't distinguish between + * FULL_KEY_DATA that contains complete data or + * incomplete data, so we require that if the data + * is complete, there is at least 1 byte of free + * space left. + */ + off = bp[bp[0]]; + len = bp[1] - off; + save_p = bufp; + save_addr = bufp->addr; + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) + return (-1); + bp = (uint16 *)bufp->page; + } else { + /* The data is all on one page. */ + tp = (char *)bp; + off = bp[bp[0]]; + val->data = (uint8 *)tp + off; + val->size = bp[1] - off; + if (set_current) { + if (bp[0] == 2) { /* No more buckets in + * chain */ + hashp->cpage = NULL; + hashp->cbucket++; + hashp->cndx = 1; + } else { + hashp->cpage = __get_buf(hashp, + bp[bp[0] - 1], bufp, 0); + if (!hashp->cpage) + return (-1); + hashp->cndx = 1; + if (!((uint16 *) + hashp->cpage->page)[0]) { + hashp->cbucket++; + hashp->cpage = NULL; + } + } + } + return (0); + } + + /* pin our saved buf so that we don't lose if + * we run out of buffers */ + save_flags = save_p->flags; + save_p->flags |= BUF_PIN; + val->size = collect_data(hashp, bufp, (int)len, set_current); + save_p->flags = save_flags; + if (val->size == (size_t)-1) + return (-1); + if (save_p->addr != save_addr) { + /* We are pretty short on buffers. */ + errno = EINVAL; /* OUT OF BUFFERS */ + return (-1); + } + memmove(hashp->tmp_buf, (save_p->page) + off, len); + val->data = (uint8 *)hashp->tmp_buf; + return (0); +} + +/* + * Count how big the total datasize is by looping through the pages. Then + * allocate a buffer and copy the data in the second loop. NOTE: Our caller + * may already have a bp which it is holding onto. The caller is + * responsible for copying that bp into our temp buffer. 'len' is how much + * space to reserve for that buffer. + */ +static int +collect_data( + HTAB *hashp, + BUFHEAD *bufp, + int len, int set) +{ + register uint16 *bp; + BUFHEAD *save_bufp; + int save_flags; + int mylen, totlen; + + /* + * save the input buf head because we need to walk the list twice. + * pin it to make sure it doesn't leave the buffer pool. + * This has the effect of growing the buffer pool if necessary. + */ + save_bufp = bufp; + save_flags = save_bufp->flags; + save_bufp->flags |= BUF_PIN; + + /* read the length of the buffer */ + for (totlen = len; bufp; bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0)) { + bp = (uint16 *)bufp->page; + mylen = hashp->BSIZE - bp[1]; + + /* if mylen ever goes negative it means that the + * page is screwed up. + */ + if (mylen < 0) { + save_bufp->flags = save_flags; + return (-1); + } + totlen += mylen; + if (bp[2] == FULL_KEY_DATA) { /* End of Data */ + break; + } + } + + if (!bufp) { + save_bufp->flags = save_flags; + return (-1); + } + + /* allocate a temp buf */ + if (hashp->tmp_buf) + free(hashp->tmp_buf); + if ((hashp->tmp_buf = (char *)malloc((size_t)totlen)) == NULL) { + save_bufp->flags = save_flags; + return (-1); + } + + /* copy the buffers back into temp buf */ + for (bufp = save_bufp; bufp; + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0)) { + bp = (uint16 *)bufp->page; + mylen = hashp->BSIZE - bp[1]; + memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], (size_t)mylen); + len += mylen; + if (bp[2] == FULL_KEY_DATA) { + break; + } + } + + /* 'clear' the pin flags */ + save_bufp->flags = save_flags; + + /* update the database cursor */ + if (set) { + hashp->cndx = 1; + if (bp[0] == 2) { /* No more buckets in chain */ + hashp->cpage = NULL; + hashp->cbucket++; + } else { + hashp->cpage = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!hashp->cpage) + return (-1); + else if (!((uint16 *)hashp->cpage->page)[0]) { + hashp->cbucket++; + hashp->cpage = NULL; + } + } + } + return (totlen); +} + +/* + * Fill in the key and data for this big pair. + */ +extern int +__big_keydata( + HTAB *hashp, + BUFHEAD *bufp, + DBT *key, DBT *val, + int set) +{ + key->size = collect_key(hashp, bufp, 0, val, set); + if (key->size == (size_t)-1) + return (-1); + key->data = (uint8 *)hashp->tmp_key; + return (0); +} + +/* + * Count how big the total key size is by recursing through the pages. Then + * collect the data, allocate a buffer and copy the key as you recurse up. + */ +static int +collect_key( + HTAB *hashp, + BUFHEAD *bufp, + int len, + DBT *val, + int set) +{ + BUFHEAD *xbp; + char *p; + int mylen, totlen; + uint16 *bp, save_addr; + + p = bufp->page; + bp = (uint16 *)p; + mylen = hashp->BSIZE - bp[1]; + + save_addr = bufp->addr; + totlen = len + mylen; + if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */ + if (hashp->tmp_key != NULL) + free(hashp->tmp_key); + if ((hashp->tmp_key = (char *)malloc((size_t)totlen)) == NULL) + return (-1); + if (__big_return(hashp, bufp, 1, val, set)) + return (-1); + } else { + xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!xbp || ((totlen = + collect_key(hashp, xbp, totlen, val, set)) < 1)) + return (-1); + } + if (bufp->addr != save_addr) { + errno = EINVAL; /* MIS -- OUT OF BUFFERS */ + return (-1); + } + memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], (size_t)mylen); + return (totlen); +} + +/* + * Returns: + * 0 => OK + * -1 => error + */ +extern int +__big_split( + HTAB *hashp, + BUFHEAD *op, /* Pointer to where to put keys that go in old bucket */ + BUFHEAD *np, /* Pointer to new bucket page */ + /* Pointer to first page containing the big key/data */ + BUFHEAD *big_keyp, + uint32 addr, /* Address of big_keyp */ + uint32 obucket, /* Old Bucket */ + SPLIT_RETURN *ret) +{ + register BUFHEAD *tmpp; + register uint16 *tp; + BUFHEAD *bp; + DBT key, val; + uint32 change; + uint16 free_space, n, off; + + bp = big_keyp; + + /* Now figure out where the big key/data goes */ + if (__big_keydata(hashp, big_keyp, &key, &val, 0)) + return (-1); + change = (__call_hash(hashp, (char *)key.data, key.size) != obucket); + + if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) { + if (!(ret->nextp = + __get_buf(hashp, ret->next_addr, big_keyp, 0))) + return (-1); + ; + } else + ret->nextp = NULL; + +/* Now make one of np/op point to the big key/data pair */ +#ifdef DEBUG + assert(np->ovfl == NULL); +#endif + if (change) + tmpp = np; + else + tmpp = op; + + tmpp->flags |= BUF_MOD; +#ifdef DEBUG1 + (void)fprintf(stderr, + "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr, + (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0)); +#endif + tmpp->ovfl = bp; /* one of op/np point to big_keyp */ + tp = (uint16 *)tmpp->page; + +#if 0 /* this get's tripped on database corrupted error */ + assert(FREESPACE(tp) >= OVFLSIZE); +#endif + if (FREESPACE(tp) < OVFLSIZE) + return (DATABASE_CORRUPTED_ERROR); + + n = tp[0]; + off = OFFSET(tp); + free_space = FREESPACE(tp); + tp[++n] = (uint16)addr; + tp[++n] = OVFLPAGE; + tp[0] = n; + OFFSET(tp) = off; + FREESPACE(tp) = free_space - OVFLSIZE; + + /* + * Finally, set the new and old return values. BIG_KEYP contains a + * pointer to the last page of the big key_data pair. Make sure that + * big_keyp has no following page (2 elements) or create an empty + * following page. + */ + + ret->newp = np; + ret->oldp = op; + + tp = (uint16 *)big_keyp->page; + big_keyp->flags |= BUF_MOD; + if (tp[0] > 2) { + /* + * There may be either one or two offsets on this page. If + * there is one, then the overflow page is linked on normally + * and tp[4] is OVFLPAGE. If there are two, tp[4] contains + * the second offset and needs to get stuffed in after the + * next overflow page is added. + */ + n = tp[4]; + free_space = FREESPACE(tp); + off = OFFSET(tp); + tp[0] -= 2; + FREESPACE(tp) = free_space + OVFLSIZE; + OFFSET(tp) = off; + tmpp = __add_ovflpage(hashp, big_keyp); + if (!tmpp) + return (-1); + tp[4] = n; + } else + tmpp = big_keyp; + + if (change) + ret->newp = tmpp; + else + ret->oldp = tmpp; + return (0); +} diff --git a/security/nss/lib/dbm/src/h_func.c b/security/nss/lib/dbm/src/h_func.c new file mode 100644 index 000000000..0d8734e8b --- /dev/null +++ b/security/nss/lib/dbm/src/h_func.c @@ -0,0 +1,207 @@ +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94"; +#endif /* LIBC_SCCS and not lint */ + +#ifndef macintosh +#include <sys/types.h> +#endif +#include "mcom_db.h" +#include "hash.h" +#include "page.h" +/* #include "extern.h" */ + +#if 0 +static uint32 hash1(const void *, size_t); +static uint32 hash2(const void *, size_t); +static uint32 hash3(const void *, size_t); +#endif +static uint32 hash4(const void *, size_t); + +/* Global default hash function */ +uint32 (*__default_hash)(const void *, size_t) = hash4; + +/* + * HASH FUNCTIONS + * + * Assume that we've already split the bucket to which this key hashes, + * calculate that bucket, and check that in fact we did already split it. + * + * This came from ejb's hsearch. + */ + +#define PRIME1 37 +#define PRIME2 1048583 + +#if 0 +static uint32 +hash1(const void *keyarg, register size_t len) +{ + register const uint8 *key; + register uint32 h; + + /* Convert string to integer */ + for (key = (const uint8 *)keyarg, h = 0; len--;) + h = h * PRIME1 ^ (*key++ - ' '); + h %= PRIME2; + return (h); +} + +/* + * Phong's linear congruential hash + */ +#define dcharhash(h, c) ((h) = 0x63c63cd9 * (h) + 0x9c39c33d + (c)) + +static uint32 +hash2(const void *keyarg, size_t len) +{ + register const uint8 *e, *key; + register uint32 h; + register uint8 c; + + key = (const uint8 *)keyarg; + e = key + len; + for (h = 0; key != e;) { + c = *key++; + if (!c && key > e) + break; + dcharhash(h, c); + } + return (h); +} + +/* + * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte + * units. On the first time through the loop we get the "leftover bytes" + * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle + * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If + * this routine is heavily used enough, it's worth the ugly coding. + * + * OZ's original sdbm hash + */ +static uint32 +hash3(const void *keyarg, register size_t len) +{ + register const uint8 *key; + register size_t loop; + register uint32 h; + +#define HASHC h = *key++ + 65599 * h + + h = 0; + key = (const uint8 *)keyarg; + if (len > 0) { + loop = (len + 8 - 1) >> 3; + + switch (len & (8 - 1)) { + case 0: + do { + HASHC; + /* FALLTHROUGH */ + case 7: + HASHC; + /* FALLTHROUGH */ + case 6: + HASHC; + /* FALLTHROUGH */ + case 5: + HASHC; + /* FALLTHROUGH */ + case 4: + HASHC; + /* FALLTHROUGH */ + case 3: + HASHC; + /* FALLTHROUGH */ + case 2: + HASHC; + /* FALLTHROUGH */ + case 1: + HASHC; + } while (--loop); + } + } + return (h); +} +#endif /* 0 */ + +/* Hash function from Chris Torek. */ +static uint32 +hash4(const void *keyarg, register size_t len) +{ + register const uint8 *key; + register size_t loop; + register uint32 h; + +#define HASH4a h = (h << 5) - h + *key++; +#define HASH4b h = (h << 5) + h + *key++; +#define HASH4 HASH4b + + h = 0; + key = (const uint8 *)keyarg; + if (len > 0) { + loop = (len + 8 - 1) >> 3; + + switch (len & (8 - 1)) { + case 0: + do { + HASH4; + /* FALLTHROUGH */ + case 7: + HASH4; + /* FALLTHROUGH */ + case 6: + HASH4; + /* FALLTHROUGH */ + case 5: + HASH4; + /* FALLTHROUGH */ + case 4: + HASH4; + /* FALLTHROUGH */ + case 3: + HASH4; + /* FALLTHROUGH */ + case 2: + HASH4; + /* FALLTHROUGH */ + case 1: + HASH4; + } while (--loop); + } + } + return (h); +} diff --git a/security/nss/lib/dbm/src/h_log2.c b/security/nss/lib/dbm/src/h_log2.c new file mode 100644 index 000000000..a42b51a99 --- /dev/null +++ b/security/nss/lib/dbm/src/h_log2.c @@ -0,0 +1,54 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)hash_log2.c 8.2 (Berkeley) 5/31/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdio.h> +#ifndef macintosh +#include <sys/types.h> +#endif +#include "mcom_db.h" + +uint32 +__log2(uint32 num) +{ + register uint32 i, limit; + + limit = 1; + for (i = 0; limit < num; limit = limit << 1, i++) { + } + return (i); +} diff --git a/security/nss/lib/dbm/src/h_page.c b/security/nss/lib/dbm/src/h_page.c new file mode 100644 index 000000000..bf1252aeb --- /dev/null +++ b/security/nss/lib/dbm/src/h_page.c @@ -0,0 +1,1252 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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(unix) +#define MY_LSEEK lseek +#else +#define MY_LSEEK new_lseek +extern long new_lseek(int fd, long pos, int start); +#endif + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94"; +#endif /* LIBC_SCCS and not lint */ + +/* + * PACKAGE: hashing + * + * DESCRIPTION: + * Page manipulation for hashing package. + * + * ROUTINES: + * + * External + * __get_page + * __add_ovflpage + * Internal + * overflow_page + * open_temp + */ +#ifndef macintosh +#include <sys/types.h> +#endif + +#if defined(macintosh) +#include <unistd.h> +#endif + +#include <errno.h> +#include <fcntl.h> +#if defined(_WIN32) || defined(_WINDOWS) +#include <io.h> +#endif +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) +#include <unistd.h> +#endif + +#include <assert.h> + +#include "mcom_db.h" +#include "hash.h" +#include "page.h" +/* #include "extern.h" */ + +extern int mkstempflags(char *path, int extraFlags); + +static uint32 *fetch_bitmap(HTAB *, uint32); +static uint32 first_free(uint32); +static int open_temp(HTAB *); +static uint16 overflow_page(HTAB *); +static void squeeze_key(uint16 *, const DBT *, const DBT *); +static int ugly_split(HTAB *, uint32, BUFHEAD *, BUFHEAD *, int, int); + +#define PAGE_INIT(P) \ + { \ + ((uint16 *)(P))[0] = 0; \ + ((uint16 *)(P))[1] = hashp->BSIZE - 3 * sizeof(uint16); \ + ((uint16 *)(P))[2] = hashp->BSIZE; \ + } + +/* implement a new lseek using lseek that + * writes zero's when extending a file + * beyond the end. + */ +long +new_lseek(int fd, long offset, int origin) +{ + long cur_pos = 0; + long end_pos = 0; + long seek_pos = 0; + + if (origin == SEEK_CUR) { + if (offset < 1) + return (lseek(fd, offset, SEEK_CUR)); + + cur_pos = lseek(fd, 0, SEEK_CUR); + + if (cur_pos < 0) + return (cur_pos); + } + + end_pos = lseek(fd, 0, SEEK_END); + if (end_pos < 0) + return (end_pos); + + if (origin == SEEK_SET) + seek_pos = offset; + else if (origin == SEEK_CUR) + seek_pos = cur_pos + offset; + else if (origin == SEEK_END) + seek_pos = end_pos + offset; + else { + assert(0); + return (-1); + } + + /* the seek position desired is before the + * end of the file. We don't need + * to do anything special except the seek. + */ + if (seek_pos <= end_pos) + return (lseek(fd, seek_pos, SEEK_SET)); + + /* the seek position is beyond the end of the + * file. Write zero's to the end. + * + * we are already at the end of the file so + * we just need to "write()" zeros for the + * difference between seek_pos-end_pos and + * then seek to the position to finish + * the call + */ + { + char buffer[1024]; + long len = seek_pos - end_pos; + memset(buffer, 0, 1024); + while (len > 0) { + if (write(fd, buffer, (size_t)(1024 > len ? len : 1024)) < 0) + return (-1); + len -= 1024; + } + return (lseek(fd, seek_pos, SEEK_SET)); + } +} + +/* + * This is called AFTER we have verified that there is room on the page for + * the pair (PAIRFITS has returned true) so we go right ahead and start moving + * stuff on. + */ +static void +putpair(char *p, const DBT *key, DBT *val) +{ + register uint16 *bp, n, off; + + bp = (uint16 *)p; + + /* Enter the key first. */ + n = bp[0]; + + off = OFFSET(bp) - key->size; + memmove(p + off, key->data, key->size); + bp[++n] = off; + + /* Now the data. */ + off -= val->size; + memmove(p + off, val->data, val->size); + bp[++n] = off; + + /* Adjust page info. */ + bp[0] = n; + bp[n + 1] = off - ((n + 3) * sizeof(uint16)); + bp[n + 2] = off; +} + +/* + * Returns: + * 0 OK + * -1 error + */ +extern int +__delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) +{ + register uint16 *bp, newoff; + register int n; + uint16 pairlen; + + bp = (uint16 *)bufp->page; + n = bp[0]; + + if (bp[ndx + 1] < REAL_KEY) + return (__big_delete(hashp, bufp)); + if (ndx != 1) + newoff = bp[ndx - 1]; + else + newoff = hashp->BSIZE; + pairlen = newoff - bp[ndx + 1]; + + if (ndx != (n - 1)) { + /* Hard Case -- need to shuffle keys */ + register int i; + register char *src = bufp->page + (int)OFFSET(bp); + uint32 dst_offset = (uint32)OFFSET(bp) + (uint32)pairlen; + register char *dst = bufp->page + dst_offset; + uint32 length = bp[ndx + 1] - OFFSET(bp); + + /* + * +-----------+XXX+---------+XXX+---------+---------> +infinity + * | | | | + * 0 src_offset dst_offset BSIZE + * + * Dst_offset is > src_offset, so if src_offset were bad, dst_offset + * would be too, therefore we check only dst_offset. + * + * If dst_offset is >= BSIZE, either OFFSET(bp), or pairlen, or both + * is corrupted. + * + * Once we know dst_offset is < BSIZE, we can subtract it from BSIZE + * to get an upper bound on length. + */ + if (dst_offset > (uint32)hashp->BSIZE) + return (DATABASE_CORRUPTED_ERROR); + + if (length > (uint32)(hashp->BSIZE - dst_offset)) + return (DATABASE_CORRUPTED_ERROR); + + memmove(dst, src, length); + + /* Now adjust the pointers */ + for (i = ndx + 2; i <= n; i += 2) { + if (bp[i + 1] == OVFLPAGE) { + bp[i - 2] = bp[i]; + bp[i - 1] = bp[i + 1]; + } else { + bp[i - 2] = bp[i] + pairlen; + bp[i - 1] = bp[i + 1] + pairlen; + } + } + } + /* Finally adjust the page data */ + bp[n] = OFFSET(bp) + pairlen; + bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(uint16); + bp[0] = n - 2; + hashp->NKEYS--; + + bufp->flags |= BUF_MOD; + return (0); +} +/* + * Returns: + * 0 ==> OK + * -1 ==> Error + */ +extern int +__split_page(HTAB *hashp, uint32 obucket, uint32 nbucket) +{ + register BUFHEAD *new_bufp, *old_bufp; + register uint16 *ino; + register uint16 *tmp_uint16_array; + register char *np; + DBT key, val; + uint16 n, ndx; + int retval; + uint16 copyto, diff, moved; + size_t off; + char *op; + + copyto = (uint16)hashp->BSIZE; + off = (uint16)hashp->BSIZE; + old_bufp = __get_buf(hashp, obucket, NULL, 0); + if (old_bufp == NULL) + return (-1); + new_bufp = __get_buf(hashp, nbucket, NULL, 0); + if (new_bufp == NULL) + return (-1); + + old_bufp->flags |= (BUF_MOD | BUF_PIN); + new_bufp->flags |= (BUF_MOD | BUF_PIN); + + ino = (uint16 *)(op = old_bufp->page); + np = new_bufp->page; + + moved = 0; + + for (n = 1, ndx = 1; n < ino[0]; n += 2) { + if (ino[n + 1] < REAL_KEY) { + retval = ugly_split(hashp, obucket, old_bufp, new_bufp, + (int)copyto, (int)moved); + old_bufp->flags &= ~BUF_PIN; + new_bufp->flags &= ~BUF_PIN; + return (retval); + } + key.data = (uint8 *)op + ino[n]; + + /* check here for ino[n] being greater than + * off. If it is then the database has + * been corrupted. + */ + if (ino[n] > off) + return (DATABASE_CORRUPTED_ERROR); + + key.size = off - ino[n]; + +#ifdef DEBUG + /* make sure the size is positive */ + assert(((int)key.size) > -1); +#endif + + if (__call_hash(hashp, (char *)key.data, key.size) == obucket) { + /* Don't switch page */ + diff = copyto - off; + if (diff) { + copyto = ino[n + 1] + diff; + memmove(op + copyto, op + ino[n + 1], + off - ino[n + 1]); + ino[ndx] = copyto + ino[n] - ino[n + 1]; + ino[ndx + 1] = copyto; + } else + copyto = ino[n + 1]; + ndx += 2; + } else { + /* Switch page */ + val.data = (uint8 *)op + ino[n + 1]; + val.size = ino[n] - ino[n + 1]; + + /* if the pair doesn't fit something is horribly + * wrong. LJM + */ + tmp_uint16_array = (uint16 *)np; + if (!PAIRFITS(tmp_uint16_array, &key, &val)) + return (DATABASE_CORRUPTED_ERROR); + + putpair(np, &key, &val); + moved += 2; + } + + off = ino[n + 1]; + } + + /* Now clean up the page */ + ino[0] -= moved; + FREESPACE(ino) = copyto - sizeof(uint16) * (ino[0] + 3); + OFFSET(ino) = copyto; + +#ifdef DEBUG3 + (void)fprintf(stderr, "split %d/%d\n", + ((uint16 *)np)[0] / 2, + ((uint16 *)op)[0] / 2); +#endif + /* unpin both pages */ + old_bufp->flags &= ~BUF_PIN; + new_bufp->flags &= ~BUF_PIN; + return (0); +} + +/* + * Called when we encounter an overflow or big key/data page during split + * handling. This is special cased since we have to begin checking whether + * the key/data pairs fit on their respective pages and because we may need + * overflow pages for both the old and new pages. + * + * The first page might be a page with regular key/data pairs in which case + * we have a regular overflow condition and just need to go on to the next + * page or it might be a big key/data pair in which case we need to fix the + * big key/data pair. + * + * Returns: + * 0 ==> success + * -1 ==> failure + */ + +/* the maximum number of loops we will allow UGLY split to chew + * on before we assume the database is corrupted and throw it + * away. + */ +#define MAX_UGLY_SPLIT_LOOPS 10000 + +static int +ugly_split(HTAB *hashp, uint32 obucket, BUFHEAD *old_bufp, + BUFHEAD *new_bufp, /* Same as __split_page. */ int copyto, int moved) +/* int copyto; First byte on page which contains key/data values. */ +/* int moved; Number of pairs moved to new page. */ +{ + register BUFHEAD *bufp; /* Buffer header for ino */ + register uint16 *ino; /* Page keys come off of */ + register uint16 *np; /* New page */ + register uint16 *op; /* Page keys go on to if they aren't moving */ + uint32 loop_detection = 0; + + BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ + DBT key, val; + SPLIT_RETURN ret; + uint16 n, off, ov_addr, scopyto; + char *cino; /* Character value of ino */ + int status; + + bufp = old_bufp; + ino = (uint16 *)old_bufp->page; + np = (uint16 *)new_bufp->page; + op = (uint16 *)old_bufp->page; + last_bfp = NULL; + scopyto = (uint16)copyto; /* ANSI */ + + n = ino[0] - 1; + while (n < ino[0]) { + + /* this function goes nuts sometimes and never returns. + * I havent found the problem yet but I need a solution + * so if we loop too often we assume a database curruption error + * :LJM + */ + loop_detection++; + + if (loop_detection > MAX_UGLY_SPLIT_LOOPS) + return DATABASE_CORRUPTED_ERROR; + + if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { + if ((status = __big_split(hashp, old_bufp, + new_bufp, bufp, bufp->addr, obucket, &ret))) + return (status); + old_bufp = ret.oldp; + if (!old_bufp) + return (-1); + op = (uint16 *)old_bufp->page; + new_bufp = ret.newp; + if (!new_bufp) + return (-1); + np = (uint16 *)new_bufp->page; + bufp = ret.nextp; + if (!bufp) + return (0); + cino = (char *)bufp->page; + ino = (uint16 *)cino; + last_bfp = ret.nextp; + } else if (ino[n + 1] == OVFLPAGE) { + ov_addr = ino[n]; + /* + * Fix up the old page -- the extra 2 are the fields + * which contained the overflow information. + */ + ino[0] -= (moved + 2); + FREESPACE(ino) = + scopyto - sizeof(uint16) * (ino[0] + 3); + OFFSET(ino) = scopyto; + + bufp = __get_buf(hashp, ov_addr, bufp, 0); + if (!bufp) + return (-1); + + ino = (uint16 *)bufp->page; + n = 1; + scopyto = hashp->BSIZE; + moved = 0; + + if (last_bfp) + __free_ovflpage(hashp, last_bfp); + last_bfp = bufp; + } + /* Move regular sized pairs of there are any */ + off = hashp->BSIZE; + for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { + cino = (char *)ino; + key.data = (uint8 *)cino + ino[n]; + key.size = off - ino[n]; + val.data = (uint8 *)cino + ino[n + 1]; + val.size = ino[n] - ino[n + 1]; + off = ino[n + 1]; + + if (__call_hash(hashp, (char *)key.data, key.size) == obucket) { + /* Keep on old page */ + if (PAIRFITS(op, (&key), (&val))) + putpair((char *)op, &key, &val); + else { + old_bufp = + __add_ovflpage(hashp, old_bufp); + if (!old_bufp) + return (-1); + op = (uint16 *)old_bufp->page; + putpair((char *)op, &key, &val); + } + old_bufp->flags |= BUF_MOD; + } else { + /* Move to new page */ + if (PAIRFITS(np, (&key), (&val))) + putpair((char *)np, &key, &val); + else { + new_bufp = + __add_ovflpage(hashp, new_bufp); + if (!new_bufp) + return (-1); + np = (uint16 *)new_bufp->page; + putpair((char *)np, &key, &val); + } + new_bufp->flags |= BUF_MOD; + } + } + } + if (last_bfp) + __free_ovflpage(hashp, last_bfp); + return (0); +} + +/* + * Add the given pair to the page + * + * Returns: + * 0 ==> OK + * 1 ==> failure + */ +extern int +__addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) +{ + register uint16 *bp, *sop; + int do_expand; + + bp = (uint16 *)bufp->page; + do_expand = 0; + while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) + /* Exception case */ + if (bp[2] == FULL_KEY_DATA && bp[0] == 2) + /* This is the last page of a big key/data pair + and we need to add another page */ + break; + else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) { +#ifdef DEBUG + assert(0); +#endif + return (-1); + } + bp = (uint16 *)bufp->page; + } else + /* Try to squeeze key on this page */ + if (FREESPACE(bp) > PAIRSIZE(key, val)) { + { + squeeze_key(bp, key, val); + + /* LJM: I added this because I think it was + * left out on accident. + * if this isn't incremented nkeys will not + * be the actual number of keys in the db. + */ + hashp->NKEYS++; + return (0); + } + } else { + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) { +#ifdef DEBUG + assert(0); +#endif + return (-1); + } + bp = (uint16 *)bufp->page; + } + + if (PAIRFITS(bp, key, val)) + putpair(bufp->page, key, (DBT *)val); + else { + do_expand = 1; + bufp = __add_ovflpage(hashp, bufp); + if (!bufp) { +#ifdef DEBUG + assert(0); +#endif + return (-1); + } + sop = (uint16 *)bufp->page; + + if (PAIRFITS(sop, key, val)) + putpair((char *)sop, key, (DBT *)val); + else if (__big_insert(hashp, bufp, key, val)) { +#ifdef DEBUG + assert(0); +#endif + return (-1); + } + } + bufp->flags |= BUF_MOD; + /* + * If the average number of keys per bucket exceeds the fill factor, + * expand the table. + */ + hashp->NKEYS++; + if (do_expand || + (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) + return (__expand_table(hashp)); + return (0); +} + +/* + * + * Returns: + * pointer on success + * NULL on error + */ +extern BUFHEAD * +__add_ovflpage(HTAB *hashp, BUFHEAD *bufp) +{ + register uint16 *sp; + uint16 ndx, ovfl_num; +#ifdef DEBUG1 + int tmp1, tmp2; +#endif + sp = (uint16 *)bufp->page; + + /* Check if we are dynamically determining the fill factor */ + if (hashp->FFACTOR == DEF_FFACTOR) { + hashp->FFACTOR = sp[0] >> 1; + if (hashp->FFACTOR < MIN_FFACTOR) + hashp->FFACTOR = MIN_FFACTOR; + } + bufp->flags |= BUF_MOD; + ovfl_num = overflow_page(hashp); +#ifdef DEBUG1 + tmp1 = bufp->addr; + tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; +#endif + if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) + return (NULL); + bufp->ovfl->flags |= BUF_MOD; +#ifdef DEBUG1 + (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", + tmp1, tmp2, bufp->ovfl->addr); +#endif + ndx = sp[0]; + /* + * Since a pair is allocated on a page only if there's room to add + * an overflow page, we know that the OVFL information will fit on + * the page. + */ + sp[ndx + 4] = OFFSET(sp); + sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; + sp[ndx + 1] = ovfl_num; + sp[ndx + 2] = OVFLPAGE; + sp[0] = ndx + 2; +#ifdef HASH_STATISTICS + hash_overflows++; +#endif + return (bufp->ovfl); +} + +/* + * Returns: + * 0 indicates SUCCESS + * -1 indicates FAILURE + */ +extern int +__get_page(HTAB *hashp, + char *p, + uint32 bucket, + int is_bucket, + int is_disk, + int is_bitmap) +{ + register int fd, page; + size_t size; + int rsize; + uint16 *bp; + + fd = hashp->fp; + size = hashp->BSIZE; + + if ((fd == -1) || !is_disk) { + PAGE_INIT(p); + return (0); + } + if (is_bucket) + page = BUCKET_TO_PAGE(bucket); + else + page = OADDR_TO_PAGE(bucket); + if ((MY_LSEEK(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || + ((rsize = read(fd, p, size)) == -1)) + return (-1); + + bp = (uint16 *)p; + if (!rsize) + bp[0] = 0; /* We hit the EOF, so initialize a new page */ + else if ((unsigned)rsize != size) { + errno = EFTYPE; + return (-1); + } + + if (!is_bitmap && !bp[0]) { + PAGE_INIT(p); + } else { + + if (hashp->LORDER != BYTE_ORDER) { + register int i, max; + + if (is_bitmap) { + max = hashp->BSIZE >> 2; /* divide by 4 */ + for (i = 0; i < max; i++) + M_32_SWAP(((int *)p)[i]); + } else { + M_16_SWAP(bp[0]); + max = bp[0] + 2; + + /* bound the size of max by + * the maximum number of entries + * in the array + */ + if ((unsigned)max > (size / sizeof(uint16))) + return (DATABASE_CORRUPTED_ERROR); + + /* do the byte order swap + */ + for (i = 1; i <= max; i++) + M_16_SWAP(bp[i]); + } + } + + /* check the validity of the page here + * (after doing byte order swaping if necessary) + */ + if (!is_bitmap && bp[0] != 0) { + uint16 num_keys = bp[0]; + uint16 offset; + uint16 i; + + /* bp[0] is supposed to be the number of + * entries currently in the page. If + * bp[0] is too large (larger than the whole + * page) then the page is corrupted + */ + if (bp[0] > (size / sizeof(uint16))) + return (DATABASE_CORRUPTED_ERROR); + + /* bound free space */ + if (FREESPACE(bp) > size) + return (DATABASE_CORRUPTED_ERROR); + + /* check each key and data offset to make + * sure they are all within bounds they + * should all be less than the previous + * offset as well. + */ + offset = size; + for (i = 1; i <= num_keys; i += 2) { + /* ignore overflow pages etc. */ + if (bp[i + 1] >= REAL_KEY) { + + if (bp[i] > offset || bp[i + 1] > bp[i]) + return (DATABASE_CORRUPTED_ERROR); + + offset = bp[i + 1]; + } else { + /* there are no other valid keys after + * seeing a non REAL_KEY + */ + break; + } + } + } + } + return (0); +} + +/* + * Write page p to disk + * + * Returns: + * 0 ==> OK + * -1 ==>failure + */ +extern int +__put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap) +{ + register int fd, page; + size_t size; + int wsize; + off_t offset; + + size = hashp->BSIZE; + if ((hashp->fp == -1) && open_temp(hashp)) + return (-1); + fd = hashp->fp; + + if (hashp->LORDER != BYTE_ORDER) { + register int i; + register int max; + + if (is_bitmap) { + max = hashp->BSIZE >> 2; /* divide by 4 */ + for (i = 0; i < max; i++) + M_32_SWAP(((int *)p)[i]); + } else { + max = ((uint16 *)p)[0] + 2; + + /* bound the size of max by + * the maximum number of entries + * in the array + */ + if ((unsigned)max > (size / sizeof(uint16))) + return (DATABASE_CORRUPTED_ERROR); + + for (i = 0; i <= max; i++) + M_16_SWAP(((uint16 *)p)[i]); + } + } + + if (is_bucket) + page = BUCKET_TO_PAGE(bucket); + else + page = OADDR_TO_PAGE(bucket); + offset = (off_t)page << hashp->BSHIFT; + if ((MY_LSEEK(fd, offset, SEEK_SET) == -1) || + ((wsize = write(fd, p, size)) == -1)) + /* Errno is set */ + return (-1); + if ((unsigned)wsize != size) { + errno = EFTYPE; + return (-1); + } +#if defined(_WIN32) || defined(_WINDOWS) + if (offset + size > hashp->file_size) { + hashp->updateEOF = 1; + } +#endif + /* put the page back the way it was so that it isn't byteswapped + * if it remains in memory - LJM + */ + if (hashp->LORDER != BYTE_ORDER) { + register int i; + register int max; + + if (is_bitmap) { + max = hashp->BSIZE >> 2; /* divide by 4 */ + for (i = 0; i < max; i++) + M_32_SWAP(((int *)p)[i]); + } else { + uint16 *bp = (uint16 *)p; + + M_16_SWAP(bp[0]); + max = bp[0] + 2; + + /* no need to bound the size if max again + * since it was done already above + */ + + /* do the byte order re-swap + */ + for (i = 1; i <= max; i++) + M_16_SWAP(bp[i]); + } + } + + return (0); +} + +#define BYTE_MASK ((1 << INT_BYTE_SHIFT) - 1) +/* + * Initialize a new bitmap page. Bitmap pages are left in memory + * once they are read in. + */ +extern int +__ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) +{ + uint32 *ip; + size_t clearbytes, clearints; + + if ((ip = (uint32 *)malloc((size_t)hashp->BSIZE)) == NULL) + return (1); + hashp->nmaps++; + clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; + clearbytes = clearints << INT_TO_BYTE; + (void)memset((char *)ip, 0, clearbytes); + (void)memset(((char *)ip) + clearbytes, 0xFF, + hashp->BSIZE - clearbytes); + ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); + SETBIT(ip, 0); + hashp->BITMAPS[ndx] = (uint16)pnum; + hashp->mapp[ndx] = ip; + return (0); +} + +static uint32 +first_free(uint32 map) +{ + register uint32 i, mask; + + mask = 0x1; + for (i = 0; i < BITS_PER_MAP; i++) { + if (!(mask & map)) + return (i); + mask = mask << 1; + } + return (i); +} + +static uint16 +overflow_page(HTAB *hashp) +{ + register uint32 *freep = NULL; + register int max_free, offset, splitnum; + uint16 addr; + uint32 i; + int bit, first_page, free_bit, free_page, in_use_bits, j; +#ifdef DEBUG2 + int tmp1, tmp2; +#endif + splitnum = hashp->OVFL_POINT; + max_free = hashp->SPARES[splitnum]; + + free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); + free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); + + /* Look through all the free maps to find the first free block */ + first_page = hashp->LAST_FREED >> (hashp->BSHIFT + BYTE_SHIFT); + for (i = first_page; i <= (unsigned)free_page; i++) { + if (!(freep = (uint32 *)hashp->mapp[i]) && + !(freep = fetch_bitmap(hashp, i))) + return (0); + if (i == (unsigned)free_page) + in_use_bits = free_bit; + else + in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; + + if (i == (unsigned)first_page) { + bit = hashp->LAST_FREED & + ((hashp->BSIZE << BYTE_SHIFT) - 1); + j = bit / BITS_PER_MAP; + bit = bit & ~(BITS_PER_MAP - 1); + } else { + bit = 0; + j = 0; + } + for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) + if (freep[j] != ALL_SET) + goto found; + } + + /* No Free Page Found */ + hashp->LAST_FREED = hashp->SPARES[splitnum]; + hashp->SPARES[splitnum]++; + offset = hashp->SPARES[splitnum] - + (splitnum ? hashp->SPARES[splitnum - 1] : 0); + +#define OVMSG "HASH: Out of overflow pages. Increase page size\n" + if (offset > SPLITMASK) { + if (++splitnum >= NCACHED) { +#ifndef macintosh + (void)fwrite(OVMSG, 1, sizeof(OVMSG) - 1, stderr); +#endif + return (0); + } + hashp->OVFL_POINT = splitnum; + hashp->SPARES[splitnum] = hashp->SPARES[splitnum - 1]; + hashp->SPARES[splitnum - 1]--; + offset = 1; + } + + /* Check if we need to allocate a new bitmap page */ + if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { + free_page++; + if (free_page >= NCACHED) { +#ifndef macintosh + (void)fwrite(OVMSG, 1, sizeof(OVMSG) - 1, stderr); +#endif + return (0); + } + /* + * This is tricky. The 1 indicates that you want the new page + * allocated with 1 clear bit. Actually, you are going to + * allocate 2 pages from this map. The first is going to be + * the map page, the second is the overflow page we were + * looking for. The init_bitmap routine automatically, sets + * the first bit of itself to indicate that the bitmap itself + * is in use. We would explicitly set the second bit, but + * don't have to if we tell init_bitmap not to leave it clear + * in the first place. + */ + if (__ibitmap(hashp, + (int)OADDR_OF(splitnum, offset), 1, free_page)) + return (0); + hashp->SPARES[splitnum]++; +#ifdef DEBUG2 + free_bit = 2; +#endif + offset++; + if (offset > SPLITMASK) { + if (++splitnum >= NCACHED) { +#ifndef macintosh + (void)fwrite(OVMSG, 1, sizeof(OVMSG) - 1, stderr); +#endif + return (0); + } + hashp->OVFL_POINT = splitnum; + hashp->SPARES[splitnum] = hashp->SPARES[splitnum - 1]; + hashp->SPARES[splitnum - 1]--; + offset = 0; + } + } else { + /* + * Free_bit addresses the last used bit. Bump it to address + * the first available bit. + */ + free_bit++; + SETBIT(freep, free_bit); + } + + /* Calculate address of the new overflow page */ + addr = OADDR_OF(splitnum, offset); +#ifdef DEBUG2 + (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", + addr, free_bit, free_page); +#endif + return (addr); + +found: + bit = bit + first_free(freep[j]); + SETBIT(freep, bit); +#ifdef DEBUG2 + tmp1 = bit; + tmp2 = i; +#endif + /* + * Bits are addressed starting with 0, but overflow pages are addressed + * beginning at 1. Bit is a bit addressnumber, so we need to increment + * it to convert it to a page number. + */ + bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); + if (bit >= hashp->LAST_FREED) + hashp->LAST_FREED = bit - 1; + + /* Calculate the split number for this page */ + for (i = 0; (i < (unsigned)splitnum) && (bit > hashp->SPARES[i]); i++) { + } + offset = (i ? bit - hashp->SPARES[i - 1] : bit); + if (offset >= SPLITMASK) + return (0); /* Out of overflow pages */ + addr = OADDR_OF(i, offset); +#ifdef DEBUG2 + (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", + addr, tmp1, tmp2); +#endif + + /* Allocate and return the overflow page */ + return (addr); +} + +/* + * Mark this overflow page as free. + */ +extern void +__free_ovflpage(HTAB *hashp, BUFHEAD *obufp) +{ + uint16 addr; + uint32 *freep; + uint32 bit_address, free_page, free_bit; + uint16 ndx; + + if (!obufp || !obufp->addr) + return; + + addr = obufp->addr; +#ifdef DEBUG1 + (void)fprintf(stderr, "Freeing %d\n", addr); +#endif + ndx = (((uint16)addr) >> SPLITSHIFT); + bit_address = + (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; + if (bit_address < (uint32)hashp->LAST_FREED) + hashp->LAST_FREED = bit_address; + free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); + free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); + + if (!(freep = hashp->mapp[free_page])) + freep = fetch_bitmap(hashp, free_page); + +#ifdef DEBUG + /* + * This had better never happen. It means we tried to read a bitmap + * that has already had overflow pages allocated off it, and we + * failed to read it from the file. + */ + if (!freep) { + assert(0); + return; + } +#endif + CLRBIT(freep, free_bit); +#ifdef DEBUG2 + (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", + obufp->addr, free_bit, free_page); +#endif + __reclaim_buf(hashp, obufp); +} + +/* + * Returns: + * 0 success + * -1 failure + */ +static int +open_temp(HTAB *hashp) +{ +#ifdef XP_OS2 + hashp->fp = mkstemp(NULL); +#else +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) + sigset_t set, oset; +#endif +#if !defined(macintosh) + char *tmpdir; + size_t len; + char last; +#endif + static const char namestr[] = "/_hashXXXXXX"; + char filename[1024]; + +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) + /* Block signals; make sure file goes away at process exit. */ + (void)sigfillset(&set); + (void)sigprocmask(SIG_BLOCK, &set, &oset); +#endif + + filename[0] = 0; +#if defined(macintosh) + strcat(filename, namestr + 1); +#else + tmpdir = getenv("TMP"); + if (!tmpdir) + tmpdir = getenv("TMPDIR"); + if (!tmpdir) + tmpdir = getenv("TEMP"); + if (!tmpdir) + tmpdir = "."; + len = strlen(tmpdir); + if (len && len < (sizeof filename - sizeof namestr)) { + strcpy(filename, tmpdir); + } + len = strlen(filename); + last = tmpdir[len - 1]; + strcat(filename, (last == '/' || last == '\\') ? namestr + 1 : namestr); +#endif + +#if defined(_WIN32) || defined(_WINDOWS) + if ((hashp->fp = mkstempflags(filename, _O_BINARY | _O_TEMPORARY)) != -1) { + if (hashp->filename) { + free(hashp->filename); + } + hashp->filename = strdup(filename); + hashp->is_temp = 1; + } +#else + if ((hashp->fp = mkstemp(filename)) != -1) { + (void)unlink(filename); +#if !defined(macintosh) + (void)fcntl(hashp->fp, F_SETFD, 1); +#endif + } +#endif + +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) + (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); +#endif +#endif /* !OS2 */ + return (hashp->fp != -1 ? 0 : -1); +} + +/* + * We have to know that the key will fit, but the last entry on the page is + * an overflow pair, so we need to shift things. + */ +static void +squeeze_key(uint16 *sp, const DBT *key, const DBT *val) +{ + register char *p; + uint16 free_space, n, off, pageno; + + p = (char *)sp; + n = sp[0]; + free_space = FREESPACE(sp); + off = OFFSET(sp); + + pageno = sp[n - 1]; + off -= key->size; + sp[n - 1] = off; + memmove(p + off, key->data, key->size); + off -= val->size; + sp[n] = off; + memmove(p + off, val->data, val->size); + sp[0] = n + 2; + sp[n + 1] = pageno; + sp[n + 2] = OVFLPAGE; + FREESPACE(sp) = free_space - PAIRSIZE(key, val); + OFFSET(sp) = off; +} + +static uint32 * +fetch_bitmap(HTAB *hashp, uint32 ndx) +{ + if (ndx >= (unsigned)hashp->nmaps) + return (NULL); + if ((hashp->mapp[ndx] = (uint32 *)malloc((size_t)hashp->BSIZE)) == NULL) + return (NULL); + if (__get_page(hashp, + (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { + free(hashp->mapp[ndx]); + hashp->mapp[ndx] = NULL; /* NEW: 9-11-95 */ + return (NULL); + } + return (hashp->mapp[ndx]); +} + +#ifdef DEBUG4 +int +print_chain(int addr) +{ + BUFHEAD *bufp; + short *bp, oaddr; + + (void)fprintf(stderr, "%d ", addr); + bufp = __get_buf(hashp, addr, NULL, 0); + bp = (short *)bufp->page; + while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || + ((bp[0] > 2) && bp[2] < REAL_KEY))) { + oaddr = bp[bp[0] - 1]; + (void)fprintf(stderr, "%d ", (int)oaddr); + bufp = __get_buf(hashp, (int)oaddr, bufp, 0); + bp = (short *)bufp->page; + } + (void)fprintf(stderr, "\n"); +} +#endif diff --git a/security/nss/lib/dbm/src/hash.c b/security/nss/lib/dbm/src/hash.c new file mode 100644 index 000000000..b80aad4d3 --- /dev/null +++ b/security/nss/lib/dbm/src/hash.c @@ -0,0 +1,1172 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)hash.c 8.9 (Berkeley) 6/16/94"; +#endif /* LIBC_SCCS and not lint */ + +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) +#include <sys/param.h> +#endif + +#if !defined(macintosh) +#ifdef XP_OS2 +#include <sys/types.h> +#endif +#include <sys/stat.h> +#endif + +#if defined(macintosh) +#include <unix.h> +#include <unistd.h> +#endif + +#include <errno.h> +#include <fcntl.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) +#include <unistd.h> +#endif +#if defined(_WIN32) || defined(_WINDOWS) +#include <windows.h> +#endif + +#include <assert.h> + +#include "mcom_db.h" +#include "hash.h" +#include "page.h" + +/* +#include "extern.h" +*/ +static int alloc_segs(HTAB *, int); +static int flush_meta(HTAB *); +static int hash_access(HTAB *, ACTION, DBT *, DBT *); +static int hash_close(DB *); +static int hash_delete(const DB *, const DBT *, uint); +static int hash_fd(const DB *); +static int hash_get(const DB *, const DBT *, DBT *, uint); +static int hash_put(const DB *, DBT *, const DBT *, uint); +static void *hash_realloc(SEGMENT **, size_t, size_t); +static int hash_seq(const DB *, DBT *, DBT *, uint); +static int hash_sync(const DB *, uint); +static int hdestroy(HTAB *); +static HTAB *init_hash(HTAB *, const char *, HASHINFO *); +static int init_htab(HTAB *, int); +#if BYTE_ORDER == LITTLE_ENDIAN +static void swap_header(HTAB *); +static void swap_header_copy(HASHHDR *, HASHHDR *); +#endif + +/* Fast arithmetic, relying on powers of 2, */ +#define MOD(x, y) ((x) & ((y)-1)) + +#define RETURN_ERROR(ERR, LOC) \ + { \ + save_errno = ERR; \ + goto LOC; \ + } + +/* Return values */ +#define SUCCESS (0) +#define DBM_ERROR (-1) +#define ABNORMAL (1) + +#ifdef HASH_STATISTICS +int hash_accesses, hash_collisions, hash_expansions, hash_overflows; +#endif + +/* A new Lou (montulli@mozilla.com) routine. + * + * The database is screwed. + * + * This closes the file, flushing buffers as appropriate. + */ +static void +__remove_database(DB *dbp) +{ + HTAB *hashp = (HTAB *)dbp->internal; + + assert(0); + + if (!hashp) + return; + hdestroy(hashp); + dbp->internal = NULL; +} + +/************************** INTERFACE ROUTINES ***************************/ +/* OPEN/CLOSE */ + +extern DB * +__hash_open(const char *file, int flags, int mode, const HASHINFO *info, int dflags) +{ + HTAB *hashp = NULL; + struct stat statbuf; + DB *dbp; + int bpages, hdrsize, new_table, nsegs, save_errno; + + if ((flags & O_ACCMODE) == O_WRONLY) { + errno = EINVAL; + return NULL; + } + + /* zero the statbuffer so that + * we can check it for a non-zero + * date to see if stat succeeded + */ + memset(&statbuf, 0, sizeof(struct stat)); + + if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) { + errno = ENOMEM; + return NULL; + } + hashp->fp = NO_FILE; + if (file) + hashp->filename = strdup(file); + + /* + * Even if user wants write only, we need to be able to read + * the actual file, so we need to open it read/write. But, the + * field in the hashp structure needs to be accurate so that + * we can check accesses. + */ + hashp->flags = flags; + + new_table = 0; + if (!file || (flags & O_TRUNC) || (stat(file, &statbuf) && (errno == ENOENT))) { + if (errno == ENOENT) + errno = 0; /* Just in case someone looks at errno */ + new_table = 1; + } else if (statbuf.st_mtime && statbuf.st_size == 0) { + /* check for a zero length file and delete it + * if it exists + */ + new_table = 1; + } + hashp->file_size = statbuf.st_size; + + if (file) { +#if defined(_WIN32) || defined(_WINDOWS) || defined(macintosh) || defined(XP_OS2) + if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1) + RETURN_ERROR(errno, error1); +#else + if ((hashp->fp = open(file, flags, mode)) == -1) + RETURN_ERROR(errno, error1); + (void)fcntl(hashp->fp, F_SETFD, 1); +#endif + } + if (new_table) { + if (!init_hash(hashp, file, (HASHINFO *)info)) + RETURN_ERROR(errno, error1); + } else { + /* Table already exists */ + if (info && info->hash) + hashp->hash = info->hash; + else + hashp->hash = __default_hash; + + hdrsize = read(hashp->fp, (char *)&hashp->hdr, sizeof(HASHHDR)); + if (hdrsize == -1) + RETURN_ERROR(errno, error1); + if (hdrsize != sizeof(HASHHDR)) + RETURN_ERROR(EFTYPE, error1); +#if BYTE_ORDER == LITTLE_ENDIAN + swap_header(hashp); +#endif + /* Verify file type, versions and hash function */ + if (hashp->MAGIC != HASHMAGIC) + RETURN_ERROR(EFTYPE, error1); +#define OLDHASHVERSION 1 + if (hashp->VERSION != HASHVERSION && + hashp->VERSION != OLDHASHVERSION) + RETURN_ERROR(EFTYPE, error1); + if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) + RETURN_ERROR(EFTYPE, error1); + if (hashp->NKEYS < 0) /* Old bad database. */ + RETURN_ERROR(EFTYPE, error1); + + /* + * Figure out how many segments we need. Max_Bucket is the + * maximum bucket number, so the number of buckets is + * max_bucket + 1. + */ + nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / + hashp->SGSIZE; + hashp->nsegs = 0; + if (alloc_segs(hashp, nsegs)) + /* If alloc_segs fails, errno will have been set. */ + RETURN_ERROR(errno, error1); + /* Read in bitmaps */ + bpages = (hashp->SPARES[hashp->OVFL_POINT] + + (hashp->BSIZE << BYTE_SHIFT) - 1) >> + (hashp->BSHIFT + BYTE_SHIFT); + + hashp->nmaps = bpages; + (void)memset(&hashp->mapp[0], 0, bpages * sizeof(uint32 *)); + } + + /* Initialize Buffer Manager */ + if (info && info->cachesize) + __buf_init(hashp, (int32)info->cachesize); + else + __buf_init(hashp, DEF_BUFSIZE); + + hashp->new_file = new_table; +#ifdef macintosh + hashp->save_file = file && !(hashp->flags & O_RDONLY); +#else + hashp->save_file = file && (hashp->flags & O_RDWR); +#endif + hashp->cbucket = -1; + if (!(dbp = (DB *)malloc(sizeof(DB)))) { + RETURN_ERROR(ENOMEM, error1); + } + dbp->internal = hashp; + dbp->close = hash_close; + dbp->del = hash_delete; + dbp->fd = hash_fd; + dbp->get = hash_get; + dbp->put = hash_put; + dbp->seq = hash_seq; + dbp->sync = hash_sync; + dbp->type = DB_HASH; + +#ifdef HASH_STATISTICS + hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; +#endif + return (dbp); + +error1: + hdestroy(hashp); + errno = save_errno; + return (NULL); +} + +static int +hash_close(DB *dbp) +{ + HTAB *hashp; + int retval; + + if (!dbp) + return (DBM_ERROR); + + hashp = (HTAB *)dbp->internal; + if (!hashp) + return (DBM_ERROR); + + retval = hdestroy(hashp); + free(dbp); + return (retval); +} + +static int +hash_fd(const DB *dbp) +{ + HTAB *hashp; + + if (!dbp) + return (DBM_ERROR); + + hashp = (HTAB *)dbp->internal; + if (!hashp) + return (DBM_ERROR); + + if (hashp->fp == -1) { + errno = ENOENT; + return (-1); + } + return (hashp->fp); +} + +/************************** LOCAL CREATION ROUTINES **********************/ +static HTAB * +init_hash(HTAB *hashp, const char *file, HASHINFO *info) +{ + struct stat statbuf; + int nelem; + + nelem = 1; + hashp->NKEYS = 0; + hashp->LORDER = BYTE_ORDER; + hashp->BSIZE = DEF_BUCKET_SIZE; + hashp->BSHIFT = DEF_BUCKET_SHIFT; + hashp->SGSIZE = DEF_SEGSIZE; + hashp->SSHIFT = DEF_SEGSIZE_SHIFT; + hashp->DSIZE = DEF_DIRSIZE; + hashp->FFACTOR = DEF_FFACTOR; + hashp->hash = __default_hash; + memset(hashp->SPARES, 0, sizeof(hashp->SPARES)); + memset(hashp->BITMAPS, 0, sizeof(hashp->BITMAPS)); + + /* Fix bucket size to be optimal for file system */ + if (file != NULL) { + if (stat(file, &statbuf)) + return (NULL); + +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) && !defined(XP_OS2) +#if defined(__QNX__) && !defined(__QNXNTO__) + hashp->BSIZE = 512; /* preferred blk size on qnx4 */ +#else + hashp->BSIZE = statbuf.st_blksize; +#endif + + /* new code added by Lou to reduce block + * size down below MAX_BSIZE + */ + if (hashp->BSIZE > MAX_BSIZE) + hashp->BSIZE = MAX_BSIZE; +#endif + hashp->BSHIFT = __log2((uint32)hashp->BSIZE); + } + + if (info) { + if (info->bsize) { + /* Round pagesize up to power of 2 */ + hashp->BSHIFT = __log2(info->bsize); + hashp->BSIZE = 1 << hashp->BSHIFT; + if (hashp->BSIZE > MAX_BSIZE) { + errno = EINVAL; + return (NULL); + } + } + if (info->ffactor) + hashp->FFACTOR = info->ffactor; + if (info->hash) + hashp->hash = info->hash; + if (info->nelem) + nelem = info->nelem; + if (info->lorder) { + if (info->lorder != BIG_ENDIAN && + info->lorder != LITTLE_ENDIAN) { + errno = EINVAL; + return (NULL); + } + hashp->LORDER = info->lorder; + } + } + /* init_htab sets errno if it fails */ + if (init_htab(hashp, nelem)) + return (NULL); + else + return (hashp); +} +/* + * This calls alloc_segs which may run out of memory. Alloc_segs will + * set errno, so we just pass the error information along. + * + * Returns 0 on No Error + */ +static int +init_htab(HTAB *hashp, int nelem) +{ + register int nbuckets, nsegs; + int l2; + + /* + * Divide number of elements by the fill factor and determine a + * desired number of buckets. Allocate space for the next greater + * power of two number of buckets. + */ + nelem = (nelem - 1) / hashp->FFACTOR + 1; + + l2 = __log2((uint32)PR_MAX(nelem, 2)); + nbuckets = 1 << l2; + + hashp->SPARES[l2] = l2 + 1; + hashp->SPARES[l2 + 1] = l2 + 1; + hashp->OVFL_POINT = l2; + hashp->LAST_FREED = 2; + + /* First bitmap page is at: splitpoint l2 page offset 1 */ + if (__ibitmap(hashp, (int)OADDR_OF(l2, 1), l2 + 1, 0)) + return (-1); + + hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; + hashp->HIGH_MASK = (nbuckets << 1) - 1; + hashp->HDRPAGES = ((PR_MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> + hashp->BSHIFT) + + 1; + + nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; + nsegs = 1 << __log2((uint32)nsegs); + + if (nsegs > hashp->DSIZE) + hashp->DSIZE = nsegs; + return (alloc_segs(hashp, nsegs)); +} + +/********************** DESTROY/CLOSE ROUTINES ************************/ + +/* + * Flushes any changes to the file if necessary and destroys the hashp + * structure, freeing all allocated space. + */ +static int +hdestroy(HTAB *hashp) +{ + int i, save_errno; + + save_errno = 0; + +#ifdef HASH_STATISTICS + (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", + hash_accesses, hash_collisions); + (void)fprintf(stderr, "hdestroy: expansions %ld\n", + hash_expansions); + (void)fprintf(stderr, "hdestroy: overflows %ld\n", + hash_overflows); + (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", + hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); + + for (i = 0; i < NCACHED; i++) + (void)fprintf(stderr, + "spares[%d] = %d\n", i, hashp->SPARES[i]); +#endif + /* + * Call on buffer manager to free buffers, and if required, + * write them to disk. + */ + if (__buf_free(hashp, 1, hashp->save_file)) + save_errno = errno; + if (hashp->dir) { + free(*hashp->dir); /* Free initial segments */ + /* Free extra segments */ + while (hashp->exsegs--) + free(hashp->dir[--hashp->nsegs]); + free(hashp->dir); + } + if (flush_meta(hashp) && !save_errno) + save_errno = errno; + /* Free Bigmaps */ + for (i = 0; i < hashp->nmaps; i++) + if (hashp->mapp[i]) + free(hashp->mapp[i]); + + if (hashp->fp != -1) + (void)close(hashp->fp); + + if (hashp->filename) { +#if defined(_WIN32) || defined(_WINDOWS) || defined(XP_OS2) + if (hashp->is_temp) + (void)unlink(hashp->filename); +#endif + free(hashp->filename); + } + if (hashp->tmp_buf) + free(hashp->tmp_buf); + if (hashp->tmp_key) + free(hashp->tmp_key); + free(hashp); + if (save_errno) { + errno = save_errno; + return (DBM_ERROR); + } + return (SUCCESS); +} + +#if defined(_WIN32) || defined(_WINDOWS) +/* + * Close and reopen file to force file length update on windows. + * + * Returns: + * 0 == OK + * -1 DBM_ERROR + */ +static int +update_EOF(HTAB *hashp) +{ +#if defined(DBM_REOPEN_ON_FLUSH) + char *file = hashp->filename; + off_t file_size; + int flags; + int mode = -1; + struct stat statbuf; + + memset(&statbuf, 0, sizeof statbuf); + + /* make sure we won't lose the file by closing it. */ + if (!file || (stat(file, &statbuf) && (errno == ENOENT))) { + /* pretend we did it. */ + return 0; + } + + (void)close(hashp->fp); + + flags = hashp->flags & ~(O_TRUNC | O_CREAT | O_EXCL); + + if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1) + return -1; + file_size = lseek(hashp->fp, (off_t)0, SEEK_END); + if (file_size == -1) + return -1; + hashp->file_size = file_size; + return 0; +#else + int fd = hashp->fp; + off_t file_size = lseek(fd, (off_t)0, SEEK_END); + HANDLE handle = (HANDLE)_get_osfhandle(fd); + BOOL cool = FlushFileBuffers(handle); +#ifdef DEBUG3 + if (!cool) { + DWORD err = GetLastError(); + (void)fprintf(stderr, + "FlushFileBuffers failed, last error = %d, 0x%08x\n", + err, err); + } +#endif + if (file_size == -1) + return -1; + hashp->file_size = file_size; + return cool ? 0 : -1; +#endif +} +#endif + +/* + * Write modified pages to disk + * + * Returns: + * 0 == OK + * -1 DBM_ERROR + */ +static int +hash_sync(const DB *dbp, uint flags) +{ + HTAB *hashp; + + if (flags != 0) { + errno = EINVAL; + return (DBM_ERROR); + } + + if (!dbp) + return (DBM_ERROR); + + hashp = (HTAB *)dbp->internal; + if (!hashp) + return (DBM_ERROR); + + if (!hashp->save_file) + return (0); + if (__buf_free(hashp, 0, 1) || flush_meta(hashp)) + return (DBM_ERROR); +#if defined(_WIN32) || defined(_WINDOWS) + if (hashp->updateEOF && hashp->filename && !hashp->is_temp) { + int status = update_EOF(hashp); + hashp->updateEOF = 0; + if (status) + return status; + } +#endif + hashp->new_file = 0; + return (0); +} + +/* + * Returns: + * 0 == OK + * -1 indicates that errno should be set + */ +static int +flush_meta(HTAB *hashp) +{ + HASHHDR *whdrp; +#if BYTE_ORDER == LITTLE_ENDIAN + HASHHDR whdr; +#endif + int fp, i, wsize; + + if (!hashp->save_file) + return (0); + hashp->MAGIC = HASHMAGIC; + hashp->VERSION = HASHVERSION; + hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); + + fp = hashp->fp; + whdrp = &hashp->hdr; +#if BYTE_ORDER == LITTLE_ENDIAN + whdrp = &whdr; + swap_header_copy(&hashp->hdr, whdrp); +#endif + if ((lseek(fp, (off_t)0, SEEK_SET) == -1) || + ((wsize = write(fp, (char *)whdrp, sizeof(HASHHDR))) == -1)) + return (-1); + else if (wsize != sizeof(HASHHDR)) { + errno = EFTYPE; + hashp->dbmerrno = errno; + return (-1); + } + for (i = 0; i < NCACHED; i++) + if (hashp->mapp[i]) + if (__put_page(hashp, (char *)hashp->mapp[i], + hashp->BITMAPS[i], 0, 1)) + return (-1); + return (0); +} + +/*******************************SEARCH ROUTINES *****************************/ +/* + * All the access routines return + * + * Returns: + * 0 on SUCCESS + * 1 to indicate an external DBM_ERROR (i.e. key not found, etc) + * -1 to indicate an internal DBM_ERROR (i.e. out of memory, etc) + */ +static int +hash_get( + const DB *dbp, + const DBT *key, + DBT *data, + uint flag) +{ + HTAB *hashp; + int rv; + + hashp = (HTAB *)dbp->internal; + if (!hashp) + return (DBM_ERROR); + + if (flag) { + hashp->dbmerrno = errno = EINVAL; + return (DBM_ERROR); + } + + rv = hash_access(hashp, HASH_GET, (DBT *)key, data); + + if (rv == DATABASE_CORRUPTED_ERROR) { +#if defined(unix) && defined(DEBUG) + printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); +#endif + __remove_database((DB *)dbp); + } + + return (rv); +} + +static int +hash_put( + const DB *dbp, + DBT *key, + const DBT *data, + uint flag) +{ + HTAB *hashp; + int rv; + + hashp = (HTAB *)dbp->internal; + if (!hashp) + return (DBM_ERROR); + + if (flag && flag != R_NOOVERWRITE) { + hashp->dbmerrno = errno = EINVAL; + return (DBM_ERROR); + } + if ((hashp->flags & O_ACCMODE) == O_RDONLY) { + hashp->dbmerrno = errno = EPERM; + return (DBM_ERROR); + } + + rv = hash_access(hashp, flag == R_NOOVERWRITE ? HASH_PUTNEW + : HASH_PUT, + (DBT *)key, (DBT *)data); + + if (rv == DATABASE_CORRUPTED_ERROR) { +#if defined(unix) && defined(DEBUG) + printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); +#endif + __remove_database((DB *)dbp); + } + + return (rv); +} + +static int +hash_delete( + const DB *dbp, + const DBT *key, + uint flag) /* Ignored */ +{ + HTAB *hashp; + int rv; + + hashp = (HTAB *)dbp->internal; + if (!hashp) + return (DBM_ERROR); + + if (flag && flag != R_CURSOR) { + hashp->dbmerrno = errno = EINVAL; + return (DBM_ERROR); + } + if ((hashp->flags & O_ACCMODE) == O_RDONLY) { + hashp->dbmerrno = errno = EPERM; + return (DBM_ERROR); + } + rv = hash_access(hashp, HASH_DELETE, (DBT *)key, NULL); + + if (rv == DATABASE_CORRUPTED_ERROR) { +#if defined(unix) && defined(DEBUG) + printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); +#endif + __remove_database((DB *)dbp); + } + + return (rv); +} + +#define MAX_OVERFLOW_HASH_ACCESS_LOOPS 2000 +/* + * Assume that hashp has been set in wrapper routine. + */ +static int +hash_access( + HTAB *hashp, + ACTION action, + DBT *key, DBT *val) +{ + register BUFHEAD *rbufp; + BUFHEAD *bufp, *save_bufp; + register uint16 *bp; + register long n, ndx, off; + register size_t size; + register char *kp; + uint16 pageno; + uint32 ovfl_loop_count = 0; + int32 last_overflow_page_no = -1; + +#ifdef HASH_STATISTICS + hash_accesses++; +#endif + + off = hashp->BSIZE; + size = key->size; + kp = (char *)key->data; + rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0); + if (!rbufp) + return (DATABASE_CORRUPTED_ERROR); + save_bufp = rbufp; + + /* Pin the bucket chain */ + rbufp->flags |= BUF_PIN; + for (bp = (uint16 *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) { + + if (bp[1] >= REAL_KEY) { + /* Real key/data pair */ + if (size == (unsigned long)(off - *bp) && + memcmp(kp, rbufp->page + *bp, size) == 0) + goto found; + off = bp[1]; +#ifdef HASH_STATISTICS + hash_collisions++; +#endif + bp += 2; + ndx += 2; + } else if (bp[1] == OVFLPAGE) { + + /* database corruption: overflow loop detection */ + if (last_overflow_page_no == (int32)*bp) + return (DATABASE_CORRUPTED_ERROR); + + last_overflow_page_no = *bp; + + rbufp = __get_buf(hashp, *bp, rbufp, 0); + if (!rbufp) { + save_bufp->flags &= ~BUF_PIN; + return (DBM_ERROR); + } + + ovfl_loop_count++; + if (ovfl_loop_count > MAX_OVERFLOW_HASH_ACCESS_LOOPS) + return (DATABASE_CORRUPTED_ERROR); + + /* FOR LOOP INIT */ + bp = (uint16 *)rbufp->page; + n = *bp++; + ndx = 1; + off = hashp->BSIZE; + } else if (bp[1] < REAL_KEY) { + if ((ndx = + __find_bigpair(hashp, rbufp, ndx, kp, (int)size)) > 0) + goto found; + if (ndx == -2) { + bufp = rbufp; + if (!(pageno = + __find_last_page(hashp, &bufp))) { + ndx = 0; + rbufp = bufp; + break; /* FOR */ + } + rbufp = __get_buf(hashp, pageno, bufp, 0); + if (!rbufp) { + save_bufp->flags &= ~BUF_PIN; + return (DBM_ERROR); + } + /* FOR LOOP INIT */ + bp = (uint16 *)rbufp->page; + n = *bp++; + ndx = 1; + off = hashp->BSIZE; + } else { + save_bufp->flags &= ~BUF_PIN; + return (DBM_ERROR); + } + } + } + + /* Not found */ + switch (action) { + case HASH_PUT: + case HASH_PUTNEW: + if (__addel(hashp, rbufp, key, val)) { + save_bufp->flags &= ~BUF_PIN; + return (DBM_ERROR); + } else { + save_bufp->flags &= ~BUF_PIN; + return (SUCCESS); + } + case HASH_GET: + case HASH_DELETE: + default: + save_bufp->flags &= ~BUF_PIN; + return (ABNORMAL); + } + +found: + switch (action) { + case HASH_PUTNEW: + save_bufp->flags &= ~BUF_PIN; + return (ABNORMAL); + case HASH_GET: + bp = (uint16 *)rbufp->page; + if (bp[ndx + 1] < REAL_KEY) { + if (__big_return(hashp, rbufp, ndx, val, 0)) + return (DBM_ERROR); + } else { + val->data = (uint8 *)rbufp->page + (int)bp[ndx + 1]; + val->size = bp[ndx] - bp[ndx + 1]; + } + break; + case HASH_PUT: + if ((__delpair(hashp, rbufp, ndx)) || + (__addel(hashp, rbufp, key, val))) { + save_bufp->flags &= ~BUF_PIN; + return (DBM_ERROR); + } + break; + case HASH_DELETE: + if (__delpair(hashp, rbufp, ndx)) + return (DBM_ERROR); + break; + default: + abort(); + } + save_bufp->flags &= ~BUF_PIN; + return (SUCCESS); +} + +static int +hash_seq( + const DB *dbp, + DBT *key, DBT *data, + uint flag) +{ + register uint32 bucket; + register BUFHEAD *bufp = NULL; + HTAB *hashp; + uint16 *bp, ndx; + + hashp = (HTAB *)dbp->internal; + if (!hashp) + return (DBM_ERROR); + + if (flag && flag != R_FIRST && flag != R_NEXT) { + hashp->dbmerrno = errno = EINVAL; + return (DBM_ERROR); + } +#ifdef HASH_STATISTICS + hash_accesses++; +#endif + if ((hashp->cbucket < 0) || (flag == R_FIRST)) { + hashp->cbucket = 0; + hashp->cndx = 1; + hashp->cpage = NULL; + } + + for (bp = NULL; !bp || !bp[0];) { + if (!(bufp = hashp->cpage)) { + for (bucket = hashp->cbucket; + bucket <= (uint32)hashp->MAX_BUCKET; + bucket++, hashp->cndx = 1) { + bufp = __get_buf(hashp, bucket, NULL, 0); + if (!bufp) + return (DBM_ERROR); + hashp->cpage = bufp; + bp = (uint16 *)bufp->page; + if (bp[0]) + break; + } + hashp->cbucket = bucket; + if (hashp->cbucket > hashp->MAX_BUCKET) { + hashp->cbucket = -1; + return (ABNORMAL); + } + } else + bp = (uint16 *)hashp->cpage->page; + +#ifdef DEBUG + assert(bp); + assert(bufp); +#endif + while (bp[hashp->cndx + 1] == OVFLPAGE) { + bufp = hashp->cpage = + __get_buf(hashp, bp[hashp->cndx], bufp, 0); + if (!bufp) + return (DBM_ERROR); + bp = (uint16 *)(bufp->page); + hashp->cndx = 1; + } + if (!bp[0]) { + hashp->cpage = NULL; + ++hashp->cbucket; + } + } + ndx = hashp->cndx; + if (bp[ndx + 1] < REAL_KEY) { + if (__big_keydata(hashp, bufp, key, data, 1)) + return (DBM_ERROR); + } else { + key->data = (uint8 *)hashp->cpage->page + bp[ndx]; + key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; + data->data = (uint8 *)hashp->cpage->page + bp[ndx + 1]; + data->size = bp[ndx] - bp[ndx + 1]; + ndx += 2; + if (ndx > bp[0]) { + hashp->cpage = NULL; + hashp->cbucket++; + hashp->cndx = 1; + } else + hashp->cndx = ndx; + } + return (SUCCESS); +} + +/********************************* UTILITIES ************************/ + +/* + * Returns: + * 0 ==> OK + * -1 ==> Error + */ +extern int +__expand_table(HTAB *hashp) +{ + uint32 old_bucket, new_bucket; + int new_segnum, spare_ndx; + size_t dirsize; + +#ifdef HASH_STATISTICS + hash_expansions++; +#endif + new_bucket = ++hashp->MAX_BUCKET; + old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); + + new_segnum = new_bucket >> hashp->SSHIFT; + + /* Check if we need a new segment */ + if (new_segnum >= hashp->nsegs) { + /* Check if we need to expand directory */ + if (new_segnum >= hashp->DSIZE) { + /* Reallocate directory */ + dirsize = hashp->DSIZE * sizeof(SEGMENT *); + if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) + return (-1); + hashp->DSIZE = dirsize << 1; + } + if ((hashp->dir[new_segnum] = + (SEGMENT)calloc((size_t)hashp->SGSIZE, sizeof(BUFHEAD *))) == NULL) + return (-1); + hashp->exsegs++; + hashp->nsegs++; + } + /* + * If the split point is increasing (MAX_BUCKET's log base 2 + * * increases), we need to copy the current contents of the spare + * split bucket to the next bucket. + */ + spare_ndx = __log2((uint32)(hashp->MAX_BUCKET + 1)); + if (spare_ndx > hashp->OVFL_POINT) { + hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; + hashp->OVFL_POINT = spare_ndx; + } + + if (new_bucket > (uint32)hashp->HIGH_MASK) { + /* Starting a new doubling */ + hashp->LOW_MASK = hashp->HIGH_MASK; + hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; + } + /* Relocate records to the new bucket */ + return (__split_page(hashp, old_bucket, new_bucket)); +} + +/* + * If realloc guarantees that the pointer is not destroyed if the realloc + * fails, then this routine can go away. + */ +static void * +hash_realloc( + SEGMENT **p_ptr, + size_t oldsize, size_t newsize) +{ + register void *p; + + if ((p = malloc(newsize))) { + memmove(p, *p_ptr, oldsize); + memset((char *)p + oldsize, 0, newsize - oldsize); + free(*p_ptr); + *p_ptr = (SEGMENT *)p; + } + return (p); +} + +extern uint32 +__call_hash(HTAB *hashp, char *k, size_t len) +{ + uint32 n, bucket; + + n = hashp->hash(k, len); + bucket = n & hashp->HIGH_MASK; + if (bucket > (uint32)hashp->MAX_BUCKET) + bucket = bucket & hashp->LOW_MASK; + return (bucket); +} + +/* + * Allocate segment table. On error, set errno. + * + * Returns 0 on success + */ +static int +alloc_segs( + HTAB *hashp, + int nsegs) +{ + register int i; + register SEGMENT store; + + if ((hashp->dir = + (SEGMENT *)calloc((size_t)hashp->DSIZE, sizeof(SEGMENT))) == NULL) { + errno = ENOMEM; + return (-1); + } + /* Allocate segments */ + if ((store = + (SEGMENT)calloc((size_t)nsegs << hashp->SSHIFT, sizeof(BUFHEAD *))) == NULL) { + errno = ENOMEM; + return (-1); + } + for (i = 0; i < nsegs; i++, hashp->nsegs++) + hashp->dir[i] = &store[i << hashp->SSHIFT]; + return (0); +} + +#if BYTE_ORDER == LITTLE_ENDIAN +/* + * Hashp->hdr needs to be byteswapped. + */ +static void +swap_header_copy( + HASHHDR *srcp, HASHHDR *destp) +{ + int i; + + P_32_COPY(srcp->magic, destp->magic); + P_32_COPY(srcp->version, destp->version); + P_32_COPY(srcp->lorder, destp->lorder); + P_32_COPY(srcp->bsize, destp->bsize); + P_32_COPY(srcp->bshift, destp->bshift); + P_32_COPY(srcp->dsize, destp->dsize); + P_32_COPY(srcp->ssize, destp->ssize); + P_32_COPY(srcp->sshift, destp->sshift); + P_32_COPY(srcp->ovfl_point, destp->ovfl_point); + P_32_COPY(srcp->last_freed, destp->last_freed); + P_32_COPY(srcp->max_bucket, destp->max_bucket); + P_32_COPY(srcp->high_mask, destp->high_mask); + P_32_COPY(srcp->low_mask, destp->low_mask); + P_32_COPY(srcp->ffactor, destp->ffactor); + P_32_COPY(srcp->nkeys, destp->nkeys); + P_32_COPY(srcp->hdrpages, destp->hdrpages); + P_32_COPY(srcp->h_charkey, destp->h_charkey); + for (i = 0; i < NCACHED; i++) { + P_32_COPY(srcp->spares[i], destp->spares[i]); + P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); + } +} + +static void +swap_header(HTAB *hashp) +{ + HASHHDR *hdrp; + int i; + + hdrp = &hashp->hdr; + + M_32_SWAP(hdrp->magic); + M_32_SWAP(hdrp->version); + M_32_SWAP(hdrp->lorder); + M_32_SWAP(hdrp->bsize); + M_32_SWAP(hdrp->bshift); + M_32_SWAP(hdrp->dsize); + M_32_SWAP(hdrp->ssize); + M_32_SWAP(hdrp->sshift); + M_32_SWAP(hdrp->ovfl_point); + M_32_SWAP(hdrp->last_freed); + M_32_SWAP(hdrp->max_bucket); + M_32_SWAP(hdrp->high_mask); + M_32_SWAP(hdrp->low_mask); + M_32_SWAP(hdrp->ffactor); + M_32_SWAP(hdrp->nkeys); + M_32_SWAP(hdrp->hdrpages); + M_32_SWAP(hdrp->h_charkey); + for (i = 0; i < NCACHED; i++) { + M_32_SWAP(hdrp->spares[i]); + M_16_SWAP(hdrp->bitmaps[i]); + } +} +#endif diff --git a/security/nss/lib/dbm/src/hash_buf.c b/security/nss/lib/dbm/src/hash_buf.c new file mode 100644 index 000000000..a7cd2d076 --- /dev/null +++ b/security/nss/lib/dbm/src/hash_buf.c @@ -0,0 +1,407 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)hash_buf.c 8.5 (Berkeley) 7/15/94"; +#endif /* LIBC_SCCS and not lint */ + +/* + * PACKAGE: hash + * + * DESCRIPTION: + * Contains buffer management + * + * ROUTINES: + * External + * __buf_init + * __get_buf + * __buf_free + * __reclaim_buf + * Internal + * newbuf + */ +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) +#include <sys/param.h> +#endif + +#include <errno.h> +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#ifdef DEBUG +#include <assert.h> +#endif + +#include "mcom_db.h" +#include "hash.h" +#include "page.h" +/* #include "extern.h" */ + +static BUFHEAD *newbuf(HTAB *, uint32, BUFHEAD *); + +/* Unlink B from its place in the lru */ +#define BUF_REMOVE(B) \ + { \ + (B)->prev->next = (B)->next; \ + (B)->next->prev = (B)->prev; \ + } + +/* Insert B after P */ +#define BUF_INSERT(B, P) \ + { \ + (B)->next = (P)->next; \ + (B)->prev = (P); \ + (P)->next = (B); \ + (B)->next->prev = (B); \ + } + +#define MRU hashp->bufhead.next +#define LRU hashp->bufhead.prev + +#define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead) +#define LRU_INSERT(B) BUF_INSERT((B), LRU) + +/* + * We are looking for a buffer with address "addr". If prev_bp is NULL, then + * address is a bucket index. If prev_bp is not NULL, then it points to the + * page previous to an overflow page that we are trying to find. + * + * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer + * be valid. Therefore, you must always verify that its address matches the + * address you are seeking. + */ +extern BUFHEAD * +__get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage) +/* If prev_bp set, indicates a new overflow page. */ +{ + register BUFHEAD *bp; + register uint32 is_disk_mask; + register int is_disk, segment_ndx = 0; + SEGMENT segp = 0; + + is_disk = 0; + is_disk_mask = 0; + if (prev_bp) { + bp = prev_bp->ovfl; + if (!bp || (bp->addr != addr)) + bp = NULL; + if (!newpage) + is_disk = BUF_DISK; + } else { + /* Grab buffer out of directory */ + segment_ndx = addr & (hashp->SGSIZE - 1); + + /* valid segment ensured by __call_hash() */ + segp = hashp->dir[addr >> hashp->SSHIFT]; +#ifdef DEBUG + assert(segp != NULL); +#endif + + bp = PTROF(segp[segment_ndx]); + + is_disk_mask = ISDISK(segp[segment_ndx]); + is_disk = is_disk_mask || !hashp->new_file; + } + + if (!bp) { + bp = newbuf(hashp, addr, prev_bp); + if (!bp) + return (NULL); + if (__get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0)) { + /* free bp and its page */ + if (prev_bp) { + /* if prev_bp is set then the new page that + * failed is hooked onto prev_bp as an overflow page. + * if we don't remove the pointer to the bad page + * we may try and access it later and we will die + * horribly because it will have already been + * free'd and overwritten with bogus data. + */ + prev_bp->ovfl = NULL; + } + BUF_REMOVE(bp); + free(bp->page); + free(bp); + return (NULL); + } + + if (!prev_bp) { +#if 0 + /* 16 bit windows and mac can't handle the + * oring of the is disk flag. + */ + segp[segment_ndx] = + (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask); +#else + /* set the is_disk thing inside the structure + */ + bp->is_disk = is_disk_mask; + segp[segment_ndx] = bp; +#endif + } + } else { + BUF_REMOVE(bp); + MRU_INSERT(bp); + } + return (bp); +} + +/* + * We need a buffer for this page. Either allocate one, or evict a resident + * one (if we have as many buffers as we're allowed) and put this one in. + * + * If newbuf finds an error (returning NULL), it also sets errno. + */ +static BUFHEAD * +newbuf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp) +{ + register BUFHEAD *bp; /* The buffer we're going to use */ + register BUFHEAD *xbp; /* Temp pointer */ + register BUFHEAD *next_xbp; + SEGMENT segp; + int segment_ndx; + uint16 oaddr, *shortp; + + oaddr = 0; + bp = LRU; + /* + * If LRU buffer is pinned, the buffer pool is too small. We need to + * allocate more buffers. + */ + if (hashp->nbufs || (bp->flags & BUF_PIN)) { + /* Allocate a new one */ + if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL) + return (NULL); + + /* this memset is supposedly unnecessary but lets add + * it anyways. + */ + memset(bp, 0xff, sizeof(BUFHEAD)); + + if ((bp->page = (char *)malloc((size_t)hashp->BSIZE)) == NULL) { + free(bp); + return (NULL); + } + + /* this memset is supposedly unnecessary but lets add + * it anyways. + */ + memset(bp->page, 0xff, (size_t)hashp->BSIZE); + + if (hashp->nbufs) + hashp->nbufs--; + } else { + /* Kick someone out */ + BUF_REMOVE(bp); + /* + * If this is an overflow page with addr 0, it's already been + * flushed back in an overflow chain and initialized. + */ + if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) { + /* + * Set oaddr before __put_page so that you get it + * before bytes are swapped. + */ + shortp = (uint16 *)bp->page; + if (shortp[0]) { + if (shortp[0] > (hashp->BSIZE / sizeof(uint16))) { + return (NULL); + } + oaddr = shortp[shortp[0] - 1]; + } + if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page, + bp->addr, (int)IS_BUCKET(bp->flags), 0)) + return (NULL); + /* + * Update the pointer to this page (i.e. invalidate it). + * + * If this is a new file (i.e. we created it at open + * time), make sure that we mark pages which have been + * written to disk so we retrieve them from disk later, + * rather than allocating new pages. + */ + if (IS_BUCKET(bp->flags)) { + segment_ndx = bp->addr & (hashp->SGSIZE - 1); + segp = hashp->dir[bp->addr >> hashp->SSHIFT]; +#ifdef DEBUG + assert(segp != NULL); +#endif + + if (hashp->new_file && + ((bp->flags & BUF_MOD) || + ISDISK(segp[segment_ndx]))) + segp[segment_ndx] = (BUFHEAD *)BUF_DISK; + else + segp[segment_ndx] = NULL; + } + /* + * Since overflow pages can only be access by means of + * their bucket, free overflow pages associated with + * this bucket. + */ + for (xbp = bp; xbp->ovfl;) { + next_xbp = xbp->ovfl; + xbp->ovfl = 0; + xbp = next_xbp; + + /* leave pinned pages alone, we are still using + * them. */ + if (xbp->flags & BUF_PIN) { + continue; + } + + /* Check that ovfl pointer is up date. */ + if (IS_BUCKET(xbp->flags) || + (oaddr != xbp->addr)) + break; + + shortp = (uint16 *)xbp->page; + if (shortp[0]) { + /* LJM is the number of reported + * pages way too much? + */ + if (shortp[0] > hashp->BSIZE / sizeof(uint16)) + return NULL; + /* set before __put_page */ + oaddr = shortp[shortp[0] - 1]; + } + if ((xbp->flags & BUF_MOD) && __put_page(hashp, + xbp->page, xbp->addr, 0, 0)) + return (NULL); + xbp->addr = 0; + xbp->flags = 0; + BUF_REMOVE(xbp); + LRU_INSERT(xbp); + } + } + } + + /* Now assign this buffer */ + bp->addr = addr; +#ifdef DEBUG1 + (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n", + bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0); +#endif + bp->ovfl = NULL; + if (prev_bp) { +/* + * If prev_bp is set, this is an overflow page, hook it in to + * the buffer overflow links. + */ +#ifdef DEBUG1 + (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n", + prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0), + (bp ? bp->addr : 0)); +#endif + prev_bp->ovfl = bp; + bp->flags = 0; + } else + bp->flags = BUF_BUCKET; + MRU_INSERT(bp); + return (bp); +} + +extern void +__buf_init(HTAB *hashp, int32 nbytes) +{ + BUFHEAD *bfp; + int npages; + + bfp = &(hashp->bufhead); + npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT; + npages = PR_MAX(npages, MIN_BUFFERS); + + hashp->nbufs = npages; + bfp->next = bfp; + bfp->prev = bfp; + /* + * This space is calloc'd so these are already null. + * + * bfp->ovfl = NULL; + * bfp->flags = 0; + * bfp->page = NULL; + * bfp->addr = 0; + */ +} + +extern int +__buf_free(HTAB *hashp, int do_free, int to_disk) +{ + BUFHEAD *bp; + int status = -1; + + /* Need to make sure that buffer manager has been initialized */ + if (!LRU) + return (0); + for (bp = LRU; bp != &hashp->bufhead;) { + /* Check that the buffer is valid */ + if (bp->addr || IS_BUCKET(bp->flags)) { + if (to_disk && (bp->flags & BUF_MOD) && + (status = __put_page(hashp, bp->page, + bp->addr, IS_BUCKET(bp->flags), 0))) { + + if (do_free) { + if (bp->page) + free(bp->page); + BUF_REMOVE(bp); + free(bp); + } + + return (status); + } + } + /* Check if we are freeing stuff */ + if (do_free) { + if (bp->page) + free(bp->page); + BUF_REMOVE(bp); + free(bp); + bp = LRU; + } else + bp = bp->prev; + } + return (0); +} + +extern void +__reclaim_buf(HTAB *hashp, BUFHEAD *bp) +{ + bp->ovfl = 0; + bp->addr = 0; + bp->flags = 0; + BUF_REMOVE(bp); + LRU_INSERT(bp); +} diff --git a/security/nss/lib/dbm/src/manifest.mn b/security/nss/lib/dbm/src/manifest.mn new file mode 100644 index 000000000..119044407 --- /dev/null +++ b/security/nss/lib/dbm/src/manifest.mn @@ -0,0 +1,28 @@ +#! gmake +# +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +CORE_DEPTH = ../../.. + +MODULE = dbm + +# +# memmove.c, snprintf.c, and strerror.c are not in CSRCS because +# the Standard C Library has memmove and strerror and DBM is not +# using snprintf. +# + +CSRCS = db.c \ + h_bigkey.c \ + h_func.c \ + h_log2.c \ + h_page.c \ + hash.c \ + hash_buf.c \ + mktemp.c \ + dirent.c \ + $(NULL) + +LIBRARY_NAME = dbm diff --git a/security/nss/lib/dbm/src/memmove.c b/security/nss/lib/dbm/src/memmove.c new file mode 100644 index 000000000..135185b35 --- /dev/null +++ b/security/nss/lib/dbm/src/memmove.c @@ -0,0 +1,146 @@ +#if defined(__sun) && !defined(__SVR4) +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)bcopy.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <string.h> + +/* + * sizeof(word) MUST BE A POWER OF TWO + * SO THAT wmask BELOW IS ALL ONES + */ +typedef int word; /* "word" used for optimal copy speed */ + +#define wsize sizeof(word) +#define wmask (wsize - 1) + +/* + * Copy a block of memory, handling overlap. + * This is the routine that actually implements + * (the portable versions of) bcopy, memcpy, and memmove. + */ +#ifdef MEMCOPY +void * + memcpy(dst0, src0, length) +#else +#ifdef MEMMOVE +void * + memmove(dst0, src0, length) +#else +void + bcopy(src0, dst0, length) +#endif +#endif + void *dst0; +const void *src0; +register size_t length; +{ + register char *dst = dst0; + register const char *src = src0; + register size_t t; + + if (length == 0 || dst == src) /* nothing to do */ + goto done; + +/* + * Macros: loop-t-times; and loop-t-times, t>0 + */ +#define TLOOP(s) \ + if (t) \ + TLOOP1(s) +#define TLOOP1(s) \ + do { \ + s; \ + } while (--t) + + if ((unsigned long)dst < (unsigned long)src) { + /* + * Copy forward. + */ + t = (int)src; /* only need low bits */ + if ((t | (int)dst) & wmask) { + /* + * Try to align operands. This cannot be done + * unless the low bits match. + */ + if ((t ^ (int)dst) & wmask || length < wsize) + t = length; + else + t = wsize - (t & wmask); + length -= t; + TLOOP1(*dst++ = *src++); + } + /* + * Copy whole words, then mop up any trailing bytes. + */ + t = length / wsize; + TLOOP(*(word *)dst = *(word *)src; src += wsize; dst += wsize); + t = length & wmask; + TLOOP(*dst++ = *src++); + } else { + /* + * Copy backwards. Otherwise essentially the same. + * Alignment works as before, except that it takes + * (t&wmask) bytes to align, not wsize-(t&wmask). + */ + src += length; + dst += length; + t = (int)src; + if ((t | (int)dst) & wmask) { + if ((t ^ (int)dst) & wmask || length <= wsize) + t = length; + else + t &= wmask; + length -= t; + TLOOP1(*--dst = *--src); + } + t = length / wsize; + TLOOP(src -= wsize; dst -= wsize; *(word *)dst = *(word *)src); + t = length & wmask; + TLOOP(*--dst = *--src); + } +done: +#if defined(MEMCOPY) || defined(MEMMOVE) + return (dst0); +#else + return; +#endif +} +#endif /* no __sgi */ + +/* Some compilers don't like an empty source file. */ +static int dummy = 0; diff --git a/security/nss/lib/dbm/src/mktemp.c b/security/nss/lib/dbm/src/mktemp.c new file mode 100644 index 000000000..b668ece18 --- /dev/null +++ b/security/nss/lib/dbm/src/mktemp.c @@ -0,0 +1,149 @@ +/* + * Copyright (c) 1987, 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)mktemp.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#ifdef macintosh +#include <unix.h> +#else +#include <sys/types.h> +#include <sys/stat.h> +#endif +#include <fcntl.h> +#include <errno.h> +#include <stdio.h> +#include <ctype.h> +#include "mcom_db.h" + +#ifndef _WINDOWS +#include <unistd.h> +#endif + +#ifdef _WINDOWS +#include <process.h> +#include "winfile.h" +#endif + +static int _gettemp(char *path, register int *doopen, int extraFlags); + +int +mkstemp(char *path) +{ +#ifdef XP_OS2 + FILE *temp = tmpfile(); + + return (temp ? fileno(temp) : -1); +#else + int fd; + + return (_gettemp(path, &fd, 0) ? fd : -1); +#endif +} + +int +mkstempflags(char *path, int extraFlags) +{ + int fd; + + return (_gettemp(path, &fd, extraFlags) ? fd : -1); +} + +/* NB: This routine modifies its input string, and does not always restore it. +** returns 1 on success, 0 on failure. +*/ +static int +_gettemp(char *path, register int *doopen, int extraFlags) +{ + register char *start, *trv; + struct stat sbuf; + unsigned int pid; + + pid = getpid(); + for (trv = path; *trv; ++trv) + ; /* extra X's get set to 0's */ + while (*--trv == 'X') { + *trv = (pid % 10) + '0'; + pid /= 10; + } + + /* + * check the target directory; if you have six X's and it + * doesn't exist this runs for a *very* long time. + */ + for (start = trv + 1;; --trv) { + char saved; + if (trv <= path) + break; + saved = *trv; + if (saved == '/' || saved == '\\') { + int rv; + *trv = '\0'; + rv = stat(path, &sbuf); + *trv = saved; + if (rv) + return (0); + if (!S_ISDIR(sbuf.st_mode)) { + errno = ENOTDIR; + return (0); + } + break; + } + } + + for (;;) { + if (doopen) { + if ((*doopen = + open(path, O_CREAT | O_EXCL | O_RDWR | extraFlags, 0600)) >= 0) + return (1); + if (errno != EEXIST) + return (0); + } else if (stat(path, &sbuf)) + return (errno == ENOENT ? 1 : 0); + + /* tricky little algorithm for backward compatibility */ + for (trv = start;;) { + if (!*trv) + return (0); + if (*trv == 'z') + *trv++ = 'a'; + else { + if (isdigit(*trv)) + *trv = 'a'; + else + ++*trv; + break; + } + } + } + /*NOTREACHED*/ +} diff --git a/security/nss/lib/dbm/src/snprintf.c b/security/nss/lib/dbm/src/snprintf.c new file mode 100644 index 000000000..3cafacf44 --- /dev/null +++ b/security/nss/lib/dbm/src/snprintf.c @@ -0,0 +1,50 @@ +#ifndef HAVE_SNPRINTF + +#include <sys/types.h> +#include <stddef.h> +#include <stdio.h> + +#include "prtypes.h" + +#include <ncompat.h> + +#include <stdarg.h> + +int +snprintf(char *str, size_t n, const char *fmt, ...) +{ + va_list ap; +#ifdef VSPRINTF_CHARSTAR + char *rp; +#else + int rval; +#endif + va_start(ap, fmt); +#ifdef VSPRINTF_CHARSTAR + rp = vsprintf(str, fmt, ap); + va_end(ap); + return (strlen(rp)); +#else + rval = vsprintf(str, fmt, ap); + va_end(ap); + return (rval); +#endif +} + +int + vsnprintf(str, n, fmt, ap) char *str; +size_t n; +const char *fmt; +va_list ap; +{ +#ifdef VSPRINTF_CHARSTAR + return (strlen(vsprintf(str, fmt, ap))); +#else + return (vsprintf(str, fmt, ap)); +#endif +} + +#endif /* HAVE_SNPRINTF */ + +/* Some compilers don't like an empty source file. */ +static int dummy = 0; diff --git a/security/nss/lib/dbm/src/src.gyp b/security/nss/lib/dbm/src/src.gyp new file mode 100644 index 000000000..a84755e60 --- /dev/null +++ b/security/nss/lib/dbm/src/src.gyp @@ -0,0 +1,40 @@ +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. +{ + 'includes': [ + '../../../coreconf/config.gypi' + ], + 'targets': [ + { + 'target_name': 'dbm', + 'type': 'static_library', + 'sources': [ + 'db.c', + 'dirent.c', + 'h_bigkey.c', + 'h_func.c', + 'h_log2.c', + 'h_page.c', + 'hash.c', + 'hash_buf.c', + 'mktemp.c' + ], + 'dependencies': [ + '<(DEPTH)/exports.gyp:dbm_exports' + ] + } + ], + 'target_defaults': { + 'defines': [ + 'STDC_HEADERS', + 'HAVE_STRERROR', + 'HAVE_SNPRINTF', + 'MEMMOVE', + '__DBINTERFACE_PRIVATE' + ] + }, + 'variables': { + 'module': 'dbm' + } +}
\ No newline at end of file diff --git a/security/nss/lib/dbm/src/strerror.c b/security/nss/lib/dbm/src/strerror.c new file mode 100644 index 000000000..d64918b5c --- /dev/null +++ b/security/nss/lib/dbm/src/strerror.c @@ -0,0 +1,73 @@ +/* + * Copyright (c) 1988, 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. ***REMOVED*** - see + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change + * 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[] = "@(#)strerror.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <string.h> + +#ifdef _DLL +#define sys_nerr (*_sys_nerr_dll) +#endif + +#ifndef HAVE_STRERROR +#ifndef _AFXDLL +char * + strerror(num) int num; +{ + extern int sys_nerr; + extern char *sys_errlist[]; +#define UPREFIX "Unknown error: " + static char ebuf[40] = UPREFIX; /* 64-bit number + slop */ + register unsigned int errnum; + register char *p, *t; + char tmp[40]; + + errnum = num; /* convert to unsigned */ + if (errnum < sys_nerr) + return (sys_errlist[errnum]); + + /* Do this by hand, so we don't include stdio(3). */ + t = tmp; + do { + *t++ = "0123456789"[errnum % 10]; + } while (errnum /= 10); + for (p = ebuf + sizeof(UPREFIX) - 1;;) { + *p++ = *--t; + if (t <= tmp) + break; + } + return (ebuf); +} + +#endif +#endif /* !HAVE_STRERROR */ |