X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=bacula%2Fsrc%2Flib%2Ftree.c;h=3cae5bbf6733bd7cebeba48a84f14b5807931d89;hb=c6064c3a1bf0db4047fce7c4a291eb108c5386a2;hp=e6ef465eb199b273711383aa951be35aa7923486;hpb=b687b31902db27c95b1623809e683899f31c85fe;p=bacula%2Fbacula diff --git a/bacula/src/lib/tree.c b/bacula/src/lib/tree.c old mode 100755 new mode 100644 index e6ef465eb1..3cae5bbf67 --- a/bacula/src/lib/tree.c +++ b/bacula/src/lib/tree.c @@ -1,37 +1,39 @@ /* - * Directory tree build/traverse routines - * - * Kern Sibbald, June MMII - * -*/ -/* - Copyright (C) 2002-2004 Kern Sibbald and John Walker + Bacula(R) - The Network Backup Solution - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License as - published by the Free Software Foundation; either version 2 of - the License, or (at your option) any later version. + Copyright (C) 2000-2017 Kern Sibbald - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. + The original author of Bacula is Kern Sibbald, with contributions + from many others, a complete list can be found in the file AUTHORS. - You should have received a copy of the GNU General Public - License along with this program; if not, write to the Free - Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, - MA 02111-1307, USA. + You may use this file and others of this release according to the + license defined in the LICENSE file, which includes the Affero General + Public License, v3.0 ("AGPLv3") and some additional permissions and + terms pursuant to its AGPLv3 Section 7. - */ + This notice must be preserved when any source code is + conveyed and/or propagated. + + Bacula(R) is a registered trademark of Kern Sibbald. +*/ +/* + * Directory tree build/traverse routines + * + * Kern Sibbald, June MMII + * +*/ #include "bacula.h" #include "findlib/find.h" - + +#define B_PAGE_SIZE 4096 +#define MAX_PAGES 2400 +#define MAX_BUF_SIZE (MAX_PAGES * B_PAGE_SIZE) /* approx 10MB */ /* Forward referenced subroutines */ -static TREE_NODE *search_and_insert_tree_node(char *fname, int type, - TREE_ROOT *root, TREE_NODE *parent); +static TREE_NODE *search_and_insert_tree_node(char *fname, int type, + TREE_ROOT *root, TREE_NODE *parent); static char *tree_alloc(TREE_ROOT *root, int size); /* @@ -75,15 +77,15 @@ TREE_ROOT *new_tree(int count) TREE_ROOT *root; uint32_t size; - if (count < 1000) { /* minimum tree size */ + if (count < 1000) { /* minimum tree size */ count = 1000; } root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT)); memset(root, 0, sizeof(TREE_ROOT)); /* Assume filename + node = 40 characters average length */ size = count * (BALIGN(sizeof(TREE_NODE)) + 40); - if (count > 1000000 || size > 10000000) { - size = 10000000; + if (count > 1000000 || size > (MAX_BUF_SIZE / 2)) { + size = MAX_BUF_SIZE; } Dmsg2(400, "count=%d size=%d\n", count, size); malloc_buf(root, size); @@ -91,10 +93,13 @@ TREE_ROOT *new_tree(int count) root->cached_path = get_pool_memory(PM_FNAME); root->type = TN_ROOT; root->fname = ""; + root->can_access = 1; + HL_ENTRY* entry = NULL; + root->hardlinks.init(entry, &entry->link, 0); return root; } -/* +/* * Create a new tree node. */ static TREE_NODE *new_tree_node(TREE_ROOT *root) @@ -103,12 +108,13 @@ static TREE_NODE *new_tree_node(TREE_ROOT *root) int size = sizeof(TREE_NODE); node = (TREE_NODE *)tree_alloc(root, size); memset(node, 0, size); + node->delta_seq = -1; + node->can_access = 1; return node; } -#ifdef USE_DLIST /* - * This routine can be called to release the + * This routine can be called to release the * previously allocated tree node. */ static void free_tree_node(TREE_ROOT *root) @@ -117,9 +123,17 @@ static void free_tree_node(TREE_ROOT *root) root->mem->rem += asize; root->mem->mem -= asize; } -#endif - +void tree_remove_node(TREE_ROOT *root, TREE_NODE *node) +{ + int asize = BALIGN(sizeof(TREE_NODE)); + node->parent->child.remove(node); + if ((root->mem->mem - asize) == (char *)node) { + free_tree_node(root); + } else { + Dmsg0(0, "Can't release tree node\n"); + } +} /* * Allocate bytes for filename in tree structure. @@ -133,10 +147,10 @@ static char *tree_alloc(TREE_ROOT *root, int size) if (root->mem->rem < asize) { uint32_t mb_size; - if (root->total_size >= 1000000) { - mb_size = 1000000; + if (root->total_size >= (MAX_BUF_SIZE / 2)) { + mb_size = MAX_BUF_SIZE; } else { - mb_size = 100000; + mb_size = MAX_BUF_SIZE / 2; } malloc_buf(root, mb_size); } @@ -151,29 +165,45 @@ static char *tree_alloc(TREE_ROOT *root, int size) void free_tree(TREE_ROOT *root) { struct s_mem *mem, *rel; + uint32_t freed_blocks = 0; + root->hardlinks.destroy(); for (mem=root->mem; mem; ) { rel = mem; mem = mem->next; free(rel); + freed_blocks++; } if (root->cached_path) { free_pool_memory(root->cached_path); root->cached_path = NULL; } - Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks); + Dmsg3(100, "Total size=%u blocks=%u freed_blocks=%u\n", root->total_size, root->blocks, freed_blocks); free(root); + garbage_collect_memory(); return; } +/* Add Delta part for this node */ +void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node, + JobId_t JobId, int32_t FileIndex) +{ + struct delta_list *elt = + (struct delta_list*) tree_alloc(root, sizeof(struct delta_list)); -/* + elt->next = node->delta_list; + elt->JobId = JobId; + elt->FileIndex = FileIndex; + node->delta_list = elt; +} + +/* * Insert a node in the tree. This is the main subroutine * called when building a tree. * */ TREE_NODE *insert_tree_node(char *path, char *fname, int type, - TREE_ROOT *root, TREE_NODE *parent) + TREE_ROOT *root, TREE_NODE *parent) { char *p, *q; int path_len = strlen(path); @@ -185,53 +215,53 @@ TREE_NODE *insert_tree_node(char *path, char *fname, int type, */ if (path_len > 0) { q = path + path_len - 1; - if (*q == '/') { - *q = 0; /* strip trailing slash */ + if (IsPathSeparator(*q)) { + *q = 0; /* strip trailing slash */ } else { - q = NULL; /* no trailing slash */ + q = NULL; /* no trailing slash */ } } else { - q = NULL; /* no trailing slash */ + q = NULL; /* no trailing slash */ } /* If no filename, strip last component of path as "filename" */ if (*fname == 0) { - p = strrchr(path, '/'); /* separate path and filename */ + p = (char *)last_path_separator(path); /* separate path and filename */ if (p) { - fname = p + 1; /* set new filename */ - *p = 0; /* terminate new path */ + fname = p + 1; /* set new filename */ + *p = '\0'; /* terminate new path */ } } else { p = NULL; } if (*fname) { - if (!parent) { /* if no parent, we need to make one */ + if (!parent) { /* if no parent, we need to make one */ Dmsg1(100, "make_tree_path for %s\n", path); - path_len = strlen(path); /* get new length */ - if (path_len == root->cached_path_len && - strcmp(path, root->cached_path) == 0) { - parent = root->cached_parent; - } else { - root->cached_path_len = path_len; - pm_strcpy(&root->cached_path, path); - parent = make_tree_path(path, root); - root->cached_parent = parent; - } + path_len = strlen(path); /* get new length */ + if (path_len == root->cached_path_len && + strcmp(path, root->cached_path) == 0) { + parent = root->cached_parent; + } else { + root->cached_path_len = path_len; + pm_strcpy(&root->cached_path, path); + parent = make_tree_path(path, root); + root->cached_parent = parent; + } Dmsg1(100, "parent=%s\n", parent->fname); } } else { fname = path; if (!parent) { - parent = (TREE_NODE *)root; - type = TN_DIR_NLS; + parent = (TREE_NODE *)root; + type = TN_DIR_NLS; } Dmsg1(100, "No / found: %s\n", path); } node = search_and_insert_tree_node(fname, 0, root, parent); - if (q) { /* if trailing slash on entry */ + if (q) { /* if trailing slash on entry */ *q = '/'; /* restore it */ } - if (p) { /* if slash in path trashed */ + if (p) { /* if slash in path trashed */ *p = '/'; /* restore full path */ } return node; @@ -252,10 +282,10 @@ TREE_NODE *make_tree_path(char *path, TREE_ROOT *root) Dmsg0(100, "make_tree_path: parent=*root*\n"); return (TREE_NODE *)root; } - p = strrchr(path, '/'); /* get last dir component of path */ + p = (char *)last_path_separator(path); /* get last dir component of path */ if (p) { fname = p + 1; - *p = 0; /* terminate path */ + *p = 0; /* terminate path */ parent = make_tree_path(path, root); *p = '/'; /* restore full name */ } else { @@ -265,9 +295,8 @@ TREE_NODE *make_tree_path(char *path, TREE_ROOT *root) } node = search_and_insert_tree_node(fname, type, root, parent); return node; -} +} -#ifdef USE_DLIST static int node_compare(void *item1, void *item2) { TREE_NODE *tn1 = (TREE_NODE *)item1; @@ -279,21 +308,19 @@ static int node_compare(void *item1, void *item2) } return strcmp(tn1->fname, tn2->fname); } -#endif /* * See if the fname already exists. If not insert a new node for it. */ -static TREE_NODE *search_and_insert_tree_node(char *fname, int type, - TREE_ROOT *root, TREE_NODE *parent) +static TREE_NODE *search_and_insert_tree_node(char *fname, int type, + TREE_ROOT *root, TREE_NODE *parent) { -#ifdef USE_DLIST TREE_NODE *node, *found_node; node = new_tree_node(root); node->fname = fname; - found_node = (TREE_NODE *)parent->child.unique_binary_insert(node, node_compare); - if (found_node != node) { /* already in list */ - free_tree_node(root); /* free node allocated above */ + found_node = (TREE_NODE *)parent->child.insert(node, node_compare); + if (found_node != node) { /* already in list */ + free_tree_node(root); /* free node allocated above */ found_node->inserted = false; return found_node; } @@ -303,7 +330,6 @@ static TREE_NODE *search_and_insert_tree_node(char *fname, int type, strcpy(node->fname, fname); node->parent = parent; node->type = type; - /* Maintain a linear chain of nodes */ if (!root->first) { root->first = node; @@ -312,85 +338,11 @@ static TREE_NODE *search_and_insert_tree_node(char *fname, int type, root->last->next = node; root->last = node; } - node->inserted = true; /* inserted into tree */ + node->inserted = true; /* inserted into tree */ return node; -#else - TREE_NODE *sibling, *last_sibling = NULL; - uint16_t fname_len = strlen(fname); - int cmp; - - /* Is it already a sibling? */ - foreach_child(sibling, parent) { - Dmsg2(000, "sibling->fname=%s fname=%s\n", sibling->fname, fname); - if (fname[0] > sibling->fname[0] || (cmp=strcmp(fname, sibling->fname)) > 0) { - last_sibling = sibling; - continue; - } - if (cmp < 0) { - /* Insert before current sibling */ - if (!node) { - node = new_tree_node(root); - } - node->sibling_ = sibling; - if (sibling == first_child(parent)) { /* if sibling was at head of list */ - parent->child_ = NULL; /* force parent to be updated below */ - } - Dmsg2(000, "insert before sibling->fname=%s fname=%s\n", sibling->fname, fname); - break; - } - /* Found it */ - sibling->inserted = false; /* already in tree */ - return sibling; - } - - - /* - * At this point, the fname is not found. We must add it - */ - if (!node) { - node = new_tree_node(root); - } - Dmsg1(000, "append_tree_node: %s\n", fname); - node->fname_len = fname_len; - node->fname = tree_alloc(root, node->fname_len + 1); - strcpy(node->fname, fname); - node->parent = parent; - node->type = type; - if (!tree_node_has_child(parent)) { - parent->child_ = node; - } else { - last_sibling->sibling_ = node; - } - - /* Maintain a linear chain of nodes */ - if (!root->first) { - root->first = node; - root->last = node; - } else { - root->last->next = node; - root->last = node; - } - node->inserted = true; /* inserted into tree */ - return node; -#endif } -#ifdef SLOW_WAY -/* Moved to tree.h to eliminate subroutine call */ -TREE_NODE *first_tree_node(TREE_ROOT *root) -{ - return root->first; -} - -TREE_NODE *next_tree_node(TREE_NODE *node) -{ - return node->next; -} -#endif - - - int tree_getpath(TREE_NODE *node, char *buf, int buf_size) { if (!node) { @@ -398,42 +350,44 @@ int tree_getpath(TREE_NODE *node, char *buf, int buf_size) return 1; } tree_getpath(node->parent, buf, buf_size); - /* - * Fixup for Win32. If we have a Win32 directory and - * there is only a / in the buffer, remove it since + /* + * Fixup for Win32. If we have a Win32 directory and + * there is only a / in the buffer, remove it since * win32 names don't generally start with / */ - if (node->type == TN_DIR_NLS && buf[0] == '/' && buf[1] == 0) { - buf[0] = 0; + if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') { + buf[0] = '\0'; } bstrncat(buf, node->fname, buf_size); /* Add a slash for all directories unless we are at the root, * also add a slash to a soft linked file if it has children * i.e. it is linked to a directory. */ - if ((node->type != TN_FILE && !(buf[0] == '/' && buf[1] == 0)) || + if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) || (node->soft_link && tree_node_has_child(node))) { bstrncat(buf, "/", buf_size); } return 1; } -/* +/* * Change to specified directory */ TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node) { - if (strcmp(path, ".") == 0) { + if (path[0] == '.' && path[1] == '\0') { return node; } - if (strcmp(path, "..") == 0) { - if (node->parent) { - return node->parent; + /* Handle relative path */ + if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) { + TREE_NODE *parent = node->parent ? node->parent : node; + if (path[2] == 0) { + return parent; } else { - return node; + return tree_cwd(path+3, root, parent); } } - if (path[0] == '/') { + if (IsPathSeparator(path[0])) { Dmsg0(100, "Doing absolute lookup.\n"); return tree_relcwd(path+1, root, (TREE_NODE *)root); } @@ -450,13 +404,14 @@ TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node) char *p; int len; TREE_NODE *cd; + char save_char; + int match; if (*path == 0) { return node; } /* Check the current segment only */ - p = strchr(path, '/'); - if (p) { + if ((p = first_path_separator(path)) != NULL) { len = p - path; } else { len = strlen(path); @@ -464,14 +419,25 @@ TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node) Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path); foreach_child(cd, node) { Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname); - if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname) - && strncmp(cd->fname, path, len) == 0) { - break; + if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname) + && strncmp(cd->fname, path, len) == 0) { + break; + } + /* fnmatch has no len in call so we truncate the string */ + save_char = path[len]; + path[len] = 0; + match = fnmatch(path, cd->fname, 0) == 0; + path[len] = save_char; + if (match) { + break; } } if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) { return NULL; } + if (!cd->can_access) { /* Will display permission denied */ + return cd; + } if (!p) { Dmsg0(100, "tree_relcwd: no more to lookup. found.\n"); return cd; @@ -542,7 +508,7 @@ void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent) char file[MAXPATHLEN]; int type; int i; - + Dmsg1(100, "FillDirectoryTree: %s\n", path); dp = opendir(path); if (!dp) { @@ -550,32 +516,33 @@ void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent) } while ((dir = readdir(dp))) { if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) { - continue; + continue; } bstrncpy(file, dir->d_name, sizeof(file)); snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file); if (lstat(pathbuf, &statbuf) < 0) { - printf("lstat() failed. ERR=%s\n", strerror(errno)); - continue; + berrno be; + printf("lstat() failed. ERR=%s\n", be.bstrerror(errno)); + continue; } // printf("got file=%s, pathbuf=%s\n", file, pathbuf); type = TN_FILE; if (S_ISLNK(statbuf.st_mode)) - type = TN_FILE; /* link */ + type = TN_FILE; /* link */ else if (S_ISREG(statbuf.st_mode)) - type = TN_FILE; + type = TN_FILE; else if (S_ISDIR(statbuf.st_mode)) { - type = TN_DIR; + type = TN_DIR; } else if (S_ISCHR(statbuf.st_mode)) - type = TN_FILE; /* char dev */ + type = TN_FILE; /* char dev */ else if (S_ISBLK(statbuf.st_mode)) - type = TN_FILE; /* block dev */ + type = TN_FILE; /* block dev */ else if (S_ISFIFO(statbuf.st_mode)) - type = TN_FILE; /* fifo */ + type = TN_FILE; /* fifo */ else if (S_ISSOCK(statbuf.st_mode)) - type = TN_FILE; /* sock */ + type = TN_FILE; /* sock */ else { - type = TN_FILE; + type = TN_FILE; printf("Unknown file type: 0x%x\n", statbuf.st_mode); } @@ -585,7 +552,7 @@ void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent) parent = insert_tree_node(pathbuf, node, root, parent); if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) { Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file); - FillDirectoryTree(pathbuf, root, node); + FillDirectoryTree(pathbuf, root, node); } } closedir(dp); @@ -606,7 +573,7 @@ void print_tree(char *path, TREE_NODE *tree) switch (tree->type) { case TN_DIR_NLS: case TN_DIR: - case TN_NEWDIR: + case TN_NEWDIR: termchr = "/"; break; case TN_ROOT: @@ -615,7 +582,7 @@ void print_tree(char *path, TREE_NODE *tree) termchr = ""; break; } - Dmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr); + Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr); switch (tree->type) { case TN_FILE: case TN_NEWDIR: