Compound page overhaul

The attached patch overhauls compound page handling.

(1) A new bit flag PG_compound_slave has been added. This is used to mark the second+ subpages of a compound page, thus making get_page() and put_page() able to determine the need to perform weird stuff quickly. This could be changed to do horribly things with the page count or to abuse the page->lru member instead of eating another page flag.

(2) Compound page metadata is now always set on high-order pages when allocating and always checked when freeing:
- PG_compound is set on all subpages
- PG_compound_slave is set on all but the first subpage
- page[1].index holds the compound page order
- page[1...N-1].private points to page[0]
- page[1].mapping may hold a destructor function for put_page()
This is now done in prep_new_page().

(3) __page_first() is now provided to find the first page of any page set (even single page sets).

(4) A new config option ENHANCED_COMPOUND_PAGES is now available. This is only set on !MMU or HUGETLB_PAGE. It causes __page_first() to dereference page->private if PG_compound_slave is set.
(5) __GFP_COMP is no longer required since compound metadata is always now set.

(6) compound_page_order() is now available. This will indicate the order of any page, high-order or not.
Since it is now trivial to work out the order of any page, free_pages() and co could all lose their order arguments.

(7) Trailing spaces have been cleaned up on lines in page_alloc.c.

(8) bootmem.c now has a separate path to release pages to the main allocator that bypasses many of the checks performed on struct pages. bootmem.c's page releaser could be improved by giving the boot allocator's bitmap sufficient bits to make sure bit 0 is 32-page or 64-page aligned (depending on bits/long), even if the page to which it corresponds doesn't actually exist.

(9) bad_page() now prints more information, including information about more pages in the case of a compound page.
(10) prep_compound_page() and destroy_compound_page() have been absorbed.

(11) A lot more unlikely() clauses have been inserted in the free page checking functions.

(12) The !MMU bits have all gone from page_alloc.c.
(13) __pagevec_free() has moved to swap.c with all the other pagevec functions.
(14) put_page() has moved to page_alloc.c with all the other related functions. This could be relegated to a separate file, but since there are many other conditionals in page_alloc.c, what's the point?

Quoted 2 lines

(1) A new bit flag PG_compound_slave has been added. This is used to mark
...

There are a lot of ways to do these things. Most of it is bitpacking and dodging assumptions in other code about various fields always being something or other they expect (e.g. bh's vs. page->private).

A generally innocuous rearrangement. Some explanation of the advantage of these new bitpacking and field arrangements over the current arrangement may be good to have.

Quoted 2 lines

(3) __page_first() is now provided to find the first page of any page set (even single page sets).

I have to question the underscores.

Also, there's a commonly-used term in the superpage literature, ``head of the superpage'', that may be more easily recognizable for readers familiar with that but not Linux specifics, but that's just nomenclature and not particularly pressing or any kind of requirement, just a non-Linux precedent.

__GFP_COMP was introduced because several unusual drivers allocate higher-order pages and then move on to free fragments of them. There's a small danger some others may allocate higher-order pages and then treat each piece as a separate entity (particularly in the freeing pass).

Sweeping affected drivers to use a fragmenting primitive may help here.

Quoted 1 line

(6) compound_page_order() is now available. This will indicate the order

...
Possible, but it's likely a micro-optimization to cache the order in registers across function calls. The allocator is something of a ``hot path'' and small alterations can have noticeable effects.

Quoted 1 line

(7) Trailing spaces have been cleaned up on lines in page_alloc.c.

I like this quite a bit. =)

Quoted 2 lines

(8) bootmem.c now has a separate path to release pages to the main allocator

...
Clearly it could merely scan the bitmap for the largest properly-sized, properly-aligned leading run of free bits beyond even that, though I wouldn't expect you to pursue that as it's far beyond the scope of the patch. I was hit up to deal with bootmem.c issues, and will be looking into that and more after the current set of bootmem changes has settled down and ia64 bootstrap has been stable for a while.

(2) The physaddr alignment comment in bootmem.c is mangled. It's not O(LOG2(BITS_PER_LONG)) -aligned, it's exactly LOG2(BITS_PER_LONG) aligned. But we don't have a LOG2(...) macro, we have fls()/ffs().

(3) page_count() probably deserves the %0*lx treatment in __bad_page(). Conserving screenspace when possible helps some, though that's offset a bit against predictable field alignment. Maybe putting variable-length fields at the end of the line would help.

Also, the pfn would be great to have there, too, while you're at it.

(4) I wonder if anyone's run with CONFIG_DEBUG_PAGEALLOC recently. bootmem.c seems a bit early for kernel_map_pages() et al. It could be okay depending.

