1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (c) 2010 Zheng Liu <lz@freebsd.org>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * $FreeBSD$
29 */
30
31 #include <sys/param.h>
32 #include <sys/systm.h>
33 #include <sys/types.h>
34 #include <sys/kernel.h>
35 #include <sys/malloc.h>
36 #include <sys/vnode.h>
37 #include <sys/bio.h>
38 #include <sys/buf.h>
39 #include <sys/conf.h>
40 #include <sys/sdt.h>
41 #include <sys/stat.h>
42
43 #include <fs/ext2fs/ext2_mount.h>
44 #include <fs/ext2fs/fs.h>
45 #include <fs/ext2fs/inode.h>
46 #include <fs/ext2fs/ext2fs.h>
47 #include <fs/ext2fs/ext2_extents.h>
48 #include <fs/ext2fs/ext2_extern.h>
49
50 SDT_PROVIDER_DECLARE(ext2fs);
51 /*
52 * ext2fs trace probe:
53 * arg0: verbosity. Higher numbers give more verbose messages
54 * arg1: Textual message
55 */
56 SDT_PROBE_DEFINE2(ext2fs, , trace, extents, "int", "char*");
57
58 static MALLOC_DEFINE(M_EXT2EXTENTS, "ext2_extents", "EXT2 extents");
59
60 #ifdef EXT2FS_PRINT_EXTENTS
61 static void
62 ext4_ext_print_extent(struct ext4_extent *ep)
63 {
64
65 printf(" ext %p => (blk %u len %u start %ju)\n",
66 ep, ep->e_blk, ep->e_len,
67 (uint64_t)ep->e_start_hi << 32 | ep->e_start_lo);
68 }
69
70 static void ext4_ext_print_header(struct inode *ip, struct ext4_extent_header *ehp);
71
72 static void
73 ext4_ext_print_index(struct inode *ip, struct ext4_extent_index *ex, int do_walk)
74 {
75 struct m_ext2fs *fs;
76 struct buf *bp;
77 int error;
78
79 fs = ip->i_e2fs;
80
81 printf(" index %p => (blk %u pblk %ju)\n",
82 ex, ex->ei_blk, (uint64_t)ex->ei_leaf_hi << 32 | ex->ei_leaf_lo);
83
84 if(!do_walk)
85 return;
86
87 if ((error = bread(ip->i_devvp,
88 fsbtodb(fs, ((uint64_t)ex->ei_leaf_hi << 32 | ex->ei_leaf_lo)),
89 (int)fs->e2fs_bsize, NOCRED, &bp)) != 0) {
90 brelse(bp);
91 return;
92 }
93
94 ext4_ext_print_header(ip, (struct ext4_extent_header *)bp->b_data);
95
96 brelse(bp);
97
98 }
99
100 static void
101 ext4_ext_print_header(struct inode *ip, struct ext4_extent_header *ehp)
102 {
103 int i;
104
105 printf("header %p => (magic 0x%x entries %d max %d depth %d gen %d)\n",
106 ehp, ehp->eh_magic, ehp->eh_ecount, ehp->eh_max, ehp->eh_depth,
107 ehp->eh_gen);
108
109 for (i = 0; i < ehp->eh_ecount; i++)
110 if (ehp->eh_depth != 0)
111 ext4_ext_print_index(ip,
112 (struct ext4_extent_index *)(ehp + 1 + i), 1);
113 else
114 ext4_ext_print_extent((struct ext4_extent *)(ehp + 1 + i));
115 }
116
117 static void
118 ext4_ext_print_path(struct inode *ip, struct ext4_extent_path *path)
119 {
120 int k, l;
121
122 l = path->ep_depth;
123
124 printf("ip=%ju, Path:\n", ip->i_number);
125 for (k = 0; k <= l; k++, path++) {
126 if (path->ep_index) {
127 ext4_ext_print_index(ip, path->ep_index, 0);
128 } else if (path->ep_ext) {
129 ext4_ext_print_extent(path->ep_ext);
130 }
131 }
132 }
133
134 void
135 ext4_ext_print_extent_tree_status(struct inode *ip)
136 {
137 struct ext4_extent_header *ehp;
138
139 ehp = (struct ext4_extent_header *)(char *)ip->i_db;
140
141 printf("Extent status:ip=%ju\n", ip->i_number);
142 if (!(ip->i_flag & IN_E4EXTENTS))
143 return;
144
145 ext4_ext_print_header(ip, ehp);
146
147 return;
148 }
149 #endif
150
151 static inline struct ext4_extent_header *
152 ext4_ext_inode_header(struct inode *ip)
153 {
154
155 return ((struct ext4_extent_header *)ip->i_db);
156 }
157
158 static inline struct ext4_extent_header *
159 ext4_ext_block_header(char *bdata)
160 {
161
162 return ((struct ext4_extent_header *)bdata);
163 }
164
165 static inline unsigned short
166 ext4_ext_inode_depth(struct inode *ip)
167 {
168 struct ext4_extent_header *ehp;
169
170 ehp = (struct ext4_extent_header *)ip->i_data;
171 return (ehp->eh_depth);
172 }
173
174 static inline e4fs_daddr_t
175 ext4_ext_index_pblock(struct ext4_extent_index *index)
176 {
177 e4fs_daddr_t blk;
178
179 blk = index->ei_leaf_lo;
180 blk |= (e4fs_daddr_t)index->ei_leaf_hi << 32;
181
182 return (blk);
183 }
184
185 static inline void
186 ext4_index_store_pblock(struct ext4_extent_index *index, e4fs_daddr_t pb)
187 {
188
189 index->ei_leaf_lo = pb & 0xffffffff;
190 index->ei_leaf_hi = (pb >> 32) & 0xffff;
191 }
192
193
194 static inline e4fs_daddr_t
195 ext4_ext_extent_pblock(struct ext4_extent *extent)
196 {
197 e4fs_daddr_t blk;
198
199 blk = extent->e_start_lo;
200 blk |= (e4fs_daddr_t)extent->e_start_hi << 32;
201
202 return (blk);
203 }
204
205 static inline void
206 ext4_ext_store_pblock(struct ext4_extent *ex, e4fs_daddr_t pb)
207 {
208
209 ex->e_start_lo = pb & 0xffffffff;
210 ex->e_start_hi = (pb >> 32) & 0xffff;
211 }
212
213 int
214 ext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep)
215 {
216 struct ext4_extent_cache *ecp;
217 int ret = EXT4_EXT_CACHE_NO;
218
219 ecp = &ip->i_ext_cache;
220 if (ecp->ec_type == EXT4_EXT_CACHE_NO)
221 return (ret);
222
223 if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
224 ep->e_blk = ecp->ec_blk;
225 ep->e_start_lo = ecp->ec_start & 0xffffffff;
226 ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
227 ep->e_len = ecp->ec_len;
228 ret = ecp->ec_type;
229 }
230 return (ret);
231 }
232
233 static int
234 ext4_ext_check_header(struct inode *ip, struct ext4_extent_header *eh)
235 {
236 struct m_ext2fs *fs;
237 char *error_msg;
238
239 fs = ip->i_e2fs;
240
241 if (eh->eh_magic != EXT4_EXT_MAGIC) {
242 error_msg = "header: invalid magic";
243 goto corrupted;
244 }
245 if (eh->eh_max == 0) {
246 error_msg = "header: invalid eh_max";
247 goto corrupted;
248 }
249 if (eh->eh_ecount > eh->eh_max) {
250 error_msg = "header: invalid eh_entries";
251 goto corrupted;
252 }
253 if (eh->eh_depth > 5) {
254 error_msg = "header: invalid eh_depth";
255 goto corrupted;
256 }
257
258 return (0);
259
260 corrupted:
261 SDT_PROBE2(ext2fs, , trace, extents, 1, error_msg);
262 return (EIO);
263 }
264
265 static void
266 ext4_ext_binsearch_index(struct ext4_extent_path *path, int blk)
267 {
268 struct ext4_extent_header *eh;
269 struct ext4_extent_index *r, *l, *m;
270
271 eh = path->ep_header;
272
273 KASSERT(eh->eh_ecount <= eh->eh_max && eh->eh_ecount > 0,
274 ("ext4_ext_binsearch_index: bad args"));
275
276 l = EXT_FIRST_INDEX(eh) + 1;
277 r = EXT_FIRST_INDEX(eh) + eh->eh_ecount - 1;
278 while (l <= r) {
279 m = l + (r - l) / 2;
280 if (blk < m->ei_blk)
281 r = m - 1;
282 else
283 l = m + 1;
284 }
285
286 path->ep_index = l - 1;
287 }
288
289 static void
290 ext4_ext_binsearch_ext(struct ext4_extent_path *path, int blk)
291 {
292 struct ext4_extent_header *eh;
293 struct ext4_extent *r, *l, *m;
294
295 eh = path->ep_header;
296
297 KASSERT(eh->eh_ecount <= eh->eh_max,
298 ("ext4_ext_binsearch_ext: bad args"));
299
300 if (eh->eh_ecount == 0)
301 return;
302
303 l = EXT_FIRST_EXTENT(eh) + 1;
304 r = EXT_FIRST_EXTENT(eh) + eh->eh_ecount - 1;
305
306 while (l <= r) {
307 m = l + (r - l) / 2;
308 if (blk < m->e_blk)
309 r = m - 1;
310 else
311 l = m + 1;
312 }
313
314 path->ep_ext = l - 1;
315 }
316
317 static int
318 ext4_ext_fill_path_bdata(struct ext4_extent_path *path,
319 struct buf *bp, uint64_t blk)
320 {
321
322 KASSERT(path->ep_data == NULL,
323 ("ext4_ext_fill_path_bdata: bad ep_data"));
324
325 path->ep_data = malloc(bp->b_bufsize, M_EXT2EXTENTS, M_WAITOK);
326 memcpy(path->ep_data, bp->b_data, bp->b_bufsize);
327 path->ep_blk = blk;
328
329 return (0);
330 }
331
332 static void
333 ext4_ext_fill_path_buf(struct ext4_extent_path *path, struct buf *bp)
334 {
335
336 KASSERT(path->ep_data != NULL,
337 ("ext4_ext_fill_path_buf: bad ep_data"));
338
339 memcpy(bp->b_data, path->ep_data, bp->b_bufsize);
340 }
341
342 static void
343 ext4_ext_drop_refs(struct ext4_extent_path *path)
344 {
345 int depth, i;
346
347 if (!path)
348 return;
349
350 depth = path->ep_depth;
351 for (i = 0; i <= depth; i++, path++)
352 if (path->ep_data) {
353 free(path->ep_data, M_EXT2EXTENTS);
354 path->ep_data = NULL;
355 }
356 }
357
358 void
359 ext4_ext_path_free(struct ext4_extent_path *path)
360 {
361
362 if (!path)
363 return;
364
365 ext4_ext_drop_refs(path);
366 free(path, M_EXT2EXTENTS);
367 }
368
369 int
370 ext4_ext_find_extent(struct inode *ip, daddr_t block,
371 struct ext4_extent_path **ppath)
372 {
373 struct m_ext2fs *fs;
374 struct ext4_extent_header *eh;
375 struct ext4_extent_path *path;
376 struct buf *bp;
377 uint64_t blk;
378 int error, depth, i, ppos, alloc;
379
380 fs = ip->i_e2fs;
381 eh = ext4_ext_inode_header(ip);
382 depth = ext4_ext_inode_depth(ip);
383 ppos = 0;
384 alloc = 0;
385
386 error = ext4_ext_check_header(ip, eh);
387 if (error)
388 return (error);
389
390 if (ppath == NULL)
391 return (EINVAL);
392
393 path = *ppath;
394 if (path == NULL) {
395 path = malloc(EXT4_EXT_DEPTH_MAX *
396 sizeof(struct ext4_extent_path),
397 M_EXT2EXTENTS, M_WAITOK | M_ZERO);
398 *ppath = path;
399 alloc = 1;
400 }
401
402 path[0].ep_header = eh;
403 path[0].ep_data = NULL;
404
405 /* Walk through the tree. */
406 i = depth;
407 while (i) {
408 ext4_ext_binsearch_index(&path[ppos], block);
409 blk = ext4_ext_index_pblock(path[ppos].ep_index);
410 path[ppos].ep_depth = i;
411 path[ppos].ep_ext = NULL;
412
413 error = bread(ip->i_devvp, fsbtodb(ip->i_e2fs, blk),
414 ip->i_e2fs->e2fs_bsize, NOCRED, &bp);
415 if (error) {
416 brelse(bp);
417 goto error;
418 }
419
420 ppos++;
421 if (ppos > depth) {
422 SDT_PROBE2(ext2fs, , trace, extents, 1,
423 "ppos > depth => extent corrupted");
424 error = EIO;
425 brelse(bp);
426 goto error;
427 }
428
429 ext4_ext_fill_path_bdata(&path[ppos], bp, blk);
430 bqrelse(bp);
431
432 eh = ext4_ext_block_header(path[ppos].ep_data);
433 if (ext4_ext_check_header(ip, eh) ||
434 ext2_extent_blk_csum_verify(ip, path[ppos].ep_data)) {
435 error = EIO;
436 goto error;
437 }
438
439 path[ppos].ep_header = eh;
440
441 i--;
442 }
443
444 error = ext4_ext_check_header(ip, eh);
445 if (error)
446 goto error;
447
448 /* Find extent. */
449 path[ppos].ep_depth = i;
450 path[ppos].ep_header = eh;
451 path[ppos].ep_ext = NULL;
452 path[ppos].ep_index = NULL;
453 ext4_ext_binsearch_ext(&path[ppos], block);
454 return (0);
455
456 error:
457 ext4_ext_drop_refs(path);
458 if (alloc)
459 free(path, M_EXT2EXTENTS);
460
461 *ppath = NULL;
462
463 return (error);
464 }
465
466 static inline int
467 ext4_ext_space_root(struct inode *ip)
468 {
469 int size;
470
471 size = sizeof(ip->i_data);
472 size -= sizeof(struct ext4_extent_header);
473 size /= sizeof(struct ext4_extent);
474
475 return (size);
476 }
477
478 static inline int
479 ext4_ext_space_block(struct inode *ip)
480 {
481 struct m_ext2fs *fs;
482 int size;
483
484 fs = ip->i_e2fs;
485
486 size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) /
487 sizeof(struct ext4_extent);
488
489 return (size);
490 }
491
492 static inline int
493 ext4_ext_space_block_index(struct inode *ip)
494 {
495 struct m_ext2fs *fs;
496 int size;
497
498 fs = ip->i_e2fs;
499
500 size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) /
501 sizeof(struct ext4_extent_index);
502
503 return (size);
504 }
505
506 void
507 ext4_ext_tree_init(struct inode *ip)
508 {
509 struct ext4_extent_header *ehp;
510
511 ip->i_flag |= IN_E4EXTENTS;
512
513 memset(ip->i_data, 0, EXT2_NDADDR + EXT2_NIADDR);
514 ehp = (struct ext4_extent_header *)ip->i_data;
515 ehp->eh_magic = EXT4_EXT_MAGIC;
516 ehp->eh_max = ext4_ext_space_root(ip);
517 ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO;
518 ip->i_flag |= IN_CHANGE | IN_UPDATE;
519 ext2_update(ip->i_vnode, 1);
520 }
521
522 static inline void
523 ext4_ext_put_in_cache(struct inode *ip, uint32_t blk,
524 uint32_t len, uint32_t start, int type)
525 {
526
527 KASSERT(len != 0, ("ext4_ext_put_in_cache: bad input"));
528
529 ip->i_ext_cache.ec_type = type;
530 ip->i_ext_cache.ec_blk = blk;
531 ip->i_ext_cache.ec_len = len;
532 ip->i_ext_cache.ec_start = start;
533 }
534
535 static e4fs_daddr_t
536 ext4_ext_blkpref(struct inode *ip, struct ext4_extent_path *path,
537 e4fs_daddr_t block)
538 {
539 struct m_ext2fs *fs;
540 struct ext4_extent *ex;
541 e4fs_daddr_t bg_start;
542 int depth;
543
544 fs = ip->i_e2fs;
545
546 if (path) {
547 depth = path->ep_depth;
548 ex = path[depth].ep_ext;
549 if (ex) {
550 e4fs_daddr_t pblk = ext4_ext_extent_pblock(ex);
551 e2fs_daddr_t blk = ex->e_blk;
552
553 if (block > blk)
554 return (pblk + (block - blk));
555 else
556 return (pblk - (blk - block));
557 }
558
559 /* Try to get block from index itself. */
560 if (path[depth].ep_data)
561 return (path[depth].ep_blk);
562 }
563
564 /* Use inode's group. */
565 bg_start = (ip->i_block_group * EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) +
566 fs->e2fs->e2fs_first_dblock;
567
568 return (bg_start + block);
569 }
570
571 static int inline
572 ext4_can_extents_be_merged(struct ext4_extent *ex1,
573 struct ext4_extent *ex2)
574 {
575
576 if (ex1->e_blk + ex1->e_len != ex2->e_blk)
577 return (0);
578
579 if (ex1->e_len + ex2->e_len > EXT4_MAX_LEN)
580 return (0);
581
582 if (ext4_ext_extent_pblock(ex1) + ex1->e_len ==
583 ext4_ext_extent_pblock(ex2))
584 return (1);
585
586 return (0);
587 }
588
589 static unsigned
590 ext4_ext_next_leaf_block(struct inode *ip, struct ext4_extent_path *path)
591 {
592 int depth = path->ep_depth;
593
594 /* Empty tree */
595 if (depth == 0)
596 return (EXT4_MAX_BLOCKS);
597
598 /* Go to indexes. */
599 depth--;
600
601 while (depth >= 0) {
602 if (path[depth].ep_index !=
603 EXT_LAST_INDEX(path[depth].ep_header))
604 return (path[depth].ep_index[1].ei_blk);
605
606 depth--;
607 }
608
609 return (EXT4_MAX_BLOCKS);
610 }
611
612 static int
613 ext4_ext_dirty(struct inode *ip, struct ext4_extent_path *path)
614 {
615 struct m_ext2fs *fs;
616 struct buf *bp;
617 uint64_t blk;
618 int error;
619
620 fs = ip->i_e2fs;
621
622 if (!path)
623 return (EINVAL);
624
625 if (path->ep_data) {
626 blk = path->ep_blk;
627 bp = getblk(ip->i_devvp, fsbtodb(fs, blk),
628 fs->e2fs_bsize, 0, 0, 0);
629 if (!bp)
630 return (EIO);
631 ext4_ext_fill_path_buf(path, bp);
632 ext2_extent_blk_csum_set(ip, bp->b_data);
633 error = bwrite(bp);
634 } else {
635 ip->i_flag |= IN_CHANGE | IN_UPDATE;
636 error = ext2_update(ip->i_vnode, 1);
637 }
638
639 return (error);
640 }
641
642 static int
643 ext4_ext_insert_index(struct inode *ip, struct ext4_extent_path *path,
644 uint32_t lblk, e4fs_daddr_t blk)
645 {
646 struct m_ext2fs *fs;
647 struct ext4_extent_index *idx;
648 int len;
649
650 fs = ip->i_e2fs;
651
652 if (lblk == path->ep_index->ei_blk) {
653 SDT_PROBE2(ext2fs, , trace, extents, 1,
654 "lblk == index blk => extent corrupted");
655 return (EIO);
656 }
657
658 if (path->ep_header->eh_ecount >= path->ep_header->eh_max) {
659 SDT_PROBE2(ext2fs, , trace, extents, 1,
660 "ecout > maxcount => extent corrupted");
661 return (EIO);
662 }
663
664 if (lblk > path->ep_index->ei_blk) {
665 /* Insert after. */
666 idx = path->ep_index + 1;
667 } else {
668 /* Insert before. */
669 idx = path->ep_index;
670 }
671
672 len = EXT_LAST_INDEX(path->ep_header) - idx + 1;
673 if (len > 0)
674 memmove(idx + 1, idx, len * sizeof(struct ext4_extent_index));
675
676 if (idx > EXT_MAX_INDEX(path->ep_header)) {
677 SDT_PROBE2(ext2fs, , trace, extents, 1,
678 "index is out of range => extent corrupted");
679 return (EIO);
680 }
681
682 idx->ei_blk = lblk;
683 ext4_index_store_pblock(idx, blk);
684 path->ep_header->eh_ecount++;
685
686 return (ext4_ext_dirty(ip, path));
687 }
688
689 static e4fs_daddr_t
690 ext4_ext_alloc_meta(struct inode *ip)
691 {
692 e4fs_daddr_t blk = ext2_alloc_meta(ip);
693 if (blk) {
694 ip->i_blocks += btodb(ip->i_e2fs->e2fs_bsize);
695 ip->i_flag |= IN_CHANGE | IN_UPDATE;
696 ext2_update(ip->i_vnode, 1);
697 }
698
699 return (blk);
700 }
701
702 static void
703 ext4_ext_blkfree(struct inode *ip, uint64_t blk, int count, int flags)
704 {
705 struct m_ext2fs *fs;
706 int i, blocksreleased;
707
708 fs = ip->i_e2fs;
709 blocksreleased = count;
710
711 for(i = 0; i < count; i++)
712 ext2_blkfree(ip, blk + i, fs->e2fs_bsize);
713
714 if (ip->i_blocks >= blocksreleased)
715 ip->i_blocks -= (btodb(fs->e2fs_bsize)*blocksreleased);
716 else
717 ip->i_blocks = 0;
718
719 ip->i_flag |= IN_CHANGE | IN_UPDATE;
720 ext2_update(ip->i_vnode, 1);
721 }
722
723 static int
724 ext4_ext_split(struct inode *ip, struct ext4_extent_path *path,
725 struct ext4_extent *newext, int at)
726 {
727 struct m_ext2fs *fs;
728 struct buf *bp;
729 int depth = ext4_ext_inode_depth(ip);
730 struct ext4_extent_header *neh;
731 struct ext4_extent_index *fidx;
732 struct ext4_extent *ex;
733 int i = at, k, m, a;
734 e4fs_daddr_t newblk, oldblk;
735 uint32_t border;
736 e4fs_daddr_t *ablks = NULL;
737 int error = 0;
738
739 fs = ip->i_e2fs;
740 bp = NULL;
741
742 /*
743 * We will split at current extent for now.
744 */
745 if (path[depth].ep_ext > EXT_MAX_EXTENT(path[depth].ep_header)) {
746 SDT_PROBE2(ext2fs, , trace, extents, 1,
747 "extent is out of range => extent corrupted");
748 return (EIO);
749 }
750
751 if (path[depth].ep_ext != EXT_MAX_EXTENT(path[depth].ep_header))
752 border = path[depth].ep_ext[1].e_blk;
753 else
754 border = newext->e_blk;
755
756 /* Allocate new blocks. */
757 ablks = malloc(sizeof(e4fs_daddr_t) * depth,
758 M_EXT2EXTENTS, M_WAITOK | M_ZERO);
759 for (a = 0; a < depth - at; a++) {
760 newblk = ext4_ext_alloc_meta(ip);
761 if (newblk == 0)
762 goto cleanup;
763 ablks[a] = newblk;
764 }
765
766 newblk = ablks[--a];
767 bp = getblk(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, 0, 0, 0);
768 if (!bp) {
769 error = EIO;
770 goto cleanup;
771 }
772
773 neh = ext4_ext_block_header(bp->b_data);
774 neh->eh_ecount = 0;
775 neh->eh_max = ext4_ext_space_block(ip);
776 neh->eh_magic = EXT4_EXT_MAGIC;
777 neh->eh_depth = 0;
778 ex = EXT_FIRST_EXTENT(neh);
779
780 if (path[depth].ep_header->eh_ecount != path[depth].ep_header->eh_max) {
781 SDT_PROBE2(ext2fs, , trace, extents, 1,
782 "extents count out of range => extent corrupted");
783 error = EIO;
784 goto cleanup;
785 }
786
787 /* Start copy from next extent. */
788 m = 0;
789 path[depth].ep_ext++;
790 while (path[depth].ep_ext <= EXT_MAX_EXTENT(path[depth].ep_header)) {
791 path[depth].ep_ext++;
792 m++;
793 }
794 if (m) {
795 memmove(ex, path[depth].ep_ext - m,
796 sizeof(struct ext4_extent) * m);
797 neh->eh_ecount = neh->eh_ecount + m;
798 }
799
800 ext2_extent_blk_csum_set(ip, bp->b_data);
801 bwrite(bp);
802 bp = NULL;
803
804 /* Fix old leaf. */
805 if (m) {
806 path[depth].ep_header->eh_ecount =
807 path[depth].ep_header->eh_ecount - m;
808 ext4_ext_dirty(ip, path + depth);
809 }
810
811 /* Create intermediate indexes. */
812 k = depth - at - 1;
813 KASSERT(k >= 0, ("ext4_ext_split: negative k"));
814
815 /* Insert new index into current index block. */
816 i = depth - 1;
817 while (k--) {
818 oldblk = newblk;
819 newblk = ablks[--a];
820 error = bread(ip->i_devvp, fsbtodb(fs, newblk),
821 (int)fs->e2fs_bsize, NOCRED, &bp);
822 if (error) {
823 brelse(bp);
824 goto cleanup;
825 }
826
827 neh = (struct ext4_extent_header *)bp->b_data;
828 neh->eh_ecount = 1;
829 neh->eh_magic = EXT4_EXT_MAGIC;
830 neh->eh_max = ext4_ext_space_block_index(ip);
831 neh->eh_depth = depth - i;
832 fidx = EXT_FIRST_INDEX(neh);
833 fidx->ei_blk = border;
834 ext4_index_store_pblock(fidx, oldblk);
835
836 m = 0;
837 path[i].ep_index++;
838 while (path[i].ep_index <= EXT_MAX_INDEX(path[i].ep_header)) {
839 path[i].ep_index++;
840 m++;
841 }
842 if (m) {
843 memmove(++fidx, path[i].ep_index - m,
844 sizeof(struct ext4_extent_index) * m);
845 neh->eh_ecount = neh->eh_ecount + m;
846 }
847
848 ext2_extent_blk_csum_set(ip, bp->b_data);
849 bwrite(bp);
850 bp = NULL;
851
852 /* Fix old index. */
853 if (m) {
854 path[i].ep_header->eh_ecount =
855 path[i].ep_header->eh_ecount - m;
856 ext4_ext_dirty(ip, path + i);
857 }
858
859 i--;
860 }
861
862 error = ext4_ext_insert_index(ip, path + at, border, newblk);
863
864 cleanup:
865 if (bp)
866 brelse(bp);
867
868 if (error) {
869 for (i = 0; i < depth; i++) {
870 if (!ablks[i])
871 continue;
872 ext4_ext_blkfree(ip, ablks[i], 1, 0);
873 }
874 }
875
876 free(ablks, M_EXT2EXTENTS);
877
878 return (error);
879 }
880
881 static int
882 ext4_ext_grow_indepth(struct inode *ip, struct ext4_extent_path *path,
883 struct ext4_extent *newext)
884 {
885 struct m_ext2fs *fs;
886 struct ext4_extent_path *curpath;
887 struct ext4_extent_header *neh;
888 struct buf *bp;
889 e4fs_daddr_t newblk;
890 int error = 0;
891
892 fs = ip->i_e2fs;
893 curpath = path;
894
895 newblk = ext4_ext_alloc_meta(ip);
896 if (newblk == 0)
897 return (error);
898
899 bp = getblk(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, 0, 0, 0);
900 if (!bp)
901 return (EIO);
902
903 /* Move top-level index/leaf into new block. */
904 memmove(bp->b_data, curpath->ep_header, sizeof(ip->i_data));
905
906 /* Set size of new block */
907 neh = ext4_ext_block_header(bp->b_data);
908 neh->eh_magic = EXT4_EXT_MAGIC;
909
910 if (ext4_ext_inode_depth(ip))
911 neh->eh_max = ext4_ext_space_block_index(ip);
912 else
913 neh->eh_max = ext4_ext_space_block(ip);
914
915 ext2_extent_blk_csum_set(ip, bp->b_data);
916 error = bwrite(bp);
917 if (error)
918 goto out;
919
920 bp = NULL;
921
922 curpath->ep_header->eh_magic = EXT4_EXT_MAGIC;
923 curpath->ep_header->eh_max = ext4_ext_space_root(ip);
924 curpath->ep_header->eh_ecount = 1;
925 curpath->ep_index = EXT_FIRST_INDEX(curpath->ep_header);
926 curpath->ep_index->ei_blk = EXT_FIRST_EXTENT(path[0].ep_header)->e_blk;
927 ext4_index_store_pblock(curpath->ep_index, newblk);
928
929 neh = ext4_ext_inode_header(ip);
930 neh->eh_depth = path->ep_depth + 1;
931 ext4_ext_dirty(ip, curpath);
932 out:
933 brelse(bp);
934
935 return (error);
936 }
937
938 static int
939 ext4_ext_create_new_leaf(struct inode *ip, struct ext4_extent_path *path,
940 struct ext4_extent *newext)
941 {
942 struct ext4_extent_path *curpath;
943 int depth, i, error;
944
945 repeat:
946 i = depth = ext4_ext_inode_depth(ip);
947
948 /* Look for free index entry int the tree */
949 curpath = path + depth;
950 while (i > 0 && !EXT_HAS_FREE_INDEX(curpath)) {
951 i--;
952 curpath--;
953 }
954
955 /*
956 * We use already allocated block for index block,
957 * so subsequent data blocks should be contiguous.
958 */
959 if (EXT_HAS_FREE_INDEX(curpath)) {
960 error = ext4_ext_split(ip, path, newext, i);
961 if (error)
962 goto out;
963
964 /* Refill path. */
965 ext4_ext_drop_refs(path);
966 error = ext4_ext_find_extent(ip, newext->e_blk, &path);
967 if (error)
968 goto out;
969 } else {
970 /* Tree is full, do grow in depth. */
971 error = ext4_ext_grow_indepth(ip, path, newext);
972 if (error)
973 goto out;
974
975 /* Refill path. */
976 ext4_ext_drop_refs(path);
977 error = ext4_ext_find_extent(ip, newext->e_blk, &path);
978 if (error)
979 goto out;
980
981 /* Check and split tree if required. */
982 depth = ext4_ext_inode_depth(ip);
983 if (path[depth].ep_header->eh_ecount ==
984 path[depth].ep_header->eh_max)
985 goto repeat;
986 }
987
988 out:
989 return (error);
990 }
991
992 static int
993 ext4_ext_correct_indexes(struct inode *ip, struct ext4_extent_path *path)
994 {
995 struct ext4_extent_header *eh;
996 struct ext4_extent *ex;
997 int32_t border;
998 int depth, k;
999
1000 depth = ext4_ext_inode_depth(ip);
1001 eh = path[depth].ep_header;
1002 ex = path[depth].ep_ext;
1003
1004 if (ex == NULL || eh == NULL)
1005 return (EIO);
1006
1007 if (!depth)
1008 return (0);
1009
1010 /* We will correct tree if first leaf got modified only. */
1011 if (ex != EXT_FIRST_EXTENT(eh))
1012 return (0);
1013
1014 k = depth - 1;
1015 border = path[depth].ep_ext->e_blk;
1016 path[k].ep_index->ei_blk = border;
1017 ext4_ext_dirty(ip, path + k);
1018 while (k--) {
1019 /* Change all left-side indexes. */
1020 if (path[k+1].ep_index != EXT_FIRST_INDEX(path[k+1].ep_header))
1021 break;
1022
1023 path[k].ep_index->ei_blk = border;
1024 ext4_ext_dirty(ip, path + k);
1025 }
1026
1027 return (0);
1028 }
1029
1030 static int
1031 ext4_ext_insert_extent(struct inode *ip, struct ext4_extent_path *path,
1032 struct ext4_extent *newext)
1033 {
1034 struct ext4_extent_header * eh;
1035 struct ext4_extent *ex, *nex, *nearex;
1036 struct ext4_extent_path *npath;
1037 int depth, len, error, next;
1038
1039 depth = ext4_ext_inode_depth(ip);
1040 ex = path[depth].ep_ext;
1041 npath = NULL;
1042
1043 if (newext->e_len == 0 || path[depth].ep_header == NULL)
1044 return (EINVAL);
1045
1046 /* Insert block into found extent. */
1047 if (ex && ext4_can_extents_be_merged(ex, newext)) {
1048 ex->e_len = ex->e_len + newext->e_len;
1049 eh = path[depth].ep_header;
1050 nearex = ex;
1051 goto merge;
1052 }
1053
1054 repeat:
1055 depth = ext4_ext_inode_depth(ip);
1056 eh = path[depth].ep_header;
1057 if (eh->eh_ecount < eh->eh_max)
1058 goto has_space;
1059
1060 /* Try next leaf */
1061 nex = EXT_LAST_EXTENT(eh);
1062 next = ext4_ext_next_leaf_block(ip, path);
1063 if (newext->e_blk > nex->e_blk && next != EXT4_MAX_BLOCKS) {
1064 KASSERT(npath == NULL,
1065 ("ext4_ext_insert_extent: bad path"));
1066
1067 error = ext4_ext_find_extent(ip, next, &npath);
1068 if (error)
1069 goto cleanup;
1070
1071 if (npath->ep_depth != path->ep_depth) {
1072 error = EIO;
1073 goto cleanup;
1074 }
1075
1076 eh = npath[depth].ep_header;
1077 if (eh->eh_ecount < eh->eh_max) {
1078 path = npath;
1079 goto repeat;
1080 }
1081 }
1082
1083 /*
1084 * There is no free space in the found leaf,
1085 * try to add a new leaf to the tree.
1086 */
1087 error = ext4_ext_create_new_leaf(ip, path, newext);
1088 if (error)
1089 goto cleanup;
1090
1091 depth = ext4_ext_inode_depth(ip);
1092 eh = path[depth].ep_header;
1093
1094 has_space:
1095 nearex = path[depth].ep_ext;
1096 if (!nearex) {
1097 /* Create new extent in the leaf. */
1098 path[depth].ep_ext = EXT_FIRST_EXTENT(eh);
1099 } else if (newext->e_blk > nearex->e_blk) {
1100 if (nearex != EXT_LAST_EXTENT(eh)) {
1101 len = EXT_MAX_EXTENT(eh) - nearex;
1102 len = (len - 1) * sizeof(struct ext4_extent);
1103 len = len < 0 ? 0 : len;
1104 memmove(nearex + 2, nearex + 1, len);
1105 }
1106 path[depth].ep_ext = nearex + 1;
1107 } else {
1108 len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
1109 len = len < 0 ? 0 : len;
1110 memmove(nearex + 1, nearex, len);
1111 path[depth].ep_ext = nearex;
1112 }
1113
1114 eh->eh_ecount = eh->eh_ecount + 1;
1115 nearex = path[depth].ep_ext;
1116 nearex->e_blk = newext->e_blk;
1117 nearex->e_start_lo = newext->e_start_lo;
1118 nearex->e_start_hi = newext->e_start_hi;
1119 nearex->e_len = newext->e_len;
1120
1121 merge:
1122 /* Try to merge extents to the right. */
1123 while (nearex < EXT_LAST_EXTENT(eh)) {
1124 if (!ext4_can_extents_be_merged(nearex, nearex + 1))
1125 break;
1126
1127 /* Merge with next extent. */
1128 nearex->e_len = nearex->e_len + nearex[1].e_len;
1129 if (nearex + 1 < EXT_LAST_EXTENT(eh)) {
1130 len = (EXT_LAST_EXTENT(eh) - nearex - 1) *
1131 sizeof(struct ext4_extent);
1132 memmove(nearex + 1, nearex + 2, len);
1133 }
1134
1135 eh->eh_ecount = eh->eh_ecount - 1;
1136 KASSERT(eh->eh_ecount != 0,
1137 ("ext4_ext_insert_extent: bad ecount"));
1138 }
1139
1140 /*
1141 * Try to merge extents to the left,
1142 * start from inexes correction.
1143 */
1144 error = ext4_ext_correct_indexes(ip, path);
1145 if (error)
1146 goto cleanup;
1147
1148 ext4_ext_dirty(ip, path + depth);
1149
1150 cleanup:
1151 if (npath) {
1152 ext4_ext_drop_refs(npath);
1153 free(npath, M_EXT2EXTENTS);
1154 }
1155
1156 ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO;
1157 return (error);
1158 }
1159
1160 static e4fs_daddr_t
1161 ext4_new_blocks(struct inode *ip, daddr_t lbn, e4fs_daddr_t pref,
1162 struct ucred *cred, unsigned long *count, int *perror)
1163 {
1164 struct m_ext2fs *fs;
1165 e4fs_daddr_t newblk;
1166
1167 /*
1168 * We will allocate only single block for now.
1169 */
1170 if (*count > 1)
1171 return (0);
1172
1173 fs = ip->i_e2fs;
1174 EXT2_LOCK(ip->i_ump);
1175 *perror = ext2_alloc(ip, lbn, pref, (int)fs->e2fs_bsize, cred, &newblk);
1176 if (*perror)
1177 return (0);
1178
1179 if (newblk) {
1180 ip->i_flag |= IN_CHANGE | IN_UPDATE;
1181 ext2_update(ip->i_vnode, 1);
1182 }
1183
1184 return (newblk);
1185 }
1186
1187 int
1188 ext4_ext_get_blocks(struct inode *ip, e4fs_daddr_t iblk,
1189 unsigned long max_blocks, struct ucred *cred, struct buf **bpp,
1190 int *pallocated, daddr_t *nb)
1191 {
1192 struct m_ext2fs *fs;
1193 struct buf *bp = NULL;
1194 struct ext4_extent_path *path;
1195 struct ext4_extent newex, *ex;
1196 e4fs_daddr_t bpref, newblk = 0;
1197 unsigned long allocated = 0;
1198 int error = 0, depth;
1199
1200 if(bpp)
1201 *bpp = NULL;
1202 *pallocated = 0;
1203
1204 /* Check cache. */
1205 path = NULL;
1206 if ((bpref = ext4_ext_in_cache(ip, iblk, &newex))) {
1207 if (bpref == EXT4_EXT_CACHE_IN) {
1208 /* Block is already allocated. */
1209 newblk = iblk - newex.e_blk +
1210 ext4_ext_extent_pblock(&newex);
1211 allocated = newex.e_len - (iblk - newex.e_blk);
1212 goto out;
1213 } else {
1214 error = EIO;
1215 goto out2;
1216 }
1217 }
1218
1219 error = ext4_ext_find_extent(ip, iblk, &path);
1220 if (error) {
1221 goto out2;
1222 }
1223
1224 depth = ext4_ext_inode_depth(ip);
1225 if (path[depth].ep_ext == NULL && depth != 0) {
1226 error = EIO;
1227 goto out2;
1228 }
1229
1230 if ((ex = path[depth].ep_ext)) {
1231 uint64_t lblk = ex->e_blk;
1232 uint16_t e_len = ex->e_len;
1233 e4fs_daddr_t e_start = ext4_ext_extent_pblock(ex);
1234
1235 if (e_len > EXT4_MAX_LEN)
1236 goto out2;
1237
1238 /* If we found extent covers block, simply return it. */
1239 if (iblk >= lblk && iblk < lblk + e_len) {
1240 newblk = iblk - lblk + e_start;
1241 allocated = e_len - (iblk - lblk);
1242 ext4_ext_put_in_cache(ip, lblk, e_len,
1243 e_start, EXT4_EXT_CACHE_IN);
1244 goto out;
1245 }
1246 }
1247
1248 /* Allocate the new block. */
1249 if (S_ISREG(ip->i_mode) && (!ip->i_next_alloc_block)) {
1250 ip->i_next_alloc_goal = 0;
1251 }
1252
1253 bpref = ext4_ext_blkpref(ip, path, iblk);
1254 allocated = max_blocks;
1255 newblk = ext4_new_blocks(ip, iblk, bpref, cred, &allocated, &error);
1256 if (!newblk)
1257 goto out2;
1258
1259 /* Try to insert new extent into found leaf and return. */
1260 newex.e_blk = iblk;
1261 ext4_ext_store_pblock(&newex, newblk);
1262 newex.e_len = allocated;
1263 error = ext4_ext_insert_extent(ip, path, &newex);
1264 if (error)
1265 goto out2;
1266
1267 newblk = ext4_ext_extent_pblock(&newex);
1268 ext4_ext_put_in_cache(ip, iblk, allocated, newblk, EXT4_EXT_CACHE_IN);
1269 *pallocated = 1;
1270
1271 out:
1272 if (allocated > max_blocks)
1273 allocated = max_blocks;
1274
1275 if (bpp)
1276 {
1277 fs = ip->i_e2fs;
1278 error = bread(ip->i_devvp, fsbtodb(fs, newblk),
1279 fs->e2fs_bsize, cred, &bp);
1280 if (error) {
1281 brelse(bp);
1282 } else {
1283 *bpp = bp;
1284 }
1285 }
1286
1287 out2:
1288 if (path) {
1289 ext4_ext_drop_refs(path);
1290 free(path, M_EXT2EXTENTS);
1291 }
1292
1293 if (nb)
1294 *nb = newblk;
1295
1296 return (error);
1297 }
1298
1299 static inline uint16_t
1300 ext4_ext_get_actual_len(struct ext4_extent *ext)
1301 {
1302
1303 return (ext->e_len <= EXT_INIT_MAX_LEN ?
1304 ext->e_len : (ext->e_len - EXT_INIT_MAX_LEN));
1305 }
1306
1307 static inline struct ext4_extent_header *
1308 ext4_ext_header(struct inode *ip)
1309 {
1310
1311 return ((struct ext4_extent_header *)ip->i_db);
1312 }
1313
1314 static int
1315 ext4_remove_blocks(struct inode *ip, struct ext4_extent *ex,
1316 unsigned long from, unsigned long to)
1317 {
1318 unsigned long num, start;
1319
1320 if (from >= ex->e_blk &&
1321 to == ex->e_blk + ext4_ext_get_actual_len(ex) - 1) {
1322 /* Tail cleanup. */
1323 num = ex->e_blk + ext4_ext_get_actual_len(ex) - from;
1324 start = ext4_ext_extent_pblock(ex) +
1325 ext4_ext_get_actual_len(ex) - num;
1326 ext4_ext_blkfree(ip, start, num, 0);
1327 }
1328
1329 return (0);
1330 }
1331
1332 static int
1333 ext4_ext_rm_index(struct inode *ip, struct ext4_extent_path *path)
1334 {
1335 e4fs_daddr_t leaf;
1336
1337 /* Free index block. */
1338 path--;
1339 leaf = ext4_ext_index_pblock(path->ep_index);
1340 KASSERT(path->ep_header->eh_ecount != 0,
1341 ("ext4_ext_rm_index: bad ecount"));
1342 path->ep_header->eh_ecount--;
1343 ext4_ext_dirty(ip, path);
1344 ext4_ext_blkfree(ip, leaf, 1, 0);
1345 return (0);
1346 }
1347
1348 static int
1349 ext4_ext_rm_leaf(struct inode *ip, struct ext4_extent_path *path,
1350 uint64_t start)
1351 {
1352 struct ext4_extent_header *eh;
1353 struct ext4_extent *ex;
1354 unsigned int a, b, block, num;
1355 unsigned long ex_blk;
1356 unsigned short ex_len;
1357 int depth;
1358 int error, correct_index;
1359
1360 depth = ext4_ext_inode_depth(ip);
1361 if (!path[depth].ep_header) {
1362 if (path[depth].ep_data == NULL)
1363 return (EINVAL);
1364 path[depth].ep_header =
1365 (struct ext4_extent_header* )path[depth].ep_data;
1366 }
1367
1368 eh = path[depth].ep_header;
1369 if (!eh) {
1370 SDT_PROBE2(ext2fs, , trace, extents, 1,
1371 "bad header => extent corrupted");
1372 return (EIO);
1373 }
1374
1375 ex = EXT_LAST_EXTENT(eh);
1376 ex_blk = ex->e_blk;
1377 ex_len = ext4_ext_get_actual_len(ex);
1378
1379 error = 0;
1380 correct_index = 0;
1381 while (ex >= EXT_FIRST_EXTENT(eh) && ex_blk + ex_len > start) {
1382 path[depth].ep_ext = ex;
1383 a = ex_blk > start ? ex_blk : start;
1384 b = (uint64_t)ex_blk + ex_len - 1 <
1385 EXT4_MAX_BLOCKS ? ex_blk + ex_len - 1 : EXT4_MAX_BLOCKS;
1386
1387 if (a != ex_blk && b != ex_blk + ex_len - 1)
1388 return (EINVAL);
1389 else if (a != ex_blk) {
1390 /* Remove tail of the extent. */
1391 block = ex_blk;
1392 num = a - block;
1393 } else if (b != ex_blk + ex_len - 1) {
1394 /* Remove head of the extent, not implemented. */
1395 return (EINVAL);
1396 } else {
1397 /* Remove whole extent. */
1398 block = ex_blk;
1399 num = 0;
1400 }
1401
1402 if (ex == EXT_FIRST_EXTENT(eh))
1403 correct_index = 1;
1404
1405 error = ext4_remove_blocks(ip, ex, a, b);
1406 if (error)
1407 goto out;
1408
1409 if (num == 0) {
1410 ext4_ext_store_pblock(ex, 0);
1411 eh->eh_ecount--;
1412 }
1413
1414 ex->e_blk = block;
1415 ex->e_len = num;
1416
1417 ext4_ext_dirty(ip, path + depth);
1418
1419 ex--;
1420 ex_blk = ex->e_blk;
1421 ex_len = ext4_ext_get_actual_len(ex);
1422 };
1423
1424 if (correct_index && eh->eh_ecount)
1425 error = ext4_ext_correct_indexes(ip, path);
1426
1427 /*
1428 * If this leaf is free, we should
1429 * remove it from index block above.
1430 */
1431 if (error == 0 && eh->eh_ecount == 0 && path[depth].ep_data != NULL)
1432 error = ext4_ext_rm_index(ip, path + depth);
1433
1434 out:
1435 return (error);
1436 }
1437
1438 static struct buf *
1439 ext4_read_extent_tree_block(struct inode *ip, e4fs_daddr_t pblk,
1440 int depth, int flags)
1441 {
1442 struct m_ext2fs *fs;
1443 struct ext4_extent_header *eh;
1444 struct buf *bp;
1445 int error;
1446
1447 fs = ip->i_e2fs;
1448 error = bread(ip->i_devvp, fsbtodb(fs, pblk),
1449 fs->e2fs_bsize, NOCRED, &bp);
1450 if (error) {
1451 brelse(bp);
1452 return (NULL);
1453 }
1454
1455 eh = ext4_ext_block_header(bp->b_data);
1456 if (eh->eh_depth != depth) {
1457 SDT_PROBE2(ext2fs, , trace, extents, 1,
1458 "unexpected eh_depth");
1459 goto err;
1460 }
1461
1462 error = ext4_ext_check_header(ip, eh);
1463 if (error)
1464 goto err;
1465
1466 return (bp);
1467
1468 err:
1469 brelse(bp);
1470 return (NULL);
1471
1472 }
1473
1474 static int inline
1475 ext4_ext_more_to_rm(struct ext4_extent_path *path)
1476 {
1477
1478 KASSERT(path->ep_index != NULL,
1479 ("ext4_ext_more_to_rm: bad index from path"));
1480
1481 if (path->ep_index < EXT_FIRST_INDEX(path->ep_header))
1482 return (0);
1483
1484 if (path->ep_header->eh_ecount == path->index_count)
1485 return (0);
1486
1487 return (1);
1488 }
1489
1490 int
1491 ext4_ext_remove_space(struct inode *ip, off_t length, int flags,
1492 struct ucred *cred, struct thread *td)
1493 {
1494 struct buf *bp;
1495 struct ext4_extent_header *ehp;
1496 struct ext4_extent_path *path;
1497 int depth;
1498 int i, error;
1499
1500 ehp = (struct ext4_extent_header *)ip->i_db;
1501 depth = ext4_ext_inode_depth(ip);
1502
1503 error = ext4_ext_check_header(ip, ehp);
1504 if(error)
1505 return (error);
1506
1507 path = malloc(sizeof(struct ext4_extent_path) * (depth + 1),
1508 M_EXT2EXTENTS, M_WAITOK | M_ZERO);
1509 path[0].ep_header = ehp;
1510 path[0].ep_depth = depth;
1511 i = 0;
1512 while (error == 0 && i >= 0) {
1513 if (i == depth) {
1514 /* This is leaf. */
1515 error = ext4_ext_rm_leaf(ip, path, length);
1516 if (error)
1517 break;
1518 free(path[i].ep_data, M_EXT2EXTENTS);
1519 path[i].ep_data = NULL;
1520 i--;
1521 continue;
1522 }
1523
1524 /* This is index. */
1525 if (!path[i].ep_header)
1526 path[i].ep_header =
1527 (struct ext4_extent_header *)path[i].ep_data;
1528
1529 if (!path[i].ep_index) {
1530 /* This level hasn't touched yet. */
1531 path[i].ep_index = EXT_LAST_INDEX(path[i].ep_header);
1532 path[i].index_count = path[i].ep_header->eh_ecount + 1;
1533 } else {
1534 /* We've already was here, see at next index. */
1535 path[i].ep_index--;
1536 }
1537
1538 if (ext4_ext_more_to_rm(path + i)) {
1539 memset(path + i + 1, 0, sizeof(*path));
1540 bp = ext4_read_extent_tree_block(ip,
1541 ext4_ext_index_pblock(path[i].ep_index),
1542 path[0].ep_depth - (i + 1), 0);
1543 if (!bp) {
1544 error = EIO;
1545 break;
1546 }
1547
1548 ext4_ext_fill_path_bdata(&path[i+1], bp,
1549 ext4_ext_index_pblock(path[i].ep_index));
1550 brelse(bp);
1551 path[i].index_count = path[i].ep_header->eh_ecount;
1552 i++;
1553 } else {
1554 if (path[i].ep_header->eh_ecount == 0 && i > 0) {
1555 /* Index is empty, remove it. */
1556 error = ext4_ext_rm_index(ip, path + i);
1557 }
1558 free(path[i].ep_data, M_EXT2EXTENTS);
1559 path[i].ep_data = NULL;
1560 i--;
1561 }
1562 }
1563
1564 if (path->ep_header->eh_ecount == 0) {
1565 /*
1566 * Truncate the tree to zero.
1567 */
1568 ext4_ext_header(ip)->eh_depth = 0;
1569 ext4_ext_header(ip)->eh_max = ext4_ext_space_root(ip);
1570 ext4_ext_dirty(ip, path);
1571 }
1572
1573 ext4_ext_drop_refs(path);
1574 free(path, M_EXT2EXTENTS);
1575
1576 return (error);
1577 }
Cache object: 090283d0e673d8356e1754d72f331256
|