Skip to content

Instantly share code, notes, and snippets.

@ancientstraits
Last active July 5, 2022 19:22
Show Gist options
  • Save ancientstraits/a2f7fb8d6b05616568f45253dfd837f1 to your computer and use it in GitHub Desktop.
Save ancientstraits/a2f7fb8d6b05616568f45253dfd837f1 to your computer and use it in GitHub Desktop.
stupid github microsoft jerks tryna indoctrinate us into using spaces instead of tabs
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
typedef struct Node {
size_t size;
struct Node* next;
struct Node* prev;
} Node;
#define BUDDY_COUNT 7
static Node* roots[BUDDY_COUNT] = {NULL};
static Node* ends[BUDDY_COUNT] = {NULL};
void insert_node(void* ptr, size_t size) {
size_t counts[BUDDY_COUNT] = {};
size_t current_size = 64;
for (uint8_t i = BUDDY_COUNT; i > 0 && size; --i) {
counts[i - 1] = size / current_size;
size -= size / current_size * current_size;
current_size /= 2;
}
size_t i2 = 1;
for (uint8_t i = 0; i < BUDDY_COUNT; ++i) {
printf("%zu: %zu\n", i2, counts[i]);
i2 *= 2;
}
printf("------\n");
current_size = 64;
for (uint8_t i = BUDDY_COUNT; i > 0; --i) {
size_t count = counts[i - 1];
if (count > 0) {
if (!roots[i - 1]) {
roots[i - 1] = (Node*) ptr;
roots[i - 1]->next = NULL;
roots[i - 1]->prev = NULL;
roots[i - 1]->size = count;
ends[i - 1] = roots[i - 1];
ptr = (void*) ((uintptr_t) ptr + count * current_size * 0x1000);
}
else {
if (ptr > (void*) ends[i - 1]) {
if ((uintptr_t) ends[i - 1] + (ends[i - 1]->size * current_size * 0x1000) == (uintptr_t) ptr) {
ends[i - 1]->size += count;
if (current_size < 64 && ends[i - 1]->size >= 2) {
if (ends[i - 1]->prev) ends[i - 1]->prev->next = ends[i - 1]->next;
Node* old_end = ends[i - 1];
ends[i - 1] = ends[i - 1]->prev;
if (old_end == roots[i - 1]) roots[i - 1] = ends[i - 1];
insert_node(old_end, old_end->size * current_size);
}
}
else {
ends[i - 1]->next = (Node*) ptr;
ends[i - 1]->next->next = NULL;
ends[i - 1]->next->prev = ends[i - 1];
ends[i - 1]->next->size = count;
ends[i - 1] = ends[i - 1]->next;
}
ptr = (void*) ((uintptr_t) ptr + count * current_size * 0x1000);
}
else if (ptr < (void*) roots[i - 1]) {
if ((uintptr_t) ptr + (count * current_size * 0x1000) == (uintptr_t) roots[i - 1]) {
Node* old_root = roots[i - 1];
roots[i - 1] = (Node*) ptr;
*roots[i - 1] = *old_root;
roots[i - 1]->size += count;
if (old_root->next) old_root->next->prev = roots[i - 1];
if (current_size < 64 && roots[i - 1]->size >= 2) {
if (roots[i - 1]->next) roots[i - 1]->next->prev = roots[i - 1]->prev;
Node* old_root_2 = roots[i - 1];
roots[i - 1] = roots[i - 1]->next;
if (old_root_2 == ends[i - 1]) ends[i - 1] = roots[i - 1];
insert_node(old_root_2, old_root_2->size * current_size);
}
}
else {
Node* old_root = roots[i - 1];
roots[i - 1] = (Node*) ptr;
roots[i - 1]->next = old_root;
roots[i - 1]->prev = NULL;
roots[i - 1]->size = count;
old_root->prev = roots[i - 1];
}
ptr = (void*) ((uintptr_t) ptr + count * current_size * 0x1000);
}
else {
Node* node = roots[i - 1];
bool done = false;
while (node->next) {
if ((void*) node > ptr) {
if (node == roots[i - 1]) {
if ((uintptr_t) ptr + (count * current_size * 0x1000) == (uintptr_t) roots[i - 1]) {
Node* old_root = roots[i - 1];
roots[i - 1] = (Node*) ptr;
*roots[i - 1] = *old_root;
roots[i - 1]->size += count;
if (old_root->next) old_root->next->prev = roots[i - 1];
if (current_size < 64 && roots[i - 1]->size >= 2) {
if (roots[i - 1]->next) roots[i - 1]->next->prev = roots[i - 1]->prev;
Node* old_root_2 = roots[i - 1];
roots[i - 1] = roots[i - 1]->next;
if (old_root_2 == ends[i - 1]) ends[i - 1] = roots[i - 1];
insert_node(old_root_2, old_root_2->size * current_size);
}
}
else {
Node* old_root = roots[i - 1];
roots[i - 1] = (Node*) ptr;
roots[i - 1]->next = old_root;
roots[i - 1]->prev = NULL;
roots[i - 1]->size = count;
old_root->prev = roots[i - 1];
}
ptr = (void*) ((uintptr_t) ptr + count * current_size * 0x1000);
}
else {
if ((uintptr_t) ptr + (count * current_size * 0x1000) == (uintptr_t) node) {
Node* new_node = (Node*) ptr;
*new_node = *node;
new_node->size += count;
node->prev->next = new_node;
if (node->next) node->next->prev = new_node;
if (current_size < 64 && new_node->size >= 2) {
if (new_node->prev) new_node->prev->next = new_node->next;
if (new_node->next) new_node->next->prev = new_node->prev;
if (new_node == ends[i - 1]) ends[i - 1] = new_node->prev;
insert_node(new_node, new_node->size * current_size);
}
}
else {
node->prev->next = (Node*) ptr;
Node* new_node = node->prev->next;
new_node->next = node;
new_node->prev = node->prev;
new_node->size = count;
}
ptr = (void*) ((uintptr_t) ptr + count * current_size * 0x1000);
}
done = true;
break;
}
node = node->next;
}
if (!done) {
if ((uintptr_t) node + node->size * current_size * 0x1000 == (uintptr_t) ptr) {
node->size += count;
if (current_size < 64 && node->size >= 2) {
if (node->prev) node->prev->next = node->next;
if (node->next) node->next->prev = node->prev;
if (node == ends[i - 1]) ends[i - 1] = node->prev;
if (node == roots[i - 1]) roots[i - 1] = node->next;
insert_node(node, node->size * current_size);
}
}
else {
node->next = (Node*) ptr;
node->next->next = NULL;
node->next->prev = node;
node->next->size = count;
ends[i - 1] = node->next;
}
ptr = (void*) ((uintptr_t) ptr + count * current_size * 0x1000);
}
}
}
}
current_size /= 2;
}
/*if (!root) {
root = (Node*) ptr;
root->next = NULL;
root->prev = NULL;
root->size = size;
end = root;
}
else {
if (ptr > (void*) end) {
end->next = (Node*) ptr;
end->next->next = NULL;
end->next->prev = end;
end->next->size = size;
end = end->next;
return;
}
Node* node = root;
while (node->next) {
if ((void*) node > ptr) {
if (node == root) {
Node* old_root = root;
root = (Node*) ptr;
root->next = old_root;
root->prev = NULL;
root->size = size;
}
else {
node->prev->next = (Node*) ptr;
Node* new_node = node->prev->next;
new_node->next = node;
new_node->prev = node->prev;
new_node->size = size;
}
return;
}
node = node->next;
}
node->next = (Node*) ptr;
node->next->next = NULL;
node->next->prev = node;
node->next->size = size;
end = node->next;
}*/
}
void add_memory(void* memory, size_t size) {
if (size < 0x1000) return;
size_t pages = size / 0x1000;
insert_node(memory, pages);
}
int main() {
void* memory = malloc(128 * 2 * 0x1000);
//add_memory(memory, 128 * 0x1000);
add_memory(memory, 1 * 0x1000);
add_memory(memory + 0x1000, 1 * 0x1000);
//add_memory(memory + 128 * 0x1000, 128 * 0x1000);
printf("Hello, World!\n");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment