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