drivers/md/dm-vdo/slab-depot.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #ifndef VDO_SLAB_DEPOT_H
   7 #define VDO_SLAB_DEPOT_H
   8
   9 #include <linux/atomic.h>
  10 #include <linux/dm-kcopyd.h>
  11 #include <linux/list.h>
  12
  13 #include "numeric.h"
  14
  15 #include "admin-state.h"
  16 #include "completion.h"
  17 #include "data-vio.h"
  18 #include "encodings.h"
  19 #include "physical-zone.h"
  20 #include "priority-table.h"
  21 #include "recovery-journal.h"
  22 #include "statistics.h"
  23 #include "types.h"
  24 #include "vio.h"
  25 #include "wait-queue.h"
  26
  27 /*
  28  * A slab_depot is responsible for managing all of the slabs and block allocators of a VDO. It has
  29  * a single array of slabs in order to eliminate the need for additional math in order to compute
  30  * which physical zone a PBN is in. It also has a block_allocator per zone.
  31  *
  32  * Each physical zone has a single dedicated queue and thread for performing all updates to the
  33  * slabs assigned to that zone. The concurrency guarantees of this single-threaded model allow the
  34  * code to omit more fine-grained locking for the various slab structures. Each physical zone
  35  * maintains a separate copy of the slab summary to remove the need for explicit locking on that
  36  * structure as well.
  37  *
  38  * Load operations must be performed on the admin thread. Normal operations, such as allocations
  39  * and reference count updates, must be performed on the appropriate physical zone thread. Requests
  40  * from the recovery journal to commit slab journal tail blocks must be scheduled from the recovery
  41  * journal thread to run on the appropriate physical zone thread. Save operations must be launched
  42  * from the same admin thread as the original load operation.
  43  */
  44
  45 enum {
  46         /* The number of vios in the vio pool is proportional to the throughput of the VDO. */
  47         BLOCK_ALLOCATOR_VIO_POOL_SIZE = 128,
  48 };
  49
  50 /*
  51  * Represents the possible status of a block.
  52  */
  53 enum reference_status {
  54         RS_FREE, /* this block is free */
  55         RS_SINGLE, /* this block is singly-referenced */
  56         RS_SHARED, /* this block is shared */
  57         RS_PROVISIONAL /* this block is provisionally allocated */
  58 };
  59
  60 struct vdo_slab;
  61
  62 struct journal_lock {
  63         u16 count;
  64         sequence_number_t recovery_start;
  65 };
  66
  67 struct slab_journal {
  68         /* A waiter object for getting a VIO pool entry */
  69         struct vdo_waiter resource_waiter;
  70         /* A waiter object for updating the slab summary */
  71         struct vdo_waiter slab_summary_waiter;
  72         /* A waiter object for getting a vio with which to flush */
  73         struct vdo_waiter flush_waiter;
  74         /* The queue of VIOs waiting to make an entry */
  75         struct vdo_wait_queue entry_waiters;
  76         /* The parent slab reference of this journal */
  77         struct vdo_slab *slab;
  78
  79         /* Whether a tail block commit is pending */
  80         bool waiting_to_commit;
  81         /* Whether the journal is updating the slab summary */
  82         bool updating_slab_summary;
  83         /* Whether the journal is adding entries from the entry_waiters queue */
  84         bool adding_entries;
  85         /* Whether a partial write is in progress */
  86         bool partial_write_in_progress;
  87
  88         /* The oldest block in the journal on disk */
  89         sequence_number_t head;
  90         /* The oldest block in the journal which may not be reaped */
  91         sequence_number_t unreapable;
  92         /* The end of the half-open interval of the active journal */
  93         sequence_number_t tail;
  94         /* The next journal block to be committed */
  95         sequence_number_t next_commit;
  96         /* The tail sequence number that is written in the slab summary */
  97         sequence_number_t summarized;
  98         /* The tail sequence number that was last summarized in slab summary */
  99         sequence_number_t last_summarized;
 100
 101         /* The sequence number of the recovery journal lock */
 102         sequence_number_t recovery_lock;
 103
 104         /*
 105          * The number of entries which fit in a single block. Can't use the constant because unit
 106          * tests change this number.
 107          */
 108         journal_entry_count_t entries_per_block;
 109         /*
 110          * The number of full entries which fit in a single block. Can't use the constant because
 111          * unit tests change this number.
 112          */
 113         journal_entry_count_t full_entries_per_block;
 114
 115         /* The recovery journal of the VDO (slab journal holds locks on it) */
 116         struct recovery_journal *recovery_journal;
 117
 118         /* The statistics shared by all slab journals in our physical zone */
 119         struct slab_journal_statistics *events;
 120         /* A list of the VIO pool entries for outstanding journal block writes */
 121         struct list_head uncommitted_blocks;
 122
 123         /*
 124          * The current tail block header state. This will be packed into the block just before it
 125          * is written.
 126          */
 127         struct slab_journal_block_header tail_header;
 128         /* A pointer to a block-sized buffer holding the packed block data */
 129         struct packed_slab_journal_block *block;
 130
 131         /* The number of blocks in the on-disk journal */
 132         block_count_t size;
 133         /* The number of blocks at which to start pushing reference blocks */
 134         block_count_t flushing_threshold;
 135         /* The number of blocks at which all reference blocks should be writing */
 136         block_count_t flushing_deadline;
 137         /* The number of blocks at which to wait for reference blocks to write */
 138         block_count_t blocking_threshold;
 139         /* The number of blocks at which to scrub the slab before coming online */
 140         block_count_t scrubbing_threshold;
 141
 142         /* This list entry is for block_allocator to keep a queue of dirty journals */
 143         struct list_head dirty_entry;
 144
 145         /* The lock for the oldest unreaped block of the journal */
 146         struct journal_lock *reap_lock;
 147         /* The locks for each on disk block */
 148         struct journal_lock *locks;
 149 };
 150
 151 /*
 152  * Reference_block structure
 153  *
 154  * Blocks are used as a proxy, permitting saves of partial refcounts.
 155  */
 156 struct reference_block {
 157         /* This block waits on the ref_counts to tell it to write */
 158         struct vdo_waiter waiter;
 159         /* The slab to which this reference_block belongs */
 160         struct vdo_slab *slab;
 161         /* The number of references in this block that represent allocations */
 162         block_size_t allocated_count;
 163         /* The slab journal block on which this block must hold a lock */
 164         sequence_number_t slab_journal_lock;
 165         /* The slab journal block which should be released when this block is committed */
 166         sequence_number_t slab_journal_lock_to_release;
 167         /* The point up to which each sector is accurate on disk */
 168         struct journal_point commit_points[VDO_SECTORS_PER_BLOCK];
 169         /* Whether this block has been modified since it was written to disk */
 170         bool is_dirty;
 171         /* Whether this block is currently writing */
 172         bool is_writing;
 173 };
 174
 175 /* The search_cursor represents the saved position of a free block search. */
 176 struct search_cursor {
 177         /* The reference block containing the current search index */
 178         struct reference_block *block;
 179         /* The position at which to start searching for the next free counter */
 180         slab_block_number index;
 181         /* The position just past the last valid counter in the current block */
 182         slab_block_number end_index;
 183
 184         /* A pointer to the first reference block in the slab */
 185         struct reference_block *first_block;
 186         /* A pointer to the last reference block in the slab */
 187         struct reference_block *last_block;
 188 };
 189
 190 enum slab_rebuild_status {
 191         VDO_SLAB_REBUILT,
 192         VDO_SLAB_REPLAYING,
 193         VDO_SLAB_REQUIRES_SCRUBBING,
 194         VDO_SLAB_REQUIRES_HIGH_PRIORITY_SCRUBBING,
 195         VDO_SLAB_REBUILDING,
 196 };
 197
 198 /*
 199  * This is the type declaration for the vdo_slab type. A vdo_slab currently consists of a run of
 200  * 2^23 data blocks, but that will soon change to dedicate a small number of those blocks for
 201  * metadata storage for the reference counts and slab journal for the slab.
 202  *
 203  * A reference count is maintained for each physical block number. The vast majority of blocks have
 204  * a very small reference count (usually 0 or 1). For references less than or equal to MAXIMUM_REFS
 205  * (254) the reference count is stored in counters[pbn].
 206  */
 207 struct vdo_slab {
 208         /* A list entry to queue this slab in a block_allocator list */
 209         struct list_head allocq_entry;
 210
 211         /* The struct block_allocator that owns this slab */
 212         struct block_allocator *allocator;
 213
 214         /* The journal for this slab */
 215         struct slab_journal journal;
 216
 217         /* The slab number of this slab */
 218         slab_count_t slab_number;
 219         /* The offset in the allocator partition of the first block in this slab */
 220         physical_block_number_t start;
 221         /* The offset of the first block past the end of this slab */
 222         physical_block_number_t end;
 223         /* The starting translated PBN of the slab journal */
 224         physical_block_number_t journal_origin;
 225         /* The starting translated PBN of the reference counts */
 226         physical_block_number_t ref_counts_origin;
 227
 228         /* The administrative state of the slab */
 229         struct admin_state state;
 230         /* The status of the slab */
 231         enum slab_rebuild_status status;
 232         /* Whether the slab was ever queued for scrubbing */
 233         bool was_queued_for_scrubbing;
 234
 235         /* The priority at which this slab has been queued for allocation */
 236         u8 priority;
 237
 238         /* Fields beyond this point are the reference counts for the data blocks in this slab. */
 239         /* The size of the counters array */
 240         u32 block_count;
 241         /* The number of free blocks */
 242         u32 free_blocks;
 243         /* The array of reference counts */
 244         vdo_refcount_t *counters; /* use vdo_allocate() to align data ptr */
 245
 246         /* The saved block pointer and array indexes for the free block search */
 247         struct search_cursor search_cursor;
 248
 249         /* A list of the dirty blocks waiting to be written out */
 250         struct vdo_wait_queue dirty_blocks;
 251         /* The number of blocks which are currently writing */
 252         size_t active_count;
 253
 254         /* A waiter object for updating the slab summary */
 255         struct vdo_waiter summary_waiter;
 256
 257         /* The latest slab journal for which there has been a reference count update */
 258         struct journal_point slab_journal_point;
 259
 260         /* The number of reference count blocks */
 261         u32 reference_block_count;
 262         /* reference count block array */
 263         struct reference_block *reference_blocks;
 264 };
 265
 266 enum block_allocator_drain_step {
 267         VDO_DRAIN_ALLOCATOR_START,
 268         VDO_DRAIN_ALLOCATOR_STEP_SCRUBBER,
 269         VDO_DRAIN_ALLOCATOR_STEP_SLABS,
 270         VDO_DRAIN_ALLOCATOR_STEP_SUMMARY,
 271         VDO_DRAIN_ALLOCATOR_STEP_FINISHED,
 272 };
 273
 274 struct slab_scrubber {
 275         /* The queue of slabs to scrub first */
 276         struct list_head high_priority_slabs;
 277         /* The queue of slabs to scrub once there are no high_priority_slabs */
 278         struct list_head slabs;
 279         /* The queue of VIOs waiting for a slab to be scrubbed */
 280         struct vdo_wait_queue waiters;
 281
 282         /*
 283          * The number of slabs that are unrecovered or being scrubbed. This field is modified by
 284          * the physical zone thread, but is queried by other threads.
 285          */
 286         slab_count_t slab_count;
 287
 288         /* The administrative state of the scrubber */
 289         struct admin_state admin_state;
 290         /* Whether to only scrub high-priority slabs */
 291         bool high_priority_only;
 292         /* The slab currently being scrubbed */
 293         struct vdo_slab *slab;
 294         /* The vio for loading slab journal blocks */
 295         struct vio vio;
 296 };
 297
 298 /* A sub-structure for applying actions in parallel to all an allocator's slabs. */
 299 struct slab_actor {
 300         /* The number of slabs performing a slab action */
 301         slab_count_t slab_action_count;
 302         /* The method to call when a slab action has been completed by all slabs */
 303         vdo_action_fn callback;
 304 };
 305
 306 /* A slab_iterator is a structure for iterating over a set of slabs. */
 307 struct slab_iterator {
 308         struct vdo_slab **slabs;
 309         struct vdo_slab *next;
 310         slab_count_t end;
 311         slab_count_t stride;
 312 };
 313
 314 /*
 315  * The slab_summary provides hints during load and recovery about the state of the slabs in order
 316  * to avoid the need to read the slab journals in their entirety before a VDO can come online.
 317  *
 318  * The information in the summary for each slab includes the rough number of free blocks (which is
 319  * used to prioritize scrubbing), the cleanliness of a slab (so that clean slabs containing free
 320  * space will be used on restart), and the location of the tail block of the slab's journal.
 321  *
 322  * The slab_summary has its own partition at the end of the volume which is sized to allow for a
 323  * complete copy of the summary for each of up to 16 physical zones.
 324  *
 325  * During resize, the slab_summary moves its backing partition and is saved once moved; the
 326  * slab_summary is not permitted to overwrite the previous recovery journal space.
 327  *
 328  * The slab_summary does not have its own version information, but relies on the VDO volume version
 329  * number.
 330  */
 331
 332 /*
 333  * A slab status is a very small structure for use in determining the ordering of slabs in the
 334  * scrubbing process.
 335  */
 336 struct slab_status {
 337         slab_count_t slab_number;
 338         bool is_clean;
 339         u8 emptiness;
 340 };
 341
 342 struct slab_summary_block {
 343         /* The block_allocator to which this block belongs */
 344         struct block_allocator *allocator;
 345         /* The index of this block in its zone's summary */
 346         block_count_t index;
 347         /* Whether this block has a write outstanding */
 348         bool writing;
 349         /* Ring of updates waiting on the outstanding write */
 350         struct vdo_wait_queue current_update_waiters;
 351         /* Ring of updates waiting on the next write */
 352         struct vdo_wait_queue next_update_waiters;
 353         /* The active slab_summary_entry array for this block */
 354         struct slab_summary_entry *entries;
 355         /* The vio used to write this block */
 356         struct vio vio;
 357         /* The packed entries, one block long, backing the vio */
 358         char *outgoing_entries;
 359 };
 360
 361 /*
 362  * The statistics for all the slab summary zones owned by this slab summary. These fields are all
 363  * mutated only by their physical zone threads, but are read by other threads when gathering
 364  * statistics for the entire depot.
 365  */
 366 struct atomic_slab_summary_statistics {
 367         /* Number of blocks written */
 368         atomic64_t blocks_written;
 369 };
 370
 371 struct block_allocator {
 372         struct vdo_completion completion;
 373         /* The slab depot for this allocator */
 374         struct slab_depot *depot;
 375         /* The nonce of the VDO */
 376         nonce_t nonce;
 377         /* The physical zone number of this allocator */
 378         zone_count_t zone_number;
 379         /* The thread ID for this allocator's physical zone */
 380         thread_id_t thread_id;
 381         /* The number of slabs in this allocator */
 382         slab_count_t slab_count;
 383         /* The number of the last slab owned by this allocator */
 384         slab_count_t last_slab;
 385         /* The reduced priority level used to preserve unopened slabs */
 386         unsigned int unopened_slab_priority;
 387         /* The state of this allocator */
 388         struct admin_state state;
 389         /* The actor for applying an action to all slabs */
 390         struct slab_actor slab_actor;
 391
 392         /* The slab from which blocks are currently being allocated */
 393         struct vdo_slab *open_slab;
 394         /* A priority queue containing all slabs available for allocation */
 395         struct priority_table *prioritized_slabs;
 396         /* The slab scrubber */
 397         struct slab_scrubber scrubber;
 398         /* What phase of the close operation the allocator is to perform */
 399         enum block_allocator_drain_step drain_step;
 400
 401         /*
 402          * These statistics are all mutated only by the physical zone thread, but are read by other
 403          * threads when gathering statistics for the entire depot.
 404          */
 405         /*
 406          * The count of allocated blocks in this zone. Not in block_allocator_statistics for
 407          * historical reasons.
 408          */
 409         u64 allocated_blocks;
 410         /* Statistics for this block allocator */
 411         struct block_allocator_statistics statistics;
 412         /* Cumulative statistics for the slab journals in this zone */
 413         struct slab_journal_statistics slab_journal_statistics;
 414         /* Cumulative statistics for the reference counters in this zone */
 415         struct ref_counts_statistics ref_counts_statistics;
 416
 417         /*
 418          * This is the head of a queue of slab journals which have entries in their tail blocks
 419          * which have not yet started to commit. When the recovery journal is under space pressure,
 420          * slab journals which have uncommitted entries holding a lock on the recovery journal head
 421          * are forced to commit their blocks early. This list is kept in order, with the tail
 422          * containing the slab journal holding the most recent recovery journal lock.
 423          */
 424         struct list_head dirty_slab_journals;
 425
 426         /* The vio pool for reading and writing block allocator metadata */
 427         struct vio_pool *vio_pool;
 428         /* The dm_kcopyd client for erasing slab journals */
 429         struct dm_kcopyd_client *eraser;
 430         /* Iterator over the slabs to be erased */
 431         struct slab_iterator slabs_to_erase;
 432
 433         /* The portion of the slab summary managed by this allocator */
 434         /* The state of the slab summary */
 435         struct admin_state summary_state;
 436         /* The number of outstanding summary writes */
 437         block_count_t summary_write_count;
 438         /* The array (owned by the blocks) of all entries */
 439         struct slab_summary_entry *summary_entries;
 440         /* The array of slab_summary_blocks */
 441         struct slab_summary_block *summary_blocks;
 442 };
 443
 444 enum slab_depot_load_type {
 445         VDO_SLAB_DEPOT_NORMAL_LOAD,
 446         VDO_SLAB_DEPOT_RECOVERY_LOAD,
 447         VDO_SLAB_DEPOT_REBUILD_LOAD
 448 };
 449
 450 struct slab_depot {
 451         zone_count_t zone_count;
 452         zone_count_t old_zone_count;
 453         struct vdo *vdo;
 454         struct slab_config slab_config;
 455         struct action_manager *action_manager;
 456
 457         physical_block_number_t first_block;
 458         physical_block_number_t last_block;
 459         physical_block_number_t origin;
 460
 461         /* slab_size == (1 << slab_size_shift) */
 462         unsigned int slab_size_shift;
 463
 464         /* Determines how slabs should be queued during load */
 465         enum slab_depot_load_type load_type;
 466
 467         /* The state for notifying slab journals to release recovery journal */
 468         sequence_number_t active_release_request;
 469         sequence_number_t new_release_request;
 470
 471         /* State variables for scrubbing complete handling */
 472         atomic_t zones_to_scrub;
 473
 474         /* Array of pointers to individually allocated slabs */
 475         struct vdo_slab **slabs;
 476         /* The number of slabs currently allocated and stored in 'slabs' */
 477         slab_count_t slab_count;
 478
 479         /* Array of pointers to a larger set of slabs (used during resize) */
 480         struct vdo_slab **new_slabs;
 481         /* The number of slabs currently allocated and stored in 'new_slabs' */
 482         slab_count_t new_slab_count;
 483         /* The size that 'new_slabs' was allocated for */
 484         block_count_t new_size;
 485
 486         /* The last block before resize, for rollback */
 487         physical_block_number_t old_last_block;
 488         /* The last block after resize, for resize */
 489         physical_block_number_t new_last_block;
 490
 491         /* The statistics for the slab summary */
 492         struct atomic_slab_summary_statistics summary_statistics;
 493         /* The start of the slab summary partition */
 494         physical_block_number_t summary_origin;
 495         /* The number of bits to shift to get a 7-bit fullness hint */
 496         unsigned int hint_shift;
 497         /* The slab summary entries for all of the zones the partition can hold */
 498         struct slab_summary_entry *summary_entries;
 499
 500         /* The block allocators for this depot */
 501         struct block_allocator allocators[];
 502 };
 503
 504 struct reference_updater;
 505
 506 bool __must_check vdo_attempt_replay_into_slab(struct vdo_slab *slab,
 507                                                physical_block_number_t pbn,
 508                                                enum journal_operation operation,
 509                                                bool increment,
 510                                                struct journal_point *recovery_point,
 511                                                struct vdo_completion *parent);
 512
 513 int __must_check vdo_adjust_reference_count_for_rebuild(struct slab_depot *depot,
 514                                                         physical_block_number_t pbn,
 515                                                         enum journal_operation operation);
 516
 517 static inline struct block_allocator *vdo_as_block_allocator(struct vdo_completion *completion)
 518 {
 519         vdo_assert_completion_type(completion, VDO_BLOCK_ALLOCATOR_COMPLETION);
 520         return container_of(completion, struct block_allocator, completion);
 521 }
 522
 523 int __must_check vdo_acquire_provisional_reference(struct vdo_slab *slab,
 524                                                    physical_block_number_t pbn,
 525                                                    struct pbn_lock *lock);
 526
 527 int __must_check vdo_allocate_block(struct block_allocator *allocator,
 528                                     physical_block_number_t *block_number_ptr);
 529
 530 int vdo_enqueue_clean_slab_waiter(struct block_allocator *allocator,
 531                                   struct vdo_waiter *waiter);
 532
 533 void vdo_modify_reference_count(struct vdo_completion *completion,
 534                                 struct reference_updater *updater);
 535
 536 int __must_check vdo_release_block_reference(struct block_allocator *allocator,
 537                                              physical_block_number_t pbn);
 538
 539 void vdo_notify_slab_journals_are_recovered(struct vdo_completion *completion);
 540
 541 void vdo_dump_block_allocator(const struct block_allocator *allocator);
 542
 543 int __must_check vdo_decode_slab_depot(struct slab_depot_state_2_0 state,
 544                                        struct vdo *vdo,
 545                                        struct partition *summary_partition,
 546                                        struct slab_depot **depot_ptr);
 547
 548 void vdo_free_slab_depot(struct slab_depot *depot);
 549
 550 struct slab_depot_state_2_0 __must_check vdo_record_slab_depot(const struct slab_depot *depot);
 551
 552 int __must_check vdo_allocate_reference_counters(struct slab_depot *depot);
 553
 554 struct vdo_slab * __must_check vdo_get_slab(const struct slab_depot *depot,
 555                                             physical_block_number_t pbn);
 556
 557 u8 __must_check vdo_get_increment_limit(struct slab_depot *depot,
 558                                         physical_block_number_t pbn);
 559
 560 bool __must_check vdo_is_physical_data_block(const struct slab_depot *depot,
 561                                              physical_block_number_t pbn);
 562
 563 block_count_t __must_check vdo_get_slab_depot_allocated_blocks(const struct slab_depot *depot);
 564
 565 block_count_t __must_check vdo_get_slab_depot_data_blocks(const struct slab_depot *depot);
 566
 567 void vdo_get_slab_depot_statistics(const struct slab_depot *depot,
 568                                    struct vdo_statistics *stats);
 569
 570 void vdo_load_slab_depot(struct slab_depot *depot,
 571                          const struct admin_state_code *operation,
 572                          struct vdo_completion *parent, void *context);
 573
 574 void vdo_prepare_slab_depot_to_allocate(struct slab_depot *depot,
 575                                         enum slab_depot_load_type load_type,
 576                                         struct vdo_completion *parent);
 577
 578 void vdo_update_slab_depot_size(struct slab_depot *depot);
 579
 580 int __must_check vdo_prepare_to_grow_slab_depot(struct slab_depot *depot,
 581                                                 const struct partition *partition);
 582
 583 void vdo_use_new_slabs(struct slab_depot *depot, struct vdo_completion *parent);
 584
 585 void vdo_abandon_new_slabs(struct slab_depot *depot);
 586
 587 void vdo_drain_slab_depot(struct slab_depot *depot,
 588                           const struct admin_state_code *operation,
 589                           struct vdo_completion *parent);
 590
 591 void vdo_resume_slab_depot(struct slab_depot *depot, struct vdo_completion *parent);
 592
 593 void vdo_commit_oldest_slab_journal_tail_blocks(struct slab_depot *depot,
 594                                                 sequence_number_t recovery_block_number);
 595
 596 void vdo_scrub_all_unrecovered_slabs(struct slab_depot *depot,
 597                                      struct vdo_completion *parent);
 598
 599 void vdo_dump_slab_depot(const struct slab_depot *depot);
 600
 601 #endif /* VDO_SLAB_DEPOT_H */