(5) This patch does a fair number of different things and it takes a bit of effort to wade through some of the longer rearrangements as they overflow 80x24. It would be helpful for reviewers if you could break this down into a somewhat more easily-digestible series of smaller patches.

Quoted 3 lines

There are a lot of ways to do these things. Most of it is bitpacking and dodging assumptions in other code about various fields always being something or other they expect (e.g. bh's vs. page->private).

I want to avoid putting magic numbers in page->private. What goes in there could be anything, as it's up to the filesystem.
Do you have any preferences? I'd prefer to use page->mapping, I think, except that's used for the destructor.
I should probably make a set-destructor function for hugetlbfs to call.

Quoted 3 lines

A generally innocuous rearrangement. Some explanation of the advantage of these new bitpacking and field arrangements over the current arrangement may be good to have.

The only differences are:
(1) PG_compound_slave now exists.
(2) I'm permitting the owner of the page to do do what it will with

     page->private on the first page.

Quoted 5 lines

Also, there's a commonly-used term in the superpage literature, ``head of the superpage'', that may be more easily recognizable for readers familiar with that but not Linux specifics, but that's just nomenclature and not particularly pressing or any kind of requirement, just a non-Linux precedent.

I couldn't think of a good name for it, so I settled on it being the first page.
How about page_head()?

Quoted 5 lines

__GFP_COMP was introduced because several unusual drivers allocate higher-order pages and then move on to free fragments of them. There's a small danger some others may allocate higher-order pages and then treat each piece as a separate entity (particularly in the freeing pass). Sweeping affected drivers to use a fragmenting primitive may help here.

I wasn't aware of that. Looking at the mm code, doing a fragmentary release would cause bad_page() to be invoked. Presumably these drivers modify the various struct pages involved directly to keep the allocator happy. It would be better, I think, to provide a page splitter function. Thus allowing pages to be cut in half, and then have the two halves made into the equivalent allocated pages.
Do you know which drivers?

Quoted 3 lines

Possible, but it's likely a micro-optimization to cache the order in registers across function calls. The allocator is something of a ``hot path'' and small alterations can have noticeable effects.

Yes... but the order gets examined anyway in the free page checker, and the second plus page structs get modified too, so I don't think it'll make much of a difference. Plus the filesystem or driver that owned the page won't need to keep track of the size, nor will it need to calculate it.

Quoted 1 line

I like this quite a bit. =)

	(defun trim ()
	  "Delete trailing whitespace in buffer"
	  (interactive)
	  (save-excursion
	    (goto-char (point-min))
	    (replace-regexp "[ \t\r]+$" "")
	    (goto-char (point-max))
	    (skip-chars-backward "\n")
	    (if (not (eobp))
		(delete-region (1+ (point)) (point-max)))))

Quoted 6 lines

Clearly it could merely scan the bitmap for the largest properly-sized, properly-aligned leading run of free bits beyond even that, though I wouldn't expect you to pursue that as it's far beyond the scope of the patch. I was hit up to deal with bootmem.c issues, and will be looking into that and more after the current set of bootmem changes has settled down and ia64 bootstrap has been stable for a while.

I may look at doing this after this patch (or similar) goes in. If so, I'll send you the patch.

Quoted 3 lines

(2) The physaddr alignment comment in bootmem.c is mangled. It's not O(LOG2(BITS_PER_LONG)) -aligned, it's exactly LOG2(BITS_PER_LONG) aligned. But we don't have a LOG2(...) macro, we have fls()/ffs().

I suspect that's meant to be mathematical notation, not strictly compilable code, though I think there may be a missing "if" in it.

Quoted 4 lines

(3) page_count() probably deserves the %0*lx treatment in __bad_page(). Conserving screenspace when possible helps some, though that's offset a bit against predictable field alignment. Maybe putting variable-length fields at the end of the line would help.

I don't think that matters too much. This message should never be seen, after all...
That said, I think I should probably provide a 64-bit version too... some of the fields will have 16-char widths there.

Quoted 3 lines

(4) I wonder if anyone's run with CONFIG_DEBUG_PAGEALLOC recently. bootmem.c seems a bit early for kernel_map_pages() et al. It could be okay depending.

I can try it. BTW, should the free page checking be contingent on this option? Or maybe it should have its own option.

Quoted 5 lines

(5) This patch does a fair number of different things and it takes a bit of effort to wade through some of the longer rearrangements as they overflow 80x24. It would be helpful for reviewers if you could break this down into a somewhat more easily-digestible series of smaller patches.

It's a little tricky to break it up logically since it's mostly incredibly interrelated.
I could separate out some of the cleanups: rearrangement between files, trailing space splatting.

