Thread: Allocate memory inside allocated memory block?

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    5

    Smile Allocate memory inside allocated memory block?

    Hi,

    I'm curious if it is possible to "allocate" chunks of memory inside an already allocated memory block.

    char *block = malloc( 1024 * 1024 );

    Here I have 1MB RAM allocated. Now, my program wants to allocate several chunks of memory FROM this block. (Don't ask why:-))

    Anyone know if this is possible? If so please tell how. I am new to "C" and have less knowledge about the nitty-gritty of explicit dynamic memory allocation.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    As in you want to use block as your own memory pool?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Sure it's possible. You just have to replicate (a small part of) what malloc (and free?) does internally - track what parts of that memory (location and size) has been used, and which parts are free, and dole out a section of available memory of sufficient size to the calling code - and if you need to allow free as well, you will need to also mark the memory as free when a call to "myfree" is made.

    I'd expect you have been given this as an assignment at school, so I will not break the code of conduct of the forum and give you an answer. If that is not the case, you'd have to explain the bit that you say "don't ask why"....

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    I have to ask... why do you want to do this?? :P

    To answer your question, yes you can. You will need to have variables to track the beginning and end of each of your blocks within the larger block...

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    5
    Thx for your insight. You guys helped me with your time. May be I can share this secret!
    Mats -> I had a kinda debate with a frend. He says it is IMPOSSIBLE and I thought it would..now I am looking for a piece of code that proves this concept.
    Hope he is not reading this ..

  6. #6
    Registered User
    Join Date
    Apr 2009
    Posts
    5
    Quote Originally Posted by Bladactania View Post
    I have to ask... why do you want to do this?? :P

    To answer your question, yes you can. You will need to have variables to track the beginning and end of each of your blocks within the larger block...
    And how do I implement this?
    Let us assume I have 5 users using a server space.
    Each of them invokes malloc() to claim his share of memory - say 1 MB each. Having done so each user has to manage this memory among 5 processes requesting for space on this 1 MB. So if u can visualize the complexity that arises here. Assume process P1 requests for 200 KB space.
    How can the user/programmer allocate this 200 KB to P1 from this 1 MB, when the 1 MB has already been allocated? I understand your concept .. but implementation seems tricky.

  7. #7
    Registered User
    Join Date
    Apr 2009
    Posts
    5

    Thumbs up

    Quote Originally Posted by matsp View Post
    Sure it's possible. You just have to replicate (a small part of) what malloc (and free?) does internally - track what parts of that memory (location and size) has been used, and which parts are free, and dole out a section of available memory of sufficient size to the calling code - and if you need to allow free as well, you will need to also mark the memory as free when a call to "myfree" is made.

    I'd expect you have been given this as an assignment at school, so I will not break the code of conduct of the forum and give you an answer. If that is not the case, you'd have to explain the bit that you say "don't ask why"....

    --
    Mats
    Thx for your insight. Assuming a contiguous memory chunk of 1MB.
    1) How I can track which parts are free and which are used?
    2) Can u please mention any useful methods to allocate a chunk of memory from a bulk that is already allocated (using malloc() ) ?

    I need to prove, this thing is POSSIBLE to a friend - the so called-GEEK!!

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Well, an easy solution is to search the Web for "memory pool", then pick some existing memory pool implementation and show it to your friend.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Heidi_Nayak View Post
    Thx for your insight. You guys helped me with your time. May be I can share this secret!
    Mats -> I had a kinda debate with a frend. He says it is IMPOSSIBLE and I thought it would..now I am looking for a piece of code that proves this concept.
    Hope he is not reading this ..
    If it is impossible to take a contiguous chunk of memory (for instance, all the RAM in your system) and allocate blocks from it... Then how exactly does malloc() work?

    Maybe what your friend is saying is that it's impossible to use malloc() to allocate from a sub-block, and that is true, at least with the standard malloc(). But is it possible to carve up memory yourself? Of course it is.

    It's not complicated if you don't intend to implement a MyFree() sort of method. If you never free, then you don't need bookkeeping, and you can get away with a simple counter that tells you where the next chunk of unallocated space is, and how big it is.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    I think you need to be clear on something... You wouldn't be strictly allocating memory from this 1MB again. You would be simulating it instead... kind of writing a memory manager over top of the existing memory manager.

    without thinking about it too much...
    1. Lets say you have 1000 bytes of memory allocated for your memory pool (I pick 1000 because its a nice round number).
    2. You need to keep track of which bytes are "allocated" and to which process. Sounds like a structure to me...

    Code:
    #define MEM_SIZE 1000
    #define FALSE 0
    #define TRUE 1
    
    typedef struct mem_block{
      int Is_Allocated;
      int Process_ID;
    } mem_block;
    
    char block[MEM_SIZE]; // I'm using a predetermined size, but mem_block *block = malloc(MEM_SIZE); would work too
    mem_block block_track[MEM_SIZE];
    3. Now when a process requests a block of memory, you have to search for a contiguous chunk of memory in some sort of loop. So you need your own version of the malloc() function

    Code:
    char * my_malloc(int size, int process_id) {
      int Block_Index = 0;
      int Size_Count = 0;
      int Start_Index = 0;
    
      while (Block_Index < MEM_SIZE) {
        if (block[Block_Index].Is_Allocated == TRUE) {
          Size_Count = 0; // Reset Size Count
          Block_Index++;
          Start_Index = Block_Index;
        } else {
          Size_Count++;
        }
    
        if (Size_Count == size) break;  // We have found a chunk big enough!
      }
    
      // Now check Size_Count to see if we found one big enough...
      if (Size_Count == size) {
        // We did!  Now allocate the memory block
        for (Block_Index = Start_Index; Block_Index < Start_Index + size; Block_Index++) {
          block[Block_Index].Is_Allocated = TRUE;
          block[Block_Index].Process_ID = process_id;
        }
      
        // Now return a pointer to the starting point of the memory block
        return &(block[Block_Index]); // I'm not 100% sure if this is correct...
      } else {
        // We didnt :(  return a null pointer
        return 0;
      }
    }
    Now you'll need to write a free() function to deallocate the memory when necessary.

  11. #11
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Quote Originally Posted by laserlight View Post
    Well, an easy solution is to search the Web for "memory pool", then pick some existing memory pool implementation and show it to your friend.
    That, or just show him a Java VM (or any other language with garbage collection).

  12. #12
    Registered User
    Join Date
    Apr 2009
    Posts
    5

    Smile

    Quote Originally Posted by Bladactania View Post
    I think you need to be clear on something... You wouldn't be strictly allocating memory from this 1MB again. You would be simulating it instead... kind of writing a memory manager over top of the existing memory manager.
    thx Bladactania. I really appreciate it.

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Bladactania View Post
    I think you need to be clear on something... You wouldn't be strictly allocating memory from this 1MB again. You would be simulating it instead...
    I don't see why it's simulation. Allocation isn't a special concept where it's only "allocation" if the runtime does it.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    perhaps the simplest (and quite effective) way is to divide 1MB to smaller "slots", and mark these as used or unused. When user requests memory, calculate how many slots is needed and mark them used. Add some "header" field to beginning of allocated chunck (Eg. information like size of allocated chucnk), and return to user a pointer which points to space right after this header. When memory is freed, calculate the beginning of header field based on pointer to memory being freed, read size of allocation, and mark the blocks unused again. You can also have some nifty extra features, like endmark at the end of allocated chunck (when user frees the memory, check that endmark was not overwritten - this helps to analyze possible buffer overwritings). You can also use the header to store a pointer to callback function which allocater can register (to offer "destructor" functionality) etc.

    This kind of memory pools are not rare - they're regularly used for example when sharing memory between processes.

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Maz View Post
    perhaps the simplest (and quite effective) way is to divide 1MB to smaller "slots", and mark these as used or unused. When user requests memory, calculate how many slots is needed and mark them used. Add some "header" field to beginning of allocated chunck (Eg. information like size of allocated chucnk), and return to user a pointer which points to space right after this header. When memory is freed, calculate the beginning of header field based on pointer to memory being freed, read size of allocation, and mark the blocks unused again. You can also have some nifty extra features, like endmark at the end of allocated chunck (when user frees the memory, check that endmark was not overwritten - this helps to analyze possible buffer overwritings). You can also use the header to store a pointer to callback function which allocater can register (to offer "destructor" functionality) etc.

    This kind of memory pools are not rare - they're regularly used for example when sharing memory between processes.
    And if you make the "slots" a single byte, that is pretty much what a basice implementation of malloc would do.

    And by the way, malloc pretty much does what we have described here, except with the difference that it doesn't call malloc, but some function that (eventually, some layers down becomes) a system call to ask for a relatively large block of memory. In Unix, it would be sbrk(), in Windows, it would be something like HeapAllocate or VirtualAlloc.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Assignment Operator, Memory and Scope
    By SevenThunders in forum C++ Programming
    Replies: 47
    Last Post: 03-31-2008, 06:22 AM
  2. Question regarding Memory Leak
    By clegs in forum C++ Programming
    Replies: 29
    Last Post: 12-07-2007, 01:57 AM
  3. How to store any value in Memory (inside chip) ?
    By burhanahmad in forum C Programming
    Replies: 3
    Last Post: 04-29-2005, 09:48 AM
  4. pointers
    By InvariantLoop in forum C Programming
    Replies: 13
    Last Post: 02-04-2005, 09:32 AM
  5. Is it necessary to write a specific memory manager ?
    By Morglum in forum Game Programming
    Replies: 18
    Last Post: 07-01-2002, 01:41 PM