/* emx/umalloc.h (emx+gcc) */ #ifndef _EMX_UMALLOC_H #define _EMX_UMALLOC_H #if defined (__cplusplus) extern "C" { #endif /* =========================== Introduction =========================== */ /* This implementation of malloc() uses two different allocation schemes, one for small blocks, one for big blocks. Small blocks are allocated from special big blocks, big blocks are made up of fixed-sized pages to reduce fragmentation. Glossary: heap A set of non-contiguous segments along with various control information. This is the entity passed by the user to _umalloc() etc. Each heap starts with a struct _uheap. Heap_t points to a heap. segment A contiguous area of memory made up of pages and organized in lumps. This is used for allocating big blocks and for allocating crates. Each segment starts with a struct _um_seg; the rest of the segment is divided into pages and used for lumps. lump A contiguous set of pages. A lump is either free or allocated. An allocated lump is either used for a user block or for a crate. The first page of a lump starts with a struct _um_lump which contains control information about the lump. The remaining bytes of the first page and the remaining pages of the lump make up a block. page Smallest allocation unit in a segment. Division into pages is used to reduce fragmentation. The size of a page, _UM_PAGE_SIZE, must be a power of two. bucket A set of free lumps of certain sizes. Bucket i contains free lumps of SIZE(i) through SIZE(i+1)-1 bytes, where SIZE(i) is a ower of two. Buckets are implemented as doubly-linked lists which may span segments. Each heap has its own set of buckets of various sizes. crate A contiguous set of crumbs, all having the same size. Crates are allocated as lumps from the heap. Lumps used for crates have state _UMS_CRATE. Each crate starts with a struct _um_crate followed by an array of crumbs. crumb Allocation unit in crates, used for allocation of small blocks. All crumbs of a crate have the same size. Each crumb starts with a struct _um_crumb. crateset A linked list of crates and a doubly-linked list of free crumbs (which may span several crates), all crumbs having the same size. Each heap has its own set of cratesets of various (small) sizes. block Memory allocated from a heap. malloc() returns a pointer to a block. Each block is preceded by control information (header); the word immediately preceding a block points to the parent structure (segment or crate). A block is either located in a lump or in a crumb, distinguished by the magic word pointed to by the parent pointer. header The control information (struct _um_hdr) preceding a block. At least, this is a pointer to the parent structure (segment or crate). The low 3 bits of the pointer are used for flag bits, therefore the parent structure must be aligned on a 8-byte boundary (the low 3 bits of the pointer are set to zero). The `size' member of the header is not valid for used crumbs (it's overlaid by the first word of the block). A different allocation scheme (crumbs) for small blocks is used for the following reasons: - The granularity (page size) of lumps is 32 bytes. That's quite a lot of overhead for, say, 4-byte blocks - If the page size were decreased to 4 to minimize overhead, there wouldn't be enough space for keeping the two free list pointers -- free crumbs don't need the size member, therefore it can be overlaid with one of the pointers - Moreover, decreasing the page size would increase fragmentation of the heap - Allocating small blocks as lumps would increase fragmentation of the heap. The following diagram shows four crumbs (of 4 bytes each), #2 being free: crumb #0 crumb #1 crumb #2 crumb #3 |<---12--->||<---12--->||<---12--->||<---12--->| |======||==||======||==||==========||======||==| hdr blk hdr blk _um_crumb hdr blk | || | | | |=======...||=======...| |=======...| _um_crumb _um_crumb _um_crumb Note that part of `struct _um_crumb' is overlaid by the block. The entire `struct _um_crumb' is used for the free crumb. The following diagram shows four crumbs (of 8 bytes each), #2 being free: crumb #0 crumb #1 crumb #2 crumb #3 |<-----16----->||<-----16----->||<-----16----->||<-----16----->| |======||======||======||======||==========|....|======||======| hdr blk hdr blk _um_crumb hdr blk |=======...| |=======...| |=======...| _um_crumb _um_crumb _um_crumb Again, part of `struct _um_crumb' is overlaid by the block. We could save another 4 bytes per crumb for block sizes >= 8 by not storing the size, which can be retrieved from the crate pointed to by the header. Then, _msize() would return the rounded size. The minimum crumb size is 12 bytes, therefore this wouldn't improve things for 4-byte blocks. The following diagram shows a used lump spanning two pages with _UM_LUMP_HEADER_SIZE == 8 and _UM_PAGE_SIZE == 32: 32-byte boundary 32-byte boundary | | |<-------- page (32) --------->||<-------- page (32) --------->| |<- 8->| || | |======||===================================|...............|==| hdr block unused size | | |=======.......| struct _um_lump By `mis-aligning' the pages by _UM_LUMP_HEADER_SIZE we can align blocks on any power of two. Note that part of `struct _um_lump' is overlaid by the block. The following diagram shows a free lump spanning two pages with _UM_LUMP_HEADER_SIZE == 8 and _UM_PAGE_SIZE == 32: 32-byte boundary 32-byte boundary | | |<-------- page (32) --------->||<-------- page (32) --------->| |==============|............................................|==| struct _um_lump unused size Note that the entire `struct _um_lump' is used. */ /* ======================== Common definitions ======================== */ /* Magic numbers. */ #define _UM_MAGIC_CRATE 0xdd63eeed #define _UM_MAGIC_SEG 0xdd73eeed #define _UM_MAGIC_HEAP 0xdd68eeed /* These flags are passed internally between the functions. */ #define _UMFI_TILED 0x0001 /* Create tiled block */ #define _UMFI_ZERO 0x0002 /* Zero the block if required */ #define _UMFI_CRATE 0x0004 /* Create a lump for a crate */ #define _UMFI_NOMOVE 0x0008 /* Expand block without moving */ /* These flags are stored in the parent pointer of lumps and crumbs. In consequence, we must align objects pointed to by those pointers (ie, segments and crates) on 8-byte boundaries. */ #define _UMF_MASK 0x07 /* Mask for all the following flags */ #define _UMF_RESERVED 0x04 /* Not yet used, _udump_allocated_delta() */ #define _UMS_MASK 0x03 /* Mask for the block status */ #define _UMS_FREE 0x00 /* The block is free (1) */ #define _UMS_USER 0x01 /* The block is used for a user block */ #define _UMS_CRATE 0x02 /* The block is used for a crate */ #define _UMS_RESERVED 0x03 /* Not yet used */ /* (1) In most cases which check the status for equality or inequality to _UMS_FREE. Defining _UMS_FREE as zero makes these tests efficient. */ /* Segments and crates must be aligned on a _UM_PARENT_ALIGN byte boundary. */ #define _UM_PARENT_ALIGN (_UMF_MASK + 1) /* Turn an _umint into a pointer. This is used for the parent pointer in the header. */ #define _PTR_FROM_UMINT(x,t) ((t *)((x) & ~_UMF_MASK)) /* Turn a pointer into an _umint. This is used for the parent pointer in the header; the flags will be set to zero if the pointer is properly aligned. */ #define _UMINT_FROM_PTR(p) ((_umint)(p)) /* Return true iff P is suitably aligned for holding a tiled object of S bytes. */ #define _UM_TILE_ALIGNED(p,s) ((((unsigned long)(p) + (s)) & 0xffff) >= (s) \ || ((unsigned long)(p) & 0xffff) == 0) /* Return true iff the address P is suitable for holding a tiled object of S bytes. */ #define _UM_TILE_TILED(p,s) ((unsigned long)(p) + (s) <= 0x20000000) /* Return true iff the address P can be used for a tiled object of S bytes. */ #define _UM_TILE_OK(p,s) (_UM_TILE_ALIGNED ((p), (s)) \ && _UM_TILE_TILED ((p), (s))) /* Compute the smallest number X such that P will be aligned on a A byte boundary if X is added (as a byte count) to P. P can be either a pointer or an integer, A must be a power of two. */ #define _UM_ALIGN_DIFF(p,a) ((((unsigned long)(p) + (a) - 1) & ~((a) - 1)) \ - (unsigned long)(p)) /* Return true iff P is aligned on an A boundary. A must be a power of two. */ #define _UM_IS_ALIGNED(p,a) (((unsigned long)(p) & ((a) - 1)) == 0) /* Return a void pointer pointing N bytes past the start of the object pointed to be P. In other words, add an integer to a pointer, interpreting the integer as byte count. */ #define _UM_ADD(p,n) ((void *)((char *)(p) + (n))) /* Set the status of a crumb or lump to S. V is the `parent' member of the header. */ #define _UM_SET_STATUS(v,s) ((v) = ((v) & ~_UMS_MASK) | (s)) /* _uheap_walk() applies the _UM_WALK_ERROR macro when returning an error. Set a breakpoint in _um_walk_error() to find out more about the error with a debugger. */ #ifdef NDEBUG #define _UM_WALK_ERROR(x) x #else #define _UM_WALK_ERROR(x) _um_walk_error(x) int _um_walk_error (int); #endif /* _umint represents a pointer as unsigned integer. */ typedef unsigned long _umint; /* _umagic holds a magic number. */ typedef unsigned long _umagic; /* Declarations for forward references. */ struct _uheap; /* ============================== Header ============================== */ /* The control information immediately preceding free and allocated blocks must have the following layout (`size' is not required for free crumbs, but is required for free lumps): */ struct _um_hdr { _umint size; /* Valid if the block is allocated */ _umint parent; /* Use _PTR_FROM_UMINT() to get the pointer */ }; #define _HDR_FROM_BLOCK(p) (((struct _um_hdr *)(p)) - 1) /* Return the status of the crumb P. */ #define _UM_HDR_STATUS(p) ((p)->parent & _UMS_MASK) /* ========================= Crates and crumbs ======================== */ /* Subheaps (crates) for blocks of constant size. All the blocks allocated from a crate have the same rounded size. Each crate has a header followed by an array of crumbs. Initially, crumbs are allocated directly from the array, starting at index INIT. This is done only for the most recently allocated crate as this is the only one which has free crumbs at INIT. Deallocating a crumb will put it into a list of free crumbs. If that list is non-empty, crumbs will be allocated from that list. */ #define _UM_MAX_CRATE_SIZE 8000 struct _um_crumb { union { struct { struct _um_crumb *prev; /* Cf. struct _um_hdr (size) */ _umint parent_crate; /* Cf. struct _um_hdr (parent) */ struct _um_crumb *next; } free; struct { _umint size; /* Cf. struct _um_hdr (size) */ _umint parent_crate; /* Cf. struct _um_hdr (parent) */ char data; } used; } x; }; struct _um_crate { /* This must be the first word. It's used for consistency checking and for distinguishing crates from segments. */ _umagic magic; struct _um_crateset *parent_crateset; /* PARENT_HEAP points to the heap this crate belongs to. For instance, we need this for locking the heap in free(). */ struct _uheap *parent_heap; /* NEXT points to the next crate of the same size of the same heap. This pointer is rarely needed, so a simply-linked list is sufficient. */ struct _um_crate *next; /* All crumbs in this crate have this size. */ size_t crumb_size; /* Maximum number of crumbs in this crate. */ unsigned max; /* Crumbs 0 through INIT-1 have been initialized, the free ones are in the fre list. Crumbs INIT through MAX-1 are available and uninitialized (they are not in the free list). */ unsigned init; /* Number of used crumbs in this crate */ unsigned used; }; /* This is the overhead added to a block in a crumb. */ #define _UM_CRUMB_OVERHEAD offsetof (struct _um_crumb, x.used.data) /* Return a pointer to the Ith crumb of the crate P. */ #define _UM_CRUMB_BY_INDEX(p,i) \ ((struct _um_crumb *) \ (_UMINT_FROM_PTR (p) + sizeof (struct _um_crate) \ + (i) * ((p)->crumb_size + _UM_CRUMB_OVERHEAD))) /* Return a pointer to the crumb containing block P. */ #define _UM_CRUMB_FROM_BLOCK(p) \ ((struct _um_crumb *)((char *)(p) \ - offsetof (struct _um_crumb, x.used.data))) /* Return a pointer to the block in crumb P. */ #define _UM_BLOCK_FROM_CRUMB(p) ((void *)&(p)->x.used.data) /* Return the status of the crumb P. */ #define _UM_CRUMB_STATUS(p) ((p)->x.used.parent_crate & _UMS_MASK) /* Set the status of the crumb P to S. */ #define _UM_CRUMB_SET_STATUS(p,s) \ _UM_SET_STATUS ((p)->x.used.parent_crate, (s)) /* Note: the most recently allocated crate is at the head of the crate list (ie, it's pointed to by crate_head). The most recently allocated crate is the only one which has INIT < MAX. */ struct _um_crateset { size_t crumb_size; struct _um_crate *crate_head; struct _um_crumb *crumb_head; struct _um_crumb *crumb_tail; }; /* ======================== Segments and lumps ======================== */ /* Each lump starts with a `struct _um_lump'. The block (of a used lump) starts at the DATA member, which is overlaid by NEXT and PREV in free lumps. The block is followed by an _umint which repeats the size. IMPORTANT: offsetof (struct _um_lump, x.used.data) must divide the page size to make alignment work! Additional members (say, for debugging) must be inserted at the beginning of the structure, preceding the SIZE member. */ struct _um_lump { _umint size; /* Cf. struct _um_hdr */ _umint parent_seg; /* Cf. struct _um_hdr */ union { struct { struct _um_lump *next; struct _um_lump *prev; } free; struct { char data; } used; } x; }; /* Each segment starts with a `struct _um_seg'. Note that this structure might be preceded by padding for proper alignment. See MEM. */ struct _um_seg { /* This must be the first word. It's used for consistency checking and for distinguishing crates from segments. */ _umagic magic; /* PARENT_HEAP points to the heap this segment belongs to. */ struct _uheap *parent_heap; /* NEXT points to the next segment of the same heap. This pointer is rarely needed, so a simply-linked list is sufficient. */ struct _um_seg *next; /* SIZE is the size of the memory area containing this segment. SIZE is relative to MEM (see below). */ size_t size; /* ZERO_LIMIT is used to avoid zeroing memory for _ucalloc() in certain cases. It is assumed that all pages at addresses >= ZERO_LIMIT are already zeroed. */ void *zero_limit; /* START points to the first page of this segment. */ void *start; /* END points to the (non-existing) page one past the last page of this segment. */ void *end; /* Pointer to memory containing the segment. This pointer is required because struct _um_seg must be aligned on a _UM_PARENT_ALIGN byte boundary. */ void *mem; }; /* A bucket of lumps is implemented as doubly-linked list. */ struct _um_bucket { struct _um_lump *head; struct _um_lump *tail; }; /* This is the maximum size of a lump. */ #define _UM_MAX_SIZE 0x40000000 /* This constant determines the size of the smallest bucket, bucket 0. Note that bucket numbers do not start at _UM_MIN_BUCKET! */ #define _UM_MIN_BUCKET 5 /* This constant determines the size of the biggest bucket. Note that bucket numbes do not end at _UM_MAX_BUCKET! */ #define _UM_MAX_BUCKET 27 /* 128 MB */ /* This is the number of buckets. Buckets are numbered 0 through _UM_BUCKETS-1. */ #define _UM_BUCKETS (_UM_MAX_BUCKET - _UM_MIN_BUCKET + 1) /* Bucket i contains free lumps with _UM_BUCKET_SIZE(i) <= SIZE < _UM_BUCKET_SIZE(i+1) where SIZE is the rounded size of the lumps. The last bucket, _UM_BUCKETS-1, contains all free lumps of _UM_BUCKET_SIZE(i) bytes or more (there is no upper limit in the last bucket, except for _UM_MAX_SIZE). */ #define _UM_BUCKET_SIZE(i) (1 << ((i) + _UM_MIN_BUCKET)) /* The page size must be a power of two and must be greater than or equal to _UM_LUMP_OVERHEAD. */ #define _UM_PAGE_SIZE (1 << _UM_MIN_BUCKET) /* This is the size of the header for a lump. */ #define _UM_LUMP_HEADER_SIZE offsetof (struct _um_lump, x.used.data) /* This is the overhead added to a block in a lump. */ #define _UM_LUMP_OVERHEAD (_UM_LUMP_HEADER_SIZE + sizeof (_umint)) /* Compute the lump size from the block size. The result is always a multiple of the page size. */ #define _UM_ROUND_LUMP(s) (((s) + _UM_LUMP_OVERHEAD + _UM_PAGE_SIZE - 1) \ & ~(_UM_PAGE_SIZE-1)) /* Return true iff P is the first lump of segment S. */ #define _UM_FIRST_LUMP(s,p) ((p) == (s)->start) /* Return true iff P is the last lump of segment S. */ #define _UM_LAST_LUMP(s,p) (_UM_NEXT_LUMP (p) == (s)->end) /* Return a pointer to the lump immediately preceding the lump P. This macro must not be applied to the first lump of a segment. */ #define _UM_PREV_LUMP(p) ((struct _um_lump *) \ ((char *)(p) \ - _UM_ROUND_LUMP (((_umint *)(p))[-1]))) /* Return a pointer to the lump immediately following the lump P. This macro can be applied to the last lump of a segment; in this case, the result should be equal the END member of the segment. */ #define _UM_NEXT_LUMP(p) ((struct _um_lump *) \ ((char *)(p) + _UM_ROUND_LUMP ((p)->size))) /* Return a pointer to the lump containing block P. */ #define _UM_LUMP_FROM_BLOCK(p) \ ((struct _um_lump *)((char *)(p) \ - offsetof (struct _um_lump, x.used.data))) /* Return a pointer to the block in lump P. */ #define _UM_BLOCK_FROM_LUMP(p) ((void *)&(p)->x.used.data) /* Return the status of the lump P. */ #define _UM_LUMP_STATUS(p) ((p)->parent_seg & _UMS_MASK) /* Set the status of the lump P to S. */ #define _UM_LUMP_SET_STATUS(p,s) _UM_SET_STATUS ((p)->parent_seg, (s)) /* =============================== Heaps =============================== */ /* This is the initial size of the default heap. It should be a multiple of 64K, see _default_alloc_fun(). */ #define _INITIAL_DEFAULT_HEAP_SIZE 65536 /* This is the maximum number of cratesets. */ #define _UM_MAX_CRATESETS 5 /* Each thread has its own default heap. */ #if defined (__MT__) #define _UM_DEFAULT_REGULAR_HEAP tp->_th_rheap #define _UM_DEFAULT_TILED_HEAP tp->_th_theap #define _UM_MT_DECL struct _thread *tp = _thread (); #else #define _UM_DEFAULT_REGULAR_HEAP _um_regular_heap #define _UM_DEFAULT_TILED_HEAP _um_tiled_heap #define _UM_MT_DECL #endif /* Note that _um_regular_heap is declared in . _um_tiled_heap isn't, so we declare it here. */ extern Heap_t _um_tiled_heap; /* This structure is stored at the start of a heap; it's pointed to by Heap_t. */ struct _uheap { /* Magic number. */ _umagic magic; /* Type flags passed to _ucreate(). */ unsigned type; /* Functions for expanding the heap and for shrinking the heap. */ void *(*alloc_fun)(Heap_t, size_t *, int *); void (*release_fun)(Heap_t, void *, size_t); int (*expand_fun)(Heap_t, void *, size_t, size_t *, int *); void (*shrink_fun)(Heap_t, void *, size_t, size_t *); /* SEG_HEAD is the head of the segment list. */ struct _um_seg *seg_head; /* INITIAL_SEG points to the initial segment created by _ucreate() in the same memory area as this structure. The initial segment is never deallocated. */ struct _um_seg *initial_seg; /* INITIAL_SEG_SIZE is the original size of the initial segment. We need INITIAL_SEG_SIZE for deallocating memory contiguously added to the end of the initial segment. */ size_t initial_seg_size; /* This is the number of segments. That value could be computed from the segment list. However, we use it to avoid an infinite loop in _uheapchk(). */ size_t n_segments; /* This is the number of crates. We use this number to avoid an infinite loop in _uheapchk(). */ size_t n_crates; /* This is an upper limit on the number of free crumbs. It's just the maximum number of crumbs all the crates can hold. We use this number to avoid an infinite loop in _uheapchk(). */ size_t max_crumbs; /* This array holds the control structures for the buckets. */ struct _um_bucket buckets[_UM_BUCKETS]; /* This is the number of createsets. A heap can have up to _UM_MAX_CREATESETS createsets. */ int n_cratesets; /* This array holds the control structures for the createsets. */ struct _um_crateset cratesets[_UM_MAX_CRATESETS]; /* Fast mutex semaphore for locking the heap. There's no point in using an HMTX; if the owner dies, we can't continue anyway because the heap is probably not in a consistent state. */ _rmutex rsem; /* This member is used for various purposes by _uheapchk(): _seg_walk() counts the number of crates in SCRATCH1. _check_bucket() uses SCRATCH1 as upper limit for the number of free lumps. */ size_t scratch1; }; /* Defines types for walker functions. */ typedef int _um_callback1 (const void *, size_t, int, int, const char *, size_t); typedef int _um_callback2 (Heap_t, const void *, size_t, int, int, const char *, size_t, void *); /* Prototypes for internal functions. */ Heap_t _um_addmem_nolock (Heap_t, void *, size_t, int); void *_um_alloc_no_lock (Heap_t, size_t, size_t, unsigned); void _um_crumb_free_maybe_lock (struct _um_crate *, struct _um_crumb *, int); void *_um_default_alloc (Heap_t, size_t *, int *); int _um_default_expand (Heap_t, void *, size_t, size_t *, int *); void _um_default_release (Heap_t, void *, size_t); void _um_default_shrink (Heap_t, void *, size_t, size_t *); int _um_find_bucket (size_t); void _um_free_maybe_lock (void *, int); void _um_init_default_regular_heap (void); void _um_init_default_tiled_heap (void); void *_um_lump_alloc (Heap_t, size_t, size_t, unsigned); void _um_lump_coalesce_free (Heap_t, struct _um_lump *, struct _um_seg *, size_t); void _um_lump_free_maybe_lock (struct _um_seg *, struct _um_lump *, int); void _um_lump_link_heap (Heap_t, struct _um_lump *); void _um_lump_make_free (Heap_t, struct _um_lump *, struct _um_seg *, size_t); void *_um_realloc (void *, size_t, size_t, unsigned); Heap_t _um_seg_addmem (Heap_t, struct _um_seg *, void *, size_t); Heap_t _um_seg_setmem (Heap_t, struct _um_seg *, void *, size_t, int); void _um_lump_unlink_bucket (struct _um_bucket *, struct _um_lump *); void _um_lump_unlink_heap (Heap_t, struct _um_lump *); int _um_walk_no_lock (Heap_t, _um_callback2 *, void *); /* Inline functions. */ static __inline__ void _um_heap_lock (Heap_t h) { #if defined (__MT__) _rmutex_checked_request (&h->rsem, _FMR_IGNINT); #endif } static __inline__ void _um_heap_unlock (Heap_t h) { #if defined (__MT__) _rmutex_checked_release (&h->rsem); #endif } static __inline__ void _um_crumb_unlink (struct _um_crateset *crateset, struct _um_crumb *crumb) { if (crumb->x.free.prev == NULL) crateset->crumb_head = crumb->x.free.next; else crumb->x.free.prev->x.free.next = crumb->x.free.next; if (crumb->x.free.next == NULL) crateset->crumb_tail = crumb->x.free.prev; else crumb->x.free.next->x.free.prev = crumb->x.free.prev; } static __inline__ void _um_lump_set_size (struct _um_lump *lump, size_t size) { lump->size = size; /* Must be done first */ ((_umint *)_UM_NEXT_LUMP (lump))[-1] = size; } #if defined (__cplusplus) } #endif #endif /* not _EMX_UMALLOC_H */