[apt.git] / methods / rred.cc

// Includes									/*{{{*/
#include <config.h>

#include <apt-pkg/fileutl.h>
#include <apt-pkg/mmap.h>
#include <apt-pkg/error.h>
#include <apt-pkg/acquire-method.h>
#include <apt-pkg/strutl.h>
#include <apt-pkg/hashes.h>
#include <apt-pkg/configuration.h>

#include <sys/stat.h>
#include <sys/uio.h>
#include <unistd.h>
#include <utime.h>
#include <stdio.h>
#include <errno.h>
#include <apti18n.h>
										/*}}}*/
/** \brief RredMethod - ed-style incremential patch method			{{{
 *
 *  This method implements a patch functionality similar to "patch --ed" that is
 *  used by the "tiffany" incremental packages download stuff. It differs from
 *  "ed" insofar that it is way more restricted (and therefore secure).
 *  The currently supported ed commands are "<em>c</em>hange", "<em>a</em>dd" and
 *  "<em>d</em>elete" (diff doesn't output any other).
 *  Additionally the records must be reverse sorted by line number and
 *  may not overlap (diff *seems* to produce this kind of output).
 * */
class RredMethod : public pkgAcqMethod {
	bool Debug;
	// the size of this doesn't really matter (except for performance)
	const static int BUF_SIZE = 1024;
	// the supported ed commands
	enum Mode {MODE_CHANGED='c', MODE_DELETED='d', MODE_ADDED='a'};
	// return values
	enum State {ED_OK, ED_ORDERING, ED_PARSER, ED_FAILURE, MMAP_FAILED};

	State applyFile(FileFd &ed_cmds, FileFd &in_file, FileFd &out_file,
	             unsigned long &line, char *buffer, Hashes *hash) const;
	void ignoreLineInFile(FileFd &fin, char *buffer) const;
	void copyLinesFromFileToFile(FileFd &fin, FileFd &fout, unsigned int lines,
	                            Hashes *hash, char *buffer) const;

	State patchFile(FileFd &Patch, FileFd &From, FileFd &out_file, Hashes *hash) const;
	State patchMMap(FileFd &Patch, FileFd &From, FileFd &out_file, Hashes *hash) const;

protected:
	// the methods main method
	virtual bool Fetch(FetchItem *Itm);

public:
	RredMethod() : pkgAcqMethod("1.1",SingleInstance | SendConfig), Debug(false) {};
};
										/*}}}*/
/** \brief applyFile - in reverse order with a tail recursion			{{{
 *
 *  As it is expected that the commands are in reversed order in the patch file
 *  we check in the first half if the command is valid, but doesn't execute it
 *  and move a step deeper. After reaching the end of the file we apply the
 *  patches in the correct order: last found command first.
 *
 *  \param ed_cmds patch file to apply
 *  \param in_file base file we want to patch
 *  \param out_file file to write the patched result to
 *  \param line of command operation
 *  \param buffer internal used read/write buffer
 *  \param hash the created file for correctness
 *  \return the success State of the ed command executor
 */
