SE350 Lab

Taking notes for these labs because I actually want to understand what is going on, instead of just copying pasting the commands.

Our code https://git.uwaterloo.ca/ecese350/group27-lab/-/blob/deliverable2/Core/Src/k_task.c?ref_type=tags

The way you start things up…

Somewhere in your main, you should initialze your kernel

osKernelInit();

We implemented a preemptive scheduler, but the preemption is done inside the task itself by calling osYield().

• osYield makes a SVC call

This looks like the following:

void osKernelInit(void) {
    if (kernel_setup != 0) return;
    kernel_setup = 1;
    kernel_info.totalTasks = 0;
    kernel_info.previousTask = -1;
    kernel_info.runningTask = -1;
    uint32_t MSP_INIT_VAL = *(uint32_t**)0x0;
    kernel_info.taskStackStartingAddress = MSP_INIT_VAL - MAIN_STACK_SIZE; // the diagrams in the rampup exercises show that there is a main stack before the task stacks.
    kernel_info.taskStackAllocatorAddress = kernel_info.taskStackStartingAddress;
    kernel_info.currentTime = 1;
    kernel_info.preemptionEnabled = 0; 
 
    // init memory here?:
    k_mem_init();
    // //
 
    for (int i = 0; i < MAX_TASKS; i++) {
        kernel_info.tcbs[i].ptask = 0;
        kernel_info.tcbs[i].stack_high = 0;
        kernel_info.tcbs[i].psp = 0;
        kernel_info.tcbs[i].tid = i;
        kernel_info.tcbs[i].state = EMPTY;
        kernel_info.tcbs[i].stack_size = 0;
        kernel_info.tcbs[i].requiresSetup = 1;
        kernel_info.tcbs[i].deadline = 0;
        kernel_info.tcbs[i].sleepDeadline = 0;
        kernel_info.tcbs[i].initialDeadlineDuration = 0;
    }
    TCB tcb;
    tcb.ptask = spin;
    tcb.stack_high = 0;
    tcb.psp = 0;
    tcb.state = EMPTY;
    tcb.stack_size = STACK_SIZE;
    tcb.requiresSetup = 1;
    tcb.deadline = 0;
    tcb.sleepDeadline = 0;
    tcb.initialDeadlineDuration = 0;
    osCreateTaskHelper(&tcb, 0);
}

• this consists of initializing your TCBs

TCB task1;
task1.ptask=&single_task_d1;
task1.stack_size = 0x400;
osCreateTask(&task1);

• Then you create our tasks back in your main

This is what the task looks like:

void single_task_d1(void* args){
	while(1){
		printf("Hello, world\r\n");
		for(int i = 0; i < 10000; i++);
		osYield();
	}
}

int osCreateTask(TCB* task) {
    kernel_info.preemptionEnabled = 0;
    const int ret = osCreateTaskHelper(task, 5);
    if (ret == RTX_OK && kernel_info.runningTask != -1) {
        EDFScheduleNewTask();
        __asm("SVC #1");
    }
    kernel_info.preemptionEnabled = 1;
    return ret;
}

So how does osYield work?

void osYield(void) {
    scheduleNewTask();
}

void scheduleNewTask() {
    int found = 0;
    kernel_info.previousTask = kernel_info.runningTask;
    
    // If the running task was stopped, we don't want to set it to ready again
    if (kernel_info.tcbs[kernel_info.runningTask].state == RUNNING) {
        kernel_info.tcbs[kernel_info.runningTask].state = READY;
    }
    int newTask = kernel_info.runningTask;
    for (int i = 0; i < MAX_TASKS; i++) {
        newTask = (newTask + 1) % MAX_TASKS;
        if (newTask != 0 && kernel_info.tcbs[newTask].state == READY) {
            found = 1;
            kernel_info.runningTask = newTask;
            kernel_info.tcbs[newTask].state = RUNNING;
            break;
        }
    }
    if (found == 0) {
        kernel_info.runningTask = 0;
        kernel_info.tcbs[0].state = RUNNING;
    }
    __asm("SVC #1");
}

• it makes a SVC call, because remember that switching between processes needs to be done in Kernel Mode, but we are generally in User Mode

Deliverable 3

I need some reminders for myself as to why we use the SVC. In theory, everything can be done at the user-level, and you don’t need to worry about making all these annoying system calls. But the reason we have system calls is because we want this level of separation between different tasks.

• Using system calls with the SVC provides a way to enforce rules and protect system resources

There are certain things you can only access through the SVC, like the stack pointer. You move the stack pointer to another address.

SVC_Handler:
    tst lr, #4
    ite eq
    mrseq r0, MSP
    mrsne r0, PSP
    mov r1, r0
    stmdb r1!, {r4-r11}
    tst lr, #4
    ite eq
    msreq MSP, r1
    msrne PSP, r1
	blx SVC_Handler_Main
    MRS R0, PSP
    LDMIA R0!, {r4-r11}
    MSR PSP, R0
    MOV LR, #0xFFFFFFFD
    BX LR

I need to understand what this does:

High Level

This code saves the context of the current task, calls a function to switch tasks, and then restores the context of the new task.

1. tst lr, #4: This tests the 4th bit of the link register (LR). The result of this test determines whether the main stack pointer (MSP) or the process stack pointer (PSP) was used before the interrupt.
2. ite eq: This stands for “If Then Else”. It’s used to conditionally execute the following instructions based on the result of the previous test.
3. mrseq r0, MSP and mrsne r0, PSP: These instructions read the value of the MSP or PSP into register r0, depending on the result of the test.
4. mov r1, r0 and stmdb r1!, {r4-r11}: These instructions save the current context (specifically, registers r4-r11) onto the stack.
5. msreq MSP, r1 and msrne PSP, r1: These instructions update the MSP or PSP with the new top of stack.
6. blx SVC_Handler_Main: This calls the main SVC handler function, which performs the actual task switch.
7. MRS R0, PSP, LDMIA R0!, {r4-r11}, and MSR PSP, R0: These instructions restore the context of the new task from the stack.
8. MOV LR, #0xFFFFFFFD: This sets the link register to a special value that tells the processor to use the PSP when it returns from the interrupt.
9. BX LR: This returns from the interrupt, resuming execution of the new task.

I have some logic, because the function can call OsSleep, OsYield, and OsSetDeadline, but that is when the stack pointer is in PSP.

• However, we also need the logic to work in MSP. So we make SVC calls depending on the context, add a flag

Deliverable 2

Alright, I kind of slacked off working on this second part. Need to catch. Basically, need to figure out how to allocate memory for different processes.

void two_task_1(void* args)
{
	printf("Second Task 1\n");
	void* ptr = k_mem_alloc(8);
	printf("Beginning of memory allocated for 2nd task %p\n", ptr);
	k_mem_dealloc(ptr);
	osTaskExit();
	printf("Beginning of memory allocated for 2nd task %p\n", ptr);
}
 
void two_task_2(void* args)
{
	printf("Second Task 2\n");
	void* ptr = k_mem_alloc(8);
	printf("Beginning of memory allocated for 2nd task %p\n", ptr);
	k_mem_dealloc(ptr);
	osTaskExit();
}
 

The HM is initialized to 0x200083c0

• the pointer is 0x200084c0 (which is correct because HM is 16 bytes) NO
• whatever, so this is the line (ptr + sizeof(HM), which points it to the data itself. If you substract sizeof(HM), you get the HM
• The pointer from two_task_1 should be 0x200083d0

The issue is caused by bad pointer arithmetic. This is our k_mem_init

void* k_mem_alloc(size_t size) {
    // round size up to the nearest multiple of 4
    if (size % 4 != 0) {
        size += 4 - size % 4;
    }
 
    // reject function calls when things are not set up
    if (heap_setup != 1 || size == 0) return NULL;
 
    HM** search = &first_heap_free;
    while (1) {
        if (*search == HEAP_END) return NULL;
        // Check that this block can fit the size 
        if ((*search)->size > (size + sizeof(HM))) {
            // Check if this block is big enough to split
            if ((*search)->size >= (size + 2 * sizeof(HM))) {
                // We can split this block into two blocks
                size_t oldSize = (*search)->size;
                size_t newSize1 = size + sizeof(HM);
                size_t newSize2 = oldSize - newSize1;
                HM* ret = *search;
                HM* newBlock = ((void*) *search) + newSize1;
                populateFreeHeapMetadata(newBlock, (HM*) ret->nextAddress, newSize2);
                populateAllocatedHeapMetadata(ret, newSize1);
                *search = newBlock;
                return ret + 1; // 1, not sizeof(HM) because ret is a HM*
            } else {
                // Leave this block intact
                HM* ret = *search;
                *search = (HM*) ret->nextAddress;
                populateAllocatedHeapMetadata(ret, ret->size);
                return ret + 1; // 1, not sizeof(HM) because ret is a HM*
            }
        }
        search = &((*search)->nextAddress);
    }
}

int k_mem_dealloc(void* ptr) {
    ...
    HM* this_heap_metadata = (HM*) ptr - 1; // this will only work if ptr is pointing to the memory address that the user got allocated
  ...
}

So updated with correct numbers that you should expect:

• The HM is initialized to 0x20008a3c0
• The pointer should be 0x200083d0 (which is where HM points to + 16)
• dealloc, and then alloc again should give the same pointer

The address space goes in the negative direction (up) as the stack grows

ADDR_STACK_j = MSP_INIT_VAL - MAIN_STACK_SIZE - (j-1)THREAD_STACK_SIZE

• Forget this, is just just for the stacks going up, but the numbers go down

Just think of the heap going down

• The pointer is 83d0

I’m confused, the new numbers are

• The HM is initialized to HEAP_START: 0x20008210
• The pointer should be 0x20008220 (which is where HM points to + 16)
• dealloc, and then alloc again should give the same pointer

So for test case 3:

• First block: 0x20008420

I am now testing the fragmentation:

• checking the size of the stack seems to be 48624

Deliverable 1

The stack has a limit, we set that to 0x4000 bytes for now.

We are going to break it up and keep track of multiple stacks – one for the main stack and several for the thread stacks.

• So a stack of stacks

The main stack is going to be pointed by the MSP.

MSP_INIT_VAL will store the location of the Main Stack Pointer

• This is initialized to 0x0

The addressing goes in the negative direction.

ADDR_STACK_j = MSP_INIT_VAL - MAIN_STACK_SIZE - (j-1)THREAD_STACK_SIZE

• The stack grows downwards
• The main stack size is to store general stack stuff

We now want to implement system calls, with the SVC.

Our OS will need to do most of its context switching via system calls, specifically using the SVC instruction and its sibling. PendSV. In particular, during a context switch we need to perform three tasks:

1. Save the current thread’s context onto its stack
2. Choose a new thread to run, and locate its stack
3. Load the new thread’s context into the registers from its stack

__asm void SVC_Handler(void)
{
  IMPORT SVC_Handler_Main
  TST lr, #4
  ITE EQ
  MRSEQ r0, MSP
  MRSNE r0, PSP
  B SVC_Handler_Main
}

So when we call __asm, the SVC_Handler automatically gets called (an interrupt gets called), and then we need to get into SVC_Handler_main

void SVC_Handler_Main( unsigned int *svc_args )
{
  unsigned int svc_number;
 
  /*
  * Stack contains:
  * r0, r1, r2, r3, r12, r14, the return address and xPSR
  * First argument (r0) is svc_args[0]
  */
  svc_number = ( ( char * )svc_args[ 6 ] )[ -2 ] ;
  printf("svc number %d \n", svc_number);
}