Home | History | Annotate | only in /src/sbin/newfs
History log of /src/sbin/newfs
RevisionDateAuthorComments
 1.42 03-Jun-2023  lukem bsd.own.mk: rename to CC_WNO_ADDRESS_OF_PACKED_MEMBER

Provide a single variable
CC_WNO_ADDRESS_OF_PACKED_MEMBER
with options for both clang and gcc, to replace
CLANG_NO_ADDR_OF_PACKED_MEMBER
CC_NO_ADDR_OF_PACKED_MEMBER
GCC_NO_ADDR_OF_PACKED_MEMBER

Using the convention CC_compilerflag, where compilerflag
is based on the full compiler flag name.
 1.41 06-Sep-2020  mrg add support for new GCC 9 warnings that may be too much to fix
right now. new address-of-packed-member and format-overflow
warnings have new GCC_NO_ADDR_OF_PACKED_MEMBER amd
GCC_NO_FORMAT_OVERFLOW variables to remove these warnings.

apply to a bunch of the tree. mostly, these are real bugs that
should be fixed, but in many cases, only by removing the 'packed'
attribute from some structure that doesn't really need it. (i
looked at many different ones, and while perhaps 60-80% were
already properly aligned, it wasn't clear to me that the uses
were always coming from sane data vs network alignment, so it
doesn't seem safe to remove packed without careful research for
each affect struct.) clang already warned (and was not erroring)
for many of these cases, but gcc picked up dozens more.
 1.40 08-Feb-2017  rin 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.39 10-Aug-2012  joerg branches: 1.39.14; 1.39.18;
Don't depend on HAVE_GCC being always defined.
 1.38 20-Jun-2011  mrg branches: 1.38.2;
remove most of the remaining HAVE_GCC tests that are always true in
the modern world.
 1.37 06-Mar-2011  bouyer branches: 1.37.2;
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.36 09-Aug-2010  pooka branches: 1.36.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.35 20-Dec-2009  dsl Push the mount path for mount_mfs through realpath().
This matches what other fs do.
Fixes PR/20362
 1.34 06-Jun-2009  haad Remove debuging CFLAGS.
 1.33 05-Jun-2009  haad Add support for DIOCGDISKINFO to disk like device drivers. Change
partutil.c::getdiskinfo to use it to get disk geometry info.
Use DIOCGWEDGEINFO ioctl to get information about partition size, if disk
driver doesn't support it use old DIOCGDINFO. This patch adds support for
wedge like devices(lvm logical volumes, ZFS zvol partitions) to newfs and
other tools.

No objections on tech-userlevel@.
 1.32 29-Aug-2008  gmcgarry Wrap compiler-specific flags with HAVE_GCC and HAVE_PCC as necessary. Add a few flags for PCC.
 1.31 26-Aug-2006  christos branches: 1.31.18; 1.31.22;
- 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.30 11-May-2006  mrg sprinkle some -fno-strict-aliasing and -Wno-pointer-sign with GCC4.
 1.29 27-Jun-2005  christos Move WARNS=3 to the Makefile.inc, and add a little const to the remaining
programs that did not compile before.
 1.28 01-Nov-2003  dsl Use fstat(2) to get the partition size (falling back to the label on old
kernels) so that newfs works on vinum (and similar).
Kill the -V hack for vinum.
Don't bother faking up a label for -F and mfs, nothing is needed from it.
Ignore label if special doesn't match DISKPART(sb.st_rdev);
Simplifly logic for default block/frag sizes.
Update man page to match.
WARNS=3.
 1.27 26-Oct-2003  mycroft Remove alpha optimization hack.
 1.26 22-Mar-2003  jdolecek no need for -I${MOUNT} & .PATH: ${MOUNT} now neither
 1.25 22-Mar-2003  tron Remove "getmntopts.c" from list of source files. getmntopts(3) is in
"libutil" now.
 1.24 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.23 19-Aug-2002  lukem Use ${NETBSDSRCDIR}/some/path instead of ${.CURDIR}/../../some/path
 1.22 08-Jan-2002  thorpej Use MACHINE_ARCH, not MACHINE.
 1.21 06-Jan-2002  lukem add ugly hack for alpha to crank the optimisation level down to -O1,
