Messages in this thread Patch in this message | | | Date | Sat, 07 May 2005 17:34:53 +0400 | From | Oleg Nesterov <> | Subject | [RFC][PATCH] alternative implementation of Priority Lists |
| |
This patch adds priority lists to the kernel, see this thread: http://marc.theaimsgroup.com/?t=111289685000001&r=1
It was thoroughly tested in userspace, you can get the test here: http://tv-sign.ru/update/plist.tgz
It lacks documentation, so it is for review only.
Notes:
This patch adds 2 structures: pl_head and pl_node. I think it is good for typechecking.
plist_add() does not require that the new node is initialized (except ->prio).
no plist_del_init(), plist_del() does initialization on the deleted node.
no plist_entry(), use container_of()
The code snippet from original patch:
struct plist *next1, *next2, *curr1, *curr2; struct rt_mutex_waiter *w;
plist_for_each_safe(curr1, curr2, next1, next2, &old_owner->pi_waiters) { w = plist_entry(curr2, struct rt_mutex_waiter, pi_list); if (w->lock == lock) { plist_del(&w->pi_list, &old_owner->pi_waiters); plist_init(&w->pi_list, w->task->prio); plist_add(&w->pi_list, &new_owner->pi_waiters);
This becomes:
struct rt_mutex_waiter *w, tmp;
plist_for_each_entry_safe(w, tmp, &old_owner->pi_waiters) { if (w->lock == lock) { plist_del(&w->pi_list, &old_owner->pi_waiters); w->pi_list.prio = w->task->prio; plist_add(&w->pi_list, &new_owner->pi_waiters);
Please comment.
Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
--- /dev/null Sat Jan 1 03:00:00 2000 +++ kernel/include/linux/plist.h Sat May 7 16:42:05 2005 @@ -0,0 +1,84 @@ +#ifndef _LINUX_PLIST_H_ +#define _LINUX_PLIST_H_ + +#include <linux/list.h> + +struct pl_head { + struct list_head prio_list; + struct list_head node_list; +}; + +struct pl_node { + int prio; + struct pl_head plist; +}; + +#define PL_HEAD_INIT(head) \ +{ \ + .prio_list = LIST_HEAD_INIT((head).prio_list), \ + .node_list = LIST_HEAD_INIT((head).node_list), \ +} + +#define PL_NODE_INIT(node, __prio) \ +{ \ + .prio = (__prio), \ + .plist = PL_HEAD_INIT((node).plist), \ +} + +static inline void pl_head_init(struct pl_head *head) +{ + INIT_LIST_HEAD(&head->prio_list); + INIT_LIST_HEAD(&head->node_list); +} + +static inline void pl_node_init(struct pl_node *node, int prio) +{ + node->prio = prio; + pl_head_init(&node->plist); +} + +extern void plist_add(struct pl_node *node, struct pl_head *head); +extern void plist_del(struct pl_node *node); + +#define plist_for_each(pos, head) \ + list_for_each_entry(pos, &(head)->node_list, plist.node_list) + +#define plist_for_each_safe(pos, n, head) \ + list_for_each_entry_safe(pos, n, &(head)->node_list, plist.node_list) + +#define plist_for_each_entry(pos, head, mem) \ + list_for_each_entry(pos, &(head)->node_list, mem.plist.node_list) + +#define plist_for_each_entry_safe(pos, n, head, mem) \ + list_for_each_entry_safe(pos, n, &(head)->node_list, mem.plist.node_list) + +static inline int plist_empty(const struct pl_head *head) +{ + return list_empty(&head->node_list); +} + +#define __pl_head_node(head, list, dir) \ + list_entry((head)->list.dir, struct pl_node, plist.list) + +static inline struct pl_node* plist_next(const struct pl_head *head) +{ + return __pl_head_node(head, node_list, next); +} + +static inline struct pl_node* plist_prev(const struct pl_head *head) +{ + return __pl_head_node(head, node_list, prev); +} + +static inline struct pl_node* plist_prio_next(const struct pl_head *head) +{ + return __pl_head_node(head, prio_list, next); +} + +static inline struct pl_node* plist_prio_prev(const struct pl_head *head) +{ + return __pl_head_node(head, prio_list, prev); +} + +#undef __pl_head_node +#endif --- /dev/null Sat Jan 1 03:00:00 2000 +++ kernel/lib/plist.c Sat May 7 16:30:50 2005 @@ -0,0 +1,32 @@ +#include <linux/plist.h> + +void plist_add(struct pl_node *node, struct pl_head *head) +{ + struct pl_node *iter; + + INIT_LIST_HEAD(&node->plist.prio_list); + + list_for_each_entry(iter, &head->prio_list, plist.prio_list) + if (node->prio < iter->prio) + goto lt_prio; + else if (node->prio == iter->prio) { + iter = plist_prio_next(&iter->plist); + goto eq_prio; + } + +lt_prio: + list_add_tail(&node->plist.prio_list, &iter->plist.prio_list); +eq_prio: + list_add_tail(&node->plist.node_list, &iter->plist.node_list); +} + +void plist_del(struct pl_node *node) +{ + if (!list_empty(&node->plist.prio_list)) { + struct pl_node *next = plist_next(&node->plist); + list_move_tail(&next->plist.prio_list, &node->plist.prio_list); + list_del_init(&node->plist.prio_list); + } + + list_del_init(&node->plist.node_list); +} _ - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |