Embedded Systems Design - August 2008 - (Page 42)

0808esd.p35to42 7/17/08 11:57 AM Page 42 20 years ago Listing continued from page 40. for (prev=NULL,nxt=frhd; nxt; nxt = nxt->ptr) { if (nxt->size >= nunits) /* big enough */ { if (nxt->size > nunits) { nxt->size -= nunits; /* Allocate tell end. */ nxt += nxt->size; nxt->size = nunits; /* nxt now == pointer to be alloc'd. */ } else { if (prev==NULL) frhd = nxt->ptr; else prev->ptr = nxt->ptr; } memleft -= nunits; /* Return a pointer past the header to the actual space requested. */ return((char *)(nxt+1)); } } /* This function that explains what catastrophe befell us before resetting the system. */ warm_boot("Allocation Failed!"); return(NULL); } void i_alloc(void) { frhd = &_heapstart; /* Initialize the allocator. */ frhd->ptr = NULL; frhd->size = ((char *)&_heapend -- (char *)&_heapstart) / sizeof(HEADER); memleft = frhd->size; /* initial size in four-byte units */ } on entry to point to the original header for the block being returned. The block being freed could be located: • • • Lower in memory than the ﬁrst entry in the free list, in which case it becomes the new free-list head. Between entries in the free list. Higher in memory than the last entry and therefore linked to the end of the list. If the returned block is lower in memory than the ﬁrst entry, it’s linked as the new ﬁrst entry ahead of the previous free-list head. The free() function then calculates the address of the byte immediately following the returned block. If this address equals the address of the next free-space entry, the two entries combine to form one larger, contiguous free block. If the returned block is found to lie between two entries of the free list, we check to see if it’s contiguous to the 42 block lower in memory. If so, a larger contiguous block is formed. Similarly, we check to see if this new, larger block is contiguous to the entry just above it and, if so, make a larger contiguous block. If the entry isn’t found, we make a new entry in the free queue for the returned block (see Figure 3) and we again attempt to form a block that’s contiguous to the entry just above it in the free list. In this way, malloc() and free() assure that memory doesn’t stay fragmented after it’s freed. Eventually, if all the allocated blocks are freed, one free-list entry will point to one contiguous block containing all the heap space. A PRACTICAL EXAMPLE Our allocator has proved quite fast and efﬁcient in practice. For example, we used the allocator on a data communications switch based on a Motorola 6809 processor. The system switched data packets to and from an IBM PC and 10 terminals over 9,600-baud RS-232 serial lines. The terminals interfaced to other devices at lower baud rates. We used the allocator to dynamically allocate and release memory for the data packets. System constraints required that no port be allowed to monopolize the system, so we modiﬁed the code presented here (see Listing 1) to limit the amount of memory allocated to any one port. For each port, we speciﬁed upper and lower threshold for available memory. When a port hit or passed the lower threshold, it was marked busy and received no more packets from the ﬁle server until it freed enough memory to pass the upper threshold value. Because we wrote the allocator, modifying it for such low-level control was fairly easy. ■ In 1989, Lee Aldridge was president of Aldridge Real-Time Software Inc., a New Jersey-based software consulting company, and Programming ARTS, which specializes in developing software for the PC market. AUGUST 2008 | embedded systems design | www.embedded.com 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.