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