// include/linux/cpuidle.h

struct cpuidle_state {
    ...
    s64             exit_latency_ns;
    s64             target_residency_ns;
    unsigned int    exit_latency;     /* in US */
    unsigned int    target_residency; /* in US */

    unsigned int    flags;
    int             power_usage; /* in mW */

    int (*enter)    (struct cpuidle_device *dev, struct cpuidle_driver *drv, int index);
};

/* Idle State Flags */
#define CPUIDLE_FLAG_NONE           (0x00)
#define CPUIDLE_FLAG_POLLING        BIT(0) /* polling state */
#define CPUIDLE_FLAG_COUPLED        BIT(1) /* state applies to multiple cpus */
#define CPUIDLE_FLAG_TIMER_STOP     BIT(2) /* timer is stopped on this state */
#define CPUIDLE_FLAG_UNUSABLE        BIT(3) /* avoid using this state */
#define CPUIDLE_FLAG_OFF        BIT(4) /* disable this state by default */
#define CPUIDLE_FLAG_TLB_FLUSHED    BIT(5) /* idle-state flushes TLBs */
#define CPUIDLE_FLAG_RCU_IDLE        BIT(6) /* idle-state takes care of RCU */

// include/linux/cpuidle.h

struct cpuidle_governor {
    char                 name[CPUIDLE_NAME_LEN];
    struct list_head     governor_list;
    unsigned int         rating; // the governor's idea of how useful it is. By default, the kernel will use
                                 // the governor with the highest rating value, but the system administrator can override that choice
    int  (*select)       (struct cpuidle_driver *drv, struct cpuidle_device *dev, bool *stop_tick);
    void (*reflect)      (struct cpuidle_device *dev, int index);
};

struct cpuidle_driver {
    ...
    const char             *name;
    struct module          *owner;

    struct cpuidle_state    states[CPUIDLE_STATE_MAX]; /* must be ordered in decreasing power consumption */
    int                     state_count;
    int                     safe_state_index;

    struct cpumask         *cpumask; /* the driver handles the cpus in cpumask */
    const char             *governor;/* preferred governor to switch at register time */
};

int cpuidle_register_driver(struct cpuidle_driver *drv);

struct cpuidle_device {
    unsigned int        registered:1;
    unsigned int        enabled:1;
    unsigned int        poll_time_limit:1;
    unsigned int        cpu;
    ktime_t            next_hrtimer;

    int            last_state_idx;
    u64            last_residency_ns;
    u64            poll_limit_ns;
    u64            forced_idle_latency_limit_ns;
    struct cpuidle_state_usage    states_usage[CPUIDLE_STATE_MAX];
    struct cpuidle_state_kobj *kobjs[CPUIDLE_STATE_MAX];
    struct cpuidle_driver_kobj *kobj_driver;
    struct cpuidle_device_kobj *kobj_dev;
    struct list_head     device_list;

    cpumask_t        coupled_cpus;
    struct cpuidle_coupled    *coupled;
};

// drivers/cpuidle/governors/menu.c

static struct cpuidle_governor menu_governor = {
    .name    =    "menu",
    .rating  =    20,
    .select  =    menu_select,
    .reflect =    menu_reflect,
};

static int __init init_menu(void) {
    return cpuidle_register_governor(&menu_governor);
}

postcore_initcall(init_menu);

// menu_select - selects the next idle state to enter
// @drv: cpuidle driver containing state data
// @dev: the CPU
// @stop_tick: indication on whether or not to stop the tick
static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev, bool *stop_tick) {
    struct menu_device *data = this_cpu_ptr(&menu_devices);
    s64 latency_req = cpuidle_governor_latency_req(dev->cpu);

    /* determine the expected residency time, round up */
    delta = tick_nohz_get_sleep_length(&delta_tick);
    data->next_timer_ns = delta;

    /* Use the lowest expected idle interval to pick the idle state. */
    predicted_ns = ...;

    // Find the idle state with the lowest power while satisfying our constraints.
    for (i = 0; i < drv->state_count; i++) {
        struct cpuidle_state *s = &drv->states[i];
        if (s->target_residency_ns > predicted_ns) {
            // Use a physical idle state, not busy polling, unless a timer is going to trigger soon enough.
            if ((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) && s->exit_latency_ns <= latency_req && s->target_residency_ns <= data->next_timer_ns) {
                predicted_ns = s->target_residency_ns;
                idx = i;
                break;
            }
            if (predicted_ns < TICK_NSEC)
                break;

            if (!tick_nohz_tick_stopped()) {
                // If the state selected so far is shallow, waking up early won't hurt, so retain the
                // tick in that case and let the governor run again in the next iteration of the loop.
                predicted_ns = drv->states[idx].target_residency_ns;
                break;
            }

            // If the state selected so far is shallow and this state's target residency matches the time till the
            // closest timer event, select this one to avoid getting stuck in the shallow one for too long.
            if (drv->states[idx].target_residency_ns < TICK_NSEC && s->target_residency_ns <= delta_tick)
                idx = i;

            return idx;
        }
        if (s->exit_latency_ns > latency_req)
            break;

        idx = i;
    }

    // Don't stop the tick if the selected state is a polling one or if the
    // expected idle duration is shorter than the tick period length.
    if (((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) || predicted_ns < TICK_NSEC) && !tick_nohz_tick_stopped()) {
        *stop_tick = false;

        if (idx > 0 && drv->states[idx].target_residency_ns > delta_tick) {
            // The tick is not going to be stopped and the target residency of the state to be returned is not within
            // the time until the next timer event including the tick, so try to correct that.
            for (i = idx - 1; i >= 0; i--) {
                idx = i;
                if (drv->states[i].target_residency_ns <= delta_tick)
                    break;
            }
        }
    }

    return idx;
}

// drivers/cpuidle/cpuidle-haltpoll.c

static struct cpuidle_driver haltpoll_driver = {
    .name = "haltpoll",
    .governor = "haltpoll",
    .states = {
        { /* entry 0 is for polling */ },
        {
            .enter            = default_enter_idle,
            .exit_latency     = 1,
            .target_residency = 1,
            .power_usage      = -1,
            .name            = "haltpoll idle",
            .desc            = "default architecture idle",
        },
    },
    .safe_state_index = 0,
    .state_count = 2,
};

static int __init haltpoll_init(void) {
    struct cpuidle_driver *drv = &haltpoll_driver;

    cpuidle_poll_state_init(drv);
    cpuidle_register_driver(drv); // register driver
    haltpoll_cpuidle_devices = alloc_percpu(struct cpuidle_device);

    ret = cpuhp_setup_state(CPUHP_AP_ONLINE_DYN, "cpuidle/haltpoll:online", haltpoll_cpu_online, haltpoll_cpu_offline);
    haltpoll_hp_state = ret;
}

static int default_enter_idle(struct cpuidle_device *dev, struct cpuidle_driver *drv, int index) {
    if (current_clr_polling_and_test()) {
        local_irq_enable();
        return index;
    }
    default_idle();
    return index;
}

// drivers/acpi/processor_idle.c

// governor/enter() 等等，都需要在后面动态初始化
struct cpuidle_driver acpi_idle_driver = {
    .name =     "acpi_idle",
    .owner =    THIS_MODULE,
};

// prepares and configures cpuidle global state data i.e. idle routines
static int acpi_processor_setup_cpuidle_states(struct acpi_processor *pr) {
    struct cpuidle_driver *drv = &acpi_idle_driver;

    if (pr->flags.has_lpi)
        return acpi_processor_setup_lpi_states(pr);

    return acpi_processor_setup_cstates(pr);
}

static int acpi_processor_setup_lpi_states(struct acpi_processor *pr) {
    struct acpi_lpi_state *lpi;
    struct cpuidle_state *state;
    struct cpuidle_driver *drv = &acpi_idle_driver;

    for (i = 0; i < pr->power.count && i < CPUIDLE_STATE_MAX; i++) {
        lpi = &pr->power.lpi_states[i];

        state = &drv->states[i];
        snprintf(state->name, CPUIDLE_NAME_LEN, "LPI-%d", i);
        strlcpy(state->desc, lpi->desc, CPUIDLE_DESC_LEN);
        state->exit_latency = lpi->wake_latency;
        state->target_residency = lpi->min_residency;
        if (lpi->arch_flags)
            state->flags |= CPUIDLE_FLAG_TIMER_STOP;
        state->enter = acpi_idle_lpi_enter;
        drv->safe_state_index = i;
    }

    drv->state_count = i;
    return 0;
}

static int acpi_processor_setup_cstates(struct acpi_processor *pr) {
    struct acpi_processor_cx *cx;
    struct cpuidle_state *state;
    struct cpuidle_driver *drv = &acpi_idle_driver;

    if (max_cstate == 0)
        max_cstate = 1;

    if (IS_ENABLED(CONFIG_ARCH_HAS_CPU_RELAX)) {
        cpuidle_poll_state_init(drv);
        count = 1;
    } else {
        count = 0;
    }

    for (i = 1; i < ACPI_PROCESSOR_MAX_POWER && i <= max_cstate; i++) {
        cx = &pr->power.states[i];

        if (!cx->valid)
            continue;

        state = &drv->states[count];
        snprintf(state->name, CPUIDLE_NAME_LEN, "C%d", i);
        strlcpy(state->desc, cx->desc, CPUIDLE_DESC_LEN);
        state->exit_latency = cx->latency;
        state->target_residency = cx->latency * latency_factor;
        state->enter = acpi_idle_enter;

        state->flags = 0;
        if (cx->type == ACPI_STATE_C1 || cx->type == ACPI_STATE_C2) {
            drv->safe_state_index = count;
        }

        count++;
        if (count == CPUIDLE_STATE_MAX)
            break;
    }

    drv->state_count = count;

    if (!count)
        return -EINVAL;

    return 0;
}

static int acpi_idle_enter(struct cpuidle_device *dev, struct cpuidle_driver *drv, int index) {
    struct acpi_processor_cx *cx = per_cpu(acpi_cstate[index], dev->cpu);
    struct acpi_processor *pr;

    pr = __this_cpu_read(processors);
    if (unlikely(!pr))
        return -EINVAL;

    if (cx->type != ACPI_STATE_C1) {
        if (cx->type == ACPI_STATE_C3 && pr->flags.bm_check)
            return acpi_idle_enter_bm(drv, pr, cx, index);

        /* C2 to C1 demotion. */
        if (acpi_idle_fallback_to_c1(pr) && num_online_cpus() > 1) {
            index = ACPI_IDLE_STATE_START;
            cx = per_cpu(acpi_cstate[index], dev->cpu);
        }
    }

    if (cx->type == ACPI_STATE_C3)
        ACPI_FLUSH_CPU_CACHE();

    acpi_idle_do_entry(cx);

    return index;
}

// acpi_idle_do_entry - enter idle state using the appropriate method
// @cx: cstate data
//
// Caller disables interrupt before call and enables interrupt after return.
static void __cpuidle acpi_idle_do_entry(struct acpi_processor_cx *cx) {
    if (cx->entry_method == ACPI_CSTATE_FFH) {
        /* Call into architectural FFH based C-state */
        acpi_processor_ffh_cstate_enter(cx);
    } else if (cx->entry_method == ACPI_CSTATE_HALT) {
        acpi_safe_halt();
    } else {
        /* IO port based C-state */
        inb(cx->address);
        wait_for_freeze();
    }
}

// Callers should disable interrupts before the call and enable interrupts after return.
static void __cpuidle acpi_safe_halt(void) {
    if (!tif_need_resched()) {
        safe_halt();
        local_irq_disable();
    }
}

#define safe_halt()                \
    do {                    \
        trace_hardirqs_on();        \
        raw_safe_halt();        \
    } while (0)

