Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 4973 | right-hear | 1 | /* Copyright (C) 1999 DJ Delorie, see COPYING.DJ for details */ |
| 2 | /* Copyright (C) 1998 DJ Delorie, see COPYING.DJ for details */ |
||
| 3 | /* Copyright (C) 1997 DJ Delorie, see COPYING.DJ for details */ |
||
| 4 | |||
| 5 | #include |
||
| 6 | #include |
||
| 7 | #include |
||
| 8 | #include |
||
| 9 | |||
| 10 | typedef struct BLOCK { |
||
| 11 | size_t size; |
||
| 12 | struct BLOCK *next; |
||
| 13 | int bucket; |
||
| 14 | } BLOCK; |
||
| 15 | |||
| 16 | #define BEFORE(bp) ((BLOCK *)((char *)bp - *(int *)((char *)bp - 4) - 8)) |
||
| 17 | #define BEFSZ(bp) (*(size_t *)((char *)bp - 4)) |
||
| 18 | #define ENDSZ(bp) (*(size_t *)((char *)bp + bp->size + 4)) |
||
| 19 | #define AFTER(bp) ((BLOCK *)((char *)bp + bp->size + 8)) |
||
| 20 | #define DATA(bp) ((char *)&(bp->next)) |
||
| 21 | |||
| 22 | #define NUMSMALL 0 |
||
| 23 | #define ALIGN 8 |
||
| 24 | #define SMALL (NUMSMALL*ALIGN) |
||
| 25 | |||
| 26 | DECLARE_STATIC_SEM(malloc_mutex) |
||
| 27 | |||
| 28 | static BLOCK *slop = 0; |
||
| 29 | static BLOCK *freelist[30]; |
||
| 30 | #if NUMSMALL |
||
| 31 | static BLOCK *smallblocks[NUMSMALL]; |
||
| 32 | #endif |
||
| 33 | |||
| 34 | static inline void malloc_lock(void) |
||
| 35 | { |
||
| 36 | sem_lock(&malloc_mutex); |
||
| 37 | } |
||
| 38 | |||
| 39 | static inline void malloc_unlock(void) |
||
| 40 | { |
||
| 41 | sem_unlock(&malloc_mutex); |
||
| 42 | } |
||
| 43 | |||
| 44 | #define MIN_SAVE_EXTRA 64 |
||
| 45 | #define BIG_BLOCK 4096 |
||
| 46 | |||
| 47 | #define DEBUG 0 |
||
| 48 | |||
| 49 | #if DEBUG |
||
| 50 | static void |
||
| 51 | check(BLOCK *b) |
||
| 52 | { |
||
| 53 | printf("check %08x %d %08x %d\n", b, b->size, &(ENDSZ(b)), ENDSZ(b)); |
||
| 54 | } |
||
| 55 | #define CHECK(p) do { check(p); assert(p->size == ENDSZ(p)); consistency(); } while (0) |
||
| 56 | #define CHECK1(p) do { check(p); assert(p->size == ENDSZ(p)); } while (0) |
||
| 57 | static void |
||
| 58 | consistency() |
||
| 59 | { |
||
| 60 | #if 0 |
||
| 61 | int b; |
||
| 62 | BLOCK *bl; |
||
| 63 | if (slop) |
||
| 64 | CHECK1(slop); |
||
| 65 | for (b=0; b<32; b++) |
||
| 66 | for (bl=freelist[b]; bl; bl=bl->next) |
||
| 67 | CHECK1(bl); |
||
| 68 | #endif |
||
| 69 | } |
||
| 70 | #else |
||
| 71 | #define CHECK(p) |
||
| 72 | #endif |
||
| 73 | |||
| 74 | static inline int |
||
| 75 | size2bucket(size_t size) |
||
| 76 | { |
||
| 77 | int rv=0; |
||
| 78 | size>>=2; |
||
| 79 | while (size) |
||
| 80 | { |
||
| 81 | rv++; |
||
| 82 | size>>=1; |
||
| 83 | } |
||
| 84 | return rv; |
||
| 85 | } |
||
| 86 | |||
| 87 | static inline int |
||
| 88 | b2bucket(BLOCK *b) |
||
| 89 | { |
||
| 90 | if (b->bucket == -1) |
||
| 91 | b->bucket = size2bucket(b->size); |
||
| 92 | return b->bucket; |
||
| 93 | } |
||
| 94 | |||
| 95 | static inline BLOCK * |
||
| 96 | split_block(BLOCK *b, size_t size) |
||
| 97 | { |
||
| 98 | BLOCK *rv = (BLOCK *)((char *)b + size+8); |
||
| 99 | #if DEBUG |
||
| 100 | printf(" split %u/%08x to %u/%08x, %u/%08x\n", |
||
| 101 | b->size, b, size, b, b->size - size - 8, rv); |
||
| 102 | #endif |
||
| 103 | rv->size = b->size - size - 8; |
||
| 104 | rv->bucket = -1; |
||
| 105 | b->size = size; |
||
| 106 | ENDSZ(b) = b->size; |
||
| 107 | ENDSZ(rv) = rv->size; |
||
| 108 | CHECK(b); |
||
| 109 | CHECK(rv); |
||
| 110 | return rv; |
||
| 111 | } |
||
| 112 | |||
| 113 | #define RET(rv) CHECK(rv); ENDSZ(rv) |= 1; rv->size |= 1; return DATA(rv) |
||
| 114 | |||
| 115 | void * malloc(size_t size) |
||
| 116 | { |
||
| 117 | int b, chunk_size; |
||
| 118 | BLOCK *rv, **prev; |
||
| 119 | static BLOCK *expected_sbrk = 0; |
||
| 120 | |||
| 121 | if (size |
||
| 122 | size = (size+(ALIGN-1))&~(ALIGN-1); |
||
| 123 | #if DEBUG |
||
| 124 | printf("malloc(%u)\n", size); |
||
| 125 | #endif |
||
| 126 | |||
| 127 | #if NUMSMALL |
||
| 128 | if (size < SMALL) |
||
| 129 | { |
||
| 130 | rv = smallblocks[size/ALIGN]; |
||
| 131 | if (rv) |
||
| 132 | { |
||
| 133 | smallblocks[size/ALIGN] = rv->next; |
||
| 134 | return DATA(rv); |
||
| 135 | } |
||
| 136 | } |
||
| 137 | #endif |
||
| 138 | |||
| 139 | if (slop && slop->size >= size) |
||
| 140 | { |
||
| 141 | rv = slop; |
||
| 142 | #if DEBUG |
||
| 143 | printf(" using slop %u/%08x\n", slop->size, slop); |
||
| 144 | #endif |
||
| 145 | if (slop->size >= size+MIN_SAVE_EXTRA) |
||
| 146 | { |
||
| 147 | slop = split_block(slop, size); |
||
| 148 | #if DEBUG |
||
| 149 | printf(" remaining slop %u/%08x\n", slop->size, slop); |
||
| 150 | #endif |
||
| 151 | } |
||
| 152 | else |
||
| 153 | slop = 0; |
||
| 154 | RET(rv); |
||
| 155 | } |
||
| 156 | |||
| 157 | b = size2bucket(size); |
||
| 158 | prev = &(freelist[b]); |
||
| 159 | for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next) |
||
| 160 | { |
||
| 161 | if (rv->size >= size && rv->size < size+size/4) |
||
| 162 | { |
||
| 163 | *prev = rv->next; |
||
| 164 | RET(rv); |
||
| 165 | } |
||
| 166 | } |
||
| 167 | |||
| 168 | while (b < 30) |
||
| 169 | { |
||
| 170 | prev = &(freelist[b]); |
||
| 171 | #if DEBUG |
||
| 172 | printf(" checking bucket %d\n", b); |
||
| 173 | #endif |
||
| 174 | for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next) |
||
| 175 | if (rv->size >= size) |
||
| 176 | { |
||
| 177 | #if DEBUG |
||
| 178 | printf(" found size %d/%08x\n", rv->size, rv); |
||
| 179 | #endif |
||
| 180 | *prev = rv->next; |
||
| 181 | if (rv->size >= size+MIN_SAVE_EXTRA) |
||
| 182 | { |
||
| 183 | #if DEBUG |
||
| 184 | printf(" enough to save\n"); |
||
| 185 | #endif |
||
| 186 | if (slop) |
||
| 187 | { |
||
| 188 | b = b2bucket(slop); |
||
| 189 | #if DEBUG |
||
| 190 | printf(" putting old slop %u/%08x on free list %d\n", |
||
| 191 | slop->size, slop, b); |
||
| 192 | #endif |
||
| 193 | slop->next = freelist[b]; |
||
| 194 | freelist[b] = slop; |
||
| 195 | } |
||
| 196 | slop = split_block(rv, size); |
||
| 197 | #if DEBUG |
||
| 198 | printf(" slop size %u/%08x\n", slop->size, slop); |
||
| 199 | #endif |
||
| 200 | } |
||
| 201 | RET(rv); |
||
| 202 | } |
||
| 203 | b++; |
||
| 204 | } |
||
| 205 | |||
| 206 | chunk_size = size+16; /* two ends plus two placeholders */ |
||
| 207 | rv = (BLOCK *)sbrk(chunk_size); |
||
| 208 | if (rv == (BLOCK *)(-1)) |
||
| 209 | return 0; |
||
| 210 | #if DEBUG |
||
| 211 | printf("sbrk(%d) -> %08x, expected %08x\n", chunk_size, rv, expected_sbrk); |
||
| 212 | #endif |
||
| 213 | if (rv == expected_sbrk) |
||
| 214 | { |
||
| 215 | expected_sbrk = (BLOCK *)((char *)rv + chunk_size); |
||
| 216 | /* absorb old end-block-marker */ |
||
| 217 | #if DEBUG |
||
| 218 | printf(" got expected sbrk\n"); |
||
| 219 | #endif |
||
| 220 | rv = (BLOCK *)((char *)rv - 4); |
||
| 221 | } |
||
| 222 | else |
||
| 223 | { |
||
| 224 | expected_sbrk = (BLOCK *)((char *)rv + chunk_size); |
||
| 225 | #if DEBUG |
||
| 226 | printf(" disconnected sbrk\n"); |
||
| 227 | #endif |
||
| 228 | /* build start-block-marker */ |
||
| 229 | rv->size = 1; |
||
| 230 | rv = (BLOCK *)((char *)rv + 4); |
||
| 231 | chunk_size -= 8; |
||
| 232 | } |
||
| 233 | rv->size = chunk_size - 8; |
||
| 234 | ENDSZ(rv) = rv->size; |
||
| 235 | AFTER(rv)->size = 1; |
||
| 236 | CHECK(rv); |
||
| 237 | |||
| 238 | RET(rv); |
||
| 239 | } |
||
| 240 | |||
| 241 | static inline BLOCK * |
||
| 242 | merge(BLOCK *a, BLOCK *b, BLOCK *c) |
||
| 243 | { |
||
| 244 | int bu; |
||
| 245 | BLOCK *bp, **bpp; |
||
| 246 | |||
| 247 | #if DEBUG |
||
| 248 | printf(" merge %u/%08x + %u/%08x = %u\n", |
||
| 249 | a->size, a, b->size, b, a->size+b->size+8); |
||
| 250 | #endif |
||
| 251 | |||
| 252 | CHECK(a); |
||
| 253 | CHECK(b); |
||
| 254 | CHECK(c); |
||
| 255 | if (c == slop) |
||
| 256 | { |
||
| 257 | #if DEBUG |
||
| 258 | printf(" snipping slop %u/%08x\n", slop->size, slop); |
||
| 259 | #endif |
||
| 260 | slop = 0; |
||
| 261 | } |
||
| 262 | bu = b2bucket(c); |
||
| 263 | #if DEBUG |
||
| 264 | printf("bucket for %u/%08x is %d\n", c->size, c, bu); |
||
| 265 | #endif |
||
| 266 | bpp = freelist+bu; |
||
| 267 | for (bp=freelist[bu]; bp; bpp=&(bp->next), bp=bp->next) |
||
| 268 | { |
||
| 269 | #if DEBUG |
||
| 270 | printf(" %08x", bp); |
||
| 271 | #endif |
||
| 272 | if (bp == c) |
||
| 273 | { |
||
| 274 | #if DEBUG |
||
| 275 | printf("\n snipping %u/%08x from freelist[%d]\n", bp->size, bp, bu); |
||
| 276 | #endif |
||
| 277 | *bpp = bp->next; |
||
| 278 | break; |
||
| 279 | } |
||
| 280 | } |
||
| 281 | CHECK(c); |
||
| 282 | |||
| 283 | a->size += b->size + 8; |
||
| 284 | a->bucket = -1; |
||
| 285 | ENDSZ(a) = a->size; |
||
| 286 | |||
| 287 | CHECK(a); |
||
| 288 | return a; |
||
| 289 | } |
||
| 290 | |||
| 291 | void |
||
| 292 | free(void *ptr) |
||
| 293 | { |
||
| 294 | int b; |
||
| 295 | BLOCK *block; |
||
| 296 | if (ptr == 0) |
||
| 297 | return; |
||
| 298 | block = (BLOCK *)((char *)ptr-4); |
||
| 299 | |||
| 300 | #if NUMSMALL |
||
| 301 | if (block->size < SMALL) |
||
| 302 | { |
||
| 303 | block->next = smallblocks[block->size/ALIGN]; |
||
| 304 | smallblocks[block->size/ALIGN] = block; |
||
| 305 | return; |
||
| 306 | } |
||
| 307 | #endif |
||
| 308 | |||
| 309 | block->size &= ~1; |
||
| 310 | ENDSZ(block) &= ~1; |
||
| 311 | block->bucket = -1; |
||
| 312 | #if DEBUG |
||
| 313 | printf("free(%u/%08x)\n", block->size, block); |
||
| 314 | #endif |
||
| 315 | |||
| 316 | CHECK(block); |
||
| 317 | if (! (AFTER(block)->size & 1)) |
||
| 318 | { |
||
| 319 | CHECK(AFTER(block)); |
||
| 320 | } |
||
| 321 | if (! (BEFSZ(block) & 1)) |
||
| 322 | { |
||
| 323 | CHECK(BEFORE(block)); |
||
| 324 | block = merge(BEFORE(block), block, BEFORE(block)); |
||
| 325 | } |
||
| 326 | CHECK(block); |
||
| 327 | if (! (AFTER(block)->size & 1)) |
||
| 328 | { |
||
| 329 | CHECK(AFTER(block)); |
||
| 330 | block = merge(block, AFTER(block), AFTER(block)); |
||
| 331 | } |
||
| 332 | CHECK(block); |
||
| 333 | |||
| 334 | b = b2bucket(block); |
||
| 335 | block->next = freelist[b]; |
||
| 336 | freelist[b] = block; |
||
| 337 | CHECK(block); |
||
| 338 | } |
||
| 339 | |||
| 340 | void * realloc(void *ptr, size_t size) |
||
| 341 | { |
||
| 342 | BLOCK *b; |
||
| 343 | char *newptr; |
||
| 344 | size_t copysize; |
||
| 345 | if (ptr == 0) return malloc(size); |
||
| 346 | b = (BLOCK *)((char *)ptr-4); |
||
| 347 | copysize = b->size & ~1; |
||
| 348 | if (size <= copysize) |
||
| 349 | { |
||
| 350 | return ptr; |
||
| 351 | copysize = size; |
||
| 352 | } |
||
| 353 | newptr = (char *)malloc(size); |
||
| 354 | if (!newptr) return NULL; |
||
| 355 | memcpy(newptr, ptr, copysize); |
||
| 356 | free(ptr); |
||
| 357 | return newptr; |
||
| 358 | } |