source/lib/tdb/common/tdb.c

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