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