Re: [Lhms-devel] [RFC] buddy allocator without bitmap(3) [1/3]

[Hiroyuki KAMEZAWA]

> New function: calculate_aligned_end()
>
> calculate_aligned_end() removes some pages from system for removing invalid
> mem_map access from __free_pages_bulk() main loop.(This is in 4th patch)
This is an illustration of the effects of calculate_aligned_end().

Examples for MAX_ORDER=4 is here.
In this case, an alignment of memmap is (1 << (4-1))=8

[unaligned end address case]

Consider contiguous mem_map from index 0 to index 19.
mem_map[16-19] is unaligned.

pfn     0           4           8          12            16 17 18 19
        -------------------------------------------------------------
order 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  -- out of range --
        -------------------------------------------------------------
order 1 |     |     |     |     |     |     |     |     |     |     |
        -------------------------------------------------------------
order 2 |           |           |           |           |           |
        ------------------------------------------------------------
order 3 |                       |                       |
        -------------------------------------------------
        <----------------------> <---------------------> <---------??? ---->
In this case, invalid mem_map access will occur during

(1) coalescing page 16 with page 20 in order=2. <- this means memory access to page 20.

calculate_aligned_end() removes page 19.

 pfn     0           4           8          12            16 17 18 19
        -------------------------------------------------------------
order 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | X|   -- out of range --
        -------------------------------------------------------------
order 1 |     |     |     |     |     |     |     |     |     |
        -------------------------------------------------------
order 2 |           |           |           |           |
        -------------------------------------------------
order 3 |                       |                       |
        -------------------------------------------------
        <----------------------> <--------------------->

        page 19 is removed.
        -> page 18 and page 19 cannot be coalesced.
        -> page 16 - page 19 cannot be coalesced.
        -> accessing invalid page 20 will not occur.


[unaligned start address case]
Consider a mem_map begins from index 2.

pfn     0     2     4           8          12           16
              -------------------------------------------------------------------
order 0       |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
              -------------------------------------------------------------------
order 1       |     |     |     |     |     |     |     |     |     |     |     |
              --------------------------------------------------------------------
order 2             |           |           |           |           |           |
                    -------------------------------------------------------------
order 3                         |                       |                       |
                                -------------------------------------------------

In this case, invalid mem_map access will occur during
	(1) coalescing page 2 and page 0 in order=1
	(2) coalescing page 4 and page 0 in order=2

calculate_aligned_end() removes page 2 and 4.

pfn     0     2     4           8          12           16
              -------------------------------------------------------------------
order 0       |x |  |x |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
              -------------------------------------------------------------------
order 1                   |     |     |     |     |     |     |     |     |     |
                          --------------------------------------------------------
order 2                         |           |           |           |           |
                                -------------------------------------------------
order 3                         |                       |                       |
                                -------------------------------------------------

	page 2 is removed.
	-> page 2 and page 3 cannot be coalesced in order=0
	-> accessing invalid page 0 in order=1 will not occur.
	
	page 4 is removed.
	-> page 4 and page 5 cannot be coalesced in order=0.
	-> page 4 and page 6 cannot be coalesced in order=1.
	-> accessing invalid page 0 in order=2 will not occur.

Thanks.
--Kame
--
--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <kamezawa.hiroyu@xxxxxxxxxxxxxx>

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/