2 * linux/fs/hfsplus/extents.c
5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handling of Extents both in catalog and extents overflow trees
11 #include <linux/errno.h>
13 #include <linux/pagemap.h>
15 #include "hfsplus_fs.h"
16 #include "hfsplus_raw.h"
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
)
28 return be32_to_cpu(k1id
) < be32_to_cpu(k2id
) ? -1 : 1;
30 if (k1
->ext
.fork_type
!= k2
->ext
.fork_type
)
31 return k1
->ext
.fork_type
< k2
->ext
.fork_type
? -1 : 1;
33 k1s
= k1
->ext
.start_block
;
34 k2s
= k2
->ext
.start_block
;
37 return be32_to_cpu(k1s
) < be32_to_cpu(k2s
) ? -1 : 1;
40 static void hfsplus_ext_build_key(hfsplus_btree_key
*key
, u32 cnid
,
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
;
50 static u32
hfsplus_ext_find_block(struct hfsplus_extent
*ext
, u32 off
)
55 for (i
= 0; i
< 8; ext
++, i
++) {
56 count
= be32_to_cpu(ext
->block_count
);
58 return be32_to_cpu(ext
->start_block
) + off
;
65 static int hfsplus_ext_block_count(struct hfsplus_extent
*ext
)
70 for (i
= 0; i
< 8; ext
++, i
++)
71 count
+= be32_to_cpu(ext
->block_count
);
75 static u32
hfsplus_ext_lastblock(struct hfsplus_extent
*ext
)
80 for (i
= 0; i
< 7; ext
--, i
++)
83 return be32_to_cpu(ext
->start_block
) + be32_to_cpu(ext
->block_count
);
86 static int __hfsplus_ext_write_extent(struct inode
*inode
,
87 struct hfs_find_data
*fd
)
89 struct hfsplus_inode_info
*hip
= HFSPLUS_I(inode
);
92 WARN_ON(!mutex_is_locked(&hip
->extents_lock
));
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
);
98 res
= hfs_brec_find(fd
, hfs_find_rec_by_key
);
99 if (hip
->extent_state
& HFSPLUS_EXT_NEW
) {
102 hfs_brec_insert(fd
, hip
->cached_extents
,
103 sizeof(hfsplus_extent_rec
));
104 hip
->extent_state
&= ~(HFSPLUS_EXT_DIRTY
| HFSPLUS_EXT_NEW
);
108 hfs_bnode_write(fd
->bnode
, hip
->cached_extents
,
109 fd
->entryoffset
, fd
->entrylength
);
110 hip
->extent_state
&= ~HFSPLUS_EXT_DIRTY
;
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.
119 set_bit(HFSPLUS_I_EXT_DIRTY
, &hip
->flags
);
124 static int hfsplus_ext_write_extent_locked(struct inode
*inode
)
128 if (HFSPLUS_I(inode
)->extent_state
& HFSPLUS_EXT_DIRTY
) {
129 struct hfs_find_data fd
;
131 res
= hfs_find_init(HFSPLUS_SB(inode
->i_sb
)->ext_tree
, &fd
);
134 res
= __hfsplus_ext_write_extent(inode
, &fd
);
140 int hfsplus_ext_write_extent(struct inode
*inode
)
144 mutex_lock(&HFSPLUS_I(inode
)->extents_lock
);
145 res
= hfsplus_ext_write_extent_locked(inode
);
146 mutex_unlock(&HFSPLUS_I(inode
)->extents_lock
);
151 static inline int __hfsplus_ext_read_extent(struct hfs_find_data
*fd
,
152 struct hfsplus_extent
*extent
,
153 u32 cnid
, u32 block
, u8 type
)
157 hfsplus_ext_build_key(fd
->search_key
, cnid
, block
, type
);
158 fd
->key
->ext
.cnid
= 0;
159 res
= hfs_brec_find(fd
, hfs_find_rec_by_key
);
160 if (res
&& res
!= -ENOENT
)
162 if (fd
->key
->ext
.cnid
!= fd
->search_key
->ext
.cnid
||
163 fd
->key
->ext
.fork_type
!= fd
->search_key
->ext
.fork_type
)
165 if (fd
->entrylength
!= sizeof(hfsplus_extent_rec
))
167 hfs_bnode_read(fd
->bnode
, extent
, fd
->entryoffset
,
168 sizeof(hfsplus_extent_rec
));
172 static inline int __hfsplus_ext_cache_extent(struct hfs_find_data
*fd
,
173 struct inode
*inode
, u32 block
)
175 struct hfsplus_inode_info
*hip
= HFSPLUS_I(inode
);
178 WARN_ON(!mutex_is_locked(&hip
->extents_lock
));
180 if (hip
->extent_state
& HFSPLUS_EXT_DIRTY
) {
181 res
= __hfsplus_ext_write_extent(inode
, fd
);
186 res
= __hfsplus_ext_read_extent(fd
, hip
->cached_extents
, inode
->i_ino
,
187 block
, HFSPLUS_IS_RSRC(inode
) ?
191 hip
->cached_start
= be32_to_cpu(fd
->key
->ext
.start_block
);
193 hfsplus_ext_block_count(hip
->cached_extents
);
195 hip
->cached_start
= hip
->cached_blocks
= 0;
196 hip
->extent_state
&= ~(HFSPLUS_EXT_DIRTY
| HFSPLUS_EXT_NEW
);
201 static int hfsplus_ext_read_extent(struct inode
*inode
, u32 block
)
203 struct hfsplus_inode_info
*hip
= HFSPLUS_I(inode
);
204 struct hfs_find_data fd
;
207 if (block
>= hip
->cached_start
&&
208 block
< hip
->cached_start
+ hip
->cached_blocks
)
211 res
= hfs_find_init(HFSPLUS_SB(inode
->i_sb
)->ext_tree
, &fd
);
213 res
= __hfsplus_ext_cache_extent(&fd
, inode
, block
);
219 /* Get a block at iblock for inode, possibly allocating if create */
220 int hfsplus_get_block(struct inode
*inode
, sector_t iblock
,
221 struct buffer_head
*bh_result
, int create
)
223 struct super_block
*sb
= inode
->i_sb
;
224 struct hfsplus_sb_info
*sbi
= HFSPLUS_SB(sb
);
225 struct hfsplus_inode_info
*hip
= HFSPLUS_I(inode
);
227 u32 ablock
, dblock
, mask
;
232 /* Convert inode block to disk allocation block */
233 shift
= sbi
->alloc_blksz_shift
- sb
->s_blocksize_bits
;
234 ablock
= iblock
>> sbi
->fs_shift
;
236 if (iblock
>= hip
->fs_blocks
) {
237 if (iblock
> hip
->fs_blocks
|| !create
)
239 if (ablock
>= hip
->alloc_blocks
) {
240 res
= hfsplus_file_extend(inode
);
247 if (ablock
< hip
->first_blocks
) {
248 dblock
= hfsplus_ext_find_block(hip
->first_extents
, ablock
);
252 if (inode
->i_ino
== HFSPLUS_EXT_CNID
)
255 mutex_lock(&hip
->extents_lock
);
258 * hfsplus_ext_read_extent will write out a cached extent into
259 * the extents btree. In that case we may have to mark the inode
260 * dirty even for a pure read of an extent here.
262 was_dirty
= (hip
->extent_state
& HFSPLUS_EXT_DIRTY
);
263 res
= hfsplus_ext_read_extent(inode
, ablock
);
265 mutex_unlock(&hip
->extents_lock
);
268 dblock
= hfsplus_ext_find_block(hip
->cached_extents
,
269 ablock
- hip
->cached_start
);
270 mutex_unlock(&hip
->extents_lock
);
273 hfs_dbg(EXTENT
, "get_block(%lu): %llu - %u\n",
274 inode
->i_ino
, (long long)iblock
, dblock
);
276 mask
= (1 << sbi
->fs_shift
) - 1;
277 sector
= ((sector_t
)dblock
<< sbi
->fs_shift
) +
278 sbi
->blockoffset
+ (iblock
& mask
);
279 map_bh(bh_result
, sb
, sector
);
282 set_buffer_new(bh_result
);
283 hip
->phys_size
+= sb
->s_blocksize
;
285 inode_add_bytes(inode
, sb
->s_blocksize
);
287 if (create
|| was_dirty
)
288 mark_inode_dirty(inode
);
292 static void hfsplus_dump_extent(struct hfsplus_extent
*extent
)
296 hfs_dbg(EXTENT
, " ");
297 for (i
= 0; i
< 8; i
++)
298 hfs_dbg_cont(EXTENT
, " %u:%u",
299 be32_to_cpu(extent
[i
].start_block
),
300 be32_to_cpu(extent
[i
].block_count
));
301 hfs_dbg_cont(EXTENT
, "\n");
304 static int hfsplus_add_extent(struct hfsplus_extent
*extent
, u32 offset
,
305 u32 alloc_block
, u32 block_count
)
310 hfsplus_dump_extent(extent
);
311 for (i
= 0; i
< 8; extent
++, i
++) {
312 count
= be32_to_cpu(extent
->block_count
);
313 if (offset
== count
) {
314 start
= be32_to_cpu(extent
->start_block
);
315 if (alloc_block
!= start
+ count
) {
319 extent
->start_block
= cpu_to_be32(alloc_block
);
321 block_count
+= count
;
322 extent
->block_count
= cpu_to_be32(block_count
);
324 } else if (offset
< count
)
332 static int hfsplus_free_extents(struct super_block
*sb
,
333 struct hfsplus_extent
*extent
,
334 u32 offset
, u32 block_nr
)
340 hfsplus_dump_extent(extent
);
341 for (i
= 0; i
< 8; extent
++, i
++) {
342 count
= be32_to_cpu(extent
->block_count
);
345 else if (offset
< count
)
353 start
= be32_to_cpu(extent
->start_block
);
354 if (count
<= block_nr
) {
355 err
= hfsplus_block_free(sb
, start
, count
);
357 pr_err("can't free extent\n");
358 hfs_dbg(EXTENT
, " start: %u count: %u\n",
361 extent
->block_count
= 0;
362 extent
->start_block
= 0;
366 err
= hfsplus_block_free(sb
, start
+ count
, block_nr
);
368 pr_err("can't free extent\n");
369 hfs_dbg(EXTENT
, " start: %u count: %u\n",
372 extent
->block_count
= cpu_to_be32(count
);
375 if (!block_nr
|| !i
) {
377 * Try to free all extents and
378 * return only last error
384 count
= be32_to_cpu(extent
->block_count
);
388 int hfsplus_free_fork(struct super_block
*sb
, u32 cnid
,
389 struct hfsplus_fork_raw
*fork
, int type
)
391 struct hfs_find_data fd
;
392 hfsplus_extent_rec ext_entry
;
393 u32 total_blocks
, blocks
, start
;
396 total_blocks
= be32_to_cpu(fork
->total_blocks
);
401 for (i
= 0; i
< 8; i
++)
402 blocks
+= be32_to_cpu(fork
->extents
[i
].block_count
);
404 res
= hfsplus_free_extents(sb
, fork
->extents
, blocks
, blocks
);
407 if (total_blocks
== blocks
)
410 res
= hfs_find_init(HFSPLUS_SB(sb
)->ext_tree
, &fd
);
414 res
= __hfsplus_ext_read_extent(&fd
, ext_entry
, cnid
,
418 start
= be32_to_cpu(fd
.key
->ext
.start_block
);
419 hfsplus_free_extents(sb
, ext_entry
,
420 total_blocks
- start
,
422 hfs_brec_remove(&fd
);
423 total_blocks
= start
;
424 } while (total_blocks
> blocks
);
430 int hfsplus_file_extend(struct inode
*inode
)
432 struct super_block
*sb
= inode
->i_sb
;
433 struct hfsplus_sb_info
*sbi
= HFSPLUS_SB(sb
);
434 struct hfsplus_inode_info
*hip
= HFSPLUS_I(inode
);
435 u32 start
, len
, goal
;
438 if (sbi
->alloc_file
->i_size
* 8 <
439 sbi
->total_blocks
- sbi
->free_blocks
+ 8) {
440 /* extend alloc file */
441 pr_err("extend alloc file! "
443 sbi
->alloc_file
->i_size
* 8,
444 sbi
->total_blocks
, sbi
->free_blocks
);
448 mutex_lock(&hip
->extents_lock
);
449 if (hip
->alloc_blocks
== hip
->first_blocks
)
450 goal
= hfsplus_ext_lastblock(hip
->first_extents
);
452 res
= hfsplus_ext_read_extent(inode
, hip
->alloc_blocks
);
455 goal
= hfsplus_ext_lastblock(hip
->cached_extents
);
458 len
= hip
->clump_blocks
;
459 start
= hfsplus_block_allocate(sb
, sbi
->total_blocks
, goal
, &len
);
460 if (start
>= sbi
->total_blocks
) {
461 start
= hfsplus_block_allocate(sb
, goal
, 0, &len
);
468 hfs_dbg(EXTENT
, "extend %lu: %u,%u\n", inode
->i_ino
, start
, len
);
470 if (hip
->alloc_blocks
<= hip
->first_blocks
) {
471 if (!hip
->first_blocks
) {
472 hfs_dbg(EXTENT
, "first extents\n");
474 hip
->first_extents
[0].start_block
= cpu_to_be32(start
);
475 hip
->first_extents
[0].block_count
= cpu_to_be32(len
);
478 /* try to append to extents in inode */
479 res
= hfsplus_add_extent(hip
->first_extents
,
486 hfsplus_dump_extent(hip
->first_extents
);
487 hip
->first_blocks
+= len
;
490 res
= hfsplus_add_extent(hip
->cached_extents
,
491 hip
->alloc_blocks
- hip
->cached_start
,
494 hfsplus_dump_extent(hip
->cached_extents
);
495 hip
->extent_state
|= HFSPLUS_EXT_DIRTY
;
496 hip
->cached_blocks
+= len
;
497 } else if (res
== -ENOSPC
)
501 mutex_unlock(&hip
->extents_lock
);
503 hip
->alloc_blocks
+= len
;
504 hfsplus_mark_inode_dirty(inode
, HFSPLUS_I_ALLOC_DIRTY
);
509 hfs_dbg(EXTENT
, "insert new extent\n");
510 res
= hfsplus_ext_write_extent_locked(inode
);
514 memset(hip
->cached_extents
, 0, sizeof(hfsplus_extent_rec
));
515 hip
->cached_extents
[0].start_block
= cpu_to_be32(start
);
516 hip
->cached_extents
[0].block_count
= cpu_to_be32(len
);
517 hfsplus_dump_extent(hip
->cached_extents
);
518 hip
->extent_state
|= HFSPLUS_EXT_DIRTY
| HFSPLUS_EXT_NEW
;
519 hip
->cached_start
= hip
->alloc_blocks
;
520 hip
->cached_blocks
= len
;
526 void hfsplus_file_truncate(struct inode
*inode
)
528 struct super_block
*sb
= inode
->i_sb
;
529 struct hfsplus_inode_info
*hip
= HFSPLUS_I(inode
);
530 struct hfs_find_data fd
;
531 u32 alloc_cnt
, blk_cnt
, start
;
534 hfs_dbg(INODE
, "truncate: %lu, %llu -> %llu\n",
535 inode
->i_ino
, (long long)hip
->phys_size
, inode
->i_size
);
537 if (inode
->i_size
> hip
->phys_size
) {
538 struct address_space
*mapping
= inode
->i_mapping
;
541 loff_t size
= inode
->i_size
;
543 res
= pagecache_write_begin(NULL
, mapping
, size
, 0,
544 AOP_FLAG_UNINTERRUPTIBLE
,
548 res
= pagecache_write_end(NULL
, mapping
, size
,
552 mark_inode_dirty(inode
);
554 } else if (inode
->i_size
== hip
->phys_size
)
557 blk_cnt
= (inode
->i_size
+ HFSPLUS_SB(sb
)->alloc_blksz
- 1) >>
558 HFSPLUS_SB(sb
)->alloc_blksz_shift
;
559 alloc_cnt
= hip
->alloc_blocks
;
560 if (blk_cnt
== alloc_cnt
)
563 mutex_lock(&hip
->extents_lock
);
564 res
= hfs_find_init(HFSPLUS_SB(sb
)->ext_tree
, &fd
);
566 mutex_unlock(&hip
->extents_lock
);
567 /* XXX: We lack error handling of hfsplus_file_truncate() */
571 if (alloc_cnt
== hip
->first_blocks
) {
572 hfsplus_free_extents(sb
, hip
->first_extents
,
573 alloc_cnt
, alloc_cnt
- blk_cnt
);
574 hfsplus_dump_extent(hip
->first_extents
);
575 hip
->first_blocks
= blk_cnt
;
578 res
= __hfsplus_ext_cache_extent(&fd
, inode
, alloc_cnt
);
581 start
= hip
->cached_start
;
582 hfsplus_free_extents(sb
, hip
->cached_extents
,
583 alloc_cnt
- start
, alloc_cnt
- blk_cnt
);
584 hfsplus_dump_extent(hip
->cached_extents
);
585 if (blk_cnt
> start
) {
586 hip
->extent_state
|= HFSPLUS_EXT_DIRTY
;
590 hip
->cached_start
= hip
->cached_blocks
= 0;
591 hip
->extent_state
&= ~(HFSPLUS_EXT_DIRTY
| HFSPLUS_EXT_NEW
);
592 hfs_brec_remove(&fd
);
595 mutex_unlock(&hip
->extents_lock
);
597 hip
->alloc_blocks
= blk_cnt
;
599 hip
->phys_size
= inode
->i_size
;
600 hip
->fs_blocks
= (inode
->i_size
+ sb
->s_blocksize
- 1) >>
601 sb
->s_blocksize_bits
;
602 inode_set_bytes(inode
, hip
->fs_blocks
<< sb
->s_blocksize_bits
);
603 hfsplus_mark_inode_dirty(inode
, HFSPLUS_I_ALLOC_DIRTY
);