CVS commit: src/sys/uvm

["Taylor R Campbell" <riastradh%netbsd.org@localhost>]

Module Name:    src
Committed By:   riastradh
Date:           Wed Aug 14 21:05:11 UTC 2024

Modified Files:
        src/sys/uvm: uvm_map.c

Log Message:
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


To generate a diff of this commit:
cvs rdiff -u -r1.422 -r1.423 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.