A look at the futex invocation tree

Futex implementation in Linux kernel is complex and prone to logical bugs. The worst of them is CVE-2014-3153. Since reversing and understanding the implementation can be difficult, I made the following tree which shows the major functions invocations and the major works done for each operation in order to help those interested understand the procedure better. Scroll horizontally to see the full tree.


sys_futex
    |
    \
     -> do_futex
            |
            |
            `---> futex_wait
                      |
                      |
                      |
                      `---> futex_wait_setup
                      |           |
                      |           |
                      |           |
                      |           `---> Calculate a unique futex key and the respective hash bucket
                      |           |
                      |           |
                      |           `---> Read futex value and check equality
                      |
                      |
                      `---> futex_wait_queue_me
                                    |
                                    |
                                    |
                                    `---> set_current_state and prepare to sleep
                                    |
                                    |
                                    `---> queue this task in the bucket 
                                    |
                                    |
                                    `---> schedule and sleep

sys_futex
    |
    \
     -> do_futex
            |
            |
            `---> futex_wake
                     |
                     |
                     |
                     `---> claculate the key and hash bucket
                     |
                     |
                     `---> iterate over the bucket and find correct waiters 
                                              |
                                              |   
                                              |
                                              `---> wake_futex
                                                        |
                                                        |
                                                        |
                                                        `---> get_task_struct : increment usage count of the task
                                                        |
                                                        |
                                                        `---> __unqueue_futex : remove from its bucket
                                                        |
                                                        |
                                                        `---> put_task_struct : decrement usage count
sys_futex
    |
    \
     -> do_futex
            |
            |
            `---> futex_lock_pi
                     |
                     |
                     |
                     `---> claculate the key and hash bucket
                     |
                     |
                     `---> futex_lock_pi_atomic
                     |            |
                     |            |
                     |            |
                     |            `---> first check if futex is free, if not
                     |            |
                     |            |
                     |            `---> set FUTEX_WAITERS bit
                     |            |
                     |            |
                     |            `---> lookup_pi_state
                     |                        |
                     |                        |
                     |                        |
                     |                        `---> find the first waiter 
                     |                        |     if found, get reference 
                     |                        |     to its pi_state, otherwise:
                     |                        |
                     |                        `---> alloc_pi_state
                     |                        |
                     |                        |
                     |                        `---> rt_mutex_init_proxy_locked: init mutex using pi_state
                     |                        |
                     |                        |
                     |                        `---> attach this pi_state to the owner of the mutex
                     |                        |     which is the owner of the futex
                     |                        |
                     |                        |
                     |                        `---> save the reference to pi_state
                     |                              int the futex_q object
                     |                              this makes the futex pi-aware
                     |
                     |
                     `---> queue_me
                     |
                     |
                     `---> rt_mutex_timed_lock      
                                   |
                                   |
                                   |
                                   `---> rt_mutex_slowlock (new rt_mutex_waiter on stack)
                                                |
                                                |
                                                |
                                                `---> try_to_take_rt_mutex : this fails and is used just in case
                                                |
                                                |
                                                `---> task_blocks_on_rt_mutex
                                                |               |
                                                |               |
                                                |               |
                                                |               `---> initialize waiter
                                                |               |
                                                |               |
                                                |               `---> add waiter to the mutex
                                                |               |
                                                |               |
                                                |               `---> attach the waiter to its task
                                                |               |
                                                |               |
                                                |               `---> __rt_mutex_adjust_prio: chain walk tasks and update priorities
                                                |               |
                                                |               |
                                                |               `---> rt_mutex_adjust_prio_chain
                                                |
                                                |
                                                `---> __rt_mutex_slowlock
                                                              |
                                                              |
                                                              |
                                                              `---> in a loop
                                                                       |
                                                                       |
                                                                       `---> try_to_take_rt_mutex
                                                                       |
                                                                       |
                                                                       `---> set current task
                                                                       |
                                                                       |
                                                                       `---> schedule


               
sys_futex
    |
    \
     -> do_futex
            |
            |
            `---> futex_unlock_pi                                            
                        |
                     |
                     |
                     `---> claculate the key and hash bucket
                     |
                     |
                     `---> check if the task is the futex owner
                     |
                     |
                     `---> iterate over the bucket to find the first waiter
                                            |
                                            |
                                            |
                                            `---> wake_futex_pi
                                                       |
                                                       |
                                                       |
                                                       `---> check if the futex is pi-aware
                                                       |
                                                       |
                                                       `---> find the next owner
                                                       |
                                                       |
                                                       `---> detach the mutex from previous owner
                                                       |
                                                       |
                                                       `---> attach the mutex to the new owner
                                                       |
                                                       |
                                                       `---> rt_mutex_unlock
                                                                   |
                                                                   |
                                                                   `---> rt_mutex_slowunlock
                                                                                 |
                                                                                 |
                                                                                 |
                                                                                 `---> wakeup_next_waiter
                                                                                 |            |
                                                                                 |            |
                                                                                 |            |
                                                                                 |            `---> remove top waiter from owner task
                                                                                 |            |
                                                                                 |            |
                                                                                 |            `---> wake_up_process : wake up top waiter                                   
                                                                                 |
                                                                                 |
                                                                                 `---> rt_mutex_adjust_prio : un-do priority boosting 
                                                            The waiter now wakes up and resume __rt_mutex_slow_lock
                                                            removes itslef from the mutex and attachs the new
                                                            top waiter to its pi_waiters list

sys_futex
    |
    \
     -> do_futex
            |
            |
            `---> futex_wait_requeue_pi (receive key1 and key2)
                           |
                           |
                           `---> new wrt_mutex_waiter on stack (CVE-2014-3153 golden key)
                           |
                           |
                           `---> make requeue_pi_key point to key2
                           |
                           |
                           `---> futex_wait_setup for key1
                           |
                           |
                           `---> futex_wait_queue_me
                                         |
                                         |
                                         `---> queue_me
                                         |
                                         |
                                         `---> schedule and wait for a requeue_pi operation 
                                               to be invoked

                                         
sys_futex
    |
    \
     -> do_futex
            |
            |
            `---> futex_requeue (receive key1 and key2) 
                       |
                       |
                       |
                       `---> calculate keys and hashbukets for both key1 and key2
                       |
                       |
                       |
                       `---> if the operation is non-pi
                       |                |
                       |                |
                       |                |
                       |                `---> iterate over futex1
                       |                |     wake the requested number
                       |                |     of waiters
                       |                |
                       |                `---> requeue_futex: requeue the requested number of remained
                       |                      waiters to futex2
                       |
                       `---> otherwise
                                |
                                |
                                `---> futex_proxy_trylock_atomic : try to wake up the top waiter
                                |                              |
                                |                              |
                                |                              |
                                |                              `---> futex_lock_pi_atomic : try to take the futex 
                                |                                                     |
                                |                                                     |
                                |                                                     `---> requeue_pi_wake_futex : wake up the top waiter
                                |
                                |
                                `---> iterate over futex1 and find correct waiters
                                                        |
                                                        |
                                                        |
                                                        `---> check each requeue_pi_key
                                                        |
                                                        |
                                                        |
                                                        `---> rt_mutex_start_proxy_lock
                                                                        |
                                                                        |
                                                                        |
                                                                        `---> try_to_take_rt_mutex
                                                                        |
                                                                        |
                                                                        `---> task_blocks_on_rt_mutex
                                                                        |
                                                                        |
                                                                        `---> requeue_futex : requeue the requested number of 
                                                                              waiters to futex2                           
                                                                                        
                                                           
                           

Leave a Reply

Your email address will not be published. Required fields are marked *