Scheduler.cc

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#include <config.h>
 
#if THREADS
 
#include "pedigree/kernel/LockGuard.h"
#include "pedigree/kernel/Log.h"
#include "pedigree/kernel/Metrics.h"
#include "pedigree/kernel/process/PerProcessorScheduler.h"
#include "pedigree/kernel/process/Process.h"
#include "pedigree/kernel/process/ProcessorThreadAllocator.h"
#include "pedigree/kernel/process/RoundRobinCoreAllocator.h"
#include "pedigree/kernel/process/Scheduler.h"
#include "pedigree/kernel/processor/Processor.h"
#include "pedigree/kernel/processor/ProcessorInformation.h"
#include "pedigree/kernel/utilities/Iterator.h"
#include "pedigree/kernel/utilities/Vector.h"
#include "pedigree/kernel/utilities/assert.h"
#include "pedigree/kernel/utilities/utility.h"
 
Scheduler Scheduler::m_Instance;
 
#if HOSTED && PEDIGREE_HOSTED_SMOKE_TESTS
namespace {
Scheduler::GenericThreadStatusHook g_GenericThreadStatusHook = nullptr;
}
#endif
 
// Scheduler can be used at times where it is not yet safe to do the useful
// "safer" Spinlock deadlock detection.
#define SCHEDULER_HAS_SAFE_SPINLOCKS true
 
// Do we allow recursing in the Scheduler lock? Note that the lock surrounds
// memory operations (editing a List<T>), so if e.g. VirtualAddressSpace depends
// on Scheduler, you need to recurse.
#define SCHEDULER_HAS_RECURSIVE_SPINLOCKS true
 
Scheduler::ProcessLease::ProcessLease() : m_pProcess(nullptr), m_TerminationDeferral(false) {}
 
Scheduler::ProcessLease::ProcessLease(Process* process)
    : m_pProcess(process), m_TerminationDeferral(process != nullptr) {}
 
Scheduler::ProcessLease::ProcessLease(ProcessLease&& other) noexcept
    : m_pProcess(other.m_pProcess),
      m_TerminationDeferral(pedigree_std::move(other.m_TerminationDeferral)) {
  other.m_pProcess = nullptr;
}
 
Scheduler::ProcessLease::~ProcessLease() {
  reset();
}
 
Scheduler::ProcessLease& Scheduler::ProcessLease::operator=(ProcessLease&& other) noexcept {
  if (this != &other) {
    if (other.m_pProcess) {
      m_TerminationDeferral = pedigree_std::move(other.m_TerminationDeferral);
 
      Process* previous = m_pProcess;
      m_pProcess = other.m_pProcess;
      other.m_pProcess = nullptr;
      if (previous) {
        Scheduler::instance().releaseProcessLease(previous);
      }
    } else {
      reset();
    }
  }
  return *this;
}
 
void Scheduler::ProcessLease::reset() {
  Process* process = m_pProcess;
  m_pProcess = nullptr;
  if (process) {
    Scheduler::instance().releaseProcessLease(process);
  }
  m_TerminationDeferral = TerminationDeferral(false);
}
 
Scheduler::Scheduler()
    : m_ActivityLock(),
      m_LoadAverage(),
      m_UserNanoseconds(0),
      m_KernelNanoseconds(0),
      m_IdleNanoseconds(0),
      m_Processes(),
      m_NextPid(0),
      m_PTMap(),
      m_TPMap(),
      m_pKernelProcess(0),
      m_pBspScheduler(0),
      m_SchedulerLock(false),
      m_ProcessRemovalWaiters() {}
 
