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: phil@cs.wwu.edu 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 39static avail_elem get_elem __P((int, avail_elem [], int *)); 40static avail_elem get_block __P((int, gdbm_file_info *)); 41static void push_avail_block __P((gdbm_file_info *)); 42static void pop_avail_block __P((gdbm_file_info *)); 43static 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 61off_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 111void 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 173static void 174pop_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 249static void 250push_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 314static avail_elem 315get_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 354int 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 437static avail_elem 438get_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. */ 465static void 466adjust_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} 496