Copy stable/10@r272459 to releng/10.1 as part of
the 10.1-RELEASE process.

Approved by: re (implicit)
Sponsored by: The FreeBSD Foundation

Refer newfs and growfs users to fsck_ffs instead of
fsck, the latter does not accept the referred to "-b" flag.

PR: 82720
Submitted by: David D.W. Downey

Copy head (r256279) to stable/10 as part of the 10.0-RELEASE cycle.

Approved by: re (implicit)
Sponsored by: The FreeBSD Foundation

The purpose of this change to the FFS layout policy is to reduce the
running time for a full fsck. It also reduces the random access time
for large files and speeds the traversal time for directory tree walks.

The key idea is to reserve a small area in each cylinder group
immediately following the inode blocks for the use of metadata,
specifically indirect blocks and directory contents. The new policy
is to preferentially place metadata in the metadata area and
everything else in the blocks that follow the metadata area.

The size of this area can be set when creating a filesystem using
newfs(8) or changed in an existing filesystem using tunefs(8).
Both utilities use the `-k held-for-metadata-blocks' option to
specify the amount of space to be held for metadata blocks in each
cylinder group. By default, newfs(8) sets this area to half of
minfree (typically 4% of the data area).

This work was inspired by a paper presented at Usenix's FAST '13:
www.usenix.org/conference/fast13/ffsck-fast-file-system-checker

Details of this implementation appears in the April 2013 of ;login:
www.usenix.org/publications/login/april-2013-volume-38-number-2.
A copy of the April 2013 ;login: paper can also be downloaded
from: www.mckusick.com/publications/faster_fsck.pdf.

Reviewed by: kib
Tested by: Peter Holm
MFC after: 4 weeks

Fix problem with geom_label(4) not recognizing UFS labels on filesystems
extended using growfs(8). The problem here is that geom_label checks if
the filesystem size recorded in UFS superblock is equal to the provider
(i.e. device) size. This check cannot be removed due to backward
compatibility. On the other hand, in most cases growfs(8) cannot set
fs_size in the superblock to match the provider size, because, differently
from newfs(8), it cannot recompute cylinder group sizes.

To fix this problem, add another superblock field, fs_providersize, used
only for this purpose. The geom_label(4) will attach if either fs_size
(filesystem created with newfs(8)) or fs_providersize (filesystem expanded
using growfs(8)) matches the device size.

PR: kern/165962
Reviewed by: mckusick
Sponsored by: FreeBSD Foundation

Fix sbin/ build with a 64-bit ino_t.

Original code by: Gleb Kurtsou

Fix warning when compiling with gcc46:
error: variable 'c' set but not used

Approved by: dim
MFC after: 3 days

Add missing static keywords for global variables to tools in sbin/.

These tools declare global variables without using the static keyword,
even though their use is limited to a single C-file, or without placing
an extern declaration of them in the proper header file.

Stop trying to zero UFS1 superblocks if we fall off the end of the disk.

This avoids a potentially many-hours-long loop of failed writes if newfs
finds a partially-overwritten superblock (or, for that matter, random
garbage which happens to have superblock magic bytes); on one occasion I
found newfs trying to zero 800 million superblocks on a 50 MB disk.

Reviewed by: mckusick
MFC after: 1 week

The dump, fsck_ffs, fsdb, fsirand, newfs, makefs, and quot utilities
include sys/time.h instead of time.h. This include is incorrect as
per the manpages for the APIs and the POSIX definitions. This commit
replaces sys/time.h where necessary with time.h.

The commit also includes some minor style(9) header fixup in newfs.

This commit is part of a larger effort by Garrett Cooper started in
//depot/user/gcooper/posix-conformance-work/ -- to make FreeBSD more
POSIX compliant.

Submitted by: Garrett Cooper yanegomi at gmail dot com

Add support for FS_TRIM to user-mode UFS utilities.

Reviewed by: mckusick, pjd, pho
Tested by: pho
MFC after: 1 month

Reported problem:
Large (60GB) filesystems created using "newfs -U -O 1 -b 65536 -f 8192"
show incorrect results from "df" for free and used space when mounted
immediately after creation. fsck on the new filesystem (before ever
mounting it once) gives a "SUMMARY INFORMATION BAD" error in phase 5.

This error hasn't occurred in any runs of fsck immediately after
"newfs -U -b 65536 -f 8192" (leaving out the "-O 1" option).

Solution:
The default UFS1 superblock is located at offset 8K in the filesystem
partition; the default UFS2 superblock is located at offset 64K in
the filesystem partition. For UFS1 filesystems with a blocksize of
64K, the first alternate superblock resides at 64K which is the the
location used for the default UFS2 superblock. By default, the
system first checks for a valid superblock at the default location
for a UFS2 filoesystem. For a UFS1 filesystem with a blocksize of
64K, there is a valid UFS1 superblock at this location. Thus, even
though it is expected to be a backup superblock, the system will
use it as its default superblock. So, we have to ensure that all the
statistcs on usage are correct in this first alternate superblock
as it is the superblock that will actually be used.

While tracking down this problem, another limitation of UFS1 became
evident. For UFS1, the number of inodes per cylinder group is stored
in an int16_t. Thus the maximum number of inodes per cylinder group
is limited to 2^15 - 1. This limit can easily be exceeded for block
sizes of 32K and above. Thus when building UFS1 filesystems, newfs
must limit the number of inodes per cylinder group to 2^15 - 1.

Reported by: Guy Helmer<ghelmer@palisadesys.com>
Followup by: Bruce Cran <brucec@freebsd.org>
PR: 107692
MFC after: 4 weeks

o bdeficize expand_number_int() function;

o revert most of the recent changes (int -> int64_t conversion) by using
this functon for parsing all options.

Cast these to intmax_t before printing to fix build bustage. Better
solutions welcome.

One last pass to get all the unsigned comparisons correct.

Ensure that newfs will never create a filesystem with more than 2^32
inodes by cutting back on the number of inodes per cylinder group if
necessary to stay under the limit. For a default (16K block) file
system, this limit begins to take effect for file systems above 32Tb.

This fix is in addition to -r203763 which corrected a problem in the
kernel that treated 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.

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

Fix typo: s/partion/partition/

Submitted by: Marc Balmer <marc@msys.ch>
MFC after: 3 days

Don't add a bwrite() symbol, it breaks the build when building newfs
statically.
Instead, bring in a stripped down version of sbwrite(), and add the offset
to every bwrite() calls.

Enable operation of newfs on plain files, which is useful when you
want to prepare disk images for emulators (though 'makefs' in port
can do something similar).

This relies on:
+ minor changes to pass the consistency checks even when working on a file;

+ an additional option, '-p partition' , to specify the disk partition to
initialize;

+ some changes on the I/O routines to deal with partition offsets.

The latter was a bit tricky to implement, see the details in newfs.h:
in newfs, I/O is done through libufs which assumes that the file
descriptor refers to the whole partition. Introducing support for
the offset in libufs would require a non-backward compatible change
in the library, to be dealt with a version bump or with symbol
versioning.

I felt both approaches to be overkill for this specific application,
especially because there might be other changes to libufs that might
become necessary in the near future.

So I used the following trick:
- read access is always done by calling bread() directly, so we just add
the offset in the (few) places that call bread();
- write access is done through bwrite() and sbwrite(), which in turn
calls bwrite(). To avoid rewriting sbwrite(), we supply our own version
of bwrite() here, which takes precedence over the version in libufs.

MFC after: 4 weeks

Use calloc().

Report erase interval (correctly) in sectors.

Rename the undocumented -E option to -X.

Implement -E option which will erase the filesystem sectors before
making the new filesystem. Reserved space in front of the superblock
(bootcode) is not erased.

NB: Erasing can take as long time as writing every sector sequentially.

This is relevant for all flash based disks which use wearlevelling.

Add -J flag to both newfs(8) and tunefs(8) which allows to enable gjournal
support.
I left -j flag for UFS journal implementation which we may gain at some
point.

Sponsored by: home.pl

Explicitly say which gid do we use as a fallback, when operator
is not found.

Suggested by: kensmith

Don't treat failure to find the operator GID as a fatal error; this
made it impossible to use newfs (and mdmfs) when /etc/group is
missing and /etc is read-only.

When creating a new FFS file system, the block size will indirectly
affect the largest file size that is allowed by the file system.
On the other hand, when creating a snapshot, the snapshot file will
appear as it is as big as the file system itself. Hence we will not
be able to create a snapshot on large file systems with small block
sizes.

Add a warning about this, and gives some hints to correct the issue.

Reviewed by: mckusick
MFC After: 1 week

When creating a new FFS file system, the block size will indirectly
affect the largest file size that is allowed by the file system.
On the other hand, when creating a snapshot, the snapshot file will
appear as it is as big as the file system itself. Hence we will not
be able to create a file system on large file systems with small
block sizes.

Add a warning about this, and gives some hints to correct the issue.

Reviewed by: mckusick
MFC After: 1 week

Add an option to suppress the creation of the .snap directory in
the new filesystem. This is intended for memory and vnode filesystems
that will never be fsck'ed or dumped.

Obtained from: St. Bernard Software RAPID
MFC after: 2 weeks

Generalize the UFS bad magic value used to determine when a filesystem
has only been partly initialized via newfs(8) so that it applies to both
UFS1 and UFS2.

Submitted by: "Xin LI" delphij at frontfree dot net
MFC: maybe?

Remove advertising clause from University of California Regent's license,
per letter dated July 22, 1999.

Approved by: core, imp

Add a "-l" flag to newfs, which sets the FS_MULTILABEL flag. This
permits users of newfs to set the multilabel flag on UFS1 and UFS2
file systems from inception without using tunefs.

Obtained from: TrustedBSD Project
Sponsored by: DARPA, McAfee Research

Fix whitespace error in previous commit.

Approved by: RE@ (Robert Watson)

Don't use UFS2_BAD_MAGIC on UFS (v1) filesystems; it is Not Ready
for Prime Time there.

Submitted by: Xin LI <delphij@frontfree.net>
Approved by: RE@ (John, Scott)

Add the -E command line option to force error conditions for testing.

Sponsord by: St. Bernard Software

Write the UFS2 superblock with a 'BAD' magic number at the beginning
of newfs, to signify the newfs operation has not yet completed. Re-
write the superblock with the correct magic number once all of the
cylinder groups have been created to show the operation has finished.

Sponsored by: St. Bernard Software

Create a .snap directory mode 770 group operator in the root of
a new filesystem. Dump and fsck will create snapshots in this
directory rather than in the root for two reasons:

1) For terabyte-sized filesystems, the snapshot may require many
minutes to build. Although the filesystem will not be suspended
during most of the snapshot build, the snapshot file itself is
locked during the entire snapshot build period. Thus, if it is
accessed during the period that it is being built, the process
trying to access it will block holding its containing directory
locked. If the snapshot is in the root, the root will lock and
the system will come to a halt until the snapshot finishes. By
putting the snapshot in a subdirectory, it is out of the likely
path of any process traversing through the root and hence much
less likely to cause a lock race to the root.

2) The dump program is usually run by a non-root user running with
operator group privilege. Such a user is typically not permitted
to create files in the root of a filesystem. By having a directory
in group operator with group write access available, such a user
will be able to create a snapshot there. Having the dump program
create its snapshot in a subdirectory below the root will benefit
from point (1) as well.

Sponsored by: DARPA & NAI Labs.

Exit with a non-zero status upon a block allocation failure.
The old way of just returning could result in a file system
extremely likely to panic the kernel. The warning printed
wouldn't help much since tools invoking newfs(8), e.g., mdmfs(8),
couldn't detect the error.

PR: bin/55078
MFC after: 1 week

When newfs'ing a partition with UFS2 that had previously been newfs'ed
with UFS1, the UFS1 superblocks were not deleted. This allowed any
RELENG_4 (or other non-UFS2-aware) fsck to think it knew how to "fix"
the file system, resulting in severe data scrambling.

This patch is a more advanced version than the one originally submitted.
Lukas improved it based on feedback from Kirk, and testing by me. It
blanks all UFS1 superblocks (if any) during a UFS2 newfs, thereby causing
fsck's that are not UFS2 aware to generate the "SEARCH FOR ALTERNATE
SUPER-BLOCK FAILED" message, and exit without damaging the fs.

PR: bin/51619
Submitted by: Lukas Ertl <l.ertl@univie.ac.at>
Reviewed by: kirk
Approved by: re (scottl)

Put back the error checking in wtfs() that was lost when newfs was
changed to use libufs in revision 1.71. Without this, any write
failures in newfs were silently ignored.

Note that this will display a meaningless errno string in the case
of a short write as opposed to a write error, since bwrite()'s
return value does not allow the caller to determine if errno is
valid.

Reported by: Lukas Ertl <l.ertl@univie.ac.at>
Reviewed by: jmallett
Approved by: re (bmah)

Use __FBSDID() to quiet GCC 3.3 warnings.

Fix the -R flag so that it provides sequential "random" numbers
so that the regression test will succeed.

Sponsored by: DARPA & NAI Labs.

Replace use of random() with arc4random() to provide less guessable
values for the initial inode generation numbers in newfs and for
newly allocated inode generation numbers in the kernel.

Submitted by: Theo de Raadt <deraadt@cvs.openbsd.org>
Sponsored by: DARPA & NAI Labs.

Correct lines incorrectly added to the copyright message. Add missing period.

Submitted by: Bruce Evans <bde@zeta.org.au>
Sponsored by: DARPA & NAI Labs.

Convert newfs to libufs (really). Solves one real issue with previous
version of such. Differences in filesystems generated were found to be
from 1) sbwrite with the "all" parameter 2) removal of writecache. The
sbwrite call was made to perform as the original version, and otherwise
this was checked against a version of newfs with the write cache removed.

Bring in support for volume labels to the filesystem utilities.

Reviewed by: mckusick

Back out conversion to libufs, for now. It seems to cause problems.

Reported by: phk

Convert newfs to use libufs. I've tested this on md filesystems, as has
keramida, and all seems well.

Correctly calculate the initial number of fragments in a filesystem
so that fsck does not complain with `SUMMARY BLK COUNT(S) WRONG IN
SUPERBLK' the first time it is run on a new filesystem.

