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