btree.c 7.9 KB

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