scheduler: Only unassign a thread's core if it is not pinned

If a pinned thread is being run while disabling a CPU core, the thread
is properly requeued to that core, but with fCore set to NULL, causing
the scheduler to panic the next time that thread is rescheduled.

Change-Id: I9cf18c5a470517124b2573347cf3eb6fd26ab7b6
Reviewed-on: https://review.haiku-os.org/c/haiku/+/6917
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

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.)

kernel/scheduler: Reset the invoke_scheduler flag on reschedule.

There is nowhere else that unsets it (or makes sense to unset it),
we have to do it here, or otherwise it will never be unset.
This has actually been broken since the new scheduler was merged
many years ago; the old scheduler (which had more complex logic here)
unset this flag correctly.

This oversight mostly did not cause obvious problems: while the scheduler
would be invoked unnecessarily on every single interrupt, that would
be a minor performance downturn at most. But there is one other effect:
since we can only reenable interrupts after invoking the scheduler,
"post_interrupt_callback"s of threads were not invoked most of the time.

The main user of "post_interrupt_callback"s is the profiler, which uses
them to trigger buffer flushes back to userland. Since they were not
invoked, the buffer would quickly fill up and then no more results
would be recorded.

Thus, this fixes #16345.

kernel/scheduler: fix compile error when TRACE is enabled

Change-Id: I95da18c9faa343fb3a44c627c1227a778701ebbe
Reviewed-on: https://review.haiku-os.org/c/haiku/+/4653
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>
Reviewed-by: Adrien Destugues <pulkomandy@gmail.com>

kernel/scheduler: enable cpu load tracking after boot

when the cpufreq module is loaded, we let the scheduler update its policy.
Improve assert report
CoreEntry::GetLoad() could return more than kMaxLoad.

Change-Id: I127f9b3e8062b5996872aae30b4021b9904fa179
Reviewed-on: https://review.haiku-os.org/c/haiku/+/3216
Reviewed-by: Jérôme Duval <jerome.duval@gmail.com>

scheduler: Fix setting priorities following the penalty cancellation changes.

Before hrev46809, the "thread->priority = priority" line was below this
check, and so all was well. But that commit moved the line to its present
location, which means ever since then, the following code which updates
CPU entries, scheduler listeners, etc. has never been run.

On my VMware instance (which is probably pretty affected by the host system
and thus not the greatest performance test), "time jam -j2 HaikuDepot" decreased
from 46.0s real to 43.3s real, 52.3s user to 48.1s user, 12.1s sys to 12.2s sys.
So this seems to make some sort of impact.

Spotted by Fishpond in #10454 and confirmed by korli, but somehow neither of
them followed up on that in the 4.5 years since...

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: Update load of idle cores

In order to keep the scheduler tickless core load is computed and updated
only during various scheduler events (i.e. thread enqueue, reschedule, etc).
The problem it creates is that if a core becomes idle its load may remain
outdated for an extended period of time thus resulting in suboptimal thread
migration decisions.

The solution to this problem is to add a timer each time an idle thread is
scheudled which, after kLoadMeasureInterval, would fire and force load
update.

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: 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.

Revert "scheduler: SCHEDULER_EXIT_FUNCTION() is not needed"

This reverts commit 667617ad043a4587d8d366d5192d9ad291cfa37a.

Scheduler profiler uses CPU local data to store function information, hence
arch_thread_context_switch() usually is not a problem. However, when
we switch to a new thread we end up scheduler_new_thread_entry() instead
of scheduler_reschedule() what may corrupt data collected by the profiler.

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

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: 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: Remove unnecessary check against disabled CPU

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: SCHEDULER_EXIT_FUNCTION() is not needed

kernel: Remove cpu_info::load

This field forces kernel to track each CPU load all the time. It is not
a problem with the current scheduler on a multicore systems, but on
single core machnies or with any other future scheduler this field may
become just an unnecessary burden. It isn't difficult for an application
to compute CPU load by itself when it needs it.

