linux/drivers/md/dm-vdo/priority-table.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright 2023 Red Hat
 */

#include "priority-table.h"

#include <linux/log2.h>

#include "errors.h"
#include "memory-alloc.h"
#include "permassert.h"

#include "status-codes.h"

/* We use a single 64-bit search vector, so the maximum priority is 63 */
#define MAX_PRIORITY …

/*
 * All the entries with the same priority are queued in a circular list in a bucket for that
 * priority. The table is essentially an array of buckets.
 */
struct bucket { … };

/*
 * A priority table is an array of buckets, indexed by priority. New entries are added to the end
 * of the queue in the appropriate bucket. The dequeue operation finds the highest-priority
 * non-empty bucket by searching a bit vector represented as a single 8-byte word, which is very
 * fast with compiler and CPU support.
 */
struct priority_table { … };

/**
 * vdo_make_priority_table() - Allocate and initialize a new priority_table.
 * @max_priority: The maximum priority value for table entries.
 * @table_ptr: A pointer to hold the new table.
 *
 * Return: VDO_SUCCESS or an error code.
 */
int vdo_make_priority_table(unsigned int max_priority, struct priority_table **table_ptr)
{ … }

/**
 * vdo_free_priority_table() - Free a priority_table.
 * @table: The table to free.
 *
 * The table does not own the entries stored in it and they are not freed by this call.
 */
void vdo_free_priority_table(struct priority_table *table)
{ … }

/**
 * vdo_reset_priority_table() - Reset a priority table, leaving it in the same empty state as when
 *                          newly constructed.
 * @table: The table to reset.
 *
 * The table does not own the entries stored in it and they are not freed (or even unlinked from
 * each other) by this call.
 */
void vdo_reset_priority_table(struct priority_table *table)
{ … }

/**
 * vdo_priority_table_enqueue() - Add a new entry to the priority table, appending it to the queue
 *                                for entries with the specified priority.
 * @table: The table in which to store the entry.
 * @priority: The priority of the entry.
 * @entry: The list_head embedded in the entry to store in the table (the caller must have
 *         initialized it).
 */
void vdo_priority_table_enqueue(struct priority_table *table, unsigned int priority,
				struct list_head *entry)
{ … }

static inline void mark_bucket_empty(struct priority_table *table, struct bucket *bucket)
{ … }

/**
 * vdo_priority_table_dequeue() - Find the highest-priority entry in the table, remove it from the
 *                                table, and return it.
 * @table: The priority table from which to remove an entry.
 *
 * If there are multiple entries with the same priority, the one that has been in the table with
 * that priority the longest will be returned.
 *
 * Return: The dequeued entry, or NULL if the table is currently empty.
 */
struct list_head *vdo_priority_table_dequeue(struct priority_table *table)
{ … }

/**
 * vdo_priority_table_remove() - Remove a specified entry from its priority table.
 * @table: The table from which to remove the entry.
 * @entry: The entry to remove from the table.
 */
void vdo_priority_table_remove(struct priority_table *table, struct list_head *entry)
{ … }

/**
 * vdo_is_priority_table_empty() - Return whether the priority table is empty.
 * @table: The table to check.
 *
 * Return: true if the table is empty.
 */
bool vdo_is_priority_table_empty(struct priority_table *table)
{ … }