Home | History | Annotate | Download | only in newfs
History log of /src/sbin/newfs/mkfs.c
RevisionDateAuthorComments
 1.137  10-May-2024  andvar s/superbock/superblock/ in comment.
 1.136  22-Feb-2024  mrg if the window size works but is 0, assume it didn't work and use 80.
 1.135  05-Jul-2023  riastradh Revert "newfs(8): Ensure A divides S before aligned_alloc(A, S)."

C17 lifted this restriction.
 1.134  04-Jul-2023  riastradh newfs(8): Ensure A divides S before aligned_alloc(A, S).

Required by C11 Sec. 7.22.3.1 The aligned_alloc function, para. 2,
p. 348:

The value of alignment shall be a valid alignment supported by the
implementation and the value of size shall be an integral multiple
of alignment.

XXX pullup-10
 1.133  07-Jan-2023  chs ufs: fixed signed/unsigned bugs affecting large file systems

Apply these commits from FreeBSD:

commit e870d1e6f97cc73308c11c40684b775bcfa906a2
Author: Kirk McKusick <mckusick@FreeBSD.org>
Date: Wed Feb 10 20:10:35 2010 +0000

This fix corrects a problem in the file system that treats large
inode numbers as negative rather than unsigned. For a default
(16K block) file system, this bug began to show up at a file system
size above about 16Tb.

To fully handle this problem, newfs must be updated to ensure that
it will never create a filesystem with more than 2^32 inodes. That
patch will be forthcoming soon.

Reported by: Scott Burns, John Kilburg, Bruce Evans
Followup by: Jeff Roberson
PR: 133980
MFC after: 2 weeks

commit 81479e688b0f643ffacd3f335b4b4bba460b769d
Author: Kirk McKusick <mckusick@FreeBSD.org>
Date: Thu Feb 11 18:14:53 2010 +0000

One last pass to get all the unsigned comparisons correct.


In additional to the changes from FreeBSD, this commit includes quite a few
related changes to appease -Wsign-compare.
 1.132  17-Nov-2022  chs branches: 1.132.2;
Restore backward compatibility of UFS2 with previous NetBSD releases by
disabling support in UFS2 for extended attributes (including ACLs).
Add a new variant of UFS2 called "UFS2ea" that does support extended attributes.
Add new fsck_ffs operations "-c ea" and "-c no-ea" to convert file systems
from UFS2 to UFS2ea and vice-versa (both of which delete all existing extended
attributes in the process).
 1.131  01-Jan-2022  msaitoh s/sytem/system/
 1.130  20-Aug-2020  riastradh mmap MAP_FAILED audit.
 1.129  17-Apr-2020  jdolecek align buffers used for I/O to DEV_BSIZE so it's executed more optimally
when run for xbd(4) device
 1.128  08-Feb-2017  rin branches: 1.128.12;
Add smaller versions of fsck_ffs(8) and newfs(8) for install media, where
support for Endian-Independent FFS and Apple UFS is disabled unless FFS_EI=1
and APPLE_UFS=1 are added to CRUNCHENV, respectively.

This reduces the size of ramdisk image for atari by over 15KB.

Thanks tsutsui and christos for their useful comments.
 1.127  07-Mar-2016  christos branches: 1.127.2; 1.127.4;
PR/50910: David Binderman: Optimize memset.
 1.126  07-Mar-2016  dholland Terminate expression with a semicolon, instead of accidentally
splicing to the next line with a comma. Noticed by Christos. Has no
actual effect, fortunately. (Compiler output is unchanged.)
 1.125  16-Jun-2015  christos fix error messages containing \n
 1.124  29-Apr-2015  christos - use calloc to zero memory
- pass the proper buffer to mkdir
- fix for apple ufs
 1.123  28-Apr-2015  christos reduce bss usage
 1.122  26-Apr-2014  martin Increase alignement of the global "buf" variable to cover all pointers it
is casted too. Fixes a crash on arm v5.
 1.121  05-Apr-2014  justin branches: 1.121.2;
Iterate over fields of struct seperately to avoid warnings from pedantic compilers
 1.120  23-Jun-2013  dholland Stick ffs_ in front of the following macros:
fragstoblks()
blkstofrags()
fragnum()
blknum()

to finish the job of distinguishing them from the lfs versions, which
Christos renamed the other day.

I believe this is the last of the overtly ambiguous exported symbols
from ffs... or at least, the last of the ones that conflicted with lfs.
ffs still pollutes the C namespace very broadly (as does ufs) and this
needs quite a bit more cleanup.

XXX: boo on macros with lowercase names. But I'm not tackling that just yet.
 1.119  23-Jun-2013  dholland Stick ffs_, ext2_, chfs_, filecore_, cd9660_, or mfs_ in front of
the following symbols so as to disambiguate fully. (Christos already
did the lfs ones.)

lblkno
lblktosize
lfragtosize
numfrags
blkroundup
fragroundup
 1.118  23-Jun-2013  dholland Revert accidental commit of the change for PR 47911; got rolled into
other stuff by mistake.
 1.117  23-Jun-2013  dholland fsbtodb() -> FFS_FSBTODB(), EXT2_FSBTODB(), or MFS_FSBTODB()
dbtofsb() -> FFS_DBTOFSB() or EXT2_DBTOFSB()

(Christos already did the lfs ones a few days back)
 1.116  19-Jun-2013  dholland Rename ambiguous macros:
MAXDIRSIZE -> UFS_MAXDIRSIZE or LFS_MAXDIRSIZE
NINDIR -> FFS_NINDIR, EXT2_NINDIR, LFS_NINDIR, or MFS_NINDIR
INOPB -> FFS_INOPB, LFS_INOPB
INOPF -> FFS_INOPF, LFS_INOPF
blksize -> ffs_blksize, ext2_blksize, or lfs_blksize
sblksize -> ffs_blksize

These are not the only ambiguously defined filesystem macros, of
course, there's a pile more. I may not have found all the ambiguous
definitions of blksize(), too, as there are a lot of other things
called 'blksize' in the system.
 1.115  09-Jun-2013  dholland Stick UFS_ in front of these symbols:
DIRBLKSIZ
DIRECTSIZ
DIRSIZ
OLDDIRFMT
NEWDIRFMT