Reported by: Poul-Henning Kamp <phk@freebsd.org>
Sponsored by: DARPA & NAI Labs.

Add some more checks to newfs so that it will not build filesystems
that the kernel will refuse to mount. Specifically it now enforces
the MAXBSIZE blocksize limit. This update also fixes a problem where
newfs could segment fault if the selected fragment size was too large.

PR: bin/30959
Submitted by: Ceri Davies <setantae@submonkey.net>
Sponsored by: DARPA & NAI Labs.

Create a new 32-bit fs_flags word in the superblock. Add code to move
the old 8-bit fs_old_flags to the new location the first time that the
filesystem is mounted by a new kernel. One of the unused flags in
fs_old_flags is used to indicate that the flags have been moved.
Leave the fs_old_flags word intact so that it will work properly if
used on an old kernel.

Change the fs_sblockloc superblock location field to be in units
of bytes instead of in units of filesystem fragments. The old units
did not work properly when the fragment size exceeeded the superblock
size (8192). Update old fs_sblockloc values at the same time that
the flags are moved.

Suggested by: BOUWSMA Barry <freebsd-misuser@netscum.dyndns.dk>
Sponsored by: DARPA & NAI Labs.

Properly calculate the initial number of fragments in a large filesystem.

Sponsored by: DARPA & NAI Labs.

