uvm_map_fill_vmmap lets callers specify an address after which they are
interested in entries. generally theyre interested in addresses after 0, but if
you start further along the address space the lookup has to traverse the
addresses looking for it.
this can be optimised by borrowing the red-black tree nfind semantic
to do a binary search for the starting point. it's the same cost
for searching for the first (0th) address, but is much faster for
other starting points.
im doing the nfind by hand so i dont have to put a vmentry on the
stack to pass to an actual RBT_NFIND call.
ok?
Index: uvm_map.c
===================================================================
RCS file: /cvs/src/sys/uvm/uvm_map.c,v
retrieving revision 1.225
diff -u -p -r1.225 uvm_map.c
--- uvm_map.c 16 Sep 2016 02:35:42 -0000 1.225
+++ uvm_map.c 5 Oct 2016 00:27:05 -0000
@@ -5215,7 +5215,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;
@@ -5233,13 +5233,22 @@ 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;
@@ -5253,8 +5262,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);
