Rev 4597 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 4597 | Rev 4687 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (c) 2009 Martin Decky |
2 | * Copyright (c) 2009 Martin Decky |
3 | * Copyright (c) 2009 Tomas Bures |
3 | * Copyright (c) 2009 Tomas Bures |
4 | * Copyright (c) 2009 Lubomir Bulej |
4 | * Copyright (c) 2009 Lubomir Bulej |
5 | * All rights reserved. |
5 | * All rights reserved. |
6 | * |
6 | * |
7 | * Redistribution and use in source and binary forms, with or without |
7 | * Redistribution and use in source and binary forms, with or without |
8 | * modification, are permitted provided that the following conditions |
8 | * modification, are permitted provided that the following conditions |
9 | * are met: |
9 | * are met: |
10 | * |
10 | * |
11 | * - Redistributions of source code must retain the above copyright |
11 | * - Redistributions of source code must retain the above copyright |
12 | * notice, this list of conditions and the following disclaimer. |
12 | * notice, this list of conditions and the following disclaimer. |
13 | * - Redistributions in binary form must reproduce the above copyright |
13 | * - Redistributions in binary form must reproduce the above copyright |
14 | * notice, this list of conditions and the following disclaimer in the |
14 | * notice, this list of conditions and the following disclaimer in the |
15 | * documentation and/or other materials provided with the distribution. |
15 | * documentation and/or other materials provided with the distribution. |
16 | * - The name of the author may not be used to endorse or promote products |
16 | * - The name of the author may not be used to endorse or promote products |
17 | * derived from this software without specific prior written permission. |
17 | * derived from this software without specific prior written permission. |
18 | * |
18 | * |
19 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
19 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
20 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
20 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
21 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
21 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
22 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
22 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
23 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
23 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
24 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
24 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
25 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
25 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
26 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
26 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
27 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
27 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
28 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
28 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
29 | */ |
29 | */ |
30 | 30 | ||
31 | #include <stdio.h> |
31 | #include <stdio.h> |
32 | #include <unistd.h> |
32 | #include <unistd.h> |
33 | #include <stdlib.h> |
33 | #include <stdlib.h> |
34 | #include <malloc.h> |
34 | #include <malloc.h> |
35 | #include "../tester.h" |
35 | #include "../tester.h" |
36 | 36 | ||
37 | /* |
37 | /* |
38 | * The test consists of several phases which differ in the size of blocks |
38 | * The test consists of several phases which differ in the size of blocks |
39 | * they allocate. The size of blocks is given as a range of minimum and |
39 | * they allocate. The size of blocks is given as a range of minimum and |
40 | * maximum allowed size. Each of the phases is divided into 3 subphases which |
40 | * maximum allowed size. Each of the phases is divided into 3 subphases which |
41 | * differ in the probability of free and alloc actions. Second subphase is |
41 | * differ in the probability of free and alloc actions. Second subphase is |
42 | * started when malloc returns 'out of memory' or when MAX_ALLOC is reached. |
42 | * started when malloc returns 'out of memory' or when MAX_ALLOC is reached. |
43 | * Third subphase is started after a given number of cycles. The third subphase |
43 | * Third subphase is started after a given number of cycles. The third subphase |
44 | * as well as the whole phase ends when all memory blocks are released. |
44 | * as well as the whole phase ends when all memory blocks are released. |
45 | */ |
45 | */ |
46 | 46 | ||
47 | /** |
47 | /** |
48 | * sizeof_array |
48 | * sizeof_array |
49 | * @array array to determine the size of |
49 | * @array array to determine the size of |
50 | * |
50 | * |
51 | * Returns the size of @array in array elements. |
51 | * Returns the size of @array in array elements. |
52 | */ |
52 | */ |
53 | #define sizeof_array(array) \ |
53 | #define sizeof_array(array) \ |
54 | (sizeof(array) / sizeof((array)[0])) |
54 | (sizeof(array) / sizeof((array)[0])) |
55 | 55 | ||
56 | #define MAX_ALLOC (16 * 1024 * 1024) |
56 | #define MAX_ALLOC (16 * 1024 * 1024) |
57 | 57 | ||
58 | /* |
58 | /* |
59 | * Subphase control structures: subphase termination conditions, |
59 | * Subphase control structures: subphase termination conditions, |
60 | * probabilities of individual actions, subphase control structure. |
60 | * probabilities of individual actions, subphase control structure. |
61 | */ |
61 | */ |
62 | 62 | ||
63 | typedef struct { |
63 | typedef struct { |
64 | unsigned int max_cycles; |
64 | unsigned int max_cycles; |
65 | unsigned int no_memory; |
65 | unsigned int no_memory; |
66 | unsigned int no_allocated; |
66 | unsigned int no_allocated; |
67 | } sp_term_cond_s; |
67 | } sp_term_cond_s; |
68 | 68 | ||
69 | typedef struct { |
69 | typedef struct { |
70 | unsigned int alloc; |
70 | unsigned int alloc; |
71 | unsigned int free; |
71 | unsigned int free; |
72 | } sp_action_prob_s; |
72 | } sp_action_prob_s; |
73 | 73 | ||
74 | typedef struct { |
74 | typedef struct { |
75 | char *name; |
75 | char *name; |
76 | sp_term_cond_s cond; |
76 | sp_term_cond_s cond; |
77 | sp_action_prob_s prob; |
77 | sp_action_prob_s prob; |
78 | } subphase_s; |
78 | } subphase_s; |
79 | 79 | ||
80 | 80 | ||
81 | /* |
81 | /* |
82 | * Phase control structures: The minimum and maximum block size that |
82 | * Phase control structures: The minimum and maximum block size that |
83 | * can be allocated during the phase execution, phase control structure. |
83 | * can be allocated during the phase execution, phase control structure. |
84 | */ |
84 | */ |
85 | 85 | ||
86 | typedef struct { |
86 | typedef struct { |
87 | size_t min_block_size; |
87 | size_t min_block_size; |
88 | size_t max_block_size; |
88 | size_t max_block_size; |
89 | } ph_alloc_size_s; |
89 | } ph_alloc_size_s; |
90 | 90 | ||
91 | typedef struct { |
91 | typedef struct { |
92 | char *name; |
92 | char *name; |
93 | ph_alloc_size_s alloc; |
93 | ph_alloc_size_s alloc; |
94 | subphase_s *subphases; |
94 | subphase_s *subphases; |
95 | } phase_s; |
95 | } phase_s; |
96 | 96 | ||
97 | 97 | ||
98 | /* |
98 | /* |
99 | * Subphases are defined separately here. This is for two reasons: |
99 | * Subphases are defined separately here. This is for two reasons: |
100 | * 1) data are not duplicated, 2) we don't have to state beforehand |
100 | * 1) data are not duplicated, 2) we don't have to state beforehand |
101 | * how many subphases a phase contains. |
101 | * how many subphases a phase contains. |
102 | */ |
102 | */ |
103 | static subphase_s subphases_32B[] = { |
103 | static subphase_s subphases_32B[] = { |
104 | { |
104 | { |
105 | .name = "Allocation", |
105 | .name = "Allocation", |
106 | .cond = { |
106 | .cond = { |
107 | .max_cycles = 200, |
107 | .max_cycles = 200, |
108 | .no_memory = 1, |
108 | .no_memory = 1, |
109 | .no_allocated = 0, |
109 | .no_allocated = 0, |
110 | }, |
110 | }, |
111 | .prob = { |
111 | .prob = { |
112 | .alloc = 90, |
112 | .alloc = 90, |
113 | .free = 100 |
113 | .free = 100 |
114 | } |
114 | } |
115 | }, |
115 | }, |
116 | { |
116 | { |
117 | .name = "Alloc/Dealloc", |
117 | .name = "Alloc/Dealloc", |
118 | .cond = { |
118 | .cond = { |
119 | .max_cycles = 200, |
119 | .max_cycles = 200, |
120 | .no_memory = 0, |
120 | .no_memory = 0, |
121 | .no_allocated = 0, |
121 | .no_allocated = 0, |
122 | }, |
122 | }, |
123 | .prob = { |
123 | .prob = { |
124 | .alloc = 50, |
124 | .alloc = 50, |
125 | .free = 100 |
125 | .free = 100 |
126 | } |
126 | } |
127 | }, |
127 | }, |
128 | { |
128 | { |
129 | .name = "Deallocation", |
129 | .name = "Deallocation", |
130 | .cond = { |
130 | .cond = { |
131 | .max_cycles = 0, |
131 | .max_cycles = 0, |
132 | .no_memory = 0, |
132 | .no_memory = 0, |
133 | .no_allocated = 1, |
133 | .no_allocated = 1, |
134 | }, |
134 | }, |
135 | .prob = { |
135 | .prob = { |
136 | .alloc = 10, |
136 | .alloc = 10, |
137 | .free = 100 |
137 | .free = 100 |
138 | } |
138 | } |
139 | } |
139 | } |
140 | }; |
140 | }; |
141 | 141 | ||
142 | static subphase_s subphases_128K[] = { |
142 | static subphase_s subphases_128K[] = { |
143 | { |
143 | { |
144 | .name = "Allocation", |
144 | .name = "Allocation", |
145 | .cond = { |
145 | .cond = { |
146 | .max_cycles = 0, |
146 | .max_cycles = 0, |
147 | .no_memory = 1, |
147 | .no_memory = 1, |
148 | .no_allocated = 0, |
148 | .no_allocated = 0, |
149 | }, |
149 | }, |
150 | .prob = { |
150 | .prob = { |
151 | .alloc = 70, |
151 | .alloc = 70, |
152 | .free = 100 |
152 | .free = 100 |
153 | } |
153 | } |
154 | }, |
154 | }, |
155 | { |
155 | { |
156 | .name = "Alloc/Dealloc", |
156 | .name = "Alloc/Dealloc", |
157 | .cond = { |
157 | .cond = { |
158 | .max_cycles = 30, |
158 | .max_cycles = 30, |
159 | .no_memory = 0, |
159 | .no_memory = 0, |
160 | .no_allocated = 0, |
160 | .no_allocated = 0, |
161 | }, |
161 | }, |
162 | .prob = { |
162 | .prob = { |
163 | .alloc = 50, |
163 | .alloc = 50, |
164 | .free = 100 |
164 | .free = 100 |
165 | } |
165 | } |
166 | }, |
166 | }, |
167 | { |
167 | { |
168 | .name = "Deallocation", |
168 | .name = "Deallocation", |
169 | .cond = { |
169 | .cond = { |
170 | .max_cycles = 0, |
170 | .max_cycles = 0, |
171 | .no_memory = 0, |
171 | .no_memory = 0, |
172 | .no_allocated = 1, |
172 | .no_allocated = 1, |
173 | }, |
173 | }, |
174 | .prob = { |
174 | .prob = { |
175 | .alloc = 30, |
175 | .alloc = 30, |
176 | .free = 100 |
176 | .free = 100 |
177 | } |
177 | } |
178 | } |
178 | } |
179 | }; |
179 | }; |
180 | 180 | ||
181 | static subphase_s subphases_default[] = { |
181 | static subphase_s subphases_default[] = { |
182 | { |
182 | { |
183 | .name = "Allocation", |
183 | .name = "Allocation", |
184 | .cond = { |
184 | .cond = { |
185 | .max_cycles = 0, |
185 | .max_cycles = 0, |
186 | .no_memory = 1, |
186 | .no_memory = 1, |
187 | .no_allocated = 0, |
187 | .no_allocated = 0, |
188 | }, |
188 | }, |
189 | .prob = { |
189 | .prob = { |
190 | .alloc = 90, |
190 | .alloc = 90, |
191 | .free = 100 |
191 | .free = 100 |
192 | } |
192 | } |
193 | }, |
193 | }, |
194 | { |
194 | { |
195 | .name = "Alloc/Dealloc", |
195 | .name = "Alloc/Dealloc", |
196 | .cond = { |
196 | .cond = { |
197 | .max_cycles = 200, |
197 | .max_cycles = 200, |
198 | .no_memory = 0, |
198 | .no_memory = 0, |
199 | .no_allocated = 0, |
199 | .no_allocated = 0, |
200 | }, |
200 | }, |
201 | .prob = { |
201 | .prob = { |
202 | .alloc = 50, |
202 | .alloc = 50, |
203 | .free = 100 |
203 | .free = 100 |
204 | } |
204 | } |
205 | }, |
205 | }, |
206 | { |
206 | { |
207 | .name = "Deallocation", |
207 | .name = "Deallocation", |
208 | .cond = { |
208 | .cond = { |
209 | .max_cycles = 0, |
209 | .max_cycles = 0, |
210 | .no_memory = 0, |
210 | .no_memory = 0, |
211 | .no_allocated = 1, |
211 | .no_allocated = 1, |
212 | }, |
212 | }, |
213 | .prob = { |
213 | .prob = { |
214 | .alloc = 10, |
214 | .alloc = 10, |
215 | .free = 100 |
215 | .free = 100 |
216 | } |
216 | } |
217 | } |
217 | } |
218 | }; |
218 | }; |
219 | 219 | ||
220 | 220 | ||
221 | /* |
221 | /* |
222 | * Phase definitions. |
222 | * Phase definitions. |
223 | */ |
223 | */ |
224 | static phase_s phases[] = { |
224 | static phase_s phases[] = { |
225 | { |
225 | { |
226 | .name = "32 B memory blocks", |
226 | .name = "32 B memory blocks", |
227 | .alloc = { |
227 | .alloc = { |
228 | .min_block_size = 32, |
228 | .min_block_size = 32, |
229 | .max_block_size = 32 |
229 | .max_block_size = 32 |
230 | }, |
230 | }, |
231 | .subphases = subphases_32B |
231 | .subphases = subphases_32B |
232 | }, |
232 | }, |
233 | { |
233 | { |
234 | .name = "128 KB memory blocks", |
234 | .name = "128 KB memory blocks", |
235 | .alloc = { |
235 | .alloc = { |
236 | .min_block_size = 128 * 1024, |
236 | .min_block_size = 128 * 1024, |
237 | .max_block_size = 128 * 1024 |
237 | .max_block_size = 128 * 1024 |
238 | }, |
238 | }, |
239 | .subphases = subphases_128K |
239 | .subphases = subphases_128K |
240 | }, |
240 | }, |
241 | { |
241 | { |
242 | .name = "2500 B memory blocks", |
242 | .name = "2500 B memory blocks", |
243 | .alloc = { |
243 | .alloc = { |
244 | .min_block_size = 2500, |
244 | .min_block_size = 2500, |
245 | .max_block_size = 2500 |
245 | .max_block_size = 2500 |
246 | }, |
246 | }, |
247 | .subphases = subphases_default |
247 | .subphases = subphases_default |
248 | }, |
248 | }, |
249 | { |
249 | { |
250 | .name = "1 B .. 250000 B memory blocks", |
250 | .name = "1 B .. 250000 B memory blocks", |
251 | .alloc = { |
251 | .alloc = { |
252 | .min_block_size = 1, |
252 | .min_block_size = 1, |
253 | .max_block_size = 250000 |
253 | .max_block_size = 250000 |
254 | }, |
254 | }, |
255 | .subphases = subphases_default |
255 | .subphases = subphases_default |
256 | } |
256 | } |
257 | }; |
257 | }; |
258 | 258 | ||
259 | 259 | ||
260 | /* |
260 | /* |
261 | * Global error flag. The flag is set if an error |
261 | * Global error flag. The flag is set if an error |
262 | * is encountered (overlapping blocks, inconsistent |
262 | * is encountered (overlapping blocks, inconsistent |
263 | * block data, etc.) |
263 | * block data, etc.) |
264 | */ |
264 | */ |
265 | static bool error_flag = false; |
265 | static bool error_flag = false; |
266 | 266 | ||
267 | /* |
267 | /* |
268 | * Memory accounting: the amount of allocated memory and the |
268 | * Memory accounting: the amount of allocated memory and the |
269 | * number and list of allocated blocks. |
269 | * number and list of allocated blocks. |
270 | */ |
270 | */ |
271 | static size_t mem_allocated; |
271 | static size_t mem_allocated; |
272 | static size_t mem_blocks_count; |
272 | static size_t mem_blocks_count; |
273 | 273 | ||
274 | static LIST_INITIALIZE(mem_blocks); |
274 | static LIST_INITIALIZE(mem_blocks); |
275 | 275 | ||
276 | typedef struct { |
276 | typedef struct { |
277 | /* Address of the start of the block */ |
277 | /* Address of the start of the block */ |
278 | void *addr; |
278 | void *addr; |
279 | 279 | ||
280 | /* Size of the memory block */ |
280 | /* Size of the memory block */ |
281 | size_t size; |
281 | size_t size; |
282 | 282 | ||
283 | /* link to other blocks */ |
283 | /* link to other blocks */ |
284 | link_t link; |
284 | link_t link; |
285 | } mem_block_s; |
285 | } mem_block_s; |
286 | 286 | ||
287 | typedef mem_block_s *mem_block_t; |
287 | typedef mem_block_s *mem_block_t; |
288 | 288 | ||
289 | 289 | ||
290 | /** init_mem |
290 | /** init_mem |
291 | * |
291 | * |
292 | * Initializes the memory accounting structures. |
292 | * Initializes the memory accounting structures. |
293 | * |
293 | * |
294 | */ |
294 | */ |
295 | static void init_mem(void) |
295 | static void init_mem(void) |
296 | { |
296 | { |
297 | mem_allocated = 0; |
297 | mem_allocated = 0; |
298 | mem_blocks_count = 0; |
298 | mem_blocks_count = 0; |
299 | } |
299 | } |
300 | 300 | ||
301 | 301 | ||
302 | static bool overlap_match(link_t *entry, void *addr, size_t size) |
302 | static bool overlap_match(link_t *entry, void *addr, size_t size) |
303 | { |
303 | { |
304 | mem_block_t mblk = list_get_instance(entry, mem_block_s, link); |
304 | mem_block_t mblk = list_get_instance(entry, mem_block_s, link); |
305 | 305 | ||
306 | /* Entry block control structure <mbeg, mend) */ |
306 | /* Entry block control structure <mbeg, mend) */ |
307 | uint8_t *mbeg = (uint8_t *) mblk; |
307 | uint8_t *mbeg = (uint8_t *) mblk; |
308 | uint8_t *mend = (uint8_t *) mblk + sizeof(mem_block_s); |
308 | uint8_t *mend = (uint8_t *) mblk + sizeof(mem_block_s); |
309 | 309 | ||
310 | /* Entry block memory <bbeg, bend) */ |
310 | /* Entry block memory <bbeg, bend) */ |
311 | uint8_t *bbeg = (uint8_t *) mblk->addr; |
311 | uint8_t *bbeg = (uint8_t *) mblk->addr; |
312 | uint8_t *bend = (uint8_t *) mblk->addr + mblk->size; |
312 | uint8_t *bend = (uint8_t *) mblk->addr + mblk->size; |
313 | 313 | ||
314 | /* Data block <dbeg, dend) */ |
314 | /* Data block <dbeg, dend) */ |
315 | uint8_t *dbeg = (uint8_t *) addr; |
315 | uint8_t *dbeg = (uint8_t *) addr; |
316 | uint8_t *dend = (uint8_t *) addr + size; |
316 | uint8_t *dend = (uint8_t *) addr + size; |
317 | 317 | ||
318 | /* Check for overlaps */ |
318 | /* Check for overlaps */ |
319 | if (((mbeg >= dbeg) && (mbeg < dend)) || |
319 | if (((mbeg >= dbeg) && (mbeg < dend)) || |
320 | ((mend > dbeg) && (mend <= dend)) || |
320 | ((mend > dbeg) && (mend <= dend)) || |
321 | ((bbeg >= dbeg) && (bbeg < dend)) || |
321 | ((bbeg >= dbeg) && (bbeg < dend)) || |
322 | ((bend > dbeg) && (bend <= dend))) |
322 | ((bend > dbeg) && (bend <= dend))) |
323 | return true; |
323 | return true; |
324 | 324 | ||
325 | return false; |
325 | return false; |
326 | } |
326 | } |
327 | 327 | ||
328 | 328 | ||
329 | /** test_overlap |
329 | /** test_overlap |
330 | * |
330 | * |
331 | * Test whether a block starting at @addr overlaps with another, previously |
331 | * Test whether a block starting at @addr overlaps with another, previously |
332 | * allocated memory block or its control structure. |
332 | * allocated memory block or its control structure. |
333 | * |
333 | * |
334 | * @param addr Initial address of the block |
334 | * @param addr Initial address of the block |
335 | * @param size Size of the block |
335 | * @param size Size of the block |
336 | * |
336 | * |
337 | * @return false if the block does not overlap. |
337 | * @return false if the block does not overlap. |
338 | * |
338 | * |
339 | */ |
339 | */ |
340 | static int test_overlap(void *addr, size_t size) |
340 | static int test_overlap(void *addr, size_t size) |
341 | { |
341 | { |
342 | link_t *entry; |
342 | link_t *entry; |
343 | bool fnd = false; |
343 | bool fnd = false; |
344 | 344 | ||
345 | for (entry = mem_blocks.next; entry != &mem_blocks; entry = entry->next) { |
345 | for (entry = mem_blocks.next; entry != &mem_blocks; entry = entry->next) { |
346 | if (overlap_match(entry, addr, size)) { |
346 | if (overlap_match(entry, addr, size)) { |
347 | fnd = true; |
347 | fnd = true; |
348 | break; |
348 | break; |
349 | } |
349 | } |
350 | } |
350 | } |
351 | 351 | ||
352 | return fnd; |
352 | return fnd; |
353 | } |
353 | } |
354 | 354 | ||
355 | 355 | ||
356 | /** checked_malloc |
356 | /** checked_malloc |
357 | * |
357 | * |
358 | * Allocate @size bytes of memory and check whether the chunk comes |
358 | * Allocate @size bytes of memory and check whether the chunk comes |
359 | * from the non-mapped memory region and whether the chunk overlaps |
359 | * from the non-mapped memory region and whether the chunk overlaps |
360 | * with other, previously allocated, chunks. |
360 | * with other, previously allocated, chunks. |
361 | * |
361 | * |
362 | * @param size Amount of memory to allocate |
362 | * @param size Amount of memory to allocate |
363 | * |
363 | * |
364 | * @return NULL if the allocation failed. Sets the global error_flag to |
364 | * @return NULL if the allocation failed. Sets the global error_flag to |
365 | * true if the allocation succeeded but is illegal. |
365 | * true if the allocation succeeded but is illegal. |
366 | * |
366 | * |
367 | */ |
367 | */ |
368 | static void *checked_malloc(size_t size) |
368 | static void *checked_malloc(size_t size) |
369 | { |
369 | { |
370 | void *data; |
370 | void *data; |
371 | 371 | ||
372 | /* Allocate the chunk of memory */ |
372 | /* Allocate the chunk of memory */ |
373 | data = malloc(size); |
373 | data = malloc(size); |
374 | if (data == NULL) |
374 | if (data == NULL) |
375 | return NULL; |
375 | return NULL; |
376 | 376 | ||
377 | /* Check for overlaps with other chunks */ |
377 | /* Check for overlaps with other chunks */ |
378 | if (test_overlap(data, size)) { |
378 | if (test_overlap(data, size)) { |
379 | TPRINTF("\nError: Allocated block overlaps with another " |
379 | TPRINTF("\nError: Allocated block overlaps with another " |
380 | "previously allocated block.\n"); |
380 | "previously allocated block.\n"); |
381 | error_flag = true; |
381 | error_flag = true; |
382 | } |
382 | } |
383 | 383 | ||
384 | return data; |
384 | return data; |
385 | } |
385 | } |
386 | 386 | ||
387 | 387 | ||
388 | /** alloc_block |
388 | /** alloc_block |
389 | * |
389 | * |
390 | * Allocate a block of memory of @size bytes and add record about it into |
390 | * Allocate a block of memory of @size bytes and add record about it into |
391 | * the mem_blocks list. Return a pointer to the block holder structure or |
391 | * the mem_blocks list. Return a pointer to the block holder structure or |
392 | * NULL if the allocation failed. |
392 | * NULL if the allocation failed. |
393 | * |
393 | * |
394 | * If the allocation is illegal (e.g. the memory does not come from the |
394 | * If the allocation is illegal (e.g. the memory does not come from the |
395 | * right region or some of the allocated blocks overlap with others), |
395 | * right region or some of the allocated blocks overlap with others), |
396 | * set the global error_flag. |
396 | * set the global error_flag. |
397 | * |
397 | * |
398 | * @param size Size of the memory block |
398 | * @param size Size of the memory block |
399 | * |
399 | * |
400 | */ |
400 | */ |
401 | static mem_block_t alloc_block(size_t size) |
401 | static mem_block_t alloc_block(size_t size) |
402 | { |
402 | { |
403 | /* Check for allocation limit */ |
403 | /* Check for allocation limit */ |
404 | if (mem_allocated >= MAX_ALLOC) |
404 | if (mem_allocated >= MAX_ALLOC) |
405 | return NULL; |
405 | return NULL; |
406 | 406 | ||
407 | /* Allocate the block holder */ |
407 | /* Allocate the block holder */ |
408 | mem_block_t block = (mem_block_t) checked_malloc(sizeof(mem_block_s)); |
408 | mem_block_t block = (mem_block_t) checked_malloc(sizeof(mem_block_s)); |
409 | if (block == NULL) |
409 | if (block == NULL) |
410 | return NULL; |
410 | return NULL; |
411 | 411 | ||
412 | link_initialize(&block->link); |
412 | link_initialize(&block->link); |
413 | 413 | ||
414 | /* Allocate the block memory */ |
414 | /* Allocate the block memory */ |
415 | block->addr = checked_malloc(size); |
415 | block->addr = checked_malloc(size); |
416 | if (block->addr == NULL) { |
416 | if (block->addr == NULL) { |
417 | free(block); |
417 | free(block); |
418 | return NULL; |
418 | return NULL; |
419 | } |
419 | } |
420 | 420 | ||
421 | block->size = size; |
421 | block->size = size; |
422 | 422 | ||
423 | /* Register the allocated block */ |
423 | /* Register the allocated block */ |
424 | list_append(&block->link, &mem_blocks); |
424 | list_append(&block->link, &mem_blocks); |
425 | mem_allocated += size + sizeof(mem_block_s); |
425 | mem_allocated += size + sizeof(mem_block_s); |
426 | mem_blocks_count++; |
426 | mem_blocks_count++; |
427 | 427 | ||
428 | return block; |
428 | return block; |
429 | } |
429 | } |
430 | 430 | ||
431 | 431 | ||
432 | /** free_block |
432 | /** free_block |
433 | * |
433 | * |
434 | * Free the block of memory and the block control structure allocated by |
434 | * Free the block of memory and the block control structure allocated by |
435 | * alloc_block. Set the global error_flag if an error occurs. |
435 | * alloc_block. Set the global error_flag if an error occurs. |
436 | * |
436 | * |
437 | * @param block Block control structure |
437 | * @param block Block control structure |
438 | * |
438 | * |
439 | */ |
439 | */ |
440 | static void free_block(mem_block_t block) |
440 | static void free_block(mem_block_t block) |
441 | { |
441 | { |
442 | /* Unregister the block */ |
442 | /* Unregister the block */ |
443 | list_remove(&block->link); |
443 | list_remove(&block->link); |
444 | mem_allocated -= block->size + sizeof(mem_block_s); |
444 | mem_allocated -= block->size + sizeof(mem_block_s); |
445 | mem_blocks_count--; |
445 | mem_blocks_count--; |
446 | 446 | ||
447 | /* Free the memory */ |
447 | /* Free the memory */ |
448 | free(block->addr); |
448 | free(block->addr); |
449 | free(block); |
449 | free(block); |
450 | } |
450 | } |
451 | 451 | ||
452 | 452 | ||
453 | /** expected_value |
453 | /** expected_value |
454 | * |
454 | * |
455 | * Compute the expected value of a byte located at @pos in memory |
455 | * Compute the expected value of a byte located at @pos in memory |
456 | * block described by @blk. |
456 | * block described by @blk. |
457 | * |
457 | * |
458 | * @param blk Memory block control structure |
458 | * @param blk Memory block control structure |
459 | * @param pos Position in the memory block data area |
459 | * @param pos Position in the memory block data area |
460 | * |
460 | * |
461 | */ |
461 | */ |
462 | static inline uint8_t expected_value(mem_block_t blk, uint8_t *pos) |
462 | static inline uint8_t expected_value(mem_block_t blk, uint8_t *pos) |
463 | { |
463 | { |
464 | return ((unsigned long) blk ^ (unsigned long) pos) & 0xff; |
464 | return ((unsigned long) blk ^ (unsigned long) pos) & 0xff; |
465 | } |
465 | } |
466 | 466 | ||
467 | 467 | ||
468 | /** fill_block |
468 | /** fill_block |
469 | * |
469 | * |
470 | * Fill the memory block controlled by @blk with data. |
470 | * Fill the memory block controlled by @blk with data. |
471 | * |
471 | * |
472 | * @param blk Memory block control structure |
472 | * @param blk Memory block control structure |
473 | * |
473 | * |
474 | */ |
474 | */ |
475 | static void fill_block(mem_block_t blk) |
475 | static void fill_block(mem_block_t blk) |
476 | { |
476 | { |
477 | uint8_t *pos; |
477 | uint8_t *pos; |
478 | uint8_t *end; |
478 | uint8_t *end; |
479 | 479 | ||
480 | for (pos = blk->addr, end = pos + blk->size; pos < end; pos++) |
480 | for (pos = blk->addr, end = pos + blk->size; pos < end; pos++) |
481 | *pos = expected_value(blk, pos); |
481 | *pos = expected_value(blk, pos); |
482 | } |
482 | } |
483 | 483 | ||
484 | 484 | ||
485 | /** check_block |
485 | /** check_block |
486 | * |
486 | * |
487 | * Check whether the block @blk contains the data it was filled with. |
487 | * Check whether the block @blk contains the data it was filled with. |
488 | * Set global error_flag if an error occurs. |
488 | * Set global error_flag if an error occurs. |
489 | * |
489 | * |
490 | * @param blk Memory block control structure |
490 | * @param blk Memory block control structure |
491 | * |
491 | * |
492 | */ |
492 | */ |
493 | static void check_block(mem_block_t blk) |
493 | static void check_block(mem_block_t blk) |
494 | { |
494 | { |
495 | uint8_t *pos; |
495 | uint8_t *pos; |
496 | uint8_t *end; |
496 | uint8_t *end; |
497 | 497 | ||
498 | for (pos = blk->addr, end = pos + blk->size; pos < end; pos++) { |
498 | for (pos = blk->addr, end = pos + blk->size; pos < end; pos++) { |
499 | if (*pos != expected_value (blk, pos)) { |
499 | if (*pos != expected_value (blk, pos)) { |
500 | TPRINTF("\nError: Corrupted content of a data block.\n"); |
500 | TPRINTF("\nError: Corrupted content of a data block.\n"); |
501 | error_flag = true; |
501 | error_flag = true; |
502 | return; |
502 | return; |
503 | } |
503 | } |
504 | } |
504 | } |
505 | } |
505 | } |
506 | 506 | ||
507 | 507 | ||
508 | static link_t *list_get_nth(link_t *list, unsigned int i) |
508 | static link_t *list_get_nth(link_t *list, unsigned int i) |
509 | { |
509 | { |
510 | unsigned int cnt = 0; |
510 | unsigned int cnt = 0; |
511 | link_t *entry; |
511 | link_t *entry; |
512 | 512 | ||
513 | for (entry = list->next; entry != list; entry = entry->next) { |
513 | for (entry = list->next; entry != list; entry = entry->next) { |
514 | if (cnt == i) |
514 | if (cnt == i) |
515 | return entry; |
515 | return entry; |
516 | 516 | ||
517 | cnt++; |
517 | cnt++; |
518 | } |
518 | } |
519 | 519 | ||
520 | return NULL; |
520 | return NULL; |
521 | } |
521 | } |
522 | 522 | ||
523 | 523 | ||
524 | /** get_random_block |
524 | /** get_random_block |
525 | * |
525 | * |
526 | * Select a random memory block from the list of allocated blocks. |
526 | * Select a random memory block from the list of allocated blocks. |
527 | * |
527 | * |
528 | * @return Block control structure or NULL if the list is empty. |
528 | * @return Block control structure or NULL if the list is empty. |
529 | * |
529 | * |
530 | */ |
530 | */ |
531 | static mem_block_t get_random_block(void) |
531 | static mem_block_t get_random_block(void) |
532 | { |
532 | { |
533 | if (mem_blocks_count == 0) |
533 | if (mem_blocks_count == 0) |
534 | return NULL; |
534 | return NULL; |
535 | 535 | ||
536 | unsigned int blkidx = rand() % mem_blocks_count; |
536 | unsigned int blkidx = rand() % mem_blocks_count; |
537 | link_t *entry = list_get_nth(&mem_blocks, blkidx); |
537 | link_t *entry = list_get_nth(&mem_blocks, blkidx); |
538 | 538 | ||
539 | if (entry == NULL) { |
539 | if (entry == NULL) { |
540 | TPRINTF("\nError: Corrupted list of allocated memory blocks.\n"); |
540 | TPRINTF("\nError: Corrupted list of allocated memory blocks.\n"); |
541 | error_flag = true; |
541 | error_flag = true; |
542 | } |
542 | } |
543 | 543 | ||
544 | return list_get_instance(entry, mem_block_s, link); |
544 | return list_get_instance(entry, mem_block_s, link); |
545 | } |
545 | } |
546 | 546 | ||
547 | 547 | ||
548 | #define RETURN_IF_ERROR \ |
548 | #define RETURN_IF_ERROR \ |
549 | { \ |
549 | { \ |
550 | if (error_flag) \ |
550 | if (error_flag) \ |
551 | return; \ |
551 | return; \ |
552 | } |
552 | } |
553 | 553 | ||
554 | 554 | ||
555 | static void do_subphase(phase_s *phase, subphase_s *subphase) |
555 | static void do_subphase(phase_s *phase, subphase_s *subphase) |
556 | { |
556 | { |
557 | unsigned int cycles; |
557 | unsigned int cycles; |
558 | for (cycles = 0; /* always */; cycles++) { |
558 | for (cycles = 0; /* always */; cycles++) { |
559 | 559 | ||
560 | if (subphase->cond.max_cycles && |
560 | if (subphase->cond.max_cycles && |
561 | cycles >= subphase->cond.max_cycles) { |
561 | cycles >= subphase->cond.max_cycles) { |
562 | /* |
562 | /* |
563 | * We have performed the required number of |
563 | * We have performed the required number of |
564 | * cycles. End the current subphase. |
564 | * cycles. End the current subphase. |
565 | */ |
565 | */ |
566 | break; |
566 | break; |
567 | } |
567 | } |
568 | 568 | ||
569 | /* |
569 | /* |
570 | * Decide whether we alloc or free memory in this step. |
570 | * Decide whether we alloc or free memory in this step. |
571 | */ |
571 | */ |
572 | unsigned int rnd = rand() % 100; |
572 | unsigned int rnd = rand() % 100; |
573 | if (rnd < subphase->prob.alloc) { |
573 | if (rnd < subphase->prob.alloc) { |
574 | /* Compute a random number lying in interval <min_block_size, max_block_size> */ |
574 | /* Compute a random number lying in interval <min_block_size, max_block_size> */ |
575 | int alloc = phase->alloc.min_block_size + |
575 | int alloc = phase->alloc.min_block_size + |
576 | (rand() % (phase->alloc.max_block_size - phase->alloc.min_block_size + 1)); |
576 | (rand() % (phase->alloc.max_block_size - phase->alloc.min_block_size + 1)); |
577 | 577 | ||
578 | mem_block_t blk = alloc_block(alloc); |
578 | mem_block_t blk = alloc_block(alloc); |
579 | RETURN_IF_ERROR; |
579 | RETURN_IF_ERROR; |
580 | 580 | ||
581 | if (blk == NULL) { |
581 | if (blk == NULL) { |
582 | TPRINTF("F(A)"); |
582 | TPRINTF("F(A)"); |
583 | if (subphase->cond.no_memory) { |
583 | if (subphase->cond.no_memory) { |
584 | /* We filled the memory. Proceed to next subphase */ |
584 | /* We filled the memory. Proceed to next subphase */ |
585 | break; |
585 | break; |
586 | } |
586 | } |
587 | 587 | ||
588 | } else { |
588 | } else { |
589 | TPRINTF("A"); |
589 | TPRINTF("A"); |
590 | fill_block(blk); |
590 | fill_block(blk); |
591 | } |
591 | } |
592 | 592 | ||
593 | } else if (rnd < subphase->prob.free) { |
593 | } else if (rnd < subphase->prob.free) { |
594 | mem_block_t blk = get_random_block(); |
594 | mem_block_t blk = get_random_block(); |
595 | if (blk == NULL) { |
595 | if (blk == NULL) { |
596 | TPRINTF("F(R)"); |
596 | TPRINTF("F(R)"); |
597 | if (subphase->cond.no_allocated) { |
597 | if (subphase->cond.no_allocated) { |
598 | /* We free all the memory. Proceed to next subphase. */ |
598 | /* We free all the memory. Proceed to next subphase. */ |
599 | break; |
599 | break; |
600 | } |
600 | } |
601 | 601 | ||
602 | } else { |
602 | } else { |
603 | TPRINTF("R"); |
603 | TPRINTF("R"); |
604 | check_block(blk); |
604 | check_block(blk); |
605 | RETURN_IF_ERROR; |
605 | RETURN_IF_ERROR; |
606 | 606 | ||
607 | free_block(blk); |
607 | free_block(blk); |
608 | RETURN_IF_ERROR; |
608 | RETURN_IF_ERROR; |
609 | } |
609 | } |
610 | } |
610 | } |
611 | } |
611 | } |
612 | 612 | ||
613 | TPRINTF("\n.. finished.\n"); |
613 | TPRINTF("\n.. finished.\n"); |
614 | } |
614 | } |
615 | 615 | ||
616 | 616 | ||
617 | static void do_phase(phase_s *phase) |
617 | static void do_phase(phase_s *phase) |
618 | { |
618 | { |
619 | unsigned int subno; |
619 | unsigned int subno; |
620 | 620 | ||
621 | for (subno = 0; subno < 3; subno++) { |
621 | for (subno = 0; subno < 3; subno++) { |
622 | subphase_s *subphase = & phase->subphases [subno]; |
622 | subphase_s *subphase = & phase->subphases [subno]; |
623 | 623 | ||
624 | TPRINTF(".. Sub-phase %u (%s)\n", subno + 1, subphase->name); |
624 | TPRINTF(".. Sub-phase %u (%s)\n", subno + 1, subphase->name); |
625 | do_subphase(phase, subphase); |
625 | do_subphase(phase, subphase); |
626 | RETURN_IF_ERROR; |
626 | RETURN_IF_ERROR; |
627 | } |
627 | } |
628 | } |
628 | } |
629 | 629 | ||
630 | char *test_malloc1(void) |
630 | char *test_malloc1(void) |
631 | { |
631 | { |
632 | init_mem(); |
632 | init_mem(); |
633 | 633 | ||
634 | unsigned int phaseno; |
634 | unsigned int phaseno; |
635 | for (phaseno = 0; phaseno < sizeof_array(phases); phaseno++) { |
635 | for (phaseno = 0; phaseno < sizeof_array(phases); phaseno++) { |
636 | phase_s *phase = &phases[phaseno]; |
636 | phase_s *phase = &phases[phaseno]; |
637 | 637 | ||
638 | TPRINTF("Entering phase %u (%s)\n", phaseno + 1, phase->name); |
638 | TPRINTF("Entering phase %u (%s)\n", phaseno + 1, phase->name); |
639 | 639 | ||
640 | do_phase(phase); |
640 | do_phase(phase); |
641 | if (error_flag) |
641 | if (error_flag) |
642 | break; |
642 | break; |
643 | 643 | ||
644 | TPRINTF("Phase finished.\n"); |
644 | TPRINTF("Phase finished.\n"); |
645 | } |
645 | } |
646 | 646 | ||
647 | if (error_flag) |
647 | if (error_flag) |
648 | return "Test failed"; |
648 | return "Test failed"; |
649 | 649 | ||
650 | return NULL; |
650 | return NULL; |
651 | } |
651 | } |
652 | 652 |