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

Last change on this file since 539 was 461, checked in by alain, 10 years ago

1) replace the "giet_locks.c" library by the "user_lock.c" library (the new library uses a ticket allocator).
2) introduce new syscalls in the stdio.c file, to support the NIC peripheral.
3) modify the MWMR library to use the lock with ticket allocator, and to separate the fifo descriptor and the data buffer.

  • Property svn:executable set to *
File size: 5.1 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 "user_lock.h"
64
65////////////////////////////////////////////////////////////////////////////////
66//  magic number indicating that heap(x,y) has been initialized.
67////////////////////////////////////////////////////////////////////////////////
68
69#define HEAP_INITIALIZED    0xDEADBEEF
70
71#define MIN_BLOCK_SIZE      0x80
72
73////////////////////////////////////////////////////////////////////////////////
74// heap(x,y) descriptor (one per cluster)
75////////////////////////////////////////////////////////////////////////////////
76typedef struct giet_heap_s
77{
78    unsigned int   init;            // initialised <=> value == HEAP_INITIALIZED
79    unsigned int   x;               // cluster X coordinate
80    unsigned int   y;               // cluster Y coordinate
81    unsigned int   heap_base;       // heap base address
82    unsigned int   heap_size;       // heap size (bytes)
83    unsigned int   alloc_base;      // alloc[] array base address
84    unsigned int   alloc_size;      // alloc[] array size (bytes)
85    user_lock_t    lock;            // lock protecting exclusive access
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* malloc( unsigned int size );
93
94extern void* remote_malloc( unsigned int size, 
95                            unsigned int x,
96                            unsigned int y );
97
98extern void free(void * ptr);
99
100
101#endif
102
103// Local Variables:
104// tab-width: 4
105// c-basic-offset: 4
106// c-file-offsets:((innamespace . 0)(inline-open . 0))
107// indent-tabs-mode: nil
108// End:
109// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
110
Note: See TracBrowser for help on using the repository browser.