Part of PR 47909.

(two stragglers in this commit; oops)
 1.114  17-Mar-2013  mlelstv For MFS, no longer use heuristic based on rlimit to determine mmap size.
This is no longer functional with current memory allocation routines.
 1.113  22-Jan-2013  dholland Stuff UFS_ in front of a few of ufs's symbols to reduce namespace
pollution. Specifically:
ROOTINO -> UFS_ROOTINO
WINO -> UFS_WINO
NXADDR -> UFS_NXADDR
NDADDR -> UFS_NDADDR
NIADDR -> UFS_NIADDR
MAXSYMLINKLEN -> UFS_MAXSYMLINKLEN
MAXSYMLINKLEN_UFS[12] -> UFS[12]_MAXSYMLINKLEN (for consistency)

Sort out ext2fs's misuse of NDADDR and NIADDR; fortunately, these have
the same values in ext2fs and ffs.

No functional change intended.
 1.112  13-Feb-2012  wiz branches: 1.112.6;
Remove unused variables.
From cppcheck via Henning Petersen in PR 46004.
 1.111  07-Feb-2012  tsutsui Explicitly zap possible Ext2fs magic leftover to prevent
kernel vfs_mountroot() and bootloaders from mis-recognizing
the newfs(8)'ed file system as still Ext2fs.

The problem is reported and the fix is tested by Frank Wille
on current-users@. Also approved by releng.
 1.110  25-Aug-2011  joerg branches: 1.110.2;
Avoid magic manipulation of the format string.
 1.109  06-Mar-2011  bouyer merge the bouyer-quota2 branch. This adds a new on-disk format
to store disk quota usage and limits, integrated with ffs
metadata. Usage is checked by fsck_ffs (no more quotacheck)
and is covered by the WAPBL journal. Enabled with kernel
option QUOTA2 (added where QUOTA was enabled in kernel config files),
turned on with tunefs(8) on a per-filesystem
basis. mount_mfs(8) can also turn quotas on.

See http://mail-index.netbsd.org/tech-kern/2011/02/19/msg010025.html
for details.
 1.108  09-Aug-2010  pooka branches: 1.108.2;
Add -G, which turns consistency check errors in warnings. The
current testing purpose is to create a file system with
block size > MAXPHYS.

(the check doesn't make that much sense anyway in these days of
mobile file systems, since we're interested in MAXPHYS where we
attempt to mount the file system, not where we happen to create it)
 1.107  31-Jan-2010  mlelstv Skip handling of APPLEUFS_LABEL if it is smaller than a device block.
In particular:

- newfs will not try to erase the label
- fsck_ffs will not try to validate the label

This lets newfs and fsck work on 2048-byte-per-sector media.

Does Apple UFS support such media and how?
 1.106  07-May-2009  lukem Consistently use FFSv1 or FFSv2
 1.105  11-Apr-2009  lukem fix sign-compare issues
 1.104  08-Dec-2007  jnemeth branches: 1.104.14;
PR/37155 - Marcelo Schmidt -- specifying too large of a size causes segvs
 1.103  27-Nov-2007  tsutsui branches: 1.103.2;
Use powerof2() macro in <sys/param.h> rather than a homegrown version.
 1.102  16-Oct-2006  christos branches: 1.102.2; 1.102.4; 1.102.8;
c99 initializers.
 1.101  26-Aug-2006  christos - Deal with wedges and the new disk geometry structures, instead of using
struct disklabel.

Functionality lost:
1. struct disklabel used to be updated to contain bsize, fsize, cpg.
This information was used to locate the alternative superblock in
the filesystem if the primary superblock was corrupted. We need
to find a new place to store this information if we need this
functionality.
2. On vax SMD drives that contained bad sector lists, the newfs program
knew how to get the offset and skip to the correct location in order
to place the label.
 1.100  21-Jan-2006  simonb Use 64-bit arithmetic to calculate fragsperinodeblk, avoiding 32-bit
overflows for large values of "-i bytes-per-inode".
 1.99  16-Jan-2006  dsl Add '-V' to usage output.
Correct a couple of comments.
 1.98  15-Jan-2006  dsl Add a '-V verbose' option that controls the amount of info writen to stdout.
0: No output. Default for mount_mfs unless -N specified
1: Output size of partition and cylinder groups.
2: Follow with a progress-bar line of dots (scaled to finish at RH margin)
3: Include a single line of alternate suberblock addresses before progress
bar. Default for newfs.
4: Output lots of lines of alternate superblock numbers that scroll madly
up the screen.
If -N given, newfs/mount_mfs exits before displaying any progress bar.
Output constrained (almost always) to 1 column less than the terminal width.
 1.97  11-Jan-2006  dsl Don't look for old superblocks if newfs -N
 1.96  11-Jan-2006  dsl The 'cylinder group' size calculation was incorrect. If the cylinder groups
were full then not enough bits were left for the inode allocation map.
Always put a multiple of 8 fragments (and non-zero) inodes into the eqns
so that answer is correct.
Fix the sum that may discard the last cylinder group if it isn't large enough
to contain all its inodes.
Spotted during some other tests, eg:
$ newfs -s 109610 -n1 -f512 -b4096 -N -O2 -F ./z
CGSIZE miscalculated 4097 > 4096
$
 1.95  11-Jan-2006  dsl Modify previous so that at most 79 (more likely 78) dots are printed, with
at most 1 dot per cylinder group.
This is much more useful for filesystems with very large numbers of cgs.
 1.94  09-Jan-2006  dsl There really isn't any point reporting all the alternate superblocks,
big filesystems can have thousands of them - no one ever writes them down.
After the first line of numbers just output a '.' for each cylinder group.
Also limit the lines to 79 columns so broken terminal emulaters don't
double-space the output lines.
 1.93  05-Jan-2006  hubertf The -b option is really on fsck_ffs, not fsck
Pointed out by Sebastian Schuetz on IRCnet #NetBSD
 1.92  05-Nov-2005  chs don't set fs_maxsymlinklen and fs_old_inodefmt twice,
we set them correctly the first time. fixes PR 26995.
 1.91  23-Aug-2005  tron Use FFS_MAXNAMLEN instead of MAXNAMLEN.
 1.90  19-Aug-2005  christos 64 bit inode changes
 1.89  03-Jun-2005  dbj ufs2 disk addresses in dp2->di_db[] must be swapped with bswap64, not bswap32
 1.88  14-Apr-2004  dbj branches: 1.88.2;
fix support for creating APPLE_UFS filesystems with -v
this addresses pr/23924

this includes most of support for creating fslevel 3 compatible filesystems,
although there is currently no command line option to invoke it when
not using apple_ufs
 1.87  18-Mar-2004  dsl branches: 1.87.2;
Speed up mkfs of ffsv1 by writing inodes more than 8k at a time.
Use mmap() instead of malloc() for temporary buffers so that they
can be unmapped for mfs.
 1.86  07-Mar-2004  dsl Re-instate the old behaviour where 'mount_mfs device mount_pt' would
use the size of 'device' for teh file syste size - fixes pr 18353.
(It might be better to be able to say 50% of the size...)
Fix 'mount_mfs -N ...', as well as supressing the creation of the fs, the -N
inhibits the supression of the prints of the mfs parameters.
 1.85  02-Jan-2004  dbj add uuid field to apple ufs volume label
 1.84  29-Oct-2003  lukem Under no circumstances try to zap an existing superblock at sector 0.
There's no reasonable situation where there will be one there, except if the
disk had data on it previously for some reason. It's significantly more
likely (read "the world until UFS2 was merged") that sector 0(..15)
contains really important stuff like boot blocks and disk labels.

Once again, I ask, why wasn't UFS2 implemented as a separate file
system a la lfs & ext2fs ?
It could have shared a chunk of the kernel code (just like those),
and had different userland tools and a different fs_type.
 1.83  15-Oct-2003  dsl The 'struct partition *pp' is only used to save the block and fragment
sizes (so they can be written back into the disklabel).
Allow pp to be NULL
 1.82  17-Sep-2003  enami Need to write entire sector.
 1.81  11-Sep-2003  dsl Make mkfs -N work again (was trying to read filesystem).
Correct calculation of number of inodes from density for small filesystems.
Add a '-n inodes' option so that the desired number of inodes can be
explicitly given - init needs this for mfs /dev, -i density is too crude.
 1.80  10-Sep-2003  dsl Try very hard to ensure that the correct superblock will be found by
invalidating a host of other possible superblocks.
 1.79  06-Sep-2003  itojun use arc4random
 1.78  04-Sep-2003  itojun s/0x7fffffff/INT32_MAX/
 1.77  04-Sep-2003  itojun use arc4random(3). it is at least better than random(3)
XXX masked topmost bit so that values don't go negative, is it the right thing
to do?
 1.76  03-Sep-2003  dsl Ensure the area between the end of the main superblock and the start of the
first alternate superblock is zerod.
Removes any possibility of any programs using a trully out of date
alternate superblock if a filesystem is remade with a larger block size.
 1.75  03-Sep-2003  dsl Randomise di_igen for the first 2 blocks of inodes for non-UFS2 filesystems.
Randomise di_igen for "/" (and lost+found) for UFS2 filesystems.
Ensure nothing from the lost+found inode leaks into the / inode.
 1.74  21-Aug-2003  dsl Rework of code that sorts out number of cylinder groups and inodes:
- allows less than 'one fragment per inode' (useful for mfs /dev)
- limits number of inodes to 2^31 (they are stored in an int32_t)
- errors if the number of cylinder groups is such that the cylinder group
summary won't fit in the first cylinder group.
- ensures that the last cylinder block contains a valid number of fragments
and inodes, and is not larger than any earlier ones.
- cylinder groups are now created with almost the same size as each other.
Change posted to tech-kern, and no one objected.
 1.73  15-Aug-2003  dsl Avoid allocating a data buffer the size of the cylinder group summary.
Write the summary every time it fills a fragment - except for the first
sector which is written last.
 1.72  15-Aug-2003  dsl Fix layout of printout of alternate superblock list when > 2^32 sectors, use
80 columns (sysinst uses full width these days).
Use {;} instead of , in a couple of places.
Abort if user tries to make a UFS1 filesytem with > 2^31 fragments.
Abort if the cylinder group summary won't fit into the first cylinder group.
Use pread/pwrite and remove a few redundant casts.
 1.71  07-Aug-2003  agc Move UCB-licensed code from 4-clause to 3-clause licence.

Patches provided by Joel Baker in PR 22308, verified by myself.
 1.70  02-May-2003  atatat Convert to using gettimeofday(2) instead of time(3) to get the current
time, and stuff as much precision as possible into as many places as
possible. This includes setting the atime, mtime, and ctime on inode
#2 of a freshly created file system, and the birthtime on a new ffs2
filesystem.

Previously these would all be left at zero, and since the birthtime
only gets set when the inode is allocated (and since inode #2 never
gets recycled), inode #2 would always have a birthtime of the epoch.
 1.69  20-Apr-2003  christos PR/5680: Markus Illenseer: Mounting and using broken mfs results into kernel
panic
Fixed by checking two return cases from alloc() that were not checked before.
 1.68  02-Apr-2003  fvdl Add support for UFS2. UFS2 is an enhanced FFS, adding support for
64 bit block pointers, extended attribute storage, and a few
other things.

This commit does not yet include the code to manipulate the extended
storage (for e.g. ACLs), this will be done later.

Originally written by Kirk McKusick and Network Associates Laboratories for
FreeBSD.
 1.67  14-Feb-2003  grant 'NetBSD.org' and some mdoc fixes.
 1.66  24-Jan-2003  fvdl Bump daddr_t to 64 bits. Replace it with int32_t in all places where
it was used on-disk, so that on-disk formats remain the same.
Remove ufs_daddr_t and ufs_lbn_t for the time being.
 1.65  28-Sep-2002  dbj Add support for the Apple UFS variation on ffs
This is the bulk of PR #17345

The general approach is to use a run time deteriminable value
for DIRBLKSIZ. Additional allowances are included for using
MAXSYMLINKLEN with FS_42INODEFMT and a shift in the cylinder group
cluster summary count array. Support is added for managing
the Apple UFS volume label.
 1.64  10-Apr-2002  mycroft Some manual strength reduction.
 1.63  10-Apr-2002  mycroft Remove debugging output.
 1.62  10-Apr-2002  mycroft Use fs_fragshift more. Simplify a bunch of arithmetic involving NSPF().
 1.61  18-Jan-2002  lukem wrap some mfs specific code in #ifdef MFS
 1.60  07-Jan-2002  simonb Add the ability for the user, group and permissions of an MFS to be set
