source3/tdb/tdb.c

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