Multitasking clone page directory triple fault

[JSmith2]

Hello, I wanted to upgrade the multitasking in my OS. I, in my early stages of OS development, used JamesM's great tutorials as a base for my OS. Now that I have come back to multitasking, I wanted to fix and make the multitasking somewhat decent in my OS. But before I could start, I had to do some preliminary testing, by forking a test process. While executing the fork, I have to clone the page directory. It executes that and my OS triple faults. I traced the whole problem down in my debugger to the kheap’s index arrays getting corrupted.

Here is how the execution goes...

Code: Select all

s32int fork(u32int priority, u32int burst_time, char *task_Name)
{
  asm volatile("cli");

  // Take a pointer to this process' task struct for later reference.
  task_t *parent_task;
  parent_task = (task_t*)current_task;
  
  u32int id = next_pid++;

  task_t *task = (task_t*)kmalloc(sizeof(task_t));

  task->id = id;
  task->esp = task->ebp = 0;
  task->eip = 0;
  task->thread = 0;
  task->thread_flags = 0;
  strcpy(task->name, task_Name);

//////////////////////////////////////////////////////////////////////////////////////////
  ///////////////EVERTHING IS FINE UNTIL HERE///////////////
//////////////////////////////////////////////////////////////////////////////////////////

  // Clone the address space.
  page_directory_t *directory = clone_directory(current_directory);
  task->page_directory = directory;

  task->priority = priority;
  task->time_to_run = 0;
  task->time_running = 0;
  task->ready_to_run = TRUE;

  task->burst_time = burst_time;
  task->averaged_priority = priority + burst_time;

  nTasks++;

  task->next = 0;

  // Add it to the end of the ready queue.
  preempt_task(task);

  u32int eip = read_eip();

  // We could be the parent or the child here - check.
  if(current_task == parent_task) //we are the parent
  {
    // We are the parent, so set up the esp/ebp/eip for our child.
    u32int esp; asm volatile("mov %%esp, %0" : "=r"(esp));
    u32int ebp; asm volatile("mov %%ebp, %0" : "=r"(ebp));
    task->esp = esp;
    task->ebp = ebp;
    task->eip = eip;
    // All finished: Reenable interrupts.
    asm volatile("sti");

    // And by convention return the PID of the child.
    return task->id;
  }else{ //we are the child
    
    // We are the child - by convention return 0.
    return 0;
  }
	
  asm volatile("sti");

  return id;
}

The clone directory contains a for loop and calls clone_table over and over again. If someone wants the clone_directory code, just write so and I'll give it.

Here is the clone table...

Code: Select all

static page_table_t *clone_table(page_table_t *src, u32int *physAddr)
{
  // Make a new page table, which is page aligned.
  page_table_t *table = (page_table_t*)kmalloc_ap(sizeof(page_table_t), physAddr);
  // Ensure that the new table is blank.
  memset((u8int*)table, 0, sizeof(page_directory_t));

  // For every entry in the table...
  int i;
  for(i = 0; i < 1024; i++)
  {
    // If the source entry has a frame associated with it...
    if (!src->pages[i].frame)
      continue;
      
    // Get a new frame.
    alloc_frame(&table->pages[i], 0, 0);
    // Clone the flags from source to destination.
    if(src->pages[i].present) table->pages[i].present = 1;
    if(src->pages[i].rw)      table->pages[i].rw = 1;
    if(src->pages[i].user)    table->pages[i].user = 1;
    if(src->pages[i].accessed)table->pages[i].accessed = 1;
    if(src->pages[i].dirty)   table->pages[i].dirty = 1;
    // Physically copy the data across. This function is in process.asm
    copy_page_physical(src->pages[i].frame*0x1000, table->pages[i].frame*0x1000);
  }
  return table;
}

