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

Last change on this file since 445 was 382, checked in by alain, 10 years ago

Major evolution of the malloc library, to provide two new services:

  • all allocated blocks are aligned, and the size is a power of 2.
  • the remote-malloc() function allows the application to explicitely define the cluster(x,y).

We keep only the close-fit allocation policy.
These services were required to implement the distributed SBT barrier.

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