← Back to branch summary

~tplavcic/percona-xtrabackup/bld-26-2.0

« back to all changes in this revision

Viewing changes to src/libarchive/libarchive_fe/pathmatch.c

  • Committer: Alexey Kopytov
  • Date: 2012-02-10 20:05:56 UTC
  • 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/libarchive_fe/pathmatch.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
 *    in this position and unchanged.
 
11
 * 2. Redistributions in binary form must reproduce the above copyright
 
12
 *    notice, this list of conditions and the following disclaimer in the
 
13
 *    documentation and/or other materials provided with the distribution.
 
14
 *
 
15
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
 
16
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
17
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 
18
 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
 
19
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
20
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
21
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
22
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
23
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
24
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
25
 */
 
26
 
 
27
#include "lafe_platform.h"
 
28
__FBSDID("$FreeBSD$");
 
29
 
 
30
#ifdef HAVE_STRING_H
 
31
#include <string.h>
 
32
#endif
 
33
 
 
34
#include "pathmatch.h"
 
35
 
 
36
/*
 
37
 * Check whether a character 'c' is matched by a list specification [...]:
 
38
 *    * Leading '!' negates the class.
 
39
 *    * <char>-<char> is a range of characters
 
40
 *    * \<char> removes any special meaning for <char>
 
41
 *
 
42
 * Some interesting boundary cases:
 
43
 *   a-d-e is one range (a-d) followed by two single characters - and e.
 
44
 *   \a-\d is same as a-d
 
45
 *   a\-d is three single characters: a, d, -
 
46
 *   Trailing - is not special (so [a-] is two characters a and -).
 
47
 *   Initial - is not special ([a-] is same as [-a] is same as [\\-a])
 
48
 *   This function never sees a trailing \.
 
49
 *   [] always fails
 
50
 *   [!] always succeeds
 
51
 */
 
52
static int
 
53
pm_list(const char *start, const char *end, const char c, int flags)
 
54
{
 
55
        const char *p = start;
 
56
        char rangeStart = '\0', nextRangeStart;
 
57
        int match = 1, nomatch = 0;
 
58
 
 
59
        /* This will be used soon... */
 
60
        (void)flags; /* UNUSED */
 
61
 
 
62
        /* If this is a negated class, return success for nomatch. */
 
63
        if (*p == '!' && p < end) {
 
64
                match = 0;
 
65
                nomatch = 1;
 
66
                ++p;
 
67
        }
 
68
 
 
69
        while (p < end) {
 
70
                nextRangeStart = '\0';
 
71
                switch (*p) {
 
72
                case '-':
 
73
                        /* Trailing or initial '-' is not special. */
 
74
                        if ((rangeStart == '\0') || (p == end - 1)) {
 
75
                                if (*p == c)
 
76
                                        return (match);
 
77
                        } else {
 
78
                                char rangeEnd = *++p;
 
79
                                if (rangeEnd == '\\')
 
80
                                        rangeEnd = *++p;
 
81
                                if ((rangeStart <= c) && (c <= rangeEnd))
 
82
                                        return (match);
 
83
                        }
 
84
                        break;
 
85
                case '\\':
 
86
                        ++p;
 
87
                        /* Fall through */
 
88
                default:
 
89
                        if (*p == c)
 
90
                                return (match);
 
91
                        nextRangeStart = *p; /* Possible start of range. */
 
92
                }
 
93
                rangeStart = nextRangeStart;
 
94
                ++p;
 
95
        }
 
96
        return (nomatch);
 
97
}
 
98
 
 
99
/*
 
100
 * If s is pointing to "./", ".//", "./././" or the like, skip it.
 
101
 */
 
102
static const char *
 
103
pm_slashskip(const char *s) {
 
104
        while ((*s == '/')
 
105
            || (s[0] == '.' && s[1] == '/')
 
106
            || (s[0] == '.' && s[1] == '\0'))
 
107
                ++s;
 
108
        return (s);
 
109
}
 
110
 
 
111
static int
 
112
pm(const char *p, const char *s, int flags)
 
