14  * struct iova_bitmap_map - A bitmap representing an IOVA range
16  * Main data structure for tracking mapped user pages of bitmap data.
24  * The user does not need to exact location of the bits in the bitmap.
26  * records the IOVA *range* in the bitmap by setting the corresponding
29  * The bitmap is an array of u64 whereas each bit represents an IOVA of
30  * range of (1 << pgshift). Thus formula for the bitmap data to be set is:
47 	/* pinned pages representing the bitmap data */
52  * struct iova_bitmap - The IOVA bitmap object
54  * Main data structure for iterating over the bitmap data.
57  * It uses a windowing scheme and pins the bitmap in relatively
60  * The bitmap object uses one base page to store all the pinned pages
61  * pointers related to the bitmap. For sizeof(struct page*) == 8 it stores
63  * 2M of bitmap data is pinned at a time. If the iova_bitmap page size is
72  * An example of the APIs on how to use/iterate over the IOVA bitmap:
74  *   bitmap = iova_bitmap_alloc(iova, length, page_size, data);
75  *   if (IS_ERR(bitmap))
76  *       return PTR_ERR(bitmap);
78  *   ret = iova_bitmap_for_each(bitmap, arg, dirty_reporter_fn);
80  *   iova_bitmap_free(bitmap);
87  *   iova_bitmap_set(bitmap, iova, iova_length);
90  * which u64 word of the bitmap is mapped, up to @mapped_total_index.
94  * The IOVA bitmap is usually located on what tracks DMA mapped ranges or
96  * bitmap.
99 	/* IOVA range representing the currently mapped bitmap data */
102 	/* userspace address of the bitmap */
103 	u8 __user *bitmap;  member
111 	/* base IOVA of the whole bitmap */
114 	/* length of the IOVA range for the whole bitmap */
122  * Converts a relative IOVA to a bitmap index.
123  * This function provides the index into the u64 array (bitmap::bitmap)
125  * Relative IOVA means relative to the bitmap::mapped base IOVA
130 static unsigned long iova_bitmap_offset_to_index(struct iova_bitmap *bitmap,  in iova_bitmap_offset_to_index()  argument
133 	unsigned long pgsize = 1 << bitmap->mapped.pgshift;  in iova_bitmap_offset_to_index()
135 	return iova / (BITS_PER_TYPE(*bitmap->bitmap) * pgsize);  in iova_bitmap_offset_to_index()
139  * Converts a bitmap index to a *relative* IOVA.
141 static unsigned long iova_bitmap_index_to_offset(struct iova_bitmap *bitmap,  in iova_bitmap_index_to_offset()  argument
144 	unsigned long pgshift = bitmap->mapped.pgshift;  in iova_bitmap_index_to_offset()
146 	return (index * BITS_PER_TYPE(*bitmap->bitmap)) << pgshift;  in iova_bitmap_index_to_offset()
152 static unsigned long iova_bitmap_mapped_iova(struct iova_bitmap *bitmap)  in iova_bitmap_mapped_iova()  argument
154 	unsigned long skip = bitmap->mapped_base_index;  in iova_bitmap_mapped_iova()
156 	return bitmap->iova + iova_bitmap_index_to_offset(bitmap, skip);  in iova_bitmap_mapped_iova()
160  * Pins the bitmap user pages for the current range window.
161  * This is internal to IOVA bitmap and called when advancing the
162  * index (@mapped_base_index) or allocating the bitmap.
164 static int iova_bitmap_get(struct iova_bitmap *bitmap)  in iova_bitmap_get()  argument
166 	struct iova_bitmap_map *mapped = &bitmap->mapped;  in iova_bitmap_get()
177 	npages = DIV_ROUND_UP((bitmap->mapped_total_index -  in iova_bitmap_get()
178 			       bitmap->mapped_base_index) *  in iova_bitmap_get()
179 			       sizeof(*bitmap->bitmap), PAGE_SIZE);  in iova_bitmap_get()
182 	 * Bitmap address to be pinned is calculated via pointer arithmetic  in iova_bitmap_get()
183 	 * with bitmap u64 word index.  in iova_bitmap_get()
185 	addr = bitmap->bitmap + bitmap->mapped_base_index;  in iova_bitmap_get()
189 	 * This is, for example, on x86 means 2M of bitmap data max.  in iova_bitmap_get()
201 	mapped->iova = iova_bitmap_mapped_iova(bitmap);  in iova_bitmap_get()
205 	 * This handles the case where the bitmap is not PAGE_SIZE  in iova_bitmap_get()
213  * Unpins the bitmap user pages and clears @npages
215  * the index or freeing the bitmap.
217 static void iova_bitmap_put(struct iova_bitmap *bitmap)  in iova_bitmap_put()  argument
219 	struct iova_bitmap_map *mapped = &bitmap->mapped;  in iova_bitmap_put()
228  * iova_bitmap_alloc() - Allocates an IOVA bitmap object
231  * @page_size: Page size of the IOVA bitmap. It defines what each bit
233  * @data: Userspace address of the bitmap
245 	struct iova_bitmap *bitmap;  in iova_bitmap_alloc()  local
248 	bitmap = kzalloc(sizeof(*bitmap), GFP_KERNEL);  in iova_bitmap_alloc()
249 	if (!bitmap)  in iova_bitmap_alloc()
252 	mapped = &bitmap->mapped;  in iova_bitmap_alloc()
254 	bitmap->bitmap = (u8 __user *)data;  in iova_bitmap_alloc()
255 	bitmap->mapped_total_index =  in iova_bitmap_alloc()
256 		iova_bitmap_offset_to_index(bitmap, length - 1) + 1;  in iova_bitmap_alloc()
257 	bitmap->iova = iova;  in iova_bitmap_alloc()
258 	bitmap->length = length;  in iova_bitmap_alloc()
266 	rc = iova_bitmap_get(bitmap);  in iova_bitmap_alloc()
269 	return bitmap;  in iova_bitmap_alloc()
272 	iova_bitmap_free(bitmap);  in iova_bitmap_alloc()
278  * iova_bitmap_free() - Frees an IOVA bitmap object
279  * @bitmap: IOVA bitmap to free
284 void iova_bitmap_free(struct iova_bitmap *bitmap)  in iova_bitmap_free()  argument
286 	struct iova_bitmap_map *mapped = &bitmap->mapped;  in iova_bitmap_free()
288 	iova_bitmap_put(bitmap);  in iova_bitmap_free()
295 	kfree(bitmap);  in iova_bitmap_free()
300  * Returns the remaining bitmap indexes from mapped_total_index to process for
301  * the currently pinned bitmap pages.
303 static unsigned long iova_bitmap_mapped_remaining(struct iova_bitmap *bitmap)  in iova_bitmap_mapped_remaining()  argument
307 	bytes = (bitmap->mapped.npages << PAGE_SHIFT) - bitmap->mapped.pgoff;  in iova_bitmap_mapped_remaining()
309 	remaining = bitmap->mapped_total_index - bitmap->mapped_base_index;  in iova_bitmap_mapped_remaining()
311 			  DIV_ROUND_UP(bytes, sizeof(*bitmap->bitmap)));  in iova_bitmap_mapped_remaining()
319 static unsigned long iova_bitmap_mapped_length(struct iova_bitmap *bitmap)  in iova_bitmap_mapped_length()  argument
321 	unsigned long max_iova = bitmap->iova + bitmap->length - 1;  in iova_bitmap_mapped_length()
322 	unsigned long iova = iova_bitmap_mapped_iova(bitmap);  in iova_bitmap_mapped_length()
327 	 * when converted to IOVA gives us a max length that the bitmap  in iova_bitmap_mapped_length()
329 	 * only cover the IOVA range in @bitmap::iova .. @bitmap::length.  in iova_bitmap_mapped_length()
331 	remaining = iova_bitmap_index_to_offset(bitmap,  in iova_bitmap_mapped_length()
332 			iova_bitmap_mapped_remaining(bitmap));  in iova_bitmap_mapped_length()
343 static bool iova_bitmap_done(struct iova_bitmap *bitmap)  in iova_bitmap_done()  argument
345 	return bitmap->mapped_base_index >= bitmap->mapped_total_index;  in iova_bitmap_done()
348 static int iova_bitmap_set_ahead(struct iova_bitmap *bitmap,  in iova_bitmap_set_ahead()  argument
353 	while (set_ahead_length > 0 && !iova_bitmap_done(bitmap)) {  in iova_bitmap_set_ahead()
354 		unsigned long length = iova_bitmap_mapped_length(bitmap);  in iova_bitmap_set_ahead()
355 		unsigned long iova = iova_bitmap_mapped_iova(bitmap);  in iova_bitmap_set_ahead()
357 		ret = iova_bitmap_get(bitmap);  in iova_bitmap_set_ahead()
362 		iova_bitmap_set(bitmap, iova, length);  in iova_bitmap_set_ahead()
365 		bitmap->mapped_base_index +=  in iova_bitmap_set_ahead()
366 			iova_bitmap_offset_to_index(bitmap, length - 1) + 1;  in iova_bitmap_set_ahead()
367 		iova_bitmap_put(bitmap);  in iova_bitmap_set_ahead()
370 	bitmap->set_ahead_length = 0;  in iova_bitmap_set_ahead()
376  * pages and pins the next set of bitmap pages.
379 static int iova_bitmap_advance(struct iova_bitmap *bitmap)  in iova_bitmap_advance()  argument
381 	unsigned long iova = iova_bitmap_mapped_length(bitmap) - 1;  in iova_bitmap_advance()
382 	unsigned long count = iova_bitmap_offset_to_index(bitmap, iova) + 1;  in iova_bitmap_advance()
384 	bitmap->mapped_base_index += count;  in iova_bitmap_advance()
386 	iova_bitmap_put(bitmap);  in iova_bitmap_advance()
387 	if (iova_bitmap_done(bitmap))  in iova_bitmap_advance()
391 	if (bitmap->set_ahead_length) {  in iova_bitmap_advance()
394 		ret = iova_bitmap_set_ahead(bitmap, bitmap->set_ahead_length);  in iova_bitmap_advance()
399 	/* When advancing the index we pin the next set of bitmap pages */  in iova_bitmap_advance()
400 	return iova_bitmap_get(bitmap);  in iova_bitmap_advance()
404  * iova_bitmap_for_each() - Iterates over the bitmap
405  * @bitmap: IOVA bitmap to iterate
409  * Helper function to iterate over bitmap data representing a portion of IOVA
411  * mapped bitmap user pages into IOVA ranges to process.
416 int iova_bitmap_for_each(struct iova_bitmap *bitmap, void *opaque,  in iova_bitmap_for_each()  argument
421 	for (; !iova_bitmap_done(bitmap) && !ret;  in iova_bitmap_for_each()
422 	     ret = iova_bitmap_advance(bitmap)) {  in iova_bitmap_for_each()
423 		ret = fn(bitmap, iova_bitmap_mapped_iova(bitmap),  in iova_bitmap_for_each()
424 			 iova_bitmap_mapped_length(bitmap), opaque);  in iova_bitmap_for_each()
434  * iova_bitmap_set() - Records an IOVA range in bitmap
435  * @bitmap: IOVA bitmap
440  * the user bitmap.
443 void iova_bitmap_set(struct iova_bitmap *bitmap,  in iova_bitmap_set()  argument
446 	struct iova_bitmap_map *mapped = &bitmap->mapped;  in iova_bitmap_set()
470 		bitmap->set_ahead_length =  in iova_bitmap_set()
471 			((last_bit - cur_bit + 1) << bitmap->mapped.pgshift);  in iova_bitmap_set()