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