For multipage allocation, try assembling smaller blocks when big-enough free lists are empty

[dougm]

Summary

vm_phys_alloc_queues_contig tries assembling consecutive small free blocks into a range big enough to satisfy a multipage request only in the case when the multipage request is for more pages than can be allocated from any free list. Change it so that it can try the same thing for smaller allocation requests that find all big-enough free lists empty.

Move the freeing of extra pages from vm_phys_alloc_queues_contig to vm_phys_alloc_contig. Move the assembly of several blocks to make a multipage allocation from vm_phys_alloc_queues to a new function, vm_phys_alloc_freelist_contig.

[pho]

I ran a four hour test with the contigmalloc() tests in a loop. This followed by random stress2 tests for 4 hours. No problems seen.

[markj]

sys/vm/vm_phys.c

1351

Now, callers are responsible for clipping the returned range and returning the excess back to the freelists. I think this comment should mention that.

1453

I hadn't thought about this before, but I'm a bit surprised that we always 1) search the default freepool first, and 2) move returned pages to the default freepool instead of having the caller specify a pool as we do for single-page allocations. Maybe the reasoning is that contig allocations are rare enough that it doesn't matter?

1455

Does it make sense to skip this search if npages is a power of 2 and alignment >= npages?

1460

It's not obvious to me that it's advantageous to do this search here, as opposed to searching all vm_phys_segs first before falling back to order - 1-sized blocks. Were both possibilities considered (or is there some reason the alternative doesn't make sense)?

[dougm]

Rename some functions from 'alloc' to 'find', since they no longer alloc. Add a check to stop some searches doomed by alignment.

sys/vm/vm_phys.c

1351

Agreed. I'm renaming two functions from *alloc* to *find* to account for the fact that they don't actually manipulate the free lists anymore.

1453

Alc has tried to explain it to me, but I'll butcher any attempt to explain it to you.

All the pages allocated with this function are mapped. So they're in the default freepool already. Was that it? I'm not sure.

1455

If order < VM_NFREEORDER, sure.

1460

The current code tries every suitable block list for a segment, before giving up and trying the next segment. That choice means that the code might split a large block in segment 2, even when a smaller block in segment 1 has exactly the right size. According to alc, that choice was made because it is better to allocate blocks at higher addresses before blocks at lower addresses.

I did not consider the alternative you suggest, and probably should have, but the implementation here can be defended on the same grounds - it will find a solution in a higher segment before searching a lower one, and thus allocate higher addresses.

[pho]

I ran tests for 16 hours without seeing any problems with D34729.104761.patch

[dougm]

Abandoning this. Too much overlap with another outstanding patch may create confusion, and I need to rearrange some of the stuff here anyway.