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