/*
 * Copyright (C) 2016 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "tracing.h"

#include <stdlib.h>
#include <string.h>

#include <map>
#include <optional>
#include <string>
#include <vector>

#include <android-base/file.h>
#include <android-base/logging.h>
#include <android-base/parseint.h>
#include <android-base/stringprintf.h>
#include <android-base/strings.h>

#include "environment.h"
#include "perf_event.h"
#include "utils.h"

const char TRACING_INFO_MAGIC[10] = {23,  8,   68,  't', 'r',
                                     'a', 'c', 'i', 'n', 'g'};

template <class T>
void AppendData(std::vector<char>& data, const T& s) {
  const char* p = reinterpret_cast<const char*>(&s);
  data.insert(data.end(), p, p + sizeof(T));
}

static void AppendData(std::vector<char>& data, const char* s) {
  data.insert(data.end(), s, s + strlen(s) + 1);
}

template <>
void AppendData(std::vector<char>& data, const std::string& s) {
  data.insert(data.end(), s.c_str(), s.c_str() + s.size() + 1);
}

template <>
void MoveFromBinaryFormat(std::string& data, const char*& p) {
  data.clear();
  while (*p != '\0') {
    data.push_back(*p++);
  }
  p++;
}

static void AppendFile(std::vector<char>& data, const std::string& file,
                       uint32_t file_size_bytes = 8) {
  if (file_size_bytes == 8) {
    uint64_t file_size = file.size();
    AppendData(data, file_size);
  } else if (file_size_bytes == 4) {
    uint32_t file_size = file.size();
    AppendData(data, file_size);
  }
  data.insert(data.end(), file.begin(), file.end());
}

static void DetachFile(const char*& p, std::string& file,
                       uint32_t file_size_bytes = 8) {
  uint64_t file_size = ConvertBytesToValue(p, file_size_bytes);
  p += file_size_bytes;
  file.clear();
  file.insert(file.end(), p, p + file_size);
  p += file_size;
}

static bool ReadTraceFsFile(const std::string& path, std::string* content, bool report_error = true) {
  const char* tracefs_dir = GetTraceFsDir();
  if (tracefs_dir == nullptr) {
    if (report_error) {
      LOG(ERROR) << "tracefs doesn't exist";
    }
    return false;
  }
  std::string full_path = tracefs_dir + path;
  if (!android::base::ReadFileToString(full_path, content)) {
    if (report_error) {
      PLOG(ERROR) << "failed to read " << full_path;
    }
    return false;
  }
  return true;
}

struct TraceType {
  std::string system;
  std::string name;
};

class TracingFile {
 public:
  TracingFile();
  bool RecordHeaderFiles();
  void RecordFtraceFiles(const std::vector<TraceType>& trace_types);
  bool RecordEventFiles(const std::vector<TraceType>& trace_types);
  bool RecordKallsymsFile();
  bool RecordPrintkFormatsFile();
  std::vector<char> BinaryFormat() const;
  void LoadFromBinary(const std::vector<char>& data);
  void Dump(size_t indent) const;
  std::vector<TracingFormat> LoadTracingFormatsFromEventFiles() const;
  const std::string& GetKallsymsFile() const { return kallsyms_file; }
  uint32_t GetPageSize() const { return page_size; }

 private:
  char magic[10];
  std::string version;
  char endian;
  uint8_t size_of_long;
  uint32_t page_size;
  std::string header_page_file;
  std::string header_event_file;

  std::vector<std::string> ftrace_format_files;
  // pair of system, format_file_data.
  std::vector<std::pair<std::string, std::string>> event_format_files;

  std::string kallsyms_file;
  std::string printk_formats_file;
};

TracingFile::TracingFile() {
  memcpy(magic, TRACING_INFO_MAGIC, sizeof(TRACING_INFO_MAGIC));
  version = "0.5";
  endian = 0;
  size_of_long = static_cast<int>(sizeof(long)); // NOLINT(google-runtime-int)
  page_size = static_cast<uint32_t>(::GetPageSize());
}

bool TracingFile::RecordHeaderFiles() {
  return ReadTraceFsFile("/events/header_page", &header_page_file) &&
         ReadTraceFsFile("/events/header_event", &header_event_file);
}

void TracingFile::RecordFtraceFiles(const std::vector<TraceType>& trace_types) {
  for (const auto& type : trace_types) {
    std::string format_data;
    if (ReadTraceFsFile("/events/ftrace/" + type.name + "/format", &format_data, false)) {
      ftrace_format_files.emplace_back(std::move(format_data));
    }
  }
}

bool TracingFile::RecordEventFiles(const std::vector<TraceType>& trace_types) {
  for (const auto& type : trace_types) {
    std::string format_data;
    if (!ReadTraceFsFile("/events/" + type.system + "/" + type.name + "/format", &format_data)) {
      return false;
    }
    event_format_files.emplace_back(type.system, std::move(format_data));
  }
  return true;
}

bool TracingFile::RecordPrintkFormatsFile() {
  return ReadTraceFsFile("/printk_formats", &printk_formats_file);
}

std::vector<char> TracingFile::BinaryFormat() const {
  std::vector<char> ret;
  ret.insert(ret.end(), magic, magic + sizeof(magic));
  AppendData(ret, version);
  ret.push_back(endian);
  AppendData(ret, size_of_long);
  AppendData(ret, page_size);
  AppendData(ret, "header_page");
  AppendFile(ret, header_page_file);
  AppendData(ret, "header_event");
  AppendFile(ret, header_event_file);
  int count = static_cast<int>(ftrace_format_files.size());
  AppendData(ret, count);
  for (const auto& format : ftrace_format_files) {
    AppendFile(ret, format);
  }
  count = static_cast<int>(event_format_files.size());
  AppendData(ret, count);
  for (const auto& pair : event_format_files) {
    AppendData(ret, pair.first);
    AppendData(ret, 1);
    AppendFile(ret, pair.second);
  }
  AppendFile(ret, kallsyms_file, 4);
  AppendFile(ret, printk_formats_file, 4);
  return ret;
}

void TracingFile::LoadFromBinary(const std::vector<char>& data) {
  const char* p = data.data();
  const char* end = data.data() + data.size();
  CHECK(memcmp(p, magic, sizeof(magic)) == 0);
  p += sizeof(magic);
  MoveFromBinaryFormat(version, p);
  MoveFromBinaryFormat(endian, p);
  MoveFromBinaryFormat(size_of_long, p);
  MoveFromBinaryFormat(page_size, p);
  std::string filename;
  MoveFromBinaryFormat(filename, p);
  CHECK_EQ(filename, "header_page");
  DetachFile(p, header_page_file);
  MoveFromBinaryFormat(filename, p);
  CHECK_EQ(filename, "header_event");
  DetachFile(p, header_event_file);
  uint32_t count;
  MoveFromBinaryFormat(count, p);
  ftrace_format_files.resize(count);
  for (uint32_t i = 0; i < count; ++i) {
    DetachFile(p, ftrace_format_files[i]);
  }
  MoveFromBinaryFormat(count, p);
  event_format_files.clear();
  for (uint32_t i = 0; i < count; ++i) {
    std::string system;
    MoveFromBinaryFormat(system, p);
    uint32_t count_in_system;
    MoveFromBinaryFormat(count_in_system, p);
    for (uint32_t i = 0; i < count_in_system; ++i) {
      std::string format;
      DetachFile(p, format);
      event_format_files.push_back(std::make_pair(system, std::move(format)));
    }
  }
  DetachFile(p, kallsyms_file, 4);
  DetachFile(p, printk_formats_file, 4);
  CHECK_EQ(p, end);
}

void TracingFile::Dump(size_t indent) const {
  PrintIndented(indent, "tracing data:\n");
  PrintIndented(indent + 1, "magic: ");
  for (size_t i = 0; i < 3u; ++i) {
    printf("0x%x ", magic[i]);
  }
  for (size_t i = 3; i < sizeof(magic); ++i) {
    printf("%c", magic[i]);
  }
  printf("\n");
  PrintIndented(indent + 1, "version: %s\n", version.c_str());
  PrintIndented(indent + 1, "endian: %d\n", endian);
  PrintIndented(indent + 1, "header_page:\n%s\n\n", header_page_file.c_str());
  PrintIndented(indent + 1, "header_event:\n%s\n\n", header_event_file.c_str());
  for (size_t i = 0; i < ftrace_format_files.size(); ++i) {
    PrintIndented(indent + 1, "ftrace format file %zu/%zu:\n%s\n\n", i + 1,
                  ftrace_format_files.size(), ftrace_format_files[i].c_str());
  }
  for (size_t i = 0; i < event_format_files.size(); ++i) {
    PrintIndented(indent + 1, "event format file %zu/%zu %s:\n%s\n\n", i + 1,
                  event_format_files.size(),
                  event_format_files[i].first.c_str(),
                  event_format_files[i].second.c_str());
  }
  PrintIndented(indent + 1, "kallsyms:\n%s\n\n", kallsyms_file.c_str());
  PrintIndented(indent + 1, "printk_formats:\n%s\n\n",
                printk_formats_file.c_str());
}

enum class FormatParsingState {
  READ_NAME,
  READ_ID,
  READ_FIELDS,
  READ_PRINTFMT,
};

// Parse lines like: field:char comm[16]; offset:8; size:16;  signed:1;
static TracingField ParseTracingField(const std::string& s) {
  TracingField field;
  size_t start = 0;
  std::string name;
  std::string value;
  for (size_t i = 0; i < s.size(); ++i) {
    if (!isspace(s[i]) && (i == 0 || isspace(s[i - 1]))) {
      start = i;
    } else if (s[i] == ':') {
      name = s.substr(start, i - start);
      start = i + 1;
    } else if (s[i] == ';') {
      value = s.substr(start, i - start);
      if (name == "field") {
        // Parse value with brackets like "comm[16]", or just a field name.
        size_t left_bracket_pos = value.find('[');
        if (left_bracket_pos == std::string::npos) {
          field.name = value;
          field.elem_count = 1;
        } else {
          field.name = value.substr(0, left_bracket_pos);
          field.elem_count = 1;
          size_t right_bracket_pos = value.find(']', left_bracket_pos);
          if (right_bracket_pos != std::string::npos) {
            size_t len = right_bracket_pos - left_bracket_pos - 1;
            size_t elem_count;
            // Array size may not be a number, like field:u32 rates[IEEE80211_NUM_BANDS].
            if (android::base::ParseUint(value.substr(left_bracket_pos + 1, len), &elem_count)) {
              field.elem_count = elem_count;
            }
          }
        }
      } else if (name == "offset") {
        field.offset =
            static_cast<size_t>(strtoull(value.c_str(), nullptr, 10));
      } else if (name == "size") {
        size_t size = static_cast<size_t>(strtoull(value.c_str(), nullptr, 10));
        CHECK_EQ(size % field.elem_count, 0u);
        field.elem_size = size / field.elem_count;
      } else if (name == "signed") {
        int is_signed = static_cast<int>(strtoull(value.c_str(), nullptr, 10));
        field.is_signed = (is_signed == 1);
      }
    }
  }
  return field;
}

static TracingFormat ParseTracingFormat(const std::string& data) {
  TracingFormat format;
  std::vector<std::string> strs = android::base::Split(data, "\n");
  FormatParsingState state = FormatParsingState::READ_NAME;
  for (const auto& s : strs) {
    if (state == FormatParsingState::READ_NAME) {
      if (size_t pos = s.find("name:"); pos != std::string::npos) {
        format.name = android::base::Trim(s.substr(pos + strlen("name:")));
        state = FormatParsingState::READ_ID;
      }
    } else if (state == FormatParsingState::READ_ID) {
      if (size_t pos = s.find("ID:"); pos != std::string::npos) {
        format.id = strtoull(s.substr(pos + strlen("ID:")).c_str(), nullptr, 10);
        state = FormatParsingState::READ_FIELDS;
      }
    } else if (state == FormatParsingState::READ_FIELDS) {
      if (size_t pos = s.find("field:"); pos != std::string::npos) {
        TracingField field = ParseTracingField(s);
        format.fields.push_back(field);
      }
    }
  }
  return format;
}

std::vector<TracingFormat> TracingFile::LoadTracingFormatsFromEventFiles()
    const {
  std::vector<TracingFormat> formats;
  for (const auto& pair : event_format_files) {
    TracingFormat format = ParseTracingFormat(pair.second);
    format.system_name = pair.first;
    formats.push_back(format);
  }
  return formats;
}

Tracing::Tracing(const std::vector<char>& data) {
  tracing_file_ = new TracingFile;
  tracing_file_->LoadFromBinary(data);
}

Tracing::~Tracing() { delete tracing_file_; }

void Tracing::Dump(size_t indent) { tracing_file_->Dump(indent); }

TracingFormat Tracing::GetTracingFormatHavingId(uint64_t trace_event_id) {
  if (tracing_formats_.empty()) {
    tracing_formats_ = tracing_file_->LoadTracingFormatsFromEventFiles();
  }
  for (const auto& format : tracing_formats_) {
    if (format.id == trace_event_id) {
      return format;
    }
  }
  LOG(FATAL) << "no tracing format for id " << trace_event_id;
  return TracingFormat();
}

std::string Tracing::GetTracingEventNameHavingId(uint64_t trace_event_id) {
  if (tracing_formats_.empty()) {
    tracing_formats_ = tracing_file_->LoadTracingFormatsFromEventFiles();
  }
  for (const auto& format : tracing_formats_) {
    if (format.id == trace_event_id) {
      return android::base::StringPrintf("%s:%s", format.system_name.c_str(),
                                         format.name.c_str());
    }
  }
  return "";
}

const std::string& Tracing::GetKallsyms() const {
  return tracing_file_->GetKallsymsFile();
}

uint32_t Tracing::GetPageSize() const { return tracing_file_->GetPageSize(); }

bool GetTracingData(const std::vector<const EventType*>& event_types,
                    std::vector<char>* data) {
  data->clear();
  std::vector<TraceType> trace_types;
  for (const auto& type : event_types) {
    CHECK_EQ(static_cast<uint32_t>(PERF_TYPE_TRACEPOINT), type->type);
    size_t pos = type->name.find(':');
    TraceType trace_type;
    trace_type.system = type->name.substr(0, pos);
    trace_type.name = type->name.substr(pos + 1);
    trace_types.push_back(trace_type);
  }
  TracingFile tracing_file;
  if (!tracing_file.RecordHeaderFiles()) {
    return false;
  }
  tracing_file.RecordFtraceFiles(trace_types);
  if (!tracing_file.RecordEventFiles(trace_types)) {
    return false;
  }
  // Don't record /proc/kallsyms here, as it will be contained in
  // KernelSymbolRecord.
  if (!tracing_file.RecordPrintkFormatsFile()) {
    return false;
  }
  *data = tracing_file.BinaryFormat();
  return true;
}

namespace {

// Briefly check if the filter format is acceptable by the kernel, which is described in
// Documentation/trace/events.rst in the kernel. Also adjust quotes in string operands.
//
// filter := predicate_expr [logical_operator predicate_expr]*
// predicate_expr := predicate | '!' predicate_expr | '(' filter ')'
// predicate := field_name relational_operator value
//
// logical_operator := '&&' | '||'
// relational_operator := numeric_operator | string_operator
// numeric_operator := '==' | '!=' | '<' | '<=' | '>' | '>=' | '&'
// string_operator := '==' | '!=' | '~'
// value := int or string
struct FilterFormatAdjuster {
  FilterFormatAdjuster(bool use_quote) : use_quote(use_quote) {}

  bool MatchFilter(const char*& p) {
    bool ok = MatchPredicateExpr(p);
    while (ok && *p != '\0') {
      RemoveSpace(p);
      if (strncmp(p, "||", 2) == 0 || strncmp(p, "&&", 2) == 0) {
        CopyBytes(p, 2);
        ok = MatchPredicateExpr(p);
      } else {
        break;
      }
    }
    RemoveSpace(p);
    return ok;
  }

  void RemoveSpace(const char*& p) {
    size_t i = 0;
    while (isspace(p[i])) {
      i++;
    }
    if (i > 0) {
      CopyBytes(p, i);
    }
  }

  bool MatchPredicateExpr(const char*& p) {
    RemoveSpace(p);
    if (*p == '!') {
      CopyBytes(p, 1);
      return MatchPredicateExpr(p);
    }
    if (*p == '(') {
      CopyBytes(p, 1);
      bool ok = MatchFilter(p);
      if (!ok) {
        return false;
      }
      RemoveSpace(p);
      if (*p != ')') {
        return false;
      }
      CopyBytes(p, 1);
      return true;
    }
    return MatchPredicate(p);
  }

  bool MatchPredicate(const char*& p) {
    return MatchFieldName(p) && MatchRelationalOperator(p) && MatchValue(p);
  }

  bool MatchFieldName(const char*& p) {
    RemoveSpace(p);
    std::string name;
    for (size_t i = 0; isalnum(p[i]) || p[i] == '_'; i++) {
      name.push_back(p[i]);
    }
    CopyBytes(p, name.size());
    if (name.empty()) {
      return false;
    }
    used_fields.emplace(std::move(name));
    return true;
  }

  bool MatchRelationalOperator(const char*& p) {
    RemoveSpace(p);
    // "==", "!=", "<", "<=", ">", ">=", "&", "~"
    if (*p == '=' || *p == '!' || *p == '<' || *p == '>') {
      if (p[1] == '=') {
        CopyBytes(p, 2);
        return true;
      }
    }
    if (*p == '<' || *p == '>' || *p == '&' || *p == '~') {
      CopyBytes(p, 1);
      return true;
    }
    return false;
  }

  bool MatchValue(const char*& p) {
    RemoveSpace(p);
    // Match a string with quotes.
    if (*p == '\'' || *p == '"') {
      char quote = *p;
      size_t len = 1;
      while (p[len] != quote && p[len] != '\0') {
        len++;
      }
      if (p[len] != quote) {
        return false;
      }
      len++;
      if (use_quote) {
        CopyBytes(p, len);
      } else {
        p++;
        CopyBytes(p, len - 2);
        p++;
      }
      return true;
    }
    // Match an int value.
    char* end;
    errno = 0;
    if (*p == '-') {
      strtoll(p, &end, 0);
    } else {
      strtoull(p, &end, 0);
    }
    if (errno == 0 && end != p) {
      CopyBytes(p, end - p);
      return true;
    }
    // Match a string without quotes, stopping at ), &&, || or space.
    size_t len = 0;
    while (p[len] != '\0' && strchr(")&| \t", p[len]) == nullptr) {
      len++;
    }
    if (len == 0) {
      return false;
    }
    if (use_quote) {
      adjusted_filter += '"';
    }
    CopyBytes(p, len);
    if (use_quote) {
      adjusted_filter += '"';
    }
    return true;
  }

  void CopyBytes(const char*& p, size_t len) {
    adjusted_filter.append(p, len);
    p += len;
  }

  const bool use_quote;
  std::string adjusted_filter;
  FieldNameSet used_fields;
};

}  // namespace

std::optional<std::string> AdjustTracepointFilter(const std::string& filter, bool use_quote,
                                                  FieldNameSet* used_fields) {
  FilterFormatAdjuster adjuster(use_quote);
  const char* p = filter.c_str();
  if (!adjuster.MatchFilter(p) || *p != '\0') {
    LOG(ERROR) << "format error in filter \"" << filter << "\" starting from \"" << p << "\"";
    return std::nullopt;
  }
  *used_fields = std::move(adjuster.used_fields);
  return std::move(adjuster.adjusted_filter);
}

std::optional<FieldNameSet> GetFieldNamesForTracepointEvent(const EventType& event) {
  std::vector<std::string> strs = android::base::Split(event.name, ":");
  if (strs.size() != 2) {
    return {};
  }
  std::string data;
  if (!ReadTraceFsFile("/events/" + strs[0] + "/" + strs[1] + "/format", &data, false)) {
    return {};
  }
  TracingFormat format = ParseTracingFormat(data);
  FieldNameSet names;
  for (auto& field : format.fields) {
    names.emplace(std::move(field.name));
  }
  return names;
}