bcache: Pointer compression for btree_node_iter

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>

4 files changed, 99 insertions, 50 deletions

diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index 00d34daf5199..f51d39f75559 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -650,21 +650,23 @@ static void verify_insert_pos(struct btree_keys *b,
  * @top must be in the last bset.
  */
 static void bch_btree_node_iter_fix(struct btree_node_iter *iter,
+				    struct btree_keys *b,
 				    const struct bkey_packed *where)
 {
 	struct btree_node_iter_set *set;
-	u64 n = where->u64s;
+	unsigned offset = __btree_node_key_to_offset(b, where);
+	unsigned shift = where->u64s;
 
 	BUG_ON(iter->used > MAX_BSETS);
 
 	for (set = iter->data;
 	     set < iter->data + iter->used;
 	     set++)
-		if (set->end >= where) {
-			set->end = (void *) ((u64 *) set->end + n);
+		if (set->end >= offset) {
+			set->end += shift;
 
-			if (set->k >= where)
-				set->k = (void *) ((u64 *) set->k + n);
+			if (set->k >= offset)
+				set->k += shift;
 			break;
 		}
 }
@@ -785,7 +787,7 @@ void bch_bset_insert(struct btree_keys *b,
 	struct bset_tree *t = bset_tree_last(b);
 	struct bset *i = t->data;
 	struct bkey_packed *prev = NULL;
-	struct bkey_packed *where = bch_btree_node_iter_bset_pos(iter, i) ?:
+	struct bkey_packed *where = bch_btree_node_iter_bset_pos(iter, b, i) ?:
 		bset_bkey_last(i);
 	struct bkey_packed packed, *src;
 	BKEY_PADDED(k) tmp;
@@ -868,7 +870,7 @@ void bch_bset_insert(struct btree_keys *b,
 		b->nr_live_u64s += src->u64s;
 
 	bch_bset_fix_lookup_table(b, t, where);
-	bch_btree_node_iter_fix(iter, where);
+	bch_btree_node_iter_fix(iter, b, where);
 
 	bch_btree_node_iter_verify(iter, b);
 }
@@ -1043,10 +1045,12 @@ static struct bkey_packed *bch_bset_search(struct btree_keys *b,
 
 static inline bool btree_node_iter_cmp(struct btree_node_iter *iter,
 				       struct btree_keys *b,
-				       struct btree_node_iter_set l,
-				       struct btree_node_iter_set r)
+				       struct btree_node_iter_set ls,
+				       struct btree_node_iter_set rs)
 {
-	s64 c = bkey_cmp_packed(&b->set->data->format, l.k, r.k);
+	struct bkey_packed *l = __btree_node_offset_to_key(b, ls.k);
+	struct bkey_packed *r = __btree_node_offset_to_key(b, rs.k);
+	s64 c = bkey_cmp_packed(&b->set->data->format, l, r);
 
 	/*
 	 * For non extents, when keys compare equal the deleted keys have to
@@ -1058,8 +1062,8 @@ static inline bool btree_node_iter_cmp(struct btree_node_iter *iter,
 	 */
 	return c ? c > 0
 		: iter->is_extents
-		? bkey_deleted(l.k) > bkey_deleted(r.k)
-		: bkey_deleted(l.k) < bkey_deleted(r.k);
+		? bkey_deleted(l) > bkey_deleted(r)
+		: bkey_deleted(l) < bkey_deleted(r);
 }
 
 void bch_btree_node_iter_push(struct btree_node_iter *iter,
@@ -1069,7 +1073,10 @@ void bch_btree_node_iter_push(struct btree_node_iter *iter,
 {
 	if (k != end) {
 		struct btree_node_iter_set n =
-			((struct btree_node_iter_set) { k, end });
+			((struct btree_node_iter_set) {
+				 __btree_node_key_to_offset(b, k),
+				 __btree_node_key_to_offset(b, end)
+			 });
 		unsigned i;
 
 		for (i = 0;
@@ -1126,8 +1133,10 @@ void bch_btree_node_iter_init_from_start(struct btree_node_iter *iter,
 EXPORT_SYMBOL(bch_btree_node_iter_init_from_start);
 
 struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *iter,
+						 struct btree_keys *b,
 						 struct bset *i)
 {
+	unsigned end = __btree_node_key_to_offset(b, bset_bkey_last(i));
 	struct btree_node_iter_set *set;
 
 	BUG_ON(iter->used > MAX_BSETS);
@@ -1135,8 +1144,8 @@ struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *iter,
 	for (set = iter->data;
 	     set < iter->data + iter->used;
 	     set++)
-		if (bset_bkey_last(i) == set->end)
-			return set->k;
+		if (end == set->end)
+			return __btree_node_offset_to_key(b, set->k);
 
 	return NULL;
 }
@@ -1177,7 +1186,7 @@ EXPORT_SYMBOL(bch_btree_node_iter_sort);
 void bch_btree_node_iter_advance(struct btree_node_iter *iter,
 				 struct btree_keys *b)
 {
-	iter->data->k = bkey_next(iter->data->k);
+	iter->data->k += __bch_btree_node_iter_peek_all(iter, b)->u64s;
 
 	BUG_ON(iter->data->k > iter->data->end);
 
@@ -1208,7 +1217,8 @@ void bch_btree_node_iter_verify(struct btree_node_iter *iter,
 		for (t =  b->set;
 		     t <= b->set + b->nsets;
 		     t++)
-			if (set->end == bset_bkey_last(t->data))
+			if (__btree_node_offset_to_key(b, set->end) ==
+			    bset_bkey_last(t->data))
 				goto next;
 		BUG();
 next:
@@ -1221,13 +1231,14 @@ static void bch_btree_node_iter_next_check(struct btree_node_iter *iter,
 					   struct bkey_packed *k)
 {
 	const struct bkey_format *f = &b->set->data->format;
+	const struct bkey_packed *n = bch_btree_node_iter_peek_all(iter, b);
 
 	bkey_unpack_key(f, k);
 
-	if (!bch_btree_node_iter_end(iter) &&
-	    keys_out_of_order(f, k, iter->data->k, iter->is_extents)) {
+	if (n &&
+	    keys_out_of_order(f, k, n, iter->is_extents)) {
 		struct bkey ku = bkey_unpack_key(f, k);
-		struct bkey nu = bkey_unpack_key(f, iter->data->k);
+		struct bkey nu = bkey_unpack_key(f, n);
 		char buf1[80], buf2[80];
 
 		bch_dump_bucket(b);
@@ -1240,7 +1251,7 @@ static void bch_btree_node_iter_next_check(struct btree_node_iter *iter,
 struct bkey_packed *bch_btree_node_iter_next_all(struct btree_node_iter *iter,
 						 struct btree_keys *b)
 {
-	struct bkey_packed *ret = bch_btree_node_iter_peek_all(iter);
+	struct bkey_packed *ret = bch_btree_node_iter_peek_all(iter, b);
 
 	if (ret) {
 		bch_btree_node_iter_advance(iter, b);
diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h
index f8e57b1fd223..b16e7a7964f7 100644
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@ -398,10 +398,10 @@ static inline enum bch_extent_overlap bch_extent_overlap(const struct bkey *k,
 
 struct btree_node_iter {
 	u8		is_extents;
-	unsigned	used:24;
+	u16		used;
 
 	struct btree_node_iter_set {
-		struct bkey_packed *k, *end;
+		u16	k, end;
 	} data[MAX_BSETS];
 };
 
@@ -412,6 +412,7 @@ void bch_btree_node_iter_init(struct btree_node_iter *, struct btree_keys *,
 void bch_btree_node_iter_init_from_start(struct btree_node_iter *,
 					 struct btree_keys *);
 struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *,
+						 struct btree_keys *,
 						 struct bset *);
 
 void bch_btree_node_iter_sort(struct btree_node_iter *, struct btree_keys *);
@@ -422,12 +423,35 @@ static inline bool bch_btree_node_iter_end(struct btree_node_iter *iter)
 	return !iter->used;
 }
 
+static inline u16
+__btree_node_key_to_offset(struct btree_keys *b, const struct bkey_packed *k)
+{
+	size_t ret = (u64 *) k - (u64 *) b->set->data;
+
+	EBUG_ON(ret > U16_MAX);
+	return ret;
+}
+
+static inline struct bkey_packed *
+__btree_node_offset_to_key(struct btree_keys *b, u16 k)
+{
+	return (void *) ((u64 *) b->set->data + k);
+}
+
+static inline struct bkey_packed *
+__bch_btree_node_iter_peek_all(struct btree_node_iter *iter,
+			       struct btree_keys *b)
+{
+	return __btree_node_offset_to_key(b, iter->data->k);
+}
+
 static inline struct bkey_packed *
-bch_btree_node_iter_peek_all(struct btree_node_iter *iter)
+bch_btree_node_iter_peek_all(struct btree_node_iter *iter,
+			     struct btree_keys *b)
 {
 	return bch_btree_node_iter_end(iter)
 		? NULL
-		: iter->data->k;
+		: __bch_btree_node_iter_peek_all(iter, b);
 }
 
 /* In debug mode, bch_btree_node_iter_next_all() does debug checks */
@@ -439,7 +463,7 @@ struct bkey_packed *bch_btree_node_iter_next_all(struct btree_node_iter *,
 static inline struct bkey_packed *
 bch_btree_node_iter_next_all(struct btree_node_iter *iter, struct btree_keys *b)
 {
-	struct bkey_packed *ret = bch_btree_node_iter_peek_all(iter);
+	struct bkey_packed *ret = bch_btree_node_iter_peek_all(iter, b);
 
 	if (ret)
 		bch_btree_node_iter_advance(iter, b);
@@ -465,7 +489,7 @@ bch_btree_node_iter_peek(struct btree_node_iter *iter, struct btree_keys *b)
 {
 	struct bkey_packed *ret;
 
-	while ((ret = bch_btree_node_iter_peek_all(iter)) &&
+	while ((ret = bch_btree_node_iter_peek_all(iter, b)) &&
 	       bkey_deleted(ret))
 		bch_btree_node_iter_next_all(iter, b);
 
@@ -481,7 +505,7 @@ bch_btree_node_iter_peek_overlapping(struct btree_node_iter *iter,
 	struct bkey_packed *ret;
 	struct bkey u;
 
-	while ((ret = bch_btree_node_iter_peek_all(iter)) &&
+	while ((ret = bch_btree_node_iter_peek_all(iter, b)) &&
 	       (bkey_cmp_left_packed(f, ret, bkey_start_pos(end)) <= 0))
 		bch_btree_node_iter_next_all(iter, b);
 
diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
index a8bed330dd77..bdb6ecfecb35 100644
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@ -2305,7 +2305,8 @@ static inline struct bkey_s_c __btree_iter_peek_all(struct btree_iter *iter)
 	const struct bkey_format *f =
 		&iter->nodes[iter->level]->keys.set->data->format;
 	struct bkey_packed *k =
-		bch_btree_node_iter_peek_all(&iter->node_iters[iter->level]);
+		bch_btree_node_iter_peek_all(&iter->node_iters[iter->level],
+					     &iter->nodes[iter->level]->keys);
 	struct bkey_s_c ret;
 
 	if (!k)
diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
index c2f6c3c5953b..ac3c8ab4d33f 100644
--- a/drivers/md/bcache/extents.c
+++ b/drivers/md/bcache/extents.c
@@ -26,9 +26,10 @@ static inline unsigned bkeyp_extent_ptrs(const struct bkey_format *f,
 }
 
 static void sort_key_next(struct btree_node_iter *iter,
+			  struct btree_keys *b,
 			  struct btree_node_iter_set *i)
 {
-	i->k = bkey_next(i->k);
+	i->k += __btree_node_offset_to_key(b, i->k)->u64s;
 
 	if (i->k == i->end)
 		*i = iter->data[--iter->used];
@@ -43,7 +44,9 @@ static void sort_key_next(struct btree_node_iter *iter,
  */
 #define key_sort_cmp(l, r)						\
 ({									\
-	int _c = bkey_cmp_packed(&b->set->data->format,	(l).k, (r).k);	\
+	int _c = bkey_cmp_packed(&b->set->data->format,			\
+				 __btree_node_offset_to_key(b, (l).k),	\
+				 __btree_node_offset_to_key(b, (r).k));	\
 									\
 	_c ? _c > 0 : (l).k > (r).k;					\
 })
@@ -54,7 +57,7 @@ static inline bool should_drop_next_key(struct btree_node_iter *iter,
 	const struct bkey_format *f = &b->set->data->format;
 	struct btree_node_iter_set *l = iter->data, *r = iter->data + 1;
 
-	if (bkey_deleted(l->k))
+	if (bkey_deleted(__btree_node_offset_to_key(b, l->k)))
 		return true;
 
 	if (iter->used < 2)
@@ -69,7 +72,9 @@ static inline bool should_drop_next_key(struct btree_node_iter *iter,
 	 * comes first; so if l->k compares equal to r->k then l->k is older and
 	 * should be dropped.
 	 */
-	return !bkey_cmp_packed(f, l->k, r->k);
+	return !bkey_cmp_packed(f,
+				__btree_node_offset_to_key(b, l->k),
+				__btree_node_offset_to_key(b, r->k));
 }
 
 void bch_key_sort_fix_overlapping(struct btree_keys *b,
@@ -82,13 +87,15 @@ void bch_key_sort_fix_overlapping(struct btree_keys *b,
 
 	while (!bch_btree_node_iter_end(iter)) {
 		if (!should_drop_next_key(iter, b)) {
+			struct bkey_packed *k =
+				__btree_node_offset_to_key(b, iter->data->k);
+
 			/* XXX: need better bkey_copy */
-			memcpy(out, iter->data->k,
-			       bkey_bytes(iter->data->k));
+			memcpy(out, k, bkey_bytes(k));
 			out = bkey_next(out);
 		}
 
-		sort_key_next(iter, iter->data);
+		sort_key_next(iter, b, iter->data);
 		heap_sift(iter, 0, key_sort_cmp);
 	}
 
@@ -111,7 +118,7 @@ bool bch_insert_fixup_key(struct btree *b, struct bkey_i *insert,
 
 	BUG_ON(replace);
 
-	while ((k = bch_btree_node_iter_peek_all(iter)) &&
+	while ((k = bch_btree_node_iter_peek_all(iter, &b->keys)) &&
 	       (c = bkey_cmp_packed(f, k, &insert->k)) <= 0) {
 		if (!c && !bkey_deleted(k)) {
 			k->type = KEY_TYPE_DELETED;
@@ -608,8 +615,10 @@ static void extent_save(struct bkey_packed *dst, struct bkey *src,
 #define extent_sort_cmp(l, r)						\
 ({									\
 	const struct bkey_format *_f = &b->set->data->format;		\
-	struct bkey _ul = bkey_unpack_key(_f, (l).k);			\
-	struct bkey _ur = bkey_unpack_key(_f, (r).k);			\
+	struct bkey _ul = bkey_unpack_key(_f,				\
+				__btree_node_offset_to_key(b, (l).k));	\
+	struct bkey _ur = bkey_unpack_key(_f,				\
+				__btree_node_offset_to_key(b, (r).k));	\
 									\
 	int _c = bkey_cmp(bkey_start_pos(&_ul), bkey_start_pos(&_ur));	\
 	_c ? _c > 0 : (l).k < (r).k;					\
@@ -625,7 +634,7 @@ static inline void extent_sort_next(struct btree_node_iter *iter,
 				    struct btree_keys *b,
 				    struct btree_node_iter_set *i)
 {
-	sort_key_next(iter, i);
+	sort_key_next(iter, b, i);
 	heap_sift(iter, i - iter->data, extent_sort_cmp);
 }
 
@@ -660,14 +669,16 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
 {
 	struct bkey_format *f = &b->set->data->format;
 	struct btree_node_iter_set *_l = iter->data, *_r;
-	struct bkey_packed *prev = NULL, *out = bset->start;
+	struct bkey_packed *prev = NULL, *out = bset->start, *lk, *rk;
 	struct bkey_tup l, r;
 
 	heap_resort(iter, extent_sort_cmp);
 
 	while (!bch_btree_node_iter_end(iter)) {
+		lk = __btree_node_offset_to_key(b, _l->k);
+
 		if (iter->used == 1) {
-			out = extent_sort_append(b, out, &prev, _l->k);
+			out = extent_sort_append(b, out, &prev, lk);
 			extent_sort_next(iter, b, _l);
 			continue;
 		}
@@ -677,12 +688,14 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
 		    extent_sort_cmp(_r[0], _r[1]))
 			_r++;
 
-		bkey_disassemble(&l, f, _l->k);
-		bkey_disassemble(&r, f, _r->k);
+		rk = __btree_node_offset_to_key(b, _r->k);
+
+		bkey_disassemble(&l, f, lk);
+		bkey_disassemble(&r, f, rk);
 
 		/* If current key and next key don't overlap, just append */
 		if (bkey_cmp(l.k.p, bkey_start_pos(&r.k)) <= 0) {
-			out = extent_sort_append(b, out, &prev, _l->k);
+			out = extent_sort_append(b, out, &prev, lk);
 			extent_sort_next(iter, b, _l);
 			continue;
 		}
@@ -706,10 +719,10 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
 		if (_l->k > _r->k) {
 			/* l wins, trim r */
 			if (bkey_cmp(l.k.p, r.k.p) >= 0) {
-				sort_key_next(iter, _r);
+				sort_key_next(iter, b, _r);
 			} else {
 				__bch_cut_front(l.k.p, bkey_tup_to_s(&r));
-				extent_save(_r->k, &r.k, f);
+				extent_save(rk, &r.k, f);
 			}
 
 			extent_sort_sift(iter, b, _r - iter->data);
@@ -723,7 +736,7 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
 			bch_cut_back(bkey_start_pos(&r.k), &tmp.k.k);
 
 			__bch_cut_front(r.k.p, bkey_tup_to_s(&l));
-			extent_save(_l->k, &l.k, f);
+			extent_save(lk, &l.k, f);
 
 			extent_sort_sift(iter, b, 0);
 
@@ -731,7 +744,7 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
 						 bkey_to_packed(&tmp.k));
 		} else {
 			bch_cut_back(bkey_start_pos(&r.k), &l.k);
-			extent_save(_l->k, &l.k, f);
+			extent_save(lk, &l.k, f);
 		}
 	}
 
@@ -1770,7 +1783,7 @@ static bool bch_extent_merge_inline(struct btree_keys *b,
 		 * if we don't find this bset in the iterator we already got to
 		 * the end of that bset, so start searching from the end.
 		 */
-		k = bch_btree_node_iter_bset_pos(iter, t->data) ?:
+		k = bch_btree_node_iter_bset_pos(iter, b, t->data) ?:
 			bkey_prev(b, t, bset_bkey_last(t->data));
 
 		if (m == l) {