~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/hfs/extent.c

Version: ~ [ linux-5.4-rc7 ] ~ [ linux-5.3.11 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.84 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.154 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.201 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.201 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.77 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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                 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 res;
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         return 0;
129 }
130 
131 int hfs_ext_write_extent(struct inode *inode)
132 {
133         struct hfs_find_data fd;
134         int res = 0;
135 
136         if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
137                 res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
138                 if (res)
139                         return res;
140                 res = __hfs_ext_write_extent(inode, &fd);
141                 hfs_find_exit(&fd);
142         }
143         return res;
144 }
145 
146 static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent,
147                                         u32 cnid, u32 block, u8 type)
148 {
149         int res;
150 
151         hfs_ext_build_key(fd->search_key, cnid, block, type);
152         fd->key->ext.FNum = 0;
153         res = hfs_brec_find(fd);
154         if (res && res != -ENOENT)
155                 return res;
156         if (fd->key->ext.FNum != fd->search_key->ext.FNum ||
157             fd->key->ext.FkType != fd->search_key->ext.FkType)
158                 return -ENOENT;
159         if (fd->entrylength != sizeof(hfs_extent_rec))
160                 return -EIO;
161         hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
162         return 0;
163 }
164 
165 static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
166 {
167         int res;
168 
169         if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
170                 res = __hfs_ext_write_extent(inode, fd);
171                 if (res)
172                         return res;
173         }
174 
175         res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
176                                     block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
177         if (!res) {
178                 HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
179                 HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
180         } else {
181                 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
182                 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
183         }
184         return res;
185 }
186 
187 static int hfs_ext_read_extent(struct inode *inode, u16 block)
188 {
189         struct hfs_find_data fd;
190         int res;
191 
192         if (block >= HFS_I(inode)->cached_start &&
193             block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
194                 return 0;
195 
196         res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
197         if (!res) {
198                 res = __hfs_ext_cache_extent(&fd, inode, block);
199                 hfs_find_exit(&fd);
200         }
201         return res;
202 }
203 
204 static void hfs_dump_extent(struct hfs_extent *extent)
205 {
206         int i;
207 
208         hfs_dbg(EXTENT, "   ");
209         for (i = 0; i < 3; i++)
210                 hfs_dbg_cont(EXTENT, " %u:%u",
211                              be16_to_cpu(extent[i].block),
212                              be16_to_cpu(extent[i].count));
213         hfs_dbg_cont(EXTENT, "\n");
214 }
215 
216 static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
217                           u16 alloc_block, u16 block_count)
218 {
219         u16 count, start;
220         int i;
221 
222         hfs_dump_extent(extent);
223         for (i = 0; i < 3; extent++, i++) {
224                 count = be16_to_cpu(extent->count);
225                 if (offset == count) {
226                         start = be16_to_cpu(extent->block);
227                         if (alloc_block != start + count) {
228                                 if (++i >= 3)
229                                         return -ENOSPC;
230                                 extent++;
231                                 extent->block = cpu_to_be16(alloc_block);
232                         } else
233                                 block_count += count;
234                         extent->count = cpu_to_be16(block_count);
235                         return 0;
236                 } else if (offset < count)
237                         break;
238                 offset -= count;
239         }
240         /* panic? */
241         return -EIO;
242 }
243 
244 static int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent,
245                             u16 offset, u16 block_nr)
246 {
247         u16 count, start;
248         int i;
249 
250         hfs_dump_extent(extent);
251         for (i = 0; i < 3; extent++, i++) {
252                 count = be16_to_cpu(extent->count);
253                 if (offset == count)
254                         goto found;
255                 else if (offset < count)
256                         break;
257                 offset -= count;
258         }
259         /* panic? */
260         return -EIO;
261 found:
262         for (;;) {
263                 start = be16_to_cpu(extent->block);
264                 if (count <= block_nr) {
265                         hfs_clear_vbm_bits(sb, start, count);
266                         extent->block = 0;
267                         extent->count = 0;
268                         block_nr -= count;
269                 } else {
270                         count -= block_nr;
271                         hfs_clear_vbm_bits(sb, start + count, block_nr);
272                         extent->count = cpu_to_be16(count);
273                         block_nr = 0;
274                 }
275                 if (!block_nr || !i)
276                         return 0;
277                 i--;
278                 extent--;
279                 count = be16_to_cpu(extent->count);
280         }
281 }
282 
283 int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type)
284 {
285         struct hfs_find_data fd;
286         u32 total_blocks, blocks, start;
287         u32 cnid = be32_to_cpu(file->FlNum);
288         struct hfs_extent *extent;
289         int res, i;
290 
291         if (type == HFS_FK_DATA) {
292                 total_blocks = be32_to_cpu(file->PyLen);
293                 extent = file->ExtRec;
294         } else {
295                 total_blocks = be32_to_cpu(file->RPyLen);
296                 extent = file->RExtRec;
297         }
298         total_blocks /= HFS_SB(sb)->alloc_blksz;
299         if (!total_blocks)
300                 return 0;
301 
302         blocks = 0;
303         for (i = 0; i < 3; extent++, i++)
304                 blocks += be16_to_cpu(extent[i].count);
305 
306         res = hfs_free_extents(sb, extent, blocks, blocks);
307         if (res)
308                 return res;
309         if (total_blocks == blocks)
310                 return 0;
311 
312         res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
313         if (res)
314                 return res;
315         do {
316                 res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
317                 if (res)
318                         break;
319                 start = be16_to_cpu(fd.key->ext.FABN);
320                 hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
321                 hfs_brec_remove(&fd);
322                 total_blocks = start;
323         } while (total_blocks > blocks);
324         hfs_find_exit(&fd);
325 
326         return res;
327 }
328 
329 /*
330  * hfs_get_block
331  */
332 int hfs_get_block(struct inode *inode, sector_t block,
333                   struct buffer_head *bh_result, int create)
334 {
335         struct super_block *sb;
336         u16 dblock, ablock;
337         int res;
338 
339         sb = inode->i_sb;
340         /* Convert inode block to disk allocation block */
341         ablock = (u32)block / HFS_SB(sb)->fs_div;
342 
343         if (block >= HFS_I(inode)->fs_blocks) {
344                 if (block > HFS_I(inode)->fs_blocks || !create)
345                         return -EIO;
346                 if (ablock >= HFS_I(inode)->alloc_blocks) {
347                         res = hfs_extend_file(inode);
348                         if (res)
349                                 return res;
350                 }
351         } else
352                 create = 0;
353 
354         if (ablock < HFS_I(inode)->first_blocks) {
355                 dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
356                 goto done;
357         }
358 
359         mutex_lock(&HFS_I(inode)->extents_lock);
360         res = hfs_ext_read_extent(inode, ablock);
361         if (!res)
362                 dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
363                                             ablock - HFS_I(inode)->cached_start);
364         else {
365                 mutex_unlock(&HFS_I(inode)->extents_lock);
366                 return -EIO;
367         }
368         mutex_unlock(&HFS_I(inode)->extents_lock);
369 
370 done:
371         map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
372                dblock * HFS_SB(sb)->fs_div +
373                (u32)block % HFS_SB(sb)->fs_div);
374 
375         if (create) {
376                 set_buffer_new(bh_result);
377                 HFS_I(inode)->phys_size += sb->s_blocksize;
378                 HFS_I(inode)->fs_blocks++;
379                 inode_add_bytes(inode, sb->s_blocksize);
380                 mark_inode_dirty(inode);
381         }
382         return 0;
383 }
384 
385 int hfs_extend_file(struct inode *inode)
386 {
387         struct super_block *sb = inode->i_sb;
388         u32 start, len, goal;
389         int res;
390 
391         mutex_lock(&HFS_I(inode)->extents_lock);
392         if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
393                 goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
394         else {
395                 res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
396                 if (res)
397                         goto out;
398                 goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
399         }
400 
401         len = HFS_I(inode)->clump_blocks;
402         start = hfs_vbm_search_free(sb, goal, &len);
403         if (!len) {
404                 res = -ENOSPC;
405                 goto out;
406         }
407 
408         hfs_dbg(EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
409         if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
410                 if (!HFS_I(inode)->first_blocks) {
411                         hfs_dbg(EXTENT, "first extents\n");
412                         /* no extents yet */
413                         HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
414                         HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
415                         res = 0;
416                 } else {
417                         /* try to append to extents in inode */
418                         res = hfs_add_extent(HFS_I(inode)->first_extents,
419                                              HFS_I(inode)->alloc_blocks,
420                                              start, len);
421                         if (res == -ENOSPC)
422                                 goto insert_extent;
423                 }
424                 if (!res) {
425                         hfs_dump_extent(HFS_I(inode)->first_extents);
426                         HFS_I(inode)->first_blocks += len;
427                 }
428         } else {
429                 res = hfs_add_extent(HFS_I(inode)->cached_extents,
430                                      HFS_I(inode)->alloc_blocks -
431                                      HFS_I(inode)->cached_start,
432                                      start, len);
433                 if (!res) {
434                         hfs_dump_extent(HFS_I(inode)->cached_extents);
435                         HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
436                         HFS_I(inode)->cached_blocks += len;
437                 } else if (res == -ENOSPC)
438                         goto insert_extent;
439         }
440 out:
441         mutex_unlock(&HFS_I(inode)->extents_lock);
442         if (!res) {
443                 HFS_I(inode)->alloc_blocks += len;
444                 mark_inode_dirty(inode);
445                 if (inode->i_ino < HFS_FIRSTUSER_CNID)
446                         set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
447                 set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
448                 hfs_mark_mdb_dirty(sb);
449         }
450         return res;
451 
452 insert_extent:
453         hfs_dbg(EXTENT, "insert new extent\n");
454         res = hfs_ext_write_extent(inode);
455         if (res)
456                 goto out;
457 
458         memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
459         HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
460         HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
461         hfs_dump_extent(HFS_I(inode)->cached_extents);
462         HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW;
463         HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
464         HFS_I(inode)->cached_blocks = len;
465 
466         res = 0;
467         goto out;
468 }
469 
470 void hfs_file_truncate(struct inode *inode)
471 {
472         struct super_block *sb = inode->i_sb;
473         struct hfs_find_data fd;
474         u16 blk_cnt, alloc_cnt, start;
475         u32 size;
476         int res;
477 
478         hfs_dbg(INODE, "truncate: %lu, %Lu -> %Lu\n",
479                 inode->i_ino, (long long)HFS_I(inode)->phys_size,
480                 inode->i_size);
481         if (inode->i_size > HFS_I(inode)->phys_size) {
482                 struct address_space *mapping = inode->i_mapping;
483                 void *fsdata;
484                 struct page *page;
485 
486                 /* XXX: Can use generic_cont_expand? */
487                 size = inode->i_size - 1;
488                 res = pagecache_write_begin(NULL, mapping, size+1, 0,
489                                 AOP_FLAG_UNINTERRUPTIBLE, &page, &fsdata);
490                 if (!res) {
491                         res = pagecache_write_end(NULL, mapping, size+1, 0, 0,
492                                         page, fsdata);
493                 }
494                 if (res)
495                         inode->i_size = HFS_I(inode)->phys_size;
496                 return;
497         } else if (inode->i_size == HFS_I(inode)->phys_size)
498                 return;
499         size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
500         blk_cnt = size / HFS_SB(sb)->alloc_blksz;
501         alloc_cnt = HFS_I(inode)->alloc_blocks;
502         if (blk_cnt == alloc_cnt)
503                 goto out;
504 
505         mutex_lock(&HFS_I(inode)->extents_lock);
506         res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
507         if (res) {
508                 mutex_unlock(&HFS_I(inode)->extents_lock);
509                 /* XXX: We lack error handling of hfs_file_truncate() */
510                 return;
511         }
512         while (1) {
513                 if (alloc_cnt == HFS_I(inode)->first_blocks) {
514                         hfs_free_extents(sb, HFS_I(inode)->first_extents,
515                                          alloc_cnt, alloc_cnt - blk_cnt);
516                         hfs_dump_extent(HFS_I(inode)->first_extents);
517                         HFS_I(inode)->first_blocks = blk_cnt;
518                         break;
519                 }
520                 res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
521                 if (res)
522                         break;
523                 start = HFS_I(inode)->cached_start;
524                 hfs_free_extents(sb, HFS_I(inode)->cached_extents,
525                                  alloc_cnt - start, alloc_cnt - blk_cnt);
526                 hfs_dump_extent(HFS_I(inode)->cached_extents);
527                 if (blk_cnt > start) {
528                         HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
529                         break;
530                 }
531                 alloc_cnt = start;
532                 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
533                 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
534                 hfs_brec_remove(&fd);
535         }
536         hfs_find_exit(&fd);
537         mutex_unlock(&HFS_I(inode)->extents_lock);
538 
539         HFS_I(inode)->alloc_blocks = blk_cnt;
540 out:
541         HFS_I(inode)->phys_size = inode->i_size;
542         HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
543         inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
544         mark_inode_dirty(inode);
545 }
546 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp