1 // SPDX-License-Identifier: GPL-2.0-only
6 #include "open-chapter.h"
11 #include "memory-alloc.h"
16 #include "hash-utils.h"
21  * records are stored in an array in the order they arrive. Additionally, a reference to each
23  * If new metadata for an existing name arrives, the record is altered in place. The array of
24  * records is 1-based so that record number 0 can be used to indicate an unused hash slot.
27  * management. The array of deleted flags overlays the array of hash slots, but the flags are
28  * indexed by record number instead of by record name. The number of hash slots will always be a
29  * power of two that is greater than the number of records to be indexed, guaranteeing that hash
39  * When the index is saved, the open chapter records are saved in a single array, once again
49 #define OPEN_CHAPTER_MAGIC_LENGTH (sizeof(OPEN_CHAPTER_MAGIC) - 1)
50 #define OPEN_CHAPTER_VERSION_LENGTH (sizeof(OPEN_CHAPTER_VERSION) - 1)
55 	return sizeof(struct uds_volume_record) * (1 + open_chapter->capacity);  in records_size()
68 	size_t capacity = geometry->records_per_chapter / zone_count;  in uds_make_open_chapter()
77 	open_chapter->slot_count = slot_count;  in uds_make_open_chapter()
78 	open_chapter->capacity = capacity;  in uds_make_open_chapter()
80 					    &open_chapter->records);  in uds_make_open_chapter()
92 	open_chapter->size = 0;  in uds_reset_open_chapter()
93 	open_chapter->deletions = 0;  in uds_reset_open_chapter()
95 	memset(open_chapter->records, 0, records_size(open_chapter));  in uds_reset_open_chapter()
96 	memset(open_chapter->slots, 0, slots_size(open_chapter->slot_count));  in uds_reset_open_chapter()
103 	unsigned int slot_count = open_chapter->slot_count;  in probe_chapter_slots()
109 		record_number = open_chapter->slots[slot].record_number;  in probe_chapter_slots()
122 		record = &open_chapter->records[record_number];  in probe_chapter_slots()
123 		if ((memcmp(&record->name, name, UDS_RECORD_NAME_SIZE) == 0) &&  in probe_chapter_slots()
124 		    !open_chapter->slots[record_number].deleted)  in probe_chapter_slots()
143 	record_number = open_chapter->slots[slot].record_number;  in uds_search_open_chapter()
148 		*metadata = open_chapter->records[record_number].data;  in uds_search_open_chapter()
161 	if (open_chapter->size >= open_chapter->capacity)  in uds_put_open_chapter()
165 	record_number = open_chapter->slots[slot].record_number;  in uds_put_open_chapter()
168 		record_number = ++open_chapter->size;  in uds_put_open_chapter()
169 		open_chapter->slots[slot].record_number = record_number;  in uds_put_open_chapter()
172 	record = &open_chapter->records[record_number];  in uds_put_open_chapter()
173 	record->name = *name;  in uds_put_open_chapter()
174 	record->data = *metadata;  in uds_put_open_chapter()
176 	return open_chapter->capacity - open_chapter->size;  in uds_put_open_chapter()
186 	record_number = open_chapter->slots[slot].record_number;  in uds_remove_from_open_chapter()
189 		open_chapter->slots[record_number].deleted = true;  in uds_remove_from_open_chapter()
190 		open_chapter->deletions += 1;  in uds_remove_from_open_chapter()
197 		vdo_free(open_chapter->records);  in uds_free_open_chapter()
227 		if (zone->size == zone->capacity) {  in fill_delta_chapter_index()
228 			fill_record = &zone->records[zone->size];  in fill_delta_chapter_index()
233 	records_per_chapter = index->geometry->records_per_chapter;  in fill_delta_chapter_index()
234 	records_per_page = index->geometry->records_per_page;  in fill_delta_chapter_index()
240 		/* The record arrays in the zones are 1-based. */  in fill_delta_chapter_index()
246 		if (record_index > open_chapter->size ||  in fill_delta_chapter_index()
247 		    open_chapter->slots[record_index].deleted) {  in fill_delta_chapter_index()
252 		*record = open_chapter->records[record_index];  in fill_delta_chapter_index()
253 		result = uds_put_open_chapter_index_record(index, &record->name,  in fill_delta_chapter_index()
312 	for (z = 0; z < index->zone_count; z++) {  in uds_save_open_chapter()
313 		open_chapter = index->zones[z]->open_chapter;  in uds_save_open_chapter()
314 		record_count += open_chapter->size - open_chapter->deletions;  in uds_save_open_chapter()
325 		for (z = 0; z < index->zone_count; z++) {  in uds_save_open_chapter()
326 			open_chapter = index->zones[z]->open_chapter;  in uds_save_open_chapter()
327 			if (record_index > open_chapter->size)  in uds_save_open_chapter()
330 			if (open_chapter->slots[record_index].deleted)  in uds_save_open_chapter()
333 			record = &open_chapter->records[record_index];  in uds_save_open_chapter()
339 			record_count--;  in uds_save_open_chapter()
350 	unsigned int records_per_chapter = geometry->records_per_chapter;  in uds_compute_saved_open_chapter_size()
378 	while (record_count-- > 0) {  in load_version20()
386 		if (index->zone_count > 1)  in load_version20()
387 			zone = uds_get_volume_index_zone(index->volume_index,  in load_version20()
394 			open_chapter = index->zones[zone]->open_chapter;  in load_version20()