cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

timerqueue.c (2340B)

      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
     12#include <linux/bug.h>
     13#include <linux/timerqueue.h>
     14#include <linux/rbtree.h>
     15#include <linux/export.h>
     16
     17#define __node_2_tq(_n) \
     18	rb_entry((_n), struct timerqueue_node, node)
     19
     20static inline bool __timerqueue_less(struct rb_node *a, const struct rb_node *b)
     21{
     22	return __node_2_tq(a)->expires < __node_2_tq(b)->expires;
     23}
     24
     25/**
     26 * timerqueue_add - Adds timer to timerqueue.
     27 *
     28 * @head: head of timerqueue
     29 * @node: timer node to be added
     30 *
     31 * Adds the timer node to the timerqueue, sorted by the node's expires
     32 * value. Returns true if the newly added timer is the first expiring timer in
     33 * the queue.
     34 */
     35bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
     36{
     37	/* Make sure we don't add nodes that are already added */
     38	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
     39
     40	return rb_add_cached(&node->node, &head->rb_root, __timerqueue_less);
     41}
     42EXPORT_SYMBOL_GPL(timerqueue_add);
     43
     44/**
     45 * timerqueue_del - Removes a timer from the timerqueue.
     46 *
     47 * @head: head of timerqueue
     48 * @node: timer node to be removed
     49 *
     50 * Removes the timer node from the timerqueue. Returns true if the queue is
     51 * not empty after the remove.
     52 */
     53bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
     54{
     55	WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
     56
     57	rb_erase_cached(&node->node, &head->rb_root);
     58	RB_CLEAR_NODE(&node->node);
     59
     60	return !RB_EMPTY_ROOT(&head->rb_root.rb_root);
     61}
     62EXPORT_SYMBOL_GPL(timerqueue_del);
     63
     64/**
     65 * timerqueue_iterate_next - Returns the timer after the provided timer
     66 *
     67 * @node: Pointer to a timer.
     68 *
     69 * Provides the timer that is after the given node. This is used, when
     70 * necessary, to iterate through the list of timers in a timer list
     71 * without modifying the list.
     72 */
     73struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
     74{
     75	struct rb_node *next;
     76
     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}
     84EXPORT_SYMBOL_GPL(timerqueue_iterate_next);