[API-NEXT,v9,3/6] linux-gen: sched scalable: add a bitset

Message ID 20170619191247.51385-4-brian.brooks@arm.com
State Superseded
Headers show
Series
  • A scalable software scheduler
Related show

Commit Message

Brian Brooks June 19, 2017, 7:12 p.m.
Signed-off-by: Ola Liljedahl <ola.liljedahl@arm.com>

Reviewed-by: Brian Brooks <brian.brooks@arm.com>

Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>

---
 platform/linux-generic/Makefile.am          |   1 +
 platform/linux-generic/include/odp_bitset.h | 210 ++++++++++++++++++++++++++++
 2 files changed, 211 insertions(+)
 create mode 100644 platform/linux-generic/include/odp_bitset.h

-- 
2.13.1

Comments

Savolainen, Petri (Nokia - FI/Espoo) June 20, 2017, 1:04 p.m. | #1
> +++ b/platform/linux-generic/include/odp_bitset.h

> @@ -0,0 +1,210 @@

> +/* Copyright (c) 2017, ARM Limited

> + * All rights reserved.

> + *

> + * SPDX-License-Identifier:     BSD-3-Clause

> + */

> +

> +#ifndef _ODP_BITSET_H_

> +#define _ODP_BITSET_H_

> +

> +#include <odp_cpu.h>

> +

> +#include <limits.h>

> +

> +/************************************************************************

> ******

> + * bitset abstract data type

> +

> **************************************************************************

> ***/

> +/* This could be a struct of scalars to support larger bit sets */

> +

> +/*

> + * Size of atomic bit set. This limits the max number of threads,

> + * scheduler groups and reorder windows. On ARMv8/64-bit and x86-64, the

> + * (lock-free) max is 128

> + */

> +

> +/* Find a suitable data type that supports lock-free atomic operations */

> +#if defined(__ARM_ARCH) &&  __ARM_ARCH == 8 &&  __ARM_64BIT_STATE == 1 &&


Why ifdef ARM? Why this code is not in arch directory ?

-Petri


> \

> +	defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ == 16

> +#define LOCKFREE16

> +typedef __int128 bitset_t;

> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT128__)

> +

> +#elif __GCC_ATOMIC_LLONG_LOCK_FREE == 2 && \

> +	__SIZEOF_LONG_LONG__ != __SIZEOF_LONG__

> +typedef unsigned long long bitset_t;

> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_LONG_LONG__)

> +

> +#elif __GCC_ATOMIC_LONG_LOCK_FREE == 2 && __SIZEOF_LONG__ !=

> __SIZEOF_INT__

> +typedef unsigned long bitset_t;

> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_LONG__)

> +

> +#elif __GCC_ATOMIC_INT_LOCK_FREE == 2

> +typedef unsigned int bitset_t;

> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT__)

> +

> +#else

> +/* Target does not support lock-free atomic operations */

> +typedef unsigned int bitset_t;

> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT__)

> +#endif

> +

> +#if ATOM_BITSET_SIZE <= 32
Ola Liljedahl June 21, 2017, 6:14 p.m. | #2
On 20/06/2017, 15:04, "Savolainen, Petri (Nokia - FI/Espoo)"
<petri.savolainen@nokia.com> wrote:

>

>

>> +++ b/platform/linux-generic/include/odp_bitset.h

>> @@ -0,0 +1,210 @@

>> +/* Copyright (c) 2017, ARM Limited

>> + * All rights reserved.

>> + *

>> + * SPDX-License-Identifier:     BSD-3-Clause

>> + */

>> +

>> +#ifndef _ODP_BITSET_H_

>> +#define _ODP_BITSET_H_

>> +

>> +#include <odp_cpu.h>

>> +

>> +#include <limits.h>

>> +

>> 

>>+/***********************************************************************

>>*

>> ******

>> + * bitset abstract data type

>> +

>> 

>>*************************************************************************

>>*

>> ***/

>> +/* This could be a struct of scalars to support larger bit sets */

>> +

>> +/*

>> + * Size of atomic bit set. This limits the max number of threads,

>> + * scheduler groups and reorder windows. On ARMv8/64-bit and x86-64,

>>the

>> + * (lock-free) max is 128

>> + */

>> +

>> +/* Find a suitable data type that supports lock-free atomic operations

>>*/

>> +#if defined(__ARM_ARCH) &&  __ARM_ARCH == 8 &&  __ARM_64BIT_STATE == 1

>>&&

>

>Why ifdef ARM? Why this code is not in arch directory ?

