methods/rred.cc

   1 // Includes                                                                     /*{{{*/
   2 #include <config.h>
   3
   4 #include <apt-pkg/fileutl.h>
   5 #include <apt-pkg/mmap.h>
   6 #include <apt-pkg/error.h>
   7 #include <apt-pkg/acquire-method.h>
   8 #include <apt-pkg/strutl.h>
   9 #include <apt-pkg/hashes.h>
  10 #include <apt-pkg/configuration.h>
  11
  12 #include <sys/stat.h>
  13 #include <sys/uio.h>
  14 #include <unistd.h>
  15 #include <utime.h>
  16 #include <stdio.h>
  17 #include <errno.h>
  18 #include <zlib.h>
  19 #include <apti18n.h>
  20                                                                                 /*}}}*/
  21 /** \brief RredMethod - ed-style incremential patch method                      {{{
  22  *
  23  *  This method implements a patch functionality similar to "patch --ed" that is
  24  *  used by the "tiffany" incremental packages download stuff. It differs from
  25  *  "ed" insofar that it is way more restricted (and therefore secure).
  26  *  The currently supported ed commands are "<em>c</em>hange", "<em>a</em>dd" and
  27  *  "<em>d</em>elete" (diff doesn't output any other).
  28  *  Additionally the records must be reverse sorted by line number and
  29  *  may not overlap (diff *seems* to produce this kind of output).
  30  * */
  31 class RredMethod : public pkgAcqMethod {
  32         bool Debug;
  33         // the size of this doesn't really matter (except for performance)
  34         const static int BUF_SIZE = 1024;
  35         // the supported ed commands
  36         enum Mode {MODE_CHANGED='c', MODE_DELETED='d', MODE_ADDED='a'};
  37         // return values
  38         enum State {ED_OK, ED_ORDERING, ED_PARSER, ED_FAILURE, MMAP_FAILED};
  39
  40         State applyFile(FileFd &ed_cmds, FILE *in_file, FILE *out_file,
  41                      unsigned long &line, char *buffer, Hashes *hash) const;
  42         void ignoreLineInFile(FILE *fin, char *buffer) const;
  43         void ignoreLineInFile(FileFd &fin, char *buffer) const;
  44         void copyLinesFromFileToFile(FILE *fin, FILE *fout, unsigned int lines,
  45                                     Hashes *hash, char *buffer) const;
  46         void copyLinesFromFileToFile(FileFd &fin, FILE *fout, unsigned int lines,
  47                                     Hashes *hash, char *buffer) const;
  48
  49         State patchFile(FileFd &Patch, FileFd &From, FileFd &out_file, Hashes *hash) const;
  50         State patchMMap(FileFd &Patch, FileFd &From, FileFd &out_file, Hashes *hash) const;
  51
  52 protected:
  53         // the methods main method
  54         virtual bool Fetch(FetchItem *Itm);
  55
  56 public:
  57         RredMethod() : pkgAcqMethod("1.1",SingleInstance | SendConfig), Debug(false) {};
  58 };
  59                                                                                 /*}}}*/
  60 /** \brief applyFile - in reverse order with a tail recursion                   {{{
  61  *
  62  *  As it is expected that the commands are in reversed order in the patch file
  63  *  we check in the first half if the command is valid, but doesn't execute it
  64  *  and move a step deeper. After reaching the end of the file we apply the
  65  *  patches in the correct order: last found command first.
  66  *
  67  *  \param ed_cmds patch file to apply
  68  *  \param in_file base file we want to patch
  69  *  \param out_file file to write the patched result to
  70  *  \param line of command operation
  71  *  \param buffer internal used read/write buffer
  72  *  \param hash the created file for correctness
  73  *  \return the success State of the ed command executor
  74  */
  75 RredMethod::State RredMethod::applyFile(FileFd &ed_cmds, FILE *in_file, FILE *out_file,
  76                         unsigned long &line, char *buffer, Hashes *hash) const {
  77         // get the current command and parse it
  78         if (ed_cmds.ReadLine(buffer, BUF_SIZE) == NULL) {
  79                 if (Debug == true)
  80                         std::clog << "rred: encounter end of file - we can start patching now." << std::endl;
  81                 line = 0;
  82                 return ED_OK;
  83         }
  84
  85         // parse in the effected linenumbers
  86         char* idx;
  87         errno=0;
  88         unsigned long const startline = strtol(buffer, &idx, 10);
  89         if (errno == ERANGE || errno == EINVAL) {
  90                 _error->Errno("rred", "startline is an invalid number");
  91                 return ED_PARSER;
  92         }
  93         if (startline > line) {
  94                 _error->Error("rred: The start line (%lu) of the next command is higher than the last line (%lu). This is not allowed.", startline, line);
  95                 return ED_ORDERING;
  96         }
  97         unsigned long stopline;
  98         if (*idx == ',') {
  99                 idx++;
 100                 errno=0;
 101                 stopline = strtol(idx, &idx, 10);
 102                 if (errno == ERANGE || errno == EINVAL) {
 103                         _error->Errno("rred", "stopline is an invalid number");
 104                         return ED_PARSER;
 105                 }
 106         }
 107         else {
 108                 stopline = startline;
 109         }
 110         line = startline;
 111
 112         // which command to execute on this line(s)?
 113         switch (*idx) {
 114                 case MODE_CHANGED:
 115                         if (Debug == true)
 116                                 std::clog << "Change from line " << startline << " to " << stopline << std::endl;
 117                         break;
 118                 case MODE_ADDED:
 119                         if (Debug == true)
 120                                 std::clog << "Insert after line " << startline << std::endl;
 121                         break;
 122                 case MODE_DELETED:
 123                         if (Debug == true)
 124                                 std::clog << "Delete from line " << startline << " to " << stopline << std::endl;
 125                         break;
 126                 default:
 127                         _error->Error("rred: Unknown ed command '%c'. Abort.", *idx);
 128                         return ED_PARSER;
 129         }
 130         unsigned char mode = *idx;
 131
 132         // save the current position
 133         unsigned const long long pos = ed_cmds.Tell();
 134
 135         // if this is add or change then go to the next full stop
 136         unsigned int data_length = 0;
 137         if (mode == MODE_CHANGED || mode == MODE_ADDED) {
 138                 do {
 139                         ignoreLineInFile(ed_cmds, buffer);
 140                         data_length++;
 141                 }
 142                 while (strncmp(buffer, ".", 1) != 0);
 143                 data_length--; // the dot should not be copied
 144         }
 145
 146         // do the recursive call - the last command is the one we need to execute at first
 147         const State child = applyFile(ed_cmds, in_file, out_file, line, buffer, hash);
 148         if (child != ED_OK) {
 149                 return child;
 150         }
 151
 152         // change and delete are working on "line" - add is done after "line"
 153         if (mode != MODE_ADDED)
 154                 line++;
 155
 156         // first wind to the current position and copy over all unchanged lines
 157         if (line < startline) {
 158                 copyLinesFromFileToFile(in_file, out_file, (startline - line), hash, buffer);
 159                 line = startline;
 160         }
 161
 162         if (mode != MODE_ADDED)
 163                 line--;
 164
 165         // include data from ed script
 166         if (mode == MODE_CHANGED || mode == MODE_ADDED) {
 167                 ed_cmds.Seek(pos);
 168                 copyLinesFromFileToFile(ed_cmds, out_file, data_length, hash, buffer);
 169         }
 170
 171         // ignore the corresponding number of lines from input
 172         if (mode == MODE_CHANGED || mode == MODE_DELETED) {
 173                 while (line < stopline) {
 174                         ignoreLineInFile(in_file, buffer);
 175                         line++;
 176                 }
 177         }
 178         return ED_OK;
 179 }
 180                                                                                 /*}}}*/
 181 void RredMethod::copyLinesFromFileToFile(FILE *fin, FILE *fout, unsigned int lines,/*{{{*/
 182                                         Hashes *hash, char *buffer) const {
 183         while (0 < lines--) {
 184                 do {
 185                         fgets(buffer, BUF_SIZE, fin);
 186                         size_t const written = fwrite(buffer, 1, strlen(buffer), fout);
 187                         hash->Add((unsigned char*)buffer, written);
 188                 } while (strlen(buffer) == (BUF_SIZE - 1) &&
 189                        buffer[BUF_SIZE - 2] != '\n');
 190         }
 191 }
 192                                                                                 /*}}}*/
 193 void RredMethod::copyLinesFromFileToFile(FileFd &fin, FILE *fout, unsigned int lines,/*{{{*/
 194                                         Hashes *hash, char *buffer) const {
 195         while (0 < lines--) {
 196                 do {
 197                         fin.ReadLine(buffer, BUF_SIZE);
 198                         size_t const written = fwrite(buffer, 1, strlen(buffer), fout);
 199                         hash->Add((unsigned char*)buffer, written);
 200                 } while (strlen(buffer) == (BUF_SIZE - 1) &&
 201                        buffer[BUF_SIZE - 2] != '\n');
 202         }
 203 }
 204                                                                                 /*}}}*/
 205 void RredMethod::ignoreLineInFile(FILE *fin, char *buffer) const {              /*{{{*/
 206         fgets(buffer, BUF_SIZE, fin);
 207         while (strlen(buffer) == (BUF_SIZE - 1) &&
 208                buffer[BUF_SIZE - 2] != '\n') {
 209                 fgets(buffer, BUF_SIZE, fin);
 210                 buffer[0] = ' ';
 211         }
 212 }
 213                                                                                 /*}}}*/
 214 void RredMethod::ignoreLineInFile(FileFd &fin, char *buffer) const {            /*{{{*/
 215         fin.ReadLine(buffer, BUF_SIZE);
 216         while (strlen(buffer) == (BUF_SIZE - 1) &&
 217                buffer[BUF_SIZE - 2] != '\n') {
 218                 fin.ReadLine(buffer, BUF_SIZE);
 219                 buffer[0] = ' ';
 220         }
 221 }
 222                                                                                 /*}}}*/
 223 RredMethod::State RredMethod::patchFile(FileFd &Patch, FileFd &From,            /*{{{*/
 224                                         FileFd &out_file, Hashes *hash) const {
 225    char buffer[BUF_SIZE];
 226    FILE* fFrom = fdopen(From.Fd(), "r");
 227    FILE* fTo = fdopen(out_file.Fd(), "w");
 228
 229    /* we do a tail recursion to read the commands in the right order */
 230    unsigned long line = -1; // assign highest possible value
 231    State const result = applyFile(Patch, fFrom, fTo, line, buffer, hash);
 232
 233    /* read the rest from infile */
 234    if (result == ED_OK) {
 235       while (fgets(buffer, BUF_SIZE, fFrom) != NULL) {
 236          size_t const written = fwrite(buffer, 1, strlen(buffer), fTo);
 237          hash->Add((unsigned char*)buffer, written);
 238       }
 239       fflush(fTo);
 240    }
 241    return result;
 242 }
 243                                                                                 /*}}}*/
 244 /* struct EdCommand                                                             {{{*/
 245 #ifdef _POSIX_MAPPED_FILES
 246 struct EdCommand {
 247   size_t data_start;
 248   size_t data_end;
 249   size_t data_lines;
 250   size_t first_line;
 251   size_t last_line;
 252   char type;
 253 };
 254 #define IOV_COUNT 1024 /* Don't really want IOV_MAX since it can be arbitrarily large */
 255 #endif
 256                                                                                 /*}}}*/
 257 RredMethod::State RredMethod::patchMMap(FileFd &Patch, FileFd &From,            /*{{{*/
 258                                         FileFd &out_file, Hashes *hash) const {
 259 #ifdef _POSIX_MAPPED_FILES
 260         MMap ed_cmds(Patch, MMap::ReadOnly);
 261         MMap in_file(From, MMap::ReadOnly);
 262
 263         if (ed_cmds.Size() == 0 || in_file.Size() == 0)
 264                 return MMAP_FAILED;
 265
 266         EdCommand* commands = 0;
 267         size_t command_count = 0;
 268         size_t command_alloc = 0;
 269
 270         const char* begin = (char*) ed_cmds.Data();
 271         const char* end = begin;
 272         const char* ed_end = (char*) ed_cmds.Data() + ed_cmds.Size();
 273
 274         const char* input = (char*) in_file.Data();
 275         const char* input_end = (char*) in_file.Data() + in_file.Size();
 276
 277         size_t i;
 278
 279         /* 1. Parse entire script.  It is executed in reverse order, so we cather it
 280          *    in the `commands' buffer first
 281          */
 282
 283         for(;;) {
 284                 EdCommand cmd;
 285                 cmd.data_start = 0;
 286                 cmd.data_end = 0;
 287
 288                 while(begin != ed_end && *begin == '\n')
 289                         ++begin;
 290                 while(end != ed_end && *end != '\n')
 291                         ++end;
 292                 if(end == ed_end && begin == end)
 293                         break;
 294
 295                 /* Determine command range */
 296                 const char* tmp = begin;
 297
 298                 for(;;) {
 299                         /* atoll is safe despite lacking NUL-termination; we know there's an
 300                          * alphabetic character at end[-1]
 301                          */
 302                         if(tmp == end) {
 303                                 cmd.first_line = atol(begin);
 304                                 cmd.last_line = cmd.first_line;
 305                                 break;
 306                         }
 307                         if(*tmp == ',') {
 308                                 cmd.first_line = atol(begin);
 309                                 cmd.last_line = atol(tmp + 1);
 310                                 break;
 311                         }
 312                         ++tmp;
 313                 }
 314
 315                 // which command to execute on this line(s)?
 316                 switch (end[-1]) {
 317                         case MODE_CHANGED:
 318                                 if (Debug == true)
 319                                         std::clog << "Change from line " << cmd.first_line << " to " << cmd.last_line << std::endl;
 320                                 break;
 321                         case MODE_ADDED:
 322                                 if (Debug == true)
 323                                         std::clog << "Insert after line " << cmd.first_line << std::endl;
 324                                 break;
 325                         case MODE_DELETED:
 326                                 if (Debug == true)
 327                                         std::clog << "Delete from line " << cmd.first_line << " to " << cmd.last_line << std::endl;
 328                                 break;
 329                         default:
 330                                 _error->Error("rred: Unknown ed command '%c'. Abort.", end[-1]);
 331                                 free(commands);
 332                                 return ED_PARSER;
 333                 }
 334                 cmd.type = end[-1];
 335
 336                 /* Determine the size of the inserted text, so we don't have to scan this
 337                  * text again later.
 338                  */
 339                 begin = end + 1;
 340                 end = begin;
 341                 cmd.data_lines = 0;
 342
 343                 if(cmd.type == MODE_ADDED || cmd.type == MODE_CHANGED) {
 344                         cmd.data_start = begin - (char*) ed_cmds.Data();
 345                         while(end != ed_end) {
 346                                 if(*end == '\n') {
 347                                         if(end[-1] == '.' && end[-2] == '\n')
 348                                                 break;
 349                                         ++cmd.data_lines;
 350                                 }
 351                                 ++end;
 352                         }
 353                         cmd.data_end = end - (char*) ed_cmds.Data() - 1;
 354                         begin = end + 1;
 355                         end = begin;
 356                 }
 357                 if(command_count == command_alloc) {
 358                         command_alloc = (command_alloc + 64) * 3 / 2;
 359                         commands = (EdCommand*) realloc(commands, command_alloc * sizeof(EdCommand));
 360                 }
 361                 commands[command_count++] = cmd;
 362         }
 363
 364         struct iovec* iov = new struct iovec[IOV_COUNT];
 365         size_t iov_size = 0;
 366
 367         size_t amount, remaining;
 368         size_t line = 1;
 369         EdCommand* cmd;
 370
 371         /* 2. Execute script.  We gather writes in a `struct iov' array, and flush
 372          *    using writev to minimize the number of system calls.  Data is read
 373          *    directly from the memory mappings of the input file and the script.
 374          */
 375
 376         for(i = command_count; i-- > 0; ) {
 377                 cmd = &commands[i];
 378                 if(cmd->type == MODE_ADDED)
 379                         amount = cmd->first_line + 1;
 380                 else
 381                         amount = cmd->first_line;
 382
 383                 if(line < amount) {
 384                         begin = input;
 385                         while(line != amount) {
 386                                 input = (const char*) memchr(input, '\n', input_end - input);
 387                                 if(!input)
 388                                         break;
 389                                 ++line;
 390                                 ++input;
 391                         }
 392
 393                         iov[iov_size].iov_base = (void*) begin;
 394                         iov[iov_size].iov_len = input - begin;
 395                         hash->Add((const unsigned char*) begin, input - begin);
 396
 397                         if(++iov_size == IOV_COUNT) {
 398                                 writev(out_file.Fd(), iov, IOV_COUNT);
 399                                 iov_size = 0;
 400                         }
 401                 }
 402
 403                 if(cmd->type == MODE_DELETED || cmd->type == MODE_CHANGED) {
 404                         remaining = (cmd->last_line - cmd->first_line) + 1;
 405                         line += remaining;
 406                         while(remaining) {
 407                                 input = (const char*) memchr(input, '\n', input_end - input);
 408                                 if(!input)
 409                                         break;
 410                                 --remaining;
 411                                 ++input;
 412                         }
 413                 }
 414
 415                 if(cmd->type == MODE_CHANGED || cmd->type == MODE_ADDED) {
 416                         if(cmd->data_end != cmd->data_start) {
 417                                 iov[iov_size].iov_base = (void*) ((char*)ed_cmds.Data() + cmd->data_start);
 418                                 iov[iov_size].iov_len = cmd->data_end - cmd->data_start;
 419                                 hash->Add((const unsigned char*) ((char*)ed_cmds.Data() + cmd->data_start),
 420                                 iov[iov_size].iov_len);
 421
 422                                 if(++iov_size == IOV_COUNT) {
 423                                         writev(out_file.Fd(), iov, IOV_COUNT);
 424                                         iov_size = 0;
 425                                 }
 426                         }
 427                 }
 428         }
 429
 430         if(input != input_end) {
 431                 iov[iov_size].iov_base = (void*) input;
 432                 iov[iov_size].iov_len = input_end - input;
 433                 hash->Add((const unsigned char*) input, input_end - input);
 434                 ++iov_size;
 435         }
 436
 437         if(iov_size) {
 438                 writev(out_file.Fd(), iov, iov_size);
 439                 iov_size = 0;
 440         }
 441
 442         for(i = 0; i < iov_size; i += IOV_COUNT) {
 443                 if(iov_size - i < IOV_COUNT)
 444                         writev(out_file.Fd(), iov + i, iov_size - i);
 445                 else
 446                         writev(out_file.Fd(), iov + i, IOV_COUNT);
 447         }
 448
 449         delete [] iov;
 450         free(commands);
 451
 452         return ED_OK;
 453 #else
 454         return MMAP_FAILED;
 455 #endif
 456 }
 457                                                                                 /*}}}*/
 458 bool RredMethod::Fetch(FetchItem *Itm)                                          /*{{{*/
 459 {
 460    Debug = _config->FindB("Debug::pkgAcquire::RRed", false);
 461    URI Get = Itm->Uri;
 462    std::string Path = Get.Host + Get.Path; // To account for relative paths
 463
 464    FetchResult Res;
 465    Res.Filename = Itm->DestFile;
 466    if (Itm->Uri.empty() == true) {
 467       Path = Itm->DestFile;
 468       Itm->DestFile.append(".result");
 469    } else
 470       URIStart(Res);
 471
 472    if (Debug == true)
 473       std::clog << "Patching " << Path << " with " << Path
 474          << ".ed and putting result into " << Itm->DestFile << std::endl;
 475    // Open the source and destination files (the d'tor of FileFd will do
 476    // the cleanup/closing of the fds)
 477    FileFd From(Path,FileFd::ReadOnly);
 478    FileFd Patch(Path+".ed",FileFd::ReadOnly, FileFd::Gzip);
 479    FileFd To(Itm->DestFile,FileFd::WriteAtomic);
 480    To.EraseOnFailure();
 481    if (_error->PendingError() == true)
 482       return false;
 483
 484    Hashes Hash;
 485    // now do the actual patching
 486    State const result = patchMMap(Patch, From, To, &Hash);
 487    if (result == MMAP_FAILED) {
 488       // retry with patchFile
 489       Patch.Seek(0);
 490       From.Seek(0);
 491       To.Open(Itm->DestFile,FileFd::WriteAtomic);
 492       if (_error->PendingError() == true)
 493          return false;
 494       if (patchFile(Patch, From, To, &Hash) != ED_OK) {
 495          return _error->WarningE("rred", _("Could not patch %s with mmap and with file operation usage - the patch seems to be corrupt."), Path.c_str());
 496       } else if (Debug == true) {
 497          std::clog << "rred: finished file patching of " << Path  << " after mmap failed." << std::endl;
 498       }
 499    } else if (result != ED_OK) {
 500       return _error->Errno("rred", _("Could not patch %s with mmap (but no mmap specific fail) - the patch seems to be corrupt."), Path.c_str());
 501    } else if (Debug == true) {
 502       std::clog << "rred: finished mmap patching of " << Path << std::endl;
 503    }
 504
 505    // write out the result
 506    From.Close();
 507    Patch.Close();
 508    To.Close();
 509
 510    /* Transfer the modification times from the patch file
 511       to be able to see in which state the file should be
 512       and use the access time from the "old" file */
 513    struct stat BufBase, BufPatch;
 514    if (stat(Path.c_str(),&BufBase) != 0 ||
 515        stat(std::string(Path+".ed").c_str(),&BufPatch) != 0)
 516       return _error->Errno("stat",_("Failed to stat"));
 517
 518    struct utimbuf TimeBuf;
 519    TimeBuf.actime = BufBase.st_atime;
 520    TimeBuf.modtime = BufPatch.st_mtime;
 521    if (utime(Itm->DestFile.c_str(),&TimeBuf) != 0)
 522       return _error->Errno("utime",_("Failed to set modification time"));
 523
 524    if (stat(Itm->DestFile.c_str(),&BufBase) != 0)
 525       return _error->Errno("stat",_("Failed to stat"));
 526
 527    // return done
 528    Res.LastModified = BufBase.st_mtime;
 529    Res.Size = BufBase.st_size;
 530    Res.TakeHashes(Hash);
 531    URIDone(Res);
 532
 533    return true;
 534 }
 535                                                                                 /*}}}*/
 536 /** \brief Wrapper class for testing rred */                                    /*{{{*/
 537 class TestRredMethod : public RredMethod {
 538 public:
 539         /** \brief Run rred in debug test mode
 540          *
 541          *  This method can be used to run the rred method outside
 542          *  of the "normal" acquire environment for easier testing.
 543          *
 544          *  \param base basename of all files involved in this rred test
 545          */
 546         bool Run(char const *base) {
 547                 _config->CndSet("Debug::pkgAcquire::RRed", "true");
 548                 FetchItem *test = new FetchItem;
 549                 test->DestFile = base;
 550                 return Fetch(test);
 551         }
 552 };
 553                                                                                 /*}}}*/
 554 /** \brief Starter for the rred method (or its test method)                     {{{
 555  *
 556  *  Used without parameters is the normal behavior for methods for
 557  *  the APT acquire system. While this works great for the acquire system
 558  *  it is very hard to test the method and therefore the method also
 559  *  accepts one parameter which will switch it directly to debug test mode:
 560  *  The test mode expects that if "Testfile" is given as parameter
 561  *  the file "Testfile" should be ed-style patched with "Testfile.ed"
 562  *  and will write the result to "Testfile.result".
 563  */
 564 int main(int argc, char *argv[]) {
 565         if (argc <= 1) {
 566                 RredMethod Mth;
 567                 return Mth.Run();
 568         } else {
 569                 TestRredMethod Mth;
 570                 bool result = Mth.Run(argv[1]);
 571                 _error->DumpErrors();
 572                 return result;
 573         }
 574 }
 575                                                                                 /*}}}*/