The C programming language (version 2) notes / 8 UNIX system interface / 8.7 instance (storage allocator)

Catalog 、 reference

---

8.7 example （ Storage allocator ）

We are the first 5 A stack oriented memory allocator with limited functions is given in chapter
There are no restrictions on the version to be written in this section , Can be called in any order malloc and free
malloc Call the operating system when necessary to get more storage space
These programs illustrate the issues that should be considered when writing system related code in a system independent manner , It also shows the structure 、 Joint and typedef Practical application of

malloc It does not allocate storage space from a fixed size array determined at compile time , Instead, you request space from the operating system when you need it
Because some parts of the program may not pass malloc Call to apply for space （ in other words , Apply for space by other means ）, therefore ,malloc The space of management is not necessarily continuous
such , The free storage space is organized as a free block linked list , Each block contains a length 、 A pointer to the next block and a pointer to its own storage space
These blocks are organized in ascending order of storage addresses , The last piece （ The highest address ） Point to the first block

When there is an application request ,malloc Will scan the free block linked list , Until you find a big enough block , The algorithm is called Adapt for the first time （first fit）
The opposite algorithm is The best fit （best fit）, It looks for the smallest piece that meets the conditions
If the block exactly matches the requested size , Then it will be removed from the linked list and returned to the user
If the block is too big , Then divide it into two parts ： The appropriate size block is returned to the user , The rest is left in the free block linked list
If you can't find a large enough block , Then apply to the operating system for a large block and add it to the free block linked list

The release process also searches the free block linked list first , To find the right place to insert the released block （ Insert the free block released this time into the free block linked list ）
If either side adjacent to the released block is a free block , Then the two blocks are combined into a larger block , In this way, there will not be too many fragments in the storage space
Because the free block linked list is linked together in the increasing order of addresses , Therefore, it is easy to determine whether adjacent blocks are free

We are the first 5 This question was raised in Chapter , That is to ensure that malloc The storage space returned by the function meets the alignment requirements of the object to be saved
Although the types of machines vary , however , Every particular machine has one of the most restricted types ： If the most restricted type can be stored in a specific address , All other types can also be stored in this address
In some machines , The most restricted type is double type , And in other machines , The most restricted type is int or long type

The free block contains a pointer to the next block in the linked list 、 A block size record and a pointer to the free space itself
The control information at the beginning of the block is called Head （header）
To simplify the alignment of blocks , The size of all blocks must be an integer multiple of the header size , And the head is correctly aligned
This is achieved through a joint , The union contains the desired head structure and an instance of the type with the most limited alignment requirements
In the following program , We assume that long Type is the most restricted type ：

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

union header {
     // block header
    struct {
    
        //  Point to the starting position of the next block in the free block list 
        union header *ptr; /* next block if on free list */
        /* * size  Is the size of the entire block , Not the size of the free part  *  The unit is  header  Size , Not bytes （ To align ） */
        unsigned size; /* size of this block */ 
    } s; 
    Align x; /* force alignment of blocks */ 
};

typedef union header Header;

In this Union ,Align Fields will never be used , It is only used to force each head to meet the alignment requirements in the worst case

stay malloc Function , The length of the request （ In characters ） Will be rounded off , To ensure that it is an integral multiple of the head size
The actual allocated block will contain one more unit , For the head itself
The size of the block actually allocated will be recorded in the header size Field
malloc The pointer returned by the function will point to the free space , Not the head of the block
The user can perform any operation on the obtained storage space , however , If you write data outside the allocated storage space , It may destroy the block linked list

chart 8-2malloc Returned block

Among them size Fields are required , Because the malloc Blocks controlled by functions are not necessarily continuous
Therefore, its size cannot be calculated by pointer arithmetic operation

Variable base Represents the header of the free block linked list
First call malloc Function time ,freep by NULL
The system will create a degenerate free block linked list , It contains only one size 0 The block , And the block points to itself
In any case , When free space is requested , Will search the free block linked list
Search where the last free block was found （freep） Start , This strategy can ensure that the linked list is uniform
If the block found is too large , Then return its tail to the user , such , The head of the initial block only needs to be modified size Field can be
In any case , The pointers returned to the user point to the free storage space in the block , That is, one unit larger than the pointer pointing to the head

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 *morecore(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 */ 
    } 
}

