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

[Nicolai Hähnle]

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.


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

If that's the interface, I'd honestly prefer a non-inline implementation 
as well.

Cheers,
Nicolai


> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* U_IDALLOC_H */
> 


-- 
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.