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    HL_ENTRY* entry = NULL;
  97    root->hardlinks.init(entry, &entry->link, 0);
  98    return root;
  99 }
 100
 101 /*
 102  * Create a new tree node.
 103  */
 104 static TREE_NODE *new_tree_node(TREE_ROOT *root)
 105 {
 106    TREE_NODE *node;
 107    int size = sizeof(TREE_NODE);
 108    node = (TREE_NODE *)tree_alloc(root, size);
 109    memset(node, 0, size);
 110    node->delta_seq = -1;
 111    return node;
 112 }
 113
 114 /*
 115  * This routine can be called to release the
 116  *  previously allocated tree node.
 117  */
 118 static void free_tree_node(TREE_ROOT *root)
 119 {
 120    int asize = BALIGN(sizeof(TREE_NODE));
 121    root->mem->rem += asize;
 122    root->mem->mem -= asize;
 123 }
 124
 125 void tree_remove_node(TREE_ROOT *root, TREE_NODE *node)
 126 {
 127    int asize = BALIGN(sizeof(TREE_NODE));
 128    node->parent->child.remove(node);
 129    if ((root->mem->mem - asize) == (char *)node) {
 130       free_tree_node(root);
 131    } else {
 132       Dmsg0(0, "Can't release tree node\n");
 133    }
 134 }
 135
 136 /*
 137  * Allocate bytes for filename in tree structure.
 138  *  Keep the pointers properly aligned by allocating
 139  *  sizes that are aligned.
 140  */
 141 static char *tree_alloc(TREE_ROOT *root, int size)
 142 {
 143    char *buf;
 144    int asize = BALIGN(size);
 145
 146    if (root->mem->rem < asize) {
 147       uint32_t mb_size;
 148       if (root->total_size >= (MAX_BUF_SIZE / 2)) {
 149          mb_size = MAX_BUF_SIZE;
 150       } else {
 151          mb_size = MAX_BUF_SIZE / 2;
 152       }
 153       malloc_buf(root, mb_size);
 154    }
 155    root->mem->rem -= asize;
 156    buf = root->mem->mem;
 157    root->mem->mem += asize;
 158    return buf;
 159 }
 160
 161
 162 /* This routine frees the whole tree */
 163 void free_tree(TREE_ROOT *root)
 164 {
 165    struct s_mem *mem, *rel;
 166    uint32_t freed_blocks = 0;
 167
 168    root->hardlinks.destroy();
 169    for (mem=root->mem; mem; ) {
 170       rel = mem;
 171       mem = mem->next;
 172       free(rel);
 173       freed_blocks++;
 174    }
 175    if (root->cached_path) {
 176       free_pool_memory(root->cached_path);
 177       root->cached_path = NULL;
 178    }
 179    Dmsg3(100, "Total size=%u blocks=%u freed_blocks=%u\n", root->total_size, root->blocks, freed_blocks);
 180    free(root);
 181    garbage_collect_memory();
 182    return;
 183 }
 184
 185 /* Add Delta part for this node */
 186 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
 187                          JobId_t JobId, int32_t FileIndex)
 188 {
 189    struct delta_list *elt =
 190       (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
 191
 192    elt->next = node->delta_list;
 193    elt->JobId = JobId;
 194    elt->FileIndex = FileIndex;
 195    node->delta_list = elt;
 196 }
 197
 198 /*
 199  * Insert a node in the tree. This is the main subroutine
 200  *   called when building a tree.
 201  *
 202  */
 203 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
 204                             TREE_ROOT *root, TREE_NODE *parent)
 205 {
 206    char *p, *q;
 207    int path_len = strlen(path);
 208    TREE_NODE *node;
 209
 210    Dmsg1(100, "insert_tree_node: %s\n", path);
 211    /*
 212     * If trailing slash on path, strip it
 213     */
 214    if (path_len > 0) {
 215       q = path + path_len - 1;
 216       if (IsPathSeparator(*q)) {
 217          *q = 0;                      /* strip trailing slash */
 218       } else {
 219          q = NULL;                    /* no trailing slash */
 220       }
 221    } else {
 222       q = NULL;                       /* no trailing slash */
 223    }
 224    /* If no filename, strip last component of path as "filename" */
 225    if (*fname == 0) {
 226       p = (char *)last_path_separator(path);  /* separate path and filename */
 227       if (p) {
 228          fname = p + 1;               /* set new filename */
 229          *p = '\0';                   /* terminate new path */
 230       }
 231    } else {
 232       p = NULL;
 233    }
 234    if (*fname) {
 235       if (!parent) {                  /* if no parent, we need to make one */
 236          Dmsg1(100, "make_tree_path for %s\n", path);
 237          path_len = strlen(path);     /* get new length */
 238          if (path_len == root->cached_path_len &&
 239              strcmp(path, root->cached_path) == 0) {
 240             parent = root->cached_parent;
 241          } else {
 242             root->cached_path_len = path_len;
 243             pm_strcpy(&root->cached_path, path);
 244             parent = make_tree_path(path, root);
 245             root->cached_parent = parent;
 246          }
 247          Dmsg1(100, "parent=%s\n", parent->fname);
 248       }
 249    } else {
 250       fname = path;
 251       if (!parent) {
 252          parent = (TREE_NODE *)root;
 253          type = TN_DIR_NLS;
 254       }
 255       Dmsg1(100, "No / found: %s\n", path);
 256    }
 257
 258    node = search_and_insert_tree_node(fname, 0, root, parent);
 259    if (q) {                           /* if trailing slash on entry */
 260       *q = '/';                       /*  restore it */
 261    }
 262    if (p) {                           /* if slash in path trashed */
 263       *p = '/';                       /* restore full path */
 264    }
 265    return node;
 266 }
 267
 268 /*
 269  * Ensure that all appropriate nodes for a full path exist in
 270  *  the tree.
 271  */
 272 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
 273 {
 274    TREE_NODE *parent, *node;
 275    char *fname, *p;
 276    int type = TN_NEWDIR;
 277
 278    Dmsg1(100, "make_tree_path: %s\n", path);
 279    if (*path == 0) {
 280       Dmsg0(100, "make_tree_path: parent=*root*\n");
 281       return (TREE_NODE *)root;
 282    }
 283    p = (char *)last_path_separator(path);           /* get last dir component of path */
 284    if (p) {
 285       fname = p + 1;
 286       *p = 0;                         /* terminate path */
 287       parent = make_tree_path(path, root);
 288       *p = '/';                       /* restore full name */
 289    } else {
 290       fname = path;
 291       parent = (TREE_NODE *)root;
 292       type = TN_DIR_NLS;
 293    }
 294    node = search_and_insert_tree_node(fname, type, root, parent);
 295    return node;
 296 }
 297
 298 static int node_compare(void *item1, void *item2)
 299 {
 300    TREE_NODE *tn1 = (TREE_NODE *)item1;
 301    TREE_NODE *tn2 = (TREE_NODE *)item2;
 302    if (tn1->fname[0] > tn2->fname[0]) {
 303       return 1;
 304    } else if (tn1->fname[0] < tn2->fname[0]) {
 305       return -1;
 306    }
 307    return strcmp(tn1->fname, tn2->fname);
 308 }
 309
 310 /*
 311  *  See if the fname already exists. If not insert a new node for it.
 312  */
 313 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
 314                TREE_ROOT *root, TREE_NODE *parent)
 315 {
 316    TREE_NODE *node, *found_node;
 317    node = new_tree_node(root);
 318    node->fname = fname;
 319    found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
 320    if (found_node != node) {          /* already in list */
 321       free_tree_node(root);           /* free node allocated above */
 322       found_node->inserted = false;
 323       return found_node;
 324    }
 325    /* It was not found, but is now inserted */
 326    node->fname_len = strlen(fname);
 327    node->fname = tree_alloc(root, node->fname_len + 1);
 328    strcpy(node->fname, fname);
 329    node->parent = parent;
 330    node->type = type;
 331    node->can_access = true;
 332
 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