Now, the problem arises in the first two lines. The first time this function is called from within the clone_directory loop, everything is fine. The second loop is where things get messy. In the first line, the kmalloc_ap, the allocator sees that another kheap array has to be created, so it creates the next (in this case 8th) array with all of its magic numbers and other structures successfully. Now, the structure is located (in my case) at 0x40ab600b. The next line, the memset, is supposed to clear the newly kmalloc'd table of any junk data, and it clears it with a size of 0x2000 bytes. The location of the table is assigned by the allocator at 0x40ab5000. Now those memory locations overlap, and the memset wipes the 8th kheap index array. Then when the third loop comes, the allocator looks for the 8th index array, finds a bunch of zeros and triple faults.

Here is the code for where it triple faults, I added an ASSERT that checks the magic. With that my OS does not triple fault, but just asserts.
As the while loop looks for an open index that will be able to fit the data, it gets the the 8th. Since its magic is wiped, the error occurs.

Code: Select all

static s32int find_smallest_hole(u32int size, u8int page_align, heap_t *heap)
{
  // Find the smallest hole that will fit.
  u32int iterator = 0;
  while(iterator < heap->index.size)
  {
    header_t *header = (header_t *)lookup_ordered_array(iterator, &heap->index);

    //check if the magic number is valid
    ASSERT(header->magic == HEAP_MAGIC);

    // If the user has requested the memory be page-aligned
    if(!page_align)
    {
      // Page-align the starting point of this header.
      u32int location = (u32int)header;
      s32int offset = 0;
      if((location+sizeof(header_t)) & 0xFFFFF000 != 0)
        offset = 0x1000 /* page size */  - (location + sizeof(header_t)) % 0x1000;
      s32int hole_size = (s32int)header->size - offset;

      // Can we fit now?
      if(hole_size >= (s32int)size)
        break;
    }else if(header->size >= size)
      break;

    iterator++;
  }
  
  // Why did the loop exit?
  if(iterator == heap->index.size)
    return -1; // We got to the end and didn't find anything.
  else
    return iterator;
}

here is a section of my code that does the create new index array... (it is at the bottom of the function, but I decided to give you all of it)

Code: Select all

