[PATCH 4/9] trinity: Add schduler module

[Jiho Chu]

This patch includes NPU scheduler interface.

Tasks can be pushed to the NPU in order by the scheduler. The default
schduling algorithm is provided using Priority policy.
The scheduler waits request from the user. When the requests are
invoked, it submits each request to the NPU by the priority, and waits
until complete interrupt arrives. The priority is calculated with
remained time to requested timeout.

Thus the scheduler algorithm may be added more in the later, it
provides an interface which can support various schedulers.

Signed-off-by: Jiho Chu <jiho.chu@xxxxxxxxxxx>
Signed-off-by: Yelin Jeong <yelini.jeong@xxxxxxxxxxx>
Signed-off-by: Dongju Chae <dongju.chae@xxxxxxxxxxx>
Signed-off-by: MyungJoo Ham <myungjoo.ham@xxxxxxxxxxx>
---
 drivers/misc/trinity/Makefile         |   1 +
 drivers/misc/trinity/sched/core.c     | 170 +++++++++++++
 drivers/misc/trinity/sched/priority.c | 335 ++++++++++++++++++++++++++
 drivers/misc/trinity/sched/priority.h |  18 ++
 drivers/misc/trinity/sched/sched.h    |  52 ++++
 5 files changed, 576 insertions(+)
 create mode 100644 drivers/misc/trinity/sched/core.c
 create mode 100644 drivers/misc/trinity/sched/priority.c
 create mode 100644 drivers/misc/trinity/sched/priority.h
 create mode 100644 drivers/misc/trinity/sched/sched.h

diff --git a/drivers/misc/trinity/Makefile b/drivers/misc/trinity/Makefile
index cf313c3afb3d..dcf9d7ad1b4b 100644
--- a/drivers/misc/trinity/Makefile
+++ b/drivers/misc/trinity/Makefile
@@ -4,5 +4,6 @@ obj-$(CONFIG_TRINITY_VISION2) += trinity_vision2.o
 
 trinity-y := trinity.o
 trinity-y += trinity_resv_mem.o trinity_hwmem.o
+trinity-y += sched/core.o sched/priority.o
 
 trinity_vision2-objs := $(trinity-y) trinity_vision2_drv.o
