linux/fs/hfsplus/btree.c
<<
>>
Prefs
   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 <linux/log2.h>
  14
  15#include "hfsplus_fs.h"
  16#include "hfsplus_raw.h"
  17
  18
  19/* Get a reference to a B*Tree and do some initial checks */
  20struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
  21{
  22        struct hfs_btree *tree;
  23        struct hfs_btree_header_rec *head;
  24        struct address_space *mapping;
  25        struct inode *inode;
  26        struct page *page;
  27        unsigned int size;
  28
  29        tree = kzalloc(sizeof(*tree), GFP_KERNEL);
  30        if (!tree)
  31                return NULL;
  32
  33        mutex_init(&tree->tree_lock);
  34        spin_lock_init(&tree->hash_lock);
  35        tree->sb = sb;
  36        tree->cnid = id;
  37        inode = hfsplus_iget(sb, id);
  38        if (IS_ERR(inode))
  39                goto free_tree;
  40        tree->inode = inode;
  41
  42        if (!HFSPLUS_I(tree->inode)->first_blocks) {
  43                pr_err("invalid btree extent records (0 size)\n");
  44                goto free_inode;
  45        }
  46
  47        mapping = tree->inode->i_mapping;
  48        page = read_mapping_page(mapping, 0, NULL);
  49        if (IS_ERR(page))
  50                goto free_inode;
  51
  52        /* Load the header */
  53        head = (struct hfs_btree_header_rec *)(kmap(page) +
  54                sizeof(struct hfs_bnode_desc));
  55        tree->root = be32_to_cpu(head->root);
  56        tree->leaf_count = be32_to_cpu(head->leaf_count);
  57        tree->leaf_head = be32_to_cpu(head->leaf_head);
  58        tree->leaf_tail = be32_to_cpu(head->leaf_tail);
  59        tree->node_count = be32_to_cpu(head->node_count);
  60        tree->free_nodes = be32_to_cpu(head->free_nodes);
  61        tree->attributes = be32_to_cpu(head->attributes);
  62        tree->node_size = be16_to_cpu(head->node_size);
  63        tree->max_key_len = be16_to_cpu(head->max_key_len);
  64        tree->depth = be16_to_cpu(head->depth);
  65
  66        /* Verify the tree and set the correct compare function */
  67        switch (id) {
  68        case HFSPLUS_EXT_CNID:
  69                if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) {
  70                        pr_err("invalid extent max_key_len %d\n",
  71                                tree->max_key_len);
  72                        goto fail_page;
  73                }
  74                if (tree->attributes & HFS_TREE_VARIDXKEYS) {
  75                        pr_err("invalid extent btree flag\n");
  76                        goto fail_page;
  77                }
  78
  79                tree->keycmp = hfsplus_ext_cmp_key;
  80                break;
  81        case HFSPLUS_CAT_CNID:
  82                if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) {
  83                        pr_err("invalid catalog max_key_len %d\n",
  84                                tree->max_key_len);
  85                        goto fail_page;
  86                }
  87                if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) {
  88                        pr_err("invalid catalog btree flag\n");
  89                        goto fail_page;
  90                }
  91
  92                if (test_bit(HFSPLUS_SB_HFSX, &HFSPLUS_SB(sb)->flags) &&
  93                    (head->key_type == HFSPLUS_KEY_BINARY))
  94                        tree->keycmp = hfsplus_cat_bin_cmp_key;
  95                else {
  96                        tree->keycmp = hfsplus_cat_case_cmp_key;
  97                        set_bit(HFSPLUS_SB_CASEFOLD, &HFSPLUS_SB(sb)->flags);
  98                }
  99                break;
 100        case HFSPLUS_ATTR_CNID:
 101                if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) {
 102                        pr_err("invalid attributes max_key_len %d\n",
 103                                tree->max_key_len);
 104                        goto fail_page;
 105                }
 106                tree->keycmp = hfsplus_attr_bin_cmp_key;
 107                break;
 108        default:
 109                pr_err("unknown B*Tree requested\n");
 110                goto fail_page;
 111        }
 112
 113        if (!(tree->attributes & HFS_TREE_BIGKEYS)) {
 114                pr_err("invalid btree flag\n");
 115                goto fail_page;
 116        }
 117
 118        size = tree->node_size;
 119        if (!is_power_of_2(size))
 120                goto fail_page;
 121        if (!tree->node_count)
 122                goto fail_page;
 123
 124        tree->node_size_shift = ffs(size) - 1;
 125
 126        tree->pages_per_bnode =
 127                (tree->node_size + PAGE_CACHE_SIZE - 1) >>
 128                PAGE_CACHE_SHIFT;
 129
 130        kunmap(page);
 131        page_cache_release(page);
 132        return tree;
 133
 134 fail_page:
 135        page_cache_release(page);
 136 free_inode:
 137        tree->inode->i_mapping->a_ops = &hfsplus_aops;
 138        iput(tree->inode);
 139 free_tree:
 140        kfree(tree);
 141        return NULL;
 142}
 143
 144/* Release resources used by a btree */
 145void hfs_btree_close(struct hfs_btree *tree)
 146{
 147        struct hfs_bnode *node;
 148        int i;
 149
 150        if (!tree)
 151                return;
 152
 153        for (i = 0; i < NODE_HASH_SIZE; i++) {
 154                while ((node = tree->node_hash[i])) {
 155                        tree->node_hash[i] = node->next_hash;
 156                        if (atomic_read(&node->refcnt))
 157                                pr_crit("node %d:%d "
 158                                                "still has %d user(s)!\n",
 159                                        node->tree->cnid, node->this,
 160                                        atomic_read(&node->refcnt));
 161                        hfs_bnode_free(node);
 162                        tree->node_hash_cnt--;
 163                }
 164        }
 165        iput(tree->inode);
 166        kfree(tree);
 167}
 168
 169int hfs_btree_write(struct hfs_btree *tree)
 170{
 171        struct hfs_btree_header_rec *head;
 172        struct hfs_bnode *node;
 173        struct page *page;
 174
 175        node = hfs_bnode_find(tree, 0);
 176        if (IS_ERR(node))
 177                /* panic? */
 178                return -EIO;
 179        /* Load the header */
 180        page = node->page[0];
 181        head = (struct hfs_btree_header_rec *)(kmap(page) +
 182                sizeof(struct hfs_bnode_desc));
 183
 184        head->root = cpu_to_be32(tree->root);
 185        head->leaf_count = cpu_to_be32(tree->leaf_count);
 186        head->leaf_head = cpu_to_be32(tree->leaf_head);
 187        head->leaf_tail = cpu_to_be32(tree->leaf_tail);
 188        head->node_count = cpu_to_be32(tree->node_count);
 189        head->free_nodes = cpu_to_be32(tree->free_nodes);
 190        head->attributes = cpu_to_be32(tree->attributes);
 191        head->depth = cpu_to_be16(tree->depth);
 192
 193        kunmap(page);
 194        set_page_dirty(page);
 195        hfs_bnode_put(node);
 196        return 0;
 197}
 198
 199static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
 200{
 201        struct hfs_btree *tree = prev->tree;
 202        struct hfs_bnode *node;
 203        struct hfs_bnode_desc desc;
 204        __be32 cnid;
 205
 206        node = hfs_bnode_create(tree, idx);
 207        if (IS_ERR(node))
 208                return node;
 209
 210        tree->free_nodes--;
 211        prev->next = idx;
 212        cnid = cpu_to_be32(idx);
 213        hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
 214
 215        node->type = HFS_NODE_MAP;
 216        node->num_recs = 1;
 217        hfs_bnode_clear(node, 0, tree->node_size);
 218        desc.next = 0;
 219        desc.prev = 0;
 220        desc.type = HFS_NODE_MAP;
 221        desc.height = 0;
 222        desc.num_recs = cpu_to_be16(1);
 223        desc.reserved = 0;
 224        hfs_bnode_write(node, &desc, 0, sizeof(desc));
 225        hfs_bnode_write_u16(node, 14, 0x8000);
 226        hfs_bnode_write_u16(node, tree->node_size - 2, 14);
 227        hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
 228
 229        return node;
 230}
 231
 232struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
 233{
 234        struct hfs_bnode *node, *next_node;
 235        struct page **pagep;
 236        u32 nidx, idx;
 237        unsigned off;
 238        u16 off16;
 239        u16 len;
 240        u8 *data, byte, m;
 241        int i;
 242
 243        while (!tree->free_nodes) {
 244                struct inode *inode = tree->inode;
 245                struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
 246                u32 count;
 247                int res;
 248
 249                res = hfsplus_file_extend(inode);
 250                if (res)
 251                        return ERR_PTR(res);
 252                hip->phys_size = inode->i_size =
 253                        (loff_t)hip->alloc_blocks <<
 254                                HFSPLUS_SB(tree->sb)->alloc_blksz_shift;
 255                hip->fs_blocks =
 256                        hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift;
 257                inode_set_bytes(inode, inode->i_size);
 258                count = inode->i_size >> tree->node_size_shift;
 259                tree->free_nodes = count - tree->node_count;
 260                tree->node_count = count;
 261        }
 262
 263        nidx = 0;
 264        node = hfs_bnode_find(tree, nidx);
 265        if (IS_ERR(node))
 266                return node;
 267        len = hfs_brec_lenoff(node, 2, &off16);
 268        off = off16;
 269
 270        off += node->page_offset;
 271        pagep = node->page + (off >> PAGE_CACHE_SHIFT);
 272        data = kmap(*pagep);
 273        off &= ~PAGE_CACHE_MASK;
 274        idx = 0;
 275
 276        for (;;) {
 277                while (len) {
 278                        byte = data[off];
 279                        if (byte != 0xff) {
 280                                for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
 281                                        if (!(byte & m)) {
 282                                                idx += i;
 283                                                data[off] |= m;
 284                                                set_page_dirty(*pagep);
 285                                                kunmap(*pagep);
 286                                                tree->free_nodes--;
 287                                                mark_inode_dirty(tree->inode);
 288                                                hfs_bnode_put(node);
 289                                                return hfs_bnode_create(tree,
 290                                                        idx);
 291                                        }
 292                                }
 293                        }
 294                        if (++off >= PAGE_CACHE_SIZE) {
 295                                kunmap(*pagep);
 296                                data = kmap(*++pagep);
 297                                off = 0;
 298                        }
 299                        idx += 8;
 300                        len--;
 301                }
 302                kunmap(*pagep);
 303                nidx = node->next;
 304                if (!nidx) {
 305                        hfs_dbg(BNODE_MOD, "create new bmap node\n");
 306                        next_node = hfs_bmap_new_bmap(node, idx);
 307                } else
 308                        next_node = hfs_bnode_find(tree, nidx);
 309                hfs_bnode_put(node);
 310                if (IS_ERR(next_node))
 311                        return next_node;
 312                node = next_node;
 313
 314                len = hfs_brec_lenoff(node, 0, &off16);
 315                off = off16;
 316                off += node->page_offset;
 317                pagep = node->page + (off >> PAGE_CACHE_SHIFT);
 318                data = kmap(*pagep);
 319                off &= ~PAGE_CACHE_MASK;
 320        }
 321}
 322
 323void hfs_bmap_free(struct hfs_bnode *node)
 324{
 325        struct hfs_btree *tree;
 326        struct page *page;
 327        u16 off, len;
 328        u32 nidx;
 329        u8 *data, byte, m;
 330
 331        hfs_dbg(BNODE_MOD, "btree_free_node: %u\n", node->this);
 332        BUG_ON(!node->this);
 333        tree = node->tree;
 334        nidx = node->this;
 335        node = hfs_bnode_find(tree, 0);
 336        if (IS_ERR(node))
 337                return;
 338        len = hfs_brec_lenoff(node, 2, &off);
 339        while (nidx >= len * 8) {
 340                u32 i;
 341
 342                nidx -= len * 8;
 343                i = node->next;
 344                hfs_bnode_put(node);
 345                if (!i) {
 346                        /* panic */;
 347                        pr_crit("unable to free bnode %u. "
 348                                        "bmap not found!\n",
 349                                node->this);
 350                        return;
 351                }
 352                node = hfs_bnode_find(tree, i);
 353                if (IS_ERR(node))
 354                        return;
 355                if (node->type != HFS_NODE_MAP) {
 356                        /* panic */;
 357                        pr_crit("invalid bmap found! "
 358                                        "(%u,%d)\n",
 359                                node->this, node->type);
 360                        hfs_bnode_put(node);
 361                        return;
 362                }
 363                len = hfs_brec_lenoff(node, 0, &off);
 364        }
 365        off += node->page_offset + nidx / 8;
 366        page = node->page[off >> PAGE_CACHE_SHIFT];
 367        data = kmap(page);
 368        off &= ~PAGE_CACHE_MASK;
 369        m = 1 << (~nidx & 7);
 370        byte = data[off];
 371        if (!(byte & m)) {
 372                pr_crit("trying to free free bnode "
 373                                "%u(%d)\n",
 374                        node->this, node->type);
 375                kunmap(page);
 376                hfs_bnode_put(node);
 377                return;
 378        }
 379        data[off] = byte & ~m;
 380        set_page_dirty(page);
 381        kunmap(page);
 382        hfs_bnode_put(node);
 383        tree->free_nodes++;
 384        mark_inode_dirty(tree->inode);
 385}
 386
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.