1213 static int assert_not_at_end(const struct delta_index_entry *delta_entry)  in assert_not_at_end()  argument
1215 	int result = VDO_ASSERT(!delta_entry->at_end,  in assert_not_at_end()
1232 				 u32 key, struct delta_index_entry *delta_entry)  in uds_start_delta_index_search()  argument
1263 		delta_list = &delta_entry->temp_delta_list;  in uds_start_delta_index_search()
1272 		delta_entry->key = delta_list->save_key;  in uds_start_delta_index_search()
1273 		delta_entry->offset = delta_list->save_offset;  in uds_start_delta_index_search()
1275 		delta_entry->key = 0;  in uds_start_delta_index_search()
1276 		delta_entry->offset = 0;  in uds_start_delta_index_search()
1287 	delta_entry->at_end = false;  in uds_start_delta_index_search()
1288 	delta_entry->delta_zone = delta_zone;  in uds_start_delta_index_search()
1289 	delta_entry->delta_list = delta_list;  in uds_start_delta_index_search()
1290 	delta_entry->entry_bits = 0;  in uds_start_delta_index_search()
1291 	delta_entry->is_collision = false;  in uds_start_delta_index_search()
1292 	delta_entry->list_number = list_number;  in uds_start_delta_index_search()
1293 	delta_entry->list_overflow = false;  in uds_start_delta_index_search()
1294 	delta_entry->value_bits = delta_zone->value_bits;  in uds_start_delta_index_search()
1298 static inline u64 get_delta_entry_offset(const struct delta_index_entry *delta_entry)  in get_delta_entry_offset()  argument
1300 	return delta_entry->delta_list->start + delta_entry->offset;  in get_delta_entry_offset()
1308 static inline void decode_delta(struct delta_index_entry *delta_entry)  in decode_delta()  argument
1312 	const struct delta_zone *delta_zone = delta_entry->delta_zone;  in decode_delta()
1314 	u64 delta_offset = get_delta_entry_offset(delta_entry) + delta_entry->value_bits;  in decode_delta()
1334 	delta_entry->delta = delta;  in decode_delta()
1335 	delta_entry->key += delta;  in decode_delta()
1338 	if (unlikely((delta == 0) && (delta_entry->offset > 0))) {  in decode_delta()
1339 		delta_entry->is_collision = true;  in decode_delta()
1340 		delta_entry->entry_bits = delta_entry->value_bits + key_bits + COLLISION_BITS;  in decode_delta()
1342 		delta_entry->is_collision = false;  in decode_delta()
1343 		delta_entry->entry_bits = delta_entry->value_bits + key_bits;  in decode_delta()
1347 noinline int uds_next_delta_index_entry(struct delta_index_entry *delta_entry)  in uds_next_delta_index_entry()  argument
1354 	result = assert_not_at_end(delta_entry);  in uds_next_delta_index_entry()
1358 	delta_list = delta_entry->delta_list;  in uds_next_delta_index_entry()
1359 	delta_entry->offset += delta_entry->entry_bits;  in uds_next_delta_index_entry()
1361 	if (unlikely(delta_entry->offset >= size)) {  in uds_next_delta_index_entry()
1362 		delta_entry->at_end = true;  in uds_next_delta_index_entry()
1363 		delta_entry->delta = 0;  in uds_next_delta_index_entry()
1364 		delta_entry->is_collision = false;  in uds_next_delta_index_entry()
1365 		result = VDO_ASSERT((delta_entry->offset == size),  in uds_next_delta_index_entry()
1373 	decode_delta(delta_entry);  in uds_next_delta_index_entry()
1375 	next_offset = delta_entry->offset + delta_entry->entry_bits;  in uds_next_delta_index_entry()
1388 int uds_remember_delta_index_offset(const struct delta_index_entry *delta_entry)  in uds_remember_delta_index_offset()  argument
1391 	struct delta_list *delta_list = delta_entry->delta_list;  in uds_remember_delta_index_offset()
1393 	result = VDO_ASSERT(!delta_entry->is_collision, "entry is not a collision");  in uds_remember_delta_index_offset()
1397 	delta_list->save_key = delta_entry->key - delta_entry->delta;  in uds_remember_delta_index_offset()
1398 	delta_list->save_offset = delta_entry->offset;  in uds_remember_delta_index_offset()
1402 static void set_delta(struct delta_index_entry *delta_entry, u32 delta)  in set_delta()  argument
1404 	const struct delta_zone *delta_zone = delta_entry->delta_zone;  in set_delta()
1409 	delta_entry->delta = delta;  in set_delta()
1410 	delta_entry->entry_bits = delta_entry->value_bits + key_bits;  in set_delta()
1441 			      struct delta_index_entry *delta_entry)  in uds_get_delta_index_entry()  argument
1446 					      delta_entry);  in uds_get_delta_index_entry()
1451 		result = uds_next_delta_index_entry(delta_entry);  in uds_get_delta_index_entry()
1454 	} while (!delta_entry->at_end && (key > delta_entry->key));  in uds_get_delta_index_entry()
1456 	result = uds_remember_delta_index_offset(delta_entry);  in uds_get_delta_index_entry()
1460 	if (!delta_entry->at_end && (key == delta_entry->key)) {  in uds_get_delta_index_entry()
1461 		struct delta_index_entry collision_entry = *delta_entry;  in uds_get_delta_index_entry()
1475 				*delta_entry = collision_entry;  in uds_get_delta_index_entry()
1484 int uds_get_delta_entry_collision(const struct delta_index_entry *delta_entry, u8 *name)  in uds_get_delta_entry_collision()  argument
1488 	result = assert_not_at_end(delta_entry);  in uds_get_delta_entry_collision()
1492 	result = VDO_ASSERT(delta_entry->is_collision,  in uds_get_delta_entry_collision()
1497 	get_collision_name(delta_entry, name);  in uds_get_delta_entry_collision()
1501 u32 uds_get_delta_entry_value(const struct delta_index_entry *delta_entry)  in uds_get_delta_entry_value()  argument
1503 	return get_field(delta_entry->delta_zone->memory,  in uds_get_delta_entry_value()
1504 			 get_delta_entry_offset(delta_entry), delta_entry->value_bits);  in uds_get_delta_entry_value()
1507 static int assert_mutable_entry(const struct delta_index_entry *delta_entry)  in assert_mutable_entry()  argument
1509 	int result = VDO_ASSERT((delta_entry->delta_list != &delta_entry->temp_delta_list),  in assert_mutable_entry()
1517 int uds_set_delta_entry_value(const struct delta_index_entry *delta_entry, u32 value)  in uds_set_delta_entry_value()  argument
1520 	u32 value_mask = (1 << delta_entry->value_bits) - 1;  in uds_set_delta_entry_value()
1522 	result = assert_mutable_entry(delta_entry);  in uds_set_delta_entry_value()
1526 	result = assert_not_at_end(delta_entry);  in uds_set_delta_entry_value()
1532 			    value, delta_entry->value_bits);  in uds_set_delta_entry_value()
1536 	set_field(value, delta_entry->delta_zone->memory,  in uds_set_delta_entry_value()
1537 		  get_delta_entry_offset(delta_entry), delta_entry->value_bits);  in uds_set_delta_entry_value()
1579 static int insert_bits(struct delta_index_entry *delta_entry, u16 size)  in insert_bits()  argument
1588 	struct delta_zone *delta_zone = delta_entry->delta_zone;  in insert_bits()
1589 	struct delta_list *delta_list = delta_entry->delta_list;  in insert_bits()
1592 	u32 before_size = delta_entry->offset;  in insert_bits()
1593 	u32 after_size = total_size - delta_entry->offset;  in insert_bits()
1596 		delta_entry->list_overflow = true;  in insert_bits()
1630 		u32 growing_index = delta_entry->list_number + 1;  in insert_bits()
1648 		source = delta_list->start + delta_entry->offset;  in insert_bits()
1658 static void encode_delta(const struct delta_index_entry *delta_entry)  in encode_delta()  argument
1664 	const struct delta_zone *delta_zone = delta_entry->delta_zone;  in encode_delta()
1667 	offset = get_delta_entry_offset(delta_entry) + delta_entry->value_bits;  in encode_delta()
1668 	if (delta_entry->delta < delta_zone->min_keys) {  in encode_delta()
1669 		set_field(delta_entry->delta, memory, offset, delta_zone->min_bits);  in encode_delta()
1673 	temp = delta_entry->delta - delta_zone->min_keys;  in encode_delta()
1681 static void encode_entry(const struct delta_index_entry *delta_entry, u32 value,  in encode_entry()  argument
1684 	u8 *memory = delta_entry->delta_zone->memory;  in encode_entry()
1685 	u64 offset = get_delta_entry_offset(delta_entry);  in encode_entry()
1687 	set_field(value, memory, offset, delta_entry->value_bits);  in encode_entry()
1688 	encode_delta(delta_entry);  in encode_entry()
1690 		set_collision_name(delta_entry, name);  in encode_entry()
1697 int uds_put_delta_index_entry(struct delta_index_entry *delta_entry, u32 key, u32 value,  in uds_put_delta_index_entry()  argument
1703 	result = assert_mutable_entry(delta_entry);  in uds_put_delta_index_entry()
1707 	if (delta_entry->is_collision) {  in uds_put_delta_index_entry()
1717 	if (delta_entry->offset < delta_entry->delta_list->save_offset) {  in uds_put_delta_index_entry()
1722 		result = uds_remember_delta_index_offset(delta_entry);  in uds_put_delta_index_entry()
1729 		result = assert_not_at_end(delta_entry);  in uds_put_delta_index_entry()
1733 		result = VDO_ASSERT((key == delta_entry->key),  in uds_put_delta_index_entry()
1738 		delta_entry->offset += delta_entry->entry_bits;  in uds_put_delta_index_entry()
1739 		set_delta(delta_entry, 0);  in uds_put_delta_index_entry()
1740 		delta_entry->is_collision = true;  in uds_put_delta_index_entry()
1741 		delta_entry->entry_bits += COLLISION_BITS;  in uds_put_delta_index_entry()
1742 		result = insert_bits(delta_entry, delta_entry->entry_bits);  in uds_put_delta_index_entry()
1743 	} else if (delta_entry->at_end) {  in uds_put_delta_index_entry()
1745 		result = VDO_ASSERT((key >= delta_entry->key), "key past end of list");  in uds_put_delta_index_entry()
1749 		set_delta(delta_entry, key - delta_entry->key);  in uds_put_delta_index_entry()
1750 		delta_entry->key = key;  in uds_put_delta_index_entry()
1751 		delta_entry->at_end = false;  in uds_put_delta_index_entry()
1752 		result = insert_bits(delta_entry, delta_entry->entry_bits);  in uds_put_delta_index_entry()
1763 		result = VDO_ASSERT((key < delta_entry->key),  in uds_put_delta_index_entry()
1768 		result = VDO_ASSERT((key >= delta_entry->key - delta_entry->delta),  in uds_put_delta_index_entry()
1773 		old_entry_size = delta_entry->entry_bits;  in uds_put_delta_index_entry()
1774 		next_entry = *delta_entry;  in uds_put_delta_index_entry()
1776 		set_delta(delta_entry, key - (delta_entry->key - delta_entry->delta));  in uds_put_delta_index_entry()
1777 		delta_entry->key = key;  in uds_put_delta_index_entry()
1779 		next_entry.offset += delta_entry->entry_bits;  in uds_put_delta_index_entry()
1781 		additional_size = (delta_entry->entry_bits +  in uds_put_delta_index_entry()
1783 		result = insert_bits(delta_entry, additional_size);  in uds_put_delta_index_entry()
1793 	encode_entry(delta_entry, value, name);  in uds_put_delta_index_entry()
1794 	delta_zone = delta_entry->delta_zone;  in uds_put_delta_index_entry()
1796 	delta_zone->collision_count += delta_entry->is_collision ? 1 : 0;  in uds_put_delta_index_entry()
1800 static void delete_bits(const struct delta_index_entry *delta_entry, int size)  in delete_bits()  argument
1806 	struct delta_list *delta_list = delta_entry->delta_list;  in delete_bits()
1807 	u8 *memory = delta_entry->delta_zone->memory;  in delete_bits()
1810 	u32 before_size = delta_entry->offset;  in delete_bits()
1811 	u32 after_size = total_size - delta_entry->offset - size;  in delete_bits()
1838 		destination = delta_list->start + delta_entry->offset;  in delete_bits()
1846 int uds_remove_delta_index_entry(struct delta_index_entry *delta_entry)  in uds_remove_delta_index_entry()  argument
1853 	result = assert_mutable_entry(delta_entry);  in uds_remove_delta_index_entry()
1857 	next_entry = *delta_entry;  in uds_remove_delta_index_entry()
1862 	delta_zone = delta_entry->delta_zone;  in uds_remove_delta_index_entry()
1864 	if (delta_entry->is_collision) {  in uds_remove_delta_index_entry()
1866 		delete_bits(delta_entry, delta_entry->entry_bits);  in uds_remove_delta_index_entry()
1867 		next_entry.offset = delta_entry->offset;  in uds_remove_delta_index_entry()
1871 		delete_bits(delta_entry, delta_entry->entry_bits);  in uds_remove_delta_index_entry()
1872 		next_entry.key -= delta_entry->delta;  in uds_remove_delta_index_entry()
1873 		next_entry.offset = delta_entry->offset;  in uds_remove_delta_index_entry()
1877 		u16 old_size = delta_entry->entry_bits + next_entry.entry_bits;  in uds_remove_delta_index_entry()
1884 		set_delta(&next_entry, delta_entry->delta + next_entry.delta);  in uds_remove_delta_index_entry()
1885 		next_entry.offset = delta_entry->offset;  in uds_remove_delta_index_entry()
1887 		delete_bits(delta_entry, old_size - next_entry.entry_bits);  in uds_remove_delta_index_entry()
1893 	*delta_entry = next_entry;  in uds_remove_delta_index_entry()
1895 	delta_list = delta_entry->delta_list;  in uds_remove_delta_index_entry()
1896 	if (delta_entry->offset < delta_list->save_offset) {  in uds_remove_delta_index_entry()
1960 void uds_log_delta_index_entry(struct delta_index_entry *delta_entry)  in uds_log_delta_index_entry()  argument
1964 			  delta_entry->list_number, delta_entry->key,  in uds_log_delta_index_entry()
1965 			  delta_entry->offset, delta_entry->at_end ? " end" : "",  in uds_log_delta_index_entry()
1966 			  delta_entry->is_collision ? " collision" : "",  in uds_log_delta_index_entry()
1967 			  delta_entry->delta_list->size,  in uds_log_delta_index_entry()
1968 			  delta_entry->list_overflow ? " overflow" : "");  in uds_log_delta_index_entry()
1969 	delta_entry->list_overflow = false;  in uds_log_delta_index_entry()