← Back to branch summary

~galfy/helenos/bird-port-mainline

« back to all changes in this revision

Viewing changes to uspace/app/tester/mm/malloc1.c

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

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