lib/dpkg/treewalk.c

   1 /*
   2  * libdpkg - Debian packaging suite library routines
   3  * treewalk.c - directory tree walk support
   4  *
   5  * Copyright © 2013-2016 Guillem Jover <guillem@debian.org>
   6  *
   7  * This is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
  19  */
  20
  21 #include <config.h>
  22 #include <compat.h>
  23
  24 #include <sys/stat.h>
  25 #include <sys/types.h>
  26 #include <dirent.h>
  27 #include <string.h>
  28 #include <stdbool.h>
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31
  32 #include <dpkg/dpkg.h>
  33 #include <dpkg/i18n.h>
  34 #include <dpkg/treewalk.h>
  35
  36 /* treenode functions. */
  37
  38 typedef int treewalk_stat_func(const char *pathname, struct stat *st);
  39
  40 struct treenode {
  41         struct treenode *up;    /* Parent dir. */
  42         struct treenode *next;  /* Next node in dir. */
  43         struct treenode **down; /* Dir contents. */
  44
  45         char *pathname;         /* Node pathname. */
  46         char *virtname;         /* Node virtname. */
  47         char *name;             /* Node name. */
  48
  49         struct stat *stat;      /* Node metadata. */
  50         mode_t mode;
  51
  52         size_t pathname_len;    /* Node pathname length. */
  53
  54         size_t down_used;       /* Number of used nodes in dir. */
  55         size_t down_size;       /* Number of allocated nodes in dir. */
  56 };
  57
  58 static inline struct treenode *
  59 treenode_alloc(void)
  60 {
  61         return m_calloc(1, sizeof(struct treenode));
  62 }
  63
  64 static struct treenode *
  65 treenode_root_new(const char *rootdir)
  66 {
  67         struct treenode *node;
  68
  69         node = treenode_alloc();
  70         node->up = NULL;
  71         node->pathname = m_strdup(rootdir);
  72         node->pathname_len = strlen(node->pathname);
  73         node->virtname = node->pathname + node->pathname_len;
  74         node->name = strrchr(node->pathname, '/');
  75         if (node->name == NULL)
  76                 node->name = node->pathname;
  77         else
  78                 node->name++;
  79
  80         return node;
  81 }
  82
  83 static struct treenode *
  84 treenode_node_new(struct treenode *root, struct treenode *dir, const char *name)
  85 {
  86         struct treenode *node;
  87
  88         node = treenode_alloc();
  89         node->up = dir;
  90
  91         node->pathname = str_fmt("%s/%s", node->up->pathname, name);
  92         node->pathname_len = strlen(node->pathname);
  93         node->virtname = node->pathname + root->pathname_len + 1;
  94         node->name = node->pathname + node->up->pathname_len + 1;
  95
  96         return node;
  97 }
  98
  99 static void
 100 treenode_stat(struct treenode *node, treewalk_stat_func *stat_func)
 101 {
 102         if (node->stat)
 103                 return;
 104
 105         node->stat = m_malloc(sizeof(*node->stat));
 106
 107         if (stat_func(node->pathname, node->stat) < 0)
 108                 ohshite(_("cannot stat pathname '%s'"), node->pathname);
 109
 110         node->mode = node->stat->st_mode;
 111 }
 112
 113 static mode_t
 114 dirent_to_mode_type(struct dirent *e)
 115 {
 116 #ifdef _DIRENT_HAVE_D_TYPE
 117         switch (e->d_type) {
 118         case DT_REG:
 119                 return S_IFREG;
 120         case DT_DIR:
 121                 return S_IFDIR;
 122         case DT_LNK:
 123                 return S_IFLNK;
 124         case DT_CHR:
 125                 return S_IFCHR;
 126         case DT_BLK:
 127                 return S_IFBLK;
 128         case DT_FIFO:
 129                 return S_IFIFO;
 130         case DT_SOCK:
 131                 return S_IFSOCK;
 132         case DT_UNKNOWN:
 133         default:
 134                 return 0;
 135         }
 136 #else
 137         return 0;
 138 #endif
 139 }
 140
 141 static void
 142 treenode_stat_shallow(struct treenode *node, struct dirent *e,
 143                       treewalk_stat_func *stat_func)
 144 {
 145         mode_t mode;
 146
 147         mode = dirent_to_mode_type(e);
 148         if (mode == 0 || S_ISDIR(mode) || S_ISLNK(mode))
 149                 treenode_stat(node, stat_func);
 150         else
 151                 node->mode |= mode;
 152 }
 153
 154 const char *
 155 treenode_get_name(struct treenode *node)
 156 {
 157         return node->name;
 158 }
 159
 160 const char *
 161 treenode_get_pathname(struct treenode *node)
 162 {
 163         return node->pathname;
 164 }
 165
 166 const char *
 167 treenode_get_virtname(struct treenode *node)
 168 {
 169         return node->virtname;
 170 }
 171
 172 mode_t
 173 treenode_get_mode(struct treenode *node)
 174 {
 175         return node->mode;
 176 }
 177
 178 struct stat *
 179 treenode_get_stat(struct treenode *node)
 180 {
 181         treenode_stat(node, lstat);
 182         return node->stat;
 183 }
 184
 185 struct treenode *
 186 treenode_get_parent(struct treenode *node)
 187 {
 188         return node->up;
 189 }
 190
 191 static inline bool
 192 treenode_is_dir(struct treenode *node)
 193 {
 194         return node && S_ISDIR(node->mode);
 195 }
 196
 197 static void
 198 treenode_resize_down(struct treenode *node)
 199 {
 200         size_t new_size;
 201
 202         if (node->down_size)
 203                 node->down_size *= 2;
 204         else if (node->stat->st_nlink > 4)
 205                 node->down_size = node->stat->st_nlink * 2;
 206         else
 207                 node->down_size = 8;
 208
 209         new_size = node->down_size * sizeof(*node);
 210         node->down = m_realloc(node->down, new_size);
 211 }
 212
 213 static int
 214 treenode_cmp(const void *a, const void *b)
 215 {
 216         return strcmp((*(const struct treenode **)a)->name,
 217                       (*(const struct treenode **)b)->name);
 218 }
 219
 220 static void
 221 treenode_sort_down(struct treenode *dir)
 222 {
 223         size_t i;
 224
 225         qsort(dir->down, dir->down_used, sizeof(struct treenode *), treenode_cmp);
 226
 227         /* Relink the nodes. */
 228         for (i = 0; i < dir->down_used - 1; i++)
 229                 dir->down[i]->next = dir->down[i + 1];
 230         dir->down[i]->next = NULL;
 231 }
 232
 233 static void
 234 treenode_fill_down(struct treenode *root, struct treenode *dir,
 235                    enum treewalk_options options)
 236 {
 237         DIR *d;
 238         struct dirent *e;
 239         treewalk_stat_func *stat_func;
 240
 241         if (options & TREEWALK_FOLLOW_LINKS)
 242                 stat_func = stat;
 243         else
 244                 stat_func = lstat;
 245
 246         d = opendir(dir->pathname);
 247         if (!d)
 248                 ohshite(_("cannot open directory '%s'"), dir->pathname);
 249
 250         while ((e = readdir(d)) != NULL) {
 251                 struct treenode *node;
 252
 253                 if (strcmp(e->d_name, ".") == 0 ||
 254                     strcmp(e->d_name, "..") == 0)
 255                         continue;
 256
 257                 if (dir->down_used >= dir->down_size)
 258                         treenode_resize_down(dir);
 259
 260                 node = treenode_node_new(root, dir, e->d_name);
 261                 if (options & TREEWALK_FORCE_STAT)
 262                         treenode_stat(node, stat_func);
 263                 else
 264                         treenode_stat_shallow(node, e, stat_func);
 265
 266                 dir->down[dir->down_used] = node;
 267                 dir->down_used++;
 268         }
 269
 270         closedir(d);
 271 }
 272
 273 static void
 274 treenode_free_node(struct treenode *node)
 275 {
 276         free(node->pathname);
 277         free(node->stat);
 278         free(node);
 279 }
 280
 281 static void
 282 treenode_free_down(struct treenode *node)
 283 {
 284         size_t i;
 285
 286         if (!node->down_size)
 287                 return;
 288
 289         for (i = 0; i < node->down_used; i++)
 290                 treenode_free_node(node->down[i]);
 291         free(node->down);
 292 }
 293
 294
 295 /* treeroot functions. */
 296
 297 struct treeroot {
 298         struct treenode *rootnode;
 299
 300         struct treenode *curdir;
 301         struct treenode *curnode;
 302
 303         enum treewalk_options options;
 304         struct treewalk_funcs func;
 305 };
 306
 307 static inline void
 308 treeroot_set_curdir(struct treeroot *tree, struct treenode *node)
 309 {
 310         tree->curdir = node;
 311 }
 312
 313 static inline void
 314 treeroot_set_curnode(struct treeroot *tree, struct treenode *node)
 315 {
 316         tree->curnode = node;
 317 }
 318
 319 static bool
 320 treeroot_skip_node(struct treeroot *tree, struct treenode *node)
 321 {
 322         if (tree->func.skip)
 323                 return tree->func.skip(node);
 324
 325         return false;
 326 }
 327
 328 static void
 329 treeroot_fill_node(struct treeroot *tree, struct treenode *dir)
 330 {
 331         treenode_fill_down(tree->rootnode, dir, tree->options);
 332 }
 333
 334 static void
 335 treeroot_sort_node(struct treeroot *tree, struct treenode *dir)
 336 {
 337         static struct treenode *down_empty[] = { NULL, NULL };
 338
 339         if (dir->down_used == 0)
 340                 dir->down = down_empty;
 341         else if (tree->func.sort)
 342                 tree->func.sort(dir);
 343         else
 344                 treenode_sort_down(dir);
 345 }
 346
 347 static void
 348 treeroot_visit_node(struct treeroot *tree, struct treenode *node)
 349 {
 350         if (tree->func.visit == NULL)
 351                 return;
 352
 353         if (!treeroot_skip_node(tree, node))
 354                 tree->func.visit(node);
 355 }
 356
 357 /**
 358  * Open a new tree to be walked.
 359  *
 360  * @param rootdir The root directory to start walking the tree.
 361  * @param options The options specifying how to walk the tree.
 362  * @param func    The functions callbacks.
 363  */
 364 struct treeroot *
 365 treewalk_open(const char *rootdir, enum treewalk_options options,
 366               const struct treewalk_funcs *func)
 367 {
 368         struct treeroot *tree;
 369         struct treenode *root;
 370
 371         tree = m_malloc(sizeof(*tree));
 372
 373         tree->options = options;
 374         if (func)
 375                 tree->func = *func;
 376         else
 377                 tree->func = TREEWALK_OBJECT;
 378
 379         root = treenode_root_new(rootdir);
 380         treenode_stat(root, lstat);
 381
 382         if (!treenode_is_dir(root))
 383                 ohshit(_("treewalk root %s is not a directory"), rootdir);
 384
 385         treeroot_set_curnode(tree, root);
 386         tree->rootnode = tree->curdir = root;
 387
 388         return tree;
 389 }
 390
 391 /**
 392  * Return the current node.
 393  *
 394  * This function is only needed if you want to start walking the tree from
 395  * the root node. With something like:
 396  *
 397  * @code
 398  * struct treeroot *tree;
 399  * struct treenode *node;
 400  *
 401  * tree = treewalk_open(...);
 402  * for (node = treewalk_node(tree); node; node = treewalk_next(tree))
 403  *         visitor(node);
 404  * treewalk_close(tree);
 405  * @endcode
 406  *
 407  * @param tree The tree structure.
 408  */
 409 struct treenode *
 410 treewalk_node(struct treeroot *tree)
 411 {
 412         return tree->curnode;
 413 }
 414
 415 /**
 416  * Return the next node.
 417  *
 418  * This function works basically as an iterator. And will return NULL when
 419  * the whole tree has been traversed. When starting it will skip the root
 420  * node, so you might want to use treewalk_node() to get that, otherwise
 421  * you could use it like this:
 422  *
 423  * @code
 424  * struct treeroot *tree;
 425  * struct treenode *node;
 426  *
 427  * tree = treewalk_open(...);
 428  * while ((node = treewalk_next(tree))
 429  *         visitor(node);
 430  * treewalk_close(tree);
 431  * @endcode
 432  *
 433  * @param tree The tree structure.
 434  */
 435 struct treenode *
 436 treewalk_next(struct treeroot *tree)
 437 {
 438         struct treenode *node;
 439
 440         /* Handle rootless trees, such as uninitialized or fully traversed. */
 441         if (tree->rootnode == NULL)
 442                 return NULL;
 443
 444         node = tree->curnode;
 445
 446         /* Handle end of tree. */
 447         if (node == NULL)
 448                 return NULL;
 449
 450         /* Get next node, descending or sidewide. */
 451         if (treenode_is_dir(node) && !treeroot_skip_node(tree, node)) {
 452                 struct treenode *dir;
 453
 454                 treeroot_fill_node(tree, node);
 455                 treeroot_sort_node(tree, node);
 456                 treeroot_set_curdir(tree, node);
 457
 458                 /* Check for directory loops. */
 459                 for (dir = node->up; dir; dir = dir->up) {
 460                         if (dir->stat->st_dev == node->stat->st_dev &&
 461                             dir->stat->st_ino == node->stat->st_ino)
 462                                 break;
 463                 }
 464
 465                 /* Skip directory loops. */
 466                 if (dir)
 467                         node = node->next;
 468                 else
 469                         node = node->down[0];
 470         } else {
 471                 node = node->next;
 472         }
 473
 474         /* Back track node, ascending. */
 475         while (node == NULL) {
 476                 struct treenode *olddir = tree->curdir;
 477
 478                 if (tree->curdir->next) {
 479                         /* Next entry in the parent directory. */
 480                         node = tree->curdir->next;
 481                         treeroot_set_curdir(tree, olddir->up);
 482                         treenode_free_down(olddir);
 483                 } else if (tree->curdir->up) {
 484                         /* Next entry in the grand-parent directory. */
 485                         node = tree->curdir->up->next;
 486                         treeroot_set_curdir(tree, olddir->up->up);
 487                         treenode_free_down(olddir);
 488                         treenode_free_down(olddir->up);
 489                 } else {
 490                         /* Otherwise, we're in the rootnode. */
 491                         treenode_free_down(olddir);
 492                         treenode_free_node(olddir);
 493                         break;
 494                 }
 495
 496                 if (tree->curdir == NULL) {
 497                         treenode_free_node(tree->rootnode);
 498                         tree->rootnode = NULL;
 499                         break;
 500                 }
 501         }
 502
 503         treeroot_set_curnode(tree, node);
 504
 505         return node;
 506 }
 507
 508 /**
 509  * Closes the tree being walked.
 510  *
 511  * It will free any resources previously allocated.
 512  */
 513 void
 514 treewalk_close(struct treeroot *tree)
 515 {
 516         free(tree);
 517 }
 518
 519 /**
 520  * Tree walker.
 521  *
 522  * @param rootdir The root directory to start walking the tree.
 523  * @param options The options specifying how to walk the tree.
 524  * @param func    The function callbacks.
 525  */
 526 int
 527 treewalk(const char *rootdir, enum treewalk_options options,
 528          struct treewalk_funcs *func)
 529 {
 530         struct treeroot *tree;
 531         struct treenode *node;
 532
 533         tree = treewalk_open(rootdir, options, func);
 534
 535         /* Breath first visit. */
 536         for (node = treewalk_node(tree); node; node = treewalk_next(tree))
 537                 treeroot_visit_node(tree, node);
 538
 539         treewalk_close(tree);
 540
 541         return 0;
 542 }