From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754723AbbDTIZU (ORCPT ); Mon, 20 Apr 2015 04:25:20 -0400 Received: from m50-110.126.com ([123.125.50.110]:40667 "EHLO m50-110.126.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754659AbbDTIZK (ORCPT ); Mon, 20 Apr 2015 04:25:10 -0400 From: Xunlei Pang To: linux-kernel@vger.kernel.org Cc: Peter Zijlstra , Steven Rostedt , Juri Lelli , Xunlei Pang Subject: [PATCH v6 1/3] lib/plist: Provide plist_add_head() for nodes with the same prio Date: Mon, 20 Apr 2015 16:22:46 +0800 Message-Id: <1429518168-7965-1-git-send-email-xlpang@126.com> X-Mailer: git-send-email 1.9.1 X-CM-TRANSID: jdKowAD3__uLtzRVzV2uAQ--.4394S2 X-Coremail-Antispam: 1Uf129KBjvJXoWxuF18tw1fGrW3uryfGr47XFb_yoWrXFyDpr y5G345J397AryIgw4SyF4j9rsagF18JF4jyryxCr9xAr1jgr4IqFy3XF4UAFn3JrWkur1r JF4rKw1UGr4UJr7anT9S1TB71UUUUUUqnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07jk8n5UUUUU= X-Originating-IP: [210.21.223.3] X-CM-SenderInfo: p0ost0bj6rjloofrz/1tbiXBXhv1R0VxnWQwAAss Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Xunlei Pang 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 Signed-off-by: Xunlei Pang --- 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