Why is this car red?
Because I like it like that.


>

>-Petri

>

>

>> \

>> +	defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ == 16

>> +#define LOCKFREE16

>> +typedef __int128 bitset_t;

>> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT128__)

>> +

>> +#elif __GCC_ATOMIC_LLONG_LOCK_FREE == 2 && \

>> +	__SIZEOF_LONG_LONG__ != __SIZEOF_LONG__

>> +typedef unsigned long long bitset_t;

>> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_LONG_LONG__)

>> +

>> +#elif __GCC_ATOMIC_LONG_LOCK_FREE == 2 && __SIZEOF_LONG__ !=

>> __SIZEOF_INT__

>> +typedef unsigned long bitset_t;

>> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_LONG__)

>> +

>> +#elif __GCC_ATOMIC_INT_LOCK_FREE == 2

>> +typedef unsigned int bitset_t;

>> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT__)

>> +

>> +#else

>> +/* Target does not support lock-free atomic operations */

>> +typedef unsigned int bitset_t;

>> +#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT__)

>> +#endif

>> +

>> +#if ATOM_BITSET_SIZE <= 32

>

>
Dmitry Eremin-Solenikov June 21, 2017, 8 p.m. | #3
On 21.06.2017 21:14, Ola Liljedahl wrote:
> 

> On 20/06/2017, 15:04, "Savolainen, Petri (Nokia - FI/Espoo)"

> <petri.savolainen@nokia.com> wrote:

> 

>>

>>

>>> +++ b/platform/linux-generic/include/odp_bitset.h

>>> @@ -0,0 +1,210 @@

>>> +/* Copyright (c) 2017, ARM Limited

>>> + * All rights reserved.

>>> + *

>>> + * SPDX-License-Identifier:     BSD-3-Clause

>>> + */

>>> +

>>> +#ifndef _ODP_BITSET_H_

>>> +#define _ODP_BITSET_H_

>>> +

>>> +#include <odp_cpu.h>

>>> +

>>> +#include <limits.h>

>>> +

>>>

>>> +/***********************************************************************

>>> *

>>> ******

>>> + * bitset abstract data type

>>> +

>>>

>>> *************************************************************************

>>> *

>>> ***/

>>> +/* This could be a struct of scalars to support larger bit sets */

>>> +

>>> +/*

>>> + * Size of atomic bit set. This limits the max number of threads,

>>> + * scheduler groups and reorder windows. On ARMv8/64-bit and x86-64,

>>> the

>>> + * (lock-free) max is 128

>>> + */

>>> +

>>> +/* Find a suitable data type that supports lock-free atomic operations

>>> */

>>> +#if defined(__ARM_ARCH) &&  __ARM_ARCH == 8 &&  __ARM_64BIT_STATE == 1

>>> &&

>>

>> Why ifdef ARM? Why this code is not in arch directory ?

> Why is this car red?

> Because I like it like that.


I think it was agreed that arch-specific code should go to arch/ dirs,
wasn't it?


-- 
With best wishes
Dmitry
Maxim Uvarov June 21, 2017, 8:02 p.m. | #4
On 06/21/17 23:00, Dmitry Eremin-Solenikov wrote:
> On 21.06.2017 21:14, Ola Liljedahl wrote:

>>

>> On 20/06/2017, 15:04, "Savolainen, Petri (Nokia - FI/Espoo)"

>> <petri.savolainen@nokia.com> wrote:

>>

>>>

>>>

>>>> +++ b/platform/linux-generic/include/odp_bitset.h

>>>> @@ -0,0 +1,210 @@

>>>> +/* Copyright (c) 2017, ARM Limited

>>>> + * All rights reserved.

>>>> + *

>>>> + * SPDX-License-Identifier:     BSD-3-Clause

>>>> + */

>>>> +

>>>> +#ifndef _ODP_BITSET_H_

>>>> +#define _ODP_BITSET_H_

>>>> +

>>>> +#include <odp_cpu.h>

>>>> +

>>>> +#include <limits.h>

>>>> +

>>>>

>>>> +/***********************************************************************

>>>> *

>>>> ******

>>>> + * bitset abstract data type

>>>> +

>>>>

>>>> *************************************************************************

>>>> *

>>>> ***/

>>>> +/* This could be a struct of scalars to support larger bit sets */

>>>> +

>>>> +/*

>>>> + * Size of atomic bit set. This limits the max number of threads,

>>>> + * scheduler groups and reorder windows. On ARMv8/64-bit and x86-64,

>>>> the

>>>> + * (lock-free) max is 128

>>>> + */

>>>> +

>>>> +/* Find a suitable data type that supports lock-free atomic operations

>>>> */

>>>> +#if defined(__ARM_ARCH) &&  __ARM_ARCH == 8 &&  __ARM_64BIT_STATE == 1

>>>> &&

>>>

>>> Why ifdef ARM? Why this code is not in arch directory ?

>> Why is this car red?

>> Because I like it like that.

> 

> I think it was agreed that arch-specific code should go to arch/ dirs,

> wasn't it?

> 

> 

yes, it has to be there.

Maxim.
Ola Liljedahl June 21, 2017, 8:08 p.m. | #5
On 21/06/2017, 22:00, "Dmitry Eremin-Solenikov"
<dmitry.ereminsolenikov@linaro.org> wrote:

>On 21.06.2017 21:14, Ola Liljedahl wrote:

>> 

>> On 20/06/2017, 15:04, "Savolainen, Petri (Nokia - FI/Espoo)"

>> <petri.savolainen@nokia.com> wrote:

>> 

>>>

>>>

>>>> +++ b/platform/linux-generic/include/odp_bitset.h

>>>> @@ -0,0 +1,210 @@

>>>> +/* Copyright (c) 2017, ARM Limited

>>>> + * All rights reserved.

>>>> + *

>>>> + * SPDX-License-Identifier:     BSD-3-Clause

>>>> + */

>>>> +

>>>> +#ifndef _ODP_BITSET_H_

>>>> +#define _ODP_BITSET_H_

>>>> +

>>>> +#include <odp_cpu.h>

>>>> +

>>>> +#include <limits.h>

>>>> +

>>>>

>>>> 

>>>>+/*********************************************************************

>>>>**

>>>> *

>>>> ******

>>>> + * bitset abstract data type

>>>> +

>>>>

>>>> 

>>>>***********************************************************************

>>>>**

>>>> *

>>>> ***/

>>>> +/* This could be a struct of scalars to support larger bit sets */

>>>> +

>>>> +/*

>>>> + * Size of atomic bit set. This limits the max number of threads,

>>>> + * scheduler groups and reorder windows. On ARMv8/64-bit and x86-64,

>>>> the

>>>> + * (lock-free) max is 128

>>>> + */

>>>> +

>>>> +/* Find a suitable data type that supports lock-free atomic

>>>>operations

>>>> */

>>>> +#if defined(__ARM_ARCH) &&  __ARM_ARCH == 8 &&  __ARM_64BIT_STATE ==

>>>>1

>>>> &&

>>>

>>> Why ifdef ARM? Why this code is not in arch directory ?

>> Why is this car red?

>> Because I like it like that.

>

>I think it was agreed that arch-specific code should go to arch/ dirs,

>wasn't it?

If you bend backwards enough, you will always touch ground again with your
hands. It doesn¹t mean it is meaningful to do so. Especially not when you
can just lean forward and accomplish the same without the pain.

>

>

>-- 

>With best wishes

>Dmitry
Dmitry Eremin-Solenikov June 21, 2017, 8:09 p.m. | #6
On 21.06.2017 23:08, Ola Liljedahl wrote:
> 

> On 21/06/2017, 22:00, "Dmitry Eremin-Solenikov"

> <dmitry.ereminsolenikov@linaro.org> wrote:

> 

>> On 21.06.2017 21:14, Ola Liljedahl wrote:

>>>

>>> On 20/06/2017, 15:04, "Savolainen, Petri (Nokia - FI/Espoo)"

>>> <petri.savolainen@nokia.com> wrote:

>>>

>>>>

>>>>

>>>>> +++ b/platform/linux-generic/include/odp_bitset.h

>>>>> @@ -0,0 +1,210 @@

>>>>> +/* Copyright (c) 2017, ARM Limited

>>>>> + * All rights reserved.

>>>>> + *

>>>>> + * SPDX-License-Identifier:     BSD-3-Clause

>>>>> + */

>>>>> +

>>>>> +#ifndef _ODP_BITSET_H_

>>>>> +#define _ODP_BITSET_H_

>>>>> +

>>>>> +#include <odp_cpu.h>

>>>>> +

>>>>> +#include <limits.h>

>>>>> +

>>>>>

>>>>>

>>>>> +/*********************************************************************

>>>>> **

>>>>> *

>>>>> ******

>>>>> + * bitset abstract data type

>>>>> +

>>>>>

>>>>>

>>>>> ***********************************************************************

>>>>> **

>>>>> *

>>>>> ***/

