Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-04-06 Thread Jason Ekstrand 
On April 6, 2017 8:29:11 AM "Juan A. Suarez Romero"  
wrote:



On Mon, 2017-04-03 at 07:44 -0700, Jason Ekstrand wrote:
On Mon, Apr 3, 2017 at 5:02 AM, Juan A. Suarez Romero  
wrote:

> 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?
>

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".

 
> >
> >  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?

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.


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.


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!



There are a lot of interesting ideas in this thread. I agree that
probably we will need to do a refactor, sooner or later.

But as you said, before going on, I also think we should fix the
original issue first. So I'll submit a patch with a fix that uses the
power-of-two based on the current patch.

Just to be clear we are in the same page regarding this power-of-two
fix, the idea is that anv_block_pool_alloc_n() and
anv_block_pool_free() will specify the required memory in bytes
(instead of blocks, as the current patch). And the memory assigned will
be a power-of-2 enough to fulfil the requirement.

And so free_list[N] is a list with blocks of memory of size 2^N bytes,
instead of blocks of size N*block_size bytes, as current patch.


Yup.  I also made a comment somewhere in there about the way the if 
statement is written in alloc_new.



Regarding the refactoring, it's pretty much clear you have better
understanding of the full problem, and it wouldn't take much time for
you to fix, and you would be happy to do it :)

So it seems more sensible if you do it. Nevertheless, if for any reason
you prefer me to do it, won't be a problem. I gladly can do it if
required.


That's fine.  I'll cook something up once your patch lands.


 
> >  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 
 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.
> > >
> > >

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-04-06 Thread Juan A. Suarez Romero 
On Mon, 2017-04-03 at 07:44 -0700, Jason Ekstrand wrote:
> On Mon, Apr 3, 2017 at 5:02 AM, Juan A. Suarez Romero  
> wrote:
> > 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?
> > 
> 
> 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".
>  
> > >
> > >  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?
> 
> 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.
> 
> 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.
> 
> 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!


There are a lot of interesting ideas in this thread. I agree that
probably we will need to do a refactor, sooner or later.

But as you said, before going on, I also think we should fix the
original issue first. So I'll submit a patch with a fix that uses the
power-of-two based on the current patch.

Just to be clear we are in the same page regarding this power-of-two
fix, the idea is that anv_block_pool_alloc_n() and
anv_block_pool_free() will specify the required memory in bytes
(instead of blocks, as the current patch). And the memory assigned will
be a power-of-2 enough to fulfil the requirement.

And so free_list[N] is a list with blocks of memory of size 2^N bytes,
instead of blocks of size N*block_size bytes, as current patch.



Regarding the refactoring, it's pretty much clear you have better
understanding of the full problem, and it wouldn't take much time for
you to fix, and you would be happy to do it :)

So it seems more sensible if you do it. Nevertheless, if for any reason
you prefer me to do it, won't be a problem. I gladly can do it if
required.



>  
> > >  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 
> > >  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)
> > > >

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-04-03 Thread Jason Ekstrand 
On Mon, Apr 3, 2017 at 7:44 AM, Jason Ekstrand  wrote:

> On Mon, Apr 3, 2017 at 5:02 AM, Juan A. Suarez Romero  > wrote:
>
>> 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?
>>
>
> 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".
>
>
>> >
>> >  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?
>>
>
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.


> 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.
>
> 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.
>
> 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!
>
>
>> >  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 <
>> jasua...@igalia.com> 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(>bo, 0, 0);
>> > > pool->block_size = block_size;
>> > > -   pool->free_list =

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-04-03 Thread Jason Ekstrand 
On Mon, Apr 3, 2017 at 9:40 AM, Kristian Høgsberg 
wrote:

> On Wed, Mar 29, 2017 at 12:06 PM, 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.
>
> I haven't looked closely, and I agree it's increasingly tricky code to
> review. I'd be careful about making this a fully generic any-block
> size allocator. The premise, when we first designed this, was that for
> something like a fixed-size, power-of-two pool, we could write a fast,
> lock-less and fragmentation free allocator without getting in over our
> heads.


Yeah, it's getting tricky but I don't think it's outside the realm of
humans yet. :-)


> However, if this evolves (devolves?) into "malloc, but for
> bos", it may be time to take a step back and look if something like
> jemalloc with bo backing is a better choice.
>

Yeah, it may be time to start considering that.  Unfortunately, I don't
think we can use jemalloc for this in a safe way.  jemalloc does provide a
way to manage pools but it does so, not with a pool pointer, but with an
arena number in a global namespace.  If an app were to use jemalloc (I
wouldn't be surprised in the gaming world if jemalloc is fairly
common-place) and uses arenas, we could end up with silent collisions.

At some point (probably later this year), I hope to look into pulling in a
foreign memory allocator and use that for BO placement and start
softpinning the universe (no relocations!).  That may be a good time to
revisit allocation strategies a bit.

