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(key: fd->search_key, cnid: 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: &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(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, cnid: 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: &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, offset: blocks, block_nr: 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: &fd, extent, cnid, block: total_blocks, type); |
321 | if (res) |
322 | break; |
323 | start = be16_to_cpu(fd.key->ext.FABN); |
324 | hfs_free_extents(sb, extent, offset: total_blocks - start, block_nr: 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, off: ablock); |
362 | goto done; |
363 | } |
364 | |
365 | mutex_lock(&HFS_I(inode)->extents_lock); |
366 | res = hfs_ext_read_extent(inode, block: ablock); |
367 | if (!res) |
368 | dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents, |
369 | off: ablock - HFS_I(inode)->cached_start); |
370 | else { |
371 | mutex_unlock(lock: &HFS_I(inode)->extents_lock); |
372 | return -EIO; |
373 | } |
374 | mutex_unlock(lock: &HFS_I(inode)->extents_lock); |
375 | |
376 | done: |
377 | map_bh(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, bytes: 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 | alloc_block: start, block_count: 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 | alloc_block: start, block_count: 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(lock: &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, addr: &HFS_SB(sb)->flags); |
453 | set_bit(HFS_FLG_MDB_DIRTY, addr: &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 = NULL; |
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, pos: size + 1, len: 0, pagep: &page, |
495 | fsdata: &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(lock: &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 | offset: alloc_cnt, block_nr: 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: &fd, inode, block: 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 | offset: alloc_cnt - start, block_nr: 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(lock: &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 | |