1/* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements.  See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License.  You may obtain a copy of the License at
7 *
8 *     http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/*
18 * sdbm - ndbm work-alike hashed database library
19 * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
20 * author: oz@nexus.yorku.ca
21 * ex-public domain, ported to APR for Apache 2
22 * core routines
23 */
24
25#include "apr.h"
26#include "apr_file_io.h"
27#include "apr_strings.h"
28#include "apr_errno.h"
29#include "apr_sdbm.h"
30
31#include "sdbm_tune.h"
32#include "sdbm_pair.h"
33#include "sdbm_private.h"
34
35#include <string.h>     /* for memset() */
36#include <stdlib.h>     /* for malloc() and free() */
37
38/*
39 * forward
40 */
41static int getdbit (apr_sdbm_t *, long);
42static apr_status_t setdbit(apr_sdbm_t *, long);
43static apr_status_t getpage(apr_sdbm_t *db, long, int, int);
44static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db);
45static apr_status_t makroom(apr_sdbm_t *, long, int);
46
47/*
48 * useful macros
49 */
50#define bad(x)		((x).dptr == NULL || (x).dsize <= 0)
51#define exhash(item)	sdbm_hash((item).dptr, (item).dsize)
52
53#define OFF_PAG(off)	(apr_off_t) (off) * PBLKSIZ
54#define OFF_DIR(off)	(apr_off_t) (off) * DBLKSIZ
55
56static const long masks[] = {
57        000000000000, 000000000001, 000000000003, 000000000007,
58        000000000017, 000000000037, 000000000077, 000000000177,
59        000000000377, 000000000777, 000000001777, 000000003777,
60        000000007777, 000000017777, 000000037777, 000000077777,
61        000000177777, 000000377777, 000000777777, 000001777777,
62        000003777777, 000007777777, 000017777777, 000037777777,
63        000077777777, 000177777777, 000377777777, 000777777777,
64        001777777777, 003777777777, 007777777777, 017777777777
65};
66
67const apr_sdbm_datum_t sdbm_nullitem = { NULL, 0 };
68
69static apr_status_t database_cleanup(void *data)
70{
71    apr_sdbm_t *db = data;
72
73    /*
74     * Can't rely on apr_sdbm_unlock, since it will merely
75     * decrement the refcnt if several locks are held.
76     */
77    if (db->flags & (SDBM_SHARED_LOCK | SDBM_EXCLUSIVE_LOCK))
78        (void) apr_file_unlock(db->dirf);
79    (void) apr_file_close(db->dirf);
80    (void) apr_file_close(db->pagf);
81    free(db);
82
83    return APR_SUCCESS;
84}
85
86static apr_status_t prep(apr_sdbm_t **pdb, const char *dirname, const char *pagname,
87                         apr_int32_t flags, apr_fileperms_t perms, apr_pool_t *p)
88{
89    apr_sdbm_t *db;
90    apr_status_t status;
91
92    *pdb = NULL;
93
94    db = malloc(sizeof(*db));
95    memset(db, 0, sizeof(*db));
96    db->pagbno = -1L;
97
98    db->pool = p;
99
100    /*
101     * adjust user flags so that WRONLY becomes RDWR,
102     * as required by this package. Also set our internal
103     * flag for RDONLY if needed.
104     */
105    if (!(flags & APR_FOPEN_WRITE)) {
106        db->flags |= SDBM_RDONLY;
107    }
108
109    /*
110     * adjust the file open flags so that we handle locking
111     * on our own (don't rely on any locking behavior within
112     * an apr_file_t, in case it's ever introduced, and set
113     * our own flag.
114     */
115    if (flags & APR_FOPEN_SHARELOCK) {
116        db->flags |= SDBM_SHARED;
117        flags &= ~APR_FOPEN_SHARELOCK;
118    }
119
120    flags |= APR_FOPEN_BINARY | APR_FOPEN_READ;
121
122    /*
123     * open the files in sequence, and stat the dirfile.
124     * If we fail anywhere, undo everything, return NULL.
125     */
126
127    if ((status = apr_file_open(&db->dirf, dirname, flags, perms, p))
128                != APR_SUCCESS)
129        goto error;
130
131    if ((status = apr_file_open(&db->pagf, pagname, flags, perms, p))
132                != APR_SUCCESS)
133        goto error;
134
135    if ((status = apr_sdbm_lock(db, (db->flags & SDBM_RDONLY)
136                                        ? APR_FLOCK_SHARED
137                                        : APR_FLOCK_EXCLUSIVE))
138                != APR_SUCCESS)
139        goto error;
140
141    /* apr_pcalloc zeroed the buffers
142     * apr_sdbm_lock stated the dirf->size and invalidated the cache
143     */
144
145    /*
146     * if we are opened in SHARED mode, unlock ourself
147     */
148    if (db->flags & SDBM_SHARED)
149        if ((status = apr_sdbm_unlock(db)) != APR_SUCCESS)
150            goto error;
151
152    /* make sure that we close the database at some point */
153    apr_pool_cleanup_register(p, db, database_cleanup, apr_pool_cleanup_null);
154
155    /* Done! */
156    *pdb = db;
157    return APR_SUCCESS;
158
159error:
160    if (db->dirf && db->pagf)
161        (void) apr_sdbm_unlock(db);
162    if (db->dirf != NULL)
163        (void) apr_file_close(db->dirf);
164    if (db->pagf != NULL) {
165        (void) apr_file_close(db->pagf);
166    }
167    free(db);
168    return status;
169}
170
171APU_DECLARE(apr_status_t) apr_sdbm_open(apr_sdbm_t **db, const char *file,
172                                        apr_int32_t flags,
173                                        apr_fileperms_t perms, apr_pool_t *p)
174{
175    char *dirname = apr_pstrcat(p, file, APR_SDBM_DIRFEXT, NULL);
176    char *pagname = apr_pstrcat(p, file, APR_SDBM_PAGFEXT, NULL);
177
178    return prep(db, dirname, pagname, flags, perms, p);
179}
180
181APU_DECLARE(apr_status_t) apr_sdbm_close(apr_sdbm_t *db)
182{
183    return apr_pool_cleanup_run(db->pool, db, database_cleanup);
184}
185
186APU_DECLARE(apr_status_t) apr_sdbm_fetch(apr_sdbm_t *db, apr_sdbm_datum_t *val,
187                                         apr_sdbm_datum_t key)
188{
189    apr_status_t status;
190
191    if (db == NULL || bad(key))
192        return APR_EINVAL;
193
194    if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
195        return status;
196
197    if ((status = getpage(db, exhash(key), 0, 1)) == APR_SUCCESS) {
198        *val = getpair(db->pagbuf, key);
199        /* ### do we want a not-found result? */
200    }
201
202    (void) apr_sdbm_unlock(db);
203
204    return status;
205}
206
207static apr_status_t write_page(apr_sdbm_t *db, const char *buf, long pagno)
208{
209    apr_status_t status;
210    apr_off_t off = OFF_PAG(pagno);
211
212    if ((status = apr_file_seek(db->pagf, APR_SET, &off)) == APR_SUCCESS)
213        status = apr_file_write_full(db->pagf, buf, PBLKSIZ, NULL);
214
215    return status;
216}
217
218APU_DECLARE(apr_status_t) apr_sdbm_delete(apr_sdbm_t *db,
219                                          const apr_sdbm_datum_t key)
220{
221    apr_status_t status;
222
223    if (db == NULL || bad(key))
224        return APR_EINVAL;
225    if (apr_sdbm_rdonly(db))
226        return APR_EINVAL;
227
228    if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS)
229        return status;
230
231    if ((status = getpage(db, exhash(key), 0, 1)) == APR_SUCCESS) {
232        if (!delpair(db->pagbuf, key))
233            /* ### should we define some APRUTIL codes? */
234            status = APR_EGENERAL;
235        else
236            status = write_page(db, db->pagbuf, db->pagbno);
237    }
238
239    (void) apr_sdbm_unlock(db);
240
241    return status;
242}
243
244APU_DECLARE(apr_status_t) apr_sdbm_store(apr_sdbm_t *db, apr_sdbm_datum_t key,
245                                         apr_sdbm_datum_t val, int flags)
246{
247    int need;
248    register long hash;
249    apr_status_t status;
250
251    if (db == NULL || bad(key))
252        return APR_EINVAL;
253    if (apr_sdbm_rdonly(db))
254        return APR_EINVAL;
255    need = key.dsize + val.dsize;
256    /*
257     * is the pair too big (or too small) for this database ??
258     */
259    if (need < 0 || need > PAIRMAX)
260        return APR_EINVAL;
261
262    if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS)
263        return status;
264
265    if ((status = getpage(db, (hash = exhash(key)), 0, 1)) == APR_SUCCESS) {
266
267        /*
268         * if we need to replace, delete the key/data pair
269         * first. If it is not there, ignore.
270         */
271        if (flags == APR_SDBM_REPLACE)
272            (void) delpair(db->pagbuf, key);
273        else if (!(flags & APR_SDBM_INSERTDUP) && duppair(db->pagbuf, key)) {
274            status = APR_EEXIST;
275            goto error;
276        }
277        /*
278         * if we do not have enough room, we have to split.
279         */
280        if (!fitpair(db->pagbuf, need))
281            if ((status = makroom(db, hash, need)) != APR_SUCCESS)
282                goto error;
283        /*
284         * we have enough room or split is successful. insert the key,
285         * and update the page file.
286         */
287        (void) putpair(db->pagbuf, key, val);
288
289        status = write_page(db, db->pagbuf, db->pagbno);
290    }
291
292error:
293    (void) apr_sdbm_unlock(db);
294
295    return status;
296}
297
298/*
299 * makroom - make room by splitting the overfull page
300 * this routine will attempt to make room for SPLTMAX times before
301 * giving up.
302 */
303static apr_status_t makroom(apr_sdbm_t *db, long hash, int need)
304{
305    long newp;
306    char twin[PBLKSIZ];
307    char *pag = db->pagbuf;
308    char *new = twin;
309    register int smax = SPLTMAX;
310    apr_status_t status;
311
312    do {
313        /*
314         * split the current page
315         */
316        (void) splpage(pag, new, db->hmask + 1);
317        /*
318         * address of the new page
319         */
320        newp = (hash & db->hmask) | (db->hmask + 1);
321
322        /*
323         * write delay, read avoidence/cache shuffle:
324         * select the page for incoming pair: if key is to go to the new page,
325         * write out the previous one, and copy the new one over, thus making
326         * it the current page. If not, simply write the new page, and we are
327         * still looking at the page of interest. current page is not updated
328         * here, as sdbm_store will do so, after it inserts the incoming pair.
329         */
330        if (hash & (db->hmask + 1)) {
331            if ((status = write_page(db, db->pagbuf, db->pagbno))
332                        != APR_SUCCESS)
333                return status;
334
335            db->pagbno = newp;
336            (void) memcpy(pag, new, PBLKSIZ);
337        }
338        else {
339            if ((status = write_page(db, new, newp)) != APR_SUCCESS)
340                return status;
341        }
342
343        if ((status = setdbit(db, db->curbit)) != APR_SUCCESS)
344            return status;
345        /*
346         * see if we have enough room now
347         */
348        if (fitpair(pag, need))
349            return APR_SUCCESS;
350        /*
351         * try again... update curbit and hmask as getpage would have
352         * done. because of our update of the current page, we do not
353         * need to read in anything. BUT we have to write the current
354         * [deferred] page out, as the window of failure is too great.
355         */
356        db->curbit = 2 * db->curbit
357                   + ((hash & (db->hmask + 1)) ? 2 : 1);
358        db->hmask |= db->hmask + 1;
359
360        if ((status = write_page(db, db->pagbuf, db->pagbno))
361                    != APR_SUCCESS)
362            return status;
363
364    } while (--smax);
365
366    /*
367     * if we are here, this is real bad news. After SPLTMAX splits,
368     * we still cannot fit the key. say goodnight.
369     */
370#if 0
371    (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
372#endif
373    /* ### ENOSPC not really appropriate but better than nothing */
374    return APR_ENOSPC;
375
376}
377
378/* Reads 'len' bytes from file 'f' at offset 'off' into buf.
379 * 'off' is given relative to the start of the file.
380 * If 'create' is asked and EOF is returned while reading, this is taken
381 * as success (i.e. a cleared buffer is returned).
382 */
383static apr_status_t read_from(apr_file_t *f, void *buf,
384                              apr_off_t off, apr_size_t len,
385                              int create)
386{
387    apr_status_t status;
388
389    if ((status = apr_file_seek(f, APR_SET, &off)) != APR_SUCCESS ||
390        ((status = apr_file_read_full(f, buf, len, NULL)) != APR_SUCCESS)) {
391        /* if EOF is reached, pretend we read all zero's */
392        if (status == APR_EOF && create) {
393            memset(buf, 0, len);
394            status = APR_SUCCESS;
395        }
396    }
397
398    return status;
399}
400
401/*
402 * the following two routines will break if
403 * deletions aren't taken into account. (ndbm bug)
404 */
405APU_DECLARE(apr_status_t) apr_sdbm_firstkey(apr_sdbm_t *db,
406                                            apr_sdbm_datum_t *key)
407{
408    apr_status_t status;
409
410    if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
411        return status;
412
413    /*
414     * start at page 0
415     */
416    if ((status = getpage(db, 0, 1, 1)) == APR_SUCCESS) {
417        db->blkptr = 0;
418        db->keyptr = 0;
419        status = getnext(key, db);
420    }
421
422    (void) apr_sdbm_unlock(db);
423
424    return status;
425}
426
427APU_DECLARE(apr_status_t) apr_sdbm_nextkey(apr_sdbm_t *db,
428                                           apr_sdbm_datum_t *key)
429{
430    apr_status_t status;
431
432    if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
433        return status;
434
435    status = getnext(key, db);
436
437    (void) apr_sdbm_unlock(db);
438
439    return status;
440}
441
442/*
443 * all important binary tree traversal
444 */
445static apr_status_t getpage(apr_sdbm_t *db, long hash, int by_num, int create)
446{
447    apr_status_t status;
448    register long pagb;
449
450    if (by_num) {
451        pagb = hash;
452    }
453    else {
454        register int hbit = 0;
455        register long dbit = 0;
456
457        while (dbit < db->maxbno && getdbit(db, dbit))
458            dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
459        debug(("dbit: %d...", dbit));
460
461        db->curbit = dbit;
462        db->hmask = masks[hbit];
463
464        pagb = hash & db->hmask;
465    }
466
467    /*
468     * see if the block we need is already in memory.
469     * note: this lookaside cache has about 10% hit rate.
470     */
471    if (pagb != db->pagbno) {
472        /*
473         * note: here, we assume a "hole" is read as 0s.
474         * if not, must zero pagbuf first.
475         * ### joe: this assumption was surely never correct? but
476         * ### we make it so in read_from anyway.
477         */
478        if ((status = read_from(db->pagf, db->pagbuf,
479                                OFF_PAG(pagb), PBLKSIZ,
480                                create)) != APR_SUCCESS)
481            return status;
482
483        if (!chkpage(db->pagbuf))
484            return APR_ENOSPC; /* ### better error? */
485
486        db->pagbno = pagb;
487
488        debug(("pag read: %d\n", pagb));
489    }
490    return APR_SUCCESS;
491}
492
493static int getdbit(apr_sdbm_t *db, long dbit)
494{
495    register long c;
496    register long dirb;
497
498    c = dbit / BYTESIZ;
499    dirb = c / DBLKSIZ;
500
501    if (dirb != db->dirbno) {
502        if (read_from(db->dirf, db->dirbuf,
503                      OFF_DIR(dirb), DBLKSIZ,
504                      1) != APR_SUCCESS)
505            return 0;
506
507        db->dirbno = dirb;
508
509        debug(("dir read: %d\n", dirb));
510    }
511
512    return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
513}
514
515static apr_status_t setdbit(apr_sdbm_t *db, long dbit)
516{
517    register long c;
518    register long dirb;
519    apr_status_t status;
520    apr_off_t off;
521
522    c = dbit / BYTESIZ;
523    dirb = c / DBLKSIZ;
524
525    if (dirb != db->dirbno) {
526        if ((status = read_from(db->dirf, db->dirbuf,
527                                OFF_DIR(dirb), DBLKSIZ,
528                                1)) != APR_SUCCESS)
529            return status;
530
531        db->dirbno = dirb;
532
533        debug(("dir read: %d\n", dirb));
534    }
535
536    db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
537
538    if (dbit >= db->maxbno)
539        db->maxbno += DBLKSIZ * BYTESIZ;
540
541    off = OFF_DIR(dirb);
542    if ((status = apr_file_seek(db->dirf, APR_SET, &off)) == APR_SUCCESS)
543        status = apr_file_write_full(db->dirf, db->dirbuf, DBLKSIZ, NULL);
544
545    return status;
546}
547
548/*
549* getnext - get the next key in the page, and if done with
550* the page, try the next page in sequence
551*/
552static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db)
553{
554    apr_status_t status;
555    for (;;) {
556        db->keyptr++;
557        *key = getnkey(db->pagbuf, db->keyptr);
558        if (key->dptr != NULL)
559            return APR_SUCCESS;
560        /*
561         * we either run out, or there is nothing on this page..
562         * try the next one... If we lost our position on the
563         * file, we will have to seek.
564         */
565        db->blkptr++;
566        db->keyptr = 0;
567
568        /* ### EOF acceptable here too? */
569        if ((status = getpage(db, db->blkptr, 1, 0)) != APR_SUCCESS)
570            return status;
571    }
572
573    /* NOTREACHED */
574}
575
576
577APU_DECLARE(int) apr_sdbm_rdonly(apr_sdbm_t *db)
578{
579    /* ### Should we return true if the first lock is a share lock,
580     *     to reflect that apr_sdbm_store and apr_sdbm_delete will fail?
581     */
582    return (db->flags & SDBM_RDONLY) != 0;
583}
584
585