git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/bkey_sort.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include "bcachefs.h"
   3 #include "bkey_on_stack.h"
   4 #include "bkey_sort.h"
   5 #include "bset.h"
   6 #include "extents.h"
   7
   8 typedef int (*sort_cmp_fn)(struct btree *,
   9                            struct bkey_packed *,
  10                            struct bkey_packed *);
  11
  12 static inline bool sort_iter_end(struct sort_iter *iter)
  13 {
  14         return !iter->used;
  15 }
  16
  17 static inline void __sort_iter_sift(struct sort_iter *iter,
  18                                     unsigned from,
  19                                     sort_cmp_fn cmp)
  20 {
  21         unsigned i;
  22
  23         for (i = from;
  24              i + 1 < iter->used &&
  25              cmp(iter->b, iter->data[i].k, iter->data[i + 1].k) > 0;
  26              i++)
  27                 swap(iter->data[i], iter->data[i + 1]);
  28 }
  29
  30 static inline void sort_iter_sift(struct sort_iter *iter, sort_cmp_fn cmp)
  31 {
  32
  33         __sort_iter_sift(iter, 0, cmp);
  34 }
  35
  36 static inline void sort_iter_sort(struct sort_iter *iter, sort_cmp_fn cmp)
  37 {
  38         unsigned i = iter->used;
  39
  40         while (i--)
  41                 __sort_iter_sift(iter, i, cmp);
  42 }
  43
  44 static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter)
  45 {
  46         return !sort_iter_end(iter) ? iter->data->k : NULL;
  47 }
  48
  49 static inline void __sort_iter_advance(struct sort_iter *iter,
  50                                        unsigned idx, sort_cmp_fn cmp)
  51 {
  52         struct sort_iter_set *i = iter->data + idx;
  53
  54         BUG_ON(idx >= iter->used);
  55
  56         i->k = bkey_next_skip_noops(i->k, i->end);
  57
  58         BUG_ON(i->k > i->end);
  59
  60         if (i->k == i->end)
  61                 array_remove_item(iter->data, iter->used, idx);
  62         else
  63                 __sort_iter_sift(iter, idx, cmp);
  64 }
  65
  66 static inline void sort_iter_advance(struct sort_iter *iter, sort_cmp_fn cmp)
  67 {
  68         __sort_iter_advance(iter, 0, cmp);
  69 }
  70
  71 static inline struct bkey_packed *sort_iter_next(struct sort_iter *iter,
  72                                                  sort_cmp_fn cmp)
  73 {
  74         struct bkey_packed *ret = sort_iter_peek(iter);
  75
  76         if (ret)
  77                 sort_iter_advance(iter, cmp);
  78
  79         return ret;
  80 }
  81
  82 /*
  83  * If keys compare equal, compare by pointer order:
  84  */
  85 static inline int key_sort_fix_overlapping_cmp(struct btree *b,
  86                                                struct bkey_packed *l,
  87                                                struct bkey_packed *r)
  88 {
  89         return bkey_cmp_packed(b, l, r) ?:
  90                 cmp_int((unsigned long) l, (unsigned long) r);
  91 }
  92
  93 static inline bool should_drop_next_key(struct sort_iter *iter)
  94 {
  95         /*
  96          * key_sort_cmp() ensures that when keys compare equal the older key
  97          * comes first; so if l->k compares equal to r->k then l->k is older
  98          * and should be dropped.
  99          */
 100         return iter->used >= 2 &&
 101                 !bkey_cmp_packed(iter->b,
 102                                  iter->data[0].k,
 103                                  iter->data[1].k);
 104 }
 105
 106 struct btree_nr_keys
 107 bch2_key_sort_fix_overlapping(struct bch_fs *c, struct bset *dst,
 108                               struct sort_iter *iter)
 109 {
 110         struct bkey_packed *out = dst->start;
 111         struct bkey_packed *k;
 112         struct btree_nr_keys nr;
 113
 114         memset(&nr, 0, sizeof(nr));
 115
 116         sort_iter_sort(iter, key_sort_fix_overlapping_cmp);
 117
 118         while ((k = sort_iter_peek(iter))) {
 119                 if (!bkey_whiteout(k) &&
 120                     !should_drop_next_key(iter)) {
 121                         bkey_copy(out, k);
 122                         btree_keys_account_key_add(&nr, 0, out);
 123                         out = bkey_next(out);
 124                 }
 125
 126                 sort_iter_advance(iter, key_sort_fix_overlapping_cmp);
 127         }
 128
 129         dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
 130         return nr;
 131 }
 132
 133 static void extent_sort_advance_prev(struct bkey_format *f,
 134                                      struct btree_nr_keys *nr,
 135                                      struct bkey_packed *start,
 136                                      struct bkey_packed **prev)
 137 {
 138         if (*prev) {
 139                 bch2_bkey_pack(*prev, (void *) *prev, f);
 140
 141                 btree_keys_account_key_add(nr, 0, *prev);
 142                 *prev = bkey_next(*prev);
 143         } else {
 144                 *prev = start;
 145         }
 146 }
 147
 148 static void extent_sort_append(struct bch_fs *c,
 149                                struct bkey_format *f,
 150                                struct btree_nr_keys *nr,
 151                                struct bkey_packed *start,
 152                                struct bkey_packed **prev,
 153                                struct bkey_s k)
 154 {
 155         if (bkey_whiteout(k.k))
 156                 return;
 157
 158         /*
 159          * prev is always unpacked, for key merging - until right before we
 160          * advance it:
 161          */
 162
 163         if (*prev &&
 164             bch2_bkey_merge(c, bkey_i_to_s((void *) *prev), k) ==
 165             BCH_MERGE_MERGE)
 166                 return;
 167
 168         extent_sort_advance_prev(f, nr, start, prev);
 169
 170         bkey_reassemble((void *) *prev, k.s_c);
 171 }
 172
 173 /* Sort + repack in a new format: */
 174 struct btree_nr_keys
 175 bch2_sort_repack(struct bset *dst, struct btree *src,
 176                  struct btree_node_iter *src_iter,
 177                  struct bkey_format *out_f,
 178                  bool filter_whiteouts)
 179 {
 180         struct bkey_format *in_f = &src->format;
 181         struct bkey_packed *in, *out = vstruct_last(dst);
 182         struct btree_nr_keys nr;
 183
 184         memset(&nr, 0, sizeof(nr));
 185
 186         while ((in = bch2_btree_node_iter_next_all(src_iter, src))) {
 187                 if (filter_whiteouts && bkey_whiteout(in))
 188                         continue;
 189
 190                 if (bch2_bkey_transform(out_f, out, bkey_packed(in)
 191                                        ? in_f : &bch2_bkey_format_current, in))
 192                         out->format = KEY_FORMAT_LOCAL_BTREE;
 193                 else
 194                         bch2_bkey_unpack(src, (void *) out, in);
 195
 196                 btree_keys_account_key_add(&nr, 0, out);
 197                 out = bkey_next(out);
 198         }
 199
 200         dst->u64s = cpu_to_le16((u64 *) out - dst->_data);
 201         return nr;
 202 }
 203
 204 /* Sort, repack, and merge: */
 205 struct btree_nr_keys
 206 bch2_sort_repack_merge(struct bch_fs *c,
 207                        struct bset *dst, struct btree *src,
 208                        struct btree_node_iter *iter,
 209                        struct bkey_format *out_f,
 210                        bool filter_whiteouts)
 211 {
 212         struct bkey_packed *prev = NULL, *k_packed;
 213         struct bkey_on_stack k;
 214         struct btree_nr_keys nr;
 215
 216         memset(&nr, 0, sizeof(nr));
 217         bkey_on_stack_init(&k);
 218
 219         while ((k_packed = bch2_btree_node_iter_next_all(iter, src))) {
 220                 if (filter_whiteouts && bkey_whiteout(k_packed))
 221                         continue;
 222
 223                 /*
 224                  * NOTE:
 225                  * bch2_bkey_normalize may modify the key we pass it (dropping
 226                  * stale pointers) and we don't have a write lock on the src
 227                  * node; we have to make a copy of the entire key before calling
 228                  * normalize
 229                  */
 230                 bkey_on_stack_realloc(&k, c, k_packed->u64s + BKEY_U64s);
 231                 bch2_bkey_unpack(src, k.k, k_packed);
 232
 233                 if (filter_whiteouts &&
 234                     bch2_bkey_normalize(c, bkey_i_to_s(k.k)))
 235                         continue;
 236
 237                 extent_sort_append(c, out_f, &nr, vstruct_last(dst),
 238                                    &prev, bkey_i_to_s(k.k));
 239         }
 240
 241         extent_sort_advance_prev(out_f, &nr, vstruct_last(dst), &prev);
 242
 243         dst->u64s = cpu_to_le16((u64 *) prev - dst->_data);
 244         bkey_on_stack_exit(&k, c);
 245         return nr;
 246 }
 247
 248 static inline int sort_keys_cmp(struct btree *b,
 249                                 struct bkey_packed *l,
 250                                 struct bkey_packed *r)
 251 {
 252         return bkey_cmp_packed(b, l, r) ?:
 253                 (int) bkey_deleted(r) - (int) bkey_deleted(l) ?:
 254                 (int) l->needs_whiteout - (int) r->needs_whiteout;
 255 }
 256
 257 unsigned bch2_sort_keys(struct bkey_packed *dst,
 258                         struct sort_iter *iter,
 259                         bool filter_whiteouts)
 260 {
 261         const struct bkey_format *f = &iter->b->format;
 262         struct bkey_packed *in, *next, *out = dst;
 263
 264         sort_iter_sort(iter, sort_keys_cmp);
 265
 266         while ((in = sort_iter_next(iter, sort_keys_cmp))) {
 267                 bool needs_whiteout = false;
 268
 269                 if (bkey_whiteout(in) &&
 270                     (filter_whiteouts || !in->needs_whiteout))
 271                         continue;
 272
 273                 while ((next = sort_iter_peek(iter)) &&
 274                        !bkey_cmp_packed(iter->b, in, next)) {
 275                         BUG_ON(in->needs_whiteout &&
 276                                next->needs_whiteout);
 277                         needs_whiteout |= in->needs_whiteout;
 278                         in = sort_iter_next(iter, sort_keys_cmp);
 279                 }
 280
 281                 if (bkey_whiteout(in)) {
 282                         memcpy_u64s(out, in, bkeyp_key_u64s(f, in));
 283                         set_bkeyp_val_u64s(f, out, 0);
 284                 } else {
 285                         bkey_copy(out, in);
 286                 }
 287                 out->needs_whiteout |= needs_whiteout;
 288                 out = bkey_next(out);
 289         }
 290
 291         return (u64 *) out - (u64 *) dst;
 292 }
 293
 294 /* Compat code for btree_node_old_extent_overwrite: */
 295
 296 /*
 297  * If keys compare equal, compare by pointer order:
 298  *
 299  * Necessary for sort_fix_overlapping() - if there are multiple keys that
 300  * compare equal in different sets, we have to process them newest to oldest.
 301  */
 302 static inline int extent_sort_fix_overlapping_cmp(struct btree *b,
 303                                                   struct bkey_packed *l,
 304                                                   struct bkey_packed *r)
 305 {
 306         struct bkey ul = bkey_unpack_key(b, l);
 307         struct bkey ur = bkey_unpack_key(b, r);
 308
 309         return bkey_cmp(bkey_start_pos(&ul),
 310                         bkey_start_pos(&ur)) ?:
 311                 cmp_int((unsigned long) r, (unsigned long) l);
 312 }
 313
 314 struct btree_nr_keys
 315 bch2_extent_sort_fix_overlapping(struct bch_fs *c, struct bset *dst,
 316                                  struct sort_iter *iter)
 317 {
 318         struct btree *b = iter->b;
 319         struct bkey_format *f = &b->format;
 320         struct sort_iter_set *_l = iter->data, *_r = iter->data + 1;
 321         struct bkey_packed *prev = NULL;
 322         struct bkey l_unpacked, r_unpacked;
 323         struct bkey_s l, r;
 324         struct btree_nr_keys nr;
 325         struct bkey_on_stack split;
 326
 327         memset(&nr, 0, sizeof(nr));
 328         bkey_on_stack_init(&split);
 329
 330         sort_iter_sort(iter, extent_sort_fix_overlapping_cmp);
 331
 332         while (!sort_iter_end(iter)) {
 333                 l = __bkey_disassemble(b, _l->k, &l_unpacked);
 334
 335                 if (iter->used == 1) {
 336                         extent_sort_append(c, f, &nr, dst->start, &prev, l);
 337                         sort_iter_advance(iter,
 338                                           extent_sort_fix_overlapping_cmp);
 339                         continue;
 340                 }
 341
 342                 r = __bkey_disassemble(b, _r->k, &r_unpacked);
 343
 344                 /* If current key and next key don't overlap, just append */
 345                 if (bkey_cmp(l.k->p, bkey_start_pos(r.k)) <= 0) {
 346                         extent_sort_append(c, f, &nr, dst->start, &prev, l);
 347                         sort_iter_advance(iter,
 348                                           extent_sort_fix_overlapping_cmp);
 349                         continue;
 350                 }
 351
 352                 /* Skip 0 size keys */
 353                 if (!r.k->size) {
 354                         __sort_iter_advance(iter, 1,
 355                                             extent_sort_fix_overlapping_cmp);
 356                         continue;
 357                 }
 358
 359                 /*
 360                  * overlap: keep the newer key and trim the older key so they
 361                  * don't overlap. comparing pointers tells us which one is
 362                  * newer, since the bsets are appended one after the other.
 363                  */
 364
 365                 /* can't happen because of comparison func */
 366                 BUG_ON(_l->k < _r->k &&
 367                        !bkey_cmp(bkey_start_pos(l.k), bkey_start_pos(r.k)));
 368
 369                 if (_l->k > _r->k) {
 370                         /* l wins, trim r */
 371                         if (bkey_cmp(l.k->p, r.k->p) >= 0) {
 372                                 __sort_iter_advance(iter, 1,
 373                                          extent_sort_fix_overlapping_cmp);
 374                         } else {
 375                                 bch2_cut_front_s(l.k->p, r);
 376                                 extent_save(b, _r->k, r.k);
 377                                 __sort_iter_sift(iter, 1,
 378                                          extent_sort_fix_overlapping_cmp);
 379                         }
 380                 } else if (bkey_cmp(l.k->p, r.k->p) > 0) {
 381
 382                         /*
 383                          * r wins, but it overlaps in the middle of l - split l:
 384                          */
 385                         bkey_on_stack_reassemble(&split, c, l.s_c);
 386                         bch2_cut_back(bkey_start_pos(r.k), split.k);
 387
 388                         bch2_cut_front_s(r.k->p, l);
 389                         extent_save(b, _l->k, l.k);
 390
 391                         __sort_iter_sift(iter, 0,
 392                                          extent_sort_fix_overlapping_cmp);
 393
 394                         extent_sort_append(c, f, &nr, dst->start,
 395                                            &prev, bkey_i_to_s(split.k));
 396                 } else {
 397                         bch2_cut_back_s(bkey_start_pos(r.k), l);
 398                         extent_save(b, _l->k, l.k);
 399                 }
 400         }
 401
 402         extent_sort_advance_prev(f, &nr, dst->start, &prev);
 403
 404         dst->u64s = cpu_to_le16((u64 *) prev - dst->_data);
 405
 406         bkey_on_stack_exit(&split, c);
 407         return nr;
 408 }
 409
 410 static inline int sort_extents_cmp(struct btree *b,
 411                                    struct bkey_packed *l,
 412                                    struct bkey_packed *r)
 413 {
 414         return bkey_cmp_packed(b, l, r) ?:
 415                 (int) bkey_deleted(l) - (int) bkey_deleted(r);
 416 }
 417
 418 unsigned bch2_sort_extents(struct bkey_packed *dst,
 419                            struct sort_iter *iter,
 420                            bool filter_whiteouts)
 421 {
 422         struct bkey_packed *in, *out = dst;
 423
 424         sort_iter_sort(iter, sort_extents_cmp);
 425
 426         while ((in = sort_iter_next(iter, sort_extents_cmp))) {
 427                 if (bkey_deleted(in))
 428                         continue;
 429
 430                 if (bkey_whiteout(in) &&
 431                     (filter_whiteouts || !in->needs_whiteout))
 432                         continue;
 433
 434                 bkey_copy(out, in);
 435                 out = bkey_next(out);
 436         }
 437
 438         return (u64 *) out - (u64 *) dst;
 439 }
 440
 441 static inline int sort_extent_whiteouts_cmp(struct btree *b,
 442                                             struct bkey_packed *l,
 443                                             struct bkey_packed *r)
 444 {
 445         struct bkey ul = bkey_unpack_key(b, l);
 446         struct bkey ur = bkey_unpack_key(b, r);
 447
 448         return bkey_cmp(bkey_start_pos(&ul), bkey_start_pos(&ur));
 449 }
 450
 451 unsigned bch2_sort_extent_whiteouts(struct bkey_packed *dst,
 452                                     struct sort_iter *iter)
 453 {
 454         const struct bkey_format *f = &iter->b->format;
 455         struct bkey_packed *in, *out = dst;
 456         struct bkey_i l, r;
 457         bool prev = false, l_packed = false;
 458         u64 max_packed_size     = bkey_field_max(f, BKEY_FIELD_SIZE);
 459         u64 max_packed_offset   = bkey_field_max(f, BKEY_FIELD_OFFSET);
 460         u64 new_size;
 461
 462         max_packed_size = min_t(u64, max_packed_size, KEY_SIZE_MAX);
 463
 464         sort_iter_sort(iter, sort_extent_whiteouts_cmp);
 465
 466         while ((in = sort_iter_next(iter, sort_extent_whiteouts_cmp))) {
 467                 if (bkey_deleted(in))
 468                         continue;
 469
 470                 EBUG_ON(bkeyp_val_u64s(f, in));
 471                 EBUG_ON(in->type != KEY_TYPE_discard);
 472
 473                 r.k = bkey_unpack_key(iter->b, in);
 474
 475                 if (prev &&
 476                     bkey_cmp(l.k.p, bkey_start_pos(&r.k)) >= 0) {
 477                         if (bkey_cmp(l.k.p, r.k.p) >= 0)
 478                                 continue;
 479
 480                         new_size = l_packed
 481                                 ? min(max_packed_size, max_packed_offset -
 482                                       bkey_start_offset(&l.k))
 483                                 : KEY_SIZE_MAX;
 484
 485                         new_size = min(new_size, r.k.p.offset -
 486                                        bkey_start_offset(&l.k));
 487
 488                         BUG_ON(new_size < l.k.size);
 489
 490                         bch2_key_resize(&l.k, new_size);
 491
 492                         if (bkey_cmp(l.k.p, r.k.p) >= 0)
 493                                 continue;
 494
 495                         bch2_cut_front(l.k.p, &r);
 496                 }
 497
 498                 if (prev) {
 499                         if (!bch2_bkey_pack(out, &l, f)) {
 500                                 BUG_ON(l_packed);
 501                                 bkey_copy(out, &l);
 502                         }
 503                         out = bkey_next(out);
 504                 }
 505
 506                 l = r;
 507                 prev = true;
 508                 l_packed = bkey_packed(in);
 509         }
 510
 511         if (prev) {
 512                 if (!bch2_bkey_pack(out, &l, f)) {
 513                         BUG_ON(l_packed);
 514                         bkey_copy(out, &l);
 515                 }
 516                 out = bkey_next(out);
 517         }
 518
 519         return (u64 *) out - (u64 *) dst;
 520 }