The libdispatch Project, (a.k.a. Grand Central Dispatch), for concurrency on multicore hardware

Grand Central Dispatch

Grand Central Dispatch (GCD or libdispatch) provides comprehensive support for concurrent code execution on multicore hardware.

libdispatch is currently available on all Darwin platforms. This project aims to make a modern version of libdispatch available on all other Swift platforms. To do this, we will implement as much of the portable subset of the API as possible, using the existing open source C implementation.

libdispatch on Darwin is a combination of logic in the xnu kernel alongside the user-space Library. The kernel has the most information available to balance workload across the entire system. As a first step, however, we believe it is useful to bring up the basic functionality of the library using user-space pthread primitives on Linux. Eventually, a Linux kernel module could be developed to support more informed thread scheduling.

Project Status

A port of libdispatch to Linux has been completed. On Linux, since Swift 3, swift-corelibs-libdispatch has been included in all Swift releases and is used by other swift-corelibs projects.

Opportunities to contribute and on-going work include:

  1. Develop a test suite for the Swift APIs of libdispatch.
  2. Enhance libdispatch as needed to support Swift language evolution and the needs of the other Core Libraries projects.

Build and Install

For detailed instructions on building and installing libdispatch, see INSTALL.md

Testing

For detailed instructions on testing libdispatch, see TESTING.md

