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