Skip to content

Commit

Permalink
Rust: implement a basic scheduler.
Browse files Browse the repository at this point in the history
whitequark committed Aug 30, 2016
1 parent 051e6e0 commit 49ba8ae
Showing 9 changed files with 412 additions and 1 deletion.
41 changes: 41 additions & 0 deletions artiq/runtime.rs/Cargo.lock

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

5 changes: 5 additions & 0 deletions artiq/runtime.rs/Cargo.toml
Original file line number Diff line number Diff line change
@@ -11,6 +11,11 @@ path = "src/lib.rs"
[dependencies]
std_artiq = { path = "libstd_artiq" }

[dependencies.fringe]
git = "https://github.com/whitequark/libfringe"
default-features = false
features = ["alloc"]

[profile.dev]
panic = 'abort'
opt-level = 2
2 changes: 2 additions & 0 deletions artiq/runtime.rs/libstd_artiq/lib.rs
Original file line number Diff line number Diff line change
@@ -13,6 +13,8 @@ pub mod prelude {
}
}

pub mod time;

use core::fmt::Write;

#[macro_export]
117 changes: 117 additions & 0 deletions artiq/runtime.rs/libstd_artiq/time/duration.rs
Original file line number Diff line number Diff line change
@@ -0,0 +1,117 @@
use core::ops::{Add, Sub, Mul, Div};

const MILLIS_PER_SEC: u64 = 1_000;
const NANOS_PER_MILLI: u32 = 1_000_000;

/// A duration type to represent a span of time, typically used for system
/// timeouts.
///
/// Each duration is composed of a number of seconds and nanosecond precision.
/// APIs binding a system timeout will typically round up the nanosecond
/// precision if the underlying system does not support that level of precision.
///
/// Durations implement many common traits, including `Add`, `Sub`, and other
/// ops traits. Currently a duration may only be inspected for its number of
/// seconds and its nanosecond precision.
///
/// # Examples
///
/// ```
/// use std::time::Duration;
///
/// let five_seconds = Duration::new(5, 0);
/// let five_seconds_and_five_nanos = five_seconds + Duration::new(0, 5);
///
/// assert_eq!(five_seconds_and_five_nanos.as_secs(), 5);
/// assert_eq!(five_seconds_and_five_nanos.subsec_nanos(), 5);
///
/// let ten_millis = Duration::from_millis(10);
/// ```
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
pub struct Duration {
millis: u64
}

impl Duration {
/// Creates a new `Duration` from the specified number of seconds and
/// additional nanosecond precision.
///
/// If the nanoseconds is greater than 1 billion (the number of nanoseconds
/// in a second), then it will carry over into the seconds provided.
pub fn new(secs: u64, nanos: u32) -> Duration {
Duration { millis: secs * MILLIS_PER_SEC + (nanos / NANOS_PER_MILLI) as u64 }
}

/// Creates a new `Duration` from the specified number of seconds.
pub fn from_secs(secs: u64) -> Duration {
Duration { millis: secs * MILLIS_PER_SEC }
}

/// Creates a new `Duration` from the specified number of milliseconds.
pub fn from_millis(millis: u64) -> Duration {
Duration { millis: millis }
}

/// Returns the number of whole milliseconds represented by this duration.
pub fn as_millis(&self) -> u64 { self.millis }

/// Returns the number of whole seconds represented by this duration.
///
/// The extra precision represented by this duration is ignored (e.g. extra
/// nanoseconds are not represented in the returned value).
pub fn as_secs(&self) -> u64 {
self.millis / MILLIS_PER_SEC
}

/// Returns the nanosecond precision represented by this duration.
///
/// This method does **not** return the length of the duration when
/// represented by nanoseconds. The returned number always represents a
/// fractional portion of a second (e.g. it is less than one billion).
pub fn subsec_nanos(&self) -> u32 {
(self.millis % MILLIS_PER_SEC) as u32 * NANOS_PER_MILLI
}
}

impl Add for Duration {
type Output = Duration;

fn add(self, rhs: Duration) -> Duration {
Duration {
millis: self.millis.checked_add(rhs.millis)
.expect("overflow when adding durations")
}
}
}

