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. See platform/linux-generic/include/odp_config_internal.h for further build time configuration. 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: - [4/8] and [8/8] cause checkpatch.pl to emit some output; no code was changed as the output is superfluous. 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 (8): test: odp_sched_latency: misc improvements test: odp_pktio_ordered: add queue size pktio: loop: use handle instead of pointer to buffer Add arch/ files Add a bitset Add a concurrent queue Add queue accessor methods Add scalable scheduler platform/linux-generic/Makefile.am | 15 +- platform/linux-generic/arch/arm/odp_atomic.h | 210 +++ platform/linux-generic/arch/arm/odp_cpu.h | 63 + 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 | 10 + platform/linux-generic/arch/mips64/odp_cpu.h | 10 + platform/linux-generic/arch/powerpc/odp_cpu.h | 10 + platform/linux-generic/arch/x86/odp_cpu.h | 41 + .../include/odp/api/plat/schedule_types.h | 20 +- platform/linux-generic/include/odp_bitset.h | 210 +++ .../linux-generic/include/odp_config_internal.h | 19 +- platform/linux-generic/include/odp_llqueue.h | 309 ++++ .../linux-generic/include/odp_queue_internal.h | 120 +- platform/linux-generic/include/odp_schedule_if.h | 166 +- .../include/odp_schedule_ordered_internal.h | 149 ++ .../include/odp_schedule_scalable_config.h | 52 + platform/linux-generic/m4/odp_schedule.m4 | 55 +- platform/linux-generic/odp_classification.c | 4 +- platform/linux-generic/odp_packet_io.c | 89 +- platform/linux-generic/odp_queue.c | 2 +- platform/linux-generic/odp_queue_scalable.c | 917 ++++++++++ platform/linux-generic/odp_schedule_if.c | 36 +- platform/linux-generic/odp_schedule_scalable.c | 1920 ++++++++++++++++++++ .../linux-generic/odp_schedule_scalable_ordered.c | 284 +++ platform/linux-generic/odp_traffic_mngr.c | 7 +- platform/linux-generic/pktio/loop.c | 11 +- test/common_plat/performance/odp_pktio_ordered.c | 4 + test/common_plat/performance/odp_sched_latency.c | 68 +- 29 files changed, 5007 insertions(+), 94 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_schedule_ordered_internal.h create mode 100644 platform/linux-generic/include/odp_schedule_scalable_config.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.12.2