Bound the size of the superblock to SBLOCKSIZE.

Submitted by: BOUWSMA Beery <freebsd-misuser@netscum.dyndns.dk>
Sponsored by: DARPA & NAI Labs.

Use the standardized CHAR_BIT constant instead of NBBY in userland.

s/filesystem/file system/g as discussed on -developers

di_createtime -> di_birthtime.

Submitted by: Udo Schweigert <Udo.Schweigert@siemens.com>

Fixed 4 printf format errors that were fatal on alphas. %qd is not even
suitable for printing quad_t's since it is equivalent to %lld but quad_t
is unsigned long on alphas. quad_t shouldn't be used anyway.

Get rid of paranoia that zeros the boot block area as this has
bad effect on existing bootstraps.

Submitted by: Jake Burkholder <jake@locore.ca>
Sponsored by: DARPA & NAI Labs.

This commit adds basic support for the UFS2 filesystem. The UFS2
filesystem expands the inode to 256 bytes to make space for 64-bit
block pointers. It also adds a file-creation time field, an ability
to use jumbo blocks per inode to allow extent like pointer density,
and space for extended attributes (up to twice the filesystem block
size worth of attributes, e.g., on a 16K filesystem, there is space
for 32K of attributes). UFS2 fully supports and runs existing UFS1
filesystems. New filesystems built using newfs can be built in either
UFS1 or UFS2 format using the -O option. In this commit UFS1 is
the default format, so if you want to build UFS2 format filesystems,
you must specify -O 2. This default will be changed to UFS2 when
UFS2 proves itself to be stable. In this commit the boot code for
reading UFS2 filesystems is not compiled (see /sys/boot/common/ufsread.c)
as there is insufficient space in the boot block. Once the size of the
boot block is increased, this code can be defined.

