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