a Rust library implementing safe, lightweight context switches, without relying on kernel services

Overview

crates travis rustdoc irccloud

libfringe

libfringe is a library implementing safe, lightweight context switches, without relying on kernel services. It can be used in hosted environments (using std) as well as on bare metal (using core).

It provides the following safe abstractions:

  • an implementation of generators, Generator.

It also provides the necessary low-level building blocks:

  • a trait that can be implemented by stack allocators, Stack;
  • a wrapper for using slice references as stacks, SliceStack;
  • a stack allocator based on Box<[u8]>, OwnedStack;
  • a stack allocator based on anonymous memory mappings with guard pages, OsStack.

libfringe emphasizes safety and correctness, and goes to great lengths to never violate the platform ABI.

Usage example

extern crate fringe;

use fringe::{OsStack, Generator};

fn main() {
  let stack = OsStack::new(1 << 16).unwrap();
  let mut gen = Generator::new(stack, move |yielder, ()| {
    for i in 1..4 { yielder.suspend(i) }
  });

  println!("{:?}", gen.resume(())); // Some(1)
  println!("{:?}", gen.resume(())); // Some(2)
  println!("{:?}", gen.resume(())); // Some(3)
  println!("{:?}", gen.resume(())); // None
}

Performance

libfringe does context switches in 3ns flat on x86 and x86_64!

test swap ... bench:         6 ns/iter (+/- 0)

Debuggability

Uniquely among libraries implementing context switching, libfringe ensures that the call stack does not abruptly end at the boundary of a generator. Let's consider this buggy code:

extern crate fringe;

use fringe::{OsStack, Generator};

fn main() {
  let stack = OsStack::new(1 << 16).unwrap();
  let mut gen = Generator::new(stack, move |yielder, mut index| {
    let values = [1, 2, 3];
    loop { index = yielder.suspend(values[index]) }
  });

  println!("{:?}", gen.resume(5));
}

It crashes with the following backtrace:

thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 5', /checkout/src/libcore/slice.rs:658
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: <usize as core::slice::SliceIndex<T>>::index
             at /checkout/src/libcore/slice.rs:658
   1: core::slice::<impl core::ops::Index<I> for [T]>::index
             at /checkout/src/libcore/slice.rs:560
   2: crash_test::main::{{closure}}
             at ./src/main.rs:9
   3: <fringe::generator::Generator<'a, Input, Output, Stack>>::unsafe_new::generator_wrapper
             at /home/edef/src/github.com/edef1c/libfringe/src/generator.rs:137
   4: fringe::arch::imp::init::trampoline_2
             at /home/edef/src/github.com/edef1c/libfringe/src/arch/x86_64.rs:116
   5: fringe::arch::imp::init::trampoline_1
             at /home/edef/src/github.com/edef1c/libfringe/src/arch/x86_64.rs:61
   6: <fringe::generator::Generator<'a, Input, Output, Stack>>::resume
             at /home/edef/src/github.com/edef1c/libfringe/src/arch/x86_64.rs:184
             at /home/edef/src/github.com/edef1c/libfringe/src/generator.rs:171
   7: crash_test::main
             at ./src/main.rs:12

Similarly, debuggers, profilers, and all other tools using the DWARF debug information have full insight into the call stacks.

Note that the stack should be deep enough for the panic machinery to store its state—at any point there should be at least 8 KiB of free stack space, or panicking will result in a segfault.

Limitations

The architectures currently supported are: x86, x86_64, aarch64, or1k.

The platforms currently supported are: bare metal, Linux (any libc), FreeBSD, DragonFly BSD, macOS. Windows is not supported (see explanation below).

Installation

libfringe is a Cargo package. Add this to your Cargo.toml:

[dependencies.fringe]
version = "1.2.1"

To use libfringe on a bare-metal target, add the no-default-features key:

[dependencies.fringe]
version = "1.2.1"
no-default-features = true

Feature flags

libfringe provides some optional features through Cargo's feature flags. Currently, all of them are enabled by default.

alloc

This flag enables dependency on the alloc crate, which is required for the OwnedStack.

valgrind

This flag enables Valgrind integration. libfringe will register context stacks with Valgrind.

Internals

libfringe uses two key implementation techniques.

Compiler-assisted register spilling

Traditionally, libraries implementing context switches in userspace have to spill all callee-saved registers. On the other hand, libfringe fully inlines calls to every function that eventually results in a context switch, and uses an inline assembly statement marking every register as clobbered to implement the context switching itself.

As a result, only minimal work needs to be performed in the context switching code (LLVM does not support spilling the frame pointer), which is especially important on architectures with lots of callee-saved registers.

