scheduler: Fix and simplify thread migration logic in low latency mode

This patch remove the old thread migration logic which used few special
cases and (broken) general check that attempted to balance threads.

The new logic is pretty straightforward and seems perform well without
any additional special cases. Current core is compared with the least loaded
one and the thread is migrated if that would result in estimated loads of
both cores (i.e. the current one and the least loaded one) to become closer
to the average load (i.e. average of that two cores).

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/low_latency: Try harder to balance load

In low latency mode the scheduler would not attempt to balance load
on not heavily loaded cores unless difference in load exceeded
kLoadDifference * 2 (i.e. 40 percentage points), which does not seem
to be good enough.

scheduler: Always protect gCore[High]LoadHeap with spinlock

Should fix #10628. If there is a race condition with a writer getting
minimum or maximum from double ended heap may incorrectly result NULL.
Which is not expected in the most of the thread migration logic. Apart
from that, because of the race condition heap state may be observed as
inconsistent thus failing assertions.
ended heap

scheduler: low_latency: Try to keep all cores busy

scheduler: Improve latencies

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: Improve recognition of CPU bound threads

scheduler: Improve should_rebalance

scheduler: Inherit penalty and core from creator thread

scheduler: Use single ended heap for CPU heap

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: 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: Use sequential locks instead of atomic 64 bit access

scheduler: Code refactoring

scheduler: Allow mode to specify time slice length

scheduler: Migrate threads less often in power saving mode

scheduler: Protect package data with rw_spinlock

scheduler: Fix power saving mode and other minor improvements

scheduler: Calculate correct load on SMT processors

scheduler: Improve locking

scheduler: Preallocate temporary heaps for debug commands

scheduler: Try to pack IRQs in power saving mode

scheduler: Move mode specific logic to separate files

scheduler: Fix and simplify thread migration logic in low latency mode

This patch remove the old thread migration logic which used few special
cases and (broken) general check that attempted to balance threads.

The new logic is pretty straightforward and seems perform well without
any additional special cases. Current core is compared with the least loaded
one and the thread is migrated if that would result in estimated loads of
both cores (i.e. the current one and the least loaded one) to become closer
to the average load (i.e. average of that two cores).

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/low_latency: Try harder to balance load

In low latency mode the scheduler would not attempt to balance load
on not heavily loaded cores unless difference in load exceeded
kLoadDifference * 2 (i.e. 40 percentage points), which does not seem
to be good enough.

scheduler: Always protect gCore[High]LoadHeap with spinlock

Should fix #10628. If there is a race condition with a writer getting
minimum or maximum from double ended heap may incorrectly result NULL.
Which is not expected in the most of the thread migration logic. Apart
from that, because of the race condition heap state may be observed as
inconsistent thus failing assertions.
ended heap

scheduler: low_latency: Try to keep all cores busy

scheduler: Improve latencies

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: Improve recognition of CPU bound threads

scheduler: Improve should_rebalance

scheduler: Inherit penalty and core from creator thread

scheduler: Use single ended heap for CPU heap

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: 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: Use sequential locks instead of atomic 64 bit access

scheduler: Code refactoring

scheduler: Allow mode to specify time slice length

scheduler: Migrate threads less often in power saving mode

scheduler: Protect package data with rw_spinlock

scheduler: Fix power saving mode and other minor improvements

scheduler: Calculate correct load on SMT processors

scheduler: Improve locking

scheduler: Preallocate temporary heaps for debug commands

scheduler: Try to pack IRQs in power saving mode

scheduler: Move mode specific logic to separate files