kernel - Scale tsleep() performance vs many (thousands) of processes

* In situations where a huge number of processes or threads are present
  and sleeping (that is, more than a few thousand), the global cpumask hash
  table used by tsleep() would saturate and effectively cause any wakeup()
  call to broadcast to all CPUs.

* Refactor the tsleep initialization code to allow the global cpumask
  hash table and the pcpu hash tables to be dynamically allocated.

* Allocate a MUCH larger global cpumask hash table, and significantly
  smaller pcpu hash tables.  The global cpumask hash table is now
  sized to approximate 2 * maxproc, greatly reducing cpumask collisions
  when large numbers of processes exist in the system.

  The pcpu hash tables can be smaller without effecting performance.  This
  will simply result in more entries in each queue which are trivially
  iterated.

  Nominal maxproc ~32,000 -> in the noise (normal desktop system)
  Nominal maxproc ~250,000 -> 16MB worth of hash tables (on a 128G box)
  Maximal maxproc ~2,000,000 -> 122MB worth of hash tables (on a 128G box)

* Remove the unused sched_quantum sysctl and variable.

* Tested with running a pipe() chain through 900,000 processes, the
  end-to-end latency dropped from 25 seconds to 10 seconds and the
  pcpu IPI rate dropped from 60,000 IPIs/cpu to 5000 IPIs/cpu.  This
  is still a bit more than ideal, but much better than before.

* Fix a low-memory panic in zalloc().  A possible infinite recursion
  was not being properly handled.

kernel - Change maxproc cap calculation

* Increase the calculation for the maxproc cap based on physical ram.
  This allows a machine with 128GB of ram to maxproc past a million,
  though it should be noted that PIDs are only 6-digits, so for now
  a million processes is the actual limit.

kernel - Break up scheduler and loadavg callout

* Change the scheduler and loadavg callouts from cpu 0 to all cpus, and
  adjust the allproc_scan() and alllwp_scan() to segment the hash table
  when asked.

  Every cpu is now tasked with handling the nominal scheduler recalc and
  nominal load calculation for a portion of the process list.  The portion
  is unrelated to which cpu(s) the processes are actually scheduled on,
  it is strictly a way to spread the work around, split up by hash range.

* Significantly reduces cpu 0 stalls when a large number of user processes
  or threads are present (that is, in the tens of thousands or more).  In
  the test below, before this change, cpu 0 was straining under 40%+
  interupt load (from the callout).  After this change the load is spread
  across all cpus, approximately 1.5% per cpu.

* Tested with 400,000 running user processes on a 32-thread dual-socket
  xeon (yes, these numbers are real):

  12:27PM  up 8 mins,  3 users, load avg: 395143.28, 270541.13, 132638.33
  12:33PM  up 14 mins, 3 users, load avg: 399496.57, 361405.54, 225669.14

* NOTE: There are still a number of other non-segmented allproc scans in
the system, particularly related to paging and swapping.

* NOTE: Further spreading-out of the work may be needed, by using a more
   frequent callout and smaller hash index range for each.

kernel - Bump wakeup hash size a little

* Bump from 4001 to 8191 entries to reduce chain length to help situations
  where a large numbers of user threads are in a wait state (in the tens or
  hundreds of thousands of threads).

kernel - loadavg structure 32->64 bit fields

* The loadavg structure overflows when a large number of processes
  are running.  Yes, I in fact got it to overflow.  Change the load
  fields from 32 to 64 bits.

* Tested to 400,000 runnable processes.

kernel - Fix bottlenecks that develop when many processes are running

* When a large number of processes or threads are running (in the tens of
  thousands or more), a number of O(n) or O(ncpus) bottlenecks can develop.
  These bottlenecks do not develop when only a few thousand threads
  are present.

  By fixing these bottlenecks, and assuming kern.maxproc is autoconfigured
  or manually set high enough, DFly can now handle hundreds of thousands
  of active processes running, polling, sleeping, whatever.

  Tested to around 400,000 discrete processes (no shared VM pages) on
  a 32-thread dual-socket Xeon system.  Each process is placed in a
  1/10 second sleep loop using umtx timeouts:

  baseline  - (before changes), system bottlenecked starting
  at around the 30,000 process mark, eating all
  available cpu, high IPI rate from hash
  collisions, and other unrelated user processes
  bogged down due to the scheduling overhead.

  200,000 processes - System settles down to 45% idle, and low IPI
  rate.

  220,000 processes - System 30% idle and low IPI rate

  250,000 processes - System 0% idle and low IPI rate

  300,000 processes - System 0% idle and low IPI rate.

  400,000 processes - Scheduler begins to bottleneck again after the
  350,000 while the process test is still in its
  fork/exec loop.

  Once all 400,000 processes are settled down,
  system behaves fairly well.  0% idle, modest
  IPI rate averaging 300 IPI/sec/cpu (due to
  hash collisions in the wakeup code).

