summaryrefslogtreecommitdiff
path: root/libbcachefs/extents.h
blob: 1ce0d38d278af488589f795fd6897197d4d0748c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
#ifndef _BCACHEFS_EXTENTS_H
#define _BCACHEFS_EXTENTS_H

#include "bcachefs.h"
#include "bkey.h"
#include "extents_types.h"

struct bch_fs;
struct journal_res;
struct btree_node_iter;
struct btree_node_iter_large;
struct btree_insert;
struct btree_insert_entry;
struct extent_insert_hook;
struct bch_devs_mask;
union bch_extent_crc;

struct btree_nr_keys bch2_key_sort_fix_overlapping(struct bset *,
						  struct btree *,
						  struct btree_node_iter_large *);
struct btree_nr_keys bch2_extent_sort_fix_overlapping(struct bch_fs *c,
						     struct bset *,
						     struct btree *,
						     struct btree_node_iter_large *);

extern const struct bkey_ops bch2_bkey_btree_ops;
extern const struct bkey_ops bch2_bkey_extent_ops;

struct extent_pick_ptr
bch2_btree_pick_ptr(struct bch_fs *, const struct btree *,
		    struct bch_devs_mask *avoid);

void bch2_extent_pick_ptr(struct bch_fs *, struct bkey_s_c,
			  struct bch_devs_mask *,
			  struct extent_pick_ptr *);

enum btree_insert_ret
bch2_insert_fixup_extent(struct btree_insert *,
			struct btree_insert_entry *);

bool bch2_extent_normalize(struct bch_fs *, struct bkey_s);
void bch2_extent_mark_replicas_cached(struct bch_fs *, struct bkey_s_extent,
				      unsigned, unsigned);

const struct bch_extent_ptr *
bch2_extent_has_device(struct bkey_s_c_extent, unsigned);
bool bch2_extent_drop_device(struct bkey_s_extent, unsigned);
const struct bch_extent_ptr *
bch2_extent_has_group(struct bch_fs *, struct bkey_s_c_extent, unsigned);
const struct bch_extent_ptr *
bch2_extent_has_target(struct bch_fs *, struct bkey_s_c_extent, unsigned);

unsigned bch2_extent_nr_ptrs(struct bkey_s_c_extent);
unsigned bch2_extent_nr_dirty_ptrs(struct bkey_s_c);
unsigned bch2_extent_nr_good_ptrs(struct bch_fs *, struct bkey_s_c_extent);
unsigned bch2_extent_is_compressed(struct bkey_s_c);

bool bch2_extent_matches_ptr(struct bch_fs *, struct bkey_s_c_extent,
			     struct bch_extent_ptr, u64);

static inline bool bkey_extent_is_data(const struct bkey *k)
{
	switch (k->type) {
	case BCH_EXTENT:
	case BCH_EXTENT_CACHED:
		return true;
	default:
		return false;
	}
}

static inline bool bkey_extent_is_allocation(const struct bkey *k)
{
	switch (k->type) {
	case BCH_EXTENT:
	case BCH_EXTENT_CACHED:
	case BCH_RESERVATION:
		return true;
	default:
		return false;
	}
}

static inline bool bch2_extent_is_fully_allocated(struct bkey_s_c k)
{
	return bkey_extent_is_allocation(k.k) &&
		!bch2_extent_is_compressed(k);
}

static inline bool bkey_extent_is_cached(const struct bkey *k)
{
	return k->type == BCH_EXTENT_CACHED;
}

static inline void bkey_extent_set_cached(struct bkey *k, bool cached)
{
	EBUG_ON(k->type != BCH_EXTENT &&
		k->type != BCH_EXTENT_CACHED);

	k->type = cached ? BCH_EXTENT_CACHED : BCH_EXTENT;
}

static inline unsigned
__extent_entry_type(const union bch_extent_entry *e)
{
	return e->type ? __ffs(e->type) : BCH_EXTENT_ENTRY_MAX;
}

static inline enum bch_extent_entry_type
extent_entry_type(const union bch_extent_entry *e)
{
	int ret = __ffs(e->type);

	EBUG_ON(ret < 0 || ret >= BCH_EXTENT_ENTRY_MAX);

	return ret;
}

static inline size_t extent_entry_bytes(const union bch_extent_entry *entry)
{
	switch (extent_entry_type(entry)) {
	case BCH_EXTENT_ENTRY_crc32:
		return sizeof(struct bch_extent_crc32);
	case BCH_EXTENT_ENTRY_crc64:
		return sizeof(struct bch_extent_crc64);
	case BCH_EXTENT_ENTRY_crc128:
		return sizeof(struct bch_extent_crc128);
	case BCH_EXTENT_ENTRY_ptr:
		return sizeof(struct bch_extent_ptr);
	default:
		BUG();
	}
}

