Contents of /xml/htdocs/proj/en/glep/glep-0025.html

Parent Directory Parent Directory | Revision Log Revision Log

Revision 1.2 - (show annotations) (download) (as text)
Thu Nov 11 21:34:45 2004 UTC (13 years, 7 months ago) by g2boojum
Branch: MAIN
Changes since 1.1: +49 -44 lines
File MIME type: text/html

1 <?xml version="1.0" encoding="utf-8" ?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
4 <!--
5 This HTML is auto-generated. DO NOT EDIT THIS FILE! If you are writing a new
6 PEP, see http://www.python.org/peps/pep-0001.html for instructions and links
8 -->
9 <head>
10 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
11 <meta name="generator" content="Docutils 0.3.3: http://docutils.sourceforge.net/" />
12 <title>GLEP 25 -- Distfile Patching Support</title>
13 <link rel="stylesheet" href="tools/glep.css" type="text/css" />
14 </head>
15 <body bgcolor="white">
16 <table class="navigation" cellpadding="0" cellspacing="0"
17 width="100%" border="0">
18 <tr><td class="navicon" width="150" height="35">
19 <a href="http://www.gentoo.org/" title="Gentoo Linux Home Page">
20 <img src="http://www.gentoo.org/images/gentoo-new.gif" alt="[Gentoo]"
21 border="0" width="150" height="35" /></a></td>
22 <td class="textlinks" align="left">
23 [<b><a href="http://www.gentoo.org/">Gentoo Linux Home</a></b>]
24 [<b><a href="http://www.gentoo.org/proj/en/glep">GLEP Index</a></b>]
25 [<b><a href="./glep-0025.txt">GLEP Source</a></b>]
26 </td></tr></table>
27 <div class="document">
28 <table class="rfc2822 field-list" frame="void" rules="none">
29 <col class="field-name" />
30 <col class="field-body" />
31 <tbody valign="top">
32 <tr class="field"><th class="field-name">GLEP:</th><td class="field-body">25</td>
33 </tr>
34 <tr class="field"><th class="field-name">Title:</th><td class="field-body">Distfile Patching Support</td>
35 </tr>
36 <tr class="field"><th class="field-name">Version:</th><td class="field-body">1.2</td>
37 </tr>
38 <tr class="field"><th class="field-name">Last-Modified:</th><td class="field-body"><a class="reference" href="http://www.gentoo.org/cgi-bin/viewcvs/xml/htdocs/proj/en/glep/glep-0025.txt?cvsroot=gentoo">2004/11/11 21:34:36</a></td>
39 </tr>
40 <tr class="field"><th class="field-name">Author:</th><td class="field-body">Brian Harring &lt;ferringb&#32;&#97;t&#32;gentoo.org&gt;</td>
41 </tr>
42 <tr class="field"><th class="field-name">Status:</th><td class="field-body">deferred</td>
43 </tr>
44 <tr class="field"><th class="field-name">Type:</th><td class="field-body">Standards Track</td>
45 </tr>
46 <tr class="field"><th class="field-name">Content-Type:</th><td class="field-body"><a class="reference" href="glep-0012.html">text/x-rst</a></td>
47 </tr>
48 <tr class="field"><th class="field-name">Created:</th><td class="field-body">6-Mar-2004</td>
49 </tr>
50 <tr class="field"><th class="field-name">Post-History:</th><td class="field-body">4-Apr-2004, 11-Nov-2004</td>
51 </tr>
52 </tbody>
53 </table>
54 <hr />
55 <div class="contents topic" id="contents">
56 <p class="topic-title first"><a name="contents">Contents</a></p>
57 <ul class="simple">
58 <li><a class="reference" href="#abstract" id="id7" name="id7">Abstract</a></li>
59 <li><a class="reference" href="#status" id="id8" name="id8">Status</a></li>
60 <li><a class="reference" href="#motivation" id="id9" name="id9">Motivation</a></li>
61 <li><a class="reference" href="#binary-patches-vs-gnudiff-patches" id="id10" name="id10">Binary patches vs GNUDiff patches</a></li>
62 <li><a class="reference" href="#rationale" id="id11" name="id11">Rationale</a></li>
63 <li><a class="reference" href="#specification" id="id12" name="id12">Specification</a><ul>
64 <li><a class="reference" href="#additions-to-the-tree" id="id13" name="id13">Additions to the tree</a></li>
65 <li><a class="reference" href="#portage-implementation" id="id14" name="id14">Portage Implementation</a><ul>
66 <li><a class="reference" href="#fetching" id="id15" name="id15">Fetching</a></li>
67 <li><a class="reference" href="#reconstruction" id="id16" name="id16">Reconstruction</a></li>
68 <li><a class="reference" href="#compressed-md5sums" id="id17" name="id17">Compressed MD5sums:</a><ul>
69 <li><a class="reference" href="#the-problem-in-detail" id="id18" name="id18">The Problem in Detail</a></li>
70 <li><a class="reference" href="#the-proposed-solution" id="id19" name="id19">The Proposed Solution</a></li>
71 </ul>
72 </li>
73 </ul>
74 </li>
75 <li><a class="reference" href="#distfile-mirror-additions" id="id20" name="id20">Distfile Mirror Additions</a></li>
76 <li><a class="reference" href="#patch-creation" id="id21" name="id21">Patch Creation</a></li>
77 </ul>
78 </li>
79 <li><a class="reference" href="#backwards-compatability" id="id22" name="id22">Backwards Compatability</a></li>
80 <li><a class="reference" href="#reference-implementation" id="id23" name="id23">Reference Implementation</a></li>
81 <li><a class="reference" href="#references" id="id24" name="id24">References</a></li>
82 <li><a class="reference" href="#copyright" id="id25" name="id25">Copyright</a></li>
83 </ul>
84 </div>
85 <div class="section" id="abstract">
86 <h1><a class="toc-backref" href="#id7" name="abstract">Abstract</a></h1>
87 <p>The intention of this GLEP is to propose the creation of patching support for
88 portage, and iron out the implementation details.</p>
89 </div>
90 <div class="section" id="status">
91 <h1><a class="toc-backref" href="#id8" name="status">Status</a></h1>
92 <p>Timed out</p>
93 </div>
94 <div class="section" id="motivation">
95 <h1><a class="toc-backref" href="#id9" name="motivation">Motivation</a></h1>
96 <p>Reduce the bandwidth load placed on our mirrors by decreasing the amount of
97 bytes transferred when upgrading between versions. Side benefit of this is to
98 significantly decrease the download requirements for users lacking broadband.</p>
99 </div>
100 <div class="section" id="binary-patches-vs-gnudiff-patches">
101 <h1><a class="toc-backref" href="#id10" name="binary-patches-vs-gnudiff-patches">Binary patches vs GNUDiff patches</a></h1>
102 <p>Most people are familiar with diff patches (unified diff for example)- this
103 glep is specifically proposing the use of an actual binary differencer. The
104 reason for this is that diff patches are line based- you change a single
105 character in a line, and the whole line must be included in the patch. Binary
106 differencers work at the byte level- it encodes just that byte. In that
107 respect binary patches are often much more efficient then diff patches.</p>
108 <p>Further, the ability to reverse a unified patch is due to the fact the diff
109 includes <strong>both</strong> the original line, and the modified line. The author isn't
110 aware of any binary differencer that is able to create patches the can be
111 reversed- basically they're unidirectional, the patch that is generated can
112 only be used to upgrade or downgrade the version, not both. The plus side of
113 this limitation is a significantly decreased patch size.</p>
114 <p>The choice of binary patches over diff patches pretty much comes down to the
115 fact they're smaller- example being a kdelibs binary patch for 3.1.4-&gt;3.1.5 is
116 75kb, the equivalent diff patch is 123kb, and is unable to result in a correct
117 md5 <a class="footnote-reference" href="#id4" id="id1" name="id1">[1]</a>.</p>
118 <p>Currently, this glep is proposing only the usage of binary patches- that's not
119 to say (with a fair amount of work) it couldn't be extended to support
120 standard diffs.</p>
121 </div>
122 <div class="section" id="rationale">
123 <h1><a class="toc-backref" href="#id11" name="rationale">Rationale</a></h1>
124 <p>The difference between source releases typically isn't very large, especially
125 for minor releases. As an example, kdelibs-3.1.4.tar.bz2 is 10.53 MB, and
126 kdelibs-3.1.5.tar.bz2 is 10.54 MB. A bzip2'ed patch between those versions is
127 75.6 kb <a class="footnote-reference" href="#id5" id="id2" name="id2">[2]</a>, less then 1% the size of 3.1.5's tbz2.</p>
128 </div>
129 <div class="section" id="specification">
130 <h1><a class="toc-backref" href="#id12" name="specification">Specification</a></h1>
131 <p>Quite a few sections of gentoo are affected- mirroring, the portage tree, and
132 portage itself.</p>
133 <div class="section" id="additions-to-the-tree">
134 <h2><a class="toc-backref" href="#id13" name="additions-to-the-tree">Additions to the tree</a></h2>
135 <p>For adding patch info into the tree, this glep proposes a global patch list
136 (stored in profiles as patches.global), and individual patch lists stored in
137 relevant package directories (named patches). Using the kernel packages as an
138 example, a global list of patches enables us to create a patch once, add an
139 entry, and have all kernel packages benefit from that single entry. Both
140 patches.global, and individual package patch files share the same format:</p>
141 <pre class="literal-block">
142 MD5 md5-value patch-url size MD5 md5-value ref-file size UMD5 md5-value new-file size
143 </pre>
144 <p>For those familiar with digest file layout, this should look familiar.
145 Essentially, chksum type, value, filename, size. The UMD5 chksum type is just
146 the uncompressed md5/size of the file- so if the UMD5 were for a bzip2
147 compressed file, it would be the md5 value/size of the uncompressed file.
148 And an example:</p>
149 <pre class="literal-block">
150 MD5 ccd5411b3558326cbce0306fcae32e26 http://dev.gentoo.org/~ferringb/patches/kdelibs-3.1.4-3.1.5.patch.bz2 75687 MD5 82c265de78d53c7060a09c5cb1a78942 kdelibs-3.1.4.tar.bz2 10537433 UMD5 0b1908a51e739c07ff5a88e189d2f7a9 kdelibs-3.1.5.tar.bz2 48056320
151 </pre>
152 <p>In the above example, the md5sum of
153 <a class="reference" href="http://dev.gentoo.org/~ferringb/patches/kdelibs-3.1.4-3.1.5.patch.bz2">http://dev.gentoo.org/~ferringb/patches/kdelibs-3.1.4-3.1.5.patch.bz2</a> is
154 calculated, compared to the stored value, and then the file size is checked.
155 The one difference is the UMD5 checksum type- the md5 value and the size are
156 specific to the <em>uncompressed</em> file. Continuing, for cases where the patch
157 will reside on one of our mirrors, the patch filename would be sufficient.</p>
158 <p>Finally, note that this is a unidirectional patch- using the above example,
159 kdelibs-3.1.4-3.1.5 can <strong>only</strong> be used to upgrade from 3.1.4 to 3.1.5, not
160 in reverse (originally explained in <a class="reference" href="#binary-patches-vs-gnudiff-patches">Binary patches vs GNUDiff patches</a>).</p>
161 </div>
162 <div class="section" id="portage-implementation">
163 <h2><a class="toc-backref" href="#id14" name="portage-implementation">Portage Implementation</a></h2>
164 <p>This glep proposes the patching support should be (at this stage) optional-
165 specifically, enabled via FEATURES=&quot;patching&quot;.</p>
166 <div class="section" id="fetching">
167 <h3><a class="toc-backref" href="#id15" name="fetching">Fetching</a></h3>
168 <p>When patching is enabled, the global patch list is read, and the packages
169 patch list is read. From there, portage determines what files could be used
170 as a base for patching to the desired file- further, determining if it's
171 actually worth patching (case where it wouldn't be is when the target file is
172 less then the sum of the patches needed). Any patches to be used are fetched,
173 and md5 verified.</p>
174 </div>
175 <div class="section" id="reconstruction">
176 <h3><a class="toc-backref" href="#id16" name="reconstruction">Reconstruction</a></h3>
177 <p>Upon fetching and md5 verification of patch(es), the desired file is
178 reconstructed. Assuming reconstruction didn't return any errors, the target
179 file has its uncompressed md5sum calculated and verified, then is recompressed
180 and the compressed md5sum calculated. At this point, if the compressed md5
181 matches the md5 stored in the tree, then portage transfers the file into
182 distfiles, and continues on it's merry way.</p>
183 <p>If the compressed md5 is different from the tree's value, then the (proposed)
184 md5 database is updated with new compressed md5. Details of this database
185 (and the issue it addresses) follow.</p>
186 </div>
187 <div class="section" id="compressed-md5sums">
188 <h3><a class="toc-backref" href="#id17" name="compressed-md5sums">Compressed MD5sums:</a></h3>
189 <p>There will be instances where a file is reconstructed perfectly, recompressed,
190 and the recompressed md5sum differs from what is stored in the tree- the
191 problem is that the md5sum of a compressed file is inherently tied to the
192 compressor version/options used to compress the original source.</p>
193 <div class="section" id="the-problem-in-detail">
194 <h4><a class="toc-backref" href="#id18" name="the-problem-in-detail">The Problem in Detail</a></h4>
195 <p>A good example of this problem is related to bzip2 versions used for
196 compression. Between bzip2 0.9x and bzip2 1.x, there was a subtle change in
197 the compressor resulting in a slightly better compression result- end result
198 being a different file, eg a different md5sum. Assuming compressor versions
199 are the same, there also is the issue of what compression level the target
200 source was originally compressed at- was it compressed with -9, -8 or -7?
201 That's just a sampling of the various original settings that must be accounted
202 for, and that's limited to gzip/bzip2; other compressors will add to the
203 number of variables to be accounted for to produce an exact recreation of the
204 compressed md5sum.</p>
205 <p>Tracking the compressor version and options originally used isn't really a
206 valid option- assuming all options were accounted for, clients would still be
207 required to have multiple versions of the same compressor installed just for
208 the sake of recreating a compressed md5sum <em>even though</em> the uncompressed
209 source's md5 has already been verified.</p>
210 </div>
211 <div class="section" id="the-proposed-solution">
212 <h4><a class="toc-backref" href="#id19" name="the-proposed-solution">The Proposed Solution</a></h4>
213 <p>The creation of a clientside flatfile/db of valid alternate md5/size pairs
214 would enable portage to handle perfectly reconstructed files, that have a
215 different md5sum due to compression differences. The proposed format is thus:</p>
216 <pre class="literal-block">
217 MD5 md5sum orig-file size MD5 md5sum [ optional new-name ] size
218 </pre>
219 <p>Example:</p>
220 <pre class="literal-block">
221 MD5 984146931906a7d53300b29f58f6a899 OOo_1.0.3_source.tar.bz2 165475319 MD5 0733dd85ed44d88d1eabed704d579721 165444187
222 </pre>
223 <p>An alternate md5/size pair for a file would be added <strong>only</strong> when the
224 uncompressed source's md5/size has been verified, yet upon recompression the
225 md5 differs. For cleansing of older md5/size pairs from this db, a utility
226 would be required- the author suggests the addition of a distfiles-cleaning
227 utility to portage, with the ability to also cleanse old md5/size pairs when
228 the file the pair was created for no longer exists in distfiles.</p>
229 <p>Where to store the database is debatable- /etc/portage or /var/cache/edb are
230 definite options.</p>
231 <p>The reasoning for allowing for an optional new-name is that it provides needed
232 functionality should anyone attempt to extend portage to allow for clients to
233 change the compression used for a source (eg, recompress all gzip files as
234 bzip2). Granted, no such code or attempt has been made, but nothing is lost
235 by leaving the option open should the request/attempt be made.</p>
236 <p>A potential gotcha of adding this support is that in environments where the
237 distfiles directory is shared out to multiple systems, this db must be shared
238 also.</p>
239 </div>
240 </div>
241 </div>
242 <div class="section" id="distfile-mirror-additions">
243 <h2><a class="toc-backref" href="#id20" name="distfile-mirror-additions">Distfile Mirror Additions</a></h2>
244 <p>One issue of contention is where these files will actually be stored. As of
245 the writing of this glep, a full distfiles mirror is roughly around 40 gb- a
246 rough estimate by the author places the space requirements for patches for
247 each version at a total of around 4gb. Note this isn't even remotely a hard
248 figure yet, and a better figure is being checked into currently.</p>
249 <p>Regardless of the exact space figure, finding a place to store the patches
250 will be problematic. Expansion of the required mirror space (essentially just
251 swallowing the patches storage requirement) is unlikely, since it was one of
252 the main arguements against the now defunct glep9 attempt <a class="footnote-reference" href="#id5" id="id3" name="id3">[2]</a>. A couple of
253 ideas that have been put forth to handle the additional space requirements are
254 as follows-</p>
255 <p>1) Identification of mirrors willing to handle the extra space requirements-
256 essentially create an additional patch mirror tier.</p>
257 <p>2) Mirroring only a patch for certain package versions, rather then full
258 source. Using kdelibs-3.1.5 as an example, only the patch would be mirrored
259 (rather then the full 10.53 MB source). Downside to this approach is that a
260 user who is downloading kdelibs for the first time would either need to pull
261 it from the original SRC_URI (placing the burden onto the upstream mirror), or
262 pull the 3.1.4 version, and the patch- pulling 63k more then if they had just
263 pulled the full version. The kdelibs 3.1.4/3.1.5 example is something of an
264 optimal case- not all versions will have such miniscule patches.</p>
265 <p>3) A variation on the idea above, essentially mirroring only the patch for
266 the oldest version(s) of a package; eg, kdelibs currently has version 3.05,
267 3.1.5, 3.2.0, and 3.2.1- the mirrors would only carry a patch for 3.05, not
268 full source (think RESTRICT=&quot;fetch&quot;). One plus to this is that patches to
269 downgrade in version are smaller then the patches to upgrade in version- there
270 are exceptions to this, but they're hard to find. A major downside to this
271 approach is A) a user would have to sync up to get the patchlists for that
272 version, B) creation of a set of patches to go backwards in version (see
273 <a class="reference" href="#binary-patches-vs-gnudiff-patches">Binary patches vs GNUDiff patches</a>)..</p>
274 <p>Of the options listed above, the first is the easiest, although the second
275 could be made to work. Feedback and any possible alternatives would be
276 greatly appreciated.</p>
277 </div>
278 <div class="section" id="patch-creation">
279 <h2><a class="toc-backref" href="#id21" name="patch-creation">Patch Creation</a></h2>
280 <p>Maintenance of patch lists, and the actual patch creation ought to be managed
281 by a high level script- essentally a dev says &quot;I want a patch between this
282 version, and that version: make it so&quot;, the script churns away
283 creating/updating the patch list, and generating the patch locally. The
284 utility next uploads the new patch to /space/distfiles-local on dev.gentoo.org
285 (exempting if it's not a locally generated patch), and repoman is used to
286 commit the updated patch list.</p>
287 <p>What would be preferable (although possibly wishful thinking), is if hardware
288 could be co-opted for automatic patch generation, rather then forcing it upon
289 the devs- something akin to how files are pulled onto the mirror automatically
290 for new ebuilds.</p>
291 <p>The initial bulk of patches to get will be generated by the author, to ease
292 the transition and offer patches for people to test out.</p>
293 </div>
294 </div>
295 <div class="section" id="backwards-compatability">
296 <h1><a class="toc-backref" href="#id22" name="backwards-compatability">Backwards Compatability</a></h1>
297 <p>As noted in <a class="reference" href="#the-proposed-solution">The Proposed Solution</a>, a system using patching and sharing out
298 it's distfiles must share out it's alternate md5 db. Any system that uses the
299 distfiles share must support the alternate md5 db also. If this is considered
300 enough of an issue, it is conceivable to place reconstructed sources with an
301 alternate md5 into a subdirectory of distdir- portage only looks within
302 distdir, unwilling to descend into subdirectories.</p>
303 <p>Also note that <a class="reference" href="#distfile-mirror-additions">Distfile Mirror Additions</a> may add additional backwards
304 compatability issues, depending on what solution is accepted.</p>
305 </div>
306 <div class="section" id="reference-implementation">
307 <h1><a class="toc-backref" href="#id23" name="reference-implementation">Reference Implementation</a></h1>
308 <p>TODO</p>
309 </div>
310 <div class="section" id="references">
311 <h1><a class="toc-backref" href="#id24" name="references">References</a></h1>
312 <table class="footnote" frame="void" id="id4" rules="none">
313 <colgroup><col class="label" /><col /></colgroup>
314 <tbody valign="top">
315 <tr><td class="label"><a class="fn-backref" href="#id1" name="id4">[1]</a></td><td><a class="reference" href="http://dev.gentoo.org/~ferringb/patches/kdelibs-3.1.4-3.1.5">http://dev.gentoo.org/~ferringb/patches/kdelibs-3.1.4-3.1.5</a>.{patch,diff}.bz2.</td></tr>
316 </tbody>
317 </table>
318 <table class="footnote" frame="void" id="id5" rules="none">
319 <colgroup><col class="label" /><col /></colgroup>
320 <tbody valign="top">
321 <tr><td class="label"><a name="id5">[2]</a></td><td><em>(<a class="fn-backref" href="#id2">1</a>, <a class="fn-backref" href="#id3">2</a>)</em> kdelibs-3.1.4-3.1.5.patch.bz2, switching format patch, created via diffball-0.4_pre4 (diffball is available at <a class="reference" href="http://sourceforge.net/projects/diffball">http://sourceforge.net/projects/diffball</a>)
322 Bzip2 -9 compressed, the patch is 75,687 bytes, uncompressed it is 337,649 bytes. The patch is available at <a class="reference" href="http://dev.gentoo.org/~ferringb/kdelibs-3.1.4-3.1.5.patch.bz2">http://dev.gentoo.org/~ferringb/kdelibs-3.1.4-3.1.5.patch.bz2</a> for those curious.</td></tr>
323 </tbody>
324 </table>
325 <table class="footnote" frame="void" id="id6" rules="none">
326 <colgroup><col class="label" /><col /></colgroup>
327 <tbody valign="top">
328 <tr><td class="label"><a name="id6">[3]</a></td><td>Glep9, 'Gentoo Package Update System'
329 (<a class="reference" href="http://glep.gentoo.org/glep-0009.html">http://glep.gentoo.org/glep-0009.html</a>)</td></tr>
330 </tbody>
331 </table>
332 </div>
333 <div class="section" id="copyright">
334 <h1><a class="toc-backref" href="#id25" name="copyright">Copyright</a></h1>
335 <p>This document has been placed in the public domain.</p>
336 </div>
337 </div>
339 <hr class="footer" />
340 <div class="footer">
341 <a class="reference" href="glep-0025.txt">View document source</a>.
342 Generated on: 2004-11-11 21:27 UTC.
343 Generated by <a class="reference" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
344 </div>
345 </body>
346 </html>

  ViewVC Help
Powered by ViewVC 1.1.20