<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Apr 3, 2017 at 7:44 AM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net" target="_blank">jason@jlekstrand.net</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Apr 3, 2017 at 5:02 AM, Juan A. Suarez Romero <<a href="mailto:jasuarez@igalia.com" target="_blank">jasuarez@igalia.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Wed, 2017-03-29 at 12:06 -0700, Jason Ekstrand wrote: > Looking over the patch, I think I've convinced myself that it's correct. (I honestly wasn't expecting to come to that conclusion without more iteration.) That said, this raises some interesting questions. I added Kristian to the Cc in case he has any input. > > 1. Should we do powers of two or linear. I'm still a fan of powers of two. In which specific part do you mean? In free block lists? or in the allocator_new? </blockquote><div> </div><div>In the state pool, we just round all allocation sizes up to the nearest power-of-two, and then the index into the array of free lists isn't "size - base", it's "ilog2(size) - base". </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> > > 2. Should block pools even have a block size at all? We could just make every block pool allow any power-of-two size from 4 KiB up to. say, 1 MiB and then make the block size part of the state pool or stream that's allocating from it. At the moment, I like this idea, but I've given it very little thought. > So IIUC, the idea would be the block pool is just a flat chunk of memory, where we later fetch blocks of memory from, as requested by applications. Is that correct? </blockquote></div></div></div></blockquote><div> </div><div>Thinking about this again, I think your statement may have been more correct than I thought. If we make the state_stream chain off of a state_pool rather than the block_pool, we could make the block pool structure a simple bi-directional growing BO and trust in the state pool for 100% of the re-use. That would probably be a way simpler structure. For that matter, the state pool could just own the block_pool and setup/teardown would be easier. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"></blockquote><div>Sorry, but this patch gave me some sudden revelations and things are still in the process of reforming in my brain. In the past, we assumed a two-layered allocation strategy where we had a block pool which was the base and then the state pool and state stream allocators sat on top of it. Originally, the state pool allocator was just for a single size as well. </div><div>Now that the block pool is going to be capable of allocating multiple sizes, the whole mental model of the separation falls apart. The new future that I see is one where the block pool and state pool aren't separate. Instead, we have a single thing which I'll call state_pool (we have to pick one of the names) which lets you allocate a state of any size from 32B to 2MB. The state stream will then allocate off of a state_pool instead of a block_pool since they're now the same. For smaller states, we still want to allocate reasonably large chunks (probably 4K) so that we ensure that things are nicely aligned. I think I've got a pretty good idea of how it should work at this point and can write more if you'd like. </div><div>Before we dive in and do a pile of refactoring, I think this patch is pretty much good-to-go assuming we fix the power-of-two thing and it fixes a bug so let's focus there. Are you interested in doing the refactoring? If not, that's ok, I'm happy to do it and it wouldn't take me long now that I've gotten a chance to think about it. If you are interested, go for it! </div><div><div class="h5"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="m_6482888752956205086HOEnZb"><div class="m_6482888752956205086h5"> > 3. If we go with the idea in 2. should we still call it block_pool? I think we can keep the name but it doesn't it as well as it once did. > > Thanks for working on this! I'm sorry it's taken so long to respond. Every time I've looked at it, my brain hasn't been in the right state to think about lock-free code. :-/ > > On Wed, Mar 15, 2017 at 5:05 AM, Juan A. Suarez Romero <<a href="mailto:jasuarez@igalia.com" target="_blank">jasuarez@igalia.com</a>> wrote: > > Current Anv allocator assign memory in terms of a fixed block size. > > > > But there can be cases where this block is not enough for a memory > > request, and thus several blocks must be assigned in a row. > > > > This commit adds support for specifying how many blocks of memory must > > be assigned. > > > > This fixes a number dEQP-VK.pipeline.render_to_image.* tests that crash. > > > > v2: lock-free free-list is not handled correctly (Jason) > > --- > > src/intel/vulkan/anv_allocator.c | 81 +++++++++++++++++++++++++++----------- > > src/intel/vulkan/anv_batch_chain.c | 4 +- > > src/intel/vulkan/anv_private.h | 7 +++- > > 3 files changed, 66 insertions(+), 26 deletions(-) > > > > diff --git a/src/intel/vulkan/anv_allocator.c b/src/intel/vulkan/anv_allocator.c > > index 45c663b..3924551 100644 > > --- a/src/intel/vulkan/anv_allocator.c > > +++ b/src/intel/vulkan/anv_allocator.c > > @@ -257,7 +257,8 @@ anv_block_pool_init(struct anv_block_pool *pool, > > pool->device = device; > > anv_bo_init(&pool->bo, 0, 0); > > pool->block_size = block_size; > > - pool->free_list = ANV_FREE_LIST_EMPTY; > > + for (uint32_t i = 0; i < ANV_MAX_BLOCKS; i++) > > + pool->free_list[i] = ANV_FREE_LIST_EMPTY; > > pool->back_free_list = ANV_FREE_LIST_EMPTY; > > > > pool->fd = memfd_create("block pool", MFD_CLOEXEC); > > @@ -500,30 +501,35 @@ fail: > > > > static uint32_t > > anv_block_pool_alloc_new(struct anv_block_pool *pool, > > - struct anv_block_state *pool_state) > > + struct anv_block_state *pool_state, > > + uint32_t n_blocks) > > Maybe have this take a size rather than n_blocks? It's only ever called by stuff in the block pool so the caller can do the multiplication. It would certainly make some of the math below easier. > > > { > > struct anv_block_state state, old, new; > > > > while (1) { > > - state.u64 = __sync_fetch_and_add(&pool_state->u64, pool->block_size); > > - if (state.next < state.end) { > > + state.u64 = __sync_fetch_and_add(&pool_state->u64, n_blocks * pool->block_size); > > + if (state.next > state.end) { > > + futex_wait(&pool_state->end, state.end); > > + continue; > > + } else if ((state.next + (n_blocks - 1) * pool->block_size) < state.end) { > > First off, please keep the if's in the same order unless we have a reason to re-arrange them. It would make this way easier to review. :-) > > Second, I think this would be much easier to read as: > > if (state.next + size <= state.end) { > /* Success */ > } else if (state.next <= state.end) { > /* Our block is the one that crosses the line */ > } else { > /* Wait like everyone else */ > } > > > assert(pool->map); > > return state.next; > > - } else if (state.next == state.end) { > > - /* We allocated the first block outside the pool, we have to grow it. > > - * pool_state->next acts a mutex: threads who try to allocate now will > > - * get block indexes above the current limit and hit futex_wait > > - * below. */ > > - new.next = state.next + pool->block_size; > > + } else { > > + /* We allocated the firsts blocks outside the pool, we have to grow > > + * it. pool_state->next acts a mutex: threads who try to allocate > > + * now will get block indexes above the current limit and hit > > + * futex_wait below. > > + */ > > + new.next = state.next + n_blocks * pool->block_size; > > new.end = anv_block_pool_grow(pool, pool_state); > > + /* We assume that just growing once the pool is enough to fulfil the > > + * memory requirements > > + */ > > I think this is probably a reasonable assumption. That said, it wouldn't hurt to add a size parameter to block_pool_grow but I don't know that it's needed. > > > assert(new.end >= new.next && new.end % pool->block_size == 0); > > old.u64 = __sync_lock_test_and_set(&pool_state->u64, new.u64); > > if (old.next != state.next) > > futex_wake(&pool_state->end, INT_MAX); > > return state.next; > > - } else { > > - futex_wait(&pool_state->end, state.end); > > - continue; > > } > > } > > } > > @@ -531,16 +537,38 @@ anv_block_pool_alloc_new(struct anv_block_pool *pool, > > int32_t > > anv_block_pool_alloc(struct anv_block_pool *pool) > > { > > + return anv_block_pool_alloc_n(pool, 1); > > +} > > + > > +int32_t > > +anv_block_pool_alloc_n(struct anv_block_pool *pool, uint32_t n_blocks) > > +{ > > int32_t offset; > > > > + assert(n_blocks >= 1 && n_blocks <= ANV_MAX_BLOCKS); > > The more I look at this, the more I want it to be in powers of 2. > > > + > > /* Try free list first. */ > > - if (anv_free_list_pop(&pool->free_list, &pool->map, &offset)) { > > + if (anv_free_list_pop(&(pool->free_list[n_blocks - 1]), &pool->map, &offset)) { > > assert(offset >= 0); > > assert(pool->map); > > return offset; > > } > > > > - return anv_block_pool_alloc_new(pool, &pool->state); > > + /* Try to steal them. */ > > + for (unsigned int i = n_blocks; i < ANV_MAX_BLOCKS; i++) { > > + if (anv_free_list_pop (&(pool->free_list[i]), &pool->map, &offset)) { > > + assert(offset >= 0); > > + assert(pool->map); > > + /* Just return the blocks we do not require */ > > + int32_t needless_blocks = i + 1 - n_blocks; > > + int32_t needless_offset = offset + n_blocks * pool->block_size; > > + anv_free_list_push(&(pool->free_list[needless_blocks - 1]), pool->map, needless_offset); > > I really like this. That way one-shot giant blocks don't stay around forever when we need piles of little ones. We have no path for defragmentation, but I think that's ok. > > > + return offset; > > + } > > + } > > + > > + return anv_block_pool_alloc_new(pool, &pool->state, n_blocks); > > } > > > > /* Allocates a block out of the back of the block pool. > > @@ -564,7 +592,7 @@ anv_block_pool_alloc_back(struct anv_block_pool *pool) > > return offset; > > } > > > > - offset = anv_block_pool_alloc_new(pool, &pool->back_state); > > + offset = anv_block_pool_alloc_new(pool, &pool->back_state, 1); > > > > /* The offset we get out of anv_block_pool_alloc_new() is actually the > > * number of bytes downwards from the middle to the end of the block. > > @@ -576,12 +604,14 @@ anv_block_pool_alloc_back(struct anv_block_pool *pool) > > } > > > > void > > -anv_block_pool_free(struct anv_block_pool *pool, int32_t offset) > > +anv_block_pool_free(struct anv_block_pool *pool, int32_t offset, uint32_t n_blocks) > > { > > + assert(n_blocks >= 1 && n_blocks <= ANV_MAX_BLOCKS); > > + > > if (offset < 0) { > > anv_free_list_push(&pool->back_free_list, pool->map, offset); > > } else { > > - anv_free_list_push(&pool->free_list, pool->map, offset); > > + anv_free_list_push(&(pool->free_list[n_blocks - 1]), pool->map, offset); > > } > > } > > > > @@ -698,6 +728,9 @@ struct anv_state_stream_block { > > /* The offset into the block pool at which this block starts */ > > uint32_t offset; > > > > + /* Blocks allocated */ > > + uint32_t n_blocks; > > + > > #ifdef HAVE_VALGRIND > > /* A pointer to the first user-allocated thing in this block. This is > > * what valgrind sees as the start of the block. > > @@ -736,7 +769,7 @@ anv_state_stream_finish(struct anv_state_stream *stream) > > struct anv_state_stream_block sb = VG_NOACCESS_READ(next); > > VG(VALGRIND_MEMPOOL_FREE(stream, sb._vg_ptr)); > > VG(VALGRIND_MAKE_MEM_UNDEFINED(next, block_size)); > > - anv_block_pool_free(stream->block_pool, sb.offset); > > + anv_block_pool_free(stream->block_pool, sb.offset, sb.n_blocks); > > next = sb.next; > > } > > > > @@ -753,19 +786,23 @@ anv_state_stream_alloc(struct anv_state_stream *stream, > > > > state.offset = align_u32(stream->next, alignment); > > if (state.offset + size > stream->end) { > > - uint32_t block = anv_block_pool_alloc(stream->block_pool); > > + uint32_t n_blocks = > > + DIV_ROUND_UP(state.offset - stream->next + size, stream->block_pool->block_size); > > + uint32_t block = anv_block_pool_alloc_n(stream->block_pool, n_blocks); > > + > > sb = stream->block_pool->map + block; > > > > VG(VALGRIND_MAKE_MEM_UNDEFINED(sb, sizeof(*sb))); > > sb->next = stream->block; > > sb->offset = block; > > + sb->n_blocks = n_blocks; > > VG(sb->_vg_ptr = NULL); > > - VG(VALGRIND_MAKE_MEM_NOACCESS(sb, stream->block_pool->block_size)); > > + VG(VALGRIND_MAKE_MEM_NOACCESS(sb, n_blocks * stream->block_pool->block_size)); > > > > stream->block = sb; > > stream->start = block; > > stream->next = block + sizeof(*sb); > > - stream->end = block + stream->block_pool->block_size; > > + stream->end = block + n_blocks * stream->block_pool->block_size; > > > > state.offset = align_u32(stream->next, alignment); > > assert(state.offset + size <= stream->end); > > diff --git a/src/intel/vulkan/anv_batch_chain.c b/src/intel/vulkan/anv_batch_chain.c > > index 3f6039e..cc9d9d7 100644 > > --- a/src/intel/vulkan/anv_batch_chain.c > > +++ b/src/intel/vulkan/anv_batch_chain.c > > @@ -716,7 +716,7 @@ anv_cmd_buffer_fini_batch_bo_chain(struct anv_cmd_buffer *cmd_buffer) > > int32_t *bt_block; > > u_vector_foreach(bt_block, &cmd_buffer->bt_blocks) { > > anv_block_pool_free(&cmd_buffer->device->surface_state_block_pool, > > - *bt_block); > > + *bt_block, 1); > > } > > u_vector_finish(&cmd_buffer->bt_blocks); > > > > @@ -750,7 +750,7 @@ anv_cmd_buffer_reset_batch_bo_chain(struct anv_cmd_buffer *cmd_buffer) > > while (u_vector_length(&cmd_buffer->bt_blocks) > 1) { > > int32_t *bt_block = u_vector_remove(&cmd_buffer->bt_blocks); > > anv_block_pool_free(&cmd_buffer->device->surface_state_block_pool, > > - *bt_block); > > + *bt_block, 1); > > } > > assert(u_vector_length(&cmd_buffer->bt_blocks) == 1); > > cmd_buffer->bt_next = 0; > > diff --git a/src/intel/vulkan/anv_private.h b/src/intel/vulkan/anv_private.h > > index 7682bfc..bf92d64 100644 > > --- a/src/intel/vulkan/anv_private.h > > +++ b/src/intel/vulkan/anv_private.h > > @@ -339,6 +339,8 @@ struct anv_block_state { > > }; > > }; > > > > +#define ANV_MAX_BLOCKS 256 > > + > > struct anv_block_pool { > > struct anv_device *device; > > > > @@ -370,7 +372,7 @@ struct anv_block_pool { > > > > uint32_t block_size; > > > > - union anv_free_list free_list; > > + union anv_free_list free_list[ANV_MAX_BLOCKS]; > > struct anv_block_state state; > > > > union anv_free_list back_free_list; > > @@ -462,8 +464,9 @@ VkResult anv_block_pool_init(struct anv_block_pool *pool, > > struct anv_device *device, uint32_t block_size); > > void anv_block_pool_finish(struct anv_block_pool *pool); > > int32_t anv_block_pool_alloc(struct anv_block_pool *pool); > > +int32_t anv_block_pool_alloc_n(struct anv_block_pool *pool, uint32_t n_blocks); > > int32_t anv_block_pool_alloc_back(struct anv_block_pool *pool); > > -void anv_block_pool_free(struct anv_block_pool *pool, int32_t offset); > > +void anv_block_pool_free(struct anv_block_pool *pool, int32_t offset, uint32_t n_blocks); > > void anv_state_pool_init(struct anv_state_pool *pool, > > struct anv_block_pool *block_pool); > > void anv_state_pool_finish(struct anv_state_pool *pool); > > -- > > 2.9.3 > > > > > > </div></div></blockquote></div></div></div> </div></div> </blockquote></div> </div></div>