Apollo 10.0
自动驾驶开放平台
apollo::cyber::transport::ArenaAddressAllocator类 参考

#include <arena_address_allocator.h>

apollo::cyber::transport::ArenaAddressAllocator 的协作图:

Public 成员函数

 ArenaAddressAllocator ()
 
 ~ArenaAddressAllocator ()
 
bool Init (uint64_t capacity, void *base_address, uint64_t address_segment_size)
 
bool OpenOrCreate (uint64_t key, uint64_t size, void *base_address, void **shm_address, bool *is_created)
 
bool Open (uint64_t key, void *base_address, void **shm_address)
 
bool OpenOrCreate (uint64_t capacity, void *base_address, uint64_t address_segment_size)
 
bool OpenMetaShm (uint64_t capacity, void *base_address, uint64_t address_segment_size)
 
bool OpenNodeShm (uint64_t capacity, void *base_address, uint64_t address_segment_size)
 
ArenaAddressNodeNewNode (uint64_t key)
 
void ReclaimNode (ArenaAddressNode *node)
 
ArenaAddressNodeFindNode (ArenaAddressNode *node, uint64_t key)
 
ArenaAddressNodeFindOrInsertNode (ArenaAddressNode *node, ArenaAddressNode **node_p, ArenaAddressNode *parent, uint64_t key)
 
void RemoveNode (ArenaAddressNode *node, ArenaAddressNode **node_addr, uint64_t key)
 
void SwapNodePosition (ArenaAddressNode *x, ArenaAddressNode **x_p, ArenaAddressNode *y, ArenaAddressNode **y_p)
 
uint64_t TreeHeight (ArenaAddressNode *node)
 
ArenaAddressNodeTreeMax (ArenaAddressNode *node, ArenaAddressNode ***node_pp)
 
ArenaAddressNodeTreeMin (ArenaAddressNode *node, ArenaAddressNode ***node_pp)
 
int64_t TreeBalanceFactor (ArenaAddressNode *node)
 
ArenaAddressNodeTreeRebalance (ArenaAddressNode *node, ArenaAddressNode **node_p)
 
ArenaAddressNodeTreeRotateLeft (ArenaAddressNode *node, ArenaAddressNode **node_p)
 
ArenaAddressNodeTreeRotateRight (ArenaAddressNode *node, ArenaAddressNode **node_p)
 
ArenaAddressNodeTreeRotateLeftRight (ArenaAddressNode *node, ArenaAddressNode **node_p)
 
ArenaAddressNodeTreeRotateRightLeft (ArenaAddressNode *node, ArenaAddressNode **node_p)
 
void * Allocate (uint64_t key)
 
void Deallocate (uint64_t key)
 

详细描述

在文件 arena_address_allocator.h55 行定义.

构造及析构函数说明

◆ ArenaAddressAllocator()

apollo::cyber::transport::ArenaAddressAllocator::ArenaAddressAllocator ( )

在文件 arena_address_allocator.cc30 行定义.

31 : meta_shm_key_(
32 std::hash<std::string>{}("/apollo/__arena__/__address__/__meta__")),
33 node_shm_key_(
34 std::hash<std::string>{}("/apollo/__arena__/__address__/__node__")),
35 meta_(nullptr),
36 nodes_(nullptr),
37 reclaim_stack_(nullptr) {
38 // TODO(all): configurable and address management for shared memory of cyber
39 meta_shm_address_ = nullptr;
40 // use fixed address
41 node_shm_address_ = reinterpret_cast<void*>(0x7f0000000000);
42
43 // ensure the allocator's segment size is larger
44 // than the actual arena's segment size
45 // otherwise the shmat will fail
46 Init(1024, reinterpret_cast<void*>(
47 0x710000000000), 2ULL * 1024 * 1024 * 1024);
48}
bool Init(uint64_t capacity, void *base_address, uint64_t address_segment_size)

◆ ~ArenaAddressAllocator()

apollo::cyber::transport::ArenaAddressAllocator::~ArenaAddressAllocator ( )

在文件 arena_address_allocator.cc50 行定义.

50 {
51 if (meta_ && meta_->struct_.ref_count_.fetch_sub(1) == 0) {
52 shmdt(meta_);
53 shmctl(shmget(meta_shm_key_, 0, 0), IPC_RMID, nullptr);
54 shmdt(nodes_);
55 shmctl(shmget(node_shm_key_, 0, 0), IPC_RMID, nullptr);
56 }
57}
struct apollo::cyber::transport::ArenaAddressAllocatorMeta::@2 struct_

