memblock算法是linux内核初始化阶段的一个内存分配器（它取代了原来的bootmem算法），实现较为简单。负责page allocator初始化之前的内存管理和分配请求。

分析memblock算法，可以从几点入手：

1. memblock算法初始化；
2. memblock算法管理内存的申请和释放；

memblock算法前的准备：

前面已经分析了linux系统在初始化的过程中，使用int 15中断探知了机器的内存分布图（e820图），其数据是存储在boot_params.e820_map里面，这里面是没有经过整理的数据，杂乱无章，毕竟BIOS没有责任做整理内存的事情，所以这部分事情由系统来实现。那么看一下linux如何实现这部分功能的，这部分功能是在setup_memory_map里面实现的。

该函数在初始化中的调用位置：

start_kernel()

└->setup_arch()

└->setup_memory_map();

函数实现：

【file:/arch/x86/kernel/e820.c】
void __init setup_memory_map(void)
{
    char *who;
 
    who = x86_init.resources.memory_setup();
    memcpy(&e820_saved, &e820, sizeof(struct e820map));
    printk(KERN_INFO "e820: BIOS-provided physical RAM map:\n");
    e820_print_map(who);
}

可以看到实现很简单，先是调用了一个钩子函数，然后将e820保存到e820_saved里面，再往下就是print函数。很明显可以看到关键点在于这个钩子函数的实现，在x86_init.c里面可以找到x86_init该结构体变量的定义：

【file:/arch/x86/kernel/x86_init.c】
struct x86_init_ops x86_init __initdata = {
 
    .resources = {
        .probe_roms = probe_roms,
        .reserve_resources = reserve_standard_io_resources,
        .memory_setup = default_machine_specific_memory_setup,
    },
 
    .mpparse = {
        .mpc_record = x86_init_uint_noop,
        .setup_ioapic_ids = x86_init_noop,
        .mpc_apic_id = default_mpc_apic_id,
        .smp_read_mpc_oem = default_smp_read_mpc_oem,
        .mpc_oem_bus_info = default_mpc_oem_bus_info,
        .find_smp_config = default_find_smp_config,
        .get_smp_config = default_get_smp_config,
    },
 
    .irqs = {
        .pre_vector_init = init_ISA_irqs,
        .intr_init = native_init_IRQ,
        .trap_init = x86_init_noop,
    },
 
    .oem = {
        .arch_setup = x86_init_noop,
        .banner = default_banner,
    },
 
    .paging = {
        .pagetable_init = native_pagetable_init,
    },
 
    .timers = {
        .setup_percpu_clockev = setup_boot_APIC_clock,
        .tsc_pre_init = x86_init_noop,
        .timer_init = hpet_time_init,
        .wallclock_init = x86_init_noop,
    },
 
    .iommu = {
        .iommu_init = iommu_init_noop,
    },
 
    .pci = {
        .init = x86_default_pci_init,
        .init_irq = x86_default_pci_init_irq,
        .fixup_irqs = x86_default_pci_fixup_irqs,
    },
};

由此可以看到该钩子函数挂的是default_machine_specific_memory_setup()。

进一步看一下该函数的实现：

【file:/arch/x86/kernel/e820.c】
char *__init default_machine_specific_memory_setup(void)
{
    char *who = "BIOS-e820";
    u32 new_nr;
    /*
     * Try to copy the BIOS-supplied E820-map.
     *
     * Otherwise fake a memory map; one section from 0k->640k,
     * the next section from 1mb->appropriate_mem_k
     */
    new_nr = boot_params.e820_entries;
    sanitize_e820_map(boot_params.e820_map,
            ARRAY_SIZE(boot_params.e820_map),
            &new_nr);
    boot_params.e820_entries = new_nr;
    if (append_e820_map(boot_params.e820_map, boot_params.e820_entries)
      < 0) {
        u64 mem_size;
 
        /* compare results from other methods and take the greater */
        if (boot_params.alt_mem_k
            < boot_params.screen_info.ext_mem_k) {
            mem_size = boot_params.screen_info.ext_mem_k;
            who = "BIOS-88";
        } else {
            mem_size = boot_params.alt_mem_k;
            who = "BIOS-e801";
        }
 
        e820.nr_map = 0;
        e820_add_region(0, LOWMEMSIZE(), E820_RAM);
        e820_add_region(HIGH_MEMORY, mem_size << 10, E820_RAM);
    }
 
    /* In case someone cares... */
    return who;
}

在这个函数里面，可以看到前面探测到的内存布局信息boot_params.e820_map在这里被使用了。

首先分析一下sanitize_e820_map该函数把e820信息进行了如何处理，函数实现：

【file:/arch/x86/kernel/e820.c】
int __init sanitize_e820_map(struct e820en