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 void __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;
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);
122 } else {
123 if (res)
124 return;
125 hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
126 HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
127 }
128 }
129
hfs_ext_write_extent(struct inode * inode)130 void hfs_ext_write_extent(struct inode *inode)
131 {
132 struct hfs_find_data fd;
133
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);
137 hfs_find_exit(&fd);
138 }
139 }
140
__hfs_ext_read_extent(struct hfs_find_data * fd,struct hfs_extent * extent,u32 cnid,u32 block,u8 type)141 static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent,
142 u32 cnid, u32 block, u8 type)
143 {
144 int res;
145
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)
150 return res;
151 if (fd->key->ext.FNum != fd->search_key->ext.FNum ||
152 fd->key->ext.FkType != fd->search_key->ext.FkType)
153 return -ENOENT;
154 if (fd->entrylength != sizeof(hfs_extent_rec))
155 return -EIO;
156 hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
157 return 0;
158 }
159
__hfs_ext_cache_extent(struct hfs_find_data * fd,struct inode * inode,u32 block)160 static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
161 {
162 int res;
163
164 if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY)
165 __hfs_ext_write_extent(inode, fd);
166
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);
169 if (!res) {
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);
172 } else {
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);
175 }
176 return res;
177 }
178
hfs_ext_read_extent(struct inode * inode,u16 block)179 static int hfs_ext_read_extent(struct inode *inode, u16 block)
180 {
181 struct hfs_find_data fd;
182 int res;
183
184 if (block >= HFS_I(inode)->cached_start &&
185 block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
186 return 0;
187
188 hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
189 res = __hfs_ext_cache_extent(&fd, inode, block);
190 hfs_find_exit(&fd);
191 return res;
192 }
193
hfs_dump_extent(struct hfs_extent * extent)194 static void hfs_dump_extent(struct hfs_extent *extent)
195 {
196 int i;
197
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");
203 }
204
hfs_add_extent(struct hfs_extent * extent,u16 offset,u16 alloc_block,u16 block_count)205 static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
206 u16 alloc_block, u16 block_count)
207 {
208 u16 count, start;
209 int i;
210
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) {
217 if (++i >= 3)
218 return -ENOSPC;
219 extent++;
220 extent->block = cpu_to_be16(alloc_block);
221 } else
222 block_count += count;
223 extent->count = cpu_to_be16(block_count);
224 return 0;
225 } else if (offset < count)
226 break;
227 offset -= count;
228 }
229 /* panic? */
230 return -EIO;
231 }
232
hfs_free_extents(struct super_block * sb,struct hfs_extent * extent,u16 offset,u16 block_nr)233 static int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent,
234 u16 offset, u16 block_nr)
235 {
236 u16 count, start;
237 int i;
238
239 hfs_dump_extent(extent);
240 for (i = 0; i < 3; extent++, i++) {
241 count = be16_to_cpu(extent->count);
242 if (offset == count)
243 goto found;
244 else if (offset < count)
245 break;
246 offset -= count;
247 }
248 /* panic? */
249 return -EIO;
250 found:
251 for (;;) {
252 start = be16_to_cpu(extent->block);
253 if (count <= block_nr) {
254 hfs_clear_vbm_bits(sb, start, count);
255 extent->block = 0;
256 extent->count = 0;
257 block_nr -= count;
258 } else {
259 count -= block_nr;
260 hfs_clear_vbm_bits(sb, start + count, block_nr);
261 extent->count = cpu_to_be16(count);
262 block_nr = 0;
263 }
264 if (!block_nr || !i)
265 return 0;
266 i--;
267 extent--;
268 count = be16_to_cpu(extent->count);
269 }
270 }
271
hfs_free_fork(struct super_block * sb,struct hfs_cat_file * file,int type)272 int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type)
273 {
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;
278 int res, i;
279
280 if (type == HFS_FK_DATA) {
281 total_blocks = be32_to_cpu(file->PyLen);
282 extent = file->ExtRec;
283 } else {
284 total_blocks = be32_to_cpu(file->RPyLen);
285 extent = file->RExtRec;
286 }
287 total_blocks /= HFS_SB(sb)->alloc_blksz;
288 if (!total_blocks)
289 return 0;
290
291 blocks = 0;
292 for (i = 0; i < 3; extent++, i++)
293 blocks += be16_to_cpu(extent[i].count);
294
295 res = hfs_free_extents(sb, extent, blocks, blocks);
296 if (res)
297 return res;
298 if (total_blocks == blocks)
299 return 0;
300
301 hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
302 do {
303 res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
304 if (res)
305 break;
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);
311 hfs_find_exit(&fd);
312
313 return res;
314 }
315
316 /*
317 * hfs_get_block
318 */
hfs_get_block(struct inode * inode,sector_t block,struct buffer_head * bh_result,int create)319 int hfs_get_block(struct inode *inode, sector_t block,
320 struct buffer_head *bh_result, int create)
321 {
322 struct super_block *sb;
323 u16 dblock, ablock;
324 int res;
325
326 sb = inode->i_sb;
327 /* Convert inode block to disk allocation block */
328 ablock = (u32)block / HFS_SB(sb)->fs_div;
329
330 if (block >= HFS_I(inode)->fs_blocks) {
331 if (block > HFS_I(inode)->fs_blocks || !create)
332 return -EIO;
333 if (ablock >= HFS_I(inode)->alloc_blocks) {
334 res = hfs_extend_file(inode);
335 if (res)
336 return res;
337 }
338 } else
339 create = 0;
340
341 if (ablock < HFS_I(inode)->first_blocks) {
342 dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
343 goto done;
344 }
345
346 mutex_lock(&HFS_I(inode)->extents_lock);
347 res = hfs_ext_read_extent(inode, ablock);
348 if (!res)
349 dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
350 ablock - HFS_I(inode)->cached_start);
351 else {
352 mutex_unlock(&HFS_I(inode)->extents_lock);
353 return -EIO;
354 }
355 mutex_unlock(&HFS_I(inode)->extents_lock);
356
357 done:
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);
361
362 if (create) {
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);
368 }
369 return 0;
370 }
371
hfs_extend_file(struct inode * inode)372 int hfs_extend_file(struct inode *inode)
373 {
374 struct super_block *sb = inode->i_sb;
375 u32 start, len, goal;
376 int res;
377
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);
381 else {
382 res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
383 if (res)
384 goto out;
385 goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
386 }
387
388 len = HFS_I(inode)->clump_blocks;
389 start = hfs_vbm_search_free(sb, goal, &len);
390 if (!len) {
391 res = -ENOSPC;
392 goto out;
393 }
394
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");
399 /* no extents yet */
400 HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
401 HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
402 res = 0;
403 } else {
404 /* try to append to extents in inode */
405 res = hfs_add_extent(HFS_I(inode)->first_extents,
406 HFS_I(inode)->alloc_blocks,
407 start, len);
408 if (res == -ENOSPC)
409 goto insert_extent;
410 }
411 if (!res) {
412 hfs_dump_extent(HFS_I(inode)->first_extents);
413 HFS_I(inode)->first_blocks += len;
414 }
415 } else {
416 res = hfs_add_extent(HFS_I(inode)->cached_extents,
417 HFS_I(inode)->alloc_blocks -
418 HFS_I(inode)->cached_start,
419 start, len);
420 if (!res) {
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)
425 goto insert_extent;
426 }
427 out:
428 mutex_unlock(&HFS_I(inode)->extents_lock);
429 if (!res) {
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);
435 sb->s_dirt = 1;
436 }
437 return res;
438
439 insert_extent:
440 dprint(DBG_EXTENT, "insert new extent\n");
441 hfs_ext_write_extent(inode);
442
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;
450
451 res = 0;
452 goto out;
453 }
454
hfs_file_truncate(struct inode * inode)455 void hfs_file_truncate(struct inode *inode)
456 {
457 struct super_block *sb = inode->i_sb;
458 struct hfs_find_data fd;
459 u16 blk_cnt, alloc_cnt, start;
460 u32 size;
461 int res;
462
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;
467 void *fsdata;
468 struct page *page;
469 int res;
470
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);
475 if (!res) {
476 res = pagecache_write_end(NULL, mapping, size+1, 0, 0,
477 page, fsdata);
478 }
479 if (res)
480 inode->i_size = HFS_I(inode)->phys_size;
481 return;
482 } else if (inode->i_size == HFS_I(inode)->phys_size)
483 return;
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)
488 goto out;
489
490 mutex_lock(&HFS_I(inode)->extents_lock);
491 hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
492 while (1) {
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;
498 break;
499 }
500 res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
501 if (res)
502 break;
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;
509 break;
510 }
511 alloc_cnt = start;
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);
515 }
516 hfs_find_exit(&fd);
517 mutex_unlock(&HFS_I(inode)->extents_lock);
518
519 HFS_I(inode)->alloc_blocks = blk_cnt;
520 out:
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);
525 }
526