I would like a logic check, please.

This is a discussion on I would like a logic check, please. within the C Programming forums, part of the General Programming Boards category; I've got this for my pmm, but it's ugly. Speed is very important, so I tried to make it as ...

  1. #1
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587

    I would like a logic check, please.

    I've got this for my pmm, but it's ugly. Speed is very important, so I tried to make it as simple as possible, but also very fast. I'm kinda dissatisfied with it and not sure it will function as it's supposed to. I'm nowhere near(weeks away) from being able to compile, so I need some reassurance that it's correct before I proceed with development. If anyone can help me simplify it, or point out a bug, I'd greatly appreciate it.
    Code:
    unsigned int get_pages(int pages)
    {
        int i,j = 0;
        for(i = reserved_low_pages + 1;i + pages <= total_pages;i += (j + 1))
            for(j = 0;j <= pages;j++)
                if(j == pages)
                {
                    alloc_pages(i, pages);
                    return i;
                }
                else if(check_page(i + j))
                    break;
        panic("Out of memory!");
        return 0;
    }
    Pages are managed starting at 1(ie first page is identified with 1, not 0).

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    It seems to me that you could improve it to:
    Code:
    unsigned int get_pages(int pages)
    {
        int i,j = 0;
        for(i = reserved_low_pages + 1;i + pages <= total_pages;i += (j + 1))
        {
            for(j = 0;j < pages && check_page(i + j);j++)
                /* do nothing here */;
            if(j == pages)
            {
                alloc_pages(i, pages);
                return i;
            }
        }
        panic("Out of memory!");
        return 0;
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    That was my original design, but the ambiguity of whether or not it would execute the if w/o me wanting it to caused me to redesign it to explicitly with the if. How do I specify I want it to do nothing? When there are no braces, doesn't it assume the next thing it finds is the instruction to loop?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    Personally, I would put the comment within braces as I think that that is a less error prone approach, but I noticed that your style appears to prefer leaving out braces when they are unnecessary, which is why I put the comment before an empty statement. There is no ambiguity since the body of the for loop is the empty statement.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Would putting a ";" after the for expression be clearer? It doesn't seem to cause a warning or error in a test I made. Is this a GCC extension?
    Code:
    int main()
    {
        int i;
        for(i = 0;i < 5;i++);
        if(i == 4)
            break;
    }
    The break is there to test if it is inside the for, it isn't because I get an error saying the break is outside of any loop.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    Quote Originally Posted by User Name:
    Would putting a ";" after the for expression be clearer?
    Maybe, maybe not. This is why I prefer braces here: a mere semi-colon is easier to miss and easier to mistake for a typographical error. With braces, the reader will find it more likely that the empty body is intentional, and this is then confirmed with a comment.

    Quote Originally Posted by User Name:
    It doesn't seem to cause a warning or error in a test I made. Is this a GCC extension?
    No, this is standard C.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Other than the ambiguous for, can you see any bug in my algo?

    And btw, thanks for your help on the for thing.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,422
    Well assuming check_page() and alloc_pages() actually perform some non-trivial action, you're wasting your time on pointless micro-optimisation of the loops in this code.

    Unless of course you're ACTUALLY changing the number of times those functions get called (and I didn't see that you did).

    Get the damn thing to work "at all" first before trying to second-guess where the performance problems are.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Alloc and check are very trivial. Alloc checks if a page is used, if not it marks it used, if it is, it panics. Check just checks if a bit in a bitmap is set and returns 1 or 0 indicating one way or another.

    I've renamed stuff. I didn't like that the names resembled early Linux as much as they did.
    pmem.c:
    Code:
    #include <kernel/mem/pmem.h>
    #include <kernel/panic.h>
    
    unsigned int high_mem, low_mem, reserved_low_pages;
    unsigned int pbmp[MAX_PAGES/32];
    
    #define pbmpset(page) pbmp[(unsigned int)page / 32] |= (1 << page % 32)
    #define pbmpclear(page) pbmp[(unsigned int)page / 32] &= ~(1 << page % 32)
    #define pbmpcheck(page) pbmp[(unsigned int)page / 32] & ~(1 << page % 32)
    
    int palloc(unsigned int page)
    {
    	if(pcheck(page) != MEM_RESERVED)
    	{
    		pbmpset(page);
    		return PALLOC_SUCCESS;
    	}
    	else
    	{
    		panic("Allocating used page!");
    		return PALLOC_FAIL;
    	}
    }
    
    int palloc_m(unsigned int start, int len)
    {
    	unsigned int i;
    	if(pcheck_m(start, len) == MEM_RESERVED)
    		return PALLOC_FAIL;
    	for(i = start;i < start + len;i++)
    		palloc(i);
    	return PALLOC_SUCCESS;
    }
    
    int pfree(unsigned int page)
    {
    	if(pcheck(page) == MEM_RESERVED)
    		pbmpclear(page);
    	else
    	{
    		panic("Freeing free page!");
    		return PFREE_FAIL;
    	}
    	return PFREE_SUCCESS;
    }
    
    int pfree_m(unsigned int start, int len)
    {
    	int i;
    	for(i = start;i < start + len;i++)
    		if(pfree(i))
    			return PFREE_FAIL;
    	return PFREE_SUCCESS;
    }
    
    
    int pcheck(unsigned int page)
    {
    	if(pbmpcheck(page))
    		return MEM_RESERVED;
    	else
    		return MEM_FREE;
    }
    
    int pcheck_m(unsigned int start, int len)
    {
    	unsigned int i;
    	for(i = start;i < start + len;i++)
    		if(pcheck(i) == MEM_RESERVED)
    			return MEM_RESERVED;
    	return MEM_FREE;
    }
    
    unsigned int pget()
    {
    	unsigned int i;
    	for(i = reserved_low_pages + 1;i <= high_page;i++)
    		if(pcheck(i) == MEM_FREE)
    		{
    			palloc(i);
    			return i;
    		}
    	panic("Out of memory!");
    	return PGET_FAIL;
    }
    
    unsigned int pget_m(int pages)
    {
    	unsigned int i, j = 0;
    	for(i = reserved_low_pages + 1;i + pages <= high_page;i += (j + 1))
    		for(j = 0;j <= pages;j++);
    		if(j == pages)
    		{
    			if(palloc_m(i, pages) == 0)
    				return i;
    			else
    				return PGET_FAIL;
    		}
    	panic("Out of memory!");
    	return 0;
    }

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    In the interest of future-proofing your code, you may want to write:
    Code:
    #define pbmpset(page) (pbmp[(unsigned int)(page) / 32] |= (1 << (page) % 32))
    #define pbmpclear(page) (pbmp[(unsigned int)(page) / 32] &= ~(1 << (page) % 32))
    #define pbmpcheck(page) (pbmp[(unsigned int)(page) / 32] & ~(1 << (page) % 32))
    I would also follow the convention of fully capitalised macro names, but of course that is your call.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    I would if it was for external use, but since typing caps is twice the work, I'm gonna take the easy way out.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BN_CLICKED, change button style
    By bennyandthejets in forum Windows Programming
    Replies: 13
    Last Post: 07-05-2010, 11:42 PM
  2. Please check this loop
    By Daesom in forum C++ Programming
    Replies: 13
    Last Post: 11-02-2006, 12:52 AM
  3. Check application visibility
    By 3saul in forum Linux Programming
    Replies: 2
    Last Post: 02-13-2006, 04:13 PM
  4. A way to check for Win98 or WinXP
    By Shadow in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 10-31-2002, 10:06 AM
  5. how to check for end of line in a text file
    By anooj123 in forum C++ Programming
    Replies: 6
    Last Post: 10-24-2002, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21