void *alloc(u32int size, u8int page_align, heap_t *heap)
{
  // Make sure we take the size of header/footer into account.
  u32int new_size = size + sizeof(header_t) + sizeof(footer_t);
  // Find the smallest hole that will fit.
  s32int iterator = find_smallest_hole(new_size, page_align, heap);

  if(iterator == -1) // If we didn't find a suitable hole
  {
    // Save some previous data.
    u32int old_length = heap->end_address - heap->start_address;
    u32int old_end_address = heap->end_address;

    // We need to allocate some more space.
    expand(old_length + new_size, heap);
    //~ expand(0x4000000, heap);
    u32int new_length = heap->end_address - heap->start_address;

    // Find the endmost header. (Not endmost in size, but in location).
    iterator = 0;
    // Vars to hold the index of, and value of, the endmost header found so far.
    u32int idx = -1; u32int value = 0x0;
    while(iterator < heap->index.size)
    {
      u32int tmp = (u32int)lookup_ordered_array(iterator, &heap->index);
      if (tmp > value)
      {
        value = tmp;
        idx = iterator;
      }
      iterator++;
    }

    // If we didn't find ANY headers, we need to add one.
    if(idx == -1)
    {
      header_t *header = (header_t *)old_end_address;
      header->magic = HEAP_MAGIC;
      header->size = new_length - old_length;
      header->is_hole = 1;
      footer_t *footer = (footer_t *) (old_end_address + header->size - sizeof(footer_t));
      footer->magic = HEAP_MAGIC;
      footer->header = header;
      insert_ordered_array((void*)header, &heap->index);
    }else{
      // The last header needs adjusting.
      header_t *header = lookup_ordered_array(idx, &heap->index);
      header->size += new_length - old_length;
      // Rewrite the footer.
      footer_t *footer = (footer_t *)((u32int)header + header->size - sizeof(footer_t));
      footer->header = header;
      footer->magic = HEAP_MAGIC;
    }
    // We now have enough space. Recurse, and call the function again.
    return alloc(size, page_align, heap);
  }

  header_t *orig_hole_header = (header_t *)lookup_ordered_array(iterator, &heap->index);
  u32int orig_hole_pos = (u32int)orig_hole_header;
  u32int orig_hole_size = orig_hole_header->size;
  // Here we work out if we should split the hole we found into two parts.
  // Is the original hole size - requested hole size less than the overhead for adding a new hole?
  if(orig_hole_size - new_size < sizeof(header_t) + sizeof(footer_t))
  {
    // Then just increase the requested size to the size of the hole we found.
    size += orig_hole_size - new_size;
    new_size = orig_hole_size;
  }

  // If we need to page-align the data, do it now and make a new hole in front of our block.
  if(page_align && orig_hole_pos & 0xFFFFF000)
  {
    u32int new_location   = orig_hole_pos + 0x1000 /* page size */ - (orig_hole_pos & 0xFFF) - sizeof(header_t);
    header_t *hole_header = (header_t *)orig_hole_pos;
    hole_header->size     = 0x1000 /* page size */ - (orig_hole_pos & 0xFFF) - sizeof(header_t);
    hole_header->magic = HEAP_MAGIC;
    hole_header->is_hole = 1;
    footer_t *hole_footer = (footer_t *) ( (u32int)new_location - sizeof(footer_t) );
    hole_footer->magic = HEAP_MAGIC;
    hole_footer->header = hole_header;
    orig_hole_pos = new_location;
    orig_hole_size = orig_hole_size - hole_header->size;
  }else{
    // Else we don't need this hole any more, delete it from the index.
    remove_ordered_array(iterator, &heap->index);
  }

  // Overwrite the original header...
  header_t *block_header = (header_t *)orig_hole_pos;
  block_header->magic = HEAP_MAGIC;
  block_header->is_hole = 0;
  block_header->size = new_size;
  // ...And the footer
  footer_t *block_footer = (footer_t *) (orig_hole_pos + sizeof(header_t) + size);
  block_footer->magic = HEAP_MAGIC;
  block_footer->header = block_header;

  // We may need to write a new hole after the allocated block.
  // We do this only if the new hole would have positive size...
  if(orig_hole_size - new_size > 0)
  {
//////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////
    //Here is where the new index array is created
//////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////
    header_t *hole_header = (header_t *) (orig_hole_pos + sizeof(header_t) + size + sizeof(footer_t));
    hole_header->magic    = HEAP_MAGIC;
    hole_header->is_hole  = 1;
    hole_header->size     = orig_hole_size - new_size;
    footer_t *hole_footer = (footer_t *) ( (u32int)hole_header + orig_hole_size - new_size - sizeof(footer_t) );
    if((u32int)hole_footer < heap->end_address)
    {
      hole_footer->magic = HEAP_MAGIC;
      hole_footer->header = hole_header;
    }
    // Put the new hole in the index;
    insert_ordered_array((void*)hole_header, &heap->index);
  }
  
  // ...And we're done!
  return (void *)((u32int)block_header + sizeof(header_t));
}

I have looked on other threads that had expressed similar problems to mine, but have found no solutions.
Thank you.

[dozniak]

It looks like cloning function from the old JamesM tutorial, it is known to have some issues.

[JSmith2]

Yes, yet after a few days of investigating myself, I decided to post this problem on the Forum.

[dozniak]

Yes, yet after a few days of investigating myself, I decided to post this problem on the Forum.

But you didn't search the forum before posting.

[JSmith2]

Well, by investigating it included looking on the forum. I did notice though, that a lot of the problems regarding the clone directory is while the switch page directory is being executed, after the clone directory function exits, my issue happens inside of the clone directory function.

[JSmith2]

So, I found the problem. I explained it in my other post, http://forum.osdev.org/viewtopic.php?f= ... 0b5c6d8325
The post's title is: Found a bug in JamesM multitasking code, in clone table