2 * linux/fs/hfs/extent.c
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.
8 * This file contains the functions related to the extents B-tree.
11 #include <linux/pagemap.h>
16 /*================ File-local functions ================*/
21 static void hfs_ext_build_key(hfs_btree_key
*key
, u32 cnid
, u16 block
, u8 type
)
24 key
->ext
.FkType
= type
;
25 key
->ext
.FNum
= cpu_to_be32(cnid
);
26 key
->ext
.FABN
= cpu_to_be16(block
);
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).
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
45 * int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
47 * key1 and key2 point to "valid" (struct hfs_ext_key)s.
49 * This function has no side-effects */
50 int hfs_ext_keycmp(const btree_key
*key1
, const btree_key
*key2
)
53 __be16 block1
, block2
;
55 fnum1
= key1
->ext
.FNum
;
56 fnum2
= key2
->ext
.FNum
;
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;
62 block1
= key1
->ext
.FABN
;
63 block2
= key2
->ext
.FABN
;
66 return be16_to_cpu(block1
) < be16_to_cpu(block2
) ? -1 : 1;
72 * Find a block within an extent record
74 static u16
hfs_ext_find_block(struct hfs_extent
*ext
, u16 off
)
79 for (i
= 0; i
< 3; ext
++, i
++) {
80 count
= be16_to_cpu(ext
->count
);
82 return be16_to_cpu(ext
->block
) + off
;
89 static int hfs_ext_block_count(struct hfs_extent
*ext
)
94 for (i
= 0; i
< 3; ext
++, i
++)
95 count
+= be16_to_cpu(ext
->count
);
99 static u16
hfs_ext_lastblock(struct hfs_extent
*ext
)
104 for (i
= 0; i
< 2; ext
--, i
++)
107 return be16_to_cpu(ext
->block
) + be16_to_cpu(ext
->count
);
110 static int __hfs_ext_write_extent(struct inode
*inode
, struct hfs_find_data
*fd
)
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
) {
120 hfs_brec_insert(fd
, HFS_I(inode
)->cached_extents
, sizeof(hfs_extent_rec
));
121 HFS_I(inode
)->flags
&= ~(HFS_FLG_EXT_DIRTY
|HFS_FLG_EXT_NEW
);
125 hfs_bnode_write(fd
->bnode
, HFS_I(inode
)->cached_extents
, fd
->entryoffset
, fd
->entrylength
);
126 HFS_I(inode
)->flags
&= ~HFS_FLG_EXT_DIRTY
;
131 int hfs_ext_write_extent(struct inode
*inode
)
133 struct hfs_find_data fd
;
136 if (HFS_I(inode
)->flags
& HFS_FLG_EXT_DIRTY
) {
137 res
= hfs_find_init(HFS_SB(inode
->i_sb
)->ext_tree
, &fd
);
140 res
= __hfs_ext_write_extent(inode
, &fd
);
146 static inline int __hfs_ext_read_extent(struct hfs_find_data
*fd
, struct hfs_extent
*extent
,
147 u32 cnid
, u32 block
, u8 type
)
151 hfs_ext_build_key(fd
->search_key
, cnid
, block
, type
);
152 fd
->key
->ext
.FNum
= 0;
153 res
= hfs_brec_find(fd
);
154 if (res
&& res
!= -ENOENT
)
156 if (fd
->key
->ext
.FNum
!= fd
->search_key
->ext
.FNum
||
157 fd
->key
->ext
.FkType
!= fd
->search_key
->ext
.FkType
)
159 if (fd
->entrylength
!= sizeof(hfs_extent_rec
))
161 hfs_bnode_read(fd
->bnode
, extent
, fd
->entryoffset
, sizeof(hfs_extent_rec
));
165 static inline int __hfs_ext_cache_extent(struct hfs_find_data
*fd
, struct inode
*inode
, u32 block
)
169 if (HFS_I(inode
)->flags
& HFS_FLG_EXT_DIRTY
) {
170 res
= __hfs_ext_write_extent(inode
, fd
);
175 res
= __hfs_ext_read_extent(fd
, HFS_I(inode
)->cached_extents
, inode
->i_ino
,
176 block
, HFS_IS_RSRC(inode
) ? HFS_FK_RSRC
: HFS_FK_DATA
);
178 HFS_I(inode
)->cached_start
= be16_to_cpu(fd
->key
->ext
.FABN
);
179 HFS_I(inode
)->cached_blocks
= hfs_ext_block_count(HFS_I(inode
)->cached_extents
);
181 HFS_I(inode
)->cached_start
= HFS_I(inode
)->cached_blocks
= 0;
182 HFS_I(inode
)->flags
&= ~(HFS_FLG_EXT_DIRTY
|HFS_FLG_EXT_NEW
);
187 static int hfs_ext_read_extent(struct inode
*inode
, u16 block
)
189 struct hfs_find_data fd
;
192 if (block
>= HFS_I(inode
)->cached_start
&&
193 block
< HFS_I(inode
)->cached_start
+ HFS_I(inode
)->cached_blocks
)
196 res
= hfs_find_init(HFS_SB(inode
->i_sb
)->ext_tree
, &fd
);
198 res
= __hfs_ext_cache_extent(&fd
, inode
, block
);
204 static void hfs_dump_extent(struct hfs_extent
*extent
)
208 hfs_dbg(EXTENT
, " ");
209 for (i
= 0; i
< 3; i
++)
210 hfs_dbg_cont(EXTENT
, " %u:%u",
211 be16_to_cpu(extent
[i
].block
),
212 be16_to_cpu(extent
[i
].count
));
213 hfs_dbg_cont(EXTENT
, "\n");
216 static int hfs_add_extent(struct hfs_extent
*extent
, u16 offset
,
217 u16 alloc_block
, u16 block_count
)
222 hfs_dump_extent(extent
);
223 for (i
= 0; i
< 3; extent
++, i
++) {
224 count
= be16_to_cpu(extent
->count
);
225 if (offset
== count
) {
226 start
= be16_to_cpu(extent
->block
);
227 if (alloc_block
!= start
+ count
) {
231 extent
->block
= cpu_to_be16(alloc_block
);
233 block_count
+= count
;
234 extent
->count
= cpu_to_be16(block_count
);
236 } else if (offset
< count
)
244 static int hfs_free_extents(struct super_block
*sb
, struct hfs_extent
*extent
,
245 u16 offset
, u16 block_nr
)
250 hfs_dump_extent(extent
);
251 for (i
= 0; i
< 3; extent
++, i
++) {
252 count
= be16_to_cpu(extent
->count
);
255 else if (offset
< count
)
263 start
= be16_to_cpu(extent
->block
);
264 if (count
<= block_nr
) {
265 hfs_clear_vbm_bits(sb
, start
, count
);
271 hfs_clear_vbm_bits(sb
, start
+ count
, block_nr
);
272 extent
->count
= cpu_to_be16(count
);
279 count
= be16_to_cpu(extent
->count
);
283 int hfs_free_fork(struct super_block
*sb
, struct hfs_cat_file
*file
, int type
)
285 struct hfs_find_data fd
;
286 u32 total_blocks
, blocks
, start
;
287 u32 cnid
= be32_to_cpu(file
->FlNum
);
288 struct hfs_extent
*extent
;
291 if (type
== HFS_FK_DATA
) {
292 total_blocks
= be32_to_cpu(file
->PyLen
);
293 extent
= file
->ExtRec
;
295 total_blocks
= be32_to_cpu(file
->RPyLen
);
296 extent
= file
->RExtRec
;
298 total_blocks
/= HFS_SB(sb
)->alloc_blksz
;
303 for (i
= 0; i
< 3; extent
++, i
++)
304 blocks
+= be16_to_cpu(extent
[i
].count
);
306 res
= hfs_free_extents(sb
, extent
, blocks
, blocks
);
309 if (total_blocks
== blocks
)
312 res
= hfs_find_init(HFS_SB(sb
)->ext_tree
, &fd
);
316 res
= __hfs_ext_read_extent(&fd
, extent
, cnid
, total_blocks
, type
);
319 start
= be16_to_cpu(fd
.key
->ext
.FABN
);
320 hfs_free_extents(sb
, extent
, total_blocks
- start
, total_blocks
);
321 hfs_brec_remove(&fd
);
322 total_blocks
= start
;
323 } while (total_blocks
> blocks
);
332 int hfs_get_block(struct inode
*inode
, sector_t block
,
333 struct buffer_head
*bh_result
, int create
)
335 struct super_block
*sb
;
340 /* Convert inode block to disk allocation block */
341 ablock
= (u32
)block
/ HFS_SB(sb
)->fs_div
;
343 if (block
>= HFS_I(inode
)->fs_blocks
) {
344 if (block
> HFS_I(inode
)->fs_blocks
|| !create
)
346 if (ablock
>= HFS_I(inode
)->alloc_blocks
) {
347 res
= hfs_extend_file(inode
);
354 if (ablock
< HFS_I(inode
)->first_blocks
) {
355 dblock
= hfs_ext_find_block(HFS_I(inode
)->first_extents
, ablock
);
359 mutex_lock(&HFS_I(inode
)->extents_lock
);
360 res
= hfs_ext_read_extent(inode
, ablock
);
362 dblock
= hfs_ext_find_block(HFS_I(inode
)->cached_extents
,
363 ablock
- HFS_I(inode
)->cached_start
);
365 mutex_unlock(&HFS_I(inode
)->extents_lock
);
368 mutex_unlock(&HFS_I(inode
)->extents_lock
);
371 map_bh(bh_result
, sb
, HFS_SB(sb
)->fs_start
+
372 dblock
* HFS_SB(sb
)->fs_div
+
373 (u32
)block
% HFS_SB(sb
)->fs_div
);
376 set_buffer_new(bh_result
);
377 HFS_I(inode
)->phys_size
+= sb
->s_blocksize
;
378 HFS_I(inode
)->fs_blocks
++;
379 inode_add_bytes(inode
, sb
->s_blocksize
);
380 mark_inode_dirty(inode
);
385 int hfs_extend_file(struct inode
*inode
)
387 struct super_block
*sb
= inode
->i_sb
;
388 u32 start
, len
, goal
;
391 mutex_lock(&HFS_I(inode
)->extents_lock
);
392 if (HFS_I(inode
)->alloc_blocks
== HFS_I(inode
)->first_blocks
)
393 goal
= hfs_ext_lastblock(HFS_I(inode
)->first_extents
);
395 res
= hfs_ext_read_extent(inode
, HFS_I(inode
)->alloc_blocks
);
398 goal
= hfs_ext_lastblock(HFS_I(inode
)->cached_extents
);
401 len
= HFS_I(inode
)->clump_blocks
;
402 start
= hfs_vbm_search_free(sb
, goal
, &len
);
408 hfs_dbg(EXTENT
, "extend %lu: %u,%u\n", inode
->i_ino
, start
, len
);
409 if (HFS_I(inode
)->alloc_blocks
== HFS_I(inode
)->first_blocks
) {
410 if (!HFS_I(inode
)->first_blocks
) {
411 hfs_dbg(EXTENT
, "first extents\n");
413 HFS_I(inode
)->first_extents
[0].block
= cpu_to_be16(start
);
414 HFS_I(inode
)->first_extents
[0].count
= cpu_to_be16(len
);
417 /* try to append to extents in inode */
418 res
= hfs_add_extent(HFS_I(inode
)->first_extents
,
419 HFS_I(inode
)->alloc_blocks
,
425 hfs_dump_extent(HFS_I(inode
)->first_extents
);
426 HFS_I(inode
)->first_blocks
+= len
;
429 res
= hfs_add_extent(HFS_I(inode
)->cached_extents
,
430 HFS_I(inode
)->alloc_blocks
-
431 HFS_I(inode
)->cached_start
,
434 hfs_dump_extent(HFS_I(inode
)->cached_extents
);
435 HFS_I(inode
)->flags
|= HFS_FLG_EXT_DIRTY
;
436 HFS_I(inode
)->cached_blocks
+= len
;
437 } else if (res
== -ENOSPC
)
441 mutex_unlock(&HFS_I(inode
)->extents_lock
);
443 HFS_I(inode
)->alloc_blocks
+= len
;
444 mark_inode_dirty(inode
);
445 if (inode
->i_ino
< HFS_FIRSTUSER_CNID
)
446 set_bit(HFS_FLG_ALT_MDB_DIRTY
, &HFS_SB(sb
)->flags
);
447 set_bit(HFS_FLG_MDB_DIRTY
, &HFS_SB(sb
)->flags
);
448 hfs_mark_mdb_dirty(sb
);
453 hfs_dbg(EXTENT
, "insert new extent\n");
454 res
= hfs_ext_write_extent(inode
);
458 memset(HFS_I(inode
)->cached_extents
, 0, sizeof(hfs_extent_rec
));
459 HFS_I(inode
)->cached_extents
[0].block
= cpu_to_be16(start
);
460 HFS_I(inode
)->cached_extents
[0].count
= cpu_to_be16(len
);
461 hfs_dump_extent(HFS_I(inode
)->cached_extents
);
462 HFS_I(inode
)->flags
|= HFS_FLG_EXT_DIRTY
|HFS_FLG_EXT_NEW
;
463 HFS_I(inode
)->cached_start
= HFS_I(inode
)->alloc_blocks
;
464 HFS_I(inode
)->cached_blocks
= len
;
470 void hfs_file_truncate(struct inode
*inode
)
472 struct super_block
*sb
= inode
->i_sb
;
473 struct hfs_find_data fd
;
474 u16 blk_cnt
, alloc_cnt
, start
;
478 hfs_dbg(INODE
, "truncate: %lu, %Lu -> %Lu\n",
479 inode
->i_ino
, (long long)HFS_I(inode
)->phys_size
,
481 if (inode
->i_size
> HFS_I(inode
)->phys_size
) {
482 struct address_space
*mapping
= inode
->i_mapping
;
486 /* XXX: Can use generic_cont_expand? */
487 size
= inode
->i_size
- 1;
488 res
= pagecache_write_begin(NULL
, mapping
, size
+1, 0,
489 AOP_FLAG_UNINTERRUPTIBLE
, &page
, &fsdata
);
491 res
= pagecache_write_end(NULL
, mapping
, size
+1, 0, 0,
495 inode
->i_size
= HFS_I(inode
)->phys_size
;
497 } else if (inode
->i_size
== HFS_I(inode
)->phys_size
)
499 size
= inode
->i_size
+ HFS_SB(sb
)->alloc_blksz
- 1;
500 blk_cnt
= size
/ HFS_SB(sb
)->alloc_blksz
;
501 alloc_cnt
= HFS_I(inode
)->alloc_blocks
;
502 if (blk_cnt
== alloc_cnt
)
505 mutex_lock(&HFS_I(inode
)->extents_lock
);
506 res
= hfs_find_init(HFS_SB(sb
)->ext_tree
, &fd
);
508 mutex_unlock(&HFS_I(inode
)->extents_lock
);
509 /* XXX: We lack error handling of hfs_file_truncate() */
513 if (alloc_cnt
== HFS_I(inode
)->first_blocks
) {
514 hfs_free_extents(sb
, HFS_I(inode
)->first_extents
,
515 alloc_cnt
, alloc_cnt
- blk_cnt
);
516 hfs_dump_extent(HFS_I(inode
)->first_extents
);
517 HFS_I(inode
)->first_blocks
= blk_cnt
;
520 res
= __hfs_ext_cache_extent(&fd
, inode
, alloc_cnt
);
523 start
= HFS_I(inode
)->cached_start
;
524 hfs_free_extents(sb
, HFS_I(inode
)->cached_extents
,
525 alloc_cnt
- start
, alloc_cnt
- blk_cnt
);
526 hfs_dump_extent(HFS_I(inode
)->cached_extents
);
527 if (blk_cnt
> start
) {
528 HFS_I(inode
)->flags
|= HFS_FLG_EXT_DIRTY
;
532 HFS_I(inode
)->cached_start
= HFS_I(inode
)->cached_blocks
= 0;
533 HFS_I(inode
)->flags
&= ~(HFS_FLG_EXT_DIRTY
|HFS_FLG_EXT_NEW
);
534 hfs_brec_remove(&fd
);
537 mutex_unlock(&HFS_I(inode
)->extents_lock
);
539 HFS_I(inode
)->alloc_blocks
= blk_cnt
;
541 HFS_I(inode
)->phys_size
= inode
->i_size
;
542 HFS_I(inode
)->fs_blocks
= (inode
->i_size
+ sb
->s_blocksize
- 1) >> sb
->s_blocksize_bits
;
543 inode_set_bytes(inode
, HFS_I(inode
)->fs_blocks
<< sb
->s_blocksize_bits
);
544 mark_inode_dirty(inode
);
This page took 0.0427 seconds and 6 git commands to generate.