#include <linux/types.h>

#include <linux/kernel.h>

#include <linux/sched.h>

#include <linux/sched/rt.h>

#include <linux/sched/task.h>

#include <linux/sched/debug.h>

#include <linux/sched/wake_q.h>

#include <linux/sched/signal.h>

#include <linux/sched/clock.h>

#include <linux/export.h>

#include <linux/rwsem.h>

#include <linux/atomic.h>

#include <linux/hung_task.h>

#include <trace/events/lock.h>

#ifndef CONFIG_PREEMPT_RT

#include "lock_events.h"

#define RWSEM_READER_OWNED (1UL << 0)

#define RWSEM_NONSPINNABLE (1UL << 1)

#define RWSEM_OWNER_FLAGS_MASK (RWSEM_READER_OWNED | RWSEM_NONSPINNABLE)

#ifdef CONFIG_DEBUG_RWSEMS

# define DEBUG_RWSEMS_WARN_ON(c, sem) do { \

if (!debug_locks_silent && \

WARN_ONCE(c, "DEBUG_RWSEMS_WARN_ON(%s): count = 0x%lx, magic = 0x%lx, owner = 0x%lx, curr 0x%lx, list %sempty\n",\

#c, atomic_long_read(&(sem)->count), \

(unsigned long) sem->magic, \

atomic_long_read(&(sem)->owner), (long)current, \

rwsem_is_contended(sem) ? "" : "not ")) \

debug_locks_off(); \

} while (0)

# define DEBUG_RWSEMS_WARN_ON(c, sem)

#define RWSEM_WRITER_LOCKED (1UL << 0)

#define RWSEM_FLAG_WAITERS (1UL << 1)

#define RWSEM_FLAG_HANDOFF (1UL << 2)

#define RWSEM_FLAG_READFAIL (1UL << (BITS_PER_LONG - 1))

#define RWSEM_READER_SHIFT 8

#define RWSEM_READER_BIAS (1UL << RWSEM_READER_SHIFT)

#define RWSEM_READER_MASK (~(RWSEM_READER_BIAS - 1))

#define RWSEM_WRITER_MASK RWSEM_WRITER_LOCKED

#define RWSEM_LOCK_MASK (RWSEM_WRITER_MASK|RWSEM_READER_MASK)

#define RWSEM_READ_FAILED_MASK (RWSEM_WRITER_MASK|RWSEM_FLAG_WAITERS|\

RWSEM_FLAG_HANDOFF|RWSEM_FLAG_READFAIL)

static inline void rwsem_set_owner(struct rw_semaphore *sem)

{

lockdep_assert_preemption_disabled();

atomic_long_set(&sem->owner, (long)current);

}

static inline void rwsem_clear_owner(struct rw_semaphore *sem)

{

lockdep_assert_preemption_disabled();

atomic_long_set(&sem->owner, 0);

}

static inline bool rwsem_test_oflags(struct rw_semaphore *sem, long flags)

{

return atomic_long_read(&sem->owner) & flags;

}

static inline void __rwsem_set_reader_owned(struct rw_semaphore *sem,

struct task_struct *owner)

{

unsigned long val = (unsigned long)owner | RWSEM_READER_OWNED |

(atomic_long_read(&sem->owner) & RWSEM_NONSPINNABLE);

atomic_long_set(&sem->owner, val);

}

static inline void rwsem_set_reader_owned(struct rw_semaphore *sem)

{

__rwsem_set_reader_owned(sem, current);

}

#if defined(CONFIG_DEBUG_RWSEMS) || defined(CONFIG_DETECT_HUNG_TASK_BLOCKER)

struct task_struct *rwsem_owner(struct rw_semaphore *sem)

{

return (struct task_struct *)

(atomic_long_read(&sem->owner) & ~RWSEM_OWNER_FLAGS_MASK);

}

bool is_rwsem_reader_owned(struct rw_semaphore *sem)

