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