2 Bacula® - The Network Backup Solution
4 Copyright (C) 2002-2008 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;
174 for (mem=root->mem; mem; ) {
179 if (root->cached_path) {
180 free_pool_memory(root->cached_path);
181 root->cached_path = NULL;
183 Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
188 /* Add Delta part for this node */
189 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
190 JobId_t JobId, int32_t FileIndex)
192 struct delta_list *elt =
193 (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
195 elt->next = node->delta_list;
197 elt->FileIndex = FileIndex;
198 node->delta_list = elt;
202 * Insert a node in the tree. This is the main subroutine
203 * called when building a tree.
206 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
207 TREE_ROOT *root, TREE_NODE *parent)
210 int path_len = strlen(path);
213 Dmsg1(100, "insert_tree_node: %s\n", path);
215 * If trailing slash on path, strip it
218 q = path + path_len - 1;
219 if (IsPathSeparator(*q)) {
220 *q = 0; /* strip trailing slash */
222 q = NULL; /* no trailing slash */
225 q = NULL; /* no trailing slash */
227 /* If no filename, strip last component of path as "filename" */
229 p = (char *)last_path_separator(path); /* separate path and filename */
231 fname = p + 1; /* set new filename */
232 *p = '\0'; /* terminate new path */
238 if (!parent) { /* if no parent, we need to make one */
239 Dmsg1(100, "make_tree_path for %s\n", path);
240 path_len = strlen(path); /* get new length */
241 if (path_len == root->cached_path_len &&
242 strcmp(path, root->cached_path) == 0) {
243 parent = root->cached_parent;
245 root->cached_path_len = path_len;
246 pm_strcpy(&root->cached_path, path);
247 parent = make_tree_path(path, root);
248 root->cached_parent = parent;
250 Dmsg1(100, "parent=%s\n", parent->fname);
255 parent = (TREE_NODE *)root;
258 Dmsg1(100, "No / found: %s\n", path);
261 node = search_and_insert_tree_node(fname, 0, root, parent);
262 if (q) { /* if trailing slash on entry */
263 *q = '/'; /* restore it */
265 if (p) { /* if slash in path trashed */
266 *p = '/'; /* restore full path */
272 * Ensure that all appropriate nodes for a full path exist in
275 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
277 TREE_NODE *parent, *node;
279 int type = TN_NEWDIR;
281 Dmsg1(100, "make_tree_path: %s\n", path);
283 Dmsg0(100, "make_tree_path: parent=*root*\n");
284 return (TREE_NODE *)root;
286 p = (char *)last_path_separator(path); /* get last dir component of path */
289 *p = 0; /* terminate path */
290 parent = make_tree_path(path, root);
291 *p = '/'; /* restore full name */
294 parent = (TREE_NODE *)root;
297 node = search_and_insert_tree_node(fname, type, root, parent);
301 static int node_compare(void *item1, void *item2)
303 TREE_NODE *tn1 = (TREE_NODE *)item1;
304 TREE_NODE *tn2 = (TREE_NODE *)item2;
305 if (tn1->fname[0] > tn2->fname[0]) {
307 } else if (tn1->fname[0] < tn2->fname[0]) {
310 return strcmp(tn1->fname, tn2->fname);
314 * See if the fname already exists. If not insert a new node for it.
316 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
317 TREE_ROOT *root, TREE_NODE *parent)
319 TREE_NODE *node, *found_node;
320 node = new_tree_node(root);
322 found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
323 if (found_node != node) { /* already in list */
324 free_tree_node(root); /* free node allocated above */
325 found_node->inserted = false;
328 /* It was not found, but is now inserted */
329 node->fname_len = strlen(fname);
330 node->fname = tree_alloc(root, node->fname_len + 1);
331 strcpy(node->fname, fname);
332 node->parent = parent;
335 /* Maintain a linear chain of nodes */
340 root->last->next = node;
343 node->inserted = true; /* inserted into tree */
348 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
354 tree_getpath(node->parent, buf, buf_size);
356 * Fixup for Win32. If we have a Win32 directory and
357 * there is only a / in the buffer, remove it since
358 * win32 names don't generally start with /
360 if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
363 bstrncat(buf, node->fname, buf_size);
364 /* Add a slash for all directories unless we are at the root,
365 * also add a slash to a soft linked file if it has children
366 * i.e. it is linked to a directory.
368 if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
369 (node->soft_link && tree_node_has_child(node))) {
370 bstrncat(buf, "/", buf_size);
376 * Change to specified directory
378 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
380 if (path[0] == '.' && path[1] == '\0') {
383 /* Handle relative path */
384 if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
385 TREE_NODE *parent = node->parent ? node->parent : node;
389 return tree_cwd(path+3, root, parent);
392 if (IsPathSeparator(path[0])) {
393 Dmsg0(100, "Doing absolute lookup.\n");
394 return tree_relcwd(path+1, root, (TREE_NODE *)root);
396 Dmsg0(100, "Doing relative lookup.\n");
397 return tree_relcwd(path, root, node);
402 * Do a relative cwd -- i.e. relative to current node rather than root node
404 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
413 /* Check the current segment only */
414 if ((p = first_path_separator(path)) != NULL) {
419 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
420 foreach_child(cd, node) {
421 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
422 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
423 && strncmp(cd->fname, path, len) == 0) {
427 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
431 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
434 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
435 /* Check the next segment if any */
436 return tree_relcwd(p+1, root, cd);
441 #ifdef BUILD_TEST_PROGRAM
443 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
445 static uint32_t FileIndex = 0;
447 * Simple test program for tree routines
449 int main(int argc, char *argv[])
453 char buf[MAXPATHLEN];
456 root->fname = tree_alloc(root, 1);
460 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
462 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
463 tree_getpath(node, buf, sizeof(buf));
464 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
467 node = (TREE_NODE *)root;
468 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
469 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
471 tree_getpath(node, buf, sizeof(buf));
472 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
475 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
476 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
478 tree_getpath(node, buf, sizeof(buf));
479 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
481 Dmsg0(100, "testprogs not found.\n");
484 free_tree((TREE_NODE *)root);
489 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
491 TREE_NODE *newparent = NULL;
496 char pathbuf[MAXPATHLEN];
497 char file[MAXPATHLEN];
501 Dmsg1(100, "FillDirectoryTree: %s\n", path);
506 while ((dir = readdir(dp))) {
507 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
510 bstrncpy(file, dir->d_name, sizeof(file));
511 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
512 if (lstat(pathbuf, &statbuf) < 0) {
514 printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
517 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
519 if (S_ISLNK(statbuf.st_mode))
520 type = TN_FILE; /* link */
521 else if (S_ISREG(statbuf.st_mode))
523 else if (S_ISDIR(statbuf.st_mode)) {
525 } else if (S_ISCHR(statbuf.st_mode))
526 type = TN_FILE; /* char dev */
527 else if (S_ISBLK(statbuf.st_mode))
528 type = TN_FILE; /* block dev */
529 else if (S_ISFIFO(statbuf.st_mode))
530 type = TN_FILE; /* fifo */
531 else if (S_ISSOCK(statbuf.st_mode))
532 type = TN_FILE; /* sock */
535 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
538 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
539 node = new_tree_node(root);
540 node->FileIndex = ++FileIndex;
541 parent = insert_tree_node(pathbuf, node, root, parent);
542 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
543 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
544 FillDirectoryTree(pathbuf, root, node);
551 #define MAXPATHLEN 2000
554 void print_tree(char *path, TREE_NODE *tree)
556 char buf[MAXPATHLEN];
562 switch (tree->type) {
574 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
575 switch (tree->type) {
580 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
581 print_tree(buf, first_child(tree));
584 print_tree(path, first_child(tree));
587 Pmsg1(000, "Unknown node type %d\n", tree->type);
589 print_tree(path, tree->sibling_);