#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <stdarg.h>
#include <stdbool.h>
#include <assert.h>
#include <sys/param.h>
#define PHYSMAP_SIZE 8
#define KASSERT(exp,msg) do { \
if (!(exp)) { \
printf("KASSERT: "); \
printf msg ; \
printf(". "); \
return; \
} \
} while (0)
typedef uint64_t vm_paddr_t;
vm_paddr_t phys_avail[PHYSMAP_SIZE + 2];
/* must be 2 less so 0 0 can signal end of chunks */
#define PHYS_AVAIL_ARRAY_END PHYSMAP_SIZE
static int phys_avail_free_count(void);
static void phys_avail_insert_at(int index, vm_paddr_t val);
static void phys_avail_delete_at(int index);
void phys_avail_reserve(vm_paddr_t start, vm_paddr_t end);
void printarray() {
printf("Array [");
for (int i=0; i<PHYS_AVAIL_ARRAY_END+1; i+=1) {
printf("%lu, ", phys_avail[i]);
}
printf("%lu]\n",phys_avail[PHYS_AVAIL_ARRAY_END+1]);
}
void printsegments() {
printf("Segments ");
for (int i=0; phys_avail[i+1] != 0; i+=2) {
vm_paddr_t start = phys_avail[i];
vm_paddr_t end = phys_avail[i+1] - 1;
vm_paddr_t size = phys_avail[i+1] - phys_avail[i];
printf("%d: %lu-%lu (%lu), ", i/2, start, end, size);
}
printf("\n");
}
void initarray() {
phys_avail[0] = 0; // seg 0 start
phys_avail[1] = 100; // seg 0 end
phys_avail[2] = 200; // seg 1 start
phys_avail[3] = 300; // seg 1 end
phys_avail[4] = 400; // seg 2 start
phys_avail[5] = 500; // seg 2 end
phys_avail[6] = 0;
phys_avail[7] = 0;
phys_avail[8] = 0;
phys_avail[9] = 0;
}
void test(const char *test, vm_paddr_t hole_start, vm_paddr_t hole_end, vm_paddr_t expect[PHYS_AVAIL_ARRAY_END]) {
printf("Test: %s. (%lu-%lu)", test, hole_start, hole_end);
phys_avail_reserve(hole_start, hole_end);
if (memcmp(phys_avail, expect, sizeof(vm_paddr_t)*PHYS_AVAIL_ARRAY_END) != 0) {
printf(" - MISMATCH. ");
printarray();
exit(EXIT_FAILURE);
}
printf(" - OK. ");
printsegments();
initarray();
}
void test_assert(const char *test, vm_paddr_t hole_start, vm_paddr_t hole_end) {
printf("Test KASSERT: %s. (%lu-%lu). ", test, hole_start, hole_end);
phys_avail_reserve(hole_start, hole_end);
printarray();
initarray();
}
int main() {
printf("\nInitialized array\n");
initarray();
printarray();
printsegments();
printf("\n");
test("Exact match hole", 100, 200, (vm_paddr_t []) {0,100,200,300,400,500,0,0,0,0});
test("Exact match segment first", 0, 100, (vm_paddr_t []) {200,300,400,500,0,0,0,0,0,0});
test("Exact match segment middle", 200, 300, (vm_paddr_t []) {0,100,400,500,0,0,0,0,0,0});
test("Exact match segment last", 400, 500, (vm_paddr_t []) {0,100,200,300,0,0,0,0,0,0});
test("Inside hole", 120, 130, (vm_paddr_t []) {0,100,200,300,400,500,0,0,0,0});
test("Inside segment", 220, 230, (vm_paddr_t []) {0,100,200,220,230,300,400,500,0,0});
test("Start in hole, end in segment", 150, 250, (vm_paddr_t []) {0,100,250,300,400,500,0,0,0,0});
test("Start in segment, end in hole", 250, 350, (vm_paddr_t []) {0,100,200,250,400,500,0,0,0,0});
test("Start in hole, skip segment, end in segment", 150, 450, (vm_paddr_t []) {0,100,450,500,0,0,0,0,0,0});
test("Start in segment, skip segment, end in hole", 50, 350, (vm_paddr_t []) {0,50,400,500,0,0,0,0,0,0});
test("Start in hole, skip segment, end in hole", 150, 350, (vm_paddr_t []) {0,100,400,500,0,0,0,0,0,0});
test("Start in segment, skip segment, end in segment", 50, 450, (vm_paddr_t []) {0,50,450,500,0,0,0,0,0,0});
test("Exact match segment+hole", 0, 200, (vm_paddr_t []) {200,300,400,500,0,0,0,0,0,0});
test("Exact match hole+segment", 100, 300, (vm_paddr_t []) {0,100,400,500,0,0,0,0,0,0});
test("Start in segment, end on segment end", 50, 100, (vm_paddr_t []) {0,50,200,300,400,500,0,0,0,0});
test("Start on segment start, end in same segment", 0, 50, (vm_paddr_t []) {50,100,200,300,400,500,0,0,0,0});
test("Almost exact match hole", 101, 199, (vm_paddr_t []) {0,100,200,300,400,500,0,0,0,0});
test("Almost exact match segment", 99, 201, (vm_paddr_t []) {0,99,201,300,400,500,0,0,0,0});
test("Hole starting in last segment, ending after", 450, 600, (vm_paddr_t []) {0,100,200,300,400,450,0,0,0,0});
test("Hole after last segment", 600, 700, (vm_paddr_t []) {0,100,200,300,400,500,0,0,0,0});
phys_avail[6] = 600;
phys_avail[7] = 700;
test("Hole after last segment full array", 800, 900, (vm_paddr_t []) {0,100,200,300,400,500,600,700,0,0});
phys_avail[0] = 50;
test("Hole before first segment", 0, 40, (vm_paddr_t []) {50,100,200,300,400,500,0,0,0,0});
phys_avail[0] = 50;
test("Hole start before first segment, end in segment", 0, 80, (vm_paddr_t []) {80,100,200,300,400,500,0,0,0,0});
/* Trigger KASSERT */
phys_avail[6] = 600;
phys_avail[7] = 700;
test_assert("No more free slots", 220, 230);
test_assert("Invalid range", 100, 100);
test_assert("Invalid range", 100, 50);
/* Test free count */
initarray();
assert(phys_avail_free_count() == 2);
phys_avail[6] = 600;
phys_avail[7] = 700;
assert(phys_avail_free_count() == 0);
memset(phys_avail, 0, sizeof(vm_paddr_t)*PHYS_AVAIL_ARRAY_END);
assert(phys_avail_free_count() == 8);
return 0;
}
/* Paste functions from kern/physmem.c here: */
static int
phys_avail_free_count(void)
{
int i;
for (i = PHYS_AVAIL_ARRAY_END; i > 0 && phys_avail[i-1] == 0 && phys_avail[i] == 0; i -= 2);
return (PHYS_AVAIL_ARRAY_END - i);
}
static void
phys_avail_insert_at(int index, vm_paddr_t val)
{
int i;
KASSERT(phys_avail_free_count() > 0,
("phys_avail_insert_at: phys_avail has no more free slots"));
KASSERT(index >= 0 && index <= PHYS_AVAIL_ARRAY_END,
("phys_avail_insert_at: index %d is out of range", index));
for (i = PHYS_AVAIL_ARRAY_END; i >= index; i--) {
phys_avail[i + 1] = phys_avail[i];
}
phys_avail[i + 1] = val;
}
static void
phys_avail_delete_at(int index)
{
int i;
KASSERT(index >= 0 && index <= PHYS_AVAIL_ARRAY_END,
("phys_avail_delete_at: index %d is out of range", index));
i = index;
while (i <= PHYS_AVAIL_ARRAY_END) {
phys_avail[i] = phys_avail[i + 1];
i++;
}
}
void
phys_avail_reserve(vm_paddr_t start, vm_paddr_t end)
{
int deleted, i;
KASSERT(start < end, ("phys_avail_reserve: invalid range start = "
"0x%016jx, end = 0x%016jx", (uintmax_t)start, (uintmax_t)end));
/* Check if new hole is before first segment. */
if (end <= phys_avail[0])
return;
i = 0;
/* Check if between segments (inside existing hole) */
while (phys_avail[i + 2] != 0 && phys_avail[i + 3] != 0) {
if (start >= phys_avail[i + 1] && end <= phys_avail[i + 2])
return;
i += 2;
}
/* Check if after last segment end (i+1). */
if (start >= phys_avail[i + 1])
return;
i=0;
/* Check if inside any segment */
while (phys_avail[i + 1] != 0) {
if (start > phys_avail[i] && end < phys_avail[i + 1]) {
phys_avail_insert_at(i + 1, end);
phys_avail_insert_at(i + 1, start);
return;
}
i += 2;
}
/* Other cases */
i=0;
while (phys_avail[i] < start && i <= PHYS_AVAIL_ARRAY_END) {
i++;
}
if (phys_avail[i + 1] == 0) {
/* The new hole starts in the last segment and ends after. */
phys_avail[i] = start;
return;
}
/* At the index located on or after the new hole start. */
if (i % 2 == 0) {
/*
* Even index mean beginning of a segment. If hole ends in
* segment, shrink the segment. If exact match, delete the
* segment. Other cases are handled below.
*/
if (start == phys_avail[i]) {
if (end < phys_avail[i + 1]) {
phys_avail[i] = end;
return;
} else if (end == phys_avail[i + 1]) {
phys_avail_delete_at(i);
phys_avail_delete_at(i);
return;
}
}
} else {
/*
* Odd index mean the hole starts inside a memory segment.
* Shrink segment to hole start.
*/
phys_avail[i] = start;
i++;
}
deleted = 0;
while (phys_avail[i] <= end && phys_avail[i + 1] != 0) {
phys_avail_delete_at(i);
deleted++;
}
/* At the index located after the new hole end. */
if (i % 2 == 0 && deleted % 2 == 1) {
/*
* If index is even and odd number of entries have been deleted,
* we are at the end of a segment. Insert hole end before this
* segment end.
*/
phys_avail_insert_at(i, end);
} else if (i % 2 == 1) {
/*
* Odd index mean our hole ends in the previous segment,
* move segment start to new hole end.
*/
phys_avail[i-1] = start;
}
}
