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

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