a good testing for a page allocator and malloc/free

[earlz]

I have recently made major repairs to my page allocator and have added malloc, free, and friends

but really I'm not really sure on how to test each componet or well do a full test that is

I really don't want to do what I just did again, I only tested the page allocator a little bit and then found a major bug that I basically had to rewrite the whole thing because of it

edit:
or if someone could maybe look at this code and say whats wrong with it

[edited again with the code]

Code: Select all

unsigned int is_free_bits(unsigned int *data,unsigned int start_bit,unsigned int num,unsigned int len){
   unsigned int i,j=0,endbit,total,counter; //i bet i could've used less stack but anyway
   endbit=num+start_bit; //make it the end bit
   total=0;
   counter=0;
   for(i=start_bit;total<=endbit;i++,total++){
      if(counter/8==len+1){return 2;} //bits go past length
      counter++;
      if(data[j]&(1<<i)!=0){return 4+total;} //the bits are not free-- subtract 4 and you got number of the set bit
      if(i==31 && total<endbit){i=0;start_bit=0;j++;} //bits are free here but need to check next dword
   }
   return 1; //the bits are free
}


unsigned int num_set_bits(unsigned int *data,unsigned int start_bit,unsigned int len){
     unsigned int i,j=0,endbit,total,counter; //i bet i could've used less stack but anyway
   endbit=len*8+start_bit; //make it the end bit
   total=0;
   counter=0;
   for(i=start_bit;total<=endbit;i++,total++){
      if(counter/8==len+1){return 1;} //bits go past length --have to use signed stuff for this
      counter++;
      if(data[j]&(1<<i)==0){return total+4;} //the bits are not free-- subtract 4 and you got number of the set bit
      if(i==31 && total<endbit){i=0;start_bit=0;j++;} //bits are free here but need to check next dword
   }
   return 0; //the bits are free
}

unsigned int* set_bits(unsigned int *data,unsigned int start_bit,unsigned int end_bit,unsigned int len){
   unsigned int i,counter,j,total;
   j=0;
   counter=0;
   total=0;
   for(i=start_bit;total<=end_bit;i++,total++){
      if(counter==len+1){return 0;} //goes past len
      counter++;
      data[j]=data[j]|(1<<i);
      if(i==31 && total<end_bit){i=0;start_bit=0;j++;}
   }
   return data;
}

unsigned int* clear_bits(unsigned int *data,unsigned int start_bit,unsigned int end_bit,unsigned int len){
   unsigned int i,counter,j,total;
   j=0;
   total=0;
   counter=0;
   for(i=start_bit;total<=end_bit;i++,total++){ //i gets roundoff every 32 cycles so we need one that don't
      if(counter==len+1){return 0;} //goes past len
      counter++;
      data[j]=data[j]&(0xFFFFFFFF^(1<<i));
      if(i==31 && total<end_bit){i=0;start_bit=0;j++;}
   }
return data;
}



void *FreeCore(void *page_ptr,unsigned int num_pages);
void *AllocCore(unsigned int num_pages){
   unsigned int i=0,t,j;unsigned int page,super_page;
   unsigned char *tmp;
   unsigned int index,index2,j2;
   /*
   while(superpages[i]==0xFFFFFFFF){
      if(i>=32){return 0;} //error! couldnt find a free superpage
      i++;
   }
   super_page=find_0_bit(superpages[i]);
   super_page=super_page+(i*32);
   i=super_page*1024; //this is the page number where the super page begins*/
   
   if (num_pages>1){ //use a special allocation method
          while(pages[i]==0xFFFFFFFF){
      if(i>=32768){return 0;}
      //k_printf("t3");
      i++;
          }
          index=i;
          t=find_0_bit(pages[i]);
          j=t;
          for(;;){
             j=is_free_bits(&pages[index],t,num_pages,32768*4-index*4);
             if(j==1){
                if(set_bits(&pages[index],t,num_pages+t,32768*4-index*4)==0){return 0;} //means page table is full or there isn't enough room
                    return (index+(t*32))*4096; //this and above means that the bits were free
               }
               if(j==2){return 0;} //goes past length
               if(j>=4){ //some bits weren't free
                    j=j-4; //we added 4 to it for error code
                    index=index+j/32; //advances index if past a dword
                    t=(j%32)+1;
                    t=num_set_bits(&pages[index],t,32768*4-index*4);
                    //if t is 0 then we just continue
                    if(t==1){return 0;} //goes beyond, full
                    t=t-4; //we added 4 on this one too
                    index=index+t/32; //advances index if past a dword
                    t=(t%32)+1;
               
                    
                     //idk who would need 32 pages but anyway
                    //and now reset and will begin the loop again
               }
          }   }else{ //if num_pages==1
     
     
   }
   while(pages[i]==0xFFFFFFFF){
      if(i>=32768){return 0;}
      //k_printf("t3");
      i++;
   }
   
   page=find_0_bit(pages[i]);
   
   pages[i]=pages[i]|(1<<page);
   page=page+(i*32);
   page=page*4096;
   //if (i==0){   k_printf("t3");}
     t=i;
     return page;
}

it hasn't passed the test of getting text onto the screen(i use AllocCore() to allocate 3 pages for a buffer that gets written to the screen[used as a double buffer])

[mystran]

For malloc/free there's good test for it: make it work on top of Unix, LD_PRELOAD (or something) it as a replacement for the normal malloc, and run emacs with it, or firefox, or whole gnome, or whatever.

Then you see if it works, and you see how much worse it is than whatever malloc your system is using.

[dc0d32]

brilliant idea mystran!

[earlz]

I really have hardly any unix/linux experience so how exactly would i replace the malloc/free without going into the apps source

[nick8325]

I really have hardly any unix/linux experience so how exactly would i replace the malloc/free without going into the apps source

AFAIK:

You need to make a shared library with your version of malloc and free (http://www.adp-gmbh.ch/cpp/gcc/create_lib.html says how to do that).

Then run LD_PRELOAD=name_of_shared_library name_of_program. For example, if your library is called /foo/my_malloc.so (I'm not sure if relative paths will work), to run firefox use LD_PRELOAD=/foo/my_malloc.so firefox.

That should mean that any call to malloc or free will be linked to the version in my_malloc.so.

EDIT: I haven't tested this, though.

[earlz]

So anyone got an idea for how to test paging
I trust that the malloc/free that was given to me works good considering he said he tested it that way but my major concern is my paging allocation method; I just did a complete rewrite of it and really have no way to tell that it works well, my main concern is reliability and not speed though

[mystran]

Apart from formally (or semi-formally) verifying that it's correct, I can't think any easy ways. You can try to stress test it (by deliberately trying all kinds of strange things in strange order) and sanity check that it does what is expected.

Here's the trick for reliable testing: you should design your code such that you can easily verify (or at least sanity check) it.

I think Dijkstra used to claim something along the lines of it making little sense to try to prove arbitary programs, because the proof is basicly the program, so you could just as well design the proof directly, especially since this most of the time would be much easier.

Oh well, there's also the legendary "I must warn that while I've proven this code correct, I haven't really debugged it."

[earlz]

geuss I will allocate random pages and then free some and such and then fill them all and if they are not what they should be then give error

[mystran]

Yeah. Something like that.

Hint though: don't use totally random pages. If you use something like a random number generator, seed it with a constant value, so at least you can reproduce things.

[proxy]

I find that the best way to find bugs is to spinkle all sorts of assertions in the code. This really has no negative effect since it only makes a difference in debug builds.

Any statement which you know shoudl be true, make an assert for it.

For example, each and every function in my kernel that takes a pointer as an argument (excluding those which have well defnied behavior for accepting a NULL) has an assert along the lines of:

assert(p != 0);

The point is, if you design by contract, bugs tend to present themselves on there own, which is a nice thing.

proxy

[earlz]

hmmm good idea
actually I haven't even made an assert() yet(never understood what it did)

edit:
how do you debug an OS i have to run in bochs so it doesn't compile debug

[mystran]

Make your assertions have a condition that must be true, and then make them panic the kernel and print on screen the filename and line number or something.

You can use __FILE__ and __LINE__ to make a macro out of that.

[Candy]

Make your assertions have a condition that must be true, and then make them panic the kernel and print on screen the filename and line number or something.

You can use __FILE__ and __LINE__ to make a macro out of that.

Or go all-out with help of the preprocessor:

Code: Select all

#ifdef DEBUG
#define assert(x) \
   if (!x) {\
      printf("ASSERT FAILED: %s evaluated to false in %s, %s:%d\n", #x, __FUNCTION__, __FILE__, __LINE__);\
      // some other code as you like \
   }
#else
#define assert(x) x
#endif

The non-debug assert was defined to x to avoid the "problem" that occasionally happens when you do something like assert(x=2) in some place, then get the code working, turn off asserts and it fails. Also, it prints the function (I think that's a GNU extension, not sure), the code that you asserted to be true (but that wasn't), the file and the line.

The idea is that you assert all sorts of invariants and pre/postconditions. Invariants are things that are always true, eg:

Code: Select all

assert(pi == 3.141592653589793...);

Preconditions are things that should be true when you enter the function (thereby moving the correctness of execution to calling it only with valid parameters, also called programming by contract):

Code: Select all

int dereference(int *p) {
   assert(p != NULL);
   return *p;
}

Postconditions are things that should be true at the end of a function:

Code: Select all

void freeAndNil(void *&p) {
  free(p);
  p = NULL;
  assert(p == NULL);
}

Even though these examples are trivial, for most classes and functions you can find a bunch of these around. Testing them and asserting on them makes finding errors a lot easier, most of the time, by the time you notice something malfunctioning, you'd have gotten a few hundred asserts.

There are some commonly used progarms that have asserts turned on in production releases, which is odd but fun to see. In Linux, I occasionally see an assert for some things fail (mainly with KDE font management).


[edit]
Oh, add to that that the compiler usually optimizes away the asserted statement so that the overhead is null when you have debugged the program.
[/edit]

[earlz]

Thanks so much this is great!

[Solar]

One notion on Candy's post:

The assert() macro you get by including [tt]<assert.h>[/tt] does not execute the assertion when NDEBUG is defined. Which means, Candy's code fragment

Code: Select all

#else
#define assert(x) x

is nice, but non-standard. (Standard would be [tt]#define assert(x) ( (void) 0 )[/tt].) If you do non-standard things, consider naming the function / macro in a non-standard way. While persons used to the standard assert() wouldn't put side-effects in there anyway, it's better to play it safe IMHO.