From ce6cd75dc367b92f65e4fb539dd166d0f3361f8c Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 31 Aug 2016 11:36:44 +0200 Subject: Fix segfault and out-of-bounds read in Binary fields If a Binary field contains one or more spaces before a comma, the code produced a segmentation fault, as it accidentally set a pointer to 0 instead of the value of the pointer. If the comma is at the beginning of the field, the code would create a binStartNext that points one element before the start of the string, which is undefined behavior. We also need to check that we do not exit the string during the replacement of spaces before commas: A string of the form " ," would normally exit the boundary of the Buffer: binStartNext = offset 1 ',' binEnd = offset 0 ' ' isspace_ascii(*binEnd) = true => --binEnd => binEnd = - 1 We get rid of the problem by only allowing spaces to be eliminated if they are not the first character of the buffer: binStartNext = offset 1 ',' binEnd = offset 0 ' ' binEnd > buffer = false, isspace_ascii(*binEnd) = true => exit loop => binEnd remains 0 --- apt-pkg/deb/debsrcrecords.cc | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/deb/debsrcrecords.cc b/apt-pkg/deb/debsrcrecords.cc index 5454d79c3..d296161d6 100644 --- a/apt-pkg/deb/debsrcrecords.cc +++ b/apt-pkg/deb/debsrcrecords.cc @@ -73,9 +73,12 @@ const char **debSrcRecordParser::Binaries() char* bin = Buffer; do { char* binStartNext = strchrnul(bin, ','); - char* binEnd = binStartNext - 1; - for (; isspace_ascii(*binEnd) != 0; --binEnd) - binEnd = 0; + // Found a comma, clean up any space before it + if (binStartNext > Buffer) { + char* binEnd = binStartNext - 1; + for (; binEnd > Buffer && isspace_ascii(*binEnd) != 0; --binEnd) + *binEnd = 0; + } StaticBinList.push_back(bin); if (*binStartNext != ',') break; -- cgit v1.2.3 From 923c592ceb6014b31ec751b97b3ed659fa3e88ae Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 31 Aug 2016 17:01:04 +0200 Subject: TagFile: Fix off-by-one errors in comment stripping Adding 1 to the value of d->End - current makes restLength one byte too long: If we pass memchr(current, ..., restLength) has thus undefined behavior. Also, reading the value of current has undefined behavior if current >= d->End, not only for current > d->End: Consider a string of length 1, that is d->End = d->Current + 1. We can only read at d->Current + 0, but d->Current + 1 is beyond the end of the string. This probably caused several inexplicable build failures on hurd-i386 in the past, and just now caused a build failure on Ubuntu's amd64 builder. Reported-By: valgrind --- apt-pkg/tagfile.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/tagfile.cc b/apt-pkg/tagfile.cc index 3a3a3a04a..69148e08b 100644 --- a/apt-pkg/tagfile.cc +++ b/apt-pkg/tagfile.cc @@ -300,7 +300,7 @@ static void RemoveCommentsFromBuffer(pkgTagFilePrivate * const d) std::vector> good_parts; while (current <= d->End) { - size_t const restLength = (d->End - current) + 1; + size_t const restLength = (d->End - current); if (d->isCommentedLine == false) { current = static_cast(memchr(current, '#', restLength)); @@ -335,7 +335,7 @@ static void RemoveCommentsFromBuffer(pkgTagFilePrivate * const d) } ++current; // is the next line a comment, too? - if (current > d->End || *current != '#') + if (current >= d->End || *current != '#') { d->chunks.emplace_back(false, (current - bad_start)); good_start = current; -- cgit v1.2.3 From cf7503d8a09ebce695423fdeb2402c456c18f3d8 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 31 Aug 2016 17:18:07 +0200 Subject: Base256ToNum: Fix uninitialized value If the inner Base256ToNum() returned false, it did not set Num to a new value, causing it to be uninitialized, and thus might have caused the function to exit despite a good result. Also document why the Res = Num, if (Res != Num) magic is done. Reported-By: valgrind --- apt-pkg/contrib/strutl.cc | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'apt-pkg') diff --git a/apt-pkg/contrib/strutl.cc b/apt-pkg/contrib/strutl.cc index 66b0078dc..cf8feb970 100644 --- a/apt-pkg/contrib/strutl.cc +++ b/apt-pkg/contrib/strutl.cc @@ -1171,10 +1171,11 @@ bool Base256ToNum(const char *Str,unsigned long long &Res,unsigned int Len) tar files */ bool Base256ToNum(const char *Str,unsigned long &Res,unsigned int Len) { - unsigned long long Num; + unsigned long long Num = 0; bool rc; rc = Base256ToNum(Str, Num, Len); + // rudimentary check for overflow (Res = ulong, Num = ulonglong) Res = Num; if (Res != Num) return false; -- cgit v1.2.3 From 644478e8db56f305601c3628a74e53de048b28c8 Mon Sep 17 00:00:00 2001 From: David Kalnischkies Date: Wed, 31 Aug 2016 10:11:07 +0200 Subject: try not to call memcpy with length 0 in hash calculations memcpy is marked as nonnull for its input, but ignores the input anyhow if the declared length is zero. Our SHA2 implementations do this as well, it was "just" MD5 and SHA1 missing, so we add the length check here as well as along the callstack as it is really pointless to do all these method calls for "nothing". Reported-By: gcc -fsanitize=undefined --- apt-pkg/contrib/hashes.cc | 2 ++ apt-pkg/contrib/hashes.h | 8 ++++---- apt-pkg/contrib/hashsum_template.h | 12 ++++++------ apt-pkg/contrib/md5.cc | 2 ++ apt-pkg/contrib/md5.h | 2 +- apt-pkg/contrib/sha1.cc | 2 ++ apt-pkg/contrib/sha1.h | 2 +- apt-pkg/contrib/sha2.h | 6 +++--- 8 files changed, 21 insertions(+), 15 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/contrib/hashes.cc b/apt-pkg/contrib/hashes.cc index 755ad2035..662c2bf8b 100644 --- a/apt-pkg/contrib/hashes.cc +++ b/apt-pkg/contrib/hashes.cc @@ -312,6 +312,8 @@ public: // Hashes::Add* - Add the contents of data or FD /*{{{*/ bool Hashes::Add(const unsigned char * const Data, unsigned long long const Size) { + if (Size == 0) + return true; bool Res = true; APT_IGNORE_DEPRECATED_PUSH if ((d->CalcHashes & MD5SUM) == MD5SUM) diff --git a/apt-pkg/contrib/hashes.h b/apt-pkg/contrib/hashes.h index 9bfc32c54..1fe0afc00 100644 --- a/apt-pkg/contrib/hashes.h +++ b/apt-pkg/contrib/hashes.h @@ -195,11 +195,11 @@ class Hashes static const int UntilEOF = 0; - bool Add(const unsigned char * const Data, unsigned long long const Size); - APT_DEPRECATED_MSG("Construct accordingly instead of choosing hashes while adding") bool Add(const unsigned char * const Data, unsigned long long const Size, unsigned int const Hashes); - inline bool Add(const char * const Data) + bool Add(const unsigned char * const Data, unsigned long long const Size) APT_NONNULL(2); + APT_DEPRECATED_MSG("Construct accordingly instead of choosing hashes while adding") bool Add(const unsigned char * const Data, unsigned long long const Size, unsigned int const Hashes) APT_NONNULL(2); + inline bool Add(const char * const Data) APT_NONNULL(2) {return Add((unsigned char const * const)Data,strlen(Data));}; - inline bool Add(const unsigned char * const Beg,const unsigned char * const End) + inline bool Add(const unsigned char * const Beg,const unsigned char * const End) APT_NONNULL(2,3) {return Add(Beg,End-Beg);}; enum SupportedHashes { MD5SUM = (1 << 0), SHA1SUM = (1 << 1), SHA256SUM = (1 << 2), diff --git a/apt-pkg/contrib/hashsum_template.h b/apt-pkg/contrib/hashsum_template.h index 4000f230d..e5032d02f 100644 --- a/apt-pkg/contrib/hashsum_template.h +++ b/apt-pkg/contrib/hashsum_template.h @@ -122,18 +122,18 @@ class HashSumValue class SummationImplementation { public: - virtual bool Add(const unsigned char *inbuf, unsigned long long inlen) = 0; - inline bool Add(const char *inbuf, unsigned long long const inlen) + virtual bool Add(const unsigned char *inbuf, unsigned long long inlen) APT_NONNULL(2) = 0; + inline bool Add(const char *inbuf, unsigned long long const inlen) APT_NONNULL(2) { return Add((const unsigned char *)inbuf, inlen); } - inline bool Add(const unsigned char *Data) + inline bool Add(const unsigned char *Data) APT_NONNULL(2) { return Add(Data, strlen((const char *)Data)); } - inline bool Add(const char *Data) + inline bool Add(const char *Data) APT_NONNULL(2) { return Add((const unsigned char *)Data, strlen(Data)); } - inline bool Add(const unsigned char *Beg, const unsigned char *End) + inline bool Add(const unsigned char *Beg, const unsigned char *End) APT_NONNULL(2,3) { return Add(Beg, End - Beg); } - inline bool Add(const char *Beg, const char *End) + inline bool Add(const char *Beg, const char *End) APT_NONNULL(2,3) { return Add((const unsigned char *)Beg, End - Beg); } bool AddFD(int Fd, unsigned long long Size = 0); diff --git a/apt-pkg/contrib/md5.cc b/apt-pkg/contrib/md5.cc index b487a96f9..ff7868fe2 100644 --- a/apt-pkg/contrib/md5.cc +++ b/apt-pkg/contrib/md5.cc @@ -187,6 +187,8 @@ bool MD5Summation::Add(const unsigned char *data,unsigned long long len) { if (Done == true) return false; + if (len == 0) + return true; uint32_t *buf = (uint32_t *)Buf; uint32_t *bytes = (uint32_t *)Bytes; diff --git a/apt-pkg/contrib/md5.h b/apt-pkg/contrib/md5.h index a16ea4d2d..a286f092a 100644 --- a/apt-pkg/contrib/md5.h +++ b/apt-pkg/contrib/md5.h @@ -48,7 +48,7 @@ class MD5Summation : public SummationImplementation public: - bool Add(const unsigned char *inbuf, unsigned long long inlen) APT_OVERRIDE; + bool Add(const unsigned char *inbuf, unsigned long long inlen) APT_OVERRIDE APT_NONNULL(2); using SummationImplementation::Add; MD5SumValue Result(); diff --git a/apt-pkg/contrib/sha1.cc b/apt-pkg/contrib/sha1.cc index bf6bc6cb6..298a7799b 100644 --- a/apt-pkg/contrib/sha1.cc +++ b/apt-pkg/contrib/sha1.cc @@ -243,6 +243,8 @@ bool SHA1Summation::Add(const unsigned char *data,unsigned long long len) { if (Done) return false; + if (len == 0) + return true; uint32_t *state = (uint32_t *)State; uint32_t *count = (uint32_t *)Count; diff --git a/apt-pkg/contrib/sha1.h b/apt-pkg/contrib/sha1.h index 1c5cb5aa1..3387c1cfd 100644 --- a/apt-pkg/contrib/sha1.h +++ b/apt-pkg/contrib/sha1.h @@ -37,7 +37,7 @@ class SHA1Summation : public SummationImplementation bool Done; public: - bool Add(const unsigned char *inbuf, unsigned long long inlen) APT_OVERRIDE; + bool Add(const unsigned char *inbuf, unsigned long long inlen) APT_OVERRIDE APT_NONNULL(2); using SummationImplementation::Add; SHA1SumValue Result(); diff --git a/apt-pkg/contrib/sha2.h b/apt-pkg/contrib/sha2.h index 8b4bdd439..164840d3b 100644 --- a/apt-pkg/contrib/sha2.h +++ b/apt-pkg/contrib/sha2.h @@ -34,7 +34,7 @@ class SHA2SummationBase : public SummationImplementation protected: bool Done; public: - bool Add(const unsigned char *inbuf, unsigned long long len) APT_OVERRIDE = 0; + bool Add(const unsigned char *inbuf, unsigned long long len) APT_OVERRIDE APT_NONNULL(2) = 0; void Result(); }; @@ -45,7 +45,7 @@ class SHA256Summation : public SHA2SummationBase unsigned char Sum[32]; public: - bool Add(const unsigned char *inbuf, unsigned long long len) APT_OVERRIDE + bool Add(const unsigned char *inbuf, unsigned long long len) APT_OVERRIDE APT_NONNULL(2) { if (Done) return false; @@ -78,7 +78,7 @@ class SHA512Summation : public SHA2SummationBase unsigned char Sum[64]; public: - bool Add(const unsigned char *inbuf, unsigned long long len) APT_OVERRIDE + bool Add(const unsigned char *inbuf, unsigned long long len) APT_OVERRIDE APT_NONNULL(2) { if (Done) return false; -- cgit v1.2.3 From 544e1528b18025fad8318e6fb825ad296976cf24 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Fri, 2 Sep 2016 14:44:08 +0200 Subject: CMake: apt-pkg: Use correct ICONV_INCLUDE_DIRS variable This accidentally used ICONV_DIRECTORIES, which does not even exist. Weird. --- apt-pkg/CMakeLists.txt | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'apt-pkg') diff --git a/apt-pkg/CMakeLists.txt b/apt-pkg/CMakeLists.txt index 34930c8e9..bdaa93d67 100644 --- a/apt-pkg/CMakeLists.txt +++ b/apt-pkg/CMakeLists.txt @@ -29,7 +29,7 @@ target_include_directories(apt-pkg ${BZIP2_INCLUDE_DIR} ${LZMA_INCLUDE_DIRS} ${LZ4_INCLUDE_DIRS} - ${ICONV_DIRECTORIES} + ${ICONV_INCLUDE_DIRS} ) target_link_libraries(apt-pkg -- cgit v1.2.3 From 2a440328ea19e9646a93f847dd9eff21e03ad16d Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 15 Jun 2016 23:13:43 +0200 Subject: acquire: Use priority queues and a 3 stage pipeline design Employ a priority queue instead of a normal queue to hold the items; and only add items to the running pipeline if their priority is the same or higher than the priority of items in the queue. The priorities are designed for a 3 stage pipeline system: In stage 1, all Release files and .diff/Index files are fetched. This allows us to determine what files remain to be fetched, and thus ensures a usable progress reporting. In stage 2, all Pdiff patches are fetched, so we can apply them in parallel with fetching other files in stage 3. In stage 3, all other files are fetched (complete index files such as Contents, Packages). Performance improvements, mainly from fetching the pdiff patches before complete files, so they can be applied in parallel: For the 01 Sep 2016 03:35:23 UTC -> 02 Sep 2016 09:25:37 update of Debian unstable and testing with Contents and appstream for amd64 and i386, update time reduced from 37 seconds to 24-28 seconds. Previously, apt would first download new DEP11 icon tarballs and metadata files, causing the CPU to be idle. By fetching the diffs in stage 2, we can now patch our contents and Packages files while we are downloading the DEP11 stuff. --- apt-pkg/acquire-item.cc | 22 ++++++++++++++++++++++ apt-pkg/acquire-item.h | 2 ++ apt-pkg/acquire.cc | 36 ++++++++++++++++++++++++++++++++---- apt-pkg/acquire.h | 2 ++ 4 files changed, 58 insertions(+), 4 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/acquire-item.cc b/apt-pkg/acquire-item.cc index 0e1614330..bf1c68d82 100644 --- a/apt-pkg/acquire-item.cc +++ b/apt-pkg/acquire-item.cc @@ -1019,6 +1019,28 @@ bool pkgAcquire::Item::IsRedirectionLoop(std::string const &NewURI) /*{{{*/ } /*}}}*/ + /*}}}*/ +int pkgAcquire::Item::Priority() /*{{{*/ +{ + // Stage 1: Meta indices and diff indices + // - those need to be fetched first to have progress reporting working + // for the rest + if (dynamic_cast(this) != nullptr + || dynamic_cast(this) != nullptr + || dynamic_cast(this) != nullptr) + return 1000; + // Stage 2: Diff files + // - fetch before complete indexes so we can apply the diffs while fetching + // larger files. + if (dynamic_cast(this) != nullptr || + dynamic_cast(this) != nullptr) + return 800; + + // Stage 3: The rest - complete index files and other stuff + return 500; +} + /*}}}*/ + pkgAcqTransactionItem::pkgAcqTransactionItem(pkgAcquire * const Owner, /*{{{*/ pkgAcqMetaClearSig * const transactionManager, IndexTarget const &target) : pkgAcquire::Item(Owner), d(NULL), Target(target), TransactionManager(transactionManager) diff --git a/apt-pkg/acquire-item.h b/apt-pkg/acquire-item.h index 71a11bcde..26e1a1922 100644 --- a/apt-pkg/acquire-item.h +++ b/apt-pkg/acquire-item.h @@ -305,6 +305,8 @@ class pkgAcquire::Item : public WeakPointable /*{{{*/ virtual ~Item(); bool APT_HIDDEN IsRedirectionLoop(std::string const &NewURI); + /** \brief The priority of the item, used for queuing */ + int APT_HIDDEN Priority(); protected: /** \brief The acquire object with which this item is associated. */ diff --git a/apt-pkg/acquire.cc b/apt-pkg/acquire.cc index b4d1b5959..2ad6bc47f 100644 --- a/apt-pkg/acquire.cc +++ b/apt-pkg/acquire.cc @@ -894,9 +894,10 @@ pkgAcquire::Queue::~Queue() /* */ bool pkgAcquire::Queue::Enqueue(ItemDesc &Item) { + QItem **OptimalI = &Items; QItem **I = &Items; // move to the end of the queue and check for duplicates here - for (; *I != 0; I = &(*I)->Next) + for (; *I != 0; ) { if (Item.URI == (*I)->URI) { if (_config->FindB("Debug::pkgAcquire::Worker",false) == true) @@ -905,12 +906,22 @@ bool pkgAcquire::Queue::Enqueue(ItemDesc &Item) Item.Owner->Status = (*I)->Owner->Status; return false; } + // Determine the optimal position to insert: before anything with a + // higher priority. + int priority = (*I)->GetPriority(); + + I = &(*I)->Next; + if (priority >= Item.Owner->Priority()) { + OptimalI = I; + } + } + // Create a new item QItem *Itm = new QItem; *Itm = Item; - Itm->Next = 0; - *I = Itm; + Itm->Next = *OptimalI; + *OptimalI = Itm; Item.Owner->QueueCounter++; if (Items->Next == 0) @@ -1060,16 +1071,24 @@ bool pkgAcquire::Queue::Cycle() // Look for a queable item QItem *I = Items; + int ActivePriority = 0; while (PipeDepth < (signed)MaxPipeDepth) { - for (; I != 0; I = I->Next) + for (; I != 0; I = I->Next) { + if (I->Owner->Status == pkgAcquire::Item::StatFetching) + ActivePriority = std::max(ActivePriority, I->GetPriority()); if (I->Owner->Status == pkgAcquire::Item::StatIdle) break; + } // Nothing to do, queue is idle. if (I == 0) return true; + // This item has a lower priority than stuff in the pipeline, pretend + // the queue is idle + if (I->GetPriority() < ActivePriority) + return true; I->Worker = Workers; for (auto const &O: I->Owners) O->Status = pkgAcquire::Item::StatFetching; @@ -1135,6 +1154,15 @@ APT_PURE unsigned long long pkgAcquire::Queue::QItem::GetMaximumSize() const /*{ return Maximum; } /*}}}*/ +APT_PURE int pkgAcquire::Queue::QItem::GetPriority() const /*{{{*/ +{ + int Priority = 0; + for (auto const &O: Owners) + Priority = std::max(Priority, O->Priority()); + + return Priority; +} + /*}}}*/ void pkgAcquire::Queue::QItem::SyncDestinationFiles() const /*{{{*/ { /* ensure that the first owner has the best partial file of all and diff --git a/apt-pkg/acquire.h b/apt-pkg/acquire.h index 7044797b3..1fae662f8 100644 --- a/apt-pkg/acquire.h +++ b/apt-pkg/acquire.h @@ -464,6 +464,8 @@ class pkgAcquire::Queue /** @return the custom headers to use for this item */ std::string Custom600Headers() const; + /** @return the maximum priority of this item */ + int APT_HIDDEN GetPriority() const; }; /** \brief The name of this queue. */ -- cgit v1.2.3