[lvm2.git] / libdm / libdm-deptree.c

/*
 * Copyright (C) 2005 Red Hat, Inc. All rights reserved.
 *
 * This file is part of the device-mapper userspace tools.
 *
 * This copyrighted material is made available to anyone wishing to use,
 * modify, copy, or redistribute it subject to the terms and conditions
 * of the GNU Lesser General Public License v.2.1.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include "lib.h"
#include "libdm-targets.h"
#include "libdm-common.h"
#include "list.h"
#include "kdev_t.h"
#include "pool.h"
#include "hash.h"

#include <stdarg.h>
#include <sys/param.h>

#include <linux/dm-ioctl.h>

struct deptree_node {
	struct deptree *deptree;

        const char *name;
        const char *uuid;
        struct dm_info info;

        struct list uses;       	/* Nodes this node uses */
        struct list used_by;    	/* Nodes that use this node */
};

struct deptree {
	struct pool *mem;
	struct hash_table *devs;
	struct deptree_node root;
};

struct deptree_link {
	struct list list;
	struct deptree_node *node;
};

struct deptree *dm_deptree_create(void)
{
	struct deptree *deptree;

	if (!(deptree = dbg_malloc(sizeof(*deptree)))) {
		log_error("dm_deptree_create malloc failed");
		return NULL;
	}

	memset(deptree, 0, sizeof(*deptree));
	deptree->root.deptree = deptree;
	list_init(&deptree->root.uses);
	list_init(&deptree->root.used_by);

	if (!(deptree->mem = pool_create("deptree", 1024))) {
		log_error("deptree pool creation failed");
		dbg_free(deptree);
		return NULL;
	}

	if (!(deptree->devs = hash_create(8))) {
		log_error("deptree hash creation failed");
		pool_destroy(deptree->mem);
		dbg_free(deptree);
		return NULL;
	}

	return deptree;
}

void dm_deptree_free(struct deptree *deptree)
{
	if (!deptree)
		return;

	hash_destroy(deptree->devs);
	pool_destroy(deptree->mem);
	dbg_free(deptree);
}

static int _nodes_are_linked(struct deptree_node *parent,
			     struct deptree_node *child)
{
	struct deptree_link *dlink;

	list_iterate_items(dlink, &parent->uses) {
		if (dlink->node == child)
			return 1;
	}

	return 0;
}

static int _link(struct list *list, struct deptree_node *node)
{
	struct deptree_link *dlink;

	if (!(dlink = pool_alloc(node->deptree->mem, sizeof(*dlink)))) {
		log_error("deptree link allocation failed");
		return 0;
	}

	dlink->node = node;
	list_add(list, &dlink->list);

	return 1;
}

static int _link_nodes(struct deptree_node *parent,
		       struct deptree_node *child)
{
	if (_nodes_are_linked(parent, child))
		return 1;

	if (!_link(&parent->uses, child))
		return 0;

	if (!_link(&child->used_by, parent))
		return 0;

	return 1;
}

static void _unlink(struct list *list, struct deptree_node *node)
{
	struct deptree_link *dlink;

	list_iterate_items(dlink, list) {
		if (dlink->node == node) {
			list_del(&dlink->list);
			break;
		}
	}
}

static void _unlink_nodes(struct deptree_node *parent,
			  struct deptree_node *child)
{
	if (!_nodes_are_linked(parent, child))
		return;

	_unlink(&parent->uses, child);
	_unlink(&child->used_by, parent);
}

static void _remove_from_toplevel(struct deptree_node *node)
{
	return _unlink_nodes(&node->deptree->root, node);
}

static int _add_to_bottomlevel(struct deptree_node *node)
{
	return _link_nodes(node, &node->deptree->root);
}

static struct deptree_node *_create_deptree_node(struct deptree *deptree,
						 struct deptree_node *parent,
						 const char *name,
						 const char *uuid,
						 struct dm_info *info)
{
	struct deptree_node *node;
	uint64_t dev;

	if (!(node = pool_zalloc(deptree->mem, sizeof(*node)))) {
		log_error("_create_deptree_node alloc failed");
		return NULL;
	}

	node->deptree = deptree;

	node->name = name;
	node->uuid = uuid;
	node->info = *info;

	list_init(&node->uses);
	list_init(&node->used_by);

	dev = MKDEV(info->major, info->minor);

