Skip to contentSkip to conversation

Real-Time Preemption, -RT-2.6.12-rc4-V0.7.47-06

PATCH Oleg Nesterov 3 participants 14 messages May 23, 2005 – Jun 1, 2005

lore
Share & tools
lore
#0 lore raw
Quoted 4 lines · Ingo Molnar

Changes:

- more plist fixes (Daniel Walker)

plists were changed so that all nodes are tied via ->sp_node.

Now:

	#define plist_for_each(pos1, head)	\
		list_for_each_entry(pos1, &((head)->sp_node), sp_node)

This is correct.

	plist_for_each(curr1, &old_owner->pi_waiters) {
		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
		if (w == waiter)
			goto ok;
	}

And this is not. because:

	#define plist_entry(ptr, type, member) \
		container_of(plist_first(ptr), type, member)
			     ^^^^^^^^^^^
	struct plist * plist_first(struct plist *plist)
	{
		return list_entry(plist->dp_node.next, struct plist, dp_node);
	}

So the very first node will be skipped, iteration will be out of order, and you will have the plist's *head* as a last element (which is not struct rt_mutex_waiter, of course).

Review

Quoted 5 lines

unsigned plist_empty(const struct plist *plist)
{

(quoted diff) +1 -1
-	return list_empty (&plist->dp_node);
+	return list_empty(&plist->dp_node) && list_empty(&plist->sp_node);
 }

It's enough to check list_empty(&plist->sp_node) only.

And I don't understand why __plist_add_sorted is so complecated. Why should we consider ->prio == INT_MAX as a special case? This is also strange:

	new_sp_head:
		itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
		list_add(&pl->sp_node, &itr_pl2->sp_node);

Why? Just list_add_tail(&pl->sp_node, itr_pl->sp_node), you don't need itr_pl2 at all.

Daniel, if you accepted all-nodes-tied-via-sp_node idea, could you also look at the code I've suggested. I think it is much simpler and understandable.

void plist_add(struct plist *new, struct plist *head)

{
	struct plist* pos;

	INIT_LIST_HEAD(&new->dp_node);

	list_for_each_entry(pos, &head->dp_node, dp_node)
		if (new->prio < pos->prio)
			goto lt_prio;
		else if (new->prio == pos->prio) {
			pos = list_entry(pos->dp_node.next,
					 struct plist, dp_node);
			goto eq_prio;
		}

lt_prio:

	list_add_tail(&new->dp_node, &pos->dp_node);
eq_prio:
	list_add_tail(&new->sp_node, &pos->sp_node);
}

void plist_del(struct plist *del)

{
	if (!list_empty(&del->dp_node)) {
		struct plist *next = list_entry(del->sp_node.next,
						struct plist, sp_node);
		list_move_tail(&next->dp_node, &del->dp_node);
		list_del_init(&del->dp_node);
	}

	list_del_init(&del->sp_node);
}

Personally, I think it is better to have pl_head for plist's head, and pl_node for nodes. It is pointless to store ->prio in the plist's head, it can be found in plist_first()->prio. This way we can trim the size of rt_mutex to 32 bytes, and it is good for typechecking.

Ingo, did you see these patches?
http://marc.theaimsgroup.com/?l=linux-kernel&m=111565001426673
http://marc.theaimsgroup.com/?l=linux-kernel&m=111565001415428
http://marc.theaimsgroup.com/?l=linux-kernel&m=111565001427334
http://marc.theaimsgroup.com/?l=linux-kernel&m=111565001408303
?

What do you think?

Oleg.

#1 lore raw
Quoted 3 lines · Oleg Nesterov

So the very first node will be skipped, iteration will be out of order, and you will have the plist's *head* as a last element (which is not struct rt_mutex_waiter, of course).

True, but the first node is the list head which must be static, It's not an actual list member.

Quoted 7 lines

Review

Quoted 5 lines

unsigned plist_empty(const struct plist *plist)
{

(quoted diff) +1 -1
-	return list_empty (&plist->dp_node);
+	return list_empty(&plist->dp_node) && list_empty(&plist->sp_node);
 }

It's enough to check list_empty(&plist->sp_node) only.

True.

Quoted 6 lines
	new_sp_head:
		itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
		list_add(&pl->sp_node, &itr_pl2->sp_node);

Why? Just list_add_tail(&pl->sp_node, itr_pl->sp_node), you don't need itr_pl2 at all.

Wouldn't work . What if itr_pl has 15 elements at it's priority?

Quoted 3 lines

Daniel, if you accepted all-nodes-tied-via-sp_node idea, could you also look at the code I've suggested. I think it is much simpler and understandable.

I will/have. The sp_node all connect idea came from your stuff.

Quoted 4 lines

Personally, I think it is better to have pl_head for plist's head, and pl_node for nodes. It is pointless to store ->prio in the plist's head, it can be found in plist_first()->prio. This way we can trim the size of rt_mutex to 32 bytes, and it is good for typechecking.

I like that idea, I just haven't done it yet.

Daniel

#2 lore raw
Quoted 9 lines · Daniel Walker
Quoted 3 lines · Oleg Nesterov

So the very first node will be skipped, iteration will be out of order, and you will have the plist's *head* as a last element (which is not struct rt_mutex_waiter, of course).

True, but the first node is the list head which must be static, It's not an actual list member.

No. Look, plist_for_each() is just list_for_each_entry() now. So, the the first iteration will play with head->sp_node.next, not with head! And then you are doing ->dp_node.next again in plist_entry().

I'd suggest you to write simple programm, and test. I bet I'm right.

Quoted 8 lines
Quoted 6 lines
	new_sp_head:
		itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
		list_add(&pl->sp_node, &itr_pl2->sp_node);

Why? Just list_add_tail(&pl->sp_node, itr_pl->sp_node), you don't need itr_pl2 at all.

Wouldn't work . What if itr_pl has 15 elements at it's priority?

15 or 0, I think it would work. Look, it is *new* priority, and pl->prio < itr_pl->prio, so pl should stay just before itr_pl in ->sp_node list. That is why list_add_tail(&pl->sp_node, itr_pl->sp_node) is enough.

Oleg.

#3 lore raw
In reply to Daniel Walker

Another problem in plist_add:

Quoted 3 lines

existing_sp_head:

	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
	list_add(&pl->sp_node, &itr_pl2->sp_node);

This breaks fifo ordering.

Oleg.

#4 lore raw
Quoted 7 lines · Oleg Nesterov

Another problem in plist_add:

Quoted 3 lines

existing_sp_head:

	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
	list_add(&pl->sp_node, &itr_pl2->sp_node);

This breaks fifo ordering.

Daniel, is the issue (and other issues) Oleg noticed still present? I'm still a bit uneasy about the complexity of the plist changes.

Ingo

#5 lore raw
Quoted 5 lines · Ingo Molnar
Quoted 2 lines · Oleg Nesterov

Another problem in plist_add:

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

existing_sp_head:

	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
	list_add(&pl->sp_node, &itr_pl2->sp_node);

This breaks fifo ordering.

Daniel, is the issue (and other issues) Oleg noticed still present? I'm still a bit uneasy about the complexity of the plist changes.

I think this one isn't right. We could make a test quite to check correctness. Find the errors before they find us. Oleg may even have something like that already half done.

Are you concerned with plist as a whole, or just my recent changes?

There is still a problem with plist_for_each() missing the first list member, which I need to fix.

Daniel

#6 lore raw
Quoted 9 lines · Daniel Walker
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

existing_sp_head:

	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
	list_add(&pl->sp_node, &itr_pl2->sp_node);

This breaks fifo ordering.

Daniel, is the issue (and other issues) Oleg noticed still present? I'm still a bit uneasy about the complexity of the plist changes.

Quoted 8 lines

I think this one isn't right. We could make a test quite to check correctness. Find the errors before they find us. Oleg may even have something like that already half done.

Are you concerned with plist as a whole, or just my recent changes?

There is still a problem with plist_for_each() missing the first list member, which I need to fix.

plist seems pretty stable now, but i'm still worried about behavioral correctness. The previous method, while it didnt scale as well, was at least more obvious to review.

Ingo

#7 lore raw
Quoted 16 lines · Ingo Molnar
Quoted 13 lines · Daniel Walker
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

existing_sp_head:

	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
	list_add(&pl->sp_node, &itr_pl2->sp_node);

This breaks fifo ordering.

Daniel, is the issue (and other issues) Oleg noticed still present? I'm still a bit uneasy about the complexity of the plist changes.

I think this one isn't right. We could make a test quite to check correctness. Find the errors before they find us. Oleg may even have something like that already half done.

Quoted 8 lines
Quoted 4 lines

Are you concerned with plist as a whole, or just my recent changes?

There is still a problem with plist_for_each() missing the first list member, which I need to fix.

plist seems pretty stable now, but i'm still worried about behavioral correctness. The previous method, while it didnt scale as well, was at least more obvious to review.

True, list_add() vs. 200+ lines of code .. I've added our plist to fusyn with no ill effects. As Oleg suggested I used some userspace code to check what it was doing, while I was working on it. I've fairly confident in it, however I do still have some concerns for the same reasons you do.

I could do some cleanup on it, some comments are wrong now. That and a test suite, maybe that will change the confidence level.

Daniel

#8 lore raw
In reply to Daniel Walker
Quoted 9 lines · Daniel Walker
Quoted 6 lines · Ingo Molnar
Quoted 4 lines · Oleg Nesterov
Quoted 3 lines

existing_sp_head:
itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node); list_add(&pl->sp_node, &itr_pl2->sp_node);

Quoted 8 lines
Quoted 4 lines
Quoted 1 line

This breaks fifo ordering.

Daniel, is the issue (and other issues) Oleg noticed still present? I'm still a bit uneasy about the complexity of the plist changes.

I think this one isn't right. We could make a test quite to check correctness. Find the errors before they find us. Oleg may even have something like that already half done.

Ok, I'll do the testing...

int main(void)

{
	struct plist head, node[3], *pos;
	int i;

	plist_init(&head, INT_MAX);

	for (i = 0; i < 3; ++i) {
		plist_init(node + i, 0);
		plist_add(node + i, &head);
	}

	plist_for_each(pos, &head)
		printf("fifo? %d\n", pos - node);

	return 0;
}

output:

fifo? 2
fifo? 1
fifo? 0

Oleg.

#9 lore raw
Quoted 3 lines · Oleg Nesterov

fifo? 2
fifo? 1
fifo? 0

plist_for_each() wasn't designed to be FIFO , as you've discovered. That's the slow method , you should test the fast method via pulling the nodes off the front of the list.

Daniel

#10 lore raw
Quoted 10 lines · Daniel Walker
Quoted 3 lines · Oleg Nesterov

fifo? 2
fifo? 1
fifo? 0

plist_for_each() wasn't designed to be FIFO , as you've discovered. That's the slow method , you should test the fast method via pulling the nodes off the front of the list.

Sorry, I don't understand you. Could you please explain this to me?

Oleg.

#11 lore raw
Quoted 8 lines · Oleg Nesterov
Quoted 7 lines · Daniel Walker
Quoted 3 lines · Oleg Nesterov

fifo? 2
fifo? 1
fifo? 0

Quoted 5 lines
Quoted 3 lines

plist_for_each() wasn't designed to be FIFO , as you've discovered. That's the slow method , you should test the fast method via pulling the nodes off the front of the list.

Sorry, I don't understand you. Could you please explain this to me?

plist_for_each() was just created to walk through all the nodes in the list, There is no guaranteed ordering via that method. From your test it appeared to be working since you printed all the nodes you inserted.

There are other methods like plist_first() which will give you FIFO ordered nodes (or should) . The reason is that plist_first() pulls off the dp_node , which is the first node inserted at that priority. All the other nodes are inserted behind the dp_node. That's why I used list_add() and not list_add_tail()

In your case node "2" should have been the dp_node .

Daniel

#12 lore raw
Quoted 8 lines · Daniel Walker
Quoted 1 line · Oleg Nesterov

Sorry, I don't understand you. Could you please explain this to me?

plist_for_each() was just created to walk through all the nodes in the list, There is no guaranteed ordering via that method. From your test it appeared to be working since you printed all the nodes you inserted.

Yes, plist_for_each() without plist_entry() works.

Quoted 5 lines

There are other methods like plist_first() which will give you FIFO ordered nodes (or should) . The reason is that plist_first() pulls off the dp_node , which is the first node inserted at that priority. All the other nodes are inserted behind the dp_node. That's why I used list_add() and not list_add_tail()

So plist_for_each() works in reverse order, and the comment about fifo ordering applies only to plist_first(). Thanks for explanation.

I don't understand why you are doing it this way, though.

Oleg.

#13 lore raw
Quoted 4 lines · Oleg Nesterov

So plist_for_each() works in reverse order, and the comment about fifo ordering applies only to plist_first(). Thanks for explanation.

I don't understand why you are doing it this way, though.

It could be changed. I just did what was natural considering the old code.. It would be nice to reverse it though .

Daniel