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

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