linux-kernel - Re: Question regarding put_prev

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20130618095533.GI3204@twins.programming.kicks-ass.net>
Date:	Tue, 18 Jun 2013 11:55:33 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Lei Wen <adrian.wenl@...il.com>
Cc:	linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...nel.org>
Subject: Re: Question regarding put_prev_task in preempted condition

On Sun, Jun 09, 2013 at 11:59:36PM +0800, Lei Wen wrote:
> Hi Peter,
> 
> While I am checking the preempt related code, I find a interesting part.
> That is when preempt_schedule is called, for its preempt_count be added
> PREEMPT_ACTIVE, so in __schedule() it could not be dequeued from rq
> by deactivate_task.
> 
> Thus in put_prev_task, which is called a little later in __schedule(), it
> would call put_prev_task_fair, which finally calls put_prev_entity.
> For current task is not dequeued from rq, so in this function, it would
> enqueue it again to the rq by __enqueue_entity.
> 
> Is there any reason to do like this, since entity already is over rq,
> why need to queue it again?

Because we keep the current running task outside of the actual queue
structure. This is because every time we update the runtime
(__update_curr) the key on which the tree is sorted (vruntime) is
changed and we'd need to dequeue + enqueue to keep the tree in sync.

By not having the actively running task in the tree we can avoid this;
at the cost of having to dequeue on switching to the task and enqueue
when switching from the task.

> And if current rq's vruntime distribution like below, and vruntime with 8
> is the task that would be get preempted. So in __enqueue_entity,
> its rb_left/rb_right would be set as NULL and reinserted into this RB tree.
> Then seems to me now, the entity with vruntime of 3 would be disappeared
> from the RB tree.
>             13
>            /  \
>          8    19
>         /  \
>       3    11
> 
> I am not sure whether I understand the whole process correctly...
> Would the example as above happen in our real life?

No, the RB tree code will ensure we'll not loose 3. I suppose you're
confused by rb_link_node() which does indeed clear the left and right
node of the entity we're about to link.

However, we link the previously unlinked entity as a leaf node. So your
example is flawed; before insertion the tree would look something like:

         13
	/  \
       11  19
      /
     3

Then the lookup in __enqueue_entity would find the place to insert 8 and
would select the right sibling of 3:

         13
	/  \
       11  19
      / 
     3  
      \
       (8)

We'd then link 8 as a child leaf of 3; which will indeed have NULL
leafs. rb_insert_color() will then fix up the tree so we conform to the
RB constraints. Please read lib/rbtree.c:__rb_insert() the code is quite
readable.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/