[Mesa-dev] [PATCH] gallium/util: add new module that allocate "numbers"

[Samuel Pitoiset]

On 08/09/2017 06:41 PM, Nicolai Hähnle wrote:
> On 08.08.2017 18:57, Samuel Pitoiset wrote:
>> Will be used for allocating bindless descriptor slots for
>> RadeonSI.
>>
>> Signed-off-by: Samuel Pitoiset <samuel.pitoiset at gmail.com>
>> ---
>>   src/gallium/auxiliary/Makefile.sources |   1 +
>>   src/gallium/auxiliary/util/u_idalloc.h | 103 
>> +++++++++++++++++++++++++++++++++
>>   2 files changed, 104 insertions(+)
>>   create mode 100644 src/gallium/auxiliary/util/u_idalloc.h
>>
>> diff --git a/src/gallium/auxiliary/Makefile.sources 
>> b/src/gallium/auxiliary/Makefile.sources
>> index 9ae8e6c8ca..10101d45a4 100644
>> --- a/src/gallium/auxiliary/Makefile.sources
>> +++ b/src/gallium/auxiliary/Makefile.sources
>> @@ -253,6 +253,7 @@ C_SOURCES := \
>>       util/u_hash_table.h \
>>       util/u_helpers.c \
>>       util/u_helpers.h \
>> +    util/u_idalloc.h \
>>       util/u_index_modify.c \
>>       util/u_index_modify.h \
>>       util/u_inlines.h \
>> diff --git a/src/gallium/auxiliary/util/u_idalloc.h 
>> b/src/gallium/auxiliary/util/u_idalloc.h
>> new file mode 100644
>> index 0000000000..e98f47ccb1
>> --- /dev/null
>> +++ b/src/gallium/auxiliary/util/u_idalloc.h
>> @@ -0,0 +1,103 @@
>> +/************************************************************************** 
>>
>> + *
>> + * Copyright 2017 Valve Corporation
>> + * All Rights Reserved.
>> + *
>> + * Permission is hereby granted, free of charge, to any person 
>> obtaining a
>> + * copy of this software and associated documentation files (the
>> + * "Software"), to deal in the Software without restriction, including
>> + * without limitation the rights to use, copy, modify, merge, publish,
>> + * distribute, sub license, and/or sell copies of the Software, and to
>> + * permit persons to whom the Software is furnished to do so, subject to
>> + * the following conditions:
>> + *
>> + * The above copyright notice and this permission notice (including the
>> + * next paragraph) shall be included in all copies or substantial 
>> portions
>> + * of the Software.
>> + *
>> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
>> EXPRESS
>> + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
>> + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
>> NON-INFRINGEMENT.
>> + * IN NO EVENT SHALL THE AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR
>> + * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
>> CONTRACT,
>> + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
>> + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
>> + *
>> + 
>> **************************************************************************/ 
>>
>> +
>> +#ifndef U_IDALLOC_H
>> +#define U_IDALLOC_H
>> +
>> +/* A simple allocator that allocates and release "numbers". */
>> +
>> +#include "util/u_memory.h"
>> +
>> +#ifdef __cplusplus
>> +extern "C" {
>> +#endif
>> +
>> +struct util_idalloc
>> +{
>> +   uint32_t *data;
>> +   unsigned num_elements;
>> +};
>> +
>> +static inline void
>> +util_idalloc_init(struct util_idalloc *buf)
>> +{
>> +   memset(buf, 0, sizeof(*buf));
>> +}
>> +
>> +static inline void
>> +util_idalloc_fini(struct util_idalloc *buf)
>> +{
>> +   if (buf->data)
>> +      free(buf->data);
>> +}
>> +
>> +static inline void
>> +util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements)
>> +{
>> +   assert(!(new_num_elements % 32));
> 
> Just round up. That's cheap enough, and there's no reason to leak this 
> implementation detail to the caller.

Yeah, that sounds better.

> 
> 
>> +
>> +   if (new_num_elements > buf->num_elements) {
>> +      unsigned i;
>> +
>> +      buf->data = realloc(buf->data,
>> +                          (new_num_elements / 32) * sizeof(*buf->data));
>> +
>> +      for (i = buf->num_elements / 32; i < new_num_elements / 32; i++)
>> +         buf->data[i] = 0;
>> +      buf->num_elements = new_num_elements;
>> +   }
>> +}
>> +
>> +static inline int32_t
>> +util_idalloc_get_next_free(struct util_idalloc *buf)
> 
> Call it get_first_free and use bit scan per word. (I wouldn't be 
> surprised if GCC actually recognized and optimized that pattern in 
> optimized builds, but still...). But see below as well.
> 
> 
>> +{
>> +   for (unsigned i = 0; i < buf->num_elements; i++) {
>> +      if (!(buf->data[i / 32] & (1 << (i % 32))))
>> +         return i;
>> +   }
>> +   return -1;
>> +}
>> +
>> +static inline void
>> +util_idalloc_lock(struct util_idalloc *buf, unsigned id)
>> +{
>> +   assert(id < buf->num_elements);
>> +   buf->data[id / 32] |= 1 << (id % 32);
>> +}
>> +
>> +static inline void
>> +util_idalloc_unlock(struct util_idalloc *buf, unsigned id)
>> +{
>> +   assert(id < buf->num_elements);
>> +   buf->data[id / 32] &= ~(1 << (id % 32));
>> +}
> 
> lock/unlock sounds a lot like mutexes/locks in the threading sense.
> 
> Is the get_next_free/lock/unlock interface really needed? Since this 
> module calls itself an ID allocator, how about an interface
> 
> unsigned util_idalloc_alloc(struct util_idalloc *buf);
> void util_idalloc_free(struct util_idalloc *buf, unsigned id);
> 
> instead?

This interface is simpler and should be enough for my needs.

> 
> If that's the interface, I'd honestly prefer a non-inline implementation 
> as well.
> 
> Cheers,
> Nicolai
> 
> 
>> +
>> +#ifdef __cplusplus
>> +}
>> +#endif
>> +
>> +#endif /* U_IDALLOC_H */
>>
> 
>