fs/hfs/btree.c

   1 /*
   2  *  linux/fs/hfs/btree.c
   3  *
   4  * Copyright (C) 2001
   5  * Brad Boyer (flar@allandria.com)
   6  * (C) 2003 Ardis Technologies <roman@ardistech.com>
   7  *
   8  * Handle opening/closing btree
   9  */
  10
  11 #include <linux/pagemap.h>
  12
  13 #include "btree.h"
  14
  15 /* Get a reference to a B*Tree and do some initial checks */
  16 struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id, btree_keycmp keycmp)
  17 {
  18         struct hfs_btree *tree;
  19         struct hfs_btree_header_rec *head;
  20         struct address_space *mapping;
  21         struct page *page;
  22         unsigned int size;
  23
  24         tree = kzalloc(sizeof(*tree), GFP_KERNEL);
  25         if (!tree)
  26                 return NULL;
  27
  28         init_MUTEX(&tree->tree_lock);
  29         spin_lock_init(&tree->hash_lock);
  30         /* Set the correct compare function */
  31         tree->sb = sb;
  32         tree->cnid = id;
  33         tree->keycmp = keycmp;
  34
  35         tree->inode = iget_locked(sb, id);
  36         if (!tree->inode)
  37                 goto free_tree;
  38         BUG_ON(!(tree->inode->i_state & I_NEW));
  39         {
  40         struct hfs_mdb *mdb = HFS_SB(sb)->mdb;
  41         HFS_I(tree->inode)->flags = 0;
  42         init_MUTEX(&HFS_I(tree->inode)->extents_lock);
  43         switch (id) {
  44         case HFS_EXT_CNID:
  45                 hfs_inode_read_fork(tree->inode, mdb->drXTExtRec, mdb->drXTFlSize,
  46                                     mdb->drXTFlSize, be32_to_cpu(mdb->drXTClpSiz));
  47                 tree->inode->i_mapping->a_ops = &hfs_btree_aops;
  48                 break;
  49         case HFS_CAT_CNID:
  50                 hfs_inode_read_fork(tree->inode, mdb->drCTExtRec, mdb->drCTFlSize,
  51                                     mdb->drCTFlSize, be32_to_cpu(mdb->drCTClpSiz));
  52                 tree->inode->i_mapping->a_ops = &hfs_btree_aops;
  53                 break;
  54         default:
  55                 BUG();
  56         }
  57         }
  58         unlock_new_inode(tree->inode);
  59
  60         mapping = tree->inode->i_mapping;
  61         page = read_mapping_page(mapping, 0, NULL);
  62         if (IS_ERR(page))
  63                 goto free_tree;
  64
  65         /* Load the header */
  66         head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
  67         tree->root = be32_to_cpu(head->root);
  68         tree->leaf_count = be32_to_cpu(head->leaf_count);
  69         tree->leaf_head = be32_to_cpu(head->leaf_head);
  70         tree->leaf_tail = be32_to_cpu(head->leaf_tail);
  71         tree->node_count = be32_to_cpu(head->node_count);
  72         tree->free_nodes = be32_to_cpu(head->free_nodes);
  73         tree->attributes = be32_to_cpu(head->attributes);
  74         tree->node_size = be16_to_cpu(head->node_size);
  75         tree->max_key_len = be16_to_cpu(head->max_key_len);
  76         tree->depth = be16_to_cpu(head->depth);
  77
  78         size = tree->node_size;
  79         if (!size || size & (size - 1))
  80                 goto fail_page;
  81         if (!tree->node_count)
  82                 goto fail_page;
  83         tree->node_size_shift = ffs(size) - 1;
  84         tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
  85
  86         kunmap(page);
  87         page_cache_release(page);
  88         return tree;
  89
  90  fail_page:
  91         tree->inode->i_mapping->a_ops = &hfs_aops;
  92         page_cache_release(page);
  93  free_tree:
  94         iput(tree->inode);
  95         kfree(tree);
  96         return NULL;
  97 }
  98
  99 /* Release resources used by a btree */
 100 void hfs_btree_close(struct hfs_btree *tree)
 101 {
 102         struct hfs_bnode *node;
 103         int i;
 104
 105         if (!tree)
 106                 return;
 107
 108         for (i = 0; i < NODE_HASH_SIZE; i++) {
 109                 while ((node = tree->node_hash[i])) {
 110                         tree->node_hash[i] = node->next_hash;
 111                         if (atomic_read(&node->refcnt))
 112                                 printk(KERN_ERR "hfs: node %d:%d still has %d user(s)!\n",
 113                                         node->tree->cnid, node->this, atomic_read(&node->refcnt));
 114                         hfs_bnode_free(node);
 115                         tree->node_hash_cnt--;
 116                 }
 117         }
 118         iput(tree->inode);
 119         kfree(tree);
 120 }
 121
 122 void hfs_btree_write(struct hfs_btree *tree)
 123 {
 124         struct hfs_btree_header_rec *head;
 125         struct hfs_bnode *node;
 126         struct page *page;
 127
 128         node = hfs_bnode_find(tree, 0);
 129         if (IS_ERR(node))
 130                 /* panic? */
 131                 return;
 132         /* Load the header */
 133         page = node->page[0];
 134         head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
 135
 136         head->root = cpu_to_be32(tree->root);
 137         head->leaf_count = cpu_to_be32(tree->leaf_count);
 138         head->leaf_head = cpu_to_be32(tree->leaf_head);
 139         head->leaf_tail = cpu_to_be32(tree->leaf_tail);
 140         head->node_count = cpu_to_be32(tree->node_count);
 141         head->free_nodes = cpu_to_be32(tree->free_nodes);
 142         head->attributes = cpu_to_be32(tree->attributes);
 143         head->depth = cpu_to_be16(tree->depth);
 144
 145         kunmap(page);
 146         set_page_dirty(page);
 147         hfs_bnode_put(node);
 148 }
 149
 150 static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
 151 {
 152         struct hfs_btree *tree = prev->tree;
 153         struct hfs_bnode *node;
 154         struct hfs_bnode_desc desc;
 155         __be32 cnid;
 156
 157         node = hfs_bnode_create(tree, idx);
 158         if (IS_ERR(node))
 159                 return node;
 160
 161         if (!tree->free_nodes)
 162                 panic("FIXME!!!");
 163         tree->free_nodes--;
 164         prev->next = idx;
 165         cnid = cpu_to_be32(idx);
 166         hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
 167
 168         node->type = HFS_NODE_MAP;
 169         node->num_recs = 1;
 170         hfs_bnode_clear(node, 0, tree->node_size);
 171         desc.next = 0;
 172         desc.prev = 0;
 173         desc.type = HFS_NODE_MAP;
 174         desc.height = 0;
 175         desc.num_recs = cpu_to_be16(1);
 176         desc.reserved = 0;
 177         hfs_bnode_write(node, &desc, 0, sizeof(desc));
 178         hfs_bnode_write_u16(node, 14, 0x8000);
 179         hfs_bnode_write_u16(node, tree->node_size - 2, 14);
 180         hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
 181
 182         return node;
 183 }
 184
 185 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
 186 {
 187         struct hfs_bnode *node, *next_node;
 188         struct page **pagep;
 189         u32 nidx, idx;
 190         u16 off, len;
 191         u8 *data, byte, m;
 192         int i;
 193
 194         while (!tree->free_nodes) {
 195                 struct inode *inode = tree->inode;
 196                 u32 count;
 197                 int res;
 198
 199                 res = hfs_extend_file(inode);
 200                 if (res)
 201                         return ERR_PTR(res);
 202                 HFS_I(inode)->phys_size = inode->i_size =
 203                                 (loff_t)HFS_I(inode)->alloc_blocks *
 204                                 HFS_SB(tree->sb)->alloc_blksz;
 205                 HFS_I(inode)->fs_blocks = inode->i_size >>
 206                                           tree->sb->s_blocksize_bits;
 207                 inode_set_bytes(inode, inode->i_size);
 208                 count = inode->i_size >> tree->node_size_shift;
 209                 tree->free_nodes = count - tree->node_count;
 210                 tree->node_count = count;
 211         }
 212
 213         nidx = 0;
 214         node = hfs_bnode_find(tree, nidx);
 215         if (IS_ERR(node))
 216                 return node;
 217         len = hfs_brec_lenoff(node, 2, &off);
 218
 219         off += node->page_offset;
 220         pagep = node->page + (off >> PAGE_CACHE_SHIFT);
 221         data = kmap(*pagep);
 222         off &= ~PAGE_CACHE_MASK;
 223         idx = 0;
 224
 225         for (;;) {
 226                 while (len) {
 227                         byte = data[off];
 228                         if (byte != 0xff) {
 229                                 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
 230                                         if (!(byte & m)) {
 231                                                 idx += i;
 232                                                 data[off] |= m;
 233                                                 set_page_dirty(*pagep);
 234                                                 kunmap(*pagep);
 235                                                 tree->free_nodes--;
 236                                                 mark_inode_dirty(tree->inode);
 237                                                 hfs_bnode_put(node);
 238                                                 return hfs_bnode_create(tree, idx);
 239                                         }
 240                                 }
 241                         }
 242                         if (++off >= PAGE_CACHE_SIZE) {
 243                                 kunmap(*pagep);
 244                                 data = kmap(*++pagep);
 245                                 off = 0;
 246                         }
 247                         idx += 8;
 248                         len--;
 249                 }
 250                 kunmap(*pagep);
 251                 nidx = node->next;
 252                 if (!nidx) {
 253                         printk(KERN_DEBUG "hfs: create new bmap node...\n");
 254                         next_node = hfs_bmap_new_bmap(node, idx);
 255                 } else
 256                         next_node = hfs_bnode_find(tree, nidx);
 257                 hfs_bnode_put(node);
 258                 if (IS_ERR(next_node))
 259                         return next_node;
 260                 node = next_node;
 261
 262                 len = hfs_brec_lenoff(node, 0, &off);
 263                 off += node->page_offset;
 264                 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
 265                 data = kmap(*pagep);
 266                 off &= ~PAGE_CACHE_MASK;
 267         }
 268 }
 269
 270 void hfs_bmap_free(struct hfs_bnode *node)
 271 {
 272         struct hfs_btree *tree;
 273         struct page *page;
 274         u16 off, len;
 275         u32 nidx;
 276         u8 *data, byte, m;
 277
 278         dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
 279         tree = node->tree;
 280         nidx = node->this;
 281         node = hfs_bnode_find(tree, 0);
 282         if (IS_ERR(node))
 283                 return;
 284         len = hfs_brec_lenoff(node, 2, &off);
 285         while (nidx >= len * 8) {
 286                 u32 i;
 287
 288                 nidx -= len * 8;
 289                 i = node->next;
 290                 hfs_bnode_put(node);
 291                 if (!i) {
 292                         /* panic */;
 293                         printk(KERN_CRIT "hfs: unable to free bnode %u. bmap not found!\n", node->this);
 294                         return;
 295                 }
 296                 node = hfs_bnode_find(tree, i);
 297                 if (IS_ERR(node))
 298                         return;
 299                 if (node->type != HFS_NODE_MAP) {
 300                         /* panic */;
 301                         printk(KERN_CRIT "hfs: invalid bmap found! (%u,%d)\n", node->this, node->type);
 302                         hfs_bnode_put(node);
 303                         return;
 304                 }
 305                 len = hfs_brec_lenoff(node, 0, &off);
 306         }
 307         off += node->page_offset + nidx / 8;
 308         page = node->page[off >> PAGE_CACHE_SHIFT];
 309         data = kmap(page);
 310         off &= ~PAGE_CACHE_MASK;
 311         m = 1 << (~nidx & 7);
 312         byte = data[off];
 313         if (!(byte & m)) {
 314                 printk(KERN_CRIT "hfs: trying to free free bnode %u(%d)\n", node->this, node->type);
 315                 kunmap(page);
 316                 hfs_bnode_put(node);
 317                 return;
 318         }
 319         data[off] = byte & ~m;
 320         set_page_dirty(page);
 321         kunmap(page);
 322         hfs_bnode_put(node);
 323         tree->free_nodes++;
 324         mark_inode_dirty(tree->inode);
 325 }