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-2016 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
 332    /* Maintain a linear chain of nodes */
 333    if (!root->first) {
 334       root->first = node;
 335       root->last = node;
 336    } else {
 337       root->last->next = node;
 338       root->last = node;
 339    }
 340    node->inserted = true;             /* inserted into tree */
 341    return node;
 342
 343 }
 344
 345 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
 346 {
 347    if (!node) {
 348       buf[0] = 0;
 349       return 1;
 350    }
 351    tree_getpath(node->parent, buf, buf_size);
 352    /*
 353     * Fixup for Win32. If we have a Win32 directory and
 354     *    there is only a / in the buffer, remove it since
 355     *    win32 names don't generally start with /
 356     */
 357    if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
 358       buf[0] = '\0';
 359    }
 360    bstrncat(buf, node->fname, buf_size);
 361    /* Add a slash for all directories unless we are at the root,
 362     *  also add a slash to a soft linked file if it has children
 363     *  i.e. it is linked to a directory.
 364     */
 365    if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
 366        (node->soft_link && tree_node_has_child(node))) {
 367       bstrncat(buf, "/", buf_size);
 368    }
 369    return 1;
 370 }
 371
 372 /*
 373  * Change to specified directory
 374  */
 375 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 376 {
 377    if (path[0] == '.' && path[1] == '\0') {
 378       return node;
 379    }
 380    /* Handle relative path */
 381    if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
 382       TREE_NODE *parent = node->parent ? node->parent : node;
 383       if (path[2] == 0) {
 384          return parent;
 385       } else {
 386          return tree_cwd(path+3, root, parent);
 387       }
 388    }
 389    if (IsPathSeparator(path[0])) {
 390       Dmsg0(100, "Doing absolute lookup.\n");
 391       return tree_relcwd(path+1, root, (TREE_NODE *)root);
 392    }
 393    Dmsg0(100, "Doing relative lookup.\n");
 394    return tree_relcwd(path, root, node);
 395 }
 396
 397
 398 /*
 399  * Do a relative cwd -- i.e. relative to current node rather than root node
 400  */
 401 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 402 {
 403    char *p;
 404    int len;
 405    TREE_NODE *cd;
 406    char save_char;
 407    int match;
 408
 409    if (*path == 0) {
 410       return node;
 411    }
 412    /* Check the current segment only */
 413    if ((p = first_path_separator(path)) != NULL) {
 414       len = p - path;
 415    } else {
 416       len = strlen(path);
 417    }
 418    Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
 419    foreach_child(cd, node) {
 420       Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
 421       if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
 422           && strncmp(cd->fname, path, len) == 0) {
 423          break;
 424       }
 425       /* fnmatch has no len in call so we truncate the string */
 426       save_char = path[len];
 427       path[len] = 0;
 428       match = fnmatch(path, cd->fname, 0) == 0;
 429       path[len] = save_char;
 430       if (match) {
 431          break;
 432       }
 433    }
 434    if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
 435       return NULL;
 436    }
 437    if (!p) {
 438       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 439       return cd;
 440    }
 441    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 442    /* Check the next segment if any */
 443    return tree_relcwd(p+1, root, cd);
 444 }
 445
 446
 447
 448 #ifdef BUILD_TEST_PROGRAM
 449
 450 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 451
 452 static uint32_t FileIndex = 0;
 453 /*
 454  * Simple test program for tree routines
 455  */
 456 int main(int argc, char *argv[])
 457 {
 458     TREE_ROOT *root;
 459     TREE_NODE *node;
 460     char buf[MAXPATHLEN];
 461
 462     root = new_tree();
 463     root->fname = tree_alloc(root, 1);
 464     *root->fname = 0;
 465     root->fname_len = 0;
 466
 467     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 468
 469     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 470        tree_getpath(node, buf, sizeof(buf));
 471        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 472     }
 473
 474     node = (TREE_NODE *)root;
 475     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 476     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 477     if (node) {
 478        tree_getpath(node, buf, sizeof(buf));
 479        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 480     }
 481
 482     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 483     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 484     if (node) {
 485        tree_getpath(node, buf, sizeof(buf));
 486        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 487     } else {
 488        Dmsg0(100, "testprogs not found.\n");
 489     }
 490
 491     free_tree((TREE_NODE *)root);
 492
 493     return 0;
 494 }
 495
 496 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 497 {
 498    TREE_NODE *newparent = NULL;
 499    TREE_NODE *node;
 500    struct stat statbuf;
 501    DIR *dp;
 502    struct dirent *dir;
 503    char pathbuf[MAXPATHLEN];
 504    char file[MAXPATHLEN];
 505    int type;
 506    int i;
 507
 508    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 509    dp = opendir(path);
 510    if (!dp) {
 511       return;
 512    }
 513    while ((dir = readdir(dp))) {
 514       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 515          continue;
 516       }
 517       bstrncpy(file, dir->d_name, sizeof(file));
 518       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 519       if (lstat(pathbuf, &statbuf) < 0) {
 520          berrno be;
 521          printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
 522          continue;
 523       }
 524 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 525       type = TN_FILE;
 526       if (S_ISLNK(statbuf.st_mode))
 527          type =  TN_FILE;  /* link */
 528       else if (S_ISREG(statbuf.st_mode))
 529          type = TN_FILE;
 530       else if (S_ISDIR(statbuf.st_mode)) {
 531          type = TN_DIR;
 532       } else if (S_ISCHR(statbuf.st_mode))
 533          type = TN_FILE; /* char dev */
 534       else if (S_ISBLK(statbuf.st_mode))
 535          type = TN_FILE; /* block dev */
 536       else if (S_ISFIFO(statbuf.st_mode))
 537          type = TN_FILE; /* fifo */
 538       else if (S_ISSOCK(statbuf.st_mode))
 539          type = TN_FILE; /* sock */
 540       else {
 541          type = TN_FILE;
 542          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 543       }
 544
 545       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 546       node = new_tree_node(root);
 547       node->FileIndex = ++FileIndex;
 548       parent = insert_tree_node(pathbuf, node, root, parent);
 549       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 550          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 551          FillDirectoryTree(pathbuf, root, node);
 552       }
 553    }
 554    closedir(dp);
 555 }
 556
 557 #ifndef MAXPATHLEN
 558 #define MAXPATHLEN 2000
 559 #endif
 560
 561 void print_tree(char *path, TREE_NODE *tree)
 562 {
 563    char buf[MAXPATHLEN];
 564    char *termchr;
 565
 566    if (!tree) {
 567       return;
 568    }
 569    switch (tree->type) {
 570    case TN_DIR_NLS:
 571    case TN_DIR:
 572    case TN_NEWDIR:
 573       termchr = "/";
 574       break;
 575    case TN_ROOT:
 576    case TN_FILE:
 577    default:
 578       termchr = "";
 579       break;
 580    }
 581    Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 582    switch (tree->type) {
 583    case TN_FILE:
 584    case TN_NEWDIR:
 585    case TN_DIR:
 586    case TN_DIR_NLS:
 587       bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
 588       print_tree(buf, first_child(tree));
 589       break;
 590    case TN_ROOT:
 591       print_tree(path, first_child(tree));
 592       break;
 593    default:
 594       Pmsg1(000, "Unknown node type %d\n", tree->type);
 595    }
 596    print_tree(path, tree->sibling_);
 597    return;
 598 }
 599
 600 #endif