bool Scheduler::initialise(Process* pKernelProcess) {
  if (Processor::getCount() > CpuAffinityMask::MaximumCpus)
    FATAL("Processor topology exceeds the affinity mask capacity.");
  RoundRobinCoreAllocator* pRoundRobin = new RoundRobinCoreAllocator();
  ProcessorThreadAllocator::instance().setAlgorithm(pRoundRobin);
 
  m_pKernelProcess = pKernelProcess;
 
  List<PerProcessorScheduler*> procList;
 
  m_pBspScheduler = &Processor::information().getScheduler();
  procList.pushBack(m_pBspScheduler);
 
  size_t i = 0;
  for (Vector<ProcessorInformation*>::Iterator it = Processor::m_ProcessorInformation.begin();
       it != Processor::m_ProcessorInformation.end(); it++, i += 2) {
    auto thisScheduler = &((*it)->getScheduler());
    if (thisScheduler != m_pBspScheduler) {
      procList.pushBack(thisScheduler);
    }
  }
 
  pRoundRobin->initialise(procList);
 
  return true;
}
 
void Scheduler::addThread(Thread* pThread, PerProcessorScheduler& PPSched) {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  m_TPMap.insert(pThread, &PPSched);
  pThread->setScheduler(&PPSched);
  if (!pThread->m_Placement.migratable) {
    pThread->m_Placement.allowed = CpuAffinityMask();
    const size_t cpu = PPSched.logicalCpu();
    pThread->m_Placement.allowed.set(cpu == ~size_t(0) ? Processor::index() : cpu);
  }
  m_SchedulerLock.release();
}
 
void Scheduler::removeThread(Thread* pThread) {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  PerProcessorScheduler* pPpSched = m_TPMap.lookup(pThread);
  if (pPpSched) {
    pPpSched->removeThread(pThread);
    m_TPMap.remove(pThread);
  }
  m_SchedulerLock.release();
}
 
bool Scheduler::threadInSchedule(Thread* pThread) {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  PerProcessorScheduler* pPpSched = m_TPMap.lookup(pThread);
  m_SchedulerLock.release();
  return pPpSched != 0;
}
 
bool Scheduler::hasActiveSyscallLocked(Service_t service) const {
  for (auto it = m_TPMap.begin(); it != m_TPMap.end(); ++it) {
    if (__atomic_load_n(&it.key()->m_ActiveSyscalls[service], __ATOMIC_SEQ_CST)) {
      return true;
    }
  }
  return false;
}
 
size_t Scheduler::reserveProcessId() {
  const size_t id = (m_NextPid += 1) - 1;
  // Linux robust owner words reserve the upper two bits. IDs are never
  // recycled, so exhaustion cannot silently alias an older owner.
  assert(id < 0x3FFFFFFF);
  return id;
}
 
void Scheduler::releaseProcessLease(Process* process) {
  process->endExternalLease();
}
 
void Scheduler::drainDeferredTimeAccounting() {
  // Reserve outside m_SchedulerLock. A worker generation is snapshotted
  // before this call, so a Process added after the count can only publish a
  // later generation and will be covered by the next pass.
  Vector<Process*> processes(getNumProcesses());
 
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  for (List<Process*>::Iterator it = m_Processes.begin();
       it != m_Processes.end() && processes.count() < processes.size(); ++it) {
    Process* process = *it;
    if (process->beginExternalLease()) {
      processes.pushBack(process);
    }
  }
  m_SchedulerLock.release();
 
  for (Vector<Process*>::Iterator it = processes.begin(); it != processes.end(); ++it) {
    Process* process = *it;
    process->drainDeferredTimeAccounting();
    process->endExternalLease();
  }
}
 
void Scheduler::addProcess(Process* pProcess) {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  m_Processes.pushBack(pProcess);
  m_SchedulerLock.release();
}
 
void Scheduler::removeProcess(Process* pProcess) {
  bool removed = false;
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  pProcess->closeExternalLeaseAdmission();
  for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); it++) {
    if (*it == pProcess) {
      m_Processes.erase(it);
      removed = true;
      break;
    }
  }
  m_SchedulerLock.release();
  if (removed) {
    m_ProcessRemovalWaiters.wakeAll(WaitQueue::WakeReason::Signalled, WaitQueue::Channel(pProcess));
  }
}
 
void Scheduler::yield() {
  Metrics::increment(Metrics::Counter::Yield);
  Processor::information().getScheduler().schedule();
}
 
CpuAffinityMask Scheduler::onlineAffinity() {
  CpuAffinityMask mask;
  const size_t count = Processor::getCount();
  assert(count <= CpuAffinityMask::MaximumCpus);
  for (size_t cpu = 0; cpu < count; ++cpu)
    mask.set(cpu);
  return mask;
}
 
