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 PAGE_SIZE 4096
40 #define MAX_PAGES 2400
41 #define MAX_BUF_SIZE (MAX_PAGES * 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);
190 /* Add Delta part for this node */
191 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
192 JobId_t JobId, int32_t FileIndex)
194 struct delta_list *elt =
195 (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
197 elt->next = node->delta_list;
199 elt->FileIndex = FileIndex;
200 node->delta_list = elt;
204 * Insert a node in the tree. This is the main subroutine
205 * called when building a tree.
208 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
209 TREE_ROOT *root, TREE_NODE *parent)
212 int path_len = strlen(path);
215 Dmsg1(100, "insert_tree_node: %s\n", path);
217 * If trailing slash on path, strip it
220 q = path + path_len - 1;
221 if (IsPathSeparator(*q)) {
222 *q = 0; /* strip trailing slash */
224 q = NULL; /* no trailing slash */
227 q = NULL; /* no trailing slash */
229 /* If no filename, strip last component of path as "filename" */
231 p = (char *)last_path_separator(path); /* separate path and filename */
233 fname = p + 1; /* set new filename */
234 *p = '\0'; /* terminate new path */
240 if (!parent) { /* if no parent, we need to make one */
241 Dmsg1(100, "make_tree_path for %s\n", path);
242 path_len = strlen(path); /* get new length */
243 if (path_len == root->cached_path_len &&
244 strcmp(path, root->cached_path) == 0) {
245 parent = root->cached_parent;
247 root->cached_path_len = path_len;
248 pm_strcpy(&root->cached_path, path);
249 parent = make_tree_path(path, root);
250 root->cached_parent = parent;
252 Dmsg1(100, "parent=%s\n", parent->fname);
257 parent = (TREE_NODE *)root;
260 Dmsg1(100, "No / found: %s\n", path);
263 node = search_and_insert_tree_node(fname, 0, root, parent);
264 if (q) { /* if trailing slash on entry */
265 *q = '/'; /* restore it */
267 if (p) { /* if slash in path trashed */
268 *p = '/'; /* restore full path */
274 * Ensure that all appropriate nodes for a full path exist in
277 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
279 TREE_NODE *parent, *node;
281 int type = TN_NEWDIR;
283 Dmsg1(100, "make_tree_path: %s\n", path);
285 Dmsg0(100, "make_tree_path: parent=*root*\n");
286 return (TREE_NODE *)root;
288 p = (char *)last_path_separator(path); /* get last dir component of path */
291 *p = 0; /* terminate path */
292 parent = make_tree_path(path, root);
293 *p = '/'; /* restore full name */
296 parent = (TREE_NODE *)root;
299 node = search_and_insert_tree_node(fname, type, root, parent);
303 static int node_compare(void *item1, void *item2)
305 TREE_NODE *tn1 = (TREE_NODE *)item1;
306 TREE_NODE *tn2 = (TREE_NODE *)item2;
307 if (tn1->fname[0] > tn2->fname[0]) {
309 } else if (tn1->fname[0] < tn2->fname[0]) {
312 return strcmp(tn1->fname, tn2->fname);
316 * See if the fname already exists. If not insert a new node for it.
318 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
319 TREE_ROOT *root, TREE_NODE *parent)
321 TREE_NODE *node, *found_node;
322 node = new_tree_node(root);
324 found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
325 if (found_node != node) { /* already in list */
326 free_tree_node(root); /* free node allocated above */
327 found_node->inserted = false;
330 /* It was not found, but is now inserted */
331 node->fname_len = strlen(fname);
332 node->fname = tree_alloc(root, node->fname_len + 1);
333 strcpy(node->fname, fname);
334 node->parent = parent;
337 /* Maintain a linear chain of nodes */
342 root->last->next = node;
345 node->inserted = true; /* inserted into tree */
350 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
356 tree_getpath(node->parent, buf, buf_size);
358 * Fixup for Win32. If we have a Win32 directory and
359 * there is only a / in the buffer, remove it since
360 * win32 names don't generally start with /
362 if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
365 bstrncat(buf, node->fname, buf_size);
366 /* Add a slash for all directories unless we are at the root,
367 * also add a slash to a soft linked file if it has children
368 * i.e. it is linked to a directory.
370 if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
371 (node->soft_link && tree_node_has_child(node))) {
372 bstrncat(buf, "/", buf_size);
378 * Change to specified directory
380 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
382 if (path[0] == '.' && path[1] == '\0') {
385 /* Handle relative path */
386 if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
387 TREE_NODE *parent = node->parent ? node->parent : node;
391 return tree_cwd(path+3, root, parent);
394 if (IsPathSeparator(path[0])) {
395 Dmsg0(100, "Doing absolute lookup.\n");
396 return tree_relcwd(path+1, root, (TREE_NODE *)root);
398 Dmsg0(100, "Doing relative lookup.\n");
399 return tree_relcwd(path, root, node);
404 * Do a relative cwd -- i.e. relative to current node rather than root node
406 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
415 /* Check the current segment only */
416 if ((p = first_path_separator(path)) != NULL) {
421 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
422 foreach_child(cd, node) {
423 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
424 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
425 && strncmp(cd->fname, path, len) == 0) {
429 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
433 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
436 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
437 /* Check the next segment if any */
438 return tree_relcwd(p+1, root, cd);
443 #ifdef BUILD_TEST_PROGRAM
445 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
447 static uint32_t FileIndex = 0;
449 * Simple test program for tree routines
451 int main(int argc, char *argv[])
455 char buf[MAXPATHLEN];
458 root->fname = tree_alloc(root, 1);
462 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
464 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
465 tree_getpath(node, buf, sizeof(buf));
466 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
469 node = (TREE_NODE *)root;
470 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
471 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
473 tree_getpath(node, buf, sizeof(buf));
474 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
477 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
478 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
480 tree_getpath(node, buf, sizeof(buf));
481 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
483 Dmsg0(100, "testprogs not found.\n");
486 free_tree((TREE_NODE *)root);
491 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
493 TREE_NODE *newparent = NULL;
498 char pathbuf[MAXPATHLEN];
499 char file[MAXPATHLEN];
503 Dmsg1(100, "FillDirectoryTree: %s\n", path);
508 while ((dir = readdir(dp))) {
509 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
512 bstrncpy(file, dir->d_name, sizeof(file));
513 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
514 if (lstat(pathbuf, &statbuf) < 0) {
516 printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
519 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
521 if (S_ISLNK(statbuf.st_mode))
522 type = TN_FILE; /* link */
523 else if (S_ISREG(statbuf.st_mode))
525 else if (S_ISDIR(statbuf.st_mode)) {
527 } else if (S_ISCHR(statbuf.st_mode))
528 type = TN_FILE; /* char dev */
529 else if (S_ISBLK(statbuf.st_mode))
530 type = TN_FILE; /* block dev */
531 else if (S_ISFIFO(statbuf.st_mode))
532 type = TN_FILE; /* fifo */
533 else if (S_ISSOCK(statbuf.st_mode))
534 type = TN_FILE; /* sock */
537 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
540 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
541 node = new_tree_node(root);
542 node->FileIndex = ++FileIndex;
543 parent = insert_tree_node(pathbuf, node, root, parent);
544 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
545 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
546 FillDirectoryTree(pathbuf, root, node);
553 #define MAXPATHLEN 2000
556 void print_tree(char *path, TREE_NODE *tree)
558 char buf[MAXPATHLEN];
564 switch (tree->type) {
576 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
577 switch (tree->type) {
582 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
583 print_tree(buf, first_child(tree));
586 print_tree(path, first_child(tree));
589 Pmsg1(000, "Unknown node type %d\n", tree->type);
591 print_tree(path, tree->sibling_);