GNU Linux-libre 5.19-rc6-gnu
[releases.git] / fs / hfs / extent.c
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(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 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);
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(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, 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, 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, blocks, 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, 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  */
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, ablock);
362                 goto done;
363         }
364
365         mutex_lock(&HFS_I(inode)->extents_lock);
366         res = hfs_ext_read_extent(inode, ablock);
367         if (!res)
368                 dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
369                                             ablock - HFS_I(inode)->cached_start);
370         else {
371                 mutex_unlock(&HFS_I(inode)->extents_lock);
372                 return -EIO;
373         }
374         mutex_unlock(&HFS_I(inode)->extents_lock);
375
376 done:
377         map_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, 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                                              start, 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                                      start, 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(&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, &HFS_SB(sb)->flags);
453                 set_bit(HFS_FLG_MDB_DIRTY, &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;
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, size + 1, 0, &page,
495                                 &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(&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                                          alloc_cnt, 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, inode, 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                                  alloc_cnt - start, 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(&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 }