In the previous section, we talked about the principle of dynamic memory allocator asMaintaining a Heapand is a key factor in the realization of the varioussequential memory allocationMethodology.
But the previous part was directly referenced through thebuddy_system_allocatorThe problem to be solved.
Then I was interested in the memory allocation algorithm, or decided to look at the source code, in shortPeople are salted fish.But you still need to dream.
If you don't have a dream, you won't be able to find the meaning of life.
Get source code for buddy_system_allocator
buddy_system_allocatoralsorCoreThis community program .
cd ~/workspace
git clone /rcore-os/buddy_system_allocator.git
Start looking at the source code from a practical point of view
For starters, let's start with.more familiarLook at the code and think about how the code is organized.
buddy_system_allocatorHow is it referenced as an external package?- In the previous section we called
LockedHeapSo how is this class implemented and what does it depend on?
LockedHeap
We searched the source code forLockedHeapWe can find out more about this in theFind its implementation in the
pub struct LockedHeap<const ORDER: usize>(Mutex<Heap<ORDER>>);
On seeing this definition there is aseem to understand, but not to understandThe feeling that you can onlyguessLockedHeapis a thread-locked file of sizeORDER(used form a nominal expression)Heap:
- on account of
ORDERPut it in.<>In the middle, it's supposed to be withgeneralized type (math.)There is a relationship, but it is clearly labeled hereusizeclarificationORDERis a variable.- Because of the presence in the implementation of the struct
()It's a bit of a lost cause.
tuple structure (computing)
ferret outThe Rust Bible, it was found that such a structure exists where fields can be unnamed.
A new question arises here, if the field can be unnamed, then theHow to access the contents of a structureAnd?
refer toThe Official Rust Language Reference Manual, it can be seen that.
Tuple structs are similar to regular structs, but its fields have no names. They are used like tuples, with deconstruction possible via
let TupleStruct(x, y) = foo;syntax. For accessing individual variables, the same syntax is used as with regular tuples, namelyfoo.0,foo.1, etc, starting at zero.
pass (a bill or inspection etc)digital (electronics etc)to access the contents of these structures.
// If the TupleStruct exists.
let foo = TupleStruct(1,2);
// You can destruct it in this way
let TupleStruct(x, y) = foo;
// Can be accessed numerically
let x = foo.0;
let y = foo.1; // can be accessed as a number
value pantype
So here's what you need to seeBibliography-value generalizationThe content of the program is especially itstypical example.
The final conclusion: Rust is allowed to generalize values, which means that theLockedHeapThere is a generic parameter associated with the value.
It's a lot like that at times.
Cinner#define ORDER 0x30000The ...
But it's actually a lot more flexible in Rust.
this is similar toLockedHeapThe two methods provided for obtaining examples correspond to each other.
impl<const ORDER: usize> LockedHeap<ORDER> {
/// Creates an empty heap
pub const fn new() -> Self {
LockedHeap(Mutex::new(Heap::<ORDER>::new()))
}
/// Creates an empty heap
pub const fn empty() -> Self {
LockedHeap(Mutex::new(Heap::<ORDER>::new()))
}
}
You can't see it from here, because there's another layer.Heap"It depends.Heapmethod to get an instance of the
add mutex lock
Once you understand the above syntax, you only need to understand theGlobalAllocthis onetraitinsofar asLockedHeapRealization of.
#[cfg(feature = "use_spin")]
unsafe impl<const ORDER: usize> GlobalAlloc for LockedHeap<ORDER> {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
self.0
.lock()
.alloc(layout)
.ok()
.map_or(core::ptr::null_mut(), |allocation| allocation.as_ptr())
}
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
self.().dealloc(NonNull::new_unchecked(ptr), layout)
}
}
It's actually in theHeapWith an extra one on the outside.MutexMutually exclusive locks, then foralloccap (a poem)deallocimplementation, you only need to access the innerHeap, and then visit theHeap(used form a nominal expression)alloccap (a poem)deallocMethodology.
Heap
define
HeapIt actually consists of a file of lengthORDER(used form a nominal expression)listcap (a poem)user,allocatedcap (a poem)totalSeveral values.
pub struct Heap<const ORDER: usize> {
// buddy system with max order of `ORDER - 1`
free_list: [linked_list::LinkedList; ORDER],
// statistics
user: usize,
allocated: usize,
total: usize,
}
in that caseORDERin effectconst value generalizationI've got it.
Why is it not necessary to specify the ORDER value in the code?
Because we set the version of the package to0.6This version of the package does not include a generic parameter, but instead fixes the length of the chain table to be32.
Get Instance
ferret outHeap(used form a nominal expression)newcap (a poem)emptyMethods.
impl<const ORDER: usize> Heap<ORDER> {
/// Create an empty heap
pub const fn new() -> Self {
Heap {
free_list: [linked_list::LinkedList::new(); ORDER],
user: 0,
allocated: 0,
total: 0,
}
}
/// Create an empty heap
pub const fn empty() -> Self {
Self::new()
}
}
Pay attention here.listanLinkedListType, a chained table.
Setting the heap range
Remember from the last blog, we initialized it with the following code.
/// Initialize heap allocator
pub fn init_heap() {
unsafe {
HEAP_ALLOCATOR
.lock()
.init(HEAP_SPACE.as_ptr() as usize, KERNEL_HEAP_SIZE);
}
}
here areleaving asideHEAP_ALLOCATOR.lock()How did you get theHeapinstance. Here's theinitIt does callHeap(used form a nominal expression)init.
Next, let's look at its implementation.
impl<const ORDER: usize> Heap<ORDER> {
... ...
/// Add a range of memory [start, end) to the heap
pub unsafe fn add_to_heap(&mut self, mut start: usize, mut end: usize) {
// avoid unaligned access on some platforms
start = (start + size_of::<usize>() - 1) & (!size_of::<usize>() + 1);
end &= !size_of::<usize>() + 1;
assert!(start <= end);
let mut total = 0;
let mut current_start = start;
while current_start + size_of::<usize>() <= end {
let lowbit = current_start & (!current_start + 1);
let mut size = min(lowbit, prev_power_of_two(end - current_start));
// If the order of size is larger than the max order,
// split it into smaller blocks.
let mut order = size.trailing_zeros() as usize;
if order > ORDER - 1 {
order = ORDER - 1;
size = 1 << order;
}
total += size;
self.free_list[order].push(current_start as *mut usize);
current_start += size;
}
+= total;
}
/// Add a range of memory [start, start+size) to the heap
pub unsafe fn init(&mut self, start: usize, size: usize) {
self.add_to_heap(start, start + size);
}
}
initis calledadd_to_heap,The input isThe heap needs to manage the initial address of the memory and the size of the space.
stapleadd_to_heapThe subtle algorithms in the...
address alignment algorithm
insofar asfirst address, to ensure thatstartThe value of is the same as the value ofusizeThe size of the
The first thing to declare here is that all variables are of size\(2^n\). Then its binary is actuallyOne bit is 1 and the rest are 0The ...
start = (start + size_of::<usize>() - 1) & (!size_of::<usize>() + 1);
Rust.!It's a bitwise inverse, the same as in C.!logical non sequitur~It's the inverse of the bit.not the same.
The formula used here is actually $$aligned_addr = (addr + align - 1) & (!align + 1)$$
Here's a direct example.
unevenaddr:
\(addr=15,align=2\)
\(addr=b'0\_1111\)
\(addr+align-1=b'1\_0000\)
\(align=b'0\_0010\)
\(!align=b'1\_1101\)
\(!align+1=b'1\_1110\)
\(aligned\_addr=b'1\_0000\)
Final results obtainedaligned_addrIt's 16.
itself has been alignedaddr:
\(addr=16,align=2\)
\(addr=b'1\_0000\)
\(addr+align-1=b'1\_0001\)
\(align=b'0\_0010\)
\(!align=b'1\_1101\)
\(!align+1=b'1\_1110\)
\(aligned\_addr=b'1\_0000\)
Final results obtainedaligned_addrIt's 16.
foundalignbecause of\(2^n\)，addr + align - 1Guaranteed if lownBit as long as it's not all0It's all going to then + 1localization1And on the right.!(align-1)minus1After pressing the bit to take the reverse, then dotogether withlow arithmetic guaranteenbitwise0This completes the alignment, and theIf not aligned round up.
Similarly, forfinal address:
end &= !size_of::<usize>() + 1;
Also written as a formula expression:$$addr_aligned=addr&(!align+1)$$
It's easy to understand. It's guaranteed to be low.nYes.0, which is also an aligned address, but theround down.
this kind ofFirst address rounded up, last address rounded down, it is guaranteed that the address of the operation is the original address of thesubsetsThere will be no overstepping of boundaries.
#todo There may be a need to draw a diagram here.
Last adopted.
assert!(start <= end);
guarantee addressvalidity.
Algorithm for Address Entry Heap
Alignment requirements for computing addresses
according tostarting addressHow many bytes are required to calculate the address, that is, how many bytes are required to calculate the address.lowest valid bit.
Compute the lowest bit of the address1Corresponding values.
Formula:$$lowbit=num&(!num+1)$$
Example.
\(num=10\)
\(num=b'1010\)
\(!num=b'0101\)
\(!num+1=b'0110\)
\(num\&(!num+1)=b'0010\)
\(lowbit=b'0010=2\)
treat (sb a certain way)numInverse, thenminimum (point)(used form a nominal expression)1change into0balance0turn into1, then!num+1It must make the lowest level1change into1, and the rest of the bits change back to0, so that in the case withnumone's ownseek peace withAnd what you end up with is that there's onlyMinimum 1A number of.
Calculate the size of the power of 2 that can fit in the remaining space
first of allCalculated less than or equal to the given numbernum The largest power of 2 of:
pub(crate) fn prev_power_of_two(num: usize) -> usize {
1 << (usize::BITS as usize - num.leading_zeros() as usize - 1)
}
usize::BITSbeusizethe number of digits, thenum.leading_zeros()betop one1prior0ordinal number.
so thatusize::BITS as usize - num.leading_zeros() as usize - 1That's the first one.1Subsequent digits.
Then it is easy to see that the final result isLess than or equal to the given numbernum The largest power of 2 of.
Calculating Block Size
comparisonslowest1corresponding valuecap (a poem)Less than or equal to the largest power of 2 of the length of the address intervalChoose the smaller one.
Understand this.
- Under normal circumstances, the smallest block size should beconform to address alignmentThe ...
- But it's possible.space leftis not enough to hold such a block, then it is the smallest block that can fit in the remaining space.\(2^n\)The size of the block is determined by the size of the
Determine block size and maximum order
Calculate the current order, thesizeThere's a couple of them.0Just a few steps.
If the order is greater than the maximal order, then theone half,go down a level.
GPT:
The Buddy System algorithm has a concept of maximum order. Maximum order limits the maximum size of a single block.
- Memory fragmentation management: Memory fragmentation can be better managed by limiting the size of blocks. If the block is too large, it may lead to memory fragmentation problems, as large blocks may not be fully utilized by smaller requests.
- performance optimization: Smaller blocks are easier to manage and allocate and can improve the efficiency of memory allocation and release.
Accumulates the size of the currently partitioned block
utilizationtotalCalculate the size of the block used at this point.
Store the block start address according to the order in the list of available space corresponding to the order.
Each available space list of theeach elementbelinked list, chained list preservationcurrent orderStarting address.
i.e.Pointers to blocks of the same size exist in a linked table.
self.free_list[order].push(current_start as *mut usize);
Moving the starting address pointer
Move the start address pointer so that the next round of allocation continues.
current_start += size;
summarize
You can see that it is the first step to set theAddress alignment of allocatable memory, fromstartuntil (a time)end,do one's utmostDivide the space intolarger\(2^n\)blocks, without wasting space, and stored in a chained table.
What's going on?
Here the smallest alignment unit is taken as8=b1000=0x0008As an example.
Example 1
Let's say your address is(0x0100,0x0120), then after the alignmentpassably (good)be(0x0100,0x0120):
Pay attention here.0x0120-0x0100=32, so it's straightforward to allocate a file of size32The blocks.
![[Pasted image |1200]]
Example 2
Let's say your address is(0x0001,0x0021), then after alignment it is(0x0008,0x0021):
![[Pasted image |1200]]
in order toemploy one's assets the fullest, aligning the lowest bit each time.
At the end of the day, there may not be enough memory left to satisfy the alignment minimum, because ourThe address is aligned.and thus the remaining memory size is also satisfied by the\(2^n\)The remaining memory is stored directly in a block.
If the allocatable memory exceeds the availableSpace ListThe storage order, then, is broken down, up to the maximum block of storage that can be allocated.
Allocation of memory
The code to allocate memory is as follows.
pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> {
let size = max(
().next_power_of_two(),
max((), size_of::<usize>()),
);
let class = size.trailing_zeros() as usize;
for i in class..self.free_list.len() {
// Find the first non-empty size class
if !self.free_list[i].is_empty() {
// Split buffers
for j in (class + 1..i + 1).rev() {
if let Some(block) = self.free_list[j].pop() {
unsafe {
self.free_list[j - 1]
.push((block as usize + (1 << (j - 1))) as *mut usize);
self.free_list[j - 1].push(block);
}
} else {
return Err(());
}
}
let result = NonNull::new(
self.free_list[class]
.pop()
.expect("current block should have free space now")
as *mut u8,
);
if let Some(result) = result {
+= ();
+= size;
return Ok(result);
} else {
return Err(());
}
}
}
Err(())
}
First, the incoming parameterslayoutis a structure or a basic data type.
- Calculate the size of basic data types larger than this\(2^n\).
- Calculates the aligned size of this basic data type.
- count
usizeSize.
Comparing these three sizes.Select the largest of theseaccomplishmentsize.
last resortsize(used form a nominal expression)orderThe order isclass, i.e., actually looking for only the most important things that are better thanclasslargeorderCorresponds to an unallocated block in a linked table.
From the smallest - that is, the one that most closely matchessizeFind the size of the corresponding chain table, and call it up if it's not empty.
At this point the matchingorderbecause ofi.
(class + 1..i + 1).rev()It's a very clever design, from theclass+1until (a time)i+1andflips.
at a timepopA block, and divide this block into two blocks, and calculate the two blocks'first addressand then stored in the next level of blocks.
All the way up to the size block that matches theclass.
The last thing you need to do is just put the currentclassCorresponds to the first block of the chain tablepopJust come out, that's the answer.
Destroy memory
Memory is destroyed by.
pub fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) {
let size = max(
().next_power_of_two(),
max((), size_of::<usize>()),
);
let class = size.trailing_zeros() as usize;
unsafe {
// Put back into free list
self.free_list[class].push(ptr.as_ptr() as *mut usize);
// Merge free buddy lists
let mut current_ptr = ptr.as_ptr() as usize;
let mut current_class = class;
while current_class < self.free_list.len() - 1 {
let buddy = current_ptr ^ (1 << current_class);
let mut flag = false;
for block in self.free_list[current_class].iter_mut() {
if () as usize == buddy {
();
flag = true;
break;
}
}
// Free buddy found
if flag {
self.free_list[current_class].pop();
current_ptr = min(current_ptr, buddy);
current_class += 1;
self.free_list[current_class].push(current_ptr as *mut usize);
} else {
break;
}
}
}
-= ();
-= size;
}
First, the incoming parametersptris a structure or a basic data type of apointer on a gauge.
- Calculate the size of basic data types larger than this\(2^n\).
- Calculates the aligned size of this basic data type.
- count
usizeSize.
Comparing these three sizes.Select the largest of theseaccomplishmentsize.
last resortsize(used form a nominal expression)orderThe order isclass, i.e., actually looking for only the most important things that are better thanclasslargeorderCorresponds to an unallocated block in a linked table.
particle marking the following noun as a direct objectptrdeposit (e.g. in a bank account)List of available spacefree_listInside.
But simply depositing it will result in theSpace is becoming increasingly fragmented, so that subsequent requests for larger blocks of memory are not available.
There is a very central algorithm here, which is why it is calledbuddy system.
let buddy = current_ptr ^ (1 << current_class);
is the method by which the current memory block is calculatedbuddy.
1<<current_classis to derive a binaryOnly one bit is1(used form a nominal expression)Value.
followed bycurrent_ptrcompete with itdifferentiation, then in the end what is actually solved for is a pair ofcurrent_ptrexistclassThat one'sflipsResults.
provided thatcurrent_ptrbe000110100100 :
-
000110100100（current_ptr） -
000000000100(mask) -
000110100000(Heterogeneous results)
Well, actually, the two addresses areTwo adjacent blocks of the same size.
If in thisclassFind the block that starts at this address in the corresponding chain table, then merge the two blocks and find the two addresses.comparatively smallwhich is actually addressed in the first half, and then deposited into theordercomparatively higher levelin a chained table.
Buddy System Memory Allocation Algorithm
After reading the code, I feel that I have a clear idea, but it's still a mess, and I still need to clear the algorithm in a systematic way.
You can't hide from the theory part.If you don't do it right, you're going to be in deep shit.!
This is done here through theUse the method that specifies the filetypeGot it.Very good information..
linked list
When I first started working with Rust, I heard that chained lists were hard to write, and I looked at the algorithms in the repository for chained lists, and they do work.understand what one is reading or watchingBut there's a difference between being able to read and being able to write.
Three things to figure out.
- Those features of rust are used
- Why use these features
- Why do you want to use
unsafe
#TODOThere may be an exercise post on writing your own rust chain tables to follow.
summarize
Don't engineer things too much, especially.The process of self-learning(a) To emphasize the importance of basic skills development.self-developmentIt is important to pay attention to the process ofinfrastructural"To putIf you can run, you can run.Get that out of your head.
Why teach yourself if you can still run when you're self-taught? No one's paying my salary.