Discussion:
[PATCH] gallium/util: add new module that allocate "numbers"
Add Reply
Samuel Pitoiset
2017-08-08 16:57:21 UTC
Reply
Permalink
Raw Message
Will be used for allocating bindless descriptor slots for
RadeonSI.

Signed-off-by: Samuel Pitoiset <***@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));
+
+ 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)
+{
+ 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));
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* U_IDALLOC_H */
--
2.14.0
Nicolai Hähnle
2017-08-09 16:41:26 UTC
Reply
Permalink
Raw Message
Post by Samuel Pitoiset
Will be used for allocating bindless descriptor slots for
RadeonSI.
---
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 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.
Post by Samuel Pitoiset
+
+ 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.
Post by Samuel Pitoiset
+{
+ 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
Post by Samuel Pitoiset
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* U_IDALLOC_H */
--
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.
Samuel Pitoiset
2017-08-11 07:31:14 UTC
Reply
Permalink
Raw Message
Post by Nicolai Hähnle
Post by Samuel Pitoiset
Will be used for allocating bindless descriptor slots for
RadeonSI.
---
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 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.
Post by Nicolai Hähnle
Post by Samuel Pitoiset
+
+ 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.
Post by Samuel Pitoiset
+{
+ 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.
Post by Nicolai Hähnle
If that's the interface, I'd honestly prefer a non-inline implementation
as well.
Cheers,
Nicolai
Post by Samuel Pitoiset
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* U_IDALLOC_H */
Samuel Pitoiset
2017-08-11 08:55:34 UTC
Reply
Permalink
Raw Message
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 <***@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 <***@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;
+ }
+ }
+
+ /* 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
Marek Olšák
2017-08-11 17:35:40 UTC
Reply
Permalink
Raw Message
On Fri, Aug 11, 2017 at 10:55 AM, Samuel Pitoiset
Post by Samuel Pitoiset
Will be used for allocating bindless descriptor slots for
RadeonSI.
v2 - change the interface (remove lock/unlock)
- make a non-inline implementation
---
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 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.
+ *
+ **************************************************************************/
+
+/**
+ * A simple allocator that allocates and release "numbers".
+ *
+ */
+
+#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 <***@amd.com>

Marek
Post by Samuel Pitoiset
+
+ /* 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 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
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
Samuel Pitoiset
2017-08-21 14:49:48 UTC
Reply
Permalink
Raw Message
Will be used for allocating bindless descriptor slots for
RadeonSI.

v3; - use a faster loop in util_idalloc_alloc() (Marek)
v2: - change the interface (remove lock/unlock)
- make a non-inline implementation

Signed-off-by: Samuel Pitoiset <***@gmail.com>
Reviewed-by: Marek Olšák <***@amd.com> (v2)
---
src/gallium/auxiliary/Makefile.sources | 2 +
src/gallium/auxiliary/util/u_idalloc.c | 96 ++++++++++++++++++++++++++++++++++
src/gallium/auxiliary/util/u_idalloc.h | 62 ++++++++++++++++++++++
3 files changed, 160 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..26104552e5
--- /dev/null
+++ b/src/gallium/auxiliary/util/u_idalloc.c
@@ -0,0 +1,96 @@
+/**************************************************************************
+ *
+ * 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 <***@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 / 32; i++) {
+ if (buf->data[i] == 0xffffffff)
+ continue;
+
+ unsigned bit = ffs(~buf->data[i]) - 1;
+ buf->data[i] |= 1u << bit;
+ return i * 32 + bit;
+ }
+
+ /* 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.1
Eric Engestrom
2017-08-21 14:59:05 UTC
Reply
Permalink
Raw Message
Post by Samuel Pitoiset
Will be used for allocating bindless descriptor slots for
RadeonSI.
v3; - use a faster loop in util_idalloc_alloc() (Marek)
v2: - change the interface (remove lock/unlock)
- make a non-inline implementation
---
src/gallium/auxiliary/Makefile.sources | 2 +
src/gallium/auxiliary/util/u_idalloc.c | 96 ++++++++++++++++++++++++++++++++++
src/gallium/auxiliary/util/u_idalloc.h | 62 ++++++++++++++++++++++
3 files changed, 160 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..26104552e5
--- /dev/null
+++ b/src/gallium/auxiliary/util/u_idalloc.c
@@ -0,0 +1,96 @@
+/**************************************************************************
+ *
+ * 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 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.
+ *
+ **************************************************************************/
+
+/**
+ * A simple allocator that allocates and release "numbers".
+ *
+ */
+
+#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)
I'm guessing you meant `if (buf)` here?
Post by Samuel Pitoiset
+ 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 / 32; i++) {
+ if (buf->data[i] == 0xffffffff)
+ continue;
+
+ unsigned bit = ffs(~buf->data[i]) - 1;
+ buf->data[i] |= 1u << bit;
+ return i * 32 + bit;
+ }
+
+ /* 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 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.1
Samuel Pitoiset
2017-08-21 15:06:19 UTC
Reply
Permalink
Raw Message
Post by Eric Engestrom
Post by Samuel Pitoiset
Will be used for allocating bindless descriptor slots for
RadeonSI.
v3; - use a faster loop in util_idalloc_alloc() (Marek)
v2: - change the interface (remove lock/unlock)
- make a non-inline implementation
---
src/gallium/auxiliary/Makefile.sources | 2 +
src/gallium/auxiliary/util/u_idalloc.c | 96 ++++++++++++++++++++++++++++++++++
src/gallium/auxiliary/util/u_idalloc.h | 62 ++++++++++++++++++++++
3 files changed, 160 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..26104552e5
--- /dev/null
+++ b/src/gallium/auxiliary/util/u_idalloc.c
@@ -0,0 +1,96 @@
+/**************************************************************************
+ *
+ * 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 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.
+ *
+ **************************************************************************/
+
+/**
+ * A simple allocator that allocates and release "numbers".
+ *
+ */
+
+#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)
I'm guessing you meant `if (buf)` here?
Not really, it's similar to how u_dynarray is implemented actually.
Post by Eric Engestrom
Post by Samuel Pitoiset
+ 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 / 32; i++) {
+ if (buf->data[i] == 0xffffffff)
+ continue;
+
+ unsigned bit = ffs(~buf->data[i]) - 1;
+ buf->data[i] |= 1u << bit;
+ return i * 32 + bit;
+ }
+
+ /* 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 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.1
Eric Engestrom
2017-08-21 16:00:58 UTC
Reply
Permalink
Raw Message
Post by Samuel Pitoiset
Post by Eric Engestrom
Post by Samuel Pitoiset
Will be used for allocating bindless descriptor slots for
RadeonSI.
v3; - use a faster loop in util_idalloc_alloc() (Marek)
v2: - change the interface (remove lock/unlock)
- make a non-inline implementation
---
src/gallium/auxiliary/Makefile.sources | 2 +
src/gallium/auxiliary/util/u_idalloc.c | 96 ++++++++++++++++++++++++++++++++++
src/gallium/auxiliary/util/u_idalloc.h | 62 ++++++++++++++++++++++
3 files changed, 160 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..26104552e5
--- /dev/null
+++ b/src/gallium/auxiliary/util/u_idalloc.c
@@ -0,0 +1,96 @@
+/**************************************************************************
+ *
+ * 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 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.
+ *
+ **************************************************************************/
+
+/**
+ * A simple allocator that allocates and release "numbers".
+ *
+ */
+
+#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)
I'm guessing you meant `if (buf)` here?
Not really, it's similar to how u_dynarray is implemented actually.
util_dynarray_fini() has a null-check on ->data to avoid re-doing
a memset if not necessary, but this doesn't apply here... unless you
meant to do that here?

