1 /*
2 * delta.c
3 *
4 * Copyright (c) 2006-2018 Pacman Development Team <pacman-dev@archlinux.org>
5 * Copyright (c) 2007-2006 by Judd Vinet <jvinet@zeroflux.org>
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include <stdlib.h>
22 #include <string.h>
23 #include <stdint.h> /* intmax_t */
24 #include <limits.h>
25 #include <sys/types.h>
26 #include <regex.h>
27
28 /* libalpm */
29 #include "delta.h"
30 #include "alpm_list.h"
31 #include "util.h"
32 #include "log.h"
33 #include "graph.h"
34
graph_init(alpm_list_t * deltas,int reverse)35 static alpm_list_t *graph_init(alpm_list_t *deltas, int reverse)
36 {
37 alpm_list_t *i, *j;
38 alpm_list_t *vertices = NULL;
39 /* create the vertices */
40 for(i = deltas; i; i = i->next) {
41 alpm_graph_t *v = _alpm_graph_new();
42 if(!v) {
43 alpm_list_free(vertices);
44 return NULL;
45 }
46 alpm_delta_t *vdelta = i->data;
47 vdelta->download_size = vdelta->delta_size;
48 v->weight = LONG_MAX;
49 v->data = vdelta;
50 vertices = alpm_list_add(vertices, v);
51 }
52
53 /* compute the edges */
54 for(i = vertices; i; i = i->next) {
55 alpm_graph_t *v_i = i->data;
56 alpm_delta_t *d_i = v_i->data;
57 /* loop a second time so we make all possible comparisons */
58 for(j = vertices; j; j = j->next) {
59 alpm_graph_t *v_j = j->data;
60 alpm_delta_t *d_j = v_j->data;
61 /* We want to create a delta tree like the following:
62 * 1_to_2
63 * |
64 * 1_to_3 2_to_3
65 * \ /
66 * 3_to_4
67 * If J 'from' is equal to I 'to', then J is a child of I.
68 * */
69 if((!reverse && strcmp(d_j->from, d_i->to) == 0) ||
70 (reverse && strcmp(d_j->to, d_i->from) == 0)) {
71 v_i->children = alpm_list_add(v_i->children, v_j);
72 }
73 }
74 v_i->iterator = v_i->children;
75 }
76 return vertices;
77 }
78
graph_init_size(alpm_handle_t * handle,alpm_list_t * vertices)79 static void graph_init_size(alpm_handle_t *handle, alpm_list_t *vertices)
80 {
81 alpm_list_t *i;
82
83 for(i = vertices; i; i = i->next) {
84 char *fpath, *md5sum;
85 alpm_graph_t *v = i->data;
86 alpm_delta_t *vdelta = v->data;
87
88 /* determine whether the delta file already exists */
89 fpath = _alpm_filecache_find(handle, vdelta->delta);
90 if(fpath) {
91 md5sum = alpm_compute_md5sum(fpath);
92 if(md5sum && strcmp(md5sum, vdelta->delta_md5) == 0) {
93 vdelta->download_size = 0;
94 }
95 FREE(md5sum);
96 FREE(fpath);
97 } else {
98 char *fnamepart;
99 CALLOC(fnamepart, strlen(vdelta->delta) + 6, sizeof(char), return);
100 sprintf(fnamepart, "%s.part", vdelta->delta);
101 fpath = _alpm_filecache_find(handle, fnamepart);
102 if(fpath) {
103 struct stat st;
104 if(stat(fpath, &st) == 0) {
105 vdelta->download_size = vdelta->delta_size - st.st_size;
106 vdelta->download_size = vdelta->download_size < 0 ? 0 : vdelta->download_size;
107 }
108 FREE(fpath);
109 }
110 FREE(fnamepart);
111 }
112
113 /* determine whether a base 'from' file exists */
114 fpath = _alpm_filecache_find(handle, vdelta->from);
115 if(fpath) {
116 v->weight = vdelta->download_size;
117 }
118 FREE(fpath);
119 }
120 }
121
122
dijkstra(alpm_list_t * vertices)123 static void dijkstra(alpm_list_t *vertices)
124 {
125 alpm_list_t *i;
126 alpm_graph_t *v;
127 while(1) {
128 v = NULL;
129 /* find the smallest vertice not visited yet */
130 for(i = vertices; i; i = i->next) {
131 alpm_graph_t *v_i = i->data;
132
133 if(v_i->state == ALPM_GRAPH_STATE_PROCESSING) {
134 continue;
135 }
136
137 if(v == NULL || v_i->weight < v->weight) {
138 v = v_i;
139 }
140 }
141 if(v == NULL || v->weight == LONG_MAX) {
142 break;
143 }
144
145 v->state = ALPM_GRAPH_STATE_PROCESSING;
146
147 v->iterator = v->children;
148 while(v->iterator) {
149 alpm_graph_t *v_c = v->iterator->data;
150 alpm_delta_t *d_c = v_c->data;
151 if(v_c->weight > v->weight + d_c->download_size) {
152 v_c->weight = v->weight + d_c->download_size;
153 v_c->parent = v;
154 }
155
156 v->iterator = (v->iterator)->next;
157
158 }
159 }
160 }
161
shortest_path(alpm_list_t * vertices,const char * to,alpm_list_t ** path)162 static off_t shortest_path(alpm_list_t *vertices, const char *to, alpm_list_t **path)
163 {
164 alpm_list_t *i;
165 alpm_graph_t *v = NULL;
166 off_t bestsize = 0;
167 alpm_list_t *rpath = NULL;
168
169 for(i = vertices; i; i = i->next) {
170 alpm_graph_t *v_i = i->data;
171 alpm_delta_t *d_i = v_i->data;
172
173 if(strcmp(d_i->to, to) == 0) {
174 if(v == NULL || v_i->weight < v->weight) {
175 v = v_i;
176 bestsize = v->weight;
177 }
178 }
179 }
180
181 while(v != NULL) {
182 alpm_delta_t *vdelta = v->data;
183 rpath = alpm_list_add(rpath, vdelta);
184 v = v->parent;
185 }
186 *path = alpm_list_reverse(rpath);
187 alpm_list_free(rpath);
188
189 return bestsize;
190 }
191
192 /** Calculates the shortest path from one version to another.
193 * The shortest path is defined as the path with the smallest combined
194 * size, not the length of the path.
195 * @param handle the context handle
196 * @param deltas the list of alpm_delta_t * objects that a file has
197 * @param to the file to start the search at
198 * @param path the pointer to a list location where alpm_delta_t * objects that
199 * have the smallest size are placed. NULL is set if there is no path
200 * possible with the files available.
201 * @return the size of the path stored, or LONG_MAX if path is unfindable
202 */
_alpm_shortest_delta_path(alpm_handle_t * handle,alpm_list_t * deltas,const char * to,alpm_list_t ** path)203 off_t _alpm_shortest_delta_path(alpm_handle_t *handle, alpm_list_t *deltas,
204 const char *to, alpm_list_t **path)
205 {
206 alpm_list_t *bestpath = NULL;
207 alpm_list_t *vertices;
208 off_t bestsize = LONG_MAX;
209
210 if(deltas == NULL) {
211 *path = NULL;
212 return bestsize;
213 }
214
215 _alpm_log(handle, ALPM_LOG_DEBUG, "started delta shortest-path search for '%s'\n", to);
216
217 vertices = graph_init(deltas, 0);
218 graph_init_size(handle, vertices);
219 dijkstra(vertices);
220 bestsize = shortest_path(vertices, to, &bestpath);
221
222 _alpm_log(handle, ALPM_LOG_DEBUG, "delta shortest-path search complete : '%jd'\n", (intmax_t)bestsize);
223
224 alpm_list_free_inner(vertices, _alpm_graph_free);
225 alpm_list_free(vertices);
226
227 *path = bestpath;
228 return bestsize;
229 }
230
find_unused(alpm_list_t * deltas,const char * to,off_t quota)231 static alpm_list_t *find_unused(alpm_list_t *deltas, const char *to, off_t quota)
232 {
233 alpm_list_t *unused = NULL;
234 alpm_list_t *vertices;
235 alpm_list_t *i;
236 vertices = graph_init(deltas, 1);
237
238 for(i = vertices; i; i = i->next) {
239 alpm_graph_t *v = i->data;
240 alpm_delta_t *vdelta = v->data;
241 if(strcmp(vdelta->to, to) == 0) {
242 v->weight = vdelta->download_size;
243 }
244 }
245 dijkstra(vertices);
246 for(i = vertices; i; i = i->next) {
247 alpm_graph_t *v = i->data;
248 alpm_delta_t *vdelta = v->data;
249 if(v->weight > quota) {
250 unused = alpm_list_add(unused, vdelta->delta);
251 }
252 }
253 alpm_list_free_inner(vertices, _alpm_graph_free);
254 alpm_list_free(vertices);
255 return unused;
256 }
257
258 /** \addtogroup alpm_deltas Delta Functions
259 * @brief Functions to manipulate libalpm deltas
260 * @{
261 */
262
alpm_pkg_unused_deltas(alpm_pkg_t * pkg)263 alpm_list_t SYMEXPORT *alpm_pkg_unused_deltas(alpm_pkg_t *pkg)
264 {
265 ASSERT(pkg != NULL, return NULL);
266 return find_unused(pkg->deltas, pkg->filename,
267 pkg->size * pkg->handle->deltaratio);
268 }
269
270 /** @} */
271
272 #define NUM_MATCHES 6
273
274 /** Parses the string representation of a alpm_delta_t object.
275 * This function assumes that the string is in the correct format.
276 * This format is as follows:
277 * $deltafile $deltamd5 $deltasize $oldfile $newfile
278 * @param handle the context handle
279 * @param line the string to parse
280 * @return A pointer to the new alpm_delta_t object
281 */
_alpm_delta_parse(alpm_handle_t * handle,const char * line)282 alpm_delta_t *_alpm_delta_parse(alpm_handle_t *handle, const char *line)
283 {
284 alpm_delta_t *delta;
285 size_t len;
286 regmatch_t pmatch[NUM_MATCHES];
287 char filesize[32];
288
289 /* this is so we only have to compile the pattern once */
290 if(!handle->delta_regex_compiled) {
291 /* $deltafile $deltamd5 $deltasize $oldfile $newfile*/
292 regcomp(&handle->delta_regex,
293 "^([^[:space:]]+) ([[:xdigit:]]{32}) ([[:digit:]]+)"
294 " ([^[:space:]]+) ([^[:space:]]+)$",
295 REG_EXTENDED | REG_NEWLINE);
296 handle->delta_regex_compiled = 1;
297 }
298
299 if(regexec(&handle->delta_regex, line, NUM_MATCHES, pmatch, 0) != 0) {
300 /* delta line is invalid, return NULL */
301 return NULL;
302 }
303
304 CALLOC(delta, 1, sizeof(alpm_delta_t), return NULL);
305
306 /* start at index 1 -- match 0 is the entire match */
307 len = pmatch[1].rm_eo - pmatch[1].rm_so;
308 STRNDUP(delta->delta, &line[pmatch[1].rm_so], len, goto error);
309
310 len = pmatch[2].rm_eo - pmatch[2].rm_so;
311 STRNDUP(delta->delta_md5, &line[pmatch[2].rm_so], len, goto error);
312
313 len = pmatch[3].rm_eo - pmatch[3].rm_so;
314 if(len < sizeof(filesize)) {
315 strncpy(filesize, &line[pmatch[3].rm_so], len);
316 filesize[len] = '\0';
317 delta->delta_size = _alpm_strtoofft(filesize);
318 }
319
320 len = pmatch[4].rm_eo - pmatch[4].rm_so;
321 STRNDUP(delta->from, &line[pmatch[4].rm_so], len, goto error);
322
323 len = pmatch[5].rm_eo - pmatch[5].rm_so;
324 STRNDUP(delta->to, &line[pmatch[5].rm_so], len, goto error);
325
326 return delta;
327
328 error:
329 _alpm_delta_free(delta);
330 return NULL;
331 }
332
333 #undef NUM_MATCHES
334
_alpm_delta_free(alpm_delta_t * delta)335 void _alpm_delta_free(alpm_delta_t *delta)
336 {
337 ASSERT(delta != NULL, return);
338 FREE(delta->delta);
339 FREE(delta->delta_md5);
340 FREE(delta->from);
341 FREE(delta->to);
342 FREE(delta);
343 }
344
_alpm_delta_dup(const alpm_delta_t * delta)345 alpm_delta_t *_alpm_delta_dup(const alpm_delta_t *delta)
346 {
347 alpm_delta_t *newdelta;
348 CALLOC(newdelta, 1, sizeof(alpm_delta_t), return NULL);
349 STRDUP(newdelta->delta, delta->delta, goto error);
350 STRDUP(newdelta->delta_md5, delta->delta_md5, goto error);
351 STRDUP(newdelta->from, delta->from, goto error);
352 STRDUP(newdelta->to, delta->to, goto error);
353 newdelta->delta_size = delta->delta_size;
354 newdelta->download_size = delta->download_size;
355
356 return newdelta;
357
358 error:
359 _alpm_delta_free(newdelta);
360 return NULL;
361 }
362