scheduler: Disable load tracking when not needed

scheduler: Thread can not stay on CPU if it has been disabled

scheduler: Protect per CPU run queue with its own lock

kernel: Return CPU load in cpu_info

scheduler: Fix unused variable warnings

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: Use precomputed time slice lengths

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: Allow calling UpdatePriority() for disabled CPU

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: Fix unassigning threads from core being disabled

kernel: Propagate scheduler modes to cpu{freq, idle} modules

kernel: Make get_cpu_topology() return a pointer to const

The client code is not supposed to change the topology info.
It would be also nice if cpu_topology_node::children was an array of
pointers to const but that would require several const_casts in the
topology tree generation code so it's probably not worth it.

scheduler: Code refactoring

scheduler: Do not send reschedule ICI when not needed

kernel: Remove Thread::next_state

scheduler: Add missing check for real time threads

scheduler: Allow mode to specify time slice length

scheduler, kernel/util: Fix style issues

scheduler: Update CPU disabling code to match recent changes

scheduler: Introduce upper bound on latency

scheduler: Remove some unnecessary checks against idle threads

scheduler: Migrate threads less often in power saving mode

kernel: Merge two occurences of thread resume code

scheduler: Protect package data with rw_spinlock

scheduler: Update estimate_max_scheduling_latency()

scheduler: Move simple inline functions to scheduler_common.h

scheduler: Improve debug commands

scheduler: Simplify thread priority penalties

scheduler_set_thread_priority: Fix null dereference

scheduler: Send reschedule ICI after enqueueing the thread

scheduler: Clean scheduler_common.h

scheduler_common.h is now meant for types, variables and functions used
by both core scheduler code and implementations of scheduler modes.
Functions like switch_thread() and update_thread_times() do not belong
there anymore.

scheduler: Fix power saving mode and other minor improvements

scheudler: Do not include irq load in thread load

kernel: Restore logical processor disabling

scheduler: Return time stolen by irq and ipi handlers

scheduler: Calculate correct load on SMT processors

scheduler: Improve locking

scheduler: Preallocate temporary heaps for debug commands

kernel, libroot: Make scheduler modes interface public

scheduler: Reduce scheduler mode lock cache bouncing

scheduler: Improve power saving mode

* Remove possibility to temporarily disable small task packing.
* When small task packing target gets overloaded continue packing
threads on another core, but avoid migrating the already packed
ones.

Scheduler still tends to needlessly migrate threads to another cores
when under heavier load, but it is now much better than before.

scheduler: Try to pack IRQs in power saving mode

scheduler: Move mode specific logic to separate files

scheduler: Rebalance IRQs on overloaded cores

kernel: Track load produced by interrupt handlers

scheduler: Remove sSchedulerInternalLock

* pin idle threads to their specific CPUs
* allow scheduler to implement SMP_MSG_RESCHEDULE handler
* scheduler_set_thread_priority() reworked
* at reschedule: enqueue old thread after dequeueing the new one

scheduler: Fix gcc2 build

scheduler: Remove sCorePriorityHeap

sCorePriorityHeap was meant to be a temporary solution anyway. Thread
migration and assignment is now entirely based on core load.

scheduler: Minor cleanup

scheduler: Add {CPU,Core,Package}Entry constructors

scheduler: Atomically access time and load measurements

scheduler: Reduce false sharing of per-CPU and per-core data

kernel: Remove gSchedulerLock

* Thread::scheduler_lock protects thread state, priority, etc.
* sThreadCreationLock protects thread creation and removal and list of
threads in team.
* Team::signal_lock and Team::time_lock protect list of threads in team
as well.
* Scheduler uses its own internal locking.

scheduler: Performance mode is actually low latency mode

kernel: Remove B_TIMER_ACQUIRE_SCHEDULER_LOCK flag

The flag main purpose is to avoid race conditions between event handler
and cancel_timer(). However, cancel_timer() is safe even without
using gSchedulerLock.

