Class 10: Scheduling

Posted: Tue 25 February 2014

Problem Set 3 is due on Monday, 3 March. You should have definitely at least finished Problem 4 by today.

goto fail

Apple's SSL implementation (extracted from sslKeyExchange.c): (original indentation and whitespace preserved for lack-of-clarity)

static OSStatus
SSLVerifySignedServerKeyExchange(SSLContext *ctx, bool isRsa, SSLBuffer signedParams,
                                 uint8_t *signature, UInt16 signatureLen)
{
    OSStatus        err;
    SSLBuffer       hashOut, hashCtx, clientRandom, serverRandom;
    uint8_t         hashes[SSL_SHA1_DIGEST_LEN + SSL_MD5_DIGEST_LEN];
    SSLBuffer       signedHashes;
    uint8_t         *dataToSign;
    size_t          dataToSignLen;

    signedHashes.data = 0;
    hashCtx.data = 0;

    clientRandom.data = ctx->clientRandom;
    clientRandom.length = SSL_CLIENT_SRVR_RAND_SIZE;
    serverRandom.data = ctx->serverRandom;
    serverRandom.length = SSL_CLIENT_SRVR_RAND_SIZE;

    ...
    hashOut.data = hashes + SSL_MD5_DIGEST_LEN;
    hashOut.length = SSL_SHA1_DIGEST_LEN;
    if ((err = SSLFreeBuffer(&hashCtx)) != 0)
        goto fail;

    if ((err = ReadyHash(&SSLHashSHA1, &hashCtx)) != 0)
        goto fail;
    if ((err = SSLHashSHA1.update(&hashCtx, &clientRandom)) != 0)
        goto fail;
    if ((err = SSLHashSHA1.update(&hashCtx, &serverRandom)) != 0)
        goto fail;
    if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
        goto fail;
        goto fail;
    if ((err = SSLHashSHA1.final(&hashCtx, &hashOut)) != 0)
        goto fail;

    err = sslRawVerify(ctx,
                       ctx->peerPubKey,
                       dataToSign,              /* plaintext */
                       dataToSignLen,           /* plaintext length */
                       signature,
                       signatureLen);
    if(err) {
        sslErrorLog("SSLDecodeSignedServerKeyExchange: sslRawVerify "
                    "returned %d\n", (int)err);
        goto fail;
    }

fail:
    SSLFreeBuffer(&signedHashes);
    SSLFreeBuffer(&hashCtx);
    return err;

}

Test your SSL implementation Apple's Security Post Apple's SSL/TLS Bug (Adam Langley)

What are differences between Rust and C that make this time of fail much less likely?

What software development practices should be followed for any production code to greatly reduce the chances of these types of mistakes not being caught?

Theory Excursion

How hard is it to detect unreachable code in theory?

What should compilers do when desired decision procedures are undecidable?

Catch up on your theory with Dori-Mic and the Universal Machine!

Sharing across Tasks

unsafe2.rs

static mut count: uint = 0; 

fn update_count() { unsafe { count += 1; } }

fn main() {
    for _ in range(0u, 10) {
        spawn(proc() {
           for _ in range(0u, 1000) {
              update_count();
           }
        });
    }
    println!("Count: {:}", unsafe { count });
}

Assembly code produced by rustc -S unsafe2.rs: unsafe2.s

    .section    __TEXT,__text,regular,pure_instructions
    .align  4, 0x90
__ZN12update_count19h86817af0b0797e96al4v0.0E:
    .cfi_startproc
    cmpq    %gs:816, %rsp
    ja  LBB0_0
    movabsq $16, %r10
    movabsq $0, %r11
    callq   ___morestack
    ret
LBB0_0:
    pushq   %rbp
Ltmp2:
    .cfi_def_cfa_offset 16
Ltmp3:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp4:
    .cfi_def_cfa_register %rbp
    pushq   %rax
    movq    __ZN5count19hc6afed277fb1b6c3ah4v0.0E(%rip), %rax
    addq    $1, %rax
    movq    %rax, __ZN5count19hc6afed277fb1b6c3ah4v0.0E(%rip)
    movq    %rdi, -8(%rbp)
    addq    $8, %rsp
    popq    %rbp
    ret
    .cfi_endproc
...

Where is the data race?

RWArc - automatically reference-counter storage protected by a reader-writer lock

Why is it useful to have separate locks for reading and writing?

extern mod extra; 
use extra::arc::RWArc;

fn update_count(counter: RWArc<int>) {
    counter.write(|count: &mut int| { *count += 1; });
}

fn main() {
    let counter: RWArc<int> = RWArc::new(0);

    for _ in range(0, 10) {
        let ccounter = counter.clone(); // need the clone - this moves counter
        spawn(proc() {
           for _ in range(0, 1000) {
              update_count(ccounter.clone()); // shouldn't be necessary!?
           }
        });
    }

    counter.read(|count| {
       println!("Count: {:d}", *count);
    });

}

Why is the printed count still not 10000?

Scheduling

What are the two main decisions the supervisor needs to make on each kernel timer interrupt?

Max Ehrmann's "Desiderata":

Go placidly amid the noise and haste, and remember what peace there may be in silence. As far as possible without surrender be on good terms with all persons. Speak your truth quietly and clearly; and listen to others, even the dull and the ignorant; they too have their story. Avoid loud and aggressive persons, they are vexations to the spirit... Exercise caution in your business affairs; for the world is full of trickery... And whether or not it is clear to you, no doubt the universe is unfolding as it should... whatever your labors and aspirations, in the noisy confusion of life keep peace with your soul. With all its sham, drudgery, and broken dreams, it is still a beautiful world. Be cheerful. Strive to be happy.

Why is there a fundamental tradeoff between maximizing resource utilization and fairness in scheduling?

comments powered by Disqus