drivers/md/dm-vdo/int-map.c

Source file repositories/reference/linux-study-clean/drivers/md/dm-vdo/int-map.c

File Facts

System
Linux kernel
Corpus path
drivers/md/dm-vdo/int-map.c
Extension
.c
Size
23855 bytes
Lines
701
Domain
Driver Families
Bucket
drivers/md
Inferred role
Driver Families: implementation source
Status
source implementation candidate

Why This File Exists

Repeatable hardware-adapter layer. Deep compatibility for every driver is out of scope; this atlas records patterns, probe lifecycles, bus glue, IRQ/DMA usage, and links back to core abstractions.

Dependency Surface

Detected Declarations

Annotated Snippet

struct bucket {
	/**
	 * @first_hop: The biased offset of the first entry in the hop list of the neighborhood
	 *             that hashes to this bucket.
	 */
	u8 first_hop;
	/** @next_hop: The biased offset of the next bucket in the hop list. */
	u8 next_hop;
	/** @key: The key stored in this bucket. */
	u64 key;
	/** @value: The value stored in this bucket (NULL if empty). */
	void *value;
} __packed;

/**
 * struct int_map - The concrete definition of the opaque int_map type.
 *
 * To avoid having to wrap the neighborhoods of the last entries back around to the start of the
 * bucket array, we allocate a few more buckets at the end of the array instead, which is why
 * capacity and bucket_count are different.
 */
struct int_map {
	/** @size: The number of entries stored in the map. */
	size_t size;
	/** @capacity: The number of neighborhoods in the map. */
	size_t capacity;
	/** @bucket_count: The number of buckets in the bucket array. */
	size_t bucket_count;
	/** @buckets: The array of hash buckets. */
	struct bucket *buckets;
};

/**
 * mix() - The Google CityHash 16-byte hash mixing function.
 * @input1: The first input value.
 * @input2: The second input value.
 *
 * Return: A hash of the two inputs.
 */
static u64 mix(u64 input1, u64 input2)
{
	static const u64 CITY_MULTIPLIER = 0x9ddfea08eb382d69ULL;
	u64 hash = (input1 ^ input2);

	hash *= CITY_MULTIPLIER;
	hash ^= (hash >> 47);
	hash ^= input2;
	hash *= CITY_MULTIPLIER;
	hash ^= (hash >> 47);
	hash *= CITY_MULTIPLIER;
	return hash;
}

/**
 * hash_key() - Calculate a 64-bit non-cryptographic hash value for the provided 64-bit integer
 *              key.
 * @key: The mapping key.
 *
 * The implementation is based on Google's CityHash, only handling the specific case of an 8-byte
 * input.
 *
 * Return: The hash of the mapping key.
 */
static u64 hash_key(u64 key)
{
	/*
	 * Aliasing restrictions forbid us from casting pointer types, so use a union to convert a
	 * single u64 to two u32 values.
	 */
	union {
		u64 u64;
		u32 u32[2];
	} pun = {.u64 = key};

	return mix(sizeof(key) + (((u64) pun.u32[0]) << 3), pun.u32[1]);
}

/**
 * allocate_buckets() - Initialize an int_map.
 * @map: The map to initialize.
 * @capacity: The initial capacity of the map.
 *
 * Return: VDO_SUCCESS or an error code.
 */
static int allocate_buckets(struct int_map *map, size_t capacity)
{
	map->size = 0;
	map->capacity = capacity;

	/*

Annotation

Implementation Notes