misc-utils/lsblk-devtree.c

   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
  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
  32 struct lsblk_device *lsblk_new_device()
  33 {
  34         struct lsblk_device *dev;
  35
  36         dev = calloc(1, sizeof(*dev));
  37         if (!dev)
  38                 return NULL;
  39
  40         dev->refcount = 1;
  41         dev->removable = -1;
  42         dev->discard_granularity = (uint64_t) -1;
  43
  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);
  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
  59 /* removes dependence from child as well as from parent */
  60 static int remove_dependence(struct lsblk_devdep *dep)
  61 {
  62         if (!dep)
  63                 return -EINVAL;
  64
  65         DBG(DEP, ul_debugobj(dep, "   dealloc"));
  66
  67         list_del_init(&dep->ls_childs);
  68         list_del_init(&dep->ls_parents);
  69
  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
  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);
  93         }
  94
  95         return 0;
  96 }
  97
  98 void lsblk_unref_device(struct lsblk_device *dev)
  99 {
 100         if (!dev)
 101                 return;
 102
 103         if (--dev->refcount <= 0) {
 104                 DBG(DEV, ul_debugobj(dev, " freeing [%s] <<", dev->name));
 105
 106                 device_remove_dependences(dev);
 107                 lsblk_device_free_properties(dev->properties);
 108
 109                 lsblk_unref_device(dev->wholedisk);
 110
 111                 free(dev->dm_name);
 112                 free(dev->filename);
 113                 free(dev->mountpoint);
 114                 free(dev->dedupkey);
 115
 116                 ul_unref_path(dev->sysfs);
 117
 118                 DBG(DEV, ul_debugobj(dev, " >> dealloc [%s]", dev->name));
 119                 free(dev->name);
 120                 free(dev);
 121         }
 122 }
 123
 124 int lsblk_device_has_child(struct lsblk_device *dev, struct lsblk_device *child)
 125 {
 126         struct lsblk_device *x = NULL;
 127         struct lsblk_iter itr;
 128
 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;
 134         }
 135
 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
 146         if (lsblk_device_has_child(parent, child))
 147                 return 1;
 148
 149         dp = calloc(1, sizeof(*dp));
 150         if (!dp)
 151                 return -ENOMEM;
 152
 153         INIT_LIST_HEAD(&dp->ls_childs);
 154         INIT_LIST_HEAD(&dp->ls_parents);
 155
 156         dp->child = child;
 157         list_add_tail(&dp->ls_childs, &parent->childs);
 158
 159         dp->parent = parent;
 160         list_add_tail(&dp->ls_parents, &child->parents);
 161
 162         DBG(DEV, ul_debugobj(parent, "add dependence 0x%p [%s->%s]", dp, parent->name, child->name));
 163
 164         return 0;
 165 }
 166
 167 static int device_next_child(struct lsblk_device *dev,
 168                           struct lsblk_iter *itr,
 169                           struct lsblk_devdep **dp)
 170 {
 171         int rc = 1;
 172
 173         if (!dev || !itr || !dp)
 174                 return -EINVAL;
 175         *dp = NULL;
 176
 177         if (!itr->head)
 178                 LSBLK_ITER_INIT(itr, &dev->childs);
 179         if (itr->p != itr->head) {
 180                 LSBLK_ITER_ITERATE(itr, *dp, struct lsblk_devdep, ls_childs);
 181                 rc = 0;
 182         }
 183
 184         return rc;
 185 }
 186
 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;
 192         int rc = device_next_child(dev, itr, &dp);
 193
 194         if (!child)
 195                 return -EINVAL;
 196
 197         *child = rc == 0 ? dp->child : NULL;
 198         return rc;
 199 }
 200
 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);
 206         if (!dp)
 207                 return 0;
 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 }
 234
 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 {
 260         if (!tr)
 261                 return;
 262
 263         if (--tr->refcount <= 0) {
 264                 DBG(TREE, ul_debugobj(tr, "dealloc"));
 265
 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);
 270                 }
 271                 free(tr);
 272         }
 273 }
 274
 275 int lsblk_devtree_add_root(struct lsblk_devtree *tr, struct lsblk_device *dev)
 276 {
 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 */
 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
 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
 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
 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 }
 376
 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) ||
 387                      strcmp(dev->dedupkey, dev->wholedisk->dedupkey) != 0) {
 388                         DBG(DEV, ul_debugobj(dev, "%s: match deduplication pattern", dev->name));
 389                         return 1;
 390                 }
 391         }
 392         return 0;
 393 }
 394
 395 static void device_dedup_dependencies(
 396                         struct lsblk_device *dev,
 397                         struct lsblk_device *pattern)
 398 {
 399         struct lsblk_iter itr;
 400         struct lsblk_devdep *dp;
 401
 402         lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
 403
 404         while (device_next_child(dev, &itr, &dp) == 0) {
 405                 struct lsblk_device *child = dp->child;
 406
 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);
 411                 } else
 412                         device_dedup_dependencies(child, pattern);
 413         }
 414 }
 415
 416 static void devtree_dedup(struct lsblk_devtree *tr, struct lsblk_device *pattern)
 417 {
 418         struct lsblk_iter itr;
 419         struct lsblk_device *dev = NULL;
 420
 421         lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
 422
 423         DBG(TREE, ul_debugobj(tr, "de-duplicate by key: %s", pattern->dedupkey));
 424
 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]",
 428                                                 dev, dev->name));
 429                         /* Note that root list does not use ref-counting; the
 430                          * primary reference is ls_devices */
 431                         list_del_init(&dev->ls_roots);
 432                 } else
 433                         device_dedup_dependencies(dev, pattern);
 434         }
 435 }
 436
 437 static int cmp_devices_devno(struct list_head *a, struct list_head *b,
 438                           __attribute__((__unused__)) void *data)
 439 {
 440         struct lsblk_device *ax = list_entry(a, struct lsblk_device, ls_devices),
 441                             *bx = list_entry(b, struct lsblk_device, ls_devices);
 442
 443         return cmp_numbers(makedev(ax->maj, ax->min),
 444                            makedev(bx->maj, bx->min));
 445 }
 446
 447 /* Note that dev->dedupkey has to be already set */
 448 int lsblk_devtree_deduplicate_devices(struct lsblk_devtree *tr)
 449 {
 450         struct lsblk_device *pattern = NULL;
 451         struct lsblk_iter itr;
 452         char *last = NULL;
 453
 454         list_sort(&tr->devices, cmp_devices_devno, NULL);
 455         lsblk_reset_iter(&itr, LSBLK_ITER_FORWARD);
 456
 457         while (lsblk_devtree_next_device(tr, &itr, &pattern) == 0) {
 458                 if (!pattern->dedupkey)
 459                         continue;
 460                 if (device_is_partition(pattern) &&
 461                     strcmp(pattern->dedupkey, pattern->wholedisk->dedupkey) == 0)
 462                         continue;
 463                 if (last && strcmp(pattern->dedupkey, last) == 0)
 464                         continue;
 465
 466                 devtree_dedup(tr, pattern);
 467                 last = pattern->dedupkey;
 468         }
 469         return 0;
 470 }