Complementary Concurrency Programs for course "Linux Kernel Internals"

Overview

Complementary Programs for course "Linux Kernel Internals"

Project Listing

  • tpool: A lightweight thread pool.
  • tinync: A tiny nc implementation using coroutine.
  • fiber: A user-level thread (fiber) using clone system call.
  • picosh: A minimalist UNIX shell.
  • httpd: A multi-threaded web server.
  • ringbuffer: A lock-less ring buffer.
  • mbus: A concurrent message bus.

License

The above projects are released under the BSD 2 clause license. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Issues
  • Add thread-based RCU

    Add thread-based RCU

    Add the Linux Kernel style thread-based simple RCU. It supports sparse checking [1].

    With sparse, it will report:

    main.c: note: in included file:
    thrd_rcu.h:95:42: warning: Using plain integer as NULL pointer
    thrd_rcu.h:95:42: warning: Using plain integer as NULL pointer
    

    It is from the pthread_mutex_t initializer, we can ignore it.

    [1] https://www.kernel.org/doc/html/latest/dev-tools/sparse.html


    From the ThreadSanitizer report, ignore the volatile type data race warning [1][2], there still have the data race warning.

    [reader 2835343104] 0
    [reader 2826950400] 0
    [reader 2818557696] 0
    [reader 2810164992] 0
    [reader 2801772288] 0
    [updater 2793379584]
    ==================
    WARNING: ThreadSanitizer: data race (pid=434539)
      Write of size 8 at 0x7b0400000000 by thread T6:
        #0 free ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:711 (libtsan.so.0+0x37ab8)
        #1 updater_side /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:41 (main+0x1a38)
    
      Previous read of size 4 at 0x7b0400000000 by thread T5:
        #0 reader_side /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:23 (main+0x1898)
    
      Thread T6 (tid=434546, running) created by main thread at:
        #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605f8)
        #1 main /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:59 (main+0x1429)
    
      Thread T5 (tid=434545, finished) created by main thread at:
        #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605f8)
        #1 main /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:56 (main+0x13fd)
    
    SUMMARY: ThreadSanitizer: data race /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:41 in updater_side
    ==================
    [reader 2784986880] 2793379584
    [reader 2744121088] 2793379584
    [reader 2735728384] 2793379584
    [reader 2727335680] 2793379584
    [reader 2718942976] 2793379584
    ThreadSanitizer: reported 1 warnings
    

    I try to debug it, but cannot figure out where the wrong is. Not sure if it is a false positive or not.

    [1] https://gcc.gnu.org/pipermail/gcc-patches/2020-June/547633.html [2] https://gcc.gnu.org/gcc-11/changes.html

    opened by linD026 11
  • Refactor the convention for coroutines

    Refactor the convention for coroutines

    The macros of coroutine provided in the original version may cause misusing, such as declaring a set of coroutines by wrapping several pairs of cr_begin and cr_end macro in a loop, which may cause unexpected result while someone waits a condition to pass with cr_wait macro and that condition failed. To avoid such misusing, we have to abstract the usage of controlling macros that would be invoked in the coroutine function. With in this version, a set of macros are introduced, which aim to provide standard style for someone to declare or access the coroutine function and its corresponding context. One should declare a coroutine function with cr_func_def macro, and its corresponding context with cr_context macro, the argument name provides to those macros for the same coroutine should be identical. After declaration, one could run a coroutine by cr_run macro. Wrapping a set of cr_run macros in a loop makes several coroutines execute concurrently. Since the declaration of a coroutine funciton is wrapped by macro cr_func_def, there is no need to provide the context as argument of macros that contorl the coroutine, such as cr_begin, cr_end, cr_wait etc. That argument was hardcoded as __ct in the body of those macros. To pass arguments to a coroutine, one can provide a pointer to that argument as parameter of cr_context_init macro, and to extract them in the coroutine, two macros, cr_arg and cr_arg_member, were introduced. Macro cr_arg will cast __ct->arg to the pointer of corresponding type, while cr_arg_member will return a pointer to the specific member of given structure type that __ct->arg points to. Finally, to define a static variable with in the coroutine, one can define them with cr_local macro, which helps to hightlight wheather a variable is a part of that coroutine or just for temporary usage. With the changes made in this version, compiler will raise errors for one of the following situations:

    • Declaring coroutines as several pairs of cr_begin and cr_end with in a loop.
    • The declaration of function of a coroutine or its corresponding context was missed.
    opened by forward-jt 9
  • Add more operation analysis, combine with deletes and inserts variables.

    Add more operation analysis, combine with deletes and inserts variables.

    Add more operation analysis, combine with deletes and inserts variables. And Using the preprocessor to decide the analysis being set or not.

    For example:

    retry     : 187
    contains  : 0
    traversal : 21028166
    fail      : 0
    del       : 0
    ins       : 0
    load      : 63167962
    store     : 4096
    deletes   : 4098
    inserts   : 4098
    "retry"    is the number of retries in the __list_find function.
    "contains" is the number of wait-free contains in the __list_find function that curr pointer pointed.
    "traversal"is the number of list element traversal in the __list_find function.
    "fail"     is the number of CAS() failures.
    "del"      is the number of list_delete operation failed and restart again.
    "ins"      is the number of list_insert operation failed and restart again.
    "deletes"  is the number of linked list elements deleted.
    "inserts"  is the number of linked list elements created.
    "load"     is the number of atomic_load operation in list_delete, list_insert and __list_find.
    "store"    is the number of atomic_store operation in list_delete, list_insert and __list_find.
    

    The following are the new variables to record the operations: rtry is the number of retries in the __list_find function. cons is the number of wait-free contains in the __list_find function that curr pointer pointed. trav is the number of list element traversal in the __list_find function. fail is the number of CAS() failures. del is the number of list_delete operation failed and restart again. ins is the number of list_insert operation failed and restart again.

    opened by linD026 6
  • Fix bug in list_hp_retire function

    Fix bug in list_hp_retire function

    In hp_list project's function : list_hp_retire, it attempt to reorganize retire list while the object is deleting. However, as I see, the origin code doesn't adjust the index simultaneously, which will skip track of the object origin from &rl->list[iret + 1]. I'm not sure whether the behavior was originally intended or not.

    opened by kevinshieh0225 5
  • Correct the range for modulo

    Correct the range for modulo

    The value N is power of 2 integer which is declared in :

    #define N (1 << 12) /* node size */
    #define NBITS (N - 1)
    

    N will become 1 0000 0000 0000 in binary. When the divisor N is power of 2, the operator % is equal to logical AND with N - 1 which means that i mod 2^n with bitwise AND is ( i & N - 1 ) not ( i & N ).

    For example: 3 % 4 == 3 == 0011 % 0100 == 0011 & ( 0100 - 1 )

    opened by linD026 4
  • Rename ringbuf-shm to ringbuf_shm

    Rename ringbuf-shm to ringbuf_shm

    The ringbuf_shm link in README.md is not working since it's linked to an inexistent ringbuf_shm folder. Renaming ringbuf-shm folder to ringbuf_shm fixes the problem.

    opened by ChunMinChang 4
  • Fix error of __list_find

    Fix error of __list_find

    The node on the linked list should follow the ordering by its key. However, the function list_insert doesn't actually do this because of the wrong implementation of __list_find.

    There are three main fixes in this patch. First, once we should do synchronization, we have to iterate the list again but not return from the function. Second, the while loop should iterate until the last node but not the second last one. Finally, under the normal situation that the tail node with key UINTPTR_MAX should not be deleted (unless the end of the program), some codes are never executed which can be removed.

    opened by RinHizakura 2
  • Avoid buffered I/O

    Avoid buffered I/O

    Here's a macro solution to avoid unexpected output by the buffered I/O printf. It could have some limitations and need improvement, but it achieves the purpose of output in text lines as we may want.

    opened by RinHizakura 1
  • thread-rcu: Fix the types in rcu.h and barrier counter

    thread-rcu: Fix the types in rcu.h and barrier counter

    rcu.h:

    • Fix the parameter type of smp_store_release(). The parameter that wants to store should be a pointer type.
    • Fix the type of tid in rcu_node.
    • Rename all the internal parameters in Linux kernel style API to make it more prettier.

    main.c:

    • Fix the barrier counter that doesn't initialize after exit.

    No function change.

    opened by linD026 0
  • Fix grace period over bound checking

    Fix grace period over bound checking

    The array of the grace period will have the number update run + 1 of the index. So the bound of the grace period is the number of update runs, not update run + 1.

    opened by linD026 0
  • Fix wrong allocation size of ringbuffer

    Fix wrong allocation size of ringbuffer

    I'm not sure why the actual size is calculated by ALIGN_FLOOR.

    Since the constraint of count is that it must be the power of 2, so it is valid to be like 2 or 4. However, in these cases, ALIGN_FLOOR won't allocate any size for *ring[] in ringbuf_t when CACHE_LINE_SIZE == 64. It makes the overflow access of memory which can be detected by valgrind or ASAN. So I think ALIGN_CEIL should be the correct one in general? Do I miss some reason for using ALIGN_FLOOR?

    opened by RinHizakura 0
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

