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