Hosted by the courtesy of  
 GitHub 
The stars ASAP english francais spanish arab
Durée du voyage intersidéral francais
Résolutions de l'ONU en HTML francais
Bussard Ramjet english francais
DWARF : dwarf2xml english
ELF : libelf examples english
Code presentation : ctoohtml english

To rings Doc++

File Index

All Tags

Tags by File

Tags referrers

file: ring_alloc.c


  1 /*
  2 * Copyright (C) 2008-2009 by Emmanuel Azencot under the GNU LGPL
  3 * license version 2.0 or 2.1.  You should have received a copy of the
  4 * LGPL license along with this library if you did not you can find it
  5 * at http://www.gnu.org/.
  6 */

  7 /*
  8 * Azencot : Sat Dec  6 02:31:40 CET 2008
  9 *  Creation
 10 */

 11
 12 /*
 13 gcc -g -I. -I./excp -o ring_alloc ./ring.c ring_alloc.c
 14 */

 15 #include <stdlib.h>
 16 #include <string.h>
 17 #include <errno.h>
 18
 19 #include "config.h"
 20 #include "ring.h"
 21 #include "ring_alloc.h"
 22
 23 #if defined(RING_ALLOC_BLK_CHK) || defined(RING_ALLOC_POOL_CHK)
 24 #include <assert.h>
 25 #endif
 26
 27 #ifdef RING_ALLOC_POOL_CHK
 28 #undef RING_ALLOC_POOL_CHK
 29 #define /*X*/ RING_ALLOC_POOL_CHK  0x37DB5104
 30 #endif
 31 #ifdef RING_ALLOC_BLK_CHK
 32 #undef RING_ALLOC_BLK_CHK
 33 #define /*X*/ RING_ALLOC_BLK_CHK  0x37DB5104
 34 #endif
 35
 36 struct /*X*/ s_blk {
 37 #ifdef RING_ALLOC_BLK_CHK
 38   unsigned long chk_1[2];
 39 #endif
 40   struct s_ring brother;
 41   size_t size;
 42 #ifdef RING_ALLOC_BLK_CHK
 43   unsigned long chk_2[2];
 44 #endif
 45 };
 46 struct /*X*/ s_mempool {
 47 #ifdef RING_ALLOC_POOL_CHK
 48   unsigned long chk_1;
 49 #endif
 50   size_t size;
 51 #ifdef RING_ALLOC_POOL_CHK
 52   unsigned long chk_2;
 53 #endif
 54 #ifdef RING_ALLOC_STATS
 55   struct s_mempool_stats stats;
 56 #endif
 57 #ifdef RING_ALLOC_POOL_CHK
 58   unsigned long chk_3;
 59 #endif
 60   struct s_blk *alloc;
 61 #ifdef RING_ALLOC_POOL_CHK
 62   unsigned long chk_4;
 63 #endif
 64   struct s_blk *free;
 65 #ifdef RING_ALLOC_POOL_CHK
 66   unsigned long chk_5;
 67 #endif
 68   struct s_blk mem[0];
 69 };
 70 #define /*X*/ rotate(val32, bits) ( ((unsigned long)(val32))<<(bits) | ((unsigned long)(val32))>>(32-(bits)))
 71
 72 #ifdef RING_ALLOC_BLK_CHK
 73 #define /*X*/ m_blk_setup(blk) { \
 74   blk->chk_1[0] = rotate(RING_ALLOC_BLK_CHK,1) ; \
 75   blk->chk_1[1] = rotate(RING_ALLOC_BLK_CHK,2) ; \
 76   blk->chk_2[0] = rotate(RING_ALLOC_BLK_CHK,3) ; \
 77   blk->chk_2[1] = rotate(RING_ALLOC_BLK_CHK,4) ; \
 78 }

 79 #include <stdio.h>
 80 int /*X*/ f_mempool_check_blk(struct s_mempool *pool, struct s_blk *list, struct s_blk *blk) {
 81   struct s_blk *mem;
 82   int neibourgs = 0;
 83   int saved_errno = errno;
 84
 85   assert( blk );
 86   assert( pool->mem <= blk );
 87   assert( ((char *)blk + sizeof(struct s_blk) + blk->size) < ((char *)pool->mem + pool->size) );
 88   assert ( list );
 89   assert( blk->chk_1[0] == rotate(RING_ALLOC_BLK_CHK,1) );
 90   assert( blk->chk_1[1] == rotate(RING_ALLOC_BLK_CHK,2) );
 91   assert( blk->chk_2[0] == rotate(RING_ALLOC_BLK_CHK,3) );
 92   assert( blk->chk_2[1] == rotate(RING_ALLOC_BLK_CHK,4) );
 93   /* can use it cause brother is the 1st field */
 94   assert ( m_ring_is_in(blk, list, brother) );
 95
 96   // assert ( (m_ring_is_in(blk, pool->free, brother) ^ m_ring_is_in(blk, pool->alloc, brother)) );
 97   neibourgs += m_ring_is_in(blk, pool->alloc, brother);
 98   neibourgs += 2*m_ring_is_in(blk, pool->free, brother);
 99   assert ( neibourgs == 2 || neibourgs == 1 );
100   neibourgs = 0;
101
102 //   printf("\nblk   (%08x <-> %08x)\n",  blk,  ((char *)blk + blk->size + sizeof(struct s_blk)) );
103 //   printf("pool  (%08x <-> %08x)\n",  pool->mem,  ((char *)pool->mem + pool->size - sizeof(struct s_mempool)) );
104   for (mem = pool->alloc; mem; mem = m_ring_list(pool->alloc, mem, brother)) {
105 //      printf("alloc (%08x <-> %08x)\n",  mem,  ((char *)mem + mem->size + sizeof(struct s_blk)) );
106      /* bloc is behind this bloc ? */
107      if ( ((char *)mem + mem->size + sizeof(struct s_blk)) == (char *)blk ) neibourgs |= 1;
108       /* bloc is after the end of this bloc ? */
109      if ( ((char *)blk + blk->size + sizeof(struct s_blk)) == (char *)mem ) neibourgs |= 2;
110   }
111   for (mem = pool->free; mem; mem = m_ring_list(pool->free, mem, brother) ) {
112 //      printf("free  (%08x <-> %08x)\n",  mem,  ((char *)mem + mem->size + sizeof(struct s_blk)) );
113      /* bloc is behind this bloc ? */
114      if ( ((char *)mem + mem->size + sizeof(struct s_blk)) == (char *)blk ) neibourgs |= 1;
115      /* bloc is after the end of this bloc ? */
116      if ( ((char *)blk + blk->size + sizeof(struct s_blk)) == (char *)mem ) neibourgs |= 2;
117   }
118 //   printf("neibourgs = %d, ", neibourgs);
119   if ( blk == pool->mem ) neibourgs |= 1;
120   if ( ((char *)blk + blk->size + sizeof(struct s_blk)) == ((char *)pool->mem + pool->size - sizeof(struct s_mempool)) ) neibourgs |= 2;
121 //   printf("neibourgs = %d\n", neibourgs); fflush(stdout);
122   assert( neibourgs == 3 );
123   errno = saved_errno;
124   return 1;
125 }
126 #else
127 #define /*X*/ f_mempool_check_blk(list, blk) (1)
128 #define /*X*/ m_blk_setup(blk) ;
129 #endif
130
131 #ifdef RING_ALLOC_POOL_CHK
132 int /*X*/ f_mempool_check(struct s_mempool *mempool) {
133   size_t o_count_a = 0, b_count_a = 0;
134   size_t o_count_f = 0, b_count_f = 0;
135   struct s_blk *blk = mempool->free;
136   
137   assert( mempool );
138   assert( mempool->chk_1 == rotate(RING_ALLOC_POOL_CHK,1) );
139   assert( mempool->chk_2 == rotate(RING_ALLOC_POOL_CHK,2) );
140   assert( mempool->chk_3 == rotate(RING_ALLOC_POOL_CHK,3) );
141   assert( mempool->chk_4 == rotate(RING_ALLOC_POOL_CHK,4) );
142   assert( mempool->chk_5 == rotate(RING_ALLOC_POOL_CHK,5) );
143   assert( mempool->size != 0 && mempool->size < 0x80000000 );
144 #ifdef RING_ALLOC_STATS
145   assert( mempool->stats.instant.bytes.alloc <= mempool->stats.cumul.bytes.alloc );
146   assert( mempool->stats.instant.blocks.alloc <= mempool->stats.cumul.blocks.alloc );
147   assert( (sizeof(struct s_blk) * (
148               mempool->stats.instant.blocks.free +
149               mempool->stats.instant.blocks.alloc) +
150            mempool->stats.instant.bytes.free +
151            mempool->stats.instant.bytes.alloc)
152            == (mempool->size - sizeof(struct s_mempool)) );
153 #endif
154   for (blk = mempool->free; blk; blk = m_ring_list(mempool->free, blk, brother)) {
155       assert( f_mempool_check_blk(mempool, mempool->free, blk) );
156       o_count_f += blk->size;
157       ++b_count_f;
158   }
159 #ifdef RING_ALLOC_STATS
160   assert ( o_count_f == mempool->stats.instant.bytes.free );
161   assert ( b_count_f == mempool->stats.instant.blocks.free );
162 #endif
163   for (blk = mempool->alloc; blk; blk = m_ring_list(mempool->alloc, blk, brother)) {
164       assert( f_mempool_check_blk(mempool, mempool->alloc, blk) );
165       o_count_a += blk->size;
166       ++b_count_a;
167   }
168 #ifdef RING_ALLOC_STATS
169   assert ( o_count_a == mempool->stats.instant.bytes.alloc );
170   assert ( b_count_a == mempool->stats.instant.blocks.alloc );
171 #endif
172   assert( (sizeof(struct s_blk) * (b_count_a + b_count_f) + o_count_a + o_count_f)
173           == (mempool->size - sizeof(struct s_mempool)) );
174   return 1;
175 }
176 #else
177 #define /*X*/ f_mempool_check(mempool) (1)
178 #endif
179
180 to_mempool /*X*/ f_mempool_init(size_t size, void *start) {
181   struct s_mempool *pool = (typeof(pool))(start);
182   if ( !start ) { errno = EFAULT; return 0; }
183   if ( size < sizeof(struct s_mempool) + sizeof(struct s_blk)) { errno = ENOMEM; return 0; }
184   memset(pool, 0, sizeof(struct s_mempool));
185 #ifdef RING_ALLOC_POOL_CHK
186   pool->chk_1 = rotate(RING_ALLOC_POOL_CHK,1);
187   pool->chk_2 = rotate(RING_ALLOC_POOL_CHK,2);
188   pool->chk_3 = rotate(RING_ALLOC_POOL_CHK,3);
189   pool->chk_4 = rotate(RING_ALLOC_POOL_CHK,4);
190   pool->chk_5 = rotate(RING_ALLOC_POOL_CHK,5);
191 #endif
192   pool->size = size;
193   pool->alloc = 0;
194   pool->free = 0;
195   pool->free = m_ring_link(pool->free, brother, pool->mem);
196   pool->free->size = pool->size -sizeof(struct s_mempool) -sizeof(struct s_blk) ;
197   m_blk_setup(pool->free);
198 #ifdef RING_ALLOC_STATS
199   pool->stats.instant.bytes.free = pool->free->size;
200   pool->stats.instant.blocks.free = 1;
201 #endif
202   return pool;
203 }
204 int /*X*/ f_mempool_info(struct s_mempool_info *info) {
205   if ( !info ) { errno = EFAULT; return -1; }
206   info->version = RING_ALLOC_VERSION;
207   info->release = RING_ALLOC_RELEASE;
208   info->options.stats = 0;
209   info->options.chk_pool = 0;
210   info->options.chk_blk = 0;
211 #ifdef RING_ALLOC_STATS
212   info->options.stats = 1;
213 #endif
214 #ifdef RING_ALLOC_POOL_CHK
215   info->options.chk_pool = 1;
216 #endif
217 #ifdef RING_ALLOC_BLK_CHK
218   info->options.chk_blk = 1;
219 #endif
220   info->pool_head_size = sizeof(struct s_mempool); /* gcc bug ? */
221   info->block_head_size = sizeof(struct s_blk);
222   return 0;
223 }
224
225 #ifdef RING_ALLOC_STATS
226 /* stats space is provided by caller */
227 int /*X*/ f_mempool_stats(to_mempool mempool, struct s_mempool_stats *stats) {
228   f_mempool_check(mempool);
229   if ( !stats ) { errno = EFAULT; return -1; }
230   *stats = mempool->stats;
231   return 0;
232 }
233 /* increment stats alloc counters */
234 #define /*X*/ m_mempool_stats_alloc(mempool, size, split) { \
235   ++mempool->stats.instant.blocks.alloc; \
236   mempool->stats.instant.bytes.alloc += (size); \
237   mempool->stats.instant.bytes.free -= (size); \
238 \
239   ++mempool->stats.cumul.blocks.alloc; \
240   mempool->stats.cumul.bytes.alloc += (size); \
241 \
242   if ( !(split) ) { \
243      --mempool->stats.instant.blocks.free; \
244   } else { \
245      mempool->stats.instant.bytes.free -= sizeof(struct s_blk); \
246   }  \
247 }