static inline size_t extent_entry_u64s(const union bch_extent_entry *entry)
{
	return extent_entry_bytes(entry) / sizeof(u64);
}

static inline bool extent_entry_is_ptr(const union bch_extent_entry *e)
{
	return extent_entry_type(e) == BCH_EXTENT_ENTRY_ptr;
}

static inline bool extent_entry_is_crc(const union bch_extent_entry *e)
{
	return !extent_entry_is_ptr(e);
}

union bch_extent_crc {
	u8				type;
	struct bch_extent_crc32		crc32;
	struct bch_extent_crc64		crc64;
	struct bch_extent_crc128	crc128;
};

/* downcast, preserves const */
#define to_entry(_entry)						\
({									\
	BUILD_BUG_ON(!type_is(_entry, union bch_extent_crc *) &&	\
		     !type_is(_entry, struct bch_extent_ptr *));	\
									\
	__builtin_choose_expr(						\
		(type_is_exact(_entry, const union bch_extent_crc *) ||	\
		 type_is_exact(_entry, const struct bch_extent_ptr *)),	\
		(const union bch_extent_entry *) (_entry),		\
		(union bch_extent_entry *) (_entry));			\
})

#define __entry_to_crc(_entry)						\
	__builtin_choose_expr(						\
		type_is_exact(_entry, const union bch_extent_entry *),	\
		(const union bch_extent_crc *) (_entry),		\
		(union bch_extent_crc *) (_entry))

#define entry_to_crc(_entry)						\
({									\
	EBUG_ON((_entry) && !extent_entry_is_crc(_entry));		\
									\
	__entry_to_crc(_entry);						\
})

#define entry_to_ptr(_entry)						\
({									\
	EBUG_ON((_entry) && !extent_entry_is_ptr(_entry));		\
									\
	__builtin_choose_expr(						\
		type_is_exact(_entry, const union bch_extent_entry *),	\
		(const struct bch_extent_ptr *) (_entry),		\
		(struct bch_extent_ptr *) (_entry));			\
})

/* checksum entries: */

enum bch_extent_crc_type {
	BCH_EXTENT_CRC_NONE,
	BCH_EXTENT_CRC32,
	BCH_EXTENT_CRC64,
	BCH_EXTENT_CRC128,
};

static inline enum bch_extent_crc_type
__extent_crc_type(const union bch_extent_crc *crc)
{
	if (!crc)
		return BCH_EXTENT_CRC_NONE;

	switch (extent_entry_type(to_entry(crc))) {
	case BCH_EXTENT_ENTRY_crc32:
		return BCH_EXTENT_CRC32;
	case BCH_EXTENT_ENTRY_crc64:
		return BCH_EXTENT_CRC64;
	case BCH_EXTENT_ENTRY_crc128:
		return BCH_EXTENT_CRC128;
	default:
		BUG();
	}
}

#define extent_crc_type(_crc)						\
({									\
	BUILD_BUG_ON(!type_is(_crc, struct bch_extent_crc32 *) &&	\
		     !type_is(_crc, struct bch_extent_crc64 *) &&	\
		     !type_is(_crc, struct bch_extent_crc128 *) &&	\
		     !type_is(_crc, union bch_extent_crc *));		\
									\
	  type_is(_crc, struct bch_extent_crc32 *)  ? BCH_EXTENT_CRC32	\
	: type_is(_crc, struct bch_extent_crc64 *)  ? BCH_EXTENT_CRC64	\
	: type_is(_crc, struct bch_extent_crc128 *) ? BCH_EXTENT_CRC128	\
	: __extent_crc_type((union bch_extent_crc *) _crc);		\
})

