DeviceQeues: Implemented memory region pool management
authorRoni Häcki <roni.haecki@inf.ethz.ch>
Thu, 14 Jul 2016 13:52:03 +0000 (15:52 +0200)
committerRoni Häcki <roni.haecki@inf.ethz.ch>
Thu, 14 Jul 2016 13:52:03 +0000 (15:52 +0200)
Signed-off-by: Roni Häcki <roni.haecki@inf.ethz.ch>

include/device_interfaces/device_queue_interface.h
lib/device_interfaces/device_queue_interface.c
lib/device_interfaces/dqi_debug.h [new file with mode: 0644]
lib/device_interfaces/region_pool.c
lib/device_interfaces/region_pool.h

index d2c59af..59d259d 100644 (file)
@@ -19,7 +19,6 @@ typedef uint32_t bufferid_t;
 
 struct region_pool;
 
-
 /**
  * Represent the device queue itself
  */
@@ -34,9 +33,9 @@ struct device_queue {
     char device_name[MAX_DEVICE_NAME];
     // pointer to device queue state
     void* q_state;
-
-    //TODO Other state needed ...
+    // Region management
     struct region_pool* pool;
+    //TODO Other state needed ...
 };
 
 
index 1ef5f17..6634416 100644 (file)
@@ -33,7 +33,39 @@ errval_t device_queue_create(struct device_queue **q,
                              char* device_name,
                              char* misc)
 {
-    USER_PANIC("NIY\n");
+    struct region_pool* pool;
+    region_pool_init(&pool);
+    struct capref cap;
+    uint32_t region_ids[100];
+    
+    for (int i = 0; i < 100; i++) {
+        region_ids[i] = -1;
+    }
+
+    srand(rdtsc());
+
+    for (int i = 0; i < 10000000; i++) {
+        int id = rand() % 100;
+        if (region_ids[id] == -1) {
+            region_pool_add_region(pool, cap, 0x1222222, &region_ids[id]);
+        } else {
+            region_pool_remove_region(pool, region_ids[id], &cap);
+            region_ids[id] = -1;
+        }
+    }
+/*
+    for (int i = 0; i < 32; i++) {
+        region_pool_add_region(pool, cap, 0x1222222, &region_ids[i]);
+        printf("Region_id[%d]=%d \n", i, region_ids[i]);
+    }
+
+    region_pool_remove_region(pool, region_ids[0], &cap);
+    region_pool_remove_region(pool, region_ids[15], &cap);
+
+    region_pool_add_region(pool, cap, 0x1222222, &region_ids[0]);
+    region_pool_add_region(pool, cap, 0x1222222, &region_ids[15]);
+*/
+    //USER_PANIC("NIY\n");
     return SYS_ERR_OK;
 }
 
@@ -57,33 +89,6 @@ errval_t device_queue_destroy(struct device_queue *qp)
  * Datapath functions
  * ===========================================================================
  */
-
-/**
- * @brief enqueue a buffer into the device queue
- *
- * @param q             The device queue to call the operation on
- * @param region_id     Id of the memory region the buffer belongs to
- * @param base          Physical address of the start of the enqueued buffer
- * @param lenght        Lenght of the enqueued buffer
- * @param buffer_id     The buffer id of the enqueue buffer (TODO only for 
- *                      fixed size buffers?)
- * @param misc_flags    Any other argument that makes sense to the device queue
- *
- * @returns error on failure or SYS_ERR_OK on success
- *
- */
-/*
-errval_t device_queue_enqueue(struct device_queue *q,
-                              regionid_t region_id,
-                              lpaddr_t base,
-                              size_t length,
-                              bufferid_t buffer_id,
-                              char* misc_flags)
-{
-    USER_PANIC("NIY\n");
-    return SYS_ERR_OK;
-}
-*/
 /**
  * @brief enqueue some memory into the device queue
  *
@@ -107,31 +112,6 @@ errval_t device_queue_enqueue(struct device_queue *q,
  * @brief dequeue a buffer from the device queue
  *
  * @param q             The device queue to call the operation on
- * @param region_id     Return pointer to the id of the memory 
- *                      region the buffer belongs to
- * @param base          Return pointer to the physical address of 
- *                      the of the buffer
- * @param lenght        Return pointer to the lenght of the dequeue buffer
- * @param buffer_id     Return pointer to thehe buffer id of the dequeued buffer
- *
- * @returns error on failure or SYS_ERR_OK on success
- *
- */
-/*
-errval_t device_queue_dequeue(struct device_queue *q,
-                              regionid_t* region_id,
-                              lpaddr_t* base,
-                              size_t* length,
-                              bufferid_t* buffer_id)
-{
-    USER_PANIC("NIY\n");
-    return SYS_ERR_OK;
-}
-*/
-/**
- * @brief dequeue a buffer from the device queue
- *
- * @param q             The device queue to call the operation on
  * @param buf           Return pointer to the dequeued buffer
  *
  * @returns error on failure or SYS_ERR_OK on success
diff --git a/lib/device_interfaces/dqi_debug.h b/lib/device_interfaces/dqi_debug.h
new file mode 100644 (file)
index 0000000..5c9acb7
--- /dev/null
@@ -0,0 +1,29 @@
+/*
+ * Copyright (c) 2016 ETH Zurich.
+ * All rights reserved.
+ *
+ * This file is distributed under the terms in the attached LICENSE file.
+ * If you do not find this file, copies can be found by writing to:
+ * ETH Zurich D-INFK, Universitaetstr. 6, CH-8092 Zurich. Attn: Systems Group.
+ */
+#ifndef DQI_DEBUG_H_
+#define DQI_DEBUG_H_ 1
+
+
+//#define DQI_DEBUG_ENABLED 1
+
+/*****************************************************************
+ * Debug printer:
+ *****************************************************************/
+
+#if defined(DQI_DEBUG_ENABLED) 
+#define DQI_DEBUG(x...) do { printf("DQI:%s.%d:%s:%d: ", \
+            disp_name(), disp_get_core_id(), __func__, __LINE__); \
+                printf(x);\
+        } while (0)
+
+#else
+#define DQI_DEBUG(x...) ((void)0)
+#endif 
+
+#endif /* DQI_DEBUG_H_ */
index 8dfa765..981bedf 100644 (file)
 
 #include <barrelfish/barrelfish.h>
 #include "region_pool.h"
