timerqueue.c 2.5 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /*
  3. * Generic Timer-queue
  4. *
  5. * Manages a simple queue of timers, ordered by expiration time.
  6. * Uses rbtrees for quick list adds and expiration.
  7. *
  8. * NOTE: All of the following functions need to be serialized
  9. * to avoid races. No locking is done by this library code.
  10. */
  11. #include <linux/bug.h>
  12. #include <linux/timerqueue.h>
  13. #include <linux/rbtree.h>
  14. #include <linux/export.h>
  15. /**
  16. * timerqueue_add - Adds timer to timerqueue.
  17. *
  18. * @head: head of timerqueue
  19. * @node: timer node to be added
  20. *
  21. * Adds the timer node to the timerqueue, sorted by the node's expires
  22. * value. Returns true if the newly added timer is the first expiring timer in
  23. * the queue.
  24. */
  25. bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
  26. {
  27. struct rb_node **p = &head->rb_root.rb_root.rb_node;
  28. struct rb_node *parent = NULL;
  29. struct timerqueue_node *ptr;
  30. bool leftmost = true;
  31. /* Make sure we don't add nodes that are already added */
  32. WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
  33. while (*p) {
  34. parent = *p;
  35. ptr = rb_entry(parent, struct timerqueue_node, node);
  36. if (node->expires < ptr->expires) {
  37. p = &(*p)->rb_left;
  38. } else {
  39. p = &(*p)->rb_right;
  40. leftmost = false;
  41. }
  42. }
  43. rb_link_node(&node->node, parent, p);
  44. rb_insert_color_cached(&node->node, &head->rb_root, leftmost);
  45. return leftmost;
  46. }
  47. EXPORT_SYMBOL_GPL(timerqueue_add);
  48. /**
  49. * timerqueue_del - Removes a timer from the timerqueue.
  50. *
  51. * @head: head of timerqueue
  52. * @node: timer node to be removed
  53. *
  54. * Removes the timer node from the timerqueue. Returns true if the queue is
  55. * not empty after the remove.
  56. */
  57. bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
  58. {
  59. WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
  60. rb_erase_cached(&node->node, &head->rb_root);
  61. RB_CLEAR_NODE(&node->node);
  62. return !RB_EMPTY_ROOT(&head->rb_root.rb_root);
  63. }
  64. EXPORT_SYMBOL_GPL(timerqueue_del);
  65. /**
  66. * timerqueue_iterate_next - Returns the timer after the provided timer
  67. *
  68. * @node: Pointer to a timer.
  69. *
  70. * Provides the timer that is after the given node. This is used, when
  71. * necessary, to iterate through the list of timers in a timer list
  72. * without modifying the list.
  73. */
  74. struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
  75. {
  76. struct rb_node *next;
  77. if (!node)
  78. return NULL;
  79. next = rb_next(&node->node);
  80. if (!next)
  81. return NULL;
  82. return container_of(next, struct timerqueue_node, node);
  83. }
  84. EXPORT_SYMBOL_GPL(timerqueue_iterate_next);