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 unsigned int tmp;
53 int retval;
54
55 tmp = be32_to_cpu(key1->ext.FNum) - be32_to_cpu(key2->ext.FNum);
56 if (tmp != 0) {
57 retval = (int)tmp;
58 } else {
59 tmp = (unsigned char)key1->ext.FkType - (unsigned char)key2->ext.FkType;
60 if (tmp != 0) {
61 retval = (int)tmp;
62 } else {
63 retval = (int)(be16_to_cpu(key1->ext.FABN)
64 - be16_to_cpu(key2->ext.FABN));
65 }
66 }
67 return retval;
68 }
69
70 /*
71 * hfs_ext_find_block
72 *
73 * Find a block within an extent record
74 */
75 static u16 hfs_ext_find_block(struct hfs_extent *ext, u16 off)
76 {
77 int i;
78 u16 count;
79
80 for (i = 0; i < 3; ext++, i++) {
81 count = be16_to_cpu(ext->count);
82 if (off < count)
83 return be16_to_cpu(ext->block) + off;
84 off -= count;
85 }
86 /* panic? */
87 return 0;
88 }
89
90 static int hfs_ext_block_count(struct hfs_extent *ext)
91 {
92 int i;
93 u16 count = 0;
94
95 for (i = 0; i < 3; ext++, i++)
96 count += be16_to_cpu(ext->count);
97 return count;
98 }
99
100 static u16 hfs_ext_lastblock(struct hfs_extent *ext)
101 {
102 int i;
103
104 ext += 2;
105 for (i = 0; i < 2; ext--, i++)
106 if (ext->count)
107 break;
108 return be16_to_cpu(ext->block) + be16_to_cpu(ext->count);
109 }
110
111 static void __hfs_ext_write_extent(struct inode *inode, struct hfs_find_data *fd)
112 {
113 int res;
114
115 hfs_ext_build_key(fd->search_key, inode->i_ino, HFS_I(inode)->cached_start,
116 HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
117 res = hfs_brec_find(fd);
118 if (HFS_I(inode)->flags & HFS_FLG_EXT_NEW) {
119 if (res != -ENOENT)
120 return;
121 hfs_brec_insert(fd, HFS_I(inode)->cached_extents, sizeof(hfs_extent_rec));
122 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
123 } else {
124 if (res)
125 return;
126 hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
127 HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
128 }
129 }
130
131 void hfs_ext_write_extent(struct inode *inode)
132 {
133 struct hfs_find_data fd;
134
135 if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
136 hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
137 __hfs_ext_write_extent(inode, &fd);
138 hfs_find_exit(&fd);
139 }
140 }
141
142 static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent,
143 u32 cnid, u32 block, u8 type)
144 {
145 int res;
146
147 hfs_ext_build_key(fd->search_key, cnid, block, type);
148 fd->key->ext.FNum = 0;
149 res = hfs_brec_find(fd);
150 if (res && res != -ENOENT)
151 return res;
152 if (fd->key->ext.FNum != fd->search_key->ext.FNum ||
153 fd->key->ext.FkType != fd->search_key->ext.FkType)
154 return -ENOENT;
155 if (fd->entrylength != sizeof(hfs_extent_rec))
156 return -EIO;
157 hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
158 return 0;
159 }
160
161 static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
162 {
163 int res;
164
165 if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY)
166 __hfs_ext_write_extent(inode, fd);
167
168 res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
169 block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
170 if (!res) {
171 HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
172 HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
173 } else {
174 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
175 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
176 }
177 return res;
178 }
179
180 static int hfs_ext_read_extent(struct inode *inode, u16 block)
181 {
182 struct hfs_find_data fd;
183 int res;
184
185 if (block >= HFS_I(inode)->cached_start &&
186 block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
187 return 0;
188
189 hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
190 res = __hfs_ext_cache_extent(&fd, inode, block);
191 hfs_find_exit(&fd);
192 return res;
193 }
194
195 static void hfs_dump_extent(struct hfs_extent *extent)
196 {
197 int i;
198
199 dprint(DBG_EXTENT, " ");
200 for (i = 0; i < 3; i++)
201 dprint(DBG_EXTENT, " %u:%u", be16_to_cpu(extent[i].block),
202 be16_to_cpu(extent[i].count));
203 dprint(DBG_EXTENT, "\n");
204 }
205
206 static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
207 u16 alloc_block, u16 block_count)
208 {
209 u16 count, start;
210 int i;
211
212 hfs_dump_extent(extent);
213 for (i = 0; i < 3; extent++, i++) {
214 count = be16_to_cpu(extent->count);
215 if (offset == count) {
216 start = be16_to_cpu(extent->block);
217 if (alloc_block != start + count) {
218 if (++i >= 3)
219 return -ENOSPC;
220 extent++;
221 extent->block = cpu_to_be16(alloc_block);
222 } else
223 block_count += count;
224 extent->count = cpu_to_be16(block_count);
225 return 0;
226 } else if (offset < count)
227 break;
228 offset -= count;
229 }
230 /* panic? */
231 return -EIO;
232 }
233
234 int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent,
235 u16 offset, u16 block_nr)
236 {
237 u16 count, start;
238 int i;
239
240 hfs_dump_extent(extent);
241 for (i = 0; i < 3; extent++, i++) {
242 count = be16_to_cpu(extent->count);
243 if (offset == count)
244 goto found;
245 else if (offset < count)
246 break;
247 offset -= count;
248 }
249 /* panic? */
250 return -EIO;
251 found:
252 for (;;) {
253 start = be16_to_cpu(extent->block);
254 if (count <= block_nr) {
255 hfs_clear_vbm_bits(sb, start, count);
256 extent->block = 0;
257 extent->count = 0;
258 block_nr -= count;
259 } else {
260 count -= block_nr;
261 hfs_clear_vbm_bits(sb, start + count, block_nr);
262 extent->count = cpu_to_be16(count);
263 block_nr = 0;
264 }
265 if (!block_nr || !i)
266 return 0;
267 i--;
268 extent--;
269 count = be16_to_cpu(extent->count);
270 }
271 }
272
273 int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type)
274 {
275 struct hfs_find_data fd;
276 u32 total_blocks, blocks, start;
277 u32 cnid = be32_to_cpu(file->FlNum);
278 struct hfs_extent *extent;
279 int res, i;
280
281 if (type == HFS_FK_DATA) {
282 total_blocks = be32_to_cpu(file->PyLen);
283 extent = file->ExtRec;
284 } else {
285 total_blocks = be32_to_cpu(file->RPyLen);
286 extent = file->RExtRec;
287 }
288 total_blocks /= HFS_SB(sb)->alloc_blksz;
289 if (!total_blocks)
290 return 0;
291
292 blocks = 0;
293 for (i = 0; i < 3; extent++, i++)
294 blocks += be16_to_cpu(extent[i].count);
295
296 res = hfs_free_extents(sb, extent, blocks, blocks);
297 if (res)
298 return res;
299 if (total_blocks == blocks)
300 return 0;
301
302 hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
303 do {
304 res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
305 if (res)
306 break;
307 start = be16_to_cpu(fd.key->ext.FABN);
308 hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
309 hfs_brec_remove(&fd);
310 total_blocks = start;
311 } while (total_blocks > blocks);
312 hfs_find_exit(&fd);
313
314 return res;
315 }
316
317 /*
318 * hfs_get_block
319 */
320 int hfs_get_block(struct inode *inode, sector_t block,
321 struct buffer_head *bh_result, int create)
322 {
323 struct super_block *sb;
324 u16 dblock, ablock;
325 int res;
326
327 sb = inode->i_sb;
328 /* Convert inode block to disk allocation block */
329 ablock = (u32)block / HFS_SB(sb)->fs_div;
330
331 if (block >= HFS_I(inode)->fs_blocks) {
332 if (block > HFS_I(inode)->fs_blocks || !create)
333 return -EIO;
334 if (ablock >= HFS_I(inode)->alloc_blocks) {
335 res = hfs_extend_file(inode);
336 if (res)
337 return res;
338 }
339 } else
340 create = 0;
341
342 if (ablock < HFS_I(inode)->first_blocks) {
343 dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
344 goto done;
345 }
346
347 down(&HFS_I(inode)->extents_lock);
348 res = hfs_ext_read_extent(inode, ablock);
349 if (!res)
350 dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
351 ablock - HFS_I(inode)->cached_start);
352 else {
353 up(&HFS_I(inode)->extents_lock);
354 return -EIO;
355 }
356 up(&HFS_I(inode)->extents_lock);
357
358 done:
359 map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
360 dblock * HFS_SB(sb)->fs_div +
361 (u32)block % HFS_SB(sb)->fs_div);
362
363 if (create) {
364 set_buffer_new(bh_result);
365 HFS_I(inode)->phys_size += sb->s_blocksize;
366 HFS_I(inode)->fs_blocks++;
367 inode_add_bytes(inode, sb->s_blocksize);
368 mark_inode_dirty(inode);
369 }
370 return 0;
371 }
372
373 int hfs_extend_file(struct inode *inode)
374 {
375 struct super_block *sb = inode->i_sb;
376 u32 start, len, goal;
377 int res;
378
379 down(&HFS_I(inode)->extents_lock);
380 if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
381 goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
382 else {
383 res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
384 if (res)
385 goto out;
386 goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
387 }
388
389 len = HFS_I(inode)->clump_blocks;
390 start = hfs_vbm_search_free(sb, goal, &len);
391 if (!len) {
392 res = -ENOSPC;
393 goto out;
394 }
395
396 dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
397 if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
398 if (!HFS_I(inode)->first_blocks) {
399 dprint(DBG_EXTENT, "first extents\n");
400 /* no extents yet */
401 HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
402 HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
403 res = 0;
404 } else {
405 /* try to append to extents in inode */
406 res = hfs_add_extent(HFS_I(inode)->first_extents,
407 HFS_I(inode)->alloc_blocks,
408 start, len);
409 if (res == -ENOSPC)
410 goto insert_extent;
411 }
412 if (!res) {
413 hfs_dump_extent(HFS_I(inode)->first_extents);
414 HFS_I(inode)->first_blocks += len;
415 }
416 } else {
417 res = hfs_add_extent(HFS_I(inode)->cached_extents,
418 HFS_I(inode)->alloc_blocks -
419 HFS_I(inode)->cached_start,
420 start, len);
421 if (!res) {
422 hfs_dump_extent(HFS_I(inode)->cached_extents);
423 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
424 HFS_I(inode)->cached_blocks += len;
425 } else if (res == -ENOSPC)
426 goto insert_extent;
427 }
428 out:
429 up(&HFS_I(inode)->extents_lock);
430 if (!res) {
431 HFS_I(inode)->alloc_blocks += len;
432 mark_inode_dirty(inode);
433 if (inode->i_ino < HFS_FIRSTUSER_CNID)
434 set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
435 set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
436 sb->s_dirt = 1;
437 }
438 return res;
439
440 insert_extent:
441 dprint(DBG_EXTENT, "insert new extent\n");
442 hfs_ext_write_extent(inode);
443
444 memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
445 HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
446 HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
447 hfs_dump_extent(HFS_I(inode)->cached_extents);
448 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW;
449 HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
450 HFS_I(inode)->cached_blocks = len;
451
452 res = 0;
453 goto out;
454 }
455
456 void hfs_file_truncate(struct inode *inode)
457 {
458 struct super_block *sb = inode->i_sb;
459 struct hfs_find_data fd;
460 u16 blk_cnt, alloc_cnt, start;
461 u32 size;
462 int res;
463
464 dprint(DBG_INODE, "truncate: %lu, %Lu -> %Lu\n", inode->i_ino,
465 (long long)HFS_I(inode)->phys_size, inode->i_size);
466 if (inode->i_size > HFS_I(inode)->phys_size) {
467 struct address_space *mapping = inode->i_mapping;
468 struct page *page;
469 int res;
470
471 size = inode->i_size - 1;
472 page = grab_cache_page(mapping, size >> PAGE_CACHE_SHIFT);
473 if (!page)
474 return;
475 size &= PAGE_CACHE_SIZE - 1;
476 size++;
477 res = mapping->a_ops->prepare_write(NULL, page, size, size);
478 if (!res)
479 res = mapping->a_ops->commit_write(NULL, page, size, size);
480 if (res)
481 inode->i_size = HFS_I(inode)->phys_size;
482 unlock_page(page);
483 page_cache_release(page);
484 mark_inode_dirty(inode);
485 return;
486 }
487 size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
488 blk_cnt = size / HFS_SB(sb)->alloc_blksz;
489 alloc_cnt = HFS_I(inode)->alloc_blocks;
490 if (blk_cnt == alloc_cnt)
491 goto out;
492
493 down(&HFS_I(inode)->extents_lock);
494 hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
495 while (1) {
496 if (alloc_cnt == HFS_I(inode)->first_blocks) {
497 hfs_free_extents(sb, HFS_I(inode)->first_extents,
498 alloc_cnt, alloc_cnt - blk_cnt);
499 hfs_dump_extent(HFS_I(inode)->first_extents);
500 HFS_I(inode)->first_blocks = blk_cnt;
501 break;
502 }
503 res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
504 if (res)
505 break;
506 start = HFS_I(inode)->cached_start;
507 hfs_free_extents(sb, HFS_I(inode)->cached_extents,
508 alloc_cnt - start, alloc_cnt - blk_cnt);
509 hfs_dump_extent(HFS_I(inode)->cached_extents);
510 if (blk_cnt > start) {
511 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
512 break;
513 }
514 alloc_cnt = start;
515 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
516 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
517 hfs_brec_remove(&fd);
518 }
519 hfs_find_exit(&fd);
520 up(&HFS_I(inode)->extents_lock);
521
522 HFS_I(inode)->alloc_blocks = blk_cnt;
523 out:
524 HFS_I(inode)->phys_size = inode->i_size;
525 HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
526 inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
527 mark_inode_dirty(inode);
528 }
529
|
This page was automatically generated by the
LXR engine.
|