From 522957f9f302b9521507a365da5871849a03594d Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Fri, 15 Mar 2019 22:50:57 -0400
Subject: Implement a MultiLevelQueue

---
 src/common/CMakeLists.txt      |   1 +
 src/common/bit_util.h          |  19 +++
 src/common/multi_level_queue.h | 329 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 349 insertions(+)
 create mode 100644 src/common/multi_level_queue.h

(limited to 'src/common')

diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index 43ae8a9e7..850ce8006 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -98,6 +98,7 @@ add_library(common STATIC
     microprofile.h
     microprofileui.h
     misc.cpp
+    multi_level_queue.h
     page_table.cpp
     page_table.h
     param_package.cpp
diff --git a/src/common/bit_util.h b/src/common/bit_util.h
index 1eea17ba1..14e53c273 100644
--- a/src/common/bit_util.h
+++ b/src/common/bit_util.h
@@ -58,4 +58,23 @@ inline u64 CountLeadingZeroes64(u64 value) {
     return __builtin_clzll(value);
 }
 #endif
+
+inline u32 CountTrailingZeroes32(u32 value) {
+  u32 count = 0;
+  while (((value >> count) & 0xf) == 0 && count < 32)
+    count += 4;
+  while (((value >> count) & 1) == 0 && count < 32)
+    count++;
+  return count;
+}
+
+inline u64 CountTrailingZeroes64(u64 value) {
+  u64 count = 0;
+  while (((value >> count) & 0xf) == 0 && count < 64)
+    count += 4;
+  while (((value >> count) & 1) == 0 && count < 64)
+    count++;
+  return count;
+}
+
 } // namespace Common
diff --git a/src/common/multi_level_queue.h b/src/common/multi_level_queue.h
new file mode 100644
index 000000000..fc72a8238
--- /dev/null
+++ b/src/common/multi_level_queue.h
@@ -0,0 +1,329 @@
+// Copyright 2019 TuxSH
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <array>
+#include <iterator>
+#include <list>
+
+#include "common/bit_util.h"
+#include "common/common_types.h"
+
+namespace Common {
+
+template <typename T, std::size_t Depth>
+class MultiLevelQueue {
+public:
+    using value_type = T;
+    using reference = value_type&;
+    using const_reference = const value_type&;
+    using pointer = value_type*;
+    using const_pointer = const value_type*;
+
+    using difference_type = typename std::pointer_traits<pointer>::difference_type;
+    using size_type = std::size_t;
+
+    template <bool is_constant>
+    class iterator_impl {
+    public:
+        using iterator_category = std::bidirectional_iterator_tag;
+        using value_type = T;
+        using pointer = std::conditional_t<is_constant, T*, const T*>;
+        using reference = std::conditional_t<is_constant, const T&, T&>;
+        using difference_type = typename std::pointer_traits<pointer>::difference_type;
+
+        friend bool operator==(const iterator_impl& lhs, const iterator_impl& rhs) {
+            return (lhs.IsEnd() && rhs.IsEnd()) || lhs.it == rhs.it;
+        }
+
+        friend bool operator!=(const iterator_impl& lhs, const iterator_impl& rhs) {
+            return !operator==(lhs, rhs);
+        }
+
+        reference operator*() const {
+            return *it;
+        }
+
+        pointer operator->() const {
+            return it.operator->();
+        }
+
+        iterator_impl& operator++() {
+            if (IsEnd()) {
+                return *this;
+            }
+
+            ++it;
+
+            if (it == GetEndItForPrio()) {
+                u64 prios = mlq.used_priorities;
+                prios &= ~((1ULL << (current_priority + 1)) - 1);
+                if (prios == 0) {
+                    current_priority = mlq.depth();
+                } else {
+                    current_priority = CountTrailingZeroes64(prios);
+                    it = GetBeginItForPrio();
+                }
+            }
+            return *this;
+        }
+
+        iterator_impl& operator--() {
+            if (IsEnd()) {
+                if (mlq.used_priorities != 0) {
+                    current_priority = 63 - CountLeadingZeroes64(mlq.used_priorities);
+                    it = GetEndItForPrio();
+                    --it;
+                }
+            } else if (it == GetBeginItForPrio()) {
+                u64 prios = mlq.used_priorities;
+                prios &= (1ULL << current_priority) - 1;
+                if (prios != 0) {
+                    current_priority = CountTrailingZeroes64(prios);
+                    it = GetEndItForPrio();
+                    --it;
+                }
+            } else {
+                --it;
+            }
+            return *this;
+        }
+
+        iterator_impl operator++(int) {
+            const iterator_impl v{*this};
+            ++(*this);
+            return v;
+        }
+
+        iterator_impl operator--(int) {
+            const iterator_impl v{*this};
+            --(*this);
+            return v;
+        }
+
+        // allow implicit const->non-const
+        iterator_impl(const iterator_impl<false>& other)
+            : mlq(other.mlq), it(other.it), current_priority(other.current_priority) {}
+
+        iterator_impl& operator=(const iterator_impl<false>& other) {
+            mlq = other.mlq;
+            it = other.it;
+            current_priority = other.current_priority;
+            return *this;
+        }
+
+        friend class iterator_impl<true>;
+        iterator_impl() = default;
+
+    private:
+        friend class MultiLevelQueue;
+        using container_ref =
+            std::conditional_t<is_constant, const MultiLevelQueue&, MultiLevelQueue&>;
+        using list_iterator = std::conditional_t<is_constant, typename std::list<T>::const_iterator,
+                                                 typename std::list<T>::iterator>;
+
+        explicit iterator_impl(container_ref mlq, list_iterator it, u32 current_priority)
+            : mlq(mlq), it(it), current_priority(current_priority) {}
+        explicit iterator_impl(container_ref mlq, u32 current_priority)
+            : mlq(mlq), it(), current_priority(current_priority) {}
+
+        bool IsEnd() const {
+            return current_priority == mlq.depth();
+        }
+
+        list_iterator GetBeginItForPrio() const {
+            return mlq.levels[current_priority].begin();
+        }
+
+        list_iterator GetEndItForPrio() const {
+            return mlq.levels[current_priority].end();
+        }
+
+        container_ref mlq;
+        list_iterator it;
+        u32 current_priority;
+    };
+
+    using iterator = iterator_impl<false>;
+    using const_iterator = iterator_impl<true>;
+
+    void add(T& element, u32 priority, bool send_back = true) {
+        if (send_back)
+            levels[priority].push_back(element);
+        else
+            levels[priority].push_front(element);
+        used_priorities |= 1ULL << priority;
+    }
+
+    void remove(const T& element, u32 priority) {
+        levels[priority].erase(ListIterateTo(levels[priority], element));
+        if (levels[priority].empty()) {
+            used_priorities &= ~(1ULL << priority);
+        }
+    }
+
+    void adjust(const T& element, u32 old_priority, u32 new_priority, bool adjust_front = false) {
+        const auto new_next =
+            adjust_front ? levels[new_priority].cbegin() : levels[new_priority].cend();
+        ListSplice(levels[new_priority], new_next, levels[old_priority],
+                   ListIterateTo(levels[old_priority], element));
+
+        used_priorities |= 1ULL << new_priority;
+
+        if (levels[old_priority].empty()) {
+            used_priorities &= ~(1ULL << old_priority);
+        }
+    }
+    void adjust(const_iterator it, u32 old_priority, u32 new_priority, bool adjust_front = false) {
+        adjust(*it, old_priority, new_priority, adjust_front);
+    }
+
+    void transfer_to_front(const T& element, u32 priority, MultiLevelQueue& other) {
+        ListSplice(other.levels[priority], other.levels[priority].begin(), levels[priority],
+                   ListIterateTo(levels[priority], element));
+
+        other.used_priorities |= 1ULL << priority;
+
+        if (levels[priority].empty()) {
+            used_priorities &= ~(1ULL << priority);
+        }
+    }
+
+    void transfer_to_front(const_iterator it, u32 priority, MultiLevelQueue& other) {
+        transfer_to_front(*it, priority, other);
+    }
+
+    void transfer_to_back(const T& element, u32 priority, MultiLevelQueue& other) {
+        ListSplice(other.levels[priority], other.levels[priority].end(), levels[priority],
+                   ListIterateTo(levels[priority], element));
+
+        other.used_priorities |= 1ULL << priority;
+
+        if (levels[priority].empty()) {
+            used_priorities &= ~(1ULL << priority);
+        }
+    }
+
+    void transfer_to_back(const_iterator it, u32 priority, MultiLevelQueue& other) {
+        transfer_to_back(*it, priority, other);
+    }
+
+    void yield(u32 priority, std::size_t n = 1) {
+        ListShiftForward(levels[priority], n);
+    }
+
+    std::size_t depth() const {
+        return Depth;
+    }
+
+    std::size_t size(u32 priority) const {
+        return levels[priority].size();
+    }
+
+    std::size_t size() const {
+        u64 priorities = used_priorities;
+        std::size_t size = 0;
+        while (priorities != 0) {
+            const u64 current_priority = CountTrailingZeroes64(priorities);
+            size += levels[current_priority].size();
+            priorities &= ~(1ULL << current_priority);
+        }
+        return size;
+    }
+
+    bool empty() const {
+        return used_priorities == 0;
+    }
+
+    bool empty(u32 priority) const {
+        return (used_priorities & (1ULL << priority)) == 0;
+    }
+
+    u32 highest_priority_set(u32 max_priority = 0) const {
+        const u64 priorities =
+            max_priority == 0 ? used_priorities : (used_priorities & ~((1ULL << max_priority) - 1));
+        return priorities == 0 ? Depth : static_cast<u32>(CountTrailingZeroes64(priorities));
+    }
+
+    u32 lowest_priority_set(u32 min_priority = Depth - 1) const {
+        const u64 priorities = min_priority >= Depth - 1
+                                   ? used_priorities
+                                   : (used_priorities & ((1ULL << (min_priority + 1)) - 1));
+        return priorities == 0 ? Depth : 63 - CountLeadingZeroes64(priorities);
+    }
+
+    const_iterator cbegin(u32 max_prio = 0) const {
+        const u32 priority = highest_priority_set(max_prio);
+        return priority == Depth ? cend()
+                                 : const_iterator{*this, levels[priority].cbegin(), priority};
+    }
+    const_iterator begin(u32 max_prio = 0) const {
+        return cbegin(max_prio);
+    }
+    iterator begin(u32 max_prio = 0) {
+        const u32 priority = highest_priority_set(max_prio);
+        return priority == Depth ? end() : iterator{*this, levels[priority].begin(), priority};
+    }
+
+    const_iterator cend(u32 min_prio = Depth - 1) const {
+        return min_prio == Depth - 1 ? const_iterator{*this, Depth} : cbegin(min_prio + 1);
+    }
+    const_iterator end(u32 min_prio = Depth - 1) const {
+        return cend(min_prio);
+    }
+    iterator end(u32 min_prio = Depth - 1) {
+        return min_prio == Depth - 1 ? iterator{*this, Depth} : begin(min_prio + 1);
+    }
+
+    T& front(u32 max_priority = 0) {
+        const u32 priority = highest_priority_set(max_priority);
+        return levels[priority == Depth ? 0 : priority].front();
+    }
+    const T& front(u32 max_priority = 0) const {
+        const u32 priority = highest_priority_set(max_priority);
+        return levels[priority == Depth ? 0 : priority].front();
+    }
+
+    T back(u32 min_priority = Depth - 1) {
+        const u32 priority = lowest_priority_set(min_priority); // intended
+        return levels[priority == Depth ? 63 : priority].back();
+    }
+    const T& back(u32 min_priority = Depth - 1) const {
+        const u32 priority = lowest_priority_set(min_priority); // intended
+        return levels[priority == Depth ? 63 : priority].back();
+    }
+
+private:
+    using const_list_iterator = typename std::list<T>::const_iterator;
+
+    static void ListShiftForward(std::list<T>& list, const std::size_t shift = 1) {
+        // NOTE: May want to consider making this an assertion or something
+        if (shift >= list.size()) {
+            return;
+        }
+
+        const auto begin_range = list.begin();
+        const auto end_range = std::next(begin_range, shift);
+        list.splice(list.end(), list, begin_range, end_range);
+    }
+
+    static void ListSplice(std::list<T>& in_list, const_list_iterator position,
+                           std::list<T>& out_list, const_list_iterator element) {
+        in_list.splice(position, out_list, element);
+    }
+
+    static const_list_iterator ListIterateTo(const std::list<T>& list, const T& element) {
+        auto it = list.cbegin();
+        while (it != list.cend() && *it != element) {
+            ++it;
+        }
+        return it;
+    }
+
+    std::array<std::list<T>, Depth> levels;
+    u64 used_priorities = 0;
+};
+
+} // namespace Common
-- 
cgit v1.2.3


