From: Lunaixsky Date: Mon, 9 Dec 2024 03:21:58 +0000 (+0000) Subject: add btrie_map() for allocating free slot, remove isrm X-Git-Url: https://scm.lunaixsky.com/lunaix-os.git/commitdiff_plain/378a473943ba2bfe38c303d198aab41056095b71?ds=inline add btrie_map() for allocating free slot, remove isrm --- diff --git a/lunaix-os/arch/README.md b/lunaix-os/arch/README.md index 68fa2a0..5c49276 100644 --- a/lunaix-os/arch/README.md +++ b/lunaix-os/arch/README.md @@ -60,7 +60,6 @@ Lunaix provide bunch of headers that **MUST** be implemented in order to behave ``` includes/asm/cpu.h -includes/asm-generic/isrm.h includes/asm/muldiv64.h includes/asm/hart.h includes/asm/mempart.h diff --git a/lunaix-os/arch/generic/includes/asm-generic/isrm.h b/lunaix-os/arch/generic/includes/asm-generic/isrm.h deleted file mode 100644 index 5f82aca..0000000 --- a/lunaix-os/arch/generic/includes/asm-generic/isrm.h +++ /dev/null @@ -1,33 +0,0 @@ -/** - * @file irqm.h - * @author Lunaixsky - * @brief ISR Manager, managing the interrupt service routine allocations - * @version 0.1 - * @date 2022-10-18 - * - * @copyright Copyright (c) 2022 - * - */ -#ifndef __LUNAIX_ISRM_H -#define __LUNAIX_ISRM_H - -#include -#include -#include - -#include - -typedef void (*isr_cb)(const struct hart_state*); - -void -isrm_init(); - -/** - * @brief Notify end of interrupt event - * - * @param id - */ -void -isrm_notify_eoi(cpu_t id, int iv); - -#endif /* __LUNAIX_ISRM_H */ diff --git a/lunaix-os/arch/x86/LBuild b/lunaix-os/arch/x86/LBuild index 9ae2145..941453b 100644 --- a/lunaix-os/arch/x86/LBuild +++ b/lunaix-os/arch/x86/LBuild @@ -3,8 +3,6 @@ use("hal") sources([ "exceptions/interrupts.c", "exceptions/isrdef.c", - "exceptions/intr_routines.c", - "exceptions/isrm.c", "exceptions/intrhnds.S", ]) diff --git a/lunaix-os/arch/x86/arch.c b/lunaix-os/arch/x86/arch.c index e98bdd9..1d68e15 100644 --- a/lunaix-os/arch/x86/arch.c +++ b/lunaix-os/arch/x86/arch.c @@ -3,8 +3,6 @@ #include #include -#include - #include "asm/x86.h" #include "asm/hart.h" @@ -14,19 +12,12 @@ void exception_init() { exception_install_handler(); - isrm_init(); - intr_routine_init(); } -extern void -syscall_hndlr(const struct hart_state* hstate); - void arch_preinit() { exception_init(); - - isrm_bindiv(LUNAIX_SYS_CALL, syscall_hndlr); } void diff --git a/lunaix-os/arch/x86/exceptions/interrupts.c b/lunaix-os/arch/x86/exceptions/interrupts.c index ceb3853..9941a5c 100644 --- a/lunaix-os/arch/x86/exceptions/interrupts.c +++ b/lunaix-os/arch/x86/exceptions/interrupts.c @@ -5,11 +5,28 @@ #include #include #include +#include -#include +#include LOG_MODULE("INTR") +extern void +intr_routine_page_fault(const struct hart_state* state); + +extern void +syscall_hndlr(const struct hart_state* hstate); + +extern void +apic_ack_interrupt(irq_t irq); + +static void noret +__set_panic(const char* msg, const struct hart_state* state) +{ + ERROR("panic: %s", msg); + failsafe_diagnostic(); +} + static inline void update_thread_context(struct hart_state* state) { @@ -26,23 +43,83 @@ update_thread_context(struct hart_state* state) } } + +static bool +__handle_internal_vectors(const struct hart_state* state) +{ + switch (hart_vector_stamp(state)) + { + case FAULT_DIVISION_ERROR: + __set_panic("div zero", state); + break; + + case FAULT_GENERAL_PROTECTION: + __set_panic("general protection", state); + break; + + case FAULT_PAGE_FAULT: + intr_routine_page_fault(state); + break; + + case FAULT_INVALID_OPCODE: + __set_panic("invalid opcode", state);; + break; + + case LUNAIX_SCHED: + apic_ack_interrupt(NULL); + schedule(); + break; + + case APIC_SPIV_IV: + break; + + case APIC_ERROR_IV: + __set_panic("apic error", state);; + break; + + case LUNAIX_SYS_CALL: + syscall_hndlr(state); + break; + + default: + return false; + } + + return true; +} + +static bool +__handle_external_irq(const struct hart_state* state) +{ + irq_t irq; + int ex_iv; + + ex_iv = hart_vector_stamp(state); + irq = irq_find(irq_get_default_domain(), ex_iv); + + if (unlikely(!irq)) { + return false; + } + + irq_serve(irq, state); + apic_ack_interrupt(irq); + return true; +} + struct hart_state* intr_handler(struct hart_state* state) { update_thread_context(state); volatile struct exec_param* execp = state->execp; - if (execp->vector <= 255) { - isr_cb subscriber = isrm_get(execp->vector); - subscriber(state); - goto done; + + if (__handle_internal_vectors(state)) { + return state; } -done: - - if (execp->vector > IV_BASE_END) { - isrm_notify_eoi(0, execp->vector); + if (__handle_external_irq(state)) { + return state; } - return state; + __set_panic("unknown interrupt", state); } \ No newline at end of file diff --git a/lunaix-os/arch/x86/exceptions/intr_routines.c b/lunaix-os/arch/x86/exceptions/intr_routines.c deleted file mode 100644 index 9410f76..0000000 --- a/lunaix-os/arch/x86/exceptions/intr_routines.c +++ /dev/null @@ -1,103 +0,0 @@ -#include - -#include -#include -#include -#include -#include -#include - -#include - -#include -#include "asm/soc/apic.h" -#include "asm/x86.h" - -LOG_MODULE("INTR") - -extern void -intr_routine_page_fault(const struct hart_state* state); - -extern u32_t debug_resv; - -void -__print_panic_msg(const char* msg, const struct hart_state* state) -{ - ERROR("panic: %s", msg); - failsafe_diagnostic(); -} - -void -intr_routine_divide_zero(const struct hart_state* state) -{ - __print_panic_msg("div zero", state); -} - -void -intr_routine_general_protection(const struct hart_state* state) -{ - __print_panic_msg("general protection", state); -} - -void -intr_routine_invl_opcode(const struct hart_state* state) -{ - __print_panic_msg("invalid opcode", state); -} - -void -intr_routine_sys_panic(const struct hart_state* state) -{ -#ifdef CONFIG_ARCH_X86_64 - __print_panic_msg((char*)(state->registers.rdi), state); -#else - __print_panic_msg((char*)(state->registers.edi), state); -#endif -} - -void -intr_routine_fallback(const struct hart_state* state) -{ - __print_panic_msg("unknown interrupt", state); -} - -/** - * @brief ISR for Spurious interrupt - * - * @param struct hart_state passed by CPU - */ -void -intr_routine_apic_spi(const struct hart_state* state) -{ - // FUTURE: do nothing for now -} - -void -intr_routine_apic_error(const struct hart_state* state) -{ - ERROR("APIC error"); - failsafe_diagnostic(); -} - -void -intr_routine_sched(const struct hart_state* state) -{ - isrm_notify_eoi(0, LUNAIX_SCHED); - schedule(); -} - -void -intr_routine_init() -{ - isrm_bindiv(FAULT_DIVISION_ERROR, intr_routine_divide_zero); - isrm_bindiv(FAULT_GENERAL_PROTECTION, intr_routine_general_protection); - isrm_bindiv(FAULT_PAGE_FAULT, intr_routine_page_fault); - isrm_bindiv(FAULT_STACK_SEG_FAULT, intr_routine_page_fault); - isrm_bindiv(FAULT_INVALID_OPCODE, intr_routine_invl_opcode); - - isrm_bindiv(LUNAIX_SYS_PANIC, intr_routine_sys_panic); - isrm_bindiv(LUNAIX_SCHED, intr_routine_sched); - - isrm_bindiv(APIC_SPIV_IV, intr_routine_apic_spi); - isrm_bindiv(APIC_ERROR_IV, intr_routine_apic_error); -} \ No newline at end of file diff --git a/lunaix-os/arch/x86/exceptions/isrm.c b/lunaix-os/arch/x86/exceptions/isrm.c deleted file mode 100644 index cd2d81b..0000000 --- a/lunaix-os/arch/x86/exceptions/isrm.c +++ /dev/null @@ -1,129 +0,0 @@ -#include -#include - -#include "asm/x86.h" -#include "asm/soc/apic.h" - -/* - total: 256 ivs - 0~31: reserved for sys use (x32) - 32~47: reserved for os use (x16) - 48~ : free to allocate for external hardware use. (x208) -*/ - -static char iv_bmp[(IV_EX_END - IV_BASE_END) / 8]; -static isr_cb handlers[TOTAL_IV]; -static ptr_t ivhand_payload[TOTAL_IV]; - -extern void -intr_routine_fallback(const struct hart_state* state); - -void -isrm_init() -{ - for (size_t i = 0; i < TOTAL_IV; i++) { - handlers[i] = intr_routine_fallback; - } -} - -static inline int -__ivalloc_within(size_t a, size_t b, isr_cb handler) -{ - a = (a - IV_BASE_END); - b = (b - IV_BASE_END); - u8_t j = a % 8; - u8_t k = 0; - - for (size_t i = a / 8; i < b / 8; i++, k += 8) { - u8_t chunk = iv_bmp[i]; - - if (chunk == 0xff) - continue; - - chunk >>= j; - while ((chunk & 0x1) && k <= b) { - chunk >>= 1; - j++; - k++; - } - - if (j == 8) { - j = 0; - continue; - } - - if (k > b) { - break; - } - - iv_bmp[i] |= 1 << j; - - int iv = IV_BASE_END + i * 8 + j; - handlers[iv] = handler ? handler : intr_routine_fallback; - - return iv; - } - - return 0; -} - -int -isrm_ivosalloc(isr_cb handler) -{ - return __ivalloc_within(IV_BASE_END, IV_EX_BEGIN, handler); -} - -int -isrm_ivexalloc(isr_cb handler) -{ - return __ivalloc_within(IV_EX_BEGIN, IV_EX_END, handler); -} - -void -isrm_ivfree(int iv) -{ - assert(iv < 256); - - if (iv >= IV_BASE_END) { - iv_bmp[(iv - IV_BASE_END) / 8] &= ~(1 << ((iv - IV_BASE_END) % 8)); - } - - handlers[iv] = intr_routine_fallback; -} - -void -isrm_bindiv(int iv, isr_cb handler) -{ - assert(iv < 256); - - if (iv >= IV_BASE_END) { - iv_bmp[(iv - IV_BASE_END) / 8] |= 1 << ((iv - IV_BASE_END) % 8); - } - - handlers[iv] = handler; -} - -isr_cb -isrm_get(int iv) -{ - assert(iv < 256); - - return handlers[iv]; -} - -ptr_t -isrm_get_payload(const struct hart_state* state) -{ - int iv = state->execp->vector; - assert(iv < 256); - - return ivhand_payload[iv]; -} - -void -isrm_set_payload(int iv, ptr_t payload) -{ - assert(iv < 256); - - ivhand_payload[iv] = payload; -} \ No newline at end of file diff --git a/lunaix-os/arch/x86/hal/apic.c b/lunaix-os/arch/x86/hal/apic.c index cd03096..8e9a013 100644 --- a/lunaix-os/arch/x86/hal/apic.c +++ b/lunaix-os/arch/x86/hal/apic.c @@ -14,7 +14,6 @@ #include "asm/soc/apic.h" #include -#include #include #include @@ -70,13 +69,9 @@ apic_write_reg(unsigned int reg, unsigned int val) } void -isrm_notify_eoi(cpu_t id, int iv) +apic_ack_interrupt(irq_t irq) { - // for all external interrupts except the spurious interrupt - // this is required by Intel Manual Vol.3A, section 10.8.1 & 10.8.5 - if (iv >= IV_EX_BEGIN && iv != APIC_SPIV_IV) { - *(unsigned int*)(_apic_base + APIC_EOI) = 0; - } + *(unsigned int*)(_apic_base + APIC_EOI) = 0; } unsigned int @@ -205,21 +200,15 @@ __ioapic_translate_irq(struct irq_domain *domain, irq_t irq, void *irq_extra) return 0; } -static void -__external_irq_dispatch(const struct hart_state* state) -{ - irq_t irq; - - irq = irq_find(irq_get_default_domain(), hart_vector_stamp(state)); - - assert(irq); - irq_serve(irq, state); -} - static int __ioapic_install_irq(struct irq_domain *domain, irq_t irq) { - irq->vector = isrm_ivexalloc(__external_irq_dispatch); + if (irq->vector == IRQ_VECTOR_UNSET) { + irq->vector = btrie_map(&domain->irq_map, IV_EX_BEGIN, IV_EX_END, irq); + } + else { + irq_record(domain, irq); + } if (irq->type == IRQ_MESSAGE) { irq->msi->wr_addr = __APIC_BASE_PADDR; @@ -228,8 +217,6 @@ __ioapic_install_irq(struct irq_domain *domain, irq_t irq) __ioapic_install_line(domain, irq); } - irq_record(domain, irq); - return 0; } diff --git a/lunaix-os/arch/x86/hal/apic_timer.c b/lunaix-os/arch/x86/hal/apic_timer.c index 816fde3..9a42e82 100644 --- a/lunaix-os/arch/x86/hal/apic_timer.c +++ b/lunaix-os/arch/x86/hal/apic_timer.c @@ -1,12 +1,12 @@ #include "apic_timer.h" #include +#include #include #include #include #include -#include #include "asm/soc/apic.h" LOG_MODULE("timer(apic)") @@ -15,20 +15,20 @@ LOG_MODULE("timer(apic)") #define APIC_BASETICKS 0x100000 static void -temp_intr_routine_apic_timer(const struct hart_state* state) +apic_timer_count_stop(irq_t irq, const struct hart_state* state) { struct hwtimer_pot* pot; - pot = (struct hwtimer_pot*)isrm_get_payload(state); + pot = irq_payload(irq, struct hwtimer_pot); pot->systick_raw = (ticks_t)-1; } static void -apic_timer_tick_isr(const struct hart_state* state) +apic_timer_tick_isr(irq_t irq, const struct hart_state* state) { struct hwtimer_pot* pot; - pot = (struct hwtimer_pot*)isrm_get_payload(state); + pot = irq_payload(irq, struct hwtimer_pot); pot->systick_raw++; if (likely(__ptr(pot->callback))) { @@ -39,20 +39,19 @@ apic_timer_tick_isr(const struct hart_state* state) static void __apic_timer_calibrate(struct hwtimer_pot* pot, u32_t hertz) { + irq_t irq; ticks_t base_freq = 0; cpu_disable_interrupt(); - // Setup APIC timer - - // grab ourselves these irq numbers - u32_t iv_timer = isrm_ivexalloc(temp_intr_routine_apic_timer); - isrm_set_payload(iv_timer, __ptr(pot)); + irq = irq_declare_direct(apic_timer_count_stop); + irq_set_payload(irq, pot); + irq_assign(irq_get_default_domain(), irq); // Setup a one-shot timer, we will use this to measure the bus speed. So we // can then calibrate apic timer to work at *nearly* accurate hz apic_write_reg(APIC_TIMER_LVT, - LVT_ENTRY_TIMER(iv_timer, LVT_TIMER_ONESHOT)); + LVT_ENTRY_TIMER(irq->vector, LVT_TIMER_ONESHOT)); // Set divider to 64 apic_write_reg(APIC_TIMER_DCR, APIC_TIMER_DIV64); @@ -89,7 +88,6 @@ __apic_timer_calibrate(struct hwtimer_pot* pot, u32_t hertz) wait_until(!(pot->systick_raw + 1)); cpu_disable_interrupt(); - isrm_ivfree(iv_timer); sysrtc->ops->set_proactive(sysrtc, false); @@ -101,14 +99,12 @@ __apic_timer_calibrate(struct hwtimer_pot* pot, u32_t hertz) assert_msg(base_freq, "Fail to initialize timer (NOFREQ)"); INFO("hw: %u Hz; os: %u Hz", base_freq, hertz); + irq_set_servant(irq, apic_timer_tick_isr); + apic_write_reg(APIC_TIMER_ICR, base_freq / hertz); - - iv_timer = isrm_ivexalloc(apic_timer_tick_isr); - isrm_set_payload(iv_timer, __ptr(pot)); - apic_write_reg( APIC_TIMER_LVT, - LVT_ENTRY_TIMER(iv_timer, LVT_TIMER_PERIODIC)); + LVT_ENTRY_TIMER(irq->vector, LVT_TIMER_PERIODIC)); } static struct hwtimer_pot_ops potops = { diff --git a/lunaix-os/arch/x86/hal/mc146818a.c b/lunaix-os/arch/x86/hal/mc146818a.c index ec2cd4b..d6d931d 100644 --- a/lunaix-os/arch/x86/hal/mc146818a.c +++ b/lunaix-os/arch/x86/hal/mc146818a.c @@ -19,7 +19,6 @@ #include -#include #include #define RTC_INDEX_PORT 0x70 diff --git a/lunaix-os/arch/x86/hal/ps2kbd.c b/lunaix-os/arch/x86/hal/ps2kbd.c index 8799da2..4460291 100644 --- a/lunaix-os/arch/x86/hal/ps2kbd.c +++ b/lunaix-os/arch/x86/hal/ps2kbd.c @@ -13,7 +13,6 @@ #include #include "asm/x86_cpu.h" -#include #include #define PS2_PORT_ENC_DATA 0x60 diff --git a/lunaix-os/arch/x86/includes/asm/x86.h b/lunaix-os/arch/x86/includes/asm/x86.h index 33515a1..8f1e3d0 100644 --- a/lunaix-os/arch/x86/includes/asm/x86.h +++ b/lunaix-os/arch/x86/includes/asm/x86.h @@ -95,8 +95,5 @@ typedef struct x86_sysdesc x86_segdesc_t; void exception_install_handler(); -void -intr_routine_init(); - #endif #endif /* __LUNAIX_I386_ASM_H */ diff --git a/lunaix-os/arch/x86/includes/asm/x86_isrm.h b/lunaix-os/arch/x86/includes/asm/x86_isrm.h deleted file mode 100644 index 4d6fb44..0000000 --- a/lunaix-os/arch/x86/includes/asm/x86_isrm.h +++ /dev/null @@ -1,58 +0,0 @@ -#ifndef __LUNAIX_X86_ISRM_H -#define __LUNAIX_X86_ISRM_H - -#include - -/** - * @brief Bind given iv with it's associated handler - * - * @param iv - * @param handler - */ -void -isrm_bindiv(int iv, isr_cb handler); - -void -isrm_irq_attach(int irq, int iv, cpu_t dest, u32_t flags); - -/** - * @brief Allocate an iv resource for os services - * - * @param iv - */ -int -isrm_ivosalloc(isr_cb handler); - -/** - * @brief Allocate an iv resource for external events - * - * @param iv - */ -int -isrm_ivexalloc(isr_cb handler); - -/** - * @brief Release a iv resource - * - * @param iv - */ -void -isrm_ivfree(int iv); - -/** - * @brief Get the handler associated with the given iv - * - * @param iv - * @return isr_cb - */ -isr_cb -isrm_get(int iv); - -ptr_t -isrm_get_payload(const struct hart_state*); - -void -isrm_set_payload(int iv, ptr_t); - - -#endif /* __LUNAIX_X86_ISRM_H */ diff --git a/lunaix-os/arch/x86/includes/asm/x86_ivs.h b/lunaix-os/arch/x86/includes/asm/x86_ivs.h index 0a5eed2..0dbe921 100644 --- a/lunaix-os/arch/x86/includes/asm/x86_ivs.h +++ b/lunaix-os/arch/x86/includes/asm/x86_ivs.h @@ -33,11 +33,11 @@ #define LUNAIX_SYS_CALL 33 // begin allocatable iv resources -#define IV_EX_BEGIN 50 #define LUNAIX_SCHED 50 +#define IV_EX_BEGIN 51 // end allocatable iv resources -#define IV_EX_END 249 +#define IV_EX_END 249 // 来自APIC的中断有着最高的优先级。 // APIC related diff --git a/lunaix-os/hal/ahci/ahci.c b/lunaix-os/hal/ahci/ahci.c index 7d0b9b2..5ff1cc2 100644 --- a/lunaix-os/hal/ahci/ahci.c +++ b/lunaix-os/hal/ahci/ahci.c @@ -18,7 +18,6 @@ #include #include -#include #include #include #include diff --git a/lunaix-os/hal/ahci/io_event.c b/lunaix-os/hal/ahci/io_event.c index c40a85c..b751cdc 100644 --- a/lunaix-os/hal/ahci/io_event.c +++ b/lunaix-os/hal/ahci/io_event.c @@ -1,6 +1,5 @@ #include #include -#include #include #include diff --git a/lunaix-os/hal/char/uart/16x50_isa.c b/lunaix-os/hal/char/uart/16x50_isa.c index c24c1d0..7c82367 100644 --- a/lunaix-os/hal/char/uart/16x50_isa.c +++ b/lunaix-os/hal/char/uart/16x50_isa.c @@ -2,7 +2,6 @@ #include #include -#include #include "16x50.h" diff --git a/lunaix-os/hal/char/uart/16x50_mmio.c b/lunaix-os/hal/char/uart/16x50_mmio.c index e211625..4762ef1 100644 --- a/lunaix-os/hal/char/uart/16x50_mmio.c +++ b/lunaix-os/hal/char/uart/16x50_mmio.c @@ -1,5 +1,4 @@ #include -#include #include #include "16x50.h" diff --git a/lunaix-os/hal/char/uart/16x50_pci.c b/lunaix-os/hal/char/uart/16x50_pci.c index 9de2396..43e5326 100644 --- a/lunaix-os/hal/char/uart/16x50_pci.c +++ b/lunaix-os/hal/char/uart/16x50_pci.c @@ -1,5 +1,4 @@ #include -#include #include #include diff --git a/lunaix-os/hal/char/uart/16x50_pmio.c b/lunaix-os/hal/char/uart/16x50_pmio.c index ea550cb..3b97105 100644 --- a/lunaix-os/hal/char/uart/16x50_pmio.c +++ b/lunaix-os/hal/char/uart/16x50_pmio.c @@ -9,7 +9,6 @@ * */ #include -#include #include diff --git a/lunaix-os/hal/irq.c b/lunaix-os/hal/irq.c index b4bc0ec..97bbb79 100644 --- a/lunaix-os/hal/irq.c +++ b/lunaix-os/hal/irq.c @@ -93,7 +93,8 @@ irq_declare(enum irq_type type, irq_servant callback, *irq = (struct irq_object) { .type = type, .serve = callback ?: __default_servant, - .irq_extra = irq_extra + .irq_extra = irq_extra, + .vector = IRQ_VECTOR_UNSET }; if (type == IRQ_LINE) { diff --git a/lunaix-os/includes/hal/ahci/ahci.h b/lunaix-os/includes/hal/ahci/ahci.h index b55ba95..9cf80fc 100644 --- a/lunaix-os/includes/hal/ahci/ahci.h +++ b/lunaix-os/includes/hal/ahci/ahci.h @@ -2,7 +2,6 @@ #define __LUNAIX_AHCI_H #include "hba.h" -#include #include /* diff --git a/lunaix-os/includes/hal/irq.h b/lunaix-os/includes/hal/irq.h index e592e22..fc01e94 100644 --- a/lunaix-os/includes/hal/irq.h +++ b/lunaix-os/includes/hal/irq.h @@ -6,6 +6,8 @@ #include #include +#define IRQ_VECTOR_UNSET ((unsigned)-1) + struct irq_domain; typedef struct irq_object* irq_t; typedef void (*irq_servant)(irq_t, const struct hart_state*); @@ -36,6 +38,7 @@ struct irq_domain enum irq_type { + IRQ_DIRECT, IRQ_LINE, IRQ_MESSAGE }; @@ -71,8 +74,6 @@ struct irq_object int ref; }; -#define SZ sizeof(struct irq_object) - struct irq_domain* irq_create_domain(struct device* intc_dev, const struct irq_domain_ops* ops); @@ -112,6 +113,18 @@ irq_serve(irq_t irq, struct hart_state* state) irq->serve(irq, state); } +static inline void +irq_set_servant(irq_t irq, irq_servant callback) +{ + irq->serve = callback; +} + +static inline void +irq_bind_vector(irq_t irq, int vector) +{ + irq->vector = vector; +} + static inline void irq_set_payload(irq_t irq, void* payload) { @@ -144,6 +157,12 @@ irq_declare_msg(irq_servant callback, return irq; } +static inline irq_t +irq_declare_direct(irq_servant callback) +{ + return irq_declare(IRQ_DIRECT, callback, 0, NULL); +} + static inline struct irq_domain* irq_get_domain(struct device* maybe_intc) { diff --git a/lunaix-os/includes/hal/pci.h b/lunaix-os/includes/hal/pci.h index 8c7057a..81853c4 100644 --- a/lunaix-os/includes/hal/pci.h +++ b/lunaix-os/includes/hal/pci.h @@ -8,8 +8,6 @@ #include #include -#include - #include "irq.h" #define PCI_VENDOR_INVLD 0xffff diff --git a/lunaix-os/includes/lunaix/ds/btrie.h b/lunaix-os/includes/lunaix/ds/btrie.h index bcf0250..d24cf84 100644 --- a/lunaix-os/includes/lunaix/ds/btrie.h +++ b/lunaix-os/includes/lunaix/ds/btrie.h @@ -6,6 +6,9 @@ #define BTRIE_BITS 4 +/** + * key-sorted prefix tree + */ struct btrie { struct btrie_node* btrie_root; @@ -14,12 +17,13 @@ struct btrie struct btrie_node { - struct llist_header children; - struct llist_header siblings; struct llist_header nodes; struct btrie_node* parent; unsigned long index; void* data; + + struct btrie_node** children; + int children_cnt; }; void @@ -28,9 +32,21 @@ btrie_init(struct btrie* btrie, unsigned int order); void* btrie_get(struct btrie* root, unsigned long index); +/** + * Set an object into btrie tree at given location, + * override if another object is already present. + */ void btrie_set(struct btrie* root, unsigned long index, void* data); +/** + * Map an object into btrie tree, return the index the object + * mapped to + */ +unsigned long +btrie_map(struct btrie* root, + unsigned long start, unsigned long end, void* data); + void* btrie_remove(struct btrie* root, unsigned long index); diff --git a/lunaix-os/kernel/ds/btrie.c b/lunaix-os/kernel/ds/btrie.c index 72758fb..8cba604 100644 --- a/lunaix-os/kernel/ds/btrie.c +++ b/lunaix-os/kernel/ds/btrie.c @@ -13,75 +13,216 @@ #include #include -#define BTRIE_INSERT 1 +enum btrie_traverse_mode { + BTRIE_FIND, + BTRIE_FIND_PARENT, + BTRIE_INSERT +}; +struct btrie_locator +{ + enum btrie_traverse_mode mode; + int shifts; + unsigned long index; +}; + +static inline void +__btrie_locator(struct btrie_locator* loc, + unsigned long index, enum btrie_traverse_mode mode) +{ + loc->mode = mode; + loc->index = index; +} + +static inline void +__btrie_addchild(struct btrie* root, + struct btrie_node* parent, struct btrie_node* child) +{ + if (unlikely(!parent->children)) { + parent->children = vcalloc(sizeof(parent), 1 << root->order); + } + + parent->children_cnt++; + parent->children[child->index] = child; +} + +static inline struct btrie_node* +__btrie_get_child(struct btrie_node* node, int index) +{ + if (unlikely(!node->children)) { + return NULL; + } + + return node->children[index]; +} + +static inline void +__btrie_free_node(struct btrie_node* node) +{ + vfree_safe(node->children); + vfree(node); +} -struct btrie_node* -__btrie_traversal(struct btrie* root, unsigned long index, int options) +static inline bool +__full_node(struct btrie* root, struct btrie_node* node) { - unsigned long lz; + return node->children_cnt == 1 << root->order; +} + +static inline struct btrie_node* +__btrie_create(struct btrie* root, struct btrie_node* parent, int index) +{ + struct btrie_node* node; + + node = vzalloc(sizeof(struct btrie_node)); + node->index = index; + node->parent = parent; + + if (likely(parent)) { + llist_append(&root->btrie_root->nodes, &node->nodes); + __btrie_addchild(root, parent, node); + } + + return node; +} + +static struct btrie_node* +__btrie_traversal(struct btrie* root, struct btrie_locator* locator) +{ + unsigned long lz, index; unsigned long bitmask; unsigned long i = 0; - struct btrie_node* tree = root->btrie_root; + struct btrie_node *subtree, *tree = root->btrie_root; - lz = index ? ICEIL(msbitl - clzl(index), root->order) : 0; + index = locator->index; + lz = index ? (msbitl - clzl(index)) / root->order : 0; lz = lz * root->order; bitmask = ((1 << root->order) - 1) << lz; // Time complexity: O(log_2(log_2(N))) where N is the index to lookup while (bitmask && tree) { i = (index & bitmask) >> lz; - struct btrie_node *subtree = 0, *pos, *n; + subtree = __btrie_get_child(tree, i); - llist_for_each(pos, n, &tree->children, siblings) + if (!subtree && (locator->mode != BTRIE_FIND)) { - if (pos->index == i) { - subtree = pos; - break; - } + tree = __btrie_create(root, tree, i); } - - if (!subtree && (options & BTRIE_INSERT)) { - struct btrie_node* new_tree = vzalloc(sizeof(struct btrie_node)); - new_tree->index = i; - new_tree->parent = tree; - llist_init_head(&new_tree->children); - - llist_append(&tree->children, &new_tree->siblings); - llist_append(&root->btrie_root->nodes, &new_tree->nodes); - tree = new_tree; - } else { + else { tree = subtree; } + + if (lz == root->order && locator->mode == BTRIE_FIND_PARENT) + { + break; + } + bitmask = bitmask >> root->order; lz -= root->order; } + locator->shifts = lz; return tree; } +static unsigned long +__btrie_alloc_slot(struct btrie* root, struct btrie_node **slot, + unsigned long start, unsigned long end) +{ + unsigned int index, od; + unsigned long result, mask, result_next; + struct btrie_node *tree, *subtree; + struct btrie_locator locator; + + result = 0; + od = root->order; + mask = (1 << od) - 1; + tree = root->btrie_root; + + if (start) { + __btrie_locator(&locator, start, BTRIE_FIND_PARENT); + tree = __btrie_traversal(root, &locator); + result = start; + } + + while (tree && result < end) + { + index = result & mask; + result_next = result << od; + + subtree = __btrie_get_child(tree, index); + + if (subtree) { + if (result >= start && !subtree->data) { + tree = subtree; + goto done; + } + } + else { + subtree = __btrie_create(root, tree, index); + + if (result >= start) + goto done; + + goto descend; + } + + if (!__full_node(root, tree) && index != mask) { + result++; + continue; + } + +descend: + if (result_next >= end) { + tree = tree->parent; + result >>= od; + result++; + continue; + } + + tree = subtree; + result = result_next; + } + + *slot = NULL; + return -1; + +done: + *slot = subtree; + return result; +} + void btrie_init(struct btrie* btrie, unsigned int order) { - btrie->btrie_root = vzalloc(sizeof(struct btrie_node)); - llist_init_head(&btrie->btrie_root->nodes); - llist_init_head(&btrie->btrie_root->children); + btrie->btrie_root = __btrie_create(btrie, NULL, 0); btrie->order = order; + + llist_init_head(&btrie->btrie_root->nodes); } void* btrie_get(struct btrie* root, unsigned long index) { - struct btrie_node* node = __btrie_traversal(root, index, 0); + struct btrie_node* node; + struct btrie_locator locator; + + __btrie_locator(&locator, index, BTRIE_FIND); + node = __btrie_traversal(root, &locator); if (!node) { return NULL; } + return node->data; } void btrie_set(struct btrie* root, unsigned long index, void* data) { - struct btrie_node* node = __btrie_traversal(root, index, BTRIE_INSERT); + struct btrie_node* node; + struct btrie_locator locator; + + __btrie_locator(&locator, index, BTRIE_INSERT); + node = __btrie_traversal(root, &locator); node->data = data; } @@ -90,29 +231,55 @@ __btrie_rm_recursive(struct btrie_node* node) { struct btrie_node* parent = node->parent; - if (parent) { - llist_delete(&node->siblings); - llist_delete(&node->nodes); - vfree(node); - if (llist_empty(&parent->children) && !parent->data) { - __btrie_rm_recursive(parent); - } + if (!parent) { + return; + } + + parent->children[node->index] = NULL; + parent->children_cnt--; + __btrie_free_node(node); + + if (!parent->children_cnt && !parent->data) { + __btrie_rm_recursive(parent); } } +unsigned long +btrie_map(struct btrie* root, + unsigned long start, unsigned long end, void* data) +{ + struct btrie_node* node = NULL; + unsigned long alloced; + + alloced = __btrie_alloc_slot(root, &node, start, end); + + if (!node) + return -1; + + node->data = data; + return alloced; +} + void* btrie_remove(struct btrie* root, unsigned long index) { - struct btrie_node* node = __btrie_traversal(root, index, 0); + void* data; + struct btrie_node* node; + struct btrie_locator locator; + + __btrie_locator(&locator, index, BTRIE_FIND); + node = __btrie_traversal(root, &locator); if (!node) { return 0; } - void* data = node->data; - if (!llist_empty(&node->children)) { + + data = node->data; + if (!node->children_cnt) { node->data = NULL; } else { __btrie_rm_recursive(node); } + return data; } @@ -122,8 +289,8 @@ btrie_release(struct btrie* tree) struct btrie_node *pos, *n; llist_for_each(pos, n, &tree->btrie_root->nodes, nodes) { - vfree(pos); + __btrie_free_node(pos); } - vfree(tree->btrie_root); + __btrie_free_node(tree->btrie_root); } \ No newline at end of file diff --git a/lunaix-os/kernel/process/sched.c b/lunaix-os/kernel/process/sched.c index a154b0d..e9f61b3 100644 --- a/lunaix-os/kernel/process/sched.c +++ b/lunaix-os/kernel/process/sched.c @@ -20,8 +20,6 @@ #include #include -#include - #include struct thread empty_thread_obj;