2 * Copyright (c) 1982, 1986, 1989, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 4. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * @(#)ffs_alloc.c 8.18 (Berkeley) 5/26/95
30 * $FreeBSD: src/sys/ufs/ffs/ffs_alloc.c,v 1.64.2.2 2001/09/21 19:15:21 dillon Exp $
33 #include "opt_quota.h"
35 #include <sys/param.h>
36 #include <sys/systm.h>
40 #include <sys/vnode.h>
41 #include <sys/mount.h>
42 #include <sys/kernel.h>
43 #include <sys/sysctl.h>
44 #include <sys/syslog.h>
46 #include <sys/taskqueue.h>
47 #include <machine/inttypes.h>
53 #include "ufs_extern.h"
57 #include "ffs_extern.h"
59 typedef ufs_daddr_t
allocfcn_t (struct inode
*ip
, int cg
, ufs_daddr_t bpref
,
62 static ufs_daddr_t
ffs_alloccg (struct inode
*, int, ufs_daddr_t
, int);
64 ffs_alloccgblk (struct inode
*, struct buf
*, ufs_daddr_t
);
65 static void ffs_blkfree_cg(struct fs
*, struct vnode
*, cdev_t
, ino_t
,
66 uint32_t , ufs_daddr_t
, long );
68 static int ffs_checkblk (struct inode
*, ufs_daddr_t
, long);
70 static void ffs_clusteracct (struct fs
*, struct cg
*, ufs_daddr_t
,
72 static ufs_daddr_t
ffs_clusteralloc (struct inode
*, int, ufs_daddr_t
,
74 static ino_t
ffs_dirpref (struct inode
*);
75 static ufs_daddr_t
ffs_fragextend (struct inode
*, int, long, int, int);
76 static void ffs_fserr (struct fs
*, uint
, char *);
77 static u_long ffs_hashalloc
78 (struct inode
*, int, long, int, allocfcn_t
*);
79 static ino_t
ffs_nodealloccg (struct inode
*, int, ufs_daddr_t
, int);
80 static ufs_daddr_t
ffs_mapsearch (struct fs
*, struct cg
*, ufs_daddr_t
,
84 * Allocate a block in the filesystem.
86 * The size of the requested block is given, which must be some
87 * multiple of fs_fsize and <= fs_bsize.
88 * A preference may be optionally specified. If a preference is given
89 * the following hierarchy is used to allocate a block:
90 * 1) allocate the requested block.
91 * 2) allocate a rotationally optimal block in the same cylinder.
92 * 3) allocate a block in the same cylinder group.
93 * 4) quadradically rehash into other cylinder groups, until an
94 * available block is located.
95 * If no block preference is given the following heirarchy is used
96 * to allocate a block:
97 * 1) allocate a block in the cylinder group that contains the
99 * 2) quadradically rehash into other cylinder groups, until an
100 * available block is located.
103 ffs_alloc(struct inode
*ip
, ufs_daddr_t lbn
, ufs_daddr_t bpref
, int size
,
104 struct ucred
*cred
, ufs_daddr_t
*bnp
)
116 if ((uint
)size
> fs
->fs_bsize
|| fragoff(fs
, size
) != 0) {
117 kprintf("dev = %s, bsize = %ld, size = %d, fs = %s\n",
118 devtoname(ip
->i_dev
), (long)fs
->fs_bsize
, size
,
120 panic("ffs_alloc: bad size");
123 panic("ffs_alloc: missing credential");
124 #endif /* DIAGNOSTIC */
125 if (size
== fs
->fs_bsize
&& fs
->fs_cstotal
.cs_nbfree
== 0)
127 if (cred
->cr_uid
!= 0 &&
128 freespace(fs
, fs
->fs_minfree
) - numfrags(fs
, size
) < 0)
131 error
= ufs_chkdq(ip
, (long)btodb(size
), cred
, 0);
135 if (bpref
>= fs
->fs_size
)
138 cg
= ino_to_cg(fs
, ip
->i_number
);
140 cg
= dtog(fs
, bpref
);
141 bno
= (ufs_daddr_t
)ffs_hashalloc(ip
, cg
, (long)bpref
, size
,
144 ip
->i_blocks
+= btodb(size
);
145 ip
->i_flag
|= IN_CHANGE
| IN_UPDATE
;
151 * Restore user's disk quota because allocation failed.
153 (void) ufs_chkdq(ip
, (long)-btodb(size
), cred
, FORCE
);
156 ffs_fserr(fs
, cred
->cr_uid
, "filesystem full");
157 uprintf("\n%s: write failed, filesystem is full\n", fs
->fs_fsmnt
);
162 * Reallocate a fragment to a bigger size
164 * The number and size of the old block is given, and a preference
165 * and new size is also specified. The allocator attempts to extend
166 * the original block. Failing that, the regular block allocator is
167 * invoked to get an appropriate block.
170 ffs_realloccg(struct inode
*ip
, ufs_daddr_t lbprev
, ufs_daddr_t bpref
,
171 int osize
, int nsize
, struct ucred
*cred
, struct buf
**bpp
)
175 int cg
, request
, error
;
176 ufs_daddr_t bprev
, bno
;
181 if ((uint
)osize
> fs
->fs_bsize
|| fragoff(fs
, osize
) != 0 ||
182 (uint
)nsize
> fs
->fs_bsize
|| fragoff(fs
, nsize
) != 0) {
184 "dev = %s, bsize = %ld, osize = %d, nsize = %d, fs = %s\n",
185 devtoname(ip
->i_dev
), (long)fs
->fs_bsize
, osize
,
186 nsize
, fs
->fs_fsmnt
);
187 panic("ffs_realloccg: bad size");
190 panic("ffs_realloccg: missing credential");
191 #endif /* DIAGNOSTIC */
192 if (cred
->cr_uid
!= 0 &&
193 freespace(fs
, fs
->fs_minfree
) - numfrags(fs
, nsize
- osize
) < 0)
195 if ((bprev
= ip
->i_db
[lbprev
]) == 0) {
196 kprintf("dev = %s, bsize = %ld, bprev = %ld, fs = %s\n",
197 devtoname(ip
->i_dev
), (long)fs
->fs_bsize
, (long)bprev
,
199 panic("ffs_realloccg: bad bprev");
202 * Allocate the extra space in the buffer.
204 error
= bread(ITOV(ip
), lblktodoff(fs
, lbprev
), osize
, &bp
);
210 if(bp
->b_bio2
.bio_offset
== NOOFFSET
) {
211 if( lbprev
>= NDADDR
)
212 panic("ffs_realloccg: lbprev out of range");
213 bp
->b_bio2
.bio_offset
= fsbtodoff(fs
, bprev
);
217 error
= ufs_chkdq(ip
, (long)btodb(nsize
- osize
), cred
, 0);
224 * Check for extension in the existing location.
226 cg
= dtog(fs
, bprev
);
227 bno
= ffs_fragextend(ip
, cg
, (long)bprev
, osize
, nsize
);
229 if (bp
->b_bio2
.bio_offset
!= fsbtodoff(fs
, bno
))
230 panic("ffs_realloccg: bad blockno");
231 ip
->i_blocks
+= btodb(nsize
- osize
);
232 ip
->i_flag
|= IN_CHANGE
| IN_UPDATE
;
234 bzero((char *)bp
->b_data
+ osize
, (uint
)nsize
- osize
);
239 * Allocate a new disk location.
241 if (bpref
>= fs
->fs_size
)
243 switch ((int)fs
->fs_optim
) {
246 * Allocate an exact sized fragment. Although this makes
247 * best use of space, we will waste time relocating it if
248 * the file continues to grow. If the fragmentation is
249 * less than half of the minimum free reserve, we choose
250 * to begin optimizing for time.
253 if (fs
->fs_minfree
<= 5 ||
254 fs
->fs_cstotal
.cs_nffree
>
255 (off_t
)fs
->fs_dsize
* fs
->fs_minfree
/ (2 * 100))
257 log(LOG_NOTICE
, "%s: optimization changed from SPACE to TIME\n",
259 fs
->fs_optim
= FS_OPTTIME
;
263 * At this point we have discovered a file that is trying to
264 * grow a small fragment to a larger fragment. To save time,
265 * we allocate a full sized block, then free the unused portion.
266 * If the file continues to grow, the `ffs_fragextend' call
267 * above will be able to grow it in place without further
268 * copying. If aberrant programs cause disk fragmentation to
269 * grow within 2% of the free reserve, we choose to begin
270 * optimizing for space.
272 request
= fs
->fs_bsize
;
273 if (fs
->fs_cstotal
.cs_nffree
<
274 (off_t
)fs
->fs_dsize
* (fs
->fs_minfree
- 2) / 100)
276 log(LOG_NOTICE
, "%s: optimization changed from TIME to SPACE\n",
278 fs
->fs_optim
= FS_OPTSPACE
;
281 kprintf("dev = %s, optim = %ld, fs = %s\n",
282 devtoname(ip
->i_dev
), (long)fs
->fs_optim
, fs
->fs_fsmnt
);
283 panic("ffs_realloccg: bad optim");
286 bno
= (ufs_daddr_t
)ffs_hashalloc(ip
, cg
, (long)bpref
, request
,
289 bp
->b_bio2
.bio_offset
= fsbtodoff(fs
, bno
);
290 if (!DOINGSOFTDEP(ITOV(ip
)))
291 ffs_blkfree(ip
, bprev
, (long)osize
);
293 ffs_blkfree(ip
, bno
+ numfrags(fs
, nsize
),
294 (long)(request
- nsize
));
295 ip
->i_blocks
+= btodb(nsize
- osize
);
296 ip
->i_flag
|= IN_CHANGE
| IN_UPDATE
;
298 bzero((char *)bp
->b_data
+ osize
, (uint
)nsize
- osize
);
304 * Restore user's disk quota because allocation failed.
306 (void) ufs_chkdq(ip
, (long)-btodb(nsize
- osize
), cred
, FORCE
);
313 ffs_fserr(fs
, cred
->cr_uid
, "filesystem full");
314 uprintf("\n%s: write failed, filesystem is full\n", fs
->fs_fsmnt
);
318 SYSCTL_NODE(_vfs
, OID_AUTO
, ffs
, CTLFLAG_RW
, 0, "FFS filesystem");
321 * Reallocate a sequence of blocks into a contiguous sequence of blocks.
323 * The vnode and an array of buffer pointers for a range of sequential
324 * logical blocks to be made contiguous is given. The allocator attempts
325 * to find a range of sequential blocks starting as close as possible to
326 * an fs_rotdelay offset from the end of the allocation for the logical
327 * block immediately preceeding the current range. If successful, the
328 * physical block numbers in the buffer pointers and in the inode are
329 * changed to reflect the new allocation. If unsuccessful, the allocation
330 * is left unchanged. The success in doing the reallocation is returned.
331 * Note that the error return is not reflected back to the user. Rather
332 * the previous block allocation will be used.
334 static int doasyncfree
= 1;
335 SYSCTL_INT(_vfs_ffs
, FFS_ASYNCFREE
, doasyncfree
, CTLFLAG_RW
, &doasyncfree
, 0, "");
337 static int doreallocblks
= 1;
338 SYSCTL_INT(_vfs_ffs
, FFS_REALLOCBLKS
, doreallocblks
, CTLFLAG_RW
, &doreallocblks
, 0, "");
341 static volatile int prtrealloc
= 0;
345 * ffs_reallocblks(struct vnode *a_vp, struct cluster_save *a_buflist)
348 ffs_reallocblks(struct vop_reallocblks_args
*ap
)
353 struct buf
*sbp
, *ebp
;
354 ufs_daddr_t
*bap
, *sbap
, *ebap
= NULL
;
355 struct cluster_save
*buflist
;
356 ufs_daddr_t start_lbn
, end_lbn
, soff
, newblk
, blkno
;
360 struct indir start_ap
[NIADDR
+ 1], end_ap
[NIADDR
+ 1], *idp
;
361 int i
, len
, slen
, start_lvl
, end_lvl
, pref
, ssize
;
363 if (doreallocblks
== 0)
368 if (fs
->fs_contigsumsize
<= 0)
370 buflist
= ap
->a_buflist
;
371 len
= buflist
->bs_nchildren
;
372 start_lbn
= lblkno(fs
, buflist
->bs_children
[0]->b_loffset
);
373 end_lbn
= start_lbn
+ len
- 1;
375 for (i
= 0; i
< len
; i
++)
376 if (!ffs_checkblk(ip
,
377 dofftofsb(fs
, buflist
->bs_children
[i
]->b_bio2
.bio_offset
), fs
->fs_bsize
))
378 panic("ffs_reallocblks: unallocated block 1");
379 for (i
= 1; i
< len
; i
++) {
380 if (buflist
->bs_children
[i
]->b_loffset
!= lblktodoff(fs
, start_lbn
) + lblktodoff(fs
, i
))
381 panic("ffs_reallocblks: non-logical cluster");
383 boffset
= buflist
->bs_children
[0]->b_bio2
.bio_offset
;
384 ssize
= (int)fsbtodoff(fs
, fs
->fs_frag
);
385 for (i
= 1; i
< len
- 1; i
++)
386 if (buflist
->bs_children
[i
]->b_bio2
.bio_offset
!= boffset
+ (i
* ssize
))
387 panic("ffs_reallocblks: non-physical cluster %d", i
);
390 * If the latest allocation is in a new cylinder group, assume that
391 * the filesystem has decided to move and do not force it back to
392 * the previous cylinder group.
394 if (dtog(fs
, dofftofsb(fs
, buflist
->bs_children
[0]->b_bio2
.bio_offset
)) !=
395 dtog(fs
, dofftofsb(fs
, buflist
->bs_children
[len
- 1]->b_bio2
.bio_offset
)))
397 if (ufs_getlbns(vp
, start_lbn
, start_ap
, &start_lvl
) ||
398 ufs_getlbns(vp
, end_lbn
, end_ap
, &end_lvl
))
401 * Get the starting offset and block map for the first block and
402 * the number of blocks that will fit into sbap starting at soff.
404 if (start_lvl
== 0) {
407 slen
= NDADDR
- soff
;
409 idp
= &start_ap
[start_lvl
- 1];
410 if (bread(vp
, lblktodoff(fs
, idp
->in_lbn
), (int)fs
->fs_bsize
, &sbp
)) {
414 sbap
= (ufs_daddr_t
*)sbp
->b_data
;
416 slen
= fs
->fs_nindir
- soff
;
419 * Find the preferred location for the cluster.
421 pref
= ffs_blkpref(ip
, start_lbn
, soff
, sbap
);
424 * If the block range spans two block maps, get the second map.
426 if (end_lvl
== 0 || (idp
= &end_ap
[end_lvl
- 1])->in_off
+ 1 >= len
) {
430 if (start_ap
[start_lvl
-1].in_lbn
== idp
->in_lbn
)
431 panic("ffs_reallocblk: start == end");
433 ssize
= len
- (idp
->in_off
+ 1);
434 if (bread(vp
, lblktodoff(fs
, idp
->in_lbn
), (int)fs
->fs_bsize
, &ebp
))
436 ebap
= (ufs_daddr_t
*)ebp
->b_data
;
440 * Make sure we aren't spanning more then two blockmaps. ssize is
441 * our calculation of the span we have to scan in the first blockmap,
442 * while slen is our calculation of the number of entries available
443 * in the first blockmap (from soff).
446 panic("ffs_reallocblks: range spans more then two blockmaps!"
447 " start_lbn %ld len %d (%d/%d)",
448 (long)start_lbn
, len
, slen
, ssize
);
451 * Search the block map looking for an allocation of the desired size.
453 if ((newblk
= (ufs_daddr_t
)ffs_hashalloc(ip
, dtog(fs
, pref
), (long)pref
,
454 len
, ffs_clusteralloc
)) == 0)
457 * We have found a new contiguous block.
459 * First we have to replace the old block pointers with the new
460 * block pointers in the inode and indirect blocks associated
465 kprintf("realloc: ino %ju, lbns %d-%d\n\told:",
466 (uintmax_t)ip
->i_number
, start_lbn
, end_lbn
);
469 for (bap
= &sbap
[soff
], i
= 0; i
< len
; i
++, blkno
+= fs
->fs_frag
) {
475 if (!ffs_checkblk(ip
,
476 dofftofsb(fs
, buflist
->bs_children
[i
]->b_bio2
.bio_offset
), fs
->fs_bsize
))
477 panic("ffs_reallocblks: unallocated block 2");
478 if (dofftofsb(fs
, buflist
->bs_children
[i
]->b_bio2
.bio_offset
) != *bap
)
479 panic("ffs_reallocblks: alloc mismatch");
483 kprintf(" %d,", *bap
);
485 if (DOINGSOFTDEP(vp
)) {
486 if (sbap
== &ip
->i_db
[0] && i
< ssize
)
487 softdep_setup_allocdirect(ip
, start_lbn
+ i
,
488 blkno
, *bap
, fs
->fs_bsize
, fs
->fs_bsize
,
489 buflist
->bs_children
[i
]);
491 softdep_setup_allocindir_page(ip
, start_lbn
+ i
,
492 i
< ssize
? sbp
: ebp
, soff
+ i
, blkno
,
493 *bap
, buflist
->bs_children
[i
]);
498 * Next we must write out the modified inode and indirect blocks.
499 * For strict correctness, the writes should be synchronous since
500 * the old block values may have been written to disk. In practise
501 * they are almost never written, but if we are concerned about
502 * strict correctness, the `doasyncfree' flag should be set to zero.
504 * The test on `doasyncfree' should be changed to test a flag
505 * that shows whether the associated buffers and inodes have
506 * been written. The flag should be set when the cluster is
507 * started and cleared whenever the buffer or inode is flushed.
508 * We can then check below to see if it is set, and do the
509 * synchronous write only when it has been cleared.
511 if (sbap
!= &ip
->i_db
[0]) {
517 ip
->i_flag
|= IN_CHANGE
| IN_UPDATE
;
528 * Last, free the old blocks and assign the new blocks to the buffers.
534 for (blkno
= newblk
, i
= 0; i
< len
; i
++, blkno
+= fs
->fs_frag
) {
535 if (!DOINGSOFTDEP(vp
))
537 dofftofsb(fs
, buflist
->bs_children
[i
]->b_bio2
.bio_offset
),
539 buflist
->bs_children
[i
]->b_bio2
.bio_offset
= fsbtodoff(fs
, blkno
);
541 if (!ffs_checkblk(ip
,
542 dofftofsb(fs
, buflist
->bs_children
[i
]->b_bio2
.bio_offset
), fs
->fs_bsize
))
543 panic("ffs_reallocblks: unallocated block 3");
547 kprintf(" %d,", blkno
);
561 if (sbap
!= &ip
->i_db
[0])
567 * Allocate an inode in the filesystem.
569 * If allocating a directory, use ffs_dirpref to select the inode.
570 * If allocating in a directory, the following hierarchy is followed:
571 * 1) allocate the preferred inode.
572 * 2) allocate an inode in the same cylinder group.
573 * 3) quadradically rehash into other cylinder groups, until an
574 * available inode is located.
575 * If no inode preference is given the following heirarchy is used
576 * to allocate an inode:
577 * 1) allocate an inode in cylinder group 0.
578 * 2) quadradically rehash into other cylinder groups, until an
579 * available inode is located.
582 ffs_valloc(struct vnode
*pvp
, int mode
, struct ucred
*cred
, struct vnode
**vpp
)
593 if (fs
->fs_cstotal
.cs_nifree
== 0)
596 if ((mode
& IFMT
) == IFDIR
)
597 ipref
= ffs_dirpref(pip
);
599 ipref
= pip
->i_number
;
600 if (ipref
>= fs
->fs_ncg
* fs
->fs_ipg
)
602 cg
= ino_to_cg(fs
, ipref
);
604 * Track number of dirs created one after another
605 * in a same cg without intervening by files.
607 if ((mode
& IFMT
) == IFDIR
) {
608 if (fs
->fs_contigdirs
[cg
] < 255)
609 fs
->fs_contigdirs
[cg
]++;
611 if (fs
->fs_contigdirs
[cg
] > 0)
612 fs
->fs_contigdirs
[cg
]--;
614 ino
= (ino_t
)ffs_hashalloc(pip
, cg
, (long)ipref
, mode
,
615 (allocfcn_t
*)ffs_nodealloccg
);
618 error
= VFS_VGET(pvp
->v_mount
, NULL
, ino
, vpp
);
620 ffs_vfree(pvp
, ino
, mode
);
625 kprintf("mode = 0%o, inum = %lu, fs = %s\n",
626 ip
->i_mode
, (u_long
)ip
->i_number
, fs
->fs_fsmnt
);
627 panic("ffs_valloc: dup alloc");
629 if (ip
->i_blocks
) { /* XXX */
630 kprintf("free inode %s/%lu had %ld blocks\n",
631 fs
->fs_fsmnt
, (u_long
)ino
, (long)ip
->i_blocks
);
636 * Set up a new generation number for this inode.
638 if (ip
->i_gen
== 0 || ++ip
->i_gen
== 0)
639 ip
->i_gen
= krandom() / 2 + 1;
642 ffs_fserr(fs
, cred
->cr_uid
, "out of inodes");
643 uprintf("\n%s: create/symlink failed, no inodes free\n", fs
->fs_fsmnt
);
648 * Find a cylinder group to place a directory.
650 * The policy implemented by this algorithm is to allocate a
651 * directory inode in the same cylinder group as its parent
652 * directory, but also to reserve space for its files inodes
653 * and data. Restrict the number of directories which may be
654 * allocated one after another in the same cylinder group
655 * without intervening allocation of files.
657 * If we allocate a first level directory then force allocation
658 * in another cylinder group.
661 ffs_dirpref(struct inode
*pip
)
664 int cg
, prefcg
, dirsize
, cgsize
;
666 int avgifree
, avgbfree
, avgndir
, curdirsize
;
667 int minifree
, minbfree
, maxndir
;
673 avgifree
= fs
->fs_cstotal
.cs_nifree
/ fs
->fs_ncg
;
674 avgbfree
= fs
->fs_cstotal
.cs_nbfree
/ fs
->fs_ncg
;
675 avgndir
= fs
->fs_cstotal
.cs_ndir
/ fs
->fs_ncg
;
678 * Force allocation in another cg if creating a first level dir.
680 if (ITOV(pip
)->v_flag
& VROOT
) {
681 prefcg
= karc4random() % fs
->fs_ncg
;
683 minndir
= fs
->fs_ipg
;
684 for (cg
= prefcg
; cg
< fs
->fs_ncg
; cg
++)
685 if (fs
->fs_cs(fs
, cg
).cs_ndir
< minndir
&&
686 fs
->fs_cs(fs
, cg
).cs_nifree
>= avgifree
&&
687 fs
->fs_cs(fs
, cg
).cs_nbfree
>= avgbfree
) {
689 minndir
= fs
->fs_cs(fs
, cg
).cs_ndir
;
691 for (cg
= 0; cg
< prefcg
; cg
++)
692 if (fs
->fs_cs(fs
, cg
).cs_ndir
< minndir
&&
693 fs
->fs_cs(fs
, cg
).cs_nifree
>= avgifree
&&
694 fs
->fs_cs(fs
, cg
).cs_nbfree
>= avgbfree
) {
696 minndir
= fs
->fs_cs(fs
, cg
).cs_ndir
;
698 return ((ino_t
)(fs
->fs_ipg
* mincg
));
702 * Count various limits which used for
703 * optimal allocation of a directory inode.
705 maxndir
= min(avgndir
+ fs
->fs_ipg
/ 16, fs
->fs_ipg
);
706 minifree
= avgifree
- avgifree
/ 4;
709 minbfree
= avgbfree
- avgbfree
/ 4;
712 cgsize
= fs
->fs_fsize
* fs
->fs_fpg
;
715 * fs_avgfilesize and fs_avgfpdir are user-settable entities and
716 * multiplying them may overflow a 32 bit integer.
718 dirsize64
= fs
->fs_avgfilesize
* (int64_t)fs
->fs_avgfpdir
;
719 if (dirsize64
> 0x7fffffff) {
722 dirsize
= (int)dirsize64
;
723 curdirsize
= avgndir
?
724 (cgsize
- avgbfree
* fs
->fs_bsize
) / avgndir
: 0;
725 if (dirsize
< curdirsize
)
726 dirsize
= curdirsize
;
727 maxcontigdirs
= min((avgbfree
* fs
->fs_bsize
) / dirsize
, 255);
728 if (fs
->fs_avgfpdir
> 0)
729 maxcontigdirs
= min(maxcontigdirs
,
730 fs
->fs_ipg
/ fs
->fs_avgfpdir
);
731 if (maxcontigdirs
== 0)
736 * Limit number of dirs in one cg and reserve space for
737 * regular files, but only if we have no deficit in
740 prefcg
= ino_to_cg(fs
, pip
->i_number
);
741 for (cg
= prefcg
; cg
< fs
->fs_ncg
; cg
++)
742 if (fs
->fs_cs(fs
, cg
).cs_ndir
< maxndir
&&
743 fs
->fs_cs(fs
, cg
).cs_nifree
>= minifree
&&
744 fs
->fs_cs(fs
, cg
).cs_nbfree
>= minbfree
) {
745 if (fs
->fs_contigdirs
[cg
] < maxcontigdirs
)
746 return ((ino_t
)(fs
->fs_ipg
* cg
));
748 for (cg
= 0; cg
< prefcg
; cg
++)
749 if (fs
->fs_cs(fs
, cg
).cs_ndir
< maxndir
&&
750 fs
->fs_cs(fs
, cg
).cs_nifree
>= minifree
&&
751 fs
->fs_cs(fs
, cg
).cs_nbfree
>= minbfree
) {
752 if (fs
->fs_contigdirs
[cg
] < maxcontigdirs
)
753 return ((ino_t
)(fs
->fs_ipg
* cg
));
756 * This is a backstop when we have deficit in space.
758 for (cg
= prefcg
; cg
< fs
->fs_ncg
; cg
++)
759 if (fs
->fs_cs(fs
, cg
).cs_nifree
>= avgifree
)
760 return ((ino_t
)(fs
->fs_ipg
* cg
));
761 for (cg
= 0; cg
< prefcg
; cg
++)
762 if (fs
->fs_cs(fs
, cg
).cs_nifree
>= avgifree
)
764 return ((ino_t
)(fs
->fs_ipg
* cg
));
768 * Select the desired position for the next block in a file. The file is
769 * logically divided into sections. The first section is composed of the
770 * direct blocks. Each additional section contains fs_maxbpg blocks.
772 * If no blocks have been allocated in the first section, the policy is to
773 * request a block in the same cylinder group as the inode that describes
774 * the file. If no blocks have been allocated in any other section, the
775 * policy is to place the section in a cylinder group with a greater than
776 * average number of free blocks. An appropriate cylinder group is found
777 * by using a rotor that sweeps the cylinder groups. When a new group of
778 * blocks is needed, the sweep begins in the cylinder group following the
779 * cylinder group from which the previous allocation was made. The sweep
780 * continues until a cylinder group with greater than the average number
781 * of free blocks is found. If the allocation is for the first block in an
782 * indirect block, the information on the previous allocation is unavailable;
783 * here a best guess is made based upon the logical block number being
786 * If a section is already partially allocated, the policy is to
787 * contiguously allocate fs_maxcontig blocks. The end of one of these
788 * contiguous blocks and the beginning of the next is physically separated
789 * so that the disk head will be in transit between them for at least
790 * fs_rotdelay milliseconds. This is to allow time for the processor to
791 * schedule another I/O transfer.
794 ffs_blkpref(struct inode
*ip
, ufs_daddr_t lbn
, int indx
, ufs_daddr_t
*bap
)
798 int avgbfree
, startcg
;
802 if (indx
% fs
->fs_maxbpg
== 0 || bap
[indx
- 1] == 0) {
803 if (lbn
< NDADDR
+ NINDIR(fs
)) {
804 cg
= ino_to_cg(fs
, ip
->i_number
);
805 return (fs
->fs_fpg
* cg
+ fs
->fs_frag
);
808 * Find a cylinder with greater than average number of
809 * unused data blocks.
811 if (indx
== 0 || bap
[indx
- 1] == 0)
813 ino_to_cg(fs
, ip
->i_number
) + lbn
/ fs
->fs_maxbpg
;
815 startcg
= dtog(fs
, bap
[indx
- 1]) + 1;
816 startcg
%= fs
->fs_ncg
;
817 avgbfree
= fs
->fs_cstotal
.cs_nbfree
/ fs
->fs_ncg
;
818 for (cg
= startcg
; cg
< fs
->fs_ncg
; cg
++)
819 if (fs
->fs_cs(fs
, cg
).cs_nbfree
>= avgbfree
) {
821 return (fs
->fs_fpg
* cg
+ fs
->fs_frag
);
823 for (cg
= 0; cg
<= startcg
; cg
++)
824 if (fs
->fs_cs(fs
, cg
).cs_nbfree
>= avgbfree
) {
826 return (fs
->fs_fpg
* cg
+ fs
->fs_frag
);
831 * One or more previous blocks have been laid out. If less
832 * than fs_maxcontig previous blocks are contiguous, the
833 * next block is requested contiguously, otherwise it is
834 * requested rotationally delayed by fs_rotdelay milliseconds.
836 nextblk
= bap
[indx
- 1] + fs
->fs_frag
;
837 if (fs
->fs_rotdelay
== 0 || indx
< fs
->fs_maxcontig
||
838 bap
[indx
- fs
->fs_maxcontig
] +
839 blkstofrags(fs
, fs
->fs_maxcontig
) != nextblk
)
842 * Here we convert ms of delay to frags as:
843 * (frags) = (ms) * (rev/sec) * (sect/rev) /
844 * ((sect/frag) * (ms/sec))
845 * then round up to the next block.
847 nextblk
+= roundup(fs
->fs_rotdelay
* fs
->fs_rps
* fs
->fs_nsect
/
848 (NSPF(fs
) * 1000), fs
->fs_frag
);
853 * Implement the cylinder overflow algorithm.
855 * The policy implemented by this algorithm is:
856 * 1) allocate the block in its requested cylinder group.
857 * 2) quadradically rehash on the cylinder group number.
858 * 3) brute force search for a free block.
862 ffs_hashalloc(struct inode
*ip
, int cg
, long pref
,
863 int size
, /* size for data blocks, mode for inodes */
864 allocfcn_t
*allocator
)
867 long result
; /* XXX why not same type as we return? */
872 * 1: preferred cylinder group
874 result
= (*allocator
)(ip
, cg
, pref
, size
);
878 * 2: quadratic rehash
880 for (i
= 1; i
< fs
->fs_ncg
; i
*= 2) {
882 if (cg
>= fs
->fs_ncg
)
884 result
= (*allocator
)(ip
, cg
, 0, size
);
889 * 3: brute force search
890 * Note that we start at i == 2, since 0 was checked initially,
891 * and 1 is always checked in the quadratic rehash.
893 cg
= (icg
+ 2) % fs
->fs_ncg
;
894 for (i
= 2; i
< fs
->fs_ncg
; i
++) {
895 result
= (*allocator
)(ip
, cg
, 0, size
);
899 if (cg
== fs
->fs_ncg
)
906 * Determine whether a fragment can be extended.
908 * Check to see if the necessary fragments are available, and
909 * if they are, allocate them.
912 ffs_fragextend(struct inode
*ip
, int cg
, long bprev
, int osize
, int nsize
)
923 if (fs
->fs_cs(fs
, cg
).cs_nffree
< numfrags(fs
, nsize
- osize
))
925 frags
= numfrags(fs
, nsize
);
926 bbase
= fragnum(fs
, bprev
);
927 if (bbase
> fragnum(fs
, (bprev
+ frags
- 1))) {
928 /* cannot extend across a block boundary */
931 KKASSERT(blknum(fs
, bprev
) == blknum(fs
, bprev
+ frags
- 1));
932 error
= bread(ip
->i_devvp
, fsbtodoff(fs
, cgtod(fs
, cg
)),
933 (int)fs
->fs_cgsize
, &bp
);
938 cgp
= (struct cg
*)bp
->b_data
;
939 if (!cg_chkmagic(cgp
)) {
943 cgp
->cg_time
= time_second
;
944 bno
= dtogd(fs
, bprev
);
945 blksfree
= cg_blksfree(cgp
);
946 for (i
= numfrags(fs
, osize
); i
< frags
; i
++) {
947 if (isclr(blksfree
, bno
+ i
)) {
954 * the current fragment can be extended
955 * deduct the count on fragment being extended into
956 * increase the count on the remaining fragment (if any)
957 * allocate the extended piece
959 * ---oooooooooonnnnnnn111----
964 for (i
= frags
; i
< fs
->fs_frag
- bbase
; i
++) {
965 if (isclr(blksfree
, bno
+ i
))
970 * Size of original free frag is [i - numfrags(fs, osize)]
971 * Size of remaining free frag is [i - frags]
973 cgp
->cg_frsum
[i
- numfrags(fs
, osize
)]--;
975 cgp
->cg_frsum
[i
- frags
]++;
976 for (i
= numfrags(fs
, osize
); i
< frags
; i
++) {
977 clrbit(blksfree
, bno
+ i
);
978 cgp
->cg_cs
.cs_nffree
--;
979 fs
->fs_cstotal
.cs_nffree
--;
980 fs
->fs_cs(fs
, cg
).cs_nffree
--;
983 if (DOINGSOFTDEP(ITOV(ip
)))
984 softdep_setup_blkmapdep(bp
, fs
, bprev
);
990 * Determine whether a block can be allocated.
992 * Check to see if a block of the appropriate size is available,
993 * and if it is, allocate it.
996 ffs_alloccg(struct inode
*ip
, int cg
, ufs_daddr_t bpref
, int size
)
1002 ufs_daddr_t bno
, blkno
;
1003 int allocsiz
, error
, frags
;
1007 if (fs
->fs_cs(fs
, cg
).cs_nbfree
== 0 && size
== fs
->fs_bsize
)
1009 error
= bread(ip
->i_devvp
, fsbtodoff(fs
, cgtod(fs
, cg
)),
1010 (int)fs
->fs_cgsize
, &bp
);
1015 cgp
= (struct cg
*)bp
->b_data
;
1016 if (!cg_chkmagic(cgp
) ||
1017 (cgp
->cg_cs
.cs_nbfree
== 0 && size
== fs
->fs_bsize
)) {
1021 cgp
->cg_time
= time_second
;
1022 if (size
== fs
->fs_bsize
) {
1023 bno
= ffs_alloccgblk(ip
, bp
, bpref
);
1028 * Check to see if any fragments of sufficient size are already
1029 * available. Fit the data into a larger fragment if necessary,
1030 * before allocating a whole new block.
1032 blksfree
= cg_blksfree(cgp
);
1033 frags
= numfrags(fs
, size
);
1034 for (allocsiz
= frags
; allocsiz
< fs
->fs_frag
; allocsiz
++) {
1035 if (cgp
->cg_frsum
[allocsiz
] != 0)
1038 if (allocsiz
== fs
->fs_frag
) {
1040 * No fragments were available, allocate a whole block and
1041 * cut the requested fragment (of size frags) out of it.
1043 if (cgp
->cg_cs
.cs_nbfree
== 0) {
1047 bno
= ffs_alloccgblk(ip
, bp
, bpref
);
1048 bpref
= dtogd(fs
, bno
);
1049 for (i
= frags
; i
< fs
->fs_frag
; i
++)
1050 setbit(blksfree
, bpref
+ i
);
1053 * Calculate the number of free frags still remaining after
1054 * we have cut out the requested allocation. Indicate that
1055 * a fragment of that size is now available for future
1058 i
= fs
->fs_frag
- frags
;
1059 cgp
->cg_cs
.cs_nffree
+= i
;
1060 fs
->fs_cstotal
.cs_nffree
+= i
;
1061 fs
->fs_cs(fs
, cg
).cs_nffree
+= i
;
1069 * cg_frsum[] has told us that a free fragment of allocsiz size is
1070 * available. Find it, then clear the bitmap bits associated with
1073 bno
= ffs_mapsearch(fs
, cgp
, bpref
, allocsiz
);
1078 for (i
= 0; i
< frags
; i
++)
1079 clrbit(blksfree
, bno
+ i
);
1080 cgp
->cg_cs
.cs_nffree
-= frags
;
1081 fs
->fs_cstotal
.cs_nffree
-= frags
;
1082 fs
->fs_cs(fs
, cg
).cs_nffree
-= frags
;
1086 * Account for the allocation. The original searched size that we
1087 * found is no longer available. If we cut out a smaller piece then
1088 * a smaller fragment is now available.
1090 cgp
->cg_frsum
[allocsiz
]--;
1091 if (frags
!= allocsiz
)
1092 cgp
->cg_frsum
[allocsiz
- frags
]++;
1093 blkno
= cg
* fs
->fs_fpg
+ bno
;
1094 if (DOINGSOFTDEP(ITOV(ip
)))
1095 softdep_setup_blkmapdep(bp
, fs
, blkno
);
1097 return ((u_long
)blkno
);
1101 * Allocate a block in a cylinder group.
1103 * This algorithm implements the following policy:
1104 * 1) allocate the requested block.
1105 * 2) allocate a rotationally optimal block in the same cylinder.
1106 * 3) allocate the next available block on the block rotor for the
1107 * specified cylinder group.
1108 * Note that this routine only allocates fs_bsize blocks; these
1109 * blocks may be fragmented by the routine that allocates them.
1112 ffs_alloccgblk(struct inode
*ip
, struct buf
*bp
, ufs_daddr_t bpref
)
1116 ufs_daddr_t bno
, blkno
;
1117 int cylno
, pos
, delta
;
1123 cgp
= (struct cg
*)bp
->b_data
;
1124 blksfree
= cg_blksfree(cgp
);
1125 if (bpref
== 0 || dtog(fs
, bpref
) != cgp
->cg_cgx
) {
1126 bpref
= cgp
->cg_rotor
;
1129 bpref
= blknum(fs
, bpref
);
1130 bpref
= dtogd(fs
, bpref
);
1132 * if the requested block is available, use it
1134 if (ffs_isblock(fs
, blksfree
, fragstoblks(fs
, bpref
))) {
1138 if (fs
->fs_nrpos
<= 1 || fs
->fs_cpc
== 0) {
1140 * Block layout information is not available.
1141 * Leaving bpref unchanged means we take the
1142 * next available free block following the one
1143 * we just allocated. Hopefully this will at
1144 * least hit a track cache on drives of unknown
1145 * geometry (e.g. SCSI).
1150 * check for a block available on the same cylinder
1152 cylno
= cbtocylno(fs
, bpref
);
1153 if (cg_blktot(cgp
)[cylno
] == 0)
1156 * check the summary information to see if a block is
1157 * available in the requested cylinder starting at the
1158 * requested rotational position and proceeding around.
1160 cylbp
= cg_blks(fs
, cgp
, cylno
);
1161 pos
= cbtorpos(fs
, bpref
);
1162 for (i
= pos
; i
< fs
->fs_nrpos
; i
++)
1165 if (i
== fs
->fs_nrpos
)
1166 for (i
= 0; i
< pos
; i
++)
1171 * found a rotational position, now find the actual
1172 * block. A panic if none is actually there.
1174 pos
= cylno
% fs
->fs_cpc
;
1175 bno
= (cylno
- pos
) * fs
->fs_spc
/ NSPB(fs
);
1176 if (fs_postbl(fs
, pos
)[i
] == -1) {
1177 kprintf("pos = %d, i = %d, fs = %s\n",
1178 pos
, i
, fs
->fs_fsmnt
);
1179 panic("ffs_alloccgblk: cyl groups corrupted");
1181 for (i
= fs_postbl(fs
, pos
)[i
];; ) {
1182 if (ffs_isblock(fs
, blksfree
, bno
+ i
)) {
1183 bno
= blkstofrags(fs
, (bno
+ i
));
1186 delta
= fs_rotbl(fs
)[i
];
1188 delta
+ i
> fragstoblks(fs
, fs
->fs_fpg
))
1192 kprintf("pos = %d, i = %d, fs = %s\n", pos
, i
, fs
->fs_fsmnt
);
1193 panic("ffs_alloccgblk: can't find blk in cyl");
1197 * no blocks in the requested cylinder, so take next
1198 * available one in this cylinder group.
1200 bno
= ffs_mapsearch(fs
, cgp
, bpref
, (int)fs
->fs_frag
);
1203 cgp
->cg_rotor
= bno
;
1205 blkno
= fragstoblks(fs
, bno
);
1206 ffs_clrblock(fs
, blksfree
, (long)blkno
);
1207 ffs_clusteracct(fs
, cgp
, blkno
, -1);
1208 cgp
->cg_cs
.cs_nbfree
--;
1209 fs
->fs_cstotal
.cs_nbfree
--;
1210 fs
->fs_cs(fs
, cgp
->cg_cgx
).cs_nbfree
--;
1211 cylno
= cbtocylno(fs
, bno
);
1212 cg_blks(fs
, cgp
, cylno
)[cbtorpos(fs
, bno
)]--;
1213 cg_blktot(cgp
)[cylno
]--;
1215 blkno
= cgp
->cg_cgx
* fs
->fs_fpg
+ bno
;
1216 if (DOINGSOFTDEP(ITOV(ip
)))
1217 softdep_setup_blkmapdep(bp
, fs
, blkno
);
1222 * Determine whether a cluster can be allocated.
1224 * We do not currently check for optimal rotational layout if there
1225 * are multiple choices in the same cylinder group. Instead we just
1226 * take the first one that we find following bpref.
1229 ffs_clusteralloc(struct inode
*ip
, int cg
, ufs_daddr_t bpref
, int len
)
1234 int i
, got
, run
, bno
, bit
, map
;
1240 if (fs
->fs_maxcluster
[cg
] < len
)
1242 if (bread(ip
->i_devvp
, fsbtodoff(fs
, cgtod(fs
, cg
)),
1243 (int)fs
->fs_cgsize
, &bp
)) {
1246 cgp
= (struct cg
*)bp
->b_data
;
1247 if (!cg_chkmagic(cgp
))
1251 * Check to see if a cluster of the needed size (or bigger) is
1252 * available in this cylinder group.
1254 lp
= &cg_clustersum(cgp
)[len
];
1255 for (i
= len
; i
<= fs
->fs_contigsumsize
; i
++)
1258 if (i
> fs
->fs_contigsumsize
) {
1260 * This is the first time looking for a cluster in this
1261 * cylinder group. Update the cluster summary information
1262 * to reflect the true maximum sized cluster so that
1263 * future cluster allocation requests can avoid reading
1264 * the cylinder group map only to find no clusters.
1266 lp
= &cg_clustersum(cgp
)[len
- 1];
1267 for (i
= len
- 1; i
> 0; i
--)
1270 fs
->fs_maxcluster
[cg
] = i
;
1274 * Search the cluster map to find a big enough cluster.
1275 * We take the first one that we find, even if it is larger
1276 * than we need as we prefer to get one close to the previous
1277 * block allocation. We do not search before the current
1278 * preference point as we do not want to allocate a block
1279 * that is allocated before the previous one (as we will
1280 * then have to wait for another pass of the elevator
1281 * algorithm before it will be read). We prefer to fail and
1282 * be recalled to try an allocation in the next cylinder group.
1284 if (dtog(fs
, bpref
) != cg
)
1287 bpref
= fragstoblks(fs
, dtogd(fs
, blknum(fs
, bpref
)));
1288 mapp
= &cg_clustersfree(cgp
)[bpref
/ NBBY
];
1290 bit
= 1 << (bpref
% NBBY
);
1291 for (run
= 0, got
= bpref
; got
< cgp
->cg_nclusterblks
; got
++) {
1292 if ((map
& bit
) == 0) {
1299 if ((got
& (NBBY
- 1)) != (NBBY
- 1)) {
1306 if (got
>= cgp
->cg_nclusterblks
)
1309 * Allocate the cluster that we have found.
1311 blksfree
= cg_blksfree(cgp
);
1312 for (i
= 1; i
<= len
; i
++) {
1313 if (!ffs_isblock(fs
, blksfree
, got
- run
+ i
))
1314 panic("ffs_clusteralloc: map mismatch");
1316 bno
= cg
* fs
->fs_fpg
+ blkstofrags(fs
, got
- run
+ 1);
1317 if (dtog(fs
, bno
) != cg
)
1318 panic("ffs_clusteralloc: allocated out of group");
1319 len
= blkstofrags(fs
, len
);
1320 for (i
= 0; i
< len
; i
+= fs
->fs_frag
) {
1321 if ((got
= ffs_alloccgblk(ip
, bp
, bno
+ i
)) != bno
+ i
)
1322 panic("ffs_clusteralloc: lost block");
1333 * Determine whether an inode can be allocated.
1335 * Check to see if an inode is available, and if it is,
1336 * allocate it using the following policy:
1337 * 1) allocate the requested inode.
1338 * 2) allocate the next available inode after the requested
1339 * inode in the specified cylinder group.
1340 * 3) the inode must not already be in the inode hash table. We
1341 * can encounter such a case because the vnode reclamation sequence
1343 * 3) the inode must not already be in the inode hash, otherwise it
1344 * may be in the process of being deallocated. This can occur
1345 * because the bitmap is updated before the inode is removed from
1346 * hash. If we were to reallocate the inode the caller could wind
1347 * up returning a vnode/inode combination which is in an indeterminate
1351 ffs_nodealloccg(struct inode
*ip
, int cg
, ufs_daddr_t ipref
, int mode
)
1353 struct ufsmount
*ump
;
1359 int error
, len
, arraysize
, i
;
1365 ump
= VFSTOUFS(vp
->v_mount
);
1367 if (fs
->fs_cs(fs
, cg
).cs_nifree
== 0)
1369 error
= bread(ip
->i_devvp
, fsbtodoff(fs
, cgtod(fs
, cg
)),
1370 (int)fs
->fs_cgsize
, &bp
);
1375 cgp
= (struct cg
*)bp
->b_data
;
1376 if (!cg_chkmagic(cgp
) || cgp
->cg_cs
.cs_nifree
== 0) {
1380 inosused
= cg_inosused(cgp
);
1384 * Quick check, reuse the most recently free inode or continue
1385 * a scan from where we left off the last time.
1387 ibase
= cg
* fs
->fs_ipg
;
1389 ipref
%= fs
->fs_ipg
;
1390 if (isclr(inosused
, ipref
)) {
1391 if (ufs_ihashcheck(ump
, ip
->i_dev
, ibase
+ ipref
) == 0)
1397 * Scan the inode bitmap starting at irotor, be sure to handle
1398 * the edge case by going back to the beginning of the array.
1400 * If the number of inodes is not byte-aligned, the unused bits
1401 * should be set to 1. This will be sanity checked in gotit. Note
1402 * that we have to be sure not to overlap the beginning and end
1403 * when irotor is in the middle of a byte as this will cause the
1404 * same bitmap byte to be checked twice. To solve this problem we
1405 * just convert everything to a byte index for the loop.
1407 ipref
= (cgp
->cg_irotor
% fs
->fs_ipg
) >> 3; /* byte index */
1408 len
= (fs
->fs_ipg
+ 7) >> 3; /* byte size */
1412 map
= inosused
[ipref
];
1414 for (i
= 0; i
< NBBY
; ++i
) {
1416 * If we find a free bit we have to make sure
1417 * that the inode is not in the middle of
1418 * being destroyed. The inode should not exist
1419 * in the inode hash.
1421 * Adjust the rotor to try to hit the
1422 * quick-check up above.
1424 if ((map
& (1 << i
)) == 0) {
1425 if (ufs_ihashcheck(ump
, ip
->i_dev
, ibase
+ (ipref
<< 3) + i
) == 0) {
1426 ipref
= (ipref
<< 3) + i
;
1427 cgp
->cg_irotor
= (ipref
+ 1) % fs
->fs_ipg
;
1436 * Setup for the next byte, start at the beginning again if
1437 * we hit the end of the array.
1439 if (++ipref
== arraysize
)
1443 if (icheckmiss
== cgp
->cg_cs
.cs_nifree
) {
1447 kprintf("fs = %s\n", fs
->fs_fsmnt
);
1448 panic("ffs_nodealloccg: block not in map, icheckmiss/nfree %d/%d",
1449 icheckmiss
, cgp
->cg_cs
.cs_nifree
);
1453 * ipref is a bit index as of the gotit label.
1456 KKASSERT(ipref
>= 0 && ipref
< fs
->fs_ipg
);
1457 cgp
->cg_time
= time_second
;
1458 if (DOINGSOFTDEP(ITOV(ip
)))
1459 softdep_setup_inomapdep(bp
, ip
, ibase
+ ipref
);
1460 setbit(inosused
, ipref
);
1461 cgp
->cg_cs
.cs_nifree
--;
1462 fs
->fs_cstotal
.cs_nifree
--;
1463 fs
->fs_cs(fs
, cg
).cs_nifree
--;
1465 if ((mode
& IFMT
) == IFDIR
) {
1466 cgp
->cg_cs
.cs_ndir
++;
1467 fs
->fs_cstotal
.cs_ndir
++;
1468 fs
->fs_cs(fs
, cg
).cs_ndir
++;
1471 return (ibase
+ ipref
);
1475 * Free a block or fragment.
1477 * The specified block or fragment is placed back in the
1478 * free map. If a fragment is deallocated, a possible
1479 * block reassembly is checked.
1482 ffs_blkfree_cg(struct fs
* fs
, struct vnode
* i_devvp
, cdev_t i_dev
, ino_t i_number
,
1483 uint32_t i_din_uid
, ufs_daddr_t bno
, long size
)
1488 int i
, error
, cg
, blk
, frags
, bbase
;
1491 VOP_FREEBLKS(i_devvp
, fsbtodoff(fs
, bno
), size
);
1492 if ((uint
)size
> fs
->fs_bsize
|| fragoff(fs
, size
) != 0 ||
1493 fragnum(fs
, bno
) + numfrags(fs
, size
) > fs
->fs_frag
) {
1494 kprintf("dev=%s, bno = %ld, bsize = %ld, size = %ld, fs = %s\n",
1495 devtoname(i_dev
), (long)bno
, (long)fs
->fs_bsize
, size
,
1497 panic("ffs_blkfree: bad size");
1500 if ((uint
)bno
>= fs
->fs_size
) {
1501 kprintf("bad block %ld, ino %lu\n",
1502 (long)bno
, (u_long
)i_number
);
1503 ffs_fserr(fs
, i_din_uid
, "bad block");
1508 * Load the cylinder group
1510 error
= bread(i_devvp
, fsbtodoff(fs
, cgtod(fs
, cg
)),
1511 (int)fs
->fs_cgsize
, &bp
);
1516 cgp
= (struct cg
*)bp
->b_data
;
1517 if (!cg_chkmagic(cgp
)) {
1521 cgp
->cg_time
= time_second
;
1522 bno
= dtogd(fs
, bno
);
1523 blksfree
= cg_blksfree(cgp
);
1525 if (size
== fs
->fs_bsize
) {
1527 * Free a whole block
1529 blkno
= fragstoblks(fs
, bno
);
1530 if (!ffs_isfreeblock(fs
, blksfree
, blkno
)) {
1531 kprintf("dev = %s, block = %ld, fs = %s\n",
1532 devtoname(i_dev
), (long)bno
, fs
->fs_fsmnt
);
1533 panic("ffs_blkfree: freeing free block");
1535 ffs_setblock(fs
, blksfree
, blkno
);
1536 ffs_clusteracct(fs
, cgp
, blkno
, 1);
1537 cgp
->cg_cs
.cs_nbfree
++;
1538 fs
->fs_cstotal
.cs_nbfree
++;
1539 fs
->fs_cs(fs
, cg
).cs_nbfree
++;
1540 i
= cbtocylno(fs
, bno
);
1541 cg_blks(fs
, cgp
, i
)[cbtorpos(fs
, bno
)]++;
1542 cg_blktot(cgp
)[i
]++;
1545 * Free a fragment within a block.
1547 * bno is the starting block number of the fragment being
1550 * bbase is the starting block number for the filesystem
1551 * block containing the fragment.
1553 * blk is the current bitmap for the fragments within the
1554 * filesystem block containing the fragment.
1556 * frags is the number of fragments being freed
1558 * Call ffs_fragacct() to account for the removal of all
1559 * current fragments, then adjust the bitmap to free the
1560 * requested fragment, and finally call ffs_fragacct() again
1561 * to regenerate the accounting.
1563 bbase
= bno
- fragnum(fs
, bno
);
1564 blk
= blkmap(fs
, blksfree
, bbase
);
1565 ffs_fragacct(fs
, blk
, cgp
->cg_frsum
, -1);
1566 frags
= numfrags(fs
, size
);
1567 for (i
= 0; i
< frags
; i
++) {
1568 if (isset(blksfree
, bno
+ i
)) {
1569 kprintf("dev = %s, block = %ld, fs = %s\n",
1570 devtoname(i_dev
), (long)(bno
+ i
),
1572 panic("ffs_blkfree: freeing free frag");
1574 setbit(blksfree
, bno
+ i
);
1576 cgp
->cg_cs
.cs_nffree
+= i
;
1577 fs
->fs_cstotal
.cs_nffree
+= i
;
1578 fs
->fs_cs(fs
, cg
).cs_nffree
+= i
;
1581 * Add back in counts associated with the new frags
1583 blk
= blkmap(fs
, blksfree
, bbase
);
1584 ffs_fragacct(fs
, blk
, cgp
->cg_frsum
, 1);
1587 * If a complete block has been reassembled, account for it
1589 blkno
= fragstoblks(fs
, bbase
);
1590 if (ffs_isblock(fs
, blksfree
, blkno
)) {
1591 cgp
->cg_cs
.cs_nffree
-= fs
->fs_frag
;
1592 fs
->fs_cstotal
.cs_nffree
-= fs
->fs_frag
;
1593 fs
->fs_cs(fs
, cg
).cs_nffree
-= fs
->fs_frag
;
1594 ffs_clusteracct(fs
, cgp
, blkno
, 1);
1595 cgp
->cg_cs
.cs_nbfree
++;
1596 fs
->fs_cstotal
.cs_nbfree
++;
1597 fs
->fs_cs(fs
, cg
).cs_nbfree
++;
1598 i
= cbtocylno(fs
, bbase
);
1599 cg_blks(fs
, cgp
, i
)[cbtorpos(fs
, bbase
)]++;
1600 cg_blktot(cgp
)[i
]++;
1607 struct ffs_blkfree_trim_params
{
1613 * With TRIM, inode pointer is gone in the callback but we still need
1614 * the following fields for ffs_blkfree_cg()
1616 struct vnode
*i_devvp
;
1625 ffs_blkfree_trim_task(void *ctx
, int pending
)
1627 struct ffs_blkfree_trim_params
*tp
;
1630 ffs_blkfree_cg(tp
->i_fs
, tp
->i_devvp
, tp
->i_dev
, tp
->i_number
,
1631 tp
->i_din_uid
, tp
->bno
, tp
->size
);
1638 ffs_blkfree_trim_completed(struct bio
*biop
)
1640 struct buf
*bp
= biop
->bio_buf
;
1641 struct ffs_blkfree_trim_params
*tp
;
1643 tp
= bp
->b_bio1
.bio_caller_info1
.ptr
;
1644 TASK_INIT(&tp
->task
, 0, ffs_blkfree_trim_task
, tp
);
1645 tp
= biop
->bio_caller_info1
.ptr
;
1646 taskqueue_enqueue(taskqueue_swi
, &tp
->task
);
1652 * If TRIM is enabled, we TRIM the blocks first then free them. We do this
1653 * after TRIM is finished and the callback handler is called. The logic here
1654 * is that we free the blocks before updating the bitmap so that we don't
1655 * reuse a block before we actually trim it, which would result in trimming
1659 ffs_blkfree(struct inode
*ip
, ufs_daddr_t bno
, long size
)
1661 struct mount
*mp
= ip
->i_devvp
->v_mount
;
1662 struct ffs_blkfree_trim_params
*tp
;
1664 if (!(mp
->mnt_flag
& MNT_TRIM
)) {
1665 ffs_blkfree_cg(ip
->i_fs
, ip
->i_devvp
,ip
->i_dev
,ip
->i_number
,
1666 ip
->i_uid
, bno
, size
);
1672 tp
= kmalloc(sizeof(struct ffs_blkfree_trim_params
), M_TEMP
, M_WAITOK
);
1675 tp
->i_devvp
= ip
->i_devvp
;
1676 tp
->i_dev
= ip
->i_dev
;
1677 tp
->i_din_uid
= ip
->i_uid
;
1678 tp
->i_number
= ip
->i_number
;
1681 bp
= getnewbuf(0,0,0,1);
1683 bp
->b_cmd
= BUF_CMD_FREEBLKS
;
1684 bp
->b_bio1
.bio_offset
= fsbtodoff(ip
->i_fs
, bno
);
1685 bp
->b_bcount
= size
;
1686 bp
->b_bio1
.bio_caller_info1
.ptr
= tp
;
1687 bp
->b_bio1
.bio_done
= ffs_blkfree_trim_completed
;
1688 vn_strategy(ip
->i_devvp
, &bp
->b_bio1
);
1693 * Verify allocation of a block or fragment. Returns true if block or
1694 * fragment is allocated, false if it is free.
1697 ffs_checkblk(struct inode
*ip
, ufs_daddr_t bno
, long size
)
1702 int i
, error
, frags
, free
;
1706 if ((uint
)size
> fs
->fs_bsize
|| fragoff(fs
, size
) != 0) {
1707 kprintf("bsize = %ld, size = %ld, fs = %s\n",
1708 (long)fs
->fs_bsize
, size
, fs
->fs_fsmnt
);
1709 panic("ffs_checkblk: bad size");
1711 if ((uint
)bno
>= fs
->fs_size
)
1712 panic("ffs_checkblk: bad block %d", bno
);
1713 error
= bread(ip
->i_devvp
, fsbtodoff(fs
, cgtod(fs
, dtog(fs
, bno
))),
1714 (int)fs
->fs_cgsize
, &bp
);
1716 panic("ffs_checkblk: cg bread failed");
1717 cgp
= (struct cg
*)bp
->b_data
;
1718 if (!cg_chkmagic(cgp
))
1719 panic("ffs_checkblk: cg magic mismatch");
1720 blksfree
= cg_blksfree(cgp
);
1721 bno
= dtogd(fs
, bno
);
1722 if (size
== fs
->fs_bsize
) {
1723 free
= ffs_isblock(fs
, blksfree
, fragstoblks(fs
, bno
));
1725 frags
= numfrags(fs
, size
);
1726 for (free
= 0, i
= 0; i
< frags
; i
++)
1727 if (isset(blksfree
, bno
+ i
))
1729 if (free
!= 0 && free
!= frags
)
1730 panic("ffs_checkblk: partially free fragment");
1735 #endif /* DIAGNOSTIC */
1741 ffs_vfree(struct vnode
*pvp
, ino_t ino
, int mode
)
1743 if (DOINGSOFTDEP(pvp
)) {
1744 softdep_freefile(pvp
, ino
, mode
);
1747 return (ffs_freefile(pvp
, ino
, mode
));
1751 * Do the actual free operation.
1752 * The specified inode is placed back in the free map.
1755 ffs_freefile(struct vnode
*pvp
, ino_t ino
, int mode
)
1766 if ((uint
)ino
>= fs
->fs_ipg
* fs
->fs_ncg
)
1767 panic("ffs_vfree: range: dev = (%d,%d), ino = %"PRId64
", fs = %s",
1768 major(pip
->i_dev
), minor(pip
->i_dev
), ino
, fs
->fs_fsmnt
);
1769 cg
= ino_to_cg(fs
, ino
);
1770 error
= bread(pip
->i_devvp
, fsbtodoff(fs
, cgtod(fs
, cg
)),
1771 (int)fs
->fs_cgsize
, &bp
);
1776 cgp
= (struct cg
*)bp
->b_data
;
1777 if (!cg_chkmagic(cgp
)) {
1781 cgp
->cg_time
= time_second
;
1782 inosused
= cg_inosused(cgp
);
1784 if (isclr(inosused
, ino
)) {
1785 kprintf("dev = %s, ino = %lu, fs = %s\n",
1786 devtoname(pip
->i_dev
), (u_long
)ino
, fs
->fs_fsmnt
);
1787 if (fs
->fs_ronly
== 0)
1788 panic("ffs_vfree: freeing free inode");
1790 clrbit(inosused
, ino
);
1791 if (ino
< cgp
->cg_irotor
)
1792 cgp
->cg_irotor
= ino
;
1793 cgp
->cg_cs
.cs_nifree
++;
1794 fs
->fs_cstotal
.cs_nifree
++;
1795 fs
->fs_cs(fs
, cg
).cs_nifree
++;
1796 if ((mode
& IFMT
) == IFDIR
) {
1797 cgp
->cg_cs
.cs_ndir
--;
1798 fs
->fs_cstotal
.cs_ndir
--;
1799 fs
->fs_cs(fs
, cg
).cs_ndir
--;
1807 * Find a block of the specified size in the specified cylinder group.
1809 * It is a panic if a request is made to find a block if none are
1813 ffs_mapsearch(struct fs
*fs
, struct cg
*cgp
, ufs_daddr_t bpref
, int allocsiz
)
1816 int start
, len
, loc
, i
;
1817 int blk
, field
, subfield
, pos
;
1821 * find the fragment by searching through the free block
1822 * map for an appropriate bit pattern.
1825 start
= dtogd(fs
, bpref
) / NBBY
;
1827 start
= cgp
->cg_frotor
/ NBBY
;
1828 blksfree
= cg_blksfree(cgp
);
1829 len
= howmany(fs
->fs_fpg
, NBBY
) - start
;
1830 loc
= scanc((uint
)len
, (u_char
*)&blksfree
[start
],
1831 (u_char
*)fragtbl
[fs
->fs_frag
],
1832 (u_char
)(1 << (allocsiz
- 1 + (fs
->fs_frag
% NBBY
))));
1834 len
= start
+ 1; /* XXX why overlap here? */
1836 loc
= scanc((uint
)len
, (u_char
*)&blksfree
[0],
1837 (u_char
*)fragtbl
[fs
->fs_frag
],
1838 (u_char
)(1 << (allocsiz
- 1 + (fs
->fs_frag
% NBBY
))));
1840 kprintf("start = %d, len = %d, fs = %s\n",
1841 start
, len
, fs
->fs_fsmnt
);
1842 panic("ffs_alloccg: map corrupted");
1846 bno
= (start
+ len
- loc
) * NBBY
;
1847 cgp
->cg_frotor
= bno
;
1849 * found the byte in the map
1850 * sift through the bits to find the selected frag
1852 for (i
= bno
+ NBBY
; bno
< i
; bno
+= fs
->fs_frag
) {
1853 blk
= blkmap(fs
, blksfree
, bno
);
1855 field
= around
[allocsiz
];
1856 subfield
= inside
[allocsiz
];
1857 for (pos
= 0; pos
<= fs
->fs_frag
- allocsiz
; pos
++) {
1858 if ((blk
& field
) == subfield
)
1864 kprintf("bno = %lu, fs = %s\n", (u_long
)bno
, fs
->fs_fsmnt
);
1865 panic("ffs_alloccg: block not in map");
1870 * Update the cluster map because of an allocation or free.
1872 * Cnt == 1 means free; cnt == -1 means allocating.
1875 ffs_clusteracct(struct fs
*fs
, struct cg
*cgp
, ufs_daddr_t blkno
, int cnt
)
1879 u_char
*freemapp
, *mapp
;
1880 int i
, start
, end
, forw
, back
, map
, bit
;
1882 if (fs
->fs_contigsumsize
<= 0)
1884 freemapp
= cg_clustersfree(cgp
);
1885 sump
= cg_clustersum(cgp
);
1887 * Allocate or clear the actual block.
1890 setbit(freemapp
, blkno
);
1892 clrbit(freemapp
, blkno
);
1894 * Find the size of the cluster going forward.
1897 end
= start
+ fs
->fs_contigsumsize
;
1898 if (end
>= cgp
->cg_nclusterblks
)
1899 end
= cgp
->cg_nclusterblks
;
1900 mapp
= &freemapp
[start
/ NBBY
];
1902 bit
= 1 << (start
% NBBY
);
1903 for (i
= start
; i
< end
; i
++) {
1904 if ((map
& bit
) == 0)
1906 if ((i
& (NBBY
- 1)) != (NBBY
- 1)) {
1915 * Find the size of the cluster going backward.
1918 end
= start
- fs
->fs_contigsumsize
;
1921 mapp
= &freemapp
[start
/ NBBY
];
1923 bit
= 1 << (start
% NBBY
);
1924 for (i
= start
; i
> end
; i
--) {
1925 if ((map
& bit
) == 0)
1927 if ((i
& (NBBY
- 1)) != 0) {
1931 bit
= 1 << (NBBY
- 1);
1936 * Account for old cluster and the possibly new forward and
1939 i
= back
+ forw
+ 1;
1940 if (i
> fs
->fs_contigsumsize
)
1941 i
= fs
->fs_contigsumsize
;
1948 * Update cluster summary information.
1950 lp
= &sump
[fs
->fs_contigsumsize
];
1951 for (i
= fs
->fs_contigsumsize
; i
> 0; i
--)
1954 fs
->fs_maxcluster
[cgp
->cg_cgx
] = i
;
1958 * Fserr prints the name of a filesystem with an error diagnostic.
1960 * The form of the error message is:
1964 ffs_fserr(struct fs
*fs
, uint uid
, char *cp
)
1966 struct thread
*td
= curthread
;
1969 if ((p
= td
->td_proc
) != NULL
) {
1970 log(LOG_ERR
, "pid %d (%s), uid %d on %s: %s\n", p
? p
->p_pid
: -1,
1971 p
? p
->p_comm
: "-", uid
, fs
->fs_fsmnt
, cp
);
1973 log(LOG_ERR
, "system thread %p, uid %d on %s: %s\n",
1974 td
, uid
, fs
->fs_fsmnt
, cp
);