```
includes/asm/cpu.h
-includes/asm-generic/isrm.h
includes/asm/muldiv64.h
includes/asm/hart.h
includes/asm/mempart.h
+++ /dev/null
-/**
- * @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 <lunaix/types.h>
-#include <lunaix/hart_state.h>
-#include <lunaix/device.h>
-
-#include <hal/devtree.h>
-
-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 */
sources([
"exceptions/interrupts.c",
"exceptions/isrdef.c",
- "exceptions/intr_routines.c",
- "exceptions/isrm.c",
"exceptions/intrhnds.S",
])
#include <lunaix/spike.h>
#include <lunaix/process.h>
-#include <asm/x86_isrm.h>
-
#include "asm/x86.h"
#include "asm/hart.h"
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
#include <lunaix/process.h>
#include <lunaix/sched.h>
#include <lunaix/syslog.h>
+#include <lunaix/failsafe.h>
-#include <asm/x86_isrm.h>
+#include <hal/irq.h>
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)
{
}
}
+
+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
+++ /dev/null
-#include <asm/hart.h>
-
-#include <lunaix/process.h>
-#include <lunaix/sched.h>
-#include <lunaix/spike.h>
-#include <lunaix/syslog.h>
-#include <lunaix/trace.h>
-#include <lunaix/failsafe.h>
-
-#include <klibc/strfmt.h>
-
-#include <asm/x86_isrm.h>
-#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
+++ /dev/null
-#include <lunaix/spike.h>
-#include <asm/x86_isrm.h>
-
-#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
#include "asm/soc/apic.h"
#include <asm/hart.h>
-#include <asm/x86_isrm.h>
#include <lunaix/mm/mmio.h>
#include <lunaix/spike.h>
}
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
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;
__ioapic_install_line(domain, irq);
}
- irq_record(domain, irq);
-
return 0;
}
#include "apic_timer.h"
#include <hal/hwtimer.h>
+#include <hal/irq.h>
#include <lunaix/clock.h>
#include <lunaix/compiler.h>
#include <lunaix/spike.h>
#include <lunaix/syslog.h>
-#include <asm/x86_isrm.h>
#include "asm/soc/apic.h"
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))) {
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);
wait_until(!(pot->systick_raw + 1));
cpu_disable_interrupt();
- isrm_ivfree(iv_timer);
sysrtc->ops->set_proactive(sysrtc, false);
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 = {
#include <klibc/string.h>
-#include <asm/x86_isrm.h>
#include <asm/x86_pmio.h>
#define RTC_INDEX_PORT 0x70
#include <klibc/string.h>
#include "asm/x86_cpu.h"
-#include <asm/x86_isrm.h>
#include <asm/x86_pmio.h>
#define PS2_PORT_ENC_DATA 0x60
void
exception_install_handler();
-void
-intr_routine_init();
-
#endif
#endif /* __LUNAIX_I386_ASM_H */
+++ /dev/null
-#ifndef __LUNAIX_X86_ISRM_H
-#define __LUNAIX_X86_ISRM_H
-
-#include <asm-generic/isrm.h>
-
-/**
- * @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 */
#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
#include <klibc/string.h>
#include <lunaix/block.h>
-#include <asm-generic/isrm.h>
#include <lunaix/mm/mmio.h>
#include <lunaix/mm/valloc.h>
#include <lunaix/mm/page.h>
#include <hal/ahci/ahci.h>
#include <hal/ahci/sata.h>
-#include <asm-generic/isrm.h>
#include <lunaix/mm/valloc.h>
#include <lunaix/syslog.h>
#include <lunaix/syslog.h>
#include <asm/x86_pmio.h>
-#include <asm/x86_isrm.h>
#include "16x50.h"
#include <lunaix/device.h>
-#include <asm-generic/isrm.h>
#include <lunaix/mm/mmio.h>
#include "16x50.h"
#include <lunaix/device.h>
-#include <asm-generic/isrm.h>
#include <lunaix/syslog.h>
#include <lunaix/mm/mmio.h>
*
*/
#include <lunaix/device.h>
-#include <asm-generic/isrm.h>
#include <asm/x86_pmio.h>
*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) {
#define __LUNAIX_AHCI_H
#include "hba.h"
-#include <asm-generic/isrm.h>
#include <hal/irq.h>
/*
#include <lunaix/ds/btrie.h>
#include <asm/hart.h>
+#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*);
enum irq_type
{
+ IRQ_DIRECT,
IRQ_LINE,
IRQ_MESSAGE
};
int ref;
};
-#define SZ sizeof(struct irq_object)
-
struct irq_domain*
irq_create_domain(struct device* intc_dev, const struct irq_domain_ops* ops);
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)
{
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)
{
#include <lunaix/types.h>
#include <lunaix/changeling.h>
-#include <asm-generic/isrm.h>
-
#include "irq.h"
#define PCI_VENDOR_INVLD 0xffff
#define BTRIE_BITS 4
+/**
+ * key-sorted prefix tree
+ */
struct btrie
{
struct btrie_node* btrie_root;
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
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);
#include <lunaix/mm/valloc.h>
#include <lunaix/spike.h>
-#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;
}
{
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;
}
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
#include <lunaix/hart_state.h>
#include <lunaix/kpreempt.h>
-#include <asm-generic/isrm.h>
-
#include <klibc/string.h>
struct thread empty_thread_obj;
git://scm.lunaixsky.com / lunaix-os.git / commitdiff