OSDev.org

Code: Select all

int init_memory_map(multiboot_info_t *mbd, uint32_t page_size) {

	/* We only actually use the mmap_t here, and so we're going
	 * to go ahead and define it within the function
	 */
	struct mmap_t {
		uint32_t size;
		uint64_t base;
		uint64_t len;
		uint32_t type;
	} __attribute((packed));

	/* Make sure that page size is a power of 2 */
	if ((page_size == 0) || ((page_size & (page_size - 1)) != 0)) {
		printf("Page size must be a power of 2!\n");
		return 0;
	}

	unsigned char check_flag = (1 << 0) & mbd->flags;
	
	// Check flags to make sure memory mapping is sane
	if (!check_flag) {
		printf("Flag is not set at bit 0!\n");
		return 0;
	}

	check_flag = (1 << 6) & mbd->flags;

	if (!check_flag) {
		printf("Flag is not set at bit 6!\n");
		return 0;
	}

	// Get the address and length to set up
	struct mmap_t *mmap_addr = (struct mmap_t *) mbd->mmap_addr;
	uint32_t arr_size = (uint64_t) mbd->mmap_length / sizeof(struct mmap_t);

	/* Make a copy. Since it isn't very big for an x86 system, we'll have
	 * it the stack. That way it'll get destroyed when we finish initializing
	 * the physical memory and we also don't need to worry about clobbering it
	 * when we do our bitmap
	 */
	struct mmap_t entries[arr_size];

	memcpy(entries, mmap_addr, mbd->mmap_length);

	/* The exponent of the page_size as a power of 2 */
	uint32_t page_power = 0;
	uint32_t page_size_copy = page_size;

	for (page_power; page_size_copy; page_power++) {
		/* This ensures that page_power does not end
		 * up one greater than it should be
		 */
		if ((page_size_copy >> 1) == 0) {
			break;
		}
		page_size_copy >>= 1;
	}

	/* Get the base + length to determine total "usable"
	 * ram
	 */
	uint64_t last_address = entries[arr_size-1].base +
	       			entries[arr_size-1].len;

	// Get the number of pages
	uint32_t blocks = last_address / (1 << page_power); 

	// Get the number of bytes for the bitmap, each bit is 1 page
	bitmap_size = blocks / 8;
	uint64_t end = 0;
	uint64_t top_check = 0;
	uint64_t bottom_check = 0;
	uint64_t sb_addr = (uint64_t) &stack_bottom;
	uint64_t st_addr = (uint64_t) &stack_top;
	uint64_t ke_addr = (uint64_t) &kernel_end;


	/* Find available memory after the end of the kernel
	 *
	 * After that, align to the next nearest page boundary (unless the
	 * base is already aligned to a page boundary), and then use that
	 * to store the bitmap.
	 */	
	for (uint32_t i = 0; i < arr_size; ++i) {
		end = entries[i].base + entries[i].len;

		/* In order to check the space, we are going to check
		 * to see if end-bitmap_size is aligned on a page boundary.
		 * If it is not, then we are going to round down
		 * to the nearest page boundary. If it is, we are going
		 * to use it as is. That way, we can ensure that we
		 * are actually using pages to allocate memory for the
		 * bitmap
		 */
		top_check = (((end-bitmap_size) % page_size) != 0) ?
			((end-bitmap_size) & ~(page_size-1)) :
			(end-bitmap_size);

		/* Additionally, we are going to check to see if the aligned base
		 * can fit into memory. This time we are rounding up
		 */
		bottom_check = ((entries[i].base % page_size) != 0) ?
			((entries[i].base & ~(page_size-1)) + page_size) :
			(entries[i].base);
		bottom_check += bitmap_size;

		if (entries[i].type != MULTIBOOT_MEMORY_AVAILABLE) {
			continue;
		}

		/* We found some space between the stack and the kernel */
		if (st_addr < (1 << 20) && 
			top_check > st_addr && 
			end < (1 << 20)) {

		       phys_mem_bitmap = top_check;
		       break;
		}

		/* We found memory below the stack */
		else if (sb_addr < (1 << 20) && 
			bottom_check < sb_addr) {
			phys_mem_bitmap = bottom_check - bitmap_size;
			break;
		}

		/* The stack is above the kernel, but we did manage to find
		 * some memory that is below the kernel and the stack
		 *
		 * In this case, I don't think that it actually matters if
		 * we use the top range or bottom range for the bitmap
		 */
		else if (sb_addr > (1 << 20) &&
				bottom_check < sb_addr &&
				bottom_check < (1 << 20)) {
			phys_mem_bitmap = bottom_check - bitmap_size;
			break;
		}

		/* The bottom of the stack is at a higher address than the
		 * kernel, and we found some memory between the kernel and the
		 * stack bottom
		 */
		if (sb_addr > (1 << 20) &&
			bottom_check - bitmap_size > ke_addr &&
			bottom_check < sb_addr) {
			phys_mem_bitmap = bottom_check - bitmap_size;
			break;
		}
		
		/* The bottom of the stack is at a higher address than the kernel
		 * and we found some memory after the top of the stack.
		 */
		else if (sb_addr > (1 << 20) && 
			st_addr < top_check) {
			phys_mem_bitmap = top_check;
			break;
		}

		/* We went through all of the memory, but didn't find
		 * anything we liked. Time to give the kernel a panic.
		 */
		if (i == (arr_size - 1)) {
			printf("Failed to find memory for the bitmap!\n");
			return 0;
		}
	}

	// Set all bits to 1
	memset((uint8_t *) phys_mem_bitmap, 0xFF, bitmap_size);

 	uint32_t ndx = 0;
	uint64_t base = 0;
	uint64_t limit = 0;
	uint64_t address = 0;

	/* TODO: Find a faster way to do this */	
	for (uint32_t i = 0; i < blocks; ++i) {
		/* Get the address and determine if it
		 * is inside of a mmap_t structure
		 */
		address = i*(1 << page_power);
		base = entries[ndx].base;
		limit = entries[ndx].len;

		/* This means that there is a gap between
		 * two different mmap_t entries.
		 */ 
		if (address < base) {
			// The bit has already been set
			printf_serial("Bit has already been set... continuing\n");
			continue;
		}

		/* This means that the address is within the physical memory bitmap */
		if (address >= phys_mem_bitmap && 
			address <= phys_mem_bitmap + bitmap_size) {
			printf_serial("The bit is within the bitmap... continuing\n");
			continue;
		}

		// Clear the bit if the memory is available
		if (entries[ndx].type == MULTIBOOT_MEMORY_AVAILABLE) {
			((uint32_t *) phys_mem_bitmap)[i/8] &= ~(1 << (i%8));
		}

		// Ignore if the memory is not specifically available

		/* Determine if the next address is within the 
		 * mmap struct
		 */
		if ((address+(1 << page_power)) > (base+limit)) {
			++ndx;
		}
	}
	
	return 1;
}

