//===--- Randstruct.cpp ---------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains the implementation for Clang's structure field layout
// randomization.
//
//===----------------------------------------------------------------------===//

#include "clang/AST/Randstruct.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/Attr.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclCXX.h" // For StaticAssertDecl
#include "clang/Basic/Diagnostic.h"
#include "llvm/ADT/SmallVector.h"

#include <algorithm>
#include <random>
#include <set>
#include <string>

using clang::ASTContext;
using clang::FieldDecl;
using llvm::SmallVector;

namespace {

// FIXME: Replace this with some discovery once that mechanism exists.
enum { CACHE_LINE = 64 };

// The Bucket class holds the struct fields we're trying to fill to a
// cache-line.
class Bucket {
  SmallVector<FieldDecl *, 64> Fields;
  int Size = 0;

public:
  virtual ~Bucket() = default;

  SmallVector<FieldDecl *, 64> &fields() { return Fields; }
  void addField(FieldDecl *Field, int FieldSize);
  virtual bool canFit(int FieldSize) const {
    return Size + FieldSize <= CACHE_LINE;
  }
  virtual bool isBitfieldRun() const { return false; }
  bool full() const { return Size >= CACHE_LINE; }
};

void Bucket::addField(FieldDecl *Field, int FieldSize) {
  Size += FieldSize;
  Fields.push_back(Field);
}

struct BitfieldRunBucket : public Bucket {
  bool canFit(int FieldSize) const override { return true; }
  bool isBitfieldRun() const override { return true; }
};

void randomizeStructureLayoutImpl(const ASTContext &Context,
                                  llvm::SmallVectorImpl<FieldDecl *> &FieldsOut,
                                  std::mt19937 &RNG) {
  // All of the Buckets produced by best-effort cache-line algorithm.
  SmallVector<std::unique_ptr<Bucket>, 16> Buckets;

  // The current bucket of fields that we are trying to fill to a cache-line.
  std::unique_ptr<Bucket> CurrentBucket;

  // The current bucket containing the run of adjacent bitfields to ensure they
  // remain adjacent.
  std::unique_ptr<BitfieldRunBucket> CurrentBitfieldRun;

  // Tracks the number of fields that we failed to fit to the current bucket,
  // and thus still need to be added later.
  size_t Skipped = 0;

  while (!FieldsOut.empty()) {
    // If we've Skipped more fields than we have remaining to place, that means
    // that they can't fit in our current bucket, and we need to start a new
    // one.
    if (Skipped >= FieldsOut.size()) {
      Skipped = 0;
      Buckets.push_back(std::move(CurrentBucket));
    }

    // Take the first field that needs to be put in a bucket.
    auto FieldIter = FieldsOut.begin();
    FieldDecl *FD = *FieldIter;

    if (FD->isBitField() && !FD->isZeroLengthBitField()) {
      // Start a bitfield run if this is the first bitfield we have found.
      if (!CurrentBitfieldRun)
        CurrentBitfieldRun = std::make_unique<BitfieldRunBucket>();

      // We've placed the field, and can remove it from the "awaiting Buckets"
      // vector called "Fields."
      CurrentBitfieldRun->addField(FD, /*FieldSize is irrelevant here*/ 1);
      FieldsOut.erase(FieldIter);
      continue;
    }

    // Else, current field is not a bitfield. If we were previously in a
    // bitfield run, end it.
    if (CurrentBitfieldRun)
      Buckets.push_back(std::move(CurrentBitfieldRun));

    // If we don't have a bucket, make one.
    if (!CurrentBucket)
      CurrentBucket = std::make_unique<Bucket>();

    uint64_t Width = Context.getTypeInfo(FD->getType()).Width;
    if (Width >= CACHE_LINE) {
      std::unique_ptr<Bucket> OverSized = std::make_unique<Bucket>();
      OverSized->addField(FD, Width);
      FieldsOut.erase(FieldIter);
      Buckets.push_back(std::move(OverSized));
      continue;
    }

    // If it fits, add it.
    if (CurrentBucket->canFit(Width)) {
      CurrentBucket->addField(FD, Width);
      FieldsOut.erase(FieldIter);

      // If it's now full, tie off the bucket.
      if (CurrentBucket->full()) {
        Skipped = 0;
        Buckets.push_back(std::move(CurrentBucket));
      }
    } else {
      // We can't fit it in our current bucket. Move to the end for processing
      // later.
      ++Skipped; // Mark it skipped.
      FieldsOut.push_back(FD);
      FieldsOut.erase(FieldIter);
    }
  }

  // Done processing the fields awaiting a bucket.

  // If we were filling a bucket, tie it off.
  if (CurrentBucket)
    Buckets.push_back(std::move(CurrentBucket));

  // If we were processing a bitfield run bucket, tie it off.
  if (CurrentBitfieldRun)
    Buckets.push_back(std::move(CurrentBitfieldRun));

  std::shuffle(std::begin(Buckets), std::end(Buckets), RNG);

  // Produce the new ordering of the elements from the Buckets.
  SmallVector<FieldDecl *, 16> FinalOrder;
  for (const std::unique_ptr<Bucket> &B : Buckets) {
    llvm::SmallVectorImpl<FieldDecl *> &RandFields = B->fields();
    if (!B->isBitfieldRun())
      std::shuffle(std::begin(RandFields), std::end(RandFields), RNG);

    llvm::append_range(FinalOrder, RandFields);
  }

  FieldsOut = FinalOrder;
}

} // anonymous namespace

namespace clang {
namespace randstruct {

bool randomizeStructureLayout(const ASTContext &Context, RecordDecl *RD,
                              SmallVectorImpl<Decl *> &FinalOrdering) {
  SmallVector<FieldDecl *, 64> RandomizedFields;
  SmallVector<Decl *, 8> PostRandomizedFields;

  unsigned TotalNumFields = 0;
  for (Decl *D : RD->decls()) {
    ++TotalNumFields;
    if (auto *FD = dyn_cast<FieldDecl>(D))
      RandomizedFields.push_back(FD);
    else if (isa<StaticAssertDecl>(D) || isa<IndirectFieldDecl>(D))
      PostRandomizedFields.push_back(D);
    else
      FinalOrdering.push_back(D);
  }

  if (RandomizedFields.empty())
    return false;

  // Struct might end with a flexible array or an array of size 0 or 1,
  // in which case we don't want to randomize it.
  FieldDecl *FlexibleArray =
      RD->hasFlexibleArrayMember() ? RandomizedFields.pop_back_val() : nullptr;
  if (!FlexibleArray) {
    if (const auto *CA =
            dyn_cast<ConstantArrayType>(RandomizedFields.back()->getType()))
      if (CA->getSize().sle(2))
        FlexibleArray = RandomizedFields.pop_back_val();
  }

  std::string Seed =
      Context.getLangOpts().RandstructSeed + RD->getNameAsString();
  std::seed_seq SeedSeq(Seed.begin(), Seed.end());
  std::mt19937 RNG(SeedSeq);

  randomizeStructureLayoutImpl(Context, RandomizedFields, RNG);

  // Plorp the randomized decls into the final ordering.
  llvm::append_range(FinalOrdering, RandomizedFields);

  // Add fields that belong towards the end of the RecordDecl.
  llvm::append_range(FinalOrdering, PostRandomizedFields);

  // Add back the flexible array.
  if (FlexibleArray)
    FinalOrdering.push_back(FlexibleArray);

  assert(TotalNumFields == FinalOrdering.size() &&
         "Decl count has been altered after Randstruct randomization!");
  (void)TotalNumFields;
  return true;
}

} // end namespace randstruct
} // end namespace clang