lkml.org 
[lkml]   [2015]   [Apr]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH v6 1/3] lib/plist: Provide plist_add_head() for nodes with the same prio
Date
From: Xunlei Pang <pang.xunlei@linaro.org>

If there're multiple nodes with the same prio as @node, currently
plist_add() will add @node behind all of them. Now we need to add
@node before all of these nodes for SMP RT scheduler.

This patch adds a common __plist_add() for adding @node before or
after existing nodes with the same prio, then adds plist_add_head()
and plist_add_tail() inline wrapper functions for convenient uses.

Finally, define plist_add() as plist_add_tail() which has the same
behaviour as before.

Reviewed-by: Dan Streetman <ddstreet@ieee.org>
Signed-off-by: Xunlei Pang <pang.xunlei@linaro.org>
---
v5->v6:
Add more detailed annotations.

include/linux/plist.h | 30 +++++++++++++++++++++++++++++-
lib/plist.c | 28 +++++++++++++++++++++++-----
2 files changed, 52 insertions(+), 6 deletions(-)

diff --git a/include/linux/plist.h b/include/linux/plist.h
index 9788360..39806a2 100644
--- a/include/linux/plist.h
+++ b/include/linux/plist.h
@@ -138,7 +138,35 @@ static inline void plist_node_init(struct plist_node *node, int prio)
INIT_LIST_HEAD(&node->node_list);
}

-extern void plist_add(struct plist_node *node, struct plist_head *head);
+extern void __plist_add(struct plist_node *node,
+ struct plist_head *head, bool is_head);
+
+/**
+ * plist_add_head - add @node to @head, before all existing same-prio nodes
+ *
+ * @node: The plist_node to be added to @head
+ * @head: The plist_head that @node is being added to
+ */
+static inline
+void plist_add_head(struct plist_node *node, struct plist_head *head)
+{
+ __plist_add(node, head, true);
+}
+
+/**
+ * plist_add_tail - add @node to @head, after all existing same-prio nodes
+ *
+ * @node: The plist_node to be added to @head
+ * @head: The plist_head that @node is being added to
+ */
+static inline
+void plist_add_tail(struct plist_node *node, struct plist_head *head)
+{
+ __plist_add(node, head, false);
+}
+
+#define plist_add plist_add_tail
+
extern void plist_del(struct plist_node *node, struct plist_head *head);

extern void plist_requeue(struct plist_node *node, struct plist_head *head);
diff --git a/lib/plist.c b/lib/plist.c
index 3a30c53..c1ee2b0 100644
--- a/lib/plist.c
+++ b/lib/plist.c
@@ -66,12 +66,18 @@ static void plist_check_head(struct plist_head *head)
#endif

/**
- * plist_add - add @node to @head
+ * __plist_add - add @node to @head
*
- * @node: &struct plist_node pointer
- * @head: &struct plist_head pointer
+ * @node: The plist_node to be added to @head
+ * @head: The plist_head that @node is being added to
+ * @is_head: True if adding to head of prio list, false otherwise
+ *
+ * For nodes of the same prio, @node will be added at the
+ * head of previously added nodes if @is_head is true, or
+ * it will be added at the tail of previously added nodes
+ * if @is_head is false.
*/
-void plist_add(struct plist_node *node, struct plist_head *head)
+void __plist_add(struct plist_node *node, struct plist_head *head, bool is_head)
{
struct plist_node *first, *iter, *prev = NULL;
struct list_head *node_next = &head->node_list;
@@ -96,8 +102,20 @@ void plist_add(struct plist_node *node, struct plist_head *head)
struct plist_node, prio_list);
} while (iter != first);

- if (!prev || prev->prio != node->prio)
+ if (!prev || prev->prio != node->prio) {
list_add_tail(&node->prio_list, &iter->prio_list);
+ } else if (is_head) {
+ /*
+ * prev has the same priority as the node that is being
+ * added. It is also the first node for this priority,
+ * but the new node needs to be added ahead of it.
+ * To accomplish this, replace prev in the prio_list
+ * with node. Then set node_next to prev->node_list so
+ * that the new node gets added before prev and not iter.
+ */
+ list_replace_init(&prev->prio_list, &node->prio_list);
+ node_next = &prev->node_list;
+ }
ins_node:
list_add_tail(&node->node_list, node_next);

--
1.9.1



\
 
 \ /
  Last update: 2015-04-20 11:01    [W:0.161 / U:3.696 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site