From ba886cd4ac957608777fbc8d137f6b9f0450e775 Mon Sep 17 00:00:00 2001 From: Bob Moore Date: Thu, 10 Apr 2008 19:06:37 +0400 Subject: ACPICA: Update for mutiple global lock acquisitions by same thread Allows AcpiAcquireGlobalLock external interface to be called multiple times by the same thread. Allows use of AML fields that require the global lock while the running AML is already holding the global lock. Signed-off-by: Bob Moore Signed-off-by: Alexey Starikovskiy Signed-off-by: Len Brown --- drivers/acpi/utilities/utdelete.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'drivers/acpi/utilities/utdelete.c') diff --git a/drivers/acpi/utilities/utdelete.c b/drivers/acpi/utilities/utdelete.c index f777cebdc46d..dcb34f805714 100644 --- a/drivers/acpi/utilities/utdelete.c +++ b/drivers/acpi/utilities/utdelete.c @@ -158,7 +158,7 @@ static void acpi_ut_delete_internal_obj(union acpi_operand_object *object) "***** Mutex %p, OS Mutex %p\n", object, object->mutex.os_mutex)); - if (object->mutex.os_mutex == acpi_gbl_global_lock_mutex) { + if (object == acpi_gbl_global_lock_mutex) { /* Global Lock has extra semaphore */ -- cgit v1.2.2 option> The LITMUS^RT kernel.Bjoern Brandenburg
aboutsummaryrefslogblamecommitdiffstats
blob: 5530ed211f72f9ef1ceed453cf6fdcca07da27d3 (plain) (tree)




























                                                                          
                             

                              
                              


                           
                          
                          












                           
                              
                          
                            




                       









                                                               

























































































                                                                        

                                                                          










                                                                  
                             
                                                                       
 
                                                          
 

                                                                  
            
                                                              
 
 








                                                                
                                                                



                                                     



                                          

                               
                                                                             









                                                                  
           






                                                                          
                                        
                 
                                  











                                                                     

                                                        
                                        
                                   
                                  
                                                       








                                  
                                                          
 
                                             





















                                         
                                          

  
                                            
 








                                       

                                                                             
                                                             



                                                              

                                                                                





                                                            
                           






                                                        
                                                                    



                             
                                                                               


 
                                                                              
 



                                                                          






                                                                    



                                      
                                                                    







                             
                                                                               















                                                                      
                                                                              











                                                                              
      

                                       

  


                                                              
                                                              

                            
                      











                                         



                                                                           
                                                                           

                            
                      











                                                          
                                                  




                               
                                                                      









                                                                             
                            







                                                           
                                            


















                                                                            
                                  







                                                                         

                                                                               






                                                             
                                                           
                         

                                                                              
                                                                        

                                                                          

                                                                       
                 
                                 























                                                                     
                                                          





                                  




















                                                                


                                                                              





                                                                




                                                        
                                                            
   
                                           

                            
                      







                             
                                                                 














                                                                          
                                                             








                                                                     
                                                    
 
                                                       

                                      
                                                                
                               
                                                 


                                         
                                                        
















                                                                           
                                                           
 


                                                            





                                                                        
                                                           
 
                                                                           
 

                                                        






                                                                           
                  
                                                                       
 
                                      











                                                                    





                                                                     


                                                        
                                                        



                                                   
                                                                         






                                                    
                                                                         











                                                                      
                                                                         



                                                             

                                                                  







                                                       
                                                                  











                                                                
 
                                                      


                        










                                                 




















                                                                             
                                                  
 
                               














                                                                               
                  
                                                                 



                                                
                  
                                                                 



                                                
                                                                       




                                     
                                                                       





                                     





                                                         
                                                    
















                                                        
                                                












                                                                  

                                                 
                                                                 
 
                                               
 
                          

                                     
                              




                                                                    
                                                                             

                                         
                              

 



                                                             
                                                                          

                                                             
                                                      
 
                          
                               


                                     


                                                                              
                   
                                                             
 















                                                                              

                          



                                                                      
                                                                             
                                                            

                                                                     


                                                                       












                                                                               
                 

                                                        

         
                                 







                                                                            
                                                                          


                               


                         



                                                         
                                               

                                                            


         










                                                                            
                                           




                                                                    
                                            







                                                                            
                                                          




                                                                          
                                                          


                           
    





                                                     
                                                                 
 
                              











                                                                   




                                                                     
                                               
 
                


                                              



                                                                
 



                                      
                                                                 
                 
                               
                                         

     
                                                      
 
                                              







                                                         
                                                 



                                          





                                                            
                 
                      
                              
 
                                 

                     
                               
  




                                                         
          
                                                                            
 
                                   










                                                                   


                                                   
 











                                                                        
                                              

                            
                      





























                                                                        
                                        










                                                        

                                                                    



                                                              
                                                          
 
                                    
 
                      
                                             
 
                                                                


  

                                                                     
   
                                                          
 
                                    
 
                      
                                             
 







                                                                
                                    

                                         
                                                                

 
















                                                                               



                                                                      
                                                                  























                                                                            
          








                                                          
                                                                 
   

                                                                               
 
                      



                                                 



                                                       
                                           









                                                                             














                                                                            
 
                                   




                                                                              

                                      
         



                                          





                                          


                                                      



                                       
 
                                                         




                                                                              
 
                                                                          
                              














                                                              









                                                              
                                                    









                                               
                                                                 




                                                   

                              



                   
                                                           


















                                                                   
                                                                              



                                       
                      
                 
                                                 
                                      

















                                          

                      


                                              







                                                            

                 
 
                                                            

                                 
          
                                                                       
           


                                            
 

                                                                     

                                                       
 

                                                                    

                                                      


                                                                      
 
                          


                                                                              
                           
                                 
                                                           

                                          

                                                                              


















                                                                          




























                                                                            
                                                     
              

          
                                                                   

                                                               
           




                                                             
          






                                                                       













                                               
                                                   



                                                                               

                               
                                                                     



                                           
                                                                    



                                                                
                                                                
 






                                                       






                                                                        





                                                                      

                                     


                                                                 
      
                                                              

                     
                     
                                                            
                                               





















                                                                           
                                                        


                           








                                                                        
                                                                                
 
                                

                            

                                     
                                         
                                      
                          
 





















                                                                               
                                                                      


                                                                                
                                                      


















                                                                         

                                                                              
























                                                                      
                                               

                            
                      





                                                               
                                                                        











                                                                        










                                                                      
                                                                               





                                      
                                                    
                                            

                                                



                                                                           





                                                                       
                                                                              

                            
                                           
                        




                                                                    
                                                                         

                                                                           
                                                                         




                                                                            
                                 

                                     

                           
                                                




                                                                              
                                      
         





                                                                 
                                                       

                            

                                  




                                                                           







                                                               
                                  
                                                       
                                        



                                                  






                                                                     
                  





                                             
                        



                                       






                                                                
                                                      
      



























                                                                      
                                













                                                                    

                                   
 
                                








                                              
                                




                                                          














                                                                 


                 








                                                                                




                                                           
                                                          


                             
                                 



                                                            
                                














                                                             
                                                            












                                                                              
                                                                       



                                 




                                                               
                                                      
                                        








                                                    




                                                                   
                                                                   
 
                                 
                            
                      









                                                                               
 




                                               
 






                                   

                                                                             


                     
                                          
                                                                
                  

                                                     





                                                                        


                                                                      

                                   
                                  
                                  
                                   
                                    

                                                                     










                                                                          
      
                                                                        

                                                                  






                                                                    

                                                  



                                


                                   
                                    


                                                    




                                                               
                         
         
 
                                                       
                         


                 
                                                                       
 
  


                                                                              


                                     
                                                                           


                                                                             
 

                                                                   
                                             
                                      
                                
                           
 
                                                   

                         
                                      
                   
                                               
                                          


                                                                        
                                                                  


                                                                          
                                                          
 

































                                                                              
                                                             


                          




                                                                             

                                                         
                                                                    
                            
                                                                           

                                                   





                                        

                                                                     
                                          
 




                                                                     

                                             











                                                                      


                                     




                                                                        

                                                                      


                                                         
                                                                               
                                                 


                                                                              
                               

                                                                
                     





                                                                   

                                                          

                                                       





                                           

            
                                                   

                                
                                                                  
                                                                


                                                                  


                                                                
                                                                
                                                                  

                                                      





                                                 
 


                                                     
                                                                      





                                                                     
                                                                
                              
                                                                

                                         

                                                                   

                 









                                                                               





                                                                            

                                                                     


                                             


                                                               
                                                             

                                            

                                                                  
                 












































                                                                               
                                                           






                                                                   
                 

           


                                      
                                                                         







                                                                    
                                                    










                                                                               











                                                                            

                                                                         
                                                                              
 
                                                                      
                                                       


                                                                         






                                                                           
                                                     










                                                                       
 

                                                                           








                                                                              



                                                             


                                                  

                                                                
                                   

                                                                           

                                             


                                                                              
                    



                                                                        





                                                
                                                   

         


                       


                                                                       
 



                                                                
      
    






                                                                          
                  
                                                                  
                                                            
 
                                       
                                   


                                              



                                         
                               
 
                                                                             
                                 
 


                                                         






                       




                                                                        




                                                            
  

                                                                         
   
                                                         

                                                                     
 
                                                                      
                                  
                                
                           
                                      
                            
 





                                                                                
                                                                
                                                         
                            
 

                                        

                                                                            

                                                   
                          
                                  
 




                                                    
                                                                    




                                                    
                                   










                                                                          
                                      
                                                 
                                                                 

                                                                           
                                                   
                                         

                                                                            



                                                         
                                          
                 
         
 




                                                                               
 
                                                                 




                                                                                
                                                                              



                                                    


                                                             
                                                   
                         
                                                                      
                                           





                                                                           
                                                                       
                 
              

                                          
                                      

                                                                         








                                                                             

         
                                                                     
                                                         
                          


                        

                                             
                                  

               
                                            

                                                                         

                                          
                                                        
                                                         
                          









                                                                          
          
                                                                               

                                  
                                  

                                
                        
                                      
 







                                                                                
                            

                                              

                                                                        
                                                          
                     
                                                          
                                  

         

                                                                  
                       
                                                          
                                  

         

                                   
                                                               





                                                                 
                                                                             
                                                                         
                                            





                                                         

         
                        
                                                         

                                                                 

                                  
                                          
 
                        


                                                   
                                                        
                                                         
                          
                                  
 
                 





                                                                      
                                                          

                                

                                                        


                                                     
                                                                        






                                                                           
                                      

                 





                                                                      









                                                                           
                                                                       
 
                                              

                                
 
                                        
                                        


                                       

          


                                                       
           
                                        
 



                                                              
                                         
                                                    
                                                     
                                      
         
 

                                           
 






                                                                          
                                      

 
                                           
 
                                
                              
 
                                               

                              
                                                            

                                                 

                                                                                
                                                
                                     






                                                                              
                                                                            
         


  
                                                                          





                                                                       
                                  
 
                                                           
 
                                                       
                                              

                                





                                                              

                                                                            

                                       











                                                      




                                                      
                                                                          
                                                                                  

                                                                             


                                                                             

                                                
                                                   
                 


                                                

                                                                          







                                                                            
         
                                             




                                                
                                                       



      







                                                                      
                  
                                                                              
 

                                                      





                                                                 
                                                                  


                              
 
                              
                                                         
                                 
 



                  








                                                                       
                                                 








                                                                                

  





























                                                                     
                                  

















                                                                        










                                                                 
                                  










                                                                              
                                                                   
 
                                     
                                                                
                                        
                       
































                                                                        
                                                                   
































                                                                              














                                                                   


                                     
                          
                                         
                 
                        

                                                     
      

 






                                                            

                                                       



                                           

                                                               







                                        

                                                       


                                                



                                                           





                                 





                                                               




                                             
                                        
                                 


                                
                               
                           
                      





                                                                       



                                                                      
                                               

                                                       
                             




















                                                                           
                                                                            
                                                 
                                                                     











                                                                           














                                                                  



                                                  

                                          
















                                                        
                                                                     
 
                                                                    
                                                                 
                                                                     

                                  
                                                          


                                                                               





                                                                           
                 
         
                                        



                                                
                             











                                               
                                                       



                                  
                                              

                                                      





                                                                              









                                                         



                        
                                                                  













                                                                           
                                                         























                                                                             


                                
                                                               










                                                                     
                                                  




























                                                                             

                                                                      
 
                                                         
 
















                                                                               


                                                                              
                                                        
                                                                               








                                                                   
                                                  

                                                                
                                                    






                                                        










                                                                            
                                                           










                                                                      

                                                                         










































                                                                             
 















































































































































                                                                            

                                      

                                                                  










                                            











                                                    
















                                                                          











                                                                     
                                                      
 
                                 
                            
                      



































                                                                                
                                                    
 
                                 
                            
                            
                      











                                                                           
                                        
           
                               



                                                    
                    
                                       

                                             
 
                                            
                           


                                    


                                       
                                             









                                                                       

                             




                                                       
                                                         
 

                                                                      
 



                                                                     










                                                                   
                          





                                                                     

                                








                                                              


                                                      

















                                                         
                                          







                                                     
                                          


                            
                             









                                                  



                                                    
                                      







                                                                  
                                                                







                                                                       
 

                              







                                                               
                           


   
                                                                                    


                                                    
  
                                          
   

                                                         
 
                                            
                                 
                            
                      
 

                                                   




                                                              

                                                                        

                                                           

                                                                     

                                        
                                                                    
                                                              
                               
                                                                 

                               



                                                            

















                                                                              
 




                                                          




                                                              




                                                                 


                                                                
                               


                                                                  

                                                           



















                                                                                


                                                   

                              



                                      

                                                                              
 

                                  
                   




                                                                       


                        
                                     


                                                                
 











                                                                           



                                                      


















                                                                               
                              
                             

























                                                                               
                              
                             































                                                                         
                               

                              























                                                                      



                                                        














































                                                                               
                                        


                               
                                                      

                              
                                                        
                                



                                                  
                              
                   








                                     



                                               
                                                         





































                                                                          
                                                                    




                                                                      

                                                                         











                                                                     
                                    



















                                                                       
                                                      







                                    
                                
 


                                          




                                                             








                                                  

                                                                         




                                 









                                                                               
                                       
 

                    


                                   
                        

                                
                                                               
                                                           


                                            
                        
                                
         
                   
 





                                      
                                                               


                                        





                                   

                                    


                                                        
                                                              






                                               










                                                                            
                                                      
 
                                


                                   
                              
 



                                              
                                                      

                 
                                


                                        
                              



















                                                                
                         






















                                                                
                         















                                                                           
                              

                             













                                               
                                                     









                                                                     
                                         

                                            
 
                               
                       
 
                                                   

                                                                      












                                                       
                                                   

                            
                                                                         

         
                                                             








                                     
                                                  
 
                                  


                         

                                                                                    

                   

                                                                                            







                                                                     
                                                               
                                     

                                  

                                         
                                    




                                                   

 







                                                                  
                                                           
 
                                    

                            
                                        

                            
                                                  





                                                 


                                                              



                                                            
                                                                        
     
                                                  















                                                             
                                                                   




















                                                                     
                                                               
 
                                 
                            
                      
                    





















                                                                           
 

                   









                                                                     

                                                      
   
                                                                           
 
                                    
                    

                                               
                           



















                                                                      

                                                                           
                                           
                                            


                                                    
                

                                          
                   






                                                                    
                                       
 
                             
                      





                                                
                                          
                                       
 
                                




















                                                              
                                                                         

                                          


                                                              

















                                                      



                                                                        
                                                                       
 
                            
                       

                      
 
        

                                                      
                                              



                                        
                                                           


                                   


                                                           
                                           





                                                                  
                                                

                                                              
                                                          
         
                                                   
                             








                                                                        
                                                         
 
                                                                  












                                                                  
                                  


                                       

                                 

                                 


                                                           





                                                                           
                                                         


                          
                                          
                                         



                                         
                                     
 


                                                                           



                                                     

                                                                 




                                                 

                                                                        












                                                  
                                                    
                                                                      
 
                                         

                                                              
                                                                           

                                                                       
                                      
 
                           




                                                                        
                                                           
           
                               
                                            
                             
 
                           




                                                                             
                                         
                            



                                                                           
 
                                                 

                                                                             








                                                                       

                                                                            
 
                              
                             
                            
                      













                                                                               
 



                                                                        
 

                             

                                                   
                                                                           

                                                             


                                                            
 



















                                                                       

                                                  
                                                                  
                                                                     












                                                                          
                                                                 






                                                     
                

                                         

                                                                       

                                                             
 




                 




                                       
                         




                                                                




                                                                               


















                                                                  

                                                                                





                                              

                                                                               
                                                    

                                                                                













                                                                          

                                                                               





















                                                                          

                                                                   


                                

                                 
 


                                                                               



                     
                                                     

      
                                                 







                                                    


                                                   












                                                   

                                                                          

















                                                                        


                                                        






                             



                                                                    
                                                               
 
                                    






                                                                             
                                                        
                                                     


                                                            

         
                                      
                                


                                         


                                    
                                       


                                
                                                  
















                                                            



                                                                           




                                                                            
           


                                                                          





                                                       

                                                      








                                            
                                                                













                                                
                              
 



























                                                                              
                                 
















                                                                   











                                                                


































































































                                                                              


                                                   

















                                                                          

                                                                    























































































                                                                     
                                                                         


                                             
                                                                         








                                                                
                                                                         


                                             
                                                                         



                                                

                                      




































                                                                              
                                                                                
                                                                       






















                                                                        

                                                                             






















                                                                              
                                                       
                   
                                     



































































                                                                           





                                                                             
                 
                             
         

                            
                                                                 













                                                              
                  
 


















































                                                                            
                                                 

                                 









                                                                      
 







                                                      
                                                            
 
  
                     
   

                                                        
                                                            
 

                                                              
 

                                                      



                   


                            

                                                         
                                                            


                                                         

                                                               
 
                  

                                              



                                                        

                              

                                                               
 

                                                      



                   
                                                         
                                                            
 

                                                               
 
                  
                      
                                                
                                       
                                
                               

                                              
                                
     
                    
      


                                                        


                  
  


                                                                          
   
                                                         
                                                             
 
                                                             
                                                                
 

                                                                   
 








                                                               
 
 

























                                                                        

      
                  


                                                              
                   

                                          


                                                       























                                                                              
 




                                                       
 
  



















































                                                                               

                                                                           
   
                                                        

              
                                

                                                      
                            



                                                     
                                                                             
                                                       

                                                                             
                               


                                                                         

          
                                                            
           
                                        


                                                                     
                                                       

                  
                                         



                                                                              
                                                                       
                               
                                        


                                 
                                               
                                   

                                                                  

                                      
                                                       



                                               


                                    

                                      
                                                           
 


                                               



                                                       
                              
                                                           

      


                                              

                                              
                                                       
                               
                              
                                                          




                                         
                                        
                                                                
                                                                       


                                                     
                                                                                      


         






                                                                 
                                                                                    



         



                                                        
                                                       


                                         
                                                                               



                                

                                                                                   









                                                        

                                                    
                                 
                 



                                                           
                                                                             




                                                                             




                                                       


                                       
                              

















                                                             

                                                                     


                                                                               
                                           


                                          
                                              



                                                       
         


                                                                 
                       
                                        
                                              
                                               
         
      
                      
                                        
                                               
                                               

         
 
                                        
                                               
                                               

         
                  

                                                                   
 

                                       
 
                                                                         

                                                 

      
                                
                                        


                                              

                                               




                                               



                                           


                 
                  


                                   
      
 


                                                                            
                                                            

                                  
                
 






                                                                            


                                                    


                                                                
 
                                   
 
 



                                                                 
                                                            
















                                                               
                                                                         

                             
                    







                                                                




                                                      

 
































                                                                                
 


















                                                                              

                                                                          











                                                                               

                                                                           






                                                                        


                                                                          
                                                                     




                                                                           


                              
                                                        














                                                                 
                                                 


                         


                                

                                    
                           
                                                 
                                                                           

                                                               


                                                                    



                                                             










                                                                   
 






                                                           
                    
                            
 
                                  

                                         


                                          
                                                               
                                   




                                                 
                              

                                            

                                       
                            













                                                                 
                                

         
                                    
 
                 
                                     


                                                                 



                                                                   

















                                                                            
                






                                                                        
                                                                            


                                                                   
                                               

                                                       









                             
                                 
                              
                            
                      

                                      
                             


                                 

                                                      









                                                       

                                                           




                                        

















                                                               
                                      


















                                                                               
                                                  




                          
/*
 *  kernel/sched.c
 *
 *  Kernel scheduler and related syscalls
 *
 *  Copyright (C) 1991-2002  Linus Torvalds
 *
 *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and
 *		make semaphores SMP safe
 *  1998-11-19	Implemented schedule_timeout() and related stuff
 *		by Andrea Arcangeli
 *  2002-01-04	New ultra-scalable O(1) scheduler by Ingo Molnar:
 *		hybrid priority-list and round-robin design with
 *		an array-switch method of distributing timeslices
 *		and per-CPU runqueues.  Cleanups and useful suggestions
 *		by Davide Libenzi, preemptible kernel bits by Robert Love.
 *  2003-09-03	Interactivity tuning by Con Kolivas.
 *  2004-04-02	Scheduler domains code by Nick Piggin
 */

#include <linux/mm.h>
#include <linux/module.h>
#include <linux/nmi.h>
#include <linux/init.h>
#include <asm/uaccess.h>
#include <linux/highmem.h>
#include <linux/smp_lock.h>
#include <asm/mmu_context.h>
#include <linux/interrupt.h>
#include <linux/capability.h>
#include <linux/completion.h>
#include <linux/kernel_stat.h>
#include <linux/debug_locks.h>
#include <linux/security.h>
#include <linux/notifier.h>
#include <linux/profile.h>
#include <linux/freezer.h>
#include <linux/vmalloc.h>
#include <linux/blkdev.h>
#include <linux/delay.h>
#include <linux/smp.h>
#include <linux/threads.h>
#include <linux/timer.h>
#include <linux/rcupdate.h>
#include <linux/cpu.h>
#include <linux/cpuset.h>
#include <linux/percpu.h>
#include <linux/kthread.h>
#include <linux/seq_file.h>
#include <linux/syscalls.h>
#include <linux/times.h>
#include <linux/tsacct_kern.h>
#include <linux/kprobes.h>
#include <linux/delayacct.h>
#include <asm/tlb.h>

#include <asm/unistd.h>

/*
 * Scheduler clock - returns current time in nanosec units.
 * This is default implementation.
 * Architectures and sub-architectures can override this.
 */
unsigned long long __attribute__((weak)) sched_clock(void)
{
	return (unsigned long long)jiffies * (1000000000 / HZ);
}

/*
 * Convert user-nice values [ -20 ... 0 ... 19 ]
 * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
 * and back.
 */
#define NICE_TO_PRIO(nice)	(MAX_RT_PRIO + (nice) + 20)
#define PRIO_TO_NICE(prio)	((prio) - MAX_RT_PRIO - 20)
#define TASK_NICE(p)		PRIO_TO_NICE((p)->static_prio)

/*
 * 'User priority' is the nice value converted to something we
 * can work with better when scaling various scheduler parameters,
 * it's a [ 0 ... 39 ] range.
 */
#define USER_PRIO(p)		((p)-MAX_RT_PRIO)
#define TASK_USER_PRIO(p)	USER_PRIO((p)->static_prio)
#define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO))

/*
 * Some helpers for converting nanosecond timing to jiffy resolution
 */
#define NS_TO_JIFFIES(TIME)	((TIME) / (1000000000 / HZ))
#define JIFFIES_TO_NS(TIME)	((TIME) * (1000000000 / HZ))

/*
 * These are the 'tuning knobs' of the scheduler:
 *
 * Minimum timeslice is 5 msecs (or 1 jiffy, whichever is larger),
 * default timeslice is 100 msecs, maximum timeslice is 800 msecs.
 * Timeslices get refilled after they expire.
 */
#define MIN_TIMESLICE		max(5 * HZ / 1000, 1)
#define DEF_TIMESLICE		(100 * HZ / 1000)
#define ON_RUNQUEUE_WEIGHT	 30
#define CHILD_PENALTY		 95
#define PARENT_PENALTY		100
#define EXIT_WEIGHT		  3
#define PRIO_BONUS_RATIO	 25
#define MAX_BONUS		(MAX_USER_PRIO * PRIO_BONUS_RATIO / 100)
#define INTERACTIVE_DELTA	  2
#define MAX_SLEEP_AVG		(DEF_TIMESLICE * MAX_BONUS)
#define STARVATION_LIMIT	(MAX_SLEEP_AVG)
#define NS_MAX_SLEEP_AVG	(JIFFIES_TO_NS(MAX_SLEEP_AVG))

/*
 * If a task is 'interactive' then we reinsert it in the active
 * array after it has expired its current timeslice. (it will not
 * continue to run immediately, it will still roundrobin with
 * other interactive tasks.)
 *
 * This part scales the interactivity limit depending on niceness.
 *
 * We scale it linearly, offset by the INTERACTIVE_DELTA delta.
 * Here are a few examples of different nice levels:
 *
 *  TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
 *  TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
 *  TASK_INTERACTIVE(  0): [1,1,1,1,0,0,0,0,0,0,0]
 *  TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
 *  TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]
 *
 * (the X axis represents the possible -5 ... 0 ... +5 dynamic
 *  priority range a task can explore, a value of '1' means the
 *  task is rated interactive.)
 *
 * Ie. nice +19 tasks can never get 'interactive' enough to be
 * reinserted into the active array. And only heavily CPU-hog nice -20
 * tasks will be expired. Default nice 0 tasks are somewhere between,
 * it takes some effort for them to get interactive, but it's not
 * too hard.
 */

#define CURRENT_BONUS(p) \
	(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
		MAX_SLEEP_AVG)

#define GRANULARITY	(10 * HZ / 1000 ? : 1)

#ifdef CONFIG_SMP
#define TIMESLICE_GRANULARITY(p)	(GRANULARITY * \
		(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)) * \
			num_online_cpus())
#else
#define TIMESLICE_GRANULARITY(p)	(GRANULARITY * \
		(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)))
#endif

#define SCALE(v1,v1_max,v2_max) \
	(v1) * (v2_max) / (v1_max)

#define DELTA(p) \
	(SCALE(TASK_NICE(p) + 20, 40, MAX_BONUS) - 20 * MAX_BONUS / 40 + \
		INTERACTIVE_DELTA)

#define TASK_INTERACTIVE(p) \
	((p)->prio <= (p)->static_prio - DELTA(p))

#define INTERACTIVE_SLEEP(p) \
	(JIFFIES_TO_NS(MAX_SLEEP_AVG * \
		(MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))

#define TASK_PREEMPTS_CURR(p, rq) \
	((p)->prio < (rq)->curr->prio)

#define SCALE_PRIO(x, prio) \
	max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE)

static unsigned int static_prio_timeslice(int static_prio)
{
	if (static_prio < NICE_TO_PRIO(0))
		return SCALE_PRIO(DEF_TIMESLICE * 4, static_prio);
	else
		return SCALE_PRIO(DEF_TIMESLICE, static_prio);
}

/*
 * task_timeslice() scales user-nice values [ -20 ... 0 ... 19 ]
 * to time slice values: [800ms ... 100ms ... 5ms]
 *
 * The higher a thread's priority, the bigger timeslices
 * it gets during one round of execution. But even the lowest
 * priority thread gets MIN_TIMESLICE worth of execution time.
 */

static inline unsigned int task_timeslice(struct task_struct *p)
{
	return static_prio_timeslice(p->static_prio);
}

/*
 * These are the runqueue data structures:
 */

struct prio_array {
	unsigned int nr_active;
	DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
	struct list_head queue[MAX_PRIO];
};

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the thread migration code), lock
 * acquire operations must be ordered by ascending &runqueue.
 */
struct rq {
	spinlock_t lock;

	/*
	 * nr_running and cpu_load should be in the same cacheline because
	 * remote CPUs use both these fields when doing load calculation.
	 */
	unsigned long nr_running;
	unsigned long raw_weighted_load;
#ifdef CONFIG_SMP
	unsigned long cpu_load[3];
#endif
	unsigned long long nr_switches;

	/*
	 * This is part of a global counter where only the total sum
	 * over all CPUs matters. A task can increase this counter on
	 * one CPU and if it got migrated afterwards it may decrease
	 * it on another CPU. Always updated under the runqueue lock:
	 */
	unsigned long nr_uninterruptible;

	unsigned long expired_timestamp;
	/* Cached timestamp set by update_cpu_clock() */
	unsigned long long most_recent_timestamp;
	struct task_struct *curr, *idle;
	unsigned long next_balance;
	struct mm_struct *prev_mm;
	struct prio_array *active, *expired, arrays[2];
	int best_expired_prio;
	atomic_t nr_iowait;

#ifdef CONFIG_SMP
	struct sched_domain *sd;

	/* For active balancing */
	int active_balance;
	int push_cpu;
	int cpu;		/* cpu of this runqueue */

	struct task_struct *migration_thread;
	struct list_head migration_queue;
#endif

#ifdef CONFIG_SCHEDSTATS
	/* latency stats */
	struct sched_info rq_sched_info;

	/* sys_sched_yield() stats */
	unsigned long yld_exp_empty;
	unsigned long yld_act_empty;
	unsigned long yld_both_empty;
	unsigned long yld_cnt;

	/* schedule() stats */
	unsigned long sched_switch;
	unsigned long sched_cnt;
	unsigned long sched_goidle;

	/* try_to_wake_up() stats */
	unsigned long ttwu_cnt;
	unsigned long ttwu_local;
#endif
	struct lock_class_key rq_lock_key;
};

static DEFINE_PER_CPU(struct rq, runqueues);

static inline int cpu_of(struct rq *rq)
{
#ifdef CONFIG_SMP
	return rq->cpu;
#else
	return 0;
#endif
}

/*
 * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
 * See detach_destroy_domains: synchronize_sched for details.
 *
 * The domain tree of any CPU may only be accessed from within
 * preempt-disabled sections.
 */
#define for_each_domain(cpu, __sd) \
	for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)

#define cpu_rq(cpu)		(&per_cpu(runqueues, (cpu)))
#define this_rq()		(&__get_cpu_var(runqueues))
#define task_rq(p)		cpu_rq(task_cpu(p))
#define cpu_curr(cpu)		(cpu_rq(cpu)->curr)

#ifndef prepare_arch_switch
# define prepare_arch_switch(next)	do { } while (0)
#endif
#ifndef finish_arch_switch
# define finish_arch_switch(prev)	do { } while (0)
#endif

#ifndef __ARCH_WANT_UNLOCKED_CTXSW
static inline int task_running(struct rq *rq, struct task_struct *p)
{
	return rq->curr == p;
}

static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
{
}

static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
{
#ifdef CONFIG_DEBUG_SPINLOCK
	/* this is a valid case when another task releases the spinlock */
	rq->lock.owner = current;
#endif
	/*
	 * If we are tracking spinlock dependencies then we have to
	 * fix up the runqueue lock - which gets 'carried over' from
	 * prev into current:
	 */
	spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_);

	spin_unlock_irq(&rq->lock);
}

#else /* __ARCH_WANT_UNLOCKED_CTXSW */
static inline int task_running(struct rq *rq, struct task_struct *p)
{
#ifdef CONFIG_SMP
	return p->oncpu;
#else
	return rq->curr == p;
#endif
}

static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
{
#ifdef CONFIG_SMP
	/*
	 * We can optimise this out completely for !SMP, because the
	 * SMP rebalancing from interrupt is the only thing that cares
	 * here.
	 */
	next->oncpu = 1;
#endif
#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
	spin_unlock_irq(&rq->lock);
#else
	spin_unlock(&rq->lock);
#endif
}

static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
{
#ifdef CONFIG_SMP
	/*
	 * After ->oncpu is cleared, the task can be moved to a different CPU.
	 * We must ensure this doesn't happen until the switch is completely
	 * finished.
	 */
	smp_wmb();
	prev->oncpu = 0;
#endif
#ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW
	local_irq_enable();
#endif
}
#endif /* __ARCH_WANT_UNLOCKED_CTXSW */

/*
 * __task_rq_lock - lock the runqueue a given task resides on.
 * Must be called interrupts disabled.
 */
static inline struct rq *__task_rq_lock(struct task_struct *p)
	__acquires(rq->lock)
{
	struct rq *rq;

repeat_lock_task:
	rq = task_rq(p);
	spin_lock(&rq->lock);
	if (unlikely(rq != task_rq(p))) {
		spin_unlock(&rq->lock);
		goto repeat_lock_task;
	}
	return rq;
}

/*
 * task_rq_lock - lock the runqueue a given task resides on and disable
 * interrupts.  Note the ordering: we can safely lookup the task_rq without
 * explicitly disabling preemption.
 */
static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
	__acquires(rq->lock)
{
	struct rq *rq;

repeat_lock_task:
	local_irq_save(*flags);
	rq = task_rq(p);
	spin_lock(&rq->lock);
	if (unlikely(rq != task_rq(p))) {
		spin_unlock_irqrestore(&rq->lock, *flags);
		goto repeat_lock_task;
	}
	return rq;
}

static inline void __task_rq_unlock(struct rq *rq)
	__releases(rq->lock)
{
	spin_unlock(&rq->lock);
}

static inline void task_rq_unlock(struct rq *rq, unsigned long *flags)
	__releases(rq->lock)
{
	spin_unlock_irqrestore(&rq->lock, *flags);
}

#ifdef CONFIG_SCHEDSTATS
/*
 * bump this up when changing the output format or the meaning of an existing
 * format, so that tools can adapt (or abort)
 */
#define SCHEDSTAT_VERSION 14

static int show_schedstat(struct seq_file *seq, void *v)
{
	int cpu;

	seq_printf(seq, "version %d\n", SCHEDSTAT_VERSION);
	seq_printf(seq, "timestamp %lu\n", jiffies);
	for_each_online_cpu(cpu) {
		struct rq *rq = cpu_rq(cpu);
#ifdef CONFIG_SMP
		struct sched_domain *sd;
		int dcnt = 0;
#endif

		/* runqueue-specific stats */
		seq_printf(seq,
		    "cpu%d %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu",
		    cpu, rq->yld_both_empty,
		    rq->yld_act_empty, rq->yld_exp_empty, rq->yld_cnt,
		    rq->sched_switch, rq->sched_cnt, rq->sched_goidle,
		    rq->ttwu_cnt, rq->ttwu_local,
		    rq->rq_sched_info.cpu_time,
		    rq->rq_sched_info.run_delay, rq->rq_sched_info.pcnt);

		seq_printf(seq, "\n");

#ifdef CONFIG_SMP
		/* domain-specific stats */
		preempt_disable();
		for_each_domain(cpu, sd) {
			enum idle_type itype;
			char mask_str[NR_CPUS];

			cpumask_scnprintf(mask_str, NR_CPUS, sd->span);
			seq_printf(seq, "domain%d %s", dcnt++, mask_str);
			for (itype = SCHED_IDLE; itype < MAX_IDLE_TYPES;
					itype++) {
				seq_printf(seq, " %lu %lu %lu %lu %lu %lu %lu "
						"%lu",
				    sd->lb_cnt[itype],
				    sd->lb_balanced[itype],
				    sd->lb_failed[itype],
				    sd->lb_imbalance[itype],
				    sd->lb_gained[itype],
				    sd->lb_hot_gained[itype],
				    sd->lb_nobusyq[itype],
				    sd->lb_nobusyg[itype]);
			}
			seq_printf(seq, " %lu %lu %lu %lu %lu %lu %lu %lu %lu"
			    " %lu %lu %lu\n",
			    sd->alb_cnt, sd->alb_failed, sd->alb_pushed,
			    sd->sbe_cnt, sd->sbe_balanced, sd->sbe_pushed,
			    sd->sbf_cnt, sd->sbf_balanced, sd->sbf_pushed,
			    sd->ttwu_wake_remote, sd->ttwu_move_affine,
			    sd->ttwu_move_balance);
		}
		preempt_enable();
#endif
	}
	return 0;
}

static int schedstat_open(struct inode *inode, struct file *file)
{
	unsigned int size = PAGE_SIZE * (1 + num_online_cpus() / 32);
	char *buf = kmalloc(size, GFP_KERNEL);
	struct seq_file *m;
	int res;

	if (!buf)
		return -ENOMEM;
	res = single_open(file, show_schedstat, NULL);
	if (!res) {
		m = file->private_data;
		m->buf = buf;
		m->size = size;
	} else
		kfree(buf);
	return res;
}

const struct file_operations proc_schedstat_operations = {
	.open    = schedstat_open,
	.read    = seq_read,
	.llseek  = seq_lseek,
	.release = single_release,
};

/*
 * Expects runqueue lock to be held for atomicity of update
 */
static inline void
rq_sched_info_arrive(struct rq *rq, unsigned long delta_jiffies)
{
	if (rq) {
		rq->rq_sched_info.run_delay += delta_jiffies;
		rq->rq_sched_info.pcnt++;
	}
}

/*
 * Expects runqueue lock to be held for atomicity of update
 */
static inline void
rq_sched_info_depart(struct rq *rq, unsigned long delta_jiffies)
{
	if (rq)
		rq->rq_sched_info.cpu_time += delta_jiffies;
}
# define schedstat_inc(rq, field)	do { (rq)->field++; } while (0)
# define schedstat_add(rq, field, amt)	do { (rq)->field += (amt); } while (0)
#else /* !CONFIG_SCHEDSTATS */
static inline void
rq_sched_info_arrive(struct rq *rq, unsigned long delta_jiffies)
{}
static inline void
rq_sched_info_depart(struct rq *rq, unsigned long delta_jiffies)
{}
# define schedstat_inc(rq, field)	do { } while (0)
# define schedstat_add(rq, field, amt)	do { } while (0)
#endif

/*
 * this_rq_lock - lock this runqueue and disable interrupts.
 */
static inline struct rq *this_rq_lock(void)
	__acquires(rq->lock)
{
	struct rq *rq;

	local_irq_disable();
	rq = this_rq();
	spin_lock(&rq->lock);

	return rq;
}

#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
/*
 * Called when a process is dequeued from the active array and given
 * the cpu.  We should note that with the exception of interactive
 * tasks, the expired queue will become the active queue after the active
 * queue is empty, without explicitly dequeuing and requeuing tasks in the
 * expired queue.  (Interactive tasks may be requeued directly to the
 * active queue, thus delaying tasks in the expired queue from running;
 * see scheduler_tick()).
 *
 * This function is only called from sched_info_arrive(), rather than
 * dequeue_task(). Even though a task may be queued and dequeued multiple
 * times as it is shuffled about, we're really interested in knowing how
 * long it was from the *first* time it was queued to the time that it
 * finally hit a cpu.
 */
static inline void sched_info_dequeued(struct task_struct *t)
{
	t->sched_info.last_queued = 0;
}

/*
 * Called when a task finally hits the cpu.  We can now calculate how
 * long it was waiting to run.  We also note when it began so that we
 * can keep stats on how long its timeslice is.
 */
static void sched_info_arrive(struct task_struct *t)
{
	unsigned long now = jiffies, delta_jiffies = 0;

	if (t->sched_info.last_queued)
		delta_jiffies = now - t->sched_info.last_queued;
	sched_info_dequeued(t);
	t->sched_info.run_delay += delta_jiffies;
	t->sched_info.last_arrival = now;
	t->sched_info.pcnt++;

	rq_sched_info_arrive(task_rq(t), delta_jiffies);
}

/*
 * Called when a process is queued into either the active or expired
 * array.  The time is noted and later used to determine how long we
 * had to wait for us to reach the cpu.  Since the expired queue will
 * become the active queue after active queue is empty, without dequeuing
 * and requeuing any tasks, we are interested in queuing to either. It
 * is unusual but not impossible for tasks to be dequeued and immediately
 * requeued in the same or another array: this can happen in sched_yield(),
 * set_user_nice(), and even load_balance() as it moves tasks from runqueue
 * to runqueue.
 *
 * This function is only called from enqueue_task(), but also only updates
 * the timestamp if it is already not set.  It's assumed that
 * sched_info_dequeued() will clear that stamp when appropriate.
 */
static inline void sched_info_queued(struct task_struct *t)
{
	if (unlikely(sched_info_on()))
		if (!t->sched_info.last_queued)
			t->sched_info.last_queued = jiffies;
}

/*
 * Called when a process ceases being the active-running process, either
 * voluntarily or involuntarily.  Now we can calculate how long we ran.
 */
static inline void sched_info_depart(struct task_struct *t)
{
	unsigned long delta_jiffies = jiffies - t->sched_info.last_arrival;

	t->sched_info.cpu_time += delta_jiffies;
	rq_sched_info_depart(task_rq(t), delta_jiffies);
}

/*
 * Called when tasks are switched involuntarily due, typically, to expiring
 * their time slice.  (This may also be called when switching to or from
 * the idle task.)  We are only called when prev != next.
 */
