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