xref: /openbmc/linux/fs/hfs/extent.c (revision d28a1de5)
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   */
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 */
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   */
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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   */
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  
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  
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;
490  		struct page *page;
491  
492  		/* XXX: Can use generic_cont_expand? */
493  		size = inode->i_size - 1;
494  		res = hfs_write_begin(NULL, mapping, size + 1, 0, &page,
495  				&fsdata);
496  		if (!res) {
497  			res = generic_write_end(NULL, mapping, size + 1, 0, 0,
498  					page, 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