size_t Scheduler::affinityBytes() {
  return ((Processor::getCount() + CpuAffinityMask::WordBits - 1) / CpuAffinityMask::WordBits) *
         sizeof(unsigned long);
}
 
PerProcessorScheduler* Scheduler::schedulerForCpu(size_t cpu) {
  ProcessorInformation* information = Processor::informationAt(cpu);
  return information ? &information->getScheduler() : nullptr;
}
 
void Scheduler::rebindThread(Thread* thread, PerProcessorScheduler& scheduler) {
  LockGuard<Spinlock> guard(m_SchedulerLock);
  assert(m_TPMap.lookup(thread));
  m_TPMap.insert(thread, &scheduler);
  thread->setScheduler(&scheduler);
  thread->setCpuId(scheduler.m_PhysicalCpu);
}
 
size_t Scheduler::getNumProcesses() {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  size_t result = m_Processes.count();
  m_SchedulerLock.release();
  return result;
}
 
bool Scheduler::acquireProcess(ProcessLease& lease, size_t n) {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  if (n >= m_Processes.count()) {
    m_SchedulerLock.release();
    lease.reset();
    return false;
  }
 
  size_t i = 0;
  Process* pResult = 0;
  for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); it++) {
    if (i == n) {
      pResult = *it;
      break;
    }
    i++;
  }
 
  if (pResult && !pResult->beginExternalLease()) {
    pResult = nullptr;
  }
  m_SchedulerLock.release();
  lease = ProcessLease(pResult);
  return pResult != nullptr;
}
 
bool Scheduler::acquireFirstProcessOfType(ProcessLease& lease, Process::ProcessType type) {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  Process* pResult = nullptr;
  for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); ++it) {
    Process* candidate = *it;
    if (candidate->getType() == type && candidate->beginExternalLease()) {
      pResult = candidate;
      break;
    }
  }
  m_SchedulerLock.release();
 
  lease = ProcessLease(pResult);
  return pResult != nullptr;
}
 
bool Scheduler::acquireProcess(ProcessLease& lease, Process* expected) {
  if (!expected) {
    lease.reset();
    return false;
  }
 
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  Process* pResult = nullptr;
  for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); ++it) {
    if (*it == expected) {
      pResult = *it;
      break;
    }
  }
 
  if (pResult && !pResult->beginExternalLease()) {
    pResult = nullptr;
  }
  m_SchedulerLock.release();
  lease = ProcessLease(pResult);
  return pResult != nullptr;
}
 
bool Scheduler::acquireProcessById(ProcessLease& lease, size_t id) {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  Process* pResult = nullptr;
  for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); ++it) {
    Process* candidate = *it;
    if (candidate->getId() == id) {
      pResult = candidate;
      break;
    }
  }
 
  if (pResult && !pResult->beginExternalLease()) {
    pResult = nullptr;
  }
  m_SchedulerLock.release();
  lease = ProcessLease(pResult);
  return pResult != nullptr;
}
 
bool Scheduler::acquireProcessByUserspaceId(ProcessLease& lease, size_t id,
                                            const UserspacePidNamespace* space) {
  auto* current = Processor::information().getCurrentThread();
  auto owner = current && current->getParent()->pidNamespace()
                   ? current->getParent()->pidNamespace()
                   : Process::rootPidNamespace();
  if (!space) {
    space = owner.get();
  }
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  Process* pResult = nullptr;
  for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); ++it) {
    Process* candidate = *it;
    if (id && candidate->getUserspaceId(space) == id) {
      pResult = candidate;
      break;
    }
  }
 
  if (pResult && !pResult->beginExternalLease()) {
    pResult = nullptr;
  }
  m_SchedulerLock.release();
  lease = ProcessLease(pResult);
  return pResult != nullptr;
}
 
