1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include <linux/fs.h>
33#include <linux/time.h>
34#include <linux/jbd2.h>
35#include <linux/highuid.h>
36#include <linux/pagemap.h>
37#include <linux/quotaops.h>
38#include <linux/string.h>
39#include <linux/slab.h>
40#include <asm/uaccess.h>
41#include <linux/fiemap.h>
42#include <linux/backing-dev.h>
43#include "ext4_jbd2.h"
44#include "ext4_extents.h"
45#include "xattr.h"
46
47#include <trace/events/ext4.h>
48
49
50
51
52#define EXT4_EXT_MAY_ZEROOUT 0x1
53
54#define EXT4_EXT_MARK_UNWRIT1 0x2
55#define EXT4_EXT_MARK_UNWRIT2 0x4
56
57#define EXT4_EXT_DATA_VALID1 0x8
58#define EXT4_EXT_DATA_VALID2 0x10
59
60static __le32 ext4_extent_block_csum(struct inode *inode,
61 struct ext4_extent_header *eh)
62{
63 struct ext4_inode_info *ei = EXT4_I(inode);
64 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
65 __u32 csum;
66
67 csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)eh,
68 EXT4_EXTENT_TAIL_OFFSET(eh));
69 return cpu_to_le32(csum);
70}
71
72static int ext4_extent_block_csum_verify(struct inode *inode,
73 struct ext4_extent_header *eh)
74{
75 struct ext4_extent_tail *et;
76
77 if (!ext4_has_metadata_csum(inode->i_sb))
78 return 1;
79
80 et = find_ext4_extent_tail(eh);
81 if (et->et_checksum != ext4_extent_block_csum(inode, eh))
82 return 0;
83 return 1;
84}
85
86static void ext4_extent_block_csum_set(struct inode *inode,
87 struct ext4_extent_header *eh)
88{
89 struct ext4_extent_tail *et;
90
91 if (!ext4_has_metadata_csum(inode->i_sb))
92 return;
93
94 et = find_ext4_extent_tail(eh);
95 et->et_checksum = ext4_extent_block_csum(inode, eh);
96}
97
98static int ext4_split_extent(handle_t *handle,
99 struct inode *inode,
100 struct ext4_ext_path **ppath,
101 struct ext4_map_blocks *map,
102 int split_flag,
103 int flags);
104
105static int ext4_split_extent_at(handle_t *handle,
106 struct inode *inode,
107 struct ext4_ext_path **ppath,
108 ext4_lblk_t split,
109 int split_flag,
110 int flags);
111
112static int ext4_find_delayed_extent(struct inode *inode,
113 struct extent_status *newes);
114
115static int ext4_ext_truncate_extend_restart(handle_t *handle,
116 struct inode *inode,
117 int needed)
118{
119 int err;
120
121 if (!ext4_handle_valid(handle))
122 return 0;
123 if (handle->h_buffer_credits > needed)
124 return 0;
125 err = ext4_journal_extend(handle, needed);
126 if (err <= 0)
127 return err;
128 err = ext4_truncate_restart_trans(handle, inode, needed);
129 if (err == 0)
130 err = -EAGAIN;
131
132 return err;
133}
134
135
136
137
138
139
140static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
141 struct ext4_ext_path *path)
142{
143 if (path->p_bh) {
144
145 BUFFER_TRACE(path->p_bh, "get_write_access");
146 return ext4_journal_get_write_access(handle, path->p_bh);
147 }
148
149
150 return 0;
151}
152
153
154
155
156
157
158
159int __ext4_ext_dirty(const char *where, unsigned int line, handle_t *handle,
160 struct inode *inode, struct ext4_ext_path *path)
161{
162 int err;
163
164 WARN_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
165 if (path->p_bh) {
166 ext4_extent_block_csum_set(inode, ext_block_hdr(path->p_bh));
167
168 err = __ext4_handle_dirty_metadata(where, line, handle,
169 inode, path->p_bh);
170 } else {
171
172 err = ext4_mark_inode_dirty(handle, inode);
173 }
174 return err;
175}
176
177static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
178 struct ext4_ext_path *path,
179 ext4_lblk_t block)
180{
181 if (path) {
182 int depth = path->p_depth;
183 struct ext4_extent *ex;
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202 ex = path[depth].p_ext;
203 if (ex) {
204 ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
205 ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);
206
207 if (block > ext_block)
208 return ext_pblk + (block - ext_block);
209 else
210 return ext_pblk - (ext_block - block);
211 }
212
213
214
215 if (path[depth].p_bh)
216 return path[depth].p_bh->b_blocknr;
217 }
218
219
220 return ext4_inode_to_goal_block(inode);
221}
222
223
224
225
226static ext4_fsblk_t
227ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
228 struct ext4_ext_path *path,
229 struct ext4_extent *ex, int *err, unsigned int flags)
230{
231 ext4_fsblk_t goal, newblock;
232
233 goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
234 newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
235 NULL, err);
236 return newblock;
237}
238
239static inline int ext4_ext_space_block(struct inode *inode, int check)
240{
241 int size;
242
243 size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
244 / sizeof(struct ext4_extent);
245#ifdef AGGRESSIVE_TEST
246 if (!check && size > 6)
247 size = 6;
248#endif
249 return size;
250}
251
252static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
253{
254 int size;
255
256 size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
257 / sizeof(struct ext4_extent_idx);
258#ifdef AGGRESSIVE_TEST
259 if (!check && size > 5)
260 size = 5;
261#endif
262 return size;
263}
264
265static inline int ext4_ext_space_root(struct inode *inode, int check)
266{
267 int size;
268
269 size = sizeof(EXT4_I(inode)->i_data);
270 size -= sizeof(struct ext4_extent_header);
271 size /= sizeof(struct ext4_extent);
272#ifdef AGGRESSIVE_TEST
273 if (!check && size > 3)
274 size = 3;
275#endif
276 return size;
277}
278
279static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
280{
281 int size;
282
283 size = sizeof(EXT4_I(inode)->i_data);
284 size -= sizeof(struct ext4_extent_header);
285 size /= sizeof(struct ext4_extent_idx);
286#ifdef AGGRESSIVE_TEST
287 if (!check && size > 4)
288 size = 4;
289#endif
290 return size;
291}
292
293static inline int
294ext4_force_split_extent_at(handle_t *handle, struct inode *inode,
295 struct ext4_ext_path **ppath, ext4_lblk_t lblk,
296 int nofail)
297{
298 struct ext4_ext_path *path = *ppath;
299 int unwritten = ext4_ext_is_unwritten(path[path->p_depth].p_ext);
300
301 return ext4_split_extent_at(handle, inode, ppath, lblk, unwritten ?
302 EXT4_EXT_MARK_UNWRIT1|EXT4_EXT_MARK_UNWRIT2 : 0,
303 EXT4_EX_NOCACHE | EXT4_GET_BLOCKS_PRE_IO |
304 (nofail ? EXT4_GET_BLOCKS_METADATA_NOFAIL:0));
305}
306
307
308
309
310
311
312int ext4_ext_calc_metadata_amount(struct inode *inode, ext4_lblk_t lblock)
313{
314 struct ext4_inode_info *ei = EXT4_I(inode);
315 int idxs;
316
317 idxs = ((inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
318 / sizeof(struct ext4_extent_idx));
319
320
321
322
323
324
325
326
327
328 if (ei->i_da_metadata_calc_len &&
329 ei->i_da_metadata_calc_last_lblock+1 == lblock) {
330 int num = 0;
331
332 if ((ei->i_da_metadata_calc_len % idxs) == 0)
333 num++;
334 if ((ei->i_da_metadata_calc_len % (idxs*idxs)) == 0)
335 num++;
336 if ((ei->i_da_metadata_calc_len % (idxs*idxs*idxs)) == 0) {
337 num++;
338 ei->i_da_metadata_calc_len = 0;
339 } else
340 ei->i_da_metadata_calc_len++;
341 ei->i_da_metadata_calc_last_lblock++;
342 return num;
343 }
344
345
346
347
348
349 ei->i_da_metadata_calc_len = 1;
350 ei->i_da_metadata_calc_last_lblock = lblock;
351 return ext_depth(inode) + 1;
352}
353
354static int
355ext4_ext_max_entries(struct inode *inode, int depth)
356{
357 int max;
358
359 if (depth == ext_depth(inode)) {
360 if (depth == 0)
361 max = ext4_ext_space_root(inode, 1);
362 else
363 max = ext4_ext_space_root_idx(inode, 1);
364 } else {
365 if (depth == 0)
366 max = ext4_ext_space_block(inode, 1);
367 else
368 max = ext4_ext_space_block_idx(inode, 1);
369 }
370
371 return max;
372}
373
374static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
375{
376 ext4_fsblk_t block = ext4_ext_pblock(ext);
377 int len = ext4_ext_get_actual_len(ext);
378 ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
379 ext4_lblk_t last = lblock + len - 1;
380
381 if (len == 0 || lblock > last)
382 return 0;
383 return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
384}
385
386static int ext4_valid_extent_idx(struct inode *inode,
387 struct ext4_extent_idx *ext_idx)
388{
389 ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
390
391 return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
392}
393
394static int ext4_valid_extent_entries(struct inode *inode,
395 struct ext4_extent_header *eh,
396 int depth)
397{
398 unsigned short entries;
399 if (eh->eh_entries == 0)
400 return 1;
401
402 entries = le16_to_cpu(eh->eh_entries);
403
404 if (depth == 0) {
405
406 struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
407 struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
408 ext4_fsblk_t pblock = 0;
409 ext4_lblk_t lblock = 0;
410 ext4_lblk_t prev = 0;
411 int len = 0;
412 while (entries) {
413 if (!ext4_valid_extent(inode, ext))
414 return 0;
415
416
417 lblock = le32_to_cpu(ext->ee_block);
418 len = ext4_ext_get_actual_len(ext);
419 if ((lblock <= prev) && prev) {
420 pblock = ext4_ext_pblock(ext);
421 es->s_last_error_block = cpu_to_le64(pblock);
422 return 0;
423 }
424 ext++;
425 entries--;
426 prev = lblock + len - 1;
427 }
428 } else {
429 struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
430 while (entries) {
431 if (!ext4_valid_extent_idx(inode, ext_idx))
432 return 0;
433 ext_idx++;
434 entries--;
435 }
436 }
437 return 1;
438}
439
440static int __ext4_ext_check(const char *function, unsigned int line,
441 struct inode *inode, struct ext4_extent_header *eh,
442 int depth, ext4_fsblk_t pblk)
443{
444 const char *error_msg;
445 int max = 0, err = -EFSCORRUPTED;
446
447 if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
448 error_msg = "invalid magic";
449 goto corrupted;
450 }
451 if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
452 error_msg = "unexpected eh_depth";
453 goto corrupted;
454 }
455 if (unlikely(eh->eh_max == 0)) {
456 error_msg = "invalid eh_max";
457 goto corrupted;
458 }
459 max = ext4_ext_max_entries(inode, depth);
460 if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
461 error_msg = "too large eh_max";
462 goto corrupted;
463 }
464 if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
465 error_msg = "invalid eh_entries";
466 goto corrupted;
467 }
468 if (!ext4_valid_extent_entries(inode, eh, depth)) {
469 error_msg = "invalid extent entries";
470 goto corrupted;
471 }
472
473 if (ext_depth(inode) != depth &&
474 !ext4_extent_block_csum_verify(inode, eh)) {
475 error_msg = "extent tree corrupted";
476 err = -EFSBADCRC;
477 goto corrupted;
478 }
479 return 0;
480
481corrupted:
482 ext4_error_inode(inode, function, line, 0,
483 "pblk %llu bad header/extent: %s - magic %x, "
484 "entries %u, max %u(%u), depth %u(%u)",
485 (unsigned long long) pblk, error_msg,
486 le16_to_cpu(eh->eh_magic),
487 le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
488 max, le16_to_cpu(eh->eh_depth), depth);
489 return err;
490}
491
492#define ext4_ext_check(inode, eh, depth, pblk) \
493 __ext4_ext_check(__func__, __LINE__, (inode), (eh), (depth), (pblk))
494
495int ext4_ext_check_inode(struct inode *inode)
496{
497 return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode), 0);
498}
499
500static struct buffer_head *
501__read_extent_tree_block(const char *function, unsigned int line,
502 struct inode *inode, ext4_fsblk_t pblk, int depth,
503 int flags)
504{
505 struct buffer_head *bh;
506 int err;
507
508 bh = sb_getblk_gfp(inode->i_sb, pblk, __GFP_MOVABLE | GFP_NOFS);
509 if (unlikely(!bh))
510 return ERR_PTR(-ENOMEM);
511
512 if (!bh_uptodate_or_lock(bh)) {
513 trace_ext4_ext_load_extent(inode, pblk, _RET_IP_);
514 err = bh_submit_read(bh);
515 if (err < 0)
516 goto errout;
517 }
518 if (buffer_verified(bh) && !(flags & EXT4_EX_FORCE_CACHE))
519 return bh;
520 err = __ext4_ext_check(function, line, inode,
521 ext_block_hdr(bh), depth, pblk);
522 if (err)
523 goto errout;
524 set_buffer_verified(bh);
525
526
527
528 if (!(flags & EXT4_EX_NOCACHE) && depth == 0) {
529 struct ext4_extent_header *eh = ext_block_hdr(bh);
530 struct ext4_extent *ex = EXT_FIRST_EXTENT(eh);
531 ext4_lblk_t prev = 0;
532 int i;
533
534 for (i = le16_to_cpu(eh->eh_entries); i > 0; i--, ex++) {
535 unsigned int status = EXTENT_STATUS_WRITTEN;
536 ext4_lblk_t lblk = le32_to_cpu(ex->ee_block);
537 int len = ext4_ext_get_actual_len(ex);
538
539 if (prev && (prev != lblk))
540 ext4_es_cache_extent(inode, prev,
541 lblk - prev, ~0,
542 EXTENT_STATUS_HOLE);
543
544 if (ext4_ext_is_unwritten(ex))
545 status = EXTENT_STATUS_UNWRITTEN;
546 ext4_es_cache_extent(inode, lblk, len,
547 ext4_ext_pblock(ex), status);
548 prev = lblk + len;
549 }
550 }
551 return bh;
552errout:
553 put_bh(bh);
554 return ERR_PTR(err);
555
556}
557
558#define read_extent_tree_block(inode, pblk, depth, flags) \
559 __read_extent_tree_block(__func__, __LINE__, (inode), (pblk), \
560 (depth), (flags))
561
562
563
564
565
566int ext4_ext_precache(struct inode *inode)
567{
568 struct ext4_inode_info *ei = EXT4_I(inode);
569 struct ext4_ext_path *path = NULL;
570 struct buffer_head *bh;
571 int i = 0, depth, ret = 0;
572
573 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
574 return 0;
575
576 down_read(&ei->i_data_sem);
577 depth = ext_depth(inode);
578
579 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1),
580 GFP_NOFS);
581 if (path == NULL) {
582 up_read(&ei->i_data_sem);
583 return -ENOMEM;
584 }
585
586
587 if (depth == 0)
588 goto out;
589 path[0].p_hdr = ext_inode_hdr(inode);
590 ret = ext4_ext_check(inode, path[0].p_hdr, depth, 0);
591 if (ret)
592 goto out;
593 path[0].p_idx = EXT_FIRST_INDEX(path[0].p_hdr);
594 while (i >= 0) {
595
596
597
598
599 if ((i == depth) ||
600 path[i].p_idx > EXT_LAST_INDEX(path[i].p_hdr)) {
601 brelse(path[i].p_bh);
602 path[i].p_bh = NULL;
603 i--;
604 continue;
605 }
606 bh = read_extent_tree_block(inode,
607 ext4_idx_pblock(path[i].p_idx++),
608 depth - i - 1,
609 EXT4_EX_FORCE_CACHE);
610 if (IS_ERR(bh)) {
611 ret = PTR_ERR(bh);
612 break;
613 }
614 i++;
615 path[i].p_bh = bh;
616 path[i].p_hdr = ext_block_hdr(bh);
617 path[i].p_idx = EXT_FIRST_INDEX(path[i].p_hdr);
618 }
619 ext4_set_inode_state(inode, EXT4_STATE_EXT_PRECACHED);
620out:
621 up_read(&ei->i_data_sem);
622 ext4_ext_drop_refs(path);
623 kfree(path);
624 return ret;
625}
626
627#ifdef EXT_DEBUG
628static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
629{
630 int k, l = path->p_depth;
631
632 ext_debug("path:");
633 for (k = 0; k <= l; k++, path++) {
634 if (path->p_idx) {
635 ext_debug(" %d->%llu", le32_to_cpu(path->p_idx->ei_block),
636 ext4_idx_pblock(path->p_idx));
637 } else if (path->p_ext) {
638 ext_debug(" %d:[%d]%d:%llu ",
639 le32_to_cpu(path->p_ext->ee_block),
640 ext4_ext_is_unwritten(path->p_ext),
641 ext4_ext_get_actual_len(path->p_ext),
642 ext4_ext_pblock(path->p_ext));
643 } else
644 ext_debug(" []");
645 }
646 ext_debug("\n");
647}
648
649static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
650{
651 int depth = ext_depth(inode);
652 struct ext4_extent_header *eh;
653 struct ext4_extent *ex;
654 int i;
655
656 if (!path)
657 return;
658
659 eh = path[depth].p_hdr;
660 ex = EXT_FIRST_EXTENT(eh);
661
662 ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino);
663
664 for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
665 ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
666 ext4_ext_is_unwritten(ex),
667 ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
668 }
669 ext_debug("\n");
670}
671
672static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
673 ext4_fsblk_t newblock, int level)
674{
675 int depth = ext_depth(inode);
676 struct ext4_extent *ex;
677
678 if (depth != level) {
679 struct ext4_extent_idx *idx;
680 idx = path[level].p_idx;
681 while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
682 ext_debug("%d: move %d:%llu in new index %llu\n", level,
683 le32_to_cpu(idx->ei_block),
684 ext4_idx_pblock(idx),
685 newblock);
686 idx++;
687 }
688
689 return;
690 }
691
692 ex = path[depth].p_ext;
693 while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
694 ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
695 le32_to_cpu(ex->ee_block),
696 ext4_ext_pblock(ex),
697 ext4_ext_is_unwritten(ex),
698 ext4_ext_get_actual_len(ex),
699 newblock);
700 ex++;
701 }
702}
703
704#else
705#define ext4_ext_show_path(inode, path)
706#define ext4_ext_show_leaf(inode, path)
707#define ext4_ext_show_move(inode, path, newblock, level)
708#endif
709
710void ext4_ext_drop_refs(struct ext4_ext_path *path)
711{
712 int depth, i;
713
714 if (!path)
715 return;
716 depth = path->p_depth;
717 for (i = 0; i <= depth; i++, path++)
718 if (path->p_bh) {
719 brelse(path->p_bh);
720 path->p_bh = NULL;
721 }
722}
723
724
725
726
727
728
729static void
730ext4_ext_binsearch_idx(struct inode *inode,
731 struct ext4_ext_path *path, ext4_lblk_t block)
732{
733 struct ext4_extent_header *eh = path->p_hdr;
734 struct ext4_extent_idx *r, *l, *m;
735
736
737 ext_debug("binsearch for %u(idx): ", block);
738
739 l = EXT_FIRST_INDEX(eh) + 1;
740 r = EXT_LAST_INDEX(eh);
741 while (l <= r) {
742 m = l + (r - l) / 2;
743 if (block < le32_to_cpu(m->ei_block))
744 r = m - 1;
745 else
746 l = m + 1;
747 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
748 m, le32_to_cpu(m->ei_block),
749 r, le32_to_cpu(r->ei_block));
750 }
751
752 path->p_idx = l - 1;
753 ext_debug(" -> %u->%lld ", le32_to_cpu(path->p_idx->ei_block),
754 ext4_idx_pblock(path->p_idx));
755
756#ifdef CHECK_BINSEARCH
757 {
758 struct ext4_extent_idx *chix, *ix;
759 int k;
760
761 chix = ix = EXT_FIRST_INDEX(eh);
762 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
763 if (k != 0 &&
764 le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
765 printk(KERN_DEBUG "k=%d, ix=0x%p, "
766 "first=0x%p\n", k,
767 ix, EXT_FIRST_INDEX(eh));
768 printk(KERN_DEBUG "%u <= %u\n",
769 le32_to_cpu(ix->ei_block),
770 le32_to_cpu(ix[-1].ei_block));
771 }
772 BUG_ON(k && le32_to_cpu(ix->ei_block)
773 <= le32_to_cpu(ix[-1].ei_block));
774 if (block < le32_to_cpu(ix->ei_block))
775 break;
776 chix = ix;
777 }
778 BUG_ON(chix != path->p_idx);
779 }
780#endif
781
782}
783
784
785
786
787
788
789static void
790ext4_ext_binsearch(struct inode *inode,
791 struct ext4_ext_path *path, ext4_lblk_t block)
792{
793 struct ext4_extent_header *eh = path->p_hdr;
794 struct ext4_extent *r, *l, *m;
795
796 if (eh->eh_entries == 0) {
797
798
799
800
801 return;
802 }
803
804 ext_debug("binsearch for %u: ", block);
805
806 l = EXT_FIRST_EXTENT(eh) + 1;
807 r = EXT_LAST_EXTENT(eh);
808
809 while (l <= r) {
810 m = l + (r - l) / 2;
811 if (block < le32_to_cpu(m->ee_block))
812 r = m - 1;
813 else
814 l = m + 1;
815 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
816 m, le32_to_cpu(m->ee_block),
817 r, le32_to_cpu(r->ee_block));
818 }
819
820 path->p_ext = l - 1;
821 ext_debug(" -> %d:%llu:[%d]%d ",
822 le32_to_cpu(path->p_ext->ee_block),
823 ext4_ext_pblock(path->p_ext),
824 ext4_ext_is_unwritten(path->p_ext),
825 ext4_ext_get_actual_len(path->p_ext));
826
827#ifdef CHECK_BINSEARCH
828 {
829 struct ext4_extent *chex, *ex;
830 int k;
831
832 chex = ex = EXT_FIRST_EXTENT(eh);
833 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
834 BUG_ON(k && le32_to_cpu(ex->ee_block)
835 <= le32_to_cpu(ex[-1].ee_block));
836 if (block < le32_to_cpu(ex->ee_block))
837 break;
838 chex = ex;
839 }
840 BUG_ON(chex != path->p_ext);
841 }
842#endif
843
844}
845
846int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
847{
848 struct ext4_extent_header *eh;
849
850 eh = ext_inode_hdr(inode);
851 eh->eh_depth = 0;
852 eh->eh_entries = 0;
853 eh->eh_magic = EXT4_EXT_MAGIC;
854 eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
855 ext4_mark_inode_dirty(handle, inode);
856 return 0;
857}
858
859struct ext4_ext_path *
860ext4_find_extent(struct inode *inode, ext4_lblk_t block,
861 struct ext4_ext_path **orig_path, int flags)
862{
863 struct ext4_extent_header *eh;
864 struct buffer_head *bh;
865 struct ext4_ext_path *path = orig_path ? *orig_path : NULL;
866 short int depth, i, ppos = 0;
867 int ret;
868
869 eh = ext_inode_hdr(inode);
870 depth = ext_depth(inode);
871
872 if (path) {
873 ext4_ext_drop_refs(path);
874 if (depth > path[0].p_maxdepth) {
875 kfree(path);
876 *orig_path = path = NULL;
877 }
878 }
879 if (!path) {
880
881 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
882 GFP_NOFS);
883 if (unlikely(!path))
884 return ERR_PTR(-ENOMEM);
885 path[0].p_maxdepth = depth + 1;
886 }
887 path[0].p_hdr = eh;
888 path[0].p_bh = NULL;
889
890 i = depth;
891
892 while (i) {
893 ext_debug("depth %d: num %d, max %d\n",
894 ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
895
896 ext4_ext_binsearch_idx(inode, path + ppos, block);
897 path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
898 path[ppos].p_depth = i;
899 path[ppos].p_ext = NULL;
900
901 bh = read_extent_tree_block(inode, path[ppos].p_block, --i,
902 flags);
903 if (IS_ERR(bh)) {
904 ret = PTR_ERR(bh);
905 goto err;
906 }
907
908 eh = ext_block_hdr(bh);
909 ppos++;
910 if (unlikely(ppos > depth)) {
911 put_bh(bh);
912 EXT4_ERROR_INODE(inode,
913 "ppos %d > depth %d", ppos, depth);
914 ret = -EFSCORRUPTED;
915 goto err;
916 }
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 = kzalloc(sizeof(ext4_fsblk_t) * depth, 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_delayed_extent_range(inode, 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 return EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET;
2487 else if (ext4_should_journal_data(inode))
2488 return EXT4_FREE_BLOCKS_FORGET;
2489 return 0;
2490}
2491
2492static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
2493 struct ext4_extent *ex,
2494 long long *partial_cluster,
2495 ext4_lblk_t from, ext4_lblk_t to)
2496{
2497 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2498 unsigned short ee_len = ext4_ext_get_actual_len(ex);
2499 ext4_fsblk_t pblk;
2500 int flags = get_default_free_blocks_flags(inode);
2501
2502
2503
2504
2505
2506
2507
2508
2509 flags |= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER;
2510
2511 trace_ext4_remove_blocks(inode, ex, from, to, *partial_cluster);
2512
2513
2514
2515
2516
2517 pblk = ext4_ext_pblock(ex) + ee_len - 1;
2518 if (*partial_cluster > 0 &&
2519 *partial_cluster != (long long) EXT4_B2C(sbi, pblk)) {
2520 ext4_free_blocks(handle, inode, NULL,
2521 EXT4_C2B(sbi, *partial_cluster),
2522 sbi->s_cluster_ratio, flags);
2523 *partial_cluster = 0;
2524 }
2525
2526#ifdef EXTENTS_STATS
2527 {
2528 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2529 spin_lock(&sbi->s_ext_stats_lock);
2530 sbi->s_ext_blocks += ee_len;
2531 sbi->s_ext_extents++;
2532 if (ee_len < sbi->s_ext_min)
2533 sbi->s_ext_min = ee_len;
2534 if (ee_len > sbi->s_ext_max)
2535 sbi->s_ext_max = ee_len;
2536 if (ext_depth(inode) > sbi->s_depth_max)
2537 sbi->s_depth_max = ext_depth(inode);
2538 spin_unlock(&sbi->s_ext_stats_lock);
2539 }
2540#endif
2541 if (from >= le32_to_cpu(ex->ee_block)
2542 && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
2543
2544 ext4_lblk_t num;
2545 long long first_cluster;
2546
2547 num = le32_to_cpu(ex->ee_block) + ee_len - from;
2548 pblk = ext4_ext_pblock(ex) + ee_len - num;
2549
2550
2551
2552
2553
2554 if (*partial_cluster < 0 &&
2555 *partial_cluster == -(long long) EXT4_B2C(sbi, pblk+num-1))
2556 flags |= EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER;
2557
2558 ext_debug("free last %u blocks starting %llu partial %lld\n",
2559 num, pblk, *partial_cluster);
2560 ext4_free_blocks(handle, inode, NULL, pblk, num, flags);
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577 if (EXT4_PBLK_COFF(sbi, pblk) && ee_len == num) {
2578 first_cluster = (long long) EXT4_B2C(sbi, pblk);
2579 if (first_cluster != -*partial_cluster)
2580 *partial_cluster = first_cluster;
2581 } else {
2582 *partial_cluster = 0;
2583 }
2584 } else
2585 ext4_error(sbi->s_sb, "strange request: removal(2) "
2586 "%u-%u from %u:%u\n",
2587 from, to, le32_to_cpu(ex->ee_block), ee_len);
2588 return 0;
2589}
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607static int
2608ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
2609 struct ext4_ext_path *path,
2610 long long *partial_cluster,
2611 ext4_lblk_t start, ext4_lblk_t end)
2612{
2613 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2614 int err = 0, correct_index = 0;
2615 int depth = ext_depth(inode), credits;
2616 struct ext4_extent_header *eh;
2617 ext4_lblk_t a, b;
2618 unsigned num;
2619 ext4_lblk_t ex_ee_block;
2620 unsigned short ex_ee_len;
2621 unsigned unwritten = 0;
2622 struct ext4_extent *ex;
2623 ext4_fsblk_t pblk;
2624
2625
2626 ext_debug("truncate since %u in leaf to %u\n", start, end);
2627 if (!path[depth].p_hdr)
2628 path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
2629 eh = path[depth].p_hdr;
2630 if (unlikely(path[depth].p_hdr == NULL)) {
2631 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2632 return -EFSCORRUPTED;
2633 }
2634
2635 ex = path[depth].p_ext;
2636 if (!ex)
2637 ex = EXT_LAST_EXTENT(eh);
2638
2639 ex_ee_block = le32_to_cpu(ex->ee_block);
2640 ex_ee_len = ext4_ext_get_actual_len(ex);
2641
2642 trace_ext4_ext_rm_leaf(inode, start, ex, *partial_cluster);
2643
2644 while (ex >= EXT_FIRST_EXTENT(eh) &&
2645 ex_ee_block + ex_ee_len > start) {
2646
2647 if (ext4_ext_is_unwritten(ex))
2648 unwritten = 1;
2649 else
2650 unwritten = 0;
2651
2652 ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
2653 unwritten, ex_ee_len);
2654 path[depth].p_ext = ex;
2655
2656 a = ex_ee_block > start ? ex_ee_block : start;
2657 b = ex_ee_block+ex_ee_len - 1 < end ?
2658 ex_ee_block+ex_ee_len - 1 : end;
2659
2660 ext_debug(" border %u:%u\n", a, b);
2661
2662
2663 if (end < ex_ee_block) {
2664
2665
2666
2667
2668
2669
2670
2671 if (sbi->s_cluster_ratio > 1) {
2672 pblk = ext4_ext_pblock(ex);
2673 *partial_cluster =
2674 -(long long) EXT4_B2C(sbi, pblk);
2675 }
2676 ex--;
2677 ex_ee_block = le32_to_cpu(ex->ee_block);
2678 ex_ee_len = ext4_ext_get_actual_len(ex);
2679 continue;
2680 } else if (b != ex_ee_block + ex_ee_len - 1) {
2681 EXT4_ERROR_INODE(inode,
2682 "can not handle truncate %u:%u "
2683 "on extent %u:%u",
2684 start, end, ex_ee_block,
2685 ex_ee_block + ex_ee_len - 1);
2686 err = -EFSCORRUPTED;
2687 goto out;
2688 } else if (a != ex_ee_block) {
2689
2690 num = a - ex_ee_block;
2691 } else {
2692
2693 num = 0;
2694 }
2695
2696
2697
2698
2699
2700
2701 credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
2702 if (ex == EXT_FIRST_EXTENT(eh)) {
2703 correct_index = 1;
2704 credits += (ext_depth(inode)) + 1;
2705 }
2706 credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
2707
2708 err = ext4_ext_truncate_extend_restart(handle, inode, credits);
2709 if (err)
2710 goto out;
2711
2712 err = ext4_ext_get_access(handle, inode, path + depth);
2713 if (err)
2714 goto out;
2715
2716 err = ext4_remove_blocks(handle, inode, ex, partial_cluster,
2717 a, b);
2718 if (err)
2719 goto out;
2720
2721 if (num == 0)
2722
2723 ext4_ext_store_pblock(ex, 0);
2724
2725 ex->ee_len = cpu_to_le16(num);
2726
2727
2728
2729
2730 if (unwritten && num)
2731 ext4_ext_mark_unwritten(ex);
2732
2733
2734
2735
2736 if (num == 0) {
2737 if (end != EXT_MAX_BLOCKS - 1) {
2738
2739
2740
2741
2742
2743 memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
2744 sizeof(struct ext4_extent));
2745
2746
2747 memset(EXT_LAST_EXTENT(eh), 0,
2748 sizeof(struct ext4_extent));
2749 }
2750 le16_add_cpu(&eh->eh_entries, -1);
2751 }
2752
2753 err = ext4_ext_dirty(handle, inode, path + depth);
2754 if (err)
2755 goto out;
2756
2757 ext_debug("new extent: %u:%u:%llu\n", ex_ee_block, num,
2758 ext4_ext_pblock(ex));
2759 ex--;
2760 ex_ee_block = le32_to_cpu(ex->ee_block);
2761 ex_ee_len = ext4_ext_get_actual_len(ex);
2762 }
2763
2764 if (correct_index && eh->eh_entries)
2765 err = ext4_ext_correct_indexes(handle, inode, path);
2766
2767
2768
2769
2770
2771
2772
2773
2774 if (*partial_cluster > 0 && ex >= EXT_FIRST_EXTENT(eh)) {
2775 pblk = ext4_ext_pblock(ex) + ex_ee_len - 1;
2776 if (*partial_cluster != (long long) EXT4_B2C(sbi, pblk)) {
2777 ext4_free_blocks(handle, inode, NULL,
2778 EXT4_C2B(sbi, *partial_cluster),
2779 sbi->s_cluster_ratio,
2780 get_default_free_blocks_flags(inode));
2781 }
2782 *partial_cluster = 0;
2783 }
2784
2785
2786
2787 if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2788 err = ext4_ext_rm_idx(handle, inode, path, depth);
2789
2790out:
2791 return err;
2792}
2793
2794
2795
2796
2797
2798static int
2799ext4_ext_more_to_rm(struct ext4_ext_path *path)
2800{
2801 BUG_ON(path->p_idx == NULL);
2802
2803 if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2804 return 0;
2805
2806
2807
2808
2809
2810 if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2811 return 0;
2812 return 1;
2813}
2814
2815int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
2816 ext4_lblk_t end)
2817{
2818 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2819 int depth = ext_depth(inode);
2820 struct ext4_ext_path *path = NULL;
2821 long long partial_cluster = 0;
2822 handle_t *handle;
2823 int i = 0, err = 0;
2824
2825 ext_debug("truncate since %u to %u\n", start, end);
2826
2827
2828 handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, depth + 1);
2829 if (IS_ERR(handle))
2830 return PTR_ERR(handle);
2831
2832again:
2833 trace_ext4_ext_remove_space(inode, start, end, depth);
2834
2835
2836
2837
2838
2839
2840
2841
2842 if (end < EXT_MAX_BLOCKS - 1) {
2843 struct ext4_extent *ex;
2844 ext4_lblk_t ee_block, ex_end, lblk;
2845 ext4_fsblk_t pblk;
2846
2847
2848 path = ext4_find_extent(inode, end, NULL, EXT4_EX_NOCACHE);
2849 if (IS_ERR(path)) {
2850 ext4_journal_stop(handle);
2851 return PTR_ERR(path);
2852 }
2853 depth = ext_depth(inode);
2854
2855 ex = path[depth].p_ext;
2856 if (!ex) {
2857 if (depth) {
2858 EXT4_ERROR_INODE(inode,
2859 "path[%d].p_hdr == NULL",
2860 depth);
2861 err = -EFSCORRUPTED;
2862 }
2863 goto out;
2864 }
2865
2866 ee_block = le32_to_cpu(ex->ee_block);
2867 ex_end = ee_block + ext4_ext_get_actual_len(ex) - 1;
2868
2869
2870
2871
2872
2873
2874
2875 if (end >= ee_block && end < ex_end) {
2876
2877
2878
2879
2880
2881
2882 if (sbi->s_cluster_ratio > 1) {
2883 pblk = ext4_ext_pblock(ex) + end - ee_block + 2;
2884 partial_cluster =
2885 -(long long) EXT4_B2C(sbi, pblk);
2886 }
2887
2888
2889
2890
2891
2892
2893
2894 err = ext4_force_split_extent_at(handle, inode, &path,
2895 end + 1, 1);
2896 if (err < 0)
2897 goto out;
2898
2899 } else if (sbi->s_cluster_ratio > 1 && end >= ex_end) {
2900
2901
2902
2903
2904
2905
2906
2907
2908 lblk = ex_end + 1;
2909 err = ext4_ext_search_right(inode, path, &lblk, &pblk,
2910 &ex);
2911 if (err)
2912 goto out;
2913 if (pblk)
2914 partial_cluster =
2915 -(long long) EXT4_B2C(sbi, pblk);
2916 }
2917 }
2918
2919
2920
2921
2922 depth = ext_depth(inode);
2923 if (path) {
2924 int k = i = depth;
2925 while (--k > 0)
2926 path[k].p_block =
2927 le16_to_cpu(path[k].p_hdr->eh_entries)+1;
2928 } else {
2929 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1),
2930 GFP_NOFS);
2931 if (path == NULL) {
2932 ext4_journal_stop(handle);
2933 return -ENOMEM;
2934 }
2935 path[0].p_maxdepth = path[0].p_depth = depth;
2936 path[0].p_hdr = ext_inode_hdr(inode);
2937 i = 0;
2938
2939 if (ext4_ext_check(inode, path[0].p_hdr, depth, 0)) {
2940 err = -EFSCORRUPTED;
2941 goto out;
2942 }
2943 }
2944 err = 0;
2945
2946 while (i >= 0 && err == 0) {
2947 if (i == depth) {
2948
2949 err = ext4_ext_rm_leaf(handle, inode, path,
2950 &partial_cluster, start,
2951 end);
2952
2953 brelse(path[i].p_bh);
2954 path[i].p_bh = NULL;
2955 i--;
2956 continue;
2957 }
2958
2959
2960 if (!path[i].p_hdr) {
2961 ext_debug("initialize header\n");
2962 path[i].p_hdr = ext_block_hdr(path[i].p_bh);
2963 }
2964
2965 if (!path[i].p_idx) {
2966
2967 path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
2968 path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
2969 ext_debug("init index ptr: hdr 0x%p, num %d\n",
2970 path[i].p_hdr,
2971 le16_to_cpu(path[i].p_hdr->eh_entries));
2972 } else {
2973
2974 path[i].p_idx--;
2975 }
2976
2977 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2978 i, EXT_FIRST_INDEX(path[i].p_hdr),
2979 path[i].p_idx);
2980 if (ext4_ext_more_to_rm(path + i)) {
2981 struct buffer_head *bh;
2982
2983 ext_debug("move to level %d (block %llu)\n",
2984 i + 1, ext4_idx_pblock(path[i].p_idx));
2985 memset(path + i + 1, 0, sizeof(*path));
2986 bh = read_extent_tree_block(inode,
2987 ext4_idx_pblock(path[i].p_idx), depth - i - 1,
2988 EXT4_EX_NOCACHE);
2989 if (IS_ERR(bh)) {
2990
2991 err = PTR_ERR(bh);
2992 break;
2993 }
2994
2995
2996 cond_resched();
2997 if (WARN_ON(i + 1 > depth)) {
2998 err = -EFSCORRUPTED;
2999 break;
3000 }
3001 path[i + 1].p_bh = bh;
3002
3003
3004
3005 path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
3006 i++;
3007 } else {
3008
3009 if (path[i].p_hdr->eh_entries == 0 && i > 0) {
3010
3011
3012
3013 err = ext4_ext_rm_idx(handle, inode, path, i);
3014 }
3015
3016 brelse(path[i].p_bh);
3017 path[i].p_bh = NULL;
3018 i--;
3019 ext_debug("return to level %d\n", i);
3020 }
3021 }
3022
3023 trace_ext4_ext_remove_space_done(inode, start, end, depth,
3024 partial_cluster, path->p_hdr->eh_entries);
3025
3026
3027
3028
3029
3030
3031
3032 if (partial_cluster > 0 && err == 0) {
3033
3034 ext4_free_blocks(handle, inode, NULL,
3035 EXT4_C2B(sbi, partial_cluster),
3036 sbi->s_cluster_ratio,
3037 get_default_free_blocks_flags(inode));
3038 }
3039
3040
3041 if (path->p_hdr->eh_entries == 0) {
3042
3043
3044
3045
3046 err = ext4_ext_get_access(handle, inode, path);
3047 if (err == 0) {
3048 ext_inode_hdr(inode)->eh_depth = 0;
3049 ext_inode_hdr(inode)->eh_max =
3050 cpu_to_le16(ext4_ext_space_root(inode, 0));
3051 err = ext4_ext_dirty(handle, inode, path);
3052 }
3053 }
3054out:
3055 ext4_ext_drop_refs(path);
3056 kfree(path);
3057 path = NULL;
3058 if (err == -EAGAIN)
3059 goto again;
3060 ext4_journal_stop(handle);
3061
3062 return err;
3063}
3064
3065
3066
3067
3068void ext4_ext_init(struct super_block *sb)
3069{
3070
3071
3072
3073
3074 if (ext4_has_feature_extents(sb)) {
3075#if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
3076 printk(KERN_INFO "EXT4-fs: file extents enabled"
3077#ifdef AGGRESSIVE_TEST
3078 ", aggressive tests"
3079#endif
3080#ifdef CHECK_BINSEARCH
3081 ", check binsearch"
3082#endif
3083#ifdef EXTENTS_STATS
3084 ", stats"
3085#endif
3086 "\n");
3087#endif
3088#ifdef EXTENTS_STATS
3089 spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
3090 EXT4_SB(sb)->s_ext_min = 1 << 30;
3091 EXT4_SB(sb)->s_ext_max = 0;
3092#endif
3093 }
3094}
3095
3096
3097
3098
3099void ext4_ext_release(struct super_block *sb)
3100{
3101 if (!ext4_has_feature_extents(sb))
3102 return;
3103
3104#ifdef EXTENTS_STATS
3105 if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
3106 struct ext4_sb_info *sbi = EXT4_SB(sb);
3107 printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
3108 sbi->s_ext_blocks, sbi->s_ext_extents,
3109 sbi->s_ext_blocks / sbi->s_ext_extents);
3110 printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
3111 sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
3112 }
3113#endif
3114}
3115
3116static int ext4_zeroout_es(struct inode *inode, struct ext4_extent *ex)
3117{
3118 ext4_lblk_t ee_block;
3119 ext4_fsblk_t ee_pblock;
3120 unsigned int ee_len;
3121
3122 ee_block = le32_to_cpu(ex->ee_block);
3123 ee_len = ext4_ext_get_actual_len(ex);
3124 ee_pblock = ext4_ext_pblock(ex);
3125
3126 if (ee_len == 0)
3127 return 0;
3128
3129 return ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock,
3130 EXTENT_STATUS_WRITTEN);
3131}
3132
3133
3134static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
3135{
3136 ext4_fsblk_t ee_pblock;
3137 unsigned int ee_len;
3138
3139 ee_len = ext4_ext_get_actual_len(ex);
3140 ee_pblock = ext4_ext_pblock(ex);
3141 return ext4_issue_zeroout(inode, le32_to_cpu(ex->ee_block), ee_pblock,
3142 ee_len);
3143}
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166static int ext4_split_extent_at(handle_t *handle,
3167 struct inode *inode,
3168 struct ext4_ext_path **ppath,
3169 ext4_lblk_t split,
3170 int split_flag,
3171 int flags)
3172{
3173 struct ext4_ext_path *path = *ppath;
3174 ext4_fsblk_t newblock;
3175 ext4_lblk_t ee_block;
3176 struct ext4_extent *ex, newex, orig_ex, zero_ex;
3177 struct ext4_extent *ex2 = NULL;
3178 unsigned int ee_len, depth;
3179 int err = 0;
3180
3181 BUG_ON((split_flag & (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2)) ==
3182 (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2));
3183
3184 ext_debug("ext4_split_extents_at: inode %lu, logical"
3185 "block %llu\n", inode->i_ino, (unsigned long long)split);
3186
3187 ext4_ext_show_leaf(inode, path);
3188
3189 depth = ext_depth(inode);
3190 ex = path[depth].p_ext;
3191 ee_block = le32_to_cpu(ex->ee_block);
3192 ee_len = ext4_ext_get_actual_len(ex);
3193 newblock = split - ee_block + ext4_ext_pblock(ex);
3194
3195 BUG_ON(split < ee_block || split >= (ee_block + ee_len));
3196 BUG_ON(!ext4_ext_is_unwritten(ex) &&
3197 split_flag & (EXT4_EXT_MAY_ZEROOUT |
3198 EXT4_EXT_MARK_UNWRIT1 |
3199 EXT4_EXT_MARK_UNWRIT2));
3200
3201 err = ext4_ext_get_access(handle, inode, path + depth);
3202 if (err)
3203 goto out;
3204
3205 if (split == ee_block) {
3206
3207
3208
3209
3210
3211 if (split_flag & EXT4_EXT_MARK_UNWRIT2)
3212 ext4_ext_mark_unwritten(ex);
3213 else
3214 ext4_ext_mark_initialized(ex);
3215
3216 if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
3217 ext4_ext_try_to_merge(handle, inode, path, ex);
3218
3219 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3220 goto out;
3221 }
3222
3223
3224 memcpy(&orig_ex, ex, sizeof(orig_ex));
3225 ex->ee_len = cpu_to_le16(split - ee_block);
3226 if (split_flag & EXT4_EXT_MARK_UNWRIT1)
3227 ext4_ext_mark_unwritten(ex);
3228
3229
3230
3231
3232
3233 err = ext4_ext_dirty(handle, inode, path + depth);
3234 if (err)
3235 goto fix_extent_len;
3236
3237 ex2 = &newex;
3238 ex2->ee_block = cpu_to_le32(split);
3239 ex2->ee_len = cpu_to_le16(ee_len - (split - ee_block));
3240 ext4_ext_store_pblock(ex2, newblock);
3241 if (split_flag & EXT4_EXT_MARK_UNWRIT2)
3242 ext4_ext_mark_unwritten(ex2);
3243
3244 err = ext4_ext_insert_extent(handle, inode, ppath, &newex, flags);
3245 if (err == -ENOSPC && (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
3246 if (split_flag & (EXT4_EXT_DATA_VALID1|EXT4_EXT_DATA_VALID2)) {
3247 if (split_flag & EXT4_EXT_DATA_VALID1) {
3248 err = ext4_ext_zeroout(inode, ex2);
3249 zero_ex.ee_block = ex2->ee_block;
3250 zero_ex.ee_len = cpu_to_le16(
3251 ext4_ext_get_actual_len(ex2));
3252 ext4_ext_store_pblock(&zero_ex,
3253 ext4_ext_pblock(ex2));
3254 } else {
3255 err = ext4_ext_zeroout(inode, ex);
3256 zero_ex.ee_block = ex->ee_block;
3257 zero_ex.ee_len = cpu_to_le16(
3258 ext4_ext_get_actual_len(ex));
3259 ext4_ext_store_pblock(&zero_ex,
3260 ext4_ext_pblock(ex));
3261 }
3262 } else {
3263 err = ext4_ext_zeroout(inode, &orig_ex);
3264 zero_ex.ee_block = orig_ex.ee_block;
3265 zero_ex.ee_len = cpu_to_le16(
3266 ext4_ext_get_actual_len(&orig_ex));
3267 ext4_ext_store_pblock(&zero_ex,
3268 ext4_ext_pblock(&orig_ex));
3269 }
3270
3271 if (err)
3272 goto fix_extent_len;
3273
3274 ex->ee_len = cpu_to_le16(ee_len);
3275 ext4_ext_try_to_merge(handle, inode, path, ex);
3276 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3277 if (err)
3278 goto fix_extent_len;
3279
3280
3281 err = ext4_zeroout_es(inode, &zero_ex);
3282
3283 goto out;
3284 } else if (err)
3285 goto fix_extent_len;
3286
3287out:
3288 ext4_ext_show_leaf(inode, path);
3289 return err;
3290
3291fix_extent_len:
3292 ex->ee_len = orig_ex.ee_len;
3293 ext4_ext_dirty(handle, inode, path + path->p_depth);
3294 return err;
3295}
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308static int ext4_split_extent(handle_t *handle,
3309 struct inode *inode,
3310 struct ext4_ext_path **ppath,
3311 struct ext4_map_blocks *map,
3312 int split_flag,
3313 int flags)
3314{
3315 struct ext4_ext_path *path = *ppath;
3316 ext4_lblk_t ee_block;
3317 struct ext4_extent *ex;
3318 unsigned int ee_len, depth;
3319 int err = 0;
3320 int unwritten;
3321 int split_flag1, flags1;
3322 int allocated = map->m_len;
3323
3324 depth = ext_depth(inode);
3325 ex = path[depth].p_ext;
3326 ee_block = le32_to_cpu(ex->ee_block);
3327 ee_len = ext4_ext_get_actual_len(ex);
3328 unwritten = ext4_ext_is_unwritten(ex);
3329
3330 if (map->m_lblk + map->m_len < ee_block + ee_len) {
3331 split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;
3332 flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
3333 if (unwritten)
3334 split_flag1 |= EXT4_EXT_MARK_UNWRIT1 |
3335 EXT4_EXT_MARK_UNWRIT2;
3336 if (split_flag & EXT4_EXT_DATA_VALID2)
3337 split_flag1 |= EXT4_EXT_DATA_VALID1;
3338 err = ext4_split_extent_at(handle, inode, ppath,
3339 map->m_lblk + map->m_len, split_flag1, flags1);
3340 if (err)
3341 goto out;
3342 } else {
3343 allocated = ee_len - (map->m_lblk - ee_block);
3344 }
3345
3346
3347
3348
3349 path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3350 if (IS_ERR(path))
3351 return PTR_ERR(path);
3352 depth = ext_depth(inode);
3353 ex = path[depth].p_ext;
3354 if (!ex) {
3355 EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3356 (unsigned long) map->m_lblk);
3357 return -EFSCORRUPTED;
3358 }
3359 unwritten = ext4_ext_is_unwritten(ex);
3360 split_flag1 = 0;
3361
3362 if (map->m_lblk >= ee_block) {
3363 split_flag1 = split_flag & EXT4_EXT_DATA_VALID2;
3364 if (unwritten) {
3365 split_flag1 |= EXT4_EXT_MARK_UNWRIT1;
3366 split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT |
3367 EXT4_EXT_MARK_UNWRIT2);
3368 }
3369 err = ext4_split_extent_at(handle, inode, ppath,
3370 map->m_lblk, split_flag1, flags);
3371 if (err)
3372 goto out;
3373 }
3374
3375 ext4_ext_show_leaf(inode, path);
3376out:
3377 return err ? err : allocated;
3378}
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400static int ext4_ext_convert_to_initialized(handle_t *handle,
3401 struct inode *inode,
3402 struct ext4_map_blocks *map,
3403 struct ext4_ext_path **ppath,
3404 int flags)
3405{
3406 struct ext4_ext_path *path = *ppath;
3407 struct ext4_sb_info *sbi;
3408 struct ext4_extent_header *eh;
3409 struct ext4_map_blocks split_map;
3410 struct ext4_extent zero_ex;
3411 struct ext4_extent *ex, *abut_ex;
3412 ext4_lblk_t ee_block, eof_block;
3413 unsigned int ee_len, depth, map_len = map->m_len;
3414 int allocated = 0, max_zeroout = 0;
3415 int err = 0;
3416 int split_flag = 0;
3417
3418 ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
3419 "block %llu, max_blocks %u\n", inode->i_ino,
3420 (unsigned long long)map->m_lblk, map_len);
3421
3422 sbi = EXT4_SB(inode->i_sb);
3423 eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3424 inode->i_sb->s_blocksize_bits;
3425 if (eof_block < map->m_lblk + map_len)
3426 eof_block = map->m_lblk + map_len;
3427
3428 depth = ext_depth(inode);
3429 eh = path[depth].p_hdr;
3430 ex = path[depth].p_ext;
3431 ee_block = le32_to_cpu(ex->ee_block);
3432 ee_len = ext4_ext_get_actual_len(ex);
3433 zero_ex.ee_len = 0;
3434
3435 trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);
3436
3437
3438 BUG_ON(!ext4_ext_is_unwritten(ex));
3439 BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456 if ((map->m_lblk == ee_block) &&
3457
3458 (map_len < ee_len) &&
3459 (ex > EXT_FIRST_EXTENT(eh))) {
3460 ext4_lblk_t prev_lblk;
3461 ext4_fsblk_t prev_pblk, ee_pblk;
3462 unsigned int prev_len;
3463
3464 abut_ex = ex - 1;
3465 prev_lblk = le32_to_cpu(abut_ex->ee_block);
3466 prev_len = ext4_ext_get_actual_len(abut_ex);
3467 prev_pblk = ext4_ext_pblock(abut_ex);
3468 ee_pblk = ext4_ext_pblock(ex);
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479 if ((!ext4_ext_is_unwritten(abut_ex)) &&
3480 ((prev_lblk + prev_len) == ee_block) &&
3481 ((prev_pblk + prev_len) == ee_pblk) &&
3482 (prev_len < (EXT_INIT_MAX_LEN - map_len))) {
3483 err = ext4_ext_get_access(handle, inode, path + depth);
3484 if (err)
3485 goto out;
3486
3487 trace_ext4_ext_convert_to_initialized_fastpath(inode,
3488 map, ex, abut_ex);
3489
3490
3491 ex->ee_block = cpu_to_le32(ee_block + map_len);
3492 ext4_ext_store_pblock(ex, ee_pblk + map_len);
3493 ex->ee_len = cpu_to_le16(ee_len - map_len);
3494 ext4_ext_mark_unwritten(ex);
3495
3496
3497 abut_ex->ee_len = cpu_to_le16(prev_len + map_len);
3498
3499
3500 allocated = map_len;
3501 }
3502 } else if (((map->m_lblk + map_len) == (ee_block + ee_len)) &&
3503 (map_len < ee_len) &&
3504 ex < EXT_LAST_EXTENT(eh)) {
3505
3506 ext4_lblk_t next_lblk;
3507 ext4_fsblk_t next_pblk, ee_pblk;
3508 unsigned int next_len;
3509
3510 abut_ex = ex + 1;
3511 next_lblk = le32_to_cpu(abut_ex->ee_block);
3512 next_len = ext4_ext_get_actual_len(abut_ex);
3513 next_pblk = ext4_ext_pblock(abut_ex);
3514 ee_pblk = ext4_ext_pblock(ex);
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525 if ((!ext4_ext_is_unwritten(abut_ex)) &&
3526 ((map->m_lblk + map_len) == next_lblk) &&
3527 ((ee_pblk + ee_len) == next_pblk) &&
3528 (next_len < (EXT_INIT_MAX_LEN - map_len))) {
3529 err = ext4_ext_get_access(handle, inode, path + depth);
3530 if (err)
3531 goto out;
3532
3533 trace_ext4_ext_convert_to_initialized_fastpath(inode,
3534 map, ex, abut_ex);
3535
3536
3537 abut_ex->ee_block = cpu_to_le32(next_lblk - map_len);
3538 ext4_ext_store_pblock(abut_ex, next_pblk - map_len);
3539 ex->ee_len = cpu_to_le16(ee_len - map_len);
3540 ext4_ext_mark_unwritten(ex);
3541
3542
3543 abut_ex->ee_len = cpu_to_le16(next_len + map_len);
3544
3545
3546 allocated = map_len;
3547 }
3548 }
3549 if (allocated) {
3550
3551 ext4_ext_dirty(handle, inode, path + depth);
3552
3553
3554 path[depth].p_ext = abut_ex;
3555 goto out;
3556 } else
3557 allocated = ee_len - (map->m_lblk - ee_block);
3558
3559 WARN_ON(map->m_lblk < ee_block);
3560
3561
3562
3563
3564 split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3565
3566 if (EXT4_EXT_MAY_ZEROOUT & split_flag)
3567 max_zeroout = sbi->s_extent_max_zeroout_kb >>
3568 (inode->i_sb->s_blocksize_bits - 10);
3569
3570 if (ext4_encrypted_inode(inode))
3571 max_zeroout = 0;
3572
3573
3574 if (max_zeroout && (ee_len <= max_zeroout)) {
3575 err = ext4_ext_zeroout(inode, ex);
3576 if (err)
3577 goto out;
3578 zero_ex.ee_block = ex->ee_block;
3579 zero_ex.ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex));
3580 ext4_ext_store_pblock(&zero_ex, ext4_ext_pblock(ex));
3581
3582 err = ext4_ext_get_access(handle, inode, path + depth);
3583 if (err)
3584 goto out;
3585 ext4_ext_mark_initialized(ex);
3586 ext4_ext_try_to_merge(handle, inode, path, ex);
3587 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3588 goto out;
3589 }
3590
3591
3592
3593
3594
3595
3596
3597
3598 split_map.m_lblk = map->m_lblk;
3599 split_map.m_len = map->m_len;
3600
3601 if (max_zeroout && (allocated > map->m_len)) {
3602 if (allocated <= max_zeroout) {
3603
3604 zero_ex.ee_block =
3605 cpu_to_le32(map->m_lblk);
3606 zero_ex.ee_len = cpu_to_le16(allocated);
3607 ext4_ext_store_pblock(&zero_ex,
3608 ext4_ext_pblock(ex) + map->m_lblk - ee_block);
3609 err = ext4_ext_zeroout(inode, &zero_ex);
3610 if (err)
3611 goto out;
3612 split_map.m_lblk = map->m_lblk;
3613 split_map.m_len = allocated;
3614 } else if (map->m_lblk - ee_block + map->m_len < max_zeroout) {
3615
3616 if (map->m_lblk != ee_block) {
3617 zero_ex.ee_block = ex->ee_block;
3618 zero_ex.ee_len = cpu_to_le16(map->m_lblk -
3619 ee_block);
3620 ext4_ext_store_pblock(&zero_ex,
3621 ext4_ext_pblock(ex));
3622 err = ext4_ext_zeroout(inode, &zero_ex);
3623 if (err)
3624 goto out;
3625 }
3626
3627 split_map.m_lblk = ee_block;
3628 split_map.m_len = map->m_lblk - ee_block + map->m_len;
3629 allocated = map->m_len;
3630 }
3631 }
3632
3633 err = ext4_split_extent(handle, inode, ppath, &split_map, split_flag,
3634 flags);
3635 if (err > 0)
3636 err = 0;
3637out:
3638
3639 if (!err)
3640 err = ext4_zeroout_es(inode, &zero_ex);
3641 return err ? err : allocated;
3642}
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668static int ext4_split_convert_extents(handle_t *handle,
3669 struct inode *inode,
3670 struct ext4_map_blocks *map,
3671 struct ext4_ext_path **ppath,
3672 int flags)
3673{
3674 struct ext4_ext_path *path = *ppath;
3675 ext4_lblk_t eof_block;
3676 ext4_lblk_t ee_block;
3677 struct ext4_extent *ex;
3678 unsigned int ee_len;
3679 int split_flag = 0, depth;
3680
3681 ext_debug("%s: inode %lu, logical block %llu, max_blocks %u\n",
3682 __func__, inode->i_ino,
3683 (unsigned long long)map->m_lblk, map->m_len);
3684
3685 eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3686 inode->i_sb->s_blocksize_bits;
3687 if (eof_block < map->m_lblk + map->m_len)
3688 eof_block = map->m_lblk + map->m_len;
3689
3690
3691
3692
3693 depth = ext_depth(inode);
3694 ex = path[depth].p_ext;
3695 ee_block = le32_to_cpu(ex->ee_block);
3696 ee_len = ext4_ext_get_actual_len(ex);
3697
3698
3699 if (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN) {
3700 split_flag |= EXT4_EXT_DATA_VALID1;
3701
3702 } else if (flags & EXT4_GET_BLOCKS_CONVERT) {
3703 split_flag |= ee_block + ee_len <= eof_block ?
3704 EXT4_EXT_MAY_ZEROOUT : 0;
3705 split_flag |= (EXT4_EXT_MARK_UNWRIT2 | EXT4_EXT_DATA_VALID2);
3706 }
3707 flags |= EXT4_GET_BLOCKS_PRE_IO;
3708 return ext4_split_extent(handle, inode, ppath, map, split_flag, flags);
3709}
3710
3711static int ext4_convert_unwritten_extents_endio(handle_t *handle,
3712 struct inode *inode,
3713 struct ext4_map_blocks *map,
3714 struct ext4_ext_path **ppath)
3715{
3716 struct ext4_ext_path *path = *ppath;
3717 struct ext4_extent *ex;
3718 ext4_lblk_t ee_block;
3719 unsigned int ee_len;
3720 int depth;
3721 int err = 0;
3722
3723 depth = ext_depth(inode);
3724 ex = path[depth].p_ext;
3725 ee_block = le32_to_cpu(ex->ee_block);
3726 ee_len = ext4_ext_get_actual_len(ex);
3727
3728 ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
3729 "block %llu, max_blocks %u\n", inode->i_ino,
3730 (unsigned long long)ee_block, ee_len);
3731
3732
3733
3734
3735
3736
3737
3738 if (ee_block != map->m_lblk || ee_len > map->m_len) {
3739#ifdef EXT4_DEBUG
3740 ext4_warning("Inode (%ld) finished: extent logical block %llu,"
3741 " len %u; IO logical block %llu, len %u\n",
3742 inode->i_ino, (unsigned long long)ee_block, ee_len,
3743 (unsigned long long)map->m_lblk, map->m_len);
3744#endif
3745 err = ext4_split_convert_extents(handle, inode, map, ppath,
3746 EXT4_GET_BLOCKS_CONVERT);
3747 if (err < 0)
3748 return err;
3749 path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3750 if (IS_ERR(path))
3751 return PTR_ERR(path);
3752 depth = ext_depth(inode);
3753 ex = path[depth].p_ext;
3754 }
3755
3756 err = ext4_ext_get_access(handle, inode, path + depth);
3757 if (err)
3758 goto out;
3759
3760 ext4_ext_mark_initialized(ex);
3761
3762
3763
3764
3765 ext4_ext_try_to_merge(handle, inode, path, ex);
3766
3767
3768 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3769out:
3770 ext4_ext_show_leaf(inode, path);
3771 return err;
3772}
3773
3774static void unmap_underlying_metadata_blocks(struct block_device *bdev,
3775 sector_t block, int count)
3776{
3777 int i;
3778 for (i = 0; i < count; i++)
3779 unmap_underlying_metadata(bdev, block + i);
3780}
3781
3782
3783
3784
3785static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
3786 ext4_lblk_t lblk,
3787 struct ext4_ext_path *path,
3788 unsigned int len)
3789{
3790 int i, depth;
3791 struct ext4_extent_header *eh;
3792 struct ext4_extent *last_ex;
3793
3794 if (!ext4_test_inode_flag(inode, EXT4_INODE_EOFBLOCKS))
3795 return 0;
3796
3797 depth = ext_depth(inode);
3798 eh = path[depth].p_hdr;
3799
3800
3801
3802
3803
3804
3805 if (unlikely(!eh->eh_entries))
3806 goto out;
3807 last_ex = EXT_LAST_EXTENT(eh);
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817 if (lblk + len < le32_to_cpu(last_ex->ee_block) +
3818 ext4_ext_get_actual_len(last_ex))
3819 return 0;
3820
3821
3822
3823
3824
3825
3826
3827 for (i = depth-1; i >= 0; i--)
3828 if (path[i].p_idx != EXT_LAST_INDEX(path[i].p_hdr))
3829 return 0;
3830out:
3831 ext4_clear_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
3832 return ext4_mark_inode_dirty(handle, inode);
3833}
3834
3835
3836
3837
3838
3839
3840int ext4_find_delalloc_range(struct inode *inode,
3841 ext4_lblk_t lblk_start,
3842 ext4_lblk_t lblk_end)
3843{
3844 struct extent_status es;
3845
3846 ext4_es_find_delayed_extent_range(inode, lblk_start, lblk_end, &es);
3847 if (es.es_len == 0)
3848 return 0;
3849 else if (es.es_lblk <= lblk_start &&
3850 lblk_start < es.es_lblk + es.es_len)
3851 return 1;
3852 else if (lblk_start <= es.es_lblk && es.es_lblk <= lblk_end)
3853 return 1;
3854 else
3855 return 0;
3856}
3857
3858int ext4_find_delalloc_cluster(struct inode *inode, ext4_lblk_t lblk)
3859{
3860 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
3861 ext4_lblk_t lblk_start, lblk_end;
3862 lblk_start = EXT4_LBLK_CMASK(sbi, lblk);
3863 lblk_end = lblk_start + sbi->s_cluster_ratio - 1;
3864
3865 return ext4_find_delalloc_range(inode, lblk_start, lblk_end);
3866}
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903static unsigned int
3904get_reserved_cluster_alloc(struct inode *inode, ext4_lblk_t lblk_start,
3905 unsigned int num_blks)
3906{
3907 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
3908 ext4_lblk_t alloc_cluster_start, alloc_cluster_end;
3909 ext4_lblk_t lblk_from, lblk_to, c_offset;
3910 unsigned int allocated_clusters = 0;
3911
3912 alloc_cluster_start = EXT4_B2C(sbi, lblk_start);
3913 alloc_cluster_end = EXT4_B2C(sbi, lblk_start + num_blks - 1);
3914
3915
3916 allocated_clusters = alloc_cluster_end - alloc_cluster_start + 1;
3917
3918 trace_ext4_get_reserved_cluster_alloc(inode, lblk_start, num_blks);
3919
3920
3921 c_offset = EXT4_LBLK_COFF(sbi, lblk_start);
3922 if (c_offset) {
3923 lblk_from = EXT4_LBLK_CMASK(sbi, lblk_start);
3924 lblk_to = lblk_from + c_offset - 1;
3925
3926 if (ext4_find_delalloc_range(inode, lblk_from, lblk_to))
3927 allocated_clusters--;
3928 }
3929
3930
3931 c_offset = EXT4_LBLK_COFF(sbi, lblk_start + num_blks);
3932 if (allocated_clusters && c_offset) {
3933 lblk_from = lblk_start + num_blks;
3934 lblk_to = lblk_from + (sbi->s_cluster_ratio - c_offset) - 1;
3935
3936 if (ext4_find_delalloc_range(inode, lblk_from, lblk_to))
3937 allocated_clusters--;
3938 }
3939
3940 return allocated_clusters;
3941}
3942
3943static int
3944convert_initialized_extent(handle_t *handle, struct inode *inode,
3945 struct ext4_map_blocks *map,
3946 struct ext4_ext_path **ppath,
3947 unsigned int allocated)
3948{
3949 struct ext4_ext_path *path = *ppath;
3950 struct ext4_extent *ex;
3951 ext4_lblk_t ee_block;
3952 unsigned int ee_len;
3953 int depth;
3954 int err = 0;
3955
3956
3957
3958
3959
3960 if (map->m_len > EXT_UNWRITTEN_MAX_LEN)
3961 map->m_len = EXT_UNWRITTEN_MAX_LEN / 2;
3962
3963 depth = ext_depth(inode);
3964 ex = path[depth].p_ext;
3965 ee_block = le32_to_cpu(ex->ee_block);
3966 ee_len = ext4_ext_get_actual_len(ex);
3967
3968 ext_debug("%s: inode %lu, logical"
3969 "block %llu, max_blocks %u\n", __func__, inode->i_ino,
3970 (unsigned long long)ee_block, ee_len);
3971
3972 if (ee_block != map->m_lblk || ee_len > map->m_len) {
3973 err = ext4_split_convert_extents(handle, inode, map, ppath,
3974 EXT4_GET_BLOCKS_CONVERT_UNWRITTEN);
3975 if (err < 0)
3976 return err;
3977 path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3978 if (IS_ERR(path))
3979 return PTR_ERR(path);
3980 depth = ext_depth(inode);
3981 ex = path[depth].p_ext;
3982 if (!ex) {
3983 EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3984 (unsigned long) map->m_lblk);
3985 return -EFSCORRUPTED;
3986 }
3987 }
3988
3989 err = ext4_ext_get_access(handle, inode, path + depth);
3990 if (err)
3991 return err;
3992
3993 ext4_ext_mark_unwritten(ex);
3994
3995
3996
3997
3998 ext4_ext_try_to_merge(handle, inode, path, ex);
3999
4000
4001 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
4002 if (err)
4003 return err;
4004 ext4_ext_show_leaf(inode, path);
4005
4006 ext4_update_inode_fsync_trans(handle, inode, 1);
4007 err = check_eofblocks_fl(handle, inode, map->m_lblk, path, map->m_len);
4008 if (err)
4009 return err;
4010 map->m_flags |= EXT4_MAP_UNWRITTEN;
4011 if (allocated > map->m_len)
4012 allocated = map->m_len;
4013 map->m_len = allocated;
4014 return allocated;
4015}
4016
4017static int
4018ext4_ext_handle_unwritten_extents(handle_t *handle, struct inode *inode,
4019 struct ext4_map_blocks *map,
4020 struct ext4_ext_path **ppath, int flags,
4021 unsigned int allocated, ext4_fsblk_t newblock)
4022{
4023 struct ext4_ext_path *path = *ppath;
4024 int ret = 0;
4025 int err = 0;
4026
4027 ext_debug("ext4_ext_handle_unwritten_extents: inode %lu, logical "
4028 "block %llu, max_blocks %u, flags %x, allocated %u\n",
4029 inode->i_ino, (unsigned long long)map->m_lblk, map->m_len,
4030 flags, allocated);
4031 ext4_ext_show_leaf(inode, path);
4032
4033
4034
4035
4036
4037 flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL;
4038
4039 trace_ext4_ext_handle_unwritten_extents(inode, map, flags,
4040 allocated, newblock);
4041
4042
4043 if (flags & EXT4_GET_BLOCKS_PRE_IO) {
4044 ret = ext4_split_convert_extents(handle, inode, map, ppath,
4045 flags | EXT4_GET_BLOCKS_CONVERT);
4046 if (ret <= 0)
4047 goto out;
4048 map->m_flags |= EXT4_MAP_UNWRITTEN;
4049 goto out;
4050 }
4051
4052 if (flags & EXT4_GET_BLOCKS_CONVERT) {
4053 if (flags & EXT4_GET_BLOCKS_ZERO) {
4054 if (allocated > map->m_len)
4055 allocated = map->m_len;
4056 err = ext4_issue_zeroout(inode, map->m_lblk, newblock,
4057 allocated);
4058 if (err < 0)
4059 goto out2;
4060 }
4061 ret = ext4_convert_unwritten_extents_endio(handle, inode, map,
4062 ppath);
4063 if (ret >= 0) {
4064 ext4_update_inode_fsync_trans(handle, inode, 1);
4065 err = check_eofblocks_fl(handle, inode, map->m_lblk,
4066 path, map->m_len);
4067 } else
4068 err = ret;
4069 map->m_flags |= EXT4_MAP_MAPPED;
4070 map->m_pblk = newblock;
4071 if (allocated > map->m_len)
4072 allocated = map->m_len;
4073 map->m_len = allocated;
4074 goto out2;
4075 }
4076
4077
4078
4079
4080
4081 if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
4082 map->m_flags |= EXT4_MAP_UNWRITTEN;
4083 goto map_out;
4084 }
4085
4086
4087 if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4088
4089
4090
4091
4092
4093
4094
4095 map->m_flags |= EXT4_MAP_UNWRITTEN;
4096 goto out1;
4097 }
4098
4099
4100 ret = ext4_ext_convert_to_initialized(handle, inode, map, ppath, flags);
4101 if (ret >= 0)
4102 ext4_update_inode_fsync_trans(handle, inode, 1);
4103out:
4104 if (ret <= 0) {
4105 err = ret;
4106 goto out2;
4107 } else
4108 allocated = ret;
4109 map->m_flags |= EXT4_MAP_NEW;
4110
4111
4112
4113
4114
4115
4116
4117 if (allocated > map->m_len) {
4118 unmap_underlying_metadata_blocks(inode->i_sb->s_bdev,
4119 newblock + map->m_len,
4120 allocated - map->m_len);
4121 allocated = map->m_len;
4122 }
4123 map->m_len = allocated;
4124
4125
4126
4127
4128
4129
4130
4131
4132 if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
4133 unsigned int reserved_clusters;
4134 reserved_clusters = get_reserved_cluster_alloc(inode,
4135 map->m_lblk, map->m_len);
4136 if (reserved_clusters)
4137 ext4_da_update_reserve_space(inode,
4138 reserved_clusters,
4139 0);
4140 }
4141
4142map_out:
4143 map->m_flags |= EXT4_MAP_MAPPED;
4144 if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0) {
4145 err = check_eofblocks_fl(handle, inode, map->m_lblk, path,
4146 map->m_len);
4147 if (err < 0)
4148 goto out2;
4149 }
4150out1:
4151 if (allocated > map->m_len)
4152 allocated = map->m_len;
4153 ext4_ext_show_leaf(inode, path);
4154 map->m_pblk = newblock;
4155 map->m_len = allocated;
4156out2:
4157 return err ? err : allocated;
4158}
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201static int get_implied_cluster_alloc(struct super_block *sb,
4202 struct ext4_map_blocks *map,
4203 struct ext4_extent *ex,
4204 struct ext4_ext_path *path)
4205{
4206 struct ext4_sb_info *sbi = EXT4_SB(sb);
4207 ext4_lblk_t c_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4208 ext4_lblk_t ex_cluster_start, ex_cluster_end;
4209 ext4_lblk_t rr_cluster_start;
4210 ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4211 ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4212 unsigned short ee_len = ext4_ext_get_actual_len(ex);
4213
4214
4215 ex_cluster_start = EXT4_B2C(sbi, ee_block);
4216 ex_cluster_end = EXT4_B2C(sbi, ee_block + ee_len - 1);
4217
4218
4219 rr_cluster_start = EXT4_B2C(sbi, map->m_lblk);
4220
4221 if ((rr_cluster_start == ex_cluster_end) ||
4222 (rr_cluster_start == ex_cluster_start)) {
4223 if (rr_cluster_start == ex_cluster_end)
4224 ee_start += ee_len - 1;
4225 map->m_pblk = EXT4_PBLK_CMASK(sbi, ee_start) + c_offset;
4226 map->m_len = min(map->m_len,
4227 (unsigned) sbi->s_cluster_ratio - c_offset);
4228
4229
4230
4231
4232
4233
4234
4235
4236
4237 if (map->m_lblk < ee_block)
4238 map->m_len = min(map->m_len, ee_block - map->m_lblk);
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249 if (map->m_lblk > ee_block) {
4250 ext4_lblk_t next = ext4_ext_next_allocated_block(path);
4251 map->m_len = min(map->m_len, next - map->m_lblk);
4252 }
4253
4254 trace_ext4_get_implied_cluster_alloc_exit(sb, map, 1);
4255 return 1;
4256 }
4257
4258 trace_ext4_get_implied_cluster_alloc_exit(sb, map, 0);
4259 return 0;
4260}
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
4282 struct ext4_map_blocks *map, int flags)
4283{
4284 struct ext4_ext_path *path = NULL;
4285 struct ext4_extent newex, *ex, *ex2;
4286 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
4287 ext4_fsblk_t newblock = 0;
4288 int free_on_err = 0, err = 0, depth, ret;
4289 unsigned int allocated = 0, offset = 0;
4290 unsigned int allocated_clusters = 0;
4291 struct ext4_allocation_request ar;
4292 ext4_lblk_t cluster_offset;
4293 bool map_from_cluster = false;
4294
4295 ext_debug("blocks %u/%u requested for inode %lu\n",
4296 map->m_lblk, map->m_len, inode->i_ino);
4297 trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
4298
4299
4300 path = ext4_find_extent(inode, map->m_lblk, NULL, 0);
4301 if (IS_ERR(path)) {
4302 err = PTR_ERR(path);
4303 path = NULL;
4304 goto out2;
4305 }
4306
4307 depth = ext_depth(inode);
4308
4309
4310
4311
4312
4313
4314 if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
4315 EXT4_ERROR_INODE(inode, "bad extent address "
4316 "lblock: %lu, depth: %d pblock %lld",
4317 (unsigned long) map->m_lblk, depth,
4318 path[depth].p_block);
4319 err = -EFSCORRUPTED;
4320 goto out2;
4321 }
4322
4323 ex = path[depth].p_ext;
4324 if (ex) {
4325 ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4326 ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4327 unsigned short ee_len;
4328
4329
4330
4331
4332
4333
4334 ee_len = ext4_ext_get_actual_len(ex);
4335
4336 trace_ext4_ext_show_extent(inode, ee_block, ee_start, ee_len);
4337
4338
4339 if (in_range(map->m_lblk, ee_block, ee_len)) {
4340 newblock = map->m_lblk - ee_block + ee_start;
4341
4342 allocated = ee_len - (map->m_lblk - ee_block);
4343 ext_debug("%u fit into %u:%d -> %llu\n", map->m_lblk,
4344 ee_block, ee_len, newblock);
4345
4346
4347
4348
4349
4350 if ((!ext4_ext_is_unwritten(ex)) &&
4351 (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN)) {
4352 allocated = convert_initialized_extent(
4353 handle, inode, map, &path,
4354 allocated);
4355 goto out2;
4356 } else if (!ext4_ext_is_unwritten(ex))
4357 goto out;
4358
4359 ret = ext4_ext_handle_unwritten_extents(
4360 handle, inode, map, &path, flags,
4361 allocated, newblock);
4362 if (ret < 0)
4363 err = ret;
4364 else
4365 allocated = ret;
4366 goto out2;
4367 }
4368 }
4369
4370
4371
4372
4373
4374 if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4375 ext4_lblk_t hole_start, hole_len;
4376
4377 hole_start = map->m_lblk;
4378 hole_len = ext4_ext_determine_hole(inode, path, &hole_start);
4379
4380
4381
4382
4383 ext4_ext_put_gap_in_cache(inode, hole_start, hole_len);
4384
4385
4386 if (hole_start != map->m_lblk)
4387 hole_len -= map->m_lblk - hole_start;
4388 map->m_pblk = 0;
4389 map->m_len = min_t(unsigned int, map->m_len, hole_len);
4390
4391 goto out2;
4392 }
4393
4394
4395
4396
4397 newex.ee_block = cpu_to_le32(map->m_lblk);
4398 cluster_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4399
4400
4401
4402
4403
4404 if (cluster_offset && ex &&
4405 get_implied_cluster_alloc(inode->i_sb, map, ex, path)) {
4406 ar.len = allocated = map->m_len;
4407 newblock = map->m_pblk;
4408 map_from_cluster = true;
4409 goto got_allocated_blocks;
4410 }
4411
4412
4413 ar.lleft = map->m_lblk;
4414 err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
4415 if (err)
4416 goto out2;
4417 ar.lright = map->m_lblk;
4418 ex2 = NULL;
4419 err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright, &ex2);
4420 if (err)
4421 goto out2;
4422
4423
4424
4425 if ((sbi->s_cluster_ratio > 1) && ex2 &&
4426 get_implied_cluster_alloc(inode->i_sb, map, ex2, path)) {
4427 ar.len = allocated = map->m_len;
4428 newblock = map->m_pblk;
4429 map_from_cluster = true;
4430 goto got_allocated_blocks;
4431 }
4432
4433
4434
4435
4436
4437
4438
4439 if (map->m_len > EXT_INIT_MAX_LEN &&
4440 !(flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4441 map->m_len = EXT_INIT_MAX_LEN;
4442 else if (map->m_len > EXT_UNWRITTEN_MAX_LEN &&
4443 (flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4444 map->m_len = EXT_UNWRITTEN_MAX_LEN;
4445
4446
4447 newex.ee_len = cpu_to_le16(map->m_len);
4448 err = ext4_ext_check_overlap(sbi, inode, &newex, path);
4449 if (err)
4450 allocated = ext4_ext_get_actual_len(&newex);
4451 else
4452 allocated = map->m_len;
4453
4454
4455 ar.inode = inode;
4456 ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
4457 ar.logical = map->m_lblk;
4458
4459
4460
4461
4462
4463
4464
4465
4466 offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4467 ar.len = EXT4_NUM_B2C(sbi, offset+allocated);
4468 ar.goal -= offset;
4469 ar.logical -= offset;
4470 if (S_ISREG(inode->i_mode))
4471 ar.flags = EXT4_MB_HINT_DATA;
4472 else
4473
4474 ar.flags = 0;
4475 if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
4476 ar.flags |= EXT4_MB_HINT_NOPREALLOC;
4477 if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
4478 ar.flags |= EXT4_MB_DELALLOC_RESERVED;
4479 if (flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
4480 ar.flags |= EXT4_MB_USE_RESERVED;
4481 newblock = ext4_mb_new_blocks(handle, &ar, &err);
4482 if (!newblock)
4483 goto out2;
4484 ext_debug("allocate new block: goal %llu, found %llu/%u\n",
4485 ar.goal, newblock, allocated);
4486 free_on_err = 1;
4487 allocated_clusters = ar.len;
4488 ar.len = EXT4_C2B(sbi, ar.len) - offset;
4489 if (ar.len > allocated)
4490 ar.len = allocated;
4491
4492got_allocated_blocks:
4493
4494 ext4_ext_store_pblock(&newex, newblock + offset);
4495 newex.ee_len = cpu_to_le16(ar.len);
4496
4497 if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT){
4498 ext4_ext_mark_unwritten(&newex);
4499 map->m_flags |= EXT4_MAP_UNWRITTEN;
4500 }
4501
4502 err = 0;
4503 if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0)
4504 err = check_eofblocks_fl(handle, inode, map->m_lblk,
4505 path, ar.len);
4506 if (!err)
4507 err = ext4_ext_insert_extent(handle, inode, &path,
4508 &newex, flags);
4509
4510 if (err && free_on_err) {
4511 int fb_flags = flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE ?
4512 EXT4_FREE_BLOCKS_NO_QUOT_UPDATE : 0;
4513
4514
4515
4516 ext4_discard_preallocations(inode);
4517 ext4_free_blocks(handle, inode, NULL, newblock,
4518 EXT4_C2B(sbi, allocated_clusters), fb_flags);
4519 goto out2;
4520 }
4521
4522
4523 newblock = ext4_ext_pblock(&newex);
4524 allocated = ext4_ext_get_actual_len(&newex);
4525 if (allocated > map->m_len)
4526 allocated = map->m_len;
4527 map->m_flags |= EXT4_MAP_NEW;
4528
4529
4530
4531
4532
4533 if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
4534 unsigned int reserved_clusters;
4535
4536
4537
4538 reserved_clusters = get_reserved_cluster_alloc(inode,
4539 map->m_lblk, allocated);
4540 if (!map_from_cluster) {
4541 BUG_ON(allocated_clusters < reserved_clusters);
4542 if (reserved_clusters < allocated_clusters) {
4543 struct ext4_inode_info *ei = EXT4_I(inode);
4544 int reservation = allocated_clusters -
4545 reserved_clusters;
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586 dquot_reserve_block(inode,
4587 EXT4_C2B(sbi, reservation));
4588 spin_lock(&ei->i_block_reservation_lock);
4589 ei->i_reserved_data_blocks += reservation;
4590 spin_unlock(&ei->i_block_reservation_lock);
4591 }
4592
4593
4594
4595
4596
4597
4598
4599 ext4_da_update_reserve_space(inode, allocated_clusters,
4600 1);
4601 }
4602 }
4603
4604
4605
4606
4607
4608 if ((flags & EXT4_GET_BLOCKS_UNWRIT_EXT) == 0)
4609 ext4_update_inode_fsync_trans(handle, inode, 1);
4610 else
4611 ext4_update_inode_fsync_trans(handle, inode, 0);
4612out:
4613 if (allocated > map->m_len)
4614 allocated = map->m_len;
4615 ext4_ext_show_leaf(inode, path);
4616 map->m_flags |= EXT4_MAP_MAPPED;
4617 map->m_pblk = newblock;
4618 map->m_len = allocated;
4619out2:
4620 ext4_ext_drop_refs(path);
4621 kfree(path);
4622
4623 trace_ext4_ext_map_blocks_exit(inode, flags, map,
4624 err ? err : allocated);
4625 return err ? err : allocated;
4626}
4627
4628void ext4_ext_truncate(handle_t *handle, struct inode *inode)
4629{
4630 struct super_block *sb = inode->i_sb;
4631 ext4_lblk_t last_block;
4632 int err = 0;
4633
4634
4635
4636
4637
4638
4639
4640
4641 EXT4_I(inode)->i_disksize = inode->i_size;
4642 ext4_mark_inode_dirty(handle, inode);
4643
4644 last_block = (inode->i_size + sb->s_blocksize - 1)
4645 >> EXT4_BLOCK_SIZE_BITS(sb);
4646retry:
4647 err = ext4_es_remove_extent(inode, last_block,
4648 EXT_MAX_BLOCKS - last_block);
4649 if (err == -ENOMEM) {
4650 cond_resched();
4651 congestion_wait(BLK_RW_ASYNC, HZ/50);
4652 goto retry;
4653 }
4654 if (err) {
4655 ext4_std_error(inode->i_sb, err);
4656 return;
4657 }
4658 err = ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
4659 ext4_std_error(inode->i_sb, err);
4660}
4661
4662static int ext4_alloc_file_blocks(struct file *file, ext4_lblk_t offset,
4663 ext4_lblk_t len, loff_t new_size,
4664 int flags, int mode)
4665{
4666 struct inode *inode = file_inode(file);
4667 handle_t *handle;
4668 int ret = 0;
4669 int ret2 = 0;
4670 int retries = 0;
4671 int depth = 0;
4672 struct ext4_map_blocks map;
4673 unsigned int credits;
4674 loff_t epos;
4675
4676 map.m_lblk = offset;
4677 map.m_len = len;
4678
4679
4680
4681
4682
4683 if (len <= EXT_UNWRITTEN_MAX_LEN)
4684 flags |= EXT4_GET_BLOCKS_NO_NORMALIZE;
4685
4686
4687
4688
4689 credits = ext4_chunk_trans_blocks(inode, len);
4690
4691
4692
4693 if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
4694 depth = ext_depth(inode);
4695 else
4696 depth = -1;
4697
4698retry:
4699 while (ret >= 0 && len) {
4700
4701
4702
4703 if (depth >= 0 && depth != ext_depth(inode)) {
4704 credits = ext4_chunk_trans_blocks(inode, len);
4705 depth = ext_depth(inode);
4706 }
4707
4708 handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4709 credits);
4710 if (IS_ERR(handle)) {
4711 ret = PTR_ERR(handle);
4712 break;
4713 }
4714 ret = ext4_map_blocks(handle, inode, &map, flags);
4715 if (ret <= 0) {
4716 ext4_debug("inode #%lu: block %u: len %u: "
4717 "ext4_ext_map_blocks returned %d",
4718 inode->i_ino, map.m_lblk,
4719 map.m_len, ret);
4720 ext4_mark_inode_dirty(handle, inode);
4721 ret2 = ext4_journal_stop(handle);
4722 break;
4723 }
4724 map.m_lblk += ret;
4725 map.m_len = len = len - ret;
4726 epos = (loff_t)map.m_lblk << inode->i_blkbits;
4727 inode->i_ctime = ext4_current_time(inode);
4728 if (new_size) {
4729 if (epos > new_size)
4730 epos = new_size;
4731 if (ext4_update_inode_size(inode, epos) & 0x1)
4732 inode->i_mtime = inode->i_ctime;
4733 } else {
4734 if (epos > inode->i_size)
4735 ext4_set_inode_flag(inode,
4736 EXT4_INODE_EOFBLOCKS);
4737 }
4738 ext4_mark_inode_dirty(handle, inode);
4739 ret2 = ext4_journal_stop(handle);
4740 if (ret2)
4741 break;
4742 }
4743 if (ret == -ENOSPC &&
4744 ext4_should_retry_alloc(inode->i_sb, &retries)) {
4745 ret = 0;
4746 goto retry;
4747 }
4748
4749 return ret > 0 ? ret2 : ret;
4750}
4751
4752static long ext4_zero_range(struct file *file, loff_t offset,
4753 loff_t len, int mode)
4754{
4755 struct inode *inode = file_inode(file);
4756 handle_t *handle = NULL;
4757 unsigned int max_blocks;
4758 loff_t new_size = 0;
4759 int ret = 0;
4760 int flags;
4761 int credits;
4762 int partial_begin, partial_end;
4763 loff_t start, end;
4764 ext4_lblk_t lblk;
4765 unsigned int blkbits = inode->i_blkbits;
4766
4767 trace_ext4_zero_range(inode, offset, len, mode);
4768
4769 if (!S_ISREG(inode->i_mode))
4770 return -EINVAL;
4771
4772
4773 if (ext4_should_journal_data(inode)) {
4774 ret = ext4_force_commit(inode->i_sb);
4775 if (ret)
4776 return ret;
4777 }
4778
4779
4780
4781
4782
4783
4784
4785 start = round_up(offset, 1 << blkbits);
4786 end = round_down((offset + len), 1 << blkbits);
4787
4788 if (start < offset || end > offset + len)
4789 return -EINVAL;
4790 partial_begin = offset & ((1 << blkbits) - 1);
4791 partial_end = (offset + len) & ((1 << blkbits) - 1);
4792
4793 lblk = start >> blkbits;
4794 max_blocks = (end >> blkbits);
4795 if (max_blocks < lblk)
4796 max_blocks = 0;
4797 else
4798 max_blocks -= lblk;
4799
4800 inode_lock(inode);
4801
4802
4803
4804
4805 if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4806 ret = -EOPNOTSUPP;
4807 goto out_mutex;
4808 }
4809
4810 if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4811 offset + len > i_size_read(inode)) {
4812 new_size = offset + len;
4813 ret = inode_newsize_ok(inode, new_size);
4814 if (ret)
4815 goto out_mutex;
4816 }
4817
4818 flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4819 if (mode & FALLOC_FL_KEEP_SIZE)
4820 flags |= EXT4_GET_BLOCKS_KEEP_SIZE;
4821
4822
4823 ext4_inode_block_unlocked_dio(inode);
4824 inode_dio_wait(inode);
4825
4826
4827 if (partial_begin || partial_end) {
4828 ret = ext4_alloc_file_blocks(file,
4829 round_down(offset, 1 << blkbits) >> blkbits,
4830 (round_up((offset + len), 1 << blkbits) -
4831 round_down(offset, 1 << blkbits)) >> blkbits,
4832 new_size, flags, mode);
4833 if (ret)
4834 goto out_dio;
4835
4836 }
4837
4838
4839 if (max_blocks > 0) {
4840 flags |= (EXT4_GET_BLOCKS_CONVERT_UNWRITTEN |
4841 EXT4_EX_NOCACHE);
4842
4843
4844
4845
4846
4847 down_write(&EXT4_I(inode)->i_mmap_sem);
4848 ret = ext4_update_disksize_before_punch(inode, offset, len);
4849 if (ret) {
4850 up_write(&EXT4_I(inode)->i_mmap_sem);
4851 goto out_dio;
4852 }
4853
4854 truncate_pagecache_range(inode, start, end - 1);
4855 inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
4856
4857 ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size,
4858 flags, mode);
4859 up_write(&EXT4_I(inode)->i_mmap_sem);
4860 if (ret)
4861 goto out_dio;
4862 }
4863 if (!partial_begin && !partial_end)
4864 goto out_dio;
4865
4866
4867
4868
4869
4870 credits = (2 * ext4_ext_index_trans_blocks(inode, 2)) + 1;
4871 if (ext4_should_journal_data(inode))
4872 credits += 2;
4873 handle = ext4_journal_start(inode, EXT4_HT_MISC, credits);
4874 if (IS_ERR(handle)) {
4875 ret = PTR_ERR(handle);
4876 ext4_std_error(inode->i_sb, ret);
4877 goto out_dio;
4878 }
4879
4880 inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
4881 if (new_size) {
4882 ext4_update_inode_size(inode, new_size);
4883 } else {
4884
4885
4886
4887
4888 if ((offset + len) > i_size_read(inode))
4889 ext4_set_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
4890 }
4891 ext4_mark_inode_dirty(handle, inode);
4892
4893
4894 ret = ext4_zero_partial_blocks(handle, inode, offset, len);
4895
4896 if (file->f_flags & O_SYNC)
4897 ext4_handle_sync(handle);
4898
4899 ext4_journal_stop(handle);
4900out_dio:
4901 ext4_inode_resume_unlocked_dio(inode);
4902out_mutex:
4903 inode_unlock(inode);
4904 return ret;
4905}
4906
4907
4908
4909
4910
4911
4912
4913
4914long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
4915{
4916 struct inode *inode = file_inode(file);
4917 loff_t new_size = 0;
4918 unsigned int max_blocks;
4919 int ret = 0;
4920 int flags;
4921 ext4_lblk_t lblk;
4922 unsigned int blkbits = inode->i_blkbits;
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934 if (ext4_encrypted_inode(inode) &&
4935 (mode & (FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_INSERT_RANGE |
4936 FALLOC_FL_ZERO_RANGE)))
4937 return -EOPNOTSUPP;
4938
4939
4940 if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE |
4941 FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_ZERO_RANGE |
4942 FALLOC_FL_INSERT_RANGE))
4943 return -EOPNOTSUPP;
4944
4945 if (mode & FALLOC_FL_PUNCH_HOLE)
4946 return ext4_punch_hole(inode, offset, len);
4947
4948 ret = ext4_convert_inline_data(inode);
4949 if (ret)
4950 return ret;
4951
4952 if (mode & FALLOC_FL_COLLAPSE_RANGE)
4953 return ext4_collapse_range(inode, offset, len);
4954
4955 if (mode & FALLOC_FL_INSERT_RANGE)
4956 return ext4_insert_range(inode, offset, len);
4957
4958 if (mode & FALLOC_FL_ZERO_RANGE)
4959 return ext4_zero_range(file, offset, len, mode);
4960
4961 trace_ext4_fallocate_enter(inode, offset, len, mode);
4962 lblk = offset >> blkbits;
4963
4964
4965
4966
4967 max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
4968 - lblk;
4969
4970 flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4971 if (mode & FALLOC_FL_KEEP_SIZE)
4972 flags |= EXT4_GET_BLOCKS_KEEP_SIZE;
4973
4974 inode_lock(inode);
4975
4976
4977
4978
4979 if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4980 ret = -EOPNOTSUPP;
4981 goto out;
4982 }
4983
4984 if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4985 offset + len > i_size_read(inode)) {
4986 new_size = offset + len;
4987 ret = inode_newsize_ok(inode, new_size);
4988 if (ret)
4989 goto out;
4990 }
4991
4992
4993 ext4_inode_block_unlocked_dio(inode);
4994 inode_dio_wait(inode);
4995
4996 ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size,
4997 flags, mode);
4998 ext4_inode_resume_unlocked_dio(inode);
4999 if (ret)
5000 goto out;
5001
5002 if (file->f_flags & O_SYNC && EXT4_SB(inode->i_sb)->s_journal) {
5003 ret = jbd2_complete_transaction(EXT4_SB(inode->i_sb)->s_journal,
5004 EXT4_I(inode)->i_sync_tid);
5005 }
5006out:
5007 inode_unlock(inode);
5008 trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
5009 return ret;
5010}
5011
5012
5013
5014
5015
5016
5017
5018
5019
5020
5021
5022int ext4_convert_unwritten_extents(handle_t *handle, struct inode *inode,
5023 loff_t offset, ssize_t len)
5024{
5025 unsigned int max_blocks;
5026 int ret = 0;
5027 int ret2 = 0;
5028 struct ext4_map_blocks map;
5029 unsigned int credits, blkbits = inode->i_blkbits;
5030
5031 map.m_lblk = offset >> blkbits;
5032
5033
5034
5035
5036 max_blocks = ((EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits) -
5037 map.m_lblk);
5038
5039
5040
5041
5042
5043 if (handle) {
5044 handle = ext4_journal_start_reserved(handle,
5045 EXT4_HT_EXT_CONVERT);
5046 if (IS_ERR(handle))
5047 return PTR_ERR(handle);
5048 credits = 0;
5049 } else {
5050
5051
5052
5053 credits = ext4_chunk_trans_blocks(inode, max_blocks);
5054 }
5055 while (ret >= 0 && ret < max_blocks) {
5056 map.m_lblk += ret;
5057 map.m_len = (max_blocks -= ret);
5058 if (credits) {
5059 handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
5060 credits);
5061 if (IS_ERR(handle)) {
5062 ret = PTR_ERR(handle);
5063 break;
5064 }
5065 }
5066 ret = ext4_map_blocks(handle, inode, &map,
5067 EXT4_GET_BLOCKS_IO_CONVERT_EXT);
5068 if (ret <= 0)
5069 ext4_warning(inode->i_sb,
5070 "inode #%lu: block %u: len %u: "
5071 "ext4_ext_map_blocks returned %d",
5072 inode->i_ino, map.m_lblk,
5073 map.m_len, ret);
5074 ext4_mark_inode_dirty(handle, inode);
5075 if (credits)
5076 ret2 = ext4_journal_stop(handle);
5077 if (ret <= 0 || ret2)
5078 break;
5079 }
5080 if (!credits)
5081 ret2 = ext4_journal_stop(handle);
5082 return ret > 0 ? ret2 : ret;
5083}
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094static int ext4_find_delayed_extent(struct inode *inode,
5095 struct extent_status *newes)
5096{
5097 struct extent_status es;
5098 ext4_lblk_t block, next_del;
5099
5100 if (newes->es_pblk == 0) {
5101 ext4_es_find_delayed_extent_range(inode, newes->es_lblk,
5102 newes->es_lblk + newes->es_len - 1, &es);
5103
5104
5105
5106
5107
5108 if (es.es_len == 0)
5109
5110 return 0;
5111
5112 if (es.es_lblk > newes->es_lblk) {
5113
5114 newes->es_len = min(es.es_lblk - newes->es_lblk,
5115 newes->es_len);
5116 return 0;
5117 }
5118
5119 newes->es_len = es.es_lblk + es.es_len - newes->es_lblk;
5120 }
5121
5122 block = newes->es_lblk + newes->es_len;
5123 ext4_es_find_delayed_extent_range(inode, block, EXT_MAX_BLOCKS, &es);
5124 if (es.es_len == 0)
5125 next_del = EXT_MAX_BLOCKS;
5126 else
5127 next_del = es.es_lblk;
5128
5129 return next_del;
5130}
5131
5132#define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
5133
5134static int ext4_xattr_fiemap(struct inode *inode,
5135 struct fiemap_extent_info *fieinfo)
5136{
5137 __u64 physical = 0;
5138 __u64 length;
5139 __u32 flags = FIEMAP_EXTENT_LAST;
5140 int blockbits = inode->i_sb->s_blocksize_bits;
5141 int error = 0;
5142
5143
5144 if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
5145 struct ext4_iloc iloc;
5146 int offset;
5147
5148 error = ext4_get_inode_loc(inode, &iloc);
5149 if (error)
5150 return error;
5151 physical = (__u64)iloc.bh->b_blocknr << blockbits;
5152 offset = EXT4_GOOD_OLD_INODE_SIZE +
5153 EXT4_I(inode)->i_extra_isize;
5154 physical += offset;
5155 length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
5156 flags |= FIEMAP_EXTENT_DATA_INLINE;
5157 brelse(iloc.bh);
5158 } else {
5159 physical = (__u64)EXT4_I(inode)->i_file_acl << blockbits;
5160 length = inode->i_sb->s_blocksize;
5161 }
5162
5163 if (physical)
5164 error = fiemap_fill_next_extent(fieinfo, 0, physical,
5165 length, flags);
5166 return (error < 0 ? error : 0);
5167}
5168
5169int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
5170 __u64 start, __u64 len)
5171{
5172 ext4_lblk_t start_blk;
5173 int error = 0;
5174
5175 if (ext4_has_inline_data(inode)) {
5176 int has_inline = 1;
5177
5178 error = ext4_inline_data_fiemap(inode, fieinfo, &has_inline,
5179 start, len);
5180
5181 if (has_inline)
5182 return error;
5183 }
5184
5185 if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
5186 error = ext4_ext_precache(inode);
5187 if (error)
5188 return error;
5189 }
5190
5191
5192 if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
5193 return generic_block_fiemap(inode, fieinfo, start, len,
5194 ext4_get_block);
5195
5196 if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
5197 return -EBADR;
5198
5199 if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
5200 error = ext4_xattr_fiemap(inode, fieinfo);
5201 } else {
5202 ext4_lblk_t len_blks;
5203 __u64 last_blk;
5204
5205 start_blk = start >> inode->i_sb->s_blocksize_bits;
5206 last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
5207 if (last_blk >= EXT_MAX_BLOCKS)
5208 last_blk = EXT_MAX_BLOCKS-1;
5209 len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
5210
5211
5212
5213
5214
5215 error = ext4_fill_fiemap_extents(inode, start_blk,
5216 len_blks, fieinfo);
5217 }
5218 return error;
5219}
5220
5221
5222
5223
5224
5225
5226
5227static int
5228ext4_access_path(handle_t *handle, struct inode *inode,
5229 struct ext4_ext_path *path)
5230{
5231 int credits, err;
5232
5233 if (!ext4_handle_valid(handle))
5234 return 0;
5235
5236
5237
5238
5239
5240
5241
5242 if (handle->h_buffer_credits < 7) {
5243 credits = ext4_writepage_trans_blocks(inode);
5244 err = ext4_ext_truncate_extend_restart(handle, inode, credits);
5245
5246 if (err && err != -EAGAIN)
5247 return err;
5248 }
5249
5250 err = ext4_ext_get_access(handle, inode, path);
5251 return err;
5252}
5253
5254
5255
5256
5257
5258
5259
5260static int
5261ext4_ext_shift_path_extents(struct ext4_ext_path *path, ext4_lblk_t shift,
5262 struct inode *inode, handle_t *handle,
5263 enum SHIFT_DIRECTION SHIFT)
5264{
5265 int depth, err = 0;
5266 struct ext4_extent *ex_start, *ex_last;
5267 bool update = 0;
5268 depth = path->p_depth;
5269
5270 while (depth >= 0) {
5271 if (depth == path->p_depth) {
5272 ex_start = path[depth].p_ext;
5273 if (!ex_start)
5274 return -EFSCORRUPTED;
5275
5276 ex_last = EXT_LAST_EXTENT(path[depth].p_hdr);
5277
5278 err = ext4_access_path(handle, inode, path + depth);
5279 if (err)
5280 goto out;
5281
5282 if (ex_start == EXT_FIRST_EXTENT(path[depth].p_hdr))
5283 update = 1;
5284
5285 while (ex_start <= ex_last) {
5286 if (SHIFT == SHIFT_LEFT) {
5287 le32_add_cpu(&ex_start->ee_block,
5288 -shift);
5289
5290 if ((ex_start >
5291 EXT_FIRST_EXTENT(path[depth].p_hdr))
5292 &&
5293 ext4_ext_try_to_merge_right(inode,
5294 path, ex_start - 1))
5295 ex_last--;
5296 else
5297 ex_start++;
5298 } else {
5299 le32_add_cpu(&ex_last->ee_block, shift);
5300 ext4_ext_try_to_merge_right(inode, path,
5301 ex_last);
5302 ex_last--;
5303 }
5304 }
5305 err = ext4_ext_dirty(handle, inode, path + depth);
5306 if (err)
5307 goto out;
5308
5309 if (--depth < 0 || !update)
5310 break;
5311 }
5312
5313
5314 err = ext4_access_path(handle, inode, path + depth);
5315 if (err)
5316 goto out;
5317
5318 if (SHIFT == SHIFT_LEFT)
5319 le32_add_cpu(&path[depth].p_idx->ei_block, -shift);
5320 else
5321 le32_add_cpu(&path[depth].p_idx->ei_block, shift);
5322 err = ext4_ext_dirty(handle, inode, path + depth);
5323 if (err)
5324 goto out;
5325
5326
5327 if (path[depth].p_idx != EXT_FIRST_INDEX(path[depth].p_hdr))
5328 break;
5329
5330 depth--;
5331 }
5332
5333out:
5334 return err;
5335}
5336
5337
5338
5339
5340
5341
5342
5343
5344static int
5345ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
5346 ext4_lblk_t start, ext4_lblk_t shift,
5347 enum SHIFT_DIRECTION SHIFT)
5348{
5349 struct ext4_ext_path *path;
5350 int ret = 0, depth;
5351 struct ext4_extent *extent;
5352 ext4_lblk_t stop, *iterator, ex_start, ex_end;
5353
5354
5355 path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL, 0);
5356 if (IS_ERR(path))
5357 return PTR_ERR(path);
5358
5359 depth = path->p_depth;
5360 extent = path[depth].p_ext;
5361 if (!extent)
5362 goto out;
5363
5364 stop = le32_to_cpu(extent->ee_block) +
5365 ext4_ext_get_actual_len(extent);
5366
5367
5368
5369
5370
5371 if (SHIFT == SHIFT_LEFT) {
5372 path = ext4_find_extent(inode, start - 1, &path, 0);
5373 if (IS_ERR(path))
5374 return PTR_ERR(path);
5375 depth = path->p_depth;
5376 extent = path[depth].p_ext;
5377 if (extent) {
5378 ex_start = le32_to_cpu(extent->ee_block);
5379 ex_end = le32_to_cpu(extent->ee_block) +
5380 ext4_ext_get_actual_len(extent);
5381 } else {
5382 ex_start = 0;
5383 ex_end = 0;
5384 }
5385
5386 if ((start == ex_start && shift > ex_start) ||
5387 (shift > start - ex_end)) {
5388 ext4_ext_drop_refs(path);
5389 kfree(path);
5390 return -EINVAL;
5391 }
5392 }
5393
5394
5395
5396
5397
5398
5399 if (SHIFT == SHIFT_LEFT)
5400 iterator = &start;
5401 else
5402 iterator = &stop;
5403
5404
5405 while (start < stop) {
5406 path = ext4_find_extent(inode, *iterator, &path, 0);
5407 if (IS_ERR(path))
5408 return PTR_ERR(path);
5409 depth = path->p_depth;
5410 extent = path[depth].p_ext;
5411 if (!extent) {
5412 EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
5413 (unsigned long) *iterator);
5414 return -EFSCORRUPTED;
5415 }
5416 if (SHIFT == SHIFT_LEFT && *iterator >
5417 le32_to_cpu(extent->ee_block)) {
5418
5419 if (extent < EXT_LAST_EXTENT(path[depth].p_hdr)) {
5420 path[depth].p_ext++;
5421 } else {
5422 *iterator = ext4_ext_next_allocated_block(path);
5423 continue;
5424 }
5425 }
5426
5427 if (SHIFT == SHIFT_LEFT) {
5428 extent = EXT_LAST_EXTENT(path[depth].p_hdr);
5429 *iterator = le32_to_cpu(extent->ee_block) +
5430 ext4_ext_get_actual_len(extent);
5431 } else {
5432 extent = EXT_FIRST_EXTENT(path[depth].p_hdr);
5433 *iterator = le32_to_cpu(extent->ee_block) > 0 ?
5434 le32_to_cpu(extent->ee_block) - 1 : 0;
5435
5436 while (le32_to_cpu(extent->ee_block) < start)
5437 extent++;
5438 path[depth].p_ext = extent;
5439 }
5440 ret = ext4_ext_shift_path_extents(path, shift, inode,
5441 handle, SHIFT);
5442 if (ret)
5443 break;
5444 }
5445out:
5446 ext4_ext_drop_refs(path);
5447 kfree(path);
5448 return ret;
5449}
5450
5451
5452
5453
5454
5455
5456int ext4_collapse_range(struct inode *inode, loff_t offset, loff_t len)
5457{
5458 struct super_block *sb = inode->i_sb;
5459 ext4_lblk_t punch_start, punch_stop;
5460 handle_t *handle;
5461 unsigned int credits;
5462 loff_t new_size, ioffset;
5463 int ret;
5464
5465
5466
5467
5468
5469
5470 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5471 return -EOPNOTSUPP;
5472
5473
5474 if (offset & (EXT4_CLUSTER_SIZE(sb) - 1) ||
5475 len & (EXT4_CLUSTER_SIZE(sb) - 1))
5476 return -EINVAL;
5477
5478 if (!S_ISREG(inode->i_mode))
5479 return -EINVAL;
5480
5481 trace_ext4_collapse_range(inode, offset, len);
5482
5483 punch_start = offset >> EXT4_BLOCK_SIZE_BITS(sb);
5484 punch_stop = (offset + len) >> EXT4_BLOCK_SIZE_BITS(sb);
5485
5486
5487 if (ext4_should_journal_data(inode)) {
5488 ret = ext4_force_commit(inode->i_sb);
5489 if (ret)
5490 return ret;
5491 }
5492
5493 inode_lock(inode);
5494
5495
5496
5497
5498 if (offset + len >= i_size_read(inode)) {
5499 ret = -EINVAL;
5500 goto out_mutex;
5501 }
5502
5503
5504 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
5505 ret = -EOPNOTSUPP;
5506 goto out_mutex;
5507 }
5508
5509
5510 ext4_inode_block_unlocked_dio(inode);
5511 inode_dio_wait(inode);
5512
5513
5514
5515
5516
5517 down_write(&EXT4_I(inode)->i_mmap_sem);
5518
5519
5520
5521
5522 ioffset = round_down(offset, PAGE_SIZE);
5523
5524
5525
5526
5527 ret = filemap_write_and_wait_range(inode->i_mapping, ioffset, offset);
5528 if (ret)
5529 goto out_mmap;
5530
5531
5532
5533
5534
5535 ret = filemap_write_and_wait_range(inode->i_mapping, offset + len,
5536 LLONG_MAX);
5537 if (ret)
5538 goto out_mmap;
5539 truncate_pagecache(inode, ioffset);
5540
5541 credits = ext4_writepage_trans_blocks(inode);
5542 handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5543 if (IS_ERR(handle)) {
5544 ret = PTR_ERR(handle);
5545 goto out_mmap;
5546 }
5547
5548 down_write(&EXT4_I(inode)->i_data_sem);
5549 ext4_discard_preallocations(inode);
5550
5551 ret = ext4_es_remove_extent(inode, punch_start,
5552 EXT_MAX_BLOCKS - punch_start);
5553 if (ret) {
5554 up_write(&EXT4_I(inode)->i_data_sem);
5555 goto out_stop;
5556 }
5557
5558 ret = ext4_ext_remove_space(inode, punch_start, punch_stop - 1);
5559 if (ret) {
5560 up_write(&EXT4_I(inode)->i_data_sem);
5561 goto out_stop;
5562 }
5563 ext4_discard_preallocations(inode);
5564
5565 ret = ext4_ext_shift_extents(inode, handle, punch_stop,
5566 punch_stop - punch_start, SHIFT_LEFT);
5567 if (ret) {
5568 up_write(&EXT4_I(inode)->i_data_sem);
5569 goto out_stop;
5570 }
5571
5572 new_size = i_size_read(inode) - len;
5573 i_size_write(inode, new_size);
5574 EXT4_I(inode)->i_disksize = new_size;
5575
5576 up_write(&EXT4_I(inode)->i_data_sem);
5577 if (IS_SYNC(inode))
5578 ext4_handle_sync(handle);
5579 inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
5580 ext4_mark_inode_dirty(handle, inode);
5581
5582out_stop:
5583 ext4_journal_stop(handle);
5584out_mmap:
5585 up_write(&EXT4_I(inode)->i_mmap_sem);
5586 ext4_inode_resume_unlocked_dio(inode);
5587out_mutex:
5588 inode_unlock(inode);
5589 return ret;
5590}
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600int ext4_insert_range(struct inode *inode, loff_t offset, loff_t len)
5601{
5602 struct super_block *sb = inode->i_sb;
5603 handle_t *handle;
5604 struct ext4_ext_path *path;
5605 struct ext4_extent *extent;
5606 ext4_lblk_t offset_lblk, len_lblk, ee_start_lblk = 0;
5607 unsigned int credits, ee_len;
5608 int ret = 0, depth, split_flag = 0;
5609 loff_t ioffset;
5610
5611
5612
5613
5614
5615
5616 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5617 return -EOPNOTSUPP;
5618
5619
5620 if (offset & (EXT4_CLUSTER_SIZE(sb) - 1) ||
5621 len & (EXT4_CLUSTER_SIZE(sb) - 1))
5622 return -EINVAL;
5623
5624 if (!S_ISREG(inode->i_mode))
5625 return -EOPNOTSUPP;
5626
5627 trace_ext4_insert_range(inode, offset, len);
5628
5629 offset_lblk = offset >> EXT4_BLOCK_SIZE_BITS(sb);
5630 len_lblk = len >> EXT4_BLOCK_SIZE_BITS(sb);
5631
5632
5633 if (ext4_should_journal_data(inode)) {
5634 ret = ext4_force_commit(inode->i_sb);
5635 if (ret)
5636 return ret;
5637 }
5638
5639 inode_lock(inode);
5640
5641 if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
5642 ret = -EOPNOTSUPP;
5643 goto out_mutex;
5644 }
5645
5646
5647 if (inode->i_size + len > inode->i_sb->s_maxbytes) {
5648 ret = -EFBIG;
5649 goto out_mutex;
5650 }
5651
5652
5653 if (offset >= i_size_read(inode)) {
5654 ret = -EINVAL;
5655 goto out_mutex;
5656 }
5657
5658
5659 ext4_inode_block_unlocked_dio(inode);
5660 inode_dio_wait(inode);
5661
5662
5663
5664
5665
5666 down_write(&EXT4_I(inode)->i_mmap_sem);
5667
5668
5669
5670
5671 ioffset = round_down(offset, PAGE_SIZE);
5672
5673 ret = filemap_write_and_wait_range(inode->i_mapping, ioffset,
5674 LLONG_MAX);
5675 if (ret)
5676 goto out_mmap;
5677 truncate_pagecache(inode, ioffset);
5678
5679 credits = ext4_writepage_trans_blocks(inode);
5680 handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5681 if (IS_ERR(handle)) {
5682 ret = PTR_ERR(handle);
5683 goto out_mmap;
5684 }
5685
5686
5687 inode->i_size += len;
5688 EXT4_I(inode)->i_disksize += len;
5689 inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
5690 ret = ext4_mark_inode_dirty(handle, inode);
5691 if (ret)
5692 goto out_stop;
5693
5694 down_write(&EXT4_I(inode)->i_data_sem);
5695 ext4_discard_preallocations(inode);
5696
5697 path = ext4_find_extent(inode, offset_lblk, NULL, 0);
5698 if (IS_ERR(path)) {
5699 up_write(&EXT4_I(inode)->i_data_sem);
5700 goto out_stop;
5701 }
5702
5703 depth = ext_depth(inode);
5704 extent = path[depth].p_ext;
5705 if (extent) {
5706 ee_start_lblk = le32_to_cpu(extent->ee_block);
5707 ee_len = ext4_ext_get_actual_len(extent);
5708
5709
5710
5711
5712
5713 if ((offset_lblk > ee_start_lblk) &&
5714 (offset_lblk < (ee_start_lblk + ee_len))) {
5715 if (ext4_ext_is_unwritten(extent))
5716 split_flag = EXT4_EXT_MARK_UNWRIT1 |
5717 EXT4_EXT_MARK_UNWRIT2;
5718 ret = ext4_split_extent_at(handle, inode, &path,
5719 offset_lblk, split_flag,
5720 EXT4_EX_NOCACHE |
5721 EXT4_GET_BLOCKS_PRE_IO |
5722 EXT4_GET_BLOCKS_METADATA_NOFAIL);
5723 }
5724
5725 ext4_ext_drop_refs(path);
5726 kfree(path);
5727 if (ret < 0) {
5728 up_write(&EXT4_I(inode)->i_data_sem);
5729 goto out_stop;
5730 }
5731 }
5732
5733 ret = ext4_es_remove_extent(inode, offset_lblk,
5734 EXT_MAX_BLOCKS - offset_lblk);
5735 if (ret) {
5736 up_write(&EXT4_I(inode)->i_data_sem);
5737 goto out_stop;
5738 }
5739
5740
5741
5742
5743
5744 ret = ext4_ext_shift_extents(inode, handle,
5745 ee_start_lblk > offset_lblk ? ee_start_lblk : offset_lblk,
5746 len_lblk, SHIFT_RIGHT);
5747
5748 up_write(&EXT4_I(inode)->i_data_sem);
5749 if (IS_SYNC(inode))
5750 ext4_handle_sync(handle);
5751
5752out_stop:
5753 ext4_journal_stop(handle);
5754out_mmap:
5755 up_write(&EXT4_I(inode)->i_mmap_sem);
5756 ext4_inode_resume_unlocked_dio(inode);
5757out_mutex:
5758 inode_unlock(inode);
5759 return ret;
5760}
5761
5762
5763
5764
5765
5766
5767
5768
5769
5770
5771
5772
5773
5774
5775
5776
5777
5778
5779
5780
5781
5782int
5783ext4_swap_extents(handle_t *handle, struct inode *inode1,
5784 struct inode *inode2, ext4_lblk_t lblk1, ext4_lblk_t lblk2,
5785 ext4_lblk_t count, int unwritten, int *erp)
5786{
5787 struct ext4_ext_path *path1 = NULL;
5788 struct ext4_ext_path *path2 = NULL;
5789 int replaced_count = 0;
5790
5791 BUG_ON(!rwsem_is_locked(&EXT4_I(inode1)->i_data_sem));
5792 BUG_ON(!rwsem_is_locked(&EXT4_I(inode2)->i_data_sem));
5793 BUG_ON(!inode_is_locked(inode1));
5794 BUG_ON(!inode_is_locked(inode2));
5795
5796 *erp = ext4_es_remove_extent(inode1, lblk1, count);
5797 if (unlikely(*erp))
5798 return 0;
5799 *erp = ext4_es_remove_extent(inode2, lblk2, count);
5800 if (unlikely(*erp))
5801 return 0;
5802
5803 while (count) {
5804 struct ext4_extent *ex1, *ex2, tmp_ex;
5805 ext4_lblk_t e1_blk, e2_blk;
5806 int e1_len, e2_len, len;
5807 int split = 0;
5808
5809 path1 = ext4_find_extent(inode1, lblk1, NULL, EXT4_EX_NOCACHE);
5810 if (IS_ERR(path1)) {
5811 *erp = PTR_ERR(path1);
5812 path1 = NULL;
5813 finish:
5814 count = 0;
5815 goto repeat;
5816 }
5817 path2 = ext4_find_extent(inode2, lblk2, NULL, EXT4_EX_NOCACHE);
5818 if (IS_ERR(path2)) {
5819 *erp = PTR_ERR(path2);
5820 path2 = NULL;
5821 goto finish;
5822 }
5823 ex1 = path1[path1->p_depth].p_ext;
5824 ex2 = path2[path2->p_depth].p_ext;
5825
5826 if (unlikely(!ex2 || !ex1))
5827 goto finish;
5828
5829 e1_blk = le32_to_cpu(ex1->ee_block);
5830 e2_blk = le32_to_cpu(ex2->ee_block);
5831 e1_len = ext4_ext_get_actual_len(ex1);
5832 e2_len = ext4_ext_get_actual_len(ex2);
5833
5834
5835 if (!in_range(lblk1, e1_blk, e1_len) ||
5836 !in_range(lblk2, e2_blk, e2_len)) {
5837 ext4_lblk_t next1, next2;
5838
5839
5840 next1 = ext4_ext_next_allocated_block(path1);
5841 next2 = ext4_ext_next_allocated_block(path2);
5842
5843 if (e1_blk > lblk1)
5844 next1 = e1_blk;
5845 if (e2_blk > lblk2)
5846 next2 = e1_blk;
5847
5848 if (next1 == EXT_MAX_BLOCKS || next2 == EXT_MAX_BLOCKS)
5849 goto finish;
5850
5851 len = next1 - lblk1;
5852 if (len < next2 - lblk2)
5853 len = next2 - lblk2;
5854 if (len > count)
5855 len = count;
5856 lblk1 += len;
5857 lblk2 += len;
5858 count -= len;
5859 goto repeat;
5860 }
5861
5862
5863 if (e1_blk < lblk1) {
5864 split = 1;
5865 *erp = ext4_force_split_extent_at(handle, inode1,
5866 &path1, lblk1, 0);
5867 if (unlikely(*erp))
5868 goto finish;
5869 }
5870 if (e2_blk < lblk2) {
5871 split = 1;
5872 *erp = ext4_force_split_extent_at(handle, inode2,
5873 &path2, lblk2, 0);
5874 if (unlikely(*erp))
5875 goto finish;
5876 }
5877
5878
5879 if (split)
5880 goto repeat;
5881
5882
5883 len = count;
5884 if (len > e1_blk + e1_len - lblk1)
5885 len = e1_blk + e1_len - lblk1;
5886 if (len > e2_blk + e2_len - lblk2)
5887 len = e2_blk + e2_len - lblk2;
5888
5889 if (len != e1_len) {
5890 split = 1;
5891 *erp = ext4_force_split_extent_at(handle, inode1,
5892 &path1, lblk1 + len, 0);
5893 if (unlikely(*erp))
5894 goto finish;
5895 }
5896 if (len != e2_len) {
5897 split = 1;
5898 *erp = ext4_force_split_extent_at(handle, inode2,
5899 &path2, lblk2 + len, 0);
5900 if (*erp)
5901 goto finish;
5902 }
5903
5904
5905 if (split)
5906 goto repeat;
5907
5908 BUG_ON(e2_len != e1_len);
5909 *erp = ext4_ext_get_access(handle, inode1, path1 + path1->p_depth);
5910 if (unlikely(*erp))
5911 goto finish;
5912 *erp = ext4_ext_get_access(handle, inode2, path2 + path2->p_depth);
5913 if (unlikely(*erp))
5914 goto finish;
5915
5916
5917 tmp_ex = *ex1;
5918 ext4_ext_store_pblock(ex1, ext4_ext_pblock(ex2));
5919 ext4_ext_store_pblock(ex2, ext4_ext_pblock(&tmp_ex));
5920 ex1->ee_len = cpu_to_le16(e2_len);
5921 ex2->ee_len = cpu_to_le16(e1_len);
5922 if (unwritten)
5923 ext4_ext_mark_unwritten(ex2);
5924 if (ext4_ext_is_unwritten(&tmp_ex))
5925 ext4_ext_mark_unwritten(ex1);
5926
5927 ext4_ext_try_to_merge(handle, inode2, path2, ex2);
5928 ext4_ext_try_to_merge(handle, inode1, path1, ex1);
5929 *erp = ext4_ext_dirty(handle, inode2, path2 +
5930 path2->p_depth);
5931 if (unlikely(*erp))
5932 goto finish;
5933 *erp = ext4_ext_dirty(handle, inode1, path1 +
5934 path1->p_depth);
5935
5936
5937
5938
5939
5940
5941 if (unlikely(*erp))
5942 goto finish;
5943 lblk1 += len;
5944 lblk2 += len;
5945 replaced_count += len;
5946 count -= len;
5947
5948 repeat:
5949 ext4_ext_drop_refs(path1);
5950 kfree(path1);
5951 ext4_ext_drop_refs(path2);
5952 kfree(path2);
5953 path1 = path2 = NULL;
5954 }
5955 return replaced_count;
5956}
5957