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 tdb_chainwalk_ctx chainwalk;
 448         bool modified;
 449         struct {
 450                 tdb_off_t rec_ptr, last_ptr;
 451                 tdb_len_t rec_len;
 452         } bestfit;
 453         float multiplier = 1.0;
 454         bool merge_created_candidate;
 455
 456         /* over-allocate to reduce fragmentation */
 457         length *= 1.25;
 458
 459         /* Extra bytes required for tailer */
 460         length += sizeof(tdb_off_t);
 461         length = TDB_ALIGN(length, TDB_ALIGNMENT);
 462
 463  again:
 464         merge_created_candidate = false;
 465         last_ptr = FREELIST_TOP;
 466
 467         /* read in the freelist top */
 468         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
 469                 return 0;
 470
 471         modified = false;
 472         tdb_chainwalk_init(&chainwalk, rec_ptr);
 473
 474         bestfit.rec_ptr = 0;
 475         bestfit.last_ptr = 0;
 476         bestfit.rec_len = 0;
 477
 478         /*
 479            this is a best fit allocation strategy. Originally we used
 480            a first fit strategy, but it suffered from massive fragmentation
 481            issues when faced with a slowly increasing record size.
 482          */
 483         while (rec_ptr) {
 484                 int ret;
 485                 tdb_off_t left_ptr;
 486                 struct tdb_record left_rec;
 487
 488                 if (tdb_rec_free_read(tdb, rec_ptr, rec) == -1) {
 489                         return 0;
 490                 }
 491
 492                 ret = check_merge_with_left_record(tdb, rec_ptr, rec,
 493                                                    &left_ptr, &left_rec);
 494                 if (ret == -1) {
 495                         return 0;
 496                 }
 497                 if (ret == 1) {
 498                         /* merged */
 499                         rec_ptr = rec->next;
 500                         ret = tdb_ofs_write(tdb, last_ptr, &rec->next);
 501                         if (ret == -1) {
 502                                 return 0;
 503                         }
 504
 505                         /*
 506                          * We have merged the current record into the left
 507                          * neighbour. So our traverse of the freelist will
 508                          * skip it and consider the next record in the chain.
 509                          *
 510                          * But the enlarged left neighbour may be a candidate.
 511                          * If it is, we can not directly use it, though.
 512                          * The only thing we can do and have to do here is to
 513                          * update the current best fit size in the chain if the
 514                          * current best fit is the left record. (By that we may
 515                          * worsen the best fit we already had, bit this is not a
 516                          * problem.)
 517                          *
 518                          * If the current best fit is not the left record,
 519                          * all we can do is remember the fact that a merge
 520                          * created a new candidate so that we can trigger
 521                          * a second walk of the freelist if at the end of
 522                          * the first walk we have not found any fit.
 523                          * This way we can avoid expanding the database.
 524                          */
 525
 526                         if (bestfit.rec_ptr == left_ptr) {
 527                                 bestfit.rec_len = left_rec.rec_len;
 528                         }
 529
 530                         if (left_rec.rec_len > length) {
 531                                 merge_created_candidate = true;
 532                         }
 533
 534                         modified = true;
 535
 536                         continue;
 537                 }
 538
 539                 if (rec->rec_len >= length) {
 540                         if (bestfit.rec_ptr == 0 ||
 541                             rec->rec_len < bestfit.rec_len) {
 542                                 bestfit.rec_len = rec->rec_len;
 543                                 bestfit.rec_ptr = rec_ptr;
 544                                 bestfit.last_ptr = last_ptr;
 545                         }
 546                 }
 547
 548                 /* move to the next record */
 549                 last_ptr = rec_ptr;
 550                 rec_ptr = rec->next;
 551
 552                 if (!modified) {
 553                         bool ok;
 554                         ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
 555                         if (!ok) {
 556                                 return 0;
 557                         }
 558                 }
 559
 560                 /* if we've found a record that is big enough, then
 561                    stop searching if its also not too big. The
 562                    definition of 'too big' changes as we scan
 563                    through */
 564                 if (bestfit.rec_len > 0 &&
 565                     bestfit.rec_len < length * multiplier) {
 566                         break;
 567                 }
 568
 569                 /* this multiplier means we only extremely rarely
 570                    search more than 50 or so records. At 50 records we
 571                    accept records up to 11 times larger than what we
 572                    want */
 573                 multiplier *= 1.05;
 574         }
 575
 576         if (bestfit.rec_ptr != 0) {
 577                 if (tdb_rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
 578                         return 0;
 579                 }
 580
 581                 newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr,
 582                                               rec, bestfit.last_ptr);
 583                 return newrec_ptr;
 584         }
 585
 586         if (merge_created_candidate) {
 587                 goto again;
 588         }
 589
 590         /* we didn't find enough space. See if we can expand the
 591            database and if we can then try again */
 592         if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
 593                 goto again;
 594
 595         return 0;
 596 }
 597
 598 static bool tdb_alloc_dead(
 599         struct tdb_context *tdb, int hash, tdb_len_t length,
 600         tdb_off_t *rec_ptr, struct tdb_record *rec)
 601 {
 602         tdb_off_t last_ptr;
 603
 604         *rec_ptr = tdb_find_dead(tdb, hash, rec, length, &last_ptr);
 605         if (*rec_ptr == 0) {
 606                 return false;
 607         }
 608         /*
 609          * Unlink the record from the hash chain, it's about to be moved into
 610          * another one.
 611          */
 612         return (tdb_ofs_write(tdb, last_ptr, &rec->next) == 0);
 613 }
 614
 615 /*
 616  * Chain "hash" is assumed to be locked
 617  */
 618
 619 tdb_off_t tdb_allocate(struct tdb_context *tdb, int hash, tdb_len_t length,
 620                        struct tdb_record *rec)
 621 {
 622         tdb_off_t ret;
 623         uint32_t i;
 624
 625         if (tdb->max_dead_records == 0) {
 626                 /*
 627                  * No dead records to expect anywhere. Do the blocking
 628                  * freelist lock without trying to steal from others
 629                  */
 630                 goto blocking_freelist_allocate;
 631         }
 632
 633         /*
 634          * The following loop tries to get the freelist lock nonblocking. If
 635          * it gets the lock, allocate from there. If the freelist is busy,
 636          * instead of waiting we try to steal dead records from other hash
 637          * chains.
 638          *
 639          * Be aware that we do nonblocking locks on the other hash chains as
 640          * well and fail gracefully. This way we avoid deadlocks (we block two
 641          * hash chains, something which is pretty bad normally)
 642          */
 643
 644         for (i=0; i<tdb->hash_size; i++) {
 645
 646                 int list;
 647
 648                 list = BUCKET(hash+i);
 649
 650                 if (tdb_lock_nonblock(tdb, list, F_WRLCK) == 0) {
 651                         bool got_dead;
 652
 653                         got_dead = tdb_alloc_dead(tdb, list, length, &ret, rec);
 654                         tdb_unlock(tdb, list, F_WRLCK);
 655
 656                         if (got_dead) {
 657                                 return ret;
 658                         }
 659                 }
 660
 661                 if (tdb_lock_nonblock(tdb, -1, F_WRLCK) == 0) {
 662                         /*
 663                          * Under the freelist lock take the chance to give
 664                          * back our dead records.
 665                          */
 666                         tdb_purge_dead(tdb, hash);
 667
 668                         ret = tdb_allocate_from_freelist(tdb, length, rec);
 669                         tdb_unlock(tdb, -1, F_WRLCK);
 670                         return ret;
 671                 }
 672         }
 673
 674 blocking_freelist_allocate:
 675
 676         if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
 677                 return 0;
 678         }
 679         ret = tdb_allocate_from_freelist(tdb, length, rec);
 680         tdb_unlock(tdb, -1, F_WRLCK);
 681         return ret;
 682 }
 683
 684 /**
 685  * Merge adjacent records in the freelist.
 686  */
 687 static int tdb_freelist_merge_adjacent(struct tdb_context *tdb,
 688                                        int *count_records, int *count_merged)
 689 {
 690         tdb_off_t cur, next;
 691         int count = 0;
 692         int merged = 0;
 693         int ret;
 694
 695         ret = tdb_lock(tdb, -1, F_RDLCK);
 696         if (ret == -1) {
 697                 return -1;
 698         }
 699
 700         cur = FREELIST_TOP;
 701         while (tdb_ofs_read(tdb, cur, &next) == 0 && next != 0) {
 702                 tdb_off_t next2;
 703
 704                 count++;
 705
 706                 ret = check_merge_ptr_with_left_record(tdb, next, &next2);
 707                 if (ret == -1) {
 708                         goto done;
 709                 }
 710                 if (ret == 1) {
 711                         /*
 712                          * merged:
 713                          * now let cur->next point to next2 instead of next
 714                          */
 715
 716                         ret = tdb_ofs_write(tdb, cur, &next2);
 717                         if (ret != 0) {
 718                                 goto done;
 719                         }
 720
 721                         next = next2;
 722                         merged++;
 723                 }
 724
 725                 cur = next;
 726         }
 727
 728         if (count_records != NULL) {
 729                 *count_records = count;
 730         }
 731
 732         if (count_merged != NULL) {
 733                 *count_merged = merged;
 734         }
 735
 736         ret = 0;
 737
 738 done:
 739         tdb_unlock(tdb, -1, F_RDLCK);
 740         return ret;
 741 }
 742
 743 /**
 744  * return the size of the freelist - no merging done
 745  */
 746 static int tdb_freelist_size_no_merge(struct tdb_context *tdb)
 747 {
 748         tdb_off_t ptr;
 749         int count=0;
 750
 751         if (tdb_lock(tdb, -1, F_RDLCK) == -1) {
 752                 return -1;
 753         }
 754
 755         ptr = FREELIST_TOP;
 756         while (tdb_ofs_read(tdb, ptr, &ptr) == 0 && ptr != 0) {
 757                 count++;
 758         }
 759
 760         tdb_unlock(tdb, -1, F_RDLCK);
 761         return count;
 762 }
 763
 764 /**
 765  * return the size of the freelist - used to decide if we should repack
 766  *
 767  * As a side effect, adjacent records are merged unless the
 768  * database is read-only, in order to reduce the fragmentation
 769  * without repacking.
 770  */
 771 _PUBLIC_ int tdb_freelist_size(struct tdb_context *tdb)
 772 {
 773
 774         int count = 0;
 775
 776         if (tdb->read_only) {
 777                 count = tdb_freelist_size_no_merge(tdb);
 778         } else {
 779                 int ret;
 780                 ret = tdb_freelist_merge_adjacent(tdb, &count, NULL);
 781                 if (ret != 0) {
 782                         return -1;
 783                 }
 784         }
 785
 786         return count;
 787 }