diff options
| -rw-r--r-- | fs/bcachefs/alloc.c | 86 | ||||
| -rw-r--r-- | fs/bcachefs/btree_update_leaf.c | 13 | ||||
| -rw-r--r-- | fs/bcachefs/util.h | 15 |
3 files changed, 74 insertions, 40 deletions
diff --git a/fs/bcachefs/alloc.c b/fs/bcachefs/alloc.c index c195ffbdf3b3..003826d5c8ca 100644 --- a/fs/bcachefs/alloc.c +++ b/fs/bcachefs/alloc.c @@ -1201,43 +1201,75 @@ out: return ob - c->open_buckets; } -struct dev_alloc_list bch2_wp_alloc_list(struct bch_fs *c, - struct write_point *wp, - struct bch_devs_mask *devs) +static int __dev_alloc_cmp(struct bch_fs *c, + struct write_point *wp, + unsigned l, unsigned r) { - struct dev_alloc_list ret = { .nr = 0 }; - struct bch_dev *ca, *ca2; - unsigned i, j; + struct bch_dev *ca_l = rcu_dereference(c->devs[l]); + struct bch_dev *ca_r = rcu_dereference(c->devs[r]); - for_each_member_device_rcu(ca, c, i, devs) { - for (j = 0; j < ret.nr; j++) { - unsigned idx = ret.devs[j]; + if (ca_l && ca_r && ca_l->mi.tier != ca_r->mi.tier) + return ((ca_l->mi.tier > ca_r->mi.tier) - + (ca_l->mi.tier < ca_r->mi.tier)); - ca2 = rcu_dereference(c->devs[idx]); - if (!ca2) - break; + return ((wp->next_alloc[l] > wp->next_alloc[r]) - + (wp->next_alloc[l] < wp->next_alloc[r])); +} - if (ca->mi.tier < ca2->mi.tier) - break; +#define dev_alloc_cmp(l, r) __dev_alloc_cmp(c, wp, l, r) - if (ca->mi.tier == ca2->mi.tier && - wp->next_alloc[i] < wp->next_alloc[idx]) - break; - } +struct dev_alloc_list bch2_wp_alloc_list(struct bch_fs *c, + struct write_point *wp, + struct bch_devs_mask *devs) +{ + struct dev_alloc_list ret = { .nr = 0 }; + struct bch_dev *ca; + unsigned i; - array_insert_item(ret.devs, ret.nr, j, i); - } + for_each_member_device_rcu(ca, c, i, devs) + ret.devs[ret.nr++] = i; + bubble_sort(ret.devs, ret.nr, dev_alloc_cmp); return ret; } void bch2_wp_rescale(struct bch_fs *c, struct bch_dev *ca, struct write_point *wp) { - unsigned i; + u64 *v = wp->next_alloc + ca->dev_idx; + u64 free_space = dev_buckets_free(c, ca); + u64 free_space_inv = free_space + ? div64_u64(1ULL << 48, free_space) + : 1ULL << 48; + + pr_info("allocated %u next_alloc %12llu inv %llu", + ca->dev_idx, *v, free_space_inv); + + if (*v + free_space_inv >= *v) + *v += free_space_inv; + else + *v = U64_MAX; + + pr_info(" next_alloc %12llu", *v); + + for (v = wp->next_alloc; + v < wp->next_alloc + ARRAY_SIZE(wp->next_alloc); v++) { +#if 1 + + const unsigned shift = 16; + + *v = ((64 - fls64(*v) >= shift + ? *v << shift + : U64_MAX) - *v) >> shift; +#else + *v >>= 1; +#endif + } - for (i = 0; i < ARRAY_SIZE(wp->next_alloc); i++) - wp->next_alloc[i] >>= 1; + pr_info("devs: %llu %llu %llu", + wp->next_alloc[0], + wp->next_alloc[1], + wp->next_alloc[2]); } static enum bucket_alloc_ret __bch2_bucket_alloc_set(struct bch_fs *c, @@ -1249,7 +1281,6 @@ static enum bucket_alloc_ret __bch2_bucket_alloc_set(struct bch_fs *c, { enum bucket_alloc_ret ret = NO_DEVICES; struct dev_alloc_list devs_sorted; - u64 buckets_free; unsigned i; BUG_ON(nr_replicas > ARRAY_SIZE(wp->ptrs)); @@ -1281,13 +1312,6 @@ static enum bucket_alloc_ret __bch2_bucket_alloc_set(struct bch_fs *c, BUG_ON(wp->nr_ptrs >= ARRAY_SIZE(wp->ptrs)); wp->ptrs[wp->nr_ptrs++] = c->open_buckets + ob; - buckets_free = U64_MAX, dev_buckets_free(c, ca); - if (buckets_free) - wp->next_alloc[ca->dev_idx] += - div64_u64(U64_MAX, buckets_free * - ca->mi.bucket_size); - else - wp->next_alloc[ca->dev_idx] = U64_MAX; bch2_wp_rescale(c, ca, wp); __clear_bit(ca->dev_idx, devs->d); diff --git a/fs/bcachefs/btree_update_leaf.c b/fs/bcachefs/btree_update_leaf.c index 4b252b6d5e01..007aa5ef4091 100644 --- a/fs/bcachefs/btree_update_leaf.c +++ b/fs/bcachefs/btree_update_leaf.c @@ -272,15 +272,10 @@ static void multi_unlock_write(struct btree_insert *trans) bch2_btree_node_unlock_write(i->iter->l[0].b, i->iter); } -static inline void btree_trans_sort(struct btree_insert *trans) +static inline int btree_trans_cmp(struct btree_insert_entry l, + struct btree_insert_entry r) { - int i, end = trans->nr; - - while (--end > 0) - for (i = 0; i < end; i++) - if (btree_iter_cmp(trans->entries[i].iter, - trans->entries[i + 1].iter) > 0) - swap(trans->entries[i], trans->entries[i + 1]); + return btree_iter_cmp(l.iter, r.iter); } /* Normal update interface: */ @@ -313,7 +308,7 @@ int __bch2_btree_insert_at(struct btree_insert *trans) bkey_i_to_s_c(i->k))); } - btree_trans_sort(trans); + bubble_sort(trans->entries, trans->nr, btree_trans_cmp); if (unlikely(!percpu_ref_tryget(&c->writes))) return -EROFS; diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h index 6e97e83184e1..9aadb7371ffb 100644 --- a/fs/bcachefs/util.h +++ b/fs/bcachefs/util.h @@ -817,4 +817,19 @@ do { \ #define array_remove_item(_array, _nr, _pos) \ array_remove_items(_array, _nr, _pos, 1) +#define bubble_sort(_base, _nr, _cmp) \ +do { \ + unsigned _i, _end; \ + bool _swapped = true; \ + \ + for (_end = (_nr) - 1; _end && _swapped; --_end) { \ + _swapped = false; \ + for (_i = 0; _i < _end; _i++) \ + if (_cmp((_base)[_i], (_base)[_i + 1]) > 0) { \ + swap((_base)[_i], (_base)[_i + 1]); \ + _swapped = true; \ + } \ + } \ +} while (0) + #endif /* _BCACHEFS_UTIL_H */ |