Skip to contentSkip to conversation

Priority Lists for the RT mutex

PATCH Oleg Nesterov 2 participants 3 messages May 6, 2005

lore
Share & tools
lore
#0 lore raw

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.

#1 lore raw
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.

#2 lore raw
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