Last active
July 5, 2022 19:22
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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