113
{
 
114
        const char *end;
 
115
 
 
116
        /*
 
117
         * Ignore leading './', './/', '././', etc.
 
118
         */
 
119
        if (s[0] == '.' && s[1] == '/')
 
120
                s = pm_slashskip(s + 1);
 
121
        if (p[0] == '.' && p[1] == '/')
 
122
                p = pm_slashskip(p + 1);
 
123
 
 
124
        for (;;) {
 
125
                switch (*p) {
 
126
                case '\0':
 
127
                        if (s[0] == '/') {
 
128
                                if (flags & PATHMATCH_NO_ANCHOR_END)
 
129
                                        return (1);
 
130
                                /* "dir" == "dir/" == "dir/." */
 
131
                                s = pm_slashskip(s);
 
132
                        }
 
133
                        return (*s == '\0');
 
134
                case '?':
 
135
                        /* ? always succeds, unless we hit end of 's' */
 
136
                        if (*s == '\0')
 
137
                                return (0);
 
138
                        break;
 
139
                case '*':
 
140
                        /* "*" == "**" == "***" ... */
 
141
                        while (*p == '*')
 
142
                                ++p;
 
143
                        /* Trailing '*' always succeeds. */
 
144
                        if (*p == '\0')
 
145
                                return (1);
 
146
                        while (*s) {
 
147
                                if (lafe_pathmatch(p, s, flags))
 
148
                                        return (1);
 
149
                                ++s;
 
150
                        }
 
151
                        return (0);
 
152
                case '[':
 
153
                        /*
 
154
                         * Find the end of the [...] character class,
 
155
                         * ignoring \] that might occur within the class.
 
156
                         */
 
157
                        end = p + 1;
 
158
                        while (*end != '\0' && *end != ']') {
 
159
                                if (*end == '\\' && end[1] != '\0')
 
160
                                        ++end;
 
161
                                ++end;
 
162
                        }
 
163
                        if (*end == ']') {
 
164
                                /* We found [...], try to match it. */
 
165
                                if (!pm_list(p + 1, end, *s, flags))
 
166
                                        return (0);
 
167
                                p = end; /* Jump to trailing ']' char. */
 
168
                                break;
 
169
                        } else
 
170
                                /* No final ']', so just match '['. */
 
171
                                if (*p != *s)
 
172
                                        return (0);
 
173
                        break;
 
174
                case '\\':
 
175
                        /* Trailing '\\' matches itself. */
 
176
                        if (p[1] == '\0') {
 
177
                                if (*s != '\\')
 
178
                                        return (0);
 
179
                        } else {
 
180
                                ++p;
 
181
                                if (*p != *s)
 
182
                                        return (0);
 
183
                        }
 
184
                        break;
 
185
                case '/':
 
186
                        if (*s != '/' && *s != '\0')
 
187
                                return (0);
 
188
                        /* Note: pattern "/\./" won't match "/";
 
189
                         * pm_slashskip() correctly stops at backslash. */
 
190
                        p = pm_slashskip(p);
 
191
                        s = pm_slashskip(s);
 
192
                        if (*p == '\0' && (flags & PATHMATCH_NO_ANCHOR_END))
 
193
                                return (1);
 
194
                        --p; /* Counteract the increment below. */
 
195
                        --s;
 
196
                        break;
 
197
                case '$':
 
198
                        /* '$' is special only at end of pattern and only
 
199
                         * if PATHMATCH_NO_ANCHOR_END is specified. */
 
200
                        if (p[1] == '\0' && (flags & PATHMATCH_NO_ANCHOR_END)){
 
201
                                /* "dir" == "dir/" == "dir/." */
 
202
                                return (*pm_slashskip(s) == '\0');
 
203
                        }
 
204
                        /* Otherwise, '$' is not special. */
 
205
                        /* FALL THROUGH */
 
206
                default:
 
207
                        if (*p != *s)
 
208
                                return (0);
 
209
                        break;
 
210
                }
 
211
                ++p;
 
212
                ++s;
 
213
        }
 
214
}
 
215
 
 
216
/* Main entry point. */
 
217
int
 
218
lafe_pathmatch(const char *p, const char *s, int flags)
 
219
{
 
220
        /* Empty pattern only matches the empty string. */
 
221
        if (p == NULL || *p == '\0')
 
222
                return (s == NULL || *s == '\0');
 
223
 
 
224
        /* Leading '^' anchors the start of the pattern. */
 
225
        if (*p == '^') {
 
226
                ++p;
 
227
                flags &= ~PATHMATCH_NO_ANCHOR_START;
 
228
        }
 
229
 
 
230
        if (*p == '/' && *s != '/')
 
231
                return (0);
 
232
 
 
233
        /* Certain patterns and file names anchor implicitly. */
 
234
        if (*p == '*' || *p == '/' || *p == '/') {
 
235
                while (*p == '/')
 
236
                        ++p;
 
237
                while (*s == '/')
 
238
                        ++s;
 
239
                return (pm(p, s, flags));
 
240
        }
 
241
 
 
242
        /* If start is unanchored, try to match start of each path element. */
 
243
        if (flags & PATHMATCH_NO_ANCHOR_START) {
 
244
                for ( ; s != NULL; s = strchr(s, '/')) {
 
245
                        if (*s == '/')
 
246
                                s++;
 
247
                        if (pm(p, s, flags))
 
248
                                return (1);
 
249
                }
 
250
                return (0);
 
251
        }
 
252
 
 
253
        /* Default: Match from beginning. */
 
254
        return (pm(p, s, flags));
 
255
}