Introduction
Shorter post. I have a lot of stuff to do recently now that my school year has started but I figured this side-quest was worth writing up. One of my classes is about embedded systems; we are given a Maker Pico board and tasked to make a project using the board. One of my professors has spent the last few months or so porting TRON Forum's μT-Kernel for the Pico. The main issue is that the Pico is a dual-core board and the μT-Kernel does not support symmetric multiprocessing out of the box, so some engineering work is required to get this done.
Anyways there was an open challenge worth around 30% of our grade (maximum) to anyone who could find a bug in the professor's port. I got lazy and pointed GLM 5.3 at it for around 30 minutes, it produced a finding and I spent the better half of my afternoon understanding it, replicating a proof-of-concept for the bug, testing it on hardware, patching the kernel myself and then verifying the proof-of-concept failed on the newly patched kernel.
It cost about two dollars in GLM 5.3 Flash tokens; which I figure is a worthwhile tradeoff for getting a decent amount of my grade settled in the first week. To be honest I probably could have identified the bug myself over maybe a week, the codebase is small enough and the vulnerability is simple enough that a manual audit would have been successful. But, ah, I dunno. I think understanding whatever arcane, Borgesian Claudem-Ipsum these models produce and translating it into human-readable English is a worthwhile skill to practice in this day and age. Do I feel like a hack? A little bit. Aren't we all hacks now though?
The bug
Frankly the bug is sort of lame but it is critical.
Since the microkernel should now support dual-core processing, new safeguards need to be put in place to prevent race conditions or cross-core corruption of resources. One of these is the acquiring of a shared kernel lock between the two cores. The kernel implements these funny macros BEGIN_CRITICAL_SECTION and END_CRITICAL_SECTION:
18 #if TK_SUPPORT_SMP
17 #define KNL_KERNEL_LOCK_ENTER()>knl_kernel_lock_enter()
16 #define KNL_KERNEL_LOCK_LEAVE()>knl_kernel_lock_leave()
15 #else
14 #define KNL_KERNEL_LOCK_ENTER()
13 #define KNL_KERNEL_LOCK_LEAVE()
12 #endif
11
10 #define BEGIN_CRITICAL_SECTION> { UINT _primask_ = disint();> > > \
9 │ > > > KNL_KERNEL_LOCK_ENTER();
8 #define END_CRITICAL_SECTION> KNL_KERNEL_LOCK_LEAVE();> > > > \
7 │ > > > if ( !isDI(_primask_)>> > > > \
6 │ │ │ │ │ && *knl_ctxtsk_slot() != *knl_schedtsk_slot()>> \
5 │ │ │ │ │ && !*knl_dispatch_disabled_slot() ) {>> > \
4 │ │ │ │ │ knl_dispatch();>> > > > \
3 │ │ │ │ }>> > > > > > \
2 │ │ │ │ set_primask(_primask_); }
These macros call KNL_KERNEL_LOCK_ENTER and KNL_KERNEL_LOCK_LEAVE respectively. Hopefully it is intuitive as to what those clearly-named functions do. These macros are initialized whenever a single core has to acquire a shared kernel resource. However, the original kernel (which does not support symmetric multi-processing) had its own way of preventing race-conditions on a single processor: the EI() and DI() functions. These stand for ENABLE / DISABLE INTERRUPT: they prevent another process on the same core from interrupting a given process.
These functions both kind of do the same thing, but the difference is that EI() and DI() prevent races with other processes on the same core, and KNL_KERNEL_LOCK_ENTER prevents a race across both cores. So, any function that only masks interrupts without acquiring the shared kernel lock would be safe on one core but not on multiple.
Hopefully you see where this is going. When the operating system was patched to support SMP, there is one function that was missed: the kernel malloc() and free() functions. Here they are:
1 │ DI(imask); /* Exclusive control by interrupt disable */
2 │
3 │ /* Search FreeQue */
4 │ q = knl_searchFreeArea(knl_imacb, size);
5 │ if ( q == &(knl_imacb->freeque) ) {
6 │ │ q = NULL; /* Insufficient memory */
7 │ │ goto err_ret;
8 │ }
9 │
10 │ /* There is free area: Split from FreeQue once */
11 │ knl_removeFreeQue(q);
12 │
13 │ aq = q - 1;
14 │
15 │ /* If there are fragments smaller than the minimum fragment size,
16 │ │ allocate them also */
17 │ if ( FreeSize(q) - size >= MIN_FRAGMENT + sizeof(QUEUE) ) {
18 │ │
19 │ │ /* Divide area into 2 */
20 │ │ aq2 = (QUEUE*)((VB*)(aq + 1) + size);
21 │ │ knl_insertAreaQue(aq, aq2);
22 │ │
23 │ │ /* Register remaining area to FreeQue */
24 │ │ knl_appendFreeArea(knl_imacb, aq2);
25 │ }
26 │ setAreaFlag(aq, AREA_USE);
27 │
28 err_ret:
29 │ EI(imask);This code disables interrupts, and then performs an allocation. The allocations all invariably modify the kernel freelist through knl_removeFreeQue and knl_searchFreeArea. In our case, the shared kernel resource is that freelist. The PoC should then be simple: we have two processes on two cores spamming mallocs until the freelist is corrupted and subsequent allocations start to fail. Notably there is a single kernel freelist for all allocations of all sizes, so any two concurrent allocations regardless of size have a chance of preventing all further allocations completely. In my experience it took around 500 concurrent allocations for the race to get hit.
The bug is kinda stupid, subtle yet freakishly obvious and severe at the same time, but I think it's funny. To be honest I have little experience in embedded systems, especially RTOSes for microcontrollers, so coming into this my notional idea of an RTOS was a bit skewed. My understanding is that dynamic allocation for a RTOS is rare and frowned upon, typically these are only used when the microprocessor is initializing all of its structures. The initializations are pretty often concurrent, though -- two tasks could setup their initialization on two different cores at once, thus increasing the likelihood of the race to get hit. I can see this very clearly being an issue for, say, undergraduate student projects (the main use-case for the OS to begin with).
The patch is really simple; just replace DI() and EI() in the malloc() code with the correct BEGIN_CRITICAL_SECTION macros, so that memory operations acquire the given locks. For completeness sake here is the proof of concept I used:
72 #include <tk/tkernel.h>
71 #include <tm/tmonitor.h>
70 #include <bsp/libbsp.h>
69
68 #include "usb_console_compat.h"
67 #include "race_harness.h"
66
65 #define POOL_SIZE>32768
64 #define BUTTON_PIN> 20
63 #define HEARTBEAT_OPS>100
62
61 LOCAL void churn_task(INT stacd, void *exinf)
60 {
59 │ UW> n = 0, ok = 0, fail = 0;
58 │
57 │ (void)exinf;
56 │
55 │ // wait for gp20 to be pressed //
54 │ gpio_set_pin(BUTTON_PIN, GPIO_MODE_IN);
53 │ tm_printf((UB *)"[churn%d] waiting for GP20\n", stacd);
52 │ while ( gpio_get_val(BUTTON_PIN) != 0 ) {
51 │ │ tk_dly_tsk(10);
50 │ }
49 │
48 │ tm_printf((UB *)"[RACE COND] program started! \n[RACE COND]it should take around 20k mallocs / frees for the program to suddenly crash.\n", stacd);
47 │ tm_printf((UB *)"[churn%d] race started\n", stacd);
46 │
45 │ for(;;) {
44 │ │ void> *p = Kmalloc(POOL_SIZE);
43 │ │
42 │ │ if ( p != NULL ) {
41 │ │ │ ok++;
40 │ │ │ Kfree(p);
39 │ │ } else {
38 │ │ │ fail++;
37 │ │ }
36 │ │
35 │ │ n++;
34 │ │ if ( (n % HEARTBEAT_OPS) == 0 ) {
33 │ │ │ tm_printf((UB *)"[churn%d] n=%u ok=%u fail=%u\n",
32 │ │ │ │ stacd, n, ok, fail);
31 │ │ }
30 │ }
29 }
28
27 LOCAL T_CTSK ctsk_churn0 = {
26 │ .itskpri> = 10,
25 │ .stksz> > = 4096,
24 │ .task>> = churn_task,
23 │ .tskatr>> = TA_HLNG | TA_RNG3 | TA_ASSPRC,
22 │ .assprc>> = TP_PRC1,
21 };
20
19 LOCAL T_CTSK ctsk_churn1 = {
18 │ .itskpri> = 10,
17 │ .stksz> > = 4096,
16 │ .task>> = churn_task,
15 │ .tskatr>> = TA_HLNG | TA_RNG3 | TA_ASSPRC,
14 │ .assprc>> = TP_PRC2,
13 };
12
11 EXPORT INT usermain_raceharness(void)
10 {
9 │ ID> tid;
8 │
7 │ tid = tk_cre_tsk(&ctsk_churn0);
6 │ if ( tid > E_OK ) tk_sta_tsk(tid, 0);
5 │ tid = tk_cre_tsk(&ctsk_churn1);
4 │ if ( tid > E_OK ) tk_sta_tsk(tid, 1);
3 │
2 │ tk_slp_tsk(TMO_FEVR);
1 │ return 0;
73 }This code was, of course, generated by an AI. But it is simple enough -- you just create two tasks, pin them to core 0 an core 1 respectively, and make them spam allocations and frees. In about a second the kernel freelist corruption will occur, at which point the tasks will continue printing their failed allocations or some arcane kernel corruption will hard-crash the microprocessor entirely.
This was a fun way to spend like, an afternoon. On some level I do enjoy working with real, physical microcontrollers -- I like the low-levelness of it all, I like holding a chip in my hands. I am drawn to these machines in a strange, theological way; I could stare at them for hours. They look like the corkscrew passageways of some wind-eroded temple, worshipped at by antediluvian cultures with inscrutable languages and incomprehensible rituals. Anyways, that's all from me -- like and retweet for my inevitable pivot out of cybersecurity into hardware, and then my subsequent decades-long descent after that into mysticism. The final bleedinghe.art post will be me recreating the zairja.
Reward for reaching the end of this post