2 * Copyright (c) 2007, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
11 * The pool contains information about solvables
12 * stored optimized for memory consumption and fast retrieval.
24 #include "poolid_private.h"
30 #define SOLVABLE_BLOCK 255
33 // list of string constants, so we can do pointer/Id instead of string comparison
34 // index into array matches ID_xxx constants in pool.h
36 static const char *initpool_data[] = {
47 "solvable:recommends",
49 "solvable:supplements",
52 "rpm:dbid", /* direct key into rpmdb */
53 "solvable:prereqmarker",
54 "solvable:filemarker",
55 "namespace:installed",
57 "namespace:splitprovides",
75 pool = (Pool *)sat_calloc(1, sizeof(*pool));
77 stringpool_init (&pool->ss, initpool_data);
79 // pre-alloc space for a RelDep
80 pool->rels = (Reldep *)sat_calloc(1 + REL_BLOCK, sizeof(Reldep));
83 // pre-alloc space for a Solvable
84 pool->solvables = (Solvable *)sat_calloc(SOLVABLE_BLOCK + 1, sizeof(Solvable));
86 queue_init(&pool->vendormap);
87 s = pool->solvables + SYSTEMSOLVABLE;
88 s->name = SYSTEM_SYSTEM;
89 s->arch = ARCH_NOARCH;
92 pool->debugmask = SAT_DEBUG_RESULT; /* FIXME */
97 /* free all the resources of our pool */
103 pool_freewhatprovides(pool);
104 pool_freeidhashes(pool);
105 repo_freeallrepos(pool, 1);
106 sat_free(pool->id2arch);
107 sat_free(pool->solvables);
108 sat_free(pool->ss.stringspace);
109 sat_free(pool->ss.strings);
110 sat_free(pool->rels);
111 queue_free(&pool->vendormap);
112 for (i = 0; i < DEP2STRBUF; i++)
113 sat_free(pool->dep2strbuf[i]);
118 pool_add_solvable(Pool *pool)
120 if ((pool->nsolvables & SOLVABLE_BLOCK) == 0)
121 pool->solvables = sat_realloc2(pool->solvables, pool->nsolvables + (SOLVABLE_BLOCK + 1), sizeof(Solvable));
122 memset(pool->solvables + pool->nsolvables, 0, sizeof(Solvable));
123 return pool->nsolvables++;
127 pool_add_solvable_block(Pool *pool, int count)
129 Id nsolvables = pool->nsolvables;
132 if (((nsolvables - 1) | SOLVABLE_BLOCK) != ((nsolvables + count - 1) | SOLVABLE_BLOCK))
133 pool->solvables = sat_realloc2(pool->solvables, (nsolvables + count + SOLVABLE_BLOCK) & ~SOLVABLE_BLOCK, sizeof(Solvable));
134 memset(pool->solvables + nsolvables, 0, sizeof(Solvable) * count);
135 pool->nsolvables += count;
140 pool_free_solvable_block(Pool *pool, Id start, int count, int reuseids)
144 if (reuseids && start + count == pool->nsolvables)
146 /* might want to shrink solvable array */
147 pool->nsolvables = start;
150 memset(pool->solvables + start, 0, sizeof(Solvable) * count);
155 solvable2str(Pool *pool, Solvable *s)
157 int l, nn = pool->dep2strn;
158 const char *n, *e, *a;
159 n = id2str(pool, s->name);
160 e = id2str(pool, s->evr);
161 a = id2str(pool, s->arch);
162 l = strlen(n) + strlen(e) + strlen(a) + 3;
163 if (l > pool->dep2strlen[nn])
165 pool->dep2strbuf[nn] = sat_realloc(pool->dep2strbuf[nn], l + 32);
166 pool->dep2strlen[nn] = l + 32;
168 sprintf(pool->dep2strbuf[nn], "%s-%s.%s", n, e, a);
169 pool->dep2strn = (nn + 1) % DEP2STRBUF;
170 return pool->dep2strbuf[nn];
173 static Pool *pool_shrink_whatprovides_sortcmp_data;
176 pool_shrink_whatprovides_sortcmp(const void *ap, const void *bp)
179 Pool *pool = pool_shrink_whatprovides_sortcmp_data;
181 oa = pool->whatprovides[*(Id *)ap];
182 ob = pool->whatprovides[*(Id *)bp];
184 return *(Id *)ap - *(Id *)bp;
189 da = pool->whatprovidesdata + oa;
190 db = pool->whatprovidesdata + ob;
192 if ((r = (*da++ - *db++)) != 0)
196 return *(Id *)ap - *(Id *)bp;
200 * pool_shrink_whatprovides - unify whatprovides data
202 * whatprovides_rel must be empty for this to work!
206 pool_shrink_whatprovides(Pool *pool)
210 Id lastid, *last, *dp, *lp;
214 if (pool->ss.nstrings < 3)
216 sorted = sat_malloc2(pool->ss.nstrings, sizeof(Id));
217 for (id = 0; id < pool->ss.nstrings; id++)
219 pool_shrink_whatprovides_sortcmp_data = pool;
220 qsort(sorted + 1, pool->ss.nstrings - 1, sizeof(Id), pool_shrink_whatprovides_sortcmp);
223 for (i = 1; i < pool->ss.nstrings; i++)
226 o = pool->whatprovides[id];
227 if (o == 0 || o == 1)
229 dp = pool->whatprovidesdata + o;
243 pool->whatprovides[id] = -lastid;
247 last = pool->whatprovidesdata + o;
251 dp = pool->whatprovidesdata + 2;
252 for (id = 1; id < pool->ss.nstrings; id++)
254 o = pool->whatprovides[id];
255 if (o == 0 || o == 1)
262 pool->whatprovides[id] = pool->whatprovides[i];
265 lp = pool->whatprovidesdata + o;
268 pool->whatprovides[id] = dp - pool->whatprovidesdata;
269 while ((*dp++ = *lp++) != 0)
272 o = dp - pool->whatprovidesdata;
273 POOL_DEBUG(SAT_DEBUG_STATS, "shrunk whatprovidesdata from %d to %d\n", pool->whatprovidesdataoff, o);
274 if (pool->whatprovidesdataoff == o)
276 r = pool->whatprovidesdataoff - o;
277 pool->whatprovidesdataoff = o;
278 pool->whatprovidesdata = sat_realloc(pool->whatprovidesdata, (o + pool->whatprovidesdataleft) * sizeof(Id));
279 if (r > pool->whatprovidesdataleft)
280 r = pool->whatprovidesdataleft;
281 memset(pool->whatprovidesdata + o, 0, r * sizeof(Id));
286 * pool_createwhatprovides()
288 * create hashes over pool of solvables to ease provide lookups
292 pool_createwhatprovides(Pool *pool)
294 int i, num, np, extra;
299 Offset *whatprovides;
300 Id *whatprovidesdata, *d;
302 POOL_DEBUG(SAT_DEBUG_STATS, "number of solvables: %d\n", pool->nsolvables);
303 POOL_DEBUG(SAT_DEBUG_STATS, "number of ids: %d + %d\n", pool->ss.nstrings, pool->nrels);
305 pool_freeidhashes(pool); /* XXX: should not be here! */
306 pool_freewhatprovides(pool);
307 num = pool->ss.nstrings;
308 pool->whatprovides = whatprovides = sat_calloc((num + WHATPROVIDES_BLOCK) & ~WHATPROVIDES_BLOCK, sizeof(Offset));
309 pool->whatprovides_rel = sat_calloc((pool->nrels + WHATPROVIDES_BLOCK) & ~WHATPROVIDES_BLOCK, sizeof(Offset));
311 /* count providers for each name */
312 for (i = 1; i < pool->nsolvables; i++)
315 s = pool->solvables + i;
318 if (!pool_installable(pool, s))
320 pp = s->repo->idarraydata + s->provides;
321 while ((id = *pp++) != ID_NULL)
325 Reldep *rd = GETRELDEP(pool, id);
328 whatprovides[id]++; /* inc count of providers */
332 off = 2; /* first entry is undef, second is empty list */
334 np = 0; /* number of names provided */
335 for (i = 0; i < num; i++, idp++)
338 if (!n) /* no providers */
340 *idp = off; /* move from counts to offsets into whatprovidesdata */
341 off += n + 1; /* make space for all providers + terminating ID_NULL */
342 np++; /* inc # of provider 'slots' */
345 POOL_DEBUG(SAT_DEBUG_STATS, "provide ids: %d\n", np);
347 /* reserve some space for relation data */
348 extra = 2 * pool->nrels;
352 POOL_DEBUG(SAT_DEBUG_STATS, "provide space needed: %d + %d\n", off, extra);
354 /* alloc space for all providers + extra */
355 whatprovidesdata = sat_calloc(off + extra, sizeof(Id));
357 /* now fill data for all provides */
358 for (i = 1; i < pool->nsolvables; i++)
361 s = pool->solvables + i;
364 if (!pool_installable(pool, s))
367 /* for all provides of this solvable */
368 pp = s->repo->idarraydata + s->provides;
369 while ((id = *pp++) != 0)
373 Reldep *rd = GETRELDEP(pool, id);
376 d = whatprovidesdata + whatprovides[id]; /* offset into whatprovidesdata */
380 while (*d) /* find free slot */
385 *d = i; /* put solvable Id into data */
388 pool->whatprovidesdata = whatprovidesdata;
389 pool->whatprovidesdataoff = off;
390 pool->whatprovidesdataleft = extra;
391 pool_shrink_whatprovides(pool);
395 * free all of our whatprovides data
396 * be careful, everything internalized with pool_queuetowhatprovides is gone, too
399 pool_freewhatprovides(Pool *pool)
401 pool->whatprovides = sat_free(pool->whatprovides);
402 pool->whatprovides_rel = sat_free(pool->whatprovides_rel);
403 pool->whatprovidesdata = sat_free(pool->whatprovidesdata);
404 pool->whatprovidesdataoff = 0;
405 pool->whatprovidesdataleft = 0;
409 /******************************************************************************/
412 * pool_queuetowhatprovides - add queue contents to whatprovidesdata
414 * on-demand filling of provider information
415 * move queue data into whatprovidesdata
417 * returns: Offset into whatprovides
421 pool_queuetowhatprovides(Pool *pool, Queue *q)
424 int count = q->count;
426 if (count == 0) /* queue empty -> ID_EMPTY */
429 /* extend whatprovidesdata if needed, +1 for ID_NULL-termination */
430 if (pool->whatprovidesdataleft < count + 1)
432 POOL_DEBUG(SAT_DEBUG_STATS, "growing provides hash data...\n");
433 pool->whatprovidesdata = sat_realloc(pool->whatprovidesdata, (pool->whatprovidesdataoff + count + 4096) * sizeof(Id));
434 pool->whatprovidesdataleft = count + 4096;
437 /* copy queue to next free slot */
438 off = pool->whatprovidesdataoff;
439 memcpy(pool->whatprovidesdata + pool->whatprovidesdataoff, q->elements, count * sizeof(Id));
441 /* adapt count and ID_NULL-terminate */
442 pool->whatprovidesdataoff += count;
443 pool->whatprovidesdata[pool->whatprovidesdataoff++] = ID_NULL;
444 pool->whatprovidesdataleft -= count + 1;
450 /*************************************************************************/
455 * add packages fulfilling the relation to whatprovides array
456 * no exact providers, do range match
461 pool_addrelproviders(Pool *pool, Id d)
463 Reldep *rd = GETRELDEP(pool, d);
469 int flags = rd->flags;
471 Id p, *pp, *pp2, *pp3;
474 queue_init_buffer(&plist, buf, sizeof(buf)/sizeof(*buf));
479 pp = pool_whatprovides(pool, name);
480 pp2 = pool_whatprovides(pool, evr);
481 while ((p = *pp++) != 0)
483 for (pp3 = pp2; *pp3;)
486 queue_push(&plist, p);
492 pp = pool_whatprovides(pool, name);
493 while ((p = *pp++) != 0)
494 queue_push(&plist, p);
495 pp = pool_whatprovides(pool, evr);
496 while ((p = *pp++) != 0)
497 queue_pushunique(&plist, p);
500 if (pool->nscallback)
502 p = pool->nscallback(pool, pool->nscallbackdata, name, evr);
506 pool->whatprovides_rel[d] = p;
507 return pool->whatprovidesdata + p;
510 queue_push(&plist, SYSTEMSOLVABLE);
517 /* convert to whatprovides id */
519 POOL_DEBUG(DEBUG_1, "addrelproviders: what provides %s?\n", id2str(pool, name));
521 if (flags && flags < 8)
523 FOR_PROVIDES(p, pp, name)
526 POOL_DEBUG(DEBUG_1, "addrelproviders: checking package %s\n", id2str(pool, pool->p[p].name));
528 /* solvable p provides name in some rels */
529 pidp = pool->solvables[p].repo->idarraydata + pool->solvables[p].provides;
530 while ((pid = *pidp++) != 0)
537 #ifdef DEBIAN_SEMANTICS
538 continue; /* unversioned provides can
539 * never match versioned deps */
541 break; /* yes, provides all versions */
545 continue; /* wrong provides name */
546 prd = GETRELDEP(pool, pid);
547 if (prd->name != name)
548 continue; /* wrong provides name */
549 /* right package, both deps are rels */
553 if (flags == 7 || pflags == 7)
554 break; /* included */
555 if ((pflags & flags & 5) != 0)
556 break; /* same direction, match */
560 if ((pflags & flags & 2) != 0)
561 break; /* both have =, match */
565 int f = flags == 5 ? 5 : flags == 2 ? pflags : (flags ^ 5) & (pflags | 5);
566 if ((f & (1 << (1 + evrcmp(pool, pevr, evr, EVRCMP_MATCH_RELEASE)))) != 0)
571 continue; /* no rel match */
572 queue_push(&plist, p);
574 /* make our system solvable provide all unknown rpmlib() stuff */
575 if (plist.count == 0 && !strncmp(id2str(pool, name), "rpmlib(", 7))
576 queue_push(&plist, SYSTEMSOLVABLE);
578 /* add providers to whatprovides */
580 POOL_DEBUG(DEBUG_1, "addrelproviders: adding %d packages to %d\n", plist.count, d);
582 pool->whatprovides_rel[d] = pool_queuetowhatprovides(pool, &plist);
585 return pool->whatprovidesdata + pool->whatprovides_rel[d];
588 /*************************************************************************/
591 pool_debug(Pool *pool, int type, const char *format, ...)
596 if ((type & SAT_FATAL) == 0)
598 if ((pool->debugmask & type) == 0)
601 va_start(args, format);
602 if (!pool->debugcallback)
604 if ((type & (SAT_FATAL|SAT_ERROR)) == 0)
605 vprintf(format, args);
607 vfprintf(stderr, format, args);
610 vsnprintf(buf, sizeof(buf), format, args);
611 pool->debugcallback(pool, pool->debugcallbackdata, type, buf);
615 pool_setdebuglevel(Pool *pool, int level)
617 int mask = SAT_DEBUG_RESULT;
619 mask |= SAT_DEBUG_STATS|SAT_DEBUG_ANALYZE|SAT_DEBUG_UNSOLVABLE;
621 mask |= SAT_DEBUG_JOB|SAT_DEBUG_SOLUTIONS|SAT_DEBUG_POLICY;
623 mask |= SAT_DEBUG_PROPAGATE;
625 mask |= SAT_DEBUG_RULE_CREATION;
627 mask |= SAT_DEBUG_SCHUBI;
628 pool->debugmask = mask;
631 /*************************************************************************/
639 #define SEARCHFILES_BLOCK 127
642 pool_addfileprovides_dep(Pool *pool, Id *ida, struct searchfiles *sf, struct searchfiles *isf)
647 while ((dep = *ida++) != 0)
649 while (ISRELDEP(dep))
652 sid = pool->ss.nstrings + GETRELID(dep);
653 if (MAPTST(&sf->seen, sid))
658 MAPSET(&sf->seen, sid);
659 rd = GETRELDEP(pool, dep);
662 else if (rd->flags == REL_NAMESPACE)
664 if (isf && (rd->name == NAMESPACE_INSTALLED || rd->name == NAMESPACE_SPLITPROVIDES))
668 if (MAPTST(&sf->seen, sid))
673 MAPSET(&sf->seen, sid);
682 pool_addfileprovides_dep(pool, ids, sf, isf);
688 if (MAPTST(&sf->seen, dep))
690 MAPSET(&sf->seen, dep);
691 s = id2str(pool, dep);
694 if ((sf->nfiles & SEARCHFILES_BLOCK) == 0)
695 sf->files = sat_realloc2(sf->files, sf->nfiles + (SEARCHFILES_BLOCK + 1), sizeof(const char *));
696 sf->files[sf->nfiles++] = strdup(s);
702 addfileprovides_cb(void *data, Solvable *s, Id key, const char *str)
704 Pool *pool = s->repo->pool;
706 id = str2id(pool, str, 0);
708 return 0; /* can't happen */
709 s->provides = repo_addid_dep(s->repo, s->provides, id, SOLVABLE_FILEMARKER);
715 pool_addfileprovides(Pool *pool, Repo *installed)
719 struct searchfiles sf, isf;
722 memset(&sf, 0, sizeof(sf));
723 map_init(&sf.seen, pool->ss.nstrings + pool->nrels);
724 memset(&isf, 0, sizeof(isf));
725 map_init(&isf.seen, pool->ss.nstrings + pool->nrels);
727 for (i = 1, s = pool->solvables + i; i < pool->nsolvables; i++, s++)
733 pool_addfileprovides_dep(pool, repo->idarraydata + s->obsoletes, &sf, &isf);
735 pool_addfileprovides_dep(pool, repo->idarraydata + s->conflicts, &sf, &isf);
737 pool_addfileprovides_dep(pool, repo->idarraydata + s->requires, &sf, &isf);
739 pool_addfileprovides_dep(pool, repo->idarraydata + s->recommends, &sf, &isf);
741 pool_addfileprovides_dep(pool, repo->idarraydata + s->suggests, &sf, &isf);
743 pool_addfileprovides_dep(pool, repo->idarraydata + s->supplements, &sf, &isf);
745 pool_addfileprovides_dep(pool, repo->idarraydata + s->enhances, &sf, &isf);
747 pool_addfileprovides_dep(pool, repo->idarraydata + s->freshens, &sf, &isf);
751 POOL_DEBUG(SAT_DEBUG_STATS, "found %d file dependencies\n", sf.nfiles);
752 POOL_DEBUG(SAT_DEBUG_STATS, "found %d installed file dependencies\n", isf.nfiles);
756 for (i = 0; i < sf.nfiles; i++)
757 POOL_DEBUG(SAT_DEBUG_STATS, "looking up %s in filelist\n", sf.files[i]);
759 if ((sf.nfiles & SEARCHFILES_BLOCK) == 0)
760 sf.files = sat_realloc2(sf.files, sf.nfiles + (SEARCHFILES_BLOCK + 1), sizeof(const char *));
761 sf.files[sf.nfiles++] = 0;
763 pool_search(0, SOLVABLE_FILELIST, (const char *)sf.files, SEARCH_STRING|SEARCH_MULTIPLE, addfileprovides_cb, 0);
767 if (isf.nfiles && installed)
770 for (i = 0; i < isf.nfiles; i++)
771 POOL_DEBUG(SAT_DEBUG_STATS, "looking up %s in installed filelist\n", isf.files[i]);
773 if ((isf.nfiles & SEARCHFILES_BLOCK) == 0)
774 isf.files = sat_realloc2(isf.files, isf.nfiles + (SEARCHFILES_BLOCK + 1), sizeof(const char *));
775 isf.files[isf.nfiles++] = 0;
777 repo_search(installed, 0, SOLVABLE_FILELIST, (const char *)isf.files, SEARCH_STRING|SEARCH_MULTIPLE, addfileprovides_cb, 0);
781 pool_freewhatprovides(pool); /* as we have added provides */
801 struct mountpoint *mps;
807 pool_fill_DU_add_cb(void *data, Solvable *s, Id key, const char *str)
809 struct cbdata *cbdata = data;
810 Id mp, dirnum, kbytes, files;
812 dp = data_read_id(dp, &dirnum);
813 dp = data_read_id(dp, &kbytes);
814 data_read_id(dp, &files);
815 if (dirnum < 0 || dirnum > cbdata->nmap)
817 mp = cbdata->dirmap[dirnum];
820 cbdata->mps[mp].kbytes += kbytes;
821 cbdata->mps[mp].files += files;
827 pool_fill_DU_sub_cb(void *data, Solvable *s, Id key, const char *str)
829 struct cbdata *cbdata = data;
830 Id mp, dirnum, kbytes, files;
832 dp = data_read_id(dp, &dirnum);
833 dp = data_read_id(dp, &kbytes);
834 data_read_id(dp, &files);
835 if (dirnum < 0 || dirnum > cbdata->nmap)
837 mp = cbdata->dirmap[dirnum];
840 cbdata->mps[mp].kbytes -= kbytes;
841 cbdata->mps[mp].files -= files;
847 propagate_mountpoints(struct mptree *mptree, int pos, Id mountpoint)
850 if (mptree[pos].mountpoint == -1)
851 mptree[pos].mountpoint = mountpoint;
853 mountpoint = mptree[pos].mountpoint;
854 for (i = mptree[pos].child; i; i = mptree[i].sibling)
855 propagate_mountpoints(mptree, i, mountpoint);
859 pool_fill_DU(Pool *pool, struct mountpoint *mps, int nmps)
863 struct mptree *mptree;
869 struct cbdata cbdata;
871 memset(&md, 0, sizeof(md));
876 md.callback_data = &cbdata
882 mptree = sat_malloc2(16, sizeof(mptree));
885 mptree[0].sibling = 0;
889 mptree[0].mountpoint = -1;
892 /* create component tree */
893 for (mp = 0; mp < nmps; mp++)
901 if ((p = strchr('/', path)) == 0)
904 compl = strlen(comp);
915 for (i = mptree[pos].child; i; i = mptree[i].sibling)
916 if (mptree[i].compl == compl && !strncmp(mptree[i].comp, comp, compl))
920 /* create new node */
921 if ((nmptree & 15) == 0)
922 mptree = sat_realloc2(mptree, nmptree + 16, sizeof(mptree));
924 mptree[i].sibling = mptree[pos].child;
926 mptree[i].comp = comp;
927 mptree[i].compl = compl;
928 mptree[i].mountpoint = -1;
929 mptree[pos].child = i;
933 mptree[pos].mountpoint = mp;
935 propagate_mountpoints(mptree, 0, mptree[0].mountpoint);
939 for_all_repodatas_containing_DU
941 /* create map from dir to mptree */
942 dirmap = xcalloc2(pool->ndirs, sizeof(Id));
944 for (dn = 2, dirs = pool->dirs + dn; dn < pool->ndirs; dn++)
958 if (!mptree[mp].child)
963 comp = id2str(pool, id);
964 compl = strlen(comp);
965 for (i = mptree[mp].child; i; i = mptree[i].sibling)
966 if (mptree[i].compl == compl && !strncmp(mptree[i].comp, comp, compl))
968 dirmap[dn] = i ? i : -mp;
970 /* change dirmap to point to mountpoint instead of mptree */
971 for (dn = 0; dn < pool->ndirs; dn++)
974 dirmap[i] = mptree[mp > 0 ? mp : -mp].mountpoint;
977 cbdata.nmap = pool->ndirs;
978 cbdata.dirmap = dirmap;
980 md.callback = pool_fill_DU_add_cb;
981 for_solvables_to_be_installed()
983 if (p < data->start || p >= data->end)
985 repodata_search(data, p - data->start, SOLVABLE_DUDATA, &md);
987 md.callback = pool_fill_DU_sub_cb;
988 for_solvables_to_be_erased()
990 if (p < data->start || p >= data->end)
992 repodata_search(data, p - data->start, SOLVABLE_DUDATA, &md);