From 3bc815a5dc18a646334ba933c74ce7ce44099625 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Fri, 15 Mar 2019 23:18:11 -0400
Subject: Implement intrinsics CountTrailingZeroes and test it.

---
 src/common/bit_util.h | 45 +++++++++++++++++++++++++++++++++------------
 1 file changed, 33 insertions(+), 12 deletions(-)

(limited to 'src/common')

diff --git a/src/common/bit_util.h b/src/common/bit_util.h
index 14e53c273..70e728a5e 100644
--- a/src/common/bit_util.h
+++ b/src/common/bit_util.h
@@ -59,22 +59,43 @@ inline u64 CountLeadingZeroes64(u64 value) {
 }
 #endif
 
+
+#ifdef _MSC_VER
 inline u32 CountTrailingZeroes32(u32 value) {
-  u32 count = 0;
-  while (((value >> count) & 0xf) == 0 && count < 32)
-    count += 4;
-  while (((value >> count) & 1) == 0 && count < 32)
-    count++;
-  return count;
+    unsigned long trailing_zero = 0;
+
+    if (_BitScanForward(&trailing_zero, value) != 0) {
+        return trailing_zero;
+    }
+
+    return 32;
 }
 
 inline u64 CountTrailingZeroes64(u64 value) {
-  u64 count = 0;
-  while (((value >> count) & 0xf) == 0 && count < 64)
-    count += 4;
-  while (((value >> count) & 1) == 0 && count < 64)
-    count++;
-  return count;
+    unsigned long trailing_zero = 0;
+
+    if (_BitScanForward64(&trailing_zero, value) != 0) {
+        return trailing_zero;
+    }
+
+    return 64;
 }
