Bug Summary

File:malloc/malloc.c
Location:line 362, column 12
Description:The left operand of '&' is a garbage value

Annotated Source Code

1#define _GNU_SOURCE
2#include <stdlib.h>
3#include <string.h>
4#include <limits.h>
5#include <stdint.h>
6#include <errno(*__errno_location()).h>
7#include <sys/mman.h>
8#include "libc.h"
9#include "atomic.h"
10#include "pthread_impl.h"
11
12#if defined(__GNUC__4) && defined(__PIC__)
13#define inline inline __attribute__((always_inline))
14#endif
15
16void *__mmap(void *, size_t, int, int, int, off_t);
17int __munmap(void *, size_t);
18void *__mremap(void *, size_t, size_t, int, ...);
19int __madvise(void *, size_t, int);
20
21struct chunk {
22 size_t psize, csize;
23 struct chunk *next, *prev;
24};
25
26struct bin {
27 volatile int lock[2];
28 struct chunk *head;
29 struct chunk *tail;
30};
31
32static struct {
33 volatile uint64_t binmap;
34 struct bin bins[64];
35 volatile int free_lock[2];
36} mal;
37
38
39#define SIZE_ALIGN(4*sizeof(size_t)) (4*sizeof(size_t))
40#define SIZE_MASK(-(4*sizeof(size_t))) (-SIZE_ALIGN(4*sizeof(size_t)))
41#define OVERHEAD(2*sizeof(size_t)) (2*sizeof(size_t))
42#define MMAP_THRESHOLD(0x1c00*(4*sizeof(size_t))) (0x1c00*SIZE_ALIGN(4*sizeof(size_t)))
43#define DONTCARE16 16
44#define RECLAIM163840 163840
45
46#define CHUNK_SIZE(c)((c)->csize & -2) ((c)->csize & -2)
47#define CHUNK_PSIZE(c)((c)->psize & -2) ((c)->psize & -2)
48#define PREV_CHUNK(c)((struct chunk *)((char *)(c) - ((c)->psize & -2))) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c)((c)->psize & -2)))
49#define NEXT_CHUNK(c)((struct chunk *)((char *)(c) + ((c)->csize & -2))) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c)((c)->csize & -2)))
50#define MEM_TO_CHUNK(p)(struct chunk *)((char *)(p) - (2*sizeof(size_t))) (struct chunk *)((char *)(p) - OVERHEAD(2*sizeof(size_t)))
51#define CHUNK_TO_MEM(c)(void *)((char *)(c) + (2*sizeof(size_t))) (void *)((char *)(c) + OVERHEAD(2*sizeof(size_t)))
52#define BIN_TO_CHUNK(i)((struct chunk *)((char *)(&mal.bins[i].head) - (2*sizeof
(size_t)))) (MEM_TO_CHUNK(&mal.bins[i].head)(struct chunk *)((char *)(&mal.bins[i].head) - (2*sizeof(
size_t))))
53
54#define C_INUSE((size_t)1) ((size_t)1)
55
56#define IS_MMAPPED(c)!((c)->csize & (((size_t)1))) !((c)->csize & (C_INUSE((size_t)1)))
57
58
59/* Synchronization tools */
60
61static inline void lock(volatile int *lk)
62{
63 if (libc__libc.threads_minus_1)
64 while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
65}
66
67static inline void unlock(volatile int *lk)
68{
69 if (lk[0]) {
70 a_store(lk, 0);
71 if (lk[1]) __wake(lk, 1, 1);
72 }
73}
74
75static inline void lock_bin(int i)
76{
77 lock(mal.bins[i].lock);
78 if (!mal.bins[i].head)
79 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i)((struct chunk *)((char *)(&mal.bins[i].head) - (2*sizeof
(size_t))));
80}
81
82static inline void unlock_bin(int i)
83{
84 unlock(mal.bins[i].lock);
85}
86
87static int first_set(uint64_t x)
88{
89#if 1
90 return a_ctz_64(x);
91#else
92 static const char debruijn64[64] = {
93 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
94 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
95 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
96 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
97 };
98 static const char debruijn32[32] = {
99 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
100 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
101 };
102 if (sizeof(long) < 8) {
103 uint32_t y = x;
104 if (!y) {
105 y = x>>32;
106 return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
107 }
108 return debruijn32[(y&-y)*0x076be629 >> 27];
109 }
110 return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
111#endif
112}
113
114static int bin_index(size_t x)
115{
116 x = x / SIZE_ALIGN(4*sizeof(size_t)) - 1;
117 if (x <= 32) return x;
118 if (x > 0x1c00) return 63;
119 return ((union { float v; uint32_t r; }){(int)x}.r>>21) - 496;
120}
121
122static int bin_index_up(size_t x)
123{
124 x = x / SIZE_ALIGN(4*sizeof(size_t)) - 1;
125 if (x <= 32) return x;
126 return ((union { float v; uint32_t r; }){(int)x}.r+0x1fffff>>21) - 496;
127}
128
129#if 0
130void __dump_heap(int x)
131{
132 struct chunk *c;
133 int i;
134 for (c = (void *)mal.heap; CHUNK_SIZE(c)((c)->csize & -2); c = NEXT_CHUNK(c)((struct chunk *)((char *)(c) + ((c)->csize & -2))))
135 fprintf(stderr(stderr), "base %p size %zu (%d) flags %d/%d\n",
136 c, CHUNK_SIZE(c)((c)->csize & -2), bin_index(CHUNK_SIZE(c)((c)->csize & -2)),
137 c->csize & 15,
138 NEXT_CHUNK(c)((struct chunk *)((char *)(c) + ((c)->csize & -2)))->psize & 15);
139 for (i=0; i<64; i++) {
140 if (mal.bins[i].head != BIN_TO_CHUNK(i)((struct chunk *)((char *)(&mal.bins[i].head) - (2*sizeof
(size_t)))) && mal.bins[i].head) {
141 fprintf(stderr(stderr), "bin %d: %p\n", i, mal.bins[i].head);
142 if (!(mal.binmap & 1ULL<<i))
143 fprintf(stderr(stderr), "missing from binmap!\n");
144 } else if (mal.binmap & 1ULL<<i)
145 fprintf(stderr(stderr), "binmap wrongly contains %d!\n", i);
146 }
147}
148#endif
149
150void *__expand_heap(size_t *);
151
152static struct chunk *expand_heap(size_t n)
153{
154 static int heap_lock[2];
155 static void *end;
156 void *p;
157 struct chunk *w;
158
159 /* The argument n already accounts for the caller's chunk
160 * overhead needs, but if the heap can't be extended in-place,
161 * we need room for an extra zero-sized sentinel chunk. */
162 n += SIZE_ALIGN(4*sizeof(size_t));
163
164 lock(heap_lock);
165
166 p = __expand_heap(&n);
167 if (!p) {
168 unlock(heap_lock);
169 return 0;
170 }
171
172 /* If not just expanding existing space, we need to make a
173 * new sentinel chunk below the allocated space. */
174 if (p != end) {
175 /* Valid/safe because of the prologue increment. */
176 n -= SIZE_ALIGN(4*sizeof(size_t));
177 p = (char *)p + SIZE_ALIGN(4*sizeof(size_t));
178 w = MEM_TO_CHUNK(p)(struct chunk *)((char *)(p) - (2*sizeof(size_t)));
179 w->psize = 0 | C_INUSE((size_t)1);
180 }
181
182 /* Record new heap end and fill in footer. */
183 end = (char *)p + n;
184 w = MEM_TO_CHUNK(end)(struct chunk *)((char *)(end) - (2*sizeof(size_t)));
185 w->psize = n | C_INUSE((size_t)1);
186 w->csize = 0 | C_INUSE((size_t)1);
187
188 /* Fill in header, which may be new or may be replacing a
189 * zero-size sentinel header at the old end-of-heap. */
190 w = MEM_TO_CHUNK(p)(struct chunk *)((char *)(p) - (2*sizeof(size_t)));
191 w->csize = n | C_INUSE((size_t)1);
192
193 unlock(heap_lock);
194
195 return w;
196}
197
198static int adjust_size(size_t *n)
199{
200 /* Result of pointer difference must fit in ptrdiff_t. */
201 if (*n-1 > PTRDIFF_MAX(0x7fffffffffffffff) - SIZE_ALIGN(4*sizeof(size_t)) - PAGE_SIZE4096) {
202 if (*n) {
203 errno(*__errno_location()) = ENOMEM12;
204 return -1;
205 } else {
206 *n = SIZE_ALIGN(4*sizeof(size_t));
207 return 0;
208 }
209 }
210 *n = (*n + OVERHEAD(2*sizeof(size_t)) + SIZE_ALIGN(4*sizeof(size_t)) - 1) & SIZE_MASK(-(4*sizeof(size_t)));
211 return 0;
212}
213
214static void unbin(struct chunk *c, int i)
215{
216 if (c->prev == c->next)
217 a_and_64(&mal.binmap, ~(1ULL<<i));
218 c->prev->next = c->next;
219 c->next->prev = c->prev;
220 c->csize |= C_INUSE((size_t)1);
221 NEXT_CHUNK(c)((struct chunk *)((char *)(c) + ((c)->csize & -2)))->psize |= C_INUSE((size_t)1);
222}
223
224static int alloc_fwd(struct chunk *c)
225{
226 int i;
227 size_t k;
228 while (!((k=c->csize) & C_INUSE((size_t)1))) {
229 i = bin_index(k);
230 lock_bin(i);
231 if (c->csize == k) {
232 unbin(c, i);
233 unlock_bin(i);
234 return 1;
235 }
236 unlock_bin(i);
237 }
238 return 0;
239}
240
241static int alloc_rev(struct chunk *c)
242{
243 int i;
244 size_t k;
245 while (!((k=c->psize) & C_INUSE((size_t)1))) {
246 i = bin_index(k);
247 lock_bin(i);
248 if (c->psize == k) {
249 unbin(PREV_CHUNK(c)((struct chunk *)((char *)(c) - ((c)->psize & -2))), i);
250 unlock_bin(i);
251 return 1;
252 }
253 unlock_bin(i);
254 }
255 return 0;
256}
257
258
259/* pretrim - trims a chunk _prior_ to removing it from its bin.
260 * Must be called with i as the ideal bin for size n, j the bin
261 * for the _free_ chunk self, and bin j locked. */
262static int pretrim(struct chunk *self, size_t n, int i, int j)
263{
264 size_t n1;
265 struct chunk *next, *split;
266
267 /* We cannot pretrim if it would require re-binning. */
268 if (j < 40) return 0;
269 if (j < i+3) {
270 if (j != 63) return 0;
271 n1 = CHUNK_SIZE(self)((self)->csize & -2);
272 if (n1-n <= MMAP_THRESHOLD(0x1c00*(4*sizeof(size_t)))) return 0;
273 } else {
274 n1 = CHUNK_SIZE(self)((self)->csize & -2);
275 }
276 if (bin_index(n1-n) != j) return 0;
277
278 next = NEXT_CHUNK(self)((struct chunk *)((char *)(self) + ((self)->csize & -2
)));
279 split = (void *)((char *)self + n);
280
281 split->prev = self->prev;
282 split->next = self->next;
283 split->prev->next = split;
284 split->next->prev = split;
285 split->psize = n | C_INUSE((size_t)1);
286 split->csize = n1-n;
287 next->psize = n1-n;
288 self->csize = n | C_INUSE((size_t)1);
289 return 1;
290}
291
292static void trim(struct chunk *self, size_t n)
293{
294 size_t n1 = CHUNK_SIZE(self)((self)->csize & -2);
295 struct chunk *next, *split;
296
297 if (n >= n1 - DONTCARE16) return;
298
299 next = NEXT_CHUNK(self)((struct chunk *)((char *)(self) + ((self)->csize & -2
)));
300 split = (void *)((char *)self + n);
301
302 split->psize = n | C_INUSE((size_t)1);
303 split->csize = n1-n | C_INUSE((size_t)1);
304 next->psize = n1-n | C_INUSE((size_t)1);
305 self->csize = n | C_INUSE((size_t)1);
306
307 free(CHUNK_TO_MEM(split)(void *)((char *)(split) + (2*sizeof(size_t))));
308}
309
310void *malloc(size_t n)
311{
312 struct chunk *c;
313 int i, j;
314
315 if (adjust_size(&n) < 0) return 0;
316
317 if (n > MMAP_THRESHOLD(0x1c00*(4*sizeof(size_t)))) {
318 size_t len = n + OVERHEAD(2*sizeof(size_t)) + PAGE_SIZE4096 - 1 & -PAGE_SIZE4096;
319 char *base = __mmap(0, len, PROT_READ1|PROT_WRITE2,
320 MAP_PRIVATE0x02|MAP_ANONYMOUS0x20, -1, 0);
321 if (base == (void *)-1) return 0;
322 c = (void *)(base + SIZE_ALIGN(4*sizeof(size_t)) - OVERHEAD(2*sizeof(size_t)));
323 c->csize = len - (SIZE_ALIGN(4*sizeof(size_t)) - OVERHEAD(2*sizeof(size_t)));
324 c->psize = SIZE_ALIGN(4*sizeof(size_t)) - OVERHEAD(2*sizeof(size_t));
325 return CHUNK_TO_MEM(c)(void *)((char *)(c) + (2*sizeof(size_t)));
326 }
327
328 i = bin_index_up(n);
329 for (;;) {
330 uint64_t mask = mal.binmap & -(1ULL<<i);
331 if (!mask) {
332 c = expand_heap(n);
333 if (!c) return 0;
334 if (alloc_rev(c)) {
335 struct chunk *x = c;
336 c = PREV_CHUNK(c)((struct chunk *)((char *)(c) - ((c)->psize & -2)));
337 NEXT_CHUNK(x)((struct chunk *)((char *)(x) + ((x)->csize & -2)))->psize = c->csize =
338 x->csize + CHUNK_SIZE(c)((c)->csize & -2);
339 }
340 break;
341 }
342 j = first_set(mask);
343 lock_bin(j);
344 c = mal.bins[j].head;
345 if (c != BIN_TO_CHUNK(j)((struct chunk *)((char *)(&mal.bins[j].head) - (2*sizeof
(size_t))))) {
346 if (!pretrim(c, n, i, j)) unbin(c, j);
347 unlock_bin(j);
348 break;
349 }
350 unlock_bin(j);
351 }
352
353 /* Now patch up in case we over-allocated */
354 trim(c, n);
355
356 return CHUNK_TO_MEM(c)(void *)((char *)(c) + (2*sizeof(size_t)));
357}
358
359void *__malloc0(size_t n)
360{
361 void *p = malloc(n);
1
Uninitialized value stored to field 'csize'
→
362 if (p && !IS_MMAPPED(MEM_TO_CHUNK(p))!(((struct chunk *)((char *)(p) - (2*sizeof(size_t))))->csize
& (((size_t)1)))) {
2
←
Within the expansion of the macro 'IS_MMAPPED':
a
The left operand of '&' is a garbage value
363 size_t *z;
364 n = (n + sizeof *z - 1)/sizeof *z;
365 for (z=p; n; n--, z++) if (*z) *z=0;
366 }
367 return p;
368}
369
370void *realloc(void *p, size_t n)
371{
372 struct chunk *self, *next;
373 size_t n0, n1;
374 void *new;
375
376 if (!p) return malloc(n);
377
378 if (adjust_size(&n) < 0) return 0;
379
380 self = MEM_TO_CHUNK(p)(struct chunk *)((char *)(p) - (2*sizeof(size_t)));
381 n1 = n0 = CHUNK_SIZE(self)((self)->csize & -2);
382
383 if (IS_MMAPPED(self)!((self)->csize & (((size_t)1)))) {
384 size_t extra = self->psize;
385 char *base = (char *)self - extra;
386 size_t oldlen = n0 + extra;
387 size_t newlen = n + extra;
388 /* Crash on realloc of freed chunk */
389 if (extra & 1) a_crash();
390 if (newlen < PAGE_SIZE4096 && (new = malloc(n))) {
391 memcpy(new, p, n-OVERHEAD(2*sizeof(size_t)));
392 free(p);
393 return new;
394 }
395 newlen = (newlen + PAGE_SIZE4096-1) & -PAGE_SIZE4096;
396 if (oldlen == newlen) return p;
397 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE1);
398 if (base == (void *)-1)
399 return newlen < oldlen ? p : 0;
400 self = (void *)(base + extra);
401 self->csize = newlen - extra;
402 return CHUNK_TO_MEM(self)(void *)((char *)(self) + (2*sizeof(size_t)));
403 }
404
405 next = NEXT_CHUNK(self)((struct chunk *)((char *)(self) + ((self)->csize & -2
)));
406
407 /* Crash on corrupted footer (likely from buffer overflow) */
408 if (next->psize != self->csize) a_crash();
409
410 /* Merge adjacent chunks if we need more space. This is not
411 * a waste of time even if we fail to get enough space, because our
412 * subsequent call to free would otherwise have to do the merge. */
413 if (n > n1 && alloc_fwd(next)) {
414 n1 += CHUNK_SIZE(next)((next)->csize & -2);
415 next = NEXT_CHUNK(next)((struct chunk *)((char *)(next) + ((next)->csize & -2
)));
416 }
417 /* FIXME: find what's wrong here and reenable it..? */
418 if (0 && n > n1 && alloc_rev(self)) {
419 self = PREV_CHUNK(self)((struct chunk *)((char *)(self) - ((self)->psize & -2
)));
420 n1 += CHUNK_SIZE(self)((self)->csize & -2);
421 }
422 self->csize = n1 | C_INUSE((size_t)1);
423 next->psize = n1 | C_INUSE((size_t)1);
424
425 /* If we got enough space, split off the excess and return */
426 if (n <= n1) {
427 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
428 trim(self, n);
429 return CHUNK_TO_MEM(self)(void *)((char *)(self) + (2*sizeof(size_t)));
430 }
431
432 /* As a last resort, allocate a new chunk and copy to it. */
433 new = malloc(n-OVERHEAD(2*sizeof(size_t)));
434 if (!new) return 0;
435 memcpy(new, p, n0-OVERHEAD(2*sizeof(size_t)));
436 free(CHUNK_TO_MEM(self)(void *)((char *)(self) + (2*sizeof(size_t))));
437 return new;
438}
439
440void free(void *p)
441{
442 struct chunk *self = MEM_TO_CHUNK(p)(struct chunk *)((char *)(p) - (2*sizeof(size_t)));
443 struct chunk *next;
444 size_t final_size, new_size, size;
445 int reclaim=0;
446 int i;
447
448 if (!p) return;
449
450 if (IS_MMAPPED(self)!((self)->csize & (((size_t)1)))) {
451 size_t extra = self->psize;
452 char *base = (char *)self - extra;
453 size_t len = CHUNK_SIZE(self)((self)->csize & -2) + extra;
454 /* Crash on double free */
455 if (extra & 1) a_crash();
456 __munmap(base, len);
457 return;
458 }
459
460 final_size = new_size = CHUNK_SIZE(self)((self)->csize & -2);
461 next = NEXT_CHUNK(self)((struct chunk *)((char *)(self) + ((self)->csize & -2
)));
462
463 /* Crash on corrupted footer (likely from buffer overflow) */
464 if (next->psize != self->csize) a_crash();
465
466 for (;;) {
467 if (self->psize & next->csize & C_INUSE((size_t)1)) {
468 self->csize = final_size | C_INUSE((size_t)1);
469 next->psize = final_size | C_INUSE((size_t)1);
470 i = bin_index(final_size);
471 lock_bin(i);
472 lock(mal.free_lock);
473 if (self->psize & next->csize & C_INUSE((size_t)1))
474 break;
475 unlock(mal.free_lock);
476 unlock_bin(i);
477 }
478
479 if (alloc_rev(self)) {
480 self = PREV_CHUNK(self)((struct chunk *)((char *)(self) - ((self)->psize & -2
)));
481 size = CHUNK_SIZE(self)((self)->csize & -2);
482 final_size += size;
483 if (new_size+size > RECLAIM163840 && (new_size+size^size) > size)
484 reclaim = 1;
485 }
486
487 if (alloc_fwd(next)) {
488 size = CHUNK_SIZE(next)((next)->csize & -2);
489 final_size += size;
490 if (new_size+size > RECLAIM163840 && (new_size+size^size) > size)
491 reclaim = 1;
492 next = NEXT_CHUNK(next)((struct chunk *)((char *)(next) + ((next)->csize & -2
)));
493 }
494 }
495
496 if (!(mal.binmap & 1ULL<<i))
497 a_or_64(&mal.binmap, 1ULL<<i);
498
499 self->csize = final_size;
500 next->psize = final_size;
501 unlock(mal.free_lock);
502
503 self->next = BIN_TO_CHUNK(i)((struct chunk *)((char *)(&mal.bins[i].head) - (2*sizeof
(size_t))));
504 self->prev = mal.bins[i].tail;
505 self->next->prev = self;
506 self->prev->next = self;
507
508 /* Replace middle of large chunks with fresh zero pages */
509 if (reclaim) {
510 uintptr_t a = (uintptr_t)self + SIZE_ALIGN(4*sizeof(size_t))+PAGE_SIZE4096-1 & -PAGE_SIZE4096;
511 uintptr_t b = (uintptr_t)next - SIZE_ALIGN(4*sizeof(size_t)) & -PAGE_SIZE4096;
512#if 1
513 __madvise((void *)a, b-a, MADV_DONTNEED4);
514#else
515 __mmap((void *)a, b-a, PROT_READ1|PROT_WRITE2,
516 MAP_PRIVATE0x02|MAP_ANONYMOUS0x20|MAP_FIXED0x10, -1, 0);
517#endif
518 }
519
520 unlock_bin(i);
521}