xref: /illumos-gate/usr/src/lib/libnsl/yp/dbm.c (revision 61961e0f)
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 /*
24  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
25  * Use is subject to license terms.
26  */
27 
28 /*	Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T */
29 /*	  All Rights Reserved   */
30 
31 /*
32  * Portions of this source code were derived from Berkeley
33  * under license from the Regents of the University of
34  * California.
35  */
36 
37 #pragma ident	"%Z%%M%	%I%	%E% SMI"
38 
39 #include <rpcsvc/dbm.h>
40 #include <sys/types.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(char *file)
67 {
68 	struct stat statb;
69 
70 	dbrdonly = 0;
71 	if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) ||
72 	    strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) {
73 		/*
74 		 * file.pag does not fit into pagbuf.
75 		 * fails with ENAMETOOLONG.
76 		 */
77 		errno = ENAMETOOLONG;
78 		return (-1);
79 	}
80 	pagf = open(pagbuf, 2);
81 	if (pagf < 0) {
82 		pagf = open(pagbuf, 0);
83 		dbrdonly = 1;
84 	}
85 	/*
86 	 * We know this won't overflow so it is safe to ignore the
87 	 * return value; we use strl* to prevent false hits in
88 	 * code sweeps.
89 	 */
90 	(void) strlcpy(pagbuf, file, sizeof (pagbuf));
91 	(void) strlcat(pagbuf, ".dir", sizeof (pagbuf));
92 	dirf = open(pagbuf, 2);
93 	if (dirf < 0) {
94 		dirf = open(pagbuf, 0);
95 		dbrdonly = 1;
96 	}
97 	if (pagf < 0 || dirf < 0)
98 		return (-1);
99 	(void) _FSTAT(dirf, &statb);
100 	maxbno = statb.st_size*BYTESIZ-1;
101 	return (0);
102 }
103 
104 static long oldb1 = -1;
105 static long oldb2 = -1;
106 
107 /* Avoid using cached data for subsequent accesses. */
108 int
109 dbmflush(void)
110 {
111 	oldb1 = -1;
112 	oldb2 = -1;
113 	return (0);
114 }
115 
116 /* Clean up after ourself. */
117 int
118 dbmclose(void)
119 {
120 	(void) close(pagf);
121 	(void) close(dirf);
122 	bitno = 0;
123 	maxbno = 0;
124 	blkno = 0;
125 	hmask = 0;
126 	oldb1 = -1;
127 	oldb2 = -1;
128 	return (0);
129 }
130 
131 long
132 forder(datum key)
133 {
134 	long hash;
135 
136 	hash = calchash(key);
137 	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
138 		blkno = hash & hmask;
139 		bitno = blkno + hmask;
140 		if (getbit() == 0)
141 			break;
142 	}
143 	return (blkno);
144 }
145 
146 datum
147 fetch(datum key)
148 {
149 	int i;
150 	datum item;
151 
152 	dbm_access(calchash(key));
153 	for (i = 0; ; i += 2) {
154 		item = makdatum(pagbuf, i);
155 		if (item.dptr == NULL) {
156 			return (item);
157 		}
158 		if (cmpdatum(key, item) == 0) {
159 			item = makdatum(pagbuf, i+1);
160 			if (item.dptr == NULL)
161 				(void) printf("items not in pairs\n");
162 			return (item);
163 		}
164 	}
165 }
166 
167 int
168 delete(datum key)
169 {
170 	int i;
171 	datum item;
172 
173 	if (dbrdonly)
174 		return (-1);
175 	dbm_access(calchash(key));
176 	for (i = 0; ; i += 2) {
177 		item = makdatum(pagbuf, i);
178 		if (item.dptr == NULL)
179 			return (-1);
180 		if (cmpdatum(key, item) == 0) {
181 			delitem(pagbuf, i);
182 			delitem(pagbuf, i);
183 			break;
184 		}
185 	}
186 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
187 	(void) write(pagf, pagbuf, PBLKSIZ);
188 	return (0);
189 }
190 
191 int
192 store(datum key, datum dat)
193 {
194 	int i;
195 	datum item;
196 	char ovfbuf[PBLKSIZ];
197 
198 	if (dbrdonly)
199 		return (-1);
200 loop:
201 	dbm_access(calchash(key));
202 	for (i = 0; ; i += 2) {
203 		item = makdatum(pagbuf, i);
204 		if (item.dptr == NULL)
205 			break;
206 		if (cmpdatum(key, item) == 0) {
207 			delitem(pagbuf, i);
208 			delitem(pagbuf, i);
209 			break;
210 		}
211 	}
212 	i = additem(pagbuf, key);
213 	if (i < 0)
214 		goto split;
215 	if (additem(pagbuf, dat) < 0) {
216 		delitem(pagbuf, i);
217 		goto split;
218 	}
219 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
220 	(void) write(pagf, pagbuf, PBLKSIZ);
221 	return (0);
222 
223 split:
224 	if (key.dsize + dat.dsize + 3 * sizeof (short) >= PBLKSIZ) {
225 		(void) printf("entry too big\n");
226 		return (-1);
227 	}
228 	(void) memset(&ovfbuf, 0, PBLKSIZ);
229 	for (i = 0; ; ) {
230 		item = makdatum(pagbuf, i);
231 		if (item.dptr == NULL)
232 			break;
233 		if (calchash(item) & (hmask+1)) {
234 			(void) additem(ovfbuf, item);
235 			delitem(pagbuf, i);
236 			item = makdatum(pagbuf, i);
237 			if (item.dptr == NULL) {
238 				(void) printf("split not paired\n");
239 				break;
240 			}
241 			(void) additem(ovfbuf, item);
242 			delitem(pagbuf, i);
243 			continue;
244 		}
245 		i += 2;
246 	}
247 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
248 	if (write(pagf, pagbuf, PBLKSIZ) < 0) {
249 		return (-1);
250 	}
251 	(void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
252 	if (write(pagf, ovfbuf, PBLKSIZ) < 0) {
253 		return (-1);
254 	}
255 	if (setbit() < 0) {
256 		return (-1);
257 	}
258 	goto loop;
259 }
260 
261 datum
262 firstkey(void)
263 {
264 	return (firsthash(0L));
265 }
266 
267 datum
268 nextkey(datum key)
269 {
270 	int i;
271 	datum item, bitem;
272 	long hash;
273 	int f;
274 
275 #ifdef lint
276 	bitem.dptr = NULL;
277 	bitem.dsize = 0;
278 #endif /* lint */
279 	hash = calchash(key);
280 	dbm_access(hash);
281 	f = 1;
282 	for (i = 0; ; i += 2) {
283 		item = makdatum(pagbuf, i);
284 		if (item.dptr == NULL)
285 			break;
286 		if (cmpdatum(key, item) <= 0)
287 			continue;
288 		if (f || cmpdatum(bitem, item) < 0) {
289 			bitem = item;
290 			f = 0;
291 		}
292 	}
293 	if (f == 0)
294 		return (bitem);
295 	hash = hashinc(hash);
296 	if (hash == 0)
297 		return (item);
298 	return (firsthash(hash));
299 }
300 
301 datum
302 firsthash(long hash)
303 {
304 	int i;
305 	datum item, bitem;
306 
307 loop:
308 	dbm_access(hash);
309 	bitem = makdatum(pagbuf, 0);
310 	for (i = 2; ; i += 2) {
311 		item = makdatum(pagbuf, i);
312 		if (item.dptr == NULL)
313 			break;
314 		if (cmpdatum(bitem, item) < 0)
315 			bitem = item;
316 	}
317 	if (bitem.dptr != NULL)
318 		return (bitem);
319 	hash = hashinc(hash);
320 	if (hash == 0)
321 		return (item);
322 	goto loop;
323 }
324 
325 void
326 dbm_access(long hash)
327 {
328 	ssize_t readsize;
329 
330 	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
331 		blkno = hash & hmask;
332 		bitno = blkno + hmask;
333 		if (getbit() == 0)
334 			break;
335 	}
336 	if (blkno != oldb1) {
337 		(void) lseek(pagf, blkno*PBLKSIZ, 0);
338 		readsize = read(pagf, pagbuf, PBLKSIZ);
339 		if (readsize != PBLKSIZ) {
340 			if (readsize < 0)
341 				readsize = 0;
342 			(void) memset((&pagbuf+readsize), 0, PBLKSIZ-readsize);
343 		}
344 		chkblk(pagbuf);
345 		oldb1 = blkno;
346 	}
347 }
348 
349 int
350 getbit(void)
351 {
352 	long bn;
353 	ssize_t readsize;
354 	long b, i, n;
355 
356 	if (bitno > maxbno)
357 		return (0);
358 	n = bitno % BYTESIZ;
359 	bn = bitno / BYTESIZ;
360 	i = bn % DBLKSIZ;
361 	b = bn / DBLKSIZ;
362 	if (b != oldb2) {
363 		(void) lseek(dirf, (long)b*DBLKSIZ, 0);
364 		readsize = read(dirf, dirbuf, DBLKSIZ);
365 		if (readsize != DBLKSIZ) {
366 			if (readsize < 0)
367 				readsize = 0;
368 			(void) memset(&dirbuf+readsize, 0, DBLKSIZ-readsize);
369 		}
370 		oldb2 = b;
371 	}
372 	if (dirbuf[i] & (1<<n))
373 		return (1);
374 	return (0);
375 }
376 
377 int
378 setbit(void)
379 {
380 	long bn;
381 	long i, n, b;
382 
383 	if (dbrdonly)
384 		return (-1);
385 	if (bitno > maxbno) {
386 		maxbno = bitno;
387 		(void) getbit();
388 	}
389 	n = bitno % BYTESIZ;
390 	bn = bitno / BYTESIZ;
391 	i = bn % DBLKSIZ;
392 	b = bn / DBLKSIZ;
393 	dirbuf[i] |= 1<<n;
394 	(void) lseek(dirf, (long)b*DBLKSIZ, 0);
395 	if (write(dirf, dirbuf, DBLKSIZ) < 0)
396 		return (-1);
397 	return (0);
398 }
399 
400 datum
401 makdatum(char buf[PBLKSIZ], int n)
402 {
403 	short *sp;
404 	int t;
405 	datum item;
406 
407 	/* LINTED pointer cast */
408 	sp = (short *)buf;
409 	if (n < 0 || n >= sp[0])
410 		goto null;
411 	t = PBLKSIZ;
412 	if (n > 0)
413 		t = sp[n+1-1];
414 	item.dptr = buf+sp[n+1];
415 	item.dsize = t - sp[n+1];
416 	return (item);
417 
418 null:
419 	item.dptr = NULL;
420 	item.dsize = 0;
421 	return (item);
422 }
423 
424 int
425 cmpdatum(datum d1, datum d2)
426 {
427 	int n;
428 	char *p1, *p2;
429 
430 	n = d1.dsize;
431 	if (n != d2.dsize)
432 		return (n - d2.dsize);
433 	if (n == 0)
434 		return (0);
435 	p1 = d1.dptr;
436 	p2 = d2.dptr;
437 	do
438 		if (*p1++ != *p2++)
439 			return (*--p1 - *--p2);
440 	while (--n);
441 	return (0);
442 }
443 
444 int	hitab[16]
445 /*
446  * ken's
447  * {
448  *	055, 043, 036, 054, 063, 014, 004, 005,
449  *	010, 064, 077, 000, 035, 027, 025, 071,
450  * };
451  */
452 	= {	61, 57, 53, 49, 45, 41, 37, 33,
453 	29, 25, 21, 17, 13,  9,  5,  1,
454 };
455 long	hltab[64]
456 	= {
457 	06100151277L, 06106161736L, 06452611562L, 05001724107L,
458 	02614772546L, 04120731531L, 04665262210L, 07347467531L,
459 	06735253126L, 06042345173L, 03072226605L, 01464164730L,
460 	03247435524L, 07652510057L, 01546775256L, 05714532133L,
461 	06173260402L, 07517101630L, 02431460343L, 01743245566L,
462 	00261675137L, 02433103631L, 03421772437L, 04447707466L,
463 	04435620103L, 03757017115L, 03641531772L, 06767633246L,
464 	02673230344L, 00260612216L, 04133454451L, 00615531516L,
465 	06137717526L, 02574116560L, 02304023373L, 07061702261L,
466 	05153031405L, 05322056705L, 07401116734L, 06552375715L,
467 	06165233473L, 05311063631L, 01212221723L, 01052267235L,
468 	06000615237L, 01075222665L, 06330216006L, 04402355630L,
469 	01451177262L, 02000133436L, 06025467062L, 07121076461L,
470 	03123433522L, 01010635225L, 01716177066L, 05161746527L,
471 	01736635071L, 06243505026L, 03637211610L, 01756474365L,
472 	04723077174L, 03642763134L, 05750130273L, 03655541561L,
473 };
474 
475 long
476 hashinc(long hash)
477 {
478 	long bit;
479 
480 	hash &= hmask;
481 	bit = hmask+1;
482 	for (; ; ) {
483 		bit >>= 1;
484 		if (bit == 0)
485 			return (0L);
486 		if ((hash&bit) == 0)
487 			return (hash|bit);
488 		hash &= ~bit;
489 	}
490 }
491 
492 long
493 calchash(datum item)
494 {
495 	int i, j, f;
496 	long hashl;
497 	int hashi;
498 
499 	hashl = 0;
500 	hashi = 0;
501 	for (i = 0; i < item.dsize; i++) {
502 		f = item.dptr[i];
503 		for (j = 0; j < BYTESIZ; j += 4) {
504 			hashi += hitab[f&017];
505 			hashl += hltab[hashi&63];
506 			f >>= 4;
507 		}
508 	}
509 	return (hashl);
510 }
511 
512 void
513 delitem(char buf[PBLKSIZ], int n)
514 {
515 	short *sp;
516 	int i1, i2, i3;
517 
518 	/* LINTED pointer cast */
519 	sp = (short *)buf;
520 	if (n < 0 || n >= sp[0])
521 		goto bad;
522 	i1 = sp[n+1];
523 	i2 = PBLKSIZ;
524 	if (n > 0)
525 		i2 = sp[n+1-1];
526 	i3 = sp[sp[0]+1-1];
527 	if (i2 > i1)
528 	while (i1 > i3) {
529 		i1--;
530 		i2--;
531 		buf[i2] = buf[i1];
532 		buf[i1] = 0;
533 	}
534 	i2 -= i1;
535 	for (i1 = n + 1; i1 < sp[0]; i1++)
536 		sp[i1+1-1] = sp[i1+1] + i2;
537 	sp[0]--;
538 	sp[sp[0]+1] = 0;
539 	return;
540 
541 bad:
542 	(void) printf("bad delitem\n");
543 	abort();
544 }
545 
546 int
547 additem(char buf[PBLKSIZ], datum item)
548 {
549 	short *sp;
550 	int i1, i2;
551 
552 	/* LINTED pointer cast */
553 	sp = (short *)buf;
554 	i1 = PBLKSIZ;
555 	if (sp[0] > 0)
556 		i1 = sp[sp[0]+1-1];
557 	i1 -= item.dsize;
558 	i2 = (sp[0]+2) * (int)sizeof (short);
559 	if (i1 <= i2)
560 		return (-1);
561 	sp[sp[0]+1] = (short)i1;
562 	for (i2 = 0; i2 < item.dsize; i2++) {
563 		buf[i1] = item.dptr[i2];
564 		i1++;
565 	}
566 	sp[0]++;
567 	return (sp[0]-1);
568 }
569 
570 void
571 chkblk(char buf[PBLKSIZ])
572 {
573 	short *sp;
574 	int t, i;
575 
576 	/* LINTED pointer cast */
577 	sp = (short *)buf;
578 	t = PBLKSIZ;
579 	for (i = 0; i < sp[0]; i++) {
580 		if (sp[i+1] > t)
581 			goto bad;
582 		t = sp[i+1];
583 	}
584 	if (t < (sp[0]+1) * sizeof (short))
585 		goto bad;
586 	return;
587 
588 bad:
589 	(void) printf("bad block\n");
590 	abort();
591 	(void) memset(&buf, 0, PBLKSIZ);
592 }
593