Race condition in CondVar

[windows-server-2003]

Bug Report

LLM Disclosure: I used the assistance of LLMs for investigating the bug and writing the reproduction code. However, I carefully reviewed the output and am submitting this report based on my own understanding of the bug.

What's the issue you encountered?

During the development of FourthTube, I discovered some threads occasionally hang (although rare).

It turns out that this hang is caused by a race condition in libctru CondVar (described later).

How can the issue be reproduced?

In the below code, the CondVar_WaitTimeout in main thread times out, which it should not.
The app showed the following output on a physical old 2ds.

REPRODUCED
ready=1 timeout=1 cv=0

main.c

#include <3ds.h>
#include <stdbool.h>
#include <stdio.h>

LightLock lock;
CondVar cv;
volatile bool ready;

static void worker(void *) {
	LightLock_Lock(&lock);
	ready = true;
	CondVar_Signal(&cv);
	CondVar_Wait(&cv, &lock);
	LightLock_Unlock(&lock);
}

int main(void)
{
	gfxInitDefault();
	consoleInit(GFX_TOP, NULL);

	LightLock_Init(&lock);
	CondVar_Init(&cv);
	ready = false;

	/* Get main thread priority (used later) */
	s32 priority;
	svcGetThreadPriority(&priority, CUR_THREAD_HANDLE);

	LightLock_Lock(&lock);
	/*
		The reproduction heavily depends on the timing of preemption by the thread scheduler.
		For consistent reproduction, we prioritize the worker thread over the main thread.
		This (hopefully) makes it switch to worker thread as soon as the below
			CondVar_WaitTimeout() unlocks the LightLock inside
	*/
	threadCreate(worker, NULL, 4 * 1024, priority - 1, -2, false); // higher priority, same core
	// The worker thread is blocked by the LightLock until the main thread releases it in CondVar_WaitTimeout() below

	int timed_out = CondVar_WaitTimeout(&cv, &lock, 1000000000LL);
	LightLock_Unlock(&lock);

	if (!ready) puts("Oops, something went wrong!");
	else puts(timed_out ? "REPRODUCED" : "NOT REPRODUCED");
	printf("ready=%d timeout=%d cv=%ld\n", ready, timed_out, (long)cv);

	while (aptMainLoop()) gspWaitForVBlank();

	gfxExit();
	return 0;
}

Makefile

.SUFFIXES:

TARGET := libctru-condvar-aba-repro
ARCH := -march=armv6k -mtune=mpcore -mfloat-abi=hard -mtp=soft
CFLAGS := -g -O0 -Wall -Wextra -mword-relocations -ffunction-sections $(ARCH)
LDFLAGS := -specs=3dsx.specs $(ARCH)
LIBS := -lctru -lm
OFILES := main.o
DEPSDIR := .
CPPFLAGS := -I$(DEVKITPRO)/libctru/include
LIBPATHS := -L$(DEVKITPRO)/libctru/lib

include $(DEVKITARM)/3ds_rules

LD := $(CC)

.PHONY: all clean

all: $(TARGET).3dsx

$(TARGET).3dsx: $(TARGET).elf
$(TARGET).elf: $(OFILES)

clean:
	rm -f $(TARGET).3dsx $(TARGET).elf $(TARGET).lst main.o main.d

-include main.d

Environment?

FourthTube uses a modified version of libctru.
However, the bug is independent from those changes, and the test code above reproduces the bug with the stock libctru v2.7.0, devkitARM r68 and an old 2DS.

Mechanism

Suppose there is a CondVar cv.

1. Thread A waits on cv, has completed CondVar_BeginWait but has not yet entered the wait with syncArbitrateAddressWithTimeout. Now *cv == -1. Note that the mutex is unlocked
2. Another thread B calls CondVar_WakeUp(cv, 1). Now *cv == 0. (note this wakeup notification is lost)
3. Yet another thread C waits on cv, which will wait in syncArbitrateAddress. Now *cv == -1.
4. Thread A happens to continue execution, which will also wait in syncArbitrateAddress.

Now both waiter threads are blocked. However, this is inconsistent with *cv (which is -1).
Suppose someone subsequently tries to wake up both threads by calling CondVar_Signal(cv) twice.
The first call will wake either of the waiting threads, but the second one will NOT wake up the other thread because CondVar_EndWait returns hasWaiters == false and the address arbiter is not signaled.

In the reproduction code above, thread B and C are the same thread.

Additional context

FourthTube uses FFmpeg library and its multithread video decoding capability.
This race condition surfaced as a hang of the decoder threads.