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 around 80 in speed on a linux 2.6.x
1280                    system (testing using ldbtest).
1281                  */
1282                 if (!tlock->off && tlock->hash != 0) {
1283                         u32 off;
1284                         if (tdb->map_ptr) {
1285                                 for (;tlock->hash < tdb->header.hash_size;tlock->hash++) {
1286                                         if (0 != *(u32 *)(TDB_HASH_TOP(tlock->hash) + (unsigned char *)tdb->map_ptr)) {
1287                                                 break;
1288                                         }
1289                                 }
1290                         } else {
1291                                 if (ofs_read(tdb, TDB_HASH_TOP(tlock->hash), &off) == 0 &&
1292                                     off == 0) {
1293                                         continue;
1294                                 }
1295                         }
1296                 }
1297
1298                 if (tdb_lock(tdb, tlock->hash, F_WRLCK) == -1)
1299                         return -1;
1300
1301                 /* No previous record?  Start at top of chain. */
1302                 if (!tlock->off) {
1303                         if (ofs_read(tdb, TDB_HASH_TOP(tlock->hash),
1304                                      &tlock->off) == -1)
1305                                 goto fail;
1306                 } else {
1307                         /* Otherwise unlock the previous record. */
1308                         if (unlock_record(tdb, tlock->off) != 0)
1309                                 goto fail;
1310                 }
1311
1312                 if (want_next) {
1313                         /* We have offset of old record: grab next */
1314                         if (rec_read(tdb, tlock->off, rec) == -1)
1315                                 goto fail;
1316                         tlock->off = rec->next;
1317                 }
1318
1319                 /* Iterate through chain */
1320                 while( tlock->off) {
1321                         tdb_off current;
1322                         if (rec_read(tdb, tlock->off, rec) == -1)
1323                                 goto fail;
1324
1325                         /* Detect infinite loops. From "Shlomi Yaakobovich" <Shlomi@exanet.com>. */
1326                         if (tlock->off == rec->next) {
1327                                 TDB_LOG((tdb, 0, "tdb_next_lock: loop detected.\n"));
1328                                 goto fail;
1329                         }
1330
1331                         if (!TDB_DEAD(rec)) {
1332                                 /* Woohoo: we found one! */
1333                                 if (lock_record(tdb, tlock->off) != 0)
1334                                         goto fail;
1335                                 return tlock->off;
1336                         }
1337
1338                         /* Try to clean dead ones from old traverses */
1339                         current = tlock->off;
1340                         tlock->off = rec->next;
1341                         if (!tdb->read_only &&
1342                             do_delete(tdb, current, rec) != 0)
1343                                 goto fail;
1344                 }
1345                 tdb_unlock(tdb, tlock->hash, F_WRLCK);
1346                 want_next = 0;
1347         }
1348         /* We finished iteration without finding anything */
1349         return TDB_ERRCODE(TDB_SUCCESS, 0);
1350
1351  fail:
1352         tlock->off = 0;
1353         if (tdb_unlock(tdb, tlock->hash, F_WRLCK) != 0)
1354                 TDB_LOG((tdb, 0, "tdb_next_lock: On error unlock failed!\n"));
1355         return -1;
1356 }
1357
1358 /* traverse the entire database - calling fn(tdb, key, data) on each element.
1359    return -1 on error or the record count traversed
1360    if fn is NULL then it is not called
1361    a non-zero return value from fn() indicates that the traversal should stop
1362   */
1363 int tdb_traverse(TDB_CONTEXT *tdb, tdb_traverse_func fn, void *private)
1364 {
1365         TDB_DATA key, dbuf;
1366         struct list_struct rec;
1367         struct tdb_traverse_lock tl = { NULL, 0, 0 };
1368         int ret, count = 0;
1369
1370         /* This was in the initializaton, above, but the IRIX compiler
1371          * did not like it.  crh
1372          */
1373         tl.next = tdb->travlocks.next;
1374
1375         /* fcntl locks don't stack: beware traverse inside traverse */
1376         tdb->travlocks.next = &tl;
1377
1378         /* tdb_next_lock places locks on the record returned, and its chain */
1379         while ((ret = tdb_next_lock(tdb, &tl, &rec)) > 0) {
1380                 count++;
1381                 /* now read the full record */
1382                 key.dptr = tdb_alloc_read(tdb, tl.off + sizeof(rec),
1383                                           rec.key_len + rec.data_len);
1384                 if (!key.dptr) {
1385                         ret = -1;
1386                         if (tdb_unlock(tdb, tl.hash, F_WRLCK) != 0)
1387                                 goto out;
1388                         if (unlock_record(tdb, tl.off) != 0)
1389                                 TDB_LOG((tdb, 0, "tdb_traverse: key.dptr == NULL and unlock_record failed!\n"));
1390                         goto out;
1391                 }
1392                 key.dsize = rec.key_len;
1393                 dbuf.dptr = key.dptr + rec.key_len;
1394                 dbuf.dsize = rec.data_len;
1395
1396                 /* Drop chain lock, call out */
1397                 if (tdb_unlock(tdb, tl.hash, F_WRLCK) != 0) {
1398                         ret = -1;
1399                         goto out;
1400                 }
1401                 if (fn && fn(tdb, key, dbuf, private)) {
1402                         /* They want us to terminate traversal */
1403                         ret = count;
1404                         if (unlock_record(tdb, tl.off) != 0) {
1405                                 TDB_LOG((tdb, 0, "tdb_traverse: unlock_record failed!\n"));;
1406                                 ret = -1;
1407                         }
1408                         tdb->travlocks.next = tl.next;
1409                         SAFE_FREE(key.dptr);
1410                         return count;
1411                 }
1412                 SAFE_FREE(key.dptr);
1413         }
1414 out:
1415         tdb->travlocks.next = tl.next;
1416         if (ret < 0)
1417                 return -1;
1418         else
1419                 return count;
1420 }
1421
1422 /* find the first entry in the database and return its key */
1423 TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb)
1424 {
1425         TDB_DATA key;
1426         struct list_struct rec;
1427
1428         /* release any old lock */
1429         if (unlock_record(tdb, tdb->travlocks.off) != 0)
1430                 return tdb_null;
1431         tdb->travlocks.off = tdb->travlocks.hash = 0;
1432
1433         if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0)
1434                 return tdb_null;
1435         /* now read the key */
1436         key.dsize = rec.key_len;
1437         key.dptr =tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),key.dsize);
1438         if (tdb_unlock(tdb, BUCKET(tdb->travlocks.hash), F_WRLCK) != 0)
1439                 TDB_LOG((tdb, 0, "tdb_firstkey: error occurred while tdb_unlocking!\n"));
1440         return key;
1441 }
1442
1443 /* find the next entry in the database, returning its key */
1444 TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA oldkey)
1445 {
1446         u32 oldhash;
1447         TDB_DATA key = tdb_null;
1448         struct list_struct rec;
1449         char *k = NULL;
1450
1451         /* Is locked key the old key?  If so, traverse will be reliable. */
1452         if (tdb->travlocks.off) {
1453                 if (tdb_lock(tdb,tdb->travlocks.hash,F_WRLCK))
1454                         return tdb_null;
1455                 if (rec_read(tdb, tdb->travlocks.off, &rec) == -1
1456                     || !(k = tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),
1457                                             rec.key_len))
1458                     || memcmp(k, oldkey.dptr, oldkey.dsize) != 0) {
1459                         /* No, it wasn't: unlock it and start from scratch */
1460                         if (unlock_record(tdb, tdb->travlocks.off) != 0)
1461                                 return tdb_null;
1462                         if (tdb_unlock(tdb, tdb->travlocks.hash, F_WRLCK) != 0)
1463                                 return tdb_null;
1464                         tdb->travlocks.off = 0;
1465                 }
1466
1467                 SAFE_FREE(k);
1468         }
1469
1470         if (!tdb->travlocks.off) {
1471                 /* No previous element: do normal find, and lock record */
1472                 tdb->travlocks.off = tdb_find_lock_hash(tdb, oldkey, tdb->hash_fn(&oldkey), F_WRLCK, &rec);
1473                 if (!tdb->travlocks.off)
1474                         return tdb_null;
1475                 tdb->travlocks.hash = BUCKET(rec.full_hash);
1476                 if (lock_record(tdb, tdb->travlocks.off) != 0) {
1477                         TDB_LOG((tdb, 0, "tdb_nextkey: lock_record failed (%s)!\n", strerror(errno)));
1478                         return tdb_null;
1479                 }
1480         }
1481         oldhash = tdb->travlocks.hash;
1482
1483         /* Grab next record: locks chain and returned record,
1484            unlocks old record */
1485         if (tdb_next_lock(tdb, &tdb->travlocks, &rec) > 0) {
1486                 key.dsize = rec.key_len;
1487                 key.dptr = tdb_alloc_read(tdb, tdb->travlocks.off+sizeof(rec),
1488                                           key.dsize);
1489                 /* Unlock the chain of this new record */
1490                 if (tdb_unlock(tdb, tdb->travlocks.hash, F_WRLCK) != 0)
1491                         TDB_LOG((tdb, 0, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
1492         }
1493         /* Unlock the chain of old record */
1494         if (tdb_unlock(tdb, BUCKET(oldhash), F_WRLCK) != 0)
1495                 TDB_LOG((tdb, 0, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
1496         return key;
1497 }
1498
1499 /* delete an entry in the database given a key */
1500 static int tdb_delete_hash(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash)
1501 {
1502         tdb_off rec_ptr;
1503         struct list_struct rec;
1504         int ret;
1505
1506         if (!(rec_ptr = tdb_find_lock_hash(tdb, key, hash, F_WRLCK, &rec)))
1507                 return -1;
1508         ret = do_delete(tdb, rec_ptr, &rec);
1509         if (tdb_unlock(tdb, BUCKET(rec.full_hash), F_WRLCK) != 0)
1510                 TDB_LOG((tdb, 0, "tdb_delete: WARNING tdb_unlock failed!\n"));
1511         return ret;
1512 }
1513
1514 int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key)
1515 {
1516         u32 hash = tdb->hash_fn(&key);
1517         return tdb_delete_hash(tdb, key, hash);
1518 }
1519
1520 /* store an element in the database, replacing any existing element
1521    with the same key
1522
1523    return 0 on success, -1 on failure
1524 */
1525 int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
1526 {
1527         struct list_struct rec;
1528         u32 hash;
1529         tdb_off rec_ptr;
1530         char *p = NULL;
1531         int ret = 0;
1532
1533         /* find which hash bucket it is in */
1534         hash = tdb->hash_fn(&key);
1535         if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
1536                 return -1;
1537
1538         /* check for it existing, on insert. */
1539         if (flag == TDB_INSERT) {
1540                 if (tdb_exists_hash(tdb, key, hash)) {
1541                         tdb->ecode = TDB_ERR_EXISTS;
1542                         goto fail;
1543                 }
1544         } else {
1545                 /* first try in-place update, on modify or replace. */
1546                 if (tdb_update_hash(tdb, key, hash, dbuf) == 0)
1547                         goto out;
1548                 if (tdb->ecode == TDB_ERR_NOEXIST &&
1549                     flag == TDB_MODIFY) {
1550                         /* if the record doesn't exist and we are in TDB_MODIFY mode then
1551                          we should fail the store */
1552                         goto fail;
1553                 }
1554         }
1555         /* reset the error code potentially set by the tdb_update() */
1556         tdb->ecode = TDB_SUCCESS;
1557
1558         /* delete any existing record - if it doesn't exist we don't
1559            care.  Doing this first reduces fragmentation, and avoids
1560            coalescing with `allocated' block before it's updated. */
1561         if (flag != TDB_INSERT)
1562                 tdb_delete_hash(tdb, key, hash);
1563
1564         /* Copy key+value *before* allocating free space in case malloc
1565            fails and we are left with a dead spot in the tdb. */
1566
1567         if (!(p = (char *)malloc(key.dsize + dbuf.dsize))) {
1568                 tdb->ecode = TDB_ERR_OOM;
1569                 goto fail;
1570         }
1571
1572         memcpy(p, key.dptr, key.dsize);
1573         if (dbuf.dsize)
1574                 memcpy(p+key.dsize, dbuf.dptr, dbuf.dsize);
1575
1576         /* we have to allocate some space */
1577         if (!(rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize, &rec)))
1578                 goto fail;
1579
1580         /* Read hash top into next ptr */
1581         if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
1582                 goto fail;
1583
1584         rec.key_len = key.dsize;
1585         rec.data_len = dbuf.dsize;
1586         rec.full_hash = hash;
1587         rec.magic = TDB_MAGIC;
1588
1589         /* write out and point the top of the hash chain at it */
1590         if (rec_write(tdb, rec_ptr, &rec) == -1
1591             || tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+dbuf.dsize)==-1
1592             || ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
1593                 /* Need to tdb_unallocate() here */
1594                 goto fail;
1595         }
1596  out:
1597         SAFE_FREE(p);
1598         tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
1599         return ret;
1600 fail:
1601         ret = -1;
1602         goto out;
1603 }
1604
1605 /* Attempt to append data to an entry in place - this only works if the new data size
1606    is <= the old data size and the key exists.
1607    on failure return -1. Record must be locked before calling.
1608 */
1609 static int tdb_append_inplace(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash, TDB_DATA new_dbuf)
1610 {
1611         struct list_struct rec;
1612         tdb_off rec_ptr;
1613
1614         /* find entry */
1615         if (!(rec_ptr = tdb_find(tdb, key, hash, &rec)))
1616                 return -1;
1617
1618         /* Append of 0 is always ok. */
1619         if (new_dbuf.dsize == 0)
1620                 return 0;
1621
1622         /* must be long enough for key, old data + new data and tailer */
1623         if (rec.rec_len < key.dsize + rec.data_len + new_dbuf.dsize + sizeof(tdb_off)) {
1624                 /* No room. */
1625                 tdb->ecode = TDB_SUCCESS; /* Not really an error */
1626                 return -1;
1627         }
1628
1629         if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len + rec.data_len,
1630                       new_dbuf.dptr, new_dbuf.dsize) == -1)
1631                 return -1;
1632
1633         /* update size */
1634         rec.data_len += new_dbuf.dsize;
1635         return rec_write(tdb, rec_ptr, &rec);
1636 }
1637
1638 /* Append to an entry. Create if not exist. */
1639
1640 int tdb_append(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA new_dbuf)
1641 {
1642         struct list_struct rec;
1643         u32 hash;
1644         tdb_off rec_ptr;
1645         char *p = NULL;
1646         int ret = 0;
1647         size_t new_data_size = 0;
1648
1649         /* find which hash bucket it is in */
1650         hash = tdb->hash_fn(&key);
1651         if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
1652                 return -1;
1653
1654         /* first try in-place. */
1655         if (tdb_append_inplace(tdb, key, hash, new_dbuf) == 0)
1656                 goto out;
1657
1658         /* reset the error code potentially set by the tdb_append_inplace() */
1659         tdb->ecode = TDB_SUCCESS;
1660
1661         /* find entry */
1662         if (!(rec_ptr = tdb_find(tdb, key, hash, &rec))) {
1663                 if (tdb->ecode != TDB_ERR_NOEXIST)
1664                         goto fail;
1665
1666                 /* Not found - create. */
1667
1668                 ret = tdb_store(tdb, key, new_dbuf, TDB_INSERT);
1669                 goto out;
1670         }
1671
1672         new_data_size = rec.data_len + new_dbuf.dsize;
1673
1674         /* Copy key+old_value+value *before* allocating free space in case malloc
1675            fails and we are left with a dead spot in the tdb. */
1676
1677         if (!(p = (char *)malloc(key.dsize + new_data_size))) {
1678                 tdb->ecode = TDB_ERR_OOM;
1679                 goto fail;
1680         }
1681
1682         /* Copy the key in place. */
1683         memcpy(p, key.dptr, key.dsize);
1684
1685         /* Now read the old data into place. */
1686         if (rec.data_len &&
1687                 tdb_read(tdb, rec_ptr + sizeof(rec) + rec.key_len, p + key.dsize, rec.data_len, 0) == -1)
1688                         goto fail;
1689
1690         /* Finally append the new data. */
1691         if (new_dbuf.dsize)
1692                 memcpy(p+key.dsize+rec.data_len, new_dbuf.dptr, new_dbuf.dsize);
1693
1694         /* delete any existing record - if it doesn't exist we don't
1695            care.  Doing this first reduces fragmentation, and avoids
1696            coalescing with `allocated' block before it's updated. */
1697
1698         tdb_delete_hash(tdb, key, hash);
1699
1700         if (!(rec_ptr = tdb_allocate(tdb, key.dsize + new_data_size, &rec)))
1701                 goto fail;
1702
1703         /* Read hash top into next ptr */
1704         if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
1705                 goto fail;
1706
1707         rec.key_len = key.dsize;
1708         rec.data_len = new_data_size;
1709         rec.full_hash = hash;
1710         rec.magic = TDB_MAGIC;
1711
1712         /* write out and point the top of the hash chain at it */
1713         if (rec_write(tdb, rec_ptr, &rec) == -1
1714             || tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+new_data_size)==-1
1715             || ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
1716                 /* Need to tdb_unallocate() here */
1717                 goto fail;
1718         }
1719
1720  out:
1721         SAFE_FREE(p);
1722         tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
1723         return ret;
1724
1725 fail:
1726         ret = -1;
1727         goto out;
1728 }
1729
1730 static int tdb_already_open(dev_t device,
1731                             ino_t ino)
1732 {
1733         TDB_CONTEXT *i;
1734
1735         for (i = tdbs; i; i = i->next) {
1736                 if (i->device == device && i->inode == ino) {
1737                         return 1;
1738                 }
1739         }
1740
1741         return 0;
1742 }
1743
1744 /* open the database, creating it if necessary
1745
1746    The open_flags and mode are passed straight to the open call on the
1747    database file. A flags value of O_WRONLY is invalid. The hash size
1748    is advisory, use zero for a default value.
1749
1750    Return is NULL on error, in which case errno is also set.  Don't
1751    try to call tdb_error or tdb_errname, just do strerror(errno).
1752
1753    @param name may be NULL for internal databases. */
1754 TDB_CONTEXT *tdb_open(const char *name, int hash_size, int tdb_flags,
1755                       int open_flags, mode_t mode)
1756 {
1757         return tdb_open_ex(name, hash_size, tdb_flags, open_flags, mode, NULL, NULL);
1758 }
1759
1760 /* a default logging function */
1761 static void null_log_fn(TDB_CONTEXT *tdb, int level, const char *fmt, ...)
1762 {
1763 }
1764
1765
1766 TDB_CONTEXT *tdb_open_ex(const char *name, int hash_size, int tdb_flags,
1767                          int open_flags, mode_t mode,
1768                          tdb_log_func log_fn,
1769                          tdb_hash_func hash_fn)
1770 {
1771         TDB_CONTEXT *tdb;
1772         struct stat st;
1773         int rev = 0, locked = 0;
1774         uint8_t *vp;
1775         u32 vertest;
1776
1777         if (!(tdb = calloc(1, sizeof *tdb))) {
1778                 /* Can't log this */
1779                 errno = ENOMEM;
1780                 goto fail;
1781         }
1782         tdb->fd = -1;
1783         tdb->name = NULL;
1784         tdb->map_ptr = NULL;
1785         tdb->flags = tdb_flags;
1786         tdb->open_flags = open_flags;
1787         tdb->log_fn = log_fn?log_fn:null_log_fn;
1788         tdb->hash_fn = hash_fn ? hash_fn : default_tdb_hash;
1789
1790         if ((open_flags & O_ACCMODE) == O_WRONLY) {
1791                 TDB_LOG((tdb, 0, "tdb_open_ex: can't open tdb %s write-only\n",
1792                          name));
1793                 errno = EINVAL;
1794                 goto fail;
1795         }
1796
1797         if (hash_size == 0)
1798                 hash_size = DEFAULT_HASH_SIZE;
1799         if ((open_flags & O_ACCMODE) == O_RDONLY) {
1800                 tdb->read_only = 1;
1801                 /* read only databases don't do locking or clear if first */
1802                 tdb->flags |= TDB_NOLOCK;
1803                 tdb->flags &= ~TDB_CLEAR_IF_FIRST;
1804         }
1805
1806         /* internal databases don't mmap or lock, and start off cleared */
1807         if (tdb->flags & TDB_INTERNAL) {
1808                 tdb->flags |= (TDB_NOLOCK | TDB_NOMMAP);
1809                 tdb->flags &= ~TDB_CLEAR_IF_FIRST;
1810                 if (tdb_new_database(tdb, hash_size) != 0) {
1811                         TDB_LOG((tdb, 0, "tdb_open_ex: tdb_new_database failed!"));
1812                         goto fail;
1813                 }
1814                 goto internal;
1815         }
1816
1817         if ((tdb->fd = open(name, open_flags, mode)) == -1) {
1818                 TDB_LOG((tdb, 5, "tdb_open_ex: could not open file %s: %s\n",
1819                          name, strerror(errno)));
1820                 goto fail;      /* errno set by open(2) */
1821         }
1822
1823         /* ensure there is only one process initialising at once */
1824         if (tdb_brlock(tdb, GLOBAL_LOCK, F_WRLCK, F_SETLKW, 0) == -1) {
1825                 TDB_LOG((tdb, 0, "tdb_open_ex: failed to get global lock on %s: %s\n",
1826                          name, strerror(errno)));
1827                 goto fail;      /* errno set by tdb_brlock */
1828         }
1829
1830         /* we need to zero database if we are the only one with it open */
1831         if ((tdb_flags & TDB_CLEAR_IF_FIRST) &&
1832                 (locked = (tdb_brlock(tdb, ACTIVE_LOCK, F_WRLCK, F_SETLK, 0) == 0))) {
1833                 open_flags |= O_CREAT;
1834                 if (ftruncate(tdb->fd, 0) == -1) {
1835                         TDB_LOG((tdb, 0, "tdb_open_ex: "
1836                                  "failed to truncate %s: %s\n",
1837                                  name, strerror(errno)));
1838                         goto fail; /* errno set by ftruncate */
1839                 }
1840         }
1841
1842         if (read(tdb->fd, &tdb->header, sizeof(tdb->header)) != sizeof(tdb->header)
1843             || strcmp(tdb->header.magic_food, TDB_MAGIC_FOOD) != 0
1844             || (tdb->header.version != TDB_VERSION
1845                 && !(rev = (tdb->header.version==TDB_BYTEREV(TDB_VERSION))))) {
1846                 /* its not a valid database - possibly initialise it */
1847                 if (!(open_flags & O_CREAT) || tdb_new_database(tdb, hash_size) == -1) {
1848                         errno = EIO; /* ie bad format or something */
1849                         goto fail;
1850                 }
1851                 rev = (tdb->flags & TDB_CONVERT);
1852         }
1853         vp = (uint8_t *)&tdb->header.version;
1854         vertest = (((u32)vp[0]) << 24) | (((u32)vp[1]) << 16) |
1855                   (((u32)vp[2]) << 8) | (u32)vp[3];
1856         tdb->flags |= (vertest==TDB_VERSION) ? TDB_BIGENDIAN : 0;
1857         if (!rev)
1858                 tdb->flags &= ~TDB_CONVERT;
1859         else {
1860                 tdb->flags |= TDB_CONVERT;
1861                 convert(&tdb->header, sizeof(tdb->header));
1862         }
1863         if (fstat(tdb->fd, &st) == -1)
1864                 goto fail;
1865
1866         /* Is it already in the open list?  If so, fail. */
1867         if (tdb_already_open(st.st_dev, st.st_ino)) {
1868                 TDB_LOG((tdb, 2, "tdb_open_ex: "
1869                          "%s (%d,%d) is already open in this process\n",
1870                          name, (int)st.st_dev, (int)st.st_ino));
1871                 errno = EBUSY;
1872                 goto fail;
1873         }
1874
1875         if (!(tdb->name = (char *)strdup(name))) {
1876                 errno = ENOMEM;
1877                 goto fail;
1878         }
1879
1880         tdb->map_size = st.st_size;
1881         tdb->device = st.st_dev;
1882         tdb->inode = st.st_ino;
1883         tdb->locked = calloc(tdb->header.hash_size+1, sizeof(tdb->locked[0]));
1884         if (!tdb->locked) {
1885                 TDB_LOG((tdb, 2, "tdb_open_ex: "
1886                          "failed to allocate lock structure for %s\n",
1887                          name));
1888                 errno = ENOMEM;
1889                 goto fail;
1890         }
1891         tdb_mmap(tdb);
1892         if (locked) {
1893                 if (!tdb->read_only)
1894                         if (tdb_clear_spinlocks(tdb) != 0) {
1895                                 TDB_LOG((tdb, 0, "tdb_open_ex: "
1896                                 "failed to clear spinlock\n"));
1897                                 goto fail;
1898                         }
1899                 if (tdb_brlock(tdb, ACTIVE_LOCK, F_UNLCK, F_SETLK, 0) == -1) {
1900                         TDB_LOG((tdb, 0, "tdb_open_ex: "
1901                                  "failed to take ACTIVE_LOCK on %s: %s\n",
1902                                  name, strerror(errno)));
1903                         goto fail;
1904                 }
1905
1906         }
1907
1908         /* We always need to do this if the CLEAR_IF_FIRST flag is set, even if
1909            we didn't get the initial exclusive lock as we need to let all other
1910            users know we're using it. */
1911
1912         if (tdb_flags & TDB_CLEAR_IF_FIRST) {
1913         /* leave this lock in place to indicate it's in use */
1914         if (tdb_brlock(tdb, ACTIVE_LOCK, F_RDLCK, F_SETLKW, 0) == -1)
1915                 goto fail;
1916         }
1917
1918
1919  internal:
1920         /* Internal (memory-only) databases skip all the code above to
1921          * do with disk files, and resume here by releasing their
1922          * global lock and hooking into the active list. */
1923         if (tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0) == -1)
1924                 goto fail;
1925         tdb->next = tdbs;
1926         tdbs = tdb;
1927         return tdb;
1928
1929  fail:
1930         { int save_errno = errno;
1931
1932         if (!tdb)
1933                 return NULL;
1934
1935         if (tdb->map_ptr) {
1936                 if (tdb->flags & TDB_INTERNAL)
1937                         SAFE_FREE(tdb->map_ptr);
1938                 else
1939                         tdb_munmap(tdb);
1940         }
1941         SAFE_FREE(tdb->name);
1942         if (tdb->fd != -1)
1943                 if (close(tdb->fd) != 0)
1944                         TDB_LOG((tdb, 5, "tdb_open_ex: failed to close tdb->fd on error!\n"));
1945         SAFE_FREE(tdb->locked);
1946         SAFE_FREE(tdb);
1947         errno = save_errno;
1948         return NULL;
1949         }
1950 }
1951
1952 /**
1953  * Close a database.
1954  *
1955  * @returns -1 for error; 0 for success.
1956  **/
1957 int tdb_close(TDB_CONTEXT *tdb)
1958 {
1959         TDB_CONTEXT **i;
1960         int ret = 0;
1961
1962         if (tdb->map_ptr) {
1963                 if (tdb->flags & TDB_INTERNAL)
1964                         SAFE_FREE(tdb->map_ptr);
1965                 else
1966                         tdb_munmap(tdb);
1967         }
1968         SAFE_FREE(tdb->name);
1969         if (tdb->fd != -1)
1970                 ret = close(tdb->fd);
1971         SAFE_FREE(tdb->locked);
1972
1973         /* Remove from contexts list */
1974         for (i = &tdbs; *i; i = &(*i)->next) {
1975                 if (*i == tdb) {
1976                         *i = tdb->next;
1977                         break;
1978                 }
1979         }
1980
1981         memset(tdb, 0, sizeof(*tdb));
1982         SAFE_FREE(tdb);
1983
1984         return ret;
1985 }
1986
1987 /* lock/unlock entire database */
1988 int tdb_lockall(TDB_CONTEXT *tdb)
1989 {
1990         u32 i;
1991
1992         /* There are no locks on read-only dbs */
1993         if (tdb->read_only)
1994                 return TDB_ERRCODE(TDB_ERR_LOCK, -1);
1995         for (i = 0; i < tdb->header.hash_size; i++)
1996                 if (tdb_lock(tdb, i, F_WRLCK))
1997                         break;
1998
1999         /* If error, release locks we have... */
2000         if (i < tdb->header.hash_size) {
2001                 u32 j;
2002
2003                 for ( j = 0; j < i; j++)
2004                         tdb_unlock(tdb, j, F_WRLCK);
2005                 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
2006         }
2007
2008         return 0;
2009 }
2010 void tdb_unlockall(TDB_CONTEXT *tdb)
2011 {
2012         u32 i;
2013         for (i=0; i < tdb->header.hash_size; i++)
2014                 tdb_unlock(tdb, i, F_WRLCK);
2015 }
2016
2017 /* lock/unlock one hash chain. This is meant to be used to reduce
2018    contention - it cannot guarantee how many records will be locked */
2019 int tdb_chainlock(TDB_CONTEXT *tdb, TDB_DATA key)
2020 {
2021         return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
2022 }
2023
2024 int tdb_chainunlock(TDB_CONTEXT *tdb, TDB_DATA key)
2025 {
2026         return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
2027 }
2028
2029 int tdb_chainlock_read(TDB_CONTEXT *tdb, TDB_DATA key)
2030 {
2031         return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK);
2032 }
2033
2034 int tdb_chainunlock_read(TDB_CONTEXT *tdb, TDB_DATA key)
2035 {
2036         return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK);
2037 }
2038
2039
2040 /* register a loging function */
2041 void tdb_logging_function(TDB_CONTEXT *tdb, void (*fn)(TDB_CONTEXT *, int , const char *, ...))
2042 {
2043         tdb->log_fn = fn?fn:null_log_fn;
2044 }
2045
2046
2047 /* reopen a tdb - this can be used after a fork to ensure that we have an independent
2048    seek pointer from our parent and to re-establish locks */
2049 int tdb_reopen(TDB_CONTEXT *tdb)
2050 {
2051         struct stat st;
2052
2053         if (tdb->flags & TDB_INTERNAL)
2054                 return 0; /* Nothing to do. */
2055         if (tdb_munmap(tdb) != 0) {
2056                 TDB_LOG((tdb, 0, "tdb_reopen: munmap failed (%s)\n", strerror(errno)));
2057                 goto fail;
2058         }
2059         if (close(tdb->fd) != 0)
2060                 TDB_LOG((tdb, 0, "tdb_reopen: WARNING closing tdb->fd failed!\n"));
2061         tdb->fd = open(tdb->name, tdb->open_flags & ~(O_CREAT|O_TRUNC), 0);
2062         if (tdb->fd == -1) {
2063                 TDB_LOG((tdb, 0, "tdb_reopen: open failed (%s)\n", strerror(errno)));
2064                 goto fail;
2065         }
2066         if (fstat(tdb->fd, &st) != 0) {
2067                 TDB_LOG((tdb, 0, "tdb_reopen: fstat failed (%s)\n", strerror(errno)));
2068                 goto fail;
2069         }
2070         if (st.st_ino != tdb->inode || st.st_dev != tdb->device) {
2071                 TDB_LOG((tdb, 0, "tdb_reopen: file dev/inode has changed!\n"));
2072                 goto fail;
2073         }
2074         tdb_mmap(tdb);
2075         if ((tdb->flags & TDB_CLEAR_IF_FIRST) && (tdb_brlock(tdb, ACTIVE_LOCK, F_RDLCK, F_SETLKW, 0) == -1)) {
2076                 TDB_LOG((tdb, 0, "tdb_reopen: failed to obtain active lock\n"));
2077                 goto fail;
2078         }
2079
2080         return 0;
2081
2082 fail:
2083         tdb_close(tdb);
2084         return -1;
2085 }
2086
2087 /* reopen all tdb's */
2088 int tdb_reopen_all(void)
2089 {
2090         TDB_CONTEXT *tdb;
2091
2092         for (tdb=tdbs; tdb; tdb = tdb->next) {
2093                 /* Ensure no clear-if-first. */
2094                 tdb->flags &= ~TDB_CLEAR_IF_FIRST;
2095                 if (tdb_reopen(tdb) != 0)
2096                         return -1;
2097         }
2098
2099         return 0;
2100 }