pppd/tdb.c

   1 /*
   2  * Database functions
   3  * Copyright (C) Andrew Tridgell 1999
   4  *
   5  * Redistribution and use in source and binary forms are permitted
   6  * provided that the above copyright notice and this paragraph are
   7  * duplicated in all such forms AND provided that this software or
   8  * any derived work is only used as part of the PPP daemon (pppd)
   9  * and related utilities.
  10  * The name of the author may not be used to endorse or promote products
  11  * derived from this software without specific prior written permission.
  12  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  13  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  14  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  15  *
  16  * Note: this software is also available under the Gnu Public License
  17  * version 2 or later.
  18  */
  19
  20 #include <stdlib.h>
  21 #include <stdio.h>
  22 #include <fcntl.h>
  23 #include <unistd.h>
  24 #include <string.h>
  25 #include <fcntl.h>
  26 #include <errno.h>
  27 #include <sys/mman.h>
  28 #include <sys/stat.h>
  29 #include "tdb.h"
  30
  31 #define TDB_VERSION (0x26011967 + 1)
  32 #define TDB_MAGIC (0x26011999U)
  33 #define TDB_FREE_MAGIC (~TDB_MAGIC)
  34 #define TDB_ALIGN 4
  35 #define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGN)
  36 #define DEFAULT_HASH_SIZE 128
  37 #define TDB_PAGE_SIZE 0x2000
  38 #define TDB_LEN_MULTIPLIER 10
  39 #define FREELIST_TOP (sizeof(struct tdb_header))
  40
  41 #define LOCK_SET 1
  42 #define LOCK_CLEAR 0
  43
  44 /* lock offsets */
  45 #define GLOBAL_LOCK 0
  46 #define ACTIVE_LOCK 4
  47 #define LIST_LOCK_BASE 1024
  48
  49 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
  50
  51 #ifndef MAP_FILE
  52 #define MAP_FILE 0
  53 #endif
  54
  55 /* the body of the database is made of one list_struct for the free space
  56    plus a separate data list for each hash value */
  57 struct list_struct {
  58         tdb_len rec_len; /* total byte length of record */
  59         tdb_off next; /* offset of the next record in the list */
  60         tdb_len key_len; /* byte length of key */
  61         tdb_len data_len; /* byte length of data */
  62         unsigned full_hash; /* the full 32 bit hash of the key */
  63         unsigned magic;   /* try to catch errors */
  64         /*
  65            the following union is implied
  66            union {
  67               char record[rec_len];
  68               struct {
  69                 char key[key_len];
  70                 char data[data_len];
  71               }
  72            }
  73         */
  74 };
  75
  76 /* a null data record - useful for error returns */
  77 static TDB_DATA null_data;
  78
  79 /* a byte range locking function - return 0 on success
  80    this functions locks/unlocks 1 byte at the specified offset */
  81 static int tdb_brlock(TDB_CONTEXT *tdb, tdb_off offset,
  82                       int set, int rw_type, int lck_type)
  83 {
  84 #if NOLOCK
  85         return 0;
  86 #else
  87         struct flock fl;
  88
  89         if (tdb->fd == -1) return 0;   /* for in memory tdb */
  90
  91         if (tdb->read_only) return -1;
  92
  93         fl.l_type = set==LOCK_SET?rw_type:F_UNLCK;
  94         fl.l_whence = SEEK_SET;
  95         fl.l_start = offset;
  96         fl.l_len = 1;
  97         fl.l_pid = 0;
  98
  99         if (fcntl(tdb->fd, lck_type, &fl) != 0) {
 100 #if TDB_DEBUG
 101                 if (lck_type == F_SETLKW) {
 102                         printf("lock %d failed at %d (%s)\n",
 103                                set, offset, strerror(errno));
 104                 }
 105 #endif
 106                 tdb->ecode = TDB_ERR_LOCK;
 107                 return -1;
 108         }
 109         return 0;
 110 #endif
 111 }
 112
 113 /* lock a list in the database. list -1 is the alloc list */
 114 static int tdb_lock(TDB_CONTEXT *tdb, int list)
 115 {
 116         if (list < -1 || list >= (int)tdb->header.hash_size) {
 117 #if TDB_DEBUG
 118                 printf("bad list %d\n", list);
 119 #endif
 120                 return -1;
 121         }
 122         if (tdb->locked[list+1] == 0) {
 123                 if (tdb_brlock(tdb, LIST_LOCK_BASE + 4*list, LOCK_SET,
 124                                F_WRLCK, F_SETLKW) != 0) {
 125                         return -1;
 126                 }
 127         }
 128         tdb->locked[list+1]++;
 129         return 0;
 130 }
 131
 132 /* unlock the database. */
 133 static int tdb_unlock(TDB_CONTEXT *tdb, int list)
 134 {
 135         if (list < -1 || list >= (int)tdb->header.hash_size) {
 136 #if TDB_DEBUG
 137                 printf("bad unlock list %d\n", list);
 138 #endif
 139                 return -1;
 140         }
 141
 142         if (tdb->locked[list+1] == 0) {
 143 #if TDB_DEBUG
 144                 printf("not locked %d\n", list);
 145 #endif
 146                 tdb->ecode = TDB_ERR_LOCK;
 147                 return -1;
 148         }
 149         if (tdb->locked[list+1] == 1) {
 150                 if (tdb_brlock(tdb, LIST_LOCK_BASE + 4*list, LOCK_CLEAR,
 151                                F_WRLCK, F_SETLKW) != 0) {
 152                         return -1;
 153                 }
 154         }
 155         tdb->locked[list+1]--;
 156         return 0;
 157 }
 158
 159 /* the hash algorithm - turn a key into an integer
 160    This is based on the hash agorithm from gdbm */
 161 static unsigned tdb_hash(TDB_DATA *key)
 162 {
 163         unsigned value; /* Used to compute the hash value.  */
 164         unsigned   i;   /* Used to cycle through random values. */
 165
 166         /* Set the initial value from the key size. */
 167         value = 0x238F13AF * key->dsize;
 168         for (i=0; i < key->dsize; i++) {
 169                 value = (value + (key->dptr[i] << (i*5 % 24)));
 170         }
 171
 172         value = (1103515243 * value + 12345);
 173
 174         return value;
 175 }
 176
 177 /* find the top of the hash chain for an open database */
 178 static tdb_off tdb_hash_top(TDB_CONTEXT *tdb, unsigned hash)
 179 {
 180         tdb_off ret;
 181         hash = BUCKET(hash);
 182         ret = FREELIST_TOP + (hash+1)*sizeof(tdb_off);
 183         return ret;
 184 }
 185
 186
 187 /* check for an out of bounds access - if it is out of bounds then
 188    see if the database has been expanded by someone else and expand
 189    if necessary */
 190 static int tdb_oob(TDB_CONTEXT *tdb, tdb_off offset)
 191 {
 192         struct stat st;
 193         if ((offset <= tdb->map_size) || (tdb->fd == -1)) return 0;
 194
 195         fstat(tdb->fd, &st);
 196         if (st.st_size <= (ssize_t)offset) {
 197                 tdb->ecode = TDB_ERR_IO;
 198                 return -1;
 199         }
 200
 201 #if HAVE_MMAP
 202         if (tdb->map_ptr) {
 203                 munmap(tdb->map_ptr, tdb->map_size);
 204                 tdb->map_ptr = NULL;
 205         }
 206 #endif
 207
 208         tdb->map_size = st.st_size;
 209 #if HAVE_MMAP
 210         tdb->map_ptr = (void *)mmap(NULL, tdb->map_size,
 211                                     tdb->read_only?PROT_READ:PROT_READ|PROT_WRITE,
 212                                     MAP_SHARED | MAP_FILE, tdb->fd, 0);
 213 #endif
 214         return 0;
 215 }
 216
 217
 218 /* write a lump of data at a specified offset */
 219 static int tdb_write(TDB_CONTEXT *tdb, tdb_off offset, const char *buf, tdb_len len)
 220 {
 221         if (tdb_oob(tdb, offset + len) != 0) {
 222                 /* oops - trying to write beyond the end of the database! */
 223                 return -1;
 224         }
 225
 226         if (tdb->map_ptr) {
 227                 memcpy(offset + (char *)tdb->map_ptr, buf, len);
 228         } else {
 229                 if (lseek(tdb->fd, offset, SEEK_SET) != offset ||
 230                     write(tdb->fd, buf, len) != (ssize_t)len) {
 231                         tdb->ecode = TDB_ERR_IO;
 232                         return -1;
 233                 }
 234         }
 235         return 0;
 236 }
 237
 238 /* read a lump of data at a specified offset */
 239 static int tdb_read(TDB_CONTEXT *tdb, tdb_off offset, char *buf, tdb_len len)
 240 {
 241         if (tdb_oob(tdb, offset + len) != 0) {
 242                 /* oops - trying to read beyond the end of the database! */
 243                 return -1;
 244         }
 245
 246         if (tdb->map_ptr) {
 247                 memcpy(buf, offset + (char *)tdb->map_ptr, len);
 248         } else {
 249                 if (lseek(tdb->fd, offset, SEEK_SET) != offset ||
 250                     read(tdb->fd, buf, len) != (ssize_t)len) {
 251                         tdb->ecode = TDB_ERR_IO;
 252                         return -1;
 253                 }
 254         }
 255         return 0;
 256 }
 257
 258
 259 /* read a lump of data, allocating the space for it */
 260 static char *tdb_alloc_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_len len)
 261 {
 262         char *buf;
 263
 264         buf = (char *)malloc(len);
 265
 266         if (!buf) {
 267                 tdb->ecode = TDB_ERR_OOM;
 268                 return NULL;
 269         }
 270
 271         if (tdb_read(tdb, offset, buf, len) == -1) {
 272                 free(buf);
 273                 return NULL;
 274         }
 275
 276         return buf;
 277 }
 278
 279 /* convenience routine for writing a record */
 280 static int rec_write(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
 281 {
 282         return tdb_write(tdb, offset, (char *)rec, sizeof(*rec));
 283 }
 284
 285 /* convenience routine for writing a tdb_off */
 286 static int ofs_write(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
 287 {
 288         return tdb_write(tdb, offset, (char *)d, sizeof(*d));
 289 }
 290
 291 /* read a tdb_off from the store */
 292 static int ofs_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
 293 {
 294         return tdb_read(tdb, offset, (char *)d, sizeof(*d));
 295 }
 296
 297 /* read a record and check for simple errors */
 298 static int rec_read(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
 299 {
 300         if (tdb_read(tdb, offset, (char *)rec, sizeof(*rec)) == -1) return -1;
 301         if (rec->magic != TDB_MAGIC) {
 302 #if TDB_DEBUG
 303                 printf("bad magic 0x%08x at offset %d\n",
 304                        rec->magic, offset);
 305 #endif
 306                 tdb->ecode = TDB_ERR_CORRUPT;
 307                 return -1;
 308         }
 309         if (tdb_oob(tdb, rec->next) != 0) {
 310                 return -1;
 311         }
 312         return 0;
 313 }
 314
 315 /* expand the database at least length bytes by expanding the
 316    underlying file and doing the mmap again if necessary */
 317 static int tdb_expand(TDB_CONTEXT *tdb, tdb_off length)
 318 {
 319         struct list_struct rec;
 320         tdb_off offset, ptr;
 321         char b = 0;
 322
 323         tdb_lock(tdb,-1);
 324
 325         /* make sure we know about any previous expansions by another
 326            process */
 327         tdb_oob(tdb,tdb->map_size + 1);
 328
 329         /* always make room for at least 10 more records */
 330         length *= TDB_LEN_MULTIPLIER;
 331
 332         /* and round the database up to a multiple of TDB_PAGE_SIZE */
 333         length = ((tdb->map_size + length + TDB_PAGE_SIZE) & ~(TDB_PAGE_SIZE - 1)) - tdb->map_size;
 334
 335         /* expand the file itself */
 336         if (tdb->fd != -1) {
 337             lseek(tdb->fd, tdb->map_size + length - 1, SEEK_SET);
 338             if (write(tdb->fd, &b, 1) != 1) goto fail;
 339         }
 340
 341         /* form a new freelist record */
 342         offset = FREELIST_TOP;
 343         rec.rec_len = length - sizeof(rec);
 344         rec.magic = TDB_FREE_MAGIC;
 345         if (ofs_read(tdb, offset, &rec.next) == -1) {
 346                 goto fail;
 347         }
 348
 349 #if HAVE_MMAP
 350         if (tdb->fd != -1 && tdb->map_ptr) {
 351                 munmap(tdb->map_ptr, tdb->map_size);
 352                 tdb->map_ptr = NULL;
 353         }
 354 #endif
 355
 356         tdb->map_size += length;
 357
 358         if (tdb->fd == -1) {
 359             tdb->map_ptr = realloc(tdb->map_ptr, tdb->map_size);
 360         }
 361
 362         /* write it out */
 363         if (rec_write(tdb, tdb->map_size - length, &rec) == -1) {
 364                 goto fail;
 365         }
 366
 367         /* link it into the free list */
 368         ptr = tdb->map_size - length;
 369         if (ofs_write(tdb, offset, &ptr) == -1) goto fail;
 370
 371 #if HAVE_MMAP
 372         if (tdb->fd != -1) {
 373             tdb->map_ptr = (void *)mmap(NULL, tdb->map_size,
 374                                         PROT_READ|PROT_WRITE,
 375                                         MAP_SHARED | MAP_FILE, tdb->fd, 0);
 376         }
 377 #endif
 378
 379         tdb_unlock(tdb, -1);
 380         return 0;
 381
 382  fail:
 383         tdb_unlock(tdb,-1);
 384         return -1;
 385 }
 386
 387 /* allocate some space from the free list. The offset returned points
 388    to a unconnected list_struct within the database with room for at
 389    least length bytes of total data
 390
 391    0 is returned if the space could not be allocated
 392  */
 393 static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length)
 394 {
 395         tdb_off offset, rec_ptr, last_ptr;
 396         struct list_struct rec, lastrec, newrec;
 397
 398         tdb_lock(tdb, -1);
 399
 400  again:
 401         last_ptr = 0;
 402         offset = FREELIST_TOP;
 403
 404         /* read in the freelist top */
 405         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 406                 goto fail;
 407         }
 408
 409         /* keep looking until we find a freelist record that is big
 410            enough */
 411         while (rec_ptr) {
 412                 if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) {
 413                         goto fail;
 414                 }
 415
 416                 if (rec.magic != TDB_FREE_MAGIC) {
 417 #if TDB_DEBUG
 418                         printf("bad magic 0x%08x in free list\n", rec.magic);
 419 #endif
 420                         goto fail;
 421                 }
 422
 423                 if (rec.rec_len >= length) {
 424                         /* found it - now possibly split it up  */
 425                         if (rec.rec_len > length + MIN_REC_SIZE) {
 426                                 length = (length + TDB_ALIGN) & ~(TDB_ALIGN-1);
 427
 428                                 newrec.rec_len = rec.rec_len - (sizeof(rec) + length);
 429                                 newrec.next = rec.next;
 430                                 newrec.magic = TDB_FREE_MAGIC;
 431
 432                                 rec.rec_len = length;
 433                                 rec.next = rec_ptr + sizeof(rec) + rec.rec_len;
 434
 435                                 if (rec_write(tdb, rec.next, &newrec) == -1) {
 436                                         goto fail;
 437                                 }
 438
 439                                 if (rec_write(tdb, rec_ptr, &rec) == -1) {
 440                                         goto fail;
 441                                 }
 442                         }
 443
 444                         /* remove it from the list */
 445                         if (last_ptr == 0) {
 446                                 offset = FREELIST_TOP;
 447
 448                                 if (ofs_write(tdb, offset, &rec.next) == -1) {
 449                                         goto fail;
 450                                 }
 451                         } else {
 452                                 lastrec.next = rec.next;
 453                                 if (rec_write(tdb, last_ptr, &lastrec) == -1) {
 454                                         goto fail;
 455                                 }
 456                         }
 457
 458                         /* all done - return the new record offset */
 459                         tdb_unlock(tdb, -1);
 460                         return rec_ptr;
 461                 }
 462
 463                 /* move to the next record */
 464                 lastrec = rec;
 465                 last_ptr = rec_ptr;
 466                 rec_ptr = rec.next;
 467         }
 468
 469         /* we didn't find enough space. See if we can expand the
 470            database and if we can then try again */
 471         if (tdb_expand(tdb, length + sizeof(rec)) == 0) goto again;
 472
 473  fail:
 474 #if TDB_DEBUG
 475         printf("tdb_allocate failed for size %u\n", length);
 476 #endif
 477         tdb_unlock(tdb, -1);
 478         return 0;
 479 }
 480
 481 /* initialise a new database with a specified hash size */
 482 static int tdb_new_database(TDB_CONTEXT *tdb, int hash_size)
 483 {
 484         struct tdb_header header;
 485         tdb_off offset;
 486         int i, size = 0;
 487         tdb_off buf[16];
 488
 489         /* create the header */
 490         memset(&header, 0, sizeof(header));
 491         memcpy(header.magic_food, TDB_MAGIC_FOOD, strlen(TDB_MAGIC_FOOD)+1);
 492         header.version = TDB_VERSION;
 493         header.hash_size = hash_size;
 494         lseek(tdb->fd, 0, SEEK_SET);
 495         ftruncate(tdb->fd, 0);
 496
 497         if (tdb->fd != -1 && write(tdb->fd, &header, sizeof(header)) !=
 498             sizeof(header)) {
 499             tdb->ecode = TDB_ERR_IO;
 500             return -1;
 501         } else size += sizeof(header);
 502
 503         /* the freelist and hash pointers */
 504         offset = 0;
 505         memset(buf, 0, sizeof(buf));
 506
 507         for (i=0;(hash_size+1)-i >= 16; i += 16) {
 508             if (tdb->fd != -1 && write(tdb->fd, buf, sizeof(buf)) !=
 509                 sizeof(buf)) {
 510                 tdb->ecode = TDB_ERR_IO;
 511                 return -1;
 512             } else size += sizeof(buf);
 513         }
 514
 515         for (;i<hash_size+1; i++) {
 516             if (tdb->fd != -1 && write(tdb->fd, buf, sizeof(tdb_off)) !=
 517                 sizeof(tdb_off)) {
 518                 tdb->ecode = TDB_ERR_IO;
 519                 return -1;
 520             } else size += sizeof(tdb_off);
 521         }
 522
 523         if (tdb->fd == -1) {
 524             tdb->map_ptr = calloc(size, 1);
 525             tdb->map_size = size;
 526             if (tdb->map_ptr == NULL) {
 527                 tdb->ecode = TDB_ERR_IO;
 528                 return -1;
 529             }
 530             memcpy(&tdb->header, &header, sizeof(header));
 531         }
 532
 533 #if TDB_DEBUG
 534         printf("initialised database of hash_size %u\n",
 535                hash_size);
 536 #endif
 537         return 0;
 538 }
 539
 540 /* Returns 0 on fail.  On success, return offset of record, and fills
 541    in rec */
 542 static tdb_off tdb_find(TDB_CONTEXT *tdb, TDB_DATA key, unsigned int hash,
 543                         struct list_struct *rec)
 544 {
 545         tdb_off offset, rec_ptr;
 546
 547         /* find the top of the hash chain */
 548         offset = tdb_hash_top(tdb, hash);
 549
 550         /* read in the hash top */
 551         if (ofs_read(tdb, offset, &rec_ptr) == -1)
 552                 return 0;
 553
 554         /* keep looking until we find the right record */
 555         while (rec_ptr) {
 556                 if (rec_read(tdb, rec_ptr, rec) == -1)
 557                         return 0;
 558
 559                 if (hash == rec->full_hash && key.dsize == rec->key_len) {
 560                         char *k;
 561                         /* a very likely hit - read the key */
 562                         k = tdb_alloc_read(tdb, rec_ptr + sizeof(*rec),
 563                                            rec->key_len);
 564
 565                         if (!k)
 566                                 return 0;
 567
 568                         if (memcmp(key.dptr, k, key.dsize) == 0) {
 569                                 free(k);
 570                                 return rec_ptr;
 571                         }
 572                         free(k);
 573                 }
 574
 575                 /* move to the next record */
 576                 rec_ptr = rec->next;
 577         }
 578         return 0;
 579 }
 580
 581 /*
 582    return an error string for the last tdb error
 583 */
 584 char *tdb_error(TDB_CONTEXT *tdb)
 585 {
 586         int i;
 587         static struct {
 588                 enum TDB_ERROR ecode;
 589                 char *estring;
 590         } emap[] = {
 591                 {TDB_SUCCESS, "Success"},
 592                 {TDB_ERR_CORRUPT, "Corrupt database"},
 593                 {TDB_ERR_IO, "IO Error"},
 594                 {TDB_ERR_LOCK, "Locking error"},
 595                 {TDB_ERR_OOM, "Out of memory"},
 596                 {TDB_ERR_EXISTS, "Record exists"},
 597                 {-1, NULL}};
 598         if (tdb != NULL) {
 599             for (i=0;emap[i].estring;i++) {
 600                 if (tdb->ecode == emap[i].ecode) return emap[i].estring;
 601             }
 602         } else {
 603             return "Invalid tdb context";
 604         }
 605         return "Invalid error code";
 606 }
 607
 608
 609 /* update an entry in place - this only works if the new data size
 610    is <= the old data size and the key exists.
 611    on failure return -1
 612 */
 613 int tdb_update(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)
 614 {
 615         unsigned hash;
 616         struct list_struct rec;
 617         tdb_off rec_ptr;
 618         int ret = -1;
 619
 620         if (tdb == NULL) {
 621 #ifdef TDB_DEBUG
 622             printf("tdb_update() called with null context\n");
 623 #endif
 624             return -1;
 625         }
 626
 627         /* find which hash bucket it is in */
 628         hash = tdb_hash(&key);
 629
 630         tdb_lock(tdb, BUCKET(hash));
 631         rec_ptr = tdb_find(tdb, key, hash, &rec);
 632
 633         if (!rec_ptr)
 634                 goto out;
 635
 636         /* must be long enough */
 637         if (rec.rec_len < key.dsize + dbuf.dsize)
 638                 goto out;
 639
 640         if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
 641                       dbuf.dptr, dbuf.dsize) == -1)
 642                 goto out;
 643
 644         if (dbuf.dsize != rec.data_len) {
 645                 /* update size */
 646                 rec.data_len = dbuf.dsize;
 647                 ret = rec_write(tdb, rec_ptr, &rec);
 648         } else
 649                 ret = 0;
 650
 651  out:
 652         tdb_unlock(tdb, BUCKET(hash));
 653         return ret;
 654 }
 655
 656 /* find an entry in the database given a key */
 657 TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key)
 658 {
 659         unsigned hash;
 660         tdb_off rec_ptr;
 661         struct list_struct rec;
 662         TDB_DATA ret = null_data;
 663
 664         if (tdb == NULL) {
 665 #ifdef TDB_DEBUG
 666             printf("tdb_fetch() called with null context\n");
 667 #endif
 668             return null_data;
 669         }
 670
 671         /* find which hash bucket it is in */
 672         hash = tdb_hash(&key);
 673
 674         tdb_lock(tdb, BUCKET(hash));
 675         rec_ptr = tdb_find(tdb, key, hash, &rec);
 676
 677         if (rec_ptr) {
 678                 ret.dptr = tdb_alloc_read(tdb,
 679                                           rec_ptr + sizeof(rec) + rec.key_len,
 680                                           rec.data_len);
 681                 ret.dsize = rec.data_len;
 682         }
 683
 684         tdb_unlock(tdb, BUCKET(hash));
 685         return ret;
 686 }
 687
 688 /* check if an entry in the database exists
 689
 690    note that 1 is returned if the key is found and 0 is returned if not found
 691    this doesn't match the conventions in the rest of this module, but is
 692    compatible with gdbm
 693 */
 694 int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key)
 695 {
 696         unsigned hash;
 697         tdb_off rec_ptr;
 698         struct list_struct rec;
 699
 700         if (tdb == NULL) {
 701 #ifdef TDB_DEBUG
 702             printf("tdb_exists() called with null context\n");
 703 #endif
 704             return 0;
 705         }
 706
 707         /* find which hash bucket it is in */
 708         hash = tdb_hash(&key);
 709
 710         tdb_lock(tdb, BUCKET(hash));
 711         rec_ptr = tdb_find(tdb, key, hash, &rec);
 712         tdb_unlock(tdb, BUCKET(hash));
 713
 714         return rec_ptr != 0;
 715 }
 716
 717 /* traverse the entire database - calling fn(tdb, key, data) on each element.
 718    return -1 on error or the record count traversed
 719    if fn is NULL then it is not called
 720    a non-zero return value from fn() indicates that the traversal should stop
 721   */
 722 int tdb_traverse(TDB_CONTEXT *tdb, int (*fn)(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, void* state), void* state)
 723 {
 724         int count = 0;
 725         unsigned h;
 726         tdb_off offset, rec_ptr;
 727         struct list_struct rec;
 728         char *data;
 729         TDB_DATA key, dbuf;
 730
 731         if (tdb == NULL) {
 732 #ifdef TDB_DEBUG
 733             printf("tdb_traverse() called with null context\n");
 734 #endif
 735             return -1;
 736         }
 737
 738         /* loop over all hash chains */
 739         for (h = 0; h < tdb->header.hash_size; h++) {
 740                 tdb_lock(tdb, BUCKET(h));
 741
 742                 /* read in the hash top */
 743                 offset = tdb_hash_top(tdb, h);
 744                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 745                         goto fail;
 746                 }
 747
 748                 /* traverse all records for this hash */
 749                 while (rec_ptr) {
 750                         if (rec_read(tdb, rec_ptr, &rec) == -1) {
 751                                 goto fail;
 752                         }
 753
 754                         /* now read the full record */
 755                         data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec),
 756                                              rec.key_len + rec.data_len);
 757                         if (!data) {
 758                                 goto fail;
 759                         }
 760
 761                         key.dptr = data;
 762                         key.dsize = rec.key_len;
 763                         dbuf.dptr = data + rec.key_len;
 764                         dbuf.dsize = rec.data_len;
 765                         count++;
 766
 767                         if (fn && fn(tdb, key, dbuf, state) != 0) {
 768                                 /* they want us to stop traversing */
 769                                 free(data);
 770                                 tdb_unlock(tdb, BUCKET(h));
 771                                 return count;
 772                         }
 773
 774                         /* a miss - drat */
 775                         free(data);
 776
 777                         /* move to the next record */
 778                         rec_ptr = rec.next;
 779                 }
 780                 tdb_unlock(tdb, BUCKET(h));
 781         }
 782
 783         /* return the number traversed */
 784         return count;
 785
 786  fail:
 787         tdb_unlock(tdb, BUCKET(h));
 788         return -1;
 789 }
 790
 791
 792 /* find the first entry in the database and return its key */
 793 TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb)
 794 {
 795         tdb_off offset, rec_ptr;
 796         struct list_struct rec;
 797         unsigned hash;
 798         TDB_DATA ret;
 799
 800         if (tdb == NULL) {
 801 #ifdef TDB_DEBUG
 802             printf("tdb_firstkey() called with null context\n");
 803 #endif
 804             return null_data;
 805         }
 806
 807         /* look for a non-empty hash chain */
 808         for (hash = 0, rec_ptr = 0;
 809              hash < tdb->header.hash_size;
 810              hash++) {
 811                 /* find the top of the hash chain */
 812                 offset = tdb_hash_top(tdb, hash);
 813
 814                 tdb_lock(tdb, BUCKET(hash));
 815
 816                 /* read in the hash top */
 817                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 818                         goto fail;
 819                 }
 820
 821                 if (rec_ptr) break;
 822
 823                 tdb_unlock(tdb, BUCKET(hash));
 824         }
 825
 826         if (rec_ptr == 0) return null_data;
 827
 828         /* we've found a non-empty chain, now read the record */
 829         if (rec_read(tdb, rec_ptr, &rec) == -1) {
 830                 goto fail;
 831         }
 832
 833         /* allocate and read the key space */
 834         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len);
 835         ret.dsize = rec.key_len;
 836         tdb_unlock(tdb, BUCKET(hash));
 837         return ret;
 838
 839  fail:
 840         tdb_unlock(tdb, BUCKET(hash));
 841         return null_data;
 842 }
 843
 844 /* find the next entry in the database, returning its key */
 845 TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA key)
 846 {
 847         unsigned hash, hbucket;
 848         tdb_off rec_ptr, offset;
 849         struct list_struct rec;
 850         TDB_DATA ret;
 851
 852         if (tdb == NULL) {
 853 #ifdef TDB_DEBUG
 854             printf("tdb_nextkey() called with null context\n");
 855 #endif
 856             return null_data;
 857         }
 858
 859         /* find which hash bucket it is in */
 860         hash = tdb_hash(&key);
 861         hbucket = BUCKET(hash);
 862
 863         tdb_lock(tdb, hbucket);
 864         rec_ptr = tdb_find(tdb, key, hash, &rec);
 865         if (rec_ptr) {
 866                 /* we want the next record after this one */
 867                 rec_ptr = rec.next;
 868         }
 869
 870         /* not found or last in hash: look for next non-empty hash chain */
 871         while (rec_ptr == 0) {
 872                 tdb_unlock(tdb, hbucket);
 873
 874                 if (++hbucket >= tdb->header.hash_size - 1)
 875                         return null_data;
 876
 877                 offset = tdb_hash_top(tdb, hbucket);
 878                 tdb_lock(tdb, hbucket);
 879                 /* read in the hash top */
 880                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 881                         tdb_unlock(tdb, hbucket);
 882                         return null_data;
 883                 }
 884         }
 885
 886         /* Read the record. */
 887         if (rec_read(tdb, rec_ptr, &rec) == -1) {
 888                 tdb_unlock(tdb, hbucket);
 889                 return null_data;
 890         }
 891         /* allocate and read the key */
 892         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len);
 893         ret.dsize = rec.key_len;
 894         tdb_unlock(tdb, hbucket);
 895
 896         return ret;
 897 }
 898
 899 /* delete an entry in the database given a key */
 900 int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key)
 901 {
 902         unsigned hash;
 903         tdb_off offset, rec_ptr, last_ptr;
 904         struct list_struct rec, lastrec;
 905         char *data = NULL;
 906
 907         if (tdb == NULL) {
 908 #ifdef TDB_DEBUG
 909             printf("tdb_delete() called with null context\n");
 910 #endif
 911             return -1;
 912         }
 913
 914         /* find which hash bucket it is in */
 915         hash = tdb_hash(&key);
 916
 917         tdb_lock(tdb, BUCKET(hash));
 918
 919         /* find the top of the hash chain */
 920         offset = tdb_hash_top(tdb, hash);
 921
 922         /* read in the hash top */
 923         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 924                 goto fail;
 925         }
 926
 927         last_ptr = 0;
 928
 929         /* keep looking until we find the right record */
 930         while (rec_ptr) {
 931                 if (rec_read(tdb, rec_ptr, &rec) == -1) {
 932                         goto fail;
 933                 }
 934
 935                 if (hash == rec.full_hash && key.dsize == rec.key_len) {
 936                         /* a very likely hit - read the record and full key */
 937                         data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec),
 938                                              rec.key_len);
 939                         if (!data) {
 940                                 goto fail;
 941                         }
 942
 943                         if (memcmp(key.dptr, data, key.dsize) == 0) {
 944                                 /* a definite match - delete it */
 945                                 if (last_ptr == 0) {
 946                                         offset = tdb_hash_top(tdb, hash);
 947                                         if (ofs_write(tdb, offset, &rec.next) == -1) {
 948                                                 goto fail;
 949                                         }
 950                                 } else {
 951                                         lastrec.next = rec.next;
 952                                         if (rec_write(tdb, last_ptr, &lastrec) == -1) {
 953                                                 goto fail;
 954                                         }
 955                                 }
 956                                 tdb_unlock(tdb, BUCKET(hash));
 957                                 tdb_lock(tdb, -1);
 958                                 /* and recover the space */
 959                                 offset = FREELIST_TOP;
 960                                 if (ofs_read(tdb, offset, &rec.next) == -1) {
 961                                         goto fail2;
 962                                 }
 963                                 rec.magic = TDB_FREE_MAGIC;
 964                                 if (rec_write(tdb, rec_ptr, &rec) == -1) {
 965                                         goto fail2;
 966                                 }
 967                                 if (ofs_write(tdb, offset, &rec_ptr) == -1) {
 968                                         goto fail2;
 969                                 }
 970
 971                                 /* yipee - all done */
 972                                 free(data);
 973                                 tdb_unlock(tdb, -1);
 974                                 return 0;
 975                         }
 976
 977                         /* a miss - drat */
 978                         free(data);
 979                         data = NULL;
 980                 }
 981
 982                 /* move to the next record */
 983                 last_ptr = rec_ptr;
 984                 lastrec = rec;
 985                 rec_ptr = rec.next;
 986         }
 987
 988  fail:
 989         if (data) free(data);
 990         tdb_unlock(tdb, BUCKET(hash));
 991         return -1;
 992
 993  fail2:
 994         if (data) free(data);
 995         tdb_unlock(tdb, -1);
 996         return -1;
 997 }
 998
 999
