source3/tdb/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 2 of the License, or (at your option) any later version.
  18
  19    This library is distributed in the hope that it will be useful,
  20    but WITHOUT ANY WARRANTY; without even the implied warranty of
  21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  22    Lesser General Public License for more details.
  23
  24    You should have received a copy of the GNU Lesser General Public
  25    License along with this library; if not, write to the Free Software
  26    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  27 */
  28
  29 #include "tdb_private.h"
  30
  31 /* read a freelist record and check for simple errors */
  32 static int rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec)
  33 {
  34         if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
  35                 return -1;
  36
  37         if (rec->magic == TDB_MAGIC) {
  38                 /* this happens when a app is showdown while deleting a record - we should
  39                    not completely fail when this happens */
  40                 TDB_LOG((tdb, 0,"rec_free_read non-free magic 0x%x at offset=%d - fixing\n",
  41                          rec->magic, off));
  42                 rec->magic = TDB_FREE_MAGIC;
  43                 if (tdb->methods->tdb_write(tdb, off, rec, sizeof(*rec)) == -1)
  44                         return -1;
  45         }
  46
  47         if (rec->magic != TDB_FREE_MAGIC) {
  48                 /* Ensure ecode is set for log fn. */
  49                 tdb->ecode = TDB_ERR_CORRUPT;
  50                 TDB_LOG((tdb, 0,"rec_free_read bad magic 0x%x at offset=%d\n",
  51                            rec->magic, off));
  52                 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
  53         }
  54         if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0)
  55                 return -1;
  56         return 0;
  57 }
  58
  59
  60
  61 /* Remove an element from the freelist.  Must have alloc lock. */
  62 static int remove_from_freelist(struct tdb_context *tdb, tdb_off_t off, tdb_off_t next)
  63 {
  64         tdb_off_t last_ptr, i;
  65
  66         /* read in the freelist top */
  67         last_ptr = FREELIST_TOP;
  68         while (tdb_ofs_read(tdb, last_ptr, &i) != -1 && i != 0) {
  69                 if (i == off) {
  70                         /* We've found it! */
  71                         return tdb_ofs_write(tdb, last_ptr, &next);
  72                 }
  73                 /* Follow chain (next offset is at start of record) */
  74                 last_ptr = i;
  75         }
  76         TDB_LOG((tdb, 0,"remove_from_freelist: not on list at off=%d\n", off));
  77         return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
  78 }
  79
  80
  81 /* update a record tailer (must hold allocation lock) */
  82 static int update_tailer(struct tdb_context *tdb, tdb_off_t offset,
  83                          const struct list_struct *rec)
  84 {
  85         tdb_off_t totalsize;
  86
  87         /* Offset of tailer from record header */
  88         totalsize = sizeof(*rec) + rec->rec_len;
  89         return tdb_ofs_write(tdb, offset + totalsize - sizeof(tdb_off_t),
  90                          &totalsize);
  91 }
  92
  93 /* Add an element into the freelist. Merge adjacent records if
  94    neccessary. */
  95 int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec)
  96 {
  97         tdb_off_t right, left;
  98
  99         /* Allocation and tailer lock */
 100         if (tdb_lock(tdb, -1, F_WRLCK) != 0)
 101                 return -1;
 102
 103         /* set an initial tailer, so if we fail we don't leave a bogus record */
 104         if (update_tailer(tdb, offset, rec) != 0) {
 105                 TDB_LOG((tdb, 0, "tdb_free: upfate_tailer failed!\n"));
 106                 goto fail;
 107         }
 108
 109         /* Look right first (I'm an Australian, dammit) */
 110         right = offset + sizeof(*rec) + rec->rec_len;
 111         if (right + sizeof(*rec) <= tdb->map_size) {
 112                 struct list_struct r;
 113
 114                 if (tdb->methods->tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) {
 115                         TDB_LOG((tdb, 0, "tdb_free: right read failed at %u\n", right));
 116                         goto left;
 117                 }
 118
 119                 /* If it's free, expand to include it. */
 120                 if (r.magic == TDB_FREE_MAGIC) {
 121                         if (remove_from_freelist(tdb, right, r.next) == -1) {
 122                                 TDB_LOG((tdb, 0, "tdb_free: right free failed at %u\n", right));
 123                                 goto left;
 124                         }
 125                         rec->rec_len += sizeof(r) + r.rec_len;
 126                 }
 127         }
 128
 129 left:
 130         /* Look left */
 131         left = offset - sizeof(tdb_off_t);
 132         if (left > TDB_DATA_START(tdb->header.hash_size)) {
 133                 struct list_struct l;
 134                 tdb_off_t leftsize;
 135
 136                 /* Read in tailer and jump back to header */
 137                 if (tdb_ofs_read(tdb, left, &leftsize) == -1) {
 138                         TDB_LOG((tdb, 0, "tdb_free: left offset read failed at %u\n", left));
 139                         goto update;
 140                 }
 141
 142                 /* it could be uninitialised data */
 143                 if (leftsize == 0 || leftsize == TDB_PAD_U32) {
 144                         goto update;
 145                 }
 146
 147                 left = offset - leftsize;
 148
 149                 /* Now read in record */
 150                 if (tdb->methods->tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) {
 151                         TDB_LOG((tdb, 0, "tdb_free: left read failed at %u (%u)\n", left, leftsize));
 152                         goto update;
 153                 }
 154
 155                 /* If it's free, expand to include it. */
 156                 if (l.magic == TDB_FREE_MAGIC) {
 157                         if (remove_from_freelist(tdb, left, l.next) == -1) {
 158                                 TDB_LOG((tdb, 0, "tdb_free: left free failed at %u\n", left));
 159                                 goto update;
 160                         } else {
 161                                 offset = left;
 162                                 rec->rec_len += leftsize;
 163                         }
 164                 }
 165         }
 166
 167 update:
 168         if (update_tailer(tdb, offset, rec) == -1) {
 169                 TDB_LOG((tdb, 0, "tdb_free: update_tailer failed at %u\n", offset));
 170                 goto fail;
 171         }
 172
 173         /* Now, prepend to free list */
 174         rec->magic = TDB_FREE_MAGIC;
 175
 176         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
 177             tdb_rec_write(tdb, offset, rec) == -1 ||
 178             tdb_ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
 179                 TDB_LOG((tdb, 0, "tdb_free record write failed at offset=%d\n", offset));
 180                 goto fail;
 181         }
 182
 183         /* And we're done. */
 184         tdb_unlock(tdb, -1, F_WRLCK);
 185         return 0;
 186
 187  fail:
 188         tdb_unlock(tdb, -1, F_WRLCK);
 189         return -1;
 190 }
 191
 192
 193 /*
 194    the core of tdb_allocate - called when we have decided which
 195    free list entry to use
 196  */
 197 static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb, tdb_len_t length, tdb_off_t rec_ptr,
 198                                 struct list_struct *rec, tdb_off_t last_ptr)
 199 {
 200         struct list_struct newrec;
 201         tdb_off_t newrec_ptr;
 202
 203         memset(&newrec, '\0', sizeof(newrec));
 204
 205         /* found it - now possibly split it up  */
 206         if (rec->rec_len > length + MIN_REC_SIZE) {
 207                 /* Length of left piece */
 208                 length = TDB_ALIGN(length, TDB_ALIGNMENT);
 209
 210                 /* Right piece to go on free list */
 211                 newrec.rec_len = rec->rec_len - (sizeof(*rec) + length);
 212                 newrec_ptr = rec_ptr + sizeof(*rec) + length;
 213
 214                 /* And left record is shortened */
 215                 rec->rec_len = length;
 216         } else {
 217                 newrec_ptr = 0;
 218         }
 219
 220         /* Remove allocated record from the free list */
 221         if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) {
 222                 return 0;
 223         }
 224
 225         /* Update header: do this before we drop alloc
 226            lock, otherwise tdb_free() might try to
 227            merge with us, thinking we're free.
 228            (Thanks Jeremy Allison). */
 229         rec->magic = TDB_MAGIC;
 230         if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
 231                 return 0;
 232         }
 233
 234         /* Did we create new block? */
 235         if (newrec_ptr) {
 236                 /* Update allocated record tailer (we
 237                    shortened it). */
 238                 if (update_tailer(tdb, rec_ptr, rec) == -1) {
 239                         return 0;
 240                 }
 241
 242                 /* Free new record */
 243                 if (tdb_free(tdb, newrec_ptr, &newrec) == -1) {
 244                         return 0;
 245                 }
 246         }
 247
 248         /* all done - return the new record offset */
 249         return rec_ptr;
 250 }
 251
 252 /* allocate some space from the free list. The offset returned points
 253    to a unconnected list_struct within the database with room for at
 254    least length bytes of total data
 255
 256    0 is returned if the space could not be allocated
 257  */
 258 tdb_off_t tdb_allocate(struct tdb_context *tdb, tdb_len_t length, struct list_struct *rec)
 259 {
 260         tdb_off_t rec_ptr, last_ptr, newrec_ptr;
 261         struct {
 262                 tdb_off_t rec_ptr, last_ptr;
 263                 tdb_len_t rec_len;
 264         } bestfit;
 265
 266         if (tdb_lock(tdb, -1, F_WRLCK) == -1)
 267                 return 0;
 268
 269         /* Extra bytes required for tailer */
 270         length += sizeof(tdb_off_t);
 271
 272  again:
 273         last_ptr = FREELIST_TOP;
 274
 275         /* read in the freelist top */
 276         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
 277                 goto fail;
 278
 279         bestfit.rec_ptr = 0;
 280         bestfit.last_ptr = 0;
 281         bestfit.rec_len = 0;
 282
 283         /*
 284            this is a best fit allocation strategy. Originally we used
 285            a first fit strategy, but it suffered from massive fragmentation
 286            issues when faced with a slowly increasing record size.
 287          */
 288         while (rec_ptr) {
 289                 if (rec_free_read(tdb, rec_ptr, rec) == -1) {
 290                         goto fail;
 291                 }
 292
 293                 if (rec->rec_len >= length) {
 294                         if (bestfit.rec_ptr == 0 ||
 295                             rec->rec_len < bestfit.rec_len) {
 296                                 bestfit.rec_len = rec->rec_len;
 297                                 bestfit.rec_ptr = rec_ptr;
 298                                 bestfit.last_ptr = last_ptr;
 299                                 /* consider a fit to be good enough if
 300                                    we aren't wasting more than half
 301                                    the space */
 302                                 if (bestfit.rec_len < 2*length) {
 303                                         break;
 304                                 }
 305                         }
 306                 }
 307
 308                 /* move to the next record */
 309                 last_ptr = rec_ptr;
 310                 rec_ptr = rec->next;
 311         }
 312
 313         if (bestfit.rec_ptr != 0) {
 314                 if (rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
 315                         goto fail;
 316                 }
 317
 318                 newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr, rec, bestfit.last_ptr);
 319                 tdb_unlock(tdb, -1, F_WRLCK);
 320                 return newrec_ptr;
 321         }
 322
 323         /* we didn't find enough space. See if we can expand the
 324            database and if we can then try again */
 325         if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
 326                 goto again;
 327  fail:
 328         tdb_unlock(tdb, -1, F_WRLCK);
 329         return 0;
 330 }
 331