vg_mem.h

   1 #ifndef VG_MEM_H
   2 #define VG_MEM_H
   3
   4 #include "vg.h"
   5 #include "vg_stdint.h"
   6 #include "vg_platform.h"
   7 #include "vg_log.h"
   8
   9 #include <stdlib.h>
  10 #include <malloc.h>
  11
  12 static void vg_print_backtrace(void);
  13
  14 #define VG_MAX_ALLOCATIONS 128
  15 #define VG_FUZZ_ALLOCATIONS
  16
  17 typedef struct vg_linear_allocator vg_linear_allocator;
  18 typedef struct vg_allocation_meta vg_allocation_meta;
  19
  20 struct{
  21    void *rtmemory,
  22         *scratch;
  23
  24    int   use_libc_malloc;
  25    u32   quota;
  26 }
  27 static vg_mem;
  28
  29 struct vg_allocation_meta
  30 {
  31    const char *name;
  32    void *data;
  33    u32 size;
  34    enum allocation_type{
  35       k_allocation_type_block  = 0,
  36       k_allocation_type_linear = 1
  37    }
  38    type;
  39 };
  40
  41 #define VG_MEMORY_SYSTEM    0x1  /* systems memory, slow and low counts */
  42 #define VG_MEMORY_REALTIME  0x2  /* per-frame. no max allocs, only size. fast */
  43
  44 /* systems memory cannot be declared inside realtime memory regions */
  45
  46 /*
  47  * Stored just behind the array. 32 bytes.
  48  */
  49 #pragma pack(push,1)
  50 struct vg_linear_allocator
  51 {
  52    u32 size;
  53    u32 cur;
  54    u16 allocation_count;
  55    u16 flags;
  56    u32 last_alloc_size;
  57    void *last_alloc;
  58    vg_allocation_meta *alloc_table;
  59
  60 #ifdef _WIN32
  61    /* 32 bit pointers! */
  62    u8 padding[ 8 ];
  63 #endif
  64 };
  65 #pragma pack(pop)
  66
  67 static u32 vg_align8( u32 s );
  68 static u32 vg_align4( u32 s );
  69
  70 /* allocate something from a linear allocator */
  71 __attribute__((warn_unused_result))
  72 static void *_vg_linear_alloc( void *buffer, u32 size,
  73                                   const char *constr_name );
  74
  75 /* resize latest block of memory from linear */
  76 __attribute__((warn_unused_result))
  77 static void *vg_linear_resize( void *buffer, void *data, u32 newsize );
  78
  79 /* its possible to delete just the last item */
  80 static void vg_linear_del( void *buffer, void *data );
  81
  82 /* extend latest block of memory from linear */
  83 __attribute__((warn_unused_result))
  84 static void *_vg_linear_extend( void *buffer, void *data, u32 extra,
  85                                    const char *constr_name );
  86
  87 /* get the current usage of allocator */
  88 static u32 vg_linear_get_cur( void *buffer );
  89
  90 /* get the capacity of allocator. */
  91 static u32 vg_linear_get_capacity( void *buffer );
  92
  93 /* get the remaining size of the allocator */
  94 static u32 vg_linear_remaining( void *buffer );
  95
  96 /* yeet all memory from linear allocator */
  97 static void vg_linear_clear( void *buffer );
  98
  99 /* request all the memory we need in advance */
 100 static void vg_set_mem_quota( u32 size );
 101
 102 /* essentially init() */
 103 static void vg_alloc_quota(void);
 104
 105 /* print out tree of current memory used. only works with libc mode */
 106 static void vg_mem_log( void *lin_alloc, int depth, const char *name );
 107
 108 #define VG_MEM_MCSTR(S) VG_MEM_MCSTR2(S)
 109 #define VG_MEM_MCSTR2(S) #S
 110
 111 #define vg_linear_alloc(...) \
 112    _vg_linear_alloc( __VA_ARGS__, __FILE__":"VG_MEM_MCSTR(__LINE__) )
 113 #define vg_linear_extend(...) \
 114    _vg_linear_extend( __VA_ARGS__, __FILE__":"VG_MEM_MCSTR(__LINE__) )
 115 #define vg_create_linear_allocator(...) \
 116    _vg_create_linear_allocator( __VA_ARGS__, __FILE__":"VG_MEM_MCSTR(__LINE__) )
 117
 118 /* implementation
 119  * ----------------------------------------
 120  */
 121
 122 static void vg_fatal_error( const char *fmt, ... );
 123
 124 #if 0
 125 static void vg_error(const char *fmt, ...);
 126 static void vg_info(const char *fmt, ...);
 127 #endif
 128
 129 static u32 vg_align8( u32 s )
 130 {
 131    u32 m = (s + 7) >> 3;
 132    return m << 3;
 133 }
 134
 135 static u32 vg_align4( u32 s )
 136 {
 137    u32 m = (s + 3) >> 2;
 138    return m << 2;
 139 }
 140
 141 /* Returns allocator structure from data pointer */
 142 static vg_linear_allocator *vg_linear_header( void *data )
 143 {
 144    vg_linear_allocator *ptr = data;
 145    ptr --;
 146
 147    return ptr;
 148 }
 149
 150 /* allocate something from a linear allocator */
 151 __attribute__((warn_unused_result))
 152 static void *_vg_linear_alloc( void *buffer, u32 size,
 153                                   const char *constr_name )
 154 {
 155    if( size % 8 ){
 156       vg_error( "alloc(%u) is not 8 byte aligned\n", size );
 157       vg_print_backtrace();
 158       size = vg_align8( size );
 159    }
 160    if( ((u64)buffer) % 8 ){
 161       vg_fatal_error( "unaligned buffer (%p)", buffer );
 162    }
 163
 164    vg_linear_allocator *alloc = vg_linear_header( buffer );
 165
 166    if( (alloc->cur + size) > alloc->size ){
 167       vg_fatal_error( "linear allocator overflow (%u + %u > %u)\n",
 168                         alloc->cur, size, alloc->size );
 169    }
 170
 171    if( alloc->flags & VG_MEMORY_SYSTEM )
 172       if( (alloc->allocation_count + 1) > VG_MAX_ALLOCATIONS )
 173          vg_fatal_error( "Max linear allocations reached" );
 174
 175    void *data;
 176
 177    if( vg_mem.use_libc_malloc && (alloc->flags & VG_MEMORY_SYSTEM) ){
 178       data = malloc( size );
 179
 180       vg_allocation_meta *meta = &alloc->alloc_table[ alloc->allocation_count ];
 181       meta->type = k_allocation_type_block;
 182       meta->data = data;
 183       meta->size = size;
 184       meta->name = constr_name;
 185    }
 186    else{
 187       data = buffer + alloc->cur;
 188    }
 189
 190    u8 *bytes = data;
 191    for( u32 i=0; i<size; i++ ){
 192       bytes[i] = 0xfe;
 193    }
 194
 195    alloc->allocation_count ++;
 196    alloc->last_alloc = data;
 197    alloc->last_alloc_size = size;
 198    alloc->cur += size;
 199
 200    if( ((u64)data) % 8 ){
 201       vg_fatal_error( "unaligned" );
 202    }
 203
 204    return data;
 205 }
 206
 207 /* resize latest block of memory from linear */
 208 __attribute__((warn_unused_result))
 209 static void *vg_linear_resize( void *buffer, void *data, u32 newsize )
 210 {
 211    vg_linear_allocator *alloc = vg_linear_header( buffer );
 212
 213    if( newsize % 8 ){
 214       vg_error( "alloc(%u) is not 8 byte aligned\n", newsize );
 215       vg_print_backtrace();
 216       newsize = vg_align8( newsize );
 217    }
 218
 219    if( alloc->last_alloc != data )
 220       vg_fatal_error( "This block has been fixed!" );
 221
 222    if( (alloc->cur - alloc->last_alloc_size + newsize) > alloc->size )
 223       vg_fatal_error( "Cannot resize, overflow" );
 224
 225    alloc->cur -= alloc->last_alloc_size;
 226    alloc->cur += newsize;
 227    alloc->last_alloc_size = newsize;
 228
 229    if( vg_mem.use_libc_malloc && (alloc->flags & VG_MEMORY_SYSTEM) ){
 230       data = realloc( data, newsize );
 231       if( !data )
 232          vg_fatal_error( "realloc failed" );
 233
 234       alloc->alloc_table[ alloc->allocation_count-1 ].data = data;
 235       alloc->last_alloc = data;
 236       return data;
 237    }
 238    else{
 239       return data;
 240    }
 241 }
 242
 243 /* its possible to delete just the last item */
 244 static void vg_linear_del( void *buffer, void *data )
 245 {
 246    vg_linear_allocator *alloc = vg_linear_header( buffer );
 247
 248    if( alloc->last_alloc != data ){
 249       vg_fatal_error( "This block has been fixed! Last alloc: %p, this: %p\n",
 250                       alloc->last_alloc, data );
 251    }
 252
 253    if( vg_mem.use_libc_malloc && (alloc->flags & VG_MEMORY_SYSTEM) ){
 254       vg_allocation_meta *meta = &alloc->alloc_table[alloc->allocation_count-1];
 255       if( meta->type == k_allocation_type_linear )
 256          vg_fatal_error( "Cannot free a linear allocator in this conext" );
 257
 258       free( data );
 259    }
 260
 261    alloc->allocation_count --;
 262    alloc->cur -= alloc->last_alloc_size;
 263    alloc->last_alloc = NULL;
 264    alloc->last_alloc_size = 0;
 265 }
 266
 267 /* extend latest block of memory from linear */
 268 __attribute__((warn_unused_result))
 269 static void *_vg_linear_extend( void *buffer, void *data, u32 extra,
 270                                    const char *constr_name )
 271 {
 272    if( !data )
 273       return _vg_linear_alloc( buffer, vg_align8(extra), constr_name );
 274
 275    vg_linear_allocator *alloc = vg_linear_header( buffer );
 276
 277    if( alloc->last_alloc != data )
 278       vg_fatal_error( "This block has been fixed!" );
 279
 280    u32 new_size = alloc->last_alloc_size + extra;
 281    return vg_linear_resize( buffer, data, vg_align8(new_size) );
 282 }
 283
 284 /* get the current usage of allocator */
 285 static u32 vg_linear_get_cur( void *buffer )
 286 {
 287    vg_linear_allocator *alloc = vg_linear_header( buffer );
 288    return alloc->cur;
 289 }
 290
 291 /* get the capacity of allocator. */
 292 static u32 vg_linear_get_capacity( void *buffer )
 293 {
 294    vg_linear_allocator *alloc = vg_linear_header( buffer );
 295    return alloc->size;
 296 }
 297
 298 /* get the remaining size of the allocator */
 299 static u32 vg_linear_remaining( void *buffer )
 300 {
 301    vg_linear_allocator *alloc = vg_linear_header( buffer );
 302    return alloc->size - alloc->cur;
 303 }
 304
 305 /* yeet all memory from linear allocator */
 306 static void vg_linear_clear( void *buffer )
 307 {
 308    vg_linear_allocator *alloc = vg_linear_header( buffer );
 309
 310    /* libc mode we recursively free any allocations made */
 311    if( vg_mem.use_libc_malloc && (alloc->flags & VG_MEMORY_SYSTEM) ){
 312       for( u32 i=0; i<alloc->allocation_count; i++ ){
 313          vg_allocation_meta *meta = &alloc->alloc_table[i];
 314
 315          if( meta->type == k_allocation_type_block ){
 316             free( meta->data );
 317          }
 318          else{
 319             vg_linear_clear( meta->data );
 320             vg_linear_allocator *sub = vg_linear_header( meta->data );
 321
 322             free( sub->alloc_table );
 323             free( sub );
 324          }
 325       }
 326    }
 327
 328    alloc->last_alloc = NULL;
 329    alloc->last_alloc_size = 0;
 330    alloc->allocation_count = 0;
 331    alloc->cur = 0;
 332 }
 333
 334 /* allocate a FIXED SIZE linear allocator
 335  *
 336  * FIXME: there was a bug in vg's code that caused a race condition between
 337  *        two system allocations. make this IMPOSSIBLE by requiring a lock
 338  *        on the allocater to be passed between threads.
 339  *
 340  *        luckily that bug only exists when using development tools, but still!
 341  *
 342  *        this should then only be checked and turned on in debugging.
 343  *
 344  */
 345 static void *_vg_create_linear_allocator( void *lin_alloc, u32 size,
 346                                              u16 flags, const char *constr_name)
 347 {
 348    assert( sizeof( vg_linear_allocator ) == 32 );
 349
 350    vg_linear_allocator *header;
 351    u32 block_size = size + sizeof(vg_linear_allocator);
 352
 353    /* Creating it inside an existing one */
 354    if( lin_alloc ){
 355       vg_linear_allocator *alloc = vg_linear_header( lin_alloc );
 356
 357       if( alloc->cur + block_size > alloc->size )
 358          vg_fatal_error( "Out of memory" );
 359
 360       if( alloc->allocation_count + 1 > VG_MAX_ALLOCATIONS )
 361          vg_fatal_error( "Max allocations in linear allocator" );
 362
 363       if( (flags && VG_MEMORY_SYSTEM) && (alloc->flags & VG_MEMORY_REALTIME) )
 364          vg_fatal_error( "Cannot declare realtime allocator inside systems"
 365                              " allocator" );
 366
 367       if( vg_mem.use_libc_malloc ){
 368          vg_allocation_meta *meta =
 369             &alloc->alloc_table[ alloc->allocation_count ];
 370
 371          if( flags & VG_MEMORY_REALTIME )
 372             header = malloc( block_size );
 373          else
 374             header = malloc( sizeof(vg_linear_allocator) );
 375
 376          meta->data = header+1;
 377          meta->type = k_allocation_type_linear;
 378          meta->size = size;
 379          meta->name = constr_name;
 380       }
 381       else{
 382          header = lin_alloc + alloc->cur;
 383       }
 384
 385       alloc->cur += block_size;
 386       alloc->last_alloc = header;
 387       alloc->last_alloc_size = block_size;
 388       alloc->allocation_count ++;
 389    }
 390    else{
 391       if( vg_mem.use_libc_malloc && (flags & VG_MEMORY_SYSTEM) )
 392          header = malloc( sizeof(vg_linear_allocator) );
 393       else
 394          header = malloc( block_size );
 395    }
 396
 397    header->allocation_count = 0;
 398    header->cur = 0;
 399    header->last_alloc = NULL;
 400    header->last_alloc_size = 0;
 401    header->size = size;
 402    header->flags = flags;
 403
 404    if( vg_mem.use_libc_malloc && (flags & VG_MEMORY_SYSTEM) ){
 405       u32 table_size = sizeof(vg_allocation_meta)*VG_MAX_ALLOCATIONS;
 406       header->alloc_table = malloc( table_size );
 407    }
 408    else
 409       header->alloc_table = NULL;
 410
 411    return header+1;
 412 }
 413
 414 /* request all the memory we need in advance */
 415 static void vg_set_mem_quota( u32 size )
 416 {
 417    vg_mem.quota = size;
 418 }
 419
 420 static void vg_alloc_quota(void)
 421 {
 422    u32 size_scratch = 10*1024*1024;
 423    u32 size = VG_MAX( vg_mem.quota, size_scratch );
 424
 425    vg_mem.rtmemory = _vg_create_linear_allocator( NULL, size, VG_MEMORY_SYSTEM,
 426                                                   "VG Root" );
 427    vg_mem.scratch = _vg_create_linear_allocator( vg_mem.rtmemory,
 428                                                  size_scratch,
 429                                                  VG_MEMORY_SYSTEM,
 430                                                  "Scratch buffer" );
 431 }
 432
 433 static void vg_mem_log( void *lin_alloc, int depth, const char *name )
 434 {
 435    if( vg_mem.use_libc_malloc ){
 436       vg_linear_allocator *alloc = vg_linear_header( lin_alloc );
 437
 438       u32 s = alloc->size;
 439       f32 p = ((float)alloc->cur / (float)alloc->size) * 100.0f;
 440
 441       for( int i=0; i<depth; i++ ) printf( "  " );
 442       printf( "LA(%s): %u bytes, %f%% used\n", name, s, p );
 443
 444       if( alloc->flags & VG_MEMORY_SYSTEM ){
 445          for( u32 i=0; i<alloc->allocation_count; i++ ){
 446             vg_allocation_meta *meta = &alloc->alloc_table[i];
 447
 448             if( meta->type == k_allocation_type_block ){
 449                for( int i=0; i<depth+1; i++ ) printf( "  " );
 450                printf( "B(%s): %u bytes\n", meta->name, meta->size );
 451             }
 452             else{
 453                vg_mem_log( meta->data, depth +1, meta->name );
 454             }
 455          }
 456       }
 457       else{
 458          for( int i=0; i<depth+1; i++ ) printf( "  " );
 459          printf( "<opaque memory> (UNTRACKED)\n" );
 460       }
 461    }
 462    else{
 463       vg_error( "allocations are not tracked (turn on libc mode)\n" );
 464    }
 465 }
 466
 467 #endif /* VG_MEM_H */