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