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