If the event is scheduled to happen on other CPU than the CPU that
invokes cancel_timer() then cancel_timer() either disables the event
before its handler starts executing or waits until the event handler
is done.

If the event is scheduled on the same CPU that calls cancel_timer()
then, since cancel_timer() disables interrupts, the event is either
executed before cancel_timer() or when the timer interrupt handler
starts running the event is already disabled.

scheduler: Manage CPU performance

scheduler: Use load information to migrate threads

scheduler: Keep track of the load each thread produces

scheduler: Use core load to distribute threads

scheduler: Keep track of core and logical CPU load

scheduler: Decide whether to cancel thread penalty

scheduler: Increase penalty of waiting threads

The fact that thread is waiting doesn't mean that it is nice to the others.
If the thread, indeed, waits for a longer time its penalty will be cancelled
anyway, however if the thread waits for a very short time do not count that
as being nice since lower priority threads didn't have much chance to run.

scheduler: Be more demanding when cancelling penalties

scheduler: Update scheduler_set_operation_mode()

scheduler: Remove support for running different schedulers

Simple scheduler behaves exactly the same as affine scheduler with a
single core. Obviously, affine scheduler is more complicated thus
introduces greater overhead but quite a lot of multicore logic has been
disabled on single core systems in the previous commit.

kernel: Decide whether to use simple or affine scheduler

Simple scheduler is used when we do not have to worry about cache affinity
(i.e. single core with or without SMT, multicore with all cache levels
shared).

When we replace gSchedulerLock with more fine grained locking affine
scheduler should also be chosen when logical CPU count is high (regardless
of cache).

kernel: Remove scheduler_simple_smp

kernel: Add support for SMP systems to simple scheduler

In SMP systems simple scheduler will be used only when all logical
processors share all levels of cache and the number of CPUs is low.
In such systems we do not have to care about cache affinity and
the contention on the lock protecting shared run queue is low. Single
run queue makes load balancing very simple.

kernel: Allow scheduler initialization to fail

More 64-bit compilation/safety fixes.

Merged signals-merge branch into trunk with the following changes:
* Reorganized the kernel locking related to threads and teams.
* We now discriminate correctly between process and thread signals. Signal
handlers have been moved to teams. Fixes #5679.
* Implemented real-time signal support, including signal queuing, SA_SIGINFO
support, sigqueue(), sigwaitinfo(), sigtimedwait(), waitid(), and the addition
of the real-time signal range. Closes #1935 and #2695.
* Gave SIGBUS a separate signal number. Fixes #6704.
* Implemented <time.h> clock and timer support, and fixed/completed alarm() and
[set]itimer(). Closes #5682.
* Implemented support for thread cancellation. Closes #5686.
* Moved send_signal() from <signal.h> to <OS.h>. Fixes #7554.
* Lots over smaller more or less related changes.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@42116 a95241bf-73f2-0310-859d-f6bbb57e9c96

Merged the signals branch into trunk, with these changes:
* The team and thread kernel structures have been renamed to Team and Thread
respectively and moved into the new BKernel namespace.
* Several (kernel add-on) sources have been converted from C to C++ since
private kernel headers are included that are no longer C compatible.

Changes after merging:
* Fixed gcc 2 build (warnings mainly in the scary firewire bus manager).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@40196 a95241bf-73f2-0310-859d-f6bbb57e9c96

scheduler_reschedule_no_op(): panic() when the calling thread is not
continuing to run. This must not happen since the thread is the boot CPU's
idle thread performing the early kernel initialization (before the scheduler
is started).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36560 a95241bf-73f2-0310-859d-f6bbb57e9c96

Make scheduler_reschedule() an no-op until we're ready to start the
scheduler. This avoids the need to use the send_signal_etc() work-around for
resume_thread() during the early kernel initialization. Might fix #5851.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36530 a95241bf-73f2-0310-859d-f6bbb57e9c96

