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