RredMethod::State RredMethod::applyFile(FileFd &ed_cmds, FileFd &in_file, FileFd &out_file,
			unsigned long &line, char *buffer, Hashes *hash) const {
	// get the current command and parse it
	if (ed_cmds.ReadLine(buffer, BUF_SIZE) == NULL) {
		if (Debug == true)
			std::clog << "rred: encounter end of file - we can start patching now." << std::endl;
		line = 0;
		return ED_OK;
	}

	// parse in the effected linenumbers
	char* idx;
	errno=0;
	unsigned long const startline = strtol(buffer, &idx, 10);
	if (errno == ERANGE || errno == EINVAL) {
		_error->Errno("rred", "startline is an invalid number");
		return ED_PARSER;
	}
	if (startline > line) {
		_error->Error("rred: The start line (%lu) of the next command is higher than the last line (%lu). This is not allowed.", startline, line);
		return ED_ORDERING;
	}
	unsigned long stopline;
	if (*idx == ',') {
		idx++;
		errno=0;
		stopline = strtol(idx, &idx, 10);
		if (errno == ERANGE || errno == EINVAL) {
			_error->Errno("rred", "stopline is an invalid number");
			return ED_PARSER;
		}
	}
	else {
		stopline = startline;
	}
	line = startline;

	// which command to execute on this line(s)?
	switch (*idx) {
		case MODE_CHANGED:
			if (Debug == true)
				std::clog << "Change from line " << startline << " to " << stopline << std::endl;
			break;
		case MODE_ADDED:
			if (Debug == true)
				std::clog << "Insert after line " << startline << std::endl;
			break;
		case MODE_DELETED:
			if (Debug == true)
				std::clog << "Delete from line " << startline << " to " << stopline << std::endl;
			break;
		default:
			_error->Error("rred: Unknown ed command '%c'. Abort.", *idx);
			return ED_PARSER;
	}
	unsigned char mode = *idx;

	// save the current position
	unsigned const long long pos = ed_cmds.Tell();

	// if this is add or change then go to the next full stop
	unsigned int data_length = 0;
	if (mode == MODE_CHANGED || mode == MODE_ADDED) {
		do {
			ignoreLineInFile(ed_cmds, buffer);
			data_length++;
		}
		while (strncmp(buffer, ".", 1) != 0);
		data_length--; // the dot should not be copied
	}

	// do the recursive call - the last command is the one we need to execute at first
	const State child = applyFile(ed_cmds, in_file, out_file, line, buffer, hash);
	if (child != ED_OK) {
		return child;
	}

	// change and delete are working on "line" - add is done after "line"
	if (mode != MODE_ADDED)
		line++;

	// first wind to the current position and copy over all unchanged lines
	if (line < startline) {
		copyLinesFromFileToFile(in_file, out_file, (startline - line), hash, buffer);
		line = startline;
	}

	if (mode != MODE_ADDED)
		line--;

	// include data from ed script
	if (mode == MODE_CHANGED || mode == MODE_ADDED) {
		ed_cmds.Seek(pos);
		copyLinesFromFileToFile(ed_cmds, out_file, data_length, hash, buffer);
	}

	// ignore the corresponding number of lines from input
	if (mode == MODE_CHANGED || mode == MODE_DELETED) {
		while (line < stopline) {
			ignoreLineInFile(in_file, buffer);
			line++;
		}
	}
	return ED_OK;
}
										/*}}}*/
void RredMethod::copyLinesFromFileToFile(FileFd &fin, FileFd &fout, unsigned int lines,/*{{{*/
					Hashes *hash, char *buffer) const {
	while (0 < lines--) {
		do {
			fin.ReadLine(buffer, BUF_SIZE);
			unsigned long long const towrite = strlen(buffer);
			fout.Write(buffer, towrite);
			hash->Add((unsigned char*)buffer, towrite);
		} while (strlen(buffer) == (BUF_SIZE - 1) &&
		       buffer[BUF_SIZE - 2] != '\n');
	}
}
										/*}}}*/
void RredMethod::ignoreLineInFile(FileFd &fin, char *buffer) const {		/*{{{*/
	fin.ReadLine(buffer, BUF_SIZE);
	while (strlen(buffer) == (BUF_SIZE - 1) &&
	       buffer[BUF_SIZE - 2] != '\n') {
		fin.ReadLine(buffer, BUF_SIZE);
		buffer[0] = ' ';
	}
}
										/*}}}*/
RredMethod::State RredMethod::patchFile(FileFd &Patch, FileFd &From,		/*{{{*/
					FileFd &out_file, Hashes *hash) const {
   char buffer[BUF_SIZE];

   /* we do a tail recursion to read the commands in the right order */
   unsigned long line = -1; // assign highest possible value
   State const result = applyFile(Patch, From, out_file, line, buffer, hash);
   
   /* read the rest from infile */
   if (result == ED_OK) {
      while (From.ReadLine(buffer, BUF_SIZE) != NULL) {
	 unsigned long long const towrite = strlen(buffer);
	 out_file.Write(buffer, towrite);
	 hash->Add((unsigned char*)buffer, towrite);
      }
   }
   return result;
}
										/*}}}*/
/* struct EdCommand								{{{*/
#ifdef _POSIX_MAPPED_FILES
struct EdCommand {
  size_t data_start;
  size_t data_end;
  size_t data_lines;
  size_t first_line;
  size_t last_line;
  char type;
};
#define IOV_COUNT 1024 /* Don't really want IOV_MAX since it can be arbitrarily large */
static ssize_t retry_writev(int fd, const struct iovec *iov, int iovcnt) {
	ssize_t Res;
	errno = 0;
	ssize_t i = 0;
	do {
		Res = writev(fd, iov + i, iovcnt);
		if (Res < 0 && errno == EINTR)
			continue;
		if (Res < 0)
			return _error->Errno("writev",_("Write error"));
		iovcnt -= Res;
		i += Res;
	} while (Res > 0 && iovcnt > 0);
	return i;
}
#endif
										/*}}}*/
