[Qemu-devel] [PATCH 4/5] disk_deadlines: add control of requests time expiration

[Denis V. Lunev]

From: Raushaniya Maksudova <address@hidden>

If disk-deadlines option is enabled for a drive, one controls time
completion of this drive's requests. The method is as follows (further
assume that this option is enabled).

Every drive has its own red-black tree for keeping its requests.
Expiration time of the request is a key, cookie (as id of request) is an
appropriate node. Assume that every requests has 8 seconds to be completed.
If request was not accomplished in time for some reasons (server crash or
smth else), timer of this drive is fired and an appropriate callback
requests to stop Virtial Machine (VM).

VM remains stopped until all requests from the disk which caused VM's
stopping are completed. Furthermore, if there is another disks whose
requests are waiting to be completed, do not start VM : wait completion
of all "late" requests from all disks.

Signed-off-by: Raushaniya Maksudova <address@hidden>
Signed-off-by: Denis V. Lunev <address@hidden>
CC: Stefan Hajnoczi <address@hidden>
CC: Kevin Wolf <address@hidden>
---
 block/accounting.c             |   8 ++
 block/disk-deadlines.c         | 167 +++++++++++++++++++++++++++++++++++++++++
 include/block/disk-deadlines.h |  11 +++
 3 files changed, 186 insertions(+)

diff --git a/block/accounting.c b/block/accounting.c
index 01d594f..7b913fd 100644
--- a/block/accounting.c
+++ b/block/accounting.c
@@ -34,6 +34,10 @@ void block_acct_start(BlockAcctStats *stats, BlockAcctCookie 
*cookie,
     cookie->bytes = bytes;
     cookie->start_time_ns = qemu_clock_get_ns(QEMU_CLOCK_REALTIME);
     cookie->type = type;
+
+    if (stats->disk_deadlines.enabled) {
+        insert_request(&stats->disk_deadlines, cookie);
+    }
 }
 
 void block_acct_done(BlockAcctStats *stats, BlockAcctCookie *cookie)
@@ -44,6 +48,10 @@ void block_acct_done(BlockAcctStats *stats, BlockAcctCookie 
*cookie)
     stats->nr_ops[cookie->type]++;
     stats->total_time_ns[cookie->type] +=
         qemu_clock_get_ns(QEMU_CLOCK_REALTIME) - cookie->start_time_ns;
+
+    if (stats->disk_deadlines.enabled) {
+        remove_request(&stats->disk_deadlines, cookie);
+    }
 }
 
 
diff --git a/block/disk-deadlines.c b/block/disk-deadlines.c
index 39dec53..acb44bc 100644
--- a/block/disk-deadlines.c
+++ b/block/disk-deadlines.c
@@ -23,8 +23,175 @@
  */
 
 #include "block/disk-deadlines.h"
