memory defragmentation to satisfy high order allocations

The following patch implements a "coalesce_memory()" function which takes "zone" and "order" as a parameter.

It tries to move enough physically nearby pages to form a free area of "order" size.

It does that by checking whether the page can be moved, allocating a new page, unmapping the pte's to it, copying data to new page, remapping the ptes, and reinserting the page on the radix/LRU.

Quoted 4 lines · Marcelo Tosatti

The following patch implements a "coalesce_memory()" function which takes "zone" and "order" as a parameter.

Quoted 6 lines

It tries to move enough physically nearby pages to form a free area of "order" size.

It does that by checking whether the page can be moved, allocating a new page, unmapping the pte's to it, copying data to new page, remapping the ptes, and reinserting the page on the radix/LRU.

Presumably this duplicates some of the memory hot-remove patches.

Apparently Dave Hansen has working and sane-looking hot remove code which is in a close-to-submittable state.

As far as I have researched, the memory moving/remapping code on the hot remove patches dont work correctly. Please correct me.

And what I've seen (from the Fujitsu guys) was quite ugly IMHO.

Quoted 1 line · Andrew Morton

Presumably this duplicates some of the memory hot-remove patches.

As far as I have researched, the memory moving/remapping code on the hot remove patches dont work correctly. Please correct me.

And what I've seen (from the Fujitsu guys) was quite ugly IMHO.

Quoted 5 lines · Marcelo Tosatti

Quoted 1 line · Andrew Morton

Presumably this duplicates some of the memory hot-remove patches.

As far as I have researched, the memory moving/remapping code on the hot remove patches dont work correctly. Please correct me.

I definitely see some commonality, but Marcelo's approach has handling for the different kinds of pages broken out much more nicely. Can't tell yet if this produces extra code, or is just plain better.

We worked pretty hard to try and copy as little code as possible. Was there any reason that there was so much stuff copied out of rmap.c? Just for proof-of-concept?

Here's one of the recent patch sets that we're working on:

http://sprucegoose.sr71.net/patches/2.6.9-rc2-mm4-mhp-test2/

In that directory, the K* patches hijack some of the swap code (but require memory pressure to work last time I tried), and the p000* patches (by Hirokazu Takahashi) actively migrate pages around. Both approaches work, but the K* one is smaller and less intrusive, while the p000* one is much more complete. They may end up being able to coexist in the end.

I don't work for Fujitsu :) Please take a look at the patches in the above directory and see what you think. I'm sure you have some very good stuff in your patch, but I need to take a closer look.

I'm just about to head out of town for the weekend, but I'll take a much more detailed look on Monday.

Quoted 5 lines

Here's one of the recent patch sets that we're working on:

http://sprucegoose.sr71.net/patches/2.6.9-rc2-mm4-mhp-test2/

...
Andrew, what are your thoughts wrt merging this to mainline?

For the "defragmentation" operation we want to do an "easy" try - ie if we can't remap giveup.

I feel we should try to "untie" the code which checks for remapping availability / does the remapping from the page migration - so to be able to share the most code between it and other users of the same functionality.

Curiosity: How did you guys test the migration operation? Several threads on several processors operating on the memory, etc?

Cool. I'll take a closer look at the relevant parts of memory hotplug patches this weekend, hopefully. See if I can help with testing of these patches too.

Hello, Marcelo.

Generic memory defragmentation will be very nice for me to implement hugetlbpage migration, as allocating a new hugetlbpage is a hard job.

Quoted 6 lines

For the "defragmentation" operation we want to do an "easy" try - ie if we can't remap giveup.

I feel we should try to "untie" the code which checks for remapping availability / does the remapping from the page migration - so to be able to share the most code between it and other users of the same functionality.

I think it's possible to introduce non-wait mode to the migration code, as you may expect. Shall I implement it?

Quoted 2 lines

Curiosity: How did you guys test the migration operation? Several threads on several processors operating on the memory, etc?

I always test it with the zone hotplug emulation patch, which Mr.Iwamoto has made. I usually run following jobs concurrently while zones are added and removed repeatedly on a SMP machine.
- making linux kernel
- copying file trees.
- overwriting file trees.
- removing file trees
- some pages are swapped out automatically:)

And Mr.Iwamoto has some small programs to check any kind of page can be migrated. The programs repeat one of following actions:
- read/write files .
- use MAP_SHARED and MAP_PRIVATE mmap()'s and read/write there.
- use Direct I/O.
- use AIO.
- fork to have COW pages.
- use shmem.
- use sendfile.

Quoted 2 lines

Cool. I'll take a closer look at the relevant parts of memory hotplug patches this weekend, hopefully. See if I can help with testing of these patches too.

Any comments are very welcome.

Quoted 4 lines

Quoted 2 lines

Cool. I'll take a closer look at the relevant parts of memory hotplug patches this weekend, hopefully. See if I can help with testing of these patches too.

Any comments are very welcome.

I have a few comments about the code:

1)
I'm pretty sure you should transfer the radix tree tag at radix_tree_replace(). If for example you transfer a dirty tagged page to another zone, an mpage_writepages() will miss it (because it uses pagevec_lookup_tag(PAGECACHE_DIRTY_TAG)).

Should be quite trivial to do (save tags before deleting and set to new entry, all in radix_tree_replace).

My implementation also contained the same bug.

2)
At migrate_onepage you add anonymous pages which aren't swap allocated to the swap cache

(quoted diff) +10 -0

+       /*
+        * Put the page in a radix tree if it isn't in the tree yet.
+        */
+#ifdef CONFIG_SWAP
+       if (PageAnon(page) && !PageSwapCache(page))
+               if (!add_to_swap(page, GFP_KERNEL)) {
+                       unlock_page(page);
+                       return ERR_PTR(-ENOSPC);
+               }
+#endif /* CONFIG_SWAP */

Why's that? You can copy anonymous pages without adding them to swap (thats what the patch I posted does).

3) At migrate_page_common you assume additional page references (page_migratable returning -EAGAIN) means the code should try to writeout the page.

Is that assumption always valid?

In theory there is no need to writeout pages when migrating them to other zones - they will be copied and the dirty information retained (either in the PageDirty bit or radix tree tag).

