Introduce `EnvArray` data structure.

[delcypher]

Summary

It is a convenient data structure for operating on environment-variable
like arrays. The type takes template parameters that control the amount
of statically allocated storage the type has. The type uses this storage
in preference to performing heap allocations and has options to avoid
performing heap allocations altogether when performing insertions.

This design was chosen because it will be used in an environment that
may be memory constrained (just before launching a symbolizer process
where a out-of-memory situation may have ocurred).

Several unit tests are included but the type is not currently used
in any runtimes.

[vitalybuka]

Can we see patches where it's going to be used?
Can you show how this with D78050 simplify sanitizer?

[vitalybuka]

In D78051#1982423, @vitalybuka wrote:

Can we see patches where it's going to be used?
Can you show how this with D78050 simplify sanitizer?

Oh, I see some in the stack.

[delcypher]

Adapt to ArrayRef<> -> MutableArrayRef<> change.

[vitalybuka]

To my taste it's too complicated for task it's going to solve.

compiler-rt/lib/sanitizer_common/sanitizer_env_array.h

53

I would prefer if we avoid parameters which can be avoided.
How user should decide which size to use?

106

It can be much simpler without
"bool shallow_copy, bool allow_heap_allocations, bool overwrite"

144

As I understand the goal of the class to manage copy of env variables.
However public interface expose to much details about internal storage.
Could you please limit public interface as much as possible?

[vitalybuka]

I would recommend to keep the bare minimum you need right now, and remove all stuff added for hypothetical future.

[delcypher]

In D78051#1982483, @vitalybuka wrote:

I would recommend to keep the bare minimum you need right now, and remove all stuff added for hypothetical future.

Thanks for the initial feedback. Yes it probably is too complicated.

I've actually come with a much simpler solution to the problem I'm trying to solve so for now I am going to abandon these changes. I'll resurrect them if my solution turns out to be insufficient.

[delcypher]

Abandoning this change in favour of:

• https://reviews.llvm.org/D78178
• https://reviews.llvm.org/D78179

compiler-rt/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_IMPL_HEADERS
   sanitizer_common_interceptors_ioctl.inc
   sanitizer_common_interface.inc
   sanitizer_common_interface_posix.inc
   sanitizer_common_syscalls.inc
   sanitizer_coverage_interface.inc
   sanitizer_dbghelp.h
   sanitizer_deadlock_detector.h
   sanitizer_deadlock_detector_interface.h
+  sanitizer_env_array.h
   sanitizer_errno.h
   sanitizer_errno_codes.h
   sanitizer_file.h
   sanitizer_flag_parser.h
   sanitizer_flags.h
   sanitizer_flags.inc
   sanitizer_freebsd.h
   sanitizer_fuchsia.h

compiler-rt/lib/sanitizer_common/sanitizer_env_array.h

+//===-- sanitizer_env_array.h -----------------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// `EnvArray` is a convenient date type for operating on environment variable
+// like arrays.
+//
+// In all cases `EnvArray` owns the storage for the environment array (array of
+// pointers to C strings). In all cases (except when calling
+// `copyFromRawEnv(...)` with `shallow_copy=true`) `EnvArray` owns the storage
+// for the C strings that the environment array points to.
+//
+// EnvArray's implementation is designed to be usable in a memory constrained
+// environment so it has template parameters that control the available
+// statically allocated storage. This statically allocated storage make it
+// possible to avoid performing heap-allocations. Insertion operations have an
+// `allow_heap_allocations` parameter. If `allow_heap_allocations` is `false`
+// the operation will only try to use statically allocated storage. If
+// `allow_heap_allocations` is `true` the operation will try to use statically
+// allocated storage but if that fails then `EnvArray` will switch over to heap
+// allocated storage.
+//
+// The static storage for strings behaves as-if it was allocated by a bump
+// pointer allocator that is only capable of free-ing entries in the reverse
+// order that they were allocated.
+//
+// A `EnvArrayHeapBacked` type alias is provided that will always heap allocate
+// storage.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_ENV_ARRAY_H
+#define SANITIZER_ENV_ARRAY_H
+#include "sanitizer_common/sanitizer_allocator_internal.h"
+#include "sanitizer_internal_defs.h"
+#include "sanitizer_libc.h"
+#include "sanitizer_mutable_array_ref.h"
+#include "sanitizer_vector.h"
+
+namespace __sanitizer {
+
+// `STATIC_ENV_SLOTS` - The number of statically allocated environment variable
+// slots. The actual number of usable statically allocated slots is one less due
+// to the last slot always containing a nullptr.
+//
+// `STATIC_STRING_STORAGE_SIZE` - The number of bytes static allocated for
+// string storage. The static storage essentially acts like a bump pointer
+// allocator and is not very sophisticated.
+template <uptr STATIC_ENV_SLOTS = 64, uptr STATIC_STRING_STORAGE_SIZE = 64>
+class EnvArray {
+ public:
+  EnvArray()
+      : available_string_storage_slice_(string_storage_),
+        null_terminator_idx_(0) {
+    resetStaticEnvPStorage();
+    resetStaticStringStorage();
+  }
+  ~EnvArray() { reset(); }
+
+  // Prevent accidental assignments/copies.
+  EnvArray(const EnvArray&) = delete;
+  EnvArray(const EnvArray&&) = delete;
+  EnvArray operator=(const EnvArray&) = delete;
+  EnvArray operator=(const EnvArray&&) = delete;
+
+  char* operator[](uptr idx) {
+    CHECK_LE(idx, null_terminator_idx_);
+    return getStorage()[idx];
+  }
+
+  void reset() {
+    CHECK(isValid());
+    for (unsigned index = 0; index < owned_ptrs_.Size(); ++index) {
+      // This assumes that `internal_strdup()` allocates via InternalAlloc().
+      InternalFree(owned_ptrs_[index]);
+    }
+    resetStaticEnvPStorage();
+    resetStaticStringStorage();
+    owned_ptrs_.Reset();
+    envp_storage_heap_.Reset();
+    null_terminator_idx_ = 0;
+    CHECK(isValid());
+  }
+
+  // Copies environment variable entries form `envp` into this instance.
+  //
+  // `shallow_copy` - If true the strings will not be duplicated. This means
+  // that the `EnvArray` does not have ownership over these strings and
+  // therefore it is the client's responsiblity to ensure they remain valid.
+  //
+  // `allow_heap_allocations` - This method tries to use statically allocated
+  // storage.  If that fails and this option is `false` then this method will
+  // give up allocating the particular entry that was being copied. If using
+  // statically allocated storage fails but `allow_heap_allocations` is `true`
+  // then heap allocated storage will be used.
+  //
+  // `overwrite` - If `true` then overwrite existing entries in this instance
+  // that are also in `envp`.
+  //
+  // Returns number of successfully inserted entries.
+  uptr copyFromRawEnv(char** envp, bool shallow_copy,
+                      bool allow_heap_allocations, bool overwrite) {
+    CHECK(isValid());
+    uptr index = 0;
+    uptr entries_copied = 0;
+    while (char* entry = envp[index]) {
+      bool found = false;
+      char* existing_entry = nullptr;
+      uptr existing_index = getIndexForEntry(entry, &found);
+      if (found) {
+        if (!overwrite) {
+          ++index;
+          continue;
+        }
+        existing_entry = getStorage()[existing_index];
+      }
+      char* entry_to_add = allocEntry(entry, shallow_copy,
+                                      allow_heap_allocations, existing_entry);
+      if (!entry_to_add) {
+        // Allocation failed
+        CHECK(isValid());
+        return entries_copied;
+      }
+      if (!insertEntry(entry_to_add, allow_heap_allocations)) {
+        // Insertion failed
+        if (entry_to_add != existing_entry) {
+          // Avoid leaking `new_entry` provided it wasn't a re-used entry.
+          freeEntry(entry_to_add);
+        }
+        CHECK(isValid());
+        return entries_copied;
+      }
+      ++index;
+      ++entries_copied;
+    }
+    CHECK(isValid());
+    return entries_copied;
+  }
+
+  bool envArrayOnHeap() const { return envp_storage_heap_.Size() > 0; }
+
+  const char* get(const char* key) {
+    bool found = false;
+    uptr index = getIndexForKey(key, &found);
+    if (found) {
+      return getValueFromEntry(getStorage()[index]);
+    }
+    return nullptr;
+  }
+
+  uptr getNumEnvEntries() { return null_terminator_idx_; }
+
+  uptr getNumAvailableStaticEnvEntries() {
+    if (envArrayOnHeap())
+      return 0;
+    return getStaticEnvStorageSize() - getNumEnvEntries() - 1;
+  }
+
+  uptr getAvailableStaticStringStorageSize() {
+    if (stringStorageOnHeap())
+      return 0;
+    return available_string_storage_slice_.size();
+  }
+
+  // Note previously returned values may be invalidated after performing
+  // insertion due to switching from static to heap storage. Therefore
+  // `MutableArrayRef<char*>.data()` should only be stored if no more insertion
+  // operations will be performed.
+  MutableArrayRef<char*> getStorage() {
+    CHECK(isValid());
+    if (envArrayOnHeap()) {
+      return getHeapEnvpRef();
+    }
+    return getStaticEnvpRef();
+  }
+
+  uptr getIndexForKey(const char* key, bool* found) {
+    CHECK(isValid());
+    CHECK(found);
+    *found = false;
+    uptr cmp_len = internal_strlen(key);
+    CHECK_GT(cmp_len, 0);
+    auto envp_ref = getStorage();
+    for (unsigned index = 0; index < null_terminator_idx_; ++index) {
+      if (internal_strncmp(key, envp_ref[index], cmp_len) == 0) {
+        // Check next character is `=`
+        if (envp_ref[index][cmp_len] == '=') {
+          // Match
+          *found = true;
+          return index;
+        }
+      }
+    }
+    return 0;
+  }
+
+  uptr getStaticEnvStorageSize() { return STATIC_ENV_SLOTS; }
+
+  uptr getStaticStringStorageSize() { return STATIC_STRING_STORAGE_SIZE; }
+
+  bool set(const char* key, const char* value, bool overwrite = true,
+           bool allow_heap_allocations = true) {
+    CHECK(isValid());
+    bool found = false;
+    uptr index = getIndexForKey(key, &found);
+    char* new_entry = nullptr;
+    char* existing_entry = nullptr;
+    if (found) {
+      if (!overwrite) {
+        CHECK(isValid());
+        return false;
+      }
+      existing_entry = getStorage()[index];
+    }
+    if (!new_entry)
+      new_entry = allocEntryFromKeyAndValue(key, value, allow_heap_allocations,
+                                            existing_entry);
+    if (!new_entry) {
+      CHECK(isValid());
+      return false;
+    }
+    if (!insertEntry(new_entry, allow_heap_allocations)) {
+      if (new_entry != existing_entry) {
+        // Avoid leaking `new_entry` provided it wasn't a re-used entry.
+        freeEntry(new_entry);
+      }
+      CHECK(isValid());
+      return false;
+    }
+    CHECK(isValid());
+    return true;
+  }
+
+  bool stringStorageOnHeap() const { return owned_ptrs_.Size() > 0; }
+
+  bool unset(const char* key) {
+    CHECK(isValid());
+    bool found = false;
+    uptr index = getIndexForKey(key, &found);
+    if (!found) {
+      CHECK(isValid());
+      return false;
+    }
+    removeEntryAt(index);
+    CHECK(isValid());
+    return true;
+  }
+
+  void removeEntryAt(uptr index) {
+    CHECK_LT(index, null_terminator_idx_);
+    CHECK(isValid());
+    char* entry = getStorage()[index];
+    CHECK(entry);
+    freeEntry(entry);
+    // Shift subsequent entries back
+    for (unsigned current_index = index; current_index < null_terminator_idx_;
+         ++current_index) {
+      getStorage()[current_index] = getStorage()[current_index + 1];
+    }
+    --null_terminator_idx_;
+    if (envArrayOnHeap()) {
+      envp_storage_heap_.PopBack();
+    }
+    // TODO(dliew): Could implement migration back to static storage here
+    // if enough entries are removed.
+    CHECK(isValid());
+  }
+
+  bool usingHeap() const { return envArrayOnHeap() || stringStorageOnHeap(); }
+
+ private:
+  char* allocEntry(char* entry, bool shallow_copy, bool allow_heap_allocations,
+                   char* existing_entry) {
+    if (shallow_copy) {
+      // Don't allocate anything. The client manages the lifetime of this
+      // string.
+      return entry;
+    }
+
+    if (existing_entry) {
+      // We are allocating for entry we already hold. See if we can re-use it to
+      // avoid allocation.
+      if (entryIsOwned(existing_entry)) {
+        // We can only write into pointers that we own.
+        uptr existing_entry_size = internal_strlen(existing_entry) + 1;
+        uptr required_entry_size = internal_strlen(entry) + 1;
+        if (required_entry_size <= existing_entry_size) {
+          // The existing entry has sufficient space. Re-use it.
+          internal_strncpy(existing_entry, entry, existing_entry_size);
+          return existing_entry;
+        }
+      }
+    }
+
+    char* new_entry = nullptr;
+    uptr required_space = internal_strlen(entry) + 1;
+    if (available_string_storage_slice_.size() < required_space) {
+      // Need to do heap allocation
+      if (!allow_heap_allocations)
+        return nullptr;
+      new_entry = internal_strdup(entry);
+      owned_ptrs_.PushBack(new_entry);
+      return new_entry;
+    }
+
+    // Use static storage.
+    available_string_storage_slice_.copyFrom(refFrom(entry));
+    new_entry = available_string_storage_slice_.data();
+    auto new_slice = available_string_storage_slice_.slice(required_space);
+    CHECK_EQ(available_string_storage_slice_.size() - required_space,
+             new_slice.size());
+    available_string_storage_slice_ = new_slice;
+    return new_entry;
+  }
+
+  char* allocEntryFromKeyAndValue(const char* key, const char* value,
+                                  bool allow_heap_allocations,
+                                  char* existing_entry) {
+    char* new_entry = nullptr;
+    uptr required_space = getEntrySizeFor(key, value);
+
+    if (existing_entry) {
+      // We are allocating for entry we already hold. See if we can re-use it to
+      // avoid allocation.
+      if (entryIsOwned(existing_entry)) {
+        // We can only write into pointers that we own.
+        uptr existing_entry_size = internal_strlen(existing_entry) + 1;
+        uptr required_entry_size = getEntrySizeFor(key, value);
+        if (required_entry_size <= existing_entry_size) {
+          // The existing entry has sufficient space. Re-use it.
+          writeKeyAndValueToEntry(
+              MutableArrayRef<char>(existing_entry, existing_entry_size), key,
+              value);
+          return existing_entry;
+        }
+      }
+    }
+
+    if (available_string_storage_slice_.size() < required_space) {
+      // Need to do heap allocation
+      if (!allow_heap_allocations)
+        return nullptr;
+      new_entry = (char*)InternalAlloc(required_space);
+      if (!new_entry)
+        return nullptr;
+      writeKeyAndValueToEntry(MutableArrayRef<char>(new_entry, required_space),
+                              key, value);
+      owned_ptrs_.PushBack(new_entry);
+      return new_entry;
+    }
+
+    // Use static storage.
+    writeKeyAndValueToEntry(available_string_storage_slice_, key, value);
+    new_entry = available_string_storage_slice_.data();
+    auto new_slice = available_string_storage_slice_.slice(required_space);
+    CHECK_EQ(available_string_storage_slice_.size() - required_space,
+             new_slice.size());
+    available_string_storage_slice_ = new_slice;
+    return new_entry;
+  }
+
+  MutableArrayRef<char> refFrom(char* value) {
+    return MutableArrayRef<char>(value, internal_strlen(value) + 1);
+  }
+
+  enum EntryTy { STATIC_ALLOC, HEAP_ALLOC, ANY_ALLOC };
+
+  bool entryIsOwned(char* entry, EntryTy entry_type = ANY_ALLOC) {
+    if (entry_type == ANY_ALLOC || entry_type == STATIC_ALLOC) {
+      if (getStaticStringStorageRef().containsPtr(entry)) {
+        return true;
+      }
+    }
+    if (entry_type == ANY_ALLOC || entry_type == HEAP_ALLOC) {
+      // FIXME(dliew): O(N).
+      for (unsigned index = 0; index < owned_ptrs_.Size(); ++index) {
+        if (owned_ptrs_[index] == entry) {
+          return true;
+        }
+      }
+    }
+    return false;
+  }
+
+  void freeEntry(char* entry) {
+    CHECK(isValid());
+    if (entryIsOwned(entry, HEAP_ALLOC)) {
+      InternalFree(entry);
+    } else if (entryIsOwned(entry, STATIC_ALLOC)) {
+      // Implement "bump pointer" like free-ing semantics. We can only free the
+      // most recently allocated item.
+      uptr entry_length = internal_strlen(entry) + 1;
+      if (reinterpret_cast<uptr>(entry) ==
+          (reinterpret_cast<uptr>(available_string_storage_slice_.data()) -
+           entry_length)) {
+        // Entry being free'd is to the left of the free space so it's the most
+        // recent.
+        CHECK_GE(entry, string_storage_);
+        uptr offset = entry - string_storage_;
+        available_string_storage_slice_ =
+            getStaticStringStorageRef().slice(offset);
+      }
+      // TODO(dliew): We could something more sophisticated here to free holes
+      // left by recompacting the storage and adjusting all the relevant
+      // pointers but that's a bit too complicated.
+    }
+    CHECK(isValid());
+  }
+  MutableArrayRef<char*> getHeapEnvpRef() {
+    return MutableArrayRef<char*>(&(envp_storage_heap_[0]),
+                                  envp_storage_heap_.Size());
+  }
+
+  uptr getIndexForEntry(char* entry, bool* found) {
+    CHECK(isValidEntry(entry));
+    CHECK(found);
+    *found = false;
+    char* eq_ptr = internal_strstr(/*haystack=*/entry, /*needle=*/"=");
+    CHECK(eq_ptr);
+    CHECK_GE(eq_ptr, entry);
+    uptr cmp_len =
+        reinterpret_cast<uptr>(eq_ptr) - reinterpret_cast<uptr>(entry) + 1;
+    auto envp_ref = getStorage();
+    for (unsigned index = 0; index < null_terminator_idx_; ++index) {
+      if (internal_strncmp(entry, envp_ref[index], cmp_len) == 0) {
+        // Found match
+        *found = true;
+        return index;
+      }
+    }
+    return 0;
+  }
+
+  MutableArrayRef<char*> getStaticEnvpRef() {
+    return MutableArrayRef<char*>(envp_storage_);
+  }
+
+  MutableArrayRef<char> getStaticStringStorageRef() {
+    return MutableArrayRef<char>(string_storage_);
+  }
+
+  const char* getValueFromEntry(char* entry) {
+    CHECK(isValidEntry(entry));
+    char* eq_ptr = internal_strstr(/*haystack=*/entry, /*needle=*/"=");
+    CHECK(eq_ptr);
+    return ++eq_ptr;
+  }
+
+  bool insertEntry(char* entry, bool allow_heap_allocations) {
+    CHECK(isValid());
+    CHECK(isValidEntry(entry));
+    bool found = false;
+    uptr found_index = getIndexForEntry(entry, &found);
+    if (found) {
+      // Overwrite existing entry
+      auto envp_ref = getStorage();
+      if (envp_ref[found_index] != entry) {
+        // Try to free the entry if it's not being re-used.
+        freeEntry(envp_ref[found_index]);
+      }
+      envp_ref[found_index] = entry;
+      CHECK(isValid());
+      return true;
+    }
+
+    // Need to insert new entry.
+    uptr insert_index = null_terminator_idx_;
+    if (!envArrayOnHeap()) {
+      // Attempt insertion to static storage
+      auto envp_ref = getStaticEnvpRef();
+      if (envp_ref.isValidIndex(insert_index + 1)) {
+        // Sufficient static storage space.
+        envp_ref[insert_index] = entry;
+        ++null_terminator_idx_;
+        envp_ref[null_terminator_idx_] = nullptr;
+        CHECK(isValid());
+        return true;
+      }
+
+      if (!allow_heap_allocations) {
+        CHECK(isValid());
+        return false;
+      }
+      // Not enough space. Convert to heap array.
+      migrateEnvpToHeap(/*size_hint=*/envp_ref.size() + 1);
+    }
+
+    CHECK(allow_heap_allocations);
+
+    // Insert entry on heap.
+    envp_storage_heap_[insert_index] = entry;
+    envp_storage_heap_.PushBack(nullptr);
+    ++null_terminator_idx_;
+    CHECK(isValid());
+    return true;
+  }
+
+  bool isValid() {
+    bool valid = true;
+    // Can't use operator[] or `getStorage()` here due to infinite recursion.
+    if (!envArrayOnHeap()) {
+      valid &= getStaticEnvpRef().isValidIndex(null_terminator_idx_);
+      valid &= (getStaticEnvpRef()[null_terminator_idx_] == nullptr);
+    } else {
+      valid &= null_terminator_idx_ < getHeapEnvpRef().size();
+      valid &= (getHeapEnvpRef()[null_terminator_idx_] == nullptr);
+    }
+    return valid;
+  }
+
+  bool isValidEntry(char* entry) {
+    return internal_strstr(/*haystack=*/entry, /*needle=*/"=") != nullptr;
+  }
+
+  void migrateEnvpToHeap(uptr size_hint) {
+    CHECK(isValid());
+    CHECK(!envArrayOnHeap());
+    auto envp_static_ref = getStaticEnvpRef();
+    if (size_hint) {
+      envp_storage_heap_.Resize(size_hint);
+    } else {
+      envp_storage_heap_.Resize(envp_static_ref.size());
+    }
+    // Migrate pointers
+    for (unsigned index = 0; index < envp_static_ref.size(); ++index) {
+      envp_storage_heap_[index] = envp_static_ref[index];
+    }
+    // Technically not necessary but it's probably best to not hold on to
+    // potentially stale pointers.
+    resetStaticEnvPStorage();
+
+    CHECK(isValid());
+    CHECK(envArrayOnHeap());
+  }
+
+  void resetStaticEnvPStorage() {
+    internal_memset(envp_storage_, 0, sizeof(envp_storage_));
+  }
+
+  void resetStaticStringStorage() {
+    internal_memset(string_storage_, 0, sizeof(string_storage_));
+    available_string_storage_slice_ = getStaticStringStorageRef();
+  }
+
+  void writeKeyAndValueToEntry(MutableArrayRef<char> entry, const char* key,
+                               const char* value) {
+    CHECK_GE(entry.size(), getEntrySizeFor(key, value));
+    internal_strncpy(entry.data(), key, entry.size());
+    internal_strncat(entry.data(), "=", entry.size());
+    internal_strncat(entry.data(), value, entry.size());
+  }
+
+  uptr getEntrySizeFor(const char* key, const char* value) {
+    // +1 for `=` and +1 for nullptr
+    return internal_strlen(key) + internal_strlen(value) + 2;
+  }
+
+  // Statically allocated storage.
+  char* envp_storage_[STATIC_ENV_SLOTS];
+  char string_storage_[STATIC_STRING_STORAGE_SIZE];
+  // Provides a view into the remaining free space for string storage.
+  MutableArrayRef<char> available_string_storage_slice_;
+  uptr null_terminator_idx_;
+  // Heap storage
+  Vector<char*> envp_storage_heap_;
+  Vector<char*> owned_ptrs_;
+};
+
+// Convenience type that always uses the heap.
+using EnvArrayHeapBacked = EnvArray<1, 1>;
+
+}  // namespace __sanitizer
+
+#endif

compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt

 
 set(SANITIZER_UNITTESTS
   sanitizer_allocator_test.cpp
   sanitizer_atomic_test.cpp
   sanitizer_bitvector_test.cpp
   sanitizer_bvgraph_test.cpp
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
+  sanitizer_env_array_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_format_interceptor_test.cpp
   sanitizer_ioctl_test.cpp
   sanitizer_libc_test.cpp
   sanitizer_linux_test.cpp
   sanitizer_list_test.cpp
   sanitizer_mutable_array_ref_test.cpp
   sanitizer_mutex_test.cpp

compiler-rt/lib/sanitizer_common/tests/sanitizer_env_array_test.cpp

+//===-- sanitizer_env_array_test.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
+//
+//===----------------------------------------------------------------------===//
+//
+// Tests for EnvArray.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_env_array.h"
+
+#include <cstring>
+
+#include "gtest/gtest.h"
+#include "sanitizer_test_utils.h"
+
+using namespace __sanitizer;
+
+static const char kDeathRegex[] = ".*CHECK failed:.*";
+
+const char* kSimpleEnv[] = {"foo=1", "bar=2", "baz=3", nullptr};
+const uptr kSimpleEnvStringStorageSpace = 18;
+
+TEST(EnvArray, kSimpleEnvStringStorageSpaceCorrect) {
+  size_t length = 0;
+  for (unsigned index = 0; index < ARRAY_SIZE(kSimpleEnv); ++index) {
+    if (!kSimpleEnv[index])
+      break;
+    length += strlen(kSimpleEnv[index]) + 1;
+  }
+  EXPECT_EQ(kSimpleEnvStringStorageSpace, length);
+}
+
+char** getSimpleEnv() { return const_cast<char**>(kSimpleEnv); }
+
+template <class T>
+bool isInObject(T* object, uptr addr) {
+  uptr begin_byte = reinterpret_cast<uptr>(object);
+  uptr end_byte = reinterpret_cast<uptr>(object) + sizeof(T) - 1;
+  return addr >= reinterpret_cast<uptr>(begin_byte) &&
+         addr <= reinterpret_cast<uptr>(end_byte);
+}
+
+TEST(EnvArray, Construct) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  EXPECT_EQ(t[0], nullptr);
+}
+
+TEST(EnvArray, StaticStorageSize) {
+  EnvArray<5, 14> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  EXPECT_EQ(t.getStaticEnvStorageSize(), static_cast<uptr>(5));
+  EXPECT_EQ(t.getStaticStringStorageSize(), static_cast<uptr>(14));
+}
+
+TEST(EnvArray, BadIndex) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  EXPECT_DEATH(t[1], kDeathRegex);
+}
+
+TEST(EnvArray, copyFromRawShallowNoHeap) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/true,
+                       /*allow_heap_allocations=*/false, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+
+  // Shallow copy has same pointers
+  EXPECT_EQ(t[0], kSimpleEnv[0]);
+  EXPECT_EQ(t[1], kSimpleEnv[1]);
+  EXPECT_EQ(t[2], kSimpleEnv[2]);
+  EXPECT_EQ(t[3], nullptr);
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[1])));
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[2])));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+}
+
+TEST(EnvArray, copyFromRawEnvDeepCopyNoHeap) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/false,
+                       /*allow_heap_allocations=*/false, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+
+  // Should have different pointers
+  EXPECT_NE(t[0], kSimpleEnv[0]);
+  EXPECT_NE(t[1], kSimpleEnv[1]);
+  EXPECT_NE(t[2], kSimpleEnv[2]);
+
+  EXPECT_STREQ(t[0], kSimpleEnv[0]);
+  EXPECT_STREQ(t[1], kSimpleEnv[1]);
+  EXPECT_STREQ(t[2], kSimpleEnv[2]);
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[1])));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[2])));
+
+  EXPECT_EQ(t[3], nullptr);
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+}
+
+TEST(EnvArray, copyFromRawEnvShallowCopyTruncated) {
+  // Can only hold one environment env entry and no string
+  EnvArray<2, 1> t;
+  EXPECT_EQ(t.getNumAvailableStaticEnvEntries(), static_cast<uptr>(1));
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(), static_cast<uptr>(1));
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/true,
+                       /*allow_heap_allocations=*/false, /*overwrite=*/true);
+
+  // We can only copy across one entry before we run out of static storage.
+  EXPECT_EQ(t.getNumAvailableStaticEnvEntries(), static_cast<uptr>(0));
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(1));
+  EXPECT_EQ(t[0], kSimpleEnv[0]);
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+  EXPECT_EQ(t[1], nullptr);
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+}
+
+TEST(EnvArray, copyFromRawEnvThenResetHeap) {
+  EnvArrayHeapBacked t;
+  EXPECT_EQ(t.getNumAvailableStaticEnvEntries(), static_cast<uptr>(0));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  size_t num_entries_copied = 0;
+
+  for (unsigned count = 0; count < 5; ++count) {
+    num_entries_copied =
+        t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/true,
+                         /*allow_heap_allocations=*/true, /*overwrite=*/true);
+
+    EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+    EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(3));
+
+    EXPECT_STREQ(t.get("foo"), "1");
+    EXPECT_STREQ(t.get("bar"), "2");
+    EXPECT_STREQ(t.get("baz"), "3");
+    EXPECT_TRUE(t.usingHeap());
+
+    t.reset();
+    EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  }
+}
+
+TEST(EnvArray, copyFromRawEnvThenResetNoHeap) {
+  EnvArray<> t;
+  size_t num_entries_copied = 0;
+
+  for (unsigned count = 0; count < 5; ++count) {
+    num_entries_copied =
+        t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/true,
+                         /*allow_heap_allocations=*/false, /*overwrite=*/true);
+
+    EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+    EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(3));
+
+    EXPECT_STREQ(t.get("foo"), "1");
+    EXPECT_STREQ(t.get("bar"), "2");
+    EXPECT_STREQ(t.get("baz"), "3");
+    EXPECT_FALSE(t.usingHeap());
+
+    t.reset();
+    EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  }
+}
+
+TEST(EnvArray, copyFromRawEnvShallowCopyTruncatedNoOverwrite) {
+  // Can only hold one environment env entry.
+  EnvArray<2, 64> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  EXPECT_TRUE(
+      t.set("foo", "0", /*overwrite=*/false, /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/true,
+                       /*allow_heap_allocations=*/false, /*overwrite=*/false);
+
+  // We can only copy across one entry before we run out of static storage.
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(0));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_STREQ(t.get("foo"), "0");
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+}
+
+TEST(EnvArray, copyFromRawEnvDeepCopyUseHeap) {
+  EnvArrayHeapBacked t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/false,
+                       /*allow_heap_allocations=*/true, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+
+  // Should have different pointers
+  EXPECT_NE(t[0], kSimpleEnv[0]);
+  EXPECT_NE(t[1], kSimpleEnv[1]);
+  EXPECT_NE(t[2], kSimpleEnv[2]);
+
+  EXPECT_STREQ(t[0], kSimpleEnv[0]);
+  EXPECT_STREQ(t[1], kSimpleEnv[1]);
+  EXPECT_STREQ(t[2], kSimpleEnv[2]);
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[1])));
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[2])));
+
+  EXPECT_EQ(t[3], nullptr);
+  EXPECT_TRUE(t.usingHeap());
+  EXPECT_TRUE(t.envArrayOnHeap());
+  EXPECT_TRUE(t.stringStorageOnHeap());
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+}
+
+TEST(EnvArray, copyFromRawShallowNoHeapAndGet) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/true,
+                       /*allow_heap_allocations=*/false, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_STREQ(t.get("foo"), "1");
+  EXPECT_STREQ(t.get("bar"), "2");
+  EXPECT_STREQ(t.get("baz"), "3");
+  EXPECT_EQ(t.get("XXX"), nullptr);
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+}
+
+TEST(EnvArray, setNoHeap) {
+  EnvArray<3, 64> t;
+  EXPECT_TRUE(t.set("TEST", "1", /*overwrite=*/false,
+                    /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_STREQ(t.get("TEST"), "1");
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+
+  // Overwrite
+  EXPECT_TRUE(
+      t.set("TEST", "2", /*overwrite=*/true, /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_STREQ(t.get("TEST"), "2");
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+
+  // Don't overwrite
+  EXPECT_FALSE(t.set("TEST", "3", /*overwrite=*/false,
+                     /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_STREQ(t.get("TEST"), "2");
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+}
+
+TEST(EnvArray, setOnHeap) {
+  EnvArrayHeapBacked t;
+  EXPECT_TRUE(
+      t.set("TEST", "1", /*overwrite=*/false, /*allow_heap_allocations=*/true));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_TRUE(t.usingHeap());
+  EXPECT_STREQ(t.get("TEST"), "1");
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+
+  // Overwrite
+  EXPECT_TRUE(
+      t.set("TEST", "2", /*overwrite=*/true, /*allow_heap_allocations=*/true));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_TRUE(t.usingHeap());
+  EXPECT_STREQ(t.get("TEST"), "2");
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+
+  // Don't overwrite
+  EXPECT_FALSE(t.set("TEST", "3", /*overwrite=*/false,
+                     /*allow_heap_allocations=*/true));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_TRUE(t.usingHeap());
+  EXPECT_STREQ(t.get("TEST"), "2");
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+}
+
+TEST(EnvArray, setNoHeapReuseEntry) {
+  const char kTestEnvEntry[] = "TEST=1";
+  const size_t kTestEnvSize = sizeof(kTestEnvEntry);
+  // Deliberately allocate stack space that is only just enough for a single
+  // entry the size of `kTestEnvEntry`.
+  EnvArray<2, kTestEnvSize> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+
+  // Do first set. This should succeed with only using stack storage.
+  EXPECT_TRUE(
+      t.set("TEST", "1", /*overwrite=*/true, /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  const char* first_entry_str = t.get("TEST");
+  EXPECT_STREQ(first_entry_str, "1");
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+
+  // Do second set. `t` only has enough stack storage space for the `TEST=1`
+  // string. So this will fail unless `EnvArray` knows to re-use the existing
+  // entry.
+  EXPECT_TRUE(
+      t.set("TEST", "2", /*overwrite=*/true, /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_EQ(t.get("TEST"), first_entry_str);
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_STREQ(t.get("TEST"), "2");
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+
+  // Check further insertion fails.
+  EXPECT_FALSE(t.set("TEST", "23", /*overwrite=*/true,
+                     /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+}
+
+TEST(EnvArray, heapEntryMigration) {
+  const char kTestEnvEntry[] = "TEST=1";
+  const size_t kTestEnvSize = sizeof(kTestEnvEntry);
+  // Deliberately allocate stack space that is only just enough for a single
+  // entry the size of `kTestEnvEntry`.
+  EnvArray<2, kTestEnvSize> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+
+  // Do first set. This should succeed with only using stack storage.
+  EXPECT_TRUE(
+      t.set("TEST", "1", /*overwrite=*/true, /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  const char* first_entry_str = t.get("TEST");
+  EXPECT_STREQ(first_entry_str, "1");
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+
+  // Now do another insert. This should trigger a migration to heap storage
+  EXPECT_TRUE(t.set("ANOTHER_ENV", "2", /*overwrite=*/true,
+                    /*allow_heap_allocations=*/true));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(2));
+
+  // The env array storage should no longer be in the EnvArray object.
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t.getStorage().data())));
+  // The string for the first entry should not have been migrated though.
+  EXPECT_STREQ(t[0], kTestEnvEntry);
+  EXPECT_TRUE(isInObject(&t, reinterpret_cast<uptr>(t[0])));
+  EXPECT_STREQ(t.get("TEST"), "1");
+  // The string for the second entry should be on the heap because there isn't
+  // enough stack storage for it.
+  EXPECT_STREQ(t[1], "ANOTHER_ENV=2");
+  EXPECT_STREQ(t.get("ANOTHER_ENV"), "2");
+  EXPECT_FALSE(isInObject(&t, reinterpret_cast<uptr>(t[1])));
+}
+
+TEST(EnvArray, copyFromRawEnvWithExistingEntries) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+
+  // Add an entry
+  EXPECT_TRUE(
+      t.set("bar", "abc", /*overwrite=*/true, /*allow_heap_allocations=*/true));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_STREQ(t[0], "bar=abc");
+  EXPECT_STREQ(t.get("bar"), "abc");
+
+  // Now copy other entries. One of these entries is already in `t`.
+  // It should get overwritten.
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/true,
+                       /*allow_heap_allocations=*/true, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+  EXPECT_STREQ(t.get("foo"), "1");
+  EXPECT_STREQ(t.get("bar"), "2");
+  EXPECT_STREQ(t.get("baz"), "3");
+}
+
+TEST(EnvArray, copyFromRawEnvWithExistingEntriesNoOverwrite) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+
+  // Add an entry
+  EXPECT_TRUE(
+      t.set("bar", "abc", /*overwrite=*/true, /*allow_heap_allocations=*/true));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_STREQ(t[0], "bar=abc");
+  EXPECT_STREQ(t.get("bar"), "abc");
+
+  // Now copy other entries. One of these entries is already in `t`.
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/true,
+                       /*allow_heap_allocations=*/true, /*overwrite=*/false);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(2));
+  EXPECT_STREQ(t.get("foo"), "1");
+  EXPECT_STREQ(t.get("bar"), "abc");
+  EXPECT_STREQ(t.get("baz"), "3");
+}
+
+TEST(EnvArray, copyFromRawDeepNoHeapReuseEntry) {
+  // Only has enough static storage space for what's in kSimpleEnv.
+  EnvArray<ARRAY_SIZE(kSimpleEnv), kSimpleEnvStringStorageSpace> t;
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(),
+            static_cast<uptr>(kSimpleEnvStringStorageSpace));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+
+  EXPECT_TRUE(
+      t.set("foo", "X", /*overwrite=*/false, /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_STREQ(t.get("foo"), "X");
+
+  // Now copy other entries. One of these entries is already in `t`.
+  // It should get overwritten. In order for this work without heap allocations
+  // `EnvArray` needs to realise it can reuse the storage space for the `foo=X`
+  // entry which is being overwriten.
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/false,
+                       /*allow_heap_allocations=*/false, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(3));
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(), static_cast<uptr>(0));
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_STREQ(t.get("foo"), "1");
+  EXPECT_STREQ(t.get("bar"), "2");
+  EXPECT_STREQ(t.get("baz"), "3");
+}
+
+TEST(EnvArray, RemoveEntryAtBadIndex) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/false,
+                       /*allow_heap_allocations=*/true, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+  EXPECT_DEATH(t.removeEntryAt(4), kDeathRegex);
+}
+
+TEST(EnvArray, RemoveEntryAtIndex) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/false,
+                       /*allow_heap_allocations=*/true, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(3));
+
+  EXPECT_STREQ(t[0], "foo=1");
+  EXPECT_STREQ(t[1], "bar=2");
+  EXPECT_STREQ(t[2], "baz=3");
+  EXPECT_EQ(t[3], nullptr);
+
+  // Remove at beginning of array.
+  t.removeEntryAt(0);
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(2));
+  EXPECT_STREQ(t[0], "bar=2");
+  EXPECT_STREQ(t[1], "baz=3");
+  EXPECT_EQ(t[2], nullptr);
+
+  // Remove at end of array
+  t.removeEntryAt(1);
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_STREQ(t[0], "bar=2");
+  EXPECT_EQ(t[1], nullptr);
+
+  // Remove remaining item.
+  t.removeEntryAt(0);
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  EXPECT_EQ(t[0], nullptr);
+}
+
+TEST(EnvArray, Unset) {
+  EnvArray<> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/false,
+                       /*allow_heap_allocations=*/true, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(3));
+
+  // unsetting a non existent entry should fail.
+  EXPECT_EQ(t.get("__not_present"), nullptr);
+  EXPECT_FALSE(t.unset("__not_present"));
+
+  // Remove `baz`
+  EXPECT_TRUE(t.unset("baz"));
+  EXPECT_STREQ(t.get("foo"), "1");
+  EXPECT_STREQ(t.get("bar"), "2");
+  EXPECT_EQ(t.get("baz"), nullptr);
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(2));
+
+  // Remove `foo`
+  EXPECT_TRUE(t.unset("foo"));
+  EXPECT_STREQ(t.get("bar"), "2");
+  EXPECT_EQ(t.get("foo"), nullptr);
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+
+  // Remove `bar`
+  EXPECT_TRUE(t.unset("bar"));
+  EXPECT_EQ(t.get("bar"), nullptr);
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+}
+
+TEST(EnvArray, staticStringStorageFree) {
+  // Only has enough static storage space for what's in kSimpleEnv.
+  EnvArray<ARRAY_SIZE(kSimpleEnv), kSimpleEnvStringStorageSpace> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+
+  // Now copy other entries. One of these entries is already in `t`.
+  // It should get overwritten. In order for this work without heap allocations
+  // `EnvArray` needs to realise it can reuse the storage space for the `foo=X`
+  // entry which is being overwriten.
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/false,
+                       /*allow_heap_allocations=*/false, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(3));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(3));
+  EXPECT_FALSE(t.usingHeap());
+  EXPECT_STREQ(t.get("foo"), "1");
+  EXPECT_STREQ(t.get("bar"), "2");
+  EXPECT_STREQ(t.get("baz"), "3");
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(), static_cast<uptr>(0));
+
+  // Unset and set entry in a loop. This will only use static storage. This
+  // should work if "bump-pointer" like behaviour of the static string storage
+  // frees correctly. If it doesn't free as expected then we'll exhaust the
+  // static storage and this test will fail.
+  EXPECT_STREQ(t[2], "baz=3");
+  for (unsigned index = 0; index < 100; ++index) {
+    EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(3));
+    EXPECT_FALSE(t.usingHeap());
+
+    EXPECT_TRUE(t.unset("baz"));
+    EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(2));
+    EXPECT_STREQ(t.get("foo"), "1");
+    EXPECT_STREQ(t.get("bar"), "2");
+
+    EXPECT_TRUE(t.set("baz", "4", /*overwrite=*/false,
+                      /*allow_heap_allocations=*/false));
+    EXPECT_STREQ(t.get("baz"), "4");
+  }
+}
+
+TEST(EnvArray, NoLeakAllocEntryOnInsertionFail) {
+  const char* key_one = "foo";
+  const char* key_two = "bar";
+  const size_t string_storage_size = 6;
+  // +1 for `=`, +1 for `1`, +1 for `\0`.
+  const size_t string_storage_size_computed = strlen(key_one) + 3;
+  ASSERT_EQ(string_storage_size, string_storage_size_computed);
+  ASSERT_EQ(strlen(key_one), strlen(key_two));
+
+  // Only enough space for a single entry but double the string storage.
+  EnvArray<2, 2 * string_storage_size> t;
+  EXPECT_EQ(t.getNumAvailableStaticEnvEntries(), static_cast<uptr>(1));
+  EXPECT_TRUE(t.set(key_one, "1", /*overwrite=*/false,
+                    /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_EQ(t.getNumAvailableStaticEnvEntries(), static_cast<uptr>(0));
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(),
+            static_cast<uptr>(string_storage_size));
+
+  // Now attempt another insertion this should fail **but** we shouldn't leak
+  // any static storage space when the insertion fails.
+  EXPECT_FALSE(t.set(key_two, "1", /*overwrite=*/false,
+                     /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(1));
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(),
+            static_cast<uptr>(string_storage_size));
+
+  EXPECT_TRUE(t.unset(key_one));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(),
+            static_cast<uptr>(string_storage_size * 2));
+  EXPECT_TRUE(t.set(key_two, "1", /*overwrite=*/false,
+                    /*allow_heap_allocations=*/false));
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(),
+            static_cast<uptr>(string_storage_size));
+}
+
+TEST(EnvArray, copyFromNoLeakFailedEntryAlloc) {
+  // One less slot than needed to complete copy
+  EnvArray<ARRAY_SIZE(kSimpleEnv) - 1, kSimpleEnvStringStorageSpace> t;
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(0));
+
+  size_t num_entries_copied =
+      t.copyFromRawEnv(getSimpleEnv(), /*shallow_copy=*/false,
+                       /*allow_heap_allocations=*/false, /*overwrite=*/true);
+  EXPECT_EQ(num_entries_copied, static_cast<uptr>(2));
+  EXPECT_EQ(t.getNumEnvEntries(), static_cast<uptr>(2));
+  EXPECT_FALSE(t.usingHeap());
+
+  // Expected storage size is correct provided the implementation didn't leak.
+  // `+2` is for `\0` in `t[0]` and `t[1]`.
+  uptr expected_storage_size =
+      t.getStaticStringStorageSize() - (strlen(t[0]) + strlen(t[1]) + 2);
+  EXPECT_EQ(t.getAvailableStaticStringStorageSize(), expected_storage_size);
+}