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