Amanieu d'Antras 1.1k Jul 1, 2022
Concurrency Kit 2.1k Jun 18, 2022
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

The STE||AR Group 1.9k Jun 23, 2022
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.

Apple 2.2k Jun 19, 2022
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.

Martin Sustrik 2.6k Jun 23, 2022
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

Christian Blume 570 Jun 24, 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

David Haim 950 Jun 24, 2022
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.

The STE||AR Group 1.9k Jun 28, 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

null 119 Jun 9, 2022
Task System presented in "Better Code: Concurrency - Sean Parent"

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

Pranav 27 Jun 16, 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

Josip Palavra 94 Jun 21, 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

null 790 Jun 25, 2022
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+

null 2.7k Jun 25, 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

RaftLib 799 Jun 23, 2022
EnkiTS - A permissively licensed C and C++ Task Scheduler for creating parallel programs. Requires C++11 support.

Support development of enkiTS through Github Sponsors or Patreon enkiTS Master branch Dev branch enki Task Scheduler A permissively licensed C and C++

Doug Binks 1.3k Jun 20, 2022
Cpp-concurrency - cpp implementation of golang style concurrency

cpp-concurrency C++ implementation of golang style concurrency Usage Use existing single header concurrency.hpp or run script to merge multiple header

YoungJoong Kim 15 Apr 30, 2021
Fuses IMU readings with a complementary filter to achieve accurate pitch and roll readings.

