xref: /openbmc/linux/fs/hfsplus/extents.c (revision 97da55fc)
1 /*
2  *  linux/fs/hfsplus/extents.c
3  *
4  * Copyright (C) 2001
5  * Brad Boyer (flar@allandria.com)
6  * (C) 2003 Ardis Technologies <roman@ardistech.com>
7  *
8  * Handling of Extents both in catalog and extents overflow trees
9  */
10 
11 #include <linux/errno.h>
12 #include <linux/fs.h>
13 #include <linux/pagemap.h>
14 
15 #include "hfsplus_fs.h"
16 #include "hfsplus_raw.h"
17 
18 /* Compare two extents keys, returns 0 on same, pos/neg for difference */
19 int hfsplus_ext_cmp_key(const hfsplus_btree_key *k1,
20 			const hfsplus_btree_key *k2)
21 {
22 	__be32 k1id, k2id;
23 	__be32 k1s, k2s;
24 
25 	k1id = k1->ext.cnid;
26 	k2id = k2->ext.cnid;
27 	if (k1id != k2id)
28 		return be32_to_cpu(k1id) < be32_to_cpu(k2id) ? -1 : 1;
29 
30 	if (k1->ext.fork_type != k2->ext.fork_type)
31 		return k1->ext.fork_type < k2->ext.fork_type ? -1 : 1;
32 
33 	k1s = k1->ext.start_block;
34 	k2s = k2->ext.start_block;
35 	if (k1s == k2s)
36 		return 0;
37 	return be32_to_cpu(k1s) < be32_to_cpu(k2s) ? -1 : 1;
38 }
39 
40 static void hfsplus_ext_build_key(hfsplus_btree_key *key, u32 cnid,
41 				  u32 block, u8 type)
42 {
43 	key->key_len = cpu_to_be16(HFSPLUS_EXT_KEYLEN - 2);
44 	key->ext.cnid = cpu_to_be32(cnid);
45 	key->ext.start_block = cpu_to_be32(block);
46 	key->ext.fork_type = type;
47 	key->ext.pad = 0;
48 }
49 
50 static u32 hfsplus_ext_find_block(struct hfsplus_extent *ext, u32 off)
51 {
52 	int i;
53 	u32 count;
54 
55 	for (i = 0; i < 8; ext++, i++) {
56 		count = be32_to_cpu(ext->block_count);
57 		if (off < count)
58 			return be32_to_cpu(ext->start_block) + off;
59 		off -= count;
60 	}
61 	/* panic? */
62 	return 0;
63 }
64 
65 static int hfsplus_ext_block_count(struct hfsplus_extent *ext)
66 {
67 	int i;
68 	u32 count = 0;
69 
70 	for (i = 0; i < 8; ext++, i++)
71 		count += be32_to_cpu(ext->block_count);
72 	return count;
73 }
74 
75 static u32 hfsplus_ext_lastblock(struct hfsplus_extent *ext)
76 {
77 	int i;
78 
79 	ext += 7;
80 	for (i = 0; i < 7; ext--, i++)
81 		if (ext->block_count)
82 			break;
83 	return be32_to_cpu(ext->start_block) + be32_to_cpu(ext->block_count);
84 }
85 
86 static void __hfsplus_ext_write_extent(struct inode *inode,
87 		struct hfs_find_data *fd)
88 {
89 	struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
90 	int res;
91 
92 	WARN_ON(!mutex_is_locked(&hip->extents_lock));
93 
94 	hfsplus_ext_build_key(fd->search_key, inode->i_ino, hip->cached_start,
95 			      HFSPLUS_IS_RSRC(inode) ?
96 				HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);
97 
98 	res = hfs_brec_find(fd, hfs_find_rec_by_key);
99 	if (hip->extent_state & HFSPLUS_EXT_NEW) {
100 		if (res != -ENOENT)
101 			return;
102 		hfs_brec_insert(fd, hip->cached_extents,
103 				sizeof(hfsplus_extent_rec));
104 		hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW);
105 	} else {
106 		if (res)
107 			return;
108 		hfs_bnode_write(fd->bnode, hip->cached_extents,
109 				fd->entryoffset, fd->entrylength);
110 		hip->extent_state &= ~HFSPLUS_EXT_DIRTY;
111 	}
112 
113 	/*
114 	 * We can't just use hfsplus_mark_inode_dirty here, because we
115 	 * also get called from hfsplus_write_inode, which should not
116 	 * redirty the inode.  Instead the callers have to be careful
117 	 * to explicily mark the inode dirty, too.
118 	 */
119 	set_bit(HFSPLUS_I_EXT_DIRTY, &hip->flags);
120 }
121 
122 static int hfsplus_ext_write_extent_locked(struct inode *inode)
123 {
124 	int res;
125 
126 	if (HFSPLUS_I(inode)->extent_state & HFSPLUS_EXT_DIRTY) {
127 		struct hfs_find_data fd;
128 
129 		res = hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd);
130 		if (res)
131 			return res;
132 		__hfsplus_ext_write_extent(inode, &fd);
133 		hfs_find_exit(&fd);
134 	}
135 	return 0;
136 }
137 
138 int hfsplus_ext_write_extent(struct inode *inode)
139 {
140 	int res;
141 
142 	mutex_lock(&HFSPLUS_I(inode)->extents_lock);
143 	res = hfsplus_ext_write_extent_locked(inode);
144 	mutex_unlock(&HFSPLUS_I(inode)->extents_lock);
145 
146 	return res;
147 }
148 
149 static inline int __hfsplus_ext_read_extent(struct hfs_find_data *fd,
150 					    struct hfsplus_extent *extent,
151 					    u32 cnid, u32 block, u8 type)
152 {
153 	int res;
154 
155 	hfsplus_ext_build_key(fd->search_key, cnid, block, type);
156 	fd->key->ext.cnid = 0;
157 	res = hfs_brec_find(fd, hfs_find_rec_by_key);
158 	if (res && res != -ENOENT)
159 		return res;
160 	if (fd->key->ext.cnid != fd->search_key->ext.cnid ||
161 	    fd->key->ext.fork_type != fd->search_key->ext.fork_type)
162 		return -ENOENT;
163 	if (fd->entrylength != sizeof(hfsplus_extent_rec))
164 		return -EIO;
165 	hfs_bnode_read(fd->bnode, extent, fd->entryoffset,
166 		sizeof(hfsplus_extent_rec));
167 	return 0;
168 }
169 
170 static inline int __hfsplus_ext_cache_extent(struct hfs_find_data *fd,
171 		struct inode *inode, u32 block)
172 {
173 	struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
174 	int res;
175 
176 	WARN_ON(!mutex_is_locked(&hip->extents_lock));
177 
178 	if (hip->extent_state & HFSPLUS_EXT_DIRTY)
179 		__hfsplus_ext_write_extent(inode, fd);
180 
181 	res = __hfsplus_ext_read_extent(fd, hip->cached_extents, inode->i_ino,
182 					block, HFSPLUS_IS_RSRC(inode) ?
183 						HFSPLUS_TYPE_RSRC :
184 						HFSPLUS_TYPE_DATA);
185 	if (!res) {
186 		hip->cached_start = be32_to_cpu(fd->key->ext.start_block);
187 		hip->cached_blocks =
188 			hfsplus_ext_block_count(hip->cached_extents);
189 	} else {
190 		hip->cached_start = hip->cached_blocks = 0;
191 		hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW);
192 	}
193 	return res;
194 }
195 
196 static int hfsplus_ext_read_extent(struct inode *inode, u32 block)
197 {
198 	struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
199 	struct hfs_find_data fd;
200 	int res;
201 
202 	if (block >= hip->cached_start &&
203 	    block < hip->cached_start + hip->cached_blocks)
204 		return 0;
205 
206 	res = hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd);
207 	if (!res) {
208 		res = __hfsplus_ext_cache_extent(&fd, inode, block);
209 		hfs_find_exit(&fd);
210 	}
211 	return res;
212 }
213 
214 /* Get a block at iblock for inode, possibly allocating if create */
215 int hfsplus_get_block(struct inode *inode, sector_t iblock,
216 		      struct buffer_head *bh_result, int create)
217 {
218 	struct super_block *sb = inode->i_sb;
219 	struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
220 	struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
221 	int res = -EIO;
222 	u32 ablock, dblock, mask;
223 	sector_t sector;
224 	int was_dirty = 0;
225 	int shift;
226 
227 	/* Convert inode block to disk allocation block */
228 	shift = sbi->alloc_blksz_shift - sb->s_blocksize_bits;
229 	ablock = iblock >> sbi->fs_shift;
230 
231 	if (iblock >= hip->fs_blocks) {
232 		if (iblock > hip->fs_blocks || !create)
233 			return -EIO;
234 		if (ablock >= hip->alloc_blocks) {
235 			res = hfsplus_file_extend(inode);
236 			if (res)
237 				return res;
238 		}
239 	} else
240 		create = 0;
241 
242 	if (ablock < hip->first_blocks) {
243 		dblock = hfsplus_ext_find_block(hip->first_extents, ablock);
244 		goto done;
245 	}
246 
247 	if (inode->i_ino == HFSPLUS_EXT_CNID)
248 		return -EIO;
249 
250 	mutex_lock(&hip->extents_lock);
251 
252 	/*
253 	 * hfsplus_ext_read_extent will write out a cached extent into
254 	 * the extents btree.  In that case we may have to mark the inode
255 	 * dirty even for a pure read of an extent here.
256 	 */
257 	was_dirty = (hip->extent_state & HFSPLUS_EXT_DIRTY);
258 	res = hfsplus_ext_read_extent(inode, ablock);
259 	if (res) {
260 		mutex_unlock(&hip->extents_lock);
261 		return -EIO;
262 	}
263 	dblock = hfsplus_ext_find_block(hip->cached_extents,
264 					ablock - hip->cached_start);
265 	mutex_unlock(&hip->extents_lock);
266 
267 done:
268 	dprint(DBG_EXTENT, "get_block(%lu): %llu - %u\n",
269 		inode->i_ino, (long long)iblock, dblock);
270 
271 	mask = (1 << sbi->fs_shift) - 1;
272 	sector = ((sector_t)dblock << sbi->fs_shift) +
273 		  sbi->blockoffset + (iblock & mask);
274 	map_bh(bh_result, sb, sector);
275 
276 	if (create) {
277 		set_buffer_new(bh_result);
278 		hip->phys_size += sb->s_blocksize;
279 		hip->fs_blocks++;
280 		inode_add_bytes(inode, sb->s_blocksize);
281 	}
282 	if (create || was_dirty)
283 		mark_inode_dirty(inode);
284 	return 0;
285 }
286 
287 static void hfsplus_dump_extent(struct hfsplus_extent *extent)
288 {
289 	int i;
290 
291 	dprint(DBG_EXTENT, "   ");
292 	for (i = 0; i < 8; i++)
293 		dprint(DBG_EXTENT, " %u:%u", be32_to_cpu(extent[i].start_block),
294 				 be32_to_cpu(extent[i].block_count));
295 	dprint(DBG_EXTENT, "\n");
296 }
297 
298 static int hfsplus_add_extent(struct hfsplus_extent *extent, u32 offset,
299 			      u32 alloc_block, u32 block_count)
300 {
301 	u32 count, start;
302 	int i;
303 
304 	hfsplus_dump_extent(extent);
305 	for (i = 0; i < 8; extent++, i++) {
306 		count = be32_to_cpu(extent->block_count);
307 		if (offset == count) {
308 			start = be32_to_cpu(extent->start_block);
309 			if (alloc_block != start + count) {
310 				if (++i >= 8)
311 					return -ENOSPC;
312 				extent++;
313 				extent->start_block = cpu_to_be32(alloc_block);
314 			} else
315 				block_count += count;
316 			extent->block_count = cpu_to_be32(block_count);
317 			return 0;
318 		} else if (offset < count)
319 			break;
320 		offset -= count;
321 	}
322 	/* panic? */
323 	return -EIO;
324 }
325 
326 static int hfsplus_free_extents(struct super_block *sb,
327 				struct hfsplus_extent *extent,
328 				u32 offset, u32 block_nr)
329 {
330 	u32 count, start;
331 	int i;
332 	int err = 0;
333 
334 	hfsplus_dump_extent(extent);
335 	for (i = 0; i < 8; extent++, i++) {
336 		count = be32_to_cpu(extent->block_count);
337 		if (offset == count)
338 			goto found;
339 		else if (offset < count)
340 			break;
341 		offset -= count;
342 	}
343 	/* panic? */
344 	return -EIO;
345 found:
346 	for (;;) {
347 		start = be32_to_cpu(extent->start_block);
348 		if (count <= block_nr) {
349 			err = hfsplus_block_free(sb, start, count);
350 			if (err) {
351 				printk(KERN_ERR "hfs: can't free extent\n");
352 				dprint(DBG_EXTENT, " start: %u count: %u\n",
353 					start, count);
354 			}
355 			extent->block_count = 0;
356 			extent->start_block = 0;
357 			block_nr -= count;
358 		} else {
359 			count -= block_nr;
360 			err = hfsplus_block_free(sb, start + count, block_nr);
361 			if (err) {
362 				printk(KERN_ERR "hfs: can't free extent\n");
363 				dprint(DBG_EXTENT, " start: %u count: %u\n",
364 					start, count);
365 			}
366 			extent->block_count = cpu_to_be32(count);
367 			block_nr = 0;
368 		}
369 		if (!block_nr || !i) {
370 			/*
371 			 * Try to free all extents and
372 			 * return only last error
373 			 */
374 			return err;
375 		}
376 		i--;
377 		extent--;
378 		count = be32_to_cpu(extent->block_count);
379 	}
380 }
381 
382 int hfsplus_free_fork(struct super_block *sb, u32 cnid,
383 		struct hfsplus_fork_raw *fork, int type)
384 {
385 	struct hfs_find_data fd;
386 	hfsplus_extent_rec ext_entry;
387 	u32 total_blocks, blocks, start;
388 	int res, i;
389 
390 	total_blocks = be32_to_cpu(fork->total_blocks);
391 	if (!total_blocks)
392 		return 0;
393 
394 	blocks = 0;
395 	for (i = 0; i < 8; i++)
396 		blocks += be32_to_cpu(fork->extents[i].block_count);
397 
398 	res = hfsplus_free_extents(sb, fork->extents, blocks, blocks);
399 	if (res)
400 		return res;
401 	if (total_blocks == blocks)
402 		return 0;
403 
404 	res = hfs_find_init(HFSPLUS_SB(sb)->ext_tree, &fd);
405 	if (res)
406 		return res;
407 	do {
408 		res = __hfsplus_ext_read_extent(&fd, ext_entry, cnid,
409 						total_blocks, type);
410 		if (res)
411 			break;
412 		start = be32_to_cpu(fd.key->ext.start_block);
413 		hfsplus_free_extents(sb, ext_entry,
414 				     total_blocks - start,
415 				     total_blocks);
416 		hfs_brec_remove(&fd);
417 		total_blocks = start;
418 	} while (total_blocks > blocks);
419 	hfs_find_exit(&fd);
420 
421 	return res;
422 }
423 
424 int hfsplus_file_extend(struct inode *inode)
425 {
426 	struct super_block *sb = inode->i_sb;
427 	struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
428 	struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
429 	u32 start, len, goal;
430 	int res;
431 
432 	if (sbi->alloc_file->i_size * 8 <
433 	    sbi->total_blocks - sbi->free_blocks + 8) {
434 		/* extend alloc file */
435 		printk(KERN_ERR "hfs: extend alloc file! "
436 				"(%llu,%u,%u)\n",
437 			sbi->alloc_file->i_size * 8,
438 			sbi->total_blocks, sbi->free_blocks);
439 		return -ENOSPC;
440 	}
441 
442 	mutex_lock(&hip->extents_lock);
443 	if (hip->alloc_blocks == hip->first_blocks)
444 		goal = hfsplus_ext_lastblock(hip->first_extents);
445 	else {
446 		res = hfsplus_ext_read_extent(inode, hip->alloc_blocks);
447 		if (res)
448 			goto out;
449 		goal = hfsplus_ext_lastblock(hip->cached_extents);
450 	}
451 
452 	len = hip->clump_blocks;
453 	start = hfsplus_block_allocate(sb, sbi->total_blocks, goal, &len);
454 	if (start >= sbi->total_blocks) {
455 		start = hfsplus_block_allocate(sb, goal, 0, &len);
456 		if (start >= goal) {
457 			res = -ENOSPC;
458 			goto out;
459 		}
460 	}
461 
462 	dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
463 
464 	if (hip->alloc_blocks <= hip->first_blocks) {
465 		if (!hip->first_blocks) {
466 			dprint(DBG_EXTENT, "first extents\n");
467 			/* no extents yet */
468 			hip->first_extents[0].start_block = cpu_to_be32(start);
469 			hip->first_extents[0].block_count = cpu_to_be32(len);
470 			res = 0;
471 		} else {
472 			/* try to append to extents in inode */
473 			res = hfsplus_add_extent(hip->first_extents,
474 						 hip->alloc_blocks,
475 						 start, len);
476 			if (res == -ENOSPC)
477 				goto insert_extent;
478 		}
479 		if (!res) {
480 			hfsplus_dump_extent(hip->first_extents);
481 			hip->first_blocks += len;
482 		}
483 	} else {
484 		res = hfsplus_add_extent(hip->cached_extents,
485 					 hip->alloc_blocks - hip->cached_start,
486 					 start, len);
487 		if (!res) {
488 			hfsplus_dump_extent(hip->cached_extents);
489 			hip->extent_state |= HFSPLUS_EXT_DIRTY;
490 			hip->cached_blocks += len;
491 		} else if (res == -ENOSPC)
492 			goto insert_extent;
493 	}
494 out:
495 	mutex_unlock(&hip->extents_lock);
496 	if (!res) {
497 		hip->alloc_blocks += len;
498 		hfsplus_mark_inode_dirty(inode, HFSPLUS_I_ALLOC_DIRTY);
499 	}
500 	return res;
501 
502 insert_extent:
503 	dprint(DBG_EXTENT, "insert new extent\n");
504 	res = hfsplus_ext_write_extent_locked(inode);
505 	if (res)
506 		goto out;
507 
508 	memset(hip->cached_extents, 0, sizeof(hfsplus_extent_rec));
509 	hip->cached_extents[0].start_block = cpu_to_be32(start);
510 	hip->cached_extents[0].block_count = cpu_to_be32(len);
511 	hfsplus_dump_extent(hip->cached_extents);
512 	hip->extent_state |= HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW;
513 	hip->cached_start = hip->alloc_blocks;
514 	hip->cached_blocks = len;
515 
516 	res = 0;
517 	goto out;
518 }
519 
520 void hfsplus_file_truncate(struct inode *inode)
521 {
522 	struct super_block *sb = inode->i_sb;
523 	struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
524 	struct hfs_find_data fd;
525 	u32 alloc_cnt, blk_cnt, start;
526 	int res;
527 
528 	dprint(DBG_INODE, "truncate: %lu, %llu -> %llu\n",
529 		inode->i_ino, (long long)hip->phys_size,
530 		inode->i_size);
531 
532 	if (inode->i_size > hip->phys_size) {
533 		struct address_space *mapping = inode->i_mapping;
534 		struct page *page;
535 		void *fsdata;
536 		u32 size = inode->i_size;
537 
538 		res = pagecache_write_begin(NULL, mapping, size, 0,
539 						AOP_FLAG_UNINTERRUPTIBLE,
540 						&page, &fsdata);
541 		if (res)
542 			return;
543 		res = pagecache_write_end(NULL, mapping, size,
544 			0, 0, page, fsdata);
545 		if (res < 0)
546 			return;
547 		mark_inode_dirty(inode);
548 		return;
549 	} else if (inode->i_size == hip->phys_size)
550 		return;
551 
552 	blk_cnt = (inode->i_size + HFSPLUS_SB(sb)->alloc_blksz - 1) >>
553 			HFSPLUS_SB(sb)->alloc_blksz_shift;
554 	alloc_cnt = hip->alloc_blocks;
555 	if (blk_cnt == alloc_cnt)
556 		goto out;
557 
558 	mutex_lock(&hip->extents_lock);
559 	res = hfs_find_init(HFSPLUS_SB(sb)->ext_tree, &fd);
560 	if (res) {
561 		mutex_unlock(&hip->extents_lock);
562 		/* XXX: We lack error handling of hfsplus_file_truncate() */
563 		return;
564 	}
565 	while (1) {
566 		if (alloc_cnt == hip->first_blocks) {
567 			hfsplus_free_extents(sb, hip->first_extents,
568 					     alloc_cnt, alloc_cnt - blk_cnt);
569 			hfsplus_dump_extent(hip->first_extents);
570 			hip->first_blocks = blk_cnt;
571 			break;
572 		}
573 		res = __hfsplus_ext_cache_extent(&fd, inode, alloc_cnt);
574 		if (res)
575 			break;
576 		start = hip->cached_start;
577 		hfsplus_free_extents(sb, hip->cached_extents,
578 				     alloc_cnt - start, alloc_cnt - blk_cnt);
579 		hfsplus_dump_extent(hip->cached_extents);
580 		if (blk_cnt > start) {
581 			hip->extent_state |= HFSPLUS_EXT_DIRTY;
582 			break;
583 		}
584 		alloc_cnt = start;
585 		hip->cached_start = hip->cached_blocks = 0;
586 		hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW);
587 		hfs_brec_remove(&fd);
588 	}
589 	hfs_find_exit(&fd);
590 	mutex_unlock(&hip->extents_lock);
591 
592 	hip->alloc_blocks = blk_cnt;
593 out:
594 	hip->phys_size = inode->i_size;
595 	hip->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >>
596 		sb->s_blocksize_bits;
597 	inode_set_bytes(inode, hip->fs_blocks << sb->s_blocksize_bits);
598 	hfsplus_mark_inode_dirty(inode, HFSPLUS_I_ALLOC_DIRTY);
599 }
600