/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/chunk_writer.py

  • Committer: Gustav Hartvigsson
  • Date: 2021-01-09 21:36:27 UTC
  • Revision ID: gustav.hartvigsson@gmail.com-20210109213627-h1xwcutzy9m7a99b
Added 'Case Preserving Working Tree Use Cases' from Canonical Wiki

* Addod a page from the Canonical Bazaar wiki
  with information on the scmeatics of case
  perserving filesystems an a case insensitive
  filesystem works.
  
  * Needs re-work, but this will do as it is the
    same inforamoton as what was on the linked
    page in the currint documentation.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/chunk_writer.py
 
1
# Copyright (C) 2008 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
#
 
17
 
 
18
"""ChunkWriter: write compressed data out with a fixed upper bound."""
 
19
 
 
20
import zlib
 
21
from zlib import Z_FINISH, Z_SYNC_FLUSH
 
22
 
 
23
 
 
24
class ChunkWriter(object):
 
25
    """ChunkWriter allows writing of compressed data with a fixed size.
 
26
 
 
27
    If less data is supplied than fills a chunk, the chunk is padded with
 
28
    NULL bytes. If more data is supplied, then the writer packs as much
 
29
    in as it can, but never splits any item it was given.
 
30
 
 
31
    The algorithm for packing is open to improvement! Current it is:
 
32
     - write the bytes given
 
33
     - if the total seen bytes so far exceeds the chunk size, flush.
 
34
 
 
35
    :cvar _max_repack: To fit the maximum number of entries into a node, we
 
36
        will sometimes start over and compress the whole list to get tighter
 
37
        packing. We get diminishing returns after a while, so this limits the
 
38
        number of times we will try.
 
39
        The default is to try to avoid recompressing entirely, but setting this
 
40
        to something like 20 will give maximum compression.
 
41
 
 
42
    :cvar _max_zsync: Another tunable nob. If _max_repack is set to 0, then you
 
43
        can limit the number of times we will try to pack more data into a
 
44
        node. This allows us to do a single compression pass, rather than
 
45
        trying until we overflow, and then recompressing again.
 
46
    """
 
47
    #    In testing, some values for bzr.dev::
 
48
    #        repack  time  MB   max   full
 
49
    #         1       7.5  4.6  1140  0
 
50
    #         2       8.4  4.2  1036  1
 
51
    #         3       9.8  4.1  1012  278
 
52
    #         4      10.8  4.1  728   945
 
53
    #        20      11.1  4.1  0     1012
 
54
    #        repack = 0
 
55
    #        zsync   time  MB    repack  stop_for_z
 
56
    #         0       5.0  24.7  0       6270
 
57
    #         1       4.3  13.2  0       3342
 
58
    #         2       4.9   9.6  0       2414
 
59
    #         5       4.8   6.2  0       1549
 
60
    #         6       4.8   5.8  1       1435
 
61
    #         7       4.8   5.5  19      1337
 
62
    #         8       4.4   5.3  81      1220
 
63
    #        10       5.3   5.0  260     967
 
64
    #        11       5.3   4.9  366     839
 
65
    #        12       5.1   4.8  454     731
 
66
    #        15       5.8   4.7  704     450
 
67
    #        20       5.8   4.6  1133    7
 
68
 
 
69
    #    In testing, some values for mysql-unpacked::
 
70
    #                next_bytes estim
 
71
    #        repack  time  MB    full    stop_for_repack
 
72
    #         1            15.4  0       3913
 
73
    #         2      35.4  13.7  0       346
 
74
    #        20      46.7  13.4  3380    0
 
75
    #        repack=0
 
76
    #        zsync                       stop_for_z
 
77
    #         0      29.5 116.5  0       29782
 
78
    #         1      27.8  60.2  0       15356
 
79
    #         2      27.8  42.4  0       10822
 
80
    #         5      26.8  25.5  0       6491
 
81
    #         6      27.3  23.2  13      5896
 
82
    #         7      27.5  21.6  29      5451
 
83
    #         8      27.1  20.3  52      5108
 
84
    #        10      29.4  18.6  195     4526
 
85
    #        11      29.2  18.0  421     4143
 
86
    #        12      28.0  17.5  702     3738
 
87
    #        15      28.9  16.5  1223    2969
 
88
    #        20      29.6  15.7  2182    1810
 
89
    #        30      31.4  15.4  3891    23
 
