Mercurial > hg
annotate mercurial/mpatch.c @ 47072:4c041c71ec01
revlog: introduce an explicit tracking of what the revlog is about
Since the dawn of time, people have been forced to rely to lossy introspection
of the index filename to determine what the purpose and role of the revlog they
encounter is. This is hacky, error prone, inflexible, abstraction-leaky,
<insert-your-own-complaints-here>.
In f63299ee7e4d Raphaël introduced a new attribute to track this information:
`revlog_kind`. However it is initialized in an odd place and various instances
end up not having it set. In addition is only tracking some of the information
we end up having to introspect in various pieces of code.
So we add a new attribute that holds more data and is more strictly enforced.
This work is done in collaboration with Raphaël.
The `revlog_kind` one will be removed/adapted in the next changeset. We expect
to be able to clean up various existing piece of code and to simplify coming
work around the newer revlog format.
Differential Revision: https://phab.mercurial-scm.org/D10352
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Tue, 06 Apr 2021 05:20:24 +0200 |
parents | d4ba4d51f85f |
children |
rev | line source |
---|---|
72 | 1 /* |
2 mpatch.c - efficient binary patching for Mercurial | |
3 | |
4 This implements a patch algorithm that's O(m + nlog n) where m is the | |
5 size of the output and n is the number of patches. | |
6 | |
7 Given a list of binary patches, it unpacks each into a hunk list, | |
8 then combines the hunk lists with a treewise recursion to form a | |
9 single hunk list. This hunk list is then applied to the original | |
10 text. | |
11 | |
12 The text (or binary) fragments are copied directly from their source | |
13 Python objects into a preallocated output string to avoid the | |
14 allocation of intermediate Python objects. Working memory is about 2x | |
15 the total number of hunks. | |
16 | |
46819
d4ba4d51f85f
contributor: change mentions of mpm to olivia
Raphaël Gomès <rgomes@octobus.net>
parents:
41336
diff
changeset
|
17 Copyright 2005, 2006 Olivia Mackall <olivia@selenic.com> |
72 | 18 |
19 This software may be used and distributed according to the terms | |
20 of the GNU General Public License, incorporated herein by reference. | |
21 */ | |
22 | |
38190
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
23 #include <limits.h> |
72 | 24 #include <stdlib.h> |
25 #include <string.h> | |
2468
1ac0574f1768
mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents:
2083
diff
changeset
|
26 |
29444
284d742e5611
internals: move the bitmanipulation routines into its own file
Maciej Fijalkowski <fijall@gmail.com>
parents:
28782
diff
changeset
|
27 #include "bitmanipulation.h" |
29691
e9a0bcc9314d
mpatch: change Py_ssize_t to ssize_t in places that will be later copied
Maciej Fijalkowski <fijall@gmail.com>
parents:
29444
diff
changeset
|
28 #include "compat.h" |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
29 #include "mpatch.h" |
72 | 30 |
38190
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
31 /* VC9 doesn't include bool and lacks stdbool.h based on cext/util.h */ |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
32 #if defined(_MSC_VER) || __STDC_VERSION__ < 199901L |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
33 #define true 1 |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
34 #define false 0 |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
35 typedef unsigned char bool; |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
36 #else |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
37 #include <stdbool.h> |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
38 #endif |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
39 |
29741
9a1685c70db4
mpatch: change lalloc() to local function
Yuya Nishihara <yuya@tcha.org>
parents:
29740
diff
changeset
|
40 static struct mpatch_flist *lalloc(ssize_t size) |
72 | 41 { |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
42 struct mpatch_flist *a = NULL; |
72 | 43 |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
44 if (size < 1) { |
3138
cc856c4d91ca
mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents:
2859
diff
changeset
|
45 size = 1; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
46 } |
3138
cc856c4d91ca
mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents:
2859
diff
changeset
|
47 |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
48 a = (struct mpatch_flist *)malloc(sizeof(struct mpatch_flist)); |
128 | 49 if (a) { |
34633
347c0f4232e1
mpatch: re-wrap wide line with clang-format
Augie Fackler <augie@google.com>
parents:
29749
diff
changeset
|
50 a->base = (struct mpatch_frag *)malloc( |
347c0f4232e1
mpatch: re-wrap wide line with clang-format
Augie Fackler <augie@google.com>
parents:
29749
diff
changeset
|
51 sizeof(struct mpatch_frag) * size); |
2048
8f9660c568b8
Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1978
diff
changeset
|
52 if (a->base) { |
128 | 53 a->head = a->tail = a->base; |
2048
8f9660c568b8
Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1978
diff
changeset
|
54 return a; |
8f9660c568b8
Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1978
diff
changeset
|
55 } |
8f9660c568b8
Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1978
diff
changeset
|
56 free(a); |
128 | 57 } |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
58 return NULL; |
72 | 59 } |
60 | |
29693
b9b9f9a92481
mpatch: split mpatch into two files
Maciej Fijalkowski <fijall@gmail.com>
parents:
29692
diff
changeset
|
61 void mpatch_lfree(struct mpatch_flist *a) |
72 | 62 { |
128 | 63 if (a) { |
64 free(a->base); | |
65 free(a); | |
66 } | |
72 | 67 } |
68 | |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
69 static ssize_t lsize(struct mpatch_flist *a) |
72 | 70 { |
71 return a->tail - a->head; | |
72 } | |
73 | |
38190
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
74 /* add helper to add src and *dest iff it won't overflow */ |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
75 static inline bool safeadd(int src, int *dest) |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
76 { |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
77 if ((src > 0) == (*dest > 0)) { |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
78 if (*dest > 0) { |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
79 if (src > (INT_MAX - *dest)) { |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
80 return false; |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
81 } |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
82 } else { |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
83 if (src < (INT_MIN - *dest)) { |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
84 return false; |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
85 } |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
86 } |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
87 } |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
88 *dest += src; |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
89 return true; |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
90 } |
1ec4cb8cbc87
mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents:
38189
diff
changeset
|
91 |
38191
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
92 /* subtract src from dest and store result in dest */ |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
93 static inline bool safesub(int src, int *dest) |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
94 { |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
95 if (((src > 0) && (*dest < INT_MIN + src)) || |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
96 ((src < 0) && (*dest > INT_MAX + src))) { |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
97 return false; |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
98 } |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
99 *dest -= src; |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
100 return true; |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
101 } |
b8b253aec953
mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents:
38190
diff
changeset
|
102 |
72 | 103 /* move hunks in source that are less cut to dest, compensating |
104 for changes in offset. the last hunk may be split if necessary. | |
105 */ | |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
106 static int gather(struct mpatch_flist *dest, struct mpatch_flist *src, int cut, |
34800
761355833867
mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents:
34634
diff
changeset
|
107 int offset) |
72 | 108 { |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
109 struct mpatch_frag *d = dest->tail, *s = src->head; |
72 | 110 int postend, c, l; |
111 | |
112 while (s != src->tail) { | |
38192
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
113 int soffset = s->start; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
114 if (!safeadd(offset, &soffset)) { |
38192
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
115 break; /* add would overflow, oh well */ |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
116 } |
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
117 if (soffset >= cut) { |
82 | 118 break; /* we've gone far enough */ |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
119 } |
72 | 120 |
38192
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
121 postend = offset; |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
122 if (!safeadd(s->start, &postend) || |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
123 !safeadd(s->len, &postend)) { |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
124 break; |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
125 } |
72 | 126 if (postend <= cut) { |
127 /* save this hunk */ | |
38192
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
128 int tmp = s->start; |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
129 if (!safesub(s->end, &tmp)) { |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
130 break; |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
131 } |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
132 if (!safeadd(s->len, &tmp)) { |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
133 break; |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
134 } |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
135 if (!safeadd(tmp, &offset)) { |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
136 break; /* add would overflow, oh well */ |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
137 } |
72 | 138 *d++ = *s++; |
34634
2e08b69bcd29
mpatch: reflow two oddly formatted else blocks with clang-format
Augie Fackler <augie@google.com>
parents:
34633
diff
changeset
|
139 } else { |
72 | 140 /* break up this hunk */ |
38192
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
141 c = cut; |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
142 if (!safesub(offset, &c)) { |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
143 break; |
0b208c13781c
mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents:
38191
diff
changeset
|
144 } |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
145 if (s->end < c) { |
72 | 146 c = s->end; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
147 } |
72 | 148 l = cut - offset - s->start; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
149 if (s->len < l) { |
72 | 150 l = s->len; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
151 } |
72 | 152 |
153 offset += s->start + l - c; | |
154 | |
155 d->start = s->start; | |
156 d->end = c; | |
157 d->len = l; | |
158 d->data = s->data; | |
159 d++; | |
160 s->start = c; | |
161 s->len = s->len - l; | |
162 s->data = s->data + l; | |
163 | |
82 | 164 break; |
72 | 165 } |
166 } | |
167 | |
168 dest->tail = d; | |
169 src->head = s; | |
170 return offset; | |
171 } | |
172 | |
173 /* like gather, but with no output list */ | |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
174 static int discard(struct mpatch_flist *src, int cut, int offset) |
72 | 175 { |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
176 struct mpatch_frag *s = src->head; |
72 | 177 int postend, c, l; |
178 | |
179 while (s != src->tail) { | |
38193
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
180 int cmpcut = s->start; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
181 if (!safeadd(offset, &cmpcut)) { |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
182 break; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
183 } |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
184 if (cmpcut >= cut) { |
82 | 185 break; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
186 } |
72 | 187 |
38193
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
188 postend = offset; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
189 if (!safeadd(s->start, &postend)) { |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
190 break; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
191 } |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
192 if (!safeadd(s->len, &postend)) { |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
193 break; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
194 } |
72 | 195 if (postend <= cut) { |
38193
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
196 /* do the subtraction first to avoid UB integer overflow |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
197 */ |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
198 int tmp = s->start; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
199 if (!safesub(s->end, &tmp)) { |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
200 break; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
201 } |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
202 if (!safeadd(s->len, &tmp)) { |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
203 break; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
204 } |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
205 if (!safeadd(tmp, &offset)) { |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
206 break; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
207 } |
72 | 208 s++; |
34634
2e08b69bcd29
mpatch: reflow two oddly formatted else blocks with clang-format
Augie Fackler <augie@google.com>
parents:
34633
diff
changeset
|
209 } else { |
38193
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
210 c = cut; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
211 if (!safesub(offset, &c)) { |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
212 break; |
7f22ef3c0ee7
mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents:
38192
diff
changeset
|
213 } |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
214 if (s->end < c) { |
72 | 215 c = s->end; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
216 } |
72 | 217 l = cut - offset - s->start; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
218 if (s->len < l) { |
72 | 219 l = s->len; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
220 } |
72 | 221 |
222 offset += s->start + l - c; | |
223 s->start = c; | |
224 s->len = s->len - l; | |
225 s->data = s->data + l; | |
226 | |
82 | 227 break; |
72 | 228 } |
229 } | |
230 | |
231 src->head = s; | |
232 return offset; | |
233 } | |
234 | |
235 /* combine hunk lists a and b, while adjusting b for offset changes in a/ | |
236 this deletes a and b and returns the resultant list. */ | |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
237 static struct mpatch_flist *combine(struct mpatch_flist *a, |
34800
761355833867
mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents:
34634
diff
changeset
|
238 struct mpatch_flist *b) |
72 | 239 { |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
240 struct mpatch_flist *c = NULL; |
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
241 struct mpatch_frag *bh, *ct; |
72 | 242 int offset = 0, post; |
243 | |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
244 if (a && b) { |
128 | 245 c = lalloc((lsize(a) + lsize(b)) * 2); |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
246 } |
128 | 247 |
248 if (c) { | |
72 | 249 |
128 | 250 for (bh = b->head; bh != b->tail; bh++) { |
251 /* save old hunks */ | |
252 offset = gather(c, a, bh->start, offset); | |
72 | 253 |
128 | 254 /* discard replaced hunks */ |
255 post = discard(a, bh->end, offset); | |
72 | 256 |
128 | 257 /* insert new hunk */ |
258 ct = c->tail; | |
38195
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
259 ct->start = bh->start; |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
260 ct->end = bh->end; |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
261 if (!safesub(offset, &(ct->start)) || |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
262 !safesub(post, &(ct->end))) { |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
263 /* It was already possible to exit |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
264 * this function with a return value |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
265 * of NULL before the safesub()s were |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
266 * added, so this should be fine. */ |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
267 mpatch_lfree(c); |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
268 c = NULL; |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
269 goto done; |
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
270 } |
128 | 271 ct->len = bh->len; |
272 ct->data = bh->data; | |
273 c->tail++; | |
274 offset = post; | |
275 } | |
276 | |
277 /* hold on to tail from a */ | |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
278 memcpy(c->tail, a->head, sizeof(struct mpatch_frag) * lsize(a)); |
128 | 279 c->tail += lsize(a); |
72 | 280 } |
38195
9c5ced5276d6
mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents:
38194
diff
changeset
|
281 done: |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
282 mpatch_lfree(a); |
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
283 mpatch_lfree(b); |
72 | 284 return c; |
285 } | |
286 | |
287 /* decode a binary patch into a hunk list */ | |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
288 int mpatch_decode(const char *bin, ssize_t len, struct mpatch_flist **res) |
72 | 289 { |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
290 struct mpatch_flist *l; |
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
291 struct mpatch_frag *lt; |
20167
09e41ac6289d
mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16758
diff
changeset
|
292 int pos = 0; |
72 | 293 |
294 /* assume worst case size, we won't have many of these lists */ | |
28656
b6ed2505d6cf
parsers: fix list sizing rounding error (SEC)
Matt Mackall <mpm@selenic.com>
parents:
20167
diff
changeset
|
295 l = lalloc(len / 12 + 1); |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
296 if (!l) { |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
297 return MPATCH_ERR_NO_MEM; |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
298 } |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
299 |
72 | 300 lt = l->tail; |
301 | |
38187
90a274965de7
mpatch: be more careful about parsing binary patch data (SEC)
Augie Fackler <augie@google.com>
parents:
34801
diff
changeset
|
302 /* We check against len-11 to ensure we have at least 12 bytes |
90a274965de7
mpatch: be more careful about parsing binary patch data (SEC)
Augie Fackler <augie@google.com>
parents:
34801
diff
changeset
|
303 left in the patch so we can read our three be32s out of it. */ |
90a274965de7
mpatch: be more careful about parsing binary patch data (SEC)
Augie Fackler <augie@google.com>
parents:
34801
diff
changeset
|
304 while (pos >= 0 && pos < (len - 11)) { |
20167
09e41ac6289d
mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16758
diff
changeset
|
305 lt->start = getbe32(bin + pos); |
09e41ac6289d
mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16758
diff
changeset
|
306 lt->end = getbe32(bin + pos + 4); |
09e41ac6289d
mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16758
diff
changeset
|
307 lt->len = getbe32(bin + pos + 8); |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
308 if (lt->start < 0 || lt->start > lt->end || lt->len < 0) { |
28657
b9714d958e89
parsers: detect short records (SEC)
Matt Mackall <mpm@selenic.com>
parents:
28656
diff
changeset
|
309 break; /* sanity check */ |
41336
763b45bc4483
cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents:
38195
diff
changeset
|
310 } |
38194
59837a16896d
mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents:
38193
diff
changeset
|
311 if (!safeadd(12, &pos)) { |
59837a16896d
mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents:
38193
diff
changeset
|
312 break; |
59837a16896d
mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents:
38193
diff
changeset
|
313 } |
59837a16896d
mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents:
38193
diff
changeset
|
314 lt->data = bin + pos; |
59837a16896d
mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents:
38193
diff
changeset
|
315 if (!safeadd(lt->len, &pos)) { |
59837a16896d
mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents:
38193
diff
changeset
|
316 break; |
59837a16896d
mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents:
38193
diff
changeset
|
317 } |
72 | 318 lt++; |
319 } | |
320 | |
20167
09e41ac6289d
mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents:
16758
diff
changeset
|
321 if (pos != len) { |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
322 mpatch_lfree(l); |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
323 return MPATCH_ERR_CANNOT_BE_DECODED; |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
324 } |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
325 |
72 | 326 l->tail = lt; |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
327 *res = l; |
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
328 return 0; |
72 | 329 } |
330 | |
331 /* calculate the size of resultant text */ | |
29693
b9b9f9a92481
mpatch: split mpatch into two files
Maciej Fijalkowski <fijall@gmail.com>
parents:
29692
diff
changeset
|
332 ssize_t mpatch_calcsize(ssize_t len, struct mpatch_flist *l) |
72 | 333 { |
29691
e9a0bcc9314d
mpatch: change Py_ssize_t to ssize_t in places that will be later copied
Maciej Fijalkowski <fijall@gmail.com>
parents:
29444
diff
changeset
|
334 ssize_t outlen = 0, last = 0; |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
335 struct mpatch_frag *f = l->head; |
72 | 336 |
337 while (f != l->tail) { | |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
338 if (f->start < last || f->end > len) { |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
339 return MPATCH_ERR_INVALID_PATCH; |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
340 } |
72 | 341 outlen += f->start - last; |
342 last = f->end; | |
343 outlen += f->len; | |
344 f++; | |
345 } | |
346 | |
347 outlen += len - last; | |
348 return outlen; | |
349 } | |
350 | |
29693
b9b9f9a92481
mpatch: split mpatch into two files
Maciej Fijalkowski <fijall@gmail.com>
parents:
29692
diff
changeset
|
351 int mpatch_apply(char *buf, const char *orig, ssize_t len, |
34800
761355833867
mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents:
34634
diff
changeset
|
352 struct mpatch_flist *l) |
72 | 353 { |
29692
6b3a8d034b69
mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents:
29691
diff
changeset
|
354 struct mpatch_frag *f = l->head; |
72 | 355 int last = 0; |
356 char *p = buf; | |
357 | |
358 while (f != l->tail) { | |
38189
faa924469635
mpatch: ensure fragment start isn't past the end of orig (SEC)
Augie Fackler <augie@google.com>
parents:
38188
diff
changeset
|
359 if (f->start < last || f->start > len || f->end > len || |
faa924469635
mpatch: ensure fragment start isn't past the end of orig (SEC)
Augie Fackler <augie@google.com>
parents:
38188
diff
changeset
|
360 last < 0) { |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
361 return MPATCH_ERR_INVALID_PATCH; |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
362 } |
72 | 363 memcpy(p, orig + last, f->start - last); |
364 p += f->start - last; | |
365 memcpy(p, f->data, f->len); | |
366 last = f->end; | |
367 p += f->len; | |
368 f++; | |
369 } | |
38188
1acfc35d478c
mpatch: protect against underflow in mpatch_apply (SEC)
Augie Fackler <augie@google.com>
parents:
38187
diff
changeset
|
370 if (last < 0) { |
1acfc35d478c
mpatch: protect against underflow in mpatch_apply (SEC)
Augie Fackler <augie@google.com>
parents:
38187
diff
changeset
|
371 return MPATCH_ERR_INVALID_PATCH; |
1acfc35d478c
mpatch: protect against underflow in mpatch_apply (SEC)
Augie Fackler <augie@google.com>
parents:
38187
diff
changeset
|
372 } |
72 | 373 memcpy(p, orig + last, len - last); |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
374 return 0; |
72 | 375 } |
376 | |
377 /* recursively generate a patch of all bins between start and end */ | |
34800
761355833867
mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents:
34634
diff
changeset
|
378 struct mpatch_flist * |
761355833867
mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents:
34634
diff
changeset
|
379 mpatch_fold(void *bins, struct mpatch_flist *(*get_next_item)(void *, ssize_t), |
761355833867
mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents:
34634
diff
changeset
|
380 ssize_t start, ssize_t end) |
72 | 381 { |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
382 ssize_t len; |
72 | 383 |
384 if (start + 1 == end) { | |
385 /* trivial case, output a decoded list */ | |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
386 return get_next_item(bins, start); |
72 | 387 } |
388 | |
389 /* divide and conquer, memory management is elsewhere */ | |
390 len = (end - start) / 2; | |
29694
55dd12204b8e
mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents:
29693
diff
changeset
|
391 return combine(mpatch_fold(bins, get_next_item, start, start + len), |
34801
1f4249c764f1
mpatch: switch alignment of wrapped line from tab to spaces with clang-format
Augie Fackler <augie@google.com>
parents:
34800
diff
changeset
|
392 mpatch_fold(bins, get_next_item, start + len, end)); |
72 | 393 } |