Embedded Systems Design - August 2008 - (Page 37)

0808esd.p35to42 7/17/08 11:57 AM Page 37 20 years ago • • • • • All internal structures and linkage must be hidden from the call-only the number of bytes required should have to be speciﬁed. The order of calls to malloc() and free() shouldn’t matter (the order of calls to free() need not be the reverse of the order of calls to malloc()). free() must prevent fragmentation of freed memory; all small, freed blocks must be combined into larger, contiguous blocks where possible. Overhead in memory and execution time must be minimized. An error condition must be returned if no memory is available. and last bytes of RAM available to malloc(). The linker or binding utility used to build the object program normally provides a facility for deﬁning external names and assigning absolute memory addresses to them. The addresses can be assigned directly in C; for example: #deﬁne _heapstart (HEADER *)0x1000 #deﬁne _heapend (HEADER *)0x2000 After initialization. frhd ptr HEADER Size - 1,024 Memory Figure 1 THE DESIGN Malloc() allocates memory in units of structures called header blocks. For systems with two-byte memory pointers, where available memory is less than 64 kbytes, each header block comprises four bytes. For larger memory models, the header must be expanded to allow a four-byte pointer and a long integer value for the size of the block. Header blocks are deﬁned as follows: typedef struct hdr { struct hdr *ptr; unsigned int size; } HEADER; After two allocations of 128 bytes. frhd ptr HEADER Size - 958 Memory HEADER ptr Size - 33 HEADER ptr Size - 33 Figure 2 A forward-linked list, the head of which is frhd, keeps track of available space. During system operation, contiguous free blocks combine to form larger blocks. We didn’t implement a best-ﬁt scheme for allocation; the ﬁrst block that’s large enough is allocated. Each allocated block has a header that speciﬁes the length of the block in HEADER-size units. When the block is freed, the free() function uses the header to link it back into the free list. The caller doesn’t see or need to be aware of this header; the pointer to the allocated space points just beyond it. INITIALIZATION The external variables _heap-start and _heapend must be deﬁned as the ﬁrst After a free() on one of the allocated blocks. The returned block wasn’t contiguous to the larger block, so the free list shows two free blocks. The pointer (ptr) in the free list header points to the returned block, which is now the last entry to the free list. frhd ptr HEADER Size - 991 Memory HEADER ptr Size - 33 HEADER ptr Size - 33 Figure 3 www.embedded.com | embedded systems design | AUGUST 2008 37 http://www.embedded.com

Table of Contents Feed for the Digital Edition of Embedded Systems Design - August 2008

Embedded Systems Design - August 2008 Contents Number Include Parity Bit Programmer's Toolbox Cover Feature: Virtualization for Embedded X86 Multiprocessor Applications Wanted: Industry Standards for Benchmarking Embedded VMM Hypervisors Achieving Cache Coherence in a MIPS32 Multicore Design Memory Allocation in C Advertising Index Break Points Marketplace

Embedded Systems Design - August 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.