1 /*
2 BAREOS® - Backup Archiving REcovery Open Sourced
3
4 Copyright (C) 2002-2012 Free Software Foundation Europe e.V.
5 Copyright (C) 2013-2019 Bareos GmbH & Co. KG
6
7 This program is Free Software; you can redistribute it and/or
8 modify it under the terms of version three of the GNU Affero General Public
9 License as published by the Free Software Foundation and included
10 in the file LICENSE.
11
12 This program is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Affero General Public License for more details.
16
17 You should have received a copy of the GNU Affero General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.
21 */
22 /*
23 * Directory tree build/traverse routines
24 *
25 * Kern Sibbald, June MMII
26 */
27
28 #include "include/bareos.h"
29 #include "lib/tree.h"
30 #include "lib/util.h"
31
32 #define B_PAGE_SIZE 4096
33 #define MAX_PAGES 2400
34 #define MAX_BUF_SIZE (MAX_PAGES * B_PAGE_SIZE) /* approx 10MB */
35
36 /* Forward referenced subroutines */
37 static TREE_NODE* search_and_insert_tree_node(char* fname,
38 int type,
39 TREE_ROOT* root,
40 TREE_NODE* parent);
41 template <typename T>
42 static T* tree_alloc(TREE_ROOT* root, int size);
43
44 /*
45 * NOTE !!!!! we turn off Debug messages for performance reasons.
46 */
47 #undef Dmsg0
48 #undef Dmsg1
49 #undef Dmsg2
50 #undef Dmsg3
51 #define Dmsg0(n, f)
52 #define Dmsg1(n, f, a1)
53 #define Dmsg2(n, f, a1, a2)
54 #define Dmsg3(n, f, a1, a2, a3)
55
56 /*
57 * This subroutine gets a big buffer.
58 */
MallocBuf(TREE_ROOT * root,int size)59 static void MallocBuf(TREE_ROOT* root, int size)
60 {
61 struct s_mem* mem;
62
63 mem = (struct s_mem*)malloc(size);
64 root->total_size += size;
65 root->blocks++;
66 mem->next = root->mem;
67 root->mem = mem;
68 mem->mem = mem->first;
69 mem->rem = (char*)mem + size - (char*)mem->mem;
70 Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
71 }
72
73 /*
74 * Note, we allocate a big buffer in the tree root
75 * from which we allocate nodes. This runs more
76 * than 100 times as fast as directly using malloc()
77 * for each of the nodes.
78 */
new_tree(int count)79 TREE_ROOT* new_tree(int count)
80 {
81 TREE_ROOT* root;
82 uint32_t size;
83
84 if (count < 1000) { /* minimum tree size */
85 count = 1000;
86 }
87 root = static_cast<TREE_ROOT*>(malloc(sizeof(TREE_ROOT)));
88 root = new (root) TREE_ROOT();
89
90 /*
91 * Assume filename + node = 40 characters average length
92 */
93 size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
94 if (count > 1000000 || size > (MAX_BUF_SIZE / 2)) { size = MAX_BUF_SIZE; }
95 Dmsg2(400, "count=%d size=%d\n", count, size);
96 MallocBuf(root, size);
97 root->cached_path_len = -1;
98 root->cached_path = GetPoolMemory(PM_FNAME);
99 root->type = TN_ROOT;
100 root->fname = "";
101 HL_ENTRY* entry = NULL;
102 root->hardlinks.init(entry, &entry->link, 0, 1);
103 return root;
104 }
105
106 /*
107 * Create a new tree node.
108 */
new_tree_node(TREE_ROOT * root)109 static TREE_NODE* new_tree_node(TREE_ROOT* root)
110 {
111 TREE_NODE* node;
112 int size = sizeof(TREE_NODE);
113 node = tree_alloc<TREE_NODE>(root, size);
114 node = new (node) TREE_NODE();
115 node->delta_seq = -1;
116 return node;
117 }
118
119 /*
120 * This routine can be called to release the previously allocated tree node.
121 */
FreeTreeNode(TREE_ROOT * root)122 static void FreeTreeNode(TREE_ROOT* root)
123 {
124 int asize = BALIGN(sizeof(TREE_NODE));
125 root->mem->rem += asize;
126 root->mem->mem = (char*)root->mem->mem - asize;
127 }
128
TreeRemoveNode(TREE_ROOT * root,TREE_NODE * node)129 void TreeRemoveNode(TREE_ROOT* root, TREE_NODE* node)
130 {
131 int asize = BALIGN(sizeof(TREE_NODE));
132 node->parent->child.remove(node);
133 if (((char*)root->mem->mem - asize) == (char*)node) {
134 FreeTreeNode(root);
135 } else {
136 Dmsg0(0, "Can't release tree node\n");
137 }
138 }
139
140 /*
141 * Allocate bytes for filename in tree structure.
142 * Keep the pointers properly aligned by allocating
143 * sizes that are aligned.
144 */
145 template <typename T>
tree_alloc(TREE_ROOT * root,int size)146 static T* tree_alloc(TREE_ROOT* root, int size)
147 {
148 T* buf;
149 int asize = BALIGN(size);
150
151 if (root->mem->rem < asize) {
152 uint32_t mb_size;
153 if (root->total_size >= (MAX_BUF_SIZE / 2)) {
154 mb_size = MAX_BUF_SIZE;
155 } else {
156 mb_size = MAX_BUF_SIZE / 2;
157 }
158 MallocBuf(root, mb_size);
159 }
160 root->mem->rem -= asize;
161 buf = static_cast<T*>(root->mem->mem);
162 root->mem->mem = (char*)root->mem->mem + asize;
163 return buf;
164 }
165
166 /*
167 * This routine frees the whole tree
168 */
FreeTree(TREE_ROOT * root)169 void FreeTree(TREE_ROOT* root)
170 {
171 struct s_mem *mem, *rel;
172 uint32_t freed_blocks = 0;
173
174 root->hardlinks.destroy();
175 for (mem = root->mem; mem;) {
176 rel = mem;
177 mem = mem->next;
178 free(rel);
179 freed_blocks++;
180 }
181 if (root->cached_path) {
182 FreePoolMemory(root->cached_path);
183 root->cached_path = NULL;
184 }
185 Dmsg3(100, "Total size=%u blocks=%u freed_blocks=%u\n", root->total_size,
186 root->blocks, freed_blocks);
187 free(root);
188 GarbageCollectMemory();
189 return;
190 }
191
192 /*
193 * Add Delta part for this node
194 */
TreeAddDeltaPart(TREE_ROOT * root,TREE_NODE * node,JobId_t JobId,int32_t FileIndex)195 void TreeAddDeltaPart(TREE_ROOT* root,
196 TREE_NODE* node,
197 JobId_t JobId,
198 int32_t FileIndex)
199 {
200 struct delta_list* elt
201 = tree_alloc<delta_list>(root, sizeof(struct delta_list));
202
203 elt->next = node->delta_list;
204 elt->JobId = JobId;
205 elt->FileIndex = FileIndex;
206 node->delta_list = elt;
207 }
208
209 /*
210 * Insert a node in the tree. This is the main subroutine called when building a
211 * tree.
212 */
insert_tree_node(char * path,char * fname,int type,TREE_ROOT * root,TREE_NODE * parent)213 TREE_NODE* insert_tree_node(char* path,
214 char* fname,
215 int type,
216 TREE_ROOT* root,
217 TREE_NODE* parent)
218 {
219 char *p, *q;
220 int path_len = strlen(path);
221 TREE_NODE* node;
222
223 Dmsg1(100, "insert_tree_node: %s\n", path);
224
225 /*
226 * If trailing slash on path, strip it
227 */
228 if (path_len > 0) {
229 q = path + path_len - 1;
230 if (IsPathSeparator(*q)) {
231 *q = 0; /* strip trailing slash */
232 } else {
233 q = NULL; /* no trailing slash */
234 }
235 } else {
236 q = NULL; /* no trailing slash */
237 }
238
239 /*
240 * If no filename, strip last component of path as "filename"
241 */
242 if (*fname == 0) {
243 p = (char*)last_path_separator(path); /* separate path and filename */
244 if (p) {
245 fname = p + 1; /* set new filename */
246 *p = '\0'; /* Terminate new path */
247 }
248 } else {
249 p = NULL;
250 }
251
252 if (*fname) {
253 if (!parent) { /* if no parent, we need to make one */
254 Dmsg1(100, "make_tree_path for %s\n", path);
255 path_len = strlen(path); /* get new length */
256 if (path_len == root->cached_path_len
257 && bstrcmp(path, root->cached_path)) {
258 parent = root->cached_parent;
259 } else {
260 root->cached_path_len = path_len;
261 PmStrcpy(root->cached_path, path);
262 parent = make_tree_path(path, root);
263 root->cached_parent = parent;
264 }
265 Dmsg1(100, "parent=%s\n", parent->fname);
266 }
267 } else {
268 fname = path;
269 if (!parent) {
270 parent = (TREE_NODE*)root;
271 type = TN_DIR_NLS;
272 }
273 Dmsg1(100, "No / found: %s\n", path);
274 }
275
276 node = search_and_insert_tree_node(fname, 0, root, parent);
277
278 if (q) { /* if trailing slash on entry */
279 *q = '/'; /* restore it */
280 }
281
282 if (p) { /* if slash in path trashed */
283 *p = '/'; /* restore full path */
284 }
285
286 return node;
287 }
288
289 /*
290 * Ensure that all appropriate nodes for a full path exist in the tree.
291 */
make_tree_path(char * path,TREE_ROOT * root)292 TREE_NODE* make_tree_path(char* path, TREE_ROOT* root)
293 {
294 TREE_NODE *parent, *node;
295 char *fname, *p;
296 int type = TN_NEWDIR;
297
298 Dmsg1(100, "make_tree_path: %s\n", path);
299
300 if (*path == 0) {
301 Dmsg0(100, "make_tree_path: parent=*root*\n");
302 return (TREE_NODE*)root;
303 }
304
305 /*
306 * Get last dir component of path
307 */
308 p = (char*)last_path_separator(path);
309 if (p) {
310 fname = p + 1;
311 *p = 0; /* Terminate path */
312 parent = make_tree_path(path, root);
313 *p = '/'; /* restore full name */
314 } else {
315 fname = path;
316 parent = (TREE_NODE*)root;
317 type = TN_DIR_NLS;
318 }
319
320 node = search_and_insert_tree_node(fname, type, root, parent);
321
322 return node;
323 }
324
NodeCompare(void * item1,void * item2)325 static int NodeCompare(void* item1, void* item2)
326 {
327 TREE_NODE* tn1 = (TREE_NODE*)item1;
328 TREE_NODE* tn2 = (TREE_NODE*)item2;
329
330 if (tn1->fname[0] > tn2->fname[0]) {
331 return 1;
332 } else if (tn1->fname[0] < tn2->fname[0]) {
333 return -1;
334 }
335
336 return strcmp(tn1->fname, tn2->fname);
337 }
338
339 /*
340 * See if the fname already exists. If not insert a new node for it.
341 */
search_and_insert_tree_node(char * fname,int type,TREE_ROOT * root,TREE_NODE * parent)342 static TREE_NODE* search_and_insert_tree_node(char* fname,
343 int type,
344 TREE_ROOT* root,
345 TREE_NODE* parent)
346 {
347 TREE_NODE *node, *found_node;
348
349 node = new_tree_node(root);
350 node->fname = fname;
351 found_node = (TREE_NODE*)parent->child.insert(node, NodeCompare);
352 if (found_node != node) { /* already in list */
353 FreeTreeNode(root); /* free node allocated above */
354 found_node->inserted = false;
355 return found_node;
356 }
357
358 /*
359 * It was not found, but is now inserted
360 */
361 node->fname_len = strlen(fname);
362 node->fname = tree_alloc<char>(root, node->fname_len + 1);
363 strcpy(node->fname, fname);
364 node->parent = parent;
365 node->type = type;
366
367 /*
368 * Maintain a linear chain of nodes
369 */
370 if (!root->first) {
371 root->first = node;
372 root->last = node;
373 } else {
374 root->last->next = node;
375 root->last = node;
376 }
377
378 node->inserted = true; /* inserted into tree */
379 return node;
380 }
381
TreeGetpathItem(TREE_NODE * node,POOLMEM * & path)382 static void TreeGetpathItem(TREE_NODE* node, POOLMEM*& path)
383 {
384 if (!node) { return; }
385
386 TreeGetpathItem(node->parent, path);
387
388 /*
389 * Fixup for Win32. If we have a Win32 directory and
390 * there is only a / in the buffer, remove it since
391 * win32 names don't generally start with /
392 */
393 if (node->type == TN_DIR_NLS && IsPathSeparator(path[0]) && path[1] == '\0') {
394 PmStrcpy(path, "");
395 }
396 PmStrcat(path, node->fname);
397
398 /*
399 * Add a slash for all directories unless we are at the root,
400 * also add a slash to a soft linked file if it has children
401 * i.e. it is linked to a directory.
402 */
403 if ((node->type != TN_FILE && !(IsPathSeparator(path[0]) && path[1] == '\0'))
404 || (node->soft_link && TreeNodeHasChild(node))) {
405 PmStrcat(path, "/");
406 }
407 }
408
tree_getpath(TREE_NODE * node)409 POOLMEM* tree_getpath(TREE_NODE* node)
410 {
411 POOLMEM* path;
412
413 if (!node) { return NULL; }
414
415 /*
416 * Allocate a new empty path.
417 */
418 path = GetPoolMemory(PM_NAME);
419 PmStrcpy(path, "");
420
421 /*
422 * Fill the path with the full path.
423 */
424 TreeGetpathItem(node, path);
425
426 return path;
427 }
428
429 /*
430 * Change to specified directory
431 */
tree_cwd(char * path,TREE_ROOT * root,TREE_NODE * node)432 TREE_NODE* tree_cwd(char* path, TREE_ROOT* root, TREE_NODE* node)
433 {
434 if (path[0] == '.' && path[1] == '\0') { return node; }
435
436 /*
437 * Handle relative path
438 */
439 if (path[0] == '.' && path[1] == '.'
440 && (IsPathSeparator(path[2]) || path[2] == '\0')) {
441 TREE_NODE* parent = node->parent ? node->parent : node;
442 if (path[2] == 0) {
443 return parent;
444 } else {
445 return tree_cwd(path + 3, root, parent);
446 }
447 }
448
449 if (IsPathSeparator(path[0])) {
450 Dmsg0(100, "Doing absolute lookup.\n");
451 return tree_relcwd(path + 1, root, (TREE_NODE*)root);
452 }
453
454 Dmsg0(100, "Doing relative lookup.\n");
455
456 return tree_relcwd(path, root, node);
457 }
458
459 /*
460 * Do a relative cwd -- i.e. relative to current node rather than root node
461 */
tree_relcwd(char * path,TREE_ROOT * root,TREE_NODE * node)462 TREE_NODE* tree_relcwd(char* path, TREE_ROOT* root, TREE_NODE* node)
463 {
464 char* p;
465 int len;
466 TREE_NODE* cd;
467 char save_char;
468 int match;
469
470 if (*path == 0) { return node; }
471
472 /*
473 * Check the current segment only
474 */
475 if ((p = first_path_separator(path)) != NULL) {
476 len = p - path;
477 } else {
478 len = strlen(path);
479 }
480
481 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
482
483 foreach_child (cd, node) {
484 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
485 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
486 && bstrncmp(cd->fname, path, len)) {
487 break;
488 }
489
490 /*
491 * fnmatch has no len in call so we truncate the string
492 */
493 save_char = path[len];
494 path[len] = 0;
495 match = fnmatch(path, cd->fname, 0) == 0;
496 path[len] = save_char;
497
498 if (match) { break; }
499 }
500
501 if (!cd || (cd->type == TN_FILE && !TreeNodeHasChild(cd))) { return NULL; }
502
503 if (!p) {
504 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
505 return cd;
506 }
507
508 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p + 1, cd->fname);
509
510 /*
511 * Check the next segment if any
512 */
513 return tree_relcwd(p + 1, root, cd);
514 }
515