I just noticed you do that on further patches (migrate_page_buffer), but AFAICS the writeout remains. Why arent you using migrate_page_buffer yet?

I think the final aim should be to remove the need for "pageout()" completly.

4)
About implementing a nonblocking version of it. The easier way, it seems to me, is to pass a "block" argument to generic_migrate_page() and use that.

Questions: are there any documents on the memory hotplug userspace tools? Where can I find them?

Are Iwamoto's test programs available?

In general the code looks nice to me! I'll jump in and help with testing.

Hi,

Quoted 13 lines

Quoted 4 lines

Quoted 2 lines

Cool. I'll take a closer look at the relevant parts of memory hotplug patches this weekend, hopefully. See if I can help with testing of these patches too.

Any comments are very welcome.

I have a few comments about the code:

1)
I'm pretty sure you should transfer the radix tree tag at radix_tree_replace(). If for example you transfer a dirty tagged page to another zone, an mpage_writepages() will miss it (because it uses pagevec_lookup_tag(PAGECACHE_DIRTY_TAG)).

Quoted 4 lines

Should be quite trivial to do (save tags before deleting and set to new entry, all in radix_tree_replace).

My implementation also contained the same bug.

Yes, it's one of the issues to do. The tag should be transferred in radix_tree_replace() as you pointed out. The current implementation sets the tag in set_page_dirty(newpage).

Quoted 14 lines

2)
At migrate_onepage you add anonymous pages which aren't swap allocated to the swap cache

(quoted diff) +10 -0

+       /*
+        * Put the page in a radix tree if it isn't in the tree yet.
+        */
+#ifdef CONFIG_SWAP
+       if (PageAnon(page) && !PageSwapCache(page))
+               if (!add_to_swap(page, GFP_KERNEL)) {
+                       unlock_page(page);
+                       return ERR_PTR(-ENOSPC);
+               }
+#endif /* CONFIG_SWAP */

Quoted 2 lines

Why's that? You can copy anonymous pages without adding them to swap (thats what the patch I posted does).

The reason is to guarantee that any anonymous page can be migrated anytime. I want to block newly occurred accesses to the page during the migration because it can't be migrated if there remain some references on it by system calls, direct I/O and page faults.

Your approach will work fine on most of anonymous pages, which aren't heavily accessed. I think it will be enough for memory defragmentation.

Quoted 5 lines

3) At migrate_page_common you assume additional page references (page_migratable returning -EAGAIN) means the code should try to writeout the page.

Is that assumption always valid?

-EAGAIN means that the page may require to be written back

or
just to wait for a while since the page is just referred by system call or pagefault handler.

Quoted 6 lines

In theory there is no need to writeout pages when migrating them to other zones - they will be copied and the dirty information retained (either in the PageDirty bit or radix tree tag).

I just noticed you do that on further patches (migrate_page_buffer), but AFAICS the writeout remains. Why arent you using migrate_page_buffer yet?

I've designed migrate_page_buffer() for this purpose. At this moment ext2 only uses this yet.

Quoted 2 lines

I think the final aim should be to remove the need for "pageout()" completly.

Yes!

Quoted 4 lines

4)
About implementing a nonblocking version of it. The easier way, it seems to me, is to pass a "block" argument to generic_migrate_page() and use that.

Yes.

Quoted 2 lines

Questions: are there any documents on the memory hotplug userspace tools? Where can I find them?

IBM guys and Fujitsu guys are designing user interface independently. IBM team is implementing memory section hotplug while Fujitsu team try to implement NUMA node hotplug. But both of the designs use regular hot-plug mechanism, which kicks /sbin/hotplug script to control devices via sysfs.

Dave, would you explain about it?

Quoted 1 line

Are Iwamoto's test programs available?

Ok, I'll notice him to post them.

Quoted 2 lines

In general the code looks nice to me! I'll jump in and help with testing.

I appreciate your offer. I'm very happy with that.

Quoted 14 lines

Quoted 14 lines

2)
At migrate_onepage you add anonymous pages which aren't swap allocated to the swap cache

(quoted diff) +10 -0

+       /*
+        * Put the page in a radix tree if it isn't in the tree yet.
+        */
+#ifdef CONFIG_SWAP
+       if (PageAnon(page) && !PageSwapCache(page))
+               if (!add_to_swap(page, GFP_KERNEL)) {
+                       unlock_page(page);
+                       return ERR_PTR(-ENOSPC);
+               }
+#endif /* CONFIG_SWAP */

Quoted 7 lines

Quoted 2 lines

Why's that? You can copy anonymous pages without adding them to swap (thats what the patch I posted does).

The reason is to guarantee that any anonymous page can be migrated anytime. I want to block newly occurred accesses to the page during the migration because it can't be migrated if there remain some references on it by system calls, direct I/O and page faults.

It would be nice if we could block pte faults in a way such to not need adding each anonymous page to swap. It can be too costly if you have a lot memory and it makes the whole operation dependable on swap size (if you dont have enough swap, you're dead).

Maybe hold mm->page_table_lock (might be too costly in terms of CPU time, but since migration is not a common operation anyway), or create a semaphore?

Quoted 2 lines

Your approach will work fine on most of anonymous pages, which aren't heavily accessed. I think it will be enough for memory defragmentation.

Yes...

Quoted 4 lines

Quoted 4 lines

3) At migrate_page_common you assume additional page references (page_migratable returning -EAGAIN) means the code should try to writeout the page.

Quoted 3 lines

Quoted 1 line

Is that assumption always valid?

-EAGAIN means that the page may require to be written back

But why is it needed to writeout pages? We shouldnt need to. At least from what I can understand.

Quoted 3 lines

or
just to wait for a while since the page is just referred by system call or pagefault handler.

I'm not sure if making that assumption is always valid.

Kernel code can have an additional count on the page meaning "this page is pinned, dont move it". At least that should be valid.

Any piece of code which holds a reference on a page for a long time is going to be a pain for the algorithm right?

Quoted 5 lines

Quoted 4 lines

4)
About implementing a nonblocking version of it. The easier way, it seems to me, is to pass a "block" argument to generic_migrate_page() and use that.

Quoted 1 line

Yes.

