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 ftl_layout_tracker_bdev * 22 ftl_layout_tracker_bdev_init(uint64_t bdev_blks) 23 { 24 struct ftl_layout_tracker_bdev *tracker = calloc(1, sizeof(*tracker)); 25 struct layout_tracker_entry *entry_free; 26 27 if (!tracker) { 28 return NULL; 29 } 30 31 entry_free = calloc(1, sizeof(*entry_free)); 32 if (!entry_free) { 33 free(tracker); 34 return NULL; 35 } 36 37 tracker->bdev_blks = bdev_blks; 38 tracker->regs_cnt = 1; 39 TAILQ_INIT(&tracker->layout_head); 40 41 entry_free->reg.blk_sz = bdev_blks; 42 entry_free->reg.type = FTL_LAYOUT_REGION_TYPE_FREE; 43 44 TAILQ_INSERT_HEAD(&tracker->layout_head, entry_free, layout_entry); 45 46 return tracker; 47 } 48 49 void 50 ftl_layout_tracker_bdev_fini(struct ftl_layout_tracker_bdev *tracker) 51 { 52 struct layout_tracker_entry *entry; 53 54 assert(tracker); 55 56 while ((entry = TAILQ_FIRST(&tracker->layout_head))) { 57 TAILQ_REMOVE(&tracker->layout_head, entry, layout_entry); 58 free(entry); 59 } 60 61 free(tracker); 62 } 63 64 static struct layout_tracker_entry * 65 layout_region_find_min_free(struct ftl_layout_tracker_bdev *tracker, uint64_t blk_sz, 66 uint64_t blk_align) 67 { 68 struct layout_tracker_entry *min_free_entry = NULL; 69 struct layout_tracker_entry *entry; 70 71 assert(tracker); 72 73 TAILQ_FOREACH(entry, &tracker->layout_head, layout_entry) { 74 uint64_t align_offs, align_sz; 75 76 if (entry->reg.type != FTL_LAYOUT_REGION_TYPE_FREE) { 77 continue; 78 } 79 80 align_offs = entry->reg.blk_offs; 81 align_sz = entry->reg.blk_sz; 82 if (blk_align) { 83 align_offs = SPDK_ALIGN_CEIL(align_offs, blk_align); 84 align_sz -= (align_offs - entry->reg.blk_offs); 85 } 86 87 if (align_sz >= blk_sz) { 88 if (!min_free_entry || min_free_entry->reg.blk_sz > entry->reg.blk_sz) { 89 min_free_entry = entry; 90 } 91 } 92 } 93 94 return min_free_entry; 95 } 96 97 static struct layout_tracker_entry * 98 layout_region_find_from(struct ftl_layout_tracker_bdev *tracker, 99 enum ftl_layout_region_type reg_type, 100 uint32_t reg_ver, struct layout_tracker_entry *entry) 101 { 102 assert(tracker); 103 104 TAILQ_FOREACH_FROM(entry, &tracker->layout_head, layout_entry) { 105 if ((entry->reg.type == reg_type || reg_type == FTL_LAYOUT_REGION_TYPE_INVALID) 106 && (entry->reg.ver == reg_ver || reg_ver == REG_VER_ANY)) { 107 return entry; 108 } 109 } 110 111 return NULL; 112 } 113 114 static struct layout_tracker_entry * 115 layout_region_find_first(struct ftl_layout_tracker_bdev *tracker, 116 enum ftl_layout_region_type reg_type, 117 uint32_t reg_ver) 118 { 119 return layout_region_find_from(tracker, reg_type, reg_ver, TAILQ_FIRST(&tracker->layout_head)); 120 } 121 122 static struct layout_tracker_entry * 123 layout_region_find_next(struct ftl_layout_tracker_bdev *tracker, 124 enum ftl_layout_region_type reg_type, 125 uint32_t reg_ver, struct layout_tracker_entry *entry) 126 { 127 if ((entry = TAILQ_NEXT(entry, layout_entry))) { 128 return layout_region_find_from(tracker, reg_type, reg_ver, entry); 129 } 130 return NULL; 131 } 132 133 const struct ftl_layout_tracker_bdev_region_props * 134 ftl_layout_tracker_bdev_add_region(struct ftl_layout_tracker_bdev *tracker, 135 enum ftl_layout_region_type reg_type, uint32_t reg_ver, uint64_t blk_sz, uint64_t blk_align) 136 { 137 struct layout_tracker_entry *entry_free; 138 struct layout_tracker_entry *entry_new; 139 uint64_t entry_free_blks_left; 140 141 assert(tracker); 142 assert(reg_type < FTL_LAYOUT_REGION_TYPE_MAX); 143 144 entry_new = layout_region_find_first(tracker, reg_type, reg_ver); 145 if (entry_new) { 146 /* Region already exists */ 147 return NULL; 148 } 149 150 entry_free = layout_region_find_min_free(tracker, blk_sz, blk_align); 151 if (!entry_free) { 152 /* No free space */ 153 return NULL; 154 } 155 156 /* Takce care of the alignment */ 157 if (blk_align) { 158 /* Calculate the aligned region's offs and size */ 159 uint64_t align_offs = SPDK_ALIGN_CEIL(entry_free->reg.blk_offs, blk_align); 160 assert(align_offs >= entry_free->reg.blk_offs); 161 162 /* Subdivide the free region in two: unaligned free region, followed by the aligned free region */ 163 if (align_offs > entry_free->reg.blk_offs) { 164 uint64_t unaligned_sz = align_offs - entry_free->reg.blk_offs; 165 166 /* Setup the unaligned region */ 167 entry_new = calloc(1, sizeof(*entry_new)); 168 if (!entry_new) { 169 return NULL; 170 } 171 entry_new->reg = entry_free->reg; 172 entry_new->reg.blk_sz = unaligned_sz; 173 174 /* Setup the aligned region - shrink the free region found */ 175 entry_free->reg.blk_offs = align_offs; 176 entry_free->reg.blk_sz -= unaligned_sz; 177 178 /* Add the unaligned region prev to the aligned one */ 179 TAILQ_INSERT_BEFORE(entry_free, entry_new, layout_entry); 180 tracker->regs_cnt++; 181 } 182 } 183 184 entry_free_blks_left = entry_free->reg.blk_sz - blk_sz; 185 186 if (entry_free_blks_left) { 187 /* Subdivide the free region */ 188 entry_new = calloc(1, sizeof(*entry_new)); 189 if (!entry_new) { 190 return NULL; 191 } 192 193 /* Setup the new region at the beginning of the free region found */ 194 entry_new->reg.type = reg_type; 195 entry_new->reg.ver = reg_ver; 196 entry_new->reg.blk_offs = entry_free->reg.blk_offs; 197 entry_new->reg.blk_sz = blk_sz; 198 199 /* Shrink the free region found */ 200 entry_free->reg.blk_offs += blk_sz; 201 entry_free->reg.blk_sz = entry_free_blks_left; 202 203 /* Add the new region */ 204 TAILQ_INSERT_BEFORE(entry_free, entry_new, layout_entry); 205 tracker->regs_cnt++; 206 } else { 207 /* Setup the new region in place */ 208 entry_new = entry_free; 209 entry_new->reg.type = reg_type; 210 entry_new->reg.ver = reg_ver; 211 } 212 213 return &entry_new->reg; 214 } 215 216 int 217 ftl_layout_tracker_bdev_rm_region(struct ftl_layout_tracker_bdev *tracker, 218 enum ftl_layout_region_type reg_type, uint32_t reg_ver) 219 { 220 struct layout_tracker_entry *entry_rm, *entry_check __attribute__((unused)); 221 struct layout_tracker_entry *entry = layout_region_find_first(tracker, reg_type, reg_ver); 222 223 if (!entry) { 224 return -1; 225 } 226 227 /* Free the region */ 228 entry->reg.type = FTL_LAYOUT_REGION_TYPE_FREE; 229 entry->reg.ver = 0; 230 231 /* Join with the adjacent free region prev to the current region */ 232 entry_rm = TAILQ_PREV(entry, layout_tracker, layout_entry); 233 if (entry_rm && entry_rm->reg.type == FTL_LAYOUT_REGION_TYPE_FREE) { 234 TAILQ_REMOVE(&tracker->layout_head, entry_rm, layout_entry); 235 entry->reg.blk_offs = entry_rm->reg.blk_offs; 236 entry->reg.blk_sz += entry_rm->reg.blk_sz; 237 238 #if defined(DEBUG) 239 entry_check = TAILQ_PREV(entry, layout_tracker, layout_entry); 240 if (entry_check) { 241 assert(entry_check->reg.type != FTL_LAYOUT_REGION_TYPE_FREE); 242 } 243 #endif 244 245 free(entry_rm); 246 tracker->regs_cnt--; 247 } 248 249 /* Join with the adjacent free region next to the current region */ 250 entry_rm = TAILQ_NEXT(entry, layout_entry); 251 if (entry_rm && entry_rm->reg.type == FTL_LAYOUT_REGION_TYPE_FREE) { 252 TAILQ_REMOVE(&tracker->layout_head, entry_rm, layout_entry); 253 entry->reg.blk_sz += entry_rm->reg.blk_sz; 254 255 #if defined(DEBUG) 256 entry_check = TAILQ_NEXT(entry, layout_entry); 257 if (entry_check) { 258 assert(entry_check->reg.type != FTL_LAYOUT_REGION_TYPE_FREE); 259 } 260 #endif 261 free(entry_rm); 262 tracker->regs_cnt--; 263 } 264 265 return 0; 266 } 267 268 void 269 ftl_layout_tracker_bdev_find_next_region(struct ftl_layout_tracker_bdev *tracker, 270 enum ftl_layout_region_type reg_type, 271 const struct ftl_layout_tracker_bdev_region_props **search_ctx) 272 { 273 struct layout_tracker_entry *entry; 274 275 if (!search_ctx) { 276 return; 277 } 278 279 if (*search_ctx == NULL) { 280 /* Return the first region found */ 281 entry = layout_region_find_first(tracker, reg_type, REG_VER_ANY); 282 } else { 283 /* Find the next region */ 284 entry = SPDK_CONTAINEROF(*search_ctx, struct layout_tracker_entry, reg); 285 entry = layout_region_find_next(tracker, reg_type, REG_VER_ANY, entry); 286 } 287 *search_ctx = entry ? &entry->reg : NULL; 288 } 289