+#else
+inline u32 CountTrailingZeroes32(u32 value) {
+    if (value == 0) {
+        return 32;
+    }
+
+    return __builtin_ctz(value);
+}
+
+inline u64 CountTrailingZeroes64(u64 value) {
+    if (value == 0) {
+        return 64;
+    }
+
+    return __builtin_ctzll(value);
+}
+#endif
 
 } // namespace Common
-- 
cgit v1.2.3


From dde0814837866e5c27cd5c97be0461bdca481bc2 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Sat, 16 Mar 2019 00:30:15 -0400
Subject: Use MultiLevelQueue instead of old ThreadQueueList

---
 src/common/multi_level_queue.h | 22 ++++++++++------------
 1 file changed, 10 insertions(+), 12 deletions(-)

(limited to 'src/common')

diff --git a/src/common/multi_level_queue.h b/src/common/multi_level_queue.h
index fc72a8238..d56ab6531 100644
--- a/src/common/multi_level_queue.h
+++ b/src/common/multi_level_queue.h
@@ -107,6 +107,9 @@ public:
         iterator_impl(const iterator_impl<false>& other)
             : mlq(other.mlq), it(other.it), current_priority(other.current_priority) {}
 
+        iterator_impl(const iterator_impl<true>& other)
+            : mlq(other.mlq), it(other.it), current_priority(other.current_priority) {}
+
         iterator_impl& operator=(const iterator_impl<false>& other) {
             mlq = other.mlq;
             it = other.it;
@@ -149,7 +152,7 @@ public:
     using iterator = iterator_impl<false>;
     using const_iterator = iterator_impl<true>;
 
-    void add(T& element, u32 priority, bool send_back = true) {
+    void add(const T& element, u32 priority, bool send_back = true) {
         if (send_back)
             levels[priority].push_back(element);
         else
@@ -158,23 +161,18 @@ public:
     }
 
     void remove(const T& element, u32 priority) {
-        levels[priority].erase(ListIterateTo(levels[priority], element));
+        auto it = ListIterateTo(levels[priority], element);
+        if (it == levels[priority].end())
+            return;
+        levels[priority].erase(it);
         if (levels[priority].empty()) {
             used_priorities &= ~(1ULL << priority);
         }
     }
 
     void adjust(const T& element, u32 old_priority, u32 new_priority, bool adjust_front = false) {
-        const auto new_next =
-            adjust_front ? levels[new_priority].cbegin() : levels[new_priority].cend();
-        ListSplice(levels[new_priority], new_next, levels[old_priority],
-                   ListIterateTo(levels[old_priority], element));
-
-        used_priorities |= 1ULL << new_priority;
-
-        if (levels[old_priority].empty()) {
-            used_priorities &= ~(1ULL << old_priority);
-        }
+        remove(element, old_priority);
+        add(element, new_priority, !adjust_front);
     }
     void adjust(const_iterator it, u32 old_priority, u32 new_priority, bool adjust_front = false) {
         adjust(*it, old_priority, new_priority, adjust_front);
-- 
cgit v1.2.3


From f35e09fe0dee84e3373ea1e2daac8d120621fe61 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Tue, 19 Mar 2019 20:28:03 -0400
Subject: Fixes to multilevelqueue's iterator.

---
 src/common/multi_level_queue.h | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

(limited to 'src/common')

diff --git a/src/common/multi_level_queue.h b/src/common/multi_level_queue.h
index d56ab6531..68b35ffaa 100644
--- a/src/common/multi_level_queue.h
+++ b/src/common/multi_level_queue.h
@@ -35,7 +35,11 @@ public:
         using difference_type = typename std::pointer_traits<pointer>::difference_type;
 
         friend bool operator==(const iterator_impl& lhs, const iterator_impl& rhs) {
-            return (lhs.IsEnd() && rhs.IsEnd()) || lhs.it == rhs.it;
+            if (lhs.IsEnd() && rhs.IsEnd())
+                return true;
+            if (lhs.current_priority == rhs.current_priority)
+                return lhs.it == rhs.it;
+            return false;
         }
 
         friend bool operator!=(const iterator_impl& lhs, const iterator_impl& rhs) {
-- 
cgit v1.2.3


From db42bcb306323d6221e7f893d39558c3db579bf3 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Tue, 19 Mar 2019 22:20:15 -0400
Subject: Fixes and corrections on formatting.

---
 src/common/bit_util.h          |  1 -
 src/common/multi_level_queue.h | 14 ++++++++++----
 2 files changed, 10 insertions(+), 5 deletions(-)

(limited to 'src/common')

diff --git a/src/common/bit_util.h b/src/common/bit_util.h
index 70e728a5e..a4f9ed4aa 100644
--- a/src/common/bit_util.h
+++ b/src/common/bit_util.h
@@ -59,7 +59,6 @@ inline u64 CountLeadingZeroes64(u64 value) {
 }
 #endif
 
-
 #ifdef _MSC_VER
 inline u32 CountTrailingZeroes32(u32 value) {
     unsigned long trailing_zero = 0;
diff --git a/src/common/multi_level_queue.h b/src/common/multi_level_queue.h
index 68b35ffaa..2b61b91e0 100644
--- a/src/common/multi_level_queue.h
+++ b/src/common/multi_level_queue.h
@@ -7,12 +7,21 @@
 #include <array>
 #include <iterator>
 #include <list>
+#include <utility>
 
 #include "common/bit_util.h"
 #include "common/common_types.h"
 
 namespace Common {
 
+/**
+ * A MultiLevelQueue is a type of priority queue which has the following characteristics:
+ * - iteratable through each of its elements.
+ * - back can be obtained.
+ * - O(1) add, lookup (both front and back)
+ * - discrete priorities and a max of 64 priorities (limited domain)
+ * This type of priority queue is normaly used for managing threads within an scheduler
+ */
 template <typename T, std::size_t Depth>
 class MultiLevelQueue {
 public:
@@ -37,9 +46,7 @@ public:
         friend bool operator==(const iterator_impl& lhs, const iterator_impl& rhs) {
             if (lhs.IsEnd() && rhs.IsEnd())
                 return true;
-            if (lhs.current_priority == rhs.current_priority)
-                return lhs.it == rhs.it;
-            return false;
+            return std::tie(lhs.current_priority, lhs.it) == std::tie(rhs.current_priority, rhs.it);
         }
 
         friend bool operator!=(const iterator_impl& lhs, const iterator_impl& rhs) {
@@ -301,7 +308,6 @@ private:
     using const_list_iterator = typename std::list<T>::const_iterator;
 
     static void ListShiftForward(std::list<T>& list, const std::size_t shift = 1) {
-        // NOTE: May want to consider making this an assertion or something
         if (shift >= list.size()) {
             return;
         }
-- 
cgit v1.2.3