s/superbock/superblock/ in comment.

if the window size works but is 0, assume it didn't work and use 80.

Revert "newfs(8): Ensure A divides S before aligned_alloc(A, S)."

C17 lifted this restriction.

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

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.

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).

s/sytem/system/

mmap MAP_FAILED audit.

align buffers used for I/O to DEV_BSIZE so it's executed more optimally
when run for xbd(4) device

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.

branches: 1.127.2; 1.127.4;
PR/50910: David Binderman: Optimize memset.

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.)

fix error messages containing \n

- use calloc to zero memory
- pass the proper buffer to mkdir
- fix for apple ufs

reduce bss usage

Increase alignement of the global "buf" variable to cover all pointers it
is casted too. Fixes a crash on arm v5.

branches: 1.121.2;
Iterate over fields of struct seperately to avoid warnings from pedantic compilers

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.

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

Revert accidental commit of the change for PR 47911; got rolled into
other stuff by mistake.

fsbtodb() -> FFS_FSBTODB(), EXT2_FSBTODB(), or MFS_FSBTODB()
dbtofsb() -> FFS_DBTOFSB() or EXT2_DBTOFSB()

(Christos already did the lfs ones a few days back)

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.

Stick UFS_ in front of these symbols:
DIRBLKSIZ
DIRECTSIZ
DIRSIZ
OLDDIRFMT
NEWDIRFMT

Part of PR 47909.

(two stragglers in this commit; oops)

For MFS, no longer use heuristic based on rlimit to determine mmap size.
This is no longer functional with current memory allocation routines.

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.

branches: 1.112.6;
Remove unused variables.
From cppcheck via Henning Petersen in PR 46004.

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.

branches: 1.110.2;
Avoid magic manipulation of the format string.

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.

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)

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?

Consistently use FFSv1 or FFSv2

fix sign-compare issues

branches: 1.104.14;
PR/37155 - Marcelo Schmidt -- specifying too large of a size causes segvs

branches: 1.103.2;
Use powerof2() macro in <sys/param.h> rather than a homegrown version.

branches: 1.102.2; 1.102.4; 1.102.8;
c99 initializers.

- 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.

Use 64-bit arithmetic to calculate fragsperinodeblk, avoiding 32-bit
overflows for large values of "-i bytes-per-inode".

Add '-V' to usage output.
Correct a couple of comments.

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.

Don't look for old superblocks if newfs -N

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
$

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.

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.

The -b option is really on fsck_ffs, not fsck
Pointed out by Sebastian Schuetz on IRCnet #NetBSD

don't set fs_maxsymlinklen and fs_old_inodefmt twice,
we set them correctly the first time. fixes PR 26995.

Use FFS_MAXNAMLEN instead of MAXNAMLEN.

64 bit inode changes

ufs2 disk addresses in dp2->di_db[] must be swapped with bswap64, not bswap32

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

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.

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.

add uuid field to apple ufs volume label

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.

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

Need to write entire sector.

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.

Try very hard to ensure that the correct superblock will be found by
invalidating a host of other possible superblocks.

use arc4random

s/0x7fffffff/INT32_MAX/

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?

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.

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.

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.

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.

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.

Move UCB-licensed code from 4-clause to 3-clause licence.

Patches provided by Joel Baker in PR 22308, verified by myself.

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.

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.

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.

'NetBSD.org' and some mdoc fixes.

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.

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.

Some manual strength reduction.

Remove debugging output.

Use fs_fragshift more. Simplify a bunch of arithmetic involving NSPF().

wrap some mfs specific code in #ifdef MFS

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.

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.

clamp bsize to MAXBSIZE

fix error reporting in rdfs() and wtfs()

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]

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.
=====

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

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

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

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.

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.

- constify mkfs()'s first arg
- slightly reorder steps in -F image creation

rename and hide: malloc->Malloc, calloc->Calloc, free->Free. (remove realloc)

improve message describing MAXCSBUFS overflow

s/filesystem/file system/

clean up for WARNS=2 by renaming some local variables that shadow globals

- 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

remove unnecessary duplicate initialisation of sblock.fs_clean

Don't swap clustersum[0]. It's not a cluster summery but block free bitmap.

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" ...

Put extern variable declarations in "extern.h".

