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