-
+/*
+ * These functions implement tree of block devices. The devtree struct contains
+ * two basic lists:
+ *
+ * 1) devtree->devices -- This is simple list without any hierarchy. We use
+ * reference counting here.
+ *
+ * 2) devtree->roots -- The root nodes of the trees. The code does not use
+ * reference counting here due to complexity and it's unnecessary.
+ *
+ * Note that the same device maybe have more parents and more children. The
+ * device is allocated only once and shared within the tree. The dependence
+ * (devdep struct) contains reference to child as well as to parent and the
+ * dependence is reference by ls_childs from parent device and by ls_parents
+ * from child. (Yes, "childs" is used for children ;-)
+ *
+ * Copyright (C) 2018 Karel Zak <kzak@redhat.com>
+ */
#include "lsblk.h"
#include "sysfs.h"
itr->direction = direction;
}
-struct lsblk_device *lsblk_new_device(struct lsblk_devtree *tree)
+struct lsblk_device *lsblk_new_device()
{
struct lsblk_device *dev;
return NULL;
dev->refcount = 1;
+ dev->removable = -1;
+ dev->discard_granularity = (uint64_t) -1;
- dev->tree = tree;
-
- INIT_LIST_HEAD(&dev->deps);
+ INIT_LIST_HEAD(&dev->childs);
+ INIT_LIST_HEAD(&dev->parents);
INIT_LIST_HEAD(&dev->ls_roots);
INIT_LIST_HEAD(&dev->ls_devices);
dev->refcount++;
}
-
-static int device_remove_dependence(struct lsblk_device *dev, struct lsblk_devdep *dep)
+/* removes dependence from child as well as from parent */
+static int remove_dependence(struct lsblk_devdep *dep)
{
- if (!dev || !dep || !list_empty(&dev->deps))
+ if (!dep)
return -EINVAL;
- DBG(DEV, ul_debugobj(dev, " remove-deallocate dependence 0x%p", dep));
- list_del_init(&dep->ls_deps);
- lsblk_unref_device(dep->child);
+ DBG(DEP, ul_debugobj(dep, " dealloc"));
+
+ list_del_init(&dep->ls_childs);
+ list_del_init(&dep->ls_parents);
+
free(dep);
return 0;
}
if (!dev)
return -EINVAL;
- DBG(DEV, ul_debugobj(dev, "remove all depencences"));
- while (!list_empty(&dev->deps)) {
- struct lsblk_devdep *dp = list_entry(dev->deps.next,
- struct lsblk_devdep, ls_deps);
- device_remove_dependence(dev, dp);
+ if (!list_empty(&dev->childs))
+ DBG(DEV, ul_debugobj(dev, " %s: remove all children deps", dev->name));
+ while (!list_empty(&dev->childs)) {
+ struct lsblk_devdep *dp = list_entry(dev->childs.next,
+ struct lsblk_devdep, ls_childs);
+ remove_dependence(dp);
+ }
+
+ if (!list_empty(&dev->parents))
+ DBG(DEV, ul_debugobj(dev, " %s: remove all parents deps", dev->name));
+ while (!list_empty(&dev->parents)) {
+ struct lsblk_devdep *dp = list_entry(dev->parents.next,
+ struct lsblk_devdep, ls_parents);
+ remove_dependence(dp);
}
+
return 0;
}
return;
if (--dev->refcount <= 0) {
- DBG(DEV, ul_debugobj(dev, "dealloc"));
+ DBG(DEV, ul_debugobj(dev, " freeing [%s] <<", dev->name));
device_remove_dependences(dev);
lsblk_device_free_properties(dev->properties);
- free(dev->name);
+ lsblk_unref_device(dev->wholedisk);
+
free(dev->dm_name);
free(dev->filename);
free(dev->mountpoint);
+ free(dev->dedupkey);
ul_unref_path(dev->sysfs);
+ DBG(DEV, ul_debugobj(dev, " >> dealloc [%s]", dev->name));
+ free(dev->name);
free(dev);
}
}
-struct lsblk_devdep *lsblk_device_new_dependence(struct lsblk_device *parent, struct lsblk_device *child)
+int lsblk_device_has_child(struct lsblk_device *dev, struct lsblk_device *child)
{
- struct lsblk_devdep *dp;
+ struct lsblk_device *x = NULL;
+ struct lsblk_iter itr;
- if (!parent || !child) {
- errno = EINVAL;
- return NULL;
+ lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
+
+ while (lsblk_device_next_child(dev, &itr, &x) == 0) {
+ if (x == child)
+ return 1;
}
+ return 0;
+}
+
+int lsblk_device_new_dependence(struct lsblk_device *parent, struct lsblk_device *child)
+{
+ struct lsblk_devdep *dp;
+
+ if (!parent || !child)
+ return -EINVAL;
+
+ if (lsblk_device_has_child(parent, child))
+ return 1;
+
dp = calloc(1, sizeof(*dp));
if (!dp)
- return NULL;
+ return -ENOMEM;
- INIT_LIST_HEAD(&dp->ls_deps);
+ INIT_LIST_HEAD(&dp->ls_childs);
+ INIT_LIST_HEAD(&dp->ls_parents);
- lsblk_ref_device(child);
dp->child = child;
+ list_add_tail(&dp->ls_childs, &parent->childs);
+
+ dp->parent = parent;
+ list_add_tail(&dp->ls_parents, &child->parents);
DBG(DEV, ul_debugobj(parent, "add dependence 0x%p [%s->%s]", dp, parent->name, child->name));
- list_add_tail(&dp->ls_deps, &parent->deps);
- return dp;
+ return 0;
+}
+
+static int device_next_child(struct lsblk_device *dev,
+ struct lsblk_iter *itr,
+ struct lsblk_devdep **dp)
+{
+ int rc = 1;
+
+ if (!dev || !itr || !dp)
+ return -EINVAL;
+ *dp = NULL;
+
+ if (!itr->head)
+ LSBLK_ITER_INIT(itr, &dev->childs);
+ if (itr->p != itr->head) {
+ LSBLK_ITER_ITERATE(itr, *dp, struct lsblk_devdep, ls_childs);
+ rc = 0;
+ }
+
+ return rc;
}
int lsblk_device_next_child(struct lsblk_device *dev,
struct lsblk_iter *itr,
struct lsblk_device **child)
+{
+ struct lsblk_devdep *dp = NULL;
+ int rc = device_next_child(dev, itr, &dp);
+
+ if (!child)
+ return -EINVAL;
+
+ *child = rc == 0 ? dp->child : NULL;
+ return rc;
+}
+
+int lsblk_device_is_last_parent(struct lsblk_device *dev, struct lsblk_device *parent)
+{
+ struct lsblk_devdep *dp = list_last_entry(
+ &dev->parents,
+ struct lsblk_devdep, ls_parents);
+ if (!dp)
+ return 0;
+ return dp->parent == parent;
+}
+
+int lsblk_device_next_parent(
+ struct lsblk_device *dev,
+ struct lsblk_iter *itr,
+ struct lsblk_device **parent)
{
int rc = 1;
- if (!dev || !itr || !child)
+ if (!dev || !itr || !parent)
return -EINVAL;
- *child = NULL;
+ *parent = NULL;
if (!itr->head)
- LSBLK_ITER_INIT(itr, &dev->deps);
+ LSBLK_ITER_INIT(itr, &dev->parents);
if (itr->p != itr->head) {
struct lsblk_devdep *dp = NULL;
-
- LSBLK_ITER_ITERATE(itr, dp, struct lsblk_devdep, ls_deps);
-
- *child = dp->child;
+ LSBLK_ITER_ITERATE(itr, dp, struct lsblk_devdep, ls_parents);
+ if (dp)
+ *parent = dp->parent;
rc = 0;
}
return 0;
}
+static int device_dedupkey_is_equal(
+ struct lsblk_device *dev,
+ struct lsblk_device *pattern)
+{
+ assert(pattern->dedupkey);
+
+ if (!dev->dedupkey || dev == pattern)
+ return 0;
+ if (strcmp(dev->dedupkey, pattern->dedupkey) == 0) {
+ if (!device_is_partition(dev) ||
+ !dev->wholedisk->dedupkey ||
+ strcmp(dev->dedupkey, dev->wholedisk->dedupkey) != 0) {
+ DBG(DEV, ul_debugobj(dev, "%s: match deduplication pattern", dev->name));
+ return 1;
+ }
+ }
+ return 0;
+}
+
+static void device_dedup_dependencies(
+ struct lsblk_device *dev,
+ struct lsblk_device *pattern)
+{
+ struct lsblk_iter itr;
+ struct lsblk_devdep *dp;
+
+ lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
+
+ while (device_next_child(dev, &itr, &dp) == 0) {
+ struct lsblk_device *child = dp->child;
+
+ if (device_dedupkey_is_equal(child, pattern)) {
+ DBG(DEV, ul_debugobj(dev, "remove duplicate dependence: 0x%p [%s]",
+ dp->child, dp->child->name));
+ remove_dependence(dp);
+ } else
+ device_dedup_dependencies(child, pattern);
+ }
+}
+
+static void devtree_dedup(struct lsblk_devtree *tr, struct lsblk_device *pattern)
+{
+ struct lsblk_iter itr;
+ struct lsblk_device *dev = NULL;
+
+ lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
+
+ DBG(TREE, ul_debugobj(tr, "de-duplicate by key: %s", pattern->dedupkey));
+
+ while (lsblk_devtree_next_root(tr, &itr, &dev) == 0) {
+ if (device_dedupkey_is_equal(dev, pattern)) {
+ DBG(TREE, ul_debugobj(tr, "remove duplicate device: 0x%p [%s]",
+ dev, dev->name));
+ /* Note that root list does not use ref-counting; the
+ * primary reference is ls_devices */
+ list_del_init(&dev->ls_roots);
+ } else
+ device_dedup_dependencies(dev, pattern);
+ }
+}
+
+static int cmp_devices_devno(struct list_head *a, struct list_head *b,
+ __attribute__((__unused__)) void *data)
+{
+ struct lsblk_device *ax = list_entry(a, struct lsblk_device, ls_devices),
+ *bx = list_entry(b, struct lsblk_device, ls_devices);
+
+ return cmp_numbers(makedev(ax->maj, ax->min),
+ makedev(bx->maj, bx->min));
+}
+
+/* Note that dev->dedupkey has to be already set */
+int lsblk_devtree_deduplicate_devices(struct lsblk_devtree *tr)
+{
+ struct lsblk_device *pattern = NULL;
+ struct lsblk_iter itr;
+ char *last = NULL;
+
+ list_sort(&tr->devices, cmp_devices_devno, NULL);
+ lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
+
+ while (lsblk_devtree_next_device(tr, &itr, &pattern) == 0) {
+ if (!pattern->dedupkey)
+ continue;
+ if (device_is_partition(pattern) &&
+ pattern->wholedisk->dedupkey &&
+ strcmp(pattern->dedupkey, pattern->wholedisk->dedupkey) == 0)
+ continue;
+ if (last && strcmp(pattern->dedupkey, last) == 0)
+ continue;
+
+ devtree_dedup(tr, pattern);
+ last = pattern->dedupkey;
+ }
+ return 0;
+}