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