Thread: Dynamically allocated memory

  1. #1
    FOX
    Join Date
    May 2005
    Posts
    188

    Dynamically allocated memory

    If I understand it correctly, Linux will actually try to be smart when I make a request to allocate memory, and allocate a page at a time? So when I make a call to malloc to request 100 bytes, it will actually allocate a page size instead (4096 bytes I think)?

    The reason I'm asking is because I was looking at some really funky code someone else has written, and the only reason I can think of that it works is that dynamic memory allocation works like I have described above.

    The code below will only work because an entire memory page is allocated and set to zero, so the string will automatically become null terminated even though the code is not really allocating enough space for the nul character.

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int main(void)
    {
            size_t len;
            const char s[] = "Hello";
            char *p;
    
            len = strlen(s+1); /* What the hell was he thinking? */
            printf("len = %d\n", len);
            p = calloc(1, len);
            if (!p)
                    return 1;
            memcpy(p, s, len+1);
    
            printf("s is now: '%s'\n", p);
    
            return 0;
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Try
    gcc prog.c -lefence
    then.

    The code is wrong - that it works at all is down to luck, not judgement.
    In a much larger program, you'd be looking for random segfaults.
    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
    FOX
    Join Date
    May 2005
    Posts
    188
    That's what I suspected. So I was right about the way memory is allocated?

  4. #4
    .
    Join Date
    Nov 2003
    Posts
    307
    I don't think so - you aren't right. The reason it works is because brk() has page-level granularity. brk() is called first by the process to get some pages of dynamic memory.

    Salem is right - if more variables are malloc'ed the code will fail.

    If you want to see how malloc works read:
    http://www-106.ibm.com/developerwork...lnxw16InsideMe

  5. #5
    FOX
    Join Date
    May 2005
    Posts
    188
    From Programming from the group up:
    Now, in order to make the process more efficient, memory is separated out into
    groups called pages. When running Linux on x86 processors, a page is 4096 bytes
    of memory. All of the memory mappings are done a page at a time. Physical
    memory assignment, swapping, mapping, etc. are all done to memory pages
    instead of individual memory addresses.
    Wouldn't that mean that the first time I allocate some dynamic memory, an entire page is mapped? So regardless of what memory manager I'm using, Linux will always do it's own thing and allocate more memory than I actually need. The memory manager in my program will just not know that more memory is mapped than it asked for. Of course, if I allocate more memory after that, Linux will just use some of the extra memory it allocated the first time if it fits within the first page. I read everything in the link you posted, and this seems to support what I just wrote (referring to the simple memory manager in the link):
    Because sbrk() may give back more memory than we ask for, we leak some memory at the end of the heap.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > Wouldn't that mean that the first time I allocate some dynamic memory, an entire page is mapped?
    Sure the whole page is mapped, but that doesn't mean all the memory in the page is automatically available for you to use. Other calls to malloc will also allocate memory from the same page as well, and then where will you be (staring down the barrel of a segfault).

    As I understand things, sbrk() asks for a lot more memory than just one page, because such calls are really expensive compared to malloc. It also wouldn't surprise me if Linux first mapped pages on actual use rather than when you called sbrk() in the first place.
    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
    FOX
    Join Date
    May 2005
    Posts
    188
    > Other calls to malloc will also allocate memory from the same page as well, and then where will you be (staring down the barrel of a segfault).

    What exactly will cause the segfault though? You're reading and writing to mapped memory all the time, so you shouldn't have any problems until you try to free some allocated memory (whose control block structure might have been overwritten)? And that should only cause free to fail, but not a segfault since you're still accessing valid memory.

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    
    int main(void)
    {
            int i, j;
            char *p1, *p2;
    
            p1 = malloc(10);
            for (i=0; i<1000; i++)
                    p1[i] = 'A';
    
            p2 = malloc(1000);
            for (i=0; i<1000; i++)
                    p2[i] = 'B';
    
            for(i=0; i<2000; i++)
            {
                    for (j=0; j<79; j++)
                    {
                            putchar(p1[i]);
                            ++i;
                    }
                    putchar('\n');
            }
            free(p1);
            free(p2); /* This will fail. */
    
            return 0;
    }
    Last edited by ^xor; 06-28-2005 at 09:35 AM.

  8. #8
    FOX
    Join Date
    May 2005
    Posts
    188
    This one is better, but now I'm getting confused.
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    
    int main(void)
    {
            int i, j;
            char *p1, *p2;
    
            /*
             * Overwrite boundary a lot.
             */
            p1 = malloc(10);
            for (i=0; i<1000; i++)
                    p1[i] = 'A';
            /*
             * This is fine, although you're overwriting most of what
             * p1 wrote to memory.
             */
            p2 = malloc(1000);
            for (i=0; i<1000; i++)
                    p2[i] = 'B';
            /*
             * Overwrite boundary again, this time overwriting the memory control
             * structure for p2.
             */
            for (i=0; i<1000; i++)
                    p1[i] = 'C';
    
            for(i=0; i<2000; i++)
            {
                    for (j=0; j<79; j++)
                    {
                            putchar(p1[i]);
                            ++i;
                    }
                    putchar('\n');
            }
            free(p1); /* Why does this fail? The control structure is still there */
            free(p2); /* This should fail, but it doesn't... Why? */
    
            return 0;
    }

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > What exactly will cause the segfault though?
    Usually it's a following malloc or free call as it tries to use whatever crud you wrote as a pointer.

    One popular way of managing all the memory in the pool is to have a linked list of all the allocated blocks of memory, and another linked list of all the free blocks of memory. So even though you don't trash "the control structure of the memory you're freeing", the code can still traverse it's lists to something you have trashed.

    When you malloc() or free(), you basically move a block of memory from one list to another.

    But if in the meantime, you've trashed the link pointers with your errant code, this simply isn't going to work anymore. Now if you have lots of allocated memory, it could be a while before the particular bit which you trashed actually gets noticed by a following malloc or free call (this is what makes these kinds of bugs so much fun to find!).

    > This should fail, but it doesn't... Why?
    Extrapolating the universe from a single test case isn't possible. A failure to crash does not constitute correct code.
    If it crashes, it has a bug.
    If it doesn't crash, at best you can say you haven't found the bug yet.

    So when you say "this is fine", you really mean it's in the 2nd category (buggy has hell, but no ones noticed yet).

    Did you try any of this with electric fence running (see previous -lefence)
    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.

  10. #10
    FOX
    Join Date
    May 2005
    Posts
    188
    So the "memory control structures" that I referred to, are actually nodes in a linked list (glibc implementation)?

    Code:
    p1 = malloc(10); /* Set p1node->next=NULL; */
    p2 = malloc(1000); */ Set p1node->next=p2node, p2node->next=NULL */
    This explains why glibc was complaining when I was trying to free p1, but not p2 (since p2node->next=NULL). The p1node->next was pointing to p2node, but I had already trashed that node when I overwrote the p1 buffer, so the node data was completely screwed up.

    Am I right?


    > So when you say "this is fine", you really mean it's in the 2nd category (buggy has hell, but no ones noticed yet).

    Look at the code where I wrote it. I'm staying withing the bounds allocated for p2, so that's why I said it's fine.
    Last edited by ^xor; 06-28-2005 at 11:44 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Mutex and Shared Memory Segment Questions.
    By MadDog in forum Linux Programming
    Replies: 14
    Last Post: 06-20-2010, 04:04 AM
  2. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  3. To find the memory leaks without using any tools
    By asadullah in forum C Programming
    Replies: 2
    Last Post: 05-12-2008, 07:54 AM
  4. What's the difference?
    By Stonehambey in forum C++ Programming
    Replies: 9
    Last Post: 04-02-2008, 10:26 AM
  5. deleting dynamically allocated memory...
    By heljy in forum C++ Programming
    Replies: 2
    Last Post: 09-08-2002, 11:40 AM