src/google/protobuf/string_block.h

// Protocol Buffers - Google's data interchange format
// Copyright 2023 Google Inc.  All rights reserved.
// https://developers.google.com/protocol-buffers/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// This file defines the internal StringBlock class

#ifndef GOOGLE_PROTOBUF_STRING_BLOCK_H__
#define GOOGLE_PROTOBUF_STRING_BLOCK_H__

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <string>

#include "absl/base/attributes.h"
#include "absl/log/absl_check.h"
#include "google/protobuf/arena_align.h"
#include "google/protobuf/port.h"

// Must be included last.
#include "google/protobuf/port_def.inc"

namespace google {
namespace protobuf {
namespace internal {

// StringBlock provides heap allocated, dynamically sized blocks (mini arenas)
// for allocating std::string instances. StringBlocks are allocated through
// the `New` function, and must be freed using the `Delete` function.
// StringBlocks are automatically sized from 256B to 8KB depending on the
// `next` instance provided in the `New` function to keep the average maximum
// unused space limited to 25%, or up to 4KB.
class alignas(std::string) StringBlock {
 public:
  StringBlock() = delete;
  StringBlock(const StringBlock&) = delete;
  StringBlock& operator=(const StringBlock&) = delete;

  // Allocates a new StringBlock pointing to `next`, which can be null.
  // The size of the returned block depends on the allocated size of `next`.
  static StringBlock* New(StringBlock* next);

  // Deletes `block`. `block` must not be null.
  static size_t Delete(StringBlock* block);

  StringBlock* next() const;

  // Returns the string instance at offset `offset`.
  // `offset` must be a multiple of sizeof(std::string), and be less than or
  // equal to `effective_size()`. `AtOffset(effective_size())` returns the
  // end of the allocated string instances and must not be de-referenced.
  ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* AtOffset(size_t offset);

  // Returns a pointer to the first string instance in this block.
  ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* begin();

  // Returns a pointer directly beyond the last string instance in this block.
  ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* end();

  // Returns the total allocation size of this instance.
  size_t allocated_size() const { return allocated_size_; }

  // Returns the effective size available for allocation string instances.
  // This value is guaranteed to be a multiple of sizeof(std::string), and
  // guaranteed to never be zero.
  size_t effective_size() const;

 private:
  static_assert(alignof(std::string) <= sizeof(void*), "");
  static_assert(alignof(std::string) <= ArenaAlignDefault::align, "");

  ~StringBlock() = default;

  explicit StringBlock(StringBlock* next, uint32_t size,
                       uint32_t next_size) noexcept
      : next_(next), allocated_size_(size), next_size_(next_size) {}

  static constexpr uint32_t min_size() { return size_t{256}; }
  static constexpr uint32_t max_size() { return size_t{8192}; }

  // Returns the size of the next block.
  size_t next_size() const { return next_size_; }

  StringBlock* const next_;
  const uint32_t allocated_size_;
  const uint32_t next_size_;
};

inline StringBlock* StringBlock::New(StringBlock* next) {
  // Compute required size, rounding down to a multiple of sizeof(std:string)
  // so that we can optimize the allocation path. I.e., we incur a (constant
  // size) MOD() operation cost here to avoid any MUL() later on.
  uint32_t size = min_size();
  uint32_t next_size = min_size();
  if (next) {
    size = next->next_size_;
    next_size = std::min(size * 2, max_size());
  }
  size -= (size - sizeof(StringBlock)) % sizeof(std::string);
  void* p = ::operator new(size);
  return new (p) StringBlock(next, size, next_size);
}

inline size_t StringBlock::Delete(StringBlock* block) {
  ABSL_DCHECK(block != nullptr);
  size_t size = block->allocated_size();
  internal::SizedDelete(block, size);
  return size;
}

inline StringBlock* StringBlock::next() const { return next_; }

inline size_t StringBlock::effective_size() const {
  return allocated_size_ - sizeof(StringBlock);
}

ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::AtOffset(
    size_t offset) {
  ABSL_DCHECK_LE(offset, effective_size());
  return reinterpret_cast<std::string*>(reinterpret_cast<char*>(this + 1) +
                                        offset);
}

ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::begin() {
  return AtOffset(0);
}

ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::end() {
  return AtOffset(effective_size());
}

}  // namespace internal
}  // namespace protobuf
}  // namespace google

#include "google/protobuf/port_undef.inc"

#endif  // GOOGLE_PROTOBUF_STRING_BLOCK_H__