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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2002-2008 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 PAGE_SIZE 4096
  40 #define MAX_PAGES 2400
  41 #define MAX_BUF_SIZE (MAX_PAGES * 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
 174    for (mem=root->mem; mem; ) {
 175       rel = mem;
 176       mem = mem->next;
 177       free(rel);
 178    }
 179    if (root->cached_path) {
 180       free_pool_memory(root->cached_path);
 181       root->cached_path = NULL;
 182    }
 183    Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
 184    free(root);
 185    return;
 186 }
 187
 188 /* Add Delta part for this node */
 189 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
 190                          JobId_t JobId, int32_t FileIndex)
 191 {
 192    struct delta_list *elt =
 193       (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
 194
 195    elt->next = node->delta_list;
 196    elt->JobId = JobId;
 197    elt->FileIndex = FileIndex;
 198    node->delta_list = elt;
 199 }
 200
 201 /*
 202  * Insert a node in the tree. This is the main subroutine
 203  *   called when building a tree.
 204  *
 205  */
 206 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
 207                             TREE_ROOT *root, TREE_NODE *parent)
 208 {
 209    char *p, *q;
 210    int path_len = strlen(path);
 211    TREE_NODE *node;
 212
 213    Dmsg1(100, "insert_tree_node: %s\n", path);
 214    /*
 215     * If trailing slash on path, strip it
 216     */
 217    if (path_len > 0) {
 218       q = path + path_len - 1;
 219       if (IsPathSeparator(*q)) {
 220          *q = 0;                      /* strip trailing slash */
 221       } else {
 222          q = NULL;                    /* no trailing slash */
 223       }
 224    } else {
 225       q = NULL;                       /* no trailing slash */
 226    }
 227    /* If no filename, strip last component of path as "filename" */
 228    if (*fname == 0) {
 229       p = (char *)last_path_separator(path);  /* separate path and filename */
 230       if (p) {
 231          fname = p + 1;               /* set new filename */
 232          *p = '\0';                   /* terminate new path */
 233       }
 234    } else {
 235       p = NULL;
 236    }
 237    if (*fname) {
 238       if (!parent) {                  /* if no parent, we need to make one */
 239          Dmsg1(100, "make_tree_path for %s\n", path);
 240          path_len = strlen(path);     /* get new length */
 241          if (path_len == root->cached_path_len &&
 242              strcmp(path, root->cached_path) == 0) {
 243             parent = root->cached_parent;
 244          } else {
 245             root->cached_path_len = path_len;
 246             pm_strcpy(&root->cached_path, path);
 247             parent = make_tree_path(path, root);
 248             root->cached_parent = parent;
 249          }
 250          Dmsg1(100, "parent=%s\n", parent->fname);
 251       }
 252    } else {
 253       fname = path;
 254       if (!parent) {
 255          parent = (TREE_NODE *)root;
 256          type = TN_DIR_NLS;
 257       }
 258       Dmsg1(100, "No / found: %s\n", path);
 259    }
 260
 261    node = search_and_insert_tree_node(fname, 0, root, parent);
 262    if (q) {                           /* if trailing slash on entry */
 263       *q = '/';                       /*  restore it */
 264    }
 265    if (p) {                           /* if slash in path trashed */
 266       *p = '/';                       /* restore full path */
 267    }
 268    return node;
 269 }
 270
 271 /*
 272  * Ensure that all appropriate nodes for a full path exist in
 273  *  the tree.
 274  */
 275 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
 276 {
 277    TREE_NODE *parent, *node;
 278    char *fname, *p;
 279    int type = TN_NEWDIR;
 280
 281    Dmsg1(100, "make_tree_path: %s\n", path);
 282    if (*path == 0) {
 283       Dmsg0(100, "make_tree_path: parent=*root*\n");
 284       return (TREE_NODE *)root;
 285    }
 286    p = (char *)last_path_separator(path);           /* get last dir component of path */
 287    if (p) {
 288       fname = p + 1;
 289       *p = 0;                         /* terminate path */
 290       parent = make_tree_path(path, root);
 291       *p = '/';                       /* restore full name */
 292    } else {
 293       fname = path;
 294       parent = (TREE_NODE *)root;
 295       type = TN_DIR_NLS;
 296    }
 297    node = search_and_insert_tree_node(fname, type, root, parent);
 298    return node;
 299 }
 300
 301 static int node_compare(void *item1, void *item2)
 302 {
 303    TREE_NODE *tn1 = (TREE_NODE *)item1;
 304    TREE_NODE *tn2 = (TREE_NODE *)item2;
 305    if (tn1->fname[0] > tn2->fname[0]) {
 306       return 1;
 307    } else if (tn1->fname[0] < tn2->fname[0]) {
 308       return -1;
 309    }
 310    return strcmp(tn1->fname, tn2->fname);
 311 }
 312
 313 /*
 314  *  See if the fname already exists. If not insert a new node for it.
 315  */
 316 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
 317                TREE_ROOT *root, TREE_NODE *parent)
 318 {
 319    TREE_NODE *node, *found_node;
 320    node = new_tree_node(root);
 321    node->fname = fname;
 322    found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
 323    if (found_node != node) {          /* already in list */
 324       free_tree_node(root);           /* free node allocated above */
 325       found_node->inserted = false;
 326       return found_node;
 327    }
 328    /* It was not found, but is now inserted */
 329    node->fname_len = strlen(fname);
 330    node->fname = tree_alloc(root, node->fname_len + 1);
 331    strcpy(node->fname, fname);
 332    node->parent = parent;
 333    node->type = type;
 334
 335    /* Maintain a linear chain of nodes */
 336    if (!root->first) {
 337       root->first = node;
 338       root->last = node;
 339    } else {
 340       root->last->next = node;
 341       root->last = node;
 342    }
 343    node->inserted = true;             /* inserted into tree */
 344    return node;
 345
 346 }
 347
 348 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
 349 {
 350    if (!node) {
 351       buf[0] = 0;
 352       return 1;
 353    }
 354    tree_getpath(node->parent, buf, buf_size);
 355    /*
 356     * Fixup for Win32. If we have a Win32 directory and
 357     *    there is only a / in the buffer, remove it since
 358     *    win32 names don't generally start with /
 359     */
 360    if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
 361       buf[0] = '\0';
 362    }
 363    bstrncat(buf, node->fname, buf_size);
 364    /* Add a slash for all directories unless we are at the root,
 365     *  also add a slash to a soft linked file if it has children
 366     *  i.e. it is linked to a directory.
 367     */
 368    if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
 369        (node->soft_link && tree_node_has_child(node))) {
 370       bstrncat(buf, "/", buf_size);
 371    }
 372    return 1;
 373 }
 374
 375 /*
 376  * Change to specified directory
 377  */
 378 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 379 {
 380    if (path[0] == '.' && path[1] == '\0') {
 381       return node;
 382    }
 383    /* Handle relative path */
 384    if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
 385       TREE_NODE *parent = node->parent ? node->parent : node;
 386       if (path[2] == 0) {
 387          return parent;
 388       } else {
 389          return tree_cwd(path+3, root, parent);
 390       }
 391    }
 392    if (IsPathSeparator(path[0])) {
 393       Dmsg0(100, "Doing absolute lookup.\n");
 394       return tree_relcwd(path+1, root, (TREE_NODE *)root);
 395    }
 396    Dmsg0(100, "Doing relative lookup.\n");
 397    return tree_relcwd(path, root, node);
 398 }
 399
 400
 401 /*
 402  * Do a relative cwd -- i.e. relative to current node rather than root node
 403  */
 404 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 405 {
 406    char *p;
 407    int len;
 408    TREE_NODE *cd;
 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    }
 427    if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
 428       return NULL;
 429    }
 430    if (!p) {
 431       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 432       return cd;
 433    }
 434    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 435    /* Check the next segment if any */
 436    return tree_relcwd(p+1, root, cd);
 437 }
 438
 439
 440
 441 #ifdef BUILD_TEST_PROGRAM
 442
 443 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 444
 445 static uint32_t FileIndex = 0;
 446 /*
 447  * Simple test program for tree routines
 448  */
 449 int main(int argc, char *argv[])
 450 {
 451     TREE_ROOT *root;
 452     TREE_NODE *node;
 453     char buf[MAXPATHLEN];
 454
 455     root = new_tree();
 456     root->fname = tree_alloc(root, 1);
 457     *root->fname = 0;
 458     root->fname_len = 0;
 459
 460     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 461
 462     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 463        tree_getpath(node, buf, sizeof(buf));
 464        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 465     }
 466
 467     node = (TREE_NODE *)root;
 468     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 469     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 470     if (node) {
 471        tree_getpath(node, buf, sizeof(buf));
 472        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 473     }
 474
 475     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 476     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 477     if (node) {
 478        tree_getpath(node, buf, sizeof(buf));
 479        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 480     } else {
 481        Dmsg0(100, "testprogs not found.\n");
 482     }
 483
 484     free_tree((TREE_NODE *)root);
 485
 486     return 0;
 487 }
 488
 489 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 490 {
 491    TREE_NODE *newparent = NULL;
 492    TREE_NODE *node;
 493    struct stat statbuf;
 494    DIR *dp;
 495    struct dirent *dir;
 496    char pathbuf[MAXPATHLEN];
 497    char file[MAXPATHLEN];
 498    int type;
 499    int i;
 500
 501    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 502    dp = opendir(path);
 503    if (!dp) {
 504       return;
 505    }
 506    while ((dir = readdir(dp))) {
 507       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 508          continue;
 509       }
 510       bstrncpy(file, dir->d_name, sizeof(file));
 511       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 512       if (lstat(pathbuf, &statbuf) < 0) {
 513          berrno be;
 514          printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
 515          continue;
 516       }
 517 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 518       type = TN_FILE;
 519       if (S_ISLNK(statbuf.st_mode))
 520          type =  TN_FILE;  /* link */
 521       else if (S_ISREG(statbuf.st_mode))
 522          type = TN_FILE;
 523       else if (S_ISDIR(statbuf.st_mode)) {
 524          type = TN_DIR;
 525       } else if (S_ISCHR(statbuf.st_mode))
 526          type = TN_FILE; /* char dev */
 527       else if (S_ISBLK(statbuf.st_mode))
 528          type = TN_FILE; /* block dev */
 529       else if (S_ISFIFO(statbuf.st_mode))
 530          type = TN_FILE; /* fifo */
 531       else if (S_ISSOCK(statbuf.st_mode))
 532          type = TN_FILE; /* sock */
 533       else {
 534          type = TN_FILE;
 535          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 536       }
 537
 538       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 539       node = new_tree_node(root);
 540       node->FileIndex = ++FileIndex;
 541       parent = insert_tree_node(pathbuf, node, root, parent);
 542       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 543          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 544          FillDirectoryTree(pathbuf, root, node);
 545       }
 546    }
 547    closedir(dp);
 548 }
 549
 550 #ifndef MAXPATHLEN
 551 #define MAXPATHLEN 2000
 552 #endif
 553
 554 void print_tree(char *path, TREE_NODE *tree)
 555 {
 556    char buf[MAXPATHLEN];
 557    char *termchr;
 558
 559    if (!tree) {
 560       return;
 561    }
 562    switch (tree->type) {
 563    case TN_DIR_NLS:
 564    case TN_DIR:
 565    case TN_NEWDIR:
 566       termchr = "/";
 567       break;
 568    case TN_ROOT:
 569    case TN_FILE:
 570    default:
 571       termchr = "";
 572       break;
 573    }
 574    Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 575    switch (tree->type) {
 576    case TN_FILE:
 577    case TN_NEWDIR:
 578    case TN_DIR:
 579    case TN_DIR_NLS:
 580       bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
 581       print_tree(buf, first_child(tree));
 582       break;
 583    case TN_ROOT:
 584       print_tree(path, first_child(tree));
 585       break;
 586    default:
 587       Pmsg1(000, "Unknown node type %d\n", tree->type);
 588    }
 589    print_tree(path, tree->sibling_);
 590    return;
 591 }
 592
 593 #endif