23#include <l4/cxx/arith>
24#include <l4/cxx/minmax>
25#include <l4/sys/consts.h>
35 friend class List_alloc_sanity_guard;
45 inline void check_overlap(
void *,
unsigned long );
46 inline void sanity_check_list(
char const *,
char const *);
71 inline void free(
void *block,
unsigned long size,
bool initial_free =
false);
87 inline void *
alloc(
unsigned long size,
unsigned long align,
88 unsigned long lower = 0,
unsigned long upper = ~0UL);
110 inline void *
alloc_max(
unsigned long min,
unsigned long *max,
111 unsigned long align,
unsigned granularity,
112 unsigned long lower = 0,
unsigned long upper = ~0UL);
119 inline unsigned long avail();
121 template <
typename DBG>
122 void dump_free_list(DBG &out);
125#if !defined (CXX_LIST_ALLOC_SANITY)
126class List_alloc_sanity_guard
129 List_alloc_sanity_guard(List_alloc *,
char const *)
136List_alloc::check_overlap(
void *,
unsigned long )
140List_alloc::sanity_check_list(
char const *,
char const *)
145class List_alloc_sanity_guard
152 List_alloc_sanity_guard(List_alloc *a,
char const *func)
154 { a->sanity_check_list(func,
"entry"); }
156 ~List_alloc_sanity_guard()
157 { a->sanity_check_list(func,
"exit"); }
161List_alloc::check_overlap(
void *b,
unsigned long s)
163 unsigned long const mb_align = (1UL << arith::Ld<
sizeof(Mem_block)>::value) - 1;
164 if ((
unsigned long)b & mb_align)
166 L4::cerr <<
"List_alloc(FATAL): trying to free unaligned memory: "
167 << b <<
" align=" << arith::Ld<
sizeof(Mem_block)>::value <<
"\n";
170 Mem_block *c = _first;
171 for (;c ; c = c->next)
173 unsigned long x_s = (
unsigned long)b;
174 unsigned long x_e = x_s + s;
175 unsigned long b_s = (
unsigned long)c;
176 unsigned long b_e = b_s + c->size;
178 if ((x_s >= b_s && x_s < b_e)
179 || (x_e > b_s && x_e <= b_e)
180 || (b_s >= x_s && b_s < x_e)
181 || (b_e > x_s && b_e <= x_e))
183 L4::cerr <<
"List_alloc(FATAL): trying to free memory that "
184 "is already free: \n ["
185 << (
void*)x_s <<
'-' << (
void*)x_e <<
") overlaps ["
186 << (
void*)b_s <<
'-' << (
void*)b_e <<
")\n";
192List_alloc::sanity_check_list(
char const *func,
char const *info)
194 Mem_block *c = _first;
195 for (;c ; c = c->next)
201 L4::cerr <<
"List_alloc(FATAL): " << func <<
'(' << info
202 <<
"): list order violation\n";
205 if (((
unsigned long)c) + c->size > (
unsigned long)c->next)
207 L4::cerr <<
"List_alloc(FATAL): " << func <<
'(' << info
208 <<
"): list order violation\n";
219 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __func__);
220 Mem_block *c = _first;
223 unsigned long f_start =
reinterpret_cast<unsigned long>(c);
224 unsigned long f_end = f_start + c->size;
225 unsigned long n_start =
reinterpret_cast<unsigned long>(c->next);
227 if (f_end == n_start)
229 c->size += c->next->size;
230 c->next = c->next->next;
241 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __func__);
243 unsigned long const mb_align = (1UL << arith::Ld<
sizeof(Mem_block)>::value) - 1;
248 unsigned long nblock = (
reinterpret_cast<unsigned long>(block) + mb_align)
250 size = (size - (nblock -
reinterpret_cast<unsigned long>(block)))
252 block =
reinterpret_cast<void*
>(nblock);
256 size = (size + mb_align) & ~mb_align;
258 check_overlap(block, size);
260 Mem_block **c = &_first;
265 while (*c && *c < block)
271 *c =
reinterpret_cast<Mem_block*
>(block);
281 unsigned granularity,
unsigned long lower,
284 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __func__);
286 unsigned char const mb_bits = arith::Ld<
sizeof(Mem_block)>::value;
287 unsigned long const mb_align = (1UL << mb_bits) - 1;
294 *max = *max & ~(granularity - 1UL);
299 unsigned long almask = align ? (align - 1UL) : 0;
302 if (almask < mb_align)
305 Mem_block **c = &_first;
307 unsigned long max_fit = 0;
308 unsigned long a_lower = (lower + almask) & ~almask;
310 for (; *c; c = &(*c)->next)
313 unsigned long n_start =
reinterpret_cast<unsigned long>(*c);
317 if ((*c)->size < min)
321 if (upper < n_start || a_lower > n_start + (*c)->size)
325 unsigned long a_start = (n_start + almask) & ~almask;
328 if (a_start - n_start >= (*c)->size)
331 a_start = a_start < a_lower ? a_lower : a_start;
334 if (min > ~0UL - a_start)
338 if (a_start + min - 1UL > upper)
342 unsigned long r_size = (*c)->size - a_start + n_start;
345 if (a_start + r_size - 1UL > upper)
346 r_size = upper - a_start + 1UL;
349 r_size &= ~(granularity - 1UL);
362 if (r_size > max_fit)
371 unsigned long n_start =
reinterpret_cast<unsigned long>(*fit);
372 unsigned long a_lower = (lower + almask) & ~almask;
373 unsigned long a_start = (n_start + almask) & ~almask;
374 a_start = a_start < a_lower ? a_lower : a_start;
375 unsigned long r_size = (*fit)->size - a_start + n_start;
377 if (a_start > n_start)
379 (*fit)->size -= r_size;
386 if (r_size == max_fit)
387 return reinterpret_cast<void *
>(a_start);
389 Mem_block *m =
reinterpret_cast<Mem_block*
>(a_start + max_fit);
391 m->size = r_size - max_fit;
393 return reinterpret_cast<void *
>(a_start);
403 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __func__);
405 unsigned long const mb_align
406 = (1UL << arith::Ld<
sizeof(Mem_block)>::value) - 1;
409 size = (size + mb_align) & ~mb_align;
411 unsigned long almask = align ? (align - 1UL) : 0;
414 if (almask < mb_align)
417 Mem_block **c = &_first;
418 unsigned long a_lower = (lower + almask) & ~almask;
420 for (; *c; c=&(*c)->next)
423 unsigned long n_start =
reinterpret_cast<unsigned long>(*c);
427 if ((*c)->size < size)
431 if (upper < n_start || a_lower > n_start + (*c)->size)
435 unsigned long a_start = (n_start + almask) & ~almask;
438 if (a_start - n_start >= (*c)->size)
441 a_start = a_start < a_lower ? a_lower : a_start;
444 if (size > ~0UL - a_start)
448 if (a_start + size - 1UL > upper)
453 unsigned long r_size = (*c)->size - a_start + n_start;
459 if (a_start > n_start)
464 (*c)->size -= r_size;
474 return reinterpret_cast<void*
>(a_start);
477 Mem_block *m =
reinterpret_cast<Mem_block*
>(a_start + size);
479 m->size = r_size - size;
481 return reinterpret_cast<void *
>(a_start);
490 List_alloc_sanity_guard __attribute__((unused)) guard(
this, __FUNCTION__);
491 Mem_block *c = _first;
502template <
typename DBG>
504List_alloc::dump_free_list(DBG &out)
506 Mem_block *c = _first;
517 else if (c->size < 1 << 20)
528 out.printf(
"%12p - %12p (%u %s)\n", c,
529 reinterpret_cast<char *
>(c) + c->size - 1, sz, unit);
Standard list-based allocator.
unsigned long avail()
Get the amount of available memory.
void * alloc_max(unsigned long min, unsigned long *max, unsigned long align, unsigned granularity, unsigned long lower=0, unsigned long upper=~0UL)
Allocate a memory block of min <= size <= max.
List_alloc()
Initializes an empty list allocator.
void * alloc(unsigned long size, unsigned long align, unsigned long lower=0, unsigned long upper=~0UL)
Allocate a memory block.
void free(void *block, unsigned long size, bool initial_free=false)
Return a free memory block to the allocator.
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.