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