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