{

/*

long count = atomic_long_read(&sem->count);

if (count & RWSEM_WRITER_MASK)

return false;

return rwsem_test_oflags(sem, RWSEM_READER_OWNED);

}

static inline void rwsem_clear_reader_owned(struct rw_semaphore *sem)

{

unsigned long val = atomic_long_read(&sem->owner);

while ((val & ~RWSEM_OWNER_FLAGS_MASK) == (unsigned long)current) {

if (atomic_long_try_cmpxchg(&sem->owner, &val,

val & RWSEM_OWNER_FLAGS_MASK))

return;

}

}

static inline void rwsem_clear_reader_owned(struct rw_semaphore *sem)

{

}

static inline void rwsem_set_nonspinnable(struct rw_semaphore *sem)

{

unsigned long owner = atomic_long_read(&sem->owner);

do {

if (!(owner & RWSEM_READER_OWNED))

break;

if (owner & RWSEM_NONSPINNABLE)

break;

} while (!atomic_long_try_cmpxchg(&sem->owner, &owner,

owner | RWSEM_NONSPINNABLE));

}

static inline bool rwsem_read_trylock(struct rw_semaphore *sem, long *cntp)

{

*cntp = atomic_long_add_return_acquire(RWSEM_READER_BIAS, &sem->count);

if (WARN_ON_ONCE(*cntp < 0))

rwsem_set_nonspinnable(sem);

if (!(*cntp & RWSEM_READ_FAILED_MASK)) {

rwsem_set_reader_owned(sem);

return true;

}

return false;

}

static inline bool rwsem_write_trylock(struct rw_semaphore *sem)

{

long tmp = RWSEM_UNLOCKED_VALUE;

if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp, RWSEM_WRITER_LOCKED)) {

rwsem_set_owner(sem);

return true;

}

return false;

}

static inline struct task_struct *

rwsem_owner_flags(struct rw_semaphore *sem, unsigned long *pflags)

{

unsigned long owner = atomic_long_read(&sem->owner);

*pflags = owner & RWSEM_OWNER_FLAGS_MASK;

return (struct task_struct *)(owner & ~RWSEM_OWNER_FLAGS_MASK);

}

void __init_rwsem(struct rw_semaphore *sem, const char *name,

struct lock_class_key *key)

{

#ifdef CONFIG_DEBUG_LOCK_ALLOC

/*

debug_check_no_locks_freed((void *)sem, sizeof(*sem));

lockdep_init_map_wait(&sem->dep_map, name, key, 0, LD_WAIT_SLEEP);

#ifdef CONFIG_DEBUG_RWSEMS

sem->magic = sem;

atomic_long_set(&sem->count, RWSEM_UNLOCKED_VALUE);

atomic_long_set(&sem->owner, 0L);

scoped_guard (raw_spinlock_init, &sem->wait_lock) {

sem->first_waiter = NULL;

}

#ifdef CONFIG_RWSEM_SPIN_ON_OWNER

osq_lock_init(&sem->osq);

}

EXPORT_SYMBOL(__init_rwsem);

enum rwsem_waiter_type {

RWSEM_WAITING_FOR_WRITE,

RWSEM_WAITING_FOR_READ

};

struct rwsem_waiter {

struct list_head list;

struct task_struct *task;

enum rwsem_waiter_type type;

unsigned long timeout;

bool handoff_set;

};

enum rwsem_wake_type {

RWSEM_WAKE_ANY, /* Wake whatever's at head of wait list */

RWSEM_WAKE_READERS, /* Wake readers only */

RWSEM_WAKE_READ_OWNED /* Waker thread holds the read lock */

};

#define RWSEM_WAIT_TIMEOUT DIV_ROUND_UP(HZ, 250)

#define MAX_READERS_WAKEUP 0x100

static inline

bool __rwsem_del_waiter(struct rw_semaphore *sem, struct rwsem_waiter *waiter)

__must_hold(&sem->wait_lock)

{

if (list_empty(&waiter->list)) {

sem->first_waiter = NULL;

return false;

}

if (sem->first_waiter == waiter) {

sem->first_waiter = list_first_entry(&waiter->list,

struct rwsem_waiter, list);

}

list_del(&waiter->list);

return true;

}

static inline bool

rwsem_del_waiter(struct rw_semaphore *sem, struct rwsem_waiter *waiter)

{

lockdep_assert_held(&sem->wait_lock);

if (__rwsem_del_waiter(sem, waiter))

return true;

atomic_long_andnot(RWSEM_FLAG_HANDOFF | RWSEM_FLAG_WAITERS, &sem->count);

return false;

}

static inline

struct rwsem_waiter *next_waiter(const struct rw_semaphore *sem,

const struct rwsem_waiter *waiter)

__must_hold(&sem->wait_lock)

{

struct rwsem_waiter *next = list_first_entry(&waiter->list,

struct rwsem_waiter, list);

if (next == sem->first_waiter)

return NULL;

return next;

}

static void rwsem_mark_wake(struct rw_semaphore *sem,

enum rwsem_wake_type wake_type,

struct wake_q_head *wake_q)

