1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
|
/* Author: Mark Moraes <moraes@csri.toronto.edu> */
/* $Id: defs.h,v 1.3 1999/12/30 03:26:07 mea Exp $ */
#ifndef __DEFS_H__
#define __DEFS_H__
/*
* This file includes all relevant include files, and defines various
* types and constants. It also defines lots of macros which operate on
* the malloc blocks and pointers, to try and keep the ugliness
* abstracted away from the source code.
*/
#ifdef HAVE_CONFIG_H /* In GNU autoconfig environment, most likely */
#include "config.h"
#endif
#include <stdio.h>
#include <errno.h>
extern int errno; /* Some errno.h don't declare this */
#ifdef STDC_HEADERS
# define STDHEADERS
#endif
/* #ifdef HAVE_UNISTD_H
# define STDHEADERS
#endif */
/*
* ANSI defines malloc to return void *, and take size_t as an
* argument, while present Unix convention is char * and unsigned int
* respectively. This is not ifdef'ed with STDC because you may want to
* compile a Unix malloc with an ANSI C compiler or vice versa. Note
* that sys/types.h on BSD Unix systems defines size_t to be int or
* long. memsize_t is for routines that expect int in Unix and size_t
* in ANSI.
*/
#ifdef STDHEADERS
# define univptr_t void *
# define memsize_t size_t
#else /* ! STDHEADERS */
# define univptr_t char *
# define size_t unsigned int
# define memsize_t int
#endif /* STDHEADERS */
#ifndef REGISTER
# ifdef __GNUC__
/* gcc probably does better register allocation than I do */
# define REGISTER
# else
# define REGISTER register
# endif
#endif
#if defined(__STDC__)
# define proto(x) x
#else
# define proto(x) ()
# define const
# define volatile
#endif
#include "externs.h"
#include "assert.h"
#ifndef EXIT_FAILURE
# define EXIT_FAILURE 1
#endif
#ifdef __STDC__
# include <limits.h>
# ifndef BITSPERBYTE
# define BITSPERBYTE CHAR_BIT
# endif
#else
# include <values.h>
#endif
#include "align.h" /* Needs BITSPERBYTE */
/*
* We assume that FREE is a 0 bit, and the tag for a free block, Or'ing the
* tag with ALLOCED should turn on the high bit, And'ing with SIZEMASK
* should turn it off.
*/
#define FREE ((size_t) 0)
#define ALLOCED (HIBITSZ)
#define SIZEMASK (~HIBITSZ)
#define MAXBINS 8
#define DEF_SBRKUNITS 1024
union word { /* basic unit of storage */
size_t size; /* size of this block + 1 bit status */
union word *next; /* next free block */
union word *prev; /* prev free block */
univptr_t ptr; /* stops lint complaining, keeps alignment */
char c;
int i;
char *cp;
char **cpp;
int *ip;
int **ipp;
void (*allocator)(void);
ALIGN; /* alignment stuff - wild fun */
};
typedef union word Word;
/*
* WARNING - Many of these macros are UNSAFE because they have multiple
* evaluations of the arguments. Use with care, avoid side-effects.
*/
/*
* These macros define operations on a pointer to a block. The zero'th
* word of a block is the size field, where the top bit is 1 if the
* block is allocated. This word is also referred to as the starting tag.
* The last word of the block is identical to the zero'th word of the
* block and is the end tag. IF the block is free, the second last word
* is a pointer to the next block in the free list (a doubly linked list
* of all free blocks in the heap), and the third from last word is a
* pointer to the previous block in the free list. HEADERWORDS is the
* number of words before the pointer in the block that malloc returns,
* TRAILERWORDS is the number of words after the returned block. Note
* that the zero'th and the last word MUST be the boundary tags - this
* is hard-wired into the algorithm. Increasing HEADERWORDS or
* TRAILERWORDS suitably should be accompanied by additional macros to
* operate on those words. The routines most likely to be affected are
* malloc/realloc/free/memalign/mal_verify/mal_heapdump.
*/
/*
* There are two ways we can refer to a block -- by pointing at the
* start tag, or by pointing at the end tag. For reasons of efficiency
* and performance, free blocks are always referred to by the end tag,
* while allocated blocks are usually referred to by the start tag.
* Accordingly, the following macros indicate the type of their argument
* by using either 'p', 'sp', or 'ep' to indicate a pointer. 'p' means
* the pointer could point at either the start or end tag. 'sp' means it
* must point at a start tag for that macro to work correctly, 'ep'
* means it must point at the end tag. Usually, macros operating on free
* blocks (NEXT, PREV, VALID_PREV_PTR, VALID_NEXT_PTR) take 'ep', while
* macros operating on allocated blocks (REALSIZE, MAGIC_PTR,
* SET_REALSIZE) take 'sp'. The size field may be validated using either
* VALID_START_SIZE_FIELD for an 'sp' or VALID_END_SIZE_FIELD for an
* 'ep'.
*/
/*
* SIZE, SIZEFIELD and TAG are valid for allocated and free blocks,
* REALSIZE is valid for allocated blocks when debugging, and NEXT and
* PREV are valid for free blocks. We could speed things up by making
* the free list singly linked when not debugging - the double link are
* just so we can check for pointer validity. (PREV(NEXT(ep)) == ep and
* NEXT(PREV(ep)) == ep). FREESIZE is used only to get the size field
* from FREE blocks - in this implementation, free blocks have a tag
* bit of 0 so no masking is necessary to operate on the SIZEFIELD when
* a block is free. We take advantage of that as a minor optimization.
*/
#define SIZEFIELD(p) ((p)->size)
#define SIZE(p) ((size_t) (SIZEFIELD(p) & SIZEMASK))
#define ALLOCMASK(n) ((n) | ALLOCED)
#define FREESIZE(p) SIZEFIELD(p)
/*
* FREEMASK should be (n) & SIZEMASK, but since (n) will always have
* the hi bit off after the conversion from bytes requested by the user
* to words.
*/
#define FREEMASK(n) (n)
#define TAG(p) (SIZEFIELD(p) & ~SIZEMASK)
#ifdef DEBUG
# define REALSIZE(sp) (((sp)+1)->size)
#endif /* DEBUG */
#define NEXT(ep) (((ep)-1)->next)
#define PREV(ep) (((ep)-2)->prev)
/*
* HEADERWORDS is the real block header in an allocated block - the
* free block header uses extra words in the block itself
*/
#ifdef DEBUG
# define HEADERWORDS 3 /* Start boundary tag
+ real size in bytes
+ allocator address */
#else /* ! DEBUG */
# define HEADERWORDS 1 /* Start boundary tag */
#endif /* DEBUG */
#define TRAILERWORDS 1
#define FREEHEADERWORDS 1 /* Start boundary tag */
#define FREETRAILERWORDS 3 /* next and prev, end boundary tag */
#define ALLOC_OVERHEAD (HEADERWORDS + TRAILERWORDS)
#define FREE_OVERHEAD (FREEHEADERWORDS + FREETRAILERWORDS)
/*
* The allocator views memory as a list of non-contiguous arenas. (If
* successive sbrks() return contiguous blocks, they are colaesced into
* one arena - if a program never calls sbrk() other than malloc(),
* then there should only be one arena. This malloc will however
* happily coexist with other allocators calling sbrk() and uses only
* the blocks given to it by sbrk. It expects the same courtesy from
* other allocators. The arenas are chained into a linked list using
* the first word of each block as a pointer to the next arena. The
* second word of the arena, and the last word, contain fake boundary
* tags that are permanantly marked allocated, so that no attempt is
* made to coalesce past them. See the code in dumpheap for more info.
*/
#define ARENASTART 2 /* next ptr + fake start tag */
#ifdef DEBUG
/*
* 1 for prev link in free block - next link is absorbed by header
* REALSIZE word
*/
# define FIXEDOVERHEAD (1 + ALLOC_OVERHEAD)
#else /* ! DEBUG */
/* 1 for prev link, 1 for next link, + header and trailer */
# define FIXEDOVERHEAD (2 + ALLOC_OVERHEAD)
#endif /* DEBUG */
/*
* Check that pointer is safe to dereference i.e. actually points
* somewhere within the heap and is properly aligned.
*/
#define PTR_IN_HEAP(p) \
((p) > _malloc_loword && (p) < _malloc_hiword && \
ALIGNPTR(p) == ((univptr_t) (p)))
/* Check that the size field is valid */
#define VALID_START_SIZE_FIELD(sp) \
(PTR_IN_HEAP((sp) + SIZE(sp) - 1) && \
SIZEFIELD(sp) == SIZEFIELD((sp) + SIZE(sp) - 1))
#define VALID_END_SIZE_FIELD(ep) \
(PTR_IN_HEAP((ep) - SIZE(ep) + 1) && \
SIZEFIELD(ep) == SIZEFIELD((ep) - SIZE(ep) + 1))
#define ulong unsigned long
#ifdef DEBUG
/*
* Byte that is stored at the end of each block if the requested size
* of the block is not a multiple of sizeof(Word). (If it is a multiple
* of sizeof(Word), then we don't need to put the magic because the
* endboundary tag will be corrupted and the tests that check the
* validity of the boundary tag should detect it
*/
# ifndef u_char
# define u_char unsigned char
# endif /* u_char */
# define MAGIC_BYTE ((u_char) '\252')
/*
* Check if size of the block is identical to requested size. Typical
* tests will be of the form DONT_NEED_MAGIC(p) || something for
* short-circuited protection, because blocks where DONT_NEED_MAGIC is
* true will be tested for boundary tag detection so we don't need the
* magic byte at the end.
*/
# define DONT_NEED_MAGIC(sp) \
(REALSIZE(sp) == ((SIZE(sp) - ALLOC_OVERHEAD) * sizeof(Word)))
/* Note that VALID_REALSIZE must not be used if DONT_NEED_MAGIC is true */
# define VALID_REALSIZE(sp) \
(REALSIZE(sp) < ((SIZE(sp) - ALLOC_OVERHEAD)*sizeof(Word)))
/* Location of the magic byte */
# define MAGIC_PTR(sp) ((u_char *)((sp) + HEADERWORDS) + REALSIZE(sp))
/*
* malloc code should only use the next two macros SET_REALSIZE and
* VALID_MAGIC, since they are the only ones which have non-DEBUG
* (null) alternatives
*/
/* Macro sets the realsize of a block if necessary */
# define SET_REALSIZE(sp, n) \
(REALSIZE(sp) = (n), \
DONT_NEED_MAGIC(sp) || (*MAGIC_PTR(sp) = MAGIC_BYTE))
/* Macro tests that the magic byte is valid if it exists */
# define VALID_MAGIC(sp) \
(DONT_NEED_MAGIC(sp) || \
(VALID_REALSIZE(sp) && (*MAGIC_PTR(sp) == MAGIC_BYTE)))
#else /* ! DEBUG */
# define SET_REALSIZE(sp, n)
# define VALID_MAGIC(sp) (1)
#endif /* DEBUG */
/*
* Check that a free list ptr points to a block with something pointing
* back. This is the only reason we use a doubly linked free list.
*/
#define VALID_NEXT_PTR(ep) (PTR_IN_HEAP(NEXT(ep)) && PREV(NEXT(ep)) == (ep))
#define VALID_PREV_PTR(ep) (PTR_IN_HEAP(PREV(ep)) && NEXT(PREV(ep)) == (ep))
/*
* quick bit-arithmetic to check a number (including 1) is a power of two.
*/
#define is_power_of_2(x) ((((x) - 1) & (x)) == 0)
/*
* An array to try and keep track of the distribution of sizes of
* malloc'ed blocks
*/
#ifdef PROFILESIZES
# define MAXPROFILESIZE 2*1024
# define COUNTSIZE(nw) (_malloc_scount[((nw) < MAXPROFILESIZE) ? (nw) : 0]++)
#else
# define COUNTSIZE(nw)
#endif
#ifdef __GNUC__
# define CALLER_RETURN_ADDRESS ((void*)__builtin_return_address(0))
#else
# define CALLER_RETURN_ADDRESS ((void*)0)
#endif
#ifndef USESTDIO
/*
* Much better not to use stdio - stdio calls malloc() and can
* therefore cause problems when debugging heap corruption. However,
* there's no guaranteed way to turn off buffering on a FILE pointer in
* ANSI. This is a vile kludge!
*/
# define fputs(s, f) write(fileno(f), (s), strlen(s))
# define setvbuf(f, s, n, l) __nothing()
# define fflush(f) __nothing()
#endif /* USESTDIO */
#ifdef TRACE
/*
* Prints a trace string. For convenience, x is an
* sprintf(_malloc_statsbuf, ...) or strcpy(_malloc_statsbuf, ...);
* something which puts the appropriate text to be printed in
* _malloc_statsbuf - ugly, but more convenient than making x a string.
*/
# define PRTRACE(x) \
if (_malloc_tracing) { \
(void) x; \
if (_malloc_statsfile) \
(void) fputs(_malloc_statsbuf, _malloc_statsfile); \
} else \
_malloc_tracing += 0
#else
# define PRTRACE(x)
#endif
#ifdef DEBUG
# define CHECKHEAP() \
if (_malloc_debugging >= 2) \
(void) mal_verify(_malloc_debugging >= 3); \
else \
_malloc_debugging += 0
# define CHECKFREEPTR(ep, msg) \
if (_malloc_debugging >= 1) { \
ASSERT_EP(PTR_IN_HEAP(ep), "pointer outside heap", (msg), (ep)); \
ASSERT_EP(TAG(ep) == FREE, "already-allocated block", (msg), (ep)); \
ASSERT_EP(VALID_END_SIZE_FIELD(ep), "corrupt block", msg, (ep)); \
ASSERT_EP(VALID_NEXT_PTR(ep), "corrupt link to next free block", (msg), (ep)); \
ASSERT_EP(VALID_PREV_PTR(ep), "corrupt link to previous free block", (msg), (ep)); \
} else \
_malloc_debugging += 0
# define CHECKALLOCPTR(sp, msg) \
if (_malloc_debugging >= 1) { \
ASSERT_SP(PTR_IN_HEAP(sp), "pointer outside heap", (msg), (sp)); \
ASSERT_SP(TAG(sp) != FREE, "already-freed block", (msg), (sp)); \
ASSERT_SP(VALID_START_SIZE_FIELD(sp), "corrupt block", (msg), (sp)); \
ASSERT_SP(VALID_MAGIC(sp), "block with end overwritten", (msg), (sp)); \
} else \
_malloc_debugging += 0
#else /* !DEBUG */
# define CHECKHEAP()
# define CHECKFREEPTR(ep, msg)
# define CHECKALLOCPTR(sp, msg)
#endif /* DEBUG */
#define FREEMAGIC '\125'
/*
* Memory functions but in words. We just call memset/memcpy, and hope
* that someone has optimized them. If you are on pure 4.2BSD, either
* redefine these in terms of bcopy/your own memcpy, or
* get the functions from one of 4.3src/Henry Spencer's strings
* package/C News src
*/
#define MEMSET(p, c, n) \
(void) memset((univptr_t) (p), (c), (memsize_t) ((n) * sizeof(Word)))
#define MEMCPY(p1, p2, n) \
(void) memcpy((univptr_t) (p1), (univptr_t) (p2), \
(memsize_t) ((n) * sizeof(Word)))
#ifdef DEBUG
# define DMEMSET(p, n) MEMSET((p), FREEMAGIC, (n))
#else
# define DMEMSET(p, n)
#endif
/*
* Thanks to Hugh Redelmeier for pointing out that an rcsid is "a
* variable accessed in a way not obvious to the compiler", so should
* be called volatile. Amazing - a use for const volatile...
*/
#ifndef RCSID /* define RCSID(x) to nothing if don't want the rcs headers */
# if defined(lint) || defined(__STRICT_ANSI__)
# define RCSID(x)
# else
# define RCSID(x) static const volatile char *rcsid = x ;
# endif
#endif
#endif /* __DEFS_H__ */ /* Do not add anything after this line */
|