rubbos/app/httpd-2.0.64/srclib/apr-util/dbm/sdbm/sdbm.c

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