The attached patch overhauls compound page handling.

(1) A new bit flag PG_compound_slave has been added. This is used to mark the second+ subpages of a compound page, thus making get_page() and put_page() able to determine the need to perform weird stuff quickly.

This could be changed to do horribly things with the page count or to abuse the page->lru member instead of eating another page flag.

(2) Compound page metadata is now always set on high-order pages when allocating and always checked when freeing:

- PG_compound is set on all subpages
- PG_compound_slave is set on all but the first subpage
- page[1].index holds the compound page order
- page[1...N-1].private points to page[0]
- page[1].mapping may hold a destructor function for put_page()

ugh, sorry, I'd forgotten that !MMU needs to use the fields inside pages[1]. It seems that the !MMU requirement is in that case quite dissimilar from what compound pages are supposed to do. Perhaps we should just forget the whole thing and stick with the current design approach?

Andrew Morton <[email protected]>:

Quoted 4 lines

ugh, sorry, I'd forgotten that !MMU needs to use the fields inside pages[1]. It seems that the !MMU requirement is in that case quite dissimilar from what compound pages are supposed to do. Perhaps we should just forget the whole thing and stick with the current design approach?

Nonono... you misunderstand. Compound-pages support uses fields from page[1] to store extra data.

It's nothing at all to do with MMU vs !MMU.

Quoted 3 lines

ugh, sorry, I'd forgotten that !MMU needs to use the fields inside pages[1].

But !MMU really wants to treat that higher-order page as an array of zero-order pages, and that requires the usual usage of the fields of page[1], page[2], etc.

What are you saying?

Quoted 1 line

It's nothing at all to do with MMU vs !MMU.

In that case I just dunno what's going on now.
I thought we were discussing the removal of this, from __free_pages_ok():

#ifndef CONFIG_MMU
	if (order > 0)
		for (i = 1 ; i < (1 << order) ; ++i)
			__put_page(page + i);

#endif
by using compound page's refcounting logic instead. But !MMU really wants to treat that higher-order page as an array of zero-order pages, and that requires the usual usage of the fields of page[1], page[2], etc. So what I'm saying is "compound pages are designed for treating a higher-order page as a higher-order page. !MMU wants to treat a higher order page as an array of zero-order pages. Hence give up and stick with the current code".
What are you saying?

Quoted 2 lines

I had to fix it to make it work, but what's currently lurking in Andrew's tree seems more or less correct, just not necessarily safe.

Pardon my saying so, but "correct, but unsafe" sounds a bit oxymoronic. =)

Unless FRV is surprisingly more widely distributed than it appears, it's unclear it will do much to help the CONFIG_MMU=n testing level.

The MMU-less code appears to assume the refcounts of the tail pages will remain balanced, and elevates them to avoid the obvious disaster. But this looks rather broken barring some rather unlikely invariants.

I presume the patch is backing that out so refcounting works properly, or in the nomenclature above (for which there is a precedent) makes the refcount a superpage property uniformly across MMU and MMU-less cases.

It's unclear (to me) how the current MMU-less code works properly, at the very least.

It would appear to leak memory since there is no obvious guarantee the reference to the head page will be dropped when needed, though things may have intended to free the various tail pages.

i.e. AFAICT things really need to acquire and release references on the whole higher-order page as a unit for refcounting to actually work, regardless of MMU or no.