bool Scheduler::acquireNextProcess(ProcessLease& lease, size_t afterId) {
  lease.reset();
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  Process* result = nullptr;
  while (true) {
    for (Process* candidate : m_Processes) {
      if (candidate->getId() > afterId && (!result || candidate->getId() < result->getId())) {
        result = candidate;
      }
    }
    if (!result || result->beginExternalLease()) {
      break;
    }
    afterId = result->getId();
    result = nullptr;
  }
  m_SchedulerLock.release();
  lease = ProcessLease(result);
  return result != nullptr;
}
 
bool Scheduler::acquireThreadByUserspaceId(Process::ThreadLease& lease, size_t id,
                                           const UserspacePidNamespace* space) {
  lease.reset();
  auto* current = Processor::information().getCurrentThread();
  auto owner = current && current->getParent()->pidNamespace()
                   ? current->getParent()->pidNamespace()
                   : Process::rootPidNamespace();
  if (!space) {
    space = owner.get();
  }
  size_t after = 0;
  ProcessLease process;
  while (acquireNextProcess(process, after)) {
    after = process->getId();
    if (process->getUserspaceId(space) && process->acquireThreadByUserspaceId(lease, id, space)) {
      return true;
    }
  }
  return false;
}
 
bool Scheduler::acquireThreadByTaskId(Process::ThreadLease& lease, size_t id) {
  lease.reset();
  size_t afterId = 0;
  while (afterId < id) {
    Process* candidate = nullptr;
    m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
    for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); ++it) {
      Process* process = *it;
      const size_t processId = process->getId();
      if (processId > afterId && processId <= id &&
          (!candidate || processId < candidate->getId())) {
        candidate = process;
      }
    }
    if (candidate) {
      afterId = candidate->getId();
      if (!candidate->beginExternalLease()) {
        candidate = nullptr;
      }
    } else {
      afterId = id;
    }
    m_SchedulerLock.release();
 
    // A numeric cursor cannot skip a surviving process when a preceding
    // process disappears. Its lease bridges the two independent locks.
    ProcessLease process(candidate);
    if (process && process->acquireThreadByTaskId(lease, id)) {
      return true;
    }
  }
  return false;
}
 
void Scheduler::waitUntilProcessRemoved(Process* expected) {
  TerminationDeferral terminationDeferral;
  while (true) {
    auto guard = m_ProcessRemovalWaiters.acquire();
    bool present = false;
    m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
    for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); ++it) {
      if (*it == expected) {
        present = true;
        break;
      }
    }
    m_SchedulerLock.release();
    if (!present) {
      return;
    }
 
    const WaitQueue::WakeReason reason = guard.waitForCompletion(
        WaitQueue::Channel(expected), Thread::ProcessWait, reinterpret_cast<uintptr_t>(expected));
    (void)reason;
  }
}
 
Process* Scheduler::getChildProcess(Process* pParent, size_t n) {
  m_SchedulerLock.acquire(SCHEDULER_HAS_RECURSIVE_SPINLOCKS, SCHEDULER_HAS_SAFE_SPINLOCKS);
  size_t childIndex = 0;
  Process* pResult = 0;
  for (List<Process*>::Iterator it = m_Processes.begin(); it != m_Processes.end(); ++it) {
    Process* pProcess = *it;
    if (pProcess && pProcess->getParent() == pParent) {
      if (childIndex == n) {
        pResult = pProcess;
        break;
      }
      ++childIndex;
    }
  }
  m_SchedulerLock.release();
  return pResult;
}
 
void Scheduler::threadStatusChanged(Thread* pThread) {
#if HOSTED && PEDIGREE_HOSTED_SMOKE_TESTS
  GenericThreadStatusHook hook = __atomic_load_n(&g_GenericThreadStatusHook, __ATOMIC_ACQUIRE);
  if (hook) {
    hook(pThread);
  }
#endif
  PerProcessorScheduler* pSched = pThread->getScheduler();
  assert(pSched);
 
  pSched->threadStatusChanged(pThread);
}
 
#if HOSTED && PEDIGREE_HOSTED_SMOKE_TESTS
void Scheduler::setGenericThreadStatusHook(GenericThreadStatusHook hook) {
  __atomic_store_n(&g_GenericThreadStatusHook, hook, __ATOMIC_RELEASE);
}
#endif
 
#endif