CVS commit: [netbsd-9] src/sys/uvm

["Martin Husemann" <martin%netbsd.org@localhost>]

Module Name:    src
Committed By:   martin
Date:           Sat Aug 24 08:24:36 UTC 2024

Modified Files:
        src/sys/uvm [netbsd-9]: uvm_map.c

Log Message:
Pull up following revision(s) (requested by riastradh in ticket #804):

        sys/uvm/uvm_map.c: revision 1.423 (patch)
        sys/uvm/uvm_map.c: revision 1.425 (patch)

uvm_map(9): Make sure search in the nearest gap is monotonic.

The algorithm, on a hint clamped to the VM bounds, works as follows
(assuming topdown VM):

1. Make sure the hint is aligned, by subtracting the remainderin
   uvm_map_align_va.
2. If the hint is equal to the VM max, try the first free gap.
3. If the hint is not equal to the VM max, but is already in use, try
   the next gap _below_ the entry covering hint.
4. If the hint is not equal to the VM max and is not already in use,
   try gap between the entry below hint and the next entry after it,
   above hint.

In the last case, `entry' is the one below hint, and `entry->next' is
the one above it.  We would take
        entry->next->start - length
as the next candidate hint.

However, this algorithm is supposed to be a monotonic search through
the address space, and we might wind up with something like:

[0x7defb000,0x7defc000)         entry above hint (entry->next)
0x77895000                      hint
[0x77894000,0x77895000)         entry below hint (entry)

In this case, if length=0x1000, we would take
        0x7defb000 - 0x1000 = 0x7defa000
as the next candidate hint, but this violates monotonicity of the
search.

Instead, take the _smallest_ of orig_hint or entry->next->start -
length, to avoid violating monotonicity, so hint <= orig_hint.

I didn't commit this change before because it didn't seem to fix all
the manifestations of the problem, but we have more diagnostics now
so maybe we will find there is a _different_ violation of the same
invariants once this is committed -- and I'm pretty sure this change
is necessary to guarantee monotonicity in some cases (but I'm still
not sure why we're only hitting the problem on sh3).

PR kern/51254: uvm assertion "!topdown || hint <= orig_hint" failed
uvm_map(9): Apply the same orig_hint clamp again to the same entry.

Previous change dealt with case like length=0x1000 and:

[0x7defb000,0x7defc000)         entry above orig_hint (entry->next)
0x77895000                      orig_hint
[0x77894000,0x77895000)         entry below orig_hint (entry)

by changing
        entry->next->start - length
to
        MIN(orig_hint, entry->next->start - length)

in order to enforce monotonicity of search.

In this case, if the tree search for a gap has failed, we retry with
a list search with exactly the same orig_hint and entry -- nothing
has changed them (only hint and tmp).  So apply the same clamping.

PR kern/51254: uvm assertion "!topdown || hint <= orig_hint" failed


To generate a diff of this commit:
cvs rdiff -u -r1.362.2.5 -r1.362.2.6 src/sys/uvm/uvm_map.c

Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.