+#include "dqi_debug.h"
 
+#define INIT_POOL_SIZE 2
+
+struct region {
+    // ID of the region
+    uint32_t region_id;
+    // Base address of the region
+    lpaddr_t base_addr;
+    // Capability of the region
+    struct capref* cap;
+};
+
+struct region_pool {
+
+    // IDs are inserted and may have to increase size at some point
+    uint16_t size;
+    // number of regions in pool
+    uint16_t num_regions;
+
+    // random offset where regions ids start from
+    uint64_t region_offset;
+    
+    // if we have to serach for a slot, need an offset
+    uint16_t last_offset;
+
+    // structure to store regions
+    struct region** pool;
+};
+
+/**
+ * @brief initialized a pool of regions
+ *
+ * @param pool          Return pointer to the region pool
+ *
+ * @returns error on failure or SYS_ERR_OK on success
+ */
 errval_t region_pool_init(struct region_pool** pool)
 {
-    USER_PANIC("NIY\n");
+    // Allocate pool struct itself including pointers to region
+    (*pool) = calloc(sizeof(struct region_pool), 1);
+    if (*pool == NULL) {
+        DQI_DEBUG("Allocationg inital pool failed \n");
+        return LIB_ERR_MALLOC_FAIL;
+    }
+
+    (*pool)->num_regions = 0;
+
+    srand(rdtsc());
+
+    // Initialize region id offset
+    (*pool)->region_offset = (rand() >> 12) ;
+    (*pool)->size = INIT_POOL_SIZE;    
+
+    (*pool)->pool = calloc(sizeof(struct region)*INIT_POOL_SIZE, 1);
+    if (*pool == NULL) {
+        DQI_DEBUG("Allocationg inital pool failed \n");
+        return LIB_ERR_MALLOC_FAIL;
+    }
+
+    DQI_DEBUG("Init region pool size=%d addr=%p\n", INIT_POOL_SIZE, *pool);
+    return SYS_ERR_OK;
+}
+
+/**
+ * @brief increase the region pool size by a factor of 2
+ *
+ * @param pool       the regin pool that has not enough region slots
+ *
+ * @returns error on failure or SYS_ERR_OK on success
+ */
+
+
+static errval_t region_pool_grow(struct region_pool* pool)
+{
+    struct region** tmp;
+
+    uint16_t new_size = (pool->size)*2;
+    // Allocate new pool twice the size
+    tmp = calloc(sizeof(struct region)*new_size, 1);
+    if (tmp == NULL) {
+        DQI_DEBUG("Allocationg larger pool failed \n");
+        return LIB_ERR_MALLOC_FAIL;
+    }
+
+    // Copy all the pointers
+    for (int i = 0; i < new_size; i++) {
+        tmp[i] = NULL;
+    }
+
+    struct region* region;
+    for (int i = 0; i < pool->size; i++) {
+        region = pool->pool[i];
+        uint16_t index =  region->region_id % new_size;
+        tmp[index] = pool->pool[i];
+    }
+
+    free(pool->pool);
+
+    pool->pool = tmp;
+    pool->size = new_size;
+    pool->last_offset = 0;
+
     return SYS_ERR_OK;
 }
 
