[Minios-devel] [UNIKRAFT PATCH 17/23] lib/ukschedpreempt: Use priority queue for ready threads

[Costin Lupu <costin.lupu@xxxxxxxxx>]

When using preemptive scheduling, each thread is given a priority. Because of
that, we use priority queues for ready threads, which will be further scheduled
in the order of their priority. Just like in the case of cooperative
scheduling, the current thread is removed from the queue before running.

Signed-off-by: Costin Lupu <costin.lupu@xxxxxxxxx>
---
 lib/ukschedpreempt/Makefile.uk        |   1 +
 lib/ukschedpreempt/include/uk/prioq.h |  89 +++++++++++++++++++++
 lib/ukschedpreempt/prioq.c            | 108 ++++++++++++++++++++++++++
 lib/ukschedpreempt/schedpreempt.c     |  44 ++++++++++-
 4 files changed, 240 insertions(+), 2 deletions(-)
 create mode 100644 lib/ukschedpreempt/include/uk/prioq.h
 create mode 100644 lib/ukschedpreempt/prioq.c

diff --git a/lib/ukschedpreempt/Makefile.uk b/lib/ukschedpreempt/Makefile.uk
index 544e5490..031ed87f 100644
--- a/lib/ukschedpreempt/Makefile.uk
+++ b/lib/ukschedpreempt/Makefile.uk
@@ -4,3 +4,4 @@ CINCLUDES-$(CONFIG_LIBUKSCHEDPREEMPT)     += 
-I$(LIBUKSCHEDPREEMPT_BASE)/include
 CXXINCLUDES-$(CONFIG_LIBUKSCHEDPREEMPT)   += 
-I$(LIBUKSCHEDPREEMPT_BASE)/include
 
 LIBUKSCHEDPREEMPT_SRCS-y += $(LIBUKSCHEDPREEMPT_BASE)/schedpreempt.c
+LIBUKSCHEDPREEMPT_SRCS-y += $(LIBUKSCHEDPREEMPT_BASE)/prioq.c
diff --git a/lib/ukschedpreempt/include/uk/prioq.h 
b/lib/ukschedpreempt/include/uk/prioq.h
new file mode 100644
index 00000000..592c0121
--- /dev/null
+++ b/lib/ukschedpreempt/include/uk/prioq.h
@@ -0,0 +1,89 @@
+/* SPDX-License-Identifier: BSD-3-Clause */
+/*
+ * Authors: Costin Lupu <costin.lupu@xxxxxxxxx>
+ *
+ * Copyright (c) 2019, University Politehnica of Bucharest. All rights 
reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the copyright holder nor the names of its
+ *    contributors may be used to endorse or promote products derived from
+ *    this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THIS HEADER MAY NOT BE EXTRACTED OR MODIFIED IN ANY WAY.
+ */
+
+#ifndef __UK_SCHEDPREEMPT_PRIOQ_H__
+#define __UK_SCHEDPREEMPT_PRIOQ_H__
+
+#include <uk/thread.h>
+#include <uk/thread_attr.h>
+#include <uk/list.h>
+#include <uk/bitmap.h>
+
+#define PRIO_ASSERT(prio) \
+       UK_ASSERT(prio >= UK_THREAD_ATTR_PRIO_MIN && \
+               prio <= UK_THREAD_ATTR_PRIO_MAX)
+
+struct prioq {
+       /* The lists of threads */
+       struct uk_thread_list thread_list[UK_THREAD_ATTR_PRIO_MAX + 1];
+
+#define PRIOQ_L2_BM_LONGS \
+       UK_BITS_TO_LONGS(UK_THREAD_ATTR_PRIO_MAX + 1)
+#define PRIOQ_L1_BM_LONGS \
+       UK_BITS_TO_LONGS(PRIOQ_L2_BM_LONGS)
+
+       /* Bitmap cache for non-empty l2_bm elements */
+       unsigned long l1_bm[PRIOQ_L1_BM_LONGS];
+       /* Bitmap for non-empty thread lists */
+       unsigned long l2_bm[PRIOQ_L2_BM_LONGS];
+};
+
+void prioq_init(struct prioq *q);
+void prioq_enqueue(struct prioq *q, struct uk_thread *thread);
+void prioq_dequeue(struct prioq *q, struct uk_thread *thread);
+prio_t prioq_highest_prio(struct prioq *q);
+
+#define prioq_first_for_prio(q, prio) \
+       UK_TAILQ_FIRST(&(q)->thread_list[(prio)])
+
+static inline
+int prioq_empty_for_prio(struct prioq *q, prio_t prio)
+{
+       PRIO_ASSERT(prio);
+       return (prioq_first_for_prio(q, prio) == NULL);
+};
+
+static inline
+struct uk_thread *prioq_pop_for_prio(struct prioq *q, prio_t prio)
+{
+       struct uk_thread *thread;
+
+       thread = prioq_first_for_prio(q, prio);
+       UK_ASSERT(thread != NULL);
+       prioq_dequeue(q, thread);
+
+       return thread;
+}
+
+#endif /*__UK_SCHEDPREEMPT_PRIOQ_H__*/
diff --git a/lib/ukschedpreempt/prioq.c b/lib/ukschedpreempt/prioq.c
new file mode 100644
index 00000000..d8fd1a80
--- /dev/null
+++ b/lib/ukschedpreempt/prioq.c
@@ -0,0 +1,108 @@
+/* SPDX-License-Identifier: BSD-3-Clause */
+/*
+ * Authors: Costin Lupu <costin.lupu@xxxxxxxxx>
+ *
+ * Copyright (c) 2019, University Politehnica of Bucharest. All rights 
reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the copyright holder nor the names of its
+ *     contributors may be used to endorse or promote products derived from
+ *     this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THIS HEADER MAY NOT BE EXTRACTED OR MODIFIED IN ANY WAY.
+ */
+
+#include <string.h>
+#include <uk/arch/atomic.h>
+#include <uk/prioq.h>
+#include <uk/assert.h>
+
+
+void prioq_init(struct prioq *q)
+{
+       UK_ASSERT(q != NULL);
+       memset(q, 0, sizeof(struct prioq));
+       for (int i = 0; i < UK_THREAD_ATTR_PRIO_MAX + 1; i++)
+               UK_TAILQ_INIT(&q->thread_list[i]);
+}
+
+void prioq_enqueue(struct prioq *q, struct uk_thread *thread)
+{
+       prio_t prio;
+       unsigned long l1_index, l2_index;
+
+       UK_ASSERT(q != NULL);
+       UK_ASSERT(thread != NULL);
+
+       /* TODO get thread prio */
+       prio = 0;
+
+       /* add to list */
+       UK_TAILQ_INSERT_TAIL(&q->thread_list[prio], thread, thread_list);
+       /* update bitmaps */
+       l1_index = UK_BIT_WORD((unsigned long) prio);
+       l2_index = ((unsigned long) prio) % UK_BITS_PER_LONG;
+       uk_set_bit(l1_index, &q->l1_bm[0]);
+       uk_set_bit(l2_index, &q->l2_bm[l1_index]);
+}
+
+void prioq_dequeue(struct prioq *q, struct uk_thread *thread)
+{
+       prio_t prio;
+       unsigned long l1_index, l2_index;
+
+       UK_ASSERT(q != NULL);
+       UK_ASSERT(thread != NULL);
+
+       /* TODO get thread prio */
+       prio = 0;
+
+       /* remove from list */
+       UK_TAILQ_REMOVE(&q->thread_list[prio], thread, thread_list);
+       if (UK_TAILQ_EMPTY(&q->thread_list[prio])) {
+               /* updating bitmaps */
+               l1_index = UK_BIT_WORD((unsigned long) prio);
+               l2_index = ((unsigned long) prio) % UK_BITS_PER_LONG;
+               uk_clear_bit(l2_index, &q->l2_bm[l1_index]);
+               if (q->l2_bm[l1_index] == 0)
+                       uk_clear_bit(l1_index, &q->l1_bm[0]);
+       }
+}
+
+prio_t prioq_highest_prio(struct prioq *q)
+{
+       prio_t prio;
+       unsigned long l1_index, l2_index;
+
+       UK_ASSERT(q != NULL);
+
+       l1_index = uk_find_last_bit(&q->l1_bm[0],
+                       UK_BITS_PER_LONG * PRIOQ_L1_BM_LONGS);
+       if (l1_index == UK_BITS_PER_LONG * PRIOQ_L1_BM_LONGS)
+               return UK_THREAD_ATTR_PRIO_INVALID;
+
+       l2_index = uk_find_last_bit(&q->l2_bm[l1_index], UK_BITS_PER_LONG);
+       prio = l1_index * UK_BITS_PER_LONG + l2_index;
+
+       return prio;
+}
diff --git a/lib/ukschedpreempt/schedpreempt.c 
b/lib/ukschedpreempt/schedpreempt.c
index faaefd2e..ec8d50e4 100644
--- a/lib/ukschedpreempt/schedpreempt.c
+++ b/lib/ukschedpreempt/schedpreempt.c
@@ -32,11 +32,50 @@
  * THIS HEADER MAY NOT BE EXTRACTED OR MODIFIED IN ANY WAY.
  */
 
