blob: f6ca0c685987b2ebe2f12408e02c36c7c6a50dfe (
plain)
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
Problems with arena allocation
==============================
Main problems with the most naive solution:
1. Unused space at the end
2. Pointer-chasing across *all* allocated pages.
3. Large data structures can get splitted many times.
Possible solution to:
1 and 2:
- Use the tail space for book-keeping of following chunks.
(e.g. an array of offsets)
1:
- In the last chunk, we can track the amount of free space in the previous
chunk (perhaps it could be a pointer to the first free byte -- the amount
of free space can be calculated as roundup(freeptr,4k)-freeptr )
- The check could be implemented as:
if ((lastptr&0xFFF)+requested_size >= 0x1000)
- This pointer can be re-purposed as a next-pointer (which will always point
to an even 4kB address)
- At this point, the chunk would be "locked", except for tail allocations
via the following chunk (as described in the point above).
- This pointer could possibly be stored at the end.
- That way it can be repurposed as storage space, if the following chunk
can be allocated adjacent to the chunk.
- This gives worse cache efficiency, though
2:
- For sequentially mmap'ed chunks, we can have a length field
in the first chunk.
3:
- Have a special type qualifier for non-addressible data
(or even more specific: non-addressible OR non-arena-addressible data)
- Allow chunk headers to be omitted for "middle chunks" in arrays of
non-addressible data.
- Store arena meta-data at a fixed virtual address offset (e.g. +1GB
on 32-bit platforms or perhaps +1TB on 64 bit platforms).
Note that this requires MAP_FIXED_NOREPLACE support in mmap, to
protect existing mappings from getting overwritten.
Possible problem with arena chunk information and CHERI
-------------------------------------------------------
Each arena chunk contains some info at the beginning, and the address
to this area is computed by masking the low-order bits of a pointer
(to round down to the arena chunk size, e.g. 4 KiB).
* Does this work with CHERI?
* Perhaps a parameter passed as "arena" should give access to the whole
arena? (i.e. all chunks)
|