`free(NULL);` is a noop, so the `if`-guard here has no effect; I suggest
simply removing the `if` :)

(I first assumed you meant to allow `util_idalloc_fini(NULL);`, but this
isn't a free-like function, so this convention doesn't apply.)

And sorry, I didn't mean to bikeshed ;)
Post by Samuel Pitoiset
Post by Eric Engestrom
Post by Samuel Pitoiset
+ 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 / 32; i++) {
+ if (buf->data[i] == 0xffffffff)
+ continue;
+
+ unsigned bit = ffs(~buf->data[i]) - 1;
+ buf->data[i] |= 1u << bit;
+ return i * 32 + bit;
+ }
+
+ /* 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 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.1
Marek Olšák
2017-08-21 21:01:33 UTC
Reply
Permalink
Raw Message
Reviewed-by: Marek Olšák <***@amd.com>

Marek

On Mon, Aug 21, 2017 at 4:49 PM, Samuel Pitoiset
Post by Samuel Pitoiset
Will be used for allocating bindless descriptor slots for
RadeonSI.
v3; - use a faster loop in util_idalloc_alloc() (Marek)
v2: - change the interface (remove lock/unlock)
- make a non-inline implementation
---
src/gallium/auxiliary/Makefile.sources | 2 +
src/gallium/auxiliary/util/u_idalloc.c | 96 ++++++++++++++++++++++++++++++++++
src/gallium/auxiliary/util/u_idalloc.h | 62 ++++++++++++++++++++++
3 files changed, 160 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..26104552e5
--- /dev/null
+++ b/src/gallium/auxiliary/util/u_idalloc.c
@@ -0,0 +1,96 @@
+/**************************************************************************
+ *
+ * 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 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.
+ *
+ **************************************************************************/
+
+/**
+ * A simple allocator that allocates and release "numbers".
+ *
+ */
+
+#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 / 32; i++) {
+ if (buf->data[i] == 0xffffffff)
+ continue;
+
+ unsigned bit = ffs(~buf->data[i]) - 1;
+ buf->data[i] |= 1u << bit;
+ return i * 32 + bit;
+ }
+
+ /* 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 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.1
_______________________________________________
mesa-dev mailing list
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
Loading...