diff options
Diffstat (limited to 'security/nss/lib/dbm')
36 files changed, 7366 insertions, 0 deletions
diff --git a/security/nss/lib/dbm/Makefile b/security/nss/lib/dbm/Makefile new file mode 100644 index 000000000..a4df914b2 --- /dev/null +++ b/security/nss/lib/dbm/Makefile @@ -0,0 +1,52 @@ +#! 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) # +####################################################################### + + + +####################################################################### +# (4) Include "local" platform-dependent assignments (OPTIONAL). # +####################################################################### + + + +####################################################################### +# (5) Execute "global" rules. (OPTIONAL) # +####################################################################### + +include $(CORE_DEPTH)/coreconf/rules.mk + +####################################################################### +# (6) Execute "component" rules. (OPTIONAL) # +####################################################################### + + + +####################################################################### +# (7) Execute "local" rules. (OPTIONAL). # +####################################################################### + +coreconf_hack: + cd ../coreconf; gmake + gmake import + +RelEng_bld: coreconf_hack + gmake diff --git a/security/nss/lib/dbm/config/config.mk b/security/nss/lib/dbm/config/config.mk new file mode 100644 index 000000000..9ad98af82 --- /dev/null +++ b/security/nss/lib/dbm/config/config.mk @@ -0,0 +1,35 @@ +#! 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/. + +# +# These macros are defined by mozilla's configure script. +# We define them manually here. +# + +DEFINES += -DSTDC_HEADERS -DHAVE_STRERROR + +# +# Most platforms have snprintf, so it's simpler to list the exceptions. +# +HAVE_SNPRINTF = 1 +# +# OSF1 V4.0D doesn't have snprintf but V5.0A does. +# +ifeq ($(OS_TARGET)$(OS_RELEASE),OSF1V4.0D) +HAVE_SNPRINTF = +endif +ifdef HAVE_SNPRINTF +DEFINES += -DHAVE_SNPRINTF +endif + +ifeq (,$(filter-out DGUX NCR ReliantUNIX SCO_SV SCOOS UNIXWARE,$(OS_TARGET))) +DEFINES += -DHAVE_SYS_BYTEORDER_H +endif + +# +# None of the platforms that we are interested in need to +# define HAVE_MEMORY_H. +# diff --git a/security/nss/lib/dbm/include/Makefile b/security/nss/lib/dbm/include/Makefile new file mode 100644 index 000000000..4c9e4e939 --- /dev/null +++ b/security/nss/lib/dbm/include/Makefile @@ -0,0 +1,47 @@ +#! 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) # +####################################################################### + + + +####################################################################### +# (4) Include "local" platform-dependent assignments (OPTIONAL). # +####################################################################### + + + +####################################################################### +# (5) Execute "global" rules. (OPTIONAL) # +####################################################################### + +include $(CORE_DEPTH)/coreconf/rules.mk + +####################################################################### +# (6) Execute "component" rules. (OPTIONAL) # +####################################################################### + + + +####################################################################### +# (7) Execute "local" rules. (OPTIONAL). # +####################################################################### + +export:: private_export diff --git a/security/nss/lib/dbm/include/exports.gyp b/security/nss/lib/dbm/include/exports.gyp new file mode 100644 index 000000000..e80d769ca --- /dev/null +++ b/security/nss/lib/dbm/include/exports.gyp @@ -0,0 +1,38 @@ +# 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': 'lib_dbm_include_exports', + 'type': 'none', + 'copies': [ + { + 'files': [ + 'mcom_db.h', + 'ncompat.h', + 'winfile.h' + ], + 'destination': '<(nss_public_dist_dir)/<(module)' + }, + { + 'files': [ + 'extern.h', + 'hash.h', + 'hsearch.h', + 'page.h', + 'queue.h', + 'search.h' + ], + 'destination': '<(nss_private_dist_dir)/<(module)' + } + ] + } + ], + 'variables': { + 'module': 'dbm' + } +} diff --git a/security/nss/lib/dbm/include/extern.h b/security/nss/lib/dbm/include/extern.h new file mode 100644 index 000000000..897369fb8 --- /dev/null +++ b/security/nss/lib/dbm/include/extern.h @@ -0,0 +1,63 @@ +/*- + * Copyright (c) 1991, 1993, 1994 + * 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. + * + * @(#)extern.h 8.4 (Berkeley) 6/16/94 + */ + +BUFHEAD *__add_ovflpage(HTAB *, BUFHEAD *); +int __addel(HTAB *, BUFHEAD *, const DBT *, const DBT *); +int __big_delete(HTAB *, BUFHEAD *); +int __big_insert(HTAB *, BUFHEAD *, const DBT *, const DBT *); +int __big_keydata(HTAB *, BUFHEAD *, DBT *, DBT *, int); +int __big_return(HTAB *, BUFHEAD *, int, DBT *, int); +int __big_split(HTAB *, BUFHEAD *, BUFHEAD *, BUFHEAD *, + uint32, uint32, SPLIT_RETURN *); +int __buf_free(HTAB *, int, int); +void __buf_init(HTAB *, int); +uint32 __call_hash(HTAB *, char *, size_t); +int __delpair(HTAB *, BUFHEAD *, int); +int __expand_table(HTAB *); +int __find_bigpair(HTAB *, BUFHEAD *, int, char *, int); +uint16 __find_last_page(HTAB *, BUFHEAD **); +void __free_ovflpage(HTAB *, BUFHEAD *); +BUFHEAD *__get_buf(HTAB *, uint32, BUFHEAD *, int); +int __get_page(HTAB *, char *, uint32, int, int, int); +int __ibitmap(HTAB *, int, int, int); +uint32 __log2(uint32); +int __put_page(HTAB *, char *, uint32, int, int); +void __reclaim_buf(HTAB *, BUFHEAD *); +int __split_page(HTAB *, uint32, uint32); + +/* Default hash routine. */ +extern uint32 (*__default_hash)(const void *, size_t); + +#ifdef HASH_STATISTICS +extern int hash_accesses, hash_collisions, hash_expansions, hash_overflows; +#endif diff --git a/security/nss/lib/dbm/include/hash.h b/security/nss/lib/dbm/include/hash.h new file mode 100644 index 000000000..7da51dc64 --- /dev/null +++ b/security/nss/lib/dbm/include/hash.h @@ -0,0 +1,341 @@ +/*- + * 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. + * + * @(#)hash.h 8.3 (Berkeley) 5/31/94 + */ + +/* Operations */ + +#include <stdio.h> +#include "mcom_db.h" +typedef enum { + HASH_GET, + HASH_PUT, + HASH_PUTNEW, + HASH_DELETE, + HASH_FIRST, + HASH_NEXT +} ACTION; + +/* Buffer Management structures */ +typedef struct _bufhead BUFHEAD; + +struct _bufhead { + BUFHEAD *prev; /* LRU links */ + BUFHEAD *next; /* LRU links */ + BUFHEAD *ovfl; /* Overflow page buffer header */ + uint32 addr; /* Address of this page */ + char *page; /* Actual page data */ + char is_disk; + char flags; +#define BUF_MOD 0x0001 +#define BUF_DISK 0x0002 +#define BUF_BUCKET 0x0004 +#define BUF_PIN 0x0008 +}; + +#define IS_BUCKET(X) ((X)&BUF_BUCKET) + +typedef BUFHEAD **SEGMENT; + +typedef int DBFILE_PTR; +#define NO_FILE -1 +#ifdef macintosh +#define DBFILE_OPEN(path, flag, mode) open((path), flag) +#define EXISTS(path) +#else +#define DBFILE_OPEN(path, flag, mode) open((path), (flag), (mode)) +#endif +/* Hash Table Information */ +typedef struct hashhdr { /* Disk resident portion */ + int32 magic; /* Magic NO for hash tables */ + int32 version; /* Version ID */ + uint32 lorder; /* Byte Order */ + int32 bsize; /* Bucket/Page Size */ + int32 bshift; /* Bucket shift */ + int32 dsize; /* Directory Size */ + int32 ssize; /* Segment Size */ + int32 sshift; /* Segment shift */ + int32 ovfl_point; /* Where overflow pages are being + * allocated */ + int32 last_freed; /* Last overflow page freed */ + int32 max_bucket; /* ID of Maximum bucket in use */ + int32 high_mask; /* Mask to modulo into entire table */ + int32 low_mask; /* Mask to modulo into lower half of + * table */ + int32 ffactor; /* Fill factor */ + int32 nkeys; /* Number of keys in hash table */ + int32 hdrpages; /* Size of table header */ + uint32 h_charkey; /* value of hash(CHARKEY) */ +#define NCACHED 32 /* number of bit maps and spare \ + * points */ + int32 spares[NCACHED]; /* spare pages for overflow */ + uint16 bitmaps[NCACHED]; /* address of overflow page + * bitmaps */ +} HASHHDR; + +typedef struct htab { /* Memory resident data structure */ + HASHHDR hdr; /* Header */ + int nsegs; /* Number of allocated segments */ + int exsegs; /* Number of extra allocated + * segments */ + uint32 /* Hash function */ + (*hash)(const void *, size_t); + int flags; /* Flag values */ + DBFILE_PTR fp; /* File pointer */ + char *filename; + char *tmp_buf; /* Temporary Buffer for BIG data */ + char *tmp_key; /* Temporary Buffer for BIG keys */ + BUFHEAD *cpage; /* Current page */ + int cbucket; /* Current bucket */ + int cndx; /* Index of next item on cpage */ + int dbmerrno; /* Error Number -- for DBM + * compatability */ + int new_file; /* Indicates if fd is backing store + * or no */ + int save_file; /* Indicates whether we need to flush + * file at + * exit */ + uint32 *mapp[NCACHED]; /* Pointers to page maps */ + int nmaps; /* Initial number of bitmaps */ + int nbufs; /* Number of buffers left to + * allocate */ + BUFHEAD bufhead; /* Header of buffer lru list */ + SEGMENT *dir; /* Hash Bucket directory */ + off_t file_size; /* in bytes */ + char is_temp; /* unlink file on close */ + char updateEOF; /* force EOF update on flush */ +} HTAB; + +/* + * Constants + */ +#define DATABASE_CORRUPTED_ERROR -999 /* big ugly abort, delete database */ +#define OLD_MAX_BSIZE 65536 /* 2^16 */ +#define MAX_BSIZE 32l * 1024l /* 2^15 */ +#define MIN_BUFFERS 6 +#define MINHDRSIZE 512 +#define DEF_BUFSIZE 65536l /* 64 K */ +#define DEF_BUCKET_SIZE 4096 +#define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ +#define DEF_SEGSIZE 256 +#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ +#define DEF_DIRSIZE 256 +#define DEF_FFACTOR 65536l +#define MIN_FFACTOR 4 +#define SPLTMAX 8 +#define CHARKEY "%$sniglet^&" +#define NUMKEY 1038583l +#define BYTE_SHIFT 3 +#define INT_TO_BYTE 2 +#define INT_BYTE_SHIFT 5 +#define ALL_SET ((uint32)0xFFFFFFFF) +#define ALL_CLEAR 0 + +#define PTROF(X) ((ptrdiff_t)(X) == BUF_DISK ? 0 : (X)) +#define ISDISK(X) ((X) ? ((ptrdiff_t)(X) == BUF_DISK ? BUF_DISK \ + : (X)->is_disk) \ + : 0) + +#define BITS_PER_MAP 32 + +/* Given the address of the beginning of a big map, clear/set the nth bit */ +#define CLRBIT(A, N) ((A)[(N) / BITS_PER_MAP] &= ~(1 << ((N) % BITS_PER_MAP))) +#define SETBIT(A, N) ((A)[(N) / BITS_PER_MAP] |= (1 << ((N) % BITS_PER_MAP))) +#define ISSET(A, N) ((A)[(N) / BITS_PER_MAP] & (1 << ((N) % BITS_PER_MAP))) + +/* Overflow management */ +/* + * Overflow page numbers are allocated per split point. At each doubling of + * the table, we can allocate extra pages. So, an overflow page number has + * the top 5 bits indicate which split point and the lower 11 bits indicate + * which page at that split point is indicated (pages within split points are + * numberered starting with 1). + */ + +#define SPLITSHIFT 11 +#define SPLITMASK 0x7FF +#define SPLITNUM(N) (((uint32)(N)) >> SPLITSHIFT) +#define OPAGENUM(N) ((N)&SPLITMASK) +#define OADDR_OF(S, O) ((uint32)((uint32)(S) << SPLITSHIFT) + (O)) + +#define BUCKET_TO_PAGE(B) \ + (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((uint32)((B) + 1)) - 1] : 0) +#define OADDR_TO_PAGE(B) \ + BUCKET_TO_PAGE((1 << SPLITNUM((B))) - 1) + OPAGENUM((B)); + +/* + * page.h contains a detailed description of the page format. + * + * Normally, keys and data are accessed from offset tables in the top of + * each page which point to the beginning of the key and data. There are + * four flag values which may be stored in these offset tables which indicate + * the following: + * + * + * OVFLPAGE Rather than a key data pair, this pair contains + * the address of an overflow page. The format of + * the pair is: + * OVERFLOW_PAGE_NUMBER OVFLPAGE + * + * PARTIAL_KEY This must be the first key/data pair on a page + * and implies that page contains only a partial key. + * That is, the key is too big to fit on a single page + * so it starts on this page and continues on the next. + * The format of the page is: + * KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE + * + * KEY_OFF -- offset of the beginning of the key + * PARTIAL_KEY -- 1 + * OVFL_PAGENO - page number of the next overflow page + * OVFLPAGE -- 0 + * + * FULL_KEY This must be the first key/data pair on the page. It + * is used in two cases. + * + * Case 1: + * There is a complete key on the page but no data + * (because it wouldn't fit). The next page contains + * the data. + * + * Page format it: + * KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE + * + * KEY_OFF -- offset of the beginning of the key + * FULL_KEY -- 2 + * OVFL_PAGENO - page number of the next overflow page + * OVFLPAGE -- 0 + * + * Case 2: + * This page contains no key, but part of a large + * data field, which is continued on the next page. + * + * Page format it: + * DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE + * + * KEY_OFF -- offset of the beginning of the data on + * this page + * FULL_KEY -- 2 + * OVFL_PAGENO - page number of the next overflow page + * OVFLPAGE -- 0 + * + * FULL_KEY_DATA + * This must be the first key/data pair on the page. + * There are two cases: + * + * Case 1: + * This page contains a key and the beginning of the + * data field, but the data field is continued on the + * next page. + * + * Page format is: + * KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF + * + * KEY_OFF -- offset of the beginning of the key + * FULL_KEY_DATA -- 3 + * OVFL_PAGENO - page number of the next overflow page + * DATA_OFF -- offset of the beginning of the data + * + * Case 2: + * This page contains the last page of a big data pair. + * There is no key, only the tail end of the data + * on this page. + * + * Page format is: + * DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE> + * + * DATA_OFF -- offset of the beginning of the data on + * this page + * FULL_KEY_DATA -- 3 + * OVFL_PAGENO - page number of the next overflow page + * OVFLPAGE -- 0 + * + * OVFL_PAGENO and OVFLPAGE are optional (they are + * not present if there is no next page). + */ + +#define OVFLPAGE 0 +#define PARTIAL_KEY 1 +#define FULL_KEY 2 +#define FULL_KEY_DATA 3 +#define REAL_KEY 4 + +/* Short hands for accessing structure */ +#undef BSIZE +#define BSIZE hdr.bsize +#undef BSHIFT +#define BSHIFT hdr.bshift +#define DSIZE hdr.dsize +#define SGSIZE hdr.ssize +#define SSHIFT hdr.sshift +#define LORDER hdr.lorder +#define OVFL_POINT hdr.ovfl_point +#define LAST_FREED hdr.last_freed +#define MAX_BUCKET hdr.max_bucket +#define FFACTOR hdr.ffactor +#define HIGH_MASK hdr.high_mask +#define LOW_MASK hdr.low_mask +#define NKEYS hdr.nkeys +#define HDRPAGES hdr.hdrpages +#define SPARES hdr.spares +#define BITMAPS hdr.bitmaps +#define VERSION hdr.version +#define MAGIC hdr.magic +#define NEXT_FREE hdr.next_free +#define H_CHARKEY hdr.h_charkey + +extern uint32 (*__default_hash)(const void *, size_t); +void __buf_init(HTAB *hashp, int32 nbytes); +int __big_delete(HTAB *hashp, BUFHEAD *bufp); +BUFHEAD *__get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage); +uint32 __call_hash(HTAB *hashp, char *k, size_t len); +#include "page.h" +extern int __big_split(HTAB *hashp, BUFHEAD *op, BUFHEAD *np, + BUFHEAD *big_keyp, uint32 addr, uint32 obucket, SPLIT_RETURN *ret); +void __free_ovflpage(HTAB *hashp, BUFHEAD *obufp); +BUFHEAD *__add_ovflpage(HTAB *hashp, BUFHEAD *bufp); +int __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val); +int __expand_table(HTAB *hashp); +uint32 __log2(uint32 num); +void __reclaim_buf(HTAB *hashp, BUFHEAD *bp); +int __get_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_disk, int is_bitmap); +int __put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap); +int __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx); +int __buf_free(HTAB *hashp, int do_free, int to_disk); +int __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size); +uint16 __find_last_page(HTAB *hashp, BUFHEAD **bpp); +int __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val); +int __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current); +int __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx); +int __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set); +int __split_page(HTAB *hashp, uint32 obucket, uint32 nbucket); diff --git a/security/nss/lib/dbm/include/hsearch.h b/security/nss/lib/dbm/include/hsearch.h new file mode 100644 index 000000000..d6fe0d93d --- /dev/null +++ b/security/nss/lib/dbm/include/hsearch.h @@ -0,0 +1,50 @@ +/*- + * 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. + * + * @(#)search.h 8.1 (Berkeley) 6/4/93 + */ + +/* Backward compatibility to hsearch interface. */ +typedef struct entry { + char *key; + char *data; +} ENTRY; + +typedef enum { + FIND, + ENTER +} ACTION; + +int hcreate(unsigned int); +void hdestroy(void); +ENTRY *hsearch(ENTRY, ACTION); diff --git a/security/nss/lib/dbm/include/include.gyp b/security/nss/lib/dbm/include/include.gyp new file mode 100644 index 000000000..69f9c883d --- /dev/null +++ b/security/nss/lib/dbm/include/include.gyp @@ -0,0 +1,12 @@ +# 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': [], + 'variables': { + 'module': 'dbm' + } +}
\ No newline at end of file diff --git a/security/nss/lib/dbm/include/manifest.mn b/security/nss/lib/dbm/include/manifest.mn new file mode 100644 index 000000000..64b6fdac0 --- /dev/null +++ b/security/nss/lib/dbm/include/manifest.mn @@ -0,0 +1,23 @@ +#! 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 + +EXPORTS = mcom_db.h \ + ncompat.h \ + winfile.h \ + $(NULL) + +PRIVATE_EXPORTS = hsearch.h \ + page.h \ + extern.h \ + queue.h \ + hash.h \ + search.h \ + $(NULL) + diff --git a/security/nss/lib/dbm/include/mcom_db.h b/security/nss/lib/dbm/include/mcom_db.h new file mode 100644 index 000000000..0a4f6dc14 --- /dev/null +++ b/security/nss/lib/dbm/include/mcom_db.h @@ -0,0 +1,423 @@ +/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/*- + * Copyright (c) 1990, 1993, 1994 + * 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. + * + * @(#)db.h 8.7 (Berkeley) 6/16/94 + */ + +#ifndef _DB_H_ +#define _DB_H_ + +#ifndef macintosh +#include <sys/types.h> +#endif +#include "prtypes.h" + +#if !defined(XP_BEOS) && !defined(XP_OS2) && !defined(XP_UNIX) || defined(NTO) +typedef PRUintn uint; +#endif +typedef PRUint8 uint8; +typedef PRUint16 uint16; +/* On AIX 5.2, sys/inttypes.h (which is included by sys/types.h) + * defines the types int8, int16, int32, and int64. */ +#if !defined(AIX) +typedef PRInt32 int32; +#endif +typedef PRUint32 uint32; + +#include <limits.h> + +#ifdef __DBINTERFACE_PRIVATE + +#ifdef HAVE_SYS_BYTEORDER_H +#include <sys/byteorder.h> +#endif + +#if defined(__linux) || defined(__BEOS__) +#include <endian.h> +#ifndef BYTE_ORDER +#define BYTE_ORDER __BYTE_ORDER +#define BIG_ENDIAN __BIG_ENDIAN +#define LITTLE_ENDIAN __LITTLE_ENDIAN +#endif +#endif /* __linux */ + +#ifdef __sgi +#define BYTE_ORDER BIG_ENDIAN +#define BIG_ENDIAN 4321 +#define LITTLE_ENDIAN 1234 /* LSB first: i386, vax, all NT risc */ +#endif + +#ifdef __sun +#define BIG_ENDIAN 4321 +#define LITTLE_ENDIAN 1234 /* LSB first: i386, vax, all NT risc */ + +#ifndef __SVR4 +/* compat.h is only in 4.1.3 machines. - dp */ +#include <compat.h> +#endif + +/* XXX - dp + * Need to find a general way of defining endian-ness in SunOS 5.3 + * SunOS 5.4 defines _BIG_ENDIAN and _LITTLE_ENDIAN + * SunOS 5.3 does nothing like this. + */ + +#ifndef BYTE_ORDER + +#if defined(_BIG_ENDIAN) +#define BYTE_ORDER BIG_ENDIAN +#elif defined(_LITTLE_ENDIAN) +#define BYTE_ORDER LITTLE_ENDIAN +#elif !defined(__SVR4) +/* 4.1.3 is always BIG_ENDIAN as it was released only on sparc platforms. */ +#define BYTE_ORDER BIG_ENDIAN +#elif !defined(vax) && !defined(ntohl) && !defined(lint) && !defined(i386) +/* 5.3 big endian. Copied this above line from sys/byteorder.h */ +/* Now we are in a 5.3 SunOS rather non 5.4 or above SunOS */ +#define BYTE_ORDER BIG_ENDIAN +#else +#define BYTE_ORDER LITTLE_ENDIAN +#endif + +#endif /* !BYTE_ORDER */ +#endif /* __sun */ + +#if defined(__hpux) || defined(__hppa) +#define BYTE_ORDER BIG_ENDIAN +#define BIG_ENDIAN 4321 +#define LITTLE_ENDIAN 1234 /* LSB first: i386, vax, all NT risc */ +#endif + +#if defined(AIXV3) || defined(AIX) +/* BYTE_ORDER, LITTLE_ENDIAN, BIG_ENDIAN are all defined here */ +#include <sys/machine.h> +#endif + +/* Digital Unix */ +#ifdef __osf__ +#include <machine/endian.h> +#endif + +#ifdef __alpha +#ifndef WIN32 +#else +/* Alpha NT */ +#define BYTE_ORDER LITTLE_ENDIAN +#define BIG_ENDIAN 4321 +#define LITTLE_ENDIAN 1234 +#endif +#endif + +#ifdef NCR +#include <sys/endian.h> +#endif + +#ifdef __QNX__ +#ifdef __QNXNTO__ +#include <sys/param.h> +#else +#define LITTLE_ENDIAN 1234 +#define BIG_ENDIAN 4321 +#define BYTE_ORDER LITTLE_ENDIAN +#endif +#endif + +#ifdef SNI +/* #include <sys/hetero.h> */ +#define BYTE_ORDER BIG_ENDIAN +#define BIG_ENDIAN 4321 +#define LITTLE_ENDIAN 1234 +#endif + +#ifdef _WINDOWS +#ifdef BYTE_ORDER +#undef BYTE_ORDER +#endif + +#define BYTE_ORDER LITTLE_ENDIAN +#define LITTLE_ENDIAN 1234 /* LSB first: i386, vax, all NT risc */ +#define BIG_ENDIAN 4321 +#endif + +#ifdef macintosh +#define BIG_ENDIAN 4321 +#define LITTLE_ENDIAN 1234 +#define BYTE_ORDER BIG_ENDIAN +#endif + +#endif /* __DBINTERFACE_PRIVATE */ + +#ifdef SCO +#define MAXPATHLEN 1024 +#endif + +#include <fcntl.h> + +#if defined(_WINDOWS) || defined(XP_OS2) +#include <stdio.h> +#include <io.h> + +#ifndef XP_OS2 +#define MAXPATHLEN 1024 +#endif + +#define EFTYPE EINVAL /* POSIX 1003.1 format errno. */ + +#ifndef STDERR_FILENO +#define STDIN_FILENO 0 /* ANSI C #defines */ +#define STDOUT_FILENO 1 +#define STDERR_FILENO 2 +#endif + +#ifndef O_ACCMODE /* POSIX 1003.1 access mode mask. */ +#define O_ACCMODE (O_RDONLY | O_WRONLY | O_RDWR) +#endif +#endif + +#ifdef macintosh +#include <stdio.h> +#include "xp_mcom.h" +#define O_ACCMODE 3 /* Mask for file access modes */ +#define EFTYPE 2000 +PR_BEGIN_EXTERN_C +int mkstemp(const char *path); +PR_END_EXTERN_C +#endif /* MACINTOSH */ + +#if !defined(_WINDOWS) && !defined(macintosh) +#include <sys/stat.h> +#include <errno.h> +#endif + +/* define EFTYPE since most don't */ +#ifndef EFTYPE +#define EFTYPE EINVAL /* POSIX 1003.1 format errno. */ +#endif + +#define RET_ERROR -1 /* Return values. */ +#define RET_SUCCESS 0 +#define RET_SPECIAL 1 + +#define MAX_PAGE_NUMBER 0xffffffff /* >= # of pages in a file */ + +#ifndef __sgi +typedef uint32 pgno_t; +#endif + +#define MAX_PAGE_OFFSET 65535 /* >= # of bytes in a page */ +typedef uint16 indx_t; +#define MAX_REC_NUMBER 0xffffffff /* >= # of records in a tree */ +typedef uint32 recno_t; + +/* Key/data structure -- a Data-Base Thang. */ +typedef struct { + void *data; /* data */ + size_t size; /* data length */ +} DBT; + +/* Routine flags. */ +#define R_CURSOR 1 /* del, put, seq */ +#define __R_UNUSED 2 /* UNUSED */ +#define R_FIRST 3 /* seq */ +#define R_IAFTER 4 /* put (RECNO) */ +#define R_IBEFORE 5 /* put (RECNO) */ +#define R_LAST 6 /* seq (BTREE, RECNO) */ +#define R_NEXT 7 /* seq */ +#define R_NOOVERWRITE 8 /* put */ +#define R_PREV 9 /* seq (BTREE, RECNO) */ +#define R_SETCURSOR 10 /* put (RECNO) */ +#define R_RECNOSYNC 11 /* sync (RECNO) */ + +typedef enum { DB_BTREE, + DB_HASH, + DB_RECNO } DBTYPE; + +typedef enum { LockOutDatabase, + UnlockDatabase } DBLockFlagEnum; + +/* + * !!! + * The following flags are included in the dbopen(3) call as part of the + * open(2) flags. In order to avoid conflicts with the open flags, start + * at the top of the 16 or 32-bit number space and work our way down. If + * the open flags were significantly expanded in the future, it could be + * a problem. Wish I'd left another flags word in the dbopen call. + * + * !!! + * None of this stuff is implemented yet. The only reason that it's here + * is so that the access methods can skip copying the key/data pair when + * the DB_LOCK flag isn't set. + */ +#if UINT_MAX > 65535 +#define DB_LOCK 0x20000000 /* Do locking. */ +#define DB_SHMEM 0x40000000 /* Use shared memory. */ +#define DB_TXN 0x80000000 /* Do transactions. */ +#else +#define DB_LOCK 0x2000 /* Do locking. */ +#define DB_SHMEM 0x4000 /* Use shared memory. */ +#define DB_TXN 0x8000 /* Do transactions. */ +#endif + +/* Access method description structure. */ +typedef struct __db { + DBTYPE type; /* Underlying db type. */ + int (*close)(struct __db *); + int (*del)(const struct __db *, const DBT *, uint); + int (*get)(const struct __db *, const DBT *, DBT *, uint); + int (*put)(const struct __db *, DBT *, const DBT *, uint); + int (*seq)(const struct __db *, DBT *, DBT *, uint); + int (*sync)(const struct __db *, uint); + void *internal; /* Access method private. */ + int (*fd)(const struct __db *); +} DB; + +#define BTREEMAGIC 0x053162 +#define BTREEVERSION 3 + +/* Structure used to pass parameters to the btree routines. */ +typedef struct { +#define R_DUP 0x01 /* duplicate keys */ + uint32 flags; + uint cachesize; /* bytes to cache */ + int maxkeypage; /* maximum keys per page */ + int minkeypage; /* minimum keys per page */ + uint psize; /* page size */ + int(*compare) /* comparison function */ + (const DBT *, const DBT *); + size_t(*prefix) /* prefix function */ + (const DBT *, const DBT *); + int lorder; /* byte order */ +} BTREEINFO; + +#define HASHMAGIC 0x061561 +#define HASHVERSION 2 + +/* Structure used to pass parameters to the hashing routines. */ +typedef struct { + uint bsize; /* bucket size */ + uint ffactor; /* fill factor */ + uint nelem; /* number of elements */ + uint cachesize; /* bytes to cache */ + uint32 /* hash function */ + (*hash)(const void *, size_t); + int lorder; /* byte order */ +} HASHINFO; + +/* Structure used to pass parameters to the record routines. */ +typedef struct { +#define R_FIXEDLEN 0x01 /* fixed-length records */ +#define R_NOKEY 0x02 /* key not required */ +#define R_SNAPSHOT 0x04 /* snapshot the input */ + uint32 flags; + uint cachesize; /* bytes to cache */ + uint psize; /* page size */ + int lorder; /* byte order */ + size_t reclen; /* record length (fixed-length records) */ + uint8 bval; /* delimiting byte (variable-length records */ + char *bfname; /* btree file name */ +} RECNOINFO; + +#ifdef __DBINTERFACE_PRIVATE +/* + * Little endian <==> big endian 32-bit swap macros. + * M_32_SWAP swap a memory location + * P_32_SWAP swap a referenced memory location + * P_32_COPY swap from one location to another + */ +#define M_32_SWAP(a) \ + { \ + uint32 _tmp = a; \ + ((char *)&a)[0] = ((char *)&_tmp)[3]; \ + ((char *)&a)[1] = ((char *)&_tmp)[2]; \ + ((char *)&a)[2] = ((char *)&_tmp)[1]; \ + ((char *)&a)[3] = ((char *)&_tmp)[0]; \ + } +#define P_32_SWAP(a) \ + { \ + uint32 _tmp = *(uint32 *)a; \ + ((char *)a)[0] = ((char *)&_tmp)[3]; \ + ((char *)a)[1] = ((char *)&_tmp)[2]; \ + ((char *)a)[2] = ((char *)&_tmp)[1]; \ + ((char *)a)[3] = ((char *)&_tmp)[0]; \ + } +#define P_32_COPY(a, b) \ + { \ + ((char *)&(b))[0] = ((char *)&(a))[3]; \ + ((char *)&(b))[1] = ((char *)&(a))[2]; \ + ((char *)&(b))[2] = ((char *)&(a))[1]; \ + ((char *)&(b))[3] = ((char *)&(a))[0]; \ + } + +/* + * Little endian <==> big endian 16-bit swap macros. + * M_16_SWAP swap a memory location + * P_16_SWAP swap a referenced memory location + * P_16_COPY swap from one location to another + */ +#define M_16_SWAP(a) \ + { \ + uint16 _tmp = a; \ + ((char *)&a)[0] = ((char *)&_tmp)[1]; \ + ((char *)&a)[1] = ((char *)&_tmp)[0]; \ + } +#define P_16_SWAP(a) \ + { \ + uint16 _tmp = *(uint16 *)a; \ + ((char *)a)[0] = ((char *)&_tmp)[1]; \ + ((char *)a)[1] = ((char *)&_tmp)[0]; \ + } +#define P_16_COPY(a, b) \ + { \ + ((char *)&(b))[0] = ((char *)&(a))[1]; \ + ((char *)&(b))[1] = ((char *)&(a))[0]; \ + } +#endif + +PR_BEGIN_EXTERN_C + +extern DB * +dbopen(const char *, int, int, DBTYPE, const void *); + +/* set or unset a global lock flag to disable the + * opening of any DBM file + */ +void dbSetOrClearDBLock(DBLockFlagEnum type); + +#ifdef __DBINTERFACE_PRIVATE +DB *__bt_open(const char *, int, int, const BTREEINFO *, int); +DB *__hash_open(const char *, int, int, const HASHINFO *, int); +DB *__rec_open(const char *, int, int, const RECNOINFO *, int); +void __dbpanic(DB *dbp); +#endif + +PR_END_EXTERN_C + +#endif /* !_DB_H_ */ diff --git a/security/nss/lib/dbm/include/ncompat.h b/security/nss/lib/dbm/include/ncompat.h new file mode 100644 index 000000000..9fd434799 --- /dev/null +++ b/security/nss/lib/dbm/include/ncompat.h @@ -0,0 +1,224 @@ +/*- + * 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. + * + * @(#)compat.h 8.13 (Berkeley) 2/21/94 + */ + +#ifndef _COMPAT_H_ +#define _COMPAT_H_ + +#include <sys/types.h> + +/* + * If your system doesn't typedef u_long, u_short, or u_char, change + * the 0 to a 1. + */ +#if 0 +typedef unsigned char u_char; /* 4.[34]BSD names. */ +typedef unsigned int u_int; +typedef unsigned long u_long; +typedef unsigned short u_short; +#endif + +/* If your system doesn't typedef size_t, change the 0 to a 1. */ +#if 0 +typedef unsigned int size_t; /* POSIX, 4.[34]BSD names. */ +#endif + +/* If your system doesn't typedef ssize_t, change the 0 to a 1. */ +#if 0 +typedef int ssize_t; /* POSIX names. */ +#endif + +/* + * If your system doesn't have the POSIX type for a signal mask, + * change the 0 to a 1. + */ +#if 0 /* POSIX 1003.1 signal mask type. */ +typedef unsigned int sigset_t; +#endif + +/* + * If your system's vsprintf returns a char *, not an int, + * change the 0 to a 1. + */ +#if defined(__sun) && !defined(__SVR4) /* SUNOS */ +#define VSPRINTF_CHARSTAR +#endif +/* + * If you don't have POSIX 1003.1 signals, the signal code surrounding the + * temporary file creation is intended to block all of the possible signals + * long enough to create the file and unlink it. All of this stuff is + * intended to use old-style BSD calls to fake POSIX 1003.1 calls. + */ +#ifdef NO_POSIX_SIGNALS +#define sigemptyset(set) (*(set) = 0) +#define sigfillset(set) (*(set) = ~(sigset_t)0, 0) +#define sigaddset(set, signo) (*(set) |= sigmask(signo), 0) +#define sigdelset(set, signo) (*(set) &= ~sigmask(signo), 0) +#define sigismember(set, signo) ((*(set)&sigmask(signo)) != 0) + +#define SIG_BLOCK 1 +#define SIG_UNBLOCK 2 +#define SIG_SETMASK 3 + +static int __sigtemp; /* For the use of sigprocmask */ + +/* Repeated test of oset != NULL is to avoid "*0". */ +#define sigprocmask(how, set, oset) \ + ((__sigtemp = \ + (((how) == SIG_BLOCK) ? sigblock(0) | *(set) : (((how) == SIG_UNBLOCK) ? sigblock(0) & ~(*(set)) : ((how) == SIG_SETMASK ? *(set) : sigblock(0))))), \ + ((oset) ? (*(oset ? oset : set) = sigsetmask(__sigtemp)) : sigsetmask(__sigtemp)), 0) +#endif + +/* + * If your system doesn't have an include file with the appropriate + * byte order set, make sure you specify the correct one. + */ +#ifndef BYTE_ORDER +#define LITTLE_ENDIAN 1234 /* LSB first: i386, vax */ +#define BIG_ENDIAN 4321 /* MSB first: 68000, ibm, net */ +#define BYTE_ORDER BIG_ENDIAN /* Set for your system. */ +#endif + +#if defined(SYSV) || defined(SYSTEM5) || defined(__sun) +#define index(a, b) strchr(a, b) +#define rindex(a, b) strrchr(a, b) +#define bzero(a, b) memset(a, 0, b) +#define bcmp(a, b, n) memcmp(a, b, n) +#define bcopy(a, b, n) memmove(b, a, n) +#endif + +#if defined(BSD) || defined(BSD4_3) +#define strchr(a, b) index(a, b) +#define strrchr(a, b) rindex(a, b) +#define memcmp(a, b, n) bcmp(a, b, n) +#define memmove(a, b, n) bcopy(b, a, n) +#endif + +/* + * 32-bit machine. The db routines are theoretically independent of + * the size of u_shorts and u_longs, but I don't know that anyone has + * ever actually tried it. At a minimum, change the following #define's + * if you are trying to compile on a different type of system. + */ +#ifndef USHRT_MAX +#define USHRT_MAX 0xFFFF +#define ULONG_MAX 0xFFFFFFFF +#endif + +#ifndef O_ACCMODE /* POSIX 1003.1 access mode mask. */ +#define O_ACCMODE (O_RDONLY | O_WRONLY | O_RDWR) +#endif + +#ifndef _POSIX2_RE_DUP_MAX /* POSIX 1003.2 RE limit. */ +#define _POSIX2_RE_DUP_MAX 255 +#endif + +/* + * If you can't provide lock values in the open(2) call. Note, this + * allows races to happen. + */ +#ifndef O_EXLOCK /* 4.4BSD extension. */ +#define O_EXLOCK 0 +#endif + +#ifndef O_SHLOCK /* 4.4BSD extension. */ +#define O_SHLOCK 0 +#endif + +#ifndef EFTYPE +#define EFTYPE EINVAL /* POSIX 1003.1 format errno. */ +#endif + +#ifndef WCOREDUMP /* 4.4BSD extension */ +#define WCOREDUMP(a) 0 +#endif + +#ifndef STDERR_FILENO +#define STDIN_FILENO 0 /* ANSI C #defines */ +#define STDOUT_FILENO 1 +#define STDERR_FILENO 2 +#endif + +#ifndef SEEK_END +#define SEEK_SET 0 /* POSIX 1003.1 seek values */ +#define SEEK_CUR 1 +#define SEEK_END 2 +#endif + +#ifndef _POSIX_VDISABLE /* POSIX 1003.1 disabling char. */ +#define _POSIX_VDISABLE 0 /* Some systems used 0. */ +#endif + +#ifndef TCSASOFT /* 4.4BSD extension. */ +#define TCSASOFT 0 +#endif + +#ifndef _POSIX2_RE_DUP_MAX /* POSIX 1003.2 values. */ +#define _POSIX2_RE_DUP_MAX 255 +#endif + +#ifndef NULL /* ANSI C #defines NULL everywhere. */ +#define NULL 0 +#endif + +#ifndef MAX /* Usually found in <sys/param.h>. */ +#define MAX(_a, _b) ((_a) < (_b) ? (_b) : (_a)) +#endif +#ifndef MIN /* Usually found in <sys/param.h>. */ +#define MIN(_a, _b) ((_a) < (_b) ? (_a) : (_b)) +#endif + +/* Default file permissions. */ +#ifndef DEFFILEMODE /* 4.4BSD extension. */ +#define DEFFILEMODE (S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH | S_IWOTH) +#endif + +#ifndef __sun +#ifndef S_ISDIR /* POSIX 1003.1 file type tests. */ +#define S_ISDIR(m) ((m & 0170000) == 0040000) /* directory */ +#define S_ISCHR(m) ((m & 0170000) == 0020000) /* char special */ +#define S_ISBLK(m) ((m & 0170000) == 0060000) /* block special */ +#define S_ISREG(m) ((m & 0170000) == 0100000) /* regular file */ +#define S_ISFIFO(m) ((m & 0170000) == 0010000) /* fifo */ +#endif +#ifndef S_ISLNK /* BSD POSIX 1003.1 extensions */ +#define S_ISLNK(m) ((m & 0170000) == 0120000) /* symbolic link */ +#define S_ISSOCK(m) ((m & 0170000) == 0140000) /* socket */ +#endif +#endif /* __sun */ + +/* The type of a va_list. */ +#ifndef _BSD_VA_LIST_ /* 4.4BSD #define. */ +#define _BSD_VA_LIST_ char* +#endif + +#endif /* !_COMPAT_H_ */ diff --git a/security/nss/lib/dbm/include/page.h b/security/nss/lib/dbm/include/page.h new file mode 100644 index 000000000..1ece42bed --- /dev/null +++ b/security/nss/lib/dbm/include/page.h @@ -0,0 +1,93 @@ +/*- + * 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. + * + * @(#)page.h 8.2 (Berkeley) 5/31/94 + */ + +/* + * Definitions for hashing page file format. + */ + +/* + * routines dealing with a data page + * + * page format: + * +------------------------------+ + * p | n | keyoff | datoff | keyoff | + * +------------+--------+--------+ + * | datoff | free | ptr | --> | + * +--------+---------------------+ + * | F R E E A R E A | + * +--------------+---------------+ + * | <---- - - - | data | + * +--------+-----+----+----------+ + * | key | data | key | + * +--------+----------+----------+ + * + * Pointer to the free space is always: p[p[0] + 2] + * Amount of free space on the page is: p[p[0] + 1] + */ + +/* + * How many bytes required for this pair? + * 2 shorts in the table at the top of the page + room for the + * key and room for the data + * + * We prohibit entering a pair on a page unless there is also room to append + * an overflow page. The reason for this it that you can get in a situation + * where a single key/data pair fits on a page, but you can't append an + * overflow page and later you'd have to split the key/data and handle like + * a big pair. + * You might as well do this up front. + */ +#ifndef PAGE_H +#define PAGE_H + +#define PAIRSIZE(K, D) (2 * sizeof(uint16) + (K)->size + (D)->size) +#define BIGOVERHEAD (4 * sizeof(uint16)) +#define KEYSIZE(K) (4 * sizeof(uint16) + (K)->size); +#define OVFLSIZE (2 * sizeof(uint16)) +#define FREESPACE(P) ((P)[(P)[0] + 1]) +#define OFFSET(P) ((P)[(P)[0] + 2]) +#define PAIRFITS(P, K, D) \ + (((P)[2] >= REAL_KEY) && \ + (PAIRSIZE((K), (D)) + OVFLSIZE) <= FREESPACE((P))) +#define PAGE_META(N) (((N) + 3) * sizeof(uint16)) + +typedef struct { + BUFHEAD *newp; + BUFHEAD *oldp; + BUFHEAD *nextp; + uint16 next_addr; +} SPLIT_RETURN; +#endif diff --git a/security/nss/lib/dbm/include/queue.h b/security/nss/lib/dbm/include/queue.h new file mode 100644 index 000000000..adc2c524d --- /dev/null +++ b/security/nss/lib/dbm/include/queue.h @@ -0,0 +1,258 @@ +/* + * 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. + * + * @(#)queue.h 8.3 (Berkeley) 12/13/93 + */ + +#ifndef _QUEUE_H_ +#define _QUEUE_H_ + +/* + * This file defines three types of data structures: lists, tail queues, + * and circular queues. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list after + * an existing element or at the head of the list. A list may only be + * traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list after + * an existing element, at the head of the list, or at the end of the + * list. A tail queue may only be traversed in the forward direction. + * + * A circle queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the list. + * A circle queue may be traversed in either direction, but has a more + * complex end of list detection. + * + * For details on the use of these macros, see the queue(3) manual page. + */ + +/* + * List definitions. + */ +#define LIST_HEAD(name, type) \ + struct name { \ + struct type *lh_first; /* first element */ \ + } + +#define LIST_ENTRY(type) \ + struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ + } + +/* + * List functions. + */ +#define LIST_INIT(head) \ + { \ + (head)->lh_first = NULL; \ + } + +#define LIST_INSERT_AFTER(listelm, elm, field) \ + { \ + if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ + (listelm)->field.le_next->field.le_prev = \ + &(elm)->field.le_next; \ + (listelm)->field.le_next = (elm); \ + (elm)->field.le_prev = &(listelm)->field.le_next; \ + } + +#define LIST_INSERT_HEAD(head, elm, field) \ + { \ + if (((elm)->field.le_next = (head)->lh_first) != NULL) \ + (head)->lh_first->field.le_prev = &(elm)->field.le_next; \ + (head)->lh_first = (elm); \ + (elm)->field.le_prev = &(head)->lh_first; \ + } + +#define LIST_REMOVE(elm, field) \ + { \ + if ((elm)->field.le_next != NULL) \ + (elm)->field.le_next->field.le_prev = \ + (elm)->field.le_prev; \ + *(elm)->field.le_prev = (elm)->field.le_next; \ + } + +/* + * Tail queue definitions. + */ +#define TAILQ_HEAD(name, type) \ + struct name { \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ + } + +#define TAILQ_ENTRY(type) \ + struct { \ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ + } + +/* + * Tail queue functions. + */ +#define TAILQ_INIT(head) \ + { \ + (head)->tqh_first = NULL; \ + (head)->tqh_last = &(head)->tqh_first; \ + } + +#define TAILQ_INSERT_HEAD(head, elm, field) \ + { \ + if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ + (elm)->field.tqe_next->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (head)->tqh_first = (elm); \ + (elm)->field.tqe_prev = &(head)->tqh_first; \ + } + +#define TAILQ_INSERT_TAIL(head, elm, field) \ + { \ + (elm)->field.tqe_next = NULL; \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + } + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) \ + { \ + if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL) \ + (elm)->field.tqe_next->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (listelm)->field.tqe_next = (elm); \ + (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ + } + +#define TAILQ_REMOVE(head, elm, field) \ + { \ + if (((elm)->field.tqe_next) != NULL) \ + (elm)->field.tqe_next->field.tqe_prev = \ + (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ + } + +/* + * Circular queue definitions. + */ +#define CIRCLEQ_HEAD(name, type) \ + struct name { \ + struct type *cqh_first; /* first element */ \ + struct type *cqh_last; /* last element */ \ + } + +#define CIRCLEQ_ENTRY(type) \ + struct { \ + struct type *cqe_next; /* next element */ \ + struct type *cqe_prev; /* previous element */ \ + } + +/* + * Circular queue functions. + */ +#define CIRCLEQ_INIT(head) \ + { \ + (head)->cqh_first = (void *)(head); \ + (head)->cqh_last = (void *)(head); \ + } + +#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) \ + { \ + (elm)->field.cqe_next = (listelm)->field.cqe_next; \ + (elm)->field.cqe_prev = (listelm); \ + if ((listelm)->field.cqe_next == (void *)(head)) \ + (head)->cqh_last = (elm); \ + else \ + (listelm)->field.cqe_next->field.cqe_prev = (elm); \ + (listelm)->field.cqe_next = (elm); \ + } + +#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) \ + { \ + (elm)->field.cqe_next = (listelm); \ + (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ + if ((listelm)->field.cqe_prev == (void *)(head)) \ + (head)->cqh_first = (elm); \ + else \ + (listelm)->field.cqe_prev->field.cqe_next = (elm); \ + (listelm)->field.cqe_prev = (elm); \ + } + +#define CIRCLEQ_INSERT_HEAD(head, elm, field) \ + { \ + (elm)->field.cqe_next = (head)->cqh_first; \ + (elm)->field.cqe_prev = (void *)(head); \ + if ((head)->cqh_last == (void *)(head)) \ + (head)->cqh_last = (elm); \ + else \ + (head)->cqh_first->field.cqe_prev = (elm); \ + (head)->cqh_first = (elm); \ + } + +#define CIRCLEQ_INSERT_TAIL(head, elm, field) \ + { \ + (elm)->field.cqe_next = (void *)(head); \ + (elm)->field.cqe_prev = (head)->cqh_last; \ + if ((head)->cqh_first == (void *)(head)) \ + (head)->cqh_first = (elm); \ + else \ + (head)->cqh_last->field.cqe_next = (elm); \ + (head)->cqh_last = (elm); \ + } + +#define CIRCLEQ_REMOVE(head, elm, field) \ + { \ + if ((elm)->field.cqe_next == (void *)(head)) \ + (head)->cqh_last = (elm)->field.cqe_prev; \ + else \ + (elm)->field.cqe_next->field.cqe_prev = \ + (elm)->field.cqe_prev; \ + if ((elm)->field.cqe_prev == (void *)(head)) \ + (head)->cqh_first = (elm)->field.cqe_next; \ + else \ + (elm)->field.cqe_prev->field.cqe_next = \ + (elm)->field.cqe_next; \ + } +#endif /* !_QUEUE_H_ */ diff --git a/security/nss/lib/dbm/include/search.h b/security/nss/lib/dbm/include/search.h new file mode 100644 index 000000000..d6fe0d93d --- /dev/null +++ b/security/nss/lib/dbm/include/search.h @@ -0,0 +1,50 @@ +/*- + * 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. + * + * @(#)search.h 8.1 (Berkeley) 6/4/93 + */ + +/* Backward compatibility to hsearch interface. */ +typedef struct entry { + char *key; + char *data; +} ENTRY; + +typedef enum { + FIND, + ENTER +} ACTION; + +int hcreate(unsigned int); +void hdestroy(void); +ENTRY *hsearch(ENTRY, ACTION); diff --git a/security/nss/lib/dbm/include/winfile.h b/security/nss/lib/dbm/include/winfile.h new file mode 100644 index 000000000..da93ec746 --- /dev/null +++ b/security/nss/lib/dbm/include/winfile.h @@ -0,0 +1,103 @@ + +/* --------------------------------------------------------------------------- + Stuff to fake unix file I/O on windows boxes + ------------------------------------------------------------------------*/ + +#ifndef WINFILE_H +#define WINFILE_H + +#ifdef _WINDOWS +/* hacked out of <dirent.h> on an SGI */ +#if defined(XP_WIN32) || defined(_WIN32) +/* 32-bit stuff here */ +#include <windows.h> +#include <stdlib.h> +#ifdef __MINGW32__ +#include <sys/types.h> +#include <sys/stat.h> +#else +#include <sys\types.h> +#include <sys\stat.h> +#endif + +typedef struct DIR_Struct { + void* directoryPtr; + WIN32_FIND_DATA data; +} DIR; + +#define _ST_FSTYPSZ 16 + +#if !defined(__BORLANDC__) && !defined(__GNUC__) +typedef unsigned long mode_t; +typedef long uid_t; +typedef long gid_t; +typedef long off_t; +typedef unsigned long nlink_t; +#endif + +typedef struct timestruc { + time_t tv_sec; /* seconds */ + long tv_nsec; /* and nanoseconds */ +} timestruc_t; + +struct dirent { /* data from readdir() */ + ino_t d_ino; /* inode number of entry */ + off_t d_off; /* offset of disk direntory entry */ + unsigned short d_reclen; /* length of this record */ + char d_name[_MAX_FNAME]; /* name of file */ +}; + +#if !defined(__BORLANDC__) && !defined(__GNUC__) +#define S_ISDIR(s) ((s)&_S_IFDIR) +#endif + +#else /* _WIN32 */ +/* 16-bit windows stuff */ + +#include <sys\types.h> +#include <sys\stat.h> +#include <dos.h> + +/* Getting cocky to support multiple file systems */ +typedef struct dirStruct_tag { + struct _find_t file_data; + char c_checkdrive; +} dirStruct; + +typedef struct DIR_Struct { + void* directoryPtr; + dirStruct data; +} DIR; + +#define _ST_FSTYPSZ 16 +typedef unsigned long mode_t; +typedef long uid_t; +typedef long gid_t; +typedef long off_t; +typedef unsigned long nlink_t; + +typedef struct timestruc { + time_t tv_sec; /* seconds */ + long tv_nsec; /* and nanoseconds */ +} timestruc_t; + +struct dirent { /* data from readdir() */ + ino_t d_ino; /* inode number of entry */ + off_t d_off; /* offset of disk direntory entry */ + unsigned short d_reclen; /* length of this record */ +#ifdef XP_WIN32 + char d_name[_MAX_FNAME]; /* name of file */ +#else + char d_name[20]; /* name of file */ +#endif +}; + +#define S_ISDIR(s) ((s)&_S_IFDIR) + +#endif /* 16-bit windows */ + +#define CONST const + +#endif /* _WINDOWS */ + +#endif /* WINFILE_H */ diff --git a/security/nss/lib/dbm/manifest.mn b/security/nss/lib/dbm/manifest.mn new file mode 100644 index 000000000..7a3bcf4c1 --- /dev/null +++ b/security/nss/lib/dbm/manifest.mn @@ -0,0 +1,17 @@ +#! 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 + +IMPORTS = nspr20/v4.4.1 + +RELEASE = dbm + +DIRS = include \ + src \ + $(NULL) 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 */ diff --git a/security/nss/lib/dbm/tests/Makefile b/security/nss/lib/dbm/tests/Makefile new file mode 100644 index 000000000..3ecabe27c --- /dev/null +++ b/security/nss/lib/dbm/tests/Makefile @@ -0,0 +1,41 @@ +#! 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/. +DEPTH = ../../.. +CORE_DEPTH = ../../.. + +VPATH = $(CORE_DEPTH)/../dbm/tests + +MODULE = dbm + +CSRCS = lots.c + +PROGRAM = lots + +include $(DEPTH)/coreconf/config.mk + +include $(DEPTH)/dbm/config/config.mk + +ifeq (,$(filter-out WIN%,$(OS_TARGET))) +LIBDBM = ../src/$(PLATFORM)/dbm$(STATIC_LIB_SUFFIX) +else +LIBDBM = ../src/$(PLATFORM)/libdbm$(STATIC_LIB_SUFFIX) +endif + +INCLUDES += -I$(CORE_DEPTH)/../dbm/include + +LDFLAGS = $(LDOPTS) $(LIBDBM) + +include $(DEPTH)/coreconf/rules.mk + +lots.pure: lots + purify $(CC) -o lots.pure $(CFLAGS) $(OBJS) $(MYLIBS) + +crash: crash.o $(MYLIBS) + $(CC) -o crash $(CFLAGS) $^ + +crash.pure: crash.o $(MYLIBS) + purify $(CC) -o crash.pure $(CFLAGS) $^ + diff --git a/security/nss/lib/dbm/tests/dbmtest.pkg b/security/nss/lib/dbm/tests/dbmtest.pkg new file mode 100644 index 000000000..abd564bed --- /dev/null +++ b/security/nss/lib/dbm/tests/dbmtest.pkg @@ -0,0 +1,2 @@ +[gecko-tests] +dist/bin/lots@BINS@ diff --git a/security/nss/lib/dbm/tests/lots.c b/security/nss/lib/dbm/tests/lots.c new file mode 100644 index 000000000..91bba4965 --- /dev/null +++ b/security/nss/lib/dbm/tests/lots.c @@ -0,0 +1,553 @@ +/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* 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/. */ + +/* use sequental numbers printed to strings + * to store lots and lots of entries in the + * database. + * + * Start with 100 entries, put them and then + * read them out. Then delete the first + * half and verify that all of the first half + * is gone and then verify that the second + * half is still there. + * Then add the first half back and verify + * again. Then delete the middle third + * and verify again. + * Then increase the size by 1000 and do + * the whole add delete thing again. + * + * The data for each object is the number string translated + * to hex and replicated a random number of times. The + * number of times that the data is replicated is the first + * int32 in the data. + */ + +#include <stdio.h> + +#include <stdlib.h> +#ifdef STDC_HEADERS +#include <stdarg.h> +#else +#include <varargs.h> +#endif + +#ifdef HAVE_MEMORY_H +#include <memory.h> +#endif +#include <string.h> +#include <assert.h> +#include "mcom_db.h" + +DB *database = 0; +int MsgPriority = 5; + +#if defined(_WINDOWS) && !defined(WIN32) +#define int32 long +#define uint32 unsigned long +#else +#define int32 int +#define uint32 unsigned int +#endif + +typedef enum { + USE_LARGE_KEY, + USE_SMALL_KEY +} key_type_enum; + +#define TraceMe(priority, msg) \ + do { \ + if (priority <= MsgPriority) { \ + ReportStatus msg; \ + } \ + } while (0) + +int +ReportStatus(char *string, ...) +{ + va_list args; + +#ifdef STDC_HEADERS + va_start(args, string); +#else + va_start(args); +#endif + vfprintf(stderr, string, args); + va_end(args); + + fprintf(stderr, "\n"); + + return (0); +} + +int +ReportError(char *string, ...) +{ + va_list args; + +#ifdef STDC_HEADERS + va_start(args, string); +#else + va_start(args); +#endif + fprintf(stderr, "\n "); + vfprintf(stderr, string, args); + fprintf(stderr, "\n"); + va_end(args); + + return (0); +} + +DBT * +MakeLargeKey(int32 num) +{ + int32 low_bits; + static DBT rv; + static char *string_rv = 0; + int rep_char; + size_t size; + + if (string_rv) + free(string_rv); + + /* generate a really large text key derived from + * an int32 + */ + low_bits = (num % 10000) + 1; + + /* get the repeat char from the low 26 */ + rep_char = (char)((low_bits % 26) + 'a'); + + /* malloc a string low_bits wide */ + size = low_bits * sizeof(char); + string_rv = (char *)malloc(size); + + memset(string_rv, rep_char, size); + + rv.data = string_rv; + rv.size = size; + + return (&rv); +} + +DBT * +MakeSmallKey(int32 num) +{ + static DBT rv; + static char data_string[64]; + + rv.data = data_string; + + sprintf(data_string, "%ld", (long)num); + rv.size = strlen(data_string); + + return (&rv); +} + +DBT * +GenKey(int32 num, key_type_enum key_type) +{ + DBT *key; + + switch (key_type) { + case USE_LARGE_KEY: + key = MakeLargeKey(num); + break; + case USE_SMALL_KEY: + key = MakeSmallKey(num); + break; + default: + abort(); + break; + } + + return (key); +} + +int +SeqDatabase() +{ + int status; + DBT key, data; + + ReportStatus("SEQuencing through database..."); + + /* seq through the whole database */ + if (!(status = (*database->seq)(database, &key, &data, R_FIRST))) { + while (!(status = (database->seq)(database, &key, &data, R_NEXT))) + ; /* null body */ + } + + if (status < 0) + ReportError("Error seq'ing database"); + + return (status); +} + +int +VerifyData(DBT *data, int32 num, key_type_enum key_type) +{ + int32 count, compare_num; + size_t size; + int32 *int32_array; + + /* The first int32 is count + * The other n entries should + * all equal num + */ + if (data->size < sizeof(int32)) { + ReportError("Data size corrupted"); + return -1; + } + + memcpy(&count, data->data, sizeof(int32)); + + size = sizeof(int32) * (count + 1); + + if (size != data->size) { + ReportError("Data size corrupted"); + return -1; + } + + int32_array = (int32 *)data->data; + + for (; count > 0; count--) { + memcpy(&compare_num, &int32_array[count], sizeof(int32)); + + if (compare_num != num) { + ReportError("Data corrupted"); + return -1; + } + } + + return (0); +} + +/* verify that a range of number strings exist + * or don't exist. And that the data is valid + */ +#define SHOULD_EXIST 1 +#define SHOULD_NOT_EXIST 0 +int +VerifyRange(int32 low, int32 high, int32 should_exist, key_type_enum key_type) +{ + DBT *key, data; + int32 num; + int status; + + TraceMe(1, ("Verifying: %ld to %ld, using %s keys", + low, high, key_type == USE_SMALL_KEY ? "SMALL" : "LARGE")); + + for (num = low; num <= high; num++) { + + key = GenKey(num, key_type); + + status = (*database->get)(database, key, &data, 0); + + if (status == 0) { + /* got the item */ + if (!should_exist) { + ReportError("Item exists but shouldn't: %ld", num); + } else { + /* else verify the data */ + VerifyData(&data, num, key_type); + } + } else if (status > 0) { + /* item not found */ + if (should_exist) { + ReportError("Item not found but should be: %ld", num); + } + } else { + /* database error */ + ReportError("Database error"); + return (-1); + } + } + + TraceMe(1, ("Correctly verified: %ld to %ld", low, high)); + + return (0); +} + +DBT * +GenData(int32 num) +{ + int32 n; + static DBT *data = 0; + int32 *int32_array; + size_t size; + + if (!data) { + data = (DBT *)malloc(sizeof(DBT)); + data->size = 0; + data->data = 0; + } else if (data->data) { + free(data->data); + } + + n = rand(); + + n = n % 512; /* bound to a 2K size */ + + size = sizeof(int32) * (n + 1); + int32_array = (int32 *)malloc(size); + + memcpy(&int32_array[0], &n, sizeof(int32)); + + for (; n > 0; n--) { + memcpy(&int32_array[n], &num, sizeof(int32)); + } + + data->data = (void *)int32_array; + data->size = size; + + return (data); +} + +#define ADD_RANGE 1 +#define DELETE_RANGE 2 + +int +AddOrDelRange(int32 low, int32 high, int action, key_type_enum key_type) +{ + DBT *key, *data; +#if 0 /* only do this if your really analy checking the puts */ + DBT tmp_data; +#endif + int32 num; + int status; + + if (action != ADD_RANGE && action != DELETE_RANGE) + assert(0); + + if (action == ADD_RANGE) { + TraceMe(1, ("Adding: %ld to %ld: %s keys", low, high, + key_type == USE_SMALL_KEY ? "SMALL" : "LARGE")); + } else { + TraceMe(1, ("Deleting: %ld to %ld: %s keys", low, high, + key_type == USE_SMALL_KEY ? "SMALL" : "LARGE")); + } + + for (num = low; num <= high; num++) { + + key = GenKey(num, key_type); + + if (action == ADD_RANGE) { + data = GenData(num); + status = (*database->put)(database, key, data, 0); + } else { + status = (*database->del)(database, key, 0); + } + + if (status < 0) { + ReportError("Database error %s item: %ld", + action == ADD_RANGE ? "ADDING" : "DELETING", + num); + } else if (status > 0) { + ReportError("Could not %s item: %ld", + action == ADD_RANGE ? "ADD" : "DELETE", + num); + } else if (action == ADD_RANGE) { +#define SYNC_EVERY_TIME +#ifdef SYNC_EVERY_TIME + status = (*database->sync)(database, 0); + if (status != 0) + ReportError("Database error syncing after add"); +#endif + +#if 0 /* only do this if your really analy checking the puts */ + + /* make sure we can still get it + */ + status = (*database->get)(database, key, &tmp_data, 0); + + if(status != 0) + { + ReportError("Database error checking item just added: %d", + num); + } + else + { + /* now verify that none of the ones we already + * put in have disappeared + */ + VerifyRange(low, num, SHOULD_EXIST, key_type); + } +#endif + } + } + + if (action == ADD_RANGE) { + TraceMe(1, ("Successfully added: %ld to %ld", low, high)); + } else { + TraceMe(1, ("Successfully deleted: %ld to %ld", low, high)); + } + + return (0); +} + +int +TestRange(int32 low, int32 range, key_type_enum key_type) +{ + int status; + int32 low_of_range1, high_of_range1; + int32 low_of_range2, high_of_range2; + int32 low_of_range3, high_of_range3; + + status = AddOrDelRange(low, low + range, ADD_RANGE, key_type); + status = VerifyRange(low, low + range, SHOULD_EXIST, key_type); + + TraceMe(1, ("Finished with sub test 1")); + + SeqDatabase(); + + low_of_range1 = low; + high_of_range1 = low + (range / 2); + low_of_range2 = high_of_range1 + 1; + high_of_range2 = low + range; + status = AddOrDelRange(low_of_range1, high_of_range1, DELETE_RANGE, key_type); + status = VerifyRange(low_of_range1, high_of_range1, SHOULD_NOT_EXIST, key_type); + status = VerifyRange(low_of_range2, low_of_range2, SHOULD_EXIST, key_type); + + TraceMe(1, ("Finished with sub test 2")); + + SeqDatabase(); + + status = AddOrDelRange(low_of_range1, high_of_range1, ADD_RANGE, key_type); + /* the whole thing should exist now */ + status = VerifyRange(low, low + range, SHOULD_EXIST, key_type); + + TraceMe(1, ("Finished with sub test 3")); + + SeqDatabase(); + + status = AddOrDelRange(low_of_range2, high_of_range2, DELETE_RANGE, key_type); + status = VerifyRange(low_of_range1, high_of_range1, SHOULD_EXIST, key_type); + status = VerifyRange(low_of_range2, high_of_range2, SHOULD_NOT_EXIST, key_type); + + TraceMe(1, ("Finished with sub test 4")); + + SeqDatabase(); + + status = AddOrDelRange(low_of_range2, high_of_range2, ADD_RANGE, key_type); + /* the whole thing should exist now */ + status = VerifyRange(low, low + range, SHOULD_EXIST, key_type); + + TraceMe(1, ("Finished with sub test 5")); + + SeqDatabase(); + + low_of_range1 = low; + high_of_range1 = low + (range / 3); + low_of_range2 = high_of_range1 + 1; + high_of_range2 = high_of_range1 + (range / 3); + low_of_range3 = high_of_range2 + 1; + high_of_range3 = low + range; + /* delete range 2 */ + status = AddOrDelRange(low_of_range2, high_of_range2, DELETE_RANGE, key_type); + status = VerifyRange(low_of_range1, high_of_range1, SHOULD_EXIST, key_type); + status = VerifyRange(low_of_range2, low_of_range2, SHOULD_NOT_EXIST, key_type); + status = VerifyRange(low_of_range3, low_of_range2, SHOULD_EXIST, key_type); + + TraceMe(1, ("Finished with sub test 6")); + + SeqDatabase(); + + status = AddOrDelRange(low_of_range2, high_of_range2, ADD_RANGE, key_type); + /* the whole thing should exist now */ + status = VerifyRange(low, low + range, SHOULD_EXIST, key_type); + + TraceMe(1, ("Finished with sub test 7")); + + return (0); +} + +#define START_RANGE 109876 +int +main(int argc, char **argv) +{ + int32 i, j = 0; + int quick_exit = 0; + int large_keys = 0; + HASHINFO hash_info = { + 16 * 1024, + 0, + 0, + 0, + 0, + 0 + }; + + if (argc > 1) { + while (argc > 1) { + if (!strcmp(argv[argc - 1], "-quick")) + quick_exit = 1; + else if (!strcmp(argv[argc - 1], "-large")) { + large_keys = 1; + } + argc--; + } + } + + database = dbopen("test.db", O_RDWR | O_CREAT, 0644, DB_HASH, &hash_info); + + if (!database) { + ReportError("Could not open database"); +#ifdef unix + perror(""); +#endif + exit(1); + } + + if (quick_exit) { + if (large_keys) + TestRange(START_RANGE, 200, USE_LARGE_KEY); + else + TestRange(START_RANGE, 200, USE_SMALL_KEY); + + (*database->sync)(database, 0); + (*database->close)(database); + exit(0); + } + + for (i = 100; i < 10000000; i += 200) { + if (1 || j) { + TestRange(START_RANGE, i, USE_LARGE_KEY); + j = 0; + } else { + TestRange(START_RANGE, i, USE_SMALL_KEY); + j = 1; + } + + if (1 == rand() % 3) { + (*database->sync)(database, 0); + } + + if (1 == rand() % 3) { + /* close and reopen */ + (*database->close)(database); + database = dbopen("test.db", O_RDWR | O_CREAT, 0644, DB_HASH, 0); + if (!database) { + ReportError("Could not reopen database"); +#ifdef unix + perror(""); +#endif + exit(1); + } + } else { + /* reopen database without closeing the other */ + database = dbopen("test.db", O_RDWR | O_CREAT, 0644, DB_HASH, 0); + if (!database) { + ReportError("Could not reopen database " + "after not closing the other"); +#ifdef unix + perror(""); +#endif + exit(1); + } + } + } + + return (0); +} |