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

   1 /*
   2 winnie - an experimental window system
   3
   4 Copyright (C) 2013 Eleni Maria Stea
   5
   6 This program is free software: you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation, either version 3 of the License, or
   9 (at your option) any later version.
  10
  11 This program is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18
  19 Author: Eleni Maria Stea <elene.mst@gmail.com>
  20 */
  21
  22 #include <assert.h>
  23 #include <stdio.h>
  24 #include <stdint.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 #include <errno.h>
  29 #include <fcntl.h>
  30 #include <sys/mman.h>
  31 #include <sys/stat.h>
  32 #include <unistd.h>
  33
  34 #include <map>
  35
  36 #include "shalloc.h"
  37
  38 #define BLOCK_SIZE 512
  39
  40 #define NUM_BLOCKS (POOL_SIZE / BLOCK_SIZE)
  41 #define BITMAP_SIZE (NUM_BLOCKS / 32)
  42
  43 static bool is_allocated(int block_number);
  44 static int addr_to_block(unsigned char *addr);
  45 static unsigned char *block_to_addr(int block_number);
  46 static void alloc_blocks(int block_pos, int num_blocks);
  47 static void free_blocks(int block_pos, int num_blocks);
  48
  49 static void print_stats();
  50 static int fd;
  51
  52 static unsigned char *pool;
  53 static std::map<int, int> alloc_sizes; //starting block -> number of blocks
  54
  55 // 0 means not allocated 1 means allocated
  56 static uint32_t bitmap[BITMAP_SIZE];
  57
  58 struct Statistics {
  59         int alloc_num;
  60         int free_num;
  61         int alloc_memsize;
  62         int free_memsize;
  63 };
  64
  65 static Statistics stats;
  66
  67 bool init_shared_memory()
  68 {
  69         if(((fd = shm_open(SHMNAME, O_RDWR | O_CREAT, S_IRWXU)) == -1)) {
  70                 fprintf(stderr, "Failed to open shared memory: %s\n", strerror(errno));
  71                 return false;
  72         }
  73         ftruncate(fd, POOL_SIZE);
  74
  75         if((pool = (unsigned char*)mmap(0, POOL_SIZE, PROT_READ | PROT_WRITE,
  76                                         MAP_SHARED, fd, 0)) == (void*)-1) {
  77                 fprintf(stderr, "Failed to map shared memory: %s\n", strerror(errno));
  78         }
  79
  80         shm_unlink(SHMNAME);
  81
  82         for(int i=0; i<BITMAP_SIZE; i++) {
  83                 bitmap[i] = 0;
  84         }
  85
  86         alloc_sizes.clear();
  87         memset(&stats, 0, sizeof stats);
  88
  89         return true;
  90 }
  91
  92 void destroy_shared_memory()
  93 {
  94         print_stats();
  95         if(munmap(pool, POOL_SIZE) == -1) {
  96                 fprintf(stderr, "Failed to unmap shared memory: %s\n", strerror(errno));
  97         }
  98 }
  99
 100 void *sh_malloc(size_t bytes)
 101 {
 102         if(!bytes) {
 103                 return 0;
 104         }
 105
 106         int num_blocks = (bytes + BLOCK_SIZE - 1) / BLOCK_SIZE;
 107
 108         int free_block;
 109         int ctr = 0;
 110         for(int i=0; i<NUM_BLOCKS; i++) {
 111                 if(!is_allocated(i)) {
 112                         if(!ctr) {
 113                                 free_block = i;
 114                         }
 115                         ctr++;
 116                 }
 117                 else {
 118                         ctr = 0;
 119                 }
 120
 121                 if(ctr == num_blocks) {
 122                         alloc_blocks(free_block, num_blocks);
 123                         return block_to_addr(free_block);
 124                 }
 125         }
 126
 127         return 0;
 128 }
 129
 130 void sh_free(void *ptr)
 131 {
 132         int block = addr_to_block((unsigned char*)ptr);
 133         std::map<int, int>::iterator it;
 134         if((it = alloc_sizes.find(block)) != alloc_sizes.end()) {
 135                 int num_blocks = it->second;
 136                 free_blocks(block, num_blocks);
 137                 alloc_sizes.erase(it);
 138         }
 139         else {
 140                 fprintf(stderr, "Attempt to free non-existent blocks from: %d\n", block);
 141         }
 142 }
 143
 144 void *get_pool()
 145 {
 146         return (void*)pool;
 147 }
 148
 149 static bool is_allocated(int block_number)
 150 {
 151         int idx = block_number / 32;
 152         int bit_num = block_number % 32;
 153
 154         if((bitmap[idx] >> bit_num) & 1) {
 155                 return true;
 156         }
 157
 158         return false;
 159 }
 160
 161 static int addr_to_block(unsigned char *addr)
 162 {
 163         assert(addr >= pool);
 164         assert(addr < pool + POOL_SIZE);
 165
 166         return (addr - pool) / BLOCK_SIZE;
 167 }
 168
 169 static unsigned char *block_to_addr(int block_number)
 170 {
 171         assert(block_number >= 0);
 172         assert(block_number < NUM_BLOCKS);
 173
 174         return pool + block_number * BLOCK_SIZE;
 175 }
 176
 177 static void alloc_blocks(int block_pos, int num_blocks)
 178 {
 179         for(int i=0; i<num_blocks; i++) {
 180                 int block_number = i + block_pos;
 181                 int idx = block_number / 32;
 182                 int bit_num = block_number % 32;
 183
 184                 bitmap[idx] |= ((uint32_t)1 << bit_num); // or pow(2, i)
 185         }
 186
 187         alloc_sizes[block_pos] = num_blocks;
 188
 189         stats.alloc_num++;
 190         stats.alloc_memsize += BLOCK_SIZE * num_blocks;
 191 }
 192
 193 static void free_blocks(int block_pos, int num_blocks)
 194 {
 195         for(int i=0; i<num_blocks; i++) {
 196                 int block_number = i + block_pos;
 197                 int idx = block_number / 32;
 198                 int bit_num = block_number % 32;
 199
 200                 bitmap[idx] &= ~((uint32_t)1 << bit_num);
 201         }
 202
 203         stats.free_num++;
 204         stats.free_memsize += BLOCK_SIZE * num_blocks;
 205 }
 206
 207 static void print_stats()
 208 {
 209         printf("Total allocated memory: %d\n", stats.alloc_memsize);
 210         printf("Total deallocated memory: %d\n", stats.free_memsize);
 211         printf("Number of allocations: %d\n", stats.alloc_num);
 212         printf("Number of deallocations: %d\n", stats.free_num);
 213 }
 214