90
 
 
91
    # Tuple of (num_repack_attempts, num_zsync_attempts)
 
92
    # num_zsync_attempts only has meaning if num_repack_attempts is 0.
 
93
    _repack_opts_for_speed = (0, 8)
 
94
    _repack_opts_for_size = (20, 0)
 
95
 
 
96
    def __init__(self, chunk_size, reserved=0, optimize_for_size=False):
 
97
        """Create a ChunkWriter to write chunk_size chunks.
 
98
 
 
99
        :param chunk_size: The total byte count to emit at the end of the
 
100
            chunk.
 
101
        :param reserved: How many bytes to allow for reserved data. reserved
 
102
            data space can only be written to via the write(...,
 
103
            reserved=True).
 
104
        """
 
105
        self.chunk_size = chunk_size
 
106
        self.compressor = zlib.compressobj()
 
107
        self.bytes_in = []
 
108
        self.bytes_list = []
 
109
        self.bytes_out_len = 0
 
110
        # bytes that have been seen, but not included in a flush to out yet
 
111
        self.unflushed_in_bytes = 0
 
112
        self.num_repack = 0
 
113
        self.num_zsync = 0
 
114
        self.unused_bytes = None
 
115
        self.reserved_size = reserved
 
116
        # Default is to make building fast rather than compact
 
117
        self.set_optimize(for_size=optimize_for_size)
 
118
 
 
119
    def finish(self):
 
120
        """Finish the chunk.
 
121
 
 
122
        This returns the final compressed chunk, and either None, or the
 
123
        bytes that did not fit in the chunk.
 
124
 
 
125
        :return: (compressed_bytes, unused_bytes, num_nulls_needed)
 
126
 
 
127
            * compressed_bytes: a list of bytes that were output from the
 
128
              compressor. If the compressed length was not exactly chunk_size,
 
129
              the final string will be a string of all null bytes to pad this
 
130
              to chunk_size
 
131
            * unused_bytes: None, or the last bytes that were added, which we
 
132
              could not fit.
 
133
            * num_nulls_needed: How many nulls are padded at the end
 
134
        """
 
135
        self.bytes_in = None  # Free the data cached so far, we don't need it
 
136
        out = self.compressor.flush(Z_FINISH)
 
137
        self.bytes_list.append(out)
 
138
        self.bytes_out_len += len(out)
 
139
 
 
140
        if self.bytes_out_len > self.chunk_size:
 
141
            raise AssertionError('Somehow we ended up with too much'
 
142
                                 ' compressed data, %d > %d'
 
143
                                 % (self.bytes_out_len, self.chunk_size))
 
144
        nulls_needed = self.chunk_size - self.bytes_out_len
 
145
        if nulls_needed:
 
146
            self.bytes_list.append(b"\x00" * nulls_needed)
 
147
        return self.bytes_list, self.unused_bytes, nulls_needed
 
148
 
 
149
    def set_optimize(self, for_size=True):
 
150
        """Change how we optimize our writes.
 
151
 
 
152
        :param for_size: If True, optimize for minimum space usage, otherwise
 
153
            optimize for fastest writing speed.
 
154
        :return: None
 
155
        """
 
156
        if for_size:
 
157
            opts = ChunkWriter._repack_opts_for_size
 
158
        else:
 
159
            opts = ChunkWriter._repack_opts_for_speed
 
160
        self._max_repack, self._max_zsync = opts
 
161
 
 
162
    def _recompress_all_bytes_in(self, extra_bytes=None):
 
163
        """Recompress the current bytes_in, and optionally more.
 
164
 
 
165
        :param extra_bytes: Optional, if supplied we will add it with
 
166
            Z_SYNC_FLUSH
 
167
        :return: (bytes_out, bytes_out_len, alt_compressed)
 
168
 
 
169
            * bytes_out: is the compressed bytes returned from the compressor
 
170
            * bytes_out_len: the length of the compressed output
 
171
            * compressor: An object with everything packed in so far, and
 
172
              Z_SYNC_FLUSH called.
 
173
        """
 
174
        compressor = zlib.compressobj()
 
175
        bytes_out = []
 
176
        append = bytes_out.append
 
177
        compress = compressor.compress
 
178
        for accepted_bytes in self.bytes_in:
 
179
            out = compress(accepted_bytes)
 
180
            if out:
 
181
                append(out)
 
182
        if extra_bytes:
 
183
            out = compress(extra_bytes)
 
