1 #[macro_use]
2 extern crate alloc;
3 #[macro_use]
4 extern crate ctor;
5 
6 use std::sync::Arc;
7 use std::thread;
8 use std::thread::sleep;
9 use std::time::Duration;
10 
11 use alloc::alloc::GlobalAlloc;
12 use alloc::alloc::Layout;
13 use buddy_system_allocator::LockedHeap;
14 use criterion::{black_box, criterion_group, criterion_main, Criterion};
15 use rand::{Rng, SeedableRng};
16 
17 const SMALL_SIZE: usize = 8;
18 const LARGE_SIZE: usize = 1024 * 1024; // 1M
19 const ALIGN: usize = 8;
20 
21 /// Alloc small object
22 #[inline]
small_alloc<const ORDER: usize>(heap: &LockedHeap<ORDER>)23 pub fn small_alloc<const ORDER: usize>(heap: &LockedHeap<ORDER>) {
24     let layout = unsafe { Layout::from_size_align_unchecked(SMALL_SIZE, ALIGN) };
25     unsafe {
26         let addr = heap.alloc(layout);
27         heap.dealloc(addr, layout);
28     }
29 }
30 
31 /// Alloc large object
32 #[inline]
large_alloc<const ORDER: usize>(heap: &LockedHeap<ORDER>)33 pub fn large_alloc<const ORDER: usize>(heap: &LockedHeap<ORDER>) {
34     let layout = unsafe { Layout::from_size_align_unchecked(LARGE_SIZE, ALIGN) };
35     unsafe {
36         let addr = heap.alloc(layout);
37         heap.dealloc(addr, layout);
38     }
39 }
40 
41 /// Multithreads alloc random sizes of object
42 #[inline]
mutil_thread_random_size<const ORDER: usize>(heap: &'static LockedHeap<ORDER>)43 pub fn mutil_thread_random_size<const ORDER: usize>(heap: &'static LockedHeap<ORDER>) {
44     const THREAD_SIZE: usize = 10;
45 
46     let mut threads = Vec::with_capacity(THREAD_SIZE);
47     let alloc = Arc::new(heap);
48     for i in 0..THREAD_SIZE {
49         let prethread_alloc = alloc.clone();
50         let handle = thread::spawn(move || {
51             // generate a random size of object use seed `i` to ensure the fixed
52             // result of each turn
53             let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(i as u64);
54             // generate a random object size in range of [SMALL_SIZE ..= LARGE_SIZE]
55             let layout = unsafe {
56                 Layout::from_size_align_unchecked(rng.gen_range(SMALL_SIZE..=LARGE_SIZE), ALIGN)
57             };
58             let addr = unsafe { prethread_alloc.alloc(layout) };
59 
60             // sleep for a while
61             sleep(Duration::from_nanos((THREAD_SIZE - i) as u64));
62 
63             unsafe { prethread_alloc.dealloc(addr, layout) }
64         });
65         threads.push(handle);
66     }
67     drop(alloc);
68 
69     for t in threads {
70         t.join().unwrap();
71     }
72 }
73 
74 /// Multithread benchmark inspired by **Hoard** benchmark
75 ///
76 /// Warning: This benchmark generally needs long time to finish
77 ///
78 /// ----------------------------------------------------------------------
79 /// Hoard: A Fast, Scalable, and Memory-Efficient Allocator
80 ///       for Shared-Memory Multiprocessors
81 /// Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
82 //
83 /// Copyright (c) 1998-2000, The University of Texas at Austin.
84 ///
85 /// This library is free software; you can redistribute it and/or modify
86 /// it under the terms of the GNU Library General Public License as
87 /// published by the Free Software Foundation, http://www.fsf.org.
88 ///
89 /// This library is distributed in the hope that it will be useful, but
90 /// WITHOUT ANY WARRANTY; without even the implied warranty of
91 /// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
92 /// Library General Public License for more details.
93 /// ----------------------------------------------------------------------
94 ///
95 #[inline]
thread_test()96 pub fn thread_test() {
97     const N_ITERATIONS: usize = 50;
98     const N_OBJECTS: usize = 30000;
99     const N_THREADS: usize = 10;
100     const OBJECT_SIZE: usize = 1;
101 
102     #[derive(Clone)]
103     struct Foo {
104         pub a: i32,
105         pub b: i32,
106     }
107 
108     let mut threads = Vec::with_capacity(N_THREADS);
109 
110     for _i in 0..N_THREADS {
111         let handle = thread::spawn(move || {
112             // let a = new Foo * [nobjects / nthreads];
113             let mut a = Vec::with_capacity(N_OBJECTS / N_THREADS);
114             for j in 0..N_ITERATIONS {
115                 // inner object:
116                 // a[i] = new Foo[objSize];
117                 for k in 0..(N_OBJECTS / N_THREADS) {
118                     a.push(vec![
119                         Foo {
120                             a: k as i32,
121                             b: j as i32
122                         };
123                         OBJECT_SIZE
124                     ]);
125 
126                     // in order to prevent optimization delete allocation directly
127                     // FIXME: don't know whether it works or not
128                     a[k][0].a += a[k][0].b;
129                 }
130             }
131             // auto drop here
132         });
133         threads.push(handle);
134     }
135 
136     for t in threads {
137         t.join().unwrap();
138     }
139 }
140 
141 const ORDER: usize = 32;
142 const MACHINE_ALIGN: usize = core::mem::size_of::<usize>();
143 /// for now 128M is needed
144 /// TODO: reduce memory use
145 const KERNEL_HEAP_SIZE: usize = 128 * 1024 * 1024;
146 const HEAP_BLOCK: usize = KERNEL_HEAP_SIZE / MACHINE_ALIGN;
147 static mut HEAP: [usize; HEAP_BLOCK] = [0; HEAP_BLOCK];
148 
149 /// Use `LockedHeap` as global allocator
150 #[global_allocator]
151 static HEAP_ALLOCATOR: LockedHeap<ORDER> = LockedHeap::<ORDER>::new();
152 
153 /// Init heap
154 ///
155 /// We need `ctor` here because benchmark is running behind the std enviroment,
156 /// which means std will do some initialization before execute `fn main()`.
157 /// However, our memory allocator must be init in runtime(use linkedlist, which
158 /// can not be evaluated in compile time). And in the initialization phase, heap
159 /// memory is needed.
160 ///
161 /// So the solution in this dilemma is to run `fn init_heap()` in initialization phase
162 /// rather than in `fn main()`. We need `ctor` to do this.
163 #[ctor]
init_heap()164 fn init_heap() {
165     let heap_start = unsafe { HEAP.as_ptr() as usize };
166     unsafe {
167         HEAP_ALLOCATOR
168             .lock()
169             .init(heap_start, HEAP_BLOCK * MACHINE_ALIGN);
170     }
171 }
172 
173 /// Entry of benchmarks
criterion_benchmark(c: &mut Criterion)174 pub fn criterion_benchmark(c: &mut Criterion) {
175     // run benchmark
176     c.bench_function("small alloc", |b| {
177         b.iter(|| small_alloc(black_box(&HEAP_ALLOCATOR)))
178     });
179     c.bench_function("large alloc", |b| {
180         b.iter(|| large_alloc(black_box(&HEAP_ALLOCATOR)))
181     });
182     c.bench_function("mutil thread random size", |b| {
183         b.iter(|| mutil_thread_random_size(black_box(&HEAP_ALLOCATOR)))
184     });
185     c.bench_function("threadtest", |b| b.iter(|| thread_test()));
186 }
187 
188 criterion_group!(benches, criterion_benchmark);
189 criterion_main!(benches);
190