Things to note: the definition of SBSIZE has changed to SBLOCKSIZE.
The header file <ufs/ufs/dinode.h> must be included before
<ufs/ffs/fs.h> so as to get the definitions of ufs2_daddr_t and
ufs_lbn_t.

Still TODO:
Verify that the first level bootstraps work for all the architectures.
Convert the utility ffsinfo to understand UFS2 and test growfs.
Add support for the extended attribute storage. Update soft updates
to ensure integrity of extended attribute storage. Switch the
current extended attribute interfaces to use the extended attribute
storage. Add the extent like functionality (framework is there,
but is currently never used).

Sponsored by: DARPA & NAI Labs.
Reviewed by: Poul-Henning Kamp <phk@freebsd.org>

more file system > filesystem

Continue the cleanup preparations for UFS2 (& GEOM):

Use only one filedescriptor. Open in R/O or R/W based in the '-N' option.
Make the filedescriptor a global variable instead of passing it around
as semi-global variable(s).

Remove the undocumented ability to specify type without '-T' option.

Replace fatal() with straight err(3)/errx(3). Save calls to strerror()
where applicable. Loose the progname variable.

Get the sense of the cpgflag test correct so we only issue warnings if
people specify cpg and can't get that. It can be argued that this
should be an error.

Remove the check to see if the disk is mounted: Open for writing
would fail if it were mounted.

