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=%d - 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=%d\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=%d\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 /* Add an element into the freelist. Merge adjacent records if
 101    necessary. */
 102 int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec)
 103 {
 104         /* Allocation and tailer lock */
 105         if (tdb_lock(tdb, -1, F_WRLCK) != 0)
 106                 return -1;
 107
 108         /* set an initial tailer, so if we fail we don't leave a bogus record */
 109         if (update_tailer(tdb, offset, rec) != 0) {
 110                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed!\n"));
 111                 goto fail;
 112         }
 113
 114 #if USE_RIGHT_MERGES
 115         /* Look right first (I'm an Australian, dammit) */
 116         if (offset + sizeof(*rec) + rec->rec_len + sizeof(*rec) <= tdb->map_size) {
 117                 tdb_off_t right = offset + sizeof(*rec) + rec->rec_len;
 118                 struct tdb_record r;
 119
 120                 if (tdb->methods->tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) {
 121                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: right read failed at %u\n", right));
 122                         goto left;
 123                 }
 124
 125                 /* If it's free, expand to include it. */
 126                 if (r.magic == TDB_FREE_MAGIC) {
 127                         if (remove_from_freelist(tdb, right, r.next) == -1) {
 128                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: right free failed at %u\n", right));
 129                                 goto left;
 130                         }
 131                         rec->rec_len += sizeof(r) + r.rec_len;
 132                         if (update_tailer(tdb, offset, rec) == -1) {
 133                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset));
 134                                 goto fail;
 135                         }
 136                 }
 137         }
 138 left:
 139 #endif
 140
 141         /* Look left */
 142         if (offset - sizeof(tdb_off_t) > TDB_DATA_START(tdb->hash_size)) {
 143                 tdb_off_t left = offset - sizeof(tdb_off_t);
 144                 struct tdb_record l;
 145                 tdb_off_t leftsize;
 146
 147                 /* Read in tailer and jump back to header */
 148                 if (tdb_ofs_read(tdb, left, &leftsize) == -1) {
 149                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left offset read failed at %u\n", left));
 150                         goto update;
 151                 }
 152
 153                 /* it could be uninitialised data */
 154                 if (leftsize == 0 || leftsize == TDB_PAD_U32) {
 155                         goto update;
 156                 }
 157
 158                 left = offset - leftsize;
 159
 160                 if (leftsize > offset ||
 161                     left < TDB_DATA_START(tdb->hash_size)) {
 162                         goto update;
 163                 }
 164
 165                 /* Now read in the left record */
 166                 if (tdb->methods->tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) {
 167                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left read failed at %u (%u)\n", left, leftsize));
 168                         goto update;
 169                 }
 170
 171                 /* If it's free, expand to include it. */
 172                 if (l.magic == TDB_FREE_MAGIC) {
 173                         /* we now merge the new record into the left record, rather than the other
 174                            way around. This makes the operation O(1) instead of O(n). This change
 175                            prevents traverse from being O(n^2) after a lot of deletes */
 176                         l.rec_len += sizeof(*rec) + rec->rec_len;
 177                         if (tdb_rec_write(tdb, left, &l) == -1) {
 178                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_left failed at %u\n", left));
 179                                 goto fail;
 180                         }
 181                         if (update_tailer(tdb, left, &l) == -1) {
 182                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset));
 183                                 goto fail;
 184                         }
 185                         tdb_unlock(tdb, -1, F_WRLCK);
 186                         return 0;
 187                 }
 188         }
 189
 190 update:
 191
 192         /* Now, prepend to free list */
 193         rec->magic = TDB_FREE_MAGIC;
 194
 195         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
 196             tdb_rec_write(tdb, offset, rec) == -1 ||
 197             tdb_ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
 198                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free record write failed at offset=%d\n", offset));
 199                 goto fail;
 200         }
 201
 202         /* And we're done. */
 203         tdb_unlock(tdb, -1, F_WRLCK);
 204         return 0;
 205
 206  fail:
 207         tdb_unlock(tdb, -1, F_WRLCK);
 208         return -1;
 209 }
 210
 211
 212
 213 /*
 214    the core of tdb_allocate - called when we have decided which
 215    free list entry to use
 216
 217    Note that we try to allocate by grabbing data from the end of an existing record,
 218    not the beginning. This is so the left merge in a free is more likely to be
 219    able to free up the record without fragmentation
 220  */
 221 static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb,
 222                                   tdb_len_t length, tdb_off_t rec_ptr,
 223                                   struct tdb_record *rec, tdb_off_t last_ptr)
 224 {
 225 #define MIN_REC_SIZE (sizeof(struct tdb_record) + sizeof(tdb_off_t) + 8)
 226
 227         if (rec->rec_len < length + MIN_REC_SIZE) {
 228                 /* we have to grab the whole record */
 229
 230                 /* unlink it from the previous record */
 231                 if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) {
 232                         return 0;
 233                 }
 234
 235                 /* mark it not free */
 236                 rec->magic = TDB_MAGIC;
 237                 if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
 238                         return 0;
 239                 }
 240                 return rec_ptr;
 241         }
 242
 243         /* we're going to just shorten the existing record */
 244         rec->rec_len -= (length + sizeof(*rec));
 245         if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
 246                 return 0;
 247         }
 248         if (update_tailer(tdb, rec_ptr, rec) == -1) {
 249                 return 0;
 250         }
 251
 252         /* and setup the new record */
 253         rec_ptr += sizeof(*rec) + rec->rec_len;
 254
 255         memset(rec, '\0', sizeof(*rec));
 256         rec->rec_len = length;
 257         rec->magic = TDB_MAGIC;
 258
 259         if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
 260                 return 0;
 261         }
 262
 263         if (update_tailer(tdb, rec_ptr, rec) == -1) {
 264                 return 0;
 265         }
 266
 267         return rec_ptr;
 268 }
 269
 270 /* allocate some space from the free list. The offset returned points
 271    to a unconnected tdb_record within the database with room for at
 272    least length bytes of total data
 273
 274    0 is returned if the space could not be allocated
 275  */
 276 tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct tdb_record *rec)
 277 {
 278         tdb_off_t rec_ptr, last_ptr, newrec_ptr;
 279         struct {
 280                 tdb_off_t rec_ptr, last_ptr;
 281                 tdb_len_t rec_len;
 282         } bestfit;
 283         float multiplier = 1.0;
 284
 285         if (tdb_lock(tdb, -1, F_WRLCK) == -1)
 286                 return 0;
 287
 288         /* over-allocate to reduce fragmentation */
 289         length *= 1.25;
 290
 291         /* Extra bytes required for tailer */
 292         length += sizeof(tdb_off_t);
 293         length = TDB_ALIGN(length, TDB_ALIGNMENT);
 294
 295  again:
 296         last_ptr = FREELIST_TOP;
 297
 298         /* read in the freelist top */
 299         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
 300                 goto fail;
 301
 302         bestfit.rec_ptr = 0;
 303         bestfit.last_ptr = 0;
 304         bestfit.rec_len = 0;
 305
 306         /*
 307            this is a best fit allocation strategy. Originally we used
 308            a first fit strategy, but it suffered from massive fragmentation
 309            issues when faced with a slowly increasing record size.
 310          */
 311         while (rec_ptr) {
 312                 if (tdb_rec_free_read(tdb, rec_ptr, rec) == -1) {
 313                         goto fail;
 314                 }
 315
 316                 if (rec->rec_len >= length) {
 317                         if (bestfit.rec_ptr == 0 ||
 318                             rec->rec_len < bestfit.rec_len) {
 319                                 bestfit.rec_len = rec->rec_len;
 320                                 bestfit.rec_ptr = rec_ptr;
 321                                 bestfit.last_ptr = last_ptr;
 322                         }
 323                 }
 324
 325                 /* move to the next record */
 326                 last_ptr = rec_ptr;
 327                 rec_ptr = rec->next;
 328
 329                 /* if we've found a record that is big enough, then
 330                    stop searching if its also not too big. The
 331                    definition of 'too big' changes as we scan
 332                    through */
 333                 if (bestfit.rec_len > 0 &&
 334                     bestfit.rec_len < length * multiplier) {
 335                         break;
 336                 }
 337
 338                 /* this multiplier means we only extremely rarely
 339                    search more than 50 or so records. At 50 records we
 340                    accept records up to 11 times larger than what we
 341                    want */
 342                 multiplier *= 1.05;
 343         }
 344
 345         if (bestfit.rec_ptr != 0) {
 346                 if (tdb_rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
 347                         goto fail;
 348                 }
 349
 350                 newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr,
 351                                               rec, bestfit.last_ptr);
 352                 tdb_unlock(tdb, -1, F_WRLCK);
 353                 return newrec_ptr;
 354         }
 355
 356         /* we didn't find enough space. See if we can expand the
 357            database and if we can then try again */
 358         if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
 359                 goto again;
 360  fail:
 361         tdb_unlock(tdb, -1, F_WRLCK);
 362         return 0;
 363 }
 364
 365
 366
 367 /*
 368    return the size of the freelist - used to decide if we should repack
 369 */
 370 _PUBLIC_ int tdb_freelist_size(struct tdb_context *tdb)
 371 {
 372         tdb_off_t ptr;
 373         int count=0;
 374
 375         if (tdb_lock(tdb, -1, F_RDLCK) == -1) {
 376                 return -1;
 377         }
 378
 379         ptr = FREELIST_TOP;
 380         while (tdb_ofs_read(tdb, ptr, &ptr) == 0 && ptr != 0) {
 381                 count++;
 382         }
 383
 384         tdb_unlock(tdb, -1, F_RDLCK);
 385         return count;
 386 }