1 /*
2 Bacula(R) - The Network Backup Solution
3
4 Copyright (C) 2000-2020 Kern Sibbald
5
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.
8
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.
13
14 This notice must be preserved when any source code is
15 conveyed and/or propagated.
16
17 Bacula(R) is a registered trademark of Kern Sibbald.
18 */
19 /*
20 * Directory tree build/traverse routines
21 *
22 * Kern Sibbald, June MMII
23 *
24 */
25
26
27 #include "bacula.h"
28 #include "findlib/find.h"
29
30 #define B_PAGE_SIZE 4096
31 #define MAX_PAGES 2400
32 #define MAX_BUF_SIZE (MAX_PAGES * B_PAGE_SIZE) /* approx 10MB */
33
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);
38
39 /*
40 * NOTE !!!!! we turn off Debug messages for performance reasons.
41 */
42 #undef Dmsg0
43 #undef Dmsg1
44 #undef Dmsg2
45 #undef Dmsg3
46 #define Dmsg0(n,f)
47 #define Dmsg1(n,f,a1)
48 #define Dmsg2(n,f,a1,a2)
49 #define Dmsg3(n,f,a1,a2,a3)
50
51 /*
52 * This subroutine gets a big buffer.
53 */
malloc_buf(TREE_ROOT * root,int size)54 static void malloc_buf(TREE_ROOT *root, int size)
55 {
56 struct s_mem *mem;
57
58 mem = (struct s_mem *)malloc(size);
59 root->total_size += size;
60 root->blocks++;
61 mem->next = root->mem;
62 root->mem = 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);
66 }
67
68
69 /*
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.
74 */
new_tree(int count)75 TREE_ROOT *new_tree(int count)
76 {
77 TREE_ROOT *root;
78 uint32_t size;
79
80 if (count < 1000) { /* minimum tree size */
81 count = 1000;
82 }
83 root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
84 bmemset(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)) {
88 size = MAX_BUF_SIZE;
89 }
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);
94 root->type = TN_ROOT;
95 root->fname = "";
96 root->can_access = 1;
97 HL_ENTRY* entry = NULL;
98 root->hardlinks.init(entry, &entry->link, 0);
99 return root;
100 }
101
102 /*
103 * Create a new tree node.
104 */
new_tree_node(TREE_ROOT * root)105 static TREE_NODE *new_tree_node(TREE_ROOT *root)
106 {
107 TREE_NODE *node;
108 int size = sizeof(TREE_NODE);
109 node = (TREE_NODE *)tree_alloc(root, size);
110 bmemset(node, 0, size);
111 node->delta_seq = -1;
112 node->can_access = 1;
113 return node;
114 }
115
116 /*
117 * This routine can be called to release the
118 * previously allocated tree node.
119 */
free_tree_node(TREE_ROOT * root)120 static void free_tree_node(TREE_ROOT *root)
121 {
122 int asize = BALIGN(sizeof(TREE_NODE));
123 root->mem->rem += asize;
124 root->mem->mem -= asize;
125 }
126
tree_remove_node(TREE_ROOT * root,TREE_NODE * node)127 void tree_remove_node(TREE_ROOT *root, TREE_NODE *node)
128 {
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);
133 } else {
134 Dmsg0(0, "Can't release tree node\n");
135 }
136 }
137
138 /*
139 * Allocate bytes for filename in tree structure.
140 * Keep the pointers properly aligned by allocating
141 * sizes that are aligned.
142 */
tree_alloc(TREE_ROOT * root,int size)143 static char *tree_alloc(TREE_ROOT *root, int size)
144 {
145 char *buf;
146 int asize = BALIGN(size);
147
148 if (root->mem->rem < asize) {
149 uint32_t mb_size;
150 if (root->total_size >= (MAX_BUF_SIZE / 2)) {
151 mb_size = MAX_BUF_SIZE;
152 } else {
153 mb_size = MAX_BUF_SIZE / 2;
154 }
155 malloc_buf(root, mb_size);
156 }
157 root->mem->rem -= asize;
158 buf = root->mem->mem;
159 root->mem->mem += asize;
160 return buf;
161 }
162
163
164 /* This routine frees the whole tree */
free_tree(TREE_ROOT * root)165 void free_tree(TREE_ROOT *root)
166 {
167 struct s_mem *mem, *rel;
168 uint32_t freed_blocks = 0;
169
170 root->hardlinks.destroy();
171 for (mem=root->mem; mem; ) {
172 rel = mem;
173 mem = mem->next;
174 free(rel);
175 freed_blocks++;
176 }
177 if (root->cached_path) {
178 free_pool_memory(root->cached_path);
179 root->cached_path = NULL;
180 }
181 Dmsg3(100, "Total size=%u blocks=%u freed_blocks=%u\n", root->total_size, root->blocks, freed_blocks);
182 free(root);
183 garbage_collect_memory();
184 return;
185 }
186
187 /* Add Delta part for this node */
tree_add_delta_part(TREE_ROOT * root,TREE_NODE * node,JobId_t JobId,int32_t FileIndex)188 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
189 JobId_t JobId, int32_t FileIndex)
190 {
191 struct delta_list *elt =
192 (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
193
194 elt->next = node->delta_list;
195 elt->JobId = JobId;
196 elt->FileIndex = FileIndex;
197 node->delta_list = elt;
198 }
199
200 /*
201 * Insert a node in the tree. This is the main subroutine
202 * called when building a tree.
203 *
204 */
insert_tree_node(char * path,char * fname,int type,TREE_ROOT * root,TREE_NODE * parent)205 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
206 TREE_ROOT *root, TREE_NODE *parent)
207 {
208 char *p, *q;
209 int path_len = strlen(path);
210 TREE_NODE *node;
211
212 Dmsg1(100, "insert_tree_node: %s\n", path);
213 /*
214 * If trailing slash on path, strip it
215 */
216 if (path_len > 0) {
217 q = path + path_len - 1;
218 if (IsPathSeparator(*q)) {
219 *q = 0; /* strip trailing slash */
220 } else {
221 q = NULL; /* no trailing slash */
222 }
223 } else {
224 q = NULL; /* no trailing slash */
225 }
226 /* If no filename, strip last component of path as "filename" */
227 if (*fname == 0) {
228 p = (char *)last_path_separator(path); /* separate path and filename */
229 if (p) {
230 fname = p + 1; /* set new filename */
231 *p = '\0'; /* terminate new path */
232 }
233 } else {
234 p = NULL;
235 }
236 if (*fname) {
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;
243 } else {
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;
248 }
249 Dmsg1(100, "parent=%s\n", parent->fname);
250 }
251 } else {
252 fname = path;
253 if (!parent) {
254 parent = (TREE_NODE *)root;
255 type = TN_DIR_NLS;
256 }
257 Dmsg1(100, "No / found: %s\n", path);
258 }
259
260 node = search_and_insert_tree_node(fname, 0, root, parent);
261 if (q) { /* if trailing slash on entry */
262 *q = '/'; /* restore it */
263 }
264 if (p) { /* if slash in path trashed */
265 *p = '/'; /* restore full path */
266 }
267 return node;
268 }
269
270 /*
271 * Ensure that all appropriate nodes for a full path exist in
272 * the tree.
273 */
make_tree_path(char * path,TREE_ROOT * root)274 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
275 {
276 TREE_NODE *parent, *node;
277 char *fname, *p;
278 int type = TN_NEWDIR;
279
280 Dmsg1(100, "make_tree_path: %s\n", path);
281 if (*path == 0) {
282 Dmsg0(100, "make_tree_path: parent=*root*\n");
283 return (TREE_NODE *)root;
284 }
285 p = (char *)last_path_separator(path); /* get last dir component of path */
286 if (p) {
287 fname = p + 1;
288 *p = 0; /* terminate path */
289 parent = make_tree_path(path, root);
290 *p = '/'; /* restore full name */
291 } else {
292 fname = path;
293 parent = (TREE_NODE *)root;
294 type = TN_DIR_NLS;
295 }
296 node = search_and_insert_tree_node(fname, type, root, parent);
297 return node;
298 }
299
node_compare(void * item1,void * item2)300 static int node_compare(void *item1, void *item2)
301 {
302 TREE_NODE *tn1 = (TREE_NODE *)item1;
303 TREE_NODE *tn2 = (TREE_NODE *)item2;
304 if (tn1->fname[0] > tn2->fname[0]) {
305 return 1;
306 } else if (tn1->fname[0] < tn2->fname[0]) {
307 return -1;
308 }
309 return strcmp(tn1->fname, tn2->fname);
310 }
311
312 /*
313 * See if the fname already exists. If not insert a new node for it.
314 */
search_and_insert_tree_node(char * fname,int type,TREE_ROOT * root,TREE_NODE * parent)315 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
316 TREE_ROOT *root, TREE_NODE *parent)
317 {
318 TREE_NODE *node, *found_node;
319 node = new_tree_node(root);
320 node->fname = fname;
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;
325 return found_node;
326 }
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;
332 node->type = type;
333 /* Maintain a linear chain of nodes */
334 if (!root->first) {
335 root->first = node;
336 root->last = node;
337 } else {
338 root->last->next = node;
339 root->last = node;
340 }
341 node->inserted = true; /* inserted into tree */
342 return node;
343
344 }
345
tree_getpath(TREE_NODE * node,char * buf,int buf_size)346 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
347 {
348 if (!node) {
349 buf[0] = 0;
350 return 1;
351 }
352 tree_getpath(node->parent, buf, buf_size);
353 /*
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 /
357 */
358 if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
359 buf[0] = '\0';
360 }
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.
365 */
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);
369 }
370 return 1;
371 }
372
373 /*
374 * Change to specified directory
375 */
tree_cwd(char * path,TREE_ROOT * root,TREE_NODE * node)376 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
377 {
378 if (path[0] == '.' && path[1] == '\0') {
379 return node;
380 }
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;
384 if (path[2] == 0) {
385 return parent;
386 } else {
387 return tree_cwd(path+3, root, parent);
388 }
389 }
390 if (IsPathSeparator(path[0])) {
391 Dmsg0(100, "Doing absolute lookup.\n");
392 return tree_relcwd(path+1, root, (TREE_NODE *)root);
393 }
394 Dmsg0(100, "Doing relative lookup.\n");
395 return tree_relcwd(path, root, node);
396 }
397
398
399 /*
400 * Do a relative cwd -- i.e. relative to current node rather than root node
401 */
tree_relcwd(char * path,TREE_ROOT * root,TREE_NODE * node)402 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
403 {
404 char *p;
405 int len;
406 TREE_NODE *cd;
407 char save_char;
408 int match;
409
410 if (*path == 0) {
411 return node;
412 }
413 /* Check the current segment only */
414 if ((p = first_path_separator(path)) != NULL) {
415 len = p - path;
416 } else {
417 len = strlen(path);
418 }
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) {
424 break;
425 }
426 /* fnmatch has no len in call so we truncate the string */
427 save_char = path[len];
428 path[len] = 0;
429 match = fnmatch(path, cd->fname, 0) == 0;
430 path[len] = save_char;
431 if (match) {
432 break;
433 }
434 }
435 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
436 return NULL;
437 }
438 if (!cd->can_access) { /* Will display permission denied */
439 return cd;
440 }
441 if (!p) {
442 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
443 return cd;
444 }
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);
448 }
449
450
451
452 #ifdef BUILD_TEST_PROGRAM
453
454 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
455
456 static uint32_t FileIndex = 0;
457 /*
458 * Simple test program for tree routines
459 */
main(int argc,char * argv[])460 int main(int argc, char *argv[])
461 {
462 TREE_ROOT *root;
463 TREE_NODE *node;
464 char buf[MAXPATHLEN];
465
466 root = new_tree();
467 root->fname = tree_alloc(root, 1);
468 *root->fname = 0;
469 root->fname_len = 0;
470
471 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
472
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);
476 }
477
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);
481 if (node) {
482 tree_getpath(node, buf, sizeof(buf));
483 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
484 }
485
486 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
487 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
488 if (node) {
489 tree_getpath(node, buf, sizeof(buf));
490 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
491 } else {
492 Dmsg0(100, "testprogs not found.\n");
493 }
494
495 free_tree((TREE_NODE *)root);
496
497 return 0;
498 }
499
FillDirectoryTree(char * path,TREE_ROOT * root,TREE_NODE * parent)500 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
501 {
502 TREE_NODE *newparent = NULL;
503 TREE_NODE *node;
504 struct stat statbuf;
505 DIR *dp;
506 POOL_MEM dname(PM_FNAME);
507 char pathbuf[MAXPATHLEN];
508 char file[MAXPATHLEN];
509 int type;
510 int i;
511
512 Dmsg1(100, "FillDirectoryTree: %s\n", path);
513 dp = opendir(path);
514 if (!dp) {
515 return;
516 }
517 while (readdir(dp, dname.addr()) != 0) {
518 if (strcmp(dname.c_str(), ".") == 0 || strcmp(dname.c_str(), "..") == 0) {
519 continue;
520 }
521 bstrncpy(file, dname.c_str(), sizeof(file));
522 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
523 if (lstat(pathbuf, &statbuf) < 0) {
524 berrno be;
525 printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
526 continue;
527 }
528 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
529 type = TN_FILE;
530 if (S_ISLNK(statbuf.st_mode))
531 type = TN_FILE; /* link */
532 else if (S_ISREG(statbuf.st_mode))
533 type = TN_FILE;
534 else if (S_ISDIR(statbuf.st_mode)) {
535 type = TN_DIR;
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 */
544 else {
545 type = TN_FILE;
546 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
547 }
548
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);
556 }
557 }
558 closedir(dp);
559 }
560
561 #ifndef MAXPATHLEN
562 #define MAXPATHLEN 2000
563 #endif
564
print_tree(char * path,TREE_NODE * tree)565 void print_tree(char *path, TREE_NODE *tree)
566 {
567 char buf[MAXPATHLEN];
568 char *termchr;
569
570 if (!tree) {
571 return;
572 }
573 switch (tree->type) {
574 case TN_DIR_NLS:
575 case TN_DIR:
576 case TN_NEWDIR:
577 termchr = "/";
578 break;
579 case TN_ROOT:
580 case TN_FILE:
581 default:
582 termchr = "";
583 break;
584 }
585 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
586 switch (tree->type) {
587 case TN_FILE:
588 case TN_NEWDIR:
589 case TN_DIR:
590 case TN_DIR_NLS:
591 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
592 print_tree(buf, first_child(tree));
593 break;
594 case TN_ROOT:
595 print_tree(path, first_child(tree));
596 break;
597 default:
598 Pmsg1(000, "Unknown node type %d\n", tree->type);
599 }
600 print_tree(path, tree->sibling_);
601 return;
602 }
603
604 #endif
605