1 files changed, 472 insertions, 0 deletions

diff --git a/misc-utils/lsblk-devtree.c b/misc-utils/lsblk-devtree.c
new file mode 100644
index 0000000..4d15f70
--- /dev/null
+++ b/misc-utils/lsblk-devtree.c
@@ -0,0 +1,472 @@
+/*
+ * 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"
+
+
+void lsblk_reset_iter(struct lsblk_iter *itr, int direction)
+{
+	if (direction == -1)
+		direction = itr->direction;
+
+	memset(itr, 0, sizeof(*itr));
+	itr->direction = direction;
+}
+
+struct lsblk_device *lsblk_new_device()
+{
+	struct lsblk_device *dev;
+
+	dev = calloc(1, sizeof(*dev));
+	if (!dev)
+		return NULL;
+
+	dev->refcount = 1;
+	dev->removable = -1;
+	dev->discard_granularity = (uint64_t) -1;
+
+	INIT_LIST_HEAD(&dev->childs);
+	INIT_LIST_HEAD(&dev->parents);
+	INIT_LIST_HEAD(&dev->ls_roots);
+	INIT_LIST_HEAD(&dev->ls_devices);
+
+	DBG(DEV, ul_debugobj(dev, "alloc"));
+	return dev;
+}
+
+void lsblk_ref_device(struct lsblk_device *dev)
+{
+	if (dev)
+		dev->refcount++;
+}
+
+/* removes dependence from child as well as from parent */
+static int remove_dependence(struct lsblk_devdep *dep)
+{
+	if (!dep)
+		return -EINVAL;
+
+	DBG(DEP, ul_debugobj(dep, "   dealloc"));
+
+	list_del_init(&dep->ls_childs);
+	list_del_init(&dep->ls_parents);
+
+	free(dep);
+	return 0;
+}
+
+static int device_remove_dependences(struct lsblk_device *dev)
+{
+	if (!dev)
+		return -EINVAL;
+
+	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;
+}
+
+void lsblk_unref_device(struct lsblk_device *dev)
+{
+	if (!dev)
+		return;
+
+	if (--dev->refcount <= 0) {
+		DBG(DEV, ul_debugobj(dev, " freeing [%s] <<", dev->name));
+
+		device_remove_dependences(dev);
+		lsblk_device_free_properties(dev->properties);
+
+		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);
+	}
+}
+
+int lsblk_device_has_child(struct lsblk_device *dev, struct lsblk_device *child)
+{
+	struct lsblk_device *x = NULL;
+	struct lsblk_iter itr;
+
+	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 -ENOMEM;
+
+	INIT_LIST_HEAD(&dp->ls_childs);
+	INIT_LIST_HEAD(&dp->ls_parents);
+
+	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));
+
+	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 || !parent)
+		return -EINVAL;
+	*parent = NULL;
+
+	if (!itr->head)
+		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_parents);
+		if (dp)
+			*parent = dp->parent;
+		rc = 0;
+	}
+
+	return rc;
+}
+
+struct lsblk_devtree *lsblk_new_devtree()
+{
+	struct lsblk_devtree *tr;
+
+	tr = calloc(1, sizeof(*tr));
+	if (!tr)
+		return NULL;
+
+	tr->refcount = 1;
+
+	INIT_LIST_HEAD(&tr->roots);
+	INIT_LIST_HEAD(&tr->devices);
+
+	DBG(TREE, ul_debugobj(tr, "alloc"));
+	return tr;
+}
+
+void lsblk_ref_devtree(struct lsblk_devtree *tr)
+{
+	if (tr)
+		tr->refcount++;
+}
+
+void lsblk_unref_devtree(struct lsblk_devtree *tr)
+{
+	if (!tr)
+		return;
+
+	if (--tr->refcount <= 0) {
+		DBG(TREE, ul_debugobj(tr, "dealloc"));
+
+		while (!list_empty(&tr->devices)) {
+			struct lsblk_device *dev = list_entry(tr->devices.next,
+						struct lsblk_device, ls_devices);
+			lsblk_devtree_remove_device(tr, dev);
+		}
+		free(tr);
+	}
+}
+
+int lsblk_devtree_add_root(struct lsblk_devtree *tr, struct lsblk_device *dev)
+{
+	if (!lsblk_devtree_has_device(tr, dev))
+		lsblk_devtree_add_device(tr, dev);
+
+	/* We don't increment reference counter for tr->roots list. The primary
+	 * reference is tr->devices */
+
+        DBG(TREE, ul_debugobj(tr, "add root device 0x%p [%s]", dev, dev->name));
+        list_add_tail(&dev->ls_roots, &tr->roots);
+	return 0;
+}
+
+int lsblk_devtree_next_root(struct lsblk_devtree *tr,
+			    struct lsblk_iter *itr,
+			    struct lsblk_device **dev)
+{
+	int rc = 1;
+
+	if (!tr || !itr || !dev)
+		return -EINVAL;
+	*dev = NULL;
+	if (!itr->head)
+		LSBLK_ITER_INIT(itr, &tr->roots);
+	if (itr->p != itr->head) {
+		LSBLK_ITER_ITERATE(itr, *dev, struct lsblk_device, ls_roots);
+		rc = 0;
+	}
+	return rc;
+}
+
+int lsblk_devtree_add_device(struct lsblk_devtree *tr, struct lsblk_device *dev)
+{
+	lsblk_ref_device(dev);
+
+        DBG(TREE, ul_debugobj(tr, "add device 0x%p [%s]", dev, dev->name));
+        list_add_tail(&dev->ls_devices, &tr->devices);
+	return 0;
+}
+
+int lsblk_devtree_next_device(struct lsblk_devtree *tr,
+			    struct lsblk_iter *itr,
+			    struct lsblk_device **dev)
+{
+	int rc = 1;
+
+	if (!tr || !itr || !dev)
+		return -EINVAL;
+	*dev = NULL;
+	if (!itr->head)
+		LSBLK_ITER_INIT(itr, &tr->devices);
+	if (itr->p != itr->head) {
+		LSBLK_ITER_ITERATE(itr, *dev, struct lsblk_device, ls_devices);
+		rc = 0;
+	}
+	return rc;
+}
+
+int lsblk_devtree_has_device(struct lsblk_devtree *tr, struct lsblk_device *dev)
+{
+	struct lsblk_device *x = NULL;
+	struct lsblk_iter itr;
+
+	lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
+
+	while (lsblk_devtree_next_device(tr, &itr, &x) == 0) {
+		if (x == dev)
+			return 1;
+	}
+
+	return 0;
+}
+
+struct lsblk_device *lsblk_devtree_get_device(struct lsblk_devtree *tr, const char *name)
+{
+	struct lsblk_device *dev = NULL;
+	struct lsblk_iter itr;
+
+	lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
+
+	while (lsblk_devtree_next_device(tr, &itr, &dev) == 0) {
+		if (strcmp(name, dev->name) == 0)
+			return dev;
+	}
+
+	return NULL;
+}
+
+int lsblk_devtree_remove_device(struct lsblk_devtree *tr, struct lsblk_device *dev)
+{
+        DBG(TREE, ul_debugobj(tr, "remove device 0x%p [%s]", dev, dev->name));
+
+	if (!lsblk_devtree_has_device(tr, dev))
+		return 1;
+
+	list_del_init(&dev->ls_roots);
+	list_del_init(&dev->ls_devices);
+	lsblk_unref_device(dev);
+
+	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;
+}