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