ext4: Fix spelling of CONTIG_FS_EXT3 to CONFIG_FS_EXT3
[linux-2.6.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 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
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
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
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
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
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
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
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
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  */
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
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
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 }