POK
allocator.c
1 /*
2  * POK header
3  *
4  * The following file is a part of the POK project. Any modification should
5  * made according to the POK licence. You CANNOT use this file or a part of
6  * this file is this part of a file for your own project
7  *
8  * For more information on the POK licence, please see our LICENCE FILE
9  *
10  * Please follow the coding guidelines described in doc/CODING_GUIDELINES
11  *
12  * Copyright (c) 2007-2009 POK team
13  *
14  * Created by julien on Thu Jul 30 15:49:30 2009
15  */
16 
17 #include <core/dependencies.h>
18 #include <core/allocator.h>
19 
20 /*
21  * This is the allocator of POK. It remains in partition. You can configure it
22  * with POK_CONFIG_ALLOCATOR_MEMORY_SIZE (total amount of memory that can be allocated
23  * and with POK_CONFIG_ALLOCATOR_NB_SPACES (total amount of memory spaces that can be
24  * allocated (number of successive calls to malloc() or calloc() for example.
25  */
26 
27 #ifdef POK_NEEDS_ALLOCATOR
28 
29 #ifndef POK_CONFIG_ALLOCATOR_MEMORY_SIZE
30 #define POK_CONFIG_ALLOCATOR_MEMORY_SIZE 16384
31 #endif
32 
33 #ifndef POK_CONFIG_ALLOCATOR_NB_SPACES
34 #define POK_CONFIG_ALLOCATOR_NB_SPACES 100
35 #endif
36 
37 #define POK_ALLOCATOR_CHECK_INIT \
38  if (pok_allocator_initialized == 0)\
39  { \
40  uint32_t toto; \
41  for (toto = 0 ; toto < POK_CONFIG_ALLOCATOR_NB_SPACES ; toto++) \
42  { \
43  pok_allocator_spaces[toto].start = 0; \
44  pok_allocator_spaces[toto].size = 0; \
45  pok_allocator_spaces[toto].allocated = 0; \
46  } \
47  pok_allocator_used_spaces = 1; \
48  pok_allocator_spaces[0].start = 0; /* Initialize the first space */ \
49  pok_allocator_spaces[0].allocated = 0; \
50  pok_allocator_spaces[0].size = POK_CONFIG_ALLOCATOR_MEMORY_SIZE;\
51  pok_allocator_initialized = 1; \
52  }
53 
54 /* POK_ALLOCATOR_CHECK_INIT is a macro that performs initialization functions
55  * for memory allocator. It is called each time alloc or free functions are called
56  * but initialized the memory allocator only one time.
57  */
58 
59 
60 typedef struct
61 {
62  size_t start;
63  size_t size;
64  bool_t allocated;
65 } pok_allocator_space_t;
66 
67 
68 uint8_t pok_allocator_memspace[POK_CONFIG_ALLOCATOR_MEMORY_SIZE];
69 pok_allocator_space_t pok_allocator_spaces[POK_CONFIG_ALLOCATOR_NB_SPACES];
70 uint32_t pok_allocator_used_spaces = 0;
71 bool_t pok_allocator_initialized = 0;
72 
73 #ifdef POK_NEEDS_DEBUG
74 void pok_allocator_print_spaces ()
75 {
76  uint32_t space;
77  printf ("[LIBPOK] [ALLOCATOR] Used spaces = %d\n", pok_allocator_used_spaces);
78  for (space = 0 ; space < pok_allocator_used_spaces ; space++)
79  {
80  printf ("[LIBPOK] [ALLOCATOR] Space %d start=%d size=%d allocated=%d\n", space, pok_allocator_spaces[space].start, pok_allocator_spaces[space].size, pok_allocator_spaces[space].allocated);
81  }
82 }
83 #endif
84 
85 void* pok_allocator_allocate (size_t needed_size)
86 {
87  POK_ALLOCATOR_CHECK_INIT
88  uint32_t space;
89  uint32_t new_space;
90 
91  if (pok_allocator_used_spaces >= (POK_CONFIG_ALLOCATOR_NB_SPACES - 1))
92  {
93 #ifdef POK_NEEDS_DEBUG
94  printf ("[LIBPOK] [ALLOCATOR] Not enough space\n");
95 #endif
96  return NULL;
97  }
98 
99 #ifdef POK_NEEDS_DEBUG
100  printf("Try to take a new memory chunk, required space=%d\n", needed_size);
101 #endif
102 
103  for (space = 0 ; space < pok_allocator_used_spaces ; space++)
104  {
105 #ifdef POK_NEEDS_DEBUG
106  printf ("[LIBPOK] [ALLOCATOR] Look space %d, size %d, allocated=%d\n", space, pok_allocator_spaces[space].size, pok_allocator_spaces[space].allocated);
107 #endif
108  if ((pok_allocator_spaces[space].allocated == 0) && (pok_allocator_spaces[space].size >= needed_size))
109  {
110  if (pok_allocator_spaces[space].size == needed_size)
111  {
112  /*
113  * The space corresponds exactly to the requested memory space
114  */
115  pok_allocator_spaces[space].allocated = 1;
116 
117 #ifdef POK_NEEDS_DEBUG
118  printf ("[LIBPOK] [ALLOCATOR] Allocate directly space %d\n", space);
119  pok_allocator_print_spaces ();
120 #endif
121  return (&pok_allocator_memspace[pok_allocator_spaces[space].start]);
122  }
123  else
124  {
125  /*
126  * We need to split the block in two new blocks !
127  */
128  new_space = pok_allocator_used_spaces;
129  pok_allocator_used_spaces = pok_allocator_used_spaces + 1;
130 
131  pok_allocator_spaces[space].allocated = 1;
132  pok_allocator_spaces[new_space].allocated = 0;
133 
134  pok_allocator_spaces[new_space].size = pok_allocator_spaces[space].size - needed_size;
135  pok_allocator_spaces[space].size = needed_size;
136 
137  pok_allocator_spaces[new_space].start = pok_allocator_spaces[space].start + needed_size;
138 
139 #ifdef POK_NEEDS_DEBUG
140  printf("[LIBPOK] [ALLOCATOR] Allocate space %d, CREATE NEW SPACE %d (size=%d)\n", space, new_space, pok_allocator_spaces[new_space].size);
141  pok_allocator_print_spaces ();
142 #endif
143 
144  return (&pok_allocator_memspace[pok_allocator_spaces[space].start]);
145  }
146  }
147  }
148 
149 #ifdef POK_NEEDS_DEBUG
150  printf ("[LIBPOK] [ALLOCATOR] Didn't find any space for that amount of memory (%d)\n", needed_size);
151 #endif
152  return NULL;
153 }
154 
155 /*
156  * Delete a space
157  */
158 void pok_allocator_delete_space (uint32_t space)
159 {
160  uint32_t tmp;
161 
162 #ifdef POK_NEEDS_DEBUG
163  printf("[LIBPOK] [ALLOCATOR] Delete space %d\n", space);
164 #endif
165 
166  for (tmp = space ; tmp < POK_CONFIG_ALLOCATOR_NB_SPACES ; tmp++)
167  {
168  pok_allocator_spaces[tmp].allocated = pok_allocator_spaces[tmp+1].allocated;
169  pok_allocator_spaces[tmp].size = pok_allocator_spaces[tmp+1].size;
170  pok_allocator_spaces[tmp].start = pok_allocator_spaces[tmp+1].start;
171  }
172 
173  pok_allocator_used_spaces = pok_allocator_used_spaces - 1;
174 }
175 
176 void pok_allocator_merge_space (uint32_t space)
177 {
178  uint32_t space2;
179 
180  if (pok_allocator_used_spaces == 1)
181  {
182  return;
183  }
184 
185  for (space2 = 0 ; space2 < pok_allocator_used_spaces ; space2++)
186  {
187  if ((space2 == space) || (pok_allocator_spaces[space2].allocated == 1))
188  {
189  continue;
190  }
191 
192  /*
193  * In that case, space is a the end of space2. We can merge space in space2
194  */
195  if (pok_allocator_spaces[space].start == (pok_allocator_spaces[space2].start + pok_allocator_spaces[space2].size))
196  {
197 #ifdef POK_NEEDS_DEBUG
198 // printf("[LIBPOK] [ALLOCATOR] Merge space %d, with %d\n", space, space2);
199 #endif
200  pok_allocator_spaces[space2].size = pok_allocator_spaces[space2].size + pok_allocator_spaces[space].size;
201  pok_allocator_delete_space (space);
202  pok_allocator_merge_space (space2);
203  return;
204  }
205 
206  /*
207  * In that case, space2 is located at the end of space. We can merge space2 in space
208  */
209  if (pok_allocator_spaces[space2].start == (pok_allocator_spaces[space].start + pok_allocator_spaces[space].size))
210  {
211 #ifdef POK_NEEDS_DEBUG
212 // printf("[LIBPOK] [ALLOCATOR] Merge space %d, with %d\n", space, space2);
213 #endif
214  pok_allocator_spaces[space].size = pok_allocator_spaces[space].size + pok_allocator_spaces[space2].size;
215  pok_allocator_delete_space (space2);
216  pok_allocator_merge_space (space2);
217  return;
218  }
219  }
220 }
221 
222 
223 void pok_allocator_free (void* ptr)
224 {
225  POK_ALLOCATOR_CHECK_INIT
226 
227  uint32_t space;
228 
229  for (space = 0 ; space < pok_allocator_used_spaces ; space++)
230  {
231  if (ptr == &pok_allocator_memspace[pok_allocator_spaces[space].start])
232  {
233  /* Here, we find the space to free */
234  pok_allocator_spaces[space].allocated = 0;
235  pok_allocator_merge_space (space);
236 #ifdef POK_NEEDS_DEBUG
237  pok_allocator_print_spaces ();
238 #endif
239  return;
240  }
241  }
242 
243 #ifdef POK_NEEDS_DEBUG
244  printf("[LIBPOK] [ALLOCATOR] free() didn't find the space to free\n");
245  pok_allocator_print_spaces ();
246 #endif
247  return;
248 }
249 
250 #endif
251