Comments
  • implement pthread_workqueue within libdispatch

    implement pthread_workqueue within libdispatch

    Provide an implementation of the pthread_workqueue functionality as a fully integrated component of libdispatch. Integration of the workqueue implementation into the dispatch code base simplifies the process of evolving the APIs between the two layers and thus prepares for future optimization and enhancements.

    Initially, the integrated pthread_workqueue is only enabled by default on Linux. Most of the internals are built on pthread APIs and thus should be fairly portable. However, Linux-specific code is used to dynamically estimate the number of runnable worker threads by reading /proc. Porting the thread pool management code to non-Linux platforms would entail providing similar functionality for those platforms (or otherwise restructuring the manager).

  • build: add a cmake based build system

    build: add a cmake based build system

    This is far from complete, but is sufficient to build a Linux version of libdispatch. It shows what a potential cmake based build system could look like, and if desired can be completed to build all the various flavours with cmake.

  • [SR-761] dispatch_async is

    [SR-761] dispatch_async is "not very concurrent" and has a 1s overhead on Linux

    | | | |------------------|-----------------| |Previous ID | SR-761 | |Radar | None | |Original Reporter | @drewcrawford | |Type | Bug | |Status | Resolved | |Resolution | Done |

    Attachment: Download

    Environment

    Linux x64
    swift-DEVELOPMENT-SNAPSHOT-2016-02-08-a

    Additional Detail from JIRA

    | | | |------------------|-----------------| |Votes | 0 | |Component/s | libdispatch | |Labels | Bug, Linux | |Assignee | frankeh (JIRA) | |Priority | Medium |

    md5: b2ed8e5cf6e4eaac3f1ede31d47b998f

    Issue Description:

    The attached program enqueues 10 blocks of work on the default queue. On Darwin, all blocks run in parallel, and the program completes in 5 seconds:

    0.0 block 0 enter
    0.0 block 7 enter
    0.0 block 1 enter
    0.0 block 3 enter
    0.0 block 2 enter
    0.0 block 4 enter
    0.0 block 5 enter
    0.0 block 6 enter
    0.0 block 8 enter
    0.0 block 9 enter
    5.0 block 1 leave
    5.0 block 6 leave
    5.0 block 9 leave
    5.0 block 5 leave
    5.0 block 3 leave
    5.0 block 0 leave
    5.0 block 8 leave
    5.0 block 4 leave
    5.0 block 2 leave
    5.0 block 7 leave
    5.0 finished
    

    On Linux however, the blocks enter the queue staggered 1 at a time, 1 second apart. This doubles the runtime of the program:

    0.0 block 1 enter
    0.0 block 0 enter
    1.0 block 2 enter
    2.0 block 3 enter
    3.0 block 4 enter
    4.0 block 5 enter
    5.0 block 1 leave
    5.0 block 0 leave
    5.0 block 6 enter
    5.0 block 7 enter
    5.0 block 8 enter
    6.0 block 2 leave
    6.0 block 9 enter
    7.0 block 3 leave
    8.0 block 4 leave
    9.0 block 5 leave
    10.0 block 6 leave
    10.0 block 7 leave
    10.0 block 8 leave
    11.0 block 9 leave
    11.0 finished
    

    In addition to that (rather large) performance regression, the fact that dispatch_async and/or the default queue has in practice a constant-time overhead of 1 second on Linux breaks a lot of my Darwin code, which expects a Darwin-like overhead for this call.

  • Rework of Dispatch overlay for Linux

    Rework of Dispatch overlay for Linux

    The lack of Objective-C and associated bridging when importing the libdispatch header files into Swift caused a number of problems including (a) missing ref count operations in Swift compiled code (b) SR-739, dispatch types not being upcastable to dispatch_object_t (c) SR-740, dispatch types not being upcastable to AnyObject (d) SR-737, dispatch types being imported as COpaquePointer

    This commit fixes all of these issues by injecting a complete Swift overlay layer that wraps the native libdispatch objects and native APIs.

    The C header files are now imported into a distinct CDispatch module that is not made available to Swift client code (which continues to import Dispatch). Code is added to Dispatch.swift to mirror the native CDispatch APIs up to the Swift Dispatch API and to wrap/unwrap values as needed across that boundary.

    This wrapping layer does add some minor space and time overheads, but after extensively exploring implementing the Swift object model within the C code of libdispatch (to avoid introducing this overhead), I concluded that the necessary changes to libdispatch would be fairly invasive, and therefore were not justified at this point in the development of the Swift/Linux port of libdispatch.

  • [SR-7039] can't use -static-stdlib (or -static-executable) with any Dispatch using app

    [SR-7039] can't use -static-stdlib (or -static-executable) with any Dispatch using app

    | | | |------------------|-----------------| |Previous ID | SR-7039 | |Radar | rdar://problem/38913393 | |Original Reporter | @weissi | |Type | Bug | |Status | Resolved | |Resolution | Done |

    Additional Detail from JIRA

    | | | |------------------|-----------------| |Votes | 6 | |Component/s | libdispatch | |Labels | Bug | |Assignee | @spevans | |Priority | Medium |

    md5: b75d9276b711df9f7b981f99923ed483

    is duplicated by:

    • SR-7085 Link error related to libdispatch when using -static-stdlib on Linux

    relates to:

    • SR-9368 libdispatch_static unit tests are disabled
    • SR-10625 tests for -static-*

    Issue Description:

    repro

    mkdir /tmp/test && cd /tmp/test && swift package init --type=executable
    cat > Sources/test/main.swift <<EOF
    import Dispatch
    let q = DispatchQueue(label: "q")
    q.sync { print("hello") }
    EOF
    swift build -Xswiftc -static-stdlib
    

    expected

    works, just like without the -static-stdlib

    actual

    $ rm -rf .build && /usr/local/swift/swift-4.0.2-RELEASE-ubuntu16.04/usr/bin/swift build -Xswiftc -static-stdlib
    Compile Swift Module 'test' (1 sources)
    Linking ./.build/x86_64-unknown-linux/debug/test
    /usr/bin/ld.gold: error: cannot find -ldispatch
    /tmp/test/Sources/test/main.swift:2: error: undefined reference to '_T08Dispatch0A5QueueCMa'
    /tmp/test/Sources/test/main.swift:2: error: undefined reference to '_T08Dispatch0A5QueueCACSS5label_AA0A3QoSV3qosAC10AttributesV10attributesAC20AutoreleaseFrequencyO011autoreleaseI0ACSg6targettcfcfA0_'
    /tmp/test/Sources/test/main.swift:2: error: undefined reference to '_T08Dispatch0A5QueueCACSS5label_AA0A3QoSV3qosAC10AttributesV10attributesAC20AutoreleaseFrequencyO011autoreleaseI0ACSg6targettcfcfA1_'
    /tmp/test/Sources/test/main.swift:2: error: undefined reference to '_T08Dispatch0A5QueueCACSS5label_AA0A3QoSV3qosAC10AttributesV10attributesAC20AutoreleaseFrequencyO011autoreleaseI0ACSg6targettcfcfA2_'
    /tmp/test/Sources/test/main.swift:2: error: undefined reference to '_T08Dispatch0A5QueueCACSS5label_AA0A3QoSV3qosAC10AttributesV10attributesAC20AutoreleaseFrequencyO011autoreleaseI0ACSg6targettcfcfA3_'
    /tmp/test/Sources/test/main.swift:2: error: undefined reference to '_T08Dispatch0A5QueueCACSS5label_AA0A3QoSV3qosAC10AttributesV10attributesAC20AutoreleaseFrequencyO011autoreleaseI0ACSg6targettcfC'
    clang: error: linker command failed with exit code 1 (use -v to see invocation)
    <unknown>:0: error: link command failed with exit code 1 (use -v to see invocation)
    error: terminated(1): /usr/local/swift/swift-4.0.2-RELEASE-ubuntu16.04/usr/bin/swift-build-tool -f /tmp/test/.build/debug.yaml main
    

    cause

    libdispatch.a isn't shipped even though it could be. Since this patch libdispatch.a should work but it needs to be compiled with

    ./configure --enable static=yes
    
  • Merge darwin/libdispatch-1121 to master

    Merge darwin/libdispatch-1121 to master

    Merge tag darwin/libdispatch-1121 on darwin/trunk.

    This includes the latest Apple source drop libdispatch-1121 (up from libdispatch-913.1.4 in #447), on top of darwin/darwin-012.

  • [SR-1923] Building Foundation with lib dispatch support fails with a glibc module error

    [SR-1923] Building Foundation with lib dispatch support fails with a glibc module error

    | | | |------------------|-----------------| |Previous ID | SR-1923 | |Radar | None | |Original Reporter | @phausler | |Type | Bug | |Status | Resolved | |Resolution | Done |

    Additional Detail from JIRA

    | | | |------------------|-----------------| |Votes | 1 | |Component/s | libdispatch | |Labels | Bug | |Assignee | None | |Priority | Medium |

    md5: f5f4c29f9470e2d6aab03501b79a0183

    Issue Description:

    On Ubuntu 15 with the build command of ./swift/utils/build-script -r --foundation --libdispatch
    Swift fails to compile modular components for dispatch:

    <module-includes>:1:10: note: in file included from <module-includes>:1:
    #include "dispatch.h"
             ^
    /home/phausler/Documents/Public/swift-corelibs-libdispatch/dispatch/dispatch.h:60:10: note: in file included from /home/phausler/Documents/Public/swift-corelibs-libdispatch/dispatch/dispatch.h:60:
    #include <dispatch/io.h>
             ^
    /home/phausler/Documents/Public/swift-corelibs-libdispatch/dispatch/io.h:359:2: error: declaration of 'off_t' must be imported from module 'SwiftGlibc.C.stdio' before it is required
            off_t offset,
            ^
    /usr/include/stdio.h:90:17: note: previous declaration is here
    typedef __off_t off_t;
                    ^
    
  • Replace uses of @_silgen_name with uses of a shims header.

    Replace uses of @_silgen_name with uses of a shims header.

    Said shims header is in the main Swift repo because it's shared with the Darwin Dispatch overlay. This is the same effort as apple/swift#5854, but for corelibs.

    No intended functionality change.

  • Android support

    Android support

    This changeset adds support for Android cross-compilation with the same restrictions applied to swift project.

    Options

    • --disable-build-tests: tests are failing to be built due to the lack of spawn. Until this is fixed, the flag will be useful to complete compilation
    • --with-android-ndk: Android NDK path to be used as a base for cross toolchain, SDK and support files.
    • --with-android-ndk-gcc-version: NDK GCC version to be used (defaults to 4.9)
    • --with-android-api-level: API version to be used for compilation
    • --enable-android: Enabled Android cross-compilation. In this implementation, as it is being done right now in swift, this is enforcing arm-linux-androideabi armeabi-v7a.

    Issues

    There are a few things in this changeset that I'd like to iterate, assuming there are better or more generic solution that can be applied:

    • [x] src/shims/android includes: In this directory I created sys/sysctl.h + syscall.h to redirect headers to their locations in Android. -- update: moved to compiler conditionals instead of include overlay. commit
    • [x] src/shims/android libraries: libpthread.a + librt.a are dummy libraries because of the difference described here. To avoid this both libkqueue and libpwq should be modified to avoid asking libtool to link against them.
    • [x] configure.ac and src/Makefile.am: This the first time I deal with autotools, so I think there should be a better way to implement this. (C|CXX|LD)FLAGS params I think will be needed explicitly declared somewhere to enable cross compilation, but maybe in AM_$0_FLAGS? I think there are some overwrites in the am files that were causing troubles, but they can be fixed if this is the right direction. Removing flags from ac_configure_args like that with sed seems like a terrible idea, maybe both libkqueue and libpwq need to be extended somehow to support this in a better way?
    • [x] and more…

    Build

    This is an example call to compile libdispatch for Android. This is similarly formatted to the call that build script in swift does to compile libdispatch.

    $ sh autogen.sh
    $ export SWIFT_ANDROID=<...>
    $ export NDK_PATH=<...>
    $ env \
    CC="$SWIFT_ANDROID/build/Ninja-ReleaseAssert/llvm-linux-x86_64/bin/clang" \
    CXX="$SWIFT_ANDROID/build/Ninja-ReleaseAssert/llvm-linux-x86_64/bin/clang++" \
    SWIFTC="$SWIFT_ANDROID/build/Ninja-ReleaseAssert/swift-linux-x86_64/bin/swiftc" \
    $SWIFT_ANDROID/swift-corelibs-libdispatch/configure \
    --with-swift-toolchain="$SWIFT_ANDROID/build/Ninja-ReleaseAssert/swift-linux-x86_64/" \
    --with-build-variant=release \
    --enable-android \
    --host=arm-linux-androideabi \
    --with-android-ndk=$NDK_PATH \
    --with-android-api-level=21 \
    --disable-build-tests
    $ make
    

    Side note: va_list issue mentioned in #155 is affecting the build process. There's no patch for that issues here, to avoid mixing problems that may be addressed in different ways.

    Outcome

    This compilation process creates the shared library with the following ELF header:

    ELF Header:
      Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 
      Class:                             ELF32
      Data:                              2's complement, little endian
      Version:                           1 (current)
      OS/ABI:                            UNIX - System V
      ABI Version:                       0
      Type:                              DYN (Shared object file)
      Machine:                           ARM
      Version:                           0x1
      Entry point address:               0x0
      Start of program headers:          52 (bytes into file)
      Start of section headers:          1060700 (bytes into file)
      Flags:                             0x5000200, Version5 EABI, soft-float ABI
      Size of this header:               52 (bytes)
      Size of program headers:           32 (bytes)
      Number of program headers:         9
      Size of section headers:           40 (bytes)
      Number of section headers:         50
      Section header string table index: 49
    

    and dependencies

     0x00000001 (NEEDED)                     Shared library: [libstdc++.so]
     0x00000001 (NEEDED)                     Shared library: [libm.so]
     0x00000001 (NEEDED)                     Shared library: [libc.so]
     0x00000001 (NEEDED)                     Shared library: [libdl.so]
    
  • [SR-6084] libdispatch missing from Trunk Development snapshots

    [SR-6084] libdispatch missing from Trunk Development snapshots

    | | | |------------------|-----------------| |Previous ID | SR-6084 | |Radar | rdar://problem/35040697 | |Original Reporter | dowobeha (JIRA User) | |Type | Bug | |Status | Resolved | |Resolution | Done |

    Additional Detail from JIRA

    | | | |------------------|-----------------| |Votes | 1 | |Component/s | libdispatch | |Labels | Bug | |Assignee | dgrove-oss (JIRA) | |Priority | Medium |

    Watchers: @shahmishal

    md5: 5685fbff17fef7e5a99d2d3c5371f970

    Issue Description:

    In all trunk development releases for Ubuntu 16.04 currently listed on the Swift downloads page, libdispatch is absent.

    #!/bin/bash                                                                                         
    
    dates="2017-09-22 2017-09-23 2017-09-24 2017-09-25 2017-09-26 2017-09-27 2017-09-28 2017-09-29 2017-09-30 2017-10-01 2017-10-06"
    
    for date in ${dates}; do
    
        echo "Downloading swift-DEVELOPMENT-SNAPSHOT-${date}-a-ubuntu16.04.tar.gz..."
        wget https://swift.org/builds/development/ubuntu1604/swift-DEVELOPMENT-SNAPSHOT-${date}-a/swift-DEVELOPMENT-SNAPSHOT-${date}-a-ubuntu16.04.tar.gz &> /dev/null
    
        tar xfvz swift-DEVELOPMENT-SNAPSHOT-${date}-a-ubuntu16.04.tar.gz &> /dev/null
    
    done
    
    echo "Searching for libdispatch..."
    find swift-DEVELOPMENT-SNAPSHOT-* -name "*dispatch*"
    
  • [android] Update headers that were split in NDK 23

    [android] Update headers that were split in NDK 23

    NDK 23 split stdatomic.h up and that causes problems when invoked from C++ files, so use the new bits/stdatomic.h instead as a workaround, as seen in the test for aosp-mirror/[email protected]

    Building libdispatch for Android with the new NDK causes linkage issues in the headers, so I used this same workaround that can be seen in the C++ test for that Bionic commit that split the header up and libdispatch builds for Android again.

    I don't know if there's a better way to fix these linkage issues, so let me know if there is.

  • config, os: add support for Musl libc

    config, os: add support for Musl libc

    According to Musl's FAQ document, __BEGIN_DECLS and __END_DECLS macros come from Glibc private headers, thus we need to define them manually in case those aren't defined.

    Additionally, for Musl we need to override HAVE_DECL_PROGRAM_INVOCATION_SHORT_NAME, for which a corresponding #ifndef was added in config.h.

  • Use restrict keyword for format and message strings

    Use restrict keyword for format and message strings

    The standard C functions called have undefined behavior if restrict is not met, so we should add them to functions calling vsnprintf and other related functions just in case.

  • Performance fix: Lower operations and function calls by checking for zone_address before doing expensive memory reads

    Performance fix: Lower operations and function calls by checking for zone_address before doing expensive memory reads

    Not only does this defer expensive operations to when we can prove they are needed, but also the reduction of casts also help with performance on libdispatch!

  • Introduce a flag to control the path to Swift headers installation.

    Introduce a flag to control the path to Swift headers installation.

    The Swift compiler regards libdispatch headers as runtime resources, located relative to the compiler executable. If we want to distribute a standalone SDK, library and header install path should diverge.

    This PR introduces a flag to manually specify the path to Swift runtime resource directory, which is used to install headers for Swift. Notice that the flag is only effective under ENABLE_SWIFT, and the current behavior is preserved unless the flag is provided.

  • dispatch.h incompatible with gcc / g++ 12

    dispatch.h incompatible with gcc / g++ 12

    $ echo "#include <dispatch/dispatch.h>" > foo.c
    $ gcc foo.c 
    In file included from /usr/include/dispatch/dispatch.h:32,
                     from foo.c:1:
    /usr/include/os/generic_unix_base.h:58:18: error: missing binary operator before token "("
       58 | #if __has_feature(assume_nonnull)
          |                  ^
    /usr/include/os/generic_unix_base.h:72:18: error: missing binary operator before token "("
       72 | #if __has_feature(attribute_availability_swift)
          |                  ^
    /usr/include/os/generic_unix_base.h:97:18: error: missing binary operator before token "("
       97 | #if __has_feature(objc_fixed_enum) || __has_extension(cxx_strong_enums)
          |                  ^
    
Async++ concurrency framework for C++11

Async++ Async++ is a lightweight concurrency framework for C++11. The concept was inspired by the Microsoft PPL library and the N3428 C++ standard pro

Dec 30, 2022
Jan 4, 2023
The C++ Standard Library for Parallelism and Concurrency

Documentation: latest, development (master) HPX HPX is a C++ Standard Library for Concurrency and Parallelism. It implements all of the corresponding

Jan 3, 2023
Go-style concurrency in C

LIBMILL Libmill is a library that introduces Go-style concurrency to C. Documentation For the documentation check the project website: http://libmill.

Dec 31, 2022
A header-only C++ library for task concurrency
A header-only C++ library for task concurrency

transwarp Doxygen documentation transwarp is a header-only C++ library for task concurrency. It allows you to easily create a graph of tasks where eve

Dec 19, 2022
Modern concurrency for C++. Tasks, executors, timers and C++20 coroutines to rule them all

concurrencpp, the C++ concurrency library concurrencpp is a tasking library for C++ allowing developers to write highly concurrent applications easily

Jan 3, 2023
HPX is a C++ Standard Library for Concurrency and Parallelism

HPX is a C++ Standard Library for Concurrency and Parallelism. It implements all of the corresponding facilities as defined by the C++ Standard. Additionally, in HPX we implement functionalities proposed as part of the ongoing C++ standardization process. We also extend the C++ Standard APIs to the distributed case.

Dec 30, 2022
Complementary Concurrency Programs for course "Linux Kernel Internals"

Complementary Programs for course "Linux Kernel Internals" Project Listing tpool: A lightweight thread pool. tinync: A tiny nc implementation using co

Dec 20, 2022
Yet Another Concurrency Library

YACLib YACLib (Yet Another Concurrency Library) is a C++ library for concurrent tasks execution. Documentation Install guide About dependencies Target

Dec 28, 2022
Task System presented in "Better Code: Concurrency - Sean Parent"
Task System presented in

task_system task_system provides a task scheduler for modern C++. The scheduler manages an array of concurrent queues A task, when scheduled, is enque

Dec 7, 2022
Laughably simple Actor concurrency framework for C++20

Light Actor Framework Concurrency is a breeze. Also a nightmare, if you ever used synchronization techniques. Mostly a nightmare, though. This tiny li

Dec 27, 2022
Deadlockempire.github.io - The Deadlock Empire: Slay dragons, learn concurrency!

The Deadlock Empire A game that teaches locking and concurrency. It runs on https://deadlockempire.github.io. Contributing We gladly welcome all contr

Dec 23, 2022
Libgo - Go-style concurrency in C++11
Libgo - Go-style concurrency in C++11

libgo libgo -- a coroutine library and a parallel Programming Library Libgo is a stackful coroutine library for collaborative scheduling written in C+

Dec 26, 2022
The RaftLib C++ library, streaming/dataflow concurrency via C++ iostream-like operators

RaftLib is a C++ Library for enabling stream/data-flow parallel computation. Using simple right shift operators (just like the C++ streams that you wo

Dec 24, 2022
BoloPi Software Project

RT-Thread For Bolopi 中文页 Overview Bolopi-F1 is a all io extracted for f1c100s development board.Such like 40pin rgb lcd,dvp(camera),audio,tv in (cvbs)

Dec 15, 2022
Operating system project - implementing scheduling algorithms and some system calls for XV6 OS

About XV6 xv6 is a modern reimplementation of Sixth Edition Unix in ANSI C for multiprocessor x86 and RISC-V systems. It was created for pedagogical p

Dec 22, 2022
RocketOS is a Unix based OS that uses legacy BIOS and GRUB and is written in C17. It is being developed for educational purposes primarily, but it still is a serious project. It is currently in its infancy.

RocketOS What is RocketOS? RocketOS is a Unix based OS that uses legacy BIOS and GRUB and is written in C17. It is being developed for educational pur

Sep 19, 2022
Open source re-creation of the copenheimer project.

openheimer Open source re-creation of the copenheimer project. Stage 1: Completed! - Make a extremely fast minecraft server scanner that does the hand

Dec 14, 2022
CppThreadPool - The original intention of this project is to learn the new C++20 standard in use.

CppThreadPool Introduction The original intention of this project is to learn the new C++20 standard in use. Therefore, make sure your compiler suppor

Sep 27, 2022