Loading...
Note: File does not exist in v3.1.
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright 2023 Red Hat
4 */
5
6#include "index-layout.h"
7
8#include <linux/random.h>
9
10#include "logger.h"
11#include "memory-alloc.h"
12#include "murmurhash3.h"
13#include "numeric.h"
14#include "time-utils.h"
15
16#include "config.h"
17#include "open-chapter.h"
18#include "volume-index.h"
19
20/*
21 * The UDS layout on storage media is divided into a number of fixed-size regions, the sizes of
22 * which are computed when the index is created. Every header and region begins on 4K block
23 * boundary. Save regions are further sub-divided into regions of their own.
24 *
25 * Each region has a kind and an instance number. Some kinds only have one instance and therefore
26 * use RL_SOLE_INSTANCE (-1) as the instance number. The RL_KIND_INDEX used to use instances to
27 * represent sub-indices; now, however there is only ever one sub-index and therefore one instance.
28 * The RL_KIND_VOLUME_INDEX uses instances to record which zone is being saved.
29 *
30 * Every region header has a type and version.
31 *
32 * +-+-+---------+--------+--------+-+
33 * | | | I N D E X 0 101, 0 | |
34 * |H|C+---------+--------+--------+S|
35 * |D|f| Volume | Save | Save |e|
36 * |R|g| Region | Region | Region |a|
37 * | | | 201, -1 | 202, 0 | 202, 1 |l|
38 * +-+-+--------+---------+--------+-+
39 *
40 * The header contains the encoded region layout table as well as some index configuration data.
41 * The sub-index region and its subdivisions are maintained in the same table.
42 *
43 * There are two save regions to preserve the old state in case saving the new state is incomplete.
44 * They are used in alternation. Each save region is further divided into sub-regions.
45 *
46 * +-+-----+------+------+-----+-----+
47 * |H| IPM | MI | MI | | OC |
48 * |D| | zone | zone | ... | |
49 * |R| 301 | 302 | 302 | | 303 |
50 * | | -1 | 0 | 1 | | -1 |
51 * +-+-----+------+------+-----+-----+
52 *
53 * The header contains the encoded region layout table as well as index state data for that save.
54 * Each save also has a unique nonce.
55 */
56
57#define MAGIC_SIZE 32
58#define NONCE_INFO_SIZE 32
59#define MAX_SAVES 2
60
61enum region_kind {
62 RL_KIND_EMPTY = 0,
63 RL_KIND_HEADER = 1,
64 RL_KIND_CONFIG = 100,
65 RL_KIND_INDEX = 101,
66 RL_KIND_SEAL = 102,
67 RL_KIND_VOLUME = 201,
68 RL_KIND_SAVE = 202,
69 RL_KIND_INDEX_PAGE_MAP = 301,
70 RL_KIND_VOLUME_INDEX = 302,
71 RL_KIND_OPEN_CHAPTER = 303,
72};
73
74/* Some region types are historical and are no longer used. */
75enum region_type {
76 RH_TYPE_FREE = 0, /* unused */
77 RH_TYPE_SUPER = 1,
78 RH_TYPE_SAVE = 2,
79 RH_TYPE_CHECKPOINT = 3, /* unused */
80 RH_TYPE_UNSAVED = 4,
81};
82
83#define RL_SOLE_INSTANCE 65535
84
85/*
86 * Super block version 2 is the first released version.
87 *
88 * Super block version 3 is the normal version used from RHEL 8.2 onwards.
89 *
90 * Super block versions 4 through 6 were incremental development versions and
91 * are not supported.
92 *
93 * Super block version 7 is used for volumes which have been reduced in size by one chapter in
94 * order to make room to prepend LVM metadata to a volume originally created without lvm. This
95 * allows the index to retain most its deduplication records.
96 */
97#define SUPER_VERSION_MINIMUM 3
98#define SUPER_VERSION_CURRENT 3
99#define SUPER_VERSION_MAXIMUM 7
100
101static const u8 LAYOUT_MAGIC[MAGIC_SIZE] = "*ALBIREO*SINGLE*FILE*LAYOUT*001*";
102static const u64 REGION_MAGIC = 0x416c6252676e3031; /* 'AlbRgn01' */
103
104struct region_header {
105 u64 magic;
106 u64 region_blocks;
107 u16 type;
108 /* Currently always version 1 */
109 u16 version;
110 u16 region_count;
111 u16 payload;
112};
113
114struct layout_region {
115 u64 start_block;
116 u64 block_count;
117 u32 __unused;
118 u16 kind;
119 u16 instance;
120};
121
122struct region_table {
123 size_t encoded_size;
124 struct region_header header;
125 struct layout_region regions[];
126};
127
128struct index_save_data {
129 u64 timestamp;
130 u64 nonce;
131 /* Currently always version 1 */
132 u32 version;
133 u32 unused__;
134};
135
136struct index_state_version {
137 s32 signature;
138 s32 version_id;
139};
140
141static const struct index_state_version INDEX_STATE_VERSION_301 = {
142 .signature = -1,
143 .version_id = 301,
144};
145
146struct index_state_data301 {
147 struct index_state_version version;
148 u64 newest_chapter;
149 u64 oldest_chapter;
150 u64 last_save;
151 u32 unused;
152 u32 padding;
153};
154
155struct index_save_layout {
156 unsigned int zone_count;
157 struct layout_region index_save;
158 struct layout_region header;
159 struct layout_region index_page_map;
160 struct layout_region free_space;
161 struct layout_region volume_index_zones[MAX_ZONES];
162 struct layout_region open_chapter;
163 struct index_save_data save_data;
164 struct index_state_data301 state_data;
165};
166
167struct sub_index_layout {
168 u64 nonce;
169 struct layout_region sub_index;
170 struct layout_region volume;
171 struct index_save_layout *saves;
172};
173
174struct super_block_data {
175 u8 magic_label[MAGIC_SIZE];
176 u8 nonce_info[NONCE_INFO_SIZE];
177 u64 nonce;
178 u32 version;
179 u32 block_size;
180 u16 index_count;
181 u16 max_saves;
182 /* Padding reflects a blank field on permanent storage */
183 u8 padding[4];
184 u64 open_chapter_blocks;
185 u64 page_map_blocks;
186 u64 volume_offset;
187 u64 start_offset;
188};
189
190struct index_layout {
191 struct io_factory *factory;
192 size_t factory_size;
193 off_t offset;
194 struct super_block_data super;
195 struct layout_region header;
196 struct layout_region config;
197 struct sub_index_layout index;
198 struct layout_region seal;
199 u64 total_blocks;
200};
201
202struct save_layout_sizes {
203 unsigned int save_count;
204 size_t block_size;
205 u64 volume_blocks;
206 u64 volume_index_blocks;
207 u64 page_map_blocks;
208 u64 open_chapter_blocks;
209 u64 save_blocks;
210 u64 sub_index_blocks;
211 u64 total_blocks;
212 size_t total_size;
213};
214
215static inline bool is_converted_super_block(struct super_block_data *super)
216{
217 return super->version == 7;
218}
219
220static int __must_check compute_sizes(const struct uds_configuration *config,
221 struct save_layout_sizes *sls)
222{
223 int result;
224 struct index_geometry *geometry = config->geometry;
225
226 memset(sls, 0, sizeof(*sls));
227 sls->save_count = MAX_SAVES;
228 sls->block_size = UDS_BLOCK_SIZE;
229 sls->volume_blocks = geometry->bytes_per_volume / sls->block_size;
230
231 result = uds_compute_volume_index_save_blocks(config, sls->block_size,
232 &sls->volume_index_blocks);
233 if (result != UDS_SUCCESS)
234 return vdo_log_error_strerror(result, "cannot compute index save size");
235
236 sls->page_map_blocks =
237 DIV_ROUND_UP(uds_compute_index_page_map_save_size(geometry),
238 sls->block_size);
239 sls->open_chapter_blocks =
240 DIV_ROUND_UP(uds_compute_saved_open_chapter_size(geometry),
241 sls->block_size);
242 sls->save_blocks =
243 1 + (sls->volume_index_blocks + sls->page_map_blocks + sls->open_chapter_blocks);
244 sls->sub_index_blocks = sls->volume_blocks + (sls->save_count * sls->save_blocks);
245 sls->total_blocks = 3 + sls->sub_index_blocks;
246 sls->total_size = sls->total_blocks * sls->block_size;
247
248 return UDS_SUCCESS;
249}
250
251int uds_compute_index_size(const struct uds_parameters *parameters, u64 *index_size)
252{
253 int result;
254 struct uds_configuration *index_config;
255 struct save_layout_sizes sizes;
256
257 if (index_size == NULL) {
258 vdo_log_error("Missing output size pointer");
259 return -EINVAL;
260 }
261
262 result = uds_make_configuration(parameters, &index_config);
263 if (result != UDS_SUCCESS) {
264 vdo_log_error_strerror(result, "cannot compute index size");
265 return uds_status_to_errno(result);
266 }
267
268 result = compute_sizes(index_config, &sizes);
269 uds_free_configuration(index_config);
270 if (result != UDS_SUCCESS)
271 return uds_status_to_errno(result);
272
273 *index_size = sizes.total_size;
274 return UDS_SUCCESS;
275}
276
277/* Create unique data using the current time and a pseudorandom number. */
278static void create_unique_nonce_data(u8 *buffer)
279{
280 ktime_t now = current_time_ns(CLOCK_REALTIME);
281 u32 rand;
282 size_t offset = 0;
283
284 get_random_bytes(&rand, sizeof(u32));
285 memcpy(buffer + offset, &now, sizeof(now));
286 offset += sizeof(now);
287 memcpy(buffer + offset, &rand, sizeof(rand));
288 offset += sizeof(rand);
289 while (offset < NONCE_INFO_SIZE) {
290 size_t len = min(NONCE_INFO_SIZE - offset, offset);
291
292 memcpy(buffer + offset, buffer, len);
293 offset += len;
294 }
295}
296
297static u64 hash_stuff(u64 start, const void *data, size_t len)
298{
299 u32 seed = start ^ (start >> 27);
300 u8 hash_buffer[16];
301
302 murmurhash3_128(data, len, seed, hash_buffer);
303 return get_unaligned_le64(hash_buffer + 4);
304}
305
306/* Generate a primary nonce from the provided data. */
307static u64 generate_primary_nonce(const void *data, size_t len)
308{
309 return hash_stuff(0xa1b1e0fc, data, len);
310}
311
312/*
313 * Deterministically generate a secondary nonce from an existing nonce and some arbitrary data by
314 * hashing the original nonce and the data to produce a new nonce.
315 */
316static u64 generate_secondary_nonce(u64 nonce, const void *data, size_t len)
317{
318 return hash_stuff(nonce + 1, data, len);
319}
320
321static int __must_check open_layout_reader(struct index_layout *layout,
322 struct layout_region *lr, off_t offset,
323 struct buffered_reader **reader_ptr)
324{
325 return uds_make_buffered_reader(layout->factory, lr->start_block + offset,
326 lr->block_count, reader_ptr);
327}
328
329static int open_region_reader(struct index_layout *layout, struct layout_region *region,
330 struct buffered_reader **reader_ptr)
331{
332 return open_layout_reader(layout, region, -layout->super.start_offset,
333 reader_ptr);
334}
335
336static int __must_check open_layout_writer(struct index_layout *layout,
337 struct layout_region *lr, off_t offset,
338 struct buffered_writer **writer_ptr)
339{
340 return uds_make_buffered_writer(layout->factory, lr->start_block + offset,
341 lr->block_count, writer_ptr);
342}
343
344static int open_region_writer(struct index_layout *layout, struct layout_region *region,
345 struct buffered_writer **writer_ptr)
346{
347 return open_layout_writer(layout, region, -layout->super.start_offset,
348 writer_ptr);
349}
350
351static void generate_super_block_data(struct save_layout_sizes *sls,
352 struct super_block_data *super)
353{
354 memset(super, 0, sizeof(*super));
355 memcpy(super->magic_label, LAYOUT_MAGIC, MAGIC_SIZE);
356 create_unique_nonce_data(super->nonce_info);
357
358 super->nonce = generate_primary_nonce(super->nonce_info,
359 sizeof(super->nonce_info));
360 super->version = SUPER_VERSION_CURRENT;
361 super->block_size = sls->block_size;
362 super->index_count = 1;
363 super->max_saves = sls->save_count;
364 super->open_chapter_blocks = sls->open_chapter_blocks;
365 super->page_map_blocks = sls->page_map_blocks;
366 super->volume_offset = 0;
367 super->start_offset = 0;
368}
369
370static void define_sub_index_nonce(struct index_layout *layout)
371{
372 struct sub_index_nonce_data {
373 u64 offset;
374 u16 index_id;
375 };
376 struct sub_index_layout *sil = &layout->index;
377 u64 primary_nonce = layout->super.nonce;
378 u8 buffer[sizeof(struct sub_index_nonce_data)] = { 0 };
379 size_t offset = 0;
380
381 encode_u64_le(buffer, &offset, sil->sub_index.start_block);
382 encode_u16_le(buffer, &offset, 0);
383 sil->nonce = generate_secondary_nonce(primary_nonce, buffer, sizeof(buffer));
384 if (sil->nonce == 0) {
385 sil->nonce = generate_secondary_nonce(~primary_nonce + 1, buffer,
386 sizeof(buffer));
387 }
388}
389
390static void setup_sub_index(struct index_layout *layout, u64 start_block,
391 struct save_layout_sizes *sls)
392{
393 struct sub_index_layout *sil = &layout->index;
394 u64 next_block = start_block;
395 unsigned int i;
396
397 sil->sub_index = (struct layout_region) {
398 .start_block = start_block,
399 .block_count = sls->sub_index_blocks,
400 .kind = RL_KIND_INDEX,
401 .instance = 0,
402 };
403
404 sil->volume = (struct layout_region) {
405 .start_block = next_block,
406 .block_count = sls->volume_blocks,
407 .kind = RL_KIND_VOLUME,
408 .instance = RL_SOLE_INSTANCE,
409 };
410
411 next_block += sls->volume_blocks;
412
413 for (i = 0; i < sls->save_count; i++) {
414 sil->saves[i].index_save = (struct layout_region) {
415 .start_block = next_block,
416 .block_count = sls->save_blocks,
417 .kind = RL_KIND_SAVE,
418 .instance = i,
419 };
420
421 next_block += sls->save_blocks;
422 }
423
424 define_sub_index_nonce(layout);
425}
426
427static void initialize_layout(struct index_layout *layout, struct save_layout_sizes *sls)
428{
429 u64 next_block = layout->offset / sls->block_size;
430
431 layout->total_blocks = sls->total_blocks;
432 generate_super_block_data(sls, &layout->super);
433 layout->header = (struct layout_region) {
434 .start_block = next_block++,
435 .block_count = 1,
436 .kind = RL_KIND_HEADER,
437 .instance = RL_SOLE_INSTANCE,
438 };
439
440 layout->config = (struct layout_region) {
441 .start_block = next_block++,
442 .block_count = 1,
443 .kind = RL_KIND_CONFIG,
444 .instance = RL_SOLE_INSTANCE,
445 };
446
447 setup_sub_index(layout, next_block, sls);
448 next_block += sls->sub_index_blocks;
449
450 layout->seal = (struct layout_region) {
451 .start_block = next_block,
452 .block_count = 1,
453 .kind = RL_KIND_SEAL,
454 .instance = RL_SOLE_INSTANCE,
455 };
456}
457
458static int __must_check make_index_save_region_table(struct index_save_layout *isl,
459 struct region_table **table_ptr)
460{
461 int result;
462 unsigned int z;
463 struct region_table *table;
464 struct layout_region *lr;
465 u16 region_count;
466 size_t payload;
467 size_t type;
468
469 if (isl->zone_count > 0) {
470 /*
471 * Normal save regions: header, page map, volume index zones,
472 * open chapter, and possibly free space.
473 */
474 region_count = 3 + isl->zone_count;
475 if (isl->free_space.block_count > 0)
476 region_count++;
477
478 payload = sizeof(isl->save_data) + sizeof(isl->state_data);
479 type = RH_TYPE_SAVE;
480 } else {
481 /* Empty save regions: header, page map, free space. */
482 region_count = 3;
483 payload = sizeof(isl->save_data);
484 type = RH_TYPE_UNSAVED;
485 }
486
487 result = vdo_allocate_extended(struct region_table, region_count,
488 struct layout_region,
489 "layout region table for ISL", &table);
490 if (result != VDO_SUCCESS)
491 return result;
492
493 lr = &table->regions[0];
494 *lr++ = isl->header;
495 *lr++ = isl->index_page_map;
496 for (z = 0; z < isl->zone_count; z++)
497 *lr++ = isl->volume_index_zones[z];
498
499 if (isl->zone_count > 0)
500 *lr++ = isl->open_chapter;
501
502 if (isl->free_space.block_count > 0)
503 *lr++ = isl->free_space;
504
505 table->header = (struct region_header) {
506 .magic = REGION_MAGIC,
507 .region_blocks = isl->index_save.block_count,
508 .type = type,
509 .version = 1,
510 .region_count = region_count,
511 .payload = payload,
512 };
513
514 table->encoded_size = (sizeof(struct region_header) + payload +
515 region_count * sizeof(struct layout_region));
516 *table_ptr = table;
517 return UDS_SUCCESS;
518}
519
520static void encode_region_table(u8 *buffer, size_t *offset, struct region_table *table)
521{
522 unsigned int i;
523
524 encode_u64_le(buffer, offset, REGION_MAGIC);
525 encode_u64_le(buffer, offset, table->header.region_blocks);
526 encode_u16_le(buffer, offset, table->header.type);
527 encode_u16_le(buffer, offset, table->header.version);
528 encode_u16_le(buffer, offset, table->header.region_count);
529 encode_u16_le(buffer, offset, table->header.payload);
530
531 for (i = 0; i < table->header.region_count; i++) {
532 encode_u64_le(buffer, offset, table->regions[i].start_block);
533 encode_u64_le(buffer, offset, table->regions[i].block_count);
534 encode_u32_le(buffer, offset, 0);
535 encode_u16_le(buffer, offset, table->regions[i].kind);
536 encode_u16_le(buffer, offset, table->regions[i].instance);
537 }
538}
539
540static int __must_check write_index_save_header(struct index_save_layout *isl,
541 struct region_table *table,
542 struct buffered_writer *writer)
543{
544 int result;
545 u8 *buffer;
546 size_t offset = 0;
547
548 result = vdo_allocate(table->encoded_size, u8, "index save data", &buffer);
549 if (result != VDO_SUCCESS)
550 return result;
551
552 encode_region_table(buffer, &offset, table);
553 encode_u64_le(buffer, &offset, isl->save_data.timestamp);
554 encode_u64_le(buffer, &offset, isl->save_data.nonce);
555 encode_u32_le(buffer, &offset, isl->save_data.version);
556 encode_u32_le(buffer, &offset, 0);
557 if (isl->zone_count > 0) {
558 encode_u32_le(buffer, &offset, INDEX_STATE_VERSION_301.signature);
559 encode_u32_le(buffer, &offset, INDEX_STATE_VERSION_301.version_id);
560 encode_u64_le(buffer, &offset, isl->state_data.newest_chapter);
561 encode_u64_le(buffer, &offset, isl->state_data.oldest_chapter);
562 encode_u64_le(buffer, &offset, isl->state_data.last_save);
563 encode_u64_le(buffer, &offset, 0);
564 }
565
566 result = uds_write_to_buffered_writer(writer, buffer, offset);
567 vdo_free(buffer);
568 if (result != UDS_SUCCESS)
569 return result;
570
571 return uds_flush_buffered_writer(writer);
572}
573
574static int write_index_save_layout(struct index_layout *layout,
575 struct index_save_layout *isl)
576{
577 int result;
578 struct region_table *table;
579 struct buffered_writer *writer;
580
581 result = make_index_save_region_table(isl, &table);
582 if (result != UDS_SUCCESS)
583 return result;
584
585 result = open_region_writer(layout, &isl->header, &writer);
586 if (result != UDS_SUCCESS) {
587 vdo_free(table);
588 return result;
589 }
590
591 result = write_index_save_header(isl, table, writer);
592 vdo_free(table);
593 uds_free_buffered_writer(writer);
594
595 return result;
596}
597
598static void reset_index_save_layout(struct index_save_layout *isl, u64 page_map_blocks)
599{
600 u64 free_blocks;
601 u64 next_block = isl->index_save.start_block;
602
603 isl->zone_count = 0;
604 memset(&isl->save_data, 0, sizeof(isl->save_data));
605
606 isl->header = (struct layout_region) {
607 .start_block = next_block++,
608 .block_count = 1,
609 .kind = RL_KIND_HEADER,
610 .instance = RL_SOLE_INSTANCE,
611 };
612
613 isl->index_page_map = (struct layout_region) {
614 .start_block = next_block,
615 .block_count = page_map_blocks,
616 .kind = RL_KIND_INDEX_PAGE_MAP,
617 .instance = RL_SOLE_INSTANCE,
618 };
619
620 next_block += page_map_blocks;
621
622 free_blocks = isl->index_save.block_count - page_map_blocks - 1;
623 isl->free_space = (struct layout_region) {
624 .start_block = next_block,
625 .block_count = free_blocks,
626 .kind = RL_KIND_EMPTY,
627 .instance = RL_SOLE_INSTANCE,
628 };
629}
630
631static int __must_check invalidate_old_save(struct index_layout *layout,
632 struct index_save_layout *isl)
633{
634 reset_index_save_layout(isl, layout->super.page_map_blocks);
635 return write_index_save_layout(layout, isl);
636}
637
638static int discard_index_state_data(struct index_layout *layout)
639{
640 int result;
641 int saved_result = UDS_SUCCESS;
642 unsigned int i;
643
644 for (i = 0; i < layout->super.max_saves; i++) {
645 result = invalidate_old_save(layout, &layout->index.saves[i]);
646 if (result != UDS_SUCCESS)
647 saved_result = result;
648 }
649
650 if (saved_result != UDS_SUCCESS) {
651 return vdo_log_error_strerror(result,
652 "%s: cannot destroy all index saves",
653 __func__);
654 }
655
656 return UDS_SUCCESS;
657}
658
659static int __must_check make_layout_region_table(struct index_layout *layout,
660 struct region_table **table_ptr)
661{
662 int result;
663 unsigned int i;
664 /* Regions: header, config, index, volume, saves, seal */
665 u16 region_count = 5 + layout->super.max_saves;
666 u16 payload;
667 struct region_table *table;
668 struct layout_region *lr;
669
670 result = vdo_allocate_extended(struct region_table, region_count,
671 struct layout_region, "layout region table",
672 &table);
673 if (result != VDO_SUCCESS)
674 return result;
675
676 lr = &table->regions[0];
677 *lr++ = layout->header;
678 *lr++ = layout->config;
679 *lr++ = layout->index.sub_index;
680 *lr++ = layout->index.volume;
681
682 for (i = 0; i < layout->super.max_saves; i++)
683 *lr++ = layout->index.saves[i].index_save;
684
685 *lr++ = layout->seal;
686
687 if (is_converted_super_block(&layout->super)) {
688 payload = sizeof(struct super_block_data);
689 } else {
690 payload = (sizeof(struct super_block_data) -
691 sizeof(layout->super.volume_offset) -
692 sizeof(layout->super.start_offset));
693 }
694
695 table->header = (struct region_header) {
696 .magic = REGION_MAGIC,
697 .region_blocks = layout->total_blocks,
698 .type = RH_TYPE_SUPER,
699 .version = 1,
700 .region_count = region_count,
701 .payload = payload,
702 };
703
704 table->encoded_size = (sizeof(struct region_header) + payload +
705 region_count * sizeof(struct layout_region));
706 *table_ptr = table;
707 return UDS_SUCCESS;
708}
709
710static int __must_check write_layout_header(struct index_layout *layout,
711 struct region_table *table,
712 struct buffered_writer *writer)
713{
714 int result;
715 u8 *buffer;
716 size_t offset = 0;
717
718 result = vdo_allocate(table->encoded_size, u8, "layout data", &buffer);
719 if (result != VDO_SUCCESS)
720 return result;
721
722 encode_region_table(buffer, &offset, table);
723 memcpy(buffer + offset, &layout->super.magic_label, MAGIC_SIZE);
724 offset += MAGIC_SIZE;
725 memcpy(buffer + offset, &layout->super.nonce_info, NONCE_INFO_SIZE);
726 offset += NONCE_INFO_SIZE;
727 encode_u64_le(buffer, &offset, layout->super.nonce);
728 encode_u32_le(buffer, &offset, layout->super.version);
729 encode_u32_le(buffer, &offset, layout->super.block_size);
730 encode_u16_le(buffer, &offset, layout->super.index_count);
731 encode_u16_le(buffer, &offset, layout->super.max_saves);
732 encode_u32_le(buffer, &offset, 0);
733 encode_u64_le(buffer, &offset, layout->super.open_chapter_blocks);
734 encode_u64_le(buffer, &offset, layout->super.page_map_blocks);
735
736 if (is_converted_super_block(&layout->super)) {
737 encode_u64_le(buffer, &offset, layout->super.volume_offset);
738 encode_u64_le(buffer, &offset, layout->super.start_offset);
739 }
740
741 result = uds_write_to_buffered_writer(writer, buffer, offset);
742 vdo_free(buffer);
743 if (result != UDS_SUCCESS)
744 return result;
745
746 return uds_flush_buffered_writer(writer);
747}
748
749static int __must_check write_uds_index_config(struct index_layout *layout,
750 struct uds_configuration *config,
751 off_t offset)
752{
753 int result;
754 struct buffered_writer *writer = NULL;
755
756 result = open_layout_writer(layout, &layout->config, offset, &writer);
757 if (result != UDS_SUCCESS)
758 return vdo_log_error_strerror(result, "failed to open config region");
759
760 result = uds_write_config_contents(writer, config, layout->super.version);
761 if (result != UDS_SUCCESS) {
762 uds_free_buffered_writer(writer);
763 return vdo_log_error_strerror(result, "failed to write config region");
764 }
765
766 result = uds_flush_buffered_writer(writer);
767 if (result != UDS_SUCCESS) {
768 uds_free_buffered_writer(writer);
769 return vdo_log_error_strerror(result, "cannot flush config writer");
770 }
771
772 uds_free_buffered_writer(writer);
773 return UDS_SUCCESS;
774}
775
776static int __must_check save_layout(struct index_layout *layout, off_t offset)
777{
778 int result;
779 struct buffered_writer *writer = NULL;
780 struct region_table *table;
781
782 result = make_layout_region_table(layout, &table);
783 if (result != UDS_SUCCESS)
784 return result;
785
786 result = open_layout_writer(layout, &layout->header, offset, &writer);
787 if (result != UDS_SUCCESS) {
788 vdo_free(table);
789 return result;
790 }
791
792 result = write_layout_header(layout, table, writer);
793 vdo_free(table);
794 uds_free_buffered_writer(writer);
795
796 return result;
797}
798
799static int create_index_layout(struct index_layout *layout, struct uds_configuration *config)
800{
801 int result;
802 struct save_layout_sizes sizes;
803
804 result = compute_sizes(config, &sizes);
805 if (result != UDS_SUCCESS)
806 return result;
807
808 result = vdo_allocate(sizes.save_count, struct index_save_layout, __func__,
809 &layout->index.saves);
810 if (result != VDO_SUCCESS)
811 return result;
812
813 initialize_layout(layout, &sizes);
814
815 result = discard_index_state_data(layout);
816 if (result != UDS_SUCCESS)
817 return result;
818
819 result = write_uds_index_config(layout, config, 0);
820 if (result != UDS_SUCCESS)
821 return result;
822
823 return save_layout(layout, 0);
824}
825
826static u64 generate_index_save_nonce(u64 volume_nonce, struct index_save_layout *isl)
827{
828 struct save_nonce_data {
829 struct index_save_data data;
830 u64 offset;
831 } nonce_data;
832 u8 buffer[sizeof(nonce_data)];
833 size_t offset = 0;
834
835 encode_u64_le(buffer, &offset, isl->save_data.timestamp);
836 encode_u64_le(buffer, &offset, 0);
837 encode_u32_le(buffer, &offset, isl->save_data.version);
838 encode_u32_le(buffer, &offset, 0U);
839 encode_u64_le(buffer, &offset, isl->index_save.start_block);
840 VDO_ASSERT_LOG_ONLY(offset == sizeof(nonce_data),
841 "%zu bytes encoded of %zu expected",
842 offset, sizeof(nonce_data));
843 return generate_secondary_nonce(volume_nonce, buffer, sizeof(buffer));
844}
845
846static u64 validate_index_save_layout(struct index_save_layout *isl, u64 volume_nonce)
847{
848 if ((isl->zone_count == 0) || (isl->save_data.timestamp == 0))
849 return 0;
850
851 if (isl->save_data.nonce != generate_index_save_nonce(volume_nonce, isl))
852 return 0;
853
854 return isl->save_data.timestamp;
855}
856
857static int find_latest_uds_index_save_slot(struct index_layout *layout,
858 struct index_save_layout **isl_ptr)
859{
860 struct index_save_layout *latest = NULL;
861 struct index_save_layout *isl;
862 unsigned int i;
863 u64 save_time = 0;
864 u64 latest_time = 0;
865
866 for (i = 0; i < layout->super.max_saves; i++) {
867 isl = &layout->index.saves[i];
868 save_time = validate_index_save_layout(isl, layout->index.nonce);
869 if (save_time > latest_time) {
870 latest = isl;
871 latest_time = save_time;
872 }
873 }
874
875 if (latest == NULL) {
876 vdo_log_error("No valid index save found");
877 return UDS_INDEX_NOT_SAVED_CLEANLY;
878 }
879
880 *isl_ptr = latest;
881 return UDS_SUCCESS;
882}
883
884int uds_discard_open_chapter(struct index_layout *layout)
885{
886 int result;
887 struct index_save_layout *isl;
888 struct buffered_writer *writer;
889
890 result = find_latest_uds_index_save_slot(layout, &isl);
891 if (result != UDS_SUCCESS)
892 return result;
893
894 result = open_region_writer(layout, &isl->open_chapter, &writer);
895 if (result != UDS_SUCCESS)
896 return result;
897
898 result = uds_write_to_buffered_writer(writer, NULL, UDS_BLOCK_SIZE);
899 if (result != UDS_SUCCESS) {
900 uds_free_buffered_writer(writer);
901 return result;
902 }
903
904 result = uds_flush_buffered_writer(writer);
905 uds_free_buffered_writer(writer);
906 return result;
907}
908
909int uds_load_index_state(struct index_layout *layout, struct uds_index *index)
910{
911 int result;
912 unsigned int zone;
913 struct index_save_layout *isl;
914 struct buffered_reader *readers[MAX_ZONES];
915
916 result = find_latest_uds_index_save_slot(layout, &isl);
917 if (result != UDS_SUCCESS)
918 return result;
919
920 index->newest_virtual_chapter = isl->state_data.newest_chapter;
921 index->oldest_virtual_chapter = isl->state_data.oldest_chapter;
922 index->last_save = isl->state_data.last_save;
923
924 result = open_region_reader(layout, &isl->open_chapter, &readers[0]);
925 if (result != UDS_SUCCESS)
926 return result;
927
928 result = uds_load_open_chapter(index, readers[0]);
929 uds_free_buffered_reader(readers[0]);
930 if (result != UDS_SUCCESS)
931 return result;
932
933 for (zone = 0; zone < isl->zone_count; zone++) {
934 result = open_region_reader(layout, &isl->volume_index_zones[zone],
935 &readers[zone]);
936 if (result != UDS_SUCCESS) {
937 for (; zone > 0; zone--)
938 uds_free_buffered_reader(readers[zone - 1]);
939
940 return result;
941 }
942 }
943
944 result = uds_load_volume_index(index->volume_index, readers, isl->zone_count);
945 for (zone = 0; zone < isl->zone_count; zone++)
946 uds_free_buffered_reader(readers[zone]);
947 if (result != UDS_SUCCESS)
948 return result;
949
950 result = open_region_reader(layout, &isl->index_page_map, &readers[0]);
951 if (result != UDS_SUCCESS)
952 return result;
953
954 result = uds_read_index_page_map(index->volume->index_page_map, readers[0]);
955 uds_free_buffered_reader(readers[0]);
956
957 return result;
958}
959
960static struct index_save_layout *select_oldest_index_save_layout(struct index_layout *layout)
961{
962 struct index_save_layout *oldest = NULL;
963 struct index_save_layout *isl;
964 unsigned int i;
965 u64 save_time = 0;
966 u64 oldest_time = 0;
967
968 for (i = 0; i < layout->super.max_saves; i++) {
969 isl = &layout->index.saves[i];
970 save_time = validate_index_save_layout(isl, layout->index.nonce);
971 if (oldest == NULL || save_time < oldest_time) {
972 oldest = isl;
973 oldest_time = save_time;
974 }
975 }
976
977 return oldest;
978}
979
980static void instantiate_index_save_layout(struct index_save_layout *isl,
981 struct super_block_data *super,
982 u64 volume_nonce, unsigned int zone_count)
983{
984 unsigned int z;
985 u64 next_block;
986 u64 free_blocks;
987 u64 volume_index_blocks;
988
989 isl->zone_count = zone_count;
990 memset(&isl->save_data, 0, sizeof(isl->save_data));
991 isl->save_data.timestamp = ktime_to_ms(current_time_ns(CLOCK_REALTIME));
992 isl->save_data.version = 1;
993 isl->save_data.nonce = generate_index_save_nonce(volume_nonce, isl);
994
995 next_block = isl->index_save.start_block;
996 isl->header = (struct layout_region) {
997 .start_block = next_block++,
998 .block_count = 1,
999 .kind = RL_KIND_HEADER,
1000 .instance = RL_SOLE_INSTANCE,
1001 };
1002
1003 isl->index_page_map = (struct layout_region) {
1004 .start_block = next_block,
1005 .block_count = super->page_map_blocks,
1006 .kind = RL_KIND_INDEX_PAGE_MAP,
1007 .instance = RL_SOLE_INSTANCE,
1008 };
1009 next_block += super->page_map_blocks;
1010
1011 free_blocks = (isl->index_save.block_count - 1 -
1012 super->page_map_blocks -
1013 super->open_chapter_blocks);
1014 volume_index_blocks = free_blocks / isl->zone_count;
1015 for (z = 0; z < isl->zone_count; z++) {
1016 isl->volume_index_zones[z] = (struct layout_region) {
1017 .start_block = next_block,
1018 .block_count = volume_index_blocks,
1019 .kind = RL_KIND_VOLUME_INDEX,
1020 .instance = z,
1021 };
1022
1023 next_block += volume_index_blocks;
1024 free_blocks -= volume_index_blocks;
1025 }
1026
1027 isl->open_chapter = (struct layout_region) {
1028 .start_block = next_block,
1029 .block_count = super->open_chapter_blocks,
1030 .kind = RL_KIND_OPEN_CHAPTER,
1031 .instance = RL_SOLE_INSTANCE,
1032 };
1033
1034 next_block += super->open_chapter_blocks;
1035
1036 isl->free_space = (struct layout_region) {
1037 .start_block = next_block,
1038 .block_count = free_blocks,
1039 .kind = RL_KIND_EMPTY,
1040 .instance = RL_SOLE_INSTANCE,
1041 };
1042}
1043
1044static int setup_uds_index_save_slot(struct index_layout *layout,
1045 unsigned int zone_count,
1046 struct index_save_layout **isl_ptr)
1047{
1048 int result;
1049 struct index_save_layout *isl;
1050
1051 isl = select_oldest_index_save_layout(layout);
1052 result = invalidate_old_save(layout, isl);
1053 if (result != UDS_SUCCESS)
1054 return result;
1055
1056 instantiate_index_save_layout(isl, &layout->super, layout->index.nonce,
1057 zone_count);
1058
1059 *isl_ptr = isl;
1060 return UDS_SUCCESS;
1061}
1062
1063static void cancel_uds_index_save(struct index_save_layout *isl)
1064{
1065 memset(&isl->save_data, 0, sizeof(isl->save_data));
1066 memset(&isl->state_data, 0, sizeof(isl->state_data));
1067 isl->zone_count = 0;
1068}
1069
1070int uds_save_index_state(struct index_layout *layout, struct uds_index *index)
1071{
1072 int result;
1073 unsigned int zone;
1074 struct index_save_layout *isl;
1075 struct buffered_writer *writers[MAX_ZONES];
1076
1077 result = setup_uds_index_save_slot(layout, index->zone_count, &isl);
1078 if (result != UDS_SUCCESS)
1079 return result;
1080
1081 isl->state_data = (struct index_state_data301) {
1082 .newest_chapter = index->newest_virtual_chapter,
1083 .oldest_chapter = index->oldest_virtual_chapter,
1084 .last_save = index->last_save,
1085 };
1086
1087 result = open_region_writer(layout, &isl->open_chapter, &writers[0]);
1088 if (result != UDS_SUCCESS) {
1089 cancel_uds_index_save(isl);
1090 return result;
1091 }
1092
1093 result = uds_save_open_chapter(index, writers[0]);
1094 uds_free_buffered_writer(writers[0]);
1095 if (result != UDS_SUCCESS) {
1096 cancel_uds_index_save(isl);
1097 return result;
1098 }
1099
1100 for (zone = 0; zone < index->zone_count; zone++) {
1101 result = open_region_writer(layout, &isl->volume_index_zones[zone],
1102 &writers[zone]);
1103 if (result != UDS_SUCCESS) {
1104 for (; zone > 0; zone--)
1105 uds_free_buffered_writer(writers[zone - 1]);
1106
1107 cancel_uds_index_save(isl);
1108 return result;
1109 }
1110 }
1111
1112 result = uds_save_volume_index(index->volume_index, writers, index->zone_count);
1113 for (zone = 0; zone < index->zone_count; zone++)
1114 uds_free_buffered_writer(writers[zone]);
1115 if (result != UDS_SUCCESS) {
1116 cancel_uds_index_save(isl);
1117 return result;
1118 }
1119
1120 result = open_region_writer(layout, &isl->index_page_map, &writers[0]);
1121 if (result != UDS_SUCCESS) {
1122 cancel_uds_index_save(isl);
1123 return result;
1124 }
1125
1126 result = uds_write_index_page_map(index->volume->index_page_map, writers[0]);
1127 uds_free_buffered_writer(writers[0]);
1128 if (result != UDS_SUCCESS) {
1129 cancel_uds_index_save(isl);
1130 return result;
1131 }
1132
1133 return write_index_save_layout(layout, isl);
1134}
1135
1136static int __must_check load_region_table(struct buffered_reader *reader,
1137 struct region_table **table_ptr)
1138{
1139 int result;
1140 unsigned int i;
1141 struct region_header header;
1142 struct region_table *table;
1143 u8 buffer[sizeof(struct region_header)];
1144 size_t offset = 0;
1145
1146 result = uds_read_from_buffered_reader(reader, buffer, sizeof(buffer));
1147 if (result != UDS_SUCCESS)
1148 return vdo_log_error_strerror(result, "cannot read region table header");
1149
1150 decode_u64_le(buffer, &offset, &header.magic);
1151 decode_u64_le(buffer, &offset, &header.region_blocks);
1152 decode_u16_le(buffer, &offset, &header.type);
1153 decode_u16_le(buffer, &offset, &header.version);
1154 decode_u16_le(buffer, &offset, &header.region_count);
1155 decode_u16_le(buffer, &offset, &header.payload);
1156
1157 if (header.magic != REGION_MAGIC)
1158 return UDS_NO_INDEX;
1159
1160 if (header.version != 1) {
1161 return vdo_log_error_strerror(UDS_UNSUPPORTED_VERSION,
1162 "unknown region table version %hu",
1163 header.version);
1164 }
1165
1166 result = vdo_allocate_extended(struct region_table, header.region_count,
1167 struct layout_region,
1168 "single file layout region table", &table);
1169 if (result != VDO_SUCCESS)
1170 return result;
1171
1172 table->header = header;
1173 for (i = 0; i < header.region_count; i++) {
1174 u8 region_buffer[sizeof(struct layout_region)];
1175
1176 offset = 0;
1177 result = uds_read_from_buffered_reader(reader, region_buffer,
1178 sizeof(region_buffer));
1179 if (result != UDS_SUCCESS) {
1180 vdo_free(table);
1181 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1182 "cannot read region table layouts");
1183 }
1184
1185 decode_u64_le(region_buffer, &offset, &table->regions[i].start_block);
1186 decode_u64_le(region_buffer, &offset, &table->regions[i].block_count);
1187 offset += sizeof(u32);
1188 decode_u16_le(region_buffer, &offset, &table->regions[i].kind);
1189 decode_u16_le(region_buffer, &offset, &table->regions[i].instance);
1190 }
1191
1192 *table_ptr = table;
1193 return UDS_SUCCESS;
1194}
1195
1196static int __must_check read_super_block_data(struct buffered_reader *reader,
1197 struct index_layout *layout,
1198 size_t saved_size)
1199{
1200 int result;
1201 struct super_block_data *super = &layout->super;
1202 u8 *buffer;
1203 size_t offset = 0;
1204
1205 result = vdo_allocate(saved_size, u8, "super block data", &buffer);
1206 if (result != VDO_SUCCESS)
1207 return result;
1208
1209 result = uds_read_from_buffered_reader(reader, buffer, saved_size);
1210 if (result != UDS_SUCCESS) {
1211 vdo_free(buffer);
1212 return vdo_log_error_strerror(result, "cannot read region table header");
1213 }
1214
1215 memcpy(&super->magic_label, buffer, MAGIC_SIZE);
1216 offset += MAGIC_SIZE;
1217 memcpy(&super->nonce_info, buffer + offset, NONCE_INFO_SIZE);
1218 offset += NONCE_INFO_SIZE;
1219 decode_u64_le(buffer, &offset, &super->nonce);
1220 decode_u32_le(buffer, &offset, &super->version);
1221 decode_u32_le(buffer, &offset, &super->block_size);
1222 decode_u16_le(buffer, &offset, &super->index_count);
1223 decode_u16_le(buffer, &offset, &super->max_saves);
1224 offset += sizeof(u32);
1225 decode_u64_le(buffer, &offset, &super->open_chapter_blocks);
1226 decode_u64_le(buffer, &offset, &super->page_map_blocks);
1227
1228 if (is_converted_super_block(super)) {
1229 decode_u64_le(buffer, &offset, &super->volume_offset);
1230 decode_u64_le(buffer, &offset, &super->start_offset);
1231 } else {
1232 super->volume_offset = 0;
1233 super->start_offset = 0;
1234 }
1235
1236 vdo_free(buffer);
1237
1238 if (memcmp(super->magic_label, LAYOUT_MAGIC, MAGIC_SIZE) != 0)
1239 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1240 "unknown superblock magic label");
1241
1242 if ((super->version < SUPER_VERSION_MINIMUM) ||
1243 (super->version == 4) || (super->version == 5) || (super->version == 6) ||
1244 (super->version > SUPER_VERSION_MAXIMUM)) {
1245 return vdo_log_error_strerror(UDS_UNSUPPORTED_VERSION,
1246 "unknown superblock version number %u",
1247 super->version);
1248 }
1249
1250 if (super->volume_offset < super->start_offset) {
1251 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1252 "inconsistent offsets (start %llu, volume %llu)",
1253 (unsigned long long) super->start_offset,
1254 (unsigned long long) super->volume_offset);
1255 }
1256
1257 /* Sub-indexes are no longer used but the layout retains this field. */
1258 if (super->index_count != 1) {
1259 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1260 "invalid subindex count %u",
1261 super->index_count);
1262 }
1263
1264 if (generate_primary_nonce(super->nonce_info, sizeof(super->nonce_info)) != super->nonce) {
1265 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1266 "inconsistent superblock nonce");
1267 }
1268
1269 return UDS_SUCCESS;
1270}
1271
1272static int __must_check verify_region(struct layout_region *lr, u64 start_block,
1273 enum region_kind kind, unsigned int instance)
1274{
1275 if (lr->start_block != start_block)
1276 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1277 "incorrect layout region offset");
1278
1279 if (lr->kind != kind)
1280 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1281 "incorrect layout region kind");
1282
1283 if (lr->instance != instance) {
1284 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1285 "incorrect layout region instance");
1286 }
1287
1288 return UDS_SUCCESS;
1289}
1290
1291static int __must_check verify_sub_index(struct index_layout *layout, u64 start_block,
1292 struct region_table *table)
1293{
1294 int result;
1295 unsigned int i;
1296 struct sub_index_layout *sil = &layout->index;
1297 u64 next_block = start_block;
1298
1299 sil->sub_index = table->regions[2];
1300 result = verify_region(&sil->sub_index, next_block, RL_KIND_INDEX, 0);
1301 if (result != UDS_SUCCESS)
1302 return result;
1303
1304 define_sub_index_nonce(layout);
1305
1306 sil->volume = table->regions[3];
1307 result = verify_region(&sil->volume, next_block, RL_KIND_VOLUME,
1308 RL_SOLE_INSTANCE);
1309 if (result != UDS_SUCCESS)
1310 return result;
1311
1312 next_block += sil->volume.block_count + layout->super.volume_offset;
1313
1314 for (i = 0; i < layout->super.max_saves; i++) {
1315 sil->saves[i].index_save = table->regions[i + 4];
1316 result = verify_region(&sil->saves[i].index_save, next_block,
1317 RL_KIND_SAVE, i);
1318 if (result != UDS_SUCCESS)
1319 return result;
1320
1321 next_block += sil->saves[i].index_save.block_count;
1322 }
1323
1324 next_block -= layout->super.volume_offset;
1325 if (next_block != start_block + sil->sub_index.block_count) {
1326 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1327 "sub index region does not span all saves");
1328 }
1329
1330 return UDS_SUCCESS;
1331}
1332
1333static int __must_check reconstitute_layout(struct index_layout *layout,
1334 struct region_table *table, u64 first_block)
1335{
1336 int result;
1337 u64 next_block = first_block;
1338
1339 result = vdo_allocate(layout->super.max_saves, struct index_save_layout,
1340 __func__, &layout->index.saves);
1341 if (result != VDO_SUCCESS)
1342 return result;
1343
1344 layout->total_blocks = table->header.region_blocks;
1345
1346 layout->header = table->regions[0];
1347 result = verify_region(&layout->header, next_block++, RL_KIND_HEADER,
1348 RL_SOLE_INSTANCE);
1349 if (result != UDS_SUCCESS)
1350 return result;
1351
1352 layout->config = table->regions[1];
1353 result = verify_region(&layout->config, next_block++, RL_KIND_CONFIG,
1354 RL_SOLE_INSTANCE);
1355 if (result != UDS_SUCCESS)
1356 return result;
1357
1358 result = verify_sub_index(layout, next_block, table);
1359 if (result != UDS_SUCCESS)
1360 return result;
1361
1362 next_block += layout->index.sub_index.block_count;
1363
1364 layout->seal = table->regions[table->header.region_count - 1];
1365 result = verify_region(&layout->seal, next_block + layout->super.volume_offset,
1366 RL_KIND_SEAL, RL_SOLE_INSTANCE);
1367 if (result != UDS_SUCCESS)
1368 return result;
1369
1370 if (++next_block != (first_block + layout->total_blocks)) {
1371 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1372 "layout table does not span total blocks");
1373 }
1374
1375 return UDS_SUCCESS;
1376}
1377
1378static int __must_check load_super_block(struct index_layout *layout, size_t block_size,
1379 u64 first_block, struct buffered_reader *reader)
1380{
1381 int result;
1382 struct region_table *table = NULL;
1383 struct super_block_data *super = &layout->super;
1384
1385 result = load_region_table(reader, &table);
1386 if (result != UDS_SUCCESS)
1387 return result;
1388
1389 if (table->header.type != RH_TYPE_SUPER) {
1390 vdo_free(table);
1391 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1392 "not a superblock region table");
1393 }
1394
1395 result = read_super_block_data(reader, layout, table->header.payload);
1396 if (result != UDS_SUCCESS) {
1397 vdo_free(table);
1398 return vdo_log_error_strerror(result, "unknown superblock format");
1399 }
1400
1401 if (super->block_size != block_size) {
1402 vdo_free(table);
1403 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1404 "superblock saved block_size %u differs from supplied block_size %zu",
1405 super->block_size, block_size);
1406 }
1407
1408 first_block -= (super->volume_offset - super->start_offset);
1409 result = reconstitute_layout(layout, table, first_block);
1410 vdo_free(table);
1411 return result;
1412}
1413
1414static int __must_check read_index_save_data(struct buffered_reader *reader,
1415 struct index_save_layout *isl,
1416 size_t saved_size)
1417{
1418 int result;
1419 struct index_state_version file_version;
1420 u8 buffer[sizeof(struct index_save_data) + sizeof(struct index_state_data301)];
1421 size_t offset = 0;
1422
1423 if (saved_size != sizeof(buffer)) {
1424 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1425 "unexpected index save data size %zu",
1426 saved_size);
1427 }
1428
1429 result = uds_read_from_buffered_reader(reader, buffer, sizeof(buffer));
1430 if (result != UDS_SUCCESS)
1431 return vdo_log_error_strerror(result, "cannot read index save data");
1432
1433 decode_u64_le(buffer, &offset, &isl->save_data.timestamp);
1434 decode_u64_le(buffer, &offset, &isl->save_data.nonce);
1435 decode_u32_le(buffer, &offset, &isl->save_data.version);
1436 offset += sizeof(u32);
1437
1438 if (isl->save_data.version > 1) {
1439 return vdo_log_error_strerror(UDS_UNSUPPORTED_VERSION,
1440 "unknown index save version number %u",
1441 isl->save_data.version);
1442 }
1443
1444 decode_s32_le(buffer, &offset, &file_version.signature);
1445 decode_s32_le(buffer, &offset, &file_version.version_id);
1446
1447 if ((file_version.signature != INDEX_STATE_VERSION_301.signature) ||
1448 (file_version.version_id != INDEX_STATE_VERSION_301.version_id)) {
1449 return vdo_log_error_strerror(UDS_UNSUPPORTED_VERSION,
1450 "index state version %d,%d is unsupported",
1451 file_version.signature,
1452 file_version.version_id);
1453 }
1454
1455 decode_u64_le(buffer, &offset, &isl->state_data.newest_chapter);
1456 decode_u64_le(buffer, &offset, &isl->state_data.oldest_chapter);
1457 decode_u64_le(buffer, &offset, &isl->state_data.last_save);
1458 /* Skip past some historical fields that are now unused */
1459 offset += sizeof(u32) + sizeof(u32);
1460 return UDS_SUCCESS;
1461}
1462
1463static int __must_check reconstruct_index_save(struct index_save_layout *isl,
1464 struct region_table *table)
1465{
1466 int result;
1467 unsigned int z;
1468 struct layout_region *last_region;
1469 u64 next_block = isl->index_save.start_block;
1470 u64 last_block = next_block + isl->index_save.block_count;
1471
1472 isl->zone_count = table->header.region_count - 3;
1473
1474 last_region = &table->regions[table->header.region_count - 1];
1475 if (last_region->kind == RL_KIND_EMPTY) {
1476 isl->free_space = *last_region;
1477 isl->zone_count--;
1478 } else {
1479 isl->free_space = (struct layout_region) {
1480 .start_block = last_block,
1481 .block_count = 0,
1482 .kind = RL_KIND_EMPTY,
1483 .instance = RL_SOLE_INSTANCE,
1484 };
1485 }
1486
1487 isl->header = table->regions[0];
1488 result = verify_region(&isl->header, next_block++, RL_KIND_HEADER,
1489 RL_SOLE_INSTANCE);
1490 if (result != UDS_SUCCESS)
1491 return result;
1492
1493 isl->index_page_map = table->regions[1];
1494 result = verify_region(&isl->index_page_map, next_block, RL_KIND_INDEX_PAGE_MAP,
1495 RL_SOLE_INSTANCE);
1496 if (result != UDS_SUCCESS)
1497 return result;
1498
1499 next_block += isl->index_page_map.block_count;
1500
1501 for (z = 0; z < isl->zone_count; z++) {
1502 isl->volume_index_zones[z] = table->regions[z + 2];
1503 result = verify_region(&isl->volume_index_zones[z], next_block,
1504 RL_KIND_VOLUME_INDEX, z);
1505 if (result != UDS_SUCCESS)
1506 return result;
1507
1508 next_block += isl->volume_index_zones[z].block_count;
1509 }
1510
1511 isl->open_chapter = table->regions[isl->zone_count + 2];
1512 result = verify_region(&isl->open_chapter, next_block, RL_KIND_OPEN_CHAPTER,
1513 RL_SOLE_INSTANCE);
1514 if (result != UDS_SUCCESS)
1515 return result;
1516
1517 next_block += isl->open_chapter.block_count;
1518
1519 result = verify_region(&isl->free_space, next_block, RL_KIND_EMPTY,
1520 RL_SOLE_INSTANCE);
1521 if (result != UDS_SUCCESS)
1522 return result;
1523
1524 next_block += isl->free_space.block_count;
1525 if (next_block != last_block) {
1526 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1527 "index save layout table incomplete");
1528 }
1529
1530 return UDS_SUCCESS;
1531}
1532
1533static int __must_check load_index_save(struct index_save_layout *isl,
1534 struct buffered_reader *reader,
1535 unsigned int instance)
1536{
1537 int result;
1538 struct region_table *table = NULL;
1539
1540 result = load_region_table(reader, &table);
1541 if (result != UDS_SUCCESS) {
1542 return vdo_log_error_strerror(result, "cannot read index save %u header",
1543 instance);
1544 }
1545
1546 if (table->header.region_blocks != isl->index_save.block_count) {
1547 u64 region_blocks = table->header.region_blocks;
1548
1549 vdo_free(table);
1550 return vdo_log_error_strerror(UDS_CORRUPT_DATA,
1551 "unexpected index save %u region block count %llu",
1552 instance,
1553 (unsigned long long) region_blocks);
1554 }
1555
1556 if (table->header.type == RH_TYPE_UNSAVED) {
1557 vdo_free(table);
1558 reset_index_save_layout(isl, 0);
1559 return UDS_SUCCESS;
1560 }
1561
1562
1563 if (table->header.type != RH_TYPE_SAVE) {
1564 vdo_log_error_strerror(UDS_CORRUPT_DATA,
1565 "unexpected index save %u header type %u",
1566 instance, table->header.type);
1567 vdo_free(table);
1568 return UDS_CORRUPT_DATA;
1569 }
1570
1571 result = read_index_save_data(reader, isl, table->header.payload);
1572 if (result != UDS_SUCCESS) {
1573 vdo_free(table);
1574 return vdo_log_error_strerror(result,
1575 "unknown index save %u data format",
1576 instance);
1577 }
1578
1579 result = reconstruct_index_save(isl, table);
1580 vdo_free(table);
1581 if (result != UDS_SUCCESS) {
1582 return vdo_log_error_strerror(result, "cannot reconstruct index save %u",
1583 instance);
1584 }
1585
1586 return UDS_SUCCESS;
1587}
1588
1589static int __must_check load_sub_index_regions(struct index_layout *layout)
1590{
1591 int result;
1592 unsigned int j;
1593 struct index_save_layout *isl;
1594 struct buffered_reader *reader;
1595
1596 for (j = 0; j < layout->super.max_saves; j++) {
1597 isl = &layout->index.saves[j];
1598 result = open_region_reader(layout, &isl->index_save, &reader);
1599
1600 if (result != UDS_SUCCESS) {
1601 vdo_log_error_strerror(result,
1602 "cannot get reader for index 0 save %u",
1603 j);
1604 return result;
1605 }
1606
1607 result = load_index_save(isl, reader, j);
1608 uds_free_buffered_reader(reader);
1609 if (result != UDS_SUCCESS) {
1610 /* Another save slot might be valid. */
1611 reset_index_save_layout(isl, 0);
1612 continue;
1613 }
1614 }
1615
1616 return UDS_SUCCESS;
1617}
1618
1619static int __must_check verify_uds_index_config(struct index_layout *layout,
1620 struct uds_configuration *config)
1621{
1622 int result;
1623 struct buffered_reader *reader = NULL;
1624 u64 offset;
1625
1626 offset = layout->super.volume_offset - layout->super.start_offset;
1627 result = open_layout_reader(layout, &layout->config, offset, &reader);
1628 if (result != UDS_SUCCESS)
1629 return vdo_log_error_strerror(result, "failed to open config reader");
1630
1631 result = uds_validate_config_contents(reader, config);
1632 if (result != UDS_SUCCESS) {
1633 uds_free_buffered_reader(reader);
1634 return vdo_log_error_strerror(result, "failed to read config region");
1635 }
1636
1637 uds_free_buffered_reader(reader);
1638 return UDS_SUCCESS;
1639}
1640
1641static int load_index_layout(struct index_layout *layout, struct uds_configuration *config)
1642{
1643 int result;
1644 struct buffered_reader *reader;
1645
1646 result = uds_make_buffered_reader(layout->factory,
1647 layout->offset / UDS_BLOCK_SIZE, 1, &reader);
1648 if (result != UDS_SUCCESS)
1649 return vdo_log_error_strerror(result, "unable to read superblock");
1650
1651 result = load_super_block(layout, UDS_BLOCK_SIZE,
1652 layout->offset / UDS_BLOCK_SIZE, reader);
1653 uds_free_buffered_reader(reader);
1654 if (result != UDS_SUCCESS)
1655 return result;
1656
1657 result = verify_uds_index_config(layout, config);
1658 if (result != UDS_SUCCESS)
1659 return result;
1660
1661 return load_sub_index_regions(layout);
1662}
1663
1664static int create_layout_factory(struct index_layout *layout,
1665 const struct uds_configuration *config)
1666{
1667 int result;
1668 size_t writable_size;
1669 struct io_factory *factory = NULL;
1670
1671 result = uds_make_io_factory(config->bdev, &factory);
1672 if (result != UDS_SUCCESS)
1673 return result;
1674
1675 writable_size = uds_get_writable_size(factory) & -UDS_BLOCK_SIZE;
1676 if (writable_size < config->size + config->offset) {
1677 uds_put_io_factory(factory);
1678 vdo_log_error("index storage (%zu) is smaller than the requested size %zu",
1679 writable_size, config->size + config->offset);
1680 return -ENOSPC;
1681 }
1682
1683 layout->factory = factory;
1684 layout->factory_size = (config->size > 0) ? config->size : writable_size;
1685 layout->offset = config->offset;
1686 return UDS_SUCCESS;
1687}
1688
1689int uds_make_index_layout(struct uds_configuration *config, bool new_layout,
1690 struct index_layout **layout_ptr)
1691{
1692 int result;
1693 struct index_layout *layout = NULL;
1694 struct save_layout_sizes sizes;
1695
1696 result = compute_sizes(config, &sizes);
1697 if (result != UDS_SUCCESS)
1698 return result;
1699
1700 result = vdo_allocate(1, struct index_layout, __func__, &layout);
1701 if (result != VDO_SUCCESS)
1702 return result;
1703
1704 result = create_layout_factory(layout, config);
1705 if (result != UDS_SUCCESS) {
1706 uds_free_index_layout(layout);
1707 return result;
1708 }
1709
1710 if (layout->factory_size < sizes.total_size) {
1711 vdo_log_error("index storage (%zu) is smaller than the required size %llu",
1712 layout->factory_size,
1713 (unsigned long long) sizes.total_size);
1714 uds_free_index_layout(layout);
1715 return -ENOSPC;
1716 }
1717
1718 if (new_layout)
1719 result = create_index_layout(layout, config);
1720 else
1721 result = load_index_layout(layout, config);
1722 if (result != UDS_SUCCESS) {
1723 uds_free_index_layout(layout);
1724 return result;
1725 }
1726
1727 *layout_ptr = layout;
1728 return UDS_SUCCESS;
1729}
1730
1731void uds_free_index_layout(struct index_layout *layout)
1732{
1733 if (layout == NULL)
1734 return;
1735
1736 vdo_free(layout->index.saves);
1737 if (layout->factory != NULL)
1738 uds_put_io_factory(layout->factory);
1739
1740 vdo_free(layout);
1741}
1742
1743int uds_replace_index_layout_storage(struct index_layout *layout,
1744 struct block_device *bdev)
1745{
1746 return uds_replace_storage(layout->factory, bdev);
1747}
1748
1749/* Obtain a dm_bufio_client for the volume region. */
1750int uds_open_volume_bufio(struct index_layout *layout, size_t block_size,
1751 unsigned int reserved_buffers,
1752 struct dm_bufio_client **client_ptr)
1753{
1754 off_t offset = (layout->index.volume.start_block +
1755 layout->super.volume_offset -
1756 layout->super.start_offset);
1757
1758 return uds_make_bufio(layout->factory, offset, block_size, reserved_buffers,
1759 client_ptr);
1760}
1761
1762u64 uds_get_volume_nonce(struct index_layout *layout)
1763{
1764 return layout->index.nonce;
1765}