+#include "block/accounting.h"
+#include "sysemu/sysemu.h"
+#include "qemu/atomic.h"
+
+/*
+ * Number of late requests which were not completed in time
+ * (its timer has expired) and as a result it caused VM's stopping
+ */
+uint64_t num_requests_vmstopped;
+
+/* Give 8 seconds for request to complete by default */
+const uint64_t EXPIRE_DEFAULT_NS = 8000000000;
+
+typedef struct RequestInfo {
+    BlockAcctCookie *cookie;
+    int64_t expire_time;
+} RequestInfo;
+
+static gint compare(gconstpointer a, gconstpointer b)
+{
+    return (int64_t)a - (int64_t)b;
+}
+
+static gboolean find_request(gpointer key, gpointer value, gpointer data)
+{
+    BlockAcctCookie *cookie = value;
+    RequestInfo *request = data;
+    if (cookie == request->cookie) {
+        request->expire_time = (int64_t)key;
+        return true;
+    }
+    return false;
+}
+
+static gint search_min_key(gpointer key, gpointer data)
+{
+    int64_t tree_key = (int64_t)key;
+    int64_t *ptr_curr_min_key = data;
+
+    if ((tree_key <= *ptr_curr_min_key) || (*ptr_curr_min_key == 0)) {
+        *ptr_curr_min_key = tree_key;
+    }
+    /*
+     * We always want to proceed searching among key/value pairs
+     * with smaller key => return -1
+     */
+    return -1;
+}
+
+static int64_t soonest_expire_time(GTree *requests_tree)
+{
+    int64_t min_timestamp = 0;
+    /*
+     * g_tree_search() will always return NULL, because there is no
+     * key = 0 in the tree, we simply search for node the with the minimal key
+     */
+    g_tree_search(requests_tree, (GCompareFunc)search_min_key, &min_timestamp);
+    return min_timestamp;
+}
+
+static void disk_deadlines_callback(void *opaque)
+{
+    bool need_vmstop = false;
+    int64_t current_time, expire_time;
+    DiskDeadlines *disk_deadlines = opaque;
+
+    /*
+     * Check whether the request that triggered callback invocation
+     * is still in the tree of requests.
+     */
+    current_time = qemu_clock_get_ns(QEMU_CLOCK_REALTIME);
+    pthread_mutex_lock(&disk_deadlines->mtx_tree);
+    if (g_tree_nnodes(disk_deadlines->requests_tree) == 0) {
+        /* There are no requests in the tree, do nothing */
+        pthread_mutex_unlock(&disk_deadlines->mtx_tree);
+        return;
+    }
+    expire_time = soonest_expire_time(disk_deadlines->requests_tree);
+
+    /*
+     * If the request was not found, then there is no disk deadline detected,
+     * just update the timer with new value
+     */
+    if (expire_time > current_time) {
+        timer_mod_ns(disk_deadlines->request_timer, expire_time);
+        pthread_mutex_unlock(&disk_deadlines->mtx_tree);
+        return;
+    }
+
+    disk_deadlines->expired_tree = true;
+    need_vmstop = !atomic_fetch_inc(&num_requests_vmstopped);
+    pthread_mutex_unlock(&disk_deadlines->mtx_tree);
+
+    if (need_vmstop) {
+        qemu_system_vmstop_request_prepare();
+        qemu_system_vmstop_request(RUN_STATE_PAUSED);
+    }
+}
 
 void disk_deadlines_init(DiskDeadlines *disk_deadlines, bool enabled)
 {
     disk_deadlines->enabled = enabled;
+    if (!disk_deadlines->enabled) {
+        return;
+    }
+
+    disk_deadlines->requests_tree = g_tree_new(compare);
+    if (disk_deadlines->requests_tree == NULL) {
+        disk_deadlines->enabled = false;
+        fprintf(stderr,
+                "disk_deadlines_init: failed to allocate requests_tree\n");
+        return;
+    }
+
+    pthread_mutex_init(&disk_deadlines->mtx_tree, NULL);
+    disk_deadlines->expired_tree = false;
+    disk_deadlines->request_timer = timer_new_ns(QEMU_CLOCK_REALTIME,
+                                                 disk_deadlines_callback,
+                                                 (void *)disk_deadlines);
+}
+
+void insert_request(DiskDeadlines *disk_deadlines, void *request)
+{
+    BlockAcctCookie *cookie = request;
+
+    int64_t expire_time = cookie->start_time_ns + EXPIRE_DEFAULT_NS;
+
+    pthread_mutex_lock(&disk_deadlines->mtx_tree);
+    /* Set up expire time for the current disk if it is not set yet */
+    if (timer_expired(disk_deadlines->request_timer,
+        qemu_clock_get_ns(QEMU_CLOCK_REALTIME))) {
+        timer_mod_ns(disk_deadlines->request_timer, expire_time);
+    }
+
+    g_tree_insert(disk_deadlines->requests_tree, (int64_t *)expire_time,
+                  cookie);
+    pthread_mutex_unlock(&disk_deadlines->mtx_tree);
+}
+
+void remove_request(DiskDeadlines *disk_deadlines, void *request)
+{
+    bool need_vmstart = false;
+    RequestInfo request_info = {
+        .cookie = request,
+        .expire_time = 0,
+    };
+
+    /* Find the request to remove */
+    pthread_mutex_lock(&disk_deadlines->mtx_tree);
+    g_tree_foreach(disk_deadlines->requests_tree, find_request, &request_info);
+    g_tree_remove(disk_deadlines->requests_tree,
+                  (int64_t *)request_info.expire_time);
+
+    /*
+     * If tree is empty, but marked as expired, then one needs to
+     * unset "expired_tree" flag and check whether VM can be resumed
+     */
+    if (!g_tree_nnodes(disk_deadlines->requests_tree) &&
+        disk_deadlines->expired_tree) {
+        disk_deadlines->expired_tree = false;
+        /*
+         * If all requests (from all disks with enabled
+         * "disk-deadlines" feature) are completed, resume VM
+         */
+        need_vmstart = !atomic_dec_fetch(&num_requests_vmstopped);
+    }
+    pthread_mutex_unlock(&disk_deadlines->mtx_tree);
+
+    if (need_vmstart) {
+        qemu_system_vmstart_request();
+    }
 }
diff --git a/include/block/disk-deadlines.h b/include/block/disk-deadlines.h
index 2ea193b..9672aff 100644
--- a/include/block/disk-deadlines.h
+++ b/include/block/disk-deadlines.h
@@ -25,11 +25,22 @@
 #define DISK_DEADLINES_H
 
 #include <stdbool.h>
+#include <stdint.h>
+#include <glib.h>
+
+#include "qemu/typedefs.h"
+#include "qemu/timer.h"
 
 typedef struct DiskDeadlines {
     bool enabled;
+    bool expired_tree;
+    pthread_mutex_t mtx_tree;
+    GTree *requests_tree;
+    QEMUTimer *request_timer;
 } DiskDeadlines;
 
 void disk_deadlines_init(DiskDeadlines *disk_deadlines, bool enabled);
+void insert_request(DiskDeadlines *disk_deadlines, void *request);
+void remove_request(DiskDeadlines *disk_deadlines, void *request);
 
 #endif
-- 
2.1.4