on the command line with the -u, -g and -p options respectively.
The old malloc() replacement (and related functions) didn't work with
the libc get{pw,gr}nam() functions so it was removed and a separate
memory allocation function added that is only called to allocate the
space for the MFS file system.
Also use a table for the usage flags instead of multiple fprintf()'s
with "if (mfs)" checks sprinkled through.
 1.59  31-Dec-2001  lukem don't bother printing a warning about the cylinder group size being
restricted if -c isn't given; it just confuses a user of newfs (and
the cpg info is printed as part of the display anyway), and prints an
unnecessary warning for mount_mfs.
 1.58  13-Dec-2001  lukem clamp bsize to MAXBSIZE
 1.57  14-Oct-2001  lukem fix error reporting in rdfs() and wtfs()
 1.56  24-Sep-2001  lukem the change of calculation of inodes per group in rev 1.52 was far too
aggressive; rework to be a bit less susceptable to round-off error.
now it's likely that the density might not be obtained with a small
filesystem with a large number of inodes (e.g -s 4M -i 1k), but that's
an extremely unlikely corner case that can easily be rectified with
command-line arguments.
fixed provided in private email by Takao Shinohara <shin@sm.sony.co.jp>
should resolve PRs [bin/14049] and [bin/14046]
 1.55  06-Sep-2001  lukem Incorporate the enhanced ffs_dirpref() by Grigoriy Orlov, as found in
FreeBSD (three commits; the initial work, man page updates, and a fix
to ffs_reload()), with the following differences:
- Be consistent between newfs(8) and tunefs(8) as to the options which
set and control the tuning parameters for this work (avgfilesize & avgfpdir)
- Use u_int16_t instead of u_int8_t to keep track of the number of
contiguous directories (suggested by Chuck Silvers)
- Work within our FFS_EI framework
- Ensure that fs->fs_maxclusters and fs->fs_contigdirs don't point to
the same area of memory

The new algorithm has a marked performance increase, especially when
performing tasks such as untarring pkgsrc.tar.gz, etc.

The original FreeBSD commit messages are attached:

=====
mckusick 2001/04/10 01:39:00 PDT
Directory layout preference improvements from Grigoriy Orlov <gluk@ptci.ru>.
His description of the problem and solution follow. My own tests show
speedups on typical filesystem intensive workloads of 5% to 12% which
is very impressive considering the small amount of code change involved.

------

One day I noticed that some file operations run much faster on
small file systems then on big ones. I've looked at the ffs
algorithms, thought about them, and redesigned the dirpref algorithm.

First I want to describe the results of my tests. These results are old
and I have improved the algorithm after these tests were done. Nevertheless
they show how big the perfomance speedup may be. I have done two file/directory
intensive tests on a two OpenBSD systems with old and new dirpref algorithm.
The first test is "tar -xzf ports.tar.gz", the second is "rm -rf ports".
The ports.tar.gz file is the ports collection from the OpenBSD 2.8 release.
It contains 6596 directories and 13868 files. The test systems are:

1. Celeron-450, 128Mb, two IDE drives, the system at wd0, file system for
test is at wd1. Size of test file system is 8 Gb, number of cg=991,
size of cg is 8m, block size = 8k, fragment size = 1k OpenBSD-current
from Dec 2000 with BUFCACHEPERCENT=35

2. PIII-600, 128Mb, two IBM DTLA-307045 IDE drives at i815e, the system
at wd0, file system for test is at wd1. Size of test file system is 40 Gb,
number of cg=5324, size of cg is 8m, block size = 8k, fragment size = 1k
OpenBSD-current from Dec 2000 with BUFCACHEPERCENT=50

You can get more info about the test systems and methods at:
http://www.ptci.ru/gluk/dirpref/old/dirpref.html

Test Results

tar -xzf ports.tar.gz rm -rf ports
mode old dirpref new dirpref speedup old dirprefnew dirpref speedup
First system
normal 667 472 1.41 477 331 1.44
async 285 144 1.98 130 14 9.29
sync 768 616 1.25 477 334 1.43
softdep 413 252 1.64 241 38 6.34
Second system
normal 329 81 4.06 263.5 93.5 2.81
async 302 25.7 11.75 112 2.26 49.56
sync 281 57.0 4.93 263 90.5 2.9
softdep 341 40.6 8.4 284 4.76 59.66

"old dirpref" and "new dirpref" columns give a test time in seconds.
speedup - speed increasement in times, ie. old dirpref / new dirpref.

------

Algorithm description

The old dirpref algorithm is described in comments:

/*
* Find a cylinder to place a directory.
*
* The policy implemented by this algorithm is to select from
* among those cylinder groups with above the average number of
* free inodes, the one with the smallest number of directories.
*/

A new directory is allocated in a different cylinder groups than its
parent directory resulting in a directory tree that is spreaded across
all the cylinder groups. This spreading out results in a non-optimal
access to the directories and files. When we have a small filesystem
it is not a problem but when the filesystem is big then perfomance
degradation becomes very apparent.

What I mean by a big file system ?

1. A big filesystem is a filesystem which occupy 20-30 or more percent
of total drive space, i.e. first and last cylinder are physically
located relatively far from each other.
2. It has a relatively large number of cylinder groups, for example
more cylinder groups than 50% of the buffers in the buffer cache.

The first results in long access times, while the second results in
many buffers being used by metadata operations. Such operations use
cylinder group blocks and on-disk inode blocks. The cylinder group
block (fs->fs_cblkno) contains struct cg, inode and block bit maps.
It is 2k in size for the default filesystem parameters. If new and
parent directories are located in different cylinder groups then the
system performs more input/output operations and uses more buffers.
On filesystems with many cylinder groups, lots of cache buffers are
used for metadata operations.

