Week 08 Weekly Exercises

Objectives

Use basic rust threads
Understand how rust provides fearless concurrency
Apply ownership semantics

Activities To Be Completed

The following is a list of all the markedactivities available to complete this week...

Train Game
Channels!
WebServer
Send and Sync

The following practice activities are optional and are not marked, or required to be completed for the week.

Obelisk - using web frameworks

Preparation

Before attempting the weekly exercises you should re-read the relevant lecture slides and their accompanying examples.

Getting Started

Create a new directory for this week's exercises called lab08, change to this directory, and fetch the provided code for this week by running these commands:

mkdir lab08
cd lab08
6991 fetch lab 08

Or, if you're not working on CSE, you can download the provided code as a tar file.

Exercise:
Train Game

In Sydney, all train carraiges have an identifiable four digit number.

a picture of a train carriage number with the numbers 3 5 9 2 For example, in the above image, the train carriage number is 3592.

A popular game amongst Sydney train passengers is to find some arrangement of the numbers, and four mathematical operators (+, -, x, /), that will give a result of 10.

For example, in the above image, the numbers 3 5 9 2 can be arranged as

3 x 2 - 5 + 9 = 10

In this exercise, you are given starter code that currently takes in a FIVE digit number, and prints out all possible arrangements of the numbers, and four mathematical operators (+, -, x, /), that will give a result of 10.

It does this by generating all possible combinations into a vec of tuples. Each tuple is a combination of the numbers and operators: (<Vec<i32>, Vec<char>>), where the first element is a vector of the digits, and the second element is a vector of the operators.

It then iterates through the vec of tuples, evaluates the expression left to right, without order of operations, and prints out the expression if it evaluates to 10. Your task is to modify the code to take advantage of rust's fearless concurrency to speed up the program.

To do this, you will need to roughly follow the following steps:

Chunk the vec of tuples into a vec of vecs of tuples
Create a new thread scope
For each chunk (a singular vec of tuples) spawn a new thread (inside the scope)
Have each thread iterate through its chunk, and evaluate the expression
Have each thread print out the expression if it evaluates to 10

When you think your program is working, you can use autotest to run some simple automated tests:

6991 autotest

When you are finished working on this exercise, you must submit your work by running give:

6991 give-crate

The recommended due date for this exercise is Week 9 Wednesday 21:00:00.

You must run give before Week 10 Friday 17:00:00 to obtain the marks for this exercise. Note that this is an individual exercise; the work you submit with give must be entirely your own.

main.rs

use itertools::Itertools;
use std::thread;

mod test;

fn main() {
    // take number from commandline arg
    // number is guaranteed to be four digits
    let input_number = std::env::args().nth(1).unwrap().parse::<u32>().unwrap();
    if !(10000..=99999).contains(&input_number) {
        panic!("Number must be five digits");
    }

    let operators = vec!['+', '-', '*', '/'];

    // let's get a massive iterator,
    // over every arrangement of
    // digits and every arrangement of operators
    let digits_operators: Vec<(Vec<i32>, Vec<char>)> = std::env::args()
        .nth(1)
        .unwrap()
        .chars()
        .map(|x| x.to_digit(10).unwrap() as i32)
        .permutations(5)
        .into_iter()
        .cartesian_product(operators.into_iter().permutations(4).into_iter())
        .collect();

    let length = digits_operators.len();
    println!("There are {length} potential combinations",);

    // split up into 6 threads
    // we need to split up digit_operators into 6 subparts
    // and pass each subpart to a thread
    let num_threads = 6;
    // turn into vec of vecs
    let mut chunks = digits_operators
        .chunks(length / num_threads)
        .into_iter()
        .collect::<Vec<_>>()
        .into_iter();

    thread::scope(|s| {
        for _ in 0..num_threads {
            if let Some(chunk) = chunks.next() {
                s.spawn(|| {
                    chunk.iter().for_each(|(digits, operators)| {
                        // go through one combination of
                        // operators and see if it works
                        let _ = calculate(digits.to_vec(), operators.to_vec());
                    });
                });
            }
        }
    });

    // for every single combination
    // of digits and operators
}

fn calculate(digits: Vec<i32>, operators: Vec<char>) -> Result<(), ()> {
    let num1 = digits[0];
    let num2 = digits[1];
    let num3 = digits[2];
    let num4 = digits[3];
    let num5 = digits[4];

    let op1 = operators[0];
    let op2 = operators[1];
    let op3 = operators[2];
    let op4 = operators[3];

    let result = operate(num1, num2, op1)?;
    let result = operate(result, num3, op2)?;
    let result = operate(result, num4, op3)?;
    let result = operate(result, num5, op4)?;

    if result == 10 {
        println!(
            "{} {} {} {} {} {} {} {} {} = 10",
            num1, op1, num2, op2, num3, op3, num4, op4, num5
        );
    }

    Ok(())
}

fn operate(num1: i32, num2: i32, op: char) -> Result<i32, ()> {
    match op {
        '+' => Ok(num1 + num2),
        '-' => Ok(num1 - num2),
        '*' => Ok(num1 * num2),
        '/' => num1.checked_div(num2).ok_or(()),
        _ => panic!("Invalid operation"),
    }
}

test.rs

#[cfg(test)]
use std::process::Command; // Add methods on commands

#[test]
fn test() {
    // test that train_game works

    // compile the code
    let mut build = Command::new("6991")
        .args(["cargo", "build"])
        .spawn()
        .unwrap();
    let _result = build.wait().unwrap();

    // run the code
    let output = Command::new("6991")
        .args(["cargo", "run", "12345"])
        .output()
        .expect("failed to run train_game binary");

    // test output contains correct num combs
    assert!(
        String::from_utf8_lossy(&output.stdout).contains("There are 2880 potential combinations")
    );

    // assert that there are at least 59 lines of output
    // (one for each combination)
    assert!(String::from_utf8_lossy(&output.stdout).lines().count() >= 60);
}

Exercise:
Channels!

In order to get started, you will need to create a Cargo project

You can do this by running the cargo new command in your terminal

6991 cargo new channels
Created binary (application) `channels` package

Last exercise, we refactored a single threaded set of calculations to use multiple threads. Our threads all printed out the specific calculations that they were able to find that met the requirements, but, we have no way of knowing how many calculations each thread found!

In this exercise you will be making use of Rust's channels to communicate between workers.

To do this, it is assumed that you have completed the previous exercise, and have a working solution that:

chunks the work into a set of smaller vectors
creates a thread scope
spawns a thread for each sub task/vector
does the calculation (and prints) in each thread

Before you start, copy your solution from the previous exercise, and add the itertools dependency to your Cargo.toml file.

  cp train_game/src/{test,main}.rs channels/src/
  6991 cargo add itertools

You should modify your code, such that:

Before the new thread scope is created, you create a channel
Each thread sends the number of calculations it found to the channel
After all the calculations are done, you receive the number of calculations from each thread, and print out the total number of calculations

Your output should look something like this:

6991 cargo run -- 12345
cr -- 12345
   Compiling either v1.8.0
   Compiling itertools v0.10.5
   Compiling channels v0.1.0
    Finished dev [unoptimized + debuginfo] target(s) in 1.74s
     Running `target/debug/channels 12345`
There are 2880 potential combinations
2 / 4 + 3 - 1 * 5 = 10
// -- CUT FOR BREVITY, YOUR PROGRAM WILL OUTPUT MORE -- 
2 * 4 - 3 + 5 / 1 = 10
Thread 0 found 5 combinations
Thread 3 found 11 combinations
Thread 4 found 19 combinations
Thread 2 found 4 combinations
Thread 5 found 9 combinations
Thread 1 found 11 combinations
Total: 59

It may help to change the return type of calculate to indicate whether or not a calculation was found for a combination of numbers. and operators.

This will allow you to have a running "count" of how many solutions have been found, and at the end of the thread's execution, you can send back the thread_id and count to the channel.

The Shared usage example in the mspc documentation will be quite useful.

You should not need any shared state primatives such as Arc or Mutex for this exercise.

You may find the Rust Book chapter on message passing to be useful: Message Passing

When you think your program is working, you can use autotest to run some simple automated tests:

6991 autotest

When you are finished working on this exercise, you must submit your work by running give:

6991 give-crate

The recommended due date for this exercise is Week 9 Wednesday 21:00:00.

You must run give before Week 10 Friday 17:00:00 to obtain the marks for this exercise. Note that this is an individual exercise; the work you submit with give must be entirely your own.

main.rs

