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