Code: Select all

struct memblock {
  phys_addr_t start;
  size_t len;
};

struct memblock memavail[32];
struct memblock memreserved[64];
size_t navail;
size_t nreserved;

Code: Select all

static void add_range_to_memblock(struct memblock *arr, size_t *n, size_t limit, phys_addr_t start, size_t len) {
  size_t i;
  for (i = 0; i < *n; i++)
    if (arr[i].start > start)
      break;

  /* can we just add this to the preceding block? */
  if (i && arr[i-1].start + arr[i-1].len >= start) {
    size_t overlap = arr[i-1].start + arr[i-1].len - start;
    arr[i-1].len += len - overlap;
/* is it possible to unite this with the next block now? */
    if (i < *n && arr[i-1].start + arr[i-1].len == arr[i].start) {
      arr[i-1].len += arr[i].len;
      if (i + 1 < *n)
        memmove(arr + i, arr + i + 1, (*n - i - 1) * sizeof (struct memblock));
      --*n;
    }
  }
  /* can we just add this to the following block? */
  else if (i < *n && start + len >= arr[i].start) {
    size_t overlap = start + len - arr[i].start;
    arr[i].start = start;
    arr[i].len += len - overlap;
  }
  /* need to add a new block */
  else if (*n < limit) {
    if (i < *n)
      memmove(arr + i + 1, arr + i, (*n - i - 1) * sizeof (struct memblock));
    arr[i].start = start;
    arr[i].len = len;
    ++*n;
  }
  else
    die("Out of memory adding block at %x", start);
}

static void remove_range_from_memblock(struct memblock *arr, size_t *n, size_t limit, phys_addr_t start, size_t len)
{
  size_t i;
  for (i = 0; i < *n; i++)
    if (arr[i].start >= start)
      break;
  /* Both ends match? Remove entire block */
  if (i < *n && arr[i].start== start && arr[i].len == len) {
    if (i + 1 < *n)
      memmove(arr + i, arr + i + 1, (*n - i - 1) * sizeof (struct memblock));
    --*n;
  }
  /* start matches? Adjust start and len */
  else if (i < *n && arr[i].start == start) {
    arr[i].start += len;
    arr[i].len -= len;
  }
  /* end matches? Adjust len */
  else if (i < *n && arr[i].start + arr[i].len == start + len) {
    arr[i].len -= len;
  }
  /* central match? Adjust list for hole in the middle */
  else if (i < *n && start + len < arr[i].start + arr[i].len) {
    if (*n == limit) die("Out of memory adding hole at %X", start);
    if (i + 1 < *n)
      memmove(arr + i + 1, arr + i, (*n - i - 1) * sizeof (struct memblock));
    size_t offset = start - arr[i].start;
    arr[i+1].start = arr[i].start + offset + len;
    arr[i+1].len = arr[i].len - len - offset;
    arr[i].len = offset;
  }
}

Code: Select all

static phys_addr_t *alloc(size_t sz, size_t algn)
{
    size_t avidx, residx = 0;
    for (avidx = 0; avidx < navail; avidx++)
    {
        phys_addr_t start;
        size_t len;
        while (memreserved[residx].start + memreserved[residx].len < memavail[avidx].start && residx < nreserved)
            residx++;
        while (residx < nreserved && memreserved[residx].start < memavail[avidx].start + memavail[avidx].len)
        {
            start = memavail[avidx].start;
            if (memreserved[residx].start + memreserved[residx].len > start)
                start = memreserved[residx].start + memreserved[residx].len;
            len = memavail[avidx].start + memavail[avidx].len - start;
            if (residx < nreserved && memreserved[residx+1].start - start < len)
                len = memreserved[residx+1].start - start;
            if (((start + algn - 1) & -algn) + sz <= start + len)
            {
                start = (start + algn - 1) & -algn;
                add_reserved_range(start, sz);
                dbg_printf("Allocating address %8x\n", start);
                return start;
            }
        }
    }
    return 0;
}