]>
git.ipfire.org Git - thirdparty/util-linux.git/blob - misc-utils/lsblk-devtree.c
2 * These functions implement tree of block devices. The devtree struct contains
5 * 1) devtree->devices -- This is simple list without any hierarchy. We use
6 * reference counting here.
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.
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 ;-)
17 * Copyright (C) 2018 Karel Zak <kzak@redhat.com>
23 void lsblk_reset_iter(struct lsblk_iter
*itr
, int direction
)
26 direction
= itr
->direction
;
28 memset(itr
, 0, sizeof(*itr
));
29 itr
->direction
= direction
;
32 struct lsblk_device
*lsblk_new_device()
34 struct lsblk_device
*dev
;
36 dev
= calloc(1, sizeof(*dev
));
42 dev
->discard_granularity
= (uint64_t) -1;
44 INIT_LIST_HEAD(&dev
->childs
);
45 INIT_LIST_HEAD(&dev
->parents
);
46 INIT_LIST_HEAD(&dev
->ls_roots
);
47 INIT_LIST_HEAD(&dev
->ls_devices
);
49 DBG(DEV
, ul_debugobj(dev
, "alloc"));
53 void lsblk_ref_device(struct lsblk_device
*dev
)
59 /* removes dependence from child as well as from parent */
60 static int remove_dependence(struct lsblk_devdep
*dep
)
65 DBG(DEP
, ul_debugobj(dep
, " dealloc"));
67 list_del_init(&dep
->ls_childs
);
68 list_del_init(&dep
->ls_parents
);
74 static int device_remove_dependences(struct lsblk_device
*dev
)
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
);
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
);
98 void lsblk_unref_device(struct lsblk_device
*dev
)
103 if (--dev
->refcount
<= 0) {
104 DBG(DEV
, ul_debugobj(dev
, " freeing [%s] <<", dev
->name
));
106 device_remove_dependences(dev
);
107 lsblk_device_free_properties(dev
->properties
);
109 lsblk_unref_device(dev
->wholedisk
);
113 free(dev
->mountpoint
);
116 ul_unref_path(dev
->sysfs
);
118 DBG(DEV
, ul_debugobj(dev
, " >> dealloc [%s]", dev
->name
));
124 int lsblk_device_has_child(struct lsblk_device
*dev
, struct lsblk_device
*child
)
126 struct lsblk_device
*x
= NULL
;
127 struct lsblk_iter itr
;
129 lsblk_reset_iter(&itr
, LSBLK_ITER_FORWARD
);
131 while (lsblk_device_next_child(dev
, &itr
, &x
) == 0) {
139 int lsblk_device_new_dependence(struct lsblk_device
*parent
, struct lsblk_device
*child
)
141 struct lsblk_devdep
*dp
;
143 if (!parent
|| !child
)
146 if (lsblk_device_has_child(parent
, child
))
149 dp
= calloc(1, sizeof(*dp
));
153 INIT_LIST_HEAD(&dp
->ls_childs
);
154 INIT_LIST_HEAD(&dp
->ls_parents
);
157 list_add_tail(&dp
->ls_childs
, &parent
->childs
);
160 list_add_tail(&dp
->ls_parents
, &child
->parents
);
162 DBG(DEV
, ul_debugobj(parent
, "add dependence 0x%p [%s->%s]", dp
, parent
->name
, child
->name
));
167 static int device_next_child(struct lsblk_device
*dev
,
168 struct lsblk_iter
*itr
,
169 struct lsblk_devdep
**dp
)
173 if (!dev
|| !itr
|| !dp
)
178 LSBLK_ITER_INIT(itr
, &dev
->childs
);
179 if (itr
->p
!= itr
->head
) {
180 LSBLK_ITER_ITERATE(itr
, *dp
, struct lsblk_devdep
, ls_childs
);
187 int lsblk_device_next_child(struct lsblk_device
*dev
,
188 struct lsblk_iter
*itr
,
189 struct lsblk_device
**child
)
191 struct lsblk_devdep
*dp
= NULL
;
192 int rc
= device_next_child(dev
, itr
, &dp
);
197 *child
= rc
== 0 ? dp
->child
: NULL
;
201 int lsblk_device_is_last_parent(struct lsblk_device
*dev
, struct lsblk_device
*parent
)
203 struct lsblk_devdep
*dp
= list_last_entry(
205 struct lsblk_devdep
, ls_parents
);
208 return dp
->parent
== parent
;
211 int lsblk_device_next_parent(
212 struct lsblk_device
*dev
,
213 struct lsblk_iter
*itr
,
214 struct lsblk_device
**parent
)
218 if (!dev
|| !itr
|| !parent
)
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
);
228 *parent
= dp
->parent
;
235 struct lsblk_devtree
*lsblk_new_devtree()
237 struct lsblk_devtree
*tr
;
239 tr
= calloc(1, sizeof(*tr
));
245 INIT_LIST_HEAD(&tr
->roots
);
246 INIT_LIST_HEAD(&tr
->devices
);
248 DBG(TREE
, ul_debugobj(tr
, "alloc"));
252 void lsblk_ref_devtree(struct lsblk_devtree
*tr
)
258 void lsblk_unref_devtree(struct lsblk_devtree
*tr
)
263 if (--tr
->refcount
<= 0) {
264 DBG(TREE
, ul_debugobj(tr
, "dealloc"));
266 while (!list_empty(&tr
->devices
)) {
267 struct lsblk_device
*dev
= list_entry(tr
->devices
.next
,
268 struct lsblk_device
, ls_devices
);
269 lsblk_devtree_remove_device(tr
, dev
);
275 int lsblk_devtree_add_root(struct lsblk_devtree
*tr
, struct lsblk_device
*dev
)
277 if (!lsblk_devtree_has_device(tr
, dev
))
278 lsblk_devtree_add_device(tr
, dev
);
280 /* We don't increment reference counter for tr->roots list. The primary
281 * reference is tr->devices */
283 DBG(TREE
, ul_debugobj(tr
, "add root device 0x%p [%s]", dev
, dev
->name
));
284 list_add_tail(&dev
->ls_roots
, &tr
->roots
);
288 int lsblk_devtree_next_root(struct lsblk_devtree
*tr
,
289 struct lsblk_iter
*itr
,
290 struct lsblk_device
**dev
)
294 if (!tr
|| !itr
|| !dev
)
298 LSBLK_ITER_INIT(itr
, &tr
->roots
);
299 if (itr
->p
!= itr
->head
) {
300 LSBLK_ITER_ITERATE(itr
, *dev
, struct lsblk_device
, ls_roots
);
306 int lsblk_devtree_add_device(struct lsblk_devtree
*tr
, struct lsblk_device
*dev
)
308 lsblk_ref_device(dev
);
310 DBG(TREE
, ul_debugobj(tr
, "add device 0x%p [%s]", dev
, dev
->name
));
311 list_add_tail(&dev
->ls_devices
, &tr
->devices
);
315 int lsblk_devtree_next_device(struct lsblk_devtree
*tr
,
316 struct lsblk_iter
*itr
,
317 struct lsblk_device
**dev
)
321 if (!tr
|| !itr
|| !dev
)
325 LSBLK_ITER_INIT(itr
, &tr
->devices
);
326 if (itr
->p
!= itr
->head
) {
327 LSBLK_ITER_ITERATE(itr
, *dev
, struct lsblk_device
, ls_devices
);
333 int lsblk_devtree_has_device(struct lsblk_devtree
*tr
, struct lsblk_device
*dev
)
335 struct lsblk_device
*x
= NULL
;
336 struct lsblk_iter itr
;
338 lsblk_reset_iter(&itr
, LSBLK_ITER_FORWARD
);
340 while (lsblk_devtree_next_device(tr
, &itr
, &x
) == 0) {
348 struct lsblk_device
*lsblk_devtree_get_device(struct lsblk_devtree
*tr
, const char *name
)
350 struct lsblk_device
*dev
= NULL
;
351 struct lsblk_iter itr
;
353 lsblk_reset_iter(&itr
, LSBLK_ITER_FORWARD
);
355 while (lsblk_devtree_next_device(tr
, &itr
, &dev
) == 0) {
356 if (strcmp(name
, dev
->name
) == 0)
363 int lsblk_devtree_remove_device(struct lsblk_devtree
*tr
, struct lsblk_device
*dev
)
365 DBG(TREE
, ul_debugobj(tr
, "remove device 0x%p [%s]", dev
, dev
->name
));
367 if (!lsblk_devtree_has_device(tr
, dev
))
370 list_del_init(&dev
->ls_roots
);
371 list_del_init(&dev
->ls_devices
);
372 lsblk_unref_device(dev
);
377 static int device_dedupkey_is_equal(
378 struct lsblk_device
*dev
,
379 struct lsblk_device
*pattern
)
381 assert(pattern
->dedupkey
);
383 if (!dev
->dedupkey
|| dev
== pattern
)
385 if (strcmp(dev
->dedupkey
, pattern
->dedupkey
) == 0) {
386 if (!device_is_partition(dev
) ||
387 strcmp(dev
->dedupkey
, dev
->wholedisk
->dedupkey
) != 0) {
388 DBG(DEV
, ul_debugobj(dev
, "%s: match deduplication pattern", dev
->name
));
395 static void device_dedup_dependencies(
396 struct lsblk_device
*dev
,
397 struct lsblk_device
*pattern
)
399 struct lsblk_iter itr
;
400 struct lsblk_devdep
*dp
;
402 lsblk_reset_iter(&itr
, LSBLK_ITER_FORWARD
);
404 while (device_next_child(dev
, &itr
, &dp
) == 0) {
405 struct lsblk_device
*child
= dp
->child
;
407 if (device_dedupkey_is_equal(child
, pattern
)) {
408 DBG(DEV
, ul_debugobj(dev
, "remove duplicate dependence: 0x%p [%s]",
409 dp
->child
, dp
->child
->name
));
410 remove_dependence(dp
);
412 device_dedup_dependencies(child
, pattern
);
416 static void devtree_dedup(struct lsblk_devtree
*tr
, struct lsblk_device
*pattern
)
418 struct lsblk_iter itr
;
419 struct lsblk_device
*dev
= NULL
;
421 lsblk_reset_iter(&itr
, LSBLK_ITER_FORWARD
);
423 DBG(TREE
, ul_debugobj(tr
, "de-duplicate by key: %s", pattern
->dedupkey
));
425 while (lsblk_devtree_next_root(tr
, &itr
, &dev
) == 0) {
426 if (device_dedupkey_is_equal(dev
, pattern
)) {
427 DBG(TREE
, ul_debugobj(tr
, "remove duplicate device: 0x%p [%s]",
429 /* Note that root list does not use ref-counting; the
430 * primary reference is ls_devices */
431 list_del_init(&dev
->ls_roots
);
433 device_dedup_dependencies(dev
, pattern
);
437 static int cmp_devices_devno(struct list_head
*a
, struct list_head
*b
,
438 __attribute__((__unused__
)) void *data
)
440 struct lsblk_device
*ax
= list_entry(a
, struct lsblk_device
, ls_devices
),
441 *bx
= list_entry(b
, struct lsblk_device
, ls_devices
);
443 return cmp_numbers(makedev(ax
->maj
, ax
->min
),
444 makedev(bx
->maj
, bx
->min
));
447 /* Note that dev->dedupkey has to be already set */
448 int lsblk_devtree_deduplicate_devices(struct lsblk_devtree
*tr
)
450 struct lsblk_device
*pattern
= NULL
;
451 struct lsblk_iter itr
;
454 list_sort(&tr
->devices
, cmp_devices_devno
, NULL
);
455 lsblk_reset_iter(&itr
, LSBLK_ITER_FORWARD
);
457 while (lsblk_devtree_next_device(tr
, &itr
, &pattern
) == 0) {
458 if (!pattern
->dedupkey
)
460 if (device_is_partition(pattern
) &&
461 strcmp(pattern
->dedupkey
, pattern
->wholedisk
->dedupkey
) == 0)
463 if (last
&& strcmp(pattern
->dedupkey
, last
) == 0)
466 devtree_dedup(tr
, pattern
);
467 last
= pattern
->dedupkey
;