contrib/apr-util/dbm/sdbm/sdbm.c

   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  */
  41 static int getdbit (apr_sdbm_t *, long);
  42 static apr_status_t setdbit(apr_sdbm_t *, long);
  43 static apr_status_t getpage(apr_sdbm_t *db, long);
  44 static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db);
  45 static 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
  56 static 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
  67 const apr_sdbm_datum_t sdbm_nullitem = { NULL, 0 };
  68
  69 static 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
  86 static 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
  97     db->pool = p;
  98
  99     /*
 100      * adjust user flags so that WRONLY becomes RDWR,
 101      * as required by this package. Also set our internal
 102      * flag for RDONLY if needed.
 103      */
 104     if (!(flags & APR_FOPEN_WRITE)) {
 105         db->flags |= SDBM_RDONLY;
 106     }
 107
 108     /*
 109      * adjust the file open flags so that we handle locking
 110      * on our own (don't rely on any locking behavior within
 111      * an apr_file_t, in case it's ever introduced, and set
 112      * our own flag.
 113      */
 114     if (flags & APR_FOPEN_SHARELOCK) {
 115         db->flags |= SDBM_SHARED;
 116         flags &= ~APR_FOPEN_SHARELOCK;
 117     }
 118
 119     flags |= APR_FOPEN_BINARY | APR_FOPEN_READ;
 120
 121     /*
 122      * open the files in sequence, and stat the dirfile.
 123      * If we fail anywhere, undo everything, return NULL.
 124      */
 125
 126     if ((status = apr_file_open(&db->dirf, dirname, flags, perms, p))
 127                 != APR_SUCCESS)
 128         goto error;
 129
 130     if ((status = apr_file_open(&db->pagf, pagname, flags, perms, p))
 131                 != APR_SUCCESS)
 132         goto error;
 133
 134     if ((status = apr_sdbm_lock(db, (db->flags & SDBM_RDONLY)
 135                                         ? APR_FLOCK_SHARED
 136                                         : APR_FLOCK_EXCLUSIVE))
 137                 != APR_SUCCESS)
 138         goto error;
 139
 140     /* apr_pcalloc zeroed the buffers
 141      * apr_sdbm_lock stated the dirf->size and invalidated the cache
 142      */
 143
 144     /*
 145      * if we are opened in SHARED mode, unlock ourself
 146      */
 147     if (db->flags & SDBM_SHARED)
 148         if ((status = apr_sdbm_unlock(db)) != APR_SUCCESS)
 149             goto error;
 150
 151     /* make sure that we close the database at some point */
 152     apr_pool_cleanup_register(p, db, database_cleanup, apr_pool_cleanup_null);
 153
 154     /* Done! */
 155     *pdb = db;
 156     return APR_SUCCESS;
 157
 158 error:
 159     if (db->dirf && db->pagf)
 160         (void) apr_sdbm_unlock(db);
 161     if (db->dirf != NULL)
 162         (void) apr_file_close(db->dirf);
 163     if (db->pagf != NULL) {
 164         (void) apr_file_close(db->pagf);
 165     }
 166     free(db);
 167     return status;
 168 }
 169
 170 APU_DECLARE(apr_status_t) apr_sdbm_open(apr_sdbm_t **db, const char *file,
 171                                         apr_int32_t flags,
 172                                         apr_fileperms_t perms, apr_pool_t *p)
 173 {
 174     char *dirname = apr_pstrcat(p, file, APR_SDBM_DIRFEXT, NULL);
 175     char *pagname = apr_pstrcat(p, file, APR_SDBM_PAGFEXT, NULL);
 176
 177     return prep(db, dirname, pagname, flags, perms, p);
 178 }
 179
 180 APU_DECLARE(apr_status_t) apr_sdbm_close(apr_sdbm_t *db)
 181 {
 182     return apr_pool_cleanup_run(db->pool, db, database_cleanup);
 183 }
 184
 185 APU_DECLARE(apr_status_t) apr_sdbm_fetch(apr_sdbm_t *db, apr_sdbm_datum_t *val,
 186                                          apr_sdbm_datum_t key)
 187 {
 188     apr_status_t status;
 189
 190     if (db == NULL || bad(key))
 191         return APR_EINVAL;
 192
 193     if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
 194         return status;
 195
 196     if ((status = getpage(db, exhash(key))) == APR_SUCCESS) {
 197         *val = getpair(db->pagbuf, key);
 198         /* ### do we want a not-found result? */
 199     }
 200
 201     (void) apr_sdbm_unlock(db);
 202
 203     return status;
 204 }
 205
 206 static apr_status_t write_page(apr_sdbm_t *db, const char *buf, long pagno)
 207 {
 208     apr_status_t status;
 209     apr_off_t off = OFF_PAG(pagno);
 210
 211     if ((status = apr_file_seek(db->pagf, APR_SET, &off)) == APR_SUCCESS)
 212         status = apr_file_write_full(db->pagf, buf, PBLKSIZ, NULL);
 213
 214     return status;
 215 }
 216
 217 APU_DECLARE(apr_status_t) apr_sdbm_delete(apr_sdbm_t *db,
 218                                           const apr_sdbm_datum_t key)
 219 {
 220     apr_status_t status;
 221
 222     if (db == NULL || bad(key))
 223         return APR_EINVAL;
 224     if (apr_sdbm_rdonly(db))
 225         return APR_EINVAL;
 226
 227     if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS)
 228         return status;
 229
 230     if ((status = getpage(db, exhash(key))) == APR_SUCCESS) {
 231         if (!delpair(db->pagbuf, key))
 232             /* ### should we define some APRUTIL codes? */
 233             status = APR_EGENERAL;
 234         else
 235             status = write_page(db, db->pagbuf, db->pagbno);
 236     }
 237
 238     (void) apr_sdbm_unlock(db);
 239
 240     return status;
 241 }
 242
 243 APU_DECLARE(apr_status_t) apr_sdbm_store(apr_sdbm_t *db, apr_sdbm_datum_t key,
 244                                          apr_sdbm_datum_t val, int flags)
 245 {
 246     int need;
 247     register long hash;
 248     apr_status_t status;
 249
 250     if (db == NULL || bad(key))
 251         return APR_EINVAL;
 252     if (apr_sdbm_rdonly(db))
 253         return APR_EINVAL;
 254     need = key.dsize + val.dsize;
 255     /*
 256      * is the pair too big (or too small) for this database ??
 257      */
 258     if (need < 0 || need > PAIRMAX)
 259         return APR_EINVAL;
 260
 261     if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS)
 262         return status;
 263
 264     if ((status = getpage(db, (hash = exhash(key)))) == APR_SUCCESS) {
 265
 266         /*
 267          * if we need to replace, delete the key/data pair
 268          * first. If it is not there, ignore.
 269          */
 270         if (flags == APR_SDBM_REPLACE)
 271             (void) delpair(db->pagbuf, key);
 272         else if (!(flags & APR_SDBM_INSERTDUP) && duppair(db->pagbuf, key)) {
 273             status = APR_EEXIST;
 274             goto error;
 275         }
 276         /*
 277          * if we do not have enough room, we have to split.
 278          */
 279         if (!fitpair(db->pagbuf, need))
 280             if ((status = makroom(db, hash, need)) != APR_SUCCESS)
 281                 goto error;
 282         /*
 283          * we have enough room or split is successful. insert the key,
 284          * and update the page file.
 285          */
 286         (void) putpair(db->pagbuf, key, val);
 287
 288         status = write_page(db, db->pagbuf, db->pagbno);
 289     }
 290
 291 error:
 292     (void) apr_sdbm_unlock(db);
 293
 294     return status;
 295 }
 296
 297 /*
 298  * makroom - make room by splitting the overfull page
 299  * this routine will attempt to make room for SPLTMAX times before
 300  * giving up.
 301  */
 302 static apr_status_t makroom(apr_sdbm_t *db, long hash, int need)
 303 {
 304     long newp;
 305     char twin[PBLKSIZ];
 306     char *pag = db->pagbuf;
 307     char *new = twin;
 308     register int smax = SPLTMAX;
 309     apr_status_t status;
 310
 311     do {
 312         /*
 313          * split the current page
 314          */
 315         (void) splpage(pag, new, db->hmask + 1);
 316         /*
 317          * address of the new page
 318          */
 319         newp = (hash & db->hmask) | (db->hmask + 1);
 320
 321         /*
 322          * write delay, read avoidence/cache shuffle:
 323          * select the page for incoming pair: if key is to go to the new page,
 324          * write out the previous one, and copy the new one over, thus making
 325          * it the current page. If not, simply write the new page, and we are
 326          * still looking at the page of interest. current page is not updated
 327          * here, as sdbm_store will do so, after it inserts the incoming pair.
 328          */
 329         if (hash & (db->hmask + 1)) {
 330             if ((status = write_page(db, db->pagbuf, db->pagbno))
 331                         != APR_SUCCESS)
 332                 return status;
 333
 334             db->pagbno = newp;
 335             (void) memcpy(pag, new, PBLKSIZ);
 336         }
 337         else {
 338             if ((status = write_page(db, new, newp)) != APR_SUCCESS)
 339                 return status;
 340         }
 341
 342         if ((status = setdbit(db, db->curbit)) != APR_SUCCESS)
 343             return status;
 344         /*
 345          * see if we have enough room now
 346          */
 347         if (fitpair(pag, need))
 348             return APR_SUCCESS;
 349         /*
 350          * try again... update curbit and hmask as getpage would have
 351          * done. because of our update of the current page, we do not
 352          * need to read in anything. BUT we have to write the current
 353          * [deferred] page out, as the window of failure is too great.
 354          */
 355         db->curbit = 2 * db->curbit
 356                    + ((hash & (db->hmask + 1)) ? 2 : 1);
 357         db->hmask |= db->hmask + 1;
 358
 359         if ((status = write_page(db, db->pagbuf, db->pagbno))
 360                     != APR_SUCCESS)
 361             return status;
 362
 363     } while (--smax);
 364
 365     /*
 366      * if we are here, this is real bad news. After SPLTMAX splits,
 367      * we still cannot fit the key. say goodnight.
 368      */
 369 #if 0
 370     (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
 371 #endif
 372     /* ### ENOSPC not really appropriate but better than nothing */
 373     return APR_ENOSPC;
 374
 375 }
 376
 377 /* Reads 'len' bytes from file 'f' at offset 'off' into buf.
 378  * 'off' is given relative to the start of the file.
 379  * If EOF is returned while reading, this is taken as success.
 380  */
 381 static apr_status_t read_from(apr_file_t *f, void *buf,
 382              apr_off_t off, apr_size_t len)
 383 {
 384     apr_status_t status;
 385
 386     if ((status = apr_file_seek(f, APR_SET, &off)) != APR_SUCCESS ||
 387         ((status = apr_file_read_full(f, buf, len, NULL)) != APR_SUCCESS)) {
 388         /* if EOF is reached, pretend we read all zero's */
 389         if (status == APR_EOF) {
 390             memset(buf, 0, len);
 391             status = APR_SUCCESS;
 392         }
 393     }
 394
 395     return status;
 396 }
 397
 398 /*
 399  * the following two routines will break if
 400  * deletions aren't taken into account. (ndbm bug)
 401  */
 402 APU_DECLARE(apr_status_t) apr_sdbm_firstkey(apr_sdbm_t *db,
 403                                             apr_sdbm_datum_t *key)
 404 {
 405     apr_status_t status;
 406
 407     if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
 408         return status;
 409
 410     /*
 411      * start at page 0
 412      */
 413     if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(0), PBLKSIZ))
 414                 == APR_SUCCESS) {
 415         db->pagbno = 0;
 416         db->blkptr = 0;
 417         db->keyptr = 0;
 418         status = getnext(key, db);
 419     }
 420
 421     (void) apr_sdbm_unlock(db);
 422
 423     return status;
 424 }
 425
 426 APU_DECLARE(apr_status_t) apr_sdbm_nextkey(apr_sdbm_t *db,
 427                                            apr_sdbm_datum_t *key)
 428 {
 429     apr_status_t status;
 430
 431     if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
 432         return status;
 433
 434     status = getnext(key, db);
 435
 436     (void) apr_sdbm_unlock(db);
 437
 438     return status;
 439 }
 440
 441 /*
 442  * all important binary tree traversal
 443  */
 444 static apr_status_t getpage(apr_sdbm_t *db, long hash)
 445 {
 446     register int hbit;
 447     register long dbit;
 448     register long pagb;
 449     apr_status_t status;
 450
 451     dbit = 0;
 452     hbit = 0;
 453     while (dbit < db->maxbno && getdbit(db, dbit))
 454     dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
 455
 456     debug(("dbit: %d...", dbit));
 457
 458     db->curbit = dbit;
 459     db->hmask = masks[hbit];
 460
 461     pagb = hash & db->hmask;
 462     /*
 463      * see if the block we need is already in memory.
 464      * note: this lookaside cache has about 10% hit rate.
 465      */
 466     if (pagb != db->pagbno) {
 467         /*
 468          * note: here, we assume a "hole" is read as 0s.
 469          * if not, must zero pagbuf first.
 470          * ### joe: this assumption was surely never correct? but
 471          * ### we make it so in read_from anyway.
 472          */
 473         if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(pagb), PBLKSIZ))
 474                     != APR_SUCCESS)
 475             return status;
 476
 477         if (!chkpage(db->pagbuf))
 478             return APR_ENOSPC; /* ### better error? */
 479         db->pagbno = pagb;
 480
 481         debug(("pag read: %d\n", pagb));
 482     }
 483     return APR_SUCCESS;
 484 }
 485
 486 static int getdbit(apr_sdbm_t *db, long dbit)
 487 {
 488     register long c;
 489     register long dirb;
 490
 491     c = dbit / BYTESIZ;
 492     dirb = c / DBLKSIZ;
 493
 494     if (dirb != db->dirbno) {
 495         if (read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ)
 496                     != APR_SUCCESS)
 497             return 0;
 498
 499         db->dirbno = dirb;
 500
 501         debug(("dir read: %d\n", dirb));
 502     }
 503
 504     return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
 505 }
 506
 507 static apr_status_t setdbit(apr_sdbm_t *db, long dbit)
 508 {
 509     register long c;
 510     register long dirb;
 511     apr_status_t status;
 512     apr_off_t off;
 513
 514     c = dbit / BYTESIZ;
 515     dirb = c / DBLKSIZ;
 516
 517     if (dirb != db->dirbno) {
 518         if ((status = read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ))
 519                     != APR_SUCCESS)
 520             return status;
 521
 522         db->dirbno = dirb;
 523
 524         debug(("dir read: %d\n", dirb));
 525     }
 526
 527     db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
 528
 529     if (dbit >= db->maxbno)
 530         db->maxbno += DBLKSIZ * BYTESIZ;
 531
 532     off = OFF_DIR(dirb);
 533     if ((status = apr_file_seek(db->dirf, APR_SET, &off)) == APR_SUCCESS)
 534         status = apr_file_write_full(db->dirf, db->dirbuf, DBLKSIZ, NULL);
 535
 536     return status;
 537 }
 538
 539 /*
 540 * getnext - get the next key in the page, and if done with
 541 * the page, try the next page in sequence
 542 */
 543 static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db)
 544 {
 545     apr_status_t status;
 546     for (;;) {
 547         db->keyptr++;
 548         *key = getnkey(db->pagbuf, db->keyptr);
 549         if (key->dptr != NULL)
 550             return APR_SUCCESS;
 551         /*
 552          * we either run out, or there is nothing on this page..
 553          * try the next one... If we lost our position on the
 554          * file, we will have to seek.
 555          */
 556         db->keyptr = 0;
 557         if (db->pagbno != db->blkptr++) {
 558             apr_off_t off = OFF_PAG(db->blkptr);
 559             if ((status = apr_file_seek(db->pagf, APR_SET, &off))
 560                         != APR_SUCCESS)
 561                 return status;
 562         }
 563
 564         db->pagbno = db->blkptr;
 565         /* ### EOF acceptable here too? */
 566         if ((status = apr_file_read_full(db->pagf, db->pagbuf, PBLKSIZ, NULL))
 567                     != APR_SUCCESS)
 568             return status;
 569         if (!chkpage(db->pagbuf))
 570             return APR_EGENERAL;     /* ### need better error */
 571     }
 572
 573     /* NOTREACHED */
 574 }
 575
 576
 577 APU_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