+#include <uk/plat/lcpu.h>
 #include <uk/schedpreempt.h>
+#include <uk/prioq.h>
+
 
 struct schedpreempt_private {
+       struct prioq ready_queue;
 };
 
+static
+int schedpreempt_thread_add(struct uk_sched *s, struct uk_thread *t,
+               const struct uk_thread_attr *attr)
+{
+       unsigned long flags;
+       struct schedpreempt_private *prv = s->prv;
+
+       set_runnable(t);
+
+       flags = ukplat_lcpu_save_irqf();
+       prioq_enqueue(&prv->ready_queue, t);
+       ukplat_lcpu_restore_irqf(flags);
+
+       return 0;
+}
+
+static
+void schedpreempt_thread_remove(struct uk_sched *s, struct uk_thread *t)
+{
+       unsigned long flags;
+       struct schedpreempt_private *prv = s->prv;
+
+       flags = ukplat_lcpu_save_irqf();
+
+       if (t != uk_thread_current())
+               prioq_dequeue(&prv->ready_queue, t);
+
+       clear_runnable(t);
+
+       uk_thread_exit(t);
+       UK_TAILQ_INSERT_HEAD(&s->exited_threads, t, thread_list);
+
+       ukplat_lcpu_restore_irqf(flags);
+}
+
 struct uk_sched *uk_schedpreempt_init(struct uk_alloc *a)
 {
        struct uk_sched *sched = NULL;
@@ -51,11 +90,12 @@ struct uk_sched *uk_schedpreempt_init(struct uk_alloc *a)
        ukplat_ctx_callbacks_init(&sched->plat_ctx_cbs, ukplat_ctx_hw);
 
        prv = sched->prv;
+       prioq_init(&prv->ready_queue);
 
        uk_sched_init(sched,
                        NULL,
-                       NULL,
-                       NULL,
+                       schedpreempt_thread_add,
+                       schedpreempt_thread_remove,
                        NULL,
                        NULL,
                        NULL,
-- 
2.20.1


_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel