前の項目はデータ構造が少し難しめだったので、この項目では STL コンテナをフル活用してコードを読みやすくすることと、バッファーオーバーフロー時にエラーを投げるのではなく、ヒープへのフォールバックを実装してみたいと思います。
ヒープフォールバック付きのスタックアロケーターの実装はヒープをすこしばかり改造するというアプローチで良いかと思います。
まず最大の違いはヒープのように delete は不要なところです。
それとスタックにはすでにメモリー領域が固定長ではありますが確保されてるので new も不要です。
しかし使用できるアドレスの範囲内にオブジェクトを作るためにプレースメント new を使うことになります。
ではコードを見てみましょう。
main.cpp.
1 #include <memory>
2 #include <vector>
3 #include <iostream>
4 #include <cassert>
5 #include <cstddef>
6 #include <map>
7
8 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
9 class stack_allocator
10 {
11 public:
12 typedef typename std::allocator_traits<Allocator>::value_type value_type;
13 typedef typename std::allocator_traits<Allocator>::pointer pointer;
14 typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
15 typedef typename std::allocator_traits<Allocator>::size_type size_type;
16 typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
17 typedef typename std::allocator_traits<Allocator>::void_pointer void_pointer;
18 typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
19 typedef typename Allocator::reference reference;
20 typedef typename Allocator::const_reference const_reference;
21
22 typedef std::map<void*,size_t> size_map_t;
23 typedef std::map<size_t,std::vector<void*>> free_list_t;
24 typedef std::byte byte;
25
26 typedef Allocator allocator_type;
27
28 explicit stack_allocator(const allocator_type& alloc = allocator_type())
29 : M_allocator_(alloc),
30 M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
31 M_max_objects_(N),
32 M_begin_(M_buffer_),
33 M_end_(M_buffer_+M_block_size_*M_max_objects_),
34 M_stack_pointer_(M_buffer_)
35 {}
36
37 template<typename U>
38 stack_allocator(const stack_allocator<U,N,Allocator>& other)
39 : M_allocator_(other.M_allocator_),
40 M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
41 M_max_objects_(N),
42 M_begin_(other.M_begin_),
43 M_end_(other.M_end_),
44 M_stack_pointer_(other.M_stack_pointer_)
45 {}
46
47 template<typename U>
48 struct rebind
49 {
50 typedef stack_allocator<U,N,allocator_type> other;
51 };
52
53 pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
54 {
55 auto& free_chunks = M_free_list_[n*M_block_size_];
56 if(!free_chunks.empty()){
57 pointer available_block = static_cast<T*>(free_chunks.back());
58 free_chunks.pop_back();
59 std::cout << "reuse pointer: " << available_block << '\n';
60 return available_block;
61 } else if(M_stack_pointer_ + n * M_block_size_ > M_end_){
62 std::printf("over the stack capacity, fall back to default allocator\n");
63 M_stack_pointer_ += n * M_block_size_;
64 return M_allocator_.allocate(n);
65 }
66
67 pointer new_block = reinterpret_cast<pointer>(M_stack_pointer_);
68 M_stack_pointer_ += n*M_block_size_;
69 M_size_map_[new_block] = n*M_block_size_;
70 std::cout << "new pointer: " << new_block << " M_stack_pointer_: " << M_stack_pointer_ << '\n';
71 return new_block;
72 }
73
74 void deallocate(pointer p, size_type n)
75 {
76 auto freed_chunk_size = M_size_map_[(void*)p];
77 if(freed_chunk_size != 0){ // value should be initialized to zero if the map is empty
78 M_free_list_[freed_chunk_size].push_back((void*)p);
79 } else if(M_stack_pointer_ > M_end_){
80 M_allocator_.deallocate(p,n);
81 freed_chunk_size = n * M_block_size_;
82 }
83 std::printf("deallocate: %p with size %lu\n",p,freed_chunk_size);
84 }
85
86 size_type max_size() const noexcept
87 {
88 return (size_type)(~0) / sizeof(T);
89 }
90
91 template<typename U, typename... Args>
92 void construct(U* p, Args&&... args)
93 {
94 ::new ((void*)p) T(args...);
95 }
96
97 template<typename U>
98 void destroy(U* p)
99 {
100 p->~T();
101 }
102
103 pointer address(reference x) const noexcept
104 {
105 return std::addressof(x);
106 }
107
108 const_pointer address(const_reference x) const noexcept
109 {
110 return addressof(x);
111 }
112
113 pointer buffer() const noexcept
114 {
115 return M_begin_;
116 }
117
118 constexpr static size_type capacity()
119 {
120 return N;
121 }
122
123 private:
124
125 allocator_type M_allocator_;
126 size_map_t M_size_map_;
127 free_list_t M_free_list_;
128
129 byte M_buffer_[N];
130 const size_type M_block_size_;
131 const size_type M_max_objects_;
132 byte* M_begin_;
133 byte* M_end_;
134 byte* M_stack_pointer_;
135 };
136
137 template<typename T1, std::size_t N, typename Allocator, typename T2>
138 bool operator==(const stack_allocator<T1,N,Allocator>& lhs, const stack_allocator<T2,N,Allocator>& rhs) noexcept
139 {
140 return lhs.buffer() == rhs.buffer();
141 }
142
143 template<typename T1, std::size_t N, typename Allocator, typename T2>
144 bool operator!=(const stack_allocator<T1,N,Allocator>& lhs, const stack_allocator<T2,N,Allocator>& rhs) noexcept
145 {
146 return !(lhs == rhs);
147 }
148
149 const std::size_t stack_size = 8;
150
151 int main()
152 {
153 typedef stack_allocator<int,stack_size> alloc_t;
154
155 alloc_t alloc;
156 int* t = alloc.allocate(1);
157 alloc.construct(t,100);
158 std::cout << *t << '\n';
159 alloc.destroy(t);
160 alloc.deallocate(t,1);
161
162 int* d[16];
163 for(int i = 0; i < 5; ++i){
164 d[i] = alloc.allocate(1);
165 }
166 for(int i = 1; i < 5; ++i){
167 alloc.deallocate(d[i],1);
168 }
169 for(int i = 5; i < 16; ++i){
170 d[i] = alloc.allocate(1);
171 }
172 for(int i = 5; i < 16; ++i){
173 alloc.deallocate(d[i],1);
174 }
175 }
このソースコードをビルドして実行すると以下のような出力となります。
$ g++ main.cpp -std=c++17 -g $ ./a.out new pointer: 0x7ffe83fa1e08 M_stack_pointer_: 0x7ffe83fa1e10 100 deallocate: 0x7ffe83fa1e08 with size 8 reuse pointer: 0x7ffe83fa1e08 new pointer: 0x7ffe83fa1e10 M_stack_pointer_: 0x7ffe83fa1e18 new pointer: 0x7ffe83fa1e18 M_stack_pointer_: 0x7ffe83fa1e20 new pointer: 0x7ffe83fa1e20 M_stack_pointer_: 0x7ffe83fa1e28 new pointer: 0x7ffe83fa1e28 M_stack_pointer_: 0x7ffe83fa1e30 deallocate: 0x7ffe83fa1e10 with size 8 deallocate: 0x7ffe83fa1e18 with size 8 deallocate: 0x7ffe83fa1e20 with size 8 deallocate: 0x7ffe83fa1e28 with size 8 reuse pointer: 0x7ffe83fa1e28 reuse pointer: 0x7ffe83fa1e20 reuse pointer: 0x7ffe83fa1e18 reuse pointer: 0x7ffe83fa1e10 new pointer: 0x7ffe83fa1e30 M_stack_pointer_: 0x7ffe83fa1e38 new pointer: 0x7ffe83fa1e38 M_stack_pointer_: 0x7ffe83fa1e40 new pointer: 0x7ffe83fa1e40 M_stack_pointer_: 0x7ffe83fa1e48 over the stack capacity, fall back to default allocator over the stack capacity, fall back to default allocator over the stack capacity, fall back to default allocator over the stack capacity, fall back to default allocator deallocate: 0x7ffe83fa1e28 with size 8 deallocate: 0x7ffe83fa1e20 with size 8 deallocate: 0x7ffe83fa1e18 with size 8 deallocate: 0x7ffe83fa1e10 with size 8 deallocate: 0x7ffe83fa1e30 with size 8 deallocate: 0x7ffe83fa1e38 with size 8 deallocate: 0x7ffe83fa1e40 with size 8 deallocate: 0x55f7af9cf430 with size 8 deallocate: 0x55f7af9cf310 with size 8 deallocate: 0x55f7af9cf540 with size 8 deallocate: 0x55f7af9cf560 with size 8
このコードでは allocate() / deallocate() を使うケースと std::vector を使うケースの 2 パターンをテストしています。
まずはコンストラクターです。
8 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
9 class stack_allocator
10 {
11 public:
// 中略
22 typedef std::map<void*,size_t> size_map_t;
23 typedef std::map<size_t,std::vector<void*>> free_list_t;
24 typedef std::byte byte;
// 中略
28 explicit stack_allocator(const allocator_type& alloc = allocator_type())
29 : M_allocator_(alloc),
30 M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
31 M_max_objects_(N),
32 M_begin_(M_buffer_),
33 M_end_(M_buffer_+M_block_size_*M_max_objects_),
34 M_stack_pointer_(M_buffer_)
35 {}
36
37 template<typename U>
38 stack_allocator(const stack_allocator<U,N,Allocator>& other)
39 : M_allocator_(other.M_allocator_),
40 M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
41 M_max_objects_(N),
42 M_begin_(other.M_begin_),
43 M_end_(other.M_end_),
44 M_stack_pointer_(other.M_stack_pointer_)
45 {}
// 中略
123 private:
124
125 allocator_type M_allocator_;
126 size_map_t M_size_map_;
127 free_list_t M_free_list_;
128
129 byte M_buffer_[N];
130 const size_type M_block_size_;
131 const size_type M_max_objects_;
132 byte* M_begin_;
133 byte* M_end_;
134 byte* M_stack_pointer_;
135 };コピーコンストラクターが std::allocator のインスタンスを M_allocator_ にデフォルトでコピーしてます。
M_allocator_ はこのソースコードでフォールバックとして使用しているので無視してもらっても結構ですが、デフォルトアロケーターとして持っておくと便利です。
フォールバック用のデフォルトアロケーターがあると便利なのは、スタックアロケーターでは一定限度以上の割り当てが必要な場合はヒープ領域に割り当てる実装が一般的だからです。
テンプレートパラメーター N はバッファーのバイトサイズを定義するために使われます。
つまり M_buffer_[] 配列は N バイトの記憶域となります。
M_block_size_ はこのアロケーターが割り当てる固定サイズです。
M_begin_ と M_end_ は開始と終端のアドレスです。
M_stack_pointer_ はスタックポインター、つまり現在使用中の最新の位置ってことで、これを割り当て時に加算し、開放時に減算します。
アロケーターのメモリー管理機能は 2 つの型によって行います。
22 typedef std::map<void*,size_t> size_map_t; 23 typedef std::map<size_t,std::vector<void*>> free_list_t;
オブジェクト定義のほうは以下の 2 行です。
126 size_map_t M_size_map_; 127 free_list_t M_free_list_;
M_size_map_ はポインターから、割り当てられたバイトサイズを探すためのマップデータ構造です。
M_free_list_ は割り当てバイトサイズから、フリーリストの std::vector データ構造を探すためのマップです。
この 2 つはメモリー再利用の機能を実装するには不可欠となるのですが、考え方としてはメモリーの
まあ複雑なので実装をみたほうが早いかもしれないです。
次に allocate() 関数を見てみましょう。
53 pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
54 {
55 auto& free_chunks = M_free_list_[n*M_block_size_];
56 if(!free_chunks.empty()){
57 pointer available_block = static_cast<T*>(free_chunks.back());
58 free_chunks.pop_back();
59 std::cout << "reuse pointer: " << available_block << '\n';
60 return available_block;
61 } else if(M_stack_pointer_ + n * M_block_size_ > M_end_){
62 std::printf("over the stack capacity, fall back to default allocator\n");
63 M_stack_pointer_ += n * M_block_size_;
64 return M_allocator_.allocate(n);
65 }
66
67 pointer new_block = reinterpret_cast<pointer>(M_stack_pointer_);
68 M_stack_pointer_ += n*M_block_size_;
69 M_size_map_[new_block] = n*M_block_size_;
70 std::cout << "new pointer: " << new_block << " M_stack_pointer_: " << M_stack_pointer_ << '\n';
71 return new_block;
72 }スタックポインターのアドレスを new_block に代入し返しますが、その直前に M_stack_pointer_ のアドレスを n * M_block_size_ 分だけ加算して、次の割り当てに使うアドレスを取得しておきます。
67 pointer new_block = reinterpret_cast<pointer>(M_stack_pointer_); 68 M_stack_pointer_ += n*M_block_size_; 69 M_size_map_[new_block] = n*M_block_size_;
それと終端アドレス超えた場合のセーフガードとしてデフォルトアロケーター( std::allocator )がコールされるようしています。
61 } else if(M_stack_pointer_ + n * M_block_size_ > M_end_){
62 std::printf("over the stack capacity, fall back to default allocator\n");
63 M_stack_pointer_ += n * M_block_size_;
64 return M_allocator_.allocate(n);
65 }後は解放されてフリーな状態のチャンク・ブロックを再利用するロジックです。
55 auto& free_chunks = M_free_list_[n*M_block_size_];
56 if(!free_chunks.empty()){
57 pointer available_block = static_cast<T*>(free_chunks.back());
58 free_chunks.pop_back();
59 std::cout << "reuse pointer: " << available_block << '\n';
60 return available_block;ここでは、リクエストサイズのフリーチャンクが M_free_list_ に存在するかチェックしています。
55 auto& free_chunks = M_free_list_[n*M_block_size_];
56 if(!free_chunks.empty()){もし empty() が真を返すならば再利用できるフリーチャンクは存在せず、偽を返すならば再利用できるフリーチャンク・フリーブロックが存在するということです。
もしフリーチャンクがあるなら、後はそれを返すだけですが、取り出しあとにポップしておきます。
57 pointer available_block = static_cast<T*>(free_chunks.back()); 58 free_chunks.pop_back();
次に deallocate() を見てみましょう。
74 void deallocate(pointer p, size_type n)
75 {
76 auto freed_chunk_size = M_size_map_[(void*)p];
77 if(freed_chunk_size != 0){ // value should be initialized to zero if the map is empty
78 M_free_list_[freed_chunk_size].push_back((void*)p);
79 } else if(M_stack_pointer_ > M_end_){
80 M_allocator_.deallocate(p,n);
81 freed_chunk_size = n * M_block_size_;
82 }
83 std::printf("deallocate: %p with size %lu\n",p,freed_chunk_size);
84 }アロケーターではスタックポインターにブロックサイズを加算した状態なので、アロケーターのオーバーフローのチェックは以下の行で行います。
79 } else if(M_stack_pointer_ > M_end_){
80 M_allocator_.deallocate(p,n);
81 freed_chunk_size = n * M_block_size_;
82 }このようにデフォルトアロケーター M_allocator_ の deallocate() 関数をコールするだけです。
次にスタック領域内のチャンクについてです。
スタック領域のチャンクは M_size_map_ に登録されています。もとは allocate() 関数で追加されています。
M_size_map_ から p ポインターを照合する場合、返ってきた値が 0 ならデータが存在しないということになります。
76 auto freed_chunk_size = M_size_map_[(void*)p];
77 if(freed_chunk_size != 0){ // value should be initialized to zero if the map is empty
78 M_free_list_[freed_chunk_size].push_back((void*)p);該当するポインターが存在する場合はフリーチャンクとしてフリーリストに登録を行います。
それとテストのほうもみておきましょうかね。
まずスタックのサイズは 8 としておきますが、これは 8 バイトではなく、ブロックサイズのことです。
149 const std::size_t stack_size = 8;
150
151 int main()
152 {
153 typedef stack_allocator<int,stack_size> alloc_t;
154
155 alloc_t alloc;
156 int* t = alloc.allocate(1);
157 alloc.construct(t,100);
158 std::cout << *t << '\n';
159 alloc.destroy(t);
160 alloc.deallocate(t,1);
161
162 int* d[16];
163 for(int i = 0; i < 5; ++i){
164 d[i] = alloc.allocate(1);
165 }
166 for(int i = 1; i < 5; ++i){
167 alloc.deallocate(d[i],1);
168 }
169 for(int i = 5; i < 16; ++i){
170 d[i] = alloc.allocate(1);
171 }
172 for(int i = 5; i < 16; ++i){
173 alloc.deallocate(d[i],1);
174 }最初は int 型を指す領域を 1 個だけ割り当て、すぎに解放しておきます。
155 alloc_t alloc; 156 int* t = alloc.allocate(1); 157 alloc.construct(t,100); 158 std::cout << *t << '\n'; 159 alloc.destroy(t); 160 alloc.deallocate(t,1);
一応 construct() でオブジェクトを初期化し destroy() で破壊もしておいています。
次に解放したポインター再利用のロジックの実装が動作するかチェックしますね。
やってる事は i が 0,1,2,3,4 （合計 5 個）の時に allocate() 関数を呼びます。
reuse pointer: 0x7ffe83fa1e08 new pointer: 0x7ffe83fa1e10 M_stack_pointer_: 0x7ffe83fa1e18 new pointer: 0x7ffe83fa1e18 M_stack_pointer_: 0x7ffe83fa1e20 new pointer: 0x7ffe83fa1e20 M_stack_pointer_: 0x7ffe83fa1e28 new pointer: 0x7ffe83fa1e28 M_stack_pointer_: 0x7ffe83fa1e30
さらに i が 1,2,3,4 （合計 4 個）の時に deallocate() 関数をコールします。
deallocate: 0x7ffe83fa1e10 with size 8 deallocate: 0x7ffe83fa1e18 with size 8 deallocate: 0x7ffe83fa1e20 with size 8 deallocate: 0x7ffe83fa1e28 with size 8
そして i が 5,6,7,8,9,10,11,12,13,14,15 （合計 11 個）の時に allocate() 関数と呼びます。
reuse pointer: 0x7ffe83fa1e28 reuse pointer: 0x7ffe83fa1e20 reuse pointer: 0x7ffe83fa1e18 reuse pointer: 0x7ffe83fa1e10 new pointer: 0x7ffe83fa1e30 M_stack_pointer_: 0x7ffe83fa1e38 new pointer: 0x7ffe83fa1e38 M_stack_pointer_: 0x7ffe83fa1e40 new pointer: 0x7ffe83fa1e40 M_stack_pointer_: 0x7ffe83fa1e48 over the stack capacity, fall back to default allocator over the stack capacity, fall back to default allocator over the stack capacity, fall back to default allocator over the stack capacity, fall back to default allocator
この際に前もって deallocate() でフリーチャンクが 4 個分 M_free_list_ に登録されているので、その分を再利用します。
すると 7 個分までがスタック領域に割り当てられ、残りの 4 個分がヒープ領域に割り当てられます。
最後に最初に作った分と合わせ合計 12 個分のポインターに対して deallocate() 関数をコールします。
deallocate: 0x7ffe83fa1e28 with size 8 deallocate: 0x7ffe83fa1e20 with size 8 deallocate: 0x7ffe83fa1e18 with size 8 deallocate: 0x7ffe83fa1e10 with size 8 deallocate: 0x7ffe83fa1e30 with size 8 deallocate: 0x7ffe83fa1e38 with size 8 deallocate: 0x7ffe83fa1e40 with size 8 deallocate: 0x55f7af9cf430 with size 8 deallocate: 0x55f7af9cf310 with size 8 deallocate: 0x55f7af9cf540 with size 8 deallocate: 0x55f7af9cf560 with size 8
スタック領域のポインターらしきものが 8 個、ヒープ領域のポインターらしきものが 4 個解放されています。
Copyright 2018-2019, by Masaki Komatsu