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 = stgReallocBytes(mblock_maps,
  92                                       sizeof(MBlockMap*) * mblock_map_count,
  93                                       "markHeapAlloced(1)");
  94         map = mblock_maps[mblock_map_count-1] =
  95             stgMallocBytes(sizeof(MBlockMap),"markHeapAlloced(2)");
  96         memset(map,0,sizeof(MBlockMap));
  97         map->addrHigh32 = (StgWord32) (((StgWord)p) >> 32);
  98     }
  99
 100     map->lines[MBLOCK_MAP_LINE(p)] = i;
 101
 102     {
 103         StgWord mblock;
 104         nat entry_no;
 105
 106         mblock   = (StgWord)p >> MBLOCK_SHIFT;
 107         entry_no = mblock & (MBC_ENTRIES-1);
 108         mblock_cache[entry_no] = (mblock << 1) + i;
 109     }
 110 }
 111 #endif
 112
 113 static void
 114 markHeapAlloced(void *p)
 115 {
 116     setHeapAlloced(p, 1);
 117 }
 118
 119 static void
 120 markHeapUnalloced(void *p)
 121 {
 122     setHeapAlloced(p, 0);
 123 }
 124
 125 #if SIZEOF_VOID_P == 4
 126
 127 STATIC_INLINE
 128 void * mapEntryToMBlock(nat i)
 129 {
 130     return (void *)((StgWord)i << MBLOCK_SHIFT);
 131 }
 132
 133 void * getFirstMBlock(void)
 134 {
 135     nat i;
 136
 137     for (i = 0; i < MBLOCK_MAP_SIZE; i++) {
 138         if (mblock_map[i]) return mapEntryToMBlock(i);
 139     }
 140     return NULL;
 141 }
 142
 143 void * getNextMBlock(void *mblock)
 144 {
 145     nat i;
 146
 147     for (i = MBLOCK_MAP_ENTRY(mblock) + 1; i < MBLOCK_MAP_SIZE; i++) {
 148         if (mblock_map[i]) return mapEntryToMBlock(i);
 149     }
 150     return NULL;
 151 }
 152
 153 #elif SIZEOF_VOID_P == 8
 154
 155 void * getNextMBlock(void *p)
 156 {
 157     MBlockMap *map;
 158     nat off, j;
 159     nat line_no;
 160     MBlockMapLine line;
 161
 162     for (j = 0; j < mblock_map_count; j++)  {
 163         map = mblock_maps[j];
 164         if (map->addrHigh32 == (StgWord)p >> 32) break;
 165     }
 166     if (j == mblock_map_count) return NULL;
 167
 168     for (; j < mblock_map_count; j++) {
 169         map = mblock_maps[j];
 170         if (map->addrHigh32 == (StgWord)p >> 32) {
 171             line_no = MBLOCK_MAP_LINE(p);
 172             off  = (((StgWord)p >> MBLOCK_SHIFT) & (MBC_LINE_SIZE-1)) + 1;
 173             // + 1 because we want the *next* mblock
 174         } else {
 175             line_no = 0; off = 0;
 176         }
 177         for (; line_no < MBLOCK_MAP_ENTRIES; line_no++) {
 178             line = map->lines[line_no];
 179             for (; off < MBC_LINE_SIZE; off++) {
 180                 if (line & (1<<off)) {
 181                     return (void*)(((StgWord)map->addrHigh32 << 32) +
 182                                    line_no * MBC_LINE_SIZE * MBLOCK_SIZE +
 183                                    off * MBLOCK_SIZE);
 184                 }
 185             }
 186             off = 0;
 187         }
 188     }
 189     return NULL;
 190 }
 191
 192 void * getFirstMBlock(void)
 193 {
 194     MBlockMap *map = mblock_maps[0];
 195     nat line_no, off;
 196     MbcCacheLine line;
 197
 198     for (line_no = 0; line_no < MBLOCK_MAP_ENTRIES; line_no++) {
 199         line = map->lines[line_no];
 200         if (line) {
 201             for (off = 0; off < MBC_LINE_SIZE; off++) {
 202                 if (line & (1<<off)) {
 203                     return (void*)(((StgWord)map->addrHigh32 << 32) +
 204                                    line_no * MBC_LINE_SIZE * MBLOCK_SIZE +
 205                                    off * MBLOCK_SIZE);
 206                 }
 207             }
 208         }
 209     }
 210     return NULL;
 211 }
 212
 213 #endif // SIZEOF_VOID_P
 214
 215 /* -----------------------------------------------------------------------------
 216    Allocate new mblock(s)
 217    -------------------------------------------------------------------------- */
 218
 219 void *
 220 getMBlock(void)
 221 {
 222   return getMBlocks(1);
 223 }
 224
 225 // The external interface: allocate 'n' mblocks, and return the
 226 // address.
 227
 228 void *
 229 getMBlocks(nat n)
 230 {
 231     nat i;
 232     void *ret;
 233
 234     ret = osGetMBlocks(n);
 235
 236     debugTrace(DEBUG_gc, "allocated %d megablock(s) at %p",n,ret);
 237
 238     // fill in the table
 239     for (i = 0; i < n; i++) {
 240         markHeapAlloced( (StgWord8*)ret + i * MBLOCK_SIZE );
 241     }
 242
 243     mblocks_allocated += n;
 244     peak_mblocks_allocated = stg_max(peak_mblocks_allocated, mblocks_allocated);
 245
 246     return ret;
 247 }
 248
 249 void
 250 freeMBlocks(void *addr, nat n)
 251 {
 252     nat i;
 253
 254     debugTrace(DEBUG_gc, "freeing %d megablock(s) at %p",n,addr);
 255
 256     mblocks_allocated -= n;
 257
 258     for (i = 0; i < n; i++) {
 259         markHeapUnalloced( (StgWord8*)addr + i * MBLOCK_SIZE );
 260     }
 261
 262     osFreeMBlocks(addr, n);
 263 }
 264
 265 void
 266 freeAllMBlocks(void)
 267 {
 268     nat n;
 269
 270     debugTrace(DEBUG_gc, "freeing all megablocks");
 271
 272     osFreeAllMBlocks();
 273
 274     for (n = 0; n < mblock_map_count; n++) {
 275         stgFree(mblock_maps[n]);
 276     }
 277     stgFree(mblock_maps);
 278 }
 279
 280 void
 281 initMBlocks(void)
 282 {
 283     osMemInit();
 284 #if SIZEOF_VOID_P == 8
 285     memset(mblock_cache,0xff,sizeof(mblock_cache));
 286 #endif
 287 }