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