1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19
20/*!
21 *
22 * \file arena.h
23 * \brief Arena allocator that allocates
24 * memory chunks and frees them all during destruction time.
25 */
26#ifndef TVM_SUPPORT_ARENA_H_
27#define TVM_SUPPORT_ARENA_H_
28
29#include <cstddef>
30#include <type_traits>
31#include <utility>
32
33#include "generic_arena.h"
34
35namespace tvm {
36namespace support {
37
38/*!
39 * \brief Simple page allocator that uses new and delete.
40 */
41class SimplePageAllocator {
42 public:
43 /*!
44 * \brief Allocate a new page.
45 * \param min_size Minimum size of the page.
46 * \return The allocated page.
47 * \note This function can return a bigger page to meet the min_size requirement.
48 */
49 ArenaPageHeader* allocate(size_t min_size) {
50 size_t npages = ((min_size + kPageSize - 1) / kPageSize);
51 ArenaPageHeader* header = reinterpret_cast<ArenaPageHeader*>(new Page[npages]);
52 header->size = npages * kPageSize;
53 header->offset = sizeof(ArenaPageHeader);
54 return header;
55 }
56 /*!
57 * \brief De-allocate an allocate page.
58 * \param page The page to be de-allocated.
59 */
60 void deallocate(ArenaPageHeader* page) { delete[] reinterpret_cast<Page*>(page); }
61
62 static const constexpr int kPageSize = 16 << 10;
63 static const constexpr int kPageAlign = 1024;
64
65 private:
66 // page size 16 KB
67 // The page data type;
68 using Page = std::aligned_storage<kPageSize, kPageAlign>::type;
69};
70
71using Arena = GenericArena<SimplePageAllocator>;
72
73/*!
74 * \brief Link list node
75 * \tparam T the content data type
76 */
77template <typename T>
78struct LinkNode {
79 /*! \brief The content value */
80 T value;
81 /*! \brief pointer to the next location */
82 LinkNode<T>* next{nullptr};
83};
84/*!
85 * \brief LinkedList structure
86 * \tparam T the content data type
87 * \note This is a simple data structure that can be used together with the arena.
88 * \sa LinkNode
89 */
90template <typename T>
91struct LinkedList {
92 /*! \brief Head pointer */
93 LinkNode<T>* head{nullptr};
94 /*! \brief Tail pointer */
95 LinkNode<T>* tail{nullptr};
96 /*!
97 * \brief Push a new node to the end of the linked list.
98 * \param node The node to be pushed.
99 */
100 void Push(LinkNode<T>* node) {
101 node->next = nullptr;
102 if (this->tail != nullptr) {
103 this->tail->next = node;
104 this->tail = node;
105 } else {
106 head = tail = node;
107 }
108 }
109};
110
111} // namespace support
112} // namespace tvm
113#endif // TVM_SUPPORT_ARENA_H_
114