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

[Dan Streetman]

On Mon, Mar 9, 2015 at 3:32 AM, 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
> 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.
>
> cc: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
> cc: Dan Streetman <ddstreet@xxxxxxxx>
> Signed-off-by: Xunlei Pang <pang.xunlei@xxxxxxxxxx>
> ---
>  include/linux/plist.h | 30 +++++++++++++++++++++++++++++-
>  lib/plist.c           | 24 +++++++++++++++++++++---
>  2 files changed, 50 insertions(+), 4 deletions(-)
>
> diff --git a/include/linux/plist.h b/include/linux/plist.h
> index 9788360..10c834c 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, true);
> +}
> +
> +/**
> + * 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, 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..d3ebac6 100644
> --- a/lib/plist.c
> +++ b/lib/plist.c
> @@ -66,12 +66,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;
> @@ -96,8 +100,22 @@ 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, 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.
> +                */
> +               list_add(&node->prio_list, &prev->prio_list);
> +               list_del_init(&prev->prio_list);

I think this can just be

list_replace_init(&prev->prio_list, &node->prio_list);

besides that,
Reviewed-by: Dan Streetman <ddstreet@xxxxxxxx>

> +               node_next = &prev->node_list;
> +       }
>  ins_node:
>         list_add_tail(&node->node_list, node_next);
>
> --
> 1.9.1
>
>
--
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/