static inline void
__sched_info_switch(struct task_struct *prev, struct task_struct *next)
{
	struct rq *rq = task_rq(prev);

	/*
	 * prev now departs the cpu.  It's not interesting to record
	 * stats about how efficient we were at scheduling the idle
	 * process, however.
	 */
	if (prev != rq->idle)
		sched_info_depart(prev);

	if (next != rq->idle)
		sched_info_arrive(next);
}
static inline void
sched_info_switch(struct task_struct *prev, struct task_struct *next)
{
	if (unlikely(sched_info_on()))
		__sched_info_switch(prev, next);
}
#else
#define sched_info_queued(t)		do { } while (0)
#define sched_info_switch(t, next)	do { } while (0)
#endif /* CONFIG_SCHEDSTATS || CONFIG_TASK_DELAY_ACCT */

/*
 * Adding/removing a task to/from a priority array:
 */
static void dequeue_task(struct task_struct *p, struct prio_array *array)
{
	array->nr_active--;
	list_del(&p->run_list);
	if (list_empty(array->queue + p->prio))
		__clear_bit(p->prio, array->bitmap);
}

static void enqueue_task(struct task_struct *p, struct prio_array *array)
{
	sched_info_queued(p);
	list_add_tail(&p->run_list, array->queue + p->prio);
	__set_bit(p->prio, array->bitmap);
	array->nr_active++;
	p->array = array;
}

/*
 * Put task to the end of the run list without the overhead of dequeue
 * followed by enqueue.
 */
static void requeue_task(struct task_struct *p, struct prio_array *array)
{
	list_move_tail(&p->run_list, array->queue + p->prio);
}

static inline void
enqueue_task_head(struct task_struct *p, struct prio_array *array)
{
	list_add(&p->run_list, array->queue + p->prio);
	__set_bit(p->prio, array->bitmap);
	array->nr_active++;
	p->array = array;
}

/*
 * __normal_prio - return the priority that is based on the static
 * priority but is modified by bonuses/penalties.
 *
 * We scale the actual sleep average [0 .... MAX_SLEEP_AVG]
 * into the -5 ... 0 ... +5 bonus/penalty range.
 *
 * We use 25% of the full 0...39 priority range so that:
 *
 * 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs.
 * 2) nice -20 CPU hogs do not get preempted by nice 0 tasks.
 *
 * Both properties are important to certain workloads.
 */

static inline int __normal_prio(struct task_struct *p)
{
	int bonus, prio;

	bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;

	prio = p->static_prio - bonus;
	if (prio < MAX_RT_PRIO)
		prio = MAX_RT_PRIO;
	if (prio > MAX_PRIO-1)
		prio = MAX_PRIO-1;
	return prio;
}

/*
 * To aid in avoiding the subversion of "niceness" due to uneven distribution
 * of tasks with abnormal "nice" values across CPUs the contribution that
 * each task makes to its run queue's load is weighted according to its
 * scheduling class and "nice" value.  For SCHED_NORMAL tasks this is just a
 * scaled version of the new time slice allocation that they receive on time
 * slice expiry etc.
 */

/*
 * Assume: static_prio_timeslice(NICE_TO_PRIO(0)) == DEF_TIMESLICE
 * If static_prio_timeslice() is ever changed to break this assumption then
 * this code will need modification
 */
#define TIME_SLICE_NICE_ZERO DEF_TIMESLICE
#define LOAD_WEIGHT(lp) \
	(((lp) * SCHED_LOAD_SCALE) / TIME_SLICE_NICE_ZERO)
#define PRIO_TO_LOAD_WEIGHT(prio) \
	LOAD_WEIGHT(static_prio_timeslice(prio))
#define RTPRIO_TO_LOAD_WEIGHT(rp) \
	(PRIO_TO_LOAD_WEIGHT(MAX_RT_PRIO) + LOAD_WEIGHT(rp))

static void set_load_weight(struct task_struct *p)
{
	if (has_rt_policy(p)) {
#ifdef CONFIG_SMP
		if (p == task_rq(p)->migration_thread)
			/*
			 * The migration thread does the actual balancing.
			 * Giving its load any weight will skew balancing
			 * adversely.
			 */
			p->load_weight = 0;
		else
#endif
			p->load_weight = RTPRIO_TO_LOAD_WEIGHT(p->rt_priority);
	} else
		p->load_weight = PRIO_TO_LOAD_WEIGHT(p->static_prio);
}

static inline void
inc_raw_weighted_load(struct rq *rq, const struct task_struct *p)
{
	rq->raw_weighted_load += p->load_weight;
}

static inline void
dec_raw_weighted_load(struct rq *rq, const struct task_struct *p)
{
	rq->raw_weighted_load -= p->load_weight;
}

static inline void inc_nr_running(struct task_struct *p, struct rq *rq)
{
	rq->nr_running++;
	inc_raw_weighted_load(rq, p);
}

static inline void dec_nr_running(struct task_struct *p, struct rq *rq)
{
	rq->nr_running--;
	dec_raw_weighted_load(rq, p);
}

/*
 * Calculate the expected normal priority: i.e. priority
 * without taking RT-inheritance into account. Might be
 * boosted by interactivity modifiers. Changes upon fork,
 * setprio syscalls, and whenever the interactivity
 * estimator recalculates.
 */
static inline int normal_prio(struct task_struct *p)
{
	int prio;

	if (has_rt_policy(p))
		prio = MAX_RT_PRIO-1 - p->rt_priority;
	else
		prio = __normal_prio(p);
	return prio;
}

/*
 * Calculate the current priority, i.e. the priority
 * taken into account by the scheduler. This value might
 * be boosted by RT tasks, or might be boosted by
 * interactivity modifiers. Will be RT if the task got
 * RT-boosted. If not then it returns p->normal_prio.
 */
static int effective_prio(struct task_struct *p)
{
	p->normal_prio = normal_prio(p);
	/*
	 * If we are RT tasks or we were boosted to RT priority,
	 * keep the priority unchanged. Otherwise, update priority
	 * to the normal priority:
	 */
	if (!rt_prio(p->prio))
		return p->normal_prio;
	return p->prio;
}

/*
 * __activate_task - move a task to the runqueue.
 */
static void __activate_task(struct task_struct *p, struct rq *rq)
{
	struct prio_array *target = rq->active;

	if (batch_task(p))
		target = rq->expired;
	enqueue_task(p, target);
	inc_nr_running(p, rq);
}

/*
 * __activate_idle_task - move idle task to the _front_ of runqueue.
 */
static inline void __activate_idle_task(struct task_struct *p, struct rq *rq)
{
	enqueue_task_head(p, rq->active);
	inc_nr_running(p, rq);
}

/*
 * Recalculate p->normal_prio and p->prio after having slept,
 * updating the sleep-average too:
 */
static int recalc_task_prio(struct task_struct *p, unsigned long long now)
{
	/* Caller must always ensure 'now >= p->timestamp' */
	unsigned long sleep_time = now - p->timestamp;

	if (batch_task(p))
		sleep_time = 0;

	if (likely(sleep_time > 0)) {
		/*
		 * This ceiling is set to the lowest priority that would allow
		 * a task to be reinserted into the active array on timeslice
		 * completion.
		 */
		unsigned long ceiling = INTERACTIVE_SLEEP(p);

		if (p->mm && sleep_time > ceiling && p->sleep_avg < ceiling) {
			/*
			 * Prevents user tasks from achieving best priority
			 * with one single large enough sleep.
			 */
			p->sleep_avg = ceiling;
			/*
			 * Using INTERACTIVE_SLEEP() as a ceiling places a
			 * nice(0) task 1ms sleep away from promotion, and
			 * gives it 700ms to round-robin with no chance of
			 * being demoted.  This is more than generous, so
			 * mark this sleep as non-interactive to prevent the
			 * on-runqueue bonus logic from intervening should
			 * this task not receive cpu immediately.
			 */
			p->sleep_type = SLEEP_NONINTERACTIVE;
		} else {
			/*
			 * Tasks waking from uninterruptible sleep are
			 * limited in their sleep_avg rise as they
			 * are likely to be waiting on I/O
			 */
			if (p->sleep_type == SLEEP_NONINTERACTIVE && p->mm) {
				if (p->sleep_avg >= ceiling)
					sleep_time = 0;
				else if (p->sleep_avg + sleep_time >=
					 ceiling) {
						p->sleep_avg = ceiling;
						sleep_time = 0;
				}
			}

			/*
			 * This code gives a bonus to interactive tasks.
			 *
			 * The boost works by updating the 'average sleep time'
			 * value here, based on ->timestamp. The more time a
			 * task spends sleeping, the higher the average gets -
			 * and the higher the priority boost gets as well.
			 */
			p->sleep_avg += sleep_time;

		}
		if (p->sleep_avg > NS_MAX_SLEEP_AVG)
			p->sleep_avg = NS_MAX_SLEEP_AVG;
	}

	return effective_prio(p);
}

/*
 * activate_task - move a task to the runqueue and do priority recalculation
 *
 * Update all the scheduling statistics stuff. (sleep average
 * calculation, priority modifiers, etc.)
 */
static void activate_task(struct task_struct *p, struct rq *rq, int local)
{
	unsigned long long now;

	if (rt_task(p))
		goto out;

	now = sched_clock();
#ifdef CONFIG_SMP
	if (!local) {
		/* Compensate for drifting sched_clock */
		struct rq *this_rq = this_rq();
		now = (now - this_rq->most_recent_timestamp)
			+ rq->most_recent_timestamp;
	}
#endif

	/*
	 * Sleep time is in units of nanosecs, so shift by 20 to get a
	 * milliseconds-range estimation of the amount of time that the task
	 * spent sleeping:
	 */
	if (unlikely(prof_on == SLEEP_PROFILING)) {
		if (p->state == TASK_UNINTERRUPTIBLE)
			profile_hits(SLEEP_PROFILING, (void *)get_wchan(p),
				     (now - p->timestamp) >> 20);
	}

	p->prio = recalc_task_prio(p, now);

	/*
	 * This checks to make sure it's not an uninterruptible task
	 * that is now waking up.
	 */
	if (p->sleep_type == SLEEP_NORMAL) {
		/*
		 * Tasks which were woken up by interrupts (ie. hw events)
		 * are most likely of interactive nature. So we give them
		 * the credit of extending their sleep time to the period
		 * of time they spend on the runqueue, waiting for execution
		 * on a CPU, first time around:
		 */
		if (in_interrupt())
			p->sleep_type = SLEEP_INTERRUPTED;
		else {
			/*
			 * Normal first-time wakeups get a credit too for
			 * on-runqueue time, but it will be weighted down:
			 */
			p->sleep_type = SLEEP_INTERACTIVE;
		}
	}
	p->timestamp = now;
out:
	__activate_task(p, rq);
}

/*
 * deactivate_task - remove a task from the runqueue.
 */
static void deactivate_task(struct task_struct *p, struct rq *rq)
{
	dec_nr_running(p, rq);
	dequeue_task(p, p->array);
	p->array = NULL;
}

/*
 * resched_task - mark a task 'to be rescheduled now'.
 *
 * On UP this means the setting of the need_resched flag, on SMP it
 * might also involve a cross-CPU call to trigger the scheduler on
 * the target CPU.
 */
#ifdef CONFIG_SMP

#ifndef tsk_is_polling
#define tsk_is_polling(t) test_tsk_thread_flag(t, TIF_POLLING_NRFLAG)
#endif

static void resched_task(struct task_struct *p)
{
	int cpu;

	assert_spin_locked(&task_rq(p)->lock);

	if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
		return;

	set_tsk_thread_flag(p, TIF_NEED_RESCHED);

	cpu = task_cpu(p);
	if (cpu == smp_processor_id())
		return;

	/* NEED_RESCHED must be visible before we test polling */
	smp_mb();
	if (!tsk_is_polling(p))
		smp_send_reschedule(cpu);
}
#else
static inline void resched_task(struct task_struct *p)
{
	assert_spin_locked(&task_rq(p)->lock);
	set_tsk_need_resched(p);
}
#endif

/**
 * task_curr - is this task currently executing on a CPU?
 * @p: the task in question.
 */
inline int task_curr(const struct task_struct *p)
{
	return cpu_curr(task_cpu(p)) == p;
}

/* Used instead of source_load when we know the type == 0 */
unsigned long weighted_cpuload(const int cpu)
{
	return cpu_rq(cpu)->raw_weighted_load;
}

#ifdef CONFIG_SMP
struct migration_req {
	struct list_head list;

	struct task_struct *task;
	int dest_cpu;

	struct completion done;
};

/*
 * The task's runqueue lock must be held.
 * Returns true if you have to wait for migration thread.
 */
static int
migrate_task(struct task_struct *p, int dest_cpu, struct migration_req *req)
{
	struct rq *rq = task_rq(p);

	/*
	 * If the task is not on a runqueue (and not running), then
	 * it is sufficient to simply update the task's cpu field.
	 */
	if (!p->array && !task_running(rq, p)) {
		set_task_cpu(p, dest_cpu);
		return 0;
	}

	init_completion(&req->done);
	req->task = p;
	req->dest_cpu = dest_cpu;
	list_add(&req->list, &rq->migration_queue);

	return 1;
}

/*
 * wait_task_inactive - wait for a thread to unschedule.
 *
 * The caller must ensure that the task *will* unschedule sometime soon,
 * else this function might spin for a *long* time. This function can't
 * be called with interrupts off, or it may introduce deadlock with
 * smp_call_function() if an IPI is sent by the same process we are
 * waiting to become inactive.
 */
