2 * SPDX-License-Identifier: (BSD-2-Clause AND BSD-3-Clause)
4 * Copyright (c) 2002 Networks Associates Technology, Inc.
7 * This software was developed for the FreeBSD Project by Marshall
8 * Kirk McKusick and Network Associates Laboratories, the Security
9 * Research Division of Network Associates, Inc. under DARPA/SPAWAR
10 * contract N66001-01-C-8035 ("CBOSS"), as part of the DARPA CHATS
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * Copyright (c) 1982, 1986, 1989, 1993
35 * The Regents of the University of California. All rights reserved.
37 * Redistribution and use in source and binary forms, with or without
38 * modification, are permitted provided that the following conditions
40 * 1. Redistributions of source code must retain the above copyright
41 * notice, this list of conditions and the following disclaimer.
42 * 2. Redistributions in binary form must reproduce the above copyright
43 * notice, this list of conditions and the following disclaimer in the
44 * documentation and/or other materials provided with the distribution.
45 * 3. Neither the name of the University nor the names of its contributors
46 * may be used to endorse or promote products derived from this software
47 * without specific prior written permission.
49 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
50 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
51 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
52 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
53 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
54 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
55 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
56 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
57 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
58 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62 #include <sys/cdefs.h>
63 #include "opt_quota.h"
65 #include <sys/param.h>
66 #include <sys/systm.h>
69 #include <sys/capsicum.h>
71 #include <sys/fcntl.h>
73 #include <sys/filedesc.h>
74 #include <sys/gsb_crc32.h>
75 #include <sys/kernel.h>
76 #include <sys/mount.h>
80 #include <sys/syscallsubr.h>
81 #include <sys/sysctl.h>
82 #include <sys/syslog.h>
83 #include <sys/taskqueue.h>
84 #include <sys/vnode.h>
86 #include <security/audit/audit.h>
88 #include <geom/geom.h>
89 #include <geom/geom_vfs.h>
91 #include <ufs/ufs/dir.h>
92 #include <ufs/ufs/extattr.h>
93 #include <ufs/ufs/quota.h>
94 #include <ufs/ufs/inode.h>
95 #include <ufs/ufs/ufs_extern.h>
96 #include <ufs/ufs/ufsmount.h>
98 #include <ufs/ffs/fs.h>
99 #include <ufs/ffs/ffs_extern.h>
100 #include <ufs/ffs/softdep.h>
102 typedef ufs2_daddr_t allocfcn_t(struct inode *ip, uint64_t cg,
103 ufs2_daddr_t bpref, int size, int rsize);
105 static ufs2_daddr_t ffs_alloccg(struct inode *, uint64_t, ufs2_daddr_t, int,
108 ffs_alloccgblk(struct inode *, struct buf *, ufs2_daddr_t, int);
109 static void ffs_blkfree_cg(struct ufsmount *, struct fs *,
110 struct vnode *, ufs2_daddr_t, long, ino_t,
113 static int ffs_checkfreeblk(struct inode *, ufs2_daddr_t, long);
115 static void ffs_checkcgintegrity(struct fs *, uint64_t, int);
116 static ufs2_daddr_t ffs_clusteralloc(struct inode *, uint64_t, ufs2_daddr_t,
118 static ino_t ffs_dirpref(struct inode *);
119 static ufs2_daddr_t ffs_fragextend(struct inode *, uint64_t, ufs2_daddr_t,
121 static ufs2_daddr_t ffs_hashalloc(struct inode *, uint64_t, ufs2_daddr_t,
122 int, int, allocfcn_t *);
123 static ufs2_daddr_t ffs_nodealloccg(struct inode *, uint64_t, ufs2_daddr_t, int,
125 static ufs1_daddr_t ffs_mapsearch(struct fs *, struct cg *, ufs2_daddr_t, int);
126 static int ffs_reallocblks_ufs1(struct vop_reallocblks_args *);
127 static int ffs_reallocblks_ufs2(struct vop_reallocblks_args *);
128 static void ffs_ckhash_cg(struct buf *);
131 * Allocate a block in the filesystem.
133 * The size of the requested block is given, which must be some
134 * multiple of fs_fsize and <= fs_bsize.
135 * A preference may be optionally specified. If a preference is given
136 * the following hierarchy is used to allocate a block:
137 * 1) allocate the requested block.
138 * 2) allocate a rotationally optimal block in the same cylinder.
139 * 3) allocate a block in the same cylinder group.
140 * 4) quadratically rehash into other cylinder groups, until an
141 * available block is located.
142 * If no block preference is given the following hierarchy is used
143 * to allocate a block:
144 * 1) allocate a block in the cylinder group that contains the
145 * inode for the file.
146 * 2) quadratically rehash into other cylinder groups, until an
147 * available block is located.
150 ffs_alloc(struct inode *ip,
159 struct ufsmount *ump;
161 uint64_t cg, reclaimed;
170 mtx_assert(UFS_MTX(ump), MA_OWNED);
172 if ((uint64_t)size > fs->fs_bsize || fragoff(fs, size) != 0) {
173 printf("dev = %s, bsize = %ld, size = %d, fs = %s\n",
174 devtoname(ump->um_dev), (long)fs->fs_bsize, size,
176 panic("ffs_alloc: bad size");
179 panic("ffs_alloc: missing credential");
180 #endif /* INVARIANTS */
185 error = chkdq(ip, btodb(size), cred, 0);
190 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0)
192 if (priv_check_cred(cred, PRIV_VFS_BLOCKRESERVE) &&
193 freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0)
195 if (bpref >= fs->fs_size)
198 cg = ino_to_cg(fs, ip->i_number);
200 cg = dtog(fs, bpref);
201 bno = ffs_hashalloc(ip, cg, bpref, size, size, ffs_alloccg);
204 DIP_SET(ip, i_blocks, DIP(ip, i_blocks) + delta);
206 UFS_INODE_SET_FLAG(ip, IN_CHANGE);
208 UFS_INODE_SET_FLAG(ip, IN_CHANGE | IN_UPDATE);
216 * Restore user's disk quota because allocation failed.
218 (void) chkdq(ip, -btodb(size), cred, FORCE);
221 if (reclaimed == 0 && (flags & IO_BUFLOCKED) == 0) {
223 softdep_request_cleanup(fs, ITOV(ip), cred, FLUSH_BLOCKS_WAIT);
226 if (ffs_fsfail_cleanup_locked(ump, 0)) {
231 ppsratecheck(&ump->um_last_fullmsg, &ump->um_secs_fullmsg, 1)) {
233 ffs_fserr(fs, ip->i_number, "filesystem full");
234 uprintf("\n%s: write failed, filesystem is full\n",
243 * Reallocate a fragment to a bigger size
245 * The number and size of the old block is given, and a preference
246 * and new size is also specified. The allocator attempts to extend
247 * the original block. Failing that, the regular block allocator is
248 * invoked to get an appropriate block.
251 ffs_realloccg(struct inode *ip,
264 struct ufsmount *ump;
265 uint64_t cg, request, reclaimed;
274 gbflags = (flags & BA_UNMAPPED) != 0 ? GB_UNMAPPED : 0;
276 gbflags |= IS_SNAPSHOT(ip) ? GB_NOWITNESS : 0;
279 mtx_assert(UFS_MTX(ump), MA_OWNED);
281 if (vp->v_mount->mnt_kern_flag & MNTK_SUSPENDED)
282 panic("ffs_realloccg: allocation on suspended filesystem");
283 if ((uint64_t)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||
284 (uint64_t)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) {
286 "dev = %s, bsize = %ld, osize = %d, nsize = %d, fs = %s\n",
287 devtoname(ump->um_dev), (long)fs->fs_bsize, osize,
288 nsize, fs->fs_fsmnt);
289 panic("ffs_realloccg: bad size");
292 panic("ffs_realloccg: missing credential");
293 #endif /* INVARIANTS */
296 if (priv_check_cred(cred, PRIV_VFS_BLOCKRESERVE) &&
297 freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) {
301 printf("dev = %s, bsize = %ld, bprev = %jd, fs = %s\n",
302 devtoname(ump->um_dev), (long)fs->fs_bsize, (intmax_t)bprev,
304 panic("ffs_realloccg: bad bprev");
308 * Allocate the extra space in the buffer.
310 error = bread_gb(vp, lbprev, osize, NOCRED, gbflags, &bp);
315 if (bp->b_blkno == bp->b_lblkno) {
316 if (lbprev >= UFS_NDADDR)
317 panic("ffs_realloccg: lbprev out of range");
318 bp->b_blkno = fsbtodb(fs, bprev);
322 error = chkdq(ip, btodb(nsize - osize), cred, 0);
329 * Check for extension in the existing location.
332 cg = dtog(fs, bprev);
334 bno = ffs_fragextend(ip, cg, bprev, osize, nsize);
336 if (bp->b_blkno != fsbtodb(fs, bno))
337 panic("ffs_realloccg: bad blockno");
338 delta = btodb(nsize - osize);
339 DIP_SET(ip, i_blocks, DIP(ip, i_blocks) + delta);
341 UFS_INODE_SET_FLAG(ip, IN_CHANGE);
343 UFS_INODE_SET_FLAG(ip, IN_CHANGE | IN_UPDATE);
345 bp->b_flags |= B_DONE;
346 vfs_bio_bzero_buf(bp, osize, nsize - osize);
347 if ((bp->b_flags & (B_MALLOC | B_VMIO)) == B_VMIO)
348 vfs_bio_set_valid(bp, osize, nsize - osize);
353 * Allocate a new disk location.
355 if (bpref >= fs->fs_size)
357 switch ((int)fs->fs_optim) {
360 * Allocate an exact sized fragment. Although this makes
361 * best use of space, we will waste time relocating it if
362 * the file continues to grow. If the fragmentation is
363 * less than half of the minimum free reserve, we choose
364 * to begin optimizing for time.
367 if (fs->fs_minfree <= 5 ||
368 fs->fs_cstotal.cs_nffree >
369 (off_t)fs->fs_dsize * fs->fs_minfree / (2 * 100))
371 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n",
373 fs->fs_optim = FS_OPTTIME;
377 * At this point we have discovered a file that is trying to
378 * grow a small fragment to a larger fragment. To save time,
379 * we allocate a full sized block, then free the unused portion.
380 * If the file continues to grow, the `ffs_fragextend' call
381 * above will be able to grow it in place without further
382 * copying. If aberrant programs cause disk fragmentation to
383 * grow within 2% of the free reserve, we choose to begin
384 * optimizing for space.
386 request = fs->fs_bsize;
387 if (fs->fs_cstotal.cs_nffree <
388 (off_t)fs->fs_dsize * (fs->fs_minfree - 2) / 100)
390 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n",
392 fs->fs_optim = FS_OPTSPACE;
395 printf("dev = %s, optim = %ld, fs = %s\n",
396 devtoname(ump->um_dev), (long)fs->fs_optim, fs->fs_fsmnt);
397 panic("ffs_realloccg: bad optim");
400 bno = ffs_hashalloc(ip, cg, bpref, request, nsize, ffs_alloccg);
402 bp->b_blkno = fsbtodb(fs, bno);
403 if (!DOINGSOFTDEP(vp))
405 * The usual case is that a smaller fragment that
406 * was just allocated has been replaced with a bigger
407 * fragment or a full-size block. If it is marked as
408 * B_DELWRI, the current contents have not been written
409 * to disk. It is possible that the block was written
410 * earlier, but very uncommon. If the block has never
411 * been written, there is no need to send a BIO_DELETE
412 * for it when it is freed. The gain from avoiding the
413 * TRIMs for the common case of unwritten blocks far
414 * exceeds the cost of the write amplification for the
415 * uncommon case of failing to send a TRIM for a block
416 * that had been written.
418 ffs_blkfree(ump, fs, ump->um_devvp, bprev, (long)osize,
419 ip->i_number, vp->v_type, NULL,
420 (bp->b_flags & B_DELWRI) != 0 ?
421 NOTRIM_KEY : SINGLETON_KEY);
422 delta = btodb(nsize - osize);
423 DIP_SET(ip, i_blocks, DIP(ip, i_blocks) + delta);
425 UFS_INODE_SET_FLAG(ip, IN_CHANGE);
427 UFS_INODE_SET_FLAG(ip, IN_CHANGE | IN_UPDATE);
429 bp->b_flags |= B_DONE;
430 vfs_bio_bzero_buf(bp, osize, nsize - osize);
431 if ((bp->b_flags & (B_MALLOC | B_VMIO)) == B_VMIO)
432 vfs_bio_set_valid(bp, osize, nsize - osize);
439 * Restore user's disk quota because allocation failed.
441 (void) chkdq(ip, -btodb(nsize - osize), cred, FORCE);
448 if (reclaimed == 0 && (flags & IO_BUFLOCKED) == 0) {
456 softdep_request_cleanup(fs, vp, cred, FLUSH_BLOCKS_WAIT);
461 if (ffs_fsfail_cleanup_locked(ump, 0)) {
466 ppsratecheck(&ump->um_last_fullmsg, &ump->um_secs_fullmsg, 1)) {
468 ffs_fserr(fs, ip->i_number, "filesystem full");
469 uprintf("\n%s: write failed, filesystem is full\n",
478 * Reallocate a sequence of blocks into a contiguous sequence of blocks.
480 * The vnode and an array of buffer pointers for a range of sequential
481 * logical blocks to be made contiguous is given. The allocator attempts
482 * to find a range of sequential blocks starting as close as possible
483 * from the end of the allocation for the logical block immediately
484 * preceding the current range. If successful, the physical block numbers
485 * in the buffer pointers and in the inode are changed to reflect the new
486 * allocation. If unsuccessful, the allocation is left unchanged. The
487 * success in doing the reallocation is returned. Note that the error
488 * return is not reflected back to the user. Rather the previous block
489 * allocation will be used.
492 SYSCTL_NODE(_vfs, OID_AUTO, ffs, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
495 static int doasyncfree = 1;
496 SYSCTL_INT(_vfs_ffs, OID_AUTO, doasyncfree, CTLFLAG_RW, &doasyncfree, 0,
497 "do not force synchronous writes when blocks are reallocated");
499 static int doreallocblks = 1;
500 SYSCTL_INT(_vfs_ffs, OID_AUTO, doreallocblks, CTLFLAG_RW, &doreallocblks, 0,
501 "enable block reallocation");
503 static int dotrimcons = 1;
504 SYSCTL_INT(_vfs_ffs, OID_AUTO, dotrimcons, CTLFLAG_RWTUN, &dotrimcons, 0,
505 "enable BIO_DELETE / TRIM consolidation");
507 static int maxclustersearch = 10;
508 SYSCTL_INT(_vfs_ffs, OID_AUTO, maxclustersearch, CTLFLAG_RW, &maxclustersearch,
509 0, "max number of cylinder group to search for contigous blocks");
512 static int prtrealloc = 0;
513 SYSCTL_INT(_debug, OID_AUTO, ffs_prtrealloc, CTLFLAG_RW, &prtrealloc, 0,
514 "print out FFS filesystem block reallocation operations");
519 struct vop_reallocblks_args /* {
521 struct cluster_save *a_buflist;
524 struct ufsmount *ump;
528 * We used to skip reallocating the blocks of a file into a
529 * contiguous sequence if the underlying flash device requested
530 * BIO_DELETE notifications, because devices that benefit from
531 * BIO_DELETE also benefit from not moving the data. However,
532 * the destination for the data is usually moved before the data
533 * is written to the initially allocated location, so we rarely
534 * suffer the penalty of extra writes. With the addition of the
535 * consolidation of contiguous blocks into single BIO_DELETE
536 * operations, having fewer but larger contiguous blocks reduces
537 * the number of (slow and expensive) BIO_DELETE operations. So
538 * when doing BIO_DELETE consolidation, we do block reallocation.
540 * Skip if reallocblks has been disabled globally.
542 ump = ap->a_vp->v_mount->mnt_data;
543 if ((((ump->um_flags) & UM_CANDELETE) != 0 && dotrimcons == 0) ||
548 * We can't wait in softdep prealloc as it may fsync and recurse
549 * here. Instead we simply fail to reallocate blocks if this
550 * rare condition arises.
552 if (DOINGSUJ(ap->a_vp))
553 if (softdep_prealloc(ap->a_vp, MNT_NOWAIT) != 0)
555 vn_seqc_write_begin(ap->a_vp);
556 error = ump->um_fstype == UFS1 ? ffs_reallocblks_ufs1(ap) :
557 ffs_reallocblks_ufs2(ap);
558 vn_seqc_write_end(ap->a_vp);
563 ffs_reallocblks_ufs1(
564 struct vop_reallocblks_args /* {
566 struct cluster_save *a_buflist;
572 struct buf *sbp, *ebp, *bp;
573 ufs1_daddr_t *bap, *sbap, *ebap;
574 struct cluster_save *buflist;
575 struct ufsmount *ump;
576 ufs_lbn_t start_lbn, end_lbn;
577 ufs1_daddr_t soff, newblk, blkno;
579 struct indir start_ap[UFS_NIADDR + 1], end_ap[UFS_NIADDR + 1], *idp;
580 int i, cg, len, start_lvl, end_lvl, ssize;
587 * If we are not tracking block clusters or if we have less than 4%
588 * free blocks left, then do not attempt to cluster. Running with
589 * less than 5% free block reserve is not recommended and those that
590 * choose to do so do not expect to have good file layout.
592 if (fs->fs_contigsumsize <= 0 || freespace(fs, 4) < 0)
594 buflist = ap->a_buflist;
595 len = buflist->bs_nchildren;
596 start_lbn = buflist->bs_children[0]->b_lblkno;
597 end_lbn = start_lbn + len - 1;
599 for (i = 0; i < len; i++)
600 if (!ffs_checkfreeblk(ip,
601 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
602 panic("ffs_reallocblks: unallocated block 1");
603 for (i = 1; i < len; i++)
604 if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
605 panic("ffs_reallocblks: non-logical cluster");
606 blkno = buflist->bs_children[0]->b_blkno;
607 ssize = fsbtodb(fs, fs->fs_frag);
608 for (i = 1; i < len - 1; i++)
609 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize))
610 panic("ffs_reallocblks: non-physical cluster %d", i);
613 * If the cluster crosses the boundary for the first indirect
614 * block, leave space for the indirect block. Indirect blocks
615 * are initially laid out in a position after the last direct
616 * block. Block reallocation would usually destroy locality by
617 * moving the indirect block out of the way to make room for
618 * data blocks if we didn't compensate here. We should also do
619 * this for other indirect block boundaries, but it is only
620 * important for the first one.
622 if (start_lbn < UFS_NDADDR && end_lbn >= UFS_NDADDR)
625 * If the latest allocation is in a new cylinder group, assume that
626 * the filesystem has decided to move and do not force it back to
627 * the previous cylinder group.
629 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
630 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
632 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
633 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl))
636 * Get the starting offset and block map for the first block.
638 if (start_lvl == 0) {
639 sbap = &ip->i_din1->di_db[0];
642 idp = &start_ap[start_lvl - 1];
643 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) {
647 sbap = (ufs1_daddr_t *)sbp->b_data;
651 * If the block range spans two block maps, get the second map.
654 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
659 start_ap[start_lvl - 1].in_lbn == idp->in_lbn)
660 panic("ffs_reallocblk: start == end");
662 ssize = len - (idp->in_off + 1);
663 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp))
665 ebap = (ufs1_daddr_t *)ebp->b_data;
668 * Find the preferred location for the cluster. If we have not
669 * previously failed at this endeavor, then follow our standard
670 * preference calculation. If we have failed at it, then pick up
671 * where we last ended our search.
674 if (ip->i_nextclustercg == -1)
675 pref = ffs_blkpref_ufs1(ip, start_lbn, soff, sbap);
677 pref = cgdata(fs, ip->i_nextclustercg);
679 * Search the block map looking for an allocation of the desired size.
680 * To avoid wasting too much time, we limit the number of cylinder
681 * groups that we will search.
684 for (i = min(maxclustersearch, fs->fs_ncg); i > 0; i--) {
685 if ((newblk = ffs_clusteralloc(ip, cg, pref, len)) != 0)
688 if (cg >= fs->fs_ncg)
692 * If we have failed in our search, record where we gave up for
693 * next time. Otherwise, fall back to our usual search citerion.
696 ip->i_nextclustercg = cg;
700 ip->i_nextclustercg = -1;
702 * We have found a new contiguous block.
704 * First we have to replace the old block pointers with the new
705 * block pointers in the inode and indirect blocks associated
710 printf("realloc: ino %ju, lbns %jd-%jd\n\told:",
711 (uintmax_t)ip->i_number,
712 (intmax_t)start_lbn, (intmax_t)end_lbn);
715 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) {
721 if (!ffs_checkfreeblk(ip,
722 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
723 panic("ffs_reallocblks: unallocated block 2");
724 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap)
725 panic("ffs_reallocblks: alloc mismatch");
729 printf(" %d,", *bap);
731 if (DOINGSOFTDEP(vp)) {
732 if (sbap == &ip->i_din1->di_db[0] && i < ssize)
733 softdep_setup_allocdirect(ip, start_lbn + i,
734 blkno, *bap, fs->fs_bsize, fs->fs_bsize,
735 buflist->bs_children[i]);
737 softdep_setup_allocindir_page(ip, start_lbn + i,
738 i < ssize ? sbp : ebp, soff + i, blkno,
739 *bap, buflist->bs_children[i]);
744 * Next we must write out the modified inode and indirect blocks.
745 * For strict correctness, the writes should be synchronous since
746 * the old block values may have been written to disk. In practise
747 * they are almost never written, but if we are concerned about
748 * strict correctness, the `doasyncfree' flag should be set to zero.
750 * The test on `doasyncfree' should be changed to test a flag
751 * that shows whether the associated buffers and inodes have
752 * been written. The flag should be set when the cluster is
753 * started and cleared whenever the buffer or inode is flushed.
754 * We can then check below to see if it is set, and do the
755 * synchronous write only when it has been cleared.
757 if (sbap != &ip->i_din1->di_db[0]) {
763 UFS_INODE_SET_FLAG(ip, IN_CHANGE | IN_UPDATE);
774 * Last, free the old blocks and assign the new blocks to the buffers.
780 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) {
781 bp = buflist->bs_children[i];
782 if (!DOINGSOFTDEP(vp))
784 * The usual case is that a set of N-contiguous blocks
785 * that was just allocated has been replaced with a
786 * set of N+1-contiguous blocks. If they are marked as
787 * B_DELWRI, the current contents have not been written
788 * to disk. It is possible that the blocks were written
789 * earlier, but very uncommon. If the blocks have never
790 * been written, there is no need to send a BIO_DELETE
791 * for them when they are freed. The gain from avoiding
792 * the TRIMs for the common case of unwritten blocks
793 * far exceeds the cost of the write amplification for
794 * the uncommon case of failing to send a TRIM for the
795 * blocks that had been written.
797 ffs_blkfree(ump, fs, ump->um_devvp,
798 dbtofsb(fs, bp->b_blkno),
799 fs->fs_bsize, ip->i_number, vp->v_type, NULL,
800 (bp->b_flags & B_DELWRI) != 0 ?
801 NOTRIM_KEY : SINGLETON_KEY);
802 bp->b_blkno = fsbtodb(fs, blkno);
804 if (!ffs_checkfreeblk(ip, dbtofsb(fs, bp->b_blkno),
806 panic("ffs_reallocblks: unallocated block 3");
810 printf(" %d,", blkno);
824 if (sbap != &ip->i_din1->di_db[0])
830 ffs_reallocblks_ufs2(
831 struct vop_reallocblks_args /* {
833 struct cluster_save *a_buflist;
839 struct buf *sbp, *ebp, *bp;
840 ufs2_daddr_t *bap, *sbap, *ebap;
841 struct cluster_save *buflist;
842 struct ufsmount *ump;
843 ufs_lbn_t start_lbn, end_lbn;
844 ufs2_daddr_t soff, newblk, blkno, pref;
845 struct indir start_ap[UFS_NIADDR + 1], end_ap[UFS_NIADDR + 1], *idp;
846 int i, cg, len, start_lvl, end_lvl, ssize;
853 * If we are not tracking block clusters or if we have less than 4%
854 * free blocks left, then do not attempt to cluster. Running with
855 * less than 5% free block reserve is not recommended and those that
856 * choose to do so do not expect to have good file layout.
858 if (fs->fs_contigsumsize <= 0 || freespace(fs, 4) < 0)
860 buflist = ap->a_buflist;
861 len = buflist->bs_nchildren;
862 start_lbn = buflist->bs_children[0]->b_lblkno;
863 end_lbn = start_lbn + len - 1;
865 for (i = 0; i < len; i++)
866 if (!ffs_checkfreeblk(ip,
867 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
868 panic("ffs_reallocblks: unallocated block 1");
869 for (i = 1; i < len; i++)
870 if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
871 panic("ffs_reallocblks: non-logical cluster");
872 blkno = buflist->bs_children[0]->b_blkno;
873 ssize = fsbtodb(fs, fs->fs_frag);
874 for (i = 1; i < len - 1; i++)
875 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize))
876 panic("ffs_reallocblks: non-physical cluster %d", i);
879 * If the cluster crosses the boundary for the first indirect
880 * block, do not move anything in it. Indirect blocks are
881 * usually initially laid out in a position between the data
882 * blocks. Block reallocation would usually destroy locality by
883 * moving the indirect block out of the way to make room for
884 * data blocks if we didn't compensate here. We should also do
885 * this for other indirect block boundaries, but it is only
886 * important for the first one.
888 if (start_lbn < UFS_NDADDR && end_lbn >= UFS_NDADDR)
891 * If the latest allocation is in a new cylinder group, assume that
892 * the filesystem has decided to move and do not force it back to
893 * the previous cylinder group.
895 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
896 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
898 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
899 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl))
902 * Get the starting offset and block map for the first block.
904 if (start_lvl == 0) {
905 sbap = &ip->i_din2->di_db[0];
908 idp = &start_ap[start_lvl - 1];
909 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) {
913 sbap = (ufs2_daddr_t *)sbp->b_data;
917 * If the block range spans two block maps, get the second map.
920 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
925 start_ap[start_lvl - 1].in_lbn == idp->in_lbn)
926 panic("ffs_reallocblk: start == end");
928 ssize = len - (idp->in_off + 1);
929 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp))
931 ebap = (ufs2_daddr_t *)ebp->b_data;
934 * Find the preferred location for the cluster. If we have not
935 * previously failed at this endeavor, then follow our standard
936 * preference calculation. If we have failed at it, then pick up
937 * where we last ended our search.
940 if (ip->i_nextclustercg == -1)
941 pref = ffs_blkpref_ufs2(ip, start_lbn, soff, sbap);
943 pref = cgdata(fs, ip->i_nextclustercg);
945 * Search the block map looking for an allocation of the desired size.
946 * To avoid wasting too much time, we limit the number of cylinder
947 * groups that we will search.
950 for (i = min(maxclustersearch, fs->fs_ncg); i > 0; i--) {
951 if ((newblk = ffs_clusteralloc(ip, cg, pref, len)) != 0)
954 if (cg >= fs->fs_ncg)
958 * If we have failed in our search, record where we gave up for
959 * next time. Otherwise, fall back to our usual search citerion.
962 ip->i_nextclustercg = cg;
966 ip->i_nextclustercg = -1;
968 * We have found a new contiguous block.
970 * First we have to replace the old block pointers with the new
971 * block pointers in the inode and indirect blocks associated
976 printf("realloc: ino %ju, lbns %jd-%jd\n\told:", (uintmax_t)ip->i_number,
977 (intmax_t)start_lbn, (intmax_t)end_lbn);
980 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) {
986 if (!ffs_checkfreeblk(ip,
987 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
988 panic("ffs_reallocblks: unallocated block 2");
989 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap)
990 panic("ffs_reallocblks: alloc mismatch");
994 printf(" %jd,", (intmax_t)*bap);
996 if (DOINGSOFTDEP(vp)) {
997 if (sbap == &ip->i_din2->di_db[0] && i < ssize)
998 softdep_setup_allocdirect(ip, start_lbn + i,
999 blkno, *bap, fs->fs_bsize, fs->fs_bsize,
1000 buflist->bs_children[i]);
1002 softdep_setup_allocindir_page(ip, start_lbn + i,
1003 i < ssize ? sbp : ebp, soff + i, blkno,
1004 *bap, buflist->bs_children[i]);
1009 * Next we must write out the modified inode and indirect blocks.
1010 * For strict correctness, the writes should be synchronous since
1011 * the old block values may have been written to disk. In practise
1012 * they are almost never written, but if we are concerned about
1013 * strict correctness, the `doasyncfree' flag should be set to zero.
1015 * The test on `doasyncfree' should be changed to test a flag
1016 * that shows whether the associated buffers and inodes have
1017 * been written. The flag should be set when the cluster is
1018 * started and cleared whenever the buffer or inode is flushed.
1019 * We can then check below to see if it is set, and do the
1020 * synchronous write only when it has been cleared.
1022 if (sbap != &ip->i_din2->di_db[0]) {
1028 UFS_INODE_SET_FLAG(ip, IN_CHANGE | IN_UPDATE);
1039 * Last, free the old blocks and assign the new blocks to the buffers.
1045 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) {
1046 bp = buflist->bs_children[i];
1047 if (!DOINGSOFTDEP(vp))
1049 * The usual case is that a set of N-contiguous blocks
1050 * that was just allocated has been replaced with a
1051 * set of N+1-contiguous blocks. If they are marked as
1052 * B_DELWRI, the current contents have not been written
1053 * to disk. It is possible that the blocks were written
1054 * earlier, but very uncommon. If the blocks have never
1055 * been written, there is no need to send a BIO_DELETE
1056 * for them when they are freed. The gain from avoiding
1057 * the TRIMs for the common case of unwritten blocks
1058 * far exceeds the cost of the write amplification for
1059 * the uncommon case of failing to send a TRIM for the
1060 * blocks that had been written.
1062 ffs_blkfree(ump, fs, ump->um_devvp,
1063 dbtofsb(fs, bp->b_blkno),
1064 fs->fs_bsize, ip->i_number, vp->v_type, NULL,
1065 (bp->b_flags & B_DELWRI) != 0 ?
1066 NOTRIM_KEY : SINGLETON_KEY);
1067 bp->b_blkno = fsbtodb(fs, blkno);
1069 if (!ffs_checkfreeblk(ip, dbtofsb(fs, bp->b_blkno),
1071 panic("ffs_reallocblks: unallocated block 3");
1075 printf(" %jd,", (intmax_t)blkno);
1089 if (sbap != &ip->i_din2->di_db[0])
1095 * Allocate an inode in the filesystem.
1097 * If allocating a directory, use ffs_dirpref to select the inode.
1098 * If allocating in a directory, the following hierarchy is followed:
1099 * 1) allocate the preferred inode.
1100 * 2) allocate an inode in the same cylinder group.
1101 * 3) quadratically rehash into other cylinder groups, until an
1102 * available inode is located.
1103 * If no inode preference is given the following hierarchy is used
1104 * to allocate an inode:
1105 * 1) allocate an inode in cylinder group 0.
1106 * 2) quadratically rehash into other cylinder groups, until an
1107 * available inode is located.
1110 ffs_valloc(struct vnode *pvp,
1119 struct ufsmount *ump;
1122 int error, reclaimed;
1132 if (fs->fs_cstotal.cs_nifree == 0)
1135 if ((mode & IFMT) == IFDIR)
1136 ipref = ffs_dirpref(pip);
1138 ipref = pip->i_number;
1139 if (ipref >= fs->fs_ncg * fs->fs_ipg)
1141 cg = ino_to_cg(fs, ipref);
1143 * Track number of dirs created one after another
1144 * in a same cg without intervening by files.
1146 if ((mode & IFMT) == IFDIR) {
1147 if (fs->fs_contigdirs[cg] < 255)
1148 fs->fs_contigdirs[cg]++;
1150 if (fs->fs_contigdirs[cg] > 0)
1151 fs->fs_contigdirs[cg]--;
1153 ino = (ino_t)ffs_hashalloc(pip, cg, ipref, mode, 0,
1154 (allocfcn_t *)ffs_nodealloccg);
1158 * Get rid of the cached old vnode, force allocation of a new vnode
1159 * for this inode. If this fails, release the allocated ino and
1162 if ((error = ffs_vgetf(pvp->v_mount, ino, LK_EXCLUSIVE, vpp,
1163 FFSV_FORCEINSMQ | FFSV_REPLACE | FFSV_NEWINODE)) != 0) {
1164 ffs_vfree(pvp, ino, mode);
1168 * We got an inode, so check mode and panic if it is already allocated.
1172 printf("mode = 0%o, inum = %ju, fs = %s\n",
1173 ip->i_mode, (uintmax_t)ip->i_number, fs->fs_fsmnt);
1174 panic("ffs_valloc: dup alloc");
1176 if (DIP(ip, i_blocks) && (fs->fs_flags & FS_UNCLEAN) == 0) { /* XXX */
1177 printf("free inode %s/%ju had %ld blocks\n",
1178 fs->fs_fsmnt, (intmax_t)ino, (long)DIP(ip, i_blocks));
1179 DIP_SET(ip, i_blocks, 0);
1182 DIP_SET(ip, i_flags, 0);
1183 if ((mode & IFMT) == IFDIR)
1184 DIP_SET(ip, i_dirdepth, DIP(pip, i_dirdepth) + 1);
1186 * Set up a new generation number for this inode.
1188 while (ip->i_gen == 0 || ++ip->i_gen == 0)
1189 ip->i_gen = arc4random();
1190 DIP_SET(ip, i_gen, ip->i_gen);
1191 if (fs->fs_magic == FS_UFS2_MAGIC) {
1193 ip->i_din2->di_birthtime = ts.tv_sec;
1194 ip->i_din2->di_birthnsec = ts.tv_nsec;
1197 (*vpp)->v_vflag = 0;
1198 (*vpp)->v_type = VNON;
1199 if (fs->fs_magic == FS_UFS2_MAGIC) {
1200 (*vpp)->v_op = &ffs_vnodeops2;
1201 UFS_INODE_SET_FLAG(ip, IN_UFS2);
1203 (*vpp)->v_op = &ffs_vnodeops1;
1207 if (reclaimed == 0) {
1209 softdep_request_cleanup(fs, pvp, cred, FLUSH_INODES_WAIT);
1212 if (ffs_fsfail_cleanup_locked(ump, 0)) {
1216 if (ppsratecheck(&ump->um_last_fullmsg, &ump->um_secs_fullmsg, 1)) {
1218 ffs_fserr(fs, pip->i_number, "out of inodes");
1219 uprintf("\n%s: create/symlink failed, no inodes free\n",
1228 * Find a cylinder group to place a directory.
1230 * The policy implemented by this algorithm is to allocate a
1231 * directory inode in the same cylinder group as its parent
1232 * directory, but also to reserve space for its files inodes
1233 * and data. Restrict the number of directories which may be
1234 * allocated one after another in the same cylinder group
1235 * without intervening allocation of files.
1237 * If we allocate a first level directory then force allocation
1238 * in another cylinder group.
1241 ffs_dirpref(struct inode *pip)
1244 int cg, prefcg, curcg, dirsize, cgsize;
1245 int depth, range, start, end, numdirs, power, numerator, denominator;
1246 uint64_t avgifree, avgbfree, avgndir, curdirsize;
1247 uint64_t minifree, minbfree, maxndir;
1248 uint64_t maxcontigdirs;
1250 mtx_assert(UFS_MTX(ITOUMP(pip)), MA_OWNED);
1253 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg;
1254 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
1255 avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg;
1258 * Select a preferred cylinder group to place a new directory.
1259 * If we are near the root of the filesystem we aim to spread
1260 * them out as much as possible. As we descend deeper from the
1261 * root we cluster them closer together around their parent as
1262 * we expect them to be more closely interactive. Higher-level
1263 * directories like usr/src/sys and usr/src/bin should be
1264 * separated while the directories in these areas are more
1265 * likely to be accessed together so should be closer.
1267 * We pick a range of cylinder groups around the cylinder group
1268 * of the directory in which we are being created. The size of
1269 * the range for our search is based on our depth from the root
1270 * of our filesystem. We then probe that range based on how many
1271 * directories are already present. The first new directory is at
1272 * 1/2 (middle) of the range; the second is in the first 1/4 of the
1273 * range, then at 3/4, 1/8, 3/8, 5/8, 7/8, 1/16, 3/16, 5/16, etc.
1275 depth = DIP(pip, i_dirdepth);
1276 range = fs->fs_ncg / (1 << depth);
1277 curcg = ino_to_cg(fs, pip->i_number);
1278 start = curcg - (range / 2);
1280 start += fs->fs_ncg;
1281 end = curcg + (range / 2);
1282 if (end >= fs->fs_ncg)
1284 numdirs = pip->i_effnlink - 1;
1285 power = fls(numdirs);
1286 numerator = (numdirs & ~(1 << (power - 1))) * 2 + 1;
1287 denominator = 1 << power;
1288 prefcg = (curcg - (range / 2) + (range * numerator / denominator));
1290 prefcg += fs->fs_ncg;
1291 if (prefcg >= fs->fs_ncg)
1292 prefcg -= fs->fs_ncg;
1294 * If this filesystem is not tracking directory depths,
1295 * revert to the old algorithm.
1297 if (depth == 0 && pip->i_number != UFS_ROOTINO)
1301 * Count various limits which used for
1302 * optimal allocation of a directory inode.
1304 maxndir = min(avgndir + (1 << depth), fs->fs_ipg);
1305 minifree = avgifree - avgifree / 4;
1308 minbfree = avgbfree - avgbfree / 4;
1311 cgsize = fs->fs_fsize * fs->fs_fpg;
1312 dirsize = fs->fs_avgfilesize * fs->fs_avgfpdir;
1313 curdirsize = avgndir ? (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0;
1314 if (dirsize < curdirsize)
1315 dirsize = curdirsize;
1317 maxcontigdirs = 0; /* dirsize overflowed */
1319 maxcontigdirs = min((avgbfree * fs->fs_bsize) / dirsize, 255);
1320 if (fs->fs_avgfpdir > 0)
1321 maxcontigdirs = min(maxcontigdirs,
1322 fs->fs_ipg / fs->fs_avgfpdir);
1323 if (maxcontigdirs == 0)
1327 * Limit number of dirs in one cg and reserve space for
1328 * regular files, but only if we have no deficit in
1331 * We are trying to find a suitable cylinder group nearby
1332 * our preferred cylinder group to place a new directory.
1333 * We scan from our preferred cylinder group forward looking
1334 * for a cylinder group that meets our criterion. If we get
1335 * to the final cylinder group and do not find anything,
1336 * we start scanning forwards from the beginning of the
1337 * filesystem. While it might seem sensible to start scanning
1338 * backwards or even to alternate looking forward and backward,
1339 * this approach fails badly when the filesystem is nearly full.
1340 * Specifically, we first search all the areas that have no space
1341 * and finally try the one preceding that. We repeat this on
1342 * every request and in the case of the final block end up
1343 * searching the entire filesystem. By jumping to the front
1344 * of the filesystem, our future forward searches always look
1345 * in new cylinder groups so finds every possible block after
1346 * one pass over the filesystem.
1348 for (cg = prefcg; cg < fs->fs_ncg; cg++)
1349 if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
1350 fs->fs_cs(fs, cg).cs_nifree >= minifree &&
1351 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
1352 if (fs->fs_contigdirs[cg] < maxcontigdirs)
1353 return ((ino_t)(fs->fs_ipg * cg));
1355 for (cg = 0; cg < prefcg; cg++)
1356 if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
1357 fs->fs_cs(fs, cg).cs_nifree >= minifree &&
1358 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
1359 if (fs->fs_contigdirs[cg] < maxcontigdirs)
1360 return ((ino_t)(fs->fs_ipg * cg));
1363 * This is a backstop when we have deficit in space.
1365 for (cg = prefcg; cg < fs->fs_ncg; cg++)
1366 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
1367 return ((ino_t)(fs->fs_ipg * cg));
1368 for (cg = 0; cg < prefcg; cg++)
1369 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
1371 return ((ino_t)(fs->fs_ipg * cg));
1375 * Select the desired position for the next block in a file. The file is
1376 * logically divided into sections. The first section is composed of the
1377 * direct blocks and the next fs_maxbpg blocks. Each additional section
1378 * contains fs_maxbpg blocks.
1380 * If no blocks have been allocated in the first section, the policy is to
1381 * request a block in the same cylinder group as the inode that describes
1382 * the file. The first indirect is allocated immediately following the last
1383 * direct block and the data blocks for the first indirect immediately
1386 * If no blocks have been allocated in any other section, the indirect
1387 * block(s) are allocated in the same cylinder group as its inode in an
1388 * area reserved immediately following the inode blocks. The policy for
1389 * the data blocks is to place them in a cylinder group with a greater than
1390 * average number of free blocks. An appropriate cylinder group is found
1391 * by using a rotor that sweeps the cylinder groups. When a new group of
1392 * blocks is needed, the sweep begins in the cylinder group following the
1393 * cylinder group from which the previous allocation was made. The sweep
1394 * continues until a cylinder group with greater than the average number
1395 * of free blocks is found. If the allocation is for the first block in an
1396 * indirect block or the previous block is a hole, then the information on
1397 * the previous allocation is unavailable; here a best guess is made based
1398 * on the logical block number being allocated.
1400 * If a section is already partially allocated, the policy is to
1401 * allocate blocks contiguously within the section if possible.
1404 ffs_blkpref_ufs1(struct inode *ip,
1411 uint64_t avgbfree, startcg;
1412 ufs2_daddr_t pref, prevbn;
1414 KASSERT(indx <= 0 || bap != NULL, ("need non-NULL bap"));
1415 mtx_assert(UFS_MTX(ITOUMP(ip)), MA_OWNED);
1418 * Allocation of indirect blocks is indicated by passing negative
1419 * values in indx: -1 for single indirect, -2 for double indirect,
1420 * -3 for triple indirect. As noted below, we attempt to allocate
1421 * the first indirect inline with the file data. For all later
1422 * indirect blocks, the data is often allocated in other cylinder
1423 * groups. However to speed random file access and to speed up
1424 * fsck, the filesystem reserves the first fs_metaspace blocks
1425 * (typically half of fs_minfree) of the data area of each cylinder
1426 * group to hold these later indirect blocks.
1428 inocg = ino_to_cg(fs, ip->i_number);
1431 * Our preference for indirect blocks is the zone at the
1432 * beginning of the inode's cylinder group data area that
1433 * we try to reserve for indirect blocks.
1435 pref = cgmeta(fs, inocg);
1437 * If we are allocating the first indirect block, try to
1438 * place it immediately following the last direct block.
1440 if (indx == -1 && lbn < UFS_NDADDR + NINDIR(fs) &&
1441 ip->i_din1->di_db[UFS_NDADDR - 1] != 0)
1442 pref = ip->i_din1->di_db[UFS_NDADDR - 1] + fs->fs_frag;
1446 * If we are allocating the first data block in the first indirect
1447 * block and the indirect has been allocated in the data block area,
1448 * try to place it immediately following the indirect block.
1450 if (lbn == UFS_NDADDR) {
1451 pref = ip->i_din1->di_ib[0];
1452 if (pref != 0 && pref >= cgdata(fs, inocg) &&
1453 pref < cgbase(fs, inocg + 1))
1454 return (pref + fs->fs_frag);
1457 * If we are at the beginning of a file, or we have already allocated
1458 * the maximum number of blocks per cylinder group, or we do not
1459 * have a block allocated immediately preceding us, then we need
1460 * to decide where to start allocating new blocks.
1465 prevbn = bap[indx - 1];
1466 if (UFS_CHECK_BLKNO(ITOVFS(ip), ip->i_number, prevbn,
1470 if (indx % fs->fs_maxbpg == 0 || prevbn == 0) {
1472 * If we are allocating a directory data block, we want
1473 * to place it in the metadata area.
1475 if ((ip->i_mode & IFMT) == IFDIR)
1476 return (cgmeta(fs, inocg));
1478 * Until we fill all the direct and all the first indirect's
1479 * blocks, we try to allocate in the data area of the inode's
1482 if (lbn < UFS_NDADDR + NINDIR(fs))
1483 return (cgdata(fs, inocg));
1485 * Find a cylinder with greater than average number of
1486 * unused data blocks.
1488 if (indx == 0 || prevbn == 0)
1489 startcg = inocg + lbn / fs->fs_maxbpg;
1491 startcg = dtog(fs, prevbn) + 1;
1492 startcg %= fs->fs_ncg;
1493 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
1494 for (cg = startcg; cg < fs->fs_ncg; cg++)
1495 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
1496 fs->fs_cgrotor = cg;
1497 return (cgdata(fs, cg));
1499 for (cg = 0; cg <= startcg; cg++)
1500 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
1501 fs->fs_cgrotor = cg;
1502 return (cgdata(fs, cg));
1507 * Otherwise, we just always try to lay things out contiguously.
1509 return (prevbn + fs->fs_frag);
1513 * Same as above, but for UFS2
1516 ffs_blkpref_ufs2(struct inode *ip,
1523 uint64_t avgbfree, startcg;
1524 ufs2_daddr_t pref, prevbn;
1526 KASSERT(indx <= 0 || bap != NULL, ("need non-NULL bap"));
1527 mtx_assert(UFS_MTX(ITOUMP(ip)), MA_OWNED);
1530 * Allocation of indirect blocks is indicated by passing negative
1531 * values in indx: -1 for single indirect, -2 for double indirect,
1532 * -3 for triple indirect. As noted below, we attempt to allocate
1533 * the first indirect inline with the file data. For all later
1534 * indirect blocks, the data is often allocated in other cylinder
1535 * groups. However to speed random file access and to speed up
1536 * fsck, the filesystem reserves the first fs_metaspace blocks
1537 * (typically half of fs_minfree) of the data area of each cylinder
1538 * group to hold these later indirect blocks.
1540 inocg = ino_to_cg(fs, ip->i_number);
1543 * Our preference for indirect blocks is the zone at the
1544 * beginning of the inode's cylinder group data area that
1545 * we try to reserve for indirect blocks.
1547 pref = cgmeta(fs, inocg);
1549 * If we are allocating the first indirect block, try to
1550 * place it immediately following the last direct block.
1552 if (indx == -1 && lbn < UFS_NDADDR + NINDIR(fs) &&
1553 ip->i_din2->di_db[UFS_NDADDR - 1] != 0)
1554 pref = ip->i_din2->di_db[UFS_NDADDR - 1] + fs->fs_frag;
1558 * If we are allocating the first data block in the first indirect
1559 * block and the indirect has been allocated in the data block area,
1560 * try to place it immediately following the indirect block.
1562 if (lbn == UFS_NDADDR) {
1563 pref = ip->i_din2->di_ib[0];
1564 if (pref != 0 && pref >= cgdata(fs, inocg) &&
1565 pref < cgbase(fs, inocg + 1))
1566 return (pref + fs->fs_frag);
1569 * If we are at the beginning of a file, or we have already allocated
1570 * the maximum number of blocks per cylinder group, or we do not
1571 * have a block allocated immediately preceding us, then we need
1572 * to decide where to start allocating new blocks.
1577 prevbn = bap[indx - 1];
1578 if (UFS_CHECK_BLKNO(ITOVFS(ip), ip->i_number, prevbn,
1582 if (indx % fs->fs_maxbpg == 0 || prevbn == 0) {
1584 * If we are allocating a directory data block, we want
1585 * to place it in the metadata area.
1587 if ((ip->i_mode & IFMT) == IFDIR)
1588 return (cgmeta(fs, inocg));
1590 * Until we fill all the direct and all the first indirect's
1591 * blocks, we try to allocate in the data area of the inode's
1594 if (lbn < UFS_NDADDR + NINDIR(fs))
1595 return (cgdata(fs, inocg));
1597 * Find a cylinder with greater than average number of
1598 * unused data blocks.
1600 if (indx == 0 || prevbn == 0)
1601 startcg = inocg + lbn / fs->fs_maxbpg;
1603 startcg = dtog(fs, prevbn) + 1;
1604 startcg %= fs->fs_ncg;
1605 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
1606 for (cg = startcg; cg < fs->fs_ncg; cg++)
1607 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
1608 fs->fs_cgrotor = cg;
1609 return (cgdata(fs, cg));
1611 for (cg = 0; cg <= startcg; cg++)
1612 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
1613 fs->fs_cgrotor = cg;
1614 return (cgdata(fs, cg));
1619 * Otherwise, we just always try to lay things out contiguously.
1621 return (prevbn + fs->fs_frag);
1625 * Implement the cylinder overflow algorithm.
1627 * The policy implemented by this algorithm is:
1628 * 1) allocate the block in its requested cylinder group.
1629 * 2) quadratically rehash on the cylinder group number.
1630 * 3) brute force search for a free block.
1632 * Must be called with the UFS lock held. Will release the lock on success
1633 * and return with it held on failure.
1637 ffs_hashalloc(struct inode *ip,
1640 int size, /* Search size for data blocks, mode for inodes */
1641 int rsize, /* Real allocated size. */
1642 allocfcn_t *allocator)
1645 ufs2_daddr_t result;
1646 uint64_t i, icg = cg;
1648 mtx_assert(UFS_MTX(ITOUMP(ip)), MA_OWNED);
1650 if (ITOV(ip)->v_mount->mnt_kern_flag & MNTK_SUSPENDED)
1651 panic("ffs_hashalloc: allocation on suspended filesystem");
1655 * 1: preferred cylinder group
1657 result = (*allocator)(ip, cg, pref, size, rsize);
1661 * 2: quadratic rehash
1663 for (i = 1; i < fs->fs_ncg; i *= 2) {
1665 if (cg >= fs->fs_ncg)
1667 result = (*allocator)(ip, cg, 0, size, rsize);
1672 * 3: brute force search
1673 * Note that we start at i == 2, since 0 was checked initially,
1674 * and 1 is always checked in the quadratic rehash.
1676 cg = (icg + 2) % fs->fs_ncg;
1677 for (i = 2; i < fs->fs_ncg; i++) {
1678 result = (*allocator)(ip, cg, 0, size, rsize);
1682 if (cg == fs->fs_ncg)
1689 * Determine whether a fragment can be extended.
1691 * Check to see if the necessary fragments are available, and
1692 * if they are, allocate them.
1695 ffs_fragextend(struct inode *ip,
1704 struct ufsmount *ump;
1713 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize))
1715 frags = numfrags(fs, nsize);
1716 bbase = fragnum(fs, bprev);
1717 if (bbase > fragnum(fs, (bprev + frags - 1))) {
1718 /* cannot extend across a block boundary */
1722 if ((error = ffs_getcg(fs, ump->um_devvp, cg, 0, &bp, &cgp)) != 0) {
1723 ffs_checkcgintegrity(fs, cg, error);
1726 bno = dtogd(fs, bprev);
1727 blksfree = cg_blksfree(cgp);
1728 for (i = numfrags(fs, osize); i < frags; i++)
1729 if (isclr(blksfree, bno + i))
1732 * the current fragment can be extended
1733 * deduct the count on fragment being extended into
1734 * increase the count on the remaining fragment (if any)
1735 * allocate the extended piece
1737 for (i = frags; i < fs->fs_frag - bbase; i++)
1738 if (isclr(blksfree, bno + i))
1740 cgp->cg_frsum[i - numfrags(fs, osize)]--;
1742 cgp->cg_frsum[i - frags]++;
1743 for (i = numfrags(fs, osize), nffree = 0; i < frags; i++) {
1744 clrbit(blksfree, bno + i);
1745 cgp->cg_cs.cs_nffree--;
1749 fs->fs_cstotal.cs_nffree -= nffree;
1750 fs->fs_cs(fs, cg).cs_nffree -= nffree;
1752 ACTIVECLEAR(fs, cg);
1754 if (DOINGSOFTDEP(ITOV(ip)))
1755 softdep_setup_blkmapdep(bp, UFSTOVFS(ump), bprev,
1756 frags, numfrags(fs, osize));
1768 * Determine whether a block can be allocated.
1770 * Check to see if a block of the appropriate size is available,
1771 * and if it is, allocate it.
1774 ffs_alloccg(struct inode *ip,
1783 struct ufsmount *ump;
1786 int i, allocsiz, error, frags;
1791 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize)
1794 if ((error = ffs_getcg(fs, ump->um_devvp, cg, 0, &bp, &cgp)) != 0 ||
1795 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) {
1796 ffs_checkcgintegrity(fs, cg, error);
1799 if (size == fs->fs_bsize) {
1801 blkno = ffs_alloccgblk(ip, bp, bpref, rsize);
1802 ACTIVECLEAR(fs, cg);
1808 * check to see if any fragments are already available
1809 * allocsiz is the size which will be allocated, hacking
1810 * it down to a smaller size if necessary
1812 blksfree = cg_blksfree(cgp);
1813 frags = numfrags(fs, size);
1814 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++)
1815 if (cgp->cg_frsum[allocsiz] != 0)
1817 if (allocsiz == fs->fs_frag) {
1819 * no fragments were available, so a block will be
1820 * allocated, and hacked up
1822 if (cgp->cg_cs.cs_nbfree == 0)
1825 blkno = ffs_alloccgblk(ip, bp, bpref, rsize);
1826 ACTIVECLEAR(fs, cg);
1831 KASSERT(size == rsize,
1832 ("ffs_alloccg: size(%d) != rsize(%d)", size, rsize));
1833 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz);
1836 for (i = 0; i < frags; i++)
1837 clrbit(blksfree, bno + i);
1838 cgp->cg_cs.cs_nffree -= frags;
1839 cgp->cg_frsum[allocsiz]--;
1840 if (frags != allocsiz)
1841 cgp->cg_frsum[allocsiz - frags]++;
1843 fs->fs_cstotal.cs_nffree -= frags;
1844 fs->fs_cs(fs, cg).cs_nffree -= frags;
1846 blkno = cgbase(fs, cg) + bno;
1847 ACTIVECLEAR(fs, cg);
1849 if (DOINGSOFTDEP(ITOV(ip)))
1850 softdep_setup_blkmapdep(bp, UFSTOVFS(ump), blkno, frags, 0);
1861 * Allocate a block in a cylinder group.
1863 * This algorithm implements the following policy:
1864 * 1) allocate the requested block.
1865 * 2) allocate a rotationally optimal block in the same cylinder.
1866 * 3) allocate the next available block on the block rotor for the
1867 * specified cylinder group.
1868 * Note that this routine only allocates fs_bsize blocks; these
1869 * blocks may be fragmented by the routine that allocates them.
1872 ffs_alloccgblk(struct inode *ip,
1879 struct ufsmount *ump;
1887 mtx_assert(UFS_MTX(ump), MA_OWNED);
1888 cgp = (struct cg *)bp->b_data;
1889 blksfree = cg_blksfree(cgp);
1891 bpref = cgbase(fs, cgp->cg_cgx) + cgp->cg_rotor + fs->fs_frag;
1892 } else if ((cgbpref = dtog(fs, bpref)) != cgp->cg_cgx) {
1893 /* map bpref to correct zone in this cg */
1894 if (bpref < cgdata(fs, cgbpref))
1895 bpref = cgmeta(fs, cgp->cg_cgx);
1897 bpref = cgdata(fs, cgp->cg_cgx);
1900 * if the requested block is available, use it
1902 bno = dtogd(fs, blknum(fs, bpref));
1903 if (ffs_isblock(fs, blksfree, fragstoblks(fs, bno)))
1906 * Take the next available block in this cylinder group.
1908 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag);
1911 /* Update cg_rotor only if allocated from the data zone */
1912 if (bno >= dtogd(fs, cgdata(fs, cgp->cg_cgx)))
1913 cgp->cg_rotor = bno;
1915 blkno = fragstoblks(fs, bno);
1916 ffs_clrblock(fs, blksfree, (long)blkno);
1917 ffs_clusteracct(fs, cgp, blkno, -1);
1918 cgp->cg_cs.cs_nbfree--;
1919 fs->fs_cstotal.cs_nbfree--;
1920 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--;
1922 blkno = cgbase(fs, cgp->cg_cgx) + bno;
1924 * If the caller didn't want the whole block free the frags here.
1926 size = numfrags(fs, size);
1927 if (size != fs->fs_frag) {
1928 bno = dtogd(fs, blkno);
1929 for (i = size; i < fs->fs_frag; i++)
1930 setbit(blksfree, bno + i);
1931 i = fs->fs_frag - size;
1932 cgp->cg_cs.cs_nffree += i;
1933 fs->fs_cstotal.cs_nffree += i;
1934 fs->fs_cs(fs, cgp->cg_cgx).cs_nffree += i;
1940 if (DOINGSOFTDEP(ITOV(ip)))
1941 softdep_setup_blkmapdep(bp, UFSTOVFS(ump), blkno, size, 0);
1947 * Determine whether a cluster can be allocated.
1949 * We do not currently check for optimal rotational layout if there
1950 * are multiple choices in the same cylinder group. Instead we just
1951 * take the first one that we find following bpref.
1954 ffs_clusteralloc(struct inode *ip,
1962 struct ufsmount *ump;
1963 int i, run, bit, map, got, error;
1971 if (fs->fs_maxcluster[cg] < len)
1974 if ((error = ffs_getcg(fs, ump->um_devvp, cg, 0, &bp, &cgp)) != 0) {
1975 ffs_checkcgintegrity(fs, cg, error);
1980 * Check to see if a cluster of the needed size (or bigger) is
1981 * available in this cylinder group.
1983 lp = &cg_clustersum(cgp)[len];
1984 for (i = len; i <= fs->fs_contigsumsize; i++)
1987 if (i > fs->fs_contigsumsize) {
1989 * This is the first time looking for a cluster in this
1990 * cylinder group. Update the cluster summary information
1991 * to reflect the true maximum sized cluster so that
1992 * future cluster allocation requests can avoid reading
1993 * the cylinder group map only to find no clusters.
1995 lp = &cg_clustersum(cgp)[len - 1];
1996 for (i = len - 1; i > 0; i--)
2000 fs->fs_maxcluster[cg] = i;
2005 * Search the cluster map to find a big enough cluster.
2006 * We take the first one that we find, even if it is larger
2007 * than we need as we prefer to get one close to the previous
2008 * block allocation. We do not search before the current
2009 * preference point as we do not want to allocate a block
2010 * that is allocated before the previous one (as we will
2011 * then have to wait for another pass of the elevator
2012 * algorithm before it will be read). We prefer to fail and
2013 * be recalled to try an allocation in the next cylinder group.
2015 if (dtog(fs, bpref) != cg)
2016 bpref = cgdata(fs, cg);
2018 bpref = blknum(fs, bpref);
2019 bpref = fragstoblks(fs, dtogd(fs, bpref));
2020 mapp = &cg_clustersfree(cgp)[bpref / NBBY];
2022 bit = 1 << (bpref % NBBY);
2023 for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) {
2024 if ((map & bit) == 0) {
2031 if ((got & (NBBY - 1)) != (NBBY - 1)) {
2038 if (got >= cgp->cg_nclusterblks) {
2044 * Allocate the cluster that we have found.
2046 blksfree = cg_blksfree(cgp);
2047 for (i = 1; i <= len; i++)
2048 if (!ffs_isblock(fs, blksfree, got - run + i))
2049 panic("ffs_clusteralloc: map mismatch");
2050 bno = cgbase(fs, cg) + blkstofrags(fs, got - run + 1);
2051 if (dtog(fs, bno) != cg)
2052 panic("ffs_clusteralloc: allocated out of group");
2053 len = blkstofrags(fs, len);
2055 for (i = 0; i < len; i += fs->fs_frag)
2056 if (ffs_alloccgblk(ip, bp, bno + i, fs->fs_bsize) != bno + i)
2057 panic("ffs_clusteralloc: lost block");
2058 ACTIVECLEAR(fs, cg);
2064 static inline struct buf *
2065 getinobuf(struct inode *ip,
2073 return (getblk(ITODEVVP(ip), fsbtodb(fs, ino_to_fsba(fs,
2074 cg * fs->fs_ipg + cginoblk)), (int)fs->fs_bsize, 0, 0,
2079 * Synchronous inode initialization is needed only when barrier writes do not
2080 * work as advertised, and will impose a heavy cost on file creation in a newly
2081 * created filesystem.
2083 static int doasyncinodeinit = 1;
2084 SYSCTL_INT(_vfs_ffs, OID_AUTO, doasyncinodeinit, CTLFLAG_RWTUN,
2085 &doasyncinodeinit, 0,
2086 "Perform inode block initialization using asynchronous writes");
2089 * Determine whether an inode can be allocated.
2091 * Check to see if an inode is available, and if it is,
2092 * allocate it using the following policy:
2093 * 1) allocate the requested inode.
2094 * 2) allocate the next available inode after the requested
2095 * inode in the specified cylinder group.
2098 ffs_nodealloccg(struct inode *ip,
2106 struct buf *bp, *ibp;
2107 struct ufsmount *ump;
2108 uint8_t *inosused, *loc;
2109 struct ufs2_dinode *dp2;
2110 int error, start, len, i;
2111 uint32_t old_initediblk;
2116 if (fs->fs_cs(fs, cg).cs_nifree == 0)
2119 if ((error = ffs_getcg(fs, ump->um_devvp, cg, 0, &bp, &cgp)) != 0) {
2120 ffs_checkcgintegrity(fs, cg, error);
2125 if (cgp->cg_cs.cs_nifree == 0) {
2130 inosused = cg_inosused(cgp);
2132 ipref %= fs->fs_ipg;
2133 if (isclr(inosused, ipref))
2136 start = cgp->cg_irotor / NBBY;
2137 len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY);
2138 loc = memcchr(&inosused[start], 0xff, len);
2142 loc = memcchr(&inosused[start], 0xff, len);
2144 printf("cg = %ju, irotor = %ld, fs = %s\n",
2145 (intmax_t)cg, (long)cgp->cg_irotor, fs->fs_fsmnt);
2146 panic("ffs_nodealloccg: map corrupted");
2150 ipref = (loc - inosused) * NBBY + ffs(~*loc) - 1;
2153 * Check to see if we need to initialize more inodes.
2155 if (fs->fs_magic == FS_UFS2_MAGIC &&
2156 ipref + INOPB(fs) > cgp->cg_initediblk &&
2157 cgp->cg_initediblk < cgp->cg_niblk) {
2158 old_initediblk = cgp->cg_initediblk;
2161 * Free the cylinder group lock before writing the
2162 * initialized inode block. Entering the
2163 * babarrierwrite() with the cylinder group lock
2164 * causes lock order violation between the lock and
2167 * Another thread can decide to initialize the same
2168 * inode block, but whichever thread first gets the
2169 * cylinder group lock after writing the newly
2170 * allocated inode block will update it and the other
2171 * will realize that it has lost and leave the
2172 * cylinder group unchanged.
2174 ibp = getinobuf(ip, cg, old_initediblk, GB_LOCK_NOWAIT);
2178 * The inode block buffer is already owned by
2179 * another thread, which must initialize it.
2180 * Wait on the buffer to allow another thread
2181 * to finish the updates, with dropped cg
2182 * buffer lock, then retry.
2184 ibp = getinobuf(ip, cg, old_initediblk, 0);
2189 bzero(ibp->b_data, (int)fs->fs_bsize);
2190 dp2 = (struct ufs2_dinode *)(ibp->b_data);
2191 for (i = 0; i < INOPB(fs); i++) {
2192 while (dp2->di_gen == 0)
2193 dp2->di_gen = arc4random();
2198 * Rather than adding a soft updates dependency to ensure
2199 * that the new inode block is written before it is claimed
2200 * by the cylinder group map, we just do a barrier write
2201 * here. The barrier write will ensure that the inode block
2202 * gets written before the updated cylinder group map can be
2203 * written. The barrier write should only slow down bulk
2204 * loading of newly created filesystems.
2206 if (doasyncinodeinit)
2207 babarrierwrite(ibp);
2212 * After the inode block is written, try to update the
2213 * cg initediblk pointer. If another thread beat us
2214 * to it, then leave it unchanged as the other thread
2215 * has already set it correctly.
2217 error = ffs_getcg(fs, ump->um_devvp, cg, 0, &bp, &cgp);
2219 ACTIVECLEAR(fs, cg);
2223 if (cgp->cg_initediblk == old_initediblk)
2224 cgp->cg_initediblk += INOPB(fs);
2227 cgp->cg_irotor = ipref;
2229 ACTIVECLEAR(fs, cg);
2230 setbit(inosused, ipref);
2231 cgp->cg_cs.cs_nifree--;
2232 fs->fs_cstotal.cs_nifree--;
2233 fs->fs_cs(fs, cg).cs_nifree--;
2235 if ((mode & IFMT) == IFDIR) {
2236 cgp->cg_cs.cs_ndir++;
2237 fs->fs_cstotal.cs_ndir++;
2238 fs->fs_cs(fs, cg).cs_ndir++;
2241 if (DOINGSOFTDEP(ITOV(ip)))
2242 softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref, mode);
2244 return ((ino_t)(cg * fs->fs_ipg + ipref));
2248 * Free a block or fragment.
2250 * The specified block or fragment is placed back in the
2251 * free map. If a fragment is deallocated, a possible
2252 * block reassembly is checked.
2255 ffs_blkfree_cg(struct ufsmount *ump,
2257 struct vnode *devvp,
2261 struct workhead *dephd)
2267 ufs1_daddr_t fragno, cgbno;
2268 int i, blk, frags, bbase, error;
2274 if (devvp->v_type == VREG) {
2275 /* devvp is a snapshot */
2276 MPASS(devvp->v_mount->mnt_data == ump);
2277 dev = ump->um_devvp->v_rdev;
2278 } else if (devvp->v_type == VCHR) {
2280 * devvp is a normal disk device
2281 * XXXKIB: devvp is not locked there, v_rdev access depends on
2282 * busy mount, which prevents mntfs devvp from reclamation.
2284 dev = devvp->v_rdev;
2288 if ((uint64_t)size > fs->fs_bsize || fragoff(fs, size) != 0 ||
2289 fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) {
2290 printf("dev=%s, bno = %jd, bsize = %ld, size = %ld, fs = %s\n",
2291 devtoname(dev), (intmax_t)bno, (long)fs->fs_bsize,
2292 size, fs->fs_fsmnt);
2293 panic("ffs_blkfree_cg: invalid size");
2296 if ((uint64_t)bno >= fs->fs_size) {
2297 printf("bad block %jd, ino %ju\n", (intmax_t)bno,
2299 ffs_fserr(fs, inum, "bad block");
2302 if ((error = ffs_getcg(fs, devvp, cg, GB_CVTENXIO, &bp, &cgp)) != 0) {
2303 if (!MOUNTEDSOFTDEP(UFSTOVFS(ump)) || devvp->v_type != VCHR)
2306 * Would like to just downgrade to read-only. Until that
2307 * capability is available, just toss the cylinder group
2308 * update and mark the filesystem as needing to run fsck.
2310 fs->fs_flags |= FS_NEEDSFSCK;
2311 if (devvp->v_type == VREG)
2312 dbn = fragstoblks(fs, cgtod(fs, cg));
2314 dbn = fsbtodb(fs, cgtod(fs, cg));
2315 error = getblkx(devvp, dbn, dbn, fs->fs_cgsize, 0, 0, 0, &bp);
2316 KASSERT(error == 0, ("getblkx failed"));
2317 softdep_setup_blkfree(UFSTOVFS(ump), bp, bno,
2318 numfrags(fs, size), dephd, true);
2319 bp->b_flags |= B_RELBUF | B_NOCACHE;
2320 bp->b_flags &= ~B_CACHE;
2324 cgbno = dtogd(fs, bno);
2325 blksfree = cg_blksfree(cgp);
2327 if (size == fs->fs_bsize) {
2328 fragno = fragstoblks(fs, cgbno);
2329 if (!ffs_isfreeblock(fs, blksfree, fragno)) {
2330 if (devvp->v_type == VREG) {
2332 /* devvp is a snapshot */
2336 printf("dev = %s, block = %jd, fs = %s\n",
2337 devtoname(dev), (intmax_t)bno, fs->fs_fsmnt);
2338 panic("ffs_blkfree_cg: freeing free block");
2340 ffs_setblock(fs, blksfree, fragno);
2341 ffs_clusteracct(fs, cgp, fragno, 1);
2342 cgp->cg_cs.cs_nbfree++;
2343 fs->fs_cstotal.cs_nbfree++;
2344 fs->fs_cs(fs, cg).cs_nbfree++;
2346 bbase = cgbno - fragnum(fs, cgbno);
2348 * decrement the counts associated with the old frags
2350 blk = blkmap(fs, blksfree, bbase);
2351 ffs_fragacct(fs, blk, cgp->cg_frsum, -1);
2353 * deallocate the fragment
2355 frags = numfrags(fs, size);
2356 for (i = 0; i < frags; i++) {
2357 if (isset(blksfree, cgbno + i)) {
2358 printf("dev = %s, block = %jd, fs = %s\n",
2359 devtoname(dev), (intmax_t)(bno + i),
2361 panic("ffs_blkfree_cg: freeing free frag");
2363 setbit(blksfree, cgbno + i);
2365 cgp->cg_cs.cs_nffree += i;
2366 fs->fs_cstotal.cs_nffree += i;
2367 fs->fs_cs(fs, cg).cs_nffree += i;
2369 * add back in counts associated with the new frags
2371 blk = blkmap(fs, blksfree, bbase);
2372 ffs_fragacct(fs, blk, cgp->cg_frsum, 1);
2374 * if a complete block has been reassembled, account for it
2376 fragno = fragstoblks(fs, bbase);
2377 if (ffs_isblock(fs, blksfree, fragno)) {
2378 cgp->cg_cs.cs_nffree -= fs->fs_frag;
2379 fs->fs_cstotal.cs_nffree -= fs->fs_frag;
2380 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
2381 ffs_clusteracct(fs, cgp, fragno, 1);
2382 cgp->cg_cs.cs_nbfree++;
2383 fs->fs_cstotal.cs_nbfree++;
2384 fs->fs_cs(fs, cg).cs_nbfree++;
2388 ACTIVECLEAR(fs, cg);
2391 if (MOUNTEDSOFTDEP(mp) && devvp->v_type == VCHR)
2392 softdep_setup_blkfree(UFSTOVFS(ump), bp, bno,
2393 numfrags(fs, size), dephd, false);
2398 * Structures and routines associated with trim management.
2400 * The following requests are passed to trim_lookup to indicate
2401 * the actions that should be taken.
2403 #define NEW 1 /* if found, error else allocate and hash it */
2404 #define OLD 2 /* if not found, error, else return it */
2405 #define REPLACE 3 /* if not found, error else unhash and reallocate it */
2406 #define DONE 4 /* if not found, error else unhash and return it */
2407 #define SINGLE 5 /* don't look up, just allocate it and don't hash it */
2409 MALLOC_DEFINE(M_TRIM, "ufs_trim", "UFS trim structures");
2411 #define TRIMLIST_HASH(ump, key) \
2412 (&(ump)->um_trimhash[(key) & (ump)->um_trimlisthashsize])
2415 * These structures describe each of the block free requests aggregated
2416 * together to make up a trim request.
2418 struct trim_blkreq {
2419 TAILQ_ENTRY(trim_blkreq) blkreqlist;
2422 struct workhead *pdephd;
2423 struct workhead dephd;
2427 * Description of a trim request.
2429 struct ffs_blkfree_trim_params {
2430 TAILQ_HEAD(, trim_blkreq) blklist;
2431 LIST_ENTRY(ffs_blkfree_trim_params) hashlist;
2433 struct ufsmount *ump;
2434 struct vnode *devvp;
2441 static void ffs_blkfree_trim_completed(struct buf *);
2442 static void ffs_blkfree_trim_task(void *ctx, int pending __unused);
2443 static struct ffs_blkfree_trim_params *trim_lookup(struct ufsmount *,
2444 struct vnode *, ufs2_daddr_t, long, ino_t, uint64_t, int);
2445 static void ffs_blkfree_sendtrim(struct ffs_blkfree_trim_params *);
2448 * Called on trim completion to start a task to free the associated block(s).
2451 ffs_blkfree_trim_completed(struct buf *bp)
2453 struct ffs_blkfree_trim_params *tp;
2455 tp = bp->b_fsprivate1;
2457 TASK_INIT(&tp->task, 0, ffs_blkfree_trim_task, tp);
2458 taskqueue_enqueue(tp->ump->um_trim_tq, &tp->task);
2462 * Trim completion task that free associated block(s).
2465 ffs_blkfree_trim_task(void *ctx, int pending)
2467 struct ffs_blkfree_trim_params *tp;
2468 struct trim_blkreq *blkelm;
2469 struct ufsmount *ump;
2473 while ((blkelm = TAILQ_FIRST(&tp->blklist)) != NULL) {
2474 ffs_blkfree_cg(ump, ump->um_fs, tp->devvp, blkelm->bno,
2475 blkelm->size, tp->inum, blkelm->pdephd);
2476 TAILQ_REMOVE(&tp->blklist, blkelm, blkreqlist);
2477 free(blkelm, M_TRIM);
2479 vn_finished_secondary_write(UFSTOVFS(ump));
2481 ump->um_trim_inflight -= 1;
2482 ump->um_trim_inflight_blks -= numfrags(ump->um_fs, tp->size);
2488 * Lookup a trim request by inode number.
2489 * Allocate if requested (NEW, REPLACE, SINGLE).
2491 static struct ffs_blkfree_trim_params *
2492 trim_lookup(struct ufsmount *ump,
2493 struct vnode *devvp,
2500 struct trimlist_hashhead *tphashhead;
2501 struct ffs_blkfree_trim_params *tp, *ntp;
2503 ntp = malloc(sizeof(struct ffs_blkfree_trim_params), M_TRIM, M_WAITOK);
2504 if (alloctype != SINGLE) {
2505 KASSERT(key >= FIRST_VALID_KEY, ("trim_lookup: invalid key"));
2507 tphashhead = TRIMLIST_HASH(ump, key);
2508 LIST_FOREACH(tp, tphashhead, hashlist)
2512 switch (alloctype) {
2514 KASSERT(tp == NULL, ("trim_lookup: found trim"));
2518 ("trim_lookup: missing call to ffs_blkrelease_start()"));
2523 KASSERT(tp != NULL, ("trim_lookup: missing REPLACE trim"));
2524 LIST_REMOVE(tp, hashlist);
2525 /* tp will be freed by caller */
2528 KASSERT(tp != NULL, ("trim_lookup: missing DONE trim"));
2529 LIST_REMOVE(tp, hashlist);
2534 TAILQ_INIT(&ntp->blklist);
2541 if (alloctype != SINGLE) {
2542 LIST_INSERT_HEAD(tphashhead, ntp, hashlist);
2549 * Dispatch a trim request.
2552 ffs_blkfree_sendtrim(struct ffs_blkfree_trim_params *tp)
2554 struct ufsmount *ump;
2559 * Postpone the set of the free bit in the cg bitmap until the
2560 * BIO_DELETE is completed. Otherwise, due to disk queue
2561 * reordering, TRIM might be issued after we reuse the block
2562 * and write some new data into it.
2565 bp = malloc(sizeof(*bp), M_TRIM, M_WAITOK | M_ZERO);
2566 bp->b_iocmd = BIO_DELETE;
2567 bp->b_iooffset = dbtob(fsbtodb(ump->um_fs, tp->bno));
2568 bp->b_iodone = ffs_blkfree_trim_completed;
2569 bp->b_bcount = tp->size;
2570 bp->b_fsprivate1 = tp;
2572 ump->um_trim_total += 1;
2573 ump->um_trim_inflight += 1;
2574 ump->um_trim_inflight_blks += numfrags(ump->um_fs, tp->size);
2575 ump->um_trim_total_blks += numfrags(ump->um_fs, tp->size);
2579 vn_start_secondary_write(NULL, &mp, 0);
2580 g_vfs_strategy(ump->um_bo, bp);
2584 * Allocate a new key to use to identify a range of blocks.
2587 ffs_blkrelease_start(struct ufsmount *ump,
2588 struct vnode *devvp,
2591 static u_long masterkey;
2594 if (((ump->um_flags & UM_CANDELETE) == 0) || dotrimcons == 0)
2595 return (SINGLETON_KEY);
2597 key = atomic_fetchadd_long(&masterkey, 1);
2598 } while (key < FIRST_VALID_KEY);
2599 (void) trim_lookup(ump, devvp, 0, 0, inum, key, NEW);
2604 * Deallocate a key that has been used to identify a range of blocks.
2607 ffs_blkrelease_finish(struct ufsmount *ump, uint64_t key)
2609 struct ffs_blkfree_trim_params *tp;
2611 if (((ump->um_flags & UM_CANDELETE) == 0) || dotrimcons == 0)
2614 * If the vfs.ffs.dotrimcons sysctl option is enabled while
2615 * a file deletion is active, specifically after a call
2616 * to ffs_blkrelease_start() but before the call to
2617 * ffs_blkrelease_finish(), ffs_blkrelease_start() will
2618 * have handed out SINGLETON_KEY rather than starting a
2619 * collection sequence. Thus if we get a SINGLETON_KEY
2620 * passed to ffs_blkrelease_finish(), we just return rather
2621 * than trying to finish the nonexistent sequence.
2623 if (key == SINGLETON_KEY) {
2625 printf("%s: vfs.ffs.dotrimcons enabled on active filesystem\n",
2626 ump->um_mountp->mnt_stat.f_mntonname);
2631 * We are done with sending blocks using this key. Look up the key
2632 * using the DONE alloctype (in tp) to request that it be unhashed
2633 * as we will not be adding to it. If the key has never been used,
2634 * tp->size will be zero, so we can just free tp. Otherwise the call
2635 * to ffs_blkfree_sendtrim(tp) causes the block range described by
2636 * tp to be issued (and then tp to be freed).
2638 tp = trim_lookup(ump, NULL, 0, 0, 0, key, DONE);
2642 ffs_blkfree_sendtrim(tp);
2646 * Setup to free a block or fragment.
2648 * Check for snapshots that might want to claim the block.
2649 * If trims are requested, prepare a trim request. Attempt to
2650 * aggregate consecutive blocks into a single trim request.
2653 ffs_blkfree(struct ufsmount *ump,
2655 struct vnode *devvp,
2659 __enum_uint8(vtype) vtype,
2660 struct workhead *dephd,
2663 struct ffs_blkfree_trim_params *tp, *ntp;
2664 struct trim_blkreq *blkelm;
2667 * Check to see if a snapshot wants to claim the block.
2668 * Check that devvp is a normal disk device, not a snapshot,
2669 * it has a snapshot(s) associated with it, and one of the
2670 * snapshots wants to claim the block.
2672 if (devvp->v_type == VCHR &&
2673 (devvp->v_vflag & VV_COPYONWRITE) &&
2674 ffs_snapblkfree(fs, devvp, bno, size, inum, vtype, dephd)) {
2678 * Nothing to delay if TRIM is not required for this block or TRIM
2679 * is disabled or the operation is performed on a snapshot.
2681 if (key == NOTRIM_KEY || ((ump->um_flags & UM_CANDELETE) == 0) ||
2682 devvp->v_type == VREG) {
2683 ffs_blkfree_cg(ump, fs, devvp, bno, size, inum, dephd);
2686 blkelm = malloc(sizeof(struct trim_blkreq), M_TRIM, M_WAITOK);
2688 blkelm->size = size;
2689 if (dephd == NULL) {
2690 blkelm->pdephd = NULL;
2692 LIST_INIT(&blkelm->dephd);
2693 LIST_SWAP(dephd, &blkelm->dephd, worklist, wk_list);
2694 blkelm->pdephd = &blkelm->dephd;
2696 if (key == SINGLETON_KEY) {
2698 * Just a single non-contiguous piece. Use the SINGLE
2699 * alloctype to return a trim request that will not be
2700 * hashed for future lookup.
2702 tp = trim_lookup(ump, devvp, bno, size, inum, key, SINGLE);
2703 TAILQ_INSERT_HEAD(&tp->blklist, blkelm, blkreqlist);
2704 ffs_blkfree_sendtrim(tp);
2708 * The callers of this function are not tracking whether or not
2709 * the blocks are contiguous. They are just saying that they
2710 * are freeing a set of blocks. It is this code that determines
2711 * the pieces of that range that are actually contiguous.
2713 * Calling ffs_blkrelease_start() will have created an entry
2716 tp = trim_lookup(ump, devvp, bno, size, inum, key, OLD);
2717 if (tp->size == 0) {
2719 * First block of a potential range, set block and size
2720 * for the trim block.
2724 TAILQ_INSERT_HEAD(&tp->blklist, blkelm, blkreqlist);
2728 * If this block is a continuation of the range (either
2729 * follows at the end or preceeds in the front) then we
2730 * add it to the front or back of the list and return.
2732 * If it is not a continuation of the trim that we were
2733 * building, using the REPLACE alloctype, we request that
2734 * the old trim request (still in tp) be unhashed and a
2735 * new range started (in ntp). The ffs_blkfree_sendtrim(tp)
2736 * call causes the block range described by tp to be issued
2737 * (and then tp to be freed).
2739 if (bno + numfrags(fs, size) == tp->bno) {
2740 TAILQ_INSERT_HEAD(&tp->blklist, blkelm, blkreqlist);
2744 } else if (bno == tp->bno + numfrags(fs, tp->size)) {
2745 TAILQ_INSERT_TAIL(&tp->blklist, blkelm, blkreqlist);
2749 ntp = trim_lookup(ump, devvp, bno, size, inum, key, REPLACE);
2750 TAILQ_INSERT_HEAD(&ntp->blklist, blkelm, blkreqlist);
2751 ffs_blkfree_sendtrim(tp);
2756 * Verify allocation of a block or fragment.
2757 * Return 1 if block or fragment is free.
2760 ffs_checkfreeblk(struct inode *ip,
2768 int i, frags, blkalloced;
2772 if ((uint64_t)size > fs->fs_bsize || fragoff(fs, size) != 0) {
2773 printf("bsize = %ld, size = %ld, fs = %s\n",
2774 (long)fs->fs_bsize, size, fs->fs_fsmnt);
2775 panic("ffs_checkfreeblk: bad size");
2777 if ((uint64_t)bno >= fs->fs_size)
2778 panic("ffs_checkfreeblk: too big block %jd", (intmax_t)bno);
2779 if (ffs_getcg(fs, ITODEVVP(ip), dtog(fs, bno), 0, &bp, &cgp) != 0)
2781 blksfree = cg_blksfree(cgp);
2782 cgbno = dtogd(fs, bno);
2783 if (size == fs->fs_bsize) {
2784 blkalloced = ffs_isblock(fs, blksfree, fragstoblks(fs, cgbno));
2786 frags = numfrags(fs, size);
2787 for (blkalloced = 0, i = 0; i < frags; i++)
2788 if (isset(blksfree, cgbno + i))
2790 if (blkalloced != 0 && blkalloced != frags)
2791 panic("ffs_checkfreeblk: partially free fragment");
2794 return (blkalloced == 0);
2796 #endif /* INVARIANTS */
2802 ffs_vfree(struct vnode *pvp,
2806 struct ufsmount *ump;
2808 if (DOINGSOFTDEP(pvp)) {
2809 softdep_freefile(pvp, ino, mode);
2812 ump = VFSTOUFS(pvp->v_mount);
2813 return (ffs_freefile(ump, ump->um_fs, ump->um_devvp, ino, mode, NULL));
2817 * Do the actual free operation.
2818 * The specified inode is placed back in the free map.
2821 ffs_freefile(struct ufsmount *ump,
2823 struct vnode *devvp,
2826 struct workhead *wkhd)
2837 cg = ino_to_cg(fs, ino);
2838 if (devvp->v_type == VREG) {
2839 /* devvp is a snapshot */
2840 MPASS(devvp->v_mount->mnt_data == ump);
2841 dev = ump->um_devvp->v_rdev;
2842 } else if (devvp->v_type == VCHR) {
2843 /* devvp is a normal disk device */
2844 dev = devvp->v_rdev;
2849 if (ino >= fs->fs_ipg * fs->fs_ncg)
2850 panic("ffs_freefile: range: dev = %s, ino = %ju, fs = %s",
2851 devtoname(dev), (uintmax_t)ino, fs->fs_fsmnt);
2852 if ((error = ffs_getcg(fs, devvp, cg, GB_CVTENXIO, &bp, &cgp)) != 0) {
2853 if (!MOUNTEDSOFTDEP(UFSTOVFS(ump)) || devvp->v_type != VCHR)
2856 * Would like to just downgrade to read-only. Until that
2857 * capability is available, just toss the cylinder group
2858 * update and mark the filesystem as needing to run fsck.
2860 fs->fs_flags |= FS_NEEDSFSCK;
2861 if (devvp->v_type == VREG)
2862 dbn = fragstoblks(fs, cgtod(fs, cg));
2864 dbn = fsbtodb(fs, cgtod(fs, cg));
2865 error = getblkx(devvp, dbn, dbn, fs->fs_cgsize, 0, 0, 0, &bp);
2866 KASSERT(error == 0, ("getblkx failed"));
2867 softdep_setup_inofree(UFSTOVFS(ump), bp, ino, wkhd, true);
2868 bp->b_flags |= B_RELBUF | B_NOCACHE;
2869 bp->b_flags &= ~B_CACHE;
2873 inosused = cg_inosused(cgp);
2874 cgino = ino % fs->fs_ipg;
2875 if (isclr(inosused, cgino)) {
2876 printf("dev = %s, ino = %ju, fs = %s\n", devtoname(dev),
2877 (uintmax_t)ino, fs->fs_fsmnt);
2878 if (fs->fs_ronly == 0)
2879 panic("ffs_freefile: freeing free inode");
2881 clrbit(inosused, cgino);
2882 if (cgino < cgp->cg_irotor)
2883 cgp->cg_irotor = cgino;
2884 cgp->cg_cs.cs_nifree++;
2886 fs->fs_cstotal.cs_nifree++;
2887 fs->fs_cs(fs, cg).cs_nifree++;
2888 if ((mode & IFMT) == IFDIR) {
2889 cgp->cg_cs.cs_ndir--;
2890 fs->fs_cstotal.cs_ndir--;
2891 fs->fs_cs(fs, cg).cs_ndir--;
2894 ACTIVECLEAR(fs, cg);
2896 if (MOUNTEDSOFTDEP(UFSTOVFS(ump)) && devvp->v_type == VCHR)
2897 softdep_setup_inofree(UFSTOVFS(ump), bp, ino, wkhd, false);
2903 * Check to see if a file is free.
2904 * Used to check for allocated files in snapshots.
2905 * Return 1 if file is free.
2908 ffs_checkfreefile(struct fs *fs,
2909 struct vnode *devvp,
2918 cg = ino_to_cg(fs, ino);
2919 if ((devvp->v_type != VREG) && (devvp->v_type != VCHR))
2921 if (ino >= fs->fs_ipg * fs->fs_ncg)
2923 if ((error = ffs_getcg(fs, devvp, cg, 0, &bp, &cgp)) != 0)
2925 inosused = cg_inosused(cgp);
2927 ret = isclr(inosused, ino);
2933 * Find a block of the specified size in the specified cylinder group.
2935 * It is a panic if a request is made to find a block if none are
2939 ffs_mapsearch(struct fs *fs,
2945 int start, len, loc, i;
2946 int blk, field, subfield, pos;
2950 * find the fragment by searching through the free block
2951 * map for an appropriate bit pattern
2954 start = dtogd(fs, bpref) / NBBY;
2956 start = cgp->cg_frotor / NBBY;
2957 blksfree = cg_blksfree(cgp);
2958 len = howmany(fs->fs_fpg, NBBY) - start;
2959 loc = scanc((uint64_t)len, (uint8_t *)&blksfree[start],
2960 fragtbl[fs->fs_frag],
2961 (uint8_t)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
2965 loc = scanc((uint64_t)len, (uint8_t *)&blksfree[0],
2966 fragtbl[fs->fs_frag],
2967 (uint8_t)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
2969 printf("start = %d, len = %d, fs = %s\n",
2970 start, len, fs->fs_fsmnt);
2971 panic("ffs_alloccg: map corrupted");
2975 bno = (start + len - loc) * NBBY;
2976 cgp->cg_frotor = bno;
2978 * found the byte in the map
2979 * sift through the bits to find the selected frag
2981 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
2982 blk = blkmap(fs, blksfree, bno);
2984 field = around[allocsiz];
2985 subfield = inside[allocsiz];
2986 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
2987 if ((blk & field) == subfield)
2993 printf("bno = %ju, fs = %s\n", (intmax_t)bno, fs->fs_fsmnt);
2994 panic("ffs_alloccg: block not in map");
2999 * Fetch and verify a cylinder group.
3002 ffs_getcg(struct fs *fs,
3003 struct vnode *devvp,
3012 const struct statfs *sfs;
3018 if ((fs->fs_metackhash & CK_CYLGRP) != 0)
3020 if (devvp->v_type == VCHR) {
3021 blkno = fsbtodb(fs, cgtod(fs, cg));
3022 mp = devvp->v_rdev->si_mountpt;
3024 blkno = fragstoblks(fs, cgtod(fs, cg));
3025 mp = devvp->v_mount;
3027 error = breadn_flags(devvp, blkno, blkno, (int)fs->fs_cgsize, NULL,
3028 NULL, 0, NOCRED, flags, ffs_ckhash_cg, &bp);
3031 cgp = (struct cg *)bp->b_data;
3032 if ((fs->fs_metackhash & CK_CYLGRP) != 0 &&
3033 (bp->b_flags & B_CKHASH) != 0 &&
3034 cgp->cg_ckhash != bp->b_ckhash) {
3035 if (ppsratecheck(&VFSTOUFS(mp)->um_last_integritymsg,
3036 &VFSTOUFS(mp)->um_secs_integritymsg, 1)) {
3037 sfs = &mp->mnt_stat;
3038 printf("UFS %s%s (%s) cylinder checkhash failed: "
3039 "cg %ju, cgp: 0x%x != bp: 0x%jx\n",
3040 devvp->v_type == VCHR ? "" : "snapshot of ",
3041 sfs->f_mntfromname, sfs->f_mntonname, (intmax_t)cg,
3042 cgp->cg_ckhash, (uintmax_t)bp->b_ckhash);
3044 bp->b_flags &= ~B_CKHASH;
3045 bp->b_flags |= B_INVAL | B_NOCACHE;
3047 return (EINTEGRITY);
3049 if (!cg_chkmagic(cgp) || cgp->cg_cgx != cg) {
3050 if (ppsratecheck(&VFSTOUFS(mp)->um_last_integritymsg,
3051 &VFSTOUFS(mp)->um_secs_integritymsg, 1)) {
3052 sfs = &mp->mnt_stat;
3053 printf("UFS %s%s (%s)",
3054 devvp->v_type == VCHR ? "" : "snapshot of ",
3055 sfs->f_mntfromname, sfs->f_mntonname);
3056 if (!cg_chkmagic(cgp))
3057 printf(" cg %ju: bad magic number 0x%x should "
3058 "be 0x%x\n", (intmax_t)cg, cgp->cg_magic,
3061 printf(": wrong cylinder group cg %ju != "
3062 "cgx %u\n", (intmax_t)cg, cgp->cg_cgx);
3064 bp->b_flags &= ~B_CKHASH;
3065 bp->b_flags |= B_INVAL | B_NOCACHE;
3067 return (EINTEGRITY);
3069 bp->b_flags &= ~B_CKHASH;
3070 bp->b_xflags |= BX_BKGRDWRITE;
3072 * If we are using check hashes on the cylinder group then we want
3073 * to limit changing the cylinder group time to when we are actually
3074 * going to write it to disk so that its check hash remains correct
3075 * in memory. If the CK_CYLGRP flag is set the time is updated in
3076 * ffs_bufwrite() as the buffer is queued for writing. Otherwise we
3077 * update the time here as we have done historically.
3079 if ((fs->fs_metackhash & CK_CYLGRP) != 0)
3080 bp->b_xflags |= BX_CYLGRP;
3082 cgp->cg_old_time = cgp->cg_time = time_second;
3089 ffs_ckhash_cg(struct buf *bp)
3094 cgp = (struct cg *)bp->b_data;
3095 ckhash = cgp->cg_ckhash;
3097 bp->b_ckhash = calculate_crc32c(~0L, bp->b_data, bp->b_bcount);
3098 cgp->cg_ckhash = ckhash;
3102 * Called when a cylinder group read has failed. If an integrity check
3103 * is the cause of failure then the cylinder group will not be usable
3104 * until the filesystem has been unmounted and fsck has been run to
3105 * repair it. To avoid future attempts to allocate resources from the
3106 * cylinder group, its available resources are set to zero in the
3107 * superblock summary information. Since it will appear to have no
3108 * resources available, no further calls will be made to allocate
3109 * resources from it. When resources are freed to the cylinder group
3110 * the resource free routines will find the cylinder group unusable so
3111 * the resource will simply be discarded and thus will not show up in
3112 * the superblock summary information until they are recovered by fsck.
3115 ffs_checkcgintegrity(struct fs *fs,
3120 if (error != EINTEGRITY)
3122 fs->fs_cstotal.cs_nffree -= fs->fs_cs(fs, cg).cs_nffree;
3123 fs->fs_cs(fs, cg).cs_nffree = 0;
3124 fs->fs_cstotal.cs_nbfree -= fs->fs_cs(fs, cg).cs_nbfree;
3125 fs->fs_cs(fs, cg).cs_nbfree = 0;
3126 fs->fs_cstotal.cs_nifree -= fs->fs_cs(fs, cg).cs_nifree;
3127 fs->fs_cs(fs, cg).cs_nifree = 0;
3128 fs->fs_maxcluster[cg] = 0;
3129 fs->fs_flags |= FS_NEEDSFSCK;
3134 * Fserr prints the name of a filesystem with an error diagnostic.
3136 * The form of the error message is:
3140 ffs_fserr(struct fs *fs,
3144 struct thread *td = curthread; /* XXX */
3145 struct proc *p = td->td_proc;
3147 log(LOG_ERR, "pid %d (%s), uid %d inumber %ju on %s: %s\n",
3148 p->p_pid, p->p_comm, td->td_ucred->cr_uid, (uintmax_t)inum,
3153 * This function provides the capability for the fsck program to
3154 * update an active filesystem. Sixteen operations are provided:
3156 * adjrefcnt(inode, amt) - adjusts the reference count on the
3157 * specified inode by the specified amount. Under normal
3158 * operation the count should always go down. Decrementing
3159 * the count to zero will cause the inode to be freed.
3160 * adjblkcnt(inode, amt) - adjust the number of blocks used by the
3161 * inode by the specified amount.
3162 * adjdepth(inode, amt) - adjust the depth of the specified directory
3163 * inode by the specified amount.
3164 * setsize(inode, size) - set the size of the inode to the
3166 * adjndir, adjbfree, adjifree, adjffree, adjnumclusters(amt) -
3167 * adjust the superblock summary.
3168 * freedirs(inode, count) - directory inodes [inode..inode + count - 1]
3169 * are marked as free. Inodes should never have to be marked
3171 * freefiles(inode, count) - file inodes [inode..inode + count - 1]
3172 * are marked as free. Inodes should never have to be marked
3174 * freeblks(blockno, size) - blocks [blockno..blockno + size - 1]
3175 * are marked as free. Blocks should never have to be marked
3177 * setflags(flags, set/clear) - the fs_flags field has the specified
3178 * flags set (second parameter +1) or cleared (second parameter -1).
3179 * setcwd(dirinode) - set the current directory to dirinode in the
3180 * filesystem associated with the snapshot.
3181 * setdotdot(oldvalue, newvalue) - Verify that the inode number for ".."
3182 * in the current directory is oldvalue then change it to newvalue.
3183 * unlink(nameptr, oldvalue) - Verify that the inode number associated
3184 * with nameptr in the current directory is oldvalue then unlink it.
3187 static int sysctl_ffs_fsck(SYSCTL_HANDLER_ARGS);
3189 SYSCTL_PROC(_vfs_ffs, FFS_ADJ_REFCNT, adjrefcnt,
3190 CTLFLAG_WR | CTLTYPE_STRUCT | CTLFLAG_NEEDGIANT,
3191 0, 0, sysctl_ffs_fsck, "S,fsck",
3192 "Adjust Inode Reference Count");
3194 static SYSCTL_NODE(_vfs_ffs, FFS_ADJ_BLKCNT, adjblkcnt,
3195 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3196 "Adjust Inode Used Blocks Count");
3198 static SYSCTL_NODE(_vfs_ffs, FFS_ADJ_DEPTH, adjdepth,
3199 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3200 "Adjust Directory Inode Depth");
3202 static SYSCTL_NODE(_vfs_ffs, FFS_SET_SIZE, setsize,
3203 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3204 "Set the inode size");
3206 static SYSCTL_NODE(_vfs_ffs, FFS_ADJ_NDIR, adjndir,
3207 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3208 "Adjust number of directories");
3210 static SYSCTL_NODE(_vfs_ffs, FFS_ADJ_NBFREE, adjnbfree,
3211 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3212 "Adjust number of free blocks");
3214 static SYSCTL_NODE(_vfs_ffs, FFS_ADJ_NIFREE, adjnifree,
3215 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3216 "Adjust number of free inodes");
3218 static SYSCTL_NODE(_vfs_ffs, FFS_ADJ_NFFREE, adjnffree,
3219 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3220 "Adjust number of free frags");
3222 static SYSCTL_NODE(_vfs_ffs, FFS_ADJ_NUMCLUSTERS, adjnumclusters,
3223 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3224 "Adjust number of free clusters");
3226 static SYSCTL_NODE(_vfs_ffs, FFS_DIR_FREE, freedirs,
3227 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3228 "Free Range of Directory Inodes");
3230 static SYSCTL_NODE(_vfs_ffs, FFS_FILE_FREE, freefiles,
3231 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3232 "Free Range of File Inodes");
3234 static SYSCTL_NODE(_vfs_ffs, FFS_BLK_FREE, freeblks,
3235 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3236 "Free Range of Blocks");
3238 static SYSCTL_NODE(_vfs_ffs, FFS_SET_FLAGS, setflags,
3239 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3240 "Change Filesystem Flags");
3242 static SYSCTL_NODE(_vfs_ffs, FFS_SET_CWD, setcwd,
3243 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3244 "Set Current Working Directory");
3246 static SYSCTL_NODE(_vfs_ffs, FFS_SET_DOTDOT, setdotdot,
3247 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3248 "Change Value of .. Entry");
3250 static SYSCTL_NODE(_vfs_ffs, FFS_UNLINK, unlink,
3251 CTLFLAG_WR | CTLFLAG_NEEDGIANT, sysctl_ffs_fsck,
3252 "Unlink a Duplicate Name");
3255 static int fsckcmds = 0;
3256 SYSCTL_INT(_debug, OID_AUTO, ffs_fsckcmds, CTLFLAG_RW, &fsckcmds, 0,
3257 "print out fsck_ffs-based filesystem update commands");
3258 #endif /* DIAGNOSTIC */
3261 sysctl_ffs_fsck(SYSCTL_HANDLER_ARGS)
3263 struct thread *td = curthread;
3264 struct fsck_cmd cmd;
3265 struct ufsmount *ump;
3266 struct vnode *vp, *dvp, *fdvp;
3267 struct inode *ip, *dp;
3272 long blkcnt, blksize;
3275 cap_rights_t rights;
3276 int filetype, error;
3278 if (req->newptr == NULL || req->newlen > sizeof(cmd))
3280 if ((error = SYSCTL_IN(req, &cmd, sizeof(cmd))) != 0)
3282 if (cmd.version != FFS_CMD_VERSION)
3283 return (ERPCMISMATCH);
3284 if ((error = getvnode(td, cmd.handle,
3285 cap_rights_init_one(&rights, CAP_FSCK), &fp)) != 0)
3288 if (vp->v_type != VREG && vp->v_type != VDIR) {
3292 vn_start_write(vp, &mp, V_WAIT);
3294 strncmp(mp->mnt_stat.f_fstypename, "ufs", MFSNAMELEN)) {
3295 vn_finished_write(mp);
3300 if (mp->mnt_flag & MNT_RDONLY) {
3301 vn_finished_write(mp);
3308 switch (oidp->oid_number) {
3312 printf("%s: %s flags\n", mp->mnt_stat.f_mntonname,
3313 cmd.size > 0 ? "set" : "clear");
3314 #endif /* DIAGNOSTIC */
3316 fs->fs_flags |= (long)cmd.value;
3318 fs->fs_flags &= ~(long)cmd.value;
3321 case FFS_ADJ_REFCNT:
3324 printf("%s: adjust inode %jd link count by %jd\n",
3325 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value,
3326 (intmax_t)cmd.size);
3328 #endif /* DIAGNOSTIC */
3329 if ((error = ffs_vget(mp, (ino_t)cmd.value, LK_EXCLUSIVE, &vp)))
3332 ip->i_nlink += cmd.size;
3333 DIP_SET_NLINK(ip, ip->i_nlink);
3334 ip->i_effnlink += cmd.size;
3335 UFS_INODE_SET_FLAG(ip, IN_CHANGE | IN_MODIFIED);
3336 error = ffs_update(vp, 1);
3337 if (DOINGSOFTDEP(vp))
3338 softdep_change_linkcnt(ip);
3342 case FFS_ADJ_BLKCNT:
3345 printf("%s: adjust inode %jd block count by %jd\n",
3346 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value,
3347 (intmax_t)cmd.size);
3349 #endif /* DIAGNOSTIC */
3350 if ((error = ffs_vget(mp, (ino_t)cmd.value, LK_EXCLUSIVE, &vp)))
3353 DIP_SET(ip, i_blocks, DIP(ip, i_blocks) + cmd.size);
3354 UFS_INODE_SET_FLAG(ip, IN_CHANGE | IN_MODIFIED);
3355 error = ffs_update(vp, 1);
3362 printf("%s: adjust directory inode %jd depth by %jd\n",
3363 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value,
3364 (intmax_t)cmd.size);
3366 #endif /* DIAGNOSTIC */
3367 if ((error = ffs_vget(mp, (ino_t)cmd.value, LK_EXCLUSIVE, &vp)))
3369 if (vp->v_type != VDIR) {
3375 DIP_SET(ip, i_dirdepth, DIP(ip, i_dirdepth) + cmd.size);
3376 UFS_INODE_SET_FLAG(ip, IN_CHANGE | IN_MODIFIED);
3377 error = ffs_update(vp, 1);
3384 printf("%s: set inode %jd size to %jd\n",
3385 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value,
3386 (intmax_t)cmd.size);
3388 #endif /* DIAGNOSTIC */
3389 if ((error = ffs_vget(mp, (ino_t)cmd.value, LK_EXCLUSIVE, &vp)))
3392 DIP_SET(ip, i_size, cmd.size);
3393 UFS_INODE_SET_FLAG(ip, IN_SIZEMOD | IN_CHANGE | IN_MODIFIED);
3394 error = ffs_update(vp, 1);
3406 printf("%s: free %s inode %ju\n",
3407 mp->mnt_stat.f_mntonname,
3408 filetype == IFDIR ? "directory" : "file",
3409 (uintmax_t)cmd.value);
3411 printf("%s: free %s inodes %ju-%ju\n",
3412 mp->mnt_stat.f_mntonname,
3413 filetype == IFDIR ? "directory" : "file",
3414 (uintmax_t)cmd.value,
3415 (uintmax_t)(cmd.value + cmd.size - 1));
3417 #endif /* DIAGNOSTIC */
3418 while (cmd.size > 0) {
3419 if ((error = ffs_freefile(ump, fs, ump->um_devvp,
3420 cmd.value, filetype, NULL)))
3431 printf("%s: free block %jd\n",
3432 mp->mnt_stat.f_mntonname,
3433 (intmax_t)cmd.value);
3435 printf("%s: free blocks %jd-%jd\n",
3436 mp->mnt_stat.f_mntonname,
3437 (intmax_t)cmd.value,
3438 (intmax_t)cmd.value + cmd.size - 1);
3440 #endif /* DIAGNOSTIC */
3443 blksize = fs->fs_frag - (blkno % fs->fs_frag);
3444 key = ffs_blkrelease_start(ump, ump->um_devvp, UFS_ROOTINO);
3445 while (blkcnt > 0) {
3446 if (blkcnt < blksize)
3448 ffs_blkfree(ump, fs, ump->um_devvp, blkno,
3449 blksize * fs->fs_fsize, UFS_ROOTINO,
3453 blksize = fs->fs_frag;
3455 ffs_blkrelease_finish(ump, key);
3459 * Adjust superblock summaries. fsck(8) is expected to
3460 * submit deltas when necessary.
3465 printf("%s: adjust number of directories by %jd\n",
3466 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value);
3468 #endif /* DIAGNOSTIC */
3469 fs->fs_cstotal.cs_ndir += cmd.value;
3472 case FFS_ADJ_NBFREE:
3475 printf("%s: adjust number of free blocks by %+jd\n",
3476 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value);
3478 #endif /* DIAGNOSTIC */
3479 fs->fs_cstotal.cs_nbfree += cmd.value;
3482 case FFS_ADJ_NIFREE:
3485 printf("%s: adjust number of free inodes by %+jd\n",
3486 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value);
3488 #endif /* DIAGNOSTIC */
3489 fs->fs_cstotal.cs_nifree += cmd.value;
3492 case FFS_ADJ_NFFREE:
3495 printf("%s: adjust number of free frags by %+jd\n",
3496 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value);
3498 #endif /* DIAGNOSTIC */
3499 fs->fs_cstotal.cs_nffree += cmd.value;
3502 case FFS_ADJ_NUMCLUSTERS:
3505 printf("%s: adjust number of free clusters by %+jd\n",
3506 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value);
3508 #endif /* DIAGNOSTIC */
3509 fs->fs_cstotal.cs_numclusters += cmd.value;
3515 printf("%s: set current directory to inode %jd\n",
3516 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value);
3518 #endif /* DIAGNOSTIC */
3519 if ((error = ffs_vget(mp, (ino_t)cmd.value, LK_SHARED, &vp)))
3521 AUDIT_ARG_VNODE1(vp);
3522 if ((error = change_dir(vp, td)) != 0) {
3530 case FFS_SET_DOTDOT:
3533 printf("%s: change .. in cwd from %jd to %jd\n",
3534 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value,
3535 (intmax_t)cmd.size);
3537 #endif /* DIAGNOSTIC */
3539 * First we have to get and lock the parent directory
3540 * to which ".." points.
3542 error = ffs_vget(mp, (ino_t)cmd.value, LK_EXCLUSIVE, &fdvp);
3546 * Now we get and lock the child directory containing "..".
3549 dvp = pwd->pwd_cdir;
3550 if ((error = vget(dvp, LK_EXCLUSIVE)) != 0) {
3556 SET_I_OFFSET(dp, 12); /* XXX mastertemplate.dot_reclen */
3557 error = ufs_dirrewrite(dp, VTOI(fdvp), (ino_t)cmd.size,
3571 if (copyinstr((char *)(intptr_t)cmd.value, buf,32,NULL))
3572 strncpy(buf, "Name_too_long", 32);
3573 printf("%s: unlink %s (inode %jd)\n",
3574 mp->mnt_stat.f_mntonname, buf, (intmax_t)cmd.size);
3576 #endif /* DIAGNOSTIC */
3578 * kern_funlinkat will do its own start/finish writes and
3579 * they do not nest, so drop ours here. Setting mp == NULL
3580 * indicates that vn_finished_write is not needed down below.
3582 vn_finished_write(mp);
3584 error = kern_funlinkat(td, AT_FDCWD,
3585 (char *)(intptr_t)cmd.value, FD_NONE, UIO_USERSPACE,
3586 0, (ino_t)cmd.size);
3592 printf("Invalid request %d from fsck\n",
3595 #endif /* DIAGNOSTIC */
3600 vn_finished_write(mp);