lib/tdb/common/freelist.c

   1  /*
   2    Unix SMB/CIFS implementation.
   3
   4    trivial database library
   5
   6    Copyright (C) Andrew Tridgell              1999-2005
   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 3 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, see <http://www.gnu.org/licenses/>.
  26 */
  27
  28 #include "tdb_private.h"
  29
  30 /* 'right' merges can involve O(n^2) cost when combined with a
  31    traverse, so they are disabled until we find a way to do them in
  32    O(1) time
  33 */
  34 #define USE_RIGHT_MERGES 0
  35
  36 /* read a freelist record and check for simple errors */
  37 int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct tdb_record *rec)
  38 {
  39         if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
  40                 return -1;
  41
  42         if (rec->magic == TDB_MAGIC) {
  43                 /* this happens when a app is showdown while deleting a record - we should
  44                    not completely fail when this happens */
  45                 TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read non-free magic 0x%x at offset=%u - fixing\n",
  46                          rec->magic, off));
  47                 rec->magic = TDB_FREE_MAGIC;
  48                 if (tdb_rec_write(tdb, off, rec) == -1)
  49                         return -1;
  50         }
  51
  52         if (rec->magic != TDB_FREE_MAGIC) {
  53                 /* Ensure ecode is set for log fn. */
  54                 tdb->ecode = TDB_ERR_CORRUPT;
  55                 TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read bad magic 0x%x at offset=%u\n",
  56                            rec->magic, off));
  57                 return -1;
  58         }
  59         if (tdb->methods->tdb_oob(tdb, rec->next, sizeof(*rec), 0) != 0)
  60                 return -1;
  61         return 0;
  62 }
  63
  64
  65 #if USE_RIGHT_MERGES
  66 /* Remove an element from the freelist.  Must have alloc lock. */
  67 static int remove_from_freelist(struct tdb_context *tdb, tdb_off_t off, tdb_off_t next)
  68 {
  69         tdb_off_t last_ptr, i;
  70
  71         /* read in the freelist top */
  72         last_ptr = FREELIST_TOP;
  73         while (tdb_ofs_read(tdb, last_ptr, &i) != -1 && i != 0) {
  74                 if (i == off) {
  75                         /* We've found it! */
  76                         return tdb_ofs_write(tdb, last_ptr, &next);
  77                 }
  78                 /* Follow chain (next offset is at start of record) */
  79                 last_ptr = i;
  80         }
  81         tdb->ecode = TDB_ERR_CORRUPT;
  82         TDB_LOG((tdb, TDB_DEBUG_FATAL,"remove_from_freelist: not on list at off=%u\n", off));
  83         return -1;
  84 }
  85 #endif
  86
  87
  88 /* update a record tailer (must hold allocation lock) */
  89 static int update_tailer(struct tdb_context *tdb, tdb_off_t offset,
  90                          const struct tdb_record *rec)
  91 {
  92         tdb_off_t totalsize;
  93
  94         /* Offset of tailer from record header */
  95         totalsize = sizeof(*rec) + rec->rec_len;
  96         return tdb_ofs_write(tdb, offset + totalsize - sizeof(tdb_off_t),
  97                          &totalsize);
  98 }
  99
 100 /**
 101  * Read the record directly on the left.
 102  * Fail if there is no record on the left.
 103  */
 104 static int read_record_on_left(struct tdb_context *tdb, tdb_off_t rec_ptr,
 105                                tdb_off_t *left_p,
 106                                struct tdb_record *left_r)
 107 {
 108         tdb_off_t left_ptr;
 109         tdb_off_t left_size;
 110         struct tdb_record left_rec;
 111         int ret;
 112
 113         left_ptr = rec_ptr - sizeof(tdb_off_t);
 114
 115         if (left_ptr <= TDB_DATA_START(tdb->hash_size)) {
 116                 /* no record on the left */
 117                 return -1;
 118         }
 119
 120         /* Read in tailer and jump back to header */
 121         ret = tdb_ofs_read(tdb, left_ptr, &left_size);
 122         if (ret == -1) {
 123                 TDB_LOG((tdb, TDB_DEBUG_FATAL,
 124                         "tdb_free: left offset read failed at %u\n", left_ptr));
 125                 return -1;
 126         }
 127
 128         /* it could be uninitialised data */
 129         if (left_size == 0 || left_size == TDB_PAD_U32) {
 130                 return -1;
 131         }
 132
 133         if (left_size > rec_ptr) {
 134                 return -1;
 135         }
 136
 137         left_ptr = rec_ptr - left_size;
 138
 139         if (left_ptr < TDB_DATA_START(tdb->hash_size)) {
 140                 return -1;
 141         }
 142
 143         /* Now read in the left record */
 144         ret = tdb->methods->tdb_read(tdb, left_ptr, &left_rec,
 145                                      sizeof(left_rec), DOCONV());
 146         if (ret == -1) {
 147                 TDB_LOG((tdb, TDB_DEBUG_FATAL,
 148                          "tdb_free: left read failed at %u (%u)\n",
 149                          left_ptr, left_size));
 150                 return -1;
 151         }
 152
 153         *left_p = left_ptr;
 154         *left_r = left_rec;
 155
 156         return 0;
 157 }
 158
 159 /**
 160  * Merge new freelist record with the direct left neighbour.
 161  * This assumes that left_rec represents the record
 162  * directly to the left of right_rec and that this is
 163  * a freelist record.
 164  */
 165 static int merge_with_left_record(struct tdb_context *tdb,
 166                                   tdb_off_t left_ptr,
 167                                   struct tdb_record *left_rec,
 168                                   struct tdb_record *right_rec)
 169 {
 170         int ret;
 171
 172         left_rec->rec_len += sizeof(*right_rec) + right_rec->rec_len;
 173
 174         ret = tdb_rec_write(tdb, left_ptr, left_rec);
 175         if (ret == -1) {
 176                 TDB_LOG((tdb, TDB_DEBUG_FATAL,
 177                          "merge_with_left_record: update_left failed at %u\n",
 178                          left_ptr));
 179                 return -1;
 180         }
 181
 182         ret = update_tailer(tdb, left_ptr, left_rec);
 183         if (ret == -1) {
 184                 TDB_LOG((tdb, TDB_DEBUG_FATAL,
 185                          "merge_with_left_record: update_tailer failed at %u\n",
 186                          left_ptr));
 187                 return -1;
 188         }
 189
 190         return 0;
 191 }
 192
 193 /**
 194  * Check whether the record left of a given freelist record is
 195  * also a freelist record, and if so, merge the two records.
 196  *
 197  * Return code:
 198  *  -1 upon error
 199  *   0 if left was not a free record
 200  *   1 if left was free and successfully merged.
 201  *
 202  * The currend record is handed in with pointer and fully read record.
 203  *
 204  * The left record pointer and struct can be retrieved as result
 205  * in lp and lr;
 206  */
 207 static int check_merge_with_left_record(struct tdb_context *tdb,
 208                                         tdb_off_t rec_ptr,
 209                                         struct tdb_record *rec,
 210                                         tdb_off_t *lp,
 211                                         struct tdb_record *lr)
 212 {
 213         tdb_off_t left_ptr;
 214         struct tdb_record left_rec;
 215         int ret;
 216
 217         ret = read_record_on_left(tdb, rec_ptr, &left_ptr, &left_rec);
 218         if (ret != 0) {
 219                 return 0;
 220         }
 221
 222         if (left_rec.magic != TDB_FREE_MAGIC) {
 223                 return 0;
 224         }
 225
 226         /* It's free - expand to include it. */
 227         ret = merge_with_left_record(tdb, left_ptr, &left_rec, rec);
 228         if (ret != 0) {
 229                 return -1;
 230         }
 231
 232         if (lp != NULL) {
 233                 *lp = left_ptr;
 234         }
 235
 236         if (lr != NULL) {
 237                 *lr = left_rec;
 238         }
 239
 240         return 1;
 241 }
 242
 243 /**
 244  * Check whether the record left of a given freelist record is
 245  * also a freelist record, and if so, merge the two records.
 246  *
 247  * Return code:
 248  *  -1 upon error
 249  *   0 if left was not a free record
 250  *   1 if left was free and successfully merged.
 251  *
 252  * In this variant, the input record is specified just as the pointer
 253  * and is read from the database if needed.
 254  *
 255  * next_ptr will contain the original record's next pointer after
 256  * successful merging (which will be lost after merging), so that
 257  * the caller can update the last pointer.
 258  */
 259 static int check_merge_ptr_with_left_record(struct tdb_context *tdb,
 260                                             tdb_off_t rec_ptr,
 261                                             tdb_off_t *next_ptr)
 262 {
 263         tdb_off_t left_ptr;
 264         struct tdb_record rec, left_rec;
 265         int ret;
 266
 267         ret = read_record_on_left(tdb, rec_ptr, &left_ptr, &left_rec);
 268         if (ret != 0) {
 269                 return 0;
 270         }
 271
 272         if (left_rec.magic != TDB_FREE_MAGIC) {
 273                 return 0;
 274         }
 275
 276         /* It's free - expand to include it. */
 277
 278         ret = tdb->methods->tdb_read(tdb, rec_ptr, &rec,
 279                                      sizeof(rec), DOCONV());
 280         if (ret != 0) {
 281                 return -1;
 282         }
 283
 284         ret = merge_with_left_record(tdb, left_ptr, &left_rec, &rec);
 285         if (ret != 0) {
 286                 return -1;
 287         }
 288
 289         if (next_ptr != NULL) {
 290                 *next_ptr = rec.next;
 291         }
 292
 293         return 1;
 294 }
 295
 296 /**
 297  * Add an element into the freelist.
 298  *
 299  * We merge the new record into the left record if it is also a
 300  * free record, but not with the right one. This makes the
 301  * operation O(1) instead of O(n): merging with the right record
 302  * requires a traverse of the freelist to find the previous
 303  * record in the free list.
 304  *
 305  * This prevents db traverses from being O(n^2) after a lot of deletes.
 306  */
 307 int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec)
 308 {
 309         int ret;
 310
 311         /* Allocation and tailer lock */
 312         if (tdb_lock(tdb, -1, F_WRLCK) != 0)
 313                 return -1;
 314
 315         /* set an initial tailer, so if we fail we don't leave a bogus record */
 316         if (update_tailer(tdb, offset, rec) != 0) {
 317                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed!\n"));
 318                 goto fail;
 319         }
 320
 321 #if USE_RIGHT_MERGES
 322         /* Look right first (I'm an Australian, dammit) */
 323         if (offset + sizeof(*rec) + rec->rec_len + sizeof(*rec) <= tdb->map_size) {
 324                 tdb_off_t right = offset + sizeof(*rec) + rec->rec_len;
 325                 struct tdb_record r;
 326
 327                 if (tdb->methods->tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) {
 328                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: right read failed at %u\n", right));
 329                         goto left;
 330                 }
 331
 332                 /* If it's free, expand to include it. */
 333                 if (r.magic == TDB_FREE_MAGIC) {
 334                         if (remove_from_freelist(tdb, right, r.next) == -1) {
 335                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: right free failed at %u\n", right));
 336                                 goto left;
 337                         }
 338                         rec->rec_len += sizeof(r) + r.rec_len;
 339                         if (update_tailer(tdb, offset, rec) == -1) {
 340                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset));
 341                                 goto fail;
 342                         }
 343                 }
 344         }
 345 left:
 346 #endif
 347
 348         ret = check_merge_with_left_record(tdb, offset, rec, NULL, NULL);
 349         if (ret == -1) {
 350                 goto fail;
 351         }
 352         if (ret == 1) {
 353                 /* merged */
 354                 goto done;
 355         }
 356
 357         /* Nothing to merge, prepend to free list */
 358
 359         rec->magic = TDB_FREE_MAGIC;
 360
 361         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
 362             tdb_rec_write(tdb, offset, rec) == -1 ||
 363             tdb_ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
 364                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free record write failed at offset=%u\n", offset));
 365                 goto fail;
 366         }
 367
 368 done:
 369         /* And we're done. */
 370         tdb_unlock(tdb, -1, F_WRLCK);
 371         return 0;
 372
 373  fail:
 374         tdb_unlock(tdb, -1, F_WRLCK);
 375         return -1;
 376 }
 377
 378
 379
 380 /*
 381    the core of tdb_allocate - called when we have decided which
 382    free list entry to use
 383
 384    Note that we try to allocate by grabbing data from the end of an existing record,
 385    not the beginning. This is so the left merge in a free is more likely to be
 386    able to free up the record without fragmentation
 387  */
 388 static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb,
 389                                   tdb_len_t length, tdb_off_t rec_ptr,
 390                                   struct tdb_record *rec, tdb_off_t last_ptr)
 391 {
 392 #define MIN_REC_SIZE (sizeof(struct tdb_record) + sizeof(tdb_off_t) + 8)
 393
 394         if (rec->rec_len < length + MIN_REC_SIZE) {
 395                 /* we have to grab the whole record */
 396
 397                 /* unlink it from the previous record */
 398                 if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) {
 399                         return 0;
 400                 }
 401
 402                 /* mark it not free */
 403                 rec->magic = TDB_MAGIC;
 404                 if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
 405                         return 0;
 406                 }
 407                 return rec_ptr;
 408         }
 409
 410         /* we're going to just shorten the existing record */
 411         rec->rec_len -= (length + sizeof(*rec));
 412         if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
 413                 return 0;
 414         }
 415         if (update_tailer(tdb, rec_ptr, rec) == -1) {
 416                 return 0;
 417         }
 418
 419         /* and setup the new record */
 420         rec_ptr += sizeof(*rec) + rec->rec_len;
 421
 422         memset(rec, '\0', sizeof(*rec));
 423         rec->rec_len = length;
 424         rec->magic = TDB_MAGIC;
 425
 426         if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
 427                 return 0;
 428         }
 429
 430         if (update_tailer(tdb, rec_ptr, rec) == -1) {
 431                 return 0;
 432         }
 433
 434         return rec_ptr;
 435 }
 436
 437 /* allocate some space from the free list. The offset returned points
 438    to a unconnected tdb_record within the database with room for at
 439    least length bytes of total data
 440
 441    0 is returned if the space could not be allocated
 442  */
 443 static tdb_off_t tdb_allocate_from_freelist(
 444         struct tdb_context *tdb, tdb_len_t length, struct tdb_record *rec)
 445 {
 446         tdb_off_t rec_ptr, last_ptr, newrec_ptr;
 447         struct {
 448                 tdb_off_t rec_ptr, last_ptr;
 449                 tdb_len_t rec_len;
 450         } bestfit;
 451         float multiplier = 1.0;
 452
 453         /* over-allocate to reduce fragmentation */
 454         length *= 1.25;
 455
 456         /* Extra bytes required for tailer */
 457         length += sizeof(tdb_off_t);
 458         length = TDB_ALIGN(length, TDB_ALIGNMENT);
 459
 460  again:
 461         last_ptr = FREELIST_TOP;
 462
 463         /* read in the freelist top */
 464         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
 465                 return 0;
 466
 467         bestfit.rec_ptr = 0;
 468         bestfit.last_ptr = 0;
 469         bestfit.rec_len = 0;
 470
 471         /*
 472            this is a best fit allocation strategy. Originally we used
 473            a first fit strategy, but it suffered from massive fragmentation
 474            issues when faced with a slowly increasing record size.
 475          */
 476         while (rec_ptr) {
 477                 if (tdb_rec_free_read(tdb, rec_ptr, rec) == -1) {
 478                         return 0;
 479                 }
 480
 481                 if (rec->rec_len >= length) {
 482                         if (bestfit.rec_ptr == 0 ||
 483                             rec->rec_len < bestfit.rec_len) {
 484                                 bestfit.rec_len = rec->rec_len;
 485                                 bestfit.rec_ptr = rec_ptr;
 486                                 bestfit.last_ptr = last_ptr;
 487                         }
 488                 }
 489
 490                 /* move to the next record */
 491                 last_ptr = rec_ptr;
 492                 rec_ptr = rec->next;
 493
 494                 /* if we've found a record that is big enough, then
 495                    stop searching if its also not too big. The
 496                    definition of 'too big' changes as we scan
 497                    through */
 498                 if (bestfit.rec_len > 0 &&
 499                     bestfit.rec_len < length * multiplier) {
 500                         break;
 501                 }
 502
 503                 /* this multiplier means we only extremely rarely
 504                    search more than 50 or so records. At 50 records we
 505                    accept records up to 11 times larger than what we
 506                    want */
 507                 multiplier *= 1.05;
 508         }
 509
 510         if (bestfit.rec_ptr != 0) {
 511                 if (tdb_rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
 512                         return 0;
 513                 }
 514
 515                 newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr,
 516                                               rec, bestfit.last_ptr);
 517                 return newrec_ptr;
 518         }
 519
 520         /* we didn't find enough space. See if we can expand the
 521            database and if we can then try again */
 522         if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
 523                 goto again;
 524
 525         return 0;
 526 }
 527
 528 static bool tdb_alloc_dead(
 529         struct tdb_context *tdb, int hash, tdb_len_t length,
 530         tdb_off_t *rec_ptr, struct tdb_record *rec)
 531 {
 532         tdb_off_t last_ptr;
 533
 534         *rec_ptr = tdb_find_dead(tdb, hash, rec, length, &last_ptr);
 535         if (*rec_ptr == 0) {
 536                 return false;
 537         }
 538         /*
 539          * Unlink the record from the hash chain, it's about to be moved into
 540          * another one.
 541          */
 542         return (tdb_ofs_write(tdb, last_ptr, &rec->next) == 0);
 543 }
 544
 545 /*
 546  * Chain "hash" is assumed to be locked
 547  */
 548
 549 tdb_off_t tdb_allocate(struct tdb_context *tdb, int hash, tdb_len_t length,
 550                        struct tdb_record *rec)
 551 {
 552         tdb_off_t ret;
 553         int i;
 554
 555         if (tdb->max_dead_records == 0) {
 556                 /*
 557                  * No dead records to expect anywhere. Do the blocking
 558                  * freelist lock without trying to steal from others
 559                  */
 560                 goto blocking_freelist_allocate;
 561         }
 562
 563         /*
 564          * The following loop tries to get the freelist lock nonblocking. If
 565          * it gets the lock, allocate from there. If the freelist is busy,
 566          * instead of waiting we try to steal dead records from other hash
 567          * chains.
 568          *
 569          * Be aware that we do nonblocking locks on the other hash chains as
 570          * well and fail gracefully. This way we avoid deadlocks (we block two
 571          * hash chains, something which is pretty bad normally)
 572          */
 573
 574         for (i=0; i<tdb->hash_size; i++) {
 575
 576                 int list;
 577
 578                 list = BUCKET(hash+i);
 579
 580                 if (tdb_lock_nonblock(tdb, list, F_WRLCK) == 0) {
 581                         bool got_dead;
 582
 583                         got_dead = tdb_alloc_dead(tdb, list, length, &ret, rec);
 584                         tdb_unlock(tdb, list, F_WRLCK);
 585
 586                         if (got_dead) {
 587                                 return ret;
 588                         }
 589                 }
 590
 591                 if (tdb_lock_nonblock(tdb, -1, F_WRLCK) == 0) {
 592                         /*
 593                          * Under the freelist lock take the chance to give
 594                          * back our dead records.
 595                          */
 596                         tdb_purge_dead(tdb, hash);
 597
 598                         ret = tdb_allocate_from_freelist(tdb, length, rec);
 599                         tdb_unlock(tdb, -1, F_WRLCK);
 600                         return ret;
 601                 }
 602         }
 603
 604 blocking_freelist_allocate:
 605
 606         if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
 607                 return 0;
 608         }
 609         ret = tdb_allocate_from_freelist(tdb, length, rec);
 610         tdb_unlock(tdb, -1, F_WRLCK);
 611         return ret;
 612 }
 613
 614 /**
 615  * Merge adjacent records in the freelist.
 616  */
 617 static int tdb_freelist_merge_adjacent(struct tdb_context *tdb,
 618                                        int *count_records, int *count_merged)
 619 {
 620         tdb_off_t cur, next;
 621         int count = 0;
 622         int merged = 0;
 623         int ret;
 624
 625         ret = tdb_lock(tdb, -1, F_RDLCK);
 626         if (ret == -1) {
 627                 return -1;
 628         }
 629
 630         cur = FREELIST_TOP;
 631         while (tdb_ofs_read(tdb, cur, &next) == 0 && next != 0) {
 632                 tdb_off_t next2;
 633
 634                 count++;
 635
 636                 ret = check_merge_ptr_with_left_record(tdb, next, &next2);
 637                 if (ret == -1) {
 638                         goto done;
 639                 }
 640                 if (ret == 1) {
 641                         /*
 642                          * merged:
 643                          * now let cur->next point to next2 instead of next
 644                          */
 645
 646                         ret = tdb_ofs_write(tdb, cur, &next2);
 647                         if (ret != 0) {
 648                                 goto done;
 649                         }
 650
 651                         next = next2;
 652                         merged++;
 653                 }
 654
 655                 cur = next;
 656         }
 657
 658         if (count_records != NULL) {
 659                 *count_records = count;
 660         }
 661
 662         if (count_merged != NULL) {
 663                 *count_merged = merged;
 664         }
 665
 666         ret = 0;
 667
 668 done:
 669         tdb_unlock(tdb, -1, F_RDLCK);
 670         return ret;
 671 }
 672
 673 /*
 674    return the size of the freelist - used to decide if we should repack
 675 */
 676 _PUBLIC_ int tdb_freelist_size(struct tdb_context *tdb)
 677 {
 678         tdb_off_t ptr;
 679         int count=0;
 680
 681         if (tdb_lock(tdb, -1, F_RDLCK) == -1) {
 682                 return -1;
 683         }
 684
 685         ptr = FREELIST_TOP;
 686         while (tdb_ofs_read(tdb, ptr, &ptr) == 0 && ptr != 0) {
 687                 count++;
 688         }
 689
 690         tdb_unlock(tdb, -1, F_RDLCK);
 691         return count;
 692 }