/**
 * acpi_idle_lpi_enter - enters an ACPI any LPI state
 * @dev: the target CPU
 * @drv: cpuidle driver containing cpuidle state info
 * @index: index of target state
 *
 * Return: 0 for success or negative value for error
 */
static int acpi_idle_lpi_enter(struct cpuidle_device *dev, struct cpuidle_driver *drv, int index) {
    struct acpi_processor *pr;
    struct acpi_lpi_state *lpi;

    pr = __this_cpu_read(processors);

    lpi = &pr->power.lpi_states[index];
    if (lpi->entry_method == ACPI_CSTATE_FFH)
        return acpi_processor_ffh_lpi_enter(lpi);

    return -EINVAL;
}

// States are indexed by the cstate number, which is also the index into the MWAIT hint array.
// Thus C0 is a dummy.
static struct cpuidle_state nehalem_cstates[] __initdata = {
    {
        .name = "C1",
        .desc = "MWAIT 0x00",
        .flags = MWAIT2flg(0x00),
        .exit_latency = 3,
        .target_residency = 6,
        .enter = &intel_idle,
        .enter_s2idle = intel_idle_s2idle, },
    {
        .name = "C1E",
        .desc = "MWAIT 0x01",
        .flags = MWAIT2flg(0x01) | CPUIDLE_FLAG_ALWAYS_ENABLE,
        .exit_latency = 10,
        .target_residency = 20,
        .enter = &intel_idle,
        .enter_s2idle = intel_idle_s2idle, },
    {
        .name = "C3",
        .desc = "MWAIT 0x10",
        .flags = MWAIT2flg(0x10) | CPUIDLE_FLAG_TLB_FLUSHED,
        .exit_latency = 20,
        .target_residency = 80,
        .enter = &intel_idle,
        .enter_s2idle = intel_idle_s2idle, },
    {
        .name = "C6",
        .desc = "MWAIT 0x20",
        .flags = MWAIT2flg(0x20) | CPUIDLE_FLAG_TLB_FLUSHED,
        .exit_latency = 200,
        .target_residency = 800,
        .enter = &intel_idle,
        .enter_s2idle = intel_idle_s2idle, },
    {
        .enter = NULL }
};

/**
 * intel_idle - Ask the processor to enter the given idle state.
 * @dev: cpuidle device of the target CPU.
 * @drv: cpuidle driver (assumed to point to intel_idle_driver).
 * @index: Target idle state index.
 *
 * Use the MWAIT instruction to notify the processor that the CPU represented by
 * @dev is idle and it can try to enter the idle state corresponding to @index.
 *
 * If the local APIC timer is not known to be reliable in the target idle state,
 * enable one-shot tick broadcasting for the target CPU before executing MWAIT.
 *
 * Optionally call leave_mm() for the target CPU upfront to avoid wakeups due to flushing user TLBs.
 */
static __cpuidle int intel_idle(struct cpuidle_device *dev, struct cpuidle_driver *drv, int index) {
    struct cpuidle_state *state = &drv->states[index];
    unsigned long eax = flg2MWAIT(state->flags);
    unsigned long ecx = 1; /* break on interrupt flag */

    mwait_idle_with_hints(eax, ecx);
    return index;
}

/*
 * MWAIT takes an 8-bit "hint" in EAX "suggesting"
 * the C-state (top nibble) and sub-state (bottom nibble)
 * 0x00 means "MWAIT(C1)", 0x10 means "MWAIT(C2)" etc.
 *
 * We store the hint at the top of our "flags" for each state.
 */
#define flg2MWAIT(flags) (((flags) >> 24) & 0xFF)

/*
 * This uses new MONITOR/MWAIT instructions on P4 processors with PNI,
 * which can obviate IPI to trigger checking of need_resched.
 * We execute MONITOR against need_resched and enter optimized wait state
 * through MWAIT. Whenever someone changes need_resched, we would be woken
 * up from MWAIT (without an IPI).
 *
 * New with Core Duo processors, MWAIT can take some hints based on CPU capability.
 */
