kernel/scheduler: Always reschedule after enqueueing if the runqueue was empty.

Normally the heap's priority will suffice to check if we need to reschedule.
However, in cases where the CPU in question is currently in the middle of
rescheduling already, and it is about to change its priority to "idle",
we can race with it and not notice that we need to send it an ICI.
Previously this meant we would just lose some performance, but after
recent fixes to not reschedule only as necessary, this race led to hangs.

Now we report whether the runqueue we added the thread to was empty
in ThreadData::Enqueue(), and if it was, we then always trigger a
scheduler invocation on the target CPU.

In my testing, this fixes #17847; and at least in my unscientific
benchmarks, improves compile performance by as much as 10% (I saw
~55s -> ~50s in some tests.)

scheduler: Let ThreadData::ShouldRebalance() choose the actual core

Currently, ThreadData::ShouldRebalance() (and mode specific functions
it calls) only decides whether to migrate thread to another core or not.
However, in most cases it actually needs to find the best candidate for
new core so it could as well return that information.

scheduler: Relax penalty cancellation requirements

Priority penalties were made more strict in order to prevent situation
when two or more high priority threads uses up all available CPU time
in such manner that they do not receive a penalty but starve low priority
threads.

However, a significant change to thread priorites has been made since and
now priority of all non real time threads varies in a range from 1 to
static priority minus penalty. This means that the scheduler is able to
prevent thread starvation without any complex penalty policies.

scheduler: Provide more stable core load statistics

Originially, core load was a sum of eastimated loads of all currently
running or ready threads on a given core. Such value is changing very
rapidly preventing the thread migration logic from making any reasonable
decisions.

This patch changes the way core load is computed to make it more stable
thus improving the qualitiy of decisions made by the thread migration logic.
Currently core load is a sum of estimated loads of all threads that have been
ready during last load measurement interval and haven't been migrated or
killed.

scheduler: Fix core unassignment

scheduler: Check team user time timers before entering scheduler

User timers may cause another thread to become ready in which case we would
like this to happen before scheduler_reschedule() chooses next thread to
be executed.

scheduler: Always update core load at thread reenqueue

scheduler: system_time() may be unreliable

On multisocket systems as well as under virtual machines logical CPUs
may use separate TSC. We could attempt to synchronize them what probably
would solve problems on multisocket systems. Unfortunately, when running
under hypervisor there is still a chance that TSC will get out of sync
again (e.g. cpufreq enabled on host when there is no invariant TSC). As
long as we use RDTSC as our main time source the scheduler must accept the
fact that time may go backwards (what isn't really a serious problem).

scheduler: Weaken time slept assertion

scheduler: Cache quantum length

scheudler: Cache ThreadData::IsCPUBound() result

scheduler: Add ThreadData::{GetPriority, IsIdle, IsRealTime}()

scheduler: Improve latencies

scheduler: Update used time when thread yields or sleeps

scheduler: Increase thread penalty at fork

scheduler: Estimate the load thread is able to produce

Previous implementation based on the actual load of each core and share
each thread has in that load turned up to be very problematic when
balancing load on very heavily loaded systems (i.e. more threads
consuming all available CPU time than there is logical CPUs).

The new approach is to estimate how much load would a thread produce
if it had all CPU time only for itself. Summing such load estimations
of each thread assigned to a given core we get a rank that contains
much more information than just simple actual core load.

scheduler: Introduce strong and weak priority penalties

scheduler: Keep track of the number of the ready threads

scheduler: Improve recognition of CPU bound threads

kernel: Relax cpu_ent::interrupt_time locking

The value isn't accessed by the other CPUs and all writes and reads are
done with interrupts disabled.

scheduler: Improve thread creation performance

scheduler: Work around GCC2 limitations in function inlining

GCC2 won't inline a function if it is used before its definition.

scheduler: Disable load tracking when not needed

scheduler: Inherit penalty and core from creator thread

scheduler: Protect per CPU run queue with its own lock

scheduler: Fix double release of run queue lock

scheduler: Remove CPUEntry::IncreaseActiveTime()

scheduler: Add scheduler profiler

A bit hackish implementation of a profiler for the scheduler.
SCHEDULER_ENTER_FUNCTION at the begining of each function aren't nice and
usage of __PRETTY_FUNCTION__ isn't any better (both gcc and clang support
it though), but it was quick to implement and doesn't lose information
on inlined functions. It's just a tool, not an integral part of the kernal
anyway.

scheduler: No need for gQuantumLengths to be global

scheduler: Use precomputed time slice lengths

scheduler: Keep thread effective priority cached

scheduler: Encapsulate ThreadData fields

scheduler: Encapsulate CPUEntry fields

scheduler: Encapsulate CoreEntry fields

scheduler: Encapsulate PackageEntry fields

Apart from the refactoring this commit takes the opportunity and removes
unnecessary read locks when choosing a package and a core from idle lists.
The data structures are accessed in a thread safe way and it does not really
matter whether the obtained data becomes outdated just when we release the
lock or during our search for the appropriate package/core.

scheduler: Try to keep thread on the same logical CPU

