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