allocator striping wipalloc_striping

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 */