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