1 /*
2  *  Copyright (c) 2017, The OpenThread Authors.
3  *  All rights reserved.
4  *
5  *  Redistribution and use in source and binary forms, with or without
6  *  modification, are permitted provided that the following conditions are met:
7  *  1. Redistributions of source code must retain the above copyright
8  *     notice, this list of conditions and the following disclaimer.
9  *  2. Redistributions in binary form must reproduce the above copyright
10  *     notice, this list of conditions and the following disclaimer in the
11  *     documentation and/or other materials provided with the distribution.
12  *  3. Neither the name of the copyright holder nor the
13  *     names of its contributors may be used to endorse or promote products
14  *     derived from this software without specific prior written permission.
15  *
16  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17  *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19  *  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20  *  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21  *  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22  *  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23  *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24  *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25  *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26  *  POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #include <openthread/config.h>
30 
31 #include "core/utils/heap.hpp"
32 
33 #include <stdlib.h>
34 
35 #include "common/debug.hpp"
36 #include "crypto/aes_ccm.hpp"
37 
38 #include "test_platform.h"
39 #include "test_util.h"
40 
41 namespace ot {
42 
43 #if !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
44 
45 /**
46  * Verifies single variable allocating and freeing.
47  *
48  */
TestAllocateSingle(void)49 void TestAllocateSingle(void)
50 {
51     ot::Utils::Heap heap;
52 
53     const size_t totalSize = heap.GetFreeSize();
54 
55     {
56         void *p = heap.CAlloc(1, 0);
57         VerifyOrQuit(p == nullptr && totalSize == heap.GetFreeSize(), "TestAllocateSingle allocate 1 x 0 byte failed!");
58         heap.Free(p);
59 
60         p = heap.CAlloc(0, 1);
61         VerifyOrQuit(p == nullptr && totalSize == heap.GetFreeSize(), "TestAllocateSingle allocate 0 x 1 byte failed!");
62         heap.Free(p);
63     }
64 
65     for (size_t size = 1; size <= heap.GetCapacity(); ++size)
66     {
67         printf("%s allocating %zu bytes...\n", __func__, size);
68         void *p = heap.CAlloc(1, size);
69         VerifyOrQuit(p != nullptr && !heap.IsClean() && heap.GetFreeSize() + size <= totalSize, "allocating failed!");
70         memset(p, 0xff, size);
71         heap.Free(p);
72         VerifyOrQuit(heap.IsClean() && heap.GetFreeSize() == totalSize, "freeing failed!\n");
73     }
74 }
75 
76 /**
77  * Verifies randomly allocating and freeing variables.
78  *
79  * @param[in]   aSizeLimit  The maximum allocation size.
80  * @param[in]   aSeed       The seed for generating random sizes.
81  *
82  */
TestAllocateRandomly(size_t aSizeLimit,unsigned int aSeed)83 void TestAllocateRandomly(size_t aSizeLimit, unsigned int aSeed)
84 {
85     struct Node
86     {
87         Node  *mNext;
88         size_t mSize;
89     };
90 
91     ot::Utils::Heap heap;
92     Node            head;
93     size_t          nnodes = 0;
94 
95     srand(aSeed);
96 
97     const size_t totalSize = heap.GetFreeSize();
98     Node        *last      = &head;
99 
100     do
101     {
102         size_t size = sizeof(Node) + static_cast<size_t>(rand()) % aSizeLimit;
103         printf("TestAllocateRandomly allocating %zu bytes...\n", size);
104         last->mNext = static_cast<Node *>(heap.CAlloc(1, size));
105 
106         // No more memory for allocation.
107         if (last->mNext == nullptr)
108         {
109             break;
110         }
111 
112         VerifyOrQuit(last->mNext->mNext == nullptr, "TestAllocateRandomly memory not initialized to zero!");
113         last        = last->mNext;
114         last->mSize = size;
115         ++nnodes;
116 
117         // 50% probability to randomly free a node.
118         size_t freeIndex = static_cast<size_t>(rand()) % (nnodes * 2);
119 
120         if (freeIndex > nnodes)
121         {
122             freeIndex /= 2;
123 
124             Node *prev = &head;
125 
126             while (freeIndex--)
127             {
128                 prev = prev->mNext;
129             }
130 
131             Node *curr = prev->mNext;
132             printf("TestAllocateRandomly freeing %zu bytes...\n", curr->mSize);
133             prev->mNext = curr->mNext;
134             heap.Free(curr);
135 
136             if (last == curr)
137             {
138                 last = prev;
139             }
140 
141             --nnodes;
142         }
143     } while (true);
144 
145     last = head.mNext;
146 
147     while (last)
148     {
149         Node *next = last->mNext;
150         printf("TestAllocateRandomly freeing %zu bytes...\n", last->mSize);
151         heap.Free(last);
152         last = next;
153     }
154 
155     VerifyOrQuit(heap.IsClean() && heap.GetFreeSize() == totalSize,
156                  "TestAllocateRandomly heap not clean after freeing all!");
157 }
158 
159 /**
160  * Verifies allocating and free multiple variables.
161  */
TestAllocateMultiple(void)162 void TestAllocateMultiple(void)
163 {
164     for (unsigned int seed = 0; seed < 10; ++seed)
165     {
166         size_t sizeLimit = (1 << seed);
167         printf("TestAllocateRandomly(%zu, %u)...\n", sizeLimit, seed);
168         TestAllocateRandomly(sizeLimit, seed);
169     }
170 }
171 
RunTimerTests(void)172 void RunTimerTests(void)
173 {
174     TestAllocateSingle();
175     TestAllocateMultiple();
176 }
177 
178 #endif // !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
179 
180 } // namespace ot
181 
main(void)182 int main(void)
183 {
184 #if !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
185     ot::RunTimerTests();
186     printf("All tests passed\n");
187 #endif // !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
188     return 0;
189 }
190