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