Thread: Implementing malloc and free

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    50

    Implementing malloc and free

    Hi guys, I have buffer with VERY Big SIZE , how could I implement malloc and free functions without using with already functions malloc and free that C provides, any help how can I do that?

    Appreciated.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Which OS and Compiler ?

    What constitutes "VERY Big SIZE" ?
    10's of gigabytes?

    How much physical memory do you really have?
    Because just reimplementing malloc "for fun" won't get you past various system restrictions.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2019
    Posts
    50
    Quote Originally Posted by Salem View Post
    Which OS and Compiler ?

    What constitutes "VERY Big SIZE" ?
    10's of gigabytes?

    How much physical memory do you really have?
    Because just reimplementing malloc "for fun" won't get you past various system restrictions.
    about 10 gigabytes, -not for fun- frankly ..just for getting the concept of how malloc works dynamically ..

    regarding to OS AND COMPILER , it's windows and VISUAL STUDIO.

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    The basic idea is to store extra information before each object's storage in the buffer. Storing the size of the allocated block is the minimum amount of information. In practice, it's better to store pointers, too, which connect that block to a doubly-linked list of blocks.

    You need to keep track of the unused blocks as well, including the "holes" left from freeing blocks. So you would have two linked lists, used and unused.

    When allocating memory you search the unused list for a block that's large enough, move it from the unused to used list, and serve it up. If no block is large enough, return NULL.

    When freeing memory, you need to move the block from the used to unused list and coalesce it with any contiguous blocks.

    This is all ignoring alignment isses, the upshot of which is that the served-up data blocks need to be properly aligned for the data they will hold. For something as general as malloc, the returned blocks are aligned for the largest possible basic type, I think usually 8 or 16 bytes.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  5. #5
    Registered User
    Join Date
    Nov 2019
    Posts
    50
    Quote Originally Posted by john.c View Post
    The basic idea is to store extra information before each object's storage in the buffer. Storing the size of the allocated block is the minimum amount of information. In practice, it's better to store pointers, too, which connect that block to a doubly-linked list of blocks.

    You need to keep track of the unused blocks as well, including the "holes" left from freeing blocks. So you would have two linked lists, used and unused.

    When allocating memory you search the unused list for a block that's large enough, move it from the unused to used list, and serve it up. If no block is large enough, return NULL.

    When freeing memory, you need to move the block from the used to unused list and coalesce it with any contiguous blocks.

    This is all ignoring alignment isses, the upshot of which is that the served-up data blocks need to be properly aligned for the data they will hold. For something as general as malloc, the returned blocks are aligned for the largest possible basic type, I think usually 8 or 16 bytes.
    So you mean it's not an easy/simple question ..? regarding to what you're describing I need to write code about 500 rows's code .. and not just one simple function to write ..

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    It's as complicated as you want to make it.

    You could write something completely dumb in 20 lines.

    You could write something smarter in 100 lines (see the example in K&R-2)

    You could do something very sophisticated in 500 lines.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Nov 2019
    Posts
    50
    could you attach me the link for the example, I just entered here K&R2 solutions:Chapter 2:Exercise 8 - clc-wiki and didn't find malloc/free implementation, thanks alot.

  8. #8
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    So now you're too lazy to even look through those exercises to find it?
    A little inaccuracy saves tons of explanation. - H.H. Munro

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Read Chapter 8
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 12-28-2012, 04:07 PM
  2. malloc and free
    By TLV in forum C Programming
    Replies: 3
    Last Post: 07-11-2012, 05:38 AM
  3. about C malloc and free
    By lkiversonlk in forum C Programming
    Replies: 4
    Last Post: 03-25-2012, 04:52 AM
  4. Malloc - Free giving double free or corruption error
    By andrew.bolster in forum C Programming
    Replies: 2
    Last Post: 11-02-2007, 06:22 AM
  5. Malloc and Free.....
    By heljy in forum C Programming
    Replies: 5
    Last Post: 04-14-2002, 09:17 PM

Tags for this Thread