成员函数说明

◆ Allocate()

void * apollo::cyber::transport::ArenaAddressAllocator::Allocate ( uint64_t  key)

在文件 arena_address_allocator.cc413 行定义.

413 {
414 bool idle_status = false;
415 bool occupied_status = true;
416 while (!meta_->struct_.occupied_.compare_exchange_strong(
417 idle_status, occupied_status)) {
418 // exchange failed, idle_status is set to true.
419 idle_status = false;
420 std::this_thread::sleep_for(std::chrono::microseconds(1000));
421 }
422 auto node = FindOrInsertNode(meta_->struct_.root_, &(meta_->struct_.root_),
423 nullptr, key);
424 meta_->struct_.occupied_.store(false);
425 if (node == nullptr) {
426 return nullptr;
427 }
428
429 node->ref_count_.fetch_add(1);
430
431 return reinterpret_cast<void*>(
432 reinterpret_cast<uint64_t>(meta_->struct_.base_address_) +
433 meta_->struct_.address_segment_size_ * node->index_);
434}
ArenaAddressNode * FindOrInsertNode(ArenaAddressNode *node, ArenaAddressNode **node_p, ArenaAddressNode *parent, uint64_t key)

◆ Deallocate()

void apollo::cyber::transport::ArenaAddressAllocator::Deallocate ( uint64_t  key)

在文件 arena_address_allocator.cc436 行定义.

436 {
437 bool idle_status = false;
438 bool occupied_status = true;
439 while (!meta_->struct_.occupied_.compare_exchange_strong(
440 idle_status, occupied_status)) {
441 // exchange failed, idle_status is set to true.
442 idle_status = false;
443 std::this_thread::sleep_for(std::chrono::microseconds(1000));
444 }
445 auto node = FindNode(meta_->struct_.root_, key);
446 meta_->struct_.occupied_.store(false);
447 if (node == nullptr) {
448 return;
449 }
450
451 if (node->ref_count_.fetch_sub(1) == 0) {
452 RemoveNode(meta_->struct_.root_, &(meta_->struct_.root_), key);
453 }
454}
ArenaAddressNode * FindNode(ArenaAddressNode *node, uint64_t key)
void RemoveNode(ArenaAddressNode *node, ArenaAddressNode **node_addr, uint64_t key)

◆ FindNode()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::FindNode ( ArenaAddressNode node,
uint64_t  key 
)

在文件 arena_address_allocator.cc191 行定义.

192 {
193 if (node == nullptr) {
194 return nullptr;
195 }
196 if (key < node->key_) {
197 return FindNode(node->left_, key);
198 } else if (key > node->key_) {
199 return FindNode(node->right_, key);
200 }
201 return node;
202}

◆ FindOrInsertNode()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::FindOrInsertNode ( ArenaAddressNode node,
ArenaAddressNode **  node_p,
ArenaAddressNode parent,
uint64_t  key 
)

在文件 arena_address_allocator.cc204 行定义.

206 {
207 if (node == nullptr) {
208 auto target = NewNode(key);
209 *node_p = target;
210 target->parent_ = parent;
211 return target;
212 }
213 if (key < node->key_) {
214 auto target = FindOrInsertNode(node->left_, &(node->left_), node, key);
215 TreeRebalance(node->left_, &(node->left_));
216 return target;
217 } else if (key > node->key_) {
218 auto target = FindOrInsertNode(node->right_, &(node->right_), node, key);
219 TreeRebalance(node->right_, &(node->right_));
220 return target;
221 }
222 // key == node->key_
223 return node;
224}
ArenaAddressNode * TreeRebalance(ArenaAddressNode *node, ArenaAddressNode **node_p)

◆ Init()

bool apollo::cyber::transport::ArenaAddressAllocator::Init ( uint64_t  capacity,
void *  base_address,
uint64_t  address_segment_size 
)

在文件 arena_address_allocator.cc59 行定义.

60 {
61 if (!OpenMetaShm(capacity, base_address, address_segment_size)) {
62 return false;
63 }
64 if (!OpenNodeShm(capacity, base_address, address_segment_size)) {
65 return false;
66 }
67 meta_->struct_.occupied_.store(false);
68 return true;
69}
bool OpenMetaShm(uint64_t capacity, void *base_address, uint64_t address_segment_size)
bool OpenNodeShm(uint64_t capacity, void *base_address, uint64_t address_segment_size)

◆ NewNode()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::NewNode ( uint64_t  key)

在文件 arena_address_allocator.cc164 行定义.

