source: rtems/cpukit/score/src/heapallocatealigned.c @ 493e405

4.104.114.84.95
Last change on this file since 493e405 was 493e405, checked in by Joel Sherrill <joel.sherrill@…>, on Sep 12, 2007 at 8:11:33 PM

2007-09-12 Sergei Organov <osv@…>

PR 1258/rtems

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