projects / linux-2.6-block.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
hfs: prevent btree data loss on ENOSPC
[linux-2.6-block.git] / fs / hfs / extent.c
CommitLineData
1da177e4
LT		 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 */
21static 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 */
50int 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 */
74static 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
89static 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
99static 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
9509f178 110static int __hfs_ext_write_extent(struct inode *inode, struct hfs_find_data *fd)
1da177e4
LT		 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)
9509f178 119 return res;
54640c75
EF		 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;
1da177e4
LT		 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)
9509f178 128 return res;
1da177e4
LT		 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 }
9509f178 132 return 0;
1da177e4
LT		 133}
134
9509f178 135int hfs_ext_write_extent(struct inode *inode)
1da177e4
LT		 136{
137 struct hfs_find_data fd;
9509f178 138 int res = 0;
1da177e4
LT		 139
140 if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
9509f178
AK		 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);
1da177e4
LT		 145 hfs_find_exit(&fd);
146 }
9509f178 147 return res;
1da177e4
LT		 148}
149
150static 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(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
169static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
170{
171 int res;
172
9509f178
AK		 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 }
1da177e4
LT		 178
179 res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, 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
191static 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
9509f178
AK		 200 res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
201 if (!res) {
202 res = __hfs_ext_cache_extent(&fd, inode, block);
203 hfs_find_exit(&fd);
204 }
1da177e4
LT		 205 return res;
206}
207
208static void hfs_dump_extent(struct hfs_extent *extent)
209{
210 int i;
211
c2b3e1f7 212 hfs_dbg(EXTENT, " ");
1da177e4 213 for (i = 0; i < 3; i++)
c2b3e1f7
JP		 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");
1da177e4
LT		 218}
219
220static 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
248static 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;
265found:
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
287int 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; extent++, i++)
308 blocks += be16_to_cpu(extent[i].count);
309
310 res = hfs_free_extents(sb, extent, blocks, blocks);
311 if (res)
312 return res;
313 if (total_blocks == blocks)
314 return 0;
315
9509f178
AK		 316 res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
317 if (res)
318 return res;
1da177e4
LT		 319 do {
320 res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
321 if (res)
322 break;
323 start = be16_to_cpu(fd.key->ext.FABN);
324 hfs_free_extents(sb, extent, total_blocks - start, 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 */
336int 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 (block > HFS_I(inode)->fs_blocks || !create)
349 return -EIO;
350 if (ablock >= HFS_I(inode)->alloc_blocks) {
351 res = hfs_extend_file(inode);
352 if (res)
353 return res;
354 }
355 } else
356 create = 0;
357
358 if (ablock < HFS_I(inode)->first_blocks) {
359 dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
360 goto done;
361 }
362
39f8d472 363 mutex_lock(&HFS_I(inode)->extents_lock);
1da177e4
LT		 364 res = hfs_ext_read_extent(inode, ablock);
365 if (!res)
366 dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
367 ablock - HFS_I(inode)->cached_start);
368 else {
39f8d472 369 mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4
LT		 370 return -EIO;
371 }
39f8d472 372 mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4
LT		 373
374done:
375 map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
376 dblock * HFS_SB(sb)->fs_div +
377 (u32)block % HFS_SB(sb)->fs_div);
378
379 if (create) {
380 set_buffer_new(bh_result);
381 HFS_I(inode)->phys_size += sb->s_blocksize;
382 HFS_I(inode)->fs_blocks++;
383 inode_add_bytes(inode, sb->s_blocksize);
384 mark_inode_dirty(inode);
385 }
386 return 0;
387}
388
389int hfs_extend_file(struct inode *inode)
390{
391 struct super_block *sb = inode->i_sb;
392 u32 start, len, goal;
393 int res;
394
39f8d472 395 mutex_lock(&HFS_I(inode)->extents_lock);
1da177e4
LT		 396 if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
397 goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
398 else {
399 res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
400 if (res)
401 goto out;
402 goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
403 }
404
405 len = HFS_I(inode)->clump_blocks;
406 start = hfs_vbm_search_free(sb, goal, &len);
407 if (!len) {
408 res = -ENOSPC;
409 goto out;
410 }
411
c2b3e1f7 412 hfs_dbg(EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
1da177e4
LT		 413 if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
414 if (!HFS_I(inode)->first_blocks) {
c2b3e1f7 415 hfs_dbg(EXTENT, "first extents\n");
1da177e4
LT		 416 /* no extents yet */
417 HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
418 HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
419 res = 0;
420 } else {
421 /* try to append to extents in inode */
422 res = hfs_add_extent(HFS_I(inode)->first_extents,
423 HFS_I(inode)->alloc_blocks,
424 start, len);
425 if (res == -ENOSPC)
426 goto insert_extent;
427 }
428 if (!res) {
429 hfs_dump_extent(HFS_I(inode)->first_extents);
430 HFS_I(inode)->first_blocks += len;
431 }
432 } else {
433 res = hfs_add_extent(HFS_I(inode)->cached_extents,
434 HFS_I(inode)->alloc_blocks -
435 HFS_I(inode)->cached_start,
436 start, len);
437 if (!res) {
438 hfs_dump_extent(HFS_I(inode)->cached_extents);
439 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
440 HFS_I(inode)->cached_blocks += len;
441 } else if (res == -ENOSPC)
442 goto insert_extent;
443 }
444out:
39f8d472 445 mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4
LT		 446 if (!res) {
447 HFS_I(inode)->alloc_blocks += len;
448 mark_inode_dirty(inode);
449 if (inode->i_ino < HFS_FIRSTUSER_CNID)
450 set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
451 set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
5687b578 452 hfs_mark_mdb_dirty(sb);
1da177e4
LT		 453 }
454 return res;
455
456insert_extent:
c2b3e1f7 457 hfs_dbg(EXTENT, "insert new extent\n");
9509f178
AK		 458 res = hfs_ext_write_extent(inode);
459 if (res)
460 goto out;
1da177e4
LT		 461
462 memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
463 HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
464 HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
465 hfs_dump_extent(HFS_I(inode)->cached_extents);
466 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW;
467 HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
468 HFS_I(inode)->cached_blocks = len;
469
470 res = 0;
471 goto out;
472}
473
474void hfs_file_truncate(struct inode *inode)
475{
476 struct super_block *sb = inode->i_sb;
477 struct hfs_find_data fd;
478 u16 blk_cnt, alloc_cnt, start;
479 u32 size;
480 int res;
481
c2b3e1f7
JP		 482 hfs_dbg(INODE, "truncate: %lu, %Lu -> %Lu\n",
483 inode->i_ino, (long long)HFS_I(inode)->phys_size,
484 inode->i_size);
1da177e4
LT		 485 if (inode->i_size > HFS_I(inode)->phys_size) {
486 struct address_space *mapping = inode->i_mapping;
7903d9ee 487 void *fsdata;
1da177e4 488 struct page *page;
1da177e4 489
7903d9ee 490 /* XXX: Can use generic_cont_expand? */
1da177e4 491 size = inode->i_size - 1;
c718a975
TH		 492 res = pagecache_write_begin(NULL, mapping, size+1, 0, 0,
493 &page, &fsdata);
7903d9ee
NP		 494 if (!res) {
495 res = pagecache_write_end(NULL, mapping, size+1, 0, 0,
496 page, fsdata);
497 }
1da177e4
LT		 498 if (res)
499 inode->i_size = HFS_I(inode)->phys_size;
1da177e4 500 return;
f76d28d2
RZ		 501 } else if (inode->i_size == HFS_I(inode)->phys_size)
502 return;
1da177e4
LT		 503 size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
504 blk_cnt = size / HFS_SB(sb)->alloc_blksz;
505 alloc_cnt = HFS_I(inode)->alloc_blocks;
506 if (blk_cnt == alloc_cnt)
507 goto out;
508
39f8d472 509 mutex_lock(&HFS_I(inode)->extents_lock);
9509f178
AK		 510 res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
511 if (res) {
512 mutex_unlock(&HFS_I(inode)->extents_lock);
513 /* XXX: We lack error handling of hfs_file_truncate() */
514 return;
515 }
1da177e4
LT		 516 while (1) {
517 if (alloc_cnt == HFS_I(inode)->first_blocks) {
518 hfs_free_extents(sb, HFS_I(inode)->first_extents,
519 alloc_cnt, alloc_cnt - blk_cnt);
520 hfs_dump_extent(HFS_I(inode)->first_extents);
521 HFS_I(inode)->first_blocks = blk_cnt;
522 break;
523 }
524 res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
525 if (res)
526 break;
527 start = HFS_I(inode)->cached_start;
528 hfs_free_extents(sb, HFS_I(inode)->cached_extents,
529 alloc_cnt - start, alloc_cnt - blk_cnt);
530 hfs_dump_extent(HFS_I(inode)->cached_extents);
531 if (blk_cnt > start) {
532 HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
533 break;
534 }
535 alloc_cnt = start;
536 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
537 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
538 hfs_brec_remove(&fd);
539 }
540 hfs_find_exit(&fd);
39f8d472 541 mutex_unlock(&HFS_I(inode)->extents_lock);
1da177e4
LT		 542
543 HFS_I(inode)->alloc_blocks = blk_cnt;
544out:
545 HFS_I(inode)->phys_size = inode->i_size;
546 HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
547 inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
548 mark_inode_dirty(inode);
549}
Linux 6.x block layer and io_uring tree(s)