1 /*
2 * Copyright (C) 2015 Kernkonzept GmbH.
3 * Author(s): Sarah Hoffmann <sarah.hoffmann@kernkonzept.com>
4 *
5 * This file is distributed under the terms of the GNU General Public
6 * License, version 2. Please see the COPYING-GPL-2 file for details.
7 */
8 #include <cstring>
9 #include <cstdio>
10 #include <cassert>
11
12 #include <l4/cxx/slist>
13 #include <l4/cxx/minmax>
14
15 #include "debug.h"
16 #include "malloc.h"
17 #include "page_alloc.h"
18
19 static Dbg info(Dbg::Info);
20
21 namespace Moe {
22
23 /**
24 * A page with allocatable memory.
25 *
26 * Simple one-size-fits-all bin based implementation.
27 */
28 class Malloc_page : public cxx::S_list_item
29 {
30 public:
31 enum
32 {
33 Page_shift = L4_PAGESHIFT,
34 Page_size = 1 << Page_shift,
35 Inval_idx = 0xFF
36 };
37
Malloc_page(Moe::Malloc_container * container,size_t binshift)38 Malloc_page(Moe::Malloc_container *container, size_t binshift)
39 : _container(container), _bin_shift(binshift), _first_free(0), _used(0)
40 {
41 // include bin size and the one free bit in the computation
42 _num_bins = (Page_size - sizeof(Malloc_page)) / (1 << binshift);
43 auto *c = static_cast<unsigned char *>(ptr_of(0));
44
45 // initialise freelist
46 for (unsigned char i = 1; i < _num_bins; ++i, c -= (1 << binshift))
47 *c = i;
48 *c = Inval_idx;
49 }
50
container() const51 Moe::Malloc_container *container() const
52 { return _container; }
53
reparent(Moe::Malloc_container * c)54 void reparent(Moe::Malloc_container *c)
55 { _container = c; }
56
alloc(size_t shift)57 void *alloc(size_t shift) throw()
58 {
59 if (shift != _bin_shift || _used >= _num_bins)
60 return 0;
61
62 void *freeptr = ptr_of(_first_free);
63
64 _first_free = *static_cast<unsigned char *>(freeptr);
65 ++_used;
66
67 return freeptr;
68 }
69
free(void * block)70 void free(void *block) throw()
71 {
72 assert(block >= start_data() && block < end_data());
73
74 unsigned char freeidx = index_of(block);
75
76 *static_cast<unsigned char *>(ptr_of(freeidx)) = _first_free;
77 _first_free = freeidx;
78 --_used;
79 }
80
unused() const81 bool unused() const
82 { return _used == 0; }
83
from_ptr(void const * p)84 static Malloc_page *from_ptr(void const *p) throw()
85 {
86 l4_addr_t caddr = l4_trunc_size(l4_addr_t(p), Malloc_page::Page_shift);
87 return reinterpret_cast<Malloc_page *>(caddr);
88 }
89
90 private:
ptr_of(long idx) const91 void *ptr_of(long idx) const
92 { return end_data() - ((idx + 1) << _bin_shift); }
93
index_of(void * ptr) const94 long index_of(void *ptr) const
95 { return ((Page_size - l4_addr_t(ptr) + l4_addr_t(this)) >> _bin_shift) - 1; }
96
start_data() const97 char *start_data() const
98 { return end_data() - _num_bins * (1 << _bin_shift); }
99
end_data() const100 char *end_data() const
101 { return reinterpret_cast<char *>(l4_addr_t(this) + Page_size); }
102
103 Moe::Malloc_container *_container;
104 unsigned char _bin_shift;
105 unsigned char _num_bins;
106 unsigned char _first_free;
107 unsigned char _used;
108 };
109
110 }
111
112 void *
alloc(size_t size,size_t align)113 Moe::Malloc_container::alloc(size_t size, size_t align) throw()
114 {
115 if (0)
116 printf("Malloc[%p]: alloc(%zu, %zu)\n", this, size, align);
117 // make sure alignment will be ok
118 size = cxx::max(size, align);
119 // now find the next possible 2^n alignment
120 size_t outsz = 4;
121 while ((1UL << outsz) < size)
122 {
123 ++outsz;
124 if (outsz > 10)
125 return 0;
126 }
127
128 for (auto const pg : _pages)
129 {
130 void *p = pg->alloc(outsz);
131 if (p)
132 return p;
133 }
134
135 // nothing? try to allocate a new page
136 void *np = get_mem();
137
138 if (np)
139 {
140 if (0)
141 printf("Malloc[%p]: create new backing page @ %p (sz=%zu)\n",
142 this, np, outsz);
143 Malloc_page *pg = new (np) Malloc_page(this, outsz);
144 _pages.add(pg);
145 void *p = pg->alloc(outsz);
146 return p;
147 }
148
149 return 0;
150 }
151
152 void
free(void * block)153 Moe::Malloc_container::free(void *block) throw()
154 {
155 if (0)
156 printf("Malloc[%p]: free(%p)\n", this, block);
157
158 auto *pg = Malloc_page::from_ptr(block);
159
160 if (pg->container() != this)
161 {
162 info.printf("WARNING: free called on wrong allocator.\n");
163 return;
164 }
165
166 pg->free(block);
167
168 if (pg->unused())
169 {
170 for (auto it = _pages.begin(); it != _pages.end(); ++it)
171 {
172 if (*it == pg)
173 {
174 _pages.erase(it);
175 free_mem(pg);
176 return;
177 }
178 }
179 }
180 }
181
182 void *
get_mem()183 Moe::Malloc_container::get_mem()
184 {
185 return Single_page_alloc_base::_alloc(Single_page_alloc_base::nothrow,
186 Malloc_page::Page_size,
187 Malloc_page::Page_size);
188 }
189
190 void
free_mem(void * page)191 Moe::Malloc_container::free_mem(void *page)
192 {
193 Single_page_alloc_base::_free(page, Malloc_page::Page_size);
194 }
195
196 void
reparent(Malloc_container * new_container)197 Moe::Malloc_container::reparent(Malloc_container *new_container)
198 {
199 while (!_pages.empty())
200 {
201 auto *front = _pages.pop_front();
202 front->reparent(new_container);
203 new_container->_pages.add(front);
204 }
205 }
206
207 Moe::Malloc_container *
from_ptr(void const * p)208 Moe::Malloc_container::from_ptr(void const *p) throw()
209 {
210 return Malloc_page::from_ptr(p)->container();
211 }
212