+/**
+ * @brief add a memory region to the region pool
+ *
+ * @param pool          The pool to add the region to
+ * @param cap           The cap of the region
+ * @param base_addr     The physical base address of the region
+ * @param region_id     Return pointer to the region id 
+ *                      that is assigned by the pool
+ *
+ * @returns error on failure or SYS_ERR_OK on success
+ */
 errval_t region_pool_add_region(struct region_pool* pool, 
-                                struct region* region,
+                                struct capref cap,
+                                lpaddr_t base_addr,
                                 uint32_t* region_id)
 {
-    USER_PANIC("NIY\n");
+    errval_t err;
+
+    struct region* region = malloc(sizeof(struct region));
+    region->cap = &cap;
+    
+    // Check if pool size is large enough
+    if (!(pool->num_regions < pool->size)) {
+        DQI_DEBUG("Increasing pool size to %d \n", pool->size*2);
+        err = region_pool_grow(pool);
+        if (err_is_fail(err)) {
+            DQI_DEBUG("Increasing pool size failed\n");
+            return err;
+        }
+    }
+
+    pool->num_regions++;
+    uint16_t offset = pool->last_offset;
+    uint16_t index = 0;
+
+    while (true) {
+        index = (pool->region_offset + pool->num_regions + offset) % pool->size;
+        DQI_DEBUG("Trying insert index %d \n", index);
+        if (pool->pool[index] == NULL) {
+           break;
+        } else {
+            offset++;
+        }
+    }
+
+    pool->last_offset = offset;
+    region->region_id = pool->region_offset + pool->num_regions + offset;
+
+    // insert into pool
+    pool->pool[region->region_id % pool->size] = region;
+    *region_id = region->region_id;
+    DQI_DEBUG("Inserting region into pool at %d \n", region->region_id % pool->size);
     return SYS_ERR_OK;
 }
 
+/**
+ * @brief remove a memory region from the region pool
+ *
+ * @param pool          The pool to remove the region from
+ * @param region_id     The id of the region to remove
+ * @param cap           Return pointer to the cap of the removed region
+ *
+ * @returns error on failure or SYS_ERR_OK on success
+ */
 errval_t region_pool_remove_region(struct region_pool* pool, 
                                    uint32_t region_id,
-                                   struct region** region)
+                                   struct capref* cap)
 {
-    USER_PANIC("NIY\n");
+    struct region* region;
+    region = pool->pool[region_id % pool->size]; 
+    if (region == NULL) {
+        // TODO reasonable error;
+        return -1;
+    }
+
+    DQI_DEBUG("Removing slot %d \n", region_id % pool->size);
+    cap = region->cap;
+  
+    free(region);
+    pool->pool[region_id % pool->size] = NULL;
+
+    pool->num_regions--;
     return SYS_ERR_OK;
 }
 
index 0eea0c0..af75071 100644 (file)
 
 #include <barrelfish/barrelfish.h>
 
-#define INIT_POOL_SIZE 128
-struct buffer_pool;
-
-struct region {
-    domainid_t domain_id; // TODO needed?
-    // ID of the region
-    uint32_t region_id;
-    // Base address of the region
-    lpaddr_t base_addr;
-    // Capability of the region
-    struct capref* cap;
-};
-
-struct region_pool {
-
-    // IDs are "hashed" may have to increase size at some point
-    uint16_t region_pool_size;
-    // number of regions in pool
-    uint16_t num_regions;
-
-    // random offset where regions ids start from
-    uint64_t region_offset;
-
-    // TODO structure to store regions
-    struct region** pool;
-};
-
-
+struct region_pool;
+/**
+ * @brief initialized a pool of regions
+ *
+ * @param pool          Return pointer to the region pool
+ *
+ * @returns error on failure or SYS_ERR_OK on success
+ */
 errval_t region_pool_init(struct region_pool** pool);
 
+/**
+ * @brief add a memory region to the region pool
+ *
+ * @param pool          The pool to add the region to
+ * @param cap           The cap of the region
+ * @param base_addr     The physical base address of the region
+ * @param region_id     Return pointer to the region id 
+ *                      that is assigned by the pool
+ *
+ * @returns error on failure or SYS_ERR_OK on success
+ */
 errval_t region_pool_add_region(struct region_pool* pool, 
-                                struct region* region,
+                                struct capref cap,
+                                lpaddr_t base_addr,
                                 uint32_t* region_id);
 
+/**
+ * @brief remove a memory region from the region pool
+ *
+ * @param pool          The pool to remove the region from
+ * @param region_id     The id of the region to remove
+ * @param cap           Return pointer to the cap of the removed region
+ *
+ * @returns error on failure or SYS_ERR_OK on success
+ */
 errval_t region_pool_remove_region(struct region_pool* pool, 
                                    uint32_t region_id,
-                                   struct region** region);
+                                   struct capref* cap);
 
 
 #endif /* REGION_POOL_H_ */