Attempt to get the sectorsize and mediasize with the generic disk
ioctls, fall back to disklabel and /etc/disktab as we can.

Notice that on-disk labels still take precedence over /etc/disktab,
this is probably wrong, but not as wrong as the entire concept of
/etc/disktab is.

Sponsored by: DARPA & NAI Labs.

bbsize and sbsize cannot ever be trusted from the disklabel, in
particular as there may not be one. Remove #if 0'ed code which might
mislead people to think otherwise.

unifdef -ULOSTDIR, fsck can make lost+found on the fly.

Sponsored by: DARPA & NAI Labs

Fixed some English errors in previous commit.

Fixed some style bugs in the removal of __P(()). Whitespace before
"__P((" was not removed.

Add more DWIM/autoadjustment and less evil style(9) banned exit(2) codes.
Add some missing statics.

Sponsored by: DARPA & NAI Labs.

Swing the axe and remove some archaic features from newfs which modern
diskdrives do neither need nor want:

-O create a 4.3BSD format filesystem
-d rotational delay between contiguous blocks
-k sector 0 skew, per track
-l hardware sector interleave
-n number of distinguished rotational positions
-p spare sectors per track
-r revolutions/minute
-t tracks/cylinder
-x spare sectors per cylinder

No change in the produced filesystem image unless one or more of
these options were used.

Approved by: mckusick

Add the undocumented -R option to disable randomness for regression-testing.

Add a couple of simple regression tests accessible with "make test", they
depend on the md(4) driver.

