inside the memory allocation (1)

1. malloc（）algorithm

1. If our allocator has not been initialized, initialize it.

2. Add sizeof(struct mem_control_block) to the size requested.

3. Start at managed_memory_start.

4. Are we at last_valid address?

5. If we are:

   A. We didn't find any existing space that was large enough
      -- ask the operating system for more and return that.

6. Otherwise:

   A. Is the current space available (check is_available from
      the mem_control_block)?

   B. If it is:

      i)   Is it large enough (check "size" from the
           mem_control_block)?

      ii)  If so:

           a. Mark it as unavailable

           b. Move past mem_control_block and return the
              pointer

      iii) Otherwise:

           a. Move forward "size" bytes

           b. Go back go step 4

   C. Otherwise:

      i)   Move forward "size" bytes

      ii)  Go back to step 4

2. Defined global variables

malloc_init is going to be our function to initialize our memory allocator. It does three things: marks our allocator as being initialized, finds the last valid memory address on the system, and sets up the pointer to the beginning of our managed memory. These three variables are global variables:

int has_initialized = 0;
void *managed_memory_start;
void *last_valid_address;

3. The malloc_init() function

As mentioned above, the edge of mapped memory -- last valid address -- is often known as the system break or the current break. On many UNIX® systems, to find the current system break, you use the function sbrk(0). sbrk moves the current system break by the number of bytes in its argument, and then returns the new system break. Calling it with an argument of 0 simply returns the current break. Here is our malloc initialization code, which finds the current break and initializes our variables:

void malloc_init()
{
    /* grab the last valid address from the OS */
    last_valid_address = sbrk(0);
    /* 
    * we don't have any memory to manage yet, so
    * just set the beginning to be last_valid_address
    */
    managed_memory_start = last_valid_address;
    /* Okay, we're initialized and ready to go */
    has_initialized = 1;
}

4. The Memory Control Block

Now, in order to properly manage memory, we need to be able to track what we are allocating and deallocating. We need to do things like mark blocks as unused after free has been called on them, and be able to locate unused blocks when malloc is called. Therefore, the start of every piece of memory returned by malloc will have this structure at the beginning:

struct mem_control_block {
    int is_available;
    int size;
};

Now, you might think that this would cause problems for programs calling malloc -- how do they know about this struct? The answer is that they don't have to know about it; we will hide it by moving the pointer past this struct before we return it. This will make the returned pointer point to memory that is not used for any other purpose. That way, from the calling programs' perspective, all they get is free, open memory. Then, when they pass the pointer back via free(), we simply back up a few memory bytes to find this structure again.

We're going to talk about freeing before we talk about allocating memory, because it's simpler. The only thing we have to do to free memory is to take the pointer we're given, back up sizeof(struct mem_control_block) bytes, and mark it as available. Here is the code for that:

5. The void free(void *ptr) function

For freeing memoty, get the ptr of the allocated memory, and move back
"sizeof(struct mem_control_block)" chars, then mark it as available.

void free(void *firstbyte) 
{
    struct mem_control_block *mcb;
    /* 
     * Backup from the given pointer 
     * to find the mem_control_block
     */
    mcb = firstbyte - sizeof(struct mem_control_block);
    /* Mark the block as being available */
    mcb->is_available = 1;
    /* That's It!  We're done. */
    return;
}

6. The void *malloc(size_t size) function

void *malloc(long numbytes) {
    /* Holds where we are looking in memory */
    void *current_location;
    /* This is the same as current_location, but cast to a
     * memory_control_block
     */
    struct mem_control_block *current_location_mcb;
    /* This is the memory location we will return.  It will
     * be set to 0 until we find something suitable
     */
    void *memory_location;
    /* Initialize if we haven't already done so */
    if(! has_initialized) {
        malloc_init();
    }
    /* The memory we search for has to include the memory
     * control block, but the users of malloc don't need 
     * to know this, so we'll just add it in for them.
     */
    numbytes = numbytes + sizeof(struct mem_control_block);
    /* Set memory_location to 0 until we find a suitable
     * location
     */
    memory_location = 0;
    /* Begin searching at the start of managed memory */
    current_location = managed_memory_start;
    /* Keep going until we have searched all allocated space */
    while(current_location != last_valid_address)
    {
        /* current_location and current_location_mcb point
         * to the same address.  However, current_location_mcb
         * is of the correct type, so we can use it as a struct.
         * current_location is a void pointer so we can use it
         * to calculate addresses.
         */
        current_location_mcb =
        (struct mem_control_block *)current_location;
        if(current_location_mcb->is_available)
        {
            if(current_location_mcb->size >= numbytes)
            {
            /* Woohoo!  We've found an open,
             * appropriately-size location.
             */
                /* It is no longer available */
                current_location_mcb->is_available = 0;
                /* We own it */
                memory_location = current_location;
                /* Leave the loop */
                break;
            }
        }
        /* If we made it here, it's because the Current memory
         * block not suitable; move to the next one
         */
        current_location = current_location +
        current_location_mcb->size;
    }
    /* If we still don't have a valid location, we'll
     * have to ask the operating system for more memory
     */
    if(! memory_location)
    {
        /* Move the program break numbytes further */
        sbrk(numbytes);
        /* The new memory will be where the last valid
         * address left off
         */
        memory_location = last_valid_address;
        /* We'll move the last valid address forward
         * numbytes
         */
        last_valid_address = last_valid_address + numbytes;
        /* We need to initialize the mem_control_block */
        current_location_mcb = memory_location;
        current_location_mcb->is_available = 0;
        current_location_mcb->size = numbytes;
    }
    /* Now, no matter what (well, except for error conditions),
     * memory_location has the address of the memory, including
     * the mem_control_block
     */
    /* Move the pointer past the mem_control_block */
    memory_location = memory_location + sizeof(struct mem_control_block);
    /* Return the pointer */
    return memory_location;
}

7. reference:
-http://www.ibm.com/developerworks/linux/library/l-memory/