OK. I'll try to implement it this week (plus the radix_tree_replace tag thingie).

Pages for NFS also might be pinned with network problems. One of the ideas is to restrict NFS to allocate pages from specific memory region, sot that all memory except the region can be hot-removed. And it's possible to implementing whole migrate_page method, which may handled stuck pages.

Quoted 5 lines

Pages for NFS also might be pinned with network problems. One of the ideas is to restrict NFS to allocate pages from specific memory region, sot that all memory except the region can be hot-removed. And it's possible to implementing whole migrate_page method, which may handled stuck pages.

Why do you want to special-case this?

The above is a generic condition: any filesystem can suffer from the equivalent problem of a failure or slow response in the underlying device. Making an NFS-specific hack is just counter-productive to solving the generic problem.

However, while network is down network/cluster filesystems might not release pages forever unlike in the case of block devices, which may timeout or returns a error in case of failure.

Each filesystem can control what the migration code does. If it doesn't have anything to help memory migration, it's possible to wait for the network coming up before starting memory migration, or give up it if the network happen to be down. That's no problem.

Quoted 3 lines

However, while network is down network/cluster filesystems might not release pages forever unlike in the case of block devices, which may timeout or returns a error in case of failure.

Where is the difference? As far as the VM is concerned, it is a latency problem. The fact of whether or not it is a permanent hang, a hang with a long timeout, or just a slow device is irrelevant because the VM doesn't actually know about these devices.

Quoted 4 lines

Each filesystem can control what the migration code does. If it doesn't have anything to help memory migration, it's possible to wait for the network coming up before starting memory migration, or give up it if the network happen to be down. That's no problem.

Wrong. It *is* a problem: Filesystems aren't required to know anything about the particulars of the underlying block/network/... device timeout semantics either.

Think, for instance about EXT2. Where in the current code do you see that it is required to detect that it is running on top of something like the NBD device? Where does it figure out what the latencies of this device is?

AFAICS, most filesystems in linux/fs/* have no knowledge whatsoever about the underlying block/network/... devices and their timeout values. Basing your decision about whether or not you need to manage high latency situations just by inspecting the filesystem type is therefore not going to give very reliable results.

Hi, Marcelo

Quoted 27 lines

Quoted 14 lines

Quoted 14 lines

2)
At migrate_onepage you add anonymous pages which aren't swap allocated to the swap cache

(quoted diff) +10 -0

+       /*
+        * Put the page in a radix tree if it isn't in the tree yet.
+        */
+#ifdef CONFIG_SWAP
+       if (PageAnon(page) && !PageSwapCache(page))
+               if (!add_to_swap(page, GFP_KERNEL)) {
+                       unlock_page(page);
+                       return ERR_PTR(-ENOSPC);
+               }
+#endif /* CONFIG_SWAP */

Quoted 7 lines

Quoted 2 lines

Why's that? You can copy anonymous pages without adding them to swap (thats what the patch I posted does).

The reason is to guarantee that any anonymous page can be migrated anytime. I want to block newly occurred accesses to the page during the migration because it can't be migrated if there remain some references on it by system calls, direct I/O and page faults.

It would be nice if we could block pte faults in a way such to not need adding each anonymous page to swap. It can be too costly if you have a lot memory and it makes the whole operation dependable on swap size (if you dont have enough swap, you're dead).

Quoted 2 lines

Maybe hold mm->page_table_lock (might be too costly in terms of CPU time, but since migration is not a common operation anyway), or create a semaphore?

I think the problem of the holding mm->page_table_lock approach is that it doesn't allow the migration code blocked. the semaphore approach would be better.

I have another idea that each anonymous page can detach its swap entry after its migration.

It can be done by remove_exclusive_swap_page() if the page is remapped to the same spaces forcibly by touch_unmapped_address() I made.

Quoted 9 lines

Quoted 2 lines

Your approach will work fine on most of anonymous pages, which aren't heavily accessed. I think it will be enough for memory defragmentation.

Yes...

Quoted 4 lines

Quoted 4 lines

3) At migrate_page_common you assume additional page references (page_migratable returning -EAGAIN) means the code should try to writeout the page.

Quoted 6 lines

Quoted 3 lines

Quoted 1 line

Is that assumption always valid?

-EAGAIN means that the page may require to be written back

But why is it needed to writeout pages? We shouldnt need to. At least from what I can understand.

The migration code allows each filesystem to implement its own migration code or just use migrate_page_buffer() or migrate_page_common().

migrate_page_common() is a default function if filesystem doesn't implement anything. The function is the most generic and it tries to writeback pages only if they are dirty and have buffers.

Quoted 8 lines

Quoted 3 lines

or
just to wait for a while since the page is just referred by system call or pagefault handler.

I'm not sure if making that assumption is always valid.

Kernel code can have an additional count on the page meaning "this page is pinned, dont move it". At least that should be valid.

Yes, I know. I have checked all of the code.

AIO event buffers are pinned, therefore the memory-hotplug team plans to make pages for the event buffers assigned to non-hotpluggable memory regions.

And pages in sendfile() might be pinned for a while in case of network problems. I think there may be some workarounds. The easiest way is just waiting its timeout, and another way is changing the mode of sendfile() to copy pages in advance.

Pages for NFS also might be pinned with network problems. One of the ideas is to restrict NFS to allocate pages from specific memory region, sot that all memory except the region can be hot-removed. And it's possible to implementing whole migrate_page method, which may handled stuck pages.

If the migration code is used for memory defragmentation, pinned pages must be avoided. I think it can be done with the non-blocking mode.

Quoted 9 lines

Any piece of code which holds a reference on a page for a long time is going to be a pain for the algorithm right?

Quoted 5 lines

Quoted 4 lines

4)
About implementing a nonblocking version of it. The easier way, it seems to me, is to pass a "block" argument to generic_migrate_page() and use that.

Quoted 4 lines

Quoted 1 line

Yes.

OK. I'll try to implement it this week (plus the radix_tree_replace tag thingie).

Thank you for that.

Quoted 16 lines

Quoted 15 lines

Quoted 7 lines

Quoted 2 lines

Why's that? You can copy anonymous pages without adding them to swap (thats what the patch I posted does).

