kernel/bpf/rqspinlock.c

Source file repositories/reference/linux-study-clean/kernel/bpf/rqspinlock.c

File Facts

System
Linux kernel
Corpus path
kernel/bpf/rqspinlock.c
Extension
.c
Size
23376 bytes
Lines
763
Domain
Core OS
Bucket
Scheduler, Processes, Timers, Sync, And Syscalls
Inferred role
Core OS: exported/initcall integration point
Status
integration implementation candidate

Why This File Exists

Core operating-system implementation surface: boot, tasks, memory, VFS, syscall-facing interfaces, synchronization, credentials, and isolation.

Dependency Surface

Detected Declarations

Annotated Snippet

struct rqspinlock_timeout {
	u64 timeout_end;
	u64 duration;
	u64 cur;
	u16 spin;
};

#define RES_TIMEOUT_VAL	2

DEFINE_PER_CPU_ALIGNED(struct rqspinlock_held, rqspinlock_held_locks);
EXPORT_SYMBOL_GPL(rqspinlock_held_locks);

static bool is_lock_released(rqspinlock_t *lock, u32 mask)
{
	if (!(atomic_read_acquire(&lock->val) & (mask)))
		return true;
	return false;
}

static noinline int check_deadlock_AA(rqspinlock_t *lock)
{
	struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
	int cnt = min(RES_NR_HELD, rqh->cnt);

	/*
	 * Return an error if we hold the lock we are attempting to acquire.
	 * We'll iterate over max 32 locks; no need to do is_lock_released.
	 */
	for (int i = 0; i < cnt - 1; i++) {
		if (rqh->locks[i] == lock)
			return -EDEADLK;
	}
	return 0;
}

/*
 * This focuses on the most common case of ABBA deadlocks (or ABBA involving
 * more locks, which reduce to ABBA). This is not exhaustive, and we rely on
 * timeouts as the final line of defense.
 */
static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask)
{
	struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
	int rqh_cnt = min(RES_NR_HELD, rqh->cnt);
	void *remote_lock;
	int cpu;

	/*
	 * Find the CPU holding the lock that we want to acquire. If there is a
	 * deadlock scenario, we will read a stable set on the remote CPU and
	 * find the target. This would be a constant time operation instead of
	 * O(NR_CPUS) if we could determine the owning CPU from a lock value, but
	 * that requires increasing the size of the lock word.
	 */
	for_each_possible_cpu(cpu) {
		struct rqspinlock_held *rqh_cpu = per_cpu_ptr(&rqspinlock_held_locks, cpu);
		int real_cnt = READ_ONCE(rqh_cpu->cnt);
		int cnt = min(RES_NR_HELD, real_cnt);

		/*
		 * Let's ensure to break out of this loop if the lock is available for
		 * us to potentially acquire.
		 */
		if (is_lock_released(lock, mask))
			return 0;

		/*
		 * Skip ourselves, and CPUs whose count is less than 2, as they need at
		 * least one held lock and one acquisition attempt (reflected as top
		 * most entry) to participate in an ABBA deadlock.
		 *
		 * If cnt is more than RES_NR_HELD, it means the current lock being
		 * acquired won't appear in the table, and other locks in the table are
		 * already held, so we can't determine ABBA.
		 */
		if (cpu == smp_processor_id() || real_cnt < 2 || real_cnt > RES_NR_HELD)
			continue;

		/*
		 * Obtain the entry at the top, this corresponds to the lock the
		 * remote CPU is attempting to acquire in a deadlock situation,
		 * and would be one of the locks we hold on the current CPU.
		 */
		remote_lock = READ_ONCE(rqh_cpu->locks[cnt - 1]);
		/*
		 * If it is NULL, we've raced and cannot determine a deadlock
		 * conclusively, skip this CPU.
		 */
		if (!remote_lock)
			continue;

Annotation

Implementation Notes