* More work will be needed to better handle processes with massively
  shared VM pages.

  It should also be noted that the system does a *VERY* good job
  allocating and releasing kernel resources during this test using
  discrete processes.  It can kill 400,000 processes in a few seconds
  when I ^C the test.

* Change lwkt_enqueue()'s linear td_runq scan into a double-ended scan.
  This bottleneck does not arise when large numbers of processes are
  running in usermode, because typically only one user process per cpu
  will be scheduled to LWKT.

  However, this bottleneck does arise when large numbers of threads
  are woken up in-kernel.  While in-kernel, a thread schedules directly
  to LWKT.  Round-robin operation tends to result in appends to the tail
  of the queue, so this optimization saves an enormous amount of cpu
  time when large numbers of threads are present.

* Limit ncallout to ~5 minutes worth of ring.  The calculation code is
  primarily designed to allocate less space on low-memory machines,
  but will also cause an excessively-sized ring to be allocated on
  large-memory machines.  512MB was observed on a 32-way box.

* Remove vm_map->hint, which had basically stopped functioning in a
  useful manner.  Add a new vm_map hinting mechanism that caches up to
  four (size, align) start addresses for vm_map_findspace().  This cache
  is used to quickly index into the linear vm_map_entry list before
  entering the linear search phase.

  This fixes a serious bottleneck that arises due to vm_map_findspace()'s
  linear scan if the vm_map_entry list when the kernel_map becomes
  fragmented, typically when the machine is managing a large number of
  processes or threads (in the tens of thousands or more).

  This will also reduce overheads for processes with highly fragmented
  vm_maps.

* Dynamically size the action_hash[] array in vm/vm_page.c.  This array
  is used to record blocked umtx operations.  The limited size of the
  array could result in an excessive number of hash entries when a large
  number of processes/threads are present in the system.  Again, the
  effect is noticed as the number of threads exceeds a few tens of
  thousands.

kernel - Lower VM_MAX_USER_ADDRESS to finalize work-around for Ryzen bug

* Reduce VM_MAX_USER_ADDRESS by 2MB, effectively making the top 2MB of the
  user address space unmappable.  The user stack now starts 2MB down from
  where it did before.  Theoretically we only need to reduce the top of
  the user address space by 4KB, but doing it by 2MB may be more useful for
  future page table optimizations.

* As per AMD, Ryzen has an issue when the instruction pre-fetcher crosses
  from canonical to non-canonical address space.  This can only occur at
  the top of the user stack.

  In DragonFlyBSD, the signal trampoline resides at the top of the user stack
  and an IRETQ into it can cause a Ryzen box to lockup and destabilize due
  to this action.  The bug case was, basically two cpu threads on the same
  core, one in a cpu-bound loop of some sort while the other takes a normal
  UNIX signal (causing the IRETQ into the signal trampoline).  The IRETQ
  microcode freezes until the cpu-bound loop terminates, preventing the
  cpu thread from being able to take any interrupt or IPI whatsoever for
  the duration, and the cpu may destabilize afterwords as well.

* The pre-fetcher is somewhat heuristical, so just moving the trampoline
  down is no guarantee if the top 4KB of the user stack is mapped or mappable.
  It is better to make the boundary unmappable by userland.

* Bug first tracked down by myself in early 2017.  AMD validated the bug
  and determined that unmapping the boundary page completely solves the
  issue.

* Also retain the code which places the signal trampoline in its own page
  so we can maintain separate protection settings for the code, and make it
  read-only (R+X).

kcollect - Fix grammar

* gunplot -> gnuplot

