rts/sm/MBlock.c

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team 1998-2008
   4  *
   5  * MegaBlock Allocator Interface.  This file contains all the dirty
   6  * architecture-dependent hackery required to get a chunk of aligned
   7  * memory from the operating system.
   8  *
   9  * ---------------------------------------------------------------------------*/
  10
  11 #include "PosixSource.h"
  12 #include "Rts.h"
  13
  14 #include "RtsUtils.h"
  15 #include "BlockAlloc.h"
  16 #include "Trace.h"
  17 #include "OSMem.h"
  18
  19 #include <string.h>
  20
  21 lnat peak_mblocks_allocated = 0;
  22 lnat mblocks_allocated = 0;
  23 lnat mpc_misses = 0;
  24
  25 /* -----------------------------------------------------------------------------
  26    The MBlock Map: provides our implementation of HEAP_ALLOCED()
  27    -------------------------------------------------------------------------- */
  28
  29 #if SIZEOF_VOID_P == 4
  30 StgWord8 mblock_map[MBLOCK_MAP_SIZE]; // initially all zeros
  31
  32 static void
  33 setHeapAlloced(void *p, StgWord8 i)
  34 {
  35     mblock_map[MBLOCK_MAP_ENTRY(p)] = i;
  36 }
  37
  38 #elif SIZEOF_VOID_P == 8
  39
  40 MBlockMap **mblock_maps = NULL;
  41
  42 nat mblock_map_count = 0;
  43
  44 MbcCacheLine mblock_cache[MBC_ENTRIES];
  45
  46 static MBlockMap *
  47 findMBlockMap(void *p)
  48 {
  49     nat i;
  50     StgWord32 hi = (StgWord32) (((StgWord)p) >> 32);
  51     for( i = 0; i < mblock_map_count; i++ )
  52     {
  53         if(mblock_maps[i]->addrHigh32 == hi)
  54         {
  55             return mblock_maps[i];
  56         }
  57     }
  58     return NULL;
  59 }
  60
  61 StgBool HEAP_ALLOCED_miss(StgWord mblock, void *p)
  62 {
  63     MBlockMap *map;
  64     MBlockMapLine value;
  65     nat entry_no;
  66
  67     entry_no = mblock & (MBC_ENTRIES-1);
  68
  69     map = findMBlockMap(p);
  70     if (map)
  71     {
  72         mpc_misses++;
  73         value = map->lines[MBLOCK_MAP_LINE(p)];
  74         mblock_cache[entry_no] = (mblock<<1) | value;
  75         return value;
  76     }
  77     else
  78     {
  79         mblock_cache[entry_no] = (mblock<<1);
  80         return 0;
  81     }
  82 }
  83
  84 static void
  85 setHeapAlloced(void *p, StgWord8 i)
  86 {
  87     MBlockMap *map = findMBlockMap(p);
  88     if(map == NULL)
  89     {
  90         mblock_map_count++;
  91         mblock_maps = realloc(mblock_maps,
  92                               sizeof(MBlockMap*) * mblock_map_count);
  93         map = mblock_maps[mblock_map_count-1] =
  94             stgMallocBytes(sizeof(MBlockMap),"markHeapAlloced");
  95         memset(map,0,sizeof(MBlockMap));
  96         map->addrHigh32 = (StgWord32) (((StgWord)p) >> 32);
  97     }
  98
  99     map->lines[MBLOCK_MAP_LINE(p)] = i;
 100
 101     {
 102         StgWord mblock;
 103         nat entry_no;
 104
 105         mblock   = (StgWord)p >> MBLOCK_SHIFT;
 106         entry_no = mblock & (MBC_ENTRIES-1);
 107         mblock_cache[entry_no] = (mblock << 1) + i;
 108     }
 109 }
 110 #endif
 111
 112 static void
 113 markHeapAlloced(void *p)
 114 {
 115     setHeapAlloced(p, 1);
 116 }
 117
 118 static void
 119 markHeapUnalloced(void *p)
 120 {
 121     setHeapAlloced(p, 0);
 122 }
 123
 124 #if SIZEOF_VOID_P == 4
 125
 126 STATIC_INLINE
 127 void * mapEntryToMBlock(nat i)
 128 {
 129     return (void *)((StgWord)i << MBLOCK_SHIFT);
 130 }
 131
 132 void * getFirstMBlock(void)
 133 {
 134     nat i;
 135
 136     for (i = 0; i < MBLOCK_MAP_SIZE; i++) {
 137         if (mblock_map[i]) return mapEntryToMBlock(i);
 138     }
 139     return NULL;
 140 }
 141
 142 void * getNextMBlock(void *mblock)
 143 {
 144     nat i;
 145
 146     for (i = MBLOCK_MAP_ENTRY(mblock) + 1; i < MBLOCK_MAP_SIZE; i++) {
 147         if (mblock_map[i]) return mapEntryToMBlock(i);
 148     }
 149     return NULL;
 150 }
 151
 152 #elif SIZEOF_VOID_P == 8
 153
 154 void * getNextMBlock(void *p)
 155 {
 156     MBlockMap *map;
 157     nat off, j;
 158     nat line_no;
 159     MBlockMapLine line;
 160
 161     for (j = 0; j < mblock_map_count; j++)  {
 162         map = mblock_maps[j];
 163         if (map->addrHigh32 == (StgWord)p >> 32) break;
 164     }
 165     if (j == mblock_map_count) return NULL;
 166
 167     for (; j < mblock_map_count; j++) {
 168         map = mblock_maps[j];
 169         if (map->addrHigh32 == (StgWord)p >> 32) {
 170             line_no = MBLOCK_MAP_LINE(p);
 171             off  = (((StgWord)p >> MBLOCK_SHIFT) & (MBC_LINE_SIZE-1)) + 1;
 172             // + 1 because we want the *next* mblock
 173         } else {
 174             line_no = 0; off = 0;
 175         }
 176         for (; line_no < MBLOCK_MAP_ENTRIES; line_no++) {
 177             line = map->lines[line_no];
 178             for (; off < MBC_LINE_SIZE; off++) {
 179                 if (line & (1<<off)) {
 180                     return (void*)(((StgWord)map->addrHigh32 << 32) +
 181                                    line_no * MBC_LINE_SIZE * MBLOCK_SIZE +
 182                                    off * MBLOCK_SIZE);
 183                 }
 184             }
 185             off = 0;
 186         }
 187     }
 188     return NULL;
 189 }
 190
 191 void * getFirstMBlock(void)
 192 {
 193     MBlockMap *map = mblock_maps[0];
 194     nat line_no, off;
 195     MbcCacheLine line;
 196
 197     for (line_no = 0; line_no < MBLOCK_MAP_ENTRIES; line_no++) {
 198         line = map->lines[line_no];
 199         if (line) {
 200             for (off = 0; off < MBC_LINE_SIZE; off++) {
 201                 if (line & (1<<off)) {
 202                     return (void*)(((StgWord)map->addrHigh32 << 32) +
 203                                    line_no * MBC_LINE_SIZE * MBLOCK_SIZE +
 204                                    off * MBLOCK_SIZE);
 205                 }
 206             }
 207         }
 208     }
 209     return NULL;
 210 }
 211
 212 #endif // SIZEOF_VOID_P
 213
 214 /* -----------------------------------------------------------------------------
 215    Allocate new mblock(s)
 216    -------------------------------------------------------------------------- */
 217
 218 void *
 219 getMBlock(void)
 220 {
 221   return getMBlocks(1);
 222 }
 223
 224 // The external interface: allocate 'n' mblocks, and return the
 225 // address.
 226
 227 void *
 228 getMBlocks(nat n)
 229 {
 230     nat i;
 231     void *ret;
 232
 233     ret = osGetMBlocks(n);
 234
 235     debugTrace(DEBUG_gc, "allocated %d megablock(s) at %p",n,ret);
 236
 237     // fill in the table
 238     for (i = 0; i < n; i++) {
 239         markHeapAlloced( (StgWord8*)ret + i * MBLOCK_SIZE );
 240     }
 241
 242     mblocks_allocated += n;
 243     peak_mblocks_allocated = stg_max(peak_mblocks_allocated, mblocks_allocated);
 244
 245     return ret;
 246 }
 247
 248 void
 249 freeMBlocks(void *addr, nat n)
 250 {
 251     nat i;
 252
 253     debugTrace(DEBUG_gc, "freeing %d megablock(s) at %p",n,addr);
 254
 255     mblocks_allocated -= n;
 256
 257     for (i = 0; i < n; i++) {
 258         markHeapUnalloced( (StgWord8*)addr + i * MBLOCK_SIZE );
 259     }
 260
 261     osFreeMBlocks(addr, n);
 262 }
 263
 264 void
 265 freeAllMBlocks(void)
 266 {
 267     debugTrace(DEBUG_gc, "freeing all megablocks");
 268     osFreeAllMBlocks();
 269 }
 270
 271 void
 272 initMBlocks(void)
 273 {
 274     osMemInit();
 275 #if SIZEOF_VOID_P == 8
 276     memset(mblock_cache,0xff,sizeof(mblock_cache));
 277 #endif
 278 }