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 = kmalloc(sizeof(*tree), GFP_KERNEL);
  25         if (!tree)
  26                 return NULL;
  27         memset(tree, 0, sizeof(*tree));
  28
  29         init_MUTEX(&tree->tree_lock);
  30         spin_lock_init(&tree->hash_lock);
  31         /* Set the correct compare function */
  32         tree->sb = sb;
  33         tree->cnid = id;
  34         tree->keycmp = keycmp;
  35
  36         tree->inode = iget_locked(sb, id);
  37         if (!tree->inode)
  38                 goto free_tree;
  39         if (!(tree->inode->i_state & I_NEW))
  40                 BUG();
  41         {
  42         struct hfs_mdb *mdb = HFS_SB(sb)->mdb;
  43         HFS_I(tree->inode)->flags = 0;
  44         init_MUTEX(&HFS_I(tree->inode)->extents_lock);
  45         switch (id) {
  46         case HFS_EXT_CNID:
  47                 hfs_inode_read_fork(tree->inode, mdb->drXTExtRec, mdb->drXTFlSize,
  48                                     mdb->drXTFlSize, be32_to_cpu(mdb->drXTClpSiz));
  49                 tree->inode->i_mapping->a_ops = &hfs_btree_aops;
  50                 break;
  51         case HFS_CAT_CNID:
  52                 hfs_inode_read_fork(tree->inode, mdb->drCTExtRec, mdb->drCTFlSize,
  53                                     mdb->drCTFlSize, be32_to_cpu(mdb->drCTClpSiz));
  54                 tree->inode->i_mapping->a_ops = &hfs_btree_aops;
  55                 break;
  56         default:
  57                 BUG();
  58         }
  59         }
  60         unlock_new_inode(tree->inode);
  61
  62         mapping = tree->inode->i_mapping;
  63         page = read_cache_page(mapping, 0, (filler_t *)mapping->a_ops->readpage, NULL);
  64         if (IS_ERR(page))
  65                 goto free_tree;
  66
  67         /* Load the header */
  68         head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
  69         tree->root = be32_to_cpu(head->root);
  70         tree->leaf_count = be32_to_cpu(head->leaf_count);
  71         tree->leaf_head = be32_to_cpu(head->leaf_head);
  72         tree->leaf_tail = be32_to_cpu(head->leaf_tail);
  73         tree->node_count = be32_to_cpu(head->node_count);
  74         tree->free_nodes = be32_to_cpu(head->free_nodes);
  75         tree->attributes = be32_to_cpu(head->attributes);
  76         tree->node_size = be16_to_cpu(head->node_size);
  77         tree->max_key_len = be16_to_cpu(head->max_key_len);
  78         tree->depth = be16_to_cpu(head->depth);
  79
  80         size = tree->node_size;
  81         if (!size || size & (size - 1))
  82                 goto fail_page;
  83         if (!tree->node_count)
  84                 goto fail_page;
  85         tree->node_size_shift = ffs(size) - 1;
  86         tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
  87
  88         kunmap(page);
  89         page_cache_release(page);
  90         return tree;
  91
  92  fail_page:
  93         tree->inode->i_mapping->a_ops = &hfs_aops;
  94         page_cache_release(page);
  95  free_tree:
  96         iput(tree->inode);
  97         kfree(tree);
  98         return NULL;
  99 }
 100
 101 /* Release resources used by a btree */
 102 void hfs_btree_close(struct hfs_btree *tree)
 103 {
 104         struct hfs_bnode *node;
 105         int i;
 106
 107         if (!tree)
 108                 return;
 109
 110         for (i = 0; i < NODE_HASH_SIZE; i++) {
 111                 while ((node = tree->node_hash[i])) {
 112                         tree->node_hash[i] = node->next_hash;
 113                         if (atomic_read(&node->refcnt))
 114                                 printk("HFS: node %d:%d still has %d user(s)!\n",
 115                                         node->tree->cnid, node->this, atomic_read(&node->refcnt));
 116                         hfs_bnode_free(node);
 117                         tree->node_hash_cnt--;
 118                 }
 119         }
 120         iput(tree->inode);
 121         kfree(tree);
 122 }
 123
 124 void hfs_btree_write(struct hfs_btree *tree)
 125 {
 126         struct hfs_btree_header_rec *head;
 127         struct hfs_bnode *node;
 128         struct page *page;
 129
 130         node = hfs_bnode_find(tree, 0);
 131         if (IS_ERR(node))
 132                 /* panic? */
 133                 return;
 134         /* Load the header */
 135         page = node->page[0];
 136         head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
 137
 138         head->root = cpu_to_be32(tree->root);
 139         head->leaf_count = cpu_to_be32(tree->leaf_count);
 140         head->leaf_head = cpu_to_be32(tree->leaf_head);
 141         head->leaf_tail = cpu_to_be32(tree->leaf_tail);
 142         head->node_count = cpu_to_be32(tree->node_count);
 143         head->free_nodes = cpu_to_be32(tree->free_nodes);
 144         head->attributes = cpu_to_be32(tree->attributes);
 145         head->depth = cpu_to_be16(tree->depth);
 146
 147         kunmap(page);
 148         set_page_dirty(page);
 149         hfs_bnode_put(node);
 150 }
 151
 152 static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
 153 {
 154         struct hfs_btree *tree = prev->tree;
 155         struct hfs_bnode *node;
 156         struct hfs_bnode_desc desc;
 157         __be32 cnid;
 158
 159         node = hfs_bnode_create(tree, idx);
 160         if (IS_ERR(node))
 161                 return node;
 162
 163         if (!tree->free_nodes)
 164                 panic("FIXME!!!");
 165         tree->free_nodes--;
 166         prev->next = idx;
 167         cnid = cpu_to_be32(idx);
 168         hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
 169
 170         node->type = HFS_NODE_MAP;
 171         node->num_recs = 1;
 172         hfs_bnode_clear(node, 0, tree->node_size);
 173         desc.next = 0;
 174         desc.prev = 0;
 175         desc.type = HFS_NODE_MAP;
 176         desc.height = 0;
 177         desc.num_recs = cpu_to_be16(1);
 178         desc.reserved = 0;
 179         hfs_bnode_write(node, &desc, 0, sizeof(desc));
 180         hfs_bnode_write_u16(node, 14, 0x8000);
 181         hfs_bnode_write_u16(node, tree->node_size - 2, 14);
 182         hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
 183
 184         return node;
 185 }
 186
 187 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
 188 {
 189         struct hfs_bnode *node, *next_node;
 190         struct page **pagep;
 191         u32 nidx, idx;
 192         u16 off, len;
 193         u8 *data, byte, m;
 194         int i;
 195
 196         while (!tree->free_nodes) {
 197                 struct inode *inode = tree->inode;
 198                 u32 count;
 199                 int res;
 200
 201                 res = hfs_extend_file(inode);
 202                 if (res)
 203                         return ERR_PTR(res);
 204                 inode->i_blocks = HFS_I(inode)->alloc_blocks *
 205                                   HFS_SB(tree->sb)->fs_div;
 206                 HFS_I(inode)->phys_size = inode->i_size =
 207                         (loff_t)inode->i_blocks << tree->sb->s_blocksize_bits;
 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("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("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("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("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 }