xref: /linux/fs/hfs/extent.c (revision 2775df6e5e324be9dc375f7db2c8d3042df72bbf)
1 /*
2  *  linux/fs/hfs/extent.c
3  *
4  * Copyright (C) 1995-1997  Paul H. Hargrove
5  * (C) 2003 Ardis Technologies <roman@ardistech.com>
6  * This file may be distributed under the terms of the GNU General Public License.
7  *
8  * This file contains the functions related to the extents B-tree.
9  */
10 
11 #include <linux/pagemap.h>
12 
13 #include "hfs_fs.h"
14 #include "btree.h"
15 
16 /*================ File-local functions ================*/
17 
18 /*
19  * build_key
20  */
hfs_ext_build_key(hfs_btree_key * key,u32 cnid,u16 block,u8 type)21 static void hfs_ext_build_key(hfs_btree_key *key, u32 cnid, u16 block, u8 type)
22 {
23 	key->key_len = 7;
24 	key->ext.FkType = type;
25 	key->ext.FNum = cpu_to_be32(cnid);
26 	key->ext.FABN = cpu_to_be16(block);
27 }
28 
29 /*
30  * hfs_ext_compare()
31  *
32  * Description:
33  *   This is the comparison function used for the extents B-tree.  In
34  *   comparing extent B-tree entries, the file id is the most
35  *   significant field (compared as unsigned ints); the fork type is
36  *   the second most significant field (compared as unsigned chars);
37  *   and the allocation block number field is the least significant
38  *   (compared as unsigned ints).
39  * Input Variable(s):
40  *   struct hfs_ext_key *key1: pointer to the first key to compare
41  *   struct hfs_ext_key *key2: pointer to the second key to compare
42  * Output Variable(s):
43  *   NONE
44  * Returns:
45  *   int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
46  * Preconditions:
47  *   key1 and key2 point to "valid" (struct hfs_ext_key)s.
48  * Postconditions:
49  *   This function has no side-effects */
hfs_ext_keycmp(const btree_key * key1,const btree_key * key2)50 int hfs_ext_keycmp(const btree_key *key1, const btree_key *key2)
51 {
52 	__be32 fnum1, fnum2;
53 	__be16 block1, block2;
54 
55 	fnum1 = key1->ext.FNum;
56 	fnum2 = key2->ext.FNum;
57 	if (fnum1 != fnum2)
58 		return be32_to_cpu(fnum1) < be32_to_cpu(fnum2) ? -1 : 1;
59 	if (key1->ext.FkType != key2->ext.FkType)
60 		return key1->ext.FkType < key2->ext.FkType ? -1 : 1;
61 
62 	block1 = key1->ext.FABN;
63 	block2 = key2->ext.FABN;
64 	if (block1 == block2)
65 		return 0;
66 	return be16_to_cpu(block1) < be16_to_cpu(block2) ? -1 : 1;
67 }
68 
69 /*
70  * hfs_ext_find_block
71  *
72  * Find a block within an extent record
73  */
hfs_ext_find_block(struct hfs_extent * ext,u16 off)74 static u16 hfs_ext_find_block(struct hfs_extent *ext, u16 off)
75 {
76 	int i;
77 	u16 count;
78 
79 	for (i = 0; i < 3; ext++, i++) {
80 		count = be16_to_cpu(ext->count);
81 		if (off < count)
82 			return be16_to_cpu(ext->block) + off;
83 		off -= count;
84 	}
85 	/* panic? */
86 	return 0;
87 }
88 
hfs_ext_block_count(struct hfs_extent * ext)89 static int hfs_ext_block_count(struct hfs_extent *ext)
90 {
91 	int i;
92 	u16 count = 0;
93 
94 	for (i = 0; i < 3; ext++, i++)
95 		count += be16_to_cpu(ext->count);
96 	return count;
97 }
98 
hfs_ext_lastblock(struct hfs_extent * ext)99 static u16 hfs_ext_lastblock(struct hfs_extent *ext)
100 {
101 	int i;
102 
103 	ext += 2;
104 	for (i = 0; i < 2; ext--, i++)
105 		if (ext->count)
106 			break;
107 	return be16_to_cpu(ext->block) + be16_to_cpu(ext->count);
108 }
109 
__hfs_ext_write_extent(struct inode * inode,struct hfs_find_data * fd)110 static int __hfs_ext_write_extent(struct inode *inode, struct hfs_find_data *fd)
111 {
112 	int res;
113 
114 	hfs_ext_build_key(fd->search_key, inode->i_ino, HFS_I(inode)->cached_start,
115 			  HFS_IS_RSRC(inode) ?  HFS_FK_RSRC : HFS_FK_DATA);
116 	res = hfs_brec_find(fd);
117 	if (HFS_I(inode)->flags & HFS_FLG_EXT_NEW) {
118 		if (res != -ENOENT)
119 			return res;
120 		/* Fail early and avoid ENOSPC during the btree operation */
121 		res = hfs_bmap_reserve(fd->tree, fd->tree->depth + 1);
122 		if (res)
123 			return res;
124 		hfs_brec_insert(fd, HFS_I(inode)->cached_extents, sizeof(hfs_extent_rec));
125 		HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
126 	} else {
127 		if (res)
128 			return res;
129 		hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
130 		HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
131 	}
132 	return 0;
133 }
134 
hfs_ext_write_extent(struct inode * inode)135 int hfs_ext_write_extent(struct inode *inode)
136 {
137 	struct hfs_find_data fd;
138 	int res = 0;
139 
140 	if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
141 		res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
142 		if (res)
143 			return res;
144 		res = __hfs_ext_write_extent(inode, &fd);
145 		hfs_find_exit(&fd);
146 	}
147 	return res;
148 }
149 
__hfs_ext_read_extent(struct hfs_find_data * fd,struct hfs_extent * extent,u32 cnid,u32 block,u8 type)150 static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent,
151 					u32 cnid, u32 block, u8 type)
152 {
153 	int res;
154 
155 	hfs_ext_build_key(fd->search_key, cnid, block, type);
156 	fd->key->ext.FNum = 0;
157 	res = hfs_brec_find(fd);
158 	if (res && res != -ENOENT)
159 		return res;
160 	if (fd->key->ext.FNum != fd->search_key->ext.FNum ||
161 	    fd->key->ext.FkType != fd->search_key->ext.FkType)
162 		return -ENOENT;
163 	if (fd->entrylength != sizeof(hfs_extent_rec))
164 		return -EIO;
165 	hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
166 	return 0;
167 }
168 
__hfs_ext_cache_extent(struct hfs_find_data * fd,struct inode * inode,u32 block)169 static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
170 {
171 	int res;
172 
173 	if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
174 		res = __hfs_ext_write_extent(inode, fd);
175 		if (res)
176 			return res;
177 	}
178 
179 	res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
180 				    block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
181 	if (!res) {
182 		HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
183 		HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
184 	} else {
185 		HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
186 		HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
187 	}
188 	return res;
189 }
190 
hfs_ext_read_extent(struct inode * inode,u16 block)191 static int hfs_ext_read_extent(struct inode *inode, u16 block)
192 {
193 	struct hfs_find_data fd;
194 	int res;
195 
196 	if (block >= HFS_I(inode)->cached_start &&
197 	    block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
198 		return 0;
199 
200 	res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
201 	if (!res) {
202 		res = __hfs_ext_cache_extent(&fd, inode, block);
203 		hfs_find_exit(&fd);
204 	}
205 	return res;
206 }
207 
hfs_dump_extent(struct hfs_extent * extent)208 static void hfs_dump_extent(struct hfs_extent *extent)
209 {
210 	int i;
211 
212 	hfs_dbg(EXTENT, "   ");
213 	for (i = 0; i < 3; i++)
214 		hfs_dbg_cont(EXTENT, " %u:%u",
215 			     be16_to_cpu(extent[i].block),
216 			     be16_to_cpu(extent[i].count));
217 	hfs_dbg_cont(EXTENT, "\n");
218 }
219 
hfs_add_extent(struct hfs_extent * extent,u16 offset,u16 alloc_block,u16 block_count)220 static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
221 			  u16 alloc_block, u16 block_count)
222 {
223 	u16 count, start;
224 	int i;
225 
226 	hfs_dump_extent(extent);
227 	for (i = 0; i < 3; extent++, i++) {
228 		count = be16_to_cpu(extent->count);
229 		if (offset == count) {
230 			start = be16_to_cpu(extent->block);
231 			if (alloc_block != start + count) {
232 				if (++i >= 3)
233 					return -ENOSPC;
234 				extent++;
235 				extent->block = cpu_to_be16(alloc_block);
236 			} else
237 				block_count += count;
238 			extent->count = cpu_to_be16(block_count);
239 			return 0;
240 		} else if (offset < count)
241 			break;
242 		offset -= count;
243 	}
244 	/* panic? */
245 	return -EIO;
246 }
247 
hfs_free_extents(struct super_block * sb,struct hfs_extent * extent,u16 offset,u16 block_nr)248 static int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent,
249 			    u16 offset, u16 block_nr)
250 {
251 	u16 count, start;
252 	int i;
253 
254 	hfs_dump_extent(extent);
255 	for (i = 0; i < 3; extent++, i++) {
256 		count = be16_to_cpu(extent->count);
257 		if (offset == count)
258 			goto found;
259 		else if (offset < count)
260 			break;
261 		offset -= count;
262 	}
263 	/* panic? */
264 	return -EIO;
265 found:
266 	for (;;) {
267 		start = be16_to_cpu(extent->block);
268 		if (count <= block_nr) {
269 			hfs_clear_vbm_bits(sb, start, count);
270 			extent->block = 0;
271 			extent->count = 0;
272 			block_nr -= count;
273 		} else {
274 			count -= block_nr;
275 			hfs_clear_vbm_bits(sb, start + count, block_nr);
276 			extent->count = cpu_to_be16(count);
277 			block_nr = 0;
278 		}
279 		if (!block_nr || !i)
280 			return 0;
281 		i--;
282 		extent--;
283 		count = be16_to_cpu(extent->count);
284 	}
285 }
286 
hfs_free_fork(struct super_block * sb,struct hfs_cat_file * file,int type)287 int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type)
288 {
289 	struct hfs_find_data fd;
290 	u32 total_blocks, blocks, start;
291 	u32 cnid = be32_to_cpu(file->FlNum);
292 	struct hfs_extent *extent;
293 	int res, i;
294 
295 	if (type == HFS_FK_DATA) {
296 		total_blocks = be32_to_cpu(file->PyLen);
297 		extent = file->ExtRec;
298 	} else {
299 		total_blocks = be32_to_cpu(file->RPyLen);
300 		extent = file->RExtRec;
301 	}
302 	total_blocks /= HFS_SB(sb)->alloc_blksz;
303 	if (!total_blocks)
304 		return 0;
305 
306 	blocks = 0;
307 	for (i = 0; i < 3; i++)
308 		blocks += be16_to_cpu(extent[i].count);
309 
310 	res = hfs_free_extents(sb, extent, blocks, blocks);
311 	if (res)
312 		return res;
313 	if (total_blocks == blocks)
314 		return 0;
315 
316 	res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
317 	if (res)
318 		return res;
319 	do {
320 		res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
321 		if (res)
322 			break;
323 		start = be16_to_cpu(fd.key->ext.FABN);
324 		hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
325 		hfs_brec_remove(&fd);
326 		total_blocks = start;
327 	} while (total_blocks > blocks);
328 	hfs_find_exit(&fd);
329 
330 	return res;
331 }
332 
333 /*
334  * hfs_get_block
335  */
hfs_get_block(struct inode * inode,sector_t block,struct buffer_head * bh_result,int create)336 int hfs_get_block(struct inode *inode, sector_t block,
337 		  struct buffer_head *bh_result, int create)
338 {
339 	struct super_block *sb;
340 	u16 dblock, ablock;
341 	int res;
342 
343 	sb = inode->i_sb;
344 	/* Convert inode block to disk allocation block */
345 	ablock = (u32)block / HFS_SB(sb)->fs_div;
346 
347 	if (block >= HFS_I(inode)->fs_blocks) {
348 		if (!create)
349 			return 0;
350 		if (block > HFS_I(inode)->fs_blocks)
351 			return -EIO;
352 		if (ablock >= HFS_I(inode)->alloc_blocks) {
353 			res = hfs_extend_file(inode);
354 			if (res)
355 				return res;
356 		}
357 	} else
358 		create = 0;
359 
360 	if (ablock < HFS_I(inode)->first_blocks) {
361 		dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
362 		goto done;
363 	}
364 
365 	mutex_lock(&HFS_I(inode)->extents_lock);
366 	res = hfs_ext_read_extent(inode, ablock);
367 	if (!res)
368 		dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
369 					    ablock - HFS_I(inode)->cached_start);
370 	else {
371 		mutex_unlock(&HFS_I(inode)->extents_lock);
372 		return -EIO;
373 	}
374 	mutex_unlock(&HFS_I(inode)->extents_lock);
375 
376 done:
377 	map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
378 	       dblock * HFS_SB(sb)->fs_div +
379 	       (u32)block % HFS_SB(sb)->fs_div);
380 
381 	if (create) {
382 		set_buffer_new(bh_result);
383 		HFS_I(inode)->phys_size += sb->s_blocksize;
384 		HFS_I(inode)->fs_blocks++;
385 		inode_add_bytes(inode, sb->s_blocksize);
386 		mark_inode_dirty(inode);
387 	}
388 	return 0;
389 }
390 
hfs_extend_file(struct inode * inode)391 int hfs_extend_file(struct inode *inode)
392 {
393 	struct super_block *sb = inode->i_sb;
394 	u32 start, len, goal;
395 	int res;
396 
397 	mutex_lock(&HFS_I(inode)->extents_lock);
398 	if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
399 		goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
400 	else {
401 		res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
402 		if (res)
403 			goto out;
404 		goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
405 	}
406 
407 	len = HFS_I(inode)->clump_blocks;
408 	start = hfs_vbm_search_free(sb, goal, &len);
409 	if (!len) {
410 		res = -ENOSPC;
411 		goto out;
412 	}
413 
414 	hfs_dbg(EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
415 	if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
416 		if (!HFS_I(inode)->first_blocks) {
417 			hfs_dbg(EXTENT, "first extents\n");
418 			/* no extents yet */
419 			HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
420 			HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
421 			res = 0;
422 		} else {
423 			/* try to append to extents in inode */
424 			res = hfs_add_extent(HFS_I(inode)->first_extents,
425 					     HFS_I(inode)->alloc_blocks,
426 					     start, len);
427 			if (res == -ENOSPC)
428 				goto insert_extent;
429 		}
430 		if (!res) {
431 			hfs_dump_extent(HFS_I(inode)->first_extents);
432 			HFS_I(inode)->first_blocks += len;
433 		}
434 	} else {
435 		res = hfs_add_extent(HFS_I(inode)->cached_extents,
436 				     HFS_I(inode)->alloc_blocks -
437 				     HFS_I(inode)->cached_start,
438 				     start, len);
439 		if (!res) {
440 			hfs_dump_extent(HFS_I(inode)->cached_extents);
441 			HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
442 			HFS_I(inode)->cached_blocks += len;
443 		} else if (res == -ENOSPC)
444 			goto insert_extent;
445 	}
446 out:
447 	mutex_unlock(&HFS_I(inode)->extents_lock);
448 	if (!res) {
449 		HFS_I(inode)->alloc_blocks += len;
450 		mark_inode_dirty(inode);
451 		if (inode->i_ino < HFS_FIRSTUSER_CNID)
452 			set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
453 		set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
454 		hfs_mark_mdb_dirty(sb);
455 	}
456 	return res;
457 
458 insert_extent:
459 	hfs_dbg(EXTENT, "insert new extent\n");
460 	res = hfs_ext_write_extent(inode);
461 	if (res)
462 		goto out;
463 
464 	memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
465 	HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
466 	HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
467 	hfs_dump_extent(HFS_I(inode)->cached_extents);
468 	HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW;
469 	HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
470 	HFS_I(inode)->cached_blocks = len;
471 
472 	res = 0;
473 	goto out;
474 }
475 
hfs_file_truncate(struct inode * inode)476 void hfs_file_truncate(struct inode *inode)
477 {
478 	struct super_block *sb = inode->i_sb;
479 	struct hfs_find_data fd;
480 	u16 blk_cnt, alloc_cnt, start;
481 	u32 size;
482 	int res;
483 
484 	hfs_dbg(INODE, "truncate: %lu, %Lu -> %Lu\n",
485 		inode->i_ino, (long long)HFS_I(inode)->phys_size,
486 		inode->i_size);
487 	if (inode->i_size > HFS_I(inode)->phys_size) {
488 		struct address_space *mapping = inode->i_mapping;
489 		void *fsdata = NULL;
490 		struct folio *folio;
491 
492 		/* XXX: Can use generic_cont_expand? */
493 		size = inode->i_size - 1;
494 		res = hfs_write_begin(NULL, mapping, size + 1, 0, &folio,
495 				&fsdata);
496 		if (!res) {
497 			res = generic_write_end(NULL, mapping, size + 1, 0, 0,
498 					folio, fsdata);
499 		}
500 		if (res)
501 			inode->i_size = HFS_I(inode)->phys_size;
502 		return;
503 	} else if (inode->i_size == HFS_I(inode)->phys_size)
504 		return;
505 	size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
506 	blk_cnt = size / HFS_SB(sb)->alloc_blksz;
507 	alloc_cnt = HFS_I(inode)->alloc_blocks;
508 	if (blk_cnt == alloc_cnt)
509 		goto out;
510 
511 	mutex_lock(&HFS_I(inode)->extents_lock);
512 	res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
513 	if (res) {
514 		mutex_unlock(&HFS_I(inode)->extents_lock);
515 		/* XXX: We lack error handling of hfs_file_truncate() */
516 		return;
517 	}
518 	while (1) {
519 		if (alloc_cnt == HFS_I(inode)->first_blocks) {
520 			hfs_free_extents(sb, HFS_I(inode)->first_extents,
521 					 alloc_cnt, alloc_cnt - blk_cnt);
522 			hfs_dump_extent(HFS_I(inode)->first_extents);
523 			HFS_I(inode)->first_blocks = blk_cnt;
524 			break;
525 		}
526 		res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
527 		if (res)
528 			break;
529 		start = HFS_I(inode)->cached_start;
530 		hfs_free_extents(sb, HFS_I(inode)->cached_extents,
531 				 alloc_cnt - start, alloc_cnt - blk_cnt);
532 		hfs_dump_extent(HFS_I(inode)->cached_extents);
533 		if (blk_cnt > start) {
534 			HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
535 			break;
536 		}
537 		alloc_cnt = start;
538 		HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
539 		HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
540 		hfs_brec_remove(&fd);
541 	}
542 	hfs_find_exit(&fd);
543 	mutex_unlock(&HFS_I(inode)->extents_lock);
544 
545 	HFS_I(inode)->alloc_blocks = blk_cnt;
546 out:
547 	HFS_I(inode)->phys_size = inode->i_size;
548 	HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
549 	inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
550 	mark_inode_dirty(inode);
551 }
552