Priority Lists for the RT mutex
Review
Quoted 10 lines · Daniel Walker
Description:
This patch adds the priority list data structure from Inaky Perez-Gonzalez
to the Preempt Real-Time mutex....
(quoted diff) +3
-0+#define plist_for_each(pos1, pos2, head) \ + list_for_each_entry(pos1, &((head)->dp_node), dp_node) \ + list_for_each_entry(pos2, &((pos1)->sp_node), sp_node)
I can't understand how this can work.
The fist list_for_each_entry(->dp_node) will iterate over nodes with different priorities, ok. But the second one will skip the first node (which starts new priority group), because list_for_each(head) does not count head.
To be sure, I wrote simple test:
#include <stdio.h>
#include <limits.h>
#include "list.h"
#include "plist.h"
int main(void)
{
struct plist head, node, *pos1, *pos2;
plist_init(&head, 0);
plist_init(&node, 0);
plist_add(&node, &head);
plist_for_each(pos1, pos2, &head)
printf("Strange ???\n");
return 0;
}Prints nothing.
My apologies if I'm misunderstanding something.
Oleg.
Quoted 10 lines · Oleg Nesterov
Quoted 5 lines · Daniel Walker
Description:
This patch adds the priority list data structure from Inaky Perez-Gonzalez
to the Preempt Real-Time mutex....
I can't understand how this can work.
And I think it is possible to simplify plist's design.
struct plist {
int prio;
struct list_head prio_list;
struct list_head node_list;
};#define plist_for_each(pos, head) \ list_for_each_entry(pos, &(head)->node_list, node_list)
static inline void plist_add(struct plist *new, struct plist *head)
{
struct plist* pos;
INIT_LIST_HEAD(&new->prio_list);
list_for_each_entry(pos, &head->prio_list, prio_list)
if (new->prio < pos->prio)
goto lt_prio;
else if (new->prio == pos->prio) {
pos = list_entry(pos->prio_list.next,
struct plist, prio_list);
goto eq_prio;
}lt_prio:
list_add_tail(&new->prio_list, &pos->prio_list); eq_prio: list_add_tail(&new->node_list, &pos->node_list); }
static inline void plist_del(struct plist *del)
{
if (!list_empty(&del->prio_list)) {
struct plist *next = list_entry(del->node_list.next,
struct plist, node_list);
list_move_tail(&next->prio_list, &del->prio_list);
list_del_init(&del->prio_list);
}
list_del_init(&del->node_list);
}All nodes in prio list are chained via ->node_list, sorted in ascending ->prio/fifo order. Nodes which start different priority slice are chained via ->prio_list, ascending ->prio order.
Slightly tested, seems to work.
I think this would be even better:
struct plist_head {
struct list_head prio_list;
struct list_head node_list;
}struct plist {
int prio;
struct plist_head head;
}The plist_head's min/max prio can be found from
plist_head.prio_list.next/prev.
What do you think?
Oleg.
Quoted 12 lines · Oleg Nesterov
Quoted 10 lines · Oleg Nesterov
Quoted 5 lines · Daniel Walker
Description:
This patch adds the priority list data structure from Inaky Perez-Gonzalez
to the Preempt Real-Time mutex....
I can't understand how this can work.
Quoted 8 lines
And I think it is possible to simplify plist's design.
struct plist { int prio; struct list_head prio_list; struct list_head node_list; };
Make a patch .
Daniel