source: rtems/cpukit/libcsupport/src/malloc.c @ 80f2885b

4.104.114.84.9
Last change on this file since 80f2885b was 80f2885b, checked in by Joel Sherrill <joel.sherrill@…>, on May 20, 2005 at 7:15:41 PM

2005-05-14 Sergei Organov <osv@…>

PR 746/rtems
Optimize realloc(). The problem is that realloc() can neither grow
nor shrink efficiently the current memory region without support
from underlying heap/region modules. The patch introduces one new
routine for each of heap and region modules, _Heap_Resize_block(),
and rtems_region_resize_segment(), respectively, and uses the
latter to optimize realloc().

The implementation of _Heap_Resize_block() lead to changing of the
heap allocation strategy: now the heap manager, when splits larger
free block into used and new free parts, makes the first part of
the block used, not the last one as it was before. Due to this new
strategy, _Heap_Resize_block() never needs to change the user
pointer.

Caveat: unlike previous heap implementation, first few bytes of
the contents of the memory allocated from the heap are now almost
never all zero. This can trigger bugs in client code that have not
been visible before this patch.

  • libcsupport/src/malloc.c (realloc): try to resize segment in place using new rtems_region_resize_segment() routine before falling back to the malloc()/free() method.
  • score/src/heap.c: (_Heap_Initialize): change initial heap layout to reflect new allocation strategy of using of the lower part of a previously free block when splitting it for the purpose of allocation. (_Heap_Block_allocate): when split, make the lower part used, and leave the upper part free. Return type changed from Heap_Block* to uint32_t.
  • score/include/rtems/score/heap.h: (Heap_Statistics): added 'resizes' field. (Heap_Resize_status): new enum. (_Heap_Resize_block): new routine. (_Heap_Block_allocate): return type changed from Heap_Block* to uint32_t.
  • score/src/heapwalk.c: reflect new heap layout in checks.
  • score/src/heapsizeofuserarea.c: more assertions added.
  • score/src/heapresizeblock.c: new file. (_Heap_Resize_block): new routine.
  • score/src/heapfree.c: reverse the checks _Heap_Is_block_in() and _Heap_Is_prev_used() on entry to be in this order.
  • score/src/heapallocate.c, score/src/heapallocatealigned.c: ignore return value of _Heap_Block_allocate().
  • score/Makefile.am (HEAP_C_FILES): added src/heapresizeblock.c.
  • rtems/include/rtems/rtems/region.h: (rtems_region_resize_segment): new interface routine. (_Region_Process_queue): new internal routine called from rtems_region_resize_segment() and rtems_region_return_segment().
  • rtems/src/regionreturnsegment.c: move queue management code into the new internal routine _Region_Process_queue() and call it.
  • rtems/src/regionresizesegment.c: new file. (rtems_region_resize_segment): new interface routine.
  • rtems/src/regionprocessqueue.c: new file. (_Region_Process_queue): new internal routine containing queue management code factored out from 'regionreturnsegment.c'.
  • rtems/Makefile.am (REGION_C_FILES): Added src/regionresizesegment.c, and src/regionprocessqueue.c.
  • ada/rtems.adb, ada/rtems.ads: Added Region_Resize_Segment.
  • Property mode set to 100644
