source: rtems/cpukit/score/src/heapallocatealigned.c @ dea3eccb

4.104.11
Last change on this file since dea3eccb was dea3eccb, checked in by Joel Sherrill <joel.sherrill@…>, on Sep 6, 2009 at 3:24:08 PM

2009-09-06 Sebastian Huber <Sebastian.Huber@…>

  • libcsupport/src/free.c, libmisc/stackchk/check.c, rtems/include/rtems/rtems/region.h, rtems/src/regioncreate.c, rtems/src/regionextend.c, rtems/src/regiongetinfo.c, rtems/src/regiongetsegment.c, rtems/src/regiongetsegmentsize.c, rtems/src/regionresizesegment.c, score/src/pheapallocate.c, score/src/pheapallocatealigned.c, score/src/pheapextend.c, score/src/pheapfree.c, score/src/pheapgetblocksize.c, score/src/pheapgetfreeinfo.c, score/src/pheapgetinfo.c, score/src/pheapgetsize.c, score/src/pheapinit.c, score/src/pheapresizeblock.c, score/src/pheapwalk.c: Update for heap API changes.
  • score/include/rtems/score/apimutex.h, score/include/rtems/score/object.h: Documentation.
  • score/include/rtems/score/heap.h, score/include/rtems/score/protectedheap.h, score/inline/rtems/score/heap.inl, score/src/heap.c, score/src/heapallocate.c, score/src/heapallocatealigned.c, score/src/heapextend.c, score/src/heapfree.c, score/src/heapgetfreeinfo.c, score/src/heapgetinfo.c, score/src/heapresizeblock.c, score/src/heapsizeofuserarea.c, score/src/heapwalk.c: Overall cleanup. Added boundary constraint to allocation function. More changes follow.
  • Property mode set to 100644
