5 kx /* falloc.c - The file space management routines for dbm. */
5 kx
5 kx /* This file is part of GDBM, the GNU data base manager.
5 kx Copyright (C) 1990, 1991, 1993, 1994, 2007, 2011, 2013 Free Software
5 kx Foundation, Inc.
5 kx
5 kx GDBM is free software; you can redistribute it and/or modify
5 kx it under the terms of the GNU General Public License as published by
5 kx the Free Software Foundation; either version 3, or (at your option)
5 kx any later version.
5 kx
5 kx GDBM is distributed in the hope that it will be useful,
5 kx but WITHOUT ANY WARRANTY; without even the implied warranty of
5 kx MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
5 kx GNU General Public License for more details.
5 kx
5 kx You should have received a copy of the GNU General Public License
5 kx along with GDBM. If not, see <http://www.gnu.org/licenses/>. */
5 kx
5 kx /* Include system configuration before all else. */
5 kx #include "autoconf.h"
5 kx
5 kx #include "gdbmdefs.h"
5 kx
5 kx
5 kx /* The forward definitions for this file. See the functions for
5 kx the definition of the function. */
5 kx
5 kx static avail_elem get_elem (int, avail_elem [], int *);
5 kx static avail_elem get_block (int, GDBM_FILE);
5 kx static void push_avail_block (GDBM_FILE);
5 kx static void pop_avail_block (GDBM_FILE);
5 kx static void adjust_bucket_avail (GDBM_FILE);
5 kx
5 kx /* Allocate space in the file DBF for a block NUM_BYTES in length. Return
5 kx the file address of the start of the block.
5 kx
5 kx Each hash bucket has a fixed size avail table. We first check this
5 kx avail table to satisfy the request for space. In most cases we can
5 kx and this causes changes to be only in the current hash bucket.
5 kx Allocation is done on a first fit basis from the entries. If a
5 kx request can not be satisfied from the current hash bucket, then it is
5 kx satisfied from the file header avail block. If nothing is there that
5 kx has enough space, another block at the end of the file is allocated
5 kx and the unused portion is returned to the avail block. This routine
5 kx "guarantees" that an allocation does not cross a block boundary unless
5 kx the size is larger than a single block. The avail structure is
5 kx changed by this routine if a change is needed. If an error occurs,
5 kx the value of 0 will be returned. */
5 kx
5 kx off_t
5 kx _gdbm_alloc (GDBM_FILE dbf, int num_bytes)
5 kx {
5 kx off_t file_adr; /* The address of the block. */
5 kx avail_elem av_el; /* For temporary use. */
5 kx
5 kx /* The current bucket is the first place to look for space. */
5 kx av_el = get_elem (num_bytes, dbf->bucket->bucket_avail,
5 kx &dbf->bucket->av_count);
5 kx
5 kx /* If we did not find some space, we have more work to do. */
5 kx if (av_el.av_size == 0)
5 kx {
5 kx /* If the header avail table is less than half full, and there's
5 kx something on the stack. */
5 kx if ((dbf->header->avail.count <= (dbf->header->avail.size >> 1))
5 kx && (dbf->header->avail.next_block != 0))
5 kx pop_avail_block (dbf);
5 kx
5 kx /* check the header avail table next */
5 kx av_el = get_elem (num_bytes, dbf->header->avail.av_table,
5 kx &dbf->header->avail.count);
5 kx if (av_el.av_size == 0)
5 kx /* Get another full block from end of file. */
5 kx av_el = get_block (num_bytes, dbf);
5 kx
5 kx dbf->header_changed = TRUE;
5 kx }
5 kx
5 kx /* We now have the place from which we will allocate the new space. */
5 kx file_adr = av_el.av_adr;
5 kx
5 kx /* Put the unused space back in the avail block. */
5 kx av_el.av_adr += num_bytes;
5 kx av_el.av_size -= num_bytes;
5 kx _gdbm_free (dbf, av_el.av_adr, av_el.av_size);
5 kx
5 kx /* Return the address. */
5 kx return file_adr;
5 kx
5 kx }
5 kx
5 kx
5 kx
5 kx /* Free space of size NUM_BYTES in the file DBF at file address FILE_ADR. Make
5 kx it avaliable for reuse through _gdbm_alloc. This routine changes the
5 kx avail structure. */
5 kx
5 kx void
5 kx _gdbm_free (GDBM_FILE dbf, off_t file_adr, int num_bytes)
5 kx {
5 kx avail_elem temp;
5 kx
5 kx /* Is it too small to worry about? */
5 kx if (num_bytes <= IGNORE_SIZE)
5 kx return;
5 kx
5 kx /* Initialize the avail element. */
5 kx temp.av_size = num_bytes;
5 kx temp.av_adr = file_adr;
5 kx
5 kx /* Is the freed space large or small? */
5 kx if ((num_bytes >= dbf->header->block_size) || dbf->central_free)
5 kx {
5 kx if (dbf->header->avail.count == dbf->header->avail.size)
5 kx {
5 kx push_avail_block (dbf);
5 kx }
5 kx _gdbm_put_av_elem (temp, dbf->header->avail.av_table,
5 kx &dbf->header->avail.count, dbf->coalesce_blocks);
5 kx dbf->header_changed = TRUE;
5 kx }
5 kx else
5 kx {
5 kx /* Try to put into the current bucket. */
5 kx if (dbf->bucket->av_count < BUCKET_AVAIL)
5 kx _gdbm_put_av_elem (temp, dbf->bucket->bucket_avail,
5 kx &dbf->bucket->av_count, dbf->coalesce_blocks);
5 kx else
5 kx {
5 kx if (dbf->header->avail.count == dbf->header->avail.size)
5 kx {
5 kx push_avail_block (dbf);
5 kx }
5 kx _gdbm_put_av_elem (temp, dbf->header->avail.av_table,
5 kx &dbf->header->avail.count, dbf->coalesce_blocks);
5 kx dbf->header_changed = TRUE;
5 kx }
5 kx }
5 kx
5 kx if (dbf->header_changed)
5 kx adjust_bucket_avail (dbf);
5 kx
5 kx /* All work is done. */
5 kx return;
5 kx }
5 kx
5 kx
5 kx
5 kx /* The following are all utility routines needed by the previous two. */
5 kx
5 kx
5 kx /* Gets the avail block at the top of the stack and loads it into the
5 kx active avail block. It does a "free" for itself! This can (and is)
5 kx now called even when the avail block is not empty, so we must be
5 kx smart about things. */
5 kx
5 kx static void
5 kx pop_avail_block (GDBM_FILE dbf)
5 kx {
5 kx int rc;
5 kx off_t file_pos; /* For use with the lseek system call. */
5 kx avail_elem new_el;
5 kx avail_block *new_blk;
5 kx int index;
5 kx
5 kx if (dbf->header->avail.count == dbf->header->avail.size)
5 kx {
5 kx /* We're kind of stuck here, so we re-split the header in order to
5 kx avoid crashing. Sigh. */
5 kx push_avail_block(dbf);
5 kx }
5 kx
5 kx /* Set up variables. */
5 kx new_el.av_adr = dbf->header->avail.next_block;
5 kx new_el.av_size = ( ( (dbf->header->avail.size * sizeof (avail_elem)) >> 1)
5 kx + sizeof (avail_block));
5 kx
5 kx /* Allocate space for the block. */
5 kx new_blk = (avail_block *) malloc (new_el.av_size);
5 kx if (new_blk == NULL) _gdbm_fatal(dbf, _("malloc failed"));
5 kx
5 kx /* Read the block. */
5 kx file_pos = __lseek (dbf, new_el.av_adr, SEEK_SET);
5 kx if (file_pos != new_el.av_adr) _gdbm_fatal (dbf, _("lseek error"));
5 kx rc = _gdbm_full_read (dbf, new_blk, new_el.av_size);
5 kx if (rc)
5 kx _gdbm_fatal (dbf, gdbm_strerror (rc));
5 kx
5 kx /* Add the elements from the new block to the header. */
5 kx index = 0;
5 kx while (index < new_blk->count)
5 kx {
5 kx while(index < new_blk->count
5 kx && dbf->header->avail.count < dbf->header->avail.size)
5 kx {
5 kx /* With luck, this will merge a lot of blocks! */
5 kx _gdbm_put_av_elem(new_blk->av_table[index],
5 kx dbf->header->avail.av_table,
5 kx &dbf->header->avail.count, TRUE);
5 kx index++;
5 kx }
5 kx if (dbf->header->avail.count == dbf->header->avail.size)
5 kx {
5 kx /* We're kind of stuck here, so we re-split the header in order to
5 kx avoid crashing. Sigh. */
5 kx push_avail_block(dbf);
5 kx }
5 kx }
5 kx
5 kx /* Fix next_block, as well. */
5 kx dbf->header->avail.next_block = new_blk->next_block;
5 kx
5 kx /* We changed the header. */
5 kx dbf->header_changed = TRUE;
5 kx
5 kx /* Free the previous avail block. It is possible that the header table
5 kx is now FULL, which will cause us to overflow it! */
5 kx if (dbf->header->avail.count == dbf->header->avail.size)
5 kx {
5 kx /* We're kind of stuck here, so we re-split the header in order to
5 kx avoid crashing. Sigh. */
5 kx push_avail_block(dbf);
5 kx }
5 kx
5 kx _gdbm_put_av_elem (new_el, dbf->header->avail.av_table,
5 kx &dbf->header->avail.count, TRUE);
5 kx free (new_blk);
5 kx }
5 kx
5 kx
5 kx /* Splits the header avail block and pushes half onto the avail stack. */
5 kx
5 kx static void
5 kx push_avail_block (GDBM_FILE dbf)
5 kx {
5 kx int av_size;
5 kx off_t av_adr;
5 kx int index;
5 kx off_t file_pos;
5 kx avail_block *temp;
5 kx avail_elem new_loc;
5 kx int rc;
5 kx
5 kx /* Caclulate the size of the split block. */
5 kx av_size = ( (dbf->header->avail.size * sizeof (avail_elem)) >> 1)
5 kx + sizeof (avail_block);
5 kx
5 kx /* Get address in file for new av_size bytes. */
5 kx new_loc = get_elem (av_size, dbf->header->avail.av_table,
5 kx &dbf->header->avail.count);
5 kx if (new_loc.av_size == 0)
5 kx new_loc = get_block (av_size, dbf);
5 kx av_adr = new_loc.av_adr;
5 kx
5 kx
5 kx /* Split the header block. */
5 kx temp = (avail_block *) calloc (1, av_size);
5 kx if (temp == NULL) _gdbm_fatal (dbf, _("malloc error"));
5 kx /* Set the size to be correct AFTER the pop_avail_block. */
5 kx temp->size = dbf->header->avail.size;
5 kx temp->count = 0;
5 kx temp->next_block = dbf->header->avail.next_block;
5 kx dbf->header->avail.next_block = av_adr;
5 kx for (index = 1; index < dbf->header->avail.count; index++)
5 kx if ( (index & 0x1) == 1) /* Index is odd. */
5 kx temp->av_table[temp->count++] = dbf->header->avail.av_table[index];
5 kx else
5 kx dbf->header->avail.av_table[index>>1]
5 kx = dbf->header->avail.av_table[index];
5 kx
5 kx /* Update the header avail count to previous size divided by 2. */
5 kx dbf->header->avail.count >>= 1;
5 kx
5 kx /* Free the unneeded space. */
5 kx new_loc.av_adr += av_size;
5 kx new_loc.av_size -= av_size;
5 kx _gdbm_free (dbf, new_loc.av_adr, new_loc.av_size);
5 kx
5 kx /* Update the disk. */
5 kx file_pos = __lseek (dbf, av_adr, SEEK_SET);
5 kx if (file_pos != av_adr) _gdbm_fatal (dbf, _("lseek error"));
5 kx rc = _gdbm_full_write (dbf, temp, av_size);
5 kx if (rc)
5 kx _gdbm_fatal (dbf, gdbm_strerror (rc));
5 kx free (temp);
5 kx }
5 kx
5 kx
5 kx
5 kx /* Get_elem returns an element in the AV_TABLE block which is
5 kx larger than SIZE. AV_COUNT is the number of elements in the
5 kx AV_TABLE. If an item is found, it extracts it from the AV_TABLE
5 kx and moves the other elements up to fill the space. If no block is
5 kx found larger than SIZE, get_elem returns a size of zero. This
5 kx routine does no I/O. */
5 kx
5 kx static avail_elem
5 kx get_elem (int size, avail_elem av_table[], int *av_count)
5 kx {
5 kx int index; /* For searching through the avail block. */
5 kx avail_elem val; /* The default return value. */
5 kx
5 kx /* Initialize default return value. */
5 kx val.av_adr = 0;
5 kx val.av_size = 0;
5 kx
5 kx /* Search for element. List is sorted by size. */
5 kx index = 0;
5 kx while (index < *av_count && av_table[index].av_size < size)
5 kx {
5 kx index++;
5 kx }
5 kx
5 kx /* Did we find one of the right size? */
5 kx if (index >= *av_count)
5 kx return val;
5 kx
5 kx /* Ok, save that element and move all others up one. */
5 kx val = av_table[index];
5 kx *av_count -= 1;
5 kx while (index < *av_count)
5 kx {
5 kx av_table[index] = av_table[index+1];
5 kx index++;
5 kx }
5 kx
5 kx return val;
5 kx }
5 kx
5 kx
5 kx /* This routine inserts a single NEW_EL into the AV_TABLE block.
5 kx This routine does no I/O. */
5 kx
5 kx int
5 kx _gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count,
5 kx int can_merge)
5 kx {
5 kx int index; /* For searching through the avail block. */
5 kx int index1;
5 kx
5 kx /* Is it too small to deal with? */
5 kx if (new_el.av_size <= IGNORE_SIZE)
5 kx return FALSE;
5 kx
5 kx if (can_merge == TRUE)
5 kx {
5 kx /* Search for blocks to coalesce with this one. */
5 kx index = 0;
5 kx
5 kx while (index < *av_count)
5 kx {
5 kx /* Can we merge with the previous block? */
5 kx if ((av_table[index].av_adr
5 kx + av_table[index].av_size) == new_el.av_adr)
5 kx {
5 kx /* Simply expand the endtry. */
5 kx av_table[index].av_size += new_el.av_size;
5 kx }
5 kx /* Can we merge with the next block? */
5 kx else if ((new_el.av_adr
5 kx + new_el.av_size) == av_table[index].av_adr)
5 kx {
5 kx /* Update this entry. */
5 kx av_table[index].av_adr = new_el.av_adr;
5 kx av_table[index].av_size += new_el.av_size;
5 kx }
5 kx /* Not contiguous */
5 kx else
5 kx {
5 kx index++;
5 kx continue;
5 kx }
5 kx
5 kx /* If we got here, we're done. */
5 kx return TRUE;
5 kx }
5 kx }
5 kx
5 kx /* Search for place to put element. List is sorted by size. */
5 kx index = 0;
5 kx while (index < *av_count && av_table[index].av_size < new_el.av_size)
5 kx {
5 kx index++;
5 kx }
5 kx
5 kx /* Move all others up one. */
5 kx index1 = *av_count-1;
5 kx while (index1 >= index)
5 kx {
5 kx av_table[index1+1] = av_table[index1];
5 kx index1--;
5 kx }
5 kx
5 kx /* Add the new element. */
5 kx av_table[index] = new_el;
5 kx
5 kx /* Increment the number of elements. */
5 kx *av_count += 1;
5 kx
5 kx return TRUE;
5 kx }
5 kx
5 kx
5 kx
5 kx
5 kx
5 kx /* Get_block "allocates" new file space and the end of the file. This is
5 kx done in integral block sizes. (This helps insure that data smaller than
5 kx one block size is in a single block.) Enough blocks are allocated to
5 kx make sure the number of bytes allocated in the blocks is larger than SIZE.
5 kx DBF contains the file header that needs updating. This routine does
5 kx no I/O. */
5 kx
5 kx static avail_elem
5 kx get_block (int size, GDBM_FILE dbf)
5 kx {
5 kx avail_elem val;
5 kx
5 kx /* Need at least one block. */
5 kx val.av_adr = dbf->header->next_block;
5 kx val.av_size = dbf->header->block_size;
5 kx
5 kx /* Get enough blocks to fit the need. */
5 kx while (val.av_size < size)
5 kx val.av_size += dbf->header->block_size;
5 kx
5 kx /* Update the header and return. */
5 kx dbf->header->next_block += val.av_size;
5 kx
5 kx /* We changed the header. */
5 kx dbf->header_changed = TRUE;
5 kx
5 kx return val;
5 kx
5 kx }
5 kx
5 kx
5 kx /* When the header already needs writing, we can make sure the current
5 kx bucket has its avail block as close to 1/3 full as possible. */
5 kx static void
5 kx adjust_bucket_avail (GDBM_FILE dbf)
5 kx {
5 kx int third = BUCKET_AVAIL / 3;
5 kx avail_elem av_el;
5 kx
5 kx /* Can we add more entries to the bucket? */
5 kx if (dbf->bucket->av_count < third)
5 kx {
5 kx if (dbf->header->avail.count > 0)
5 kx {
5 kx dbf->header->avail.count -= 1;
5 kx av_el = dbf->header->avail.av_table[dbf->header->avail.count];
5 kx _gdbm_put_av_elem (av_el, dbf->bucket->bucket_avail,
5 kx &dbf->bucket->av_count, dbf->coalesce_blocks);
5 kx dbf->bucket_changed = TRUE;
5 kx }
5 kx return;
5 kx }
5 kx
5 kx /* Is there too much in the bucket? */
5 kx while (dbf->bucket->av_count > BUCKET_AVAIL-third
5 kx && dbf->header->avail.count < dbf->header->avail.size)
5 kx {
5 kx av_el = get_elem (0, dbf->bucket->bucket_avail, &dbf->bucket->av_count);
5 kx _gdbm_put_av_elem (av_el, dbf->header->avail.av_table,
5 kx &dbf->header->avail.count, dbf->coalesce_blocks);
5 kx dbf->bucket_changed = TRUE;
5 kx }
5 kx }
Radix cross Linux
The main Radix cross Linux repository contains the build scripts of packages, which have the most complete and common functionality for desktop machines
452 Commits
2 Branches
1 Tag