The reason is to guarantee that any anonymous page can be migrated anytime. I want to block newly occurred accesses to the page during the migration because it can't be migrated if there remain some references on it by system calls, direct I/O and page faults.

It would be nice if we could block pte faults in a way such to not need adding each anonymous page to swap. It can be too costly if you have a lot memory and it makes the whole operation dependable on swap size (if you dont have enough swap, you're dead).

Maybe hold mm->page_table_lock (might be too costly in terms of CPU time, but since migration is not a common operation anyway), or create a semaphore?

Quoted 3 lines

I think the problem of the holding mm->page_table_lock approach is that it doesn't allow the migration code blocked. the semaphore approach would be better.

OK, I think the problem is that can be more than one thread with different address spaces (ie different "current->mm", after fork) accessing the page.

Adding a waitqueue to "anon_vma" structure (to be slept at do_swap_page time, and awake after copy-page-and-flags/unlock), can be do the job I think.

Quoted 2 lines

I have another idea that each anonymous page can detach its swap entry after its migration.

Yes thats a nice idea.

Quoted 3 lines

It can be done by remove_exclusive_swap_page() if the page is remapped to the same spaces forcibly by touch_unmapped_address() I made.

touch_unmapped_address() ?

Quoted 20 lines

Quoted 9 lines

Quoted 2 lines

Your approach will work fine on most of anonymous pages, which aren't heavily accessed. I think it will be enough for memory defragmentation.

Yes...

Quoted 4 lines

Quoted 4 lines

3) At migrate_page_common you assume additional page references (page_migratable returning -EAGAIN) means the code should try to writeout the page.

Quoted 6 lines

Quoted 3 lines

Quoted 1 line

Is that assumption always valid?

-EAGAIN means that the page may require to be written back

But why is it needed to writeout pages? We shouldnt need to. At least from what I can understand.

The migration code allows each filesystem to implement its own migration code or just use migrate_page_buffer() or migrate_page_common().

Quoted 3 lines

migrate_page_common() is a default function if filesystem doesn't implement anything. The function is the most generic and it tries to writeback pages only if they are dirty and have buffers.

The thing is: What is the point of writing out pages?

We're just trying to migrate pages to another zone.

If its under writeout, wait, if its dirty, just move it to the other zone.

Can you enlight me?

It was the easiest way to handle pages with buffers when Iwamoto and I started to implement it. We thought it was slow but it would work for all kinds of filesystems.

Quoted 5 lines

We're just trying to migrate pages to another zone.

If its under writeout, wait, if its dirty, just move it to the other zone.

Quoted 1 line

Can you enlight me?

Yes, I also realize that.
migrate_page_buffer() will do this, but I'm not certain it will work for all kinds of filesystems. I guess there might be some exceptions. We may need a special operation to handle pages on a filesystem, which has releasepage method.

It seems there is typo in the current version of the patch:

int try_to_migrate_pages(struct list_head *page_list) {
...

        current->flags |= PF_KSWAPD;    /*  It's fake */
        list_for_each_entry_safe(page, page2, page_list, lru) {
                /*
                 * Start writeback I/O if it's a dirty page with buffers
                 * and it doesn't have migrate_page method.
                 */
                if (PageDirty(page) && PagePrivate(page)) {
                        if (!TestSetPageLocked(page)) {
                                mapping = page_mapping(page);
                                if (!mapping || mapping->a_ops->migrate_page ||

                                    pageout(page, mapping) != PAGE_SUCCESS) {
                                        unlock_page(page);
                                }
                        }
                }

Shouldnt that be "!mapping->a_ops->migrate_page"?

That is, if we can't migrate the page, try to write it out?

Hi, Marcelo.

Quoted 5 lines

It seems there is typo in the current version of the patch:

int try_to_migrate_pages(struct list_head *page_list) {
...

Quoted 10 lines

        current->flags |= PF_KSWAPD;    /*  It's fake */
        list_for_each_entry_safe(page, page2, page_list, lru) {
                /*
                 * Start writeback I/O if it's a dirty page with buffers
                 * and it doesn't have migrate_page method.
                 */
                if (PageDirty(page) && PagePrivate(page)) {
                        if (!TestSetPageLocked(page)) {
                                mapping = page_mapping(page);
                                if (!mapping || mapping->a_ops->migrate_page ||

a> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Quoted 8 lines

                                    pageout(page, mapping) != PAGE_SUCCESS) {
                                        unlock_page(page);
                                }
                        }
                }

Shouldnt that be "!mapping->a_ops->migrate_page"?

"mapping->a_ops->migrate_page" is correct.

This code is just for optimization. If mapping->a_ops->migrate_page isn't implemented, migrate_page_common() is used to migrate the page. migrate_page_common() will try to write it back if it's dirty, so that it would be better to start writeback I/O for target pages in advance without waiting the I/O completions.

As you may know the migration code will work fine without this code.

Quoted 1 line

That is, if we can't migrate the page, try to write it out?

Quoted 27 lines

Hi, Marcelo.

Quoted 23 lines

It seems there is typo in the current version of the patch:

int try_to_migrate_pages(struct list_head *page_list) {
...

        current->flags |= PF_KSWAPD;    /*  It's fake */
        list_for_each_entry_safe(page, page2, page_list, lru) {
                /*
                 * Start writeback I/O if it's a dirty page with buffers
                 * and it doesn't have migrate_page method.
                 */
                if (PageDirty(page) && PagePrivate(page)) {
                        if (!TestSetPageLocked(page)) {
                                mapping = page_mapping(page);
                                if (!mapping || mapping->a_ops->migrate_page ||
						^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                    pageout(page, mapping) != PAGE_SUCCESS) {
                                        unlock_page(page);
                                }
                        }
                }

Quoted 1 line

Shouldnt that be "!mapping->a_ops->migrate_page"?

Quoted 7 lines

"mapping->a_ops->migrate_page" is correct.

This code is just for optimization. If mapping->a_ops->migrate_page isn't implemented, migrate_page_common() is used to migrate the page. migrate_page_common() will try to write it back if it's dirty, so that it would be better to start writeback I/O for target pages in advance without waiting the I/O completions.

Right. But if migrate_page _is_ implemented, we also start writeback!

Shouldnt that be "if we dont have migrate_page(), start writeback, since in this case well use migrate_page_common() anyway."

It seems the logic is inverted, or maybe I'm wrong.

Quoted 1 line

As you may know the migration code will work fine without this code.

OK!

Quoted 1 line

Quoted 1 line

That is, if we can't migrate the page, try to write it out?

I just didnt understand the logic very well, maybe I should just go reread the code.

Thanks!

Hi, Marcelo.

Quoted 36 lines · Hirokazu Takahashi

Quoted 27 lines

Hi, Marcelo.

Quoted 23 lines

It seems there is typo in the current version of the patch:

int try_to_migrate_pages(struct list_head *page_list) {
...

        current->flags |= PF_KSWAPD;    /*  It's fake */
        list_for_each_entry_safe(page, page2, page_list, lru) {
                /*
                 * Start writeback I/O if it's a dirty page with buffers
                 * and it doesn't have migrate_page method.
                 */
                if (PageDirty(page) && PagePrivate(page)) {
                        if (!TestSetPageLocked(page)) {
                                mapping = page_mapping(page);
                                if (!mapping || mapping->a_ops->migrate_page ||
						^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                    pageout(page, mapping) != PAGE_SUCCESS) {
                                        unlock_page(page);
                                }
                        }
                }

Quoted 1 line

Shouldnt that be "!mapping->a_ops->migrate_page"?

Quoted 7 lines

"mapping->a_ops->migrate_page" is correct.

This code is just for optimization. If mapping->a_ops->migrate_page isn't implemented, migrate_page_common() is used to migrate the page. migrate_page_common() will try to write it back if it's dirty, so that it would be better to start writeback I/O for target pages in advance without waiting the I/O completions.

Quoted 6 lines

Right. But if migrate_page _is_ implemented, we also start writeback!

Shouldnt that be "if we dont have migrate_page(), start writeback, since in this case well use migrate_page_common() anyway."

It seems the logic is inverted, or maybe I'm wrong.

It's my understanding that the previous code is equivalent to the following code. Am I missing something?

if (PageDirty(page) && PagePrivate(page)) {
        if (!TestSetPageLocked(page)) {
                mapping = page_mapping(page);
                if (!mapping) {
                        unlock_page(page);
		} else if (mapping->a_ops->migrate_page) {
                        unlock_page(page);
		} else if (pageout(page, mapping) != PAGE_SUCCESS) {
                        unlock_page(page);
		}
	}
}

Quoted 10 lines

Quoted 1 line

As you may know the migration code will work fine without this code.

OK!

Quoted 1 line

Quoted 1 line

That is, if we can't migrate the page, try to write it out?

I just didnt understand the logic very well, maybe I should just go reread the code.

Thanks!

Quoted 5 lines

Quoted 5 lines

Quoted 1 line

Quoted 1 line

That is, if we can't migrate the page, try to write it out?

I just didnt understand the logic very well, maybe I should just go reread the code.

Quoted 1 line

Quoted 1 line

Thanks!

I'm thinking about how to implement a nonblocking version of generic_migrate_page().

For this purpose its really bad to allocate swap space to anonymous pages, well need to figure out someother way of blocking the users via pagetablefault.

Like a "virtual" swap space but without allocating swap map space.

Hi, Marcelo.

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 1 line

Quoted 1 line

That is, if we can't migrate the page, try to write it out?

I just didnt understand the logic very well, maybe I should just go reread the code.

Quoted 8 lines

Quoted 1 line

Quoted 1 line

Thanks!

I'm thinking about how to implement a nonblocking version of generic_migrate_page().

For this purpose its really bad to allocate swap space to anonymous pages, well need to figure out someother way of blocking the users via pagetablefault.

Like a "virtual" swap space but without allocating swap map space.

I've also ever thought to implement such a device. It would be nice if you can design it simple.

Mr.Iwamoto thought otherwise and posted another opinion on the lhms list, though. I felt it also has a point.

iwamoto> I don't think requiring swap is a big deal. If you don't have a iwamoto> dedicated swap device, which case I think unusual, you can swapon a iwamoto> regular file.

Quoted 22 lines · Hirokazu Takahashi

Hi, Marcelo.

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 1 line

Quoted 1 line

That is, if we can't migrate the page, try to write it out?

I just didnt understand the logic very well, maybe I should just go reread the code.

Quoted 8 lines

Quoted 1 line

Quoted 1 line

Thanks!

I'm thinking about how to implement a nonblocking version of generic_migrate_page().

For this purpose its really bad to allocate swap space to anonymous pages, well need to figure out someother way of blocking the users via pagetablefault.

Like a "virtual" swap space but without allocating swap map space.

I've also ever thought to implement such a device. It would be nice if you can design it simple.

Mr.Iwamoto thought otherwise and posted another opinion on the lhms list, though. I felt it also has a point.

Quoted 3 lines

iwamoto> I don't think requiring swap is a big deal. If you don't have a iwamoto> dedicated swap device, which case I think unusual, you can swapon a iwamoto> regular file.

Sure its not a big deal, but nicer if it doesnt require swap.

For memory defragmentation it is a big deal.

At Fri, 8 Oct 2004 12:36:46 -0300,

Quoted 28 lines · Marcelo Tosatti

Quoted 25 lines · Hirokazu Takahashi

Hi, Marcelo.

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 1 line

Quoted 1 line

That is, if we can't migrate the page, try to write it out?

I just didnt understand the logic very well, maybe I should just go reread the code.

Quoted 8 lines

Quoted 1 line

Quoted 1 line

Thanks!

I'm thinking about how to implement a nonblocking version of generic_migrate_page().

For this purpose its really bad to allocate swap space to anonymous pages, well need to figure out someother way of blocking the users via pagetablefault.

Like a "virtual" swap space but without allocating swap map space.

I've also ever thought to implement such a device. It would be nice if you can design it simple.

Mr.Iwamoto thought otherwise and posted another opinion on the lhms list, though. I felt it also has a point.

iwamoto> I don't think requiring swap is a big deal. If you don't have a iwamoto> dedicated swap device, which case I think unusual, you can swapon a iwamoto> regular file.

Quoted 3 lines

Sure its not a big deal, but nicer if it doesnt require swap.

For memory defragmentation it is a big deal.

Why? IMO, it isn't very rewarding to tune memory migration/defragmentation performance as they involve memory copy anyway.

Or, do you want memory defragmentation everywhere, including embedded systems?

It will be much faster and not interfere with swap space.

I'll use one bit of "swap type" to identify such "migration pte's".

I'll test it with memory migration operation first then with memory defragmentation.

Hope it works fine.

struct idr migration_idr;
struct address_space migration_space = {

        .page_tree      = RADIX_TREE_INIT(GFP_ATOMIC),
        .tree_lock      = RW_LOCK_UNLOCKED,
        .a_ops          = NULL,
        .flags          = GFP_HIGHUSER,

.i_mmap_nonlinear = LIST_HEAD_INIT(migration_space.i_mmap_nonlinear), .backing_dev_info = NULL,
};

int init_migration_cache(void)

{
	idr_init(&migration_idr);

	printk(KERN_INFO "Initializating migration cache!\n");

}

__initcall(init_migration_cache);

struct page *lookup_migration_cache(int id) { 
	return find_get_page(&migration_space, id);
}

int remove_from_migration_cache(struct page *page, int id)

{
	write_lock_irq(&migration_space.tree_lock);
        idr_remove(&migration_idr, id);
	radix_tree_delete(&migration_space.page_tree, id);
	write_unlock_irq(&migration_space.tree_lock);
}

int add_to_migration_cache(struct page *page)

{
	int error, offset;
	int gfp_mask = GFP_KERNEL;

	BUG_ON(PageSwapCache(page));
	BUG_ON(PagePrivate(page));

        if (idr_pre_get(&migration_idr, GFP_ATOMIC) == 0)
                return -ENOMEM;

	error = radix_tree_preload(gfp_mask);

	if (!error) {
		write_lock_irq(&migration_space.tree_lock);
	        error = idr_get_new(&migration_idr, NULL, &offset);

		error = radix_tree_insert(&migration_space.page_tree, offset,
							page);

		if (!error) {
			page_cache_get(page);
			SetPageLocked(page);
			page->private = offset;
			page->mapping = &migration_space;

		}
		write_unlock_irq(&migration_cache.tree_lock);
                radix_tree_preload_end();

	}

	return error;
}

Quoted 5 lines

Quoted 3 lines

iwamoto> I don't think requiring swap is a big deal. If you don't have a iwamoto> dedicated swap device, which case I think unusual, you can swapon a iwamoto> regular file.

Sure its not a big deal, but nicer if it doesnt require swap.

Quoted 1 line

For memory defragmentation it is a big deal.

Why? IMO, it isn't very rewarding to tune memory migration/defragmentation performance as they involve memory copy anyway.

Or, do you want memory defragmentation everywhere, including embedded systems?

Quoted 12 lines

Quoted 7 lines

Quoted 3 lines

iwamoto> I don't think requiring swap is a big deal. If you don't have a iwamoto> dedicated swap device, which case I think unusual, you can swapon a iwamoto> regular file.

Sure its not a big deal, but nicer if it doesnt require swap.

For memory defragmentation it is a big deal.

Why? IMO, it isn't very rewarding to tune memory migration/defragmentation performance as they involve memory copy anyway.

Quoted 2 lines

Or, do you want memory defragmentation everywhere, including embedded systems?

Lots of systems nowadays don't have swap configured, not just embedded. What do we gain from making defrag slower and harder to use, by forcing it to use swap? Isn't pushing it into the swapcache sufficient?

Lots of systems nowadays don't have swap configured, not just embedded. What do we gain from making defrag slower and harder to use, by forcing it to use swap? Isn't pushing it into the swapcache sufficient?

Quoted 14 lines · Hirokazu Takahashi

Quoted 14 lines

2)
At migrate_onepage you add anonymous pages which aren't swap allocated to the swap cache

(quoted diff) +10 -0

+       /*
+        * Put the page in a radix tree if it isn't in the tree yet.
+        */
+#ifdef CONFIG_SWAP
+       if (PageAnon(page) && !PageSwapCache(page))
+               if (!add_to_swap(page, GFP_KERNEL)) {
+                       unlock_page(page);
+                       return ERR_PTR(-ENOSPC);
+               }
+#endif /* CONFIG_SWAP */

Quoted 7 lines

Quoted 2 lines

Why's that? You can copy anonymous pages without adding them to swap (thats what the patch I posted does).

The reason is to guarantee that any anonymous page can be migrated anytime. I want to block newly occurred accesses to the page during the migration because it can't be migrated if there remain some references on it by system calls, direct I/O and page faults.

It would be nice if we could block pte faults in a way such to not need adding each anonymous page to swap. It can be too costly if you have a lot memory and it makes the whole operation dependable on swap size (if you dont have enough swap, you're dead).

Maybe hold mm->page_table_lock (might be too costly in terms of CPU time, but since migration is not a common operation anyway), or create a semaphore?

Quoted 2 lines

Questions: are there any documents on the memory hotplug userspace tools? Where can I find them?

IBM guys and Fujitsu guys are designing user interface independently. IBM team is implementing memory section hotplug while Fujitsu team try to implement NUMA node hotplug. But both of the designs use regular hot-plug mechanism, which kicks /sbin/hotplug script to control devices via sysfs.

Dave, would you explain about it?

Hi,

Quoted 13 lines

Quoted 4 lines

Quoted 2 lines

Cool. I'll take a closer look at the relevant parts of memory hotplug patches this weekend, hopefully. See if I can help with testing of these patches too.

Any comments are very welcome.

I have a few comments about the code:

1)
I'm pretty sure you should transfer the radix tree tag at radix_tree_replace(). If for example you transfer a dirty tagged page to another zone, an mpage_writepages() will miss it (because it uses pagevec_lookup_tag(PAGECACHE_DIRTY_TAG)).

Quoted 4 lines

Should be quite trivial to do (save tags before deleting and set to new entry, all in radix_tree_replace).

My implementation also contained the same bug.

Yes, it's one of the issues to do. The tag should be transferred in radix_tree_replace() as you pointed out. The current implementation sets the tag in set_page_dirty(newpage).

I still need to figure out how to use Iwamoto's patch to add/remove zone's on the fly (for testing the migration process).

Quoted 8 lines

Quoted 8 lines

1)
I'm pretty sure you should transfer the radix tree tag at radix_tree_replace(). If for example you transfer a dirty tagged page to another zone, an mpage_writepages() will miss it (because it uses pagevec_lookup_tag(PAGECACHE_DIRTY_TAG)).

Should be quite trivial to do (save tags before deleting and set to new entry, all in radix_tree_replace).

Quoted 5 lines

Quoted 1 line

My implementation also contained the same bug.

Yes, it's one of the issues to do. The tag should be transferred in radix_tree_replace() as you pointed out. The current implementation sets the tag in set_page_dirty(newpage).

OK, guys, can you test this please?

This transfer the dirty radix tree tag at radix_tree_replace, avoiding a potential miss on tag-lookup. We could also copy all bits representing the valid tags for this node in the radix tree.

But this uses the available interfaces from radix-lib.c. In case a new tag gets added, radix_tree_replace() will have to know about it.

Pretty straightforward.

I still need to figure out how to use Iwamoto's patch to add/remove zone's on the fly (for testing the migration process).

diff -Nur linux-2.6.9-rc2-mm4.mhp.orig/include/linux/radix-tree.h linux-2.6.9-rc2-mm4/include/linux/radix-tree.h

include/linux/radix-tree.h +8 -0

@@ -68,9 +68,17 @@
 radix_tree_replace(struct radix_tree_root *root,
 				unsigned long index, void *item)
 {
+	int dirty;
+
+	dirty = radix_tree_tag_get(root, index, PAGECACHE_TAG_DIRTY);
+
 	if (radix_tree_delete(root, index) == NULL)
 		return -1;
 	radix_tree_insert(root, index, item);
+
+	if (dirty)
+		radix_tree_tag_set(root, index, PAGECACHE_TAG_DIRTY);
+
 	return 0;
 }
 

diff -Nur linux-2.6.9-rc2-mm4.mhp.orig/lib/radix-tree.c linux-2.6.9-rc2-mm4/lib/radix-tree.c

lib/radix-tree.c +0 -3

@@ -443,7 +443,6 @@
 }
 EXPORT_SYMBOL(radix_tree_tag_clear);
 
-#ifndef __KERNEL__	/* Only the test harness uses this at present */
 /**
  *	radix_tree_tag_get - get a tag on a radix tree node
  *	@root:		radix tree root

@@ -495,7 +494,6 @@
 	}
 }
 EXPORT_SYMBOL(radix_tree_tag_get);
-#endif
 
 static unsigned int
 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
--

To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Quoted 10 lines

Quoted 10 lines

Quoted 9 lines

1)
I'm pretty sure you should transfer the radix tree tag at radix_tree_replace(). If for example you transfer a dirty tagged page to another zone, an mpage_writepages() will miss it (because it uses pagevec_lookup_tag(PAGECACHE_DIRTY_TAG)).

Should be quite trivial to do (save tags before deleting and set to new entry, all in radix_tree_replace).

My implementation also contained the same bug.

Quoted 5 lines

Quoted 3 lines

Yes, it's one of the issues to do. The tag should be transferred in radix_tree_replace() as you pointed out. The current implementation sets the tag in set_page_dirty(newpage).

OK, guys, can you test this please?

Ok, I'll test it.

Quoted 6 lines

This transfer the dirty radix tree tag at radix_tree_replace, avoiding a potential miss on tag-lookup. We could also copy all bits representing the valid tags for this node in the radix tree.

But this uses the available interfaces from radix-lib.c. In case a new tag gets added, radix_tree_replace() will have to know about it.

Yeah. I guess it would be better to copy the radix_tree_delete() code to radix_tree_replace() and modify it to replace items directly in the future.

Hi, Marcelo.

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

Quoted 9 lines

1)
I'm pretty sure you should transfer the radix tree tag at radix_tree_replace(). If for example you transfer a dirty tagged page to another zone, an mpage_writepages() will miss it (because it uses pagevec_lookup_tag(PAGECACHE_DIRTY_TAG)).

Should be quite trivial to do (save tags before deleting and set to new entry, all in radix_tree_replace).

My implementation also contained the same bug.

Quoted 7 lines

Quoted 5 lines

Quoted 3 lines

Yes, it's one of the issues to do. The tag should be transferred in radix_tree_replace() as you pointed out. The current implementation sets the tag in set_page_dirty(newpage).

OK, guys, can you test this please?

Ok, I'll test it.

It was sad that the patch couldn't be compiled because PAGECACHE_TAG_DIRTY macro depended on the filesystem code. I think radix_tree library shouldn't use it.

So that it would be better to make radix_tree_replace() accept tags to be inherited or make the function from scratch.
So I decided to re-implement it and I'm testing it now.

Quoted 10 lines

Quoted 6 lines

This transfer the dirty radix tree tag at radix_tree_replace, avoiding a potential miss on tag-lookup. We could also copy all bits representing the valid tags for this node in the radix tree.

But this uses the available interfaces from radix-lib.c. In case a new tag gets added, radix_tree_replace() will have to know about it.

Yeah. I guess it would be better to copy the radix_tree_delete() code to radix_tree_replace() and modify it to replace items directly in the future.

void *radix_tree_replace(struct radix_tree_root *root,
unsigned long index, void *item)

{
        struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
        unsigned int height, shift;
        void *ret = NULL;

        height = root->height;
        if (index > radix_tree_maxindex(height))
                goto out;

        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
        pathp->node = NULL;
        pathp->slot = &root->rnode;

        while (height > 0) {
                int offset;

                if (*pathp->slot == NULL)
                        goto out;

                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                pathp[1].offset = offset;
                pathp[1].node = *pathp[0].slot;
                pathp[1].slot = (struct radix_tree_node **)
                                (pathp[1].node->slots + offset);
                pathp++;
                shift -= RADIX_TREE_MAP_SHIFT;

                height--;
        }

        if ((ret = *pathp[0].slot))
                *pathp[0].slot = item;
out:
        return ret;
}

On Sat, Oct 02, 2004 at 06:30:15PM +0900, Hirokazu Takahashi wrote:
3) At migrate_page_common you assume additional page references (page_migratable returning -EAGAIN) means the code should try to writeout the page.

Is that assumption always valid?

In theory there is no need to writeout pages when migrating them to other zones - they will be copied and the dirty information retained (either in the PageDirty bit or radix tree tag).

I just noticed you do that on further patches (migrate_page_buffer), but AFAICS the writeout remains. Why arent you using migrate_page_buffer yet?

I think the final aim should be to remove the need for "pageout()" completly.

Questions: are there any documents on the memory hotplug userspace tools? Where can I find them?

Are Iwamoto's test programs available?

At Sat, 2 Oct 2004 15:33:49 -0300,

Quoted 6 lines · Marcelo Tosatti

On Sat, Oct 02, 2004 at 06:30:15PM +0900, Hirokazu Takahashi wrote:
3) At migrate_page_common you assume additional page references (page_migratable returning -EAGAIN) means the code should try to writeout the page.

Quoted 5 lines

Is that assumption always valid?

In theory there is no need to writeout pages when migrating them to other zones - they will be copied and the dirty information retained (either in the PageDirty bit or radix tree tag).

It's true only when page->private is NULL. Otherwise writeback is necessary to free buffer_head.

Quoted 5 lines

I just noticed you do that on further patches (migrate_page_buffer), but AFAICS the writeout remains. Why arent you using migrate_page_buffer yet?

I think the final aim should be to remove the need for "pageout()" completly.

Are you going to implement migrate_page_buffer for every file system? I don't think it's worthwhile.

Quoted 3 lines

Questions: are there any documents on the memory hotplug userspace tools? Where can I find them?

Quoted 1 line

Are Iwamoto's test programs available?

I've put them at the following URL, but I doubt they are useful for you; there are no documentation for them.

http://people.valinux.co.jp/~iwamoto/mh/tests/

With such a thing in place we can build a mechanism for kswapd (or a separate kernel thread, if needed) to notice when we are low on high order pages, and use the coalescing algorithm instead blindly freeing unique pages from LRU in the hope to build large physically contiguous memory areas.

Comments appreciated.

Quoted 10 lines · Marcelo Tosatti

With such a thing in place we can build a mechanism for kswapd (or a separate kernel thread, if needed) to notice when we are low on high order pages, and use the coalescing algorithm instead blindly freeing unique pages from LRU in the hope to build large physically contiguous memory areas.

Comments appreciated.

Hi Marcelo,
Seems like a good idea... even with regular dumb kswapd "merging", you may easily get stuck for example on systems without swap...

Anyway, I'd like to get those beat kswapd patches in first. Then your mechanism just becomes something like:

   if order-0 pages are low {
       try to free memory
   }
   else if order-1 or higher pages are low {
        try to coalesce_memory
        if that fails, try to free memory
   }

Quoted 17 lines · Nick Piggin

Quoted 6 lines · Marcelo Tosatti

With such a thing in place we can build a mechanism for kswapd (or a separate kernel thread, if needed) to notice when we are low on high order pages, and use the coalescing algorithm instead blindly freeing unique pages from LRU in the hope to build large physically contiguous memory areas.

Comments appreciated.

Hi Marcelo,
Seems like a good idea... even with regular dumb kswapd "merging", you may easily get stuck for example on systems without swap...

Anyway, I'd like to get those beat kswapd patches in first. Then your mechanism just becomes something like:

Quoted 8 lines

  if order-0 pages are low {
      try to free memory
  }
  else if order-1 or higher pages are low {
       try to coalesce_memory
       if that fails, try to free memory
  }

Hi Nick!

I understand that kswapd is broken, and it needs to go into the page reclaim path to free pages when we are out of high order pages (what your "beat kswapd" patches do and fix high-order failures by doing so), but Linus's argument against it seems to be that "it potentially frees too much pages" causing harm to the system. He also says this has been tried in the past, with not nice results.

And that is why its has not been merged into mainline.

Is my interpretation correct?

But right, kswapd needs to get fixed to honour high order pages.

For example it doesnt re establishes pte's once it has unmapped them.

Quoted 3 lines

For example it doesnt re establishes pte's once it has unmapped them.

Another thing - I don't know if I'd bother re-establishing ptes.... I'd say just leave it to happen lazily at fault time.

Quoted 4 lines · Marcelo Tosatti

For example it doesnt re establishes pte's once it has unmapped them.

Another thing - I don't know if I'd bother re-establishing ptes.... I'd say just leave it to happen lazily at fault time.

page_alloc.c renamed from page_alloc.c.orig +2 -0

+int coalesce_memory(unsigned int order, struct zone *zone)
+{

page_alloc.c renamed from page_alloc.c.orig +12 -0

+forward:
+
+			pwalk = page;
+
+			/* Look forward, skipping the page frames from this 
+			  high order page we are looking at */
+
+			for (walkcount = (1UL << torder); walkcount<nr_pages; 
+					walkcount++) {
+				pwalk = page+walkcount;
+
+				ret = can_move_page(pwalk);

how about inserting this if-sentense ?

page_alloc.c renamed from page_alloc.c.orig +2 -0

+int can_move_page(struct page *page) 
+{

Hi memory hotplug fellows,

Just in case you dont know, trying to pass "mem="
causes the -test2 tree to oops on boot.

Any ideas of what is going on wrong?

Haven't captured the oops, but can
if needed.

Quoted 6 lines · Marcelo Tosatti

Hi memory hotplug fellows,

Just in case you dont know, trying to pass "mem="
causes the -test2 tree to oops on boot.

Any ideas of what is going on wrong?

Nope. That's my normal mode of operation. What kind of system? How much RAM?

I've only tried it where the machine has 4G of ram, and I restrict it down to 2. I can imagine some funny stuff happening if the mem= causes it to cross the highmem boundary.

Quoted 2 lines

Haven't captured the oops, but can
if needed.

Let me do a bit of testing after I find out what your configuration is. I'm hopeful I can reproduce it.

mem=128M or mem=256M made it crash. Keep me posted.