Reported-by: Steve Horan <steve@horan.net.au>

mbuf: Minor style change.

netisr: Simplify assertion related bits

stf: Make route per-cpu.  And it should run in the first netisr_ncpus netisrs.

gre: Rework routing facilities.

- Make route per-cpu.
- Make sure that all routing related operation happens in the first
  netisr_ncpus netisrs.

route: Minor cleanup

route: Delete ortentry, SIOC{ADD,DEL}RT and RTM_OLD{ADD,DEL}

They have not been used for more than a decade.

gif: It should only run in the first netisr_ncpus netisrs

route: Add rtfree_async.

This prepares to run rtalloc/lookup/free in the first netisr_ncpus
netisrs.  This function is only intended to be used on slow path;
e.g. detach.

ps(1): Remove -I${.CURDIR}/../../sys from the Makefile.

FreeBSD did that in 2001 (r76812). It's not a bootstrap tool, so there
is no reason to mix up include paths.

kernel - Move sigtramp even lower

* Attempt to work around a Ryzen cpu bug by moving sigtramp even lower than
  we have already.

kdump(8): Add more support for printing flag etc. names.

* New support for: eaccess() modes, faccessat() modes and atflag,
    fchmodat() atflag, fchownat() atflag, fstatat() atflag,
    linkat() atflag, unlinkat() atflag, utimensat() atflag,
    getvfsstat() flags, lchflags() flags, chflagsat() flags and atflag,
    kenv() actions, usched_set() commands, sys_checkpoint() types,
    procctl() commands, mountctl() operations, and varsym_{list,set}()
    levels.

* Fix flags printing in chflags() and fchflags().

* Better separate mount() and getfsstat() flags definitions.

* Adjust grepping for fcntl() commands send/recvmsg() etc. flags to
    include flags with more than one underscore in their name, like
    F_DUPFD_CLOEXEC.

Still missing: extexit()'s 'how' argument.

kdump(1): Oops, remove forgotten include.

kdump(1): Remove unused ptraceopname(). ptrace ops are handled specially.

procfs - Fix blocked lock condition

* Two procfs races can result in a lock being blocked forever.  Rip out
  the old single-variable global procfs lock and per-node lock and replace
  with a normal lockmgr lock.

* The original lock existed from a time when all of procfs was wrapped with
  a global lock.  This is no longer the case.

kernel - Fix serious permissions bug for sticky directories

* An optimization improperly bypassed the sticky-bit test, creating
  a security issue with /tmp and /var/tmp.

* Fix by disabling the optimization for the second-to-last path component.
  Any prior components retain the optimization, so long directory paths
  are still well-optimized.

kdump(1): Add pathconf(2) variable name printing.

kdump(1): Add clockid_t name printing.

kdump(1): Allow auto switch funcs to not have an 'invalid' default case.

<sys/un.h>: Clean up namespace.

Remove some no longer used header files.

* <sys/device_port.h>: Kernel only, last consumer was scsi_low which was
    removed in 075c6d38244abd0b0c8dc9b2974ef574b9180bf5 in January.

* <sys/ieee754.h>: NetBSD header that is supposed to be included from
    the implementation's ieee.h header, which ours no longer does, so
    it's a leftover from some earlier state of our libm.

* <nlist_aout.h>: Last consumer was removed in 2009 when a.out support
    was dropped from modules (70eee1c9363092cae6ef68466a44ad68fa22e183).

/boot/defaults/loader.conf: Fix typo.

ipid: Call ip_randomid() on all CPUs.

- Remove unnecessary crit sections.
- Remove unapplied comment.
- Minor style fixes.

pfsync: Send packet in netisr0 and do it asynchronously.

mbuf: Add message header for generic mbuf sending/receiving.

ifconfig.8: Fix typo.

inpcb: Simplify inpcb marker interface

inpcb: All inpcb accessing should be from first netisr_ncpus netisrs

inet: ip_{output/input}() should only run in first netisr_ncpus netisrs

udp: It only runs in the first netisr_ncpus netisrs.

systimer: Adjust systimers on their owner cpus.

tcp: Prevent excessive IPI from draining TCP reassemble queues.

inet: Prevent excessive IPI from draining PR cloned host routes.

inet: Fix up draining flag setting.

