17 #define SHMNAME "/winnie.shm"
19 #define POOL_SIZE 16777216
20 #define BLOCK_SIZE 512
22 #define NUM_BLOCKS (POOL_SIZE / BLOCK_SIZE)
23 #define BITMAP_SIZE (NUM_BLOCKS / 32)
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);
31 static void print_stats();
34 static unsigned char *pool;
35 static std::map<int, int> alloc_sizes; //starting block -> number of blocks
37 // 0 means not allocated 1 means allocated
38 static uint32_t bitmap[BITMAP_SIZE];
47 static Statistics stats;
49 bool init_shared_memory()
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));
55 ftruncate(fd, POOL_SIZE);
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));
64 for(int i=0; i<BITMAP_SIZE; i++) {
69 memset(&stats, 0, sizeof stats);
74 void destroy_shared_memory()
77 if(munmap(pool, POOL_SIZE) == -1) {
78 fprintf(stderr, "Failed to unmap shared memory: %s\n", strerror(errno));
82 void *sh_malloc(size_t bytes)
88 int num_blocks = (bytes + BLOCK_SIZE - 1) / BLOCK_SIZE;
92 for(int i=0; i<NUM_BLOCKS; i++) {
93 if(!is_allocated(i)) {
103 if(ctr == num_blocks) {
104 alloc_blocks(free_block, num_blocks);
105 return block_to_addr(free_block);
112 void sh_free(void *ptr)
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);
122 fprintf(stderr, "Attempt to free non-existent blocks from: %d\n", block);
126 static bool is_allocated(int block_number)
128 int idx = block_number / 32;
129 int bit_num = block_number % 32;
131 if((bitmap[idx] >> bit_num) & 1) {
138 static int addr_to_block(unsigned char *addr)
140 assert(addr >= pool);
141 assert(addr < pool + POOL_SIZE);
143 return (addr - pool) / BLOCK_SIZE;
146 static unsigned char *block_to_addr(int block_number)
148 assert(block_number >= 0);
149 assert(block_number < NUM_BLOCKS);
151 return pool + block_number * BLOCK_SIZE;
154 static void alloc_blocks(int block_pos, int num_blocks)
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;
161 bitmap[idx] |= ((uint32_t)1 << bit_num); // or pow(2, i)
164 alloc_sizes[block_pos] = num_blocks;
167 stats.alloc_memsize += BLOCK_SIZE * num_blocks;
170 static void free_blocks(int block_pos, int num_blocks)
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;
177 bitmap[idx] &= ~((uint32_t)1 << bit_num);
181 stats.free_memsize += BLOCK_SIZE * num_blocks;
184 static void print_stats()
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);