use itertools::Itertools;
use std::sync::mpsc::channel;
use std::thread;
fn main() {
    // take number from commandline arg
    // number is guaranteed to be four digits
    let input_number = std::env::args().nth(1).unwrap().parse::<u32>().unwrap();
    if !(10000..=99999).contains(&input_number) {
        panic!("Number must be five digits");
    }

    let operators = vec!['+', '-', '*', '/'];

    // let's get a massive iterator,
    // over every arrangement of
    // digits and every arrangement of operators
    let digits_operators: Vec<(Vec<i32>, Vec<char>)> = std::env::args()
        .nth(1)
        .unwrap()
        .chars()
        .map(|x| x.to_digit(10).unwrap() as i32)
        .permutations(5)
        .into_iter()
        .cartesian_product(operators.into_iter().permutations(4).into_iter())
        .collect();

    let length = digits_operators.len();
    println!("There are {length} potential combinations",);

    // split up into 6 threads
    // we need to split up digit_operators into 6 subparts
    // and pass each subpart to a thread
    let num_threads = 6;
    // turn into vec of vecs
    let mut chunks = digits_operators
        .chunks(length / num_threads)
        .into_iter()
        .collect::<Vec<_>>()
        .into_iter();

    let (sender, receiver) = channel();
    thread::scope(|s| {
        for id in 0..num_threads {
            if let Some(chunk) = chunks.next() {
                let sender = sender.clone();
                s.spawn(move || {
                    let mut count = 0;
                    chunk.iter().for_each(|(digits, operators)| {
                        // go through one combination of
                        // operators and see if it works
                        if let Ok(true) = calculate(digits.to_vec(), operators.to_vec()) {
                            count += 1;
                        }
                    });
                    sender.send((id, count)).unwrap();
                });
            }
        }
    });

    // for every single combination
    // of digits and operators

    let mut total = 0;
    for _ in 0..num_threads {
        let (id, count) = receiver.recv().unwrap();
        println!("Thread {id} found {count} combinations",);
        total += count;
    }
    println!("Total: {total}",);
}

fn calculate(digits: Vec<i32>, operators: Vec<char>) -> Result<bool, ()> {
    let num1 = digits[0];
    let num2 = digits[1];
    let num3 = digits[2];
    let num4 = digits[3];
    let num5 = digits[4];

    let op1 = operators[0];
    let op2 = operators[1];
    let op3 = operators[2];
    let op4 = operators[3];

    let result = operate(num1, num2, op1)?;
    let result = operate(result, num3, op2)?;
    let result = operate(result, num4, op3)?;
    let result = operate(result, num5, op4)?;

    if result == 10 {
        println!(
            "{} {} {} {} {} {} {} {} {} = 10",
            num1, op1, num2, op2, num3, op3, num4, op4, num5
        );
        Ok(true)
    } else {
        Ok(false)
    }
}

fn operate(num1: i32, num2: i32, op: char) -> Result<i32, ()> {
    match op {
        '+' => Ok(num1 + num2),
        '-' => Ok(num1 - num2),
        '*' => Ok(num1 * num2),
        '/' => num1.checked_div(num2).ok_or(()),
        _ => panic!("Invalid operation"),
    }
}

Exercise:
WebServer

You have been given a simple web server - a piece of code that listens to a port for web connections, and serves back a simple HTML page. This html page two major features:

Some text that looks exactly like: {{{ counter }}}
A button that will send a POST request to /counter

The server will be started by running:

6991 cargo run -- 12345
Server running on port 12345

This will start the server on port 12345. You can then connect to it with your browser by visiting:

http://localhost:12345

The server will be listening for connections on that port, and will respond to requests with the HTML page. The HTML page looks something similar to this:

http://localhost:12345


    Hello World!!
{{{ counter }}}

You will notice that the text in the form is currently set to {{{ counter }}}. This is a placeholder, and should be replaced with the actual value of the counter, which will be 0 initially. When you click the button, the server will receive a POST request to /counter. This currently does nothing! You should make it so that the server increments the counter by one, and then returns the new HTML page with the new value of the counter.

Your task is to complete the implementation of the server, such that it will:

Spawn a thread per connection
Make State shared across threads, by using a locking primitive
Increment the counter in state when a POST request is received
Replace the {{{ counter }}} placeholder with the actual value of the counter

To test your code, you can run the server, and then visit the page in your browser. Marks will be determined based off 6991 cargo test correctly running. The given 6991 autotest will simply call 6991 cargo test.

If you see the following error when testing

Error: Os { code: 98, kind: AddrInUse, message: "Address already in
    use" }

This means that the server is already running on the port you are trying to use. You can either kill the server, or change the port number.

If your browser tests work fine, but you cannot get 6991 cargo test to pass despite changing port numbers, etc - please submit anyways, have faith in your work :D

There is no give dryrun.

When you think your program is working, you can use autotest to run some simple automated tests:

6991 autotest

When you are finished working on this exercise, you must submit your work by running give:

6991 give-crate

The recommended due date for this exercise is Week 9 Wednesday 21:00:00.

You must run give before Week 10 Friday 17:00:00 to obtain the marks for this exercise. Note that this is an individual exercise; the work you submit with give must be entirely your own.

main.rs

/// A simple web server
/// which serves some html at index.html
/// and replaces triple curly braces with the given variable 
use std::net::{TcpListener, TcpStream};
use std::sync::{Arc, Mutex};
use std::io::Read;
use std::io::Write;

mod test;

struct State {
    counter: i32,
}


fn handle_client(mut stream: TcpStream, state: Arc<Mutex<State>>) {

    let mut buffer = [0; 1024];
    stream.read(&mut buffer).unwrap();
    let string = String::from_utf8_lossy(&buffer);

    // extract header
    let mut split = string.split("\r\n");
    let header = split.next().unwrap();
    if header == "POST /counter HTTP/1.1" {
        let mut state = state.lock().unwrap();
        state.counter += 1;
    }
    let file = include_bytes!("../index.html");

    // replace triple brackets with the counter in file (array of bytes)
    let file = String::from_utf8_lossy(file).to_string();
    let state = state.lock().unwrap();
    let file = file.replace("{{{ counter }}}", &state.counter.to_string());

    let response = format!(
        "HTTP/1.1 200 OK\r\nContentType: text/html; charset=utf-8\r\nAccess-Control-Allow-Origin: *\r\nContent-Length: {}\r\n\r\n",
        file.len()
    );
    
    stream.write_all(response.as_bytes()).unwrap();
    stream.write_all(file.as_bytes()).unwrap();
    stream.flush().unwrap();
}

fn main() -> std::io::Result<()> {
    let port = std::env::args().nth(1).unwrap_or("8081".to_string());
    let listener = TcpListener::bind(format!("127.0.0.1:{port}"))?;
    println!("Server running on port {}", port);

    let state = Arc::new(Mutex::new(State { counter: 0 }));

    // accept connections and process them serially
    for stream in listener.incoming() {
        let state = state.clone();
        // spawn a thread for each connection
        std::thread::spawn(move|| {
            handle_client(stream.unwrap(), state);
        });
    }
    Ok(())
}

test.rs

#[cfg(test)]
use std::process::Command; // Run programs
#[cfg(test)]
use assert_cmd::prelude::*; // Add methods on commands

#[test]
fn test() {
    // connect to server
    // send GET request
    // check counter is 0
    // send POST request
    // check counter is 1
    // it should not be possible for these tests to fail, but to work in browser.

    let port = std::env::args().nth(2).unwrap_or("8081".to_string());    
    println!("Running on port {port}");

    if let Ok (mut child) = Command::cargo_bin("webserver").expect("failed to find webserver binary").spawn() {
        let result = std::panic::catch_unwind(|| {
            let url = format!("http://localhost:{}/", port);
            let resp = reqwest::blocking::get(url.clone()).expect("failed to get response").text().expect("failed to get text");
            assert!(!resp.contains("{{{ counter }}}"));
            assert!(resp.contains("<p>0</p>"));

            let client = reqwest::blocking::Client::new();
            client.post(format!("{url}counter"))
                .send()
                .expect("failed to send post request");
            
            let resp = reqwest::blocking::get(url.clone()).expect("failed to get response").text().expect("failed to get text");
            assert!(resp.contains("<p>1</p>"));
        }); 

        assert!(result.is_ok());

        child.kill().expect("failed to kill child");
    }

    Command::new("killall webserver");
}

Exercise:
Send and Sync

You have been asked by a colleague to explain how Rust provides static guarantees about Concurrency.

They know some basic rust (equiv to up to week 7 of the course), but are not familiar with the details of the Send and Sync traits (etc).

Your task is to write answers to their questions, which can be found in the starter code questions.md.

You will find this useful as revision for the final exam.

When you are finished working on this exercise, you must submit your work by running give:

give cs6991 lab08_send_sync questions.md

The recommended due date for this exercise is Week 9 Wednesday 21:00:00.

You must run give before Week 10 Friday 17:00:00 to obtain the marks for this exercise. Note that this is an individual exercise; the work you submit with give must be entirely your own.

crate.tar

questions.md0000644000175000017500000000136514327431003012502 0ustar  shreyshrey1) I saw someone's code fail to compile because they 
were trying to send non-thread-safe data across threads. 
How does the Rust language allow for static (i.e. at compile time)
guarantees that specific data can be sent/shared acrosss threads?

2) Do you have to then implement the Send and Sync traits for 
every piece of data (i.e. a struct) you want to share and send across threads?

