From b1a912a8a6ff472a49b2e0a09cfd433adfc2cb24 Mon Sep 17 00:00:00 2001 From: Benji Dial Date: Sat, 18 May 2024 21:53:38 -0400 Subject: reorganization, cross compiler --- documentation/euler/heap.txt | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 documentation/euler/heap.txt (limited to 'documentation/euler/heap.txt') diff --git a/documentation/euler/heap.txt b/documentation/euler/heap.txt new file mode 100644 index 0000000..de1deec --- /dev/null +++ b/documentation/euler/heap.txt @@ -0,0 +1,32 @@ +this file documents dynamic memory allocation and deallocation in userspace. +the unused areas of a process's usable mapped memory are divided into "chunks" +with a start and a length, satisfying the following properties: + a) the length of a chunk is a positive power of 2 + b) the start of a chunk is a multiple of its length + c) let s be a power of 2 and k be an integer. there are never two chunks with + length s and starts s * (2 * k) and s * (2 * k + 1). if ever an operation + would result in two such chunks, they are combined into one chunk with + length 2 * s and start 2 * s * k. + +a "chunk info page" is divided into 512 64-bit integers describing up to 255 +chunks and a pointer to another chunk info page. for each n from 0 to 254: + if the (2 * n)'th integer (where the first integer is the 0th one) is 0: + the (2 * n + 1)'th integer is unused. + if the (2 * n)'th integer is not 0: + the (2 * n)'th integer describes the length of a chunk + the (2 * n + 1)'th integer describes the start of the same chunk +the 510th integer is a pointer to the next chunk info page, and the 511th +integer is never used. + +when a program calls new or malloc with needed size s, we find a free chunk of +length at least s + 8. we then remove that chunk from the list of free chunks, +and add back in whatever is left after the first s + 8 bytes, if anything. +in the first 8 bytes of the original chunk, we store the value s + 8. the +remainder of the orginal chunk is returned to the program. + +during that process, if there isn't a chunk with the needed size, one or more +new pages are requested from the kernel to create such a chunk. + +when a program calls delete or free with pointer ptr, we read the integer in +the 8 bytes starting at ptr - 8 into a variable s. we then add the region +starting at ptr - 8 with length s to the free memory. -- cgit v1.2.3