// include/linux/preempt.h:33-53
 *         PREEMPT_MASK:    0x000000ff
 *         SOFTIRQ_MASK:    0x0000ff00
 *         HARDIRQ_MASK:    0x000f0000
 *             NMI_MASK:    0x00f00000
 * PREEMPT_NEED_RESCHED:    0x80000000
 */
#define PREEMPT_BITS    8
#define SOFTIRQ_BITS    8
#define HARDIRQ_BITS    4
#define NMI_BITS    4

#define PREEMPT_SHIFT   0
#define SOFTIRQ_SHIFT   (PREEMPT_SHIFT + PREEMPT_BITS)
#define HARDIRQ_SHIFT   (SOFTIRQ_SHIFT + SOFTIRQ_BITS)
#define NMI_SHIFT   (HARDIRQ_SHIFT + HARDIRQ_BITS)

// include/linux/preempt.h:211-233
#define preempt_disable() \
do { \
    preempt_count_inc(); \
    barrier(); \
} while (0)
...
#define preempt_enable() \
do { \
    barrier(); \
    if (unlikely(preempt_count_dec_and_test())) \
        __preempt_schedule(); \
} while (0)

// include/linux/spinlock_types_raw.h:14-24
context_lock_struct(raw_spinlock) {
    arch_spinlock_t raw_lock;
#ifdef CONFIG_DEBUG_SPINLOCK
    unsigned int magic, owner_cpu;
    void *owner;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
    struct lockdep_map dep_map;
#endif
};
typedef struct raw_spinlock raw_spinlock_t;

// include/linux/spinlock_types.h:16-30
/* Non PREEMPT_RT kernels map spinlock to raw_spinlock */
context_lock_struct(spinlock) {
    union {
        struct raw_spinlock rlock;

#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))
        struct {
            u8 __padding[LOCK_PADSIZE];
            struct lockdep_map dep_map;
        };
#endif
    };
};
typedef struct spinlock spinlock_t;

spin_lock(&lock)                      // include/linux/spinlock.h:339
  |  取 &lock->rlock，纯转发
  v
raw_spin_lock(&lock->rlock)           // include/linux/spinlock.h:218
  |  debug/lockdep 构建下包装 _raw_spin_lock()
  v
_raw_spin_lock()                      // kernel/locking/spinlock.c:152
  |  __lockfunc 导出符号，SMP 实现入口
  v
__raw_spin_lock(lock)                 // include/linux/spinlock_api_smp.h:154
     preempt_disable()
     spin_acquire(&lock->dep_map, ...)   // lockdep 登记
     LOCK_CONTENDED(lock, trylock, lock) // 真正的锁操作