because the default -O2 with gcc 2.95.3 builds a non functional newfs
 1.20 04-Jan-2002  lukem remove duplicate MAN= entry
 1.19 04-Jan-2002  lukem move mount_mfs(8) into separate man page
 1.18 29-Jul-2001  lukem enable WARNS=2
 1.17 15-Jan-1999  bouyer #include machine/bswap.h and remove -lutil.
 1.16 18-Mar-1998  bouyer Allow creation of non-native byteorder FFS (via the '-B' option).
 1.15 10-Oct-1997  christos CFLAGS->CPPFLAGS
 1.14 15-Sep-1997  lukem define WARNS?=1 for all of sbin/*
 1.13 30-Jun-1997  christos Fix compiler warnings.
 1.12 08-May-1997  gwr Back out the .PATH.c changes. The .depend problem (and others)
will be fixed using the new .NOPATH make feature instead.
 1.11 06-May-1997  gwr Use .PATH.c: ...
 1.10 16-May-1996  thorpej Use getmaxpartitions() from libutil, not a homegrown version.
 1.9 18-Mar-1995  cgd convert to new RCS Id conventions; reduce my headache
 1.8 22-Dec-1994  cgd specify man pages the new way.
 1.7 08-Jun-1994  mycroft Update from 4.4-Lite, with local changes.
 1.6 12-Feb-1994  chopps added -D${MACHINE} for amiga's becuase of differing sizeof (struct disklabel)
 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.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.31.22.1 18-Sep-2008  wrstuden Sync with wrstuden-revivesa-base-2.
 1.31.18.1 28-Sep-2008  mjf Sync with HEAD.
 1.36.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.37.2.1 23-Jun-2011  cherry Catchup with rmind-uvmplock merge.
 1.38.2.1 30-Oct-2012  yamt sync with head
 1.39.18.1 21-Apr-2017  bouyer Sync with HEAD
 1.39.14.1 20-Mar-2017  pgoyette Sync with HEAD
 1.1 08-Feb-2017  rin branches: 1.1.2; 1.1.4;
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.1.4.2 21-Apr-2017  bouyer Sync with HEAD
 1.1.4.1 08-Feb-2017  bouyer file Makefile.common was added on branch bouyer-socketcan on 2017-04-21 16:53:14 +0000
 1.1.2.2 20-Mar-2017  pgoyette Sync with HEAD
 1.1.2.1 08-Feb-2017  pgoyette file Makefile.common was added on branch pgoyette-localcount on 2017-03-20 06:57:02 +0000
 1.20 17-Nov-2022  chs 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.19 18-Apr-2020  jdolecek add NO_IOBUF_ALIGNED to not pull aligned_alloc() for really constrained
boot media
 1.18 08-Feb-2017  rin branches: 1.18.12;
__empty -> __nothing
 1.17 08-Feb-2017  rin switch to __empty
 1.16 08-Feb-2017  rin 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.15 06-Mar-2011  bouyer branches: 1.15.26; 1.15.30;
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.14 21-Oct-2009  snj branches: 1.14.2;
Remove 3rd and 4th clauses in christos' license. OK christos.
 1.13 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.12 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.11 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.10 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.9 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.8 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.7 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.6 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.5 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.4 30-Jul-2001  lukem - constify mkfs()'s first arg
- slightly reorder steps in -F image creation
 1.3 01-Dec-2000  simonb Put extern variable declarations in "extern.h".
 1.2 01-Dec-2000  simonb ANSIfy.
 1.1 30-Jun-1997  christos branches: 1.1.12;
Fix compiler warnings.
 1.1.12.3 25-Nov-2001  he Pull up revision 1.6 (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.1.12.2 25-Nov-2001  he Pull up revision 1.5 (requested by lukem):
Replace unused fs_headswitch/trkseek with fs_id.
 1.1.12.1 24-Nov-2001  he Pull up revisions 1.2-1.3 (requested by lukem):
Jumbo pullup for newfs:
o convert to ANSI function prototypes
o move external variables to extern.h
 1.14.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.15.30.1 21-Apr-2017  bouyer Sync with HEAD
 1.15.26.1 20-Mar-2017  pgoyette Sync with HEAD
 1.18.12.1 21-Apr-2020  martin Sync with HEAD
 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.2 11-Sep-2024  martin Pull up following revision(s) (requested by rin in ticket #835):

sbin/newfs/mkfs.c: revision 1.136

if the window size works but is 0, assume it didn't work and use 80.
 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.
 1.18 03-Jul-2017  wiz Remove workaround for ancient HTML generation code.
 1.17 12-Sep-2016  sevan Memory File System support appeared in 4.4BSD, implemented as an extension to
newfs(8). So while newfs may have appeared in 4.2BSD, MFS support was later.
https://svnweb.freebsd.org/csrg/sbin/newfs/Makefile?r1=39047&r2=39051
Adjust HISTORY.
Bump date.
 1.16 18-Feb-2010  wiz Fix typo (specifed -> specified).
 1.15 08-Dec-2007  jnemeth PR/37503 - De Zeurkous -- inaccurate description of -s option
 1.14 15-Jan-2006  dsl branches: 1.14.4; 1.14.6; 1.14.10; 1.14.12;
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.13 05-Aug-2005  jmmv Replace a dot with a colon, as a list of items follows it.
 1.12 11-Sep-2003  dsl Change date on man pages
 1.11 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.10 21-Aug-2003  dsl Update date for last.
 1.9 21-Aug-2003  dsl Remove unimplemented -n rotational positions
Remove depracated -c cpg (had been fragments per group in newfs.c, but...)
I might add something to let MINCYL (= 4) be configurable.
 1.8 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.7 21-Dec-2002  wiz Add a BUGS section describing that async mounts are currently disabled,
and explaining the reason. From Julio Merino.
 1.6 01-Oct-2002  wiz New sentence, new line. By Robert Elz with minimal fixes.
 1.5 20-Aug-2002  wiz Drop superfluous Ns.
 1.4 21-May-2002  lukem Add examples. Inspired by [misc/16193] from
Brian A. Seklecki <lavalamp@hurt.spiritual-machines.org>
 1.3 08-Feb-2002  ross Generate <>& symbolically. I'm avoiding .../dist/... directories for now.
 1.2 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.1 04-Jan-2002  lukem move mount_mfs(8) into separate man page
 1.14.12.1 27-Dec-2007  mjf Sync with HEAD.
 1.14.10.1 09-Jan-2008  matt sync with HEAD
 1.14.6.1 03-Jun-2008  skrll Sync with netbsd-4.
 1.14.4.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.86 17-Nov-2022  chs 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.85 13-Apr-2019  maya Omit mention of old vnd(4) bug, now resolved.

Via elge, thanks.
 1.84 03-Jul-2017  wiz branches: 1.84.6;
Remove workaround for ancient HTML generation code.
 1.83 30-Jun-2012  tsutsui Use 32KB/4KB for default block/fragment size on >= 128 GB partitions
for modern AFT disks. No particular comments against PR install/46629.
 1.82 14-May-2011  dholland branches: 1.82.4; 1.82.6;
Improve documentation of FFS formats and format levels from PR 32100.
Prompted also by recent discussion on tech-kern. Bump date.
 1.81 06-Mar-2011  wiz New sentence, new line.
 1.80 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.79 09-Aug-2010  wiz branches: 1.79.2;
Sort option descriptions.
 1.78 09-Aug-2010  pooka 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.77 21-Feb-2010  wiz Call the file system "ext2" consistently. Suggested by tsutsui.
 1.76 18-Feb-2010  wiz Pull over some of Jason McIntyre's fixes for newfs_ext2fs.
Suggested by tsutsui.
 1.75 01-Dec-2009  pooka Add note saying that special must be a raw device.
PR bin/42391
 1.74 01-Jul-2009  uwe G/c sentence fragment left over from vinum reference (forgotten in 1.69).
Noticed by bad@ in PR bin/41652
 1.73 10-May-2009  lukem Note that FFSv1 is also known as FFS, UFS, or UFS1.
Note that FFSv2 is also known as UFS2.
Add a reference to Kirk's BSDcon03 paper on UFS2.
 1.72 01-Aug-2008  simonb branches: 1.72.4;
Handle 't' suffix for terabytes for number arguments.
 1.71 08-Mar-2008  reinoud branches: 1.71.4;
Fix small documentation bug as reported in PR#38192 :

FFS -> FFSv1
UFS2 -> FFSv2
 1.70 10-Dec-2007  tsutsui branches: 1.70.4; 1.70.6;
Add Xref newfs_ext2fs(8).
 1.69 25-Feb-2006  christos branches: 1.69.4; 1.69.6; 1.69.10; 1.69.12; 1.69.14;
remove vinum reference.
 1.68 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.67 27-Dec-2005  hubertf Xref newfs_msdos, noted by rabioli on Freenode #NetBSD
 1.66 24-Jun-2005  wiz Bump date for previous.
 1.65 24-Jun-2005  peter Note that flag -a is obsolete. Thanks to Darrin B. Jewell.
Should fix PR/26883 from Hauke Fath.
 1.64 25-Jun-2004  wiz branches: 1.64.2;
Minimally document -d; addresses second part of
PR 25914 by Kouichirou Hiratsuka.
 1.63 01-Nov-2003  wiz eg -> e.g., vinum -> Xr vinum 4.
 1.62 01-Nov-2003  dsl Use fstat(2) to get the partition size (falling back to the label on old
kernels) so that newfs works on vinum (and similar).
Kill the -V hack for vinum.
Don't bother faking up a label for -F and mfs, nothing is needed from it.
Ignore label if special doesn't match DISKPART(sb.st_rdev);
Simplifly logic for default block/frag sizes.
Update man page to match.
WARNS=3.
 1.61 10-Oct-2003  wiz All single letter options are usually combined; add -V to the others.
 1.60 10-Oct-2003  grant bump date for last
 1.59 10-Oct-2003  grog Decribe the V flag.
 1.58 09-Oct-2003  dbj calculate "-s size" values after sectorsize has been fully determined
extend "-s size" argument to allow negative sizes to represent value to
subtract from diskalbel partition size
 1.57 11-Sep-2003  dsl Change date on man pages
 1.56 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.55 03-Sep-2003  dsl fsirand is no longer needed.
 1.54 12-Aug-2003  wiz Bump date for last.
 1.53 12-Aug-2003  dsl Mention and cross reference newfs_lfs and makefs.
 1.52 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.51 03-Apr-2003  wiz Sort options; mention -O default; grammar improvements; use more macros.
 1.50 03-Apr-2003  fvdl The -r option is no more, so delete it from the synopsis line too.
 1.49 03-Apr-2003  tron Document extended "-O" option after UFS2 import.
 1.48 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.47 25-Feb-2003  wiz .Nm does not need a dummy argument ("") before punctuation or
for correct formatting of the SYNOPSIS any longer.
 1.46 12-Oct-2002  wiz Remove some unnecessary ``\&''. Add an 'n' between an 'a' and an 'A'.
 1.45 01-Oct-2002  wiz New sentence, new line. By Robert Elz with minimal fixes.
 1.44 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.43 20-Aug-2002  wiz Drop superfluous Ns.
 1.42 06-Apr-2002  dsainty Reverted a small part of 1.30, removing full stops that accidentally got added
in the middle of sentences.
 1.41 20-Feb-2002  lukem change the default back to checking the file system type is '4.2BSD',
and add -I to ignore this check. per discussion with thorpej.
 1.40 08-Feb-2002  ross Generate <>& symbolically. I'm avoiding .../dist/... directories for now.
 1.39 04-Jan-2002  lukem move mount_mfs(8) into separate man page
 1.38 31-Dec-2001  lukem document that default block-size, frag-size, and bytes-per-inode are
now dependent upon file system size
 1.37 30-Dec-2001  lukem Fixes from and/or inspired by FreeBSD:
- Change the default cpg from 16 to 65536, which effectively means
that the largest allowable value for cpg will be computed if it's
not specified with -c or in the disklabel for that partition.
This is much more convenient for users.
- Improve the description of the defaults for various options
 1.36 21-Nov-2001  lukem - For mount_mfs, always ignore the `special' field and just fake up
the label instead. The previous change to use opendisk() prevented
this from working with special fields such as `/dev/wd0b', and this
new method is arguably cleaner anyway. Fixes [misc/14654]
- Don't bother supporting -T for mount_mfs anymore, since it's
superfluous. The option still works (for compatibility reasons), but
it's just ignored and not documented anymore.
- Use an RPM of 10000 instead of 3600 for the fake label (why not :-)
 1.35 16-Nov-2001  wiz Sort SEE ALSO, whitespace nits.
 1.34 16-Nov-2001  lukem - Without -F, use opendisk(3) to find the raw device
- With -F, relax the restriction that the filesystem must be a regular file
 1.33 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.32 31-Aug-2001  lukem fix a couple of typos in option descriptions
 1.31 30-Aug-2001  lukem replace mkfs reference with sentence describing what newfs does (from freebsd)
 1.30 29-Jul-2001  lukem * add -F option: enable creation of file system in a regular file. a "fake"
disklabel is created as per mfs on "swap".
* add -Z option: pre-zero the -F image file before use. this is necessary if
the image is to be used with vnd(4) because by default the files created
with -F have "holes" and vnd doesn't cope with that.
* support 'k', 'm', 'g' suffixes for all options which take numeric arguments.
provide strsuftoi() which performs the parsing mechanism.
* improve man page description of various options
* replace "filesystem" with "file system"
* when displaying usage for mfs, only list mfs options
* minor KNF and WARNS=2 cleanups
 1.29 07-Jun-2001  mrg s/primary swap area/first swap area/
 1.28 05-Jun-2001  wiz Drop arguments of .Os.
 1.27 03-Apr-2001  wiz Don't xref format(8) -- the man pages we have for it (hp300/vax) don't
seem very interesting at all, if not even obsolete.
Whitespace fixes while I'm here.
 1.26 02-Mar-2001  ad Fix typo.
 1.25 01-Dec-2000  simonb For mount_mfs, allow an 'm' suffix to the file system size option to
specify the size of the mfs in megabytes.

Inspired by the Solaris tmpfs "-o size=sz" option.
 1.24 16-May-1999  ad branches: 1.24.8;
Add NOTES section. Indicate that fstype in disklabel should be set to 4.2BSD.
 1.23 16-Mar-1999  wrstuden 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.22 07-Mar-1999  mycroft Clean up SYNOPSIS formatting.
 1.21 07-May-1998  mycroft Add a reference to fsirand(8).
 1.20 29-Apr-1998  fair fix bad .Xr references
 1.19 18-Mar-1998  bouyer Allow creation of non-native byteorder FFS (via the '-B' option).
 1.18 06-Feb-1998  perry macroize BSD, NetBSD, FreeBSD and misc cleanup
 1.17 16-Sep-1997  lukem * resolve conflicts from lite-2 import
* use int32_t instead of long
 1.16 15-Sep-1997  lukem * getopt returns -1 not EOF
* fix .Nm usage
 1.15 08-Mar-1997  mouse alternate -> alternative, per PR 2643
 1.14 26-Dec-1996  mikel eliminate obsolete reference to mkfs(8);
from Klaus Klein <kleink@layla.inka.de>.
also fixed buggy -a flag lines, reference fsck_ffs(8) instead of fsck(8).
 1.13 06-Jun-1996  mrg update to reality. from mike long (pr#2517)
 1.12 18-Mar-1995  cgd convert to new RCS Id conventions; reduce my headache
 1.11 18-Dec-1994  cgd adjust the documentation to note that 'swap' can be used instead of a dev.
 1.10 01-Dec-1994  mycroft Use defaults that are more reasonable for modern disks, and document the `-n'
option.
 1.9 16-Jul-1994  jtc Change mfs in Synopsis to mount_mfs.
 1.8 08-Jun-1994  mycroft branches: 1.8.2;
Update from 4.4-Lite, with local changes.
 1.7 20-Apr-1994  cgd back to 10%, per mkm
 1.6 12-Apr-1994  cgd 10 -> 5
 1.5 01-Aug-1993  mycroft Add RCS indentifiers.
 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.8.2.1 20-Jul-1994  cgd update from trunk.
 1.24.8.3 25-Nov-2001  he Pull up revision 1.33 (via patch, 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.24.8.2 24-Nov-2001  he Pull up revisions 1.25-1.26,1.28-1.29,1.31 (requested by lukem):
Jumbo pullup for newfs:
o allow ``m'' suffix in MFS size
o replace ``filesystem'' with ``file system''
o manual page typos and other corrections
 1.24.8.1 04-Apr-2001  he Pull up revision 1.27 (requested by wiz):
Don't xref format(8) -- the man pages we have for it (hp300/vax) don't
seem very interesting at all, if not even obsolete.
Also some whitespace fixes.
 1.64.2.1 29-Dec-2005  riz Pull up following revision(s) (requested by hubertf in ticket #1073):
sbin/newfs/newfs.8: revision 1.67 via patch
Xref newfs_msdos, noted by rabioli on Freenode #NetBSD
 1.69.14.1 09-Mar-2008  bouyer Pull up following revision(s) (requested by reinoud in ticket #1099):
sbin/newfs/newfs.8: revision 1.71
Fix small documentation bug as reported in PR#38192 :
FFS -> FFSv1
UFS2 -> FFSv2
 1.69.12.1 27-Dec-2007  mjf Sync with HEAD.
 1.69.10.2 23-Mar-2008  matt sync with HEAD
 1.69.10.1 09-Jan-2008  matt sync with HEAD
 1.69.6.1 03-Jun-2008  skrll Sync with netbsd-4.
 1.69.4.1 09-Mar-2008  bouyer Pull up following revision(s) (requested by reinoud in ticket #1099):
sbin/newfs/newfs.8: revision 1.71
Fix small documentation bug as reported in PR#38192 :
FFS -> FFSv1
UFS2 -> FFSv2
 1.70.6.2 28-Sep-2008  mjf Sync with HEAD.
 1.70.6.1 03-Apr-2008  mjf Sync with HEAD.
 1.70.4.1 24-Mar-2008  keiichi sync with head.
 1.71.4.1 18-Sep-2008  wrstuden Sync with wrstuden-revivesa-base-2.
 1.72.4.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.79.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.82.6.1 05-Jul-2012  riz Pull up following revision(s) (requested by tsutsui in ticket #396):
sbin/newfs/newfs.8: revision 1.83
sbin/newfs/newfs.c: revision 1.111
distrib/utils/sysinst/label.c: revision 1.62
Use 32KB/4KB for default block/fragment size on >= 128 GB partitions
for modern AFT disks. No particular comments against PR install/46629.
 1.82.4.1 30-Oct-2012  yamt sync with head
 1.84.6.1 10-Jun-2019  christos Sync with HEAD
 1.120 05-Jul-2023  riastradh Revert "newfs(8): Ensure A divides S before aligned_alloc(A, S)."

C17 lifted this restriction.
 1.119 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.118 17-Nov-2022  chs 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.117 16-Apr-2022  andvar fix various typos in comments and log messages.
 1.116 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.115 08-Feb-2017  rin branches: 1.115.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.114 01-Apr-2016  ryo branches: 1.114.2; 1.114.4;
no need to escape
 1.113 25-Jul-2015  mlelstv Handle getfsspecname errors.
 1.112 25-Oct-2014  mlelstv Support wedge names.

before:
newfs dk1 - formats /dev/rdk1
newfs rdk1 - cannot open /dev/rrdk1
newfs /dev/dk1 - /dev/dk1 is a block-device, use raw device
newfs /dev/rdk1 - formats /dev/rdk1

now:
newfs dk1 - formats /dev/rdk1
newfs rdk1 - cannot open /dev/rrdk1
newfs /dev/dk1 - formats /dev/rdk1 (*)
newfs /dev/rdk1 - formats /dev/rdk1
newfs NAME=wedge - formats /dev/rdk1

(*) getfsspecname() returns the block device which must be translated.
Passing a block device manually cannot be distinguished from this case.
 1.111 30-Jun-2012  tsutsui branches: 1.111.10;
Use 32KB/4KB for default block/fragment size on >= 128 GB partitions
for modern AFT disks. No particular comments against PR install/46629.
 1.110 13-Feb-2012  wiz branches: 1.110.2;
Remove unused variables.
From cppcheck via Henning Petersen in PR 46004.
 1.109 06-Mar-2011  bouyer branches: 1.109.4;
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 to usage, omission pointed out by wiz. Also, make usage format
nicer on a 80col terminal.
 1.107 09-Aug-2010  pooka 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.106 20-Dec-2009  dsl Push the mount path for mount_mfs through realpath().
This matches what other fs do.
Fixes PR/20362
 1.105 07-May-2009  lukem Consistently use FFSv1 or FFSv2
 1.104 11-Apr-2009  lukem fix sign-compare issues
 1.103 03-Apr-2009  pooka Issue a better error message if attempting to create a file system
on a block device. Inspired by PR kern/41127.
 1.102 01-Aug-2008  simonb branches: 1.102.2; 1.102.4; 1.102.8;
Handle 't' suffix for terabytes for number arguments.
 1.101 20-Jul-2008  lukem Remove the \n and tabs from the __COPYRIGHT() strings.
(Tweak some to use a consistent format.)
 1.100 15-Dec-2007  perry branches: 1.100.4; 1.100.8;
convert __attribute__s to applicable cdefs.h macros
 1.99 16-Jul-2007  pooka branches: 1.99.4; 1.99.6;
Make all mount(2) return value error checks against -1. Some file
systems just checked != 0, breaking MNT_GETARGS. Others worked with < 0,
but make them check against -1 too for consistency. And sprinkle some
stylish line wrapping where appropriate.
 1.98 14-Jul-2007  dsl Add additional 'sizeof args' parameter to mount(2).
 1.97 28-Apr-2007  christos PR/36229: Geoff Wing: uninitialized dkwedge_info structure in mount_mfs
causes random failures
 1.96 25-Nov-2006  christos PR/28884: Izumi Tsutsui: mount_mfs(8) doesn't set default fssize if "swap" is
specified
 1.95 16-Oct-2006  christos c99 initializers.
 1.94 27-Aug-2006  christos Make the "traditional" comment match reality.
 1.93 27-Aug-2006  christos Don't hard-code 3. From our secret user.
 1.92 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.91 04-May-2006  christos Since MNT_GETARGS is not allowed when any other flags are set, don't set
ASYNC in the getargs case.
 1.90 21-Mar-2006  christos Always check the results of getmntopts() and free them.
 1.89 16-Jan-2006  dsl Add '-V' to usage output.
Correct a couple of comments.
 1.88 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.87 28-Nov-2005  dsl Include the size we are trying to create in the 'partition to small'
error message.
 1.86 23-Sep-2005  jmmv Apply the NFS exports list rototill patch:

- Remove all NFS related stuff from file system specific code.
- Drop the vfs_checkexp hook and generalize it in the new nfs_check_export
function, thus removing redundancy from all file systems.
- Move all NFS export-related stuff from kern/vfs_subr.c to the new
file sys/nfs/nfs_export.c. The former was becoming large and its code
is always compiled, regardless of the build options. Using the latter,
the code is only compiled in when NFSSERVER is enabled. While doing this,
also make some functions in nfs_subs.c conditional to NFSSERVER.
- Add a new command in nfssvc(2), called NFSSVC_SETEXPORTSLIST, that takes a
path and a set of export entries. At the moment it can only clear the
exports list or append entries, one by one, but it is done in a way that
allows setting the whole set of entries atomically in the future (see the
comment in mountd_set_exports_list or in doc/TODO).
- Change mountd(8) to use the nfssvc(2) system call instead of mount(2) so
that it becomes file system agnostic. In fact, all this whole thing was
done to remove a 'XXX' block from this utility!
- Change the mount*, newfs and fsck* userland utilities to not deal with NFS
exports initialization; done internally by the kernel when initializing
the NFS support for each file system.
- Implement an interface for VFS (called VFS hooks) so that several kernel
subsystems can run arbitrary code upon receipt of specific VFS events.
At the moment, this only provides support for unmount and is used to
destroy NFS exports lists from the file systems being unmounted, though it
has room for extension.

Thanks go to yamt@, chs@, thorpej@, wrstuden@ and others for their comments
and advice in the development of this patch.
 1.85 15-Nov-2004  he branches: 1.85.2;
Add a cast to unsigned char when using a ctype function/macro.
 1.84 07-Sep-2004  lukem fix typo
 1.83 25-Jun-2004  wiz Remove last traces of -c, for which the code was removed
last summer; addresses part of PR 25914 by Kouichirou Hiratsuka.
 1.82 21-Apr-2004  christos Replace the statfs() family of system calls with statvfs().
Retain binary compatibility.
 1.81 18-Mar-2004  dsl Simplify logic for MNT_GETARGS and MNT_UPDATE of mfs filesystems.
Stop core dump caused by broken 'newfs -mfs' (= mount_mfs) hack when
newfs run with no arguments.
 1.80 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.79 07-Mar-2004  dsl Make update mounts (to change miniroot ramdisks to rw) take the same short
circuit as MNT_GETARGS.
Fixes PR#24533
 1.78 22-Dec-2003  jmmv Fix typo: numder -> number. From Christian Biere in PR bin/23838.
 1.77 11-Dec-2003  drochner If a disktype was specified, use the disktab information
and don't try the disklabel.
Allows to create a filesystem on a floppy again.
(It is arguably another bug that DIOCGDINFO returns nonsense
for floppies.)
 1.76 01-Nov-2003  wiz KNF: sort includes.
 1.75 01-Nov-2003  dsl Use fstat(2) to get the partition size (falling back to the label on old
kernels) so that newfs works on vinum (and similar).
Kill the -V hack for vinum.
Don't bother faking up a label for -F and mfs, nothing is needed from it.
Ignore label if special doesn't match DISKPART(sb.st_rdev);
Simplifly logic for default block/frag sizes.
Update man page to match.
WARNS=3.
 1.74 15-Oct-2003  dbj initialize llsize and llsizemult to 0
fixes bug noticed by Christopher SEKIYA on tech-kern@
 1.73 10-Oct-2003  wiz Sync look of -V description in usage with other option descriptions.
 1.72 10-Oct-2003  grog Add -V flag for use with Vinum to indicate that the last character of
the device name should not be interpreted as a partition identifier.
 1.71 09-Oct-2003  dbj calculate "-s size" values after sectorsize has been fully determined
extend "-s size" argument to allow negative sizes to represent value to
subtract from diskalbel partition size
 1.70 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.69 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.68 21-Aug-2003  dsl Remove -c maxblkspercg (leaving -c xxx ignored).
-c used to specify the number of cylinders per group
- but newfs has ignored cylinders for a while.
Changing what -c meant is just asking for trouble!
I might add something to let MINCYL be changed.
 1.67 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.66 13-Jul-2003  itojun use bounded string op
 1.65 02-Apr-2003  dbj On Apple UFS filesystems, change the default fragment size to 1024
and the default block size to 4096. Issue a warning if values
are used that will not work on Darwin.
 1.64 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.63 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.62 12-Dec-2002  scw Use getlabeloffset() instead of LABELOFFSET.
 1.61 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.60 21-Sep-2002  christos MNT_GETARGS support
 1.59 08-Aug-2002  soren Remove extraneous \n's in {err,warn}{,x} that used to be printfs.
 1.58 20-Feb-2002  lukem change the default back to checking the file system type is '4.2BSD',
and add -I to ignore this check. per discussion with thorpej.
 1.57 16-Feb-2002  thorpej * Undo rev 1.55. While one might think this test is useful, newfs
has historically allowed file systems to be created on non-4.2BSD
partitions, and the ability to do so is quite useful to some people.
* When rewriting the disklabel, don't consider it an error if there's
not a label already on the disk (and thus the rewrite operation fails).
 1.56 18-Jan-2002  lukem fix this if MFS is not #defined
 1.55 15-Jan-2002  lukem If -F isn't given, only newfs(8) partitions of type `4.2BSD'.
 1.54 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.53 30-Dec-2001  augustss Change how default block size is picked. The default block size is used
if there is no command line option and the disklabel gives 0 as the size.
The default used to be 8k, not the default is picked depending on the
file system size. FS < 20M gets 4k, <1G get 8k, and >1G get 16k.
The 16k default was suggested by lukem which FreeBSD is using.
 1.52 30-Dec-2001  lukem Revert rev 1.37 (use disklabel value for cpg if -c isn't given), because
we would rather let the "optimal cpg" calculation kick in at this point.
 1.51 30-Dec-2001  lukem Fixes from and/or inspired by FreeBSD:
- Change the default cpg from 16 to 65536, which effectively means
that the largest allowable value for cpg will be computed if it's
not specified with -c or in the disklabel for that partition.
This is much more convenient for users.
- Improve the description of the defaults for various options
 1.50 13-Dec-2001  lukem constrain bsize and fsize to MAXBSIZE
 1.49 21-Nov-2001  lukem - For mount_mfs, always ignore the `special' field and just fake up
the label instead. The previous change to use opendisk() prevented
this from working with special fields such as `/dev/wd0b', and this
new method is arguably cleaner anyway. Fixes [misc/14654]
- Don't bother supporting -T for mount_mfs anymore, since it's
superfluous. The option still works (for compatibility reasons), but
it's just ignored and not documented anymore.
- Use an RPM of 10000 instead of 3600 for the fake label (why not :-)
 1.48 16-Nov-2001  lukem - Without -F, use opendisk(3) to find the raw device
- With -F, relax the restriction that the filesystem must be a regular file
 1.47 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.46 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.45 08-Aug-2001  lukem when zeroing the image, use fstatfs() to find the optimal block size
(falling back to 8KB) instead of 512. should speed things up.
 1.44 30-Jul-2001  lukem - constify mkfs()'s first arg
- slightly reorder steps in -F image creation
 1.43 29-Jul-2001  lukem * add -F option: enable creation of file system in a regular file. a "fake"
disklabel is created as per mfs on "swap".
* add -Z option: pre-zero the -F image file before use. this is necessary if
the image is to be used with vnd(4) because by default the files created
with -F have "holes" and vnd doesn't cope with that.
* support 'k', 'm', 'g' suffixes for all options which take numeric arguments.
provide strsuftoi() which performs the parsing mechanism.
* improve man page description of various options
* replace "filesystem" with "file system"
* when displaying usage for mfs, only list mfs options
* minor KNF and WARNS=2 cleanups
 1.42 19-Feb-2001  cgd convert to use getprogname()
 1.41 01-Dec-2000  simonb For mount_mfs, allow an 'm' suffix to the file system size option to
specify the size of the mfs in megabytes.

Inspired by the Solaris tmpfs "-o size=sz" option.
 1.40 01-Dec-2000  simonb ANSIfy.
 1.39 10-Oct-2000  is Format string cleanups by Bill Sommerfeld.
 1.38 19-May-1999  wrstuden branches: 1.38.8;
If -c not set on command line and the partition has a non-zero cpg
value, use it for the number of cylinders per group. So now the value
in the disklabel does something. :-)
 1.37 19-Jan-1999  tron branches: 1.37.2;
Include "disktab.h" to get prototype for getdiskbyname().
 1.36 22-Oct-1998  mycroft Use the default calculation of maxcontig, based on fs_bsize and MAXPHYS, so
that the cluster summary information is correct for bsize=4k and MAXPHYS=64k.
 1.35 20-Oct-1998  matt vax -> __vax__
 1.34 28-Jul-1998  mycroft __AUDIT__ cleanup.
 1.33 18-Mar-1998  bouyer Allow creation of non-native byteorder FFS (via the '-B' option).
 1.32 01-Mar-1998  fvdl Merge with Lite2 + local changes
 1.31 19-Nov-1997  drochner mount_mfs: avoid spurious error message if the mount system call returns
for "valid reasons" (ie, "mount -u")
 1.30 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.29 01-Oct-1997  enami branches: 1.29.2;
Don't declare optind and optarg.
 1.28 29-Sep-1997  enami When calling err(3),
- Don't output unnecessary colon and space, and
- Include the name of system call just called.
 1.27 16-Sep-1997  lukem * resolve conflicts from lite-2 import
* use int32_t instead of long
 1.26 15-Sep-1997  lukem * getopt returns -1 not EOF
* fix .Nm usage
 1.25 30-Jun-1997  christos Fix compiler warnings.
 1.24 30-Jun-1997  tls I don't understand just what exactly changed in the past week that the GDINFO ioctl call here would smash the value of 'fd' and fail, but making fd volatile seems to fix it, for this program at least.
 1.23 30-Jan-1997  tls add support for noatime mount flag
 1.22 23-Oct-1996  cgd this file system (according to its source) supports MNT_UPDATE. Therefore
the mount program must recognize the 'update' option.
 1.21 18-Oct-1996  perry Remove #ifdef tahoe conditionals. We have no tahoe port. There is
still a big #if vax in this file which should be removed if possible --
#ifdef MACHINE stuff in mi code is bad.
 1.20 16-May-1996  thorpej Use getmaxpartitions() from libutil, not a homegrown version.
 1.19 28-Jun-1995  thorpej Use sysctl() to determine maxpartitions. Fixes pr #970.
 1.18 18-Mar-1995  cgd convert to new RCS Id conventions; reduce my headache
 1.17 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.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 30-Jan-1995  mycroft Use S_IS*().
 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 01-Dec-1994  mycroft Use defaults that are more reasonable for modern disks, and document the `-n'
option.
 1.12 23-Sep-1994  mycroft Remove some more uses of obsolete functions.
 1.11 23-Sep-1994  mycroft Eliminate uses of some obsolete functions.
 1.10 08-Jun-1994  mycroft Update from 4.4-Lite, with local changes.
 1.9 20-Apr-1994  cgd back to 10%, per mkm
 1.8 06-Feb-1994  cgd numeric -> symbolic constant
 1.7 28-Jan-1994  cgd MINFREE defaults to 5% per mckusick
 1.6 01-Aug-1993  mycroft Add RCS identifiers.
 1.5 28-Jul-1993  cgd incorporate changes from 0-9-base to 0-9-ALPHA
 1.4 18-Apr-1993  mycroft branches: 1.4.2;
Don't mix ANSI and pre-ANSI varargs.
 1.3 23-Mar-1993  cgd 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.4.2.2 21-Jul-1993  cgd in the last round: one of my changes was wrong, one was ugly.
 1.4.2.1 20-Jul-1993  cgd change all refs to "mfs" to be to "mount_mfs" as is appropriate
 1.29.2.3 23-Oct-1998  cgd pull up rev 1.36 from trunk (mycroft)
 1.29.2.2 19-Nov-1997  mellon Pull rev 1.31 up from trunk (drochner)
 1.29.2.1 02-Nov-1997  mellon Pull rev 1.30 up from trunk (drochner)
 1.37.2.1 10-Oct-2000  he Pull up revision 1.39 (requested by is):
Format string cleanup.
 1.38.8.4 25-Nov-2001  he Pull up revision 1.47 (via patch, 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.8.3 25-Nov-2001  he Pull up revision 1.46 (requested by lukem):
Replace unused fs_headswitch/trkseek with fs_id.
 1.38.8.2 24-Nov-2001  he Pull up revisions 1.40-1.41 (requested by lukem):
Jumbo pullup for newfs:
o convert to ANSI function prototypes
o allow ``m'' suffix in MFS size
 1.38.8.1 18-Oct-2000  tv Pullup sbin string format fixes [is].
See "cvs log" for explicit revision numbers per file, from sommerfeld.
 1.85.2.1 03-Mar-2007  bouyer Pull up following revision(s) (requested by tsutsui in ticket #1672):
sbin/newfs/newfs.c: revision 1.96
PR/28884: Izumi Tsutsui: mount_mfs(8) doesn't set default fssize if "swap" is
specified
 1.99.6.1 27-Dec-2007  mjf Sync with HEAD.
 1.99.4.1 09-Jan-2008  matt sync with HEAD
 1.100.8.1 18-Sep-2008  wrstuden Sync with wrstuden-revivesa-base-2.
 1.100.4.1 28-Sep-2008  mjf Sync with HEAD.
 1.102.8.1 21-Apr-2010  matt sync to netbsd-5
 1.102.4.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.102.2.1 10-Jun-2009  bouyer Pull up following revision(s) (requested by snj in ticket #803):
sbin/newfs/newfs.c: revision 1.103
Issue a better error message if attempting to create a file system
on a block device. Inspired by PR kern/41127.
 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.109.4.2 30-Oct-2012  yamt sync with head
 1.109.4.1 17-Apr-2012  yamt sync with head
 1.110.2.1 05-Jul-2012  riz Pull up following revision(s) (requested by tsutsui in ticket #396):
sbin/newfs/newfs.8: revision 1.83
sbin/newfs/newfs.c: revision 1.111
distrib/utils/sysinst/label.c: revision 1.62
Use 32KB/4KB for default block/fragment size on >= 128 GB partitions
for modern AFT disks. No particular comments against PR install/46629.
 1.111.10.2 30-Jul-2015  snj Pull up following revision(s) (requested by mlelstv in ticket #900):
sbin/newfs/newfs.c: revision 1.113
usr.sbin/installboot/installboot.c: revision 1.39
Handle getfsspecname errors.
 1.111.10.1 11-Nov-2014  martin Pull up following revision(s) (requested by mlelstv in ticket #199):
sbin/newfs/newfs.c: revision 1.112
sbin/fsck/fsck.c: revision 1.52
fix logic that handles command line arguments. Now you can:
fsck /mnt/point
fsck dkX
fsck rdkX
fsck /dev/dkX
fsck /dev/rdkX
fsck NAME=wedge
Support wedge names.
before:
newfs dk1 - formats /dev/rdk1
newfs rdk1 - cannot open /dev/rrdk1
newfs /dev/dk1 - /dev/dk1 is a block-device, use raw device
newfs /dev/rdk1 - formats /dev/rdk1
now:
newfs dk1 - formats /dev/rdk1
newfs rdk1 - cannot open /dev/rrdk1
newfs /dev/dk1 - formats /dev/rdk1 (*)
newfs /dev/rdk1 - formats /dev/rdk1
newfs NAME=wedge - formats /dev/rdk1
(*) getfsspecname() returns the block device which must be translated.
Passing a block device manually cannot be distinguished from this case.
 1.114.4.1 21-Apr-2017  bouyer Sync with HEAD
 1.114.2.1 20-Mar-2017  pgoyette Sync with HEAD
 1.115.12.1 21-Apr-2020  martin Sync with HEAD

RSS XML Feed