Call stack splicing

Non-Windows platforms use DWARF for both stack unwinding and debugging. DWARF call frame information is very generic to be ABI-agnostic—it defines a bytecode that describes the actions that need to be performed to simulate returning from a function. libfringe uses this bytecode to specify that, after the generator function has returned, execution continues at the point where the generator function was resumed the last time.

Windows compatibility

As was said, libfringe emphasizes following the platform ABI. On Windows, the platform ABI does not allow moving the stack pointer from the range designated by the OS during thread creation. Therefore, the technique used by libfringe on *nix platforms is not applicable, and libfringe does not provide Windows support.

You might ask, "but what about mioco?" The mioco library uses the context library to implement context switches, which is little more than a wrapper of boost::context. The boost::context library changes undocumented fields in the TIB during every context switch to try and work around the restrictions placed by the Windows platform ABI. This has failed before and it is bound to fail again, breaking existing code that uses boost::context in unexpected and complicated ways. The authors of libfringe consider this unacceptable.

The only supported way to implement user-mode context switching on Windows is fibers. There are no reasons the safe abstractions provided by libfringe could not be implemented on top of that; it is simply not yet done. This should be straightforward and an implementation is welcome. Note that while UMS threads are capable of providing user-mode context switching, they involve managing scheduler threads to run UMS threads on, which is incompatible with libfringe's design.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Comments
  • Unwinding support

    Unwinding support

    This is actually required to ensure safety. Currently the following safe code causes a segfault: https://gist.github.com/Amanieu/9f4854c096fa519f046ace876779be60

    Based on top of #51

    opened by Amanieu 13
  • Add proper CFI and other inline assembly cleanups

    Add proper CFI and other inline assembly cleanups

    The most significant change is that all of the inline asm for x86 and x86_64 now has proper CFI annotations, which allows gdb to produce a correct backtrace even if the program is interrupted in the middle of a swap operations.

    I didn't do this for the OR1K code because I am not familiar with the instruction set and don't have any way of testing the resulting code.

    I've also added a few cleanups for the inline asm clobbers.

    opened by Amanieu 10
  • fPIC troubles? relocation R_X86_64_PC32 against symbol

    fPIC troubles? relocation R_X86_64_PC32 against symbol

    Edit: a quicker/easier way to test is to paste this into libfringe/cargo.toml:

    [lib]
    name = "libfringe"
    path = "src/lib.rs"
    crate-type = ["dylib"]
    

    Hello,

    I'm unable to use libfringe with my DSO. Small test case pasted below.

      = note: /usr/bin/ld: /home/maswanso/src/external/rust/libfringefpic/target/debug/deps/libfringefpic.0.o: relocation R_X86_64_PC32 against symbol `_ZN6fringe4arch3imp4swap10trampoline17h9a2ce236cc1b16f6E' can not be used when making a shared object; recompile with -fPIC
    

    I maintain that my little test is compiled as PIC. Evidence: libfringefpic.0.o (pic) and also:

    $ file libfringefpic.0.o 
    /home/maswanso/src/external/rust/libfringefpic/target/debug/deps/libfringefpic.0.o: ELF 64-bit LSB  relocatable, x86-64, version 1 (SYSV), not stripped
    

    I'm quite fascinated with libfringe. I hope it's possible to use with DSOs.

    Any suggestions / help would be appreciated!

    • Cargo.toml
    [package]
    name = "libfringefpic"
    version = "1.0.0"
    authors = ["Mark Swanson [email protected]"]
    
    [dependencies.fringe]
    no-default-features = true
    git = "https://github.com/nathan7/libfringe.git"
    
    [lib]
    name = "libfringefpic"
    path = "src/lib.rs"
    crate-type = ["dylib"]
    
    • .cargo/config
    [build]
    # rustflags = ["-C", "prefer-dynamic", "-Z", "incremental=/tmp/rustc_incremental", "-Z", "incremental-info"]
    
    rustflags = ["-C", "prefer-dynamic", "-C", "link-args=-fPIC"]
    # rustflags = ["-C", "relocation-model=pic", "-C", "link-args=-fPIC"]
    # :-)
    
    • src/lib.rs
    extern crate fringe;
    
    use fringe::{OsStack, Generator};
    
    pub fn x() {
      let stack = OsStack::new(1 << 16).unwrap();
      let mut gen = Generator::new(stack, move |yielder, mut index| {
        let values = [1, 2, 3];
        loop { index = yielder.suspend(values[index]) }
      });
    
      println!("{:?}", gen.resume(5));
    }
    
    

    Running rustc src/lib.rs --crate-name libfringefpic --crate-type dylib -g -C metadata=63492654b52cf958 --out-dir /home/maswanso/src/external/rust/libfringefpic/target/debug/deps --emit=dep-info,link -L dependency=/home/maswanso/src/external/rust/libfringefpic/target/debug/deps --extern fringe=/home/maswanso/src/external/rust/libfringefpic/target/debug/deps/libfringe-88227e5bfb249863.rlib -C prefer-dynamic -C link-args=-fPIC

    
    error: linking with `cc` failed: exit code: 1
      |
      = note: "cc" "-Wl,--as-needed" "-Wl,-z,noexecstack" "-m64" "-L" "/home/maswanso/.multirust/toolchains/nightly-2016-09-09-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "/home/maswanso/src/external/rust/libfringefpic/target/debug/deps/libfringefpic.0.o" "-o" "/home/maswanso/src/external/rust/libfringefpic/target/debug/deps/liblibfringefpic.so" "/home/maswanso/src/external/rust/libfringefpic/target/debug/deps/libfringefpic.metadata.o" "-nodefaultlibs" "-L" "/home/maswanso/src/external/rust/libfringefpic/target/debug/deps" "-L" "/home/maswanso/.multirust/toolchains/nightly-2016-09-09-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "-Wl,-Bstatic" "-Wl,-Bdynamic" "-Wl,--whole-archive" "/tmp/rustc.5dtQdVsxlbYQ/libfringe-88227e5bfb249863.rlib" "-Wl,--no-whole-archive" "-Wl,--whole-archive" "/tmp/rustc.5dtQdVsxlbYQ/libvalgrind_request-c9df0ba26d15ec95.rlib" "-Wl,--no-whole-archive" "-Wl,--whole-archive" "/tmp/rustc.5dtQdVsxlbYQ/liblibc-ad32fde1bd850538.rlib" "-Wl,--no-whole-archive" "-L" "/home/maswanso/.multirust/toolchains/nightly-2016-09-09-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "-l" "std-411f48d3" "-l" "util" "-l" "dl" "-l" "pthread" "-l" "gcc_s" "-l" "pthread" "-l" "c" "-l" "m" "-l" "rt" "-l" "util" "-shared" "-fPIC" "-l" "compiler-rt"
      = note: /usr/bin/ld: /home/maswanso/src/external/rust/libfringefpic/target/debug/deps/libfringefpic.0.o: relocation R_X86_64_PC32 against symbol `_ZN6fringe4arch3imp4swap10trampoline17h9a2ce236cc1b16f6E' can not be used when making a shared object; recompile with -fPIC
    /usr/bin/ld: final link failed: Bad value
    
    opened by MarkSwanson 9
  • Clean up the stack implementations

    Clean up the stack implementations

    Changes:

    • ~~The valgrind stuff is moved out of the generators and into the stack implementations.~~
    • Stack is now an unsafe trait since it has a contract that must be upheld by an implementation.
    • SliceStack will now automatically align a slice on construction. However this means that its fields are now private.
    • Various cleanups and moving code around.
    opened by Amanieu 9
  • Use consistent register names where free, and make trampoline its own function

    Use consistent register names where free, and make trampoline its own function

    Ok, now things get interesting. These changes don't affect the context interface at all, but change the assembly such that I can do my parameter/coroutine stuff too. I hope after this to refactor that work so it can be added to this crate without touching the context interface interfaces.

    Feel free to ask any questions about why things are changed the way they are, of course :).

    opened by Ericson2314 8
  • project abandoned?

    project abandoned?

    This project is quite interesting and perhaps the best implementation of user mode context switch for rust. It seems that development has stalled. If it is, can the README be updated? If not is there some avenue for discussing future direction of this crate?

    opened by alkis 5
  • osx support?

    osx support?

    I tried building libfringe on OSX 10.10.5 using

    rustc 1.13.0-nightly (eac41469d 2016-08-30)
    cargo 0.13.0-nightly (3e41b6b 2016-08-29)
    
    Darwin basho.local 14.5.0 Darwin Kernel Version 14.5.0: Thu Jun 16 19:58:21 PDT 2016; root:xnu-2782.50.4~1/RELEASE_X86_64 x86_64
    

    libc::MAP_STACK

    (x.env) basho:libfringe basho$ cargo test
       Compiling fringe v1.0.2 (file:///Users/basho/w/days/rust-fringe/libfringe)
    error[E0425]: unresolved name `libc::MAP_STACK`
      --> src/os/sys.rs:21:28
       |
    21 | const STACK_FLAGS: c_int = libc::MAP_STACK
       |                            ^^^^^^^^^^^^^^^
    
    

    then I modified src/os/sys.rs to include macos in the same set as FreeBSD and Dragonfly. Then I got

    (x.env) basho:libfringe basho$ cargo test
       Compiling fringe v1.0.2 (file:///Users/basho/w/days/rust-fringe/libfringe)
    error: <inline asm>:8:7: error: unknown directive
          .local __morestack
          ^
    
      --> src/arch/x86_64.rs:54:5
       |
    54 |     asm!(
       |     ^
    
    
    opened by seanjensengrey 5
  • improve Valgrind integration, and figure out where it fits in

    improve Valgrind integration, and figure out where it fits in

    Currently, os::Stack uses the native functions provided by platform.c to register the allocated stacks with Valgrind. We don't currently expose these functions.

    Having them as extern "C" functions instead of inline assembly in Rust is also suboptimal, but might save us some implementation complexity. Performing a Valgrind call while running natively only takes about 2ns.

    Stacks should always be registered with Valgrind, even if a custom StackSource is being used — the cost is minimal, and this should work fine even in freestanding environments.

    I'm not sure if this responsibility should lie with the Stack, or with the Context. Technically, it isn't stack memory until the context is invoked, and it only ceases to be stack memory when the context finishes execution. However, the Context's main function is intended to never return (this causes an intentional abort when the trampoline function returns), so the point for stack deregistration is unclear in this case.

    opened by edef1c 5
  • File not found or module 'imp'

    File not found or module 'imp'

    Compiling fringe v1.0.5 (https://github.com/nathan7/libfringe.git#1df75900) /home/kamal/.cargo/git/checkouts/libfringe-2dc7659ef57cab6f/master/src/arch/mod.rs:15:5: 15:8 error: file not found for moduleimp/home/kamal/.cargo/git/checkouts/libfringe-2dc7659ef57cab6f/master/src/arch/mod.rs:15 mod imp; ^~~ /home/kamal/.cargo/git/checkouts/libfringe-2dc7659ef57cab6f/master/src/arch/mod.rs:15:5: 15:8 help: name the file either imp.rs or imp/mod.rs inside the directory "/home/kamal/.cargo/git/checkouts/libfringe-2dc7659ef57cab6f/master/src/arch" error: aborting due to previous error error: Could not compilefringe.

    I've tried fixing it myself, but some modules from the arch-specific files are for some reason not being imported, and I don't really know what to do further

    opened by SethDusek 4
  • Update alloc usage to support latest nightly; work around check in llvm that broke x86

    Update alloc usage to support latest nightly; work around check in llvm that broke x86

    %eip => 8 just avoids a check LLVM was making during parsing that balked with "register %eip is only available in 64-bit mode": https://github.com/llvm-mirror/llvm/blob/7ead4232dac43866b3aa2b39aa787823654f4f36/lib/Target/X86/AsmParser/X86AsmParser.cpp#L1102

    opened by alecmocatta 3
  • Don't implement Send at all

    Don't implement Send at all

    On hosted platforms, libstd allows safely borrowing values from TLS with 'thread lifetime and without a Sync bound. As a result, we can't guarantee that sending a generator across threads won't create dangling references or data races. In freestanding environments, the notion of thread-safety is likely to be defined by the consumer of libfringe, so our Send bounds and implementation are unlikely to be meaningful anyway.

    opened by edef1c 3
  • Add 32 bits RISC-V support

    Add 32 bits RISC-V support

    Summary

    This patch is to add riscv32 target support to libfringe.

    Changes

    arch/riscv32.rs: Implemented a riscv32 port similar to other supported targets. mod.rs: Point imp to riscv32.rs when using riscv32 target.

    opened by occheung 0
  • fix cargo config file for using no extra features

    fix cargo config file for using no extra features

    on my computer + in the doc https://doc.rust-lang.org/cargo/reference/features.html

    default-features = false is the way to disable extra features

    (I think no-default-features is for command line invocation)

    opened by nrolland 0
  • Keep docs in sync

    Keep docs in sync

    The website and the crates.io package docs are out of sync. Please enable multiversion support (similar to docs.rs) for docs so that it is easy to use the project.

    opened by vinaychandra 0
  • Release a new version

    Release a new version

    There have been several changes over time since the last release. Please publish the new changes to crates.io if everything is green on the current master.

    opened by vinaychandra 2
Owner
edef
@NixOS nixpkgs committer. she
edef
Horus is an open source tool for running forensic and administrative tasks at the kernel level using eBPF, a low-overhead in-kernel virtual machine, and the Rust programming language.

Horus Horus is an open-source tool for running forensic and administrative tasks at the kernel level using eBPF, a low-overhead in-kernel virtual mach

null 4 Dec 15, 2022
A minimal window context for Rust on Windows.

winctx A minimal window context for Rust on Windows. I read msdn so you don't have to. This crate provides a minimalistic method for setting up and ru

John-John Tedro 19 Dec 25, 2023
A safe, fast, lightweight embeddable scripting language written in Rust.

Bud (budlang) A safe, fast, lightweight embeddable scripting language written in Rust. WARNING: This crate is not anywhere near being ready to publish

Khonsu Labs 13 Dec 27, 2022
🐢 Atuin replaces your existing shell history with a SQLite database, and records additional context for your commands

Atuin replaces your existing shell history with a SQLite database, and records additional context for your commands. Additionally, it provides optional and fully encrypted synchronisation of your history between machines, via an Atuin server.

Ellie Huxtable 4.6k Jan 1, 2023
CtrlG - A Command Line Context Switcher

CtrlG - A Command Line Context Switcher CtrlG is a tool to quickly switch contexts to another directory, using a fuzzy finder. If enabled, ctrlg can c

Mat Jones 23 Dec 7, 2022
Low-level Rust library for implementing terminal command line interface, like in embedded systems.

Terminal CLI Need to build an interactive command prompt, with commands, properties and with full autocomplete? This is for you. Example, output only

HashMismatch 47 Nov 25, 2022
A library for python version numbers and specifiers, implementing PEP 440

PEP440 in rust A library for python version numbers and specifiers, implementing PEP 440 Not yet on crates.io due to PyO3/pyo3#2786. use std::str::Fro

konstin 9 Dec 22, 2022
A library implementing GPU-accelerated zkSync prover.

zkSync Era: A ZK Rollup For Scaling Ethereum zkSync Era is a layer 2 rollup that uses zero-knowledge proofs to scale Ethereum without compromising on

Matter Labs 4 Oct 5, 2023
A small CLI tool to query ArcGIS REST API services, implemented in Rust. The server response is returned as pretty JSON.

A small CLI tool to query ArcGIS REST API services, implemented in Rust. The server response is returned as pretty JSON.

Andrew Vitale 2 Apr 25, 2022
🦀Rust + Large Language Models - Make AI Services Freely and Easily. Inspired by LangChain

llmchain: Modern Data Transformations with LLM ?? + Large Language Models, inspired by LangChain. Features Models: LLMs & Chat Models & Embedding Mode

Shafish Labs 63 Jun 22, 2023
FastSSH is a TUI that allows you to quickly connect to your services by navigating through your SSH config.

Connect quickly to your services ?? FastSSH is a TUI that allows you to quickly connect to your services by navigating through your SSH config. Instal

Julien 85 Dec 14, 2022
This repo contains crates that are used to create the micro services and keep shared code in a common place.

MyEmma Helper Crates This repo contains crates that can are reused over different services. These crate are used in projects at MyEmma. But these crat

MyEmma 1 Jan 14, 2022
Services Info Register/KeepAlive/Publish/Subscribe. Based on etcd-rs, tokio

Services Info Register/KeepAlive/Publish/Subscribe. Based on etcd-rs, tokio

Mutalisk 5 Oct 4, 2022
OSINT from your favorite services in a friendly terminal user interface

osintui Open Source Intelligence Terminal User Interface Report Bug · Request Feature Installation First, install Rust (using the recommended rustup i

Will Sheldon 639 Jan 4, 2023
A fast, simple TUI for interacting with systemd services and their logs

systemctl-tui A fast, simple TUI for interacting with systemd services and their logs. systemctl-tui can quickly browse service status and logs, and s

Reilly Wood 11 Sep 1, 2023
SquidVM is a VM made in Rust implementing a Stack-based machine.

What is SquidVM? _____ _ ___ ____ __ / ____| (_) | \ \ / / \/ | | (___ __ _ _ _ _ __| |\ \ / /| \ /

Fragmenta 4 Dec 17, 2023
Basic template for an out-of-tree Linux kernel module written in Rust.

Rust out-of-tree module This is a basic template for an out-of-tree Linux kernel module written in Rust. Please note that: The Rust support is experim

Rust for Linux 118 Dec 26, 2022
An adaptation of the Solana token-swap program implementing Curve's StableSwap invariant.

StableSwap Program An adaptation of the Solana token-swap program implementing Curve's StableSwap invariant. Click here to try it out live on the Sola

smaster0517 3 Mar 30, 2022
For something between the likes of a toy bootloader or tiny kernel and Arch Linux.

For something between the likes of a toy bootloader or tiny kernel and Arch Linux.

Aarush Gupta 3 Oct 9, 2022