fs/hfsplus/btree.c

   1 /*
   2  *  linux/fs/hfsplus/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/slab.h>
  12 #include <linux/pagemap.h>
  13 #include <asm/div64.h>
  14
  15 #include "hfsplus_fs.h"
  16 #include "hfsplus_raw.h"
  17
  18 /* Release resources used by a btree */
  19 void hfsplus_close_btree(struct hfsplus_btree *tree)
  20 {
  21         hfsplus_bnode *node;
  22         int i;
  23
  24         if (!tree)
  25                 return;
  26
  27         for (i = 0; i < NODE_HASH_SIZE; i++) {
  28                 while ((node = tree->node_hash[i])) {
  29                         tree->node_hash[i] = node->next_hash;
  30                         if (atomic_read(&node->refcnt))
  31                                 printk("HFS+: node %d:%d still has %d user(s)!\n",
  32                                         node->tree->cnid, node->this, atomic_read(&node->refcnt));
  33                         hfsplus_bnode_free(node);
  34                         tree->node_hash_cnt--;
  35                 }
  36         }
  37         iput(tree->inode);
  38         kfree(tree);
  39 }
  40
  41 /* Fill in extra data in tree structure from header node */
  42 static void hfsplus_read_treeinfo(hfsplus_btree *tree, hfsplus_btree_head *hdr)
  43 {
  44         unsigned int shift, size;
  45
  46         if (!tree || !hdr)
  47                 return;
  48
  49         tree->root = be32_to_cpu(hdr->root);
  50         tree->leaf_count = be32_to_cpu(hdr->leaf_count);
  51         tree->leaf_head = be32_to_cpu(hdr->leaf_head);
  52         tree->leaf_tail = be32_to_cpu(hdr->leaf_tail);
  53         tree->node_count = be32_to_cpu(hdr->node_count);
  54         tree->free_nodes = be32_to_cpu(hdr->free_nodes);
  55         tree->attributes = be32_to_cpu(hdr->attributes);
  56         tree->node_size = be16_to_cpu(hdr->node_size);
  57         tree->max_key_len = be16_to_cpu(hdr->max_key_len);
  58         tree->depth = be16_to_cpu(hdr->depth);
  59
  60         size = tree->node_size;
  61         if (size & (size - 1))
  62                 /* panic */;
  63         for (shift = 0; size >>= 1; shift += 1)
  64                 ;
  65         tree->node_size_shift = shift;
  66
  67         tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
  68 }
  69
  70 static void hfsplus_write_treeinfo(hfsplus_btree *tree, hfsplus_btree_head *hdr)
  71 {
  72         hdr->root = cpu_to_be32(tree->root);
  73         hdr->leaf_count = cpu_to_be32(tree->leaf_count);
  74         hdr->leaf_head = cpu_to_be32(tree->leaf_head);
  75         hdr->leaf_tail = cpu_to_be32(tree->leaf_tail);
  76         hdr->node_count = cpu_to_be32(tree->node_count);
  77         hdr->free_nodes = cpu_to_be32(tree->free_nodes);
  78         hdr->attributes = cpu_to_be32(tree->attributes);
  79         hdr->depth = cpu_to_be16(tree->depth);
  80 }
  81
  82 /* Get a reference to a B*Tree and do some initial checks */
  83 hfsplus_btree *hfsplus_open_btree(struct super_block *sb, u32 id)
  84 {
  85         hfsplus_btree *tree;
  86         hfsplus_btree_head *head;
  87         struct address_space *mapping;
  88         struct page *page;
  89
  90         tree = kmalloc(sizeof(struct hfsplus_btree), GFP_KERNEL);
  91         if (!tree)
  92                 return NULL;
  93         memset(tree, 0, sizeof(struct hfsplus_btree));
  94
  95         init_MUTEX(&tree->tree_lock);
  96         spin_lock_init(&tree->hash_lock);
  97         /* Set the correct compare function */
  98         tree->sb = sb;
  99         tree->cnid = id;
 100         if (id == HFSPLUS_EXT_CNID) {
 101                 tree->keycmp = hfsplus_cmp_ext_key;
 102         } else if (id == HFSPLUS_CAT_CNID) {
 103                 tree->keycmp = hfsplus_cmp_cat_key;
 104         } else {
 105                 printk("HFS+-fs: unknown B*Tree requested\n");
 106                 goto free_tree;
 107         }
 108         tree->inode = iget(sb, id);
 109         if (!tree->inode)
 110                 goto free_tree;
 111
 112         mapping = tree->inode->i_mapping;
 113         page = grab_cache_page(mapping, 0);
 114         if (!page)
 115                 goto free_tree;
 116         if (!PageUptodate(page)) {
 117                 if (mapping->a_ops->readpage(NULL, page))
 118                         goto fail_page;
 119                 wait_on_page_locked(page);
 120                 if (!PageUptodate(page))
 121                         goto fail_page;
 122         } else
 123                 unlock_page(page);
 124
 125         /* Load the header */
 126         head = (hfsplus_btree_head *)(kmap(page) + sizeof(hfsplus_btree_node_desc));
 127         hfsplus_read_treeinfo(tree, head);
 128         kunmap(page);
 129         page_cache_release(page);
 130         return tree;
 131
 132  fail_page:
 133         page_cache_release(page);
 134  free_tree:
 135         iput(tree->inode);
 136         kfree(tree);
 137         return NULL;
 138 }
 139
 140 void hfsplus_write_btree(struct hfsplus_btree *tree)
 141 {
 142         hfsplus_btree_head *head;
 143         hfsplus_bnode *node;
 144         struct page *page;
 145
 146         node = hfsplus_find_bnode(tree, 0);
 147         if (!node)
 148                 /* panic? */
 149                 return;
 150         /* Load the header */
 151         page = node->page[0];
 152         head = (hfsplus_btree_head *)(kmap(page) + sizeof(hfsplus_btree_node_desc));
 153         hfsplus_write_treeinfo(tree, head);
 154         kunmap(page);
 155         set_page_dirty(page);
 156         hfsplus_put_bnode(node);
 157 }
 158
 159 hfsplus_bnode *hfsplus_btree_alloc_node(hfsplus_btree *tree)
 160 {
 161         hfsplus_bnode *node;
 162         struct page **pagep;
 163         u32 nidx;
 164         u16 idx, off, len;
 165         u8 *data, byte, m;
 166         int i;
 167
 168         while (!tree->free_nodes) {
 169                 loff_t size;
 170                 int res;
 171
 172                 res = hfsplus_extend_file(tree->inode);
 173                 if (res)
 174                         return ERR_PTR(res);
 175                 HFSPLUS_I(tree->inode).total_blocks = HFSPLUS_I(tree->inode).alloc_blocks;
 176                 size = HFSPLUS_I(tree->inode).total_blocks;
 177                 size <<= tree->sb->s_blocksize_bits;
 178                 tree->inode->i_size = size;
 179                 do_div(size, (u32)tree->node_size);
 180                 tree->free_nodes = (u32)size - tree->node_count;
 181                 tree->node_count = size;
 182         }
 183
 184         nidx = 0;
 185         node = hfsplus_find_bnode(tree, nidx);
 186         len = hfsplus_brec_lenoff(node, 2, &off);
 187
 188         off += node->page_offset;
 189         pagep = node->page + (off >> PAGE_CACHE_SHIFT);
 190         data = hfsplus_kmap(*pagep);
 191         off &= ~PAGE_CACHE_MASK;
 192         idx = 0;
 193
 194         for (;;) {
 195                 while (len) {
 196                         byte = data[off];
 197                         if (byte != 0xff) {
 198                                 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
 199                                         if (!(byte & m)) {
 200                                                 idx += i;
 201                                                 data[off] |= m;
 202                                                 set_page_dirty(*pagep);
 203                                                 hfsplus_kunmap(*pagep);
 204                                                 tree->free_nodes--;
 205                                                 mark_inode_dirty(tree->inode);
 206                                                 hfsplus_put_bnode(node);
 207                                                 return hfsplus_create_bnode(tree, idx);
 208                                         }
 209                                 }
 210                         }
 211                         if (++off >= PAGE_CACHE_SIZE) {
 212                                 hfsplus_kunmap(*pagep++);
 213                                 data = hfsplus_kmap(*pagep);
 214                                 off = 0;
 215                         }
 216                         idx += 8;
 217                         len--;
 218                 }
 219                 nidx = node->next;
 220                 hfsplus_put_bnode(node);
 221                 if (!nidx) {
 222                         printk("need new bmap node...\n");
 223                         hfsplus_kunmap(*pagep);
 224                         return ERR_PTR(-ENOSPC);
 225                 }
 226                 node = hfsplus_find_bnode(tree, nidx);
 227                 len = hfsplus_brec_lenoff(node, 0, &off);
 228
 229                 off += node->page_offset;
 230                 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
 231                 data = hfsplus_kmap(*pagep);
 232                 off &= ~PAGE_CACHE_MASK;
 233         }
 234 }
 235
 236 void hfsplus_btree_remove_node(hfsplus_bnode *node)
 237 {
 238         hfsplus_btree *tree;
 239         hfsplus_bnode *tmp;
 240         u32 cnid;
 241
 242         tree = node->tree;
 243         if (node->prev) {
 244                 tmp = hfsplus_find_bnode(tree, node->prev);
 245                 tmp->next = node->next;
 246                 cnid = cpu_to_be32(tmp->next);
 247                 hfsplus_bnode_writebytes(tmp, &cnid, offsetof(hfsplus_btree_node_desc, next), 4);
 248                 hfsplus_put_bnode(tmp);
 249         } else if (node->kind == HFSPLUS_NODE_LEAF)
 250                 tree->leaf_head = node->next;
 251
 252         if (node->next) {
 253                 tmp = hfsplus_find_bnode(tree, node->next);
 254                 tmp->prev = node->prev;
 255                 cnid = cpu_to_be32(tmp->prev);
 256                 hfsplus_bnode_writebytes(tmp, &cnid, offsetof(hfsplus_btree_node_desc, prev), 4);
 257                 hfsplus_put_bnode(tmp);
 258         } else if (node->kind == HFSPLUS_NODE_LEAF)
 259                 tree->leaf_tail = node->prev;
 260
 261         // move down?
 262         if (!node->prev && !node->next) {
 263                 printk("hfsplus_btree_del_level\n");
 264         }
 265         if (!node->parent) {
 266                 tree->root = 0;
 267                 tree->depth = 0;
 268         }
 269         set_bit(HFSPLUS_BNODE_DELETED, &node->flags);
 270 }
 271
 272 void hfsplus_btree_free_node(hfsplus_bnode *node)
 273 {
 274         hfsplus_btree *tree;
 275         struct page *page;
 276         u16 off, len;
 277         u32 nidx;
 278         u8 *data, byte, m;
 279
 280         dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
 281         tree = node->tree;
 282         nidx = node->this;
 283         node = hfsplus_find_bnode(tree, 0);
 284         len = hfsplus_brec_lenoff(node, 2, &off);
 285         while (nidx >= len * 8) {
 286                 u32 i;
 287
 288                 nidx -= len * 8;
 289                 i = node->next;
 290                 hfsplus_put_bnode(node);
 291                 if (!nidx)
 292                         /* panic */;
 293                 node = hfsplus_find_bnode(tree, nidx);
 294                 if (node->kind != HFSPLUS_NODE_MAP)
 295                         /* panic */;
 296                 len = hfsplus_brec_lenoff(node, 0, &off);
 297         }
 298         off += node->page_offset + nidx / 8;
 299         page = node->page[off >> PAGE_CACHE_SHIFT];
 300         data = hfsplus_kmap(page);
 301         off &= ~PAGE_CACHE_MASK;
 302         m = 1 << (~nidx & 7);
 303         byte = data[off];
 304         if (!(byte & m)) {
 305                 BUG();
 306                 /* panic */
 307                 hfsplus_kunmap(page);
 308                 hfsplus_put_bnode(node);
 309                 return;
 310         }
 311         data[off] = byte & ~m;
 312         set_page_dirty(page);
 313         hfsplus_kunmap(page);
 314         hfsplus_put_bnode(node);
 315         tree->free_nodes++;
 316         mark_inode_dirty(tree->inode);
 317 }