]> git.proxmox.com Git - mirror_qemu.git/blob - tests/unit/test-bdrv-graph-mod.c
block: use topological sort for permission update
[mirror_qemu.git] / tests / unit / test-bdrv-graph-mod.c
1 /*
2 * Block node graph modifications tests
3 *
4 * Copyright (c) 2019-2021 Virtuozzo International GmbH. All rights reserved.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 *
19 */
20
21 #include "qemu/osdep.h"
22 #include "qapi/error.h"
23 #include "qemu/main-loop.h"
24 #include "block/block_int.h"
25 #include "sysemu/block-backend.h"
26
27 static BlockDriver bdrv_pass_through = {
28 .format_name = "pass-through",
29 .bdrv_child_perm = bdrv_default_perms,
30 };
31
32 static void no_perm_default_perms(BlockDriverState *bs, BdrvChild *c,
33 BdrvChildRole role,
34 BlockReopenQueue *reopen_queue,
35 uint64_t perm, uint64_t shared,
36 uint64_t *nperm, uint64_t *nshared)
37 {
38 *nperm = 0;
39 *nshared = BLK_PERM_ALL;
40 }
41
42 static BlockDriver bdrv_no_perm = {
43 .format_name = "no-perm",
44 .bdrv_child_perm = no_perm_default_perms,
45 };
46
47 static void exclusive_write_perms(BlockDriverState *bs, BdrvChild *c,
48 BdrvChildRole role,
49 BlockReopenQueue *reopen_queue,
50 uint64_t perm, uint64_t shared,
51 uint64_t *nperm, uint64_t *nshared)
52 {
53 *nperm = BLK_PERM_WRITE;
54 *nshared = BLK_PERM_ALL & ~BLK_PERM_WRITE;
55 }
56
57 static BlockDriver bdrv_exclusive_writer = {
58 .format_name = "exclusive-writer",
59 .bdrv_child_perm = exclusive_write_perms,
60 };
61
62 static BlockDriverState *no_perm_node(const char *name)
63 {
64 return bdrv_new_open_driver(&bdrv_no_perm, name, BDRV_O_RDWR, &error_abort);
65 }
66
67 static BlockDriverState *pass_through_node(const char *name)
68 {
69 return bdrv_new_open_driver(&bdrv_pass_through, name,
70 BDRV_O_RDWR, &error_abort);
71 }
72
73 static BlockDriverState *exclusive_writer_node(const char *name)
74 {
75 return bdrv_new_open_driver(&bdrv_exclusive_writer, name,
76 BDRV_O_RDWR, &error_abort);
77 }
78
79 /*
80 * test_update_perm_tree
81 *
82 * When checking node for a possibility to update permissions, it's subtree
83 * should be correctly checked too. New permissions for each node should be
84 * calculated and checked in context of permissions of other nodes. If we
85 * check new permissions of the node only in context of old permissions of
86 * its neighbors, we can finish up with wrong permission graph.
87 *
88 * This test firstly create the following graph:
89 * +--------+
90 * | root |
91 * +--------+
92 * |
93 * | perm: write, read
94 * | shared: except write
95 * v
96 * +-------------------+ +----------------+
97 * | passtrough filter |---------->| null-co node |
98 * +-------------------+ +----------------+
99 *
100 *
101 * and then, tries to append filter under node. Expected behavior: fail.
102 * Otherwise we'll get the following picture, with two BdrvChild'ren, having
103 * write permission to one node, without actually sharing it.
104 *
105 * +--------+
106 * | root |
107 * +--------+
108 * |
109 * | perm: write, read
110 * | shared: except write
111 * v
112 * +-------------------+
113 * | passtrough filter |
114 * +-------------------+
115 * | |
116 * perm: write, read | | perm: write, read
117 * shared: except write | | shared: except write
118 * v v
119 * +----------------+
120 * | null co node |
121 * +----------------+
122 */
123 static void test_update_perm_tree(void)
124 {
125 int ret;
126
127 BlockBackend *root = blk_new(qemu_get_aio_context(),
128 BLK_PERM_WRITE | BLK_PERM_CONSISTENT_READ,
129 BLK_PERM_ALL & ~BLK_PERM_WRITE);
130 BlockDriverState *bs = no_perm_node("node");
131 BlockDriverState *filter = pass_through_node("filter");
132
133 blk_insert_bs(root, bs, &error_abort);
134
135 bdrv_attach_child(filter, bs, "child", &child_of_bds,
136 BDRV_CHILD_FILTERED | BDRV_CHILD_PRIMARY, &error_abort);
137
138 ret = bdrv_append(filter, bs, NULL);
139 g_assert_cmpint(ret, <, 0);
140
141 bdrv_unref(filter);
142 blk_unref(root);
143 }
144
145 /*
146 * test_should_update_child
147 *
148 * Test that bdrv_replace_node, and concretely should_update_child
149 * do the right thing, i.e. not creating loops on the graph.
150 *
151 * The test does the following:
152 * 1. initial graph:
153 *
154 * +------+ +--------+
155 * | root | | filter |
156 * +------+ +--------+
157 * | |
158 * root| target|
159 * v v
160 * +------+ +--------+
161 * | node |<---------| target |
162 * +------+ backing +--------+
163 *
164 * 2. Append @filter above @node. If should_update_child works correctly,
165 * it understands, that backing child of @target should not be updated,
166 * as it will create a loop on node graph. Resulting picture should
167 * be the left one, not the right:
168 *
169 * +------+ +------+
170 * | root | | root |
171 * +------+ +------+
172 * | |
173 * root| root|
174 * v v
175 * +--------+ target +--------+ target
176 * | filter |--------------+ | filter |--------------+
177 * +--------+ | +--------+ |
178 * | | | ^ v
179 * backing| | backing| | +--------+
180 * v v | +-----------| target |
181 * +------+ +--------+ v backing +--------+
182 * | node |<---------| target | +------+
183 * +------+ backing +--------+ | node |
184 * +------+
185 *
186 * (good picture) (bad picture)
187 *
188 */
189 static void test_should_update_child(void)
190 {
191 BlockBackend *root = blk_new(qemu_get_aio_context(), 0, BLK_PERM_ALL);
192 BlockDriverState *bs = no_perm_node("node");
193 BlockDriverState *filter = no_perm_node("filter");
194 BlockDriverState *target = no_perm_node("target");
195
196 blk_insert_bs(root, bs, &error_abort);
197
198 bdrv_set_backing_hd(target, bs, &error_abort);
199
200 g_assert(target->backing->bs == bs);
201 bdrv_attach_child(filter, target, "target", &child_of_bds,
202 BDRV_CHILD_DATA, &error_abort);
203 bdrv_append(filter, bs, &error_abort);
204 g_assert(target->backing->bs == bs);
205
206 bdrv_unref(filter);
207 bdrv_unref(bs);
208 blk_unref(root);
209 }
210
211 /*
212 * test_parallel_exclusive_write
213 *
214 * Check that when we replace node, old permissions of the node being removed
215 * doesn't break the replacement.
216 */
217 static void test_parallel_exclusive_write(void)
218 {
219 BlockDriverState *top = exclusive_writer_node("top");
220 BlockDriverState *base = no_perm_node("base");
221 BlockDriverState *fl1 = pass_through_node("fl1");
222 BlockDriverState *fl2 = pass_through_node("fl2");
223
224 /*
225 * bdrv_attach_child() eats child bs reference, so we need two @base
226 * references for two filters:
227 */
228 bdrv_ref(base);
229
230 bdrv_attach_child(top, fl1, "backing", &child_of_bds, BDRV_CHILD_DATA,
231 &error_abort);
232 bdrv_attach_child(fl1, base, "backing", &child_of_bds, BDRV_CHILD_FILTERED,
233 &error_abort);
234 bdrv_attach_child(fl2, base, "backing", &child_of_bds, BDRV_CHILD_FILTERED,
235 &error_abort);
236
237 bdrv_replace_node(fl1, fl2, &error_abort);
238
239 bdrv_unref(fl2);
240 bdrv_unref(top);
241 }
242
243 static void write_to_file_perms(BlockDriverState *bs, BdrvChild *c,
244 BdrvChildRole role,
245 BlockReopenQueue *reopen_queue,
246 uint64_t perm, uint64_t shared,
247 uint64_t *nperm, uint64_t *nshared)
248 {
249 if (bs->file && c == bs->file) {
250 *nperm = BLK_PERM_WRITE;
251 *nshared = BLK_PERM_ALL & ~BLK_PERM_WRITE;
252 } else {
253 *nperm = 0;
254 *nshared = BLK_PERM_ALL;
255 }
256 }
257
258 static BlockDriver bdrv_write_to_file = {
259 .format_name = "tricky-perm",
260 .bdrv_child_perm = write_to_file_perms,
261 };
262
263
264 /*
265 * The following test shows that topological-sort order is required for
266 * permission update, simple DFS is not enough.
267 *
268 * Consider the block driver which has two filter children: one active
269 * with exclusive write access and one inactive with no specific
270 * permissions.
271 *
272 * And, these two children has a common base child, like this:
273 *
274 * ┌─────┐ ┌──────┐
275 * │ fl2 │ ◀── │ top │
276 * └─────┘ └──────┘
277 * │ │
278 * │ │ w
279 * │ ▼
280 * │ ┌──────┐
281 * │ │ fl1 │
282 * │ └──────┘
283 * │ │
284 * │ │ w
285 * │ ▼
286 * │ ┌──────┐
287 * └───────▶ │ base │
288 * └──────┘
289 *
290 * So, exclusive write is propagated.
291 *
292 * Assume, we want to make fl2 active instead of fl1.
293 * So, we set some option for top driver and do permission update.
294 *
295 * With simple DFS, if permission update goes first through
296 * top->fl1->base branch it will succeed: it firstly drop exclusive write
297 * permissions and than apply them for another BdrvChildren.
298 * But if permission update goes first through top->fl2->base branch it
299 * will fail, as when we try to update fl2->base child, old not yet
300 * updated fl1->base child will be in conflict.
301 *
302 * With topological-sort order we always update parents before children, so fl1
303 * and fl2 are both updated when we update base and there is no conflict.
304 */
305 static void test_parallel_perm_update(void)
306 {
307 BlockDriverState *top = no_perm_node("top");
308 BlockDriverState *tricky =
309 bdrv_new_open_driver(&bdrv_write_to_file, "tricky", BDRV_O_RDWR,
310 &error_abort);
311 BlockDriverState *base = no_perm_node("base");
312 BlockDriverState *fl1 = pass_through_node("fl1");
313 BlockDriverState *fl2 = pass_through_node("fl2");
314 BdrvChild *c_fl1, *c_fl2;
315
316 /*
317 * bdrv_attach_child() eats child bs reference, so we need two @base
318 * references for two filters:
319 */
320 bdrv_ref(base);
321
322 bdrv_attach_child(top, tricky, "file", &child_of_bds, BDRV_CHILD_DATA,
323 &error_abort);
324 c_fl1 = bdrv_attach_child(tricky, fl1, "first", &child_of_bds,
325 BDRV_CHILD_FILTERED, &error_abort);
326 c_fl2 = bdrv_attach_child(tricky, fl2, "second", &child_of_bds,
327 BDRV_CHILD_FILTERED, &error_abort);
328 bdrv_attach_child(fl1, base, "backing", &child_of_bds, BDRV_CHILD_FILTERED,
329 &error_abort);
330 bdrv_attach_child(fl2, base, "backing", &child_of_bds, BDRV_CHILD_FILTERED,
331 &error_abort);
332
333 /* Select fl1 as first child to be active */
334 tricky->file = c_fl1;
335 bdrv_child_refresh_perms(top, top->children.lh_first, &error_abort);
336
337 assert(c_fl1->perm & BLK_PERM_WRITE);
338 assert(!(c_fl2->perm & BLK_PERM_WRITE));
339
340 /* Now, try to switch active child and update permissions */
341 tricky->file = c_fl2;
342 bdrv_child_refresh_perms(top, top->children.lh_first, &error_abort);
343
344 assert(c_fl2->perm & BLK_PERM_WRITE);
345 assert(!(c_fl1->perm & BLK_PERM_WRITE));
346
347 /* Switch once more, to not care about real child order in the list */
348 tricky->file = c_fl1;
349 bdrv_child_refresh_perms(top, top->children.lh_first, &error_abort);
350
351 assert(c_fl1->perm & BLK_PERM_WRITE);
352 assert(!(c_fl2->perm & BLK_PERM_WRITE));
353
354 bdrv_unref(top);
355 }
356
357 /*
358 * It's possible that filter required permissions allows to insert it to backing
359 * chain, like:
360 *
361 * 1. [top] -> [filter] -> [base]
362 *
363 * but doesn't allow to add it as a branch:
364 *
365 * 2. [filter] --\
366 * v
367 * [top] -> [base]
368 *
369 * So, inserting such filter should do all graph modifications and only then
370 * update permissions. If we try to go through intermediate state [2] and update
371 * permissions on it we'll fail.
372 *
373 * Let's check that bdrv_append() can append such a filter.
374 */
375 static void test_append_greedy_filter(void)
376 {
377 BlockDriverState *top = exclusive_writer_node("top");
378 BlockDriverState *base = no_perm_node("base");
379 BlockDriverState *fl = exclusive_writer_node("fl1");
380
381 bdrv_attach_child(top, base, "backing", &child_of_bds, BDRV_CHILD_COW,
382 &error_abort);
383
384 bdrv_append(fl, base, &error_abort);
385 bdrv_unref(fl);
386 bdrv_unref(top);
387 }
388
389 int main(int argc, char *argv[])
390 {
391 int i;
392 bool debug = false;
393
394 for (i = 1; i < argc; i++) {
395 if (!strcmp(argv[i], "-d")) {
396 debug = true;
397 break;
398 }
399 }
400
401 bdrv_init();
402 qemu_init_main_loop(&error_abort);
403
404 g_test_init(&argc, &argv, NULL);
405
406 g_test_add_func("/bdrv-graph-mod/update-perm-tree", test_update_perm_tree);
407 g_test_add_func("/bdrv-graph-mod/should-update-child",
408 test_should_update_child);
409 g_test_add_func("/bdrv-graph-mod/parallel-perm-update",
410 test_parallel_perm_update);
411
412 if (debug) {
413 g_test_add_func("/bdrv-graph-mod/parallel-exclusive-write",
414 test_parallel_exclusive_write);
415 g_test_add_func("/bdrv-graph-mod/append-greedy-filter",
416 test_append_greedy_filter);
417 }
418
419 return g_test_run();
420 }