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 2019 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 ;
447 return (0);
448 }
449
450 int hitab[16]
451 /*
452 * ken's
453 * {
454 * 055,043,036,054,063,014,004,005,
455 * 010,064,077,000,035,027,025,071,
456 * };
457 */
458 = { 61, 57, 53, 49, 45, 41, 37, 33,
459 29, 25, 21, 17, 13, 9, 5, 1,
460 };
461 long hltab[64] = {
462 06100151277L, 06106161736L, 06452611562L, 05001724107L,
463 02614772546L, 04120731531L, 04665262210L, 07347467531L,
464 06735253126L, 06042345173L, 03072226605L, 01464164730L,
465 03247435524L, 07652510057L, 01546775256L, 05714532133L,
466 06173260402L, 07517101630L, 02431460343L, 01743245566L,
467 00261675137L, 02433103631L, 03421772437L, 04447707466L,
468 04435620103L, 03757017115L, 03641531772L, 06767633246L,
469 02673230344L, 00260612216L, 04133454451L, 00615531516L,
470 06137717526L, 02574116560L, 02304023373L, 07061702261L,
471 05153031405L, 05322056705L, 07401116734L, 06552375715L,
472 06165233473L, 05311063631L, 01212221723L, 01052267235L,
473 06000615237L, 01075222665L, 06330216006L, 04402355630L,
474 01451177262L, 02000133436L, 06025467062L, 07121076461L,
475 03123433522L, 01010635225L, 01716177066L, 05161746527L,
476 01736635071L, 06243505026L, 03637211610L, 01756474365L,
477 04723077174L, 03642763134L, 05750130273L, 03655541561L,
478 };
479
480 long
481 hashinc(long hash)
482 {
483 long bit;
484
485 hash &= hmask;
486 bit = hmask+1;
487 for (;;) {
488 bit >>= 1;
489 if (bit == 0)
490 return (0L);
491 if ((hash&bit) == 0)
492 return (hash|bit);
493 hash &= ~bit;
494 }
495 }
496
497 long
498 calchash(datum item)
499 {
500 int i, j, f;
501 long hashl;
502 int hashi;
503
504 hashl = 0;
505 hashi = 0;
506 for (i = 0; i < item.dsize; i++) {
507 f = item.dptr[i];
508 for (j = 0; j < BYTESIZ; j += 4) {
509 hashi += hitab[f&017];
510 hashl += hltab[hashi&63];
511 f >>= 4;
512 }
513 }
514 return (hashl);
515 }
516
517 void
518 delitem(char buf[PBLKSIZ], int n)
519 {
520 short *sp;
521 int i1, i2, i3;
522
523 sp = (short *)buf;
524 if (n < 0 || n >= sp[0])
525 goto bad;
526 i1 = sp[n+1];
527 i2 = PBLKSIZ;
528 if (n > 0)
529 i2 = sp[n+1-1];
530 i3 = sp[sp[0]+1-1];
531 if (i2 > i1)
532 while (i1 > i3) {
533 i1--;
534 i2--;
535 buf[i2] = buf[i1];
536 buf[i1] = 0;
537 }
538 i2 -= i1;
539 for (i1 = n+1; i1 < sp[0]; i1++)
540 sp[i1+1-1] = sp[i1+1] + i2;
541 sp[0]--;
542 sp[sp[0]+1] = 0;
543 return;
544
545 bad:
546 (void) printf("bad delitem\n");
547 abort();
548 }
549
550 int
551 additem(char buf[PBLKSIZ], datum item)
552 {
553 short *sp;
554 int i1, i2;
555
556 sp = (short *)buf;
557 i1 = PBLKSIZ;
558 if (sp[0] > 0)
559 i1 = sp[sp[0]+1-1];
560 i1 -= item.dsize;
561 i2 = (int)((sp[0]+2) * sizeof (short));
562 if (i1 <= i2)
563 return (-1);
564 sp[sp[0]+1] = (short)i1;
565 for (i2 = 0; i2 < item.dsize; i2++) {
566 buf[i1] = item.dptr[i2];
567 i1++;
568 }
569 sp[0]++;
570 return (sp[0]-1);
571 }
572
573 void
574 chkblk(char buf[PBLKSIZ])
575 {
576 short *sp;
577 int t, i;
578
579 sp = (short *)buf;
580 t = PBLKSIZ;
581 for (i = 0; i < sp[0]; i++) {
582 if (sp[i+1] > t)
583 goto bad;
584 t = sp[i+1];
585 }
586 if (t < (sp[0]+1)*sizeof (short))
587 goto bad;
588 return;
589
590 bad:
591 (void) printf("bad block\n");
592 abort();
593 }