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