23#include <l4/cxx/arith>
24#include <l4/cxx/minmax>
34 friend class List_alloc_sanity_guard;
44 inline void check_overlap(
void *,
unsigned long );
45 inline void sanity_check_list(
char const *,
char const *);
70 inline void free(
void *block,
unsigned long size,
bool initial_free =
false);
82 inline void *
alloc(
unsigned long size,
unsigned long align);
100 unsigned long align,
unsigned granularity);
107 inline unsigned long avail();
109 template <
typename DBG>
110 void dump_free_list(DBG &out);
113#if !defined (CXX_LIST_ALLOC_SANITY)
114class List_alloc_sanity_guard
117 List_alloc_sanity_guard(List_alloc *,
char const *)
124List_alloc::check_overlap(
void *,
unsigned long )
128List_alloc::sanity_check_list(
char const *,
char const *)
133class List_alloc_sanity_guard
140 List_alloc_sanity_guard(List_alloc *a,
char const *func)
142 { a->sanity_check_list(func,
"entry"); }
144 ~List_alloc_sanity_guard()
145 { a->sanity_check_list(func,
"exit"); }
149List_alloc::check_overlap(
void *b,
unsigned long s)
151 unsigned long const mb_align = (1UL << arith::Ld<
sizeof(Mem_block)>::value) - 1;
152 if ((
unsigned long)b & mb_align)
154 L4::cerr <<
"List_alloc(FATAL): trying to free unaligned memory: "
155 << b <<
" align=" << arith::Ld<
sizeof(Mem_block)>::value <<
"\n";
158 Mem_block *c = _first;
159 for (;c ; c = c->next)
161 unsigned long x_s = (
unsigned long)b;
162 unsigned long x_e = x_s + s;
163 unsigned long b_s = (
unsigned long)c;
164 unsigned long b_e = b_s + c->size;
166 if ((x_s >= b_s && x_s < b_e)
167 || (x_e > b_s && x_e <= b_e)
168 || (b_s >= x_s && b_s < x_e)
169 || (b_e > x_s && b_e <= x_e))
171 L4::cerr <<
"List_alloc(FATAL): trying to free memory that "
172 "is already free: \n ["
173 << (
void*)x_s <<
'-' << (
void*)x_e <<
") overlaps ["
174 << (
void*)b_s <<
'-' << (
void*)b_e <<
")\n";
180List_alloc::sanity_check_list(
char const *func,
char const *info)
182 Mem_block *c = _first;
183 for (;c ; c = c->next)
189 L4::cerr <<
"List_alloc(FATAL): " << func <<
'(' << info
190 <<
"): list order violation\n";
193 if (((
unsigned long)c) + c->size > (
unsigned long)c->next)
195 L4::cerr <<
"List_alloc(FATAL): " << func <<
'(' << info
196 <<
"): list order violation\n";
207 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __func__);
208 Mem_block *c = _first;
211 unsigned long f_start = (
unsigned long)c;
212 unsigned long f_end = f_start + c->size;
213 unsigned long n_start = (
unsigned long)c->next;
215 if (f_end == n_start)
217 c->size += c->next->size;
218 c->next = c->next->next;
229 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __func__);
231 unsigned long const mb_align = (1UL << arith::Ld<
sizeof(Mem_block)>::value) - 1;
236 unsigned long nblock = ((
unsigned long)block + mb_align) & ~mb_align;
237 size = (size - (nblock - (
unsigned long)block)) & ~mb_align;
238 block = (
void*)nblock;
242 size = (size + mb_align) & ~mb_align;
244 check_overlap(block, size);
246 Mem_block **c = &_first;
251 while (*c && *c < block)
257 *c = (Mem_block*)block;
267 unsigned granularity)
269 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __func__);
271 unsigned char const mb_bits = arith::Ld<
sizeof(Mem_block)>::value;
272 unsigned long const mb_align = (1UL << mb_bits) - 1;
279 *
max = *
max & ~(granularity - 1UL);
284 unsigned long almask = align ? (align - 1UL) : 0;
287 if (almask < mb_align)
290 Mem_block **c = &_first;
292 unsigned long max_fit = 0;
294 for (; *c; c = &(*c)->next)
297 unsigned long n_start = (
unsigned long)(*c);
301 if ((*c)->size <
min)
305 unsigned long a_start = (n_start + almask) & ~almask;
308 if (a_start - n_start >= (*c)->size)
312 unsigned long r_size = (*c)->size - a_start + n_start;
314 r_size &= ~(granularity - 1UL);
327 if (r_size > max_fit)
336 unsigned long n_start = (
unsigned long)(*fit);
337 unsigned long a_start = (n_start + almask) & ~almask;
338 unsigned long r_size = (*fit)->size - a_start + n_start;
340 if (a_start > n_start)
342 (*fit)->size -= r_size;
349 if (r_size == max_fit)
350 return (
void *)a_start;
352 Mem_block *m = (Mem_block*)(a_start + max_fit);
354 m->size = r_size - max_fit;
356 return (
void *)a_start;
365 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __func__);
367 unsigned long const mb_align = (1UL << arith::Ld<
sizeof(Mem_block)>::value) - 1;
370 size = (size + mb_align) & ~mb_align;
372 unsigned long almask = align ? (align - 1UL) : 0;
375 if (almask < mb_align)
378 Mem_block **c = &_first;
380 for (; *c; c=&(*c)->next)
383 unsigned long n_start = (
unsigned long)(*c);
387 if ((*c)->size < size)
391 unsigned long a_start = (n_start + almask) & ~almask;
394 if (a_start - n_start >= (*c)->size)
399 unsigned long r_size = (*c)->size - a_start + n_start;
405 if (a_start > n_start)
410 (*c)->size -= r_size;
420 return (
void*)a_start;
423 Mem_block *m = (Mem_block*)(a_start + size);
425 m->size = r_size - size;
427 return (
void *)a_start;
436 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __FUNCTION__);
437 Mem_block *c = _first;
448template <
typename DBG>
450List_alloc::dump_free_list(DBG &out)
452 Mem_block *c = _first;
463 else if (c->size < 1 << 20)
474 out.printf(
"%12p - %12p (%u %s)\n", c, (
char *) c + c->size - 1, sz, unit);
Standard list-based allocator.
unsigned long avail()
Get the amount of available memory.
void * alloc(unsigned long size, unsigned long align)
Allocate a memory block.
List_alloc()
Initializes an empty list allocator.
void * alloc_max(unsigned long min, unsigned long *max, unsigned long align, unsigned granularity)
Allocate a memory block of min <= size <= max.
void free(void *block, unsigned long size, bool initial_free=false)
Return a free memory block to the allocator.
T1 min(T1 a, T1 b)
Get the minimum of a and b.
T1 max(T1 a, T1 b)
Get the maximum of a and b.
l4_addr_t l4_trunc_size(l4_addr_t address, unsigned char bits) L4_NOTHROW
Round an address down to the next lower flex page with size bits.
l4_addr_t l4_round_size(l4_addr_t value, unsigned char bits) L4_NOTHROW
Round value up to the next alignment with bits size.
BasicOStream cerr
Standard error stream.