static inline void mwait_idle_with_hints(unsigned long eax, unsigned long ecx) {
    if (static_cpu_has_bug(X86_BUG_MONITOR) || !current_set_polling_and_test()) {
        if (static_cpu_has_bug(X86_BUG_CLFLUSH_MONITOR)) {
            mb();
            clflush((void *)&current_thread_info()->flags);
            mb();
        }

        __monitor((void *)&current_thread_info()->flags, 0, 0);
        if (!need_resched())
            __mwait(eax, ecx);
    }
    current_clr_polling();
}

//  https://github.com/torvalds/linux/blob/v5.15/kernel/sched/idle.c#L261

// Generic idle loop implementation. Called with polling cleared.
static void do_idle(void) {
    int cpu = smp_processor_id();
    nohz_run_idle_balance(cpu); // Check if we need to update blocked load

    // If the arch has a polling bit, we maintain an invariant:
    //
    // Our polling bit is clear if we're not scheduled (i.e. if rq->curr != rq->idle). This means that, 
    // if rq->idle has the polling bit set, then setting need_resched is guaranteed to cause the CPU to reschedule.
    __current_set_polling();
 +- tick_nohz_idle_enter();
 |
 |  while (!need_resched()) {
 |      local_irq_disable();
 |   +- arch_cpu_idle_enter();
 |   |
 |   |  // In poll mode we reenable interrupts and spin. Also if we detected in the wakeup from idle path that the tick
 |   |  // broadcast device expired for us, we don't want to go deep idle as we know that the IPI is going to arrive right away.
 |   |  if (cpu_idle_force_poll || tick_check_broadcast_expired()) {
 |   |      tick_nohz_idle_restart_tick();
 |   |      cpu_idle_poll();
 |   |  } else {
 |   |      cpuidle_idle_call(); // --> CALLING INTO cpuidle subsystem, governor+driver
 |   |  }
 |   +- arch_cpu_idle_exit();
 |  }
 |
 |  // Since we fell out of the loop above, we know TIF_NEED_RESCHED must be set, propagate it into PREEMPT_NEED_RESCHED.
 |  // This is required because for polling idle loops we will not have had an IPI to fold the state for us.
 |  preempt_set_need_resched();
 +- tick_nohz_idle_exit();
    __current_clr_polling();

    schedule_idle();
}

/**
 * cpuidle_idle_call - the main idle function
 *
 * On architectures that support TIF_POLLING_NRFLAG, is called with polling
 * set, and it returns with polling set.  If it ever stops polling, it must clear the polling bit.
 */
static void cpuidle_idle_call(void) {
    struct cpuidle_device *dev = cpuidle_get_device();
    struct cpuidle_driver *drv = cpuidle_get_cpu_driver(dev);

    if (idle_should_enter_s2idle() || dev->forced_idle_latency_limit_ns) {
        ...
    } else {
        // Ask the cpuidle framework to choose a convenient idle state.
        bool stop_tick = true;
        next_state = cpuidle_select(drv, dev, &stop_tick);

        if (stop_tick || tick_nohz_tick_stopped())
            tick_nohz_idle_stop_tick();
        else
            tick_nohz_idle_retain_tick();

        entered_state = call_cpuidle(drv, dev, next_state);
        cpuidle_reflect(dev, entered_state); // Give the governor an opportunity to reflect on the outcome
    }

exit_idle:
    __current_set_polling();
}

static int call_cpuidle(struct cpuidle_driver *drv, struct cpuidle_device *dev, int next_state) {
    // This function will block until an interrupt occurs and will take care of re-enabling the local interrupts
    return cpuidle_enter(drv, dev, next_state);
}

// drivers/cpuidle/cpuidle.c

/**
 * cpuidle_enter - enter into the specified idle state
 *
 * @drv:   the cpuidle driver tied with the cpu
 * @dev:   the cpuidle device
 * @index: the index in the idle state table
 *
 * Returns the index in the idle state, < 0 in case of error.
 * The error code depends on the backend driver
 */
