block latency histogram

Introduce latency histogram statics for block devices. For each accounted operation type latency region [0, +inf) is divided into subregions by several points. Then, calculate hits for each subregion.

Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>

---
  include/block/accounting.h |  9 +++++
  block/accounting.c         | 97 ++++++++++++++++++++++++++++++++++++++++++++++
  2 files changed, 106 insertions(+)

include/block/accounting.h +9 -0

index b833d26d6c..9679020f64 100644
@@ -45,6 +45,12 @@ struct BlockAcctTimedStats {
      QSLIST_ENTRY(BlockAcctTimedStats) entries;
  };
 
+typedef struct BlockLatencyHistogram {
+    int size;
+    uint64_t *points; /* @size-1 points here (all points, except 0 and +inf) */
+    uint64_t *histogram[BLOCK_MAX_IOTYPE]; /* @size elements for each type */
+} BlockLatencyHistogram;
+
  struct BlockAcctStats {
      QemuMutex lock;
      uint64_t nr_bytes[BLOCK_MAX_IOTYPE];

@@ -57,6 +63,7 @@ struct BlockAcctStats {
      QSLIST_HEAD(, BlockAcctTimedStats) intervals;
      bool account_invalid;
      bool account_failed;
+    BlockLatencyHistogram latency_histogram;
  };
 
  typedef struct BlockAcctCookie {

@@ -82,5 +89,7 @@ void block_acct_merge_done(BlockAcctStats *stats, enum BlockAcctType type,
  int64_t block_acct_idle_time_ns(BlockAcctStats *stats);
  double block_acct_queue_depth(BlockAcctTimedStats *stats,
                                enum BlockAcctType type);
+int block_latency_histogram_set(BlockAcctStats *stats, uint64List *latency);
+void block_latency_histogram_clear(BlockAcctStats *stats);
 
  #endif

block/accounting.c +46 -0

index 87ef5bbfaa..0051ff0c24 100644
@@ -94,6 +94,100 @@ void block_acct_start(BlockAcctStats *stats, BlockAcctCookie *cookie,
      cookie->type = type;
  }
 
+/* block_latency_histogram_compare_func
+ * Compare @key with interval [@el, @el+1), where @el+1 is a next array element
+ * after @el.
+ * Return: -1 if @key < @el
+ *          0 if @key in [@el, @el+1)
+ *         +1 if @key >= @el+1
+ */
+static int block_latency_histogram_compare_func(const void *key, const void *el)
+{
+    uint64_t k = *(uint64_t *)key;
+    uint64_t a = *(uint64_t *)el;
+    uint64_t b = *((uint64_t *)el + 1);
+
+    return k < a ? -1 : (k < b ? 0 : 1);
+}
+
+static void block_latency_histogram_account(BlockLatencyHistogram *hist,
+                                            enum BlockAcctType type,
+                                            int64_t latency_ns)
+{
+    uint64_t *data, *pos;
+
+    if (hist->points == NULL) {
+        /* histogram disabled */
+        return;
+    }
+
+    data = hist->histogram[type];
+
+    if (latency_ns < hist->points[0]) {
+        data[0]++;
+        return;
+    }
+
+    if (latency_ns >= hist->points[hist->size - 2]) {
+        data[hist->size - 1]++;
+        return;
+    }
+
+    pos = bsearch(&latency_ns, hist->points, hist->size - 2,
+                  sizeof(hist->points[0]),
+                  block_latency_histogram_compare_func);
+    assert(pos != NULL);
+
+    data[pos - hist->points + 1]++;
+}

block/accounting.c +41 -0

+
+    for (entry = latency; entry; entry = entry->next) {
+        if (entry->value <= prev) {
+            return -EINVAL;
+        }
+        hist->size++;
+        prev = entry->value;
+    }
+
+    hist->points = g_renew(uint64_t, hist->points, hist->size - 1);
+    for (entry = latency, ptr = hist->points; entry;
+         entry = entry->next, ptr++)
+    {
+        *ptr = entry->value;
+    }
+
+    for (i = 0; i < BLOCK_MAX_IOTYPE; i++) {
+        hist->histogram[i] = g_renew(uint64_t, hist->histogram[i], hist->size);
+        memset(hist->histogram[i], 0, hist->size * sizeof(uint64_t));
+    }
+
+    return 0;
+}
+
+void block_latency_histogram_clear(BlockAcctStats *stats)
+{
+    BlockLatencyHistogram *hist = &stats->latency_histogram;
+    int i;
+
+    g_free(hist->points);
+    hist->points = NULL;
+
+    for (i = 0; i < BLOCK_MAX_IOTYPE; i++) {
+        g_free(hist->histogram[i]);
+        hist->histogram[i] = NULL;
+    }
+}
+
  static void block_account_one_io(BlockAcctStats *stats, BlockAcctCookie *cookie,
                                   bool failed)
  {

@@ -116,6 +210,9 @@ static void block_account_one_io(BlockAcctStats *stats, BlockAcctCookie *cookie,
          stats->nr_ops[cookie->type]++;
      }
 
+    block_latency_histogram_account(&stats->latency_histogram, cookie->type,
+                                    latency_ns);
+
      if (!failed || stats->account_failed) {
          stats->total_time_ns[cookie->type] += latency_ns;
          stats->last_access_time_ns = time_ns;

Introduce latency histogram statics for block devices. For each accounted operation type latency region [0, +inf) is divided into subregions by several points. Then, calculate hits for each subregion.

Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>

---
 include/block/accounting.h |  9 +++++
 block/accounting.c         | 97 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 106 insertions(+)

include/block/accounting.h +0 -0

index b833d26d6c..9679020f64 100644

include/block/accounting.h +18 -0

+int block_latency_histogram_set(BlockAcctStats *stats, uint64List *latency)
+{
+    BlockLatencyHistogram *hist = &stats->latency_histogram;
+    uint64List *entry;
+    uint64_t *ptr;
+    int i;
+    uint64_t prev = 0;
+
+    hist->size = 1;
+
+    for (entry = latency; entry; entry = entry->next) {
+        if (entry->value <= prev) {
+            return -EINVAL;
+        }
+        hist->size++;
+        prev = entry->value;
+    }
+

Quoted 7 lines · Vladimir Sementsov-Ogievskiy

Introduce latency histogram statics for block devices. For each accounted operation type latency region [0, +inf) is divided into subregions by several points. Then, calculate hits for each subregion.

Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>

---

According to Wikipedia and Mathworld, "intervals" and "bins" are commonly used terms:
https://en.wikipedia.org/wiki/Histogram
http://mathworld.wolfram.com/Histogram.html

I suggest:

typedef struct {
/* The following histogram is represented like this:
*
* 5| *
* 4| *
* 3| * *
* 2| * * *
* 1| * * * *
* +------------------
* 10 50 100
*
* BlockLatencyHistogram histogram = {
* .nbins = 4,
* .intervals = {10, 50, 100},
* .bins = {3, 1, 5, 2},
* };

Quoted 24 lines · Stefan Hajnoczi

Quoted 7 lines · Vladimir Sementsov-Ogievskiy

Introduce latency histogram statics for block devices. For each accounted operation type latency region [0, +inf) is divided into subregions by several points. Then, calculate hits for each subregion.

Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>

---

According to Wikipedia and Mathworld, "intervals" and "bins" are commonly used terms:
https://en.wikipedia.org/wiki/Histogram
http://mathworld.wolfram.com/Histogram.html

I suggest:

   typedef struct {
       /* The following histogram is represented like this:
        *

        * 5|           *
        * 4|           *
        * 3| *         *
        * 2| *         *    *
        * 1| *    *    *    *

Quoted 8 lines

        *  +------------------
        *      10   50   100
        *
        * BlockLatencyHistogram histogram = {
        *     .nbins = 4,
        *     .intervals = {10, 50, 100},
        *     .bins = {3, 1, 5, 2},
        * };

The name 'intervals' is still slightly ambiguous: does it hold the boundary point (0-10 for 10 slots, 10-50 for 40 slots, 50-100, for 50 slots, then 100-INF) or is it the interval size of each slot (first bin is 10 slots for 0-10, next bin is 50 slots wide so 10-60, next bin is 100 slots wide so 60-160, everything else is 160-INF).  But the ascii-art diagram plus the text is sufficient to resolve the intent if you keep that name (I don't have a suggestion for a better name).

Quoted 34 lines · Eric Blake

Quoted 24 lines · Stefan Hajnoczi

Quoted 7 lines · Vladimir Sementsov-Ogievskiy

Introduce latency histogram statics for block devices. For each accounted operation type latency region [0, +inf) is divided into subregions by several points. Then, calculate hits for each subregion.

Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>

---

According to Wikipedia and Mathworld, "intervals" and "bins" are commonly used terms:
https://en.wikipedia.org/wiki/Histogram
http://mathworld.wolfram.com/Histogram.html

I suggest:

   typedef struct {
       /* The following histogram is represented like this:
        *

        * 5|           *
        * 4|           *
        * 3| *         *
        * 2| *         *    *
        * 1| *    *    *    *

Quoted 8 lines

        *  +------------------
        *      10   50   100
        *
        * BlockLatencyHistogram histogram = {
        *     .nbins = 4,
        *     .intervals = {10, 50, 100},
        *     .bins = {3, 1, 5, 2},
        * };

Quoted 2 lines

The name 'intervals' is still slightly ambiguous: does it hold the boundary point (0-10 for 10 slots, 10-50 for 40 slots, 50-100, for 50 slots, then 100-INF) or is it the interval size of each slot (first bin is 10 slots for 0-10, next bin is 50 slots wide so 10-60, next bin is 100 slots wide so 60-160, everything else is 160-INF).  But the ascii-art diagram plus the text is sufficient to resolve the intent if you keep that name (I don't have a suggestion for a better name).

Hm. these numbers are actually boundary points of histogram intervals, not intervals itself. And, wiki says "The bins are usually specified as consecutive, non-overlapping intervals of a variable.", so, intervals are bins.

So, what about:

1. interval_boundaries
2. bin_boundaries
3. boundaries

(and same names with s/_/-/ for qapi)

Quoted 46 lines · Vladimir Sementsov-Ogievskiy

Quoted 34 lines · Eric Blake

Quoted 24 lines · Stefan Hajnoczi

Quoted 7 lines · Vladimir Sementsov-Ogievskiy

Introduce latency histogram statics for block devices. For each accounted operation type latency region [0, +inf) is divided into subregions by several points. Then, calculate hits for each subregion.

Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>

---

According to Wikipedia and Mathworld, "intervals" and "bins" are commonly used terms:
https://en.wikipedia.org/wiki/Histogram
http://mathworld.wolfram.com/Histogram.html

I suggest:

   typedef struct {
       /* The following histogram is represented like this:
        *

        * 5|           *
        * 4|           *
        * 3| *         *
        * 2| *         *    *
        * 1| *    *    *    *

Quoted 8 lines

        *  +------------------
        *      10   50   100
        *
        * BlockLatencyHistogram histogram = {
        *     .nbins = 4,
        *     .intervals = {10, 50, 100},
        *     .bins = {3, 1, 5, 2},
        * };

Quoted 2 lines

The name 'intervals' is still slightly ambiguous: does it hold the boundary point (0-10 for 10 slots, 10-50 for 40 slots, 50-100, for 50 slots, then 100-INF) or is it the interval size of each slot (first bin is 10 slots for 0-10, next bin is 50 slots wide so 10-60, next bin is 100 slots wide so 60-160, everything else is 160-INF).  But the ascii-art diagram plus the text is sufficient to resolve the intent if you keep that name (I don't have a suggestion for a better name).

Hm. these numbers are actually boundary points of histogram intervals, not intervals itself. And, wiki says "The bins are usually specified as consecutive, non-overlapping intervals of a variable.", so, intervals are bins.

So, what about:

1. interval_boundaries
2. bin_boundaries
3. boundaries

Quoted 3 lines

(and same names with s/_/-/ for qapi)

Also, now I doubt, is it a good idea to share same bin boundaries for each io type.

Quoted 9 lines

Quoted 9 lines

Hm. these numbers are actually boundary points of histogram intervals, not intervals itself. And, wiki says "The bins are usually specified as consecutive, non-overlapping intervals of a variable.", so, intervals are bins.

So, what about:

1. interval_boundaries
2. bin_boundaries
3. boundaries

(and same names with s/_/-/ for qapi)

Quoted 6 lines

Quoted 2 lines

Also, now I doubt, is it a good idea to share same bin boundaries for each io type.

so, for qmp command, what about:

boundaries - optional, default boundaries for all io operations boundaries-read - boundaries for read boundaries-write - boundaries for write
...

so, call without any boundaries: drop _all_ histograms
call with only specific boundaries-*: set or reset _only_ corresponding specific histograms
call with only boundaries parameter: set or reset _all_ histograms
call with boundaries parameter and some of (or all, but it is not useful) specific boundaries-*: set or reset _all_ histograms, some to default  and some to specific.

qapi/block-core.json +11 -0

+#        for 0 < i < len(@latency): @read[i] corresponds to latency region
+#            [@latency[i-1], @latency[i])
+#        @read.last_element corresponds to latency region
+#            [@latency.last_element, +inf)
+#
+# @write: list of write-request counts (see @read semantics)
+#
+# @flush: list of flush-request counts (see @read semantics)
+#
+# Since: 2.12
+##

Hi,

This series failed build test on ppc host. Please find the details below.

Type: series
Subject: [Qemu-devel] [PATCH v2 0/2] block latency histogram
Message-id: [email protected]

=== TEST SCRIPT BEGIN ===
#!/bin/bash
# Testing script will be invoked under the git checkout with # HEAD pointing to a commit that has the patches applied on top of "base"

# branch
set -e
echo "=== ENV ==="
env
echo "=== PACKAGES ==="
rpm -qa
echo "=== TEST BEGIN ==="
INSTALL=$PWD/install
BUILD=$PWD/build
mkdir -p $BUILD $INSTALL
SRC=$PWD
cd $BUILD
$SRC/configure --prefix=$INSTALL
make -j100
# XXX: we need reliable clean up
# make check -j100 V=1
make install
=== TEST SCRIPT END ===

Updating 3c8cf5a9c21ff8782164d1def7f44bd888713384
error: RPC failed; result=18, HTTP code = 200
fatal: The remote end hung up unexpectedly
error: Could not fetch 3c8cf5a9c21ff8782164d1def7f44bd888713384 Traceback (most recent call last):
File "/home/patchew/patchew/patchew-cli", line 504, in test_one

     git_clone_repo(clone, r["repo"], r["head"], logf)

File "/home/patchew/patchew/patchew-cli", line 48, in git_clone_repo
stdout=logf, stderr=logf)
File "/usr/lib64/python3.4/subprocess.py", line 558, in check_call
raise CalledProcessError(retcode, cmd)
subprocess.CalledProcessError: Command '['git', 'remote', 'add', '-f', '--mirror=fetch', '3c8cf5a9c21ff8782164d1def7f44bd888713384', 'https://github.com/patchew-project/qemu']' returned non-zero exit status 1

---
Email generated automatically by Patchew [http://patchew.org/].
Please send your feedback to [email protected]

v2:

01: add block_latency_histogram_clear()
02: fix spelling (sorry =()
some rewordings
remove histogram if latency parameter unspecified

Vladimir Sementsov-Ogievskiy (2):
block/accounting: introduce latency histogram
qapi: add block latency histogram interface

  qapi/block-core.json       | 73 +++++++++++++++++++++++++++++++++-
  include/block/accounting.h |  9 +++++
  block/accounting.c         | 97 ++++++++++++++++++++++++++++++++++++++++++++++
  block/qapi.c               | 31 +++++++++++++++
  blockdev.c                 | 19 +++++++++
  5 files changed, 228 insertions(+), 1 deletion(-)

v2:

01: add block_latency_histogram_clear()
02: fix spelling (sorry =()
some rewordings
remove histogram if latency parameter unspecified

Vladimir Sementsov-Ogievskiy (2):
block/accounting: introduce latency histogram
qapi: add block latency histogram interface

  qapi/block-core.json       | 73 +++++++++++++++++++++++++++++++++-
  include/block/accounting.h |  9 +++++
  block/accounting.c         | 97 ++++++++++++++++++++++++++++++++++++++++++++++
  block/qapi.c               | 31 +++++++++++++++
  blockdev.c                 | 19 +++++++++
  5 files changed, 228 insertions(+), 1 deletion(-)

v2:

01: add block_latency_histogram_clear()
02: fix spelling (sorry =()
some rewordings
remove histogram if latency parameter unspecified

Vladimir Sementsov-Ogievskiy (2):
block/accounting: introduce latency histogram
qapi: add block latency histogram interface

 qapi/block-core.json       | 73 +++++++++++++++++++++++++++++++++-
 include/block/accounting.h |  9 +++++
 block/accounting.c         | 97 ++++++++++++++++++++++++++++++++++++++++++++++
 block/qapi.c               | 31 +++++++++++++++
 blockdev.c                 | 19 +++++++++
 5 files changed, 228 insertions(+), 1 deletion(-)

Quoted 3 lines · Vladimir Sementsov-Ogievskiy

Vladimir Sementsov-Ogievskiy (2):
block/accounting: introduce latency histogram
qapi: add block latency histogram interface

Quoted 1 line

 5 files changed, 228 insertions(+), 1 deletion(-)

The feature looks good. I posted documentation and code readability suggestions.

Quoted 4 lines · Stefan Hajnoczi

Quoted 3 lines · Vladimir Sementsov-Ogievskiy

Vladimir Sementsov-Ogievskiy (2):
block/accounting: introduce latency histogram
qapi: add block latency histogram interface

(snip)

Quoted 3 lines

Quoted 1 line

  5 files changed, 228 insertions(+), 1 deletion(-)

The feature looks good. I posted documentation and code readability suggestions.

Hi Vladimir,

Did you consider using qdist? For reference, see commit bf3afd5f419 and/or grep 'qdist'.

Thanks,

Emilio

Hi Emilio!

Looked through qdist, if I understand correctly, it saves each added (with different value) element. It is not effective for disk io timing - we'll have too much elements. In my approach, histogram don't grow, it initially have several ranges and counts hits to each range.

Quoted 6 lines · Vladimir Sementsov-Ogievskiy

Hi Emilio!

Looked through qdist, if I understand correctly, it saves each added (with different value) element. It is not effective for disk io timing - we'll have too much elements. In my approach, histogram don't grow, it initially have several ranges and counts hits to each range.

I thought about this use case, i.e. having a gazillion elements. You should just do some pre-binning before inserting samples into qdist, as pointed out in this comment in qdist.h:

/*
* Samples with the same 'x value' end up in the same qdist_entry,
* e.g. inc(0.1) and inc(0.1) end up as {x=0.1, count=2}.
*
* Binning happens only at print time, so that we retain the flexibility to
* choose the binning. This might not be ideal for workloads that do not care
* much about precision and insert many samples all with different x values;
* in that case, pre-binning (e.g. entering both 0.115 and 0.097 as 0.1)
* should be considered.
*/

struct qdist_entry {
     double x;
     unsigned long count;
};

Let me know if you need help with that.

Thanks,

Emilio

Quoted 5 lines · Emilio G. Cota

* Binning happens only at print time, so that we retain the flexibility to
* choose the binning. This might not be ideal for workloads that do not care
* much about precision and insert many samples all with different x values;
* in that case, pre-binning (e.g. entering both 0.115 and 0.097 as 0.1)
* should be considered.

In this case, I'll have to do same bin search (and store same interval settings) as I already do, on my part, to calculate a parameter for qdist interface. And I'll have store almost all same data on my part. So, it doesn't really help. And I need nothing of qdist benefits: I don't need (and don't want) dynamic allocation of bins on adding an element or any type of visualization.

Quoted 11 lines · Vladimir Sementsov-Ogievskiy

v2:

01: add block_latency_histogram_clear()
02: fix spelling (sorry =()
some rewordings
remove histogram if latency parameter unspecified

Vladimir Sementsov-Ogievskiy (2):
block/accounting: introduce latency histogram
qapi: add block latency histogram interface

Quoted 6 lines

  qapi/block-core.json       | 73 +++++++++++++++++++++++++++++++++-
  include/block/accounting.h |  9 +++++
  block/accounting.c         | 97 ++++++++++++++++++++++++++++++++++++++++++++++
  block/qapi.c               | 31 +++++++++++++++
  blockdev.c                 | 19 +++++++++
  5 files changed, 228 insertions(+), 1 deletion(-)

The feature looks good. I posted documentation and code readability suggestions.