xref: /spdk/lib/ftl/utils/ftl_layout_tracker_bdev.c (revision 8afdeef3becfe9409cc9e7372bd0bc10e8b7d46d) 
1 /*   SPDX-License-Identifier: BSD-3-Clause
2  *   Copyright 2023 Solidigm All Rights Reserved
3  */
4 
5 #include "ftl_layout_tracker_bdev.h"
6 #include "spdk/util.h"
7 
8 #define REG_VER_ANY	UINT32_MAX
9 
10 struct layout_tracker_entry {
11 	TAILQ_ENTRY(layout_tracker_entry) layout_entry;
12 	struct ftl_layout_tracker_bdev_region_props reg;
13 };
14 
15 struct ftl_layout_tracker_bdev {
16 	TAILQ_HEAD(layout_tracker, layout_tracker_entry) layout_head;
17 	uint64_t bdev_blks;
18 	uint32_t regs_cnt;
19 };
20 
21 struct layout_tracker_blob_entry {
22 	/* Region type */
23 	uint32_t type;
24 
25 	/* Region version */
26 	uint32_t ver;
27 
28 	/* Region offset in blocks */
29 	uint64_t blk_offs;
30 
31 	/* Region size in blocks */
32 	uint64_t blk_sz;
33 } __attribute__((packed));
34 
35 static int
36 layout_tracker_init_entries(struct ftl_layout_tracker_bdev *tracker, uint64_t bdev_blks)
37 {
38 	struct layout_tracker_entry *entry_free = calloc(1, sizeof(*entry_free));
39 
40 	if (!entry_free) {
41 		return -ENOMEM;
42 	}
43 
44 	assert(tracker);
45 	assert(tracker->regs_cnt == 0);
46 
47 	tracker->bdev_blks = bdev_blks;
48 	tracker->regs_cnt = 1;
49 	TAILQ_INIT(&tracker->layout_head);
50 
51 	entry_free->reg.blk_sz = bdev_blks;
52 	entry_free->reg.type = FTL_LAYOUT_REGION_TYPE_FREE;
53 
54 	TAILQ_INSERT_HEAD(&tracker->layout_head, entry_free, layout_entry);
55 	return 0;
56 }
57 
58 struct ftl_layout_tracker_bdev *
59 ftl_layout_tracker_bdev_init(uint64_t bdev_blks)
60 {
61 	struct ftl_layout_tracker_bdev *tracker = calloc(1, sizeof(*tracker));
62 
63 	if (!tracker) {
64 		return NULL;
65 	}
66 
67 	if (layout_tracker_init_entries(tracker, bdev_blks)) {
68 		free(tracker);
69 		return NULL;
70 	}
71 
72 	return tracker;
73 }
74 
75 static void
76 layout_tracker_free_entries(struct ftl_layout_tracker_bdev *tracker)
77 {
78 	struct layout_tracker_entry *entry;
79 
80 	while ((entry = TAILQ_FIRST(&tracker->layout_head))) {
81 		TAILQ_REMOVE(&tracker->layout_head, entry, layout_entry);
82 		free(entry);
83 	}
84 	tracker->regs_cnt = 0;
85 }
86 
87 void
88 ftl_layout_tracker_bdev_fini(struct ftl_layout_tracker_bdev *tracker)
89 {
90 	assert(tracker);
91 	layout_tracker_free_entries(tracker);
92 	free(tracker);
93 }
94 
95 static struct layout_tracker_entry *
96 layout_region_find_min_free(struct ftl_layout_tracker_bdev *tracker, uint64_t blk_sz,
97 			    uint64_t blk_align)
98 {
99 	struct layout_tracker_entry *min_free_entry = NULL;
100 	struct layout_tracker_entry *entry;
101 
102 	assert(tracker);
103 
104 	TAILQ_FOREACH(entry, &tracker->layout_head, layout_entry) {
105 		uint64_t align_offs, align_sz;
106 
107 		if (entry->reg.type != FTL_LAYOUT_REGION_TYPE_FREE) {
108 			continue;
109 		}
110 
111 		align_offs = entry->reg.blk_offs;
112 		align_sz = entry->reg.blk_sz;
113 		if (blk_align) {
114 			align_offs = SPDK_ALIGN_CEIL(align_offs, blk_align);
115 			align_sz -= (align_offs - entry->reg.blk_offs);
116 		}
117 
118 		if (align_sz >= blk_sz) {
119 			if (!min_free_entry || min_free_entry->reg.blk_sz > entry->reg.blk_sz) {
120 				min_free_entry = entry;
121 			}
122 		}
123 	}
124 
125 	return min_free_entry;
126 }
127 
128 static struct layout_tracker_entry *
129 layout_region_find_from(struct ftl_layout_tracker_bdev *tracker,
130 			enum ftl_layout_region_type reg_type,
131 			uint32_t reg_ver, struct layout_tracker_entry *entry)
132 {
133 	assert(tracker);
134 
135 	TAILQ_FOREACH_FROM(entry, &tracker->layout_head, layout_entry) {
136 		if ((entry->reg.type == reg_type || reg_type == FTL_LAYOUT_REGION_TYPE_INVALID)
137 		    && (entry->reg.ver == reg_ver || reg_ver == REG_VER_ANY)) {
138 			return entry;
139 		}
140 	}
141 
142 	return NULL;
143 }
144 
145 static struct layout_tracker_entry *
146 layout_region_find_first(struct ftl_layout_tracker_bdev *tracker,
147 			 enum ftl_layout_region_type reg_type,
148 			 uint32_t reg_ver)
149 {
150 	return layout_region_find_from(tracker, reg_type, reg_ver, TAILQ_FIRST(&tracker->layout_head));
151 }
152 
153 static struct layout_tracker_entry *
154 layout_region_find_next(struct ftl_layout_tracker_bdev *tracker,
155 			enum ftl_layout_region_type reg_type,
156 			uint32_t reg_ver, struct layout_tracker_entry *entry)
157 {
158 	if ((entry = TAILQ_NEXT(entry, layout_entry))) {
159 		return layout_region_find_from(tracker, reg_type, reg_ver, entry);
160 	}
161 	return NULL;
162 }
163 
164 const struct ftl_layout_tracker_bdev_region_props *
165 ftl_layout_tracker_bdev_add_region(struct ftl_layout_tracker_bdev *tracker,
166 				   enum ftl_layout_region_type reg_type, uint32_t reg_ver, uint64_t blk_sz, uint64_t blk_align)
167 {
168 	struct layout_tracker_entry *entry_free;
169 	struct layout_tracker_entry *entry_new;
170 	uint64_t entry_free_blks_left;
171 
172 	assert(tracker);
173 	assert(reg_type < FTL_LAYOUT_REGION_TYPE_MAX);
174 
175 	entry_new = layout_region_find_first(tracker, reg_type, reg_ver);
176 	if (entry_new) {
177 		/* Region already exists */
178 		return NULL;
179 	}
180 
181 	entry_free = layout_region_find_min_free(tracker, blk_sz, blk_align);
182 	if (!entry_free) {
183 		/* No free space */
184 		return NULL;
185 	}
186 
187 	/* Takce care of the alignment */
188 	if (blk_align) {
189 		/* Calculate the aligned region's offs and size */
190 		uint64_t align_offs = SPDK_ALIGN_CEIL(entry_free->reg.blk_offs, blk_align);
191 		assert(align_offs >= entry_free->reg.blk_offs);
192 
193 		/* Subdivide the free region in two: unaligned free region, followed by the aligned free region */
194 		if (align_offs > entry_free->reg.blk_offs) {
195 			uint64_t unaligned_sz = align_offs - entry_free->reg.blk_offs;
196 
197 			/* Setup the unaligned region */
198 			entry_new = calloc(1, sizeof(*entry_new));
199 			if (!entry_new) {
200 				return NULL;
201 			}
202 			entry_new->reg = entry_free->reg;
203 			entry_new->reg.blk_sz = unaligned_sz;
204 
205 			/* Setup the aligned region - shrink the free region found */
206 			entry_free->reg.blk_offs = align_offs;
207 			entry_free->reg.blk_sz -= unaligned_sz;
208 
209 			/* Add the unaligned region prev to the aligned one */
210 			TAILQ_INSERT_BEFORE(entry_free, entry_new, layout_entry);
211 			tracker->regs_cnt++;
212 		}
213 	}
214 
215 	entry_free_blks_left = entry_free->reg.blk_sz - blk_sz;
216 
217 	if (entry_free_blks_left) {
218 		/* Subdivide the free region */
219 		entry_new = calloc(1, sizeof(*entry_new));
220 		if (!entry_new) {
221 			return NULL;
222 		}
223 
224 		/* Setup the new region at the beginning of the free region found */
225 		entry_new->reg.type = reg_type;
226 		entry_new->reg.ver = reg_ver;
227 		entry_new->reg.blk_offs = entry_free->reg.blk_offs;
228 		entry_new->reg.blk_sz = blk_sz;
229 
230 		/* Shrink the free region found */
231 		entry_free->reg.blk_offs += blk_sz;
232 		entry_free->reg.blk_sz = entry_free_blks_left;
233 
234 		/* Add the new region */
235 		TAILQ_INSERT_BEFORE(entry_free, entry_new, layout_entry);
236 		tracker->regs_cnt++;
237 	} else {
238 		/* Setup the new region in place */
239 		entry_new = entry_free;
240 		entry_new->reg.type = reg_type;
241 		entry_new->reg.ver = reg_ver;
242 	}
243 
244 	return &entry_new->reg;
245 }
246 
247 const struct ftl_layout_tracker_bdev_region_props *
248 ftl_layout_tracker_bdev_insert_region(struct ftl_layout_tracker_bdev *tracker,
249 				      enum ftl_layout_region_type reg_type, uint32_t reg_ver,
250 				      uint64_t blk_offs, uint64_t blk_sz)
251 {
252 	struct layout_tracker_entry *entry_free;
253 	struct layout_tracker_entry *entry_new;
254 	uint64_t entry_free_blks_left;
255 
256 	assert(tracker);
257 
258 	if (reg_type >= FTL_LAYOUT_REGION_TYPE_MAX && reg_type != FTL_LAYOUT_REGION_TYPE_INVALID) {
259 		/* Invalid region type */
260 		return NULL;
261 	}
262 
263 	if (reg_type != FTL_LAYOUT_REGION_TYPE_INVALID) {
264 		entry_new = layout_region_find_first(tracker, reg_type, reg_ver);
265 		if (entry_new) {
266 			/* Region already exists */
267 			return NULL;
268 		}
269 	}
270 
271 	/* Look up for the free region corresponding to the blk_offs */
272 	for (entry_free = layout_region_find_first(tracker, FTL_LAYOUT_REGION_TYPE_FREE, REG_VER_ANY);
273 	     entry_free;
274 	     entry_free = layout_region_find_next(tracker, FTL_LAYOUT_REGION_TYPE_FREE, REG_VER_ANY,
275 			     entry_free)) {
276 		/* Test if the region being added fits into the free region */
277 		if (entry_free->reg.blk_offs <= blk_offs
278 		    && blk_offs + blk_sz <= entry_free->reg.blk_offs + entry_free->reg.blk_sz) {
279 			break;
280 		}
281 	}
282 
283 	if (!entry_free) {
284 		/* Did not found the corresponding free region */
285 		return NULL;
286 	}
287 
288 	if (reg_type == FTL_LAYOUT_REGION_TYPE_INVALID) {
289 		/* Dry run */
290 		return &entry_free->reg;
291 	}
292 
293 	entry_free_blks_left = blk_offs - entry_free->reg.blk_offs;
294 	if (entry_free_blks_left) {
295 		/* Subdivide the free region */
296 		entry_new = calloc(1, sizeof(*entry_new));
297 		if (!entry_new) {
298 			return NULL;
299 		}
300 
301 		/* Setup another free region at the beginning of the free region found */
302 		entry_new->reg.type = FTL_LAYOUT_REGION_TYPE_FREE;
303 		entry_new->reg.blk_offs = entry_free->reg.blk_offs;
304 		entry_new->reg.blk_sz = entry_free_blks_left;
305 
306 		/* Shrink the free region found */
307 		entry_free->reg.blk_offs += entry_free_blks_left;
308 		assert(entry_free->reg.blk_sz > entry_free_blks_left);
309 		entry_free->reg.blk_sz -= entry_free_blks_left;
310 
311 		/* Add the new free region */
312 		TAILQ_INSERT_BEFORE(entry_free, entry_new, layout_entry);
313 		tracker->regs_cnt++;
314 	}
315 
316 	assert(entry_free->reg.blk_offs == blk_offs);
317 	assert(blk_sz <= entry_free->reg.blk_sz);
318 
319 	entry_free_blks_left = entry_free->reg.blk_sz - blk_sz;
320 	if (entry_free_blks_left) {
321 		/* Subdivide the free region */
322 		entry_new = calloc(1, sizeof(*entry_new));
323 		if (!entry_new) {
324 			return NULL;
325 		}
326 
327 		/* Setup the new region at the beginning of the free region found */
328 		entry_new->reg.type = reg_type;
329 		entry_new->reg.ver = reg_ver;
330 		entry_new->reg.blk_offs = entry_free->reg.blk_offs;
331 		entry_new->reg.blk_sz = blk_sz;
332 
333 		/* Shrink the free region found */
334 		entry_free->reg.blk_offs += blk_sz;
335 		entry_free->reg.blk_sz = entry_free_blks_left;
336 
337 		/* Add the new region */
338 		TAILQ_INSERT_BEFORE(entry_free, entry_new, layout_entry);
339 		tracker->regs_cnt++;
340 	} else {
341 		/* Setup the new region in place */
342 		entry_new = entry_free;
343 		entry_new->reg.type = reg_type;
344 		entry_new->reg.ver = reg_ver;
345 	}
346 
347 	return &entry_new->reg;
348 }
349 
350 int
351 ftl_layout_tracker_bdev_rm_region(struct ftl_layout_tracker_bdev *tracker,
352 				  enum ftl_layout_region_type reg_type, uint32_t reg_ver)
353 {
354 	struct layout_tracker_entry *entry_rm, *entry_check __attribute__((unused));
355 	struct layout_tracker_entry *entry = layout_region_find_first(tracker, reg_type, reg_ver);
356 
357 	if (!entry) {
358 		return -1;
359 	}
360 
361 	/* Free the region */
362 	entry->reg.type = FTL_LAYOUT_REGION_TYPE_FREE;
363 	entry->reg.ver = 0;
364 
365 	/* Join with the adjacent free region prev to the current region */
366 	entry_rm = TAILQ_PREV(entry, layout_tracker, layout_entry);
367 	if (entry_rm && entry_rm->reg.type == FTL_LAYOUT_REGION_TYPE_FREE) {
368 		TAILQ_REMOVE(&tracker->layout_head, entry_rm, layout_entry);
369 		entry->reg.blk_offs = entry_rm->reg.blk_offs;
370 		entry->reg.blk_sz += entry_rm->reg.blk_sz;
371 
372 #if defined(DEBUG)
373 		entry_check = TAILQ_PREV(entry, layout_tracker, layout_entry);
374 		if (entry_check) {
375 			assert(entry_check->reg.type != FTL_LAYOUT_REGION_TYPE_FREE);
376 		}
377 #endif
378 
379 		free(entry_rm);
380 		tracker->regs_cnt--;
381 	}
382 
383 	/* Join with the adjacent free region next to the current region */
384 	entry_rm = TAILQ_NEXT(entry, layout_entry);
385 	if (entry_rm && entry_rm->reg.type == FTL_LAYOUT_REGION_TYPE_FREE) {
386 		TAILQ_REMOVE(&tracker->layout_head, entry_rm, layout_entry);
387 		entry->reg.blk_sz += entry_rm->reg.blk_sz;
388 
389 #if defined(DEBUG)
390 		entry_check = TAILQ_NEXT(entry, layout_entry);
391 		if (entry_check) {
392 			assert(entry_check->reg.type != FTL_LAYOUT_REGION_TYPE_FREE);
393 		}
394 #endif
395 		free(entry_rm);
396 		tracker->regs_cnt--;
397 	}
398 
399 	return 0;
400 }
401 
402 void
403 ftl_layout_tracker_bdev_find_next_region(struct ftl_layout_tracker_bdev *tracker,
404 		enum ftl_layout_region_type reg_type,
405 		const struct ftl_layout_tracker_bdev_region_props **search_ctx)
406 {
407 	struct layout_tracker_entry *entry;
408 
409 	if (!search_ctx) {
410 		return;
411 	}
412 
413 	if (*search_ctx == NULL) {
414 		/* Return the first region found */
415 		entry = layout_region_find_first(tracker, reg_type, REG_VER_ANY);
416 	} else {
417 		/* Find the next region */
418 		entry = SPDK_CONTAINEROF(*search_ctx, struct layout_tracker_entry, reg);
419 		entry = layout_region_find_next(tracker, reg_type, REG_VER_ANY, entry);
420 	}
421 	*search_ctx = entry ? &entry->reg : NULL;
422 }
423 
424 size_t
425 ftl_layout_tracker_bdev_blob_store(struct ftl_layout_tracker_bdev *tracker, void *blob_buf,
426 				   size_t blob_buf_sz)
427 {
428 	struct layout_tracker_blob_entry *blob_entry = blob_buf;
429 	struct layout_tracker_entry *entry;
430 	size_t blob_sz = 0;
431 
432 	assert(tracker);
433 
434 	TAILQ_FOREACH(entry, &tracker->layout_head, layout_entry) {
435 		if (blob_sz + sizeof(*blob_entry) > blob_buf_sz) {
436 			/* Ran out of buf space */
437 			assert(false);
438 			return 0;
439 		}
440 
441 		/* Skip the free space entries */
442 		if (entry->reg.type == FTL_LAYOUT_REGION_TYPE_FREE) {
443 			continue;
444 		}
445 
446 		/* Store the entry */
447 		blob_entry->type = entry->reg.type;
448 		blob_entry->ver = entry->reg.ver;
449 		blob_entry->blk_offs = entry->reg.blk_offs;
450 		blob_entry->blk_sz = entry->reg.blk_sz;
451 
452 		/* Move to the next entry */
453 		blob_entry++;
454 		blob_sz += sizeof(*blob_entry);
455 	}
456 
457 	return blob_sz;
458 }
459 
460 int
461 ftl_layout_tracker_bdev_blob_load(struct ftl_layout_tracker_bdev *tracker, void *blob_buf,
462 				  size_t blob_sz)
463 {
464 	struct layout_tracker_blob_entry *blob_entry = blob_buf;
465 	size_t blob_entry_num = blob_sz / sizeof(*blob_entry);
466 	struct layout_tracker_blob_entry *blob_entry_end = blob_entry + blob_entry_num;
467 
468 	if (blob_sz % sizeof(*blob_entry) != 0) {
469 		/* Invalid blob size */
470 		return -1;
471 	}
472 
473 	/* Free the current MD layout tracking info */
474 	layout_tracker_free_entries(tracker);
475 
476 	/* Reinit MD layout tracking info */
477 	if (layout_tracker_init_entries(tracker, tracker->bdev_blks)) {
478 		return -1;
479 	}
480 
481 	for (; blob_entry < blob_entry_end; blob_entry++) {
482 		/* Verify the type */
483 		if (blob_entry->type == FTL_LAYOUT_REGION_TYPE_FREE) {
484 			return -1;
485 		}
486 
487 		/* Load the entry */
488 		if (!ftl_layout_tracker_bdev_insert_region(tracker, blob_entry->type, blob_entry->ver,
489 				blob_entry->blk_offs, blob_entry->blk_sz)) {
490 			return -1;
491 		}
492 	}
493 
494 	return 0;
495 }
496