aboutsummaryrefslogblamecommitdiffstats
path: root/net/core/neighbour.c
blob: 652da63690376b52d084a901310db39f4258aca3 (plain) (tree)
1
2
3
4
5
6
7
8
                                            






                                                      




                                                                          

                                           
                       
                           



                         





                            
                              
                          
                    

                     
                         
                        

                            
                         
                       
                             
                         
 

                               
             
                     




                                                 


                                   
                                                      


                                                                        

                                                            
 
                     
                                                      
      


























                                                                          

   
                                                                        




                         




                                                              
                                                  
                                                  
                                                              


                             







                                                                     
                                                               
 
                                     
 








                                                
                                                     
 
                                        
 

                                     
 

                                                                           
           

                                                        

                                              
                                           

                                                
                                                    



                                                                              


                                       
 
 
                                                                        

                                                 
                        


                                            
                          






                                                                               
                          

                            

                  

 

                                                                       



                             
                                             




                                                                               
                                   
























                                                                              
                                                     




                              

                                                   

                                                                        
                                  
                       



                                                  
 




                                                                  
                                                           
                                                         






                                                               









                                    









                                                                     



















                                                         

                                                                            

              
                                     
 


                                                                     
                                                      

                                                                    
 

                                                                                



                                                   



                                                                        


                                                                              

                                             
                                           
                                                             








                                                                    
                                                                 
                                                           




                                                                 
                                                                       

                                               
                                                     

                 
 
 


                                                                      
                                         

                                    
                                
 

                                                                          

                                  
                                             
                                           




                                              












                                                                       
                            
 

                                                             
                                                         




                                    
                           


                                                          



                                                          



                                                                              
                                         
                 

         
         
                                                                       


                                 
                                             
                              
                                  


                                            
                                     
                                                           
                                                       


                                          
                                    
                              
                                    

                                  



                 
                            
                                             


                 

                                      
                                  

 
                                                                    
 
                                                                
                                     
                                         
              
 


                                                
                                
                                                    
                
                                                     

                                                                   
                                                             
         


                            
         
                                    
                                

                                                      


                   
                                                      
 


                                                                            
                                                                          
                                                             
 
                                
                               

                                       
                                                                    
         
                   

 
                                                                        
                                                                        
 

                                                   


                                              

                                                                         
                                              

                               
 
                                                          

                                           

                                                                                



                                                                
 
                                                            







                                                                              

                 
 


                                                     





                                                                         
 

                                           
                           

                                                 
                                                       

                                                
         
 
                             

                 
                            
 

                                                                              

                            
                                            
                     
                                     


                                           

                                           
                                                                                  



                                                                 
                                                             
                                                   
                                                               
                                         



                                                        
 
                             

                 
                                  
 


                                                                 
                                                                            
 
                                                                              
                     
                                            
                  
                                     
 

                                                              














                                                                    
                                                   
                                                                     





                                               






                                                     
                                                                                 

                                  

                                                                     
 

                                                                
 
                                                                                           





                                      




                                                                         
                                                                                          

                                               




                                            
                    
                            

                                                             

                              



                                                                                   
                                    
                                                 





                                    

                                             


                         





                                                                           
                              
 
                                                              
 
                                                    



                                     

                        
 


                                                                     
                                                                   


                                                                     
                                                     
                                                 
                                               

                                 
         

                    
 


                                                                          
                                            



                                                              
 
                                   
 

                                                                      


                                                                      
                                            
                                                  

                                 

                                                           
                                   

                        

                         

                      



                                                      
                        
                                 



















                                                        
                             

 
                                                                             


                                         
                                            
                                                  



                                                                   
                                                                      
                                                 













                                                    

                                                            
 
                                                       






                                                    

                                                   




                                         









                                            


                       



                                                             
                                                  

                                           






                                                   

                                            


                                                   
                                                                  




                                   
                                              
 


                                             
                                       
 
                                               
                                                               
 
                     

                                      
                                                       

                                         
                              
 
                             







                                                  
                                                       

                                           








                                                  
                                                       

                                                     

 
                                                         
 
                                                                                       

                                    
                       
                                     


                                                    
                                  

                                                                     




                                                                         
                                                             
                                      
                                         
                                                              
                                           
                                                                                         

         


                                                         
                                                       
                                           
 

                                                                        
                                           
 
                                             
 
                                             

                                                                       


                                                       
 

                                                               
 
                                                             
                                                   
                                                                                                 
                                              
                                                   



                                                             
                                               

         








                                                                     

                                                                             
         
    


                                                                            
           
                                                                    
                                                                                
                                    




                                                           


                                                                         

 
                                                     

                               



                                                     
                                                    












                                                                        
                                             
                                       

 


                                                
                                                               

                                                        
                                                 
                                   

                                                
                                   
                         

 

                                                        
                                                     

                                
                                                              
                           







                                 
                                    
                         

                                    
                                       
                                                                                      
                                                                         

                                                                               

                                                                                       
                                                                     
                                                     
                                                 
                                             
                                                                               
                        
                                                                       
                                                     
                                                 
                                             
                                   

                                       
                                       

                                                                                
                                                                           
                                                         
                                                 
                                             
                                   

                                                                               
                                                                    
                                                     
                                                 
                                                      
                                   
                                                                           


                                              
                                                                   



                                                                     

                                              
                                        
                         


                                              

                                                      

                                                    

                                                              
                                   
                
    

                                           
 
                   
                                              
 

                                            





                                                                    
                                     





                                                                       

                              
 
                                                                 

                                                           

                                                          

                                                                          
                                               
                                                              
                                             

                                                                               

                                                     

                                                      
                                                 

                                                      
                                       


                                                  
                                                             
                                       
                                             
                                         

                                                                           



                                                 
                                                                           
                                                                          
                                                     
 
                                                                        


                                                                             
                                                
                                                                                 
                         
                                           
                                                                 
                                                                    



                       




                                           
                                               
                  





                                         
                                              
                 
 
                                  
 
                                                     

                            
                                                                                         



                                                              

                     
                                
                                            
                                                       
                                                          
                                                         












                                                                      
                                                               
                                                   

                                                                        
                                                                    






                                                                      


                                                                    
 
                                      

                
                       


                                

                                                                 





                                    
                                              

                                                

                                                                     
                         
         
 
                                                                           
 



                                             
                                       
                        
                                         
                                                           



                                                












                                                                  
                                        






                                                                

                                                                              
                                 
                 


                                   





                                                                           














                                                                                

                                                                      



                                          
                                                                          


                                                                              
                                              
                                         
 

                                       

                                                      
                                       

                                                                        

                                                                               
                                       
                           


                                  
                                               
                                                          
                                                 


                                                    
                                                                                          
                           













                                                                          

                                                             
                                                      

                                        













                                                                                
                                            

                                                  

                                          

                                                    
                                                     
                                               

         

                                                              
                                      
 
                                                              

                                            
                   
                                                      
 

                                            

                   





                                                                          
                            
 




                                                                            

                        


                                             

                                                            




                                                                         






                                                                           
                                                      
                                                         

                     
                              
 
                                         
                                              
 

                                        
                                     

                                
 


                                                              

                                                    
 
                                  

 

                       
                                                                      
 

                   


                                                    
                                 
 
                                                                           
                                             
 
                    
                                                                 



                                                                             
 
                             
                                                 




                                           




                       
                                    


                                          
                                                                        
 
                                            
                         
                
 
            
                                                         




                                                                     
                     
                                          





                               
                                      
 





                                                                     
                                                     
 
                                                                  

                                    
                                


                                          

                                                            
 
                                
                                                          
 
                                                             

                                                                    
                                                     

                                                  
                                               
                         














                                                                   

                                                         
                                                                     
 
                                                               


                               


                                                 





                                                                      
                          




                                                 
                              
 
                                                                             



                                                                                   
                                                        
                                                                                                
                                                                    




                                 



                                                              
                              

                                                           
 
                                                         
                
                                        
                                            
                                   
                                                                                         

                              
                                         
                                       
 
                                                                           
                                     

                                    
                 
 
                                          
                                                     
                                            

                                                   


                 
                                 










                                                                            


                                           

                               
                                    


                                                         
 
                                   
 
                                                          



                     

                                                           


                                                                       



                                    
                                         
                                      
                                                     
                                               
                                            
                                   
                                                                                             
 


                                                                  
 
                     

                                                                     
                                                                

      
                                                        

                                                                       
                                                         
 
                                             

                                                                





                                                                                 
                                
                                                                 

                                                                    
                                                               

                                                        


                                                               
 
                                  
 
                                
 
                                                         
 
                                   
                                                                    
                                                



                                              
                                               
 

                                                              
                        



                                  

                                                           


                                

                 
                                 
 


















                                                       









                                                                              
                                                     

  

                                                                  
 
                                            

                                
                                
                                
                                      
                          
 
                      
                                          

                         
                                                               

                                                                        
                         
         


                               
                                                                





                                      


                                                
 

                                                                  
                         
         
 



                                                                       
 

                         
 


                                                           
                         
         
 


                                                                            
                                  
                             

                                     
 



                   

                                                               
 

                                                                    
                                            

                                     

                                      

                                
                        
                
 
                      

                                                                    
                    

                         
                      

                                                                        
                         
         


                               
                                                                




                                      

                                                                                
                                 
                 

         


                                                
 

                                                                  
                         

         

                                                                  
 
                             
                                                        
 






                                                          

                                                        



                                
 

                                                               
                         
         
 




                                                             

                                            

                                    

                                                         
                                 

                 


                                                                             







                                                    
                                 
                 
 
                                                        

                                                                     

         


                                                    


                                                 



                                              

                                                                          



                                           

                             



                   

                                                                              

                            
                                                      

                                
 

                                                                     
                                                                            

                                                             

                                                                           






                                                                                           

                                                            

                                                                           
                                                         
                                                                              
                                                  
                                                                       
                                                      
                                                                           
                                                  
                                                                       
                                                   
                                                                        
                                                 
                                                                      
                                              
                                                                 
                                     
                                       
 
                

                                   

 

                                                                           



                              

                                                                     
                                 
 
                                 


                                          

                                
 
                                                      
                                                                               



                                                              

                                            

                                                         
                                             





                                                                                


                                                                        

                                                   
                                                     
                                                                  

                                     

                                                                 







                                               
                                            

                                                    










                                                                                
                                                                           

                 

                                                                       
                                             



                                                      
                                     

                                   

                            
 
                
                                   

                               

 

                                                            
                                                              

                                                               



                              

                                                                     
                                 
 
                                 


                                          

                                
 


                                                          

                                   

                            
       
                                   

                               
 
 
                                                                 







                                                         
                                                                   





                                                              
                                                              








                                                              

                                                                  
 
                                            
                                

                                      

                           
 

                                                                        

                            
 





                                    




                                                        

                                                                              

                                                              
                              
                 

         

                               
 
          




                                                                     

                                                
                                      
                                   
 


                                                                               

                                             
 

                                                                  
 
                                                          

                                      
                                             
                 
 


                                                  
 

                                             


                                                                           

                                                  

                                                                   

                                              

                                                                   

                                              

                                                                   

                                                

                                                                   

                                                

                                                                   
                                      



                                                                   
                                                       

                                                                     





                                                                                                 

                                                

                                                                     

                                                    

                                                                     
                                                                                             

                                                

                                                                     

                                                 

                                                                     

                                               

                                                                     

                                            

                                                                     



                                      
 





                                                         

                                                                
 

                                                                
 

                                                                
 

                                                                       


                
                
                                    
       


                   























                                                                                                   
                                                                               
 
                                             
                                            


                                     

                                







                                                                    
 
                                                        

                                      



                                         
                                                                         

                                 
                                                                            
                                                                       
                                                        

                              


                                                                     
                                                             

                                         

                                              
 
                                                                 
                                                                                
                                                                    
                                                                     
                                                                      
                                         

                               

                 
                               

         

                           


                        
 

                                                                          

                                    
                                




                                                                  
                                 
 

                                              

                             


                                               
 

                                                                           


                                            







                                                                                

         


                                                                      
                                                             

                                     


                                                                        
 


                                                                              

                            

                

                               

 















                                                                           
                                       
                                                          

                                    

                                                         
 


                                                                        

                            





                               
                                                                       

                                                              
                                                          
 
 






                                                                         
                                                               





                                                     

                                                                          
                                                               




                            




                          
                                                                         

                                                             
 
                                            


                                           
                                     
                                         
 

                                                  
 


                                           
                                                        

                                  


                                                                           

                                                                         

                                                                              
                                          
                                                                               
                                                               
                                                         
                                                         


                                         
     
                              
                 


                      
                             




                          
                                                                          

                                                              




                                            



                                                  


                                 
                                                  


                                                                          
                                                                
                                          


                                                                              
                                                                                
                                                               
                                                                            

















                                                           

















                                                                                           
                                                      



                                                                                                     




                                                                                                    


                                                                              
                

                                                                           










                                                                    


                                                             












                                                                                                         
                                                                            
 

                                             

                                
                      
                
 
                                                                    



                                                                    

                                                                      

                          



                                                                               

                          




                                               




                                                                     
                          
                                                                       
                    
                                                                      

                              
         




                        

























                                                                                            

                                                                          

































































                                                                                                          
                                                           




















































































                                                                                  


                                                                                                  
                                     
 


                                           
                                                  
                                                                  

                                    


                                                                      

                                      

                                







                                                             
                                     
 

                                                                     
                                                                  

                                            
 
                                               

                                                                                




                                             


                                                                              
                                                   


                                               

                                                             




                                        
                                                 

                                                     

                                              


                                        
                                          

                                 
                                   






                                                                     


                                                                      

                                             
                                           
                 
                                                
                                     
         






                                                                     







                          




                                                              
                                            
                                                  
                                   
                   

                                             
                                                                     
                                                                  

                           
                                                          
                                          











                                                                            

                                                        














                                                             
                                            
                                                  





                                                               
                                        


                           
                                                          
                                          










                                                                               

                                                        




                              
                                                              

                              
                                                                         











                                                                         
                         











                                                                  
                                            






                                                               
                                                          
                                      












                                                                    
                                            

                                             



                                                     



                                                       
                                                          
                                      














                                                                             
                         












                                                                 
                             
 
                                         
                                                          
                                                  




                                                                                                               
                             
                          

                                                     




                                                                

                                                  
                              
 
                                                                    








                                                                
                                          




















                                                            
                             
                          
 



                                                     
                             






                                                                    
                                                                  



                                       
 
                                                     









                                                                            
                                                                  

                
                                                   














                                                              
                                                                  


                                        
                                                                                                                                                                                                       



                                                                       
                                                                 














                                              
                                      

                                      




                     
                                                         




                                       

                           

                                                                    
 
                                          
                            
                           
 
                                                        
                        
                            
 
                                                           





                                                                 

                                                                  

                    
                                                         

 
                                      
 
                                                          
 
                            

                    
                                                                  
 

                                                                           

                      
                                    
 
                                 
                                     
                         



                                                                    




                                                                       


                                                                          

                         
                                                       


                                                       























                                                                         
                                             





                                                

                                                                             



                                                            




                                                                            
                
 

                                    
 


                                                                    

 


                                                                        



                                                                






                                                                 



                                                                        






                                                                               



                                                                               





                                                                    



                                                                           






                                                                           



                                                                  

 
























                                                                                     















                                                                                     
                                                                               

                                                       
                                                                                      

                                                   
                                                                                  

                                                                     
                                                                                       

                                                                     
                                                                                       
 

                                               
                                                       
                                         
                       


                                                                              
                                                                                  











                                                                                                                            
                                           


                                                        
                                                                
                  
                                          


                                                       

                                                         
                                                               
                  
                                          


                                                       

                                                         
                                                               
                  
                                          


                                                       

                                                         
                                                               
                  
                   



                                                                        
                                                
 
              
                                     
                                    
                                                                       
                     
 
                                                                    
               

                         
                                                     
                                                  
                                              
                                            
         


                                            
                                               

                                                                     
                
                                                 
                                            



                                                                              

         
                      
                                 
                                                                             
                                   
                                                                                    
                                                  
                                                                                
                                                     
                                                                                       












                                                                                       

         



                                                         










                                        

                                                                   
                          
                                                                                   
                              
                          
 


                            
     
                 

                        
 
                                     





                                                               
                                                              


                         
                                       


                           

                                  

                                                                      
                                                                              
 
                                                                           

                                                                         




                            
// SPDX-License-Identifier: GPL-2.0-or-later
/*
 *	Generic address resolution entity
 *
 *	Authors:
 *	Pedro Roque		<roque@di.fc.ul.pt>
 *	Alexey Kuznetsov	<kuznet@ms2.inr.ac.ru>
 *
 *	Fixes:
 *	Vitaly E. Lavrov	releasing NULL neighbor in neigh_add.
 *	Harald Welte		Add neighbour cache statistics like rtstat
 */

#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

#include <linux/slab.h>
#include <linux/kmemleak.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/socket.h>
#include <linux/netdevice.h>
#include <linux/proc_fs.h>
#ifdef CONFIG_SYSCTL
#include <linux/sysctl.h>
#endif
#include <linux/times.h>
#include <net/net_namespace.h>
#include <net/neighbour.h>
#include <net/arp.h>
#include <net/dst.h>
#include <net/sock.h>
#include <net/netevent.h>
#include <net/netlink.h>
#include <linux/rtnetlink.h>
#include <linux/random.h>
#include <linux/string.h>
#include <linux/log2.h>
#include <linux/inetdevice.h>
#include <net/addrconf.h>

#include <trace/events/neigh.h>

#define DEBUG
#define NEIGH_DEBUG 1
#define neigh_dbg(level, fmt, ...)		\
do {						\
	if (level <= NEIGH_DEBUG)		\
		pr_debug(fmt, ##__VA_ARGS__);	\
} while (0)

#define PNEIGH_HASHMASK		0xF

static void neigh_timer_handler(struct timer_list *t);
static void __neigh_notify(struct neighbour *n, int type, int flags,
			   u32 pid);
static void neigh_update_notify(struct neighbour *neigh, u32 nlmsg_pid);
static int pneigh_ifdown_and_unlock(struct neigh_table *tbl,
				    struct net_device *dev);

#ifdef CONFIG_PROC_FS
static const struct seq_operations neigh_stat_seq_ops;
#endif

/*
   Neighbour hash table buckets are protected with rwlock tbl->lock.

   - All the scans/updates to hash buckets MUST be made under this lock.
   - NOTHING clever should be made under this lock: no callbacks
     to protocol backends, no attempts to send something to network.
     It will result in deadlocks, if backend/driver wants to use neighbour
     cache.
   - If the entry requires some non-trivial actions, increase
     its reference count and release table lock.

   Neighbour entries are protected:
   - with reference count.
   - with rwlock neigh->lock

   Reference count prevents destruction.

   neigh->lock mainly serializes ll address data and its validity state.
   However, the same lock is used to protect another entry fields:
    - timer
    - resolution queue

   Again, nothing clever shall be made under neigh->lock,
   the most complicated procedure, which we allow is dev->hard_header.
   It is supposed, that dev->hard_header is simplistic and does
   not make callbacks to neighbour tables.
 */

static int neigh_blackhole(struct neighbour *neigh, struct sk_buff *skb)
{
	kfree_skb(skb);
	return -ENETDOWN;
}

static void neigh_cleanup_and_release(struct neighbour *neigh)
{
	if (neigh->parms->neigh_cleanup)
		neigh->parms->neigh_cleanup(neigh);

	trace_neigh_cleanup_and_release(neigh, 0);
	__neigh_notify(neigh, RTM_DELNEIGH, 0, 0);
	call_netevent_notifiers(NETEVENT_NEIGH_UPDATE, neigh);
	neigh_release(neigh);
}

/*
 * It is random distribution in the interval (1/2)*base...(3/2)*base.
 * It corresponds to default IPv6 settings and is not overridable,
 * because it is really reasonable choice.
 */

unsigned long neigh_rand_reach_time(unsigned long base)
{
	return base ? (prandom_u32() % base) + (base >> 1) : 0;
}
EXPORT_SYMBOL(neigh_rand_reach_time);

static void neigh_mark_dead(struct neighbour *n)
{
	n->dead = 1;
	if (!list_empty(&n->gc_list)) {
		list_del_init(&n->gc_list);
		atomic_dec(&n->tbl->gc_entries);
	}
}

static void neigh_update_gc_list(struct neighbour *n)
{
	bool on_gc_list, exempt_from_gc;

	write_lock_bh(&n->tbl->lock);
	write_lock(&n->lock);

	/* remove from the gc list if new state is permanent or if neighbor
	 * is externally learned; otherwise entry should be on the gc list
	 */
	exempt_from_gc = n->nud_state & NUD_PERMANENT ||
			 n->flags & NTF_EXT_LEARNED;
	on_gc_list = !list_empty(&n->gc_list);

	if (exempt_from_gc && on_gc_list) {
		list_del_init(&n->gc_list);
		atomic_dec(&n->tbl->gc_entries);
	} else if (!exempt_from_gc && !on_gc_list) {
		/* add entries to the tail; cleaning removes from the front */
		list_add_tail(&n->gc_list, &n->tbl->gc_list);
		atomic_inc(&n->tbl->gc_entries);
	}

	write_unlock(&n->lock);
	write_unlock_bh(&n->tbl->lock);
}

static bool neigh_update_ext_learned(struct neighbour *neigh, u32 flags,
				     int *notify)
{
	bool rc = false;
	u8 ndm_flags;

	if (!(flags & NEIGH_UPDATE_F_ADMIN))
		return rc;

	ndm_flags = (flags & NEIGH_UPDATE_F_EXT_LEARNED) ? NTF_EXT_LEARNED : 0;
	if ((neigh->flags ^ ndm_flags) & NTF_EXT_LEARNED) {
		if (ndm_flags & NTF_EXT_LEARNED)
			neigh->flags |= NTF_EXT_LEARNED;
		else
			neigh->flags &= ~NTF_EXT_LEARNED;
		rc = true;
		*notify = 1;
	}

	return rc;
}

static bool neigh_del(struct neighbour *n, struct neighbour __rcu **np,
		      struct neigh_table *tbl)
{
	bool retval = false;

	write_lock(&n->lock);
	if (refcount_read(&n->refcnt) == 1) {
		struct neighbour *neigh;

		neigh = rcu_dereference_protected(n->next,
						  lockdep_is_held(&tbl->lock));
		rcu_assign_pointer(*np, neigh);
		neigh_mark_dead(n);
		retval = true;
	}
	write_unlock(&n->lock);
	if (retval)
		neigh_cleanup_and_release(n);
	return retval;
}

bool neigh_remove_one(struct neighbour *ndel, struct neigh_table *tbl)
{
	struct neigh_hash_table *nht;
	void *pkey = ndel->primary_key;
	u32 hash_val;
	struct neighbour *n;
	struct neighbour __rcu **np;

	nht = rcu_dereference_protected(tbl->nht,
					lockdep_is_held(&tbl->lock));
	hash_val = tbl->hash(pkey, ndel->dev, nht->hash_rnd);
	hash_val = hash_val >> (32 - nht->hash_shift);

	np = &nht->hash_buckets[hash_val];
	while ((n = rcu_dereference_protected(*np,
					      lockdep_is_held(&tbl->lock)))) {
		if (n == ndel)
			return neigh_del(n, np, tbl);
		np = &n->next;
	}
	return false;
}

static int neigh_forced_gc(struct neigh_table *tbl)
{
	int max_clean = atomic_read(&tbl->gc_entries) - tbl->gc_thresh2;
	unsigned long tref = jiffies - 5 * HZ;
	struct neighbour *n, *tmp;
	int shrunk = 0;

	NEIGH_CACHE_STAT_INC(tbl, forced_gc_runs);

	write_lock_bh(&tbl->lock);

	list_for_each_entry_safe(n, tmp, &tbl->gc_list, gc_list) {
		if (refcount_read(&n->refcnt) == 1) {
			bool remove = false;

			write_lock(&n->lock);
			if ((n->nud_state == NUD_FAILED) ||
			    time_after(tref, n->updated))
				remove = true;
			write_unlock(&n->lock);

			if (remove && neigh_remove_one(n, tbl))
				shrunk++;
			if (shrunk >= max_clean)
				break;
		}
	}

	tbl->last_flush = jiffies;

	write_unlock_bh(&tbl->lock);

	return shrunk;
}

static void neigh_add_timer(struct neighbour *n, unsigned long when)
{
	neigh_hold(n);
	if (unlikely(mod_timer(&n->timer, when))) {
		printk("NEIGH: BUG, double timer add, state is %x\n",
		       n->nud_state);
		dump_stack();
	}
}

static int neigh_del_timer(struct neighbour *n)
{
	if ((n->nud_state & NUD_IN_TIMER) &&
	    del_timer(&n->timer)) {
		neigh_release(n);
		return 1;
	}
	return 0;
}

static void pneigh_queue_purge(struct sk_buff_head *list)
{
	struct sk_buff *skb;

	while ((skb = skb_dequeue(list)) != NULL) {
		dev_put(skb->dev);
		kfree_skb(skb);
	}
}

static void neigh_flush_dev(struct neigh_table *tbl, struct net_device *dev,
			    bool skip_perm)
{
	int i;
	struct neigh_hash_table *nht;

	nht = rcu_dereference_protected(tbl->nht,
					lockdep_is_held(&tbl->lock));

	for (i = 0; i < (1 << nht->hash_shift); i++) {
		struct neighbour *n;
		struct neighbour __rcu **np = &nht->hash_buckets[i];

		while ((n = rcu_dereference_protected(*np,
					lockdep_is_held(&tbl->lock))) != NULL) {
			if (dev && n->dev != dev) {
				np = &n->next;
				continue;
			}
			if (skip_perm && n->nud_state & NUD_PERMANENT) {
				np = &n->next;
				continue;
			}
			rcu_assign_pointer(*np,
				   rcu_dereference_protected(n->next,
						lockdep_is_held(&tbl->lock)));
			write_lock(&n->lock);
			neigh_del_timer(n);
			neigh_mark_dead(n);
			if (refcount_read(&n->refcnt) != 1) {
				/* The most unpleasant situation.
				   We must destroy neighbour entry,
				   but someone still uses it.

				   The destroy will be delayed until
				   the last user releases us, but
				   we must kill timers etc. and move
				   it to safe state.
				 */
				__skb_queue_purge(&n->arp_queue);
				n->arp_queue_len_bytes = 0;
				n->output = neigh_blackhole;
				if (n->nud_state & NUD_VALID)
					n->nud_state = NUD_NOARP;
				else
					n->nud_state = NUD_NONE;
				neigh_dbg(2, "neigh %p is stray\n", n);
			}
			write_unlock(&n->lock);
			neigh_cleanup_and_release(n);
		}
	}
}

void neigh_changeaddr(struct neigh_table *tbl, struct net_device *dev)
{
	write_lock_bh(&tbl->lock);
	neigh_flush_dev(tbl, dev, false);
	write_unlock_bh(&tbl->lock);
}
EXPORT_SYMBOL(neigh_changeaddr);

static int __neigh_ifdown(struct neigh_table *tbl, struct net_device *dev,
			  bool skip_perm)
{
	write_lock_bh(&tbl->lock);
	neigh_flush_dev(tbl, dev, skip_perm);
	pneigh_ifdown_and_unlock(tbl, dev);

	del_timer_sync(&tbl->proxy_timer);
	pneigh_queue_purge(&tbl->proxy_queue);
	return 0;
}

int neigh_carrier_down(struct neigh_table *tbl, struct net_device *dev)
{
	__neigh_ifdown(tbl, dev, true);
	return 0;
}
EXPORT_SYMBOL(neigh_carrier_down);

int neigh_ifdown(struct neigh_table *tbl, struct net_device *dev)
{
	__neigh_ifdown(tbl, dev, false);
	return 0;
}
EXPORT_SYMBOL(neigh_ifdown);

static struct neighbour *neigh_alloc(struct neigh_table *tbl,
				     struct net_device *dev,
				     bool exempt_from_gc)
{
	struct neighbour *n = NULL;
	unsigned long now = jiffies;
	int entries;

	if (exempt_from_gc)
		goto do_alloc;

	entries = atomic_inc_return(&tbl->gc_entries) - 1;
	if (entries >= tbl->gc_thresh3 ||
	    (entries >= tbl->gc_thresh2 &&
	     time_after(now, tbl->last_flush + 5 * HZ))) {
		if (!neigh_forced_gc(tbl) &&
		    entries >= tbl->gc_thresh3) {
			net_info_ratelimited("%s: neighbor table overflow!\n",
					     tbl->id);
			NEIGH_CACHE_STAT_INC(tbl, table_fulls);
			goto out_entries;
		}
	}

do_alloc:
	n = kzalloc(tbl->entry_size + dev->neigh_priv_len, GFP_ATOMIC);
	if (!n)
		goto out_entries;

	__skb_queue_head_init(&n->arp_queue);
	rwlock_init(&n->lock);
	seqlock_init(&n->ha_lock);
	n->updated	  = n->used = now;
	n->nud_state	  = NUD_NONE;
	n->output	  = neigh_blackhole;
	seqlock_init(&n->hh.hh_lock);
	n->parms	  = neigh_parms_clone(&tbl->parms);
	timer_setup(&n->timer, neigh_timer_handler, 0);

	NEIGH_CACHE_STAT_INC(tbl, allocs);
	n->tbl		  = tbl;
	refcount_set(&n->refcnt, 1);
	n->dead		  = 1;
	INIT_LIST_HEAD(&n->gc_list);

	atomic_inc(&tbl->entries);
out:
	return n;

out_entries:
	if (!exempt_from_gc)
		atomic_dec(&tbl->gc_entries);
	goto out;
}

static void neigh_get_hash_rnd(u32 *x)
{
	*x = get_random_u32() | 1;
}

static struct neigh_hash_table *neigh_hash_alloc(unsigned int shift)
{
	size_t size = (1 << shift) * sizeof(struct neighbour *);
	struct neigh_hash_table *ret;
	struct neighbour __rcu **buckets;
	int i;

	ret = kmalloc(sizeof(*ret), GFP_ATOMIC);
	if (!ret)
		return NULL;
	if (size <= PAGE_SIZE) {
		buckets = kzalloc(size, GFP_ATOMIC);
	} else {
		buckets = (struct neighbour __rcu **)
			  __get_free_pages(GFP_ATOMIC | __GFP_ZERO,
					   get_order(size));
		kmemleak_alloc(buckets, size, 1, GFP_ATOMIC);
	}
	if (!buckets) {
		kfree(ret);
		return NULL;
	}
	ret->hash_buckets = buckets;
	ret->hash_shift = shift;
	for (i = 0; i < NEIGH_NUM_HASH_RND; i++)
		neigh_get_hash_rnd(&ret->hash_rnd[i]);
	return ret;
}

static void neigh_hash_free_rcu(struct rcu_head *head)
{
	struct neigh_hash_table *nht = container_of(head,
						    struct neigh_hash_table,
						    rcu);
	size_t size = (1 << nht->hash_shift) * sizeof(struct neighbour *);
	struct neighbour __rcu **buckets = nht->hash_buckets;

	if (size <= PAGE_SIZE) {
		kfree(buckets);
	} else {
		kmemleak_free(buckets);
		free_pages((unsigned long)buckets, get_order(size));
	}
	kfree(nht);
}

static struct neigh_hash_table *neigh_hash_grow(struct neigh_table *tbl,
						unsigned long new_shift)
{
	unsigned int i, hash;
	struct neigh_hash_table *new_nht, *old_nht;

	NEIGH_CACHE_STAT_INC(tbl, hash_grows);

	old_nht = rcu_dereference_protected(tbl->nht,
					    lockdep_is_held(&tbl->lock));
	new_nht = neigh_hash_alloc(new_shift);
	if (!new_nht)
		return old_nht;

	for (i = 0; i < (1 << old_nht->hash_shift); i++) {
		struct neighbour *n, *next;

		for (n = rcu_dereference_protected(old_nht->hash_buckets[i],
						   lockdep_is_held(&tbl->lock));
		     n != NULL;
		     n = next) {
			hash = tbl->hash(n->primary_key, n->dev,
					 new_nht->hash_rnd);

			hash >>= (32 - new_nht->hash_shift);
			next = rcu_dereference_protected(n->next,
						lockdep_is_held(&tbl->lock));

			rcu_assign_pointer(n->next,
					   rcu_dereference_protected(
						new_nht->hash_buckets[hash],
						lockdep_is_held(&tbl->lock)));
			rcu_assign_pointer(new_nht->hash_buckets[hash], n);
		}
	}

	rcu_assign_pointer(tbl->nht, new_nht);
	call_rcu(&old_nht->rcu, neigh_hash_free_rcu);
	return new_nht;
}

struct neighbour *neigh_lookup(struct neigh_table *tbl, const void *pkey,
			       struct net_device *dev)
{
	struct neighbour *n;

	NEIGH_CACHE_STAT_INC(tbl, lookups);

	rcu_read_lock_bh();
	n = __neigh_lookup_noref(tbl, pkey, dev);
	if (n) {
		if (!refcount_inc_not_zero(&n->refcnt))
			n = NULL;
		NEIGH_CACHE_STAT_INC(tbl, hits);
	}

	rcu_read_unlock_bh();
	return n;
}
EXPORT_SYMBOL(neigh_lookup);

struct neighbour *neigh_lookup_nodev(struct neigh_table *tbl, struct net *net,
				     const void *pkey)
{
	struct neighbour *n;
	unsigned int key_len = tbl->key_len;
	u32 hash_val;
	struct neigh_hash_table *nht;

	NEIGH_CACHE_STAT_INC(tbl, lookups);

	rcu_read_lock_bh();
	nht = rcu_dereference_bh(tbl->nht);
	hash_val = tbl->hash(pkey, NULL, nht->hash_rnd) >> (32 - nht->hash_shift);

	for (n = rcu_dereference_bh(nht->hash_buckets[hash_val]);
	     n != NULL;
	     n = rcu_dereference_bh(n->next)) {
		if (!memcmp(n->primary_key, pkey, key_len) &&
		    net_eq(dev_net(n->dev), net)) {
			if (!refcount_inc_not_zero(&n->refcnt))
				n = NULL;
			NEIGH_CACHE_STAT_INC(tbl, hits);
			break;
		}
	}

	rcu_read_unlock_bh();
	return n;
}
EXPORT_SYMBOL(neigh_lookup_nodev);

static struct neighbour *___neigh_create(struct neigh_table *tbl,
					 const void *pkey,
					 struct net_device *dev,
					 bool exempt_from_gc, bool want_ref)
{
	struct neighbour *n1, *rc, *n = neigh_alloc(tbl, dev, exempt_from_gc);
	u32 hash_val;
	unsigned int key_len = tbl->key_len;
	int error;
	struct neigh_hash_table *nht;

	trace_neigh_create(tbl, dev, pkey, n, exempt_from_gc);

	if (!n) {
		rc = ERR_PTR(-ENOBUFS);
		goto out;
	}

	memcpy(n->primary_key, pkey, key_len);
	n->dev = dev;
	dev_hold(dev);

	/* Protocol specific setup. */
	if (tbl->constructor &&	(error = tbl->constructor(n)) < 0) {
		rc = ERR_PTR(error);
		goto out_neigh_release;
	}

	if (dev->netdev_ops->ndo_neigh_construct) {
		error = dev->netdev_ops->ndo_neigh_construct(dev, n);
		if (error < 0) {
			rc = ERR_PTR(error);
			goto out_neigh_release;
		}
	}

	/* Device specific setup. */
	if (n->parms->neigh_setup &&
	    (error = n->parms->neigh_setup(n)) < 0) {
		rc = ERR_PTR(error);
		goto out_neigh_release;
	}

	n->confirmed = jiffies - (NEIGH_VAR(n->parms, BASE_REACHABLE_TIME) << 1);

	write_lock_bh(&tbl->lock);
	nht = rcu_dereference_protected(tbl->nht,
					lockdep_is_held(&tbl->lock));

	if (atomic_read(&tbl->entries) > (1 << nht->hash_shift))
		nht = neigh_hash_grow(tbl, nht->hash_shift + 1);

	hash_val = tbl->hash(n->primary_key, dev, nht->hash_rnd) >> (32 - nht->hash_shift);

	if (n->parms->dead) {
		rc = ERR_PTR(-EINVAL);
		goto out_tbl_unlock;
	}

	for (n1 = rcu_dereference_protected(nht->hash_buckets[hash_val],
					    lockdep_is_held(&tbl->lock));
	     n1 != NULL;
	     n1 = rcu_dereference_protected(n1->next,
			lockdep_is_held(&tbl->lock))) {
		if (dev == n1->dev && !memcmp(n1->primary_key, n->primary_key, key_len)) {
			if (want_ref)
				neigh_hold(n1);
			rc = n1;
			goto out_tbl_unlock;
		}
	}

	n->dead = 0;
	if (!exempt_from_gc)
		list_add_tail(&n->gc_list, &n->tbl->gc_list);

	if (want_ref)
		neigh_hold(n);
	rcu_assign_pointer(n->next,
			   rcu_dereference_protected(nht->hash_buckets[hash_val],
						     lockdep_is_held(&tbl->lock)));
	rcu_assign_pointer(nht->hash_buckets[hash_val], n);
	write_unlock_bh(&tbl->lock);
	neigh_dbg(2, "neigh %p is created\n", n);
	rc = n;
out:
	return rc;
out_tbl_unlock:
	write_unlock_bh(&tbl->lock);
out_neigh_release:
	if (!exempt_from_gc)
		atomic_dec(&tbl->gc_entries);
	neigh_release(n);
	goto out;
}

struct neighbour *__neigh_create(struct neigh_table *tbl, const void *pkey,
				 struct net_device *dev, bool want_ref)
{
	return ___neigh_create(tbl, pkey, dev, false, want_ref);
}
EXPORT_SYMBOL(__neigh_create);

static u32 pneigh_hash(const void *pkey, unsigned int key_len)
{
	u32 hash_val = *(u32 *)(pkey + key_len - 4);
	hash_val ^= (hash_val >> 16);
	hash_val ^= hash_val >> 8;
	hash_val ^= hash_val >> 4;
	hash_val &= PNEIGH_HASHMASK;
	return hash_val;
}

static struct pneigh_entry *__pneigh_lookup_1(struct pneigh_entry *n,
					      struct net *net,
					      const void *pkey,
					      unsigned int key_len,
					      struct net_device *dev)
{
	while (n) {
		if (!memcmp(n->key, pkey, key_len) &&
		    net_eq(pneigh_net(n), net) &&
		    (n->dev == dev || !n->dev))
			return n;
		n = n->next;
	}
	return NULL;
}

struct pneigh_entry *__pneigh_lookup(struct neigh_table *tbl,
		struct net *net, const void *pkey, struct net_device *dev)
{
	unsigned int key_len = tbl->key_len;
	u32 hash_val = pneigh_hash(pkey, key_len);

	return __pneigh_lookup_1(tbl->phash_buckets[hash_val],
				 net, pkey, key_len, dev);
}
EXPORT_SYMBOL_GPL(__pneigh_lookup);

struct pneigh_entry * pneigh_lookup(struct neigh_table *tbl,
				    struct net *net, const void *pkey,
				    struct net_device *dev, int creat)
{
	struct pneigh_entry *n;
	unsigned int key_len = tbl->key_len;
	u32 hash_val = pneigh_hash(pkey, key_len);

	read_lock_bh(&tbl->lock);
	n = __pneigh_lookup_1(tbl->phash_buckets[hash_val],
			      net, pkey, key_len, dev);
	read_unlock_bh(&tbl->lock);

	if (n || !creat)
		goto out;

	ASSERT_RTNL();

	n = kmalloc(sizeof(*n) + key_len, GFP_KERNEL);
	if (!n)
		goto out;

	n->protocol = 0;
	write_pnet(&n->net, net);
	memcpy(n->key, pkey, key_len);
	n->dev = dev;
	if (dev)
		dev_hold(dev);

	if (tbl->pconstructor && tbl->pconstructor(n)) {
		if (dev)
			dev_put(dev);
		kfree(n);
		n = NULL;
		goto out;
	}

	write_lock_bh(&tbl->lock);
	n->next = tbl->phash_buckets[hash_val];
	tbl->phash_buckets[hash_val] = n;
	write_unlock_bh(&tbl->lock);
out:
	return n;
}
EXPORT_SYMBOL(pneigh_lookup);


int pneigh_delete(struct neigh_table *tbl, struct net *net, const void *pkey,
		  struct net_device *dev)
{
	struct pneigh_entry *n, **np;
	unsigned int key_len = tbl->key_len;
	u32 hash_val = pneigh_hash(pkey, key_len);

	write_lock_bh(&tbl->lock);
	for (np = &tbl->phash_buckets[hash_val]; (n = *np) != NULL;
	     np = &n->next) {
		if (!memcmp(n->key, pkey, key_len) && n->dev == dev &&
		    net_eq(pneigh_net(n), net)) {
			*np = n->next;
			write_unlock_bh(&tbl->lock);
			if (tbl->pdestructor)
				tbl->pdestructor(n);
			if (n->dev)
				dev_put(n->dev);
			kfree(n);
			return 0;
		}
	}
	write_unlock_bh(&tbl->lock);
	return -ENOENT;
}

static int pneigh_ifdown_and_unlock(struct neigh_table *tbl,
				    struct net_device *dev)
{
	struct pneigh_entry *n, **np, *freelist = NULL;
	u32 h;

	for (h = 0; h <= PNEIGH_HASHMASK; h++) {
		np = &tbl->phash_buckets[h];
		while ((n = *np) != NULL) {
			if (!dev || n->dev == dev) {
				*np = n->next;
				n->next = freelist;
				freelist = n;
				continue;
			}
			np = &n->next;
		}
	}
	write_unlock_bh(&tbl->lock);
	while ((n = freelist)) {
		freelist = n->next;
		n->next = NULL;
		if (tbl->pdestructor)
			tbl->pdestructor(n);
		if (n->dev)
			dev_put(n->dev);
		kfree(n);
	}
	return -ENOENT;
}

static void neigh_parms_destroy(struct neigh_parms *parms);

static inline void neigh_parms_put(struct neigh_parms *parms)
{
	if (refcount_dec_and_test(&parms->refcnt))
		neigh_parms_destroy(parms);
}

/*
 *	neighbour must already be out of the table;
 *
 */
void neigh_destroy(struct neighbour *neigh)
{
	struct net_device *dev = neigh->dev;

	NEIGH_CACHE_STAT_INC(neigh->tbl, destroys);

	if (!neigh->dead) {
		pr_warn("Destroying alive neighbour %p\n", neigh);
		dump_stack();
		return;
	}

	if (neigh_del_timer(neigh))
		pr_warn("Impossible event\n");

	write_lock_bh(&neigh->lock);
	__skb_queue_purge(&neigh->arp_queue);
	write_unlock_bh(&neigh->lock);
	neigh->arp_queue_len_bytes = 0;

	if (dev->netdev_ops->ndo_neigh_destroy)
		dev->netdev_ops->ndo_neigh_destroy(dev, neigh);

	dev_put(dev);
	neigh_parms_put(neigh->parms);

	neigh_dbg(2, "neigh %p is destroyed\n", neigh);

	atomic_dec(&neigh->tbl->entries);
	kfree_rcu(neigh, rcu);
}
EXPORT_SYMBOL(neigh_destroy);

/* Neighbour state is suspicious;
   disable fast path.

   Called with write_locked neigh.
 */
static void neigh_suspect(struct neighbour *neigh)
{
	neigh_dbg(2, "neigh %p is suspected\n", neigh);

	neigh->output = neigh->ops->output;
}

/* Neighbour state is OK;
   enable fast path.

   Called with write_locked neigh.
 */
static void neigh_connect(struct neighbour *neigh)
{
	neigh_dbg(2, "neigh %p is connected\n", neigh);

	neigh->output = neigh->ops->connected_output;
}

static void neigh_periodic_work(struct work_struct *work)
{
	struct neigh_table *tbl = container_of(work, struct neigh_table, gc_work.work);
	struct neighbour *n;
	struct neighbour __rcu **np;
	unsigned int i;
	struct neigh_hash_table *nht;

	NEIGH_CACHE_STAT_INC(tbl, periodic_gc_runs);

	write_lock_bh(&tbl->lock);
	nht = rcu_dereference_protected(tbl->nht,
					lockdep_is_held(&tbl->lock));

	/*
	 *	periodically recompute ReachableTime from random function
	 */

	if (time_after(jiffies, tbl->last_rand + 300 * HZ)) {
		struct neigh_parms *p;
		tbl->last_rand = jiffies;
		list_for_each_entry(p, &tbl->parms_list, list)
			p->reachable_time =
				neigh_rand_reach_time(NEIGH_VAR(p, BASE_REACHABLE_TIME));
	}

	if (atomic_read(&tbl->entries) < tbl->gc_thresh1)
		goto out;

	for (i = 0 ; i < (1 << nht->hash_shift); i++) {
		np = &nht->hash_buckets[i];

		while ((n = rcu_dereference_protected(*np,
				lockdep_is_held(&tbl->lock))) != NULL) {
			unsigned int state;

			write_lock(&n->lock);

			state = n->nud_state;
			if ((state & (NUD_PERMANENT | NUD_IN_TIMER)) ||
			    (n->flags &