static inline struct bch_extent_crc_unpacked
bch2_extent_crc_unpack(const struct bkey *k, const union bch_extent_crc *crc)
{
#define common_fields(_crc)						\
		.csum_type		= _crc.csum_type,		\
		.compression_type	= _crc.compression_type,	\
		.compressed_size	= _crc._compressed_size + 1,	\
		.uncompressed_size	= _crc._uncompressed_size + 1,	\
		.offset			= _crc.offset,			\
		.live_size		= k->size

	switch (extent_crc_type(crc)) {
	case BCH_EXTENT_CRC_NONE:
		return (struct bch_extent_crc_unpacked) {
			.compressed_size	= k->size,
			.uncompressed_size	= k->size,
			.live_size		= k->size,
		};
	case BCH_EXTENT_CRC32:
		return (struct bch_extent_crc_unpacked) {
			common_fields(crc->crc32),
			.csum.lo		= (__force __le64) crc->crc32.csum,
		};
	case BCH_EXTENT_CRC64:
		return (struct bch_extent_crc_unpacked) {
			common_fields(crc->crc64),
			.nonce			= crc->crc64.nonce,
			.csum.lo		= (__force __le64) crc->crc64.csum_lo,
			.csum.hi		= (__force __le64) crc->crc64.csum_hi,
		};
	case BCH_EXTENT_CRC128:
		return (struct bch_extent_crc_unpacked) {
			common_fields(crc->crc128),
			.nonce			= crc->crc128.nonce,
			.csum			= crc->crc128.csum,
		};
	default:
		BUG();
	}
#undef common_fields
}

/* Extent entry iteration: */

#define extent_entry_next(_entry)					\
	((typeof(_entry)) ((void *) (_entry) + extent_entry_bytes(_entry)))

#define extent_entry_last(_e)						\
	vstruct_idx((_e).v, bkey_val_u64s((_e).k))

/* Iterate over all entries: */

#define extent_for_each_entry_from(_e, _entry, _start)			\
	for ((_entry) = _start;						\
	     (_entry) < extent_entry_last(_e);				\
	     (_entry) = extent_entry_next(_entry))

#define extent_for_each_entry(_e, _entry)				\
	extent_for_each_entry_from(_e, _entry, (_e).v->start)

/* Iterate over crcs only: */

#define __extent_crc_next(_e, _p)					\
({									\
	typeof(&(_e).v->start[0]) _entry = _p;				\
									\
	while ((_entry) < extent_entry_last(_e) &&			\
	       !extent_entry_is_crc(_entry))				\
		(_entry) = extent_entry_next(_entry);			\
									\
	entry_to_crc(_entry < extent_entry_last(_e) ? _entry : NULL);	\
})

#define __extent_for_each_crc(_e, _crc)					\
	for ((_crc) = __extent_crc_next(_e, (_e).v->start);		\
	     (_crc);							\
	     (_crc) = __extent_crc_next(_e, extent_entry_next(to_entry(_crc))))

#define extent_crc_next(_e, _crc, _iter)				\
({									\
	extent_for_each_entry_from(_e, _iter, _iter)			\
		if (extent_entry_is_crc(_iter)) {			\
			(_crc) = bch2_extent_crc_unpack((_e).k, entry_to_crc(_iter));\
			break;						\
		}							\
									\
	(_iter) < extent_entry_last(_e);				\
})

#define extent_for_each_crc(_e, _crc, _iter)				\
	for ((_crc) = bch2_extent_crc_unpack((_e).k, NULL),		\
	     (_iter) = (_e).v->start;					\
	     extent_crc_next(_e, _crc, _iter);				\
	     (_iter) = extent_entry_next(_iter))

/* Iterate over pointers, with crcs: */

#define extent_ptr_crc_next(_e, _ptr, _crc)				\
({									\
	__label__ out;							\
	typeof(&(_e).v->start[0]) _entry;				\
									\
	extent_for_each_entry_from(_e, _entry, to_entry(_ptr))		\
		if (extent_entry_is_crc(_entry)) {			\
			(_crc) = bch2_extent_crc_unpack((_e).k, entry_to_crc(_entry));\
		} else {						\
			_ptr = entry_to_ptr(_entry);			\
			goto out;					\
		}							\
									\
	_ptr = NULL;							\
out:									\
	_ptr;								\
})

#define extent_for_each_ptr_crc(_e, _ptr, _crc)				\
	for ((_crc) = bch2_extent_crc_unpack((_e).k, NULL),		\
	     (_ptr) = &(_e).v->start->ptr;				\
	     ((_ptr) = extent_ptr_crc_next(_e, _ptr, _crc));		\
	     (_ptr)++)

/* Iterate over pointers only, and from a given position: */

#define extent_ptr_next(_e, _ptr)					\
({									\
	struct bch_extent_crc_unpacked _crc;				\
									\
	extent_ptr_crc_next(_e, _ptr, _crc);				\
})

#define extent_for_each_ptr(_e, _ptr)					\
	for ((_ptr) = &(_e).v->start->ptr;				\
	     ((_ptr) = extent_ptr_next(_e, _ptr));			\
	     (_ptr)++)

