bcachefs: Use KEY_TYPE_deleted whitouts for extents

Previously, partial overwrites of existing extents were handled
implicitly by the btree code; when reading in a btree node, we'd do a
mergesort of the different bsets and detect and fix partially
overlapping extents during that mergesort.

That approach won't work with snapshots: this changes extents to work
like regular keys as far as the btree code is concerned, where a 0 size
KEY_TYPE_deleted whiteout will completely overwrite an existing extent.

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

1 files changed, 117 insertions, 115 deletions

diff --git a/fs/bcachefs/bkey_sort.c b/fs/bcachefs/bkey_sort.c
index 23b51ef57303..18f842012f05 100644
--- a/fs/bcachefs/bkey_sort.c
+++ b/fs/bcachefs/bkey_sort.c
@@ -130,24 +130,6 @@ bch2_key_sort_fix_overlapping(struct bch_fs *c, struct bset *dst,
 	return nr;
 }
 
-/*
- * If keys compare equal, compare by pointer order:
- *
- * Necessary for sort_fix_overlapping() - if there are multiple keys that
- * compare equal in different sets, we have to process them newest to oldest.
- */
-static inline int extent_sort_fix_overlapping_cmp(struct btree *b,
-						  struct bkey_packed *l,
-						  struct bkey_packed *r)
-{
-	struct bkey ul = bkey_unpack_key(b, l);
-	struct bkey ur = bkey_unpack_key(b, r);
-
-	return bkey_cmp(bkey_start_pos(&ul),
-			bkey_start_pos(&ur)) ?:
-		cmp_int((unsigned long) r, (unsigned long) l);
-}
-
 static void extent_sort_advance_prev(struct bkey_format *f,
 				     struct btree_nr_keys *nr,
 				     struct bkey_packed *start,
@@ -188,102 +170,6 @@ static void extent_sort_append(struct bch_fs *c,
 	bkey_reassemble((void *) *prev, k.s_c);
 }
 
-struct btree_nr_keys
-bch2_extent_sort_fix_overlapping(struct bch_fs *c, struct bset *dst,
-				 struct sort_iter *iter)
-{
-	struct btree *b = iter->b;
-	struct bkey_format *f = &b->format;
-	struct sort_iter_set *_l = iter->data, *_r = iter->data + 1;
-	struct bkey_packed *prev = NULL;
-	struct bkey l_unpacked, r_unpacked;
-	struct bkey_s l, r;
-	struct btree_nr_keys nr;
-	struct bkey_on_stack split;
-
-	memset(&nr, 0, sizeof(nr));
-	bkey_on_stack_init(&split);
-
-	sort_iter_sort(iter, extent_sort_fix_overlapping_cmp);
-
-	while (!sort_iter_end(iter)) {
-		l = __bkey_disassemble(b, _l->k, &l_unpacked);
-
-		if (iter->used == 1) {
-			extent_sort_append(c, f, &nr, dst->start, &prev, l);
-			sort_iter_advance(iter,
-					  extent_sort_fix_overlapping_cmp);
-			continue;
-		}
-
-		r = __bkey_disassemble(b, _r->k, &r_unpacked);
-
-		/* If current key and next key don't overlap, just append */
-		if (bkey_cmp(l.k->p, bkey_start_pos(r.k)) <= 0) {
-			extent_sort_append(c, f, &nr, dst->start, &prev, l);
-			sort_iter_advance(iter,
-					  extent_sort_fix_overlapping_cmp);
-			continue;
-		}
-
-		/* Skip 0 size keys */
-		if (!r.k->size) {
-			__sort_iter_advance(iter, 1,
-					    extent_sort_fix_overlapping_cmp);
-			continue;
-		}
-
-		/*
-		 * overlap: keep the newer key and trim the older key so they
-		 * don't overlap. comparing pointers tells us which one is
-		 * newer, since the bsets are appended one after the other.
-		 */
-
-		/* can't happen because of comparison func */
-		BUG_ON(_l->k < _r->k &&
-		       !bkey_cmp(bkey_start_pos(l.k), bkey_start_pos(r.k)));
-
-		if (_l->k > _r->k) {
-			/* l wins, trim r */
-			if (bkey_cmp(l.k->p, r.k->p) >= 0) {
-				__sort_iter_advance(iter, 1,
-					 extent_sort_fix_overlapping_cmp);
-			} else {
-				bch2_cut_front_s(l.k->p, r);
-				extent_save(b, _r->k, r.k);
-				__sort_iter_sift(iter, 1,
-					 extent_sort_fix_overlapping_cmp);
-			}
-		} else if (bkey_cmp(l.k->p, r.k->p) > 0) {
-
-			/*
-			 * r wins, but it overlaps in the middle of l - split l:
-			 */
-			bkey_on_stack_reassemble(&split, c, l.s_c);
-			bch2_cut_back(bkey_start_pos(r.k), split.k);
-
-			bch2_cut_front_s(r.k->p, l);
-			extent_save(b, _l->k, l.k);
-
-			__sort_iter_sift(iter, 0,
-					 extent_sort_fix_overlapping_cmp);
-
-			extent_sort_append(c, f, &nr, dst->start,
-					   &prev, bkey_i_to_s(split.k));
-		} else {
-			bch2_cut_back_s(bkey_start_pos(r.k), l);
-			extent_save(b, _l->k, l.k);
-		}
-	}
-
-	extent_sort_advance_prev(f, &nr, dst->start, &prev);
-
-	dst->u64s = cpu_to_le16((u64 *) prev - dst->_data);
-
-	bkey_on_stack_exit(&split, c);
-	return nr;
-}
-
 /* Sort + repack in a new format: */
 struct btree_nr_keys
 bch2_sort_repack(struct bset *dst, struct btree *src,
@@ -354,7 +240,7 @@ static inline int sort_keys_cmp(struct btree *b,
 				struct bkey_packed *r)
 {
 	return bkey_cmp_packed(b, l, r) ?:
-		(int) bkey_whiteout(r) - (int) bkey_whiteout(l) ?:
+		(int) bkey_deleted(r) - (int) bkey_deleted(l) ?:
 		(int) l->needs_whiteout - (int) r->needs_whiteout;
 }
 
@@ -399,6 +285,122 @@ unsigned bch2_sort_keys(struct bkey_packed *dst,
 	return (u64 *) out - (u64 *) dst;
 }
 
+/* Compat code for btree_node_old_extent_overwrite: */
+
+/*
+ * If keys compare equal, compare by pointer order:
+ *
+ * Necessary for sort_fix_overlapping() - if there are multiple keys that
+ * compare equal in different sets, we have to process them newest to oldest.
+ */
+static inline int extent_sort_fix_overlapping_cmp(struct btree *b,
+						  struct bkey_packed *l,
+						  struct bkey_packed *r)
+{
+	struct bkey ul = bkey_unpack_key(b, l);
+	struct bkey ur = bkey_unpack_key(b, r);
+
+	return bkey_cmp(bkey_start_pos(&ul),
+			bkey_start_pos(&ur)) ?:
+		cmp_int((unsigned long) r, (unsigned long) l);
+}
+
+struct btree_nr_keys
+bch2_extent_sort_fix_overlapping(struct bch_fs *c, struct bset *dst,
+				 struct sort_iter *iter)
+{
+	struct btree *b = iter->b;
+	struct bkey_format *f = &b->format;
+	struct sort_iter_set *_l = iter->data, *_r = iter->data + 1;
+	struct bkey_packed *prev = NULL;
+	struct bkey l_unpacked, r_unpacked;
+	struct bkey_s l, r;
+	struct btree_nr_keys nr;
+	struct bkey_on_stack split;
+
+	memset(&nr, 0, sizeof(nr));
+	bkey_on_stack_init(&split);
+
+	sort_iter_sort(iter, extent_sort_fix_overlapping_cmp);
+
+	while (!sort_iter_end(iter)) {
+		l = __bkey_disassemble(b, _l->k, &l_unpacked);
+
+		if (iter->used == 1) {
+			extent_sort_append(c, f, &nr, dst->start, &prev, l);
+			sort_iter_advance(iter,
+					  extent_sort_fix_overlapping_cmp);
+			continue;
+		}
+
+		r = __bkey_disassemble(b, _r->k, &r_unpacked);
+
+		/* If current key and next key don't overlap, just append */
+		if (bkey_cmp(l.k->p, bkey_start_pos(r.k)) <= 0) {
+			extent_sort_append(c, f, &nr, dst->start, &prev, l);
+			sort_iter_advance(iter,
+					  extent_sort_fix_overlapping_cmp);
+			continue;
+		}
+
+		/* Skip 0 size keys */
+		if (!r.k->size) {
+			__sort_iter_advance(iter, 1,
+					    extent_sort_fix_overlapping_cmp);
+			continue;
+		}
+
+		/*
+		 * overlap: keep the newer key and trim the older key so they
+		 * don't overlap. comparing pointers tells us which one is
+		 * newer, since the bsets are appended one after the other.
+		 */
+
+		/* can't happen because of comparison func */
+		BUG_ON(_l->k < _r->k &&
+		       !bkey_cmp(bkey_start_pos(l.k), bkey_start_pos(r.k)));
+
+		if (_l->k > _r->k) {
+			/* l wins, trim r */
+			if (bkey_cmp(l.k->p, r.k->p) >= 0) {
+				__sort_iter_advance(iter, 1,
+					 extent_sort_fix_overlapping_cmp);
+			} else {
+				bch2_cut_front_s(l.k->p, r);
+				extent_save(b, _r->k, r.k);
+				__sort_iter_sift(iter, 1,
+					 extent_sort_fix_overlapping_cmp);
+			}
+		} else if (bkey_cmp(l.k->p, r.k->p) > 0) {
+
+			/*
+			 * r wins, but it overlaps in the middle of l - split l:
+			 */
+			bkey_on_stack_reassemble(&split, c, l.s_c);
+			bch2_cut_back(bkey_start_pos(r.k), split.k);
+
+			bch2_cut_front_s(r.k->p, l);
+			extent_save(b, _l->k, l.k);
+
+			__sort_iter_sift(iter, 0,
+					 extent_sort_fix_overlapping_cmp);
+
+			extent_sort_append(c, f, &nr, dst->start,
+					   &prev, bkey_i_to_s(split.k));
+		} else {
+			bch2_cut_back_s(bkey_start_pos(r.k), l);
+			extent_save(b, _l->k, l.k);
+		}
+	}
+
+	extent_sort_advance_prev(f, &nr, dst->start, &prev);
+
+	dst->u64s = cpu_to_le16((u64 *) prev - dst->_data);
+
+	bkey_on_stack_exit(&split, c);
+	return nr;
+}
+
 static inline int sort_extents_cmp(struct btree *b,
 				   struct bkey_packed *l,
 				   struct bkey_packed *r)