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         //TODO delete it
  65         /*if(!(pool = (unsigned char *)malloc(POOL_SIZE))) {
  66                 return false;
  67         }*/
  68
  69         for(int i=0; i<BITMAP_SIZE; i++) {
  70                 bitmap[i] = 0;
  71         }
  72
  73         alloc_sizes.clear();
  74         memset(&stats, 0, sizeof stats);
  75
  76         return true;
  77 }
  78
  79 void destroy_shared_memory()
  80 {
  81         print_stats();
  82         //free(pool); //TODO DELETE it
  83         if(munmap(pool, POOL_SIZE) == -1) {
  84                 fprintf(stderr, "Failed to unmap shared memory: %s\n", strerror(errno));
  85         }
  86 }
  87
  88 void *sh_malloc(size_t bytes)
  89 {
  90         if(!bytes) {
  91                 return 0;
  92         }
  93
  94         int num_blocks = (bytes + BLOCK_SIZE - 1) / BLOCK_SIZE;
  95
  96         int free_block;
  97         int ctr = 0;
  98         for(int i=0; i<NUM_BLOCKS; i++) {
  99                 if(!is_allocated(i)) {
 100                         if(!ctr) {
 101                                 free_block = i;
 102                         }
 103                         ctr++;
 104                 }
 105                 else {
 106                         ctr = 0;
 107                 }
 108
 109                 if(ctr == num_blocks) {
 110                         alloc_blocks(free_block, num_blocks);
 111                         return block_to_addr(free_block);
 112                 }
 113         }
 114
 115         return 0;
 116 }
 117
 118 void sh_free(void *ptr)
 119 {
 120         int block = addr_to_block((unsigned char*)ptr);
 121         std::map<int, int>::iterator it;
 122         if((it = alloc_sizes.find(block)) != alloc_sizes.end()) {
 123                 int num_blocks = it->second;
 124                 free_blocks(block, num_blocks);
 125                 alloc_sizes.erase(it);
 126         }
 127         else {
 128                 fprintf(stderr, "Attempt to free non-existent blocks from: %d\n", block);
 129         }
 130 }
 131
 132 static bool is_allocated(int block_number)
 133 {
 134         int idx = block_number / 32;
 135         int bit_num = block_number % 32;
 136
 137         if((bitmap[idx] >> bit_num) & 1) {
 138                 return true;
 139         }
 140
 141         return false;
 142 }
 143
 144 static int addr_to_block(unsigned char *addr)
 145 {
 146         assert(addr >= pool);
 147         assert(addr < pool + POOL_SIZE);
 148
 149         return (addr - pool) / BLOCK_SIZE;
 150 }
 151
 152 static unsigned char *block_to_addr(int block_number)
 153 {
 154         assert(block_number >= 0);
 155         assert(block_number < NUM_BLOCKS);
 156
 157         return pool + block_number * BLOCK_SIZE;
 158 }
 159
 160 static void alloc_blocks(int block_pos, int num_blocks)
 161 {
 162         for(int i=0; i<num_blocks; i++) {
 163                 int block_number = i + block_pos;
 164                 int idx = block_number / 32;
 165                 int bit_num = block_number % 32;
 166
 167                 bitmap[idx] |= ((uint32_t)1 << bit_num); // or pow(2, i)
 168         }
 169
 170         alloc_sizes[block_pos] = num_blocks;
 171
 172         stats.alloc_num++;
 173         stats.alloc_memsize += BLOCK_SIZE * num_blocks;
 174 }
 175
 176 static void free_blocks(int block_pos, int num_blocks)
 177 {
 178         for(int i=0; i<num_blocks; i++) {
 179                 int block_number = i + block_pos;
 180                 int idx = block_number / 32;
 181                 int bit_num = block_number % 32;
 182
 183                 bitmap[idx] &= ~((uint32_t)1 << bit_num);
 184         }
 185
 186         stats.free_num++;
 187         stats.free_memsize += BLOCK_SIZE * num_blocks;
 188 }
 189
 190 static void print_stats()
 191 {
 192         printf("Total allocated memory: %d\n", stats.alloc_memsize);
 193         printf("Total deallocated memory: %d\n", stats.free_memsize);
 194         printf("Number of allocations: %d\n", stats.alloc_num);
 195         printf("Number of deallocations: %d\n", stats.free_num);
 196 }
 197