void wait_task_inactive(struct task_struct *p)
{
	unsigned long flags;
	struct rq *rq;
	int preempted;

repeat:
	rq = task_rq_lock(p, &flags);
	/* Must be off runqueue entirely, not preempted. */
	if (unlikely(p->array || task_running(rq, p))) {
		/* If it's preempted, we yield.  It could be a while. */
		preempted = !task_running(rq, p);
		task_rq_unlock(rq, &flags);
		cpu_relax();
		if (preempted)
			yield();
		goto repeat;
	}
	task_rq_unlock(rq, &flags);
}

/***
 * kick_process - kick a running thread to enter/exit the kernel
 * @p: the to-be-kicked thread
 *
 * Cause a process which is running on another CPU to enter
 * kernel-mode, without any delay. (to get signals handled.)
 *
 * NOTE: this function doesnt have to take the runqueue lock,
 * because all it wants to ensure is that the remote task enters
 * the kernel. If the IPI races and the task has been migrated
 * to another CPU then no harm is done and the purpose has been
 * achieved as well.
 */
void kick_process(struct task_struct *p)
{
	int cpu;

	preempt_disable();
	cpu = task_cpu(p);
	if ((cpu != smp_processor_id()) && task_curr(p))
		smp_send_reschedule(cpu);
	preempt_enable();
}

/*
 * Return a low guess at the load of a migration-source cpu weighted
 * according to the scheduling class and "nice" value.
 *
 * We want to under-estimate the load of migration sources, to
 * balance conservatively.
 */
static inline unsigned long source_load(int cpu, int type)
{
	struct rq *rq = cpu_rq(cpu);

	if (type == 0)
		return rq->raw_weighted_load;

	return min(rq->cpu_load[type-1], rq->raw_weighted_load);
}

/*
 * Return a high guess at the load of a migration-target cpu weighted
 * according to the scheduling class and "nice" value.
 */
static inline unsigned long target_load(int cpu, int type)
{
	struct rq *rq = cpu_rq(cpu);

	if (type == 0)
		return rq->raw_weighted_load;

	return max(rq->cpu_load[type-1], rq->raw_weighted_load);
}

/*
 * Return the average load per task on the cpu's run queue
 */
static inline unsigned long cpu_avg_load_per_task(int cpu)
{
	struct rq *rq = cpu_rq(cpu);
	unsigned long n = rq->nr_running;

	return n ? rq->raw_weighted_load / n : SCHED_LOAD_SCALE;
}

/*
 * find_idlest_group finds and returns the least busy CPU group within the
 * domain.
 */
static struct sched_group *
find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)
{
	struct sched_group *idlest = NULL, *this = NULL, *group = sd->groups;
	unsigned long min_load = ULONG_MAX, this_load = 0;
	int load_idx = sd->forkexec_idx;
	int imbalance = 100 + (sd->imbalance_pct-100)/2;

	do {
		unsigned long load, avg_load;
		int local_group;
		int i;

		/* Skip over this group if it has no CPUs allowed */
		if (!cpus_intersects(group->cpumask, p->cpus_allowed))
			goto nextgroup;

		local_group = cpu_isset(this_cpu, group->cpumask);

		/* Tally up the load of all CPUs in the group */
		avg_load = 0;

		for_each_cpu_mask(i, group->cpumask) {
			/* Bias balancing toward cpus of our domain */
			if (local_group)
				load = source_load(i, load_idx);
			else
				load = target_load(i, load_idx);

			avg_load += load;
		}

		/* Adjust by relative CPU power of the group */
		avg_load = (avg_load * SCHED_LOAD_SCALE) / group->cpu_power;

		if (local_group) {
			this_load = avg_load;
			this = group;
		} else if (avg_load < min_load) {
			min_load = avg_load;
			idlest = group;
		}
nextgroup:
		group = group->next;
	} while (group != sd->groups);

	if (!idlest || 100*this_load < imbalance*min_load)
		return NULL;
	return idlest;
}

/*
 * find_idlest_cpu - find the idlest cpu among the cpus in group.
 */
static int
find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
{
	cpumask_t tmp;
	unsigned long load, min_load = ULONG_MAX;
	int idlest = -1;
	int i;

	/* Traverse only the allowed CPUs */
	cpus_and(tmp, group->cpumask, p->cpus_allowed);

	for_each_cpu_mask(i, tmp) {
		load = weighted_cpuload(i);

		if (load < min_load || (load == min_load && i == this_cpu)) {
			min_load = load;
			idlest = i;
		}
	}

	return idlest;
}

/*
 * sched_balance_self: balance the current task (running on cpu) in domains
 * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
 * SD_BALANCE_EXEC.
 *
 * Balance, ie. select the least loaded group.
 *
 * Returns the target CPU number, or the same CPU if no balancing is needed.
 *
 * preempt must be disabled.
 */
static int sched_balance_self(int cpu, int flag)
{
	struct task_struct *t = current;
	struct sched_domain *tmp, *sd = NULL;

	for_each_domain(cpu, tmp) {
 		/*
 	 	 * If power savings logic is enabled for a domain, stop there.
 	 	 */
		if (tmp->flags & SD_POWERSAVINGS_BALANCE)
			break;
		if (tmp->flags & flag)
			sd = tmp;
	}

	while (sd) {
		cpumask_t span;
		struct sched_group *group;
		int new_cpu, weight;

		if (!(sd->flags & flag)) {
			sd = sd->child;
			continue;
		}

		span = sd->span;
		group = find_idlest_group(sd, t, cpu);
		if (!group) {
			sd = sd->child;
			continue;
		}

		new_cpu = find_idlest_cpu(group, t, cpu);
		if (new_cpu == -1 || new_cpu == cpu) {
			/* Now try balancing at a lower domain level of cpu */
			sd = sd->child;
			continue;
		}

		/* Now try balancing at a lower domain level of new_cpu */
		cpu = new_cpu;
		sd = NULL;
		weight = cpus_weight(span);
		for_each_domain(cpu, tmp) {
			if (weight <= cpus_weight(tmp->span))
				break;
			if (tmp->flags & flag)
				sd = tmp;
		}
		/* while loop will break here if sd == NULL */
	}

	return cpu;
}

#endif /* CONFIG_SMP */

/*
 * wake_idle() will wake a task on an idle cpu if task->cpu is
 * not idle and an idle cpu is available.  The span of cpus to
 * search starts with cpus closest then further out as needed,
 * so we always favor a closer, idle cpu.
 *
 * Returns the CPU we should wake onto.
 */
#if defined(ARCH_HAS_SCHED_WAKE_IDLE)
static int wake_idle(int cpu, struct task_struct *p)
{
	cpumask_t tmp;
	struct sched_domain *sd;
	int i;

	if (idle_cpu(cpu))
		return cpu;

	for_each_domain(cpu, sd) {
		if (sd->flags & SD_WAKE_IDLE) {
			cpus_and(tmp, sd->span, p->cpus_allowed);
			for_each_cpu_mask(i, tmp) {
				if (idle_cpu(i))
					return i;
			}
		}
		else
			break;
	}
	return cpu;
}
#else
static inline int wake_idle(int cpu, struct task_struct *p)
{
	return cpu;
}
#endif

/***
 * try_to_wake_up - wake up a thread
 * @p: the to-be-woken-up thread
 * @state: the mask of task states that can be woken
 * @sync: do a synchronous wakeup?
 *
 * Put it on the run-queue if it's not already there. The "current"
 * thread is always on the run-queue (except when the actual
 * re-schedule is in progress), and as such you're allowed to do
 * the simpler "current->state = TASK_RUNNING" to mark yourself
 * runnable without the overhead of this.
 *
 * returns failure only if the task is already active.
 */
static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
{
	int cpu, this_cpu, success = 0;
	unsigned long flags;
	long old_state;
	struct rq *rq;
#ifdef CONFIG_SMP
	struct sched_domain *sd, *this_sd = NULL;
	unsigned long load, this_load;
	int new_cpu;
#endif

	rq = task_rq_lock(p, &flags);
	old_state = p->state;
	if (!(old_state & state))
		goto out;

	if (p->array)
		goto out_running;

	cpu = task_cpu(p);
	this_cpu = smp_processor_id();

#ifdef CONFIG_SMP
	if (unlikely(task_running(rq, p)))
		goto out_activate;

	new_cpu = cpu;

	schedstat_inc(rq, ttwu_cnt);
	if (cpu == this_cpu) {
		schedstat_inc(rq, ttwu_local);
		goto out_set_cpu;
	}

	for_each_domain(this_cpu, sd) {
		if (cpu_isset(cpu, sd->span)) {
			schedstat_inc(sd, ttwu_wake_remote);
			this_sd = sd;
			break;
		}
	}

	if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
		goto out_set_cpu;

	/*
	 * Check for affine wakeup and passive balancing possibilities.
	 */
	if (this_sd) {
		int idx = this_sd->wake_idx;
		unsigned int imbalance;

		imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;

		load = source_load(cpu, idx);
		this_load = target_load(this_cpu, idx);

		new_cpu = this_cpu; /* Wake to this CPU if we can */

		if (this_sd->flags & SD_WAKE_AFFINE) {
			unsigned long tl = this_load;
			unsigned long tl_per_task;

			tl_per_task = cpu_avg_load_per_task(this_cpu);

			/*
			 * If sync wakeup then subtract the (maximum possible)
			 * effect of the currently running task from the load
			 * of the current CPU:
			 */
			if (sync)
				tl -= current->load_weight;

			if ((tl <= load &&
				tl + target_load(cpu, idx) <= tl_per_task) ||
				100*(tl + p->load_weight) <= imbalance*load) {
				/*
				 * This domain has SD_WAKE_AFFINE and
				 * p is cache cold in this domain, and
				 * there is no bad imbalance.
				 */
				schedstat_inc(this_sd, ttwu_move_affine);
				goto out_set_cpu;
			}
		}

		/*
		 * Start passive balancing when half the imbalance_pct
		 * limit is reached.
		 */
		if (this_sd->flags & SD_WAKE_BALANCE) {
			if (imbalance*this_load <= 100*load) {
				schedstat_inc(this_sd, ttwu_move_balance);
				goto out_set_cpu;
			}
		}
	}

	new_cpu = cpu; /* Could not wake to this_cpu. Wake to cpu instead */
out_set_cpu:
	new_cpu = wake_idle(new_cpu, p);
	if (new_cpu != cpu) {
		set_task_cpu(p, new_cpu);
		task_rq_unlock(rq, &flags);
		/* might preempt at this point */
		rq = task_rq_lock(p, &flags);
		old_state = p->state;
		if (!(old_state & state))
			goto out;
		if (p->array)
			goto out_running;

		this_cpu = smp_processor_id();
		cpu = task_cpu(p);
	}

out_activate:
#endif /* CONFIG_SMP */
	if (old_state == TASK_UNINTERRUPTIBLE) {
		rq->nr_uninterruptible--;
		/*
		 * Tasks on involuntary sleep don't earn
		 * sleep_avg beyond just interactive state.
		 */
		p->sleep_type = SLEEP_NONINTERACTIVE;
	} else

	/*
	 * Tasks that have marked their sleep as noninteractive get
	 * woken up with their sleep average not weighted in an
	 * interactive way.
	 */
		if (old_state & TASK_NONINTERACTIVE)
			p->sleep_type = SLEEP_NONINTERACTIVE;


	activate_task(p, rq, cpu == this_cpu);
	/*
	 * Sync wakeups (i.e. those types of wakeups where the waker
	 * has indicated that it will leave the CPU in short order)
	 * don't trigger a preemption, if the woken up task will run on
	 * this cpu. (in this case the 'I will reschedule' promise of
	 * the waker guarantees that the freshly woken up task is going
	 * to be considered on this CPU.)
	 */
	if (!sync || cpu != this_cpu) {
		if (TASK_PREEMPTS_CURR(p, rq))
			resched_task(rq->curr);
	}
	success = 1;

out_running:
	p->state = TASK_RUNNING;
out:
	task_rq_unlock(rq, &flags);

	return success;
}

int fastcall wake_up_process(struct task_struct *p)
{
	return try_to_wake_up(p, TASK_STOPPED | TASK_TRACED |
				 TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE, 0);
}
EXPORT_SYMBOL(wake_up_process);

int fastcall wake_up_state(struct task_struct *p, unsigned int state)
{
	return try_to_wake_up(p, state, 0);
}

static void task_running_tick(struct rq *rq, struct task_struct *p);
/*
 * Perform scheduler related setup for a newly forked process p.
 * p is forked by current.
 */
void fastcall sched_fork(struct task_struct *p, int clone_flags)
{
	int cpu = get_cpu();

#ifdef CONFIG_SMP
	cpu = sched_balance_self(cpu, SD_BALANCE_FORK);
#endif
	set_task_cpu(p, cpu);

	/*
	 * We mark the process as running here, but have not actually
	 * inserted it onto the runqueue yet. This guarantees that
	 * nobody will actually run it, and a signal or other external
	 * event cannot wake it up and insert it on the runqueue either.
	 */
	p->state = TASK_RUNNING;

	/*
	 * Make sure we do not leak PI boosting priority to the child:
	 */
	p->prio = current->normal_prio;

	INIT_LIST_HEAD(&p->run_list);
	p->array = NULL;
#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
	if (unlikely(sched_info_on()))
		memset(&p->sched_info, 0, sizeof(p->sched_info));
#endif
#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
	p->oncpu = 0;
#endif
#ifdef CONFIG_PREEMPT
	/* Want to start with kernel preemption disabled. */
	task_thread_info(p)->preempt_count = 1;
#endif
	/*
	 * Share the timeslice between parent and child, thus the
	 * total amount of pending timeslices in the system doesn't change,
	 * resulting in more scheduling fairness.
	 */
	local_irq_disable();
	p->time_slice = (current->time_slice + 1) >> 1;
	/*
	 * The remainder of the first timeslice might be recovered by
	 * the parent if the child exits early enough.
	 */
	p->first_time_slice = 1;
	current->time_slice >>= 1;
	p->timestamp = sched_clock();
	if (unlikely(!current->time_slice)) {
		/*
		 * This case is rare, it happens when the parent has only
		 * a single jiffy left from its timeslice. Taking the
		 * runqueue lock is not a problem.
		 */
		current->time_slice = 1;
		task_running_tick(cpu_rq(cpu), current);
	}
	local_irq_enable();
	put_cpu();
}