impl Sub for Duration {
type Output = Duration;

fn sub(self, rhs: Duration) -> Duration {
Duration {
millis: self.millis.checked_sub(rhs.millis)
.expect("overflow when subtracting durations")
}
}
}

impl Mul<u32> for Duration {
type Output = Duration;

fn mul(self, rhs: u32) -> Duration {
Duration {
millis: self.millis.checked_mul(rhs as u64)
.expect("overflow when multiplying duration")
}
}
}

impl Div<u32> for Duration {
type Output = Duration;

fn div(self, rhs: u32) -> Duration {
Duration {
millis: self.millis / (rhs as u64)
}
}
}
81 changes: 81 additions & 0 deletions artiq/runtime.rs/libstd_artiq/time/instant.rs
Original file line number Diff line number Diff line change
@@ -0,0 +1,81 @@
use core::ops::{Add, Sub};
use time::duration::Duration;

/// A measurement of a monotonically increasing clock.
///
/// Instants are always guaranteed to be greater than any previously measured
/// instant when created, and are often useful for tasks such as measuring
/// benchmarks or timing how long an operation takes.
///
/// Note, however, that instants are not guaranteed to be **steady**. In other
/// words, each tick of the underlying clock may not be the same length (e.g.
/// some seconds may be longer than others). An instant may jump forwards or
/// experience time dilation (slow down or speed up), but it will never go
/// backwards.
///
/// Instants are opaque types that can only be compared to one another. There is
/// no method to get "the number of seconds" from an instant. Instead, it only
/// allows measuring the duration between two instants (or comparing two
/// instants).
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Instant {
millis: u64
}

impl Instant {
/// Returns an instant corresponding to "now".
pub fn now() -> Instant {
extern {
fn clock_get_ms() -> i64;
}

Instant { millis: unsafe { clock_get_ms() as u64 } }
}

/// Returns the amount of time elapsed from another instant to this one.
///
/// # Panics
///
/// This function will panic if `earlier` is later than `self`, which should
/// only be possible if `earlier` was created after `self`. Because
/// `Instant` is monotonic, the only time that this should happen should be
/// a bug.
pub fn duration_from_earlier(&self, earlier: Instant) -> Duration {
let millis = self.millis.checked_sub(earlier.millis)
.expect("`earlier` is later than `self`");
Duration::from_millis(millis)
}

/// Returns the amount of time elapsed since this instant was created.
///
/// # Panics
///
/// This function may panic if the current time is earlier than this
/// instant, which is something that can happen if an `Instant` is
/// produced synthetically.
pub fn elapsed(&self) -> Duration {
Instant::now().duration_from_earlier(*self)
}
}

impl Add<Duration> for Instant {
type Output = Instant;

fn add(self, other: Duration) -> Instant {
Instant {
millis: self.millis.checked_add(other.as_millis())
.expect("overflow when adding duration to instant")
}
}
}

impl Sub<Duration> for Instant {
type Output = Instant;

fn sub(self, other: Duration) -> Instant {
Instant {
millis: self.millis.checked_sub(other.as_millis())
.expect("overflow when subtracting duration from instant")
}
}
}
5 changes: 5 additions & 0 deletions artiq/runtime.rs/libstd_artiq/time/mod.rs
Original file line number Diff line number Diff line change
@@ -0,0 +1,5 @@
pub use self::duration::Duration;
pub use self::instant::Instant;

mod duration;
mod instant;
21 changes: 20 additions & 1 deletion artiq/runtime.rs/src/lib.rs
Original file line number Diff line number Diff line change
@@ -4,8 +4,27 @@
extern crate std_artiq as std;

use std::prelude::v1::*;
use std::time::Duration;
use scheduler::Scheduler;

pub mod scheduler;

