A Storage Allocator sample program in C

By: Emiley J Emailed: 1606 times Printed: 2075 times    

Latest comments
By: rohit kumar - how this program is work
By: Kirti - Hi..thx for the hadoop in
By: Spijker - I have altered the code a
By: ali mohammed - why we use the java in ne
By: ali mohammed - why we use the java in ne
By: mizhelle - when I exported the data
By: raul - no output as well, i'm ge
By: Rajesh - thanx very much...
By: Suindu De - Suppose we are executing

In this tutorial let us write a storage allocator which is unrestricted. Calls to malloc and free may occur in any order; malloc calls upon the operating system to obtain more memory as necessary. These routines illustrate some of the considerations involved in writing machine-dependent code in a relatively machine-independent way, and also show a real-life application of structures, unions and typedef.

Rather than allocating from a compiled-in fixed-size array, malloc will request space from the operating system as needed. Since other activities in the program may also request space without calling this allocator, the space that malloc manages may not be contiguous. Thus its free storage is kept as a list of free blocks. Each block contains a size, a pointer to the next block, and the space itself. The blocks are kept in order of increasing storage address, and the last block (highest address) points to the first.

 

When a request is made, the free list is scanned until a big-enough block is found. This algorithm is called ``first fit,'' by contrast with ``best fit,'' which looks for the smallest block that will satisfy the request. If the block is exactly the size requested it is unlinked from the list and returned to the user. If the block is too big, it is split, and the proper amount is returned to the user while the residue remains on the free list. If no big-enough block is found, another large chunk is obtained by the operating system and linked into the free list.

Freeing also causes a search of the free list, to find the proper place to insert the block being freed. If the block being freed is adjacent to a free block on either side, it is coalesced with it into a single bigger block, so storage does not become too fragmented. Determining the adjacency is easy because the free list is maintained in order of decreasing address.

One problem, is to ensure that the storage returned by malloc is aligned properly for the objects that will be stored in it. Although machines vary, for each machine there is a most restrictive type: if the most restrictive type can be stored at a particular address, all other types may be also. On some machines, the most restrictive type is a double; on others, int or long suffices.

A free block contains a pointer to the next block in the chain, a record of the size of the block, and then the free space itself; the control information at the beginning is called the ``header.'' To simplify alignment, all blocks are multiples of the header size, and the header is aligned properly. This is achieved by a union that contains the desired header structure and an instance of the most restrictive alignment type, which we have arbitrarily made a long:

   typedef long Align;    /* for alignment to long boundary */

   union header {         /* block header */
       struct {
           union header *ptr; /* next block if on free list */
           unsigned size;     /* size of this block */
       } s;
       Align x;           /* force alignment of blocks */
   };

   typedef union header Header;
The Align field is never used; it just forces each header to be aligned on a worst-case boundary.

In malloc, the requested size in characters is rounded up to the proper number of header-sized units; the block that will be allocated contains one more unit, for the header itself, and this is the value recorded in the size field of the header. The pointer returned by malloc points at the free space, not at the header itself. The user can do anything with the space requested, but if anything is written outside of the allocated space the list is likely to be scrambled.

The size field is necessary because the blocks controlled by malloc need not be contiguous - it is not possible to compute sizes by pointer arithmetic.

The variable base is used to get started. If freep is NULL, as it is at the first call of malloc, then a degenerate free list is created; it contains one block of size zero, and points to itself. In any case, the free list is then searched. The search for a free block of adequate size begins at the point (freep) where the last block was found; this strategy helps keep the list homogeneous. If a too-big block is found, the tail end is returned to the user; in this way the header of the original needs only to have its size adjusted. In all cases, the pointer returned to the user points to the free space within the block, which begins one unit beyond the header.

   static Header base;       /* empty list to get started */
   static Header *freep = NULL;     /* start of free list */

   /* malloc:  general-purpose storage allocator */
   void *malloc(unsigned nbytes)
   {
       Header *p, *prevp;
       Header *moreroce(unsigned);
       unsigned nunits;

       nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
       if ((prevp = freep) == NULL) {   /* no free list yet */ 
           base.s.ptr = freeptr = prevptr = &base;
           base.s.size = 0;
       }
       for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
           if (p->s.size >= nunits) {  /* big enough */
               if (p->s.size == nunits)  /* exactly */
                   prevp->s.ptr = p->s.ptr;
               else {              /* allocate tail end */
                   p->s.size -= nunits;
                   p += p->s.size;
                   p->s.size = nunits;
               }
               freep = prevp;
               return (void *)(p+1);
           }
           if (p == freep)  /* wrapped around free list */
               if ((p = morecore(nunits)) == NULL)
                   return NULL;    /* none left */
       }
   }
The function morecore obtains storage from the operating system. The details of how it does this vary from system to system. Since asking the system for memory is a comparatively expensive operation. we don't want to do that on every call to malloc, so morecore requests al least NALLOC units; this larger block will be chopped up as needed. After setting the size field, morecore inserts the additional memory into the arena by calling free.

The UNIX system call sbrk(n) returns a pointer to n more bytes of storage. sbrk returns -1 if there was no space, even though NULL could have been a better design. The -1 must be cast to char * so it can be compared with the return value. Again, casts make the function relatively immune to the details of pointer representation on different machines. There is still one assumption, however, that pointers to different blocks returned by sbrk can be meaningfully compared. This is not guaranteed by the standard, which permits pointer comparisons only within an array. Thus this version of malloc is portable only among machines for which general pointer comparison is meaningful.

   #define NALLOC  1024   /* minimum #units to request */

   /* morecore:  ask system for more memory */
   static Header *morecore(unsigned nu)
   {
       char *cp, *sbrk(int);
       Header *up;

       if (nu < NALLOC)
           nu = NALLOC;
       cp = sbrk(nu * sizeof(Header));
       if (cp == (char *) -1)   /* no space at all */
           return NULL;
       up = (Header *) cp;
       up->s.size = nu;
       free((void *)(up+1));
       return freep;
   }
free itself is the last thing. It scans the free list, starting at freep, looking for the place to insert the free block. This is either between two existing blocks or at the end of the list. In any case, if the block being freed is adjacent to either neighbor, the adjacent blocks are combined. The only troubles are keeping the pointers pointing to the right things and the sizes correct.
   /* free:  put block ap in free list */
   void free(void *ap)
   {
       Header *bp, *p;

       bp = (Header *)ap - 1;    /* point to  block header */
       for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
            if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
                break;  /* freed block at start or end of arena */

       if (bp + bp->size == p->s.ptr) {    /* join to upper nbr */
           bp->s.size += p->s.ptr->s.size;
           bp->s.ptr = p->s.ptr->s.ptr;
       } else
           bp->s.ptr = p->s.ptr;
       if (p + p->size == bp) {            /* join to lower nbr */
           p->s.size += bp->s.size;
           p->s.ptr = bp->s.ptr;
       } else
           p->s.ptr = bp;
       freep = p;
   }
Although storage allocation is intrinsically machine-dependent, the code above illustrates how the machine dependencies can be controlled and confined to a very small part of the program. The use of typedef and union handles alignment (given that sbrk supplies an appropriate pointer). Casts arrange that pointer conversions are made explicit, and even cope with a badly-designed system interface. Even though the details here are related to storage allocation, the general approach is applicable to other situations as well.

C Home | All C Tutorials | Latest C Tutorials

Sponsored Links

If this tutorial doesn't answer your question, or you have a specific question, just ask an expert here. Post your question to get a direct answer.



Bookmark and Share

Comments(0)


Be the first one to add a comment

Your name (required):


Your email(required, will not be shown to the public):


Your sites URL (optional):


Your comments:



More Tutorials by Emiley J
Password must include both numeric and alphabetic characters - Magento
What is Hadoop?
Returning multiple values from a web service
Tomcat and httpd configured in port 8080 and 80
Java Webservices using Netbeans and Tomcat
Java WebService connected to Database
How to Deploy a Java Web Service
Call a webservice in Java
Java WebService - Create your first web service in Java
package javax.jws does not exist
Getting Started with Android
HTML5 Location - getCurrentPosition() in HTML5
HTML5 Canvas - Using Canvas in HTML5
HTML5 - Introduction
HTML5 Video - Handling video in HTML5

More Tutorials in C
Sum of the elements of an array in C
Printing a simple histogram in C
Sorting an integer array in C
Find square and square root for a given number in C
Simple arithmetic calculations in C
Command-line arguments in C
Calculator in C
Passing double value to a function in C
Passing pointer to a function in C
Infix to Prefix And Postfix in C
while, do while and for loops in C
Unicode and UTF-8 in C
Formatting with printf in C
if, if...else and switch statements in C with samples
Statements in C

More Latest News
Most Viewed Articles (in C )
Using memset(), memcpy(), and memmove() in C
Open, Creat, Close, Unlink system calls sample program in C
Listing Files and Directories sample program in C
perror() Function - example program in C
scanf and sscanf sample program in C
UNIX read and write system calls sample program in C
Using free() Function in C
assert() Function Example program in C
Printing a simple histogram in C
Sum of the elements of an array in C
lseek() sample program in C
Find square and square root for a given number in C
fgets(), fputs() - Line Input and Output - sample program in C
Fopen and Getc implementation program in C
Sorting an integer array in C
Most Emailed Articles (in C)
Address Arithmetic and pointers in C
Macro Substitution using #define in C
Pointers to Structures example program in C
Getting Started with C
Variables and Arithmetic Expressions in C
register Variables in C
Trigonometric, Hyperbolic, Exponential and Logarithmic Functions in C
Printing a simple histogram in C
Symbolic Constants using #define in C
Arguments - Call by Value in C
Conditional Expressions in C
Functions returning non-integer values in C
Recursion in C
Tutorial on Complicated Declarations in C
Standard Input and Output in C