fs/hfs/balloc.c

   1 /*
   2  * linux/fs/hfs/balloc.c
   3  *
   4  * Copyright (C) 1995-1997  Paul H. Hargrove
   5  * This file may be distributed under the terms of the GNU General Public License.
   6  *
   7  * hfs_bnode_alloc() and hfs_bnode_bitop() are based on GPLed code
   8  * Copyright (C) 1995  Michael Dreher
   9  *
  10  * This file contains the code to create and destroy nodes
  11  * in the B-tree structure.
  12  *
  13  * "XXX" in a comment is a note to myself to consider changing something.
  14  *
  15  * In function preconditions the term "valid" applied to a pointer to
  16  * a structure means that the pointer is non-NULL and the structure it
  17  * points to has all fields initialized to consistent values.
  18  *
  19  * The code in this file initializes some structures which contain
  20  * pointers by calling memset(&foo, 0, sizeof(foo)).
  21  * This produces the desired behavior only due to the non-ANSI
  22  * assumption that the machine representation of NULL is all zeros.
  23  */
  24
  25 #include "hfs_btree.h"
  26
  27 /*================ File-local functions ================*/
  28
  29 /*
  30  * get_new_node()
  31  *
  32  * Get a buffer for a new node with out reading it from disk.
  33  */
  34 static hfs_buffer get_new_node(struct hfs_btree *tree, hfs_u32 node)
  35 {
  36         int tmp;
  37         hfs_buffer retval = HFS_BAD_BUFFER;
  38
  39         tmp = hfs_extent_map(&tree->entry.u.file.data_fork, node, 0);
  40         if (tmp) {
  41                 retval = hfs_buffer_get(tree->sys_mdb, tmp, 0);
  42         }
  43         return retval;
  44 }
  45
  46 /*
  47  * hfs_bnode_init()
  48  *
  49  * Description:
  50  *   Initialize a newly allocated bnode.
  51  * Input Variable(s):
  52  *   struct hfs_btree *tree: Pointer to a B-tree
  53  *   hfs_u32 node: the node number to allocate
  54  * Output Variable(s):
  55  *   NONE
  56  * Returns:
  57  *   struct hfs_bnode_ref for the new node
  58  * Preconditions:
  59  *   'tree' points to a "valid" (struct hfs_btree)
  60  *   'node' exists and has been allocated in the bitmap of bnodes.
  61  * Postconditions:
  62  *   On success:
  63  *    The node is not read from disk, nor added to the bnode cache.
  64  *    The 'sticky' and locking-related fields are all zero/NULL.
  65  *    The bnode's nd{[FB]Link, Type, NHeight} fields are uninitialized.
  66  *    The bnode's ndNRecs field and offsets table indicate an empty bnode.
  67  *   On failure:
  68  *    The node is deallocated.
  69  */
  70 static struct hfs_bnode_ref hfs_bnode_init(struct hfs_btree * tree,
  71                                            hfs_u32 node)
  72 {
  73 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  74         extern int bnode_count;
  75 #endif
  76         struct hfs_bnode_ref retval;
  77
  78         retval.lock_type = HFS_LOCK_NONE;
  79         if (!HFS_NEW(retval.bn)) {
  80                 hfs_warn("hfs_bnode_init: out of memory.\n");
  81                 goto bail2;
  82         }
  83
  84         /* Partially initialize the in-core structure */
  85         memset(retval.bn, 0, sizeof(*retval.bn));
  86         retval.bn->magic = HFS_BNODE_MAGIC;
  87         retval.bn->tree = tree;
  88         retval.bn->node = node;
  89         hfs_init_waitqueue(&retval.bn->wqueue);
  90         hfs_init_waitqueue(&retval.bn->rqueue);
  91         hfs_bnode_lock(&retval, HFS_LOCK_WRITE);
  92
  93         retval.bn->buf = get_new_node(tree, node);
  94         if (!hfs_buffer_ok(retval.bn->buf)) {
  95                 goto bail1;
  96         }
  97
  98 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  99         ++bnode_count;
 100 #endif
 101
 102         /* Partially initialize the on-disk structure */
 103         memset(hfs_buffer_data(retval.bn->buf), 0, HFS_SECTOR_SIZE);
 104         hfs_put_hs(sizeof(struct NodeDescriptor), RECTBL(retval.bn, 1));
 105
 106         return retval;
 107
 108 bail1:
 109         HFS_DELETE(retval.bn);
 110 bail2:
 111         /* clear the bit in the bitmap */
 112         hfs_bnode_bitop(tree, node, 0);
 113         return retval;
 114 }
 115
 116 /*
 117  * init_mapnode()
 118  *
 119  * Description:
 120  *   Initializes a given node as a mapnode in the given tree.
 121  * Input Variable(s):
 122  *   struct hfs_bnode *bn: the node to add the mapnode after.
 123  *   hfs_u32: the node to use as a mapnode.
 124  * Output Variable(s):
 125  *   NONE
 126  * Returns:
 127  *   struct hfs_bnode *: the new mapnode or NULL
 128  * Preconditions:
 129  *   'tree' is a valid (struct hfs_btree).
 130  *   'node' is the number of the first node in 'tree' that is not
 131  *    represented by a bit in the existing mapnodes.
 132  * Postconditions:
 133  *   On failure 'tree' is unchanged and NULL is returned.
 134  *   On success the node given by 'node' has been added to the linked
 135  *    list of mapnodes attached to 'tree', and has been initialized as
 136  *    a valid mapnode with its first bit set to indicate itself as
 137  *    allocated.
 138  */
 139 static struct hfs_bnode *init_mapnode(struct hfs_bnode *bn, hfs_u32 node)
 140 {
 141 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 142         extern int bnode_count;
 143 #endif
 144         struct hfs_bnode *retval;
 145
 146         if (!HFS_NEW(retval)) {
 147                 hfs_warn("hfs_bnode_add: out of memory.\n");
 148                 return NULL;
 149         }
 150
 151         memset(retval, 0, sizeof(*retval));
 152         retval->magic = HFS_BNODE_MAGIC;
 153         retval->tree = bn->tree;
 154         retval->node = node;
 155         retval->sticky = HFS_STICKY;
 156         retval->buf = get_new_node(bn->tree, node);
 157         if (!hfs_buffer_ok(retval->buf)) {
 158                 HFS_DELETE(retval);
 159                 return NULL;
 160         }
 161
 162 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 163         ++bnode_count;
 164 #endif
 165
 166         /* Initialize the bnode data structure */
 167         memset(hfs_buffer_data(retval->buf), 0, HFS_SECTOR_SIZE);
 168         retval->ndFLink = 0;
 169         retval->ndBLink = bn->node;
 170         retval->ndType = ndMapNode;
 171         retval->ndNHeight = 0;
 172         retval->ndNRecs = 1;
 173         hfs_put_hs(sizeof(struct NodeDescriptor), RECTBL(retval, 1));
 174         hfs_put_hs(0x1fa,                         RECTBL(retval, 2));
 175         *((hfs_u8 *)bnode_key(retval, 1)) = 0x80; /* set first bit of bitmap */
 176         retval->prev = bn;
 177         hfs_bnode_commit(retval);
 178
 179         bn->ndFLink = node;
 180         bn->next = retval;
 181         hfs_bnode_commit(bn);
 182
 183         return retval;
 184 }
 185
 186 /*================ Global functions ================*/
 187
 188 /*
 189  * hfs_bnode_bitop()
 190  *
 191  * Description:
 192  *   Allocate/free the requested node of a B-tree of the hfs filesystem
 193  *   by setting/clearing the corresponding bit in the B-tree bitmap.
 194  *   The size of the B-tree will not be changed.
 195  * Input Variable(s):
 196  *   struct hfs_btree *tree: Pointer to a B-tree
 197  *   hfs_u32 bitnr: The node number to free
 198  *   int set: 0 to clear the bit, non-zero to set it.
 199  * Output Variable(s):
 200  *   None
 201  * Returns:
 202  *    0: no error
 203  *   -1: The node was already allocated/free, nothing has been done.
 204  *   -2: The node is out of range of the B-tree.
 205  *   -4: not enough map nodes to hold all the bits
 206  * Preconditions:
 207  *   'tree' points to a "valid" (struct hfs_btree)
 208  *   'bitnr' is a node number within the range of the btree, which is
 209  *   currently free/allocated.
 210  * Postconditions:
 211  *   The bit number 'bitnr' of the node bitmap is set/cleared and the
 212  *   number of free nodes in the btree is decremented/incremented by one.
 213  */
 214 int hfs_bnode_bitop(struct hfs_btree *tree, hfs_u32 bitnr, int set)
 215 {
 216         struct hfs_bnode *bn;   /* the current bnode */
 217         hfs_u16 start;          /* the start (in bits) of the bitmap in node */
 218         hfs_u16 len;            /* the len (in bits) of the bitmap in node */
 219         hfs_u32 *u32;           /* address of the u32 containing the bit */
 220
 221         if (bitnr >= tree->bthNNodes) {
 222                 hfs_warn("hfs_bnode_bitop: node number out of range.\n");
 223                 return -2;
 224         }
 225
 226         bn = &tree->head;
 227         for (;;) {
 228                 start = bnode_offset(bn, bn->ndNRecs) << 3;
 229                 len = (bnode_offset(bn, bn->ndNRecs + 1) << 3) - start;
 230
 231                 if (bitnr < len) {
 232                         break;
 233                 }
 234
 235                 /* continue on to next map node if available */
 236                 if (!(bn = bn->next)) {
 237                         hfs_warn("hfs_bnode_bitop: too few map nodes.\n");
 238                         return -4;
 239                 }
 240                 bitnr -= len;
 241         }
 242
 243         /* Change the correct bit */
 244         bitnr += start;
 245         u32 = (hfs_u32 *)hfs_buffer_data(bn->buf) + (bitnr >> 5);
 246         bitnr %= 32;
 247         if ((set && hfs_set_bit(bitnr, u32)) ||
 248             (!set && !hfs_clear_bit(bitnr, u32))) {
 249                 hfs_warn("hfs_bnode_bitop: bitmap corruption.\n");
 250                 return -1;
 251         }
 252         hfs_buffer_dirty(bn->buf);
 253
 254         /* adjust the free count */
 255         tree->bthFree += (set ? -1 : 1);
 256         tree->dirt = 1;
 257
 258         return 0;
 259 }
 260
 261 /*
 262  * hfs_bnode_alloc()
 263  *
 264  * Description:
 265  *   Find a cleared bit in the B-tree node bitmap of the hfs filesystem,
 266  *   set it and return the corresponding bnode, with its contents zeroed.
 267  *   When there is no free bnode in the tree, an error is returned, no
 268  *   new nodes will be added by this function!
 269  * Input Variable(s):
 270  *   struct hfs_btree *tree: Pointer to a B-tree
 271  * Output Variable(s):
 272  *   NONE
 273  * Returns:
 274  *   struct hfs_bnode_ref for the new bnode
 275  * Preconditions:
 276  *   'tree' points to a "valid" (struct hfs_btree)
 277  *   There is at least one free bnode.
 278  * Postconditions:
 279  *   On success:
 280  *     The corresponding bit in the btree bitmap is set.
 281  *     The number of free nodes in the btree is decremented by one.
 282  *   The node is not read from disk, nor added to the bnode cache.
 283  *   The 'sticky' field is uninitialized.
 284  */
 285 struct hfs_bnode_ref hfs_bnode_alloc(struct hfs_btree *tree)
 286 {
 287         struct hfs_bnode *bn;   /* the current bnode */
 288         hfs_u32 bitnr = 0;      /* which bit are we examining */
 289         hfs_u16 first;          /* the first clear bit in this bnode */
 290         hfs_u16 start;          /* the start (in bits) of the bitmap in node */
 291         hfs_u16 end;            /* the end (in bits) of the bitmap in node */
 292         hfs_u32 *data;          /* address of the data in this bnode */
 293
 294         bn = &tree->head;
 295         for (;;) {
 296                 start = bnode_offset(bn, bn->ndNRecs) << 3;
 297                 end = bnode_offset(bn, bn->ndNRecs + 1) << 3;
 298                 data =  (hfs_u32 *)hfs_buffer_data(bn->buf);
 299
 300                 /* search the current node */
 301                 first = hfs_find_zero_bit(data, end, start);
 302                 if (first < end) {
 303                         break;
 304                 }
 305
 306                 /* continue search in next map node */
 307                 bn = bn->next;
 308
 309                 if (!bn) {
 310                         hfs_warn("hfs_bnode_alloc: too few map nodes.\n");
 311                         goto bail;
 312                 }
 313                 bitnr += (end - start);
 314         }
 315
 316         if ((bitnr += (first - start)) >= tree->bthNNodes) {
 317                 hfs_warn("hfs_bnode_alloc: no free nodes found, "
 318                          "count wrong?\n");
 319                 goto bail;
 320         }
 321
 322         if (hfs_set_bit(first % 32, data + (first>>5))) {
 323                 hfs_warn("hfs_bnode_alloc: bitmap corruption.\n");
 324                 goto bail;
 325         }
 326         hfs_buffer_dirty(bn->buf);
 327
 328         /* decrement the free count */
 329         --tree->bthFree;
 330         tree->dirt = 1;
 331
 332         return hfs_bnode_init(tree, bitnr);
 333
 334 bail:
 335         return (struct hfs_bnode_ref){NULL, HFS_LOCK_NONE};
 336 }
 337
 338 /*
 339  * hfs_btree_extend()
 340  *
 341  * Description:
 342  *   Adds nodes to a B*-tree if possible.
 343  * Input Variable(s):
 344  *   struct hfs_btree *tree: the btree to add nodes to.
 345  * Output Variable(s):
 346  *   NONE
 347  * Returns:
 348  *   void
 349  * Preconditions:
 350  *   'tree' is a valid (struct hfs_btree *).
 351  * Postconditions:
 352  *   If possible the number of nodes indicated by the tree's clumpsize
 353  *    have been added to the tree, updating all in-core and on-disk
 354  *    allocation information.
 355  *   If insufficient disk-space was available then fewer nodes may have
 356  *    been added than would be expected based on the clumpsize.
 357  *   In the case of the extents B*-tree this function will add fewer
 358  *    nodes than expected if adding more would result in an extent
 359  *    record for the extents tree being added to the extents tree.
 360  *    The situation could be dealt with, but doing so confuses Macs.
 361  */
 362 void hfs_btree_extend(struct hfs_btree *tree)
 363 {
 364         struct hfs_bnode_ref head;
 365         struct hfs_bnode *bn, *tmp;
 366         struct hfs_cat_entry *entry = &tree->entry;
 367         struct hfs_mdb *mdb = entry->mdb;
 368         hfs_u32 old_nodes, new_nodes, total_nodes, new_mapnodes, seen;
 369
 370         old_nodes = entry->u.file.data_fork.psize;
 371
 372         entry->u.file.data_fork.lsize += 1; /* rounded up to clumpsize */
 373         hfs_extent_adj(&entry->u.file.data_fork);
 374
 375         total_nodes = entry->u.file.data_fork.psize;
 376         entry->u.file.data_fork.lsize = total_nodes << HFS_SECTOR_SIZE_BITS;
 377         new_nodes = total_nodes - old_nodes;
 378         if (!new_nodes) {
 379                 return;
 380         }
 381
 382         head = hfs_bnode_find(tree, 0, HFS_LOCK_WRITE);
 383         if (!(bn = head.bn)) {
 384                 hfs_warn("hfs_btree_extend: header node not found.\n");
 385                 return;
 386         }
 387
 388         seen = 0;
 389         new_mapnodes = 0;
 390         for (;;) {
 391                 seen += bnode_rsize(bn, bn->ndNRecs) << 3;
 392
 393                 if (seen >= total_nodes) {
 394                         break;
 395                 }
 396
 397                 if (!bn->next) {
 398                         tmp = init_mapnode(bn, seen);
 399                         if (!tmp) {
 400                                 hfs_warn("hfs_btree_extend: "
 401                                          "can't build mapnode.\n");
 402                                 hfs_bnode_relse(&head);
 403                                 return;
 404                         }
 405                         ++new_mapnodes;
 406                 }
 407                 bn = bn->next;
 408         }
 409         hfs_bnode_relse(&head);
 410
 411         tree->bthNNodes = total_nodes;
 412         tree->bthFree += (new_nodes - new_mapnodes);
 413         tree->dirt = 1;
 414
 415         /* write the backup MDB, not returning until it is written */
 416         hfs_mdb_commit(mdb, 1);
 417
 418         return;
 419 }
 420
 421 /*
 422  * hfs_bnode_free()
 423  *
 424  * Remove a node from the cache and mark it free in the bitmap.
 425  */
 426 int hfs_bnode_free(struct hfs_bnode_ref *bnr)
 427 {
 428         hfs_u32 node = bnr->bn->node;
 429         struct hfs_btree *tree = bnr->bn->tree;
 430
 431         if (bnr->bn->count != 1) {
 432                 hfs_warn("hfs_bnode_free: count != 1.\n");
 433                 return -EIO;
 434         }
 435
 436         hfs_bnode_relse(bnr);
 437         hfs_bnode_bitop(tree, node, 0);
 438         return 0;
 439 }