1000 /* store an element in the database, replacing any existing element
1001    with the same key
1002
1003    return 0 on success, -1 on failure
1004 */
1005 int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
1006 {
1007         struct list_struct rec;
1008         unsigned hash;
1009         tdb_off rec_ptr, offset;
1010         char *p = NULL;
1011
1012         if (tdb == NULL) {
1013 #ifdef TDB_DEBUG
1014             printf("tdb_store() called with null context\n");
1015 #endif
1016             return -1;
1017         }
1018
1019         /* find which hash bucket it is in */
1020         hash = tdb_hash(&key);
1021
1022         /* check for it existing */
1023         if (flag == TDB_INSERT && tdb_exists(tdb, key)) {
1024                 tdb->ecode = TDB_ERR_EXISTS;
1025                 return -1;
1026         }
1027
1028         /* first try in-place update */
1029         if (flag != TDB_INSERT && tdb_update(tdb, key, dbuf) == 0) {
1030                 return 0;
1031         }
1032
1033         rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize);
1034         if (rec_ptr == 0) {
1035                 return -1;
1036         }
1037
1038         tdb_lock(tdb, BUCKET(hash));
1039
1040         /* delete any existing record - if it doesn't exist we don't care */
1041         if (flag != TDB_INSERT) {
1042                 tdb_delete(tdb, key);
1043         }
1044
1045         /* read the newly created record */
1046         if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) {
1047                 goto fail;
1048         }
1049
1050         if (rec.magic != TDB_FREE_MAGIC) goto fail;
1051
1052         /* find the top of the hash chain */
1053         offset = tdb_hash_top(tdb, hash);
1054
1055         /* read in the hash top diretcly into our next pointer */
1056         if (ofs_read(tdb, offset, &rec.next) == -1) {
1057                 goto fail;
1058         }
1059
1060         rec.key_len = key.dsize;
1061         rec.data_len = dbuf.dsize;
1062         rec.full_hash = hash;
1063         rec.magic = TDB_MAGIC;
1064
1065         p = (char *)malloc(sizeof(rec) + key.dsize + dbuf.dsize);
1066         if (!p) {
1067                 tdb->ecode = TDB_ERR_OOM;
1068                 goto fail;
1069         }
1070
1071         memcpy(p, &rec, sizeof(rec));
1072         memcpy(p+sizeof(rec), key.dptr, key.dsize);
1073         memcpy(p+sizeof(rec)+key.dsize, dbuf.dptr, dbuf.dsize);
1074
1075         if (tdb_write(tdb, rec_ptr, p, sizeof(rec)+key.dsize+dbuf.dsize) == -1)
1076                 goto fail;
1077
1078         free(p);
1079         p = NULL;
1080
1081         /* and point the top of the hash chain at it */
1082         if (ofs_write(tdb, offset, &rec_ptr) == -1) goto fail;
1083
1084         tdb_unlock(tdb, BUCKET(hash));
1085         return 0;
1086
1087  fail:
1088 #if TDB_DEBUG
1089         printf("store failed for hash 0x%08x in bucket %u\n", hash, BUCKET(hash));
1090 #endif
1091         if (p) free(p);
1092         tdb_unlock(tdb, BUCKET(hash));
1093         return -1;
1094 }
1095
1096
1097 /* open the database, creating it if necessary
1098
1099    The open_flags and mode are passed straight to the open call on the database
1100    file. A flags value of O_WRONLY is invalid
1101
1102    The hash size is advisory, use zero for a default value.
1103
1104    return is NULL on error
1105 */
1106 TDB_CONTEXT *tdb_open(char *name, int hash_size, int tdb_flags,
1107                       int open_flags, mode_t mode)
1108 {
1109         TDB_CONTEXT tdb, *ret;
1110         struct stat st;
1111
1112         memset(&tdb, 0, sizeof(tdb));
1113
1114         tdb.fd = -1;
1115         tdb.name = NULL;
1116         tdb.map_ptr = NULL;
1117
1118         if ((open_flags & O_ACCMODE) == O_WRONLY) {
1119                 goto fail;
1120         }
1121
1122         if (hash_size == 0) hash_size = DEFAULT_HASH_SIZE;
1123
1124         tdb.read_only = ((open_flags & O_ACCMODE) == O_RDONLY);
1125
1126         if (name != NULL) {
1127             tdb.fd = open(name, open_flags, mode);
1128             if (tdb.fd == -1) {
1129                 goto fail;
1130             }
1131         }
1132
1133         /* ensure there is only one process initialising at once */
1134         tdb_brlock(&tdb, GLOBAL_LOCK, LOCK_SET, F_WRLCK, F_SETLKW);
1135
1136         if (tdb_flags & TDB_CLEAR_IF_FIRST) {
1137                 /* we need to zero the database if we are the only
1138                    one with it open */
1139                 if (tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_SET, F_WRLCK, F_SETLK) == 0) {
1140                         ftruncate(tdb.fd, 0);
1141                         tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_CLEAR, F_WRLCK, F_SETLK);
1142                 }
1143         }
1144
1145         /* leave this lock in place */
1146         tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_SET, F_RDLCK, F_SETLKW);
1147
1148         if (read(tdb.fd, &tdb.header, sizeof(tdb.header)) != sizeof(tdb.header) ||
1149             strcmp(tdb.header.magic_food, TDB_MAGIC_FOOD) != 0 ||
1150             tdb.header.version != TDB_VERSION) {
1151                 /* its not a valid database - possibly initialise it */
1152                 if (!(open_flags & O_CREAT)) {
1153                         goto fail;
1154                 }
1155                 if (tdb_new_database(&tdb, hash_size) == -1) goto fail;
1156
1157                 lseek(tdb.fd, 0, SEEK_SET);
1158                 if (tdb.fd != -1 && read(tdb.fd, &tdb.header,
1159                                          sizeof(tdb.header)) !=
1160                                          sizeof(tdb.header))
1161                     goto fail;
1162         }
1163
1164         if (tdb.fd != -1) {
1165             fstat(tdb.fd, &st);
1166
1167             /* map the database and fill in the return structure */
1168             tdb.name = (char *)strdup(name);
1169             tdb.map_size = st.st_size;
1170         }
1171
1172         tdb.locked = (int *)calloc(tdb.header.hash_size+1,
1173                                    sizeof(tdb.locked[0]));
1174         if (!tdb.locked) {
1175             goto fail;
1176         }
1177
1178 #if HAVE_MMAP
1179         if (tdb.fd != -1) {
1180             tdb.map_ptr = (void *)mmap(NULL, st.st_size,
1181                                        tdb.read_only? PROT_READ : PROT_READ|PROT_WRITE,
1182                                        MAP_SHARED | MAP_FILE, tdb.fd, 0);
1183         }
1184 #endif
1185
1186         ret = (TDB_CONTEXT *)malloc(sizeof(tdb));
1187         if (!ret) goto fail;
1188
1189         *ret = tdb;
1190
1191 #if TDB_DEBUG
1192         printf("mapped database of hash_size %u map_size=%u\n",
1193                hash_size, tdb.map_size);
1194 #endif
1195
1196         tdb_brlock(&tdb, GLOBAL_LOCK, LOCK_CLEAR, F_WRLCK, F_SETLKW);
1197         return ret;
1198
1199  fail:
1200         if (tdb.name) free(tdb.name);
1201         if (tdb.fd != -1) close(tdb.fd);
1202         if (tdb.map_ptr) munmap(tdb.map_ptr, tdb.map_size);
1203
1204         return NULL;
1205 }
1206
1207 /* close a database */
1208 int tdb_close(TDB_CONTEXT *tdb)
1209 {
1210         if (!tdb) return -1;
1211
1212         if (tdb->name) free(tdb->name);
1213         if (tdb->fd != -1) close(tdb->fd);
1214         if (tdb->locked) free(tdb->locked);
1215
1216         if (tdb->map_ptr) {
1217             if (tdb->fd != -1) {
1218                 munmap(tdb->map_ptr, tdb->map_size);
1219             } else {
1220                 free(tdb->map_ptr);
1221             }
1222         }
1223
1224         memset(tdb, 0, sizeof(*tdb));
1225         free(tdb);
1226
1227         return 0;
1228 }
1229
1230 /* lock the database. If we already have it locked then don't do anything */
1231 int tdb_writelock(TDB_CONTEXT *tdb)
1232 {
1233         if (tdb == NULL) {
1234 #ifdef TDB_DEBUG
1235             printf("tdb_writelock() called with null context\n");
1236 #endif
1237             return -1;
1238         }
1239
1240         return tdb_lock(tdb, -1);
1241 }
1242
1243 /* unlock the database. */
1244 int tdb_writeunlock(TDB_CONTEXT *tdb)
1245 {
1246         if (tdb == NULL) {
1247 #ifdef TDB_DEBUG
1248             printf("tdb_writeunlock() called with null context\n");
1249 #endif
1250             return -1;
1251         }
1252
1253         return tdb_unlock(tdb, -1);
1254 }
1255
1256 /* lock one hash chain. This is meant to be used to reduce locking
1257    contention - it cannot guarantee how many records will be locked */
1258 int tdb_lockchain(TDB_CONTEXT *tdb, TDB_DATA key)
1259 {
1260         if (tdb == NULL) {
1261 #ifdef TDB_DEBUG
1262             printf("tdb_lockchain() called with null context\n");
1263 #endif
1264             return -1;
1265         }
1266
1267         return tdb_lock(tdb, BUCKET(tdb_hash(&key)));
1268 }
1269
1270
1271 /* unlock one hash chain */
1272 int tdb_unlockchain(TDB_CONTEXT *tdb, TDB_DATA key)
1273 {
1274         if (tdb == NULL) {
1275 #ifdef TDB_DEBUG
1276             printf("tdb_unlockchain() called with null context\n");
1277 #endif
1278             return -1;
1279         }
1280
1281         return tdb_unlock(tdb, BUCKET(tdb_hash(&key)));
1282 }