For multipage allocation, start block scan at start of free range

[dougm]

Summary

Move the allocation of memory from vm_phys_alloc_queues_contig to vm_phys_alloc_contig, and rename the former to vm_phys_find_queues_contig.

In vm_phys_find_queues_contig, leave the fast allocation code here, but move the scanning-multiple-blocks allocation code to a new function, vm_phys_find_freelist_contig.

In vm_phys_alloc_freelist_contig, don't start walking a sequence of free blocks of a certain size except when it's the first in a sequence. Try to use the smaller free blocks that may precede that first free block as part of the allocation, if present and if alignment conditions allow.

[dougm]

Take those parts of D34729 that seem unobjectionable and leave them here, discarding the rest, so that testing and review of this change can proceed independently.

[pho]

I got a panic with this: https://people.freebsd.org/~pho/stress/log/log0278.txt

[dougm]

Perhaps there is something unhealthy about backing up over small blocks at the beginning. Blank that out and see if tests still fail.

[pho]

../../../vm/vm_phys.c:1360:6: error: unused variable 'order' [-Werror,-Wunused-variable]
        int order;
            ^
1 error generated.

The panic is gone with D34815.104837.patch

[dougm]

Restore the commented out code for capturing small initial blocks in the allocation. Change the code that frees small leftover blocks at the end so that it does not assume that the allocation must have started at the start of a big aligned block.

[pho]

D34815.104865.patch LGTM

[markj]

sys/vm/vm_phys.c

1389

As a general comment, we should be careful about truncation here: with 64KB pages and NFREEORDER = 13, we're very close to left-shifting a signed 32-bit int by 31. I suspect that this expression should always be written as (1ul << (PAGE_SHIFT + oind)).

1389

Do we assert somewhere that physical pages never have an address of zero? If not, we might want to be paranoid and check for underflow in the calculation of pa_prev.

1396

[dougm]

Alc comments, and objects, verbally. I recap:

The problem with backing up to the first tiny free block in a range of free blocks is that you may end up with an allocation that overlaps one more than the fewest possible number of max blocks that could satisfy the request. Using a free 4k just before the first max free block may only mean that you leave unallocated the last 4k of the last max free block of this free block range, and for that you've bound one extra max block in this allocation which, if this allocation is long lived, means that that max block will, for a very long time, not be able to be transformed into a max free block. Rather than worry about packing one allocation tight against another, worry about overlapping the fewest number of max blocks.

[dougm]

Address reviewer comments. Shift 1UL (instead of 1) and 2UL (instead of 2) in the code being modified here. This isn't making changes to code elsewhere to which the same concerns may apply. Add a zero-check before backing up from one address to its precesessor.

Only back up from the first max-block to include smaller blocks in the allocation when there is enough free space in that fragment to prevent the allocation from spilling over into an extra max-block at the other end.

[pho]

D34815.104986.patch also looks good to me.

[markj]

sys/vm/vm_phys.c

1389

Sorry for revising my suggestion, but 1ul is actually not correct in some cases, specifically i386 with PAE (where physical addresses are 64 bits but sizeof(unsigned long) is 4). ((vm_paddr_t)1 << (PAGE_SHIFT + oind)) is better.

1504

This check effectively means that we won't try merging allocations unless npages >= 16MB on amd64. Is that intentional?

[dougm]

Change the type of a shifted bit to vm_paddr_t.

sys/vm/vm_phys.c

1504

I don't intend to change, in this commit, when we try merging two adjacent blocks of the same size. We do that now when order >= VM_NFREEORDER.

In a proposed change that I have since cancelled, I sought to do that, but I realized that to do so in a way that would be approved would require a greater change to the control flow than I had proposed. I'll get back to that, but I thought this could be approved more quickly.