1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (c) 2022, Oracle and/or its affiliates. 4 * Copyright (c) 2022, NVIDIA CORPORATION & AFFILIATES. All rights reserved 5 */ 6 #include <linux/iova_bitmap.h> 7 #include <linux/mm.h> 8 #include <linux/highmem.h> 9 10 #define BITS_PER_PAGE (PAGE_SIZE * BITS_PER_BYTE) 11 12 /* 13 * struct iova_bitmap_map - A bitmap representing an IOVA range 14 * 15 * Main data structure for tracking mapped user pages of bitmap data. 16 * 17 * For example, for something recording dirty IOVAs, it will be provided a 18 * struct iova_bitmap structure, as a general structure for iterating the 19 * total IOVA range. The struct iova_bitmap_map, though, represents the 20 * subset of said IOVA space that is pinned by its parent structure (struct 21 * iova_bitmap). 22 * 23 * The user does not need to exact location of the bits in the bitmap. 24 * From user perspective the only API available is iova_bitmap_set() which 25 * records the IOVA *range* in the bitmap by setting the corresponding 26 * bits. 27 * 28 * The bitmap is an array of u64 whereas each bit represents an IOVA of 29 * range of (1 << pgshift). Thus formula for the bitmap data to be set is: 30 * 31 * data[(iova / page_size) / 64] & (1ULL << (iova % 64)) 32 */ 33 struct iova_bitmap_map { 34 /* base IOVA representing bit 0 of the first page */ 35 unsigned long iova; 36 37 /* page size order that each bit granules to */ 38 unsigned long pgshift; 39 40 /* page offset of the first user page pinned */ 41 unsigned long pgoff; 42 43 /* number of pages pinned */ 44 unsigned long npages; 45 46 /* pinned pages representing the bitmap data */ 47 struct page **pages; 48 }; 49 50 /* 51 * struct iova_bitmap - The IOVA bitmap object 52 * 53 * Main data structure for iterating over the bitmap data. 54 * 55 * Abstracts the pinning work and iterates in IOVA ranges. 56 * It uses a windowing scheme and pins the bitmap in relatively 57 * big ranges e.g. 58 * 59 * The bitmap object uses one base page to store all the pinned pages 60 * pointers related to the bitmap. For sizeof(struct page*) == 8 it stores 61 * 512 struct page pointers which, if the base page size is 4K, it means 62 * 2M of bitmap data is pinned at a time. If the iova_bitmap page size is 63 * also 4K then the range window to iterate is 64G. 64 * 65 * For example iterating on a total IOVA range of 4G..128G, it will walk 66 * through this set of ranges: 67 * 68 * 4G - 68G-1 (64G) 69 * 68G - 128G-1 (64G) 70 * 71 * An example of the APIs on how to use/iterate over the IOVA bitmap: 72 * 73 * bitmap = iova_bitmap_alloc(iova, length, page_size, data); 74 * if (IS_ERR(bitmap)) 75 * return PTR_ERR(bitmap); 76 * 77 * ret = iova_bitmap_for_each(bitmap, arg, dirty_reporter_fn); 78 * 79 * iova_bitmap_free(bitmap); 80 * 81 * Each iteration of the @dirty_reporter_fn is called with a unique @iova 82 * and @length argument, indicating the current range available through the 83 * iova_bitmap. The @dirty_reporter_fn uses iova_bitmap_set() to mark dirty 84 * areas (@iova_length) within that provided range, as following: 85 * 86 * iova_bitmap_set(bitmap, iova, iova_length); 87 * 88 * The internals of the object uses an index @mapped_base_index that indexes 89 * which u64 word of the bitmap is mapped, up to @mapped_total_index. 90 * Those keep being incremented until @mapped_total_index is reached while 91 * mapping up to PAGE_SIZE / sizeof(struct page*) maximum of pages. 92 * 93 * The IOVA bitmap is usually located on what tracks DMA mapped ranges or 94 * some form of IOVA range tracking that co-relates to the user passed 95 * bitmap. 96 */ 97 struct iova_bitmap { 98 /* IOVA range representing the currently mapped bitmap data */ 99 struct iova_bitmap_map mapped; 100 101 /* userspace address of the bitmap */ 102 u64 __user *bitmap; 103 104 /* u64 index that @mapped points to */ 105 unsigned long mapped_base_index; 106 107 /* how many u64 can we walk in total */ 108 unsigned long mapped_total_index; 109 110 /* base IOVA of the whole bitmap */ 111 unsigned long iova; 112 113 /* length of the IOVA range for the whole bitmap */ 114 size_t length; 115 }; 116 117 /* 118 * Converts a relative IOVA to a bitmap index. 119 * This function provides the index into the u64 array (bitmap::bitmap) 120 * for a given IOVA offset. 121 * Relative IOVA means relative to the bitmap::mapped base IOVA 122 * (stored in mapped::iova). All computations in this file are done using 123 * relative IOVAs and thus avoid an extra subtraction against mapped::iova. 124 * The user API iova_bitmap_set() always uses a regular absolute IOVAs. 125 */ 126 static unsigned long iova_bitmap_offset_to_index(struct iova_bitmap *bitmap, 127 unsigned long iova) 128 { 129 unsigned long pgsize = 1 << bitmap->mapped.pgshift; 130 131 return iova / (BITS_PER_TYPE(*bitmap->bitmap) * pgsize); 132 } 133 134 /* 135 * Converts a bitmap index to a *relative* IOVA. 136 */ 137 static unsigned long iova_bitmap_index_to_offset(struct iova_bitmap *bitmap, 138 unsigned long index) 139 { 140 unsigned long pgshift = bitmap->mapped.pgshift; 141 142 return (index * BITS_PER_TYPE(*bitmap->bitmap)) << pgshift; 143 } 144 145 /* 146 * Returns the base IOVA of the mapped range. 147 */ 148 static unsigned long iova_bitmap_mapped_iova(struct iova_bitmap *bitmap) 149 { 150 unsigned long skip = bitmap->mapped_base_index; 151 152 return bitmap->iova + iova_bitmap_index_to_offset(bitmap, skip); 153 } 154 155 /* 156 * Pins the bitmap user pages for the current range window. 157 * This is internal to IOVA bitmap and called when advancing the 158 * index (@mapped_base_index) or allocating the bitmap. 159 */ 160 static int iova_bitmap_get(struct iova_bitmap *bitmap) 161 { 162 struct iova_bitmap_map *mapped = &bitmap->mapped; 163 unsigned long npages; 164 u64 __user *addr; 165 long ret; 166 167 /* 168 * @mapped_base_index is the index of the currently mapped u64 words 169 * that we have access. Anything before @mapped_base_index is not 170 * mapped. The range @mapped_base_index .. @mapped_total_index-1 is 171 * mapped but capped at a maximum number of pages. 172 */ 173 npages = DIV_ROUND_UP((bitmap->mapped_total_index - 174 bitmap->mapped_base_index) * 175 sizeof(*bitmap->bitmap), PAGE_SIZE); 176 177 /* 178 * We always cap at max number of 'struct page' a base page can fit. 179 * This is, for example, on x86 means 2M of bitmap data max. 180 */ 181 npages = min(npages, PAGE_SIZE / sizeof(struct page *)); 182 183 /* 184 * Bitmap address to be pinned is calculated via pointer arithmetic 185 * with bitmap u64 word index. 186 */ 187 addr = bitmap->bitmap + bitmap->mapped_base_index; 188 189 ret = pin_user_pages_fast((unsigned long)addr, npages, 190 FOLL_WRITE, mapped->pages); 191 if (ret <= 0) 192 return -EFAULT; 193 194 mapped->npages = (unsigned long)ret; 195 /* Base IOVA where @pages point to i.e. bit 0 of the first page */ 196 mapped->iova = iova_bitmap_mapped_iova(bitmap); 197 198 /* 199 * offset of the page where pinned pages bit 0 is located. 200 * This handles the case where the bitmap is not PAGE_SIZE 201 * aligned. 202 */ 203 mapped->pgoff = offset_in_page(addr); 204 return 0; 205 } 206 207 /* 208 * Unpins the bitmap user pages and clears @npages 209 * (un)pinning is abstracted from API user and it's done when advancing 210 * the index or freeing the bitmap. 211 */ 212 static void iova_bitmap_put(struct iova_bitmap *bitmap) 213 { 214 struct iova_bitmap_map *mapped = &bitmap->mapped; 215 216 if (mapped->npages) { 217 unpin_user_pages(mapped->pages, mapped->npages); 218 mapped->npages = 0; 219 } 220 } 221 222 /** 223 * iova_bitmap_alloc() - Allocates an IOVA bitmap object 224 * @iova: Start address of the IOVA range 225 * @length: Length of the IOVA range 226 * @page_size: Page size of the IOVA bitmap. It defines what each bit 227 * granularity represents 228 * @data: Userspace address of the bitmap 229 * 230 * Allocates an IOVA object and initializes all its fields including the 231 * first user pages of @data. 232 * 233 * Return: A pointer to a newly allocated struct iova_bitmap 234 * or ERR_PTR() on error. 235 */ 236 struct iova_bitmap *iova_bitmap_alloc(unsigned long iova, size_t length, 237 unsigned long page_size, u64 __user *data) 238 { 239 struct iova_bitmap_map *mapped; 240 struct iova_bitmap *bitmap; 241 int rc; 242 243 bitmap = kzalloc(sizeof(*bitmap), GFP_KERNEL); 244 if (!bitmap) 245 return ERR_PTR(-ENOMEM); 246 247 mapped = &bitmap->mapped; 248 mapped->pgshift = __ffs(page_size); 249 bitmap->bitmap = data; 250 bitmap->mapped_total_index = 251 iova_bitmap_offset_to_index(bitmap, length - 1) + 1; 252 bitmap->iova = iova; 253 bitmap->length = length; 254 mapped->iova = iova; 255 mapped->pages = (struct page **)__get_free_page(GFP_KERNEL); 256 if (!mapped->pages) { 257 rc = -ENOMEM; 258 goto err; 259 } 260 261 rc = iova_bitmap_get(bitmap); 262 if (rc) 263 goto err; 264 return bitmap; 265 266 err: 267 iova_bitmap_free(bitmap); 268 return ERR_PTR(rc); 269 } 270 271 /** 272 * iova_bitmap_free() - Frees an IOVA bitmap object 273 * @bitmap: IOVA bitmap to free 274 * 275 * It unpins and releases pages array memory and clears any leftover 276 * state. 277 */ 278 void iova_bitmap_free(struct iova_bitmap *bitmap) 279 { 280 struct iova_bitmap_map *mapped = &bitmap->mapped; 281 282 iova_bitmap_put(bitmap); 283 284 if (mapped->pages) { 285 free_page((unsigned long)mapped->pages); 286 mapped->pages = NULL; 287 } 288 289 kfree(bitmap); 290 } 291 292 /* 293 * Returns the remaining bitmap indexes from mapped_total_index to process for 294 * the currently pinned bitmap pages. 295 */ 296 static unsigned long iova_bitmap_mapped_remaining(struct iova_bitmap *bitmap) 297 { 298 unsigned long remaining; 299 300 remaining = bitmap->mapped_total_index - bitmap->mapped_base_index; 301 remaining = min_t(unsigned long, remaining, 302 (bitmap->mapped.npages << PAGE_SHIFT) / sizeof(*bitmap->bitmap)); 303 304 return remaining; 305 } 306 307 /* 308 * Returns the length of the mapped IOVA range. 309 */ 310 static unsigned long iova_bitmap_mapped_length(struct iova_bitmap *bitmap) 311 { 312 unsigned long max_iova = bitmap->iova + bitmap->length - 1; 313 unsigned long iova = iova_bitmap_mapped_iova(bitmap); 314 unsigned long remaining; 315 316 /* 317 * iova_bitmap_mapped_remaining() returns a number of indexes which 318 * when converted to IOVA gives us a max length that the bitmap 319 * pinned data can cover. Afterwards, that is capped to 320 * only cover the IOVA range in @bitmap::iova .. @bitmap::length. 321 */ 322 remaining = iova_bitmap_index_to_offset(bitmap, 323 iova_bitmap_mapped_remaining(bitmap)); 324 325 if (iova + remaining - 1 > max_iova) 326 remaining -= ((iova + remaining - 1) - max_iova); 327 328 return remaining; 329 } 330 331 /* 332 * Returns true if there's not more data to iterate. 333 */ 334 static bool iova_bitmap_done(struct iova_bitmap *bitmap) 335 { 336 return bitmap->mapped_base_index >= bitmap->mapped_total_index; 337 } 338 339 /* 340 * Advances to the next range, releases the current pinned 341 * pages and pins the next set of bitmap pages. 342 * Returns 0 on success or otherwise errno. 343 */ 344 static int iova_bitmap_advance(struct iova_bitmap *bitmap) 345 { 346 unsigned long iova = iova_bitmap_mapped_length(bitmap) - 1; 347 unsigned long count = iova_bitmap_offset_to_index(bitmap, iova) + 1; 348 349 bitmap->mapped_base_index += count; 350 351 iova_bitmap_put(bitmap); 352 if (iova_bitmap_done(bitmap)) 353 return 0; 354 355 /* When advancing the index we pin the next set of bitmap pages */ 356 return iova_bitmap_get(bitmap); 357 } 358 359 /** 360 * iova_bitmap_for_each() - Iterates over the bitmap 361 * @bitmap: IOVA bitmap to iterate 362 * @opaque: Additional argument to pass to the callback 363 * @fn: Function that gets called for each IOVA range 364 * 365 * Helper function to iterate over bitmap data representing a portion of IOVA 366 * space. It hides the complexity of iterating bitmaps and translating the 367 * mapped bitmap user pages into IOVA ranges to process. 368 * 369 * Return: 0 on success, and an error on failure either upon 370 * iteration or when the callback returns an error. 371 */ 372 int iova_bitmap_for_each(struct iova_bitmap *bitmap, void *opaque, 373 iova_bitmap_fn_t fn) 374 { 375 int ret = 0; 376 377 for (; !iova_bitmap_done(bitmap) && !ret; 378 ret = iova_bitmap_advance(bitmap)) { 379 ret = fn(bitmap, iova_bitmap_mapped_iova(bitmap), 380 iova_bitmap_mapped_length(bitmap), opaque); 381 if (ret) 382 break; 383 } 384 385 return ret; 386 } 387 388 /** 389 * iova_bitmap_set() - Records an IOVA range in bitmap 390 * @bitmap: IOVA bitmap 391 * @iova: IOVA to start 392 * @length: IOVA range length 393 * 394 * Set the bits corresponding to the range [iova .. iova+length-1] in 395 * the user bitmap. 396 * 397 * Return: The number of bits set. 398 */ 399 void iova_bitmap_set(struct iova_bitmap *bitmap, 400 unsigned long iova, size_t length) 401 { 402 struct iova_bitmap_map *mapped = &bitmap->mapped; 403 unsigned long offset = (iova - mapped->iova) >> mapped->pgshift; 404 unsigned long nbits = max_t(unsigned long, 1, length >> mapped->pgshift); 405 unsigned long page_idx = offset / BITS_PER_PAGE; 406 unsigned long page_offset = mapped->pgoff; 407 void *kaddr; 408 409 offset = offset % BITS_PER_PAGE; 410 411 do { 412 unsigned long size = min(BITS_PER_PAGE - offset, nbits); 413 414 kaddr = kmap_local_page(mapped->pages[page_idx]); 415 bitmap_set(kaddr + page_offset, offset, size); 416 kunmap_local(kaddr); 417 page_offset = offset = 0; 418 nbits -= size; 419 page_idx++; 420 } while (nbits > 0); 421 } 422 EXPORT_SYMBOL_GPL(iova_bitmap_set); 423