2 Bacula(R) - The Network Backup Solution
4 Copyright (C) 2000-2017 Kern Sibbald
6 The original author of Bacula is Kern Sibbald, with contributions
7 from many others, a complete list can be found in the file AUTHORS.
9 You may use this file and others of this release according to the
10 license defined in the LICENSE file, which includes the Affero General
11 Public License, v3.0 ("AGPLv3") and some additional permissions and
12 terms pursuant to its AGPLv3 Section 7.
14 This notice must be preserved when any source code is
15 conveyed and/or propagated.
17 Bacula(R) is a registered trademark of Kern Sibbald.
20 * Directory tree build/traverse routines
22 * Kern Sibbald, June MMII
28 #include "findlib/find.h"
30 #define B_PAGE_SIZE 4096
31 #define MAX_PAGES 2400
32 #define MAX_BUF_SIZE (MAX_PAGES * B_PAGE_SIZE) /* approx 10MB */
34 /* Forward referenced subroutines */
35 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
36 TREE_ROOT *root, TREE_NODE *parent);
37 static char *tree_alloc(TREE_ROOT *root, int size);
40 * NOTE !!!!! we turn off Debug messages for performance reasons.
48 #define Dmsg2(n,f,a1,a2)
49 #define Dmsg3(n,f,a1,a2,a3)
52 * This subroutine gets a big buffer.
54 static void malloc_buf(TREE_ROOT *root, int size)
58 mem = (struct s_mem *)malloc(size);
59 root->total_size += size;
61 mem->next = root->mem;
63 mem->mem = mem->first;
64 mem->rem = (char *)mem + size - mem->mem;
65 Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
70 * Note, we allocate a big buffer in the tree root
71 * from which we allocate nodes. This runs more
72 * than 100 times as fast as directly using malloc()
73 * for each of the nodes.
75 TREE_ROOT *new_tree(int count)
80 if (count < 1000) { /* minimum tree size */
83 root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
84 memset(root, 0, sizeof(TREE_ROOT));
85 /* Assume filename + node = 40 characters average length */
86 size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
87 if (count > 1000000 || size > (MAX_BUF_SIZE / 2)) {
90 Dmsg2(400, "count=%d size=%d\n", count, size);
91 malloc_buf(root, size);
92 root->cached_path_len = -1;
93 root->cached_path = get_pool_memory(PM_FNAME);
97 HL_ENTRY* entry = NULL;
98 root->hardlinks.init(entry, &entry->link, 0);
103 * Create a new tree node.
105 static TREE_NODE *new_tree_node(TREE_ROOT *root)
108 int size = sizeof(TREE_NODE);
109 node = (TREE_NODE *)tree_alloc(root, size);
110 memset(node, 0, size);
111 node->delta_seq = -1;
112 node->can_access = 1;
117 * This routine can be called to release the
118 * previously allocated tree node.
120 static void free_tree_node(TREE_ROOT *root)
122 int asize = BALIGN(sizeof(TREE_NODE));
123 root->mem->rem += asize;
124 root->mem->mem -= asize;
127 void tree_remove_node(TREE_ROOT *root, TREE_NODE *node)
129 int asize = BALIGN(sizeof(TREE_NODE));
130 node->parent->child.remove(node);
131 if ((root->mem->mem - asize) == (char *)node) {
132 free_tree_node(root);
134 Dmsg0(0, "Can't release tree node\n");
139 * Allocate bytes for filename in tree structure.
140 * Keep the pointers properly aligned by allocating
141 * sizes that are aligned.
143 static char *tree_alloc(TREE_ROOT *root, int size)
146 int asize = BALIGN(size);
148 if (root->mem->rem < asize) {
150 if (root->total_size >= (MAX_BUF_SIZE / 2)) {
151 mb_size = MAX_BUF_SIZE;
153 mb_size = MAX_BUF_SIZE / 2;
155 malloc_buf(root, mb_size);
157 root->mem->rem -= asize;
158 buf = root->mem->mem;
159 root->mem->mem += asize;
164 /* This routine frees the whole tree */
165 void free_tree(TREE_ROOT *root)
167 struct s_mem *mem, *rel;
168 uint32_t freed_blocks = 0;
170 root->hardlinks.destroy();
171 for (mem=root->mem; mem; ) {
177 if (root->cached_path) {
178 free_pool_memory(root->cached_path);
179 root->cached_path = NULL;
181 Dmsg3(100, "Total size=%u blocks=%u freed_blocks=%u\n", root->total_size, root->blocks, freed_blocks);
183 garbage_collect_memory();
187 /* Add Delta part for this node */
188 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
189 JobId_t JobId, int32_t FileIndex)
191 struct delta_list *elt =
192 (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
194 elt->next = node->delta_list;
196 elt->FileIndex = FileIndex;
197 node->delta_list = elt;
201 * Insert a node in the tree. This is the main subroutine
202 * called when building a tree.
205 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
206 TREE_ROOT *root, TREE_NODE *parent)
209 int path_len = strlen(path);
212 Dmsg1(100, "insert_tree_node: %s\n", path);
214 * If trailing slash on path, strip it
217 q = path + path_len - 1;
218 if (IsPathSeparator(*q)) {
219 *q = 0; /* strip trailing slash */
221 q = NULL; /* no trailing slash */
224 q = NULL; /* no trailing slash */
226 /* If no filename, strip last component of path as "filename" */
228 p = (char *)last_path_separator(path); /* separate path and filename */
230 fname = p + 1; /* set new filename */
231 *p = '\0'; /* terminate new path */
237 if (!parent) { /* if no parent, we need to make one */
238 Dmsg1(100, "make_tree_path for %s\n", path);
239 path_len = strlen(path); /* get new length */
240 if (path_len == root->cached_path_len &&
241 strcmp(path, root->cached_path) == 0) {
242 parent = root->cached_parent;
244 root->cached_path_len = path_len;
245 pm_strcpy(&root->cached_path, path);
246 parent = make_tree_path(path, root);
247 root->cached_parent = parent;
249 Dmsg1(100, "parent=%s\n", parent->fname);
254 parent = (TREE_NODE *)root;
257 Dmsg1(100, "No / found: %s\n", path);
260 node = search_and_insert_tree_node(fname, 0, root, parent);
261 if (q) { /* if trailing slash on entry */
262 *q = '/'; /* restore it */
264 if (p) { /* if slash in path trashed */
265 *p = '/'; /* restore full path */
271 * Ensure that all appropriate nodes for a full path exist in
274 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
276 TREE_NODE *parent, *node;
278 int type = TN_NEWDIR;
280 Dmsg1(100, "make_tree_path: %s\n", path);
282 Dmsg0(100, "make_tree_path: parent=*root*\n");
283 return (TREE_NODE *)root;
285 p = (char *)last_path_separator(path); /* get last dir component of path */
288 *p = 0; /* terminate path */
289 parent = make_tree_path(path, root);
290 *p = '/'; /* restore full name */
293 parent = (TREE_NODE *)root;
296 node = search_and_insert_tree_node(fname, type, root, parent);
300 static int node_compare(void *item1, void *item2)
302 TREE_NODE *tn1 = (TREE_NODE *)item1;
303 TREE_NODE *tn2 = (TREE_NODE *)item2;
304 if (tn1->fname[0] > tn2->fname[0]) {
306 } else if (tn1->fname[0] < tn2->fname[0]) {
309 return strcmp(tn1->fname, tn2->fname);
313 * See if the fname already exists. If not insert a new node for it.
315 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
316 TREE_ROOT *root, TREE_NODE *parent)
318 TREE_NODE *node, *found_node;
319 node = new_tree_node(root);
321 found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
322 if (found_node != node) { /* already in list */
323 free_tree_node(root); /* free node allocated above */
324 found_node->inserted = false;
327 /* It was not found, but is now inserted */
328 node->fname_len = strlen(fname);
329 node->fname = tree_alloc(root, node->fname_len + 1);
330 strcpy(node->fname, fname);
331 node->parent = parent;
333 /* Maintain a linear chain of nodes */
338 root->last->next = node;
341 node->inserted = true; /* inserted into tree */
346 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
352 tree_getpath(node->parent, buf, buf_size);
354 * Fixup for Win32. If we have a Win32 directory and
355 * there is only a / in the buffer, remove it since
356 * win32 names don't generally start with /
358 if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
361 bstrncat(buf, node->fname, buf_size);
362 /* Add a slash for all directories unless we are at the root,
363 * also add a slash to a soft linked file if it has children
364 * i.e. it is linked to a directory.
366 if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
367 (node->soft_link && tree_node_has_child(node))) {
368 bstrncat(buf, "/", buf_size);
374 * Change to specified directory
376 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
378 if (path[0] == '.' && path[1] == '\0') {
381 /* Handle relative path */
382 if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
383 TREE_NODE *parent = node->parent ? node->parent : node;
387 return tree_cwd(path+3, root, parent);
390 if (IsPathSeparator(path[0])) {
391 Dmsg0(100, "Doing absolute lookup.\n");
392 return tree_relcwd(path+1, root, (TREE_NODE *)root);
394 Dmsg0(100, "Doing relative lookup.\n");
395 return tree_relcwd(path, root, node);
400 * Do a relative cwd -- i.e. relative to current node rather than root node
402 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) {
426 /* fnmatch has no len in call so we truncate the string */
427 save_char = path[len];
429 match = fnmatch(path, cd->fname, 0) == 0;
430 path[len] = save_char;
435 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
438 if (!cd->can_access) { /* Will display permission denied */
442 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
445 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
446 /* Check the next segment if any */
447 return tree_relcwd(p+1, root, cd);
452 #ifdef BUILD_TEST_PROGRAM
454 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
456 static uint32_t FileIndex = 0;
458 * Simple test program for tree routines
460 int main(int argc, char *argv[])
464 char buf[MAXPATHLEN];
467 root->fname = tree_alloc(root, 1);
471 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
473 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
474 tree_getpath(node, buf, sizeof(buf));
475 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
478 node = (TREE_NODE *)root;
479 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
480 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
482 tree_getpath(node, buf, sizeof(buf));
483 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
486 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
487 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
489 tree_getpath(node, buf, sizeof(buf));
490 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
492 Dmsg0(100, "testprogs not found.\n");
495 free_tree((TREE_NODE *)root);
500 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
502 TREE_NODE *newparent = NULL;
507 char pathbuf[MAXPATHLEN];
508 char file[MAXPATHLEN];
512 Dmsg1(100, "FillDirectoryTree: %s\n", path);
517 while ((dir = readdir(dp))) {
518 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
521 bstrncpy(file, dir->d_name, sizeof(file));
522 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
523 if (lstat(pathbuf, &statbuf) < 0) {
525 printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
528 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
530 if (S_ISLNK(statbuf.st_mode))
531 type = TN_FILE; /* link */
532 else if (S_ISREG(statbuf.st_mode))
534 else if (S_ISDIR(statbuf.st_mode)) {
536 } else if (S_ISCHR(statbuf.st_mode))
537 type = TN_FILE; /* char dev */
538 else if (S_ISBLK(statbuf.st_mode))
539 type = TN_FILE; /* block dev */
540 else if (S_ISFIFO(statbuf.st_mode))
541 type = TN_FILE; /* fifo */
542 else if (S_ISSOCK(statbuf.st_mode))
543 type = TN_FILE; /* sock */
546 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
549 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
550 node = new_tree_node(root);
551 node->FileIndex = ++FileIndex;
552 parent = insert_tree_node(pathbuf, node, root, parent);
553 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
554 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
555 FillDirectoryTree(pathbuf, root, node);
562 #define MAXPATHLEN 2000
565 void print_tree(char *path, TREE_NODE *tree)
567 char buf[MAXPATHLEN];
573 switch (tree->type) {
585 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
586 switch (tree->type) {
591 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
592 print_tree(buf, first_child(tree));
595 print_tree(path, first_child(tree));
598 Pmsg1(000, "Unknown node type %d\n", tree->type);
600 print_tree(path, tree->sibling_);