FYI I have also tried running the test against a week old newfs and it
passed.

Further cleanups.

Replace a number of similar `for' loops with a new `ilog2()' function
that computes the base-2 log of a power of 2.

Complete the ANSIfication of newfs by converting function declarations
to C89 style.

The FSIRAND code is always compiled in, and it is unlikely that
anyone needs a newfs without it. Remove the #ifdef's from around
the code and the -DFSIRAND from the Makefile. Also remove redundant
declarations of random() and srandomdev().

Remove the ancient STANDALONE code.

Approved by: phk

Remove yet more vestiges of mount_mfs.

Fixed some style bugs (mainly ones not fixed or made worse by rev.1.41).
Old code obfuscates long (but single-line) messages by printing them in
pieces using %s. Rev.1.41 obfuscated some new long messages using ISO
string concatenation. This commit only fixes the new obfuscations.

Remove __P() and register.
Set WARNS=2

This is the beginning of a pre-UFS2 cleanup of newfs.

Sponsored by: DARPA, NAI Labs

style(9) cleanup.

Submitted by: j mckitrick <jcm@freebsd-uk.eu.org>
Reviewed by: phk, /sbin/md5

Handle snprintf() returning < 0 (not just -1)

MFC after: 2 weeks

Handle snprintf() returning -1.

MFC after: 2 weeks

A more complete removal of MFS related code.

XXX: This program badly needs a style(9) + BDECFLAGS treatment.

sprintf() -> snprintf()

Partially submitted by: "Andrew R. Reiter" <arr@watson.org>
Obtained from: OpenBSD

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>

Fixed style bugs in previous commit.

Allow enabling soft updates (with -U) on a new filesystem.

[I first added this functionality, and thought to check prior art. Seeing
OpenBSD had already done this, I changed my addition to reduce the diffs
between the two and went with their option letter.]
Obtained from: OpenBSD

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

Cast block number to off_t to avoid possible overflow bugs.

Pointed out by: Bruce Evans <bde@zeta.org.au>

The write combining code in revision 1.30 needs a few additional
touch ups. The cache needs to be flushed against block
reads, and a final flush at process termination to force the
backup superblocks to disk.

I believe this will allow 'make release' to complete.

Submitted by: Tor.Egge@fast.no

Implement simple write combining for newfs - this is particularly useful
for large scsi disks with WCE = 0. This yields around a 7 times speedup
on elapsed newfs time on test disks here. 64k clusters seems to be the
sweet spot for scsi disks using our present drivers.

$Id$ -> $FreeBSD$

Don't print a "," after the last superblock.

Submitted by: adrian

Fix bug in mount_mfs whereby mount_mfs would sometimes return before
the mount is completely active, causing the next few commands attempting
to manipulate data on the mount to fail. mount_mfs's parent now tries
to wait for the mount point st_dev to change before returning, indicating
that the mount has gone active.

Use explicitly sized types when formatting cylinder groups.

Forgot to remove a ';' in my previous commit.

Add prototypes. Check malloc() return value. Use err(). Remove unused #includes
Do not \n nor dot terminate syslog()/err() messages. -Wall.

Fixed printf format errors.

Fixed overflow in the calculation of the number of inodes per group
for filesystems with almost the maximum number of sectors. The maxiumum
is 2^31, but overflow is common for that size, and overflow normally
occurred here at size (2^31 - 4096).

Don't create superblocks with size larger than SBSIZE (8192). The
size was rounded up to a multiple of the fragment size, but this
gave invalid file systems when the fragment size was > SBSIZE (fsck
aborts early on them). Now a fragment size of 32768 seems to work
(too-simple tests with fsck and iozone worked).

Some tweaks to get this to cope with ELF where the address space starts
higher up in memory (0x0800000 upwards) rather than near zero (0x1000
for our qmagic a.out format). The method that mount_mfs uses to allocate
the memory within data size rlimits for the ram disk is entirely too much
of a kludge for my liking. I mean, if it's run as root, surely it makes
sense to just raise the resource limits to infinity or something, and if
it's a non-root user mount (do these work? with mfs?) it could just fail
if it's outside limits.

Removed "hack to prevent overflow of a 32bit block number". Lite2 has a
better hack in ffs_vfsops.c. The hack here restricted the maximum file
size to 2^39 bytes (512GB). fs_bsize * 2^31 - 1 (16TB for the default
blocksize of 8K) would have been better. There is no good way to remove
this limit on old BSD4.4 file systems.

Remove srandomdev fallback

Fix the mount_mfs case from the last cleanup. The code was (ab)using
it's internal malloc() implementation to try and avoid overstepping it's
resource limits (yuk!). Remain using libc's malloc(), but check the
resource limits right before trying to malloc the ramdisk space and leave
some spare memory for libc. In Andrey's words, the internal malloc
was "true evil".. Among it's sins is it's ability to allocate less memory
than asked for and still return success. stdio would just love that. :-)

Reviewed by: ache

Cleanup STANDALONE stuff
Not replace malloc() family for non-standalone variant
Pay attention on malloc() family return code now
Use srandomdev() now for RNG initialization

Add generation number randomization. Newly created filesystems wil now
automatically have random generation numbers. The kenel way of handling those
also changed. Further it is advised to run fsirand on all your nfs exported
filesystems. the code is mostly copied from OpenBSD, with the randomization
chanegd to use /dev/urandom
Reviewed by: Garrett
Obtained from: OpenBSD

Merge from Lite2:
- use new getvfsbyname() and mount(2) interface (mount_mfs)
- use new fs include files
- updated inode / cg layout calculations (?)

Sweep through the tree fixing mmap() usage:

- Use MAP_FAILED instead of the constant -1 to indicate
failure (required by POSIX).
- Removed flag arguments of '0' (required by POSIX).
- Fixed code which expected an error return of 0.
- Fixed code which thought any address with the high bit set
was an error.
- Check for failure where no checks were present.

Discussed with: bde

This update adds the support for != 512 byte sector SCSI devices to
the sd & od drivers. There is also slight changes to fdisk & newfs
in order to comply with different sectorsizes.
Currently sectors of size 512, 1024 & 2048 are supported, the only
restriction beeing in fdisk, which hunts for the sectorsize of
the device.
This is based on patches to od.c and the other system files by
John Gumb & Barry Scott, minor changes and the sd.c patches by
me.
There also exist some patches for the msdos filesys code, but I
havn't been able to test those (yet).

John Gumb (john@talisker.demon.co.uk)
Barry Scott (barry@scottb.demon.co.uk)

ts_sec -> tv_sec
ts_nsec -> tv_nsec

A better algorithm to place the numbers on the lines.

Submitted by: satoshi

Make the numbers for the "superblock backups" fit nicely on the screen,
even for larger partitions. Until now, partition sizes > 500 MB messed
up the screen.

Remove trailing whitespace.

Flush stdout when writing out each superblock backup.

Restrict fs_maxfilesize to 2^40; this is part of a bug fix from Kirk
McKusick to work around problems in FFS related to the blkno of a 64bit
offset not fitting into an int.

Submitted by: Marshall Kirk McKusick

Added '-F file' option of mount_mfs. This allows me to make floppy images
without waiting for my floppy-drive all the time :-) Might have other
interesting uses too.

Backed out part of the last change that prevents the rpos table from
being output if <= 1 rpos; there is a bug in the kernel which doesn't
quite get along with this. Changed default #rpos to 1, and fixed up
manual page. Converted nrpos to 1 if user specifies 0.

1) If nrpos <= 1, don't output rpos table (and set fs_cpc to 0) - disabling
the use of the rotational position table.
2) Allow specification of 0 rotational positions (disables function).
3) Make rotdelay=0 and nrpos=0 by default.

The purpose of the above is to optimize for modern SCSI (and IDE) drives
that do read-ahead/write-behind.

Set fs_clean.

This commit was generated by cvs2svn to compensate for changes in r1558,
which included commits to RCS files with non-trunk default branches.

BSD 4.4 Lite sbin Sources

Note: XNSrouted and routed NOT imported here, they shall be imported with
usr.sbin.