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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2002-2011 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    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
 413    if (*path == 0) {
 414       return node;
 415    }
 416    /* Check the current segment only */
 417    if ((p = first_path_separator(path)) != NULL) {
 418       len = p - path;
 419    } else {
 420       len = strlen(path);
 421    }
 422    Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
 423    foreach_child(cd, node) {
 424       Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
 425       if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
 426           && strncmp(cd->fname, path, len) == 0) {
 427          break;
 428       }
 429    }
 430    if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
 431       return NULL;
 432    }
 433    if (!p) {
 434       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 435       return cd;
 436    }
 437    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 438    /* Check the next segment if any */
 439    return tree_relcwd(p+1, root, cd);
 440 }
 441
 442
 443
 444 #ifdef BUILD_TEST_PROGRAM
 445
 446 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 447
 448 static uint32_t FileIndex = 0;
 449 /*
 450  * Simple test program for tree routines
 451  */
 452 int main(int argc, char *argv[])
 453 {
 454     TREE_ROOT *root;
 455     TREE_NODE *node;
 456     char buf[MAXPATHLEN];
 457
 458     root = new_tree();
 459     root->fname = tree_alloc(root, 1);
 460     *root->fname = 0;
 461     root->fname_len = 0;
 462
 463     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 464
 465     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 466        tree_getpath(node, buf, sizeof(buf));
 467        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 468     }
 469
 470     node = (TREE_NODE *)root;
 471     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 472     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 473     if (node) {
 474        tree_getpath(node, buf, sizeof(buf));
 475        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 476     }
 477
 478     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 479     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 480     if (node) {
 481        tree_getpath(node, buf, sizeof(buf));
 482        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 483     } else {
 484        Dmsg0(100, "testprogs not found.\n");
 485     }
 486
 487     free_tree((TREE_NODE *)root);
 488
 489     return 0;
 490 }
 491
 492 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 493 {
 494    TREE_NODE *newparent = NULL;
 495    TREE_NODE *node;
 496    struct stat statbuf;
 497    DIR *dp;
 498    struct dirent *dir;
 499    char pathbuf[MAXPATHLEN];
 500    char file[MAXPATHLEN];
 501    int type;
 502    int i;
 503
 504    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 505    dp = opendir(path);
 506    if (!dp) {
 507       return;
 508    }
 509    while ((dir = readdir(dp))) {
 510       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 511          continue;
 512       }
 513       bstrncpy(file, dir->d_name, sizeof(file));
 514       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 515       if (lstat(pathbuf, &statbuf) < 0) {
 516          berrno be;
 517          printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
 518          continue;
 519       }
 520 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 521       type = TN_FILE;
 522       if (S_ISLNK(statbuf.st_mode))
 523          type =  TN_FILE;  /* link */
 524       else if (S_ISREG(statbuf.st_mode))
 525          type = TN_FILE;
 526       else if (S_ISDIR(statbuf.st_mode)) {
 527          type = TN_DIR;
 528       } else if (S_ISCHR(statbuf.st_mode))
 529          type = TN_FILE; /* char dev */
 530       else if (S_ISBLK(statbuf.st_mode))
 531          type = TN_FILE; /* block dev */
 532       else if (S_ISFIFO(statbuf.st_mode))
 533          type = TN_FILE; /* fifo */
 534       else if (S_ISSOCK(statbuf.st_mode))
 535          type = TN_FILE; /* sock */
 536       else {
 537          type = TN_FILE;
 538          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 539       }
 540
 541       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 542       node = new_tree_node(root);
 543       node->FileIndex = ++FileIndex;
 544       parent = insert_tree_node(pathbuf, node, root, parent);
 545       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 546          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 547          FillDirectoryTree(pathbuf, root, node);
 548       }
 549    }
 550    closedir(dp);
 551 }
 552
 553 #ifndef MAXPATHLEN
 554 #define MAXPATHLEN 2000
 555 #endif
 556
 557 void print_tree(char *path, TREE_NODE *tree)
 558 {
 559    char buf[MAXPATHLEN];
 560    char *termchr;
 561
 562    if (!tree) {
 563       return;
 564    }
 565    switch (tree->type) {
 566    case TN_DIR_NLS:
 567    case TN_DIR:
 568    case TN_NEWDIR:
 569       termchr = "/";
 570       break;
 571    case TN_ROOT:
 572    case TN_FILE:
 573    default:
 574       termchr = "";
 575       break;
 576    }
 577    Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 578    switch (tree->type) {
 579    case TN_FILE:
 580    case TN_NEWDIR:
 581    case TN_DIR:
 582    case TN_DIR_NLS:
 583       bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
 584       print_tree(buf, first_child(tree));
 585       break;
 586    case TN_ROOT:
 587       print_tree(path, first_child(tree));
 588       break;
 589    default:
 590       Pmsg1(000, "Unknown node type %d\n", tree->type);
 591    }
 592    print_tree(path, tree->sibling_);
 593    return;
 594 }
 595
 596 #endif