blob: de1deec8d936f14cdc42e165c728e0d2c9f85e08 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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.
|