source: soft/giet_vm/giet_libs/malloc.h @ 786

Last change on this file since 786 was 781, checked in by alain, 9 years ago

Fixing two bugs:
1) In the string library: the strcpy() function must copy
the terminating NUL character in the destination buffer.
2) In the malloc library: the free() function must reset
the entry associated to the released buffer in the alloc[array].

  • Property svn:executable set to *
File size: 5.2 KB
Line 
1////////////////////////////////////////////////////////////////////////////////
2// File     : malloc.h
3// Date     : 05/03/2013
4// Author   : Jean-Baptiste Bréjon / alain greiner
5// Copyright (c) UPMC-LIP6
6////////////////////////////////////////////////////////////////////////////////
7// Initialisation policy:
8//   The user application must initialize the heap(x,y) structure before
9//   using the malloc() or remote_malloc() functions, and this initialization
10//   must be done by a single task.
11////////////////////////////////////////////////////////////////////////////////
12// Free blocks organisation:
13// - All free blocks have a size that is a power of 2, larger or equal
14//   to MIN_BLOCK_SIZE (typically 64 bytes).
15// - All free blocks are aligned.
16// - They are pre-classed in NB_SIZES linked lists, where all blocks in a
17//   given list have the same size.
18// - The NEXT pointer implementing those linked lists is written
19//   in the 4 first bytes of the block itself, using the unsigned int type.
20// - The pointers on the first free block for each size are stored in an
21//   array of pointers free[32] in the heap(x,y) descriptor.
22////////////////////////////////////////////////////////////////////////////////
23// Allocation policy:
24// - The block size required by the user can be any value, but the allocated
25//   block size can be larger than the requested size:
26// - The allocator computes actual_size, that is the smallest power of 2
27//   value larger or equal to the requested size AND larger or equal to
28//   MIN_BLOCK_SIZE.
29// - It pop the linked list of free blocks corresponding to actual_size,
30//   and returns the block B if the list[actual_size] is not empty.
31// - If the list[actual_size] is empty, it pop the list[actual_size * 2].
32//   If a block B' is found, it break this block in 2 B/2 blocks, returns
33//   the first B/2 block and push the other B/2 block into list[actual_size].
34// - If the list[actual_size * 2] is empty, it pop the list[actual_size * 4].
35//   If a block B is found, it break this block in 3 blocks B/4, B/4 and B/2,
36//   returns the first B/4 block, push the other blocks B/4 and B/2 into
37//   the proper lists. etc...
38// - If no block satisfying the request is available it returns a failure
39//   (NULL pointer).
40// - This allocation policy has the nice following property:
41//   If the heap segment is aligned (the heap_base is a multiple of the
42//   heap_size), all allocated blocks are aligned on the actual_size.
43////////////////////////////////////////////////////////////////////////////////
44// Free policy:
45// - Each allocated block is registered in an alloc[] array of unsigned char.
46// - This registration is required by the free() operation, because the size
47//   of the allocated block must be obtained from the base address of the block. 
48// - The number of entries in this array is equal to the max number
49//   of allocated block is : heap_size / MIN_BLOCK_SIZE.
50// - For each allocated block, the value registered in the alloc[] array
51//   is log2( size_of_allocated_block ).
52// - The index in this array is computed from the allocated block base address:
53//      index = (block_base - heap_base) / MIN_BLOCK_SIZE
54// - The alloc[] array is stored at the end of heap segment. This consume
55//   (1 / MIN_BLOCK_SIZE) of the total heap storage capacity.
56////////////////////////////////////////////////////////////////////////////////
57
58#ifndef _MALLOC_H_
59#define _MALLOC_H_
60
61#include "giet_config.h"
62#include "user_lock.h"
63
64////////////////////////////////////////////////////////////////////////////////
65//  magic number indicating that heap(x,y) has been initialized.
66////////////////////////////////////////////////////////////////////////////////
67
68#define HEAP_INITIALIZED    0xDEADBEEF
69
70#define MIN_BLOCK_SIZE      0x40
71
72////////////////////////////////////////////////////////////////////////////////
73// heap(x,y) descriptor (one per cluster)
74////////////////////////////////////////////////////////////////////////////////
75
76typedef struct giet_heap_s
77{
78    user_lock_t    lock;            // lock protecting exclusive access
79    unsigned int   init;            // initialised <=> value == HEAP_INITIALIZED
80    unsigned int   x;               // cluster X coordinate
81    unsigned int   y;               // cluster Y coordinate
82    unsigned int   heap_base;       // heap base address
83    unsigned int   heap_size;       // heap size (bytes)
84    unsigned int   alloc_base;      // alloc[] array base address
85    unsigned int   alloc_size;      // alloc[] array size (bytes)
86    unsigned int   free[32];        // array of base addresses of free blocks
87                                    // (address of first block of a given size)
88} giet_heap_t;
89
90///////// user functions /////////////////
91
92extern void heap_init( unsigned int x,
93                       unsigned int y );
94
95extern void * malloc( int size );
96extern void * calloc( int nbmem,
97                      int size );
98
99extern void * remote_malloc( int size, 
100                             unsigned int x,
101                             unsigned int y );
102
103extern void free(void * ptr);
104
105#endif
106
107// Local Variables:
108// tab-width: 4
109// c-basic-offset: 4
110// c-file-offsets:((innamespace . 0)(inline-open . 0))
111// indent-tabs-mode: nil
112// End:
113// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
114
Note: See TracBrowser for help on using the repository browser.