Remove $FreeBSD$: one-line .c pattern

Remove /^[\s*]*__FBSDID\("\$FreeBSD\$"\);?\s*\n/

spdx: The BSD-2-Clause-FreeBSD identifier is obsolete, drop -FreeBSD

The SPDX folks have obsoleted the BSD-2-Clause-FreeBSD identifier. Catch
up to that fact and revert to their recommended match of BSD-2-Clause.

Discussed with: pfg
MFC After: 3 days
Sponsored by: Netflix

sort: remove NLS support

NLS support for sort(1) is:
1/ incomplete: many error string are not using nls
2/ only covers hu_HU.ISO8859-2

sort: Fix message catalogue usage

- Check that catopen() succeeded before calling catclose(). musl will
crash in the latter if the catalogue descriptor is -1.
- Keep the message catalogue open for most of sort(1)'s actual
operation.
- Don't use catgets(3) to print error messages if catopen(3) had failed.

Reviewed by: arichardson, emaste
MFC after: 1 week
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D34081

sort: Cache value of MB_CUR_MAX

Every usage of MB_CUR_MAX results in a call to __mb_cur_max. This is
inefficient and redundant. Caching the value of MB_CUR_MAX in a global
variable removes these calls and speeds up the runtime of sort. For
numeric sorting, runtime is almost halved in some tests.

PR: 255551
PR: 255840
Reviewed by: markj
MFC after: 1 week
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D30170

sort: Stop "fixing" obsolete key syntax after -- flag

PR: 255798
Reviewed by: markj
MFC after: 1 week
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D30234

sort(1): Memoize MD5 computation to reduce repeated computation

Experimentally, reduces sort -R time of a 148160 line corpus from about
3.15s to about 0.93s on this particular system.

There's probably room for improvement using some digest other than md5, but
I don't want to look at sort(1) anymore. Some discussion of other possible
improvements in the Test Plan section of the Differential.

PR: 230792
Reviewed by: jhb (earlier version)
Differential Revision: https://reviews.freebsd.org/D19885

sort(1): Simplify and bound random seeding

Bound input file processing length to avoid the issue reported in [1]. For
simplicity, only allow regular file and character device inputs. For
character devices, only allow /dev/random (and /dev/urandom symblink).

32 bytes of random is perfectly sufficient to seed MD5; we don't need any
more. Users that want to use large files as seeds are encouraged to truncate
those files down to an appropriate input file via tools like sha256(1).

(This does not change the sort algorithm of sort -R.)

[1]: https://lists.freebsd.org/pipermail/freebsd-hackers/2018-August/053152.html

PR: 230792
Reported by: Ali Abdallah <aliovx AT gmail.com>
Relnotes: yes

sort(1): Whitespace and style cleanup

No functional change.

Sponsored by: Dell EMC Isilon

sort(1): Fix -m when only implicit stdin is used for input

Observe:

printf "a\nb\nc\n" > /tmp/foo
# Next command results in no output
cat /tmp/foo | sort -m
# Next command results in proper output
cat /tmp/foo | sort -m -
# Also works:
sort -m /tmp/foo

Some const'ification was done to simplify the actual solution of adding "-"
explicitly to the file list if we didn't have any file arguments left over.

PR: 190099
MFC after: 1 week

various: general adoption of SPDX licensing ID tags.

Mainly focus on files that use BSD 2-Clause license, however the tool I
was using misidentified many licenses so this was mostly a manual - error
prone - task.

The Software Package Data Exchange (SPDX) group provides a specification
to make it easier for automated tools to detect and summarize well known
opensource licenses. We are gradually adopting the specification, noting
that the tags are considered only advisory and do not, in any way,
superceed or replace the license texts.

No functional change intended.

pages and psize are always assigned, so there is no need to initialize
them as zero.

MFC after: 2 weeks

Eliminate variables that are computed, assigned but never
used.

MFC after: 2 weeks

Fix an obvious typo.

MFC after: 2 weeks

-C and -c allow at most one input file. Ensure this is the case when the
input files are specified through --files0-from.

Submitted by: tim@OpenBSD
Obtained from: OpenBSD
MFC after: 1 week

Remove custom getdelim(3) and fix a small memory leak.

