created libwinnie (library), winnie (the server application) and clients
[winnie] / 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 <stdlib.h>
25 #include <stdint.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 SHMNAME "/winnie.shm"
39
40 #define POOL_SIZE 16777216
41 #define BLOCK_SIZE 512
42
43 #define NUM_BLOCKS (POOL_SIZE / BLOCK_SIZE)
44 #define BITMAP_SIZE (NUM_BLOCKS / 32)
45
46 static bool is_allocated(int block_number);
47 static int addr_to_block(unsigned char *addr);
48 static unsigned char *block_to_addr(int block_number);
49 static void alloc_blocks(int block_pos, int num_blocks);
50 static void free_blocks(int block_pos, int num_blocks);
51
52 static void print_stats();
53 static int fd;
54
55 static unsigned char *pool;
56 static std::map<int, int> alloc_sizes; //starting block -> number of blocks
57
58 // 0 means not allocated 1 means allocated
59 static uint32_t bitmap[BITMAP_SIZE];
60
61 struct Statistics {
62         int alloc_num;
63         int free_num;
64         int alloc_memsize;
65         int free_memsize;
66 };
67
68 static Statistics stats;
69
70 bool init_shared_memory()
71 {
72         if(((fd = shm_open(SHMNAME, O_RDWR | O_CREAT, S_IRWXU)) == -1)) {
73                 fprintf(stderr, "Failed to open shared memory: %s\n", strerror(errno));
74                 return false;
75         }
76         ftruncate(fd, POOL_SIZE);
77
78         if((pool = (unsigned char*)mmap(0, POOL_SIZE, PROT_READ | PROT_WRITE,
79                                         MAP_SHARED, fd, 0)) == (void*)-1) {
80                 fprintf(stderr, "Failed to map shared memory: %s\n", strerror(errno));
81         }
82
83         shm_unlink(SHMNAME);
84
85         for(int i=0; i<BITMAP_SIZE; i++) {
86                 bitmap[i] = 0;
87         }
88
89         alloc_sizes.clear();
90         memset(&stats, 0, sizeof stats);
91
92         return true;
93 }
94
95 void destroy_shared_memory()
96 {
97         print_stats();
98         if(munmap(pool, POOL_SIZE) == -1) {
99                 fprintf(stderr, "Failed to unmap shared memory: %s\n", strerror(errno));
100         }
101 }
102
103 void *sh_malloc(size_t bytes)
104 {
105         if(!bytes) {
106                 return 0;
107         }
108
109         int num_blocks = (bytes + BLOCK_SIZE - 1) / BLOCK_SIZE;
110         
111         int free_block;
112         int ctr = 0;
113         for(int i=0; i<NUM_BLOCKS; i++) {
114                 if(!is_allocated(i)) {
115                         if(!ctr) {
116                                 free_block = i;
117                         }
118                         ctr++;
119                 }
120                 else {
121                         ctr = 0;
122                 }
123
124                 if(ctr == num_blocks) {
125                         alloc_blocks(free_block, num_blocks);
126                         return block_to_addr(free_block);
127                 }
128         }
129
130         return 0;
131 }
132
133 void sh_free(void *ptr)
134 {
135         int block = addr_to_block((unsigned char*)ptr);
136         std::map<int, int>::iterator it;
137         if((it = alloc_sizes.find(block)) != alloc_sizes.end()) {
138                 int num_blocks = it->second;
139                 free_blocks(block, num_blocks);
140                 alloc_sizes.erase(it);
141         }
142         else {
143                 fprintf(stderr, "Attempt to free non-existent blocks from: %d\n", block);
144         }
145 }
146
147 void *get_pool()
148 {
149         return (void*)pool;
150 }
151
152 static bool is_allocated(int block_number)
153 {
154         int idx = block_number / 32;
155         int bit_num = block_number % 32;
156
157         if((bitmap[idx] >> bit_num) & 1) {
158                 return true;
159         }
160
161         return false;
162 }
163
164 static int addr_to_block(unsigned char *addr)
165 {
166         assert(addr >= pool);
167         assert(addr < pool + POOL_SIZE);
168
169         return (addr - pool) / BLOCK_SIZE;
170 }
171
172 static unsigned char *block_to_addr(int block_number)
173 {
174         assert(block_number >= 0);
175         assert(block_number < NUM_BLOCKS);
176
177         return pool + block_number * BLOCK_SIZE;
178 }
179
180 static void alloc_blocks(int block_pos, int num_blocks)
181 {
182         for(int i=0; i<num_blocks; i++) {
183                 int block_number = i + block_pos;
184                 int idx = block_number / 32;
185                 int bit_num = block_number % 32;
186         
187                 bitmap[idx] |= ((uint32_t)1 << bit_num); // or pow(2, i)
188         }
189
190         alloc_sizes[block_pos] = num_blocks;
191
192         stats.alloc_num++;
193         stats.alloc_memsize += BLOCK_SIZE * num_blocks;
194 }
195
196 static void free_blocks(int block_pos, int num_blocks)
197 {
198         for(int i=0; i<num_blocks; i++) {
199                 int block_number = i + block_pos;
200                 int idx = block_number / 32;
201                 int bit_num = block_number % 32;
202
203                 bitmap[idx] &= ~((uint32_t)1 << bit_num);
204         }
205
206         stats.free_num++;
207         stats.free_memsize += BLOCK_SIZE * num_blocks;
208 }
209
210 static void print_stats()
211 {
212         printf("Total allocated memory: %d\n", stats.alloc_memsize);
213         printf("Total deallocated memory: %d\n", stats.free_memsize);
214         printf("Number of allocations: %d\n", stats.alloc_num);
215         printf("Number of deallocations: %d\n", stats.free_num);
216 }
217