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