source: rtems/cpukit/score/src/heapwalk.c @ 1f89943

4.104.11
Last change on this file since 1f89943 was 1f89943, checked in by Ralf Corsepius <ralf.corsepius@…>, on Sep 29, 2009 at 4:25:52 AM

2009-09-29 Ralf Corsépius <ralf.corsepius@…>

  • score/src/heapwalk.c(Heap_Walk_printer): Add missing return type.
  • Property mode set to 100644
File size: 8.7 KB
Line 
1/**
2 * @file
3 *
4 * @ingroup ScoreHeap
5 *
6 * @brief Heap Handler implementation.
7 */
8
9/*
10 *  COPYRIGHT ( c ) 1989-2007.
11 *  On-Line Applications Research Corporation ( OAR ).
12 *
13 *  The license and distribution terms for this file may be
14 *  found in the file LICENSE in this distribution or at
15 *  http://www.rtems.com/license/LICENSE.
16 *
17 *  $Id$
18 */
19
20#if HAVE_CONFIG_H
21#include "config.h"
22#endif
23
24#include <rtems/system.h>
25#include <rtems/score/address.h>
26#include <rtems/score/sysstate.h>
27#include <rtems/score/heap.h>
28#include <rtems/score/interr.h>
29#include <rtems/bspIo.h>
30
31typedef int (*Heap_Walk_printer)(int, bool, const char*, ...);
32
33static void _Heap_Walk_print_nothing(
34  int source,
35  bool error,
36  const char *fmt,
37  ...
38)
39{
40  /* Do nothing */
41}
42
43static void _Heap_Walk_print( int source, bool error, const char *fmt, ... )
44{
45  va_list ap;
46
47  if ( error ) {
48    printk( "FAIL[%d]: ", source );
49  } else {
50    printk( "PASS[%d]: ", source );
51  }
52
53  va_start( ap, fmt );
54  vprintk( fmt, ap );
55  va_end( ap );
56}
57
58static bool _Heap_Walk_check_free_list(
59  int source,
60  Heap_Walk_printer printer,
61  Heap_Control *heap
62)
63{
64  uintptr_t const page_size = heap->page_size;
65  const Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
66  const Heap_Block *const first_free_block = _Heap_Free_list_first( heap );
67  const Heap_Block *prev_block = free_list_tail;
68  const Heap_Block *free_block = first_free_block;
69
70  while ( free_block != free_list_tail ) {
71    if ( !_Heap_Is_block_in_heap( heap, free_block ) ) {
72      (*printer)(
73        source,
74        true,
75        "free block 0x%08x: not in heap\n",
76        free_block
77      );
78
79      return false;
80    }
81
82    if (
83      !_Heap_Is_aligned( _Heap_Alloc_area_of_block( free_block ), page_size )
84    ) {
85      (*printer)(
86        source,
87        true,
88        "free block 0x%08x: alloc area not page aligned\n",
89        free_block
90      );
91
92      return false;
93    }
94
95    if ( _Heap_Is_used( free_block ) ) {
96      (*printer)(
97        source,
98        true,
99        "free block 0x%08x: is used\n",
100        free_block
101      );
102
103      return false;
104    }
105
106    if ( free_block->prev != prev_block ) {
107      (*printer)(
108        source,
109        true,
110        "free block 0x%08x: invalid previous block 0x%08x\n",
111        free_block,
112        free_block->prev
113      );
114
115      return false;
116    }
117
118    prev_block = free_block;
119    free_block = free_block->next;
120  }
121
122  return true;
123}
124
125static bool _Heap_Walk_is_in_free_list(
126  Heap_Control *heap,
127  Heap_Block *block
128)
129{
130  const Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
131  const Heap_Block *free_block = _Heap_Free_list_first( heap );
132
133  while ( free_block != free_list_tail ) {
134    if ( free_block == block ) {
135      return true;
136    }
137    free_block = free_block->next;
138  }
139
140  return false;
141}
142
143static bool _Heap_Walk_check_control(
144  int source,
145  Heap_Walk_printer printer,
146  Heap_Control *heap
147)
148{
149  uintptr_t const page_size = heap->page_size;
150  uintptr_t const min_block_size = heap->min_block_size;
151  Heap_Block *const first_free_block = _Heap_Free_list_first( heap );
152  Heap_Block *const last_free_block = _Heap_Free_list_last( heap );
153  Heap_Block *const first_block = heap->first_block;
154  Heap_Block *const last_block = heap->last_block;
155
156  (*printer)(
157    source,
158    false,
159    "page size %u, min block size %u\n"
160      "\tarea begin 0x%08x, area end 0x%08x\n"
161      "\tfirst block 0x%08x, last block 0x%08x\n"
162      "\tfirst free 0x%08x, last free 0x%08x\n",
163    page_size, min_block_size,
164    heap->area_begin, heap->area_end,
165    first_block, last_block,
166    first_free_block, last_free_block
167  );
168
169  if ( page_size == 0 ) {
170    (*printer)( source, true, "page size is zero\n" );
171
172    return false;
173  }
174
175  if ( !_Addresses_Is_aligned( (void *) page_size ) ) {
176    (*printer)(
177      source,
178      true,
179      "page size %u not CPU aligned\n",
180      page_size
181    );
182
183    return false;
184  }
185
186  if ( !_Heap_Is_aligned( min_block_size, page_size ) ) {
187    (*printer)(
188      source,
189      true,
190      "min block size %u not page aligned\n",
191      min_block_size
192    );
193
194    return false;
195  }
196
197  if (
198    !_Heap_Is_aligned( _Heap_Alloc_area_of_block( first_block ), page_size )
199  ) {
200    (*printer)(
201      source,
202      true,
203      "first block 0x%08x: alloc area not page aligned\n",
204      first_block
205    );
206
207    return false;
208  }
209
210  if ( !_Heap_Is_prev_used( first_block ) ) {
211    (*printer)(
212      source,
213      true,
214      "first block: HEAP_PREV_BLOCK_USED is cleared\n"
215    );
216
217    return false;
218  }
219
220  if ( first_block->prev_size != page_size ) {
221    (*printer)(
222      source,
223      true,
224      "first block: prev size %u != page size %u\n",
225      first_block->prev_size,
226      page_size
227    );
228
229    return false;
230  }
231
232  if ( _Heap_Is_free( last_block ) ) {
233    (*printer)(
234      source,
235      true,
236      "last block: is free\n"
237    );
238
239    return false;
240  }
241
242  return _Heap_Walk_check_free_list( source, printer, heap );
243}
244
245static bool _Heap_Walk_check_free_block(
246  int source,
247  Heap_Walk_printer printer,
248  Heap_Control *heap,
249  Heap_Block *block
250)
251{
252  Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap );
253  Heap_Block *const free_list_head = _Heap_Free_list_head( heap );
254  Heap_Block *const first_free_block = _Heap_Free_list_first( heap );
255  Heap_Block *const last_free_block = _Heap_Free_list_last( heap );
256  bool const prev_used = _Heap_Is_prev_used( block );
257  uintptr_t const block_size = _Heap_Block_size( block );
258  Heap_Block *const next_block = _Heap_Block_at( block, block_size );
259
260  (*printer)(
261    source,
262    false,
263    "block 0x%08x: prev 0x%08x%s, next 0x%08x%s\n",
264    block,
265    block->prev,
266    block->prev == first_free_block ?
267      " (= first)"
268        : (block->prev == free_list_head ? " (= head)" : ""),
269    block->next,
270    block->next == last_free_block ?
271      " (= last)"
272        : (block->next == free_list_tail ? " (= tail)" : "")
273  );
274
275  if ( block_size != next_block->prev_size ) {
276    (*printer)(
277      source,
278      true,
279      "block 0x%08x: size %u != size %u (in next block 0x%08x)\n",
280      block,
281      block_size,
282      next_block->prev_size,
283      next_block
284    );
285
286    return false;
287  }
288
289  if ( !prev_used ) {
290    (*printer)(
291      source,
292      true,
293      "block 0x%08x: two consecutive blocks are free\n",
294      block
295    );
296
297    return false;
298  }
299
300  if ( !_Heap_Walk_is_in_free_list( heap, block ) ) {
301    (*printer)(
302      source,
303      true,
304      "block 0x%08x: free block not in free list\n",
305      block
306    );
307
308    return false;
309  }
310
311  return true;
312}
313
314bool _Heap_Walk(
315  Heap_Control *heap,
316  int source,
317  bool dump
318)
319{
320  uintptr_t const page_size = heap->page_size;
321  uintptr_t const min_block_size = heap->min_block_size;
322  Heap_Block *const last_block = heap->last_block;
323  Heap_Block *block = heap->first_block;
324  Heap_Walk_printer printer = dump ?
325    _Heap_Walk_print : _Heap_Walk_print_nothing;
326
327  if ( !_System_state_Is_up( _System_state_Get() ) ) {
328    return true;
329  }
330
331  if ( !_Heap_Walk_check_control( source, printer, heap ) ) {
332    return false;
333  }
334
335  while ( block != last_block ) {
336    uintptr_t const block_begin = (uintptr_t) block;
337    uintptr_t const block_size = _Heap_Block_size( block );
338    bool const prev_used = _Heap_Is_prev_used( block );
339    Heap_Block *const next_block = _Heap_Block_at( block, block_size );
340    uintptr_t const next_block_begin = (uintptr_t) next_block;
341
342    if ( prev_used ) {
343      (*printer)(
344        source,
345        false,
346        "block 0x%08x: size %u\n",
347        block,
348        block_size
349      );
350    } else {
351      (*printer)(
352        source,
353        false,
354        "block 0x%08x: size %u, prev_size %u\n",
355        block,
356        block_size,
357        block->prev_size
358      );
359    }
360
361    if ( !_Heap_Is_block_in_heap( heap, next_block ) ) {
362      (*printer)(
363        source,
364        true,
365        "block 0x%08x: next block 0x%08x not in heap\n",
366        block,
367        next_block
368      );
369     
370      return false;
371    }
372
373    if ( !_Heap_Is_aligned( block_size, page_size ) ) {
374      (*printer)(
375        source,
376        true,
377        "block 0x%08x: block size %u not page aligned\n",
378        block,
379        block_size
380      );
381     
382      return false;
383    }
384
385    if ( block_size < min_block_size ) {
386      (*printer)(
387        source,
388        true,
389        "block 0x%08x: size %u < min block size %u\n",
390        block,
391        block_size,
392        min_block_size
393      );
394     
395      return false;
396    }
397
398    if ( next_block_begin <= block_begin ) {
399      (*printer)(
400        source,
401        true,
402        "block 0x%08x: next block 0x%08x is not a successor\n",
403        block,
404        next_block
405      );
406     
407      return false;
408    }
409   
410    if ( !_Heap_Is_prev_used( next_block ) ) {
411      if ( !_Heap_Walk_check_free_block( source, printer, heap, block ) ) {
412        return false;
413      }
414    }
415
416    block = next_block;
417  }
418
419  return true;
420}
Note: See TracBrowser for help on using the repository browser.