1 /* falloc.c - The file space management routines for dbm. */
3 /* This file is part of GDBM, the GNU data base manager.
4 Copyright (C) 1990, 1991, 1993, 1994, 2007, 2011, 2013 Free Software
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)
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.
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/>. */
20 /* Include system configuration before all else. */
26 /* The forward definitions for this file. See the functions for
27 the definition of the function. */
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);
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.
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. */
52 _gdbm_alloc (GDBM_FILE dbf, int num_bytes)
54 off_t file_adr; /* The address of the block. */
55 avail_elem av_el; /* For temporary use. */
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);
61 /* If we did not find some space, we have more work to do. */
62 if (av_el.av_size == 0)
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);
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);
77 dbf->header_changed = TRUE;
80 /* We now have the place from which we will allocate the new space. */
81 file_adr = av_el.av_adr;
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);
88 /* Return the address. */
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
100 _gdbm_free (GDBM_FILE dbf, off_t file_adr, int num_bytes)
104 /* Is it too small to worry about? */
105 if (num_bytes <= IGNORE_SIZE)
108 /* Initialize the avail element. */
109 temp.av_size = num_bytes;
110 temp.av_adr = file_adr;
112 /* Is the freed space large or small? */
113 if ((num_bytes >= dbf->header->block_size) || dbf->central_free)
115 if (dbf->header->avail.count == dbf->header->avail.size)
117 push_avail_block (dbf);
119 _gdbm_put_av_elem (temp, dbf->header->avail.av_table,
120 &dbf->header->avail.count, dbf->coalesce_blocks);
121 dbf->header_changed = TRUE;
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);
131 if (dbf->header->avail.count == dbf->header->avail.size)
133 push_avail_block (dbf);
135 _gdbm_put_av_elem (temp, dbf->header->avail.av_table,
136 &dbf->header->avail.count, dbf->coalesce_blocks);
137 dbf->header_changed = TRUE;
141 if (dbf->header_changed)
142 adjust_bucket_avail (dbf);
144 /* All work is done. */
150 /* The following are all utility routines needed by the previous two. */
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. */
159 pop_avail_block (GDBM_FILE dbf)
162 off_t file_pos; /* For use with the lseek system call. */
164 avail_block *new_blk;
167 if (dbf->header->avail.count == dbf->header->avail.size)
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);
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));
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"));
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);
188 _gdbm_fatal (dbf, gdbm_strerror (rc));
190 /* Add the elements from the new block to the header. */
192 while (index < new_blk->count)
194 while(index < new_blk->count
195 && dbf->header->avail.count < dbf->header->avail.size)
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);
203 if (dbf->header->avail.count == dbf->header->avail.size)
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);
211 /* Fix next_block, as well. */
212 dbf->header->avail.next_block = new_blk->next_block;
214 /* We changed the header. */
215 dbf->header_changed = TRUE;
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)
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);
226 _gdbm_put_av_elem (new_el, dbf->header->avail.av_table,
227 &dbf->header->avail.count, TRUE);
232 /* Splits the header avail block and pushes half onto the avail stack. */
235 push_avail_block (GDBM_FILE dbf)
245 /* Caclulate the size of the split block. */
246 av_size = ( (dbf->header->avail.size * sizeof (avail_elem)) >> 1)
247 + sizeof (avail_block);
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;
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;
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];
269 dbf->header->avail.av_table[index>>1]
270 = dbf->header->avail.av_table[index];
272 /* Update the header avail count to previous size divided by 2. */
273 dbf->header->avail.count >>= 1;
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);
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);
285 _gdbm_fatal (dbf, gdbm_strerror (rc));
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. */
299 get_elem (int size, avail_elem av_table[], int *av_count)
301 int index; /* For searching through the avail block. */
302 avail_elem val; /* The default return value. */
304 /* Initialize default return value. */
308 /* Search for element. List is sorted by size. */
310 while (index < *av_count && av_table[index].av_size < size)
315 /* Did we find one of the right size? */
316 if (index >= *av_count)
319 /* Ok, save that element and move all others up one. */
320 val = av_table[index];
322 while (index < *av_count)
324 av_table[index] = av_table[index+1];
332 /* This routine inserts a single NEW_EL into the AV_TABLE block.
333 This routine does no I/O. */
336 _gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count,
339 int index; /* For searching through the avail block. */
342 /* Is it too small to deal with? */
343 if (new_el.av_size <= IGNORE_SIZE)
346 if (can_merge == TRUE)
348 /* Search for blocks to coalesce with this one. */
351 while (index < *av_count)
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)
357 /* Simply expand the endtry. */
358 av_table[index].av_size += new_el.av_size;
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)
364 /* Update this entry. */
365 av_table[index].av_adr = new_el.av_adr;
366 av_table[index].av_size += new_el.av_size;
375 /* If we got here, we're done. */
380 /* Search for place to put element. List is sorted by size. */
382 while (index < *av_count && av_table[index].av_size < new_el.av_size)
387 /* Move all others up one. */
388 index1 = *av_count-1;
389 while (index1 >= index)
391 av_table[index1+1] = av_table[index1];
395 /* Add the new element. */
396 av_table[index] = new_el;
398 /* Increment the number of elements. */
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
416 get_block (int size, GDBM_FILE dbf)
420 /* Need at least one block. */
421 val.av_adr = dbf->header->next_block;
422 val.av_size = dbf->header->block_size;
424 /* Get enough blocks to fit the need. */
425 while (val.av_size < size)
426 val.av_size += dbf->header->block_size;
428 /* Update the header and return. */
429 dbf->header->next_block += val.av_size;
431 /* We changed the header. */
432 dbf->header_changed = TRUE;
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. */
442 adjust_bucket_avail (GDBM_FILE dbf)
444 int third = BUCKET_AVAIL / 3;
447 /* Can we add more entries to the bucket? */
448 if (dbf->bucket->av_count < third)
450 if (dbf->header->avail.count > 0)
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;
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)
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;