Add a new wart, I mean feature, on to gdb-remote protocol: compression.

For some communication channels, sending large packets can be very 
slow.  In those cases, it may be faster to compress the contents of
the packet on the target device and decompress it on the debug host
system.  For instance, communicating with a device using something
like Bluetooth may be an environment where this tradeoff is a good one.

This patch adds a new field to the response to the "qSupported" packet
(which returns a "qXfer:features:" response) -- SupportedCompressions
and DefaultCompressionMinSize.  These tell you what the remote
stub can support.

lldb, if it wants to enable compression and can handle one of those 
algorithms, it can send a QEnableCompression packet specifying the
algorithm and optionally the minimum packet size to use compression
on.  lldb may have better knowledge about the best tradeoff for
a given communication channel.

I added support to debugserver an lldb to use the zlib APIs
(if -DHAVE_LIBZ=1 is in CFLAGS and -lz is in LDFLAGS) and the
libcompression APIs on Mac OS X 10.11 and later 
(if -DHAVE_LIBCOMPRESSION=1).  libz "zlib-deflate" compression.
libcompression can support deflate, lz4, lzma, and a proprietary
lzfse algorithm.  libcompression has been hand-tuned for Apple
hardware so it should be preferred if available.

debugserver currently only adds the SupportedCompressions when
it is being run on an Apple watch (TARGET_OS_WATCH).  Comment
that #if out from RNBRemote.cpp if you want to enable it to
see how it works.  I haven't tested this on a native system
configuration but surely it will be slower to compress & decompress
the packets in a same-system debug session.

I haven't had a chance to add support for this to 
GDBRemoteCommunciationServer.cpp yet.

<rdar://problem/21090180> 

llvm-svn: 240066

4 files changed, 437 insertions, 5 deletions

diff --git a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication.cpp b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication.cpp
index da04f46c25a..1af3947a75f 100644
--- a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication.cpp
+++ b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication.cpp
@@ -42,6 +42,14 @@
 # define DEBUGSERVER_BASENAME    "lldb-server"
 #endif
 
+#if defined (HAVE_LIBCOMPRESSION)
+#include <compression.h>
+#endif
+
+#if defined (HAVE_LIBZ)
+#include <zlib.h>
+#endif
+
 using namespace lldb;
 using namespace lldb_private;
 using namespace lldb_private::process_gdb_remote;
@@ -158,6 +166,7 @@ GDBRemoteCommunication::GDBRemoteCommunication(const char *comm_name,
     m_private_is_running (false),
     m_history (512),
     m_send_acks (true),
+    m_compression_type (CompressionType::None),
     m_listen_url ()
 {
 }
@@ -546,6 +555,226 @@ GDBRemoteCommunication::WaitForPacketWithTimeoutMicroSecondsNoLock (StringExtrac
         return PacketResult::ErrorReplyFailed;
 }
 
+bool
+GDBRemoteCommunication::DecompressPacket ()
+{
+    Log *log (ProcessGDBRemoteLog::GetLogIfAllCategoriesSet (GDBR_LOG_PACKETS));
+
+    if (!CompressionIsEnabled())
+        return true;
+
+    size_t pkt_size = m_bytes.size();
+    if (pkt_size < 6)
+        return true;
+    if (m_bytes[0] != '$' && m_bytes[0] != '%')
+        return true;
+    if (m_bytes[1] != 'C' && m_bytes[1] != 'N')
+        return true;
+    if (m_bytes[pkt_size - 3] != '#')
+        return true;
+    if (!::isxdigit (m_bytes[pkt_size - 2]) || !::isxdigit (m_bytes[pkt_size - 1]))
+        return true;
+
+    size_t content_length = pkt_size - 5;   // not counting '$', 'C' | 'N', '#', & the two hex checksum chars
+    size_t content_start = 2;               // The first character of the compressed/not-compressed text of the packet
+    size_t hash_mark_idx = pkt_size - 3;    // The '#' character marking the end of the packet
+    size_t checksum_idx = pkt_size - 2;     // The first character of the two hex checksum characters
+
+    // Compressed packets ("$C") start with a base10 number which is the size of the uncompressed payload,
+    // then a : and then the compressed data.  e.g. $C1024:<binary>#00
+    // Update content_start and content_length to only include the <binary> part of the packet.
+
+    uint64_t decompressed_bufsize = ULONG_MAX;
+    if (m_bytes[1] == 'C')
+    {
+        size_t i = content_start;
+        while (i < hash_mark_idx && isdigit(m_bytes[i]))
+            i++;
+        if (i < hash_mark_idx && m_bytes[i] == ':')
+        {
+            i++;
+            content_start = i;
+            content_length = hash_mark_idx - content_start;
+            std::string bufsize_str (m_bytes.data() + 2, i - 2 - 1);
+            errno = 0;
+            decompressed_bufsize = ::strtoul (bufsize_str.c_str(), NULL, 10);
+            if (errno != 0 || decompressed_bufsize == ULONG_MAX)
+            {
+                m_bytes.erase (0, pkt_size);
+                return false;
+            }
+        }
+    }
+
+    if (GetSendAcks ())
+    {
+        char packet_checksum_cstr[3];
+        packet_checksum_cstr[0] = m_bytes[checksum_idx];
+        packet_checksum_cstr[1] = m_bytes[checksum_idx + 1];
+        packet_checksum_cstr[2] = '\0';
+        long packet_checksum = strtol (packet_checksum_cstr, NULL, 16);
+
+        long actual_checksum = CalculcateChecksum (m_bytes.data() + 1, hash_mark_idx - 1);
+        bool success = packet_checksum == actual_checksum;
+        if (!success)
+        {
+            if (log)
+                log->Printf ("error: checksum mismatch: %.*s expected 0x%2.2x, got 0x%2.2x", 
+                             (int)(pkt_size), 
+                             m_bytes.c_str(),
+                             (uint8_t)packet_checksum,
+                             (uint8_t)actual_checksum);
+        }
+        // Send the ack or nack if needed
+        if (!success)
+        {
+            SendNack();
+            m_bytes.erase (0, pkt_size);
+            return false;
+        }
+        else
+        {
+            SendAck();
+        }
+    }
+
+    if (m_bytes[1] == 'N')
+    {
+        // This packet was not compressed -- delete the 'N' character at the 
+        // start and the packet may be processed as-is.
+        m_bytes.erase(1, 1);
+        return true;
+    }
+
+    // Reverse the gdb-remote binary escaping that was done to the compressed text to
+    // guard characters like '$', '#', '}', etc.
+    std::vector<uint8_t> unescaped_content;
+    unescaped_content.reserve (content_length);
+    size_t i = content_start;
+    while (i < hash_mark_idx)
+    {
+        if (m_bytes[i] == '}')
+        {
+            i++;
+            unescaped_content.push_back (m_bytes[i] ^ 0x20);
+        }
+        else
+        {
+            unescaped_content.push_back (m_bytes[i]);
+        }
+        i++;
+    }
+
+    uint8_t *decompressed_buffer = nullptr;
+    size_t decompressed_bytes = 0;
+
+    if (decompressed_bufsize != ULONG_MAX)
+    {
+        decompressed_buffer = (uint8_t *) malloc (decompressed_bufsize + 1);
+        if (decompressed_buffer == nullptr)
+        {
+            m_bytes.erase (0, pkt_size);
+            return false;
+        }
+
+    }
+
+#if defined (HAVE_LIBCOMPRESSION)
+    // libcompression is weak linked so check that compression_decode_buffer() is available
+    if (compression_decode_buffer != NULL &&
+        (m_compression_type == CompressionType::ZlibDeflate 
+         || m_compression_type == CompressionType::LZFSE
+         || m_compression_type == CompressionType::LZ4))
+    {
+        compression_algorithm compression_type;
+        if (m_compression_type == CompressionType::ZlibDeflate)
+            compression_type = COMPRESSION_ZLIB;
+        else if (m_compression_type == CompressionType::LZFSE)
+            compression_type = COMPRESSION_LZFSE;
+        else if (m_compression_type == CompressionType::LZ4)
+            compression_type = COMPRESSION_LZ4_RAW;
+        else if (m_compression_type == CompressionType::LZMA)
+            compression_type = COMPRESSION_LZMA;
+
+
+        // If we have the expected size of the decompressed payload, we can allocate
+        // the right-sized buffer and do it.  If we don't have that information, we'll
+        // need to try decoding into a big buffer and if the buffer wasn't big enough,
+        // increase it and try again.
+
+        if (decompressed_bufsize != ULONG_MAX && decompressed_buffer != nullptr)
+        {
+            decompressed_bytes = compression_decode_buffer (decompressed_buffer, decompressed_bufsize + 10 ,
+                                                        (uint8_t*) unescaped_content.data(),
+                                                        unescaped_content.size(),
+                                                        NULL,
+                                                        compression_type);
+        }
+    }
+#endif
+
+#if defined (HAVE_LIBZ)
+    if (decompressed_bytes == 0 
+        && decompressed_bufsize != ULONG_MAX
+        && decompressed_buffer != nullptr 
+        && m_compression_type == CompressionType::ZlibDeflate)
+    {
+        z_stream stream;
+        memset (&stream, 0, sizeof (z_stream));
+        stream.next_in = (Bytef *) unescaped_content.data();
+        stream.avail_in = (uInt) unescaped_content.size();
+        stream.total_in = 0;
+        stream.next_out = (Bytef *) decompressed_buffer;
+        stream.avail_out = decompressed_bufsize;
+        stream.total_out = 0;
+        stream.zalloc = Z_NULL;
+        stream.zfree = Z_NULL;
+        stream.opaque = Z_NULL;
+
+        if (inflateInit2 (&stream, -15) == Z_OK)
+        {
+            int status = inflate (&stream, Z_NO_FLUSH);
+            inflateEnd (&stream);
+            if (status == Z_STREAM_END)
+            {
+                decompressed_bytes = stream.total_out;
+            }
+        }
+    }
+#endif
+
+    if (decompressed_bytes == 0 || decompressed_buffer == nullptr)
+    {
+        if (decompressed_buffer)
+            free (decompressed_buffer);
+        m_bytes.erase (0, pkt_size);
+        return false;
+    }
+
+    std::string new_packet;
+    new_packet.reserve (decompressed_bytes + 6);
+    new_packet.push_back (m_bytes[0]);
+    new_packet.append ((const char *) decompressed_buffer, decompressed_bytes);
+    new_packet.push_back ('#');
+    if (GetSendAcks ())
+    {
+        uint8_t decompressed_checksum = CalculcateChecksum ((const char *) decompressed_buffer, decompressed_bytes);
+        char decompressed_checksum_str[3];
+        snprintf (decompressed_checksum_str, 3, "%02x", decompressed_checksum);
+        new_packet.append (decompressed_checksum_str);
+    }
+    else
+    {
+        new_packet.push_back ('0');
+        new_packet.push_back ('0');
+    }
+
+    m_bytes = new_packet;
+
+    free (decompressed_buffer);
+    return true;
+}
+
 GDBRemoteCommunication::PacketType
 GDBRemoteCommunication::CheckForPacket (const uint8_t *src, size_t src_len, StringExtractorGDBRemote &packet)
 {
@@ -581,6 +810,17 @@ GDBRemoteCommunication::CheckForPacket (const uint8_t *src, size_t src_len, Stri
         size_t total_length = 0;
         size_t checksum_idx = std::string::npos;
 
+        // Size of packet before it is decompressed, for logging purposes
+        size_t original_packet_size = m_bytes.size();
+        if (CompressionIsEnabled())
+        {
+            if (DecompressPacket() == false)
+            {
+                packet.Clear();
+                return GDBRemoteCommunication::PacketType::Standard;
+            }
+        }
+
         switch (m_bytes[0])
         {
             case '+':       // Look for ack
@@ -664,12 +904,10 @@ GDBRemoteCommunication::CheckForPacket (const uint8_t *src, size_t src_len, Stri
             assert (content_length <= m_bytes.size());
             assert (total_length <= m_bytes.size());
             assert (content_length <= total_length);
-            const size_t content_end = content_start + content_length;
+            size_t content_end = content_start + content_length;
 
             bool success = true;
             std::string &packet_str = packet.GetStringRef();
-            
-            
             if (log)
             {
                 // If logging was just enabled and we have history, then dump out what
@@ -693,7 +931,10 @@ GDBRemoteCommunication::CheckForPacket (const uint8_t *src, size_t src_len, Stri
                 {
                     StreamString strm;
                     // Packet header...
-                    strm.Printf("<%4" PRIu64 "> read packet: %c", (uint64_t)total_length, m_bytes[0]);
+                    if (CompressionIsEnabled())
+                        strm.Printf("<%4" PRIu64 ":%" PRIu64 "> read packet: %c", (uint64_t) original_packet_size, (uint64_t)total_length, m_bytes[0]);
+                    else
+                        strm.Printf("<%4" PRIu64 "> read packet: %c", (uint64_t)total_length, m_bytes[0]);
                     for (size_t i=content_start; i<content_end; ++i)
                     {
                         // Remove binary escaped bytes when displaying the packet...
@@ -716,7 +957,10 @@ GDBRemoteCommunication::CheckForPacket (const uint8_t *src, size_t src_len, Stri
                 }
                 else
                 {
-                    log->Printf("<%4" PRIu64 "> read packet: %.*s", (uint64_t)total_length, (int)(total_length), m_bytes.c_str());
+                    if (CompressionIsEnabled())
+                        log->Printf("<%4" PRIu64 ":%" PRIu64 "> read packet: %.*s", (uint64_t) original_packet_size, (uint64_t)total_length, (int)(total_length), m_bytes.c_str());
+                    else
+                        log->Printf("<%4" PRIu64 "> read packet: %.*s", (uint64_t)total_length, (int)(total_length), m_bytes.c_str());
                 }
             }
 
diff --git a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication.h b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication.h
index c13352781b3..7379bb3aa09 100644
--- a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication.h
+++ b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication.h
@@ -41,6 +41,15 @@ typedef enum
     eWatchpointReadWrite
 } GDBStoppointType;
 
+enum class CompressionType
+{
+    None = 0,       // no compression
+    ZlibDeflate,    // zlib's deflate compression scheme, requires zlib or Apple's libcompression
+    LZFSE,          // an Apple compression scheme, requires Apple's libcompression
+    LZ4,            // lz compression - called "lz4 raw" in libcompression terms, compat with https://code.google.com/p/lz4/
+    LZMA,           // Lempel–Ziv–Markov chain algorithm
+};
+
 class ProcessGDBRemote;
 
 class GDBRemoteCommunication : public Communication
@@ -296,6 +305,22 @@ protected:
     bool
     WaitForNotRunningPrivate (const TimeValue *timeout_ptr);
 
+    bool
+    CompressionIsEnabled ()
+    {
+        return m_compression_type != CompressionType::None;
+    }
+
+    // If compression is enabled, decompress the packet in m_bytes and update
+    // m_bytes with the uncompressed version.
+    // Returns 'true' packet was decompressed and m_bytes is the now-decompressed text.
+    // Returns 'false' if unable to decompress or if the checksum was invalid.
+    //
+    // NB: Once the packet has been decompressed, checksum cannot be computed based
+    // on m_bytes.  The checksum was for the compressed packet.
+    bool
+    DecompressPacket ();
+
     //------------------------------------------------------------------
     // Classes that inherit from GDBRemoteCommunication can see and modify these
     //------------------------------------------------------------------
@@ -315,6 +340,7 @@ protected:
                         // false if this class represents a debug session for
                         // a single process
     
+    CompressionType m_compression_type;
 
     Error
     StartListenThread (const char *hostname = "127.0.0.1", uint16_t port = 0);
diff --git a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp
index 21a538ced17..d2a15b3152e 100644
--- a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp
+++ b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp
@@ -43,6 +43,10 @@
 #include "ProcessGDBRemoteLog.h"
 #include "lldb/Host/Config.h"
 
+#if defined (HAVE_LIBCOMPRESSION)
+#include <compression.h>
+#endif
+
 using namespace lldb;
 using namespace lldb_private;
 using namespace lldb_private::process_gdb_remote;
@@ -423,6 +427,59 @@ GDBRemoteCommunicationClient::GetRemoteQSupported ()
         if (::strstr (response_cstr, "qXfer:features:read+"))
             m_supports_qXfer_features_read = eLazyBoolYes;
 
+
+        // Look for a list of compressions in the features list e.g.
+        // qXfer:features:read+;PacketSize=20000;qEcho+;SupportedCompressions=zlib-deflate,lzma
+        const char *features_list = ::strstr (response_cstr, "qXfer:features:");
+        if (features_list)
+        {
+            const char *compressions = ::strstr (features_list, "SupportedCompressions=");
+            if (compressions)
+            {
+                std::vector<std::string> supported_compressions;
+                compressions += sizeof ("SupportedCompressions=") - 1;
+                const char *end_of_compressions = strchr (compressions, ';');
+                if (end_of_compressions == NULL)
+                {
+                    end_of_compressions = strchr (compressions, '\0');
+                }
+                const char *current_compression = compressions;
+                while (current_compression < end_of_compressions)
+                {
+                    const char *next_compression_name = strchr (current_compression, ',');
+                    const char *end_of_this_word = next_compression_name;
+                    if (next_compression_name == NULL || end_of_compressions < next_compression_name)
+                    {
+                        end_of_this_word = end_of_compressions;
+                    }
+
+                    if (end_of_this_word)
+                    {
+                        if (end_of_this_word == current_compression)
+                        {
+                            current_compression++;
+                        }
+                        else
+                        {
+                            std::string this_compression (current_compression, end_of_this_word - current_compression);
+                            supported_compressions.push_back (this_compression);
+                            current_compression = end_of_this_word + 1;
+                        }
+                    }
+                    else
+                    {
+                        supported_compressions.push_back (current_compression);
+                        current_compression = end_of_compressions;
+                    }
+                }
+
+                if (supported_compressions.size() > 0)
+                {
+                    MaybeEnableCompression (supported_compressions);
+                }
+            }
+        }
+
         if (::strstr (response_cstr, "qEcho"))
             m_supports_qEcho = eLazyBoolYes;
         else
@@ -1629,6 +1686,105 @@ GDBRemoteCommunicationClient::GetGDBServerVersion()
     return m_qGDBServerVersion_is_valid == eLazyBoolYes;
 }
 
+void
+GDBRemoteCommunicationClient::MaybeEnableCompression (std::vector<std::string> supported_compressions)
+{
+    CompressionType avail_type = CompressionType::None;
+    std::string avail_name;
+
+#if defined (HAVE_LIBCOMPRESSION)
+    // libcompression is weak linked so test if compression_decode_buffer() is available
+    if (compression_decode_buffer != NULL && avail_type == CompressionType::None)
+    {
+        for (auto compression : supported_compressions)
+        {
+            if (compression == "lzfse")
+            {
+                avail_type = CompressionType::LZFSE;
+                avail_name = compression;
+                break;
+            }
+        }
+    }
+#endif
+
+#if defined (HAVE_LIBCOMPRESSION)
+    // libcompression is weak linked so test if compression_decode_buffer() is available
+    if (compression_decode_buffer != NULL && avail_type == CompressionType::None)
+    {
+        for (auto compression : supported_compressions)
+        {
+            if (compression == "zlib-deflate")
+            {
+                avail_type = CompressionType::ZlibDeflate;
+                avail_name = compression;
+                break;
+            }
+        }
+    }
+#endif
+
+#if defined (HAVE_LIBZ)
+    if (avail_type == CompressionType::None)
+    {
+        for (auto compression : supported_compressions)
+        {
+            if (compression == "zlib-deflate")
+            {
+                avail_type = CompressionType::ZlibDeflate;
+                avail_name = compression;
+                break;
+            }
+        }
+    }
+#endif
+
+#if defined (HAVE_LIBCOMPRESSION)
+    // libcompression is weak linked so test if compression_decode_buffer() is available
+    if (compression_decode_buffer != NULL && avail_type == CompressionType::None)
+    {
+        for (auto compression : supported_compressions)
+        {
+            if (compression == "lz4")
+            {
+                avail_type = CompressionType::LZ4;
+                avail_name = compression;
+                break;
+            }
+        }
+    }
+#endif
+
+#if defined (HAVE_LIBCOMPRESSION)
+    // libcompression is weak linked so test if compression_decode_buffer() is available
+    if (compression_decode_buffer != NULL && avail_type == CompressionType::None)
+    {
+        for (auto compression : supported_compressions)
+        {
+            if (compression == "lzma")
+            {
+                avail_type = CompressionType::LZMA;
+                avail_name = compression;
+                break;
+            }
+        }
+    }
+#endif
+
+    if (avail_type != CompressionType::None)
+    {
+        StringExtractorGDBRemote response;
+        std::string packet = "QEnableCompression:type:" + avail_name + ";";
+        if (SendPacketAndWaitForResponse (packet.c_str(), response, false) !=  PacketResult::Success)
+            return;
+    
+        if (response.IsOKResponse())
+        {
+            m_compression_type = avail_type;
+        }
+    }
+}
+
 const char *
 GDBRemoteCommunicationClient::GetGDBServerProgramName()
 {
diff --git a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.h b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.h
index 726bc577a1b..ba34a313090 100644
--- a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.h
+++ b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.h
@@ -564,6 +564,11 @@ protected:
     bool
     GetGDBServerVersion();
 
+    // Given the list of compression types that the remote debug stub can support,
+    // possibly enable compression if we find an encoding we can handle.
+    void
+    MaybeEnableCompression (std::vector<std::string> supported_compressions);
+
     //------------------------------------------------------------------
     // Classes that inherit from GDBRemoteCommunicationClient can see and modify these
     //------------------------------------------------------------------
@@ -643,6 +648,7 @@ protected:
     uint32_t m_gdb_server_version; // from reply to qGDBServerVersion, zero if qGDBServerVersion is not supported
     uint32_t m_default_packet_timeout;
     uint64_t m_max_packet_size;  // as returned by qSupported
+
     
     bool
     DecodeProcessInfoResponse (StringExtractorGDBRemote &response,