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