From ca66f606234198cbcff67431d6e722fd87a32727 Mon Sep 17 00:00:00 2001 From: William Henderson Date: Wed, 30 Aug 2023 13:55:13 +0000 Subject: refactor dirty page get Signed-off-by: William Henderson --- lib/dma.c | 284 ++++++++++++++++++++++++++++++++++---------------------------- lib/dma.h | 9 -- 2 files changed, 156 insertions(+), 137 deletions(-) diff --git a/lib/dma.c b/lib/dma.c index 1a73c7c..bde1226 100644 --- a/lib/dma.c +++ b/lib/dma.c @@ -537,6 +537,147 @@ log_dirty_bitmap(vfu_ctx_t *vfu_ctx, dma_memory_region_t *region, } #endif +static void +dirty_page_exchange(uint8_t *outp, uint8_t *bitmap) +{ + /* + * If no bits are dirty, avoid the atomic exchange. This is obviously + * racy, but it's OK: if we miss a dirty bit being set, we'll catch it + * the next time around. + * + * Otherwise, atomically exchange the dirty bits with zero: as we use + * atomic or in _dma_mark_dirty(), this cannot lose set bits - we might + * miss a bit being set after, but again, we'll catch that next time + * around. + */ + if (*bitmap == 0) { + *outp = 0; + } else { + uint8_t zero = 0; + __atomic_exchange(bitmap, &zero, outp, __ATOMIC_SEQ_CST); + } +} + +static void +dirty_page_get_same_pgsize(dma_memory_region_t *region, char *bitmap, + size_t bitmap_size) +{ + for (size_t i = 0; i < bitmap_size; i++) { + dirty_page_exchange((uint8_t *)&bitmap[i], ®ion->dirty_bitmap[i]); + } +} + +static void +dirty_page_get_extend(dma_memory_region_t *region, char *bitmap, + size_t server_bitmap_size, size_t server_pgsize, + size_t client_bitmap_size, size_t client_pgsize) +{ + /* + * The index of the bit in the client bitmap that we are currently + * considering. By keeping track of this separately to the for loop, we + * allow for one server bit to be repeated for multiple client bytes. + */ + uint8_t client_bit_idx = 0; + size_t server_byte_idx; + int server_bit_idx_into_byte; + size_t factor = server_pgsize / client_pgsize; + + /* + * Iterate through the bytes of the server bitmap. + */ + for (server_byte_idx = 0; server_byte_idx < server_bitmap_size; + server_byte_idx++) { + if (client_bit_idx / CHAR_BIT >= client_bitmap_size) { + break; + } + + uint8_t out = 0; + + dirty_page_exchange(&out, ®ion->dirty_bitmap[server_byte_idx]); + + /* + * Iterate through the bits of the server byte, repeating bits to reach + * the desired page size. + */ + for (server_bit_idx_into_byte = 0; + server_bit_idx_into_byte < CHAR_BIT; + server_bit_idx_into_byte++) { + uint8_t server_bit = (out >> server_bit_idx_into_byte) & 1; + + /* + * Repeat `factor` times the bit at index `j` of `out`. + * + * OR the same bit from the server bitmap (`server_bit`) with + * `factor` bits in the client bitmap, from `client_bit_idx` to + * `end_client_bit_idx`. + */ + size_t end_client_bit_idx = client_bit_idx + factor; + while (client_bit_idx < end_client_bit_idx) { + bitmap[client_bit_idx / CHAR_BIT] |= + server_bit << (client_bit_idx % CHAR_BIT); + client_bit_idx++; + } + } + } +} + +static void +dirty_page_get_combine(dma_memory_region_t *region, char *bitmap, + size_t server_bitmap_size, size_t server_pgsize, + size_t client_bitmap_size, size_t client_pgsize) +{ + /* + * The index of the bit in the client bitmap that we are currently + * considering. By keeping track of this separately to the for loop, we + * allow multiple bytes' worth of server bits to be OR'd together to + * calculate one client bit. + */ + uint8_t client_bit_idx = 0; + size_t server_byte_idx; + int server_bit_idx_into_byte; + size_t factor = client_pgsize / server_pgsize; + + /* + * Iterate through the bytes of the server bitmap. + */ + for (server_byte_idx = 0; server_byte_idx < server_bitmap_size; + server_byte_idx++) { + if (client_bit_idx / CHAR_BIT >= client_bitmap_size) { + break; + } + + uint8_t out = 0; + + dirty_page_exchange(&out, ®ion->dirty_bitmap[server_byte_idx]); + + /* + * Iterate through the bits of the server byte, combining bits to reach + * the desired page size. + */ + for (server_bit_idx_into_byte = 0; + server_bit_idx_into_byte < CHAR_BIT; + server_bit_idx_into_byte++) { + uint8_t server_bit = (out >> server_bit_idx_into_byte) & 1; + + /* + * OR `factor` bits of the server bitmap with the same bit at + * index `client_bit_idx` in the client bitmap. + */ + bitmap[client_bit_idx / CHAR_BIT] |= + server_bit << (client_bit_idx % CHAR_BIT); + + /* + * Only move onto the next bit in the client bitmap once we've + * OR'd `factor` bits. + */ + if (((server_byte_idx * CHAR_BIT) + server_bit_idx_into_byte) + % factor == factor - 1) { + client_bit_idx++; + } + } + } +} + int dma_controller_dirty_page_get(dma_controller_t *dma, vfu_dma_addr_t addr, uint64_t len, size_t pgsize, size_t size, @@ -589,7 +730,7 @@ dma_controller_dirty_page_get(dma_controller_t *dma, vfu_dma_addr_t addr, client_bitmap_size = get_bitmap_size(len, pgsize); if (client_bitmap_size < 0) { - vfu_log(dma->vfu_ctx, LOG_ERR, "failed to get client bitmap size"); + vfu_log(dma->vfu_ctx, LOG_ERR, "bad requested page size %ld", pgsize); return client_bitmap_size; } @@ -612,10 +753,21 @@ dma_controller_dirty_page_get(dma_controller_t *dma, vfu_dma_addr_t addr, if (pgsize == dma->dirty_pgsize) { dirty_page_get_same_pgsize(region, bitmap, client_bitmap_size); + } else if (pgsize < dma->dirty_pgsize) { + /* + * If the requested page size is less than that used for logging by + * the server, the bitmap will need to be extended, repeating bits. + */ + dirty_page_get_extend(region, bitmap, server_bitmap_size, + dma->dirty_pgsize, client_bitmap_size, pgsize); } else { - dirty_page_get_different_pgsize(region, bitmap, server_bitmap_size, - dma->dirty_pgsize, client_bitmap_size, - pgsize); + /* + * If the requested page size is larger than that used for logging by + * the server, the bitmap will need to combine bits with OR, losing + * accuracy. + */ + dirty_page_get_combine(region, bitmap, server_bitmap_size, + dma->dirty_pgsize, client_bitmap_size, pgsize); } #ifdef DEBUG @@ -625,128 +777,4 @@ dma_controller_dirty_page_get(dma_controller_t *dma, vfu_dma_addr_t addr, return 0; } -static void -dirty_page_exchange(uint8_t *outp, uint8_t *bitmap) -{ - /* - * If no bits are dirty, avoid the atomic exchange. This is obviously - * racy, but it's OK: if we miss a dirty bit being set, we'll catch it - * the next time around. - * - * Otherwise, atomically exchange the dirty bits with zero: as we use - * atomic or in _dma_mark_dirty(), this cannot lose set bits - we might - * miss a bit being set after, but again, we'll catch that next time - * around. - */ - if (*bitmap == 0) { - *outp = 0; - } else { - uint8_t zero = 0; - __atomic_exchange(bitmap, &zero, outp, __ATOMIC_SEQ_CST); - } -} - -void -dirty_page_get_same_pgsize(dma_memory_region_t *region, char *bitmap, - size_t bitmap_size) -{ - for (size_t i = 0; i < bitmap_size; i++) { - dirty_page_exchange((uint8_t *)&bitmap[i], ®ion->dirty_bitmap[i]); - } -} - -void -dirty_page_get_different_pgsize(dma_memory_region_t *region, char *bitmap, - size_t server_bitmap_size, size_t server_pgsize, - size_t client_bitmap_size, size_t client_pgsize) -{ - /* - * The index of the bit in the client bitmap that we are currently - * considering. By keeping track of this separately to the for loops, we - * allow for one server bit to be repeated for multiple client bytes, or - * multiple bytes' worth of server bits to be OR'd together to calculate one - * client bit. - */ - uint8_t client_bit_idx = 0; - /* - * The index of the byte in the server bitmap that we are currently - * considering. - */ - size_t server_byte_idx; - /* - * The index of the bit in the currently considered byte of the server - * bitmap that we are currently considering. - */ - int server_bit_idx_into_byte; - - /* - * Whether we are extending the server bitmap (repeating bits to - * generate a larger client bitmap) or not (combining bits with OR to - * generate a smaller client bitmap). - * - * If the server page size is greater than the client's requested page size, - * we will be extending. - */ - bool extend = server_pgsize >= client_pgsize; - /* - * If extending, the number of times to repeat each bit of the server - * bitmap. If not, the number of bits of the server bitmap to OR together to - * calculate one bit of the client bitmap. - */ - size_t factor = extend ? - server_pgsize / client_pgsize : client_pgsize / server_pgsize; - - /* - * Iterate through the bytes of the server bitmap. - */ - for (server_byte_idx = 0; server_byte_idx < server_bitmap_size && - client_bit_idx / CHAR_BIT < client_bitmap_size; server_byte_idx++) { - uint8_t out = 0; - - dirty_page_exchange(&out, ®ion->dirty_bitmap[server_byte_idx]); - - /* - * Iterate through the bits of the server byte, repeating or combining - * bits to reach the desired page size. - */ - for (server_bit_idx_into_byte = 0; - server_bit_idx_into_byte < CHAR_BIT; - server_bit_idx_into_byte++) { - uint8_t server_bit = (out >> server_bit_idx_into_byte) & 1; - - if (extend) { - /* - * Repeat `factor` times the bit at index `j` of `out`. - * - * OR the same bit from the server bitmap (`server_bit`) with - * `factor` bits in the client bitmap, from `client_bit_idx` to - * `end_client_bit_idx`. - */ - size_t end_client_bit_idx = client_bit_idx + factor; - while (client_bit_idx < end_client_bit_idx) { - bitmap[client_bit_idx / CHAR_BIT] |= - server_bit << (client_bit_idx % CHAR_BIT); - client_bit_idx++; - } - } else { - /* - * OR `factor` bits of the server bitmap with the same bit at - * index `client_bit_idx` in the client bitmap. - */ - bitmap[client_bit_idx / CHAR_BIT] |= - server_bit << (client_bit_idx % CHAR_BIT); - - /* - * Only move onto the next bit in the client bitmap once we've - * OR'd `factor` bits. - */ - if (((server_byte_idx * CHAR_BIT) + server_bit_idx_into_byte) - % factor == factor - 1) { - client_bit_idx++; - } - } - } - } -} - /* ex: set tabstop=4 shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/lib/dma.h b/lib/dma.h index eaa4052..789904f 100644 --- a/lib/dma.h +++ b/lib/dma.h @@ -387,15 +387,6 @@ dma_controller_dirty_page_get(dma_controller_t *dma, vfu_dma_addr_t addr, uint64_t len, size_t pgsize, size_t size, char *bitmap); -void -dirty_page_get_same_pgsize(dma_memory_region_t *region, char *bitmap, - size_t bitmap_size); -void -dirty_page_get_different_pgsize(dma_memory_region_t *region, char *bitmap, - size_t server_bitmap_size, size_t server_pgsize, - size_t client_bitmap_size, - size_t client_pgsize); - bool dma_sg_is_mappable(const dma_controller_t *dma, const dma_sg_t *sg); -- cgit v1.1