git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/extents.h

   1 #ifndef _BCACHEFS_EXTENTS_H
   2 #define _BCACHEFS_EXTENTS_H
   3
   4 #include "bcachefs.h"
   5 #include "bkey.h"
   6 #include "io_types.h"
   7
   8 struct bch_fs;
   9 struct journal_res;
  10 struct btree_node_iter;
  11 struct btree_insert;
  12 struct btree_insert_entry;
  13 struct extent_insert_hook;
  14 struct bch_devs_mask;
  15 union bch_extent_crc;
  16
  17 struct btree_nr_keys bch2_key_sort_fix_overlapping(struct bset *,
  18                                                   struct btree *,
  19                                                   struct btree_node_iter *);
  20 struct btree_nr_keys bch2_extent_sort_fix_overlapping(struct bch_fs *c,
  21                                                      struct bset *,
  22                                                      struct btree *,
  23                                                      struct btree_node_iter *);
  24
  25 extern const struct bkey_ops bch2_bkey_btree_ops;
  26 extern const struct bkey_ops bch2_bkey_extent_ops;
  27
  28 struct extent_pick_ptr
  29 bch2_btree_pick_ptr(struct bch_fs *, const struct btree *,
  30                     struct bch_devs_mask *avoid);
  31
  32 void bch2_extent_pick_ptr(struct bch_fs *, struct bkey_s_c,
  33                           struct bch_devs_mask *,
  34                           struct extent_pick_ptr *);
  35
  36 enum btree_insert_ret
  37 bch2_insert_fixup_extent(struct btree_insert *,
  38                         struct btree_insert_entry *);
  39
  40 bool bch2_extent_normalize(struct bch_fs *, struct bkey_s);
  41 void bch2_extent_mark_replicas_cached(struct bch_fs *,
  42                                      struct bkey_s_extent, unsigned);
  43
  44 unsigned bch2_extent_nr_ptrs(struct bkey_s_c_extent);
  45 unsigned bch2_extent_nr_dirty_ptrs(struct bkey_s_c);
  46
  47 static inline bool bkey_extent_is_data(const struct bkey *k)
  48 {
  49         switch (k->type) {
  50         case BCH_EXTENT:
  51         case BCH_EXTENT_CACHED:
  52                 return true;
  53         default:
  54                 return false;
  55         }
  56 }
  57
  58 static inline bool bkey_extent_is_allocation(const struct bkey *k)
  59 {
  60         switch (k->type) {
  61         case BCH_EXTENT:
  62         case BCH_EXTENT_CACHED:
  63         case BCH_RESERVATION:
  64                 return true;
  65         default:
  66                 return false;
  67         }
  68 }
  69
  70 static inline bool bkey_extent_is_cached(const struct bkey *k)
  71 {
  72         return k->type == BCH_EXTENT_CACHED;
  73 }
  74
  75 static inline void bkey_extent_set_cached(struct bkey *k, bool cached)
  76 {
  77         EBUG_ON(k->type != BCH_EXTENT &&
  78                 k->type != BCH_EXTENT_CACHED);
  79
  80         k->type = cached ? BCH_EXTENT_CACHED : BCH_EXTENT;
  81 }
  82
  83 static inline unsigned
  84 __extent_entry_type(const union bch_extent_entry *e)
  85 {
  86         return e->type ? __ffs(e->type) : BCH_EXTENT_ENTRY_MAX;
  87 }
  88
  89 static inline enum bch_extent_entry_type
  90 extent_entry_type(const union bch_extent_entry *e)
  91 {
  92         int ret = __ffs(e->type);
  93
  94         EBUG_ON(ret < 0 || ret >= BCH_EXTENT_ENTRY_MAX);
  95
  96         return ret;
  97 }
  98
  99 static inline size_t extent_entry_bytes(const union bch_extent_entry *entry)
 100 {
 101         switch (extent_entry_type(entry)) {
 102         case BCH_EXTENT_ENTRY_crc32:
 103                 return sizeof(struct bch_extent_crc32);
 104         case BCH_EXTENT_ENTRY_crc64:
 105                 return sizeof(struct bch_extent_crc64);
 106         case BCH_EXTENT_ENTRY_crc128:
 107                 return sizeof(struct bch_extent_crc128);
 108         case BCH_EXTENT_ENTRY_ptr:
 109                 return sizeof(struct bch_extent_ptr);
 110         default:
 111                 BUG();
 112         }
 113 }
 114
 115 static inline size_t extent_entry_u64s(const union bch_extent_entry *entry)
 116 {
 117         return extent_entry_bytes(entry) / sizeof(u64);
 118 }
 119
 120 static inline bool extent_entry_is_ptr(const union bch_extent_entry *e)
 121 {
 122         return extent_entry_type(e) == BCH_EXTENT_ENTRY_ptr;
 123 }
 124
 125 static inline bool extent_entry_is_crc(const union bch_extent_entry *e)
 126 {
 127         return !extent_entry_is_ptr(e);
 128 }
 129
 130 union bch_extent_crc {
 131         u8                              type;
 132         struct bch_extent_crc32         crc32;
 133         struct bch_extent_crc64         crc64;
 134         struct bch_extent_crc128        crc128;
 135 };
 136
 137 /* downcast, preserves const */
 138 #define to_entry(_entry)                                                \
 139 ({                                                                      \
 140         BUILD_BUG_ON(!type_is(_entry, union bch_extent_crc *) &&        \
 141                      !type_is(_entry, struct bch_extent_ptr *));        \
 142                                                                         \
 143         __builtin_choose_expr(                                          \
 144                 (type_is_exact(_entry, const union bch_extent_crc *) || \
 145                  type_is_exact(_entry, const struct bch_extent_ptr *)), \
 146                 (const union bch_extent_entry *) (_entry),              \
 147                 (union bch_extent_entry *) (_entry));                   \
 148 })
 149
 150 #define __entry_to_crc(_entry)                                          \
 151         __builtin_choose_expr(                                          \
 152                 type_is_exact(_entry, const union bch_extent_entry *),  \
 153                 (const union bch_extent_crc *) (_entry),                \
 154                 (union bch_extent_crc *) (_entry))
 155
 156 #define entry_to_crc(_entry)                                            \
 157 ({                                                                      \
 158         EBUG_ON((_entry) && !extent_entry_is_crc(_entry));              \
 159                                                                         \
 160         __entry_to_crc(_entry);                                         \
 161 })
 162
 163 #define entry_to_ptr(_entry)                                            \
 164 ({                                                                      \
 165         EBUG_ON((_entry) && !extent_entry_is_ptr(_entry));              \
 166                                                                         \
 167         __builtin_choose_expr(                                          \
 168                 type_is_exact(_entry, const union bch_extent_entry *),  \
 169                 (const struct bch_extent_ptr *) (_entry),               \
 170                 (struct bch_extent_ptr *) (_entry));                    \
 171 })
 172
 173 enum bch_extent_crc_type {
 174         BCH_EXTENT_CRC_NONE,
 175         BCH_EXTENT_CRC32,
 176         BCH_EXTENT_CRC64,
 177         BCH_EXTENT_CRC128,
 178 };
 179
 180 static inline enum bch_extent_crc_type
 181 __extent_crc_type(const union bch_extent_crc *crc)
 182 {
 183         if (!crc)
 184                 return BCH_EXTENT_CRC_NONE;
 185
 186         switch (extent_entry_type(to_entry(crc))) {
 187         case BCH_EXTENT_ENTRY_crc32:
 188                 return BCH_EXTENT_CRC32;
 189         case BCH_EXTENT_ENTRY_crc64:
 190                 return BCH_EXTENT_CRC64;
 191         case BCH_EXTENT_ENTRY_crc128:
 192                 return BCH_EXTENT_CRC128;
 193         default:
 194                 BUG();
 195         }
 196 }
 197
 198 #define extent_crc_type(_crc)                                           \
 199 ({                                                                      \
 200         BUILD_BUG_ON(!type_is(_crc, struct bch_extent_crc32 *) &&       \
 201                      !type_is(_crc, struct bch_extent_crc64 *) &&       \
 202                      !type_is(_crc, struct bch_extent_crc128 *) &&      \
 203                      !type_is(_crc, union bch_extent_crc *));           \
 204                                                                         \
 205           type_is(_crc, struct bch_extent_crc32 *)  ? BCH_EXTENT_CRC32  \
 206         : type_is(_crc, struct bch_extent_crc64 *)  ? BCH_EXTENT_CRC64  \
 207         : type_is(_crc, struct bch_extent_crc128 *) ? BCH_EXTENT_CRC128 \
 208         : __extent_crc_type((union bch_extent_crc *) _crc);             \
 209 })
 210
 211 #define extent_entry_next(_entry)                                       \
 212         ((typeof(_entry)) ((void *) (_entry) + extent_entry_bytes(_entry)))
 213
 214 #define extent_entry_last(_e)                                           \
 215         vstruct_idx((_e).v, bkey_val_u64s((_e).k))
 216
 217 /* Iterate over all entries: */
 218
 219 #define extent_for_each_entry_from(_e, _entry, _start)                  \
 220         for ((_entry) = _start;                                         \
 221              (_entry) < extent_entry_last(_e);                          \
 222              (_entry) = extent_entry_next(_entry))
 223
 224 #define extent_for_each_entry(_e, _entry)                               \
 225         extent_for_each_entry_from(_e, _entry, (_e).v->start)
 226
 227 /* Iterate over crcs only: */
 228
 229 #define extent_crc_next(_e, _p)                                         \
 230 ({                                                                      \
 231         typeof(&(_e).v->start[0]) _entry = _p;                          \
 232                                                                         \
 233         while ((_entry) < extent_entry_last(_e) &&                      \
 234                !extent_entry_is_crc(_entry))                            \
 235                 (_entry) = extent_entry_next(_entry);                   \
 236                                                                         \
 237         entry_to_crc(_entry < extent_entry_last(_e) ? _entry : NULL);   \
 238 })
 239
 240 #define extent_for_each_crc(_e, _crc)                                   \
 241         for ((_crc) = extent_crc_next(_e, (_e).v->start);               \
 242              (_crc);                                                    \
 243              (_crc) = extent_crc_next(_e, extent_entry_next(to_entry(_crc))))
 244
 245 /* Iterate over pointers, with crcs: */
 246
 247 #define extent_ptr_crc_next_filter(_e, _crc, _ptr, _filter)             \
 248 ({                                                                      \
 249         __label__ out;                                                  \
 250         typeof(&(_e).v->start[0]) _entry;                               \
 251                                                                         \
 252         extent_for_each_entry_from(_e, _entry, to_entry(_ptr))          \
 253                 if (extent_entry_is_crc(_entry)) {                      \
 254                         (_crc) = entry_to_crc(_entry);                  \
 255                 } else {                                                \
 256                         _ptr = entry_to_ptr(_entry);                    \
 257                         if (_filter)                                    \
 258                                 goto out;                               \
 259                 }                                                       \
 260                                                                         \
 261         _ptr = NULL;                                                    \
 262 out:                                                                    \
 263         _ptr;                                                           \
 264 })
 265
 266 #define extent_for_each_ptr_crc_filter(_e, _ptr, _crc, _filter)         \
 267         for ((_crc) = NULL,                                             \
 268              (_ptr) = &(_e).v->start->ptr;                              \
 269              ((_ptr) = extent_ptr_crc_next_filter(_e, _crc, _ptr, _filter));\
 270              (_ptr)++)
 271
 272 #define extent_for_each_ptr_crc(_e, _ptr, _crc)                         \
 273         extent_for_each_ptr_crc_filter(_e, _ptr, _crc, true)
 274
 275 /* Iterate over pointers only, and from a given position: */
 276
 277 #define extent_ptr_next_filter(_e, _ptr, _filter)                       \
 278 ({                                                                      \
 279         typeof(__entry_to_crc(&(_e).v->start[0])) _crc;                 \
 280                                                                         \
 281         extent_ptr_crc_next_filter(_e, _crc, _ptr, _filter);            \
 282 })
 283
 284 #define extent_ptr_next(_e, _ptr)                                       \
 285         extent_ptr_next_filter(_e, _ptr, true)
 286
 287 #define extent_for_each_ptr_filter(_e, _ptr, _filter)                   \
 288         for ((_ptr) = &(_e).v->start->ptr;                              \
 289              ((_ptr) = extent_ptr_next_filter(_e, _ptr, _filter));      \
 290              (_ptr)++)
 291
 292 #define extent_for_each_ptr(_e, _ptr)                                   \
 293         extent_for_each_ptr_filter(_e, _ptr, true)
 294
 295 #define extent_ptr_prev(_e, _ptr)                                       \
 296 ({                                                                      \
 297         typeof(&(_e).v->start->ptr) _p;                                 \
 298         typeof(&(_e).v->start->ptr) _prev = NULL;                       \
 299                                                                         \
 300         extent_for_each_ptr(_e, _p) {                                   \
 301                 if (_p == (_ptr))                                       \
 302                         break;                                          \
 303                 _prev = _p;                                             \
 304         }                                                               \
 305                                                                         \
 306         _prev;                                                          \
 307 })
 308
 309 /*
 310  * Use this when you'll be dropping pointers as you iterate. Quadratic,
 311  * unfortunately:
 312  */
 313 #define extent_for_each_ptr_backwards(_e, _ptr)                         \
 314         for ((_ptr) = extent_ptr_prev(_e, NULL);                        \
 315              (_ptr);                                                    \
 316              (_ptr) = extent_ptr_prev(_e, _ptr))
 317
 318 void bch2_extent_crc_append(struct bkey_i_extent *, unsigned, unsigned,
 319                            unsigned, unsigned, struct bch_csum, unsigned);
 320
 321 static inline void __extent_entry_push(struct bkey_i_extent *e)
 322 {
 323         union bch_extent_entry *entry = extent_entry_last(extent_i_to_s(e));
 324
 325         EBUG_ON(bkey_val_u64s(&e->k) + extent_entry_u64s(entry) >
 326                 BKEY_EXTENT_VAL_U64s_MAX);
 327
 328         e->k.u64s += extent_entry_u64s(entry);
 329 }
 330
 331 static inline void extent_ptr_append(struct bkey_i_extent *e,
 332                                      struct bch_extent_ptr ptr)
 333 {
 334         ptr.type = 1 << BCH_EXTENT_ENTRY_ptr;
 335         extent_entry_last(extent_i_to_s(e))->ptr = ptr;
 336         __extent_entry_push(e);
 337 }
 338
 339 static inline struct bch_extent_crc128 crc_to_128(const struct bkey *k,
 340                                                   const union bch_extent_crc *crc)
 341 {
 342         EBUG_ON(!k->size);
 343
 344         switch (extent_crc_type(crc)) {
 345         case BCH_EXTENT_CRC_NONE:
 346                 return (struct bch_extent_crc128) {
 347                         ._compressed_size       = k->size - 1,
 348                         ._uncompressed_size     = k->size - 1,
 349                 };
 350         case BCH_EXTENT_CRC32:
 351                 return (struct bch_extent_crc128) {
 352                         .type                   = 1 << BCH_EXTENT_ENTRY_crc128,
 353                         ._compressed_size       = crc->crc32._compressed_size,
 354                         ._uncompressed_size     = crc->crc32._uncompressed_size,
 355                         .offset                 = crc->crc32.offset,
 356                         .csum_type              = crc->crc32.csum_type,
 357                         .compression_type       = crc->crc32.compression_type,
 358                         .csum.lo                = crc->crc32.csum,
 359                 };
 360         case BCH_EXTENT_CRC64:
 361                 return (struct bch_extent_crc128) {
 362                         .type                   = 1 << BCH_EXTENT_ENTRY_crc128,
 363                         ._compressed_size       = crc->crc64._compressed_size,
 364                         ._uncompressed_size     = crc->crc64._uncompressed_size,
 365                         .offset                 = crc->crc64.offset,
 366                         .nonce                  = crc->crc64.nonce,
 367                         .csum_type              = crc->crc64.csum_type,
 368                         .compression_type       = crc->crc64.compression_type,
 369                         .csum.lo                = crc->crc64.csum_lo,
 370                         .csum.hi                = crc->crc64.csum_hi,
 371                 };
 372         case BCH_EXTENT_CRC128:
 373                 return crc->crc128;
 374         default:
 375                 BUG();
 376         }
 377 }
 378
 379 #define crc_compressed_size(_k, _crc)                                   \
 380 ({                                                                      \
 381         unsigned _size = 0;                                             \
 382                                                                         \
 383         switch (extent_crc_type(_crc)) {                                \
 384         case BCH_EXTENT_CRC_NONE:                                       \
 385                 _size = ((const struct bkey *) (_k))->size;             \
 386                 break;                                                  \
 387         case BCH_EXTENT_CRC32:                                          \
 388                 _size = ((struct bch_extent_crc32 *) _crc)              \
 389                         ->_compressed_size + 1;                         \
 390                 break;                                                  \
 391         case BCH_EXTENT_CRC64:                                          \
 392                 _size = ((struct bch_extent_crc64 *) _crc)              \
 393                         ->_compressed_size + 1;                         \
 394                 break;                                                  \
 395         case BCH_EXTENT_CRC128:                                         \
 396                 _size = ((struct bch_extent_crc128 *) _crc)             \
 397                         ->_compressed_size + 1;                         \
 398                 break;                                                  \
 399         }                                                               \
 400         _size;                                                          \
 401 })
 402
 403 #define crc_uncompressed_size(_k, _crc)                                 \
 404 ({                                                                      \
 405         unsigned _size = 0;                                             \
 406                                                                         \
 407         switch (extent_crc_type(_crc)) {                                \
 408         case BCH_EXTENT_CRC_NONE:                                       \
 409                 _size = ((const struct bkey *) (_k))->size;             \
 410                 break;                                                  \
 411         case BCH_EXTENT_CRC32:                                          \
 412                 _size = ((struct bch_extent_crc32 *) _crc)              \
 413                         ->_uncompressed_size + 1;                       \
 414                 break;                                                  \
 415         case BCH_EXTENT_CRC64:                                          \
 416                 _size = ((struct bch_extent_crc64 *) _crc)              \
 417                         ->_uncompressed_size + 1;                       \
 418                 break;                                                  \
 419         case BCH_EXTENT_CRC128:                                         \
 420                 _size = ((struct bch_extent_crc128 *) _crc)             \
 421                         ->_uncompressed_size + 1;                       \
 422                 break;                                                  \
 423         }                                                               \
 424         _size;                                                          \
 425 })
 426
 427 static inline unsigned crc_offset(const union bch_extent_crc *crc)
 428 {
 429         switch (extent_crc_type(crc)) {
 430         case BCH_EXTENT_CRC_NONE:
 431                 return 0;
 432         case BCH_EXTENT_CRC32:
 433                 return crc->crc32.offset;
 434         case BCH_EXTENT_CRC64:
 435                 return crc->crc64.offset;
 436         case BCH_EXTENT_CRC128:
 437                 return crc->crc128.offset;
 438         default:
 439                 BUG();
 440         }
 441 }
 442
 443 static inline unsigned crc_nonce(const union bch_extent_crc *crc)
 444 {
 445         switch (extent_crc_type(crc)) {
 446         case BCH_EXTENT_CRC_NONE:
 447         case BCH_EXTENT_CRC32:
 448                 return 0;
 449         case BCH_EXTENT_CRC64:
 450                 return crc->crc64.nonce;
 451         case BCH_EXTENT_CRC128:
 452                 return crc->crc128.nonce;
 453         default:
 454                 BUG();
 455         }
 456 }
 457
 458 static inline unsigned crc_csum_type(const union bch_extent_crc *crc)
 459 {
 460         switch (extent_crc_type(crc)) {
 461         case BCH_EXTENT_CRC_NONE:
 462                 return 0;
 463         case BCH_EXTENT_CRC32:
 464                 return crc->crc32.csum_type;
 465         case BCH_EXTENT_CRC64:
 466                 return crc->crc64.csum_type;
 467         case BCH_EXTENT_CRC128:
 468                 return crc->crc128.csum_type;
 469         default:
 470                 BUG();
 471         }
 472 }
 473
 474 static inline unsigned crc_compression_type(const union bch_extent_crc *crc)
 475 {
 476         switch (extent_crc_type(crc)) {
 477         case BCH_EXTENT_CRC_NONE:
 478                 return 0;
 479         case BCH_EXTENT_CRC32:
 480                 return crc->crc32.compression_type;
 481         case BCH_EXTENT_CRC64:
 482                 return crc->crc64.compression_type;
 483         case BCH_EXTENT_CRC128:
 484                 return crc->crc128.compression_type;
 485         default:
 486                 BUG();
 487         }
 488 }
 489
 490 static inline struct bch_csum crc_csum(const union bch_extent_crc *crc)
 491 {
 492         switch (extent_crc_type(crc)) {
 493         case BCH_EXTENT_CRC_NONE:
 494                 return (struct bch_csum) { 0 };
 495         case BCH_EXTENT_CRC32:
 496                 return (struct bch_csum) { .lo = crc->crc32.csum };
 497         case BCH_EXTENT_CRC64:
 498                 return (struct bch_csum) {
 499                         .lo = crc->crc64.csum_lo,
 500                         .hi = crc->crc64.csum_hi,
 501                 };
 502         case BCH_EXTENT_CRC128:
 503                 return crc->crc128.csum;
 504         default:
 505                 BUG();
 506         }
 507 }
 508
 509 static inline unsigned bkey_extent_is_compressed(struct bkey_s_c k)
 510 {
 511         struct bkey_s_c_extent e;
 512         const struct bch_extent_ptr *ptr;
 513         const union bch_extent_crc *crc;
 514         unsigned ret = 0;
 515
 516         switch (k.k->type) {
 517         case BCH_EXTENT:
 518         case BCH_EXTENT_CACHED:
 519                 e = bkey_s_c_to_extent(k);
 520
 521                 extent_for_each_ptr_crc(e, ptr, crc)
 522                         if (!ptr->cached &&
 523                             crc_compression_type(crc) != BCH_COMPRESSION_NONE &&
 524                             crc_compressed_size(e.k, crc) < k.k->size)
 525                                 ret = max_t(unsigned, ret,
 526                                             crc_compressed_size(e.k, crc));
 527         }
 528
 529         return ret;
 530 }
 531
 532 static inline unsigned extent_current_nonce(struct bkey_s_c_extent e)
 533 {
 534         const union bch_extent_crc *crc;
 535
 536         extent_for_each_crc(e, crc)
 537                 if (bch2_csum_type_is_encryption(crc_csum_type(crc)))
 538                         return crc_offset(crc) + crc_nonce(crc);
 539
 540         return 0;
 541 }
 542
 543 void bch2_extent_narrow_crcs(struct bkey_s_extent);
 544 void bch2_extent_drop_redundant_crcs(struct bkey_s_extent);
 545
 546 void __bch2_extent_drop_ptr(struct bkey_s_extent, struct bch_extent_ptr *);
 547 void bch2_extent_drop_ptr(struct bkey_s_extent, struct bch_extent_ptr *);
 548 void bch2_extent_drop_ptr_idx(struct bkey_s_extent, unsigned);
 549
 550 const struct bch_extent_ptr *
 551 bch2_extent_has_device(struct bkey_s_c_extent, unsigned);
 552 struct bch_extent_ptr *
 553 bch2_extent_find_ptr(struct bch_fs *, struct bkey_s_extent,
 554                      struct bch_extent_ptr);
 555 struct bch_extent_ptr *
 556 bch2_extent_find_matching_ptr(struct bch_fs *, struct bkey_s_extent,
 557                               struct bkey_s_c_extent);
 558
 559 bool bch2_cut_front(struct bpos, struct bkey_i *);
 560 bool bch2_cut_back(struct bpos, struct bkey *);
 561 void bch2_key_resize(struct bkey *, unsigned);
 562
 563 #endif /* _BCACHEFS_EXTENTS_H */