added memory allocator

[winnie] / src / shalloc.cc

diff --git a/src/shalloc.cc b/src/shalloc.cc
index d8f97dc..b5c155f 100644 (file)
--- a/src/shalloc.cc
+++ b/src/shalloc.cc
@@ -1,29 +1,171 @@
-#include <map>
+#include <assert.h>
+#include <stdio.h>
 #include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+
+#include <map>
 
 #include "shalloc.h"
 
 #define POOL_SIZE 16777216
-#define BLOCK_SIZE 1024
+#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 unsigned char *pool;
-static std::map<unsigned char*, size_t> alloc_sizes;
-//address size
+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(!(pool = (unsigned char *)malloc(POOL_SIZE))) {
                return false;
        }
+
+       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()
 {
-       //TODO print statistics
+       print_stats();
        free(pool);
 }
 
-// an zitaei 45 mb 8a vriskw posa blocks kai meta
-// 8a psaxnw tosa sunexomena bits sto bitmap
-// an den exei return 0
-// pool[arxidi]
+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);
+       }
+}
+
+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);
+}
+