[Mesa-dev] [PATCH v2] gallium/util: add new module that allocate "numbers"
Marek Olšák
maraeo at gmail.com
Fri Aug 11 17:35:40 UTC 2017
On Fri, Aug 11, 2017 at 10:55 AM, Samuel Pitoiset
<samuel.pitoiset at gmail.com> wrote:
> Will be used for allocating bindless descriptor slots for
> RadeonSI.
>
> v2 - change the interface (remove lock/unlock)
> - make a non-inline implementation
>
> Signed-off-by: Samuel Pitoiset <samuel.pitoiset at gmail.com>
> ---
> src/gallium/auxiliary/Makefile.sources | 2 +
> src/gallium/auxiliary/util/u_idalloc.c | 94 ++++++++++++++++++++++++++++++++++
> src/gallium/auxiliary/util/u_idalloc.h | 62 ++++++++++++++++++++++
> 3 files changed, 158 insertions(+)
> create mode 100644 src/gallium/auxiliary/util/u_idalloc.c
> 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..7d5f9e7899 100644
> --- a/src/gallium/auxiliary/Makefile.sources
> +++ b/src/gallium/auxiliary/Makefile.sources
> @@ -253,6 +253,8 @@ C_SOURCES := \
> util/u_hash_table.h \
> util/u_helpers.c \
> util/u_helpers.h \
> + util/u_idalloc.c \
> + 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.c b/src/gallium/auxiliary/util/u_idalloc.c
> new file mode 100644
> index 0000000000..61b0e0cc49
> --- /dev/null
> +++ b/src/gallium/auxiliary/util/u_idalloc.c
> @@ -0,0 +1,94 @@
> +/**************************************************************************
> + *
> + * 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.
> + *
> + **************************************************************************/
> +
> +/**
> + * @file
> + * A simple allocator that allocates and release "numbers".
> + *
> + * @author Samuel Pitoiset <samuel.pitoiset at gmail.com>
> + */
> +
> +#include "util/u_idalloc.h"
> +#include "util/u_math.h"
> +#include "util/u_memory.h"
> +
> +void
> +util_idalloc_init(struct util_idalloc *buf)
> +{
> + memset(buf, 0, sizeof(*buf));
> +}
> +
> +void
> +util_idalloc_fini(struct util_idalloc *buf)
> +{
> + if (buf->data)
> + free(buf->data);
> +}
> +
> +void
> +util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements)
> +{
> + new_num_elements = align(new_num_elements, 32);
> +
> + 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;
> + }
> +}
> +
> +unsigned
> +util_idalloc_alloc(struct util_idalloc *buf)
> +{
> + unsigned num_elements = buf->num_elements;
> +
> + for (unsigned i = 0; i < num_elements; i++) {
> + if (!(buf->data[i / 32] & (1 << (i % 32)))) {
> + buf->data[i / 32] |= 1 << (i % 32);
> + return i;
> + }
> + }
This is faster:
for (unsigned i = 0; i < num_elements / 32; i++) {
if (buf->data[i] == 0xffffffff)
continue;
unsigned bit = ffs(~buf->data[i]) - 1;
but->data[i] |= 1u << bit;
return i * 32 + bit;
}
If you replace the loop with mine, the patch is:
Reviewed-by: Marek Olšák <marek.olsak at amd.com>
Marek
> +
> + /* No slots available, resize and return the first free. */
> + util_idalloc_resize(buf, num_elements * 2);
> +
> + buf->data[num_elements / 32] |= 1 << (num_elements % 32);
> +
> + return num_elements;
> +}
> +
> +void
> +util_idalloc_free(struct util_idalloc *buf, unsigned id)
> +{
> + assert(id < buf->num_elements);
> + buf->data[id / 32] &= ~(1 << (id % 32));
> +}
> diff --git a/src/gallium/auxiliary/util/u_idalloc.h b/src/gallium/auxiliary/util/u_idalloc.h
> new file mode 100644
> index 0000000000..82469e94d8
> --- /dev/null
> +++ b/src/gallium/auxiliary/util/u_idalloc.h
> @@ -0,0 +1,62 @@
> +/**************************************************************************
> + *
> + * 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
> +
> +#include <inttypes.h>
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +struct util_idalloc
> +{
> + uint32_t *data;
> + unsigned num_elements;
> +};
> +
> +void
> +util_idalloc_init(struct util_idalloc *buf);
> +
> +void
> +util_idalloc_fini(struct util_idalloc *buf);
> +
> +void
> +util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements);
> +
> +unsigned
> +util_idalloc_alloc(struct util_idalloc *buf);
> +
> +void
> +util_idalloc_free(struct util_idalloc *buf, unsigned id);
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* U_IDALLOC_H */
> --
> 2.14.0
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list