From what I have understood so far about the Linux CFS is that scheduling entities are indexed by their virtual runtime (vruntime) inside the RB-tree.
The scheduler regularly updates this vruntime by calling the update_curr function which basically increase the vruntime value of the current running entity.
What I don't understand is how does the scheduler keeps the RB-tree always well ordered. The update_curr function increases the value of vruntime but does not seem to check whether the entity should be moved back into the right of RB-tree. Which function performs this check?
While Ahmed is right about update_curr, I was still confused about the fact the tree could be unbalanced between the moment vruntime is updated and the eventual call to resched_curr. As a matter of fact, it turns out that the task that is currently scheduled is not part of the tree.
It is removed from the tree in set_next_entity(cfs_rq_of(se), se); which is called when pick_next_task_fair is invoked. So the tree is always balanced and the only function performing the balancing are enqueue_entity and dequeue_entity