1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
// Copyright 2022 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_OBJECTS_STRING_FORWARDING_TABLE_H_
#define V8_OBJECTS_STRING_FORWARDING_TABLE_H_
#include "src/objects/string.h"
// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"
namespace v8 {
namespace internal {
// Mapping from forwarding indices (stored in a string's hash field) to
// internalized strings/external resources.
// The table is used to handle string transitions (temporarily until the next
// full GC, during which actual string transitions happen) that overwrite the
// string buffer. In particular these are Internalization and Externalization.
// The table is organised in "blocks". As writes only append new entries, the
// organisation in blocks allows lock-free writes. We need a lock only for
// growing the table (adding more blocks). When the vector holding the blocks
// needs to grow, we keep a copy of the old vector alive to allow concurrent
// reads while the vector is relocated.
class StringForwardingTable {
public:
// Capacity for the first block.
static constexpr int kInitialBlockSize = 16;
static_assert(base::bits::IsPowerOfTwo(kInitialBlockSize));
static constexpr int kInitialBlockSizeHighestBit =
kBitsPerInt - base::bits::CountLeadingZeros32(kInitialBlockSize) - 1;
// Initial capacity in the block vector.
static constexpr int kInitialBlockVectorCapacity = 4;
static constexpr Smi unused_element() { return Smi::FromInt(0); }
static constexpr Smi deleted_element() { return Smi::FromInt(1); }
explicit StringForwardingTable(Isolate* isolate);
~StringForwardingTable();
inline int size() const;
inline bool empty() const;
// Returns the index of the added record.
int AddForwardString(String string, String forward_to);
template <typename T>
EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
int AddExternalResourceAndHash(String string, T* resource, uint32_t raw_hash);
void UpdateForwardString(int index, String forward_to);
// Returns true when the resource was set. When an external resource is
// already set for the record, false is returned and the resource not stored.
// The caller is responsible for disposing the resource.
template <typename T>
EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
bool TryUpdateExternalResource(int index, T* resource);
String GetForwardString(PtrComprCageBase cage_base, int index) const;
static Address GetForwardStringAddress(Isolate* isolate, int index);
V8_EXPORT_PRIVATE uint32_t GetRawHash(PtrComprCageBase cage_base,
int index) const;
static uint32_t GetRawHashStatic(Isolate* isolate, int index);
v8::String::ExternalStringResourceBase* GetExternalResource(
int index, bool* is_one_byte) const;
template <typename Func>
V8_INLINE void IterateElements(Func&& callback);
// Dispose all external resources stored in the table.
void TearDown();
void Reset();
void UpdateAfterEvacuation();
class Record;
private:
class Block;
class BlockVector;
// Returns the block for a given index and sets the index within this block
// as out parameter.
static inline uint32_t BlockForIndex(int index, uint32_t* index_in_block_out);
static inline uint32_t IndexInBlock(int index, uint32_t block);
static inline uint32_t CapacityForBlock(uint32_t block);
void InitializeBlockVector();
// Ensure that |block| exists in the BlockVector already. If not, a new block
// is created (with capacity double the capacity of the last block) and
// inserted into the BlockVector. The BlockVector itself might grow (to double
// the capacity).
BlockVector* EnsureCapacity(uint32_t block);
Isolate* isolate_;
std::atomic<BlockVector*> blocks_;
// We need a vector of BlockVectors to keep old BlockVectors alive when we
// grow the table, due to concurrent reads that may still hold a pointer to
// them. |block_vector_sotrage_| is only accessed while we grow with the mutex
// held. All regular access go through |block_|, which holds a pointer to the
// current BlockVector.
std::vector<std::unique_ptr<BlockVector>> block_vector_storage_;
std::atomic<int> next_free_index_;
base::Mutex grow_mutex_;
};
} // namespace internal
} // namespace v8
#include "src/objects/object-macros-undef.h"
#endif // V8_OBJECTS_STRING_FORWARDING_TABLE_H_
|
