Re: [PATCH v3 4/6] util: implement seqcache
05.03.2021 20:35, Vladimir Sementsov-Ogievskiy wrote: Implement cache for small sequential unaligned writes, so that they may be cached until we get a complete cluster and then write it. The cache is intended to be used for backup to qcow2 compressed target opened in O_DIRECT mode, but can be reused for any similar (even not block-layer related) task. Signed-off-by: Vladimir Sementsov-Ogievskiy --- include/qemu/seqcache.h | 42 + util/seqcache.c | 361 MAINTAINERS | 6 + util/meson.build| 1 + 4 files changed, 410 insertions(+) create mode 100644 include/qemu/seqcache.h create mode 100644 util/seqcache.c diff --git a/include/qemu/seqcache.h b/include/qemu/seqcache.h new file mode 100644 index 00..a308d54b01 --- /dev/null +++ b/include/qemu/seqcache.h @@ -0,0 +1,42 @@ +/* + * Cache for small sequential write requests. + * + * Copyright (c) 2021 Virtuozzo International GmbH. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#ifndef QEMU_SEQCACHE_H +#define QEMU_SEQCACHE_H + +typedef struct SeqCache SeqCache; + +SeqCache *seqcache_new(int64_t cluster_size); +void seqcache_free(SeqCache *s); + +void seqcache_write(SeqCache *s, int64_t offset, int64_t bytes, uint8_t *buf); +int64_t seqcache_read(SeqCache *s, int64_t offset, int64_t bytes, uint8_t *buf); + +bool seqcache_get_next_flush(SeqCache *s, int64_t *offset, int64_t *bytes, + uint8_t **buf, bool *unfinished); +void seqcache_discard_cluster(SeqCache *s, int64_t offset); + +uint64_t seqcache_nb_clusters(SeqCache *s); + +#endif /* QEMU_SEQCACHE_H */ diff --git a/util/seqcache.c b/util/seqcache.c new file mode 100644 index 00..d923560eab --- /dev/null +++ b/util/seqcache.c @@ -0,0 +1,361 @@ +/* + * Cache for small sequential write requests. + * + * Copyright (c) 2021 Virtuozzo International GmbH. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + * + * = Description = + * + * SeqCache is an abbreviation for Sequential Cache. + * + * The Cache is intended to improve performance of small unaligned sequential + * writes. Cache has a cluster_size parameter and the unit of caching is aligned + * cluster. Cache has a list of cached clusters, several "finished" ones and at + * most one "unfinished". "unfinished" cluster is a cluster where last byte of + * last write operation is cached and there is a free place after that byte to + * the end of cluster. "finished" clusters are just stored in cache to be read + * or flushed and don't allow any writes to them. + * + * If write to the cache intersects cluster bounds, it's splat into several + * requests by cluster bounds. So, consider a write that doesn't intersect + * cluster bounds to describe the whole picture: + * + * There are two cases allowed: + * + * 1. Sequential write to "unfinished" cluster. Actually it's
Re: [PATCH v3 4/6] util: implement seqcache
On 12.03.21 15:37, Vladimir Sementsov-Ogievskiy wrote:
12.03.2021 16:41, Max Reitz wrote:
On 05.03.21 18:35, Vladimir Sementsov-Ogievskiy wrote:
Implement cache for small sequential unaligned writes, so that they may
be cached until we get a complete cluster and then write it.
The cache is intended to be used for backup to qcow2 compressed target
opened in O_DIRECT mode, but can be reused for any similar (even not
block-layer related) task.
Signed-off-by: Vladimir Sementsov-Ogievskiy
---
include/qemu/seqcache.h | 42 +
util/seqcache.c | 361
MAINTAINERS | 6 +
util/meson.build | 1 +
4 files changed, 410 insertions(+)
create mode 100644 include/qemu/seqcache.h
create mode 100644 util/seqcache.c
Looks quite good to me, thanks. Nice explanations, too. :)
The only design question I have is whether there’s a reason you’re
using a list again instead of a hash table. I suppose we do need the
list anyway because of the next_flush iterator, so using a hash table
would only complicate the implementation, but still.
Yes, it seems correct for flush iterator go in same order as writes
comes, so we need a list. We can add a hash table, it will only help on
read.. But for compressed cache in qcow2 we try to flush often enough,
so there should not be many clusters in the cache. So I think addition
of hash table may be done later if needed.
Sure. The problem I see is that we’ll probably never reach the point of
it really being needed. O:)
So I think it’s a question of now or never.
[...]
+ */
+bool seqcache_get_next_flush(SeqCache *s, int64_t *offset, int64_t
*bytes,
+ uint8_t **buf, bool *unfinished)
Could be “uint8_t *const *buf”, I suppose. Don’t know how much the
callers would hate that, though.
Will do. And actually I wrote quite big explanation but missed the fact
that caller don't get ownership on buf, it should be mentioned.
Great, thanks.
+{
+ Cluster *req = s->next_flush;
+
+ if (s->next_flush) {
+ *unfinished = false;
+ req = s->next_flush;
+ s->next_flush = QSIMPLEQ_NEXT(req, entry);
+ if (s->next_flush == s->cur_write) {
+ s->next_flush = NULL;
+ }
+ } else if (s->cur_write && *unfinished) {
+ req = s->cur_write;
I was wondering whether flushing an unfinished cluster wouldn’t kind
of finalize it, but I suppose the problem with that would be that you
can’t add data to a finished cluster, which wouldn’t be that great if
you’re just flushing the cache without wanting to drop it all.
(The problem I see is that flushing it later will mean all the data
that already has been written here will have to be rewritten. Not
that bad, I suppose.)
Yes that's all correct. Also there is additional strong reason: qcow2
depends on the fact that clusters become "finished" by defined rules:
only when it really finished up the the end or when qcow2 starts writing
another cluster.
For "finished" clusters with unaligned end we can safely align this end
up to some good alignment writing a bit more data than needed. It's safe
because tail of the cluster is never used. And we'll perform better with
aligned write avoiding RMW.
But when flushing "unfinished" cluster, we should write exactly what we
have in the cache, as there may happen parallel write to the same
cluster, which will continue the sequential process.
OK, thanks for the explanation.
Max
Re: [PATCH v3 4/6] util: implement seqcache
12.03.2021 16:41, Max Reitz wrote: On 05.03.21 18:35, Vladimir Sementsov-Ogievskiy wrote: Implement cache for small sequential unaligned writes, so that they may be cached until we get a complete cluster and then write it. The cache is intended to be used for backup to qcow2 compressed target opened in O_DIRECT mode, but can be reused for any similar (even not block-layer related) task. Signed-off-by: Vladimir Sementsov-Ogievskiy --- include/qemu/seqcache.h | 42 + util/seqcache.c | 361 MAINTAINERS | 6 + util/meson.build | 1 + 4 files changed, 410 insertions(+) create mode 100644 include/qemu/seqcache.h create mode 100644 util/seqcache.c Looks quite good to me, thanks. Nice explanations, too. :) The only design question I have is whether there’s a reason you’re using a list again instead of a hash table. I suppose we do need the list anyway because of the next_flush iterator, so using a hash table would only complicate the implementation, but still. Yes, it seems correct for flush iterator go in same order as writes comes, so we need a list. We can add a hash table, it will only help on read.. But for compressed cache in qcow2 we try to flush often enough, so there should not be many clusters in the cache. So I think addition of hash table may be done later if needed. [...] diff --git a/util/seqcache.c b/util/seqcache.c new file mode 100644 index 00..d923560eab --- /dev/null +++ b/util/seqcache.c @@ -0,0 +1,361 @@ +/* + * Cache for small sequential write requests. + * + * Copyright (c) 2021 Virtuozzo International GmbH. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + * + * = Description = + * + * SeqCache is an abbreviation for Sequential Cache. + * + * The Cache is intended to improve performance of small unaligned sequential + * writes. Cache has a cluster_size parameter and the unit of caching is aligned + * cluster. Cache has a list of cached clusters, several "finished" ones and at + * most one "unfinished". "unfinished" cluster is a cluster where last byte of + * last write operation is cached and there is a free place after that byte to + * the end of cluster. "finished" clusters are just stored in cache to be read + * or flushed and don't allow any writes to them. + * + * If write to the cache intersects cluster bounds, it's splat into several *split (Though I like “splat”. Sounds like a wet blotch.) + * requests by cluster bounds. So, consider a write that doesn't intersect + * cluster bounds to describe the whole picture: + * + * There are two cases allowed: + * + * 1. Sequential write to "unfinished" cluster. Actually it's a write sequential + * previous write. The data goes to "unfinished" cluster. If "unfinished" is + * filled up to the cluster bound it becomes "finished". + * + * 2. Write to new cluster, not existing in the cache. It may be sequential to + * previous write or not. Current "unfinshed" cluster (if exists) becomes *unfinished + * "finished" and new "unfinished" cluster is started. Note also that offset + * of the write to new cluster is not required to be aligned. + * + * Any other write operation (non-sequential write to "unfinished" cluster + * or write to any of "finished" clusters) will crash. + */ + +#include "qemu/osdep.h" + +#include "qemu/queue.h" +#include "qemu/seqcache.h" + +/* + * Cluster + * + * Representation of one cached cluster, aligned to SeqCache::cluster_size. + * Caches only one subregion of the cluster, started at @offset (may be + * unaligned to cluster_size) and of @bytes length (may be unaligned as well). + * The whole subregion always lay in one aligned cluster: + * + * QEMU_ALIGN_DOWN(offset, cluster_size) == + * QEMU_ALIGN_DOWN(offset + bytes - 1, cluster_size) + * + * @buf is allocated to be able to fill the cluster up to the cluster end, i.e. + *
Re: [PATCH v3 4/6] util: implement seqcache
On 05.03.21 18:35, Vladimir Sementsov-Ogievskiy wrote:
Implement cache for small sequential unaligned writes, so that they may
be cached until we get a complete cluster and then write it.
The cache is intended to be used for backup to qcow2 compressed target
opened in O_DIRECT mode, but can be reused for any similar (even not
block-layer related) task.
Signed-off-by: Vladimir Sementsov-Ogievskiy
---
include/qemu/seqcache.h | 42 +
util/seqcache.c | 361
MAINTAINERS | 6 +
util/meson.build| 1 +
4 files changed, 410 insertions(+)
create mode 100644 include/qemu/seqcache.h
create mode 100644 util/seqcache.c
Looks quite good to me, thanks. Nice explanations, too. :)
The only design question I have is whether there’s a reason you’re using
a list again instead of a hash table. I suppose we do need the list
anyway because of the next_flush iterator, so using a hash table would
only complicate the implementation, but still.
[...]
diff --git a/util/seqcache.c b/util/seqcache.c
new file mode 100644
index 00..d923560eab
--- /dev/null
+++ b/util/seqcache.c
@@ -0,0 +1,361 @@
+/*
+ * Cache for small sequential write requests.
+ *
+ * Copyright (c) 2021 Virtuozzo International GmbH.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ *
+ *
+ * = Description =
+ *
+ * SeqCache is an abbreviation for Sequential Cache.
+ *
+ * The Cache is intended to improve performance of small unaligned sequential
+ * writes. Cache has a cluster_size parameter and the unit of caching is
aligned
+ * cluster. Cache has a list of cached clusters, several "finished" ones and
at
+ * most one "unfinished". "unfinished" cluster is a cluster where last byte of
+ * last write operation is cached and there is a free place after that byte to
+ * the end of cluster. "finished" clusters are just stored in cache to be read
+ * or flushed and don't allow any writes to them.
+ *
+ * If write to the cache intersects cluster bounds, it's splat into several
*split
(Though I like “splat”. Sounds like a wet blotch.)
+ * requests by cluster bounds. So, consider a write that doesn't intersect
+ * cluster bounds to describe the whole picture:
+ *
+ * There are two cases allowed:
+ *
+ * 1. Sequential write to "unfinished" cluster. Actually it's a write
sequential
+ *previous write. The data goes to "unfinished" cluster. If "unfinished" is
+ *filled up to the cluster bound it becomes "finished".
+ *
+ * 2. Write to new cluster, not existing in the cache. It may be sequential to
+ *previous write or not. Current "unfinshed" cluster (if exists) becomes
*unfinished
+ *"finished" and new "unfinished" cluster is started. Note also that offset
+ *of the write to new cluster is not required to be aligned.
+ *
+ *Any other write operation (non-sequential write to "unfinished" cluster
+ *or write to any of "finished" clusters) will crash.
+ */
+
+#include "qemu/osdep.h"
+
+#include "qemu/queue.h"
+#include "qemu/seqcache.h"
+
+/*
+ * Cluster
+ *
+ * Representation of one cached cluster, aligned to SeqCache::cluster_size.
+ * Caches only one subregion of the cluster, started at @offset (may be
+ * unaligned to cluster_size) and of @bytes length (may be unaligned as well).
+ * The whole subregion always lay in one aligned cluster:
+ *
+ * QEMU_ALIGN_DOWN(offset, cluster_size) ==
+ * QEMU_ALIGN_DOWN(offset + bytes - 1, cluster_size)
+ *
+ * @buf is allocated to be able to fill the cluster up to the cluster end, i.e.
+ * allocated @buf length is at least:
+ *
+ * cluster_size - offset % cluster_size
+ */
+typedef struct Cluster {
+ int64_t offset;
+ int64_t bytes;
+ uint8_t *buf;
+ QSIMPLEQ_ENTRY(Cluster) entry;
+} Cluster;
+
+/*
+ * SeqCache caches small sequential writes into "unfinished" @cur_write
cluster,
+ * until entire cluster (of @cluster_size bytes) is filled
[PATCH v3 4/6] util: implement seqcache
Implement cache for small sequential unaligned writes, so that they may be cached until we get a complete cluster and then write it. The cache is intended to be used for backup to qcow2 compressed target opened in O_DIRECT mode, but can be reused for any similar (even not block-layer related) task. Signed-off-by: Vladimir Sementsov-Ogievskiy --- include/qemu/seqcache.h | 42 + util/seqcache.c | 361 MAINTAINERS | 6 + util/meson.build| 1 + 4 files changed, 410 insertions(+) create mode 100644 include/qemu/seqcache.h create mode 100644 util/seqcache.c diff --git a/include/qemu/seqcache.h b/include/qemu/seqcache.h new file mode 100644 index 00..a308d54b01 --- /dev/null +++ b/include/qemu/seqcache.h @@ -0,0 +1,42 @@ +/* + * Cache for small sequential write requests. + * + * Copyright (c) 2021 Virtuozzo International GmbH. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#ifndef QEMU_SEQCACHE_H +#define QEMU_SEQCACHE_H + +typedef struct SeqCache SeqCache; + +SeqCache *seqcache_new(int64_t cluster_size); +void seqcache_free(SeqCache *s); + +void seqcache_write(SeqCache *s, int64_t offset, int64_t bytes, uint8_t *buf); +int64_t seqcache_read(SeqCache *s, int64_t offset, int64_t bytes, uint8_t *buf); + +bool seqcache_get_next_flush(SeqCache *s, int64_t *offset, int64_t *bytes, + uint8_t **buf, bool *unfinished); +void seqcache_discard_cluster(SeqCache *s, int64_t offset); + +uint64_t seqcache_nb_clusters(SeqCache *s); + +#endif /* QEMU_SEQCACHE_H */ diff --git a/util/seqcache.c b/util/seqcache.c new file mode 100644 index 00..d923560eab --- /dev/null +++ b/util/seqcache.c @@ -0,0 +1,361 @@ +/* + * Cache for small sequential write requests. + * + * Copyright (c) 2021 Virtuozzo International GmbH. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + * + * = Description = + * + * SeqCache is an abbreviation for Sequential Cache. + * + * The Cache is intended to improve performance of small unaligned sequential + * writes. Cache has a cluster_size parameter and the unit of caching is aligned + * cluster. Cache has a list of cached clusters, several "finished" ones and at + * most one "unfinished". "unfinished" cluster is a cluster where last byte of + * last write operation is cached and there is a free place after that byte to + * the end of cluster. "finished" clusters are just stored in cache to be read + * or flushed and don't allow any writes to them. + * + * If write to the cache intersects cluster bounds, it's splat into several + * requests by cluster bounds. So, consider a write that doesn't intersect + * cluster bounds to describe the whole picture: + * + * There are two cases allowed: + * + * 1. Sequential write to "unfinished" cluster. Actually it's a write sequential + *previous write. The data goes to
