portable-dlmalloc 0.1.0

Portable Fork of Doug Lea's malloc Implementation.
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

# portable-dlmalloc

Portable Fork of Doug Lea's `malloc` Implementation.

## Introduction

[This code is originally implemented by Doug Lea.](https://gee.cs.oswego.edu/dl/html/malloc.html) The original source code is no longer available from [the FTP URL listed in the website](ftp://g.oswego.edu/pub/misc/malloc.c), but you can still find it through [Wayback Machine](https://web.archive.org/web/20190530015756/ftp://g.oswego.edu/pub/misc/malloc.c).

This repository serves as a fork so that `dlmalloc` can be ported to any arbitrary platforms modularly.

This repository also contains a Rust crate so that you can use `portable-dlmalloc` in almost anywhere.

## Rust Crate

You may use this crate to help you make a portable global allocator. \
You will have to implement the eight C functions as described in [Port To Your Platform](#port-to-your-platform) chapter.

### Global Allocator

To use this crate as your global allocator:
```Rust
use portable_dlmalloc::DLMalloc;
#[global_alloactor] static GLOBAL_ALLOCATOR:DLMalloc=DLMalloc;

```
Then you will be able to use `alloc` crate.
```
extern crate alloc;
```

The default alignment of `dlmalloc` is twice the pointer size (e.g.: 16 bytes on 64-bit systems). \
If you need to use a different alignment, use `dlmemalign` function to implement your [`GlobalAlloc` trait](https://doc.rust-lang.org/alloc/alloc/trait.GlobalAlloc.html).

### Alternate Allocator

The [Allocator Trait](https://doc.rust-lang.org/alloc/alloc/trait.Allocator.html) is currently nightly-only. \
Currently, this crate does not support this trait.

### Raw FFI

The `raw` module from this crate exports FFI bindings for `dlmalloc` library.
```Rust
use portable_dlmalloc::raw::*;
```
For example, you may use `dlmallopt` to adjust `mmap` granularity (default is 2MiB in Rust crate):
```Rust
dlmallopt(M_GRANULARITY,0x20000);	// Change `mmap` granularity to 128KiB.
```
You may use `dlpvalloc` to allocate memory on page-granularity.
```Rust
let p=dlpvalloc(12345);
assert_eq!(p as usize & 0xfff,0);
```
**Warning**: `dlpvalloc` - as well as other routines that allocate memories with higher granularities - may cause serious memory fragmentation if you overrely on them.
```Rust
// Assume 4096 is page size.
let p=dlpvalloc(4096) as usize;
let q=dlpvalloc(4096) as usize;
// Consecutive allocations do not guarantee them to be adjacent.
assert_eq!(q-p,8192);
```

## Port To Your Platform

To port `dlmalloc` to your platform, implement the following procedures:

- `custom_mmap`/`custom_munmap`: Allocate and free pages from the system. `mmap` should return `(void*)-1` to indicate failure instead of `NULL`. `munmap` should return `0` to indicate success, and `-1` to indicate failure.
	```C
	void* custom_mmap(size_t length);
	int custom_munmap(void* ptr,size_t length);
	```
	```Rust
	#[no_mangle] unsafe extern "C" custom_mmap(length:usize)->*mut c_void;
	#[no_mangle] unsafe extern "C" custom_munmap(ptr:*mut c_void,length:usize)->i32;
 	```
- `custom_direct_mmap`: Extend the allocated pages. This is optional. Return `(void*)-1` to indicate failure/no-support.
	```C
	void* custom_direct_mmap(size_t length);
	```
	```Rust
	#[no_mangle] unsafe extern "C" custom_mmap(length:usize)->*mut c_void;
	```
- `init_lock`/`final_lock`/`acquire_lock`/`release_lock`: Implement thread-safety for `dlmalloc`. The minimal implementation can be a simple spinlock. You can leave the implementations empty for this set of routines if you do not need thread-safety.
	```C
	void init_lock(void* *lock);	// Initialize the mutex.
	void final_lock(void* *lock);	// Finalize the mutex.
	void acquire_lock(void* *lock);	// Acquire the mutex.
	void release_lock(void* *lock);	// Release the mutex.
	```
	```Rust
	#[no_mangle] unsafe extern "C" init_lock(lock:*mut *mut c_void);	// Initialize the mutex.
	#[no_mangle] unsafe extern "C" final_lock(lock:*mut *mut c_void);	// Finalize the mutex.
	#[no_mangle] unsafe extern "C" acquire_lock(lock:*mut *mut c_void);	// Acquire the mutex.
	#[no_mangle] unsafe extern "C" release_lock(lock:*mut *mut c_void);	// Release the mutex.
	```
- `custom_abort`: Implement `abort()` routine. `dlmalloc` calls `custom_abort()` when internal assertion fails. You may use panic here.
	```C
	void custom_abort(void);
	```
	```Rust
	#[no_mangle] unsafe extern "C" custom_abort()->!;
	```
- `dprintf2`: Implement debug-printer, which can trace file-name and line-numbers, for `dlmalloc`. Note that the format specifiers are implementation-specific. For example, you might have to use `%a` to print ASCII-strings in EDK2. You do not have to implement `dprintf2` if you won't debug `malloc.c`.
	```C
	int dprintf2(const char* src_fn,const int src_ln,const char* fmt,...);
	```
	If you need to print stuff in `malloc.c` codes, just use the `dprintf` macro.

	If you use `portable-dlmalloc` crate, do not implement this routine.
- `memcpy`/`memset`: I suppose no explanations are needed for these two. `dlmalloc` uses these two routines, but they can be easily implemented. Some embedded SDKs may even include `memcpy`/`memset`, though they might not have `malloc`.

When you compile `malloc.c`, define the following preprocessor flags:

- `PORTABLE`: This flag makes `dlmalloc` call `custom_mmap`, `custom_munmap` and `custom_direct_mmap` functions. This flag is required to port `dlmalloc` to your platform.
- `NO_MALLOC_STATS=1`: This flag forbids `dlmalloc` from outputting debug messages. Otherwise, you will have to implement `dprintf2`.
- `USE_LOCKS=2`: This flag makes `dlmalloc` call `init_lock`, `final_lock`, `acquire_lock` and `release_lock` functions. This flag is required to port `dlmalloc` to your platform while ensuring thread-safety. Otherwise, define `USE_LOCKS=0`.
- `USE_DL_PREFIX`: This flags makes all routines from `dlmalloc` has `dl` prefix so that you can avoid name-conflict issues.
- `DEFAULT_GRANULARITY`: This constant determines the size granularity when `dlmalloc` calls `custom_mmap`. The default is 64KiB.

Note: the following samples with Custom Port do not keep track of allocated pages. There will be unreleased pages after your program quits even if you freed all allocated buffers. If you port `dlmalloc` to programs that are volatile to its address-space (e.g.: Kernel-Mode drivers, pluggable dynamic libraries), you have to keep track of allocated pages and release them before you quit.

## Samples

This chapter describes how to build samples with `dlmalloc` library. Note that this chapter emphasizes on the given samples. If you wish to port `dlmalloc` to your platform, it's recommended to check out [Port to Your Platform](#port-to-your-platform) section, which provides the generalized guide for building the portable `dlmalloc`. You should be able to use this generalized guide if you are familiar with your compiler suite / build system.

### Build for Windows with Internal Port

Download [Windows Driver Kit 7.1 (WDK-7600)](https://www.microsoft.com/en-us/download/details.aspx?id=11800) and install to default location in C: drive.

Execute `compchk_win7x64.bat` (Debug/Check version, optimizations are disabled) and `compfre_win7x64.bat` (Release/Free version, optimizations are enabled) to build DLLs. The DLL has dependencies on `msvcrt.dll` and `kernel32.dll`, which are present in most Windows systems. The DLL exports both `dlmalloc` and `malloc`, just in case you might encounter name conflicts. This file is ready-to-use.

This option will build `dlmalloc` into a very small binary size. Note that `mmap` and `munmap` emulations via `VirtualAlloc` and `VirtualFree` are already implemented by Doug Lea.

The `dlmalloc.dll` can be directly used.

See `sample.c` for details.

### Build for Windows with Custom Port

Download [Enterprise Windows Driver Kit for Windows 11, version 24H2 with Visual Studio Build Tools 17.10.5 (EWDK-26100)](https://learn.microsoft.com/en-us/legal/windows/hardware/enterprise-wdk-license-2022) and mount it to V: drive. You may use [WinCDEmu](https://wincdemu.sysprogs.org/download/) to mount ISO images.

Execute `compchk_win11x64.bat` (Debug/Check version, optimizations are disabled) and `compfre_win11x64.bat` (Release/Free version, optimizations are enabled) to build static libraries and corresponding samples.

This option serves as a basic sample for implementing necessary routines for thread-safe `dlmalloc`. This sample uses Windows `SRWLock` to act as a lightweight mutex.

The `dlmalloc.lib` can be directly used in anywhere, as long as the program uses MSVC ABI and PE-COFF executable format.

See `port_win.c` for details.

### Build for UEFI with Custom Port

Download [Enterprise Windows Driver Kit for Windows 11, version 24H2 with Visual Studio Build Tools 17.10.5 (EWDK-26100)](https://learn.microsoft.com/en-us/legal/windows/hardware/enterprise-wdk-license-2022) and mount it to V: drive. You may use [WinCDEmu](https://wincdemu.sysprogs.org/download/) to mount ISO images.

Clone the [EDK-II-Library](https://github.com/Zero-Tang/EDK-II-Library) recursively and create the `EDK2_PATH` environment variable pointing to the `EDK-II-Library`.

Execute `compchk_uefix64.bat` (Debug/Check version, optimizations are disabled) and `compfre_uefix64.bat` (Release/Free version, optimizations are enabled) to build static libraries and corresponding samples.

This option serves as a basic sample for implementing necessary routines for thread-safe `dlmalloc` on UEFI platform. This sample implements a TAS spinlock to act as a mutex.

See `port_uefi.c` for details.

### Build for Rust with Custom Port

Install [Rust](https://www.rust-lang.org/) with target `x86_64-pc-windows-msvc`.

Execute:
```
cargo build --all
```

This option serves as a basic sample for utilizing `dlmalloc` as the Rust global allocator.

When you implement port functions, make sure you append `#[no_mangle] extern "C"` prefix on your function. For example:
```Rust
#[no_mangle] extern "C" fn custom_abort()->!

```

Note that `print!` (as well as `println!`) macro from rust std has allocation behaviors! To be precise, both `std::fmt::Arguments::to_string()` and `std::io::stdout().write()` have allocation behaviors! Therefore, this sample provides a `naprint!` macro for you to trace allocation operations without recursion. Be careful, the `naprint!` macro cannot handle formatted output larger than 512 bytes! \
Therefore, if you use `print!`/`println!` in `dlmalloc` port routines, you will find your program being deadlocked, as `SRWLock` does not support recursive locking.

## License

This repository is under the [MIT license](./license.txt). \
If you do not want to obey the MIT license, just [use the original `dlmalloc` implementation](https://web.archive.org/web/20190530015756/ftp://g.oswego.edu/pub/misc/malloc.c) instead. It is in the [Public Domain](https://wiki.creativecommons.org/wiki/public_domain).