validator/cpp/htmlparser/allocator.h - main - githubmirror/amphtml

validator/cpp/htmlparser/allocator.h
369 строк14 KB
Allan Banaag
Sync for validator cpp engine and cpp htmlparser (#39797)
06 фев 2024, 01:17
06 фев 2024, 01:176e751a4
// An average HTML DOM tree consists of hundreds or thousands of nodes and
// their attributes. The malloc/new and free/delete are very expensive
// operations for small objects and htmlparser spends majority of the time in
// allocation and deallocation of these small objects.
//
// Usage:
// One Allocator for each type. This approach simplifies the design and
// alignment requirements of different types.
//
//     // Allocator for Node with 8k blocks, and 8 byte alignment boundary.
//     Allocator<Node> node_allocator(8192);
//
//     // Allocator for Attributes with 4k blocks, and 1 byte alignment.
//     Allocator<Attribute> attr_allocator(4096);
//
//     // Default block size.
//     Allocator<Node> node_allocator;  // Block size = OS page_size.
//
// The allocator takes care of alignment requirements of the objects. The blocks
// are always created in the multiples of page_size. For the following Allocator
// the block size is upgraded to 4096 for 4k page_size or 8192 for 8k page_size.
//
//     Allocator<Node> node_allocator(3000);  // Block size = 4096.
//
// To construct the object:
//   Node* node = node_allocator.Construct(NodeType::ELEMENT_NODE);
//
// The construct method supports varargs. Following forwards 4 parameters to the
// AboutMe constructor.
//   Allocator<AboutMe> alloc;
//   AboutMe* name = alloc.Construct("John", "Doe", 94043, MALE);
//
// THREAD SAFETY: Allocator is not thread safe. Multiple threads cannot call
// Allocate() simultaneously. In multi-threaded program a thread local allocator
// per thread is recommended.
//
//
// ---------------------------------------------------------------------------
//                   Internals for code reviewers:
// ---------------------------------------------------------------------------
// The allocator maintains linked list of blocks of memory buffers for
// allocation of small objects.  It allocates blocks on demand, one block at a
// time.
//
// The block is always multiple of page size. It is rounded to nearest page size
// multiple in case caller provided a different size which is not multiple of
// page size. So a 3000 block size request becomes 4096 block and 5000 block
// size request becomes 8192 block size respectively on a 4k page size kernel.
//
// The block_size is the only configurable parameter, and depends on three
// fators: A) Object size, B) Number of objects and C) Alignment boundary.
//
//
// Alignment requirements:
// Every object type has a property called alignment requirement, which is an
// integer value of type std::size_t representing the number of bytes  between
// successive addresses at which objects of this type can be allocated.
// The valid alignment values are non-negative integral powers of two.
//
// We call an object naturally aligned if its address is aligned to its size.
// It's called misaligned otherwise. For example, an 8-byte floating-point data
// is naturally aligned if the address used to identify it has an 8-byte
// alignment.
//
// Following data struture contains members totaling 13 bytes, but it's actual
// size is 24 bytes due to 8 byte alignment.
//
// Alignment is always equal to the largest sized element in the structure.
//
// struct {
//   int32_t a;  // 4 bytes.
//   int64_t b;  // 8 bytes.
//   char c;     // 1 byte.
// };
//
// The above data structure will be padded by compiler to satisfy alignment
// requirement.
// struct {
//   int32_t a;     // 4 byte                                 0x0000
//   char _pad[4];  // compiler added 8 byte padding.
//   int64_t b;     // 8 byte (now at 8 byte alignment).      0x0008
//   char c;        // 1 byte (also at 8 byte alignment).     0x0010
//   char _pad[7]   // compiler added padding
// };
//
// The same data structure if fields are re-organized will consume 16 bytes,
// still at 8 byte alignment.
// struct {
//   int32_t a;     // 4 byte at 0x00000 (like above).        0x0000
//   char c;        // 1 byte char.                           0x0001
//   chr _pad[3]    // 3 bytes for 8 byte alignment.
//   int64_t b;     // at 8 byte alignment.                   0x0010
// };
//
// Allocator computes the alignment requirement of the Type and starts the block
// at the address which is multiple of 8, and hence we say the block is aligned.
//
// +-------------------------------------------------------------------------+
// | Address  |    Block 1  |  Address  |   Block 2  | Address  |  Block 3   |
// +----------+-------------+-----------+------------+----------+------------+
// |   10     |    waste    |   120     |    Obj22   |   164    |   waste    |
// |   11     |    waste    |   121     |            |   165    |   waste    |
// |   12     |    waste    |   122     |            |   166    |   waste    |
// |   13     |    waste    |   123     |            |   167    |   waste    |
// |   14     |    waste    |   124     |            |   168    |   Obj33    |
// |   15     |    waste    |   125     |            |   169    |            |
// |   16     |    Obj1     |   126     |            |   170    |            |
// |   17     |             |   127     |            |   171    |            |
// |   N      |             |   N       |            |   N      |            |
// +-------------------------------------------------------------------------+
//
// In the above diagram there are three blocks with alignment of 8.
//
// Block one start address is 16 so 6 bytes are skipped (or wasted).
// Block two start address is 120 since it is multiple of 8.
// Block three start address is 68 causing 4 bytes to skip (or wasted).
//
// The block alignment is done by std::align or AlignFreeAddress method.
//
// The block is considered full when the remaining bytes are less than the
// object size. So the remaining bytes in the block are skipped and new block
// created. In our tests for 500 objects of 144 bytes and 4096 bytes block
// about 1024 bytes wasted.
//
// Since objects size is always multiple of alignment, subsequent objects can be
// allocated sequentially in the block. So if the object size is 96 bytes, the
// second object in block 1 will be allocated 112 address in block 1.
//
// A block is allocated using operator new at the time of block initialization
// and start address aligned. See NewBlock();
//
// A block is freed at the time of destruction of the allocator object.
// The allocator takes complete ownership of the objects it allocates, client is
// not responsible for deallocating or destroying the objects allocated by this
// allocator. Allocator will call the destructors of the objects it allocated.
// See ~Allocator() and Destroy() method.
//
// IMPORTANT: Tree like structure must not destroy the child nodes or sibling
// nodes. Allocator destroys all the objects and call its destructor, it is an
// error to invoke destructors on objects allocated by this allocator. Allocator
// is the master owner of all the objects. Client treats all objects as const
// pointer as far as destruction goes.
//
// It is not possible to destroy random objects or free up the slots to be
// re-used for allocation of objects. This allocator is used for html parsing
// which should free up the resources after document parsing. A singleton
// allocator for example will keep growing unless Reset() is called upon each
// new parsing.
//
// Bit shifting syntax used in this source:
// A) To round the block size to nearest page size (4096) multiple:
//    ((block_size - 1) | (page_size - 1) + 1.
//    Examples:
//    - block_size = 3000;
//     (3000 - 1) | (4096 - 1) + 1 = 4096.
//    - block_size = 5000;
//     (5000 - 1) | (4096 - 1) + 1 = 8096.
//
// B) If N is multiple of A.
//    (N & (A - 1)) == 0
//    This can also be achieved by modulo operator N % A == 0.
//    Examples:
//    - 40 is multiple of 8?
//     40 & (8 - 1) == 0;
//    - 62 is multiple of 4?
//     60 & (4 - 1) != 0;

#ifndef CPP_HTMLPARSER_ALLOCATOR_H_
#define CPP_HTMLPARSER_ALLOCATOR_H_

#include <unistd.h>  // For getpagesize()

#include <array>
#include <cstring>
#include <memory>
#include <tuple>
#include <vector>

namespace htmlparser {

template <class T>
class Allocator {
 public:
  explicit Allocator(std::size_t block_size = 0) :
    alignment_(std::alignment_of_v<T>),
    // Rounds the block_size_ to page size multiple.
    // 3000 becomes 4096 and 5000 becomes 8192 for 4k page size OS.
    block_size_(
        ((block_size < 1 ? 0 : block_size - 1) | (getpagesize() - 1)) + 1),
    object_size_(sizeof(T)),
    remaining_(0),
    next_free_(nullptr),
    blocks_allocated_(0),
    block_(nullptr) {}

  ~Allocator() {
    FreeBlocks();
  }

  Allocator(const Allocator&) = delete;
  Allocator& operator=(const Allocator&) = delete;

  // Allocates memory of same size required to construct object of type T.
  // Returns nullptr if alloction failed.
  void* Allocate() {
    // Checks if remaining bytes in block are less than object size, or
    // reamining bytes after alignment is less than object size.
    // Add a new block.
    if (object_size_ > remaining_ || !AlignFreeAddress()) {
      if (!NewBlock()) return nullptr;
    }

    // Get the address for object allocation.
    last_alloc_ = next_free_;
    remaining_ -= object_size_;
    // Move the pointer for next object.
    next_free_ += object_size_;
    return static_cast<void*>(last_alloc_);
  }

  // Allocates memory and constructs the object.
  // Returns nullptr if memory allocation failed.
  template <typename ...Args>
  T* Construct(Args&& ...args) {
    void* mem = Allocate();
    // New object or nullptr if memory allocation failed.
    return mem ? new (mem) T(std::forward<Args>(args)...) : nullptr;
  }

  // Default constructor.
  T* Construct() {
    void* mem = Allocate();
    return mem ? new (mem) T() : nullptr;
  }

  // Deallocates the blocks and restores the allocator for reuse.
  void Reset() {
    FreeBlocks();
    next_free_ = nullptr;
    remaining_ = 0;
  }

  // Used only by test or development environment.
  std::tuple<int /*alignment*/,
             int /*block_size*/,
             int /*object_size*/,
             unsigned char* /*last_alloc*/,
             unsigned char* /*next_free*/,
             std::size_t /*remaining*/,
             uint32_t /*blocks_allocated*/> DebugInfo() const {
    return {alignment_, block_size_, object_size_, last_alloc_, next_free_,
      remaining_, blocks_allocated_};
  }

 private:
  struct Block {
    Block* previous;
    void* buf;
  };

  // Deallocates the blocks.
  void FreeBlocks() {
    Block* current_block = block_;
    bool partial = true;
    while (current_block != nullptr) {
      Block* previous = current_block->previous;
      Destroy(current_block, partial);
      partial = false;
      FreeBlockMemory(current_block);
      delete current_block;
      blocks_allocated_--;
      current_block = previous;
    }
  }

  // Creates a new block.
  bool NewBlock() {
    Block* block = new Block;
    block->previous = block_;
    if (alignment_ <=  __STDCPP_DEFAULT_NEW_ALIGNMENT__) {
      block->buf = ::operator new(block_size_);
    } else {
      block->buf = ::operator new(block_size_, std::align_val_t(alignment_));
    }
    std::memset(block->buf, 0, block_size_);
    // Align the block to alignment boundary.
    //
    // The adjusted space may be lesser than block size.
    std::size_t adjusted_space = block_size_;
    if (alignment_ > 1) {
      if (block->buf = std::align(alignment_, block_size_, block->buf,
                                  adjusted_space);
          block->buf == nullptr) {
        // In case std::align fails, try manual alignment.
        if (!AlignFreeAddress()) {
          return false;
        }
      } else if (adjusted_space < object_size_) {
        return false;
      }
    }

    next_free_ = static_cast<unsigned char*>(block->buf);
    remaining_ = adjusted_space;
    blocks_allocated_++;
    block_ = block;
    return true;
  }

  void FreeBlockMemory(Block* block) {
    if (alignment_ <= __STDCPP_DEFAULT_NEW_ALIGNMENT__) {
      ::operator delete(block->buf, block_size_);
      block->buf = nullptr;
    } else {
      ::operator delete(block->buf, block_size_, std::align_val_t(alignment_));
      block->buf = nullptr;
    }
  }

  // Destroys the T objects allocated and constructed using this block.
  // If the block is only partially consumed, destroys only objects allocated
  // in the partial space.
  void Destroy(Block* block, bool partial_allocation = false) {
    unsigned char* t_ptr = static_cast<unsigned char*>(block->buf);
    unsigned char* block_end = t_ptr + block_size_;
    std::size_t remaining = block_end - t_ptr;
    // All offsets are aligned, so simply increment and destroy.
    if ((object_size_ & (alignment_ - 1)) == 0) {
      while (remaining >= object_size_) {
        reinterpret_cast<T*>(t_ptr)->~T();
        t_ptr += object_size_;
        if (partial_allocation && t_ptr >= next_free_) {
          return;
        }
        remaining -= object_size_;
      }
    }
  }

  // If the block's address is not aligned, moves the pointer to the address
  // that is multiple of aligment_.
  bool AlignFreeAddress() {
    // Checks how many bytes to skip to be at the correct alignment.
    if (const std::size_t skip =
            reinterpret_cast<std::size_t>(next_free_) & (alignment_ - 1);
        skip > 0) {
      auto waste = remaining_ - skip;
      if (waste >= remaining_) return false;
      next_free_ += waste;
      remaining_ -= waste;
    }

    return true;
  }

  const std::size_t alignment_;
  const std::size_t block_size_;
  const std::size_t object_size_;
  std::size_t remaining_;
  unsigned char* last_alloc_;
  unsigned char* next_free_;
  uint32_t blocks_allocated_;

  Block* block_;
};

}  // namespace htmlparser

#endif  // CPP_HTMLPARSER_ALLOCATOR_H_