~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/hfsplus/btree.c

Version: ~ [ linux-5.2 ] ~ [ linux-5.1.16 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.57 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.132 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.184 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.184 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.69 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp