1 struct memblock_type {
2     unsigned long cnt;    /* number of regions */
3     unsigned long max;    /* size of the allocated array */
4     phys_addr_t total_size;    /* size of all regions */
5     struct memblock_region *regions;
6     char *name;
7 };

1 struct memblock_type {
2     unsigned long cnt;    /* number of regions */
3     unsigned long max;    /* size of the allocated array */
4     phys_addr_t total_size;    /* size of all regions */
5     struct memblock_region *regions;
6     char *name;
7 };

1 struct memblock_region {
2     phys_addr_t base;
3     phys_addr_t size;
4     unsigned long flags;
5 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
6     int nid;
7 #endif
8 };

 1 void __init_memblock __next_mem_range(u64 *idx, int nid, ulong flags,
 2                       struct memblock_type *type_a,
 3                       struct memblock_type *type_b,
 4                       phys_addr_t *out_start,
 5                       phys_addr_t *out_end, int *out_nid)
 6 {
 7     int idx_a = *idx & 0xffffffff;
 8     int idx_b = *idx >> 32;
 9  
10     if (WARN_ONCE(nid == MAX_NUMNODES,
11     "Usage of MAX_NUMNODES is deprecated. Use NUMA_NO_NODE instead\n"))
12         nid = NUMA_NO_NODE;
13  
14     for (; idx_a < type_a->cnt; idx_a++) {
15         struct memblock_region *m = &type_a->regions[idx_a];
16  
17         phys_addr_t m_start = m->base;
18         phys_addr_t m_end = m->base + m->size;
19         int        m_nid = memblock_get_region_node(m);
20  
21         /* only memory regions are associated with nodes, check it */
22         if (nid != NUMA_NO_NODE && nid != m_nid)
23             continue;
24  
25         /* skip hotpluggable memory regions if needed */
26         if (movable_node_is_enabled() && memblock_is_hotpluggable(m))
27             continue;
28  
29         /* if we want mirror memory skip non-mirror memory regions */
30         if ((flags & MEMBLOCK_MIRROR) && !memblock_is_mirror(m))
31             continue;
32  
33         /* skip nomap memory unless we were asked for it explicitly */
34         if (!(flags & MEMBLOCK_NOMAP) && memblock_is_nomap(m))
35             continue;
36  
37         if (!type_b) {
38             if (out_start)
39                 *out_start = m_start;
40             if (out_end)
41                 *out_end = m_end;
42             if (out_nid)
43                 *out_nid = m_nid;
44             idx_a++;
45             *idx = (u32)idx_a | (u64)idx_b << 32;
46             return;
47         }
48  
49         /* scan areas before each reservation */
50         for (; idx_b < type_b->cnt + 1; idx_b++) {
51             struct memblock_region *r;
52             phys_addr_t r_start;
53             phys_addr_t r_end;
54  
55             r = &type_b->regions[idx_b];
56             r_start = idx_b ? r[-1].base + r[-1].size : 0;
57             r_end = idx_b < type_b->cnt ?
58                 r->base : ULLONG_MAX;
59  
60             /*
61              * if idx_b advanced past idx_a,
62              * break out to advance idx_a
63              */
64             if (r_start >= m_end)
65                 break;
66             /* if the two regions intersect, we‘re done */
67             if (m_start < r_end) {
68                 if (out_start)
69                     *out_start =
70                         max(m_start, r_start);
71                 if (out_end)
72                     *out_end = min(m_end, r_end);
73                 if (out_nid)
74                     *out_nid = m_nid;
75                 /*
76                  * The region which ends first is
77                  * advanced for the next iteration.
78                  */
79                 if (m_end <= r_end)
80                     idx_a++;
81                 else
82                     idx_b++;
83                 *idx = (u32)idx_a | (u64)idx_b << 32;
84                 return;
85             }
86         }
87     }
88  
89     /* signal end of iteration */
90     *idx = ULLONG_MAX;
91 }

 1 void __init_memblock __next_mem_range_rev(u64 *idx, int nid, ulong flags,
 2                       struct memblock_type *type_a,
 3                       struct memblock_type *type_b,
 4                       phys_addr_t *out_start,
 5                       phys_addr_t *out_end, int *out_nid)
 6 {
 7     int idx_a = *idx & 0xffffffff;
 8     int idx_b = *idx >> 32;
 9  
10     if (WARN_ONCE(nid == MAX_NUMNODES, "Usage of MAX_NUMNODES is deprecated. Use NUMA_NO_NODE instead\n"))
11         nid = NUMA_NO_NODE;
12  
13     if (*idx == (u64)ULLONG_MAX) {
14         idx_a = type_a->cnt - 1;
15         if (type_b != NULL)
16             idx_b = type_b->cnt;
17         else
18             idx_b = 0;
19     }
20  
21     for (; idx_a >= 0; idx_a--) {
22         struct memblock_region *m = &type_a->regions[idx_a];
23  
24         phys_addr_t m_start = m->base;
25         phys_addr_t m_end = m->base + m->size;
26         int m_nid = memblock_get_region_node(m);
27  
28         /* only memory regions are associated with nodes, check it */
29         if (nid != NUMA_NO_NODE && nid != m_nid)
30             continue;
31  
32         /* skip hotpluggable memory regions if needed */
33         if (movable_node_is_enabled() && memblock_is_hotpluggable(m))
34             continue;
35  
36         /* if we want mirror memory skip non-mirror memory regions */
37         if ((flags & MEMBLOCK_MIRROR) && !memblock_is_mirror(m))
38             continue;
39  
40         /* skip nomap memory unless we were asked for it explicitly */
41         if (!(flags & MEMBLOCK_NOMAP) && memblock_is_nomap(m))
42             continue;
43  
44         if (!type_b) {
45             if (out_start)
46                 *out_start = m_start;
47             if (out_end)
48                 *out_end = m_end;
49             if (out_nid)
50                 *out_nid = m_nid;
51             idx_a--;
52             *idx = (u32)idx_a | (u64)idx_b << 32;
53             return;
54         }
55  
56         /* scan areas before each reservation */
57         for (; idx_b >= 0; idx_b--) {
58             struct memblock_region *r;
59             phys_addr_t r_start;
60             phys_addr_t r_end;
61  
62             r = &type_b->regions[idx_b];
63             r_start = idx_b ? r[-1].base + r[-1].size : 0;
64             r_end = idx_b < type_b->cnt ?
65                 r->base : ULLONG_MAX;
66             /*
67              * if idx_b advanced past idx_a,
68              * break out to advance idx_a
69              */
70  
71             if (r_end <= m_start)
72                 break;
73             /* if the two regions intersect, we‘re done */
74             if (m_end > r_start) {
75                 if (out_start)
76                     *out_start = max(m_start, r_start);
77                 if (out_end)
78                     *out_end = min(m_end, r_end);
79                 if (out_nid)
80                     *out_nid = m_nid;
81                 if (m_start >= r_start)
82                     idx_a--;
83                 else
84                     idx_b--;
85                 *idx = (u32)idx_a | (u64)idx_b << 32;
86                 return;
87             }
88         }
89     }
90     /* signal end of iteration */
91     *idx = ULLONG_MAX;
92 }

 1 phys_addr_t __init_memblock memblock_find_in_range_node(phys_addr_t size,
 2                     phys_addr_t align, phys_addr_t start,
 3                     phys_addr_t end, int nid, ulong flags)
 4 {
 5     phys_addr_t kernel_end, ret;
 6  
 7     /* pump up @end */
 8     if (end == MEMBLOCK_ALLOC_ACCESSIBLE)
 9         end = memblock.current_limit;
10  
11     /* avoid allocating the first page */
12     start = max_t(phys_addr_t, start, PAGE_SIZE);
13     end = max(start, end);
14     kernel_end = __pa_symbol(_end);

 1 /*
 2      * try bottom-up allocation only when bottom-up mode
 3      * is set and @end is above the kernel image.
 4      */
 5     if (memblock_bottom_up() && end > kernel_end) {
 6         phys_addr_t bottom_up_start;
 7  
 8         /* make sure we will allocate above the kernel */
 9         bottom_up_start = max(start, kernel_end);
10  
11         /* ok, try bottom-up allocation first */
12         ret = __memblock_find_range_bottom_up(bottom_up_start, end,
13                               size, align, nid, flags);
14         if (ret)
15             return ret;
16  
17         /*
18          * we always limit bottom-up allocation above the kernel,
19          * but top-down allocation doesn‘t have the limit, so
20          * retrying top-down allocation may succeed when bottom-up
21          * allocation failed.
22          *
23          * bottom-up allocation is expected to be fail very rarely,
24          * so we use WARN_ONCE() here to see the stack trace if
25          * fail happens.
26          */
27         WARN_ONCE(1, "memblock: bottom-up allocation failed, memory hotunplug may be affected\n");
28     }

 1 static phys_addr_t __init_memblock
 2 __memblock_find_range_bottom_up(phys_addr_t start, phys_addr_t end,
 3                 phys_addr_t size, phys_addr_t align, int nid,
 4                 ulong flags)
 5 {
 6     phys_addr_t this_start, this_end, cand;
 7     u64 i;
 8  
 9     for_each_free_mem_range(i, nid, flags, &this_start, &this_end, NULL) {
10         this_start = clamp(this_start, start, end);
11         this_end = clamp(this_end, start, end);
12  
13         cand = round_up(this_start, align);
14         if (cand < this_end && this_end - cand >= size)
15             return cand;
16     }
17  
18     return 0;
19 }

 1 static phys_addr_t __init_memblock
 2 __memblock_find_range_top_down(phys_addr_t start, phys_addr_t end,
 3                    phys_addr_t size, phys_addr_t align, int nid,
 4                    ulong flags)
 5 {
 6     phys_addr_t this_start, this_end, cand;
 7     u64 i;
 8  
 9     for_each_free_mem_range_reverse(i, nid, flags, &this_start, &this_end,
10                     NULL) {
11         this_start = clamp(this_start, start, end);
12         this_end = clamp(this_end, start, end);
13  
14         if (this_end < size)
15             continue;
16  
17         cand = round_down(this_end - size, align);
18         if (cand >= this_start)
19             return cand;
20     }
21  
22     return 0;
23 }

 1 int __init_memblock memblock_add_range(struct memblock_type *type,
 2                 phys_addr_t base, phys_addr_t size,
 3                 int nid, unsigned long flags)
 4 {
 5     bool insert = false;
 6     phys_addr_t obase = base;
 7     phys_addr_t end = base + memblock_cap_size(base, &size);
 8     int idx, nr_new;
 9     struct memblock_region *rgn;
10  
11     if (!size)
12         return 0;
13  
14     /* special case for empty array */
15     if (type->regions[0].size == 0) {
16         WARN_ON(type->cnt != 1 || type->total_size);
17         type->regions[0].base = base;
18         type->regions[0].size = size;
19         type->regions[0].flags = flags;
20         memblock_set_region_node(&type->regions[0], nid);
21         type->total_size = size;
22         return 0;
23     }

 1 repeat:
 2     /*
 3      * The following is executed twice.  Once with %false @insert and
 4      * then with %true.  The first counts the number of regions needed
 5      * to accommodate the new area.  The second actually inserts them.
 6      */
 7     base = obase;
 8     nr_new = 0;
 9  
10     for_each_memblock_type(idx, type, rgn) {
11         phys_addr_t rbase = rgn->base;
12         phys_addr_t rend = rbase + rgn->size;
13  
14         if (rbase >= end)
15             break;
16         if (rend <= base)
17             continue;
18         /*
19          * @rgn overlaps.  If it separates the lower part of new
20          * area, insert that portion.
21          */
22         if (rbase > base) {
23 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
24             WARN_ON(nid != memblock_get_region_node(rgn));
25 #endif
26             WARN_ON(flags != rgn->flags);
27             nr_new++;
28             if (insert)
29                 memblock_insert_region(type, idx++, base,
30                                rbase - base, nid,
31                                flags);
32         }
33         /* area below @rend is dealt with, forget about it */
34         base = min(rend, end);
35     }

 1 /* insert the remaining portion */
 2     if (base < end) {
 3         nr_new++;
 4         if (insert)
 5             memblock_insert_region(type, idx, base, end - base,
 6                            nid, flags);
 7     }
 8  
 9     if (!nr_new)
10         return 0;

 1     /*
 2      * If this was the first round, resize array and repeat for actual
 3      * insertions; otherwise, merge and return.
 4      */
 5     if (!insert) {
 6         while (type->cnt + nr_new > type->max)
 7             if (memblock_double_array(type, obase, size) < 0)
 8                 return -ENOMEM;
 9         insert = true;
10         goto repeat;
11     } else {
12         memblock_merge_regions(type);
13         return 0;
14     }

 1 static void __init_memblock memblock_insert_region(struct memblock_type *type,
 2                            int idx, phys_addr_t base,
 3                            phys_addr_t size,
 4                            int nid, unsigned long flags)
 5 {
 6     struct memblock_region *rgn = &type->regions[idx];
 7  
 8     BUG_ON(type->cnt >= type->max);
 9     memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
10     rgn->base = base;
11     rgn->size = size;
12     rgn->flags = flags;
13     memblock_set_region_node(rgn, nid);
14     type->cnt++;
15     type->total_size += size;
16 }

 1 static void __init_memblock memblock_merge_regions(struct memblock_type *type)
 2 {
 3     int i = 0;
 4  
 5     /* cnt never goes below 1 */
 6     while (i < type->cnt - 1) {
 7         struct memblock_region *this = &type->regions[i];
 8         struct memblock_region *next = &type->regions[i + 1];
 9  
10         if (this->base + this->size != next->base ||
11             memblock_get_region_node(this) !=
12             memblock_get_region_node(next) ||
13             this->flags != next->flags) {
14             BUG_ON(this->base + this->size > next->base);
15             i++;
16             continue;
17         }
18  
19         this->size += next->size;
20         /* move forward from next + 1, index of which is i + 2 */
21         memmove(next, next + 1, (type->cnt - (i + 2)) * sizeof(*next));
22         type->cnt--;
23     }
24 }

 1 static int __init_memblock memblock_double_array(struct memblock_type *type,
 2                         phys_addr_t new_area_start,
 3                         phys_addr_t new_area_size)
 4 {
 5     struct memblock_region *new_array, *old_array;
 6     phys_addr_t old_alloc_size, new_alloc_size;
 7     phys_addr_t old_size, new_size, addr;
 8     int use_slab = slab_is_available();
 9     int *in_slab;
10  
11     /* We don‘t allow resizing until we know about the reserved regions
12      * of memory that aren‘t suitable for allocation
13      */
14     if (!memblock_can_resize)
15         return -1;

 1     /* Calculate new doubled size */
 2     old_size = type->max * sizeof(struct memblock_region);
 3     new_size = old_size << 1;
 4     /*
 5      * We need to allocated new one align to PAGE_SIZE,
 6      *   so we can free them completely later.
 7      */
 8     old_alloc_size = PAGE_ALIGN(old_size);
 9     new_alloc_size = PAGE_ALIGN(new_size);
10  
11     /* Retrieve the slab flag */
12     if (type == &memblock.memory)
13         in_slab = &memblock_memory_in_slab;
14     else
15         in_slab = &memblock_reserved_in_slab;

 1     if (use_slab) {
 2         new_array = kmalloc(new_size, GFP_KERNEL);
 3         addr = new_array ? __pa(new_array) : 0;
 4     } else {
 5         /* only exclude range when trying to double reserved.regions */
 6         if (type != &memblock.reserved)
 7             new_area_start = new_area_size = 0;
 8  
 9         addr = memblock_find_in_range(new_area_start + new_area_size,
10                         memblock.current_limit,
11                         new_alloc_size, PAGE_SIZE);
12         if (!addr && new_area_size)
13             addr = memblock_find_in_range(0,
14                 min(new_area_start, memblock.current_limit),
15                 new_alloc_size, PAGE_SIZE);
16  
17         new_array = addr ? __va(addr) : NULL;
18     }
19     if (!addr) {
20         pr_err("memblock: Failed to double %s array from %ld to %ld entries !\n",
21                type->name, type->max, type->max * 2);
22         return -1;
23     }

 1     memcpy(new_array, type->regions, old_size);
 2     memset(new_array + type->max, 0, old_size);
 3     old_array = type->regions;
 4     type->regions = new_array;
 5     type->max <<= 1;
 6  
 7     /* Free old array. We needn‘t free it if the array is the static one */
 8     if (*in_slab)
 9         kfree(old_array);
10     else if (old_array != memblock_memory_init_regions &&
11          old_array != memblock_reserved_init_regions)
12         memblock_free(__pa(old_array), old_alloc_size);
13  
14     /*
15      * Reserve the new array if that comes from the memblock.  Otherwise, we
16      * needn‘t do it
17      */
18     if (!use_slab)
19         BUG_ON(memblock_reserve(addr, new_alloc_size));
20  
21     /* Update slab flag */
22     *in_slab = use_slab;
23  
24     return 0;

 1 static int __init_memblock memblock_isolate_range(struct memblock_type *type,
 2                     phys_addr_t base, phys_addr_t size,
 3                     int *start_rgn, int *end_rgn)
 4 {
 5     phys_addr_t end = base + memblock_cap_size(base, &size);
 6     int idx;
 7     struct memblock_region *rgn;
 8  
 9     *start_rgn = *end_rgn = 0;
10  
11     if (!size)
12         return 0;
13  
14  
15     /* we‘ll create at most two more regions */
16     while (type->cnt + 2 > type->max)
17         if (memblock_double_array(type, base, size) < 0)
18             return -ENOMEM;

 1 for_each_memblock_type(idx, type, rgn) {
 2         phys_addr_t rbase = rgn->base;
 3         phys_addr_t rend = rbase + rgn->size;
 4  
 5         if (rbase >= end)
 6             break;
 7         if (rend <= base)
 8             continue;
 9  
10         if (rbase < base) {
11             /*
12              * @rgn intersects from below.  Split and continue
13              * to process the next region - the new top half.
14              */
15             rgn->base = base;
16             rgn->size -= base - rbase;
17             type->total_size -= base - rbase;
18             memblock_insert_region(type, idx, rbase, base - rbase,
19                            memblock_get_region_node(rgn),
20                            rgn->flags);
21         } else if (rend > end) {
22             /*
23              * @rgn intersects from above.  Split and redo the
24              * current region - the new bottom half.
25              */
26             rgn->base = end;
27             rgn->size -= end - rbase;
28             type->total_size -= end - rbase;
29             memblock_insert_region(type, idx--, rbase, end - rbase,
30                            memblock_get_region_node(rgn),
31                            rgn->flags);
32         } else {
33             /* @rgn is fully contained, record it */
34             if (!*end_rgn)
35                 *start_rgn = idx;
36             *end_rgn = idx + 1;
37         }
38     }
39  
40     return 0;

 1 static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r)
 2 {
 3     type->total_size -= type->regions[r].size;
 4     memmove(&type->regions[r], &type->regions[r + 1],
 5         (type->cnt - (r + 1)) * sizeof(type->regions[r]));
 6     type->cnt--;
 7  
 8     /* Special case for empty arrays */
 9     if (type->cnt == 0) {
10         WARN_ON(type->total_size != 0);
11         type->cnt = 1;
12         type->regions[0].base = 0;
13         type->regions[0].size = 0;
14         type->regions[0].flags = 0;
15         memblock_set_region_node(&type->regions[0], MAX_NUMNODES);
16     }
17 }

 1 static int __init_memblock memblock_remove_range(struct memblock_type *type,
 2                       phys_addr_t base, phys_addr_t size)
 3 {
 4     int start_rgn, end_rgn;
 5     int i, ret;
 6  
 7     ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
 8     if (ret)
 9         return ret;
10  
11     for (i = end_rgn - 1; i >= start_rgn; i--)
12         memblock_remove_region(type, i);
13     return 0;
14 }