184
            out += compressor.flush(Z_SYNC_FLUSH)
 
185
            append(out)
 
186
        bytes_out_len = sum(map(len, bytes_out))
 
187
        return bytes_out, bytes_out_len, compressor
 
188
 
 
189
    def write(self, bytes, reserved=False):
 
190
        """Write some bytes to the chunk.
 
191
 
 
192
        If the bytes fit, False is returned. Otherwise True is returned
 
193
        and the bytes have not been added to the chunk.
 
194
 
 
195
        :param bytes: The bytes to include
 
196
        :param reserved: If True, we can use the space reserved in the
 
197
            constructor.
 
198
        """
 
199
        if self.num_repack > self._max_repack and not reserved:
 
200
            self.unused_bytes = bytes
 
201
            return True
 
202
        if reserved:
 
203
            capacity = self.chunk_size
 
204
        else:
 
205
            capacity = self.chunk_size - self.reserved_size
 
206
        comp = self.compressor
 
207
 
 
208
        # Check to see if the currently unflushed bytes would fit with a bit of
 
209
        # room to spare, assuming no compression.
 
210
        next_unflushed = self.unflushed_in_bytes + len(bytes)
 
211
        remaining_capacity = capacity - self.bytes_out_len - 10
 
212
        if (next_unflushed < remaining_capacity):
 
213
            # looks like it will fit
 
214
            out = comp.compress(bytes)
 
215
            if out:
 
216
                self.bytes_list.append(out)
 
217
                self.bytes_out_len += len(out)
 
218
            self.bytes_in.append(bytes)
 
219
            self.unflushed_in_bytes += len(bytes)
 
220
        else:
 
221
            # This may or may not fit, try to add it with Z_SYNC_FLUSH
 
222
            # Note: It is tempting to do this as a look-ahead pass, and to
 
223
            #       'copy()' the compressor before flushing. However, it seems
 
224
            #       that Which means that it is the same thing as increasing
 
225
            #       repack, similar cost, same benefit. And this way we still
 
226
            #       have the 'repack' knob that can be adjusted, and not depend
 
227
            #       on a platform-specific 'copy()' function.
 
228
            self.num_zsync += 1
 
229
            if self._max_repack == 0 and self.num_zsync > self._max_zsync:
 
230
                self.num_repack += 1
 
231
                self.unused_bytes = bytes
 
232
                return True
 
233
            out = comp.compress(bytes)
 
234
            out += comp.flush(Z_SYNC_FLUSH)
 
235
            self.unflushed_in_bytes = 0
 
236
            if out:
 
237
                self.bytes_list.append(out)
 
238
                self.bytes_out_len += len(out)
 
239
 
 
240
            # We are a bit extra conservative, because it seems that you *can*
 
241
            # get better compression with Z_SYNC_FLUSH than a full compress. It
 
242
            # is probably very rare, but we were able to trigger it.
 
243
            if self.num_repack == 0:
 
244
                safety_margin = 100
 
245
            else:
 
246
                safety_margin = 10
 
247
            if self.bytes_out_len + safety_margin <= capacity:
 
248
                # It fit, so mark it added
 
249
                self.bytes_in.append(bytes)
 
250
            else:
 
251
                # We are over budget, try to squeeze this in without any
 
252
                # Z_SYNC_FLUSH calls
 
253
                self.num_repack += 1
 
254
                (bytes_out, this_len,
 
255
                 compressor) = self._recompress_all_bytes_in(bytes)
 
256
                if self.num_repack >= self._max_repack:
 
257
                    # When we get *to* _max_repack, bump over so that the
 
258
                    # earlier > _max_repack will be triggered.
 
259
                    self.num_repack += 1
 
260
                if this_len + 10 > capacity:
 
261
                    (bytes_out, this_len,
 
262
                     compressor) = self._recompress_all_bytes_in()
 
263
                    self.compressor = compressor
 
264
                    # Force us to not allow more data
 
265
                    self.num_repack = self._max_repack + 1
 
266
                    self.bytes_list = bytes_out
 
267
                    self.bytes_out_len = this_len
 
268
                    self.unused_bytes = bytes
 
269
                    return True
 
270
                else:
 
271
                    # This fits when we pack it tighter, so use the new packing
 
272
                    self.compressor = compressor
 
273
                    self.bytes_in.append(bytes)
 
274
                    self.bytes_list = bytes_out
 
275
                    self.bytes_out_len = this_len
 
276
        return False