Kristian
>
> >
> >  1. Should we do powers of two or linear.  I'm still a fan of powers of
> two.
> >
> >  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.
> >
> >  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 <
> jasua...@igalia.com>
> > 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(>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(_state->u64,
> >> pool->block_size);
> >> -  if (state.next < state.end) {
> >> +  state.u64 = __sync_fetch_and_add(_state->u64, n_blocks *
> >> pool->block_size);
> >> +  if (state.next > state.end) {
> >> + futex_wait(_state->end, state.end);
> >> + continue;
> >>

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-04-03 Thread Kristian Høgsberg 
On Wed, Mar 29, 2017 at 12:06 PM, 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.

I haven't looked closely, and I agree it's increasingly tricky code to
review. I'd be careful about making this a fully generic any-block
size allocator. The premise, when we first designed this, was that for
something like a fixed-size, power-of-two pool, we could write a fast,
lock-less and fragmentation free allocator without getting in over our
heads. However, if this evolves (devolves?) into "malloc, but for
bos", it may be time to take a step back and look if something like
jemalloc with bo backing is a better choice.

Kristian

>
>  1. Should we do powers of two or linear.  I'm still a fan of powers of two.
>
>  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.
>
>  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 
> 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(>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(_state->u64,
>> pool->block_size);
>> -  if (state.next < state.end) {
>> +  state.u64 = __sync_fetch_and_add(_state->u64, n_blocks *
>> pool->block_size);
>> +  if (state.next > state.end) {
>> + futex_wait(_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
>> +

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-04-03 Thread Jason Ekstrand 
On Mon, Apr 3, 2017 at 5:02 AM, Juan A. Suarez Romero 
wrote:

> 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?
>

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".


> >
> >  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?
>

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.

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.

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!


> >  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 <
> jasua...@igalia.com> 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(>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

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-04-03 Thread Juan A. Suarez Romero 
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? 

> 
>  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?



>  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  
> 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(>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(_state->u64, pool->block_size);
> > -      if (state.next < state.end) {
> > +      state.u64 = __sync_fetch_and_add(_state->u64, n_blocks * 
> > pool->block_size);
> > +      if (state.next > state.end) {
> > +         futex_wait(_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.
> > +          */
> > +         

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-03-29 Thread Jason Ekstrand 
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.

 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.

 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 
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(>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(_state->u64,
> pool->block_size);
> -  if (state.next < state.end) {
> +  state.u64 = __sync_fetch_and_add(_state->u64, n_blocks *
> pool->block_size);
> +  if (state.next > state.end) {
> + futex_wait(_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(_state->u64, new.u64);
>

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-03-23 Thread Jason Ekstrand 
On Thu, Mar 23, 2017 at 1:50 PM, Jason Ekstrand 
wrote:

> On Wed, Mar 22, 2017 at 4:14 AM, Juan A. Suarez Romero <
> jasua...@igalia.com> wrote:
>
>> On Wed, 2017-03-15 at 13:05 +0100, Juan A. Suarez Romero 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)
>> > ---
>>
>> Gently ping to get feedback/review O:)
>>
>
> Yup.  I took a break from e-mail so I could write some of my own patches
> for once. :-)
>

I'll try to get to it tomorrow.  Sorry about the delay.  This stuff is
hairy enough that I have to carve out some serious brain-space to review
it.
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-03-23 Thread Jason Ekstrand 
On Wed, Mar 22, 2017 at 4:14 AM, Juan A. Suarez Romero 
wrote:

> On Wed, 2017-03-15 at 13:05 +0100, Juan A. Suarez Romero 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)
> > ---
>
> Gently ping to get feedback/review O:)
>

Yup.  I took a break from e-mail so I could write some of my own patches
for once. :-)

--Jason
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

Re: [Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-03-22 Thread Juan A. Suarez Romero 
On Wed, 2017-03-15 at 13:05 +0100, Juan A. Suarez Romero 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)
> ---

Gently ping to get feedback/review O:)

J.A.

___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

[Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-03-15 Thread Juan A. Suarez Romero 
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(>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)
 {
struct anv_block_state state, old, new;
 
while (1) {
-  state.u64 = __sync_fetch_and_add(_state->u64, pool->block_size);
-  if (state.next < state.end) {
+  state.u64 = __sync_fetch_and_add(_state->u64, n_blocks * 
pool->block_size);
+  if (state.next > state.end) {
+ futex_wait(_state->end, state.end);
+ continue;
+  } else if ((state.next + (n_blocks - 1) * pool->block_size) < state.end) 
{
  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
+  */
  assert(new.end >= new.next && new.end % pool->block_size == 0);
  old.u64 = __sync_lock_test_and_set(_state->u64, new.u64);
  if (old.next != state.next)
 futex_wake(_state->end, INT_MAX);
  return state.next;
-  } else {
- futex_wait(_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);
+
/* Try free list first. */
-   if (anv_free_list_pop(>free_list, >map, )) {
+   if (anv_free_list_pop(&(pool->free_list[n_blocks - 1]), >map, 
)) {
   assert(offset >= 0);
   assert(pool->map);
   return offset;
}
 
-   return anv_block_pool_alloc_new(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]), >map, )) {
+ 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);
+
+ return offset;
+  }
+   }
+
+   return anv_block_pool_alloc_new(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, >back_state);
+   offset = anv_block_pool_alloc_new(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

[Mesa-dev] [PATCH v2] anv: add support for allocating more than 1 block of memory

2017-03-15 Thread Juan A. Suarez Romero 
The current ANV allocator is restricted to allocate just 1 block of memory,
which causes crashes in some Vulkan CTS tests. This patch allows to allocate
more than 1 block.

This is a re-work for the first version, which had issues due the nature of the
lock-free free-list.

In this version, instead of one list of free-blocks, we use an array: N-th list
keeps a list of free blocks that are N+1 consecutives. This array is 256
elements, meaning that we can request up to 256 blocks. If this is too much (or
too low), we can tune it.

Thus, if a program requests, let's say, 16 blocks of memory, we pull it from
free_list[15]. If this list is empty, we search in the list of bigger blocks,
pull one, split it, and returning back to the free_list the blocks we are not
using. Finally, if none is available, then we pull a fresh blocks.

Other than that, it works like the previous patch: when pulling fresh blocks, we
grow up the pool if no space is available.


Juan A. Suarez Romero (1):
  anv: add support for allocating more than 1 block of memory

 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(-)

-- 
2.9.3

___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev