HAMMER 53H/Many: Performance tuning, bug fixes

* CHANGE THE ON-MEDIA B-TREE STRUCTURE.  The number of elements per node has
  been increased from 16 to 64.  The intent is to reduce the number of seeks
  required in a heavy random-access loading situation.

* Add a shortcut to the B-Tree node scanning code (requires more testing).
  Instead of scanning linearly we do a power-of-2 narrowing search.

* Only do clustered reads for DATA types.  Do not cluster meta-data (aka
  B-Tree) I/O.  Note that the inode data structure is considered to be
  a DATA type.  Reduce the cluster read side from 256K to 64K to avoid
  blowing out the buffer cache.

* Augment hammer locks so one can discern between a normal lock blockage
  and one that is recovering from a deadlock.

* Change the slave work threads for the flusher to pull their work off a
  single queue.  This fixes an issue where one slave work thread would
  sometimes get a disproportionate percentage of the work and the
  master thread then had to wait for it to finish while the other work
  threads were twiddling their thumbs.

* Adjust the wait reclaims code to solve a long standing performance issue.
  The flusher could get so far behind that the system's buffer cache buffers
  would no longer have any locality of reference to what was being flushed,
  causing a massive drop in performance.

* Do not queue a dirty inode to the flusher unconditionally in the strategy
  write code.  Only do it if system resources appear to be stressed.
  The inode will get flushed when the filesystem syncs.

* Code cleanup.

* Fix a bug reported by Antonio Huete Jimenez related to 0-length writes
  not working properly.

Switch from bioq_insert_tail() to bioqdisksort().  When the kernel is
juggling hundreds of I/O requests the on-disk controllers, which have limited
queue sizes, are unable to completely optimize the accesses.

This seems to make a pretty big difference on the twe device I tested with
when running blogbench on HAMMER, which can approach 1000 simultaniously
queued I/O's.

Make sure host controller interrupts are not enabled until all
initialisation is finished.

Obtained-from: NetBSD

Remove the code which disables port status change interrupts for 1 second
when one occured. It meant that event get lost or delayed until the next
change leaving the port dead under some circumstances.

Obtained-from: NetBSD

HAMMER 53G/Many: Performance tuning.

* Implement multiple flusher threads.

* Move the call to hammer_inode_waitreclaims() yet again.  Call it from
  hammer_vop_reclaim().

HAMMER 53F/Many: Fix deadlock.

* Do not sleep waiting for reclaimed inodes to drain while holding
  an inode lock.

Remove superfluous recursive lock. This little change makes possible (safe)
to use spinlock(9) instead of lockmgr(9).

Fix ordering mismatch between KERN_* values and CTL_KERN_NAMES array.

HAMMER 53E/Many: Performance tuning

* Change the code which waits for reclaims to drain to be more inline with
  the new bwillwrite().  Impose a dynamic delay instead of blocking outright.

* Move the hammer_inode_waitreclaims() call from hammer_vop_open() to
  hammer_get_inode(), and only call it when we would otherwise have to
  create a new inode.

* Sort HAMMER's file list in conf/files.

Change bwillwrite() to smooth out performance under heavy loads.  Blocking
based on strict hystersis was being used to try to gang flushes together
but filesystems can still blow out the buffer cache and cause processes
to block for long periods of time waiting for the dirty count to drop
significantly.

Instead, as the number of dirty buffers exceeds the desired maximum
bwillwrite() imposes a dynamic delay which increases as the number of
dirty buffers increase.  This improves the stall behavior under heavy loads
and keeps the system responsive.

TODO: The algorithm needs to have a per-LWP heuristic to penalize heavy
writers more then light ones.

HAMMER 53D/Many: Stabilization

* Fix an overwrite bug with direct write which could result in file
  corruption.

* Reserve just-freed big blocks for two flush cycles to prevent HAMMER from
  overwriting destroyed data so it does not become corrupt if the system
  crashes.  This is needed because the recover code does not record UNDOs
  for data (nor do we want it to).

* More I/O subsystem work.  There may still be an ellusive panic related
  to calls to regetblk().

Add an extern for hidirtybuffers.

Reported-by: Michael Neumann <mneumann@ntecs.de>

Parallelize in_ifaddrhashtbl

Move stack variable near its usage

Fix a SMP race in signotify_remote().  LWPHOLD() the lwp being
passed from one cpu to another over an IPI to prevent it from exiting
in the mean time and causing the IPI to panic.

HAMMER 53C/Many: Stabilization

* HAMMER queues dirty inodes reclaimed by the kernel to the backend for
  their final sync.  Programs like blogbench can overload the backend and
  generate more new inodes then the backend can dispose of, running
  M_HAMMER out of memory.

  Add code to stall on vop_open() when this condition is detected to
  give the backend a chance to catch-up.  (see NOTE 1 below).

* HAMMER could build up too many meta-data buffers and cause the system
  to deadlock in newbuf.  Recode the flusher to allow a block of UNDOs,
  the volume header, and all related meta-data buffers to be flushed
  piecemeal, and then continue the flush loop without closing out the
  transaction.   If a crash occurs the recovery code will undo the partial
  flushes.

* Fix an issue located by FSX under load.  The in-memory/on-disk record
  merging code was not dealing with in-memory data records properly
  The key field for data records is (base_offset + data_len), not just
  (base_off), so a 'match' between an in-memory data record and an on-disk
  data records requires a special case test.  This is the case where the
  in-memory record is intended to overwrite the on-disk record, so the
  in-memory record must be chosen and the on-disk record discarded for
  the purposes of read().

* Fix a bug in hammer_io.c related to the handling of B_LOCKED buffers
  that resulted in an assertion at umount time.  Buffer cache buffers
  were not being properly disassociated from their hammer_buffer countparts
  in the direct-write case.

* The frontend's direct-write capability for truncated buffers (such as
  used with small files) was causing an assertion to occur on the backend.
  Add an interlock on the related hammer_buffer to prevent the frontend
  from attempting to modify the buffer while the backend is trying to
  write it to the media.

* Dynamically size the dirty buffer limit.  This still needs some work.

(NOTE 1): On read/write performance issues.  Currently HAMMER's frontend
VOPs are massively disassociated from modifying B-Tree updates.  Even though
a direct-write capability now exists, it applies only to bulk data writes
to disk and NOT to B-Tree updates.  Each direct write creates a record
which must be queued to the backend to do the B-Tree update on the
media.  The flusher is currently single-threaded and when HAMMER gets
too far behind doing these updates the current safeties will cause
performance to degrade drastically.  This is a known issue that
will be addressed.

Fix typo.

Fix typos.

HAMMER 53B/Many: Complete overhaul of strategy code, reservations, etc

* Completely overhaul the strategy code.  Implement direct reads and writes
  for all cases.  REMOVE THE BACKEND BIO QUEUE.  BIOs are no longer queued
  to the flusher under any circumstances.

  Remove numerous hacks that were previously emplaced to deal with BIO's
  being queued to the flusher.

* Add a mechanism to invalidate buffer cache buffers that might be shadowed
  by direct I/O.  e.g. if a strategy write uses the vnode's bio directly
  there may be a shadow hammer_buffer that will then become stale and must
  be invalidated.

* Implement a reservation tracking structure (hammer_reserve) to track
  storage reservations made by the frontend.  The backend will not attempt
  to free or reuse reserved space if it encounters it.

  Use reservations to back cached holes (struct hammer_hole) for the
  same reason.

* Index hammer_buffer on the zone-X offset instead of the zone-2 offset.
  Base the RB tree in the hammer_mount instead of (zone-2) hammer_volume.
  This removes nearly all blockmap lookup operations from the critical path.

* Do a much better job tracking cached dirty data for the purposes of
  calculating whether the filesystem will become full or not.

* Fix a critical bug in the CRC generation of short data buffers.

* Fix a VM deadlock.

* Use 16-byte alignment for all on-disk data instead of 8-byte alignment.

* Major code cleanup.

As-of this commit write performance is now extremely good.

HAMMER Utilities: Critical bug in newfs_hammer

* newfs_hammer was not properly setting up the small-data zone.

Add tunable to enable/disable PBCC support in acx(4) and it is enabled
by default.

Parallelize in_ifaddrhead operation

Assert that move in directory entry hash table can't fail.

- oia is no longer used
- Tranform for(;;) loop into while() loop

Move fetching of "hw.hasbrokenint12" tunable closer to it's usage.

Cosmetic changes (remove whitespace).

Remove unnecessary conversion to kilobytes (divide by 1024) to then later
multiply it again by 1024 to get to bytes.

Use NULL instead of 0.

Correct typos.

HAMMER 53A/Many: Read and write performance enhancements, etc.

* Add hammer_io_direct_read().  For full-block reads this code allows
  a high-level frontend buffer cache buffer associated with the
  regular file vnode to directly access the underlying storage,
  instead of loading that storage via a hammer_buffer and bcopy()ing it.

* Add a write bypass, allowing the frontend to bypass the flusher and
  write full-blocks directly to the underlying storage, greatly improving
  frontend write performance.  Caveat: See note at bottom.

  The write bypass is implemented by adding a feature whereby the frontend
  can soft-reserve unused disk space on the physical media without having
  to interact (much) with on-disk meta-data structures.  This allows the
  frontend to flush high-level buffer cache buffers directly to disk
  and release the buffer for reuse by the system, resulting in very high
  write performance.

  To properly associate the reserved space with the filesystem so it can be
  accessed in later reads, an in-memory hammer_record is created referencing
  it.  This record is queued to the backend flusher for final disposition.
  The backend disposes of the record by inserting the appropriate B-Tree
  element and marking the storage as allocated.  At that point the storage
  becomes official.

* Clean up numerous procedures to support the above new features.  In
  particular, do a major cleanup of the cached truncation offset code
  (this is the code which allows HAMMER to implement wholely asynchronous
  truncate()/ftruncate() support.

  Also clean up the flusher triggering code, removing numerous hacks that
  had been in place to deal with the lack of a direct-write mechanism.

* Start working on statistics gathering to track record and B-Tree
  operations.

* CAVEAT: The backend flusher creates a significant cpu burden when flushing
  a large number of in-memory data records.  Even though the data itself
  has already been written to disk, there is currently a great deal of
  overhead involved in manipulating the B-Tree to insert the new records.
  Overall write performance will only be modestly improved until these
  code paths are optimized.

Use ASSERT_IFAC_VALID whenever possible

Add ASSERT_IFAC_VALID

- Expose ifa_forwardmsg()
- Add ifa_domsg()

# They will be needed soon

Don't use NULL where 0 is meant.

Make sure that ifac is still valid before unlinking it from or linking it to ifnet

Add periodic rf calibration support for acx111 part.  This seems to stablize
performance during long time TX stress.

* Fix some cases where NULL was used but 0 was meant (and vice versa).

* Remove some bogus casts of NULL to (void *).

Remove some unneeded definitions of NULL.

Include <sys/_null.h> for the definition of NULL.

Add <sys/_null.h> for the definition of NULL:

[...]
#ifndef __cplusplus
#define NULL ((void *)0)
#else
#define NULL 0
#endif
[...]

Add rt_cpuid, which records rtentry's owning CPU id.  It could ease route
entry related debugging and sanity checks.

Fix bugs in spin_trylock_wr():

- globaldata.gd_spinlock_wr was not decremented back on failure;

- incorrect comparison in loop trying to clear cached shared bits (loop
  must fail if spinlock is still held for read by another cpu).

Reviewed-by: dillon@

HAMMER 52/Many: Read-only mounts and mount upgrades/downgrades.

* Finish implementing MNT_UPDATE, allowing a HAMMER mount to be upgraded
  or downgraded.

* Adjust the recovery code to not flush buffers dirtied by recovery
  operations (running the UNDOs) when the mount is read-only.  The
  buffers will be flushed when the mount is updated to read-write.

* Improve recovery performance by not flushing dirty buffers until the
  end (if a read-write mount).

* A crash which occurs during recovery might cause the next recovery to
  fail.  Delay writing out the recovered volume header until all the other
  buffers have been written out to fix the problem.

HAMMER Utilities: Enhance mount_hammer

* Allow devices to be specified as dev:dev:dev, so a multi-volume hammer
  mount can be specified in /etc/fstab.

* Implement -u (mount update)

Do not update f_offset on EINVAL.

Reported-by: VOROSKOI Andras <voroskoi@gmail.com>

mdoc cleanup

Fix a crash when "Arctic Ocean" was selected.

Taken-from: FreeBSD

HAMMER Utilities: More pre-formatting, cleanup

* Fully initialize the large-data and small-data blockmaps in addition
  to the B-Tree blockmap.

* Set vol0_stat_bigblocks properly so used space shows as 0, or otherwise
  a fairly small number, when the volume is empty.

* Display the total amount of space pre-allocated by newfs_hammer for
  the boot-area, memory-log, undo-buffer, and blockmap infrastructure.

Add 'options HAMMER' to LINT.

Noticed-by: Dionysus Blazakis <dion.blazakis@gmail.com>

HAMMER 51/Many: Filesystem full casework, nohistory flag.

* Track the amount of unsynced information and return ENOSPC if the
  filesystem would become full.  The idea here is to detect that the
  filesystem is full and yet still give the flusher enough runway to
  flush cached dirty data and inodes.

* Implement the NOHISTORY flag.  Implement inheritance of NOHISTORY and
  NODUMP.

  The NOHISTORY flag tells HAMMER not to retain historical information on
  a filesystem object.  If set on a directory any objects created in that
  directory will also inherit the flag.  For example, it could be set
  on /usr/obj.

Report the nohistory, noshistory, and nouhistory flags, and allow them
to be specified with chflags.

Set the inverted field for nosunlink, nosunlnk, nouunlink, nouulnk.  This
is an inverted flag.

Add the UF_NOHISTORY and SF_NOHISTORY chflags flags.  The nohistory flag
allows you to mount a HAMMER filesystem normally and still specify that
certain files and directory not retain historical information.

If set on a directory the flag will be inherited by any objects
created within that directory.

Adjust UFS to inherit the NOHISTORY and NODUMP flags from the parent
directory when creating new objects.  NODUMP used to be ufs-specific
and UFS's backup/restore remembered the inheritance.  As a more generic
flag it needs to be inherited within the filesystem.  Note that UFS
has no historical retention capability and ignores the NOHISTORY flag,
but we might use it with the journaling audit trail later.

Disallow negative seek positions for regular files, directories, and
character-special devices to conform to OpenGroup specifications.

Reported-by: VOROSKOI Andras <voroskoi@gmail.com>

Add missing exit(1).

Reported-by: Johannes Hofmann <hofmann@blob.baaderstrasse.com>

HAMMER Utilities: Correct vol0_stat_freebigblocks.

* The root_vol->ondisk->vol0_stat_freebigblocks was not being properly
  decremented when newfs_hammer allocated big blocks, causing it to report
  a value that is too large.

Fix kernel compile warnings.

Even using the objcache we need a one-per-cpu free-thread cache in order
to keep an exiting thread intact throughout its exit sequence.

This fixes a double-fault which can occur on shutdown.  The bug was mainly
tickled by exiting kernel threads.

According to SUSv3 including just regex.h must be enough. Fixes build of
several pkgsrc packages.

Unbreak buildworld.

HAMMER 50/Many: VFS_STATVFS() support, stabilization.

* Add support for VFS_STATVFS(), returning 64 bit quantities for available
  space, etc.

* When freeing a big-block any holes cached for that block must be
  cleaned out.

* Fix a conditional testing whether a layer2 big-block must be allocated in
  layer1.  The bug could only occur if a layer2 big-block gets freed in
  layer1, and we currently never do this.

* Clean-up comments related to freeing blocks.

HAMMER Utilities: Performance adjustments, bug fixes.

* Newfs_hammer now pre-allocates the layer1 and layer2 blockmap blocks,
  and pre-sizes each blockmap to 4x the initial filesystem size instead
  of 100x the initial filesystem size.

  The blockmap can be dynamically resized at any time, given a little code.
  In addition, there is simply no need to give it a 100x initial dynamic
  range.  This only bloats the size of the layer-2 map unnecessarily.

* Change alloc_blockmap() to use rootmap->next_offset for allocations
  instead of rootmap->alloc_offset and fix a bug where rootmap->phys_offset
  was improperly being incremented (it is a fixed field once set).

  The bug was in a code-path that could not by executed by current
  incarnations of newfs_hammer.

Use newly available libc and system calls related to statvfs to make df
work with 64 bit statvfs fields.  Tested with a 4TB VN-backed HAMMER
filesystem.

Add getmntvinfo() which uses the new getvfsstat() system call.

More header file cleanups related statvfs.

Clean up statvfs() and related prototypes.  Place the prototypes in the
correct file.

Implement a new system call: getvfsstat().  This system call returns
an array of statfs and statvfs structures.  Unfortunately there is no way
to just return an array of statvfs structures because the statvfs structure
does not have sufficient information in it to identify the mount point.

    getvfsstat(struct statfs *buf, struct statvfs *vbuf,
       long vbufsize, int flags);

* Implement new system calls in the kernel:  statvfs(), fstatvfs(),
  fhstatvfs().

* Implement a new VFS op, VFS_STATVFS().  Implement a default for this new
  op for VFSs which do not implement VFS_STATVFS(), which calls VFS_STATFS()
  and converts the structure (using Joerg's conversion procedure from libc).

* Remove statvfs(), fstatvfs(), and fhstatvfs() from libc.  These functions
  are now system calls.

Raise the size of the /etc MFS to 12MB (for ssh blacklists).

- Rename ifa_portfn() to ifnet_portfn()
- Create inline function ifa_portfn() which simply calls ifnet_portfn()

Rename:
ifaddrinit -> ifnetinit
ifaddr_threads -> ifnet_threads

Avoid code duplication

acx111 parts can't send using short slot time, but it seems to have no problem
to receive packets sent using short slot time.  Turn on short slot time
support, so that we don't prevent other STA from using short slot time.

Use 1Mbits/s as beacon sending rate; it seems to fix TX performance issue
when using acx(4) as hostap.

HAMMER Utilities: New utility 'undo'.

* Add a new utility called 'undo' which makes use of HAMMER capabilities
  to retrieve prior versions of a file, even if that file has been deleted.

  This utility can dump all prior versions of the file, generate a history
  of transaction ids associated with the file, has a 'quick diff' relative
  to the most recent change, and can also generate diffs for all versions
  of the file.

  This utility only works with HAMMER filesystems.

HAMMER Utilities: Cleanup

* Cleanup the softprune code a bit.

HAMMER 49B/Many: Stabilization pass

* Fix range checks in the pruning ioctl.

* Fix an incorrect assertion in hammer_vop_strategy_read().

HAMMER Utilities: Add the 'hammer softprune' command.

Add a new hammer pruning command called 'hammer softprune'.  This command
is much simpler to use then the 'hammer prune' command.  You simply specify
a directory containing softlinks to HAMMER snapshots, typically in the form:
"<path_to_hammer_filesystem>/@@0x<16-char-transaction_id>".  The command
will scan the directory non-recursively, collect all the softlinks, extract
the transaction ids, and prune the HAMMER filesystem to contain only those
snapshots.

In addition, information created before the snapshot softlink with the
lowest transaction id is destroyed and information created after the
softlink with the highest transaction id is retained (remains fine-grained).

This gives the administrator an easy way to maintain official snapshots
while at the same time retaining our 'undo' capability by leaving recent
modifications intact.

A simple cron job or script coupled with the use of the 'hammer synctid'
can be used to create a snapshot softlink every so often, and older
snapshots can be cleaned out or thinned simply by removing the associated
softlinks, and then re-running 'hammer softprune' on the directory
containing the softlinks.

Unlike the 'hammer prune' command, the softprune command does not require
the time ranges for snapshots to be well-ordered.

HAMMER 49/Many: Enhance pruning code

* Pass the element array in as a pointer rather then embedding it in
  the hammer_ioc_prune structure.

* Adjust the modulo calculations to allow non-aligned snapshots to be
  pruned, to support the new 'hammer softprune' command.

Reduce log verbosity

mdoc cleanup

Use same naming convention as other host controller stats

- Avoid excessive goto
- Adjust arphdr pointer, if we need to do another m_pullup()
- Indentation in switch block

Obtained-from: FreeBSD w/ mod

Add ifa_listmask field in ifaddr_container; currently it is mainly used
to do sanity checks.

Add some missing manual pages: wcscoll(3), wcswidth(3), wcsxfrm(3), and
wcwidth(3)

Taken-from: NetBSD

Mention that -W too only works with -p or -d.

Minor corrections.

Implement Farnsworth mode.

Fix typo.

Noticed-by: Antonio Huete Jimenez <tuxillo@quantumachine.net>

Include sys/select.h to conform to SUS.

Noticed-by: hasso@

Fix type name as well.

Noticed-by: hasso@

Fix macro name.

Noticed-by: hasso@

Add brief description about the recently added interrupt moderation sysctl nodes

- Rename bce_init_context() to bce_init_ctx()
- Clear out all quick context entries.  This fixes the watchdog timeout, which
  usually happens after many tiny packets are transmitted

Obtained-from: FreeBSD if_bce.c rev 1.36

# FreeBSD didn't mention a _single_ word of this change and its effect in the
# commit log.  The description of the fix and the its effect is obtained from
# Linux bnx2 commit log.

- ifnet.if_output() should be called without ifnet.if_serializer being
  held.  Add assertion about it in ether_output().
- ether_output_frame() should be called without the ifnet.if_serializer
  being held.  Add assertion in it.
- arp_ifinit() will be called with ifnet.if_serializer being held.  To
  prevent serializer from recursion, ifnet.if_serializer is released
  before calling arprequest(), which supposes caller does not hold output
  iface's serializer.
- ifnet.if_serializer can't be held when calling arp_ifinit2().

Reported-by: dillon@

- Add tunables and sysctl nodes for interrupt moderation variables.
  Settings are committed to device during device initialization or in
  interrupt routine.
- Default interrupt moderation variables' value from Broadcom's driver
  seem to be misconfigiured.  Following changes are made:
  Send max coalesced BD count 20 -> 24
  Send coalescing ticks 80 -> 1000 (~1000HZ)
  Receive max coalesced BD count 6  -> 24
  Receive coalescing ticks 18 -> 125  (~8000Hz)
  Two changes on "Receive" interrupt moderation variables avoid livelock

Include sys/fd_set.h in the BSD_VISIBLE case.

Seems that a lot of software assumes that fd_set will be defined after
including sys/types.h, so restore this property.

Noted-by: hasso@

Move definition of fd_set to sys/fd_set.h.

Generate a semi-random MAC address when connecting to a SOCK_SEQPACKET
socket (ala vknetd's /dev/vknet) instead of a TAP interface.

Implement a new utility called vknet.  This utility interconnects the
networks between the local machine and a remote machine, typically by
connecting to a TAP interface or socket supplied by a running vknetd on
each machine.

Update manual pages for vknetd and vkernel to include vknet.

Only test the IP protocol (ip_p) for IP frames.