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