1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22/*
23 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 * Copyright (c) 2016 by Delphix. All rights reserved.
26 */
27
28/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
29/*	  All Rights Reserved  	*/
30
31/*
32 * University Copyright- Copyright (c) 1982, 1986, 1988
33 * The Regents of the University of California
34 * All Rights Reserved
35 *
36 * University Acknowledgment- Portions of this document are derived from
37 * software developed by the University of California, Berkeley, and its
38 * contributors.
39 */
40
41#pragma ident	"%Z%%M%	%I%	%E% SMI"
42
43#include "lint.h"
44#include <sys/types.h>
45#include <sys/stat.h>
46#include <fcntl.h>
47#include <sys/file.h>
48#include <stdio.h>
49#include <stdlib.h>
50#include <errno.h>
51#include <ndbm.h>
52#include <unistd.h>
53#include <string.h>
54#include <pthread.h>
55
56/* add support for batched writing for NIS */
57
58#define	_DBM_DEFWRITE 0x4
59#define	_DBM_DIRTY 0x8
60#define	_DBM_DIRDIRTY 0x10
61#define	dbm_dirty(db) ((db)->dbm_flags & _DBM_DIRTY)
62#define	dbm_dirdirty(db) ((db)->dbm_flags & _DBM_DIRDIRTY)
63#define	dbm_defwrite(db) ((db)->dbm_flags & _DBM_DEFWRITE)
64#define	dbm_setdirty(db) (db)->dbm_flags |= _DBM_DIRTY
65#define	dbm_clrdirty(db) (db)->dbm_flags &= ~_DBM_DIRTY
66#define	dbm_setdirdirty(db) (db)->dbm_flags |= _DBM_DIRDIRTY
67#define	dbm_clrdirdirty(db) (db)->dbm_flags &= ~_DBM_DIRDIRTY
68
69/*
70 * forward declarations
71 */
72static datum makdatum(char *, int);
73static unsigned long dcalchash(datum);
74static void dbm_access(DBM *, unsigned long);
75static int finddatum(char *, datum);
76static int delitem(char *, int);
77static int additem(char *, datum, datum);
78static int cmpdatum(datum, datum);
79static int setbit(DBM *);
80static int getbit(DBM *);
81static int dbm_flushdir(DBM *);
82static int dbm_flushpag(DBM *db);
83
84/* the following three are required by mapfile-vers */
85datum dbm_do_nextkey(DBM *, datum);
86int dbm_close_status(DBM *);
87
88/* used to make a dbm file all at once instead of incrementally */
89void
90dbm_setdefwrite(DBM *db)
91{
92	db->dbm_flags |= _DBM_DEFWRITE;
93}
94
95#undef	dbm_error
96
97int
98dbm_error(DBM *db)
99{
100	return (db->dbm_flags & _DBM_IOERR);
101}
102
103#undef	dbm_clearerr
104
105int
106dbm_clearerr(DBM *db)
107{
108	return (db->dbm_flags &= ~_DBM_IOERR);
109}
110
111int
112dbm_flush(DBM *db)
113{
114	int ok = 0;
115	if (dbm_flushpag(db) < 0)
116		ok = -1;
117	if (dbm_flushdir(db) < 0)
118		ok = -1;
119	return (ok);
120}
121
122static int
123dbm_flushpag(DBM *db)
124{
125	int ok = 0;
126	off64_t where;
127
128	if (dbm_dirty(db)) { /* must page out the page */
129		where = (((off64_t)db->dbm_pagbno) * PBLKSIZ);
130		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
131		    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
132			db->dbm_flags |= _DBM_IOERR;
133			ok = -1;
134		}
135		dbm_clrdirty(db);
136	}
137	return (ok);
138}
139
140static int
141dbm_flushdir(DBM *db)
142{
143	int ok = 0;
144	off64_t where;
145	if (dbm_dirdirty(db)) { /* must page out the dir */
146		where = (((off64_t)db->dbm_dirbno) * DBLKSIZ);
147		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
148		    (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)) {
149			ok = -1;
150		}
151		dbm_clrdirdirty(db);
152	}
153	return (ok);
154}
155
156#define	BYTESIZ 8
157#undef setbit
158
159DBM *
160dbm_open(const char *file, int flags, mode_t mode)
161{
162	struct stat64 statb;
163	DBM *db;
164	int	serrno;
165
166	if ((db = (DBM *)malloc(sizeof (*db))) == 0) {
167		errno = ENOMEM;
168		return ((DBM *)0);
169	}
170	db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
171	if ((flags & 03) == O_WRONLY)
172		flags = (flags & ~03) | O_RDWR;
173	if (strlcpy(db->dbm_pagbuf, file, sizeof (db->dbm_pagbuf)) >=
174	    sizeof (db->dbm_pagbuf) ||
175	    strlcat(db->dbm_pagbuf, ".pag", sizeof (db->dbm_pagbuf)) >=
176	    sizeof (db->dbm_pagbuf)) {
177		/*
178		 * file.pag does not fit into dbm_pagbuf.
179		 * fail with ENAMETOOLONG.
180		 */
181		serrno = ENAMETOOLONG;
182		goto bad;
183	}
184	db->dbm_pagf = open64(db->dbm_pagbuf, flags, mode);
185	if (db->dbm_pagf < 0) {
186		serrno = errno;
187		goto bad;
188	}
189	/*
190	 * We know this won't overflow so it is safe to ignore the
191	 * return value; we use strl* to prevent false hits in
192	 * code sweeps.
193	 */
194	(void) strlcpy(db->dbm_pagbuf, file, sizeof (db->dbm_pagbuf));
195	(void) strlcat(db->dbm_pagbuf, ".dir", sizeof (db->dbm_pagbuf));
196	db->dbm_dirf = open64(db->dbm_pagbuf, flags, mode);
197	if (db->dbm_dirf < 0) {
198		serrno = errno;
199		goto bad1;
200	}
201	(void) fstat64(db->dbm_dirf, &statb);
202	db->dbm_maxbno = statb.st_size * BYTESIZ-1;
203	db->dbm_pagbno = db->dbm_dirbno = -1;
204	return (db);
205bad1:
206	(void) close(db->dbm_pagf);
207bad:
208	free((char *)db);
209	errno = serrno;
210	return ((DBM *)0);
211}
212
213void
214dbm_close(DBM *db)
215{
216(void) dbm_close_status(db);
217}
218
219/* close with return code */
220int
221dbm_close_status(DBM *db)
222{
223	int ok;
224	ok = 0;
225
226	if (dbm_flush(db) < 0)
227		ok = -1;
228	if (close(db->dbm_dirf) < 0)
229		ok = -1;
230	if (close(db->dbm_pagf) < 0)
231		ok = -1;
232	free((char *)db);
233	return (ok);
234}
235
236long
237dbm_forder(DBM *db, datum key)
238{
239	unsigned long hash;
240
241	hash = dcalchash(key);
242	for (db->dbm_hmask = 0; ; db->dbm_hmask = (db->dbm_hmask<<1)+1) {
243		db->dbm_blkno = hash & db->dbm_hmask;
244		db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
245		if (getbit(db) == 0)
246			break;
247	}
248	return (db->dbm_blkno);
249}
250
251datum
252dbm_fetch(DBM *db, datum key)
253{
254	int i;
255	datum item;
256
257	if (dbm_error(db))
258		goto err;
259	dbm_access(db, dcalchash(key));
260	if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
261		item = makdatum(db->dbm_pagbuf, i+1);
262		if (item.dptr != NULL)
263			return (item);
264	}
265err:
266	item.dptr = NULL;
267	item.dsize = 0;
268	return (item);
269}
270
271int
272dbm_delete(DBM *db, datum key)
273{
274	int i;
275	off64_t where;
276
277	if (dbm_error(db))
278		return (-1);
279	if (dbm_rdonly(db)) {
280		errno = EPERM;
281		return (-1);
282	}
283	dbm_access(db, dcalchash(key));
284	if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
285		return (-1);
286	if (!delitem(db->dbm_pagbuf, i))
287		goto err;
288	db->dbm_pagbno = db->dbm_blkno;
289	if (dbm_defwrite(db)) {
290		dbm_setdirty(db);
291	} else {
292		where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
293		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
294		    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
295			err:
296				db->dbm_flags |= _DBM_IOERR;
297				return (-1);
298		}
299	}
300	return (0);
301}
302
303int
304dbm_store(DBM *db, datum key, datum dat, int replace)
305{
306	int i;
307	datum item, item1;
308	char ovfbuf[PBLKSIZ];
309	unsigned long hashdiff, key_hash, item_hash;
310	off64_t where;
311
312	if (dbm_error(db))
313		return (-1);
314	if (dbm_rdonly(db)) {
315		errno = EPERM;
316		return (-1);
317	}
318loop:
319	key_hash = dcalchash(key);
320	dbm_access(db, key_hash);
321	if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
322		if (!replace)
323			return (1);
324		if (!delitem(db->dbm_pagbuf, i)) {
325			db->dbm_flags |= _DBM_IOERR;
326			return (-1);
327		}
328	}
329	if (!additem(db->dbm_pagbuf, key, dat))
330		goto split;
331	db->dbm_pagbno = db->dbm_blkno;
332	if (dbm_defwrite(db)) {
333		dbm_setdirty(db);
334	} else {
335		where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
336		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
337		    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
338			db->dbm_flags |= _DBM_IOERR;
339			return (-1);
340		}
341	}
342	return (0);
343split:
344	hashdiff = 0;
345	if (key.dsize + dat.dsize + 3 * (int)sizeof (short) >= PBLKSIZ) {
346		db->dbm_flags |= _DBM_IOERR;
347		errno = ENOSPC;
348		return (-1);
349	}
350	(void) memset(ovfbuf, 0, PBLKSIZ);
351	for (i = 0; ; ) {
352		item = makdatum(db->dbm_pagbuf, i);
353		if (item.dptr == NULL)
354			break;
355		item_hash = dcalchash(item);
356		if (item_hash != key_hash) {
357			hashdiff++;
358		}
359
360		if (item_hash & (db->dbm_hmask+1)) {
361			item1 = makdatum(db->dbm_pagbuf, i+1);
362			if (item1.dptr == NULL) {
363				/* (void) fprintf(stderr, "ndbm: */
364				/* split not paired\n"); */
365				db->dbm_flags |= _DBM_IOERR;
366				break;
367			}
368			if (!additem(ovfbuf, item, item1) ||
369			    !delitem(db->dbm_pagbuf, i)) {
370				db->dbm_flags |= _DBM_IOERR;
371				return (-1);
372			}
373			continue;
374		}
375		i += 2;
376	}
377	db->dbm_pagbno = db->dbm_blkno;
378	where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
379	if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
380	    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
381		db->dbm_flags |= _DBM_IOERR;
382		return (-1);
383	}
384	dbm_clrdirty(db); /* clear dirty */
385	where = (((off64_t)db->dbm_blkno + db->dbm_hmask + 1) * PBLKSIZ);
386	if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
387	    (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ)) {
388		db->dbm_flags |= _DBM_IOERR;
389		return (-1);
390	}
391	if (setbit(db) < 0) {
392		db->dbm_flags |= _DBM_IOERR;
393		return (-1);
394	}
395	if (hashdiff == 0) {
396		db->dbm_flags |= _DBM_IOERR;
397		return (-1);
398	}
399	goto loop;
400}
401
402static unsigned long
403dbm_hashinc(DBM *db, unsigned long hash)
404{
405	long bit;
406
407	hash &= db->dbm_hmask;
408	bit = db->dbm_hmask+1;
409	for (;;) {
410		bit >>= 1;
411		if (bit == 0)
412			return (0L);
413		if ((hash&bit) == 0)
414			return (hash|bit);
415		hash &= ~bit;
416	}
417}
418
419
420
421static datum nullkey = {NULL, 0};
422
423datum
424dbm_firsthash(DBM *db, unsigned long hash)
425{
426	int i, j;
427	datum item, bitem;
428
429loop:
430	dbm_access(db, hash);
431	j = 0;
432	bitem = makdatum(db->dbm_pagbuf, 0);
433	for (i = 2; ; i += 2) {
434		item = makdatum(db->dbm_pagbuf, i);
435		if (item.dptr == NULL)
436			break;
437		if (cmpdatum(bitem, item) < 0) {
438			j = i;
439			bitem = item;
440		}
441	}
442	if (bitem.dptr != NULL) {
443		db->dbm_keyptr = j + 2;
444		db->dbm_blkptr = db->dbm_blkno;
445		return (bitem);
446	}
447	hash = dbm_hashinc(db, hash);
448	if (hash == 0)
449		return (item); /* null item */
450	goto loop;
451
452}
453
454datum
455dbm_firstkey(DBM *db)
456{
457	/*
458	 * For some reason, the Posix specification (SUSv3)
459	 * says that dbm_firstkey() is not a cancellation point.
460	 * It really should be, but in order to pass the SUSv3
461	 * test suite we make it not a cancellation point.
462	 * XXX: fix me when the SUSv3 specification gets fixed.
463	 */
464	int cancel_state;
465	datum rval;
466
467	db->dbm_blkptr = 0L;
468	db->dbm_keyptr = 0;
469	(void) pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cancel_state);
470	rval = dbm_firsthash(db, 0L);
471	(void) pthread_setcancelstate(cancel_state, NULL);
472	return (rval);
473}
474
475datum
476dbm_nextkey(DBM *db)
477{
478
479	return (dbm_do_nextkey(db, nullkey));
480}
481
482/*
483 * this is used if keyptr-2, blocknum doesn't point to the previous
484 * specific key allowing the fast hash order search --
485 * its use indicates user tampering with our state variables,
486 * which some evil users might do to search from some specific place.
487 * It finds the first key at or after blkptr, keyptr in block seq order
488 * this requires looking at all sorts of emtpy blocks in many cases
489 */
490
491static
492datum
493dbm_slow_nextkey(DBM *db)
494{
495
496	struct stat64 statb;
497	datum item;
498	off64_t where;
499
500	if (dbm_error(db) || fstat64(db->dbm_pagf, &statb) < 0)
501		goto err;
502	statb.st_size /= PBLKSIZ;
503
504	for (;;) {
505		if (db->dbm_blkptr != db->dbm_pagbno) {
506
507			if (dbm_dirty(db)) (void) dbm_flushpag(db);
508
509			db->dbm_pagbno = db->dbm_blkptr;
510			where = (((off64_t)db->dbm_blkptr) * PBLKSIZ);
511			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
512			    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
513			    PBLKSIZ))
514				(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
515#ifdef DEBUG
516			else if (chkblk(db->dbm_pagbuf) < 0)
517				db->dbm_flags |= _DBM_IOERR;
518#endif
519		}
520		/* Am I an empty block? */
521		if (((short *)(uintptr_t)db->dbm_pagbuf)[0] != 0) {
522			item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
523			if (item.dptr != NULL) {
524				db->dbm_keyptr += 2;
525				return (item);
526			}
527			db->dbm_keyptr = 0;
528		}
529		/* go to next sequential block */
530		if (++db->dbm_blkptr >= statb.st_size)
531			break;
532	}
533err:
534	item.dptr = NULL;
535	item.dsize = 0;
536	return (item);
537}
538
539
540
541datum
542dbm_do_nextkey(DBM *db, datum inkey)
543{
544	datum item, bitem;
545	unsigned long hash;
546	datum key;
547	int f;
548	int i;
549	int j;
550	short *sp;
551	long n;
552	char *p1, *p2;
553	off64_t where;
554
555	if (dbm_error(db)) {
556		item.dptr = NULL;
557		item.dsize = 0;
558		return (item);
559	}
560
561	/* user has supplied lastkey */
562
563	if (inkey.dptr != NULL) {
564		dbm_access(db, (hash = dcalchash(inkey)));
565		if ((i = finddatum(db->dbm_pagbuf, inkey)) >= 0) {
566			db->dbm_keyptr = i + 2;
567			db->dbm_blkptr = db->dbm_blkno;
568		}
569		key = inkey;
570	} else  {
571		/* is this a manual firstkey request? */
572
573		if (db->dbm_blkptr == 0L &&
574		    db->dbm_keyptr == 0)
575			return (dbm_firsthash(db, 0L));
576
577		/* no -- get lastkey this is like dbm_access by blkptr */
578
579		if (db->dbm_blkptr != db->dbm_pagbno) {
580
581			if (dbm_dirty(db)) (void) dbm_flushpag(db);
582			db->dbm_pagbno = db->dbm_blkptr;
583			where = (((off64_t)db->dbm_blkptr) * PBLKSIZ);
584			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
585			    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
586			    PBLKSIZ))
587				(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
588#ifdef DEBUG
589			else if (chkblk(db->dbm_pagbuf) < 0)
590			db->dbm_flags |= _DBM_IOERR;
591#endif
592		}
593		/* now just make up last key datum */
594		if (db->dbm_keyptr >= 2)
595			key = makdatum(db->dbm_pagbuf, (db->dbm_keyptr-2));
596		else key = nullkey;
597
598		/*
599		 * the keyptr pagbuf have failed us, the user must
600		 * be an extra clever moron who depends on
601		 * these variables and their former meaning.
602		 * If we set the variables this would have got
603		 * us the key for sure! So give it the old algorithm.
604		 */
605		if (key.dptr == NULL)
606			return (dbm_slow_nextkey(db));
607	}
608
609	/*
610	 * at this point the last key is paged in and
611	 * we can proceed as in old dbm -- like Ken did his.
612	 */
613
614	f = 1;
615	j = 0;
616	sp = (short *)(uintptr_t)db->dbm_pagbuf;
617
618	for (i = 0; ; i += 2) {
619
620		/* begin put makdatum inline */
621
622		if ((unsigned)i >= sp[0]) {
623			item.dptr = NULL;
624			item.dsize = 0;
625			break; /* from below */
626		} else {
627			if (i > 0) item.dsize = sp[i] - sp[i + 1];
628			else item.dsize = PBLKSIZ - sp[i + 1];
629			item.dptr = db->dbm_pagbuf+sp[i + 1];
630		}
631
632		/* item = makdatum(db->dbm_pagbuf, i); */
633		/* end put makdatum inline */
634
635		if (item.dptr == NULL)
636			break;
637/* inline cmpdatum */
638
639
640		n = key.dsize;
641		if (n != item.dsize) {
642			if ((n - item.dsize) <= 0)
643				continue;
644		} else {
645			if (n == 0) continue;
646			p1 = key.dptr;
647			p2 = item.dptr;
648			do {
649				if (*p1++ != *p2++)
650					if ((*--p1 - *--p2) > 0)
651						goto keep_going;
652					else continue;
653			} while (--n);
654			continue;
655		}
656
657keep_going:
658
659/* end inline cmpdatum */
660		/*
661		 * if (cmpdatum(key, item) <= 0)
662		 *	continue;
663		 */
664
665		if (f) {
666			bitem = item;
667			j = i;
668			f = 0;
669		} else {
670
671			/* if (cmpdatum(bitem, item) < 0) */
672
673			n = bitem.dsize;
674			if (n != item.dsize) {
675				if ((n - item.dsize) < 0) {
676					bitem = item;
677					j = i;
678				}
679			} else
680				if (n != 0) {
681					p1 = bitem.dptr;
682					p2 = item.dptr;
683					do {
684					if (*p1++ != *p2++) {
685						if ((*--p1 - *--p2) < 0) {
686							bitem = item;
687							j = i;
688						}
689						break;
690					}
691					} while (--n);
692				}
693			}
694	}
695
696	if (f == 0) {
697		db->dbm_keyptr = j + 2;
698		db->dbm_blkptr = db->dbm_blkno;
699		return (bitem);
700	}
701
702	/* really need hash at this point */
703	/* if it gave us a key we have already calculated the hash */
704	/* if not get the hash */
705	if (inkey.dptr == NULL)
706		hash = dcalchash(key);
707	hash = dbm_hashinc(db, hash);
708
709	if (hash == 0)
710		return (item); /* null */
711	/* get first item on next page in hash table order */
712	return (dbm_firsthash(db, hash));
713
714
715}
716
717static void
718dbm_access(DBM *db, unsigned long hash)
719{
720	long b, i, n;
721	long bn;
722	long my_bitno;
723	long my_hmask;
724	long my_blkno;
725	int j = (sizeof (my_hmask)) * 8;
726	off64_t where;
727
728	for (my_hmask = 0; j-- > 0; my_hmask = (my_hmask<<1) + 1) {
729		my_blkno = hash & my_hmask;
730		my_bitno = my_blkno + my_hmask;
731		/* getbit inline */
732		if (my_bitno > db->dbm_maxbno) break;
733		n = my_bitno % BYTESIZ;
734		bn = my_bitno / BYTESIZ;
735		i = bn % DBLKSIZ;
736		b = bn / DBLKSIZ;
737		if (b != db->dbm_dirbno) {
738			if (dbm_dirdirty(db))
739				(void) dbm_flushdir(db); /* must flush */
740			db->dbm_dirbno = b;
741			where = (((off64_t)b) * DBLKSIZ);
742			if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
743			    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) !=
744			    DBLKSIZ))
745				(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
746		}
747		if ((db->dbm_dirbuf[i] & (1<<n)) == 0) break;
748
749		/*
750		 * if (getbit(db) == 0)
751		 *	break;
752		 */
753	}
754	/* copy */
755	db->dbm_blkno = my_blkno;
756	db->dbm_bitno = my_bitno;
757	db->dbm_hmask = my_hmask;
758
759	if (my_blkno != db->dbm_pagbno) {
760		if (dbm_dirty(db)) { /* must page out the page */
761			where = (((off64_t)db->dbm_pagbno) * PBLKSIZ);
762			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
763			    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
764			    PBLKSIZ)) {
765				db->dbm_flags |= _DBM_IOERR;
766			}
767		dbm_clrdirty(db);
768		}
769
770		db->dbm_pagbno = my_blkno;
771		where = (((off64_t)my_blkno) * PBLKSIZ);
772		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
773		    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ))
774			(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
775#ifdef DEBUG
776		else if (chkblk(db->dbm_pagbuf) < 0)
777			db->dbm_flags |= _DBM_IOERR;
778#endif
779	}
780}
781
782static int
783getbit(DBM *db)
784{
785	long bn;
786	long b, i, n;
787	off64_t where;
788
789	if (db->dbm_bitno > db->dbm_maxbno)
790		return (0);
791	n = db->dbm_bitno % BYTESIZ;
792	bn = db->dbm_bitno / BYTESIZ;
793	i = bn % DBLKSIZ;
794	b = bn / DBLKSIZ;
795	if (b != db->dbm_dirbno) {
796		if (dbm_dirdirty(db))
797			(void) dbm_flushdir(db); /* must flush */
798		db->dbm_dirbno = b;
799		where = (((off64_t)b) * DBLKSIZ);
800		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
801		    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ))
802			(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
803	}
804	return (db->dbm_dirbuf[i] & (1<<n));
805}
806
807static int
808setbit(DBM *db)
809{
810	long bn;
811	long i, n, b;
812	off64_t where;
813
814	if (db->dbm_bitno > db->dbm_maxbno)
815		db->dbm_maxbno = db->dbm_bitno;
816	n = db->dbm_bitno % BYTESIZ;
817	bn = db->dbm_bitno / BYTESIZ;
818	i = bn % DBLKSIZ;
819	b = bn / DBLKSIZ;
820	if (b != db->dbm_dirbno) {
821		if (dbm_dirdirty(db))
822			(void) dbm_flushdir(db);
823		db->dbm_dirbno = b;
824		where = (((off64_t)b) * DBLKSIZ);
825		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
826		    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ))
827			(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
828	}
829	db->dbm_dirbuf[i] |= 1<<n;
830	db->dbm_dirbno = b;
831	if (dbm_defwrite(db)) {
832		dbm_setdirdirty(db);
833	} else {
834		where = (((off64_t)b) * DBLKSIZ);
835		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
836		    (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)) {
837			return (-1);
838		}
839	}
840	return (0);
841}
842
843static datum
844makdatum(char buf[PBLKSIZ], int n)
845{
846	short *sp;
847	int t;
848	datum item;
849
850	sp = (short *)(uintptr_t)buf;
851	if ((unsigned)n >= sp[0]) {
852		item.dptr = NULL;
853		item.dsize = 0;
854		return (item);
855	}
856	t = PBLKSIZ;
857	if (n > 0)
858		t = sp[n];
859	item.dptr = buf + sp[n + 1];
860	item.dsize = t - sp[n + 1];
861	return (item);
862}
863
864static int
865cmpdatum(datum d1, datum d2)
866{
867	long n;
868	char *p1, *p2;
869
870	n = d1.dsize;
871	if (n != d2.dsize)
872		return ((int)(n - d2.dsize));
873	if (n == 0)
874		return (0);
875	p1 = d1.dptr;
876	p2 = d2.dptr;
877	do {
878		if (*p1 != *p2)
879			return (*p1 - *p2);
880		else {
881			p1++;
882			p2++;
883		}
884	} while (--n);
885	return (0);
886}
887
888static int
889finddatum(char buf[PBLKSIZ], datum item)
890{
891	short *sp;
892	int i, n, j;
893
894	sp = (short *)(uintptr_t)buf;
895	n = PBLKSIZ;
896	for (i = 0, j = sp[0]; i < j; i += 2, n = sp[i]) {
897		n -= sp[i + 1];
898		if (n != item.dsize)
899			continue;
900		if (n == 0 || memcmp(&buf[sp[i+1]], item.dptr, n) == 0)
901			return (i);
902	}
903	return (-1);
904}
905
906static const int hitab[16]
907/*
908 * ken's
909 * {
910 *	055, 043, 036, 054, 063, 014, 004, 005,
911 *	010, 064, 077, 000, 035, 027, 025, 071,
912 * };
913 */
914	= {    61, 57, 53, 49, 45, 41, 37, 33,
915		29, 25, 21, 17, 13,  9,  5,  1,
916};
917
918/* could consider to make it 32-bit int table to minimize memory usage */
919static const long hltab[64]
920	= {
921	06100151277L, 06106161736L, 06452611562L, 05001724107L,
922	02614772546L, 04120731531L, 04665262210L, 07347467531L,
923	06735253126L, 06042345173L, 03072226605L, 01464164730L,
924	03247435524L, 07652510057L, 01546775256L, 05714532133L,
925	06173260402L, 07517101630L, 02431460343L, 01743245566L,
926	00261675137L, 02433103631L, 03421772437L, 04447707466L,
927	04435620103L, 03757017115L, 03641531772L, 06767633246L,
928	02673230344L, 00260612216L, 04133454451L, 00615531516L,
929	06137717526L, 02574116560L, 02304023373L, 07061702261L,
930	05153031405L, 05322056705L, 07401116734L, 06552375715L,
931	06165233473L, 05311063631L, 01212221723L, 01052267235L,
932	06000615237L, 01075222665L, 06330216006L, 04402355630L,
933	01451177262L, 02000133436L, 06025467062L, 07121076461L,
934	03123433522L, 01010635225L, 01716177066L, 05161746527L,
935	01736635071L, 06243505026L, 03637211610L, 01756474365L,
936	04723077174L, 03642763134L, 05750130273L, 03655541561L,
937};
938
939static unsigned long
940dcalchash(datum item)
941{
942	long s;
943	int c, j;
944	char *cp;
945	unsigned long hashl;
946	long hashi;
947
948	hashl = 0;
949	hashi = 0;
950	for (cp = item.dptr, s = item.dsize; --s >= 0; ) {
951		c = *cp++;
952		for (j = 0; j < BYTESIZ; j += 4) {
953			hashi += hitab[c&017];
954			hashl += hltab[hashi&63];
955			c >>= 4;
956		}
957	}
958	return (hashl);
959}
960
961/*
962 * Delete pairs of items (n & n+1).
963 */
964static int
965delitem(char buf[PBLKSIZ], int n)
966{
967	short *sp, *sp1;
968	int i1, i2;
969
970	sp = (short *)(uintptr_t)buf;
971	i2 = sp[0];
972	if ((unsigned)n >= i2 || (n & 1))
973		return (0);
974	if (n == i2-2) {
975		sp[0] -= 2;
976		return (1);
977	}
978	i1 = PBLKSIZ;
979	if (n > 0)
980		i1 = sp[n];
981	i1 -= sp[n+2];
982	if (i1 > 0) {
983		i2 = sp[i2];
984		(void) memmove(&buf[i2 + i1], &buf[i2], sp[n+2] - i2);
985	}
986	sp[0] -= 2;
987	for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
988		sp[0] = sp[2] + i1;
989	return (1);
990}
991
992/*
993 * Add pairs of items (item & item1).
994 */
995static int
996additem(char buf[PBLKSIZ], datum item, datum item1)
997{
998	short *sp;
999	int i1, i2;
1000
1001	sp = (short *)(uintptr_t)buf;
1002	i1 = PBLKSIZ;
1003	i2 = sp[0];
1004	if (i2 > 0)
1005		i1 = sp[i2];
1006	i1 -= item.dsize + item1.dsize;
1007	if (i1 <= (i2+3) * (int)sizeof (short))
1008		return (0);
1009	sp[0] += 2;
1010	sp[++i2] = (short)(i1 + item1.dsize);
1011	(void) memmove(&buf[i1 + item1.dsize], item.dptr, item.dsize);
1012	sp[++i2] = i1;
1013	(void) memmove(&buf[i1], item1.dptr, item1.dsize);
1014	return (1);
1015}
1016
1017#ifdef DEBUG
1018static int
1019chkblk(char buf[PBLKSIZ])
1020{
1021	short *sp;
1022	int t, i;
1023
1024	sp = (short *)buf;
1025	t = PBLKSIZ;
1026	for (i = 0; i < sp[0]; i++) {
1027		if (sp[i + 1] > t)
1028			return (-1);
1029		t = sp[i + 1];
1030	}
1031	if (t < (sp[0] + 1) * sizeof (short))
1032		return (-1);
1033	return (0);
1034}
1035#endif
1036