File size: 8.4 KB
Line 
1#if 0
2/*
3 *  Heap Handler
4 *
5 *  COPYRIGHT (c) 1989-1999.
6 *  On-Line Applications Research Corporation (OAR).
7 *
8 *  The license and distribution terms for this file may be
9 *  found in the file LICENSE in this distribution or at
10 *  http://www.rtems.com/license/LICENSE.
11 *
12 *  $Id$
13 */
14
15#if HAVE_CONFIG_H
16#include "config.h"
17#endif
18
19#include <rtems/system.h>
20#include <rtems/score/sysstate.h>
21#include <rtems/score/heap.h>
22
23#if defined(RTEMS_HEAP_DEBUG)
24
25static void
26check_result(
27  Heap_Control *the_heap,
28  Heap_Block   *the_block,
29  uintptr_t     user_addr,
30  uintptr_t     aligned_user_addr,
31  uintptr_t      size
32)
33{
34  uintptr_t const user_area = _Heap_Alloc_area_of_block(the_block);
35  uintptr_t const block_end = (uintptr_t) the_block
36    + _Heap_Block_size(the_block) + HEAP_BLOCK_SIZE_OFFSET;
37  uintptr_t const user_end = aligned_user_addr + size;
38  uintptr_t const heap_start = (uintptr_t) the_heap->start + HEAP_BLOCK_HEADER_SIZE;
39  uintptr_t const heap_end = (uintptr_t) the_heap->final
40    + HEAP_BLOCK_SIZE_OFFSET;
41  uintptr_t const page_size = the_heap->page_size;
42
43  _HAssert(user_addr == user_area);
44  _HAssert(aligned_user_addr - user_area < page_size);
45  _HAssert(aligned_user_addr >= user_area);
46  _HAssert(aligned_user_addr < block_end);
47  _HAssert(user_end > user_area);
48  _HAssert(user_end <= block_end);
49  _HAssert(aligned_user_addr >= heap_start);
50  _HAssert(aligned_user_addr < heap_end);
51  _HAssert(user_end > heap_start);
52  _HAssert(user_end <= heap_end);
53}
54
55#else /* !defined(RTEMS_HEAP_DEBUG) */
56
57#define check_result(a, b, c, d, e) ((void)0)
58
59#endif /* !defined(RTEMS_HEAP_DEBUG) */
60
61/*
62 * Allocate block of size 'alloc_size' from 'the_block' belonging to
63 * 'the_heap'. Split 'the_block' if possible, otherwise allocate it entirely.
64 * When split, make the upper part used, and leave the lower part free.
65 * Return the block allocated.
66 *
67 * NOTE: this is similar to _Heap_Block_allocate(), except it makes different
68 * part of the split block used, and returns address of the block instead of its
69 * size. We do need such variant for _Heap_Allocate_aligned() as we can't allow
70 * user pointer to be too far from the beginning of the block, so that we can
71 * recover start-of-block address from the user pointer without additional
72 * information stored in the heap.
73 */
74static
75Heap_Block *block_allocate(
76  Heap_Control  *the_heap,
77  Heap_Block    *the_block,
78  uintptr_t       alloc_size
79)
80{
81  Heap_Statistics *const stats = &the_heap->stats;
82  uintptr_t const block_size = _Heap_Block_size(the_block);
83  uintptr_t const the_rest = block_size - alloc_size;
84
85  _HAssert(_Heap_Is_aligned(block_size, the_heap->page_size));
86  _HAssert(_Heap_Is_aligned(alloc_size, the_heap->page_size));
87  _HAssert(alloc_size <= block_size);
88  _HAssert(_Heap_Is_prev_used(the_block));
89
90  if (the_rest >= the_heap->min_block_size) {
91    /* Split the block so that lower part is still free, and upper part
92       becomes used. */
93    the_block->size_and_flag = the_rest | HEAP_PREV_BLOCK_USED;
94    the_block = _Heap_Block_at(the_block, the_rest);
95    the_block->prev_size = the_rest;
96    the_block->size_and_flag = alloc_size;
97  } else {
98    /* Don't split the block as remainder is either zero or too small to be
99       used as a separate free block. Change 'alloc_size' to the size of the
100       block and remove the block from the list of free blocks. */
101    _Heap_Free_list_remove(the_block);
102    alloc_size = block_size;
103    stats->free_blocks -= 1;
104  }
105  /* Mark the block as used (in the next block). */
106  _Heap_Block_at(the_block, alloc_size)->size_and_flag |= HEAP_PREV_BLOCK_USED;
107  /* Update statistics */
108  stats->free_size -= alloc_size;
109  if (stats->min_free_size > stats->free_size)
110    stats->min_free_size = stats->free_size;
111  stats->used_blocks += 1;
112  return the_block;
113}
114
115
116/*PAGE
117 *
118 *  _Heap_Allocate_aligned
119 *
120 *  This kernel routine allocates the requested size of memory
121 *  from the specified heap so that returned address is aligned according to
122 *  the 'alignment'.
123 *
124 *  Input parameters:
125 *    the_heap  - pointer to the heap control block.
126 *    size      - size in bytes of the memory block to allocate.
127 *    alignment - required user pointer alignment in bytes
128 *
129 *  Output parameters:
130 *    returns - starting address of memory block allocated. The address is
131 *              aligned on specified boundary.
132 */
133
134void *_Heap_Allocate_aligned(
135  Heap_Control *the_heap,
136  uintptr_t      size,
137  uintptr_t      alignment
138)
139{
140  uintptr_t search_count;
141  Heap_Block *the_block;
142
143  void *user_ptr = NULL;
144  uintptr_t  const page_size = the_heap->page_size;
145  Heap_Statistics *const stats = &the_heap->stats;
146  Heap_Block *const tail = _Heap_Free_list_tail(the_heap);
147
148  uintptr_t const end_to_user_offs = size - HEAP_BLOCK_SIZE_OFFSET;
149
150  uintptr_t const the_size =
151    _Heap_Calc_block_size(size, page_size, the_heap->min_block_size);
152
153  if (the_size == 0)
154    return NULL;
155
156  if (alignment == 0)
157    alignment = CPU_ALIGNMENT;
158
159  /* Find large enough free block that satisfies the alignment requirements. */
160
161  for (the_block = _Heap_Free_list_first(the_heap), search_count = 0;
162      the_block != tail;
163      the_block = the_block->next, ++search_count)
164  {
165    uintptr_t const block_size = _Heap_Block_size(the_block);
166
167    /* As we always coalesce free blocks, prev block must have been used. */
168    _HAssert(_Heap_Is_prev_used(the_block));
169
170    if (block_size >= the_size) { /* the_block is large enough. */
171
172      uintptr_t user_addr;
173      uintptr_t aligned_user_addr;
174      uintptr_t const user_area = _Heap_Alloc_area_of_block(the_block);
175
176      /* Calculate 'aligned_user_addr' that will become the user pointer we
177         return. It should be at least 'end_to_user_offs' bytes less than the
178         the 'block_end' and should be aligned on 'alignment' boundary.
179         Calculations are from the 'block_end' as we are going to split free
180         block so that the upper part of the block becomes used block. */
181      uintptr_t const block_end = (uintptr_t) the_block + block_size;
182      aligned_user_addr =
183        _Heap_Align_down(block_end - end_to_user_offs, alignment);
184
185      /* 'user_addr' is the 'aligned_user_addr' further aligned down to the
186         'page_size' boundary. We need it as blocks' user areas should begin
187         only at 'page_size' aligned addresses */
188      user_addr = _Heap_Align_down(aligned_user_addr, page_size);
189
190      /* Make sure 'user_addr' calculated didn't run out of 'the_block'. */
191      if (user_addr >= user_area) {
192
193        /* The block seems to be acceptable. Check if the remainder of
194           'the_block' is less than 'min_block_size' so that 'the_block' won't
195           actually be split at the address we assume. */
196        if (user_addr - user_area < the_heap->min_block_size) {
197
198          /* The block won't be split, so 'user_addr' will be equal to the
199             'user_area'. */
200          user_addr = user_area;
201
202          /* We can't allow the distance between 'user_addr' and
203           'aligned_user_addr' to be outside of [0,page_size) range. If we do,
204           we will need to store this distance somewhere to be able to
205           resurrect the block address from the user pointer. (Having the
206           distance within [0,page_size) range allows resurrection by
207           aligning user pointer down to the nearest 'page_size' boundary.) */
208          if (aligned_user_addr - user_addr >= page_size) {
209
210            /* The user pointer will be too far from 'user_addr'. See if we
211               can make 'aligned_user_addr' to be close enough to the
212               'user_addr'. */
213            aligned_user_addr = _Heap_Align_up(user_addr, alignment);
214            if (aligned_user_addr - user_addr >= page_size) {
215              /* No, we can't use the block */
216              continue;
217            }
218          }
219        }
220
221        /* The block is indeed acceptable: calculate the size of the block
222           to be allocated and perform allocation. */
223        uintptr_t const alloc_size =
224            block_end - user_addr + HEAP_BLOCK_HEADER_SIZE;
225
226        _HAssert(_Heap_Is_aligned(aligned_user_addr, alignment));
227
228        the_block = block_allocate(the_heap, the_block, alloc_size);
229
230        stats->searches += search_count + 1;
231        stats->allocs += 1;
232
233        check_result(the_heap, the_block, user_addr,
234        aligned_user_addr, size);
235
236        user_ptr = (void*)aligned_user_addr;
237
238        break;
239      }
240    }
241  }
242
243  if (stats->max_search < search_count)
244    stats->max_search = search_count;
245
246  return user_ptr;
247}
248#endif
Note: See TracBrowser for help on using the repository browser.