3) What types in the course have I seen that aren't Send? Give one example, 
and explain why that type isn't Send 

4) What is the relationship between Send and Sync? Does this relate
to Rust's Ownership system somehow?

5) Are there any types that could be Send but NOT Sync? Is that even possible?

6) Could we implement Send ourselves using safe rust? why/why not?

questions.md

1) I saw someone's code fail to compile because they 
were trying to send non-thread-safe data across threads. 
How does the Rust language allow for static (i.e. at compile time)
guarantees that specific data can be sent/shared acrosss threads?

2) Do you have to then implement the Send and Sync traits for 
every piece of data (i.e. a struct) you want to share and send across threads?

3) What types in the course have I seen that aren't Send? Give one example, 
and explain why that type isn't Send 

4) What is the relationship between Send and Sync? Does this relate
to Rust's Ownership system somehow?

5) Are there any types that could be Send but NOT Sync? Is that even possible?

6) Could we implement Send ourselves using safe rust? why/why not?

(Optional) Exercise:
Obelisk - using web frameworks

In this exercise, you will be using the axum crate to build a simple web server.

The starter code has two simple endpoints, designed to show off some of the advantages of building web servers in Rust, specifically around type safety and compile-time error checking.

The first endpoint is GET /ping, which returns a simple string "pong".

The second endpoint is POST /users, which expects a JSON body with a single field, username, and returns a JSON response with the username and some id.

These are represented by the CreateUser and User structs in the starter code! The axum framework allows the function for that route to use these structs as parameters and return types, and returns a 400 status code for bad arguments, if the input cannot be transformed into those structs.

Your task is to add a third endpoint, GET /hello/{name}, which returns a string "Hello, {name}!".

You can test your code by running RUST_LOG=info 6991 cargo run and then running the following commands in a separate terminal:

curl https://localhost:3000/hello/shrey

There are no autotests for this exercise.

The book Zero2Prod is a great book that highlights the benefits of building web servers in Rust, and goes through the large process of building a production-ready web server in Rust, including testing, logging, deployment and more.

main.rs

use axum::{
    extract::Path,
    http::StatusCode,
    response::IntoResponse,
    routing::{get, post},
    Json, Router,
};
use serde::{Deserialize, Serialize};
use std::net::SocketAddr;

#[tokio::main]
async fn main() {
    // initialize tracing
    tracing_subscriber::fmt::init();

    // build our application with a route
    let app = Router::new()
        // `GET /ping` goes to the `ping` function
        .route("/ping", get(ping))
        // `POST /users` goes to `create_user`
        .route("/users", post(create_user))
        // `GET /hello/:name` goes to `hello`
        .route("/hello/:name", get(hello));

    let addr = SocketAddr::from(([127, 0, 0, 1], 3000));
    tracing::debug!("listening on {}", addr);

    axum::Server::bind(&addr)
        .serve(app.into_make_service())
        .await
        .unwrap();
}

// A basic route handler that returns a static 
// string, "pong"
async fn ping() -> &'static str {
    "pong"
}

// TODO: Add a route handler for the `/users` route
async fn create_user(
    // this argument tells axum to parse the request body
    // as JSON into a `CreateUser` type
    Json(payload): Json<CreateUser>,
) -> impl IntoResponse {
    // if this was a real world program,
    // you might insert into a database here
    // and return the newly created user
    // with their id
    //
    // The sqlx crate is a good choice for
    // interacting with databases in Rust
    // via staticly typed sql queries
    let user = User {
        id: 1337,
        username: payload.username,
    };

    // this will be converted into a JSON response
    // with a status code of `201 Created`
    (StatusCode::CREATED, Json(user))
}

// the input to our `create_user` handler
#[derive(Deserialize)]
struct CreateUser {
    username: String,
}

// the output to our `create_user` handler
#[derive(Serialize)]
struct User {
    id: u64,
    username: String,
}


// TODO: Add a route handler for the `/hello/:name` route
// that returns a string of "hello {name}"
async fn hello(
    // this argument tells axum to extract the `name` parameter
    // from the request path
    Path(name): axum::extract::Path<String>,
) -> impl IntoResponse {
    // return a string of "hello {name}"
    format!("hello {}", name)
}

Submission

When you are finished each exercise make sure you submit your work by running give.

You can run give multiple times.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

The recommended due date for this week's exercises is Week 9 Wednesday 21:00:00.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

Automarking will be run continuously throughout the term, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run you can view your results here or by running this command on a CSE machine:

6991 classrun -sturec