RoundRobin.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/ActivityDiagnostics.h"
#include "pedigree/kernel/LockGuard.h"
#include "pedigree/kernel/process/RoundRobin.h"
#include "pedigree/kernel/process/Thread.h"
#include "pedigree/kernel/processor/Processor.h"
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/assert.h"
 
RoundRobin::RoundRobin() : m_Lock(false) {
  for (size_t i = 0; i < MAX_PRIORITIES; ++i) {
    m_pReadyQueueHeads[i] = nullptr;
    m_pReadyQueueTails[i] = nullptr;
#if PEDIGREE_READY_QUEUE_COUNTS
    m_ReadyQueueCounts[i] = 0;
#endif
  }
}
 
RoundRobin::~RoundRobin() {
  for (size_t i = 0; i < MAX_PRIORITIES; ++i) {
    while (m_pReadyQueueHeads[i]) {
      unlink(m_pReadyQueueHeads[i]);
    }
    assert(!m_pReadyQueueTails[i]);
  }
}
 
void RoundRobin::addThread(Thread* pThread) {}
 
void RoundRobin::removeThread(Thread* pThread) {
  LockGuard<Spinlock> guard(m_Lock);
  unlink(pThread);
}
 
void RoundRobin::enqueue(Thread* pThread) {
  assert(pThread);
  assert(isReady(pThread));
  assert(!pThread->m_bReadyQueued);
  assert(!pThread->m_pReadyPrevious);
  assert(!pThread->m_pReadyNext);
  assert(pThread->getPriority() < MAX_PRIORITIES);
 
  const size_t priority = pThread->getPriority();
  pThread->m_pReadyPrevious = m_pReadyQueueTails[priority];
  pThread->m_ReadyQueuePriority = priority;
  pThread->m_bReadyQueued = true;
  if (m_pReadyQueueTails[priority]) {
    m_pReadyQueueTails[priority]->m_pReadyNext = pThread;
  } else {
    m_pReadyQueueHeads[priority] = pThread;
  }
  m_pReadyQueueTails[priority] = pThread;
#if PEDIGREE_READY_QUEUE_COUNTS
  ++m_ReadyQueueCounts[priority];
#endif
}
 
void RoundRobin::unlink(Thread* pThread) {
  if (!pThread || !pThread->m_bReadyQueued) {
    return;
  }
 
  const size_t priority = pThread->m_ReadyQueuePriority;
  assert(priority < MAX_PRIORITIES);
  if (pThread->m_pReadyPrevious) {
    pThread->m_pReadyPrevious->m_pReadyNext = pThread->m_pReadyNext;
  } else {
    assert(m_pReadyQueueHeads[priority] == pThread);
    m_pReadyQueueHeads[priority] = pThread->m_pReadyNext;
  }
  if (pThread->m_pReadyNext) {
    pThread->m_pReadyNext->m_pReadyPrevious = pThread->m_pReadyPrevious;
  } else {
    assert(m_pReadyQueueTails[priority] == pThread);
    m_pReadyQueueTails[priority] = pThread->m_pReadyPrevious;
  }
 
  pThread->m_pReadyPrevious = nullptr;
  pThread->m_pReadyNext = nullptr;
  pThread->m_ReadyQueuePriority = MAX_PRIORITIES;
  pThread->m_bReadyQueued = false;
#if PEDIGREE_READY_QUEUE_COUNTS
  assert(m_ReadyQueueCounts[priority]);
  --m_ReadyQueueCounts[priority];
#endif
}
 
