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