1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#include <linux/fs.h>
21#include <linux/time.h>
22#include <linux/jbd2.h>
23#include <linux/highuid.h>
24#include <linux/pagemap.h>
25#include <linux/quotaops.h>
26#include <linux/string.h>
27#include <linux/slab.h>
28#include <linux/uaccess.h>
29#include <linux/fiemap.h>
30#include <linux/backing-dev.h>
31#include "ext4_jbd2.h"
32#include "ext4_extents.h"
33#include "xattr.h"
34
35#include <trace/events/ext4.h>
36
37
38
39
40#define EXT4_EXT_MAY_ZEROOUT 0x1
41
42#define EXT4_EXT_MARK_UNWRIT1 0x2
43#define EXT4_EXT_MARK_UNWRIT2 0x4
44
45#define EXT4_EXT_DATA_VALID1 0x8
46#define EXT4_EXT_DATA_VALID2 0x10
47
48static __le32 ext4_extent_block_csum(struct inode *inode,
49 struct ext4_extent_header *eh)
50{
51 struct ext4_inode_info *ei = EXT4_I(inode);
52 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
53 __u32 csum;
54
55 csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)eh,
56 EXT4_EXTENT_TAIL_OFFSET(eh));
57 return cpu_to_le32(csum);
58}
59
60static int ext4_extent_block_csum_verify(struct inode *inode,
61 struct ext4_extent_header *eh)
62{
63 struct ext4_extent_tail *et;
64
65 if (!ext4_has_metadata_csum(inode->i_sb))
66 return 1;
67
68 et = find_ext4_extent_tail(eh);
69 if (et->et_checksum != ext4_extent_block_csum(inode, eh))
70 return 0;
71 return 1;
72}
73
74static void ext4_extent_block_csum_set(struct inode *inode,
75 struct ext4_extent_header *eh)
76{
77 struct ext4_extent_tail *et;
78
79 if (!ext4_has_metadata_csum(inode->i_sb))
80 return;
81
82 et = find_ext4_extent_tail(eh);
83 et->et_checksum = ext4_extent_block_csum(inode, eh);
84}
85
86static int ext4_split_extent(handle_t *handle,
87 struct inode *inode,
88 struct ext4_ext_path **ppath,
89 struct ext4_map_blocks *map,
90 int split_flag,
91 int flags);
92
93static int ext4_split_extent_at(handle_t *handle,
94 struct inode *inode,
95 struct ext4_ext_path **ppath,
96 ext4_lblk_t split,
97 int split_flag,
98 int flags);
99
100static int ext4_find_delayed_extent(struct inode *inode,
101 struct extent_status *newes);
102
103static int ext4_ext_truncate_extend_restart(handle_t *handle,
104 struct inode *inode,
105 int needed)
106{
107 int err;
108
109 if (!ext4_handle_valid(handle))
110 return 0;
111 if (handle->h_buffer_credits >= needed)
112 return 0;
113
114
115
116
117 needed += 3;
118 err = ext4_journal_extend(handle, needed - handle->h_buffer_credits);
119 if (err <= 0)
120 return err;
121 err = ext4_truncate_restart_trans(handle, inode, needed);
122 if (err == 0)
123 err = -EAGAIN;
124
125 return err;
126}
127
128
129
130
131
132
133static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
134 struct ext4_ext_path *path)
135{
136 if (path->p_bh) {
137
138 BUFFER_TRACE(path->p_bh, "get_write_access");
139 return ext4_journal_get_write_access(handle, path->p_bh);
140 }
141
142
143 return 0;
144}
145
146
147
148
149
150
151
152int __ext4_ext_dirty(const char *where, unsigned int line, handle_t *handle,
153 struct inode *inode, struct ext4_ext_path *path)
154{
155 int err;
156
157 WARN_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
158 if (path->p_bh) {
159 ext4_extent_block_csum_set(inode, ext_block_hdr(path->p_bh));
160
161 err = __ext4_handle_dirty_metadata(where, line, handle,
162 inode, path->p_bh);
163 } else {
164
165 err = ext4_mark_inode_dirty(handle, inode);
166 }
167 return err;
168}
169
170static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
171 struct ext4_ext_path *path,
172 ext4_lblk_t block)
173{
174 if (path) {
175 int depth = path->p_depth;
176 struct ext4_extent *ex;
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195 ex = path[depth].p_ext;
196 if (ex) {
197 ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
198 ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);
199
200 if (block > ext_block)
201 return ext_pblk + (block - ext_block);
202 else
203 return ext_pblk - (ext_block - block);
204 }
205
206
207
208 if (path[depth].p_bh)
209 return path[depth].p_bh->b_blocknr;
210 }
211
212
213 return ext4_inode_to_goal_block(inode);
214}
215
216
217
218
219static ext4_fsblk_t
220ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
221 struct ext4_ext_path *path,
222 struct ext4_extent *ex, int *err, unsigned int flags)
223{
224 ext4_fsblk_t goal, newblock;
225
226 goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
227 newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
228 NULL, err);
229 return newblock;
230}
231
232static inline int ext4_ext_space_block(struct inode *inode, int check)
233{
234 int size;
235
236 size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
237 / sizeof(struct ext4_extent);
238#ifdef AGGRESSIVE_TEST
239 if (!check && size > 6)
240 size = 6;
241#endif
242 return size;
243}
244
245static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
246{
247 int size;
248
249 size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
250 / sizeof(struct ext4_extent_idx);
251#ifdef AGGRESSIVE_TEST
252 if (!check && size > 5)
253 size = 5;
254#endif
255 return size;
256}
257
258static inline int ext4_ext_space_root(struct inode *inode, int check)
259{
260 int size;
261
262 size = sizeof(EXT4_I(inode)->i_data);
263 size -= sizeof(struct ext4_extent_header);
264 size /= sizeof(struct ext4_extent);
265#ifdef AGGRESSIVE_TEST
266 if (!check && size > 3)
267 size = 3;
268#endif
269 return size;
270}
271
272static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
273{
274 int size;
275
276 size = sizeof(EXT4_I(inode)->i_data);
277 size -= sizeof(struct ext4_extent_header);
278 size /= sizeof(struct ext4_extent_idx);
279#ifdef AGGRESSIVE_TEST
280 if (!check && size > 4)
281 size = 4;
282#endif
283 return size;
284}
285
286static inline int
287ext4_force_split_extent_at(handle_t *handle, struct inode *inode,
288 struct ext4_ext_path **ppath, ext4_lblk_t lblk,
289 int nofail)
290{
291 struct ext4_ext_path *path = *ppath;
292 int unwritten = ext4_ext_is_unwritten(path[path->p_depth].p_ext);
293
294 return ext4_split_extent_at(handle, inode, ppath, lblk, unwritten ?
295 EXT4_EXT_MARK_UNWRIT1|EXT4_EXT_MARK_UNWRIT2 : 0,
296 EXT4_EX_NOCACHE | EXT4_GET_BLOCKS_PRE_IO |
297 (nofail ? EXT4_GET_BLOCKS_METADATA_NOFAIL:0));
298}
299
300
301
302
303
304
305int ext4_ext_calc_metadata_amount(struct inode *inode, ext4_lblk_t lblock)
306{
307 struct ext4_inode_info *ei = EXT4_I(inode);
308 int idxs;
309
310 idxs = ((inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
311 / sizeof(struct ext4_extent_idx));
312
313
314
315
316
317
318
319
320
321 if (ei->i_da_metadata_calc_len &&
322 ei->i_da_metadata_calc_last_lblock+1 == lblock) {
323 int num = 0;
324
325 if ((ei->i_da_metadata_calc_len % idxs) == 0)
326 num++;
327 if ((ei->i_da_metadata_calc_len % (idxs*idxs)) == 0)
328 num++;
329 if ((ei->i_da_metadata_calc_len % (idxs*idxs*idxs)) == 0) {
330 num++;
331 ei->i_da_metadata_calc_len = 0;
332 } else
333 ei->i_da_metadata_calc_len++;
334 ei->i_da_metadata_calc_last_lblock++;
335 return num;
336 }
337
338
339
340
341
342 ei->i_da_metadata_calc_len = 1;
343 ei->i_da_metadata_calc_last_lblock = lblock;
344 return ext_depth(inode) + 1;
345}
346
347static int
348ext4_ext_max_entries(struct inode *inode, int depth)
349{
350 int max;
351
352 if (depth == ext_depth(inode)) {
353 if (depth == 0)
354 max = ext4_ext_space_root(inode, 1);
355 else
356 max = ext4_ext_space_root_idx(inode, 1);
357 } else {
358 if (depth == 0)
359 max = ext4_ext_space_block(inode, 1);
360 else
361 max = ext4_ext_space_block_idx(inode, 1);
362 }
363
364 return max;
365}
366
367static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
368{
369 ext4_fsblk_t block = ext4_ext_pblock(ext);
370 int len = ext4_ext_get_actual_len(ext);
371 ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
372
373
374
375
376
377
378 if (lblock + len <= lblock)
379 return 0;
380 return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
381}
382
383static int ext4_valid_extent_idx(struct inode *inode,
384 struct ext4_extent_idx *ext_idx)
385{
386 ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
387
388 return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
389}
390
391static int ext4_valid_extent_entries(struct inode *inode,
392 struct ext4_extent_header *eh,
393 int depth)
394{
395 unsigned short entries;
396 if (eh->eh_entries == 0)
397 return 1;
398
399 entries = le16_to_cpu(eh->eh_entries);
400
401 if (depth == 0) {
402
403 struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
404 struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
405 ext4_fsblk_t pblock = 0;
406 ext4_lblk_t lblock = 0;
407 ext4_lblk_t prev = 0;
408 int len = 0;
409 while (entries) {
410 if (!ext4_valid_extent(inode, ext))
411 return 0;
412
413
414 lblock = le32_to_cpu(ext->ee_block);
415 len = ext4_ext_get_actual_len(ext);
416 if ((lblock <= prev) && prev) {
417 pblock = ext4_ext_pblock(ext);
418 es->s_last_error_block = cpu_to_le64(pblock);
419 return 0;
420 }
421 ext++;
422 entries--;
423 prev = lblock + len - 1;
424 }
425 } else {
426 struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
427 while (entries) {
428 if (!ext4_valid_extent_idx(inode, ext_idx))
429 return 0;
430 ext_idx++;
431 entries--;
432 }
433 }
434 return 1;
435}
436
437static int __ext4_ext_check(const char *function, unsigned int line,
438 struct inode *inode, struct ext4_extent_header *eh,
439 int depth, ext4_fsblk_t pblk)
440{
441 const char *error_msg;
442 int max = 0, err = -EFSCORRUPTED;
443
444 if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
445 error_msg = "invalid magic";
446 goto corrupted;
447 }
448 if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
449 error_msg = "unexpected eh_depth";
450 goto corrupted;
451 }
452 if (unlikely(eh->eh_max == 0)) {
453 error_msg = "invalid eh_max";
454 goto corrupted;
455 }
456 max = ext4_ext_max_entries(inode, depth);
457 if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
458 error_msg = "too large eh_max";
459 goto corrupted;
460 }
461 if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
462 error_msg = "invalid eh_entries";
463 goto corrupted;
464 }
465 if (!ext4_valid_extent_entries(inode, eh, depth)) {
466 error_msg = "invalid extent entries";
467 goto corrupted;
468 }
469 if (unlikely(depth > 32)) {
470 error_msg = "too large eh_depth";
471 goto corrupted;
472 }
473
474 if (ext_depth(inode) != depth &&
475 !ext4_extent_block_csum_verify(inode, eh)) {
476 error_msg = "extent tree corrupted";
477 err = -EFSBADCRC;
478 goto corrupted;
479 }
480 return 0;
481
482corrupted:
483 ext4_error_inode(inode, function, line, 0,
484 "pblk %llu bad header/extent: %s - magic %x, "
485 "entries %u, max %u(%u), depth %u(%u)",
486 (unsigned long long) pblk, error_msg,
487 le16_to_cpu(eh->eh_magic),
488 le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
489 max, le16_to_cpu(eh->eh_depth), depth);
490 return err;
491}
492
493#define ext4_ext_check(inode, eh, depth, pblk) \
494 __ext4_ext_check(__func__, __LINE__, (inode), (eh), (depth), (pblk))
495
496int ext4_ext_check_inode(struct inode *inode)
497{
498 return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode), 0);
499}
500
501static struct buffer_head *
502__read_extent_tree_block(const char *function, unsigned int line,
503 struct inode *inode, ext4_fsblk_t pblk, int depth,
504 int flags)
505{
506 struct buffer_head *bh;
507 int err;
508
509 bh = sb_getblk_gfp(inode->i_sb, pblk, __GFP_MOVABLE | GFP_NOFS);
510 if (unlikely(!bh))
511 return ERR_PTR(-ENOMEM);
512
513 if (!bh_uptodate_or_lock(bh)) {
514 trace_ext4_ext_load_extent(inode, pblk, _RET_IP_);
515 err = bh_submit_read(bh);
516 if (err < 0)
517 goto errout;
518 }
519 if (buffer_verified(bh) && !(flags & EXT4_EX_FORCE_CACHE))
520 return bh;
521 err = __ext4_ext_check(function, line, inode,
522 ext_block_hdr(bh), depth, pblk);
523 if (err)
524 goto errout;
525 set_buffer_verified(bh);
526
527
528
529 if (!(flags & EXT4_EX_NOCACHE) && depth == 0) {
530 struct ext4_extent_header *eh = ext_block_hdr(bh);
531 struct ext4_extent *ex = EXT_FIRST_EXTENT(eh);
532 ext4_lblk_t prev = 0;
533 int i;
534
535 for (i = le16_to_cpu(eh->eh_entries); i > 0; i--, ex++) {
536 unsigned int status = EXTENT_STATUS_WRITTEN;
537 ext4_lblk_t lblk = le32_to_cpu(ex->ee_block);
538 int len = ext4_ext_get_actual_len(ex);
539
540 if (prev && (prev != lblk))
541 ext4_es_cache_extent(inode, prev,
542 lblk - prev, ~0,
543 EXTENT_STATUS_HOLE);
544
545 if (ext4_ext_is_unwritten(ex))
546 status = EXTENT_STATUS_UNWRITTEN;
547 ext4_es_cache_extent(inode, lblk, len,
548 ext4_ext_pblock(ex), status);
549 prev = lblk + len;
550 }
551 }
552 return bh;
553errout:
554 put_bh(bh);
555 return ERR_PTR(err);
556
557}
558
559#define read_extent_tree_block(inode, pblk, depth, flags) \
560 __read_extent_tree_block(__func__, __LINE__, (inode), (pblk), \
561 (depth), (flags))
562
563
564
565
566
567int ext4_ext_precache(struct inode *inode)
568{
569 struct ext4_inode_info *ei = EXT4_I(inode);
570 struct ext4_ext_path *path = NULL;
571 struct buffer_head *bh;
572 int i = 0, depth, ret = 0;
573
574 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
575 return 0;
576
577 down_read(&ei->i_data_sem);
578 depth = ext_depth(inode);
579
580 path = kcalloc(depth + 1, sizeof(struct ext4_ext_path),
581 GFP_NOFS);
582 if (path == NULL) {
583 up_read(&ei->i_data_sem);
584 return -ENOMEM;
585 }
586
587
588 if (depth == 0)
589 goto out;
590 path[0].p_hdr = ext_inode_hdr(inode);
591 ret = ext4_ext_check(inode, path[0].p_hdr, depth, 0);
592 if (ret)
593 goto out;
594 path[0].p_idx = EXT_FIRST_INDEX(path[0].p_hdr);
595 while (i >= 0) {
596
597
598
599
600 if ((i == depth) ||
601 path[i].p_idx > EXT_LAST_INDEX(path[i].p_hdr)) {
602 brelse(path[i].p_bh);
603 path[i].p_bh = NULL;
604 i--;
605 continue;
606 }
607 bh = read_extent_tree_block(inode,
608 ext4_idx_pblock(path[i].p_idx++),
609 depth - i - 1,
610 EXT4_EX_FORCE_CACHE);
611 if (IS_ERR(bh)) {
612 ret = PTR_ERR(bh);
613 break;
614 }
615 i++;
616 path[i].p_bh = bh;
617 path[i].p_hdr = ext_block_hdr(bh);
618 path[i].p_idx = EXT_FIRST_INDEX(path[i].p_hdr);
619 }
620 ext4_set_inode_state(inode, EXT4_STATE_EXT_PRECACHED);
621out:
622 up_read(&ei->i_data_sem);
623 ext4_ext_drop_refs(path);
624 kfree(path);
625 return ret;
626}
627
628#ifdef EXT_DEBUG
629static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
630{
631 int k, l = path->p_depth;
632
633 ext_debug("path:");
634 for (k = 0; k <= l; k++, path++) {
635 if (path->p_idx) {
636 ext_debug(" %d->%llu", le32_to_cpu(path->p_idx->ei_block),
637 ext4_idx_pblock(path->p_idx));
638 } else if (path->p_ext) {
639 ext_debug(" %d:[%d]%d:%llu ",
640 le32_to_cpu(path->p_ext->ee_block),
641 ext4_ext_is_unwritten(path->p_ext),
642 ext4_ext_get_actual_len(path->p_ext),
643 ext4_ext_pblock(path->p_ext));
644 } else
645 ext_debug(" []");
646 }
647 ext_debug("\n");
648}
649
650static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
651{
652 int depth = ext_depth(inode);
653 struct ext4_extent_header *eh;
654 struct ext4_extent *ex;
655 int i;
656
657 if (!path)
658 return;
659
660 eh = path[depth].p_hdr;
661 ex = EXT_FIRST_EXTENT(eh);
662
663 ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino);
664
665 for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
666 ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
667 ext4_ext_is_unwritten(ex),
668 ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
669 }
670 ext_debug("\n");
671}
672
673static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
674 ext4_fsblk_t newblock, int level)
675{
676 int depth = ext_depth(inode);
677 struct ext4_extent *ex;
678
679 if (depth != level) {
680 struct ext4_extent_idx *idx;
681 idx = path[level].p_idx;
682 while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
683 ext_debug("%d: move %d:%llu in new index %llu\n", level,
684 le32_to_cpu(idx->ei_block),
685 ext4_idx_pblock(idx),
686 newblock);
687 idx++;
688 }
689
690 return;
691 }
692
693 ex = path[depth].p_ext;
694 while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
695 ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
696 le32_to_cpu(ex->ee_block),
697 ext4_ext_pblock(ex),
698 ext4_ext_is_unwritten(ex),
699 ext4_ext_get_actual_len(ex),
700 newblock);
701 ex++;
702 }
703}
704
705#else
706#define ext4_ext_show_path(inode, path)
707#define ext4_ext_show_leaf(inode, path)
708#define ext4_ext_show_move(inode, path, newblock, level)
709#endif
710
711void ext4_ext_drop_refs(struct ext4_ext_path *path)
712{
713 int depth, i;
714
715 if (!path)
716 return;
717 depth = path->p_depth;
718 for (i = 0; i <= depth; i++, path++)
719 if (path->p_bh) {
720 brelse(path->p_bh);
721 path->p_bh = NULL;
722 }
723}
724
725
726
727
728
729
730static void
731ext4_ext_binsearch_idx(struct inode *inode,
732 struct ext4_ext_path *path, ext4_lblk_t block)
733{
734 struct ext4_extent_header *eh = path->p_hdr;
735 struct ext4_extent_idx *r, *l, *m;
736
737
738 ext_debug("binsearch for %u(idx): ", block);
739
740 l = EXT_FIRST_INDEX(eh) + 1;
741 r = EXT_LAST_INDEX(eh);
742 while (l <= r) {
743 m = l + (r - l) / 2;
744 if (block < le32_to_cpu(m->ei_block))
745 r = m - 1;
746 else
747 l = m + 1;
748 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
749 m, le32_to_cpu(m->ei_block),
750 r, le32_to_cpu(r->ei_block));
751 }
752
753 path->p_idx = l - 1;
754 ext_debug(" -> %u->%lld ", le32_to_cpu(path->p_idx->ei_block),
755 ext4_idx_pblock(path->p_idx));
756
757#ifdef CHECK_BINSEARCH
758 {
759 struct ext4_extent_idx *chix, *ix;
760 int k;
761
762 chix = ix = EXT_FIRST_INDEX(eh);
763 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
764 if (k != 0 &&
765 le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
766 printk(KERN_DEBUG "k=%d, ix=0x%p, "
767 "first=0x%p\n", k,
768 ix, EXT_FIRST_INDEX(eh));
769 printk(KERN_DEBUG "%u <= %u\n",
770 le32_to_cpu(ix->ei_block),
771 le32_to_cpu(ix[-1].ei_block));
772 }
773 BUG_ON(k && le32_to_cpu(ix->ei_block)
774 <= le32_to_cpu(ix[-1].ei_block));
775 if (block < le32_to_cpu(ix->ei_block))
776 break;
777 chix = ix;
778 }
779 BUG_ON(chix != path->p_idx);
780 }
781#endif
782
783}
784
785
786
787
788
789
790static void
791ext4_ext_binsearch(struct inode *inode,
792 struct ext4_ext_path *path, ext4_lblk_t block)
793{
794 struct ext4_extent_header *eh = path->p_hdr;
795 struct ext4_extent *r, *l, *m;
796
797 if (eh->eh_entries == 0) {
798
799
800
801
802 return;
803 }
804
805 ext_debug("binsearch for %u: ", block);
806
807 l = EXT_FIRST_EXTENT(eh) + 1;
808 r = EXT_LAST_EXTENT(eh);
809
810 while (l <= r) {
811 m = l + (r - l) / 2;
812 if (block < le32_to_cpu(m->ee_block))
813 r = m - 1;
814 else
815 l = m + 1;
816 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
817 m, le32_to_cpu(m->ee_block),
818 r, le32_to_cpu(r->ee_block));
819 }
820
821 path->p_ext = l - 1;
822 ext_debug(" -> %d:%llu:[%d]%d ",
823 le32_to_cpu(path->p_ext->ee_block),
824 ext4_ext_pblock(path->p_ext),
825 ext4_ext_is_unwritten(path->p_ext),
826 ext4_ext_get_actual_len(path->p_ext));
827
828#ifdef CHECK_BINSEARCH
829 {
830 struct ext4_extent *chex, *ex;
831 int k;
832
833 chex = ex = EXT_FIRST_EXTENT(eh);
834 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
835 BUG_ON(k && le32_to_cpu(ex->ee_block)
836 <= le32_to_cpu(ex[-1].ee_block));
837 if (block < le32_to_cpu(ex->ee_block))
838 break;
839 chex = ex;
840 }
841 BUG_ON(chex != path->p_ext);
842 }
843#endif
844
845}
846
847int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
848{
849 struct ext4_extent_header *eh;
850
851 eh = ext_inode_hdr(inode);
852 eh->eh_depth = 0;
853 eh->eh_entries = 0;
854 eh->eh_magic = EXT4_EXT_MAGIC;
855 eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
856 ext4_mark_inode_dirty(handle, inode);
857 return 0;
858}
859
860struct ext4_ext_path *
861ext4_find_extent(struct inode *inode, ext4_lblk_t block,
862 struct ext4_ext_path **orig_path, int flags)
863{
864 struct ext4_extent_header *eh;
865 struct buffer_head *bh;
866 struct ext4_ext_path *path = orig_path ? *orig_path : NULL;
867 short int depth, i, ppos = 0;
868 int ret;
869
870 eh = ext_inode_hdr(inode);
871 depth = ext_depth(inode);
872 if (depth < 0 || depth > EXT4_MAX_EXTENT_DEPTH) {
873 EXT4_ERROR_INODE(inode, "inode has invalid extent depth: %d",
874 depth);
875 ret = -EFSCORRUPTED;
876 goto err;
877 }
878
879 if (path) {
880 ext4_ext_drop_refs(path);
881 if (depth > path[0].p_maxdepth) {
882 kfree(path);
883 *orig_path = path = NULL;
884 }
885 }
886 if (!path) {
887
888 path = kcalloc(depth + 2, sizeof(struct ext4_ext_path),
889 GFP_NOFS);
890 if (unlikely(!path))
891 return ERR_PTR(-ENOMEM);
892 path[0].p_maxdepth = depth + 1;
893 }
894 path[0].p_hdr = eh;
895 path[0].p_bh = NULL;
896
897 i = depth;
898
899 while (i) {
900 ext_debug("depth %d: num %d, max %d\n",
901 ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
902
903 ext4_ext_binsearch_idx(inode, path + ppos, block);
904 path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
905 path[ppos].p_depth = i;
906 path[ppos].p_ext = NULL;
907
908 bh = read_extent_tree_block(inode, path[ppos].p_block, --i,
909 flags);
910 if (IS_ERR(bh)) {
911 ret = PTR_ERR(bh);
912 goto err;
913 }
914
915 eh = ext_block_hdr(bh);
916 ppos++;
917 path[ppos].p_bh = bh;
918 path[ppos].p_hdr = eh;
919 }
920
921 path[ppos].p_depth = i;
922 path[ppos].p_ext = NULL;
923 path[ppos].p_idx = NULL;
924
925
926 ext4_ext_binsearch(inode, path + ppos, block);
927
928 if (path[ppos].p_ext)
929 path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
930
931 ext4_ext_show_path(inode, path);
932
933 return path;
934
935err:
936 ext4_ext_drop_refs(path);
937 kfree(path);
938 if (orig_path)
939 *orig_path = NULL;
940 return ERR_PTR(ret);
941}
942
943
944
945
946
947
948static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
949 struct ext4_ext_path *curp,
950 int logical, ext4_fsblk_t ptr)
951{
952 struct ext4_extent_idx *ix;
953 int len, err;
954
955 err = ext4_ext_get_access(handle, inode, curp);
956 if (err)
957 return err;
958
959 if (unlikely(logical == le32_to_cpu(curp->p_idx->ei_block))) {
960 EXT4_ERROR_INODE(inode,
961 "logical %d == ei_block %d!",
962 logical, le32_to_cpu(curp->p_idx->ei_block));
963 return -EFSCORRUPTED;
964 }
965
966 if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
967 >= le16_to_cpu(curp->p_hdr->eh_max))) {
968 EXT4_ERROR_INODE(inode,
969 "eh_entries %d >= eh_max %d!",
970 le16_to_cpu(curp->p_hdr->eh_entries),
971 le16_to_cpu(curp->p_hdr->eh_max));
972 return -EFSCORRUPTED;
973 }
974
975 if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
976
977 ext_debug("insert new index %d after: %llu\n", logical, ptr);
978 ix = curp->p_idx + 1;
979 } else {
980
981 ext_debug("insert new index %d before: %llu\n", logical, ptr);
982 ix = curp->p_idx;
983 }
984
985 len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1;
986 BUG_ON(len < 0);
987 if (len > 0) {
988 ext_debug("insert new index %d: "
989 "move %d indices from 0x%p to 0x%p\n",
990 logical, len, ix, ix + 1);
991 memmove(ix + 1, ix, len * sizeof(struct ext4_extent_idx));
992 }
993
994 if (unlikely(ix > EXT_MAX_INDEX(curp->p_hdr))) {
995 EXT4_ERROR_INODE(inode, "ix > EXT_MAX_INDEX!");
996 return -EFSCORRUPTED;
997 }
998
999 ix->ei_block = cpu_to_le32(logical);
1000 ext4_idx_store_pblock(ix, ptr);
1001 le16_add_cpu(&curp->p_hdr->eh_entries, 1);
1002
1003 if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
1004 EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
1005 return -EFSCORRUPTED;
1006 }
1007
1008 err = ext4_ext_dirty(handle, inode, curp);
1009 ext4_std_error(inode->i_sb, err);
1010
1011 return err;
1012}
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024static int ext4_ext_split(handle_t *handle, struct inode *inode,
1025 unsigned int flags,
1026 struct ext4_ext_path *path,
1027 struct ext4_extent *newext, int at)
1028{
1029 struct buffer_head *bh = NULL;
1030 int depth = ext_depth(inode);
1031 struct ext4_extent_header *neh;
1032 struct ext4_extent_idx *fidx;
1033 int i = at, k, m, a;
1034 ext4_fsblk_t newblock, oldblock;
1035 __le32 border;
1036 ext4_fsblk_t *ablocks = NULL;
1037 int err = 0;
1038
1039
1040
1041
1042
1043
1044 if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
1045 EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
1046 return -EFSCORRUPTED;
1047 }
1048 if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
1049 border = path[depth].p_ext[1].ee_block;
1050 ext_debug("leaf will be split."
1051 " next leaf starts at %d\n",
1052 le32_to_cpu(border));
1053 } else {
1054 border = newext->ee_block;
1055 ext_debug("leaf will be added."
1056 " next leaf starts at %d\n",
1057 le32_to_cpu(border));
1058 }
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072 ablocks = kcalloc(depth, sizeof(ext4_fsblk_t), GFP_NOFS);
1073 if (!ablocks)
1074 return -ENOMEM;
1075
1076
1077 ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
1078 for (a = 0; a < depth - at; a++) {
1079 newblock = ext4_ext_new_meta_block(handle, inode, path,
1080 newext, &err, flags);
1081 if (newblock == 0)
1082 goto cleanup;
1083 ablocks[a] = newblock;
1084 }
1085
1086
1087 newblock = ablocks[--a];
1088 if (unlikely(newblock == 0)) {
1089 EXT4_ERROR_INODE(inode, "newblock == 0!");
1090 err = -EFSCORRUPTED;
1091 goto cleanup;
1092 }
1093 bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1094 if (unlikely(!bh)) {
1095 err = -ENOMEM;
1096 goto cleanup;
1097 }
1098 lock_buffer(bh);
1099
1100 err = ext4_journal_get_create_access(handle, bh);
1101 if (err)
1102 goto cleanup;
1103
1104 neh = ext_block_hdr(bh);
1105 neh->eh_entries = 0;
1106 neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1107 neh->eh_magic = EXT4_EXT_MAGIC;
1108 neh->eh_depth = 0;
1109
1110
1111 if (unlikely(path[depth].p_hdr->eh_entries !=
1112 path[depth].p_hdr->eh_max)) {
1113 EXT4_ERROR_INODE(inode, "eh_entries %d != eh_max %d!",
1114 path[depth].p_hdr->eh_entries,
1115 path[depth].p_hdr->eh_max);
1116 err = -EFSCORRUPTED;
1117 goto cleanup;
1118 }
1119
1120 m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
1121 ext4_ext_show_move(inode, path, newblock, depth);
1122 if (m) {
1123 struct ext4_extent *ex;
1124 ex = EXT_FIRST_EXTENT(neh);
1125 memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
1126 le16_add_cpu(&neh->eh_entries, m);
1127 }
1128
1129 ext4_extent_block_csum_set(inode, neh);
1130 set_buffer_uptodate(bh);
1131 unlock_buffer(bh);
1132
1133 err = ext4_handle_dirty_metadata(handle, inode, bh);
1134 if (err)
1135 goto cleanup;
1136 brelse(bh);
1137 bh = NULL;
1138
1139
1140 if (m) {
1141 err = ext4_ext_get_access(handle, inode, path + depth);
1142 if (err)
1143 goto cleanup;
1144 le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
1145 err = ext4_ext_dirty(handle, inode, path + depth);
1146 if (err)
1147 goto cleanup;
1148
1149 }
1150
1151
1152 k = depth - at - 1;
1153 if (unlikely(k < 0)) {
1154 EXT4_ERROR_INODE(inode, "k %d < 0!", k);
1155 err = -EFSCORRUPTED;
1156 goto cleanup;
1157 }
1158 if (k)
1159 ext_debug("create %d intermediate indices\n", k);
1160
1161
1162 i = depth - 1;
1163 while (k--) {
1164 oldblock = newblock;
1165 newblock = ablocks[--a];
1166 bh = sb_getblk(inode->i_sb, newblock);
1167 if (unlikely(!bh)) {
1168 err = -ENOMEM;
1169 goto cleanup;
1170 }
1171 lock_buffer(bh);
1172
1173 err = ext4_journal_get_create_access(handle, bh);
1174 if (err)
1175 goto cleanup;
1176
1177 neh = ext_block_hdr(bh);
1178 neh->eh_entries = cpu_to_le16(1);
1179 neh->eh_magic = EXT4_EXT_MAGIC;
1180 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1181 neh->eh_depth = cpu_to_le16(depth - i);
1182 fidx = EXT_FIRST_INDEX(neh);
1183 fidx->ei_block = border;
1184 ext4_idx_store_pblock(fidx, oldblock);
1185
1186 ext_debug("int.index at %d (block %llu): %u -> %llu\n",
1187 i, newblock, le32_to_cpu(border), oldblock);
1188
1189
1190 if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
1191 EXT_LAST_INDEX(path[i].p_hdr))) {
1192 EXT4_ERROR_INODE(inode,
1193 "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
1194 le32_to_cpu(path[i].p_ext->ee_block));
1195 err = -EFSCORRUPTED;
1196 goto cleanup;
1197 }
1198
1199 m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
1200 ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
1201 EXT_MAX_INDEX(path[i].p_hdr));
1202 ext4_ext_show_move(inode, path, newblock, i);
1203 if (m) {
1204 memmove(++fidx, path[i].p_idx,
1205 sizeof(struct ext4_extent_idx) * m);
1206 le16_add_cpu(&neh->eh_entries, m);
1207 }
1208 ext4_extent_block_csum_set(inode, neh);
1209 set_buffer_uptodate(bh);
1210 unlock_buffer(bh);
1211
1212 err = ext4_handle_dirty_metadata(handle, inode, bh);
1213 if (err)
1214 goto cleanup;
1215 brelse(bh);
1216 bh = NULL;
1217
1218
1219 if (m) {
1220 err = ext4_ext_get_access(handle, inode, path + i);
1221 if (err)
1222 goto cleanup;
1223 le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
1224 err = ext4_ext_dirty(handle, inode, path + i);
1225 if (err)
1226 goto cleanup;
1227 }
1228
1229 i--;
1230 }
1231
1232
1233 err = ext4_ext_insert_index(handle, inode, path + at,
1234 le32_to_cpu(border), newblock);
1235
1236cleanup:
1237 if (bh) {
1238 if (buffer_locked(bh))
1239 unlock_buffer(bh);
1240 brelse(bh);
1241 }
1242
1243 if (err) {
1244
1245 for (i = 0; i < depth; i++) {
1246 if (!ablocks[i])
1247 continue;
1248 ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
1249 EXT4_FREE_BLOCKS_METADATA);
1250 }
1251 }
1252 kfree(ablocks);
1253
1254 return err;
1255}
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
1266 unsigned int flags)
1267{
1268 struct ext4_extent_header *neh;
1269 struct buffer_head *bh;
1270 ext4_fsblk_t newblock, goal = 0;
1271 struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
1272 int err = 0;
1273
1274
1275 if (ext_depth(inode))
1276 goal = ext4_idx_pblock(EXT_FIRST_INDEX(ext_inode_hdr(inode)));
1277 if (goal > le32_to_cpu(es->s_first_data_block)) {
1278 flags |= EXT4_MB_HINT_TRY_GOAL;
1279 goal--;
1280 } else
1281 goal = ext4_inode_to_goal_block(inode);
1282 newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
1283 NULL, &err);
1284 if (newblock == 0)
1285 return err;
1286
1287 bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1288 if (unlikely(!bh))
1289 return -ENOMEM;
1290 lock_buffer(bh);
1291
1292 err = ext4_journal_get_create_access(handle, bh);
1293 if (err) {
1294 unlock_buffer(bh);
1295 goto out;
1296 }
1297
1298
1299 memmove(bh->b_data, EXT4_I(inode)->i_data,
1300 sizeof(EXT4_I(inode)->i_data));
1301
1302
1303 neh = ext_block_hdr(bh);
1304
1305
1306 if (ext_depth(inode))
1307 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1308 else
1309 neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1310 neh->eh_magic = EXT4_EXT_MAGIC;
1311 ext4_extent_block_csum_set(inode, neh);
1312 set_buffer_uptodate(bh);
1313 unlock_buffer(bh);
1314
1315 err = ext4_handle_dirty_metadata(handle, inode, bh);
1316 if (err)
1317 goto out;
1318
1319
1320 neh = ext_inode_hdr(inode);
1321 neh->eh_entries = cpu_to_le16(1);
1322 ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock);
1323 if (neh->eh_depth == 0) {
1324
1325 neh->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
1326 EXT_FIRST_INDEX(neh)->ei_block =
1327 EXT_FIRST_EXTENT(neh)->ee_block;
1328 }
1329 ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
1330 le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
1331 le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
1332 ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
1333
1334 le16_add_cpu(&neh->eh_depth, 1);
1335 ext4_mark_inode_dirty(handle, inode);
1336out:
1337 brelse(bh);
1338
1339 return err;
1340}
1341
1342
1343
1344
1345
1346
1347static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1348 unsigned int mb_flags,
1349 unsigned int gb_flags,
1350 struct ext4_ext_path **ppath,
1351 struct ext4_extent *newext)
1352{
1353 struct ext4_ext_path *path = *ppath;
1354 struct ext4_ext_path *curp;
1355 int depth, i, err = 0;
1356
1357repeat:
1358 i = depth = ext_depth(inode);
1359
1360
1361 curp = path + depth;
1362 while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
1363 i--;
1364 curp--;
1365 }
1366
1367
1368
1369 if (EXT_HAS_FREE_INDEX(curp)) {
1370
1371
1372 err = ext4_ext_split(handle, inode, mb_flags, path, newext, i);
1373 if (err)
1374 goto out;
1375
1376
1377 path = ext4_find_extent(inode,
1378 (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1379 ppath, gb_flags);
1380 if (IS_ERR(path))
1381 err = PTR_ERR(path);
1382 } else {
1383
1384 err = ext4_ext_grow_indepth(handle, inode, mb_flags);
1385 if (err)
1386 goto out;
1387
1388
1389 path = ext4_find_extent(inode,
1390 (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1391 ppath, gb_flags);
1392 if (IS_ERR(path)) {
1393 err = PTR_ERR(path);
1394 goto out;
1395 }
1396
1397
1398
1399
1400
1401 depth = ext_depth(inode);
1402 if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1403
1404 goto repeat;
1405 }
1406 }
1407
1408out:
1409 return err;
1410}
1411
1412
1413
1414
1415
1416
1417
1418
1419static int ext4_ext_search_left(struct inode *inode,
1420 struct ext4_ext_path *path,
1421 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1422{
1423 struct ext4_extent_idx *ix;
1424 struct ext4_extent *ex;
1425 int depth, ee_len;
1426
1427 if (unlikely(path == NULL)) {
1428 EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1429 return -EFSCORRUPTED;
1430 }
1431 depth = path->p_depth;
1432 *phys = 0;
1433
1434 if (depth == 0 && path->p_ext == NULL)
1435 return 0;
1436
1437
1438
1439
1440
1441 ex = path[depth].p_ext;
1442 ee_len = ext4_ext_get_actual_len(ex);
1443 if (*logical < le32_to_cpu(ex->ee_block)) {
1444 if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1445 EXT4_ERROR_INODE(inode,
1446 "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
1447 *logical, le32_to_cpu(ex->ee_block));
1448 return -EFSCORRUPTED;
1449 }
1450 while (--depth >= 0) {
1451 ix = path[depth].p_idx;
1452 if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1453 EXT4_ERROR_INODE(inode,
1454 "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
1455 ix != NULL ? le32_to_cpu(ix->ei_block) : 0,
1456 EXT_FIRST_INDEX(path[depth].p_hdr) != NULL ?
1457 le32_to_cpu(EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block) : 0,
1458 depth);
1459 return -EFSCORRUPTED;
1460 }
1461 }
1462 return 0;
1463 }
1464
1465 if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1466 EXT4_ERROR_INODE(inode,
1467 "logical %d < ee_block %d + ee_len %d!",
1468 *logical, le32_to_cpu(ex->ee_block), ee_len);
1469 return -EFSCORRUPTED;
1470 }
1471
1472 *logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1473 *phys = ext4_ext_pblock(ex) + ee_len - 1;
1474 return 0;
1475}
1476
1477
1478
1479
1480
1481
1482
1483
1484static int ext4_ext_search_right(struct inode *inode,
1485 struct ext4_ext_path *path,
1486 ext4_lblk_t *logical, ext4_fsblk_t *phys,
1487 struct ext4_extent **ret_ex)
1488{
1489 struct buffer_head *bh = NULL;
1490 struct ext4_extent_header *eh;
1491 struct ext4_extent_idx *ix;
1492 struct ext4_extent *ex;
1493 ext4_fsblk_t block;
1494 int depth;
1495 int ee_len;
1496
1497 if (unlikely(path == NULL)) {
1498 EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1499 return -EFSCORRUPTED;
1500 }
1501 depth = path->p_depth;
1502 *phys = 0;
1503
1504 if (depth == 0 && path->p_ext == NULL)
1505 return 0;
1506
1507
1508
1509
1510
1511 ex = path[depth].p_ext;
1512 ee_len = ext4_ext_get_actual_len(ex);
1513 if (*logical < le32_to_cpu(ex->ee_block)) {
1514 if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1515 EXT4_ERROR_INODE(inode,
1516 "first_extent(path[%d].p_hdr) != ex",
1517 depth);
1518 return -EFSCORRUPTED;
1519 }
1520 while (--depth >= 0) {
1521 ix = path[depth].p_idx;
1522 if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1523 EXT4_ERROR_INODE(inode,
1524 "ix != EXT_FIRST_INDEX *logical %d!",
1525 *logical);
1526 return -EFSCORRUPTED;
1527 }
1528 }
1529 goto found_extent;
1530 }
1531
1532 if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1533 EXT4_ERROR_INODE(inode,
1534 "logical %d < ee_block %d + ee_len %d!",
1535 *logical, le32_to_cpu(ex->ee_block), ee_len);
1536 return -EFSCORRUPTED;
1537 }
1538
1539 if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
1540
1541 ex++;
1542 goto found_extent;
1543 }
1544
1545
1546 while (--depth >= 0) {
1547 ix = path[depth].p_idx;
1548 if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
1549 goto got_index;
1550 }
1551
1552
1553 return 0;
1554
1555got_index:
1556
1557
1558
1559 ix++;
1560 block = ext4_idx_pblock(ix);
1561 while (++depth < path->p_depth) {
1562
1563 bh = read_extent_tree_block(inode, block,
1564 path->p_depth - depth, 0);
1565 if (IS_ERR(bh))
1566 return PTR_ERR(bh);
1567 eh = ext_block_hdr(bh);
1568 ix = EXT_FIRST_INDEX(eh);
1569 block = ext4_idx_pblock(ix);
1570 put_bh(bh);
1571 }
1572
1573 bh = read_extent_tree_block(inode, block, path->p_depth - depth, 0);
1574 if (IS_ERR(bh))
1575 return PTR_ERR(bh);
1576 eh = ext_block_hdr(bh);
1577 ex = EXT_FIRST_EXTENT(eh);
1578found_extent:
1579 *logical = le32_to_cpu(ex->ee_block);
1580 *phys = ext4_ext_pblock(ex);
1581 *ret_ex = ex;
1582 if (bh)
1583 put_bh(bh);
1584 return 0;
1585}
1586
1587
1588
1589
1590
1591
1592
1593
1594ext4_lblk_t
1595ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1596{
1597 int depth;
1598
1599 BUG_ON(path == NULL);
1600 depth = path->p_depth;
1601
1602 if (depth == 0 && path->p_ext == NULL)
1603 return EXT_MAX_BLOCKS;
1604
1605 while (depth >= 0) {
1606 if (depth == path->p_depth) {
1607
1608 if (path[depth].p_ext &&
1609 path[depth].p_ext !=
1610 EXT_LAST_EXTENT(path[depth].p_hdr))
1611 return le32_to_cpu(path[depth].p_ext[1].ee_block);
1612 } else {
1613
1614 if (path[depth].p_idx !=
1615 EXT_LAST_INDEX(path[depth].p_hdr))
1616 return le32_to_cpu(path[depth].p_idx[1].ei_block);
1617 }
1618 depth--;
1619 }
1620
1621 return EXT_MAX_BLOCKS;
1622}
1623
1624
1625
1626
1627
1628static ext4_lblk_t ext4_ext_next_leaf_block(struct ext4_ext_path *path)
1629{
1630 int depth;
1631
1632 BUG_ON(path == NULL);
1633 depth = path->p_depth;
1634
1635
1636 if (depth == 0)
1637 return EXT_MAX_BLOCKS;
1638
1639
1640 depth--;
1641
1642 while (depth >= 0) {
1643 if (path[depth].p_idx !=
1644 EXT_LAST_INDEX(path[depth].p_hdr))
1645 return (ext4_lblk_t)
1646 le32_to_cpu(path[depth].p_idx[1].ei_block);
1647 depth--;
1648 }
1649
1650 return EXT_MAX_BLOCKS;
1651}
1652
1653
1654
1655
1656
1657
1658
1659static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
1660 struct ext4_ext_path *path)
1661{
1662 struct ext4_extent_header *eh;
1663 int depth = ext_depth(inode);
1664 struct ext4_extent *ex;
1665 __le32 border;
1666 int k, err = 0;
1667
1668 eh = path[depth].p_hdr;
1669 ex = path[depth].p_ext;
1670
1671 if (unlikely(ex == NULL || eh == NULL)) {
1672 EXT4_ERROR_INODE(inode,
1673 "ex %p == NULL or eh %p == NULL", ex, eh);
1674 return -EFSCORRUPTED;
1675 }
1676
1677 if (depth == 0) {
1678
1679 return 0;
1680 }
1681
1682 if (ex != EXT_FIRST_EXTENT(eh)) {
1683
1684 return 0;
1685 }
1686
1687
1688
1689
1690 k = depth - 1;
1691 border = path[depth].p_ext->ee_block;
1692 err = ext4_ext_get_access(handle, inode, path + k);
1693 if (err)
1694 return err;
1695 path[k].p_idx->ei_block = border;
1696 err = ext4_ext_dirty(handle, inode, path + k);
1697 if (err)
1698 return err;
1699
1700 while (k--) {
1701
1702 if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1703 break;
1704 err = ext4_ext_get_access(handle, inode, path + k);
1705 if (err)
1706 break;
1707 path[k].p_idx->ei_block = border;
1708 err = ext4_ext_dirty(handle, inode, path + k);
1709 if (err)
1710 break;
1711 }
1712
1713 return err;
1714}
1715
1716int
1717ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
1718 struct ext4_extent *ex2)
1719{
1720 unsigned short ext1_ee_len, ext2_ee_len;
1721
1722 if (ext4_ext_is_unwritten(ex1) != ext4_ext_is_unwritten(ex2))
1723 return 0;
1724
1725 ext1_ee_len = ext4_ext_get_actual_len(ex1);
1726 ext2_ee_len = ext4_ext_get_actual_len(ex2);
1727
1728 if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
1729 le32_to_cpu(ex2->ee_block))
1730 return 0;
1731
1732
1733
1734
1735
1736
1737 if (ext1_ee_len + ext2_ee_len > EXT_INIT_MAX_LEN)
1738 return 0;
1739
1740
1741
1742
1743
1744
1745 if (ext4_ext_is_unwritten(ex1) &&
1746 (ext4_test_inode_state(inode, EXT4_STATE_DIO_UNWRITTEN) ||
1747 atomic_read(&EXT4_I(inode)->i_unwritten) ||
1748 (ext1_ee_len + ext2_ee_len > EXT_UNWRITTEN_MAX_LEN)))
1749 return 0;
1750#ifdef AGGRESSIVE_TEST
1751 if (ext1_ee_len >= 4)
1752 return 0;
1753#endif
1754
1755 if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
1756 return 1;
1757 return 0;
1758}
1759
1760
1761
1762
1763
1764
1765
1766
1767static int ext4_ext_try_to_merge_right(struct inode *inode,
1768 struct ext4_ext_path *path,
1769 struct ext4_extent *ex)
1770{
1771 struct ext4_extent_header *eh;
1772 unsigned int depth, len;
1773 int merge_done = 0, unwritten;
1774
1775 depth = ext_depth(inode);
1776 BUG_ON(path[depth].p_hdr == NULL);
1777 eh = path[depth].p_hdr;
1778
1779 while (ex < EXT_LAST_EXTENT(eh)) {
1780 if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
1781 break;
1782
1783 unwritten = ext4_ext_is_unwritten(ex);
1784 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1785 + ext4_ext_get_actual_len(ex + 1));
1786 if (unwritten)
1787 ext4_ext_mark_unwritten(ex);
1788
1789 if (ex + 1 < EXT_LAST_EXTENT(eh)) {
1790 len = (EXT_LAST_EXTENT(eh) - ex - 1)
1791 * sizeof(struct ext4_extent);
1792 memmove(ex + 1, ex + 2, len);
1793 }
1794 le16_add_cpu(&eh->eh_entries, -1);
1795 merge_done = 1;
1796 WARN_ON(eh->eh_entries == 0);
1797 if (!eh->eh_entries)
1798 EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
1799 }
1800
1801 return merge_done;
1802}
1803
1804
1805
1806
1807
1808static void ext4_ext_try_to_merge_up(handle_t *handle,
1809 struct inode *inode,
1810 struct ext4_ext_path *path)
1811{
1812 size_t s;
1813 unsigned max_root = ext4_ext_space_root(inode, 0);
1814 ext4_fsblk_t blk;
1815
1816 if ((path[0].p_depth != 1) ||
1817 (le16_to_cpu(path[0].p_hdr->eh_entries) != 1) ||
1818 (le16_to_cpu(path[1].p_hdr->eh_entries) > max_root))
1819 return;
1820
1821
1822
1823
1824
1825
1826 if (ext4_journal_extend(handle, 2))
1827 return;
1828
1829
1830
1831
1832 blk = ext4_idx_pblock(path[0].p_idx);
1833 s = le16_to_cpu(path[1].p_hdr->eh_entries) *
1834 sizeof(struct ext4_extent_idx);
1835 s += sizeof(struct ext4_extent_header);
1836
1837 path[1].p_maxdepth = path[0].p_maxdepth;
1838 memcpy(path[0].p_hdr, path[1].p_hdr, s);
1839 path[0].p_depth = 0;
1840 path[0].p_ext = EXT_FIRST_EXTENT(path[0].p_hdr) +
1841 (path[1].p_ext - EXT_FIRST_EXTENT(path[1].p_hdr));
1842 path[0].p_hdr->eh_max = cpu_to_le16(max_root);
1843
1844 brelse(path[1].p_bh);
1845 ext4_free_blocks(handle, inode, NULL, blk, 1,
1846 EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
1847}
1848
1849
1850
1851
1852
1853static void ext4_ext_try_to_merge(handle_t *handle,
1854 struct inode *inode,
1855 struct ext4_ext_path *path,
1856 struct ext4_extent *ex) {
1857 struct ext4_extent_header *eh;
1858 unsigned int depth;
1859 int merge_done = 0;
1860
1861 depth = ext_depth(inode);
1862 BUG_ON(path[depth].p_hdr == NULL);
1863 eh = path[depth].p_hdr;
1864
1865 if (ex > EXT_FIRST_EXTENT(eh))
1866 merge_done = ext4_ext_try_to_merge_right(inode, path, ex - 1);
1867
1868 if (!merge_done)
1869 (void) ext4_ext_try_to_merge_right(inode, path, ex);
1870
1871 ext4_ext_try_to_merge_up(handle, inode, path);
1872}
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882static unsigned int ext4_ext_check_overlap(struct ext4_sb_info *sbi,
1883 struct inode *inode,
1884 struct ext4_extent *newext,
1885 struct ext4_ext_path *path)
1886{
1887 ext4_lblk_t b1, b2;
1888 unsigned int depth, len1;
1889 unsigned int ret = 0;
1890
1891 b1 = le32_to_cpu(newext->ee_block);
1892 len1 = ext4_ext_get_actual_len(newext);
1893 depth = ext_depth(inode);
1894 if (!path[depth].p_ext)
1895 goto out;
1896 b2 = EXT4_LBLK_CMASK(sbi, le32_to_cpu(path[depth].p_ext->ee_block));
1897
1898
1899
1900
1901
1902 if (b2 < b1) {
1903 b2 = ext4_ext_next_allocated_block(path);
1904 if (b2 == EXT_MAX_BLOCKS)
1905 goto out;
1906 b2 = EXT4_LBLK_CMASK(sbi, b2);
1907 }
1908
1909
1910 if (b1 + len1 < b1) {
1911 len1 = EXT_MAX_BLOCKS - b1;
1912 newext->ee_len = cpu_to_le16(len1);
1913 ret = 1;
1914 }
1915
1916
1917 if (b1 + len1 > b2) {
1918 newext->ee_len = cpu_to_le16(b2 - b1);
1919 ret = 1;
1920 }
1921out:
1922 return ret;
1923}
1924
1925
1926
1927
1928
1929
1930
1931int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1932 struct ext4_ext_path **ppath,
1933 struct ext4_extent *newext, int gb_flags)
1934{
1935 struct ext4_ext_path *path = *ppath;
1936 struct ext4_extent_header *eh;
1937 struct ext4_extent *ex, *fex;
1938 struct ext4_extent *nearex;
1939 struct ext4_ext_path *npath = NULL;
1940 int depth, len, err;
1941 ext4_lblk_t next;
1942 int mb_flags = 0, unwritten;
1943
1944 if (gb_flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
1945 mb_flags |= EXT4_MB_DELALLOC_RESERVED;
1946 if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
1947 EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
1948 return -EFSCORRUPTED;
1949 }
1950 depth = ext_depth(inode);
1951 ex = path[depth].p_ext;
1952 eh = path[depth].p_hdr;
1953 if (unlikely(path[depth].p_hdr == NULL)) {
1954 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
1955 return -EFSCORRUPTED;
1956 }
1957
1958
1959 if (ex && !(gb_flags & EXT4_GET_BLOCKS_PRE_IO)) {
1960
1961
1962
1963
1964
1965
1966
1967
1968 if (ex < EXT_LAST_EXTENT(eh) &&
1969 (le32_to_cpu(ex->ee_block) +
1970 ext4_ext_get_actual_len(ex) <
1971 le32_to_cpu(newext->ee_block))) {
1972 ex += 1;
1973 goto prepend;
1974 } else if ((ex > EXT_FIRST_EXTENT(eh)) &&
1975 (le32_to_cpu(newext->ee_block) +
1976 ext4_ext_get_actual_len(newext) <
1977 le32_to_cpu(ex->ee_block)))
1978 ex -= 1;
1979
1980
1981 if (ext4_can_extents_be_merged(inode, ex, newext)) {
1982 ext_debug("append [%d]%d block to %u:[%d]%d"
1983 "(from %llu)\n",
1984 ext4_ext_is_unwritten(newext),
1985 ext4_ext_get_actual_len(newext),
1986 le32_to_cpu(ex->ee_block),
1987 ext4_ext_is_unwritten(ex),
1988 ext4_ext_get_actual_len(ex),
1989 ext4_ext_pblock(ex));
1990 err = ext4_ext_get_access(handle, inode,
1991 path + depth);
1992 if (err)
1993 return err;
1994 unwritten = ext4_ext_is_unwritten(ex);
1995 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1996 + ext4_ext_get_actual_len(newext));
1997 if (unwritten)
1998 ext4_ext_mark_unwritten(ex);
1999 eh = path[depth].p_hdr;
2000 nearex = ex;
2001 goto merge;
2002 }
2003
2004prepend:
2005
2006 if (ext4_can_extents_be_merged(inode, newext, ex)) {
2007 ext_debug("prepend %u[%d]%d block to %u:[%d]%d"
2008 "(from %llu)\n",
2009 le32_to_cpu(newext->ee_block),
2010 ext4_ext_is_unwritten(newext),
2011 ext4_ext_get_actual_len(newext),
2012 le32_to_cpu(ex->ee_block),
2013 ext4_ext_is_unwritten(ex),
2014 ext4_ext_get_actual_len(ex),
2015 ext4_ext_pblock(ex));
2016 err = ext4_ext_get_access(handle, inode,
2017 path + depth);
2018 if (err)
2019 return err;
2020
2021 unwritten = ext4_ext_is_unwritten(ex);
2022 ex->ee_block = newext->ee_block;
2023 ext4_ext_store_pblock(ex, ext4_ext_pblock(newext));
2024 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
2025 + ext4_ext_get_actual_len(newext));
2026 if (unwritten)
2027 ext4_ext_mark_unwritten(ex);
2028 eh = path[depth].p_hdr;
2029 nearex = ex;
2030 goto merge;
2031 }
2032 }
2033
2034 depth = ext_depth(inode);
2035 eh = path[depth].p_hdr;
2036 if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
2037 goto has_space;
2038
2039
2040 fex = EXT_LAST_EXTENT(eh);
2041 next = EXT_MAX_BLOCKS;
2042 if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))
2043 next = ext4_ext_next_leaf_block(path);
2044 if (next != EXT_MAX_BLOCKS) {
2045 ext_debug("next leaf block - %u\n", next);
2046 BUG_ON(npath != NULL);
2047 npath = ext4_find_extent(inode, next, NULL, 0);
2048 if (IS_ERR(npath))
2049 return PTR_ERR(npath);
2050 BUG_ON(npath->p_depth != path->p_depth);
2051 eh = npath[depth].p_hdr;
2052 if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
2053 ext_debug("next leaf isn't full(%d)\n",
2054 le16_to_cpu(eh->eh_entries));
2055 path = npath;
2056 goto has_space;
2057 }
2058 ext_debug("next leaf has no free space(%d,%d)\n",
2059 le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
2060 }
2061
2062
2063
2064
2065
2066 if (gb_flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
2067 mb_flags |= EXT4_MB_USE_RESERVED;
2068 err = ext4_ext_create_new_leaf(handle, inode, mb_flags, gb_flags,
2069 ppath, newext);
2070 if (err)
2071 goto cleanup;
2072 depth = ext_depth(inode);
2073 eh = path[depth].p_hdr;
2074
2075has_space:
2076 nearex = path[depth].p_ext;
2077
2078 err = ext4_ext_get_access(handle, inode, path + depth);
2079 if (err)
2080 goto cleanup;
2081
2082 if (!nearex) {
2083
2084 ext_debug("first extent in the leaf: %u:%llu:[%d]%d\n",
2085 le32_to_cpu(newext->ee_block),
2086 ext4_ext_pblock(newext),
2087 ext4_ext_is_unwritten(newext),
2088 ext4_ext_get_actual_len(newext));
2089 nearex = EXT_FIRST_EXTENT(eh);
2090 } else {
2091 if (le32_to_cpu(newext->ee_block)
2092 > le32_to_cpu(nearex->ee_block)) {
2093
2094 ext_debug("insert %u:%llu:[%d]%d before: "
2095 "nearest %p\n",
2096 le32_to_cpu(newext->ee_block),
2097 ext4_ext_pblock(newext),
2098 ext4_ext_is_unwritten(newext),
2099 ext4_ext_get_actual_len(newext),
2100 nearex);
2101 nearex++;
2102 } else {
2103
2104 BUG_ON(newext->ee_block == nearex->ee_block);
2105 ext_debug("insert %u:%llu:[%d]%d after: "
2106 "nearest %p\n",
2107 le32_to_cpu(newext->ee_block),
2108 ext4_ext_pblock(newext),
2109 ext4_ext_is_unwritten(newext),
2110 ext4_ext_get_actual_len(newext),
2111 nearex);
2112 }
2113 len = EXT_LAST_EXTENT(eh) - nearex + 1;
2114 if (len > 0) {
2115 ext_debug("insert %u:%llu:[%d]%d: "
2116 "move %d extents from 0x%p to 0x%p\n",
2117 le32_to_cpu(newext->ee_block),
2118 ext4_ext_pblock(newext),
2119 ext4_ext_is_unwritten(newext),
2120 ext4_ext_get_actual_len(newext),
2121 len, nearex, nearex + 1);
2122 memmove(nearex + 1, nearex,
2123 len * sizeof(struct ext4_extent));
2124 }
2125 }
2126
2127 le16_add_cpu(&eh->eh_entries, 1);
2128 path[depth].p_ext = nearex;
2129 nearex->ee_block = newext->ee_block;
2130 ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
2131 nearex->ee_len = newext->ee_len;
2132
2133merge:
2134
2135 if (!(gb_flags & EXT4_GET_BLOCKS_PRE_IO))
2136 ext4_ext_try_to_merge(handle, inode, path, nearex);
2137
2138
2139
2140 err = ext4_ext_correct_indexes(handle, inode, path);
2141 if (err)
2142 goto cleanup;
2143
2144 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
2145
2146cleanup:
2147 ext4_ext_drop_refs(npath);
2148 kfree(npath);
2149 return err;
2150}
2151
2152static int ext4_fill_fiemap_extents(struct inode *inode,
2153 ext4_lblk_t block, ext4_lblk_t num,
2154 struct fiemap_extent_info *fieinfo)
2155{
2156 struct ext4_ext_path *path = NULL;
2157 struct ext4_extent *ex;
2158 struct extent_status es;
2159 ext4_lblk_t next, next_del, start = 0, end = 0;
2160 ext4_lblk_t last = block + num;
2161 int exists, depth = 0, err = 0;
2162 unsigned int flags = 0;
2163 unsigned char blksize_bits = inode->i_sb->s_blocksize_bits;
2164
2165 while (block < last && block != EXT_MAX_BLOCKS) {
2166 num = last - block;
2167
2168 down_read(&EXT4_I(inode)->i_data_sem);
2169
2170 path = ext4_find_extent(inode, block, &path, 0);
2171 if (IS_ERR(path)) {
2172 up_read(&EXT4_I(inode)->i_data_sem);
2173 err = PTR_ERR(path);
2174 path = NULL;
2175 break;
2176 }
2177
2178 depth = ext_depth(inode);
2179 if (unlikely(path[depth].p_hdr == NULL)) {
2180 up_read(&EXT4_I(inode)->i_data_sem);
2181 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2182 err = -EFSCORRUPTED;
2183 break;
2184 }
2185 ex = path[depth].p_ext;
2186 next = ext4_ext_next_allocated_block(path);
2187
2188 flags = 0;
2189 exists = 0;
2190 if (!ex) {
2191
2192
2193 start = block;
2194 end = block + num;
2195 } else if (le32_to_cpu(ex->ee_block) > block) {
2196
2197 start = block;
2198 end = le32_to_cpu(ex->ee_block);
2199 if (block + num < end)
2200 end = block + num;
2201 } else if (block >= le32_to_cpu(ex->ee_block)
2202 + ext4_ext_get_actual_len(ex)) {
2203
2204 start = block;
2205 end = block + num;
2206 if (end >= next)
2207 end = next;
2208 } else if (block >= le32_to_cpu(ex->ee_block)) {
2209
2210
2211
2212
2213 start = block;
2214 end = le32_to_cpu(ex->ee_block)
2215 + ext4_ext_get_actual_len(ex);
2216 if (block + num < end)
2217 end = block + num;
2218 exists = 1;
2219 } else {
2220 BUG();
2221 }
2222 BUG_ON(end <= start);
2223
2224 if (!exists) {
2225 es.es_lblk = start;
2226 es.es_len = end - start;
2227 es.es_pblk = 0;
2228 } else {
2229 es.es_lblk = le32_to_cpu(ex->ee_block);
2230 es.es_len = ext4_ext_get_actual_len(ex);
2231 es.es_pblk = ext4_ext_pblock(ex);
2232 if (ext4_ext_is_unwritten(ex))
2233 flags |= FIEMAP_EXTENT_UNWRITTEN;
2234 }
2235
2236
2237
2238
2239
2240
2241 next_del = ext4_find_delayed_extent(inode, &es);
2242 if (!exists && next_del) {
2243 exists = 1;
2244 flags |= (FIEMAP_EXTENT_DELALLOC |
2245 FIEMAP_EXTENT_UNKNOWN);
2246 }
2247 up_read(&EXT4_I(inode)->i_data_sem);
2248
2249 if (unlikely(es.es_len == 0)) {
2250 EXT4_ERROR_INODE(inode, "es.es_len == 0");
2251 err = -EFSCORRUPTED;
2252 break;
2253 }
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266 if (next == next_del && next == EXT_MAX_BLOCKS) {
2267 flags |= FIEMAP_EXTENT_LAST;
2268 if (unlikely(next_del != EXT_MAX_BLOCKS ||
2269 next != EXT_MAX_BLOCKS)) {
2270 EXT4_ERROR_INODE(inode,
2271 "next extent == %u, next "
2272 "delalloc extent = %u",
2273 next, next_del);
2274 err = -EFSCORRUPTED;
2275 break;
2276 }
2277 }
2278
2279 if (exists) {
2280 err = fiemap_fill_next_extent(fieinfo,
2281 (__u64)es.es_lblk << blksize_bits,
2282 (__u64)es.es_pblk << blksize_bits,
2283 (__u64)es.es_len << blksize_bits,
2284 flags);
2285 if (err < 0)
2286 break;
2287 if (err == 1) {
2288 err = 0;
2289 break;
2290 }
2291 }
2292
2293 block = es.es_lblk + es.es_len;
2294 }
2295
2296 ext4_ext_drop_refs(path);
2297 kfree(path);
2298 return err;
2299}
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314static ext4_lblk_t ext4_ext_determine_hole(struct inode *inode,
2315 struct ext4_ext_path *path,
2316 ext4_lblk_t *lblk)
2317{
2318 int depth = ext_depth(inode);
2319 struct ext4_extent *ex;
2320 ext4_lblk_t len;
2321
2322 ex = path[depth].p_ext;
2323 if (ex == NULL) {
2324
2325 *lblk = 0;
2326 len = EXT_MAX_BLOCKS;
2327 } else if (*lblk < le32_to_cpu(ex->ee_block)) {
2328 len = le32_to_cpu(ex->ee_block) - *lblk;
2329 } else if (*lblk >= le32_to_cpu(ex->ee_block)
2330 + ext4_ext_get_actual_len(ex)) {
2331 ext4_lblk_t next;
2332
2333 *lblk = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
2334 next = ext4_ext_next_allocated_block(path);
2335 BUG_ON(next == *lblk);
2336 len = next - *lblk;
2337 } else {
2338 BUG();
2339 }
2340 return len;
2341}
2342
2343
2344
2345
2346
2347
2348static void
2349ext4_ext_put_gap_in_cache(struct inode *inode, ext4_lblk_t hole_start,
2350 ext4_lblk_t hole_len)
2351{
2352 struct extent_status es;
2353
2354 ext4_es_find_extent_range(inode, &ext4_es_is_delayed, hole_start,
2355 hole_start + hole_len - 1, &es);
2356 if (es.es_len) {
2357
2358 if (es.es_lblk <= hole_start)
2359 return;
2360 hole_len = min(es.es_lblk - hole_start, hole_len);
2361 }
2362 ext_debug(" -> %u:%u\n", hole_start, hole_len);
2363 ext4_es_insert_extent(inode, hole_start, hole_len, ~0,
2364 EXTENT_STATUS_HOLE);
2365}
2366
2367
2368
2369
2370
2371static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
2372 struct ext4_ext_path *path, int depth)
2373{
2374 int err;
2375 ext4_fsblk_t leaf;
2376
2377
2378 depth--;
2379 path = path + depth;
2380 leaf = ext4_idx_pblock(path->p_idx);
2381 if (unlikely(path->p_hdr->eh_entries == 0)) {
2382 EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
2383 return -EFSCORRUPTED;
2384 }
2385 err = ext4_ext_get_access(handle, inode, path);
2386 if (err)
2387 return err;
2388
2389 if (path->p_idx != EXT_LAST_INDEX(path->p_hdr)) {
2390 int len = EXT_LAST_INDEX(path->p_hdr) - path->p_idx;
2391 len *= sizeof(struct ext4_extent_idx);
2392 memmove(path->p_idx, path->p_idx + 1, len);
2393 }
2394
2395 le16_add_cpu(&path->p_hdr->eh_entries, -1);
2396 err = ext4_ext_dirty(handle, inode, path);
2397 if (err)
2398 return err;
2399 ext_debug("index is empty, remove it, free block %llu\n", leaf);
2400 trace_ext4_ext_rm_idx(inode, leaf);
2401
2402 ext4_free_blocks(handle, inode, NULL, leaf, 1,
2403 EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
2404
2405 while (--depth >= 0) {
2406 if (path->p_idx != EXT_FIRST_INDEX(path->p_hdr))
2407 break;
2408 path--;
2409 err = ext4_ext_get_access(handle, inode, path);
2410 if (err)
2411 break;
2412 path->p_idx->ei_block = (path+1)->p_idx->ei_block;
2413 err = ext4_ext_dirty(handle, inode, path);
2414 if (err)
2415 break;
2416 }
2417 return err;
2418}
2419
2420
2421
2422
2423
2424
2425
2426
2427int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
2428 struct ext4_ext_path *path)
2429{
2430 if (path) {
2431 int depth = ext_depth(inode);
2432 int ret = 0;
2433
2434
2435 if (le16_to_cpu(path[depth].p_hdr->eh_entries)
2436 < le16_to_cpu(path[depth].p_hdr->eh_max)) {
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447 ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
2448 return ret;
2449 }
2450 }
2451
2452 return ext4_chunk_trans_blocks(inode, nrblocks);
2453}
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464int ext4_ext_index_trans_blocks(struct inode *inode, int extents)
2465{
2466 int index;
2467 int depth;
2468
2469
2470 if (ext4_has_inline_data(inode))
2471 return 1;
2472
2473 depth = ext_depth(inode);
2474
2475 if (extents <= 1)
2476 index = depth * 2;
2477 else
2478 index = depth * 3;
2479
2480 return index;
2481}
2482
2483static inline int get_default_free_blocks_flags(struct inode *inode)
2484{
2485 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) ||
2486 ext4_test_inode_flag(inode, EXT4_INODE_EA_INODE))
2487 return EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET;
2488 else if (ext4_should_journal_data(inode))
2489 return EXT4_FREE_BLOCKS_FORGET;
2490 return 0;
2491}
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508static void ext4_rereserve_cluster(struct inode *inode, ext4_lblk_t lblk)
2509{
2510 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2511 struct ext4_inode_info *ei = EXT4_I(inode);
2512
2513 dquot_reclaim_block(inode, EXT4_C2B(sbi, 1));
2514
2515 spin_lock(&ei->i_block_reservation_lock);
2516 ei->i_reserved_data_blocks++;
2517 percpu_counter_add(&sbi->s_dirtyclusters_counter, 1);
2518 spin_unlock(&ei->i_block_reservation_lock);
2519
2520 percpu_counter_add(&sbi->s_freeclusters_counter, 1);
2521 ext4_remove_pending(inode, lblk);
2522}
2523
2524static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
2525 struct ext4_extent *ex,
2526 struct partial_cluster *partial,
2527 ext4_lblk_t from, ext4_lblk_t to)
2528{
2529 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2530 unsigned short ee_len = ext4_ext_get_actual_len(ex);
2531 ext4_fsblk_t last_pblk, pblk;
2532 ext4_lblk_t num;
2533 int flags;
2534
2535
2536 if (from < le32_to_cpu(ex->ee_block) ||
2537 to != le32_to_cpu(ex->ee_block) + ee_len - 1) {
2538 ext4_error(sbi->s_sb,
2539 "strange request: removal(2) %u-%u from %u:%u",
2540 from, to, le32_to_cpu(ex->ee_block), ee_len);
2541 return 0;
2542 }
2543
2544#ifdef EXTENTS_STATS
2545 spin_lock(&sbi->s_ext_stats_lock);
2546 sbi->s_ext_blocks += ee_len;
2547 sbi->s_ext_extents++;
2548 if (ee_len < sbi->s_ext_min)
2549 sbi->s_ext_min = ee_len;
2550 if (ee_len > sbi->s_ext_max)
2551 sbi->s_ext_max = ee_len;
2552 if (ext_depth(inode) > sbi->s_depth_max)
2553 sbi->s_depth_max = ext_depth(inode);
2554 spin_unlock(&sbi->s_ext_stats_lock);
2555#endif
2556
2557 trace_ext4_remove_blocks(inode, ex, from, to, partial);
2558
2559
2560
2561
2562
2563 last_pblk = ext4_ext_pblock(ex) + ee_len - 1;
2564
2565 if (partial->state != initial &&
2566 partial->pclu != EXT4_B2C(sbi, last_pblk)) {
2567 if (partial->state == tofree) {
2568 flags = get_default_free_blocks_flags(inode);
2569 if (ext4_is_pending(inode, partial->lblk))
2570 flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
2571 ext4_free_blocks(handle, inode, NULL,
2572 EXT4_C2B(sbi, partial->pclu),
2573 sbi->s_cluster_ratio, flags);
2574 if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
2575 ext4_rereserve_cluster(inode, partial->lblk);
2576 }
2577 partial->state = initial;
2578 }
2579
2580 num = le32_to_cpu(ex->ee_block) + ee_len - from;
2581 pblk = ext4_ext_pblock(ex) + ee_len - num;
2582
2583
2584
2585
2586
2587
2588
2589 flags = get_default_free_blocks_flags(inode);
2590
2591
2592 if ((EXT4_LBLK_COFF(sbi, to) != sbi->s_cluster_ratio - 1) &&
2593 (EXT4_LBLK_CMASK(sbi, to) >= from) &&
2594 (partial->state != nofree)) {
2595 if (ext4_is_pending(inode, to))
2596 flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
2597 ext4_free_blocks(handle, inode, NULL,
2598 EXT4_PBLK_CMASK(sbi, last_pblk),
2599 sbi->s_cluster_ratio, flags);
2600 if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
2601 ext4_rereserve_cluster(inode, to);
2602 partial->state = initial;
2603 flags = get_default_free_blocks_flags(inode);
2604 }
2605
2606 flags |= EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER;
2607
2608
2609
2610
2611
2612
2613
2614 flags |= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER;
2615 ext4_free_blocks(handle, inode, NULL, pblk, num, flags);
2616
2617
2618 if (partial->state != initial && partial->pclu != EXT4_B2C(sbi, pblk))
2619 partial->state = initial;
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631 if (EXT4_LBLK_COFF(sbi, from) && num == ee_len) {
2632 if (partial->state == initial) {
2633 partial->pclu = EXT4_B2C(sbi, pblk);
2634 partial->lblk = from;
2635 partial->state = tofree;
2636 }
2637 } else {
2638 partial->state = initial;
2639 }
2640
2641 return 0;
2642}
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659static int
2660ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
2661 struct ext4_ext_path *path,
2662 struct partial_cluster *partial,
2663 ext4_lblk_t start, ext4_lblk_t end)
2664{
2665 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2666 int err = 0, correct_index = 0;
2667 int depth = ext_depth(inode), credits;
2668 struct ext4_extent_header *eh;
2669 ext4_lblk_t a, b;
2670 unsigned num;
2671 ext4_lblk_t ex_ee_block;
2672 unsigned short ex_ee_len;
2673 unsigned unwritten = 0;
2674 struct ext4_extent *ex;
2675 ext4_fsblk_t pblk;
2676
2677
2678 ext_debug("truncate since %u in leaf to %u\n", start, end);
2679 if (!path[depth].p_hdr)
2680 path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
2681 eh = path[depth].p_hdr;
2682 if (unlikely(path[depth].p_hdr == NULL)) {
2683 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2684 return -EFSCORRUPTED;
2685 }
2686
2687 ex = path[depth].p_ext;
2688 if (!ex)
2689 ex = EXT_LAST_EXTENT(eh);
2690
2691 ex_ee_block = le32_to_cpu(ex->ee_block);
2692 ex_ee_len = ext4_ext_get_actual_len(ex);
2693
2694 trace_ext4_ext_rm_leaf(inode, start, ex, partial);
2695
2696 while (ex >= EXT_FIRST_EXTENT(eh) &&
2697 ex_ee_block + ex_ee_len > start) {
2698
2699 if (ext4_ext_is_unwritten(ex))
2700 unwritten = 1;
2701 else
2702 unwritten = 0;
2703
2704 ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
2705 unwritten, ex_ee_len);
2706 path[depth].p_ext = ex;
2707
2708 a = ex_ee_block > start ? ex_ee_block : start;
2709 b = ex_ee_block+ex_ee_len - 1 < end ?
2710 ex_ee_block+ex_ee_len - 1 : end;
2711
2712 ext_debug(" border %u:%u\n", a, b);
2713
2714
2715 if (end < ex_ee_block) {
2716
2717
2718
2719
2720
2721
2722
2723 if (sbi->s_cluster_ratio > 1) {
2724 pblk = ext4_ext_pblock(ex);
2725 partial->pclu = EXT4_B2C(sbi, pblk);
2726 partial->state = nofree;
2727 }
2728 ex--;
2729 ex_ee_block = le32_to_cpu(ex->ee_block);
2730 ex_ee_len = ext4_ext_get_actual_len(ex);
2731 continue;
2732 } else if (b != ex_ee_block + ex_ee_len - 1) {
2733 EXT4_ERROR_INODE(inode,
2734 "can not handle truncate %u:%u "
2735 "on extent %u:%u",
2736 start, end, ex_ee_block,
2737 ex_ee_block + ex_ee_len - 1);
2738 err = -EFSCORRUPTED;
2739 goto out;
2740 } else if (a != ex_ee_block) {
2741
2742 num = a - ex_ee_block;
2743 } else {
2744
2745 num = 0;
2746 }
2747
2748
2749
2750
2751
2752
2753 credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
2754 if (ex == EXT_FIRST_EXTENT(eh)) {
2755 correct_index = 1;
2756 credits += (ext_depth(inode)) + 1;
2757 }
2758 credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
2759
2760 err = ext4_ext_truncate_extend_restart(handle, inode, credits);
2761 if (err)
2762 goto out;
2763
2764 err = ext4_ext_get_access(handle, inode, path + depth);
2765 if (err)
2766 goto out;
2767
2768 err = ext4_remove_blocks(handle, inode, ex, partial, a, b);
2769 if (err)
2770 goto out;
2771
2772 if (num == 0)
2773
2774 ext4_ext_store_pblock(ex, 0);
2775
2776 ex->ee_len = cpu_to_le16(num);
2777
2778
2779
2780
2781 if (unwritten && num)
2782 ext4_ext_mark_unwritten(ex);
2783
2784
2785
2786
2787 if (num == 0) {
2788 if (end != EXT_MAX_BLOCKS - 1) {
2789
2790
2791
2792
2793
2794 memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
2795 sizeof(struct ext4_extent));
2796
2797
2798 memset(EXT_LAST_EXTENT(eh), 0,
2799 sizeof(struct ext4_extent));
2800 }
2801 le16_add_cpu(&eh->eh_entries, -1);
2802 }
2803
2804 err = ext4_ext_dirty(handle, inode, path + depth);
2805 if (err)
2806 goto out;
2807
2808 ext_debug("new extent: %u:%u:%llu\n", ex_ee_block, num,
2809 ext4_ext_pblock(ex));
2810 ex--;
2811 ex_ee_block = le32_to_cpu(ex->ee_block);
2812 ex_ee_len = ext4_ext_get_actual_len(ex);
2813 }
2814
2815 if (correct_index && eh->eh_entries)
2816 err = ext4_ext_correct_indexes(handle, inode, path);
2817
2818
2819
2820
2821
2822
2823
2824
2825 if (partial->state == tofree && ex >= EXT_FIRST_EXTENT(eh)) {
2826 pblk = ext4_ext_pblock(ex) + ex_ee_len - 1;
2827 if (partial->pclu != EXT4_B2C(sbi, pblk)) {
2828 int flags = get_default_free_blocks_flags(inode);
2829
2830 if (ext4_is_pending(inode, partial->lblk))
2831 flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
2832 ext4_free_blocks(handle, inode, NULL,
2833 EXT4_C2B(sbi, partial->pclu),
2834 sbi->s_cluster_ratio, flags);
2835 if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
2836 ext4_rereserve_cluster(inode, partial->lblk);
2837 }
2838 partial->state = initial;
2839 }
2840
2841
2842
2843 if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2844 err = ext4_ext_rm_idx(handle, inode, path, depth);
2845
2846out:
2847 return err;
2848}
2849
2850
2851
2852
2853
2854static int
2855ext4_ext_more_to_rm(struct ext4_ext_path *path)
2856{
2857 BUG_ON(path->p_idx == NULL);
2858
2859 if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2860 return 0;
2861
2862
2863
2864
2865
2866 if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2867 return 0;
2868 return 1;
2869}
2870
2871int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
2872 ext4_lblk_t end)
2873{
2874 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2875 int depth = ext_depth(inode);
2876 struct ext4_ext_path *path = NULL;
2877 struct partial_cluster partial;
2878 handle_t *handle;
2879 int i = 0, err = 0;
2880
2881 partial.pclu = 0;
2882 partial.lblk = 0;
2883 partial.state = initial;
2884
2885 ext_debug("truncate since %u to %u\n", start, end);
2886
2887
2888 handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, depth + 1);
2889 if (IS_ERR(handle))
2890 return PTR_ERR(handle);
2891
2892again:
2893 trace_ext4_ext_remove_space(inode, start, end, depth);
2894
2895
2896
2897
2898
2899
2900
2901
2902 if (end < EXT_MAX_BLOCKS - 1) {
2903 struct ext4_extent *ex;
2904 ext4_lblk_t ee_block, ex_end, lblk;
2905 ext4_fsblk_t pblk;
2906
2907
2908 path = ext4_find_extent(inode, end, NULL, EXT4_EX_NOCACHE);
2909 if (IS_ERR(path)) {
2910 ext4_journal_stop(handle);
2911 return PTR_ERR(path);
2912 }
2913 depth = ext_depth(inode);
2914
2915 ex = path[depth].p_ext;
2916 if (!ex) {
2917 if (depth) {
2918 EXT4_ERROR_INODE(inode,
2919 "path[%d].p_hdr == NULL",
2920 depth);
2921 err = -EFSCORRUPTED;
2922 }
2923 goto out;
2924 }
2925
2926 ee_block = le32_to_cpu(ex->ee_block);
2927 ex_end = ee_block + ext4_ext_get_actual_len(ex) - 1;
2928
2929
2930
2931
2932
2933
2934
2935 if (end >= ee_block && end < ex_end) {
2936
2937
2938
2939
2940
2941
2942 if (sbi->s_cluster_ratio > 1) {
2943 pblk = ext4_ext_pblock(ex) + end - ee_block + 2;
2944 partial.pclu = EXT4_B2C(sbi, pblk);
2945 partial.state = nofree;
2946 }
2947
2948
2949
2950
2951
2952
2953
2954 err = ext4_force_split_extent_at(handle, inode, &path,
2955 end + 1, 1);
2956 if (err < 0)
2957 goto out;
2958
2959 } else if (sbi->s_cluster_ratio > 1 && end >= ex_end &&
2960 partial.state == initial) {
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971 lblk = ex_end + 1;
2972 err = ext4_ext_search_right(inode, path, &lblk, &pblk,
2973 &ex);
2974 if (err)
2975 goto out;
2976 if (pblk) {
2977 partial.pclu = EXT4_B2C(sbi, pblk);
2978 partial.state = nofree;
2979 }
2980 }
2981 }
2982
2983
2984
2985
2986 depth = ext_depth(inode);
2987 if (path) {
2988 int k = i = depth;
2989 while (--k > 0)
2990 path[k].p_block =
2991 le16_to_cpu(path[k].p_hdr->eh_entries)+1;
2992 } else {
2993 path = kcalloc(depth + 1, sizeof(struct ext4_ext_path),
2994 GFP_NOFS);
2995 if (path == NULL) {
2996 ext4_journal_stop(handle);
2997 return -ENOMEM;
2998 }
2999 path[0].p_maxdepth = path[0].p_depth = depth;
3000 path[0].p_hdr = ext_inode_hdr(inode);
3001 i = 0;
3002
3003 if (ext4_ext_check(inode, path[0].p_hdr, depth, 0)) {
3004 err = -EFSCORRUPTED;
3005 goto out;
3006 }
3007 }
3008 err = 0;
3009
3010 while (i >= 0 && err == 0) {
3011 if (i == depth) {
3012
3013 err = ext4_ext_rm_leaf(handle, inode, path,
3014 &partial, start, end);
3015
3016 brelse(path[i].p_bh);
3017 path[i].p_bh = NULL;
3018 i--;
3019 continue;
3020 }
3021
3022
3023 if (!path[i].p_hdr) {
3024 ext_debug("initialize header\n");
3025 path[i].p_hdr = ext_block_hdr(path[i].p_bh);
3026 }
3027
3028 if (!path[i].p_idx) {
3029
3030 path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
3031 path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
3032 ext_debug("init index ptr: hdr 0x%p, num %d\n",
3033 path[i].p_hdr,
3034 le16_to_cpu(path[i].p_hdr->eh_entries));
3035 } else {
3036
3037 path[i].p_idx--;
3038 }
3039
3040 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
3041 i, EXT_FIRST_INDEX(path[i].p_hdr),
3042 path[i].p_idx);
3043 if (ext4_ext_more_to_rm(path + i)) {
3044 struct buffer_head *bh;
3045
3046 ext_debug("move to level %d (block %llu)\n",
3047 i + 1, ext4_idx_pblock(path[i].p_idx));
3048 memset(path + i + 1, 0, sizeof(*path));
3049 bh = read_extent_tree_block(inode,
3050 ext4_idx_pblock(path[i].p_idx), depth - i - 1,
3051 EXT4_EX_NOCACHE);
3052 if (IS_ERR(bh)) {
3053
3054 err = PTR_ERR(bh);
3055 break;
3056 }
3057
3058
3059 cond_resched();
3060 if (WARN_ON(i + 1 > depth)) {
3061 err = -EFSCORRUPTED;
3062 break;
3063 }
3064 path[i + 1].p_bh = bh;
3065
3066
3067
3068 path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
3069 i++;
3070 } else {
3071
3072 if (path[i].p_hdr->eh_entries == 0 && i > 0) {
3073
3074
3075
3076 err = ext4_ext_rm_idx(handle, inode, path, i);
3077 }
3078
3079 brelse(path[i].p_bh);
3080 path[i].p_bh = NULL;
3081 i--;
3082 ext_debug("return to level %d\n", i);
3083 }
3084 }
3085
3086 trace_ext4_ext_remove_space_done(inode, start, end, depth, &partial,
3087 path->p_hdr->eh_entries);
3088
3089
3090
3091
3092
3093 if (partial.state == tofree && err == 0) {
3094 int flags = get_default_free_blocks_flags(inode);
3095
3096 if (ext4_is_pending(inode, partial.lblk))
3097 flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
3098 ext4_free_blocks(handle, inode, NULL,
3099 EXT4_C2B(sbi, partial.pclu),
3100 sbi->s_cluster_ratio, flags);
3101 if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
3102 ext4_rereserve_cluster(inode, partial.lblk);
3103 partial.state = initial;
3104 }
3105
3106
3107 if (path->p_hdr->eh_entries == 0) {
3108
3109
3110
3111
3112 err = ext4_ext_get_access(handle, inode, path);
3113 if (err == 0) {
3114 ext_inode_hdr(inode)->eh_depth = 0;
3115 ext_inode_hdr(inode)->eh_max =
3116 cpu_to_le16(ext4_ext_space_root(inode, 0));
3117 err = ext4_ext_dirty(handle, inode, path);
3118 }
3119 }
3120out:
3121 ext4_ext_drop_refs(path);
3122 kfree(path);
3123 path = NULL;
3124 if (err == -EAGAIN)
3125 goto again;
3126 ext4_journal_stop(handle);
3127
3128 return err;
3129}
3130
3131
3132
3133
3134void ext4_ext_init(struct super_block *sb)
3135{
3136
3137
3138
3139
3140 if (ext4_has_feature_extents(sb)) {
3141#if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
3142 printk(KERN_INFO "EXT4-fs: file extents enabled"
3143#ifdef AGGRESSIVE_TEST
3144 ", aggressive tests"
3145#endif
3146#ifdef CHECK_BINSEARCH
3147 ", check binsearch"
3148#endif
3149#ifdef EXTENTS_STATS
3150 ", stats"
3151#endif
3152 "\n");
3153#endif
3154#ifdef EXTENTS_STATS
3155 spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
3156 EXT4_SB(sb)->s_ext_min = 1 << 30;
3157 EXT4_SB(sb)->s_ext_max = 0;
3158#endif
3159 }
3160}
3161
3162
3163
3164
3165void ext4_ext_release(struct super_block *sb)
3166{
3167 if (!ext4_has_feature_extents(sb))
3168 return;
3169
3170#ifdef EXTENTS_STATS
3171 if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
3172 struct ext4_sb_info *sbi = EXT4_SB(sb);
3173 printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
3174 sbi->s_ext_blocks, sbi->s_ext_extents,
3175 sbi->s_ext_blocks / sbi->s_ext_extents);
3176 printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
3177 sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
3178 }
3179#endif
3180}
3181
3182static int ext4_zeroout_es(struct inode *inode, struct ext4_extent *ex)
3183{
3184 ext4_lblk_t ee_block;
3185 ext4_fsblk_t ee_pblock;
3186 unsigned int ee_len;
3187
3188 ee_block = le32_to_cpu(ex->ee_block);
3189 ee_len = ext4_ext_get_actual_len(ex);
3190 ee_pblock = ext4_ext_pblock(ex);
3191
3192 if (ee_len == 0)
3193 return 0;
3194
3195 return ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock,
3196 EXTENT_STATUS_WRITTEN);
3197}
3198
3199
3200static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
3201{
3202 ext4_fsblk_t ee_pblock;
3203 unsigned int ee_len;
3204
3205 ee_len = ext4_ext_get_actual_len(ex);
3206 ee_pblock = ext4_ext_pblock(ex);
3207 return ext4_issue_zeroout(inode, le32_to_cpu(ex->ee_block), ee_pblock,
3208 ee_len);
3209}
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232static int ext4_split_extent_at(handle_t *handle,
3233 struct inode *inode,
3234 struct ext4_ext_path **ppath,
3235 ext4_lblk_t split,
3236 int split_flag,
3237 int flags)
3238{
3239 struct ext4_ext_path *path = *ppath;
3240 ext4_fsblk_t newblock;
3241 ext4_lblk_t ee_block;
3242 struct ext4_extent *ex, newex, orig_ex, zero_ex;
3243 struct ext4_extent *ex2 = NULL;
3244 unsigned int ee_len, depth;
3245 int err = 0;
3246
3247 BUG_ON((split_flag & (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2)) ==
3248 (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2));
3249
3250 ext_debug("ext4_split_extents_at: inode %lu, logical"
3251 "block %llu\n", inode->i_ino, (unsigned long long)split);
3252
3253 ext4_ext_show_leaf(inode, path);
3254
3255 depth = ext_depth(inode);
3256 ex = path[depth].p_ext;
3257 ee_block = le32_to_cpu(ex->ee_block);
3258 ee_len = ext4_ext_get_actual_len(ex);
3259 newblock = split - ee_block + ext4_ext_pblock(ex);
3260
3261 BUG_ON(split < ee_block || split >= (ee_block + ee_len));
3262 BUG_ON(!ext4_ext_is_unwritten(ex) &&
3263 split_flag & (EXT4_EXT_MAY_ZEROOUT |
3264 EXT4_EXT_MARK_UNWRIT1 |
3265 EXT4_EXT_MARK_UNWRIT2));
3266
3267 err = ext4_ext_get_access(handle, inode, path + depth);
3268 if (err)
3269 goto out;
3270
3271 if (split == ee_block) {
3272
3273
3274
3275
3276
3277 if (split_flag & EXT4_EXT_MARK_UNWRIT2)
3278 ext4_ext_mark_unwritten(ex);
3279 else
3280 ext4_ext_mark_initialized(ex);
3281
3282 if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
3283 ext4_ext_try_to_merge(handle, inode, path, ex);
3284
3285 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3286 goto out;
3287 }
3288
3289
3290 memcpy(&orig_ex, ex, sizeof(orig_ex));
3291 ex->ee_len = cpu_to_le16(split - ee_block);
3292 if (split_flag & EXT4_EXT_MARK_UNWRIT1)
3293 ext4_ext_mark_unwritten(ex);
3294
3295
3296
3297
3298
3299 err = ext4_ext_dirty(handle, inode, path + depth);
3300 if (err)
3301 goto fix_extent_len;
3302
3303 ex2 = &newex;
3304 ex2->ee_block = cpu_to_le32(split);
3305 ex2->ee_len = cpu_to_le16(ee_len - (split - ee_block));
3306 ext4_ext_store_pblock(ex2, newblock);
3307 if (split_flag & EXT4_EXT_MARK_UNWRIT2)
3308 ext4_ext_mark_unwritten(ex2);
3309
3310 err = ext4_ext_insert_extent(handle, inode, ppath, &newex, flags);
3311 if (err == -ENOSPC && (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
3312 if (split_flag & (EXT4_EXT_DATA_VALID1|EXT4_EXT_DATA_VALID2)) {
3313 if (split_flag & EXT4_EXT_DATA_VALID1) {
3314 err = ext4_ext_zeroout(inode, ex2);
3315 zero_ex.ee_block = ex2->ee_block;
3316 zero_ex.ee_len = cpu_to_le16(
3317 ext4_ext_get_actual_len(ex2));
3318 ext4_ext_store_pblock(&zero_ex,
3319 ext4_ext_pblock(ex2));
3320 } else {
3321 err = ext4_ext_zeroout(inode, ex);
3322 zero_ex.ee_block = ex->ee_block;
3323 zero_ex.ee_len = cpu_to_le16(
3324 ext4_ext_get_actual_len(ex));
3325 ext4_ext_store_pblock(&zero_ex,
3326 ext4_ext_pblock(ex));
3327 }
3328 } else {
3329 err = ext4_ext_zeroout(inode, &orig_ex);
3330 zero_ex.ee_block = orig_ex.ee_block;
3331 zero_ex.ee_len = cpu_to_le16(
3332 ext4_ext_get_actual_len(&orig_ex));
3333 ext4_ext_store_pblock(&zero_ex,
3334 ext4_ext_pblock(&orig_ex));
3335 }
3336
3337 if (err)
3338 goto fix_extent_len;
3339
3340 ex->ee_len = cpu_to_le16(ee_len);
3341 ext4_ext_try_to_merge(handle, inode, path, ex);
3342 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3343 if (err)
3344 goto fix_extent_len;
3345
3346
3347 err = ext4_zeroout_es(inode, &zero_ex);
3348
3349 goto out;
3350 } else if (err)
3351 goto fix_extent_len;
3352
3353out:
3354 ext4_ext_show_leaf(inode, path);
3355 return err;
3356
3357fix_extent_len:
3358 ex->ee_len = orig_ex.ee_len;
3359 ext4_ext_dirty(handle, inode, path + path->p_depth);
3360 return err;
3361}
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374static int ext4_split_extent(handle_t *handle,
3375 struct inode *inode,
3376 struct ext4_ext_path **ppath,
3377 struct ext4_map_blocks *map,
3378 int split_flag,
3379 int flags)
3380{
3381 struct ext4_ext_path *path = *ppath;
3382 ext4_lblk_t ee_block;
3383 struct ext4_extent *ex;
3384 unsigned int ee_len, depth;
3385 int err = 0;
3386 int unwritten;
3387 int split_flag1, flags1;
3388 int allocated = map->m_len;
3389
3390 depth = ext_depth(inode);
3391 ex = path[depth].p_ext;
3392 ee_block = le32_to_cpu(ex->ee_block);
3393 ee_len = ext4_ext_get_actual_len(ex);
3394 unwritten = ext4_ext_is_unwritten(ex);
3395
3396 if (map->m_lblk + map->m_len < ee_block + ee_len) {
3397 split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;
3398 flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
3399 if (unwritten)
3400 split_flag1 |= EXT4_EXT_MARK_UNWRIT1 |
3401 EXT4_EXT_MARK_UNWRIT2;
3402 if (split_flag & EXT4_EXT_DATA_VALID2)
3403 split_flag1 |= EXT4_EXT_DATA_VALID1;
3404 err = ext4_split_extent_at(handle, inode, ppath,
3405 map->m_lblk + map->m_len, split_flag1, flags1);
3406 if (err)
3407 goto out;
3408 } else {
3409 allocated = ee_len - (map->m_lblk - ee_block);
3410 }
3411
3412
3413
3414
3415 path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3416 if (IS_ERR(path))
3417 return PTR_ERR(path);
3418 depth = ext_depth(inode);
3419 ex = path[depth].p_ext;
3420 if (!ex) {
3421 EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3422 (unsigned long) map->m_lblk);
3423 return -EFSCORRUPTED;
3424 }
3425 unwritten = ext4_ext_is_unwritten(ex);
3426 split_flag1 = 0;
3427
3428 if (map->m_lblk >= ee_block) {
3429 split_flag1 = split_flag & EXT4_EXT_DATA_VALID2;
3430 if (unwritten) {
3431 split_flag1 |= EXT4_EXT_MARK_UNWRIT1;
3432 split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT |
3433 EXT4_EXT_MARK_UNWRIT2);
3434 }
3435 err = ext4_split_extent_at(handle, inode, ppath,
3436 map->m_lblk, split_flag1, flags);
3437 if (err)
3438 goto out;
3439 }
3440
3441 ext4_ext_show_leaf(inode, path);
3442out:
3443 return err ? err : allocated;
3444}
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466static int ext4_ext_convert_to_initialized(handle_t *handle,
3467 struct inode *inode,
3468 struct ext4_map_blocks *map,
3469 struct ext4_ext_path **ppath,
3470 int flags)
3471{
3472 struct ext4_ext_path *path = *ppath;
3473 struct ext4_sb_info *sbi;
3474 struct ext4_extent_header *eh;
3475 struct ext4_map_blocks split_map;
3476 struct ext4_extent zero_ex1, zero_ex2;
3477 struct ext4_extent *ex, *abut_ex;
3478 ext4_lblk_t ee_block, eof_block;
3479 unsigned int ee_len, depth, map_len = map->m_len;
3480 int allocated = 0, max_zeroout = 0;
3481 int err = 0;
3482 int split_flag = EXT4_EXT_DATA_VALID2;
3483
3484 ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
3485 "block %llu, max_blocks %u\n", inode->i_ino,
3486 (unsigned long long)map->m_lblk, map_len);
3487
3488 sbi = EXT4_SB(inode->i_sb);
3489 eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3490 inode->i_sb->s_blocksize_bits;
3491 if (eof_block < map->m_lblk + map_len)
3492 eof_block = map->m_lblk + map_len;
3493
3494 depth = ext_depth(inode);
3495 eh = path[depth].p_hdr;
3496 ex = path[depth].p_ext;
3497 ee_block = le32_to_cpu(ex->ee_block);
3498 ee_len = ext4_ext_get_actual_len(ex);
3499 zero_ex1.ee_len = 0;
3500 zero_ex2.ee_len = 0;
3501
3502 trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);
3503
3504
3505 BUG_ON(!ext4_ext_is_unwritten(ex));
3506 BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523 if ((map->m_lblk == ee_block) &&
3524
3525 (map_len < ee_len) &&
3526 (ex > EXT_FIRST_EXTENT(eh))) {
3527 ext4_lblk_t prev_lblk;
3528 ext4_fsblk_t prev_pblk, ee_pblk;
3529 unsigned int prev_len;
3530
3531 abut_ex = ex - 1;
3532 prev_lblk = le32_to_cpu(abut_ex->ee_block);
3533 prev_len = ext4_ext_get_actual_len(abut_ex);
3534 prev_pblk = ext4_ext_pblock(abut_ex);
3535 ee_pblk = ext4_ext_pblock(ex);
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546 if ((!ext4_ext_is_unwritten(abut_ex)) &&
3547 ((prev_lblk + prev_len) == ee_block) &&
3548 ((prev_pblk + prev_len) == ee_pblk) &&
3549 (prev_len < (EXT_INIT_MAX_LEN - map_len))) {
3550 err = ext4_ext_get_access(handle, inode, path + depth);
3551 if (err)
3552 goto out;
3553
3554 trace_ext4_ext_convert_to_initialized_fastpath(inode,
3555 map, ex, abut_ex);
3556
3557
3558 ex->ee_block = cpu_to_le32(ee_block + map_len);
3559 ext4_ext_store_pblock(ex, ee_pblk + map_len);
3560 ex->ee_len = cpu_to_le16(ee_len - map_len);
3561 ext4_ext_mark_unwritten(ex);
3562
3563
3564 abut_ex->ee_len = cpu_to_le16(prev_len + map_len);
3565
3566
3567 allocated = map_len;
3568 }
3569 } else if (((map->m_lblk + map_len) == (ee_block + ee_len)) &&
3570 (map_len < ee_len) &&
3571 ex < EXT_LAST_EXTENT(eh)) {
3572
3573 ext4_lblk_t next_lblk;
3574 ext4_fsblk_t next_pblk, ee_pblk;
3575 unsigned int next_len;
3576
3577 abut_ex = ex + 1;
3578 next_lblk = le32_to_cpu(abut_ex->ee_block);
3579 next_len = ext4_ext_get_actual_len(abut_ex);
3580 next_pblk = ext4_ext_pblock(abut_ex);
3581 ee_pblk = ext4_ext_pblock(ex);
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592 if ((!ext4_ext_is_unwritten(abut_ex)) &&
3593 ((map->m_lblk + map_len) == next_lblk) &&
3594 ((ee_pblk + ee_len) == next_pblk) &&
3595 (next_len < (EXT_INIT_MAX_LEN - map_len))) {
3596 err = ext4_ext_get_access(handle, inode, path + depth);
3597 if (err)
3598 goto out;
3599
3600 trace_ext4_ext_convert_to_initialized_fastpath(inode,
3601 map, ex, abut_ex);
3602
3603
3604 abut_ex->ee_block = cpu_to_le32(next_lblk - map_len);
3605 ext4_ext_store_pblock(abut_ex, next_pblk - map_len);
3606 ex->ee_len = cpu_to_le16(ee_len - map_len);
3607 ext4_ext_mark_unwritten(ex);
3608
3609
3610 abut_ex->ee_len = cpu_to_le16(next_len + map_len);
3611
3612
3613 allocated = map_len;
3614 }
3615 }
3616 if (allocated) {
3617
3618 ext4_ext_dirty(handle, inode, path + depth);
3619
3620
3621 path[depth].p_ext = abut_ex;
3622 goto out;
3623 } else
3624 allocated = ee_len - (map->m_lblk - ee_block);
3625
3626 WARN_ON(map->m_lblk < ee_block);
3627
3628
3629
3630
3631 split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3632
3633 if (EXT4_EXT_MAY_ZEROOUT & split_flag)
3634 max_zeroout = sbi->s_extent_max_zeroout_kb >>
3635 (inode->i_sb->s_blocksize_bits - 10);
3636
3637 if (IS_ENCRYPTED(inode))
3638 max_zeroout = 0;
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651 split_map.m_lblk = map->m_lblk;
3652 split_map.m_len = map->m_len;
3653
3654 if (max_zeroout && (allocated > split_map.m_len)) {
3655 if (allocated <= max_zeroout) {
3656
3657 zero_ex1.ee_block =
3658 cpu_to_le32(split_map.m_lblk +
3659 split_map.m_len);
3660 zero_ex1.ee_len =
3661 cpu_to_le16(allocated - split_map.m_len);
3662 ext4_ext_store_pblock(&zero_ex1,
3663 ext4_ext_pblock(ex) + split_map.m_lblk +
3664 split_map.m_len - ee_block);
3665 err = ext4_ext_zeroout(inode, &zero_ex1);
3666 if (err)
3667 goto out;
3668 split_map.m_len = allocated;
3669 }
3670 if (split_map.m_lblk - ee_block + split_map.m_len <
3671 max_zeroout) {
3672
3673 if (split_map.m_lblk != ee_block) {
3674 zero_ex2.ee_block = ex->ee_block;
3675 zero_ex2.ee_len = cpu_to_le16(split_map.m_lblk -
3676 ee_block);
3677 ext4_ext_store_pblock(&zero_ex2,
3678 ext4_ext_pblock(ex));
3679 err = ext4_ext_zeroout(inode, &zero_ex2);
3680 if (err)
3681 goto out;
3682 }
3683
3684 split_map.m_len += split_map.m_lblk - ee_block;
3685 split_map.m_lblk = ee_block;
3686 allocated = map->m_len;
3687 }
3688 }
3689
3690 err = ext4_split_extent(handle, inode, ppath, &split_map, split_flag,
3691 flags);
3692 if (err > 0)
3693 err = 0;
3694out:
3695
3696 if (!err) {
3697 err = ext4_zeroout_es(inode, &zero_ex1);
3698 if (!err)
3699 err = ext4_zeroout_es(inode, &zero_ex2);
3700 }
3701 return err ? err : allocated;
3702}
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728static int ext4_split_convert_extents(handle_t *handle,
3729 struct inode *inode,
3730 struct ext4_map_blocks *map,
3731 struct ext4_ext_path **ppath,
3732 int flags)
3733{
3734 struct ext4_ext_path *path = *ppath;
3735 ext4_lblk_t eof_block;
3736 ext4_lblk_t ee_block;
3737 struct ext4_extent *ex;
3738 unsigned int ee_len;
3739 int split_flag = 0, depth;
3740
3741 ext_debug("%s: inode %lu, logical block %llu, max_blocks %u\n",
3742 __func__, inode->i_ino,
3743 (unsigned long long)map->m_lblk, map->m_len);
3744
3745 eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3746 inode->i_sb->s_blocksize_bits;
3747 if (eof_block < map->m_lblk + map->m_len)
3748 eof_block = map->m_lblk + map->m_len;
3749
3750
3751
3752
3753 depth = ext_depth(inode);
3754 ex = path[depth].p_ext;
3755 ee_block = le32_to_cpu(ex->ee_block);
3756 ee_len = ext4_ext_get_actual_len(ex);
3757
3758
3759 if (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN) {
3760 split_flag |= EXT4_EXT_DATA_VALID1;
3761
3762 } else if (flags & EXT4_GET_BLOCKS_CONVERT) {
3763 split_flag |= ee_block + ee_len <= eof_block ?
3764 EXT4_EXT_MAY_ZEROOUT : 0;
3765 split_flag |= (EXT4_EXT_MARK_UNWRIT2 | EXT4_EXT_DATA_VALID2);
3766 }
3767 flags |= EXT4_GET_BLOCKS_PRE_IO;
3768 return ext4_split_extent(handle, inode, ppath, map, split_flag, flags);
3769}
3770
3771static int ext4_convert_unwritten_extents_endio(handle_t *handle,
3772 struct inode *inode,
3773 struct ext4_map_blocks *map,
3774 struct ext4_ext_path **ppath)
3775{
3776 struct ext4_ext_path *path = *ppath;
3777 struct ext4_extent *ex;
3778 ext4_lblk_t ee_block;
3779 unsigned int ee_len;
3780 int depth;
3781 int err = 0;
3782
3783 depth = ext_depth(inode);
3784 ex = path[depth].p_ext;
3785 ee_block = le32_to_cpu(ex->ee_block);
3786 ee_len = ext4_ext_get_actual_len(ex);
3787
3788 ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
3789 "block %llu, max_blocks %u\n", inode->i_ino,
3790 (unsigned long long)ee_block, ee_len);
3791
3792
3793
3794
3795
3796
3797
3798 if (ee_block != map->m_lblk || ee_len > map->m_len) {
3799#ifdef EXT4_DEBUG
3800 ext4_warning("Inode (%ld) finished: extent logical block %llu,"
3801 " len %u; IO logical block %llu, len %u",
3802 inode->i_ino, (unsigned long long)ee_block, ee_len,
3803 (unsigned long long)map->m_lblk, map->m_len);
3804#endif
3805 err = ext4_split_convert_extents(handle, inode, map, ppath,
3806 EXT4_GET_BLOCKS_CONVERT);
3807 if (err < 0)
3808 return err;
3809 path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3810 if (IS_ERR(path))
3811 return PTR_ERR(path);
3812 depth = ext_depth(inode);
3813 ex = path[depth].p_ext;
3814 }
3815
3816 err = ext4_ext_get_access(handle, inode, path + depth);
3817 if (err)
3818 goto out;
3819
3820 ext4_ext_mark_initialized(ex);
3821
3822
3823
3824
3825 ext4_ext_try_to_merge(handle, inode, path, ex);
3826
3827
3828 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3829out:
3830 ext4_ext_show_leaf(inode, path);
3831 return err;
3832}
3833
3834
3835
3836
3837static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
3838 ext4_lblk_t lblk,
3839 struct ext4_ext_path *path,
3840 unsigned int len)
3841{
3842 int i, depth;
3843 struct ext4_extent_header *eh;
3844 struct ext4_extent *last_ex;
3845
3846 if (!ext4_test_inode_flag(inode, EXT4_INODE_EOFBLOCKS))
3847 return 0;
3848
3849 depth = ext_depth(inode);
3850 eh = path[depth].p_hdr;
3851
3852
3853
3854
3855
3856
3857 if (unlikely(!eh->eh_entries))
3858 goto out;
3859 last_ex = EXT_LAST_EXTENT(eh);
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869 if (lblk + len < le32_to_cpu(last_ex->ee_block) +
3870 ext4_ext_get_actual_len(last_ex))
3871 return 0;
3872
3873
3874
3875
3876
3877
3878
3879 for (i = depth-1; i >= 0; i--)
3880 if (path[i].p_idx != EXT_LAST_INDEX(path[i].p_hdr))
3881 return 0;
3882out:
3883 ext4_clear_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
3884 return ext4_mark_inode_dirty(handle, inode);
3885}
3886
3887static int
3888convert_initialized_extent(handle_t *handle, struct inode *inode,
3889 struct ext4_map_blocks *map,
3890 struct ext4_ext_path **ppath,
3891 unsigned int allocated)
3892{
3893 struct ext4_ext_path *path = *ppath;
3894 struct ext4_extent *ex;
3895 ext4_lblk_t ee_block;
3896 unsigned int ee_len;
3897 int depth;
3898 int err = 0;
3899
3900
3901
3902
3903
3904 if (map->m_len > EXT_UNWRITTEN_MAX_LEN)
3905 map->m_len = EXT_UNWRITTEN_MAX_LEN / 2;
3906
3907 depth = ext_depth(inode);
3908 ex = path[depth].p_ext;
3909 ee_block = le32_to_cpu(ex->ee_block);
3910 ee_len = ext4_ext_get_actual_len(ex);
3911
3912 ext_debug("%s: inode %lu, logical"
3913 "block %llu, max_blocks %u\n", __func__, inode->i_ino,
3914 (unsigned long long)ee_block, ee_len);
3915
3916 if (ee_block != map->m_lblk || ee_len > map->m_len) {
3917 err = ext4_split_convert_extents(handle, inode, map, ppath,
3918 EXT4_GET_BLOCKS_CONVERT_UNWRITTEN);
3919 if (err < 0)
3920 return err;
3921 path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3922 if (IS_ERR(path))
3923 return PTR_ERR(path);
3924 depth = ext_depth(inode);
3925 ex = path[depth].p_ext;
3926 if (!ex) {
3927 EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3928 (unsigned long) map->m_lblk);
3929 return -EFSCORRUPTED;
3930 }
3931 }
3932
3933 err = ext4_ext_get_access(handle, inode, path + depth);
3934 if (err)
3935 return err;
3936
3937 ext4_ext_mark_unwritten(ex);
3938
3939
3940
3941
3942 ext4_ext_try_to_merge(handle, inode, path, ex);
3943
3944
3945 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3946 if (err)
3947 return err;
3948 ext4_ext_show_leaf(inode, path);
3949
3950 ext4_update_inode_fsync_trans(handle, inode, 1);
3951 err = check_eofblocks_fl(handle, inode, map->m_lblk, path, map->m_len);
3952 if (err)
3953 return err;
3954 map->m_flags |= EXT4_MAP_UNWRITTEN;
3955 if (allocated > map->m_len)
3956 allocated = map->m_len;
3957 map->m_len = allocated;
3958 return allocated;
3959}
3960
3961static int
3962ext4_ext_handle_unwritten_extents(handle_t *handle, struct inode *inode,
3963 struct ext4_map_blocks *map,
3964 struct ext4_ext_path **ppath, int flags,
3965 unsigned int allocated, ext4_fsblk_t newblock)
3966{
3967 struct ext4_ext_path *path = *ppath;
3968 int ret = 0;
3969 int err = 0;
3970
3971 ext_debug("ext4_ext_handle_unwritten_extents: inode %lu, logical "
3972 "block %llu, max_blocks %u, flags %x, allocated %u\n",
3973 inode->i_ino, (unsigned long long)map->m_lblk, map->m_len,
3974 flags, allocated);
3975 ext4_ext_show_leaf(inode, path);
3976
3977
3978
3979
3980
3981 flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL;
3982
3983 trace_ext4_ext_handle_unwritten_extents(inode, map, flags,
3984 allocated, newblock);
3985
3986
3987 if (flags & EXT4_GET_BLOCKS_PRE_IO) {
3988 ret = ext4_split_convert_extents(handle, inode, map, ppath,
3989 flags | EXT4_GET_BLOCKS_CONVERT);
3990 if (ret <= 0)
3991 goto out;
3992 map->m_flags |= EXT4_MAP_UNWRITTEN;
3993 goto out;
3994 }
3995
3996 if (flags & EXT4_GET_BLOCKS_CONVERT) {
3997 if (flags & EXT4_GET_BLOCKS_ZERO) {
3998 if (allocated > map->m_len)
3999 allocated = map->m_len;
4000 err = ext4_issue_zeroout(inode, map->m_lblk, newblock,
4001 allocated);
4002 if (err < 0)
4003 goto out2;
4004 }
4005 ret = ext4_convert_unwritten_extents_endio(handle, inode, map,
4006 ppath);
4007 if (ret >= 0) {
4008 ext4_update_inode_fsync_trans(handle, inode, 1);
4009 err = check_eofblocks_fl(handle, inode, map->m_lblk,
4010 path, map->m_len);
4011 } else
4012 err = ret;
4013 map->m_flags |= EXT4_MAP_MAPPED;
4014 map->m_pblk = newblock;
4015 if (allocated > map->m_len)
4016 allocated = map->m_len;
4017 map->m_len = allocated;
4018 goto out2;
4019 }
4020
4021
4022
4023
4024
4025 if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
4026 map->m_flags |= EXT4_MAP_UNWRITTEN;
4027 goto map_out;
4028 }
4029
4030
4031 if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4032
4033
4034
4035
4036
4037
4038
4039 map->m_flags |= EXT4_MAP_UNWRITTEN;
4040 goto out1;
4041 }
4042
4043
4044 ret = ext4_ext_convert_to_initialized(handle, inode, map, ppath, flags);
4045 if (ret >= 0)
4046 ext4_update_inode_fsync_trans(handle, inode, 1);
4047out:
4048 if (ret <= 0) {
4049 err = ret;
4050 goto out2;
4051 } else
4052 allocated = ret;
4053 map->m_flags |= EXT4_MAP_NEW;
4054 if (allocated > map->m_len)
4055 allocated = map->m_len;
4056 map->m_len = allocated;
4057
4058map_out:
4059 map->m_flags |= EXT4_MAP_MAPPED;
4060 if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0) {
4061 err = check_eofblocks_fl(handle, inode, map->m_lblk, path,
4062 map->m_len);
4063 if (err < 0)
4064 goto out2;
4065 }
4066out1:
4067 if (allocated > map->m_len)
4068 allocated = map->m_len;
4069 ext4_ext_show_leaf(inode, path);
4070 map->m_pblk = newblock;
4071 map->m_len = allocated;
4072out2:
4073 return err ? err : allocated;
4074}
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117static int get_implied_cluster_alloc(struct super_block *sb,
4118 struct ext4_map_blocks *map,
4119 struct ext4_extent *ex,
4120 struct ext4_ext_path *path)
4121{
4122 struct ext4_sb_info *sbi = EXT4_SB(sb);
4123 ext4_lblk_t c_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4124 ext4_lblk_t ex_cluster_start, ex_cluster_end;
4125 ext4_lblk_t rr_cluster_start;
4126 ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4127 ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4128 unsigned short ee_len = ext4_ext_get_actual_len(ex);
4129
4130
4131 ex_cluster_start = EXT4_B2C(sbi, ee_block);
4132 ex_cluster_end = EXT4_B2C(sbi, ee_block + ee_len - 1);
4133
4134
4135 rr_cluster_start = EXT4_B2C(sbi, map->m_lblk);
4136
4137 if ((rr_cluster_start == ex_cluster_end) ||
4138 (rr_cluster_start == ex_cluster_start)) {
4139 if (rr_cluster_start == ex_cluster_end)
4140 ee_start += ee_len - 1;
4141 map->m_pblk = EXT4_PBLK_CMASK(sbi, ee_start) + c_offset;
4142 map->m_len = min(map->m_len,
4143 (unsigned) sbi->s_cluster_ratio - c_offset);
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153 if (map->m_lblk < ee_block)
4154 map->m_len = min(map->m_len, ee_block - map->m_lblk);
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165 if (map->m_lblk > ee_block) {
4166 ext4_lblk_t next = ext4_ext_next_allocated_block(path);
4167 map->m_len = min(map->m_len, next - map->m_lblk);
4168 }
4169
4170 trace_ext4_get_implied_cluster_alloc_exit(sb, map, 1);
4171 return 1;
4172 }
4173
4174 trace_ext4_get_implied_cluster_alloc_exit(sb, map, 0);
4175 return 0;
4176}
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
4198 struct ext4_map_blocks *map, int flags)
4199{
4200 struct ext4_ext_path *path = NULL;
4201 struct ext4_extent newex, *ex, *ex2;
4202 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
4203 ext4_fsblk_t newblock = 0;
4204 int free_on_err = 0, err = 0, depth, ret;
4205 unsigned int allocated = 0, offset = 0;
4206 unsigned int allocated_clusters = 0;
4207 struct ext4_allocation_request ar;
4208 ext4_lblk_t cluster_offset;
4209 bool map_from_cluster = false;
4210
4211 ext_debug("blocks %u/%u requested for inode %lu\n",
4212 map->m_lblk, map->m_len, inode->i_ino);
4213 trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
4214
4215
4216 path = ext4_find_extent(inode, map->m_lblk, NULL, 0);
4217 if (IS_ERR(path)) {
4218 err = PTR_ERR(path);
4219 path = NULL;
4220 goto out2;
4221 }
4222
4223 depth = ext_depth(inode);
4224
4225
4226
4227
4228
4229
4230 if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
4231 EXT4_ERROR_INODE(inode, "bad extent address "
4232 "lblock: %lu, depth: %d pblock %lld",
4233 (unsigned long) map->m_lblk, depth,
4234 path[depth].p_block);
4235 err = -EFSCORRUPTED;
4236 goto out2;
4237 }
4238
4239 ex = path[depth].p_ext;
4240 if (ex) {
4241 ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4242 ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4243 unsigned short ee_len;
4244
4245
4246
4247
4248
4249
4250 ee_len = ext4_ext_get_actual_len(ex);
4251
4252 trace_ext4_ext_show_extent(inode, ee_block, ee_start, ee_len);
4253
4254
4255 if (in_range(map->m_lblk, ee_block, ee_len)) {
4256 newblock = map->m_lblk - ee_block + ee_start;
4257
4258 allocated = ee_len - (map->m_lblk - ee_block);
4259 ext_debug("%u fit into %u:%d -> %llu\n", map->m_lblk,
4260 ee_block, ee_len, newblock);
4261
4262
4263
4264
4265
4266 if ((!ext4_ext_is_unwritten(ex)) &&
4267 (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN)) {
4268 allocated = convert_initialized_extent(
4269 handle, inode, map, &path,
4270 allocated);
4271 goto out2;
4272 } else if (!ext4_ext_is_unwritten(ex))
4273 goto out;
4274
4275 ret = ext4_ext_handle_unwritten_extents(
4276 handle, inode, map, &path, flags,
4277 allocated, newblock);
4278 if (ret < 0)
4279 err = ret;
4280 else
4281 allocated = ret;
4282 goto out2;
4283 }
4284 }
4285
4286
4287
4288
4289
4290 if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4291 ext4_lblk_t hole_start, hole_len;
4292
4293 hole_start = map->m_lblk;
4294 hole_len = ext4_ext_determine_hole(inode, path, &hole_start);
4295
4296
4297
4298
4299 ext4_ext_put_gap_in_cache(inode, hole_start, hole_len);
4300
4301
4302 if (hole_start != map->m_lblk)
4303 hole_len -= map->m_lblk - hole_start;
4304 map->m_pblk = 0;
4305 map->m_len = min_t(unsigned int, map->m_len, hole_len);
4306
4307 goto out2;
4308 }
4309
4310
4311
4312
4313 newex.ee_block = cpu_to_le32(map->m_lblk);
4314 cluster_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4315
4316
4317
4318
4319
4320 if (cluster_offset && ex &&
4321 get_implied_cluster_alloc(inode->i_sb, map, ex, path)) {
4322 ar.len = allocated = map->m_len;
4323 newblock = map->m_pblk;
4324 map_from_cluster = true;
4325 goto got_allocated_blocks;
4326 }
4327
4328
4329 ar.lleft = map->m_lblk;
4330 err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
4331 if (err)
4332 goto out2;
4333 ar.lright = map->m_lblk;
4334 ex2 = NULL;
4335 err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright, &ex2);
4336 if (err)
4337 goto out2;
4338
4339
4340
4341 if ((sbi->s_cluster_ratio > 1) && ex2 &&
4342 get_implied_cluster_alloc(inode->i_sb, map, ex2, path)) {
4343 ar.len = allocated = map->m_len;
4344 newblock = map->m_pblk;
4345 map_from_cluster = true;
4346 goto got_allocated_blocks;
4347 }
4348
4349
4350
4351
4352
4353
4354
4355 if (map->m_len > EXT_INIT_MAX_LEN &&
4356 !(flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4357 map->m_len = EXT_INIT_MAX_LEN;
4358 else if (map->m_len > EXT_UNWRITTEN_MAX_LEN &&
4359 (flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4360 map->m_len = EXT_UNWRITTEN_MAX_LEN;
4361
4362
4363 newex.ee_len = cpu_to_le16(map->m_len);
4364 err = ext4_ext_check_overlap(sbi, inode, &newex, path);
4365 if (err)
4366 allocated = ext4_ext_get_actual_len(&newex);
4367 else
4368 allocated = map->m_len;
4369
4370
4371 ar.inode = inode;
4372 ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
4373 ar.logical = map->m_lblk;
4374
4375
4376
4377
4378
4379
4380
4381
4382 offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4383 ar.len = EXT4_NUM_B2C(sbi, offset+allocated);
4384 ar.goal -= offset;
4385 ar.logical -= offset;
4386 if (S_ISREG(inode->i_mode))
4387 ar.flags = EXT4_MB_HINT_DATA;
4388 else
4389
4390 ar.flags = 0;
4391 if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
4392 ar.flags |= EXT4_MB_HINT_NOPREALLOC;
4393 if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
4394 ar.flags |= EXT4_MB_DELALLOC_RESERVED;
4395 if (flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
4396 ar.flags |= EXT4_MB_USE_RESERVED;
4397 newblock = ext4_mb_new_blocks(handle, &ar, &err);
4398 if (!newblock)
4399 goto out2;
4400 ext_debug("allocate new block: goal %llu, found %llu/%u\n",
4401 ar.goal, newblock, allocated);
4402 free_on_err = 1;
4403 allocated_clusters = ar.len;
4404 ar.len = EXT4_C2B(sbi, ar.len) - offset;
4405 if (ar.len > allocated)
4406 ar.len = allocated;
4407
4408got_allocated_blocks:
4409
4410 ext4_ext_store_pblock(&newex, newblock + offset);
4411 newex.ee_len = cpu_to_le16(ar.len);
4412
4413 if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT){
4414 ext4_ext_mark_unwritten(&newex);
4415 map->m_flags |= EXT4_MAP_UNWRITTEN;
4416 }
4417
4418 err = 0;
4419 if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0)
4420 err = check_eofblocks_fl(handle, inode, map->m_lblk,
4421 path, ar.len);
4422 if (!err)
4423 err = ext4_ext_insert_extent(handle, inode, &path,
4424 &newex, flags);
4425
4426 if (err && free_on_err) {
4427 int fb_flags = flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE ?
4428 EXT4_FREE_BLOCKS_NO_QUOT_UPDATE : 0;
4429
4430
4431
4432 ext4_discard_preallocations(inode);
4433 ext4_free_blocks(handle, inode, NULL, newblock,
4434 EXT4_C2B(sbi, allocated_clusters), fb_flags);
4435 goto out2;
4436 }
4437
4438
4439 newblock = ext4_ext_pblock(&newex);
4440 allocated = ext4_ext_get_actual_len(&newex);
4441 if (allocated > map->m_len)
4442 allocated = map->m_len;
4443 map->m_flags |= EXT4_MAP_NEW;
4444
4445
4446
4447
4448
4449
4450
4451 if (test_opt(inode->i_sb, DELALLOC) && !map_from_cluster) {
4452 if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
4453
4454
4455
4456
4457 ext4_da_update_reserve_space(inode, allocated_clusters,
4458 1);
4459 } else {
4460 ext4_lblk_t lblk, len;
4461 unsigned int n;
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474 lblk = EXT4_LBLK_CMASK(sbi, map->m_lblk);
4475 len = allocated_clusters << sbi->s_cluster_bits;
4476 n = ext4_es_delayed_clu(inode, lblk, len);
4477 if (n > 0)
4478 ext4_da_update_reserve_space(inode, (int) n, 0);
4479 }
4480 }
4481
4482
4483
4484
4485
4486 if ((flags & EXT4_GET_BLOCKS_UNWRIT_EXT) == 0)
4487 ext4_update_inode_fsync_trans(handle, inode, 1);
4488 else
4489 ext4_update_inode_fsync_trans(handle, inode, 0);
4490out:
4491 if (allocated > map->m_len)
4492 allocated = map->m_len;
4493 ext4_ext_show_leaf(inode, path);
4494 map->m_flags |= EXT4_MAP_MAPPED;
4495 map->m_pblk = newblock;
4496 map->m_len = allocated;
4497out2:
4498 ext4_ext_drop_refs(path);
4499 kfree(path);
4500
4501 trace_ext4_ext_map_blocks_exit(inode, flags, map,
4502 err ? err : allocated);
4503 return err ? err : allocated;
4504}
4505
4506int ext4_ext_truncate(handle_t *handle, struct inode *inode)
4507{
4508 struct super_block *sb = inode->i_sb;
4509 ext4_lblk_t last_block;
4510 int err = 0;
4511
4512
4513
4514
4515
4516
4517
4518
4519 EXT4_I(inode)->i_disksize = inode->i_size;
4520 err = ext4_mark_inode_dirty(handle, inode);
4521 if (err)
4522 return err;
4523
4524 last_block = (inode->i_size + sb->s_blocksize - 1)
4525 >> EXT4_BLOCK_SIZE_BITS(sb);
4526retry:
4527 err = ext4_es_remove_extent(inode, last_block,
4528 EXT_MAX_BLOCKS - last_block);
4529 if (err == -ENOMEM) {
4530 cond_resched();
4531 congestion_wait(BLK_RW_ASYNC, HZ/50);
4532 goto retry;
4533 }
4534 if (err)
4535 return err;
4536 return ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
4537}
4538
4539static int ext4_alloc_file_blocks(struct file *file, ext4_lblk_t offset,
4540 ext4_lblk_t len, loff_t new_size,
4541 int flags)
4542{
4543 struct inode *inode = file_inode(file);
4544 handle_t *handle;
4545 int ret = 0;
4546 int ret2 = 0;
4547 int retries = 0;
4548 int depth = 0;
4549 struct ext4_map_blocks map;
4550 unsigned int credits;
4551 loff_t epos;
4552
4553 BUG_ON(!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS));
4554 map.m_lblk = offset;
4555 map.m_len = len;
4556
4557
4558
4559
4560
4561 if (len <= EXT_UNWRITTEN_MAX_LEN)
4562 flags |= EXT4_GET_BLOCKS_NO_NORMALIZE;
4563
4564
4565
4566
4567 credits = ext4_chunk_trans_blocks(inode, len);
4568 depth = ext_depth(inode);
4569
4570retry:
4571 while (ret >= 0 && len) {
4572
4573
4574
4575 if (depth != ext_depth(inode)) {
4576 credits = ext4_chunk_trans_blocks(inode, len);
4577 depth = ext_depth(inode);
4578 }
4579
4580 handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4581 credits);
4582 if (IS_ERR(handle)) {
4583 ret = PTR_ERR(handle);
4584 break;
4585 }
4586 ret = ext4_map_blocks(handle, inode, &map, flags);
4587 if (ret <= 0) {
4588 ext4_debug("inode #%lu: block %u: len %u: "
4589 "ext4_ext_map_blocks returned %d",
4590 inode->i_ino, map.m_lblk,
4591 map.m_len, ret);
4592 ext4_mark_inode_dirty(handle, inode);
4593 ret2 = ext4_journal_stop(handle);
4594 break;
4595 }
4596 map.m_lblk += ret;
4597 map.m_len = len = len - ret;
4598 epos = (loff_t)map.m_lblk << inode->i_blkbits;
4599 inode->i_ctime = current_time(inode);
4600 if (new_size) {
4601 if (epos > new_size)
4602 epos = new_size;
4603 if (ext4_update_inode_size(inode, epos) & 0x1)
4604 inode->i_mtime = inode->i_ctime;
4605 } else {
4606 if (epos > inode->i_size)
4607 ext4_set_inode_flag(inode,
4608 EXT4_INODE_EOFBLOCKS);
4609 }
4610 ext4_mark_inode_dirty(handle, inode);
4611 ext4_update_inode_fsync_trans(handle, inode, 1);
4612 ret2 = ext4_journal_stop(handle);
4613 if (ret2)
4614 break;
4615 }
4616 if (ret == -ENOSPC &&
4617 ext4_should_retry_alloc(inode->i_sb, &retries)) {
4618 ret = 0;
4619 goto retry;
4620 }
4621
4622 return ret > 0 ? ret2 : ret;
4623}
4624
4625static long ext4_zero_range(struct file *file, loff_t offset,
4626 loff_t len, int mode)
4627{
4628 struct inode *inode = file_inode(file);
4629 handle_t *handle = NULL;
4630 unsigned int max_blocks;
4631 loff_t new_size = 0;
4632 int ret = 0;
4633 int flags;
4634 int credits;
4635 int partial_begin, partial_end;
4636 loff_t start, end;
4637 ext4_lblk_t lblk;
4638 unsigned int blkbits = inode->i_blkbits;
4639
4640 trace_ext4_zero_range(inode, offset, len, mode);
4641
4642 if (!S_ISREG(inode->i_mode))
4643 return -EINVAL;
4644
4645
4646 if (ext4_should_journal_data(inode)) {
4647 ret = ext4_force_commit(inode->i_sb);
4648 if (ret)
4649 return ret;
4650 }
4651
4652
4653
4654
4655
4656
4657
4658 start = round_up(offset, 1 << blkbits);
4659 end = round_down((offset + len), 1 << blkbits);
4660
4661 if (start < offset || end > offset + len)
4662 return -EINVAL;
4663 partial_begin = offset & ((1 << blkbits) - 1);
4664 partial_end = (offset + len) & ((1 << blkbits) - 1);
4665
4666 lblk = start >> blkbits;
4667 max_blocks = (end >> blkbits);
4668 if (max_blocks < lblk)
4669 max_blocks = 0;
4670 else
4671 max_blocks -= lblk;
4672
4673 inode_lock(inode);
4674
4675
4676
4677
4678 if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4679 ret = -EOPNOTSUPP;
4680 goto out_mutex;
4681 }
4682
4683 if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4684 (offset + len > i_size_read(inode) ||
4685 offset + len > EXT4_I(inode)->i_disksize)) {
4686 new_size = offset + len;
4687 ret = inode_newsize_ok(inode, new_size);
4688 if (ret)
4689 goto out_mutex;
4690 }
4691
4692 flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4693 if (mode & FALLOC_FL_KEEP_SIZE)
4694 flags |= EXT4_GET_BLOCKS_KEEP_SIZE;
4695
4696
4697 inode_dio_wait(inode);
4698
4699
4700 if (partial_begin || partial_end) {
4701 ret = ext4_alloc_file_blocks(file,
4702 round_down(offset, 1 << blkbits) >> blkbits,
4703 (round_up((offset + len), 1 << blkbits) -
4704 round_down(offset, 1 << blkbits)) >> blkbits,
4705 new_size, flags);
4706 if (ret)
4707 goto out_mutex;
4708
4709 }
4710
4711
4712 if (max_blocks > 0) {
4713 flags |= (EXT4_GET_BLOCKS_CONVERT_UNWRITTEN |
4714 EXT4_EX_NOCACHE);
4715
4716
4717
4718
4719
4720 down_write(&EXT4_I(inode)->i_mmap_sem);
4721
4722 ret = ext4_break_layouts(inode);
4723 if (ret) {
4724 up_write(&EXT4_I(inode)->i_mmap_sem);
4725 goto out_mutex;
4726 }
4727
4728 ret = ext4_update_disksize_before_punch(inode, offset, len);
4729 if (ret) {
4730 up_write(&EXT4_I(inode)->i_mmap_sem);
4731 goto out_mutex;
4732 }
4733
4734 truncate_pagecache_range(inode, start, end - 1);
4735 inode->i_mtime = inode->i_ctime = current_time(inode);
4736
4737 ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size,
4738 flags);
4739 up_write(&EXT4_I(inode)->i_mmap_sem);
4740 if (ret)
4741 goto out_mutex;
4742 }
4743 if (!partial_begin && !partial_end)
4744 goto out_mutex;
4745
4746
4747
4748
4749
4750 credits = (2 * ext4_ext_index_trans_blocks(inode, 2)) + 1;
4751 if (ext4_should_journal_data(inode))
4752 credits += 2;
4753 handle = ext4_journal_start(inode, EXT4_HT_MISC, credits);
4754 if (IS_ERR(handle)) {
4755 ret = PTR_ERR(handle);
4756 ext4_std_error(inode->i_sb, ret);
4757 goto out_mutex;
4758 }
4759
4760 inode->i_mtime = inode->i_ctime = current_time(inode);
4761 if (new_size) {
4762 ext4_update_inode_size(inode, new_size);
4763 } else {
4764
4765
4766
4767
4768 if ((offset + len) > i_size_read(inode))
4769 ext4_set_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
4770 }
4771 ext4_mark_inode_dirty(handle, inode);
4772
4773
4774 ret = ext4_zero_partial_blocks(handle, inode, offset, len);
4775 if (ret >= 0)
4776 ext4_update_inode_fsync_trans(handle, inode, 1);
4777
4778 if (file->f_flags & O_SYNC)
4779 ext4_handle_sync(handle);
4780
4781 ext4_journal_stop(handle);
4782out_mutex:
4783 inode_unlock(inode);
4784 return ret;
4785}
4786
4787
4788
4789
4790
4791
4792
4793
4794long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
4795{
4796 struct inode *inode = file_inode(file);
4797 loff_t new_size = 0;
4798 unsigned int max_blocks;
4799 int ret = 0;
4800 int flags;
4801 ext4_lblk_t lblk;
4802 unsigned int blkbits = inode->i_blkbits;
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814 if (IS_ENCRYPTED(inode) &&
4815 (mode & (FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_INSERT_RANGE |
4816 FALLOC_FL_ZERO_RANGE)))
4817 return -EOPNOTSUPP;
4818
4819
4820 if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE |
4821 FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_ZERO_RANGE |
4822 FALLOC_FL_INSERT_RANGE))
4823 return -EOPNOTSUPP;
4824
4825 if (mode & FALLOC_FL_PUNCH_HOLE)
4826 return ext4_punch_hole(inode, offset, len);
4827
4828 ret = ext4_convert_inline_data(inode);
4829 if (ret)
4830 return ret;
4831
4832 if (mode & FALLOC_FL_COLLAPSE_RANGE)
4833 return ext4_collapse_range(inode, offset, len);
4834
4835 if (mode & FALLOC_FL_INSERT_RANGE)
4836 return ext4_insert_range(inode, offset, len);
4837
4838 if (mode & FALLOC_FL_ZERO_RANGE)
4839 return ext4_zero_range(file, offset, len, mode);
4840
4841 trace_ext4_fallocate_enter(inode, offset, len, mode);
4842 lblk = offset >> blkbits;
4843
4844 max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
4845 flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4846 if (mode & FALLOC_FL_KEEP_SIZE)
4847 flags |= EXT4_GET_BLOCKS_KEEP_SIZE;
4848
4849 inode_lock(inode);
4850
4851
4852
4853
4854 if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4855 ret = -EOPNOTSUPP;
4856 goto out;
4857 }
4858
4859 if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4860 (offset + len > i_size_read(inode) ||
4861 offset + len > EXT4_I(inode)->i_disksize)) {
4862 new_size = offset + len;
4863 ret = inode_newsize_ok(inode, new_size);
4864 if (ret)
4865 goto out;
4866 }
4867
4868
4869 inode_dio_wait(inode);
4870
4871 ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size, flags);
4872 if (ret)
4873 goto out;
4874
4875 if (file->f_flags & O_SYNC && EXT4_SB(inode->i_sb)->s_journal) {
4876 ret = jbd2_complete_transaction(EXT4_SB(inode->i_sb)->s_journal,
4877 EXT4_I(inode)->i_sync_tid);
4878 }
4879out:
4880 inode_unlock(inode);
4881 trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
4882 return ret;
4883}
4884
4885
4886
4887
4888
4889
4890
4891
4892
4893
4894
4895int ext4_convert_unwritten_extents(handle_t *handle, struct inode *inode,
4896 loff_t offset, ssize_t len)
4897{
4898 unsigned int max_blocks;
4899 int ret = 0;
4900 int ret2 = 0;
4901 struct ext4_map_blocks map;
4902 unsigned int credits, blkbits = inode->i_blkbits;
4903
4904 map.m_lblk = offset >> blkbits;
4905 max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
4906
4907
4908
4909
4910
4911
4912 if (handle) {
4913 handle = ext4_journal_start_reserved(handle,
4914 EXT4_HT_EXT_CONVERT);
4915 if (IS_ERR(handle))
4916 return PTR_ERR(handle);
4917 credits = 0;
4918 } else {
4919
4920
4921
4922 credits = ext4_chunk_trans_blocks(inode, max_blocks);
4923 }
4924 while (ret >= 0 && ret < max_blocks) {
4925 map.m_lblk += ret;
4926 map.m_len = (max_blocks -= ret);
4927 if (credits) {
4928 handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4929 credits);
4930 if (IS_ERR(handle)) {
4931 ret = PTR_ERR(handle);
4932 break;
4933 }
4934 }
4935 ret = ext4_map_blocks(handle, inode, &map,
4936 EXT4_GET_BLOCKS_IO_CONVERT_EXT);
4937 if (ret <= 0)
4938 ext4_warning(inode->i_sb,
4939 "inode #%lu: block %u: len %u: "
4940 "ext4_ext_map_blocks returned %d",
4941 inode->i_ino, map.m_lblk,
4942 map.m_len, ret);
4943 ext4_mark_inode_dirty(handle, inode);
4944 if (credits)
4945 ret2 = ext4_journal_stop(handle);
4946 if (ret <= 0 || ret2)
4947 break;
4948 }
4949 if (!credits)
4950 ret2 = ext4_journal_stop(handle);
4951 return ret > 0 ? ret2 : ret;
4952}
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
4963static int ext4_find_delayed_extent(struct inode *inode,
4964 struct extent_status *newes)
4965{
4966 struct extent_status es;
4967 ext4_lblk_t block, next_del;
4968
4969 if (newes->es_pblk == 0) {
4970 ext4_es_find_extent_range(inode, &ext4_es_is_delayed,
4971 newes->es_lblk,
4972 newes->es_lblk + newes->es_len - 1,
4973 &es);
4974
4975
4976
4977
4978
4979 if (es.es_len == 0)
4980
4981 return 0;
4982
4983 if (es.es_lblk > newes->es_lblk) {
4984
4985 newes->es_len = min(es.es_lblk - newes->es_lblk,
4986 newes->es_len);
4987 return 0;
4988 }
4989
4990 newes->es_len = es.es_lblk + es.es_len - newes->es_lblk;
4991 }
4992
4993 block = newes->es_lblk + newes->es_len;
4994 ext4_es_find_extent_range(inode, &ext4_es_is_delayed, block,
4995 EXT_MAX_BLOCKS, &es);
4996 if (es.es_len == 0)
4997 next_del = EXT_MAX_BLOCKS;
4998 else
4999 next_del = es.es_lblk;
5000
5001 return next_del;
5002}
5003
5004#define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
5005
5006static int ext4_xattr_fiemap(struct inode *inode,
5007 struct fiemap_extent_info *fieinfo)
5008{
5009 __u64 physical = 0;
5010 __u64 length;
5011 __u32 flags = FIEMAP_EXTENT_LAST;
5012 int blockbits = inode->i_sb->s_blocksize_bits;
5013 int error = 0;
5014
5015
5016 if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
5017 struct ext4_iloc iloc;
5018 int offset;
5019
5020 error = ext4_get_inode_loc(inode, &iloc);
5021 if (error)
5022 return error;
5023 physical = (__u64)iloc.bh->b_blocknr << blockbits;
5024 offset = EXT4_GOOD_OLD_INODE_SIZE +
5025 EXT4_I(inode)->i_extra_isize;
5026 physical += offset;
5027 length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
5028 flags |= FIEMAP_EXTENT_DATA_INLINE;
5029 brelse(iloc.bh);
5030 } else {
5031 physical = (__u64)EXT4_I(inode)->i_file_acl << blockbits;
5032 length = inode->i_sb->s_blocksize;
5033 }
5034
5035 if (physical)
5036 error = fiemap_fill_next_extent(fieinfo, 0, physical,
5037 length, flags);
5038 return (error < 0 ? error : 0);
5039}
5040
5041int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
5042 __u64 start, __u64 len)
5043{
5044 ext4_lblk_t start_blk;
5045 int error = 0;
5046
5047 if (ext4_has_inline_data(inode)) {
5048 int has_inline = 1;
5049
5050 error = ext4_inline_data_fiemap(inode, fieinfo, &has_inline,
5051 start, len);
5052
5053 if (has_inline)
5054 return error;
5055 }
5056
5057 if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
5058 error = ext4_ext_precache(inode);
5059 if (error)
5060 return error;
5061 }
5062
5063
5064 if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
5065 return generic_block_fiemap(inode, fieinfo, start, len,
5066 ext4_get_block);
5067
5068 if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
5069 return -EBADR;
5070
5071 if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
5072 error = ext4_xattr_fiemap(inode, fieinfo);
5073 } else {
5074 ext4_lblk_t len_blks;
5075 __u64 last_blk;
5076
5077 start_blk = start >> inode->i_sb->s_blocksize_bits;
5078 last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
5079 if (last_blk >= EXT_MAX_BLOCKS)
5080 last_blk = EXT_MAX_BLOCKS-1;
5081 len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
5082
5083
5084
5085
5086
5087 error = ext4_fill_fiemap_extents(inode, start_blk,
5088 len_blks, fieinfo);
5089 }
5090 return error;
5091}
5092
5093
5094
5095
5096
5097
5098
5099static int
5100ext4_access_path(handle_t *handle, struct inode *inode,
5101 struct ext4_ext_path *path)
5102{
5103 int credits, err;
5104
5105 if (!ext4_handle_valid(handle))
5106 return 0;
5107
5108
5109
5110
5111
5112
5113
5114 if (handle->h_buffer_credits < 7) {
5115 credits = ext4_writepage_trans_blocks(inode);
5116 err = ext4_ext_truncate_extend_restart(handle, inode, credits);
5117
5118 if (err && err != -EAGAIN)
5119 return err;
5120 }
5121
5122 err = ext4_ext_get_access(handle, inode, path);
5123 return err;
5124}
5125
5126
5127
5128
5129
5130
5131
5132static int
5133ext4_ext_shift_path_extents(struct ext4_ext_path *path, ext4_lblk_t shift,
5134 struct inode *inode, handle_t *handle,
5135 enum SHIFT_DIRECTION SHIFT)
5136{
5137 int depth, err = 0;
5138 struct ext4_extent *ex_start, *ex_last;
5139 bool update = 0;
5140 depth = path->p_depth;
5141
5142 while (depth >= 0) {
5143 if (depth == path->p_depth) {
5144 ex_start = path[depth].p_ext;
5145 if (!ex_start)
5146 return -EFSCORRUPTED;
5147
5148 ex_last = EXT_LAST_EXTENT(path[depth].p_hdr);
5149
5150 err = ext4_access_path(handle, inode, path + depth);
5151 if (err)
5152 goto out;
5153
5154 if (ex_start == EXT_FIRST_EXTENT(path[depth].p_hdr))
5155 update = 1;
5156
5157 while (ex_start <= ex_last) {
5158 if (SHIFT == SHIFT_LEFT) {
5159 le32_add_cpu(&ex_start->ee_block,
5160 -shift);
5161
5162 if ((ex_start >
5163 EXT_FIRST_EXTENT(path[depth].p_hdr))
5164 &&
5165 ext4_ext_try_to_merge_right(inode,
5166 path, ex_start - 1))
5167 ex_last--;
5168 else
5169 ex_start++;
5170 } else {
5171 le32_add_cpu(&ex_last->ee_block, shift);
5172 ext4_ext_try_to_merge_right(inode, path,
5173 ex_last);
5174 ex_last--;
5175 }
5176 }
5177 err = ext4_ext_dirty(handle, inode, path + depth);
5178 if (err)
5179 goto out;
5180
5181 if (--depth < 0 || !update)
5182 break;
5183 }
5184
5185
5186 err = ext4_access_path(handle, inode, path + depth);
5187 if (err)
5188 goto out;
5189
5190 if (SHIFT == SHIFT_LEFT)
5191 le32_add_cpu(&path[depth].p_idx->ei_block, -shift);
5192 else
5193 le32_add_cpu(&path[depth].p_idx->ei_block, shift);
5194 err = ext4_ext_dirty(handle, inode, path + depth);
5195 if (err)
5196 goto out;
5197
5198
5199 if (path[depth].p_idx != EXT_FIRST_INDEX(path[depth].p_hdr))
5200 break;
5201
5202 depth--;
5203 }
5204
5205out:
5206 return err;
5207}
5208
5209
5210
5211
5212
5213
5214
5215
5216static int
5217ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
5218 ext4_lblk_t start, ext4_lblk_t shift,
5219 enum SHIFT_DIRECTION SHIFT)
5220{
5221 struct ext4_ext_path *path;
5222 int ret = 0, depth;
5223 struct ext4_extent *extent;
5224 ext4_lblk_t stop, *iterator, ex_start, ex_end;
5225
5226
5227 path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
5228 EXT4_EX_NOCACHE);
5229 if (IS_ERR(path))
5230 return PTR_ERR(path);
5231
5232 depth = path->p_depth;
5233 extent = path[depth].p_ext;
5234 if (!extent)
5235 goto out;
5236
5237 stop = le32_to_cpu(extent->ee_block);
5238
5239
5240
5241
5242
5243
5244 if (SHIFT == SHIFT_LEFT) {
5245 path = ext4_find_extent(inode, start - 1, &path,
5246 EXT4_EX_NOCACHE);
5247 if (IS_ERR(path))
5248 return PTR_ERR(path);
5249 depth = path->p_depth;
5250 extent = path[depth].p_ext;
5251 if (extent) {
5252 ex_start = le32_to_cpu(extent->ee_block);
5253 ex_end = le32_to_cpu(extent->ee_block) +
5254 ext4_ext_get_actual_len(extent);
5255 } else {
5256 ex_start = 0;
5257 ex_end = 0;
5258 }
5259
5260 if ((start == ex_start && shift > ex_start) ||
5261 (shift > start - ex_end)) {
5262 ret = -EINVAL;
5263 goto out;
5264 }
5265 } else {
5266 if (shift > EXT_MAX_BLOCKS -
5267 (stop + ext4_ext_get_actual_len(extent))) {
5268 ret = -EINVAL;
5269 goto out;
5270 }
5271 }
5272
5273
5274
5275
5276
5277
5278 if (SHIFT == SHIFT_LEFT)
5279 iterator = &start;
5280 else
5281 iterator = &stop;
5282
5283
5284
5285
5286
5287
5288 while (iterator && start <= stop) {
5289 path = ext4_find_extent(inode, *iterator, &path,
5290 EXT4_EX_NOCACHE);
5291 if (IS_ERR(path))
5292 return PTR_ERR(path);
5293 depth = path->p_depth;
5294 extent = path[depth].p_ext;
5295 if (!extent) {
5296 EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
5297 (unsigned long) *iterator);
5298 return -EFSCORRUPTED;
5299 }
5300 if (SHIFT == SHIFT_LEFT && *iterator >
5301 le32_to_cpu(extent->ee_block)) {
5302
5303 if (extent < EXT_LAST_EXTENT(path[depth].p_hdr)) {
5304 path[depth].p_ext++;
5305 } else {
5306 *iterator = ext4_ext_next_allocated_block(path);
5307 continue;
5308 }
5309 }
5310
5311 if (SHIFT == SHIFT_LEFT) {
5312 extent = EXT_LAST_EXTENT(path[depth].p_hdr);
5313 *iterator = le32_to_cpu(extent->ee_block) +
5314 ext4_ext_get_actual_len(extent);
5315 } else {
5316 extent = EXT_FIRST_EXTENT(path[depth].p_hdr);
5317 if (le32_to_cpu(extent->ee_block) > 0)
5318 *iterator = le32_to_cpu(extent->ee_block) - 1;
5319 else
5320
5321 iterator = NULL;
5322
5323 while (le32_to_cpu(extent->ee_block) < start)
5324 extent++;
5325 path[depth].p_ext = extent;
5326 }
5327 ret = ext4_ext_shift_path_extents(path, shift, inode,
5328 handle, SHIFT);
5329 if (ret)
5330 break;
5331 }
5332out:
5333 ext4_ext_drop_refs(path);
5334 kfree(path);
5335 return ret;
5336}
5337
5338
5339
5340
5341
5342
5343int ext4_collapse_range(struct inode *inode, loff_t offset, loff_t len)
5344{
5345 struct super_block *sb = inode->i_sb;
5346 ext4_lblk_t punch_start, punch_stop;
5347 handle_t *handle;
5348 unsigned int credits;
5349 loff_t new_size, ioffset;
5350 int ret;
5351
5352
5353
5354
5355
5356
5357 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5358 return -EOPNOTSUPP;
5359
5360
5361 if (offset & (EXT4_CLUSTER_SIZE(sb) - 1) ||
5362 len & (EXT4_CLUSTER_SIZE(sb) - 1))
5363 return -EINVAL;
5364
5365 if (!S_ISREG(inode->i_mode))
5366 return -EINVAL;
5367
5368 trace_ext4_collapse_range(inode, offset, len);
5369
5370 punch_start = offset >> EXT4_BLOCK_SIZE_BITS(sb);
5371 punch_stop = (offset + len) >> EXT4_BLOCK_SIZE_BITS(sb);
5372
5373
5374 if (ext4_should_journal_data(inode)) {
5375 ret = ext4_force_commit(inode->i_sb);
5376 if (ret)
5377 return ret;
5378 }
5379
5380 inode_lock(inode);
5381
5382
5383
5384
5385 if (offset + len >= i_size_read(inode)) {
5386 ret = -EINVAL;
5387 goto out_mutex;
5388 }
5389
5390
5391 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
5392 ret = -EOPNOTSUPP;
5393 goto out_mutex;
5394 }
5395
5396
5397 inode_dio_wait(inode);
5398
5399
5400
5401
5402
5403 down_write(&EXT4_I(inode)->i_mmap_sem);
5404
5405 ret = ext4_break_layouts(inode);
5406 if (ret)
5407 goto out_mmap;
5408
5409
5410
5411
5412
5413 ioffset = round_down(offset, PAGE_SIZE);
5414
5415
5416
5417
5418 ret = filemap_write_and_wait_range(inode->i_mapping, ioffset, offset);
5419 if (ret)
5420 goto out_mmap;
5421
5422
5423
5424
5425
5426 ret = filemap_write_and_wait_range(inode->i_mapping, offset + len,
5427 LLONG_MAX);
5428 if (ret)
5429 goto out_mmap;
5430 truncate_pagecache(inode, ioffset);
5431
5432 credits = ext4_writepage_trans_blocks(inode);
5433 handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5434 if (IS_ERR(handle)) {
5435 ret = PTR_ERR(handle);
5436 goto out_mmap;
5437 }
5438
5439 down_write(&EXT4_I(inode)->i_data_sem);
5440 ext4_discard_preallocations(inode);
5441
5442 ret = ext4_es_remove_extent(inode, punch_start,
5443 EXT_MAX_BLOCKS - punch_start);
5444 if (ret) {
5445 up_write(&EXT4_I(inode)->i_data_sem);
5446 goto out_stop;
5447 }
5448
5449 ret = ext4_ext_remove_space(inode, punch_start, punch_stop - 1);
5450 if (ret) {
5451 up_write(&EXT4_I(inode)->i_data_sem);
5452 goto out_stop;
5453 }
5454 ext4_discard_preallocations(inode);
5455
5456 ret = ext4_ext_shift_extents(inode, handle, punch_stop,
5457 punch_stop - punch_start, SHIFT_LEFT);
5458 if (ret) {
5459 up_write(&EXT4_I(inode)->i_data_sem);
5460 goto out_stop;
5461 }
5462
5463 new_size = i_size_read(inode) - len;
5464 i_size_write(inode, new_size);
5465 EXT4_I(inode)->i_disksize = new_size;
5466
5467 up_write(&EXT4_I(inode)->i_data_sem);
5468 if (IS_SYNC(inode))
5469 ext4_handle_sync(handle);
5470 inode->i_mtime = inode->i_ctime = current_time(inode);
5471 ext4_mark_inode_dirty(handle, inode);
5472 ext4_update_inode_fsync_trans(handle, inode, 1);
5473
5474out_stop:
5475 ext4_journal_stop(handle);
5476out_mmap:
5477 up_write(&EXT4_I(inode)->i_mmap_sem);
5478out_mutex:
5479 inode_unlock(inode);
5480 return ret;
5481}
5482
5483
5484
5485
5486
5487
5488
5489
5490
5491int ext4_insert_range(struct inode *inode, loff_t offset, loff_t len)
5492{
5493 struct super_block *sb = inode->i_sb;
5494 handle_t *handle;
5495 struct ext4_ext_path *path;
5496 struct ext4_extent *extent;
5497 ext4_lblk_t offset_lblk, len_lblk, ee_start_lblk = 0;
5498 unsigned int credits, ee_len;
5499 int ret = 0, depth, split_flag = 0;
5500 loff_t ioffset;
5501
5502
5503
5504
5505
5506
5507 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5508 return -EOPNOTSUPP;
5509
5510
5511 if (offset & (EXT4_CLUSTER_SIZE(sb) - 1) ||
5512 len & (EXT4_CLUSTER_SIZE(sb) - 1))
5513 return -EINVAL;
5514
5515 if (!S_ISREG(inode->i_mode))
5516 return -EOPNOTSUPP;
5517
5518 trace_ext4_insert_range(inode, offset, len);
5519
5520 offset_lblk = offset >> EXT4_BLOCK_SIZE_BITS(sb);
5521 len_lblk = len >> EXT4_BLOCK_SIZE_BITS(sb);
5522
5523
5524 if (ext4_should_journal_data(inode)) {
5525 ret = ext4_force_commit(inode->i_sb);
5526 if (ret)
5527 return ret;
5528 }
5529
5530 inode_lock(inode);
5531
5532 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
5533 ret = -EOPNOTSUPP;
5534 goto out_mutex;
5535 }
5536
5537
5538 if (inode->i_size + len > inode->i_sb->s_maxbytes) {
5539 ret = -EFBIG;
5540 goto out_mutex;
5541 }
5542
5543
5544 if (offset >= i_size_read(inode)) {
5545 ret = -EINVAL;
5546 goto out_mutex;
5547 }
5548
5549
5550 inode_dio_wait(inode);
5551
5552
5553
5554
5555
5556 down_write(&EXT4_I(inode)->i_mmap_sem);
5557
5558 ret = ext4_break_layouts(inode);
5559 if (ret)
5560 goto out_mmap;
5561
5562
5563
5564
5565
5566 ioffset = round_down(offset, PAGE_SIZE);
5567
5568 ret = filemap_write_and_wait_range(inode->i_mapping, ioffset,
5569 LLONG_MAX);
5570 if (ret)
5571 goto out_mmap;
5572 truncate_pagecache(inode, ioffset);
5573
5574 credits = ext4_writepage_trans_blocks(inode);
5575 handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5576 if (IS_ERR(handle)) {
5577 ret = PTR_ERR(handle);
5578 goto out_mmap;
5579 }
5580
5581
5582 inode->i_size += len;
5583 EXT4_I(inode)->i_disksize += len;
5584 inode->i_mtime = inode->i_ctime = current_time(inode);
5585 ret = ext4_mark_inode_dirty(handle, inode);
5586 if (ret)
5587 goto out_stop;
5588
5589 down_write(&EXT4_I(inode)->i_data_sem);
5590 ext4_discard_preallocations(inode);
5591
5592 path = ext4_find_extent(inode, offset_lblk, NULL, 0);
5593 if (IS_ERR(path)) {
5594 up_write(&EXT4_I(inode)->i_data_sem);
5595 goto out_stop;
5596 }
5597
5598 depth = ext_depth(inode);
5599 extent = path[depth].p_ext;
5600 if (extent) {
5601 ee_start_lblk = le32_to_cpu(extent->ee_block);
5602 ee_len = ext4_ext_get_actual_len(extent);
5603
5604
5605
5606
5607
5608 if ((offset_lblk > ee_start_lblk) &&
5609 (offset_lblk < (ee_start_lblk + ee_len))) {
5610 if (ext4_ext_is_unwritten(extent))
5611 split_flag = EXT4_EXT_MARK_UNWRIT1 |
5612 EXT4_EXT_MARK_UNWRIT2;
5613 ret = ext4_split_extent_at(handle, inode, &path,
5614 offset_lblk, split_flag,
5615 EXT4_EX_NOCACHE |
5616 EXT4_GET_BLOCKS_PRE_IO |
5617 EXT4_GET_BLOCKS_METADATA_NOFAIL);
5618 }
5619
5620 ext4_ext_drop_refs(path);
5621 kfree(path);
5622 if (ret < 0) {
5623 up_write(&EXT4_I(inode)->i_data_sem);
5624 goto out_stop;
5625 }
5626 } else {
5627 ext4_ext_drop_refs(path);
5628 kfree(path);
5629 }
5630
5631 ret = ext4_es_remove_extent(inode, offset_lblk,
5632 EXT_MAX_BLOCKS - offset_lblk);
5633 if (ret) {
5634 up_write(&EXT4_I(inode)->i_data_sem);
5635 goto out_stop;
5636 }
5637
5638
5639
5640
5641
5642 ret = ext4_ext_shift_extents(inode, handle,
5643 ee_start_lblk > offset_lblk ? ee_start_lblk : offset_lblk,
5644 len_lblk, SHIFT_RIGHT);
5645
5646 up_write(&EXT4_I(inode)->i_data_sem);
5647 if (IS_SYNC(inode))
5648 ext4_handle_sync(handle);
5649 if (ret >= 0)
5650 ext4_update_inode_fsync_trans(handle, inode, 1);
5651
5652out_stop:
5653 ext4_journal_stop(handle);
5654out_mmap:
5655 up_write(&EXT4_I(inode)->i_mmap_sem);
5656out_mutex:
5657 inode_unlock(inode);
5658 return ret;
5659}
5660
5661
5662
5663
5664
5665
5666
5667
5668
5669
5670
5671
5672
5673
5674
5675
5676
5677
5678
5679
5680
5681int
5682ext4_swap_extents(handle_t *handle, struct inode *inode1,
5683 struct inode *inode2, ext4_lblk_t lblk1, ext4_lblk_t lblk2,
5684 ext4_lblk_t count, int unwritten, int *erp)
5685{
5686 struct ext4_ext_path *path1 = NULL;
5687 struct ext4_ext_path *path2 = NULL;
5688 int replaced_count = 0;
5689
5690 BUG_ON(!rwsem_is_locked(&EXT4_I(inode1)->i_data_sem));
5691 BUG_ON(!rwsem_is_locked(&EXT4_I(inode2)->i_data_sem));
5692 BUG_ON(!inode_is_locked(inode1));
5693 BUG_ON(!inode_is_locked(inode2));
5694
5695 *erp = ext4_es_remove_extent(inode1, lblk1, count);
5696 if (unlikely(*erp))
5697 return 0;
5698 *erp = ext4_es_remove_extent(inode2, lblk2, count);
5699 if (unlikely(*erp))
5700 return 0;
5701
5702 while (count) {
5703 struct ext4_extent *ex1, *ex2, tmp_ex;
5704 ext4_lblk_t e1_blk, e2_blk;
5705 int e1_len, e2_len, len;
5706 int split = 0;
5707
5708 path1 = ext4_find_extent(inode1, lblk1, NULL, EXT4_EX_NOCACHE);
5709 if (IS_ERR(path1)) {
5710 *erp = PTR_ERR(path1);
5711 path1 = NULL;
5712 finish:
5713 count = 0;
5714 goto repeat;
5715 }
5716 path2 = ext4_find_extent(inode2, lblk2, NULL, EXT4_EX_NOCACHE);
5717 if (IS_ERR(path2)) {
5718 *erp = PTR_ERR(path2);
5719 path2 = NULL;
5720 goto finish;
5721 }
5722 ex1 = path1[path1->p_depth].p_ext;
5723 ex2 = path2[path2->p_depth].p_ext;
5724
5725 if (unlikely(!ex2 || !ex1))
5726 goto finish;
5727
5728 e1_blk = le32_to_cpu(ex1->ee_block);
5729 e2_blk = le32_to_cpu(ex2->ee_block);
5730 e1_len = ext4_ext_get_actual_len(ex1);
5731 e2_len = ext4_ext_get_actual_len(ex2);
5732
5733
5734 if (!in_range(lblk1, e1_blk, e1_len) ||
5735 !in_range(lblk2, e2_blk, e2_len)) {
5736 ext4_lblk_t next1, next2;
5737
5738
5739 next1 = ext4_ext_next_allocated_block(path1);
5740 next2 = ext4_ext_next_allocated_block(path2);
5741
5742 if (e1_blk > lblk1)
5743 next1 = e1_blk;
5744 if (e2_blk > lblk2)
5745 next2 = e2_blk;
5746
5747 if (next1 == EXT_MAX_BLOCKS || next2 == EXT_MAX_BLOCKS)
5748 goto finish;
5749
5750 len = next1 - lblk1;
5751 if (len < next2 - lblk2)
5752 len = next2 - lblk2;
5753 if (len > count)
5754 len = count;
5755 lblk1 += len;
5756 lblk2 += len;
5757 count -= len;
5758 goto repeat;
5759 }
5760
5761
5762 if (e1_blk < lblk1) {
5763 split = 1;
5764 *erp = ext4_force_split_extent_at(handle, inode1,
5765 &path1, lblk1, 0);
5766 if (unlikely(*erp))
5767 goto finish;
5768 }
5769 if (e2_blk < lblk2) {
5770 split = 1;
5771 *erp = ext4_force_split_extent_at(handle, inode2,
5772 &path2, lblk2, 0);
5773 if (unlikely(*erp))
5774 goto finish;
5775 }
5776
5777
5778 if (split)
5779 goto repeat;
5780
5781
5782 len = count;
5783 if (len > e1_blk + e1_len - lblk1)
5784 len = e1_blk + e1_len - lblk1;
5785 if (len > e2_blk + e2_len - lblk2)
5786 len = e2_blk + e2_len - lblk2;
5787
5788 if (len != e1_len) {
5789 split = 1;
5790 *erp = ext4_force_split_extent_at(handle, inode1,
5791 &path1, lblk1 + len, 0);
5792 if (unlikely(*erp))
5793 goto finish;
5794 }
5795 if (len != e2_len) {
5796 split = 1;
5797 *erp = ext4_force_split_extent_at(handle, inode2,
5798 &path2, lblk2 + len, 0);
5799 if (*erp)
5800 goto finish;
5801 }
5802
5803
5804 if (split)
5805 goto repeat;
5806
5807 BUG_ON(e2_len != e1_len);
5808 *erp = ext4_ext_get_access(handle, inode1, path1 + path1->p_depth);
5809 if (unlikely(*erp))
5810 goto finish;
5811 *erp = ext4_ext_get_access(handle, inode2, path2 + path2->p_depth);
5812 if (unlikely(*erp))
5813 goto finish;
5814
5815
5816 tmp_ex = *ex1;
5817 ext4_ext_store_pblock(ex1, ext4_ext_pblock(ex2));
5818 ext4_ext_store_pblock(ex2, ext4_ext_pblock(&tmp_ex));
5819 ex1->ee_len = cpu_to_le16(e2_len);
5820 ex2->ee_len = cpu_to_le16(e1_len);
5821 if (unwritten)
5822 ext4_ext_mark_unwritten(ex2);
5823 if (ext4_ext_is_unwritten(&tmp_ex))
5824 ext4_ext_mark_unwritten(ex1);
5825
5826 ext4_ext_try_to_merge(handle, inode2, path2, ex2);
5827 ext4_ext_try_to_merge(handle, inode1, path1, ex1);
5828 *erp = ext4_ext_dirty(handle, inode2, path2 +
5829 path2->p_depth);
5830 if (unlikely(*erp))
5831 goto finish;
5832 *erp = ext4_ext_dirty(handle, inode1, path1 +
5833 path1->p_depth);
5834
5835
5836
5837
5838
5839
5840 if (unlikely(*erp))
5841 goto finish;
5842 lblk1 += len;
5843 lblk2 += len;
5844 replaced_count += len;
5845 count -= len;
5846
5847 repeat:
5848 ext4_ext_drop_refs(path1);
5849 kfree(path1);
5850 ext4_ext_drop_refs(path2);
5851 kfree(path2);
5852 path1 = path2 = NULL;
5853 }
5854 return replaced_count;
5855}
5856
5857
5858
5859
5860
5861
5862
5863
5864
5865
5866
5867
5868
5869int ext4_clu_mapped(struct inode *inode, ext4_lblk_t lclu)
5870{
5871 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
5872 struct ext4_ext_path *path;
5873 int depth, mapped = 0, err = 0;
5874 struct ext4_extent *extent;
5875 ext4_lblk_t first_lblk, first_lclu, last_lclu;
5876
5877
5878 path = ext4_find_extent(inode, EXT4_C2B(sbi, lclu), NULL, 0);
5879 if (IS_ERR(path)) {
5880 err = PTR_ERR(path);
5881 path = NULL;
5882 goto out;
5883 }
5884
5885 depth = ext_depth(inode);
5886
5887
5888
5889
5890
5891
5892 if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
5893 EXT4_ERROR_INODE(inode,
5894 "bad extent address - lblock: %lu, depth: %d, pblock: %lld",
5895 (unsigned long) EXT4_C2B(sbi, lclu),
5896 depth, path[depth].p_block);
5897 err = -EFSCORRUPTED;
5898 goto out;
5899 }
5900
5901 extent = path[depth].p_ext;
5902
5903
5904 if (extent == NULL)
5905 goto out;
5906
5907 first_lblk = le32_to_cpu(extent->ee_block);
5908 first_lclu = EXT4_B2C(sbi, first_lblk);
5909
5910
5911
5912
5913
5914
5915
5916 if (lclu >= first_lclu) {
5917 last_lclu = EXT4_B2C(sbi, first_lblk +
5918 ext4_ext_get_actual_len(extent) - 1);
5919 if (lclu <= last_lclu) {
5920 mapped = 1;
5921 } else {
5922 first_lblk = ext4_ext_next_allocated_block(path);
5923 first_lclu = EXT4_B2C(sbi, first_lblk);
5924 if (lclu == first_lclu)
5925 mapped = 1;
5926 }
5927 }
5928
5929out:
5930 ext4_ext_drop_refs(path);
5931 kfree(path);
5932
5933 return err ? err : mapped;
5934}
5935