Thread* RoundRobin::getNext(Thread* pCurrentThread) {
  ActivityDiagnostics::ReadyQueueSelectionScope selectionScope;
  LockGuard<Spinlock> guard(m_Lock);
 
  Thread* pThread = 0;
  for (size_t i = 0; i < MAX_PRIORITIES; i++) {
    // Bound the scan so a stale entry whose priority changes cannot be
#if PEDIGREE_READY_QUEUE_COUNTS
    // requeued forever in the same selection pass. The maintained count
    // avoids walking this list once merely to determine that bound.
    size_t candidates = m_ReadyQueueCounts[i];
#else
    // Bound the scan so a stale entry whose priority changes cannot be
    // requeued forever in the same selection pass.
    size_t candidates = 0;
    for (pThread = m_pReadyQueueHeads[i]; pThread; pThread = pThread->m_pReadyNext)
      ++candidates;
#endif
    while (candidates--) {
      pThread = m_pReadyQueueHeads[i];
      assert(pThread);
      ActivityDiagnostics::recordReadyQueueCandidateVisit();
      unlink(pThread);
 
      if (pThread == pCurrentThread || !isReady(pThread)) {
        continue;
      }
 
      if (pThread->getPriority() != i) {
        enqueue(pThread);
        continue;
      }
 
      return pThread;
    }
  }
  ActivityDiagnostics::recordSchedulerNoEligibleSelection();
  return 0;
}
 
bool RoundRobin::hasReady() {
  LockGuard<Spinlock> guard(m_Lock);
  for (size_t i = 0; i < MAX_PRIORITIES; ++i) {
    if (m_pReadyQueueHeads[i]) {
      return true;
    }
  }
  return false;
}
 
void RoundRobin::threadStatusChanged(Thread* pThread) {
  LockGuard<Spinlock> guard(m_Lock);
 
  if (pThread->m_bReadyQueued) {
    if (!RoundRobin::isReady(pThread) || pThread->m_ReadyQueuePriority != pThread->getPriority()) {
      unlink(pThread);
    } else {
      return;
    }
  }
 
  if (RoundRobin::isReady(pThread)) {
    enqueue(pThread);
  }
}
 
bool RoundRobin::isReady(Thread* pThread) {
  return pThread->getStatus() == Thread::Ready &&
         !__atomic_load_n(&pThread->m_ReadyPublicationPending, __ATOMIC_ACQUIRE);
}
 
#if HOSTED && PEDIGREE_HOSTED_SMOKE_TESTS
bool RoundRobin::runHostedIntrusiveQueueRegressions(Thread* pThread) {
  if (!pThread || pThread->m_bReadyQueued || pThread->m_pReadyPrevious || pThread->m_pReadyNext) {
    return false;
  }
 
  const bool interrupts = Processor::getInterrupts();
  Processor::setInterrupts(false);
  const Thread::Status status = pThread->m_Status;
  const size_t priority = pThread->m_Priority;
  bool passed = true;
 
  {
    RoundRobin queue;
    pThread->m_Status = Thread::Ready;
    pThread->m_Priority = 1;
    queue.threadStatusChanged(pThread);
    queue.threadStatusChanged(pThread);
    passed &= pThread->m_bReadyQueued && pThread->m_ReadyQueuePriority == 1 &&
              !pThread->m_pReadyPrevious && !pThread->m_pReadyNext;
 
    pThread->m_Priority = 2;
    queue.threadStatusChanged(pThread);
    passed &= pThread->m_bReadyQueued && pThread->m_ReadyQueuePriority == 2 &&
              !pThread->m_pReadyPrevious && !pThread->m_pReadyNext;
 
    pThread->m_Status = Thread::AwaitingJoin;
    passed &= !queue.getNext(nullptr) && !pThread->m_bReadyQueued;
 
    pThread->m_Status = Thread::Ready;
    queue.threadStatusChanged(pThread);
    passed &= !queue.getNext(pThread) && !pThread->m_bReadyQueued;
 
    pThread->m_Status = Thread::Ready;
    queue.threadStatusChanged(pThread);
    passed &= pThread->m_bReadyQueued;
  }
 
  passed &= !pThread->m_bReadyQueued && !pThread->m_pReadyPrevious && !pThread->m_pReadyNext &&
            pThread->m_ReadyQueuePriority == MAX_PRIORITIES;
  {
    RoundRobin reused;
    pThread->m_Status = Thread::Ready;
    pThread->m_Priority = 0;
    reused.threadStatusChanged(pThread);
    passed &= reused.getNext(nullptr) == pThread && !pThread->m_bReadyQueued;
  }
 
  pThread->m_Status = status;
  pThread->m_Priority = priority;
  Processor::setInterrupts(interrupts);
  return passed;
}
#endif
 
#endif