>>>>> +/* This could be a struct of scalars to support larger bit sets */

>>>>> +

>>>>> +/*

>>>>> + * Size of atomic bit set. This limits the max number of threads,

>>>>> + * scheduler groups and reorder windows. On ARMv8/64-bit and x86-64,

>>>>> the

>>>>> + * (lock-free) max is 128

>>>>> + */

>>>>> +

>>>>> +/* Find a suitable data type that supports lock-free atomic

>>>>> operations

>>>>> */

>>>>> +#if defined(__ARM_ARCH) &&  __ARM_ARCH == 8 &&  __ARM_64BIT_STATE ==

>>>>> 1

>>>>> &&

>>>>

>>>> Why ifdef ARM? Why this code is not in arch directory ?

>>> Why is this car red?

>>> Because I like it like that.

>>

>> I think it was agreed that arch-specific code should go to arch/ dirs,

>> wasn't it?

> If you bend backwards enough, you will always touch ground again with your

> hands. It doesn¹t mean it is meaningful to do so. Especially not when you

> can just lean forward and accomplish the same without the pain.


Ola, sometimes it is necessary to bend backwards.

-- 
With best wishes
Dmitry

Patch hide | download patch | download mbox

diff --git a/platform/linux-generic/Makefile.am b/platform/linux-generic/Makefile.am
index 4690a650..b869fd4b 100644
--- a/platform/linux-generic/Makefile.am
+++ b/platform/linux-generic/Makefile.am
@@ -146,6 +146,7 @@  noinst_HEADERS = \
 		  ${srcdir}/include/odp_atomic_internal.h \
 		  ${srcdir}/include/odp_buffer_inlines.h \
 		  ${srcdir}/include/odp_bitmap_internal.h \
+		  ${srcdir}/include/odp_bitset.h \
 		  ${srcdir}/include/odp_buffer_internal.h \
 		  ${srcdir}/include/odp_classification_datamodel.h \
 		  ${srcdir}/include/odp_classification_inlines.h \