ANSIfy.

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.

Adjust column-sizing code to keep output in 76 character lines, so output
doesn't wrap in sysinst.

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. :-)

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>

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.

Explicitly zero "node" before we start using it.

Use DINODE_SIZE instead of sizeof(struct dinode). Also, eliminate some
unnecessary pointer casts.

Need <time.h> for time() prototype.

Allow creation of non-native byteorder FFS (via the '-B' option).

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.

branches: 1.28.2;
Quell gcc 2.7.2 initialization warning.

* resolve conflicts from lite-2 import
* use int32_t instead of long

Fix compiler warnings.

update for posixified stat structure

Back out previous change.

typeof(timeval.tv_sec) != time_t

flush stdout instead of stderr, so that each block number is displayed
as it is printed. From PR 989.

Set the `clean' flag.

short -> int16_t in a couple of places

convert to new RCS Id conventions; reduce my headache

calculate the 'offset' argument to lseek() in a prettier way, more
consistent with the way fsck(8) does it. no functional change.

flush stdout after printing each alternate superblock location.

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!)

compile against new headers.

type size paranoia, and allow one to mount an mfs on the device 'swap',
so that diskless machines can use MFS /tmp directories.

types/field names.

Eliminate uses of some obsolete functions.

fix from Peter Galbavy <peter@alice.wonderland.org>: don't overflow 80cols.

fix that annoying 'cgd0: bad magic number' bug

branches: 1.9.2;
Update from 4.4-Lite, with local changes.

various grunge

off_t death...

Set clean flags.

Add RCS identifiers.

incorporate changes from 0-9-base to 0-9-ALPHA

branches: 1.3.2;
changed "Id" to "Header" for rcsids

added rcs ids to all files

branches: 1.1.1;
Initial revision

if the window size works but is 0, assume it didn't work and use 80.

Revert "newfs(8): Ensure A divides S before aligned_alloc(A, S)."

C17 lifted this restriction.

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

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.

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).

s/sytem/system/

mmap MAP_FAILED audit.

align buffers used for I/O to DEV_BSIZE so it's executed more optimally
when run for xbd(4) device

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.

branches: 1.127.2; 1.127.4;
PR/50910: David Binderman: Optimize memset.

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.)

fix error messages containing \n

- use calloc to zero memory
- pass the proper buffer to mkdir
- fix for apple ufs

reduce bss usage

Increase alignement of the global "buf" variable to cover all pointers it
is casted too. Fixes a crash on arm v5.

branches: 1.121.2;
Iterate over fields of struct seperately to avoid warnings from pedantic compilers

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.

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

Revert accidental commit of the change for PR 47911; got rolled into
other stuff by mistake.

fsbtodb() -> FFS_FSBTODB(), EXT2_FSBTODB(), or MFS_FSBTODB()
dbtofsb() -> FFS_DBTOFSB() or EXT2_DBTOFSB()

(Christos already did the lfs ones a few days back)

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.

Stick UFS_ in front of these symbols:
DIRBLKSIZ
DIRECTSIZ
DIRSIZ
OLDDIRFMT
NEWDIRFMT

Part of PR 47909.

(two stragglers in this commit; oops)

For MFS, no longer use heuristic based on rlimit to determine mmap size.
This is no longer functional with current memory allocation routines.

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.

branches: 1.112.6;
Remove unused variables.
From cppcheck via Henning Petersen in PR 46004.

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.

branches: 1.110.2;
Avoid magic manipulation of the format string.

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.

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)

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?

Consistently use FFSv1 or FFSv2

fix sign-compare issues

branches: 1.104.14;
PR/37155 - Marcelo Schmidt -- specifying too large of a size causes segvs

branches: 1.103.2;
Use powerof2() macro in <sys/param.h> rather than a homegrown version.

branches: 1.102.2; 1.102.4; 1.102.8;
c99 initializers.

- 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.

Use 64-bit arithmetic to calculate fragsperinodeblk, avoiding 32-bit
overflows for large values of "-i bytes-per-inode".

Add '-V' to usage output.
Correct a couple of comments.

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.

Don't look for old superblocks if newfs -N

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
$

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.

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.

The -b option is really on fsck_ffs, not fsck
Pointed out by Sebastian Schuetz on IRCnet #NetBSD

don't set fs_maxsymlinklen and fs_old_inodefmt twice,
we set them correctly the first time. fixes PR 26995.

Use FFS_MAXNAMLEN instead of MAXNAMLEN.

64 bit inode changes

ufs2 disk addresses in dp2->di_db[] must be swapped with bswap64, not bswap32

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

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.

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.

add uuid field to apple ufs volume label

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.

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

Need to write entire sector.

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.

Try very hard to ensure that the correct superblock will be found by
invalidating a host of other possible superblocks.

use arc4random

s/0x7fffffff/INT32_MAX/

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?

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.

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.

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.

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.

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.

Move UCB-licensed code from 4-clause to 3-clause licence.

Patches provided by Joel Baker in PR 22308, verified by myself.

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.

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.

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.

'NetBSD.org' and some mdoc fixes.

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.

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.

Some manual strength reduction.

Remove debugging output.

Use fs_fragshift more. Simplify a bunch of arithmetic involving NSPF().

wrap some mfs specific code in #ifdef MFS

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.

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.

clamp bsize to MAXBSIZE

fix error reporting in rdfs() and wtfs()

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]

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.
=====

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

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

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

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.

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.

- constify mkfs()'s first arg
- slightly reorder steps in -F image creation

rename and hide: malloc->Malloc, calloc->Calloc, free->Free. (remove realloc)

improve message describing MAXCSBUFS overflow

s/filesystem/file system/

clean up for WARNS=2 by renaming some local variables that shadow globals

- 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

remove unnecessary duplicate initialisation of sblock.fs_clean

Don't swap clustersum[0]. It's not a cluster summery but block free bitmap.

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" ...

Put extern variable declarations in "extern.h".

ANSIfy.

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.

Adjust column-sizing code to keep output in 76 character lines, so output
doesn't wrap in sysinst.

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. :-)

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>

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.

Explicitly zero "node" before we start using it.

Use DINODE_SIZE instead of sizeof(struct dinode). Also, eliminate some
unnecessary pointer casts.

Need <time.h> for time() prototype.

Allow creation of non-native byteorder FFS (via the '-B' option).

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.

branches: 1.28.2;
Quell gcc 2.7.2 initialization warning.

* resolve conflicts from lite-2 import
* use int32_t instead of long

Fix compiler warnings.

update for posixified stat structure

Back out previous change.

typeof(timeval.tv_sec) != time_t

flush stdout instead of stderr, so that each block number is displayed
as it is printed. From PR 989.

Set the `clean' flag.