It may also be helpful for Greg Ungerer to help review these patches, as he appears to represent some of the other MMU-less concerns, and may have more concrete notions of how things behave in the MMU-less case than I myself do (hardware tends to resolve these issues, but that's not always feasible; perhaps an MMU-less port of a "normal" architecture would be enlightening to those otherwise unable to directly observe MMU-less behavior). In particular, correcting what misinterpretations in the above there may be.

So why did you create a "Compound page overhaul" in the first place? Was it not to address some insufficiency for !MMU?

The current compound page logic should handle that quite happily, no?

Quoted 3 lines

The MMU-less code appears to assume the refcounts of the tail pages will remain balanced, and elevates them to avoid the obvious disaster. But this looks rather broken barring some rather unlikely invariants.

I had to fix it to make it work, but what's currently lurking in Andrew's tree seems more or less correct, just not necessarily safe.

Quoted 2 lines

It's unclear (to me) how the current MMU-less code works properly, at the very least.

For the most part it's down to two !MMU bits in page_alloc.c - one sets all the refcounts on the pages of a high-order allocation, and the other decrements them all again during the first part of freeing.

Quoted 3 lines

It would appear to leak memory since there is no obvious guarantee the reference to the head page will be dropped when needed, though things may have intended to free the various tail pages.

Actually, it's more a problem of the "superpage" being freed when the subpages have elevated counts.

Quoted 8 lines

It may also be helpful for Greg Ungerer to help review these patches, as he appears to represent some of the other MMU-less concerns, and may have more concrete notions of how things behave in the MMU-less case than I myself do (hardware tends to resolve these issues, but that's not always feasible; perhaps an MMU-less port of a "normal" architecture would be enlightening to those otherwise unable to directly observe MMU-less behavior). In particular, correcting what misinterpretations in the above there may be.

The FRV arch does both MMU and !MMU versions. It's settable by a config option, and I check both.

Quoted 4 lines

Quoted 4 lines

ugh, sorry, I'd forgotten that !MMU needs to use the fields inside pages[1].

Perhaps I misunderstood what you meant here. I _assumed_ you meant that it used the bits of pages[1] for compound page metadata - which it now does only because it's now using compound pages (if only with my patch applied).

Quoted 3 lines

But !MMU really wants to treat that higher-order page as an array of zero-order pages, and that requires the usual usage of the fields of page[1], page[2], etc.

That's not really so. For the most part, !MMU linux treats pages identically to MMU linux, whether those pages are big or small.

It's only for interprocess userspace access that there's an issue, and the issue there is, I think, that access_process_vm() wants to pin the page in place to stop it going away whilst it is being fiddled with.

Normally, the page is pinned in place by its refcount and/or flags. However, for compound pages, the refcount in question is really on the first page of the batch, and so refcount accesses should be directed there, and not to a secondary page.

Quoted 1 line · David Howells

Quoted 1 line

It's nothing at all to do with MMU vs !MMU.

Quoted 6 lines · Andrew Morton

In that case I just dunno what's going on now.
I thought we were discussing the removal of this, from __free_pages_ok():

#ifndef CONFIG_MMU
	if (order > 0)
		for (i = 1 ; i < (1 << order) ; ++i)
			__put_page(page + i);

Quoted 9 lines

#endif
by using compound page's refcounting logic instead. But !MMU really wants to treat that higher-order page as an array of zero-order pages, and that requires the usual usage of the fields of page[1], page[2], etc. So what I'm saying is "compound pages are designed for treating a higher-order page as a higher-order page. !MMU wants to treat a higher order page as an array of zero-order pages. Hence give up and stick with the current code".
What are you saying?

The way I interpreted this is something like:

The usual way this goes (as I've seen it elsewhere) is that some fields are "base page properties", so each struct page in the subarray of mem_map the higher-order page represents can have some different, meaningful value for the field, and so on. Others are "superpage properties", which refer to the head of the higher-order page.

The MMU-less code appears to assume the refcounts of the tail pages will remain balanced, and elevates them to avoid the obvious disaster. But this looks rather broken barring some rather unlikely invariants. I presume the patch is backing that out so refcounting works properly, or in the nomenclature above (for which there is a precedent) makes the refcount a superpage property uniformly across MMU and MMU-less cases.

It's unclear (to me) how the current MMU-less code works properly, at the very least. It would appear to leak memory since there is no obvious guarantee the reference to the head page will be dropped when needed, though things may have intended to free the various tail pages.

i.e. AFAICT things really need to acquire and release references on the whole higher-order page as a unit for refcounting to actually work, regardless of MMU or no.

It may also be helpful for Greg Ungerer to help review these patches, as he appears to represent some of the other MMU-less concerns, and may have more concrete notions of how things behave in the MMU-less case than I myself do (hardware tends to resolve these issues, but that's not always feasible; perhaps an MMU-less port of a "normal" architecture would be enlightening to those otherwise unable to directly observe MMU-less behavior). In particular, correcting what misinterpretations in the above there may be.

The refcounting has been annoying me for a while, it just feels wrong. It has been done that way for a very long time (since 2.4.0 IIRC). I am sure there was more to it back in the 2.4 but I don't think we need to do it like this any more.

I don't have any problem with what David has done so far though I need to test it more extensively first.

Greg Ungerer <[email protected]>:

Quoted 4 lines

The refcounting has been annoying me for a while, it just feels wrong. It has been done that way for a very long time (since 2.4.0 IIRC). I am sure there was more to it back in the 2.4 but I don't think we need to do it like this any more.

It was like that in 2.4 also - where I first developed this arch and these mm changes. The refcount-on-free bug is there also. I don't know why no one else has hit it.

Quoted 2 lines

I don't have any problem with what David has done so far though I need to test it more extensively first.

That'd be great! :-)

I need to look at dumping my 2.4 arch & changes into the 2.4-uc kernels too.