mm: use a radix-tree to make do_move_pages() complexity linear

Add a radix-tree in do_move_pages() to associate each page with the struct page_to_node that describes its migration. new_page_node() can now easily find out the page_to_node of the given page instead of traversing the whole page_to_node array. So the overall complexity is linear instead of quadratic.

We still need the page_to_node array since it is allocated by the caller (sys_move_page()) and used by do_pages_stat() when no target nodes are given by the application. And we need room to store all these page_to_node entries for do_move_pages() as well anyway.

If a page is given twice by the application, the old code would return -EBUSY (failure from the second isolate_lru_page()). Now, radix_tree_insert() will return -EEXIST, and we convert it back to -EBUSY to keep the user-space ABI.

The radix-tree is emptied at the end of do_move_pages() since new_page_node() doesn't know when an entry is used for the last time (unmap_and_move() could try another pass later). Marking pp->page as ZERO_PAGE(0) was actually never used. We now set it to NULL when pp is not in the radix-tree. It is faster than doing a loop of radix_tree_lookup_gang()+delete().

Quoted 16 lines · On Thu, 09 Oct 2008 14:32:26 +0200 Brice Goglin <[email protected]> wrote:

Add a radix-tree in do_move_pages() to associate each page with the struct page_to_node that describes its migration. new_page_node() can now easily find out the page_to_node of the given page instead of traversing the whole page_to_node array. So the overall complexity is linear instead of quadratic.

We still need the page_to_node array since it is allocated by the caller (sys_move_page()) and used by do_pages_stat() when no target nodes are given by the application. And we need room to store all these page_to_node entries for do_move_pages() as well anyway.

If a page is given twice by the application, the old code would return -EBUSY (failure from the second isolate_lru_page()). Now, radix_tree_insert() will return -EEXIST, and we convert it back to -EBUSY to keep the user-space ABI.

Quoted 7 lines

The radix-tree is emptied at the end of do_move_pages() since new_page_node() doesn't know when an entry is used for the last time (unmap_and_move() could try another pass later). Marking pp->page as ZERO_PAGE(0) was actually never used. We now set it to NULL when pp is not in the radix-tree. It is faster than doing a loop of radix_tree_lookup_gang()+delete().

Any O(n*n) code always catches up with us in the end. But I do think that to merge this code we'd need some description of the problem which we fixed.

Please send a description of the situation under which the current code performs unacceptably. Some before-and-after quantitative measurements would be good.

Because it could be (as far as I know) that the problem is purely theoretical, in which case we might not want the patch at all.

Just try sys_move_pages() on a 10-100MB buffer, you'll get something like 50MB/s on a recent Opteron machine. This throughput decreases significantly with the number of pages. With this patch, we get about 350MB/s and the throughput is stable when the migrated buffer gets larger. I don't have detailled numbers at hand, I'll send them by monday.

Would it be possible to restructure this in such a way that we work in chunks of 100 or so pages each so that we can avoid the vmalloc?

We also could do a kmalloc for each individual struct pm_struct with the radix tree which would also avoid the vmalloc but still keep the need to allocate 4MB for temporary struct pm_structs.

Or get rid of the pm_struct altogether by storing the address of the node vector somewhere and retrieve the node as needed from the array. This would allow storing the struct page * pointers in the radix tree.

Quoted 10 lines · Christoph Lameter

Would it be possible to restructure this in such a way that we work in chunks of 100 or so pages each so that we can avoid the vmalloc?

We also could do a kmalloc for each individual struct pm_struct with the radix tree which would also avoid the vmalloc but still keep the need to allocate 4MB for temporary struct pm_structs.

Or get rid of the pm_struct altogether by storing the address of the node vector somewhere and retrieve the node as needed from the array. This would allow storing the struct page * pointers in the radix tree.

