Sistema multitasking per Xmega

A fine anno passato mi è arrivata la richiesta di estendere il firmware AVR di un progetto preesistente per un nuovo prodotto. Il codice, che già di per sé era abbastanza intricato, rischiava di divenire una poltiglia incomprensibile e piena di bug. Così, chiacchierando con un amico informatico, concordiamo sul fatto che “se ci fossero i thread, il codice sarebbe veramente più lineare”. Ed è così che, dopo una serie di ricerche su GitHub ed affini, sono finito ad implementarmi un sistema multitasking per AVR Xmega.

Ancora AVR?

Con l’avvento dei controllori ARM a 32-bit, l’architettura AVR ha accusato un duro colpo. Quindi perché elaborare, nel 2021, un sistema multitasking per questa piattaforma? La risposta è quantomeno banale: l’hardware faceva già uso di questo particolare microcontrollore, ed il software era già stato scritto in buona parte.

Caratteristiche

Come punto di partenza ho fatto riferimento al repository xmultitasking ¹, una implementazione molto essenziale che ho esteso per rispondere alle seguenti esigenze:

• Non preemptive: è il task in esecuzione che rilascia la CPU di sua spontanea volontà;
• Statico: nessun uso di allocazione dinamica della memoria;
• Presenza di “systick”: è presente un timer che genera una interruzione periodica (es. 1ms). Un task può rilasciare la CPU per mettersi in attesa di un timeout;
• Semplici primitive di sincronizzazione.

Descrittore del task

Un task corrisponde, all’atto pratico, ad una funzione eseguita ciclicamente, ad esempio:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void task1() __attribute__((noreturn));

void task1() {
  /* do something, but once */

  for(;;) {
    /* do something */
		// Release CPU

		/* do something else */
		// Release CPU again
  }
}

Ciascun task può assumere uno fra i tre seguenti stati:

• in esecuzione
• pronto
• bloccato

Dato che l’AVR è un processore a singolo core, solo un task alla volta può essere in esecuzione, quindi detenere l’uso della CPU. Un task bloccato è in attesa di un qualche tipo di evento, come un timeout, una particolare interruzione oppure un evento da parte di un altro task. Il task pronto è invece in lista per poter riprendere l’esecuzione, non appena la CPU gli sarà resa disponibile.

Suddivisione dello stack

Nel layout di memoria tipico le variabili statiche sono allocate negli indirizzi di memoria più bassi, all’inizio della RAM. Tradizionalmente, quest’area è suddivisa in due sezioni, .data e .bss, quest’ultima riservata alle variabili statiche senza valore di inizializzazione. L’occupazione è perfettamente nota a tempo di compilazione e la si può ricavare interrogando avr-size project.elf.

 text    data     bss     dec     hex filename
   58       2       2      62      3e project.elf

Le variabili automatiche necessitano di un’area di memoria a dimensione variabile, che prende il nome di stack. L’area di stack è localizzata a partire dal fondo RAM e cresce verso gli indirizzi più bassi. La dimensione è, appunto, variabile: la memoria viene allocata quando si aggiungono nuove variabili allo scope, e poi automaticamente deallocata. Inoltre, è sullo stack che viene memorizzato l’indirizzo chiamante all’atto di una chiamata a funzione.

Per mantenere un riferimento alla testa dello stack è previsto un registro del processore dedicato, lo stack pointer (SP).

Ogni task possiede uno scope personale con la propia pila di variabili automatiche. Dunque, si rende necessario partizionare la memoria disponibile così da virtualizzare la presenza di MAX_TASK aree di stack. Nella corrente implementazione ciascun task ha la stessa quantità di stack, STACK_SIZE, pari a 200 byte.

Inizializzazione dello stack

Un task viene creato ricorrendo alla funzione TASK_create che, salvo un brevissimo prologo, rappresenta un alter ego della routine assembly TASK_init. Come sarà chiarito nel prossimo paragrafo la routine che gestisce il cambio di contesto si aspetta un assetto ben preciso dello stack. A partire dal fondo va riservato lo spazio per il program counter, per i 32 registri generali e per i registri accessori del core Xmega.

In fase di creazione di un nuovo task tutti i registri sono posti a zero meno che il program counter, che deve coincidere con l’indirizzo della funzione handler del task. È opportuno ricordare che alcuni modelli di Xmega hanno uno spazio di indirizzamento della memoria programma maggiore di 64 kword: in tal caso la dimensione del program counter è di 24 bit ed è necessario inserire un byte in più sullo stack. In questo semplice sistema di multitasking si suppone che l’handler non sia locato nella “memoria estesa”, pertanto il byte più significativo è sempre posto a zero.

Cambio di contesto

All’atto del passaggio da un task all’altro è necessario preservare sia il contenuto dei registri del processore, sia lo stato corrente dello stack pointer. La routine di cambio di contesto è implementata all’interno della funzione TASK_yield(), di cui parlerò nel prossimo paragrafo.

Le operazioni da eseguire sono, nell’ordine:

1. salvataggio del program counter per il task i (return address, o RA)
2. salvataggio di tutti i registri generali (r0-r31) e di eventuali registri accessori;
3. salvataggio dello stack pointer corrente SPi;
4. caricamento del nuovo stack pointer SPj;
5. caricamento dei registri registri accessori e dei registri generali;
6. ritorno all’indirizzo del task j

Con la routine di inizializzazione, queste sono le uniche parti di programma ad essere implementata in puro assembly dovendo modificare puntualmente il contenuto dello stack e del relativo puntatore.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

context_switch:
// Save general CPU registers (task i context)
push	r31
push	r30
; ... omissis ...
push	r1
push	r0
; save Xmega I/O register, omissis

// Save current stack pointer
; load SP vector base
ldi		zl, lo8(task_stack_ptr)
ldi		zh, hi8(task_stack_ptr)
; move to &SPi
lsl		r19				// old task index * 2
add		zl, r19
adc		zh, r1			// GGC keeps r1 always 0
; critical section, save stack pointer in SPi
cli
in		r16, CPU_SPL
st		Z+, r16
in		r16, CPU_SPH
sei
st		Z, r16

// Load next stack pointer
; load SP vector base (again!)
ldi		zl, lo8(task_stack_ptr)
ldi		zh, hi8(task_stack_ptr)
; move to &SPj
lsl		r17				// new task in index * 2
add		zl, r17
adc		zh, r1			// GGC keeps r1 always 0
; critical section, store SPj in stack pointer
ld		r16, Z+
cli
out		CPU_SPL, r16
ld		r16, Z
out		CPU_SPH, r16
sei

// Reload general CPU registers (task j context)
; restore Xmega I/O register, omissis

pop		r0
pop		r1
; ... omissis ...
pop		r30
pop		r31

; ret

È interessante osservare che in nessun punto del codice si vanno a manipolare gli indirizzi di ritorno, o almeno in apparenza. Questo perché l’istruzione call, qui usata per chiamare la TASK_yield, salva già l’indirizzo di ritorno sullo stack, pushando i due o tre byte del program counter. Viceversa, ret esegue l’operazione inversa per ritornare al chiamante. Il trucco che permette alla TASK_yield di effettuare il cambio di contesto sta tutto nello spostare lo stack pointer nella porzione di codice intermedia fra call e ret.

Scheduler

Lo scheduler implementa un semplice algoritmo round robin senza priorità e senza preemption, quindi deve essere invocato manualmente tramite la sopracitata funzione TASK_yield().

In breve, lo scheduler cicla finché la maschera dei task abilitati task_enable_mask_AT è nulla. Rilevata la presenza di almeno un task attivo, viene selezionato il primo a partire dal task corrente, quindi viene eseguito il cambio di contesto.

Nel caso in cui il task corrente sia l’unico ad essere stato risvegliato si evita il cambio di contesto, risparmiando qualche ciclo macchina.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// find next task
	lds		r17, task_index
find_next_task:
	lds		r16, task_index_mask
	lsl		r16
	inc		r17
	cpi		r17, 8
	brlt	no_wrap
	ldi		r17, 0			// task_index
	ldi		r16, 1			// task_index_mask
no_wrap:
	sts		task_index, r17
	sts		task_index_mask, r16

	//lds		r18, task_enable_mask_AT
	and		r16, r18		// & task_enable_mask_AT
	breq	find_next_task	// not enabled

	// Found a task

	// 1) check if same task, avoiding some context switch overhead
	cp		r17, r19
	brne	context_switch
	jmp		same_task

Stack smash!

L’architettura AVR non prevede alcun meccanismo hardware di protezione della memoria. Ma poiché un task potrebbe allocare più stack del dovuto con conseguenze disastrose, mi è parso opportuno implementare perlomeno un rozzo meccanismo software di controllo ispirandomi ai canary byte ².

Il principio è molto semplice: in coda ad ogni segmento di stack pongo un byte inizializzato ad un valore noto (canary byte), quindi ad ogni cambio di contesto verifico che il contenuto sia rimasto invariato. Se così non fosse, posso concludere che il task in procinto di rilasciare la CPU si è allargato troppo ed ha corrotto gli stack altrui.

In questi sciagurati casi c’è poco da fare: ho previsto che il programma abortisca, eventualmente lampeggiando un minaccioso LED rosso. Se sto debuggando posso comunque ispezionare il contenuto dei registri per annotare quale task ha compiuto il danno e salvare un dump della memoria.

Miglioramenti

• Stack smash detector;
• Watchdog;
• Sleepmode.

Reference