xref: /illumos-gate/usr/src/lib/libnsl/yp/dbm.c (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
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, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 /*	Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T */
28 /*	  All Rights Reserved   */
29 
30 /*
31  * Portions of this source code were derived from Berkeley
32  * under license from the Regents of the University of
33  * California.
34  */
35 
36 #pragma ident	"%Z%%M%	%I%	%E% SMI"
37 
38 #include <rpcsvc/dbm.h>
39 #include <sys/types.h>
40 #include <rpc/trace.h>
41 #include <sys/stat.h>
42 #include <string.h>
43 #include <unistd.h>
44 #include <stdlib.h>
45 #include <fcntl.h>
46 #include <stdio.h>
47 #include <errno.h>
48 
49 #if defined(sparc)
50 #define	_FSTAT	_fstat
51 extern int _fstat(int, struct stat *);
52 #else  /* !sparc */
53 #define	_FSTAT	fstat
54 #endif /* sparc */
55 
56 
57 void dbm_access(long);
58 void delitem(char *, int);
59 void chkblk(char *);
60 int  additem(char *, datum);
61 int  getbit(void);
62 int  setbit(void);
63 int  cmpdatum(datum, datum);
64 
65 int
66 dbminit(file)
67 	char *file;
68 {
69 	struct stat statb;
70 
71 	trace1(TR_dbminit, 0);
72 	dbrdonly = 0;
73 	if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) ||
74 	    strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) {
75 		/*
76 		 * file.pag does not fit into pagbuf.
77 		 * fails with ENAMETOOLONG.
78 		 */
79 		trace1(TR_dbminit, 1);
80 		errno = ENAMETOOLONG;
81 		return (-1);
82 	}
83 	pagf = open(pagbuf, 2);
84 	if (pagf < 0) {
85 		pagf = open(pagbuf, 0);
86 		dbrdonly = 1;
87 	}
88 	/*
89 	 * We know this won't overflow so it is safe to ignore the
90 	 * return value; we use strl* to prevent false hits in
91 	 * code sweeps.
92 	 */
93 	(void) strlcpy(pagbuf, file, sizeof (pagbuf));
94 	(void) strlcat(pagbuf, ".dir", sizeof (pagbuf));
95 	dirf = open(pagbuf, 2);
96 	if (dirf < 0) {
97 		dirf = open(pagbuf, 0);
98 		dbrdonly = 1;
99 	}
100 	if (pagf < 0 || dirf < 0) {
101 		trace1(TR_dbminit, 1);
102 		return (-1);
103 	}
104 	_FSTAT(dirf, &statb);
105 	maxbno = statb.st_size*BYTESIZ-1;
106 	trace1(TR_dbminit, 1);
107 	return (0);
108 }
109 
110 static long oldb1 = -1;
111 static long oldb2 = -1;
112 
113 /* Avoid using cached data for subsequent accesses. */
114 int
115 dbmflush()
116 {
117 	trace1(TR_dbmflush, 0);
118 	oldb1 = -1;
119 	oldb2 = -1;
120 	trace1(TR_dbmflush, 1);
121 	return (0);
122 }
123 
124 /* Clean up after ourself. */
125 int
126 dbmclose()
127 {
128 	trace1(TR_dbmclose, 0);
129 	(void) close(pagf);
130 	(void) close(dirf);
131 	bitno = 0;
132 	maxbno = 0;
133 	blkno = 0;
134 	hmask = 0;
135 	oldb1 = -1;
136 	oldb2 = -1;
137 	trace1(TR_dbmclose, 1);
138 	return (0);
139 }
140 
141 long
142 forder(key)
143 	datum key;
144 {
145 	long hash;
146 
147 	trace1(TR_forder, 0);
148 	hash = calchash(key);
149 	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
150 		blkno = hash & hmask;
151 		bitno = blkno + hmask;
152 		if (getbit() == 0)
153 			break;
154 	}
155 	trace1(TR_forder, 1);
156 	return (blkno);
157 }
158 
159 datum
160 fetch(key)
161 	datum key;
162 {
163 	int i;
164 	datum item;
165 
166 	trace1(TR_fetch, 0);
167 	dbm_access(calchash(key));
168 	for (i = 0; ; i += 2) {
169 		item = makdatum(pagbuf, i);
170 		if (item.dptr == NULL) {
171 			trace1(TR_fetch, 1);
172 			return (item);
173 		}
174 		if (cmpdatum(key, item) == 0) {
175 			item = makdatum(pagbuf, i+1);
176 			if (item.dptr == NULL)
177 				(void) printf("items not in pairs\n");
178 			trace1(TR_fetch, 1);
179 			return (item);
180 		}
181 	}
182 }
183 
184 int
185 delete(key)
186 	datum key;
187 {
188 	int i;
189 	datum item;
190 
191 	trace1(TR_delete, 0);
192 	if (dbrdonly) {
193 		trace1(TR_delete, 1);
194 		return (-1);
195 	}
196 	dbm_access(calchash(key));
197 	for (i = 0; ; i += 2) {
198 		item = makdatum(pagbuf, i);
199 		if (item.dptr == NULL) {
200 			trace1(TR_delete, 1);
201 			return (-1);
202 		}
203 		if (cmpdatum(key, item) == 0) {
204 			delitem(pagbuf, i);
205 			delitem(pagbuf, i);
206 			break;
207 		}
208 	}
209 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
210 	(void) write(pagf, pagbuf, PBLKSIZ);
211 	trace1(TR_delete, 1);
212 	return (0);
213 }
214 
215 int
216 store(key, dat)
217 	datum key, dat;
218 {
219 	int i;
220 	datum item;
221 	char ovfbuf[PBLKSIZ];
222 
223 	trace1(TR_store, 0);
224 	if (dbrdonly) {
225 		trace1(TR_store, 1);
226 		return (-1);
227 	}
228 loop:
229 	dbm_access(calchash(key));
230 	for (i = 0; ; i += 2) {
231 		item = makdatum(pagbuf, i);
232 		if (item.dptr == NULL)
233 			break;
234 		if (cmpdatum(key, item) == 0) {
235 			delitem(pagbuf, i);
236 			delitem(pagbuf, i);
237 			break;
238 		}
239 	}
240 	i = additem(pagbuf, key);
241 	if (i < 0)
242 		goto split;
243 	if (additem(pagbuf, dat) < 0) {
244 		delitem(pagbuf, i);
245 		goto split;
246 	}
247 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
248 	(void) write(pagf, pagbuf, PBLKSIZ);
249 	trace1(TR_store, 1);
250 	return (0);
251 
252 split:
253 	if (key.dsize + dat.dsize + 3 * sizeof (short) >= PBLKSIZ) {
254 		(void) printf("entry too big\n");
255 		trace1(TR_store, 1);
256 		return (-1);
257 	}
258 	(void) memset((char *)&ovfbuf, 0, PBLKSIZ);
259 	for (i = 0; ; ) {
260 		item = makdatum(pagbuf, i);
261 		if (item.dptr == NULL)
262 			break;
263 		if (calchash(item) & (hmask+1)) {
264 			(void) additem(ovfbuf, item);
265 			delitem(pagbuf, i);
266 			item = makdatum(pagbuf, i);
267 			if (item.dptr == NULL) {
268 				(void) printf("split not paired\n");
269 				break;
270 			}
271 			(void) additem(ovfbuf, item);
272 			delitem(pagbuf, i);
273 			continue;
274 		}
275 		i += 2;
276 	}
277 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
278 	if (write(pagf, pagbuf, PBLKSIZ) < 0) {
279 		trace1(TR_store, 1);
280 		return (-1);
281 	}
282 	(void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
283 	if (write(pagf, ovfbuf, PBLKSIZ) < 0) {
284 		trace1(TR_store, 1);
285 		return (-1);
286 	}
287 	if (setbit() < 0) {
288 		trace1(TR_store, 1);
289 		return (-1);
290 	}
291 	goto loop;
292 }
293 
294 datum
295 firstkey()
296 {
297 	datum dummy;
298 
299 	trace1(TR_firstkey, 0);
300 	dummy = firsthash(0L);
301 	trace1(TR_firstkey, 1);
302 	return (dummy);
303 }
304 
305 datum
306 nextkey(key)
307 	datum key;
308 {
309 	int i;
310 	datum item, bitem;
311 	long hash;
312 	int f;
313 	datum dummy;
314 
315 	trace1(TR_nextkey, 0);
316 #ifdef lint
317 	bitem.dptr = NULL;
318 	bitem.dsize = 0;
319 #endif /* lint */
320 	hash = calchash(key);
321 	dbm_access(hash);
322 	f = 1;
323 	for (i = 0; ; i += 2) {
324 		item = makdatum(pagbuf, i);
325 		if (item.dptr == NULL)
326 			break;
327 		if (cmpdatum(key, item) <= 0)
328 			continue;
329 		if (f || cmpdatum(bitem, item) < 0) {
330 			bitem = item;
331 			f = 0;
332 		}
333 	}
334 	if (f == 0) {
335 		trace1(TR_nextkey, 1);
336 		return (bitem);
337 	}
338 	hash = hashinc(hash);
339 	if (hash == 0) {
340 		trace1(TR_nextkey, 1);
341 		return (item);
342 	}
343 	dummy = firsthash(hash);
344 	trace1(TR_nextkey, 1);
345 	return (dummy);
346 }
347 
348 datum
349 firsthash(hash)
350 	long hash;
351 {
352 	int i;
353 	datum item, bitem;
354 
355 	trace2(TR_firsthash, 0, hash);
356 loop:
357 	dbm_access(hash);
358 	bitem = makdatum(pagbuf, 0);
359 	for (i = 2; ; i += 2) {
360 		item = makdatum(pagbuf, i);
361 		if (item.dptr == NULL)
362 			break;
363 		if (cmpdatum(bitem, item) < 0)
364 			bitem = item;
365 	}
366 	if (bitem.dptr != NULL) {
367 		trace1(TR_firsthash, 1);
368 		return (bitem);
369 	}
370 	hash = hashinc(hash);
371 	if (hash == 0) {
372 		trace1(TR_firsthash, 1);
373 		return (item);
374 	}
375 	goto loop;
376 }
377 
378 void
379 dbm_access(hash)
380 	long hash;
381 {
382 	ssize_t readsize;
383 
384 	trace2(TR_dbm_access, 0, hash);
385 	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
386 		blkno = hash & hmask;
387 		bitno = blkno + hmask;
388 		if (getbit() == 0)
389 			break;
390 	}
391 	if (blkno != oldb1) {
392 		(void) lseek(pagf, blkno*PBLKSIZ, 0);
393 		readsize = read(pagf, pagbuf, PBLKSIZ);
394 		if (readsize != PBLKSIZ) {
395 			if (readsize < 0) readsize = 0;
396 			(void) memset((char *)(&pagbuf+readsize),
397 			    0, PBLKSIZ-readsize);
398 		}
399 		chkblk(pagbuf);
400 		oldb1 = blkno;
401 	}
402 	trace1(TR_dbm_access, 1);
403 }
404 
405 int
406 getbit(void)
407 {
408 	long bn;
409 	ssize_t readsize;
410 	long b, i, n;
411 
412 	trace1(TR_getbit, 0);
413 	if (bitno > maxbno) {
414 		trace1(TR_getbit, 1);
415 		return (0);
416 	}
417 	n = bitno % BYTESIZ;
418 	bn = bitno / BYTESIZ;
419 	i = bn % DBLKSIZ;
420 	b = bn / DBLKSIZ;
421 	if (b != oldb2) {
422 		(void) lseek(dirf, (long)b*DBLKSIZ, 0);
423 		readsize = read(dirf, dirbuf, DBLKSIZ);
424 		if (readsize != DBLKSIZ) {
425 			if (readsize < 0) readsize = 0;
426 			(void) memset((char *)(&dirbuf+readsize),
427 			    0, DBLKSIZ-readsize);
428 		}
429 		oldb2 = b;
430 	}
431 	if (dirbuf[i] & (1<<n)) {
432 		trace1(TR_getbit, 1);
433 		return (1);
434 	}
435 	trace1(TR_getbit, 1);
436 	return (0);
437 }
438 
439 int
440 setbit(void)
441 {
442 	long bn;
443 	long i, n, b;
444 
445 	trace1(TR_setbit, 0);
446 	if (dbrdonly) {
447 		trace1(TR_setbit, 1);
448 		return (-1);
449 	}
450 	if (bitno > maxbno) {
451 		maxbno = bitno;
452 		(void) getbit();
453 	}
454 	n = bitno % BYTESIZ;
455 	bn = bitno / BYTESIZ;
456 	i = bn % DBLKSIZ;
457 	b = bn / DBLKSIZ;
458 	dirbuf[i] |= 1<<n;
459 	(void) lseek(dirf, (long)b*DBLKSIZ, 0);
460 	if (write(dirf, dirbuf, DBLKSIZ) < 0) {
461 		trace1(TR_setbit, 1);
462 		return (-1);
463 	}
464 	trace1(TR_setbit, 1);
465 	return (0);
466 }
467 
468 datum
469 makdatum(char buf[PBLKSIZ], int n)
470 {
471 	short *sp;
472 	int t;
473 	datum item;
474 
475 	trace1(TR_makdatum, 0);
476 	sp = (short *)buf;
477 	if (n < 0 || n >= sp[0])
478 		goto null;
479 	t = PBLKSIZ;
480 	if (n > 0)
481 		t = sp[n+1-1];
482 	item.dptr = buf+sp[n+1];
483 	item.dsize = t - sp[n+1];
484 	trace1(TR_makdatum, 1);
485 	return (item);
486 
487 null:
488 	item.dptr = NULL;
489 	item.dsize = 0;
490 	trace1(TR_makdatum, 1);
491 	return (item);
492 }
493 
494 int
495 cmpdatum(d1, d2)
496 	datum d1, d2;
497 {
498 	int n;
499 	char *p1, *p2;
500 
501 	trace1(TR_cmpdatum, 0);
502 	n = d1.dsize;
503 	if (n != d2.dsize) {
504 		trace1(TR_cmpdatum, 1);
505 		return (n - d2.dsize);
506 	}
507 	if (n == 0) {
508 		trace1(TR_cmpdatum, 1);
509 		return (0);
510 	}
511 	p1 = d1.dptr;
512 	p2 = d2.dptr;
513 	do
514 		if (*p1++ != *p2++) {
515 			trace1(TR_cmpdatum, 1);
516 			return (*--p1 - *--p2);
517 		}
518 	while (--n);
519 	trace1(TR_cmpdatum, 1);
520 	return (0);
521 }
522 
523 int	hitab[16]
524 /*
525  * ken's
526  * {
527  *	055, 043, 036, 054, 063, 014, 004, 005,
528  *	010, 064, 077, 000, 035, 027, 025, 071,
529  * };
530  */
531 	= {	61, 57, 53, 49, 45, 41, 37, 33,
532 	29, 25, 21, 17, 13,  9,  5,  1,
533 };
534 long	hltab[64]
535 	= {
536 	06100151277L, 06106161736L, 06452611562L, 05001724107L,
537 	02614772546L, 04120731531L, 04665262210L, 07347467531L,
538 	06735253126L, 06042345173L, 03072226605L, 01464164730L,
539 	03247435524L, 07652510057L, 01546775256L, 05714532133L,
540 	06173260402L, 07517101630L, 02431460343L, 01743245566L,
541 	00261675137L, 02433103631L, 03421772437L, 04447707466L,
542 	04435620103L, 03757017115L, 03641531772L, 06767633246L,
543 	02673230344L, 00260612216L, 04133454451L, 00615531516L,
544 	06137717526L, 02574116560L, 02304023373L, 07061702261L,
545 	05153031405L, 05322056705L, 07401116734L, 06552375715L,
546 	06165233473L, 05311063631L, 01212221723L, 01052267235L,
547 	06000615237L, 01075222665L, 06330216006L, 04402355630L,
548 	01451177262L, 02000133436L, 06025467062L, 07121076461L,
549 	03123433522L, 01010635225L, 01716177066L, 05161746527L,
550 	01736635071L, 06243505026L, 03637211610L, 01756474365L,
551 	04723077174L, 03642763134L, 05750130273L, 03655541561L,
552 };
553 
554 long
555 hashinc(hash)
556 	long hash;
557 {
558 	long bit;
559 
560 	trace2(TR_hashinc, 0, hash);
561 	hash &= hmask;
562 	bit = hmask+1;
563 	for (; ; ) {
564 		bit >>= 1;
565 		if (bit == 0) {
566 			trace1(TR_hashinc, 1);
567 			return (0L);
568 		}
569 		if ((hash&bit) == 0) {
570 			trace1(TR_hashinc, 1);
571 			return (hash|bit);
572 		}
573 		hash &= ~bit;
574 	}
575 }
576 
577 long
578 calchash(item)
579 	datum item;
580 {
581 	int i, j, f;
582 	long hashl;
583 	int hashi;
584 
585 	trace1(TR_calchash, 0);
586 	hashl = 0;
587 	hashi = 0;
588 	for (i = 0; i < item.dsize; i++) {
589 		f = item.dptr[i];
590 		for (j = 0; j < BYTESIZ; j += 4) {
591 			hashi += hitab[f&017];
592 			hashl += hltab[hashi&63];
593 			f >>= 4;
594 		}
595 	}
596 	trace1(TR_calchash, 1);
597 	return (hashl);
598 }
599 
600 void
601 delitem(buf, n)
602 	char buf[PBLKSIZ];
603 	int n;
604 {
605 	short *sp;
606 	int i1, i2, i3;
607 
608 	trace1(TR_delitem, 0);
609 	sp = (short *)buf;
610 	if (n < 0 || n >= sp[0])
611 		goto bad;
612 	i1 = sp[n+1];
613 	i2 = PBLKSIZ;
614 	if (n > 0)
615 		i2 = sp[n+1-1];
616 	i3 = sp[sp[0]+1-1];
617 	if (i2 > i1)
618 	while (i1 > i3) {
619 		i1--;
620 		i2--;
621 		buf[i2] = buf[i1];
622 		buf[i1] = 0;
623 	}
624 	i2 -= i1;
625 	for (i1 = n + 1; i1 < sp[0]; i1++)
626 		sp[i1+1-1] = sp[i1+1] + i2;
627 	sp[0]--;
628 	sp[sp[0]+1] = 0;
629 	trace1(TR_delitem, 1);
630 	return;
631 
632 bad:
633 	(void) printf("bad delitem\n");
634 	trace1(TR_delitem, 1);
635 	abort();
636 }
637 
638 int
639 additem(buf, item)
640 	char buf[PBLKSIZ];
641 	datum item;
642 {
643 	short *sp;
644 	int i1, i2;
645 
646 	trace1(TR_additem, 0);
647 	sp = (short *)buf;
648 	i1 = PBLKSIZ;
649 	if (sp[0] > 0)
650 		i1 = sp[sp[0]+1-1];
651 	i1 -= item.dsize;
652 	i2 = (sp[0]+2) * (int)sizeof (short);
653 	if (i1 <= i2) {
654 		trace1(TR_additem, 1);
655 		return (-1);
656 	}
657 	sp[sp[0]+1] = (short)i1;
658 	for (i2 = 0; i2 < item.dsize; i2++) {
659 		buf[i1] = item.dptr[i2];
660 		i1++;
661 	}
662 	sp[0]++;
663 	trace1(TR_additem, 1);
664 	return (sp[0]-1);
665 }
666 
667 void
668 chkblk(buf)
669 	char buf[PBLKSIZ];
670 {
671 	short *sp;
672 	int t, i;
673 
674 	trace1(TR_chkblk, 0);
675 	sp = (short *)buf;
676 	t = PBLKSIZ;
677 	for (i = 0; i < sp[0]; i++) {
678 		if (sp[i+1] > t)
679 			goto bad;
680 		t = sp[i+1];
681 	}
682 	if (t < (sp[0]+1) * sizeof (short))
683 		goto bad;
684 	trace1(TR_chkblk, 1);
685 	return;
686 
687 bad:
688 	(void) printf("bad block\n");
689 	trace1(TR_chkblk, 1);
690 	abort();
691 	(void) memset((char *)&buf, 0, PBLKSIZ);
692 }
693