eleni.mutantstargoat.com Git - winnie/blob - src/shalloc.cc

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <stdint.h>
   5 #include <string.h>
   6
   7 #include <map>
   8
   9 #include "shalloc.h"
  10
  11 #define POOL_SIZE 16777216
  12 #define BLOCK_SIZE 512
  13
  14 #define NUM_BLOCKS (POOL_SIZE / BLOCK_SIZE)
  15 #define BITMAP_SIZE (NUM_BLOCKS / 32)
  16
  17 static bool is_allocated(int block_number);
  18 static int addr_to_block(unsigned char *addr);
  19 static unsigned char *block_to_addr(int block_number);
  20 static void alloc_blocks(int block_pos, int num_blocks);
  21 static void free_blocks(int block_pos, int num_blocks);
  22
  23 static void print_stats();
  24
  25 static unsigned char *pool;
  26 static std::map<int, int> alloc_sizes; //starting block -> number of blocks
  27
  28 // 0 means not allocated 1 means allocated
  29 static uint32_t bitmap[BITMAP_SIZE];
  30
  31 struct Statistics {
  32         int alloc_num;
  33         int free_num;
  34         int alloc_memsize;
  35         int free_memsize;
  36 };
  37
  38 static Statistics stats;
  39
  40 bool init_shared_memory()
  41 {
  42         if(!(pool = (unsigned char *)malloc(POOL_SIZE))) {
  43                 return false;
  44         }
  45
  46         for(int i=0; i<BITMAP_SIZE; i++) {
  47                 bitmap[i] = 0;
  48         }
  49
  50         alloc_sizes.clear();
  51         memset(&stats, 0, sizeof stats);
  52
  53         return true;
  54 }
  55
  56 void destroy_shared_memory()
  57 {
  58         print_stats();
  59         free(pool);
  60 }
  61
  62 void *sh_malloc(size_t bytes)
  63 {
  64         if(!bytes) {
  65                 return 0;
  66         }
  67
  68         int num_blocks = (bytes + BLOCK_SIZE - 1) / BLOCK_SIZE;
  69
  70         int free_block;
  71         int ctr = 0;
  72         for(int i=0; i<NUM_BLOCKS; i++) {
  73                 if(!is_allocated(i)) {
  74                         if(!ctr) {
  75                                 free_block = i;
  76                         }
  77                         ctr++;
  78                 }
  79                 else {
  80                         ctr = 0;
  81                 }
  82
  83                 if(ctr == num_blocks) {
  84                         alloc_blocks(free_block, num_blocks);
  85                         return block_to_addr(free_block);
  86                 }
  87         }
  88
  89         return 0;
  90 }
  91
  92 void sh_free(void *ptr)
  93 {
  94         int block = addr_to_block((unsigned char*)ptr);
  95         std::map<int, int>::iterator it;
  96         if((it = alloc_sizes.find(block)) != alloc_sizes.end()) {
  97                 int num_blocks = it->second;
  98                 free_blocks(block, num_blocks);
  99                 alloc_sizes.erase(it);
 100         }
 101         else {
 102                 fprintf(stderr, "Attempt to free non-existent blocks from: %d\n", block);
 103         }
 104 }
 105
 106 static bool is_allocated(int block_number)
 107 {
 108         int idx = block_number / 32;
 109         int bit_num = block_number % 32;
 110
 111         if((bitmap[idx] >> bit_num) & 1) {
 112                 return true;
 113         }
 114
 115         return false;
 116 }
 117
 118 static int addr_to_block(unsigned char *addr)
 119 {
 120         assert(addr >= pool);
 121         assert(addr < pool + POOL_SIZE);
 122
 123         return (addr - pool) / BLOCK_SIZE;
 124 }
 125
 126 static unsigned char *block_to_addr(int block_number)
 127 {
 128         assert(block_number >= 0);
 129         assert(block_number < NUM_BLOCKS);
 130
 131         return pool + block_number * BLOCK_SIZE;
 132 }
 133
 134 static void alloc_blocks(int block_pos, int num_blocks)
 135 {
 136         for(int i=0; i<num_blocks; i++) {
 137                 int block_number = i + block_pos;
 138                 int idx = block_number / 32;
 139                 int bit_num = block_number % 32;
 140
 141                 bitmap[idx] |= ((uint32_t)1 << bit_num); // or pow(2, i)
 142         }
 143
 144         alloc_sizes[block_pos] = num_blocks;
 145
 146         stats.alloc_num++;
 147         stats.alloc_memsize += BLOCK_SIZE * num_blocks;
 148 }
 149
 150 static void free_blocks(int block_pos, int num_blocks)
 151 {
 152         for(int i=0; i<num_blocks; i++) {
 153                 int block_number = i + block_pos;
 154                 int idx = block_number / 32;
 155                 int bit_num = block_number % 32;
 156
 157                 bitmap[idx] &= ~((uint32_t)1 << bit_num);
 158         }
 159
 160         stats.free_num++;
 161         stats.free_memsize += BLOCK_SIZE * num_blocks;
 162 }
 163
 164 static void print_stats()
 165 {
 166         printf("Total allocated memory: %d\n", stats.alloc_memsize);
 167         printf("Total deallocated memory: %d\n", stats.free_memsize);
 168         printf("Number of allocations: %d\n", stats.alloc_num);
 169         printf("Number of deallocations: %d\n", stats.free_num);
 170 }
 171