git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/tree.c

   1 /*
   2    Bacula(R) - The Network Backup Solution
   3
   4    Copyright (C) 2000-2017 Kern Sibbald
   5
   6    The original author of Bacula is Kern Sibbald, with contributions
   7    from many others, a complete list can be found in the file AUTHORS.
   8
   9    You may use this file and others of this release according to the
  10    license defined in the LICENSE file, which includes the Affero General
  11    Public License, v3.0 ("AGPLv3") and some additional permissions and
  12    terms pursuant to its AGPLv3 Section 7.
  13
  14    This notice must be preserved when any source code is
  15    conveyed and/or propagated.
  16
  17    Bacula(R) is a registered trademark of Kern Sibbald.
  18 */
  19 /*
  20  * Directory tree build/traverse routines
  21  *
  22  *    Kern Sibbald, June MMII
  23  *
  24 */
  25
  26
  27 #include "bacula.h"
  28 #include "findlib/find.h"
  29
  30 #define B_PAGE_SIZE 4096
  31 #define MAX_PAGES 2400
  32 #define MAX_BUF_SIZE (MAX_PAGES * B_PAGE_SIZE)  /* approx 10MB */
  33
  34 /* Forward referenced subroutines */
  35 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
  36                TREE_ROOT *root, TREE_NODE *parent);
  37 static char *tree_alloc(TREE_ROOT *root, int size);
  38
  39 /*
  40  * NOTE !!!!! we turn off Debug messages for performance reasons.
  41  */
  42 #undef Dmsg0
  43 #undef Dmsg1
  44 #undef Dmsg2
  45 #undef Dmsg3
  46 #define Dmsg0(n,f)
  47 #define Dmsg1(n,f,a1)
  48 #define Dmsg2(n,f,a1,a2)
  49 #define Dmsg3(n,f,a1,a2,a3)
  50
  51 /*
  52  * This subroutine gets a big buffer.
  53  */
  54 static void malloc_buf(TREE_ROOT *root, int size)
  55 {
  56    struct s_mem *mem;
  57
  58    mem = (struct s_mem *)malloc(size);
  59    root->total_size += size;
  60    root->blocks++;
  61    mem->next = root->mem;
  62    root->mem = mem;
  63    mem->mem = mem->first;
  64    mem->rem = (char *)mem + size - mem->mem;
  65    Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
  66 }
  67
  68
  69 /*
  70  * Note, we allocate a big buffer in the tree root
  71  *  from which we allocate nodes. This runs more
  72  *  than 100 times as fast as directly using malloc()
  73  *  for each of the nodes.
  74  */
  75 TREE_ROOT *new_tree(int count)
  76 {
  77    TREE_ROOT *root;
  78    uint32_t size;
  79
  80    if (count < 1000) {                /* minimum tree size */
  81       count = 1000;
  82    }
  83    root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
  84    memset(root, 0, sizeof(TREE_ROOT));
  85    /* Assume filename + node  = 40 characters average length */
  86    size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
  87    if (count > 1000000 || size > (MAX_BUF_SIZE / 2)) {
  88       size = MAX_BUF_SIZE;
  89    }
  90    Dmsg2(400, "count=%d size=%d\n", count, size);
  91    malloc_buf(root, size);
  92    root->cached_path_len = -1;
  93    root->cached_path = get_pool_memory(PM_FNAME);
  94    root->type = TN_ROOT;
  95    root->fname = "";
  96    root->can_access = 1;
  97    HL_ENTRY* entry = NULL;
  98    root->hardlinks.init(entry, &entry->link, 0);
  99    return root;
 100 }
 101
 102 /*
 103  * Create a new tree node.
 104  */
 105 static TREE_NODE *new_tree_node(TREE_ROOT *root)
 106 {
 107    TREE_NODE *node;
 108    int size = sizeof(TREE_NODE);
 109    node = (TREE_NODE *)tree_alloc(root, size);
 110    memset(node, 0, size);
 111    node->delta_seq = -1;
 112    node->can_access = 1;
 113    return node;
 114 }
 115
 116 /*
 117  * This routine can be called to release the
 118  *  previously allocated tree node.
 119  */
 120 static void free_tree_node(TREE_ROOT *root)
 121 {
 122    int asize = BALIGN(sizeof(TREE_NODE));
 123    root->mem->rem += asize;
 124    root->mem->mem -= asize;
 125 }
 126
 127 void tree_remove_node(TREE_ROOT *root, TREE_NODE *node)
 128 {
 129    int asize = BALIGN(sizeof(TREE_NODE));
 130    node->parent->child.remove(node);
 131    if ((root->mem->mem - asize) == (char *)node) {
 132       free_tree_node(root);
 133    } else {
 134       Dmsg0(0, "Can't release tree node\n");
 135    }
 136 }
 137
 138 /*
 139  * Allocate bytes for filename in tree structure.
 140  *  Keep the pointers properly aligned by allocating
 141  *  sizes that are aligned.
 142  */
 143 static char *tree_alloc(TREE_ROOT *root, int size)
 144 {
 145    char *buf;
 146    int asize = BALIGN(size);
 147
 148    if (root->mem->rem < asize) {
 149       uint32_t mb_size;
 150       if (root->total_size >= (MAX_BUF_SIZE / 2)) {
 151          mb_size = MAX_BUF_SIZE;
 152       } else {
 153          mb_size = MAX_BUF_SIZE / 2;
 154       }
 155       malloc_buf(root, mb_size);
 156    }
 157    root->mem->rem -= asize;
 158    buf = root->mem->mem;
 159    root->mem->mem += asize;
 160    return buf;
 161 }
 162
 163
 164 /* This routine frees the whole tree */
 165 void free_tree(TREE_ROOT *root)
 166 {
 167    struct s_mem *mem, *rel;
 168    uint32_t freed_blocks = 0;
 169
 170    root->hardlinks.destroy();
 171    for (mem=root->mem; mem; ) {
 172       rel = mem;
 173       mem = mem->next;
 174       free(rel);
 175       freed_blocks++;
 176    }
 177    if (root->cached_path) {
 178       free_pool_memory(root->cached_path);
 179       root->cached_path = NULL;
 180    }
 181    Dmsg3(100, "Total size=%u blocks=%u freed_blocks=%u\n", root->total_size, root->blocks, freed_blocks);
 182    free(root);
 183    garbage_collect_memory();
 184    return;
 185 }
 186
 187 /* Add Delta part for this node */
 188 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
 189                          JobId_t JobId, int32_t FileIndex)
 190 {
 191    struct delta_list *elt =
 192       (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
 193
 194    elt->next = node->delta_list;
 195    elt->JobId = JobId;
 196    elt->FileIndex = FileIndex;
 197    node->delta_list = elt;
 198 }
 199
 200 /*
 201  * Insert a node in the tree. This is the main subroutine
 202  *   called when building a tree.
 203  *
 204  */
 205 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
 206                             TREE_ROOT *root, TREE_NODE *parent)
 207 {
 208    char *p, *q;
 209    int path_len = strlen(path);
 210    TREE_NODE *node;
 211
 212    Dmsg1(100, "insert_tree_node: %s\n", path);
 213    /*
 214     * If trailing slash on path, strip it
 215     */
 216    if (path_len > 0) {
 217       q = path + path_len - 1;
 218       if (IsPathSeparator(*q)) {
 219          *q = 0;                      /* strip trailing slash */
 220       } else {
 221          q = NULL;                    /* no trailing slash */
 222       }
 223    } else {
 224       q = NULL;                       /* no trailing slash */
 225    }
 226    /* If no filename, strip last component of path as "filename" */
 227    if (*fname == 0) {
 228       p = (char *)last_path_separator(path);  /* separate path and filename */
 229       if (p) {
 230          fname = p + 1;               /* set new filename */
 231          *p = '\0';                   /* terminate new path */
 232       }
 233    } else {
 234       p = NULL;
 235    }
 236    if (*fname) {
 237       if (!parent) {                  /* if no parent, we need to make one */
 238          Dmsg1(100, "make_tree_path for %s\n", path);
 239          path_len = strlen(path);     /* get new length */
 240          if (path_len == root->cached_path_len &&
 241              strcmp(path, root->cached_path) == 0) {
 242             parent = root->cached_parent;
 243          } else {
 244             root->cached_path_len = path_len;
 245             pm_strcpy(&root->cached_path, path);
 246             parent = make_tree_path(path, root);
 247             root->cached_parent = parent;
 248          }
 249          Dmsg1(100, "parent=%s\n", parent->fname);
 250       }
 251    } else {
 252       fname = path;
 253       if (!parent) {
 254          parent = (TREE_NODE *)root;
 255          type = TN_DIR_NLS;
 256       }
 257       Dmsg1(100, "No / found: %s\n", path);
 258    }
 259
 260    node = search_and_insert_tree_node(fname, 0, root, parent);
 261    if (q) {                           /* if trailing slash on entry */
 262       *q = '/';                       /*  restore it */
 263    }
 264    if (p) {                           /* if slash in path trashed */
 265       *p = '/';                       /* restore full path */
 266    }
 267    return node;
 268 }
 269
 270 /*
 271  * Ensure that all appropriate nodes for a full path exist in
 272  *  the tree.
 273  */
 274 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
 275 {
 276    TREE_NODE *parent, *node;
 277    char *fname, *p;
 278    int type = TN_NEWDIR;
 279
 280    Dmsg1(100, "make_tree_path: %s\n", path);
 281    if (*path == 0) {
 282       Dmsg0(100, "make_tree_path: parent=*root*\n");
 283       return (TREE_NODE *)root;
 284    }
 285    p = (char *)last_path_separator(path);           /* get last dir component of path */
 286    if (p) {
 287       fname = p + 1;
 288       *p = 0;                         /* terminate path */
 289       parent = make_tree_path(path, root);
 290       *p = '/';                       /* restore full name */
 291    } else {
 292       fname = path;
 293       parent = (TREE_NODE *)root;
 294       type = TN_DIR_NLS;
 295    }
 296    node = search_and_insert_tree_node(fname, type, root, parent);
 297    return node;
 298 }
 299
 300 static int node_compare(void *item1, void *item2)
 301 {
 302    TREE_NODE *tn1 = (TREE_NODE *)item1;
 303    TREE_NODE *tn2 = (TREE_NODE *)item2;
 304    if (tn1->fname[0] > tn2->fname[0]) {
 305       return 1;
 306    } else if (tn1->fname[0] < tn2->fname[0]) {
 307       return -1;
 308    }
 309    return strcmp(tn1->fname, tn2->fname);
 310 }
 311
 312 /*
 313  *  See if the fname already exists. If not insert a new node for it.
 314  */
 315 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
 316                TREE_ROOT *root, TREE_NODE *parent)
 317 {
 318    TREE_NODE *node, *found_node;
 319    node = new_tree_node(root);
 320    node->fname = fname;
 321    found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
 322    if (found_node != node) {          /* already in list */
 323       free_tree_node(root);           /* free node allocated above */
 324       found_node->inserted = false;
 325       return found_node;
 326    }
 327    /* It was not found, but is now inserted */
 328    node->fname_len = strlen(fname);
 329    node->fname = tree_alloc(root, node->fname_len + 1);
 330    strcpy(node->fname, fname);
 331    node->parent = parent;
 332    node->type = type;
 333    /* Maintain a linear chain of nodes */
 334    if (!root->first) {
 335       root->first = node;
 336       root->last = node;
 337    } else {
 338       root->last->next = node;
 339       root->last = node;
 340    }
 341    node->inserted = true;             /* inserted into tree */
 342    return node;
 343
 344 }
 345
 346 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
 347 {
 348    if (!node) {
 349       buf[0] = 0;
 350       return 1;
 351    }
 352    tree_getpath(node->parent, buf, buf_size);
 353    /*
 354     * Fixup for Win32. If we have a Win32 directory and
 355     *    there is only a / in the buffer, remove it since
 356     *    win32 names don't generally start with /
 357     */
 358    if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
 359       buf[0] = '\0';
 360    }
 361    bstrncat(buf, node->fname, buf_size);
 362    /* Add a slash for all directories unless we are at the root,
 363     *  also add a slash to a soft linked file if it has children
 364     *  i.e. it is linked to a directory.
 365     */
 366    if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
 367        (node->soft_link && tree_node_has_child(node))) {
 368       bstrncat(buf, "/", buf_size);
 369    }
 370    return 1;
 371 }
 372
 373 /*
 374  * Change to specified directory
 375  */
 376 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 377 {
 378    if (path[0] == '.' && path[1] == '\0') {
 379       return node;
 380    }
 381    /* Handle relative path */
 382    if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
 383       TREE_NODE *parent = node->parent ? node->parent : node;
 384       if (path[2] == 0) {
 385          return parent;
 386       } else {
 387          return tree_cwd(path+3, root, parent);
 388       }
 389    }
 390    if (IsPathSeparator(path[0])) {
 391       Dmsg0(100, "Doing absolute lookup.\n");
 392       return tree_relcwd(path+1, root, (TREE_NODE *)root);
 393    }
 394    Dmsg0(100, "Doing relative lookup.\n");
 395    return tree_relcwd(path, root, node);
 396 }
 397
 398
 399 /*
 400  * Do a relative cwd -- i.e. relative to current node rather than root node
 401  */
 402 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 403 {
 404    char *p;
 405    int len;
 406    TREE_NODE *cd;
 407    char save_char;
 408    int match;
 409
 410    if (*path == 0) {
 411       return node;
 412    }
 413    /* Check the current segment only */
 414    if ((p = first_path_separator(path)) != NULL) {
 415       len = p - path;
 416    } else {
 417       len = strlen(path);
 418    }
 419    Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
 420    foreach_child(cd, node) {
 421       Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
 422       if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
 423           && strncmp(cd->fname, path, len) == 0) {
 424          break;
 425       }
 426       /* fnmatch has no len in call so we truncate the string */
 427       save_char = path[len];
 428       path[len] = 0;
 429       match = fnmatch(path, cd->fname, 0) == 0;
 430       path[len] = save_char;
 431       if (match) {
 432          break;
 433       }
 434    }
 435    if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
 436       return NULL;
 437    }
 438    if (!cd->can_access) {       /* Will display permission denied */
 439       return cd;
 440    }
 441    if (!p) {
 442       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 443       return cd;
 444    }
 445    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 446    /* Check the next segment if any */
 447    return tree_relcwd(p+1, root, cd);
 448 }
 449
 450
 451
 452 #ifdef BUILD_TEST_PROGRAM
 453
 454 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 455
 456 static uint32_t FileIndex = 0;
 457 /*
 458  * Simple test program for tree routines
 459  */
 460 int main(int argc, char *argv[])
 461 {
 462     TREE_ROOT *root;
 463     TREE_NODE *node;
 464     char buf[MAXPATHLEN];
 465
 466     root = new_tree();
 467     root->fname = tree_alloc(root, 1);
 468     *root->fname = 0;
 469     root->fname_len = 0;
 470
 471     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 472
 473     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 474        tree_getpath(node, buf, sizeof(buf));
 475        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 476     }
 477
 478     node = (TREE_NODE *)root;
 479     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 480     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 481     if (node) {
 482        tree_getpath(node, buf, sizeof(buf));
 483        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 484     }
 485
 486     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 487     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 488     if (node) {
 489        tree_getpath(node, buf, sizeof(buf));
 490        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 491     } else {
 492        Dmsg0(100, "testprogs not found.\n");
 493     }
 494
 495     free_tree((TREE_NODE *)root);
 496
 497     return 0;
 498 }
 499
 500 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 501 {
 502    TREE_NODE *newparent = NULL;
 503    TREE_NODE *node;
 504    struct stat statbuf;
 505    DIR *dp;
 506    struct dirent *dir;
 507    char pathbuf[MAXPATHLEN];
 508    char file[MAXPATHLEN];
 509    int type;
 510    int i;
 511
 512    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 513    dp = opendir(path);
 514    if (!dp) {
 515       return;
 516    }
 517    while ((dir = readdir(dp))) {
 518       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 519          continue;
 520       }
 521       bstrncpy(file, dir->d_name, sizeof(file));
 522       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 523       if (lstat(pathbuf, &statbuf) < 0) {
 524          berrno be;
 525          printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
 526          continue;
 527       }
 528 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 529       type = TN_FILE;
 530       if (S_ISLNK(statbuf.st_mode))
 531          type =  TN_FILE;  /* link */
 532       else if (S_ISREG(statbuf.st_mode))
 533          type = TN_FILE;
 534       else if (S_ISDIR(statbuf.st_mode)) {
 535          type = TN_DIR;
 536       } else if (S_ISCHR(statbuf.st_mode))
 537          type = TN_FILE; /* char dev */
 538       else if (S_ISBLK(statbuf.st_mode))
 539          type = TN_FILE; /* block dev */
 540       else if (S_ISFIFO(statbuf.st_mode))
 541          type = TN_FILE; /* fifo */
 542       else if (S_ISSOCK(statbuf.st_mode))
 543          type = TN_FILE; /* sock */
 544       else {
 545          type = TN_FILE;
 546          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 547       }
 548
 549       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 550       node = new_tree_node(root);
 551       node->FileIndex = ++FileIndex;
 552       parent = insert_tree_node(pathbuf, node, root, parent);
 553       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 554          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 555          FillDirectoryTree(pathbuf, root, node);
 556       }
 557    }
 558    closedir(dp);
 559 }
 560
 561 #ifndef MAXPATHLEN
 562 #define MAXPATHLEN 2000
 563 #endif
 564
 565 void print_tree(char *path, TREE_NODE *tree)
 566 {
 567    char buf[MAXPATHLEN];
 568    char *termchr;
 569
 570    if (!tree) {
 571       return;
 572    }
 573    switch (tree->type) {
 574    case TN_DIR_NLS:
 575    case TN_DIR:
 576    case TN_NEWDIR:
 577       termchr = "/";
 578       break;
 579    case TN_ROOT:
 580    case TN_FILE:
 581    default:
 582       termchr = "";
 583       break;
 584    }
 585    Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 586    switch (tree->type) {
 587    case TN_FILE:
 588    case TN_NEWDIR:
 589    case TN_DIR:
 590    case TN_DIR_NLS:
 591       bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
 592       print_tree(buf, first_child(tree));
 593       break;
 594    case TN_ROOT:
 595       print_tree(path, first_child(tree));
 596       break;
 597    default:
 598       Pmsg1(000, "Unknown node type %d\n", tree->type);
 599    }
 600    print_tree(path, tree->sibling_);
 601    return;
 602 }
 603
 604 #endif