[thirdparty/util-linux.git] / misc-utils / lsblk-devtree.c

/*
 * 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;
}
Commit	Line	Data
0986f29a KZ	1	/*
	2	* These functions implement tree of block devices. The devtree struct contains
	3	* two basic lists:
	4	*
	5	* 1) devtree->devices -- This is simple list without any hierarchy. We use
	6	* reference counting here.
	7	*
	8	* 2) devtree->roots -- The root nodes of the trees. The code does not use
	9	* reference counting here due to complexity and it's unnecessary.
	10	*
	11	* Note that the same device maybe have more parents and more children. The
	12	* device is allocated only once and shared within the tree. The dependence
	13	* (devdep struct) contains reference to child as well as to parent and the
	14	* dependence is reference by ls_childs from parent device and by ls_parents
	15	* from child. (Yes, "childs" is used for children ;-)
	16	*
	17	* Copyright (C) 2018 Karel Zak <kzak@redhat.com>
	18	*/
5bb395f4 KZ	19	#include "lsblk.h"
	20	#include "sysfs.h"
	21
	22
	23	void lsblk_reset_iter(struct lsblk_iter *itr, int direction)
	24	{
	25	if (direction == -1)
	26	direction = itr->direction;
	27
	28	memset(itr, 0, sizeof(*itr));
	29	itr->direction = direction;
	30	}
	31
10501add	32	struct lsblk_device *lsblk_new_device()
5bb395f4 KZ	33	{
	34	struct lsblk_device *dev;
	35
	36	dev = calloc(1, sizeof(*dev));
	37	if (!dev)
	38	return NULL;
	39
	40	dev->refcount = 1;
81a8936c	41	dev->removable = -1;
8a2f175c	42	dev->discard_granularity = (uint64_t) -1;
5bb395f4	43
0986f29a KZ	44	INIT_LIST_HEAD(&dev->childs);
0986f29a KZ	45	INIT_LIST_HEAD(&dev->parents);
5bb395f4 KZ	46	INIT_LIST_HEAD(&dev->ls_roots);
	47	INIT_LIST_HEAD(&dev->ls_devices);
	48
	49	DBG(DEV, ul_debugobj(dev, "alloc"));
	50	return dev;
	51	}
	52
	53	void lsblk_ref_device(struct lsblk_device *dev)
	54	{
	55	if (dev)
	56	dev->refcount++;
	57	}
	58
0986f29a KZ	59	/* removes dependence from child as well as from parent */
0986f29a KZ	60	static int remove_dependence(struct lsblk_devdep *dep)
5bb395f4	61	{
0986f29a	62	if (!dep)
5bb395f4 KZ	63	return -EINVAL;
5bb395f4 KZ	64
0986f29a KZ	65	DBG(DEP, ul_debugobj(dep, " dealloc"));
	66
	67	list_del_init(&dep->ls_childs);
	68	list_del_init(&dep->ls_parents);
	69
5bb395f4 KZ	70	free(dep);
	71	return 0;
	72	}
	73
	74	static int device_remove_dependences(struct lsblk_device *dev)
	75	{
	76	if (!dev)
	77	return -EINVAL;
	78
0986f29a KZ	79	if (!list_empty(&dev->childs))
	80	DBG(DEV, ul_debugobj(dev, " %s: remove all children deps", dev->name));
	81	while (!list_empty(&dev->childs)) {
	82	struct lsblk_devdep *dp = list_entry(dev->childs.next,
	83	struct lsblk_devdep, ls_childs);
	84	remove_dependence(dp);
	85	}
	86
	87	if (!list_empty(&dev->parents))
	88	DBG(DEV, ul_debugobj(dev, " %s: remove all parents deps", dev->name));
	89	while (!list_empty(&dev->parents)) {
	90	struct lsblk_devdep *dp = list_entry(dev->parents.next,
	91	struct lsblk_devdep, ls_parents);
	92	remove_dependence(dp);
5bb395f4	93	}
0986f29a	94
5bb395f4 KZ	95	return 0;
	96	}
	97
	98	void lsblk_unref_device(struct lsblk_device *dev)
	99	{
57502dd3	100	if (!dev)
5bb395f4 KZ	101	return;
	102
	103	if (--dev->refcount <= 0) {
0986f29a	104	DBG(DEV, ul_debugobj(dev, " freeing [%s] <<", dev->name));
5bb395f4 KZ	105
	106	device_remove_dependences(dev);
	107	lsblk_device_free_properties(dev->properties);
	108
10501add KZ	109	lsblk_unref_device(dev->wholedisk);
10501add KZ	110
5bb395f4 KZ	111	free(dev->dm_name);
	112	free(dev->filename);
	113	free(dev->mountpoint);
dc4662f0	114	free(dev->dedupkey);
5bb395f4 KZ	115
5bb395f4 KZ	116	ul_unref_path(dev->sysfs);
5bb395f4	117
0986f29a KZ	118	DBG(DEV, ul_debugobj(dev, " >> dealloc [%s]", dev->name));
0986f29a KZ	119	free(dev->name);
5bb395f4 KZ	120	free(dev);
	121	}
	122	}
	123
0986f29a	124	int lsblk_device_has_child(struct lsblk_device dev, struct lsblk_device child)
5bb395f4	125	{
e2d7870b KZ	126	struct lsblk_device *x = NULL;
e2d7870b KZ	127	struct lsblk_iter itr;
5bb395f4	128
e2d7870b KZ	129	lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
	130
	131	while (lsblk_device_next_child(dev, &itr, &x) == 0) {
	132	if (x == child)
	133	return 1;
5bb395f4 KZ	134	}
5bb395f4 KZ	135
e2d7870b KZ	136	return 0;
	137	}
	138
	139	int lsblk_device_new_dependence(struct lsblk_device parent, struct lsblk_device child)
	140	{
	141	struct lsblk_devdep *dp;
	142
	143	if (!parent \|\| !child)
	144	return -EINVAL;
	145
0986f29a	146	if (lsblk_device_has_child(parent, child))
e2d7870b KZ	147	return 1;
e2d7870b KZ	148
5bb395f4 KZ	149	dp = calloc(1, sizeof(*dp));
5bb395f4 KZ	150	if (!dp)
e2d7870b	151	return -ENOMEM;
5bb395f4	152
0986f29a KZ	153	INIT_LIST_HEAD(&dp->ls_childs);
0986f29a KZ	154	INIT_LIST_HEAD(&dp->ls_parents);
5bb395f4	155
5bb395f4	156	dp->child = child;
0986f29a KZ	157	list_add_tail(&dp->ls_childs, &parent->childs);
	158
	159	dp->parent = parent;
0bd05f5e	160	list_add_tail(&dp->ls_parents, &child->parents);
5bb395f4 KZ	161
5bb395f4 KZ	162	DBG(DEV, ul_debugobj(parent, "add dependence 0x%p [%s->%s]", dp, parent->name, child->name));
5bb395f4	163
e2d7870b	164	return 0;
5bb395f4 KZ	165	}
5bb395f4 KZ	166
0986f29a	167	static int device_next_child(struct lsblk_device *dev,
5bb395f4	168	struct lsblk_iter *itr,
dc4662f0	169	struct lsblk_devdep **dp)
5bb395f4 KZ	170	{
	171	int rc = 1;
	172
dc4662f0	173	if (!dev \|\| !itr \|\| !dp)
5bb395f4	174	return -EINVAL;
dc4662f0	175	*dp = NULL;
5bb395f4 KZ	176
5bb395f4 KZ	177	if (!itr->head)
0986f29a	178	LSBLK_ITER_INIT(itr, &dev->childs);
5bb395f4	179	if (itr->p != itr->head) {
0986f29a	180	LSBLK_ITER_ITERATE(itr, *dp, struct lsblk_devdep, ls_childs);
5bb395f4 KZ	181	rc = 0;
	182	}
	183
	184	return rc;
	185	}
	186
dc4662f0 KZ	187	int lsblk_device_next_child(struct lsblk_device *dev,
	188	struct lsblk_iter *itr,
	189	struct lsblk_device **child)
	190	{
	191	struct lsblk_devdep *dp = NULL;
0986f29a	192	int rc = device_next_child(dev, itr, &dp);
dc4662f0 KZ	193
	194	if (!child)
	195	return -EINVAL;
	196
	197	*child = rc == 0 ? dp->child : NULL;
	198	return rc;
	199	}
	200
0bd05f5e KZ	201	int lsblk_device_is_last_parent(struct lsblk_device dev, struct lsblk_device parent)
	202	{
	203	struct lsblk_devdep *dp = list_last_entry(
	204	&dev->parents,
	205	struct lsblk_devdep, ls_parents);
e361253e SK	206	if (!dp)
e361253e SK	207	return 0;
0bd05f5e KZ	208	return dp->parent == parent;
	209	}
	210
	211	int lsblk_device_next_parent(
	212	struct lsblk_device *dev,
	213	struct lsblk_iter *itr,
	214	struct lsblk_device **parent)
	215	{
	216	int rc = 1;
	217
	218	if (!dev \|\| !itr \|\| !parent)
	219	return -EINVAL;
	220	*parent = NULL;
	221
	222	if (!itr->head)
	223	LSBLK_ITER_INIT(itr, &dev->parents);
	224	if (itr->p != itr->head) {
	225	struct lsblk_devdep *dp = NULL;
	226	LSBLK_ITER_ITERATE(itr, dp, struct lsblk_devdep, ls_parents);
	227	if (dp)
	228	*parent = dp->parent;
	229	rc = 0;
	230	}
	231
	232	return rc;
	233	}
e2d7870b	234
5bb395f4 KZ	235	struct lsblk_devtree *lsblk_new_devtree()
	236	{
	237	struct lsblk_devtree *tr;
	238
	239	tr = calloc(1, sizeof(*tr));
	240	if (!tr)
	241	return NULL;
	242
	243	tr->refcount = 1;
	244
	245	INIT_LIST_HEAD(&tr->roots);
	246	INIT_LIST_HEAD(&tr->devices);
	247
	248	DBG(TREE, ul_debugobj(tr, "alloc"));
	249	return tr;
	250	}
	251
	252	void lsblk_ref_devtree(struct lsblk_devtree *tr)
	253	{
	254	if (tr)
	255	tr->refcount++;
	256	}
	257
	258	void lsblk_unref_devtree(struct lsblk_devtree *tr)
	259	{
57502dd3	260	if (!tr)
5bb395f4 KZ	261	return;
	262
	263	if (--tr->refcount <= 0) {
	264	DBG(TREE, ul_debugobj(tr, "dealloc"));
	265
5bb395f4 KZ	266	while (!list_empty(&tr->devices)) {
	267	struct lsblk_device *dev = list_entry(tr->devices.next,
	268	struct lsblk_device, ls_devices);
57502dd3	269	lsblk_devtree_remove_device(tr, dev);
5bb395f4 KZ	270	}
	271	free(tr);
	272	}
	273	}
	274
	275	int lsblk_devtree_add_root(struct lsblk_devtree tr, struct lsblk_device dev)
	276	{
21d4a48c KZ	277	if (!lsblk_devtree_has_device(tr, dev))
	278	lsblk_devtree_add_device(tr, dev);
	279
	280	/* We don't increment reference counter for tr->roots list. The primary
	281	* reference is tr->devices */
5bb395f4 KZ	282
	283	DBG(TREE, ul_debugobj(tr, "add root device 0x%p [%s]", dev, dev->name));
	284	list_add_tail(&dev->ls_roots, &tr->roots);
	285	return 0;
	286	}
	287
	288	int lsblk_devtree_next_root(struct lsblk_devtree *tr,
	289	struct lsblk_iter *itr,
	290	struct lsblk_device **dev)
	291	{
	292	int rc = 1;
	293
	294	if (!tr \|\| !itr \|\| !dev)
	295	return -EINVAL;
	296	*dev = NULL;
	297	if (!itr->head)
	298	LSBLK_ITER_INIT(itr, &tr->roots);
	299	if (itr->p != itr->head) {
	300	LSBLK_ITER_ITERATE(itr, *dev, struct lsblk_device, ls_roots);
	301	rc = 0;
	302	}
	303	return rc;
	304	}
	305
	306	int lsblk_devtree_add_device(struct lsblk_devtree tr, struct lsblk_device dev)
	307	{
	308	lsblk_ref_device(dev);
	309
	310	DBG(TREE, ul_debugobj(tr, "add device 0x%p [%s]", dev, dev->name));
	311	list_add_tail(&dev->ls_devices, &tr->devices);
	312	return 0;
	313	}
	314
	315	int lsblk_devtree_next_device(struct lsblk_devtree *tr,
	316	struct lsblk_iter *itr,
	317	struct lsblk_device **dev)
	318	{
	319	int rc = 1;
	320
	321	if (!tr \|\| !itr \|\| !dev)
	322	return -EINVAL;
	323	*dev = NULL;
	324	if (!itr->head)
	325	LSBLK_ITER_INIT(itr, &tr->devices);
	326	if (itr->p != itr->head) {
	327	LSBLK_ITER_ITERATE(itr, *dev, struct lsblk_device, ls_devices);
	328	rc = 0;
	329	}
	330	return rc;
	331	}
	332
21d4a48c KZ	333	int lsblk_devtree_has_device(struct lsblk_devtree tr, struct lsblk_device dev)
	334	{
	335	struct lsblk_device *x = NULL;
	336	struct lsblk_iter itr;
	337
	338	lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
	339
	340	while (lsblk_devtree_next_device(tr, &itr, &x) == 0) {
	341	if (x == dev)
	342	return 1;
	343	}
	344
	345	return 0;
	346	}
	347
5bb395f4 KZ	348	struct lsblk_device lsblk_devtree_get_device(struct lsblk_devtree tr, const char *name)
	349	{
	350	struct lsblk_device *dev = NULL;
	351	struct lsblk_iter itr;
	352
	353	lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
	354
	355	while (lsblk_devtree_next_device(tr, &itr, &dev) == 0) {
	356	if (strcmp(name, dev->name) == 0)
	357	return dev;
	358	}
	359
	360	return NULL;
	361	}
	362
21d4a48c KZ	363	int lsblk_devtree_remove_device(struct lsblk_devtree tr, struct lsblk_device dev)
	364	{
	365	DBG(TREE, ul_debugobj(tr, "remove device 0x%p [%s]", dev, dev->name));
	366
	367	if (!lsblk_devtree_has_device(tr, dev))
	368	return 1;
	369
	370	list_del_init(&dev->ls_roots);
	371	list_del_init(&dev->ls_devices);
	372	lsblk_unref_device(dev);
	373
	374	return 0;
	375	}
5bb395f4	376
dc4662f0 KZ	377	static int device_dedupkey_is_equal(
	378	struct lsblk_device *dev,
	379	struct lsblk_device *pattern)
	380	{
	381	assert(pattern->dedupkey);
	382
	383	if (!dev->dedupkey \|\| dev == pattern)
	384	return 0;
	385	if (strcmp(dev->dedupkey, pattern->dedupkey) == 0) {
	386	if (!device_is_partition(dev) \|\|
9e677de1	387	!dev->wholedisk->dedupkey \|\|
dc4662f0 KZ	388	strcmp(dev->dedupkey, dev->wholedisk->dedupkey) != 0) {
	389	DBG(DEV, ul_debugobj(dev, "%s: match deduplication pattern", dev->name));
	390	return 1;
	391	}
	392	}
	393	return 0;
	394	}
	395
	396	static void device_dedup_dependencies(
	397	struct lsblk_device *dev,
	398	struct lsblk_device *pattern)
	399	{
	400	struct lsblk_iter itr;
	401	struct lsblk_devdep *dp;
	402
	403	lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
	404
0986f29a	405	while (device_next_child(dev, &itr, &dp) == 0) {
dc4662f0 KZ	406	struct lsblk_device *child = dp->child;
	407
	408	if (device_dedupkey_is_equal(child, pattern)) {
	409	DBG(DEV, ul_debugobj(dev, "remove duplicate dependence: 0x%p [%s]",
	410	dp->child, dp->child->name));
0986f29a	411	remove_dependence(dp);
dc4662f0 KZ	412	} else
	413	device_dedup_dependencies(child, pattern);
	414	}
	415	}
	416
	417	static void devtree_dedup(struct lsblk_devtree tr, struct lsblk_device pattern)
	418	{
	419	struct lsblk_iter itr;
	420	struct lsblk_device *dev = NULL;
	421
	422	lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
	423
	424	DBG(TREE, ul_debugobj(tr, "de-duplicate by key: %s", pattern->dedupkey));
	425
	426	while (lsblk_devtree_next_root(tr, &itr, &dev) == 0) {
	427	if (device_dedupkey_is_equal(dev, pattern)) {
	428	DBG(TREE, ul_debugobj(tr, "remove duplicate device: 0x%p [%s]",
	429	dev, dev->name));
	430	/* Note that root list does not use ref-counting; the
	431	* primary reference is ls_devices */
	432	list_del_init(&dev->ls_roots);
	433	} else
	434	device_dedup_dependencies(dev, pattern);
	435	}
	436	}
	437
	438	static int cmp_devices_devno(struct list_head a, struct list_head b,
	439	__attribute__((__unused__)) void *data)
	440	{
	441	struct lsblk_device *ax = list_entry(a, struct lsblk_device, ls_devices),
	442	*bx = list_entry(b, struct lsblk_device, ls_devices);
	443
	444	return cmp_numbers(makedev(ax->maj, ax->min),
	445	makedev(bx->maj, bx->min));
	446	}
	447
	448	/* Note that dev->dedupkey has to be already set */
	449	int lsblk_devtree_deduplicate_devices(struct lsblk_devtree *tr)
	450	{
	451	struct lsblk_device *pattern = NULL;
	452	struct lsblk_iter itr;
	453	char *last = NULL;
	454
	455	list_sort(&tr->devices, cmp_devices_devno, NULL);
	456	lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
	457
	458	while (lsblk_devtree_next_device(tr, &itr, &pattern) == 0) {
	459	if (!pattern->dedupkey)
	460	continue;
	461	if (device_is_partition(pattern) &&
9e677de1	462	pattern->wholedisk->dedupkey &&
dc4662f0 KZ	463	strcmp(pattern->dedupkey, pattern->wholedisk->dedupkey) == 0)
	464	continue;
	465	if (last && strcmp(pattern->dedupkey, last) == 0)
	466	continue;
	467
	468	devtree_dedup(tr, pattern);
	469	last = pattern->dedupkey;
	470	}
	471	return 0;
	472	}