/*
 * wake_up_new_task - wake up a newly created task for the first time.
 *
 * This function will do some initial scheduler statistics housekeeping
 * that must be done for every newly created context, then puts the task
 * on the runqueue and wakes it.
 */
void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
{
	struct rq *rq, *this_rq;
	unsigned long flags;
	int this_cpu, cpu;

	rq = task_rq_lock(p, &flags);
	BUG_ON(p->state != TASK_RUNNING);
	this_cpu = smp_processor_id();
	cpu = task_cpu(p);

	/*
	 * We decrease the sleep average of forking parents
	 * and children as well, to keep max-interactive tasks
	 * from forking tasks that are max-interactive. The parent
	 * (current) is done further down, under its lock.
	 */
	p->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(p) *
		CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);

	p->prio = effective_prio(p);

	if (likely(cpu == this_cpu)) {
		if (!(clone_flags & CLONE_VM)) {
			/*
			 * The VM isn't cloned, so we're in a good position to
			 * do child-runs-first in anticipation of an exec. This
			 * usually avoids a lot of COW overhead.
			 */
			if (unlikely(!current->array))
				__activate_task(p, rq);
			else {
				p->prio = current->prio;
				p->normal_prio = current->normal_prio;
				list_add_tail(&p->run_list, &current->run_list);
				p->array = current->array;
				p->array->nr_active++;
				inc_nr_running(p, rq);
			}
			set_need_resched();
		} else
			/* Run child last */
			__activate_task(p, rq);
		/*
		 * We skip the following code due to cpu == this_cpu
	 	 *
		 *   task_rq_unlock(rq, &flags);
		 *   this_rq = task_rq_lock(current, &flags);
		 */
		this_rq = rq;
	} else {
		this_rq = cpu_rq(this_cpu);

		/*
		 * Not the local CPU - must adjust timestamp. This should
		 * get optimised away in the !CONFIG_SMP case.
		 */
		p->timestamp = (p->timestamp - this_rq->most_recent_timestamp)
					+ rq->most_recent_timestamp;
		__activate_task(p, rq);
		if (TASK_PREEMPTS_CURR(p, rq))
			resched_task(rq->curr);

		/*
		 * Parent and child are on different CPUs, now get the
		 * parent runqueue to update the parent's ->sleep_avg:
		 */
		task_rq_unlock(rq, &flags);
		this_rq = task_rq_lock(current, &flags);
	}
	current->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(current) *
		PARENT_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
	task_rq_unlock(this_rq, &flags);
}

/*
 * Potentially available exiting-child timeslices are
 * retrieved here - this way the parent does not get
 * penalized for creating too many threads.
 *
 * (this cannot be used to 'generate' timeslices
 * artificially, because any timeslice recovered here
 * was given away by the parent in the first place.)
 */
void fastcall sched_exit(struct task_struct *p)
{
	unsigned long flags;
	struct rq *rq;

	/*
	 * If the child was a (relative-) CPU hog then decrease
	 * the sleep_avg of the parent as well.
	 */
	rq = task_rq_lock(p->parent, &flags);
	if (p->first_time_slice && task_cpu(p) == task_cpu(p->parent)) {
		p->parent->time_slice += p->time_slice;
		if (unlikely(p->parent->time_slice > task_timeslice(p)))
			p->parent->time_slice = task_timeslice(p);
	}
	if (p->sleep_avg < p->parent->sleep_avg)
		p->parent->sleep_avg = p->parent->sleep_avg /
		(EXIT_WEIGHT + 1) * EXIT_WEIGHT + p->sleep_avg /
		(EXIT_WEIGHT + 1);
	task_rq_unlock(rq, &flags);
}

/**
 * prepare_task_switch - prepare to switch tasks
 * @rq: the runqueue preparing to switch
 * @next: the task we are going to switch to.
 *
 * This is called with the rq lock held and interrupts off. It must
 * be paired with a subsequent finish_task_switch after the context
 * switch.
 *
 * prepare_task_switch sets up locking and calls architecture specific
 * hooks.
 */
static inline void prepare_task_switch(struct rq *rq, struct task_struct *next)
{
	prepare_lock_switch(rq, next);
	prepare_arch_switch(next);
}

/**
 * finish_task_switch - clean up after a task-switch
 * @rq: runqueue associated with task-switch
 * @prev: the thread we just switched away from.
 *
 * finish_task_switch must be called after the context switch, paired
 * with a prepare_task_switch call before the context switch.
 * finish_task_switch will reconcile locking set up by prepare_task_switch,
 * and do any other architecture-specific cleanup actions.
 *
 * Note that we may have delayed dropping an mm in context_switch(). If
 * so, we finish that here outside of the runqueue lock.  (Doing it
 * with the lock held can cause deadlocks; see schedule() for
 * details.)
 */
static inline void finish_task_switch(struct rq *rq, struct task_struct *prev)
	__releases(rq->lock)
{
	struct mm_struct *mm = rq->prev_mm;
	long prev_state;

	rq->prev_mm = NULL;

	/*
	 * A task struct has one reference for the use as "current".
	 * If a task dies, then it sets TASK_DEAD in tsk->state and calls
	 * schedule one last time. The schedule call will never return, and
	 * the scheduled task must drop that reference.
	 * The test for TASK_DEAD must occur while the runqueue locks are
	 * still held, otherwise prev could be scheduled on another cpu, die
	 * there before we look at prev->state, and then the reference would
	 * be dropped twice.
	 *		Manfred Spraul <manfred@colorfullife.com>
	 */
	prev_state = prev->state;
	finish_arch_switch(prev);
	finish_lock_switch(rq, prev);
	if (mm)
		mmdrop(mm);
	if (unlikely(prev_state == TASK_DEAD)) {
		/*
		 * Remove function-return probe instances associated with this
		 * task and put them back on the free list.
	 	 */
		kprobe_flush_task(prev);
		put_task_struct(prev);
	}
}

/**
 * schedule_tail - first thing a freshly forked thread must call.
 * @prev: the thread we just switched away from.
 */
asmlinkage void schedule_tail(struct task_struct *prev)
	__releases(rq->lock)
{
	struct rq *rq = this_rq();

	finish_task_switch(rq, prev);
#ifdef __ARCH_WANT_UNLOCKED_CTXSW
	/* In this case, finish_task_switch does not reenable preemption */
	preempt_enable();
#endif
	if (current->set_child_tid)
		put_user(current->pid, current->set_child_tid);
}

/*
 * context_switch - switch to the new MM and the new
 * thread's register state.
 */
static inline struct task_struct *
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next)
{
	struct mm_struct *mm = next->mm;
	struct mm_struct *oldmm = prev->active_mm;

	/*
	 * For paravirt, this is coupled with an exit in switch_to to
	 * combine the page table reload and the switch backend into
	 * one hypercall.
	 */
	arch_enter_lazy_cpu_mode();

	if (!mm) {
		next->active_mm = oldmm;
		atomic_inc(&oldmm->mm_count);
		enter_lazy_tlb(oldmm, next);
	} else
		switch_mm(oldmm, mm, next);

	if (!prev->mm) {
		prev->active_mm = NULL;
		WARN_ON(rq->prev_mm);
		rq->prev_mm = oldmm;
	}
	/*
	 * Since the runqueue lock will be released by the next
	 * task (which is an invalid locking op but in the case
	 * of the scheduler it's an obvious special-case), so we
	 * do an early lockdep release here:
	 */
#ifndef __ARCH_WANT_UNLOCKED_CTXSW
	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
#endif

	/* Here we just switch the register state and the stack. */
	switch_to(prev, next, prev);

	return prev;
}

/*
 * nr_running, nr_uninterruptible and nr_context_switches:
 *
 * externally visible scheduler statistics: current number of runnable
 * threads, current number of uninterruptible-sleeping threads, total
 * number of context switches performed since bootup.
 */
unsigned long nr_running(void)
{
	unsigned long i, sum = 0;

	for_each_online_cpu(i)
		sum += cpu_rq(i)->nr_running;

	return sum;
}

unsigned long nr_uninterruptible(void)
{
	unsigned long i, sum = 0;

	for_each_possible_cpu(i)
		sum += cpu_rq(i)->nr_uninterruptible;

	/*
	 * Since we read the counters lockless, it might be slightly
	 * inaccurate. Do not allow it to go below zero though:
	 */
	if (unlikely((long)sum < 0))
		sum = 0;

	return sum;
}

unsigned long long nr_context_switches(void)
{
	int i;
	unsigned long long sum = 0;

	for_each_possible_cpu(i)
		sum += cpu_rq(i)->nr_switches;

	return sum;
}

unsigned long nr_iowait(void)
{
	unsigned long i, sum = 0;

	for_each_possible_cpu(i)
		sum += atomic_read(&cpu_rq(i)->nr_iowait);

	return sum;
}

unsigned long nr_active(void)
{
	unsigned long i, running = 0, uninterruptible = 0;

	for_each_online_cpu(i) {
		running += cpu_rq(i)->nr_running;
		uninterruptible += cpu_rq(i)->nr_uninterruptible;
	}

	if (unlikely((long)uninterruptible < 0))
		uninterruptible = 0;

	return running + uninterruptible;
}

#ifdef CONFIG_SMP

/*
 * Is this task likely cache-hot:
 */
static inline int
task_hot(struct task_struct *p, unsigned long long now, struct sched_domain *sd)
{
	return (long long)(now - p->last_ran) < (long long)sd->cache_hot_time;
}

/*
 * double_rq_lock - safely lock two runqueues
 *
 * Note this does not disable interrupts like task_rq_lock,
 * you need to do so manually before calling.
 */
static void double_rq_lock(struct rq *rq1, struct rq *rq2)
	__acquires(rq1->lock)
	__acquires(rq2->lock)
{
	BUG_ON(!irqs_disabled());
	if (rq1 == rq2) {
		spin_lock(&rq1->lock);
		__acquire(rq2->lock);	/* Fake it out ;) */
	} else {
		if (rq1 < rq2) {
			spin_lock(&rq1->lock);
			spin_lock(&rq2->lock);
		} else {
			spin_lock(&rq2->lock);
			spin_lock(&rq1->lock);
		}
	}
}

/*
 * double_rq_unlock - safely unlock two runqueues
 *
 * Note this does not restore interrupts like task_rq_unlock,
 * you need to do so manually after calling.
 */
static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
	__releases(rq1->lock)
	__releases(rq2->lock)
{
	spin_unlock(&rq1->lock);
	if (rq1 != rq2)
		spin_unlock(&rq2->lock);
	else
		__release(rq2->lock);
}

/*
 * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
 */
static void double_lock_balance(struct rq *this_rq, struct rq *busiest)
	__releases(this_rq->lock)
	__acquires(busiest->lock)
	__acquires(this_rq->lock)
{
	if (unlikely(!irqs_disabled())) {
		/* printk() doesn't work good under rq->lock */
		spin_unlock(&this_rq->lock);
		BUG_ON(1);
	}
	if (unlikely(!spin_trylock(&busiest->lock))) {
		if (busiest < this_rq) {
			spin_unlock(&this_rq->lock);
			spin_lock(&busiest->lock);
			spin_lock(&this_rq->lock);
		} else
			spin_lock(&busiest->lock);
	}
}

/*
 * If dest_cpu is allowed for this process, migrate the task to it.
 * This is accomplished by forcing the cpu_allowed mask to only
 * allow dest_cpu, which will force the cpu onto dest_cpu.  Then
 * the cpu_allowed mask is restored.
 */
static void sched_migrate_task(struct task_struct *p, int dest_cpu)
{
	struct migration_req req;
	unsigned long flags;
	struct rq *rq;

	rq = task_rq_lock(p, &flags);
	if (!cpu_isset(dest_cpu, p->cpus_allowed)
	    || unlikely(cpu_is_offline(dest_cpu)))
		goto out;

	/* force the process onto the specified CPU */
	if (migrate_task(p, dest_cpu, &req)) {
		/* Need to wait for migration thread (might exit: take ref). */
		struct task_struct *mt = rq->migration_thread;

		get_task_struct(mt);
		task_rq_unlock(rq, &flags);
		wake_up_process(mt);
		put_task_struct(mt);
		wait_for_completion(&req.done);

		return;
	}
out:
	task_rq_unlock(rq, &flags);
}

/*
 * sched_exec - execve() is a valuable balancing opportunity, because at
 * this point the task has the smallest effective memory and cache footprint.
 */
void sched_exec(void)
{
	int new_cpu, this_cpu = get_cpu();
	new_cpu = sched_balance_self(this_cpu, SD_BALANCE_EXEC);
	put_cpu();
	if (new_cpu != this_cpu)
		sched_migrate_task(current, new_cpu);
}

/*
 * pull_task - move a task from a remote runqueue to the local runqueue.
 * Both runqueues must be locked.
 */
static void pull_task(struct rq *src_rq, struct prio_array *src_array,
		      struct task_struct *p, struct rq *this_rq,
		      struct prio_array *this_array, int this_cpu)
{
	dequeue_task(p, src_array);
	dec_nr_running(p, src_rq);
	set_task_cpu(p, this_cpu);
	inc_nr_running(p, this_rq);
	enqueue_task(p, this_array);
	p->timestamp = (p->timestamp - src_rq->most_recent_timestamp)
				+ this_rq->most_recent_timestamp;
	/*
	 * Note that idle threads have a prio of MAX_PRIO, for this test
	 * to be always true for them.
	 */
	if (TASK_PREEMPTS_CURR(p, this_rq))
		resched_task(this_rq->curr);
}

