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 */
19 #include "lsblk.h"
20 #include "sysfs.h"
21 #include "pathnames.h"
22
23
24 void lsblk_reset_iter(struct lsblk_iter *itr, int direction)
25 {
26 if (direction == -1)
27 direction = itr->direction;
28
29 memset(itr, 0, sizeof(*itr));
30 itr->direction = direction;
31 }
32
33 struct lsblk_device *lsblk_new_device(void)
34 {
35 struct lsblk_device *dev;
36
37 dev = calloc(1, sizeof(*dev));
38 if (!dev)
39 return NULL;
40
41 dev->refcount = 1;
42 dev->removable = -1;
43 dev->discard_granularity = (uint64_t) -1;
44
45 INIT_LIST_HEAD(&dev->childs);
46 INIT_LIST_HEAD(&dev->parents);
47 INIT_LIST_HEAD(&dev->ls_roots);
48 INIT_LIST_HEAD(&dev->ls_devices);
49
50 DBG(DEV, ul_debugobj(dev, "alloc"));
51 return dev;
52 }
53
54 void lsblk_ref_device(struct lsblk_device *dev)
55 {
56 if (dev)
57 dev->refcount++;
58 }
59
60 /* removes dependence from child as well as from parent */
61 static int remove_dependence(struct lsblk_devdep *dep)
62 {
63 if (!dep)
64 return -EINVAL;
65
66 DBG(DEP, ul_debugobj(dep, " dealloc"));
67
68 list_del_init(&dep->ls_childs);
69 list_del_init(&dep->ls_parents);
70
71 free(dep);
72 return 0;
73 }
74
75 static int device_remove_dependences(struct lsblk_device *dev)
76 {
77 if (!dev)
78 return -EINVAL;
79
80 if (!list_empty(&dev->childs))
81 DBG(DEV, ul_debugobj(dev, " %s: remove all children deps", dev->name));
82 while (!list_empty(&dev->childs)) {
83 struct lsblk_devdep *dp = list_entry(dev->childs.next,
84 struct lsblk_devdep, ls_childs);
85 remove_dependence(dp);
86 }
87
88 if (!list_empty(&dev->parents))
89 DBG(DEV, ul_debugobj(dev, " %s: remove all parents deps", dev->name));
90 while (!list_empty(&dev->parents)) {
91 struct lsblk_devdep *dp = list_entry(dev->parents.next,
92 struct lsblk_devdep, ls_parents);
93 remove_dependence(dp);
94 }
95
96 return 0;
97 }
98
99 void lsblk_unref_device(struct lsblk_device *dev)
100 {
101 if (!dev)
102 return;
103
104 if (--dev->refcount <= 0) {
105 DBG(DEV, ul_debugobj(dev, " freeing [%s] <<", dev->name));
106
107 device_remove_dependences(dev);
108 lsblk_device_free_properties(dev->properties);
109 lsblk_device_free_filesystems(dev);
110
111 lsblk_unref_device(dev->wholedisk);
112
113 free(dev->dm_name);
114 free(dev->filename);
115 free(dev->dedupkey);
116
117 ul_unref_path(dev->sysfs);
118
119 DBG(DEV, ul_debugobj(dev, " >> dealloc [%s]", dev->name));
120 free(dev->name);
121 free(dev);
122 }
123 }
124
125 int lsblk_device_has_child(struct lsblk_device *dev, struct lsblk_device *child)
126 {
127 struct lsblk_device *x = NULL;
128 struct lsblk_iter itr;
129
130 lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
131
132 while (lsblk_device_next_child(dev, &itr, &x) == 0) {
133 if (x == child)
134 return 1;
135 }
136
137 return 0;
138 }
139
140 int lsblk_device_new_dependence(struct lsblk_device *parent, struct lsblk_device *child)
141 {
142 struct lsblk_devdep *dp;
143
144 if (!parent || !child)
145 return -EINVAL;
146
147 if (lsblk_device_has_child(parent, child))
148 return 1;
149
150 dp = calloc(1, sizeof(*dp));
151 if (!dp)
152 return -ENOMEM;
153
154 INIT_LIST_HEAD(&dp->ls_childs);
155 INIT_LIST_HEAD(&dp->ls_parents);
156
157 dp->child = child;
158 list_add_tail(&dp->ls_childs, &parent->childs);
159
160 dp->parent = parent;
161 list_add_tail(&dp->ls_parents, &child->parents);
162
163 DBG(DEV, ul_debugobj(parent, "add dependence 0x%p [%s->%s]", dp, parent->name, child->name));
164
165 return 0;
166 }
167
168 static int device_next_child(struct lsblk_device *dev,
169 struct lsblk_iter *itr,
170 struct lsblk_devdep **dp)
171 {
172 int rc = 1;
173
174 if (!dev || !itr || !dp)
175 return -EINVAL;
176 *dp = NULL;
177
178 if (!itr->head)
179 LSBLK_ITER_INIT(itr, &dev->childs);
180 if (itr->p != itr->head) {
181 LSBLK_ITER_ITERATE(itr, *dp, struct lsblk_devdep, ls_childs);
182 rc = 0;
183 }
184
185 return rc;
186 }
187
188 int lsblk_device_next_child(struct lsblk_device *dev,
189 struct lsblk_iter *itr,
190 struct lsblk_device **child)
191 {
192 struct lsblk_devdep *dp = NULL;
193 int rc = device_next_child(dev, itr, &dp);
194
195 if (!child)
196 return -EINVAL;
197
198 *child = rc == 0 ? dp->child : NULL;
199 return rc;
200 }
201
202 int lsblk_device_is_last_parent(struct lsblk_device *dev, struct lsblk_device *parent)
203 {
204 struct lsblk_devdep *dp = list_last_entry(
205 &dev->parents,
206 struct lsblk_devdep, ls_parents);
207 if (!dp)
208 return 0;
209 return dp->parent == parent;
210 }
211
212 int lsblk_device_next_parent(
213 struct lsblk_device *dev,
214 struct lsblk_iter *itr,
215 struct lsblk_device **parent)
216 {
217 int rc = 1;
218
219 if (!dev || !itr || !parent)
220 return -EINVAL;
221 *parent = NULL;
222
223 if (!itr->head)
224 LSBLK_ITER_INIT(itr, &dev->parents);
225 if (itr->p != itr->head) {
226 struct lsblk_devdep *dp = NULL;
227 LSBLK_ITER_ITERATE(itr, dp, struct lsblk_devdep, ls_parents);
228 if (dp)
229 *parent = dp->parent;
230 rc = 0;
231 }
232
233 return rc;
234 }
235
236 struct lsblk_devtree *lsblk_new_devtree(void)
237 {
238 struct lsblk_devtree *tr;
239
240 tr = calloc(1, sizeof(*tr));
241 if (!tr)
242 return NULL;
243
244 tr->refcount = 1;
245
246 INIT_LIST_HEAD(&tr->roots);
247 INIT_LIST_HEAD(&tr->devices);
248 INIT_LIST_HEAD(&tr->pktcdvd_map);
249
250 DBG(TREE, ul_debugobj(tr, "alloc"));
251 return tr;
252 }
253
254 void lsblk_ref_devtree(struct lsblk_devtree *tr)
255 {
256 if (tr)
257 tr->refcount++;
258 }
259
260 void lsblk_unref_devtree(struct lsblk_devtree *tr)
261 {
262 if (!tr)
263 return;
264
265 if (--tr->refcount <= 0) {
266 DBG(TREE, ul_debugobj(tr, "dealloc"));
267
268 while (!list_empty(&tr->devices)) {
269 struct lsblk_device *dev = list_entry(tr->devices.next,
270 struct lsblk_device, ls_devices);
271 lsblk_devtree_remove_device(tr, dev);
272 }
273
274 while (!list_empty(&tr->pktcdvd_map)) {
275 struct lsblk_devnomap *map = list_entry(tr->pktcdvd_map.next,
276 struct lsblk_devnomap, ls_devnomap);
277 list_del(&map->ls_devnomap);
278 free(map);
279 }
280
281 free(tr);
282 }
283 }
284
285 static int has_root(struct lsblk_devtree *tr, struct lsblk_device *dev)
286 {
287 struct lsblk_iter itr;
288 struct lsblk_device *x = NULL;
289
290 lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
291
292 while (lsblk_devtree_next_root(tr, &itr, &x) == 0) {
293 if (x == dev)
294 return 1;
295 }
296 return 0;
297 }
298
299 int lsblk_devtree_add_root(struct lsblk_devtree *tr, struct lsblk_device *dev)
300 {
301 if (has_root(tr, dev))
302 return 0;
303
304 if (!lsblk_devtree_has_device(tr, dev))
305 lsblk_devtree_add_device(tr, dev);
306
307 /* We don't increment reference counter for tr->roots list. The primary
308 * reference is tr->devices */
309
310 DBG(TREE, ul_debugobj(tr, "add root device 0x%p [%s]", dev, dev->name));
311 list_add_tail(&dev->ls_roots, &tr->roots);
312 return 0;
313 }
314
315 int lsblk_devtree_remove_root(struct lsblk_devtree *tr __attribute__((unused)),
316 struct lsblk_device *dev)
317 {
318 DBG(TREE, ul_debugobj(tr, "remove root device 0x%p [%s]", dev, dev->name));
319 list_del_init(&dev->ls_roots);
320
321 return 0;
322 }
323
324 int lsblk_devtree_next_root(struct lsblk_devtree *tr,
325 struct lsblk_iter *itr,
326 struct lsblk_device **dev)
327 {
328 int rc = 1;
329
330 if (!tr || !itr || !dev)
331 return -EINVAL;
332 *dev = NULL;
333 if (!itr->head)
334 LSBLK_ITER_INIT(itr, &tr->roots);
335 if (itr->p != itr->head) {
336 LSBLK_ITER_ITERATE(itr, *dev, struct lsblk_device, ls_roots);
337 rc = 0;
338 }
339 return rc;
340 }
341
342 int lsblk_devtree_add_device(struct lsblk_devtree *tr, struct lsblk_device *dev)
343 {
344 lsblk_ref_device(dev);
345
346 DBG(TREE, ul_debugobj(tr, "add device 0x%p [%s]", dev, dev->name));
347 list_add_tail(&dev->ls_devices, &tr->devices);
348 return 0;
349 }
350
351 int lsblk_devtree_next_device(struct lsblk_devtree *tr,
352 struct lsblk_iter *itr,
353 struct lsblk_device **dev)
354 {
355 int rc = 1;
356
357 if (!tr || !itr || !dev)
358 return -EINVAL;
359 *dev = NULL;
360 if (!itr->head)
361 LSBLK_ITER_INIT(itr, &tr->devices);
362 if (itr->p != itr->head) {
363 LSBLK_ITER_ITERATE(itr, *dev, struct lsblk_device, ls_devices);
364 rc = 0;
365 }
366 return rc;
367 }
368
369 int lsblk_devtree_has_device(struct lsblk_devtree *tr, struct lsblk_device *dev)
370 {
371 struct lsblk_device *x = NULL;
372 struct lsblk_iter itr;
373
374 lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
375
376 while (lsblk_devtree_next_device(tr, &itr, &x) == 0) {
377 if (x == dev)
378 return 1;
379 }
380
381 return 0;
382 }
383
384 struct lsblk_device *lsblk_devtree_get_device(struct lsblk_devtree *tr, const char *name)
385 {
386 struct lsblk_device *dev = NULL;
387 struct lsblk_iter itr;
388
389 lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
390
391 while (lsblk_devtree_next_device(tr, &itr, &dev) == 0) {
392 if (strcmp(name, dev->name) == 0)
393 return dev;
394 }
395
396 return NULL;
397 }
398
399 int lsblk_devtree_remove_device(struct lsblk_devtree *tr, struct lsblk_device *dev)
400 {
401 DBG(TREE, ul_debugobj(tr, "remove device 0x%p [%s]", dev, dev->name));
402
403 if (!lsblk_devtree_has_device(tr, dev))
404 return 1;
405
406 list_del_init(&dev->ls_roots);
407 list_del_init(&dev->ls_devices);
408 lsblk_unref_device(dev);
409
410 return 0;
411 }
412
413 static void read_pktcdvd_map(struct lsblk_devtree *tr)
414 {
415 char buf[PATH_MAX];
416 FILE *f;
417
418 assert(tr->pktcdvd_read == 0);
419
420 f = ul_path_fopen(NULL, "r", _PATH_SYS_CLASS "/pktcdvd/device_map");
421 if (!f)
422 goto done;
423
424 while (fgets(buf, sizeof(buf), f)) {
425 struct lsblk_devnomap *map;
426 int pkt_maj, pkt_min, blk_maj, blk_min;
427
428 if (sscanf(buf, "%*s %d:%d %d:%d\n",
429 &pkt_maj, &pkt_min,
430 &blk_maj, &blk_min) != 4)
431 continue;
432
433 map = malloc(sizeof(*map));
434 if (!map)
435 break;
436 map->holder = makedev(pkt_maj, pkt_min);
437 map->slave = makedev(blk_maj, blk_min);
438 INIT_LIST_HEAD(&map->ls_devnomap);
439 list_add_tail(&map->ls_devnomap, &tr->pktcdvd_map);
440 }
441
442 fclose(f);
443 done:
444 tr->pktcdvd_read = 1;
445 }
446
447 /* returns opposite device of @devno for blk->pkt relation -- e.g. if devno
448 * is_slave (blk) then returns holder (pkt) and vice-versa */
449 dev_t lsblk_devtree_pktcdvd_get_mate(struct lsblk_devtree *tr, dev_t devno, int is_slave)
450 {
451 struct list_head *p;
452
453 if (!tr->pktcdvd_read)
454 read_pktcdvd_map(tr);
455 if (list_empty(&tr->pktcdvd_map))
456 return 0;
457
458 list_for_each(p, &tr->pktcdvd_map) {
459 struct lsblk_devnomap *x = list_entry(p, struct lsblk_devnomap, ls_devnomap);
460
461 if (is_slave && devno == x->slave)
462 return x->holder;
463 if (!is_slave && devno == x->holder)
464 return x->slave;
465 }
466 return 0;
467 }
468
469 static int device_dedupkey_is_equal(
470 struct lsblk_device *dev,
471 struct lsblk_device *pattern)
472 {
473 assert(pattern->dedupkey);
474
475 if (!dev->dedupkey || dev == pattern)
476 return 0;
477 if (strcmp(dev->dedupkey, pattern->dedupkey) == 0) {
478 if (!device_is_partition(dev) ||
479 !dev->wholedisk->dedupkey ||
480 strcmp(dev->dedupkey, dev->wholedisk->dedupkey) != 0) {
481 DBG(DEV, ul_debugobj(dev, "%s: match deduplication pattern", dev->name));
482 return 1;
483 }
484 }
485 return 0;
486 }
487
488 static void device_dedup_dependencies(
489 struct lsblk_device *dev,
490 struct lsblk_device *pattern)
491 {
492 struct lsblk_iter itr;
493 struct lsblk_devdep *dp;
494
495 lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
496
497 while (device_next_child(dev, &itr, &dp) == 0) {
498 struct lsblk_device *child = dp->child;
499
500 if (device_dedupkey_is_equal(child, pattern)) {
501 DBG(DEV, ul_debugobj(dev, "remove duplicate dependence: 0x%p [%s]",
502 dp->child, dp->child->name));
503 remove_dependence(dp);
504 } else
505 device_dedup_dependencies(child, pattern);
506 }
507 }
508
509 static void devtree_dedup(struct lsblk_devtree *tr, struct lsblk_device *pattern)
510 {
511 struct lsblk_iter itr;
512 struct lsblk_device *dev = NULL;
513
514 lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
515
516 DBG(TREE, ul_debugobj(tr, "de-duplicate by key: %s", pattern->dedupkey));
517
518 while (lsblk_devtree_next_root(tr, &itr, &dev) == 0) {
519 if (device_dedupkey_is_equal(dev, pattern)) {
520 DBG(TREE, ul_debugobj(tr, "remove duplicate device: 0x%p [%s]",
521 dev, dev->name));
522 /* Note that root list does not use ref-counting; the
523 * primary reference is ls_devices */
524 list_del_init(&dev->ls_roots);
525 } else
526 device_dedup_dependencies(dev, pattern);
527 }
528 }
529
530 static int cmp_devices_devno(struct list_head *a, struct list_head *b,
531 __attribute__((__unused__)) void *data)
532 {
533 struct lsblk_device *ax = list_entry(a, struct lsblk_device, ls_devices),
534 *bx = list_entry(b, struct lsblk_device, ls_devices);
535
536 return cmp_numbers(makedev(ax->maj, ax->min),
537 makedev(bx->maj, bx->min));
538 }
539
540 /* Note that dev->dedupkey has to be already set */
541 int lsblk_devtree_deduplicate_devices(struct lsblk_devtree *tr)
542 {
543 struct lsblk_device *pattern = NULL;
544 struct lsblk_iter itr;
545 char *last = NULL;
546
547 list_sort(&tr->devices, cmp_devices_devno, NULL);
548 lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
549
550 while (lsblk_devtree_next_device(tr, &itr, &pattern) == 0) {
551 if (!pattern->dedupkey)
552 continue;
553 if (device_is_partition(pattern) &&
554 pattern->wholedisk->dedupkey &&
555 strcmp(pattern->dedupkey, pattern->wholedisk->dedupkey) == 0)
556 continue;
557 if (last && strcmp(pattern->dedupkey, last) == 0)
558 continue;
559
560 devtree_dedup(tr, pattern);
561 last = pattern->dedupkey;
562 }
563 return 0;
564 }