164 {
165 if (meta_->struct_.reclaim_stack_top_ > 0) {
166 uint64_t index = reclaim_stack_[--meta_->struct_.reclaim_stack_top_];
167 nodes_[index].left_ = nullptr;
168 nodes_[index].right_ = nullptr;
169 nodes_[index].key_ = key;
170 return &nodes_[index];
171 }
172 if (meta_->struct_.allocated_index_ >= meta_->struct_.capacity_) {
173 // TODO(all): expand nodes
174 return nullptr;
175 }
176 nodes_[meta_->struct_.allocated_index_].left_ = nullptr;
177 nodes_[meta_->struct_.allocated_index_].right_ = nullptr;
178 nodes_[meta_->struct_.allocated_index_].key_ = key;
179 nodes_[meta_->struct_.allocated_index_].index_ =
181 return &nodes_[meta_->struct_.allocated_index_++];
182}

◆ Open()

bool apollo::cyber::transport::ArenaAddressAllocator::Open ( uint64_t  key,
void *  base_address,
void **  shm_address 
)

在文件 arena_address_allocator.cc71 行定义.

72 {
73 auto shmid = shmget(static_cast<key_t>(key), 0, 0);
74
75 shmid = shmget(static_cast<key_t>(key), 0, 0);
76 if (shmid == -1) {
77 // open failed
78 return false;
79 }
80 *shm_address = shmat(shmid, base_address, 0);
81 if (*shm_address == reinterpret_cast<void*>(-1)) {
82 // shmat failed
83 return false;
84 }
85 return true;
86}

◆ OpenMetaShm()

bool apollo::cyber::transport::ArenaAddressAllocator::OpenMetaShm ( uint64_t  capacity,
void *  base_address,
uint64_t  address_segment_size 
)

在文件 arena_address_allocator.cc113 行定义.

114 {
115 bool is_created = false;
116 bool ret = false;
117 for (uint32_t retry = 0; retry < 2 && !ret;
118 ++retry, ret = OpenOrCreate(
119 meta_shm_key_, sizeof(ArenaAddressAllocatorMeta),
120 meta_shm_address_, reinterpret_cast<void**>(&meta_),
121 &is_created)) {
122 }
123 if (!ret) {
124 // create or open failed
125 return false;
126 }
127 if (!is_created) {
128 meta_->struct_.ref_count_.fetch_add(1);
129 } else {
130 meta_->struct_.version_ = 1;
131 meta_->struct_.capacity_ = capacity;
132 meta_->struct_.base_address_ = base_address;
133 meta_->struct_.address_segment_size_ = address_segment_size;
134 meta_->struct_.root_ = nullptr;
135 meta_->struct_.allocated_index_ = 0;
136 meta_->struct_.reclaim_stack_top_ = 0;
137 meta_->struct_.ref_count_.store(1);
138 }
139 return true;
140}
bool OpenOrCreate(uint64_t key, uint64_t size, void *base_address, void **shm_address, bool *is_created)

◆ OpenNodeShm()

bool apollo::cyber::transport::ArenaAddressAllocator::OpenNodeShm ( uint64_t  capacity,
void *  base_address,
uint64_t  address_segment_size 
)

在文件 arena_address_allocator.cc142 行定义.

143 {
144 uint64_t size = sizeof(ArenaAddressAllocatorMeta) +
145 sizeof(ArenaAddressNode) * (capacity + 1) +
146 sizeof(uint64_t) * capacity;
147 bool is_created = false;
148 bool ret = false;
149 for (uint32_t retry = 0; retry < 2 && !ret;
150 ++retry, ret = OpenOrCreate(node_shm_key_, size, node_shm_address_,
151 reinterpret_cast<void**>(&nodes_),
152 &is_created)) {
153 }
154 if (!ret) {
155 // create or open failed
156 return false;
157 }
158
159 reclaim_stack_ = reinterpret_cast<uint64_t*>(
160 reinterpret_cast<uint64_t>(nodes_) + sizeof(ArenaAddressNode) * capacity);
161 return true;
162}

◆ OpenOrCreate() [1/2]

bool apollo::cyber::transport::ArenaAddressAllocator::OpenOrCreate ( uint64_t  capacity,
void *  base_address,
uint64_t  address_segment_size 
)

◆ OpenOrCreate() [2/2]

bool apollo::cyber::transport::ArenaAddressAllocator::OpenOrCreate ( uint64_t  key,
uint64_t  size,
void *  base_address,
void **  shm_address,
bool *  is_created 
)

在文件 arena_address_allocator.cc88 行定义.

90 {
91 auto shmid =
92 shmget(static_cast<key_t>(key), size, 0644 | IPC_CREAT | IPC_EXCL);
93
94 if (shmid == -1) {
95 if (errno == EINVAL) {
96 // TODO(all): recreate larger shm
97 } else if (errno == EEXIST) {
98 *is_created = false;
99 return Open(key, base_address, shm_address);
100 } else {
101 return false;
102 }
103 }
104 *shm_address = shmat(shmid, base_address, 0);
105 if (*shm_address == reinterpret_cast<void*>(-1)) {
106 // shmat failed
107 return false;
108 }
109 *is_created = true;
110 return true;
111}
bool Open(uint64_t key, void *base_address, void **shm_address)

◆ ReclaimNode()

void apollo::cyber::transport::ArenaAddressAllocator::ReclaimNode ( ArenaAddressNode node)

在文件 arena_address_allocator.cc184 行定义.

184 {
185 nodes_[node->index_].left_ = nullptr;
186 nodes_[node->index_].right_ = nullptr;
187 nodes_[node->index_].parent_ = nullptr;
188 reclaim_stack_[meta_->struct_.reclaim_stack_top_++] = node->index_;
189}

◆ RemoveNode()

void apollo::cyber::transport::ArenaAddressAllocator::RemoveNode ( ArenaAddressNode node,
ArenaAddressNode **  node_addr,
uint64_t  key 
)

在文件 arena_address_allocator.cc226 行定义.

228 {
229 if (!node) {
230 return;
231 }
232 if (!FindNode(node, key)) {
233 return;
234 }
235 if (key < node->key_) {
236 RemoveNode(node->left_, &(node->left_), key);
237 if (TreeBalanceFactor(node) < -1) {
238 TreeRebalance(meta_->struct_.root_, &(meta_->struct_.root_));
239 }
240 return;
241 } else if (key > node->key_) {
242 RemoveNode(node->right_, &(node->right_), key);
243 if (TreeBalanceFactor(node) > 1) {
244 TreeRebalance(meta_->struct_.root_, &(meta_->struct_.root_));
245 }
246 return;
247 }
248 // node->key_ == key
249 // left and right both exist
250 if (node->left_ && node->right_) {
251 if (TreeBalanceFactor(node) > 0) {
252 auto max_p = &(node->left_);
253 auto max = TreeMax(node->left_, &max_p);
254 SwapNodePosition(node, node_p, max, max_p);
255 RemoveNode(max->left_, &(max->left_), key);
256 return;
257 } else {
258 auto min_p = &(node->right_);
259 auto min = TreeMin(node->right_, &min_p);
260 SwapNodePosition(node, node_p, min, min_p);
261 RemoveNode(min->right_, &(min->right_), key);
262 return;
263 }
264 }
265 // left or right exist
266 *node_p = node->left_ ? node->left_ : node->right_;
267 ReclaimNode(node);
268}
ArenaAddressNode * TreeMax(ArenaAddressNode *node, ArenaAddressNode ***node_pp)
void SwapNodePosition(ArenaAddressNode *x, ArenaAddressNode **x_p, ArenaAddressNode *y, ArenaAddressNode **y_p)
ArenaAddressNode * TreeMin(ArenaAddressNode *node, ArenaAddressNode ***node_pp)

◆ SwapNodePosition()

void apollo::cyber::transport::ArenaAddressAllocator::SwapNodePosition ( ArenaAddressNode x,
ArenaAddressNode **  x_p,
ArenaAddressNode y,
ArenaAddressNode **  y_p 
)

在文件 arena_address_allocator.cc270 行定义.

273 {
274 if (x == nullptr || y == nullptr) {
275 // cannot swap nullptr
276 return;
277 }
278
279 // swap address
280 *x_p = y;
281 *y_p = x;
282 // swap parent
283 auto parent_x = x->parent_;
284 auto parent_y = y->parent_;
285 x->parent_ = parent_y;
286 y->parent_ = parent_x;
287
288 ArenaAddressNode* tmp = nullptr;
289
290 // swap left
291 tmp = x->left_;
292 x->left_ = y->left_;
293 if (x->left_) {
294 x->left_->parent_ = x;
295 }
296 y->left_ = tmp;
297 if (y->left_) {
298 y->left_->parent_ = y;
299 }
300
301 // swap right
302 tmp = x->right_;
303 x->right_ = y->right_;
304 if (x->right_) {
305 x->right_->parent_ = x;
306 }
307 y->right_ = tmp;
308 if (y->right_) {
309 y->right_->parent_ = y;
310 }
311}

