Push the setting of a->entry->start down into dmar_gas_match_one. Add a documentary comment before that function.

Fix the upper limits passed to dmar_gas_match_one from dmar_gas_uppermatch.

Stop sending the prev entry to dmar_gas_match_insert. I was sending the prev entry sometimes and the next entry sometimes, but the insert function was only using them for assertion checking anyway.

Update assertion code to test first and last, rather than free_after.

Rework intel_gas.c more than I had planned. Along with free_down, keep a first and last value for each entry describing the least and greatest value in the subtree rooted there. Update these in the augment routine. In lowermatch, look for the fit with greatest address less than the lowaddr, which I understand to be an upper bound on the address. In uppermatch, duplicate the lowermatch code, looking for the fit with least address greater than highaddr, which I understand to be a lower bound on the address.

Correct the augmentation after RB_INSERT so that the newly inserted node is augmented too, before its parent.

In D23189#508661, @kib wrote:

If RB_ code would do the walk, I am fine with it.
Did you tested this on a machine with DMAR enabled ? You may ask Peter, long-running high-load networking tests exercise the GAS allocator quite efficiently.

Add an important omitted line.

Add comments.

Yes I think it should be fixed by r355985. At least, the bug fixed in r355985 could cause this panic. This is a VMIO buffer and so should contain managed pages.

In D22897#501357, @pho wrote:

With D22897.65888.diff I got this after 5 hours:

This approach has a fatal flaw. It may be impossible to distinguish parent from child without a complete search-from-root.

Remove #include <sys/lock.h> from tmpfs.h.

Add in the next planned change - the fix of the max_free test cases at the start of SPLAY_{LEFT,RIGHT}_STEP.

In D21964#500501, @neel_neelc.org wrote:

Sounds good, lets go with your patch then.
I closed my merge request on the GNOME GitLab.

In D21964#500456, @neel_neelc.org wrote:

@dougm Your patch surely does look cleaner than mine (I just needed something to unbreak the build), but are you sure it will work on 12.x and 11.x? If so, lets go with yours.
I built my patch to (hopefully) be compatible with 12.x and 11.x, so that's why it looks ugly, it has #ifdefs. I don't know if 12.x and below has vm_map_entry_read_succ().

In D21964#500392, @neel_neelc.org wrote:

I integrated your changes. Would the updated Ports/GNOME changes work?

In D21964#500356, @neel_neelc.org wrote:

I sent an updated patch to the GNOME people here: https://gitlab.gnome.org/GNOME/libgtop/merge_requests/12
I also have an fixed Bugzilla patch here: https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=242533

In D21964#500073, @pkubaj wrote:

This change broke devel/libgtop on powerpc64 (I didn't try amd64, it could also break there). The error is:

procmap.c:282:39: error: no member named 'next' in 'struct vm_map_entry'
        first = vmspace.vm_map.header.next;

A similar problem arose in lib/libprocstat/libprocstat.c and was
addressed in the most recent change to that file.  I'll look at this
problem tonight, and expect to find that a similar solution will suffice.

Rework the path compression so that there's no need to consider entries not strictly between entry and next_entry (or prev_entry).

Carefully pick the end-of-list marker before starting the walk toward a successor in clip_end.

Fix failure to update map->nentries. Fix problem updating max_free when entry and successor/predecessor are parent and child in the tree. Do path-halving when taking more than one step to find the successor/predecessor to avoid walking long paths when the same entry is clipped one piece at a time repeatedly.

Apply reviewer's suggestions.

Resolve merge conflicts.

Completing the threading of the vm_map splay tree makes this pointless.

In D22324#490910, @kib wrote:

I am somewhat curious how much does the upgrade succeed. Did you measured it ? E.g. the counters of total vm_pager_page_unswapped calls during buildworld vs. the number of times the lock needs to be upgraded vs. the number of successfull upgrades.

Make more clear that the new function is not used by the kernel.

In D22728#497480, @kib wrote:

I was bitten by use of seemingly kernel-only headers in userspace too many times. I believe that it is much better to not try to adapt vm/vm_map.h inlines to userspace, but have separate code in libprocstat, as Mark suggested.

Add comment. Change vm_map_entry_read_succ so that it leaves the next entry in vmentry, and doesn't only return the pointer to that entry.

In D22728#497468, @markj wrote:

I don't have an objection to this approach, but it's kind of unusual when compared with other routines which use libkvm. That is, I would just implement entry_read_succ directly in libprocstat. With this patch, libprocstat still embed details of the implementation (such as the fact that iteration terminates after visiting the header) so we still do not get a clean separation between userspace and the kernel, and vm_map_entry_read_succ() is harder to understand because of the indirection through "reader".

Fix compilation errors.

Update base to r355439. Stop passing dereferenced pointers to SPLAY_{LEFT,RIGHT}_STEP macros, since it seems that the compiler can't avoid extra operations for possible aliasing.

In D21964#496486, @markj wrote:

Thanks. To be clear, "old" is unmodified sources, "new" is the patch but with next and prev pointers retained, and "new, thread-only" is this patch?

In D21964#495950, @markj wrote:

How are you collecting performance counters in your benchmark? Would it also be possible to collect branch miss and CPI statistics?

With the attached simple test program, compiled with -O3, the results without and with DM defined are:

Apply reviewer suggestions. Modify SPLAY_{LEFT,RIGHT}_STEP to address performance issues. Update timing results. More than have the time lost is recovered. The rest is likely due to the cost of successor and predecessor.

Update to account for the fact that several parts originally in this patch have now been checked in. They were the parts that let me show a little time improvement, and what's left here, about nothing but threading the tree, will probably give back some of that time saved. I'll update the timing results and cache miss results in a while.

Incrementing the nupdates counter, which matters only when DIAGNOSTICS is #defined, fell out of the previous version. Add it back in, in a new and better place.

In D22544#493747, @alc wrote:

Can you explain why this change reduces the number of L1 data cache misses?