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