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