diff --git a/drivers/misc/trinity/sched/core.c b/drivers/misc/trinity/sched/core.c
new file mode 100644
index 000000000000..2d94f5d07e8b
--- /dev/null
+++ b/drivers/misc/trinity/sched/core.c
@@ -0,0 +1,170 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * NPU scheduler interface
+ *
+ * Copyright (C) 2021-2022 Samsung Electronics
+ * Copyright (C) 2021 Dongju Chae <dongju.chae@xxxxxxxxxxx>
+ * Copyright (C) 2022 MyungJoo Ham <myungjoo.ham@xxxxxxxxxxx>
+ * Copyright (C) 2022 Yelin Jeong <yelini.jeong@xxxxxxxxxxx>
+ * Copyright (C) 2022 Jiho Chu <jiho.chu@xxxxxxxxxxx>
+ */
+
+#include <linux/spinlock.h>
+
+#include "../trinity_common.h"
+#include "sched.h"
+#include "priority.h"
+
+static struct trinity_sched_desc *sched_table[SCHED_END];
+static DEFINE_SPINLOCK(sched_lock);
+
+/**
+ * trinity_sched_register() - Register trinity task scheduler
+ *   It does nothing if it is already registered.
+ *
+ * @type: scheduler type
+ * @desc: scheduler description
+ */
+void trinity_sched_register(enum trinity_sched_type type,
+			    struct trinity_sched_desc *desc)
+{
+	if (type >= SCHED_END)
+		return;
+
+	spin_lock(&sched_lock);
+	if (!sched_table[type])
+		sched_table[type] = desc;
+	spin_unlock(&sched_lock);
+}
+
+/**
+ * trinity_sched_unregister() - Unregister trinity task scheduler
+ *
+ * @type: scheduler type
+ * @desc: scheduler description
+ */
+void trinity_sched_unregister(enum trinity_sched_type type,
+			      struct trinity_sched_desc *desc)
+{
+	if (type >= SCHED_END)
+		return;
+
+	spin_lock(&sched_lock);
+	if (sched_table[type] == desc)
+		sched_table[type] = NULL;
+	spin_unlock(&sched_lock);
+}
+
+/**
+ * trinity_sched_find() - Find trinity task scheduler
+ *
+ * @type: scheduler type
+ * Return: trinity scheduler description on Success, Otherwise return NULL.
+ */
+struct trinity_sched_desc *trinity_sched_find(enum trinity_sched_type type)
+{
+	struct trinity_sched_desc *desc;
+	unsigned long flags;
+
+	if (type >= SCHED_END)
+		return NULL;
+
+	spin_lock_irqsave(&sched_lock, flags);
+	desc = sched_table[type];
+	spin_unlock_irqrestore(&sched_lock, flags);
+
+	return desc;
+}
+
+/**
+ * trinity_sched_run_req() - Schedules a req to the target from the req queue
+ *
+ * @req_data: The data ptr to hold req information to be submitted.
+ *
+ * Return: 0 on success. Otherwise, returns negative error. Additional status of
+ * the submitted req could be passed by req->status.
+ */
+int32_t trinity_sched_run_req(void *req_data, void *sched_data)
+{
+	struct trinity_req *req = (struct trinity_req *)req_data;
+	struct trinity_driver *drv = req->drv;
+	int32_t err = 0;
+	int32_t ready;
+
+	/** setup is only allowed in ready state */
+	ready = drv->desc->get_state(drv);
+	if (ready != TRINITY_STATE_READY) {
+		dev_err(drv_to_dev_ptr(drv),
+			"Cannot setup NPU when it's in a non-ready state");
+		err = -EPERM;
+		goto out;
+	}
+
+	if (req->stat->status != TRINITY_REQ_STATUS_PENDING &&
+	    req->stat->status != TRINITY_REQ_STATUS_FINISHED) {
+		dev_err(drv_to_dev_ptr(drv), "Invalid req status: %d",
+			req->stat->status);
+		err = -EINVAL;
+		goto out;
+	}
+
+	req->stat->status = TRINITY_REQ_STATUS_RUNNING;
+	err = drv->desc->invoke_req(drv, req, sched_data);
+out:
+	if (err != 0)
+		req->stat->status = TRINITY_REQ_STATUS_ERROR;
+
+	return err;
+}
+
+/**
+ * trinity_sched_suspend() - Suspend whole task schedulers
+ */
+void trinity_sched_suspend(void)
+{
+	enum trinity_sched_type type;
+	struct trinity_sched_desc *desc;
+
+	for (type = SCHED_PRI; type < SCHED_END; type++) {
+		desc = sched_table[type];
+		if (desc)
+			desc->suspend();
+	}
+}
+
+/**
+ * trinity_sched_suspend() - Resume whole task schedulers
+ */
+void trinity_sched_resume(void)
+{
+	enum trinity_sched_type type;
+	struct trinity_sched_desc *desc;
+
+	for (type = SCHED_PRI; type < SCHED_END; type++) {
+		desc = sched_table[type];
+		if (desc)
+			desc->resume();
+	}
+}
+
+/**
+ * trinity_sched_init() - Initialize trinity task schedulers
+ *
+ * @dev: an instance of the device
+ * Return: always returns 0
+ */
+int32_t trinity_sched_init(struct device *dev)
+{
+	if (trinity_sched_init_pri(dev) < 0)
+		dev_warn(dev, "Unable to initialize SR task scheduler");
+
+	return 0;
+}
+
+/**
+ * trinity_sched_exit() - Exit trinity task schedulers
+ */
+void trinity_sched_exit(void)
+{
+	trinity_sched_exit_pri();
+}
diff --git a/drivers/misc/trinity/sched/priority.c b/drivers/misc/trinity/sched/priority.c
new file mode 100644
index 000000000000..3d27c84ff0ba
--- /dev/null
+++ b/drivers/misc/trinity/sched/priority.c
@@ -0,0 +1,335 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * NPU scheduler follows priority policy
+ *
+ * Copyright (C) 2021-2022 Samsung Electronics
+ * Copyright (C) 2021 Dongju Chae <dongju.chae@xxxxxxxxxxx>
+ * Copyright (C) 2022 MyungJoo Ham <myungjoo.ham@xxxxxxxxxxx>
+ * Copyright (C) 2022 Yelin Jeong <yelini.jeong@xxxxxxxxxxx>
+ * Copyright (C) 2022 Jiho Chu <jiho.chu@xxxxxxxxxxx>
+ */
+
+#include <linux/fs.h>
+#include <linux/kernel.h>
+#include <linux/kthread.h>
+#include <linux/miscdevice.h>
+#include <linux/module.h>
+#include <linux/mutex.h>
+
+#include "../trinity_common.h"
+#include "sched.h"
+
+#define get_dev_ptr() (g_sched_priv.dev)
+
+struct trinity_sched_priv {
+	struct device *dev;
+	struct llist_head req_queue;
+	wait_queue_head_t wait_queue;
+	struct task_struct *sched_thread;
+	struct mutex lock;
+	unsigned long suspended;
+};
+
+static struct trinity_sched_priv g_sched_priv;
+
+/**
+ * sched_calc_pri() - Calculate priority using timeout
+ */
+static unsigned long sched_calc_pri(struct trinity_req *req)
+{
+	ktime_t elapsed_time;
+	int64_t priority;
+
+	if (req->input.config.timeout_ms == 0)
+		return 0; /** @todo need preemption */
+
+	elapsed_time = ktime_to_ms(ktime_sub(ktime_get(), req->time_started));
+	WARN_ON(elapsed_time < 0);
+
+	/**
+	 * if the elapsed time exceeds the timeout of req,
+	 * its priority value is set to the minimum (highest).
+	 */
+	priority = req->input.config.timeout_ms - elapsed_time;
+	if (priority < 0)
+		priority = 0;
+
+	return priority;
+}
+
+/**
+ * sched_pick_req() - Pick the top-priority request from request queue
+ */
+static struct trinity_req *sched_pick_req(struct llist_head *queue)
+{
+	struct trinity_req *req, *req_prev;
+	struct trinity_req *top_req, *top_req_prev;
+	int64_t top_priority = S64_MAX;
+	unsigned long priority;
+
+	if (llist_empty(queue))
+		return NULL;
+
+	req = req_prev = NULL;
+	top_req = top_req_prev = NULL;
+
+	/**
+	 * llist is not a double linked list, and sorting is not easy
+	 * because llist provides only limited APIs.
+	 * it could be better than sorting if there are a few pending reqs.
+	 * Note that each user application can submit only one req at once.
+	 */
+	llist_for_each_entry(req, queue->first, llist) {
+		priority = sched_calc_pri(req);
+		if (top_priority > priority) {
+			top_priority = priority;
+			top_req = req;
+			top_req_prev = req_prev;
+		}
+
+		req_prev = req;
+	}
+
+	if (top_req_prev) {
+		WARN_ON(!top_req);
+		top_req_prev->llist.next = top_req->llist.next;
+	} else {
+		/** it's first entry */
+		top_req = llist_entry(llist_del_first(queue), typeof(*(req)),
+				      llist);
+	}
+
+	return top_req;
+}
+
+/**
+ * llist_last() - Get latest node from list
+ */
+static struct llist_node *llist_last(struct llist_node *first)
+{
+	struct llist_node *last = first;
+
+	while (first && first->next) {
+		last = first->next;
+		first = last;
+	}
+
+	return last;
+}
+
+/**
+ * sched_thread_func() - Scheduler thread function
+ */
+static int sched_thread_func(void *data)
+{
+	const unsigned long MAX_RETRY_COUNT = 100;
+
+	struct llist_head local_queue;
+	struct llist_node *new_first;
+
+	init_llist_head(&local_queue);
+repeat:
+	if (kthread_should_stop())
+		return 0;
+
+	/** extract requests from global queue without locking */
+	new_first = llist_del_all(&g_sched_priv.req_queue);
+	/** new and pending requests could be located together */
+	if (new_first) {
+		struct llist_node *new_last = llist_last(new_first);
+
+		llist_add_batch(new_first, new_last, &local_queue);
+	}
+
+	/** flush requests in the queue */
+	while (!llist_empty(&local_queue)) {
+		struct trinity_req *req;
+		int32_t ret;
+
+		/**
+		 * pick the top-priority request from the queue.
+		 * first and last node pointers are updated
+		 */
+		req = sched_pick_req(&local_queue);
+		if (!req)
+			goto repeat;
+
+		mutex_lock(&g_sched_priv.lock);
+		ret = trinity_sched_run_req(req, NULL);
+		mutex_unlock(&g_sched_priv.lock);
+
+		/** do not modify or access for 'req' except on an error case.
+		 *  it could be released by the interrupt.
+		 */
+
+		if (ret == -EBUSY) {
+			if (req->submit_retry >= MAX_RETRY_COUNT) {
+				/** give up to handling this req*/
+				complete_all(&req->complete);
+			} else {
+				req->submit_retry++;
+				/** push again and restart the loop */
+				llist_add(&req->llist, &local_queue);
+			}
+			goto repeat;
+		} else if (ret != 0) {
+			/** let's notify this unknown error */
+			complete_all(&req->complete);
+		}
+	}
+
+	/** ensure the local queue is empty */
+	WARN_ON(!llist_empty(&local_queue));
+
+	wait_event_interruptible(
+		g_sched_priv.wait_queue,
+		kthread_should_stop() ||
+			!llist_empty(&(g_sched_priv.req_queue)));
+	goto repeat;
+}
+
+/**
+ * sched_ready() - Check scheduler is ready
+ */
+static bool sched_ready(void)
+{
+	return (test_bit(1, &g_sched_priv.suspended) != 1);
+}
+
+/**
+ * sched_submit() - Submit request to scheduler
+ */
+static int32_t sched_submit(void *data)
+{
+	struct trinity_req *req = data;
+
+	if (!req)
+		return -EINVAL;
+
+	if (!sched_ready())
+		return -EAGAIN;
+
+	llist_add(&req->llist, &g_sched_priv.req_queue);
+	wake_up(&g_sched_priv.wait_queue);
+
+	return 0;
+}
+
+/**
+ * sched_notify() - finishes and notify the request handled
+ */
+static void sched_notify(void *data, bool error)
+{
+	struct trinity_req *req = data;
+
+	req->scheduled = false;
+}
+
+/**
+ * sched_suspend() - Suspend scheduler
+ */
+static void sched_suspend(void)
+{
+	if (!test_and_set_bit(1, &g_sched_priv.suspended))
+		mutex_lock(&g_sched_priv.lock);
+}
+
+/**
+ * sched_resume() - Resume scheduler
+ */
+static void sched_resume(void)
+{
+	if (test_and_clear_bit(1, &g_sched_priv.suspended))
+		mutex_unlock(&g_sched_priv.lock);
+}
+
+static struct trinity_sched_desc trinity_sched_pri = {
+	.ready = sched_ready,
+	.submit = sched_submit,
+	.notify = sched_notify,
+	.suspend = sched_suspend,
+	.resume = sched_resume,
+};
+
+/**
+ * sched_open() - Open scheduler
+ */
+static int sched_open(struct inode *inodep, struct file *filp)
+{
+	return 0;
+}
+
+/**
+ * sched_open() - Release scheduler
+ */
+static int sched_release(struct inode *inodep, struct file *filp)
+{
+	return 0;
+}
+
+static const struct file_operations sched_fops = {
+	.owner = THIS_MODULE,
+	.open = sched_open,
+	.release = sched_release,
+	.llseek = no_llseek,
+};
+
+static struct miscdevice sched_device = {
+	.minor = MISC_DYNAMIC_MINOR,
+	.name = "trinity_sched_pri",
+	.fops = &sched_fops,
+};
+
+/**
+ * sched_init_priv() - Initialize scheduler
+ */
+static int sched_init_priv(void)
+{
+	g_sched_priv.dev = sched_device.this_device;
+
+	init_llist_head(&g_sched_priv.req_queue);
+	init_waitqueue_head(&g_sched_priv.wait_queue);
+
+	g_sched_priv.sched_thread =
+		kthread_run(sched_thread_func, NULL, "trinity_sched_thread");
+	if (IS_ERR(g_sched_priv.sched_thread)) {
+		dev_err(get_dev_ptr(),
+			"Failed to create a thread for scheduling reqs");
+		misc_deregister(&sched_device);
+		return PTR_ERR(g_sched_priv.sched_thread);
+	}
+
+	mutex_init(&g_sched_priv.lock);
+	clear_bit(1, &g_sched_priv.suspended);
+
+	return 0;
+}
+
+/**
+ * trinity_sched_init_pri() - Initialize trinity priority task schedulers
+ *
+ * @dev: an instance of the device
+ */
+int trinity_sched_init_pri(struct device *dev)
+{
+	int err;
+
+	err = misc_register(&sched_device);
+	if (err) {
+		dev_err(dev,
+			"Failed to register a misc device for scheduler\n");
+		return err;
+	}
+
+	trinity_sched_register(SCHED_PRI, &trinity_sched_pri);
+	return sched_init_priv();
+}
+
+/**
+ * trinity_sched_exit_pri() - Exit trinity priority task schedulers
+ */
+void trinity_sched_exit_pri(void)
+{
+	trinity_sched_unregister(SCHED_PRI, &trinity_sched_pri);
+	misc_deregister(&sched_device);
+}
diff --git a/drivers/misc/trinity/sched/priority.h b/drivers/misc/trinity/sched/priority.h
new file mode 100644
index 000000000000..35ac07530496
--- /dev/null
+++ b/drivers/misc/trinity/sched/priority.h
@@ -0,0 +1,18 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/**
+ * NPU scheduler follows priority policy
+ *
+ * Copyright (C) 2021-2022 Samsung Electronics
+ * Copyright (C) 2021 Dongju Chae <dongju.chae@xxxxxxxxxxx>
+ * Copyright (C) 2022 MyungJoo Ham <myungjoo.ham@xxxxxxxxxxx>
+ * Copyright (C) 2022 Yelin Jeong <yelini.jeong@xxxxxxxxxxx>
+ * Copyright (C) 2022 Jiho Chu <jiho.chu@xxxxxxxxxxx>
+ */
+
+#ifndef __TRINITY_SCHED_PRI_H__
+#define __TRINITY_SCHED_PRI_H__
+
+int trinity_sched_init_pri(struct device *dev);
+void trinity_sched_exit_pri(void);
+
+#endif /* __TRINITY_SCHED_PRI_H__ */
diff --git a/drivers/misc/trinity/sched/sched.h b/drivers/misc/trinity/sched/sched.h
new file mode 100644
index 000000000000..d13ef5857fc7
--- /dev/null
+++ b/drivers/misc/trinity/sched/sched.h
@@ -0,0 +1,52 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/**
+ * Scheduler I/F header for trinity devices
+ *
+ * Copyright (C) 2021-2022 Samsung Electronics
+ * Copyright (C) 2021 Dongju Chae <dongju.chae@xxxxxxxxxxx>
+ * Copyright (C) 2022 MyungJoo Ham <myungjoo.ham@xxxxxxxxxxx>
+ * Copyright (C) 2022 Yelin Jeong <yelini.jeong@xxxxxxxxxxx>
+ * Copyright (C) 2022 Jiho Chu <jiho.chu@xxxxxxxxxxx>
+ */
+
+#ifndef __TRINITY_SCHED_H__
+#define __TRINITY_SCHED_H__
+
+#include <linux/device.h>
+#include <linux/types.h>
+
+/**
+ * struct trinity_sched_type - scheduler type
+ */
+enum trinity_sched_type { SCHED_PRI = 0, SCHED_END };
+
+typedef void (*remove_req_cb)(void *data, void *req);
+
+/**
+ * struct trinity_sched_desc - a structure for scheduler description
+ */
+struct trinity_sched_desc {
+	bool (*ready)(void);
+	int32_t (*submit)(void *data);
+	bool (*cancel)(void *data);
+	void (*suspend)(void);
+	void (*resume)(void);
+	void (*notify)(void *data, bool error);
+
+	struct trinity_req *(*find_req)(uint32_t dev_id, int req_id);
+	void (*remove_reqs)(void *data, remove_req_cb cb);
+	void (*test_run)(void *data, int req_id);
+};
+
+struct trinity_sched_desc *trinity_sched_find(enum trinity_sched_type type);
+void trinity_sched_register(enum trinity_sched_type type,
+			    struct trinity_sched_desc *desc);
+void trinity_sched_unregister(enum trinity_sched_type type,
+			      struct trinity_sched_desc *desc);
+int32_t trinity_sched_run_req(void *req_data, void *sched_data);
+void trinity_sched_suspend(void);
+void trinity_sched_resume(void);
+int32_t trinity_sched_init(struct device *dev);
+void trinity_sched_exit(void);
+
+#endif /* __TRINITY_SCHED_H__ */
-- 
2.25.1