{

struct rwsem_waiter *waiter, *next;

long oldcount, woken = 0, adjustment = 0;

struct list_head wlist;

lockdep_assert_held(&sem->wait_lock);

/*

waiter = sem->first_waiter;

if (waiter->type == RWSEM_WAITING_FOR_WRITE) {

if (wake_type == RWSEM_WAKE_ANY) {

/*

wake_q_add(wake_q, waiter->task);

lockevent_inc(rwsem_wake_writer);

}

return;

}

/*

if (unlikely(atomic_long_read(&sem->count) < 0))

return;

/*

if (wake_type != RWSEM_WAKE_READ_OWNED) {

struct task_struct *owner;

adjustment = RWSEM_READER_BIAS;

oldcount = atomic_long_fetch_add(adjustment, &sem->count);

if (unlikely(oldcount & RWSEM_WRITER_MASK)) {

/*

if (time_after(jiffies, waiter->timeout)) {

if (!(oldcount & RWSEM_FLAG_HANDOFF)) {

adjustment -= RWSEM_FLAG_HANDOFF;

lockevent_inc(rwsem_rlock_handoff);

}

waiter->handoff_set = true;

}

atomic_long_add(-adjustment, &sem->count);

return;

}

/*

owner = waiter->task;

__rwsem_set_reader_owned(sem, owner);

}

/*

INIT_LIST_HEAD(&wlist);

do {

next = next_waiter(sem, waiter);

if (waiter->type == RWSEM_WAITING_FOR_WRITE)

continue;

woken++;

list_move_tail(&waiter->list, &wlist);

if (sem->first_waiter == waiter)

sem->first_waiter = next;

/*

if (unlikely(woken >= MAX_READERS_WAKEUP))

break;

} while ((waiter = next) != NULL);

adjustment = woken * RWSEM_READER_BIAS - adjustment;

lockevent_cond_inc(rwsem_wake_reader, woken);

oldcount = atomic_long_read(&sem->count);

if (!sem->first_waiter) {

/*

adjustment -= RWSEM_FLAG_WAITERS;

if (oldcount & RWSEM_FLAG_HANDOFF)

adjustment -= RWSEM_FLAG_HANDOFF;

} else if (woken) {

/*

if (oldcount & RWSEM_FLAG_HANDOFF)

adjustment -= RWSEM_FLAG_HANDOFF;

}

if (adjustment)

atomic_long_add(adjustment, &sem->count);

/* 2nd pass */

list_for_each_entry_safe(waiter, next, &wlist, list) {

struct task_struct *tsk;

tsk = waiter->task;

get_task_struct(tsk);

/*

smp_store_release(&waiter->task, NULL);

/*

wake_q_add_safe(wake_q, tsk);

}

}

static inline void

rwsem_del_wake_waiter(struct rw_semaphore *sem, struct rwsem_waiter *waiter,

struct wake_q_head *wake_q)

__releases(&sem->wait_lock)

{

bool first = sem->first_waiter == waiter;

wake_q_init(wake_q);

/*

if (rwsem_del_waiter(sem, waiter) && first)

rwsem_mark_wake(sem, RWSEM_WAKE_ANY, wake_q);

raw_spin_unlock_irq(&sem->wait_lock);

if (!wake_q_empty(wake_q))

wake_up_q(wake_q);

}

static inline bool rwsem_try_write_lock(struct rw_semaphore *sem,

struct rwsem_waiter *waiter)

__must_hold(&sem->wait_lock)

{

struct rwsem_waiter *first = sem->first_waiter;

long count, new;

lockdep_assert_held(&sem->wait_lock);

count = atomic_long_read(&sem->count);

do {

bool has_handoff = !!(count & RWSEM_FLAG_HANDOFF);

if (has_handoff) {

/*

if (first->handoff_set && (waiter != first))

return false;

}

new = count;

if (count & RWSEM_LOCK_MASK) {

/*

if (has_handoff || (!rt_or_dl_task(waiter->task) &&

!time_after(jiffies, waiter->timeout)))

return false;

new |= RWSEM_FLAG_HANDOFF;

} else {

new |= RWSEM_WRITER_LOCKED;

new &= ~RWSEM_FLAG_HANDOFF;

if (list_empty(&first->list))

new &= ~RWSEM_FLAG_WAITERS;

}

} while (!atomic_long_try_cmpxchg_acquire(&sem->count, &count, new));

/*

if (new & RWSEM_FLAG_HANDOFF) {

first->handoff_set = true;

lockevent_inc(rwsem_wlock_handoff);

return false;

}

/*

__rwsem_del_waiter(sem, waiter);

rwsem_set_owner(sem);

return true;

}

enum owner_state {

OWNER_NULL = 1 << 0,

OWNER_WRITER = 1 << 1,

OWNER_READER = 1 << 2,

OWNER_NONSPINNABLE = 1 << 3,

};

#ifdef CONFIG_RWSEM_SPIN_ON_OWNER

static inline bool rwsem_try_write_lock_unqueued(struct rw_semaphore *sem)

{

long count = atomic_long_read(&sem->count);

while (!(count & (RWSEM_LOCK_MASK|RWSEM_FLAG_HANDOFF))) {

if (atomic_long_try_cmpxchg_acquire(&sem->count, &count,

count | RWSEM_WRITER_LOCKED)) {

rwsem_set_owner(sem);

lockevent_inc(rwsem_opt_lock);

return true;

}

}

return false;

}

static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem)

{

struct task_struct *owner;

unsigned long flags;

bool ret = true;

if (need_resched()) {

lockevent_inc(rwsem_opt_fail);

return false;

}

/*

owner = rwsem_owner_flags(sem, &flags);

/*

if ((flags & RWSEM_NONSPINNABLE) ||

(owner && !(flags & RWSEM_READER_OWNED) && !owner_on_cpu(owner)))

ret = false;

lockevent_cond_inc(rwsem_opt_fail, !ret);

return ret;

}

static inline enum owner_state

rwsem_owner_state(struct task_struct *owner, unsigned long flags)

{

if (flags & RWSEM_NONSPINNABLE)

return OWNER_NONSPINNABLE;

if (flags & RWSEM_READER_OWNED)

return OWNER_READER;

return owner ? OWNER_WRITER : OWNER_NULL;

}

static noinline enum owner_state

rwsem_spin_on_owner(struct rw_semaphore *sem)

{

struct task_struct *new, *owner;

unsigned long flags, new_flags;

enum owner_state state;

lockdep_assert_preemption_disabled();

owner = rwsem_owner_flags(sem, &flags);

state = rwsem_owner_state(owner, flags);

if (state != OWNER_WRITER)

return state;

for (;;) {

/*

new = rwsem_owner_flags(sem, &new_flags);

if ((new != owner) || (new_flags != flags)) {

state = rwsem_owner_state(new, new_flags);

break;

}

/*

barrier();

if (need_resched() || !owner_on_cpu(owner)) {

state = OWNER_NONSPINNABLE;

break;

}

cpu_relax();

}

return state;

}

static inline u64 rwsem_rspin_threshold(struct rw_semaphore *sem)

{

long count = atomic_long_read(&sem->count);

int readers = count >> RWSEM_READER_SHIFT;

u64 delta;

if (readers > 30)

readers = 30;

delta = (20 + readers) * NSEC_PER_USEC / 2;

return sched_clock() + delta;

}

static bool rwsem_optimistic_spin(struct rw_semaphore *sem)

{

bool taken = false;

int prev_owner_state = OWNER_NULL;

int loop = 0;

u64 rspin_threshold = 0;

/* sem->wait_lock should not be held when doing optimistic spinning */

if (!osq_lock(&sem->osq))

goto done;

/*

for (;;) {

enum owner_state owner_state;

owner_state = rwsem_spin_on_owner(sem);

if (owner_state == OWNER_NONSPINNABLE)

break;

/*

taken = rwsem_try_write_lock_unqueued(sem);

if (taken)

break;

/*

if (owner_state == OWNER_READER) {

/*

if (prev_owner_state != OWNER_READER) {

if (rwsem_test_oflags(sem, RWSEM_NONSPINNABLE))

break;

rspin_threshold = rwsem_rspin_threshold(sem);

loop = 0;

}

/*

else if (!(++loop & 0xf) && (sched_clock() > rspin_threshold)) {

rwsem_set_nonspinnable(sem);

lockevent_inc(rwsem_opt_nospin);

break;

}

}

/*

if (owner_state != OWNER_WRITER) {

if (need_resched())

break;

if (rt_or_dl_task(current) &&

(prev_owner_state != OWNER_WRITER))

break;

}

prev_owner_state = owner_state;

/*

cpu_relax();

}

osq_unlock(&sem->osq);

done:

lockevent_cond_inc(rwsem_opt_fail, !taken);

return taken;

}

static inline void clear_nonspinnable(struct rw_semaphore *sem)

{

if (unlikely(rwsem_test_oflags(sem, RWSEM_NONSPINNABLE)))

atomic_long_andnot(RWSEM_NONSPINNABLE, &sem->owner);

}

static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem)

{

return false;

}

static inline bool rwsem_optimistic_spin(struct rw_semaphore *sem)

{

return false;

}

static inline void clear_nonspinnable(struct rw_semaphore *sem) { }

static inline enum owner_state

rwsem_spin_on_owner(struct rw_semaphore *sem)

{

return OWNER_NONSPINNABLE;

}

static inline void rwsem_cond_wake_waiter(struct rw_semaphore *sem, long count,

struct wake_q_head *wake_q)

{

enum rwsem_wake_type wake_type;