function morecore Used to request storage space from the operating system , The implementation details vary from system to system
Because requesting storage space from the system is an expensive operation , therefore , We don't want to call every time malloc Function
Based on this consideration ,morecore Function requests at least NALLOC A unit , This larger block will be divided into smaller blocks as needed
After setting up size After the fields ,morecore Function call free Function to insert extra storage space into the free area

UNIX system call sbrk(n) Return a pointer , The pointer points to n Bytes of storage space
If there is no free space , Despite returning NULL Maybe better , but sbrk Call return -1
Must be -1 Cast to char * type , To compare with the return value
and , Casts make the function unaffected by different pointer representations on different machines
however , It is still assumed that , from sbrk Multiple pointers to different blocks returned by the call can be compared meaningfully
ANSI The standard does not guarantee this , It only allows comparisons between pointers to the same array
therefore , Only on machines where the comparison between general pointers makes sense , The version malloc Function can be transplanted

#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 Function from freep Start at the address pointed to , Scan the free block linked list one by one , Find a place where you can insert free blocks
This location may be between two free blocks , It may also be at the end of the linked list
In any case , If the released block is adjacent to another free block , Then combine the two blocks
Merging two blocks is simple , Just set the pointer to the correct position , And set the correct block size

/* free: put block ap in free list */ 
void free(void *ap) 
{
     
    Header *bp, *p;

    /* *  Give Way  bp  Points to the block to be released  header *  because  ap  It refers to the part of the block to be released that will be treated as idle , Cast it to  Header *  Subtract after the pointer  1 *  It is equivalent to moving the pointer position to the low address direction  1  individual  Header  The size of the type data  *  Just moved to the block to be released  header  Starting position  */
    bp = (Header *)ap - 1; /* point to block header */
    /* * freep  Point to the starting position of the free block linked list （ Points to a block  header, Not the free part ） * for  Loop through the free block list ：for (p = freep; ...; p = p->s.ptr) *  Conditions  bp > p && bp < p->s.ptr  Indicates that the block to be released is already between the currently traversed free block and the next free block  *  Conditions  p >= p->s.ptr  Indicates that the end node of the free block linked list has been traversed  *  Conditions  (p >= p->s.ptr) && (bp > p || bp < p->s.ptr)  Indicates that the block to be released is after the tail node or before the head node  */
    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 */
        //  If the block to be released and  p->s.ptr  one by one , Will  p->s.ptr  Incorporate the block to be released 
        bp->s.size += p->s.ptr->s.size; 
        bp->s.ptr = p->s.ptr->s.ptr; 
    } else
        //  If the block to be released and  p->s.ptr  Not next to , Then... Of the block to be released  next  Pointer to  p->s.ptr
        bp->s.ptr = p->s.ptr;

    if (p + p->size == bp) {
     /* join to lower nbr */
        //  If the block to be released and  p  one by one , Then the block to be released is incorporated into  p
        p->s.size += bp->s.size; 
        p->s.ptr = bp->s.ptr; 
    } else
        //  If the block to be released and  p  Not next to , Will  p  Of  next  Pointer to  bp
        p->s.ptr = bp;

    /* * freep  Point to any node in the linked list , Because the linked list itself is a ring , Any node can be a header node  *  Here let it point to  p, Because if the original header node is merged to the back of a block , Then the original pointer to the header node does not correctly point to the starting position of the block  *  And merge anyway ,p  Is the starting position of a free block  *  therefore  freep = p  To ensure the  freep  It can point to the starting position of a free block  */
    freep = p; 
}

Although storage allocation is machine related in nature , however , The above code shows how to control the parts related to a specific machine , And control this part of the program to the minimum
typedef and union The use of has solved the problem of address alignment （ Assume sbrk The appropriate pointer is returned ） problem
Type casting makes the conversion of pointers explicit , This can even deal with system interface problems that are not well designed
Although the content here only involves storage allocation , however , This general method can also be used in other cases

---

Catalog 、 reference