◆ TreeBalanceFactor()

int64_t apollo::cyber::transport::ArenaAddressAllocator::TreeBalanceFactor ( ArenaAddressNode node)

在文件 arena_address_allocator.cc344 行定义.

344 {
345 if (node == nullptr) {
346 return 0;
347 }
348 return TreeHeight(node->left_) - TreeHeight(node->right_);
349}

◆ TreeHeight()

uint64_t apollo::cyber::transport::ArenaAddressAllocator::TreeHeight ( ArenaAddressNode node)

在文件 arena_address_allocator.cc313 行定义.

313 {
314 if (node == nullptr) {
315 return 0;
316 }
317 return 1 + std::max(TreeHeight(node->left_), TreeHeight(node->right_));
318}

◆ TreeMax()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::TreeMax ( ArenaAddressNode node,
ArenaAddressNode ***  node_pp 
)

在文件 arena_address_allocator.cc320 行定义.

321 {
322 if (node == nullptr) {
323 return nullptr;
324 }
325 for (; node->right_;) {
326 *node_pp = &(node->right_);
327 node = node->right_;
328 }
329 return node;
330}

◆ TreeMin()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::TreeMin ( ArenaAddressNode node,
ArenaAddressNode ***  node_pp 
)

在文件 arena_address_allocator.cc332 行定义.

333 {
334 if (node == nullptr) {
335 return nullptr;
336 }
337 for (; node->left_;) {
338 *node_pp = &(node->left_);
339 node = node->left_;
340 }
341 return node;
342}

◆ TreeRebalance()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::TreeRebalance ( ArenaAddressNode node,
ArenaAddressNode **  node_p 
)

在文件 arena_address_allocator.cc391 行定义.

392 {
393 if (node == nullptr) {
394 return nullptr;
395 }
396 auto balance_factor = TreeBalanceFactor(node);
397 if (balance_factor > 1) {
398 if (TreeBalanceFactor(node->left_) > 0) {
399 return TreeRotateRight(node, node_p);
400 } else {
401 return TreeRotateLeftRight(node, node_p);
402 }
403 } else if (balance_factor < -1) {
404 if (TreeBalanceFactor(node->right_) < 0) {
405 return TreeRotateLeft(node, node_p);
406 } else {
407 return TreeRotateRightLeft(node, node_p);
408 }
409 }
410 return node;
411}
ArenaAddressNode * TreeRotateLeftRight(ArenaAddressNode *node, ArenaAddressNode **node_p)
ArenaAddressNode * TreeRotateLeft(ArenaAddressNode *node, ArenaAddressNode **node_p)
ArenaAddressNode * TreeRotateRightLeft(ArenaAddressNode *node, ArenaAddressNode **node_p)
ArenaAddressNode * TreeRotateRight(ArenaAddressNode *node, ArenaAddressNode **node_p)

◆ TreeRotateLeft()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::TreeRotateLeft ( ArenaAddressNode node,
ArenaAddressNode **  node_p 
)

在文件 arena_address_allocator.cc351 行定义.

352 {
353 auto parent = node->parent_;
354 auto right = node->right_;
355
356 node->right_ = right->left_;
357 right->left_ = node;
358 node->parent_ = right;
359 *node_p = right;
360 right->parent_ = parent;
361
362 return right;
363}

◆ TreeRotateLeftRight()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::TreeRotateLeftRight ( ArenaAddressNode node,
ArenaAddressNode **  node_p 
)

在文件 arena_address_allocator.cc379 行定义.

380 {
381 TreeRotateLeft(node->left_, &(node->left_));
382 return TreeRotateRight(node, node_p);
383}

◆ TreeRotateRight()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::TreeRotateRight ( ArenaAddressNode node,
ArenaAddressNode **  node_p 
)

在文件 arena_address_allocator.cc365 行定义.

366 {
367 auto parent = node->parent_;
368 auto left = node->left_;
369
370 node->left_ = left->right_;
371 left->right_ = node;
372 node->parent_ = left;
373 *node_p = left;
374 left->parent_ = parent;
375
376 return left;
377}

◆ TreeRotateRightLeft()

ArenaAddressNode * apollo::cyber::transport::ArenaAddressAllocator::TreeRotateRightLeft ( ArenaAddressNode node,
ArenaAddressNode **  node_p 
)

在文件 arena_address_allocator.cc385 行定义.

386 {
387 TreeRotateRight(node->right_, &(node->right_));
388 return TreeRotateLeft(node, node_p);
389}

该类的文档由以下文件生成: