fs/hfs/btree.c

   1 /*
   2  * linux/fs/hfs/btree.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  * This file contains the code to manipulate the B-tree structure.
   8  * The catalog and extents files are both B-trees.
   9  *
  10  * "XXX" in a comment is a note to myself to consider changing something.
  11  *
  12  * In function preconditions the term "valid" applied to a pointer to
  13  * a structure means that the pointer is non-NULL and the structure it
  14  * points to has all fields initialized to consistent values.
  15  *
  16  * The code in this file initializes some structures which contain
  17  * pointers by calling memset(&foo, 0, sizeof(foo)).
  18  * This produces the desired behavior only due to the non-ANSI
  19  * assumption that the machine representation of NULL is all zeros.
  20  */
  21
  22 #include "hfs_btree.h"
  23
  24 /*================ File-local functions ================*/
  25
  26 /*
  27  * hfs_bnode_ditch()
  28  *
  29  * Description:
  30  *   This function deletes an entire linked list of bnodes, so it
  31  *   does not need to keep the linked list consistent as
  32  *   hfs_bnode_delete() does.
  33  *   Called by hfs_btree_init() for error cleanup and by hfs_btree_free().
  34  * Input Variable(s):
  35  *   struct hfs_bnode *bn: pointer to the first (struct hfs_bnode) in
  36  *    the linked list to be deleted.
  37  * Output Variable(s):
  38  *   NONE
  39  * Returns:
  40  *   void
  41  * Preconditions:
  42  *   'bn' is NULL or points to a "valid" (struct hfs_bnode) with a 'prev'
  43  *    field of NULL.
  44  * Postconditions:
  45  *   'bn' and all (struct hfs_bnode)s in the chain of 'next' pointers
  46  *   are deleted, freeing the associated memory and hfs_buffer_put()ing
  47  *   the associated buffer.
  48  */
  49 static void hfs_bnode_ditch(struct hfs_bnode *bn) {
  50         struct hfs_bnode *tmp;
  51 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  52         extern int bnode_count;
  53 #endif
  54
  55         while (bn != NULL) {
  56                 tmp = bn->next;
  57 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  58                 hfs_warn("deleting node %d from tree %d with count %d\n",
  59                          bn->node, (int)ntohl(bn->tree->entry.cnid), bn->count);
  60                 --bnode_count;
  61 #endif
  62                 hfs_buffer_put(bn->buf); /* safe: checks for NULL argument */
  63
  64                 /* free all but the header */
  65                 if (bn->node) {
  66                         HFS_DELETE(bn);
  67                 }
  68                 bn = tmp;
  69         }
  70 }
  71
  72 /*================ Global functions ================*/
  73
  74 /*
  75  * hfs_btree_free()
  76  *
  77  * Description:
  78  *   This function frees a (struct hfs_btree) obtained from hfs_btree_init().
  79  *   Called by hfs_put_super().
  80  * Input Variable(s):
  81  *   struct hfs_btree *bt: pointer to the (struct hfs_btree) to free
  82  * Output Variable(s):
  83  *   NONE
  84  * Returns:
  85  *   void
  86  * Preconditions:
  87  *   'bt' is NULL or points to a "valid" (struct hfs_btree)
  88  * Postconditions:
  89  *   If 'bt' points to a "valid" (struct hfs_btree) then all (struct
  90  *    hfs_bnode)s associated with 'bt' are freed by calling
  91  *    hfs_bnode_ditch() and the memory associated with the (struct
  92  *    hfs_btree) is freed.
  93  *   If 'bt' is NULL or not "valid" an error is printed and nothing
  94  *    is changed.
  95  */
  96 void hfs_btree_free(struct hfs_btree *bt)
  97 {
  98         int lcv;
  99
 100         if (bt && (bt->magic == HFS_BTREE_MAGIC)) {
 101                 hfs_extent_free(&bt->entry.u.file.data_fork);
 102
 103                 for (lcv=0; lcv<HFS_CACHELEN; ++lcv) {
 104 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 105                         hfs_warn("deleting nodes from bucket %d:\n", lcv);
 106 #endif
 107                         hfs_bnode_ditch(bt->cache[lcv]);
 108                 }
 109
 110 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 111                 hfs_warn("deleting header and bitmap nodes\n");
 112 #endif
 113                 hfs_bnode_ditch(&bt->head);
 114
 115 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 116                 hfs_warn("deleting root node\n");
 117 #endif
 118                 hfs_bnode_ditch(bt->root);
 119
 120                 HFS_DELETE(bt);
 121         } else if (bt) {
 122                 hfs_warn("hfs_btree_free: corrupted hfs_btree.\n");
 123         }
 124 }
 125
 126 /*
 127  * hfs_btree_init()
 128  *
 129  * Description:
 130  *   Given some vital information from the MDB (HFS superblock),
 131  *   initializes the fields of a (struct hfs_btree).
 132  * Input Variable(s):
 133  *   struct hfs_mdb *mdb: pointer to the MDB
 134  *   ino_t cnid: the CNID (HFS_CAT_CNID or HFS_EXT_CNID) of the B-tree
 135  *   hfs_u32 tsize: the size, in bytes, of the B-tree
 136  *   hfs_u32 csize: the size, in bytes, of the clump size for the B-tree
 137  * Output Variable(s):
 138  *   NONE
 139  * Returns:
 140  *   (struct hfs_btree *): pointer to the initialized hfs_btree on success,
 141  *    or NULL on failure
 142  * Preconditions:
 143  *   'mdb' points to a "valid" (struct hfs_mdb)
 144  * Postconditions:
 145  *   Assuming the inputs are what they claim to be, no errors occur
 146  *   reading from disk, and no inconsistencies are noticed in the data
 147  *   read from disk, the return value is a pointer to a "valid"
 148  *   (struct hfs_btree).  If there are errors reading from disk or
 149  *   inconsistencies are noticed in the data read from disk, then and
 150  *   all resources that were allocated are released and NULL is
 151  *   returned.  If the inputs are not what they claim to be or if they
 152  *   are unnoticed inconsistencies in the data read from disk then the
 153  *   returned hfs_btree is probably going to lead to errors when it is
 154  *   used in a non-trivial way.
 155  */
 156 struct hfs_btree * hfs_btree_init(struct hfs_mdb *mdb, ino_t cnid,
 157                                   hfs_byte_t ext[12],
 158                                   hfs_u32 tsize, hfs_u32 csize)
 159 {
 160         struct hfs_btree * bt;
 161         struct BTHdrRec * th;
 162         struct hfs_bnode * tmp;
 163         unsigned int next;
 164 #if defined(DEBUG_HEADER) || defined(DEBUG_ALL)
 165         unsigned char *p, *q;
 166 #endif
 167
 168         if (!mdb || !ext || !HFS_NEW(bt)) {
 169                 goto bail3;
 170         }
 171
 172         bt->magic = HFS_BTREE_MAGIC;
 173         bt->sys_mdb = mdb->sys_mdb;
 174         bt->reserved = 0;
 175         bt->lock = 0;
 176         hfs_init_waitqueue(&bt->wait);
 177         bt->dirt = 0;
 178         memset(bt->cache, 0, sizeof(bt->cache));
 179
 180 #if 0   /* this is a fake entry. so we don't need to initialize it. */
 181         memset(&bt->entry, 0, sizeof(bt->entry));
 182         hfs_init_waitqueue(&bt->entry.wait);
 183         INIT_LIST_HEAD(&bt->entry.hash);
 184         INIT_LIST_HEAD(&bt->entry.list);
 185 #endif
 186
 187         bt->entry.mdb = mdb;
 188         bt->entry.cnid = cnid;
 189         bt->entry.type = HFS_CDR_FIL;
 190         bt->entry.u.file.magic = HFS_FILE_MAGIC;
 191         bt->entry.u.file.clumpablks = (csize / mdb->alloc_blksz)
 192                                                 >> HFS_SECTOR_SIZE_BITS;
 193         bt->entry.u.file.data_fork.entry = &bt->entry;
 194         bt->entry.u.file.data_fork.lsize = tsize;
 195         bt->entry.u.file.data_fork.psize = tsize >> HFS_SECTOR_SIZE_BITS;
 196         bt->entry.u.file.data_fork.fork = HFS_FK_DATA;
 197         hfs_extent_in(&bt->entry.u.file.data_fork, ext);
 198
 199         hfs_bnode_read(&bt->head, bt, 0, HFS_STICKY);
 200         if (!hfs_buffer_ok(bt->head.buf)) {
 201                 goto bail2;
 202         }
 203         th = (struct BTHdrRec *)((char *)hfs_buffer_data(bt->head.buf) +
 204                                                 sizeof(struct NodeDescriptor));
 205
 206         /* read in the bitmap nodes (if any) */
 207         tmp = &bt->head;
 208         while ((next = tmp->ndFLink)) {
 209                 if (!HFS_NEW(tmp->next)) {
 210                         goto bail2;
 211                 }
 212                 hfs_bnode_read(tmp->next, bt, next, HFS_STICKY);
 213                 if (!hfs_buffer_ok(tmp->next->buf)) {
 214                         goto bail2;
 215                 }
 216                 tmp->next->prev = tmp;
 217                 tmp = tmp->next;
 218         }
 219
 220         if (hfs_get_ns(th->bthNodeSize) != htons(HFS_SECTOR_SIZE)) {
 221                 hfs_warn("hfs_btree_init: bthNodeSize!=512 not supported\n");
 222                 goto bail2;
 223         }
 224
 225         if (cnid == htonl(HFS_CAT_CNID)) {
 226                 bt->compare = (hfs_cmpfn)hfs_cat_compare;
 227         } else if (cnid == htonl(HFS_EXT_CNID)) {
 228                 bt->compare = (hfs_cmpfn)hfs_ext_compare;
 229         } else {
 230                 goto bail2;
 231         }
 232         bt->bthDepth  = hfs_get_hs(th->bthDepth);
 233         bt->bthRoot   = hfs_get_hl(th->bthRoot);
 234         bt->bthNRecs  = hfs_get_hl(th->bthNRecs);
 235         bt->bthFNode  = hfs_get_hl(th->bthFNode);
 236         bt->bthLNode  = hfs_get_hl(th->bthLNode);
 237         bt->bthNNodes = hfs_get_hl(th->bthNNodes);
 238         bt->bthFree   = hfs_get_hl(th->bthFree);
 239         bt->bthKeyLen = hfs_get_hs(th->bthKeyLen);
 240
 241 #if defined(DEBUG_HEADER) || defined(DEBUG_ALL)
 242         hfs_warn("bthDepth %d\n", bt->bthDepth);
 243         hfs_warn("bthRoot %d\n", bt->bthRoot);
 244         hfs_warn("bthNRecs %d\n", bt->bthNRecs);
 245         hfs_warn("bthFNode %d\n", bt->bthFNode);
 246         hfs_warn("bthLNode %d\n", bt->bthLNode);
 247         hfs_warn("bthKeyLen %d\n", bt->bthKeyLen);
 248         hfs_warn("bthNNodes %d\n", bt->bthNNodes);
 249         hfs_warn("bthFree %d\n", bt->bthFree);
 250         p = (unsigned char *)hfs_buffer_data(bt->head.buf);
 251         q = p + HFS_SECTOR_SIZE;
 252         while (p < q) {
 253                 hfs_warn("%02x %02x %02x %02x %02x %02x %02x %02x "
 254                          "%02x %02x %02x %02x %02x %02x %02x %02x\n",
 255                          *p++, *p++, *p++, *p++, *p++, *p++, *p++, *p++,
 256                          *p++, *p++, *p++, *p++, *p++, *p++, *p++, *p++);
 257         }
 258 #endif
 259
 260         /* Read in the root if it exists.
 261            The header always exists, but the root exists only if the
 262            tree is non-empty */
 263         if (bt->bthDepth && bt->bthRoot) {
 264                 if (!HFS_NEW(bt->root)) {
 265                         goto bail2;
 266                 }
 267                 hfs_bnode_read(bt->root, bt, bt->bthRoot, HFS_STICKY);
 268                 if (!hfs_buffer_ok(bt->root->buf)) {
 269                         goto bail1;
 270                 }
 271         } else {
 272                 bt->root = NULL;
 273         }
 274
 275         return bt;
 276
 277  bail1:
 278         hfs_bnode_ditch(bt->root);
 279  bail2:
 280         hfs_bnode_ditch(&bt->head);
 281         HFS_DELETE(bt);
 282  bail3:
 283         return NULL;
 284 }
 285
 286 /*
 287  * hfs_btree_commit()
 288  *
 289  * Called to write a possibly dirty btree back to disk.
 290  */
 291 void hfs_btree_commit(struct hfs_btree *bt, hfs_byte_t ext[12], hfs_lword_t size)
 292 {
 293         if (bt->dirt) {
 294                 struct BTHdrRec *th;
 295                 th = (struct BTHdrRec *)((char *)hfs_buffer_data(bt->head.buf) +
 296                                                  sizeof(struct NodeDescriptor));
 297
 298                 hfs_put_hs(bt->bthDepth,  th->bthDepth);
 299                 hfs_put_hl(bt->bthRoot,   th->bthRoot);
 300                 hfs_put_hl(bt->bthNRecs,  th->bthNRecs);
 301                 hfs_put_hl(bt->bthFNode,  th->bthFNode);
 302                 hfs_put_hl(bt->bthLNode,  th->bthLNode);
 303                 hfs_put_hl(bt->bthNNodes, th->bthNNodes);
 304                 hfs_put_hl(bt->bthFree,   th->bthFree);
 305                 hfs_buffer_dirty(bt->head.buf);
 306
 307                 /*
 308                  * Commit the bnodes which are not cached.
 309                  * The map nodes don't need to be committed here because
 310                  * they are committed every time they are changed.
 311                  */
 312                 hfs_bnode_commit(&bt->head);
 313                 if (bt->root) {
 314                         hfs_bnode_commit(bt->root);
 315                 }
 316
 317
 318                 hfs_put_hl(bt->bthNNodes << HFS_SECTOR_SIZE_BITS, size);
 319                 hfs_extent_out(&bt->entry.u.file.data_fork, ext);
 320                 /* hfs_buffer_dirty(mdb->buf); (Done by caller) */
 321
 322                 bt->dirt = 0;
 323         }
 324 }