drivers/md/dm-vdo/indexer/delta-index.c

Source file repositories/reference/linux-study-clean/drivers/md/dm-vdo/indexer/delta-index.c

File Facts

System
Linux kernel
Corpus path
drivers/md/dm-vdo/indexer/delta-index.c
Extension
.c
Size
64041 bytes
Lines
1968
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 delta_index_header {
	char magic[MAGIC_SIZE];
	u32 zone_number;
	u32 zone_count;
	u32 first_list;
	u32 list_count;
	u64 record_count;
	u64 collision_count;
};

/*
 * Header data used for immutable delta index pages. This data is followed by the delta list offset
 * table.
 */
struct delta_page_header {
	/* Externally-defined nonce */
	u64 nonce;
	/* The virtual chapter number */
	u64 virtual_chapter_number;
	/* Index of the first delta list on the page */
	u16 first_list;
	/* Number of delta lists on the page */
	u16 list_count;
} __packed;

static inline u64 get_delta_list_byte_start(const struct delta_list *delta_list)
{
	return delta_list->start / BITS_PER_BYTE;
}

static inline u16 get_delta_list_byte_size(const struct delta_list *delta_list)
{
	unsigned int bit_offset = delta_list->start % BITS_PER_BYTE;

	return BITS_TO_BYTES(bit_offset + delta_list->size);
}

static void rebalance_delta_zone(const struct delta_zone *delta_zone, u32 first,
				 u32 last)
{
	struct delta_list *delta_list;
	u64 new_start;

	if (first == last) {
		/* Only one list is moving, and we know there is space. */
		delta_list = &delta_zone->delta_lists[first];
		new_start = delta_zone->new_offsets[first];
		if (delta_list->start != new_start) {
			u64 source;
			u64 destination;

			source = get_delta_list_byte_start(delta_list);
			delta_list->start = new_start;
			destination = get_delta_list_byte_start(delta_list);
			memmove(delta_zone->memory + destination,
				delta_zone->memory + source,
				get_delta_list_byte_size(delta_list));
		}
	} else {
		/*
		 * There is more than one list. Divide the problem in half, and use recursive calls
		 * to process each half. Note that after this computation, first <= middle, and
		 * middle < last.
		 */
		u32 middle = (first + last) / 2;

		delta_list = &delta_zone->delta_lists[middle];
		new_start = delta_zone->new_offsets[middle];

		/*
		 * The direction that our middle list is moving determines which half of the
		 * problem must be processed first.
		 */
		if (new_start > delta_list->start) {
			rebalance_delta_zone(delta_zone, middle + 1, last);
			rebalance_delta_zone(delta_zone, first, middle);
		} else {
			rebalance_delta_zone(delta_zone, first, middle);
			rebalance_delta_zone(delta_zone, middle + 1, last);
		}
	}
}

static inline size_t get_zone_memory_size(unsigned int zone_count, size_t memory_size)
{
	/* Round up so that each zone is a multiple of 64K in size. */
	size_t ALLOC_BOUNDARY = 64 * 1024;

	return (memory_size / zone_count + ALLOC_BOUNDARY - 1) & -ALLOC_BOUNDARY;
}

Annotation

Implementation Notes