在没有 malloc、brk 或 mmap 的情况下，BareMetalOS 如何在 Assembly 中分配内存？
How is BareMetalOS allocating memory in Assembly without malloc, brk, or mmap?
作为学习实验，我有兴趣在程序集中创建哈希表（OSX 上的 NASM 中的 x86-64）。要求之一是能够动态分配/管理内存。
在浏览了许多关于如何在汇编中分配内存的资源后，他们中的大多数推荐 brk 或 mmap 系统调用。我还没有确切地了解它们是如何工作的，因为我在 BareMetal-OS 中发现了另一个内存分配的实现，它不使用任何系统调用（在下面复制了它们的代码）。
我的问题是，他们是怎么做到的？您能否为没有系统编程背景且刚接触汇编的人解释执行内存分配的汇编中的相关指令？之所以想了解如何在汇编中实现内存分配是为了能够在汇编中实现哈希表。
刚开始接触汇编（我主要做 JavaScript），还没有找到任何关于汇编内存分配的详细资源，我不知道从哪里开始。这对你来说可能是显而易见的，但你有背景，而我没有。过去一两周我有 done some assembly，所以我了解有关寄存器 mov 和跳转命令的基础知识，但还不了解他们为实现这些内存内容所做的额外工作。我的想法是，如果他们可以在没有 brk 或 mmap 的情况下在汇编中实现内存分配，那么我想那样做，因为那样我真的是在没有任何系统层的情况下直接操纵内存，而且看起来就像你真的可以微调东西一样。
这是他们从 GitHub 复制的代码：
https://github.com/ReturnInfinity/BareMetal-OS/blob/master/os/syscalls/memory.asm
# =============================================================================
# BareMetal -- a 64-bit OS written in Assembly for x86-64 systems
# Copyright (C) 2008-2014 Return Infinity -- see LICENSE.TXT
#
# Memory functions
# =============================================================================
align 16
db 'DEBUG: MEMORY '
align 16
# -----------------------------------------------------------------------------
# os_mem_allocate -- Allocates the requested number of 2 MiB pages
# IN: RCX = Number of pages to allocate
# OUT: RAX = Starting address (Set to 0 on failure)
# This function will only allocate continuous pages
os_mem_allocate:
push rsi
push rdx
push rbx
cmp rcx, 0
je os_mem_allocate_fail # At least 1 page must be allocated
# Here, we'll load the last existing page of memory in RSI.
# RAX and RSI instructions are purposefully interleaved.
xor rax, rax
mov rsi, os_MemoryMap # First available memory block
mov eax, [os_MemAmount] # Total memory in MiB from a double-word
mov rdx, rsi # Keep os_MemoryMap unmodified for later in RDX
shr eax, 1 # Divide actual memory by 2
sub rsi, 1
std # Set direction flag to backward
add rsi, rax # RSI now points to the last page
os_mem_allocate_start: # Find a free page of memory, from the end.
mov rbx, rcx # RBX is our temporary counter
os_mem_allocate_nextpage:
lodsb
cmp rsi, rdx # We have hit the start of the memory map, no more free pages
je os_mem_allocate_fail
cmp al, 1
jne os_mem_allocate_start # Page is taken, start counting from scratch
dec rbx # We found a page! Any page left to find?
jnz os_mem_allocate_nextpage
os_mem_allocate_mark: # We have a suitable free series of pages. Allocate them.
cld # Set direction flag to forward
xor rdi, rsi # We swap rdi and rsi to keep rdi contents.
xor rsi, rdi
xor rdi, rsi
# Instructions are purposefully swapped at some places here to avoid
# direct dependencies line after line.
push rcx # Keep RCX as is for the 'rep stosb' to come
add rdi, 1
mov al, 2
mov rbx, rdi # RBX points to the starting page
rep stosb
mov rdi, rsi # Restoring RDI
sub rbx, rdx # RBX now contains the memory page number
pop rcx # Restore RCX
# Only dependency left is between the two next lines.
shl rbx, 21 # Quick multiply by 2097152 (2 MiB) to get the starting memory address
mov rax, rbx # Return the starting address in RAX
jmp os_mem_allocate_end
os_mem_allocate_fail:
cld # Set direction flag to forward
xor rax, rax # Failure so set RAX to 0 (No pages allocated)
os_mem_allocate_end:
pop rbx
pop rdx
pop rsi
ret
# -----------------------------------------------------------------------------
# -----------------------------------------------------------------------------
# os_mem_release -- Frees the requested number of 2 MiB pages
# IN: RAX = Starting address
# RCX = Number of pages to free
# OUT: RCX = Number of pages freed
os_mem_release:
push rdi
push rcx
push rax
shr rax, 21 # Quick divide by 2097152 (2 MiB) to get the starting page number
add rax, os_MemoryMap
mov rdi, rax
mov al, 1
rep stosb
pop rax
pop rcx
pop rdi
ret
# -----------------------------------------------------------------------------
# -----------------------------------------------------------------------------
# os_mem_get_free -- Returns the number of 2 MiB pages that are available
# IN: Nothing
# OUT: RCX = Number of free 2 MiB pages
os_mem_get_free:
push rsi
push rbx
push rax
mov rsi, os_MemoryMap
xor rcx, rcx
xor rbx, rbx
os_mem_get_free_next:
lodsb
inc rcx
cmp rcx, 65536
je os_mem_get_free_end
cmp al, 1
jne os_mem_get_free_next
inc rbx
jmp os_mem_get_free_next
os_mem_get_free_end:
mov rcx, rbx
pop rax
pop rbx
pop rsi
ret
# -----------------------------------------------------------------------------
# -----------------------------------------------------------------------------
# os_mem_copy -- Copy a number of bytes
# IN: RSI = Source address
# RDI = Destination address
# RCX = Number of bytes to copy
# OUT: Nothing, all registers preserved
os_mem_copy:
push rdi
push rsi
push rcx
rep movsb # Optimize this!
pop rcx
pop rsi
pop rdi
ret
# -----------------------------------------------------------------------------
# =============================================================================
# EOF
另请注意，我已经阅读了很多关于在 C 中创建哈希表的资源，我复制了其中之一 here（其中包含 C 代码和相应的程序集）。然而，几乎所有的 C 示例都使用 malloc，我想避免这种情况。我正在尝试完全不依赖 C 来学习汇编。
此外，this resource from Quora 有助于指出 malloc.c 源代码中使用 brk 和 mmap 的位置。但是，我还没有研究它，因为发现了 BareMetal-OS memory.asm 代码，它似乎甚至没有使用那些系统调用就分配了内存。因此问题来了，他们是怎么做到的？你能解释一下他们汇编中执行内存分配的相关指令吗？
更新
这本书帮助解释了几乎所有关于 mmap 和 brk 内存内部结构的内容，都是在操作系统实现领域。 http://www.amazon.com/Modern-Operating-Systems-4th-Edition/dp/013359162X
为了管理内存，您的代码需要 "own" 一些内存。问题是在任何有操作系统的机器上，操作系统拥有 all 内存。所以你的代码必须向操作系统请求一些内存，它可以用 brk，或 mmap，或 malloc 来完成。
例如，如果你想用汇编写一个内存管理器，而你有一台4GB内存的机器，那么在malloc开头请求1GB内存也不是没有道理的程序，然后以您喜欢的方式管理该内存。
来自 BareMetal-OS 的汇编代码确实不适用于您的情况，因为 BareMetal 是 操作系统，因此不需要向任何人询问记忆。它已经拥有所有的内存，并且可以随心所欲地管理它。
根据其他评论和答案，BareMetal-OS 可以以这种方式实现分配的原因是因为它依赖于发布的代码或通用汇编编译器中不存在的几个附加函数调用，例如如NASM等。具体来说，贴出的代码中依赖的调用是：
os_MemoryMap
os_MemAmount
它们要么是 BareMetal-OS 特定的 调用，要么可能是特定于发布代码的人使用的某些内存管理器的调用。如果没有一些外部库（例如 libc 或内存管理器库），您将只能使用 brk 指令。 （45 on x86 和 12 on x86_64）希望这能为这个谜题增加另一块。祝你好运。
此 post 解释了 os_mem_allocate 函数的汇编代码。基本思想是以 2MB 块分配内存。有一个 65536 字节 (os_MemoryMap) 的数组，用于跟踪哪些块是空闲的，哪些块已被使用。值 1 是空闲块，值 2 是已用块。可管理的内存总量为 64K * 2MB = 128GB。由于大多数机器没有那么多内存，因此还有另一个变量 (os_MemAmount) 指示机器的内存大小（以 MB 为单位）。
os_mem_allocate 函数的输入是一个计数，即要分配多少个 2MB 块。该函数旨在仅分配连续的块。例如，如果输入请求为 3，则函数尝试分配 6MB 内存，并通过在数组中连续搜索三个 1 来实现。函数的 return 值是指向已分配内存的指针，如果无法满足请求，则为 0。
输入计数在 rcx 中传递。该代码验证请求是针对非零数量的块。输入 0 会导致 return 值为 0。
os_mem_allocate:
push rsi # save some registers
push rdx
push rbx
cmp rcx, 0 # Is the count 0?
je os_mem_allocate_fail # If YES, then return 0
代码执行迂回计算以将 rsi 指向 65536 字节数组中的最后一个可用字节。以下片段的最后两行是最有趣的。设置方向标志意味着后续 lodsb 指令将递减 rsi。当然，将 rsi 指向数组中的最后一个可用字节是计算的重点。
xor rax, rax
mov rsi, os_MemoryMap # Get the address of the 65536 byte array into RSI
mov eax, [os_MemAmount] # Get the memory size in MB into EAX
mov rdx, rsi # Keep os_MemoryMap in RDX for later use
shr eax, 1 # Divide by 2 because os_MemAmount is in MB, but chunks are 2MB
sub rsi, 1 # in C syntax, we're calculating &array[amount/2-1], which is the address of the last usable byte in the array
std # Set direction flag to backward
add rsi, rax # RSI now points to the last byte
接下来的代码有一个循环，用于搜索 N 个连续的空闲块，其中 N 是传递给 rcx 中的函数的计数。循环向后扫描数组以查找一行中的 N 个 1。如果 rbx 达到 0，则循环成功。只要循环在数组中找到 2，它就会将 rbx 重置回 N。
os_mem_allocate_start:
mov rbx, rcx # RBX is the number of contiguous free chunks we need to find
os_mem_allocate_nextpage:
lodsb # read a byte into AL, and decrement RSI
cmp rsi, rdx # if RSI has reached the beginning of the array
je os_mem_allocate_fail # then the loop has failed
cmp al, 1 # Is the chunk free?
jne os_mem_allocate_start # If NO, we need to restart the count
dec rbx # If YES, decrement the count
jnz os_mem_allocate_nextpage # If the count reaches zero we've succeeded, otherwise continue looping
此时代码已找到足够的连续块来满足请求，因此现在它通过将数组中的字节设置为 2 将所有块标记为 "used"。方向标志设置为向前，以便后续 stosb 指令将递增 rdi。
os_mem_allocate_mark: # We have a suitable free series of chunks, mark them as used
cld # Set direction flag to forward
xor rdi, rsi # We swap RDI and RSI to keep RDI contents, but
xor rsi, rdi # more importantly we want RDI to point to the
xor rdi, rsi # location in the array where we want to write 2's
push rcx # Save RCX since 'rep stosb' will modify it
add rdi, 1 # the previous loop decremented RSI too many times
mov al, 2 # the value 2 indicates a "used" chunk
mov rbx, rdi # RBX is going to be used to calculate the return value
rep stosb # store some 2's in the array, using the count in RCX
mov rdi, rsi # Restoring RDI
最后，该函数需要向调用者提供一个指向 return 的指针。
sub rbx, rdx # RBX is now an index into the 65536 byte array
pop rcx # Restore RCX
shl rbx, 21 # Multiply by 2MB to convert the index to a pointer
mov rax, rbx # Return the pointer in RAX
jmp os_mem_allocate_end
下一个代码片段通过将 return 值设置为 0 来处理错误。清除方向标志很重要，因为按照惯例方向是向前的。
os_mem_allocate_fail:
cld # Set direction flag to forward
xor rax, rax # Failure so set RAX to 0 (No pages allocated)
最后，恢复寄存器和return指针。
os_mem_allocate_end:
pop rbx
pop rdx
pop rsi
ret
作为学习实验，我有兴趣在程序集中创建哈希表（OSX 上的 NASM 中的 x86-64）。要求之一是能够动态分配/管理内存。
在浏览了许多关于如何在汇编中分配内存的资源后，他们中的大多数推荐 brk 或 mmap 系统调用。我还没有确切地了解它们是如何工作的，因为我在 BareMetal-OS 中发现了另一个内存分配的实现，它不使用任何系统调用（在下面复制了它们的代码）。
我的问题是，他们是怎么做到的？您能否为没有系统编程背景且刚接触汇编的人解释执行内存分配的汇编中的相关指令？之所以想了解如何在汇编中实现内存分配是为了能够在汇编中实现哈希表。
刚开始接触汇编（我主要做 JavaScript），还没有找到任何关于汇编内存分配的详细资源，我不知道从哪里开始。这对你来说可能是显而易见的，但你有背景，而我没有。过去一两周我有 done some assembly，所以我了解有关寄存器 mov 和跳转命令的基础知识，但还不了解他们为实现这些内存内容所做的额外工作。我的想法是，如果他们可以在没有 brk 或 mmap 的情况下在汇编中实现内存分配，那么我想那样做，因为那样我真的是在没有任何系统层的情况下直接操纵内存，而且看起来就像你真的可以微调东西一样。
这是他们从 GitHub 复制的代码：
https://github.com/ReturnInfinity/BareMetal-OS/blob/master/os/syscalls/memory.asm
# =============================================================================
# BareMetal -- a 64-bit OS written in Assembly for x86-64 systems
# Copyright (C) 2008-2014 Return Infinity -- see LICENSE.TXT
#
# Memory functions
# =============================================================================
align 16
db 'DEBUG: MEMORY '
align 16
# -----------------------------------------------------------------------------
# os_mem_allocate -- Allocates the requested number of 2 MiB pages
# IN: RCX = Number of pages to allocate
# OUT: RAX = Starting address (Set to 0 on failure)
# This function will only allocate continuous pages
os_mem_allocate:
push rsi
push rdx
push rbx
cmp rcx, 0
je os_mem_allocate_fail # At least 1 page must be allocated
# Here, we'll load the last existing page of memory in RSI.
# RAX and RSI instructions are purposefully interleaved.
xor rax, rax
mov rsi, os_MemoryMap # First available memory block
mov eax, [os_MemAmount] # Total memory in MiB from a double-word
mov rdx, rsi # Keep os_MemoryMap unmodified for later in RDX
shr eax, 1 # Divide actual memory by 2
sub rsi, 1
std # Set direction flag to backward
add rsi, rax # RSI now points to the last page
os_mem_allocate_start: # Find a free page of memory, from the end.
mov rbx, rcx # RBX is our temporary counter
os_mem_allocate_nextpage:
lodsb
cmp rsi, rdx # We have hit the start of the memory map, no more free pages
je os_mem_allocate_fail
cmp al, 1
jne os_mem_allocate_start # Page is taken, start counting from scratch
dec rbx # We found a page! Any page left to find?
jnz os_mem_allocate_nextpage
os_mem_allocate_mark: # We have a suitable free series of pages. Allocate them.
cld # Set direction flag to forward
xor rdi, rsi # We swap rdi and rsi to keep rdi contents.
xor rsi, rdi
xor rdi, rsi
# Instructions are purposefully swapped at some places here to avoid
# direct dependencies line after line.
push rcx # Keep RCX as is for the 'rep stosb' to come
add rdi, 1
mov al, 2
mov rbx, rdi # RBX points to the starting page
rep stosb
mov rdi, rsi # Restoring RDI
sub rbx, rdx # RBX now contains the memory page number
pop rcx # Restore RCX
# Only dependency left is between the two next lines.
shl rbx, 21 # Quick multiply by 2097152 (2 MiB) to get the starting memory address
mov rax, rbx # Return the starting address in RAX
jmp os_mem_allocate_end
os_mem_allocate_fail:
cld # Set direction flag to forward
xor rax, rax # Failure so set RAX to 0 (No pages allocated)
os_mem_allocate_end:
pop rbx
pop rdx
pop rsi
ret
# -----------------------------------------------------------------------------
# -----------------------------------------------------------------------------
# os_mem_release -- Frees the requested number of 2 MiB pages
# IN: RAX = Starting address
# RCX = Number of pages to free
# OUT: RCX = Number of pages freed
os_mem_release:
push rdi
push rcx
push rax
shr rax, 21 # Quick divide by 2097152 (2 MiB) to get the starting page number
add rax, os_MemoryMap
mov rdi, rax
mov al, 1
rep stosb
pop rax
pop rcx
pop rdi
ret
# -----------------------------------------------------------------------------
# -----------------------------------------------------------------------------
# os_mem_get_free -- Returns the number of 2 MiB pages that are available
# IN: Nothing
# OUT: RCX = Number of free 2 MiB pages
os_mem_get_free:
push rsi
push rbx
push rax
mov rsi, os_MemoryMap
xor rcx, rcx
xor rbx, rbx
os_mem_get_free_next:
lodsb
inc rcx
cmp rcx, 65536
je os_mem_get_free_end
cmp al, 1
jne os_mem_get_free_next
inc rbx
jmp os_mem_get_free_next
os_mem_get_free_end:
mov rcx, rbx
pop rax
pop rbx
pop rsi
ret
# -----------------------------------------------------------------------------
# -----------------------------------------------------------------------------
# os_mem_copy -- Copy a number of bytes
# IN: RSI = Source address
# RDI = Destination address
# RCX = Number of bytes to copy
# OUT: Nothing, all registers preserved
os_mem_copy:
push rdi
push rsi
push rcx
rep movsb # Optimize this!
pop rcx
pop rsi
pop rdi
ret
# -----------------------------------------------------------------------------
# =============================================================================
# EOF
另请注意，我已经阅读了很多关于在 C 中创建哈希表的资源，我复制了其中之一 here（其中包含 C 代码和相应的程序集）。然而，几乎所有的 C 示例都使用 malloc，我想避免这种情况。我正在尝试完全不依赖 C 来学习汇编。
此外，this resource from Quora 有助于指出 malloc.c 源代码中使用 brk 和 mmap 的位置。但是，我还没有研究它，因为发现了 BareMetal-OS memory.asm 代码，它似乎甚至没有使用那些系统调用就分配了内存。因此问题来了，他们是怎么做到的？你能解释一下他们汇编中执行内存分配的相关指令吗？
更新
这本书帮助解释了几乎所有关于 mmap 和 brk 内存内部结构的内容，都是在操作系统实现领域。 http://www.amazon.com/Modern-Operating-Systems-4th-Edition/dp/013359162X
为了管理内存，您的代码需要 "own" 一些内存。问题是在任何有操作系统的机器上，操作系统拥有 all 内存。所以你的代码必须向操作系统请求一些内存，它可以用 brk，或 mmap，或 malloc 来完成。
例如，如果你想用汇编写一个内存管理器，而你有一台4GB内存的机器，那么在malloc开头请求1GB内存也不是没有道理的程序，然后以您喜欢的方式管理该内存。
来自 BareMetal-OS 的汇编代码确实不适用于您的情况，因为 BareMetal 是 操作系统，因此不需要向任何人询问记忆。它已经拥有所有的内存，并且可以随心所欲地管理它。
根据其他评论和答案，BareMetal-OS 可以以这种方式实现分配的原因是因为它依赖于发布的代码或通用汇编编译器中不存在的几个附加函数调用，例如如NASM等。具体来说，贴出的代码中依赖的调用是：
os_MemoryMap
os_MemAmount
它们要么是 BareMetal-OS 特定的 调用，要么可能是特定于发布代码的人使用的某些内存管理器的调用。如果没有一些外部库（例如 libc 或内存管理器库），您将只能使用 brk 指令。 （45 on x86 和 12 on x86_64）希望这能为这个谜题增加另一块。祝你好运。
此 post 解释了 os_mem_allocate 函数的汇编代码。基本思想是以 2MB 块分配内存。有一个 65536 字节 (os_MemoryMap) 的数组，用于跟踪哪些块是空闲的，哪些块已被使用。值 1 是空闲块，值 2 是已用块。可管理的内存总量为 64K * 2MB = 128GB。由于大多数机器没有那么多内存，因此还有另一个变量 (os_MemAmount) 指示机器的内存大小（以 MB 为单位）。
os_mem_allocate 函数的输入是一个计数，即要分配多少个 2MB 块。该函数旨在仅分配连续的块。例如，如果输入请求为 3，则函数尝试分配 6MB 内存，并通过在数组中连续搜索三个 1 来实现。函数的 return 值是指向已分配内存的指针，如果无法满足请求，则为 0。
输入计数在 rcx 中传递。该代码验证请求是针对非零数量的块。输入 0 会导致 return 值为 0。
os_mem_allocate:
push rsi # save some registers
push rdx
push rbx
cmp rcx, 0 # Is the count 0?
je os_mem_allocate_fail # If YES, then return 0
代码执行迂回计算以将 rsi 指向 65536 字节数组中的最后一个可用字节。以下片段的最后两行是最有趣的。设置方向标志意味着后续 lodsb 指令将递减 rsi。当然，将 rsi 指向数组中的最后一个可用字节是计算的重点。
xor rax, rax
mov rsi, os_MemoryMap # Get the address of the 65536 byte array into RSI
mov eax, [os_MemAmount] # Get the memory size in MB into EAX
mov rdx, rsi # Keep os_MemoryMap in RDX for later use
shr eax, 1 # Divide by 2 because os_MemAmount is in MB, but chunks are 2MB
sub rsi, 1 # in C syntax, we're calculating &array[amount/2-1], which is the address of the last usable byte in the array
std # Set direction flag to backward
add rsi, rax # RSI now points to the last byte
接下来的代码有一个循环，用于搜索 N 个连续的空闲块，其中 N 是传递给 rcx 中的函数的计数。循环向后扫描数组以查找一行中的 N 个 1。如果 rbx 达到 0，则循环成功。只要循环在数组中找到 2，它就会将 rbx 重置回 N。
os_mem_allocate_start:
mov rbx, rcx # RBX is the number of contiguous free chunks we need to find
os_mem_allocate_nextpage:
lodsb # read a byte into AL, and decrement RSI
cmp rsi, rdx # if RSI has reached the beginning of the array
je os_mem_allocate_fail # then the loop has failed
cmp al, 1 # Is the chunk free?
jne os_mem_allocate_start # If NO, we need to restart the count
dec rbx # If YES, decrement the count
jnz os_mem_allocate_nextpage # If the count reaches zero we've succeeded, otherwise continue looping
此时代码已找到足够的连续块来满足请求，因此现在它通过将数组中的字节设置为 2 将所有块标记为 "used"。方向标志设置为向前，以便后续 stosb 指令将递增 rdi。
os_mem_allocate_mark: # We have a suitable free series of chunks, mark them as used
cld # Set direction flag to forward
xor rdi, rsi # We swap RDI and RSI to keep RDI contents, but
xor rsi, rdi # more importantly we want RDI to point to the
xor rdi, rsi # location in the array where we want to write 2's
push rcx # Save RCX since 'rep stosb' will modify it
add rdi, 1 # the previous loop decremented RSI too many times
mov al, 2 # the value 2 indicates a "used" chunk
mov rbx, rdi # RBX is going to be used to calculate the return value
rep stosb # store some 2's in the array, using the count in RCX
mov rdi, rsi # Restoring RDI
最后，该函数需要向调用者提供一个指向 return 的指针。
sub rbx, rdx # RBX is now an index into the 65536 byte array
pop rcx # Restore RCX
shl rbx, 21 # Multiply by 2MB to convert the index to a pointer
mov rax, rbx # Return the pointer in RAX
jmp os_mem_allocate_end
下一个代码片段通过将 return 值设置为 0 来处理错误。清除方向标志很重要，因为按照惯例方向是向前的。
os_mem_allocate_fail:
cld # Set direction flag to forward
xor rax, rax # Failure so set RAX to 0 (No pages allocated)
最后，恢复寄存器和return指针。
os_mem_allocate_end:
pop rbx
pop rdx
pop rsi
ret