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