官方库中Vec的很多底层被屏蔽了，学习的时候，需要注意一个问题，Vec的内存是如何分配的？Rust是如何解决了C++中数组能够越界访问的问题的？
从Vec的定义着手：
pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {buf: RawVec<T, A>,len: usize,}
其中两个需要注意的地方，一个是RawVec<T,A>这个数据结构，看名称知道是一个底层的数据结构
第二个是非稳定的Allocator，查看简介是：
/// An implementation of Allocator can allocate, grow, shrink, and deallocate arbitrary blocks of data described via Layout.是一种分配器的实现，就是为了去操作任意的 `一块` 数据，而描述这块数据使用的是 `Layout` 这个数据结构
Allocator
简介
该分配器属于核心包core::alloc，定义为一个trait：
注意目前是unstable的，后面更新后再修改这部分！
首先摘抄文档：
- Allocator是允许分配0大小的内存的（不同于
GlobalAlloc），如果Allocator底层的分配器不支持的话，我们的实现需要考虑到这个问题并进行复写（比如jemalloc 或者 libc::malloc 返回null指针）。此外，需要注意，Allocator的实现是基于ZST、引用以及智能指针的，因为如果不是这样实现的话，比如我们使用MyAlloc([u8; N])实现一个Allocator，分配了内存，那么会因为这个分配器就是固定在了堆上面而无法随意move，除非指向他的指针一齐改变。 - 注意”当前分配的内存”，对于这个概念，实现定义Allocator的trait需要满足
allocate, grow, or shrink三个方法需要返回分配的内存的起始地址的指针- 同时，指向并没有被deallocated的内存块的起始地址指针需要保持有效。所谓deallocated需要通过两种办法达到
deallocated方法或者成功grow or shrink（返回Ok）
- 分配的内存块必须（适配）
**fit**Layout！反过来也一致，Layout适配内存块。这句话意味着：- 就像方法
layout.align()一样，分配的内存必须对齐(alignment) - 定义min为Layout最近一次用于分配内存块的大小，定义max为最新的实际的大小，由
grow or shrink修改，那么layout.size()必须满足min..=max的条件
- 就像方法
安全性要求：
NonNull<u8>指针，包裹起来内存的起始地址Layout结构体，描述了内存的大小以及对齐模式，确保了对齐
因此，核心的线就是，查找：
- 内存起始地址在什么地方定义的？（这个移交给了Allocator，而Allocator作为了接口方法没有作为默认方法交由实现者执行）
- 内存的大小如何确定？（解决了，Layout里面通过计算确保了大小不会溢出不会不满足对齐，且具体大小的测算来则mem包，最后调用了内部的编译器方法）
对齐应该是多大？（应该是结构体中的最大对齐大小，所有元素的对齐大小由编译器的内部方法计算了）
关键的四个方法
分配内存
// 即具体内存怎么分配由实例化的Allocator决定fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>;// 可以默认分配0空间内存fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {let ptr = self.allocate(layout)?;// SAFETY: `alloc` returns a valid memory blockunsafe { ptr.as_non_null_ptr().as_ptr().write_bytes(0, ptr.len()) }Ok(ptr)}
扩展内存
```rust unsafe fn grow( &self, ptr: NonNull
, old_layout: Layout, new_layout: Layout, ) -> Result new_layout.size() >= old_layout.size(), "`new_layout.size()` must be greater than or equal to `old_layout.size()`");
let new_ptr = self.allocate(new_layout)?;
// SAFETY: because
new_layout.size()must be greater than or equal to //old_layout.size(), both the old and new memory allocation are valid for reads and writes forold_layout.size()bytes. Also, because the old allocation wasn’t yet deallocated, it cannot overlapnew_ptr. Thus, the call tocopy_nonoverlappingis safe. The safety contract fordeallocmust be upheld by the caller. unsafe {// 注意这个方法，将src(第一个参数)内存中的部分字节(第三个参数)拷贝到dst(第二个参数)，因此dst是mut的，但是注意，如果src中重叠了dst中的内存，这就会造成问题，因为复写不完整了 ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), old_layout.size()); self.deallocate(ptr, old_layout);} Ok(new_ptr) }
// 有个可以看着玩的，查看两个指针指向的地址是否重叠，思路就是直接比较两个指针起始点的绝对距离
[cfg(debug_assertions)]
pub(crate) fn is_nonoverlapping
<a name="Y2Zo2"></a>
### 收缩内存
```rust
unsafe fn shrink(
&self,
ptr: NonNull<u8>,
old_layout: Layout,
new_layout: Layout,
) -> Result<NonNull<[u8]>, AllocError> {
debug_assert!(
new_layout.size() <= old_layout.size(),
"`new_layout.size()` must be smaller than or equal to `old_layout.size()`"
);
let new_ptr = self.allocate(new_layout)?;
// SAFETY: because `new_layout.size()` must be lower than or equal to
// `old_layout.size()`, both the old and new memory allocation are valid for reads and
// writes for `new_layout.size()` bytes. Also, because the old allocation wasn't yet
// deallocated, it cannot overlap `new_ptr`. Thus, the call to `copy_nonoverlapping` is
// safe. The safety contract for `dealloc` must be upheld by the caller.
unsafe {
ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), new_layout.size());
self.deallocate(ptr, old_layout);
}
Ok(new_ptr)
}
释放内存
// 注意！
// ptr must denote a block of memory ``currently allocated`` via this allocator, and layout must ``fit`` that block of memory.
unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);
Vec使用的分配器：Global
注意Global存在两个意义，一个是core包中的GlobalAlloc Trait，这个Trait可以经过#[global_allocator] attribute�注册来替代默认使用的std包中的Global，我们核心是去理解Vec使用的Global分配器的实现。记得关键的三个地方，内存的起始地址、大小以及对齐大小。
定义很简单，为：
#[unstable(feature = "allocator_api", issue = "32838")]
#[derive(Copy, Clone, Default, Debug)]
#[cfg(not(test))]
pub struct Global;
核心的分配、重分配以及收回内存的方法来源于，可能是编译器中：
extern "Rust" {
// These are the magic symbols to call the global allocator. rustc generates
// them to call `__rg_alloc` etc. if there is a `#[global_allocator]` attribute
// (the code expanding that attribute macro generates those functions), or to call
// the default implementations in libstd (`__rdl_alloc` etc. in `library/std/src/alloc.rs`)
// otherwise.
// The rustc fork of LLVM also special-cases these function names to be able to optimize them
// like `malloc`, `realloc`, and `free`, respectively.
#[rustc_allocator]
#[rustc_allocator_nounwind]
fn __rust_alloc(size: usize, align: usize) -> *mut u8;
#[rustc_allocator_nounwind]
fn __rust_dealloc(ptr: *mut u8, size: usize, align: usize);
#[rustc_allocator_nounwind]
fn __rust_realloc(ptr: *mut u8, old_size: usize, align: usize, new_size: usize) -> *mut u8;
#[rustc_allocator_nounwind]
fn __rust_alloc_zeroed(size: usize, align: usize) -> *mut u8;
}
因此，实际_std::alloc::{alloc_zeroed, dealloc, alloc};_这几个方法实际上来源于对以上四个方法的包装，以后再探究上面这四个方法究竟来源于什么地方：
// 回忆current allocate的概念，这里实际上返回的都是内存的起始地址
pub unsafe fn alloc_zeroed(layout: Layout) -> *mut u8 {
unsafe { __rust_alloc_zeroed(layout.size(), layout.align()) }
}
pub unsafe fn realloc(pt
r: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
unsafe { __rust_realloc(ptr, layout.size(), layout.align(), new_size) }
}
pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) {
unsafe { __rust_dealloc(ptr, layout.size(), layout.align()) }
}
pub unsafe fn alloc(layout: Layout) -> *mut u8 {
unsafe { __rust_alloc(layout.size(), layout.align()) }
}
所以就可以看两个Global核心的方法了，代码的理解在注释上面：�
注意到这里，实际上内存的起始地址是在这里被分配的。另外，注意，layout完成了舍入大小等的控制并防止了溢出，alloct这里完成了起始地址的分配，后面的slice的分配意味着实际上的内存序列不是在alloc中完成的，而是在这里完成的，alloc只是给到了起始地址以及安全的一块内存。
#[cfg(not(test))]
impl Global {
#[inline]
// 分配内存的核心方法，接收参数为布局以及是否分配零内存，返回包装好的内存地址
fn alloc_impl(&self, layout: Layout, zeroed: bool) -> Result<NonNull<[u8]>, AllocError> {
match layout.size() {
// 如果是layout的大小为0的化，通过align直接分配地址，align为8则得到0x8，至于这个方法，看后面
// 强行转换为了一个slice
0 => Ok(NonNull::slice_from_raw_parts(layout.dangling(), 0)),
// SAFETY: `layout` is non-zero in size,
size => unsafe {
// 分配内存得到指向内存起始地址的指针之后，只需要将其看为一个无限长的slice，然后从中取出有限的size长度的slice存储为一个[u8]slice，达到实现分配并表示内存的目的。而此时，我们分配的整个内存都是存储在了这个NonNull中
let raw_ptr = if zeroed { alloc_zeroed(layout) } else { alloc(layout) };
let ptr = NonNull::new(raw_Nptr).ok_or(AllocError)?;
Ok(NonNull::slice_from_raw_parts(ptr, size))
},
}
}
// SAFETY: Same as `Allocator::grow`
#[inline]
unsafe fn grow_impl(
&self,
ptr: NonNull<u8>,
old_layout: Layout,
new_layout: Layout,
zeroed: bool,
) -> Result<NonNull<[u8]>, AllocError> {
debug_assert!(
new_layout.size() >= old_layout.size(),
"`new_layout.size()` must be greater than or equal to `old_layout.size()`"
);
match old_layout.size() {
0 => self.alloc_impl(new_layout, zeroed),
// SAFETY: `new_size` is non-zero as `old_size` is greater than or equal to `new_size`
// as required by safety conditions. Other conditions must be upheld by the caller
// 如果变化后的内存布局中，align的大小相同的时候，只需要
old_size if old_layout.align() == new_layout.align() => unsafe {
let new_size = new_layout.size();
// `realloc` probably checks for `new_size >= old_layout.size()` or something similar.
// 确保新分配的内存比原来的大
intrinsics::assume(new_size >= old_layout.size());
// 调用重新分配的工具方法，在原本的内存上面进行分配
let raw_ptr = realloc(ptr.as_ptr(), old_layout, new_size);
let ptr = NonNull::new(raw_ptr).ok_or(AllocError)?;
// 注意这里，如果是0的话，把新分配的内存全写为0，add是类似于offset的偏移
if zeroed {
raw_ptr.add(old_size).write_bytes(0, new_size - old_size);
}
// 返回新的内存起始地址
Ok(NonNull::slice_from_raw_parts(ptr, new_size))
},
// SAFETY: because `new_layout.size()` must be greater than or equal to `old_size`,
// both the old and new memory allocation are valid for reads and writes for `old_size`
// bytes. Also, because the old allocation wasn't yet deallocated, it cannot overlap
// `new_ptr`. Thus, the call to `copy_nonoverlapping` is safe. The safety contract
// for `dealloc` must be upheld by the caller.
old_size => unsafe {
// 如果align不一样，就直接分配新的，并把旧的写过来
let new_ptr = self.alloc_impl(new_layout, zeroed)?;
// 这个方法很有意思，确保了使用旧的内存写入新的内存的时候，保证了新的内存中与旧的内存不重叠，
// 比如从左往右写，如果新的内存中左边有旧的内存，那么写入的时候会产生覆盖
ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), old_size);
self.deallocate(ptr, old_layout);
Ok(new_ptr)
},
}
}
}
注意其中关于NonNull的一些疑问在这里：
fn main() {
let raw_ptr = Layout::for_value(&ptr);
println!("为ptr分配的内存布局为：{:?}", raw_ptr);
let raw_ptr = unsafe { alloc(raw_ptr) };
println!("{:#?}", raw_ptr);
let ptr = NonNull::new(raw_ptr).unwrap();
println!("{:?}", ptr);
let res = NonNull::slice_from_raw_parts(ptr, 3);
println!("{:?}", res);
}
// 输出
为ptr分配的内存布局为：Layout { size_: 8, align_: 8 }
0x0000561e75f3ead0
0x561e75f3ead0
0x561e75f3ead0
这段代码对于理解上面的Global allocator很重要，关键是
- NonNull存储的是指向类型T的指针。我们得到一个layout之后会有一个布局，根据此布局进行内存分配可以得到一个指针，这个指针是
*mut u8，即我们的raw_ptr指向了一个u8的类型。那么使用NonNull包装起来之后，得到的即为一个指向分配内存的起始位置的指针，而内存是一个字节一个字节的描述的。 - 具体分配的内存的大小就是最后的方法，我们获取了一个来自于起始地址的slice。即，最开始分配的内存是一个起始地址来描述的，没有描述具体这个地址要到多远去，可能是无限远，而使用这个方法之后，NonNull还是那个起始地址，但是指向的空间变成了一个slice，存储了以字节描述的一串地址。
- 既然指向的空间是一个slice，那么这一串slice的内存就是我们能够使用的数组的内存大小，不知道底层是不是连续的内存，但是但从Global中看感觉是连续的哈哈哈哈哈
到这里之后，Global的分配的原理就没有其它重要的内容了，具体的分配、解分配、扩大以及缩小都是对上面四个核心编译器方法的再包装。
那么下一个问题就是RawVec中是如何使用到了我们的Global来进行内存分配的呢？
RawVec:Vec的底层实现
RawVec的内存分配
主要逻辑为：
因此核心的方法就是allocate_in:
#[cfg(not(no_global_oom_handling))]
// 描述了两种内存的分配方式
enum AllocInit {
/// The contents of the new memory are uninitialized.
Uninitialized,
/// The new memory is guaranteed to be zeroed.
Zeroed,
}
#[cfg(not(no_global_oom_handling))]
// 分配内存为capacity大小的，根据alloc分配器的，AllocInit描述为是否需要初始化为0的
fn allocate_in(capacity: usize, init: AllocInit, alloc: A) -> Self {
if mem::size_of::<T>() == 0 {
// new_in看下一部分
Self::new_in(alloc)
} else {
// We avoid `unwrap_or_else` here because it bloats the amount of
// LLVM IR generated.这是为了编译器级的优化
let layout = match Layout::array::<T>(capacity) {
Ok(layout) => layout,
Err(_) => capacity_overflow(),
};
// 守卫方法，确保了跨平台的安全性，实现在下面
match alloc_guard(layout.size()) {
Ok(_) => {}
Err(_) => capacity_overflow(),
}
// 调用分配器，进行内存分配，注意这里返回的是一个Result包裹的NonNull<[u8]>，即一个slice的起始地址
let result = match init {
AllocInit::Uninitialized => alloc.allocate(layout),
AllocInit::Zeroed => alloc.allocate_zeroed(layout),
};
// 解开Rsult并进行安全检查
let ptr = match result {
Ok(ptr) => ptr,
Err(_) => handle_alloc_error(layout),
};
// Allocators currently return a `NonNull<[u8]>` whose length
// matches the size requested. If that ever changes, the capacity
// here should change to `ptr.len() / mem::size_of::<T>()`.
Self {
ptr: unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) },
cap: capacity,
alloc,
}
}
}
// We need to guarantee the following:
// * We don't ever allocate `> isize::MAX` byte-size objects.
// * We don't overflow `usize::MAX` and actually allocate too little.
//
// On 64-bit we just need to check for overflow since trying to allocate
// `> isize::MAX` bytes will surely fail. On 32-bit and 16-bit we need to add
// an extra guard for this in case we're running on a platform which can use
// all 4GB in user-space, e.g., PAE or x32.
#[inline]
// 注意，分配的内存的大小最大不是usize的最大寻址空间的大小，而是isize的
fn alloc_guard(alloc_size: usize) -> Result<(), TryReserveError> {
if usize::BITS < 64 && alloc_size > isize::MAX as usize {
Err(CapacityOverflow.into())
} else {
Ok(())
}
}
这里就可以比较清晰的看见是如何通过allocator进行内存分配的了，但是有一个例外的情况，即我们通过new来进行创建的时候实际上是没有进行内存分配的：
/// Like `new`, but parameterized over the choice of allocator for
/// the returned `RawVec`.
#[rustc_allow_const_fn_unstable(const_fn)]
pub const fn new_in(alloc: A) -> Self {
// `cap: 0` means "unallocated". zero-sized types are ignored.
// 注意这里，我们只是创建了一个well-aligned的地址，但是没有内存大小
Self { ptr: Unique::dangling(), cap: 0, alloc }
}
// 而new，只不过是使用了Global
/// Creates the biggest possible `RawVec` (on the system heap)
/// without allocating. If `T` has positive size, then this makes a
/// `RawVec` with capacity `0`. If `T` is zero-sized, then it makes a
/// `RawVec` with capacity `usize::MAX`. Useful for implementing
/// delayed allocation.
#[must_use]
pub const fn new() -> Self {
Self::new_in(Global)
}
注意到文档中的关键句：Creates the biggest possibleRawVec(on the system heap)，看似是没有分配大小的，实际上根据类型T分了情况：
- 如果
T的大小是正的，即该类型有大小，那么创建的RawVec<T>即为大小为0 - 但是
T是没有大小的话，那么RawVec<T>大小为能够分配的最大
不太能理解为什么这么干，留个坑，说法是Useful for implementing delayed allocation
这个的实现主要是通过Unique::dangling()实现：
/// Creates a new `Unique` that is dangling, but well-aligned.
///
/// This is useful for initializing types which lazily allocate, like
/// `Vec::new` does.
///
/// Note that the pointer value may potentially represent a valid pointer to
/// a `T`, which means this must not be used as a "not yet initialized"
/// sentinel value. 注意：Types that lazily allocate must track initialization by
/// some other means.
#[must_use]
#[inline]
pub const fn dangling() -> Self {
// SAFETY: mem::align_of() returns a valid, non-null pointer. The
// conditions to call new_unchecked() are thus respected.
unsafe { Unique::new_unchecked(mem::align_of::<T>() as *mut T) }
}
内存的grow以及shrink
主要过程如下：
grow的关键在于grow_amortized以及finish_grow：
finsh_grow的关键在于
- 他不是
T的泛型而是A的，意味着主要是取决与分配器的性能 - 检查了grow前后的align相同之后，直接调用alloc的方法进行分配
`` // This function is outsideRawVecto minimize compile times. See the comment // aboveRawVec::grow_amortizedfor details. (TheAparameter isn't // significant, because the number of differentAtypes seen in practice is // much smaller than the number ofT` types.)
[inline(never)]
fn finishgrow(
new_layout: Result
alloc_guard(new_layout.size())?;
let memory = if let Some((ptr, old_layout)) = current_memory {
debug_assert_eq!(old_layout.align(), new_layout.align());
unsafe {
// The allocator checks for alignment equality
// 实际上的分配实现
intrinsics::assume(old_layout.align() == new_layout.align());
alloc.grow(ptr, old_layout, new_layout)
}
} else {
alloc.allocate(new_layout)
};
memory.map_err(|_| AllocError { layout: new_layout, non_exhaustive: () }.into())
}
但是在包装成为`grow_amortized`后，就多了两步和类型有关的检查：
1. 防止加法溢出之后，检查新需要的大小与原容量2倍大小的比较
1. 比较`MIN_NON_ZERO_CAP`
// This method is usually instantiated many times. So we want it to be as
// small as possible, to improve compile times. But we also want as much of
// its contents to be statically computable as possible, to make the
// generated code run faster. Therefore, this method is carefully written
// so that all of the code that depends on T is within it, while as much
// of the code that doesn’t depend on T as possible is in functions that
// are non-generic over T.
fn grow_amortized(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
// This is ensured by the calling contexts.
debug_assert!(additional > 0);
if mem::size_of::<T>() == 0 {
// Since we return a capacity of `usize::MAX` when `elem_size` is
// 0, getting to here necessarily means the `RawVec` is overfull.
return Err(CapacityOverflow.into());
}
// Nothing we can really do about these checks, sadly.
// 检查溢出
let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;
// This guarantees exponential growth. The doubling cannot overflow
// because `cap <= isize::MAX` and the type of `cap` is `usize`.
// 主要比grow_exact多的部分
let cap = cmp::max(self.cap * 2, required_cap);
let cap = cmp::max(Self::MIN_NON_ZERO_CAP, cap);
let new_layout = Layout::array::<T>(cap);
// `finish_grow` is non-generic over `T`.
let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?;
self.set_ptr_and_cap(ptr, cap);
Ok(())
}
对于比较`MIN_NON_ZERO_CAP`：<br />目的是为了确保vec不会很小，很tiny，文档中表示过于小的vec是愚蠢的
// Tiny Vecs are dumb. Skip to:
// - 8 if the element size is 1, because any heap allocators is likely
// to round up a request of less than 8 bytes to at least 8 bytes.
// - 4 if elements are moderate-sized (<= 1 KiB).
// - 1 otherwise, to avoid wasting too much space for very short Vecs.
pub(crate) const MIN_NON_ZERO_CAP: usize = if mem::size_of::
最后的实现就是reverse系列方法：<br />注意采用了一种内置函数的方式，保证了
[cfg(not(no_global_oom_handling))]
[inline]
pub fn reserve(&mut self, len: usize, additional: usize) { // Callers expect this function to be very cheap when there is already sufficient capacity. // Therefore, we move all the resizing and error-handling logic from grow_amortized and // handle_reserve behind a call, while making sure that this function is likely to be // inlined as just a comparison and a call if the comparison fails.
#[cold]
fn do_reserve_and_handle<T, A: Allocator>(
slf: &mut RawVec<T, A>,
len: usize,
additional: usize,
) {
// 抓取grow_amortized中出现的错误，比如溢出、内存不够啥的
handle_reserve(slf.grow_amortized(len, additional));
}
if self.needs_to_grow(len, additional) {
do_reserve_and_handle(self, len, additional);
}
}
相比来说shrink简单了许多：
fn shrink(&mut self, cap: usize) -> Result<(), TryReserveError> { assert!(cap <= self.capacity(), “Tried to shrink to a larger capacity”);
let (ptr, layout) = if let Some(mem) = self.current_memory() { mem } else { return Ok(()) };
let new_size = cap * mem::size_of::<T>();
let ptr = unsafe {
// 重新分配布局
let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
// 调用分配器进行重新分配
self.alloc
.shrink(ptr, layout, new_layout)
.map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })?
};
self.set_ptr_and_cap(ptr, cap);
Ok(())
} ```
若有收获，就点个赞吧
0 人点赞
