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