Originally from Andre Smagin.

Obtained from: OpenBSD
MFC after: 1 week

sort: style knits / cleanups.

Minor cleanups that got accidentally reverted.

Obtained from: OpenBSD

Revert (partial) r281123, r281125:
sort: style knits / cleanups.

Our style guide(9) specifies that in absence of local variables
an empty line must be inserted.

Pointed out by: eadler

sort: style knits / cleanups.

Obtained from: OpenBSD

Make sure to not skip any argument when converting from deprecated
+POS1, -POS2 to -kPOS1,POS2, so that sort +0n gets translated to sort -k1,1n
as it is expected

PR: 193994
Submitted by: rodrigo
MFC after: 3 days

- Update Oleg Moskalenko's email address

Requested by: Oleg Moskalenko <mom040267@gmail.com>

- Remove forgotten commented out debug code

Submitted by: Christoph Mallon <christoph.mallon@gmx.de>
Reviewed by: Oleg Moskalenko <oleg.moskalenko@citrix.com>

- Simplify and unify diagnostic and error message handling

Submitted by: Christoph Mallon <christoph.mallon@gmx.de>
Reviewed by: Oleg Moskalenko <oleg.moskalenko@citrix.com>

- Change the memory heuristics to an actually working one

Submitted by: Oleg Moskalenko <oleg.moskalenko@citrix.com>
Prodded by: kib

- Use unsigned int for values obtained with sysctlbyname(). This fixes
sparc64 performance problems.

Submitted by: Oleg Moskalenko <oleg.moskalenko@citrix.com>
Tested by: trasz

- Portability changes for ARM
- Allow larger sort memory on 64-bit platforms

Submitted by: Oleg Moskalenko <oleg.moskalenko@citrix.com>

More -Wmissing-variable-declarations fixes.

In addition to adding `static' where possible:

- bin/date: Move `retval' into extern.h to make it visible to date.c.
- bin/ed: Move globally used variables into ed.h.
- sbin/camcontrol: Move `verbose' into camcontrol.h and fix shadow warnings.
- usr.bin/calendar: Remove unneeded variables.
- usr.bin/chat: Make `line' local instead of global.
- usr.bin/elfdump: Comment out unneeded function.
- usr.bin/rlogin: Use _Noreturn instead of __dead2.
- usr.bin/tset: Pull `Ospeed' into extern.h.
- usr.sbin/mfiutil: Put global variables in mfiutil.h.
- usr.sbin/pkg: Remove unused `os_corres'.
- usr.sbin/quotaon, usr.sbin/repquota: Remove unused `qfname'.

- Change --nthreads parameter to --parallel for GNU compatibility
- Change default sort method to mergesort, which has a better worst case
performance than qsort

Submitted by: Oleg Moskalenko <oleg.moskalenko@citrix.com>

- Only use multi-threading for large files
- Do not use mmap() by default; it can be enabled by --mmap
- Add some minor optimizations for -u
- Update manual page according to the changes

Submitted by: Oleg Moskalenko <oleg.moskalenko@citrix.com>

- Fix -o option that was broken by my clang compile fix

Submitted by: Oleg Moskalenko <oleg.moskalenko@citrix.com>

- Eliminate initializations if global variables. Compilers are not
required to optimize these so it may result in larger binary size.

Pointed out by: kib

- Fix build with clang

Add a BSD-licensed sort rewrite that was started by me and later completed
with the major functionality and optimizations by Oleg Moskalenko.
It is compatible with the latest version of POSIX and the current GNU sort
version that we have in base. Beside this, it implements all the
functionality introduced in later versions of GNU sort. For now, it will
be installed as "bsdsort", keeping GNU sort as the default sort
implementation.

Remove old sort files to _actually_ build it from contrib sources

Forgotten by: des

Remove __P

Remove \n from __COPYRIGHT to shut assembler warning

Remove double SINGL_FLD and SEP_FLAG initialization

Remove double REC_D assignment
Cast REC_D optarg assignment to (u_char) to prevent out of bounds indexing

Make this compile on FreeBSD. Sort out VCS tags, fix warnings.

Vendor import NETBSD's sort(1). This will be a replacement for
our GNU sort, as discussed 6 months or more ago.