2 Bacula® - The Network Backup Solution
4 Copyright (C) 2002-2012 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)
418 /* Check the current segment only */
419 if ((p = first_path_separator(path)) != NULL) {
424 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
425 foreach_child(cd, node) {
426 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
427 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
428 && strncmp(cd->fname, path, len) == 0) {
431 /* fnmatch has no len in call so we truncate the string */
432 save_char = path[len];
434 match = fnmatch(path, cd->fname, 0) == 0;
435 path[len] = save_char;
440 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
444 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
447 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
448 /* Check the next segment if any */
449 return tree_relcwd(p+1, root, cd);
454 #ifdef BUILD_TEST_PROGRAM
456 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
458 static uint32_t FileIndex = 0;
460 * Simple test program for tree routines
462 int main(int argc, char *argv[])
466 char buf[MAXPATHLEN];
469 root->fname = tree_alloc(root, 1);
473 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
475 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
476 tree_getpath(node, buf, sizeof(buf));
477 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
480 node = (TREE_NODE *)root;
481 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
482 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
484 tree_getpath(node, buf, sizeof(buf));
485 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
488 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
489 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
491 tree_getpath(node, buf, sizeof(buf));
492 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
494 Dmsg0(100, "testprogs not found.\n");
497 free_tree((TREE_NODE *)root);
502 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
504 TREE_NODE *newparent = NULL;
509 char pathbuf[MAXPATHLEN];
510 char file[MAXPATHLEN];
514 Dmsg1(100, "FillDirectoryTree: %s\n", path);
519 while ((dir = readdir(dp))) {
520 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
523 bstrncpy(file, dir->d_name, sizeof(file));
524 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
525 if (lstat(pathbuf, &statbuf) < 0) {
527 printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
530 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
532 if (S_ISLNK(statbuf.st_mode))
533 type = TN_FILE; /* link */
534 else if (S_ISREG(statbuf.st_mode))
536 else if (S_ISDIR(statbuf.st_mode)) {
538 } else if (S_ISCHR(statbuf.st_mode))
539 type = TN_FILE; /* char dev */
540 else if (S_ISBLK(statbuf.st_mode))
541 type = TN_FILE; /* block dev */
542 else if (S_ISFIFO(statbuf.st_mode))
543 type = TN_FILE; /* fifo */
544 else if (S_ISSOCK(statbuf.st_mode))
545 type = TN_FILE; /* sock */
548 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
551 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
552 node = new_tree_node(root);
553 node->FileIndex = ++FileIndex;
554 parent = insert_tree_node(pathbuf, node, root, parent);
555 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
556 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
557 FillDirectoryTree(pathbuf, root, node);
564 #define MAXPATHLEN 2000
567 void print_tree(char *path, TREE_NODE *tree)
569 char buf[MAXPATHLEN];
575 switch (tree->type) {
587 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
588 switch (tree->type) {
593 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
594 print_tree(buf, first_child(tree));
597 print_tree(path, first_child(tree));
600 Pmsg1(000, "Unknown node type %d\n", tree->type);
602 print_tree(path, tree->sibling_);