]>
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 |