My solution for this problem is very simple. I allocate many directories
in one cylinder group. I also do some things, so that the new allocation
method does not cause excessive fragmentation and all directory inodes
will not be located at a location far from its file's inodes and data.
The algorithm is:
/*
* Find a cylinder group to place a directory.
*
* The policy implemented by this algorithm is to allocate a
* directory inode in the same cylinder group as its parent
* directory, but also to reserve space for its files inodes
* and data. Restrict the number of directories which may be
* allocated one after another in the same cylinder group
* without intervening allocation of files.
*
* If we allocate a first level directory then force allocation
* in another cylinder group.
*/

My early versions of dirpref give me a good results for a wide range of
file operations and different filesystem capacities except one case:
those applications that create their entire directory structure first
and only later fill this structure with files.

My solution for such and similar cases is to limit a number of
directories which may be created one after another in the same cylinder
group without intervening file creations. For this purpose, I allocate
an array of counters at mount time. This array is linked to the superblock
fs->fs_contigdirs[cg]. Each time a directory is created the counter
increases and each time a file is created the counter decreases. A 60Gb
filesystem with 8mb/cg requires 10kb of memory for the counters array.

The maxcontigdirs is a maximum number of directories which may be created
without an intervening file creation. I found in my tests that the best
performance occurs when I restrict the number of directories in one cylinder
group such that all its files may be located in the same cylinder group.
There may be some deterioration in performance if all the file inodes
are in the same cylinder group as its containing directory, but their
data partially resides in a different cylinder group. The maxcontigdirs
value is calculated to try to prevent this condition. Since there is
no way to know how many files and directories will be allocated later
I added two optimization parameters in superblock/tunefs. They are:

int32_t fs_avgfilesize; /* expected average file size */
int32_t fs_avgfpdir; /* expected # of files per directory */

These parameters have reasonable defaults but may be tweeked for special
uses of a filesystem. They are only necessary in rare cases like better
tuning a filesystem being used to store a squid cache.

I have been using this algorithm for about 3 months. I have done
a lot of testing on filesystems with different capacities, average
filesize, average number of files per directory, and so on. I think
this algorithm has no negative impact on filesystem perfomance. It
works better than the default one in all cases. The new dirpref
will greatly improve untarring/removing/coping of big directories,
decrease load on cvs servers and much more. The new dirpref doesn't
speedup a compilation process, but also doesn't slow it down.

Obtained from: Grigoriy Orlov <gluk@ptci.ru>
=====

=====
iedowse 2001/04/23 17:37:17 PDT
Pre-dirpref versions of fsck may zero out the new superblock fields
fs_contigdirs, fs_avgfilesize and fs_avgfpdir. This could cause
panics if these fields were zeroed while a filesystem was mounted
read-only, and then remounted read-write.

Add code to ffs_reload() which copies the fs_contigdirs pointer
from the previous superblock, and reinitialises fs_avgf* if necessary.

Reviewed by: mckusick
=====

=====
nik 2001/04/10 03:36:44 PDT
Add information about the new options to newfs and tunefs which set the
expected average file size and number of files per directory. Could do
with some fleshing out.
=====
 1.54  02-Sep-2001  lukem Incorporate fix by iedowse @ FreeBSD to allow disks with large numbers of
cylinder groups to work correctly, with minor modifications by me to work
with our FFS_EI code. From the FreeBSD commit message:

The ffs superblock includes a 128-byte region for use by temporary
in-core pointers to summary information. An array in this region
(fs_csp) could overflow on filesystems with a very large number of
cylinder groups (~16000 on i386 with 8k blocks). When this happens,
other fields in the superblock get corrupted, and fsck refuses to
check the filesystem.

Solve this problem by replacing the fs_csp array in 'struct fs'
with a single pointer, and add padding to keep the length of the
128-byte region fixed. Update the kernel and userland utilities
to use just this single pointer.

With this change, the kernel no longer makes use of the superblock
fields 'fs_csshift' and 'fs_csmask'. Add a comment to newfs/mkfs.c
to indicate that these fields must be calculated for compatibility
with older kernels.

Reviewed by: mckusick
 1.53  30-Aug-2001  lukem some improvements from freebsd/openbsd
- replace the unused fs_headswitch and fs_trkseek with fs_id[2], bringing
our struct fs closer to that in freebsd & openbsd (& solaris FWIW)
- dumpfs: improve warning message when cpc == 0
 1.52  25-Aug-2001  lukem various calcipg() fixes:
- fix round-off errors when determining the number of inodes per group,
which often resulted in the total number of inodes in the file system
being less than what the density asked for.
now you might get more inodes than requested for a given density,
rather than less.
- if the new inodes/group is <= 0, ensure that it's at least 1, preventing
a possible division by zero or other wacky problems
- use long long instead of quad_t
 1.51  17-Aug-2001  lukem remove third argument (`int ns') from ffs_sb_swap(), and let ffs_sb_swap()
determine the endianness of the `struct fs *o' superblock from o->fs_magic
and set needswap as necessary, rather than trusting the caller to get
it right. invariably, almost every caller of ffs_sb_swap() was calling it
with ns set to the wrong value for ns anyway!
ansi KNF ffs_bswap.c declarations whilst here.

this fixes all sorts of problems when trying to use other-endian file systems,
notably the kernel trying to access memory *way* off, possibly corrupting or
panicing, and userland programs SEGVing and/or corrupting things (e.g,
"fsck_ffs -B" to swap a file system endianness).

whilst the previous rev of ffs_bswap.c (1.10, 2000/12/23) made this problem
worse, i suspect that the problem was always there and previous versions
just happened not to trash things at the wrong time.

FFS_EI should now be a lot more stable.
 1.50  31-Jul-2001  lukem revert rev 1.48 for now, until i'm sure the malloc (et al) rename is
safe (since there's two separate mallocs using sbrk(2) in that case)

XXX: local malloc provided for mfs memory store allocation; need to
investigate if system (phk) malloc can be used instead.
 1.49  30-Jul-2001  lukem - constify mkfs()'s first arg
- slightly reorder steps in -F image creation
 1.48  30-Jul-2001  lukem rename and hide: malloc->Malloc, calloc->Calloc, free->Free. (remove realloc)
 1.47  27-Jul-2001  lukem improve message describing MAXCSBUFS overflow
 1.46  27-Jul-2001  lukem s/filesystem/file system/
 1.45  26-Jul-2001  lukem clean up for WARNS=2 by renaming some local variables that shadow globals
 1.44  26-Jul-2001  lukem - check return value of calloc() in mkfs()
- in replacement malloc(), if sbrk(2) returns (void *)-1, convert to NULL
before returning
- in replacement calloc(), check return value of malloc() before zeroing result
 1.43  26-Jul-2001  lukem remove unnecessary duplicate initialisation of sblock.fs_clean
 1.42  23-Dec-2000  enami Don't swap clustersum[0]. It's not a cluster summery but block free bitmap.
 1.41  04-Dec-2000  scw Fix a bug introduced by 4.4-Lite:
Don't try to subtract the address of "acg.cg_firstfield" from
"acg.cg_nextfreeoff", as it's already relative to the start of "&acg".
This always worked because the result of the subtraction was
always negative, thus could never be > "sblock.fs_cgsize" ...
 1.40  01-Dec-2000  simonb Put extern variable declarations in "extern.h".
 1.39  01-Dec-2000  simonb ANSIfy.
 1.38  22-May-2000  bouyer branches: 1.38.4;
Check the number of cylinder group summary area against MAXCSBUFS. fsck and
the kernel will happilly trash data after fs_csp[] in the superblock with
a large number of cylinder group.
 1.37  30-Jul-1999  wrstuden Adjust column-sizing code to keep output in 76 character lines, so output
doesn't wrap in sysinst.
 1.36  14-May-1999  wrstuden Make newfs's spare superblock output nicer. Figure out how wide the
largest block number will be, and make the columns wide enough for it. Then
make enough columns to fit in an 80 character window.

Samples: small end & faked up values:

super-block backups (for fsck -b #) at:
32, 176, 272, 416, 512, 656, 752, 896, 992, 1136, 1232, 1376, 1472,
1616, 1712, 1856, 1952, 2096, 2192, 2336, 2432, 2576, 2672, 2816, 2912, 3056,
3152, 3296, 3392, 3536, 3632, 3776, 3872, 4016, 4112, 4256, 4352, 4496, 4592,

For a 155 GB fs we have:

super-block backups (for fsck -b #) at:
128, 65792, 131456, 197120, 262784, 328448, 394112,
459776, 525440, 591104, 656768, 722432, 788096, 853760,
919424, 985088, 1050752, 1116416, 1182080, 1247744, 1313408,
1379072, 1444736, 1510400, 1576064, 1641728, 1707392, 1773056,
...
317462144, 317527808, 317593472, 317659136, 317724800, 317790464, 317856128,
317921792, 317987456, 318053120, 318118784, 318184448, 318250112, 318315776,
318381440, 318447104, 318512768, 318578432,

Now it actually looks like someone's thought about making large fs's. :-)
 1.35  16-Mar-1999  wrstuden branches: 1.35.2;
Modify newfs so that the root node (and lost+found dir, if created)
of the new fs has uid.gid equal to the euid.egid of the process
which made it. This change permits users who have write access to
a device (say a floppy) to create a filesystem that, when mounted,
they have write access to.

This change closes PR bin/5990 from jbernard@ox.mines.edu, and is also the
change requested in PR bin/6276 from "Charles M. Hannum" <mycroft@netbsd.org>
 1.34  11-Mar-1999  wrstuden Modify how the byteswapping of the cylinder summaries is handled. If we
need to swap, allocate a buffer for the swapped summaries rather than using
writebuf. The latter is fixed at 64k, which is only enough room to hold
4096 summaries. Creating an fs with more results in a buffer overrun.

First noted by Matt Jacob mjacob@netbsd.org, and fixed by Albeaus
Bayucan, bayucan@nas.nasa.gov. Minor mods by me.
 1.33  03-Nov-1998  simonb Explicitly zero "node" before we start using it.
 1.32  23-Oct-1998  thorpej Use DINODE_SIZE instead of sizeof(struct dinode). Also, eliminate some
unnecessary pointer casts.
 1.31  01-Apr-1998  kleink Need <time.h> for time() prototype.
 1.30  18-Mar-1998  bouyer Allow creation of non-native byteorder FFS (via the '-B' option).
 1.29  01-Nov-1997  drochner Make "mount_mfs" behave synchronously - don't exit before the mount is
done. This has 2 advantages:
-The calling process can rely on the mounted filesystem.
-We get error messages if the mount system call fails.
 1.28  21-Sep-1997  jeremy branches: 1.28.2;
Quell gcc 2.7.2 initialization warning.
 1.27  16-Sep-1997  lukem * resolve conflicts from lite-2 import
* use int32_t instead of long
 1.26  30-Jun-1997  christos Fix compiler warnings.
 1.25  18-Jun-1995  cgd update for posixified stat structure
 1.24  11-Jun-1995  mycroft Back out previous change.
 1.23  07-Jun-1995  cgd typeof(timeval.tv_sec) != time_t
 1.22  06-May-1995  jtc flush stdout instead of stderr, so that each block number is displayed
as it is printed. From PR 989.
 1.21  12-Apr-1995  mycroft Set the `clean' flag.
 1.20  21-Mar-1995  cgd short -> int16_t in a couple of places
 1.19  18-Mar-1995  cgd convert to new RCS Id conventions; reduce my headache
 1.18  18-Mar-1995  cgd calculate the 'offset' argument to lseek() in a prettier way, more
consistent with the way fsck(8) does it. no functional change.
 1.17  04-Mar-1995  cgd flush stdout after printing each alternate superblock location.
 1.16  04-Mar-1995  cgd fix up inconsisten uses of lseek(). (three uses. one hard-coded 'whence'
as a number, one used an L_ constant and the other used a SEEK_ constant!)
 1.15  18-Dec-1994  cgd compile against new headers.
 1.14  18-Dec-1994  cgd type size paranoia, and allow one to mount an mfs on the device 'swap',
so that diskless machines can use MFS /tmp directories.
 1.13  31-Oct-1994  cgd types/field names.
 1.12  23-Sep-1994  mycroft Eliminate uses of some obsolete functions.
 1.11  20-Jul-1994  cgd fix from Peter Galbavy <peter@alice.wonderland.org>: don't overflow 80cols.
 1.10  20-Jul-1994  cgd fix that annoying 'cgd0: bad magic number' bug
 1.9  08-Jun-1994  mycroft branches: 1.9.2;
Update from 4.4-Lite, with local changes.
 1.8  25-Apr-1994  cgd various grunge
 1.7  01-Apr-1994  cgd off_t death...
 1.6  01-Oct-1993  mycroft Set clean flags.
 1.5  01-Aug-1993  mycroft Add RCS identifiers.
 1.4  28-Jul-1993  cgd incorporate changes from 0-9-base to 0-9-ALPHA
 1.3  23-Mar-1993  cgd branches: 1.3.2;
changed "Id" to "Header" for rcsids
 1.2  22-Mar-1993  cgd added rcs ids to all files
 1.1  21-Mar-1993  cgd branches: 1.1.1;
Initial revision
 1.1.1.3  16-Sep-1997  lukem imported from lite-2
 1.1.1.2  13-Jun-1994  mycroft Import 4.4-Lite version.
 1.1.1.1  21-Mar-1993  cgd initial import of 386bsd-0.1 sources
 1.3.2.1  20-Jul-1993  cgd change all refs to "mfs" to be to "mount_mfs" as is appropriate
 1.9.2.2  20-Jul-1994  cgd from trunk.
 1.9.2.1  20-Jul-1994  cgd update from trunk.
 1.28.2.1  02-Nov-1997  mellon Pull rev 1.29 up from trunk (drochner)
 1.35.2.1  01-Jun-2000  he Pull up revision 1.38 (requested by bouyer):
Abort if the number of cylinder group summary area is larger than
MAXCSBUFS.
 1.38.4.6  25-Nov-2001  he Pull up revisions 1.52,1.56-1.57 (requested by lukem):
Improve calcipg() calculations, and fix error reporting.
 1.38.4.5  25-Nov-2001  he Pull up revision 1.55 (requested by lukem):
Pull in enhanced ffs_dirpref() algorithm, which provides a
substantial performance improvement through better locality
between parent/child directories and their files, and by easing
the pressure on the buffer cache for metadata operations.
 1.38.4.4  25-Nov-2001  he Pull up revision 1.54 (requested by lukem):
Change fs_csp[] from being a fixed size to being an array sized
as required. This allows file systems with more than about 15500
cylinder groups (on 32-bit systems) to be used.
 1.38.4.3  25-Nov-2001  he Pull up revision 1.53 (requested by lukem):
Replace unused fs_headswitch/trkseek with fs_id.
 1.38.4.2  25-Nov-2001  he Pull up revision 1.51 (requested by lukem):
Call ffs_sb_swap() with the correct arguments. Fixes problems
with using other-endian file systems.
 1.38.4.1  24-Nov-2001  he Pull up revisions 1.39-1.47 (requested by lukem):
Jumbo pullup for newfs:
o convert to ANSI function prototypes
o move external variables to extern.h
o allow ``m'' suffix in MFS size
o fix cg_firstfield bug introduced in 4.4-Lite
o don't swap clustersum[0], it's a bitmap
o don't unnecessarily set fs_clean twice
o check return vailues of memory allocation functions
o cleanup to reduce compile warnings
o replace ``filesystem'' with ``file system''
o improve warning messages describing the MAXCSBUFS overflow
o manual page typos and other corrections
 1.87.2.2  06-Nov-2005  riz Pull up following revision(s) (requested by chs in ticket #5971):
sbin/newfs/mkfs.c: revision 1.92
don't set fs_maxsymlinklen and fs_old_inodefmt twice,
we set them correctly the first time. fixes PR 26995.
 1.87.2.1  27-Apr-2004  jdc branches: 1.87.2.1.2; 1.87.2.1.4;
Pull up revision 1.88 (requested by dbj in ticket #184)

fix support for creating APPLE_UFS filesystems with -v
this addresses pr/23924

this includes most of support for creating fslevel 3 compatible filesystems,
although there is currently no command line option to invoke it when
not using apple_ufs
 1.87.2.1.4.1  06-Nov-2005  riz Pull up following revision(s) (requested by chs in ticket #5971):
sbin/newfs/mkfs.c: revision 1.92
don't set fs_maxsymlinklen and fs_old_inodefmt twice,
we set them correctly the first time. fixes PR 26995.
 1.87.2.1.2.1  06-Nov-2005  riz Pull up following revision(s) (requested by chs in ticket #5971):
sbin/newfs/mkfs.c: revision 1.92
don't set fs_maxsymlinklen and fs_old_inodefmt twice,
we set them correctly the first time. fixes PR 26995.
 1.88.2.3  30-May-2009  snj Pull up following revision(s) (requested by jnemeth in ticket #2020):
sbin/newfs/mkfs.c: revision 1.104
PR/37155 - Marcelo Schmidt -- specifying too large of a size causes segvs
 1.88.2.2  05-Jan-2006  riz Pull up following revision(s) (requested by hubertf in ticket #1088):
sbin/newfs/mkfs.c: revision 1.93
The -b option is really on fsck_ffs, not fsck
Pointed out by Sebastian Schuetz on IRCnet #NetBSD
 1.88.2.1  06-Nov-2005  tron Pull up following revision(s) (requested by chs in ticket #935):
sbin/newfs/mkfs.c: revision 1.92
don't set fs_maxsymlinklen and fs_old_inodefmt twice,
we set them correctly the first time. fixes PR 26995.
 1.102.8.1  09-Jan-2008  matt sync with HEAD
 1.102.4.1  03-Jun-2008  skrll Sync with netbsd-4.
 1.102.2.1  02-Feb-2008  riz Pull up following revision(s) (requested by jnemeth in ticket #1024):
sbin/newfs/mount_mfs.8: revision 1.15
sbin/newfs/mkfs.c: revision 1.104
PR/37503 - De Zeurkous -- inaccurate description of -s option
PR/37155 - Marcelo Schmidt -- specifying too large of a size causes segvs
 1.103.2.2  27-Dec-2007  mjf Sync with HEAD.
 1.103.2.1  27-Nov-2007  mjf file mkfs.c was added on branch mjf-devfs on 2007-12-27 00:47:02 +0000
 1.104.14.1  13-May-2009  jym Sync with HEAD.

Third (and last) commit. See http://mail-index.netbsd.org/source-changes/2009/05/13/msg221222.html
 1.108.2.2  08-Feb-2011  bouyer Q2V -> QL
 1.108.2.1  20-Jan-2011  bouyer Snapshot of work in progress on a modernised disk quota system:
- new quotactl syscall (versionned for backward compat), which takes
as parameter a path to a mount point, and a prop_dictionary
(in plistref format) describing commands and arguments.
For each command, status and data are returned as a prop_dictionary.
quota commands features will be added to take advantage of this,
exporting quota data or getting quota commands as plists.

- new on disk-format storage (all 64bit wide), integrated to metadata for
ffs (and playing nicely with wapbl).
Quotas are enabled on a ffs filesystem via superblock flags.
tunefs(8) can enable or disable quotas.
On a quota-enabled filesystem, fsck_ffs(8) will track per-uid/gid
block and inode usages, and will check and update quotas in Pass 6.
quota usage and limits are stored in unliked files (one for users,
one for groups)l fsck_ffs(8) will create the files if needed, or
free them if needed. This means that after enabling or disabling
quotas on a filesystem; a fsck_ffs(8) run is required.
quotacheck(8) is not needed any more, on a unclean shutdown
fsck or journal replay will take care of fixing quotas.
newfs(8) can create a ready-to-mount quota-enabled filesystem
(superblock flags are set and quota inodes are created).
Other new features or semantic changes:
- default quota datas, applied to users or groups which don't already
have a quota entry
- per-user/group grace time (instead of a filesystem global one)
- 0 really means "nothing allowed at all", not "no limit".
If you want "no limit", set the limit to UQUAD_MAX (tools will
understand "unlimited" and "-")

A quota file is structured as follow:
it starts with a header, containing a few per-filesystem values,
and the default quota limits.
Quota entries are linked together as a simple list, each entry has a
pointer (as an offset withing the file) to the next.
The header has a pointer to a list of free quota entries, and
a hash table of in-use entries. The size of the hash table depends
on the filesystem block size (header+hash table should fit in the
first block). The file is not sparse and is a multiple of
filesystem block size (when the free quota entry list is empty a new
filesystem block is allocated). quota entries to not cross
filesystem block boundaries.

In memory, the kernel keeps a cache of recently used quota entries
as a reference to the block number, and offset withing the block.
The quota entry itself is keept in the buf cache.

fsck_ffs(8), tunefs(8) and newfs(8) supports are completed (with
related atf tests :)
The kernel can update disk usage and report it via quotactl(2).

Todo: enforce quotas limits (limits are not checked by kernel yet)
update repquota, edquota and rpc.rquotad to the new world
implement compat_50_quotactl ioctl.
update quotactl(2) man page

fsck_ffs required fixes so that allocating new blocks or inodes will
properly update the superblock and cg sumaries. This was not an issue up
to now because superblock and cg sumaries check happened last, but now
allocations or frees can happen in pass 6.
 1.110.2.3  22-May-2014  yamt sync with head.

for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.

this commit was splitted into small chunks to avoid
a limitation of cvs. ("Protocol error: too many arguments")
 1.110.2.2  23-Jan-2013  yamt sync with head
 1.110.2.1  17-Apr-2012  yamt sync with head
 1.112.6.3  20-Aug-2014  tls Rebase to HEAD as of a few days ago.
 1.112.6.2  23-Jun-2013  tls resync from head
 1.112.6.1  25-Feb-2013  tls resync with head
 1.121.2.1  10-Aug-2014  tls Rebase.
 1.127.4.1  21-Apr-2017  bouyer Sync with HEAD
 1.127.2.1  20-Mar-2017  pgoyette Sync with HEAD
 1.128.12.1  21-Apr-2020  martin Sync with HEAD
 1.132.2.1  13-May-2023  martin Pull up following revision(s) (requested by chs in ticket #160):

usr.sbin/makefs/ffs/ffs_alloc.c: revision 1.31
sbin/tunefs/tunefs.c: revision 1.58
sbin/fsck_ffs/setup.c: revision 1.105
sbin/fsck_ffs/pass5.c: revision 1.56
usr.sbin/makefs/ffs.c: revision 1.74
usr.sbin/makefs/ffs/mkfs.c: revision 1.42
usr.sbin/makefs/Makefile: revision 1.40
sys/ufs/ffs/fs.h: revision 1.71
sbin/fsdb/fsdb.c: revision 1.54
sbin/resize_ffs/resize_ffs.c: revision 1.58
sbin/fsck_ffs/pass4.c: revision 1.29
usr.sbin/makefs/ffs/ffs_extern.h: revision 1.9
sbin/newfs/mkfs.c: revision 1.133
sys/ufs/ffs/ffs_alloc.c: revision 1.172
sbin/fsck_ffs/pass1b.c: revision 1.24
usr.sbin/dumpfs/dumpfs.c: revision 1.68
sys/ufs/ffs/ffs_extern.h: revision 1.88
usr.sbin/quotacheck/quotacheck.c: revision 1.51
sys/ufs/ffs/ffs_subr.c: revision 1.54
sbin/fsck_ffs/main.c: revision 1.91
sbin/fsck_ffs/pass1.c: revision 1.63

ufs: fixed signed/unsigned bugs affecting large file systems

Apply these commits from FreeBSD:
commit e870d1e6f97cc73308c11c40684b775bcfa906a2
Author: Kirk McKusick <mckusick@FreeBSD.org>
Date: Wed Feb 10 20:10:35 2010 +0000
This fix corrects a problem in the file system that treats large
inode numbers as negative rather than unsigned. For a default
(16K block) file system, this bug began to show up at a file system
size above about 16Tb.
To fully handle this problem, newfs must be updated to ensure that
it will never create a filesystem with more than 2^32 inodes. That
patch will be forthcoming soon.
Reported by: Scott Burns, John Kilburg, Bruce Evans
Followup by: Jeff Roberson
PR: 133980
MFC after: 2 weeks

commit 81479e688b0f643ffacd3f335b4b4bba460b769d
Author: Kirk McKusick <mckusick@FreeBSD.org>
Date: Thu Feb 11 18:14:53 2010 +0000
One last pass to get all the unsigned comparisons correct.

In additional to the changes from FreeBSD, this commit includes quite a few
related changes to appease -Wsign-compare.

RSS XML Feed