/*
 * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
 */
static
int can_migrate_task(struct task_struct *p, struct rq *rq, int this_cpu,
		     struct sched_domain *sd, enum idle_type idle,
		     int *all_pinned)
{
	/*
	 * We do not migrate tasks that are:
	 * 1) running (obviously), or
	 * 2) cannot be migrated to this CPU due to cpus_allowed, or
	 * 3) are cache-hot on their current CPU.
	 */
	if (!cpu_isset(this_cpu, p->cpus_allowed))
		return 0;
	*all_pinned = 0;

	if (task_running(rq, p))
		return 0;

	/*
	 * Aggressive migration if:
	 * 1) task is cache cold, or
	 * 2) too many balance attempts have failed.
	 */

	if (sd->nr_balance_failed > sd->cache_nice_tries) {
#ifdef CONFIG_SCHEDSTATS
		if (task_hot(p, rq->most_recent_timestamp, sd))
			schedstat_inc(sd, lb_hot_gained[idle]);
#endif
		return 1;
	}

	if (task_hot(p, rq->most_recent_timestamp, sd))
		return 0;
	return 1;
}

#define rq_best_prio(rq) min((rq)->curr->prio, (rq)->best_expired_prio)

/*
 * move_tasks tries to move up to max_nr_move tasks and max_load_move weighted
 * load from busiest to this_rq, as part of a balancing operation within
 * "domain". Returns the number of tasks moved.
 *
 * Called with both runqueues locked.
 */
static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
		      unsigned long max_nr_move, unsigned long max_load_move,
		      struct sched_domain *sd, enum idle_type idle,
		      int *all_pinned)
{
	int idx, pulled = 0, pinned = 0, this_best_prio, best_prio,
	    best_prio_seen, skip_for_load;
	struct prio_array *array, *dst_array;
	struct list_head *head, *curr;
	struct task_struct *tmp;
	long rem_load_move;

	if (max_nr_move == 0 || max_load_move == 0)
		goto out;

	rem_load_move = max_load_move;
	pinned = 1;
	this_best_prio = rq_best_prio(this_rq);
	best_prio = rq_best_prio(busiest);
	/*
	 * Enable handling of the case where there is more than one task
	 * with the best priority.   If the current running task is one
	 * of those with prio==best_prio we know it won't be moved
	 * and therefore it's safe to override the skip (based on load) of
	 * any task we find with that prio.
	 */
	best_prio_seen = best_prio == busiest->curr->prio;

	/*
	 * We first consider expired tasks. Those will likely not be
	 * executed in the near future, and they are most likely to
	 * be cache-cold, thus switching CPUs has the least effect
	 * on them.
	 */
	if (busiest->expired->nr_active) {
		array = busiest->expired;
		dst_array = this_rq->expired;
	} else {
		array = busiest->active;
		dst_array = this_rq->active;
	}

new_array:
	/* Start searching at priority 0: */
	idx = 0;
skip_bitmap:
	if (!idx)
		idx = sched_find_first_bit(array->bitmap);
	else
		idx = find_next_bit(array->bitmap, MAX_PRIO, idx);
	if (idx >= MAX_PRIO) {
		if (array == busiest->expired && busiest->active->nr_active) {
			array = busiest->active;
			dst_array = this_rq->active;
			goto new_array;
		}
		goto out;
	}

	head = array->queue + idx;
	curr = head->prev;
skip_queue:
	tmp = list_entry(curr, struct task_struct, run_list);

	curr = curr->prev;

	/*
	 * To help distribute high priority tasks accross CPUs we don't
	 * skip a task if it will be the highest priority task (i.e. smallest
	 * prio value) on its new queue regardless of its load weight
	 */
	skip_for_load = tmp->load_weight > rem_load_move;
	if (skip_for_load && idx < this_best_prio)
		skip_for_load = !best_prio_seen && idx == best_prio;
	if (skip_for_load ||
	    !can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {

		best_prio_seen |= idx == best_prio;
		if (curr != head)
			goto skip_queue;
		idx++;
		goto skip_bitmap;
	}

	pull_task(busiest, array, tmp, this_rq, dst_array, this_cpu);
	pulled++;
	rem_load_move -= tmp->load_weight;

	/*
	 * We only want to steal up to the prescribed number of tasks
	 * and the prescribed amount of weighted load.
	 */
	if (pulled < max_nr_move && rem_load_move > 0) {
		if (idx < this_best_prio)
			this_best_prio = idx;
		if (curr != head)
			goto skip_queue;
		idx++;
		goto skip_bitmap;
	}
out:
	/*
	 * Right now, this is the only place pull_task() is called,
	 * so we can safely collect pull_task() stats here rather than
	 * inside pull_task().
	 */
	schedstat_add(sd, lb_gained[idle], pulled);

	if (all_pinned)
		*all_pinned = pinned;
	return pulled;
}

/*
 * find_busiest_group finds and returns the busiest CPU group within the
 * domain. It calculates and returns the amount of weighted load which
 * should be moved to restore balance via the imbalance parameter.
 */
static struct sched_group *
find_busiest_group(struct sched_domain *sd, int this_cpu,
		   unsigned long *imbalance, enum idle_type idle, int *sd_idle,
		   cpumask_t *cpus, int *balance)
{
	struct sched_group *busiest = NULL, *this = NULL, *group = sd->groups;
	unsigned long max_load, avg_load, total_load, this_load, total_pwr;
	unsigned long max_pull;
	unsigned long busiest_load_per_task, busiest_nr_running;
	unsigned long this_load_per_task, this_nr_running;
	int load_idx;
#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
	int power_savings_balance = 1;
	unsigned long leader_nr_running = 0, min_load_per_task = 0;
	unsigned long min_nr_running = ULONG_MAX;
	struct sched_group *group_min = NULL, *group_leader = NULL;
#endif

	max_load = this_load = total_load = total_pwr = 0;
	busiest_load_per_task = busiest_nr_running = 0;
	this_load_per_task = this_nr_running = 0;
	if (idle == NOT_IDLE)
		load_idx = sd->busy_idx;
	else if (idle == NEWLY_IDLE)
		load_idx = sd->newidle_idx;
	else
		load_idx = sd->idle_idx;

	do {
		unsigned long load, group_capacity;
		int local_group;
		int i;
		unsigned int balance_cpu = -1, first_idle_cpu = 0;
		unsigned long sum_nr_running, sum_weighted_load;

		local_group = cpu_isset(this_cpu, group->cpumask);

		if (local_group)
			balance_cpu = first_cpu(group->cpumask);

		/* Tally up the load of all CPUs in the group */
		sum_weighted_load = sum_nr_running = avg_load = 0;

		for_each_cpu_mask(i, group->cpumask) {
			struct rq *rq;

			if (!cpu_isset(i, *cpus))
				continue;

			rq = cpu_rq(i);

			if (*sd_idle && !idle_cpu(i))
				*sd_idle = 0;

			/* Bias balancing toward cpus of our domain */
			if (local_group) {
				if (idle_cpu(i) && !first_idle_cpu) {
					first_idle_cpu = 1;
					balance_cpu = i;
				}

				load = target_load(i, load_idx);
			} else
				load = source_load(i, load_idx);

			avg_load += load;
			sum_nr_running += rq->nr_running;
			sum_weighted_load += rq->raw_weighted_load;
		}

		/*
		 * First idle cpu or the first cpu(busiest) in this sched group
		 * is eligible for doing load balancing at this and above
		 * domains.
		 */
		if (local_group && balance_cpu != this_cpu && balance) {
			*balance = 0;
			goto ret;
		}

		total_load += avg_load;
		total_pwr += group->cpu_power;

		/* Adjust by relative CPU power of the group */
		avg_load = (avg_load * SCHED_LOAD_SCALE) / group->cpu_power;

		group_capacity = group->cpu_power / SCHED_LOAD_SCALE;

		if (local_group) {
			this_load = avg_load;
			this = group;
			this_nr_running = sum_nr_running;
			this_load_per_task = sum_weighted_load;
		} else if (avg_load > max_load &&
			   sum_nr_running > group_capacity) {
			max_load = avg_load;
			busiest = group;
			busiest_nr_running = sum_nr_running;
			busiest_load_per_task = sum_weighted_load;
		}

#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
		/*
		 * Busy processors will not participate in power savings
		 * balance.
		 */
 		if (idle == NOT_IDLE || !(sd->flags & SD_POWERSAVINGS_BALANCE))
 			goto group_next;

		/*
		 * If the local group is idle or completely loaded
		 * no need to do power savings balance at this domain
		 */
		if (local_group && (this_nr_running >= group_capacity ||
				    !this_nr_running))
			power_savings_balance = 0;

 		/*
		 * If a group is already running at full capacity or idle,
		 * don't include that group in power savings calculations
 		 */
 		if (!power_savings_balance || sum_nr_running >= group_capacity
		    || !sum_nr_running)
 			goto group_next;

 		/*
		 * Calculate the group which has the least non-idle load.
 		 * This is the group from where we need to pick up the load
 		 * for saving power
 		 */
 		if ((sum_nr_running < min_nr_running) ||
 		    (sum_nr_running == min_nr_running &&
		     first_cpu(group->cpumask) <
		     first_cpu(group_min->cpumask))) {
 			group_min = group;
 			min_nr_running = sum_nr_running;
			min_load_per_task = sum_weighted_load /
						sum_nr_running;
 		}

 		/*
		 * Calculate the group which is almost near its
 		 * capacity but still has some space to pick up some load
 		 * from other group and save more power
 		 */
 		if (sum_nr_running <= group_capacity - 1) {
 			if (sum_nr_running > leader_nr_running ||
 			    (sum_nr_running == leader_nr_running &&
 			     first_cpu(group->cpumask) >
 			      first_cpu(group_leader->cpumask))) {
 				group_leader = group;
 				leader_nr_running = sum_nr_running;
 			}
		}
group_next:
#endif
		group = group->next;
	} while (group != sd->groups);

	if (!busiest || this_load >= max_load || busiest_nr_running == 0)
		goto out_balanced;

	avg_load = (SCHED_LOAD_SCALE * total_load) / total_pwr;

	if (this_load >= avg_load ||
			100*max_load <= sd->imbalance_pct*this_load)
		goto out_balanced;

	busiest_load_per_task /= busiest_nr_running;
	/*
	 * We're trying to get all the cpus to the average_load, so we don't
	 * want to push ourselves above the average load, nor do we wish to
	 * reduce the max loaded cpu below the average load, as either of these
	 * actions would just result in more rebalancing later, and ping-pong
	 * tasks around. Thus we look for the minimum possible imbalance.
	 * Negative imbalances (*we* are more loaded than anyone else) will
	 * be counted as no imbalance for these purposes -- we can't fix that
	 * by pulling tasks to us.  Be careful of negative numbers as they'll
	 * appear as very large values with unsigned longs.
	 */
	if (max_load <= busiest_load_per_task)
		goto out_balanced;

	/*
	 * In the presence of smp nice balancing, certain scenarios can have
	 * max load less than avg load(as we skip the groups at or below
	 * its cpu_power, while calculating max_load..)
	 */
	if (max_load < avg_load) {
		*imbalance = 0;
		goto small_imbalance;
	}

	/* Don't want to pull so many tasks that a group would go idle */
	max_pull = min(max_load - avg_load, max_load - busiest_load_per_task);

	/* How much load to actually move to equalise the imbalance */
	*imbalance = min(max_pull * busiest->cpu_power,
				(avg_load - this_load) * this->cpu_power)
			/ SCHED_LOAD_SCALE;

	/*
	 * if *imbalance is less than the average load per runnable task
	 * there is no gaurantee that any tasks will be moved so we'll have
	 * a think about bumping its value to force at least one task to be
	 * moved
	 */
	if (*imbalance < busiest_load_per_task) {
		unsigned long tmp, pwr_now, pwr_move;
		unsigned int imbn;

small_imbalance:
		pwr_move = pwr_now = 0;
		imbn = 2;
		if (this_nr_running) {
			this_load_per_task /= this_nr_running;
			if (busiest_load_per_task > this_load_per_task)
				imbn = 1;
		} else
			this_load_per_task = SCHED_LOAD_SCALE;

		if (max_load - this_load >= busiest_load_per_task * imbn) {
			*imbalance = busiest_load_per_task;
			return busiest;
		}

		/*
		 * OK, we don't have enough imbalance to justify moving tasks,
		 * however we may be able to increase total CPU power used by
		 * moving them.
		 */

		pwr_now += busiest->cpu_power *
			min(busiest_load_per_task, max_load);
		pwr_now += this->cpu_power *
			min(this_load_per_task, this_load);
		pwr_now /= SCHED_LOAD_SCALE;

		/* Amount of load we'd subtract */
		tmp = busiest_load_per_task * SCHED_LOAD_SCALE /
			busiest->cpu_power;
		if (max_load > tmp)
			pwr_move += busiest->cpu_power *
				min(busiest_load_per_task, max_load - tmp);

		/* Amount of load we'd add */
		if (max_load * busiest->cpu_power <
				busiest_load_per_task * SCHED_LOAD_SCALE)
			tmp = max_load * busiest->cpu_power / this->cpu_power;
		else
			tmp = busiest_load_per_task * SCHED_LOAD_SCALE /
				this->cpu_power;
		pwr_move += this->cpu_power *
			min(this_load_per_task, this_load + tmp);
		pwr_move /= SCHED_LOAD_SCALE;

		/* Move if we gain throughput */
		if (pwr_move <= pwr_now)
			goto out_balanced;

		*imbalance = busiest_load_per_task;
	}

	return busiest;

out_balanced:
#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
	if (idle == NOT_IDLE || !(sd->flags & SD_POWERSAVINGS_BALANCE))
		goto ret;

	if (this == group_leader && group_leader != group_min) {
		*imbalance = min_load_per_task;
		return group_min;
	}
#endif
ret:
	*imbalance = 0;
	return NULL;
}

/*
 * find_busiest_queue - find the busiest runqueue among the cpus in group.
 */
static struct rq *
find_busiest_queue(struct sched_group *group, enum idle_type idle,
		   unsigned long imbalance, cpumask_t *cpus)
{
	struct rq *busiest = NULL, *rq;
	unsigned long max_load = 0;
	int i;

	for_each_cpu_mask(i, group->cpumask) {

		if (!cpu_isset(i, *cpus))
			continue;

		rq = cpu_rq(i);

		if (rq->nr_running == 1 && rq->raw_weighted_load > imbalance)
			continue;

		if (rq->raw_weighted_load > max_load) {
			max_load = rq->raw_weighted_load;
			busiest = rq;
		}
	}

	return busiest;
}

/*
 * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
 * so long as it is large enough.
 */
#define MAX_PINNED_INTERVAL	512

static inline unsigned long minus_1_or_zero(unsigned long n)
{
	return n > 0 ? n - 1 : 0;
}

/*
 * Check this_cpu to ensure it is balanced within domain. Attempt to move
 * tasks if there is an imbalance.
 */
static int load_balance(int this_cpu, struct rq *this_rq,
			struct sched_domain *sd, enum idle_type idle,
			int *balance)
{
	int nr_moved, all_pinned = 0, active_balance = 0, sd_idle = 0;
	struct sched_group *group;
	unsigned long imbalance;
	struct rq *busiest;
	cpumask_t cpus = CPU_MASK_ALL;
	unsigned long flags;

	/*
	 * When power savings policy is enabled for the parent domain, idle
	 * sibling can pick up load irrespective of busy siblings. In this case,
	 * let the state of idle sibling percolate up as IDLE, instead of
	 * portraying it as NOT_IDLE.
	 */
	if (idle != NOT_IDLE && sd->flags & SD_SHARE_CPUPOWER &&
	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
		sd_idle = 1;

	schedstat_inc(sd, lb_cnt[idle]);

redo:
	group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
				   &cpus, balance);

	if (*balance == 0)
		goto out_balanced;

	if (!group) {
		schedstat_inc(sd, lb_nobusyg[idle]);
		goto out_balanced;
	}

	busiest = find_busiest_queue(group, idle, imbalance, &cpus);
	if (!busiest) {
		schedstat_inc(sd, lb_nobusyq[idle]);
		goto out_balanced;
	}

	BUG_ON(busiest == this_rq);

	schedstat_add(sd, lb_imbalance[idle], imbalance);

	nr_moved = 0;
	if (busiest->nr_running > 1) {
		/*
		 * Attempt to move tasks. If find_busiest_group has found
		 * an imbalance but busiest->nr_running <= 1, the group is
		 * still unbalanced. nr_moved simply stays zero, so it is
		 * correctly treated as an imbalance.
		 */
		local_irq_save(flags);
		double_rq_lock(this_rq, busiest);
		nr_moved = move_tasks(this_rq, this_cpu, busiest,
				      minus_1_or_zero(busiest->nr_running),
				      imbalance, sd, idle, &all_pinned);
		double_rq_unlock(this_rq, busiest);
		local_irq_restore(flags);

		/* All tasks on this runqueue were pinned by CPU affinity */
		if (unlikely(all_pinned)) {
			cpu_clear(cpu_of(busiest), cpus);
			if (!cpus_empty(cpus))
				goto redo;
			goto out_balanced;
		}
	}

	if (!nr_moved) {
		schedstat_inc(sd, lb_failed[idle]);
		sd->nr_balance_failed++;

		if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) {

			spin_lock_irqsave(&busiest->lock, flags);

			/* don't kick the migration_thread, if the curr
			 * task on busiest cpu can't be moved to this_cpu
			 */
			if (!cpu_isset(this_cpu, busiest->curr->cpus_allowed)) {
				spin_unlock_irqrestore(&busiest->lock, flags);
				all_pinned = 1;
				goto out_one_pinned;
			}

			if (!busiest->active_balance) {
				busiest->active_balance = 1;
				busiest->push_cpu = this_cpu;
				active_balance = 1;
			}
			spin_unlock_irqrestore(&busiest->lock, flags);
			if (active_balance)
				wake_up_process(busiest->migration_thread);

			/*
			 * We've kicked active balancing, reset the failure
			 * counter.
			 */
			sd->nr_balance_failed = sd->cache_nice_tries+1;
		}
	} else
		sd->nr_balance_failed = 0;

	if (likely(!active_balance)) {
		/* We were unbalanced, so reset the balancing interval */
		sd->balance_interval = sd->min_interval;
	} else {
		/*
		 * If we've begun active balancing, start to back off. This
		 * case may not be covered by the all_pinned logic if there
		 * is only 1 task on the busy runqueue (because we don't call
		 * move_tasks).
		 */
		if (sd->balance_interval < sd->max_interval)
			sd->balance_interval *= 2;
	}

	if (!nr_moved && !sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
		return -1;
	return nr_moved;

out_balanced:
	schedstat_inc(sd, lb_balanced[idle]);

	sd->nr_balance_failed = 0;

out_one_pinned:
	/* tune up the balancing interval */
	if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) ||
			(sd->balance_interval < sd->max_interval))
		sd->balance_interval *= 2;

	if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
		return -1;
	return 0;
}

