Changeset 6f7071b in mainline for kernel/generic/src/ddi/ddi.c

Timestamp:

2018-11-05T09:13:04Z (6 years ago)

Author:

Jiri Svoboda <jiri@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

4a8d0dd1

Parents:

9c26ef0

git-author:

Jiri Svoboda <jiri@…> (2018-10-04 18:11:52)

git-committer:

Jiri Svoboda <jiri@…> (2018-11-05 09:13:04)

Message:

Use ordered dictionary for kernel pareas instead of B+ tree.

File:

• kernel/generic/src/ddi/ddi.c (modified) (10 diffs)

kernel/generic/src/ddi/ddi.c

@@ -49 +49 @@
 #include <synch/mutex.h>
 #include <syscall/copy.h>
-#include <adt/btree.h>
+#include <adt/odict.h>
 #include <arch.h>
 #include <align.h>
 #include <errno.h>
+#include <mem.h>
 #include <trace.h>
 #include <bitops.h>
 
-/** 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 +71 @@
 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 +95 @@
 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 +146 @@
          */
 
-        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 +161 @@
 
         parea = NULL;
-        mutex_unlock(&parea_lock);
+        mutex_unlock(&pareas_lock);
 
         /*
@@ -193 +210 @@
 
                 if (parea != NULL)
-                        mutex_unlock(&parea_lock);
+                        mutex_unlock(&pareas_lock);
 
                 return ENOMEM;
@@ -204 +221 @@
         if (parea != NULL) {
                 parea->mapped = true;
-                mutex_unlock(&parea_lock);
+                mutex_unlock(&pareas_lock);
         }
 
@@ -255 +272 @@
 }
 
+/** 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 +335 @@
         }
 
-        /* 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 +376 @@
         }
 
-        /* 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);