optimise uvm_map_fill_vmmap with a binary search

[David Gwynne]

userland can ask for an array of a processes memory mappings via
sysctl, starting from a specified point. currently that starting
point is found by iterating over the mappings from start to finish,
but because the mappings are in an RBT we can do a binary search
instead.

ok?

Index: uvm_map.c
===================================================================
RCS file: /cvs/src/sys/uvm/uvm_map.c,v
retrieving revision 1.231
diff -u -p -r1.231 uvm_map.c
--- uvm_map.c   17 May 2017 08:13:33 -0000      1.231
+++ uvm_map.c   20 Jun 2017 00:35:50 -0000
@@ -5211,7 +5211,7 @@ int
 uvm_map_fill_vmmap(struct vm_map *map, struct kinfo_vmentry *kve,
     size_t *lenp)
 {
-       struct vm_map_entry *entry;
+       struct vm_map_entry *entry = NULL, *tmp;
        vaddr_t start;
        int cnt, maxcnt, error = 0;
 
@@ -5229,13 +5229,21 @@ uvm_map_fill_vmmap(struct vm_map *map, s
        start = (vaddr_t)kve[0].kve_start;
 
        vm_map_lock(map);
-       RBT_FOREACH(entry, uvm_map_addr, &map->addr) {
-               if (cnt == maxcnt) {
-                       error = ENOMEM;
+       /* look for the starting address by doing nfind (by hand) */
+       tmp = RBT_ROOT(uvm_map_addr, &map->addr);
+       while (tmp != NULL) {
+               if (start < tmp->start) {
+                       entry = tmp;
+                       tmp = RBT_LEFT(uvm_map_addr, tmp);
+               } else if (start > tmp->start) {
+                       tmp = RBT_RIGHT(uvm_map_addr, tmp);
+               } else { /* exact match */
+                       entry = tmp;
                        break;
                }
-               if (start != 0 && entry->start < start)
-                       continue;
+       }
+
+       while (entry != NULL) {
                kve->kve_start = entry->start;
                kve->kve_end = entry->end;
                kve->kve_guard = entry->guard;
@@ -5249,8 +5257,14 @@ uvm_map_fill_vmmap(struct vm_map *map, s
                kve->kve_advice = entry->advice;
                kve->kve_inheritance = entry->inheritance;
                kve->kve_flags = entry->flags;
+
+               if (++cnt == maxcnt) {
+                       error = ENOMEM;
+                       break;
+               }
+
                kve++;
-               cnt++;
+               entry = RBT_NEXT(uvm_map_addr, entry);
        }
        vm_map_unlock(map);