1 /*
2 * virdomainmomentobjlist.c: handle snapshot/checkpoint objects
3 * (derived from snapshot_conf.c)
4 *
5 * Copyright (C) 2006-2019 Red Hat, Inc.
6 * Copyright (C) 2006-2008 Daniel P. Berrange
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library. If not, see
20 * <http://www.gnu.org/licenses/>.
21 */
22
23 #include <config.h>
24
25 #include "internal.h"
26 #include "virdomainmomentobjlist.h"
27 #include "virlog.h"
28 #include "virerror.h"
29 #include "virstring.h"
30 #include "moment_conf.h"
31 #include "viralloc.h"
32
33 /* FIXME: using virObject would allow us to not need this */
34 #include "virdomainsnapshotobjlist.h"
35 #include "virdomaincheckpointobjlist.h"
36
37 #define VIR_FROM_THIS VIR_FROM_DOMAIN
38
39 VIR_LOG_INIT("conf.virdomainmomentobjlist");
40
41 /* Opaque struct */
42 struct _virDomainMomentObjList {
43 /* name string -> virDomainMomentObj mapping
44 * for O(1), lockless lookup-by-name */
45 GHashTable *objs;
46
47 virDomainMomentObj metaroot; /* Special parent of all root moments */
48 virDomainMomentObj *current; /* The current moment, if any */
49 };
50
51
52 /* Run iter(data) on all direct children of moment, while ignoring all
53 * other entries in moments. Return the number of children
54 * visited. No particular ordering is guaranteed. */
55 int
virDomainMomentForEachChild(virDomainMomentObj * moment,virHashIterator iter,void * data)56 virDomainMomentForEachChild(virDomainMomentObj *moment,
57 virHashIterator iter,
58 void *data)
59 {
60 virDomainMomentObj *child = moment->first_child;
61
62 while (child) {
63 virDomainMomentObj *next = child->sibling;
64 (iter)(child, child->def->name, data);
65 child = next;
66 }
67
68 return moment->nchildren;
69 }
70
71 struct moment_act_on_descendant {
72 int number;
73 virHashIterator iter;
74 void *data;
75 };
76
77 static int
virDomainMomentActOnDescendant(void * payload,const char * name,void * data)78 virDomainMomentActOnDescendant(void *payload,
79 const char *name,
80 void *data)
81 {
82 virDomainMomentObj *obj = payload;
83 struct moment_act_on_descendant *curr = data;
84 virDomainMomentObj tmp = *obj;
85
86 /* Careful: curr->iter can delete obj, hence the need for tmp */
87 (curr->iter)(payload, name, curr->data);
88 curr->number += 1 + virDomainMomentForEachDescendant(&tmp,
89 curr->iter,
90 curr->data);
91 return 0;
92 }
93
94 /* Run iter(data) on all descendants of moment, while ignoring all
95 * other entries in moments. Return the number of descendants
96 * visited. The visit is guaranteed to be topological, but no
97 * particular order between siblings is guaranteed. */
98 int
virDomainMomentForEachDescendant(virDomainMomentObj * moment,virHashIterator iter,void * data)99 virDomainMomentForEachDescendant(virDomainMomentObj *moment,
100 virHashIterator iter,
101 void *data)
102 {
103 struct moment_act_on_descendant act;
104
105 act.number = 0;
106 act.iter = iter;
107 act.data = data;
108 virDomainMomentForEachChild(moment,
109 virDomainMomentActOnDescendant, &act);
110
111 return act.number;
112 }
113
114
115 /* Prepare to reparent or delete moment, by removing it from its
116 * current listed parent. Note that when bulk removing all children
117 * of a parent, it is faster to just 0 the count rather than calling
118 * this function on each child. */
119 void
virDomainMomentDropParent(virDomainMomentObj * moment)120 virDomainMomentDropParent(virDomainMomentObj *moment)
121 {
122 virDomainMomentObj *prev = NULL;
123 virDomainMomentObj *curr = NULL;
124
125 moment->parent->nchildren--;
126 curr = moment->parent->first_child;
127 while (curr != moment) {
128 if (!curr) {
129 VIR_WARN("inconsistent moment relations");
130 return;
131 }
132 prev = curr;
133 curr = curr->sibling;
134 }
135 if (prev)
136 prev->sibling = g_steal_pointer(&moment->sibling);
137 else
138 moment->parent->first_child = g_steal_pointer(&moment->sibling);
139 moment->parent = NULL;
140 }
141
142
143 /* Update @moment to no longer have children. */
144 void
virDomainMomentDropChildren(virDomainMomentObj * moment)145 virDomainMomentDropChildren(virDomainMomentObj *moment)
146 {
147 moment->nchildren = 0;
148 moment->first_child = NULL;
149 }
150
151
152 /* Add @moment to @parent's list of children. */
153 static void
virDomainMomentSetParent(virDomainMomentObj * moment,virDomainMomentObj * parent)154 virDomainMomentSetParent(virDomainMomentObj *moment,
155 virDomainMomentObj *parent)
156 {
157 moment->parent = parent;
158 parent->nchildren++;
159 moment->sibling = parent->first_child;
160 parent->first_child = moment;
161 }
162
163
164 /* Add @moment to the appropriate parent's list of children. The
165 * caller must ensure that moment->def->parent_name is either NULL
166 * (for a new root) or set to an existing moment already in the
167 * list. */
168 void
virDomainMomentLinkParent(virDomainMomentObjList * moments,virDomainMomentObj * moment)169 virDomainMomentLinkParent(virDomainMomentObjList *moments,
170 virDomainMomentObj *moment)
171 {
172 virDomainMomentObj *parent;
173
174 parent = virDomainMomentFindByName(moments, moment->def->parent_name);
175 if (!parent) {
176 parent = &moments->metaroot;
177 if (moment->def->parent_name)
178 VIR_WARN("moment %s lacks parent %s", moment->def->name,
179 moment->def->parent_name);
180 }
181 virDomainMomentSetParent(moment, parent);
182 }
183
184
185 /* Take all children of @from and convert them into children of @to. */
186 void
virDomainMomentMoveChildren(virDomainMomentObj * from,virDomainMomentObj * to)187 virDomainMomentMoveChildren(virDomainMomentObj *from,
188 virDomainMomentObj *to)
189 {
190 virDomainMomentObj *child = from->first_child;
191
192 if (!from->nchildren)
193 return;
194 while (child) {
195 child->parent = to;
196 if (!child->sibling) {
197 child->sibling = to->first_child;
198 break;
199 }
200 child = child->sibling;
201 }
202 to->nchildren += from->nchildren;
203 to->first_child = g_steal_pointer(&from->first_child);
204 from->nchildren = 0;
205 }
206
207
208 static virDomainMomentObj *
virDomainMomentObjNew(void)209 virDomainMomentObjNew(void)
210 {
211 virDomainMomentObj *moment;
212
213 moment = g_new0(virDomainMomentObj, 1);
214
215 VIR_DEBUG("obj=%p", moment);
216
217 return moment;
218 }
219
220
221 static void
virDomainMomentObjFree(virDomainMomentObj * moment)222 virDomainMomentObjFree(virDomainMomentObj *moment)
223 {
224 if (!moment)
225 return;
226
227 VIR_DEBUG("obj=%p", moment);
228
229 virObjectUnref(moment->def);
230 g_free(moment);
231 }
232
233
234 /* Add def to the list and return a matching object, or NULL on error */
235 virDomainMomentObj *
virDomainMomentAssignDef(virDomainMomentObjList * moments,virDomainMomentDef * def)236 virDomainMomentAssignDef(virDomainMomentObjList *moments,
237 virDomainMomentDef *def)
238 {
239 virDomainMomentObj *moment;
240
241 if (virHashLookup(moments->objs, def->name) != NULL) {
242 virReportError(VIR_ERR_OPERATION_FAILED,
243 _("domain moment %s already exists"),
244 def->name);
245 return NULL;
246 }
247
248 if (!(moment = virDomainMomentObjNew()))
249 return NULL;
250
251 if (virHashAddEntry(moments->objs, def->name, moment) < 0) {
252 VIR_FREE(moment);
253 return NULL;
254 }
255 moment->def = def;
256
257 return moment;
258 }
259
260
261 static void
virDomainMomentObjListDataFree(void * payload)262 virDomainMomentObjListDataFree(void *payload)
263 {
264 virDomainMomentObj *obj = payload;
265
266 virDomainMomentObjFree(obj);
267 }
268
269
270 virDomainMomentObjList *
virDomainMomentObjListNew(void)271 virDomainMomentObjListNew(void)
272 {
273 virDomainMomentObjList *moments;
274
275 moments = g_new0(virDomainMomentObjList, 1);
276 moments->objs = virHashNew(virDomainMomentObjListDataFree);
277 return moments;
278 }
279
280 void
virDomainMomentObjListFree(virDomainMomentObjList * moments)281 virDomainMomentObjListFree(virDomainMomentObjList *moments)
282 {
283 if (!moments)
284 return;
285 virHashFree(moments->objs);
286 g_free(moments);
287 }
288
289
290 /* Struct and callback for collecting a list of names of moments that
291 * meet a particular filter. */
292 struct virDomainMomentNameData {
293 char **const names;
294 int maxnames;
295 unsigned int flags;
296 int count;
297 bool error;
298 virDomainMomentObjListFilter filter;
299 unsigned int filter_flags;
300 };
301
302
virDomainMomentObjListCopyNames(void * payload,const char * name G_GNUC_UNUSED,void * opaque)303 static int virDomainMomentObjListCopyNames(void *payload,
304 const char *name G_GNUC_UNUSED,
305 void *opaque)
306 {
307 virDomainMomentObj *obj = payload;
308 struct virDomainMomentNameData *data = opaque;
309
310 if (data->error)
311 return 0;
312 /* Caller already sanitized flags. Filtering on DESCENDANTS was
313 * done by choice of iteration in the caller. */
314 if ((data->flags & VIR_DOMAIN_MOMENT_LIST_LEAVES) && obj->nchildren)
315 return 0;
316 if ((data->flags & VIR_DOMAIN_MOMENT_LIST_NO_LEAVES) && !obj->nchildren)
317 return 0;
318
319 if (!data->filter(obj, data->filter_flags))
320 return 0;
321
322 if (data->names && data->count < data->maxnames)
323 data->names[data->count] = g_strdup(obj->def->name);
324 data->count++;
325 return 0;
326 }
327
328
329 int
virDomainMomentObjListGetNames(virDomainMomentObjList * moments,virDomainMomentObj * from,char ** const names,int maxnames,unsigned int flags,virDomainMomentObjListFilter filter,unsigned int filter_flags)330 virDomainMomentObjListGetNames(virDomainMomentObjList *moments,
331 virDomainMomentObj *from,
332 char **const names,
333 int maxnames,
334 unsigned int flags,
335 virDomainMomentObjListFilter filter,
336 unsigned int filter_flags)
337 {
338 struct virDomainMomentNameData data = { names, maxnames, flags, 0,
339 false, filter, filter_flags };
340 size_t i;
341
342 virCheckFlags(VIR_DOMAIN_MOMENT_FILTERS_ALL, -1);
343 if (!from) {
344 /* LIST_ROOTS and LIST_DESCENDANTS have the same bit value,
345 * but opposite semantics. Toggle here to get the correct
346 * traversal on the metaroot. */
347 flags ^= VIR_DOMAIN_MOMENT_LIST_ROOTS;
348 from = &moments->metaroot;
349 }
350
351 /* We handle LIST_ROOT/LIST_DESCENDANTS and LIST_TOPOLOGICAL directly,
352 * mask those bits out to determine when we must use the filter callback. */
353 data.flags &= ~(VIR_DOMAIN_MOMENT_LIST_DESCENDANTS |
354 VIR_DOMAIN_MOMENT_LIST_TOPOLOGICAL);
355
356 /* If this common code is being used, we assume that all moments
357 * have metadata, and thus can handle METADATA up front as an
358 * all-or-none filter. XXX This might not always be true, if we
359 * add the ability to track qcow2 internal snapshots without the
360 * use of metadata, in which case this check should move into the
361 * filter callback. */
362 if ((data.flags & VIR_DOMAIN_MOMENT_FILTERS_METADATA) ==
363 VIR_DOMAIN_MOMENT_LIST_NO_METADATA)
364 return 0;
365 data.flags &= ~VIR_DOMAIN_MOMENT_FILTERS_METADATA;
366
367 if (flags & VIR_DOMAIN_MOMENT_LIST_DESCENDANTS) {
368 /* We could just always do a topological visit; but it is
369 * possible to optimize for less stack usage and time when a
370 * simpler full hashtable visit or counter will do. */
371 if (from->def || (names &&
372 (flags & VIR_DOMAIN_MOMENT_LIST_TOPOLOGICAL)))
373 virDomainMomentForEachDescendant(from,
374 virDomainMomentObjListCopyNames,
375 &data);
376 else if (names || data.flags || filter_flags)
377 virHashForEach(moments->objs, virDomainMomentObjListCopyNames,
378 &data);
379 else
380 data.count = virHashSize(moments->objs);
381 } else if (names || data.flags || filter_flags) {
382 virDomainMomentForEachChild(from,
383 virDomainMomentObjListCopyNames, &data);
384 } else {
385 data.count = from->nchildren;
386 }
387
388 if (data.error) {
389 for (i = 0; i < data.count; i++)
390 VIR_FREE(names[i]);
391 return -1;
392 }
393
394 return data.count;
395 }
396
397
398 virDomainMomentObj *
virDomainMomentFindByName(virDomainMomentObjList * moments,const char * name)399 virDomainMomentFindByName(virDomainMomentObjList *moments,
400 const char *name)
401 {
402 if (name)
403 return virHashLookup(moments->objs, name);
404 return NULL;
405 }
406
407
408 /* Return the current moment, or NULL */
409 virDomainMomentObj *
virDomainMomentGetCurrent(virDomainMomentObjList * moments)410 virDomainMomentGetCurrent(virDomainMomentObjList *moments)
411 {
412 return moments->current;
413 }
414
415
416 /* Return the current moment's name, or NULL */
417 const char *
virDomainMomentGetCurrentName(virDomainMomentObjList * moments)418 virDomainMomentGetCurrentName(virDomainMomentObjList *moments)
419 {
420 if (moments->current)
421 return moments->current->def->name;
422 return NULL;
423 }
424
425
426 /* Update the current moment, using NULL if no current remains */
427 void
virDomainMomentSetCurrent(virDomainMomentObjList * moments,virDomainMomentObj * moment)428 virDomainMomentSetCurrent(virDomainMomentObjList *moments,
429 virDomainMomentObj *moment)
430 {
431 moments->current = moment;
432 }
433
434
435 /* Return the number of moments in the list */
436 int
virDomainMomentObjListSize(virDomainMomentObjList * moments)437 virDomainMomentObjListSize(virDomainMomentObjList *moments)
438 {
439 return virHashSize(moments->objs);
440 }
441
442
443 /* Remove moment from the list; return true if it was current */
444 bool
virDomainMomentObjListRemove(virDomainMomentObjList * moments,virDomainMomentObj * moment)445 virDomainMomentObjListRemove(virDomainMomentObjList *moments,
446 virDomainMomentObj *moment)
447 {
448 bool ret = moments->current == moment;
449
450 virHashRemoveEntry(moments->objs, moment->def->name);
451 if (ret)
452 moments->current = NULL;
453 return ret;
454 }
455
456
457 /* Remove all moments tracked in the list */
458 void
virDomainMomentObjListRemoveAll(virDomainMomentObjList * moments)459 virDomainMomentObjListRemoveAll(virDomainMomentObjList *moments)
460 {
461 virHashRemoveAll(moments->objs);
462 virDomainMomentDropChildren(&moments->metaroot);
463 }
464
465
466 /* Call iter on each member of the list, in unspecified order */
467 int
virDomainMomentForEach(virDomainMomentObjList * moments,virHashIterator iter,void * data)468 virDomainMomentForEach(virDomainMomentObjList *moments,
469 virHashIterator iter,
470 void *data)
471 {
472 return virHashForEachSafe(moments->objs, iter, data);
473 }
474
475
476 /* Struct and callback function used as a hash table callback; each call
477 * inspects the pre-existing moment->def->parent_name field, and adjusts
478 * the moment->parent field as well as the parent's child fields to
479 * wire up the hierarchical relations for the given moment. The error
480 * indicator gets set if a parent is missing or a requested parent would
481 * cause a circular parent chain. */
482 struct moment_set_relation {
483 virDomainMomentObjList *moments;
484 int err;
485 };
486 static int
virDomainMomentSetRelations(void * payload,const char * name G_GNUC_UNUSED,void * data)487 virDomainMomentSetRelations(void *payload,
488 const char *name G_GNUC_UNUSED,
489 void *data)
490 {
491 virDomainMomentObj *obj = payload;
492 struct moment_set_relation *curr = data;
493 virDomainMomentObj *tmp;
494 virDomainMomentObj *parent;
495
496 parent = virDomainMomentFindByName(curr->moments, obj->def->parent_name);
497 if (!parent) {
498 parent = &curr->moments->metaroot;
499 if (obj->def->parent_name) {
500 curr->err = -1;
501 VIR_WARN("moment %s lacks parent %s", obj->def->name,
502 obj->def->parent_name);
503 }
504 } else {
505 tmp = parent;
506 while (tmp && tmp->def) {
507 if (tmp == obj) {
508 curr->err = -1;
509 parent = &curr->moments->metaroot;
510 VIR_WARN("moment %s in circular chain", obj->def->name);
511 break;
512 }
513 tmp = tmp->parent;
514 }
515 }
516 virDomainMomentSetParent(obj, parent);
517 return 0;
518 }
519
520
521 /* Populate parent link and child count of all moments, with all
522 * assigned defs having relations starting as 0/NULL. Return 0 on
523 * success, -1 if a parent is missing or if a circular relationship
524 * was requested. */
525 int
virDomainMomentUpdateRelations(virDomainMomentObjList * moments)526 virDomainMomentUpdateRelations(virDomainMomentObjList *moments)
527 {
528 struct moment_set_relation act = { moments, 0 };
529
530 virDomainMomentDropChildren(&moments->metaroot);
531 virHashForEach(moments->objs, virDomainMomentSetRelations, &act);
532 if (act.err)
533 moments->current = NULL;
534 return act.err;
535 }
536
537
538 /* Check that inserting def into list would not create any impossible
539 * parent-child relationships (cycles or missing parents). Return 0
540 * on success, or report an error on behalf of domname before
541 * returning -1. */
542 int
virDomainMomentCheckCycles(virDomainMomentObjList * list,virDomainMomentDef * def,const char * domname)543 virDomainMomentCheckCycles(virDomainMomentObjList *list,
544 virDomainMomentDef *def,
545 const char *domname)
546 {
547 virDomainMomentObj *other;
548
549 if (def->parent_name) {
550 if (STREQ(def->name, def->parent_name)) {
551 virReportError(VIR_ERR_INVALID_ARG,
552 _("cannot set moment %s as its own parent"),
553 def->name);
554 return -1;
555 }
556 other = virDomainMomentFindByName(list, def->parent_name);
557 if (!other) {
558 virReportError(VIR_ERR_INVALID_ARG,
559 _("parent %s for moment %s not found"),
560 def->parent_name, def->name);
561 return -1;
562 }
563 while (other->def->parent_name) {
564 if (STREQ(other->def->parent_name, def->name)) {
565 virReportError(VIR_ERR_INVALID_ARG,
566 _("parent %s would create cycle to %s"),
567 other->def->name, def->name);
568 return -1;
569 }
570 other = virDomainMomentFindByName(list, other->def->parent_name);
571 if (!other) {
572 VIR_WARN("moments are inconsistent for domain %s",
573 domname);
574 break;
575 }
576 }
577 }
578 return 0;
579 }
580
581 /* If there is exactly one leaf node, return that node. */
582 virDomainMomentObj *
virDomainMomentFindLeaf(virDomainMomentObjList * list)583 virDomainMomentFindLeaf(virDomainMomentObjList *list)
584 {
585 virDomainMomentObj *moment = &list->metaroot;
586
587 if (moment->nchildren != 1)
588 return NULL;
589 while (moment->nchildren == 1)
590 moment = moment->first_child;
591 if (moment->nchildren == 0)
592 return moment;
593 return NULL;
594 }
595