b24413180f560 (Greg Kroah-Hartman 2017-11-01 15:07:57 +0100 1) // SPDX-License-Identifier: GPL-2.0
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 2) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 3) * linux/fs/hfsplus/btree.c
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 4) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 5) * Copyright (C) 2001
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 6) * Brad Boyer (flar@allandria.com)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 7) * (C) 2003 Ardis Technologies <roman@ardistech.com>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 8) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 9) * Handle opening/closing btree
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 10) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 11)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 12) #include <linux/slab.h>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 13) #include <linux/pagemap.h>
e1b5c1d3da05c (Vignesh Babu BM 2007-05-08 00:24:30 -0700 14) #include <linux/log2.h>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 15)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 16) #include "hfsplus_fs.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 17) #include "hfsplus_raw.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 18)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 19) /*
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 20) * Initial source code of clump size calculation is gotten
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 21) * from http://opensource.apple.com/tarballs/diskdev_cmds/
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 22) */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 23) #define CLUMP_ENTRIES 15
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 24)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 25) static short clumptbl[CLUMP_ENTRIES * 3] = {
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 26) /*
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 27) * Volume Attributes Catalog Extents
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 28) * Size Clump (MB) Clump (MB) Clump (MB)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 29) */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 30) /* 1GB */ 4, 4, 4,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 31) /* 2GB */ 6, 6, 4,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 32) /* 4GB */ 8, 8, 4,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 33) /* 8GB */ 11, 11, 5,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 34) /*
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 35) * For volumes 16GB and larger, we want to make sure that a full OS
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 36) * install won't require fragmentation of the Catalog or Attributes
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 37) * B-trees. We do this by making the clump sizes sufficiently large,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 38) * and by leaving a gap after the B-trees for them to grow into.
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 39) *
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 40) * For SnowLeopard 10A298, a FullNetInstall with all packages selected
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 41) * results in:
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 42) * Catalog B-tree Header
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 43) * nodeSize: 8192
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 44) * totalNodes: 31616
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 45) * freeNodes: 1978
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 46) * (used = 231.55 MB)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 47) * Attributes B-tree Header
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 48) * nodeSize: 8192
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 49) * totalNodes: 63232
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 50) * freeNodes: 958
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 51) * (used = 486.52 MB)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 52) *
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 53) * We also want Time Machine backup volumes to have a sufficiently
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 54) * large clump size to reduce fragmentation.
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 55) *
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 56) * The series of numbers for Catalog and Attribute form a geometric
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 57) * series. For Catalog (16GB to 512GB), each term is 8**(1/5) times
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 58) * the previous term. For Attributes (16GB to 512GB), each term is
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 59) * 4**(1/5) times the previous term. For 1TB to 16TB, each term is
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 60) * 2**(1/5) times the previous term.
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 61) */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 62) /* 16GB */ 64, 32, 5,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 63) /* 32GB */ 84, 49, 6,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 64) /* 64GB */ 111, 74, 7,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 65) /* 128GB */ 147, 111, 8,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 66) /* 256GB */ 194, 169, 9,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 67) /* 512GB */ 256, 256, 11,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 68) /* 1TB */ 294, 294, 14,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 69) /* 2TB */ 338, 338, 16,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 70) /* 4TB */ 388, 388, 20,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 71) /* 8TB */ 446, 446, 25,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 72) /* 16TB */ 512, 512, 32
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 73) };
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 74)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 75) u32 hfsplus_calc_btree_clump_size(u32 block_size, u32 node_size,
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 76) u64 sectors, int file_id)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 77) {
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 78) u32 mod = max(node_size, block_size);
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 79) u32 clump_size;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 80) int column;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 81) int i;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 82)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 83) /* Figure out which column of the above table to use for this file. */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 84) switch (file_id) {
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 85) case HFSPLUS_ATTR_CNID:
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 86) column = 0;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 87) break;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 88) case HFSPLUS_CAT_CNID:
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 89) column = 1;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 90) break;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 91) default:
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 92) column = 2;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 93) break;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 94) }
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 95)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 96) /*
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 97) * The default clump size is 0.8% of the volume size. And
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 98) * it must also be a multiple of the node and block size.
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 99) */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 100) if (sectors < 0x200000) {
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 101) clump_size = sectors << 2; /* 0.8 % */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 102) if (clump_size < (8 * node_size))
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 103) clump_size = 8 * node_size;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 104) } else {
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 105) /* turn exponent into table index... */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 106) for (i = 0, sectors = sectors >> 22;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 107) sectors && (i < CLUMP_ENTRIES - 1);
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 108) ++i, sectors = sectors >> 1) {
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 109) /* empty body */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 110) }
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 111)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 112) clump_size = clumptbl[column + (i) * 3] * 1024 * 1024;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 113) }
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 114)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 115) /*
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 116) * Round the clump size to a multiple of node and block size.
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 117) * NOTE: This rounds down.
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 118) */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 119) clump_size /= mod;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 120) clump_size *= mod;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 121)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 122) /*
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 123) * Rounding down could have rounded down to 0 if the block size was
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 124) * greater than the clump size. If so, just use one block or node.
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 125) */
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 126) if (clump_size == 0)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 127) clump_size = mod;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 128)
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 129) return clump_size;
b3b5b0f03cc4e (Vyacheslav Dubeyko 2013-11-12 15:11:07 -0800 130) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 131)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 132) /* Get a reference to a B*Tree and do some initial checks */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 133) struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 134) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 135) struct hfs_btree *tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 136) struct hfs_btree_header_rec *head;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 137) struct address_space *mapping;
635253915b329 (David Howells 2008-02-07 00:15:40 -0800 138) struct inode *inode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 139) struct page *page;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 140) unsigned int size;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 141)
f8314dc60ccba (Panagiotis Issaris 2006-09-27 01:49:37 -0700 142) tree = kzalloc(sizeof(*tree), GFP_KERNEL);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 143) if (!tree)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 144) return NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 145)
467c3d9cd541e (Thomas Gleixner 2010-10-01 05:46:52 +0200 146) mutex_init(&tree->tree_lock);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 147) spin_lock_init(&tree->hash_lock);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 148) tree->sb = sb;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 149) tree->cnid = id;
635253915b329 (David Howells 2008-02-07 00:15:40 -0800 150) inode = hfsplus_iget(sb, id);
635253915b329 (David Howells 2008-02-07 00:15:40 -0800 151) if (IS_ERR(inode))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 152) goto free_tree;
635253915b329 (David Howells 2008-02-07 00:15:40 -0800 153) tree->inode = inode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 154)
ee52716245877 (Jeff Mahoney 2010-10-14 09:53:37 -0400 155) if (!HFSPLUS_I(tree->inode)->first_blocks) {
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 156) pr_err("invalid btree extent records (0 size)\n");
ee52716245877 (Jeff Mahoney 2010-10-14 09:53:37 -0400 157) goto free_inode;
ee52716245877 (Jeff Mahoney 2010-10-14 09:53:37 -0400 158) }
ee52716245877 (Jeff Mahoney 2010-10-14 09:53:37 -0400 159)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 160) mapping = tree->inode->i_mapping;
090d2b185d868 (Pekka Enberg 2006-06-23 02:05:08 -0700 161) page = read_mapping_page(mapping, 0, NULL);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 162) if (IS_ERR(page))
ee52716245877 (Jeff Mahoney 2010-10-14 09:53:37 -0400 163) goto free_inode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 164)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 165) /* Load the header */
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 166) head = (struct hfs_btree_header_rec *)(kmap(page) +
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 167) sizeof(struct hfs_bnode_desc));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 168) tree->root = be32_to_cpu(head->root);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 169) tree->leaf_count = be32_to_cpu(head->leaf_count);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 170) tree->leaf_head = be32_to_cpu(head->leaf_head);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 171) tree->leaf_tail = be32_to_cpu(head->leaf_tail);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 172) tree->node_count = be32_to_cpu(head->node_count);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 173) tree->free_nodes = be32_to_cpu(head->free_nodes);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 174) tree->attributes = be32_to_cpu(head->attributes);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 175) tree->node_size = be16_to_cpu(head->node_size);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 176) tree->max_key_len = be16_to_cpu(head->max_key_len);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 177) tree->depth = be16_to_cpu(head->depth);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 178)
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 179) /* Verify the tree and set the correct compare function */
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 180) switch (id) {
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 181) case HFSPLUS_EXT_CNID:
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 182) if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) {
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 183) pr_err("invalid extent max_key_len %d\n",
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 184) tree->max_key_len);
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 185) goto fail_page;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 186) }
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 187) if (tree->attributes & HFS_TREE_VARIDXKEYS) {
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 188) pr_err("invalid extent btree flag\n");
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 189) goto fail_page;
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 190) }
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 191)
2179d372d9f8b (David Elliott 2006-01-18 17:43:08 -0800 192) tree->keycmp = hfsplus_ext_cmp_key;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 193) break;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 194) case HFSPLUS_CAT_CNID:
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 195) if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) {
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 196) pr_err("invalid catalog max_key_len %d\n",
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 197) tree->max_key_len);
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 198) goto fail_page;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 199) }
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 200) if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) {
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 201) pr_err("invalid catalog btree flag\n");
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 202) goto fail_page;
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 203) }
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 204)
84adede31267a (Christoph Hellwig 2010-10-01 05:45:20 +0200 205) if (test_bit(HFSPLUS_SB_HFSX, &HFSPLUS_SB(sb)->flags) &&
2179d372d9f8b (David Elliott 2006-01-18 17:43:08 -0800 206) (head->key_type == HFSPLUS_KEY_BINARY))
2179d372d9f8b (David Elliott 2006-01-18 17:43:08 -0800 207) tree->keycmp = hfsplus_cat_bin_cmp_key;
d45bce8faf555 (Duane Griffin 2007-07-15 23:41:23 -0700 208) else {
2179d372d9f8b (David Elliott 2006-01-18 17:43:08 -0800 209) tree->keycmp = hfsplus_cat_case_cmp_key;
84adede31267a (Christoph Hellwig 2010-10-01 05:45:20 +0200 210) set_bit(HFSPLUS_SB_CASEFOLD, &HFSPLUS_SB(sb)->flags);
d45bce8faf555 (Duane Griffin 2007-07-15 23:41:23 -0700 211) }
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 212) break;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 213) case HFSPLUS_ATTR_CNID:
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 214) if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) {
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 215) pr_err("invalid attributes max_key_len %d\n",
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 216) tree->max_key_len);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 217) goto fail_page;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 218) }
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 219) tree->keycmp = hfsplus_attr_bin_cmp_key;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 220) break;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 221) default:
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 222) pr_err("unknown B*Tree requested\n");
2179d372d9f8b (David Elliott 2006-01-18 17:43:08 -0800 223) goto fail_page;
2179d372d9f8b (David Elliott 2006-01-18 17:43:08 -0800 224) }
2179d372d9f8b (David Elliott 2006-01-18 17:43:08 -0800 225)
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 226) if (!(tree->attributes & HFS_TREE_BIGKEYS)) {
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 227) pr_err("invalid btree flag\n");
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 228) goto fail_page;
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 229) }
13571a6977f82 (Christoph Hellwig 2010-10-14 09:54:23 -0400 230)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 231) size = tree->node_size;
e1b5c1d3da05c (Vignesh Babu BM 2007-05-08 00:24:30 -0700 232) if (!is_power_of_2(size))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 233) goto fail_page;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 234) if (!tree->node_count)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 235) goto fail_page;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 236)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 237) tree->node_size_shift = ffs(size) - 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 238)
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 239) tree->pages_per_bnode =
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 240) (tree->node_size + PAGE_SIZE - 1) >>
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 241) PAGE_SHIFT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 242)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 243) kunmap(page);
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 244) put_page(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 245) return tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 246)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 247) fail_page:
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 248) put_page(page);
ee52716245877 (Jeff Mahoney 2010-10-14 09:53:37 -0400 249) free_inode:
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 250) tree->inode->i_mapping->a_ops = &hfsplus_aops;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 251) iput(tree->inode);
ee52716245877 (Jeff Mahoney 2010-10-14 09:53:37 -0400 252) free_tree:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 253) kfree(tree);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 254) return NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 255) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 256)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 257) /* Release resources used by a btree */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 258) void hfs_btree_close(struct hfs_btree *tree)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 259) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 260) struct hfs_bnode *node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 261) int i;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 262)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 263) if (!tree)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 264) return;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 265)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 266) for (i = 0; i < NODE_HASH_SIZE; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 267) while ((node = tree->node_hash[i])) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 268) tree->node_hash[i] = node->next_hash;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 269) if (atomic_read(&node->refcnt))
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 270) pr_crit("node %d:%d "
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 271) "still has %d user(s)!\n",
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 272) node->tree->cnid, node->this,
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 273) atomic_read(&node->refcnt));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 274) hfs_bnode_free(node);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 275) tree->node_hash_cnt--;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 276) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 277) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 278) iput(tree->inode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 279) kfree(tree);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 280) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 281)
81cc7fad552bc (Vyacheslav Dubeyko 2012-12-20 15:05:28 -0800 282) int hfs_btree_write(struct hfs_btree *tree)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 283) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 284) struct hfs_btree_header_rec *head;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 285) struct hfs_bnode *node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 286) struct page *page;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 287)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 288) node = hfs_bnode_find(tree, 0);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 289) if (IS_ERR(node))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 290) /* panic? */
81cc7fad552bc (Vyacheslav Dubeyko 2012-12-20 15:05:28 -0800 291) return -EIO;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 292) /* Load the header */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 293) page = node->page[0];
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 294) head = (struct hfs_btree_header_rec *)(kmap(page) +
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 295) sizeof(struct hfs_bnode_desc));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 296)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 297) head->root = cpu_to_be32(tree->root);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 298) head->leaf_count = cpu_to_be32(tree->leaf_count);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 299) head->leaf_head = cpu_to_be32(tree->leaf_head);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 300) head->leaf_tail = cpu_to_be32(tree->leaf_tail);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 301) head->node_count = cpu_to_be32(tree->node_count);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 302) head->free_nodes = cpu_to_be32(tree->free_nodes);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 303) head->attributes = cpu_to_be32(tree->attributes);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 304) head->depth = cpu_to_be16(tree->depth);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 305)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 306) kunmap(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 307) set_page_dirty(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 308) hfs_bnode_put(node);
81cc7fad552bc (Vyacheslav Dubeyko 2012-12-20 15:05:28 -0800 309) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 310) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 311)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 312) static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 313) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 314) struct hfs_btree *tree = prev->tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 315) struct hfs_bnode *node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 316) struct hfs_bnode_desc desc;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 317) __be32 cnid;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 318)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 319) node = hfs_bnode_create(tree, idx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 320) if (IS_ERR(node))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 321) return node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 322)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 323) tree->free_nodes--;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 324) prev->next = idx;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 325) cnid = cpu_to_be32(idx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 326) hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 327)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 328) node->type = HFS_NODE_MAP;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 329) node->num_recs = 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 330) hfs_bnode_clear(node, 0, tree->node_size);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 331) desc.next = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 332) desc.prev = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 333) desc.type = HFS_NODE_MAP;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 334) desc.height = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 335) desc.num_recs = cpu_to_be16(1);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 336) desc.reserved = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 337) hfs_bnode_write(node, &desc, 0, sizeof(desc));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 338) hfs_bnode_write_u16(node, 14, 0x8000);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 339) hfs_bnode_write_u16(node, tree->node_size - 2, 14);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 340) hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 341)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 342) return node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 343) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 344)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 345) /* Make sure @tree has enough space for the @rsvd_nodes */
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 346) int hfs_bmap_reserve(struct hfs_btree *tree, int rsvd_nodes)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 347) {
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 348) struct inode *inode = tree->inode;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 349) struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 350) u32 count;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 351) int res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 352)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 353) if (rsvd_nodes <= 0)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 354) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 355)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 356) while (tree->free_nodes < rsvd_nodes) {
2cd282a1bc6b9 (Sergei Antonov 2014-06-06 14:36:28 -0700 357) res = hfsplus_file_extend(inode, hfs_bnode_need_zeroout(tree));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 358) if (res)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 359) return res;
6af502de224c3 (Christoph Hellwig 2010-10-01 05:43:31 +0200 360) hip->phys_size = inode->i_size =
6af502de224c3 (Christoph Hellwig 2010-10-01 05:43:31 +0200 361) (loff_t)hip->alloc_blocks <<
dd73a01a30d72 (Christoph Hellwig 2010-10-01 05:42:59 +0200 362) HFSPLUS_SB(tree->sb)->alloc_blksz_shift;
6af502de224c3 (Christoph Hellwig 2010-10-01 05:43:31 +0200 363) hip->fs_blocks =
6af502de224c3 (Christoph Hellwig 2010-10-01 05:43:31 +0200 364) hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 365) inode_set_bytes(inode, inode->i_size);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 366) count = inode->i_size >> tree->node_size_shift;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 367) tree->free_nodes += count - tree->node_count;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 368) tree->node_count = count;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 369) }
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 370) return 0;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 371) }
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 372)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 373) struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 374) {
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 375) struct hfs_bnode *node, *next_node;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 376) struct page **pagep;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 377) u32 nidx, idx;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 378) unsigned off;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 379) u16 off16;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 380) u16 len;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 381) u8 *data, byte, m;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 382) int i, res;
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 383)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 384) res = hfs_bmap_reserve(tree, 1);
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 385) if (res)
d92915c35bfaf (Ernesto A. Fernández 2018-10-30 15:06:14 -0700 386) return ERR_PTR(res);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 387)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 388) nidx = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 389) node = hfs_bnode_find(tree, nidx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 390) if (IS_ERR(node))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 391) return node;
487798df6d25e (Andrew Morton 2008-04-30 00:54:54 -0700 392) len = hfs_brec_lenoff(node, 2, &off16);
487798df6d25e (Andrew Morton 2008-04-30 00:54:54 -0700 393) off = off16;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 394)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 395) off += node->page_offset;
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 396) pagep = node->page + (off >> PAGE_SHIFT);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 397) data = kmap(*pagep);
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 398) off &= ~PAGE_MASK;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 399) idx = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 400)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 401) for (;;) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 402) while (len) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 403) byte = data[off];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 404) if (byte != 0xff) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 405) for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 406) if (!(byte & m)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 407) idx += i;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 408) data[off] |= m;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 409) set_page_dirty(*pagep);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 410) kunmap(*pagep);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 411) tree->free_nodes--;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 412) mark_inode_dirty(tree->inode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 413) hfs_bnode_put(node);
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 414) return hfs_bnode_create(tree,
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 415) idx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 416) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 417) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 418) }
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 419) if (++off >= PAGE_SIZE) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 420) kunmap(*pagep);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 421) data = kmap(*++pagep);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 422) off = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 423) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 424) idx += 8;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 425) len--;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 426) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 427) kunmap(*pagep);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 428) nidx = node->next;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 429) if (!nidx) {
c2b3e1f76e5c9 (Joe Perches 2013-04-30 15:27:54 -0700 430) hfs_dbg(BNODE_MOD, "create new bmap node\n");
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 431) next_node = hfs_bmap_new_bmap(node, idx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 432) } else
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 433) next_node = hfs_bnode_find(tree, nidx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 434) hfs_bnode_put(node);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 435) if (IS_ERR(next_node))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 436) return next_node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 437) node = next_node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 438)
487798df6d25e (Andrew Morton 2008-04-30 00:54:54 -0700 439) len = hfs_brec_lenoff(node, 0, &off16);
487798df6d25e (Andrew Morton 2008-04-30 00:54:54 -0700 440) off = off16;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 441) off += node->page_offset;
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 442) pagep = node->page + (off >> PAGE_SHIFT);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 443) data = kmap(*pagep);
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 444) off &= ~PAGE_MASK;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 445) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 446) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 447)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 448) void hfs_bmap_free(struct hfs_bnode *node)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 449) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 450) struct hfs_btree *tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 451) struct page *page;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 452) u16 off, len;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 453) u32 nidx;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 454) u8 *data, byte, m;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 455)
c2b3e1f76e5c9 (Joe Perches 2013-04-30 15:27:54 -0700 456) hfs_dbg(BNODE_MOD, "btree_free_node: %u\n", node->this);
0bf3ba538a150 (Eric Sesterhenn 2006-04-01 01:14:43 +0200 457) BUG_ON(!node->this);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 458) tree = node->tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 459) nidx = node->this;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 460) node = hfs_bnode_find(tree, 0);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 461) if (IS_ERR(node))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 462) return;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 463) len = hfs_brec_lenoff(node, 2, &off);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 464) while (nidx >= len * 8) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 465) u32 i;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 466)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 467) nidx -= len * 8;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 468) i = node->next;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 469) if (!i) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 470) /* panic */;
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 471) pr_crit("unable to free bnode %u. "
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 472) "bmap not found!\n",
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 473) node->this);
c7d7d620dcbd2 (Pan Bian 2018-11-30 14:09:18 -0800 474) hfs_bnode_put(node);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 475) return;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 476) }
c7d7d620dcbd2 (Pan Bian 2018-11-30 14:09:18 -0800 477) hfs_bnode_put(node);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 478) node = hfs_bnode_find(tree, i);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 479) if (IS_ERR(node))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 480) return;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 481) if (node->type != HFS_NODE_MAP) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 482) /* panic */;
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 483) pr_crit("invalid bmap found! "
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 484) "(%u,%d)\n",
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 485) node->this, node->type);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 486) hfs_bnode_put(node);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 487) return;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 488) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 489) len = hfs_brec_lenoff(node, 0, &off);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 490) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 491) off += node->page_offset + nidx / 8;
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 492) page = node->page[off >> PAGE_SHIFT];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 493) data = kmap(page);
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 494) off &= ~PAGE_MASK;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 495) m = 1 << (~nidx & 7);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 496) byte = data[off];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 497) if (!(byte & m)) {
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 498) pr_crit("trying to free free bnode "
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 499) "%u(%d)\n",
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 500) node->this, node->type);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 501) kunmap(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 502) hfs_bnode_put(node);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 503) return;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 504) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 505) data[off] = byte & ~m;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 506) set_page_dirty(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 507) kunmap(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 508) hfs_bnode_put(node);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 509) tree->free_nodes++;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 510) mark_inode_dirty(tree->inode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 511) }
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags