btree.c 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318
  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 "hfsplus_fs.h"
  13. #include "hfsplus_raw.h"
  14. /* Get a reference to a B*Tree and do some initial checks */
  15. struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
  16. {
  17. struct hfs_btree *tree;
  18. struct hfs_btree_header_rec *head;
  19. struct address_space *mapping;
  20. struct page *page;
  21. unsigned int size;
  22. tree = kzalloc(sizeof(*tree), GFP_KERNEL);
  23. if (!tree)
  24. return NULL;
  25. init_MUTEX(&tree->tree_lock);
  26. spin_lock_init(&tree->hash_lock);
  27. tree->sb = sb;
  28. tree->cnid = id;
  29. tree->inode = iget(sb, id);
  30. if (!tree->inode)
  31. goto free_tree;
  32. mapping = tree->inode->i_mapping;
  33. page = read_mapping_page(mapping, 0, NULL);
  34. if (IS_ERR(page))
  35. goto free_tree;
  36. /* Load the header */
  37. head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
  38. tree->root = be32_to_cpu(head->root);
  39. tree->leaf_count = be32_to_cpu(head->leaf_count);
  40. tree->leaf_head = be32_to_cpu(head->leaf_head);
  41. tree->leaf_tail = be32_to_cpu(head->leaf_tail);
  42. tree->node_count = be32_to_cpu(head->node_count);
  43. tree->free_nodes = be32_to_cpu(head->free_nodes);
  44. tree->attributes = be32_to_cpu(head->attributes);
  45. tree->node_size = be16_to_cpu(head->node_size);
  46. tree->max_key_len = be16_to_cpu(head->max_key_len);
  47. tree->depth = be16_to_cpu(head->depth);
  48. /* Set the correct compare function */
  49. if (id == HFSPLUS_EXT_CNID) {
  50. tree->keycmp = hfsplus_ext_cmp_key;
  51. } else if (id == HFSPLUS_CAT_CNID) {
  52. if ((HFSPLUS_SB(sb).flags & HFSPLUS_SB_HFSX) &&
  53. (head->key_type == HFSPLUS_KEY_BINARY))
  54. tree->keycmp = hfsplus_cat_bin_cmp_key;
  55. else
  56. tree->keycmp = hfsplus_cat_case_cmp_key;
  57. } else {
  58. printk(KERN_ERR "hfs: unknown B*Tree requested\n");
  59. goto fail_page;
  60. }
  61. size = tree->node_size;
  62. if (!size || size & (size - 1))
  63. goto fail_page;
  64. if (!tree->node_count)
  65. goto fail_page;
  66. tree->node_size_shift = ffs(size) - 1;
  67. tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
  68. kunmap(page);
  69. page_cache_release(page);
  70. return tree;
  71. fail_page:
  72. tree->inode->i_mapping->a_ops = &hfsplus_aops;
  73. page_cache_release(page);
  74. free_tree:
  75. iput(tree->inode);
  76. kfree(tree);
  77. return NULL;
  78. }
  79. /* Release resources used by a btree */
  80. void hfs_btree_close(struct hfs_btree *tree)
  81. {
  82. struct hfs_bnode *node;
  83. int i;
  84. if (!tree)
  85. return;
  86. for (i = 0; i < NODE_HASH_SIZE; i++) {
  87. while ((node = tree->node_hash[i])) {
  88. tree->node_hash[i] = node->next_hash;
  89. if (atomic_read(&node->refcnt))
  90. printk(KERN_CRIT "hfs: node %d:%d still has %d user(s)!\n",
  91. node->tree->cnid, node->this, atomic_read(&node->refcnt));
  92. hfs_bnode_free(node);
  93. tree->node_hash_cnt--;
  94. }
  95. }
  96. iput(tree->inode);
  97. kfree(tree);
  98. }
  99. void hfs_btree_write(struct hfs_btree *tree)
  100. {
  101. struct hfs_btree_header_rec *head;
  102. struct hfs_bnode *node;
  103. struct page *page;
  104. node = hfs_bnode_find(tree, 0);
  105. if (IS_ERR(node))
  106. /* panic? */
  107. return;
  108. /* Load the header */
  109. page = node->page[0];
  110. head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
  111. head->root = cpu_to_be32(tree->root);
  112. head->leaf_count = cpu_to_be32(tree->leaf_count);
  113. head->leaf_head = cpu_to_be32(tree->leaf_head);
  114. head->leaf_tail = cpu_to_be32(tree->leaf_tail);
  115. head->node_count = cpu_to_be32(tree->node_count);
  116. head->free_nodes = cpu_to_be32(tree->free_nodes);
  117. head->attributes = cpu_to_be32(tree->attributes);
  118. head->depth = cpu_to_be16(tree->depth);
  119. kunmap(page);
  120. set_page_dirty(page);
  121. hfs_bnode_put(node);
  122. }
  123. static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
  124. {
  125. struct hfs_btree *tree = prev->tree;
  126. struct hfs_bnode *node;
  127. struct hfs_bnode_desc desc;
  128. __be32 cnid;
  129. node = hfs_bnode_create(tree, idx);
  130. if (IS_ERR(node))
  131. return node;
  132. tree->free_nodes--;
  133. prev->next = idx;
  134. cnid = cpu_to_be32(idx);
  135. hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
  136. node->type = HFS_NODE_MAP;
  137. node->num_recs = 1;
  138. hfs_bnode_clear(node, 0, tree->node_size);
  139. desc.next = 0;
  140. desc.prev = 0;
  141. desc.type = HFS_NODE_MAP;
  142. desc.height = 0;
  143. desc.num_recs = cpu_to_be16(1);
  144. desc.reserved = 0;
  145. hfs_bnode_write(node, &desc, 0, sizeof(desc));
  146. hfs_bnode_write_u16(node, 14, 0x8000);
  147. hfs_bnode_write_u16(node, tree->node_size - 2, 14);
  148. hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
  149. return node;
  150. }
  151. struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
  152. {
  153. struct hfs_bnode *node, *next_node;
  154. struct page **pagep;
  155. u32 nidx, idx;
  156. u16 off, len;
  157. u8 *data, byte, m;
  158. int i;
  159. while (!tree->free_nodes) {
  160. struct inode *inode = tree->inode;
  161. u32 count;
  162. int res;
  163. res = hfsplus_file_extend(inode);
  164. if (res)
  165. return ERR_PTR(res);
  166. HFSPLUS_I(inode).phys_size = inode->i_size =
  167. (loff_t)HFSPLUS_I(inode).alloc_blocks <<
  168. HFSPLUS_SB(tree->sb).alloc_blksz_shift;
  169. HFSPLUS_I(inode).fs_blocks = HFSPLUS_I(inode).alloc_blocks <<
  170. HFSPLUS_SB(tree->sb).fs_shift;
  171. inode_set_bytes(inode, inode->i_size);
  172. count = inode->i_size >> tree->node_size_shift;
  173. tree->free_nodes = count - tree->node_count;
  174. tree->node_count = count;
  175. }
  176. nidx = 0;
  177. node = hfs_bnode_find(tree, nidx);
  178. if (IS_ERR(node))
  179. return node;
  180. len = hfs_brec_lenoff(node, 2, &off);
  181. off += node->page_offset;
  182. pagep = node->page + (off >> PAGE_CACHE_SHIFT);
  183. data = kmap(*pagep);
  184. off &= ~PAGE_CACHE_MASK;
  185. idx = 0;
  186. for (;;) {
  187. while (len) {
  188. byte = data[off];
  189. if (byte != 0xff) {
  190. for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
  191. if (!(byte & m)) {
  192. idx += i;
  193. data[off] |= m;
  194. set_page_dirty(*pagep);
  195. kunmap(*pagep);
  196. tree->free_nodes--;
  197. mark_inode_dirty(tree->inode);
  198. hfs_bnode_put(node);
  199. return hfs_bnode_create(tree, idx);
  200. }
  201. }
  202. }
  203. if (++off >= PAGE_CACHE_SIZE) {
  204. kunmap(*pagep);
  205. data = kmap(*++pagep);
  206. off = 0;
  207. }
  208. idx += 8;
  209. len--;
  210. }
  211. kunmap(*pagep);
  212. nidx = node->next;
  213. if (!nidx) {
  214. printk(KERN_DEBUG "hfs: create new bmap node...\n");
  215. next_node = hfs_bmap_new_bmap(node, idx);
  216. } else
  217. next_node = hfs_bnode_find(tree, nidx);
  218. hfs_bnode_put(node);
  219. if (IS_ERR(next_node))
  220. return next_node;
  221. node = next_node;
  222. len = hfs_brec_lenoff(node, 0, &off);
  223. off += node->page_offset;
  224. pagep = node->page + (off >> PAGE_CACHE_SHIFT);
  225. data = kmap(*pagep);
  226. off &= ~PAGE_CACHE_MASK;
  227. }
  228. }
  229. void hfs_bmap_free(struct hfs_bnode *node)
  230. {
  231. struct hfs_btree *tree;
  232. struct page *page;
  233. u16 off, len;
  234. u32 nidx;
  235. u8 *data, byte, m;
  236. dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
  237. BUG_ON(!node->this);
  238. tree = node->tree;
  239. nidx = node->this;
  240. node = hfs_bnode_find(tree, 0);
  241. if (IS_ERR(node))
  242. return;
  243. len = hfs_brec_lenoff(node, 2, &off);
  244. while (nidx >= len * 8) {
  245. u32 i;
  246. nidx -= len * 8;
  247. i = node->next;
  248. hfs_bnode_put(node);
  249. if (!i) {
  250. /* panic */;
  251. printk(KERN_CRIT "hfs: unable to free bnode %u. bmap not found!\n", node->this);
  252. return;
  253. }
  254. node = hfs_bnode_find(tree, i);
  255. if (IS_ERR(node))
  256. return;
  257. if (node->type != HFS_NODE_MAP) {
  258. /* panic */;
  259. printk(KERN_CRIT "hfs: invalid bmap found! (%u,%d)\n", node->this, node->type);
  260. hfs_bnode_put(node);
  261. return;
  262. }
  263. len = hfs_brec_lenoff(node, 0, &off);
  264. }
  265. off += node->page_offset + nidx / 8;
  266. page = node->page[off >> PAGE_CACHE_SHIFT];
  267. data = kmap(page);
  268. off &= ~PAGE_CACHE_MASK;
  269. m = 1 << (~nidx & 7);
  270. byte = data[off];
  271. if (!(byte & m)) {
  272. printk(KERN_CRIT "hfs: trying to free free bnode %u(%d)\n", node->this, node->type);
  273. kunmap(page);
  274. hfs_bnode_put(node);
  275. return;
  276. }
  277. data[off] = byte & ~m;
  278. set_page_dirty(page);
  279. kunmap(page);
  280. hfs_bnode_put(node);
  281. tree->free_nodes++;
  282. mark_inode_dirty(tree->inode);
  283. }