Ring containers source code: ring

Hosted by the courtesy of

The stars ASAP

Durée du voyage intersidéral

Résolutions de l'ONU en HTML

Bussard Ramjet

DWARF : dwarf2xml

ELF : libelf examples

Code presentation : ctoohtml

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