	if (!hash_insert_binary(deptree->devs, (const char *) &dev,
				sizeof(dev), node)) {
		log_error("deptree node hash insertion failed");
		pool_free(deptree->mem, node);
		return NULL;
	}

	return node;
}

static struct deptree_node *_find_deptree_node(struct deptree *deptree,
					       uint32_t major, uint32_t minor)
{
	uint64_t dev = MKDEV(major, minor);

	return hash_lookup_binary(deptree->devs, (const char *) &dev,
				  sizeof(dev));
}

static int _deps(struct dm_task **dmt, struct pool *mem, uint32_t major, uint32_t minor,
		 const char **name, const char **uuid,
		 struct dm_info *info, struct dm_deps **deps)
{
	memset(info, 0, sizeof(*info));

	if (!dm_is_dm_major(major)) {
		*name = "";
		*uuid = "";
		*deps = NULL;
		info->major = major;
		info->minor = minor;
		info->exists = 0;
		return 1;
	}

	if (!(*dmt = dm_task_create(DM_DEVICE_DEPS))) {
		log_error("deps dm_task creation failed");
		return 0;
	}

	if (!dm_task_set_major(*dmt, major))
		goto failed;

	if (!dm_task_set_minor(*dmt, minor))
		goto failed;

	if (!dm_task_run(*dmt))
		goto failed;

	if (!dm_task_get_info(*dmt, info))
		goto failed;

	if (!info->exists) {
		*name = "";
		*uuid = "";
		*deps = NULL;
	} else {
		if (info->major != major) {
			log_error("Inconsistent deptree major number: %u != %u",
				  major, info->major);
			goto failed;
		}
		if (info->minor != minor) {
			log_error("Inconsistent deptree minor number: %u != %u",
				  minor, info->minor);
			goto failed;
		}
		if (!(*name = pool_strdup(mem, dm_task_get_name(*dmt)))) {
			log_error("name pool_strdup failed");
			goto failed;
		}
		if (!(*uuid = pool_strdup(mem, dm_task_get_uuid(*dmt)))) {
			log_error("uuid pool_strdup failed");
			goto failed;
		}
		*deps = dm_task_get_deps(*dmt);
	}

	return 1;

failed:
	dm_task_destroy(*dmt);
	return 0;
}

static int _add_dev(struct deptree *deptree, struct deptree_node *parent,
		    uint32_t major, uint32_t minor)
{
	struct dm_task *dmt = NULL;
	struct dm_info info;
	struct dm_deps *deps = NULL;
	const char *name = NULL;
	const char *uuid = NULL;
	struct deptree_node *node;
	uint32_t i;
	int r = 0;
	int new = 0;

	/* Already in tree? */
	if (!(node = _find_deptree_node(deptree, major, minor))) {
		if (!_deps(&dmt, deptree->mem, major, minor, &name, &uuid, &info, &deps))
			return 0;

		if (!(node = _create_deptree_node(deptree, node, name, uuid,
						  &info)))
			goto out;
		new = 1;
	}

	/* If new parent not root node, remove any existing root node parent */
	if (parent != &deptree->root)
		_remove_from_toplevel(node);

	/* Create link to parent.  Use root node only if no other parents. */
	if ((parent != &deptree->root) || !dm_deptree_node_num_children(node, 1))
		if (!_link_nodes(parent, node))
			goto out;

	/* If node was already in tree, no need to recurse. */
	if (!new)
		return 1;

	/* Can't recurse if not a mapped device or there are no dependencies */
	if (!node->info.exists || !deps->count) {
		if (!_add_to_bottomlevel(node))
			goto out;
		return 1;
	}

	/* Add dependencies to tree */
	for (i = 0; i < deps->count; i++)
		if (!_add_dev(deptree, node, MAJOR(deps->device[i]),
			      MINOR(deps->device[i])))
			goto out;

	r = 1;
out:
	if (dmt)
		dm_task_destroy(dmt);

	return r;
}

int dm_deptree_add_dev(struct deptree *deptree, uint32_t major, uint32_t minor)
{
	return _add_dev(deptree, &deptree->root, major, minor);
}

const char *dm_deptree_node_get_name(struct deptree_node *node)
{
	return node->info.exists ? node->name : "";
}

const char *dm_deptree_node_get_uuid(struct deptree_node *node)
{
	return node->info.exists ? node->uuid : "";
}

const struct dm_info *dm_deptree_node_get_info(struct deptree_node *node)
{
	return &node->info;
}

int dm_deptree_node_num_children(struct deptree_node *node, uint32_t inverted)
{
	if (inverted) {
		if (_nodes_are_linked(&node->deptree->root, node))
			return 0;
		return list_size(&node->used_by);
	}

	if (_nodes_are_linked(node, &node->deptree->root))
		return 0;

	return list_size(&node->uses);
}

/*
 * Set major and minor to zero for root of tree.
 */
struct deptree_node *dm_deptree_find_node(struct deptree *deptree,
					  uint32_t major,
					  uint32_t minor)
{
	if (!major && !minor)
		return &deptree->root;

	return _find_deptree_node(deptree, major, minor);
}

/*
 * First time set *handle to NULL.
 * Set inverted to invert the tree.
 */
struct deptree_node *dm_deptree_next_child(void **handle,
					   struct deptree_node *parent,
					   uint32_t inverted)
{
	struct list **dlink = (struct list **) handle;
	struct list *use_list;

	if (inverted)
		use_list = &parent->used_by;
	else
		use_list = &parent->uses;

	if (!*dlink)
		*dlink = list_first(use_list);
	else
		*dlink = list_next(use_list, *dlink);

	return (*dlink) ? list_item(*dlink, struct deptree_link)->node : NULL;
}
Commit	Line	Data
3d0480ed AK	1	/*
	2	* Copyright (C) 2005 Red Hat, Inc. All rights reserved.
	3	*
	4	* This file is part of the device-mapper userspace tools.
	5	*
	6	* This copyrighted material is made available to anyone wishing to use,
	7	* modify, copy, or redistribute it subject to the terms and conditions
	8	* of the GNU Lesser General Public License v.2.1.
	9	*
	10	* You should have received a copy of the GNU Lesser General Public License
	11	* along with this program; if not, write to the Free Software Foundation,
	12	* Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	13	*/
	14
	15	#include "lib.h"
	16	#include "libdm-targets.h"
	17	#include "libdm-common.h"
	18	#include "list.h"
	19	#include "kdev_t.h"
	20	#include "pool.h"
	21	#include "hash.h"
	22
	23	#include <stdarg.h>
	24	#include <sys/param.h>
	25
	26	#include <linux/dm-ioctl.h>
	27
	28	struct deptree_node {
	29	struct deptree *deptree;
	30
	31	const char *name;
	32	const char *uuid;
	33	struct dm_info info;
	34
	35	struct list uses; /* Nodes this node uses */
	36	struct list used_by; /* Nodes that use this node */
	37	};
	38
	39	struct deptree {
	40	struct pool *mem;
	41	struct hash_table *devs;
	42	struct deptree_node root;
	43	};
	44
	45	struct deptree_link {
	46	struct list list;
	47	struct deptree_node *node;
	48	};
	49
	50	struct deptree *dm_deptree_create(void)
	51	{
	52	struct deptree *deptree;
	53
	54	if (!(deptree = dbg_malloc(sizeof(*deptree)))) {
	55	log_error("dm_deptree_create malloc failed");
	56	return NULL;
	57	}
	58
	59	memset(deptree, 0, sizeof(*deptree));
	60	deptree->root.deptree = deptree;
	61	list_init(&deptree->root.uses);
	62	list_init(&deptree->root.used_by);
	63
	64	if (!(deptree->mem = pool_create("deptree", 1024))) {
65	log_error("deptree pool creation failed");
66	dbg_free(deptree);
67	return NULL;
68	}
69
70	if (!(deptree->devs = hash_create(8))) {
71	log_error("deptree hash creation failed");
72	pool_destroy(deptree->mem);
73	dbg_free(deptree);
74	return NULL;
75	}
76
77	return deptree;
78	}
79
80	void dm_deptree_free(struct deptree *deptree)
81	{
82	if (!deptree)
83	return;
84
85	hash_destroy(deptree->devs);
86	pool_destroy(deptree->mem);
87	dbg_free(deptree);
88	}
89
90	static int _nodes_are_linked(struct deptree_node *parent,
91	struct deptree_node *child)
92	{
93	struct deptree_link *dlink;
94
95	list_iterate_items(dlink, &parent->uses) {
96	if (dlink->node == child)
97	return 1;
98	}
99
100	return 0;
101	}
102
103	static int _link(struct list list, struct deptree_node node)
104	{
105	struct deptree_link *dlink;
106
107	if (!(dlink = pool_alloc(node->deptree->mem, sizeof(*dlink)))) {
108	log_error("deptree link allocation failed");
109	return 0;
110	}
111
112	dlink->node = node;
113	list_add(list, &dlink->list);
114
115	return 1;
116	}
117
118	static int _link_nodes(struct deptree_node *parent,
119	struct deptree_node *child)
120	{
121	if (_nodes_are_linked(parent, child))
122	return 1;
123
124	if (!_link(&parent->uses, child))
125	return 0;
126
127	if (!_link(&child->used_by, parent))
128	return 0;
129
130	return 1;
131	}
132
133	static void _unlink(struct list list, struct deptree_node node)
134	{
135	struct deptree_link *dlink;
136
137	list_iterate_items(dlink, list) {
138	if (dlink->node == node) {
139	list_del(&dlink->list);
140	break;
141	}
142	}
143	}
144
145	static void _unlink_nodes(struct deptree_node *parent,
146	struct deptree_node *child)
147	{
148	if (!_nodes_are_linked(parent, child))
149	return;
150
151	_unlink(&parent->uses, child);
152	_unlink(&child->used_by, parent);
153	}
154
155	static void _remove_from_toplevel(struct deptree_node *node)
156	{
157	return _unlink_nodes(&node->deptree->root, node);
158	}
159
160	static int _add_to_bottomlevel(struct deptree_node *node)
161	{
162	return _link_nodes(node, &node->deptree->root);
163	}
164
165	static struct deptree_node _create_deptree_node(struct deptree deptree,
166	struct deptree_node *parent,
167	const char *name,
168	const char *uuid,
169	struct dm_info *info)
170	{
171	struct deptree_node *node;
172	uint64_t dev;
173
174	if (!(node = pool_zalloc(deptree->mem, sizeof(*node)))) {
175	log_error("_create_deptree_node alloc failed");
176	return NULL;
177	}
178
179	node->deptree = deptree;
180
181	node->name = name;
182	node->uuid = uuid;
183	node->info = *info;
184
185	list_init(&node->uses);
186	list_init(&node->used_by);
187
188	dev = MKDEV(info->major, info->minor);
189
190	if (!hash_insert_binary(deptree->devs, (const char *) &dev,
191	sizeof(dev), node)) {
192	log_error("deptree node hash insertion failed");
193	pool_free(deptree->mem, node);
194	return NULL;
195	}
196
197	return node;
198	}
199
200	static struct deptree_node _find_deptree_node(struct deptree deptree,
201	uint32_t major, uint32_t minor)
202	{
203	uint64_t dev = MKDEV(major, minor);
204
205	return hash_lookup_binary(deptree->devs, (const char *) &dev,
206	sizeof(dev));
207	}
208
209	static int _deps(struct dm_task *dmt, struct pool mem, uint32_t major, uint32_t minor,
210	const char name, const char uuid,
211	struct dm_info info, struct dm_deps *deps)
212	{
213	memset(info, 0, sizeof(*info));
214
215	if (!dm_is_dm_major(major)) {
216	*name = "";
217	*uuid = "";
218	*deps = NULL;
219	info->major = major;
220	info->minor = minor;
221	info->exists = 0;
222	return 1;
223	}
224
225	if (!(*dmt = dm_task_create(DM_DEVICE_DEPS))) {
226	log_error("deps dm_task creation failed");
227	return 0;
228	}
229
230	if (!dm_task_set_major(*dmt, major))
231	goto failed;
232
233	if (!dm_task_set_minor(*dmt, minor))
234	goto failed;
235
236	if (!dm_task_run(*dmt))
237	goto failed;
238
239	if (!dm_task_get_info(*dmt, info))
240	goto failed;
241
242	if (!info->exists) {
243	*name = "";
244	*uuid = "";
245	*deps = NULL;
246	} else {
247	if (info->major != major) {
248	log_error("Inconsistent deptree major number: %u != %u",
249	major, info->major);
250	goto failed;
251	}
252	if (info->minor != minor) {
253	log_error("Inconsistent deptree minor number: %u != %u",
254	minor, info->minor);
255	goto failed;
256	}
257	if (!(name = pool_strdup(mem, dm_task_get_name(dmt)))) {
258	log_error("name pool_strdup failed");
259	goto failed;
260	}
261	if (!(uuid = pool_strdup(mem, dm_task_get_uuid(dmt)))) {
262	log_error("uuid pool_strdup failed");
263	goto failed;
264	}
265	deps = dm_task_get_deps(dmt);
266	}
267
268	return 1;
269
270	failed:
271	dm_task_destroy(*dmt);
272	return 0;
273	}
274
275	static int _add_dev(struct deptree deptree, struct deptree_node parent,
276	uint32_t major, uint32_t minor)
277	{
278	struct dm_task *dmt = NULL;
279	struct dm_info info;
280	struct dm_deps *deps = NULL;
281	const char *name = NULL;
282	const char *uuid = NULL;
283	struct deptree_node *node;
284	uint32_t i;
285	int r = 0;
286	int new = 0;
287
288	/* Already in tree? */
289	if (!(node = _find_deptree_node(deptree, major, minor))) {
290	if (!_deps(&dmt, deptree->mem, major, minor, &name, &uuid, &info, &deps))
291	return 0;
292
293	if (!(node = _create_deptree_node(deptree, node, name, uuid,
294	&info)))
295	goto out;
296	new = 1;
297	}
298
299	/* If new parent not root node, remove any existing root node parent */
300	if (parent != &deptree->root)
301	_remove_from_toplevel(node);
302
303	/* Create link to parent. Use root node only if no other parents. */
304	if ((parent != &deptree->root) \|\| !dm_deptree_node_num_children(node, 1))
305	if (!_link_nodes(parent, node))
306	goto out;
307
308	/* If node was already in tree, no need to recurse. */
309	if (!new)
310	return 1;
311
312	/* Can't recurse if not a mapped device or there are no dependencies */
313	if (!node->info.exists \|\| !deps->count) {
314	if (!_add_to_bottomlevel(node))
315	goto out;
316	return 1;
317	}
318
319	/* Add dependencies to tree */
320	for (i = 0; i < deps->count; i++)
321	if (!_add_dev(deptree, node, MAJOR(deps->device[i]),
322	MINOR(deps->device[i])))
323	goto out;
324
325	r = 1;
326	out:
327	if (dmt)
328	dm_task_destroy(dmt);
329
330	return r;
331	}
332
333	int dm_deptree_add_dev(struct deptree *deptree, uint32_t major, uint32_t minor)
334	{
335	return _add_dev(deptree, &deptree->root, major, minor);
336	}
337
338	const char dm_deptree_node_get_name(struct deptree_node node)
339	{
340	return node->info.exists ? node->name : "";
341	}
342
343	const char dm_deptree_node_get_uuid(struct deptree_node node)
344	{
345	return node->info.exists ? node->uuid : "";
346	}
347
348	const struct dm_info dm_deptree_node_get_info(struct deptree_node node)
349	{
350	return &node->info;
351	}
352
353	int dm_deptree_node_num_children(struct deptree_node *node, uint32_t inverted)
354	{
355	if (inverted) {
356	if (_nodes_are_linked(&node->deptree->root, node))
357	return 0;
358	return list_size(&node->used_by);
359	}
360
361	if (_nodes_are_linked(node, &node->deptree->root))
362	return 0;
363
364	return list_size(&node->uses);
365	}
366
367	/*
368	* Set major and minor to zero for root of tree.
369	*/
370	struct deptree_node dm_deptree_find_node(struct deptree deptree,
371	uint32_t major,
372	uint32_t minor)
373	{
374	if (!major && !minor)
375	return &deptree->root;
376
377	return _find_deptree_node(deptree, major, minor);
378	}
379
380	/*
381	* First time set *handle to NULL.
382	* Set inverted to invert the tree.
383	*/
384	struct deptree_node dm_deptree_next_child(void *handle,
385	struct deptree_node *parent,
386	uint32_t inverted)
387	{
388	struct list dlink = (struct list ) handle;
389	struct list *use_list;
390
391	if (inverted)
392	use_list = &parent->used_by;
393	else
394	use_list = &parent->uses;
395
396	if (!*dlink)
397	*dlink = list_first(use_list);
398	else
399	dlink = list_next(use_list, dlink);
400
401	return (dlink) ? list_item(dlink, struct deptree_link)->node : NULL;
402	}
403