source: rtems/cpukit/score/src/heapextend.c @ 25f5730f

4.11
Last change on this file since 25f5730f was c499856, checked in by Chris Johns <chrisj@…>, on Mar 20, 2014 at 9:10:47 PM

Change all references of rtems.com to rtems.org.

  • Property mode set to 100644
File size: 7.0 KB
Line 
1/**
2 * @file
3 *
4 * @ingroup ScoreHeap
5 *
6 * @brief Heap Handler implementation.
7 */
8
9/*
10 *  COPYRIGHT (c) 1989-1999.
11 *  On-Line Applications Research Corporation (OAR).
12 *
13 *  Copyright (c) 2010 embedded brains GmbH.
14 *
15 *  The license and distribution terms for this file may be
16 *  found in the file LICENSE in this distribution or at
17 *  http://www.rtems.org/license/LICENSE.
18 */
19
20#if HAVE_CONFIG_H
21#include "config.h"
22#endif
23
24#include <rtems/system.h>
25#include <rtems/score/heapimpl.h>
26
27static void _Heap_Free_block( Heap_Control *heap, Heap_Block *block )
28{
29  Heap_Statistics *const stats = &heap->stats;
30  Heap_Block *first_free;
31
32  /* Statistics */
33  ++stats->used_blocks;
34  --stats->frees;
35
36  /*
37   * The _Heap_Free() will place the block to the head of free list.  We want
38   * the new block at the end of the free list.  So that initial and earlier
39   * areas are consumed first.
40   */
41  _Heap_Free( heap, (void *) _Heap_Alloc_area_of_block( block ) );
42  _Heap_Protection_free_all_delayed_blocks( heap );
43  first_free = _Heap_Free_list_first( heap );
44  _Heap_Free_list_remove( first_free );
45  _Heap_Free_list_insert_before( _Heap_Free_list_tail( heap ), first_free );
46}
47
48static void _Heap_Merge_below(
49  Heap_Control *heap,
50  uintptr_t extend_area_begin,
51  Heap_Block *first_block
52)
53{
54  uintptr_t const page_size = heap->page_size;
55  uintptr_t const new_first_block_alloc_begin =
56    _Heap_Align_up( extend_area_begin + HEAP_BLOCK_HEADER_SIZE, page_size );
57  uintptr_t const new_first_block_begin =
58    new_first_block_alloc_begin - HEAP_BLOCK_HEADER_SIZE;
59  uintptr_t const first_block_begin = (uintptr_t) first_block;
60  uintptr_t const new_first_block_size =
61    first_block_begin - new_first_block_begin;
62  Heap_Block *const new_first_block = (Heap_Block *) new_first_block_begin;
63
64  new_first_block->prev_size = first_block->prev_size;
65  new_first_block->size_and_flag = new_first_block_size | HEAP_PREV_BLOCK_USED;
66
67  _Heap_Free_block( heap, new_first_block );
68}
69
70static void _Heap_Merge_above(
71  Heap_Control *heap,
72  Heap_Block *last_block,
73  uintptr_t extend_area_end
74)
75{
76  uintptr_t const page_size = heap->page_size;
77  uintptr_t const last_block_begin = (uintptr_t) last_block;
78  uintptr_t const last_block_new_size = _Heap_Align_down(
79    extend_area_end - last_block_begin - HEAP_BLOCK_HEADER_SIZE,
80    page_size
81  );
82  Heap_Block *const new_last_block =
83    _Heap_Block_at( last_block, last_block_new_size );
84
85  new_last_block->size_and_flag =
86    (last_block->size_and_flag - last_block_new_size)
87      | HEAP_PREV_BLOCK_USED;
88
89  _Heap_Block_set_size( last_block, last_block_new_size );
90
91  _Heap_Free_block( heap, last_block );
92}
93
94static void _Heap_Link_below(
95  Heap_Block *link,
96  Heap_Block *last_block
97)
98{
99  uintptr_t const last_block_begin = (uintptr_t) last_block;
100  uintptr_t const link_begin = (uintptr_t) link;
101
102  last_block->size_and_flag =
103    (link_begin - last_block_begin) | HEAP_PREV_BLOCK_USED;
104}
105
106static void _Heap_Link_above(
107  Heap_Block *link,
108  Heap_Block *first_block,
109  Heap_Block *last_block
110)
111{
112  uintptr_t const link_begin = (uintptr_t) link;
113  uintptr_t const first_block_begin = (uintptr_t) first_block;
114
115  _Heap_Block_set_size( link, first_block_begin - link_begin );
116
117  last_block->size_and_flag |= HEAP_PREV_BLOCK_USED;
118}
119
120uintptr_t _Heap_Extend(
121  Heap_Control *heap,
122  void *extend_area_begin_ptr,
123  uintptr_t extend_area_size,
124  uintptr_t unused __attribute__((unused))
125)
126{
127  Heap_Statistics *const stats = &heap->stats;
128  Heap_Block *const first_block = heap->first_block;
129  Heap_Block *start_block = first_block;
130  Heap_Block *merge_below_block = NULL;
131  Heap_Block *merge_above_block = NULL;
132  Heap_Block *link_below_block = NULL;
133  Heap_Block *link_above_block = NULL;
134  Heap_Block *extend_first_block = NULL;
135  Heap_Block *extend_last_block = NULL;
136  uintptr_t const page_size = heap->page_size;
137  uintptr_t const min_block_size = heap->min_block_size;
138  uintptr_t const extend_area_begin = (uintptr_t) extend_area_begin_ptr;
139  uintptr_t const extend_area_end = extend_area_begin + extend_area_size;
140  uintptr_t const free_size = stats->free_size;
141  uintptr_t extend_first_block_size = 0;
142  uintptr_t extended_size = 0;
143  bool extend_area_ok = false;
144
145  if ( extend_area_end < extend_area_begin ) {
146    return 0;
147  }
148
149  extend_area_ok = _Heap_Get_first_and_last_block(
150    extend_area_begin,
151    extend_area_size,
152    page_size,
153    min_block_size,
154    &extend_first_block,
155    &extend_last_block
156  );
157  if (!extend_area_ok ) {
158    /* For simplicity we reject extend areas that are too small */
159    return 0;
160  }
161
162  do {
163    uintptr_t const sub_area_begin = (start_block != first_block) ?
164      (uintptr_t) start_block : heap->area_begin;
165    uintptr_t const sub_area_end = start_block->prev_size;
166    Heap_Block *const end_block =
167      _Heap_Block_of_alloc_area( sub_area_end, page_size );
168
169    if (
170      sub_area_end > extend_area_begin && extend_area_end > sub_area_begin
171    ) {
172      return 0;
173    }
174
175    if ( extend_area_end == sub_area_begin ) {
176      merge_below_block = start_block;
177    } else if ( extend_area_end < sub_area_end ) {
178      link_below_block = start_block;
179    }
180
181    if ( sub_area_end == extend_area_begin ) {
182      start_block->prev_size = extend_area_end;
183
184      merge_above_block = end_block;
185    } else if ( sub_area_end < extend_area_begin ) {
186      link_above_block = end_block;
187    }
188
189    start_block = _Heap_Block_at( end_block, _Heap_Block_size( end_block ) );
190  } while ( start_block != first_block );
191
192  if ( extend_area_begin < heap->area_begin ) {
193    heap->area_begin = extend_area_begin;
194  } else if ( heap->area_end < extend_area_end ) {
195    heap->area_end = extend_area_end;
196  }
197
198  extend_first_block_size =
199    (uintptr_t) extend_last_block - (uintptr_t) extend_first_block;
200
201  extend_first_block->prev_size = extend_area_end;
202  extend_first_block->size_and_flag =
203    extend_first_block_size | HEAP_PREV_BLOCK_USED;
204  _Heap_Protection_block_initialize( heap, extend_first_block );
205
206  extend_last_block->prev_size = extend_first_block_size;
207  extend_last_block->size_and_flag = 0;
208  _Heap_Protection_block_initialize( heap, extend_last_block );
209
210  if ( (uintptr_t) extend_first_block < (uintptr_t) heap->first_block ) {
211    heap->first_block = extend_first_block;
212  } else if ( (uintptr_t) extend_last_block > (uintptr_t) heap->last_block ) {
213    heap->last_block = extend_last_block;
214  }
215
216  if ( merge_below_block != NULL ) {
217    _Heap_Merge_below( heap, extend_area_begin, merge_below_block );
218  } else if ( link_below_block != NULL ) {
219    _Heap_Link_below(
220      link_below_block,
221      extend_last_block
222    );
223  }
224
225  if ( merge_above_block != NULL ) {
226    _Heap_Merge_above( heap, merge_above_block, extend_area_end );
227  } else if ( link_above_block != NULL ) {
228    _Heap_Link_above(
229      link_above_block,
230      extend_first_block,
231      extend_last_block
232    );
233  }
234
235  if ( merge_below_block == NULL && merge_above_block == NULL ) {
236    _Heap_Free_block( heap, extend_first_block );
237  }
238
239  _Heap_Set_last_block_size( heap );
240
241  extended_size = stats->free_size - free_size;
242
243  /* Statistics */
244  stats->size += extended_size;
245
246  return extended_size;
247}
Note: See TracBrowser for help on using the repository browser.