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