btree.c 8.6 KB

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