apt-inst/filelist.cc

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