bonefish+axeld:
* Implemented a tiny bit more sophisticated version of
estimate_max_scheduling_latency() that uses a syscall that lets the scheduler
decide.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36170 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed build with scheduler tracing enabled.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34714 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Reintroduced the SMP_MSG_RESCHEDULE_IF_IDLE ICI message. This time
implemented by means of an additional member in cpu_ent.
* Removed thread::keep_scheduled and the related functions. The feature
wasn't used yet and wouldn't have worked as implemented anyway.
* Resurrected an older, SMP aware version of our simple scheduler and made it
the default instead of the affine scheduler. The latter is in no state to
be used yet. It causes enormous latencies (I've seen up to 0.1s) even when
six or seven CPUs were idle at the same time, totally killing parallelism.
That's also the reason why a -j8 build was slower than a -j2. This is no
longer the case. On my machine the -j2 build takes about 10% less time now
and the -j8 build saves another 20%. The latter is not particularly
impressive (compared with Linux), but that seems to be due to lock
contention.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34615 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Strip down scheduler_simple. Anything related to multiple CPU handling has
been removed. That includes CPU disabling and thread pinning, as that becomes
pointless with only one CPU.
* Return a proper reschedule hint on enqueing a thread, based on the priority
of the current thread vs. the enqueued one.
* Enable dynamic scheduler selection. With one CPU the simple scheduler will
be used, otherwise affine is selected.
* Removed the scheduler type define as we now always auto-select it.
* Some cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@32573 a95241bf-73f2-0310-859d-f6bbb57e9c96

anevilyak+mmlr:
* scheduler_enqueue_in_runqueue() now allows the scheduler to return a hint as to whether a reschedule is desirable or not. This is used in a few other places in order to relegate scheduling decisions entirely to the scheduler rather than the priority hacks previously used. There are probably other places in the kernel that could now make use of that information to more intelligently call reschedule() though.
* Switch over the default scheduler to scheduler_affine().



git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@32554 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Scheduler/wait object listener:
- Moved scheduler listening interface to <listeners.h> and added more
convenient to use templatized notification functions.
- Added a listener mechanism for the wait objects (semaphores, condition
variables, mutex, rw_lock).
* system profiler:
- Hopefully fixed locking issues related to notifying the profiler thread
for good. We still had an inconsistent locking order, since the scheduler
notification callbacks are invoked with the thread lock held and have to
acquire the object lock then, while the other callbacks acquired the object
lock first and as a side effect of ConditionVariable::NotifyOne() acquired
the thread lock. Now we make sure the object lock is the innermost lock.
- Track the number of dropped events due to a full buffer.
_user_system_profiler_next_buffer() returns this count now.
- When scheduling profiling events are requested also listen to wait objects
and generate the respective profiling events. We send those events lazily
and cache the infos to avoid resending an event for the same wait object.
- When starting profiling we do now generate "thread scheduled" events for
the already running threads.
- _user_system_profiler_start(): Check whether the parameters pointer is a
userland address at all.
- The system_profiler_team_added event does now also contain the team's name.
* Added a sem_get_name_unsafe() returning a semaphore's name. It is "unsafe",
since the caller has to ensure that the semaphore exists and continues to
exist as long as the returned name is used.
* Adjusted the "profile" and "scheduling_recorder" according to the system
profiling changes. The latter prints the number of dropped events, now.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@30345 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added a listener mechanism to the scheduler (ATM only for scheduler_simple).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@30242 a95241bf-73f2-0310-859d-f6bbb57e9c96

Introduce an experimental new scheduler intended to work fundamentally the same as our existing one, but with various optimizations to better handle the SMP case:
1) We now maintain a runqueue per CPU, rather than a single global shared queue. Idle threads are segregated into their own queue for simplicity.
2) Enqueueing threads is now somewhat more intelligent - if the thread is pinned, it is always enqueued onto that core. Otherwise we enqueue it on whichever CPU it previously ran, unless it either hasn't run before, or that core has been disabled via ProcessController. If so, we try to enqueue it on whichever core has been the most idle recently.
3) The above allow various simplifications to thread scheduling. Pinned threads and/or disabled cores are now no longer special cases that need to be dealt with. If a CPU has no threads ready, it looks for another one to steal a thread from, though that part still needs some tuning along with enqueueing for load balancing purposes.

The chief aim here is better load balancing and support for soft affinity. However, at the moment the overall behavior still exhibits some regressions compared to the old scheduler, so it's disabled by default. If you wish to experiment/debug with it, instructions for enabling it can be found in scheduler.cpp. Much thanks to Ingo, Axel and everyone who's helped with either code review/advice or testing so far.



git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@29643 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Replaced scheduler_remove_from_run_queue() by
scheduler_set_thread_priority(). Setting the thread priority was the
only situation in which it was used.
* Renamed scheduler.cpp to scheduler_simple.cpp.
* The scheduler functions are no longer called directly. Instead there's
an operation vector now, which is initialized at kernel init time.
This allows for picking the most suitable scheduler for the machine
(e.g. a non-SMP scheduler on a non-SMP machine).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28262 a95241bf-73f2-0310-859d-f6bbb57e9c96

Moved scheduler.cpp into new subdirectory scheduler/. Moved the
scheduler tracing and scheduler analysis code into separate source
files.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28253 a95241bf-73f2-0310-859d-f6bbb57e9c96

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: Update load of idle cores

In order to keep the scheduler tickless core load is computed and updated
only during various scheduler events (i.e. thread enqueue, reschedule, etc).
The problem it creates is that if a core becomes idle its load may remain
outdated for an extended period of time thus resulting in suboptimal thread
migration decisions.

The solution to this problem is to add a timer each time an idle thread is
scheudled which, after kLoadMeasureInterval, would fire and force load
update.

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: 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.

Revert "scheduler: SCHEDULER_EXIT_FUNCTION() is not needed"

This reverts commit 667617ad043a4587d8d366d5192d9ad291cfa37a.

Scheduler profiler uses CPU local data to store function information, hence
arch_thread_context_switch() usually is not a problem. However, when
we switch to a new thread we end up scheduler_new_thread_entry() instead
of scheduler_reschedule() what may corrupt data collected by the profiler.

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

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: 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: Remove unnecessary check against disabled CPU

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: SCHEDULER_EXIT_FUNCTION() is not needed

kernel: Remove cpu_info::load

This field forces kernel to track each CPU load all the time. It is not
a problem with the current scheduler on a multicore systems, but on
single core machnies or with any other future scheduler this field may
become just an unnecessary burden. It isn't difficult for an application
to compute CPU load by itself when it needs it.

scheduler: Disable load tracking when not needed

scheduler: Thread can not stay on CPU if it has been disabled

scheduler: Protect per CPU run queue with its own lock

kernel: Return CPU load in cpu_info

scheduler: Fix unused variable warnings

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: Use precomputed time slice lengths

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: Allow calling UpdatePriority() for disabled CPU

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: Fix unassigning threads from core being disabled

kernel: Propagate scheduler modes to cpu{freq, idle} modules

kernel: Make get_cpu_topology() return a pointer to const

The client code is not supposed to change the topology info.
It would be also nice if cpu_topology_node::children was an array of
pointers to const but that would require several const_casts in the
topology tree generation code so it's probably not worth it.

scheduler: Code refactoring

scheduler: Do not send reschedule ICI when not needed

kernel: Remove Thread::next_state

scheduler: Add missing check for real time threads

scheduler: Allow mode to specify time slice length

scheduler, kernel/util: Fix style issues

scheduler: Update CPU disabling code to match recent changes

scheduler: Introduce upper bound on latency

scheduler: Remove some unnecessary checks against idle threads

scheduler: Migrate threads less often in power saving mode

kernel: Merge two occurences of thread resume code

scheduler: Protect package data with rw_spinlock

scheduler: Update estimate_max_scheduling_latency()

scheduler: Move simple inline functions to scheduler_common.h

scheduler: Improve debug commands

scheduler: Simplify thread priority penalties

scheduler_set_thread_priority: Fix null dereference

scheduler: Send reschedule ICI after enqueueing the thread

scheduler: Clean scheduler_common.h

scheduler_common.h is now meant for types, variables and functions used
by both core scheduler code and implementations of scheduler modes.
Functions like switch_thread() and update_thread_times() do not belong
there anymore.

scheduler: Fix power saving mode and other minor improvements

scheudler: Do not include irq load in thread load

kernel: Restore logical processor disabling

scheduler: Return time stolen by irq and ipi handlers

scheduler: Calculate correct load on SMT processors

scheduler: Improve locking

scheduler: Preallocate temporary heaps for debug commands

kernel, libroot: Make scheduler modes interface public

scheduler: Reduce scheduler mode lock cache bouncing

scheduler: Improve power saving mode

* Remove possibility to temporarily disable small task packing.
* When small task packing target gets overloaded continue packing
threads on another core, but avoid migrating the already packed
ones.

Scheduler still tends to needlessly migrate threads to another cores
when under heavier load, but it is now much better than before.

scheduler: Try to pack IRQs in power saving mode

scheduler: Move mode specific logic to separate files

scheduler: Rebalance IRQs on overloaded cores

kernel: Track load produced by interrupt handlers

scheduler: Remove sSchedulerInternalLock

* pin idle threads to their specific CPUs
* allow scheduler to implement SMP_MSG_RESCHEDULE handler
* scheduler_set_thread_priority() reworked
* at reschedule: enqueue old thread after dequeueing the new one

scheduler: Fix gcc2 build

scheduler: Remove sCorePriorityHeap

sCorePriorityHeap was meant to be a temporary solution anyway. Thread
migration and assignment is now entirely based on core load.

scheduler: Minor cleanup

scheduler: Add {CPU,Core,Package}Entry constructors

scheduler: Atomically access time and load measurements

scheduler: Reduce false sharing of per-CPU and per-core data

kernel: Remove gSchedulerLock

* Thread::scheduler_lock protects thread state, priority, etc.
* sThreadCreationLock protects thread creation and removal and list of
threads in team.
* Team::signal_lock and Team::time_lock protect list of threads in team
as well.
* Scheduler uses its own internal locking.

scheduler: Performance mode is actually low latency mode

kernel: Remove B_TIMER_ACQUIRE_SCHEDULER_LOCK flag

The flag main purpose is to avoid race conditions between event handler
and cancel_timer(). However, cancel_timer() is safe even without
using gSchedulerLock.

If the event is scheduled to happen on other CPU than the CPU that
invokes cancel_timer() then cancel_timer() either disables the event
before its handler starts executing or waits until the event handler
is done.

If the event is scheduled on the same CPU that calls cancel_timer()
then, since cancel_timer() disables interrupts, the event is either
executed before cancel_timer() or when the timer interrupt handler
starts running the event is already disabled.

scheduler: Manage CPU performance

scheduler: Use load information to migrate threads

scheduler: Keep track of the load each thread produces

scheduler: Use core load to distribute threads

scheduler: Keep track of core and logical CPU load

scheduler: Decide whether to cancel thread penalty

scheduler: Increase penalty of waiting threads

The fact that thread is waiting doesn't mean that it is nice to the others.
If the thread, indeed, waits for a longer time its penalty will be cancelled
anyway, however if the thread waits for a very short time do not count that
as being nice since lower priority threads didn't have much chance to run.

scheduler: Be more demanding when cancelling penalties

scheduler: Update scheduler_set_operation_mode()

scheduler: Remove support for running different schedulers

Simple scheduler behaves exactly the same as affine scheduler with a
single core. Obviously, affine scheduler is more complicated thus
introduces greater overhead but quite a lot of multicore logic has been
disabled on single core systems in the previous commit.

kernel: Decide whether to use simple or affine scheduler

Simple scheduler is used when we do not have to worry about cache affinity
(i.e. single core with or without SMT, multicore with all cache levels
shared).

When we replace gSchedulerLock with more fine grained locking affine
scheduler should also be chosen when logical CPU count is high (regardless
of cache).

kernel: Remove scheduler_simple_smp

kernel: Add support for SMP systems to simple scheduler

In SMP systems simple scheduler will be used only when all logical
processors share all levels of cache and the number of CPUs is low.
In such systems we do not have to care about cache affinity and
the contention on the lock protecting shared run queue is low. Single
run queue makes load balancing very simple.

kernel: Allow scheduler initialization to fail

More 64-bit compilation/safety fixes.

Merged signals-merge branch into trunk with the following changes:
* Reorganized the kernel locking related to threads and teams.
* We now discriminate correctly between process and thread signals. Signal
handlers have been moved to teams. Fixes #5679.
* Implemented real-time signal support, including signal queuing, SA_SIGINFO
support, sigqueue(), sigwaitinfo(), sigtimedwait(), waitid(), and the addition
of the real-time signal range. Closes #1935 and #2695.
* Gave SIGBUS a separate signal number. Fixes #6704.
* Implemented <time.h> clock and timer support, and fixed/completed alarm() and
[set]itimer(). Closes #5682.
* Implemented support for thread cancellation. Closes #5686.
* Moved send_signal() from <signal.h> to <OS.h>. Fixes #7554.
* Lots over smaller more or less related changes.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@42116 a95241bf-73f2-0310-859d-f6bbb57e9c96

Merged the signals branch into trunk, with these changes:
* The team and thread kernel structures have been renamed to Team and Thread
respectively and moved into the new BKernel namespace.
* Several (kernel add-on) sources have been converted from C to C++ since
private kernel headers are included that are no longer C compatible.

Changes after merging:
* Fixed gcc 2 build (warnings mainly in the scary firewire bus manager).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@40196 a95241bf-73f2-0310-859d-f6bbb57e9c96

scheduler_reschedule_no_op(): panic() when the calling thread is not
continuing to run. This must not happen since the thread is the boot CPU's
idle thread performing the early kernel initialization (before the scheduler
is started).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36560 a95241bf-73f2-0310-859d-f6bbb57e9c96

Make scheduler_reschedule() an no-op until we're ready to start the
scheduler. This avoids the need to use the send_signal_etc() work-around for
resume_thread() during the early kernel initialization. Might fix #5851.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36530 a95241bf-73f2-0310-859d-f6bbb57e9c96

bonefish+axeld:
* Implemented a tiny bit more sophisticated version of
estimate_max_scheduling_latency() that uses a syscall that lets the scheduler
decide.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36170 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed build with scheduler tracing enabled.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34714 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Reintroduced the SMP_MSG_RESCHEDULE_IF_IDLE ICI message. This time
implemented by means of an additional member in cpu_ent.
* Removed thread::keep_scheduled and the related functions. The feature
wasn't used yet and wouldn't have worked as implemented anyway.
* Resurrected an older, SMP aware version of our simple scheduler and made it
the default instead of the affine scheduler. The latter is in no state to
be used yet. It causes enormous latencies (I've seen up to 0.1s) even when
six or seven CPUs were idle at the same time, totally killing parallelism.
That's also the reason why a -j8 build was slower than a -j2. This is no
longer the case. On my machine the -j2 build takes about 10% less time now
and the -j8 build saves another 20%. The latter is not particularly
impressive (compared with Linux), but that seems to be due to lock
contention.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34615 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Strip down scheduler_simple. Anything related to multiple CPU handling has
been removed. That includes CPU disabling and thread pinning, as that becomes
pointless with only one CPU.
* Return a proper reschedule hint on enqueing a thread, based on the priority
of the current thread vs. the enqueued one.
* Enable dynamic scheduler selection. With one CPU the simple scheduler will
be used, otherwise affine is selected.
* Removed the scheduler type define as we now always auto-select it.
* Some cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@32573 a95241bf-73f2-0310-859d-f6bbb57e9c96

anevilyak+mmlr:
* scheduler_enqueue_in_runqueue() now allows the scheduler to return a hint as to whether a reschedule is desirable or not. This is used in a few other places in order to relegate scheduling decisions entirely to the scheduler rather than the priority hacks previously used. There are probably other places in the kernel that could now make use of that information to more intelligently call reschedule() though.
* Switch over the default scheduler to scheduler_affine().



git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@32554 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Scheduler/wait object listener:
- Moved scheduler listening interface to <listeners.h> and added more
convenient to use templatized notification functions.
- Added a listener mechanism for the wait objects (semaphores, condition
variables, mutex, rw_lock).
* system profiler:
- Hopefully fixed locking issues related to notifying the profiler thread
for good. We still had an inconsistent locking order, since the scheduler
notification callbacks are invoked with the thread lock held and have to
acquire the object lock then, while the other callbacks acquired the object
lock first and as a side effect of ConditionVariable::NotifyOne() acquired
the thread lock. Now we make sure the object lock is the innermost lock.
- Track the number of dropped events due to a full buffer.
_user_system_profiler_next_buffer() returns this count now.
- When scheduling profiling events are requested also listen to wait objects
and generate the respective profiling events. We send those events lazily
and cache the infos to avoid resending an event for the same wait object.
- When starting profiling we do now generate "thread scheduled" events for
the already running threads.
- _user_system_profiler_start(): Check whether the parameters pointer is a
userland address at all.
- The system_profiler_team_added event does now also contain the team's name.
* Added a sem_get_name_unsafe() returning a semaphore's name. It is "unsafe",
since the caller has to ensure that the semaphore exists and continues to
exist as long as the returned name is used.
* Adjusted the "profile" and "scheduling_recorder" according to the system
profiling changes. The latter prints the number of dropped events, now.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@30345 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added a listener mechanism to the scheduler (ATM only for scheduler_simple).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@30242 a95241bf-73f2-0310-859d-f6bbb57e9c96

Introduce an experimental new scheduler intended to work fundamentally the same as our existing one, but with various optimizations to better handle the SMP case:
1) We now maintain a runqueue per CPU, rather than a single global shared queue. Idle threads are segregated into their own queue for simplicity.
2) Enqueueing threads is now somewhat more intelligent - if the thread is pinned, it is always enqueued onto that core. Otherwise we enqueue it on whichever CPU it previously ran, unless it either hasn't run before, or that core has been disabled via ProcessController. If so, we try to enqueue it on whichever core has been the most idle recently.
3) The above allow various simplifications to thread scheduling. Pinned threads and/or disabled cores are now no longer special cases that need to be dealt with. If a CPU has no threads ready, it looks for another one to steal a thread from, though that part still needs some tuning along with enqueueing for load balancing purposes.

The chief aim here is better load balancing and support for soft affinity. However, at the moment the overall behavior still exhibits some regressions compared to the old scheduler, so it's disabled by default. If you wish to experiment/debug with it, instructions for enabling it can be found in scheduler.cpp. Much thanks to Ingo, Axel and everyone who's helped with either code review/advice or testing so far.



git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@29643 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Replaced scheduler_remove_from_run_queue() by
scheduler_set_thread_priority(). Setting the thread priority was the
only situation in which it was used.
* Renamed scheduler.cpp to scheduler_simple.cpp.
* The scheduler functions are no longer called directly. Instead there's
an operation vector now, which is initialized at kernel init time.
This allows for picking the most suitable scheduler for the machine
(e.g. a non-SMP scheduler on a non-SMP machine).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28262 a95241bf-73f2-0310-859d-f6bbb57e9c96

Moved scheduler.cpp into new subdirectory scheduler/. Moved the
scheduler tracing and scheduler analysis code into separate source
files.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28253 a95241bf-73f2-0310-859d-f6bbb57e9c96