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