File size: 11.0 KB
Line 
1/*
2 *  RTEMS Malloc Family Implementation
3 *
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#define __RTEMS_VIOLATE_KERNEL_VISIBILITY__
20#include <rtems.h>
21#include <rtems/libcsupport.h>
22#include <rtems/score/apimutex.h>
23#ifdef RTEMS_NEWLIB
24#include <sys/reent.h>
25#endif
26
27#include <stdio.h>
28#include <stdlib.h>
29#include <sys/types.h>
30#include <assert.h>
31#include <errno.h>
32#include <string.h>
33
34#include <unistd.h>    /* sbrk(2) */
35
36#include <rtems/chain.h>
37
38Chain_Control RTEMS_Malloc_GC_list;
39
40rtems_id RTEMS_Malloc_Heap;
41size_t RTEMS_Malloc_Sbrk_amount;
42
43#ifdef RTEMS_DEBUG
44#define MALLOC_STATS
45#define MALLOC_DIRTY
46#endif
47
48#ifdef MALLOC_STATS
49#define MSBUMP(f,n)    rtems_malloc_stats.f += (n)
50
51struct {
52    uint32_t    space_available;             /* current size of malloc area */
53    uint32_t    malloc_calls;                /* # calls to malloc */
54    uint32_t    free_calls;
55    uint32_t    realloc_calls;
56    uint32_t    calloc_calls;
57    uint32_t    max_depth;                   /* most ever malloc'd at 1 time */
58    uint64_t    lifetime_allocated;
59    uint64_t    lifetime_freed;
60} rtems_malloc_stats;
61
62#else                   /* No rtems_malloc_stats */
63#define MSBUMP(f,n)
64#endif
65
66void RTEMS_Malloc_Initialize(
67  void   *start,
68  size_t  length,
69  size_t  sbrk_amount
70)
71{
72  rtems_status_code   status;
73  void               *starting_address;
74  uint32_t      old_address;
75  uint32_t      u32_address;
76
77  /*
78   *  Initialize the garbage collection list to start with nothing on it.
79   */
80  Chain_Initialize_empty(&RTEMS_Malloc_GC_list);
81
82  /*
83   * If the starting address is 0 then we are to attempt to
84   * get length worth of memory using sbrk. Make sure we
85   * align the address that we get back.
86   */
87
88  starting_address = start;
89  RTEMS_Malloc_Sbrk_amount = sbrk_amount;
90
91  if (!starting_address) {
92    u32_address = (unsigned int)sbrk(length);
93
94    if (u32_address == (uint32_t  ) -1) {
95      rtems_fatal_error_occurred( RTEMS_NO_MEMORY );
96      /* DOES NOT RETURN!!! */
97    }
98
99    if (u32_address & (CPU_HEAP_ALIGNMENT-1)) {
100      old_address = u32_address;
101      u32_address = (u32_address + CPU_HEAP_ALIGNMENT) & ~(CPU_HEAP_ALIGNMENT-1);
102
103       /*
104        * adjust the length by whatever we aligned by
105        */
106
107      length -= u32_address - old_address;
108    }
109
110    starting_address = (void *)u32_address;
111  }
112
113  /*
114   *  If the BSP is not clearing out the workspace, then it is most likely
115   *  not clearing out the initial memory for the heap.  There is no
116   *  standard supporting zeroing out the heap memory.  But much code
117   *  with UNIX history seems to assume that memory malloc'ed during
118   *  initialization (before any free's) is zero'ed.  This is true most
119   *  of the time under UNIX because zero'ing memory when it is first
120   *  given to a process eliminates the chance of a process seeing data
121   *  left over from another process.  This would be a security violation.
122   */
123
124  if ( rtems_cpu_configuration_get_do_zero_of_workspace() )
125     memset( starting_address, 0, length );
126
127  /*
128   *  Unfortunately we cannot use assert if this fails because if this
129   *  has failed we do not have a heap and if we do not have a heap
130   *  STDIO cannot work because there will be no buffers.
131   */
132
133  status = rtems_region_create(
134    rtems_build_name( 'H', 'E', 'A', 'P' ),
135    starting_address,
136    length,
137    CPU_HEAP_ALIGNMENT,
138    RTEMS_DEFAULT_ATTRIBUTES,
139    &RTEMS_Malloc_Heap
140  );
141  if ( status != RTEMS_SUCCESSFUL )
142    rtems_fatal_error_occurred( status );
143
144#ifdef MALLOC_STATS
145  /* zero all the stats */
146  (void) memset( &rtems_malloc_stats, 0, sizeof(rtems_malloc_stats) );
147#endif
148
149  MSBUMP(space_available, length);
150}
151
152#ifdef RTEMS_NEWLIB
153void *malloc(
154  size_t  size
155)
156{
157  void              *return_this;
158  void              *starting_address;
159  uint32_t     the_size;
160  uint32_t     sbrk_amount;
161  rtems_status_code  status;
162  Chain_Node        *to_be_freed;
163
164  MSBUMP(malloc_calls, 1);
165
166  if ( !size )
167    return (void *) 0;
168
169  /*
170   *  Do not attempt to allocate memory if in a critical section or ISR.
171   */
172
173  if (_System_state_Is_up(_System_state_Get())) {
174    if (_Thread_Dispatch_disable_level > 0)
175      return (void *) 0;
176
177    if (_ISR_Nest_level > 0)
178      return (void *) 0;
179  }
180
181  /*
182   *  If some free's have been deferred, then do them now.
183   */
184  while ((to_be_freed = Chain_Get(&RTEMS_Malloc_GC_list)) != NULL)
185    free(to_be_freed);
186
187  /*
188   * Try to give a segment in the current region if there is not
189   * enough space then try to grow the region using rtems_region_extend().
190   * If this fails then return a NULL pointer.
191   */
192
193  status = rtems_region_get_segment(
194    RTEMS_Malloc_Heap,
195    size,
196    RTEMS_NO_WAIT,
197    RTEMS_NO_TIMEOUT,
198    &return_this
199  );
200
201  if ( status != RTEMS_SUCCESSFUL ) {
202    /*
203     *  Round to the "requested sbrk amount" so hopefully we won't have
204     *  to grow again for a while.  This effectively does sbrk() calls
205     *  in "page" amounts.
206     */
207
208    sbrk_amount = RTEMS_Malloc_Sbrk_amount;
209
210    if ( sbrk_amount == 0 )
211      return (void *) 0;
212
213    the_size = ((size + sbrk_amount) / sbrk_amount * sbrk_amount);
214
215    if ((starting_address = (void *)sbrk(the_size))
216            == (void*) -1)
217      return (void *) 0;
218
219    status = rtems_region_extend(
220      RTEMS_Malloc_Heap,
221      starting_address,
222      the_size
223    );
224    if ( status != RTEMS_SUCCESSFUL ) {
225      sbrk(-the_size);
226      errno = ENOMEM;
227      return (void *) 0;
228    }
229
230    MSBUMP(space_available, the_size);
231
232    status = rtems_region_get_segment(
233      RTEMS_Malloc_Heap,
234       size,
235       RTEMS_NO_WAIT,
236       RTEMS_NO_TIMEOUT,
237       &return_this
238    );
239    if ( status != RTEMS_SUCCESSFUL ) {
240      errno = ENOMEM;
241      return (void *) 0;
242    }
243  }
244
245#ifdef MALLOC_STATS
246  if (return_this)
247  {
248      size_t     actual_size;
249      uint32_t   current_depth;
250      status = rtems_region_get_segment_size(
251                   RTEMS_Malloc_Heap, return_this, &actual_size);
252      MSBUMP(lifetime_allocated, actual_size);
253      current_depth = rtems_malloc_stats.lifetime_allocated -
254                   rtems_malloc_stats.lifetime_freed;
255      if (current_depth > rtems_malloc_stats.max_depth)
256          rtems_malloc_stats.max_depth = current_depth;
257  }
258#endif
259
260#ifdef MALLOC_DIRTY
261  (void) memset(return_this, 0xCF, size);
262#endif
263
264  return return_this;
265}
266
267void *calloc(
268  size_t nelem,
269  size_t elsize
270)
271{
272  register char *cptr;
273  int length;
274
275  MSBUMP(calloc_calls, 1);
276
277  length = nelem * elsize;
278  cptr = malloc( length );
279  if ( cptr )
280    memset( cptr, '\0', length );
281
282  MSBUMP(malloc_calls, -1);   /* subtract off the malloc */
283
284  return cptr;
285}
286
287void *realloc(
288  void *ptr,
289  size_t size
290)
291{
292  size_t old_size;
293  rtems_status_code status;
294  char *new_area;
295
296  MSBUMP(realloc_calls, 1);
297
298  /*
299   *  Do not attempt to allocate memory if in a critical section or ISR.
300   */
301
302  if (_System_state_Is_up(_System_state_Get())) {
303    if (_Thread_Dispatch_disable_level > 0)
304      return (void *) 0;
305
306    if (_ISR_Nest_level > 0)
307      return (void *) 0;
308  }
309
310  /*
311   * Continue with realloc().
312   */
313  if ( !ptr )
314    return malloc( size );
315
316  if ( !size ) {
317    free( ptr );
318    return (void *) 0;
319  }
320
321  status =
322    rtems_region_resize_segment( RTEMS_Malloc_Heap, ptr, size, &old_size );
323
324  if( status == RTEMS_SUCCESSFUL ) {
325    return ptr;
326  }
327  else if ( status != RTEMS_UNSATISFIED ) {
328    errno = EINVAL;
329    return (void *) 0;
330  }
331
332  new_area = malloc( size );
333
334  MSBUMP(malloc_calls, -1);   /* subtract off the malloc */
335
336  /*
337   *  There used to be a free on this error case but it is wrong to
338   *  free the memory per OpenGroup Single UNIX Specification V2
339   *  and the C Standard.
340   */
341
342  if ( !new_area ) {
343    return (void *) 0;
344  }
345
346  status = rtems_region_get_segment_size( RTEMS_Malloc_Heap, ptr, &old_size );
347  if ( status != RTEMS_SUCCESSFUL ) {
348    errno = EINVAL;
349    return (void *) 0;
350  }
351
352  memcpy( new_area, ptr, (size < old_size) ? size : old_size );
353  free( ptr );
354
355  return new_area;
356
357}
358
359void free(
360  void *ptr
361)
362{
363  rtems_status_code status;
364
365  MSBUMP(free_calls, 1);
366
367  if ( !ptr )
368    return;
369
370  /*
371   *  Do not attempt to free memory if in a critical section or ISR.
372   */
373
374  if (_System_state_Is_up(_System_state_Get())) {
375    if ((_Thread_Dispatch_disable_level > 0) || (_ISR_Nest_level > 0)) {
376      Chain_Append(&RTEMS_Malloc_GC_list, (Chain_Node *)ptr);
377      return;
378    }
379  }
380
381#ifdef MALLOC_STATS
382  {
383      size_t size;
384      status = rtems_region_get_segment_size( RTEMS_Malloc_Heap, ptr, &size );
385      if ( status == RTEMS_SUCCESSFUL ) {
386          MSBUMP(lifetime_freed, size);
387      }
388  }
389#endif
390
391  status = rtems_region_return_segment( RTEMS_Malloc_Heap, ptr );
392  if ( status != RTEMS_SUCCESSFUL ) {
393    errno = EINVAL;
394    assert( 0 );
395  }
396}
397/* end if RTEMS_NEWLIB */
398#endif
399
400#ifdef MALLOC_STATS
401/*
402 * Dump the malloc statistics
403 * May be called via atexit()  (installable by our bsp) or
404 * at any time by user
405 */
406
407void malloc_dump(void)
408{
409    uint32_t   allocated = rtems_malloc_stats.lifetime_allocated -
410                     rtems_malloc_stats.lifetime_freed;
411
412    printf("Malloc stats\n");
413    printf("  avail:%uk  allocated:%uk (%d%%) "
414              "max:%uk (%d%%) lifetime:%Luk freed:%Luk\n",
415           (unsigned int) rtems_malloc_stats.space_available / 1024,
416           (unsigned int) allocated / 1024,
417           /* avoid float! */
418           (allocated * 100) / rtems_malloc_stats.space_available,
419           (unsigned int) rtems_malloc_stats.max_depth / 1024,
420           (rtems_malloc_stats.max_depth * 100) / rtems_malloc_stats.space_available,
421           (uint64_t  ) rtems_malloc_stats.lifetime_allocated / 1024,
422           (uint64_t  ) rtems_malloc_stats.lifetime_freed / 1024);
423    printf("  Call counts:   malloc:%d   free:%d   realloc:%d   calloc:%d\n",
424           rtems_malloc_stats.malloc_calls,
425           rtems_malloc_stats.free_calls,
426           rtems_malloc_stats.realloc_calls,
427           rtems_malloc_stats.calloc_calls);
428}
429
430
431void malloc_walk(size_t source, size_t printf_enabled)
432{
433   register Region_Control *the_region;
434   Objects_Locations        location;
435
436  _RTEMS_Lock_allocator();                      /* to prevent deletion */
437   the_region = _Region_Get( RTEMS_Malloc_Heap, &location );
438   if ( location == OBJECTS_LOCAL )
439   {
440      _Heap_Walk( &the_region->Memory, source, printf_enabled );
441   }
442  _RTEMS_Unlock_allocator();
443}
444
445#else
446
447void malloc_dump(void)
448{
449   return;
450}
451
452void malloc_walk(size_t source, size_t printf_enabled)
453{
454   return;
455}
456
457#endif
458
459/*
460 *  "Reentrant" versions of the above routines implemented above.
461 */
462
463#ifdef RTEMS_NEWLIB
464void *_malloc_r(
465  struct _reent *ignored,
466  size_t  size
467)
468{
469  return malloc( size );
470}
471
472void *_calloc_r(
473  struct _reent *ignored,
474  size_t nelem,
475  size_t elsize
476)
477{
478  return calloc( nelem, elsize );
479}
480
481void *_realloc_r(
482  struct _reent *ignored,
483  void *ptr,
484  size_t size
485)
486{
487  return realloc( ptr, size );
488}
489
490void _free_r(
491  struct _reent *ignored,
492  void *ptr
493)
494{
495  free( ptr );
496}
497
498#endif
Note: See TracBrowser for help on using the repository browser.