RredMethod::State RredMethod::patchMMap(FileFd &Patch, FileFd &From,		/*{{{*/
					FileFd &out_file, Hashes *hash) const {
#ifdef _POSIX_MAPPED_FILES
	MMap ed_cmds(Patch, MMap::ReadOnly);
	MMap in_file(From, MMap::ReadOnly);

	unsigned long long const ed_size = ed_cmds.Size();
	unsigned long long const in_size = in_file.Size();
	if (ed_size == 0 || in_size == 0)
		return MMAP_FAILED;

	EdCommand* commands = 0;
	size_t command_count = 0;
	size_t command_alloc = 0;

	const char* begin = (char*) ed_cmds.Data();
	const char* end = begin;
	const char* ed_end = (char*) ed_cmds.Data() + ed_size;

	const char* input = (char*) in_file.Data();
	const char* input_end = (char*) in_file.Data() + in_size;

	size_t i;

	/* 1. Parse entire script.  It is executed in reverse order, so we cather it
	 *    in the `commands' buffer first
	 */

	for(;;) {
		EdCommand cmd;
		cmd.data_start = 0;
		cmd.data_end = 0;

		while(begin != ed_end && *begin == '\n')
			++begin;
		while(end != ed_end && *end != '\n')
			++end;
		if(end == ed_end && begin == end)
			break;

		/* Determine command range */
		const char* tmp = begin;

		for(;;) {
			/* atoll is safe despite lacking NUL-termination; we know there's an
			 * alphabetic character at end[-1]
			 */
			if(tmp == end) {
				cmd.first_line = atol(begin);
				cmd.last_line = cmd.first_line;
				break;
			}
			if(*tmp == ',') {
				cmd.first_line = atol(begin);
				cmd.last_line = atol(tmp + 1);
				break;
			}
			++tmp;
		}

		// which command to execute on this line(s)?
		switch (end[-1]) {
			case MODE_CHANGED:
				if (Debug == true)
					std::clog << "Change from line " << cmd.first_line << " to " << cmd.last_line << std::endl;
				break;
			case MODE_ADDED:
				if (Debug == true)
					std::clog << "Insert after line " << cmd.first_line << std::endl;
				break;
			case MODE_DELETED:
				if (Debug == true)
					std::clog << "Delete from line " << cmd.first_line << " to " << cmd.last_line << std::endl;
				break;
			default:
				_error->Error("rred: Unknown ed command '%c'. Abort.", end[-1]);
				free(commands);
				return ED_PARSER;
		}
		cmd.type = end[-1];

		/* Determine the size of the inserted text, so we don't have to scan this
		 * text again later.
		 */
		begin = end + 1;
		end = begin;
		cmd.data_lines = 0;

		if(cmd.type == MODE_ADDED || cmd.type == MODE_CHANGED) {
			cmd.data_start = begin - (char*) ed_cmds.Data();
			while(end != ed_end) {
				if(*end == '\n') {
					if(end[-1] == '.' && end[-2] == '\n')
						break;
					++cmd.data_lines;
				}
				++end;
			}
			cmd.data_end = end - (char*) ed_cmds.Data() - 1;
			begin = end + 1;
			end = begin;
		}
		if(command_count == command_alloc) {
			command_alloc = (command_alloc + 64) * 3 / 2;
			EdCommand* newCommands = (EdCommand*) realloc(commands, command_alloc * sizeof(EdCommand));
			if (newCommands == NULL) {
				free(commands);
				return MMAP_FAILED;
			}
			commands = newCommands;
		}
		commands[command_count++] = cmd;
	}

	struct iovec* iov = new struct iovec[IOV_COUNT];
	size_t iov_size = 0;

	size_t amount, remaining;
	size_t line = 1;
	EdCommand* cmd;

	/* 2. Execute script.  We gather writes in a `struct iov' array, and flush
	 *    using writev to minimize the number of system calls.  Data is read
	 *    directly from the memory mappings of the input file and the script.
	 */

	for(i = command_count; i-- > 0; ) {
		cmd = &commands[i];
		if(cmd->type == MODE_ADDED)
			amount = cmd->first_line + 1;
		else
			amount = cmd->first_line;

		if(line < amount) {
			begin = input;
			while(line != amount) {
				input = (const char*) memchr(input, '\n', input_end - input);
				if(!input)
					break;
				++line;
				++input;
			}

			iov[iov_size].iov_base = (void*) begin;
			iov[iov_size].iov_len = input - begin;
			hash->Add((const unsigned char*) begin, input - begin);

			if(++iov_size == IOV_COUNT) {
				retry_writev(out_file.Fd(), iov, IOV_COUNT);
				iov_size = 0;
			}
		}

		if(cmd->type == MODE_DELETED || cmd->type == MODE_CHANGED) {
			remaining = (cmd->last_line - cmd->first_line) + 1;
			line += remaining;
			while(remaining) {
				input = (const char*) memchr(input, '\n', input_end - input);
				if(!input)
					break;
				--remaining;
				++input;
			}
		}

		if(cmd->type == MODE_CHANGED || cmd->type == MODE_ADDED) {
			if(cmd->data_end != cmd->data_start) {
				iov[iov_size].iov_base = (void*) ((char*)ed_cmds.Data() + cmd->data_start);
				iov[iov_size].iov_len = cmd->data_end - cmd->data_start;
				hash->Add((const unsigned char*) ((char*)ed_cmds.Data() + cmd->data_start),
				iov[iov_size].iov_len);

				if(++iov_size == IOV_COUNT) {
					retry_writev(out_file.Fd(), iov, IOV_COUNT);
					iov_size = 0;
				}
			}
		}
	}

	if(input != input_end) {
		iov[iov_size].iov_base = (void*) input;
		iov[iov_size].iov_len = input_end - input;
		hash->Add((const unsigned char*) input, input_end - input);
		++iov_size;
	}

	if(iov_size) {
		retry_writev(out_file.Fd(), iov, iov_size);
		iov_size = 0;
	}

	for(i = 0; i < iov_size; i += IOV_COUNT) {
		if(iov_size - i < IOV_COUNT)
			retry_writev(out_file.Fd(), iov + i, iov_size - i);
		else
			retry_writev(out_file.Fd(), iov + i, IOV_COUNT);
	}

	delete [] iov;
	free(commands);

	return ED_OK;
#else
	return MMAP_FAILED;
#endif
}
										/*}}}*/
bool RredMethod::Fetch(FetchItem *Itm)						/*{{{*/
{
   Debug = _config->FindB("Debug::pkgAcquire::RRed", false);
   URI Get = Itm->Uri;
   std::string Path = Get.Host + Get.Path; // To account for relative paths

   FetchResult Res;
   Res.Filename = Itm->DestFile;
   if (Itm->Uri.empty() == true) {
      Path = Itm->DestFile;
      Itm->DestFile.append(".result");
   } else
      URIStart(Res);

   if (Debug == true) 
      std::clog << "Patching " << Path << " with " << Path 
         << ".ed and putting result into " << Itm->DestFile << std::endl;
   // Open the source and destination files (the d'tor of FileFd will do 
   // the cleanup/closing of the fds)
   FileFd From(Path,FileFd::ReadOnly);
   FileFd Patch(Path+".ed",FileFd::ReadOnly, FileFd::Gzip);
   FileFd To(Itm->DestFile,FileFd::WriteAtomic);   
   To.EraseOnFailure();
   if (_error->PendingError() == true)
      return false;
   
   Hashes Hash;
   // now do the actual patching
   State const result = patchMMap(Patch, From, To, &Hash);
   if (result == MMAP_FAILED) {
      // retry with patchFile
      Patch.Seek(0);
      From.Seek(0);
      To.Open(Itm->DestFile,FileFd::WriteAtomic);
      if (_error->PendingError() == true)
         return false;
      if (patchFile(Patch, From, To, &Hash) != ED_OK) {
	 return _error->WarningE("rred", _("Could not patch %s with mmap and with file operation usage - the patch seems to be corrupt."), Path.c_str());
      } else if (Debug == true) {
	 std::clog << "rred: finished file patching of " << Path  << " after mmap failed." << std::endl;
      }
   } else if (result != ED_OK) {
      return _error->Errno("rred", _("Could not patch %s with mmap (but no mmap specific fail) - the patch seems to be corrupt."), Path.c_str());
   } else if (Debug == true) {
      std::clog << "rred: finished mmap patching of " << Path << std::endl;
   }

   // write out the result
   From.Close();
   Patch.Close();
   To.Close();

   /* Transfer the modification times from the patch file
      to be able to see in which state the file should be
      and use the access time from the "old" file */
   struct stat BufBase, BufPatch;
   if (stat(Path.c_str(),&BufBase) != 0 ||
       stat(std::string(Path+".ed").c_str(),&BufPatch) != 0)
      return _error->Errno("stat",_("Failed to stat"));

   struct utimbuf TimeBuf;
   TimeBuf.actime = BufBase.st_atime;
   TimeBuf.modtime = BufPatch.st_mtime;
   if (utime(Itm->DestFile.c_str(),&TimeBuf) != 0)
      return _error->Errno("utime",_("Failed to set modification time"));

   if (stat(Itm->DestFile.c_str(),&BufBase) != 0)
      return _error->Errno("stat",_("Failed to stat"));

   // return done
   Res.LastModified = BufBase.st_mtime;
   Res.Size = BufBase.st_size;
   Res.TakeHashes(Hash);
   URIDone(Res);

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