Index: kernel/arch/sparc64/src/drivers/niagara.c =================================================================== --- kernel/arch/sparc64/src/drivers/niagara.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/arch/sparc64/src/drivers/niagara.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -221,4 +221,5 @@ INPUT_BUFFER_SIZE); + ddi_parea_init(&outbuf_parea); outbuf_parea.pbase = (uintptr_t) (KA2PA(&output_buffer)); outbuf_parea.frames = 1; Index: kernel/genarch/src/drivers/dsrln/dsrlnout.c =================================================================== --- kernel/genarch/src/drivers/dsrln/dsrlnout.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/genarch/src/drivers/dsrln/dsrlnout.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -84,5 +84,5 @@ instance->base = base; - link_initialize(&instance->parea.link); + ddi_parea_init(&instance->parea); instance->parea.pbase = KA2PA(base); instance->parea.frames = 1; Index: kernel/genarch/src/drivers/ega/ega.c =================================================================== --- kernel/genarch/src/drivers/ega/ega.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/genarch/src/drivers/ega/ega.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -616,5 +616,5 @@ } - link_initialize(&instance->parea.link); + ddi_parea_init(&instance->parea); instance->parea.pbase = addr; instance->parea.frames = SIZE2FRAMES(EGA_VRAM_SIZE); Index: kernel/genarch/src/drivers/ns16550/ns16550.c =================================================================== --- kernel/genarch/src/drivers/ns16550/ns16550.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/genarch/src/drivers/ns16550/ns16550.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -175,4 +175,5 @@ instance->irq.cir_arg = cir_arg; + ddi_parea_init(&instance->parea); instance->parea.pbase = (uintptr_t) dev; instance->parea.frames = 1; Index: kernel/genarch/src/drivers/s3c24xx/uart.c =================================================================== --- kernel/genarch/src/drivers/s3c24xx/uart.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/genarch/src/drivers/s3c24xx/uart.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -135,5 +135,5 @@ pio_read_32(&uart->io->ucon) & ~UCON_RX_INT_LEVEL); - link_initialize(&uart->parea.link); + ddi_parea_init(&uart->parea); uart->parea.pbase = paddr; uart->parea.frames = 1; Index: kernel/genarch/src/fb/fb.c =================================================================== --- kernel/genarch/src/fb/fb.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/genarch/src/fb/fb.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -647,5 +647,5 @@ glyphs_render(instance); - link_initialize(&instance->parea.link); + ddi_parea_init(&instance->parea); instance->parea.pbase = props->addr; instance->parea.frames = SIZE2FRAMES(fbsize); Index: kernel/generic/include/ddi/ddi.h =================================================================== --- kernel/generic/include/ddi/ddi.h (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/generic/include/ddi/ddi.h (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -39,10 +39,10 @@ #include #include -#include +#include /** Structure representing contiguous physical memory area. */ typedef struct { - /** Linked list link */ - link_t link; + /** Link to @c pareas ordered dictionary */ + odlink_t lpareas; /** Physical base of the area. */ @@ -57,4 +57,5 @@ extern void ddi_init(void); +extern void ddi_parea_init(parea_t *); extern void ddi_parea_register(parea_t *); Index: kernel/generic/include/proc/task.h =================================================================== --- kernel/generic/include/proc/task.h (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/generic/include/proc/task.h (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -44,5 +44,4 @@ #include #include -#include #include #include Index: kernel/generic/src/console/console.c =================================================================== --- kernel/generic/src/console/console.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/generic/src/console/console.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -193,4 +193,5 @@ assert((uintptr_t) faddr % FRAME_SIZE == 0); + ddi_parea_init(&kio_parea); kio_parea.pbase = (uintptr_t) faddr; kio_parea.frames = SIZE2FRAMES(sizeof(kio)); Index: kernel/generic/src/ddi/ddi.c =================================================================== --- kernel/generic/src/ddi/ddi.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/generic/src/ddi/ddi.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -49,16 +49,20 @@ #include #include -#include +#include #include #include #include +#include #include #include -/** This lock protects the parea_btree. */ -static mutex_t parea_lock; - -/** B+tree with enabled physical memory areas. */ -static btree_t parea_btree; +/** This lock protects the @c pareas ordered dictionary. */ +static mutex_t pareas_lock; + +/** Ordered dictionary of enabled physical memory areas by base address. */ +static odict_t pareas; + +static void *pareas_getkey(odlink_t *); +static int pareas_cmp(void *, void *); /** Initialize DDI. @@ -67,6 +71,19 @@ void ddi_init(void) { - btree_create(&parea_btree); - mutex_initialize(&parea_lock, MUTEX_PASSIVE); + odict_initialize(&pareas, pareas_getkey, pareas_cmp); + mutex_initialize(&pareas_lock, MUTEX_PASSIVE); +} + +/** Initialize physical area structure. + * + * This should always be called first on the parea structure before + * filling in fields and calling ddi_parea_register. + * + * @param parea Pointer to physical area structure. + * + */ +void ddi_parea_init(parea_t *parea) +{ + memset(parea, 0, sizeof(parea_t)); } @@ -78,12 +95,12 @@ void ddi_parea_register(parea_t *parea) { - mutex_lock(&parea_lock); + mutex_lock(&pareas_lock); /* * We don't check for overlaps here as the kernel is pretty sane. */ - btree_insert(&parea_btree, (btree_key_t) parea->pbase, parea, NULL); - - mutex_unlock(&parea_lock); + odict_insert(&parea->lpareas, &pareas, NULL); + + mutex_unlock(&pareas_lock); } @@ -129,12 +146,12 @@ */ - mutex_lock(&parea_lock); - btree_node_t *nodep; - parea_t *parea = (parea_t *) btree_search(&parea_btree, - (btree_key_t) phys, &nodep); + mutex_lock(&pareas_lock); + odlink_t *odlink = odict_find_eq(&pareas, &phys, NULL); + parea_t *parea = odlink != NULL ? + odict_get_instance(odlink, parea_t, lpareas) : NULL; if ((parea != NULL) && (parea->frames >= pages)) { if ((!priv) && (!parea->unpriv)) { - mutex_unlock(&parea_lock); + mutex_unlock(&pareas_lock); return EPERM; } @@ -144,5 +161,5 @@ parea = NULL; - mutex_unlock(&parea_lock); + mutex_unlock(&pareas_lock); /* @@ -193,5 +210,5 @@ if (parea != NULL) - mutex_unlock(&parea_lock); + mutex_unlock(&pareas_lock); return ENOMEM; @@ -204,5 +221,5 @@ if (parea != NULL) { parea->mapped = true; - mutex_unlock(&parea_lock); + mutex_unlock(&pareas_lock); } @@ -255,4 +272,34 @@ } +/** Get key function for the @c pareas ordered dictionary. + * + * @param odlink Link + * @return Pointer to base address cast as 'void *' + */ +static void *pareas_getkey(odlink_t *odlink) +{ + parea_t *parea = odict_get_instance(odlink, parea_t, lpareas); + return (void *) &parea->pbase; +} + +/** Key comparison function for the @c pareas ordered dictionary. + * + * @param a Pointer to parea A base + * @param b Pointer to parea B base + * @return -1, 0, 1 iff base of A is less than, equal to, greater than B + */ +static int pareas_cmp(void *a, void *b) +{ + uintptr_t pa = *(uintptr_t *)a; + uintptr_t pb = *(uintptr_t *)b; + + if (pa < pb) + return -1; + else if (pa == pb) + return 0; + else + return +1; +} + /** Enable range of I/O space for task. * @@ -288,5 +335,5 @@ } - /* Lock the task and release the lock protecting tasks_btree. */ + /* Lock the task and release the lock protecting tasks dictionary. */ irq_spinlock_exchange(&tasks_lock, &task->lock); errno_t rc = ddi_iospace_enable_arch(task, ioaddr, size); @@ -329,5 +376,5 @@ } - /* Lock the task and release the lock protecting tasks_btree. */ + /* Lock the task and release the lock protecting tasks dictionary. */ irq_spinlock_exchange(&tasks_lock, &task->lock); errno_t rc = ddi_iospace_disable_arch(task, ioaddr, size); Index: kernel/generic/src/lib/rd.c =================================================================== --- kernel/generic/src/lib/rd.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/generic/src/lib/rd.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -59,4 +59,5 @@ assert((base % FRAME_SIZE) == 0); + ddi_parea_init(&rd_parea); rd_parea.pbase = base; rd_parea.frames = SIZE2FRAMES(size); Index: kernel/generic/src/proc/task.c =================================================================== --- kernel/generic/src/proc/task.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/generic/src/proc/task.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -48,5 +48,4 @@ #include #include -#include #include #include Index: kernel/generic/src/time/clock.c =================================================================== --- kernel/generic/src/time/clock.c (revision 9c26ef0ab86146cbf34945fa1e96ad602fa9c891) +++ kernel/generic/src/time/clock.c (revision 6f7071b562c845499c96c4a1354e9a5d3ce94a05) @@ -91,4 +91,5 @@ uptime->useconds = 0; + ddi_parea_init(&clock_parea); clock_parea.pbase = faddr; clock_parea.frames = 1;