Changeset 382 for soft/giet_vm/giet_libs/malloc.h

Timestamp:

Aug 7, 2014, 12:23:12 PM (10 years ago)

Author:

alain

Message:

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.

File:

• soft/giet_vm/giet_libs/malloc.h (modified) (1 diff)

soft/giet_vm/giet_libs/malloc.h

@@ -1 @@
-////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
 // File     : malloc.h
 // Date     : 05/03/2013
-// Author   : Jean-Baptiste Bréjon
+// Author   : Jean-Baptiste Bréjon / alain greiner
 // Copyright (c) UPMC-LIP6
-////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+// Initialisation policy:
+//   Each heap(x,y) structure is initialized by the malloc() or remote_malloc()
+//   function, when this function is called the first time.
+//   The function hep_init() initialise the free blocks linked lists as 
+//   explained below.
+////////////////////////////////////////////////////////////////////////////////
+// Free blocks organisation:
+// - All free blocks have a size that is a power of 2, larger or equal
+//   to MIN_BLOCK_SIZE (typically 128 bytes).
+// - All free blocks are aligned.
+// - They are pre-classed in NB_SIZES linked lists, where all blocks in the
+//   same list have the same size. 
+// - The NEXT pointer implementing those linked lists is written 
+//   in the 4 first bytes of the block itself, using the unsigned int type.
+// - The pointers on the first free block for each size are stored in an
+//   array of pointers free[32] in the heap(x,y) descriptor.
+////////////////////////////////////////////////////////////////////////////////
+// Allocation policy:
+// - The block size required by the user can be any value, but the allocated
+//   block size can be larger than the requested size:
+// - The allocator computes actual_size, that is the smallest power of 2 
+//   value larger or equal to the requested size AND larger or equal to
+//   MIN_BLOCK_SIZE.
+// - It pop the linked list of free blocks corresponding to actual_size,
+//   and returns the block B if the list[actual_size] is not empty.
+// - If the list[actual_size] is empty, it pop the list[actual_size * 2].
+//   If a block B' is found, it break this block in 2 B/2 blocks, returns 
+//   the first B/2 block and push the other B/2 block into list[actual_size].
+// - If the list[actual_size * 2] is empty, it pop the list[actual_size * 4].
+//   If a block B is found, it break this block in 3 blocks B/4, B/4 and B/2,
+//   returns the first B/4 block, push the other blocks B/4 and B/2 into
+//   the proper lists. etc... 
+// - If no block satisfying the request is available it returns a failure
+//   (NULL pointer).
+// - This allocation policy has the nice following property:
+//   If the heap segment is aligned (the heap_base is a multiple of the
+//   heap_base), all allocated blocks are aligned on the actual_size.
+////////////////////////////////////////////////////////////////////////////////
+// Free policy:
+// - Each allocated block is registered in an alloc[] array of unsigned char.
+// - This registration is required by the free() operation, because the size
+//   of the allocated block must obtained from the base address of the block.  
+// - The number of entries in this array is equal to the max number
+//   of allocated block is : heap_size / 128.
+// - For each allocated block, the value registered in the alloc[] array
+//   is log2( size_of_allocated_block ).
+// - The index in this array is computed from the allocated block base address:
+//      index = (block_base - heap_base) / MIN_BLOCK_SIZE
+// - The allocated[] array is stored at the end of heap segment. This consume
+//   (1 / MIN_BLOCK_SIZE) of the total heap storage capacity.
+////////////////////////////////////////////////////////////////////////////////
 
 #ifndef _MALLOC_H_
 #define _MALLOC_H_
 
-//#define DEBUG_MALLOC 1
-
 #include "giet_config.h"
 #include "spin_lock.h"
 
-//#define MALLOC_SELECTED 2
+// There is the magic number indicating that heap(x,y) has been initialized.
 
-void * malloc(unsigned int size);
-void free(void * ptr);
+#define HEAP_INITIALIZED    0xDEADBEEF
+
+#define MIN_BLOCK_SIZE      0x80
+
+////////////////////////////////////////////////////////////////////////////////
+// heap(x,y) descriptor (one per cluster)
+////////////////////////////////////////////////////////////////////////////////
+typedef struct giet_heap_s
+{
+    unsigned int   init;            // initialised <=> value == HEAP_INITIALIZED
+    unsigned int   x;               // cluster X coordinate
+    unsigned int   y;               // cluster Y coordinate
+    unsigned int   heap_base;       // heap base address
+    unsigned int   heap_size;       // heap size (bytes)
+    unsigned int   alloc_base;      // alloc[] array base address
+    unsigned int   alloc_size;      // alloc[] array size (bytes)
+    giet_lock_t    lock;            // lock protecting exclusive access
+    unsigned int   free[32];        // array of base addresses of free blocks 
+                                    // (address of first block of a given size)
+} giet_heap_t;
+
+///////// user functions /////////////////
+
+extern void* malloc( unsigned int size );
+
+extern void* remote_malloc( unsigned int size, 
+                            unsigned int x,
+                            unsigned int y );
+
+extern void free(void * ptr);