2 Bacula® - The Network Backup Solution
4 Copyright (C) 2002-2011 Free Software Foundation Europe e.V.
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
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.
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
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.
29 * Directory tree build/traverse routines
31 * Kern Sibbald, June MMII
37 #include "findlib/find.h"
39 #define B_PAGE_SIZE 4096
40 #define MAX_PAGES 2400
41 #define MAX_BUF_SIZE (MAX_PAGES * B_PAGE_SIZE) /* approx 10MB */
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);
49 * NOTE !!!!! we turn off Debug messages for performance reasons.
57 #define Dmsg2(n,f,a1,a2)
58 #define Dmsg3(n,f,a1,a2,a3)
61 * This subroutine gets a big buffer.
63 static void malloc_buf(TREE_ROOT *root, int size)
67 mem = (struct s_mem *)malloc(size);
68 root->total_size += size;
70 mem->next = root->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);
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.
84 TREE_ROOT *new_tree(int count)
89 if (count < 1000) { /* minimum tree size */
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)) {
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;
109 * Create a new tree node.
111 static TREE_NODE *new_tree_node(TREE_ROOT *root)
114 int size = sizeof(TREE_NODE);
115 node = (TREE_NODE *)tree_alloc(root, size);
116 memset(node, 0, size);
117 node->delta_seq = -1;
122 * This routine can be called to release the
123 * previously allocated tree node.
125 static void free_tree_node(TREE_ROOT *root)
127 int asize = BALIGN(sizeof(TREE_NODE));
128 root->mem->rem += asize;
129 root->mem->mem -= asize;
132 void tree_remove_node(TREE_ROOT *root, TREE_NODE *node)
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);
139 Dmsg0(0, "Can't release tree node\n");
144 * Allocate bytes for filename in tree structure.
145 * Keep the pointers properly aligned by allocating
146 * sizes that are aligned.
148 static char *tree_alloc(TREE_ROOT *root, int size)
151 int asize = BALIGN(size);
153 if (root->mem->rem < asize) {
155 if (root->total_size >= (MAX_BUF_SIZE / 2)) {
156 mb_size = MAX_BUF_SIZE;
158 mb_size = MAX_BUF_SIZE / 2;
160 malloc_buf(root, mb_size);
162 root->mem->rem -= asize;
163 buf = root->mem->mem;
164 root->mem->mem += asize;
169 /* This routine frees the whole tree */
170 void free_tree(TREE_ROOT *root)
172 struct s_mem *mem, *rel;
173 uint32_t freed_blocks = 0;
175 for (mem=root->mem; mem; ) {
181 if (root->cached_path) {
182 free_pool_memory(root->cached_path);
183 root->cached_path = NULL;
185 Dmsg3(100, "Total size=%u blocks=%u freed_blocks=%u\n", root->total_size, root->blocks, freed_blocks);
187 garbage_collect_memory();
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)
195 struct delta_list *elt =
196 (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
198 elt->next = node->delta_list;
200 elt->FileIndex = FileIndex;
201 node->delta_list = elt;
205 * Insert a node in the tree. This is the main subroutine
206 * called when building a tree.
209 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
210 TREE_ROOT *root, TREE_NODE *parent)
213 int path_len = strlen(path);
216 Dmsg1(100, "insert_tree_node: %s\n", path);
218 * If trailing slash on path, strip it
221 q = path + path_len - 1;
222 if (IsPathSeparator(*q)) {
223 *q = 0; /* strip trailing slash */
225 q = NULL; /* no trailing slash */
228 q = NULL; /* no trailing slash */
230 /* If no filename, strip last component of path as "filename" */
232 p = (char *)last_path_separator(path); /* separate path and filename */
234 fname = p + 1; /* set new filename */
235 *p = '\0'; /* terminate new path */
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;
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;
253 Dmsg1(100, "parent=%s\n", parent->fname);
258 parent = (TREE_NODE *)root;
261 Dmsg1(100, "No / found: %s\n", path);
264 node = search_and_insert_tree_node(fname, 0, root, parent);
265 if (q) { /* if trailing slash on entry */
266 *q = '/'; /* restore it */
268 if (p) { /* if slash in path trashed */
269 *p = '/'; /* restore full path */
275 * Ensure that all appropriate nodes for a full path exist in
278 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
280 TREE_NODE *parent, *node;
282 int type = TN_NEWDIR;
284 Dmsg1(100, "make_tree_path: %s\n", path);
286 Dmsg0(100, "make_tree_path: parent=*root*\n");
287 return (TREE_NODE *)root;
289 p = (char *)last_path_separator(path); /* get last dir component of path */
292 *p = 0; /* terminate path */
293 parent = make_tree_path(path, root);
294 *p = '/'; /* restore full name */
297 parent = (TREE_NODE *)root;
300 node = search_and_insert_tree_node(fname, type, root, parent);
304 static int node_compare(void *item1, void *item2)
306 TREE_NODE *tn1 = (TREE_NODE *)item1;
307 TREE_NODE *tn2 = (TREE_NODE *)item2;
308 if (tn1->fname[0] > tn2->fname[0]) {
310 } else if (tn1->fname[0] < tn2->fname[0]) {
313 return strcmp(tn1->fname, tn2->fname);
317 * See if the fname already exists. If not insert a new node for it.
319 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
320 TREE_ROOT *root, TREE_NODE *parent)
322 TREE_NODE *node, *found_node;
323 node = new_tree_node(root);
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;
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;
338 /* Maintain a linear chain of nodes */
343 root->last->next = node;
346 node->inserted = true; /* inserted into tree */
351 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
357 tree_getpath(node->parent, buf, buf_size);
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 /
363 if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
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.
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);
379 * Change to specified directory
381 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
383 if (path[0] == '.' && path[1] == '\0') {
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;
392 return tree_cwd(path+3, root, parent);
395 if (IsPathSeparator(path[0])) {
396 Dmsg0(100, "Doing absolute lookup.\n");
397 return tree_relcwd(path+1, root, (TREE_NODE *)root);
399 Dmsg0(100, "Doing relative lookup.\n");
400 return tree_relcwd(path, root, node);
405 * Do a relative cwd -- i.e. relative to current node rather than root node
407 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
416 /* Check the current segment only */
417 if ((p = first_path_separator(path)) != NULL) {
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) {
430 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
434 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
437 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
438 /* Check the next segment if any */
439 return tree_relcwd(p+1, root, cd);
444 #ifdef BUILD_TEST_PROGRAM
446 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
448 static uint32_t FileIndex = 0;
450 * Simple test program for tree routines
452 int main(int argc, char *argv[])
456 char buf[MAXPATHLEN];
459 root->fname = tree_alloc(root, 1);
463 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
465 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
466 tree_getpath(node, buf, sizeof(buf));
467 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
470 node = (TREE_NODE *)root;
471 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
472 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
474 tree_getpath(node, buf, sizeof(buf));
475 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
478 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
479 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
481 tree_getpath(node, buf, sizeof(buf));
482 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
484 Dmsg0(100, "testprogs not found.\n");
487 free_tree((TREE_NODE *)root);
492 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
494 TREE_NODE *newparent = NULL;
499 char pathbuf[MAXPATHLEN];
500 char file[MAXPATHLEN];
504 Dmsg1(100, "FillDirectoryTree: %s\n", path);
509 while ((dir = readdir(dp))) {
510 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
513 bstrncpy(file, dir->d_name, sizeof(file));
514 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
515 if (lstat(pathbuf, &statbuf) < 0) {
517 printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
520 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
522 if (S_ISLNK(statbuf.st_mode))
523 type = TN_FILE; /* link */
524 else if (S_ISREG(statbuf.st_mode))
526 else if (S_ISDIR(statbuf.st_mode)) {
528 } else if (S_ISCHR(statbuf.st_mode))
529 type = TN_FILE; /* char dev */
530 else if (S_ISBLK(statbuf.st_mode))
531 type = TN_FILE; /* block dev */
532 else if (S_ISFIFO(statbuf.st_mode))
533 type = TN_FILE; /* fifo */
534 else if (S_ISSOCK(statbuf.st_mode))
535 type = TN_FILE; /* sock */
538 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
541 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
542 node = new_tree_node(root);
543 node->FileIndex = ++FileIndex;
544 parent = insert_tree_node(pathbuf, node, root, parent);
545 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
546 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
547 FillDirectoryTree(pathbuf, root, node);
554 #define MAXPATHLEN 2000
557 void print_tree(char *path, TREE_NODE *tree)
559 char buf[MAXPATHLEN];
565 switch (tree->type) {
577 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
578 switch (tree->type) {
583 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
584 print_tree(buf, first_child(tree));
587 print_tree(path, first_child(tree));
590 Pmsg1(000, "Unknown node type %d\n", tree->type);
592 print_tree(path, tree->sibling_);