1 /*
2 * Copyright (c) 2007-2016, SUSE LLC
3 *
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
6 */
7
8 /*
9 * fileprovides.c
10 *
11 * Add missing file dependencies to the package provides
12 */
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <stdarg.h>
17 #include <unistd.h>
18 #include <string.h>
19
20 #include "pool.h"
21 #include "repo.h"
22 #include "util.h"
23 #include "bitmap.h"
24
25
26 struct searchfiles {
27 Id *ids;
28 int nfiles;
29 Map seen;
30 };
31
32 #define SEARCHFILES_BLOCK 127
33
34 static void
pool_addfileprovides_dep(Pool * pool,Id * ida,struct searchfiles * sf,struct searchfiles * isf)35 pool_addfileprovides_dep(Pool *pool, Id *ida, struct searchfiles *sf, struct searchfiles *isf)
36 {
37 Id dep, sid;
38 const char *s;
39 struct searchfiles *csf;
40
41 while ((dep = *ida++) != 0)
42 {
43 csf = sf;
44 while (ISRELDEP(dep))
45 {
46 Reldep *rd;
47 sid = pool->ss.nstrings + GETRELID(dep);
48 if (MAPTST(&csf->seen, sid))
49 {
50 dep = 0;
51 break;
52 }
53 MAPSET(&csf->seen, sid);
54 rd = GETRELDEP(pool, dep);
55 if (rd->flags < 8)
56 dep = rd->name;
57 else if (rd->flags == REL_NAMESPACE)
58 {
59 if (rd->name == NAMESPACE_SPLITPROVIDES)
60 {
61 csf = isf;
62 if (!csf || MAPTST(&csf->seen, sid))
63 {
64 dep = 0;
65 break;
66 }
67 MAPSET(&csf->seen, sid);
68 }
69 dep = rd->evr;
70 }
71 else if (rd->flags == REL_FILECONFLICT)
72 {
73 dep = 0;
74 break;
75 }
76 else
77 {
78 Id ids[2];
79 ids[0] = rd->name;
80 ids[1] = 0;
81 pool_addfileprovides_dep(pool, ids, csf, isf);
82 dep = rd->evr;
83 }
84 }
85 if (!dep)
86 continue;
87 if (MAPTST(&csf->seen, dep))
88 continue;
89 MAPSET(&csf->seen, dep);
90 s = pool_id2str(pool, dep);
91 if (*s != '/')
92 continue;
93 if (csf != isf && pool->addedfileprovides == 1 && !repodata_filelistfilter_matches(0, s))
94 continue; /* skip non-standard locations csf == isf: installed case */
95 csf->ids = solv_extend(csf->ids, csf->nfiles, 1, sizeof(Id), SEARCHFILES_BLOCK);
96 csf->ids[csf->nfiles++] = dep;
97 }
98 }
99
100 struct addfileprovides_cbdata {
101 int nfiles;
102 Id *ids;
103 char **dirs;
104 char **names;
105 Id *dids;
106
107 Map *providedids;
108 int provstart;
109 int provend;
110
111 Map *todo;
112 int todo_start;
113 int todo_end;
114 };
115
116 /* split filelist dep into basename and dirname */
117 static void
create_dirs_names_array(struct addfileprovides_cbdata * cbd,Pool * pool)118 create_dirs_names_array(struct addfileprovides_cbdata *cbd, Pool *pool)
119 {
120 int i;
121 cbd->dirs = solv_malloc2(cbd->nfiles, sizeof(char *));
122 cbd->names = solv_malloc2(cbd->nfiles, sizeof(char *));
123 for (i = 0; i < cbd->nfiles; i++)
124 {
125 char *s = solv_strdup(pool_id2str(pool, cbd->ids[i]));
126 cbd->dirs[i] = s;
127 s = strrchr(s, '/');
128 *s = 0;
129 cbd->names[i] = s + 1;
130 }
131 }
132
133 static void
free_dirs_names_array(struct addfileprovides_cbdata * cbd)134 free_dirs_names_array(struct addfileprovides_cbdata *cbd)
135 {
136 int i;
137 if (cbd->dirs)
138 {
139 for (i = 0; i < cbd->nfiles; i++)
140 solv_free(cbd->dirs[i]);
141 cbd->dirs = solv_free(cbd->dirs);
142 cbd->names = solv_free(cbd->names);
143 }
144 }
145
146 static void
prune_todo_range(Repo * repo,struct addfileprovides_cbdata * cbd)147 prune_todo_range(Repo *repo, struct addfileprovides_cbdata *cbd)
148 {
149 int start = cbd->todo_start, end = cbd->todo_end;
150 while (start < end && !MAPTST(cbd->todo, start - repo->start))
151 start++;
152 while (end > start && !MAPTST(cbd->todo, end - 1 - repo->start))
153 end--;
154 cbd->todo_start = start;
155 cbd->todo_end = end;
156 }
157
158 static int
repodata_intersects_todo(Repodata * data,struct addfileprovides_cbdata * cbd)159 repodata_intersects_todo(Repodata *data, struct addfileprovides_cbdata *cbd)
160 {
161 Repo *repo;
162 int p, start = data->start, end = data->end;
163 if (start >= cbd->todo_end || end <= cbd->todo_start)
164 return 0;
165 repo = data->repo;
166 if (start < cbd->todo_start)
167 start = cbd->todo_start;
168 if (end > cbd->todo_end)
169 end = cbd->todo_end;
170 for (p = start; p < end; p++)
171 if (MAPTST(cbd->todo, p - repo->start))
172 return 1;
173 return 0;
174 }
175
176 /* forward declaration */
177 static void repodata_addfileprovides_search(Repodata *data, struct addfileprovides_cbdata *cbd);
178
179 /* search a subset of the todo range */
180 static void
repodata_addfileprovides_search_limited(Repodata * data,struct addfileprovides_cbdata * cbd,int start,int end)181 repodata_addfileprovides_search_limited(Repodata *data, struct addfileprovides_cbdata *cbd, int start, int end)
182 {
183
184 int old_todo_start = cbd->todo_start;
185 int old_todo_end = cbd->todo_end;
186 if (start < cbd->todo_start)
187 start = cbd->todo_start;
188 if (end > cbd->todo_end)
189 end = cbd->todo_end;
190 if (start >= end)
191 return;
192 cbd->todo_start = start;
193 cbd->todo_end = end;
194 repodata_addfileprovides_search(data, cbd);
195 cbd->todo_start = old_todo_start;
196 cbd->todo_end = old_todo_end;
197 prune_todo_range(data->repo, cbd);
198 }
199
200 static void
repodata_addfileprovides_search(Repodata * data,struct addfileprovides_cbdata * cbd)201 repodata_addfileprovides_search(Repodata *data, struct addfileprovides_cbdata *cbd)
202 {
203 Repo *repo = data->repo;
204 int i, p, start, end;
205 Map useddirs;
206 Map *providedids = 0;
207
208 /* make it available */
209 if (data->state == REPODATA_STUB)
210 repodata_load(data);
211 if (data->state != REPODATA_AVAILABLE)
212 return;
213 if (!data->incoredata || !data->dirpool.ndirs)
214 return;
215
216 start = cbd->todo_start > data->start ? cbd->todo_start : data->start;
217 end = cbd->todo_end > data->end ? data->end : cbd->todo_end;
218
219 if (start >= end)
220 return;
221
222 /* deal with provideids overlap */
223 if (cbd->providedids)
224 {
225 if (start >= cbd->provstart && end <= cbd->provend)
226 providedids = cbd->providedids; /* complete overlap */
227 else if (start < cbd->provend && end > cbd->provstart)
228 {
229 /* partial overlap, need to split search */
230 if (start < cbd->provstart)
231 {
232 repodata_addfileprovides_search_limited(data, cbd, start, cbd->provstart);
233 start = cbd->provstart;
234 }
235 if (end > cbd->provend)
236 {
237 repodata_addfileprovides_search_limited(data, cbd, cbd->provend, end);
238 end = cbd->provend;
239 }
240 if (start < end)
241 repodata_addfileprovides_search_limited(data, cbd, start, end);
242 return;
243 }
244 }
245
246 /* set up dirs and names array if not already done */
247 if (!cbd->dirs)
248 create_dirs_names_array(cbd, repo->pool);
249
250 /* set up useddirs map and the cbd->dids array */
251 map_init(&useddirs, data->dirpool.ndirs);
252 for (i = 0; i < cbd->nfiles; i++)
253 {
254 Id did;
255 if (providedids && MAPTST(providedids, cbd->ids[i]))
256 {
257 cbd->dids[i] = 0; /* already included, do not add again */
258 continue;
259 }
260 cbd->dids[i] = did = repodata_str2dir(data, cbd->dirs[i], 0);
261 if (did)
262 MAPSET(&useddirs, did);
263 }
264 repodata_free_dircache(data); /* repodata_str2dir created it */
265
266 for (p = start; p < end; p++)
267 {
268 const unsigned char *dp;
269 Solvable *s;
270 if (!MAPTST(cbd->todo, p - repo->start))
271 continue;
272 dp = repodata_lookup_packed_dirstrarray(data, p, SOLVABLE_FILELIST);
273 if (!dp)
274 continue;
275 /* now iterate through the packed array */
276 s = repo->pool->solvables + p;
277 MAPCLR(cbd->todo, p - repo->start); /* this entry is done */
278 for (;;)
279 {
280 Id did = 0;
281 int c;
282 while ((c = *dp++) & 0x80)
283 did = (did << 7) ^ c ^ 0x80;
284 did = (did << 6) | (c & 0x3f);
285 if ((unsigned int)did < (unsigned int)data->dirpool.ndirs && MAPTST(&useddirs, did))
286 {
287 /* there is at least one entry with that did */
288 for (i = 0; i < cbd->nfiles; i++)
289 if (cbd->dids[i] == did && !strcmp(cbd->names[i], (const char *)dp))
290 s->provides = repo_addid_dep(s->repo, s->provides, cbd->ids[i], SOLVABLE_FILEMARKER);
291 }
292 if (!(c & 0x40))
293 break;
294 dp += strlen((const char *)dp) + 1;
295 }
296 }
297 map_free(&useddirs);
298 prune_todo_range(repo, cbd);
299 }
300
301 static void
repo_addfileprovides_search_filtered(Repo * repo,struct addfileprovides_cbdata * cbd,int filteredid,Map * postpone)302 repo_addfileprovides_search_filtered(Repo *repo, struct addfileprovides_cbdata *cbd, int filteredid, Map *postpone)
303 {
304 Repodata *data = repo->repodata + filteredid;
305 Map *providedids = cbd->providedids;
306 int rdid;
307 int start, end, p, i;
308 Map old_todo;
309 int old_todo_start, old_todo_end;
310
311 start = cbd->todo_start > data->start ? cbd->todo_start : data->start;
312 end = cbd->todo_end > data->end ? data->end : cbd->todo_end;
313
314 if (providedids)
315 {
316 /* check if all solvables are in the provide range */
317 if (start < cbd->provstart || end > cbd->provend)
318 {
319 /* unclear, check each solvable */
320 for (p = start; p < end; p++)
321 {
322 if (p >= cbd->provstart && p < cbd->provend)
323 continue;
324 if (data->incoreoffset[p - data->start] && MAPTST(cbd->todo, p - repo->start))
325 {
326 providedids = 0; /* nope, cannot prune with providedids */
327 break;
328 }
329 }
330 }
331 }
332
333 /* check if the filtered files are enough */
334 for (i = 0; i < cbd->nfiles; i++)
335 {
336 if (providedids && MAPTST(providedids, cbd->ids[i])) /* this one is already provided */
337 continue;
338 if (!repodata_filelistfilter_matches(data, pool_id2str(repo->pool, cbd->ids[i])))
339 break;
340 }
341 if (i < cbd->nfiles)
342 {
343 /* nope, need to search the extensions as well. postpone. */
344 for (p = start; p < end; p++)
345 {
346 if (data->incoreoffset[p - data->start] && MAPTST(cbd->todo, p - repo->start))
347 {
348 if (!postpone->size)
349 map_grow(postpone, repo->nsolvables);
350 MAPSET(postpone, p - repo->start);
351 MAPCLR(cbd->todo, p - repo->start);
352 }
353 }
354 prune_todo_range(repo, cbd);
355 return;
356 }
357
358 /* now check if there is no data marked withour EXTENSION */
359 /* limit todo to the solvables in this repodata */
360 old_todo_start = cbd->todo_start;
361 old_todo_end = cbd->todo_end;
362 old_todo = *cbd->todo;
363 map_init(cbd->todo, repo->nsolvables);
364 for (p = start; p < end; p++)
365 if (data->incoreoffset[p - data->start] && MAPTST(&old_todo, p - repo->start))
366 {
367 MAPCLR(&old_todo, p - repo->start);
368 MAPSET(cbd->todo, p - repo->start);
369 }
370 prune_todo_range(repo, cbd);
371
372 /* do the check */
373 for (rdid = repo->nrepodata - 1, data = repo->repodata + rdid; rdid > filteredid ; rdid--, data--)
374 {
375 if (data->filelisttype == REPODATA_FILELIST_EXTENSION)
376 continue;
377 if (data->start >= cbd->todo_end || data->end <= cbd->todo_start)
378 continue;
379 if (!repodata_has_keyname(data, SOLVABLE_FILELIST))
380 continue;
381 if (!repodata_intersects_todo(data, cbd))
382 continue;
383 /* oh no, this filelist data is not tagged with REPODATA_FILELIST_EXTENSION! */
384 /* postpone entries that have filelist data */
385 start = cbd->todo_start > data->start ? cbd->todo_start : data->start;
386 end = cbd->todo_end > data->end ? data->end : cbd->todo_end;
387 for (p = start; p < end; p++)
388 if (MAPTST(cbd->todo, p - repo->start))
389 if (repodata_lookup_type(data, p, SOLVABLE_FILELIST))
390 {
391 if (!postpone->size)
392 map_grow(postpone, repo->nsolvables);
393 MAPSET(postpone, p - repo->start);
394 MAPCLR(cbd->todo, p - repo->start);
395 }
396 prune_todo_range(repo, cbd);
397 if (cbd->todo_start >= cbd->todo_end)
398 break;
399 }
400
401 /* do the search over the filtered file list with the remaining entries*/
402 if (cbd->todo_start < cbd->todo_end)
403 repodata_addfileprovides_search(repo->repodata + filteredid, cbd);
404
405 /* restore todo map */
406 map_free(cbd->todo);
407 *cbd->todo = old_todo;
408 cbd->todo_start = old_todo_start;
409 cbd->todo_end = old_todo_end;
410 prune_todo_range(repo, cbd);
411 }
412
413 static void
repo_addfileprovides_search(Repo * repo,struct addfileprovides_cbdata * cbd,struct searchfiles * sf)414 repo_addfileprovides_search(Repo *repo, struct addfileprovides_cbdata *cbd, struct searchfiles *sf)
415 {
416 Repodata *data;
417 int rdid, p, i;
418 int provstart, provend;
419 Map todo;
420 Map providedids;
421
422 if (repo->end <= repo->start || !repo->nsolvables || !sf->nfiles)
423 return;
424
425 /* update search data if changed */
426 if (cbd->nfiles != sf->nfiles || cbd->ids != sf->ids)
427 {
428 free_dirs_names_array(cbd);
429 cbd->nfiles = sf->nfiles;
430 cbd->ids = sf->ids;
431 cbd->dids = solv_realloc2(cbd->dids, sf->nfiles, sizeof(Id));
432 }
433
434 /* create todo map and range */
435 map_init(&todo, repo->end - repo->start);
436 for (p = repo->start; p < repo->end; p++)
437 if (repo->pool->solvables[p].repo == repo)
438 MAPSET(&todo, p - repo->start);
439 cbd->todo = &todo;
440 cbd->todo_start = repo->start;
441 cbd->todo_end = repo->end;
442 prune_todo_range(repo, cbd);
443
444 provstart = provend = 0;
445 map_init(&providedids, 0);
446 data = repo_lookup_repodata(repo, SOLVID_META, REPOSITORY_ADDEDFILEPROVIDES);
447 if (data)
448 {
449 Queue fileprovidesq;
450 queue_init(&fileprovidesq);
451 if (repodata_lookup_idarray(data, SOLVID_META, REPOSITORY_ADDEDFILEPROVIDES, &fileprovidesq))
452 {
453 map_grow(&providedids, repo->pool->ss.nstrings);
454 cbd->providedids = &providedids;
455 provstart = data->start;
456 provend = data->end;
457 for (i = 0; i < fileprovidesq.count; i++)
458 MAPSET(&providedids, fileprovidesq.elements[i]);
459 for (i = 0; i < cbd->nfiles; i++)
460 if (!MAPTST(&providedids, cbd->ids[i]))
461 break;
462 if (i == cbd->nfiles)
463 {
464 /* all included, clear entries from todo list */
465 if (provstart <= cbd->todo_start && provend >= cbd->todo_end)
466 cbd->todo_end = cbd->todo_start; /* clear complete range */
467 else
468 {
469 for (p = provstart; p < provend; p++)
470 MAPCLR(&todo, p - repo->start);
471 prune_todo_range(repo, cbd);
472 }
473 }
474 }
475 queue_free(&fileprovidesq);
476 }
477
478 if (cbd->todo_start >= cbd->todo_end)
479 {
480 map_free(&todo);
481 cbd->todo = 0;
482 map_free(&providedids);
483 cbd->providedids = 0;
484 return;
485 }
486
487 /* this is similar to repo_lookup_filelist_repodata in repo.c */
488
489 for (rdid = 1, data = repo->repodata + rdid; rdid < repo->nrepodata; rdid++, data++)
490 if (data->filelisttype == REPODATA_FILELIST_FILTERED)
491 break;
492 for (; rdid < repo->nrepodata; rdid++, data++)
493 if (data->filelisttype == REPODATA_FILELIST_EXTENSION)
494 break;
495
496 if (rdid < repo->nrepodata)
497 {
498 /* have at least one repodata with REPODATA_FILELIST_FILTERED followed by REPODATA_FILELIST_EXTENSION */
499 Map postpone;
500 map_init(&postpone, 0);
501 for (rdid = repo->nrepodata - 1, data = repo->repodata + rdid; rdid > 0; rdid--, data--)
502 {
503 if (data->filelisttype != REPODATA_FILELIST_FILTERED)
504 continue;
505 if (!repodata_intersects_todo(data, cbd))
506 continue;
507 if (data->state != REPODATA_AVAILABLE)
508 {
509 if (data->state != REPODATA_STUB)
510 continue;
511 repodata_load(data);
512 if (data->state != REPODATA_AVAILABLE || data->filelisttype != REPODATA_FILELIST_FILTERED)
513 continue;
514 }
515 repo_addfileprovides_search_filtered(repo, cbd, rdid, &postpone);
516 }
517 if (postpone.size)
518 {
519 /* add postponed entries back to todo */
520 map_or(&todo, &postpone);
521 cbd->todo_start = repo->start;
522 cbd->todo_end = repo->end;
523 prune_todo_range(repo, cbd);
524 }
525 map_free(&postpone);
526 }
527
528 /* search remaining entries in the standard way */
529 if (cbd->todo_start < cbd->todo_end)
530 {
531 for (rdid = repo->nrepodata - 1, data = repo->repodata + rdid; rdid > 0; rdid--, data--)
532 {
533 if (data->start >= cbd->todo_end || data->end <= cbd->todo_start)
534 continue;
535 if (!repodata_has_keyname(data, SOLVABLE_FILELIST))
536 continue;
537 if (!repodata_intersects_todo(data, cbd))
538 continue;
539 repodata_addfileprovides_search(data, cbd);
540 if (cbd->todo_start >= cbd->todo_end)
541 break;
542 }
543 }
544
545 map_free(&todo);
546 cbd->todo = 0;
547 map_free(&providedids);
548 cbd->providedids = 0;
549 }
550
551 void
pool_addfileprovides_queue(Pool * pool,Queue * idq,Queue * idqinst)552 pool_addfileprovides_queue(Pool *pool, Queue *idq, Queue *idqinst)
553 {
554 Solvable *s;
555 Repo *installed, *repo;
556 struct searchfiles sf, isf, *isfp;
557 struct addfileprovides_cbdata cbd;
558 int i;
559 unsigned int now;
560
561 installed = pool->installed;
562 now = solv_timems(0);
563 memset(&cbd, 0, sizeof(cbd));
564 memset(&sf, 0, sizeof(sf));
565 map_init(&sf.seen, pool->ss.nstrings + pool->nrels);
566 memset(&isf, 0, sizeof(isf));
567 map_init(&isf.seen, pool->ss.nstrings + pool->nrels);
568 pool->addedfileprovides = pool->addfileprovidesfiltered ? 1 : 2;
569
570 if (idq)
571 queue_empty(idq);
572 if (idqinst)
573 queue_empty(idqinst);
574 isfp = installed ? &isf : 0;
575 for (i = 1, s = pool->solvables + i; i < pool->nsolvables; i++, s++)
576 {
577 repo = s->repo;
578 if (!repo)
579 continue;
580 if (s->obsoletes)
581 pool_addfileprovides_dep(pool, repo->idarraydata + s->obsoletes, &sf, isfp);
582 if (s->conflicts)
583 pool_addfileprovides_dep(pool, repo->idarraydata + s->conflicts, &sf, isfp);
584 if (s->requires)
585 pool_addfileprovides_dep(pool, repo->idarraydata + s->requires, &sf, isfp);
586 if (s->recommends)
587 pool_addfileprovides_dep(pool, repo->idarraydata + s->recommends, &sf, isfp);
588 if (s->suggests)
589 pool_addfileprovides_dep(pool, repo->idarraydata + s->suggests, &sf, isfp);
590 if (s->supplements)
591 pool_addfileprovides_dep(pool, repo->idarraydata + s->supplements, &sf, isfp);
592 if (s->enhances)
593 pool_addfileprovides_dep(pool, repo->idarraydata + s->enhances, &sf, isfp);
594 }
595
596 map_free(&sf.seen);
597 map_free(&isf.seen);
598 POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file dependencies, %d installed file dependencies\n", sf.nfiles, isf.nfiles);
599 if (sf.nfiles)
600 {
601 #if 0
602 for (i = 0; i < sf.nfiles; i++)
603 POOL_DEBUG(SOLV_DEBUG_STATS, "looking up %s in filelist\n", pool_id2str(pool, sf.ids[i]));
604 #endif
605 FOR_REPOS(i, repo)
606 repo_addfileprovides_search(repo, &cbd, &sf);
607 if (idq)
608 queue_insertn(idq, idq->count, sf.nfiles, sf.ids);
609 if (idqinst)
610 queue_insertn(idqinst, idqinst->count, sf.nfiles, sf.ids);
611 solv_free(sf.ids);
612 }
613 if (isf.nfiles)
614 {
615 #if 0
616 for (i = 0; i < isf.nfiles; i++)
617 POOL_DEBUG(SOLV_DEBUG_STATS, "looking up %s in installed filelist\n", pool_id2str(pool, isf.ids[i]));
618 #endif
619 if (installed)
620 repo_addfileprovides_search(installed, &cbd, &isf);
621 if (installed && idqinst)
622 for (i = 0; i < isf.nfiles; i++)
623 queue_pushunique(idqinst, isf.ids[i]);
624 solv_free(isf.ids);
625 }
626 free_dirs_names_array(&cbd);
627 solv_free(cbd.dids);
628 pool_freewhatprovides(pool); /* as we have added provides */
629 POOL_DEBUG(SOLV_DEBUG_STATS, "addfileprovides took %d ms\n", solv_timems(now));
630 }
631
632 void
pool_addfileprovides(Pool * pool)633 pool_addfileprovides(Pool *pool)
634 {
635 pool_addfileprovides_queue(pool, 0, 0);
636 }
637
638