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 v2: - Move ARMv8 issues and other fixes into separate patches - Abstract away some #ifdefs - Fix some checkpatch.pl warnings Brian Brooks (14): Fix native Clang build on ARMv8 api: queue: Add ring_size Add ODP_CONFIG_QUEUE_SIZE Fix a locking bug test: odp_scheduling: Handle dequeueing from a concurrent queue test: scheduler: Fixup calling release operations Avoid shm namespace collisions and allow shm block per queue Add _odp_packet_to_buf_hdr_ptr() Add scalable scheduler build config Add LL/SC and signaling primitives Add a bitset Add atomic ops for 128-bit scalars Add llqueue, an unbounded concurrent queue Add scalable scheduler Ola Liljedahl (2): linux-generic: ring.c: use required memory orderings helper: cuckootable: Specify queue ring_size configure.ac | 30 +- helper/cuckootable.c | 1 + include/odp/api/spec/queue.h | 5 + platform/linux-generic/Makefile.am | 21 +- .../include/odp/api/plat/schedule_types.h | 20 +- platform/linux-generic/include/odp_atomic16.h | 214 +++ platform/linux-generic/include/odp_bitset.h | 155 ++ .../linux-generic/include/odp_config_internal.h | 91 +- platform/linux-generic/include/odp_llqueue.h | 285 +++ platform/linux-generic/include/odp_llsc.h | 332 ++++ .../linux-generic/include/odp_packet_internal.h | 3 + .../linux-generic/include/odp_queue_internal.h | 122 +- platform/linux-generic/include/odp_schedule_if.h | 166 +- .../include/odp_schedule_ordered_internal.h | 150 ++ platform/linux-generic/m4/odp_schedule.m4 | 55 +- platform/linux-generic/odp_classification.c | 4 +- platform/linux-generic/odp_packet.c | 5 + platform/linux-generic/odp_packet_io.c | 88 +- platform/linux-generic/odp_queue.c | 2 +- platform/linux-generic/odp_queue_scalable.c | 883 +++++++++ platform/linux-generic/odp_schedule_if.c | 36 +- platform/linux-generic/odp_schedule_scalable.c | 1922 ++++++++++++++++++++ .../linux-generic/odp_schedule_scalable_ordered.c | 285 +++ platform/linux-generic/odp_traffic_mngr.c | 7 +- platform/linux-generic/pktio/loop.c | 11 +- platform/linux-generic/pktio/ring.c | 30 +- test/common_plat/performance/odp_sched_latency.c | 68 +- test/common_plat/performance/odp_scheduling.c | 12 +- .../api/classification/odp_classification_basic.c | 8 +- .../classification/odp_classification_test_pmr.c | 42 +- .../validation/api/scheduler/scheduler.c | 11 +- test/common_plat/validation/api/timer/timer.c | 5 +- 32 files changed, 4922 insertions(+), 147 deletions(-) create mode 100644 platform/linux-generic/include/odp_atomic16.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_llsc.h create mode 100644 platform/linux-generic/include/odp_schedule_ordered_internal.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
