src/pool.c

   1 /*
   2  * Copyright (c) 2007, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * pool.c
  10  *
  11  * The pool contains information about solvables
  12  * stored optimized for memory consumption and fast retrieval.
  13  */
  14
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <stdarg.h>
  18 #include <unistd.h>
  19 #include <string.h>
  20
  21 #include "pool.h"
  22 #include "repo.h"
  23 #include "poolid.h"
  24 #include "poolid_private.h"
  25 #include "poolarch.h"
  26 #include "util.h"
  27 #include "evr.h"
  28
  29 #define SOLVABLE_BLOCK  255
  30
  31
  32 // list of string constants, so we can do pointer/Id instead of string comparison
  33 // index into array matches ID_xxx constants in pool.h
  34
  35 static const char *initpool_data[] = {
  36   "<NULL>",                   // ID_NULL
  37   "",                         // ID_EMPTY
  38   "solvable:name",
  39   "solvable:arch",
  40   "solvable:evr",
  41   "solvable:vendor",
  42   "solvable:provides",
  43   "solvable:obsoletes",
  44   "solvable:conflicts",
  45   "solvable:requires",
  46   "solvable:recommends",
  47   "solvable:suggests",
  48   "solvable:supplements",
  49   "solvable:enhances",
  50   "solvable:freshens",
  51   "rpm:dbid",                          /* direct key into rpmdb */
  52   "solvable:prereqmarker",
  53   "solvable:filemarker",
  54   "namespace:installed",
  55   "namespace:modalias",
  56   "system:system",
  57   "src",
  58   "nosrc",
  59   "noarch",
  60   "repodata:external",
  61   "repodata:keys",
  62   "repodata:location",
  63   0
  64 };
  65
  66 /* create pool */
  67 Pool *
  68 pool_create(void)
  69 {
  70   Pool *pool;
  71   Solvable *s;
  72
  73   pool = (Pool *)xcalloc(1, sizeof(*pool));
  74
  75   stringpool_init (&pool->ss, initpool_data);
  76
  77   // pre-alloc space for a RelDep
  78   pool->rels = (Reldep *)xcalloc(1 + REL_BLOCK, sizeof(Reldep));
  79   pool->nrels = 1;
  80
  81   // pre-alloc space for a Solvable
  82   pool->solvables = (Solvable *)xcalloc(SOLVABLE_BLOCK + 1, sizeof(Solvable));
  83   pool->nsolvables = 2;
  84   queue_init(&pool->vendormap);
  85   s = pool->solvables + SYSTEMSOLVABLE;
  86   s->name = SYSTEM_SYSTEM;
  87   s->arch = ARCH_NOARCH;
  88   s->evr = ID_EMPTY;
  89
  90   pool->debugmask = SAT_DEBUG_RESULT;   /* FIXME */
  91   return pool;
  92 }
  93
  94
  95 /* free all the resources of our pool */
  96 void
  97 pool_free(Pool *pool)
  98 {
  99   int i;
 100
 101   pool_freewhatprovides(pool);
 102   pool_freeidhashes(pool);
 103   repo_freeallrepos(pool, 1);
 104   xfree(pool->id2arch);
 105   xfree(pool->solvables);
 106   xfree(pool->ss.stringspace);
 107   xfree(pool->ss.strings);
 108   xfree(pool->rels);
 109   queue_free(&pool->vendormap);
 110   for (i = 0; i < DEP2STRBUF; i++)
 111     xfree(pool->dep2strbuf[i]);
 112   xfree(pool);
 113 }
 114
 115 Id
 116 pool_add_solvable(Pool *pool)
 117 {
 118   if ((pool->nsolvables & SOLVABLE_BLOCK) == 0)
 119     pool->solvables = xrealloc2(pool->solvables, pool->nsolvables + (SOLVABLE_BLOCK + 1), sizeof(Solvable));
 120   memset(pool->solvables + pool->nsolvables, 0, sizeof(Solvable));
 121   return pool->nsolvables++;
 122 }
 123
 124 Id
 125 pool_add_solvable_block(Pool *pool, int count)
 126 {
 127   Id nsolvables = pool->nsolvables;
 128   if (!count)
 129     return nsolvables;
 130   if (((nsolvables - 1) | SOLVABLE_BLOCK) != ((nsolvables + count - 1) | SOLVABLE_BLOCK))
 131     pool->solvables = xrealloc2(pool->solvables, (nsolvables + count + SOLVABLE_BLOCK) & ~SOLVABLE_BLOCK, sizeof(Solvable));
 132   memset(pool->solvables + nsolvables, 0, sizeof(Solvable) * count);
 133   pool->nsolvables += count;
 134   return nsolvables;
 135 }
 136
 137 void
 138 pool_free_solvable_block(Pool *pool, Id start, int count, int reuseids)
 139 {
 140   if (!count)
 141     return;
 142   if (reuseids && start + count == pool->nsolvables)
 143     {
 144       /* might want to shrink solvable array */
 145       pool->nsolvables = start;
 146       return;
 147     }
 148   memset(pool->solvables + start, 0, sizeof(Solvable) * count);
 149 }
 150
 151
 152 const char *
 153 solvable2str(Pool *pool, Solvable *s)
 154 {
 155   int l, nn = pool->dep2strn;
 156   const char *n, *e, *a;
 157   n = id2str(pool, s->name);
 158   e = id2str(pool, s->evr);
 159   a = id2str(pool, s->arch);
 160   l = strlen(n) + strlen(e) + strlen(a) + 3;
 161   if (l > pool->dep2strlen[nn])
 162     {
 163       pool->dep2strbuf[nn] = xrealloc(pool->dep2strbuf[nn], l + 32);
 164       pool->dep2strlen[nn] = l + 32;
 165     }
 166   sprintf(pool->dep2strbuf[nn], "%s-%s.%s", n, e, a);
 167   pool->dep2strn = (nn + 1) % DEP2STRBUF;
 168   return pool->dep2strbuf[nn];
 169 }
 170
 171 static Pool *pool_shrink_whatprovides_sortcmp_data;
 172
 173 static int
 174 pool_shrink_whatprovides_sortcmp(const void *ap, const void *bp)
 175 {
 176   int r;
 177   Pool *pool = pool_shrink_whatprovides_sortcmp_data;
 178   Id oa, ob, *da, *db;
 179   oa = pool->whatprovides[*(Id *)ap];
 180   ob = pool->whatprovides[*(Id *)bp];
 181   if (oa == ob)
 182     return *(Id *)ap - *(Id *)bp;
 183   if (!oa)
 184     return -1;
 185   if (!ob)
 186     return 1;
 187   da = pool->whatprovidesdata + oa;
 188   db = pool->whatprovidesdata + ob;
 189   while (*db)
 190     if ((r = (*da++ - *db++)) != 0)
 191       return r;
 192   if (*da)
 193     return *da;
 194   return *(Id *)ap - *(Id *)bp;
 195 }
 196
 197 /*
 198  * pool_shrink_whatprovides  - unify whatprovides data
 199  *
 200  * whatprovides_rel must be empty for this to work!
 201  *
 202  */
 203 static void
 204 pool_shrink_whatprovides(Pool *pool)
 205 {
 206   Id i, id;
 207   Id *sorted;
 208   Id lastid, *last, *dp, *lp;
 209   Offset o;
 210   int r;
 211
 212   if (pool->ss.nstrings < 3)
 213     return;
 214   sorted = xmalloc2(pool->ss.nstrings, sizeof(Id));
 215   for (id = 0; id < pool->ss.nstrings; id++)
 216     sorted[id] = id;
 217   pool_shrink_whatprovides_sortcmp_data = pool;
 218   qsort(sorted + 1, pool->ss.nstrings - 1, sizeof(Id), pool_shrink_whatprovides_sortcmp);
 219   last = 0;
 220   lastid = 0;
 221   for (i = 1; i < pool->ss.nstrings; i++)
 222     {
 223       id = sorted[i];
 224       o = pool->whatprovides[id];
 225       if (o == 0 || o == 1)
 226         continue;
 227       dp = pool->whatprovidesdata + o;
 228       if (last)
 229         {
 230           lp = last;
 231           while (*dp)
 232             if (*dp++ != *lp++)
 233               {
 234                 last = 0;
 235                 break;
 236               }
 237           if (last && *lp)
 238             last = 0;
 239           if (last)
 240             {
 241               pool->whatprovides[id] = -lastid;
 242               continue;
 243             }
 244         }
 245       last = pool->whatprovidesdata + o;
 246       lastid = id;
 247     }
 248   xfree(sorted);
 249   dp = pool->whatprovidesdata + 2;
 250   for (id = 1; id < pool->ss.nstrings; id++)
 251     {
 252       o = pool->whatprovides[id];
 253       if (o == 0 || o == 1)
 254         continue;
 255       if ((Id)o < 0)
 256         {
 257           i = -(Id)o;
 258           if (i >= id)
 259             abort();
 260           pool->whatprovides[id] = pool->whatprovides[i];
 261           continue;
 262         }
 263       lp = pool->whatprovidesdata + o;
 264       if (lp < dp)
 265         abort();
 266       pool->whatprovides[id] = dp - pool->whatprovidesdata;
 267       while ((*dp++ = *lp++) != 0)
 268         ;
 269     }
 270   o = dp - pool->whatprovidesdata;
 271   POOL_DEBUG(SAT_DEBUG_STATS, "shrunk whatprovidesdata from %d to %d\n", pool->whatprovidesdataoff, o);
 272   if (pool->whatprovidesdataoff == o)
 273     return;
 274   r = pool->whatprovidesdataoff - o;
 275   pool->whatprovidesdataoff = o;
 276   pool->whatprovidesdata = xrealloc(pool->whatprovidesdata, (o + pool->whatprovidesdataleft) * sizeof(Id));
 277   if (r > pool->whatprovidesdataleft)
 278     r = pool->whatprovidesdataleft;
 279   memset(pool->whatprovidesdata + o, 0, r * sizeof(Id));
 280 }
 281
 282
 283 /*
 284  * pool_createwhatprovides()
 285  *
 286  * create hashes over pool of solvables to ease provide lookups
 287  *
 288  */
 289 void
 290 pool_createwhatprovides(Pool *pool)
 291 {
 292   int i, num, np, extra;
 293   Offset off;
 294   Solvable *s;
 295   Id id;
 296   Offset *idp, n;
 297   Offset *whatprovides;
 298   Id *whatprovidesdata, *d;
 299
 300   POOL_DEBUG(SAT_DEBUG_STATS, "number of solvables: %d\n", pool->nsolvables);
 301   POOL_DEBUG(SAT_DEBUG_STATS, "number of ids: %d + %d\n", pool->ss.nstrings, pool->nrels);
 302
 303   pool_freeidhashes(pool);      /* XXX: should not be here! */
 304   pool_freewhatprovides(pool);
 305   num = pool->ss.nstrings;
 306   pool->whatprovides = whatprovides = (Offset *)xcalloc((num + WHATPROVIDES_BLOCK) & ~WHATPROVIDES_BLOCK, sizeof(Offset));
 307   pool->whatprovides_rel = (Offset *)xcalloc((pool->nrels + WHATPROVIDES_BLOCK) & ~WHATPROVIDES_BLOCK, sizeof(Offset));
 308
 309   /* count providers for each name */
 310   for (i = 1; i < pool->nsolvables; i++)
 311     {
 312       Id *pp;
 313       s = pool->solvables + i;
 314       if (!s->provides)
 315         continue;
 316       if (!pool_installable(pool, s))
 317         continue;
 318       pp = s->repo->idarraydata + s->provides;
 319       while ((id = *pp++) != ID_NULL)
 320         {
 321           while (ISRELDEP(id))
 322             {
 323               Reldep *rd = GETRELDEP(pool, id);
 324               id = rd->name;
 325             }
 326           whatprovides[id]++;          /* inc count of providers */
 327         }
 328     }
 329
 330   off = 2;      /* first entry is undef, second is empty list */
 331   idp = whatprovides;
 332   np = 0;                              /* number of names provided */
 333   for (i = 0; i < num; i++, idp++)
 334     {
 335       n = *idp;
 336       if (!n)                          /* no providers */
 337         continue;
 338       *idp = off;                      /* move from counts to offsets into whatprovidesdata */
 339       off += n + 1;                    /* make space for all providers + terminating ID_NULL */
 340       np++;                            /* inc # of provider 'slots' */
 341     }
 342
 343   POOL_DEBUG(SAT_DEBUG_STATS, "provide ids: %d\n", np);
 344
 345   /* reserve some space for relation data */
 346   extra = 2 * pool->nrels;
 347   if (extra < 256)
 348     extra = 256;
 349
 350   POOL_DEBUG(SAT_DEBUG_STATS, "provide space needed: %d + %d\n", off, extra);
 351
 352   /* alloc space for all providers + extra */
 353   whatprovidesdata = (Id *)xcalloc(off + extra, sizeof(Id));
 354
 355   /* now fill data for all provides */
 356   for (i = 1; i < pool->nsolvables; i++)
 357     {
 358       Id *pp;
 359       s = pool->solvables + i;
 360       if (!s->provides)
 361         continue;
 362       if (!pool_installable(pool, s))
 363         continue;
 364
 365       /* for all provides of this solvable */
 366       pp = s->repo->idarraydata + s->provides;
 367       while ((id = *pp++) != 0)
 368         {
 369           while (ISRELDEP(id))
 370             {
 371               Reldep *rd = GETRELDEP(pool, id);
 372               id = rd->name;
 373             }
 374           d = whatprovidesdata + whatprovides[id];   /* offset into whatprovidesdata */
 375           if (*d)
 376             {
 377               d++;
 378               while (*d)               /* find free slot */
 379                 d++;
 380               if (d[-1] == i)
 381                 continue;
 382             }
 383           *d = i;                      /* put solvable Id into data */
 384         }
 385     }
 386   pool->whatprovidesdata = whatprovidesdata;
 387   pool->whatprovidesdataoff = off;
 388   pool->whatprovidesdataleft = extra;
 389   pool_shrink_whatprovides(pool);
 390 }
 391
 392 /*
 393  * free all of our whatprovides data
 394  * be careful, everything internalized with pool_queuetowhatprovides is gone, too
 395  */
 396 void
 397 pool_freewhatprovides(Pool *pool)
 398 {
 399   pool->whatprovides = xfree(pool->whatprovides);
 400   pool->whatprovides_rel = xfree(pool->whatprovides_rel);
 401   pool->whatprovidesdata = xfree(pool->whatprovidesdata);
 402   pool->whatprovidesdataoff = 0;
 403   pool->whatprovidesdataleft = 0;
 404 }
 405
 406
 407 /******************************************************************************/
 408
 409 /*
 410  * pool_queuetowhatprovides  - add queue contents to whatprovidesdata
 411  *
 412  * on-demand filling of provider information
 413  * move queue data into whatprovidesdata
 414  * q: queue of Ids
 415  * returns: Offset into whatprovides
 416  *
 417  */
 418 Id
 419 pool_queuetowhatprovides(Pool *pool, Queue *q)
 420 {
 421   Offset off;
 422   int count = q->count;
 423
 424   if (count == 0)                      /* queue empty -> ID_EMPTY */
 425     return ID_EMPTY;
 426
 427   /* extend whatprovidesdata if needed, +1 for ID_NULL-termination */
 428   if (pool->whatprovidesdataleft < count + 1)
 429     {
 430       POOL_DEBUG(SAT_DEBUG_STATS, "growing provides hash data...\n");
 431       pool->whatprovidesdata = (Id *)xrealloc(pool->whatprovidesdata, (pool->whatprovidesdataoff + count + 4096) * sizeof(Id));
 432       pool->whatprovidesdataleft = count + 4096;
 433     }
 434
 435   /* copy queue to next free slot */
 436   off = pool->whatprovidesdataoff;
 437   memcpy(pool->whatprovidesdata + pool->whatprovidesdataoff, q->elements, count * sizeof(Id));
 438
 439   /* adapt count and ID_NULL-terminate */
 440   pool->whatprovidesdataoff += count;
 441   pool->whatprovidesdata[pool->whatprovidesdataoff++] = ID_NULL;
 442   pool->whatprovidesdataleft -= count + 1;
 443
 444   return (Id)off;
 445 }
 446
 447
 448 /*************************************************************************/
 449
 450 /*
 451  * addrelproviders
 452  *
 453  * add packages fulfilling the relation to whatprovides array
 454  * no exact providers, do range match
 455  *
 456  */
 457
 458 Id *
 459 pool_addrelproviders(Pool *pool, Id d)
 460 {
 461   Reldep *rd = GETRELDEP(pool, d);
 462   Reldep *prd;
 463   Queue plist;
 464   Id buf[16];
 465   Id name = rd->name;
 466   Id evr = rd->evr;
 467   int flags = rd->flags;
 468   Id pid, *pidp;
 469   Id p, *pp, *pp2, *pp3;
 470
 471   d = GETRELID(d);
 472   queue_init_buffer(&plist, buf, sizeof(buf)/sizeof(*buf));
 473   switch (flags)
 474     {
 475     case REL_AND:
 476     case REL_WITH:
 477       pp = pool_whatprovides(pool, name);
 478       pp2 = pool_whatprovides(pool, evr);
 479       while ((p = *pp++) != 0)
 480         {
 481           for (pp3 = pp2; *pp3;)
 482             if (*pp3++ == p)
 483               {
 484                 queue_push(&plist, p);
 485                 break;
 486               }
 487         }
 488       break;
 489     case REL_OR:
 490       pp = pool_whatprovides(pool, name);
 491       while ((p = *pp++) != 0)
 492         queue_push(&plist, p);
 493       pp = pool_whatprovides(pool, evr);
 494       while ((p = *pp++) != 0)
 495         queue_pushunique(&plist, p);
 496       break;
 497     case REL_NAMESPACE:
 498       if (pool->nscallback)
 499         {
 500           p = pool->nscallback(pool, pool->nscallbackdata, name, evr);
 501           if (p > 1)
 502             {
 503               queue_free(&plist);
 504               pool->whatprovides_rel[d] = p;
 505               return pool->whatprovidesdata + p;
 506             }
 507           if (p == 1)
 508             queue_push(&plist, SYSTEMSOLVABLE);
 509         }
 510       break;
 511     default:
 512       break;
 513     }
 514
 515   /* convert to whatprovides id */
 516 #if 0
 517   POOL_DEBUG(DEBUG_1, "addrelproviders: what provides %s?\n", id2str(pool, name));
 518 #endif
 519   if (flags && flags < 8)
 520     {
 521       FOR_PROVIDES(p, pp, name)
 522         {
 523 #if 0
 524           POOL_DEBUG(DEBUG_1, "addrelproviders: checking package %s\n", id2str(pool, pool->p[p].name));
 525 #endif
 526           /* solvable p provides name in some rels */
 527           pidp = pool->solvables[p].repo->idarraydata + pool->solvables[p].provides;
 528           while ((pid = *pidp++) != 0)
 529             {
 530               int pflags;
 531               Id pevr;
 532
 533               if (pid == name)
 534                 {
 535 #ifdef DEBIAN_SEMANTICS
 536                   continue;             /* unversioned provides can
 537                                          * never match versioned deps */
 538 #else
 539                   break;                /* yes, provides all versions */
 540 #endif
 541                 }
 542               if (!ISRELDEP(pid))
 543                 continue;               /* wrong provides name */
 544               prd = GETRELDEP(pool, pid);
 545               if (prd->name != name)
 546                 continue;               /* wrong provides name */
 547               /* right package, both deps are rels */
 548               pflags = prd->flags;
 549               if (!pflags)
 550                 continue;
 551               if (flags == 7 || pflags == 7)
 552                 break; /* included */
 553               if ((pflags & flags & 5) != 0)
 554                 break; /* same direction, match */
 555               pevr = prd->evr;
 556               if (pevr == evr)
 557                 {
 558                   if ((pflags & flags & 2) != 0)
 559                     break; /* both have =, match */
 560                 }
 561               else
 562                 {
 563                   int f = flags == 5 ? 5 : flags == 2 ? pflags : (flags ^ 5) & (pflags | 5);
 564                   if ((f & (1 << (1 + evrcmp(pool, pevr, evr, EVRCMP_MATCH_RELEASE)))) != 0)
 565                     break;
 566                 }
 567             }
 568           if (!pid)
 569             continue;   /* no rel match */
 570           queue_push(&plist, p);
 571         }
 572       /* make our system solvable provide all unknown rpmlib() stuff */
 573       if (plist.count == 0 && !strncmp(id2str(pool, name), "rpmlib(", 7))
 574         queue_push(&plist, SYSTEMSOLVABLE);
 575     }
 576   /* add providers to whatprovides */
 577 #if 0
 578   POOL_DEBUG(DEBUG_1, "addrelproviders: adding %d packages to %d\n", plist.count, d);
 579 #endif
 580   pool->whatprovides_rel[d] = pool_queuetowhatprovides(pool, &plist);
 581   queue_free(&plist);
 582
 583   return pool->whatprovidesdata + pool->whatprovides_rel[d];
 584 }
 585
 586 /*************************************************************************/
 587
 588 void
 589 pool_debug(Pool *pool, int type, const char *format, ...)
 590 {
 591   va_list args;
 592   char buf[1024];
 593
 594   if ((type & SAT_FATAL) == 0)
 595     {
 596       if ((pool->debugmask & type) == 0)
 597         return;
 598     }
 599   va_start(args, format);
 600   if (!pool->debugcallback)
 601     {
 602       if ((type & (SAT_FATAL|SAT_ERROR)) == 0)
 603         vprintf(format, args);
 604       else
 605         vfprintf(stderr, format, args);
 606       return;
 607     }
 608   vsnprintf(buf, sizeof(buf), format, args);
 609   pool->debugcallback(pool, pool->debugcallbackdata, type, buf);
 610 }
 611
 612 void
 613 pool_setdebuglevel(Pool *pool, int level)
 614 {
 615   int mask = SAT_DEBUG_RESULT;
 616   if (level > 0)
 617     mask |= SAT_DEBUG_STATS|SAT_DEBUG_ANALYZE|SAT_DEBUG_UNSOLVABLE;
 618   if (level > 1)
 619     mask |= SAT_DEBUG_JOB|SAT_DEBUG_SOLUTIONS|SAT_DEBUG_POLICY;
 620   if (level > 2)
 621     mask |= SAT_DEBUG_PROPAGATE;
 622   if (level > 3)
 623     mask |= SAT_DEBUG_RULE_CREATION;
 624   if (level > 4)
 625     mask |= SAT_DEBUG_SCHUBI;
 626   pool->debugmask = mask;
 627 }
 628
 629
 630 // EOF