btree.c 8.9 KB

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