inet: Prevent excessive IPI from draining IPv4 fragments.

inet6: Prevent excessive IPI from draining IPv6 fragments.

net: Use PR_{FAST,SLOW}HZ, some code has the assumption of these macro usage.

efivar.8: Fix typos/improve language (taken from FreeBSD).

libthread_xu: Add a check for integer overflow (FreeBSD r321011).

domain: Nuke pfslowtimo.

ip: Don't use pr_slowtimo.

igmp: Don't use pr_slowtimo.

inet6: Drain IPv6 fragments in netisr0

inet6: Dispatch frag6 slowtimo to netisr0 and stop using pr_slowtimo

domain: Nuke pffasttimo

kernel: Fix wrong indentation in a few places.

kernel/sdhci: Remove wrong semicolon.

kernel/ieee80211: Add missing braces.

kernel/urtwn: Add missing braces.

igmp: Use callout instead of pffasttimo.

icmp6: Don't use pffasttimo and dispatch fasttimo to netisr0

Reported-by: ivadasz

kernel: Add FreeBSD's virtio_scsi(4) driver.

Thanks to ivadasz for figuring out the shutdown freeze issue
(see c022ffc9484ecf07d8d7c4fb918d84a6154367be).

Tested-by: ivadasz, Peter Cannici <turkchess123@gmail.com>

kernel/cam: Add CAM_SCSI_IT_NEXUS_LOST (in preparation for virtio_scsi(4)).

larn(6): Fix two "use of index before limits check" issues.

Make sure that cam(4)'s dashutdown handler runs before DEVICE_SHUTDOWN().

This meant, that the DEVICE_SHUTDOWN() callback of scsi drivers was running
before the final SYNCHRONIZE_CACHE scsi command was sent by cam(4). For
most drivers this was still fine, since usually the DEVICE_SHUTDOWN()
callback - if it's even implemented - only flushes the command queue.

This change avoids freezing at the end of shutdown which was known to
happen with the twa(4), and virtio_scsi(4) drivers.

The SHUTDOWN_PRI_SECOND priority is selected, because it's so far unused,
and inbetween existing handlers in the shutdown_post_sync phase, that are
at SHUTDOWN_PRI_FIRST and at SHUTDOWN_PRI_DEFAULT.

Tested-by: swildner (on twa(4)), ivadasz (on virtio_scsi(4))

kernel - Fix kcollect swapuse%

* The calculation was improperly using vm_swap_size (which is really free swap
  remaining) instead of vm_swap_max.

kcollect - add swap% to plot output

* swap% used can be added easily, so go ahead and do it.  Added to the bottom
  graph.

kcollect - Fix gunplot warning when -x -f is specified

* gnuplot warns about multiple set terminal commands when the refresh
  occurs.  Rearrange when the command is sent to avoid the problem.

kcollect - Add a smoothing option (-s)

* Add an option (-s) which smooths the plot.  The smoothing algorithm uses
  an exponential average with fast collapse to the high-side so spikes do
  not get lost.

kcollect - Add -t option to limit output

* Add the -t N option, limiting the output to the most recent N seconds
  worth of samples.  'm'inutes, 'h'ours, and 'd'ays suffixes are allowed
  for convenience.

kcollect - Adjust ordering of gnuplot solids

* Adjust ordering so active use fills solids upwards instead of downwards.

kcollect - Implement gnuplot output feature

* Implement the gunplot output feature.  This feature currently
  hard-selects a set of fields (fields cannot be specified).

  Generates two graphs.  The first collects memory statistics
  and machine load.  The second collects cpu utilization and
  fault, syscall, and nlookup (file path resolution) rate.

* In gnuplot output mode, -f will cause the entire dataset to be
  regenerated every 60 seconds (I don't see any way to avoid this
  to update an existing gnuplot window).

* Finish implementing -o fields

kcollect - Fix swap text output

* Collection data for type 'm' is still stored in bytes.

* Fix field width for megabytes display field.

kernel - Store page statistics in bytes

* Store page statistics in bytes rather than pages.  Pages aren't useful
  for userland display and there is no reason to force useland to do the
  conversion.

* Include a realtime timestamp along with ticks in the structure.

* Flesh out text output for kcollect.  Reverse output order to print
  oldest data first, so output from the -f option stays consistent.

