apt-inst/filelist.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: filelist.cc,v 1.4.2.1 2004/01/16 18:58:50 mdz Exp $
   4 /* ######################################################################
   5
   6    File Listing - Manages a Cache of File -> Package names.
   7
   8    Diversions add some significant complexity to the system. To keep
   9    storage space down in the very special case of a diverted file no
  10    extra bytes are allocated in the Node structure. Instead a diversion
  11    is inserted directly into the hash table and its flag bit set. Every
  12    lookup for that filename will always return the diversion.
  13
  14    The hash buckets are stored in sorted form, with diversions having
  15    the highest sort order. Identical files are assigned the same file
  16    pointer, thus after a search all of the nodes owning that file can be
  17    found by iterating down the bucket.
  18
  19    Re-updates of diversions (another extremely special case) are done by
  20    marking all diversions as untouched, then loading the entire diversion
  21    list again, touching each diversion and then finally going back and
  22    releasing all untouched diversions. It is assumed that the diversion
  23    table will always be quite small and be a very irregular case.
  24
  25    Diversions that are user-installed are represented by a package with
  26    an empty name string.
  27
  28    Conf files are handled like diversions by changing the meaning of the
  29    Pointer field to point to a conf file entry - again to reduce over
  30    head for a special case.
  31
  32    ##################################################################### */
  33                                                                         /*}}}*/
  34 // Include Files                                                        /*{{{*/
  35 #include<config.h>
  36
  37 #include <apt-pkg/filelist.h>
  38 #include <apt-pkg/mmap.h>
  39 #include <apt-pkg/error.h>
  40 #include <apt-pkg/strutl.h>
  41
  42 #include <string.h>
  43 #include <iostream>
  44 #include <apti18n.h>
  45                                                                         /*}}}*/
  46
  47 using namespace std;
  48
  49 // FlCache::Header::Header - Constructor                                /*{{{*/
  50 // ---------------------------------------------------------------------
  51 /* Initialize the header variables. These are the defaults used when
  52    creating new caches */
  53 pkgFLCache::Header::Header()
  54 {
  55    Signature = 0xEA3F1295;
  56
  57    /* Whenever the structures change the major version should be bumped,
  58     whenever the generator changes the minor version should be bumped. */
  59    MajorVersion = 1;
  60    MinorVersion = 0;
  61    Dirty = true;
  62
  63    HeaderSz = sizeof(pkgFLCache::Header);
  64    NodeSz = sizeof(pkgFLCache::Node);
  65    DirSz = sizeof(pkgFLCache::Directory);
  66    PackageSz = sizeof(pkgFLCache::Package);
  67    DiversionSz = sizeof(pkgFLCache::Diversion);
  68    ConfFileSz = sizeof(pkgFLCache::ConfFile);
  69
  70    NodeCount = 0;
  71    DirCount = 0;
  72    PackageCount = 0;
  73    DiversionCount = 0;
  74    ConfFileCount = 0;
  75    HashSize = 1 << 14;
  76
  77    FileHash = 0;
  78    DirTree = 0;
  79    Packages = 0;
  80    Diversions = 0;
  81    UniqNodes = 0;
  82    memset(Pools,0,sizeof(Pools));
  83 }
  84                                                                         /*}}}*/
  85 // FLCache::Header::CheckSizes - Check if the two headers have same *sz /*{{{*/
  86 // ---------------------------------------------------------------------
  87 /* Compare to make sure we are matching versions */
  88 APT_PURE bool pkgFLCache::Header::CheckSizes(Header &Against) const
  89 {
  90    if (HeaderSz == Against.HeaderSz &&
  91        NodeSz == Against.NodeSz &&
  92        DirSz == Against.DirSz &&
  93        DiversionSz == Against.DiversionSz &&
  94        PackageSz == Against.PackageSz &&
  95        ConfFileSz == Against.ConfFileSz)
  96             return true;
  97       return false;
  98 }
  99                                                                         /*}}}*/
 100
 101 // FLCache::pkgFLCache - Constructor                                    /*{{{*/
 102 // ---------------------------------------------------------------------
 103 /* If this is a new cache then a new header and hash table are instantaited
 104    otherwise the existing ones are mearly attached */
 105 pkgFLCache::pkgFLCache(DynamicMMap &Map) : Map(Map)
 106 {
 107    if (_error->PendingError() == true)
 108       return;
 109
 110    LastTreeLookup = 0;
 111    LastLookupSize = 0;
 112
 113    // Apply the typecasts
 114    HeaderP = (Header *)Map.Data();
 115    NodeP = (Node *)Map.Data();
 116    DirP = (Directory *)Map.Data();
 117    DiverP = (Diversion *)Map.Data();
 118    PkgP = (Package *)Map.Data();
 119    ConfP = (ConfFile *)Map.Data();
 120    StrP = (char *)Map.Data();
 121    AnyP = (unsigned char *)Map.Data();
 122
 123    // New mapping, create the basic cache structures
 124    if (Map.Size() == 0)
 125    {
 126       Map.RawAllocate(sizeof(pkgFLCache::Header));
 127       *HeaderP = pkgFLCache::Header();
 128       HeaderP->FileHash = Map.RawAllocate(sizeof(pkgFLCache::Node)*HeaderP->HashSize,
 129                                           sizeof(pkgFLCache::Node))/sizeof(pkgFLCache::Node);
 130    }
 131
 132    FileHash = NodeP + HeaderP->FileHash;
 133
 134    // Setup the dynamic map manager
 135    HeaderP->Dirty = true;
 136    Map.Sync(0,sizeof(pkgFLCache::Header));
 137    Map.UsePools(*HeaderP->Pools,sizeof(HeaderP->Pools)/sizeof(HeaderP->Pools[0]));
 138 }
 139                                                                         /*}}}*/
 140 // FLCache::TreeLookup - Perform a lookup in a generic tree             /*{{{*/
 141 // ---------------------------------------------------------------------
 142 /* This is a simple generic tree lookup. The first three entries of
 143    the Directory structure are used as a template, but any other similar
 144    structure could be used in it's place. */
 145 map_ptrloc pkgFLCache::TreeLookup(map_ptrloc *Base,const char *Text,
 146                                   const char *TextEnd,unsigned long Size,
 147                                   unsigned int *Count,bool Insert)
 148 {
 149    pkgFLCache::Directory *Dir;
 150
 151    // Check our last entry cache
 152    if (LastTreeLookup != 0 && LastLookupSize == Size)
 153    {
 154       Dir = (pkgFLCache::Directory *)(AnyP + LastTreeLookup*Size);
 155       if (stringcmp(Text,TextEnd,StrP + Dir->Name) == 0)
 156          return LastTreeLookup;
 157    }
 158
 159    while (1)
 160    {
 161       // Allocate a new one
 162       if (*Base == 0)
 163       {
 164          if (Insert == false)
 165             return 0;
 166
 167          *Base = Map.Allocate(Size);
 168          if (*Base == 0)
 169             return 0;
 170
 171          (*Count)++;
 172          Dir = (pkgFLCache::Directory *)(AnyP + *Base*Size);
 173          Dir->Name = Map.WriteString(Text,TextEnd - Text);
 174          LastTreeLookup = *Base;
 175          LastLookupSize = Size;
 176          return *Base;
 177       }
 178
 179       // Compare this node
 180       Dir = (pkgFLCache::Directory *)(AnyP + *Base*Size);
 181       int Res = stringcmp(Text,TextEnd,StrP + Dir->Name);
 182       if (Res == 0)
 183       {
 184          LastTreeLookup = *Base;
 185          LastLookupSize = Size;
 186          return *Base;
 187       }
 188
 189       if (Res > 0)
 190          Base = &Dir->Left;
 191       if (Res < 0)
 192          Base = &Dir->Right;
 193    }
 194 }
 195                                                                         /*}}}*/
 196 // FLCache::PrintTree - Print out a tree                                /*{{{*/
 197 // ---------------------------------------------------------------------
 198 /* This is a simple generic tree dumper, ment for debugging. */
 199 void pkgFLCache::PrintTree(map_ptrloc Base,unsigned long Size)
 200 {
 201    if (Base == 0)
 202       return;
 203
 204    pkgFLCache::Directory *Dir = (pkgFLCache::Directory *)(AnyP + Base*Size);
 205    PrintTree(Dir->Left,Size);
 206    cout << (StrP + Dir->Name) << endl;
 207    PrintTree(Dir->Right,Size);
 208 }
 209                                                                         /*}}}*/
 210 // FLCache::GetPkg - Get a package pointer                              /*{{{*/
 211 // ---------------------------------------------------------------------
 212 /* Locate a package by name in it's tree, this is just a wrapper for
 213    TreeLookup */
 214 pkgFLCache::PkgIterator pkgFLCache::GetPkg(const char *Name,const char *NameEnd,
 215                                            bool Insert)
 216 {
 217    if (NameEnd == 0)
 218       NameEnd = Name + strlen(Name);
 219
 220    map_ptrloc Pos = TreeLookup(&HeaderP->Packages,Name,NameEnd,
 221                                sizeof(pkgFLCache::Package),
 222                                &HeaderP->PackageCount,Insert);
 223    if (Pos == 0)
 224       return pkgFLCache::PkgIterator();
 225    return pkgFLCache::PkgIterator(*this,PkgP + Pos);
 226 }
 227                                                                         /*}}}*/
 228 // FLCache::GetNode - Get the node associated with the filename         /*{{{*/
 229 // ---------------------------------------------------------------------
 230 /* Lookup a node in the hash table. If Insert is true then a new node is
 231    always inserted. The hash table can have multiple instances of a
 232    single name available. A search returns the first. It is important
 233    that additions for the same name insert after the first entry of
 234    the name group. */
 235 pkgFLCache::NodeIterator pkgFLCache::GetNode(const char *Name,
 236                                              const char *NameEnd,
 237                                              map_ptrloc Loc,
 238                                              bool Insert,bool Divert)
 239 {
 240    // Split the name into file and directory, hashing as it is copied
 241    const char *File = Name;
 242    unsigned long HashPos = 0;
 243    for (const char *I = Name; I < NameEnd; I++)
 244    {
 245       HashPos = 1637*HashPos + *I;
 246       if (*I == '/')
 247          File = I;
 248    }
 249
 250    // Search for it
 251    Node *Hash = NodeP + HeaderP->FileHash + (HashPos % HeaderP->HashSize);
 252    int Res = 0;
 253    map_ptrloc FilePtr = 0;
 254    while (Hash->Pointer != 0)
 255    {
 256       // Compare
 257       Res = stringcmp(File+1,NameEnd,StrP + Hash->File);
 258       if (Res == 0)
 259          Res = stringcmp(Name,File,StrP + DirP[Hash->Dir].Name);
 260
 261       // Diversion?
 262       if (Res == 0 && Insert == true)
 263       {
 264          /* Dir and File match exactly, we need to reuse the file name
 265             when we link it in */
 266          FilePtr = Hash->File;
 267          Res = Divert - ((Hash->Flags & Node::Diversion) == Node::Diversion);
 268       }
 269
 270       // Is a match
 271       if (Res == 0)
 272       {
 273          if (Insert == false)
 274             return NodeIterator(*this,Hash);
 275
 276          // Only one diversion per name!
 277          if (Divert == true)
 278             return NodeIterator(*this,Hash);
 279          break;
 280       }
 281
 282       // Out of sort order
 283       if (Res > 0)
 284          break;
 285
 286       if (Hash->Next != 0)
 287          Hash = NodeP + Hash->Next;
 288       else
 289          break;
 290    }
 291
 292    // Fail, not found
 293    if (Insert == false)
 294       return NodeIterator(*this);
 295
 296    // Find a directory node
 297    map_ptrloc Dir = TreeLookup(&HeaderP->DirTree,Name,File,
 298                                sizeof(pkgFLCache::Directory),
 299                                &HeaderP->DirCount,true);
 300    if (Dir == 0)
 301       return NodeIterator(*this);
 302
 303    // Allocate a new node
 304    if (Hash->Pointer != 0)
 305    {
 306       // Overwrite or append
 307       if (Res > 0)
 308       {
 309          Node *Next = NodeP + Map.Allocate(sizeof(*Hash));
 310          if (Next == NodeP)
 311             return NodeIterator(*this);
 312          *Next = *Hash;
 313          Hash->Next = Next - NodeP;
 314       }
 315       else
 316       {
 317          unsigned long NewNext = Map.Allocate(sizeof(*Hash));
 318          if (NewNext == 0)
 319             return NodeIterator(*this);
 320          NodeP[NewNext].Next = Hash->Next;
 321          Hash->Next = NewNext;
 322          Hash = NodeP + Hash->Next;
 323       }
 324    }
 325
 326    // Insert into the new item
 327    Hash->Dir = Dir;
 328    Hash->Pointer = Loc;
 329    Hash->Flags = 0;
 330    if (Divert == true)
 331       Hash->Flags |= Node::Diversion;
 332
 333    if (FilePtr != 0)
 334       Hash->File = FilePtr;
 335    else
 336    {
 337       HeaderP->UniqNodes++;
 338       Hash->File = Map.WriteString(File+1,NameEnd - File-1);
 339    }
 340
 341    // Link the node to the package list
 342    if (Divert == false && Loc == 0)
 343    {
 344       Hash->Next = PkgP[Loc].Files;
 345       PkgP[Loc].Files = Hash - NodeP;
 346    }
 347
 348    HeaderP->NodeCount++;
 349    return NodeIterator(*this,Hash);
 350 }
 351                                                                         /*}}}*/
 352 // FLCache::HashNode - Return the hash bucket for the node              /*{{{*/
 353 // ---------------------------------------------------------------------
 354 /* This is one of two hashing functions. The other is inlined into the
 355    GetNode routine. */
 356 APT_PURE pkgFLCache::Node *pkgFLCache::HashNode(NodeIterator const &Nde)
 357 {
 358    // Hash the node
 359    unsigned long HashPos = 0;
 360    for (const char *I = Nde.DirN(); *I != 0; I++)
 361       HashPos = 1637*HashPos + *I;
 362    HashPos = 1637*HashPos + '/';
 363    for (const char *I = Nde.File(); *I != 0; I++)
 364       HashPos = 1637*HashPos + *I;
 365    return NodeP + HeaderP->FileHash + (HashPos % HeaderP->HashSize);
 366 }
 367                                                                         /*}}}*/
 368 // FLCache::DropNode - Drop a node from the hash table                  /*{{{*/
 369 // ---------------------------------------------------------------------
 370 /* This erases a node from the hash table. Note that this does not unlink
 371    the node from the package linked list. */
 372 void pkgFLCache::DropNode(map_ptrloc N)
 373 {
 374    if (N == 0)
 375       return;
 376
 377    NodeIterator Nde(*this,NodeP + N);
 378
 379    if (Nde->NextPkg != 0)
 380       _error->Warning(_("DropNode called on still linked node"));
 381
 382    // Locate it in the hash table
 383    Node *Last = 0;
 384    Node *Hash = HashNode(Nde);
 385    while (Hash->Pointer != 0)
 386    {
 387       // Got it
 388       if (Hash == Nde)
 389       {
 390          // Top of the bucket..
 391          if (Last == 0)
 392          {
 393             Hash->Pointer = 0;
 394             if (Hash->Next == 0)
 395                return;
 396             *Hash = NodeP[Hash->Next];
 397             // Release Hash->Next
 398             return;
 399          }
 400          Last->Next = Hash->Next;
 401          // Release Hash
 402          return;
 403       }
 404
 405       Last = Hash;
 406       if (Hash->Next != 0)
 407          Hash = NodeP + Hash->Next;
 408       else
 409          break;
 410    }
 411
 412    _error->Error(_("Failed to locate the hash element!"));
 413 }
 414                                                                         /*}}}*/
 415 // FLCache::BeginDiverLoad - Start reading new diversions               /*{{{*/
 416 // ---------------------------------------------------------------------
 417 /* Tag all the diversions as untouched */
 418 void pkgFLCache::BeginDiverLoad()
 419 {
 420    for (DiverIterator I = DiverBegin(); I.end() == false; I++)
 421       I->Flags = 0;
 422 }
 423                                                                         /*}}}*/
 424 // FLCache::FinishDiverLoad - Finish up a new diversion load            /*{{{*/
 425 // ---------------------------------------------------------------------
 426 /* This drops any untouched diversions. In effect removing any diversions
 427    that where not loaded (ie missing from the diversion file) */
 428 void pkgFLCache::FinishDiverLoad()
 429 {
 430    map_ptrloc *Cur = &HeaderP->Diversions;
 431    while (*Cur != 0)
 432    {
 433       Diversion *Div = DiverP + *Cur;
 434       if ((Div->Flags & Diversion::Touched) == Diversion::Touched)
 435       {
 436          Cur = &Div->Next;
 437          continue;
 438       }
 439
 440       // Purge!
 441       DropNode(Div->DivertTo);
 442       DropNode(Div->DivertFrom);
 443       *Cur = Div->Next;
 444    }
 445 }
 446                                                                         /*}}}*/
 447 // FLCache::AddDiversion - Add a new diversion                          /*{{{*/
 448 // ---------------------------------------------------------------------
 449 /* Add a new diversion to the diverion tables and make sure that it is
 450    unique and non-chaining. */
 451 bool pkgFLCache::AddDiversion(PkgIterator const &Owner,
 452                               const char *From,const char *To)
 453 {
 454    /* Locate the two hash nodes we are going to manipulate. If there
 455       are pre-existing diversions then they will be returned */
 456    NodeIterator FromN = GetNode(From,From+strlen(From),0,true,true);
 457    NodeIterator ToN = GetNode(To,To+strlen(To),0,true,true);
 458    if (FromN.end() == true || ToN.end() == true)
 459       return _error->Error(_("Failed to allocate diversion"));
 460
 461    // Should never happen
 462    if ((FromN->Flags & Node::Diversion) != Node::Diversion ||
 463        (ToN->Flags & Node::Diversion) != Node::Diversion)
 464       return _error->Error(_("Internal error in AddDiversion"));
 465
 466    // Now, try to reclaim an existing diversion..
 467    map_ptrloc Diver = 0;
 468    if (FromN->Pointer != 0)
 469       Diver = FromN->Pointer;
 470
 471    /* Make sure from and to point to the same diversion, if they don't
 472       then we are trying to intermix diversions - very bad */
 473    if (ToN->Pointer != 0 && ToN->Pointer != Diver)
 474    {
 475       // It could be that the other diversion is no longer in use
 476       if ((DiverP[ToN->Pointer].Flags & Diversion::Touched) == Diversion::Touched)
 477          return _error->Error(_("Trying to overwrite a diversion, %s -> %s and %s/%s"),
 478                               From,To,ToN.File(),ToN.Dir().Name());
 479
 480       // We can erase it.
 481       Diversion *Div = DiverP + ToN->Pointer;
 482       ToN->Pointer = 0;
 483
 484       if (Div->DivertTo == ToN.Offset())
 485          Div->DivertTo = 0;
 486       if (Div->DivertFrom == ToN.Offset())
 487          Div->DivertFrom = 0;
 488
 489       // This diversion will be cleaned up by FinishDiverLoad
 490    }
 491
 492    // Allocate a new diversion
 493    if (Diver == 0)
 494    {
 495       Diver = Map.Allocate(sizeof(Diversion));
 496       if (Diver == 0)
 497          return false;
 498       DiverP[Diver].Next = HeaderP->Diversions;
 499       HeaderP->Diversions = Diver;
 500       HeaderP->DiversionCount++;
 501    }
 502
 503    // Can only have one diversion of the same files
 504    Diversion *Div = DiverP + Diver;
 505    if ((Div->Flags & Diversion::Touched) == Diversion::Touched)
 506       return _error->Error(_("Double add of diversion %s -> %s"),From,To);
 507
 508    // Setup the From/To links
 509    if (Div->DivertFrom != FromN.Offset() && Div->DivertFrom != ToN.Offset())
 510       DropNode(Div->DivertFrom);
 511    Div->DivertFrom = FromN.Offset();
 512    if (Div->DivertTo != FromN.Offset() && Div->DivertTo != ToN.Offset())
 513       DropNode(Div->DivertTo);
 514    Div->DivertTo = ToN.Offset();
 515
 516    // Link it to the two nodes
 517    FromN->Pointer = Diver;
 518    ToN->Pointer = Diver;
 519
 520    // And the package
 521    Div->OwnerPkg = Owner.Offset();
 522    Div->Flags |= Diversion::Touched;
 523
 524    return true;
 525 }
 526                                                                         /*}}}*/
 527 // FLCache::AddConfFile - Add a new configuration file                  /*{{{*/
 528 // ---------------------------------------------------------------------
 529 /* This simply adds a new conf file node to the hash table. This is only
 530    used by the status file reader. It associates a hash with each conf
 531    file entry that exists in the status file and the list file for
 532    the proper package. Duplicate conf files (across packages) are left
 533    up to other routines to deal with. */
 534 bool pkgFLCache::AddConfFile(const char *Name,const char *NameEnd,
 535                              PkgIterator const &Owner,
 536                              const unsigned char *Sum)
 537 {
 538    NodeIterator Nde = GetNode(Name,NameEnd,0,false,false);
 539    if (Nde.end() == true)
 540       return true;
 541
 542    unsigned long File = Nde->File;
 543    for (; Nde->File == File && Nde.end() == false; Nde++)
 544    {
 545       if (Nde.RealPackage() != Owner)
 546          continue;
 547
 548       if ((Nde->Flags & Node::ConfFile) == Node::ConfFile)
 549          return _error->Error(_("Duplicate conf file %s/%s"),Nde.DirN(),Nde.File());
 550
 551       // Allocate a new conf file structure
 552       map_ptrloc Conf = Map.Allocate(sizeof(ConfFile));
 553       if (Conf == 0)
 554          return false;
 555       ConfP[Conf].OwnerPkg = Owner.Offset();
 556       memcpy(ConfP[Conf].MD5,Sum,sizeof(ConfP[Conf].MD5));
 557
 558       Nde->Pointer = Conf;
 559       Nde->Flags |= Node::ConfFile;
 560       return true;
 561    }
 562
 563    /* This means the conf file has been replaced, but the entry in the
 564       status file was not updated */
 565    return true;
 566 }
 567                                                                         /*}}}*/
 568
 569 // NodeIterator::RealPackage - Return the package for this node         /*{{{*/
 570 // ---------------------------------------------------------------------
 571 /* Since the package pointer is indirected in all sorts of interesting ways
 572    this is used to get a pointer to the owning package */
 573 APT_PURE pkgFLCache::Package *pkgFLCache::NodeIterator::RealPackage() const
 574 {
 575    if (Nde->Pointer == 0)
 576       return 0;
 577
 578    if ((Nde->Flags & Node::ConfFile) == Node::ConfFile)
 579       return Owner->PkgP + Owner->ConfP[Nde->Pointer].OwnerPkg;
 580
 581    // Diversions are ignored
 582    if ((Nde->Flags & Node::Diversion) == Node::Diversion)
 583       return 0;
 584
 585    return Owner->PkgP + Nde->Pointer;
 586 }
 587                                                                         /*}}}*/