/* ialloc.c (emx+gcc) -- Copyright (c) 1996-1999 by Eberhard Mattes */ #include #include #include #include #include #include /* For */ #include /* For */ #include #include /* ALIGN must be a power of two. */ void *_um_crumb_alloc (struct _um_crateset *crateset, size_t size, size_t align, unsigned flags) { void *result; struct _um_crumb *crumb; struct _um_crate *crate; crumb = crateset->crumb_head; while (crumb != NULL) { crate = _PTR_FROM_UMINT (crumb->x.free.parent_crate, struct _um_crate); assert (_UM_CRUMB_STATUS (crumb) == _UMS_FREE); assert (crate->magic == _UM_MAGIC_CRATE); assert (crate->parent_crateset == crateset); assert (crate->used < crate->max); result = _UM_BLOCK_FROM_CRUMB (crumb); if (_UM_IS_ALIGNED (result, align) && (!(flags & _UMFI_TILED) || _UM_TILE_OK (result, size))) { _um_crumb_unlink (crateset, crumb); crate->used += 1; _UM_CRUMB_SET_STATUS (crumb, _UMS_USER); crumb->x.used.size = size; if (flags & _UMFI_ZERO) memset (result, 0, size); return result; } /* Move to the next crumb of the list. */ crumb = crumb->x.free.next; } /* No (suitable) free crumb found in the free list. Allocate from the most recently allocated crate. The most recently allocated crate is at the head of the list (ie, it's pointed to by crateset->crate_head). The most recently allocated crate is the only one which has crate->init < crate->max. */ crate = crateset->crate_head; if (crate == NULL || crate->init >= crate->max) return NULL; crumb = _UM_CRUMB_BY_INDEX (crate, crate->init); result = _UM_BLOCK_FROM_CRUMB (crumb); if (_UM_IS_ALIGNED (result, align) && (!(flags & _UMFI_TILED) || _UM_TILE_OK (result, size))) { assert (_UM_IS_ALIGNED (crate, _UM_PARENT_ALIGN)); crumb->x.used.parent_crate = _UMINT_FROM_PTR (crate) | _UMS_USER; crumb->x.used.size = size; crate->init += 1; crate->used += 1; if (flags & _UMFI_ZERO) /* TODO: Not always required */ memset (result, 0, size); return result; } /* Well, we could try the next crumb. However, it's simpler to allocate a lump. */ return NULL; } /* Attempt to allocate a lump without expanding the heap. */ static void *_um_lump_alloc_noexpand (Heap_t h, size_t size, size_t align, unsigned flags) { int bucket_number; struct _um_lump *olump, *ulump, *slack; size_t rsize, osize, diff; void *block; struct _um_seg *seg; /* Set RSIZE to the rounded size of the lump. */ rsize = _UM_ROUND_LUMP (size); if (rsize >= _UM_MAX_SIZE) return NULL; /* Find the smallest bucket for that lump size (`small' with respect to the size of the lumps, not to the number of the free lumps in that bucket). There can't be a suitable free lump in any smaller bucket. */ bucket_number = _um_find_bucket (rsize); /* Try all the lumps of the smallest bucket. If this fails, try the next bigger bucket, and so on. */ while (bucket_number < _UM_BUCKETS) { /* Examine all lumps of the current bucket. */ for (olump = h->buckets[bucket_number].head; olump != NULL; olump = olump->x.free.next) { assert (_UM_LUMP_STATUS (olump) == _UMS_FREE); /* Compute the rounded size of the current lump; try the next lump if it's too small. */ osize = _UM_ROUND_LUMP (olump->size); if (osize < rsize) continue; /* Reject this lump if it's not big enough to obtain the requested alignment. */ block = _UM_BLOCK_FROM_LUMP (olump); diff = _UM_ALIGN_DIFF (block, align); assert (diff % _UM_PAGE_SIZE == 0); if (osize < diff + rsize) continue; /* Align the block as requested. This may leave a free lump of DIFF bytes preceding the block. */ block = _UM_ADD (block, diff); assert (_UM_IS_ALIGNED (block, align)); /* If tiling is requested, realign the block again if required. Reject this lump if it's not big enough to obtain proper alignment for tiling or if its address is too high for tiling. Update DIFF and BLOCK. */ if (flags & _UMFI_TILED) { if (!_UM_TILE_TILED (block, size)) continue; if (!_UM_TILE_ALIGNED (block, size)) { diff += _UM_ALIGN_DIFF (block, 0x10000); if (osize < diff + rsize) continue; block = _UM_ADD (_UM_BLOCK_FROM_LUMP (olump), diff); if (!_UM_TILE_TILED (block, size)) continue; } assert (_UM_TILE_OK (block, size)); } /* Remove the lump from the free list. */ _um_lump_unlink_bucket (&h->buckets[bucket_number], olump); /* Initialize the lump. ULUMP points to the aligned lump. */ seg = _PTR_FROM_UMINT (olump->parent_seg, struct _um_seg); ulump = _UM_ADD (olump, diff); assert (_UM_IS_ALIGNED (seg, _UM_PARENT_ALIGN)); ulump->parent_seg = _UMINT_FROM_PTR (seg) | _UMS_USER; if (flags & _UMFI_CRATE) _UM_LUMP_SET_STATUS (ulump, _UMS_CRATE); _um_lump_set_size (ulump, size); /* If the lump is bigger than required, add the slack to the appropriate free list. There's no need to coalesce with other free blocks as the slack is part of a (previously) free lump which cannot have neighboring fre lumps. */ if (osize > diff + rsize) { assert ((osize - rsize) % _UM_PAGE_SIZE == 0); slack = (struct _um_lump *)_UM_ADD (olump, diff + rsize); _um_lump_make_free (h, slack, seg, osize - (diff + rsize)); } /* If padding was inserted before the block for alignment and/or tiling, add the padding to the free list. There's no need to coalesce with other free blocks as the slack is part of a (previously) free lump which cannot have neighboring fre lumps. */ if (diff > 0) { assert (diff % _UM_PAGE_SIZE == 0); _um_lump_make_free (h, olump, seg, diff); } if (flags & _UMFI_ZERO) /* TODO: Not always required */ memset (block, 0, size); return block; } ++bucket_number; } /* All suitable buckets searched, in vain. Fail. */ return NULL; } /* Call ALLOC_FUN to add SIZE bytes to the heap. Return -1 on error, 0 if ALLOC_FUN allocated less than SIZE bytes, or 1 if ALLOC_FUN allocated SIZE bytes or more. */ static int _um_heap_expand2 (Heap_t h, size_t size) { void *memory; size_t mem_size, shrink_size; int clean; mem_size = size; clean = !_BLOCK_CLEAN; memory = h->alloc_fun (h, &mem_size, &clean); if (memory == NULL) return -1; if (_um_addmem_nolock (h, memory, mem_size, clean) != h) { /* _um_addmem_nolock() failed -- give back the memory. */ if (h->release_fun != NULL) h->release_fun (h, memory, mem_size); else if (h->shrink_fun != NULL) { shrink_size = 0; h->shrink_fun (h, memory, mem_size, &shrink_size); } return -1; } return mem_size < size ? 0 : 1; } /* Attempt to expand the heap to enable allocation of a lump of SIZE bytes. Return true iff successful. */ static int _um_heap_expand (Heap_t h, size_t size) { size_t rsize, add_size; int r; /* Can't expand a fixed-size heap, ie, a heap which doesn't have an ALLOC_FUN. */ if (h->alloc_fun == NULL) return 0; rsize = _UM_ROUND_LUMP (size); if (rsize >= _UM_MAX_SIZE) return 0; add_size = rsize + _HEAP_MIN_SIZE; r = _um_heap_expand2 (h, add_size); if (r == 0) { /* ALLOC_FUN may allocate less memory than requested to avoid wasting the rest of a heap object. Therefore we call ALLOC_FUN again if it did not allocate enough memory. Note that we have to request the same amount of memory as in the first attempt! Otherwise the ADD_SIZE bytes might be split in two heap objects. */ r = _um_heap_expand2 (h, add_size); } return r > 0; } /* Allocate a lump, possibly expanding the heap to satisfy the allocation request. */ void *_um_lump_alloc (Heap_t h, size_t size, size_t align, unsigned flags) { void *block; if (_UM_ROUND_LUMP (size) < size) return NULL; /* Overflow */ block = _um_lump_alloc_noexpand (h, size, align, flags); if (block != NULL) return block; if (!_um_heap_expand (h, size)) return NULL; /* This should succeed -- note that the heap is locked. Failure indicates an internal error or heap corruption. */ return _um_lump_alloc_noexpand (h, size, align, flags); } static void *_um_crateset_alloc (Heap_t h, struct _um_crateset *crateset, size_t size, size_t align, unsigned flags) { struct _um_crate *crate; size_t crate_size; void *block; int n; block = _um_crumb_alloc (crateset, size, align, flags); if (block != NULL) return block; /* Don't add a new crate if allocation failed due to alignment requirements. */ if (crateset->crumb_head == NULL && (crateset->crate_head == NULL || crateset->crate_head->init >= crateset->crate_head->max)) { n = _UM_MAX_CRATE_SIZE / (crateset->crumb_size + _UM_CRUMB_OVERHEAD); crate_size = (sizeof (struct _um_crate) + n * (crateset->crumb_size + _UM_CRUMB_OVERHEAD)); crate = _um_lump_alloc (h, crate_size, _UM_PARENT_ALIGN, _UMFI_CRATE); if (crate != NULL) { crate->magic = _UM_MAGIC_CRATE; crate->parent_crateset = crateset; crate->parent_heap = h; crate->crumb_size = crateset->crumb_size; crate->max = n; crate->init = 0; crate->used = 0; crate->next = crateset->crate_head; crateset->crate_head = crate; /* Update the heap's number of crates and maximum number of crumbs. */ h->n_crates += 1; h->max_crumbs += n; /* Try again to allocate a crumb. */ return _um_crumb_alloc (crateset, size, align, flags); } } return NULL; } void *_um_alloc_no_lock (Heap_t h, size_t size, size_t align, unsigned flags) { int i; void *block; if (h->n_cratesets > 0 && size <= h->cratesets[h->n_cratesets-1].crumb_size) { i = 0; while (size > h->cratesets[i].crumb_size) ++i; block = _um_crateset_alloc (h, &h->cratesets[i], size, align, flags); if (block != NULL) return block; } return _um_lump_alloc (h, size, align, flags); }