I have been thinking about all this, and here's some ideas:
* do_pages_stat() may easily be rewritten without the huge pm array. It just need to user-space pointers to the page and status arrays. It traverses the first array , and for each page does: doing get_user() the address, retrieve the page node, and put_user() the result in the status array. No need to allocate any single page_to_node structure.
* If we split the migration in small chunks (such as one page of pm's), the quadratic complexity doesn't matter that much. There will be at most several dozens of pm in the chunk array, so the linear search in new_page_node() won't be that slow, it may even be faster than the overall cost of adding a radix-tree to improve this search. So we can keep the internal code unchanged and just add the chunking around it.
* One thing that bothers me is move_pages() returning -ENOENT when no page are given to migrate_pages(). I don't see why having 100/100 pages not migrated would return a different error than having only 99/100 pages not migrated. We have the status array to place -ENOENT for all these pages. If the user doesn't know where his pages are allocated, he shouldn't get a different return value depending on how many pages were already on the right node. And actually, this convention makes user-space application harder to write since you need to treat -ENOENT as a success unless you already knew for sure where your pages were allocated. And the big thing is that this convention makes the chunking painfully/uselessly more complex. Breaking user-ABI is bad, but fixing crazy ABI...

Here are some other numbers from the above (dirty) implementation, migrating from node #2 to #3 on a quad-quad-core opteron 2347HE with vanilla 2.6.27:

length move_pages (us) move_pages with patch (us)
4kB 126 98
40kB 198 168
400kB 963 937
4MB 12503 11930
40MB 246867 11848

It seems to be even slightly better than the previous patch (but the kernel are a bit different). And I quickly checked that it scales well up to 4GB buffers.

If you are worried about vmalloc overhead, I'd suggest testing with -mm. I've rewritten the vmap code so it is now slightly scalable and sane to use.

* One thing that bothers me is move_pages() returning -ENOENT when no page are given to migrate_pages(). I don't see why having 100/100 pages not migrated would return a different error than having only 99/100 pages not migrated. We have the status array to place -ENOENT for all

these pages. If the user doesn't know where his pages are allocated, he shouldn't get a different return value depending on how many pages were already on the right node. And actually, this convention makes user-space application harder to write since you need to treat -ENOENT as a success unless you already knew for sure where your pages were allocated. And the big thing is that this convention makes the chunking painfully/uselessly more complex. Breaking user-ABI is bad, but fixing crazy ABI...

Quoted 33 lines · Andrew Morton

Quoted 16 lines · On Thu, 09 Oct 2008 14:32:26 +0200 Brice Goglin <[email protected]> wrote:

Add a radix-tree in do_move_pages() to associate each page with the struct page_to_node that describes its migration. new_page_node() can now easily find out the page_to_node of the given page instead of traversing the whole page_to_node array. So the overall complexity is linear instead of quadratic.

We still need the page_to_node array since it is allocated by the caller (sys_move_page()) and used by do_pages_stat() when no target nodes are given by the application. And we need room to store all these page_to_node entries for do_move_pages() as well anyway.

If a page is given twice by the application, the old code would return -EBUSY (failure from the second isolate_lru_page()). Now, radix_tree_insert() will return -EEXIST, and we convert it back to -EBUSY to keep the user-space ABI.

Quoted 8 lines

The radix-tree is emptied at the end of do_move_pages() since new_page_node() doesn't know when an entry is used for the last time (unmap_and_move() could try another pass later). Marking pp->page as ZERO_PAGE(0) was actually never used. We now set it to NULL when pp is not in the radix-tree. It is faster than doing a loop of radix_tree_lookup_gang()+delete().

Any O(n*n) code always catches up with us in the end. But I do think that to merge this code we'd need some description of the problem which we fixed.

Quoted 8 lines

Please send a description of the situation under which the current code performs unacceptably. Some before-and-after quantitative measurements would be good.

Because it could be (as far as I know) that the problem is purely theoretical, in which case we might not want the patch at all.

Just try sys_move_pages() on a 10-100MB buffer, you'll get something like 50MB/s on a recent Opteron machine. This throughput decreases significantly with the number of pages. With this patch, we get about 350MB/s and the throughput is stable when the migrated buffer gets larger. I don't have detailled numbers at hand, I'll send them by monday.