Add aligned page-table metadata, NUMA-aware allocation hooks, copy-on-write accounting, lazy mappings and priority-aware scheduler structures for x86_64, AArch64 and RISC-V contracts.
Signed-off-by: Breno Rodrigues Alves <[email protected]> --- modern/include/mach/c17/sched.h | 191 +++++ modern/include/mach/c17/vm.h | 276 ++++++++ modern/src/sched/sched.c | 682 ++++++++++++++++++ modern/src/vm/vm.c | 1155 +++++++++++++++++++++++++++++++ modern/tests/test_sched.c | 158 +++++ modern/tests/test_vm.c | 310 +++++++++ 6 files changed, 2772 insertions(+) create mode 100644 modern/include/mach/c17/sched.h create mode 100644 modern/include/mach/c17/vm.h create mode 100644 modern/src/sched/sched.c create mode 100644 modern/src/vm/vm.c create mode 100644 modern/tests/test_sched.c create mode 100644 modern/tests/test_vm.c diff --git a/modern/include/mach/c17/sched.h b/modern/include/mach/c17/sched.h new file mode 100644 index 00000000..81b9446d --- /dev/null +++ b/modern/include/mach/c17/sched.h @@ -0,0 +1,191 @@ +/* Hybrid, priority-aware scheduler for the C17 Mach kernel. + Copyright (C) 2026 Free Software Foundation, Inc. + + This file is part of GNU Mach. See base.h for the license. */ + +#ifndef _MACH_C17_SCHED_H +#define _MACH_C17_SCHED_H 1 + +#include <mach/c17/base.h> +#include <mach/c17/atomic.h> + +#define MACH_SCHED_PRIORITIES 256 +#define MACH_SCHED_CLASSES 4 +#define MACH_SCHED_DONATIONS 8 +#define MACH_SCHED_TSS_KEYS 16 + +/* Priorities grow with importance, unlike the historical Mach scale. + The bands are fixed so that policies can reason about them without + consulting a table at run time. */ +#define MACH_PRIO_IDLE 0 +#define MACH_PRIO_BACKGROUND 32 +#define MACH_PRIO_TIMESHARE 96 +#define MACH_PRIO_REALTIME 160 +#define MACH_PRIO_MAX 255 + +#define MACH_THREAD_NEED_RESCHED 0x1u + +typedef enum mach_thread_state +{ + MACH_THREAD_FREE = 0, + MACH_THREAD_READY, + MACH_THREAD_RUNNING, + MACH_THREAD_BLOCKED, + MACH_THREAD_SLEEPING, + MACH_THREAD_ZOMBIE +} mach_thread_state_t; + +typedef enum mach_sched_class +{ + MACH_SCHED_IDLE = 0, + MACH_SCHED_BACKGROUND, + MACH_SCHED_TIMESHARE, + MACH_SCHED_REALTIME +} mach_sched_class_t; + +/* Heterogeneous CPUs advertise what they are good at. A performance + core has a larger capacity value; the scheduler uses the capacity to + normalise load and to decide where a wakeup should land. */ +typedef enum mach_cpu_kind +{ + MACH_CPU_EFFICIENCY = 0, + MACH_CPU_PERFORMANCE +} mach_cpu_kind_t; + +struct mach_cpu; +struct mach_thread_internal; + +typedef void (*mach_thread_entry_t) (void *argument); + +/* A donation is one waiter lending its priority to a lock owner. The + small table makes priority inheritance exact when several waiters + share an owner: removing one donation recomputes the maximum from the + remaining entries instead of guessing. */ +struct mach_donation +{ + mach_priority_t priority; + uint32_t count; +}; + +struct mach_thread +{ + mach_thread_id_t id; + mach_thread_state_t state; + mach_sched_class_t sched_class; + mach_priority_t base_priority; + mach_priority_t priority; /* Effective priority. */ + struct mach_cpu *cpu; + struct mach_list run_link; /* Run queue linkage. */ + struct mach_list all_link; /* Global thread registry. */ + uint64_t vruntime; /* Fair-share clock, ns. */ + uint32_t time_slice; /* Remaining slice, ns. */ + mach_flags_t flags; + bool pi_boosted; + bool queued; /* On a run queue. */ + mach_priority_t queued_priority; /* Priority used when queued. */ + + struct mach_donation donations[MACH_SCHED_DONATIONS]; + uint32_t donation_count; + + mach_thread_entry_t entry; + void *argument; + void *stack_base; + size_t stack_size; + void *tss[MACH_SCHED_TSS_KEYS]; + + int exit_status; + bool detached; + struct mach_thread *joiner; + struct mach_list join_link; +}; + +struct mach_cpu +{ + mach_cpu_id_t id; + mach_cpu_kind_t kind; + uint32_t capacity; /* 1024 is the baseline core. */ + mach_atomic_u32 online; + mach_atomic_u32 nr_running; + struct mach_spinlock lock; + uint64_t bitmap[MACH_SCHED_PRIORITIES / 64u]; + struct mach_list runq[MACH_SCHED_PRIORITIES]; + struct mach_thread *current; + uint64_t clock; /* Monotonic, ns. */ + uint64_t idle_time; /* Total idle ns. */ +} MACH_CACHELINE_ALIGN; + +/* The scheduler keeps a small fixed table: the kernel boots with a + bounded number of CPUs and threads that are ready at any instant. + Allocation happens in the thread layer, never in the dispatch path. */ +#define MACH_SCHED_MAX_CPUS 256 +#define MACH_SCHED_MAX_THREADS 8192 + +struct mach_sched_ops +{ + /* Called when the current thread must give up the CPU. In the real + kernel this is the assembly context switch; the test harness + supplies a cooperative implementation. */ + void (*switch_cpu) (struct mach_thread *from, struct mach_thread *to); + /* Monotonic clock in nanoseconds. */ + mach_time_t (*now) (void); +}; + +struct mach_sched +{ + struct mach_spinlock lock; + struct mach_list runnable; + struct mach_list all_threads; + struct mach_thread *threads; + uint32_t nr_threads; + uint32_t nr_cpus; + struct mach_cpu cpus[MACH_SCHED_MAX_CPUS]; + struct mach_sched_ops ops; + struct mach_thread *current; + mach_atomic_u64 context_switches; + mach_atomic_u64 migrations; +}; + +void mach_sched_init (const struct mach_sched_ops *ops); +mach_error_t mach_sched_register_cpu (mach_cpu_id_t id, mach_cpu_kind_t kind, + uint32_t capacity); +mach_error_t mach_sched_start_cpu (mach_cpu_id_t id); + +/* Thread lifecycle. Memory for a thread comes from the caller so that + allocation policy stays with the task layer. */ +mach_error_t mach_sched_thread_init (struct mach_thread *thread, + mach_priority_t priority, + mach_sched_class_t sched_class, + mach_thread_entry_t entry, + void *argument); +void mach_sched_thread_destroy (struct mach_thread *thread); +void mach_sched_make_ready (struct mach_thread *thread); +void mach_sched_block (struct mach_thread *thread); +void mach_sched_wake (struct mach_thread *thread); +void mach_sched_yield (void); +void mach_sched_tick (struct mach_cpu *cpu, uint64_t elapsed); + +/* Dispatch. Returns the highest-priority runnable thread, preferring + the local CPU and then a CPU that shares the thread's class. */ +struct mach_thread *mach_sched_pick_next (struct mach_cpu *cpu); +void mach_sched_account_switch (struct mach_cpu *cpu, + struct mach_thread *previous, + struct mach_thread *next); + +/* Priority inheritance. A waiter donates its effective priority to the + lock owner; the donation is removed when the owner releases. */ +void mach_sched_donate (struct mach_thread *owner, mach_priority_t priority); +void mach_sched_undonate (struct mach_thread *owner, mach_priority_t priority); +void mach_sched_set_priority (struct mach_thread *thread, + mach_priority_t priority); + +/* Heterogeneous placement and load balancing. */ +struct mach_cpu *mach_sched_select_cpu (const struct mach_thread *thread); +void mach_sched_balance (struct mach_cpu *cpu); +struct mach_cpu *mach_sched_cpu_by_id (mach_cpu_id_t id); +struct mach_cpu *mach_sched_cpu_at (uint32_t index); +uint32_t mach_sched_cpu_count (void); +mach_time_t mach_sched_now_ns (void); +struct mach_thread *mach_sched_current_thread (void); +uint32_t mach_sched_runnable_count (void); + +#endif /* _MACH_C17_SCHED_H */ diff --git a/modern/include/mach/c17/vm.h b/modern/include/mach/c17/vm.h new file mode 100644 index 00000000..07c45fe6 --- /dev/null +++ b/modern/include/mach/c17/vm.h @@ -0,0 +1,276 @@ +/* Virtual memory: radix page tables, NUMA allocator, COW and paging. + Copyright (C) 2026 Free Software Foundation, Inc. + + This file is part of GNU Mach. See base.h for the license. */ + +#ifndef _MACH_C17_VM_H +#define _MACH_C17_VM_H 1 + +#include <mach/c17/base.h> +#include <mach/c17/atomic.h> + +#define MACH_VM_MAX_LEVELS 5 +#define MACH_VM_PT_ENTRIES 512u +#define MACH_VM_PT_INDEX_BITS 9u +#define MACH_VM_PT_INDEX_MASK (MACH_VM_PT_ENTRIES - 1u) + +#define MACH_VM_MAX_ORDER 11u /* 2^11 pages = 8 MiB. */ +#define MACH_VM_MAX_NODES 8u +#define MACH_PHYS_NULL ((mach_phys_t) ~0ull) + +#define MACH_VM_PROT_READ 0x1u +#define MACH_VM_PROT_WRITE 0x2u +#define MACH_VM_PROT_EXEC 0x4u +#define MACH_VM_PROT_USER 0x8u + +#define MACH_VM_PAGE_RESIDENT 0x1u +#define MACH_VM_PAGE_SHARED 0x2u +#define MACH_VM_PAGE_DIRTY 0x4u +#define MACH_VM_PAGE_HUGE 0x8u + +/* --------------------------------------------------------------------- + Page table formats. + + The walker below is shared by x86_64 and AArch64. Both architectures + use nine-bit indices starting at bit twelve; what differs is the bit + that marks a translation as valid and the encoding of permissions. + Keeping the encoding in a descriptor means a single, auditable walk + routine serves four- and five-level configurations on either ISA. */ + +typedef enum mach_pmap_arch +{ + MACH_PMAP_X86_64 = 0, + MACH_PMAP_AARCH64 +} mach_pmap_arch_t; + +struct mach_pmap_format +{ + mach_pmap_arch_t arch; + unsigned int levels; /* 4 or 5. */ + uint64_t phys_mask; + uint64_t present; + uint64_t writable; + uint64_t user; + uint64_t no_exec; + uint64_t huge; + uint64_t table_flags; /* AF/SH for AArch64. */ +}; + +struct mach_pmap_ops +{ + /* Map a page-table page into the kernel's direct map. */ + void *(*phys_to_virt) (void *context, mach_phys_t address); + mach_phys_t (*alloc_table) (void *context); + void (*free_table) (void *context, mach_phys_t address); + void (*flush_tlb) (void *context, mach_vaddr_t address, size_t length); + /* Copy one page between physical addresses, used by COW. */ + void (*copy_page) (void *context, mach_phys_t destination, + mach_phys_t source); + /* Fill a page with zeroes for demand paging. */ + void (*zero_page) (void *context, mach_phys_t address); +}; + +struct mach_pmap +{ + mach_phys_t root; + struct mach_pmap_format format; + struct mach_pmap_ops ops; + void *context; + mach_vaddr_t user_min; + mach_vaddr_t user_max; + mach_spinlock_t lock; + mach_atomic_u64 mapped_pages; +}; + +/* Build the format descriptor for an ISA and a level count. */ +void mach_pmap_format_init (struct mach_pmap_format *format, + mach_pmap_arch_t arch, unsigned int levels); + +mach_error_t mach_pmap_init (struct mach_pmap *pmap, + const struct mach_pmap_format *format, + const struct mach_pmap_ops *ops, void *context); + +/* Map LENGTH bytes of physical memory at VIRTUAL. The range must be + page aligned. A large mapping is installed with huge pages whenever + alignment and the architecture allow it. */ +mach_error_t mach_pmap_map (struct mach_pmap *pmap, mach_vaddr_t virtual_address, + mach_phys_t physical_address, size_t length, + uint32_t protection); +mach_error_t mach_pmap_unmap (struct mach_pmap *pmap, + mach_vaddr_t virtual_address, size_t length); +mach_error_t mach_pmap_protect (struct mach_pmap *pmap, + mach_vaddr_t virtual_address, size_t length, + uint32_t protection); +/* Translate one page. Returns MACH_ENOENT for an unmapped address. */ +mach_error_t mach_pmap_translate (struct mach_pmap *pmap, + mach_vaddr_t virtual_address, + mach_phys_t *physical_address, + uint32_t *protection); + +/* Walk to the PTE that covers ADDRESS. When ALLOCATE is true missing + intermediate tables are allocated. On success *ENTRY points at the + descriptor and *LEVEL receives its level (0 is the leaf level). */ +mach_error_t mach_pmap_walk (struct mach_pmap *pmap, mach_vaddr_t address, + bool allocate, uint64_t **entry, + unsigned int *level); + +/* --------------------------------------------------------------------- + NUMA-aware physical page allocator. + + One buddy allocator per node. Allocation tries the preferred node, + then nodes in increasing distance order; this keeps locality on the + fast path while degrading gracefully when a node is full. */ + +struct mach_numa_region +{ + uint32_t node; + mach_phys_t base; /* Page aligned. */ + uint64_t nr_pages; +}; + +struct mach_vm_page +{ + uint8_t order; /* Order when free. */ + bool free; + struct mach_list link; +}; + +struct mach_numa_node +{ + uint32_t id; + mach_phys_t base; + uint64_t nr_pages; + struct mach_vm_page *pages; + struct mach_list free_area[MACH_VM_MAX_ORDER + 1u]; + mach_atomic_u64 free_pages; + struct mach_spinlock lock; +}; + +struct mach_vm_phys +{ + struct mach_numa_node nodes[MACH_VM_MAX_NODES]; + uint32_t nr_nodes; + uint8_t distance[MACH_VM_MAX_NODES][MACH_VM_MAX_NODES]; + struct mach_pmap_ops ops; + void *context; + mach_atomic_u64 total_pages; + mach_atomic_u64 allocated_pages; +}; + +mach_error_t mach_vm_phys_init (struct mach_vm_phys *physical, + const struct mach_numa_region *regions, + uint32_t nr_regions, + struct mach_vm_page *page_storage, + uint64_t nr_page_storage, + const uint8_t *distances, + const struct mach_pmap_ops *ops, + void *context); +mach_phys_t mach_vm_alloc_pages (struct mach_vm_phys *physical, + uint32_t nr_pages, int preferred_node); +mach_error_t mach_vm_free_pages (struct mach_vm_phys *physical, + mach_phys_t address, uint32_t nr_pages); +uint64_t mach_vm_free_page_count (const struct mach_vm_phys *physical); +uint64_t mach_vm_free_page_count_node (const struct mach_vm_phys *physical, + uint32_t node); + +/* --------------------------------------------------------------------- + Objects, copy-on-write and demand paging. + + A slot is the unit of sharing: two address spaces that fork receive + the same slot with an incremented reference count. A write fault on + a slot with more than one reference copies the page, which is the + whole COW protocol. */ + +struct mach_vm_pager; + +struct mach_vm_pager_ops +{ + /* Fetch the page at OFFSET. The pager returns a physical page with + one reference for the faulting map. */ + mach_error_t (*get_page) (struct mach_vm_pager *pager, uint64_t offset, + mach_phys_t *address); + /* Optional write-back hook for dirty pages. */ + mach_error_t (*put_page) (struct mach_vm_pager *pager, uint64_t offset, + mach_phys_t address, bool dirty); +}; + +struct mach_vm_pager +{ + const struct mach_vm_pager_ops *ops; + void *data; +}; + +struct mach_vm_slot +{ + /* A resident page is shared between every address space that mapped + it before a fork. Keeping the reference count on the resident, + rather than on the slot, is what makes COW correct: each map owns + its own slot, so replacing one slot cannot disturb the other. */ + struct mach_vm_resident *resident; +}; + +struct mach_vm_resident +{ + mach_refcount_t refs; + mach_phys_t address; + uint32_t flags; + uint32_t reserved; +}; + +struct mach_vm_object +{ + struct mach_vm_slot *slots; + struct mach_vm_resident *residents; + uint64_t nr_slots; + uint64_t nr_residents; + struct mach_vm_pager *pager; + mach_refcount_t refs; + struct mach_spinlock lock; + uint64_t object_size; + mach_atomic_u64 resident_cursor; +}; + +#define MACH_VM_RESIDENT_FREE 0u +#define MACH_VM_RESIDENT_USED 1u + +struct mach_vm_map +{ + struct mach_pmap pmap; + struct mach_vm_object *object; + struct mach_vm_phys *physical; + mach_vaddr_t base; /* First address of slot 0. */ + mach_vaddr_t next_hint; + uint32_t protection; +}; + +mach_error_t mach_vm_object_init (struct mach_vm_object *object, + struct mach_vm_slot *slots, uint64_t nr_slots, + struct mach_vm_resident *residents, + uint64_t nr_residents, + struct mach_vm_pager *pager, + uint64_t object_size); +mach_error_t mach_vm_map_init (struct mach_vm_map *map, + struct mach_vm_object *object, + struct mach_vm_phys *physical, + const struct mach_pmap_format *format, + const struct mach_pmap_ops *ops, + void *context, uint32_t protection); + +/* Fault handler for demand paging and COW. On success the mapping is + installed in the page table and *ADDRESS receives the physical page. */ +mach_error_t mach_vm_map_fault (struct mach_vm_map *map, + mach_vaddr_t virtual_address, bool write, + mach_phys_t *address); + +/* Share every resident with a child object (fork). The child must own + its own slot and resident arrays. */ +mach_error_t mach_vm_object_fork (struct mach_vm_object *parent, + struct mach_vm_object *child, + struct mach_vm_slot *child_slots, + struct mach_vm_resident *child_residents, + uint64_t nr_slots); + +/* Drop one reference from a slot, freeing the page when it was last. */ +void mach_vm_slot_release (struct mach_vm_map *map, struct mach_vm_slot *slot); + +#endif /* _MACH_C17_VM_H */ diff --git a/modern/src/sched/sched.c b/modern/src/sched/sched.c new file mode 100644 index 00000000..c9778661 --- /dev/null +++ b/modern/src/sched/sched.c @@ -0,0 +1,682 @@ +/* Hybrid priority scheduler implementation. + Copyright (C) 2026 Free Software Foundation, Inc. + + This file is part of GNU Mach. See base.h for the license. + + The design follows three rules: + + - the highest effective priority always runs, and real-time threads + never share a CPU with a lower band if a performance core is free; + - wakeups land on a CPU that fits the thread's class and current + load, which is what makes big.LITTLE useful rather than merely + present; + - priority inheritance is exact: a donation is a counted entry, so + removing one donor cannot accidentally discard another donor's + boost. */ + +#include <mach/c17/sched.h> + +static struct mach_sched mach_scheduler; +static mach_atomic_u32 mach_next_thread_id = 1u; + +#define MACH_TIMESLICE_NS 4000000u + +static mach_time_t +sched_now (void) +{ + if (mach_scheduler.ops.now != NULL) + return mach_scheduler.ops.now (); + + return 0; +} + +static uint32_t +sched_cpu_load (const struct mach_cpu *cpu) +{ + uint32_t running = atomic_load_explicit (&cpu->nr_running, + memory_order_relaxed); + + if (cpu->capacity == 0) + return running * 1024u; + + return (running * 1024u) / cpu->capacity; +} + +static bool +sched_class_prefers_efficiency (mach_sched_class_t sched_class) +{ + return sched_class == MACH_SCHED_IDLE + || sched_class == MACH_SCHED_BACKGROUND; +} + +void +mach_sched_init (const struct mach_sched_ops *ops) +{ + uint32_t index; + + mach_memset (&mach_scheduler, 0, sizeof (mach_scheduler)); + mach_spinlock_init (&mach_scheduler.lock); + mach_list_init (&mach_scheduler.runnable); + mach_list_init (&mach_scheduler.all_threads); + mach_scheduler.nr_threads = 0; + mach_scheduler.nr_cpus = 0; + mach_scheduler.current = NULL; + atomic_init (&mach_scheduler.context_switches, 0u); + atomic_init (&mach_scheduler.migrations, 0u); + + for (index = 0; index < MACH_SCHED_MAX_CPUS; index++) + mach_scheduler.cpus[index].id = MACH_CPU_NULL; + + if (ops != NULL) + mach_scheduler.ops = *ops; + + atomic_store_explicit (&mach_next_thread_id, 1u, memory_order_relaxed); +} + +mach_error_t +mach_sched_register_cpu (mach_cpu_id_t id, mach_cpu_kind_t kind, + uint32_t capacity) +{ + struct mach_cpu *cpu; + uint32_t index; + + if (capacity == 0) + return MACH_EINVAL; + + if (mach_scheduler.nr_cpus >= MACH_SCHED_MAX_CPUS) + return MACH_ENOMEM; + + for (index = 0; index < mach_scheduler.nr_cpus; index++) + if (mach_scheduler.cpus[index].id == id) + return MACH_EBUSY; + + cpu = &mach_scheduler.cpus[mach_scheduler.nr_cpus]; + mach_memset (cpu, 0, sizeof (*cpu)); + cpu->id = id; + cpu->kind = kind; + cpu->capacity = capacity; + cpu->current = NULL; + cpu->clock = 0; + cpu->idle_time = 0; + mach_spinlock_init (&cpu->lock); + atomic_init (&cpu->online, 1u); + atomic_init (&cpu->nr_running, 0u); + + for (index = 0; index < MACH_SCHED_PRIORITIES; index++) + mach_list_init (&cpu->runq[index]); + + mach_scheduler.nr_cpus++; + return MACH_OK; +} + +mach_error_t +mach_sched_start_cpu (mach_cpu_id_t id) +{ + struct mach_cpu *cpu = mach_sched_cpu_by_id (id); + + if (cpu == NULL) + return MACH_ENOENT; + + atomic_store_explicit (&cpu->online, 1u, memory_order_release); + return MACH_OK; +} + +struct mach_cpu * +mach_sched_cpu_by_id (mach_cpu_id_t id) +{ + uint32_t index; + + for (index = 0; index < mach_scheduler.nr_cpus; index++) + if (mach_scheduler.cpus[index].id == id) + return &mach_scheduler.cpus[index]; + + return NULL; +} + +struct mach_cpu * +mach_sched_cpu_at (uint32_t index) +{ + if (index >= mach_scheduler.nr_cpus) + return NULL; + + return &mach_scheduler.cpus[index]; +} + +uint32_t +mach_sched_cpu_count (void) +{ + return mach_scheduler.nr_cpus; +} + +mach_time_t +mach_sched_now_ns (void) +{ + return sched_now (); +} + +mach_error_t +mach_sched_thread_init (struct mach_thread *thread, + mach_priority_t priority, + mach_sched_class_t sched_class, + mach_thread_entry_t entry, void *argument) +{ + if (thread == NULL || entry == NULL) + return MACH_EINVAL; + + if (priority < 0 || priority > MACH_PRIO_MAX) + return MACH_EINVAL; + + mach_memset (thread, 0, sizeof (*thread)); + thread->id = atomic_fetch_add_explicit (&mach_next_thread_id, 1u, + memory_order_relaxed); + thread->state = MACH_THREAD_FREE; + thread->sched_class = sched_class; + thread->base_priority = priority; + thread->priority = priority; + thread->time_slice = MACH_TIMESLICE_NS; + thread->vruntime = sched_now (); + thread->entry = entry; + thread->argument = argument; + thread->queued = false; + thread->pi_boosted = false; + mach_list_init (&thread->run_link); + mach_list_init (&thread->join_link); + + mach_spinlock_lock (&mach_scheduler.lock); + mach_list_add_tail (&mach_scheduler.all_threads, &thread->all_link); + mach_scheduler.nr_threads++; + mach_spinlock_unlock (&mach_scheduler.lock); + + return MACH_OK; +} + +void +mach_sched_thread_destroy (struct mach_thread *thread) +{ + if (thread == NULL) + return; + + if (thread->queued) + { + mach_spinlock_lock (&thread->cpu->lock); + mach_list_remove (&thread->run_link); + mach_bit_clear (&thread->cpu->bitmap[thread->priority / 64u], + thread->priority % 64u); + atomic_fetch_sub_explicit (&thread->cpu->nr_running, 1u, + memory_order_relaxed); + thread->queued = false; + mach_spinlock_unlock (&thread->cpu->lock); + } + + mach_spinlock_lock (&mach_scheduler.lock); + mach_list_remove (&thread->all_link); + if (mach_scheduler.nr_threads > 0) + mach_scheduler.nr_threads--; + mach_spinlock_unlock (&mach_scheduler.lock); + + thread->state = MACH_THREAD_FREE; +} + +static void +sched_enqueue_locked (struct mach_cpu *cpu, struct mach_thread *thread, + mach_priority_t priority) +{ + if (priority < 0 || priority > MACH_PRIO_MAX) + priority = MACH_PRIO_MAX; + + mach_list_add_tail (&cpu->runq[priority], &thread->run_link); + mach_bit_set (&cpu->bitmap[priority / 64u], priority % 64u); + atomic_fetch_add_explicit (&cpu->nr_running, 1u, memory_order_relaxed); + thread->queued = true; + thread->queued_priority = priority; +} + +static void +sched_dequeue_locked (struct mach_cpu *cpu, struct mach_thread *thread) +{ + uint32_t priority; + + if (!thread->queued) + return; + + mach_list_remove (&thread->run_link); + thread->queued = false; + priority = (uint32_t) thread->queued_priority; + if (mach_list_empty (&cpu->runq[priority])) + mach_bit_clear (&cpu->bitmap[priority / 64u], priority % 64u); + atomic_fetch_sub_explicit (&cpu->nr_running, 1u, memory_order_relaxed); +} + +/* Reposition a queued thread after its effective priority changed. */ + +static void +sched_reposition (struct mach_thread *thread) +{ + struct mach_cpu *cpu; + + if (!thread->queued) + return; + + cpu = thread->cpu; + mach_spinlock_lock (&cpu->lock); + sched_dequeue_locked (cpu, thread); + sched_enqueue_locked (cpu, thread, thread->priority); + mach_spinlock_unlock (&cpu->lock); +} + +void +mach_sched_make_ready (struct mach_thread *thread) +{ + struct mach_cpu *selected; + + if (thread == NULL) + return; + + if (thread->state == MACH_THREAD_READY || thread->state == MACH_THREAD_RUNNING) + return; + + selected = mach_sched_select_cpu (thread); + if (selected == NULL) + return; + + thread->state = MACH_THREAD_READY; + thread->cpu = selected; + + mach_spinlock_lock (&selected->lock); + sched_enqueue_locked (selected, thread, thread->priority); + mach_spinlock_unlock (&selected->lock); +} + +void +mach_sched_block (struct mach_thread *thread) +{ + struct mach_cpu *cpu; + + if (thread == NULL) + return; + + if (thread->queued) + { + cpu = thread->cpu; + mach_spinlock_lock (&cpu->lock); + sched_dequeue_locked (cpu, thread); + mach_spinlock_unlock (&cpu->lock); + } + + if (thread->state == MACH_THREAD_RUNNING) + thread->state = MACH_THREAD_BLOCKED; + else if (thread->state != MACH_THREAD_ZOMBIE) + thread->state = MACH_THREAD_BLOCKED; +} + +void +mach_sched_wake (struct mach_thread *thread) +{ + if (thread == NULL || thread->state == MACH_THREAD_ZOMBIE + || thread->state == MACH_THREAD_RUNNING) + return; + + mach_sched_make_ready (thread); +} + +struct mach_thread * +mach_sched_pick_next (struct mach_cpu *cpu) +{ + struct mach_list *list; + struct mach_thread *thread = NULL; + uint32_t word; + uint32_t bit; + uint32_t priority; + + if (cpu == NULL) + return NULL; + + mach_spinlock_lock (&cpu->lock); + + for (word = MACH_SCHED_PRIORITIES / 64u; word-- > 0;) + { + if (cpu->bitmap[word] == 0) + continue; + + bit = 63u - (uint32_t) __builtin_clzll (cpu->bitmap[word]); + priority = word * 64u + bit; + list = &cpu->runq[priority]; + if (mach_list_empty (list)) + { + mach_bit_clear (&cpu->bitmap[word], bit); + continue; + } + + thread = MACH_LIST_ENTRY (list->next, struct mach_thread, run_link); + sched_dequeue_locked (cpu, thread); + break; + } + + mach_spinlock_unlock (&cpu->lock); + return thread; +} + +struct mach_cpu * +mach_sched_select_cpu (const struct mach_thread *thread) +{ + struct mach_cpu *best = NULL; + int32_t best_score = 0; + bool prefer_efficiency; + uint32_t index; + + prefer_efficiency = sched_class_prefers_efficiency (thread->sched_class); + + for (index = 0; index < mach_scheduler.nr_cpus; index++) + { + struct mach_cpu *cpu = &mach_scheduler.cpus[index]; + int32_t score; + + if (atomic_load_explicit (&cpu->online, memory_order_acquire) == 0) + continue; + + score = (int32_t) sched_cpu_load (cpu); + + /* Real-time work wants an idle performance core; background work + prefers an efficiency core and falls back only when none is + available. */ + if (thread->sched_class == MACH_SCHED_REALTIME) + { + if (cpu->kind != MACH_CPU_PERFORMANCE) + score += 4096; + score += (int32_t) atomic_load_explicit (&cpu->nr_running, + memory_order_relaxed) + * 2048; + } + else if (prefer_efficiency) + { + if (cpu->kind != MACH_CPU_EFFICIENCY) + score += 512; + } + else + { + if (cpu->kind != MACH_CPU_PERFORMANCE) + score += 256; + } + + if (cpu->current == NULL) + score -= 64; + + if (best == NULL || score < best_score + || (score == best_score && cpu->kind == MACH_CPU_PERFORMANCE + && best->kind != MACH_CPU_PERFORMANCE)) + { + best = cpu; + best_score = score; + } + } + + return best; +} + +void +mach_sched_account_switch (struct mach_cpu *cpu, struct mach_thread *previous, + struct mach_thread *next) +{ + if (cpu == NULL) + return; + + if (previous != NULL && previous != next) + { + if (previous->state == MACH_THREAD_RUNNING) + previous->state = MACH_THREAD_READY; + } + + if (next != NULL) + { + next->state = MACH_THREAD_RUNNING; + next->cpu = cpu; + } + + cpu->current = next; + mach_scheduler.current = next; + + if (previous != next) + atomic_fetch_add_explicit (&mach_scheduler.context_switches, 1u, + memory_order_relaxed); +} + +void +mach_sched_tick (struct mach_cpu *cpu, uint64_t elapsed) +{ + struct mach_thread *thread; + + if (cpu == NULL) + return; + + cpu->clock += elapsed; + + thread = cpu->current; + if (thread == NULL) + { + cpu->idle_time += elapsed; + return; + } + + if (cpu->capacity != 0) + thread->vruntime += (elapsed * 1024u) / cpu->capacity; + else + thread->vruntime += elapsed; + + if (thread->time_slice > elapsed) + thread->time_slice -= (uint32_t) elapsed; + else + { + thread->time_slice = MACH_TIMESLICE_NS; + thread->flags |= MACH_THREAD_NEED_RESCHED; + } +} + +void +mach_sched_yield (void) +{ + struct mach_cpu *cpu; + struct mach_thread *current; + struct mach_thread *next; + + if (mach_scheduler.nr_cpus == 0) + return; + + cpu = &mach_scheduler.cpus[0]; + current = cpu->current; + + if (mach_scheduler.ops.switch_cpu == NULL) + return; + + next = mach_sched_pick_next (cpu); + if (next == NULL || next == current) + { + if (next != NULL) + { + mach_spinlock_lock (&cpu->lock); + sched_enqueue_locked (cpu, next, next->priority); + mach_spinlock_unlock (&cpu->lock); + } + return; + } + + mach_scheduler.ops.switch_cpu (current, next); + mach_sched_account_switch (cpu, current, next); +} + +void +mach_sched_balance (struct mach_cpu *cpu) +{ + struct mach_cpu *busiest = NULL; + struct mach_thread *thread; + uint32_t busiest_load = 0; + uint32_t index; + + if (cpu == NULL) + return; + + for (index = 0; index < mach_scheduler.nr_cpus; index++) + { + struct mach_cpu *candidate = &mach_scheduler.cpus[index]; + uint32_t load; + + if (candidate == cpu) + continue; + if (atomic_load_explicit (&candidate->online, memory_order_acquire) == 0) + continue; + + load = atomic_load_explicit (&candidate->nr_running, + memory_order_relaxed); + if (load > busiest_load + && (candidate->kind == cpu->kind + || atomic_load_explicit (&cpu->nr_running, + memory_order_relaxed) == 0)) + { + busiest = candidate; + busiest_load = load; + } + } + + if (busiest == NULL || busiest_load < 2) + return; + + thread = mach_sched_pick_next (busiest); + if (thread == NULL) + return; + + mach_spinlock_lock (&cpu->lock); + sched_enqueue_locked (cpu, thread, thread->priority); + mach_spinlock_unlock (&cpu->lock); + + atomic_fetch_add_explicit (&mach_scheduler.migrations, 1u, + memory_order_relaxed); +} + +void +mach_sched_set_priority (struct mach_thread *thread, mach_priority_t priority) +{ + if (thread == NULL) + return; + + if (priority < 0) + priority = 0; + if (priority > MACH_PRIO_MAX) + priority = MACH_PRIO_MAX; + + mach_spinlock_lock (&mach_scheduler.lock); + thread->base_priority = priority; + if (!thread->pi_boosted) + thread->priority = priority; + mach_spinlock_unlock (&mach_scheduler.lock); + + sched_reposition (thread); +} + +/* Recompute the effective priority from the base priority and the + donation table. Must be called with the scheduler lock held. */ + +static void +sched_recompute_priority (struct mach_thread *thread) +{ + mach_priority_t best = thread->base_priority; + uint32_t index; + + for (index = 0; index < MACH_SCHED_DONATIONS; index++) + if (thread->donations[index].count != 0 + && thread->donations[index].priority > best) + best = thread->donations[index].priority; + + thread->priority = best; + thread->pi_boosted = best != thread->base_priority; +} + +void +mach_sched_donate (struct mach_thread *owner, mach_priority_t priority) +{ + uint32_t index; + bool stored = false; + + if (owner == NULL) + return; + + if (priority > MACH_PRIO_MAX) + priority = MACH_PRIO_MAX; + + mach_spinlock_lock (&mach_scheduler.lock); + + for (index = 0; index < MACH_SCHED_DONATIONS; index++) + if (owner->donations[index].count != 0 + && owner->donations[index].priority == priority) + { + owner->donations[index].count++; + stored = true; + break; + } + + if (!stored) + for (index = 0; index < MACH_SCHED_DONATIONS; index++) + if (owner->donations[index].count == 0) + { + owner->donations[index].priority = priority; + owner->donations[index].count = 1; + owner->donation_count++; + stored = true; + break; + } + + sched_recompute_priority (owner); + mach_spinlock_unlock (&mach_scheduler.lock); + + if (stored) + sched_reposition (owner); +} + +void +mach_sched_undonate (struct mach_thread *owner, mach_priority_t priority) +{ + uint32_t index; + + if (owner == NULL) + return; + + mach_spinlock_lock (&mach_scheduler.lock); + + for (index = 0; index < MACH_SCHED_DONATIONS; index++) + { + if (owner->donations[index].count == 0 + || owner->donations[index].priority != priority) + continue; + + owner->donations[index].count--; + if (owner->donations[index].count == 0) + { + owner->donations[index].priority = 0; + if (owner->donation_count > 0) + owner->donation_count--; + } + break; + } + + sched_recompute_priority (owner); + mach_spinlock_unlock (&mach_scheduler.lock); + + sched_reposition (owner); +} + +struct mach_thread * +mach_sched_current_thread (void) +{ + return mach_scheduler.current; +} + +uint32_t +mach_sched_runnable_count (void) +{ + uint32_t total = 0; + uint32_t index; + + for (index = 0; index < mach_scheduler.nr_cpus; index++) + total += atomic_load_explicit (&mach_scheduler.cpus[index].nr_running, + memory_order_relaxed); + + return total; +} diff --git a/modern/src/vm/vm.c b/modern/src/vm/vm.c new file mode 100644 index 00000000..5d072543 --- /dev/null +++ b/modern/src/vm/vm.c @@ -0,0 +1,1155 @@ +/* Virtual memory implementation: radix page tables, NUMA buddy and COW. + Copyright (C) 2026 Free Software Foundation, Inc. + + This file is part of GNU Mach. See base.h for the license. */ + +#include <mach/c17/vm.h> +#include <mach/c17/atomic.h> + +/* --------------------------------------------------------------------- + Page table encoding. + --------------------------------------------------------------------- */ + +#define MACH_PTE_ADDR_MASK 0x000ffffffffff000ull +#define MACH_ARM_AF (1ull << 10) +#define MACH_ARM_SH_INNER (3ull << 8) +#define MACH_ARM_AP_EL0 (1ull << 6) +#define MACH_ARM_AP_RO (1ull << 7) +#define MACH_ARM_PXN (1ull << 53) +#define MACH_ARM_UXN (1ull << 54) + +static bool +pte_present (const struct mach_pmap_format *format, uint64_t entry) +{ + return (entry & format->present) != 0; +} + +MACH_UNUSED static bool +pte_is_table (const struct mach_pmap_format *format, uint64_t entry, + unsigned int level) +{ + if (!pte_present (format, entry) || level == 0) + return false; + + if (format->arch == MACH_PMAP_AARCH64) + return (entry & 2u) != 0; + + return (entry & format->huge) == 0; +} + +static bool +pte_is_leaf (const struct mach_pmap_format *format, uint64_t entry, + unsigned int level) +{ + if (!pte_present (format, entry)) + return false; + + if (level == 0) + return true; + + if (format->arch == MACH_PMAP_AARCH64) + return (entry & 2u) == 0; + + return (entry & format->huge) != 0; +} + +static uint64_t +pte_encode (const struct mach_pmap_format *format, mach_phys_t address, + uint32_t protection, bool table) +{ + uint64_t entry = address & format->phys_mask; + + entry |= format->present; + + if (table) + { + if (format->arch == MACH_PMAP_AARCH64) + entry |= 2u | MACH_ARM_AF | MACH_ARM_SH_INNER; + else + /* x86_64 checks the user bit at every level, so propagate it + through the table entries. */ + entry |= format->user; + return entry; + } + + if (format->arch == MACH_PMAP_AARCH64) + { + entry |= MACH_ARM_AF | MACH_ARM_SH_INNER; + if ((protection & MACH_VM_PROT_USER) != 0) + entry |= MACH_ARM_AP_EL0; + if ((protection & MACH_VM_PROT_WRITE) == 0) + entry |= MACH_ARM_AP_RO; + if ((protection & MACH_VM_PROT_EXEC) == 0) + entry |= MACH_ARM_PXN | MACH_ARM_UXN; + } + else + { + if ((protection & MACH_VM_PROT_WRITE) != 0) + entry |= format->writable; + if ((protection & MACH_VM_PROT_USER) != 0) + entry |= format->user; + if ((protection & MACH_VM_PROT_EXEC) == 0) + entry |= format->no_exec; + } + + return entry; +} + +static uint32_t +pte_decode_protection (const struct mach_pmap_format *format, uint64_t entry) +{ + uint32_t protection = MACH_VM_PROT_READ; + + if (format->arch == MACH_PMAP_AARCH64) + { + if ((entry & MACH_ARM_AP_RO) == 0) + protection |= MACH_VM_PROT_WRITE; + if ((entry & MACH_ARM_AP_EL0) != 0) + protection |= MACH_VM_PROT_USER; + if ((entry & (MACH_ARM_PXN | MACH_ARM_UXN)) == 0) + protection |= MACH_VM_PROT_EXEC; + } + else + { + if ((entry & format->writable) != 0) + protection |= MACH_VM_PROT_WRITE; + if ((entry & format->user) != 0) + protection |= MACH_VM_PROT_USER; + if ((entry & format->no_exec) == 0) + protection |= MACH_VM_PROT_EXEC; + } + + return protection; +} + +void +mach_pmap_format_init (struct mach_pmap_format *format, mach_pmap_arch_t arch, + unsigned int levels) +{ + mach_memset (format, 0, sizeof (*format)); + format->arch = arch; + format->levels = levels == 5 ? 5u : 4u; + + if (arch == MACH_PMAP_AARCH64) + { + format->phys_mask = MACH_PTE_ADDR_MASK; + format->present = 1u; + format->no_exec = MACH_ARM_PXN | MACH_ARM_UXN; + format->huge = 2u; /* Table bit; layout is checked. */ + format->table_flags = MACH_ARM_AF | MACH_ARM_SH_INNER; + } + else + { + format->phys_mask = MACH_PTE_ADDR_MASK; + format->present = 1u; + format->writable = 2u; + format->user = 4u; + format->no_exec = 1ull << 63; + format->huge = 1ull << 7; + format->table_flags = 0; + } +} + +mach_error_t +mach_pmap_init (struct mach_pmap *pmap, + const struct mach_pmap_format *format, + const struct mach_pmap_ops *ops, void *context) +{ + mach_phys_t root; + + if (pmap == NULL || format == NULL || ops == NULL + || ops->alloc_table == NULL || ops->phys_to_virt == NULL) + return MACH_EINVAL; + + mach_memset (pmap, 0, sizeof (*pmap)); + pmap->format = *format; + pmap->ops = *ops; + pmap->context = context; + mach_spinlock_init (&pmap->lock); + atomic_init (&pmap->mapped_pages, 0u); + + pmap->user_min = 0x10000ull; + pmap->user_max = format->levels == 5 ? (1ull << 56) : (1ull << 47); + + root = ops->alloc_table (context); + if (root == MACH_PHYS_NULL) + return MACH_ENOMEM; + + if (ops->zero_page != NULL) + ops->zero_page (context, root); + else + mach_memset (ops->phys_to_virt (context, root), 0, + MACH_PAGE_SIZE); + + pmap->root = root; + return MACH_OK; +} + +/* Return the address of the entry for ADDRESS at LEAF_LEVEL, allocating + the tables on the way when ALLOCATE is set. The caller holds the + pmap lock. */ + +static uint64_t * +pmap_entry (struct mach_pmap *pmap, mach_vaddr_t address, + unsigned int leaf_level, bool allocate, mach_error_t *error) +{ + const struct mach_pmap_format *format = &pmap->format; + uint64_t *table = pmap->ops.phys_to_virt (pmap->context, pmap->root); + unsigned int level; + + for (level = format->levels - 1; level > leaf_level; level--) + { + uint64_t *entry; + unsigned int index; + + index = (unsigned int) ((address >> (12 + level * 9)) & 0x1ffu); + entry = &table[index]; + + if (pte_is_leaf (format, *entry, level)) + { + *error = MACH_EBUSY; + return NULL; + } + + if (!pte_present (format, *entry)) + { + mach_phys_t next; + + if (!allocate) + { + *error = MACH_ENOENT; + return NULL; + } + + next = pmap->ops.alloc_table (pmap->context); + if (next == MACH_PHYS_NULL) + { + *error = MACH_ENOMEM; + return NULL; + } + + if (pmap->ops.zero_page != NULL) + pmap->ops.zero_page (pmap->context, next); + else + mach_memset (pmap->ops.phys_to_virt (pmap->context, next), 0, + MACH_PAGE_SIZE); + + *entry = pte_encode (format, next, MACH_VM_PROT_READ + | MACH_VM_PROT_WRITE, true); + } + + table = pmap->ops.phys_to_virt (pmap->context, + *entry & format->phys_mask); + } + + *error = MACH_OK; + return &table[(address >> (12 + leaf_level * 9)) & 0x1ffu]; +} + +mach_error_t +mach_pmap_walk (struct mach_pmap *pmap, mach_vaddr_t address, bool allocate, + uint64_t **entry, unsigned int *level) +{ + const struct mach_pmap_format *format; + uint64_t *table; + unsigned int current; + + if (pmap == NULL || entry == NULL || level == NULL) + return MACH_EINVAL; + + format = &pmap->format; + table = pmap->ops.phys_to_virt (pmap->context, pmap->root); + + for (current = format->levels - 1; current > 0; current--) + { + uint64_t *slot = &table[(address >> (12 + current * 9)) & 0x1ffu]; + + if (pte_is_leaf (format, *slot, current)) + { + *entry = slot; + *level = current; + return MACH_OK; + } + + if (!pte_present (format, *slot)) + { + if (!allocate) + { + *entry = slot; + *level = current; + return MACH_ENOENT; + } + + { + mach_phys_t next = pmap->ops.alloc_table (pmap->context); + + if (next == MACH_PHYS_NULL) + return MACH_ENOMEM; + if (pmap->ops.zero_page != NULL) + pmap->ops.zero_page (pmap->context, next); + else + mach_memset (pmap->ops.phys_to_virt (pmap->context, next), 0, + MACH_PAGE_SIZE); + *slot = pte_encode (format, next, + MACH_VM_PROT_READ | MACH_VM_PROT_WRITE, true); + } + } + + table = pmap->ops.phys_to_virt (pmap->context, + *slot & format->phys_mask); + } + + *entry = &table[(address >> 12) & 0x1ffu]; + *level = 0; + return pte_present (format, **entry) ? MACH_OK : MACH_ENOENT; +} + +mach_error_t +mach_pmap_map (struct mach_pmap *pmap, mach_vaddr_t virtual_address, + mach_phys_t physical_address, size_t length, + uint32_t protection) +{ + mach_error_t error = MACH_OK; + + if (pmap == NULL || length == 0 + || (virtual_address & MACH_PAGE_MASK) != 0 + || (physical_address & MACH_PAGE_MASK) != 0 + || (length & MACH_PAGE_MASK) != 0) + return MACH_EINVAL; + + if (virtual_address < pmap->user_min + || virtual_address + length > pmap->user_max) + return MACH_ERANGE; + + mach_spinlock_lock (&pmap->lock); + + while (length != 0) + { + uint64_t *entry; + uint64_t value; + + if ((virtual_address & 0x1fffffull) == 0 + && (physical_address & 0x1fffffull) == 0 + && length >= 0x200000u) + { + entry = pmap_entry (pmap, virtual_address, 1, true, &error); + if (entry == NULL) + break; + if (pte_present (&pmap->format, *entry)) + { + error = MACH_EBUSY; + break; + } + + value = pte_encode (&pmap->format, physical_address, protection, + false); + value |= pmap->format.huge; + *entry = value; + virtual_address += 0x200000u; + physical_address += 0x200000u; + length -= 0x200000u; + atomic_fetch_add_explicit (&pmap->mapped_pages, 512u, + memory_order_relaxed); + } + else + { + entry = pmap_entry (pmap, virtual_address, 0, true, &error); + if (entry == NULL) + break; + if (pte_present (&pmap->format, *entry)) + { + error = MACH_EBUSY; + break; + } + + *entry = pte_encode (&pmap->format, physical_address, protection, + false); + virtual_address += MACH_PAGE_SIZE; + physical_address += MACH_PAGE_SIZE; + length -= MACH_PAGE_SIZE; + atomic_fetch_add_explicit (&pmap->mapped_pages, 1u, + memory_order_relaxed); + } + + if (pmap->ops.flush_tlb != NULL) + pmap->ops.flush_tlb (pmap->context, virtual_address, MACH_PAGE_SIZE); + } + + mach_spinlock_unlock (&pmap->lock); + return error; +} + +mach_error_t +mach_pmap_unmap (struct mach_pmap *pmap, mach_vaddr_t virtual_address, + size_t length) +{ + if (pmap == NULL || length == 0 + || (virtual_address & MACH_PAGE_MASK) != 0 + || (length & MACH_PAGE_MASK) != 0) + return MACH_EINVAL; + + mach_spinlock_lock (&pmap->lock); + + while (length != 0) + { + mach_error_t error; + uint64_t *entry; + + entry = pmap_entry (pmap, virtual_address, 0, false, &error); + if (entry == NULL && error == MACH_EBUSY) + { + /* A huge mapping covers this address. It can only be removed + when the request covers the whole huge page. */ + if ((virtual_address & 0x1fffffull) != 0 || length < 0x200000u) + { + mach_spinlock_unlock (&pmap->lock); + return MACH_EINVAL; + } + entry = pmap_entry (pmap, virtual_address, 1, false, &error); + + if (entry != NULL && pte_present (&pmap->format, *entry)) + { + *entry = 0; + atomic_fetch_sub_explicit (&pmap->mapped_pages, 512u, + memory_order_relaxed); + if (pmap->ops.flush_tlb != NULL) + pmap->ops.flush_tlb (pmap->context, virtual_address, + 0x200000u); + virtual_address += 0x200000u; + length -= 0x200000u; + continue; + } + } + + if (entry != NULL && pte_present (&pmap->format, *entry)) + { + *entry = 0; + atomic_fetch_sub_explicit (&pmap->mapped_pages, 1u, + memory_order_relaxed); + + if (pmap->ops.flush_tlb != NULL) + pmap->ops.flush_tlb (pmap->context, virtual_address, + MACH_PAGE_SIZE); + virtual_address += MACH_PAGE_SIZE; + length -= MACH_PAGE_SIZE; + } + else + { + virtual_address += MACH_PAGE_SIZE; + if (length >= MACH_PAGE_SIZE) + length -= MACH_PAGE_SIZE; + else + length = 0; + } + } + + mach_spinlock_unlock (&pmap->lock); + return MACH_OK; +} + +mach_error_t +mach_pmap_protect (struct mach_pmap *pmap, mach_vaddr_t virtual_address, + size_t length, uint32_t protection) +{ + if (pmap == NULL || (virtual_address & MACH_PAGE_MASK) != 0) + return MACH_EINVAL; + + mach_spinlock_lock (&pmap->lock); + + while (length != 0) + { + mach_error_t error; + uint64_t *entry = pmap_entry (pmap, virtual_address, 0, false, &error); + + if (entry != NULL && pte_present (&pmap->format, *entry)) + { + mach_phys_t address = *entry & pmap->format.phys_mask; + + *entry = pte_encode (&pmap->format, address, protection, false); + + if (pmap->ops.flush_tlb != NULL) + pmap->ops.flush_tlb (pmap->context, virtual_address, + MACH_PAGE_SIZE); + } + + virtual_address += MACH_PAGE_SIZE; + length = length >= MACH_PAGE_SIZE ? length - MACH_PAGE_SIZE : 0; + } + + mach_spinlock_unlock (&pmap->lock); + return MACH_OK; +} + +mach_error_t +mach_pmap_translate (struct mach_pmap *pmap, mach_vaddr_t virtual_address, + mach_phys_t *physical_address, uint32_t *protection) +{ + mach_error_t error; + uint64_t *entry; + unsigned int level; + + if (pmap == NULL || physical_address == NULL) + return MACH_EINVAL; + + mach_spinlock_lock (&pmap->lock); + error = mach_pmap_walk (pmap, virtual_address, false, &entry, &level); + + if (error == MACH_OK && pte_present (&pmap->format, *entry)) + { + uint64_t offset_mask = (1ull << (12 + level * 9)) - 1u; + + *physical_address = (*entry & pmap->format.phys_mask) + | (virtual_address & offset_mask); + if (protection != NULL) + *protection = pte_decode_protection (&pmap->format, *entry); + } + else + error = MACH_ENOENT; + + mach_spinlock_unlock (&pmap->lock); + return error; +} + +/* --------------------------------------------------------------------- + NUMA buddy allocator. + --------------------------------------------------------------------- */ + +static uint64_t +node_index (const struct mach_numa_node *node, mach_phys_t address) +{ + return (address - node->base) / MACH_PAGE_SIZE; +} + +static void +node_push (struct mach_numa_node *node, uint64_t index, uint32_t order) +{ + struct mach_vm_page *page = &node->pages[index]; + + page->order = (uint8_t) order; + page->free = true; + mach_list_init (&page->link); + mach_list_add_head (&node->free_area[order], &page->link); +} + +static struct mach_vm_page * +node_pop (struct mach_numa_node *node, uint32_t order) +{ + struct mach_list *list = &node->free_area[order]; + struct mach_vm_page *page; + + if (mach_list_empty (list)) + return NULL; + + page = MACH_LIST_ENTRY (list->next, struct mach_vm_page, link); + mach_list_remove (&page->link); + page->free = false; + return page; +} + +static mach_phys_t +node_alloc (struct mach_numa_node *node, uint32_t order) +{ + struct mach_vm_page *page; + uint64_t index; + uint32_t current; + + for (current = order; current <= MACH_VM_MAX_ORDER; current++) + { + page = node_pop (node, current); + if (page != NULL) + { + uint64_t base_index = (uint64_t) (page - node->pages); + + while (current > order) + { + current--; + node_push (node, base_index + (1ull << current), current); + } + + index = base_index; + for (uint64_t i = 0; i < (1ull << order); i++) + { + node->pages[index + i].free = false; + node->pages[index + i].order = (uint8_t) order; + } + + atomic_fetch_sub_explicit (&node->free_pages, 1ull << order, + memory_order_relaxed); + return node->base + index * MACH_PAGE_SIZE; + } + } + + return MACH_PHYS_NULL; +} + +static void +node_free (struct mach_numa_node *node, uint64_t index, uint32_t order) +{ + uint64_t size = 1ull << order; + + atomic_fetch_add_explicit (&node->free_pages, size, memory_order_relaxed); + + while (order < MACH_VM_MAX_ORDER) + { + uint64_t buddy = index ^ size; + struct mach_vm_page *buddy_page; + + if (buddy >= node->nr_pages) + break; + + buddy_page = &node->pages[buddy]; + if (!buddy_page->free || buddy_page->order != order) + break; + + mach_list_remove (&buddy_page->link); + buddy_page->free = false; + if (buddy < index) + index = buddy; + order++; + size = 1ull << order; + } + + for (uint64_t i = 0; i < size; i++) + node->pages[index + i].free = true; + + node_push (node, index, order); +} + +mach_error_t +mach_vm_phys_init (struct mach_vm_phys *physical, + const struct mach_numa_region *regions, uint32_t nr_regions, + struct mach_vm_page *page_storage, uint64_t nr_page_storage, + const uint8_t *distances, const struct mach_pmap_ops *ops, + void *context) +{ + uint64_t cursor = 0; + uint32_t region; + uint32_t index; + + if (physical == NULL || regions == NULL || page_storage == NULL + || nr_regions == 0 || nr_regions > MACH_VM_MAX_NODES) + return MACH_EINVAL; + + mach_memset (physical, 0, sizeof (*physical)); + physical->nr_nodes = nr_regions; + physical->context = context; + if (ops != NULL) + physical->ops = *ops; + atomic_init (&physical->total_pages, 0u); + atomic_init (&physical->allocated_pages, 0u); + + for (index = 0; index < MACH_VM_MAX_NODES; index++) + for (region = 0; region < MACH_VM_MAX_NODES; region++) + physical->distance[index][region] = index == region ? 10 : 20; + + if (distances != NULL) + for (index = 0; index < nr_regions; index++) + for (region = 0; region < nr_regions; region++) + physical->distance[index][region] + = distances[index * nr_regions + region]; + + for (region = 0; region < nr_regions; region++) + { + struct mach_numa_node *node = &physical->nodes[region]; + uint64_t nr_pages = regions[region].nr_pages; + uint64_t page_index = 0; + + if (regions[region].node >= MACH_VM_MAX_NODES + || (regions[region].base & MACH_PAGE_MASK) != 0 + || nr_pages == 0 + || cursor + nr_pages > nr_page_storage) + return MACH_EINVAL; + + for (uint32_t previous = 0; previous < region; previous++) + if (regions[previous].node == regions[region].node) + return MACH_EINVAL; + + node->id = regions[region].node; + node->base = regions[region].base; + node->nr_pages = nr_pages; + node->pages = &page_storage[cursor]; + atomic_init (&node->free_pages, 0u); + mach_spinlock_init (&node->lock); + + for (index = 0; index <= MACH_VM_MAX_ORDER; index++) + mach_list_init (&node->free_area[index]); + + for (index = 0; index < (uint32_t) nr_pages; index++) + { + node->pages[index].free = false; + node->pages[index].order = 0; + mach_list_init (&node->pages[index].link); + } + + while (page_index < nr_pages) + { + uint32_t order = 0; + + while (order < MACH_VM_MAX_ORDER + && (page_index & ((1ull << (order + 1)) - 1u)) == 0 + && page_index + (1ull << (order + 1)) <= nr_pages) + order++; + + node_push (node, page_index, order); + atomic_fetch_add_explicit (&node->free_pages, 1ull << order, + memory_order_relaxed); + page_index += 1ull << order; + } + + cursor += nr_pages; + atomic_fetch_add_explicit (&physical->total_pages, nr_pages, + memory_order_relaxed); + } + + return MACH_OK; +} + +mach_phys_t +mach_vm_alloc_pages (struct mach_vm_phys *physical, uint32_t nr_pages, + int preferred_node) +{ + uint32_t order = (uint32_t) mach_log2_ceil_u64 (nr_pages); + bool tried[MACH_VM_MAX_NODES]; + mach_phys_t result = MACH_PHYS_NULL; + uint32_t attempt; + + if (physical == NULL || nr_pages == 0) + return MACH_PHYS_NULL; + + if (order > MACH_VM_MAX_ORDER) + return MACH_PHYS_NULL; + + for (uint32_t index = 0; index < MACH_VM_MAX_NODES; index++) + tried[index] = false; + + for (attempt = 0; attempt < physical->nr_nodes; attempt++) + { + uint32_t best = physical->nr_nodes; + uint8_t best_distance = 0xffu; + + for (uint32_t index = 0; index < physical->nr_nodes; index++) + { + uint8_t distance; + + if (tried[index]) + continue; + + distance = preferred_node >= 0 + && (uint32_t) preferred_node < physical->nr_nodes + ? physical->distance[preferred_node][index] + : 1u; + + if (best == physical->nr_nodes || distance < best_distance) + { + best = index; + best_distance = distance; + } + } + + if (best == physical->nr_nodes) + break; + + tried[best] = true; + { + struct mach_numa_node *node = &physical->nodes[best]; + + mach_spinlock_lock (&node->lock); + result = node_alloc (node, order); + mach_spinlock_unlock (&node->lock); + } + + if (result != MACH_PHYS_NULL) + { + atomic_fetch_add_explicit (&physical->allocated_pages, nr_pages, + memory_order_relaxed); + return result; + } + } + + return MACH_PHYS_NULL; +} + +mach_error_t +mach_vm_free_pages (struct mach_vm_phys *physical, mach_phys_t address, + uint32_t nr_pages) +{ + struct mach_numa_node *node = NULL; + uint64_t index; + uint32_t remaining = nr_pages; + + if (physical == NULL || nr_pages == 0 + || (address & MACH_PAGE_MASK) != 0) + return MACH_EINVAL; + + for (uint32_t i = 0; i < physical->nr_nodes; i++) + if (address >= physical->nodes[i].base + && address < physical->nodes[i].base + + physical->nodes[i].nr_pages * MACH_PAGE_SIZE) + { + node = &physical->nodes[i]; + break; + } + + if (node == NULL) + return MACH_EINVAL; + + index = node_index (node, address); + + if (index + nr_pages > node->nr_pages) + return MACH_EINVAL; + + mach_spinlock_lock (&node->lock); + + while (remaining != 0) + { + uint32_t order = (uint32_t) mach_log2_floor_u64 (remaining); + + while (order > 0 && (index & ((1ull << order) - 1u)) != 0) + order--; + + node_free (node, index, order); + index += 1ull << order; + remaining -= 1u << order; + } + + mach_spinlock_unlock (&node->lock); + atomic_fetch_sub_explicit (&physical->allocated_pages, + (uint64_t) nr_pages, memory_order_relaxed); + return MACH_OK; +} + +uint64_t +mach_vm_free_page_count (const struct mach_vm_phys *physical) +{ + uint64_t total = 0; + + for (uint32_t index = 0; index < physical->nr_nodes; index++) + total += atomic_load_explicit (&physical->nodes[index].free_pages, + memory_order_relaxed); + + return total; +} + +uint64_t +mach_vm_free_page_count_node (const struct mach_vm_phys *physical, + uint32_t node) +{ + if (physical == NULL || node >= physical->nr_nodes) + return 0; + + return atomic_load_explicit (&physical->nodes[node].free_pages, + memory_order_relaxed); +} + +/* --------------------------------------------------------------------- + VM objects, copy-on-write and demand paging. + --------------------------------------------------------------------- */ + +mach_error_t +mach_vm_object_init (struct mach_vm_object *object, struct mach_vm_slot *slots, + uint64_t nr_slots, struct mach_vm_resident *residents, + uint64_t nr_residents, struct mach_vm_pager *pager, + uint64_t object_size) +{ + if (object == NULL || slots == NULL || residents == NULL || nr_slots == 0) + return MACH_EINVAL; + + mach_memset (object, 0, sizeof (*object)); + mach_memset (slots, 0, sizeof (*slots) * nr_slots); + mach_memset (residents, 0, sizeof (*residents) * nr_residents); + + for (uint64_t index = 0; index < nr_residents; index++) + mach_refcount_init (&residents[index].refs, 0); + + object->slots = slots; + object->residents = residents; + object->nr_slots = nr_slots; + object->nr_residents = nr_residents; + object->pager = pager; + object->object_size = object_size; + mach_refcount_init (&object->refs, 1u); + mach_spinlock_init (&object->lock); + atomic_init (&object->resident_cursor, 0u); + return MACH_OK; +} + +static struct mach_vm_resident * +object_resident_alloc (struct mach_vm_object *object) +{ + uint64_t start; + uint64_t index; + + start = atomic_load_explicit (&object->resident_cursor, + memory_order_relaxed); + + for (index = 0; index < object->nr_residents; index++) + { + uint64_t slot = (start + index) % object->nr_residents; + struct mach_vm_resident *resident = &object->residents[slot]; + uint32_t expected = 0; + + if (atomic_compare_exchange_strong_explicit (&resident->refs.count, + &expected, 1u, + memory_order_acquire, + memory_order_relaxed)) + { + resident->address = MACH_PHYS_NULL; + resident->flags = MACH_VM_RESIDENT_USED; + atomic_store_explicit (&object->resident_cursor, slot + 1u, + memory_order_relaxed); + return resident; + } + } + + return NULL; +} + +mach_error_t +mach_vm_object_fork (struct mach_vm_object *parent, + struct mach_vm_object *child, + struct mach_vm_slot *child_slots, + struct mach_vm_resident *child_residents, + uint64_t nr_slots) +{ + mach_error_t error; + + if (parent == NULL || child == NULL || child_slots == NULL + || child_residents == NULL || nr_slots < parent->nr_slots) + return MACH_EINVAL; + + error = mach_vm_object_init (child, child_slots, parent->nr_slots, + child_residents, parent->nr_residents, + parent->pager, parent->object_size); + if (error != MACH_OK) + return error; + + mach_spinlock_lock (&parent->lock); + + for (uint64_t index = 0; index < parent->nr_slots; index++) + { + struct mach_vm_resident *resident = parent->slots[index].resident; + + child_slots[index].resident = resident; + if (resident != NULL) + mach_refcount_inc (&resident->refs); + } + + mach_spinlock_unlock (&parent->lock); + return MACH_OK; +} + +void +mach_vm_slot_release (struct mach_vm_map *map, struct mach_vm_slot *slot) +{ + struct mach_vm_resident *resident = slot->resident; + + if (resident == NULL) + return; + + slot->resident = NULL; + if (mach_refcount_dec_and_test (&resident->refs)) + { + if (resident->address != MACH_PHYS_NULL && map->physical != NULL) + mach_vm_free_pages (map->physical, resident->address, 1); + resident->address = MACH_PHYS_NULL; + resident->flags = MACH_VM_RESIDENT_FREE; + } +} + +mach_error_t +mach_vm_map_init (struct mach_vm_map *map, struct mach_vm_object *object, + struct mach_vm_phys *physical, + const struct mach_pmap_format *format, + const struct mach_pmap_ops *ops, void *context, + uint32_t protection) +{ + mach_error_t error; + + if (map == NULL || object == NULL) + return MACH_EINVAL; + + mach_memset (map, 0, sizeof (*map)); + map->object = object; + map->physical = physical; + map->protection = protection; + map->base = 0; + map->next_hint = 0x10000ull; + + error = mach_pmap_init (&map->pmap, format, ops, context); + if (error != MACH_OK) + return error; + + return MACH_OK; +} + +/* Make sure the page for SLOT is resident and, for a write fault on a + shared page, replace it with a private copy. The object lock is held + by the caller. */ + +static mach_error_t +object_resolve (struct mach_vm_map *map, struct mach_vm_slot *slot, + uint64_t offset, bool write, mach_phys_t *address) +{ + struct mach_vm_object *object = map->object; + struct mach_vm_resident *resident = slot->resident; + + if (resident == NULL) + { + mach_error_t error = MACH_ENOMEM; + + resident = object_resident_alloc (object); + if (resident == NULL) + return MACH_ENOMEM; + + if (object->pager != NULL && object->pager->ops != NULL + && object->pager->ops->get_page != NULL) + error = object->pager->ops->get_page (object->pager, offset, + &resident->address); + + if (error != MACH_OK || resident->address == MACH_PHYS_NULL) + { + if (map->physical == NULL) + { + atomic_store_explicit (&resident->refs.count, 0u, + memory_order_relaxed); + return error == MACH_OK ? MACH_ENOMEM : error; + } + + resident->address = mach_vm_alloc_pages (map->physical, 1, -1); + if (resident->address == MACH_PHYS_NULL) + { + atomic_store_explicit (&resident->refs.count, 0u, + memory_order_relaxed); + return MACH_ENOMEM; + } + + if (map->pmap.ops.zero_page != NULL) + map->pmap.ops.zero_page (map->pmap.context, resident->address); + else + mach_memset (map->pmap.ops.phys_to_virt (map->pmap.context, + resident->address), + 0, MACH_PAGE_SIZE); + } + + resident->flags = MACH_VM_PAGE_RESIDENT; + slot->resident = resident; + } + else if (write && mach_refcount_load (&resident->refs) > 1) + { + struct mach_vm_resident *copy; + mach_phys_t new_page; + + copy = object_resident_alloc (object); + if (copy == NULL) + return MACH_ENOMEM; + + if (map->physical == NULL) + { + atomic_store_explicit (©->refs.count, 0u, memory_order_relaxed); + return MACH_ENOMEM; + } + + new_page = mach_vm_alloc_pages (map->physical, 1, -1); + if (new_page == MACH_PHYS_NULL) + { + atomic_store_explicit (©->refs.count, 0u, memory_order_relaxed); + return MACH_ENOMEM; + } + + if (map->pmap.ops.copy_page != NULL) + map->pmap.ops.copy_page (map->pmap.context, new_page, + resident->address); + else + mach_memcpy (map->pmap.ops.phys_to_virt (map->pmap.context, new_page), + map->pmap.ops.phys_to_virt (map->pmap.context, + resident->address), + MACH_PAGE_SIZE); + + copy->address = new_page; + copy->flags = MACH_VM_PAGE_RESIDENT | MACH_VM_PAGE_DIRTY; + slot->resident = copy; + + /* Drop this map's reference to the shared page. */ + if (mach_refcount_dec_and_test (&resident->refs)) + { + mach_vm_free_pages (map->physical, resident->address, 1); + resident->address = MACH_PHYS_NULL; + resident->flags = MACH_VM_RESIDENT_FREE; + } + + resident = copy; + } + + *address = resident->address; + return resident->address == MACH_PHYS_NULL ? MACH_ENOMEM : MACH_OK; +} + +mach_error_t +mach_vm_map_fault (struct mach_vm_map *map, mach_vaddr_t virtual_address, + bool write, mach_phys_t *address) +{ + struct mach_vm_object *object; + struct mach_vm_slot *slot; + mach_error_t error; + mach_phys_t physical = MACH_PHYS_NULL; + uint32_t protection; + uint64_t index; + + if (map == NULL || map->object == NULL + || (virtual_address & MACH_PAGE_MASK) != 0) + return MACH_EINVAL; + + if (virtual_address < map->base) + return MACH_ERANGE; + + object = map->object; + index = (virtual_address - map->base) / MACH_PAGE_SIZE; + + if (index >= object->nr_slots) + return MACH_ERANGE; + + slot = &object->slots[index]; + + mach_spinlock_lock (&object->lock); + error = object_resolve (map, slot, index * MACH_PAGE_SIZE, write, &physical); + mach_spinlock_unlock (&object->lock); + + if (error != MACH_OK) + return error; + + protection = MACH_VM_PROT_READ + | (write ? MACH_VM_PROT_WRITE : 0) + | (map->protection & (MACH_VM_PROT_EXEC | MACH_VM_PROT_USER)); + + { + mach_phys_t existing; + + if (mach_pmap_translate (&map->pmap, virtual_address, &existing, NULL) + == MACH_OK) + { + if (existing == physical) + { + if (write) + mach_pmap_protect (&map->pmap, virtual_address, MACH_PAGE_SIZE, + protection); + if (address != NULL) + *address = physical; + return MACH_OK; + } + + /* The slot was replaced (by COW or by a pager): drop the stale + translation before installing the new page. */ + error = mach_pmap_unmap (&map->pmap, virtual_address, + MACH_PAGE_SIZE); + if (error != MACH_OK) + return error; + } + } + + error = mach_pmap_map (&map->pmap, virtual_address, physical, + MACH_PAGE_SIZE, protection); + if (error == MACH_OK && address != NULL) + *address = physical; + + return error; +} diff --git a/modern/tests/test_sched.c b/modern/tests/test_sched.c new file mode 100644 index 00000000..da658a9b --- /dev/null +++ b/modern/tests/test_sched.c @@ -0,0 +1,158 @@ +/* Tests for hybrid placement, priority inheritance and accounting. */ + +#include <mach/c17/sched.h> + +#include "test.h" + +static struct mach_thread threads[8]; + +static void +dummy_entry (void *argument) +{ + (void) argument; +} + +static void +test_placement (void) +{ + struct mach_thread *thread; + + mach_sched_init (NULL); + CHECK_EQ (mach_sched_register_cpu (0, MACH_CPU_PERFORMANCE, 2048), MACH_OK); + CHECK_EQ (mach_sched_register_cpu (1, MACH_CPU_EFFICIENCY, 1024), MACH_OK); + CHECK_EQ (mach_sched_cpu_count (), 2); + + thread = &threads[0]; + CHECK_EQ (mach_sched_thread_init (thread, MACH_PRIO_REALTIME, + MACH_SCHED_REALTIME, dummy_entry, NULL), + MACH_OK); + CHECK (mach_sched_select_cpu (thread)->kind == MACH_CPU_PERFORMANCE); + + thread = &threads[1]; + CHECK_EQ (mach_sched_thread_init (thread, MACH_PRIO_BACKGROUND, + MACH_SCHED_BACKGROUND, dummy_entry, NULL), + MACH_OK); + CHECK (mach_sched_select_cpu (thread)->kind == MACH_CPU_EFFICIENCY); + + thread = &threads[2]; + CHECK_EQ (mach_sched_thread_init (thread, MACH_PRIO_TIMESHARE, + MACH_SCHED_TIMESHARE, dummy_entry, NULL), + MACH_OK); + CHECK (mach_sched_select_cpu (thread)->kind == MACH_CPU_PERFORMANCE); +} + +static void +test_runqueue (void) +{ + struct mach_cpu *cpu; + struct mach_thread *selected; + + mach_sched_init (NULL); + mach_sched_register_cpu (0, MACH_CPU_PERFORMANCE, 1024); + + for (uint32_t index = 0; index < 3; index++) + { + CHECK_EQ (mach_sched_thread_init (&threads[index], + 100 + (mach_priority_t) index * 10, + MACH_SCHED_TIMESHARE, dummy_entry, + NULL), MACH_OK); + mach_sched_make_ready (&threads[index]); + } + + cpu = mach_sched_cpu_at (0); + selected = mach_sched_pick_next (cpu); + CHECK (selected == &threads[2]); + selected = mach_sched_pick_next (cpu); + CHECK (selected == &threads[1]); + selected = mach_sched_pick_next (cpu); + CHECK (selected == &threads[0]); + CHECK (mach_sched_pick_next (cpu) == NULL); +} + +static void +test_priority_inheritance (void) +{ + struct mach_cpu *cpu; + struct mach_thread *owner = &threads[0]; + struct mach_thread *waiter = &threads[1]; + struct mach_thread *other = &threads[2]; + + mach_sched_init (NULL); + mach_sched_register_cpu (0, MACH_CPU_PERFORMANCE, 1024); + + mach_sched_thread_init (owner, 100, MACH_SCHED_TIMESHARE, dummy_entry, NULL); + mach_sched_thread_init (waiter, 200, MACH_SCHED_REALTIME, dummy_entry, NULL); + mach_sched_thread_init (other, 150, MACH_SCHED_TIMESHARE, dummy_entry, NULL); + + mach_sched_make_ready (owner); + mach_sched_make_ready (other); + + /* The owner starts below OTHER; the donation must move it above. */ + mach_sched_donate (owner, waiter->priority); + CHECK_EQ (owner->priority, 200); + CHECK (owner->pi_boosted); + + cpu = mach_sched_cpu_at (0); + CHECK (mach_sched_pick_next (cpu) == owner); + + mach_sched_undonate (owner, waiter->priority); + CHECK_EQ (owner->priority, 100); + CHECK (!owner->pi_boosted); + + /* Two donors: removing one must keep the other's boost. */ + mach_sched_donate (owner, 120); + mach_sched_donate (owner, 220); + CHECK_EQ (owner->priority, 220); + mach_sched_undonate (owner, 220); + CHECK_EQ (owner->priority, 120); + mach_sched_undonate (owner, 120); + CHECK_EQ (owner->priority, 100); +} + +static void +test_tick_and_balance (void) +{ + struct mach_cpu *cpu0; + struct mach_cpu *cpu1; + struct mach_thread *current = &threads[0]; + uint64_t before; + + mach_sched_init (NULL); + mach_sched_register_cpu (0, MACH_CPU_PERFORMANCE, 1024); + mach_sched_register_cpu (1, MACH_CPU_PERFORMANCE, 1024); + + mach_sched_thread_init (current, 128, MACH_SCHED_TIMESHARE, dummy_entry, + NULL); + mach_sched_thread_init (&threads[1], 128, MACH_SCHED_TIMESHARE, dummy_entry, + NULL); + mach_sched_thread_init (&threads[2], 128, MACH_SCHED_TIMESHARE, dummy_entry, + NULL); + + cpu0 = mach_sched_cpu_at (0); + cpu1 = mach_sched_cpu_at (1); + + cpu0->current = current; + current->state = MACH_THREAD_RUNNING; + before = current->vruntime; + mach_sched_tick (cpu0, 5000000u); + CHECK (current->vruntime > before); + CHECK ((current->flags & MACH_THREAD_NEED_RESCHED) != 0); + + mach_sched_make_ready (&threads[1]); + mach_sched_make_ready (&threads[2]); + /* Put both on CPU 0 so that CPU 1 has work to steal. */ + mach_sched_balance (cpu1); + CHECK_EQ (mach_sched_runnable_count (), 2); + CHECK (mach_sched_pick_next (cpu1) != NULL); +} + +static void +run_tests (void) +{ + test_placement (); + test_runqueue (); + test_priority_inheritance (); + test_tick_and_balance (); +} + +TEST_MAIN ("sched") diff --git a/modern/tests/test_vm.c b/modern/tests/test_vm.c new file mode 100644 index 00000000..974c2e9c --- /dev/null +++ b/modern/tests/test_vm.c @@ -0,0 +1,310 @@ +/* Tests for page tables, the NUMA allocator and copy-on-write. */ + +#include <mach/c17/vm.h> + +#include "test.h" + +#define ARENA_SIZE (16u * 1024u * 1024u) +#define TABLE_START 0xc00000u +#define NODE0_BASE 0x100000u +#define NODE0_PAGES 1024u +#define NODE1_BASE 0x600000u +#define NODE1_PAGES 1024u + +static unsigned char arena[ARENA_SIZE] __attribute__ ((aligned (4096))); +static struct mach_vm_page page_storage[NODE0_PAGES + NODE1_PAGES]; +static mach_phys_t table_cursor = TABLE_START; +static unsigned int tlb_flushes; + +static void * +fake_phys_to_virt (void *context, mach_phys_t address) +{ + (void) context; + return arena + address; +} + +static mach_phys_t +fake_alloc_table (void *context) +{ + mach_phys_t result; + + (void) context; + if (table_cursor + MACH_PAGE_SIZE > ARENA_SIZE) + return MACH_PHYS_NULL; + + result = table_cursor; + table_cursor += MACH_PAGE_SIZE; + return result; +} + +static void +fake_free_table (void *context, mach_phys_t address) +{ + (void) context; + (void) address; +} + +static void +fake_flush (void *context, mach_vaddr_t address, size_t length) +{ + (void) context; + (void) address; + (void) length; + tlb_flushes++; +} + +static void +fake_copy (void *context, mach_phys_t destination, mach_phys_t source) +{ + (void) context; + memcpy (arena + destination, arena + source, MACH_PAGE_SIZE); +} + +static void +fake_zero (void *context, mach_phys_t address) +{ + (void) context; + memset (arena + address, 0, MACH_PAGE_SIZE); +} + +static struct mach_pmap_ops fake_ops = +{ + .phys_to_virt = fake_phys_to_virt, + .alloc_table = fake_alloc_table, + .free_table = fake_free_table, + .flush_tlb = fake_flush, + .copy_page = fake_copy, + .zero_page = fake_zero +}; + +static void +test_pmap_4level (void) +{ + struct mach_pmap_format format; + struct mach_pmap pmap; + mach_phys_t translated; + uint32_t protection; + + mach_pmap_format_init (&format, MACH_PMAP_X86_64, 4); + CHECK_EQ (format.levels, 4); + CHECK_EQ (mach_pmap_init (&pmap, &format, &fake_ops, NULL), MACH_OK); + + CHECK_EQ (mach_pmap_map (&pmap, 0x40000000u, 0x100000u, MACH_PAGE_SIZE, + MACH_VM_PROT_READ | MACH_VM_PROT_WRITE + | MACH_VM_PROT_USER), MACH_OK); + CHECK_EQ (mach_pmap_translate (&pmap, 0x40000000u, &translated, &protection), + MACH_OK); + CHECK_EQ (translated, 0x100000u); + CHECK ((protection & MACH_VM_PROT_WRITE) != 0); + CHECK ((protection & MACH_VM_PROT_USER) != 0); + + CHECK_EQ (mach_pmap_protect (&pmap, 0x40000000u, MACH_PAGE_SIZE, + MACH_VM_PROT_READ), MACH_OK); + CHECK_EQ (mach_pmap_translate (&pmap, 0x40000000u, &translated, &protection), + MACH_OK); + CHECK ((protection & MACH_VM_PROT_WRITE) == 0); + + CHECK_EQ (mach_pmap_unmap (&pmap, 0x40000000u, MACH_PAGE_SIZE), MACH_OK); + CHECK_EQ (mach_pmap_translate (&pmap, 0x40000000u, &translated, &protection), + MACH_ENOENT); + + /* A 2 MiB mapping uses a huge page. */ + CHECK_EQ (mach_pmap_map (&pmap, 0x80000000u, 0x200000u, 0x200000u, + MACH_VM_PROT_READ | MACH_VM_PROT_WRITE), MACH_OK); + CHECK_EQ (mach_pmap_translate (&pmap, 0x80100000u, &translated, NULL), + MACH_OK); + CHECK_EQ (translated, 0x300000u); + CHECK_EQ (mach_pmap_unmap (&pmap, 0x80000000u, 0x200000u), MACH_OK); + CHECK_EQ (mach_pmap_translate (&pmap, 0x80100000u, &translated, NULL), + MACH_ENOENT); +} + +static void +test_pmap_5level (void) +{ + struct mach_pmap_format format; + struct mach_pmap pmap; + mach_phys_t translated; + + mach_pmap_format_init (&format, MACH_PMAP_X86_64, 5); + CHECK_EQ (format.levels, 5); + CHECK_EQ (mach_pmap_init (&pmap, &format, &fake_ops, NULL), MACH_OK); + + /* 1 TiB is only reachable with five levels. */ + CHECK_EQ (mach_pmap_map (&pmap, 0x10000000000ull, 0x110000u, MACH_PAGE_SIZE, + MACH_VM_PROT_READ | MACH_VM_PROT_WRITE), MACH_OK); + CHECK_EQ (mach_pmap_translate (&pmap, 0x10000000000ull, &translated, NULL), + MACH_OK); + CHECK_EQ (translated, 0x110000u); + CHECK_EQ (mach_pmap_unmap (&pmap, 0x10000000000ull, MACH_PAGE_SIZE), + MACH_OK); +} + +static void +test_pmap_aarch64 (void) +{ + struct mach_pmap_format format; + struct mach_pmap pmap; + mach_phys_t translated; + uint32_t protection; + + mach_pmap_format_init (&format, MACH_PMAP_AARCH64, 4); + CHECK_EQ (mach_pmap_init (&pmap, &format, &fake_ops, NULL), MACH_OK); + + CHECK_EQ (mach_pmap_map (&pmap, 0x40000000u, 0x120000u, MACH_PAGE_SIZE, + MACH_VM_PROT_READ | MACH_VM_PROT_USER), MACH_OK); + CHECK_EQ (mach_pmap_translate (&pmap, 0x40000000u, &translated, &protection), + MACH_OK); + CHECK_EQ (translated, 0x120000u); + CHECK ((protection & MACH_VM_PROT_READ) != 0); + CHECK ((protection & MACH_VM_PROT_WRITE) == 0); + CHECK ((protection & MACH_VM_PROT_USER) != 0); +} + +static void +test_numa (void) +{ + struct mach_numa_region regions[2] = + { + { .node = 0, .base = NODE0_BASE, .nr_pages = NODE0_PAGES }, + { .node = 1, .base = NODE1_BASE, .nr_pages = NODE1_PAGES } + }; + uint8_t distances[4] = { 10, 20, 20, 10 }; + struct mach_vm_phys physical; + mach_phys_t address; + uint64_t free_before; + + CHECK_EQ (mach_vm_phys_init (&physical, regions, 2, page_storage, + NODE0_PAGES * 2, distances, &fake_ops, NULL), + MACH_OK); + CHECK_EQ (mach_vm_free_page_count (&physical), + (uint64_t) NODE0_PAGES + NODE1_PAGES); + + address = mach_vm_alloc_pages (&physical, 1, 1); + CHECK (address >= NODE1_BASE && address < NODE1_BASE + NODE1_PAGES * 4096); + CHECK_EQ (mach_vm_free_pages (&physical, address, 1), MACH_OK); + CHECK_EQ (mach_vm_free_page_count (&physical), + (uint64_t) NODE0_PAGES + NODE1_PAGES); + + address = mach_vm_alloc_pages (&physical, 8, 0); + CHECK (address != MACH_PHYS_NULL); + CHECK_EQ (address & (8u * 4096u - 1u), 0); + CHECK_EQ (mach_vm_free_page_count (&physical), + (uint64_t) NODE0_PAGES + NODE1_PAGES - 8); + CHECK_EQ (mach_vm_free_pages (&physical, address, 8), MACH_OK); + + /* Allocation falls back to the other node when the first is full. */ + free_before = mach_vm_free_page_count_node (&physical, 0); + CHECK_EQ (free_before, (uint64_t) NODE0_PAGES); + address = mach_vm_alloc_pages (&physical, (uint32_t) free_before, 0); + CHECK (address != MACH_PHYS_NULL); + CHECK_EQ (mach_vm_free_page_count_node (&physical, 0), 0); + CHECK_EQ (mach_vm_free_pages (&physical, address, (uint32_t) free_before), + MACH_OK); + + /* Exhaust the whole machine and check the failure path. */ + { + mach_phys_t blocks[64]; + uint32_t count = 0; + + while (count < 64) + { + blocks[count] = mach_vm_alloc_pages (&physical, 512, -1); + if (blocks[count] == MACH_PHYS_NULL) + break; + count++; + } + + CHECK (mach_vm_alloc_pages (&physical, 1, -1) == MACH_PHYS_NULL); + for (uint32_t index = 0; index < count; index++) + CHECK_EQ (mach_vm_free_pages (&physical, blocks[index], 512), MACH_OK); + } + + CHECK_EQ (mach_vm_free_page_count (&physical), + (uint64_t) NODE0_PAGES + NODE1_PAGES); +} + +static void +test_cow (void) +{ + struct mach_numa_region region = + { .node = 0, .base = NODE0_BASE, .nr_pages = NODE0_PAGES }; + struct mach_vm_phys physical; + struct mach_vm_page storage[NODE0_PAGES]; + struct mach_vm_slot slots[4]; + struct mach_vm_resident residents[4]; + struct mach_vm_slot child_slots[4]; + struct mach_vm_resident child_residents[4]; + struct mach_vm_object object; + struct mach_vm_object child; + struct mach_pmap_format format; + struct mach_vm_map map; + struct mach_vm_map child_map; + mach_phys_t first; + mach_phys_t second; + mach_phys_t translated; + uint64_t free_before; + + CHECK_EQ (mach_vm_phys_init (&physical, ®ion, 1, storage, NODE0_PAGES, + NULL, &fake_ops, NULL), MACH_OK); + CHECK_EQ (mach_vm_object_init (&object, slots, 4, residents, 4, NULL, + 4 * 4096), MACH_OK); + mach_pmap_format_init (&format, MACH_PMAP_X86_64, 4); + + CHECK_EQ (mach_vm_map_init (&map, &object, &physical, &format, &fake_ops, + NULL, MACH_VM_PROT_READ | MACH_VM_PROT_WRITE), + MACH_OK); + CHECK_EQ (mach_vm_map_init (&child_map, &object, &physical, &format, + &fake_ops, NULL, + MACH_VM_PROT_READ | MACH_VM_PROT_WRITE), + MACH_OK); + map.base = 0x100000u; + child_map.base = 0x100000u; + + free_before = mach_vm_free_page_count (&physical); + + CHECK_EQ (mach_vm_map_fault (&map, 0x100000u, false, &first), MACH_OK); + CHECK_EQ (mach_vm_free_page_count (&physical), free_before - 1); + arena[first] = 0x41; + + CHECK_EQ (mach_vm_object_fork (&object, &child, child_slots, + child_residents, 4), MACH_OK); + child_map.object = &child; + + CHECK_EQ (mach_vm_map_fault (&child_map, 0x100000u, false, &second), + MACH_OK); + CHECK_EQ (first, second); + CHECK_EQ (mach_refcount_load (&residents[0].refs), 2); + + /* A write in the parent must produce a private copy. */ + CHECK_EQ (mach_vm_map_fault (&map, 0x100000u, true, &second), MACH_OK); + CHECK (second != first); + CHECK_EQ (arena[second], 0x41); + CHECK_EQ (mach_refcount_load (&residents[0].refs), 1); + + arena[second] = 0x42; + CHECK_EQ (arena[first], 0x41); + CHECK_EQ (mach_pmap_translate (&map.pmap, 0x100000u, &translated, NULL), + MACH_OK); + CHECK_EQ (translated, second); + CHECK_EQ (mach_pmap_translate (&child_map.pmap, 0x100000u, &translated, + NULL), MACH_OK); + CHECK_EQ (translated, first); + + mach_vm_slot_release (&map, &object.slots[0]); + mach_vm_slot_release (&child_map, &child.slots[0]); + CHECK_EQ (mach_vm_free_page_count (&physical), free_before); +} + +static void +run_tests (void) +{ + test_pmap_4level (); + test_pmap_5level (); + test_pmap_aarch64 (); + test_numa (); + test_cow (); + CHECK (tlb_flushes > 0); +} + +TEST_MAIN ("vm") -- 2.56.0
