GNU Linux-libre 4.9.308-gnu1
[releases.git] / fs / hfsplus / bnode.c
1 /*
2  *  linux/fs/hfsplus/bnode.c
3  *
4  * Copyright (C) 2001
5  * Brad Boyer (flar@allandria.com)
6  * (C) 2003 Ardis Technologies <roman@ardistech.com>
7  *
8  * Handle basic btree node operations
9  */
10
11 #include <linux/string.h>
12 #include <linux/slab.h>
13 #include <linux/pagemap.h>
14 #include <linux/fs.h>
15 #include <linux/swap.h>
16
17 #include "hfsplus_fs.h"
18 #include "hfsplus_raw.h"
19
20 /* Copy a specified range of bytes from the raw data of a node */
21 void hfs_bnode_read(struct hfs_bnode *node, void *buf, int off, int len)
22 {
23         struct page **pagep;
24         int l;
25
26         off += node->page_offset;
27         pagep = node->page + (off >> PAGE_SHIFT);
28         off &= ~PAGE_MASK;
29
30         l = min_t(int, len, PAGE_SIZE - off);
31         memcpy(buf, kmap(*pagep) + off, l);
32         kunmap(*pagep);
33
34         while ((len -= l) != 0) {
35                 buf += l;
36                 l = min_t(int, len, PAGE_SIZE);
37                 memcpy(buf, kmap(*++pagep), l);
38                 kunmap(*pagep);
39         }
40 }
41
42 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off)
43 {
44         __be16 data;
45         /* TODO: optimize later... */
46         hfs_bnode_read(node, &data, off, 2);
47         return be16_to_cpu(data);
48 }
49
50 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off)
51 {
52         u8 data;
53         /* TODO: optimize later... */
54         hfs_bnode_read(node, &data, off, 1);
55         return data;
56 }
57
58 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off)
59 {
60         struct hfs_btree *tree;
61         int key_len;
62
63         tree = node->tree;
64         if (node->type == HFS_NODE_LEAF ||
65             tree->attributes & HFS_TREE_VARIDXKEYS ||
66             node->tree->cnid == HFSPLUS_ATTR_CNID)
67                 key_len = hfs_bnode_read_u16(node, off) + 2;
68         else
69                 key_len = tree->max_key_len + 2;
70
71         hfs_bnode_read(node, key, off, key_len);
72 }
73
74 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len)
75 {
76         struct page **pagep;
77         int l;
78
79         off += node->page_offset;
80         pagep = node->page + (off >> PAGE_SHIFT);
81         off &= ~PAGE_MASK;
82
83         l = min_t(int, len, PAGE_SIZE - off);
84         memcpy(kmap(*pagep) + off, buf, l);
85         set_page_dirty(*pagep);
86         kunmap(*pagep);
87
88         while ((len -= l) != 0) {
89                 buf += l;
90                 l = min_t(int, len, PAGE_SIZE);
91                 memcpy(kmap(*++pagep), buf, l);
92                 set_page_dirty(*pagep);
93                 kunmap(*pagep);
94         }
95 }
96
97 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data)
98 {
99         __be16 v = cpu_to_be16(data);
100         /* TODO: optimize later... */
101         hfs_bnode_write(node, &v, off, 2);
102 }
103
104 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len)
105 {
106         struct page **pagep;
107         int l;
108
109         off += node->page_offset;
110         pagep = node->page + (off >> PAGE_SHIFT);
111         off &= ~PAGE_MASK;
112
113         l = min_t(int, len, PAGE_SIZE - off);
114         memset(kmap(*pagep) + off, 0, l);
115         set_page_dirty(*pagep);
116         kunmap(*pagep);
117
118         while ((len -= l) != 0) {
119                 l = min_t(int, len, PAGE_SIZE);
120                 memset(kmap(*++pagep), 0, l);
121                 set_page_dirty(*pagep);
122                 kunmap(*pagep);
123         }
124 }
125
126 void hfs_bnode_copy(struct hfs_bnode *dst_node, int dst,
127                     struct hfs_bnode *src_node, int src, int len)
128 {
129         struct hfs_btree *tree;
130         struct page **src_page, **dst_page;
131         int l;
132
133         hfs_dbg(BNODE_MOD, "copybytes: %u,%u,%u\n", dst, src, len);
134         if (!len)
135                 return;
136         tree = src_node->tree;
137         src += src_node->page_offset;
138         dst += dst_node->page_offset;
139         src_page = src_node->page + (src >> PAGE_SHIFT);
140         src &= ~PAGE_MASK;
141         dst_page = dst_node->page + (dst >> PAGE_SHIFT);
142         dst &= ~PAGE_MASK;
143
144         if (src == dst) {
145                 l = min_t(int, len, PAGE_SIZE - src);
146                 memcpy(kmap(*dst_page) + src, kmap(*src_page) + src, l);
147                 kunmap(*src_page);
148                 set_page_dirty(*dst_page);
149                 kunmap(*dst_page);
150
151                 while ((len -= l) != 0) {
152                         l = min_t(int, len, PAGE_SIZE);
153                         memcpy(kmap(*++dst_page), kmap(*++src_page), l);
154                         kunmap(*src_page);
155                         set_page_dirty(*dst_page);
156                         kunmap(*dst_page);
157                 }
158         } else {
159                 void *src_ptr, *dst_ptr;
160
161                 do {
162                         src_ptr = kmap(*src_page) + src;
163                         dst_ptr = kmap(*dst_page) + dst;
164                         if (PAGE_SIZE - src < PAGE_SIZE - dst) {
165                                 l = PAGE_SIZE - src;
166                                 src = 0;
167                                 dst += l;
168                         } else {
169                                 l = PAGE_SIZE - dst;
170                                 src += l;
171                                 dst = 0;
172                         }
173                         l = min(len, l);
174                         memcpy(dst_ptr, src_ptr, l);
175                         kunmap(*src_page);
176                         set_page_dirty(*dst_page);
177                         kunmap(*dst_page);
178                         if (!dst)
179                                 dst_page++;
180                         else
181                                 src_page++;
182                 } while ((len -= l));
183         }
184 }
185
186 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len)
187 {
188         struct page **src_page, **dst_page;
189         int l;
190
191         hfs_dbg(BNODE_MOD, "movebytes: %u,%u,%u\n", dst, src, len);
192         if (!len)
193                 return;
194         src += node->page_offset;
195         dst += node->page_offset;
196         if (dst > src) {
197                 src += len - 1;
198                 src_page = node->page + (src >> PAGE_SHIFT);
199                 src = (src & ~PAGE_MASK) + 1;
200                 dst += len - 1;
201                 dst_page = node->page + (dst >> PAGE_SHIFT);
202                 dst = (dst & ~PAGE_MASK) + 1;
203
204                 if (src == dst) {
205                         while (src < len) {
206                                 memmove(kmap(*dst_page), kmap(*src_page), src);
207                                 kunmap(*src_page);
208                                 set_page_dirty(*dst_page);
209                                 kunmap(*dst_page);
210                                 len -= src;
211                                 src = PAGE_SIZE;
212                                 src_page--;
213                                 dst_page--;
214                         }
215                         src -= len;
216                         memmove(kmap(*dst_page) + src,
217                                 kmap(*src_page) + src, len);
218                         kunmap(*src_page);
219                         set_page_dirty(*dst_page);
220                         kunmap(*dst_page);
221                 } else {
222                         void *src_ptr, *dst_ptr;
223
224                         do {
225                                 src_ptr = kmap(*src_page) + src;
226                                 dst_ptr = kmap(*dst_page) + dst;
227                                 if (src < dst) {
228                                         l = src;
229                                         src = PAGE_SIZE;
230                                         dst -= l;
231                                 } else {
232                                         l = dst;
233                                         src -= l;
234                                         dst = PAGE_SIZE;
235                                 }
236                                 l = min(len, l);
237                                 memmove(dst_ptr - l, src_ptr - l, l);
238                                 kunmap(*src_page);
239                                 set_page_dirty(*dst_page);
240                                 kunmap(*dst_page);
241                                 if (dst == PAGE_SIZE)
242                                         dst_page--;
243                                 else
244                                         src_page--;
245                         } while ((len -= l));
246                 }
247         } else {
248                 src_page = node->page + (src >> PAGE_SHIFT);
249                 src &= ~PAGE_MASK;
250                 dst_page = node->page + (dst >> PAGE_SHIFT);
251                 dst &= ~PAGE_MASK;
252
253                 if (src == dst) {
254                         l = min_t(int, len, PAGE_SIZE - src);
255                         memmove(kmap(*dst_page) + src,
256                                 kmap(*src_page) + src, l);
257                         kunmap(*src_page);
258                         set_page_dirty(*dst_page);
259                         kunmap(*dst_page);
260
261                         while ((len -= l) != 0) {
262                                 l = min_t(int, len, PAGE_SIZE);
263                                 memmove(kmap(*++dst_page),
264                                         kmap(*++src_page), l);
265                                 kunmap(*src_page);
266                                 set_page_dirty(*dst_page);
267                                 kunmap(*dst_page);
268                         }
269                 } else {
270                         void *src_ptr, *dst_ptr;
271
272                         do {
273                                 src_ptr = kmap(*src_page) + src;
274                                 dst_ptr = kmap(*dst_page) + dst;
275                                 if (PAGE_SIZE - src <
276                                                 PAGE_SIZE - dst) {
277                                         l = PAGE_SIZE - src;
278                                         src = 0;
279                                         dst += l;
280                                 } else {
281                                         l = PAGE_SIZE - dst;
282                                         src += l;
283                                         dst = 0;
284                                 }
285                                 l = min(len, l);
286                                 memmove(dst_ptr, src_ptr, l);
287                                 kunmap(*src_page);
288                                 set_page_dirty(*dst_page);
289                                 kunmap(*dst_page);
290                                 if (!dst)
291                                         dst_page++;
292                                 else
293                                         src_page++;
294                         } while ((len -= l));
295                 }
296         }
297 }
298
299 void hfs_bnode_dump(struct hfs_bnode *node)
300 {
301         struct hfs_bnode_desc desc;
302         __be32 cnid;
303         int i, off, key_off;
304
305         hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this);
306         hfs_bnode_read(node, &desc, 0, sizeof(desc));
307         hfs_dbg(BNODE_MOD, "%d, %d, %d, %d, %d\n",
308                 be32_to_cpu(desc.next), be32_to_cpu(desc.prev),
309                 desc.type, desc.height, be16_to_cpu(desc.num_recs));
310
311         off = node->tree->node_size - 2;
312         for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) {
313                 key_off = hfs_bnode_read_u16(node, off);
314                 hfs_dbg(BNODE_MOD, " %d", key_off);
315                 if (i && node->type == HFS_NODE_INDEX) {
316                         int tmp;
317
318                         if (node->tree->attributes & HFS_TREE_VARIDXKEYS ||
319                                         node->tree->cnid == HFSPLUS_ATTR_CNID)
320                                 tmp = hfs_bnode_read_u16(node, key_off) + 2;
321                         else
322                                 tmp = node->tree->max_key_len + 2;
323                         hfs_dbg_cont(BNODE_MOD, " (%d", tmp);
324                         hfs_bnode_read(node, &cnid, key_off + tmp, 4);
325                         hfs_dbg_cont(BNODE_MOD, ",%d)", be32_to_cpu(cnid));
326                 } else if (i && node->type == HFS_NODE_LEAF) {
327                         int tmp;
328
329                         tmp = hfs_bnode_read_u16(node, key_off);
330                         hfs_dbg_cont(BNODE_MOD, " (%d)", tmp);
331                 }
332         }
333         hfs_dbg_cont(BNODE_MOD, "\n");
334 }
335
336 void hfs_bnode_unlink(struct hfs_bnode *node)
337 {
338         struct hfs_btree *tree;
339         struct hfs_bnode *tmp;
340         __be32 cnid;
341
342         tree = node->tree;
343         if (node->prev) {
344                 tmp = hfs_bnode_find(tree, node->prev);
345                 if (IS_ERR(tmp))
346                         return;
347                 tmp->next = node->next;
348                 cnid = cpu_to_be32(tmp->next);
349                 hfs_bnode_write(tmp, &cnid,
350                         offsetof(struct hfs_bnode_desc, next), 4);
351                 hfs_bnode_put(tmp);
352         } else if (node->type == HFS_NODE_LEAF)
353                 tree->leaf_head = node->next;
354
355         if (node->next) {
356                 tmp = hfs_bnode_find(tree, node->next);
357                 if (IS_ERR(tmp))
358                         return;
359                 tmp->prev = node->prev;
360                 cnid = cpu_to_be32(tmp->prev);
361                 hfs_bnode_write(tmp, &cnid,
362                         offsetof(struct hfs_bnode_desc, prev), 4);
363                 hfs_bnode_put(tmp);
364         } else if (node->type == HFS_NODE_LEAF)
365                 tree->leaf_tail = node->prev;
366
367         /* move down? */
368         if (!node->prev && !node->next)
369                 hfs_dbg(BNODE_MOD, "hfs_btree_del_level\n");
370         if (!node->parent) {
371                 tree->root = 0;
372                 tree->depth = 0;
373         }
374         set_bit(HFS_BNODE_DELETED, &node->flags);
375 }
376
377 static inline int hfs_bnode_hash(u32 num)
378 {
379         num = (num >> 16) + num;
380         num += num >> 8;
381         return num & (NODE_HASH_SIZE - 1);
382 }
383
384 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid)
385 {
386         struct hfs_bnode *node;
387
388         if (cnid >= tree->node_count) {
389                 pr_err("request for non-existent node %d in B*Tree\n",
390                        cnid);
391                 return NULL;
392         }
393
394         for (node = tree->node_hash[hfs_bnode_hash(cnid)];
395                         node; node = node->next_hash)
396                 if (node->this == cnid)
397                         return node;
398         return NULL;
399 }
400
401 static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid)
402 {
403         struct super_block *sb;
404         struct hfs_bnode *node, *node2;
405         struct address_space *mapping;
406         struct page *page;
407         int size, block, i, hash;
408         loff_t off;
409
410         if (cnid >= tree->node_count) {
411                 pr_err("request for non-existent node %d in B*Tree\n",
412                        cnid);
413                 return NULL;
414         }
415
416         sb = tree->inode->i_sb;
417         size = sizeof(struct hfs_bnode) + tree->pages_per_bnode *
418                 sizeof(struct page *);
419         node = kzalloc(size, GFP_KERNEL);
420         if (!node)
421                 return NULL;
422         node->tree = tree;
423         node->this = cnid;
424         set_bit(HFS_BNODE_NEW, &node->flags);
425         atomic_set(&node->refcnt, 1);
426         hfs_dbg(BNODE_REFS, "new_node(%d:%d): 1\n",
427                 node->tree->cnid, node->this);
428         init_waitqueue_head(&node->lock_wq);
429         spin_lock(&tree->hash_lock);
430         node2 = hfs_bnode_findhash(tree, cnid);
431         if (!node2) {
432                 hash = hfs_bnode_hash(cnid);
433                 node->next_hash = tree->node_hash[hash];
434                 tree->node_hash[hash] = node;
435                 tree->node_hash_cnt++;
436         } else {
437                 spin_unlock(&tree->hash_lock);
438                 kfree(node);
439                 wait_event(node2->lock_wq,
440                         !test_bit(HFS_BNODE_NEW, &node2->flags));
441                 return node2;
442         }
443         spin_unlock(&tree->hash_lock);
444
445         mapping = tree->inode->i_mapping;
446         off = (loff_t)cnid << tree->node_size_shift;
447         block = off >> PAGE_SHIFT;
448         node->page_offset = off & ~PAGE_MASK;
449         for (i = 0; i < tree->pages_per_bnode; block++, i++) {
450                 page = read_mapping_page(mapping, block, NULL);
451                 if (IS_ERR(page))
452                         goto fail;
453                 if (PageError(page)) {
454                         put_page(page);
455                         goto fail;
456                 }
457                 node->page[i] = page;
458         }
459
460         return node;
461 fail:
462         set_bit(HFS_BNODE_ERROR, &node->flags);
463         return node;
464 }
465
466 void hfs_bnode_unhash(struct hfs_bnode *node)
467 {
468         struct hfs_bnode **p;
469
470         hfs_dbg(BNODE_REFS, "remove_node(%d:%d): %d\n",
471                 node->tree->cnid, node->this, atomic_read(&node->refcnt));
472         for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)];
473              *p && *p != node; p = &(*p)->next_hash)
474                 ;
475         BUG_ON(!*p);
476         *p = node->next_hash;
477         node->tree->node_hash_cnt--;
478 }
479
480 /* Load a particular node out of a tree */
481 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num)
482 {
483         struct hfs_bnode *node;
484         struct hfs_bnode_desc *desc;
485         int i, rec_off, off, next_off;
486         int entry_size, key_size;
487
488         spin_lock(&tree->hash_lock);
489         node = hfs_bnode_findhash(tree, num);
490         if (node) {
491                 hfs_bnode_get(node);
492                 spin_unlock(&tree->hash_lock);
493                 wait_event(node->lock_wq,
494                         !test_bit(HFS_BNODE_NEW, &node->flags));
495                 if (test_bit(HFS_BNODE_ERROR, &node->flags))
496                         goto node_error;
497                 return node;
498         }
499         spin_unlock(&tree->hash_lock);
500         node = __hfs_bnode_create(tree, num);
501         if (!node)
502                 return ERR_PTR(-ENOMEM);
503         if (test_bit(HFS_BNODE_ERROR, &node->flags))
504                 goto node_error;
505         if (!test_bit(HFS_BNODE_NEW, &node->flags))
506                 return node;
507
508         desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) +
509                         node->page_offset);
510         node->prev = be32_to_cpu(desc->prev);
511         node->next = be32_to_cpu(desc->next);
512         node->num_recs = be16_to_cpu(desc->num_recs);
513         node->type = desc->type;
514         node->height = desc->height;
515         kunmap(node->page[0]);
516
517         switch (node->type) {
518         case HFS_NODE_HEADER:
519         case HFS_NODE_MAP:
520                 if (node->height != 0)
521                         goto node_error;
522                 break;
523         case HFS_NODE_LEAF:
524                 if (node->height != 1)
525                         goto node_error;
526                 break;
527         case HFS_NODE_INDEX:
528                 if (node->height <= 1 || node->height > tree->depth)
529                         goto node_error;
530                 break;
531         default:
532                 goto node_error;
533         }
534
535         rec_off = tree->node_size - 2;
536         off = hfs_bnode_read_u16(node, rec_off);
537         if (off != sizeof(struct hfs_bnode_desc))
538                 goto node_error;
539         for (i = 1; i <= node->num_recs; off = next_off, i++) {
540                 rec_off -= 2;
541                 next_off = hfs_bnode_read_u16(node, rec_off);
542                 if (next_off <= off ||
543                     next_off > tree->node_size ||
544                     next_off & 1)
545                         goto node_error;
546                 entry_size = next_off - off;
547                 if (node->type != HFS_NODE_INDEX &&
548                     node->type != HFS_NODE_LEAF)
549                         continue;
550                 key_size = hfs_bnode_read_u16(node, off) + 2;
551                 if (key_size >= entry_size || key_size & 1)
552                         goto node_error;
553         }
554         clear_bit(HFS_BNODE_NEW, &node->flags);
555         wake_up(&node->lock_wq);
556         return node;
557
558 node_error:
559         set_bit(HFS_BNODE_ERROR, &node->flags);
560         clear_bit(HFS_BNODE_NEW, &node->flags);
561         wake_up(&node->lock_wq);
562         hfs_bnode_put(node);
563         return ERR_PTR(-EIO);
564 }
565
566 void hfs_bnode_free(struct hfs_bnode *node)
567 {
568         int i;
569
570         for (i = 0; i < node->tree->pages_per_bnode; i++)
571                 if (node->page[i])
572                         put_page(node->page[i]);
573         kfree(node);
574 }
575
576 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num)
577 {
578         struct hfs_bnode *node;
579         struct page **pagep;
580         int i;
581
582         spin_lock(&tree->hash_lock);
583         node = hfs_bnode_findhash(tree, num);
584         spin_unlock(&tree->hash_lock);
585         if (node) {
586                 pr_crit("new node %u already hashed?\n", num);
587                 WARN_ON(1);
588                 return node;
589         }
590         node = __hfs_bnode_create(tree, num);
591         if (!node)
592                 return ERR_PTR(-ENOMEM);
593         if (test_bit(HFS_BNODE_ERROR, &node->flags)) {
594                 hfs_bnode_put(node);
595                 return ERR_PTR(-EIO);
596         }
597
598         pagep = node->page;
599         memset(kmap(*pagep) + node->page_offset, 0,
600                min_t(int, PAGE_SIZE, tree->node_size));
601         set_page_dirty(*pagep);
602         kunmap(*pagep);
603         for (i = 1; i < tree->pages_per_bnode; i++) {
604                 memset(kmap(*++pagep), 0, PAGE_SIZE);
605                 set_page_dirty(*pagep);
606                 kunmap(*pagep);
607         }
608         clear_bit(HFS_BNODE_NEW, &node->flags);
609         wake_up(&node->lock_wq);
610
611         return node;
612 }
613
614 void hfs_bnode_get(struct hfs_bnode *node)
615 {
616         if (node) {
617                 atomic_inc(&node->refcnt);
618                 hfs_dbg(BNODE_REFS, "get_node(%d:%d): %d\n",
619                         node->tree->cnid, node->this,
620                         atomic_read(&node->refcnt));
621         }
622 }
623
624 /* Dispose of resources used by a node */
625 void hfs_bnode_put(struct hfs_bnode *node)
626 {
627         if (node) {
628                 struct hfs_btree *tree = node->tree;
629                 int i;
630
631                 hfs_dbg(BNODE_REFS, "put_node(%d:%d): %d\n",
632                         node->tree->cnid, node->this,
633                         atomic_read(&node->refcnt));
634                 BUG_ON(!atomic_read(&node->refcnt));
635                 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock))
636                         return;
637                 for (i = 0; i < tree->pages_per_bnode; i++) {
638                         if (!node->page[i])
639                                 continue;
640                         mark_page_accessed(node->page[i]);
641                 }
642
643                 if (test_bit(HFS_BNODE_DELETED, &node->flags)) {
644                         hfs_bnode_unhash(node);
645                         spin_unlock(&tree->hash_lock);
646                         if (hfs_bnode_need_zeroout(tree))
647                                 hfs_bnode_clear(node, 0, tree->node_size);
648                         hfs_bmap_free(node);
649                         hfs_bnode_free(node);
650                         return;
651                 }
652                 spin_unlock(&tree->hash_lock);
653         }
654 }
655
656 /*
657  * Unused nodes have to be zeroed if this is the catalog tree and
658  * a corresponding flag in the volume header is set.
659  */
660 bool hfs_bnode_need_zeroout(struct hfs_btree *tree)
661 {
662         struct super_block *sb = tree->inode->i_sb;
663         struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
664         const u32 volume_attr = be32_to_cpu(sbi->s_vhdr->attributes);
665
666         return tree->cnid == HFSPLUS_CAT_CNID &&
667                 volume_attr & HFSPLUS_VOL_UNUSED_NODE_FIX;
668 }