source: rtems/testsuites/libtests/rbheap01/init.c @ e752630

4.115
Last change on this file since e752630 was e752630, checked in by Sebastian Huber <sebastian.huber@…>, on 04/10/12 at 09:19:39

rbheap: New files

In the Red-Black Tree Heap the administration data structures are not
contained in the managed memory area. This can be used for example in a
task stack allocator which protects the task stacks from access by other
tasks.
  • Property mode set to 100644
File size: 11.0 KB
Line 
1/*
2 * Copyright (c) 2012 embedded brains GmbH.  All rights reserved.
3 *
4 *  embedded brains GmbH
5 *  Obere Lagerstr. 30
6 *  82178 Puchheim
7 *  Germany
8 *  <rtems@embedded-brains.de>
9 *
10 * The license and distribution terms for this file may be
11 * found in the file LICENSE in this distribution or at
12 * http://www.rtems.com/license/LICENSE.
13 */
14
15#ifdef HAVE_CONFIG_H
16  #include "config.h"
17#endif
18
19#include "tmacros.h"
20
21#include <rtems.h>
22#include <rtems/rbheap.h>
23
24#define PAGE_SIZE 1024
25
26#define PAGE_COUNT 8
27
28static char area [PAGE_SIZE * PAGE_COUNT + PAGE_SIZE - 1];
29
30static rtems_rbheap_page pages [PAGE_COUNT];
31
32static void extend_page_pool(rtems_rbheap_control *control)
33{
34  rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control);
35
36  rtems_rbheap_set_extend_page_pool(
37    control,
38    rtems_rbheap_extend_page_pool_never
39  );
40
41  rtems_chain_initialize(
42    pool_chain,
43    pages,
44    PAGE_COUNT,
45    sizeof(pages [0])
46  );
47}
48
49static uintptr_t idx(const rtems_rbheap_page *page)
50{
51  uintptr_t base = (uintptr_t) area;
52  uintptr_t excess = base % PAGE_SIZE;
53
54  if (excess > 0) {
55    base += PAGE_SIZE - excess;
56  }
57
58  return (page->begin - base) / PAGE_SIZE;
59}
60
61typedef struct {
62  const uintptr_t *index_current;
63  const uintptr_t *index_end;
64  const bool *free_current;
65  const bool *free_end;
66} page_visitor_context;
67
68static bool page_visitor(
69  const RBTree_Node *node,
70  RBTree_Direction dir,
71  void *visitor_arg
72)
73{
74  rtems_rbheap_page *page = rtems_rbheap_page_of_node(node);
75  page_visitor_context *context = visitor_arg;
76
77  rtems_test_assert(context->index_current != context->index_end);
78  rtems_test_assert(context->free_current != context->free_end);
79
80  rtems_test_assert(idx(page) == *context->index_current);
81  rtems_test_assert(rtems_rbheap_is_page_free(page) == *context->free_current);
82
83  ++context->index_current;
84  ++context->free_current;
85
86  return false;
87}
88
89static void test_init_page_alignment(void)
90{
91  rtems_status_code sc = RTEMS_SUCCESSFUL;
92  rtems_rbheap_control control;
93
94  sc = rtems_rbheap_initialize(
95    &control,
96    area,
97    sizeof(area),
98    0,
99    extend_page_pool,
100    NULL
101  );
102  rtems_test_assert(sc == RTEMS_INVALID_NUMBER);
103}
104
105static void test_init_begin_greater_than_end(void)
106{
107  rtems_status_code sc = RTEMS_SUCCESSFUL;
108  rtems_rbheap_control control;
109
110  sc = rtems_rbheap_initialize(
111    &control,
112    (void *) PAGE_SIZE,
113    (uintptr_t) -PAGE_SIZE,
114    PAGE_SIZE,
115    extend_page_pool,
116    NULL
117  );
118  rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
119}
120
121static void test_init_begin_greater_than_aligned_begin(void)
122{
123  rtems_status_code sc = RTEMS_SUCCESSFUL;
124  rtems_rbheap_control control;
125
126  sc = rtems_rbheap_initialize(
127    &control,
128    (void *) -(PAGE_SIZE / 2),
129    PAGE_SIZE,
130    PAGE_SIZE,
131    extend_page_pool,
132    NULL
133  );
134  rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
135}
136
137static void test_init_aligned_begin_greater_than_aligned_end(void)
138{
139  rtems_status_code sc = RTEMS_SUCCESSFUL;
140  rtems_rbheap_control control;
141
142  sc = rtems_rbheap_initialize(
143    &control,
144    (void *) PAGE_SIZE,
145    PAGE_SIZE / 2,
146    PAGE_SIZE,
147    extend_page_pool,
148    NULL
149  );
150  rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
151}
152
153static void test_init_empty_page_pool(void)
154{
155  rtems_status_code sc = RTEMS_SUCCESSFUL;
156  rtems_rbheap_control control;
157
158  sc = rtems_rbheap_initialize(
159    &control,
160    (void *) PAGE_SIZE,
161    PAGE_SIZE,
162    PAGE_SIZE,
163    rtems_rbheap_extend_page_pool_never,
164    NULL
165  );
166  rtems_test_assert(sc == RTEMS_NO_MEMORY);
167}
168
169static void test_page_tree(
170  const rtems_rbheap_control *control,
171  const uintptr_t *index_begin,
172  const uintptr_t *index_end,
173  const bool *free_begin,
174  const bool *free_end
175)
176{
177  page_visitor_context context = {
178    .index_current = index_begin,
179    .index_end = index_end,
180    .free_current = free_begin,
181    .free_end = free_end
182  };
183
184  _RBTree_Iterate_unprotected(
185    &control->page_tree,
186    RBT_RIGHT,
187    page_visitor,
188    &context
189  );
190}
191
192#define TEST_PAGE_TREE(control, indices, frees) \
193  test_page_tree( \
194    control, \
195    indices, \
196    &indices [sizeof(indices) / sizeof(indices [0])], \
197    frees, \
198    &frees [sizeof(frees) / sizeof(frees [0])] \
199  )
200
201static void test_init_successful(rtems_rbheap_control *control)
202{
203  static const uintptr_t indices [] = {
204    0
205  };
206  static const bool frees [] = {
207    true
208  };
209
210  rtems_status_code sc = RTEMS_SUCCESSFUL;
211
212  sc = rtems_rbheap_initialize(
213    control,
214    area,
215    sizeof(area),
216    PAGE_SIZE,
217    extend_page_pool,
218    NULL
219  );
220  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
221
222  TEST_PAGE_TREE(control, indices, frees);
223}
224
225static void test_alloc_and_free_one(void)
226{
227  static const uintptr_t indices_0 [] = {
228    0,
229    PAGE_COUNT - 1
230  };
231  static const bool frees_0 [] = {
232    true,
233    false
234  };
235  static const uintptr_t indices_1 [] = {
236    0
237  };
238  static const bool frees_1 [] = {
239    true,
240  };
241
242  rtems_status_code sc = RTEMS_SUCCESSFUL;
243  rtems_rbheap_control control;
244  void *ptr = NULL;
245
246  test_init_successful(&control);
247
248  ptr = rtems_rbheap_allocate(&control, PAGE_SIZE);
249  rtems_test_assert(ptr != NULL);
250
251  TEST_PAGE_TREE(&control, indices_0, frees_0);
252
253  sc = rtems_rbheap_free(&control, ptr);
254  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
255
256  TEST_PAGE_TREE(&control, indices_1, frees_1);
257}
258
259static void test_alloc_zero(void)
260{
261  static const uintptr_t indices [] = {
262    0
263  };
264  static const bool frees [] = {
265    true
266  };
267
268  rtems_rbheap_control control;
269  void *ptr = NULL;
270
271  test_init_successful(&control);
272
273  ptr = rtems_rbheap_allocate(&control, 0);
274  rtems_test_assert(ptr == NULL);
275
276  TEST_PAGE_TREE(&control, indices, frees);
277}
278
279static void test_alloc_huge_page(void)
280{
281  static const uintptr_t indices [] = {
282    0
283  };
284  static const bool frees [] = {
285    true
286  };
287
288  rtems_rbheap_control control;
289  void *ptr = NULL;
290
291  test_init_successful(&control);
292
293  ptr = rtems_rbheap_allocate(&control, (PAGE_COUNT + 1) * PAGE_SIZE);
294  rtems_test_assert(ptr == NULL);
295
296  TEST_PAGE_TREE(&control, indices, frees);
297}
298
299static void test_alloc_one_page(void)
300{
301  static const uintptr_t indices_0 [] = {
302    0
303  };
304  static const bool frees_0 [] = {
305    false
306  };
307  static const uintptr_t indices_1 [] = {
308    0
309  };
310  static const bool frees_1 [] = {
311    true,
312  };
313
314  rtems_status_code sc = RTEMS_SUCCESSFUL;
315  rtems_rbheap_control control;
316  void *ptr = NULL;
317
318  test_init_successful(&control);
319
320  ptr = rtems_rbheap_allocate(&control, PAGE_COUNT * PAGE_SIZE);
321  rtems_test_assert(ptr != NULL);
322
323  TEST_PAGE_TREE(&control, indices_0, frees_0);
324
325  sc = rtems_rbheap_free(&control, ptr);
326  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
327
328  TEST_PAGE_TREE(&control, indices_1, frees_1);
329}
330
331static void test_alloc_many_pages(void)
332{
333  static const uintptr_t indices_0 [] = {
334    0,
335    1,
336    2,
337    3,
338    4,
339    5,
340    6,
341    7
342  };
343  static const bool frees_0 [] = {
344    false,
345    false,
346    false,
347    false,
348    false,
349    false,
350    false,
351    false
352  };
353  static const uintptr_t indices_1 [] = {
354    0
355  };
356  static const bool frees_1 [] = {
357    true,
358  };
359
360  rtems_status_code sc = RTEMS_SUCCESSFUL;
361  rtems_rbheap_control control;
362  void *ptr [PAGE_COUNT];
363  void *null = NULL;
364  int i = 0;
365
366  test_init_successful(&control);
367
368  for (i = 0; i < PAGE_COUNT; ++i) {
369    ptr [i] = rtems_rbheap_allocate(&control, PAGE_SIZE);
370    rtems_test_assert(ptr [i] != NULL);
371  }
372
373  TEST_PAGE_TREE(&control, indices_0, frees_0);
374
375  null = rtems_rbheap_allocate(&control, PAGE_SIZE);
376  rtems_test_assert(null == NULL);
377
378  TEST_PAGE_TREE(&control, indices_0, frees_0);
379
380  for (i = 0; i < PAGE_COUNT; ++i) {
381    sc = rtems_rbheap_free(&control, ptr [i]);
382    rtems_test_assert(sc == RTEMS_SUCCESSFUL);
383  }
384
385  TEST_PAGE_TREE(&control, indices_1, frees_1);
386}
387
388static void test_free_invalid(void)
389{
390  rtems_status_code sc = RTEMS_SUCCESSFUL;
391  rtems_rbheap_control control;
392
393  test_init_successful(&control);
394
395  sc = rtems_rbheap_free(&control, NULL);
396  rtems_test_assert(sc == RTEMS_INVALID_ID);
397}
398
399static void test_free_double(void)
400{
401  rtems_status_code sc = RTEMS_SUCCESSFUL;
402  rtems_rbheap_control control;
403  void *ptr = NULL;
404
405  test_init_successful(&control);
406
407  ptr = rtems_rbheap_allocate(&control, PAGE_COUNT * PAGE_SIZE);
408  rtems_test_assert(ptr != NULL);
409
410  sc = rtems_rbheap_free(&control, ptr);
411  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
412
413  sc = rtems_rbheap_free(&control, ptr);
414  rtems_test_assert(sc == RTEMS_INCORRECT_STATE);
415}
416
417enum {
418  LOW,
419  LEFT,
420  MIDDLE,
421  RIGHT,
422  HIGH
423};
424
425static void test_free_merge_left_or_right(bool left)
426{
427  static const uintptr_t indices_0 [] = {
428    0,
429    3,
430    4,
431    5,
432    6,
433    7
434  };
435  static const bool frees_0 [] = {
436    true,
437    false,
438    false,
439    false,
440    false,
441    false
442  };
443  static const uintptr_t indices_1_left [] = {
444    0,
445    3,
446    4,
447    5,
448    6,
449    7
450  };
451  static const bool frees_1_left [] = {
452    true,
453    false,
454    true,
455    false,
456    false,
457    false
458  };
459  static const uintptr_t indices_1_right [] = {
460    0,
461    3,
462    4,
463    5,
464    6,
465    7
466  };
467  static const bool frees_1_right [] = {
468    true,
469    false,
470    false,
471    false,
472    true,
473    false
474  };
475  static const uintptr_t indices_2_left [] = {
476    0,
477    3,
478    4,
479    6,
480    7
481  };
482  static const bool frees_2_left [] = {
483    true,
484    false,
485    true,
486    false,
487    false
488  };
489  static const uintptr_t indices_2_right [] = {
490    0,
491    3,
492    4,
493    5,
494    7
495  };
496  static const bool frees_2_right [] = {
497    true,
498    false,
499    false,
500    true,
501    false
502  };
503
504  rtems_status_code sc = RTEMS_SUCCESSFUL;
505  rtems_rbheap_control control;
506  void *ptr [HIGH + 1];
507  int dir = left ? LEFT : RIGHT;
508  int i = 0;
509
510  test_init_successful(&control);
511
512  for (i = sizeof(ptr) / sizeof(ptr [0]) - 1; i >= 0; --i) {
513    ptr [i] = rtems_rbheap_allocate(&control, PAGE_SIZE);
514    rtems_test_assert(ptr [i] != NULL);
515  }
516
517  TEST_PAGE_TREE(&control, indices_0, frees_0);
518
519  sc = rtems_rbheap_free(&control, ptr [dir]);
520  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
521
522  if (left) {
523    TEST_PAGE_TREE(&control, indices_1_left, frees_1_left);
524  } else {
525    TEST_PAGE_TREE(&control, indices_1_right, frees_1_right);
526  }
527
528  sc = rtems_rbheap_free(&control, ptr [MIDDLE]);
529  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
530
531  if (left) {
532    TEST_PAGE_TREE(&control, indices_2_left, frees_2_left);
533  } else {
534    TEST_PAGE_TREE(&control, indices_2_right, frees_2_right);
535  }
536}
537
538static void Init(rtems_task_argument arg)
539{
540  puts("\n\n*** TEST RBHEAP 1 ***");
541
542  test_init_page_alignment();
543  test_init_begin_greater_than_end();
544  test_init_begin_greater_than_aligned_begin();
545  test_init_aligned_begin_greater_than_aligned_end();
546  test_init_empty_page_pool();
547  test_alloc_and_free_one();
548  test_alloc_zero();
549  test_alloc_huge_page();
550  test_alloc_one_page();
551  test_alloc_many_pages();
552  test_free_invalid();
553  test_free_double();
554  test_free_merge_left_or_right(true);
555  test_free_merge_left_or_right(false);
556
557  puts("*** END OF TEST RBHEAP 1 ***");
558
559  rtems_test_exit(0);
560}
561
562#define CONFIGURE_APPLICATION_NEEDS_CLOCK_DRIVER
563#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
564
565#define CONFIGURE_MAXIMUM_TASKS 1
566
567#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
568
569#define CONFIGURE_INIT
570
571#include <rtems/confdefs.h>
Note: See TracBrowser for help on using the repository browser.