Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/fs/hfsplus/btree.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
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 11 #include <linux/slab.h> 12 #include <linux/pagemap.h> 13 #include <asm/div64.h> 14 15 #include "hfsplus_fs.h" 16 #include "hfsplus_raw.h" 17 18 /* Release resources used by a btree */ 19 void hfsplus_close_btree(struct hfsplus_btree *tree) 20 { 21 hfsplus_bnode *node; 22 int i; 23 24 if (!tree) 25 return; 26 27 for (i = 0; i < NODE_HASH_SIZE; i++) { 28 while ((node = tree->node_hash[i])) { 29 tree->node_hash[i] = node->next_hash; 30 if (atomic_read(&node->refcnt)) 31 printk("HFS+: node %d:%d still has %d user(s)!\n", 32 node->tree->cnid, node->this, atomic_read(&node->refcnt)); 33 hfsplus_bnode_free(node); 34 tree->node_hash_cnt--; 35 } 36 } 37 iput(tree->inode); 38 kfree(tree); 39 } 40 41 /* Fill in extra data in tree structure from header node */ 42 static void hfsplus_read_treeinfo(hfsplus_btree *tree, hfsplus_btree_head *hdr) 43 { 44 unsigned int shift, size; 45 46 if (!tree || !hdr) 47 return; 48 49 tree->root = be32_to_cpu(hdr->root); 50 tree->leaf_count = be32_to_cpu(hdr->leaf_count); 51 tree->leaf_head = be32_to_cpu(hdr->leaf_head); 52 tree->leaf_tail = be32_to_cpu(hdr->leaf_tail); 53 tree->node_count = be32_to_cpu(hdr->node_count); 54 tree->free_nodes = be32_to_cpu(hdr->free_nodes); 55 tree->attributes = be32_to_cpu(hdr->attributes); 56 tree->node_size = be16_to_cpu(hdr->node_size); 57 tree->max_key_len = be16_to_cpu(hdr->max_key_len); 58 tree->depth = be16_to_cpu(hdr->depth); 59 60 size = tree->node_size; 61 if (size & (size - 1)) 62 /* panic */; 63 for (shift = 0; size >>= 1; shift += 1) 64 ; 65 tree->node_size_shift = shift; 66 67 tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT; 68 } 69 70 static void hfsplus_write_treeinfo(hfsplus_btree *tree, hfsplus_btree_head *hdr) 71 { 72 hdr->root = cpu_to_be32(tree->root); 73 hdr->leaf_count = cpu_to_be32(tree->leaf_count); 74 hdr->leaf_head = cpu_to_be32(tree->leaf_head); 75 hdr->leaf_tail = cpu_to_be32(tree->leaf_tail); 76 hdr->node_count = cpu_to_be32(tree->node_count); 77 hdr->free_nodes = cpu_to_be32(tree->free_nodes); 78 hdr->attributes = cpu_to_be32(tree->attributes); 79 hdr->depth = cpu_to_be16(tree->depth); 80 } 81 82 /* Get a reference to a B*Tree and do some initial checks */ 83 hfsplus_btree *hfsplus_open_btree(struct super_block *sb, u32 id) 84 { 85 hfsplus_btree *tree; 86 hfsplus_btree_head *head; 87 struct address_space *mapping; 88 struct page *page; 89 90 tree = kmalloc(sizeof(struct hfsplus_btree), GFP_KERNEL); 91 if (!tree) 92 return NULL; 93 memset(tree, 0, sizeof(struct hfsplus_btree)); 94 95 init_MUTEX(&tree->tree_lock); 96 spin_lock_init(&tree->hash_lock); 97 /* Set the correct compare function */ 98 tree->sb = sb; 99 tree->cnid = id; 100 if (id == HFSPLUS_EXT_CNID) { 101 tree->keycmp = hfsplus_cmp_ext_key; 102 } else if (id == HFSPLUS_CAT_CNID) { 103 tree->keycmp = hfsplus_cmp_cat_key; 104 } else { 105 printk("HFS+-fs: unknown B*Tree requested\n"); 106 goto free_tree; 107 } 108 tree->inode = iget(sb, id); 109 if (!tree->inode) 110 goto free_tree; 111 112 mapping = tree->inode->i_mapping; 113 page = grab_cache_page(mapping, 0); 114 if (!page) 115 goto free_tree; 116 if (!PageUptodate(page)) { 117 if (mapping->a_ops->readpage(NULL, page)) 118 goto fail_page; 119 wait_on_page_locked(page); 120 if (!PageUptodate(page)) 121 goto fail_page; 122 } else 123 unlock_page(page); 124 125 /* Load the header */ 126 head = (hfsplus_btree_head *)(kmap(page) + sizeof(hfsplus_btree_node_desc)); 127 hfsplus_read_treeinfo(tree, head); 128 kunmap(page); 129 page_cache_release(page); 130 return tree; 131 132 fail_page: 133 page_cache_release(page); 134 free_tree: 135 iput(tree->inode); 136 kfree(tree); 137 return NULL; 138 } 139 140 void hfsplus_write_btree(struct hfsplus_btree *tree) 141 { 142 hfsplus_btree_head *head; 143 hfsplus_bnode *node; 144 struct page *page; 145 146 node = hfsplus_find_bnode(tree, 0); 147 if (!node) 148 /* panic? */ 149 return; 150 /* Load the header */ 151 page = node->page[0]; 152 head = (hfsplus_btree_head *)(kmap(page) + sizeof(hfsplus_btree_node_desc)); 153 hfsplus_write_treeinfo(tree, head); 154 kunmap(page); 155 set_page_dirty(page); 156 hfsplus_put_bnode(node); 157 } 158 159 hfsplus_bnode *hfsplus_btree_alloc_node(hfsplus_btree *tree) 160 { 161 hfsplus_bnode *node; 162 struct page **pagep; 163 u32 nidx; 164 u16 idx, off, len; 165 u8 *data, byte, m; 166 int i; 167 168 while (!tree->free_nodes) { 169 loff_t size; 170 int res; 171 172 res = hfsplus_extend_file(tree->inode); 173 if (res) 174 return ERR_PTR(res); 175 HFSPLUS_I(tree->inode).total_blocks = HFSPLUS_I(tree->inode).alloc_blocks; 176 size = HFSPLUS_I(tree->inode).total_blocks; 177 size <<= tree->sb->s_blocksize_bits; 178 tree->inode->i_size = size; 179 do_div(size, (u32)tree->node_size); 180 tree->free_nodes = (u32)size - tree->node_count; 181 tree->node_count = size; 182 } 183 184 nidx = 0; 185 node = hfsplus_find_bnode(tree, nidx); 186 len = hfsplus_brec_lenoff(node, 2, &off); 187 188 off += node->page_offset; 189 pagep = node->page + (off >> PAGE_CACHE_SHIFT); 190 data = hfsplus_kmap(*pagep); 191 off &= ~PAGE_CACHE_MASK; 192 idx = 0; 193 194 for (;;) { 195 while (len) { 196 byte = data[off]; 197 if (byte != 0xff) { 198 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) { 199 if (!(byte & m)) { 200 idx += i; 201 data[off] |= m; 202 set_page_dirty(*pagep); 203 hfsplus_kunmap(*pagep); 204 tree->free_nodes--; 205 mark_inode_dirty(tree->inode); 206 hfsplus_put_bnode(node); 207 return hfsplus_create_bnode(tree, idx); 208 } 209 } 210 } 211 if (++off >= PAGE_CACHE_SIZE) { 212 hfsplus_kunmap(*pagep++); 213 data = hfsplus_kmap(*pagep); 214 off = 0; 215 } 216 idx += 8; 217 len--; 218 } 219 nidx = node->next; 220 hfsplus_put_bnode(node); 221 if (!nidx) { 222 printk("need new bmap node...\n"); 223 hfsplus_kunmap(*pagep); 224 return ERR_PTR(-ENOSPC); 225 } 226 node = hfsplus_find_bnode(tree, nidx); 227 len = hfsplus_brec_lenoff(node, 0, &off); 228 229 off += node->page_offset; 230 pagep = node->page + (off >> PAGE_CACHE_SHIFT); 231 data = hfsplus_kmap(*pagep); 232 off &= ~PAGE_CACHE_MASK; 233 } 234 } 235 236 void hfsplus_btree_remove_node(hfsplus_bnode *node) 237 { 238 hfsplus_btree *tree; 239 hfsplus_bnode *tmp; 240 u32 cnid; 241 242 tree = node->tree; 243 if (node->prev) { 244 tmp = hfsplus_find_bnode(tree, node->prev); 245 tmp->next = node->next; 246 cnid = cpu_to_be32(tmp->next); 247 hfsplus_bnode_writebytes(tmp, &cnid, offsetof(hfsplus_btree_node_desc, next), 4); 248 hfsplus_put_bnode(tmp); 249 } else if (node->kind == HFSPLUS_NODE_LEAF) 250 tree->leaf_head = node->next; 251 252 if (node->next) { 253 tmp = hfsplus_find_bnode(tree, node->next); 254 tmp->prev = node->prev; 255 cnid = cpu_to_be32(tmp->prev); 256 hfsplus_bnode_writebytes(tmp, &cnid, offsetof(hfsplus_btree_node_desc, prev), 4); 257 hfsplus_put_bnode(tmp); 258 } else if (node->kind == HFSPLUS_NODE_LEAF) 259 tree->leaf_tail = node->prev; 260 261 // move down? 262 if (!node->prev && !node->next) { 263 printk("hfsplus_btree_del_level\n"); 264 } 265 if (!node->parent) { 266 tree->root = 0; 267 tree->depth = 0; 268 } 269 set_bit(HFSPLUS_BNODE_DELETED, &node->flags); 270 } 271 272 void hfsplus_btree_free_node(hfsplus_bnode *node) 273 { 274 hfsplus_btree *tree; 275 struct page *page; 276 u16 off, len; 277 u32 nidx; 278 u8 *data, byte, m; 279 280 dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this); 281 tree = node->tree; 282 nidx = node->this; 283 node = hfsplus_find_bnode(tree, 0); 284 len = hfsplus_brec_lenoff(node, 2, &off); 285 while (nidx >= len * 8) { 286 u32 i; 287 288 nidx -= len * 8; 289 i = node->next; 290 hfsplus_put_bnode(node); 291 if (!nidx) 292 /* panic */; 293 node = hfsplus_find_bnode(tree, nidx); 294 if (node->kind != HFSPLUS_NODE_MAP) 295 /* panic */; 296 len = hfsplus_brec_lenoff(node, 0, &off); 297 } 298 off += node->page_offset + nidx / 8; 299 page = node->page[off >> PAGE_CACHE_SHIFT]; 300 data = hfsplus_kmap(page); 301 off &= ~PAGE_CACHE_MASK; 302 m = 1 << (~nidx & 7); 303 byte = data[off]; 304 if (!(byte & m)) { 305 BUG(); 306 /* panic */ 307 hfsplus_kunmap(page); 308 hfsplus_put_bnode(node); 309 return; 310 } 311 data[off] = byte & ~m; 312 set_page_dirty(page); 313 hfsplus_kunmap(page); 314 hfsplus_put_bnode(node); 315 tree->free_nodes++; 316 mark_inode_dirty(tree->inode); 317 }
Cache object: 0fd48fe69b22c661cfbf529e3aba47ca
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]