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