|
DataMuseum.dkPresents historical artifacts from the history of: DKUUG/EUUG Conference tapes |
This is an automatic "excavation" of a thematic subset of
See our Wiki for more about DKUUG/EUUG Conference tapes Excavated with: AutoArchaeologist - Free & Open Source Software. |
top - metrics - downloadIndex: T f
Length: 21568 (0x5440)
Types: TextFile
Names: »falloc.c«
└─⟦a05ed705a⟧ Bits:30007078 DKUUG GNU 2/12/89
└─⟦0befd2614⟧ »./gdbm-0.8.tar.Z«
└─⟦b993d2893⟧
└─⟦this⟧ »gdbm/falloc.c«
/* falloc.c - The file space management routines for dbm. */
/* GNU DBM - DataBase Manager (database subroutines) by Philip A. Nelson
Copyright (C) 1989 Free Software Foundation, Inc.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
You may contact the author by:
e-mail: phil@wwu.edu
us-mail: Philip A. Nelson
Computer Science Department
Western Washington University
Bellingham, WA 98226
phone: (206) 676-3035
*************************************************************************/
#include <stdio.h>
#include <sys/file.h>
#include <sys/types.h>
#include <sys/stat.h>
#include "gdbm.h"
static int free_adr; /* When allocating a block, we may need */
static int free_size; /* to "free" part of a previous block. */
/* Allocate space in the file DBF for a block NUM_BYTES in length. Return
the file address of the start of the block. Allocation is done on a
first fit basis. The avail structure is changed by this routine if a
change is needed. If AT_BLOCK_START is true, the allocation is wanted
at the start of read/write block. This is used for allocating new buckets,
new directories or any other structure that should start at the start
of a block. If an error occurs, the value of 0 will be returned. */
int
_dbm_alloc (dbf, num_bytes, at_block_start)
dbm_file_info *dbf;
int num_bytes;
int at_block_start;
{
int new_address;
/* Get the new address. */
new_address = _file_alloc (dbf, num_bytes, at_block_start);
/* Free unused space on previous block if there is any. */
if (free_size != 0)
_dbm_free (dbf, free_adr, free_size);
return new_address;
}
/* This is the routine that does all the work for _dbm_alloc except doing the
final freeing of space freed by a block allocation. This is to allow
_dbm_free to work correctly and stop recursion. */
static int
_file_alloc (dbf, num_bytes, at_block_start)
dbm_file_info *dbf;
int num_bytes;
int at_block_start;
{
int file_adr; /* The address of the block. */
int temp; /* For temporary storage. */
avail_elem *av_el; /* For temporary accesss to elements. */
/* Start by checking the avail structure. Load the avail block that has
the "best" chance of having the correct element in it. */
temp = num_bytes >> AVAIL_BITS;
if (temp >= AVAIL_SIZE)
temp = AVAIL_SIZE -1;
temp = dbf->header.avail_list[temp];
get_avail_block (dbf, temp, dbf->avail, &dbf->avail_adr);
/* Initialize free_size so we don't free something already freed. */
free_size = 0;
/* Now look in the avail list.*/
while (dbf->avail_adr != 0)
{
/* Check the local block for what we want. */
for (temp = 0; temp < dbf->avail->count; temp++)
{
av_el = &dbf->avail->av_table[temp];
if (av_el->av_size >= num_bytes
&& (!at_block_start || (av_el->av_adr
% dbf->header.block_size) == 0) )
{
/* This is the block to allocate. */
file_adr = av_el->av_adr;
/* Delete the smaller item and remember it for later freeing. */
free_adr = av_el->av_adr + num_bytes;
free_size = av_el->av_size - num_bytes;
dbf->avail->count -= 1;
for (; temp < dbf->avail->count; temp++)
{
dbf->avail->av_table[temp] = dbf->avail->av_table[temp+1];
}
/* Write the updated current avail block. */
_dbm_update (dbf, 0x77777701, file_adr, num_bytes,
free_size, dbf->avail_adr);
write_avail_block (dbf, dbf->avail, &dbf->avail_adr);
return file_adr;
}
}
/* Nothing on this block. How about the next. */
get_avail_block (dbf, dbf->avail->next_block, dbf->avail, &dbf->avail_adr);
}
/* We did not allocate from the avail list, so allocate at the end of the file. */
if (at_block_start && (dbf->header.file_size % dbf->header.block_size) != 0)
{
/* Adjust file length to end of a block and set up for later freeing
of the unused space in the previous block. */
temp = dbf->header.file_size / dbf->header.block_size + 1;
file_adr = temp * dbf->header.block_size;
free_adr = dbf->header.file_size;
free_size = file_adr - dbf->header.file_size;
dbf->header.file_size = file_adr + num_bytes;
}
else
{
/* Allocate at next byte. */
file_adr = dbf->header.file_size;
free_size = 0;
dbf->header.file_size += num_bytes;
}
/* Update dbf->header on disk by calling _dbm_update. */
_dbm_update (dbf, 0x77777702, file_adr, num_bytes, free_adr, free_size);
/* Return the address. */
return file_adr;
}
\f
/* Free space of size NUM_BYTES in the file DBF at file address FILE_ADR. Make
it avaliable for reuse through _dbm_alloc. This routine changes the
avail structure. The value TRUE is returned if there were errors. If no
errors occured, the value FALSE is returned. */
_dbm_free (dbf, file_adr, num_bytes)
dbm_file_info *dbf;
int file_adr;
int num_bytes;
{
int temp;
int temp1;
/* Put it into the avail structure in sorted order by size. */
temp = num_bytes >> AVAIL_BITS;
if (temp >= AVAIL_SIZE)
temp = AVAIL_SIZE -1;
temp = dbf->header.avail_list[temp];
get_avail_block (dbf, temp, dbf->avail, &dbf->avail_adr);
/* Find the correct block. */
while (dbf->avail->next_block != 0
&& dbf->avail->av_table[dbf->avail->count-1].av_size < num_bytes)
get_avail_block (dbf, dbf->avail->next_block, dbf->avail, &dbf->avail_adr);
/* Find the correct place in the block; */
temp = 0;
while (temp < dbf->avail->count && dbf->avail->av_table[temp].av_size <= num_bytes)
temp++;
/* Move all down. */
for (temp1 = dbf->avail->count; temp1 > temp; temp1--)
dbf->avail->av_table[temp1] = dbf->avail->av_table[temp1-1];
/* Add it now. */
dbf->avail->av_table[temp].av_adr = file_adr;
dbf->avail->av_table[temp].av_size = num_bytes;
dbf->avail->count += 1;
_dbm_update (dbf, 0x77777703, file_adr, num_bytes,
dbf->avail_adr, dbf->avail->count);
write_avail_block(dbf, dbf->avail, &dbf->avail_adr);
/* Do we need more space? We do if the current updated block is full. */
if (dbf->avail->count == dbf->avail->size)
{
avail_block *block; /* The pointer to an avail block. */
avail_block *new_block; /* The pointer the a new avail block. */
int curr_block; /* The address of the current block. */
int prev_block; /* The address of the previous block. */
int next_block; /* The address of the next block. */
int new_adr; /* The address of the new block. */
int count; /* The number of items in the current avail block. */
int temp_adr; /* Used to force get_avail_block to read. */
/* Allocate space for another avail block. */
block = (avail_block *) alloca (dbf->header.block_size);
count = dbf->avail->count;
/* Can we share with previous block? */
prev_block = dbf->avail->prev_block;
if (prev_block != 0)
{
temp_adr = 0;
get_avail_block (dbf, prev_block, block, &temp_adr);
if (block->count < block->size / 2)
{
/* Adjust elements between the two blocks. */
temp = count - ((count + block->count) / 2); /* The number to copy. */
for (temp1 = 0; temp1 < temp; temp1++)
block->av_table[temp1+block->count] = dbf->avail->av_table[temp1];
for (temp1 = 0; temp1 < count-temp; temp1++)
dbf->avail->av_table[temp1] = dbf->avail->av_table[temp1+temp];
block->count += temp;
dbf->avail->count -= temp;
/* Adjust the pointers in the header. */
adjust_header (dbf, prev_block, block->av_table[0].av_size,
block->av_table[block->count-1].av_size,
dbf->avail_adr, dbf->avail->av_table[0].av_size,
dbf->avail->av_table[dbf->avail->count-1].av_size,
dbf->avail->next_block);
/* Update the disk. _dbm_update writes current header. */
_dbm_update (dbf, 0x77777704, dbf->avail_adr, count,
prev_block, block->count-temp);
write_avail_block(dbf, block, &prev_block);
write_avail_block(dbf, dbf->avail, &dbf->avail_adr);
/* Return with no errors. */
return FALSE;
}
}
/* Can we share with next block? */
next_block = dbf->avail->next_block;
if (next_block != 0)
{
temp_adr = 0;
get_avail_block (dbf, next_block, block, &temp_adr);
if (block->count < block->size / 2)
{
/* Adjust elements between the two blocks. */
temp = count - ((count + block->count) / 2); /* The number to copy. */
for (temp1 = block->count-1; temp1 >= 0; temp1--)
block->av_table[temp1+temp] = block->av_table[temp1];
for (temp1 = 0; temp1 < temp; temp1++)
block->av_table[count-temp+temp1] = dbf->avail->av_table[temp1];
block->count += temp;
dbf->avail->count -= temp;
/* Adjust the pointers in the header. */
adjust_header (dbf, dbf->avail_adr, dbf->avail->av_table[0].av_size,
dbf->avail->av_table[dbf->avail->count-1].av_size,
next_block, block->av_table[0].av_size,
block->av_table[block->count-1].av_size,
block->next_block);
/* Update the disk. _dbm_update writes current header. */
_dbm_update (dbf, 0x77777705, dbf->avail_adr, count,
next_block, block->count-temp);
write_avail_block(dbf, block, &next_block);
write_avail_block(dbf, dbf->avail, &dbf->avail_adr);
/* Return with no errors. */
return FALSE;
}
}
/* We can't share, so we must split the current block. */
curr_block = dbf->avail_adr;
new_block = (avail_block *) alloca (dbf->header.block_size);
/* Use the allocation procedure that does not call _dbm_free. */
new_adr = _file_alloc (dbf, dbf->header.block_size, TRUE);
/* Make dbf->avail the previous current block. It is possible
_file_alloc changed the structure by a little by removing one item.
It is guaranteed that _dbm_free was not called. */
get_avail_block (dbf, curr_block, dbf->avail, &dbf->avail_adr);
count = dbf->avail->count;
/* Do the split. */
temp1 = count / 2;
dbf->avail->next_block = new_adr;
dbf->avail->count = temp1;
new_block->size = dbf->avail->size;
new_block->prev_block = dbf->avail_adr;
new_block->next_block = next_block;
new_block->count = count-temp1;
for (temp = 0; temp1+temp < count; temp++)
new_block->av_table[temp] = dbf->avail->av_table[temp+temp1];
/* Adjust the pointers in the header. */
adjust_header (dbf, dbf->avail_adr, dbf->avail->av_table[0].av_size,
dbf->avail->av_table[temp1-1].av_size, new_adr,
new_block->av_table[0].av_size,
new_block->av_table[count-temp1-1].av_size, next_block);
_dbm_update (dbf, 0x77777706, dbf->avail_adr, count, new_adr, next_block);
/* Update next block. It is already read in, so just update it. */
if (next_block != 0)
{
block->prev_block = new_adr;
write_avail_block(dbf, block, &next_block);
}
write_avail_block(dbf, new_block, &new_adr);
write_avail_block(dbf, dbf->avail, &dbf->avail_adr);
/* Now that the split is complete, we can free any space left unused by
the call to _file_alloc. */
if (free_size != 0)
_dbm_free (dbf, free_adr, free_size);
}
/* No errors were found. */
return FALSE;
}
\f
/* Gets the avail block at AV_ADR in file DBF and put it into AVAIL_BLOCK.
CUR_ADR is the address of the block in AVAIL_BLOCK so it is possible
that this call does nothing but verify that AV_ADR is in AVAIL_BLOCK. */
static
get_avail_block (dbf, av_adr, avail_block, cur_adr)
dbm_file_info *dbf;
int av_adr;
int *avail_block;
int *cur_adr;
{
int num_bytes; /* For reading. */
if (*cur_adr != av_adr)
{
*cur_adr = av_adr;
if (*cur_adr != 0)
{
num_bytes = lseek (dbf->desc, *cur_adr, L_SET);
if (num_bytes != *cur_adr) _dbm_fatal(dbf, "lseek error");
num_bytes = read (dbf->desc, avail_block, dbf->header.block_size);
if (num_bytes != dbf->header.block_size) _dbm_fatal(dbf, "read error");
}
}
}
/* Writes the AVAIL_BLOCK to file DBF at address CUR_ADR. */
static
write_avail_block (dbf, avail_block, cur_adr)
dbm_file_info *dbf;
int *avail_block;
int *cur_adr;
{
int num_bytes;
/* Update the disk. */
num_bytes = lseek (dbf->desc, *cur_adr, L_SET);
if (num_bytes != *cur_adr) _dbm_fatal(dbf, "lseek error");
num_bytes = write (dbf->desc, avail_block, dbf->header.block_size);
if (num_bytes != dbf->header.block_size) _dbm_fatal(dbf, "write error");
fsync (dbf->desc);
}
/* Adjust the avail pointers to point correctly. */
static
adjust_header (dbf, block1, low1, high1, block2, low2, high2, next)
dbm_file_info *dbf;
int block1, low1, high1, block2, low2, high2, next;
{
int temp;
/* Truncate the bits into indices in avail_list. */
low1 = (low1 >> AVAIL_BITS) + 1;
high1 = high1 >> AVAIL_BITS;
low2 = low2 >> AVAIL_BITS;
high2 = high2 >> AVAIL_BITS;
/* Update for the first block. */
if (low1 >= AVAIL_SIZE) return;
if (high1 >= AVAIL_SIZE) high1 = AVAIL_SIZE-1;
for (temp = low1; temp <= high1; temp++)
if (dbf->header.avail_list[temp] == block2)
dbf->header.avail_list[temp] = block1;
/* Update fo the second block. */
if (low2 >= AVAIL_SIZE) return;
if (high2 >= AVAIL_SIZE) high2 = AVAIL_SIZE-1;
if (low2 == high1) low2 += 1;
if (next == 0) high2 = AVAIL_SIZE-1;
for (temp = low2; temp <= high2; temp++)
if (dbf->header.avail_list[temp] == block1)
dbf->header.avail_list[temp] = block2;
}
\f
/* Repair the avail structure. dbmopen found the file in a state where the
last operation to write the header came from falloc. UPDATE_CODE tells
which update operation was last and PARAM1 through PARAM4 give the details. */
_dbm_alloc_repair (dbf, update_code, param1, param2, param3, param4)
dbm_file_info *dbf;
int update_code;
int param1;
int param2;
int param3;
int param4;
{
int index; /* A general index varaible. */
switch (update_code)
{
case 1: /* _file_alloc - updating current avail block.
param1 = address of new allocation.
param2 = size of new allocation.
param3 = size of unused portion.
param4 = address of avail block. */
/* Get the block that was being updated. */
get_avail_block (dbf, param4, dbf->avail, &dbf->avail_adr);
/* Search for the allocated entry. */
index = 0;
while (index < dbf->avail->count
&& dbf->avail->av_table[index].av_adr != param1 )
index ++;
/* If it is not found, then the write was successful and we must free it. */
if (index == dbf->avail->count)
_dbm_free (dbf, param1, param2+param3);
break;
case 2: /* _file_alloc - allocating at the end of the file.
param1 = address of new allocation.
param2 = size of new allocation.
param3 = address of unused portion of previous block.
param4 = size of unused portion. */
/* The easiest solution is to free both blocks. */
_dbm_free (dbf, param1, param2);
_dbm_free (dbf, param3, param4);
break;
case 3: /* _dbm_free - updating current avail block.
param1 = address of new available block.
param2 = size of new avaliable block.
param3 = address of the avail block.
param4 = size of avail block. */
/* Get the block that was being updated. */
get_avail_block (dbf, param3, dbf->avail, &dbf->avail_adr);
/* If the count is correct, the block was written. */
if (param4 != dbf->avail->count)
_dbm_free (dbf, param1, param2);
break;
case 4: /* _dbm_free - splitting current avail block.
Sharing with the previous block.
param1 = address of current block.
param2 = size of current block before split.
param3 = address of previous block.
param4 = size of previous block before split. */
{
avail_block *block1, *block2; /* Blocks for making corrections. */
int adr1, adr2; /* Addresses of the blocks. */
/* Allocate the space. */
block1 = (avail_block *) alloca (dbf->header.block_size);
block2 = (avail_block *) alloca (dbf->header.block_size);
/* Get the block that was to be split. */
adr1 = 0;
get_avail_block (dbf, param1, block1, &adr1);
/* Check to see which ones were changed. */
if (block1->count == param2)
{
/* Current was not changed. */
int temp, temp1;
/* Get the block that was to receive items. */
adr2 = 0;
get_avail_block (dbf, param3, block2, &adr2);
temp = param2 - ((param2 + param4) / 2); /* The number to copy. */
if (block2->count == param4)
{
/* Previous was not changed, fix it. */
for (temp1 = 0; temp1 < temp; temp1++)
block2->av_table[temp1+param4] = block1->av_table[temp1];
write_avail_block (dbf, block2, &adr2);
}
/* Fix up "current" block. */
for (temp1 = 0; temp1 < param2 - temp; temp1++)
block1->av_table[temp1] = block1->av_table[temp1+temp];
block1->count -= temp;
write_avail_block (dbf, block1, &adr1);
}
}
break;
case 5: /* _dbm_free - splitting current avail block.
Sharing with the next block.
param1 = address of current block.
param2 = size of current block before split.
param3 = address of next
param4 = size of unused portion before split. */
{
avail_block *block1, *block2; /* Blocks for making corrections. */
int adr1, adr2; /* Addresses of the blocks. */
/* Allocate the space. */
block1 = (avail_block *) alloca (dbf->header.block_size);
block2 = (avail_block *) alloca (dbf->header.block_size);
/* Get the block that was to be split. */
adr1 = 0;
get_avail_block (dbf, param1, block1, &adr1);
/* Check to see which ones were changed. */
if (block1->count == param2)
{
/* Current was not changed. */
int temp, temp1;
/* Get the block that was to receive items. */
adr2 = 0;
get_avail_block (dbf, param3, block2, &adr2);
temp = param2 - ((param2 + param4) / 2); /* The number to copy. */
if (block2->count == param4)
{
/* Next was not changed, fix it. */
for (temp1 = param4-1; temp1 >= 0; temp1--)
block2->av_table[temp1+temp] = block2->av_table[temp1];
for (temp1 = 0; temp1 < temp; temp1++)
block2->av_table[temp1] = block1->av_table[param2-temp+temp1];
write_avail_block (dbf, block2, &adr2);
}
/* Fix up "current" block. */
block1->count -= temp;
write_avail_block (dbf, block1, &adr1);
}
}
break;
case 6: /* _dbm_free - splitting current avail block.
Creating a new block.
param1 = address of current block.
param2 = size of current block before the split.
param3 = address of new block.
param4 = address of the next block.
Note: This crash will loose a little free space. */
{
avail_block *block1, *block2; /* Blocks for making corrections. */
int adr1, adr2; /* Addresses of the blocks. */
/* Allocate the space. */
block1 = (avail_block *) alloca (dbf->header.block_size);
block2 = (avail_block *) alloca (dbf->header.block_size);
/* Get the block that was to be split. */
adr1 = 0;
get_avail_block (dbf, param1, block1, &adr1);
if (block1->count == param2)
{
/* The current block was not changed. */
int temp, temp1;
/* Resplit current. Set the address for block2. */
adr2 = param3;
/* Do the split. */
temp1 = param2 / 2;
block1->next_block = param3;
block1->count = temp1;
block2->size = block1->size;
block2->prev_block = param1;
block2->next_block = param4;
block2->count = param2-temp1;
for (temp = 0; temp1+temp < param2; temp++)
block2->av_table[temp] = block1->av_table[temp+temp1];
write_avail_block (dbf, block2, &adr2);
write_avail_block (dbf, block1, &adr1);
/* Make sure next_block is fixed. */
if (param4 != 0)
{
adr2 = 0;
get_avail_block (dbf, param4, block2, &adr2);
block2->prev_block = param3;
write_avail_block (dbf, block2, &adr2);
}
}
}
break;
}
}
\f
/* A debugging routine to see the stuff! */
_dbm_print_avail_list (dbf)
dbm_file_info *dbf;
{
int temp;
/* Start at the first block! */
get_avail_block (dbf, dbf->header.avail_list[0], dbf->avail, &dbf->avail_adr);
while (dbf->avail_adr != 0)
{
/* Print the block! */
printf ("\nblock = %d\nsize = %d\ncount = %d\n", dbf->avail_adr,
dbf->avail->size, dbf->avail->count);
for (temp = 0; temp < dbf->avail->count; temp++)
{
printf (" %15d %10d \n", dbf->avail->av_table[temp].av_size,
dbf->avail->av_table[temp].av_adr);
}
/* How about the next. */
get_avail_block (dbf, dbf->avail->next_block, dbf->avail, &dbf->avail_adr);
}
}