This work derives from Ola Liljedahl's prototype [1] which introduced a scalable scheduler design based on primarily lock-free algorithms and data structures designed to decrease contention. A thread searches through a data structure containing only queues that are both non-empty and allowed to be scheduled to that thread. Strict priority scheduling is respected, and (W)RR scheduling may be used within queues of the same priority. Lastly, pre-scheduling or stashing is not employed since it is optional functionality that can be implemented in the application.
In addition to scalable ring buffers, the algorithm also uses unbounded concurrent queues. LL/SC and CAS variants exist in cases where absense of ABA problem cannot be proved, and also in cases where the compiler's atomic built-ins may not be lowered to the desired instruction(s). Finally, a version of the algorithm that uses locks is also provided. Use --enable-schedule-scalable to conditionally compile this scheduler into the library. [1] https://lists.linaro.org/pipermail/lng-odp/2016-September/025682.html On checkpatch.pl: - [2/5] and [5/5] have checkpatch.pl issues that are superfluous v7: - Rebase against new modular queue interface - Duplicate arch files under mips64 and powerpc - Fix sched->order_lock() - Loop until all deferred events have been enqueued - Implement ord_enq_multi() - Fix ordered_lock/unlock - Revert stylistic changes - Add default xfactor - Remove changes to odp_sched_latency - Remove ULL suffix to alleviate Clang build v6: - Move conversions into scalable scheduler to alleviate #ifdefs - Remove unnecessary prefetch - Fix ARMv8 build v5: - Allocate cache aligned memory using shm pool APIs - Move more code to scalable scheduler specific files - Remove CONFIG_SPLIT_READWRITE - Fix 'make distcheck' issue v4: - Fix a couple more checkpatch.pl issues v3: - Only conditionally compile scalable scheduler and queue - Move some code to arch/ dir - Use a single shm block for queues instead of block-per-queue - De-interleave odp_llqueue.h - Use compiler macros to determine ATOM_BITSET_SIZE - Incorporated queue size changes - Dropped 'ODP_' prefix on config and moved to other files - Dropped a few patches that were send independently to the list v2: - Move ARMv8 issues and other fixes into separate patches - Abstract away some #ifdefs - Fix some checkpatch.pl warnings Brian Brooks (5): test: odp_pktio_ordered: add queue size Add arch/ files Add a bitset Add a concurrent queue Add scalable scheduler platform/linux-generic/Makefile.am | 10 + platform/linux-generic/arch/arm/odp_atomic.h | 210 +++ platform/linux-generic/arch/arm/odp_cpu.h | 65 + platform/linux-generic/arch/arm/odp_cpu_idling.h | 51 + platform/linux-generic/arch/arm/odp_llsc.h | 249 +++ platform/linux-generic/arch/default/odp_cpu.h | 41 + platform/linux-generic/arch/mips64/odp_cpu.h | 41 + platform/linux-generic/arch/powerpc/odp_cpu.h | 41 + platform/linux-generic/arch/x86/odp_cpu.h | 41 + .../include/odp/api/plat/schedule_types.h | 4 +- platform/linux-generic/include/odp_bitset.h | 210 +++ .../linux-generic/include/odp_config_internal.h | 17 +- platform/linux-generic/include/odp_llqueue.h | 309 +++ .../include/odp_queue_scalable_internal.h | 102 + platform/linux-generic/include/odp_schedule_if.h | 2 +- .../linux-generic/include/odp_schedule_scalable.h | 137 ++ .../include/odp_schedule_scalable_config.h | 55 + .../include/odp_schedule_scalable_ordered.h | 132 ++ platform/linux-generic/m4/odp_schedule.m4 | 55 +- platform/linux-generic/odp_queue_if.c | 8 + platform/linux-generic/odp_queue_scalable.c | 1020 ++++++++++ platform/linux-generic/odp_schedule_if.c | 6 + platform/linux-generic/odp_schedule_scalable.c | 1978 ++++++++++++++++++++ .../linux-generic/odp_schedule_scalable_ordered.c | 347 ++++ test/common_plat/performance/odp_pktio_ordered.c | 4 + 25 files changed, 5113 insertions(+), 22 deletions(-) create mode 100644 platform/linux-generic/arch/arm/odp_atomic.h create mode 100644 platform/linux-generic/arch/arm/odp_cpu.h create mode 100644 platform/linux-generic/arch/arm/odp_cpu_idling.h create mode 100644 platform/linux-generic/arch/arm/odp_llsc.h create mode 100644 platform/linux-generic/arch/default/odp_cpu.h create mode 100644 platform/linux-generic/arch/mips64/odp_cpu.h create mode 100644 platform/linux-generic/arch/powerpc/odp_cpu.h create mode 100644 platform/linux-generic/arch/x86/odp_cpu.h create mode 100644 platform/linux-generic/include/odp_bitset.h create mode 100644 platform/linux-generic/include/odp_llqueue.h create mode 100644 platform/linux-generic/include/odp_queue_scalable_internal.h create mode 100644 platform/linux-generic/include/odp_schedule_scalable.h create mode 100644 platform/linux-generic/include/odp_schedule_scalable_config.h create mode 100644 platform/linux-generic/include/odp_schedule_scalable_ordered.h create mode 100644 platform/linux-generic/odp_queue_scalable.c create mode 100644 platform/linux-generic/odp_schedule_scalable.c create mode 100644 platform/linux-generic/odp_schedule_scalable_ordered.c -- 2.13.1
