source3/tdb/tdb.c

   1  /*
   2    Unix SMB/Netbios implementation.
   3    Version 3.0
   4    Samba database functions
   5    Copyright (C) Andrew Tridgell              1999-2000
   6    Copyright (C) Luke Kenneth Casson Leighton      2000
   7    Copyright (C) Paul `Rusty' Russell              2000
   8    Copyright (C) Jeremy Allison                    2000
   9
  10    This program is free software; you can redistribute it and/or modify
  11    it under the terms of the GNU General Public License as published by
  12    the Free Software Foundation; either version 2 of the License, or
  13    (at your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18    GNU General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  23 */
  24 #ifdef STANDALONE
  25 #if HAVE_CONFIG_H
  26 #include <config.h>
  27 #endif
  28
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31 #include <fcntl.h>
  32 #include <unistd.h>
  33 #include <string.h>
  34 #include <fcntl.h>
  35 #include <errno.h>
  36 #include <sys/mman.h>
  37 #include <sys/stat.h>
  38 #include "tdb.h"
  39 #include "spinlock.h"
  40 #else
  41 #include "includes.h"
  42 #endif
  43
  44 #define TDB_MAGIC_FOOD "TDB file\n"
  45 #define TDB_VERSION (0x26011967 + 6)
  46 #define TDB_MAGIC (0x26011999U)
  47 #define TDB_FREE_MAGIC (~TDB_MAGIC)
  48 #define TDB_DEAD_MAGIC (0xFEE1DEAD)
  49 #define TDB_ALIGNMENT 4
  50 #define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGNMENT)
  51 #define DEFAULT_HASH_SIZE 131
  52 #define TDB_PAGE_SIZE 0x2000
  53 #define FREELIST_TOP (sizeof(struct tdb_header))
  54 #define TDB_ALIGN(x,a) (((x) + (a)-1) & ~((a)-1))
  55 #define TDB_BYTEREV(x) (((((x)&0xff)<<24)|((x)&0xFF00)<<8)|(((x)>>8)&0xFF00)|((x)>>24))
  56 #define TDB_DEAD(r) ((r)->magic == TDB_DEAD_MAGIC)
  57 #define TDB_BAD_MAGIC(r) ((r)->magic != TDB_MAGIC && !TDB_DEAD(r))
  58 #define TDB_HASH_TOP(hash) (FREELIST_TOP + (BUCKET(hash)+1)*sizeof(tdb_off))
  59 #define TDB_LOG(x) (tdb->log_fn?((tdb->log_fn x),0) : 0)
  60
  61 /* lock offsets */
  62 #define GLOBAL_LOCK 0
  63 #define ACTIVE_LOCK 4
  64
  65 #ifndef MAP_FILE
  66 #define MAP_FILE 0
  67 #endif
  68
  69 #ifndef MAP_FAILED
  70 #define MAP_FAILED ((void *)-1)
  71 #endif
  72
  73 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
  74 TDB_DATA tdb_null;
  75
  76 /* all contexts, to ensure no double-opens (fcntl locks don't nest!) */
  77 static TDB_CONTEXT *tdbs = NULL;
  78
  79 static void tdb_munmap(TDB_CONTEXT *tdb)
  80 {
  81         if (tdb->flags & TDB_INTERNAL)
  82                 return;
  83
  84 #ifdef HAVE_MMAP
  85         if (tdb->map_ptr)
  86                 munmap(tdb->map_ptr, tdb->map_size);
  87 #endif
  88         tdb->map_ptr = NULL;
  89 }
  90
  91 static void tdb_mmap(TDB_CONTEXT *tdb)
  92 {
  93         if (tdb->flags & TDB_INTERNAL)
  94                 return;
  95
  96 #ifdef HAVE_MMAP
  97         if (!(tdb->flags & TDB_NOMMAP)) {
  98                 tdb->map_ptr = mmap(NULL, tdb->map_size,
  99                                     PROT_READ|(tdb->read_only? 0:PROT_WRITE),
 100                                     MAP_SHARED|MAP_FILE, tdb->fd, 0);
 101
 102                 /*
 103                  * NB. When mmap fails it returns MAP_FAILED *NOT* NULL !!!!
 104                  */
 105
 106                 if (tdb->map_ptr == MAP_FAILED) {
 107                         tdb->map_ptr = NULL;
 108                         TDB_LOG((tdb, 2, "tdb_mmap failed for size %d (%s)\n",
 109                                  tdb->map_size, strerror(errno)));
 110                 }
 111         } else {
 112                 tdb->map_ptr = NULL;
 113         }
 114 #else
 115         tdb->map_ptr = NULL;
 116 #endif
 117 }
 118
 119 /* Endian conversion: we only ever deal with 4 byte quantities */
 120 static void *convert(void *buf, u32 size)
 121 {
 122         u32 i, *p = buf;
 123         for (i = 0; i < size / 4; i++)
 124                 p[i] = TDB_BYTEREV(p[i]);
 125         return buf;
 126 }
 127 #define DOCONV() (tdb->flags & TDB_CONVERT)
 128 #define CONVERT(x) (DOCONV() ? convert(&x, sizeof(x)) : &x)
 129
 130 /* the body of the database is made of one list_struct for the free space
 131    plus a separate data list for each hash value */
 132 struct list_struct {
 133         tdb_off next; /* offset of the next record in the list */
 134         tdb_len rec_len; /* total byte length of record */
 135         tdb_len key_len; /* byte length of key */
 136         tdb_len data_len; /* byte length of data */
 137         u32 full_hash; /* the full 32 bit hash of the key */
 138         u32 magic;   /* try to catch errors */
 139         /* the following union is implied:
 140                 union {
 141                         char record[rec_len];
 142                         struct {
 143                                 char key[key_len];
 144                                 char data[data_len];
 145                         }
 146                         u32 totalsize; (tailer)
 147                 }
 148         */
 149 };
 150
 151 /* a byte range locking function - return 0 on success
 152    this functions locks/unlocks 1 byte at the specified offset.
 153
 154    On error, errno is also set so that errors are passed back properly
 155    through tdb_open(). */
 156 static int tdb_brlock(TDB_CONTEXT *tdb, tdb_off offset,
 157                       int rw_type, int lck_type, int probe)
 158 {
 159         struct flock fl;
 160
 161         if (tdb->flags & TDB_NOLOCK)
 162                 return 0;
 163         if (tdb->read_only) {
 164                 errno = EACCES;
 165                 return -1;
 166         }
 167
 168         fl.l_type = rw_type;
 169         fl.l_whence = SEEK_SET;
 170         fl.l_start = offset;
 171         fl.l_len = 1;
 172         fl.l_pid = 0;
 173
 174         if (fcntl(tdb->fd,lck_type,&fl)) {
 175                 if (!probe) {
 176                         TDB_LOG((tdb, 5,"tdb_brlock failed at offset %d rw_type=%d lck_type=%d\n",
 177                                  offset, rw_type, lck_type));
 178                 }
 179                 /* errno set by fcntl */
 180                 return TDB_ERRCODE(TDB_ERR_LOCK, -1);
 181         }
 182         return 0;
 183 }
 184
 185 /* lock a list in the database. list -1 is the alloc list */
 186 static int tdb_lock(TDB_CONTEXT *tdb, int list, int ltype)
 187 {
 188         if (list < -1 || list >= (int)tdb->header.hash_size) {
 189                 TDB_LOG((tdb, 0,"tdb_lock: invalid list %d for ltype=%d\n",
 190                            list, ltype));
 191                 return -1;
 192         }
 193         if (tdb->flags & TDB_NOLOCK)
 194                 return 0;
 195
 196         /* Since fcntl locks don't nest, we do a lock for the first one,
 197            and simply bump the count for future ones */
 198         if (tdb->locked[list+1].count == 0) {
 199                 if (!tdb->read_only && tdb->header.rwlocks) {
 200                         if (tdb_spinlock(tdb, list, ltype)) {
 201                                 TDB_LOG((tdb, 0, "tdb_lock spinlock on list ltype=%d\n",
 202                                            list, ltype));
 203                                 return -1;
 204                         }
 205                 } else if (tdb_brlock(tdb,FREELIST_TOP+4*list,ltype,F_SETLKW, 0)) {
 206                         TDB_LOG((tdb, 0,"tdb_lock failed on list %d ltype=%d (%s)\n",
 207                                            list, ltype, strerror(errno)));
 208                         return -1;
 209                 }
 210                 tdb->locked[list+1].ltype = ltype;
 211         }
 212         tdb->locked[list+1].count++;
 213         return 0;
 214 }
 215
 216 /* unlock the database: returns void because it's too late for errors. */
 217 static void tdb_unlock(TDB_CONTEXT *tdb, int list, int ltype)
 218 {
 219         if (tdb->flags & TDB_NOLOCK)
 220                 return;
 221
 222         /* Sanity checks */
 223         if (list < -1 || list >= (int)tdb->header.hash_size)
 224                 return;
 225         if (tdb->locked[list+1].count==0)
 226                 return;
 227
 228         if (tdb->locked[list+1].count == 1) {
 229                 /* Down to last nested lock: unlock underneath */
 230                 if (!tdb->read_only && tdb->header.rwlocks)
 231                         tdb_spinunlock(tdb, list, ltype);
 232                 else
 233                         tdb_brlock(tdb, FREELIST_TOP+4*list, F_UNLCK, F_SETLKW, 0);
 234         }
 235         tdb->locked[list+1].count--;
 236 }
 237
 238 /* This is based on the hash agorithm from gdbm */
 239 static u32 tdb_hash(TDB_DATA *key)
 240 {
 241         u32 value;      /* Used to compute the hash value.  */
 242         u32   i;        /* Used to cycle through random values. */
 243
 244         /* Set the initial value from the key size. */
 245         for (value = 0x238F13AF * key->dsize, i=0; i < key->dsize; i++)
 246                 value = (value + (key->dptr[i] << (i*5 % 24)));
 247
 248         return (1103515243 * value + 12345);
 249 }
 250
 251 /* check for an out of bounds access - if it is out of bounds then
 252    see if the database has been expanded by someone else and expand
 253    if necessary
 254    note that "len" is the minimum length needed for the db
 255 */
 256 static int tdb_oob(TDB_CONTEXT *tdb, tdb_off len, int probe)
 257 {
 258         struct stat st;
 259         if (len <= tdb->map_size)
 260                 return 0;
 261         if (tdb->flags & TDB_INTERNAL) {
 262                 if (!probe) {
 263                         TDB_LOG((tdb, 0,"tdb_oob len %d beyond internal malloc size %d\n",
 264                                  (int)len, (int)tdb->map_size));
 265                 }
 266                 return TDB_ERRCODE(TDB_ERR_IO, -1);
 267         }
 268
 269         if (fstat(tdb->fd, &st) == -1)
 270                 return TDB_ERRCODE(TDB_ERR_IO, -1);
 271
 272         if (st.st_size < (size_t)len) {
 273                 if (!probe) {
 274                         TDB_LOG((tdb, 0,"tdb_oob len %d beyond eof at %d\n",
 275                                  (int)len, (int)st.st_size));
 276                 }
 277                 return TDB_ERRCODE(TDB_ERR_IO, -1);
 278         }
 279
 280         /* Unmap, update size, remap */
 281         tdb_munmap(tdb);
 282         tdb->map_size = st.st_size;
 283         tdb_mmap(tdb);
 284         return 0;
 285 }
 286
 287 /* write a lump of data at a specified offset */
 288 static int tdb_write(TDB_CONTEXT *tdb, tdb_off off, void *buf, tdb_len len)
 289 {
 290         if (tdb_oob(tdb, off + len, 0) != 0)
 291                 return -1;
 292
 293         if (tdb->map_ptr)
 294                 memcpy(off + (char *)tdb->map_ptr, buf, len);
 295 #ifdef HAVE_PWRITE
 296         else if (pwrite(tdb->fd, buf, len, off) != (ssize_t)len) {
 297 #else
 298         else if (lseek(tdb->fd, off, SEEK_SET) != off
 299                  || write(tdb->fd, buf, len) != (ssize_t)len) {
 300 #endif
 301                 TDB_LOG((tdb, 0,"tdb_write failed at %d len=%d (%s)\n",
 302                            off, len, strerror(errno)));
 303                 return TDB_ERRCODE(TDB_ERR_IO, -1);
 304         }
 305         return 0;
 306 }
 307
 308 /* read a lump of data at a specified offset, maybe convert */
 309 static int tdb_read(TDB_CONTEXT *tdb,tdb_off off,void *buf,tdb_len len,int cv)
 310 {
 311         if (tdb_oob(tdb, off + len, 0) != 0)
 312                 return -1;
 313
 314         if (tdb->map_ptr)
 315                 memcpy(buf, off + (char *)tdb->map_ptr, len);
 316 #ifdef HAVE_PREAD
 317         else if (pread(tdb->fd, buf, len, off) != (ssize_t)len) {
 318 #else
 319         else if (lseek(tdb->fd, off, SEEK_SET) != off
 320                  || read(tdb->fd, buf, len) != (ssize_t)len) {
 321 #endif
 322                 TDB_LOG((tdb, 0,"tdb_read failed at %d len=%d (%s)\n",
 323                            off, len, strerror(errno)));
 324                 return TDB_ERRCODE(TDB_ERR_IO, -1);
 325         }
 326         if (cv)
 327                 convert(buf, len);
 328         return 0;
 329 }
 330
 331 /* read a lump of data, allocating the space for it */
 332 static char *tdb_alloc_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_len len)
 333 {
 334         char *buf;
 335
 336         if (!(buf = malloc(len))) {
 337                 TDB_LOG((tdb, 0,"tdb_alloc_read malloc failed len=%d (%s)\n",
 338                            len, strerror(errno)));
 339                 return TDB_ERRCODE(TDB_ERR_OOM, buf);
 340         }
 341         if (tdb_read(tdb, offset, buf, len, 0) == -1) {
 342                 free(buf);
 343                 return NULL;
 344         }
 345         return buf;
 346 }
 347
 348 /* read/write a tdb_off */
 349 static int ofs_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
 350 {
 351         return tdb_read(tdb, offset, (char*)d, sizeof(*d), DOCONV());
 352 }
 353 static int ofs_write(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
 354 {
 355         tdb_off off = *d;
 356         return tdb_write(tdb, offset, CONVERT(off), sizeof(*d));
 357 }
 358
 359 /* read/write a record */
 360 static int rec_read(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
 361 {
 362         if (tdb_read(tdb, offset, rec, sizeof(*rec),DOCONV()) == -1)
 363                 return -1;
 364         if (TDB_BAD_MAGIC(rec)) {
 365                 TDB_LOG((tdb, 0,"rec_read bad magic 0x%x at offset=%d\n", rec->magic, offset));
 366                 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
 367         }
 368         return tdb_oob(tdb, rec->next+sizeof(*rec), 0);
 369 }
 370 static int rec_write(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
 371 {
 372         struct list_struct r = *rec;
 373         return tdb_write(tdb, offset, CONVERT(r), sizeof(r));
 374 }
 375
 376 /* read a freelist record and check for simple errors */
 377 static int rec_free_read(TDB_CONTEXT *tdb, tdb_off off, struct list_struct *rec)
 378 {
 379         if (tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
 380                 return -1;
 381         if (rec->magic != TDB_FREE_MAGIC) {
 382                 TDB_LOG((tdb, 0,"rec_free_read bad magic 0x%x at offset=%d\n",
 383                            rec->magic, off));
 384                 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
 385         }
 386         if (tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0)
 387                 return -1;
 388         return 0;
 389 }
 390
 391 /* update a record tailer (must hold allocation lock) */
 392 static int update_tailer(TDB_CONTEXT *tdb, tdb_off offset,
 393                          const struct list_struct *rec)
 394 {
 395         tdb_off totalsize;
 396
 397         /* Offset of tailer from record header */
 398         totalsize = sizeof(*rec) + rec->rec_len;
 399         return ofs_write(tdb, offset + totalsize - sizeof(tdb_off),
 400                          &totalsize);
 401 }
 402
 403 static tdb_off tdb_dump_record(TDB_CONTEXT *tdb, tdb_off offset)
 404 {
 405         struct list_struct rec;
 406         tdb_off tailer_ofs, tailer;
 407
 408         if (tdb_read(tdb, offset, (char *)&rec, sizeof(rec), DOCONV()) == -1) {
 409                 printf("ERROR: failed to read record at %u\n", offset);
 410                 return 0;
 411         }
 412
 413         printf(" rec: offset=%u next=%d rec_len=%d key_len=%d data_len=%d full_hash=0x%x magic=0x%x\n",
 414                offset, rec.next, rec.rec_len, rec.key_len, rec.data_len, rec.full_hash, rec.magic);
 415
 416         tailer_ofs = offset + sizeof(rec) + rec.rec_len - sizeof(tdb_off);
 417         if (ofs_read(tdb, tailer_ofs, &tailer) == -1) {
 418                 printf("ERROR: failed to read tailer at %u\n", tailer_ofs);
 419                 return rec.next;
 420         }
 421
 422         if (tailer != rec.rec_len + sizeof(rec)) {
 423                 printf("ERROR: tailer does not match record! tailer=%u totalsize=%u\n", tailer, rec.rec_len + sizeof(rec));
 424         }
 425         return rec.next;
 426 }
 427
 428 static void tdb_dump_chain(TDB_CONTEXT *tdb, int i)
 429 {
 430         tdb_off rec_ptr, top;
 431
 432         top = TDB_HASH_TOP(i);
 433
 434         tdb_lock(tdb, i, F_WRLCK);
 435
 436         if (ofs_read(tdb, top, &rec_ptr) == -1) {
 437                 tdb_unlock(tdb, i, F_WRLCK);
 438                 return;
 439         }
 440
 441         if (rec_ptr)
 442                 printf("hash=%d\n", i);
 443
 444         while (rec_ptr) {
 445                 rec_ptr = tdb_dump_record(tdb, rec_ptr);
 446         }
 447         tdb_unlock(tdb, i, F_WRLCK);
 448 }
 449
 450 void tdb_dump_all(TDB_CONTEXT *tdb)
 451 {
 452         int i;
 453         for (i=0;i<tdb->header.hash_size;i++) {
 454                 tdb_dump_chain(tdb, i);
 455         }
 456         printf("freelist:\n");
 457         tdb_dump_chain(tdb, -1);
 458 }
 459
 460 void tdb_printfreelist(TDB_CONTEXT *tdb)
 461 {
 462         long total_free = 0;
 463         tdb_off offset, rec_ptr, last_ptr;
 464         struct list_struct rec;
 465
 466         tdb_lock(tdb, -1, F_WRLCK);
 467
 468         last_ptr = 0;
 469         offset = FREELIST_TOP;
 470
 471         /* read in the freelist top */
 472         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
 473                 return;
 474         }
 475
 476         printf("freelist top=[0x%08x]\n", rec_ptr );
 477         while (rec_ptr) {
 478                 if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec), DOCONV()) == -1) {
 479                         return;
 480                 }
 481
 482                 if (rec.magic != TDB_FREE_MAGIC) {
 483                         printf("bad magic 0x%08x in free list\n", rec.magic);
 484                         return;
 485                 }
 486
 487                 printf("entry offset=[0x%08x], rec.rec_len = [0x%08x (%d)]\n", rec.next, rec.rec_len, rec.rec_len );
 488                 total_free += rec.rec_len;
 489
 490                 /* move to the next record */
 491                 rec_ptr = rec.next;
 492         }
 493         printf("total rec_len = [0x%08x (%d)]\n", (int)total_free,
 494                (int)total_free);
 495
 496         tdb_unlock(tdb, -1, F_WRLCK);
 497 }
 498
 499 /* Remove an element from the freelist.  Must have alloc lock. */
 500 static int remove_from_freelist(TDB_CONTEXT *tdb, tdb_off off, tdb_off next)
 501 {
 502         tdb_off last_ptr, i;
 503
 504         /* read in the freelist top */
 505         last_ptr = FREELIST_TOP;
 506         while (ofs_read(tdb, last_ptr, &i) != -1 && i != 0) {
 507                 if (i == off) {
 508                         /* We've found it! */
 509                         return ofs_write(tdb, last_ptr, &next);
 510                 }
 511                 /* Follow chain (next offset is at start of record) */
 512                 last_ptr = i;
 513         }
 514         TDB_LOG((tdb, 0,"remove_from_freelist: not on list at off=%d\n", off));
 515         return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
 516 }
 517
 518 /* Add an element into the freelist. Merge adjacent records if
 519    neccessary. */
 520 static int tdb_free(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
 521 {
 522         tdb_off right, left;
 523
 524         /* Allocation and tailer lock */
 525         if (tdb_lock(tdb, -1, F_WRLCK) != 0)
 526                 return -1;
 527
 528         /* set an initial tailer, so if we fail we don't leave a bogus record */
 529         update_tailer(tdb, offset, rec);
 530
 531         /* Look right first (I'm an Australian, dammit) */
 532         right = offset + sizeof(*rec) + rec->rec_len;
 533         if (right + sizeof(*rec) <= tdb->map_size) {
 534                 struct list_struct r;
 535
 536                 if (tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) {
 537                         TDB_LOG((tdb, 0, "tdb_free: right read failed at %u\n", right));
 538                         goto left;
 539                 }
 540
 541                 /* If it's free, expand to include it. */
 542                 if (r.magic == TDB_FREE_MAGIC) {
 543                         if (remove_from_freelist(tdb, right, r.next) == -1) {
 544                                 TDB_LOG((tdb, 0, "tdb_free: right free failed at %u\n", right));
 545                                 goto left;
 546                         }
 547                         rec->rec_len += sizeof(r) + r.rec_len;
 548                 }
 549         }
 550
 551 left:
 552         /* Look left */
 553         left = offset - sizeof(tdb_off);
 554         if (left > TDB_HASH_TOP(tdb->header.hash_size-1)) {
 555                 struct list_struct l;
 556                 tdb_off leftsize;
 557
 558                 /* Read in tailer and jump back to header */
 559                 if (ofs_read(tdb, left, &leftsize) == -1) {
 560                         TDB_LOG((tdb, 0, "tdb_free: left offset read failed at %u\n", left));
 561                         goto update;
 562                 }
 563                 left = offset - leftsize;
 564
 565                 /* Now read in record */
 566                 if (tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) {
 567                         TDB_LOG((tdb, 0, "tdb_free: left read failed at %u (%u)\n", left, leftsize));
 568                         goto update;
 569                 }
 570
 571                 /* If it's free, expand to include it. */
 572                 if (l.magic == TDB_FREE_MAGIC) {
 573                         if (remove_from_freelist(tdb, left, l.next) == -1) {
 574                                 TDB_LOG((tdb, 0, "tdb_free: left free failed at %u\n", left));
 575                                 goto update;
 576                         } else {
 577                                 offset = left;
 578                                 rec->rec_len += leftsize;
 579                         }
 580                 }
 581         }
 582
 583 update:
 584         if (update_tailer(tdb, offset, rec) == -1) {
 585                 TDB_LOG((tdb, 0, "tdb_free: update_tailer failed at %u\n", offset));
 586                 goto fail;
 587         }
 588
 589         /* Now, prepend to free list */
 590         rec->magic = TDB_FREE_MAGIC;
 591
 592         if (ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
 593             rec_write(tdb, offset, rec) == -1 ||
 594             ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
 595                 TDB_LOG((tdb, 0, "tdb_free record write failed at offset=%d\n", offset));
 596                 goto fail;
 597         }
 598
 599         /* And we're done. */
 600         tdb_unlock(tdb, -1, F_WRLCK);
 601         return 0;
 602
 603  fail:
 604         tdb_unlock(tdb, -1, F_WRLCK);
 605         return -1;
 606 }
 607
 608
 609 /* expand a file.  we prefer to use ftruncate, as that is what posix
 610   says to use for mmap expansion */
 611 static int expand_file(TDB_CONTEXT *tdb, tdb_off size, tdb_off addition)
 612 {
 613         char buf[1024];
 614 #if HAVE_FTRUNCATE_EXTEND
 615         if (ftruncate(tdb->fd, size+addition) != 0) {
 616                 TDB_LOG((tdb, 0, "expand_file ftruncate to %d failed (%s)\n",
 617                            size+addition, strerror(errno)));
 618                 return -1;
 619         }
 620 #else
 621         char b = 0;
 622
 623 #ifdef HAVE_PWRITE
 624         if (pwrite(tdb->fd,  &b, 1, (size+addition) - 1) != 1) {
 625 #else
 626         if (lseek(tdb->fd, (size+addition) - 1, SEEK_SET) != (size+addition) - 1 ||
 627             write(tdb->fd, &b, 1) != 1) {
 628 #endif
 629                 TDB_LOG((tdb, 0, "expand_file to %d failed (%s)\n",
 630                            size+addition, strerror(errno)));
 631                 return -1;
 632         }
 633 #endif
 634
 635         /* now fill the file with something. This ensures that the file isn't sparse, which would be
 636            very bad if we ran out of disk. This must be done with write, not via mmap */
 637         memset(buf, 0x42, sizeof(buf));
 638         while (addition) {
 639                 int n = addition>sizeof(buf)?sizeof(buf):addition;
 640 #ifdef HAVE_PWRITE
 641                 int ret = pwrite(tdb->fd, buf, n, size);
 642 #else
 643                 int ret;
 644                 if (lseek(tdb->fd, size, SEEK_SET) != size)
 645                         return -1;
 646                 ret = write(tdb->fd, buf, n);
 647 #endif
 648                 if (ret != n) {
 649                         TDB_LOG((tdb, 0, "expand_file write of %d failed (%s)\n",
 650                                    n, strerror(errno)));
 651                         return -1;
 652                 }
 653                 addition -= n;
 654                 size += n;
 655         }
 656         return 0;
 657 }
 658
 659
 660 /* expand the database at least size bytes by expanding the underlying
 661    file and doing the mmap again if necessary */
 662 static int tdb_expand(TDB_CONTEXT *tdb, tdb_off size)
 663 {
 664         struct list_struct rec;
 665         tdb_off offset;
 666
 667         if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
 668                 TDB_LOG((tdb, 0, "lock failed in tdb_expand\n"));
 669                 return -1;
 670         }
 671
 672         /* must know about any previous expansions by another process */
 673         tdb_oob(tdb, tdb->map_size + 1, 1);
 674
 675         /* always make room for at least 10 more records, and round
 676            the database up to a multiple of TDB_PAGE_SIZE */
 677         size = TDB_ALIGN(tdb->map_size + size*10, TDB_PAGE_SIZE) - tdb->map_size;
 678
 679         if (!(tdb->flags & TDB_INTERNAL))
 680                 tdb_munmap(tdb);
 681
 682         /*
 683          * We must ensure the file is unmapped before doing this
 684          * to ensure consistency with systems like OpenBSD where
 685          * writes and mmaps are not consistent.
 686          */
 687
 688         /* expand the file itself */
 689         if (!(tdb->flags & TDB_INTERNAL)) {
 690                 if (expand_file(tdb, tdb->map_size, size) != 0)
 691                         goto fail;
 692         }
 693
 694         tdb->map_size += size;
 695
 696         if (tdb->flags & TDB_INTERNAL)
 697                 tdb->map_ptr = realloc(tdb->map_ptr, tdb->map_size);
 698         else {
 699                 /*
 700                  * We must ensure the file is remapped before adding the space
 701                  * to ensure consistency with systems like OpenBSD where
 702                  * writes and mmaps are not consistent.
 703                  */
 704
 705                 /* We're ok if the mmap fails as we'll fallback to read/write */
 706                 tdb_mmap(tdb);
 707         }
 708
 709         /* form a new freelist record */
 710         memset(&rec,'\0',sizeof(rec));
 711         rec.rec_len = size - sizeof(rec);
 712
 713         /* link it into the free list */
 714         offset = tdb->map_size - size;
 715         if (tdb_free(tdb, offset, &rec) == -1)
 716                 goto fail;
 717
 718         tdb_unlock(tdb, -1, F_WRLCK);
 719         return 0;
 720  fail:
 721         tdb_unlock(tdb, -1, F_WRLCK);
 722         return -1;
 723 }
 724
 725 /* allocate some space from the free list. The offset returned points
 726    to a unconnected list_struct within the database with room for at
 727    least length bytes of total data
 728
 729    0 is returned if the space could not be allocated
 730  */
 731 static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length,
 732                             struct list_struct *rec)
 733 {
 734         tdb_off rec_ptr, last_ptr, newrec_ptr;
 735         struct list_struct newrec;
 736
 737         if (tdb_lock(tdb, -1, F_WRLCK) == -1)
 738                 return 0;
 739
 740         /* Extra bytes required for tailer */
 741         length += sizeof(tdb_off);
 742
 743  again:
 744         last_ptr = FREELIST_TOP;
 745
 746         /* read in the freelist top */
 747         if (ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
 748                 goto fail;
 749
 750         /* keep looking until we find a freelist record big enough */
 751         while (rec_ptr) {
 752                 if (rec_free_read(tdb, rec_ptr, rec) == -1)
 753                         goto fail;
 754
 755                 if (rec->rec_len >= length) {
 756                         /* found it - now possibly split it up  */
 757                         if (rec->rec_len > length + MIN_REC_SIZE) {
 758                                 /* Length of left piece */
 759                                 length = TDB_ALIGN(length, TDB_ALIGNMENT);
 760
 761                                 /* Right piece to go on free list */
 762                                 newrec.rec_len = rec->rec_len
 763                                         - (sizeof(*rec) + length);
 764                                 newrec_ptr = rec_ptr + sizeof(*rec) + length;
 765
 766                                 /* And left record is shortened */
 767                                 rec->rec_len = length;
 768                         } else
 769                                 newrec_ptr = 0;
 770
 771                         /* Remove allocated record from the free list */
 772                         if (ofs_write(tdb, last_ptr, &rec->next) == -1)
 773                                 goto fail;
 774
 775                         /* Update header: do this before we drop alloc
 776                            lock, otherwise tdb_free() might try to
 777                            merge with us, thinking we're free.
 778                            (Thanks Jeremy Allison). */
 779                         rec->magic = TDB_MAGIC;
 780                         if (rec_write(tdb, rec_ptr, rec) == -1)
 781                                 goto fail;
 782
 783                         /* Did we create new block? */
 784                         if (newrec_ptr) {
 785                                 /* Update allocated record tailer (we
 786                                    shortened it). */
 787                                 if (update_tailer(tdb, rec_ptr, rec) == -1)
 788                                         goto fail;
 789
 790                                 /* Free new record */
 791                                 if (tdb_free(tdb, newrec_ptr, &newrec) == -1)
 792                                         goto fail;
 793                         }
 794
 795                         /* all done - return the new record offset */
 796                         tdb_unlock(tdb, -1, F_WRLCK);
 797                         return rec_ptr;
 798                 }
 799                 /* move to the next record */
 800                 last_ptr = rec_ptr;
 801                 rec_ptr = rec->next;
 802         }
 803         /* we didn't find enough space. See if we can expand the
 804            database and if we can then try again */
 805         if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
 806                 goto again;
 807  fail:
 808         tdb_unlock(tdb, -1, F_WRLCK);
 809         return 0;
 810 }
 811
 812 /* initialise a new database with a specified hash size */
 813 static int tdb_new_database(TDB_CONTEXT *tdb, int hash_size)
 814 {
 815         struct tdb_header *newdb;
 816         int size, ret = -1;
 817
 818         /* We make it up in memory, then write it out if not internal */
 819         size = sizeof(struct tdb_header) + (hash_size+1)*sizeof(tdb_off);
 820         if (!(newdb = calloc(size, 1)))
 821                 return TDB_ERRCODE(TDB_ERR_OOM, -1);
 822
 823         /* Fill in the header */
 824         newdb->version = TDB_VERSION;
 825         newdb->hash_size = hash_size;
 826 #ifdef USE_SPINLOCKS
 827         newdb->rwlocks = size;
 828 #endif
 829         if (tdb->flags & TDB_INTERNAL) {
 830                 tdb->map_size = size;
 831                 tdb->map_ptr = (char *)newdb;
 832                 memcpy(&tdb->header, newdb, sizeof(tdb->header));
 833                 /* Convert the `ondisk' version if asked. */
 834                 CONVERT(*newdb);
 835                 return 0;
 836         }
 837         if (lseek(tdb->fd, 0, SEEK_SET) == -1)
 838                 goto fail;
 839
 840         if (ftruncate(tdb->fd, 0) == -1)
 841                 goto fail;
 842
 843         /* This creates an endian-converted header, as if read from disk */
 844         CONVERT(*newdb);
 845         memcpy(&tdb->header, newdb, sizeof(tdb->header));
 846         /* Don't endian-convert the magic food! */
 847         memcpy(newdb->magic_food, TDB_MAGIC_FOOD, strlen(TDB_MAGIC_FOOD)+1);
 848         if (write(tdb->fd, newdb, size) != size)
 849                 ret = -1;
 850         else
 851                 ret = tdb_create_rwlocks(tdb->fd, hash_size);
 852
 853   fail:
 854         free(newdb);
 855         return ret;
 856 }
 857
 858 /* Returns 0 on fail.  On success, return offset of record, and fills
 859    in rec */
 860 static tdb_off tdb_find(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash,
 861                         struct list_struct *r)
 862 {
 863         tdb_off rec_ptr;
 864
 865         /* read in the hash top */
 866         if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
 867                 return 0;
 868
 869         /* keep looking until we find the right record */
 870         while (rec_ptr) {
 871                 if (rec_read(tdb, rec_ptr, r) == -1)
 872                         return 0;
 873
 874                 if (!TDB_DEAD(r) && hash==r->full_hash && key.dsize==r->key_len) {
 875                         char *k;
 876                         /* a very likely hit - read the key */
 877                         k = tdb_alloc_read(tdb, rec_ptr + sizeof(*r),
 878                                            r->key_len);
 879                         if (!k)
 880                                 return 0;
 881
 882                         if (memcmp(key.dptr, k, key.dsize) == 0) {
 883                                 free(k);
 884                                 return rec_ptr;
 885                         }
 886                         free(k);
 887                 }
 888                 rec_ptr = r->next;
 889         }
 890         return TDB_ERRCODE(TDB_ERR_NOEXIST, 0);
 891 }
 892
 893 /* If they do lockkeys, check that this hash is one they locked */
 894 static int tdb_keylocked(TDB_CONTEXT *tdb, u32 hash)
 895 {
 896         u32 i;
 897         if (!tdb->lockedkeys)
 898                 return 1;
 899         for (i = 0; i < tdb->lockedkeys[0]; i++)
 900                 if (tdb->lockedkeys[i+1] == hash)
 901                         return 1;
 902         return TDB_ERRCODE(TDB_ERR_NOLOCK, 0);
 903 }
 904
 905 /* As tdb_find, but if you succeed, keep the lock */
 906 static tdb_off tdb_find_lock(TDB_CONTEXT *tdb, TDB_DATA key, int locktype,
 907                              struct list_struct *rec)
 908 {
 909         u32 hash, rec_ptr;
 910
 911         hash = tdb_hash(&key);
 912         if (!tdb_keylocked(tdb, hash))
 913                 return 0;
 914         if (tdb_lock(tdb, BUCKET(hash), locktype) == -1)
 915                 return 0;
 916         if (!(rec_ptr = tdb_find(tdb, key, hash, rec)))
 917                 tdb_unlock(tdb, BUCKET(hash), locktype);
 918         return rec_ptr;
 919 }
 920
 921 enum TDB_ERROR tdb_error(TDB_CONTEXT *tdb)
 922 {
 923         return tdb->ecode;
 924 }
 925
 926 static struct tdb_errname {
 927         enum TDB_ERROR ecode; const char *estring;
 928 } emap[] = { {TDB_SUCCESS, "Success"},
 929              {TDB_ERR_CORRUPT, "Corrupt database"},
 930              {TDB_ERR_IO, "IO Error"},
 931              {TDB_ERR_LOCK, "Locking error"},
 932              {TDB_ERR_OOM, "Out of memory"},
 933              {TDB_ERR_EXISTS, "Record exists"},
 934              {TDB_ERR_NOLOCK, "Lock exists on other keys"},
 935              {TDB_ERR_NOEXIST, "Record does not exist"} };
 936
 937 /* Error string for the last tdb error */
 938 const char *tdb_errorstr(TDB_CONTEXT *tdb)
 939 {
 940         u32 i;
 941         for (i = 0; i < sizeof(emap) / sizeof(struct tdb_errname); i++)
 942                 if (tdb->ecode == emap[i].ecode)
 943                         return emap[i].estring;
 944         return "Invalid error code";
 945 }
 946
 947 /* update an entry in place - this only works if the new data size
 948    is <= the old data size and the key exists.
 949    on failure return -1
 950 */
 951 static int tdb_update(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)
 952 {
 953         struct list_struct rec;
 954         tdb_off rec_ptr;
 955         int ret = -1;
 956
 957         /* find entry */
 958         if (!(rec_ptr = tdb_find_lock(tdb, key, F_WRLCK, &rec)))
 959                 return -1;
 960
 961         /* must be long enough key, data and tailer */
 962         if (rec.rec_len < key.dsize + dbuf.dsize + sizeof(tdb_off)) {
 963                 tdb->ecode = TDB_SUCCESS; /* Not really an error */
 964                 goto out;
 965         }
 966
 967         if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
 968                       dbuf.dptr, dbuf.dsize) == -1)
 969                 goto out;
 970
 971         if (dbuf.dsize != rec.data_len) {
 972                 /* update size */
 973                 rec.data_len = dbuf.dsize;
 974                 ret = rec_write(tdb, rec_ptr, &rec);
 975         } else
 976                 ret = 0;
 977  out:
 978         tdb_unlock(tdb, BUCKET(rec.full_hash), F_WRLCK);
 979         return ret;
 980 }
 981
 982 /* find an entry in the database given a key */
 983 TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key)
 984 {
 985         tdb_off rec_ptr;
 986         struct list_struct rec;
 987         TDB_DATA ret;
 988
 989         /* find which hash bucket it is in */
 990         if (!(rec_ptr = tdb_find_lock(tdb,key,F_RDLCK,&rec)))
 991                 return tdb_null;
 992
 993         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec) + rec.key_len,
 994                                   rec.data_len);
 995         ret.dsize = rec.data_len;
 996         tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
 997         return ret;
 998 }
 999
1000 /* check if an entry in the database exists
1001
1002    note that 1 is returned if the key is found and 0 is returned if not found
1003    this doesn't match the conventions in the rest of this module, but is
1004    compatible with gdbm
1005 */
1006 int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key)
1007 {
1008         struct list_struct rec;
1009
1010         if (tdb_find_lock(tdb, key, F_RDLCK, &rec) == 0)
1011                 return 0;
1012         tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
1013         return 1;
1014 }
1015
1016 /* record lock stops delete underneath */
1017 static int lock_record(TDB_CONTEXT *tdb, tdb_off off)
1018 {
1019         return off ? tdb_brlock(tdb, off, F_RDLCK, F_SETLKW, 0) : 0;
1020 }
1021 /*
1022   Write locks override our own fcntl readlocks, so check it here.
1023   Note this is meant to be F_SETLK, *not* F_SETLKW, as it's not
1024   an error to fail to get the lock here.
1025 */
1026
1027 static int write_lock_record(TDB_CONTEXT *tdb, tdb_off off)
1028 {
1029         struct tdb_traverse_lock *i;
1030         for (i = &tdb->travlocks; i; i = i->next)
1031                 if (i->off == off)
1032                         return -1;
1033         return tdb_brlock(tdb, off, F_WRLCK, F_SETLK, 1);
1034 }
1035
1036 /*
1037   Note this is meant to be F_SETLK, *not* F_SETLKW, as it's not
1038   an error to fail to get the lock here.
1039 */
1040
1041 static int write_unlock_record(TDB_CONTEXT *tdb, tdb_off off)
1042 {
1043         return tdb_brlock(tdb, off, F_UNLCK, F_SETLK, 0);
1044 }
1045 /* fcntl locks don't stack: avoid unlocking someone else's */
1046 static int unlock_record(TDB_CONTEXT *tdb, tdb_off off)
1047 {
1048         struct tdb_traverse_lock *i;
1049         u32 count = 0;
1050
1051         if (off == 0)
1052                 return 0;
1053         for (i = &tdb->travlocks; i; i = i->next)
1054                 if (i->off == off)
1055                         count++;
1056         return (count == 1 ? tdb_brlock(tdb, off, F_UNLCK, F_SETLKW, 0) : 0);
1057 }
1058
1059 /* actually delete an entry in the database given the offset */
1060 static int do_delete(TDB_CONTEXT *tdb, tdb_off rec_ptr, struct list_struct*rec)
1061 {
1062         tdb_off last_ptr, i;
1063         struct list_struct lastrec;
1064
1065         if (tdb->read_only) return -1;
1066
1067         if (write_lock_record(tdb, rec_ptr) == -1) {
1068                 /* Someone traversing here: mark it as dead */
1069                 rec->magic = TDB_DEAD_MAGIC;
1070                 return rec_write(tdb, rec_ptr, rec);
1071         }
1072         write_unlock_record(tdb, rec_ptr);
1073
1074         /* find previous record in hash chain */
1075         if (ofs_read(tdb, TDB_HASH_TOP(rec->full_hash), &i) == -1)
1076                 return -1;
1077         for (last_ptr = 0; i != rec_ptr; last_ptr = i, i = lastrec.next)
1078                 if (rec_read(tdb, i, &lastrec) == -1)
1079                         return -1;
1080
1081         /* unlink it: next ptr is at start of record. */
1082         if (last_ptr == 0)
1083                 last_ptr = TDB_HASH_TOP(rec->full_hash);
1084         if (ofs_write(tdb, last_ptr, &rec->next) == -1)
1085                 return -1;
1086
1087         /* recover the space */
1088         if (tdb_free(tdb, rec_ptr, rec) == -1)
1089                 return -1;
1090         return 0;
1091 }
1092
1093 /* Uses traverse lock: 0 = finish, -1 = error, other = record offset */
1094 static int tdb_next_lock(TDB_CONTEXT *tdb, struct tdb_traverse_lock *tlock,
1095                          struct list_struct *rec)
1096 {
1097         int want_next = (tlock->off != 0);
1098
1099         /* No traversal allows if you've called tdb_lockkeys() */
1100         if (tdb->lockedkeys)
1101                 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1102
1103         /* Lock each chain from the start one. */
1104         for (; tlock->hash < tdb->header.hash_size; tlock->hash++) {
1105                 if (tdb_lock(tdb, tlock->hash, F_WRLCK) == -1)
1106                         return -1;
1107
1108                 /* No previous record?  Start at top of chain. */
1109                 if (!tlock->off) {
1110                         if (ofs_read(tdb, TDB_HASH_TOP(tlock->hash),
1111                                      &tlock->off) == -1)
1112                                 goto fail;
1113                 } else {
1114                         /* Otherwise unlock the previous record. */
1115                         unlock_record(tdb, tlock->off);
1116                 }
1117
1118                 if (want_next) {
1119                         /* We have offset of old record: grab next */
1120                         if (rec_read(tdb, tlock->off, rec) == -1)
1121                                 goto fail;
1122                         tlock->off = rec->next;
1123                 }
1124
1125                 /* Iterate through chain */
1126                 while( tlock->off) {
1127                         tdb_off current;
1128                         if (rec_read(tdb, tlock->off, rec) == -1)
1129                                 goto fail;
1130                         if (!TDB_DEAD(rec)) {
1131                                 /* Woohoo: we found one! */
1132                                 lock_record(tdb, tlock->off);
1133                                 return tlock->off;
1134                         }
1135                         /* Try to clean dead ones from old traverses */
1136                         current = tlock->off;
1137                         tlock->off = rec->next;
1138                         do_delete(tdb, current, rec);
1139                 }
1140                 tdb_unlock(tdb, tlock->hash, F_WRLCK);
1141                 want_next = 0;
1142         }
1143         /* We finished iteration without finding anything */
1144         return TDB_ERRCODE(TDB_SUCCESS, 0);
1145
1146  fail:
1147         tlock->off = 0;
1148         tdb_unlock(tdb, tlock->hash, F_WRLCK);
1149         return -1;
1150 }
1151
1152 /* traverse the entire database - calling fn(tdb, key, data) on each element.
1153    return -1 on error or the record count traversed
1154    if fn is NULL then it is not called
1155    a non-zero return value from fn() indicates that the traversal should stop
1156   */
1157 int tdb_traverse(TDB_CONTEXT *tdb, tdb_traverse_func fn, void *state)
1158 {
1159         TDB_DATA key, dbuf;
1160         struct list_struct rec;
1161         struct tdb_traverse_lock tl = { NULL, 0, 0 };
1162         int ret, count = 0;
1163
1164         /* This was in the initializaton, above, but the IRIX compiler
1165          * did not like it.  crh
1166          */
1167         tl.next = tdb->travlocks.next;
1168
1169         /* fcntl locks don't stack: beware traverse inside traverse */
1170         tdb->travlocks.next = &tl;
1171
1172         /* tdb_next_lock places locks on the record returned, and its chain */
1173         while ((ret = tdb_next_lock(tdb, &tl, &rec)) > 0) {
1174                 count++;
1175                 /* now read the full record */
1176                 key.dptr = tdb_alloc_read(tdb, tl.off + sizeof(rec),
1177                                           rec.key_len + rec.data_len);
1178                 if (!key.dptr) {
1179                         tdb_unlock(tdb, tl.hash, F_WRLCK);
1180                         unlock_record(tdb, tl.off);
1181                         tdb->travlocks.next = tl.next;
1182                         return -1;
1183                 }
1184                 key.dsize = rec.key_len;
1185                 dbuf.dptr = key.dptr + rec.key_len;
1186                 dbuf.dsize = rec.data_len;
1187
1188                 /* Drop chain lock, call out */
1189                 tdb_unlock(tdb, tl.hash, F_WRLCK);
1190                 if (fn && fn(tdb, key, dbuf, state)) {
1191                         /* They want us to terminate traversal */
1192                         unlock_record(tdb, tl.off);
1193                         tdb->travlocks.next = tl.next;
1194                         free(key.dptr);
1195                         return count;
1196                 }
1197                 free(key.dptr);
1198         }
1199         tdb->travlocks.next = tl.next;
1200         if (ret < 0)
1201                 return -1;
1202         else
1203                 return count;
1204 }
1205
1206 /* find the first entry in the database and return its key */
1207 TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb)
1208 {
1209         TDB_DATA key;
1210         struct list_struct rec;
1211
1212         /* release any old lock */
1213         unlock_record(tdb, tdb->travlocks.off);
1214         tdb->travlocks.off = tdb->travlocks.hash = 0;
1215
1216         if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0)
1217                 return tdb_null;
1218         /* now read the key */
1219         key.dsize = rec.key_len;
1220         key.dptr =tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),key.dsize);
1221         tdb_unlock(tdb, BUCKET(tdb->travlocks.hash), F_WRLCK);
1222         return key;
1223 }
1224
1225 /* find the next entry in the database, returning its key */
1226 TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA oldkey)
1227 {
1228         u32 oldhash;
1229         TDB_DATA key = tdb_null;
1230         struct list_struct rec;
1231         char *k = NULL;
1232
1233         /* Is locked key the old key?  If so, traverse will be reliable. */
1234         if (tdb->travlocks.off) {
1235                 if (tdb_lock(tdb,tdb->travlocks.hash,F_WRLCK))
1236                         return tdb_null;
1237                 if (rec_read(tdb, tdb->travlocks.off, &rec) == -1
1238                     || !(k = tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),
1239                                             rec.key_len))
1240                     || memcmp(k, oldkey.dptr, oldkey.dsize) != 0) {
1241                         /* No, it wasn't: unlock it and start from scratch */
1242                         unlock_record(tdb, tdb->travlocks.off);
1243                         tdb_unlock(tdb, tdb->travlocks.hash, F_WRLCK);
1244                         tdb->travlocks.off = 0;
1245                 }
1246
1247                 if (k)
1248                         free(k);
1249         }
1250
1251         if (!tdb->travlocks.off) {
1252                 /* No previous element: do normal find, and lock record */
1253                 tdb->travlocks.off = tdb_find_lock(tdb, oldkey, F_WRLCK, &rec);
1254                 if (!tdb->travlocks.off)
1255                         return tdb_null;
1256                 tdb->travlocks.hash = BUCKET(rec.full_hash);
1257                 lock_record(tdb, tdb->travlocks.off);
1258         }
1259         oldhash = tdb->travlocks.hash;
1260
1261         /* Grab next record: locks chain and returned record,
1262            unlocks old record */
1263         if (tdb_next_lock(tdb, &tdb->travlocks, &rec) > 0) {
1264                 key.dsize = rec.key_len;
1265                 key.dptr = tdb_alloc_read(tdb, tdb->travlocks.off+sizeof(rec),
1266                                           key.dsize);
1267                 /* Unlock the chain of this new record */
1268                 tdb_unlock(tdb, tdb->travlocks.hash, F_WRLCK);
1269         }
1270         /* Unlock the chain of old record */
1271         tdb_unlock(tdb, BUCKET(oldhash), F_WRLCK);
1272         return key;
1273 }
1274
1275 /* delete an entry in the database given a key */
1276 int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key)
1277 {
1278         tdb_off rec_ptr;
1279         struct list_struct rec;
1280         int ret;
1281
1282         if (!(rec_ptr = tdb_find_lock(tdb, key, F_WRLCK, &rec)))
1283                 return -1;
1284         ret = do_delete(tdb, rec_ptr, &rec);
1285         tdb_unlock(tdb, BUCKET(rec.full_hash), F_WRLCK);
1286         return ret;
1287 }
1288
1289 /* store an element in the database, replacing any existing element
1290    with the same key
1291
1292    return 0 on success, -1 on failure
1293 */
1294 int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
1295 {
1296         struct list_struct rec;
1297         u32 hash;
1298         tdb_off rec_ptr;
1299         char *p = NULL;
1300         int ret = 0;
1301
1302         /* find which hash bucket it is in */
1303         hash = tdb_hash(&key);
1304         if (!tdb_keylocked(tdb, hash))
1305                 return -1;
1306         if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
1307                 return -1;
1308
1309         /* check for it existing, on insert. */
1310         if (flag == TDB_INSERT) {
1311                 if (tdb_exists(tdb, key)) {
1312                         tdb->ecode = TDB_ERR_EXISTS;
1313                         goto fail;
1314                 }
1315         } else {
1316                 /* first try in-place update, on modify or replace. */
1317                 if (tdb_update(tdb, key, dbuf) == 0)
1318                         goto out;
1319                 if (flag == TDB_MODIFY && tdb->ecode == TDB_ERR_NOEXIST)
1320                         goto fail;
1321         }
1322         /* reset the error code potentially set by the tdb_update() */
1323         tdb->ecode = TDB_SUCCESS;
1324
1325         /* delete any existing record - if it doesn't exist we don't
1326            care.  Doing this first reduces fragmentation, and avoids
1327            coalescing with `allocated' block before it's updated. */
1328         if (flag != TDB_INSERT)
1329                 tdb_delete(tdb, key);
1330
1331         /* Copy key+value *before* allocating free space in case malloc
1332            fails and we are left with a dead spot in the tdb. */
1333
1334         if (!(p = (char *)malloc(key.dsize + dbuf.dsize))) {
1335                 tdb->ecode = TDB_ERR_OOM;
1336                 goto fail;
1337         }
1338
1339         memcpy(p, key.dptr, key.dsize);
1340         memcpy(p+key.dsize, dbuf.dptr, dbuf.dsize);
1341
1342         /* now we're into insert / modify / replace of a record which
1343          * we know could not be optimised by an in-place store (for
1344          * various reasons).  */
1345         if (!(rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize, &rec)))
1346                 goto fail;
1347
1348         /* Read hash top into next ptr */
1349         if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
1350                 goto fail;
1351
1352         rec.key_len = key.dsize;
1353         rec.data_len = dbuf.dsize;
1354         rec.full_hash = hash;
1355         rec.magic = TDB_MAGIC;
1356
1357         /* write out and point the top of the hash chain at it */
1358         if (rec_write(tdb, rec_ptr, &rec) == -1
1359             || tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+dbuf.dsize)==-1
1360             || ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
1361         fail:
1362                 /* Need to tdb_unallocate() here */
1363                 ret = -1;
1364         }
1365  out:
1366         if (p)
1367                 free(p);
1368         tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
1369         return ret;
1370 }
1371
1372 /* open the database, creating it if necessary
1373
1374    The open_flags and mode are passed straight to the open call on the
1375    database file. A flags value of O_WRONLY is invalid. The hash size
1376    is advisory, use zero for a default value.
1377
1378    Return is NULL on error, in which case errno is also set.  Don't
1379    try to call tdb_error or tdb_errname, just do strerror(errno).  */
1380 TDB_CONTEXT *tdb_open(char *name, int hash_size, int tdb_flags,
1381                       int open_flags, mode_t mode)
1382 {
1383         return tdb_open_ex(name, hash_size, tdb_flags, open_flags, mode, NULL);
1384 }
1385
1386 TDB_CONTEXT *tdb_open_ex(char *name, int hash_size, int tdb_flags,
1387                          int open_flags, mode_t mode,
1388                          tdb_log_func log_fn)
1389 {
1390         TDB_CONTEXT tdb, *ret, *i;
1391         struct stat st;
1392         int rev = 0, locked;
1393
1394         memset(&tdb, 0, sizeof(tdb));
1395         tdb.fd = -1;
1396         tdb.name = NULL;
1397         tdb.map_ptr = NULL;
1398         tdb.lockedkeys = NULL;
1399         tdb.flags = tdb_flags;
1400         tdb.open_flags = open_flags;
1401         tdb.log_fn = log_fn;
1402
1403         if ((open_flags & O_ACCMODE) == O_WRONLY) {
1404                 errno = EINVAL;
1405                 goto fail;
1406         }
1407
1408         if (hash_size == 0)
1409                 hash_size = DEFAULT_HASH_SIZE;
1410         if ((open_flags & O_ACCMODE) == O_RDONLY) {
1411                 tdb.read_only = 1;
1412                 /* read only databases don't do locking or clear if first */
1413                 tdb.flags |= TDB_NOLOCK;
1414                 tdb.flags &= ~TDB_CLEAR_IF_FIRST;
1415         }
1416
1417         /* internal databases don't mmap or lock, and start off cleared */
1418         if (tdb.flags & TDB_INTERNAL) {
1419                 tdb.flags |= (TDB_NOLOCK | TDB_NOMMAP);
1420                 tdb.flags &= ~TDB_CLEAR_IF_FIRST;
1421                 tdb_new_database(&tdb, hash_size);
1422                 goto internal;
1423         }
1424
1425         if ((tdb.fd = open(name, open_flags, mode)) == -1)
1426                 goto fail;      /* errno set by open(2) */
1427
1428         /* ensure there is only one process initialising at once */
1429         if (tdb_brlock(&tdb, GLOBAL_LOCK, F_WRLCK, F_SETLKW, 0) == -1)
1430                 goto fail;      /* errno set by tdb_brlock */
1431
1432         /* we need to zero database if we are the only one with it open */
1433         if ((locked = (tdb_brlock(&tdb, ACTIVE_LOCK, F_WRLCK, F_SETLK, 0) == 0))
1434             && (tdb_flags & TDB_CLEAR_IF_FIRST)) {
1435                 open_flags |= O_CREAT;
1436                 if (ftruncate(tdb.fd, 0) == -1)
1437                         goto fail; /* errno set by ftruncate */
1438         }
1439
1440         if (read(tdb.fd, &tdb.header, sizeof(tdb.header)) != sizeof(tdb.header)
1441             || strcmp(tdb.header.magic_food, TDB_MAGIC_FOOD) != 0
1442             || (tdb.header.version != TDB_VERSION
1443                 && !(rev = (tdb.header.version==TDB_BYTEREV(TDB_VERSION))))) {
1444                 /* its not a valid database - possibly initialise it */
1445                 if (!(open_flags & O_CREAT) || tdb_new_database(&tdb, hash_size) == -1) {
1446                         errno = EIO; /* ie bad format or something */
1447                         goto fail;
1448                 }
1449                 rev = (tdb.flags & TDB_CONVERT);
1450         }
1451         if (!rev)
1452                 tdb.flags &= ~TDB_CONVERT;
1453         else {
1454                 tdb.flags |= TDB_CONVERT;
1455                 convert(&tdb.header, sizeof(tdb.header));
1456         }
1457         if (fstat(tdb.fd, &st) == -1)
1458                 goto fail;
1459
1460         /* Is it already in the open list?  If so, fail. */
1461         for (i = tdbs; i; i = i->next) {
1462                 if (i->device == st.st_dev && i->inode == st.st_ino) {
1463                         errno = EBUSY;
1464                         close(tdb.fd);
1465                         return NULL;
1466                 }
1467         }
1468
1469         /* map the database and fill in the return structure */
1470         tdb.name = (char *)strdup(name);
1471         if (!tdb.name) {
1472                 errno = ENOMEM;
1473                 goto fail;
1474         }
1475         tdb.map_size = st.st_size;
1476         tdb.device = st.st_dev;
1477         tdb.inode = st.st_ino;
1478         tdb.locked = calloc(tdb.header.hash_size+1, sizeof(tdb.locked[0]));
1479         if (!tdb.locked) {
1480                 errno = ENOMEM;
1481                 goto fail;
1482         }
1483         tdb_mmap(&tdb);
1484         if (locked) {
1485                 if (!tdb.read_only)
1486                         tdb_clear_spinlocks(&tdb);
1487                 if (tdb_brlock(&tdb, ACTIVE_LOCK, F_UNLCK, F_SETLK, 0) == -1)
1488                         goto fail;
1489         }
1490         /* leave this lock in place to indicate it's in use */
1491         if (tdb_brlock(&tdb, ACTIVE_LOCK, F_RDLCK, F_SETLKW, 0) == -1)
1492                 goto fail;
1493
1494  internal:
1495         if (!(ret = malloc(sizeof(tdb)))) {
1496                 errno = ENOMEM;
1497                 goto fail;
1498         }
1499         *ret = tdb;
1500         if (tdb_brlock(&tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0) == -1)
1501                 goto fail;
1502         ret->next = tdbs;
1503         tdbs = ret;
1504         return ret;
1505
1506  fail:
1507         { int save_errno = errno;
1508
1509         if (tdb.map_ptr) {
1510                 if (tdb.flags & TDB_INTERNAL)
1511                         free(tdb.map_ptr);
1512                 else
1513                         tdb_munmap(&tdb);
1514         }
1515         if (tdb.name)
1516                 free(tdb.name);
1517         if (tdb.fd != -1)
1518                 close(tdb.fd);
1519         if (tdb.locked)
1520                 free(tdb.locked);
1521         errno = save_errno;
1522         return NULL;
1523         }
1524 }
1525
1526 /* close a database */
1527 int tdb_close(TDB_CONTEXT *tdb)
1528 {
1529         TDB_CONTEXT **i;
1530         int ret = 0;
1531
1532         if (tdb->map_ptr) {
1533                 if (tdb->flags & TDB_INTERNAL)
1534                         free(tdb->map_ptr);
1535                 else
1536                         tdb_munmap(tdb);
1537         }
1538         if (tdb->name)
1539                 free(tdb->name);
1540         if (tdb->fd != -1)
1541                 ret = close(tdb->fd);
1542         if (tdb->locked)
1543                 free(tdb->locked);
1544         if (tdb->lockedkeys)
1545                 free(tdb->lockedkeys);
1546
1547         /* Remove from contexts list */
1548         for (i = &tdbs; *i; i = &(*i)->next) {
1549                 if (*i == tdb) {
1550                         *i = tdb->next;
1551                         break;
1552                 }
1553         }
1554
1555         memset(tdb, 0, sizeof(*tdb));
1556         free(tdb);
1557
1558         return ret;
1559 }
1560
1561 /* lock/unlock entire database */
1562 int tdb_lockall(TDB_CONTEXT *tdb)
1563 {
1564         u32 i;
1565
1566         /* There are no locks on read-only dbs */
1567         if (tdb->read_only)
1568                 return TDB_ERRCODE(TDB_ERR_LOCK, -1);
1569         if (tdb->lockedkeys)
1570                 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1571         for (i = 0; i < tdb->header.hash_size; i++)
1572                 if (tdb_lock(tdb, i, F_WRLCK))
1573                         break;
1574
1575         /* If error, release locks we have... */
1576         if (i < tdb->header.hash_size) {
1577                 u32 j;
1578
1579                 for ( j = 0; j < i; j++)
1580                         tdb_unlock(tdb, j, F_WRLCK);
1581                 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1582         }
1583
1584         return 0;
1585 }
1586 void tdb_unlockall(TDB_CONTEXT *tdb)
1587 {
1588         u32 i;
1589         for (i=0; i < tdb->header.hash_size; i++)
1590                 tdb_unlock(tdb, i, F_WRLCK);
1591 }
1592
1593 int tdb_lockkeys(TDB_CONTEXT *tdb, u32 number, TDB_DATA keys[])
1594 {
1595         u32 i, j, hash;
1596
1597         /* Can't lock more keys if already locked */
1598         if (tdb->lockedkeys)
1599                 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1600         if (!(tdb->lockedkeys = malloc(sizeof(u32) * (number+1))))
1601                 return TDB_ERRCODE(TDB_ERR_OOM, -1);
1602         /* First number in array is # keys */
1603         tdb->lockedkeys[0] = number;
1604
1605         /* Insertion sort by bucket */
1606         for (i = 0; i < number; i++) {
1607                 hash = tdb_hash(&keys[i]);
1608                 for (j = 0; j < i && BUCKET(tdb->lockedkeys[j+1]) < BUCKET(hash); j++);
1609                         memmove(&tdb->lockedkeys[j+2], &tdb->lockedkeys[j+1], sizeof(u32) * (i-j));
1610                 tdb->lockedkeys[j+1] = hash;
1611         }
1612         /* Finally, lock in order */
1613         for (i = 0; i < number; i++)
1614                 if (tdb_lock(tdb, i, F_WRLCK))
1615                         break;
1616
1617         /* If error, release locks we have... */
1618         if (i < number) {
1619                 for ( j = 0; j < i; j++)
1620                         tdb_unlock(tdb, j, F_WRLCK);
1621                 free(tdb->lockedkeys);
1622                 tdb->lockedkeys = NULL;
1623                 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1624         }
1625         return 0;
1626 }
1627
1628 /* Unlock the keys previously locked by tdb_lockkeys() */
1629 void tdb_unlockkeys(TDB_CONTEXT *tdb)
1630 {
1631         u32 i;
1632         for (i = 0; i < tdb->lockedkeys[0]; i++)
1633                 tdb_unlock(tdb, tdb->lockedkeys[i+1], F_WRLCK);
1634         free(tdb->lockedkeys);
1635         tdb->lockedkeys = NULL;
1636 }
1637
1638 /* lock/unlock one hash chain. This is meant to be used to reduce
1639    contention - it cannot guarantee how many records will be locked */
1640 int tdb_chainlock(TDB_CONTEXT *tdb, TDB_DATA key)
1641 {
1642         return tdb_lock(tdb, BUCKET(tdb_hash(&key)), F_WRLCK);
1643 }
1644 void tdb_chainunlock(TDB_CONTEXT *tdb, TDB_DATA key)
1645 {
1646         tdb_unlock(tdb, BUCKET(tdb_hash(&key)), F_WRLCK);
1647 }
1648
1649
1650 /* register a loging function */
1651 void tdb_logging_function(TDB_CONTEXT *tdb, void (*fn)(TDB_CONTEXT *, int , const char *, ...))
1652 {
1653         tdb->log_fn = fn;
1654 }
1655
1656
1657 /* reopen a tdb - this is used after a fork to ensure that we have an independent
1658    seek pointer from our parent and to re-establish locks */
1659 int tdb_reopen(TDB_CONTEXT *tdb)
1660 {
1661         struct stat st;
1662
1663         tdb_munmap(tdb);
1664         close(tdb->fd);
1665         tdb->fd = open(tdb->name, tdb->open_flags & ~(O_CREAT|O_TRUNC), 0);
1666         if (tdb->fd == -1) {
1667                 TDB_LOG((tdb, 0, "tdb_reopen: open failed (%s)\n", strerror(errno)));
1668                 goto fail;
1669         }
1670         fstat(tdb->fd, &st);
1671         if (st.st_ino != tdb->inode || st.st_dev != tdb->device) {
1672                 TDB_LOG((tdb, 0, "tdb_reopen: file dev/inode has changed!\n"));
1673                 goto fail;
1674         }
1675         tdb_mmap(tdb);
1676         if (tdb_brlock(tdb, ACTIVE_LOCK, F_RDLCK, F_SETLKW, 0) == -1) {
1677                 TDB_LOG((tdb, 0, "tdb_reopen: failed to obtain active lock\n"));
1678                 goto fail;
1679         }
1680
1681         return 0;
1682
1683 fail:
1684         tdb_close(tdb);
1685         return -1;
1686 }
1687
1688 /* reopen all tdb's */
1689 int tdb_reopen_all(void)
1690 {
1691         TDB_CONTEXT *tdb;
1692
1693         for (tdb=tdbs; tdb; tdb = tdb->next) {
1694                 if (tdb_reopen(tdb) != 0) return -1;
1695         }
1696
1697         return 0;
1698 }