// include/linux/spinlock_api_smp.h:154-171
static inline void __raw_spin_lock(raw_spinlock_t *lock)
    __acquires(lock) __no_context_analysis
{
    preempt_disable();
    spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
    LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

static inline void __raw_spin_unlock(raw_spinlock_t *lock)
    __releases(lock)
{
    spin_release(&lock->dep_map, _RET_IP_);
    do_raw_spin_unlock(lock);
    preempt_enable();
}

// kernel/locking/spinlock.c:67-78
#define BUILD_LOCK_OPS(op, locktype)                    \
static void __lockfunc __raw_##op##_lock(locktype##_t *lock)        \
{                                   \
    for (;;) {                          \
        preempt_disable();                  \
        if (likely(do_raw_##op##_trylock(lock)))        \
            break;                      \
        preempt_enable();                   \
                                    \
        arch_##op##_relax(&lock->raw_lock);         \
    }                               \
}                                   \

// include/asm-generic/ticket_spinlock.h:33-51
static __always_inline void ticket_spin_lock(arch_spinlock_t *lock)
{
    u32 val = atomic_fetch_add(1<<16, &lock->val);
    u16 ticket = val >> 16;

    if (ticket == (u16)val)
        return;

    /*
     * atomic_cond_read_acquire() is RCpc, but rather than defining a
     * custom cond_read_rcsc() here we just emit a full fence. ...
     */
    atomic_cond_read_acquire(&lock->val, ticket == (u16)VAL);
    smp_mb();
}

// include/asm-generic/ticket_spinlock.h:53-69
static __always_inline bool ticket_spin_trylock(arch_spinlock_t *lock)
{
    u32 old = atomic_read(&lock->val);

    if (old >> 16)
        return false;

    return atomic_try_cmpxchg(&lock->val, &old, old + (1 << 16));
}

static __always_inline void ticket_spin_unlock(arch_spinlock_t *lock)
{
    /*
     * unlock() needs release semantics:
     */
    u16 val = atomic_add_return_release(1, &lock->val) >> 16;
    ...
}

// include/asm-generic/qspinlock_types.h:14-44
typedef struct qspinlock {
    union {
        atomic_t val;
        /*
         * By using the whole 2nd least significant byte for the
         * pending bit, we can allow better optimization of the lock
         * acquisition for the pending bit holder.
         */
#ifdef __LITTLE_ENDIAN
        struct {
            u8  locked;
            u8  pending;
        };
        struct {
            u16 locked_pending;
            u16 tail;
        };
#else
        ...
#endif
    };
} arch_spinlock_t;

// include/asm-generic/qspinlock_types.h:67-93
#define _Q_SET_MASK(type)   (((1U << _Q_ ## type ## _BITS) - 1)\
                << _Q_ ## type ## _OFFSET)
#define _Q_LOCKED_OFFSET    0
#define _Q_LOCKED_BITS      8
#define _Q_PENDING_OFFSET   (_Q_LOCKED_OFFSET + _Q_LOCKED_BITS)
#if CONFIG_NR_CPUS < (1U << 14)
#define _Q_PENDING_BITS     8
#else
#define _Q_PENDING_BITS     1
#endif
#define _Q_TAIL_IDX_OFFSET  (_Q_PENDING_OFFSET + _Q_PENDING_BITS)
#define _Q_TAIL_IDX_BITS    2
#define _Q_TAIL_CPU_OFFSET  (_Q_TAIL_IDX_OFFSET + _Q_TAIL_IDX_BITS)
#define _Q_TAIL_CPU_BITS    (32 - _Q_TAIL_CPU_OFFSET)
#define _Q_TAIL_OFFSET      _Q_TAIL_IDX_OFFSET
#define _Q_LOCKED_VAL       (1U << _Q_LOCKED_OFFSET)
#define _Q_PENDING_VAL      (1U << _Q_PENDING_OFFSET)

// include/asm-generic/qspinlock.h:107-129
static __always_inline void queued_spin_lock(struct qspinlock *lock)
{
    int val = 0;

    if (likely(atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL)))
        return;

    queued_spin_lock_slowpath(lock, val);
}
...
static __always_inline void queued_spin_unlock(struct qspinlock *lock)
{
    /*
     * unlock() needs release semantics:
     */
    smp_store_release(&lock->locked, 0);
}

 *              fast     :    slow                                  :    unlock
 *                       :                                          :
 * uncontended  (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
 *                       :       | ^--------.------.             /   :
 * pending               :    (0,1,1) +--> (0,1,0)   \           |   :
 * uncontended           :    (n,x,y) +--> (n,0,0) --'           |   :
 *   queue               :       | ^--'                          |   :
 * contended             :    (*,x,y) +--> (*,0,0) ---> (*,0,1) -'   :
 *   queue               :         ^--'                             :

// kernel/locking/qspinlock.c:156-206
    /*
     * If we observe any contention; queue.
     */
    if (val & ~_Q_LOCKED_MASK)
        goto queue;

    /*
     * trylock || pending
     *
     * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
     */
    val = queued_fetch_set_pending_acquire(lock);

    if (unlikely(val & ~_Q_LOCKED_MASK)) {

        /* Undo PENDING if we set it. */
        if (!(val & _Q_PENDING_MASK))
            clear_pending(lock);

        goto queue;
    }

    if (val & _Q_LOCKED_MASK)
        smp_cond_load_acquire(&lock->locked, !VAL);

    /*
     * take ownership and clear the pending bit.
     *
     * 0,1,0 -> 0,0,1
     */
    clear_pending_set_locked(lock);
    lockevent_inc(lock_pending);
    return;

static DEFINE_PER_CPU_ALIGNED(struct qnode, qnodes[_Q_MAX_NODES]);

// kernel/locking/qspinlock.h:52-69
static inline __pure u32 encode_tail(int cpu, int idx)
{
    u32 tail;

    tail  = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
    tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */

    return tail;
}
...
static inline struct qnode *decode_tail(u32 tail, struct qnode *qnodes)
{
    int cpu = ((tail >> _Q_TAIL_CPU_OFFSET) - 1) % nr_cpu_ids;
    int idx = (tail & _Q_TAIL_MASK) >> _Q_TAIL_IDX_OFFSET;

    return per_cpu_ptr(&qnodes[idx], cpu);
}

// kernel/locking/qspinlock.c:212-291
queue:
    lockevent_inc(lock_slowpath);
pv_queue:
    node = this_cpu_ptr(&qnodes[0].mcs);
    idx = node->count++;
    tail = encode_tail(smp_processor_id(), idx);
    ...
    old = xchg_tail(lock, tail);
    next = NULL;

    /*
     * if there was a previous node; link it and wait until reaching the
     * head of the waitqueue.
     */
    if (old & _Q_TAIL_MASK) {
        prev = decode_tail(old, qnodes);

        /* Link @node into the waitqueue. */
        WRITE_ONCE(prev->next, node);

        pv_wait_node(node, prev);
        arch_mcs_spin_lock_contended(&node->locked);

// kernel/locking/qspinlock.c:325-379
    /*
     * We're pending, we're at the head of the waitqueue, wait for the
     * owner to release the lock.
     */
    ...
    for (;;) {
        if (atomic_cond_read_acquire(&lock->val,
                         !(VAL & _Q_LOCKED_PENDING_MASK)))
            break;
    }

    /* take ownership and clear the tail */
    set_locked(lock);
    ...
    if (next) {
        arch_mcs_spin_unlock_contended(&next->locked);
        ...
    }

// drivers/char/random.c:156-168
int __cold execute_with_initialized_rng(struct notifier_block *nb)
{
    unsigned long flags;
    int ret = 0;

    spin_lock_irqsave(&random_ready_notifier.lock, flags);
    if (crng_ready())
        nb->notifier_call(nb, 0, NULL);
    else
        ret = raw_notifier_chain_register((struct raw_notifier_head *)&random_ready_notifier.head, nb);
    spin_unlock_irqrestore(&random_ready_notifier.lock, flags);
    return ret;
}

// include/linux/mutex_types.h:41-54
context_lock_struct(mutex) {
    atomic_long_t       owner;
    raw_spinlock_t      wait_lock;
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
    struct optimistic_spin_queue osq; /* Spinner MCS lock */
#endif
    struct list_head    wait_list;
#ifdef CONFIG_DEBUG_MUTEXES
    void            *magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
    struct lockdep_map  dep_map;
#endif
};

// kernel/locking/mutex.h:23-36
 * @owner: contains: 'struct task_struct *' to the current lock owner,
 * NULL means not owned. ...
 * Bit0 indicates a non-empty waiter list; unlock must issue a wakeup.
 * Bit1 indicates unlock needs to hand the lock to the top-waiter
 * Bit2 indicates handoff has been done and we're waiting for pickup.
 */
#define MUTEX_FLAG_WAITERS  0x01
#define MUTEX_FLAG_HANDOFF  0x02
#define MUTEX_FLAG_PICKUP   0x04

#define MUTEX_FLAGS     0x07

// kernel/locking/mutex.h:14-21
struct mutex_waiter {
    struct list_head    list;
    struct task_struct  *task;
    struct ww_acquire_ctx   *ww_ctx;
#ifdef CONFIG_DEBUG_MUTEXES
    void            *magic;
#endif
};

mutex_lock()
  |
  |-- [1] __mutex_trylock_fast()      owner: 0 -> current       (无锁 cmpxchg)
  |        失败
  |-- [2] __mutex_trylock()           含 WAITERS/HANDOFF 标志语义的 trylock
  |        失败
  |-- [3] mutex_optimistic_spin()     OSQ 排队 + 盯 owner 自旋   (不睡眠)
  |        失败
  |-- [4] wait_list 排队 + schedule_preempt_disabled() 睡眠     (FIFO)
  |        被唤醒
  |-- [5] __mutex_trylock_or_handoff() HANDOFF 语义拾取
  v
  获得锁

// kernel/locking/mutex.c:152-170
static __always_inline bool __mutex_trylock_fast(struct mutex *lock)
{
    unsigned long curr = (unsigned long)current;
    unsigned long zero = 0UL;

    MUTEX_WARN_ON(lock->magic != lock);

    if (atomic_long_try_cmpxchg_acquire(&lock->owner, &zero, curr))
        return true;

    return false;
}

// kernel/locking/mutex.c:285-291
void __sched mutex_lock(struct mutex *lock)
{
    might_sleep();

    if (!__mutex_trylock_fast(lock))
        __mutex_lock_slowpath(lock);
}

// kernel/locking/mutex.c:613-692
    preempt_disable();
    mutex_acquire_nest(&lock->dep_map, subclass, 0, nest_lock, ip);

    trace_contention_begin(lock, LCB_F_MUTEX | LCB_F_SPIN);
    if (__mutex_trylock(lock) ||
        mutex_optimistic_spin(lock, ww_ctx, NULL)) {
        /* got the lock, yay! */
        lock_acquired(&lock->dep_map, ip);
        ...
        preempt_enable();
        return 0;
    }

    raw_spin_lock_irqsave(&lock->wait_lock, flags);
    /*
     * After waiting to acquire the wait_lock, try again.
     */
    if (__mutex_trylock(lock)) {
        ...
        goto skip_wait;
    }
    ...
    if (!use_ww_ctx) {
        /* add waiting tasks to the end of the waitqueue (FIFO): */
        __mutex_add_waiter(lock, &waiter, &lock->wait_list);
    }
    ...
    set_current_state(state);
    for (;;) {
        bool first;
        ...
        if (__mutex_trylock(lock))
            goto acquired;
        ...
        raw_spin_unlock_irqrestore_wake(&lock->wait_lock, flags, &wake_q);

        schedule_preempt_disabled();

// kernel/locking/mutex.c:84-134
static inline bool __mutex_trylock_common(struct mutex *lock, bool handoff)
{
    unsigned long curr, owner = atomic_long_read(&lock->owner);

    for (;;) {
        unsigned long flags;

        /* We own the lock already? */
        if (__owner_task(owner) == current) {
            /*
             * o -> 0: ... trylock, but we already own the lock
             */
            MUTEX_WARN_ON(!owner & MUTEX_FLAG_WAITERS);
            return false;
        }

        flags = owner & MUTEX_FLAGS;

        if (flags & MUTEX_FLAG_PICKUP) {
            if (!handoff)
                return false;

            flags &= ~MUTEX_FLAG_PICKUP;
        } else if (flags & MUTEX_FLAG_HANDOFF) {
            if (!handoff)
                return false;
        }

        curr = (unsigned long)current | flags;

        if (atomic_long_try_cmpxchg_acquire(&lock->owner,
                            &owner, curr)) {
            ...
            return true;
        }
    }
}

// kernel/locking/mutex.c:444-481
static __always_inline bool
mutex_optimistic_spin(struct mutex *lock, struct ww_acquire_ctx *ww_ctx,
              struct mutex_waiter *waiter)
{
    if (!waiter) {
        /*
         * The purpose of the mutex_can_spin_on_owner() function is
         * to eliminate the overhead of osq_lock() and osq_unlock()
         * in case spinning isn't possible. ...
         */
        if (!mutex_can_spin_on_owner(lock))
            goto fail;

        /*
         * In order to avoid a stampede of mutex spinners trying to
         * acquire the mutex all at once, the spinners need to take a
         * MCS (queued) lock first before spinning on the owner field.
         */
        if (!osq_lock(&lock->osq))
            goto fail;
    }

    for (;;) {
        struct task_struct *owner;

        /* Try to acquire the mutex... */
        owner = __mutex_trylock_or_owner(lock);
        if (!owner)
            break;

        if (!mutex_spin_on_owner(lock, owner, ww_ctx, waiter))
            goto fail_unlock;
        ...

// kernel/locking/mutex.c:355-421
static bool mutex_spin_on_owner(struct mutex *lock,
                struct task_struct *owner,
                struct ww_acquire_ctx *ww_ctx,
                struct mutex_waiter *waiter)
{
    bool ret = true;
    ...
    lockdep_assert_preemption_disabled();

    for (;;) {
        int prev = READ_ONCE(waiter->ww_ctx ? waiter->ww_ctx->deadlock : 0);
        ...
        /*
         * If the owner changed, we must not spin.
         */
        if (!owner_on_cpu(owner)) {
            ret = false;
            break;
        }

        /*
         * Provide a ST_SPIN_ON_OWNER spark for debugging.
         */
        if (need_resched()) {
            ...
            ret = false;
            break;
        }
        ...
        cpu_relax();
    }
    ...
}

// kernel/locking/osq_lock.c:15-42
struct optimistic_spin_node {
    struct optimistic_spin_node *next, *prev;
    int locked; /* 1 if lock acquired */
    int cpu; /* encoded CPU # + 1 value */
};

static DEFINE_PER_CPU_SHARED_ALIGNED(struct optimistic_spin_node, osq_node);

/*
 * We use the value 0 to represent "no CPU", thus the encoded value
 * will be the CPU number incremented by 1.
 */
static inline int encode_cpu(int cpu_nr)
{
    return cpu_nr + 1;
}

// kernel/locking/osq_lock.c:93-148
bool osq_lock(struct optimistic_spin_queue *lock)
{
    struct optimistic_spin_node *node = this_cpu_ptr(&osq_node);
    struct optimistic_spin_node *prev, *next;
    int curr = encode_cpu(smp_processor_id());
    int old;

    node->locked = 0;
    node->next = NULL;
    node->cpu = curr;

    /*
     * We need both ACQUIRE (pairs with corresponding RELEASE in
     * unlock() uncontended, or fastpath) and RELEASE (to publish
     * the node fields we just initialised) semantics when updating
     * the lock tail.
     */
    old = atomic_xchg(&lock->tail, curr);
    if (old == OSQ_UNLOCKED_VAL)
        return true;

    prev = decode_cpu(old);
    node->prev = prev;
    ...
    smp_wmb();

    WRITE_ONCE(prev->next, node);
    ...
    /*
     * Wait to acquire the lock or cancellation. Note that need_resched()
     * will come with an IPI, which will wake smp_cond_load_relaxed() ...
     */
    if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
                  vcpu_is_preempted(node_cpu(node->prev))))
        return true;

// kernel/locking/mutex.c:235-253
static void __mutex_handoff(struct mutex *lock,
                struct task_struct *task)
{
    unsigned long owner = atomic_long_read(&lock->owner);

    for (;;) {
        unsigned long old, new;

        MUTEX_WARN_ON(__owner_task(owner) != current);
        MUTEX_WARN_ON(!(owner & MUTEX_FLAG_WAITERS));

        old = owner;
        new = (unsigned long)task;
        if (task) {
            new |= MUTEX_FLAG_PICKUP;
            new &= ~MUTEX_FLAG_HANDOFF;
        }
        ...
        if (atomic_long_try_cmpxchg(&lock->owner, &old, new))
            break;
        ...
    }
}

// kernel/locking/mutex.c:940-981
    /*
     * Release the lock before (potentially) taking the spinlock such that
     * other contenders can get on with things ASAP.
     *
     * Except when HANDOFF, in that case we must not clear the owner field,
     * but instead set it to the top waiter.
     */
    owner = atomic_long_read(&lock->owner);
    for (;;) {
        MUTEX_WARN_ON(__owner_task(owner) != current);

        if (owner & MUTEX_FLAG_HANDOFF)
            break;

        if (atomic_long_try_cmpxchg_release(&lock->owner, &owner, __owner_flags(owner))) {
            if (owner & MUTEX_FLAG_WAITERS)
                break;

            return;
        }
    }

    raw_spin_lock_irqsave(&lock->wait_lock, flags);
    debug_mutex_unlock(lock);
    if (!list_empty(&lock->wait_list)) {
        /* get the first entry from the wait-list: */
        struct mutex_waiter *waiter =
            list_first_entry(&lock->wait_list,
                     struct mutex_waiter, list);
        ...
        wake_q_add(&wake_q, next);
    }

// mm/ksm.c:3513-3546
static ssize_t run_store(struct kobject *kobj, struct kobj_attribute *attr,
             const char *buf, size_t count)
{
    unsigned int flags;
    int err;

    err = kstrtouint(buf, 10, &flags);
    if (err)
        return -EINVAL;
    ...
    mutex_lock(&ksm_thread_mutex);
    wait_while_offlining();
    if (ksm_run != flags) {
        ksm_run = flags;
        if (flags & KSM_RUN_UNMERGE) {
            set_current_oom_origin();
            err = unmerge_and_remove_all_rmap_items();
            clear_current_oom_origin();
            if (err) {
                ksm_run = KSM_RUN_STOP;
                count = err;
            }
        }
    }
    mutex_unlock(&ksm_thread_mutex);

// include/asm-generic/qrwlock_types.h:13-32
struct qrwlock {
    atomic_t        cnts;
    u8          wlocked;
    arch_spinlock_t     wait_lock;
};

// include/asm-generic/qrwlock.h:27-31
#define _QW_WAITING 0x100       /* A writer is waiting     */
#define _QW_LOCKED  0x0ff       /* A writer holds the lock */
#define _QW_WMASK   0x1ff       /* Writer mask         */
#define _QR_SHIFT   9       /* Reader count shift      */
#define _QR_BIAS    (1U << _QR_SHIFT)

// include/linux/rwlock_api_smp.h:225-239
static inline void __raw_write_lock(rwlock_t *lock)
    __acquires(lock) __no_context_analysis
{
    preempt_disable();
    rwlock_acquire(&lock->dep_map, 0, 0, _RET_IP_);
    LOCK_CONTENDED(lock, do_raw_write_trylock, do_raw_write_lock);
}

// include/asm-generic/qrwlock.h:78-92
static inline void queued_read_lock(struct qrwlock *lock)
{
    int cnts;

    cnts = atomic_add_return_acquire(_QR_BIAS, &lock->cnts);
    if (likely(!(cnts & _QW_WMASK)))
        return;

    /* The slowpath will decrement the reader count, if necessary. */
    queued_read_lock_slowpath(lock);
}

// include/asm-generic/qrwlock.h:94-102
static inline void queued_write_lock(struct qrwlock *lock)
{
    int cnts = 0;
    /* Optimize for the unfair lock case where the fair flag is 0. */
    if (likely(atomic_try_cmpxchg_acquire(&lock->cnts, &cnts, _QW_LOCKED)))
        return;

    queued_write_lock_slowpath(lock);
}

// kernel/locking/qrwlock.c:66-91
void __lockfunc queued_write_lock_slowpath(struct qrwlock *lock)
{
    int cnts;

    trace_contention_begin(lock, LCB_F_SPIN | LCB_F_WRITE);

    /* Put the writer into the wait queue */
    arch_spin_lock(&lock->wait_lock);

    /* Try to acquire the lock directly if no reader is present */
    if (!(cnts = atomic_read(&lock->cnts)) &&
        atomic_try_cmpxchg_acquire(&lock->cnts, &cnts, _QW_LOCKED))
        goto unlock;

    /* Set the waiting flag to notify readers that a writer is pending */
    atomic_or(_QW_WAITING, &lock->cnts);

    /* When no more readers or writers, set the locked flag */
    do {
        cnts = atomic_cond_read_relaxed(&lock->cnts, VAL == _QW_WAITING);
    } while (!atomic_try_cmpxchg_acquire(&lock->cnts, &cnts, _QW_LOCKED));
unlock:
    arch_spin_unlock(&lock->wait_lock);

    trace_contention_end(lock, 0);
}

// include/linux/seqlock_types.h:33-38
typedef struct seqcount {
    unsigned sequence;
#ifdef CONFIG_DEBUG_LOCK_ALLOC
    struct lockdep_map dep_map;
#endif
} seqcount_t;

// include/linux/seqlock.h:421-455
#define raw_write_seqcount_begin(s)                 \
do {                                    \
    if (seqprop_preemptible(s))                 \
        preempt_disable();                  \
                                    \
    do_raw_write_seqcount_begin(seqprop_ptr(s));            \
} while (0)

static inline void do_raw_write_seqcount_begin(seqcount_t *s)
{
    kcsan_nestable_atomic_begin();
    s->sequence++;
    smp_wmb();
}
...
static inline void do_raw_write_seqcount_end(seqcount_t *s)
{
    smp_wmb();
    s->sequence++;
    kcsan_nestable_atomic_end();
}

// include/linux/seqlock.h:272-320, 386-413
#define __read_seqcount_begin(s)                    \
({                                  \
    unsigned __seq;                         \
                                    \
    while (unlikely((__seq = seqprop_sequence(s)) & 1))     \
        cpu_relax();                        \
                                    \
    kcsan_atomic_next(KCSAN_SEQLOCK_REGION_MAX);            \
    __seq;                              \
})
...
#define raw_read_seqcount(s)                        \
({                                  \
    unsigned __seq = seqprop_sequence(s);               \
                                    \
    kcsan_atomic_next(KCSAN_SEQLOCK_REGION_MAX);            \
    __seq;                              \
})
...
static inline int do___read_seqcount_retry(const seqcount_t *s, unsigned start)
{
    kcsan_atomic_next(0);
    return unlikely(READ_ONCE(s->sequence) != start);
}
...
static inline int do_read_seqcount_retry(const seqcount_t *s, unsigned start)
{
    smp_rmb();
    return do___read_seqcount_retry(s, start);
}

seq = read_seqcount_begin(&s);   // 等到偶数序号并记下
...读共享数据...                 // 纯读，无任何原子操作
if (read_seqcount_retry(&s, seq)) // 序号变了 → 有写穿插，重来
        goto 重试;

// include/linux/seqlock_types.h:84-92
context_lock_struct(seqlock) {
    /*
     * Make sure that readers don't starve writers on PREEMPT_RT: use
     * seqcount_spinlock_t instead of seqcount_t. Check __SEQ_LOCK().
     */
    seqcount_spinlock_t seqcount;
    spinlock_t lock;
};
typedef struct seqlock seqlock_t;

// include/linux/seqlock.h:877-896
static inline void write_seqlock(seqlock_t *sl)
    __acquires(sl) __no_context_analysis
{
    spin_lock(&sl->lock);
    do_write_seqcount_begin(&sl->seqcount.seqcount);
}

static inline void write_sequnlock(seqlock_t *sl)
    __releases(sl) __no_context_analysis
{
    do_write_seqcount_end(&sl->seqcount.seqcount);
    spin_unlock(&sl->lock);
}

// include/linux/seqlock.h:227-231
SEQCOUNT_LOCKNAME(raw_spinlock, raw_spinlock_t,  false,    raw_spin)
SEQCOUNT_LOCKNAME(spinlock,     spinlock_t,      __SEQ_RT, spin)
SEQCOUNT_LOCKNAME(rwlock,       rwlock_t,        __SEQ_RT, read)
SEQCOUNT_LOCKNAME(mutex,        struct mutex,    true,     mutex)

// include/linux/seqlock.h:606-612
typedef struct seqcount_latch {
    seqcount_t seqcount;
} seqcount_latch_t;

// kernel/time/jiffies.c:43-59
__cacheline_aligned_in_smp DEFINE_RAW_SPINLOCK(jiffies_lock);
__cacheline_aligned_in_smp seqcount_raw_spinlock_t jiffies_seq =
    SEQCNT_RAW_SPINLOCK_ZERO(jiffies_seq, &jiffies_lock);
...
u64 get_jiffies_64(void)
{
    unsigned int seq;
    u64 ret;

    do {
        seq = read_seqcount_begin(&jiffies_seq);
        ret = jiffies_64;
    } while (read_seqcount_retry(&jiffies_seq, seq));
    return ret;
}

// kernel/time/timekeeping.c:814-832
static __always_inline ktime_t __ktime_get_fast_ns(...)
...
ktime_t ktime_get(void)
{
    struct timekeeper *tk = &tk_core.timekeeper;
    unsigned int seq;
    ktime_t base;
    u64 nsecs;

    do {
        seq = read_seqcount_begin(&tk_core.seq);
        base = tk->tkr_mono.base;
        nsecs = timekeeping_get_ns(&tk->tkr_mono);
    } while (read_seqcount_retry(&tk_core.seq, seq));
    ...
}

lock_classes[MAX_LOCKDEP_KEYS]        锁类数组          (lockdep.c:208)
list_entries[]                        依赖边数组        (lockdep.c:210)
lock_chains[]                         锁链缓存          (lockdep.c:3326)
chain_hlocks[]                        锁链的索引存储    (lockdep.c:3328)

// include/linux/lockdep_types.h:70-83
struct lockdep_subclass_key {
    char __one_byte;
} __attribute__ ((packed));

struct lock_class_key {
    struct lockdep_subclass_key subkeys[MAX_LOCKDEP_SUBCLASSES];
};

// include/linux/lockdep_types.h:98-147
struct lock_class {
    struct hlist_node       hash_entry;
    struct list_head        lock_entry;

    struct lockdep_subclass_key *key;
    unsigned int            subclass;
    unsigned int            dep_gen_id;

    /*
     * IRQ/softirq usage tracking bits:
     */
    unsigned long           usage_mask;
    struct stack_trace      usage_traces[XXX_LOCK_USAGE_STATES];
    ...
    /*
     * These fields represent a directed graph of lock dependencies,
     * round-robin-dispatched...
     */
    struct list_head        locks_after, locks_before;
    ...
    const char          *name;
    int             name_version;
    ...
};

// kernel/locking/lockdep.c:1285-1394
static struct lock_class *
register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
{
    struct lock_class *class = NULL;
    struct hlist_head *hash_head;
    struct lockdep_subclass_key *key;
    ...
    key = lock->key->subkeys + subclass;
    hash_head = classhash_table + hash_pointer(key);
    ...
    /*
     * We have to do the hash-walk again, to avoid taking
     * a lock-class whose key is identical to this one...
     */
    hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
        if (class->key == key) {
            ...
            goto out_unlock_set;
        }
    }
    ...
    /*
     * Allocate a new key from the static array...
     */
    if (nr_lock_classes >= MAX_LOCKDEP_KEYS) {
        ...
        dump_lock_classes();
        ...
        pr_err("BUG: MAX_LOCKDEP_KEYS too low!\n");
        ...
        return NULL;
    }
    ...
    /*
     * We haven't seen this lock before, so we need to
     * allocate a new class...
     */
    class = lock_classes + nr_lock_classes++;
    ...
    class->name = lock->name;
    class->key = key;
    class->subclass = subclass;
    ...
    hlist_add_head_rcu(&class->hash_entry, hash_head);
    ...

// include/linux/lockdep_types.h:206-257
struct held_lock {
    u64             prev_chain_key;
    unsigned long           acquire_ip;
    struct lockdep_map      *instance;
    struct lockdep_map      *nest_lock;
#ifdef CONFIG_LOCK_STAT
    u64             waittime_stamp;
    u64             holdtime_stamp;
#endif
    unsigned int            class_idx:MAX_LOCKDEP_KEYS_BITS;
    ...
    unsigned int            read:2;      /* 0: exclusive, 1: read, 2: recursive read */
    unsigned int            check:1;
    unsigned int            hardirqs_off:1;
    unsigned int            softirqs_off:1;
    unsigned int            references:12;
    unsigned int            pin_count;
};

// kernel/locking/lockdep.c:3056-3097
static int
check_deadlock(struct task_struct *curr, struct held_lock *next)
{
    ...
    for (i = 0; i < curr->lockdep_depth; i++) {
        prev = curr->held_locks + i;

        if (prev->instance == next->nest_lock)
            nest = prev;

        if (hlock_class(prev) != hlock_class(next))
            continue;

        /*
         * Allow read-after-read recursion of the same
         * lock class (i.e. read_lock(lock)+read_lock(lock)):
         */
        if ((next->read == 2) && prev->read)
            continue;
        ...
        if (nest)
            return 2;

        print_deadlock_bug(curr, prev, next);
        return 0;
    }
    return 1;
}

// kernel/locking/lockdep.c:3155-3170
    /*
     * Prove that the new <prev> -> <next> dependency would not
     * create a circular dependency in the graph. (We do this by
     * a breadth-first search into the graph starting at <next>,
     * and check whether we can reach <prev>.)
     *
     * The search is limited by the size of the circular queue (i.e.,
     * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes
     * in the graph whose neighbours are to be checked.
     */
    ret = check_noncircular(next, prev, trace);
    if (unlikely(bfs_error(ret) || ret == BFS_RMATCH))
        return 0;

    if (!check_irq_usage(curr, prev, next))
        return 0;

// kernel/locking/lockdep_internals.h:13-24
enum lock_usage_bit {
#define LOCKDEP_STATE(__STATE)      \
    LOCK_USED_IN_##__STATE,     \
    LOCK_USED_IN_##__STATE##_READ,  \
    LOCK_ENABLED_##__STATE,     \
    LOCK_ENABLED_##__STATE##_READ,
#include "lockdep_states.h"
#undef LOCKDEP_STATE
    LOCK_USED,
    LOCK_USED_READ,
    LOCK_USAGE_STATES,
};

// kernel/locking/lockdep.c:4617-4645
static int
mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
{
    if (!check)
        goto lock_used;

    /*
     * If non-trylock use in a hardirq or softirq context, then
     * mark the lock as used in these contexts:
     */
    if (!hlock->trylock) {
        if (hlock->read) {
            if (lockdep_hardirq_context())
                if (!mark_lock(curr, hlock,
                        LOCK_USED_IN_HARDIRQ_READ))
                    return 0;
        ...
        } else {
            if (lockdep_hardirq_context())
                if (!mark_lock(curr, hlock, LOCK_USED_IN_HARDIRQ))
                    return 0;
    ...