int cpuidle_enter(struct cpuidle_driver *drv, struct cpuidle_device *dev, int index) {
    /*
     * Store the next hrtimer, which becomes either next tick or the next
     * timer event, whatever expires first. Additionally, to make this data
     * useful for consumers outside cpuidle, we rely on that the governor's
     * ->select() callback have decided, whether to stop the tick or not.
     */
    WRITE_ONCE(dev->next_hrtimer, tick_nohz_get_next_hrtimer());

    if (cpuidle_state_is_coupled(drv, index))
        ret = cpuidle_enter_state_coupled(dev, drv, index);
    else
        ret = cpuidle_enter_state(dev, drv, index);

    WRITE_ONCE(dev->next_hrtimer, 0);
    return ret;
}

// drivers/cpuidle/cpuidle.c

/**
 * cpuidle_enter_state - enter the state and update stats
 * @dev: cpuidle device for this cpu
 * @drv: cpuidle driver for this cpu
 * @index: index into the states table in @drv of the state to enter
 */
int cpuidle_enter_state(struct cpuidle_device *dev, struct cpuidle_driver *drv, int index) {
    struct cpuidle_state *target_state = &drv->states[index];
    bool broadcast = !!(target_state->flags & CPUIDLE_FLAG_TIMER_STOP);

    /*
     * Tell the time framework to switch to a broadcast timer because our
     * local timer will be shut down.  If a local timer is used from another
     * CPU as a broadcast timer, this call may fail if it is not available.
     */
    if (broadcast && tick_broadcast_enter()) {
        index = find_deepest_state(drv, dev, target_state->exit_latency_ns, CPUIDLE_FLAG_TIMER_STOP, false);
        if (index < 0) {
            default_idle_call();
            return -EBUSY;
        }
        target_state = &drv->states[index];
        broadcast = false;
    }

    if (target_state->flags & CPUIDLE_FLAG_TLB_FLUSHED)
        leave_mm(dev->cpu);

    sched_idle_set_state(target_state); /* Take note of the planned idle state. */

    time_start = ns_to_ktime(local_clock());
    int entered_state = target_state->enter(dev, drv, index);
    sched_clock_idle_wakeup_event();
    time_end = ns_to_ktime(local_clock());

    sched_idle_set_state(NULL); /* The cpu is no longer idle or about to enter idle. */

    if (broadcast) {
        if (WARN_ON_ONCE(!irqs_disabled()))
            local_irq_disable();

        tick_broadcast_exit();
    }

    if (!cpuidle_state_is_coupled(drv, index))
        local_irq_enable();

    if (entered_state >= 0) {
        s64 diff, delay = drv->states[entered_state].exit_latency_ns;

        // Update cpuidle counters
        diff = ktime_sub(time_end, time_start);
        dev->last_residency_ns = diff;
        dev->states_usage[entered_state].time_ns += diff;
        dev->states_usage[entered_state].usage++;

        if (diff < drv->states[entered_state].target_residency_ns) {
            for (i = entered_state - 1; i >= 0; i--) {
                if (dev->states_usage[i].disable)
                    continue;

                dev->states_usage[entered_state].above++; /* Shallower states are enabled, so update. */
                break;
            }
        } else if (diff > delay) {
            for (i = entered_state + 1; i < drv->state_count; i++) {
                if (dev->states_usage[i].disable)
                    continue;

                // Update if a deeper state would have been a better match for the observed idle duration.
                if (diff - delay >= drv->states[i].target_residency_ns)
                    dev->states_usage[entered_state].below++;

                break;
            }
        }
    } else {
        dev->last_residency_ns = 0;
        dev->states_usage[index].rejected++;
    }

    return entered_state;
}

// https://github.com/torvalds/linux/blob/v5.15/arch/x86/include/asm/irqflags.h#L54

static inline __cpuidle void native_halt(void) {
    mds_idle_clear_cpu_buffers();
    asm volatile("hlt": : :"memory");
}