Some SMT implementations (e.g. recent AMD microarchitectures) have
separate L1d cache for each SMT thread (which AMD decides to call "cores").
This means that we shouldn't move threads to another logical processor too
often even if it belongs to the same core. We aren't very strict about
this as it would complicate load balancing, but we try to reduce unnecessary
migrations.

scheduler: Use sequential locks instead of atomic 64 bit access

scheduler: Code refactoring

scheduler: Let ThreadData::ShouldRebalance() choose the actual core

Currently, ThreadData::ShouldRebalance() (and mode specific functions
it calls) only decides whether to migrate thread to another core or not.
However, in most cases it actually needs to find the best candidate for
new core so it could as well return that information.

scheduler: Relax penalty cancellation requirements

Priority penalties were made more strict in order to prevent situation
when two or more high priority threads uses up all available CPU time
in such manner that they do not receive a penalty but starve low priority
threads.

However, a significant change to thread priorites has been made since and
now priority of all non real time threads varies in a range from 1 to
static priority minus penalty. This means that the scheduler is able to
prevent thread starvation without any complex penalty policies.

scheduler: Provide more stable core load statistics

Originially, core load was a sum of eastimated loads of all currently
running or ready threads on a given core. Such value is changing very
rapidly preventing the thread migration logic from making any reasonable
decisions.

This patch changes the way core load is computed to make it more stable
thus improving the qualitiy of decisions made by the thread migration logic.
Currently core load is a sum of estimated loads of all threads that have been
ready during last load measurement interval and haven't been migrated or
killed.

scheduler: Fix core unassignment

scheduler: Check team user time timers before entering scheduler

User timers may cause another thread to become ready in which case we would
like this to happen before scheduler_reschedule() chooses next thread to
be executed.

scheduler: Always update core load at thread reenqueue

scheduler: system_time() may be unreliable

On multisocket systems as well as under virtual machines logical CPUs
may use separate TSC. We could attempt to synchronize them what probably
would solve problems on multisocket systems. Unfortunately, when running
under hypervisor there is still a chance that TSC will get out of sync
again (e.g. cpufreq enabled on host when there is no invariant TSC). As
long as we use RDTSC as our main time source the scheduler must accept the
fact that time may go backwards (what isn't really a serious problem).

scheduler: Weaken time slept assertion

scheduler: Cache quantum length

scheudler: Cache ThreadData::IsCPUBound() result

scheduler: Add ThreadData::{GetPriority, IsIdle, IsRealTime}()

scheduler: Improve latencies

scheduler: Update used time when thread yields or sleeps

scheduler: Increase thread penalty at fork

scheduler: Estimate the load thread is able to produce

Previous implementation based on the actual load of each core and share
each thread has in that load turned up to be very problematic when
balancing load on very heavily loaded systems (i.e. more threads
consuming all available CPU time than there is logical CPUs).

The new approach is to estimate how much load would a thread produce
if it had all CPU time only for itself. Summing such load estimations
of each thread assigned to a given core we get a rank that contains
much more information than just simple actual core load.

scheduler: Introduce strong and weak priority penalties

scheduler: Keep track of the number of the ready threads

scheduler: Improve recognition of CPU bound threads

kernel: Relax cpu_ent::interrupt_time locking

The value isn't accessed by the other CPUs and all writes and reads are
done with interrupts disabled.

scheduler: Improve thread creation performance

scheduler: Work around GCC2 limitations in function inlining

GCC2 won't inline a function if it is used before its definition.

scheduler: Disable load tracking when not needed

scheduler: Inherit penalty and core from creator thread

scheduler: Protect per CPU run queue with its own lock

scheduler: Fix double release of run queue lock

scheduler: Remove CPUEntry::IncreaseActiveTime()

scheduler: Add scheduler profiler

A bit hackish implementation of a profiler for the scheduler.
SCHEDULER_ENTER_FUNCTION at the begining of each function aren't nice and
usage of __PRETTY_FUNCTION__ isn't any better (both gcc and clang support
it though), but it was quick to implement and doesn't lose information
on inlined functions. It's just a tool, not an integral part of the kernal
anyway.

scheduler: No need for gQuantumLengths to be global

scheduler: Use precomputed time slice lengths

scheduler: Keep thread effective priority cached

scheduler: Encapsulate ThreadData fields

scheduler: Encapsulate CPUEntry fields

scheduler: Encapsulate CoreEntry fields

scheduler: Encapsulate PackageEntry fields

Apart from the refactoring this commit takes the opportunity and removes
unnecessary read locks when choosing a package and a core from idle lists.
The data structures are accessed in a thread safe way and it does not really
matter whether the obtained data becomes outdated just when we release the
lock or during our search for the appropriate package/core.

scheduler: Try to keep thread on the same logical CPU

Some SMT implementations (e.g. recent AMD microarchitectures) have
separate L1d cache for each SMT thread (which AMD decides to call "cores").
This means that we shouldn't move threads to another logical processor too
often even if it belongs to the same core. We aren't very strict about
this as it would complicate load balancing, but we try to reduce unnecessary
migrations.

scheduler: Use sequential locks instead of atomic 64 bit access

scheduler: Code refactoring