source3/tdb/tdb.c

   1 /*
   2    Unix SMB/Netbios implementation.
   3    Version 3.0
   4    Samba database functions
   5    Copyright (C) Andrew Tridgell 1999
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20 */
  21
  22 #if STANDALONE
  23 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <fcntl.h>
  26 #include <unistd.h>
  27 #include <string.h>
  28 #include <fcntl.h>
  29 #include <errno.h>
  30 #include <sys/mman.h>
  31 #include <sys/stat.h>
  32 #include "tdb.h"
  33 #else
  34 #include "includes.h"
  35 #endif
  36
  37 #define TDB_VERSION (0x26011967 + 1)
  38 #define TDB_MAGIC (0x26011999U)
  39 #define TDB_FREE_MAGIC (~TDB_MAGIC)
  40 #define TDB_ALIGN 4
  41 #define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGN)
  42 #define DEFAULT_HASH_SIZE 128
  43 #define TDB_PAGE_SIZE 0x2000
  44 #define TDB_LEN_MULTIPLIER 10
  45 #define FREELIST_TOP (sizeof(struct tdb_header))
  46
  47 #define LOCK_SET 1
  48 #define LOCK_CLEAR 0
  49
  50 /* lock offsets */
  51 #define GLOBAL_LOCK 0
  52 #define ACTIVE_LOCK 4
  53 #define LIST_LOCK_BASE 1024
  54
  55 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
  56
  57 /* the body of the database is made of one list_struct for the free space
  58    plus a separate data list for each hash value */
  59 struct list_struct {
  60         tdb_len rec_len; /* total byte length of record */
  61         tdb_off next; /* offset of the next record in the list */
  62         tdb_len key_len; /* byte length of key */
  63         tdb_len data_len; /* byte length of data */
  64         unsigned full_hash; /* the full 32 bit hash of the key */
  65         unsigned magic;   /* try to catch errors */
  66         /*
  67            the following union is implied
  68            union {
  69               char record[rec_len];
  70               struct {
  71                 char key[key_len];
  72                 char data[data_len];
  73               }
  74            }
  75         */
  76 };
  77
  78 /* a null data record - useful for error returns */
  79 static TDB_DATA null_data;
  80
  81 /* a byte range locking function - return 0 on success
  82    this functions locks/unlocks 1 byte at the specified offset */
  83 static int tdb_brlock(TDB_CONTEXT *tdb, tdb_off offset,
  84                       int set, int rw_type, int lck_type)
  85 {
  86 #if NOLOCK
  87         return 0;
  88 #else
  89         struct flock fl;
  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) 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, 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         lseek(tdb->fd, tdb->map_size + length - 1, SEEK_SET);
 337         if (write(tdb->fd, &b, 1) != 1) goto fail;
 338
 339         /* form a new freelist record */
 340         offset = FREELIST_TOP;
 341         rec.rec_len = length - sizeof(rec);
 342         rec.magic = TDB_FREE_MAGIC;
 343         if (ofs_read(tdb, offset, &rec.next) == -1) {
 344                 goto fail;
 345         }
 346
 347 #if HAVE_MMAP
 348         if (tdb->map_ptr) {
 349                 munmap(tdb->map_ptr, tdb->map_size);
 350                 tdb->map_ptr = NULL;
 351         }
 352 #endif
 353
 354         tdb->map_size += length;
 355
 356         /* write it out */
 357         if (rec_write(tdb, tdb->map_size - length, &rec) == -1) {
 358                 goto fail;
 359         }
 360
 361         /* link it into the free list */
 362         ptr = tdb->map_size - length;
 363         if (ofs_write(tdb, offset, &ptr) == -1) goto fail;
 364
 365 #if HAVE_MMAP
 366         tdb->map_ptr = (void *)mmap(NULL, tdb->map_size,
 367                                    PROT_READ|PROT_WRITE,
 368                                    MAP_SHARED | MAP_FILE, tdb->fd, 0);
 369 #endif
 370         tdb_unlock(tdb, -1);
 371         return 0;
 372
 373  fail:
 374         tdb_unlock(tdb,-1);
 375         return -1;
 376 }
 377
 378 /* allocate some space from the free list. The offset returned points
 379    to a unconnected list_struct within the database with room for at
 380    least length bytes of total data
 381
 382    0 is returned if the space could not be allocated
 383  */
 384 static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length)
 385 {
 386         tdb_off offset, rec_ptr, last_ptr;
 387         struct list_struct rec, lastrec, newrec;
 388
 389         tdb_lock(tdb, -1);
 390
 391  again:
 392         last_ptr = 0;
 393         offset = FREELIST_TOP;
 394
 395         /* read in the freelist top */
 396         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 397                 goto fail;
 398         }
 399
 400         /* keep looking until we find a freelist record that is big
 401            enough */
 402         while (rec_ptr) {
 403                 if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) {
 404                         goto fail;
 405                 }
 406
 407                 if (rec.magic != TDB_FREE_MAGIC) {
 408 #if TDB_DEBUG
 409                         printf("bad magic 0x%08x in free list\n", rec.magic);
 410 #endif
 411                         goto fail;
 412                 }
 413
 414                 if (rec.rec_len >= length) {
 415                         /* found it - now possibly split it up  */
 416                         if (rec.rec_len > length + MIN_REC_SIZE) {
 417                                 length = (length + TDB_ALIGN) & ~(TDB_ALIGN-1);
 418
 419                                 newrec.rec_len = rec.rec_len - (sizeof(rec) + length);
 420                                 newrec.next = rec.next;
 421                                 newrec.magic = TDB_FREE_MAGIC;
 422
 423                                 rec.rec_len = length;
 424                                 rec.next = rec_ptr + sizeof(rec) + rec.rec_len;
 425
 426                                 if (rec_write(tdb, rec.next, &newrec) == -1) {
 427                                         goto fail;
 428                                 }
 429
 430                                 if (rec_write(tdb, rec_ptr, &rec) == -1) {
 431                                         goto fail;
 432                                 }
 433                         }
 434
 435                         /* remove it from the list */
 436                         if (last_ptr == 0) {
 437                                 offset = FREELIST_TOP;
 438
 439                                 if (ofs_write(tdb, offset, &rec.next) == -1) {
 440                                         goto fail;
 441                                 }
 442                         } else {
 443                                 lastrec.next = rec.next;
 444                                 if (rec_write(tdb, last_ptr, &lastrec) == -1) {
 445                                         goto fail;
 446                                 }
 447                         }
 448
 449                         /* all done - return the new record offset */
 450                         tdb_unlock(tdb, -1);
 451                         return rec_ptr;
 452                 }
 453
 454                 /* move to the next record */
 455                 lastrec = rec;
 456                 last_ptr = rec_ptr;
 457                 rec_ptr = rec.next;
 458         }
 459
 460         /* we didn't find enough space. See if we can expand the
 461            database and if we can then try again */
 462         if (tdb_expand(tdb, length + sizeof(rec)) == 0) goto again;
 463
 464  fail:
 465 #if TDB_DEBUG
 466         printf("tdb_allocate failed for size %u\n", length);
 467 #endif
 468         tdb_unlock(tdb, -1);
 469         return 0;
 470 }
 471
 472 /* initialise a new database with a specified hash size */
 473 static int tdb_new_database(TDB_CONTEXT *tdb, int hash_size)
 474 {
 475         struct tdb_header header;
 476         tdb_off offset;
 477         int i;
 478         tdb_off buf[16];
 479
 480         /* create the header */
 481         memset(&header, 0, sizeof(header));
 482         memcpy(header.magic_food, TDB_MAGIC_FOOD, strlen(TDB_MAGIC_FOOD)+1);
 483         header.version = TDB_VERSION;
 484         header.hash_size = hash_size;
 485         lseek(tdb->fd, 0, SEEK_SET);
 486         ftruncate(tdb->fd, 0);
 487
 488         if (write(tdb->fd, &header, sizeof(header)) != sizeof(header)) {
 489                 tdb->ecode = TDB_ERR_IO;
 490                 return -1;
 491         }
 492
 493         /* the freelist and hash pointers */
 494         offset = 0;
 495         memset(buf, 0, sizeof(buf));
 496         for (i=0;(hash_size+1)-i >= 16; i += 16) {
 497                 if (write(tdb->fd, buf, sizeof(buf)) != sizeof(buf)) {
 498                         tdb->ecode = TDB_ERR_IO;
 499                         return -1;
 500                 }
 501         }
 502         for (;i<hash_size+1; i++) {
 503                 if (write(tdb->fd, buf, sizeof(tdb_off)) != sizeof(tdb_off)) {
 504                         tdb->ecode = TDB_ERR_IO;
 505                         return -1;
 506                 }
 507         }
 508
 509 #if TDB_DEBUG
 510         printf("initialised database of hash_size %u\n",
 511                hash_size);
 512 #endif
 513         return 0;
 514 }
 515
 516 /* Returns 0 on fail.  On success, return offset of record, and fills
 517    in rec */
 518 static tdb_off tdb_find(TDB_CONTEXT *tdb, TDB_DATA key, unsigned int hash,
 519                         struct list_struct *rec)
 520 {
 521         tdb_off offset, rec_ptr;
 522
 523         /* find the top of the hash chain */
 524         offset = tdb_hash_top(tdb, hash);
 525
 526         /* read in the hash top */
 527         if (ofs_read(tdb, offset, &rec_ptr) == -1)
 528                 return 0;
 529
 530         /* keep looking until we find the right record */
 531         while (rec_ptr) {
 532                 if (rec_read(tdb, rec_ptr, rec) == -1)
 533                         return 0;
 534
 535                 if (hash == rec->full_hash && key.dsize == rec->key_len) {
 536                         char *k;
 537                         /* a very likely hit - read the key */
 538                         k = tdb_alloc_read(tdb, rec_ptr + sizeof(*rec),
 539                                            rec->key_len);
 540
 541                         if (!k)
 542                                 return 0;
 543
 544                         if (memcmp(key.dptr, k, key.dsize) == 0) {
 545                                 free(k);
 546                                 return rec_ptr;
 547                         }
 548                         free(k);
 549                 }
 550
 551                 /* move to the next record */
 552                 rec_ptr = rec->next;
 553         }
 554         return 0;
 555 }
 556
 557 /*
 558    return an error string for the last tdb error
 559 */
 560 char *tdb_error(TDB_CONTEXT *tdb)
 561 {
 562         int i;
 563         static struct {
 564                 enum TDB_ERROR ecode;
 565                 char *estring;
 566         } emap[] = {
 567                 {TDB_SUCCESS, "Success"},
 568                 {TDB_ERR_CORRUPT, "Corrupt database"},
 569                 {TDB_ERR_IO, "IO Error"},
 570                 {TDB_ERR_LOCK, "Locking error"},
 571                 {TDB_ERR_OOM, "Out of memory"},
 572                 {TDB_ERR_EXISTS, "Record exists"},
 573                 {-1, NULL}};
 574         for (i=0;emap[i].estring;i++) {
 575                 if (tdb->ecode == emap[i].ecode) return emap[i].estring;
 576         }
 577         return "Invalid error code";
 578 }
 579
 580
 581 /* update an entry in place - this only works if the new data size
 582    is <= the old data size and the key exists.
 583    on failure return -1
 584 */
 585 int tdb_update(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)
 586 {
 587         unsigned hash;
 588         struct list_struct rec;
 589         tdb_off rec_ptr;
 590         int ret = -1;
 591
 592         /* find which hash bucket it is in */
 593         hash = tdb_hash(&key);
 594
 595         tdb_lock(tdb, BUCKET(hash));
 596         rec_ptr = tdb_find(tdb, key, hash, &rec);
 597
 598         if (!rec_ptr)
 599                 goto out;
 600
 601         /* must be long enough */
 602         if (rec.rec_len < key.dsize + dbuf.dsize)
 603                 goto out;
 604
 605         if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
 606                       dbuf.dptr, dbuf.dsize) == -1)
 607                 goto out;
 608
 609         if (dbuf.dsize != rec.data_len) {
 610                 /* update size */
 611                 rec.data_len = dbuf.dsize;
 612                 ret = rec_write(tdb, rec_ptr, &rec);
 613         } else
 614                 ret = 0;
 615
 616  out:
 617         tdb_unlock(tdb, BUCKET(hash));
 618         return ret;
 619 }
 620
 621 /* find an entry in the database given a key */
 622 TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key)
 623 {
 624         unsigned hash;
 625         tdb_off rec_ptr;
 626         struct list_struct rec;
 627         TDB_DATA ret = null_data;
 628
 629         /* find which hash bucket it is in */
 630         hash = tdb_hash(&key);
 631
 632         tdb_lock(tdb, BUCKET(hash));
 633         rec_ptr = tdb_find(tdb, key, hash, &rec);
 634
 635         if (rec_ptr) {
 636                 ret.dptr = tdb_alloc_read(tdb,
 637                                           rec_ptr + sizeof(rec) + rec.key_len,
 638                                           rec.data_len);
 639                 ret.dsize = rec.data_len;
 640         }
 641
 642         tdb_unlock(tdb, BUCKET(hash));
 643         return ret;
 644 }
 645
 646 /* check if an entry in the database exists
 647
 648    note that 1 is returned if the key is found and 0 is returned if not found
 649    this doesn't match the conventions in the rest of this module, but is
 650    compatible with gdbm
 651 */
 652 int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key)
 653 {
 654         unsigned hash;
 655         tdb_off rec_ptr;
 656         struct list_struct rec;
 657
 658         /* find which hash bucket it is in */
 659         hash = tdb_hash(&key);
 660
 661         tdb_lock(tdb, BUCKET(hash));
 662         rec_ptr = tdb_find(tdb, key, hash, &rec);
 663         tdb_unlock(tdb, BUCKET(hash));
 664
 665         return rec_ptr != 0;
 666 }
 667
 668 /* traverse the entire database - calling fn(tdb, key, data) on each element.
 669    return -1 on error or the record count traversed
 670    if fn is NULL then it is not called
 671    a non-zero return value from fn() indicates that the traversal should stop
 672   */
 673 int tdb_traverse(TDB_CONTEXT *tdb, int (*fn)(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf))
 674 {
 675         int count = 0;
 676         unsigned h;
 677         tdb_off offset, rec_ptr;
 678         struct list_struct rec;
 679         char *data;
 680         TDB_DATA key, dbuf;
 681
 682         /* loop over all hash chains */
 683         for (h = 0; h < tdb->header.hash_size; h++) {
 684                 tdb_lock(tdb, BUCKET(h));
 685
 686                 /* read in the hash top */
 687                 offset = tdb_hash_top(tdb, h);
 688                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 689                         goto fail;
 690                 }
 691
 692                 /* traverse all records for this hash */
 693                 while (rec_ptr) {
 694                         if (rec_read(tdb, rec_ptr, &rec) == -1) {
 695                                 goto fail;
 696                         }
 697
 698                         /* now read the full record */
 699                         data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec),
 700                                              rec.key_len + rec.data_len);
 701                         if (!data) {
 702                                 goto fail;
 703                         }
 704
 705                         key.dptr = data;
 706                         key.dsize = rec.key_len;
 707                         dbuf.dptr = data + rec.key_len;
 708                         dbuf.dsize = rec.data_len;
 709                         count++;
 710
 711                         if (fn && fn(tdb, key, dbuf) != 0) {
 712                                 /* they want us to stop traversing */
 713                                 free(data);
 714                                 tdb_unlock(tdb, BUCKET(h));
 715                                 return count;
 716                         }
 717
 718                         /* a miss - drat */
 719                         free(data);
 720
 721                         /* move to the next record */
 722                         rec_ptr = rec.next;
 723                 }
 724                 tdb_unlock(tdb, BUCKET(h));
 725         }
 726
 727         /* return the number traversed */
 728         return count;
 729
 730  fail:
 731         tdb_unlock(tdb, BUCKET(h));
 732         return -1;
 733 }
 734
 735
 736 /* find the first entry in the database and return its key */
 737 TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb)
 738 {
 739         tdb_off offset, rec_ptr;
 740         struct list_struct rec;
 741         unsigned hash;
 742         TDB_DATA ret;
 743
 744         /* look for a non-empty hash chain */
 745         for (hash = 0, rec_ptr = 0;
 746              hash < tdb->header.hash_size;
 747              hash++) {
 748                 /* find the top of the hash chain */
 749                 offset = tdb_hash_top(tdb, hash);
 750
 751                 tdb_lock(tdb, BUCKET(hash));
 752
 753                 /* read in the hash top */
 754                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 755                         goto fail;
 756                 }
 757
 758                 if (rec_ptr) break;
 759
 760                 tdb_unlock(tdb, BUCKET(hash));
 761         }
 762
 763         if (rec_ptr == 0) return null_data;
 764
 765         /* we've found a non-empty chain, now read the record */
 766         if (rec_read(tdb, rec_ptr, &rec) == -1) {
 767                 goto fail;
 768         }
 769
 770         /* allocate and read the key space */
 771         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len);
 772         ret.dsize = rec.key_len;
 773         tdb_unlock(tdb, BUCKET(hash));
 774         return ret;
 775
 776  fail:
 777         tdb_unlock(tdb, BUCKET(hash));
 778         return null_data;
 779 }
 780
 781 /* find the next entry in the database, returning its key */
 782 TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA key)
 783 {
 784         unsigned hash, hbucket;
 785         tdb_off rec_ptr, offset;
 786         struct list_struct rec;
 787         TDB_DATA ret;
 788
 789         /* find which hash bucket it is in */
 790         hash = tdb_hash(&key);
 791         hbucket = BUCKET(hash);
 792
 793         tdb_lock(tdb, hbucket);
 794         rec_ptr = tdb_find(tdb, key, hash, &rec);
 795         if (rec_ptr) {
 796                 /* we want the next record after this one */
 797                 rec_ptr = rec.next;
 798         }
 799
 800         /* not found or last in hash: look for next non-empty hash chain */
 801         while (rec_ptr == 0) {
 802                 tdb_unlock(tdb, hbucket);
 803
 804                 if (++hbucket >= tdb->header.hash_size - 1)
 805                         return null_data;
 806
 807                 offset = tdb_hash_top(tdb, hbucket);
 808                 tdb_lock(tdb, hbucket);
 809                 /* read in the hash top */
 810                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 811                         tdb_unlock(tdb, hbucket);
 812                         return null_data;
 813                 }
 814         }
 815
 816         /* Read the record. */
 817         if (rec_read(tdb, rec_ptr, &rec) == 0) {
 818                 tdb_unlock(tdb, hbucket);
 819                 return null_data;
 820         }
 821         /* allocate and read the key */
 822         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len);
 823         ret.dsize = rec.key_len;
 824         tdb_unlock(tdb, hbucket);
 825
 826         return ret;
 827 }
 828
 829 /* delete an entry in the database given a key */
 830 int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key)
 831 {
 832         unsigned hash;
 833         tdb_off offset, rec_ptr, last_ptr;
 834         struct list_struct rec, lastrec;
 835         char *data = NULL;
 836
 837         /* find which hash bucket it is in */
 838         hash = tdb_hash(&key);
 839
 840         tdb_lock(tdb, BUCKET(hash));
 841
 842         /* find the top of the hash chain */
 843         offset = tdb_hash_top(tdb, hash);
 844
 845         /* read in the hash top */
 846         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 847                 goto fail;
 848         }
 849
 850         last_ptr = 0;
 851
 852         /* keep looking until we find the right record */
 853         while (rec_ptr) {
 854                 if (rec_read(tdb, rec_ptr, &rec) == -1) {
 855                         goto fail;
 856                 }
 857
 858                 if (hash == rec.full_hash && key.dsize == rec.key_len) {
 859                         /* a very likely hit - read the record and full key */
 860                         data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec),
 861                                              rec.key_len);
 862                         if (!data) {
 863                                 goto fail;
 864                         }
 865
 866                         if (memcmp(key.dptr, data, key.dsize) == 0) {
 867                                 /* a definite match - delete it */
 868                                 if (last_ptr == 0) {
 869                                         offset = tdb_hash_top(tdb, hash);
 870                                         if (ofs_write(tdb, offset, &rec.next) == -1) {
 871                                                 goto fail;
 872                                         }
 873                                 } else {
 874                                         lastrec.next = rec.next;
 875                                         if (rec_write(tdb, last_ptr, &lastrec) == -1) {
 876                                                 goto fail;
 877                                         }
 878                                 }
 879                                 tdb_unlock(tdb, BUCKET(hash));
 880                                 tdb_lock(tdb, -1);
 881                                 /* and recover the space */
 882                                 offset = FREELIST_TOP;
 883                                 if (ofs_read(tdb, offset, &rec.next) == -1) {
 884                                         goto fail2;
 885                                 }
 886                                 rec.magic = TDB_FREE_MAGIC;
 887                                 if (rec_write(tdb, rec_ptr, &rec) == -1) {
 888                                         goto fail2;
 889                                 }
 890                                 if (ofs_write(tdb, offset, &rec_ptr) == -1) {
 891                                         goto fail2;
 892                                 }
 893
 894                                 /* yipee - all done */
 895                                 free(data);
 896                                 tdb_unlock(tdb, -1);
 897                                 return 0;
 898                         }
 899
 900                         /* a miss - drat */
 901                         free(data);
 902                         data = NULL;
 903                 }
 904
 905                 /* move to the next record */
 906                 last_ptr = rec_ptr;
 907                 lastrec = rec;
 908                 rec_ptr = rec.next;
 909         }
 910
 911  fail:
 912         if (data) free(data);
 913         tdb_unlock(tdb, BUCKET(hash));
 914         return -1;
 915
 916  fail2:
 917         if (data) free(data);
 918         tdb_unlock(tdb, -1);
 919         return -1;
 920 }
 921
 922
 923 /* store an element in the database, replacing any existing element
 924    with the same key
 925
 926    return 0 on success, -1 on failure
 927 */
 928 int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
 929 {
 930         struct list_struct rec;
 931         unsigned hash;
 932         tdb_off rec_ptr, offset;
 933         char *p = NULL;
 934
 935         /* find which hash bucket it is in */
 936         hash = tdb_hash(&key);
 937
 938         /* check for it existing */
 939         if (flag == TDB_INSERT && tdb_exists(tdb, key)) {
 940                 tdb->ecode = TDB_ERR_EXISTS;
 941                 return -1;
 942         }
 943
 944         /* first try in-place update */
 945         if (flag != TDB_INSERT && tdb_update(tdb, key, dbuf) == 0) {
 946                 return 0;
 947         }
 948
 949         rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize);
 950         if (rec_ptr == 0) {
 951                 return -1;
 952         }
 953
 954         tdb_lock(tdb, BUCKET(hash));
 955
 956         /* delete any existing record - if it doesn't exist we don't care */
 957         if (flag != TDB_INSERT) {
 958                 tdb_delete(tdb, key);
 959         }
 960
 961         /* read the newly created record */
 962         if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) {
 963                 goto fail;
 964         }
 965
 966         if (rec.magic != TDB_FREE_MAGIC) goto fail;
 967
 968         /* find the top of the hash chain */
 969         offset = tdb_hash_top(tdb, hash);
 970
 971         /* read in the hash top diretcly into our next pointer */
 972         if (ofs_read(tdb, offset, &rec.next) == -1) {
 973                 goto fail;
 974         }
 975
 976         rec.key_len = key.dsize;
 977         rec.data_len = dbuf.dsize;
 978         rec.full_hash = hash;
 979         rec.magic = TDB_MAGIC;
 980
 981         p = (char *)malloc(sizeof(rec) + key.dsize + dbuf.dsize);
 982         if (!p) {
 983                 tdb->ecode = TDB_ERR_OOM;
 984                 goto fail;
 985         }
 986
 987         memcpy(p, &rec, sizeof(rec));
 988         memcpy(p+sizeof(rec), key.dptr, key.dsize);
 989         memcpy(p+sizeof(rec)+key.dsize, dbuf.dptr, dbuf.dsize);
 990
 991         if (tdb_write(tdb, rec_ptr, p, sizeof(rec)+key.dsize+dbuf.dsize) == -1)
 992                 goto fail;
 993
 994         free(p);
 995         p = NULL;
 996
 997         /* and point the top of the hash chain at it */
 998         if (ofs_write(tdb, offset, &rec_ptr) == -1) goto fail;
 999
1000         tdb_unlock(tdb, BUCKET(hash));
1001         return 0;
1002
1003  fail:
1004 #if TDB_DEBUG
1005         printf("store failed for hash 0x%08x in bucket %u\n", hash, BUCKET(hash));
1006 #endif
1007         if (p) free(p);
1008         tdb_unlock(tdb, BUCKET(hash));
1009         return -1;
1010 }
1011
1012
1013 /* open the database, creating it if necessary
1014
1015    The open_flags and mode are passed straight to the open call on the database
1016    file. A flags value of O_WRONLY is invalid
1017
1018    The hash size is advisory, use zero for a default value.
1019
1020    return is NULL on error
1021 */
1022 TDB_CONTEXT *tdb_open(char *name, int hash_size, int tdb_flags,
1023                       int open_flags, mode_t mode)
1024 {
1025         TDB_CONTEXT tdb, *ret;
1026         struct stat st;
1027
1028         tdb.fd = -1;
1029         tdb.name = NULL;
1030         tdb.map_ptr = NULL;
1031
1032         if ((open_flags & O_ACCMODE) == O_WRONLY) {
1033                 goto fail;
1034         }
1035
1036         if (hash_size == 0) hash_size = DEFAULT_HASH_SIZE;
1037
1038         memset(&tdb, 0, sizeof(tdb));
1039
1040         tdb.read_only = ((open_flags & O_ACCMODE) == O_RDONLY);
1041
1042         tdb.fd = open(name, open_flags, mode);
1043         if (tdb.fd == -1) {
1044                 goto fail;
1045         }
1046
1047         /* ensure there is only one process initialising at once */
1048         tdb_brlock(&tdb, GLOBAL_LOCK, LOCK_SET, F_WRLCK, F_SETLKW);
1049
1050         if (tdb_flags & TDB_CLEAR_IF_FIRST) {
1051                 /* we need to zero the database if we are the only
1052                    one with it open */
1053                 if (tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_SET, F_WRLCK, F_SETLK) == 0) {
1054                         ftruncate(tdb.fd, 0);
1055                         tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_CLEAR, F_WRLCK, F_SETLK);
1056                 }
1057         }
1058
1059         /* leave this lock in place */
1060         tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_SET, F_RDLCK, F_SETLKW);
1061
1062         if (read(tdb.fd, &tdb.header, sizeof(tdb.header)) != sizeof(tdb.header) ||
1063             strcmp(tdb.header.magic_food, TDB_MAGIC_FOOD) != 0 ||
1064             tdb.header.version != TDB_VERSION) {
1065                 /* its not a valid database - possibly initialise it */
1066                 if (!(open_flags & O_CREAT)) {
1067                         goto fail;
1068                 }
1069                 if (tdb_new_database(&tdb, hash_size) == -1) goto fail;
1070
1071                 lseek(tdb.fd, 0, SEEK_SET);
1072                 if (read(tdb.fd, &tdb.header, sizeof(tdb.header)) != sizeof(tdb.header)) goto fail;
1073         }
1074
1075         fstat(tdb.fd, &st);
1076
1077         /* map the database and fill in the return structure */
1078         tdb.name = (char *)strdup(name);
1079         tdb.locked = (int *)calloc(tdb.header.hash_size+1,
1080                                    sizeof(tdb.locked[0]));
1081         if (!tdb.locked) {
1082                 goto fail;
1083         }
1084         tdb.map_size = st.st_size;
1085 #if HAVE_MMAP
1086         tdb.map_ptr = (void *)mmap(NULL, st.st_size,
1087                                   tdb.read_only? PROT_READ : PROT_READ|PROT_WRITE,
1088                                   MAP_SHARED | MAP_FILE, tdb.fd, 0);
1089 #endif
1090
1091         ret = (TDB_CONTEXT *)malloc(sizeof(tdb));
1092         if (!ret) goto fail;
1093
1094         *ret = tdb;
1095
1096 #if TDB_DEBUG
1097         printf("mapped database of hash_size %u map_size=%u\n",
1098                hash_size, tdb.map_size);
1099 #endif
1100
1101         tdb_brlock(&tdb, GLOBAL_LOCK, LOCK_CLEAR, F_WRLCK, F_SETLKW);
1102         return ret;
1103
1104  fail:
1105         if (tdb.name) free(tdb.name);
1106         if (tdb.fd != -1) close(tdb.fd);
1107         if (tdb.map_ptr) munmap(tdb.map_ptr, tdb.map_size);
1108
1109         return NULL;
1110 }
1111
1112 /* close a database */
1113 int tdb_close(TDB_CONTEXT *tdb)
1114 {
1115         if (!tdb) return -1;
1116
1117         if (tdb->name) free(tdb->name);
1118         if (tdb->fd != -1) close(tdb->fd);
1119         if (tdb->map_ptr) munmap(tdb->map_ptr, tdb->map_size);
1120         if (tdb->locked) free(tdb->locked);
1121
1122         memset(tdb, 0, sizeof(*tdb));
1123         free(tdb);
1124
1125         return 0;
1126 }
1127
1128 /* lock the database. If we already have it locked then don't do anything */
1129 int tdb_writelock(TDB_CONTEXT *tdb)
1130 {
1131         return tdb_lock(tdb, -1);
1132 }
1133
1134 /* unlock the database. */
1135 int tdb_writeunlock(TDB_CONTEXT *tdb)
1136 {
1137         return tdb_unlock(tdb, -1);
1138 }
1139
1140 /* lock one hash chain. This is meant to be used to reduce locking
1141    contention - it cannot guarantee how many records will be locked */
1142 int tdb_lockchain(TDB_CONTEXT *tdb, TDB_DATA key)
1143 {
1144         return tdb_lock(tdb, BUCKET(tdb_hash(&key)));
1145 }
1146
1147
1148 /* unlock one hash chain */
1149 int tdb_unlockchain(TDB_CONTEXT *tdb, TDB_DATA key)
1150 {
1151         return tdb_unlock(tdb, BUCKET(tdb_hash(&key)));
1152 }