/*
 * Check this_cpu to ensure it is balanced within domain. Attempt to move
 * tasks if there is an imbalance.
 *
 * Called from schedule when this_rq is about to become idle (NEWLY_IDLE).
 * this_rq is locked.
 */
static int
load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
{
	struct sched_group *group;
	struct rq *busiest = NULL;
	unsigned long imbalance;
	int nr_moved = 0;
	int sd_idle = 0;
	cpumask_t cpus = CPU_MASK_ALL;

	/*
	 * When power savings policy is enabled for the parent domain, idle
	 * sibling can pick up load irrespective of busy siblings. In this case,
	 * let the state of idle sibling percolate up as IDLE, instead of
	 * portraying it as NOT_IDLE.
	 */
	if (sd->flags & SD_SHARE_CPUPOWER &&
	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
		sd_idle = 1;

	schedstat_inc(sd, lb_cnt[NEWLY_IDLE]);
redo:
	group = find_busiest_group(sd, this_cpu, &imbalance, NEWLY_IDLE,
				   &sd_idle, &cpus, NULL);
	if (!group) {
		schedstat_inc(sd, lb_nobusyg[NEWLY_IDLE]);
		goto out_balanced;
	}

	busiest = find_busiest_queue(group, NEWLY_IDLE, imbalance,
				&cpus);
	if (!busiest) {
		schedstat_inc(sd, lb_nobusyq[NEWLY_IDLE]);
		goto out_balanced;
	}

	BUG_ON(busiest == this_rq);

	schedstat_add(sd, lb_imbalance[NEWLY_IDLE], imbalance);

	nr_moved = 0;
	if (busiest->nr_running > 1) {
		/* Attempt to move tasks */
		double_lock_balance(this_rq, busiest);
		nr_moved = move_tasks(this_rq, this_cpu, busiest,
					minus_1_or_zero(busiest->nr_running),
					imbalance, sd, NEWLY_IDLE, NULL);
		spin_unlock(&busiest->lock);

		if (!nr_moved) {
			cpu_clear(cpu_of(busiest), cpus);
			if (!cpus_empty(cpus))
				goto redo;
		}
	}

	if (!nr_moved) {
		schedstat_inc(sd, lb_failed[NEWLY_IDLE]);
		if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
		    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
			return -1;
	} else
		sd->nr_balance_failed = 0;

	return nr_moved;

out_balanced:
	schedstat_inc(sd, lb_balanced[NEWLY_IDLE]);
	if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
		return -1;
	sd->nr_balance_failed = 0;

	return 0;
}

/*
 * idle_balance is called by schedule() if this_cpu is about to become
 * idle. Attempts to pull tasks from other CPUs.
 */
static void idle_balance(int this_cpu, struct rq *this_rq)
{
	struct sched_domain *sd;
	int pulled_task = 0;
	unsigned long next_balance = jiffies + 60 *  HZ;

	for_each_domain(this_cpu, sd) {
		if (sd->flags & SD_BALANCE_NEWIDLE) {
			/* If we've pulled tasks over stop searching: */
			pulled_task = load_balance_newidle(this_cpu,
							this_rq, sd);
			if (time_after(next_balance,
				  sd->last_balance + sd->balance_interval))
				next_balance = sd->last_balance
						+ sd->balance_interval;
			if (pulled_task)
				break;
		}
	}
	if (!pulled_task)
		/*
		 * We are going idle. next_balance may be set based on
		 * a busy processor. So reset next_balance.
		 */
		this_rq->next_balance = next_balance;
}

/*
 * active_load_balance is run by migration threads. It pushes running tasks
 * off the busiest CPU onto idle CPUs. It requires at least 1 task to be
 * running on each physical CPU where possible, and avoids physical /
 * logical imbalances.
 *
 * Called with busiest_rq locked.
 */
static void active_load_balance(struct rq *busiest_rq, int busiest_cpu)
{
	int target_cpu = busiest_rq->push_cpu;
	struct sched_domain *sd;
	struct rq *target_rq;

	/* Is there any task to move? */
	if (busiest_rq->nr_running <= 1)
		return;

	target_rq = cpu_rq(target_cpu);

	/*
	 * This condition is "impossible", if it occurs
	 * we need to fix it.  Originally reported by
	 * Bjorn Helgaas on a 128-cpu setup.
	 */
	BUG_ON(busiest_rq == target_rq);

	/* move a task from busiest_rq to target_rq */
	double_lock_balance(busiest_rq, target_rq);

	/* Search for an sd spanning us and the target CPU. */
	for_each_domain(target_cpu, sd) {
		if ((sd->flags & SD_LOAD_BALANCE) &&
		    cpu_isset(busiest_cpu, sd->span))
				break;
	}

	if (likely(sd)) {
		schedstat_inc(sd, alb_cnt);

		if (move_tasks(target_rq, target_cpu, busiest_rq, 1,
			       RTPRIO_TO_LOAD_WEIGHT(100), sd, SCHED_IDLE,
			       NULL))
			schedstat_inc(sd, alb_pushed);
		else
			schedstat_inc(sd, alb_failed);
	}
	spin_unlock(&target_rq->lock);
}

static void update_load(struct rq *this_rq)
{
	unsigned long this_load;
	unsigned int i, scale;

	this_load = this_rq->raw_weighted_load;

	/* Update our load: */
	for (i = 0, scale = 1; i < 3; i++, scale += scale) {
		unsigned long old_load, new_load;

		/* scale is effectively 1 << i now, and >> i divides by scale */

		old_load = this_rq->cpu_load[i];
		new_load = this_load;
		/*
		 * Round up the averaging division if load is increasing. This
		 * prevents us from getting stuck on 9 if the load is 10, for
		 * example.
		 */
		if (new_load > old_load)
			new_load += scale-1;
		this_rq->cpu_load[i] = (old_load*(scale-1) + new_load) >> i;
	}
}

/*
 * run_rebalance_domains is triggered when needed from the scheduler tick.
 *
 * It checks each scheduling domain to see if it is due to be balanced,
 * and initiates a balancing operation if so.
 *
 * Balancing parameters are set up in arch_init_sched_domains.
 */
static DEFINE_SPINLOCK(balancing);

static void run_rebalance_domains(struct softirq_action *h)
{
	int this_cpu = smp_processor_id(), balance = 1;
	struct rq *this_rq = cpu_rq(this_cpu);
	unsigned long interval;
	struct sched_domain *sd;
	/*
	 * We are idle if there are no processes running. This
	 * is valid even if we are the idle process (SMT).
	 */
	enum idle_type idle = !this_rq->nr_running ?
				SCHED_IDLE : NOT_IDLE;
	/* Earliest time when we have to call run_rebalance_domains again */
	unsigned long next_balance = jiffies + 60*HZ;

	for_each_domain(this_cpu, sd) {
		if (!(sd->flags & SD_LOAD_BALANCE))
			continue;

		interval = sd->balance_interval;
		if (idle != SCHED_IDLE)
			interval *= sd->busy_factor;

		/* scale ms to jiffies */
		interval = msecs_to_jiffies(interval);
		if (unlikely(!interval))
			interval = 1;

		if (sd->flags & SD_SERIALIZE) {
			if (!spin_trylock(&balancing))
				goto out;
		}

		if (time_after_eq(jiffies, sd->last_balance + interval)) {
			if (load_balance(this_cpu, this_rq, sd, idle, &balance)) {
				/*
				 * We've pulled tasks over so either we're no
				 * longer idle, or one of our SMT siblings is
				 * not idle.
				 */
				idle = NOT_IDLE;
			}
			sd->last_balance = jiffies;
		}
		if (sd->flags & SD_SERIALIZE)
			spin_unlock(&balancing);
out:
		if (time_after(next_balance, sd->last_balance + interval))
			next_balance = sd->last_balance + interval;

		/*
		 * Stop the load balance at this level. There is another
		 * CPU in our sched group which is doing load balancing more
		 * actively.
		 */
		if (!balance)
			break;
	}
	this_rq->next_balance = next_balance;
}
#else
/*
 * on UP we do not need to balance between CPUs:
 */
static inline void idle_balance(int cpu, struct rq *rq)
{
}
#endif

DEFINE_PER_CPU(struct kernel_stat, kstat);

EXPORT_PER_CPU_SYMBOL(kstat);

/*
 * This is called on clock ticks and on context switches.
 * Bank in p->sched_time the ns elapsed since the last tick or switch.
 */
static inline void
update_cpu_clock(struct task_struct *p, struct rq *rq, unsigned long long now)
{
	p->sched_time += now - p->last_ran;
	p->last_ran = rq->most_recent_timestamp = now;
}