src/falloc.c

   1 /* falloc.c - The file space management routines for dbm. */
   2
   3 /* This file is part of GDBM, the GNU data base manager.
   4    Copyright (C) 1990, 1991, 1993, 1994, 2007, 2011, 2013 Free Software
   5    Foundation, Inc.
   6
   7    GDBM is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GDBM is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GDBM. If not, see <http://www.gnu.org/licenses/>.    */
  19
  20 /* Include system configuration before all else. */
  21 #include "autoconf.h"
  22
  23 #include "gdbmdefs.h"
  24
  25
  26 /* The forward definitions for this file.  See the functions for
  27    the definition of the function. */
  28
  29 static avail_elem get_elem (int, avail_elem [], int *);
  30 static avail_elem get_block (int, GDBM_FILE);
  31 static void push_avail_block (GDBM_FILE);
  32 static void pop_avail_block (GDBM_FILE);
  33 static void adjust_bucket_avail (GDBM_FILE);
  34
  35 /* Allocate space in the file DBF for a block NUM_BYTES in length.  Return
  36    the file address of the start of the block.
  37
  38    Each hash bucket has a fixed size avail table.  We first check this
  39    avail table to satisfy the request for space.  In most cases we can
  40    and this causes changes to be only in the current hash bucket.
  41    Allocation is done on a first fit basis from the entries.  If a
  42    request can not be satisfied from the current hash bucket, then it is
  43    satisfied from the file header avail block.  If nothing is there that
  44    has enough space, another block at the end of the file is allocated
  45    and the unused portion is returned to the avail block.  This routine
  46    "guarantees" that an allocation does not cross a block boundary unless
  47    the size is larger than a single block.  The avail structure is
  48    changed by this routine if a change is needed.  If an error occurs,
  49    the value of 0 will be returned.  */
  50
  51 off_t
  52 _gdbm_alloc (GDBM_FILE dbf, int num_bytes)
  53 {
  54   off_t file_adr;               /* The address of the block. */
  55   avail_elem av_el;             /* For temporary use. */
  56
  57   /* The current bucket is the first place to look for space. */
  58   av_el = get_elem (num_bytes, dbf->bucket->bucket_avail,
  59                     &dbf->bucket->av_count);
  60
  61   /* If we did not find some space, we have more work to do. */
  62   if (av_el.av_size == 0)
  63     {
  64       /* If the header avail table is less than half full, and there's
  65          something on the stack. */
  66       if ((dbf->header->avail.count <= (dbf->header->avail.size >> 1))
  67           && (dbf->header->avail.next_block != 0))
  68         pop_avail_block (dbf);
  69
  70       /* check the header avail table next */
  71       av_el = get_elem (num_bytes, dbf->header->avail.av_table,
  72                         &dbf->header->avail.count);
  73       if (av_el.av_size == 0)
  74         /* Get another full block from end of file. */
  75         av_el = get_block (num_bytes, dbf);
  76
  77       dbf->header_changed = TRUE;
  78     }
  79
  80   /* We now have the place from which we will allocate the new space. */
  81   file_adr = av_el.av_adr;
  82
  83   /* Put the unused space back in the avail block. */
  84   av_el.av_adr += num_bytes;
  85   av_el.av_size -= num_bytes;
  86   _gdbm_free (dbf, av_el.av_adr, av_el.av_size);
  87
  88   /* Return the address. */
  89   return file_adr;
  90
  91 }
  92
  93
  94
  95 /* Free space of size NUM_BYTES in the file DBF at file address FILE_ADR.  Make
  96    it avaliable for reuse through _gdbm_alloc.  This routine changes the
  97    avail structure. */
  98
  99 void
 100 _gdbm_free (GDBM_FILE dbf, off_t file_adr, int num_bytes)
 101 {
 102   avail_elem temp;
 103
 104   /* Is it too small to worry about? */
 105   if (num_bytes <= IGNORE_SIZE)
 106     return;
 107
 108   /* Initialize the avail element. */
 109   temp.av_size = num_bytes;
 110   temp.av_adr = file_adr;
 111
 112   /* Is the freed space large or small? */
 113   if ((num_bytes >= dbf->header->block_size) || dbf->central_free)
 114     {
 115       if (dbf->header->avail.count == dbf->header->avail.size)
 116         {
 117           push_avail_block (dbf);
 118         }
 119       _gdbm_put_av_elem (temp, dbf->header->avail.av_table,
 120                          &dbf->header->avail.count, dbf->coalesce_blocks);
 121       dbf->header_changed = TRUE;
 122     }
 123   else
 124     {
 125       /* Try to put into the current bucket. */
 126       if (dbf->bucket->av_count < BUCKET_AVAIL)
 127         _gdbm_put_av_elem (temp, dbf->bucket->bucket_avail,
 128                            &dbf->bucket->av_count, dbf->coalesce_blocks);
 129       else
 130         {
 131           if (dbf->header->avail.count == dbf->header->avail.size)
 132             {
 133               push_avail_block (dbf);
 134             }
 135           _gdbm_put_av_elem (temp, dbf->header->avail.av_table,
 136                              &dbf->header->avail.count, dbf->coalesce_blocks);
 137           dbf->header_changed = TRUE;
 138         }
 139     }
 140
 141   if (dbf->header_changed)
 142     adjust_bucket_avail (dbf);
 143
 144   /* All work is done. */
 145   return;
 146 }
 147
 148
 149
 150 /* The following are all utility routines needed by the previous two. */
 151
 152
 153 /* Gets the avail block at the top of the stack and loads it into the
 154    active avail block.  It does a "free" for itself!  This can (and is)
 155    now called even when the avail block is not empty, so we must be
 156    smart about things. */
 157
 158 static void
 159 pop_avail_block (GDBM_FILE dbf)
 160 {
 161   int rc;
 162   off_t file_pos;               /* For use with the lseek system call. */
 163   avail_elem new_el;
 164   avail_block *new_blk;
 165   int index;
 166
 167   if (dbf->header->avail.count == dbf->header->avail.size)
 168     {
 169       /* We're kind of stuck here, so we re-split the header in order to
 170          avoid crashing.  Sigh. */
 171       push_avail_block(dbf);
 172     }
 173
 174   /* Set up variables. */
 175   new_el.av_adr = dbf->header->avail.next_block;
 176   new_el.av_size = ( ( (dbf->header->avail.size * sizeof (avail_elem)) >> 1)
 177                         + sizeof (avail_block));
 178
 179   /* Allocate space for the block. */
 180   new_blk = (avail_block *) malloc (new_el.av_size);
 181   if (new_blk == NULL) _gdbm_fatal(dbf, _("malloc failed"));
 182
 183   /* Read the block. */
 184   file_pos = __lseek (dbf, new_el.av_adr, SEEK_SET);
 185   if (file_pos != new_el.av_adr)  _gdbm_fatal (dbf, _("lseek error"));
 186   rc = _gdbm_full_read (dbf, new_blk, new_el.av_size);
 187   if (rc)
 188     _gdbm_fatal (dbf, gdbm_strerror (rc));
 189
 190   /* Add the elements from the new block to the header. */
 191   index = 0;
 192   while (index < new_blk->count)
 193     {
 194       while(index < new_blk->count
 195             && dbf->header->avail.count < dbf->header->avail.size)
 196         {
 197            /* With luck, this will merge a lot of blocks! */
 198            _gdbm_put_av_elem(new_blk->av_table[index],
 199                              dbf->header->avail.av_table,
 200                              &dbf->header->avail.count, TRUE);
 201            index++;
 202         }
 203       if (dbf->header->avail.count == dbf->header->avail.size)
 204         {
 205           /* We're kind of stuck here, so we re-split the header in order to
 206              avoid crashing.  Sigh. */
 207           push_avail_block(dbf);
 208         }
 209     }
 210
 211   /* Fix next_block, as well. */
 212   dbf->header->avail.next_block = new_blk->next_block;
 213
 214   /* We changed the header. */
 215   dbf->header_changed = TRUE;
 216
 217   /* Free the previous avail block.   It is possible that the header table
 218      is now FULL, which will cause us to overflow it! */
 219   if (dbf->header->avail.count == dbf->header->avail.size)
 220     {
 221       /* We're kind of stuck here, so we re-split the header in order to
 222          avoid crashing.  Sigh. */
 223       push_avail_block(dbf);
 224     }
 225
 226   _gdbm_put_av_elem (new_el, dbf->header->avail.av_table,
 227                      &dbf->header->avail.count, TRUE);
 228   free (new_blk);
 229 }
 230
 231
 232 /* Splits the header avail block and pushes half onto the avail stack. */
 233
 234 static void
 235 push_avail_block (GDBM_FILE dbf)
 236 {
 237   int  av_size;
 238   off_t av_adr;
 239   int  index;
 240   off_t file_pos;
 241   avail_block *temp;
 242   avail_elem  new_loc;
 243   int rc;
 244
 245   /* Caclulate the size of the split block. */
 246   av_size = ( (dbf->header->avail.size * sizeof (avail_elem)) >> 1)
 247             + sizeof (avail_block);
 248
 249   /* Get address in file for new av_size bytes. */
 250   new_loc = get_elem (av_size, dbf->header->avail.av_table,
 251                       &dbf->header->avail.count);
 252   if (new_loc.av_size == 0)
 253     new_loc = get_block (av_size, dbf);
 254   av_adr = new_loc.av_adr;
 255
 256
 257   /* Split the header block. */
 258   temp = (avail_block *) malloc (av_size);
 259   if (temp == NULL) _gdbm_fatal (dbf, _("malloc error"));
 260   /* Set the size to be correct AFTER the pop_avail_block. */
 261   temp->size = dbf->header->avail.size;
 262   temp->count = 0;
 263   temp->next_block = dbf->header->avail.next_block;
 264   dbf->header->avail.next_block = av_adr;
 265   for (index = 1; index < dbf->header->avail.count; index++)
 266     if ( (index & 0x1) == 1)    /* Index is odd. */
 267       temp->av_table[temp->count++] = dbf->header->avail.av_table[index];
 268     else
 269       dbf->header->avail.av_table[index>>1]
 270         = dbf->header->avail.av_table[index];
 271
 272   /* Update the header avail count to previous size divided by 2. */
 273   dbf->header->avail.count >>= 1;
 274
 275   /* Free the unneeded space. */
 276   new_loc.av_adr += av_size;
 277   new_loc.av_size -= av_size;
 278   _gdbm_free (dbf, new_loc.av_adr, new_loc.av_size);
 279
 280   /* Update the disk. */
 281   file_pos = __lseek (dbf, av_adr, SEEK_SET);
 282   if (file_pos != av_adr) _gdbm_fatal (dbf, _("lseek error"));
 283   rc = _gdbm_full_write (dbf, temp, av_size);
 284   if (rc)
 285     _gdbm_fatal (dbf, gdbm_strerror (rc));
 286   free (temp);
 287 }
 288
 289
 290
 291 /* Get_elem returns an element in the AV_TABLE block which is
 292    larger than SIZE.  AV_COUNT is the number of elements in the
 293    AV_TABLE.  If an item is found, it extracts it from the AV_TABLE
 294    and moves the other elements up to fill the space. If no block is
 295    found larger than SIZE, get_elem returns a size of zero.  This
 296    routine does no I/O. */
 297
 298 static avail_elem
 299 get_elem (int size, avail_elem av_table[], int *av_count)
 300 {
 301   int index;                    /* For searching through the avail block. */
 302   avail_elem val;               /* The default return value. */
 303
 304   /* Initialize default return value. */
 305   val.av_adr = 0;
 306   val.av_size = 0;
 307
 308   /* Search for element.  List is sorted by size. */
 309   index = 0;
 310   while (index < *av_count && av_table[index].av_size < size)
 311     {
 312       index++;
 313     }
 314
 315   /* Did we find one of the right size? */
 316   if (index >= *av_count)
 317     return val;
 318
 319   /* Ok, save that element and move all others up one. */
 320   val = av_table[index];
 321   *av_count -= 1;
 322   while (index < *av_count)
 323     {
 324       av_table[index] = av_table[index+1];
 325       index++;
 326     }
 327
 328   return val;
 329 }
 330
 331
 332 /* This routine inserts a single NEW_EL into the AV_TABLE block.
 333    This routine does no I/O. */
 334
 335 int
 336 _gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count,
 337                    int can_merge)
 338 {
 339   int index;                    /* For searching through the avail block. */
 340   int index1;
 341
 342   /* Is it too small to deal with? */
 343   if (new_el.av_size <= IGNORE_SIZE)
 344     return FALSE;
 345
 346   if (can_merge == TRUE)
 347     {
 348       /* Search for blocks to coalesce with this one. */
 349       index = 0;
 350
 351       while (index < *av_count)
 352         {
 353           /* Can we merge with the previous block? */
 354           if ((av_table[index].av_adr
 355                + av_table[index].av_size) == new_el.av_adr)
 356             {
 357               /* Simply expand the endtry. */
 358               av_table[index].av_size += new_el.av_size;
 359             }
 360             /* Can we merge with the next block? */
 361             else if ((new_el.av_adr
 362                       + new_el.av_size) == av_table[index].av_adr)
 363               {
 364                 /* Update this entry. */
 365                 av_table[index].av_adr = new_el.av_adr;
 366                 av_table[index].av_size += new_el.av_size;
 367               }
 368             /* Not contiguous */
 369             else
 370               {
 371                 index++;
 372                 continue;
 373               }
 374
 375             /* If we got here, we're done. */
 376             return TRUE;
 377         }
 378     }
 379
 380   /* Search for place to put element.  List is sorted by size. */
 381   index = 0;
 382   while (index < *av_count && av_table[index].av_size < new_el.av_size)
 383     {
 384       index++;
 385     }
 386
 387   /* Move all others up one. */
 388   index1 = *av_count-1;
 389   while (index1 >= index)
 390     {
 391       av_table[index1+1] = av_table[index1];
 392       index1--;
 393     }
 394
 395   /* Add the new element. */
 396   av_table[index] = new_el;
 397
 398   /* Increment the number of elements. */
 399   *av_count += 1;
 400
 401   return TRUE;
 402 }
 403
 404
 405
 406
 407
 408 /* Get_block "allocates" new file space and the end of the file.  This is
 409    done in integral block sizes.  (This helps insure that data smaller than
 410    one block size is in a single block.)  Enough blocks are allocated to
 411    make sure the number of bytes allocated in the blocks is larger than SIZE.
 412    DBF contains the file header that needs updating.  This routine does
 413    no I/O.  */
 414
 415 static avail_elem
 416 get_block (int size, GDBM_FILE dbf)
 417 {
 418   avail_elem val;
 419
 420   /* Need at least one block. */
 421   val.av_adr  = dbf->header->next_block;
 422   val.av_size = dbf->header->block_size;
 423
 424   /* Get enough blocks to fit the need. */
 425   while (val.av_size < size)
 426     val.av_size += dbf->header->block_size;
 427
 428   /* Update the header and return. */
 429   dbf->header->next_block += val.av_size;
 430
 431   /* We changed the header. */
 432   dbf->header_changed = TRUE;
 433
 434   return val;
 435
 436 }
 437
 438
 439 /*  When the header already needs writing, we can make sure the current
 440     bucket has its avail block as close to 1/3 full as possible. */
 441 static void
 442 adjust_bucket_avail (GDBM_FILE dbf)
 443 {
 444   int third = BUCKET_AVAIL / 3;
 445   avail_elem av_el;
 446
 447   /* Can we add more entries to the bucket? */
 448   if (dbf->bucket->av_count < third)
 449     {
 450       if (dbf->header->avail.count > 0)
 451         {
 452           dbf->header->avail.count -= 1;
 453           av_el = dbf->header->avail.av_table[dbf->header->avail.count];
 454           _gdbm_put_av_elem (av_el, dbf->bucket->bucket_avail,
 455                              &dbf->bucket->av_count, dbf->coalesce_blocks);
 456           dbf->bucket_changed = TRUE;
 457         }
 458       return;
 459     }
 460
 461   /* Is there too much in the bucket? */
 462   while (dbf->bucket->av_count > BUCKET_AVAIL-third
 463          && dbf->header->avail.count < dbf->header->avail.size)
 464     {
 465       av_el = get_elem (0, dbf->bucket->bucket_avail, &dbf->bucket->av_count);
 466       _gdbm_put_av_elem (av_el, dbf->header->avail.av_table,
 467                          &dbf->header->avail.count, dbf->coalesce_blocks);
 468       dbf->bucket_changed = TRUE;
 469     }
 470 }