2 files changed, 54 insertions, 0 deletions

diff --git a/include/linux/plist.h b/include/linux/plist.h
index c81549119bd4..8b6c970cff6c 100644
--- a/include/linux/plist.h
+++ b/include/linux/plist.h
@@ -141,6 +141,8 @@ static inline void plist_node_init(struct plist_node *node, int prio)
 extern void plist_add(struct plist_node *node, struct plist_head *head);
 extern void plist_del(struct plist_node *node, struct plist_head *head);
 
+extern void plist_requeue(struct plist_node *node, struct plist_head *head);
+
 /**
  * plist_for_each - iterate over the plist
  * @pos:        the type * to use as a loop counter
diff --git a/lib/plist.c b/lib/plist.c
index 1ebc95f7a46f..0f2084d30798 100644
--- a/lib/plist.c
+++ b/lib/plist.c
@@ -134,6 +134,46 @@ void plist_del(struct plist_node *node, struct plist_head *head)
         plist_check_head(head);
 }
 
+/**
+ * plist_requeue - Requeue @node at end of same-prio entries.
+ *
+ * This is essentially an optimized plist_del() followed by
+ * plist_add().  It moves an entry already in the plist to
+ * after any other same-priority entries.
+ *
+ * @node:       &struct plist_node pointer - entry to be moved
+ * @head:       &struct plist_head pointer - list head
+ */
+void plist_requeue(struct plist_node *node, struct plist_head *head)
+{
+        struct plist_node *iter;
+        struct list_head *node_next = &head->node_list;
+
+        plist_check_head(head);
+        BUG_ON(plist_head_empty(head));
+        BUG_ON(plist_node_empty(node));
+
+        if (node == plist_last(head))
+                return;
+
+        iter = plist_next(node);
+
+        if (node->prio != iter->prio)
+                return;
+
+        plist_del(node, head);
+
+        plist_for_each_continue(iter, head) {
+                if (node->prio != iter->prio) {
+                        node_next = &iter->node_list;
+                        break;
+                }
+        }
+        list_add_tail(&node->node_list, node_next);
+
+        plist_check_head(head);
+}
+
 #ifdef CONFIG_DEBUG_PI_LIST
 #include <linux/sched.h>
 #include <linux/module.h>
@@ -170,6 +210,14 @@ static void __init plist_test_check(int nr_expect)
         BUG_ON(prio_pos->prio_list.next != &first->prio_list);
 }
 
+static void __init plist_test_requeue(struct plist_node *node)
+{
+        plist_requeue(node, &test_head);
+
+        if (node != plist_last(&test_head))
+                BUG_ON(node->prio == plist_next(node)->prio);
+}
+
 static int  __init plist_test(void)
 {
         int nr_expect = 0, i, loop;
@@ -193,6 +241,10 @@ static int  __init plist_test(void)
                         nr_expect--;
                 }
                 plist_test_check(nr_expect);
+                if (!plist_node_empty(test_node + i)) {
+                        plist_test_requeue(test_node + i);
+                        plist_test_check(nr_expect);
+                }
         }
 
         for (i = 0; i < ARRAY_SIZE(test_node); i++) {