kernel - Add a sampling history mechanism called kcollect (2)

* Add collection code for remaining base statistics.

* Round-up some calculations.

Restore WARNS in ftpd, it was just for testing.

ftpd(8): Remove weird line with just '#'.

ccdconfig(8): Add missing free().

Reported-by: dcb
Dragonfly-bug: <https://bugs.dragonflybsd.org/issues/3014>

kernel: Remove some variables that are only set but never used.

Reported-by: dcb
Dragonfly-bug: <https://bugs.dragonflybsd.org/issues/3019>

libpuffs: Fix two asserts.

Reported-by: dcb
Dragonfly-bug: <https://bugs.dragonflybsd.org/issues/3013>

kernel - Add a sampling history mechanism called kcollect

* Add a kernel API which automatically samples useful statistics on a
  10-second period without needing a user program to poll it.  This API
  is enabled by default and can be disabled by setting kern.collect_samples=0
  in /boot/loader.conf (or setting it higher, if desired).

  The idea is for the kernel to always collect a solid amount of historical
  data for various useful statistics such that a user can pull it all up
  going back upwards of 23 hours (or more, depending on configured samples)
  after the fact.  "Oh, what happened recently"... bang.

* The sysctl provides sufficient information to userland to be able to
  process the statistics dynamically, without necessarily having to know
  what they are.

  The sysctl can be cut short to request less data for ongoing incremental
  collection, if desired.

* Implement "load" collection to start with as a test.  Add #defines for
  everything I want the kernel to collect.  The kernel API's critical path
  is lockless.

* Start working on a front-end user program called 'kcollect'.  This program
  will eventually generate fancy graphs via gnuplot and have a dbm interface
  for collecting data continuously if desired.

<sys/malloc.h>: Remove an empty #ifdef.

Sync ACPICA with Intel's version 20170728.

* Support in the resource walking code for _DMA.

* Various additions and improvements.

* Fix various bugs and regressions.

For a more detailed list, please see sys/contrib/dev/acpica/changes.txt.

polling: Simplify the code by using netsr_*msg functions.

netisr: Add netisr_sendmsg_oncpu()

bridge: It should only run in netisr_cpus netisrs

hammer2 - Allow @LABEL to be omitted

* Allow the @LABEL in "<devicepath>@LABEL" to be omitted when mounting.
  If omitted, H2 will automatically supply "@LOCAL".

* Provides convenience for simple use cases.

hammer2 - Synchronize write-in-place feature

* Disable hole creation when the check mode is disabled on a file.
  Writing zeros maintains any previously assigned block.

* Allows reserving storage for a file (such as an image) by dd'ing
  /dev/zero into it, as long as check mode has also been disabled
  on that file.  No data CRCs or hashes will be computed or checked
  for the file.

* Note that this should still work properly with snapshots.  A snapshot
  will force block reallocation on the master for any writes that cross
  the snapshot boundary.

hammer2 - Consolidate backend rename ops

* Reduce frontend XOP ops required for rename from 3 to 2 by integrating
  the unlink-target operation into xop_nrename.  The xop_nrename backend
  function now handles replacing the target namespace when it exists and
  will also get rid of any duplicates as a safety.

* Adjust the frontend inode locking order to try to avoid deadlocks.

* Adjust iparent documentation.

* Properly set iparent in the rename operation.  The iparent was not
  being adjusted at all.

* Properly set iparent in the inode create operation.  The iparent was
  improperly being set to 0 instead 1 when the parent directory was the
  mount point.

libc - Fix bug in rcmdsh()

* rcmdsh() (which really nothing should be using any more anyway) used
  a generic wait(NULL) to wait for a child to exit, but this can wind
  up waiting for the wrong pid in a multi-threaded or multi-fork environment.

* Solved by waiting on the specific pid instead.

sshlockout - Improve manual page

* Rewrite the manual page, provide a more concise example.

* Suggest using pfctl -T expire <seconds> instead of -T flush for the
  crontab entry.

Reported-by: Miroslav Lachman <000.fbsd@quip.cz>

libc/libpthread: Add clock_getcpuclockid() and pthread_getcpuclockid().

* Adjust clock_gettime() and clock_getres() to accept values obtained
  this way.

* Also set _POSIX_CPUTIME and _POSIX_THREAD_CPUTIME, although we should
  really support values obtained by these functions in clock_settime()
  too.

Based on and taken from FreeBSD's code.

Reviewed-by: sephe

Remove <stab.h> and <struct.h>.

* <stab.h> had information about the a.out related symbol table
  format.

* <struct.h> has been removed from FreeBSD since 2001.

Both headers are not needed by anything in our tree or dports.

kernel/time: Change get_curthread_cputime() to get_thread_cputime().

<sys/types.h>: Add guard around lwpid_t, also put under __BSD_VISIBLE.

altq/cbq: Drain pending callout and the cooresponding netmsg.

altq/cbq: Redispatch restart function to netisr0.

Now, all pseudo interfaces' if_start run in netisr_ncpus netisrs.

hammer2 - Update DESIGN document

* Update the DESIGN document to reflect changes.

hammer2 - correct readdir bug

* Correct a readdir iteration bug for the new DIRENT type.

hammer2 - Initial HARDLINK -> DIRENT replacement code

* Initial removal of the vestiges of the old embedded inode code.  Inodes
  were moved to the root directory long ago but directories still contain
  dummy OBJTYPE_HARDLINK inodes instead of real directory entries to point
  to the moved inodes.  These inodes ate 1024 bytes of disk space for each
  directory entry.

* Remove the dummy OBJTYPE_HARDLINK inodes and replace with new
  BREF_TYPE_DIRENT blockrefs.  These blockrefs represent directory
  entries, and the entire dirent will fit in the blockref (requiring
  no data ref) if the filename is <= 64 bytes.

* This new DIRENT mechanic significantly improves performance and reduces
  storage overage vs the previous mechanicn, for obvious reasons.

  Directory entries are now 128 bytes instead of 1024 bytes, and since they
  are collected together in indirect blocks or (if <= 4 entries) simply
  placed in the 4 blockrefs embedded in the directory inode, the related
  I/O tends to be fairly optimal.

  Only directory entries whos filenames are > 64 bytes long require an
  additional data block reference.  For now, due to other constraints,
  we use the minimum H2 allocation size of 1KB for these, so certainly
  space is wasted.  But in real life there aren't actually a whole lot
  of filenames that are that long so it should be fine.

hammer2 - Adjust blockref to create an embedded area, start dirent work

* Create a type-specific embedded area in the blockref structure.  Move
  data_count and inode_count into the new area.  The blockref structure
  size does not change.

* Adjust code to access data_count and inode_count conditionally for
  BREF_TYPE_INODE, DATA, and INDIRECT types only.

* Now that we have abandoned embedding inodes directly in directories for
  normal operation, start working on removing HAMMER2_OBJTYPE_HARDLINK and
  creating a real directory entry abstraction.

  The real directory entry abstraction will allow directory entries to be
  directly embedded in blockref structures, without requiring a data
  reference for any filename <= 64 bytes.  This will be accomplished by
  using the new embedded area in the blockref for the directory entry
  header and the check area for the filename (up to 64 bytes).

  This will significantly improve directory compactness and I/O efficiency
  by reducing the directory entry overhead from 1152 bytes (1024 + 128) to
  just 128 bytes and guaranteeing locality since the blockrefs are
  collected together in indirect blocks.  Another nice facet is that since
  inodes can embed up to four direct blockrefs, any directory with <=
  4 entries in it can embed those entries in the directory inode itself.
  So small directories will wind up being VERY compact.

  We haven't entirely abandoned embedding inodes in directories as
  directory entries.  In fact, the feature is still used for superroot
  entries, and may be allowed in the future mixed into normal directories
  for 'special' non-hardlinkable directory inodes for quota control,
  subdirectory
  snapshot, and (NFS) export purposes.

hammer2 - Cleanup pass, remove unused fields and code

* Remove the unused per-inode cluster cache.  The code isn't really
  compatible with the XOP mechanism.

* Remove unused hammer2_xop_nlink() and related structures.  Hardlinking
  is handled through normal hammer2_inode_*() functions and no longer
  needs an explicit backend.

* Remove the unused iocb.cluster field.  iocb's are now exclusively
  backend entities.

altq: Fix typo