SimpleFusion A library that fuses accelerometer and gyroscope readings quickly and easily with a complementary filter. Overview This library combines

Sean Boerhout 5 May 13, 2022
The final project for the Udacity C++ Nanodegree Concurrency course

CPPND: Program a Concurrent Traffic Simulation This is the project for the fourth course in the Udacity C++ Nanodegree Program: Concurrency. Throughou

Franz 2 Oct 15, 2021
Programs and my Notes from the course: "Beginning c++ Programming - From Beginner to Beyond" by Dr. Frank J. Mitropoulos

Project Info Technology Stack Linux (Arch) Visual Studio Code GCC 11.1.0 (since GCC 11.1 the default target is gnu++17, a superset of C++17) Source Ud

Alok Shandilya 1 Oct 22, 2021
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

Amanieu d'Antras 1.1k Jul 1, 2022
Concurrency Kit 2.1k Jun 18, 2022
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

The STE||AR Group 1.9k Jun 23, 2022
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.

Apple 2.2k Jun 19, 2022
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.

Martin Sustrik 2.6k Jun 23, 2022
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

Christian Blume 570 Jun 24, 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

David Haim 950 Jun 24, 2022
jemalloc websitejemalloc - General purpose malloc(3) implementation that emphasizes fragmentation avoidance and scalable concurrency support. [BSD] website

jemalloc is a general purpose malloc(3) implementation that emphasizes fragmentation avoidance and scalable concurrency support. jemalloc first came

jemalloc memory allocator 7.1k Jun 27, 2022
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.

The STE||AR Group 1.9k Jun 28, 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

null 119 Jun 9, 2022