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