Re: [PATCH v4 1/3] lib/plist: Provide plist_add_head() for nodes with the same prio

[Steven Rostedt]

On Mon, 16 Feb 2015 17:32:22 +0800
Xunlei Pang <xlpang@xxxxxxx> wrote:

> From: Xunlei Pang <pang.xunlei@xxxxxxxxxx>
> 
> 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
> behind 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() with plist_add_tail() which has the same
> behaviour as before.
> 
> Signed-off-by: Xunlei Pang <pang.xunlei@xxxxxxxxxx>
> ---
>  include/linux/plist.h | 30 +++++++++++++++++++++++++++++-
>  lib/plist.c           | 15 ++++++++++++---
>  2 files changed, 41 insertions(+), 4 deletions(-)
> 
> diff --git a/include/linux/plist.h b/include/linux/plist.h
> index 9788360..e17bb96 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:	&struct plist_node pointer
> + * @head:	&struct plist_head pointer
> + */
> +static inline
> +void plist_add_head(struct plist_node *node, struct plist_head *head)
> +{
> +	__plist_add(node, head, 1);

is_head is boolean, shouldn't that be "true" instead of "1".

> +}
> +
> +/**
> + * plist_add_tail - add @node to @head, after all existing same-prio nodes
> + *
> + * @node:	&struct plist_node pointer
> + * @head:	&struct plist_head pointer
> + */
> +static inline
> +void plist_add_tail(struct plist_node *node, struct plist_head *head)
> +{
> +	__plist_add(node, head, 0);

And "false" here.

> +}
> +
> +#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 d408e77..0e1f1b3 100644
> --- a/lib/plist.c
> +++ b/lib/plist.c
> @@ -67,12 +67,16 @@ 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
> + * @is_head:	bool
> + *
> + * If there're any nodes with the same prio, add @node
> + * behind or before all of them according to @is_head.
>   */
> -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;
> @@ -97,8 +101,13 @@ 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) {
> +		list_add(&node->prio_list, &prev->prio_list);
> +		list_del_init(&prev->prio_list);
> +		node_next = &prev->node_list;

The above could use some comments. I would say the entire plist code
could use more comments, but that's out of scope with this series. But
at least lets add comments when adding new code. Something like:

	} 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, insert node right after prev
		 * in the prio_list and then remove prev from that list.
		 * Then set node_next to prev->node_list so that the
		 * new node gets added before prev and not iter.
		 */

Something like that, because it took me some time to figure out how
plist works. It's one of those algorithms that seem to page fault out
quickly, and takes some time to page fault back into one's mind.


-- Steve


> +	}
>  ins_node:
>  	list_add_tail(&node->node_list, node_next);
>  

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/