diff options
Diffstat (limited to 'libwinnie/src/shalloc.cc')
| -rw-r--r-- | libwinnie/src/shalloc.cc | 217 |
1 files changed, 217 insertions, 0 deletions
diff --git a/libwinnie/src/shalloc.cc b/libwinnie/src/shalloc.cc new file mode 100644 index 0000000..5d4715a --- /dev/null +++ b/libwinnie/src/shalloc.cc @@ -0,0 +1,217 @@ +/* +winnie - an experimental window system + +Copyright (C) 2013 Eleni Maria Stea + +This program is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program. If not, see <http://www.gnu.org/licenses/>. + +Author: Eleni Maria Stea <elene.mst@gmail.com> +*/ + +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <string.h> + +#include <errno.h> +#include <fcntl.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <unistd.h> + +#include <map> + +#include "shalloc.h" + +#define SHMNAME "/winnie.shm" + +#define POOL_SIZE 16777216 +#define BLOCK_SIZE 512 + +#define NUM_BLOCKS (POOL_SIZE / BLOCK_SIZE) +#define BITMAP_SIZE (NUM_BLOCKS / 32) + +static bool is_allocated(int block_number); +static int addr_to_block(unsigned char *addr); +static unsigned char *block_to_addr(int block_number); +static void alloc_blocks(int block_pos, int num_blocks); +static void free_blocks(int block_pos, int num_blocks); + +static void print_stats(); +static int fd; + +static unsigned char *pool; +static std::map<int, int> alloc_sizes; //starting block -> number of blocks + +// 0 means not allocated 1 means allocated +static uint32_t bitmap[BITMAP_SIZE]; + +struct Statistics { + int alloc_num; + int free_num; + int alloc_memsize; + int free_memsize; +}; + +static Statistics stats; + +bool init_shared_memory() +{ + if(((fd = shm_open(SHMNAME, O_RDWR | O_CREAT, S_IRWXU)) == -1)) { + fprintf(stderr, "Failed to open shared memory: %s\n", strerror(errno)); + return false; + } + ftruncate(fd, POOL_SIZE); + + if((pool = (unsigned char*)mmap(0, POOL_SIZE, PROT_READ | PROT_WRITE, + MAP_SHARED, fd, 0)) == (void*)-1) { + fprintf(stderr, "Failed to map shared memory: %s\n", strerror(errno)); + } + + shm_unlink(SHMNAME); + + for(int i=0; i<BITMAP_SIZE; i++) { + bitmap[i] = 0; + } + + alloc_sizes.clear(); + memset(&stats, 0, sizeof stats); + + return true; +} + +void destroy_shared_memory() +{ + print_stats(); + if(munmap(pool, POOL_SIZE) == -1) { + fprintf(stderr, "Failed to unmap shared memory: %s\n", strerror(errno)); + } +} + +void *sh_malloc(size_t bytes) +{ + if(!bytes) { + return 0; + } + + int num_blocks = (bytes + BLOCK_SIZE - 1) / BLOCK_SIZE; + + int free_block; + int ctr = 0; + for(int i=0; i<NUM_BLOCKS; i++) { + if(!is_allocated(i)) { + if(!ctr) { + free_block = i; + } + ctr++; + } + else { + ctr = 0; + } + + if(ctr == num_blocks) { + alloc_blocks(free_block, num_blocks); + return block_to_addr(free_block); + } + } + + return 0; +} + +void sh_free(void *ptr) +{ + int block = addr_to_block((unsigned char*)ptr); + std::map<int, int>::iterator it; + if((it = alloc_sizes.find(block)) != alloc_sizes.end()) { + int num_blocks = it->second; + free_blocks(block, num_blocks); + alloc_sizes.erase(it); + } + else { + fprintf(stderr, "Attempt to free non-existent blocks from: %d\n", block); + } +} + +void *get_pool() +{ + return (void*)pool; +} + +static bool is_allocated(int block_number) +{ + int idx = block_number / 32; + int bit_num = block_number % 32; + + if((bitmap[idx] >> bit_num) & 1) { + return true; + } + + return false; +} + +static int addr_to_block(unsigned char *addr) +{ + assert(addr >= pool); + assert(addr < pool + POOL_SIZE); + + return (addr - pool) / BLOCK_SIZE; +} + +static unsigned char *block_to_addr(int block_number) +{ + assert(block_number >= 0); + assert(block_number < NUM_BLOCKS); + + return pool + block_number * BLOCK_SIZE; +} + +static void alloc_blocks(int block_pos, int num_blocks) +{ + for(int i=0; i<num_blocks; i++) { + int block_number = i + block_pos; + int idx = block_number / 32; + int bit_num = block_number % 32; + + bitmap[idx] |= ((uint32_t)1 << bit_num); // or pow(2, i) + } + + alloc_sizes[block_pos] = num_blocks; + + stats.alloc_num++; + stats.alloc_memsize += BLOCK_SIZE * num_blocks; +} + +static void free_blocks(int block_pos, int num_blocks) +{ + for(int i=0; i<num_blocks; i++) { + int block_number = i + block_pos; + int idx = block_number / 32; + int bit_num = block_number % 32; + + bitmap[idx] &= ~((uint32_t)1 << bit_num); + } + + stats.free_num++; + stats.free_memsize += BLOCK_SIZE * num_blocks; +} + +static void print_stats() +{ + printf("Total allocated memory: %d\n", stats.alloc_memsize); + printf("Total deallocated memory: %d\n", stats.free_memsize); + printf("Number of allocations: %d\n", stats.alloc_num); + printf("Number of deallocations: %d\n", stats.free_num); +} + |