Subversion Repositories HelenOS

Rev

Rev 4597 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
4597 decky 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
}