248 /* decrement stats alloc counters */
249 #define /*X*/ m_mempool_stats_free(mempool, size, nb_cat) { \
250   --mempool->stats.instant.blocks.alloc; \
251   mempool->stats.instant.bytes.free += (size) + (nb_cat)*sizeof(struct s_blk); \
252   mempool->stats.instant.bytes.alloc -= (size); \
253 \
254   ++mempool->stats.cumul.blocks.free; \
255   mempool->stats.cumul.bytes.free += (size); \
256 \
257  mempool->stats.instant.blocks.free += (1 -(nb_cat)); \
258 }

259 #else /* RING_ALLOC_STATS */
260 /* stats not available */
261 int /*X*/ f_mempool_stats(to_mempool mempool, struct s_mempool_stats *stats) {
262   memset(stats, 0, sizeof(*stats));
263   errno = ENOTSUP; return -1;
264 }
265 /* internal use */
266 #define /*X*/ m_mempool_stats_alloc(mempool, size, split) ;
267 #define /*X*/ m_mempool_stats_free(mempool, size, nb_cat) ;
268 #endif /* RING_ALLOC_STATS */
269
270 void * /*X*/ f_mempool_malloc(to_mempool mempool, size_t size) {
271   int split = 0; /* stat */
272   struct s_blk *blk = mempool->free, *best = 0;
273   /* can help, disable/enable at compile */
274   f_mempool_check(mempool);
275   if ( !blk ) { errno = ENOMEM; return 0; }
276
277   /* find smallest free block */
278   for (blk = mempool->free; blk; blk = m_ring_list(mempool->free, blk, brother)) {
279      if ( blk->size < size ) continue;
280      if ( best && best->size < blk->size) continue;
281      best = blk;
282   }
283   /* nothing bigger enougth */
284   if ( !best ) { errno = ENOMEM; return 0; }
285   /* if best is bigger enougth to contain an other bloc, split it */
286   if ( sizeof(struct s_blk) < best->size - size ) {
287      split = 1; /* stat */
288      /* begin stays in free list, reduce size */
289      best->size -= (sizeof(struct s_blk) + size);
290      /* move to begin of new block */
291      best = (struct s_blk *)((char *)best + sizeof(struct s_blk) + best->size);
292      /* put new block in allocated */
293      best->size = size;
294      m_blk_setup(best);
295      mempool->alloc = m_ring_link(mempool->alloc, brother, best);
296   } else {
297      /* it fits well enougth, just move it to allocated blocks */
298      mempool->free = m_ring_unlink(best, brother);
299      mempool->alloc = m_ring_link(mempool->alloc, brother, best);
300   }
301   m_mempool_stats_alloc(mempool, best->size, split);
302   f_mempool_check(mempool);
303   return best+1;
304 }
305 int /*X*/ f_mempool_free(to_mempool mempool, void *mem) {
306   int cat = 0, size;
307   struct s_blk *blk = mempool->free;
308   struct s_blk *umem = (typeof(blk))mem -1;
309
310   f_mempool_check(mempool);
311   if ( !mem ) return 0;
312
313   if( mempool->mem > umem ||
314      ((char *)mempool->mem + mempool->size) <= ((char *)umem + sizeof(struct s_blk) + umem->size) ) {
315      errno = ENOTDIR;
316      return -1;
317   }
318
319   /* can use it cause brother is the 1st field */
320   if ( !m_ring_is_in(umem, mempool->alloc, brother) ) {
321      errno = ENOENT; return -1;
322   }
323   size = umem->size;
324   mempool->alloc = m_ring_unlink(umem, brother);
325   /* find if this free bloc can be collapsed to a neibourg */
326   for (blk = mempool->free; blk; blk = m_ring_list(mempool->free, blk, brother)) {
327      /* freed bloc is behind this bloc ? */
328      if ( ((char *)umem + umem->size + sizeof(struct s_blk)) == (char *)blk ) {
329         mempool->free = m_ring_unlink(blk, brother);
330         umem->size += blk->size + sizeof(struct s_blk);
331         ++cat;
332         break;
333      }
334   }
335   for (blk = mempool->free; blk; blk = m_ring_list(mempool->free, blk, brother)) {
336      /* freed bloc is at the end of this bloc ? */
337      if ( ((char *)blk + blk->size + sizeof(struct s_blk)) == (char *)umem ) {
338         blk->size += umem->size + sizeof(struct s_blk);
339         ++cat;
340         goto stats;
341      }
342   }
343   mempool->free = m_ring_link(mempool->free, brother, umem);
344 stats:
345   m_mempool_stats_free(mempool, size, cat);
346   f_mempool_check(mempool);
347   return 0;
348 }
349 void * /*X*/ f_mempool_realloc(to_mempool mempool, void *mem, size_t size) {
350   int split = 0;
351   struct s_blk *blk = mempool->free;
352   struct s_blk *umem = (typeof(blk))mem -1;
353
354   if ( !mem ) return f_mempool_malloc(mempool, size);
355   if( mempool->mem > umem ||
356      ((char *)mempool->mem + mempool->size) <= ((char *)umem + sizeof(struct s_blk) + umem->size) ) {
357      errno = ENOTDIR;
358      return 0;
359   }
360
361   if ( size < umem->size ) return mem;
362   /* need blok after */
363   for (blk = mempool->free; blk; blk = m_ring_list(mempool->free, blk, brother)) {
364      if ( ((char *)umem + umem->size + sizeof(struct s_blk)) == (char *)blk ) {
365         mempool->free = m_ring_unlink(blk, brother);
366         umem->size += blk->size + sizeof(struct s_blk);
367
368         if ( sizeof(struct s_blk) < umem->size - size ) {
369            split = 1;
370            /* begin stays in free list, reduce size */
371            umem->size -= sizeof(struct s_blk) + size;
372            /* move to begin of new block */
373            umem = (struct s_blk *)((char *)umem + sizeof(struct s_blk) + size);
374            /* put new block in allocated */
375            umem->size = size;
376            mempool->alloc = m_ring_link(mempool->alloc, brother, umem);
377         } else {
378            /* it fits well enougth, just move it to allocated blocks */
379            mempool->free = m_ring_unlink(umem, brother);
380            mempool->alloc = m_ring_link(mempool->alloc, brother, umem);
381         }
382         return umem -1;
383      }
384   }
385   if ( !(umem = f_mempool_malloc(mempool, size)) ) return 0;
386   memcpy(umem, mem, size);
387   if ( f_mempool_free(mempool, mem) < 0 ) return 0;
388   return umem -1;
389 }
390
391 void * /*X*/ f_mempool_calloc(to_mempool mempool, size_t nmemb, size_t size) {
392   void *mem;
393
394   if ( !(mem = f_mempool_malloc(mempool, nmemb*size)) == 0) return 0;
395   memset(mem, 0, nmemb*size);
396
397   return mem;
398 }
399


To rings Doc++

File Index

All Tags

Tags by File

Tags referrers

C to HTML Conversion by ctoohtml

Hosted by the courtesy of  
 GitHub 
The stars ASAP english francais spanish
Durée du voyage intersidéral francais
Résolutions de l'ONU en HTML francais
Bussard Ramjet english francais
DWARF : dwarf2xml english
ELF : libelf examples english
Code presentation : ctoohtml english