395 lines · c
1/* SPDX-License-Identifier: GPL-2.0-only */2/*3 * Copyright 2023 Red Hat4 */5 6#ifndef VDO_BLOCK_MAP_H7#define VDO_BLOCK_MAP_H8 9#include <linux/list.h>10 11#include "numeric.h"12 13#include "admin-state.h"14#include "completion.h"15#include "encodings.h"16#include "int-map.h"17#include "statistics.h"18#include "types.h"19#include "vio.h"20#include "wait-queue.h"21 22/*23 * The block map is responsible for tracking all the logical to physical mappings of a VDO. It24 * consists of a collection of 60 radix trees gradually allocated as logical addresses are used.25 * Each tree is assigned to a logical zone such that it is easy to compute which zone must handle26 * each logical address. Each logical zone also has a dedicated portion of the leaf page cache.27 *28 * Each logical zone has a single dedicated queue and thread for performing all updates to the29 * radix trees assigned to that zone. The concurrency guarantees of this single-threaded model30 * allow the code to omit more fine-grained locking for the block map structures.31 *32 * Load operations must be performed on the admin thread. Normal operations, such as reading and33 * updating mappings, must be performed on the appropriate logical zone thread. Save operations34 * must be launched from the same admin thread as the original load operation.35 */36 37enum {38 BLOCK_MAP_VIO_POOL_SIZE = 64,39};40 41/*42 * Generation counter for page references.43 */44typedef u32 vdo_page_generation;45 46extern const struct block_map_entry UNMAPPED_BLOCK_MAP_ENTRY;47 48/* The VDO Page Cache abstraction. */49struct vdo_page_cache {50 /* the VDO which owns this cache */51 struct vdo *vdo;52 /* number of pages in cache */53 page_count_t page_count;54 /* number of pages to write in the current batch */55 page_count_t pages_in_batch;56 /* Whether the VDO is doing a read-only rebuild */57 bool rebuilding;58 59 /* array of page information entries */60 struct page_info *infos;61 /* raw memory for pages */62 char *pages;63 /* cache last found page info */64 struct page_info *last_found;65 /* map of page number to info */66 struct int_map *page_map;67 /* main LRU list (all infos) */68 struct list_head lru_list;69 /* free page list (oldest first) */70 struct list_head free_list;71 /* outgoing page list */72 struct list_head outgoing_list;73 /* number of read I/O operations pending */74 page_count_t outstanding_reads;75 /* number of write I/O operations pending */76 page_count_t outstanding_writes;77 /* number of pages covered by the current flush */78 page_count_t pages_in_flush;79 /* number of pages waiting to be included in the next flush */80 page_count_t pages_to_flush;81 /* number of discards in progress */82 unsigned int discard_count;83 /* how many VPCs waiting for free page */84 unsigned int waiter_count;85 /* queue of waiters who want a free page */86 struct vdo_wait_queue free_waiters;87 /*88 * Statistics are only updated on the logical zone thread, but are accessed from other89 * threads.90 */91 struct block_map_statistics stats;92 /* counter for pressure reports */93 u32 pressure_report;94 /* the block map zone to which this cache belongs */95 struct block_map_zone *zone;96};97 98/*99 * The state of a page buffer. If the page buffer is free no particular page is bound to it,100 * otherwise the page buffer is bound to particular page whose absolute pbn is in the pbn field. If101 * the page is resident or dirty the page data is stable and may be accessed. Otherwise the page is102 * in flight (incoming or outgoing) and its data should not be accessed.103 *104 * @note Update the static data in get_page_state_name() if you change this enumeration.105 */106enum vdo_page_buffer_state {107 /* this page buffer is not being used */108 PS_FREE,109 /* this page is being read from store */110 PS_INCOMING,111 /* attempt to load this page failed */112 PS_FAILED,113 /* this page is valid and un-modified */114 PS_RESIDENT,115 /* this page is valid and modified */116 PS_DIRTY,117 /* this page is being written and should not be used */118 PS_OUTGOING,119 /* not a state */120 PAGE_STATE_COUNT,121} __packed;122 123/*124 * The write status of page125 */126enum vdo_page_write_status {127 WRITE_STATUS_NORMAL,128 WRITE_STATUS_DISCARD,129 WRITE_STATUS_DEFERRED,130} __packed;131 132/* Per-page-slot information. */133struct page_info {134 /* Preallocated page struct vio */135 struct vio *vio;136 /* back-link for references */137 struct vdo_page_cache *cache;138 /* the pbn of the page */139 physical_block_number_t pbn;140 /* page is busy (temporarily locked) */141 u16 busy;142 /* the write status the page */143 enum vdo_page_write_status write_status;144 /* page state */145 enum vdo_page_buffer_state state;146 /* queue of completions awaiting this item */147 struct vdo_wait_queue waiting;148 /* state linked list entry */149 struct list_head state_entry;150 /* LRU entry */151 struct list_head lru_entry;152 /*153 * The earliest recovery journal block containing uncommitted updates to the block map page154 * associated with this page_info. A reference (lock) is held on that block to prevent it155 * from being reaped. When this value changes, the reference on the old value must be156 * released and a reference on the new value must be acquired.157 */158 sequence_number_t recovery_lock;159};160 161/*162 * A completion awaiting a specific page. Also a live reference into the page once completed, until163 * freed.164 */165struct vdo_page_completion {166 /* The generic completion */167 struct vdo_completion completion;168 /* The cache involved */169 struct vdo_page_cache *cache;170 /* The waiter for the pending list */171 struct vdo_waiter waiter;172 /* The absolute physical block number of the page on disk */173 physical_block_number_t pbn;174 /* Whether the page may be modified */175 bool writable;176 /* Whether the page is available */177 bool ready;178 /* The info structure for the page, only valid when ready */179 struct page_info *info;180};181 182struct forest;183 184struct tree_page {185 struct vdo_waiter waiter;186 187 /* Dirty list entry */188 struct list_head entry;189 190 /* If dirty, the tree zone flush generation in which it was last dirtied. */191 u8 generation;192 193 /* Whether this page is an interior tree page being written out. */194 bool writing;195 196 /* If writing, the tree zone flush generation of the copy being written. */197 u8 writing_generation;198 199 /*200 * Sequence number of the earliest recovery journal block containing uncommitted updates to201 * this page202 */203 sequence_number_t recovery_lock;204 205 /* The value of recovery_lock when the this page last started writing */206 sequence_number_t writing_recovery_lock;207 208 char page_buffer[VDO_BLOCK_SIZE];209};210 211enum block_map_page_type {212 VDO_TREE_PAGE,213 VDO_CACHE_PAGE,214};215 216typedef struct list_head dirty_era_t[2];217 218struct dirty_lists {219 /* The number of periods after which an element will be expired */220 block_count_t maximum_age;221 /* The oldest period which has unexpired elements */222 sequence_number_t oldest_period;223 /* One more than the current period */224 sequence_number_t next_period;225 /* The offset in the array of lists of the oldest period */226 block_count_t offset;227 /* Expired pages */228 dirty_era_t expired;229 /* The lists of dirty pages */230 dirty_era_t eras[];231};232 233struct block_map_zone {234 zone_count_t zone_number;235 thread_id_t thread_id;236 struct admin_state state;237 struct block_map *block_map;238 /* Dirty pages, by era*/239 struct dirty_lists *dirty_lists;240 struct vdo_page_cache page_cache;241 data_vio_count_t active_lookups;242 struct int_map *loading_pages;243 struct vio_pool *vio_pool;244 /* The tree page which has issued or will be issuing a flush */245 struct tree_page *flusher;246 struct vdo_wait_queue flush_waiters;247 /* The generation after the most recent flush */248 u8 generation;249 u8 oldest_generation;250 /* The counts of dirty pages in each generation */251 u32 dirty_page_counts[256];252};253 254struct block_map {255 struct vdo *vdo;256 struct action_manager *action_manager;257 /* The absolute PBN of the first root of the tree part of the block map */258 physical_block_number_t root_origin;259 block_count_t root_count;260 261 /* The era point we are currently distributing to the zones */262 sequence_number_t current_era_point;263 /* The next era point */264 sequence_number_t pending_era_point;265 266 /* The number of entries in block map */267 block_count_t entry_count;268 nonce_t nonce;269 struct recovery_journal *journal;270 271 /* The trees for finding block map pages */272 struct forest *forest;273 /* The expanded trees awaiting growth */274 struct forest *next_forest;275 /* The number of entries after growth */276 block_count_t next_entry_count;277 278 zone_count_t zone_count;279 struct block_map_zone zones[];280};281 282/**283 * typedef vdo_entry_callback_fn - A function to be called for each allocated PBN when traversing284 * the forest.285 * @pbn: A PBN of a tree node.286 * @completion: The parent completion of the traversal.287 *288 * Return: VDO_SUCCESS or an error.289 */290typedef int (*vdo_entry_callback_fn)(physical_block_number_t pbn,291 struct vdo_completion *completion);292 293static inline struct vdo_page_completion *as_vdo_page_completion(struct vdo_completion *completion)294{295 vdo_assert_completion_type(completion, VDO_PAGE_COMPLETION);296 return container_of(completion, struct vdo_page_completion, completion);297}298 299void vdo_release_page_completion(struct vdo_completion *completion);300 301void vdo_get_page(struct vdo_page_completion *page_completion,302 struct block_map_zone *zone, physical_block_number_t pbn,303 bool writable, void *parent, vdo_action_fn callback,304 vdo_action_fn error_handler, bool requeue);305 306void vdo_request_page_write(struct vdo_completion *completion);307 308int __must_check vdo_get_cached_page(struct vdo_completion *completion,309 struct block_map_page **page_ptr);310 311int __must_check vdo_invalidate_page_cache(struct vdo_page_cache *cache);312 313static inline struct block_map_page * __must_check314vdo_as_block_map_page(struct tree_page *tree_page)315{316 return (struct block_map_page *) tree_page->page_buffer;317}318 319bool vdo_copy_valid_page(char *buffer, nonce_t nonce,320 physical_block_number_t pbn,321 struct block_map_page *page);322 323void vdo_find_block_map_slot(struct data_vio *data_vio);324 325physical_block_number_t vdo_find_block_map_page_pbn(struct block_map *map,326 page_number_t page_number);327 328void vdo_write_tree_page(struct tree_page *page, struct block_map_zone *zone);329 330void vdo_traverse_forest(struct block_map *map, vdo_entry_callback_fn callback,331 struct vdo_completion *completion);332 333int __must_check vdo_decode_block_map(struct block_map_state_2_0 state,334 block_count_t logical_blocks, struct vdo *vdo,335 struct recovery_journal *journal, nonce_t nonce,336 page_count_t cache_size, block_count_t maximum_age,337 struct block_map **map_ptr);338 339void vdo_drain_block_map(struct block_map *map, const struct admin_state_code *operation,340 struct vdo_completion *parent);341 342void vdo_resume_block_map(struct block_map *map, struct vdo_completion *parent);343 344int __must_check vdo_prepare_to_grow_block_map(struct block_map *map,345 block_count_t new_logical_blocks);346 347void vdo_grow_block_map(struct block_map *map, struct vdo_completion *parent);348 349void vdo_abandon_block_map_growth(struct block_map *map);350 351void vdo_free_block_map(struct block_map *map);352 353struct block_map_state_2_0 __must_check vdo_record_block_map(const struct block_map *map);354 355void vdo_initialize_block_map_from_journal(struct block_map *map,356 struct recovery_journal *journal);357 358zone_count_t vdo_compute_logical_zone(struct data_vio *data_vio);359 360void vdo_advance_block_map_era(struct block_map *map,361 sequence_number_t recovery_block_number);362 363void vdo_update_block_map_page(struct block_map_page *page, struct data_vio *data_vio,364 physical_block_number_t pbn,365 enum block_mapping_state mapping_state,366 sequence_number_t *recovery_lock);367 368void vdo_get_mapped_block(struct data_vio *data_vio);369 370void vdo_put_mapped_block(struct data_vio *data_vio);371 372struct block_map_statistics __must_check vdo_get_block_map_statistics(struct block_map *map);373 374/**375 * vdo_convert_maximum_age() - Convert the maximum age to reflect the new recovery journal format376 * @age: The configured maximum age377 *378 * Return: The converted age379 *380 * In the old recovery journal format, each journal block held 311 entries, and every write bio381 * made two entries. The old maximum age was half the usable journal length. In the new format,382 * each block holds only 217 entries, but each bio only makes one entry. We convert the configured383 * age so that the number of writes in a block map era is the same in the old and new formats. This384 * keeps the bound on the amount of work required to recover the block map from the recovery385 * journal the same across the format change. It also keeps the amortization of block map page386 * writes to write bios the same.387 */388static inline block_count_t vdo_convert_maximum_age(block_count_t age)389{390 return DIV_ROUND_UP(age * RECOVERY_JOURNAL_1_ENTRIES_PER_BLOCK,391 2 * RECOVERY_JOURNAL_ENTRIES_PER_BLOCK);392}393 394#endif /* VDO_BLOCK_MAP_H */395