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 void __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
;
130 void hfs_ext_write_extent(struct inode
*inode
)
132 struct hfs_find_data fd
;
134 if (HFS_I(inode
)->flags
& HFS_FLG_EXT_DIRTY
) {
135 hfs_find_init(HFS_SB(inode
->i_sb
)->ext_tree
, &fd
);
136 __hfs_ext_write_extent(inode
, &fd
);
141 static inline int __hfs_ext_read_extent(struct hfs_find_data
*fd
, struct hfs_extent
*extent
,
142 u32 cnid
, u32 block
, u8 type
)
146 hfs_ext_build_key(fd
->search_key
, cnid
, block
, type
);
147 fd
->key
->ext
.FNum
= 0;
148 res
= hfs_brec_find(fd
);
149 if (res
&& res
!= -ENOENT
)
151 if (fd
->key
->ext
.FNum
!= fd
->search_key
->ext
.FNum
||
152 fd
->key
->ext
.FkType
!= fd
->search_key
->ext
.FkType
)
154 if (fd
->entrylength
!= sizeof(hfs_extent_rec
))
156 hfs_bnode_read(fd
->bnode
, extent
, fd
->entryoffset
, sizeof(hfs_extent_rec
));
160 static inline int __hfs_ext_cache_extent(struct hfs_find_data
*fd
, struct inode
*inode
, u32 block
)
164 if (HFS_I(inode
)->flags
& HFS_FLG_EXT_DIRTY
)
165 __hfs_ext_write_extent(inode
, fd
);
167 res
= __hfs_ext_read_extent(fd
, HFS_I(inode
)->cached_extents
, inode
->i_ino
,
168 block
, HFS_IS_RSRC(inode
) ? HFS_FK_RSRC
: HFS_FK_DATA
);
170 HFS_I(inode
)->cached_start
= be16_to_cpu(fd
->key
->ext
.FABN
);
171 HFS_I(inode
)->cached_blocks
= hfs_ext_block_count(HFS_I(inode
)->cached_extents
);
173 HFS_I(inode
)->cached_start
= HFS_I(inode
)->cached_blocks
= 0;
174 HFS_I(inode
)->flags
&= ~(HFS_FLG_EXT_DIRTY
|HFS_FLG_EXT_NEW
);
179 static int hfs_ext_read_extent(struct inode
*inode
, u16 block
)
181 struct hfs_find_data fd
;
184 if (block
>= HFS_I(inode
)->cached_start
&&
185 block
< HFS_I(inode
)->cached_start
+ HFS_I(inode
)->cached_blocks
)
188 hfs_find_init(HFS_SB(inode
->i_sb
)->ext_tree
, &fd
);
189 res
= __hfs_ext_cache_extent(&fd
, inode
, block
);
194 static void hfs_dump_extent(struct hfs_extent
*extent
)
198 dprint(DBG_EXTENT
, " ");
199 for (i
= 0; i
< 3; i
++)
200 dprint(DBG_EXTENT
, " %u:%u", be16_to_cpu(extent
[i
].block
),
201 be16_to_cpu(extent
[i
].count
));
202 dprint(DBG_EXTENT
, "\n");
205 static int hfs_add_extent(struct hfs_extent
*extent
, u16 offset
,
206 u16 alloc_block
, u16 block_count
)
211 hfs_dump_extent(extent
);
212 for (i
= 0; i
< 3; extent
++, i
++) {
213 count
= be16_to_cpu(extent
->count
);
214 if (offset
== count
) {
215 start
= be16_to_cpu(extent
->block
);
216 if (alloc_block
!= start
+ count
) {
220 extent
->block
= cpu_to_be16(alloc_block
);
222 block_count
+= count
;
223 extent
->count
= cpu_to_be16(block_count
);
225 } else if (offset
< count
)
233 static int hfs_free_extents(struct super_block
*sb
, struct hfs_extent
*extent
,
234 u16 offset
, u16 block_nr
)
239 hfs_dump_extent(extent
);
240 for (i
= 0; i
< 3; extent
++, i
++) {
241 count
= be16_to_cpu(extent
->count
);
244 else if (offset
< count
)
252 start
= be16_to_cpu(extent
->block
);
253 if (count
<= block_nr
) {
254 hfs_clear_vbm_bits(sb
, start
, count
);
260 hfs_clear_vbm_bits(sb
, start
+ count
, block_nr
);
261 extent
->count
= cpu_to_be16(count
);
268 count
= be16_to_cpu(extent
->count
);
272 int hfs_free_fork(struct super_block
*sb
, struct hfs_cat_file
*file
, int type
)
274 struct hfs_find_data fd
;
275 u32 total_blocks
, blocks
, start
;
276 u32 cnid
= be32_to_cpu(file
->FlNum
);
277 struct hfs_extent
*extent
;
280 if (type
== HFS_FK_DATA
) {
281 total_blocks
= be32_to_cpu(file
->PyLen
);
282 extent
= file
->ExtRec
;
284 total_blocks
= be32_to_cpu(file
->RPyLen
);
285 extent
= file
->RExtRec
;
287 total_blocks
/= HFS_SB(sb
)->alloc_blksz
;
292 for (i
= 0; i
< 3; extent
++, i
++)
293 blocks
+= be16_to_cpu(extent
[i
].count
);
295 res
= hfs_free_extents(sb
, extent
, blocks
, blocks
);
298 if (total_blocks
== blocks
)
301 hfs_find_init(HFS_SB(sb
)->ext_tree
, &fd
);
303 res
= __hfs_ext_read_extent(&fd
, extent
, cnid
, total_blocks
, type
);
306 start
= be16_to_cpu(fd
.key
->ext
.FABN
);
307 hfs_free_extents(sb
, extent
, total_blocks
- start
, total_blocks
);
308 hfs_brec_remove(&fd
);
309 total_blocks
= start
;
310 } while (total_blocks
> blocks
);
319 int hfs_get_block(struct inode
*inode
, sector_t block
,
320 struct buffer_head
*bh_result
, int create
)
322 struct super_block
*sb
;
327 /* Convert inode block to disk allocation block */
328 ablock
= (u32
)block
/ HFS_SB(sb
)->fs_div
;
330 if (block
>= HFS_I(inode
)->fs_blocks
) {
331 if (block
> HFS_I(inode
)->fs_blocks
|| !create
)
333 if (ablock
>= HFS_I(inode
)->alloc_blocks
) {
334 res
= hfs_extend_file(inode
);
341 if (ablock
< HFS_I(inode
)->first_blocks
) {
342 dblock
= hfs_ext_find_block(HFS_I(inode
)->first_extents
, ablock
);
346 mutex_lock(&HFS_I(inode
)->extents_lock
);
347 res
= hfs_ext_read_extent(inode
, ablock
);
349 dblock
= hfs_ext_find_block(HFS_I(inode
)->cached_extents
,
350 ablock
- HFS_I(inode
)->cached_start
);
352 mutex_unlock(&HFS_I(inode
)->extents_lock
);
355 mutex_unlock(&HFS_I(inode
)->extents_lock
);
358 map_bh(bh_result
, sb
, HFS_SB(sb
)->fs_start
+
359 dblock
* HFS_SB(sb
)->fs_div
+
360 (u32
)block
% HFS_SB(sb
)->fs_div
);
363 set_buffer_new(bh_result
);
364 HFS_I(inode
)->phys_size
+= sb
->s_blocksize
;
365 HFS_I(inode
)->fs_blocks
++;
366 inode_add_bytes(inode
, sb
->s_blocksize
);
367 mark_inode_dirty(inode
);
372 int hfs_extend_file(struct inode
*inode
)
374 struct super_block
*sb
= inode
->i_sb
;
375 u32 start
, len
, goal
;
378 mutex_lock(&HFS_I(inode
)->extents_lock
);
379 if (HFS_I(inode
)->alloc_blocks
== HFS_I(inode
)->first_blocks
)
380 goal
= hfs_ext_lastblock(HFS_I(inode
)->first_extents
);
382 res
= hfs_ext_read_extent(inode
, HFS_I(inode
)->alloc_blocks
);
385 goal
= hfs_ext_lastblock(HFS_I(inode
)->cached_extents
);
388 len
= HFS_I(inode
)->clump_blocks
;
389 start
= hfs_vbm_search_free(sb
, goal
, &len
);
395 dprint(DBG_EXTENT
, "extend %lu: %u,%u\n", inode
->i_ino
, start
, len
);
396 if (HFS_I(inode
)->alloc_blocks
== HFS_I(inode
)->first_blocks
) {
397 if (!HFS_I(inode
)->first_blocks
) {
398 dprint(DBG_EXTENT
, "first extents\n");
400 HFS_I(inode
)->first_extents
[0].block
= cpu_to_be16(start
);
401 HFS_I(inode
)->first_extents
[0].count
= cpu_to_be16(len
);
404 /* try to append to extents in inode */
405 res
= hfs_add_extent(HFS_I(inode
)->first_extents
,
406 HFS_I(inode
)->alloc_blocks
,
412 hfs_dump_extent(HFS_I(inode
)->first_extents
);
413 HFS_I(inode
)->first_blocks
+= len
;
416 res
= hfs_add_extent(HFS_I(inode
)->cached_extents
,
417 HFS_I(inode
)->alloc_blocks
-
418 HFS_I(inode
)->cached_start
,
421 hfs_dump_extent(HFS_I(inode
)->cached_extents
);
422 HFS_I(inode
)->flags
|= HFS_FLG_EXT_DIRTY
;
423 HFS_I(inode
)->cached_blocks
+= len
;
424 } else if (res
== -ENOSPC
)
428 mutex_unlock(&HFS_I(inode
)->extents_lock
);
430 HFS_I(inode
)->alloc_blocks
+= len
;
431 mark_inode_dirty(inode
);
432 if (inode
->i_ino
< HFS_FIRSTUSER_CNID
)
433 set_bit(HFS_FLG_ALT_MDB_DIRTY
, &HFS_SB(sb
)->flags
);
434 set_bit(HFS_FLG_MDB_DIRTY
, &HFS_SB(sb
)->flags
);
440 dprint(DBG_EXTENT
, "insert new extent\n");
441 hfs_ext_write_extent(inode
);
443 memset(HFS_I(inode
)->cached_extents
, 0, sizeof(hfs_extent_rec
));
444 HFS_I(inode
)->cached_extents
[0].block
= cpu_to_be16(start
);
445 HFS_I(inode
)->cached_extents
[0].count
= cpu_to_be16(len
);
446 hfs_dump_extent(HFS_I(inode
)->cached_extents
);
447 HFS_I(inode
)->flags
|= HFS_FLG_EXT_DIRTY
|HFS_FLG_EXT_NEW
;
448 HFS_I(inode
)->cached_start
= HFS_I(inode
)->alloc_blocks
;
449 HFS_I(inode
)->cached_blocks
= len
;
455 void hfs_file_truncate(struct inode
*inode
)
457 struct super_block
*sb
= inode
->i_sb
;
458 struct hfs_find_data fd
;
459 u16 blk_cnt
, alloc_cnt
, start
;
463 dprint(DBG_INODE
, "truncate: %lu, %Lu -> %Lu\n", inode
->i_ino
,
464 (long long)HFS_I(inode
)->phys_size
, inode
->i_size
);
465 if (inode
->i_size
> HFS_I(inode
)->phys_size
) {
466 struct address_space
*mapping
= inode
->i_mapping
;
471 /* XXX: Can use generic_cont_expand? */
472 size
= inode
->i_size
- 1;
473 res
= pagecache_write_begin(NULL
, mapping
, size
+1, 0,
474 AOP_FLAG_UNINTERRUPTIBLE
, &page
, &fsdata
);
476 res
= pagecache_write_end(NULL
, mapping
, size
+1, 0, 0,
480 inode
->i_size
= HFS_I(inode
)->phys_size
;
482 } else if (inode
->i_size
== HFS_I(inode
)->phys_size
)
484 size
= inode
->i_size
+ HFS_SB(sb
)->alloc_blksz
- 1;
485 blk_cnt
= size
/ HFS_SB(sb
)->alloc_blksz
;
486 alloc_cnt
= HFS_I(inode
)->alloc_blocks
;
487 if (blk_cnt
== alloc_cnt
)
490 mutex_lock(&HFS_I(inode
)->extents_lock
);
491 hfs_find_init(HFS_SB(sb
)->ext_tree
, &fd
);
493 if (alloc_cnt
== HFS_I(inode
)->first_blocks
) {
494 hfs_free_extents(sb
, HFS_I(inode
)->first_extents
,
495 alloc_cnt
, alloc_cnt
- blk_cnt
);
496 hfs_dump_extent(HFS_I(inode
)->first_extents
);
497 HFS_I(inode
)->first_blocks
= blk_cnt
;
500 res
= __hfs_ext_cache_extent(&fd
, inode
, alloc_cnt
);
503 start
= HFS_I(inode
)->cached_start
;
504 hfs_free_extents(sb
, HFS_I(inode
)->cached_extents
,
505 alloc_cnt
- start
, alloc_cnt
- blk_cnt
);
506 hfs_dump_extent(HFS_I(inode
)->cached_extents
);
507 if (blk_cnt
> start
) {
508 HFS_I(inode
)->flags
|= HFS_FLG_EXT_DIRTY
;
512 HFS_I(inode
)->cached_start
= HFS_I(inode
)->cached_blocks
= 0;
513 HFS_I(inode
)->flags
&= ~(HFS_FLG_EXT_DIRTY
|HFS_FLG_EXT_NEW
);
514 hfs_brec_remove(&fd
);
517 mutex_unlock(&HFS_I(inode
)->extents_lock
);
519 HFS_I(inode
)->alloc_blocks
= blk_cnt
;
521 HFS_I(inode
)->phys_size
= inode
->i_size
;
522 HFS_I(inode
)->fs_blocks
= (inode
->i_size
+ sb
->s_blocksize
- 1) >> sb
->s_blocksize_bits
;
523 inode_set_bytes(inode
, HFS_I(inode
)->fs_blocks
<< sb
->s_blocksize_bits
);
524 mark_inode_dirty(inode
);
This page took 0.041442 seconds and 5 git commands to generate.