diff --git a/platform/linux-generic/include/odp_bitset.h b/platform/linux-generic/include/odp_bitset.h
new file mode 100644
index 00000000..69b1a8dc
--- /dev/null
+++ b/platform/linux-generic/include/odp_bitset.h
@@ -0,0 +1,210 @@ 
+/* Copyright (c) 2017, ARM Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier:     BSD-3-Clause
+ */
+
+#ifndef _ODP_BITSET_H_
+#define _ODP_BITSET_H_
+
+#include <odp_cpu.h>
+
+#include <limits.h>
+
+/******************************************************************************
+ * bitset abstract data type
+ *****************************************************************************/
+/* This could be a struct of scalars to support larger bit sets */
+
+/*
+ * Size of atomic bit set. This limits the max number of threads,
+ * scheduler groups and reorder windows. On ARMv8/64-bit and x86-64, the
+ * (lock-free) max is 128
+ */
+
+/* Find a suitable data type that supports lock-free atomic operations */
+#if defined(__ARM_ARCH) &&  __ARM_ARCH == 8 &&  __ARM_64BIT_STATE == 1 && \
+	defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ == 16
+#define LOCKFREE16
+typedef __int128 bitset_t;
+#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT128__)
+
+#elif __GCC_ATOMIC_LLONG_LOCK_FREE == 2 && \
+	__SIZEOF_LONG_LONG__ != __SIZEOF_LONG__
+typedef unsigned long long bitset_t;
+#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_LONG_LONG__)
+
+#elif __GCC_ATOMIC_LONG_LOCK_FREE == 2 && __SIZEOF_LONG__ != __SIZEOF_INT__
+typedef unsigned long bitset_t;
+#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_LONG__)
+
+#elif __GCC_ATOMIC_INT_LOCK_FREE == 2
+typedef unsigned int bitset_t;
+#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT__)
+
+#else
+/* Target does not support lock-free atomic operations */
+typedef unsigned int bitset_t;
+#define ATOM_BITSET_SIZE (CHAR_BIT * __SIZEOF_INT__)
+#endif
+
+#if ATOM_BITSET_SIZE <= 32
+
+static inline bitset_t bitset_mask(uint32_t bit)
+{
+	return 1UL << bit;
+}
+
+/* Return first-bit-set with StdC ffs() semantics */
+static inline uint32_t bitset_ffs(bitset_t b)
+{
+	return __builtin_ffsl(b);
+}
+
+/* Load-exclusive with memory ordering */
+static inline bitset_t bitset_monitor(bitset_t *bs, int mo)
+{
+	return monitor32(bs, mo);
+}
+
+#elif ATOM_BITSET_SIZE <= 64
+
+static inline bitset_t bitset_mask(uint32_t bit)
+{
+	return 1ULL << bit;
+}
+
+/* Return first-bit-set with StdC ffs() semantics */
+static inline uint32_t bitset_ffs(bitset_t b)
+{
+	return __builtin_ffsll(b);
+}
+
+/* Load-exclusive with memory ordering */
+static inline bitset_t bitset_monitor(bitset_t *bs, int mo)
+{
+	return monitor64(bs, mo);
+}
+
+#elif ATOM_BITSET_SIZE <= 128
+
+static inline bitset_t bitset_mask(uint32_t bit)
+{
+	if (bit < 64)
+		return 1ULL << bit;
+	else
+		return (unsigned __int128)(1ULL << (bit - 64)) << 64;
+}
+
+/* Return first-bit-set with StdC ffs() semantics */
+static inline uint32_t bitset_ffs(bitset_t b)
+{
+	if ((uint64_t)b != 0)
+		return __builtin_ffsll((uint64_t)b);
+	else if ((b >> 64) != 0)
+		return __builtin_ffsll((uint64_t)(b >> 64)) + 64;
+	else
+		return 0;
+}
+
+/* Load-exclusive with memory ordering */
+static inline bitset_t bitset_monitor(bitset_t *bs, int mo)
+{
+	return monitor128(bs, mo);
+}
+
+#else
+#error Unsupported size of bit sets (ATOM_BITSET_SIZE)
+#endif
+
+/* Atomic load with memory ordering */
+static inline bitset_t atom_bitset_load(bitset_t *bs, int mo)
+{
+#ifdef LOCKFREE16
+	return __lockfree_load_16(bs, mo);
+#else
+	return __atomic_load_n(bs, mo);
+#endif
+}
+
+/* Atomic bit set with memory ordering */
+static inline void atom_bitset_set(bitset_t *bs, uint32_t bit, int mo)
+{
+#ifdef LOCKFREE16
+	(void)__lockfree_fetch_or_16(bs, bitset_mask(bit), mo);
+#else
+	(void)__atomic_fetch_or(bs, bitset_mask(bit), mo);
+#endif
+}
+
+/* Atomic bit clear with memory ordering */
+static inline void atom_bitset_clr(bitset_t *bs, uint32_t bit, int mo)
+{
+#ifdef LOCKFREE16
+	(void)__lockfree_fetch_and_16(bs, ~bitset_mask(bit), mo);
+#else
+	(void)__atomic_fetch_and(bs, ~bitset_mask(bit), mo);
+#endif
+}
+
+/* Atomic exchange with memory ordering */
+static inline bitset_t atom_bitset_xchg(bitset_t *bs, bitset_t neu, int mo)
+{
+#ifdef LOCKFREE16
+	return __lockfree_exchange_16(bs, neu, mo);
+#else
+	return __atomic_exchange_n(bs, neu, mo);
+#endif
+}
+
+/* Atomic compare&exchange with memory ordering */
+static inline bitset_t atom_bitset_cmpxchg(bitset_t *bs, bitset_t *old,
+					   bitset_t neu, bool weak,
+					   int mo_success, int mo_failure)
+{
+#ifdef LOCKFREE16
+	return __lockfree_compare_exchange_16(
+		bs, old, neu, weak, mo_success, mo_failure);
+#else
+	return __atomic_compare_exchange_n(
+		bs, old, neu, weak, mo_success, mo_failure);
+#endif
+}
+
+/* Return a & ~b */
+static inline bitset_t bitset_andn(bitset_t a, bitset_t b)
+{
+	return a & ~b;
+}
+
+static inline bool bitset_is_eql(bitset_t a, bitset_t b)
+{
+	return a == b;
+}
+
+static inline bitset_t bitset_clr(bitset_t bs, uint32_t bit)
+{
+	return bs & ~bitset_mask(bit);
+}
+
+static inline bitset_t bitset_set(bitset_t bs, uint32_t bit)
+{
+	return bs | bitset_mask(bit);
+}
+
+static inline bitset_t bitset_null(void)
+{
+	return 0U;
+}
+
+static inline bool bitset_is_null(bitset_t a)
+{
+	return a == 0U;
+}
+
+static inline bool bitset_is_set(bitset_t a, uint32_t bit)
+{
+	return (a & bitset_mask(bit)) != 0;
+}
+
+#endif