#[no_mangle]
pub extern "C" fn rust_main() {
println!("hello from rust!");
// let mut scheduler = Scheduler::new();
// unsafe {
// scheduler.spawn(4096, move |mut io| {
// loop {
// println!("thread A");
// io.sleep(Duration::from_secs(1)).unwrap()
// }
// });
// scheduler.spawn(4096, move |mut io| {
// loop {
// println!("thread B");
// io.sleep(Duration::from_millis(333)).unwrap()
// }
// });
// }
// loop { scheduler.run() }
}
131 changes: 131 additions & 0 deletions artiq/runtime.rs/src/scheduler.rs
Original file line number Diff line number Diff line change
@@ -0,0 +1,131 @@
extern crate fringe;

use std::prelude::v1::*;
use std::time::{Instant, Duration};
use self::fringe::OwnedStack;
use self::fringe::generator::{Generator, Yielder};

#[derive(Debug)]
pub struct WaitRequest {
timeout: Option<Instant>,
event: Option<WaitEvent>
}

#[derive(Debug)]
pub enum WaitResult {
Completed,
TimedOut,
Interrupted
}

#[derive(Debug)]
struct Thread {
generator: Generator<WaitResult, WaitRequest, OwnedStack>,
waiting_for: WaitRequest,
interrupted: bool
}

#[derive(Debug)]
pub struct Scheduler {
threads: Vec<Thread>,
index: usize
}

impl Scheduler {
pub fn new() -> Scheduler {
Scheduler { threads: Vec::new(), index: 0 }
}

pub unsafe fn spawn<F: FnOnce(Io) + Send>(&mut self, stack_size: usize, f: F) {
let stack = OwnedStack::new(stack_size);
let thread = Thread {
generator: Generator::unsafe_new(stack, move |yielder, _| {
f(Io(yielder))
}),
waiting_for: WaitRequest {
timeout: None,
event: None
},
interrupted: false
};
self.threads.push(thread)
}

pub fn run(&mut self) {
if self.threads.len() == 0 { return }

let now = Instant::now();

let start_index = self.index;
loop {
self.index = (self.index + 1) % self.threads.len();

let result = {
let thread = &mut self.threads[self.index];
match thread.waiting_for {
_ if thread.interrupted => {
thread.interrupted = false;
thread.generator.resume(WaitResult::Interrupted)
}
WaitRequest { timeout: Some(instant), .. } if now >= instant =>
thread.generator.resume(WaitResult::TimedOut),
WaitRequest { event: Some(ref event), .. } if event.completed() =>
thread.generator.resume(WaitResult::Completed),
WaitRequest { timeout: None, event: None } =>
thread.generator.resume(WaitResult::Completed),
_ => {
if self.index == start_index {
// We've checked every thread and none of them are runnable.
break
} else {
continue
}
}
}
};

match result {
None => {
// The thread has terminated.
self.threads.remove(self.index);
self.index = 0
},
Some(wait_request) => {
// The thread has suspended itself.
self.threads[self.index].waiting_for = wait_request
}
}

break
}
}
}

#[derive(Debug)]
pub enum WaitEvent {}

impl WaitEvent {
fn completed(&self) -> bool {
match *self {}
}
}

pub type IoResult<T> = Result<T, ()>;

#[derive(Debug)]
pub struct Io<'a>(&'a mut Yielder<WaitResult, WaitRequest, OwnedStack>);

impl<'a> Io<'a> {
pub fn sleep(&mut self, duration: Duration) -> IoResult<()> {
let request = WaitRequest {
timeout: Some(Instant::now() + duration),
event: None
};

match self.0.suspend(request) {
WaitResult::TimedOut => Ok(()),
WaitResult::Interrupted => Err(()),
_ => unreachable!()
}
}
}
10 changes: 10 additions & 0 deletions artiq/runtime/runtime.ld
Original file line number Diff line number Diff line change
@@ -26,6 +26,16 @@ SECTIONS
_etext = .;
} > runtime

/* https://sourceware.org/bugzilla/show_bug.cgi?id=20475 */
.got : {
_GLOBAL_OFFSET_TABLE_ = .;
*(.got)
} > runtime

.got.plt : {
*(.got.plt)
} > runtime

.rodata :
{
. = ALIGN(4);

0 comments on commit 49ba8ae

Please sign in to comment.