Skip to content
GitLab
Projects Groups Topics Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Register
  • Sign in
  • L linux
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
  • Issues 0
    • Issues 0
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 0
    • Merge requests 0
  • Deployments
    • Deployments
    • Releases
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Commits
  • Issue Boards
Collapse sidebar
  • Kirill Smelkov
  • linux
  • Repository
  • linux
  • include
  • linux
  • timerqueue.h
Find file BlameHistoryPermalink
  • Davidlohr Bueso's avatar
    lib/timerqueue: Rely on rbtree semantics for next timer · 511885d7
    Davidlohr Bueso authored Jul 24, 2019
    
    
    Simplify the timerqueue code by using cached rbtrees and rely on the tree
    leftmost node semantics to get the timer with earliest expiration time.
    This is a drop in conversion, and therefore semantics remain untouched.
    
    The runtime overhead of cached rbtrees is be pretty much the same as the
    current head->next method, noting that when removing the leftmost node,
    a common operation for the timerqueue, the rb_next(leftmost) is O(1) as
    well, so the next timer will either be the right node or its parent.
    Therefore no extra pointer chasing. Finally, the size of the struct
    timerqueue_head remains the same.
    
    Passes several hours of rcutorture.
    
    Signed-off-by: default avatarDavidlohr Bueso <dbueso@suse.de>
    Signed-off-by: default avatarThomas Gleixner <tglx@linutronix.de>
    Link: https://lkml.kernel.org/r/20190724152323.bojciei3muvfxalm@linux-r8p5
    511885d7
GitLab Nexedi Edition | About GitLab | About Nexedi | 沪ICP备2021021310号-2 | 沪ICP备2021021310号-7