← Back to branch summary

~stewart/percona-xtrabackup/bug1213036

« back to all changes in this revision

Viewing changes to src/libarchive/contrib/shar/tree.c

  • Committer: Alexey Kopytov
  • Date: 2012-02-10 20:05:56 UTC
  • mto: (391.1.5 staging)
  • mto: This revision was merged to the branch mainline in revision 390.
  • Revision ID: akopytov@gmail.com-20120210200556-6kx41z8wwrqfucro
Rebase of the parallel compression patch on new trunk + post-review
fixes.

Implementation of parallel compression and streaming for XtraBackup.

This revision implements the following changes:

* InnoDB files are now streamed by the xtrabackup binary rather than
innobackupex. As a result, integrity is now verified by xtrabackup and
thus tar4ibd is no longer needed, so it was removed.

* xtrabackup binary now accepts the new '--stream' option which has
exactly the same semantics as the '--stream' option in
innobackupex: it tells xtrabackup to stream all files to the standard
output in the specified format rather than storing them locally.

* The xtrabackup binary can now do parallel compression using the
quicklz library. Two new options were added to xtrabackup to support
this feature:

- '--compress' tells xtrabackup to compress all output data, including
the transaction log file and meta data files, using the specified
compression algorithm. The only currently supported algorithm is
'quicklz'. The resulting files have the qpress archive format,
i.e. every *.qp file produced by xtrabackup is essentially a one-file
qpress archive and can be extracted and uncompressed by the qpress
file archiver (http://www.quicklz.com/).

- '--compress-threads' specifies the number of worker threads used by
xtrabackup for parallel data compression. This option defaults to 1.

Parallel compression ('--compress-threads') can be used together with
parallel file copying ('--parallel'). For example, '--parallel=4
--compress --compress-threads=2' will create 4 IO threads that will
read the data and pipe it to 2 compression threads.

* To support simultaneous compression and streaming, a new custom
streaming format called 'xbstream' was introduced to XtraBackup in
addition to the 'tar' format. That was required to overcome some
limitations of traditional archive formats such as 'tar', 'cpio' and
others that do not allow streaming dynamically generated files, for
example dynamically compressed files.  Other advantages of xbstream over
traditional streaming/archive formats include ability to stream multiple
files concurrently (so it is possible to use streaming in the xbstream
format together with the --parallel option) and more compact data
storage.

* To allow streaming and extracting files to/from the xbstream format
produced by xtrabackup, a new utility aptly called 'xbstream' was
added to the XtraBackup distribution. This utility has a tar-like
interface:

- with the '-x' option it extracts files from the stream read from its
standard input to the current directory unless specified otherwise
with the '-C' option.

- with the '-c' option it streams files specified on the command line
to its standard output.

The utility also tries to minimize its impact on the OS page cache by
using the appropriate posix_fadvise() calls when available.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libarchive/contrib/shar/tree.c
 
1
/*-
 
2
 * Copyright (c) 2003-2007 Tim Kientzle
 
3
 * All rights reserved.
 
4
 *
 
5
 * Redistribution and use in source and binary forms, with or without
 
6
 * modification, are permitted provided that the following conditions
 
7
 * are met:
 
8
 * 1. Redistributions of source code must retain the above copyright
 
9
 *    notice, this list of conditions and the following disclaimer.
 
10
 * 2. Redistributions in binary form must reproduce the above copyright
 
11
 *    notice, this list of conditions and the following disclaimer in the
 
12
 *    documentation and/or other materials provided with the distribution.
 
13
 *
 
14
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
 
15
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
16
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 
17
 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
 
18
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
19
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
20
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
21
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
22
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
23
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
24
 */
 
25
 
 
26
/*-
 
27
 * This is a new directory-walking system that addresses a number
 
28
 * of problems I've had with fts(3).  In particular, it has no
 
29
 * pathname-length limits (other than the size of 'int'), handles
 
30
 * deep logical traversals, uses considerably less memory, and has
 
31
 * an opaque interface (easier to modify in the future).
 
32
 *
 
33
 * Internally, it keeps a single list of "tree_entry" items that
 
34
 * represent filesystem objects that require further attention.
 
35
 * Non-directories are not kept in memory: they are pulled from
 
36
 * readdir(), returned to the client, then freed as soon as possible.
 
37
 * Any directory entry to be traversed gets pushed onto the stack.
 
38
 *
 
39
 * There is surprisingly little information that needs to be kept for
 
40
 * each item on the stack.  Just the name, depth (represented here as the
 
41
 * string length of the parent directory's pathname), and some markers
 
42
 * indicating how to get back to the parent (via chdir("..") for a
 
43
 * regular dir or via fchdir(2) for a symlink).
 
44
 */
 
45
#include "tree_config.h"
 
46
__FBSDID("$FreeBSD$");
 
47
 
 
48
#ifdef HAVE_SYS_STAT_H
 
49
#include <sys/stat.h>
 
50
#endif
 
51
#ifdef HAVE_DIRENT_H
 
52
#include <dirent.h>
 
53
#endif
 
54
#ifdef HAVE_ERRNO_H
 
55
#include <errno.h>
 
56
#endif
 
57
#ifdef HAVE_FCNTL_H
 
58
#include <fcntl.h>
 
59
#endif
 
60
#ifdef HAVE_STDLIB_H
 
61
#include <stdlib.h>
 
62
#endif
 
63
#ifdef HAVE_STRING_H
 
64
#include <string.h>
 
65
#endif
 
66
#ifdef HAVE_UNISTD_H
 
67
#include <unistd.h>
 
68
#endif
 
69
 
 
70
#include "tree.h"
 
71
 
 
72
/*
 
73
 * TODO:
 
74
 *    1) Loop checking.
 
75
 *    3) Arbitrary logical traversals by closing/reopening intermediate fds.
 
76
 */
 
77
 
 
78
struct tree_entry {
 
79
        struct tree_entry *next;
 
80
        struct tree_entry *parent;
 
81
        char *name;
 
82
        size_t dirname_length;
 
83
        dev_t dev;
 
84
        ino_t ino;
 
85
        int fd;
 
86
        int flags;
 
87
};
 
88
 
 
89
/* Definitions for tree_entry.flags bitmap. */
 
90
#define isDir 1 /* This entry is a regular directory. */
 
91
#define isDirLink 2 /* This entry is a symbolic link to a directory. */
 
92
#define needsPreVisit 4 /* This entry needs to be previsited. */
 
93
#define needsPostVisit 8 /* This entry needs to be postvisited. */
 
94
 
 
95
/*
 
96
 * Local data for this package.
 
97
 */
 
98
struct tree {
 
99
        struct tree_entry       *stack;
 
100
        struct tree_entry       *current;
 
101
        DIR     *d;
 
102
        int      initialDirFd;
 
103
        int      flags;
 
104
        int      visit_type;
 
105
        int      tree_errno; /* Error code from last failed operation. */
 
106
 
 
107
        char    *buff;
 
108
        const char      *basename;
 
109
        size_t   buff_length;
 
110
        size_t   path_length;
 
111
        size_t   dirname_length;
 
112
 
 
113
        int      depth;
 
114
        int      openCount;
 
115
        int      maxOpenCount;
 
116
 
 
117
        struct stat     lst;
 
118
        struct stat     st;
 
119
};
 
120
 
 
121
/* Definitions for tree.flags bitmap. */
 
122
#define needsReturn 8  /* Marks first entry as not having been returned yet. */
 
123
#define hasStat 16  /* The st entry is set. */
 
124
#define hasLstat 32 /* The lst entry is set. */
 
125
 
 
126
 
 
127
#ifdef HAVE_DIRENT_D_NAMLEN
 
128
/* BSD extension; avoids need for a strlen() call. */
 
129
#define D_NAMELEN(dp)   (dp)->d_namlen
 
130
#else
 
131
#define D_NAMELEN(dp)   (strlen((dp)->d_name))
 
132
#endif
 
133
 
 
134
#if 0
 
135
#include <stdio.h>
 
136
void
 
137
tree_dump(struct tree *t, FILE *out)
 
138
{
 
139
        struct tree_entry *te;
 
140
 
 
141
        fprintf(out, "\tdepth: %d\n", t->depth);
 
142
        fprintf(out, "\tbuff: %s\n", t->buff);
 
143
        fprintf(out, "\tpwd: "); fflush(stdout); system("pwd");
 
144
        fprintf(out, "\taccess: %s\n", t->basename);
 
145
        fprintf(out, "\tstack:\n");
 
146
        for (te = t->stack; te != NULL; te = te->next) {
 
147
                fprintf(out, "\t\tte->name: %s%s%s\n", te->name,
 
148
                    te->flags & needsPreVisit ? "" : " *",
 
149
                    t->current == te ? " (current)" : "");
 
150
        }
 
151
}
 
152
#endif
 
153
 
 
154
/*
 
155
 * Add a directory path to the current stack.
 
156
 */
 
157
static void
 
158
tree_push(struct tree *t, const char *path)
 
159
{
 
160
        struct tree_entry *te;
 
161
 
 
162
        te = malloc(sizeof(*te));
 
163
        memset(te, 0, sizeof(*te));
 
164
        te->next = t->stack;
 
165
        t->stack = te;
 
166
        te->fd = -1;
 
167
        te->name = strdup(path);
 
168
        te->flags = needsPreVisit | needsPostVisit;
 
169
        te->dirname_length = t->dirname_length;
 
170
}
 
171
 
 
172
/*
 
173
 * Append a name to the current path.
 
174
 */
 
175
static void
 
176
tree_append(struct tree *t, const char *name, size_t name_length)
 
177
{
 
178
        char *p;
 
179
 
 
180
        if (t->buff != NULL)
 
181
                t->buff[t->dirname_length] = '\0';
 
182
        /* Strip trailing '/' from name, unless entire name is "/". */
 
183
        while (name_length > 1 && name[name_length - 1] == '/')
 
184
                name_length--;
 
185
 
 
186
        /* Resize pathname buffer as needed. */
 
187
        while (name_length + 1 + t->dirname_length >= t->buff_length) {
 
188
                t->buff_length *= 2;
 
189
                if (t->buff_length < 1024)
 
190
                        t->buff_length = 1024;
 
191
                t->buff = realloc(t->buff, t->buff_length);
 
192
        }
 
193
        p = t->buff + t->dirname_length;
 
194
        t->path_length = t->dirname_length + name_length;
 
195
        /* Add a separating '/' if it's needed. */
 
196
        if (t->dirname_length > 0 && p[-1] != '/') {
 
197
                *p++ = '/';
 
198
                t->path_length ++;
 
199
        }
 
200
        strncpy(p, name, name_length);
 
201
        p[name_length] = '\0';
 
202
        t->basename = p;
 
203
}
 
204
 
 
205
/*
 
206
 * Open a directory tree for traversal.
 
207
 */
 
208
struct tree *
 
209
tree_open(const char *path)
 
210
{
 
211
        struct tree *t;
 
212
 
 
213
        t = malloc(sizeof(*t));
 
214
        memset(t, 0, sizeof(*t));
 
215
        tree_append(t, path, strlen(path));
 
216
        t->initialDirFd = open(".", O_RDONLY);
 
217
        /*
 
218
         * During most of the traversal, items are set up and then
 
219
         * returned immediately from tree_next().  That doesn't work
 
220
         * for the very first entry, so we set a flag for this special
 
221
         * case.
 
222
         */
 
223
        t->flags = needsReturn;
 
224
        return (t);
 
225
}
 
226
 
 
227
/*
 
228
 * We've finished a directory; ascend back to the parent.
 
229
 */
 
230
static void
 
231
tree_ascend(struct tree *t)
 
232
{
 
233
        struct tree_entry *te;
 
234
 
 
235
        te = t->stack;
 
236
        t->depth--;
 
237
        if (te->flags & isDirLink) {
 
238
                fchdir(te->fd);
 
239
                close(te->fd);
 
240
                t->openCount--;
 
241
        } else {
 
242
                chdir("..");
 
243
        }
 
244
}
 
245
 
 
246
/*
 
247
 * Pop the working stack.
 
248
 */
 
249
static void
 
250
tree_pop(struct tree *t)
 
251
{
 
252
        struct tree_entry *te;
 
253
 
 
254
        t->buff[t->dirname_length] = '\0';
 
255
        if (t->stack == t->current && t->current != NULL)
 
256
                t->current = t->current->parent;
 
257
        te = t->stack;
 
258
        t->stack = te->next;
 
259
        t->dirname_length = te->dirname_length;
 
260
        t->basename = t->buff + t->dirname_length;
 
261
        /* Special case: starting dir doesn't skip leading '/'. */
 
262
        if (t->dirname_length > 0)
 
263
                t->basename++;
 
264
        free(te->name);
 
265
        free(te);
 
266
}
 
267
 
 
268
/*
 
269
 * Get the next item in the tree traversal.
 
270
 */
 
271
int
 
272
tree_next(struct tree *t)
 
273
{
 
274
        struct dirent *de = NULL;
 
275
 
 
276
        /* Handle the startup case by returning the initial entry. */
 
277
        if (t->flags & needsReturn) {
 
278
                t->flags &= ~needsReturn;
 
279
                return (t->visit_type = TREE_REGULAR);
 
280
        }
 
281
 
 
282
        while (t->stack != NULL) {
 
283
                /* If there's an open dir, get the next entry from there. */
 
284
                while (t->d != NULL) {
 
285
                        de = readdir(t->d);
 
286
                        if (de == NULL) {
 
287
                                closedir(t->d);
 
288
                                t->d = NULL;
 
289
                        } else if (de->d_name[0] == '.'
 
290
                            && de->d_name[1] == '\0') {
 
291
                                /* Skip '.' */
 
292
                        } else if (de->d_name[0] == '.'
 
293
                            && de->d_name[1] == '.'
 
294
                            && de->d_name[2] == '\0') {
 
295
                                /* Skip '..' */
 
296
                        } else {
 
297
                                /*
 
298
                                 * Append the path to the current path
 
299
                                 * and return it.
 
300
                                 */
 
301
                                tree_append(t, de->d_name, D_NAMELEN(de));
 
302
                                t->flags &= ~hasLstat;
 
303
                                t->flags &= ~hasStat;
 
304
                                return (t->visit_type = TREE_REGULAR);
 
305
                        }
 
306
                }
 
307
 
 
308
                /* If the current dir needs to be visited, set it up. */
 
309
                if (t->stack->flags & needsPreVisit) {
 
310
                        t->current = t->stack;
 
311
                        tree_append(t, t->stack->name, strlen(t->stack->name));
 
312
                        t->stack->flags &= ~needsPreVisit;
 
313
                        /* If it is a link, set up fd for the ascent. */
 
314
                        if (t->stack->flags & isDirLink) {
 
315
                                t->stack->fd = open(".", O_RDONLY);
 
316
                                t->openCount++;
 
317
                                if (t->openCount > t->maxOpenCount)
 
318
                                        t->maxOpenCount = t->openCount;
 
319
                        }
 
320
                        t->dirname_length = t->path_length;
 
321
                        if (chdir(t->stack->name) != 0) {
 
322
                                /* chdir() failed; return error */
 
323
                                tree_pop(t);
 
324
                                t->tree_errno = errno;
 
325
                                return (t->visit_type = TREE_ERROR_DIR);
 
326
                        }
 
327
                        t->depth++;
 
328
                        t->d = opendir(".");
 
329
                        if (t->d == NULL) {
 
330
                                tree_ascend(t); /* Undo "chdir" */
 
331
                                tree_pop(t);
 
332
                                t->tree_errno = errno;
 
333
                                return (t->visit_type = TREE_ERROR_DIR);
 
334
                        }
 
335
                        t->flags &= ~hasLstat;
 
336
                        t->flags &= ~hasStat;
 
337
                        t->basename = ".";
 
338
                        return (t->visit_type = TREE_POSTDESCENT);
 
339
                }
 
340
 
 
341
                /* We've done everything necessary for the top stack entry. */
 
342
                if (t->stack->flags & needsPostVisit) {
 
343
                        tree_ascend(t);
 
344
                        tree_pop(t);
 
345
                        t->flags &= ~hasLstat;
 
346
                        t->flags &= ~hasStat;
 
347
                        return (t->visit_type = TREE_POSTASCENT);
 
348
                }
 
349
        }
 
350
        return (t->visit_type = 0);
 
351
}
 
352
 
 
353
/*
 
354
 * Return error code.
 
355
 */
 
356
int
 
357
tree_errno(struct tree *t)
 
358
{
 
359
        return (t->tree_errno);
 
360
}
 
361
 
 
362
/*
 
363
 * Called by the client to mark the directory just returned from
 
364
 * tree_next() as needing to be visited.
 
365
 */
 
366
void
 
367
tree_descend(struct tree *t)
 
368
{
 
369
        if (t->visit_type != TREE_REGULAR)
 
370
                return;
 
371
 
 
372
        if (tree_current_is_physical_dir(t)) {
 
373
                tree_push(t, t->basename);
 
374
                t->stack->flags |= isDir;
 
375
        } else if (tree_current_is_dir(t)) {
 
376
                tree_push(t, t->basename);
 
377
                t->stack->flags |= isDirLink;
 
378
        }
 
379
}
 
380
 
 
381
/*
 
382
 * Get the stat() data for the entry just returned from tree_next().
 
383
 */
 
384
const struct stat *
 
385
tree_current_stat(struct tree *t)
 
386
{
 
387
        if (!(t->flags & hasStat)) {
 
388
                if (stat(t->basename, &t->st) != 0)
 
389
                        return NULL;
 
390
                t->flags |= hasStat;
 
391
        }
 
392
        return (&t->st);
 
393
}
 
394
 
 
395
/*
 
396
 * Get the lstat() data for the entry just returned from tree_next().
 
397
 */
 
398
const struct stat *
 
399
tree_current_lstat(struct tree *t)
 
400
{
 
401
        if (!(t->flags & hasLstat)) {
 
402
                if (lstat(t->basename, &t->lst) != 0)
 
403
                        return NULL;
 
404
                t->flags |= hasLstat;
 
405
        }
 
406
        return (&t->lst);
 
407
}
 
408
 
 
409
/*
 
410
 * Test whether current entry is a dir or link to a dir.
 
411
 */
 
412
int
 
413
tree_current_is_dir(struct tree *t)
 
414
{
 
415
        const struct stat *st;
 
416
 
 
417
        /*
 
418
         * If we already have lstat() info, then try some
 
419
         * cheap tests to determine if this is a dir.
 
420
         */
 
421
        if (t->flags & hasLstat) {
 
422
                /* If lstat() says it's a dir, it must be a dir. */
 
423
                if (S_ISDIR(tree_current_lstat(t)->st_mode))
 
424
                        return 1;
 
425
                /* Not a dir; might be a link to a dir. */
 
426
                /* If it's not a link, then it's not a link to a dir. */
 
427
                if (!S_ISLNK(tree_current_lstat(t)->st_mode))
 
428
                        return 0;
 
429
                /*
 
430
                 * It's a link, but we don't know what it's a link to,
 
431
                 * so we'll have to use stat().
 
432
                 */
 
433
        }
 
434
 
 
435
        st = tree_current_stat(t);
 
436
        /* If we can't stat it, it's not a dir. */
 
437
        if (st == NULL)
 
438
                return 0;
 
439
        /* Use the definitive test.  Hopefully this is cached. */
 
440
        return (S_ISDIR(st->st_mode));
 
441
}
 
442
 
 
443
/*
 
444
 * Test whether current entry is a physical directory.  Usually, we
 
445
 * already have at least one of stat() or lstat() in memory, so we
 
446
 * use tricks to try to avoid an extra trip to the disk.
 
447
 */
 
448
int
 
449
tree_current_is_physical_dir(struct tree *t)
 
450
{
 
451
        const struct stat *st;
 
452
 
 
453
        /*
 
454
         * If stat() says it isn't a dir, then it's not a dir.
 
455
         * If stat() data is cached, this check is free, so do it first.
 
456
         */
 
457
        if ((t->flags & hasStat)
 
458
            && (!S_ISDIR(tree_current_stat(t)->st_mode)))
 
459
                return 0;
 
460
 
 
461
        /*
 
462
         * Either stat() said it was a dir (in which case, we have
 
463
         * to determine whether it's really a link to a dir) or
 
464
         * stat() info wasn't available.  So we use lstat(), which
 
465
         * hopefully is already cached.
 
466
         */
 
467
 
 
468
        st = tree_current_lstat(t);
 
469
        /* If we can't stat it, it's not a dir. */
 
470
        if (st == NULL)
 
471
                return 0;
 
472
        /* Use the definitive test.  Hopefully this is cached. */
 
473
        return (S_ISDIR(st->st_mode));
 
474
}
 
475
 
 
476
/*
 
477
 * Test whether current entry is a symbolic link.
 
478
 */
 
479
int
 
480
tree_current_is_physical_link(struct tree *t)
 
481
{
 
482
        const struct stat *st = tree_current_lstat(t);
 
483
        if (st == NULL)
 
484
                return 0;
 
485
        return (S_ISLNK(st->st_mode));
 
486
}
 
487
 
 
488
/*
 
489
 * Return the access path for the entry just returned from tree_next().
 
490
 */
 
491
const char *
 
492
tree_current_access_path(struct tree *t)
 
493
{
 
494
        return (t->basename);
 
495
}
 
496
 
 
497
/*
 
498
 * Return the full path for the entry just returned from tree_next().
 
499
 */
 
500
const char *
 
501
tree_current_path(struct tree *t)
 
502
{
 
503
        return (t->buff);
 
504
}
 
505
 
 
506
/*
 
507
 * Return the length of the path for the entry just returned from tree_next().
 
508
 */
 
509
size_t
 
510
tree_current_pathlen(struct tree *t)
 
511
{
 
512
        return (t->path_length);
 
513
}
 
514
 
 
515
/*
 
516
 * Return the nesting depth of the entry just returned from tree_next().
 
517
 */
 
518
int
 
519
tree_current_depth(struct tree *t)
 
520
{
 
521
        return (t->depth);
 
522
}
 
523
 
 
524
/*
 
525
 * Terminate the traversal and release any resources.
 
526
 */
 
527
void
 
528
tree_close(struct tree *t)
 
529
{
 
530
        /* Release anything remaining in the stack. */
 
531
        while (t->stack != NULL)
 
532
                tree_pop(t);
 
533
        if (t->buff)
 
534
                free(t->buff);
 
535
        /* chdir() back to where we started. */
 
536
        if (t->initialDirFd >= 0) {
 
537
                fchdir(t->initialDirFd);
 
538
                close(t->initialDirFd);
 
539
                t->initialDirFd = -1;
 
540
        }
 
541
        free(t);
 
542
}