short -> int16_t in a couple of places

convert to new RCS Id conventions; reduce my headache

calculate the 'offset' argument to lseek() in a prettier way, more
consistent with the way fsck(8) does it. no functional change.

flush stdout after printing each alternate superblock location.

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!)

compile against new headers.

type size paranoia, and allow one to mount an mfs on the device 'swap',
so that diskless machines can use MFS /tmp directories.

types/field names.

Eliminate uses of some obsolete functions.

fix from Peter Galbavy <peter@alice.wonderland.org>: don't overflow 80cols.

fix that annoying 'cgd0: bad magic number' bug

branches: 1.9.2;
Update from 4.4-Lite, with local changes.

various grunge

off_t death...

Set clean flags.

Add RCS identifiers.

incorporate changes from 0-9-base to 0-9-ALPHA

branches: 1.3.2;
changed "Id" to "Header" for rcsids

added rcs ids to all files

branches: 1.1.1;
Initial revision

Revert "newfs(8): Ensure A divides S before aligned_alloc(A, S)."

C17 lifted this restriction.

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

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.

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).

s/sytem/system/

mmap MAP_FAILED audit.

align buffers used for I/O to DEV_BSIZE so it's executed more optimally
when run for xbd(4) device

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.

branches: 1.127.2; 1.127.4;
PR/50910: David Binderman: Optimize memset.

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.)

fix error messages containing \n

- use calloc to zero memory
- pass the proper buffer to mkdir
- fix for apple ufs

reduce bss usage

Increase alignement of the global "buf" variable to cover all pointers it
is casted too. Fixes a crash on arm v5.

branches: 1.121.2;
Iterate over fields of struct seperately to avoid warnings from pedantic compilers

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.

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

Revert accidental commit of the change for PR 47911; got rolled into
other stuff by mistake.

fsbtodb() -> FFS_FSBTODB(), EXT2_FSBTODB(), or MFS_FSBTODB()
dbtofsb() -> FFS_DBTOFSB() or EXT2_DBTOFSB()

(Christos already did the lfs ones a few days back)

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.

Stick UFS_ in front of these symbols:
DIRBLKSIZ
DIRECTSIZ
DIRSIZ
OLDDIRFMT
NEWDIRFMT

Part of PR 47909.

(two stragglers in this commit; oops)

For MFS, no longer use heuristic based on rlimit to determine mmap size.
This is no longer functional with current memory allocation routines.

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.

branches: 1.112.6;
Remove unused variables.
From cppcheck via Henning Petersen in PR 46004.

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.

branches: 1.110.2;
Avoid magic manipulation of the format string.

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.

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)

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?

Consistently use FFSv1 or FFSv2

fix sign-compare issues

branches: 1.104.14;
PR/37155 - Marcelo Schmidt -- specifying too large of a size causes segvs

branches: 1.103.2;
Use powerof2() macro in <sys/param.h> rather than a homegrown version.

branches: 1.102.2; 1.102.4; 1.102.8;
c99 initializers.

- 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.

Use 64-bit arithmetic to calculate fragsperinodeblk, avoiding 32-bit
overflows for large values of "-i bytes-per-inode".

Add '-V' to usage output.
Correct a couple of comments.

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.

Don't look for old superblocks if newfs -N

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
$

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.

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.

The -b option is really on fsck_ffs, not fsck
Pointed out by Sebastian Schuetz on IRCnet #NetBSD

don't set fs_maxsymlinklen and fs_old_inodefmt twice,
we set them correctly the first time. fixes PR 26995.

Use FFS_MAXNAMLEN instead of MAXNAMLEN.

64 bit inode changes

ufs2 disk addresses in dp2->di_db[] must be swapped with bswap64, not bswap32

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

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.

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.

add uuid field to apple ufs volume label

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.

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

Need to write entire sector.

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.

Try very hard to ensure that the correct superblock will be found by
invalidating a host of other possible superblocks.

use arc4random

s/0x7fffffff/INT32_MAX/

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?

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.

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.

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.

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.

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.

Move UCB-licensed code from 4-clause to 3-clause licence.

Patches provided by Joel Baker in PR 22308, verified by myself.

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.

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.

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.

'NetBSD.org' and some mdoc fixes.

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.

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.

Some manual strength reduction.

Remove debugging output.

Use fs_fragshift more. Simplify a bunch of arithmetic involving NSPF().

wrap some mfs specific code in #ifdef MFS

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.

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.

clamp bsize to MAXBSIZE

fix error reporting in rdfs() and wtfs()

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]

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.
=====

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

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

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

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.

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.

- constify mkfs()'s first arg
- slightly reorder steps in -F image creation

rename and hide: malloc->Malloc, calloc->Calloc, free->Free. (remove realloc)

improve message describing MAXCSBUFS overflow

s/filesystem/file system/

clean up for WARNS=2 by renaming some local variables that shadow globals

- 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

remove unnecessary duplicate initialisation of sblock.fs_clean

Don't swap clustersum[0]. It's not a cluster summery but block free bitmap.

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" ...

Put extern variable declarations in "extern.h".

ANSIfy.

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.

Adjust column-sizing code to keep output in 76 character lines, so output
doesn't wrap in sysinst.

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. :-)

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>

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.

Explicitly zero "node" before we start using it.

Use DINODE_SIZE instead of sizeof(struct dinode). Also, eliminate some
unnecessary pointer casts.

Need <time.h> for time() prototype.

Allow creation of non-native byteorder FFS (via the '-B' option).

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.

branches: 1.28.2;
Quell gcc 2.7.2 initialization warning.

* resolve conflicts from lite-2 import
* use int32_t instead of long

Fix compiler warnings.

update for posixified stat structure

Back out previous change.

typeof(timeval.tv_sec) != time_t

flush stdout instead of stderr, so that each block number is displayed
as it is printed. From PR 989.