#define extent_ptr_prev(_e, _ptr)					\
({									\
	typeof(&(_e).v->start->ptr) _p;					\
	typeof(&(_e).v->start->ptr) _prev = NULL;			\
									\
	extent_for_each_ptr(_e, _p) {					\
		if (_p == (_ptr))					\
			break;						\
		_prev = _p;						\
	}								\
									\
	_prev;								\
})

/*
 * Use this when you'll be dropping pointers as you iterate. Quadratic,
 * unfortunately:
 */
#define extent_for_each_ptr_backwards(_e, _ptr)				\
	for ((_ptr) = extent_ptr_prev(_e, NULL);			\
	     (_ptr);							\
	     (_ptr) = extent_ptr_prev(_e, _ptr))

void bch2_extent_crc_append(struct bkey_i_extent *,
			    struct bch_extent_crc_unpacked);

static inline void __extent_entry_push(struct bkey_i_extent *e)
{
	union bch_extent_entry *entry = extent_entry_last(extent_i_to_s(e));

	EBUG_ON(bkey_val_u64s(&e->k) + extent_entry_u64s(entry) >
		BKEY_EXTENT_VAL_U64s_MAX);

	e->k.u64s += extent_entry_u64s(entry);
}

static inline void extent_ptr_append(struct bkey_i_extent *e,
				     struct bch_extent_ptr ptr)
{
	ptr.type = 1 << BCH_EXTENT_ENTRY_ptr;
	extent_entry_last(extent_i_to_s(e))->ptr = ptr;
	__extent_entry_push(e);
}

static inline struct bch_devs_list bch2_extent_devs(struct bkey_s_c_extent e)
{
	struct bch_devs_list ret = (struct bch_devs_list) { 0 };
	const struct bch_extent_ptr *ptr;

	extent_for_each_ptr(e, ptr)
		ret.devs[ret.nr++] = ptr->dev;

	return ret;
}

static inline struct bch_devs_list bch2_extent_dirty_devs(struct bkey_s_c_extent e)
{
	struct bch_devs_list ret = (struct bch_devs_list) { 0 };
	const struct bch_extent_ptr *ptr;

	extent_for_each_ptr(e, ptr)
		if (!ptr->cached)
			ret.devs[ret.nr++] = ptr->dev;

	return ret;
}

static inline struct bch_devs_list bch2_extent_cached_devs(struct bkey_s_c_extent e)
{
	struct bch_devs_list ret = (struct bch_devs_list) { 0 };
	const struct bch_extent_ptr *ptr;

	extent_for_each_ptr(e, ptr)
		if (ptr->cached)
			ret.devs[ret.nr++] = ptr->dev;

	return ret;
}

static inline struct bch_devs_list bch2_bkey_devs(struct bkey_s_c k)
{
	switch (k.k->type) {
	case BCH_EXTENT:
	case BCH_EXTENT_CACHED:
		return bch2_extent_devs(bkey_s_c_to_extent(k));
	default:
		return (struct bch_devs_list) { .nr = 0 };
	}
}

static inline struct bch_devs_list bch2_bkey_dirty_devs(struct bkey_s_c k)
{
	switch (k.k->type) {
	case BCH_EXTENT:
	case BCH_EXTENT_CACHED:
		return bch2_extent_dirty_devs(bkey_s_c_to_extent(k));
	default:
		return (struct bch_devs_list) { .nr = 0 };
	}
}

static inline struct bch_devs_list bch2_bkey_cached_devs(struct bkey_s_c k)
{
	switch (k.k->type) {
	case BCH_EXTENT:
	case BCH_EXTENT_CACHED:
		return bch2_extent_cached_devs(bkey_s_c_to_extent(k));
	default:
		return (struct bch_devs_list) { .nr = 0 };
	}
}

bool bch2_can_narrow_extent_crcs(struct bkey_s_c_extent,
				 struct bch_extent_crc_unpacked);
bool bch2_extent_narrow_crcs(struct bkey_i_extent *, struct bch_extent_crc_unpacked);
void bch2_extent_drop_redundant_crcs(struct bkey_s_extent);

void __bch2_extent_drop_ptr(struct bkey_s_extent, struct bch_extent_ptr *);
void bch2_extent_drop_ptr(struct bkey_s_extent, struct bch_extent_ptr *);

bool bch2_cut_front(struct bpos, struct bkey_i *);
bool bch2_cut_back(struct bpos, struct bkey *);
void bch2_key_resize(struct bkey *, unsigned);

int bch2_check_range_allocated(struct bch_fs *, struct bpos, u64);

#endif /* _BCACHEFS_EXTENTS_H */